The patent for the 6502’s ALU adder circuits, now expired, I found while writing a BCD adder in Verilog to go with a toy 6502ish CPU I am designing. So, I thought I’d re-implement it loosely based on the MOS solution.

The following schematic is unlikely to be needed, but might shed some light on the details. The scans have been pasted together, but don’t quite align towards the bottom. Some squinting will be required to make sense of it. There are a few lines that look unconnected, which I assume are just separators.

Roughly, the schematic is formed by three columns, the left side defines the binary adder, the middle shows the decimal carry calculation, and the right side generates the decimal correction.

The patent text really just describes the gates implemented above. However, it talks about them logically, rather than referring to the actual gates used, so unless you can apply De Morgan’s’ laws as you read (I can’t!), then it will be slow going trying to figure it all out.

The C code below is a behavioural implementation of the circuits described in the patent. It doesn’t overlap exactly the diagram in Fig.1, e.g. the carry flags are generated in the adder module rather than being derived separately using gates.

The code in the main() block generates test data output for the adder, the decimal corrector, and then both parts combined into two 4-bit adders.

#include <stdio.h> #include <stdbool.h> /* * The Parallel Binary Adder - (4-bit) module. */ void pbAdder( unsigned char A, // 4-bit nibble unsigned char B, // 4-bit nibble bool Cin, // Carry in unsigned char *BS, // Binary Sum bool *BC, // Binary Carry bool *DC) // Decimal Carry { // Sanitise 8-bit values to 4 bits. A = A & 0xf; B = B & 0xf; *BS = (A + B + Cin) & 0xf; *BC = ((A + B + Cin) & 0x10) != 0; *DC = (A + B + Cin) > 9; printf("A=%d, B=%d, BS=%d, BC=%d, DC=%d\n", A, B, *BS, *BC, *DC); } /* * Decimal correction gating, generating DS (final ACC output) */ void dcGating( unsigned char BS, // 4-bit Binary Sum bool DAA, // Decimal Addition flag bool DSA, // Decimal Subtraction flag unsigned char *DS) // Decimal Sum (or Binary pass-thru) { bool BS0 = (BS & 1); bool BS1 = (BS & 2) >> 1; bool BS2 = (BS & 4) >> 2; bool BS3 = (BS & 8) >> 3; bool DS0 = BS0; bool DS1 = (DAA | DSA) ^ BS1; bool DS2 = ((DSA & BS1) | (DAA & ~BS1)) ^ BS2; bool DS3 = ( ((BS1 | BS2) & DAA) | (~BS1 | ~BS2) & DSA) ^ BS3; printf("BS: %d%d%d%d\t", BS3, BS2, BS1, BS0); printf("DS: %d%d%d%d\n", DS3, DS2, DS1, DS0); // Select DS if resulting decimal is 0xa thru 0xf *DS = (DAA | DSA) & BS3 & (BS1|BS2) ? DS3 << 3|DS2 << 2|DS1 << 1 | DS0 : BS3 << 3|BS2 << 2|BS1 << 1 | BS0; printf("ACC OUT: %02X\n", *DS); } void main() { // Test some 4-bit addition and carry outputs. unsigned char sum; bool BC3; // Binary Carry from adder bit 3 bool DC3; // Decimal Carry from adder bit 3 // Test data 1 - mostly boundary cases. {A, B, Cin} unsigned char td1[][3] = { {1,2,0}, {8,1,0}, {8,1,1}, {9,1,0}, {9,1,1}, {14,1,0}, {14,1,1} }; int num_td1 = sizeof(td1) / sizeof(*td1); int i; for(i=0; i < num_td1; i++) { pbAdder(td1[i][0], td1[i][1], td1[i][2], &sum, &BC3, &DC3); } // Enumerate all adder outputs, with decimal corrections. unsigned char accumulator; for(i=9; i < 16; i++) { printf("\n"); dcGating(i, 1, 0, &accumulator); } printf("\n"); // Test combination of two 4-bit adders unsigned char td2[][5] = { {0, 15, 0, 0, 0}, {240, 15, 0, 0, 0}, {0x98, 1, 0, 1, 0}, {0x98, 1, 1, 1, 0}, {0x98, 2, 0, 1, 0}, {0x99, ~2, 1, 0, 1}, {0x99, ~0x22, 1, 0, 1}, {100, ~2, 1, 0, 0} }; int num_td2 = sizeof(td2) / sizeof(*td2); for(i=0; i < num_td2; i++) { unsigned char A=td2[i][0], B=td2[i][1]; bool Cin = td2[i][2]; bool DAA=td2[i][3], DSA=td2[i][4]; unsigned char sumL, sumH; unsigned char ACC; printf("A:%02X (%d), B:%02X (%d), Cin:%d\n", A, A, B, B, Cin); pbAdder(A&0xf, B&0xf, Cin, &sumL, &BC3, &DC3); dcGating(sumL, DAA, DSA, &sumL); pbAdder((A&0xf0)>>4, (B&0xf0)>>4, DAA&DC3|BC3, &sumH, &BC3, &DC3); dcGating(sumH, DAA, DSA, &sumH); ACC=sumH * 16 + sumL; printf("8-Bit OUT: 0x%02X (%d) BC=%d, DC=%d\n\n", ACC, ACC, BC3, DC3); } }

