HYPERGRAPH COLORING AND RECONFIGURED RAM TESTING

RAM decoders are designed with a view to minimize the overall silicon area and critical path lengths. This can result in designs in which physically adjacent rows (and columns are not logically adjacent. Even if physically adjacent row (and columns) are logically adjacent, there are other issue that preclude the possibility of identical physical and logical addresses. State-of-the-art memory chips are designed with spare rows and spare columns for reconfiguration purposes. After a memory chip is reconfigured, physically adjacent cells may no longer have consecutive logical addresses. Test algorithm used at later stages for the detection of physical neighborhood pattern sensitive faults have to consider the fact that the address mapping of the memory chip is no longer available. In this paper, we present test algorithms to detect 5-cell and 9-cell physical neighborhood pattern sensitive faults and arbitrary 3-coupling faults, even if the logical and physical addresses are different and the physical-to-logical address mapping is not available. These algorithms have test lengths of O(N [log3 N]4) and O(N [log3 N]2), respectively, for N-bit RAM's, and are especially suited for testing reconfigured DRAM's. They also detect other conventional faults such as stuck-at faults and decoder faults. These test algorithms are based on efficiently identifying all triplets of objects among a group of n objects. We formulated this triplet identification problem as a hypergraph coloring problem, and developed an efficient 3-coloring algorithm that colors the n vertices of a complete uniform hypergraph of rank 3 such that each edge of the hypergraph is trichromatically colored in at most [log3 n]2 coloring steps.