Synchronous sequential circuit

Synchronous counter:This is the simplest synchronous sequential circuit.

How can we design a modulo 6 counter ?

We know a mod 6 counter counts the sequence (0, 1, 2, 3, 4, 5, 0, 1, …). It has 6 counts or 6 states which starts with 0 and then count 1, 2, 3, 4, 5 and then loops back to 0 and continues. This is a binary counter. We need log2(number of states) flip flops to design this counter which is equal to 3 in this case.

So let us put the 3 flips flops here as shown in figure. The clocks and the asynchronous reset  to the 3 flops are tied together. There are 3 Qs (Q2, Q1 and Q0) as output and 3 Ds (D2, D1 and D0) as inputs. Assume at power on ,the output Q becomes (000). When the clock comes we should get (001) at Q.

So how to make the output 001 ?

As we know when the clock comes, as far as registers are concerned, whatever at D is transferred to Q. So it is enough that if we can make ready ‘001’ at the input D, then upon the clock edge, this D(001 ) is transferred to the output Q. In the next clock ‘010’ should be ready at D and so on.

Sequential Logic

So it is enough that if we put a combinational  circuit(next state logic or NSL) before the input D of flif flops and feedback the present count to the input of that circuit (NSL). So we design the circuit such that

given 000 –> should give 001

given 001 –> should give 010 and so on.

So this is the structure of a synchronous counter. We have flip flops and we call this ouput Q as Present State(of the FFs) and it goes to a combinational circuit and the output of comb circuit is called the Next State (NS) because upon the clock, the Next State becomes the Present State.

We call this combinational circuit as Next State Logic because it is a logic /comb circuit which decode the NextState(NS) from the Present State(PS).

Now how to design this Next State Logic ?

In order to design the NS Logic, we need to write the Truth Table in terms of the input (Present State) and Next State as shown below.

The Present State has 3 inputs (Q2, Q1, Q0) and the Next State has 3 outputs(D2, D1, D0). The moment we write the Truth Table, we have to look the D2 separately, D1 separately and D0 seperatlely and pick out the ‘1’ s in colomns of D2, D1 and D0 and minimize it using K map and come out with a SOP (sum of products)  equation in terms of Q2, Q1 and Q0. So ultimately you will get 3 boolean equations for Ds (D2, D1 and D0).

ie Di =Fi (Q2, Q1, Q0)  or

D2= F2(Q2, Q1, Q0);  D1= F1(Q2, Q1, Q0);  D0= F0(Q2, Q1, Q0);

ie    NS = function (Present State);

It is enough that if you describe the Truth table in terms of an HDL(VHDL or Verilog) in a high level design, you will get this design.

Reference: NPTEL Lecture series on Digital System design with PLDs and FPGAs by Kuruvilla Varghese, DESE, IISc Bangalore

Puzzle #3

This is similar to the Puzzle#1.

There are 50 sweets out of which 49 are good and one is bad which is having a different weight than the other 49. We have a weighing balance.

In minimum use of the weighing balance select one good sweet.

Major Constituents: Timing

Combinational Circuits : 

•     tpd : Propagation Delay
  • tpLH = tpd when output switches from LOW to HIGH
  • tpHL = tpd when output switches from HIGH to LOW

For combinational circuits, timing constraint is a propagation delay ‘tpd’. This means, if one of the input changes, how much time it take that input change to propagate to the output.

tpd is divided into two sections: tpLH and tpHL which will be different since the circuit is not symmetric. Depending on an input signal, may be the pMOS is ON or OFF, nMOS is ON or OFF, nMOS is in series, pMOS is in parallel etc. So depending on how the output switches(ie going from LOW to HIGH or HIGH to LOW), some part of the circuit is switched, some nMOS is involed, some pMOS is involved etc and we know that the mobility of electrons and holes are different, may be the sizes of the transistor depends on the design is different, that all will make difference in the propagation delay tpd.

Sequential Circuits : 

• ts:Setup Time- Minimum time input must be valid before the active clock edge
• th: Hold Time- Minimum time the input must be valid after the active clock edge
• tco/tcq: Propagation delay for the input to appear at the output from active clock edge

In case of an Edge triggered flipflop, its NOT that when the clock comes, whatever at the input D is immediately transferred to the output Q. It takes sometime, called tco(clock to output)  or the propagation delay for the input to appear at the output from the active clock edge.

Now the input goes to Q after the tco time. But for this to happen, the input itself should meet some timing requirements with respect to the active clock edge. The requirement is that the input should setup sometime before the clock edge.That time is called the Setup time ts.

Not only that, after the clock edge, the input should remain there for some time called the Hold time(th), then only the input will transfer to the output properly.

If these are not met (setup and hold conditions), we cannot guarantee the state of the output, it could become 1 or 0 or can even stuck in between.

Reference: NPTEL Lecture series on Digital System design with PLDs and FPGAs by Kuruvilla Varghese, DESE, IISc Bangalore

 

 

 

 

 

 

 

Can we use this Flip Flop ?

Given a Flip Flop with input D and output Q and a clock  CLK.

The timing parameters of the flop are :

Setup Time (ts) = 1ns

Clock to Q delay (tcq)= 1ns

Hold time (th)= 2ns .

