The ALU, the swiss knife of every cpu
Today the author wants to introduce an important part of every cpu: The arithmetic logic unit (ALU), we already know about some functions presented in the blog posts before. In this post we want to close the gaps systematically. Time for a short recap: The logic functions 'and','or','not' and 'xor' were introduced, also the arithmetic functions 'add' and 'sub' for integers were shown. Now we want to build most of those functionalities in one unit, the 1bit alu cell.
Function  description  Ainvert  Binvert  Operation 

and 
a & b 
0 
0 
00 
or 
a  b 
0 
0 
01 
add 
a + b 
0 
0 
10 
sub 
a  b 
0 
1 
10 
slt 
a < b 
0 
1 
11 
nor 
a nor b 
1 
1 
00 
nand 
a nand b 
1 
1 
01 
A 1bit ALU cell
To keep things simple we implement an ALU for 1 bit, which then can be adapted to every bitwidth simply by repitition. We introduce an implementation designed by Hennessey and Peterson, quoted from the popular book Computer Organization and Design (RISCV) Edition by Hennessey and Patterson.
The implementation will support the fundamental operations 'and','or', 'add' and 'sub'. As we already learned the subtraction can be realised two’s complement: Inverting the input B and setting the carryin to one.
Construct an nbit ALU
The 1bit ALUcell we created in the first section, can be chained to an nbit widthalu. The last ALUcell in the chain, differs a bit from the regular cell as it also includes an overflowdetection circuit. We will get to it later in the article.
Setlessthan
We want the complete ALU to support another fundamental instruction setlessthan (slt), necessary to allow branchoperations later on. For this operation the addional input 'less' is designed. So the ALU supports an instruction that in C looks like:
(a < b)? 1 : 0
This can be simply implemented by subtracting b from a, and testing if the value is less than zero. In the implementation, every alucell in the chain but the leastsignificantbit, gets a zero on the 'less' input. The first alucell gets the result of the last one, which is representing the mostsignificantbit. As the msb also represents the sign bit, we can simply route as input to the leastsignificant and we are done. This is  however  not true, in case the subtraction might result in an overflow.
Also, we add a norgate with inputs from all result bits to detect zero.
Overflow Detection
The last 1bit ALU cell in the chain has another output 'overflow', to indicate an overflow of the addition of two integer values. The encourages the inclined reader to derive the truth table and circuit as an exercise.
For a two’s complement interpretation overflow occurs in two cases:

Two positive numbers are added, the result becomes negative

Two negative number are added, the result becomes positive
The truth table for overflow is as follows (original source can be found here)
Binv  a(n1)  b(n1)  c(n1)  OF 

0 
0 
0 
0 
0 
0 
0 
0 
1 
1 
0 
0 
1 
0 
0 
0 
0 
1 
1 
0 
0 
1 
0 
0 
0 
0 
1 
0 
1 
0 
0 
1 
1 
0 
1 
0 
1 
1 
1 
0 
1 
0 
0 
0 
0 
1 
0 
0 
1 
0 
1 
0 
1 
0 
0 
1 
0 
1 
1 
1 
1 
1 
0 
0 
1 
1 
1 
0 
1 
0 
1 
1 
1 
0 
0 
1 
1 
1 
1 
0 
The circuit generated by Logisim is accordingly:
Multiplexer & Demultiplexer
To select one line out of multiple sources we need another key component, the multiplexer. We can find multiplexer in multiple places, however in an ALU it used to select one of the logic or arithmetic operations, we will see that later.
The demultiplexer as the name suggest does the exact opposite task and distributes signal on one line (input) to one of multiple outputs, depending on the selection bit(s).
Multiplexer in complementary PassTransistor Logic
We show and implement the multiplexer in passtransistorlogic, as this is the most resourceefficient design…