A:00 (0), B:0F (15), Cin:0 A=0, B=15, BS=15, BC=0, DC=1 BS: 1111 DS: 1111 ACC OUT: 0F A=0, B=0, BS=0, BC=0, DC=0 BS: 0000 DS: 0000 ACC OUT: 00 8-Bit OUT: 0x0F (15) BC=0, DC=0 A:F0 (240), B:0F (15), Cin:0 A=0, B=15, BS=15, BC=0, DC=1 BS: 1111 DS: 1111 ACC OUT: 0F A=15, B=0, BS=15, BC=0, DC=1 BS: 1111 DS: 1111 ACC OUT: 0F 8-Bit OUT: 0xFF (255) BC=0, DC=1 A:98 (152), B:01 (1), Cin:0 A=8, B=1, BS=9, BC=0, DC=0 BS: 1001 DS: 1111 ACC OUT: 09 A=9, B=0, BS=9, BC=0, DC=0 BS: 1001 DS: 1111 ACC OUT: 09 8-Bit OUT: 0x99 (153) BC=0, DC=0 A:98 (152), B:01 (1), Cin:1 A=8, B=1, BS=10, BC=0, DC=1 BS: 1010 DS: 0000 ACC OUT: 00 A=9, B=0, BS=10, BC=0, DC=1 BS: 1010 DS: 0000 ACC OUT: 00 8-Bit OUT: 0x00 (0) BC=0, DC=1 A:98 (152), B:02 (2), Cin:0 A=8, B=2, BS=10, BC=0, DC=1 BS: 1010 DS: 0000 ACC OUT: 00 A=9, B=0, BS=10, BC=0, DC=1 BS: 1010 DS: 0000 ACC OUT: 00 8-Bit OUT: 0x00 (0) BC=0, DC=1 A:99 (153), B:FD (253), Cin:1 A=9, B=13, BS=7, BC=1, DC=1 BS: 0111 DS: 0001 ACC OUT: 07 A=9, B=15, BS=9, BC=1, DC=1 BS: 1001 DS: 0011 ACC OUT: 09 8-Bit OUT: 0x97 (151) BC=1, DC=1 A:99 (153), B:DD (221), Cin:1 A=9, B=13, BS=7, BC=1, DC=1 BS: 0111 DS: 0001 ACC OUT: 07 A=9, B=13, BS=7, BC=1, DC=1 BS: 0111 DS: 0001 ACC OUT: 07 8-Bit OUT: 0x77 (119) BC=1, DC=1 A:64 (100), B:FD (253), Cin:1 A=4, B=13, BS=2, BC=1, DC=1 BS: 0010 DS: 0010 ACC OUT: 02 A=6, B=15, BS=6, BC=1, DC=1 BS: 0110 DS: 0110 ACC OUT: 06 8-Bit OUT: 0x62 (98) BC=1, DC=1

