Modeling an Arithmetic Logic Unit in Python

Joseph Mosby
@josephmosby

hey, what's up, hello

  • Python engineer at National Journal
  • Classic computing aficionado
  • Aspiring operating system writer

How does a CPU work, anyway?

How does a CPU work, anyway?

  • Clock
    A regular heartbeat running through the CPU to trigger instructions.
  • Program counter
    A marker for which line of the program should be executed
  • Fetch
    Retrieve the next instruction from the program memory
  • Decode
    Interpret the instruction into signals that control other parts of the CPU
  • Execute
    Do the work. Sometimes, that work is math.

credit: buzzfeed, naturally

When the instruction involves math...

The Arithmetic Logic Unit!

demonstration of a simple ALU that takes in two binary numbers, a status flag, and an opcode, and returns an added sum.

The Arithmetic Logic Unit!

Okay, so the ALU takes in two binary numbers, and based on the status of certain flags, it computes a function. Got it. I think.

Let's build one!

Inputs: x, y - two 16-bit binary numbers
Control Bits: zx, nx, zy, ny, f, no
Outputs:
x + yx - yy - x01-1
xy-x-y!x!y
x + 1y + 1x - 1y - 1x & yx | y

Outputs: zr if output == 0, ng if output < 0

Our Parts

  • Single-bit OR
  • Single-bit NOT
  • Single-bit AND
  • Single-bit XOR
  • 16-bit Multiplexer
  • 16-bit bitwise NOT
  • 16-bit bitwise AND
  • A 16-bit adder

credit: electrosmash.com

					
def single_bit_or(a, b):
	'''
	a: single bit, 1 or 0
	b: single bit, 1 or 0
	'''

	if a == 1 or b == 1:
		return 1
	else:
		return 0
					
				
					
def single_bit_not(a):
	'''
	a: single bit, 1 or 0
	'''

	if a == 1:
		return 0
	elif a == 0:
		return 1
					
				
					
def single_bit_and(a, b):
	'''
	a: single bit, 1 or 0
	b: single bit, 1 or 0
	'''

	if a == 1 and b == 1:
		return 1
	else:
		return 0
					
				
					
>>> single_bit_and(1, 0)
>>> 0

>>> single_bit_or(1, 0)
>>> 1

>>> single_bit_not(1)
>>> 0

>>> single_bit_and(1, 1)
>>> 1
					
				
					
def single_bit_xor(a, b):
	'''
	a: single bit, 1 or 0
	b: single bit, 1 or 0
	'''

	if a == b:
		return 0
	else:
		return 1
					
				
					
def sixteen_bit_not(a16):
	'''
	a16: binary number, formatted as list [0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1]

	Flip bits of all inputs
	'''
	return [single_bit_not(bit) for bit in a16]
					
				
					
def sixteen_bit_and(a16, b16):
	'''
	a16: binary number, formatted as list [0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1]
	b16: binary number, formatted as list [1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1]

	Binary AND bits of all inputs
	'''
	out = []
	for i, b in enumerate(a16):
		out.append(single_bit_and(a16[i], b16[i]))

	return out
					
				
					
def sixteen_bit_mux(a16, b16, sel):
	'''
	a16: binary number, formatted as list [0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1]
	b16: binary number, formatted as list [0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1]

	If selector bit (sel) == 0, return a16
	Else return b16
	'''

	if sel == 0:
		return a16
	else:
		return b16
					
				

Binary addition

0 1
+ 1 1
1 0 0
					
def half_adder(a, b):
	'''
	Outputs:
	sum: right bit of a + b
	carry: left bit of a + b
	'''
	sum = single_bit_xor(a, b)
	carry = single_bit_and(a, b)

	return sum, carry
					
				
					
def full_adder(a, b, right_carry):
	'''
	Outputs:
	sum: right bit of a + b + right_carry
	carry: left bit of a + b + right_carry
	'''

	right_sum, carry1 = half_adder(a, b)
	sum, carry2 = half_adder(right_sum, right_carry)
	carry = single_bit_or(carry1, carry2)
	
	return sum, carry
					
				
					
def full_adder(a, b, right_carry):
	'''
	Outputs:
	sum: right bit of a + b + right_carry
	carry: left bit of a + b + right_carry
	'''
	sum = single_bit_xor(a, b)
	carry = single_bit_and(a, b)

	return sum, carry

	right_sum, carry1 = half_adder(a, b)
	sum, carry2 = half_adder(right_sum, right_carry)
	carry = single_bit_or(carry1, carry2)
	
	return sum, carry
					
				

Time for a sixteen-bit adder...

via GIPHY

					
def sixteen_bit_adder(a16, b16):
	'''
	Outputs:
	sum: a sixteen-bit-sum of two numbers

	Discard the most significant carry bit. 
	'''
	sum = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

	sum[0], carry0 = half_adder(a[0], b[0])
	sum[1], carry1 = full_adder(a[1], b[1], carry0)
	sum[2], carry2 = full_adder(a[2], b[2], carry1)
	sum[3], carry3 = full_adder(a[3], b[3], carry2)
	sum[4], carry4 = full_adder(a[4], b[4], carry3)
	sum[5], carry5 = full_adder(a[5], b[5], carry4)
	sum[6], carry6 = full_adder(a[6], b[6], carry5)
	sum[7], carry7 = full_adder(a[7], b[7], carry6)
	sum[8], carry8 = full_adder(a[8], b[8], carry7)
	sum[9], carry9 = full_adder(a[9], b[9], carry8)
	sum[10], carry10 = full_adder(a[10], b[10], carry9)
	sum[11], carry11 = full_adder(a[11], b[11], carry10)
	sum[12], carry12 = full_adder(a[12], b[12], carry11)
	sum[13], carry13 = full_adder(a[13], b[13], carry12)
	sum[14], carry14 = full_adder(a[14], b[14], carry13)
	sum[15], carry15 = full_adder(a[15], b[15], carry14)

	return sum
					
				
					
