Report

Review for Exam 2 Chapters 4 and 5 Close book and close notes Bring pencil No computers or cell phones allowed Logic and Computer Design Fundamentals Chapter 4 – Arithmetic Functions Charles Kime & Thomas Kaminski © 2008 Pearson Education, Inc. (Hyperlinks are active in View Show mode) Implementations: Half-Adder The most common half adder implementation is: S = XY C = XY X Y S C X Y C S 0 0 1 1 0 0 0 1 0 1 1 0 0 1 0 1 Implementation: Full Adder Full Adder Schematic for bit i Gi Si =(Ai Bi)Ci Co = AB + (AB)Ci or Ci+1 = AiBi + (AiBi )Ci Ai Bi Pi with G = generate (=AB) and P = propagate (=AB) Ci+1 = Gi + Pi · Ci or: Ci+ 1 Si Co= (G = Generate) OR (P =Propagate AND Ci = Carry In) Ci 4-bit Ripple-Carry Binary Adder A four-bit Ripple Carry Adder made from four Ai Bi 1-bit Full Adders: Ci+1 FA Si Slow adder: many delays from input to output Ci Delay of a Full Adder Assume that AND, OR gates have 1 gate delay and the XOR has 2 gate delays Delay of the Sum and Carry bit: = Gi Si Ai Bi Ci Ai Bi S0= A0 B0 C0 2 delays 2+2=4 delays P i Ci Ci+1=AiBi+ ( Ai Bi) Ci C1 =A0B0+ ( A0 B0) C0 @2 Ci+ 1 Si @3 2+2=4 delays Delay of the Carry C2 = A1B1+ ( A1 B1) C1 @2 @4 @? Gi Ai Bi @? C3 = A2B2+ ( A2 B2) C2 @2 @6 Pi @7 @8 C4: delay 8+2 = 10 Ci+1 For n stage: delay of Cn: 2n+2 delays! and Sn: 2n+4 ([email protected] + 2) The bottleneck is the delay of the carry. Si Ci Delay in a Ripple-carry adder Example: 4-bit adder (n=4) @0 @0 @10 @10 @4 @6 @8 @8 @6 @4 One problem with the addition of binary numbers is the length of time to propagate the ripple carry from the least significant bit to the most significant bit. Example: 32-bit Ripple-carry has a unit gate delay of 1ns. •What is the total delay of the adder? •What is the max frequency at which it can be clocked? Carry Lookahead Adder Uses a different circuit to calculate the carry out (calculates it ahead), to speed up the overall addition Requires more complex circuits. Trade-off: speed vs. area (complexity, cost) PFA generates G and P @6 4-bit Implementation @6 @6 @4 @4 C 1 = G0 + P 0 C 0 C2= G1 + P1G0 + P1P0 C0 @4 C3= G2 + P2G1 + P2P1G0 + P2P1P0 C0 Carry lookahead logic @4 4-3 b. Complements Two type of complements: • Diminished Radix Complement of N Defined as (rn - 1) – N, with n = number of digits or bits 1’s complement for radix 2 • Radix Complement Defined as rn - N 2’s complement in binary As we will see shortly, subtraction is done by adding the complement of the subtrahend If the result is negative, takes its 2’s complement Binary 1's Complement For r = 2, N = 0111 00112, n = 8 (8 digits): (rn – 1) = 256 -1 = 25510 or 111111112 The 1's complement of 011100112 is then: 11111111 rn – 1 - N – 01110011 1’s compl 10001100 Since the 2n – 1 factor consists of all 1's and since 1 – 0 = 1 and 1 – 1 = 0, the one's complement is obtained by complementing each individual bit (bitwise NOT). Binary 2's Complement For r = 2, N = 0111 00112, n = 8 (8 digits), we have: (rn ) = 25610 or 1000000002 The 2's complement of 01110011 is then: 100000000 rn - N – 01110011 2’s compl 10001101 Note the result is the 1's complement plus 1: 01110011 Invert bit-wise 10001100 + 1 2’s complement 10001101 Alternate 2’s Complement Method Given: an n-bit binary number, beginning at the least significant bit and proceeding upward: • Copy all least significant 0’s • Copy the first 1 • Complement all bits thereafter. 2’s Complement Example: 10010100 • Copy underlined bits: 100 • and complement bits to the left: 01101100 3-3c. Subtraction with 2’s Complement For n-digit, unsigned numbers M and N, find M N in base 2: Algorithm Add the 2's complement of the subtrahend N to the minuend M: M + (2n N) = M N + 2n Unsigned 2’s Complement Subtraction Example 1 Find 010101002 – 010000112 84 -67 17 Discard carry 101010100 01010100 –01000011 2’s comp + 10111101 00010001 The carry of 1 indicates that no correction of the result is required Unsigned 2’s Complement Subtraction Example 2 Find 010000112 – 010101002 67 -84 -17 01000011 – 01010100 0 01000011 2’s comp + 10101100 11101111 2’s comp 00010001 The carry of 0 indicates that a correction of the result is required. Result = – (00010001) Signed Binary Numbers So far we focused on the addition and subtraction of unsigned numbers. For SIGNED numbers: • How to represent a sign (+ or –)? One need one more bit of information. Two ways: • Sign + magnitude • Signed-Complements Thus: • Positive number are unchanged • Negative numbers: use one of the above methods Exercise Give the sign+magnitude, 1’s complement and 2’s complement of (using minimal required bits): Sign+Mag +2 010 -2 110 +3 011 -3 111 +0 000 -0 100 One’s compl. 010 101 011 100 000 111 Two’s compl. 010 110 011 101 000 000 2’s Complement Arithmetic Addition: Simple rule • Represent negative number by its 2’s complement. Then, add the numbers including the sign bits, discarding a carry out of the sign bits (2's complement): • Indeed, e.x. M+(-N) M + (2n-N) If M ≥ N: (M-N) + 2n ignore carry out: M-N is the answer in two’s complement) If M ≤ N: (M-N) + 2n = 2n – (N-M) which is 2’s complement of the (negative) number (M-N): -(N-M). Subtraction: M-N M + (2n-N) Form the complement of the number you are subtracting and follow the rules for addition. Overflow examples (continued) carries 18 +15 33 011110 010010 +0 0 1 1 1 1 100001 -31! wrong answer due to overflow 18 - 15 3 110000 010010 +1 1 0 0 0 1 000011 3 correct answer no overflow Overflow occurs when the carry-in into the sign bit (most left bit) is different from the carry-out of the sign bit. Logic and Computer Design Fundamentals Chapter 5 – Sequential Circuits Charles Kime & Thomas Kaminski © 2008 Pearson Education, Inc. (Hyperlinks are active in View Show mode) 5-1 Sequential circuit block diagram Outputs Inputs Combinational Logic Next State Storage State Elements (or present state) Combinatorial Logic gives: CLOCK •Next state function Next State = f(Inputs, State) •Output function Synchronous machine Types of Sequential Circuits Illustra Moore machine: • Outputs = h(State) Mealy machine • Outputs = g(Inputs, State) Mealy Comb. Outputs logic Inputs Combinational Logic Next State Storage State Elements (or present state) CLOCK Basic (NOR) S – R Latch Function Table: R (reset) S (set) Q Q This element is also the basic building block in SRAM memories S R Q Q 0 0 hold, no change 0 1 0 1 Reset 1 0 1 0 Set 1 1 0 0 not allowed, unstable (Q=Q) Timing waveforms of NOR S-R latch S 0 R 0 Q 0 Q 1 S 1 Q R 2 Q set reset tpd No change unstable not allowed Clocked (NOR) S-R Latch S 1 Q 2 Q Clk R • Clk=0: input has no effect: latch is always in “hold” mode • Clk=1: latch is a regular S-R latch Function table of the (NAND) S - R latch S (set) R (reset) Function table: S R 1 1 0 1 1 0 0 0 Q Q Q Q hold, no change 1 0 Set 0 1 Reset 1 1 not allowed, unstable (Q=Q=1) S = 0, R = 0 is forbidden as input pattern Latch with NAND A A = 1 A A When both S=R=1: the NAND gates act as inverters and the circuit implements two inverters: “hold mode” Q 1 Q Q Clocked latch: C 0 1 1 1 1 S x 0 0 1 1 R Next state Q(t+1) S Q(t) no change x 0 Q(t) no change Q(t+1) = 0, Reset C 1 0 Q(t+1) = 1, Set 1 Q=Q’=1 UndefinedR 1 Q S Q R Q D Latch (Delay latch) S-R Latch can be used D for at D Latch: Q C Q(t+1) SR latch: S R Q+ Q+ 0 0 hold, 0 1 0 1 1 0 1 0 1 1 0 0 Q D Q C Q Function table D latch: D Q(t+1) 0 0 1 1 Latch issues Latches can cause serious timing problems (races) in sequential circuits • Due to the fact that a latch is “transparent” when the clock C = 1 The timing problems can be prevented by using “Flip-Flops” The Latch Timing Problem (continued) Similar timing problems in the sequential circuits: Outputs Inputs X0 X2 Combinational Logic X1 X2 X3 Next State D Latch X0 X1 X2 (storage) State C=0 1 • The state should change only once every new clock cycle: • C=1: • Now the current state becomes X1 and a new state is generated by the combinational logic circuit: X2. • However, if C=1, the new “next state” X2 will create a new current state X2!, etc… How to solve the timing problem: use Flip-Flops A solution to the latch timing problem is to break the closed path from In to Out within the storage element In D Q In Out D Q C Q C: 0 1 C: 0 1 C Q Out D-Flip-Flop D-Latch C C In In Out Out Symbol: Master-Slave Flip-Flop S S C C R R Q Y S Q Q Q Q C Q Y’ R Notice; the output changes when the clock C goes low. C Symbol: S Q C R Q Sometimes one adds: To indicate that the input responds when C=1, but the output changes when C goes to 0 Flip-Flop Problem: 1’ catching Glitch C S R Y Master out Q Slave out Master Slave active active S S C C R R 1’ catching Q Y S Q Q Q Q C Q Y’ R wrong output should have been 0 Flip-Flop Solution: Edge-triggered An edge-triggered flip-flop changes values at the clock edge (transition): • responds to its input at a well-defined moment (at the clock-transition) • ignores the pulse while it is at a constant level Negative edge-triggered Clock Positive edge-triggered ignored In The value of the input at the clock transition (negative or positive) determines the output Edge-Triggered D Flip-Flop D D Q S Q Q Q Q C C C Q R The 1s-catching behavior is not present with D replacing S and R inputs The change of the D flip-flop output is associated with the negative edge at the end of the pulse: It is called a negative-edge triggered flip-flop No 1’s catching in the edge-triggered D Flip-Flops D D Q C C Q Y S C R Q Q Q Q C D Y Master out Q Slave out Master active Slave active no 1’ catching correct output Exercise Timing diagram of a (Nor) S-R MasterSlave Flip-Flop S Q C R C Master active Q = S S C C R R Q Y S Q Q Q Q C Q Y’ R Slave active Master active S R Y undefined Y’ undefined Master out Q Slave out undefined Direct inputs: active-low or activehigh D flip-flop with active-low direct inputs : Direct inputs S D Q C R Q S 0 1 1 1 Active high direct inputs: D S Q C Q R S 0 1 0 0 R 1 0 1 1 C x x D x x 0 1 Q 1 0 0 1 Q’ 0 1 1 0 R 1 0 0 0 C x x D x x 0 1 Q 0 1 0 1 Q’ 1 0 1 0 5-4 Sequential Circuit Analysis Consider the following circuit: input x Q A C Q’ A Q B D D CLK states What does it do? How do the outputs change when an input arrives? C Q' y output Step 1: Input and output equations DA x • DA = A(t)x(t)+B(t)x(t) • DB = A(t)x(t) Q A C Q’ A Q B D Next State Output y DB • y(t) = x(t)(B(t) + A(t)) D CLK C Q' y Output Present state Boolean equations for the inputs to the flip flops: State Table For the example: A(t+1) = A(t)x(t) + B(t)x(t) B(t+1) =A (t)x(t) y(t) =x (t)(B(t) + A(t)) (2m+n) rows 23 rows Inputs of the table m: no. of FF n: no. of inputs Outputs of the table Present State Input Next State Output A(t) B(t) 0 0 0 0 0 1 0 1 1 0 1 0 1 1 1 1 x(t) 0 1 0 1 0 1 0 1 A(t+1) B(t+1) y(t) 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 1 0 1 0 1 0 State diagram convention Moore Machine: Mealy Machine: to next state In/out in State out Example: AB y State 1 x 01 1 Moore type output depends only on state x/y’ x=1/y=0 01 01 Mealy type output depends on state and input State Diagram for the example Graphical representation of the state table: x=0/y=0 x=0/y=1 AB 00 x=1/y=0 x=0/y=1 1 0 x=1/y=0 Present State Input Next State Output A(t) B(t) 0 0 0 0 0 1 0 1 1 0 1 0 1 1 1 1 x(t) 0 1 0 1 0 1 0 1 A(t+1) B(t+1) 0 0 0 1 0 0 1 1 0 0 1 0 0 0 1 0 y(t) 0 0 1 0 1 0 1 0 x=1/y=0 x=0/y=1 11 01 x=1/y=0 Equivalent State Example 0/0 Are there other equivalent states? Examining the new diagram, states S1 and S2 are equivalent since S0 1/0 • their outputs for input 0 is 1 and input 1 is 0, and • their next state for input 0 is both S0 and for input 1 is both S2, Replacing S1 and S2 by a single state gives state diagram: S1 0/1 1/0 0/1 S2 1/0 0/0 S0 1/0 S1 0/1 1/0 Exercise: Derive the state diagram of the following Circuit Logic Diagram: D Q A C RQ Moore or Mealy? What is the reset state? D Q B C RQ 5V D Q Reset • • Clock CR Q C Z 5-5 Sequential Circuit Design Idea, New product Specification ? IN •Word description State Diagram Comb. Crct. DA DB •State Table State encoding Design procedure •Select type of Flip-flop •Input equations to FF, output eq. •Verification O U T Specification Component Forms of Specification • • • • • • Written description Mathematical description Hardware description language Tabular description Equation description Diagram describing operation (not just structure) 5-6 Other Flip-Flop Types J-K and T flip-flops • Behavior • Implementation Basic descriptors for understanding and using different flip-flop types • Characteristic tables • Characteristic equations • Excitation tables J-K Flip-flop Behavior of JK flip-flop: • Same as S-R flip-flop with J analogous to S and K analogous to R • Except that J = K = 1 is allowed, and • For J = K = 1, the flip-flop changes to the opposite state (toggle) Behavior described by the characteristic table (function table): J Q C K J 0 0 1 1 K Q(t+1) 0 Q(t) no change 1 0 reset 0 1 set 1 Q(t) toggle T Flip-flop Behavior described T by its characteristic 0 1 table: • Has a single input T For T = 0, no change to state For T = 1, changes to opposite state Q(t+1) Q(t) no change Q(t) complement Characteristic equation: Q(t+1)=T’Q(t) + TQ’(t) = TQ(t) T C