List page: One bit computer

I am working on building a computer with no ICs.

The goal is to build a computer using the simplest components available, and where it is possible follow data through an entire computation. Ideally, it would be built from relays, but they are very expensive and too slow for any real time applications. Transistors offer a nice balance between cost, speed and complexity. While you can not see how a transistor operates just by looking at it, the function is fairly simple, and so is the actual physics behind them.

To minimize the amount of logic required for a functional computer, it will use a one bit data bus, ALU and registers. This also allows the most efficient use of RAM. (Most computers use a whole 8 bits for a boolean value)

Unfortunately, the addresses and program counter have to be bigger then one bit. (Building a counter is a lot simpler then an multi-bit adder) The instructions will also have to be a lot bigger to fit both an opcode and operand address.

Design Requirements:

I want the computer to be able to run simple games like Snake and Tetris, as well as a do simple mathematics like addition, multiplication, square roots, logs, etc. 4kB of address space should be more then enough for these applications and can always be left mostly empty. It should also be constructed from just a few types of components: NPN transistors, diodes, resistors, LEDs and switches. (and a few capacitors for the clock)

It should also be reasonably compact, a functional system should fit in 1 m² with all the components visible. A full 32 thousand bits of ram (4 kB) probably won’t fit, I am totally fine with stacking memory boards to have enough for games and stuff.

General Architecture:

To avoid a separate fetch and execute stage, the computer will use a Harvard style architecture with separate program ROM and data RAM. This also has the advantage that ROM is much, much simpler then RAM. There are 2 clock phases, during phase 1, the program counter updates, the instruction is read from ROM, the operand is fetched and the new register state is computed. During phase 2, the registers update, memory is written to, and the next value for the program counter is computed.

Instructions will be 16 bits with 4 opcode bits, a zero page bit, a register select bit and 10 address offset bits:

Range (inclusive)	Use
Bit 0 (LSB) to bit 9	Address offset (10 bits)
Bit 10	Register select
Bit 11	Zero page bit
Bit 12 to 15 (MSB)	Opcode

CPU:

The CPU itself has a one bit ALU, accumulator register and carry flag. There are 2 more registers, Skip and OEN (Output ENable) that are used for conditional execution. Skip is used to skip single instructions, and OEN can disable writing to memory to perform larger conditionals without jumping.

The registers are implemented as a chain of 2 d-latches, with the first one saving the result from the ALU, and the second being the input to the ALU. During phase 1, the first one stores the result, and during phase 2, the second one copies the data in the first. The exception is the Skip register, which has the clock phases reversed, so that it updates during phase 1, and stays constant during phase 2. The Skip register is used to gate the phase 2 clock to registers, memory, as well as jump circuitry, so it has to stay constant during phase 2.

There are 16 instructions, based off of the MC14500 ICU chip. Unlike the MC14500, my computer will include arithmetic instructions, which add quite a bit of complexity (full adder, carry register and control logic) but add a lot of utility. (The MC14500 takes 12 cycles to add a bit with carry!)

Opcode	Name	Function
0000 0	NOP	Strobes the NOP flag.
0001 1	LD	Load the bus into the accumulator.
0010 2	LDC	Load the complement of the bus into the accumulator.
0011 3	STO	Writes the accumulator on the the bus
0100 4	STOC	Writes the complement of the accumulator on the bus.
0101 5	OEN	Loads the OEN register from the bus.
0110 6	ADD	Adds the accumulator, carry register and the bus, using the carry register to store the carry.
0111 7	XNOR	XNORs the accumulator with the bus.
1000 8	XOR	XORs the accumulator with the bus.
1001 9	AND	ANDs the accumulator with the bus.
1010 A	OR	ORs the accumulator with the bus.
1011 B	ONE	Forces a one into the accumulator and a zero into the carry.
1100 C	TWO	Forces a zero into the accumulator and a one into the carry.
1101 D	JMP	Strobes the jump flag, see the “program counter” section.
1110 E	SKZ	Skips the next instruction if the data bus is zero.
1111 F	RET	Skips the next instruction and strobes the return flag.

If OEN is set to zero, write operations are skipped (STO/STOC), but computation continues normally.

Some of these instructions don’t have a function, like NOP and RET, and can be used as spare instruction for expansion.

This CPU can be implemnted in very few gates, and in practice will be even fewer as the gates can often be combined together when building them from transistors:

Memory/Addressing:

There are 2, 15-bit, memory mapped index registers, each can address 4kB of memory (yes, 4kB, each address only has one bit). They are used for cheap offset addressing, where an OR gate is used instead of an adder.

The index register used for an instruction is selected by the register select bit. If the zero page bit is 0, the value in the selected index register register is ORed with the address offset in the instruction to determine the memory address. If the zero page bit is 1, the address offset is used directly as the memory address.

The memory map currently looks like this:

Start	End (inclusive)	Use
0x0	0x0	Value of the accumulator register, read only
0x0	0x0	Halt flag, stops execution if a one is written, write only
0x1	0xf	The currently unselected index register (MSB first)
0x10	0x1f	Jump destination (MSB first)
0x20	0x7fff	Main memory, will include IO at some point

The reason the currently unselected index register is mapped is to prevent writing to an index register using indirect addressing causing memory corruption when the address changes during a write.

Program counter:

The program counter is the address into the program ROM of the current instruction, and counts up by 1 every cycle at the start of phase 1. It will be implemented using 2 chained latches for every bit, with the first one updating during phase 2, and the second during phase 1. During normal operation, the lest significant one always toggles, and every other only toggles if all the bits less significant then it it are ones

