Reconfiguration of memory arrays using spare lines is known to be an NP-complete problem. In this paper, we present an algorithm that reconfigures a memory array without any faults by using spare lines effectively even if they contain faulty elements. First, the reconfiguration problem is transformed to an equivalent covering problem in which faulty elements are covered by imaginary fault-free spare lines. Next, the covering problem is heuristically solved by using the Dulmange-Mendelsohn decomposition. The experiments for recently designed memory arrays show that the proposed algorithm is fast and practical.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Keiichi HANDA, Kazuhito HARUKI, "A Reconfiguration Algorithm for Memory Arrays Containing Faulty Spares" in IEICE TRANSACTIONS on Fundamentals,
vol. E83-A, no. 6, pp. 1123-1130, June 2000, doi: .
Abstract: Reconfiguration of memory arrays using spare lines is known to be an NP-complete problem. In this paper, we present an algorithm that reconfigures a memory array without any faults by using spare lines effectively even if they contain faulty elements. First, the reconfiguration problem is transformed to an equivalent covering problem in which faulty elements are covered by imaginary fault-free spare lines. Next, the covering problem is heuristically solved by using the Dulmange-Mendelsohn decomposition. The experiments for recently designed memory arrays show that the proposed algorithm is fast and practical.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e83-a_6_1123/_p
Copy
@ARTICLE{e83-a_6_1123,
author={Keiichi HANDA, Kazuhito HARUKI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Reconfiguration Algorithm for Memory Arrays Containing Faulty Spares},
year={2000},
volume={E83-A},
number={6},
pages={1123-1130},
abstract={Reconfiguration of memory arrays using spare lines is known to be an NP-complete problem. In this paper, we present an algorithm that reconfigures a memory array without any faults by using spare lines effectively even if they contain faulty elements. First, the reconfiguration problem is transformed to an equivalent covering problem in which faulty elements are covered by imaginary fault-free spare lines. Next, the covering problem is heuristically solved by using the Dulmange-Mendelsohn decomposition. The experiments for recently designed memory arrays show that the proposed algorithm is fast and practical.},
keywords={},
doi={},
ISSN={},
month={June},}
Copy
TY - JOUR
TI - A Reconfiguration Algorithm for Memory Arrays Containing Faulty Spares
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1123
EP - 1130
AU - Keiichi HANDA
AU - Kazuhito HARUKI
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E83-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2000
AB - Reconfiguration of memory arrays using spare lines is known to be an NP-complete problem. In this paper, we present an algorithm that reconfigures a memory array without any faults by using spare lines effectively even if they contain faulty elements. First, the reconfiguration problem is transformed to an equivalent covering problem in which faulty elements are covered by imaginary fault-free spare lines. Next, the covering problem is heuristically solved by using the Dulmange-Mendelsohn decomposition. The experiments for recently designed memory arrays show that the proposed algorithm is fast and practical.
ER -