Scan tree construction

A scan forest, comprising:

• a plurality of scan trees and at least one demultiplexer, wherein
• each of the plurality of scan trees comprises a plurality of scan chains, each of the scan chains in the same scan tree comprises a plurality of flip-flops in series, and the scan chains in the same scan tree are configured to receive the same input signal and are controlled by the same logic control signal;
• each demultiplexer drives a group of scan trees;
• different demultiplexers are connected to different groups of scan trees, respectively;
• each of the groups of scan trees has the same number of scan trees;
• the scan trees in the same group are controlled by different logic control signals, respectively;
• and
• the scan trees at corresponding positions in respective different groups of scan trees are controlled by the same logic control signals;
• wherein, the scan forest is constructed by:
• (1) setting a parameter g for representing the number of scan chains in one scan tree;
• (2) providing a current scan flip-flop set Q comprising a plurality of scan flip-flops, and an unprocessed scan flip-flop set U;
• and performing the following (a) to (d) until the scan flip-flop set Q is empty, to group scan flip-flops in the scan flip-flop set Q, thereby obtaining a plurality of flip-flop groups:
• in a case where the scan flip-flop set Q is not empty:
• (2a) taking a scan flip-flop f out from Q randomly, putting f into a scan flip-flop group set Q1, and calculating an OUT[f] reachable from f, wherein the OUT[f] represents a set of pseudo-primary outputs (PPOs) and primary outputs (POs);
• (2b) in a case of |Q1|<g, performing (2c) and (2d);
• (2c) taking a scan flip-flop f1 out from U, and checking whether f1 converges with any one of scan flip-flops in Q1, in a case where f1 converges with none of scan flip-flops in Q, putting f1 into Q1;
• and in a case where f1 converges with any one of scan flip-flops in Q, putting f1 into U;
• (2d) taking f1 out from U, checking whether f1 converges with any one of scan flip-flops in Q1, in a case where f1 converges with none of scan flip-flops in Q1, putting f1 into Q1;
• and in a case where f1 converges with any one of scan flip-flops in Q1, recording OUT[f1] reachable from f1, and putting f1 into U;
• (3) constructing the scan forest in the following (3a) to (3c):
• (3a) determining the number of external scan-in pins ce, the number of internal scan-in pins ci, and k for gating logic;
• and determining a depth of a scan tree d according to k, ce and ci;
• (3b) constructing the scan tree from left to right as follows:
• randomly taking a scan flip-flop group G1, sequentially putting g scan flip-flops as first scan flip-flops for k scan chains of a first scan tree;
• (3c) randomly taking another scan flip-flop group G2, sequentially connecting to the g scan chains, and repeating the above until the first scan tree is established;
• repeating steps (2 and (3 until all scan trees are established.