The patent for the 6502’s ALU adder circuits expired today, by chance the same day I wrote 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 [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 > 9) ? binSum + 6 : binSum; assign Cbin = binSum[4]; assign Cdec = binSum > 9; endmodule

All those gates described in eight pages of a patent in the mid 1970s boil down to the simple behaviour above. What was arguably patentable a few decades ago is, given today’s tools, meaningless as any kind of ‘invention’. I see this as an example of why the patent system needs to keep pace with tools. What made sense in the mid 1970s is absurd today.

Anyway, I digress. Here’s the testbed code that puts two of these together to form an 8-bit BCD parallel adder, and generates signals to show typical and boundary calculations.

`timescale 1us / 1us module bcdd_tb; reg [7:0] A; reg [7:0] B; reg Cin; wire [7:0] OUT; wire hCbin; wire hCdec; wire Cbin; wire Cdec; initial begin $dumpfile("bcdd_tb.lxt"); $dumpvars(0, bcdd_tb, A,B,Cin,OUT,hCbin,hCdec,Cbin,Cdec); // 1 + 7 = 8 #0 Cin = 0; #0 A = 1; #0 B = 7; // 8 + 3 = 1 with C #1 Cin = 0; #0 A = 8; #0 B = 3; // 1 + 0 = 1 #1 Cin = 0; #0 A = 1; #0 B = 0; // 8 + 0 + C = 9 #1 Cin = 1; #0 A = 8; #0 B = 0; // 75 + 21 = 96 #1 Cin = 0; #0 A = 8'h75; #0 B = 8'h21; // 98 + 1 + C = 100 #1 Cin = 1; #0 A = 8'h98; #0 B = 8'h1; // 99 + 1 = 100 #1 Cin = 0; #0 A = 8'h99; #0 B = 8'h1; #1 $finish; end bcdAdder bcdd1( A[3:0], B[3:0], Cin, OUT[3:0], hCbin, hCdec ); bcdAdder bcdd2( A[7:4], B[7:4], hCbin|hCdec, OUT[7:4], Cbin, Cdec );

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 to go into the ALU of my toy 6502ish CPU. I have a mild urge to reproduce the schematic in Verilog at gate level, but I can’t face the (admittedly modest) boolean algebra needed. I’m not made of the same stuff as the folk who invented this stuff!