Digital Design practice - 4

Assume Cload on an EXOR-2 gate = 108 units. (yup I purposely chose it so that stage gain will be a whole number)
Approach one: every stage has equal gain
3 stage NAND realization of EXOR-2: stage 1: Y1= A NAND B
               stage 2: 2 branches, B1= Y1 NAND A, B2= Y1 NAND B
               stage 3: out = B1 NAND B2
Logical effort of 2 input NAND = 4/3.
L.E of path = 4/3 * 2 * 4/3 * 4/3
Gain of path = Cload/ Cin * path LE = 108 * 128/27 = 4 * 2 * 4 cubed
stage gain = Nth root of path gain, where N = number of stages, aka 3 in our example.
stage gain  = 8
(Note: Optimum gain is 4, though gain of 2-6 is also OK. Probably in this case we need to use a 4th stage?)
Working gate sizes backwards: gain = LE * Cout / Cin
Cin = LE * Cout / gain
Cin3 = 4/3 * 108/ 8 = 18
Cin2 = 4/3 * 18 / 8 = 3

since there were 2 branches at stage 2, Cout1 = 2*3=6
Cin3 = 4/3 * 6/ 8 = 1 (getting Cin =1 confirms that calculations are correct)

Now, get the gate sizes: suppose unit gate capacitance corresponds to 20 lambda
stage1: PMOS 2, NMOS 2 => PMOS or NMOS W/L is 10lambda/2 lambda
stage2: PMOS 6, NMOS 6 => W/L is 30lambda/2lambda
stage3: PMOS 36, NMOS 36 => W/L is 180lambda/2lambda

delay of nand2: falling: R/2*2C + R*(6C+4fC) = RC( 4f + 7)
rising: R*(4f+8)
average delay = 4f + 7.5

stage1 f=3*2=6, stage2 f=6, stage3 f= 6
delay of the exor gate designed above = 3*(4*6 + 7.5) = 94.5


Another way to solve this is such that every stage has equal fanout.  The 3rd technique to solve this is such that every stage has equal delay. In this case all 3 methods give same answer because all 3 stages are the same.
I will pick a different value of Cload for some extra practice.
Let Cload = 81.
Method2: equal fanout: F = cuberoot (81*2) = 5.45;
Cin2 = 5.45 * Cin1 /2 = 2.725
Cin3 = 2.725 * 5.45 = 14.85
Cload= 14.85 * 5.45 = 81 confirmed, and verified calculations.
delay = 3 (4f + 7.5)  = 3(4*5.45 + 7.5) = 87.9
Equal fanout method is very convenient to do quick mental calculations.
gate sizes: stage1: PMOS, NMOS W/L = 10 lambda/2 lambda
stage2: PMOS, NMOS W/L = 27.256 lambda/ 2lambda
stage3: PMOS, NMOS W/L= 148.586 lambda

I will pick a different combination for more practice. Lets do an OR gate with Cload = 15.
Method1: equal stage gain
NOR-2 g= 5/3, INV g=1, path LE 5/3 * 1 = 5/3
path gain = path LE * Cout / Cin = 5/3*15=25
stage gain = root (25) = 5
Cout/Cin * stage_LE = stage_gain
Cin = LE * Cout / stage_gain
Cin for inverter = 1 * 15/ 5 = 3.
Gtae sizing assuming unit capacitance = gate capacitance for 20 lambda
NOR-2: PMOS=16/2, NMOS =4/2
INV: PMOS = 40/2, NMOS = 20/2
delay of NOR2: rising: 2R/4*4C + 2R/2(4C + 4C + 2C + 5hC) = RC (12 + 5h)
falling: R(4C + 2C + 5h) = RC(6+5h)
average = RC(5h + 9)
stage1 f = 3/1 = 3, stage2 f = 15/3 = 5
delay = (5*3 + 9) + (3*5 + 3) = 42

Method2: equal fanout, f = root(15) = 3.87
Gate sizing:
NOR-2: PMOS 16/2, NMOS = 4/2
Cin2 = 3.87= 77.4 lambda cap, INV: PMOS=51.6/2, NMOS=25.8/2 => obviously we have to choose whole number sizing, PMOS = 52/2, NMOS=26/2
delay = 8*3.87 + 12 = 42.96

Method3: equal stage delay:
5h1+9=3h2+3, where h1h2=15
h2=(5h1+6)/3
h1*(5h1+6)=45
5h1square + 6h1 -45 =0,
roots = {-6 +/- root (36+4*5*45)}/10
h1= 2.46
delay = 2( 5*2.46 + 9) = 42.6
Note that all the 3 methods give very close results.
Also note that delay is least when using equal stage_gain.

