Chapter 1 Basic Principles of Digital Systems outlin e 1

—— addsub4g.vhd

ENTITY addsub4g IS

PORT (

a, b : IN BIT_VECTOR (4 downto 1);

c4 : OUT BIT;

sum : OUT BIT_VECTOR (4 downto 1));

END addsub4g;

ARCHITECTURE adder OF addsub4g IS

—— Component declaration

COMPONENT full_add

PORT (

a, b, c_in : IN BIT;

END COMPONENT;

—— Define a signal for internal carry bits

SIGNAL c : BIT_VECTOR (4 downto 0);

SIGNAL b_comp : BIT_VECTOR (4 downto 1);

BEGIN

c(0) __ sub;

adders:

FOR i IN 1 to 4 GENERATE

—— do not invert for add (b(i) xor 0)

b_comp(i) __ b(i) xor sub;

adder: full_add PORT MAP (a(i), b_comp(i), c(i-1), c(i),

sum(i));

END GENERATE;

c4 __ c(4);

END adder;

XOR as a Programmable Inverter

➥ addsub4g.vhd

6.6 • Binary Adders and Subtractors 255

The VHDL code for the adder/subtractor is the same as that for the 4-bit adder created

using aGENERATE statement, except that there is an input to select the add or subtract function.

This input (sub) is tied to c(0) and to a set ofXORfunctions that invert b for subtraction.

Input b is transferred through the XOR functions without inversion for the add function.

FIGURE 6.17

Example 6.21 Simulation of a

4-bit Adder/Subtractor

❘❙❚ EXAMPLE 6.23 Note that the simulation in Figure 6.17 shows some intermediate states on the sum waveform

in between steady state values. Examine the transition from the sum F _ 0 _ F to the

sum F _ 1 _ 10 by using the Zoom In function in the Simulator window. Briefly explain

how the intermediate states arise in this transition.

SOLUTION Figures 6.18 and 6.19 show the transition from F _ 0 _ F to F _ 1 _ 10.

The transition on the sum waveform is from F to E to 0 or in binary from 1111 to 1110 to

7 _ 1 _ 8 0111 _ 0001 _ 0 1000 (Unsigned)

8 _ 8 _ 10 1000 _ 1000 _ 1 0000 (Unsigned)

A _ 1 _ B 1010 _ 0001 _ 0 1011 (Unsigned)

F _ 0 _ F 1111 _ 0000 _ 0 1111 (Unsigned)

F _ 1 _ 10 1111 _ 0001 _ 1 0000 (Unsigned)

0 _ 1 _ F 0000 _ 0001 _ 1111 (Signed: _1)

0 _ 8 _ 8 0000 _ 1000 _ 1000 (Signed: _8)

0 _A _ 6 0000 _ 1010 _ 0110 (Signed: 0 _ (_6) __6)

0 _ F _ 1 0000 _ 1111 _ 0001 (Signed: 0 _ (_1) __1)

Example 6.22

Interval from F to E

Figure 6.17 shows the simulation for the adder/subtractor. Table 6.8 shows the operations

included in the simulation in both hexadecimal and binary form. Note that the sums

are interpreted as unsigned operations and the differences are interpreted as signed operations.

Any sum or difference can be interpreted either way, but this will sometimes result in

a sign bit overflow. (e.g., the sums 8 _ 8 _ 10 and F _ 1 _ 10 both indicate an overflow

if they are interpreted as signed additions.)

➥ addSub4g.scf

0000. This transition is the result of a change from 0 to 1 on the b1 input of the adder/

subtractor.

Figure 6.18 shows the interval from F to E (the time difference between the vertical

line marking 36 ns and the arrow cursor, shown in the box labeled Interval) as 7.4 ns. This

is the delay from b1 to sum1.

Figure 6.19 shows the interval from F to 0 on the sum waveform, given as 12.6 ns.

This interval represents the time required for sum2, sum3, and sum4 to change after a

change on b1. ❘❙❚

Overflow Detection

We will examine two methods for detecting overflow in a binary adder/subtractor: one that

requires access to the sign bits of the operands and result and another that requires access

to the internal carry bits of the circuit.

Recall from Example 6.12 the condition for detecting a sign bit overflow in a sum of

two binary numbers.

If the sign bits of both operands are the same and the sign bit of the sum is different

from the operand sign bits, an overflow has occurred.

This implies that overflow is not possible if the sign bits of the operands are different

from each other. This is true because the sum of two opposite-sign numbers will always be

smaller in magnitude than the larger of the two operands.

Here are two examples:

1. (_15) _ (_7) _ (_8); _8 has a smaller magnitude than _15.

2. (_13) _ (_9) _ (_4); _4 has a smaller magnitude than _13.

No carry into the sign bit will be generated in either case.

An 8-bit parallel binary adder will add two signed binary numbers as follows:

SA A7 A6 A5 A4 A3 A2 A1 (SA _ Sign bit of A)

SB B7 B6 B5 B4 B3 B2 B1 (SB _ Sign bit of B)

S_ _7 _6 _5 _4 _3 _2 _1 (S_ _ Sign bit of sum)

From our condition for overflow detection, we can make a truth table for an overflow

variable, V, in terms of SA, SB, and S_. Let us specify that V _ 1 when there is an overflow

condition. This condition occurs when (SA _ SB) S_. Table 6.9 shows the truth table for

the overflow detector function.

N O T E

Example 6.22

Interval from F to 0

Table 6.9 Overflow Detector

Truth Table

0 0 0 0

0 1 0 0

1 0 0 0

1 1 0 1

The SOP Boolean expression for the overflow detector is:

Figure 6.20 shows a logic circuit that will detect a sign bit overflow in a parallel binary

adder. The inputs SA, SB, and S_ are the MSBs of the adder A and B inputs and _ outputs,

respectively.

Overflow Detector

❘❙❚ EXAMPLE 6.24 Combine two instances of the 4-bit counter shown in Figure 6.15 and other logic to make

an 8-bit adder/subtractor that includes a circuit to detect sign bit overflow.

of the type shown in Figure 6.20.

Example 6.24 8-Bit Adder With Overflow Detector

A second method of overflow detection generates an overflow indication by examining

the carry bits into and out of the MSB of a 2’s complement adder/subtractor.

Consider the following 8-bit 2’s complement sums. We will use our previous knowledge

of overflow to see whether overflow occurs and then compare the carry bits into and

out of the MSB.

a. 80H _ 80H

b. 7FH _ 01H

c. 7FH _ 80H

d. 7FH _ C0H

a. 80H _ 10000000 10000000

_10000000

1 00000000 (Sign bit overflow; V _ 1)

Carry into MSB _ 0

Carry out of MSB _ 1

b. 7FH _ 01111111 01111111

01H _ 00000001 _00000001

0 10000000 (Sign bit overflow; V _ 1)

Carry into MSB _ 1

Carry out of MSB _ 0

c. 7FH _ 01111111 01111111

80H _ 10000000 _10000000

0 11111111 (No sign bit overflow; V _ 0)

Carry into MSB _ 0

Carry out of MSB _ 0

d. 7FH _ 01111111 01111111

C0H _ 11000000 _11000000

1 00111111 (No sign bit overflow; V _ 0)

Carry into MSB _ 1

Carry out of MSB _ 1

The above examples suggest that a 2’s complement sum has overflowed if there is a

carry into or out of the MSB, but not both. For an 8-bit adder/subtractor, we can write the

Boolean equation for this condition as V _ C8 _ C7. More generally, for an n-bit

adder/subtractor, V _ Cn _ Cn_1.

Figure 6.22 shows a circuit that can implement the overflow detection from the carry

into and out of the MSB of an 8-bit adder.

C8

_8

C7

B8

A8

_7

C6

A7

FIGURE 6.22

❘❙❚

6.7 • BCD Adders 259

❘❙❚ SECTION 6.6B REVIEW PROBLEM

6.10 What is the permissible range of values of a sum or difference, x, in a 12-bit parallel

binary adder if it is written as:

a. A signed binary number?

b. An unsigned binary number?

(This section may be omitted without loss of continuity.)

a BCD digit.

It is sometimes convenient to have the output of an adder circuit available as a BCD number,

particularly if the result is to be displayed numerically. The problem is that most parallel

adders have binary outputs, and 6 of the 16 possible 4-bit binary sums—1010 to

1111—are not within the range of the BCD code.

BCD numbers range from 0000 to 1001, or 0 to 9 in decimal. The unsigned binary

sum of any two BCD numbers plus an input carry can range from 00000 (_ 0000 _ 0000

_ 0) to 10011 (_ 1001 _ 1001 _ 1 _ 1910).

For any sum up to 1001, the BCD and binary values are the same. Any sum greater

than 1001 must be modified, since it requires a second BCD digit. For example, the binary

value of 1910 is 100112. The BCD value of 1910 is 0001 1001BCD. (The most significant

digit of a sum of two BCD digits and a carry will never be larger than 1, since the largest

such sum is 1910.)

Table 6.10 shows the complete list of possible binary sums of two BCD digits (A and

B) and a carry (C), their decimal equivalents, and their corrected BCD values. The MSD of

the BCD sum is shown only as a carry bit, with leading zeros suppressed.

K E Y T E R M

Table 6.10 Binary Sums of Two BCD Digits

and a Carry Bit

00000 0 0 _ 0000

00001 1 0 _ 0001

00010 2 0 _ 0010

00011 3 0 _ 0011

00100 4 0 _ 0100

00101 5 0 _ 0101

00110 6 0 _ 0110

00111 7 0 _ 0111

01000 8 0 _ 1000

01001 9 0 _ 1001

01010 10 1 _ 0000

01011 11 1 _ 0001

01100 12 1 _ 0010

01101 13 1 _ 0011

01110 14 1 _ 0100

01111 15 1 _ 0101

10000 16 1 _ 0110

10001 17 1 _ 0111

10010 18 1 _ 1000

10011 19 1 _ 1001

260 C H A P T E R 6 • Digital Arithmetic and Arithmetic Circuits

Figure 6.23 shows how we can add two BCD digits and get a corrected output. The

code converter to translate it into BCD.

The Binary-to-BCD code converter operates on the binary inputs as follows:

1. A carry output is generated if the binary sum is in the range 01010 _ sum _ 10011

(BCD equivalent: 1 0000 _ sum _ 1 1001).

2. If the binary sum is less than 01001, the output is the same as the input.

3. If the sum is in the range 01010 _ sum _ 10011, the four LSBs of the input must be

corrected to a BCD value. This can be done by adding 0110 to the four LSBs of the input

and discarding any resulting carry. We add 01102 (610) because we must account for

six unused codes.

Let’s look at how each of these requirements can be implemented by a digital circuit.

Carry Output

The carry output will be automatically 0 for any uncorrected sum from 00000 to 01001 and

automatically 1 for any sum from 10000 to 10011. Thus, if the binary adder’s carry output,

which we will call C4_, is 1, the BCD adder’s carry output, C4, will also be 1.

Any sum falling between these ranges, that is, between 01010 and 01111, must have

its MSB modified. This modifying condition is a function, designated C4_, of the binary

adder’s sum outputs when its carry output is 0. This function can be simplified by a Karnaugh

map, as shown in Figure 6.24, resulting in the following Boolean expression.

C4_ _ _4_ _3_ _ _4_ _2_

The BCD carry output C4 is given by:

_ C4_ _ _4_ _3_ _ _4_ _2_

The BCD carry circuit is shown in Figure 6.25.

4-bit Adder

BCD Adder (11⁄2 Digit Output)

Sum Correction

The four LSBs of the binary adder output need to be corrected if the sum is 01010 or

greater and need not be corrected if the binary sum is 01001 or less. This condition is indicated

by the BCD carry. Let us designate the binary sum outputs as _4_ _3_ _2_ _1_ and the

BCD sum outputs as _4 _3 _2 _1.

If C4 _ 0, _4 _3 _2 _1 _ _4_ _3_ _2_ _1_ _ 0000;

If C4 _ 1, _4 _3 _2 _1 _ _4_ _3_ _2_ _1_ _ 0110.

Figure 6.26 shows a BCD adder, complete with a binary adder, BCD carry, and

sum correction. A second parallel adder is used for sum correction. The B inputs are the

uncorrected binary sum inputs. The A inputs are either 0000 or 0110, depending on the

value of the BCD carry.

Carry as a Function of Sum

Bits When C4_ _ 0

C4

_3

_4

C4

BCD Carry Circuit

C4

Code

_4 _3 _2 _1

C4 C0 C0

A4 A3 A2 A1 B4 B3 B2 B1

_4 _3 _2 _1

_4 _3 _2 _1

C4 C0

A4 A3 A2 A1 B4 B3 B2 B1

4-bit Adder

4-bit Adder

FIGURE 6.26

BCD Adder

❘❙❚ EXAMPLE 6.25 Write a VHDL file for a BCD adder, using two parallel adder components, such as in the

logic diagram in Figure 6.26.

SOLUTION

—— bcd_add.vhd

—— BCD adder, using 2 instances of the component add4par

ENTITY bcd_add IS

PORT (

c0 : IN BIT;

c4 : OUT BIT;

sum : OUT BIT_VECTOR (4 downto 1));

END bcd_add;

ARCHITECTURE adder OF bcd add IS

—— Component declaration

COMPONENT add4par

PORT (

a, b : IN BIT_VECTOR (4 downto 1);

c4 : OUT BIT;

sum : OUT BIT_VECTOR (4 downto 1));

END COMPONENT;

SIGNAL c4_bin : BIT;

SIGNAL sum_bin : BIT_VECTOR (4 downto 1);

SIGNAL a_bcd : BIT_VECTOR (4 downto 1);

SIGNAL b_bcd : BIT_VECTOR (4 downto 1);

SIGNAL c0_bcd: BIT;

BEGIN

—— Instantiate 4-bit adder (binary sum)

PORT MAP ( c0 __ c0,

a __ a,

b __ b,

sum __ sum_bin);

——Instantiate 4-bit adder (binary-BCD converter)

converter: add4par

PORT MAP ( c0 __ c0_bcd,

a __ a_bcd,

b __ b_bcd,

sum __ sum);

——Connect components

c0_bcd __ ´0´;

b_bcd __ sum_bin;

a_bcd(4) __ ´0´;

a_bcd(3) __ c4 bin or (sum_bin(4) and sum_bin(3))

or (sum_bin(4) and sum_bin(2));

a_bcd(2) __ c4 bin or (sum_bin(4) and sum_bin(3))

or (sum_bin(4) and sum_bin(2));

a_bcd(1) __ ´0´;

c4 __ c4_bin or (sum_bin(4) and sum_bin(3))

or (sum_bin(4) and sum_bin(2));

END adder;

❘❙❚

➥ bcd_add.vhd

Multiple-Digit BCD Adders

Several BCD adders can be cascaded to add multidigit BCD numbers. Figure 6.27 shows a

4_

1

_-digit BCD adder. The carry output of the most significant digit is considered to be a

half-digit since it can only be 0 or 1. The output range of the 4_

1

2

to 19999.

41⁄2-Digit BCD Adder

BCD adders are cascaded by connecting the code converter carry output of one stage to

the binary adder carry input of the next most significant stage. Each BCD output digit represents

a decade, designated as the units, tens, hundreds, thousands, and ten thousands digits.

❘❙❚ SECTION 6.7 REVIEW PROBLEM

6.11 What is the maximum BCD sum of two 3-digit numbers with no carry input? How

many digits are required to display this result on a numerical output?

of a CPLD.

term for general use within a CPLD.

The VHDL adder circuits implemented in Section 6.6 were all defined using a ripple carry

format. Is it necessary to design a fast carry circuit when compiling one of these adder designs

in MAX_PLUS II? Probably not.

Recall that the design strategy behind the fast carry circuit was to flatten the gate network,

that is, to replace a long network (many gates for the carry bit to pass through) with

a wide one (fewer levels of gating). Also recall that any combinational logic function can

be implemented as a sum-of-products (SOP) network, which inherently is a very flat network

form.

The internal circuit of a MAX7000S CPLD is a programmable SOP network. In order

to program such a device, the MAX_PLUS II compiler must analyze the design entity,

break it into product terms and reassemble it as an SOP network. (This is an oversimplification.

Sometimes SOP outputs are fed back into the circuit to be reused by other parts of

the circuit, thus lengthening the logic path.)

MAX_PLUS II allows us to choose a style of logic synthesis that balances circuit

speed and chip area occupied by the programmed circuit. The styles can be user-defined or

we can use one of three predefined synthesis styles called Normal, Fast, and WYSIWYG

(What You See Is What You Get). Each one of these styles is optimized for speed, area, or

a compromise. The Normal and Fast styles disassemble the design entity and reassemble it

after optimizing the logic according to the style rules. The WYSIWYG style allows us

(rather than the compiler) to largely define the logic synthesis without altering our design

format by very much.

To choose a synthesis style, select Global Project Logic Synthesis, from the

MAX_PLUS II Assign menu, as shown in Figure 6.28. A drop-down menu in the resulting

dialog box, shown in Figure 6.29, allows us to select one of the three Altera-defined

synthesis styles.

Assigning a Synthesis Style (Assign Menu)

Assigning a Synthesis Style

To use the WYSIWYG style, you must also check the box that says Multi-Level

Synthesis for MAX 5000/7000 Devices.

We can calculate the circuit delays for an adder by running the compiled design

through the MAX_PLUS II Timing Analyzer. Figure 6.30 shows an example of such an

analysis for the parallel adder add4par.vhd with a Normal synthesis style and an

EPM7128SLC84-7 as the selected device.

N O T E

The values in the Destination columns are the delays from logic level changes on the

inputs specified by the Source rows. For example, a change on input a1 reaches the output

sum1 in 7.5 ns and sum4 in 12.5 ns. Most of the entries in the c4 column have two values

(7.5 ns and 11.5 ns), indicating that the delay to output carry is the same from all input bits

(i.e., a fast carry). The actual delay to c4 will depend on the logic level change that takes

place on the source line and thus which logic path is taken. The delay time of 7.5 ns is

about the lowest value possible in the EPM7128SLC84-7 device. (The “_7” tells us that

the chip has a speed grade of minus 7, meaning an internal delay of about 7 ns.)

Figure 6.31 shows the timing analysis of the same adder with a WYSIWYG synthesis

style. (The synthesis style is the only design change.) In this analysis, the delay from an input

bit to c4 varies from 7.5 ns (from a4 or b4) to as much as 16.5 ns (for a1, b1, a2, or b2).

Since the lower-order bits result in a longer delay to the carry bit, we can infer that the

compiler has not synthesized a fast carry circuit.

FIGURE 6.30

Delay matrix for a 4-bit adder (Normal Synthesis)

Delay matrix for a 4-bit adder

(WYSIWYG Synthesis)

266 C H A P T E R 6 • Digital Arithmetic and Arithmetic Circuits

We can examine the actual equations from the MAX_PLUS II report file to confirm

our assessment. The synthesized equations for c4 are given below.

WYSIWYG Synthesis:

—— Node name is ´c4´ _ ´full_add:adder4:12´

—— Equation name is ´c4´, type is output

c4 _ LCELL( _EQ001 $ GND);

_EQ001 _ a3 & b3 & b4

# b4 & _LC113 & _LC114

# a3 & a4 & b3

# a4 & _LC113 & _LC114

# a4 & b4;

—— Node name is ´full_add:adder2:12´

—— Equation name is ´_LC113´, type is buried

_LC113 _ LCELL( _EQ008 $ GND);

_EQ008 _ a2 & b2

# a2 & c0 & _X007

# b2 & c0 & _X007

# a1 & b1 & _X002;

_X007 _ EXP (!a1 & !b1);

_X002 _ EXP (!a2 & !b2);

—— Node name is ´full_add:adder3:9´

—— Equation name is ´_LC114´, type is buried

_LC114 _ LCELL( b3 $ a3);

Normal synthesis:

—— Node name is ´c4´

—— Equation name is ´c4´, location is LC123, type is output.

c4 _ LCELL ( EQ001 $ VCC);

_EQ001 _ !a1 & _X001 & _X002 & _X003 & _X004

# !b1 & !c0 & _X001 & _X003 & _X004

# !a2 & !b2 & _X003 & _X004

# !a3 & !b3 & _X004

# !a4 & !b4;

_X001 _ EXP ( a2 & b2);

_X002 _ EXP ( b1 & c0);

_X003 _ EXP ( a3 & b3);

_X004 _ EXP ( a4 & b4);

The function EXP(signal) is for a MAX_PLUS II primitive called an expander