The output from the 8-bit operations is shown in the right-hand column. Note that the patent is based on the NMOS version of the 6502, and predates the CMOS version that included changes to the way flags get handled.

The test data provides negative numbers pre-converted to 2’s complement form, which would normally be done within the ALU.

This code was written as an intermediate step to be subsequently converted to Verilog – I’m more familiar with C, so this made sense to me. A hardware engineer would doubtless go straight to the testbench.

The Verilog code below behaviourally describes the 4 bit adder. The carry input to the next 4-bit adder is `Cdec`

(decimal carry), though in the full implementation this would be `DAA & Cdec | Cbin`

(decimal flag AND decimal carry, or binary carry).

/* * BCD Digit Adder * Given two 4 bit inputs and a carry, produce a BCD addition. */ module bcdAdder( input DSA, input [3:0] A, input [3:0] B, input Cin, output [3:0] OUT, output Cbin, output Cdec ); wire [4:0] binSum; assign binSum = (A + B) + Cin; assign OUT = (binSum[3:0] > 9) ? (DSA ? (binSum - 6)&15 : binSum + 6) : binSum; assign Cbin = binSum[4]; assign Cdec = (binSum > 9) ^ DSA; endmodule

Here’s the code that puts two of these together to form an 8-bit BCD parallel adder inside the ALU. I have a testbed to generate some signals to show typical and boundary calculations, with the results shown in the GTKWave traces below.

/* * A 6502-like ALU. */ module alu( input [7:0] A, input [7:0] B, input Cin, input D, input [3:0] SEL, output [7:0] OUT, output C, output Z, output V, output N ); `include "alu_params.h" reg [8:0] x; // BCD adder wires wire [7:0] xd; wire Cbin, hCbin; wire Cdec, hCdec; wire sub = (SEL == op_sub); assign OUT = D ? xd : x[7:0]; assign C = (sub ^ x[8]); assign N = x[7]; assign V = ( (A[7] ^ x[7]) & ((sub ^ B[7]) ^ x[7]) ) != 0; assign Z = (OUT == 0); always @(A, B, Cin, D, SEL) begin case(SEL) op_add : x <= (A + B) + Cin; op_sub : x <= (A + (~B)) + Cin; op_and : x <= (A & B); op_or : x <= (A | B); op_xor : x <= (A ^ B); op_asl : x <= (A << 1); op_asr : x <= (A >> 1); op_lsl : x <= (A << 1); op_lsr : x <= (A >> 1); endcase end bcdAdder bcdd1(D & (SEL == op_sub), A[3:0], SEL == op_sub ? ~B[3:0] : B[3:0], Cin, xd[3:0], hCbin, hCdec ); bcdAdder bcdd2(D & (SEL == op_sub), A[7:4], SEL==op_sub?~B[7:4]:B[7:4], (D & hCdec)|hCbin, xd[7:4], Cbin, Cdec ); endmodule /* * BCD Digit Adder * Given two 4 bit inputs and a carry, produce a BCD addition. */ module bcdAdder( input DSA, input [3:0] A, input [3:0] B, input Cin, output [3:0] OUT, output Cbin, output Cdec ); wire [4:0] binSum; assign binSum = (A + B) + Cin; assign OUT = (binSum[3:0] > 9) ? (DSA ? (binSum - 6)&15 : binSum + 6) : binSum; assign Cbin = binSum[4]; assign Cdec = (binSum > 9) ^ DSA; endmodule

The resulting waveforms are shown below, which includes both the nibble adders as well as the register inputs and outputs.

So, that’s good enough for now, though it feels a bit messy; I have a strong suspicion that there’s redundancy in my implementation, but until I evaluate the gates in the schematic and implement it more accurately, it’s not pressing enough for me to bottom out. I’ll revisit when I have a bit more Verilog under my belt.

## References

Patent US3991307A – US Patent 991,307: Integrated circuit microprocessor with parallel binary adder having on-the-fly correction to provide decimal results.

Great work! Can you please send pdf/link to this patent in which the first 2 diagrams are from. Thanks a lot in advance!

Thanks for mentioning this, I’ve added a link to the patent, for anyone else who might be interested (I know you managed to find it yourself).