Just for comparison, lets do OR using INV followed by NAND-2.
path LE = 1 * 4/3 = 4/3
path gain = 20
stage gain = root(20)=4.47
Cin2= 4/3*15/4.47=4.47
stage f2= 15/4.47 = 3.35, f1=4.47
delay = (3*4.47 + 3) * (4/3 * 3.35 + 9) = 30
Wow, the INV-NAND2 or gate is so much faster than NOR2-INV or gate.







   

Digital Design Practice - 3

So I was asked about sizing of NAND gates. I gave the regular textbook answer of PMOS = size 2, NMOS = 2. Then I was asked if I could use other sizes. I said yes I could downsize what I want faster and upsize the other to keep total resistance the same.
For instance I can choose NMOS sizes as 4R/3 and 4R. The gate with size 4R/3 will be much faster.

There's a small derivation for calculating gate size for least average delay. Here it goes:
For inverter driving other inverter
For NMOS: assume size X, assume PMOS is Y times as big as NMOS. so PMOS size is YX.
NMOS resi = R/X, cap = XC
PMOS resi = 2R/XY, cap=XYC
falling delay = R/X(XC + XC + XYC + XYC) = 2(1+Y)RC
rising delay = 4(1+Y)RC/Y
2 * t-average = 2RC (3+ Y + 2/Y)
to get minimum t-average we have to find derivative w.r.t Y
1-2/Ysquare = 0
Y = root-2

unit width transistor = 6 lambda (contact size 2, surrounded by 1 diffusion for diff-contact connection, surrounded by 1 lambda because if you want to have twice unit width and all, there is minimum spacing you need between 2 metals.) For unit average resistance:
6R/X + 12 R/root2*X = 2R
X = 3*root2 + 3 = 7.24 lambda

So for least average delay, inverter sizing is NMOS = 7.24 lambda, PMOS = root2 * 7.24 lambda = 10.24 lambda.

I was curious if this root2 sizing holds good for other gates too? and also for different driver-load combinations?
Lets choose a inverter driving NAND.
2 inputs of NAND are shorted together driven by INv, so its gate cap at inverter load = 2XC + 2XYC.
2* t-average = R/X ( XC + XYC + 2XC + 2XYC) + 2RC/XY (3XC + 3XYC)
2* t-average = 3RC (1+Y + 2/Y + 2)
2*t-average = 3RC(3 + Y + 2/Y)
Surprise surprise!! the root2 sizing holds good for this case too!!
So basically this Y + 2/Y part that contributes to derivative is coming from the mobility ratio which I assumed as 2.
So in general if NMOS mobility is n times PMOS mobility, for least average delay the PMOS is root-p times NMOS.

Case 2: Least sizing for NAND2
Temporarily taking X out of equation.
NMOS size = 2, PMOS size = Y
Assume NAND driving inverter.
Bottommost nmos sees:  2C + 2C + YC + YC + YC + C capacitance on its path to Y.
upper nmos sees:  3C + 3YC cap.
elmore delay when nmos on: RC/2(5+3Y+3+3Y) = RC(4+3Y)
each pmos sees: YC + YC + 2C + YC + C
elmore delay when one of the pmos on = 2RC/Y(3Y + 3)
2*t-average = RC(4+3Y + 6 + 6/Y)
3 -6/Ysquare = 0
Y = root2
PMOS size = root2, NMOS =2

Sometimes, elmore delay is also calculated in terms of how much resi. a capacitor sees. Same thing effectively.
rising delay when only 1 pmos on: 2R/Y( 3C+3YC) = RC(6/Y + 6)
falling delay when both nmos on: R/2*2C + R*(3C+3YC) = RC (4 + 3Y)

Case 3: Least sizing for NOR2 driving inverter
NMOS size = 1, PMOS size = 2Y
Topmost pmos sees: (2Y + 2Y + 2 + Y + 1)C = (5Y + 3)C
lower pmos sees: (3Y + 3)C
elmore delay when both pmos on: 2RC/2Y*(5Y+3) + 2RC/2Y*(3Y+3)  = RC(8+6/Y)
each nmos sees: (3+ 3Y)C
elmore delay when one of the nmos is on: RC(3+3Y)
2*t-average = RC(8 + 6/Y + 3 + 3Y)
-6/Ysquare+3 = 0
Y = root2
PMOS size = 2root2, NMOS size=1

