Functional testing of constrained and unconstrained memory using march tests

Memory systems exist in every computer system, making it important to test them in order to ensure the correct functionality of computer systems. Memories are used in different forms such as caches, main memories, buffers and unidirectional memories. Memories are used in different environments, where each environment imposes different constraints on the procedure for accessing memory. Every implementation and every environment requires different techniques to test the memory due to the nature of the constraints imposed on accessing the memory's contents.; March tests are commonly used for testing memories. They are well known for their high fault coverage and low time complexity. We present new methodologies to generate optimal march tests. Optimality of march tests can be defined in terms of their length and uniformity. Such features in march tests are desirable to lower test time and the complexity of the BIST design. We have completed a methodology for a number of common fault models and we have generated optimal march tests for those fault models. The methodology depends on generating necessary and sufficient conditions for fault detection, and using the properties of march tests to generate the optimal tests using a branch-and-bound search tree. Constrained memories are tested using a subset of the detection conditions that do not violate the memory constraints. We also present a new methodology for testing cache memories. Our new methodology is proven to generate a 60.6% reduction in time complexity compared with previously published methodologies. We have developed a transformation that benefits from the cache design features in order to lower the time complexity.