Файл: Circuit Design with VHDL (A.Pedroni, 2004).pdf

Figure 9.6

4-bit carry ripple adder and truth table of Full Adder Unit (FAU).

9.3Carry Ripple and Carry Look Ahead Adders

Carry ripple and carry look ahead are two classical approaches to the design of adders. The former has the advantage of requiring less hardware, while the latter is faster. Both approaches are discussed below.

Carry Ripple Adder

Figure 9.6 shows a 4-bit unsigned carry ripple adder. For each bit, a full adder unit (FAU, section 1.4) is employed. The truth table of the FAU is also shown. In it, a and b represent the input bits, cin is the carry-in bit, s is the sum bit, and cout is the carry-out bit. s must be high whenever the number of inputs that are high is odd (parity function), while cout must be high when two or more inputs are high (majority function). Notice in figure 9.6 that each FAU relies on the carry bit produced by the previous stage. This approach minimizes the size of the circuitry, at the expense of increased propagation delay.

Based on the truth table of figure 9.6, a very simple way of computing s and cout is the following:

s ¼ a XOR b XOR cin

cout ¼ (a AND b) OR (a AND cin) OR (b AND cin)

Therefore, a VHDL implementation of the carry ripple adder is straightforward. The solution shown below works for any number (n) of input bits, defined by means of a GENERIC statement in line 5. Simulation results from the circuit synthesized with the code below are shown in figure 9.7.

1LIBRARY ieee;

2USE ieee.std_logic_1164.all;

TLFeBOOK

Figure 9.7

Simulation results from the carry ripple adder of figure 9.6.

3 ---------------------------------------------

4ENTITY adder_cripple IS

5GENERIC (n: INTEGER := 4);

