This paper presents a low-overhead scheme for the built-in self-test (BIST) of circuits with scan. Complete (100%) fault coverage is obtained without modifying the function logic and without degrading system performance (beyond using scan). Deterministic test cubes that detect the random-pattern-resistant faults are embedded in a pseudo-random sequence of bits generated by a linear feedback shift register (LFSR). This is accomplished by altering the pseudo-random sequence by adding logic at the LFSR's serial output to "fix" certain bits. A procedure for synthesizing the bit-fixing logic for embedding the test cubes is described. Experimental results indicate that complete fault coverage can be obtained with low hardware overhead. Also, the proposed approach permits the use of small LFSRs for generating the pseudo-random bit sequence. The faults that are not detected because of linear dependencies in the LFSR can be detected by embedding deterministic cubes at the expense of additional bit-fixing logic. Data is presented showing how much additional logic is required for different size LFSRs.