In a cascaded 4 bit full adder setup what is the propogation delay?#

Find the propogation delay for 1 full adder and multiply by 4. For a full adder implementation the carry bit passess through two gates. So 8 is the answer.

Carry look ahead adder basic idea#

• You essentially calculate the carry while adding so no delay.
• If A and B are 1. Cout is always 1.
• If Cin is 1, either A or B has to be 1 for Cout to be 1.
• This means: Cout = AB + Cin*(A+B).
  • AB is called carry generator (Gi)
  • A + B is called carry propogate (Pi). You can also use A ^ B instead, since A and B both being 1 is already taken care off.
• Ci (Carry out of the ith full adder)Ci = Gi + Pi * C(i-1)
• After you find the carry just XOR with the Sum to get the final Sum.

Use XOR gates as control elements where you want either A or A'#

Hook up one input of the gate to A and the other to control signal.

• A ^ 0 = A
• A ^ 1 = A'

Turn an adder into a subtractor.#

You want the result as A-B. Which is same as A + B' + 1. (A + 2s compliment of B).

• Supply 1 to C0.
• Add inverter in the line of B.

Overflow and Carry#

• Unsigned operation
  • For unsigned addition, if Cout=1 is invalid
  • For unsigned subtraction Cout=0 is invalid
• Signed
  • For signed addition overflow is when Cin and Cout of the signed bit are not same. i.e OV = Cin ^ Cout.
  • The above rule also applies to subtraction.

Comparision#

• To compute signed A < B generally we do A-B and check if the MSB is 1 (-ve). But this fails during an overflow because the the actual MSB with the sign gets dropped and a -ve sign is not read. So the final check should be (A < B) = N ^ OV.

Shifters#

• Logical shifter: Left and right shift; fills empty spots with 0's
• Arithmetic Shifter: On right shift fills the new MSB with the old MSB. Left shift is same as logical
• Rotator: rotates the bits in a circle

good to know: Arithmetic right shift is division by 2. Logical left shift is multiplication by 2.

Counters#

• MSB toggles after every 2^N cycles which means MSB is clk/2^N.
• You can produce almost any frequency by adding p each cycle. MSB toggles at fout = fclk * (p/2^N).

Decoders#

• Essentially a minterm generator.
• Since you have access to all 2^n minterms, just OR them to get your desired function.
• A decoder with an enable pin can be used as a demux. The input is the line selector and the EN itself acts a data line.
• A decoder with an enable pin can be connected together to create a larger decoder.
  • If you have two 3x8 decoder with EN pin, use the EN as the 4th input (say X). EN1 gets X and EN2 gets X'. Now X acts as the MSB of the input. It is now a 4x16 decoder.

tip: If your function uses more than half the minterms, use a NOR gate instead of the OR. For n=3, say F=sum(1,2,3,4,5). Just feed the lines 6,7,8 into a NOR gate instead. You get the same function.

Standard decoders are active low (made using NAND instead of AND gates inside). Which means OR gates won't work to create the SOP(sum of products). Because AND-OR is same as NAND-NAND, replacing OR gates with NAND gates will create the same SOP of your function.

Encoders#

Multiplexer#

mental model: n input decoder is used to select 2^n lines. Each of those lines are AND'ed with a set of data lines. Finally OR all the AND gates and you have a mux.

• Another implementation is using tristate buffers.
• You can program any n input logic using a 2^n:1 mux. Just hardwire each data line according to the truth table and use the line selector as input.
• Folding one variable allows you to implement the same logic using a 2^(n-1):1 mux. Now your output might depend on the folded variable. An additional inverter can be used to get access X' (if X is the folded variable).
• If you fold two varibles you might also need 2 input gates. like X+Y or XY which in turn reduces you mux size by half again.

Glitch in combinational circuits (static hazards)#

It is when a single input transition causes multiple output transition. Often caused by data racing. This can be observed in situations where one input branches out to multiple gates and then converges at the output again. Consider Y = AB + A'C; say C=B=1. Now when A transtions from 1->0 there could be a breif moment where both A=A'=0 due to the delay of that NOT gate.

how to detect them: K maps help you find them easily. When transitioning from a state to another if you have to cross the boundary between two islands (circled groups) then it has a possibility of glitch.

Latch#

• SR Latch using cross-coupled NOR gates. (S=1, R=1) to (S=0, R=0) transition is metastable in the sense that fastest gate will flip first, hence the output is unpredictible. (S=0, R=0) does not change the state, so a typical set-reset goes like this: (0,0) -> (1,0) -> (0,0) -> (0,1). Use the (0,0) state to avoid going into (1,1) which results in (Q=0, Q'=0).
• SR Latch using cross-coupled NAND gates is the exact opposite of the above. (1,1) is the no-change state; (0,0) is the forbidden state. Set is (0,1) and reset is (1,0).
• NAND-Enable SR latch is just SR NAND latch with a control NAND gate inserted between S, R hooked upto an Enabled signal. Note that becuase of the new control NAND gate the entire thing behaves like SR NOR; except for any change to occur EN must be 1.
• D-Latch simplifies everything. You connect input D to S and compliment it to R. Now you have two options only. D=1 sets the latch and D=0 resets it. En=0 retains whatever was on it regardless of what D is.

Edge Triggered Latches (Flip-Flops)#

Master-Slave topology: Think of it as two air locked doors. When CLK=1 master is open. When CLK=0 slave is open. Both are never open at the same time. During CLK=1 master is transparent and lets data inside. During CLK 1->0 master tries to shut down the door locking the value of data and at the same time slave starts to open up. During CLK=0 slave is open and lets the data in as output locking it becuase master is now closed. Ideally both doors do not overlap but in practice both doors can be open at the same time for a small window through which data can rush directly to the output, hence the requirement for a hold time. Setup time is for the master to settle in.

Why latches cannot be used in circuits that run on a clock#

A latch can be changed during the level window of a clock pulse. This is not at all ideal. Imagine you have some hardware that implements count = count + 1; initially count = 0. When clock is high 0 is pushed to the adder and outputs 1 into the same latch. But our adder is really fast and finished well before the clock transition; meaning the latch is still enabled. So 1 goes to the adder and out comes 2. This will go on until the clock becomes low. Now you can see why this is a problem; you meant to increment it every clock cycle but now the value of count is unpredictible.

Moore vs Mealy#

• Moore looks only at the state registers to determine the output. That means output is updated only after each clock trigger.
• Mealy looks at both state registers and input to determine the output. It can get away with not encoding certain things into the register because it can react immediately to the input.

example: In a pattern detector Mealy does not need to encode the final "pattern found" as a separate state. It can immediately flag the output. Because it skips encoding, it is one clock cycle faster than Moore(also has one state less than Moore) and responds as soon as the last bit is found. Moore takes up one clock cycle to write that "found" state into register which then gets evaluated into the ouput in upcoming clock trigger.

Cyclic loop in the circuit does not imply it is sequential#

Consider Y = A + AY, this circuit has a loop but settles to Y = A. A cyclic looking path is not sequential if it does not have means to store state values.

Setup time (constraints)#