A new approach to diagnostic testing of embedded memories is presented which enables the design of tests that provide complete detection and distinguishing of all faults in a given fault model. The approach is based on decomposition of functional memory faults into basic fault effects and output tracing. Output tracing involves storing all read operation results for defective memory cells and replaces the commonly used evaluation of a “fail” signal. In particular, we examine memory tests of linear order (O(N)), since this class of tests requires low-test application times and is realizable as Built-In Self-Test circuitry with very low area overhead.