Combinational Logic Blocks

Data Multiplexors

1.3 Logic Gates

Multiple MUX can be combined together to get more way selection.

a --
   +--MUX----
b --   |    |
       ---  +--MUX--e
c --     |  |   |
   +--MUX----   |
d --   | |      |
       +--      |
       S0       S1

Arithmetic Logic Unit (ALU)

Most processors contain a special logic block called "Arithmetic Logic Unit" (ALU).

A simple version that does ADD, SUB, bitwise AND (&), bitwise OR (|)

  A     B
  |     |
  /32   /32
  |     |               when S=00, R=A+B
__v__ __v__             when S=01, R=A-B
\    V    /             when S=10, R=A&B
 \  ALU  /<---/---S     when S=11, R=A|B
  \_____/     2
     |
     /32
     |
     v
     R

Implementation

                   A     B
                   |     |
                   / 32  / 32
                   |     |
     --------------+--------------
     |       ------|-----+-------|------
     |       |     |     |       |     |
   +-----------+  +-------+     +-------+
S0>|  ADD/SUB  |  |  AND  |     |  O R  |
   +-|---|-----+  +---|---+     +---|---+
     |   |            / 32          / 32
     |   -----        |             |
     |       |        -----     -----
     v       |            |     |
  overflow   |          __v_____v__
             |          \ 0 MUX 1 /<----S0
             / 32        \_______/
             |               |
             |     -----------
		     |     |
		   __v_____v__
		   \ 0 MUX 1 /<-----------------S1
		    \_______/
		        |
		        / 32
		        |
		        v
		        R

• All operations done altogether
• Let MUX choose which one to output

Adder

2.2 Binary Addition

Full Adder (Alternative Implementation)

$$\begin{array}{rl}{s}_i& =\mathrm{XOR}(a_i,b_i,c_i)\\ c_{i+1}& =\mathrm{MAJ}(a_i,b_i,c_i)=a_i{b}_i+a_i{c}_i+b_i{c}_i\end{array}$$

• $\mathrm{MAJ}$ is the majority operator, where$$\mathrm{MAJ}(x_1,x_2,\cdots ,x_n)=\{\begin{array}{ll}1,& {\displaystyle \sum _{x_i=1}i>\sum _{x_j=0}j,}\\ 0& {\displaystyle \sum _{x_i=1}i\le \sum _{x_j=0}j.}\end{array}$$

Multibit Adder

Cascading n instances of 1-bit Full Adder

• Unsigned: Last carry $c_n$ is overflow bit
• Signed: $\mathrm{XOR}(c_n,c_{n-1})$ is overflow bit
  • No overflow: Last bit ${\bar{c}}_{in}{\bar{c}}_{out}$ or $c_{in}{c}_{out}$
  • Overflow: Either $c_{in}$ or $c_{out}$ is 1

Subtractor

$$A-B=A+(-B)=A+(\bar{B}+1)$$

• XOR serve as conditional inverter
  • x = 0, XOR(x, y) = y
  • x = 1, XOR(x, y) = -y
• One bit carry input into the LSB as $+1$

Final design: