How to reduce an ALU logic with the minimum logic possible? Its very challenging

alucomputer-architecturedigital-logicvhdlvlsi

Our professor wants us to reduce 8-function ALU (8 outputs) to a 4 out ALU that has the capability to implement all the 8 functions. We can use any gates(even AOI's), muxes, and can create our control signals.
I am so stuck, my logic design works but I ended up using 5 inverts and 5 two-to-one muxes, I was told its too big. I am stuck now, I don't know how to approach this problem.

The functionality of the ALU (but ADD and SUBTRACT are not here, I am good with those);

enter image description here

This is the given logic circuit to implement, manipulate it to give out all the 5 logical functions i.e states (3 to 7) whose outputs should only exit the 3 outputs given because I already used one output for (add/sub). we basically have to get OR, NOR, XOR, XNOR, AND. no NAnd. The 's' and 'r' shouldn't be connected to the inverter, that was my error, they are the inputs to be operated

enter image description here

Best Answer

You didn't take my hint form your previous question: "Gate count can be reduced further by share logic with the gates inside the fulladder." To get the minimum gate count you need to look the full combination logic.

One of the best methods to simplify the logic and reduce the gate count is by using a Karnaugh map (also referred to as a K-map).

This is looks like a homework question, therefore I will not give the full solution. I may or may not have injected errors in the table/equation ;-)

The K-map should look like:

\ I[5:3]
 \  000 | 001 | 011 | 010 | 110 | 111 | 101 | 100
RS\_____|_____|_____|_____|_____|_____|_____|____
00|  0  |  0  |  0  |  0  |  0  |  1  |  0  |  0 
  |_____|_____|_____|_____|_____|_____|_____|____
01|  1  |  1  |  1  |  1  |  1  |  0  |  1  |  0 
  |_____|_____|_____|_____|_____|_____|_____|____
11|  0  |  0  |  1  |  0  |  0  |  1  |  0  |  1 
  |_____|_____|_____|_____|_____|_____|_____|____
10|  1  |  1  |  1  |  1  |  1  |  0  |  0  |  0 
  |_____|_____|_____|_____|_____|_____|_____|____

By pulling out the 1s expressions: $$ ALU= \bar{R} S \bar{I_5} + R \bar{S} \bar{I_5} + I_5 I_4 (I_3 \oplus S) + I_5 \bar{I_4} \bar{S} (I_3 \oplus R) + ... $$

If you want to reduce the transistor count, then apply De Morgan's Laws (aka Duality principle) and maximize the use of smaller gates (INV,NAND,NOR). For example every place you see an OR gate whose inputs are only AND gates then convert all to NAND. $$ AB+CD \equiv \overline{(\overline{AB}) (\overline{CD})} \\ 18 gates \rightarrow 12 gates $$

XORs are a little tricky to spot, so I'll point out: $$ \bar{R} S \bar{I_5} + R \bar{S} \bar{I_5} \equiv \bar{I_5} (R \oplus S) \\ 30 gates \rightarrow 16 gates $$

Related Topic