The exception to this is the JMP instruction, if the Jump flag is one, and Skip is zero, the the next value will instead be computed from the operand to the instruction: If the zero page bit is 0, the Jump Destination register (really just a special 16 bits in memory) is ORed with the offset to determine the new program counter value. If the zero page bit is 1, the program counter will simply be set to the offset part of the instruction.

Progress updates:

Below is a every post I have made about the computer, in reverse chronological order:

One bit computer: Improving code density by redesigning JMP

A big problem with the one bit computer architecture is its very low code density. It takes 2 instructions just to copy a bit, copying a byte takes 16, and 2 bytes 32 instructions. At two bytes per instructions, that’s 64 bytes of code to copy 16 bits! If you want to loop to avoid repeating code, the jump destination register (16 bits) has to be set, which itself takes 17 instructions. Oct 12, 2023 (One bit computer)

One bit computer: transistor level register design

Previously, I looked at gate level register designs, but now I need a transistor level design: The loop of NOT gates made from transistors looks like this: Adding inputs inputs is easier then with logic gates, simply add another transistor to pull the output of a gate low: To ensure things happen at the right time, the latch needs an enable input. The simplest way to add this is by connecting/disconnecting the ground to the transistors on the input. Oct 10, 2023 (One bit computer)

One bit computer: 4 to 16 instruction decoder

The first thing the computer has to with an instruction is to figure out what instruction it is. This is done using a fairly standard decoder (in the red box): A NOR gate only outputs a 1 if all of the inputs, in this case, bits of the instruction are 0. If a bit of the instruction is inverted before the NOR gate, that bit will have to be a 1 for the output to be a 1. Oct 10, 2023 (One bit computer)

One bit computer: Instruction set tweaks

I have decided to make a few small changes to the instruction set, to make things more usable. The first change is to make the SKZ instruction use the data bus, not the accumulator1. This makes it much more versatile, because it can be used in the middle of a computation, without modifying the accumulator. As the accumulator is memory mapped, the old behavior can still be achieved. Another change is with the NOP instruction, becuase it is not used for instruction skipping, it can be used for something else. Sep 17, 2023 (One bit computer)

Building logic gates

This is a gate level diagram of the one bit CPU: Not much is new here, it has an ALU, a few registers, a fairly standard decoder and some OR gates to drive the ALU. Together they implement all 16 of the instructions from the first post: Opcode Name Function 0000 0 NOP Does nothing 0001 1 LD Load the bus into the accumulator 0010 2 LDC Load the complement of the bus into the accumulator 0011 3 STO Writes the accumulator on the the bus 0100 4 STOC Writes the complement of the accumulator on the bus 0101 5 OEN Loads the OEN register from the bus 0110 6 ADD Adds the accumulator to the bus, using the carry register to store the carry 0111 7 XNOR XNORs the accumulator with the bus 1000 8 XOR XORs the accumulator with the bus 1001 9 AND ANDs the accumulator with the bus 1010 A OR ORs the accumulator with the bus 1011 B ONE Forces a one into the accumulator and a zero into the carry 1100 C TWO Forces a zero into the accumulator and a one into the carry 1101 D JMP Strobes the jump flag 1110 E SKZ Skips the next instruction of the accumulator is zero 1111 F RET Skips the next instruction and strobes the return flag The diagram is drawn with logic gates, describing abstract logic, like “The output should be true if and only if all of the inputs are true”. Sep 16, 2023 (One bit computer)

Block diagram and control logic requirements

One-bit CPU block diagram, does not include program ROM, addressing, memory, or IO: Unlike many other simple computers, the data bus (the thick bidirectional arrow, in reality just a long wire) is only used for interacting with memory and IO. This has the advantage that almost everything can happen at the same time, allowing all instructions to be executed in just one clock cycle, removing the need for microcode or complex sequencing logic. Sep 14, 2023 (One bit computer)

One bit computer: designing a register

Two NOT gates wired into a loop have a rather interesting property: They have 2 distinct stable states: This is of limited utility, because there is no way to switch between the two states. This can be fixed by replacing the not gates with NAND1 gates, if an input is high, it behaves like a NOT gate, but if an input is low, the output is forced high: This circuit stores 1 bit of information, it remembers which input was last pulled low. Sep 7, 2023 (One bit computer)

One bit computer: Addressing considerations

I handwaved addressing in the first post, but it is very important, and will have a huge impact on how usable the final computer is. Because the opcodes contain no addressing information, addressing must be done with extra bits in the instruction1. The simplest option is direct addressing, where the extra bits directly control the address. For example, a 12 bit instruction can be spit into a 4-bit opcode and a 8-bit address, providing 256 bits (32 bytes) of address space: Sep 6, 2023 (One bit computer)

One bit computer: ALU design

The one bit computer’s ALU will have to perform a quite a few different operations: Addition Loading into the accumulator Loading the complement into the accumulator Logical AND Logical OR Logical XOR Logical XNOR Forcing a 1 Forcing a 2. It turns out most of these operations can be implemented using a very simple circuit: A 4 to 1 multiplexer (One can be constructed with just 8 transistors). Sep 6, 2023 (One bit computer)

Designing a Discrete Transistor Computer

Computers are ubiquitous, but nearly all computers are literal black boxes: integrated circuits. Sure, in older, larger computers you might be able to see the data being transferred in and out of memory with a few LEDs, but the data still disappears into an black box: the CPU. Even if you decap an old CPU like the Z80 or MOS 6502, all you can see is a static view of the transistors, you can’t see the computer actually computing. Sep 4, 2023 (One bit computer)