March algorithm
The March algorithm is a widely used 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. The March algorithm is often used to find functional faults in SRAM during testing such as:
- Stuck-at Faults (SAFs)
- Transition Faults (TFs)
- Address Decoder Faults
- Coupling Faults, such as Inversion, Idempotent, and State coupling faults
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".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:
| Name | Elements | Complexity |
| MATS+ | 5 N | |
| MATS++ | 6 N | |
| March A | 15 N | |
| March B | 17 N | |
| March C- | 10 N | |
| March C+ | 14 N | |
| March SR | 14 N | |
| March SS | 22 N | |
| March X | 6 N | |
| March Y | 22 N |