6PORT ( a, b: IN STD_LOGIC_VECTOR (n-1 DOWNTO 0);

7cin: IN STD_LOGIC;

8s: OUT STD_LOGIC_VECTOR (n-1 DOWNTO 0);

13SIGNAL c: STD_LOGIC_VECTOR (n DOWNTO 0);

14BEGIN

15c(0) <= cin;

16G1: FOR i IN 0 TO n-1 GENERATE

17s(i) <= a(i) XOR b(i) XOR c(i);

18c(i+1) <= (a(i) AND b(i)) OR

21END GENERATE;

22cout <= c(n);

23END adder;

24 ---------------------------------------------

Pre-defined ‘‘B’’ Operator

We have already seen that an adder can be implemented directly with the ‘‘þ’’ (addition) operator (section 4.1). In this case, a carry ripple type of solution will be normally implemented by the synthesizer. If, however, if we want the solution to be of a certain type (like the one presented next), then an explicit code must be written.

TLFeBOOK

Figure 9.8

4-bit carry look ahead adder.

Carry Look Ahead Adder

A diagram of a 4-bit carry look ahead adder is shown in figure 9.8. Its implementation is based on the generate and propagate concept, which gives the circuit higher speed than its carry ripple adder counterpart (at the expense of more silicon area).

Consider two input bits, a and b. The generate (g) and propagate (p) signals are defined as:

g ¼ a AND b

p ¼ a XOR b

Notice that such signals can be computed in advance, because neither depends on the carry bit.

If we consider now two input vectors, a ¼ a(n 1) . . . a(1)a(0) and b ¼ b(n 1)

. . . b(1)b(0), then the corresponding generate and propagate vectors are g ¼ g(n 1)

. . . g(1)g(0) and p ¼ p(n 1) . . . p(1)p(0), where

g( j) ¼ a( j) AND b( j)

p( j) ¼ a( j) XOR b( j)

Let us consider now the carry vector, c ¼ c(n 1) . . . c(1)c(0). The carry bits can be computed from g and p:

c(0) C cin

c(1) ¼ c(0)p(0) þ g(0)

TLFeBOOK

c(2) ¼ c(0)p(0)p(1) þ g(0)p(1) þ g(1)

c(3) ¼ c(0)p(0)p(1)p(2) þ g(0)p(1)p(2) þ g(1)p(2) þ g(2), etc.

Notice that, contrary to the carry ripple adder, each carry bit above is computed independently; that is, none of the expressions above depends on preceding carry computations, and that is the reason why this circuit is faster. On the other hand, the hardware complexity grows very fast, limiting this approach to just a few bits (typically four). Larger carry look ahead adders can be implemented by associating such 4-bit-or-so units.

The implementation of the adder of figure 9.8 is now straightforward. The PGU (Propagate—Generate Unit) computes p and g (four units are required), plus the actual sum (s), while the CLAU (Carry Look Ahead Unit) computes the carry bits.

Note: In order to construct bigger carry look ahead adders, the CLAU block of figure 9.8 must posses Group Propagate (GP) and Group Generate (GG) outputs, which were omitted in the figure because this implementation is intended for four bits only.

1 ---------------------------------------------

2LIBRARY ieee;

3 USE ieee.std_logic_1164.all;

4 ---------------------------------------------

5ENTITY CLA_Adder IS

6PORT ( a, b: IN STD_LOGIC_VECTOR (3 DOWNTO 0);

7cin: IN STD_LOGIC;

8s: OUT STD_LOGIC_VECTOR (3 DOWNTO 0);

13SIGNAL c: STD_LOGIC_VECTOR (4 DOWNTO 0);

14SIGNAL p: STD_LOGIC_VECTOR (3 DOWNTO 0);

15SIGNAL g: STD_LOGIC_VECTOR (3 DOWNTO 0);

16BEGIN

17---- PGU: ---------------------------------

18G1: FOR i IN 0 TO 3 GENERATE

19p(i) <= a(i) XOR b(i);

20g(i) <= a(i) AND b(i);

21s(i) <= p(i) XOR c(i);

TLFeBOOK

22END GENERATE;

23---- CLAU: --------------------------------

24c(0) <= cin;

25c(1) <= (cin AND p(0)) OR

39cout <= c(4);

40END CLA_Adder;

41---------------------------------------------

Qualitatively, the simulation results obtained from the circuit synthesized with the code above are similar to those from the carry ripple adder presented in figure 9.7.

9.4 Fixed-Point Division

We saw in chapter 4 that the pre-defined ‘‘/’’ (division) operator accepts only power of two divisors, that is, it is indeed a ‘‘shift’’ operator. In this section, we will discuss the implementation of generic division, in which the dividend and divisor can be any integer. We start by describing the division algorithm, then we present two VHDL solutions followed by simulation results.

Division Algorithm

Say that we want to calculate y ¼ a/b, where a, b, and y have the same number (n þ 1) of bits. The algorithm is illustrated in figure 9.9, for a ¼ ‘‘1011’’ (decimal 11) and b ¼ ‘‘0011’’ (decimal 3), from which we expect y ¼ ‘‘0011’’ (decimal 3) and remainder ‘‘0010’’ (decimal 2). We first create a shifted version of b, whose length is 2n þ 1 bits (shown in the b-related column in figure 9.9). b_inp(i) is simply b shifted to the left by i positions (notice the underscored characters in the b-related column).

TLFeBOOK

The computation of the quotient is performed as follows. Starting from the top of the table, we compare a_inp(i) with b_inp(i). If the former is bigger than or equal to the latter, than y(i) ¼ ‘1’ and b_inp(i) is subtracted from a_inp(i); otherwise, y(i) ¼ ‘0’ and we simply proceed to the next line. After n þ 1 iterations, the computation is completed and the value left in a_inp is the remainder.

Note: It is obvious that, to subtract b_inp from a_inp, the number of bits of a_inp cannot be less than that of b_inp, so the actual length of a_inp must be increased, which is attained by simply filling a_inp with n ‘0’s on its left-hand side (‘0’s not shown in figure 9.9).

Another way of presenting the division algorithm is the following. We multiply b by 2**n, where n þ 1 is the number of bits. This, of course, corresponds to shifting b n positions to the left, but without throwing out any of its bits (so the new b-vector must be n bits longer than the original vector). If a is bigger than the new b, then y(n) ¼ ‘1’, and b (the new value) must be subtracted from a; otherwise, y(n) ¼ ‘0’. Now we move to the next iteration. We multiply b (the original value) by 2**(n 1), which is equivalent to shifting the original vector n 1 positions to the left, or shifting the value of b just used in the previous computation back one position to the right. Then we compare it to a, as we did before, to decide whether y(n 1) should be ‘1’ or ‘0’, and so on.

VHDL Dividers

Below are two solutions for the division problem. Both use sequential code: IF is used in the first, while LOOP plus IF are employed in the second. The first solution is a step-by-step code, so the division algorithm described above can be clearly observed. The second is more compact and is also generic (notice that n was defined

TLFeBOOK

Figure 9.10

Simulation results of divider (for 4-bit operands).

by means of a GENERIC statement in line 6). The solutions include also a b ¼ 0 check routine.

Simulation results are shown in figure 9.10.

1 ----- Solution 1: step-by-step -------------------

2LIBRARY ieee;

3 USE ieee.std_logic_1164.all;

4 --------------------------------------------------

5ENTITY divider IS

6PORT ( a, b: IN INTEGER RANGE 0 TO 15;

7y: OUT STD_LOGIC_VECTOR (3 DOWNTO 0);

8rest: OUT INTEGER RANGE 0 TO 15;

13BEGIN

14PROCESS (a, b)

15VARIABLE temp1: INTEGER RANGE 0 TO 15;

16VARIABLE temp2: INTEGER RANGE 0 TO 15;

17BEGIN

18----- Error and initialization: -------

19temp1 := a;

20temp2 := b;

21IF (b=0) THEN err <= '1';

22ELSE err <= '0';

23END IF;

24----- y(3): ---------------------------

TLFeBOOK

25IF (temp1 >= temp2 * 8) THEN

26y(3) <= '1';

27temp1 := temp1 - temp2*8;

28ELSE y(3) <= '0';

29END IF;

30----- y(2): ---------------------------

31IF (temp1 >= temp2 * 4) THEN

32y(2) <= '1';

33temp1 := temp1 - temp2 * 4;

34ELSE y(2) <= '0';

35END IF;

36----- y(1): ---------------------------

37IF (temp1 >= temp2 * 2) THEN

38y(1) <= '1';

39temp1 := temp1 - temp2 * 2;

40ELSE y(1) <= '0';

41END IF;

42----- y(0): ---------------------------

43IF (temp1 >= temp2) THEN

44y(0) <= '1';

45temp1 := temp1 - temp2;

46ELSE y(0) <= '0';

47END IF;

48----- Remainder: ----------------------

49rest <= temp1;

50END PROCESS;

51END rtl;

52 --------------------------------------------------

1 ------ Solution 2: compact and generic -----------

2LIBRARY ieee;

3 USE ieee.std_logic_1164.all;

4 --------------------------------------------------

5ENTITY divider IS

6GENERIC(n: INTEGER := 3);

7PORT ( a, b: IN INTEGER RANGE 0 TO 15;

8y: OUT STD_LOGIC_VECTOR (3 DOWNTO 0);

TLFeBOOK