Abstract
Paths in a circuit are structurally related to each other. Therefore, under certain assumptions, an unknown path delay could be calculated as a linear combination of known path delays [1]. In other words the delays of all paths of a circuit could be showed as a linear combination of the delays of a small subset of paths called the basis path set [2]. To find the maximum path delay, it must know the delay of all paths, either by direct measurement or by calculation. This means that every path not directly measured by a test pattern must be equal to a linear combination of basis path set. In this thesis, we improve the algorithm of determining linearly dependent paths based on the one given [2]. We combine some same and redundant structures of a circuit graph and increase more testable paths to the basis path set. Then, we will get more linearly dependent paths. The experimental results for benchmark circuits are given.