March algorithm

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, $\{\Updownarrow (w0);\Uparrow (r0,w1);\Downarrow (r1,w0,r0)\}$ 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:

Named March algorithms
Name	Elements	Complexity
MATS+^[5]	$\Updownarrow (w0)\Uparrow (r0,w1)\Downarrow (r1,w0)$ ^{[note 1]}	5 N
MATS++^[1]	$\Updownarrow (w0)\Uparrow (r0,w1)\Downarrow (r1,w0,r0)$	6 N
March A^[1]	$\Updownarrow (w0)\Uparrow (r0,w1,w0,w1)\Uparrow (r1,w0,w1)\Downarrow (r1,w0,w1,w0)\Downarrow (r0,w1,w0)$	15 N
March B^[1]^[5]	$\Updownarrow (w0)\Uparrow (r0,w1,r1,w0,r0,w1)\Uparrow (r1,w0,w1)\Downarrow (r1,w0,w1,w0)\Downarrow (r0,w1,w0)$	17 N
March C-^[1]^[5]	$\Updownarrow (w0)\Uparrow (r0,w1)\Uparrow (r1,w0)\Downarrow (r0,w1)\Downarrow (r1,w0)\Updownarrow (r0)$	10 N
March C+^[5]	$\Updownarrow (w0)\Uparrow (r0,w1,r1)\Uparrow (r1,w0,r0)\Downarrow (r0,w1,r1)\Downarrow (r1,w0,r0)\Updownarrow (r0)$	14 N
March SR^[1]	$\Downarrow (w0)\Uparrow (r0,w1,r1,w0)\Downarrow (r0,r0)\Uparrow (w1)\Downarrow (r1,w0,r0,w1)\Uparrow (r1,r1)$	14 N
March SS^[1]	$\Downarrow (w0)\Uparrow (r0,r0,w0,r0,w1)\Uparrow (r1,r1,w1,r1,w0)\Downarrow (r0,r0,w0,r0,w1)\Downarrow (r1,r1,w1,r1,w0)\Updownarrow (r0)$	22 N
March X^[1]	$\Updownarrow (w0)\Uparrow (r0,w1)\Downarrow (r1,w0)\Updownarrow (r0)$	6 N
March Y^[5]	$\Updownarrow (w0)\Uparrow (w0,r0,w1,w1,r1)\Uparrow (w1,r1,w0,w0,r0)\Downarrow (r0,w0,w1,w1,r1)\Downarrow (r1,w1,w0,w0,r0)\Updownarrow (r0)$	22 N

Notes

^ Wang et. al. lists the last element of MATS+ as $\Downarrow (w1,r0)$ , but this appears to be a mistake as such an element would fail in the absence of faults.

References

^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j Masnita, M. I.; Zuha, W. H. W.; Sidek, R. M.; Izhal, A. H. (2009). "March-based SRAM diagnostic algorithm for distinguishing Stuck-At and transition faults". IEICE Electronics Express. 6 (15). Institute of Electronics, Information and Communications Engineers (IEICE): 1091–1097. doi:10.1587/elex.6.1091. ISSN 1349-2543. Retrieved May 25, 2025.
^ "Documentation – Arm Developer". developer.arm.com. Retrieved 2025-05-25.
^ Van De Goor, A.J. (1993). "Using march tests to test SRAMs". IEEE Design & Test of Computers. 10 (1): 8–14. Bibcode:1993IDTC...10....8V. doi:10.1109/54.199799. ISSN 0740-7475. Retrieved 2025-05-25.
^ Kruthika, J.; Nisha, G. R.; Gayathri, R.; Jeyalakshmi, V. (November 24, 2022). SRAM Memory Built in Self-Test using MARCH Algorithm. pp. 1288–1292. doi:10.1109/ICAISS55157.2022.10010813. ISBN 978-1-6654-8962-1.
^ ^a ^b ^c ^d ^e Wang, Yongwen; Zheng, Qianbing; Yuan, Yin (2016). "The Improvement of March C+ Algorithm for Embedded Memory Test". Computer Engineering and Technology. Communications in Computer and Information Science. 592: 21–37. doi:10.1007/978-3-662-49283-3_4. ISBN 978-3-662-49282-6.

This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it.

[6] Wang et. al. lists the last element of MATS+ as $\Downarrow (w1,r0)$ , but this appears to be a mistake as such an element would fail in the absence of faults.

[masnita-1] ^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j Masnita, M. I.; Zuha, W. H. W.; Sidek, R. M.; Izhal, A. H. (2009). "March-based SRAM diagnostic algorithm for distinguishing Stuck-At and transition faults". IEICE Electronics Express. 6 (15). Institute of Electronics, Information and Communications Engineers (IEICE): 1091–1097. doi:10.1587/elex.6.1091. ISSN 1349-2543. Retrieved May 25, 2025.

[2] "Documentation – Arm Developer". developer.arm.com. Retrieved 2025-05-25.

[3] Van De Goor, A.J. (1993). "Using march tests to test SRAMs". IEEE Design & Test of Computers. 10 (1): 8–14. Bibcode:1993IDTC...10....8V. doi:10.1109/54.199799. ISSN 0740-7475. Retrieved 2025-05-25.

[4] Kruthika, J.; Nisha, G. R.; Gayathri, R.; Jeyalakshmi, V. (November 24, 2022). SRAM Memory Built in Self-Test using MARCH Algorithm. pp. 1288–1292. doi:10.1109/ICAISS55157.2022.10010813. ISBN 978-1-6654-8962-1.

[wang-5] Wang, Yongwen; Zheng, Qianbing; Yuan, Yin (2016). "The Improvement of March C+ Algorithm for Embedded Memory Test". Computer Engineering and Technology. Communications in Computer and Information Science. 592: 21–37. doi:10.1007/978-3-662-49283-3_4. ISBN 978-3-662-49282-6.

[1]

[2]

[3]

[4]

[5]

[note 1]