Digital Design Practice - 2

Counter from D flip flop:

Up	Down	Q2	Q1	Q0	Q2+	Q1+	Q0+
1	0	0	0	0	0	0	1
1	0	0	0	1	0	1	0
1	0	0	1	0	0	1	1
1	0	0	1	1	1	0	0
1	0	1	0	0	1	0	1
1	0	1	0	1	1	1	0
1	0	1	1	0	1	1	1
1	0	1	1	1	0	0	0

K maps for up:
D0 = Q0bar;
D1 = Q0 exor Q1;
D2 = Q2 exor Q1Q0

extending the logic: 4 bit counter

Q3	Q2	Q1	Q0	Q3+	Q2+	Q1+	Q0+
0	0	0	0	0	0	0	1
0	0	0	1	0	0	1	0
0	0	1	0	0	0	1	1
0	0	1	1	0	1	0	0
0	1	0	0	0	1	0	1
0	1	0	1	0	1	1	0
0	1	1	0	0	1	1	1
0	1	1	1	1	0	0	0

D3 = Q3.(Q2.Q1.Q0) + Q3bar((Q2Q1Q0)bar)

hence D3 = Q3 exor Q2Q1Q0

Did you start noticing the trend here? In fact even D0 = Q0 exor 1 to keep in line with the trend.  

Now lets add a count enable to this curry. 

D0 = Q0 exor en

D1 = Q1 exor Q0.en

D2 = Q2 exor Q1.Q0.en

D3= Q3 exor Q2.Q1.Q0.en

And now with the "en" in place it is so easy to obtain a 8 bit counter from 2 4-bit counters. 

Lower set of 4-bit counters follow above equation. 

Upper set follow same equation, simply replace en by Q3Q2Q1Q0en. 

Now if you notice this, the equation for D7 is Q7 exor Q6Q5Q4Q3Q2Q1Q0en. I dont like this ripple chain already. But my interview question was how does 128 bit counter schematic look like. My answer was to use a ripple counter with T flip flops. But the interviewer insisted that it be a synchronous counter, and he pointed out that T flip flops usually arent in the standard cell library. What the interviewer drew for me was a set of 128 flip flops which go to a 128-bit adder with other input to adder as 1. I am hoping the adder doesnt have a ripple carry :P My interview question was how can I save area in the implementation that the interviewer drew for me. I said either get equations for all D's and do it by eqations (that time I didnt know about this ripple chain) or use pipelining to reuse a 8 bit adder or whatever. 

I am going to count the gates for above circuit for 8 bit counter: 

Exor = 5 NAND gates = 4 exors=20 nand. 

Ands: 2/3/4 input nands + inverters.

upper set enable generation: and = 5 input nand + inverters

total transistors for the above implementation of 8 bit counter = 2(80+24) + 12 = 220 + D flip flops. 

For curiosity's sake I synthesized a 8 bit counter using Cadence RC. It was too complicated to post here, so downgraded to 4-bit counter for demo. Here it goes:

module counter(clk, reset, en, outp);

  input clk, reset, en;

  output [3:0] outp;

  wire clk, reset, en;

  wire [3:0] outp;

  wire UNCONNECTED, UNCONNECTED0, UNCONNECTED1, UNCONNECTED2, n_0, n_1,

       n_2, n_3;

  wire n_4, n_5, n_6, n_7, n_8, n_9, n_10, n_11;

  wire n_12;

  SFF \outp_reg[2] (.RD (reset), .CK (clk), .D (n_12), .SI

       (n_11), .SE (outp[2]), .Q (outp[2]), .SO (UNCONNECTED));

  SFF \outp_reg[3] (.RD (reset), .CK (clk), .D (n_0), .SI

       (outp[3]), .SE (n_10), .Q (outp[3]), .SO (UNCONNECTED0));

  SFF \outp_reg[1] (.RD (reset), .CK (clk), .D (n_7), .SI

       (n_6), .SE (outp[1]), .Q (outp[1]), .SO (UNCONNECTED1));

  INV g518(.A (n_11), .X (n_12));

  ND2 g517(.A1 (n_5), .A2 (n_8), .X (n_10));

  ND2 g519(.A1 (n_9), .A2 (outp[0]), .X (n_11));

  SFF \outp_reg[0] (.RD (reset), .CK (clk), .D (outp[0]),

       .SI (n_1), .SE (en), .Q (outp[0]), .SO (UNCONNECTED2));

  INV g524(.A (n_3), .X (n_9));

  INV g526(.A (n_2), .X (n_8));

  INV g520(.A (n_6), .X (n_7));

  INV g522(.A (n_4), .X (n_5));

  ND2 g523(.A1 (outp[0]), .A2 (outp[1]), .X (n_4));

  ND2 g525(.A1 (outp[1]), .A2 (en), .X (n_3));

  ND2 g527(.A1 (outp[2]), .A2 (en), .X (n_2));

  ND2 g521(.A1 (outp[0]), .A2 (en), .X (n_6));

  INV g529(.A (outp[0]), .X (n_1));

  INV g528(.A (outp[3]), .X (n_0));

endmodule

(Note: it used equation: Q = D*SEbar + SI*SE + D*SI). Quite ingenious the way it saved exor gates using scan flip flops.  8-bit counter was synthesized in the same way. Impressed!! but still think that what if there really was a scan chain that needed to be used. What would the circuit be synthesized to in that case!. For now I will stop here till I have enough patience to use DFT flow etc.

P.S: Technology schematic on Xilinx used look up tables. Note we should take the xilinx equations with a pinch of salt because a) if we are designing an asic from scratch, our equations are going to be different => either reduced or not reduced to avoid glitches, and b) in most circumstances we would not be using look up tables anyways if we are not using FPGAs.
D0 = Q0bar.  Qo -> inverter -> inverter output goes to D0
D1 = Q1 exor Q0
D2 = used a look up table with equation: D2 = ((Q0 * !Q2 * Q1) + (!Q0 * Q2) + (Q2 * !Q1)); 
D3 used a look up table with equation: D3 = ((Q3 * !Q1) + (Q0 * !Q3 * Q1 * Q2) + (!Q0 * Q3) + (Q3 * !Q2)); 

P.S 2) If we are using T flip flops to get a asynchronous 128 bit counter its going to need a gigantic verification effort. At each stage, the Q will toggle after "clock reaches previous stage + clock to Q delay of previous stage". So net delay from main clock toggles to FFx toggles is X*clock_to_Q_delay. Forget about 128 bit counter, we could have likely messed up things by 16 bit counter itself.

P.S 3) During my interview, I had said that ideally only least significant few bits are going to be toggling all the time. So maybe we can do something to use this to our advantage. That time I had said maybe there is another adder already lying around (something on the lines of Tomasulo's algorithm). So my best answer is: we have only a 8 bit counter (or whatever sounds reasonable, 16 bit or 32 bit, I definitely havent heard of a 128 bit microprocessor yet). Kind of have something as a mini Interrupt to signal that 8 bit counter overflew. Then store the rest of the count in registers and use the adder in ALU to increment the register. This way you are using the adder that is already present and saving on the area.