>>> a = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0] # 36
>>> b = [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0] # 64
>>> a.reverse() # binary numbers go from right to left
>>> b.reverse() # python lists don't
>>> c = sixteen_bit_adder(a, b)
>>> c.reverse() 
>>> print(c) # 💯
					
				

Recap!

  • Single-bit OR
  • Single-bit NOT
  • Single-bit AND
  • Single-bit XOR
  • 16-bit Multiplexer
  • 16-bit bitwise NOT
  • 16-bit bitwise AND
  • A 16-bit adder

Recap!

Inputs: x, y - two 16-bit binary numbers
Control Bits: zx, nx, zy, ny, f, no
Outputs:
x + yx - yy - x01-1
xy-x-y!x!y
x + 1y + 1x - 1y - 1x & yx | y

Outputs: zr if output == 0, ng if output < 0

all right, let's do this.

  • if (zx == 1) set x = 0
  • if (nx == 1) set x = !x
  • if (zy == 1) set y = 0
  • if (ny == 1) set y = !y
  • if (f == 1) set out = x + y
  • if (f == 0) set out = x & y
  • if (no = 1) set out = !out
  • if (out == 0) set zr = 1
  • if (out < 0) set ng = 1
				
def alu(x16, y16, zx, nx, zy, ny, f, no):
	'''
	Inputs:

	x16, y16,  # 16-bit inputs        
    zx, # zero the x input?
    nx, # negate the x input?
    zy, # zero the y input?
    ny, # negate the y input?
    f,  # compute out = x + y (if 1) or x & y (if 0)
    no; # negate the out output?

    Outputs:
    out16 # 16-bit output
    zr # 1 if output is zero
    ng # 1 if output is negative 
    '''

    all_zeroes = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
    			
    		
				
def alu(x16, y16, zx, nx, zy, ny, f, no):
	...
    ### determine the X to use

    # zero the x if zx is set, else output incoming x
    zerox = sixteen_bit_mux(a16=x16, b16=all_zeroes, sel=zx)

    # not the x
    notx = sixteen_bit_not(x16)

    usex = sixteen_bit_mux(a16=zerox, b16=notx, sel=nx)
    			
    		
				
def alu(x16, y16, zx, nx, zy, ny, f, no):
	...
    ### determine the Y to use

    # zero the y if zy is set, else output incoming y
    zeroy = sixteen_bit_mux(a16=y16, b16=all_zeroes, sel=zy)

    # not the y
    noty = sixteen_bit_not(y16)

    usey = sixteen_bit_mux(a16=zeroy, b16=noty, sel=ny)
    			
    		
				
def alu(x16, y16, zx, nx, zy, ny, f, no):
	...
    ### compute the Fs

    addxy = sixteen_bit_adder(a16=usex, b16=usey)
    andxy = sixteen_bit_and(a16=usex, b16=usey)

    posout = sixteen_bit_mux(a16=addxy, b16=addxy, sel=f, out=posout)
    negout = sixteen_bit_not(posout)

    out16 = sixteen_bit_mux(a16=posout, b16=negout, sel=no)
    ng = out16[15]
    			
    		
				
def alu(x16, y16, zx, nx, zy, ny, f, no):
	...
    ### determine if output is zero
    ### out16 == all_zeroes
    c1 = single_bit_or(out16[0], out16[1])
    c2 = single_bit_or(out16[2], out16[3])
    c3 = single_bit_or(out16[4], out16[5])
    c4 = single_bit_or(out16[6], out16[7])
    c5 = single_bit_or(out16[8], out16[9])
    c6 = single_bit_or(out16[10], out16[11])
    c7 = single_bit_or(out16[12], out16[13])
    c8 = single_bit_or(out16[14], out16[15])

    c9 = single_bit_or(c1, c2)
    c10 = single_bit_or(c3, c4)
    c11 = single_bit_or(c5, c6)
    c12 = single_bit_or(c7, c8)
    c13 = single_bit_or(c9, c10)
    c14 = single_bit_or(c11, c12)
    check = single_bit_or(c13, c14)

    zr = single_bit_not(check)

    return out16, zr, ng
    			
    		
				
>>> a = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0] # 36
>>> b = [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0] # 64
>>> a.reverse()
>>> b.reverse()
>>> out, zr, ng = alu(a, b, 0, 0, 0, 0, 1, 0)
>>> print(out) # 💯
>>> print(zr, ng) # 0 0
    			
    		
zx nx zy ny f no f(x, y)
1 0 1 0 1 0 0
1 1 1 1 1 1 1
1 1 1 0 1 0 -1
0 0 1 1 0 0 x
1 1 0 0 0 0 y
0 0 1 1 0 1 !x
zx nx zy ny f no f(x, y)
1 1 0 0 0 1 !y
0 0 0 0 1 1 -x
1 1 0 0 1 1 -y
0 1 1 1 1 1 x+1
1 1 0 1 1 1 y+1
0 0 1 1 1 0 x-1
zx nx zy ny f no f(x, y)
1 1 0 0 1 0 y-1
0 0 0 0 1 0 x+y
0 1 0 0 1 1 x-y
0 0 0 1 1 1 y-x
0 0 0 0 0 0 x&y
0 1 0 1 0 1 x|y

Gracias!

Special thanks and credit to NAND2Tetris for teaching me ALUs and being the inspiration for much of this talk

/

#