8-bit Computer: ALU

With an "A" and "B" register in place for my 8-bit computer, I need to implement an Arithmetic Logic (ALU).  The ALU is the part of the computer where the interesting stuff happens - data is manipulated in some way, i.e. where the computer actually COMPUTES!  Ben Eater uses 2 x 74LS283 4-bit addition ICs in his ALU to perform 8-bit addition of an A and B register, and uses a control signal and some glue logic to implement subtraction by way of 2s complement addition.  Flags are then set based on the outcome of the ALU, and the program can branch (or not).  I considered a similar implementation with 74LS283 chips, but also adding some logic gate, i.e. an 8-bit NAND or NOR function to construct different logic functions.  The outputs from the addition/subtraction section and the NAND/NOR logic section would then need to be multiplexed to select the output of interest and latched into the flag register which I decided not to have the appetite for.

ALU design

On reflection I decided to keep my ALU simple and cheat (kinda) by using 2 x 74LS181, 4-bit ALU/function generators.  The chips generate 16 logic functions (wikipedia), including addition and subtraction and so are an efficient use of space for a breadboard ALU.  Four inputs are used to select one of 16 functions.  In addition a further input selects between logic and arithmetic mode, and a carry-in bit can be specified.  In total 6 control signals are required therefore for input into the ALU.  A further two control signals will be required to specify the ALU-output to the databus and latching the ALU-flags into the flag register.  Ultimately the control signals will be outputs from a panel of EEPROMs and the more control signals I have, the more EEPROMs I will need, and the more of a pain in the a** it will be to program the microcode across them all.  Therefore I am mindful to try and be as efficient as possible with control signals, for example I may use a decoding system for the databus outputs, as only one chip can output onto the databus at once.  In this case, I am using the lower 4-bits of the instruction register, and the carry-bit from the flag register, as a lookup into an EEPROM on the ALU to set the 4 control signals, the mode signal and the carry-in bit.  Therefore I have eliminated the need for 6 direct control signals in the ALU!  The 74LS181-based ALU is shown below, fed by registers A and B directly, and the 6 control signals set by the EEPROM (AT28C16).

I'm addressing the Atmel AT28C16 EEPROM chip using the lower 4-bits of the instruction and the carry bit, to form a 5-bit address.  The address looks up the output byte that then correctly sets S0-3, M and Carry-in on the 74LS181 chips, using the following table:

I wrote a python script (ALU_rom.py on github) which generates ALU.py.  I then hooked up my micropython pyboard (v1.0) to my EEPROM chip and used it as a EEPROM programmer by running main.py (imports ALU.py previously generated).  After writing the EEPROM into the ALU, and entering data into A and B, and setting the instruction 4-bits manually, all seems to be working as planned!

FLAG register

The purpose of the flag register, is primary to set signals high or low based on the output of the ALU, such that program branching can occur conditionally.  After some thought, I have decided to implement a 4-bit flag register to monitor:

• Zero flag (Z). Set true when the ALU output is equal to 0.  This can be used for implementing JZ (jump if zero) and JNZ (jump if not zero) instructions.
• Carry flag (C). Note that the carry bit is actually inverted because of the way the 75LS181 operates, so a Carry = High means no carry bit set, and a Carry = Low means a carry bit is set.  I will probably write the microcode to obscure this from the programmer though as it is a little confusing.
• Negative (N) = Useful for negative number arithmetic, and indicates whether the MSB of the ALU output is high or low.  At the moment I haven't thought too much about implementing negative numbers, but this flag will probably be useful when I do.
• There is no fourth flag! I reserve the option to add something later...  

The 4-bits of the FLAG register can either be set from the flag values derived from the ALU or imported from the data bus, by use of a multiplex 74LS157 (quad 2-line to 1-line data selector/multiplexer).  After the multiplex, the values are latched with a 74LS173 D-type flip-flop.  The register can also be put onto the data bus with the octal bus transceiver 74LS245.   This ability to store and restore the FLAG register (from the stack for example) will be useful if I implement interrupts later.  The remaining 4 bits higher of the FLAG register can be used for holding other useful status bits, such as whether there is a UART character in the RX buffer.  Note that 8-bits of the flag register go onto the data bus, so that the higher bits in particular can be examined and acted on, i.e. imagine we CALL checkRX:

checkRX:

MOV A, FLAGS    ; Move FLAGS register into A

AND (1<<RX_WAITING)    ; Test the RX_WAITING bit for UART RX status 

