Please use this identifier to cite or link to this item: https://doi.org/10.1109/43.503937
Title: Minimum fault coverage in memory arrays: A fast algorithm and probabilistic analysis
Authors: Low, C.-P. 
Leong, H.W. 
Issue Date: 1996
Citation: Low, C.-P., Leong, H.W. (1996). Minimum fault coverage in memory arrays: A fast algorithm and probabilistic analysis. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 15 (6) : 681-690. ScholarBank@NUS Repository. https://doi.org/10.1109/43.503937
Abstract: The problem of reconfiguring memory arrays using spare rows and spare columns is known to be NP-complete and has received a great deal of attention in recent years. For reason of cost effectiveness, it is desirable in practice to flnd minimum reconfiguration solutions. While numerous algorithms have been proposed to find minimum reconfiguration solutions, they all run in worst case exponential time complexities. On the other hand, existing heuristic algorithms with fast polynomial running time cannot guarantee minimum solutions. This paper presents a provably good heuristic algorithm for finding minimum reconfiguration solution. Using random bipartite graphs, we prove that the reconfiguration problem is almost always optimally solvable with our new algorithm in polynomial time for all practical purposes. We also show that our algorithm can be used to estimate the number of spare rows and columns that are required to achieve a given percentage of yield for RRAM's with known defect probabilities. © 1996 IEEE.
Source Title: IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
URI: http://scholarbank.nus.edu.sg/handle/10635/99336
ISSN: 02780070
DOI: 10.1109/43.503937
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

14
checked on Sep 24, 2022

WEB OF SCIENCETM
Citations

13
checked on Sep 16, 2022

Page view(s)

207
checked on Sep 22, 2022

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.