## Digital Arithmetic

Sometimes it is convenenient to perform hard-wired digital arithmetic. In the simplest case, we have several inputs that produce one or more outputs constantly reflecting the input values. When an input changes, the output changes rapidly, after a propagation delay that seldom exceeds a few hundred nanoseconds, provided mechanical component are not included. Mechanical components, such as relays, may introduce propagation delays of milliseconds, and sometimes delays are intentional. This is classic combinational logic.

More complicated are circuits with a clock pulse that distinguishes successive states in time. The outputs may depend on past inputs, which requires a storage mechanism, usually a flip-flop or a stick relay. Despite its name, the clock pulse does not have to recur at regular intervals (though this is often convenient). It may be manually introduced by a debounced pushbutton, for example. These are sequential circuits.

In the experiments for this page, we shall use 4-bit numbers ("nibbles") to ease the wiring problems, and to make the illustrations easy to grasp. These numbers are too limited for most practical uses, but all the circuits we use can be cascaded to handle any number of bits. Also, we will represent a 1 by a high level, and a 0 by a low level, the usual positive logic. Everything works as well for negative logic, mutatis mutandis. When writing a number down, the high-order or most significant bit will be on the left, the low-order or least significant bit on the right. When cascading circuits, we usually start with the low order nibble and proceed to higher orders, left to right. Bits here are numbered 1-4, with 1 the least significant bit, and 4 the most significant, instead of starting with 0, the usual computer convention.

Processors are what we use to do most of our arithmetic, so their capabilities form a guide to what we should consider. In arithmetic we include all manipulations of binary numbers, logical and bitwise operations as well. Every processor performs the complement or NOT operation on a single number, and the AND, OR and XOR operations on two numbers. There is the capacity of shifting the bits of a number to the right (dividing by 2) or to the left (multiplying by two). Processors can do the four fundamental operations of arithmetic: sum, difference, product and quotient. We shall see that only addition is essential, and that all other arithmetic operations can be done with it and the help of certain logic functions. Arithmetic operations imply an order of significance of the bits, which logical operations do not. Since numbers in this case can be ordered in magnitude, two numbers can be compared to determine if they are equal, or one is greater or lesser than the other. These operations are all those that processors can do that are of interest here (excluding such things as parity).

All of these operations can be performed with the help of integrated circuits in a hard-wired circuit. The NOT operation is performed by the 74LS04 inverter, the AND by the 74LS08, the OR by the 74LS02, and the XOR by the 74LS86. The latter three come four to a package, just the right number to handle a nibble. Shifting is done by the bit connections. A shift-right is performed by connecting A4 with B3, A3 with B2, A2 with B1, where A and B are an output and an input group. What we apply to B4 can be chosen for what is needed, 0 for a logical shift, or A4 for an arithmetic shift, in the usual nomenclature. This is shifting in a static or combinatorial circuit. In a sequential circuit, a shift register may be required, clocked by the clock pulse. The 74LS194B is a 4-bit shift register with parallel input and output, that can shift either right or left.

For testing these circuits, I have found very convenient a pair of hex thumbwheel switches that give two nibbles, with the digits clearly displayed. The outputs are buffered for general convenience. I also have eight buffered LED's that show logic levels. Changing values by moving wires is pestilential. The Karnaugh maps for what are known as a half adder and a full adder are shown at the right. These are just another way of expressing the truth table, but they show how the circuits can be built. A half adder needs only a 74LS86 XOR gate and a 74LS08 AND gate to produce the sum, Σ, and the carry out. The carry out goes to the next highest bit, so a definite order of bits is implied. The half adder has no carry input, which is why it is so-called. There must be another addition to include the carry input. This is a more complicated circuit, with two XOR gates to give Σ, and a pair each of AND and OR gates to create the carry out. Note that there are three inputs and two outputs to a full adder. It is not necessary to make adders from discrete gates. Four cascaded full adders are in a 74LS83A adder, whose pinout is shown at the left. Note carefully the midships power connections, and that +5 is on the left. This inconvenience is relieved in the 74LS283, which is the same but with corner power pins (the pinout is different, of course). The inputs are A and B, and the outputs are Σ. There is a carry in to the least-significant bit, and a carry out from the most significant bit. It is obvious how to cascade these packages to handle any number of bits. You can, of course, try out the adder, but subtraction is more exciting. The circuit is shown at the right. The subtrahend is complemented and added to the minuend with carry. The output appears in 2's-complement notation. The 2's complement, you remember, is the NOT plus 1. When added to the original number, the sum is all zeros and a carry out. One can see this explicitly here, which clarifies the concepts considerably. The subtractor is exactly the same hardware as the adder!