JNZ getRXchar          ; If there is a bit, jump to getRXchar

; No character carry on doing stuff

.

.

ret

getRXchar:

; Got a character, handle that here

ret

Combining Z and C flag for conditional jumps

I plan to implement a "Compare" (CMP) instruction to evaluate whether two values are equal, less than, or greater than, etc.  Internally, this will be implemented by evaluating a A-B on the ALU, setting the flags but not moving the result out of the ALU (as we would do with SUB instruction).

A-B (CMP instruction):

	A<B	A=B	A>B
Z	0	1	0
C	1	0	0

We can see how different Z,C combinations can allow us to implement a JE (jump if equal), JNE (jump if not equal), JL (jump if less than) and JG (jump if greater than) instructions.  It is also trivial to implement a JLE (jump if less than or equal) and a JGE (jump if greater than or equal) by jumping on the equality condition as well in each case.  The final combination table of the Carry flag and Z flag to implement these instructions therefore looks like this:

	C=0	C=1
Z=0	JG, JGE, JNE	JL, JLE, JNE
Z=1	JE,JGE, JLE	-

ALU instruction set

As previously mentioned, the lower four bits of the instruction register form part of the EEPROM lookup for the ALU control signals, in combination with the FLAG carry bit.  This means that all opcodes will mindlessly change the ALU function and output.  This isn't a problem as the microcode has to signal to the FLAG register to update the flags, or output the ALU product so no harm can be caused inadvertently.  In fact it has the advantage of saving ALU control signals and allowing easy implementation of different addressing modes and operations.  

For example let's define an instruction and give it the opcode 0x02:

NAND 0x42 ; means A = NAND(A, 0x42)

; machine-code would be 0x02, 0x42

The NAND product is produced by setting S3,S2,S1,S0 and M to L,H,L,L and H respectively on the 74LS181.  Given the way I am controlling the ALU, any instruction opcode with '2' as the lower 4 bits ( i.e. 2, 2+16, 2+16+16, etc) will direct the ALU to perform the NAND instruction,.  Now let's say we want to implement a different addressing mode where we want to NAND with the B register, we can define this new instruction at 0x02+16 = 0x12 i.e.:

NAND B ; means A = NAND(A,B), machine code is 0x02 + 16 = 0x12 

It will be up to the microcode to distinguish the two instructions (NAND immediate and NAND B) by implementing the different data addressing modes.  We could then implement a NAND [0x1234] or NAND [0x12] (zero-page addressing) in a similar way to use a value from a memory address.

In addition to the most useful logic and arithmetic operations, I have included operands for adding and subtracting with carry, for simulating 16-bit numbers (and beyond...).   For example, let's look at ADDC , add with carry:

; Add 0x1234 and 0x01F0 and store the result at memory location 0x0100.  Start with the lower bytes and then the higher bytes.

MOV A, 0x34    ; A = 0x34

ADD A, 0xF0    ; A = 0x34 + 0xF0 = 292 & 0xFF = 36, CARRY set

MOV A, [0x100] ; Store A in memory 0x0100

MOV A, 0x12    ; A = 0x12

ADDC 0x01      ; A = 0x12 + 0x01 + CARRY = 0x14

MOV A, [0x101] ; Store A in memory 0x0101

Subtract with carry (SUBC, opcode = 0x06) has also been implemented.  It turns out the same control signals for SUBC are required for "Compare with Carry", which is similar to CMP but uses the carry flag to remember the result of a previous CMP in the correct way and can be used to compare 16-bit numbers.  As the control signals are the same, I can set the opcode of CMPC in a spare slot, so long as the lower 4-bits = 0x06.  I used the next free slot, 0x24 = 38 = 6 + 2*16.  An example of CMP and CMPC in action:

; Let's compare 0xAA01 and 0xAA02.

MOV A, 0x01     ; A = 01

CMP A, 0x02     ; Carry flag is set

MOV A, 0xAA     ; A = 0xAA

CMPC A, 0xAA    ; carry flag (C=1) and Zero flag = 0

; Therefore A<B as required.  Without CMPC 0xAA = 0xAA we are misled to think A=B.

Well, that's enough about the ALU and the FLAG register.  Suddenly I feel like this pile of 7400 series logic chips has just become more interesting!  Of course it can't do anything until the control logic is implemented, but the ALU and FLAG register were crucial steps.  I think next I'll tackle the 16-bit Memory Address Register (MAR) and the logic to control the VRAM, SRAM and ROM!