Designing a simple ALU

Question

I need to design an ALU with two 8-bit inputs A and B and control inputs x, y, and z that supports the following operations:

x  y  z  |  operation

0  0  0  |  S = A-B
0  0  1  |  S = A+B
0  1  0  |  S = A*8
0  1  1  |  S = A/8
1  0  0  | S = A NAND B (bitwise)
1  0  1  | S = A XOR B (bitwise)
1  1  0  | s = reverse the bits of A
1  1  1  | S = NOT A (bitwise)

This is supposed to be done with an 8-bit adder and an arithmetic-logic extender. Reading through my textbook, I see that the purpose of an AL-extender is to alter the input bits so that an adder, rather than a lot of extra components, can be used to do everything (or at least that's what I understand from it). For example, the AL-extender could put the bits in two's complement so that the adder does a subtraction. Likewise, for the bitwise logical operations, the bits could be altered appropriately and one of the adder inputs could just be zero so that the result comes through properly.

But what exactly do I do about multiplication? My book is very vague, so I'm not sure if an AL-extender would require me to do something clever to make the adder do the work (just add 8 times in my case? ...ha ha), or if I can just throw a multiplier in there. I'll have to read up on division, but I bet it's similar to multiplication.

Well, anyway, the bottom line is still, what is an AL-extender "allowed" to be/able to have in it? Is its only purpose to alter input so that it can be fed to an adder?

*EDIT: Well, it is multiplication/division by 8, so this can be easily performed with shifting left or right by 3. Would I still have a real/proper AL-extender if I added some shifters in there? (Maybe I'm overthinking this as a complete beginner...)

Answer 1

The simplest approach would be to decode the x y z inputs into eight lines. Then from these, you implement logic which drives chip select lines to enable the appropriate unit which handles the inputs, as well as any transformations that are needed so that the unit performs the correct operation.

I don't think you can use an adder for your logic operations because the adder carries (unless it has some input which disables the behavior of carry propagation). But you can have a single unit to do all the logic.

Maybe there is a reason why they call these ALU's, with a separate A and L. :)

Multiplication by 8 just means driving zeros on the lowest three input lines, ignoring the upper three lines, and mapping line 0 to line 3, 1 to 4, and so on. It's like a railway switch.

Answer 2

(Cheat)
The simplest yet most powerful solution is to use a Flash memory as a lookup table for the results. 8-bit A input + 8-bit B input + 3 bits operation code is 19 bits. Pick a 512 k \$\times\$ 16 bit Flash (about $2), use the 19 input lines as address, and program it with the results for each input combination. This way you can have any operation you like. You want sin(A)? Just add a 256-word sine lookup table, you can even have a 16-bit precise result. You're not limited to multiplying by 8; you can multiply A by B. Like wise, you can divide A by B, and get an 8-bit quotient and an 8-bit remainder. For the multiplication and division you'll use all bits in a 64 kword block, but for instance the bit reversal makes less efficient use of it: it doesn't depend on the value of B, so you'll have 256 identical values for each A input, and the high order byte wouldn't even be used. So whereas you only need 256 \$\times\$ 8 = 2048 bits for the bit reversal you would use 65536 \$\times\$ 16 = 1048576 bits; that's not very efficient. You could call this a serious drawback of the Flash solution, but I would like to see you implement an 8 \$\times\$ 8 multiplier using basic logic gates for $2.

OK, maybe you don't want that; logic gates are much more challenging. Like Kaz says start with a 3-to-8 decoder to have a unique signal for each opcode. You can make this with basic gates, but I would suggest to use a 74HC238 to start with. When the ALU works you can still replace the HC238 by a collection of gates.

What you don't want for the multiplier is a shift register which shifts left 3 times. That's a registered function which needs a clock, instead of a combinatory function which produces the result immediately. (Note that the Flash also produces any result in nanoseconds, though slower than with combinatory logic.) Have a path from A0 to Y3, A1 to Y4, etc, which you enable with the "010" decoded opcode. Likewise, Y3 will be connected to A6 if the "011" signal is active (division), and to A4 when the opcoe is "110" (bit reversal). That means a lot of multiplexing.

To get back to the Flash, you can also make a combination of combinatory logic for simple operations, like NAND, NOR, shift left, shift right\$^{(*)}\$, and only use the Flash for the multiplication and division. You could use a smaller Flash (128 kword instead of 512 kword), or add more advanced functions, like the sine I gave as an example (maybe not the best, but I'm sure you can think of something).

---

\$^{(*)}\$ How come you have a multiply by 8, but not the more basic shift left? Shift left/right, rotate left/right (both through carry and not) are must haves for any ALU, and you can divide by 8 using 3 shift rights, while you can't divide by 2. The bit reversal is a typical DSP function, but you don't want to build a DSP to start with, do you? I would change the functions to

x  y  z  |  operation

0  0  0  |  S = A - B
0  0  1  |  S = A + B
0  1  0  |  S = shift left A by 1 bit
0  1  1  |  S = shift right A by 1 bit
1  0  0  |  S = A NAND B (bitwise)
1  0  1  |  S = A XOR B (bitwise)
1  1  0  |  S = rotate left A
1  1  1  |  S = NOT A (bitwise)

Answer 3

I got stuck on the same problem from the same book. Luckily I stumbled upon this thread which gave me an idea what to do. Kaz has a very good point about driving zeros and mapping lines. The ALU extender in this book is designed of n (n representing the number of bits on which to operate) identical but sepparate combinational components and one different component for carry in. These components have five inputs and two outputs. The five inputs are: 'X', 'Y', 'Z' (to select operation) and 'a', 'b' (individual bits of A and B with same significance). I guess the idea here is to divide the problem into smaller chunks in order to have a reasonable size truth table. That is 5 inputs vs 8 + 8 + 3 = 19 inputs if the extender would accept all the bits from A and B plus control inputs. Now, if the extender was composed in such a way (19 inputs) I think the logic for multiplication could be implemented in that single component, but writing a truth table for this would be out of the question. So anyway, my solution is to use muxes after each component that handles a and b individual bits assuming that the component is already designed such a way that an input XYZ = 010 passes 'a' bit unchanged and filters out 'b', that is 'b' = 0. The mux should have two inputs, one from the above component, and one from the component three places to the right. Three rightmost muxes should have zeros as a second input. A simple combinational logic with an AND gate and two inverters can set the muxes when XYZ = 010. This same method can be used for division too but it needs muxes with three inputs and a slightly different combinational circuit to drive them.