advertisement

Arithmetic Operations • We will review the arithmetic building blocks we have previously used, and look at some new ones. – – – – – Addition incrementer Addition/subtraction decrementer Comparison BR 8/99 Binary Adder F (A,B,C) = A xor B xor C G = AB + AC + BC These equations look familiar. These define a Binary Full Adder : A B Sum = A xor B xor Cin A Cout B Cout = AB + Cin A + Cin B = AB + Cin (A + B) Cin Co Ci S Full Adder (FA) Sum BR 8/99 4 Bit Ripple Carry Adder A(3) B(3) Cout C(4) A B Co A(2) B(2) C(3) Ci A B Co S Ci S Sum(3) A(1) B(1) C(2) A B Co Ci S Sum(2) Sum(1) A(0) B(0) C(1) A B Co Ci C(0) Cin S Sum(0) A[3:0] B[3:0] + SUM[3:0] BR 8/99 1 Incrementer A(3) A(2) A(1) A(0) EN xor xor xor xor Y(3) Y(2) Y(1) Y(0) A[3:0] Y[3:0] inc If EN = 1 then Y = A + 1 If EN = 0 then Y = A EN BR 8/99 How did we get the Incrementer equations? Full Adder equations: Sum = A xor B xor Cin Cout = AB or Cin A or Cin B = AB or Cin (A or B) Let B = 0, Cin = 1 so that Sum = A + 1. Then equations simplify to: SUM = A xor 1 xor 0 = A xor 1 = A’ Cout = 0 or 1 (A or 0) = A. If we want an “En” input, then we want SUM = A if En=0, else SUM = A+1 if En = ‘1’. Filling in the above equations: SUM = A En’ or A’ En = A xor En Cout = A En (note that Cout = 0 if En = 0). The “Cout” of one bit becomes the “En” signal for the next bit!!!! BR 8/99 A Subtractor What is subtraction? A-B = A + (-B) How do you take the negative of a number? Depends on the sign representation (signed magnitude, 1s complement, 2s complement). Lets assume 2’s complement since it is most common). (-B) = B’ + 1 So: A - B = A + (-B) = A + B’ + 1 BR 8/99 2 Subtractor using an Adder A[3:0] B[3:0] B’[3:0] SUM[3:0] = A - B + Cin 1 What if we want a block that can do both addition and subtraction? BR 8/99 Adder/Subtractor A[3:0] 0 2/1 Mux 1 B[3:0] + Y[3:0] Cin Sub VHDL representation: Y <= (A-B) when (Sub = ‘1’) else A+B; BR 8/99 Recall what a Comparator is... Equality comparator. N N A AeqB B A=B if A(0) = B(0) and A(1) = B(1) … and A(n-1)=B(n-1) Recall that “xnor” function is ‘1’ if A=0, B=0 or A=1, B=1! So AeqB is: AeqB = (A(0) xnor B(0)) and (A(1) xnor B(1)) and ….etc. BR 8/99 3 What is logic structure for equality comparator? A(N-1) B(N-1) A(N-2) B(N-2) xnor xnor A0 B0 xnor AND Tree (will be multiple AND gates in tree arrangement) AeqB BR 8/99 Is there another Logic structure possible? Compare “iteratively” from LSB to MSB If (A(0) = B(0) then if (A(1) = B(1) then …. If (A(N-1) = B(N-1) then AeqB = ‘1’; !!!!! A(N-1) B(N-1) A(1) B(1) A(0) B(0) AeqB Signal from one bit block to next is “enable” for that block. BR 8/99 Iterative Comparator Structure A(N-1) B(N-1) A(1) B(1) A(0) B(0) xnor AeqB An advantage to this structure is that the design for each bit is the same same, and we can extend it indefinitely. But it will be slow. BR 8/99 4 Two ways to do a Large AND function Multi-level. # of levels depends on total number of inputs, number of inputs on each gate. A tree arrangment like this will take more gates, but will be fast. A(0) A(1) A(2) A(N-1) Serial arrangement. Will take less gates, but will be slow. BR 8/99 What about “<“ (less than), “>” (greater than?) Full comparator. N N A AltB AeqB B AgtB The logic for AltB, AgtB depends on whether we are comparing signed numbers or not. We will assume unsigned numbers for now. BR 8/99 Logic for “AgtB” (unsigned) Consider A > B, both N bit numbers, A[N-1:0], B[N-1:0] If (A(N-1) = ‘1’ and (B(N-1) = ‘0’) then AgtB = ‘1’; A=1xxx… B=0xxxxx elsif ((A(N-1) = B(N-1)) and (A(N-2) = ‘1’ and (B(N-2)=‘0’) ) then AgtB = ‘1’; etc... A=01xx… B=00xxxx A=11xx… B=10xxxx Look at “bit(i)”. The enable signal from previous bit is A= B up until now . If this is ‘1’, then we need to do a comparison. However, if “AgtB” is already true, then we don’t need to do comparison and can skip this comparison! BR 8/99 5 Iterative Implementation of AgtB A(i+1) B(i+1) A(i) B(i) A(i-1) B(i-1) En_i En_o En_i En_o En_i En_o Skip_i Skip_o Skip_i Skip_o Skip_i en_o = (A xnor B) and en_i ; Skip_o A=B signal If (skip_i = ‘1’) then skip_o = ‘1’; else skip_o = en_i and (A and B’) ; end if; BR 8/99 Logic Implementation en_o = (A xnor B) and en_i; Can use a K-map to simplify this logic. If (skip_i = ‘1’) then skip_o = ‘1’; else skip_o = en_i and (A and B’) ; end if; en_i A B en_o The skip_o of the LAST bit is the AgtB signal! The en_o of the LAST bit is the AeqB signal! xnor What about AltB??? skip_o AltB = AgtB’ and AeqB’ skip_i BR 8/99 Final Comparator A(N-1) B(N-1) 1 En_i En_o 0 Skip_i A(i) B(i) En_i AltB <= B(0) En_i En_o Skip_i Skip_o A(0) En_o AeqB Skip_i Skip_o Skip_o AgtB not (AeqB) and not (AgtB); BR 8/99 6 A(7) B(7) A(6) B(6) A(5) B(5) A(4) B(4) A(3) B(3) A(2) B(2) A(1) B(1) A(0) B(0) En(2) En(2) En(1) En(1) En(4) En(4) En(3) En(3) En(6) En(6) En(5) En(5) En(7) Skip(8) Skip(7) Skip(6) Skip(5) Skip(4) Skip(3) Skip(2) Skip(1) skip(7) skip(6) skip(5) skip(4) skip(3) skip(2) skip(1) skip(0) 1 En(8) En(7) AeqB En(0) 0 For i’th bit: AgtB 8 Bit Comparator en(i) = (A(i) xnor B(i)) and en(i+1); If (skip(i+1) = ‘1’) then skip(i)= ‘1’; else skip(i) = en(i) and (A(i) and B’(i)) ; end if; BR 8/99 architecture a of comp is signal en, skip: std_logic_vector(8 downto 0); begin aeqb <= en(0); agtb <= skip(0); altb <= (not en(0)) and (not skip(0)); process (a,b) begin en(8) <= ’1’; skip(8) <= ’0’; for i in 7 downto 0 loop en(i) <= not (a(i) xor b(i)) and en(i+1); if (skip(i+1) = ’1’) then skip(i) <= ’1’; else skip(i) <= en(i+1) and (a(i) and not b(i)); end if; end loop; end process; end a; BR 8/99 VHDL architecture that implements comparator logic as shown on previous slides. Alternate VHDL specification architecture a of compa is begin aeqb <= ' 1'when (a = b) else ' 0' ; agtb <= ' 1'when (a > b) else ' 0' ; altb <= ' 1'when (a < b) else ' 0' ; Synthesis tool will pick a logic implementation for implementation of ‘=‘, ‘>’, ‘<‘ based on user constraints such as propagation delay. end a; BR 8/99 7 A B AeqB AltB AgtB Glitches in synthesized logic. Ok as long as we are using FFs toBRlatch result. 8/99 8