It is quite impressive that Y came out to be root2 for gates when inverter was considered as the load.

Case 4: NOR3 driving F*NOR3
NMOS size=1, PMOS size = 3Y
pmos on: 2RC/3Y(9Y + 3 + 9FY + 3F) + 2RC/3Y(6Y+3 + 9FY + 3F) + 2RC/3Y(3Y+3 + 9FY +3F) =2RC/3Y(18Y +9+27FY + 9F)
=RC/(12+6/Y+18F+6F/Y)
one of the nmos on: RC(3Y+3 + 9FY + 3F)
2*t-average = RC(12 + 6/Y + 18F + 6F/Y + 3Y + 3 + 9FY + 3F)
 -(6F+6)/Ysquare + (3+9F) =0
Y=root {(6F+6)/(9F+3)}

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.  

Digital design practice

1. Sequence detector:
Easiest option for a small sequence is to use one hot encoding.
Example: circuit to detect the sequence 1001.
Just save past 4 input history aka 4 flip flops.
Output = Q.Q-1bar.Q-2bar.Q-3

Just putting up my practice encoding (non-one-hot):

2. Sequence Generator:
Simplest option is a bunch of flip flops arranged as shift registers, parallel load, shift out serially. The advantage of this approach is that new sequence is just as easy as the next set of data loaded in.
The way to generate same sequence over and over is to have a bunch of flip flops, again arranged as shift registers, but now the input data is determined by the "state" of flip flops.
The minimum number of flip flops needed depends upon the number of flip flops needed to get a unique state.
For instance lets get a simple sequence generator for sequence, 101001, 1st lets try with minimum = 3 flip flops, and check if all states are unique. In this case, they are unique with just 3 FFs.

3. Divide by 3 counter with equal duty cycle
The equal duty cycle is the catch here, and we have to use both positive and negative edge triggered flip flops.
My spur of the moment answer used 2 mod-3 counters, one on +ve edge and one on -ve edge, i anded their Q1bars to get divide-by-3-with-equal-duty-cycle.
The elegant solution is inspired by R.P.Jain, example 8.4.
It is a mod-3-counter, the output of which is fed to -ve edge triggered flipflop. With some output jugglery, we get required divide-by-3-with-equal-duty-cycle output.

4. Timing Analysis:
Data should be stable setup_time before clock edge and hold_time after clock edge.
Hence maximum [clock-to-q + combinational delay] (ignoring skew) < clock period - setup time
minimum [clock-to-q + combinational delay] > hold_time

Also note that hold_time + setup_time should be less than clock_period, else reduce the clock_frequency.
Solving Setup time violation
1. Reduce clock speed
2. Increase drive strength
Suppose initially a unit sized inverter is driving another unit inverter which drives a large load, lets call it Clarge.
delay = R(6C) + R(3C + Clarge)
Now lets add drive strength to inverter2 by using wider transistor => resistance goes down
delay = R(9C) + R/2(6C + Clarge)
3. Adding buffer to clock path, this effectively adds buffer_delay_time to hold_time and might cause hold violation.

Solving hold violation
1. Insert buffers in data path to increase minimum combinational delay.
2. If you discover a hold time violation after the chip is in silicon, do you just chuck out the chip? One of my interviewers told me this: just lower the Vdd. :)

5. Charged capacitor in parallel to uncharged capacitor
2 things happen here, a. charge is conserved, and b. voltage across the 2 capacitors must be same because they are in parallel.
Consider initial case: capacitor C1, charged to voltage V0. charge on capacitor = C1V0
When the capacitor is connected to uncharged capacitor, charge sharing takes place instantly.
Let V be common parallel combination voltage.
C1V0 = C1 V + C2 V
V = C1 /(C1+C2) * V0
The cool thing about this is what happens to the energy. Initial energy = 1/2C1V0^2, final energy = 1/2 (C1V0)^2 / C1+C2.
The difference in these 2 numbers is the energy spent in sending that charge from cap1 to cap2.

Charge sharing is an issue for dynamc logic. Lets consider a dynamic NAND gate, with NMOS for input A as inner input (drain connected to output bus). If input A = 1, and B=0 during evaluation phase, the expected output is 1. But because the uncharged parasitic capacitor on A is now in parallel with charged output capacitor, the actual output is (Cadiff/ Cadiff + Cload) * Vdd.  We need to use a weak pull-up PMOS to counteract this issue.