CODEWITHSUNDEEP
logiccpu-architecture
rjm27trekkie
rjm27trekkie

Reputation: 294

Universal Gate (NOR or NAND) Operator using Only Addition and Subtraction (8 bit)

I'm constructing an implementation of Ben Eater's 8 bit computer and the claim at the end is that it will be made turing complete by adding a conditional jump instruction. If this is true, then it should be possible to execute logical operators such as AND, OR, NOT... etc. using the ALU which does only addition and subtraction.

How would one implement NAND or NOR (universal gate operators) using only addition or subtraction? Is it even possible to do this given that the machine has 16 bytes of RAM and 2 bytes of registers?

Upvotes: 2

Views: 1012

Answers (1)

nathancharlesjones
nathancharlesjones

Reputation: 11

I think the 16 byte RAM is the limiting factor, but in general it's possible to implement any logical function using an ALU with just an adder. The trick is to get away from thinking about things at the bit level and towards thinking of using the full instruction set (however limited it might be) to write a subroutine or mini-program to do the thing we want.

For instance, we could create a 2 bit NOR operation using a 16-element look-up table with the following pseudo-assembly. Assume A and B are 2-bits numbers, A1A0 and B1B0, and there exists in memory a 16-element array called nor_array defined as { 0b11, 0b10, 0b01, 0b00, 0b10, ... }.

add a, a, a           // A = A + A, this is basically A = 2*A which effects a left shift
add a, a, a           // Same, only now A is equal to the original A * 4
add a, a, b           // A = A + B. A now has the original value of A in position [3,2]
                      // and the original value of B in position [1,0]
load a, nor_array[a]  // Load A with the value in memory at the nor_array base addr + A

Notice how the elements of nor_array are set equal to the 0th and 2nd bits of the array index nor'd together and the 1st and 3rd bits nor'd together.

nor_array[0000] = 0b11 // 0 NOR 0 = 1 ; 0 NOR 0 = 1
nor_array[0001] = 0b10 // 0 NOR 0 = 1 ; 0 NOR 1 = 0
nor_array[0010] = 0b01 // 0 NOR 1 = 0 ; 0 NOR 0 = 1
nor_array[0011] = 0b00 // 0 NOR 1 = 0 ; 0 NOR 1 = 0
nor_array[0100] = 0b10 // 0 NOR 0 = 1 ; 1 NOR 0 = 0
...

So A and B, together, define 16 total unique input combinations and we can effect a NOR operation by merely looking up in memory a value which we've pre-computed to be the result of a NOR operation between A and B. We can effect any logical operation on 2-bit numbers in this way and I believe that it's possible to extend those little subroutine to also be able to implement logical operations on arbitrarily long values of A and B by just shifting the operands in such a way as to build up the final result 2-bits at a time.

Upvotes: 1

Related Questions