I just finished the document, and although it's in somewhat of a rough state, I thought I might pass it along to the folks at 6502.org since that's basically where everyone goes for 6502 information these days. However, it seems that the e-mail address on 6502.org isn't working right now, and I really have no other place to post this (other than my Tripod website, which is out of storage space), so I figured I might as well just dump this here for now so it doesn't disappear forever. Without further ado, then, I present to you...
Creating a 6502 ALU using 7400-series logic chips
The ALU (arithmetic-logic unit) is often thought of as the heart of a CPU. Because the ALU only performs arithmetic and logic operations--as its name indeed implies--this viewpoint is arguably one-sided, but there is no doubt that the ALU is a key part of the CPU, and perhaps the most complex single piece of a complete microprocessor. Although the 6502 certainly has considerable internal structure that is not part of the ALU, the ALU is probably the single most "black-boxed" component of the CPU, typically reduced to a single block in a block diagram. This document purports to describe how a fully-functional ALU that functions identically to that inside a 6502 can be built out of 7400-series logic chips.
Because so much of from-the-ground-up CPU design focuses on the design of the ALU, first-time CPU builders may be justified in using a pre-built ALU chip instead of creating their own ALU. This black-boxes a segment whcih might otherwise dominate the CPU design process, allowing designers (and students) to focus on how the other parts of the CPU work together before delving into how to make binary arithmetic work. In terms of pre-packaged ALUs, the 74181 is one of the most popular chips, although since it is only a 4-bit ALU, you would need to use two of them to work with the 6502's 8-bit architecture. For CPU builders who are ready to build their own ALU, this document exists to inform that task.
The 6502 can broadly be broken down into four sections: ALU, registers, timing circuitry, and microcode. It is hoped that this document can serve as a foundation for later work which would build a complete and fully-functional 6502 CPU out of 7400-series logic chips, although it is anticipated that a single exception would be made for an EEPROM chip (or bank of such chips) to serve as the CPU's microcode.
Because of the significantly added complexity required in implementing BCD support in this ALU, and the fact that BCD has been rarely used in actual 6502 applications, this document does not implement BCD in the ALU described. All other 6502 ALU functions are implemented, and the resultant ALU described should function equivalently to a real-world 6502 ALU.
Although the 6502's ALU is used in 15 of the 6502's opcodes, the ALU itself has only five functions: SUM (add), AND (bitwise AND), OR (bitwise OR), EOR (bitwise Exclusive OR), and SR (shift right). Through these five functions of the ALU, the 6502 accomplishes other functions involving arithmetic and logic.
The 6502 ALU's complete list of inputs is as follows:
8-bit input register A
8-bit input register B
1-bit SUM function input (used for both addition and subtraction)
1-bit AND function input
1-bit OR function input
1-bit EOR (Exclusive OR) function input
1-bit SR function input (SR, in this case, stands for "shift right")
1-bit Carry input
1-bit "Decimal mode" input
The "Decimal mode" input tells the ALU to perform BCD (binary-coded decimal) operations instead of regular binary math operations. As this implementation of a 6502 ALU does not currently implement BCD, it will ignore this input.
The Carry input is simply the usual mathematical carry bit used in ordinary binary addition.
The 6502 ALU's complete list of outputs is as follows:
8-bit ALU output register (also known as the "Adder Hold Register," or ADD)
1-bit overflow output
1-bit carry output
1-bit half-carry output
The ALU's overflow and carry outputs are only used to set the appropriate bits in the 6502's status register; they have no other function.
The ALU's "half-carry" output is only used in decimal mode, to correct the result of an addition operation into BCD. It has no other purpose. As this implementation of a 6502 ALU does not currently implement BCD, we will not implement a half-carry output.
Structure surrounding the ALU, and the ALU's place within the 6502
Broadly, the ALU simply takes in two numbers which are received through the two input registers, and outputs the result of an operation into its output register. The ALU has five single-wire function inputs which tell the ALU which operation to perform: SUMS, ANDS, EORS, ORS, and SRS. Only one of these function inputs should ever be active at a time! All five of these function inputs are controlled by the 6502's control logic (microcode or control matrix), so having more than one of these functions active at once indicates a failure of the CPU's control logic. When any of these 5 inputs are enabled, the output of the ALU is enabled, and it will send the result of the selected operation to the ADD.
The ALU is directly connected to three registers: Two input registers and one output register. The input registers are simply called A and B, sometimes abbreviated AI and BI for "A Input register" and "B Input register." The ALU's primary data outputs lead directly into the Adder Hold Register (ADD), which stores the result of any ALU operation.
Of the 5 operations which the ALU can perform, 3 of them--to wit, OR, AND, and EOR--are part of the classic series of logic-gate functions, and as such can easily be reproduced using off-the-shelf 7400-series chips, such as the 7432 or 744078 for OR functionality, the 7408 or 7409 for AND functionality, and the 7486, 74136, or 74386 for EOR functionality. Similarly, binary adder circuits are copious, and can be replicated using the 7480 or 7483. The 7400 series also has its own shift register chips, such as the 7491, 74164, 74198, and 744094. With so many parts available to package these functions, ALU design can be as modular or as granular as the designer wishes.
Ultimately, the ALU will be divided into 5 main sections, each of which fulfills ones of the ALU's 5 possible functions. Each section will be turn "on" at all times, meaning that every possible function's result is "available" as having already been calculated by the ALU and controlling the output is simply a matter of enabling the output for one of the ALU's 5 internal output buffers.
Background details on how the original 6502 performs ALU operations
Because part of the intent of this project is the recreation of history, it is of some interest to understand how the original 6502 CPU chip performs ALU operations, even though we cannot replicate these functionalities exactly without creating custom circuitry; these transistor-level details are not relevant to creating projects with 7400-series chips, but I have taken a moment to devote a few side notes below to how the 6502 performs various ALU functions as items of interest to anyone studying the original 6502 transistor schematics.
The ALU performs subtraction using the typical binary-math trick which allows an adder circuit to function as a subtractor circuit. The steps involved are as follows:
1. Invert the subtrahend (the number being subtracted; not the number being subtracted from, which is the minuend), meaning replace all the subtrahend's 1s with 0s, and all its 0s with 1s. The ALU performs this step with a pair of 7404 inverter chips. The result of this operation is known as the "one's complement" of the subtrahend.
2. Add 1 to the result of step 1. The result of this operation is known as the "two's complement" of the subtrahend. (The 6502 simply adds 1 by enabling its carry input for this addition operation.)
3. Add the result of step 2 to the minuend. The result is the subtraction difference.
The result of step 3 may result in a bit carry. If so, the carry bit is ignored; it is not part of the solution.
A quick check of the ALU's 5 control inputs reveals that the ALU has only an input for "shift right." Yet the 6502 can shift left as well; how is this done without an appropriate input for this purpose?
As it happens, any digital number can be shifted one place to the left by simply adding it to itself. Thus, the ALU's equivalent "shift left" operation is performed by loading the same number into both ALU inputs and then adding them to each other.
The original 6502 accomplishes shifting-right in a somewhat roundabout way: First, it loads the item to be shifted into both input registers A and B. Because an internal NAND of these two registers is always internally available, it then inverts the result of the NAND (to produce an AND result which is the same as the contents of both A and B), then shifts the result for each bit down to the next-lower bit.
To keep things simple, we will shift bits right by simply loading a single ALU input register (we'll use register A for the sake of simplicity) and then shift the bits by "skewing" the results to an output buffer.
The original 6502 does not actually contain OR gates; it produces OR operations by using NOR gates and then inverting the results. This is easy to do in silicon since the NOR gate only requires one depletion-mode MOSFET and two enhancement-mode MOSFETs, and the inverter only requires one of each mode.
For our purposes, since we are using 74-series logic, we will use regular OR gates, as supplied by the 7432 chip.
The original 6502 also performs ANDing using a NAND gate and an inverter. The NAND gate also requires only one depletion-mode MOSFET and two enhancement-mode MOSFETs, although the two enhancement-mode MOSFETs are in a series configuration instead of the parallel configuration used by the NOR gate.
We will be using AND gates supplied by the 7408 chip.
The original 6502 does not use true XOR gates. Instead, since it already has NOR and NAND results available from the previous operations, the NAND results are simply inverted to produce AND results, and then the AND and the NOR results are run through one more NOR gate to produce XOR output.
We will be using XOR gates supplied by the 7486 chip.
The sum bit in a full adder is simply: (A XOR B) XOR CarryIn.
Since XOR results of the ALU inputs are already available from the previous operation, the original 6502 produces a sum bit by simply XORing the XOR result with CarryIn.
These details regarding the handling of the sum bits and the carry bits will all be handled for us by the 74283 full-adder chip. The 74283 is functionally identical to the older 7483 chip, except that the 74283 is recommended for newer designs since it has standard corner power pins, as opposed to the 7483 which has its power pins near the center of its pin rows.
Descriptions of the ALU substructures
As the ALU is a relatively complex portion of any CPU, we will divide our ALU into the following substructures, which will be discussed separately:
The adder substructure
The OR substructure
The AND substructure
The EOR (XOR) substructure
The shift-right substructure
The CarryOut substructure
The overflow substructure
The first five structures are the "core" of the ALU, which define the ALU's five basic logic functions: Adding, ORing, ANDing, EORing (XORing), and shifting right. All these sections receive their input from registers A and B, and they all output to the adder hold register.
The CarryOut substructure is what determines whether the ALU's single-wire CarryOut output signal should be on.
The overflow substructure is what determines whether the ALU's single-wire overflow output signal should be on.
The adder substructure
The adder substructure consists of three chips: Two 74283 full-adder chips, and a 74244 buffer to gate the output.
The two 74283 adder chips get their inputs from registers A and B. Their outputs go to the inputs of the 74244 buffer chip. The output of the buffer, in turn, leads to the ALU output register. The buffer's gates are controlled by the SUMS control signal.
The least significant adder chip's "Carry in" input is connected to the ALU's "Carry in" input.
The least significant adder chip's "Carry out" output is connected to the most significant adder chip's "Carry in" input.
The most significant adder chip's "Carry out" output is connected to the ALU's "Carry out" output.
The OR substructure
The OR substructure consists of three chips: Two 7432 OR chips, and a 74244 buffer to gate the output.
The two 7432 OR chips get their inputs from registers A and B. Their outputs go to the inputs of the 74244 buffer chip. The output of the buffer, in turn, leads to the ALU output register. The buffer's gates are controlled by the ORS control signal.
The AND substructure
The AND substructure consists of three chips: Two 7408 AND chips, and a 74244 buffer to gate the output.
The two 7408 AND chips get their inputs from registers A and B. Their outputs go to the inputs of the 74244 buffer chip. The output of the buffer, in turn, leads to the ALU output register. The buffer's gates are controlled by the ANDS control signal.
The EOR (XOR) substructure
The EOR (exclusive OR, or XOR) substructure consists of three chips: Two 7486 XOR chips, and a 74244 buffer to gate the output.
The two 7486 XOR chips get their inputs from registers A and B. Their outputs go to the inputs of the 74244 buffer chip. The output of the buffer, in turn, leads to the ALU output register. The buffer's gates are controlled by the EORS control signal.
The shift-right substructure
The shift-right substructure consists of only one chip: A 74244 buffer to gate the output.
This buffer chip takes the output of register A, but the connections between the two chips are skewed: Register A's bit 7 goes to the buffer chip's bit 6. Likewise, register A's bit 6 goes to the buffer chip's bit 5, and so on.
The buffer's input for bit 7 is read from the ALU's CarryIn input.
Register A's bit 0 does not go to the buffer chip, but rather to the CarryOut substructure.
The buffer's gates are controlled by the SRS control signal.
The CarryOut substructure
The ALU's CarryOut substructure consists of only one chip: A 74244 buffer.
The ALU's CarryOut output can be controlled by both the adder substructure and the shift-right substructure. Since this output can be driven by more than one pin, it is necessary to use the high-impedance outputs which the 74244 provides us.
The buffer chip receives two inputs: One from the adder substructure's carry-out signal, and one from register A's bit 0 (which is shifted to CarryOut during a shift-right operation).
The buffer's gates are controlled by the SUMS and the SRS control signals.
The overflow substructure
The 6502's relatively rarely-used overflow flag can be set by the ALU. This flag is used to indicate when signed addition or subtraction has exceeded its bounds, i.e. when a "sign change" occurs. The ALU turns on the overflow bit when either of the following logic conditions is true:
1. The most significant bits of registers A and B are both 0, and the most significant bit of the ALU's output is 1.
2. The most significant bits of registers A and B are both 1, and the most significant bit of the ALU's output is 0.
In both of these cases, the "sign bit" of the two inputs was the same, but the sign bit changed on the output. This is considered an overflow.
The overflow condition can thus be logically stated as follows:
((NOT A7 AND NOT B7) AND ADD7) OR (A7 AND B7 AND NOT ADD7)
(Where ADD7 refers to the high bit of the ALU output.)
Because this is three NOTs, four ANDs, and an OR, we can achieve this result with one 7404 hex inverter, one 7408 AND gate chip, and one 7432 OR gate chip. However, a more gate-efficient way to do this is with one XNOR gate, one XOR gate, and one AND gate:
(A7 XNOR B7) AND (A7 XOR ADD7)
The latter setup is preferable, since it leaves us with free AND gates on the 7408 chip. This is important, because we need to AND the result of this whole operation with SUMS. The 6502 only has two opcodes which use the ALU and can set the overflow flag, namely ADC (addition) and SBC (subtraction).* Since these are the operations that use the adder portion of the ALU, the overflow-out signal from the ALU should only turn on when the adder is active, meaning when SUMS is active.
* Except for the BIT opcode, but this is not relevant here since BIT does not set the overflow flag using the ALU's overflow-out signal, but rather using the 6502's DB6/V signal.
Thus, the overflow substructure is one 74266 XNOR chip, one 7408 AND chip, and one 7486 XOR chip. A7 is XNORed with B7, A7 is XORed with ADD7, and the results of these two operations are ANDed together. The result of this AND operation is finally ANDed with SUMS to produce the overflow output.
Brief overview of opcodes that invoke the 6502's ALU
As this document focuses primarily on the ALU itself and opcode work lies in the domain of the CPU's microcode, it is currently beyond the scope of this document to describe how the 6502's ALU would be programmed using microcode or a control matrix. However, the following is a brief overview of all the 6502 opcodes that make use of the ALU, with some details on how the 6502 implements these opcodes using the mere five functions that the ALU allows.
Normal addition. This is obviously performed using the adder within the ALU.
ASL (Arithmetic Shift Left)
As mentioned previously, any digital number can be shifted one place to the left by simply adding it to itself. Thus, the ALU's "shift left" operation is performed by loading the same number into both ALU inputs and then adding them to each other.
BIT (test bits)
Bit "testing" is actually performed using an AND operation: The contents of a given memory address are loaded into one ALU input, and the contents of the 6502's accumulator are loaded into the other ALU input. These inputs are then ANDed together to produce output.
CMP (compare accumulator), CPX (compare X register), and CPY (compare Y register)
Compare operations are actually performed as a binary subtraction operation; as noted earlier, binary "subtraction" is actually performed as an addition.
Decrementing is simply a subtraction by the number 1. DEC is thus implemented as a subtraction in which the subtrahend is always 1.
EOR (exclusive OR)
Bitwise EOR, also known as XOR.
Incrementing is simply an addition with the number 1. INC is thus implemented as an addition in which one addend is always 1.
LSR (Logical Shift Right)
Shifts all bits right one position. Bit 0 is shifted into bit 7, and the original bit 0 is shifted into the Carry.
ORA (OR with Accumulator)
ROL (Rotate Left)
Shifts all bits left one position. The Carry is shifted into bit 0, and the original bit 7 is shifted into the Carry.
ROR (Rotate Right)
Shifts all bits right one position. The Carry is shifted into bit 7, and the original bit 0 is shifted into the Carry.
Subtraction, which, again, is actually a form of addition.
Implementing the registers surrounding the ALU
The 6502's ALU connects to three registers: Two input registers and one output register. While these registers are not technically part of the ALU itself, I have taken the liberty of suggesting an implementation of these registers and how they might be connected to the rest of the ALU. I will divide this section into three substructures:
Register A substructure
Register B substructure
Adder hold register substructure
Overview of the three registers surrounding the ALU
Input register A receives data input from the system bus (SB) of the 6502. This register has two control input signals: SB/ADD and 0/ADD. The SB/ADD signal, when active, loads the contents of the system bus into the register. The 0/ADD signal "zeroes out" input register A by connecting all of its data inputs to ground. Input register A's only output is its 8-bit data ouput, which is directly connected to the ALU and is "always on," meaning there is no signal to enable or disable this register's output.
Input register B can receive data input from either the data bus (DB) of the 6502, or the low address bus (ADL) of the 6502. This register has three control input signals: DB/ADD, /DB/ADD, and ADL/ADD. ("/DB/ADD" should properly be rendered with a bar over the "DB" portion to indicate inversion, but as this cannot be done in HTML without CSS, I am using "slash notation" to indicate negation here.) The DB/ADD signal, when active, loads the contents of the data bus into input register B. The /DB/ADD signal loads the inverted contents of the data bus into input register B; this is accomplished with a bank of inverters. The ADL/ADD signal loads the contents of the low address bus into input register B. Like input register A, Input register B has only one output: its 8-bit data ouput, which is directly connected to the ALU and is "always on," meaning there is no signal to enable or disable this register's output.
The adder hold register (ADD) receives output from the ALU. This register is clocked by the 6502's internal PHI2 clock signal, meaning that when PHI2 becomes active, the contents of the ALU are loaded into the ADD. The ADD has three other input signals, each of which controls its output: ADD/ADL, ADD/SB(0-6), and ADD/SB(7). The ADD/ADL signal, when active, outputs the contents of the ADD onto the low address bus (ADL) of the 6502. The ADD/SB(0-6) signal outputs the lowest seven bits of the ADD onto the system bus (SB) of the 6502. The ADD/SB(7) signal outputs the highest bit of the ADD onto the system bus (SB) of the 6502.
Register A substructure
The substructure for the ALU's input register A consists of five chips: The 74374 chip which constitutes the actual A register itself, two 74244 buffer chips, a 7404 NOT gate (inverter) chip, and a 7432 OR gate chip.
One of the 74244 buffer chips stands between the system bus (SB) and register A. This buffer chip's gate inputs are attached to the SB/ADD control signal. The chip's inputs are connected directly to the system bus, and its outputs go directly to the inputs of register A.
The other 74244 buffer chip is the one used when we simply want to fill register A with all zeroes. This chip's gate inputs are controlled by the 0/ADD control signal. Its inputs are all connected directly to ground. Its outputs go directly to the inputs of register A.
The problem that arises here is that register A can get its input from two separate places, and both places need the ability to drive register A's clock input. Because this clock input can be driven by two separate signals, we run both signals through an OR gate. However, these signals are active-low, and register A's clock input triggers on a rising edge, so we first invert the SB/ADD and 0/ADD signals using the 7404 chip, then the results go to the input of an OR gate on the 7432. Finally, the output of this OR gate drives the clock input for register A.
Register A's outputs go into the body of the ALU.
Register B substructure
The substructure for the ALU's input register B is somewhat more complicated than that for register A, partly because register B can get its input from three different sources, and also because one of those sources requires an inversion.
Technically, register B can only get its input from either the data bus (DB) or the address bus low (ADL). However, there is an option to load register B with the inverted contents of the data bus, and so this requires a third buffer chip.
There are thus seven chips which comprise the register B substructure: The 74374 chip which constitutes the actual B register itself, three 74244 buffer chips (since the B register can get its input from three separate places), two 7404 hex inverters (which will form the inverted contents of the data bus), and a 7432 OR gate chip, which will control register B's clock input.
The ADL is connected directly to the inputs of one of the 74244 buffer chips, and the gates on this buffer chip are controlled by the ADL/ADD control signal.
The data bus is similarly connected directly to the inputs of another 74244 buffer chip, and the gates on this buffer chip are controlled by the DB/ADD control signal.
Finally, the data bus is also connected to the inputs of the two 7404 hex inverters, and the output of these inverters goes to the input of the third buffer chip, whose gates are controlled by the /DB/ADD control signal.
The outputs of all three buffer chips go to the inputs of register B.
Because the control signals ADL/ADD, DB/ADD, and /DB/ADD are all active-low, we run them through inverters (which we conveniently have more than enough of left over since we used two 7404 chips), then finally cascade these three active-high signals into the 7432 OR chip. If any of these signals are active, this will trigger register B's clock input.
Register B's outputs go into the body of the ALU.
Adder hold register substructure
The ALU's output register is called the adder holder register, abbreviated ADD. Its substructure consists of six chips: The 74374 chip which constitutes the actual ADD register itself, a 7404 hex inverter chip, a 7432 OR chip, and three 74244 buffer chips.
Because the ADD gets input from five different places (the OR substructure, the AND substructure, the EOR substructure, the adder substructure, and the shift-right substructure), we run into the same input-clocking problem we had with registers A and B, namely that several different outputs are driving that one input. To circumvent this issue, ORS, ANDS, EORS, SUMS, and SRS are all inverted (to make them active-high), then cascaded in a series or OR gates such that if any of these inputs are on, ADD's clock input is activated.
The three 74244 buffer chips are for the ADD's output. The ADD has three separate output control signals, and so each of these drives a separate buffer chip to direct the ADD's output to different parts of the CPU.