STA problem: Checking for setup/hold violations in a timing path

Problem: Figure 1 below shows a timing path from positive edge-triggered register to a positive edge-triggered register. Can you figure out if there is any setup and/or hold violation in the following circuit?

Figure 1: A sample timing path

Solution:

To check if a timing path violates setup and/or hold, we need to check if they satisfy setup and hold equations. A violating timing path has a negative setup/hold slack value.

The above circuit has a positive clock skew of 1 ns (as capture flip-flop gets clock 1 ns later than launch flip-flop).

Let us first check for setup violation. As we know, for a full cycle register-to-register timing path, setup equation is given as:

T_ck->q + T_prop + T_setup - Tskew < T_period

Here,

T_ck->q = 2 ns,  T_prop (max value of combinational propagation delay) = 4 ns,  T_setup = 1 ns, T_period = 10 ns, Tskew = 1 ns

Now, T_ck->q + T_prop + T_setup  = 2 + 4 + 1 - 1 = 6 ns < T_period

So, the above circuit does not have a setup violation. The setup slack, in this case, will be given as:

SS = T_{period -} (T_ck->q + T_prop + T_setup - Tskew₎ 

SS = +4 ns 

Since, setup slack comes out to be positive, this path does not have a setup violation.


Now, let us check is there is a hold violation for this timing path. Hold timing equation is given as:

T_ck->q  + T_prop > T_hold + T_skew

Here,

T_ck->q  =  2 ns, T_prop (min value of combinational propagation delay) = 2 ns, T_hold = 2ns, T_skew = 1 ns

 Now, T_ck->q  + T_prop = 2 ns + 2 ns = 4 ns

And T_hold + T_skew = 2 ns + 1 ns = 3 ns

Now, 4 ns > 3 ns, so this circuit does not have a hold violation. The hold slack, in this case, will be given as:

HS = T_ck->q  + T_prop  - (T_hold + T_skew)  = +1 ns

Since, hold slack comes out to be positive, this path does not have a hold violation.

Also read:

• Finding the maximum frequency of operation of a timing path
• Setup and hold interview questions

Mice and poisonous bottles

Problem: There are 20 bottles filled with water, out of which exactly one is poisonous. We have to figure out the poisonous one. We have, with us, available some mice. When a mice tastes water from a bottle, it dies after exactly half an hour. We have one hour to figure out the poisonous bottle. What approach we should take.                                (Problem source : www.quora.com)

Solution: Each bottle can either be drunk from by a mice or not; i.e., there are two possibilities. We can interpret this as a binary number system problem wherein '1' represents that the mice has drunk from a bottle and '0' represents it has not.

Now, let us approach with a very simple but un-optimized method. Let us have 20 mice, and assign 1 mice to each bottle (1 mice will dring water from a bottle). After half an hour, one of the mice will die. Clearly, we have the culprit bottle. This solution requires 20 mice. But, we can have a better solution as discussed below. Another option can be to choose 1 mouse only. Let it drink from one bottle, wait for half an hour if it dies. If not, let it drink from next bottle. The maximum this approach can take is 10 hours, which is way more than the budget allocated. So, solution 2 is not for this problem.

To represent number 20, we need 5 binary digits. Let us number each bottle with numbers from 1 to 20 and assign binary code representing that number to the bottle. Now, each of the bottles has a unique 5 bit code. We can assume each bit representative of 1 mouse, '1' shows that the mouse will drink water from this bottle, '0' shows otherwise. 

Let us take an example. Bottle '12' will have code '01100', meaning that mouse 2 and 3 will drink water from it. The code for each bottle and respective interpretation is as shown below:

Bottle no	Code	Interpretation
1	"00000"	No mouse will drink water
2	"00001"	Mouse 1 will dring water
3	"00010"	Mouse 2 will drink water
4	"00011"	Mouse 1 and 2 will drink water
5	"00100"	Mouse 3 will drink water
6	"00101"	Mouse 1 and 3 will drink water
7	"00110"	Mouse 2 and 3 will drink water
8	"00111"	Mouse 1,2 and 3 will drink water
9	"01000"	Mouse 4 will drink water
10	"01001"	Mouse 1 and 4 will drink water
11	"01010"	Mouse 2 and 4 will drink water
12	"01011"	Mouse 1, 2 and 4 will drink water
13	"01100"	Mouse 3 and 4 will drink water
14	"01101"	Mouse 1, 3 and 4 will drink water
15	"01110"	Mouse 2, 3 and 4 will drink water
16	"01111"	Mouse 1, 2, 3 and 4 will drink water
17	"10000"	Mouse 5 will drink water
18	"10001"	Mouse 1 and 5 will drink water
19	"10010"	Mouse 2 and 5 will drink water
20	"10011"	Mouse 1, 2 and 5 will drink water

Let us say, bottle 15 had poison. So, after half an hour,  mouse 2, 3 and 4 will die as only these mice drank water from this bottle, with the help of which we will come to know that this bottle contained poison.