What is an adder subtracter circuit

14 adders and subtractors

Transcript

14 Adders and subtractors 14.1 Representation of positive and negative numbers The number of bit positions must be specified in order to distinguish between positive and negative numbers. Binary m -1 = 3 positive decimal sign and amount two's complement binary m -1 = 3 positive decimal sign and the amount of two's complement can. DIGITAL TECHNOLOGY 14-1

2 The two's complement (I) There is no sign - in the binary representation. Therefore half of the number supply is reserved for positive and the other half for negative numbers. Each number (including the zero) can only be represented unambiguously in the two's complement representation. The two's complement representation is also chosen in microprocessors for arithmetic operations. The subtraction can be traced back to the addition of two numbers in two's complement. Two's complement representation of negative numbers: Let z: Negative number z *: Amount z of the negative number zzp: Positive number Then the two's complement rule applies to m-digit numbers and radix 2: C (z) complement + z * + amount R m maximum number that can be represented + 1 (outside the range of numbers) DIGITAL TECHNOLOGY 14-2

3 The two's complement (II) -R m 2 z 0 z * R m 2 C (z) = R m - z * C (z) R m A real complement is described by non-overlapping number ranges: (e.g. for m = 3) Negative numbers: -R m-1 z <0-8 z <0 Positive numbers: 0 zp R mzp 7 Two's complement: R m-1 C (z)

4 Simplified two's complement formation Modified representation of the two's complement rule: C (z) = (R m - 1) - z * + 1 ± 1 where: (R m - 1): Because R = 2, a binary number in which all m places are 1 . (R m - 1) - z *: Since 1 0 = 1 and 1 1 = 0, it follows that this expression represents z * inverted in all bit positions. Conclusion: The two's complement of a negative number z is obtained by inverting all bit positions and then adding 1. Transforming the two's complement rule results in: z * = (R m - 1) - C (z) + 1 Conclusion: The absolute value of a negative number, which is represented by the two's complement C (z), is obtained by inverting all bit positions of the two's complement representation and then 1 is added. DIGITAL TECHNOLOGY 14-4

5 Addition and subtraction in two's complement The rules for unsigned and signed numbers are basically the same. However, two additional effects must be taken into account: Carry and borrow, which exceed the selected number range of m bits, must be ignored in order to obtain a correct result. The calculation results can leave the permitted number range of the two's complement representation. In this case the result is invalid and an overflow bit OV must be set (the only remedy here is to expand the number range to m + 1 bit). The overflow bit OV is set under the following conditions: When adding: A + B: - If both summands are positive and the result is negative. - If both summands are negative and the result is positive. When subtracting: A-B: - If the minuend A is negative and the subtrahend B is positive and the result is also positive. - If the minuend A is positive, the subtrahend B is negative and the result is negative. DIGITAL TECHNOLOGY 14-5

6 14.2 Structure of a full adder AB CI Σ SUM CI CO COUT CI BA COUT SUM Logical equations: Sum: SUM = AB CI Carry: COUT = (AB) (CI (AB)) Generate: CG = AB Propagate: CP = AB DIGITALTECHNIK 14 -6

7 14.3 Ripple-Carry Adders With n 1-bit adders, two n-bit wide binary words A and B can be added in a combinatorial circuit. To do this, all 1-bit adders must be cascaded. The ripple-carry effect is the progression of a toggle carry bit through the chain of 1-bit adders. It is based on the transit time delay of the individual adder stages and means that the result of the i-th digit is only available after i-transit times. If fractions are to be added, the number of places after the decimal point must be the same for both operands. The decimal place itself is arbitrary as it is not required for the addition. DIGITAL TECHNOLOGY 14-7

8 Simulation of the ripple-carry adder 9ns 9ns 9ns 9ns 20ns 20ns 20ns 20ns DIGITAL TECHNOLOGY 14-8

9 Analysis of the ripple-carry addition behavior (using the example of the addition of 0x01 + 0x0E + CIN = 0x10) The signal propagation times are: t plh = 9ns and t phl = 20 ns. The summation bits S0 ... S3 are possibly set in the meantime and then deleted again because the carry signal advances from stage to stage. Invalid values ​​are output in between. In this example, the signal delay results from: - The three carry signals C0, C1, C2 are set one after the other (3 * 9 = 27ns) - The last carry signal C2 clears the temporarily set summation bit S3 again (20ns) the output signal is only valid after 47ns. Depending on the old and new summands, the time until the valid values ​​appear can be very different! What is the worst-case situation and how long does the associated signal delay last? General disadvantage of ripple-carry adders: The signal propagation time of the adder increases with each bit by the propagation time of an adder stage. DIGITAL TECHNOLOGY 14-9

