welcome to lecture series on advanced VLSI design so continuing with my last lecture on VLSI test where we discussed about the fault modeling and test generation using algebraic method and we discussed that algebraic method is a complete method it gives you the test vector if it exists otherwise it tells you that that fault is a redundant fault and complexity of both of the processes are immense a the problem that we discussed about algebraic method fast that it's not scalable so that means if you have design of multi million gates you may not be able to generate test using algebraic methods so then we have to to look for the alternate method which are scalable and so the algorithm method is an alternate solution algorithmic methods are based on path sensitization which follows three steps fault sensitization or activation fault propagation and lines justification there are couple of algorithms given in the literature and some of them I have listed here like D algorithm which was the first complete algorithm given by Roth in 1966 from IBM then there was further improvement on on that in 1981 by goal from IBM and which is called as Patel then again the some new concepts were introduced by Professor Fujiwara from Osaka University and in 1984 and that is known as Fang and then so these in almost in all the automatic test pattern generators we may use either podium or for fan as the the base test generation engine then over the years people started to put some more concepts which are more or less based on the learning from the circuits and two of the examples I have listed here Socrates given by soultion and spirit given by ml so in this course I will briefly describe about D algorithm and then means you can follow poor demand and fen and I so as I mentioned that all these algorithms are based on path sensitization what does it mean what is path sensitization so let's look at this circuit which has four input and and and one output it's pretty simple say simple circuit and now let's say we have stuck at 0 fault at line II and so I I have to have find out if input vector that can give me the distinguishable faulty and fold free output at G then so if I assign 0 at E in that case it can never give me the distinguishable behavior so that means here I have to assign opposite value to to the the faulty value at fault site did this is known as fault site so now here I have to assign opposite value and that is known as fault sensitization or fault activation now I need to assign value 1 at some intermediate point here at the fault site right so now and and I do not have any control over here so what I have to do is I have to go back to the primary input and and and try to find out some input which can you can justify value 1 here at E right and we know that that here if I have 1 and 1 at a and B I can get equal to 1 so this can activate the fault so that means here I in order to activate I need to have opposite value here and in order to do that I have to go back all the way to the primary input and and assign this value the primary input and this is known as line justification because you are justifying that at the primary input line now the next thing is I cannot observe the fault effect right at this this point because I do not have any observability from this point so now what I have to do I have to transfer this fault effect to the primary outputs so now in order to do that what I need to do is I have to assign the the known controlling value to the other input of this gate right and now known controlling value of this gate is 1 so so that that's the requirement for the fault propagation now here again I cannot justify I cannot assign any value or the intermediate points so in order to do that I have to go all the way to to the primary input and I have to assign one one at C and D now here if I assign one one one one at primary input in that case here this will give me me one as if circuit is fault free and it will give me mean zero if circuit has strict at 0 fault at fault site II so now here it has three component one is the full tech deviation another is the fault propagation to the primary output and then I I have to justify some of the unjustified in intermediate values and for that I have to go all the way to the primary input and and so that means primary input means here if you level I your circuit you go all the way to the input line that is level 0 so and that that is referred as line justification so these are the three steps all the the ADIZ algorithms have to follow for sensitization fault propagation and line justification now here so the then basic structure of the any of the dat pz tool would be like this you have to set all the way values at primary input as X initially then you justify some value say V at the the fault fault site which is L and then so this will activate the fault and then after that that that you have to propagate the fault effect to the primary one of the primary output so now here if your V zero in that case you propagate means L as d these are symbols that I will discuss in a minute what D and D bar mean so you propagate this one otherwise if he is one in that case you propagate the bar and so the this is the basic skeleton for example here in this circuit here say say your DS is stuck at zero so in that KK case here I I assign a single B here and now here in order to do that what I mean IIIi need I need to have opposite value assigned to D so that means I I have to create a function justify D D line as one so in order to do that I cannot do anything here so I have to go all the way to the primary inputs and that means here I have to justify a s1 and I have to justify B as one and since these two are the primary inputs so always you can justify these these values so your fault is activated so now after that that you have to propagate this fold to the one of the primary outputs here we have only one primary output so now you propagate d2 to F now now here because this is inverting gate so D would be propagated as d bar so now if d is propagated as d bar at the output so in that and in order to do that you need to have non-controlling value at e which is 0 right so in order to assign 0 here what you need you so you have to justify value 0 at E and in order to do that you need to justify be as as 1 and C as 1 me it's already 1 so now when you do justify CS 1 in that case here you are done so so now here your 1 1 1 is your test vector now if you look at this process in that case yet as I said that there are three steps one is fault activation and then fault propagation and lines justification look at the complexity of the these fault activation for line justification and and fault propagation so first its fault activation or fault sensitization so now in order to means what do we need to do in fault a activation or sensitization I have to assign the opposite value of the a at the fault site right so now here you need to justify 1 so and and how you can justify you can justify that by by assignment at primary input right so that that means here this problem converts into lines justification problem so your fault activation is a problem is like a lion justification problem if you look at the fault propagation in the in this example which we have seen if we have only one primary output it may possible that there would be a fan-out point here and then this can propagate this may potentially be propagate to multiple outputs in that case you have to select one right so if that means here you may need to you need to select a fault propagation path to one of the primary outputs at least and that's the decision making process so now here this is a this isn't making making process it's like you want to go from the Institute to the hostel and then if you are not aware about they all the ways you start to follow the design and then you reach to some cross point and then at some cross quality oh if sign is not there you have to make a decision which way you you should go go and then you keep on moving and until the next this is in point and you make another decision and keep on going hoping that you you would reach the destination or hostel if your decision is wrong you you end up in a forest then you have to to come back to the previous decision point and then take the different decisions right so means the the fault propagation is a decision-making process unless you're you how to make a decision at the fan-out point once you make it make a decision after that say say once you make a decision here in this case there is no decision there is only one path so you propagate it and then you need to assign non-controlling value to to all the off inputs of that gate thread so not now here and then you cannot assign any value at the intermediate point so you have to go all the way again to the primary input and then this problem converts into line justification problems so now here fold propagation problem is either decision making so this is decision making as well as the line justification problem if you look at the lines of stiff occation problem in again in this small example here when you are you want to justify say 0 0 here you need to have both 1 1 so there is no choice this may possible that you may need to assign one here in that KK case here you can have any one as 0 that satisfies your requirement so now you're lying justification problem is either decision making process or implication what is implication safe in this this gate here if you want to justify output C as 1 in that case always you need to have a and B as 1 there is no choice so that is implication so if you want one here in that case here a and B are 1 this is typically referred as backward implication if you have say a is 0 and B can be anything in that case output C is always 0 that's forward implication so this is this is the implication implication but if you want to assign C as 0 in that case you have choice you can have either a s 0 or you can have be a 0 so that is decision making process now say you you make a decision that is and then here again a maybe intermediate point and then you may want to go back to the primary input and then there may be a conflict in between and your decision may be wrong and then then you may need to come back again and take assign the idea alternative value so alternate assignment could be like here be at zero and and C can be any value X all right so this is decision making process and so now now in the the fault propagation you are making a decision in line justification you are making a decision so there are a couple of decisions you are making and your decision may be right may not be right in other words your decision may be wrong if your decision is wrong in that case here you have to backtrack like a old you mean you are exploring a new path you know if you end up saying Forrest you may need to come back and then where you will come back you will come back to the previous decision making point and then you have to explore way the alternate alternate path so so that that's backtracking so now here if you if you backtrack multiple times it will take more time to reach to the destination so in case of incorrect this is a new backtrack and then make an another decision and then if you reach to the the primary output here you you say that you are done and then that gives you the test vector so as I mentioned to you earlier that the algorithm was the first complete algorithm given by rot in from IBM in 1966 it was the complete algorithm complete algorithm means it gives you the test vector if it if exist otherwise it tells you that that particular fault is a redundant fault so that means here having that fault in the circuit won't result in two malfunctioning of the circuit this is based on five valued logic or five valued algebra that five value because here what you want is you want to have distinguishable faulty and fault free behavior so that means your when you propagate your signal you have to propagate both of the values faulty value as well as fault free value so that means here your logic must have composite value that has fault free value and faulty value and and so now here so we can have three kind of values 0 1 and X and how many combinations we may have your your fault free value and and faulty value if you look at fault free value is 0 for T value may be 0 fault free value is 0 for T may be 1 this is 0 and this is X then your your fault free value may be 1 for T 0 this is 1 for T is 1 and 1 and X and your fault 3 may be X and and for T is 0 X hole T is 1 X and both are X's now if you look at this in this case both values are indistinguishable always is T to 0 I assign one symbol say that symbol is 0 in this case both values are 1 so these are again in distinguishable and I assign another symbol say that symbol is what this condition when fault free value is 1 and faulty value is 0 I assign another symbol and and say that symbol is D what it represent this represent your stuck at 0 fault at fault sight right because here for in case of fault it it gives you 0 value in case of fault free signal it is 1 because that you want to assign this value and fault free is 1 and for T is 0 this is another they just opposite to this and hence here we assign another symbol D bar and all other values where in one value is X so that means here we cannot determine what what would be that value that may be 1 so so in that case it may be indistinguishable or or it may be distinguishable but we cannot reason about that so we Club all these well who has access in one symbol that is X so now here we have five valued values 0 1 D D bar and and X right so not now here this method works on five valued algebra where in the five symbols that we use are 0 1 D D bar and X and it heavily uses implications in the four direction as well as in the backward direction because keep in mind that when you are making a decision there are chances that you may make incorrect a decision and you need to backtrack and so so now here when you are making backtrack you are losing losing time and and you need to search more more space in order to backtrack here what we need to do is we have to maintain a stack of all the decisions so that here when you backtrack you will come back to the previous decision point and then you you you will you will freshly start to explore the search space right from that the previous decision making point so now here let's look at a little bit more in this so as I discussed here your it follows all those three steps fault sensitization fault propagation and line justification so when you are propagating the the fourth effect you are making a decision and if your decision is wrong you have to backtrack right so now I'm now here how do you how do you do let's assume that you have this circuit and there is a stuck-at 1 fault present at this point at the point where we have arrow so now now here what i i I want here I want to assign value 1 here it's zero here and in case of fault fault here this produce one I always 1 here right in case of so whether I I assign here 0 I assign one here always it will produce one so now here that I can capture by a symbol D bar in order to have D bar here here after they do this for T site here I need to have 0 in order to have 0 what I need I need I need a must be 1 being must be 1 C must be 1 and this is line justification problem so once I I have this I will I will get get it once you have one here in that KK case here this will imply 0 here right and so so now now here I have choice that so from this point this is by implication from this point now now there are 2 fan out branches one goes to get g5 another goes to get g6 so now I have to make a decision here so let's say I I want to first I I may make a decision in favor of g5 so that means here I want to propagate volt effect to f1 through g5 if I Y if i propagate this and this is non inverting gate so now here D bar should propagate here as D bar in order to have propagate this as D bar here what I want this should have norm controlling value non-controlling value must is here 1 and now if it is 1 in that KK case here what I want both of the input must be 0 in order to have one here right and because now here you have already assigned one here so there is a conflict you cannot assign two values at a single input so now here and and that arises because of really convergent fanouts so now here your your fault propagation failed if it is failed then then you have to come back to the previous decision making point and make an alternate decision so your previous decision making point is here all right now you have to you already explored propagation through G file now you you left with only one choice through G 6 so try to explore through G 6 if you explore through G 6 in that case case here this D bar will propagate as d bar here provided that you you assign value one at the V of input of G six now in order to assign one here what you need you you you need this value is already already 0 so if you assign 0 here another input of e in that case here you will get 1 as output of get G 5 and without any conflict hence you are done so now your test vector would be a is 1 B is 1 C is 1 D it can be anything X because it doesn't depend on that and II must be 0 so now here 1 1 1 ax 0 is the test vector which can detect a stuck-at 1 fault at the output of gate G 1 so this explained that the decision making process so now here we had to make a decision between get G Phi on g6 we explored first g5 we failed we backtrack and then we explored the another possibility that is through g6 and we succeed and it gave us the test vector in order to so that means here at every point you have to maintain or a stack wherein at least there must be D 1 D or D bar must exist in the circuit so for that here we define a set that that's called as D frontier different here is the set of all the gates whose output value is currently X so that means output is no determinant but but at least one of the input is is faulty value that means D or D bar so that means those are the potential gates through which you can transfer or propagate the fault effect to one of the primary outputs okay so always always at every means any point in time there must be at least one gate in the D frontier otherwise you block the fault effect propagation and enhance your your algorithm cannot progress so and that you that fault is is nonsense attachable or it's a redundant fault so this gives you some understanding about how we can make a decision for for the fault propagation now another decision you need to make during the line justification let's see how we make decision during the line justification so now here say in this circuit you made you need to have test for a stuck-at 1 fault at line edge so in order to have that I need to assign a symbol D bar so in order to excite this is stuck-at 1 fault here H must be zero if and and if H is zero then in order to purl then you have to propagate it and in order to propagate you need to have F as one and E as one so if you have both this in that case case here this will propagate as d bar if e is 1 in that case you are simply by implication o would be be 0 right now this is not the primary output so you have to propagate to one of the primary output and there is one possibility you have you have to propagate through this end gate to output s in order to propagate that that here what you need you you need to justify non-controlling value at Q and R and non-controlling value for this gate is 1 so hence you have to have Q equal to 1 and R equal to 1 let's take means now now you have to sequence realize it so not let's take first you want to assign Q equal to 1 what do you do we need to do because if Q is equal to 1 now here how you this is decision making point because this gate can give you Q equal to 1 if either case 1 or L is 1 now let's explore that make a decision in favor of also assign L equal to 1 if L equal to 1 in that case here again you reach to the implication that L can be 1 only when C and D both are 1 okay now let's see what happens if both C and D both are 1 in that KK case here this C 1 implies equal to one and D implies an equal to sorry c1 implies m equal to 0 D implies D equal to 1 implies n equal to 0 e equal to 1 implies m equal to 0 all 3 inputs of this or gate are 0 and so output would be 0 and then this will block the propagation of fault effect so now now it results in 2 into conflict because here you you wanted to have one here and then you you happen to get 0 and and so now now you have to go back to the previous decision point now where I made decision what was the decision here there were there was no decision but when I was assigning 1 are they the input of this or gate I made a decision in favor of L that was wrong so I have to make the I I have to correct that decision or maker and alternate choice and that that is k equal to 1 if i say k equal to 1 then by implication your a should be 1 and B should be 1 and then they there's no conflict so now here k equal to 1 a equal to 1 and B equal to 1 give you UK equal to 1 that will give you Q equal to 1 is still here R equal to 1 is unjustified value so in order to do that here what what you want at least one of the input of big this gate must be 1 right so so now now here say o is 1 if oh is 1 in that kk case here that implies that C must be 0 if C is 0 u equal to 0 implies that an is 0 that doesn't block the propagation because output Q is still remain as 1 and now now this Q is equal to 1 is justified R equal to 1 is justified and now here that justifies the propagation of the fault effect to the primary output hence now my test vector is a equal to 1 B equal to 1 C 0 D can be any value X T must be B 1 F must be 1 and s must be 0 so this 1 1 0 X 1 1 0 is the test vector so now here in order to track the the decision when you are going backward here you need to maintain a set and that the third set is is called as J frontier it is set of all the gates whose output is determined but that is not implied by then in input value so like here you want output equal to say 0 but but both of the inputs are accepts of any gate so now here those so through those gates you can justify these values now so now here you made a decision that Q equal to 1 from there you you you may have made another another decision L equal to 1 wherein you failed so you came back to to the another previous decision making point k equal to 1 when when you made k equal to 1 then here the this this objective was justified then you made another decision then R equal to 1 for R equal to 1 you made a decision that a Miss should be equal to 1 and that succeed and then you are done so this way you explore the decision tree ok let's take a a small example that that consider both both fault propagation and line justification so let's there say a stuck-at 1 fault at this folds fold side so that means just after fan-out branch here so if there is a stuck-at 0 fault here we need to have D ba is sorry stuck-at 1 fault so we need to have a symbol D bar here in order to excite that fault you you you need to have zero value at the primary input a and then if then now here your fault is activated you have to propagate that so in order to propagate here you need to have known controlling value at B and C and since these are primary input you can always assign these values so now here this will propagate this is a fault effect to they prime to the output of this gate and now this was D bar that can be propagated as d @ @ G now here if you look at this is fan-out point and then there are three fan out branches so if you look at the D frontier D frontier consists of those gates whose one of the input is D and output is not determined yet so now here one of the input of this gate gate is d one of the input of this gate is d one of the input of this gate is d so now here gate I K and M are in the D frontier you have to choose one and and past or propagate your fault effects through that gate at the same time if you look at the the implication if a is is 0 so that means here one of the this input of this and gate is 0 that means your ass will always be me 1 by implication ok now now as you select to propagate your fault effects through this NAND gate so if then in order to propagate through this what you need you need to have non-controlling value at the off input of this gate and that is d d is the primary input so you can always assigned 1 and this will propagate a d bar here so now here if you if you look at the the D frontier then like this in one of the input of this gate is already D D one of the input of this gate is already D and output is no determined yet and now here one of the input of this gate is also D so now now here these 3 gates are in the D frontier K and N and now you have to choose one gate through which you can easily propagate volt effect to the one of the primary outputs and and that gate is n because the that's pretty close to the primary output so now you you to choose to propagate through this this is inverting gate so now now here D bar can be propagated here as D R and so now now you propagate this as D in order to do that you need to assign all the the of inputs to the the non-controlling value so that means J must be 1 K must be 1 L must be 1 and M must be 1 right if all these things are there then you can propagate the on the primary output and now let's see how I can justify that so say I justify the first wave value so now now say we want to justify Z equal to one in order to justify J equal to one what you need to do because here one one of the input to this gate is it's already one so that means the other input must be zero right so that means e bar must be 0 if Y bar is 0 in that case here II must be 1 and if E is 1 in that case here this D bar sorry this D will propagate here at at K K output as as D bar and then there is a conflict because you wanted one and then you of you happen to get D bar that's one conflict and you have to backtrack so now now here what we're doing bin backtracking so you have to come back to your your different here now in D frontier you have we get K and M so you have to choose one so in order to to to choose one now you want to propagate the fault effect through gate K and now in order to do that in order to propagate through this one again you you want one here if each one in that case here this will allow you to propagate fault effects through this one and then the this e is equal to 1 gives you V Bar as 0 and then here J would be 1 now you will get maybe this H 1 D is is T bar J equal to 1 and in case is your D bar right now here and then here output of this gate is is not not yet determined output of this gate is not yet determined now again here you have two gates in the D frontier one is N and another is n because here there are two D bars are they the input of this gate so now now again you need to choose one out of these two and then of course you would like to choose gate and because it is it is closer to the primary output so now now here in order to do that what again you need you need one here and one from here so say you want to justify one here in order to to to justify one here what what you want you want F is equal to 1 and when F equal to 1 in that case here that will give you f bar equal to 0 this also propagates here D bar but not now here when you have D bar here one D bar here one and D bar that are also at the same time this will give you D at output and now here you are able to propagate deep at the primary output and you are done so now here what test vector can test this particular fault that test vector is a equal to zero B equal to 1 C equal to 1 D equal to 1 equal to 1 and F equal to 1 so now here 0 1 1 1 1 1 is the test vector for this fault this way we can we can detect or or we can did generate test vector for a given fault and so as I said that that this is very directed approach in worst possible case it may need to explore all possible combinations so if you look at the complexity I don't want to go in in that detail but this is np-complete problem so in worst case it may need to explore exponentially or entire search space but observation says that most of the time you because this is a directed approach you can quickly generate test and hence this is a scalable approach you can handle large number of large number of of gates in a circuit then there there means one of the issue here is always you need to justify or a science of non controlling value at the intermediate points and because you cannot assign non-controlling value value at the intermediate point you have to go back all the way to the primary input to assign those values this problem was further looked by oil in from IBM and he came up with another algorithm that was known known as poor dam in which he says that when we cannot assign any value at the primary mean intermediate point why we are looking at intermediate point why why not we go all the way to one of the primary input assign some value forwarding were implicated and and see whether it allows you to propagate the fault effect or not if it doesn't allow if it blocks then you change that that way value and that algorithm podem became almost hundred times faster than then the algorithm then further they did the problems of burden algorithms were or the the in other way I should say that some of the new concepts were introduced on top of the podium algorithm by Professor Fujiwara that thus known as fan-out oriented a generation and that was almost 100 times faster than the podium algorithm so they these are they were various algorithms you can go through the literature and look at the various recent algorithms and and as I said that here most of the test generation engines are based on either podium or fan mostly fan ok this summarizes the the decision making process you can look at all these steps that we discussed earlier ok so these were the this was the decision tree which we made rehearing earlier they be your D frontier has gate K L M then we have choosen one and then L and then we introduce another gate and in the the different here we had chosen and we fell then we came back to the previous decision point wherein you had M and N in the different here you had children and again you fail then you come back and and so had choosen m and then you you succeed so now here there were two bad back tracks and this so now here as I said that theoretically taste in the recent complexity of a combinational automatic test pattern generator is np-complete but observation says that you can generate test in reasonable time the big problem is redundant faults so if full test vector exist these tests this algorithms can can generate test vector pretty fast but if it is redundant it may may need to not necessary all the time but may need to explore the entire entire a decision tree and and that may not be practical so now in general what these practical ATPG tools does all these practical ATPG tools are based on is they keep a backtrack limit if say a backtrack limit is is 1,000 then if it exceeds 1000 it will abort that and idea is that most of time again keep in mind I said most of the time most of the time that fault may be redundant fault but it's not sure and that's the the reason we it's difficult to get very high coverage that means 100% fault coverage because we have to abort that that if your decision-making points are exceeding or or back-to-back tracks are exceeding beyond the assigned limit so and so then that means he if your your about limit is is lower you can generate a test quickly because then if it exceeds beyond that limit it abort that and and then they test for the next day a fault if you you you increase the boat limit it will take it will take longer time and then here this time is not proportional to it grows exponentially this was the test generation for combinational logic now in general we do not have combinational circuit we have sequential circuit and how sequential circuits are different from combinational circuit sequential circuits have additional memory and element in that so now the bigger problem we may end up to is your fault effect may propagate to to the flip flops or or memory elements rather than propagating to one of the primary outputs look at the structure this is your combinational logic and this is your flip-flop you are getting input from this one this are your primary input primary output the these inputs from the flip-flop are known as pseudo primary input and the output from the circuit which are going to the D flip-flop are known as pseudo primary output so your fault effect may fault may be here and then this may propagate to the one of the pseudo primary output and I cannot observe that so now now here what you need to do you have to run your circuit again so the until the time when you it propagates to the primary output where you can observe another issue is that here when you are generating tests for this you may demand some value from the pseudo primary input or from daily the flip-flops and that those flip-flops may be in any state when you are powerful when you power up your your circuit right so that means here you how to initialize your circuit to some fixed value in the primary in this flip-flops so it demands so test for a fort in the sequential circuit is a sequence of vectors rather than a single vector and that sequence comes from first thing is you need to initialize circuit to an on state then you have to activate the for fault and if that fault effect is not propagating to the primary output and propagates to the the one of the pseudo primary output in that case you have to run your circuit in several cycle to propagate the fault effect to the primary output so that that means here you need a sequence of vectors rather than a single vector in order to handle this problem there are two methods one is the time frame expansion method another is simulation based method time frame expansion method I'll explain you briefly so let's look at this example this is brief example say there I guess all of you are familiar with the serial adder this adder has say two inputs a and B and then two outputs one is the output and another is the carry so now here carry would be B store in there the flip flip flop and then in every cycle you are getting new inputs and and and giving the output of that cycle so now here say there is a stuck-at 0 fault here for a stuck-at 0 fault here what you demand you demand one from here and then by implication you say that a and and B n must be 1 in order to propagate this for a fault effect here there is a D and then here propagate that that is d bar here what you demand you you demand one from here that the that's full fulfilled goes by implication a and equal to 1 and BN equal to one will give you this as one now your fault effect is here right so now now here there are two part you can you you how to propagate the that faulty felt through this gate or through this gate right in order to propagate you need to have non controlling well value here so here there there must be one and here there must be zero but because he or a circuit can power up in any state in that case here you have X and then once you have ax here as one of the inputs to these gates output would be X and then your your primary output would be X and then then you you will assign value one in the flip-flop so that means here you are not able to propagate fault effect to the primary output if you start from value X now here what's the solution and solution is that here you you how to initialize this flip-flop into a non state and that known status is one that you are you are demanding so that means here you have to unroll your circuit in multiple timeframes and all means here you have to have two copies of this circuit two copies of this circuit doesn't mean that you you implement mirror or fabricate two copies you you are fabricating only one copy of the circuit but now here for the test generation purpose you replicate that coffee so now now here in this and in both of the copies because here the same fault exists here as well as here so now now in order to excite that here you you need to have 1 1 as input from here and then you are demanding one from this one in order to have one here you you you need to you demand one from here and in order to to demand one here you need to have one and one here so that means here you need to have a sequence of two inputs one one followed by one one that can test this fault so that means here this give tells you that that how complex test generation for sequence circuit is okay so here what we need to do we need n vector so that and so we need to replicate our circuit and times and now now here they the same fault may exist in in n copy so that means in in totals combinational circuit that I have I have n number of faults so now here the this is the the instance of multiple force rather than then single stuck at fault now they time when I excite the fault that that we say say vector zero and then here time frame that we used to initialize our circuit we call at – one – two – three – n right and how many times I need to unroll I need to unroll until I reach to a point wherein I start from all access from the memory elements or flip-flops and then here because the fault effect may propagate to the the pseudo prime D output in that case again I need to unroll and I need to unroll until I am able to propagate fault effect to one of the primary outwards so I need to to unroll it multi multiple times so now here they they typically ATP's implementation select the one of the primary output based on they they the drivability III I skip that for a while but here say to run W one of the primary output it places logical where value 1 or 0 or 0 or 1 different so these are the composite composite values D or D bar depending on the full type we justify our output from the the primary inputs considering all necessary paths and and adding the backward timeframes if justification is impossible in that case you you need to select another primary output to propagate and do you repeat all these things if your processor fails for all the reachable primary output in that case here you have to say that that voltage is untestable now here you are unrolling this in multiple time frame and now the question is in worst possible case many times you need to unroll it and this gives you some scary numbers your your circuit maybe cycle-free or may may may have cycles so that means you're you may have feedback or or or you may not have feedback if circle is a circuit is cycle free in that case you need to unroll your circuit maximum sequential depth of the circuit plus one and sequential depth of circuit is defined as maximum number of flip-flop appears in any pair of input/output so if you say in one of the paths if there are maximum three flip-flops are appearing in that case your total 4sy you need to to unroll your circuit and you can easily understand that because if your circuit has sequential depth three that means here in three timeframes you may be able to initialize all the flip-flops because there is no feedback there is only feed forward if circuit is acyclic circuit and there are n number of flip-flops in that case here you need you may need to maximum unroll and raised to the nine raise to the power number of flip-flop times that's really scary figure because assume that you have only two flip-flops then you may need to unroll it 81 times to flip-flop circuit is is pretty small circuit though these numbers are scary but most of the time you don't need to unroll that many times you need to unroll pretty small number of times than these numbers but in order to give a guarantee you need to explore explore this so now here it is very very very difficult to to generate test for reasonably large sequential circuit if it has cycles involved in this now what is the solution and solution so now now means the the difficulties are poor initialize ability of the sequential circuit for controllability or observability of state variables because you you you cannot directly controller of those variables gate counts and number of flip-flops are increasing and then sequence and left is increasing and cycles are main responsible for the this complexity if you look at the the the tests in the recent time and fault coverage so if you have a small circuit then traffic light controller that has a three say 355 gates and 21 flip-flops and sequential deafness is say 14 in that case here ATPG that time would be something thousand two hundred forty seven seconds and fault coverages is still 89% whereas the another says circuits here you have chip a that that has pretty higher a number of gates and number of flip-flops and sequential depth as fourteen buffer but here is still it needs less number of so there now here the what does this a slide tells you that gate count and number of flip-flops are really not maybe the determining factor you study the the sequential or cycles which are determining the how much time or how complex this this process is if you look at some of the benchmark circuits some circuits are these are a race car 39 benchmark circuit they give this as one one nine six and and as for in 1996 so these two first two circuits are cycle free circuits and last two circuits are cyclic circuits though here all are having the similar kind of flip-flops like here the a cyclic circuits do have 18 flip-flop and cyclic circuits do have six flip-flops now you can see the test in recent time a cyclic circuits and it takes 10 to 15 seconds whereas the cyclic circuits are taking about 20,000 second so huge difference and and hence here the it's not practical to generate test for a significantly large sequential it so you have to to to to to adapt some other technique and as we know that that this complexity is coming from the cycles in the circuits and poor initialize ability and controllability of the circuit so if we happen to to initialize circuit by any random value and we can observe any value from the flip-flops you can always use the same combinational ATPG to generate the test and then your test generation complexities same as the combinational circuit test generation complexity with this I stop here today will continue with the the test generation for sequential circuit in the next class thank you very much good day you

# Mod-01 Lec-36 VLSI Testing: Automatic Test Pattern Generation

1 year ago
No Comments