{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/19672"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/19672","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Design, diagnosis and reconfiguration of defect-tolerant VLSI","abstract":"This thesis examines three specific issues of defect-tolerant VLSI: (1) design and reconfiguration of defect-tolerant linear arrays, (2) diagnosis and reconfiguration of memory chips with spare rows/columns, and (3) optimal diagnosis procedures for k-out-of-n structures.","abstract_html":"This thesis examines three specific issues of defect-tolerant VLSI: (1) design and reconfiguration of defect-tolerant linear arrays, (2) diagnosis and reconfiguration of memory chips with spare rows/columns, and (3) optimal diagnosis procedures for k-out-of-n structures.","abstract_has_math":false,"creators":["Chang, Ming-Feng"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Fuchs, W. Kent"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T12:14:50Z","date_published":"2011-05-07T12:14:50Z","updated_at":"2026-07-22T22:25:14Z","subjects":["Engineering, Electronics and Electrical","Computer Science"],"languages":["eng"],"rights":["Copyright 1991 Chang, Ming-Feng"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9124391","(UMI)AAI9124391"],"render_values":[{"text":"AAI9124391","href":null,"code":true},{"text":"(UMI)AAI9124391","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/19672","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Fuchs, W. Kent"]},{"key":"dc:creator","label":"Author","values":["Chang, Ming-Feng"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T12:14:50Z","10000-01-01","1991"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Engineering, Electronics and Electrical","Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1991 Chang, Ming-Feng"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9124391","(UMI)AAI9124391","http://hdl.handle.net/2142/19672"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["This thesis examines three specific issues of defect-tolerant VLSI: (1) design and reconfiguration of defect-tolerant linear arrays, (2) diagnosis and reconfiguration of memory chips with spare rows/columns, and (3) optimal diagnosis procedures for k-out-of-n structures.","In Chapter 2, design and reconfiguration approaches for high harvest rates and high performance of linear arrays are described. Our design is an extension of the loop-based approach developed by Horst. The defect-tolerant designs allow each cell to interconnect with up to eight neighbors, and maintain a constant wire length between any two logically adjacent cells independent of fault distribution. A reconfiguration strategy is developed to improve the harvest rate of loop-based approaches. The problem complexity of harvesting the maximum number of fault-free cells is analyzed and a heuristic reconfiguration algorithm is presented.","In Chapter 3, the problem of diagnosis and spare allocation for random access memory with coupling faults is investigated. Both diagnosis and repair of coupling faults by utilizing spare rows and columns are examined. We show that a coupling fault is repaired if its coupling cell is replaced by utilizing a spare row or its coupled cell is replaced by utilizing a spare row or column. By specifying both the coupled cell and coupling cell, the amount of redundancy required to repair a given set of faults may be reduced. A diagnosis procedure for RAM is provided to locate stuck-at faults as well as coupling faults, and a repair procedure has been implemented to allocate rows and columns for repair. A graph model is employed to describe the repair of coupling faults.","In Chapter 4, optimal diagnosis procedures of k-out-of-n structures are described. Knowledge of the probability of each unit being good and the expected test time of each unit are used by the diagnosis algorithm to select units for testing. The general problem of optimal diagnosis is described followed by an examination of diagnosis for k-out-of-n structures. The optimal diagnosis of k-out-of-n systems is presented along with a complete proof. A compact representation of the optimal diagnosis scheme which needs $O$($n\\sp2$) space and can be generated in $O$($n\\sp2$) time is also described.","Made available in DSpace on 2011-05-07T12:14:50Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9124391.pdf: 3312078 bytes, checksum: 2a4daf8519a530791c06af57e0a1fe3d (MD5) Previous issue date: 1991","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:38:39Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:16:08-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"]},{"key":"dc:title","label":"Title","values":["Design, diagnosis and reconfiguration of defect-tolerant VLSI"]}]}],"canonical_facts":{"dc:contributor":["Fuchs, W. Kent"],"dc:creator":["Chang, Ming-Feng"],"dc:date":["2011-05-07T12:14:50Z","10000-01-01","1991"],"dc:description":["This thesis examines three specific issues of defect-tolerant VLSI: (1) design and reconfiguration of defect-tolerant linear arrays, (2) diagnosis and reconfiguration of memory chips with spare rows/columns, and (3) optimal diagnosis procedures for k-out-of-n structures.","In Chapter 2, design and reconfiguration approaches for high harvest rates and high performance of linear arrays are described. Our design is an extension of the loop-based approach developed by Horst. The defect-tolerant designs allow each cell to interconnect with up to eight neighbors, and maintain a constant wire length between any two logically adjacent cells independent of fault distribution. A reconfiguration strategy is developed to improve the harvest rate of loop-based approaches. The problem complexity of harvesting the maximum number of fault-free cells is analyzed and a heuristic reconfiguration algorithm is presented.","In Chapter 3, the problem of diagnosis and spare allocation for random access memory with coupling faults is investigated. Both diagnosis and repair of coupling faults by utilizing spare rows and columns are examined. We show that a coupling fault is repaired if its coupling cell is replaced by utilizing a spare row or its coupled cell is replaced by utilizing a spare row or column. By specifying both the coupled cell and coupling cell, the amount of redundancy required to repair a given set of faults may be reduced. A diagnosis procedure for RAM is provided to locate stuck-at faults as well as coupling faults, and a repair procedure has been implemented to allocate rows and columns for repair. A graph model is employed to describe the repair of coupling faults.","In Chapter 4, optimal diagnosis procedures of k-out-of-n structures are described. Knowledge of the probability of each unit being good and the expected test time of each unit are used by the diagnosis algorithm to select units for testing. The general problem of optimal diagnosis is described followed by an examination of diagnosis for k-out-of-n structures. The optimal diagnosis of k-out-of-n systems is presented along with a complete proof. A compact representation of the optimal diagnosis scheme which needs $O$($n\\sp2$) space and can be generated in $O$($n\\sp2$) time is also described.","Made available in DSpace on 2011-05-07T12:14:50Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9124391.pdf: 3312078 bytes, checksum: 2a4daf8519a530791c06af57e0a1fe3d (MD5) Previous issue date: 1991","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:38:39Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:16:08-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"],"dc:identifier":["AAI9124391","(UMI)AAI9124391","http://hdl.handle.net/2142/19672"],"dc:language":["eng"],"dc:rights":["Copyright 1991 Chang, Ming-Feng"],"dc:subject":["Engineering, Electronics and Electrical","Computer Science"],"dc:title":["Design, diagnosis and reconfiguration of defect-tolerant VLSI"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:14Z"}