With four bits, the signed integers from -8 to +7 can be represented. A positive number has its highest bit 0, so its range is 0000 (0) to 0111 (7). A negative number has its highest bit 1, so its range is 1000 (-8) to 1111 (-1). This interpretation should be carefully distinguished from the unsigned integer representation, with a range 0000 (0) to 1111 (F). These representations are simultaneous; it is only the interpretation that differs. For example, if we have the unsigned integer 1111 and add 1 to it, we get 0000 and a carry to the fifth position, which is 16. On the other hand, if we consider it as -1 instead, we are not surprised by the zero. Use the subtractor to subtract integers from 0, which will yield the 2's complement of the integer. It is interesting to see these things on the hardware, and not simply on a piece of paper.

Also try a variety of subtractions, noting the result and the state of the carry out. The basic relation we are using is that x + /x = -1 (all 1's), so that /x = NOT x is the 1's complement of x. Then, x + (/x + 1) = 0 (and a carry), so that /x + 1 is the 2's complement, and represents the negative of x. This is the reason we do not have to build subtractors explicitly--adders will do the job. In fact, the 8048 microcomputer had no subtraction instruction at all, just add and complement, and the ability to control the carry flag, which was sufficient. For a long time, microprocessors had no multiply or divide instructions, since this was easy enough to do with a subroutine that involved shifting and adding (or subtracting). It is even possible to take square roots, and many other things, just with the basic adder. Both signed and unsigned integers can be compared to tell if one is greater than, equal to, or less than the other. This comparison is different in the two cases. For example, with signed integers, 1111 (-1) is less than 0000, while for unsigned integers, 1111 (16) is greater than 0000. The 74LS85, whose pinout is shown at the left, compares two unsigned integers. It has three pins for the input of A lt B, A=B and A gt B status (gt, lt to keep the browser happy), as decided by the lower-order nibbles, includes the comparison for the present nibble, and outputs the status of A lt B, A=B, and A gt B for use, or for feeding to the next comparator. The status inputs of the least-significant nibble are A lt B = A gt B = L (low value, or 0), and A=B = H. This is reasonable, since before any bits are considered, the two values are equal. It should be clear how the comparators are cascaded to compare numbers of any size.

The comparison of signed integers is somewhat inconvenient. Comparison for equality is, of course, the same. If the sign bit of both numbers is 0, then the comparison is the same as for unsigned integers. If the sign bit of both numbers is 1, then gt and lt are reversed. If the sign bits are different, then the number with the 1 sign bit is less than the one with the 0 sign bit.

Connect LED's to the A gt B, A=B and A lt B outputs of an LS85, and see what happens when you apply various numbers to the inputs. An active output is high, so the LED will go out in this case, unless you have used an inverter to buffer it.

The 74LS181 arithmetic-logical unit (ALU) is an interesting circuit. It is furnished in a 24-pin 0.300"-wide DIP because of all the pin connections it requires. It accepts two 4-bit inputs, and provides a 4-bit output. These numbers can be either in positive logic (H = 1) or negative logic (L = 1). It seems that the chip is generally used with negative logic, and the description here is on that basis. There are four function select inputs S0, S1, S2 and S3, that choose any one of 16 different functions, and a mode control pin M that selects logic operations when high, and arithmetic operations when low. For logic operations, carries are ignored and have no effect on the outputs. There are carry inputs and outputs, that are inverted with respect to the number bits. That is, when using negative logic, the carry input and output are positive logic levels. There is also an A=B output that is low when the output is all zeros. There is an input and an output for cascading LS181 chips for larger numbers, but I shall not discuss them here. The LS181 is most applicable where it will do different things at different times in a sequential, or processor-controlled, circuit. If you have just one operation to perform, it is more economical to do it other ways.

To learn what the LS181 can do, it is useful and fun to exercise all its functions, both logical and arithmetic. I supplied the operands A and B from hex thumbwheel switches, while observing the outputs F, carry and A=B using LED's. DIP switches made changing the function select inputs easy. Carry in and M were supplied by wires connected to +5 and GND as required. The function table supplied with the data sheet was not always easy to interpret, and was wrong in at least one case, so this exercise is not wasted time if you intend to use the LS181. The logic functions AND, NAND, OR, NOR, XOR, XNOR and NOT are available, as well as the arithmetic functions PLUS, MINUS, DOUBLE and 2's Complement. In many cases, there is more than one way to do the same thing, and some of the functions do not seem to be very useful.

For example, Functions 3 and 12 give F = 1111 and F = 0000, respectively, no matter what the inputs A and B are. The 2's complement of B is found using Function 7, with A=0, M=0 and Cin=1. For any arithmetic operation, carry adds one to the the output in any case. For doubling a number, it can be added to itself with Function 9, or Function 4 with B=1111, or Function 8 with B=0000. This is equivalent to a left shift by one place. In the data sheets, + means logical OR, while addition is denoted by "plus."