Will this flip flop work properly? If not why ?

If it works properly what is the maximum frequency of operation?

Setup and Hold Timings with skew in clock path

In the last post we have discussed the setup and hold timings when there is a skew in the data path. In this section we will discuss the case when there is a skew in the clock path.

As shown in the diagram there is a 3 ns skew in the clock path. Assume that there is no skew in data path. We have a pin at CLK’ that suffers a delay of 3 ns before it reaching the CK port of the particular flip flop. We would like to know the relation of the data setup and hold time at D with respect to CLK’ where we have control.

The original clock(CLK) is shown and has a setup time of 2 ns and hold time of 1 ns with respect to D. The new reference clock CLK’ is appearing earlier to CLK by 3 ns.  If you refer to the waveforms you can see that, the data at D is setting up after the active edge of CLK’. So the setup time which was earlier 2ns is now -1 ns (2ns -3ns) which is negative. Now for the hold time, the data has to be stable for an additional 3 ns after the active edge of CLK’ resulting a hold time of 4 ns.

So this means that if there is a skew in the clock path, the setup time is reduced and the hold time is increased, both by the delay in the clock path. In this case the setup time can be negative which means that with respect to CLK’, the data is setup after the active clock edge.

Point to note:

• When there is a delay ‘t’ in the path to clock input, the setup time with respect to new reference point CLK’ is decreased by t and hold time is increased by t.
• In this case the setup time can take a negative value. A setup time of -t means that at point CLK’ the data at D can be setup ‘t’ time after the active clock edge.
• Setup time is defined as time before clock, the data has to be setup. So for setup time positive value is going backward from the clock edge and negative value means it is forward from the clock. For hold time, the reverse case applies.

Reference: NPTEL Lecture series on Digital System design with PLDs and FPGAs by Kuruvilla Varghese, DESE, IISc Bangalore

Setup and Hold Timings with skew in data path

We know that for a flip flop, the setup time and the hold time is specified at the input D as shown in the diagram. The timing parameters states that, with respect to the active clock(CLK) edge, there is a setup time (ts = 2ns) before which the data has to be setup and there is a hold time (th = 1ns) for which the data has to be held some time after the clock edge.

Here in this waveform, the data is changing from 0 to 1, 2 ns (ts) before the active clock edge and remain high for 2 ns up to the clock edge and 1 ns more after the clock edge and then it changes.

But many at a times we may take the input at a pin D’ on a chip, like a wire is going from a pin through a buffer and reaches at D. So there could be additional delays in the data path. Here in this case point D’ incur a delay of 2 ns w.r.t D, meaning that when you give a data at D’, it appears at D after 2 ns delay. When you supply a clock (assume CLK has no delay) we would like to know what is the setup time and hold time w.r.t the point D’, because we have control over this point only, we are supplying data from outside at this point and we are not worried about the setup and hold time at the point D since that doesn’t help us because there is an additional 2 ns delay.

what is the new setup time at D’ ?

With respect to CLK, the setup time has increased because the data at D’ has to be setup 4 ns (old 2ns(ts) + 2ns data path delay) before the active clock edge. So the data path delay 2 ns is added to the setup time and setup time has increased.

What is the new hold time at D’?

Hold time is 1 ns towards left of the active clock edge. Remember Setup time is defined as the time before the active clock edge, the data has to setup and the Hold time is defined as the time for which the data has to to be held after the active clock edge. But here in this case, the data is removed before the active clock edge (normally we remove data after the active clock edge) and so the hold time become -ve and is -1 ns (old 1ns (th) – 2 ns data path delay). When the hold time become -ve in the opposite direction, it means that you can remove the data at D’ even before the active clock edge.

Points to note

• When there is a delay ‘t’ in the path to D input, the setup time w.r.t new reference point D’ is increased by t and hold time is decreased by t.
• In this case hold time can take a -ve value. A hold time of -t means at point D’, the data can be removed or changed ‘t’ time before the active clock edge

Reference: NPTEL Lecture series on Digital System design with PLDs and FPGAs by Kuruvilla Varghese, DESE, IISc Bangalore

FIFO DESIGN #2

Here is another FIFO Depth calculation. The write side is 5MHz 10 bits and read side is 4MHz 12 bits. What is the minimum depth required for continuous data transfer.

Puzzle #2 River crossing

Here is another puzzle I was asked in an interview.

Four people A,B,C,D want to cross a river using a boat which can carry only two people at a time. A need 1 minute to cross the river while B,C,D requires 2,5 and 10 minutes respectively. What is the minimum time required for every one to be at the other side of the river.

Digital Design: Major Constituents

Suppose somebody asked us to design a Multiplier, what should we focus on?

Some may say that we should focus on Low Power, Low Area, working at a certain frequency etc.

• Function/Logic

The function or the logic is the primary part to consider while designing any system while power, area, frequency and all come later. What is the use if we get wrong results out of a design which is power wise or area wise or timing wise very perfect. In every data sheets of IC, the first thing stated is the function of the IC and that shows that function has priority over the others.

Puzzle #1 – Identify the odd ball

Here is a puzzle I got from an interview.

There are nine identical sized balls out of which one is having little less weight than other eight balls. We have a weighing balance available. The question is what is the minimum number of steps required to identify the odd ball?