10 14.4 Carry-Look-Ahead adder A much faster solution that is independent of the word length is the forward-looking carry formation, which can take place simultaneously for all bit positions (carry-look-ahead). For this purpose, two additional signals are fed out of the full adders (see p. 6): Generate Signal: CG i indicates that an adder at position i is generating a carry signal C i as a result of the bit values ​​A i and B i. Propagate signal: CP i indicates that a carry signal C i-1 from the previous stage i-1 is passed on to the following stage i + 1. No. C i-1 B i A i CG i CP i C i S i Meaning C i is generated C i-1 is absorbed C i-1 is forwarded C i-1 is forwarded C i is generated Logical equations: CG i = A i B i CP i = (A i B i) DIGITAL TECHNOLOGY 14-10

11 4-bit carry-look-ahead structure (CLA) Σ Σ Σ Σ DIGITAL TECHNOLOGY 14-11

12 Carry-Look-Ahead Generator The formation of the carry signals CO i of the individual stages from the generate and propagate signals CG i and CP i can be described recursively: General expression: C i = C i-1 P i G i First stage i = 0: C 0 = C -1 P 0 G 0 By successive insertion one obtains the further stages: Second stage i = 1: C 1 = C 0 P 1 G 1 = (C -1 P 0 G 0) P 1 G 1 ... C 1 = (C -1 P 1 P 0) (P 1 G 0) G 1 The implementation takes place in a carry-look-ahead generator. Advantages: Each carry bit depends only on the input carry C -1 as well as the carry-generate and carry-propagate signals. All result bits are available at the same time. A maximum of 3 run times are required for this (2 * through the full adder stages and 1 * through the CLA generator). Disadvantage: higher hardware expenditure compared to the ripple carry adder (#Gatter = (n² + 9n) / 2) DIGITALTECHNIK 14-12

13 Simulation of a 4-bit carry-look-ahead adder 35ns 35ns 10ns DIGITAL TECHNOLOGY 14-13

14 VHDL description of a 4-bit carry-look-ahead adder The source code consists of three entities: 1. the full adder ADD_COMP 2. the carry-look-ahead generator CLA_GEN 3. the structural VHDL design of the carry-look-ahead adder CLA_ADD To clarify the time behavior, symbolic runtimes are used (10ns for the full adder signals, 15ns for the CLA generator signals) - 1-bit full adder for CLA generator entity ADD_COMP is port (A, B, CIN: in bit; SUM, CO, CG, CP: out bit); end ADD_COMP; architecture CLA_ARCH of ADD_COMP is begin SUM <= A xor B xor CIN after 10 ns; CO <= (A and B) or (CIN and (A xor B)) after 10 ns; CP <= A xor B after 10 ns; CG <= A and B after 10 ns; end CLA_ARCH; DIGITAL TECHNOLOGY 14-14

15 - 4-Bit Carry-Look-Ahead Generator entity CLA_GEN is port (G, P: in bit_vector (3 downto 0); CIN: in bit; C: out bit_vector (2 downto 0); CGOUT, CPOUT: out bit ); end CLA_GEN; architecture CLA of CLA_GEN is begin C (0) <= G (0) or (P (0) and CIN) after 15 ns; C (1) <= G (1) or (P (1) and G (0)) or (P (1) and P (0) and CIN) after 15 ns; C (2) <= G (2) or (P (2) and G (1)) or (P (2) and P (1) and G (0)) or (P (2) and P (1) and P (0) and CIN) after 15 ns; CPOUT <= (P (3) and P (2) and P (1) and P (0)) after 15 ns; CGOUT <= G (3) or (P (3) and G (2)) or (P (3) and P (2) and G (1)) or (P (3) and P (2) and P ( 1) and G (0)) after 15 ns; - or - (P (3) and P (2) and P (1) and P (0) and CIN) after 15 ns; - error !!!!! end CLA; DIGITAL TECHNOLOGY 14-15

16 Prof. Dr. J. Reichardt entity CLA_ADD is - 4-bit carry-look-ahead adder port (A, B: in bit_vector (3 downto 0); CIN: in bit; SUM: out bit_vector (3 downto 0); CGOUT, CPOUT: out bit); end CLA_ADD; architecture STRUCTURE of CLA_ADD is component ADD_COMP - component declaration of the full adder port (A, B, CIN: in bit; SUM, CO, CG, CP: out bit); end component; component CLA_GEN - component declaration of the CLA generator port (G, P: in bit_vector (3 downto 0); CIN: in bit; C: out bit_vector (2 downto 0); CGOUT, CPOUT: out bit); end component; signal CG, CP, CARRY: bit_vector (3 downto 0); - local signals of the architecture begin CARRY (0) <= CIN; VA: for I in 0 to 3 generate - generate 4 full adders and connect ADD: ADD_COMP port map (A (I), B (I), CARRY (I), SUM (I), open, CG (I), CP (I)); end generate VA; CLA: CLA_GEN port map (cg, CP, CIN, CARRY (3 downto 1), CGOUT, CPOUT); - CLA generator end STRUCTURE; DIGITAL TECHNOLOGY 14-16

17 Notes on the structural VHDL design Every already compiled entity can be used as a component on a higher level. A component declaration must exist in the higher design hierarchy. The name and the port definition must be specified in the same as in the entity declaration. The component declaration comes before the begin of the architecture. The components are instantiated by specifying a label and the component name. The components are connected to signals in a port map instruction. Here (as one possibility) the order of the signals or signal types transferred in the port map instruction must be identical to the signals in the component declaration. Output signals of a component do not have to be connected (open). It is possible to have components instantiated automatically in a for loop in a generate statement. The loop index does not have to be declared separately for this. Within the loop, e.g. when using bus signals, the loop index can be used. The loop is ended with an end generate statement. The for generate instruction, like the component instantiations, must have a label. DIGITAL TECHNOLOGY 14-17

18 14.5 Combined adder and subtractor 1-bit full adder / subtractor (AS_COMP): In order to keep the microprocessor hardware as simple as possible, the carry flag is often used inverted during subtraction (i.e. carry = 1 means NO carry during subtraction and with the addition a carry). The carry flag must be interpreted accordingly in the software! A selection input of the AS component decides: SEL = 0 addition (A + B) SEL = 0 subtraction (AB) SEL C n A n B n S n C n S n: SEL B n A n C n + 1 SEL B n A n C n C n DIGITAL TECHNOLOGY 14-18

19 4-bit ripple carry adder / subtractor DIGITALTECHNIK 14-19

20 Analysis of the 4-bit adder / subtracter DIGITALTECHNIK 14-20

21 14.6 Arithmetic in VHDL VHDL simulation and synthesis tools support some arithmetic operations. It is recommended to use the data type std_logic_vector for this purpose. To do this, in addition to the ieee.std_logic_1164 library, one of the libraries ieee.std_logic_unsigned (for unsigned arithmetic), ieee.std_logic_signed (for signed arithmetic) or ieee.std_logic_arith (for mixed unsigned and signed arithmetic: ieee; use ieee.std_logic_1164.all; use ieee.std_logic_unsigned.all; - Unsigned operations only - use ieee.std_logic_signed.all; - Only signed operations - use ieee.std_logic_arith.all; - Mixed operations, this library - only applies in connection with - the data types signed and unsigned !! entity XYZ is ... The comparison operators =, / =, <, <=,>,> = for the data type std_logic_vector are defined in these libraries. DIGITAL TECHNOLOGY 14-21

22 Arithmetic Operators Operator Meaning Example Synthesis ability + addition Y <= A + B synthesis ability - subtraction Y <= A - B synthesis ability abs Absolute value formation Y <= abs (a) synthesis ability * Multiplication Y <= A * B supported by most synthesis tools / division Y <= A / B mostly not suitable for synthesis ** Power of two Y <= 2 ** A only allows powers of 2, since this corresponds to a simple left shift of a binary number mod remainder of division A / BA mod B = A - B * n; (n is the integer part of the division) Y <= A mod B can be synthesized if B is a power of two of 2 examples see e.g. [13] and [39] The sign of the result is the same as that of B. rem remainder of division A / B. A rem B = A - (A / B) * B The sign of the result is the same as that of A. Y <= A rem B can be synthesized if B is a power of two of 2 examples see e.g. [13] and [39] DIGITALTECHNIK 14-22

23 Example: Combined adder / subtractor library IEEE; use IEEE.std_logic_1164.all; use IEEE.std_logic_signed.all; entity ARITH is port (a, b: in std_logic_vector (3 downto 0); SEL: in bit; SUM: out std_logic_vector (3 downto 0); ZERO: out bit); end ARITH; architecture BEHAVIOR of ARITH is begin P1: process (a, B, SEL) variable SUMVAR: std_logic_vector (3 downto 0); - Declaration of a variable begin if SEL = '0' then SUMVAR: = A + B; - addition else SUMVAR: = A-B; - subtraction end if; if SUMVAR = "0000" then - comparison to "0000" ZERO <= '1'; else ZERO <= '0'; end if; SUM <= SUMVAR; - output signal assignment end process P1; end BEHAVIOR; DIGITAL TECHNOLOGY 14-23

24 Synthesis result (Viewlogic) A prepared 4-bit combined adder / subtracter module is used. A quadruple OR is used to check for 0. If the bit_vector data type is to be used as input or output signals, conversion functions are required. These are declared as follows: function To_bit (s: std_ulogic; xmap: bit) return bit; function To_bitvector (s: std_logic_vector; xmap: bit) return bit_vector; function To_StdLogicVector (b: bit_vector) return std_logic_vector; A conversion between the scalar types bit and std_logic_vector does not exist! DIGITAL TECHNOLOGY 14-24