March algorithm
Memory testing algorithm
From Wikipedia, the free encyclopedia
The March algorithm is a widely used[1] algorithm that tests SRAM memory by filling all its entries test patterns. It carries out several passes through an SRAM checking the patterns and writing new patterns.
The SRAM read and write operations performed on each pass are called a March element and each element is repeated for each entry.[2][3] The March algorithm is often used to find functional faults in SRAM during testing[1] such as:
- Stuck-at Faults (SAFs)
- Transition Faults (TFs)
- Address Decoder Faults (AFs)
- Coupling Faults (CFs), such as Inversion (CFin), Idempotent (CFid), and State (CFst) coupling faults
It has been suggested to test SRAM modules using the algorithm before sale using a built-in self-test mechanism.[4]
Notation
Each pass in a test sequence is represented by an "element". An element consists of a vertical arrow to indicate the direction in which the memory is scanned followed by a list of read/write operations to be applied to each memory cell. Multiple elements can be listed, separated by semicolons, to form a "test".[1]
For example, specifies to:
- Scan in both directions, writing 0.
- Scan from lowest to highest address, reading 0 and writing 1.
- Scan from highest to lowest address, reading 1, writing 0 and reading 0.
Variants
Many variants of the March algorithm exist with different sequences of tests. Each variant makes a different tradeoff between what faults it can detect and the complexity of the algorithm.
Several variants have been given names:
, 
...
Notes
- Wang et. al. lists the last element of MATS+ as , but this appears to be a mistake as such an element would fail in the absence of faults.
