Muxtopia

My last post introduced the trivial but necessary “Not” chip. Before I move away from the first project I would like to mention one last chip that I found intriguing and especially difficult to solve. That chip is called a “Multiplexer” chip, or a “Mux” chip for short. This chip has a much more complicated specification than the “Not” chip.

A diagram of a multiplexer chip.

How it works

The mux chip has three inputs which I will refer to as ‘a’, ‘b’, and ‘sel’ short for selector. The mux chip also has just a singular output. The functionality that we want from this chip is when the ‘sel’ input is 0 the out should equal ‘a’. If ‘sel’ is 1 the output should equal ‘b’. Therefore from that information we can derive the following truth table.

 MUX CHIP TRUTH TABLE
| a | b | sel | out |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |

This is a more complicated table than the table that was generated from the “Not” chip. Because of this you probably won’t be able to come up with the solution just by looking at this table. You’ll need to break this information into chunks making it easier to digest.

Combinational Logic vs Sequential Logic

In order to break this problem down into chunks we must first understand the difference between these two forms of logic. As a programmer just about every problem we have faced has been sequential in nature. We apply filters that direct outcomes down different branches of logic. If we were to approach this chip with sequential logic it would look something like this:

1. if(sel ==0)
2. {return a;}
3. else
4. {return b;}

What makes this expressively sequential in nature is the fact that this logic has to be executed line by line, starting at the top and working towards the bottom. Therefore it has to have some sense of where it is currently and it also has to know where to go next. Essentially what is happening is the program starts at line one. If line one is true it will move to line two. If it is not true it will have to jump to line three. The problem with trying to build a low level chip with this type of logic is that we are working with voltage. Therefore for all intents and purposes there is not concept of time. Everything happens instantly. Well if sequential logic wont work then what do we need? This is where combinational Logic comes in to save the day.

Image of three differently colored discs.

These three discs are an excellent example of combinational logic. There is no sense of time or execution order. The color that you see is strictly based on the color or combination of colors that happen to overlap. So how can we take this logic and apply it to the mux chip? This is where we are forced to do some Boolean algebra. It’ll be fun though I promise.

Boolean Algebra

What is Boolean Algebra? Boolean Algebra is the a special kind of math that deals strictly with the numbers 0 and 1. Because the numbers have such a limited scope you will see that we can take complicated expressions and simplify them much more than would be expected.

First lets take another look at that truth table and see if we can pull out some useful info.

 MUX CHIP TRUTH TABLE
| a | b | sel | out |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |

What we need is some sort of formula that will match up with this truth table. The first thing you want to do when trying to derive a formula (or design a chip) from a truth table is to extract the scenarios where the output or result was equal to one. Doing that results in a far simpler table

 
| a | b | sel | out |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |

From here we can design a formula for each line. An easy way of thinking about is looking at a line’s inputs and then re-writing the variables to so that it works as a long “AND” statement. As we know an “AND” statement only returns true if both inputs are true so the first line would be converted into something like this:

So in this case we know that if we take the “NOT” of ‘a’ then “AND” that together with ‘b’ and ‘c’ we would get the desired out.The HDL for that would look like this:

If we were only given that one line the above chip would work perfectly. But there are actually three different scenarios where the output is also one. So how do we get a formula that defines each those occasions? We do the same thing as we did above but then we just “OR” those statements together. Like so:

As you can see this is getting somewhat unwieldy at this point. But I’ll still convert this as is into HDL to show that it works as is.

Sure enough if you put the above code into the compiler and run it against the tests it passes with flying colors. But something tells me we can simplify this chip quite a bit. So lets go back and write out the whole expression that we have discovered so far. If we try to make it a single statement it would look like this:

(Not(a) & b & sel) Or (a & NOT(b) & NOT(sel)) Or (a & b & NOT(sel)) Or (a & b & sel) 

“In Boolean Algebra to “AND” something is equivalent to multiplying it, because since the two numbers you are multiplying can only be a one or a zero the result of the multiplication can only be one if both numbers being multiplied are one. To “OR” something is equivalent to addition because similarly you will only get one if one of the numbers you are adding together is one. Lastly anywhere where you see a “NOT” you can replace it with a ‘-‘ symbol to make it easier to read. So lets re-write the above expression replacing the “AND” and “OR” operations with multiplication and addition as well as removing the all “NOT” operations.

(-absel)+(a-b-sel)+(ab-sel)+(absel)

If we look at the above formula you can see that there are several repeating factors that can be simplified. Lets start by removing ‘sel’ where ever possible.

(-abSEL)+(a-b-sel)+(ab-sel)+(abSEL)
sel(-ab+ab) + a-b-sel + ab-sel

It turns out we can simplify “sel(-ab+ab)” even more by factoring out the ‘b’

 
sel(-aB+aB) + a-b-sel + ab-sel
sel(b(-a+a)) + a-b-sel + ab- sel

Now we ended up with “-a + a”. Which will always equal one because if ‘a’ was equal to zero, then zero + NOT(zero) equals one and vice versa. Therefore we can simplify the expression even more.

sel(b(-a+a)) + a-b-sel + ab- sel 
sel(b(1)) + a-b-sel +ab-sel
sel(b) + a-b-sel+ab-sel

So now lets do the same thing but focusing on removing “-sel” where we can

sel(b) + a-b-SEL+ab-SEL 
sel(b) + -sel(A-b +Ab)
sel(b) + -sel(a(-b+b))
sel(b) + -sel(a(1))
sel(b) + -sel(a)

Just like that we have cut a huge expression down into something manageable. Now how do we convert this back into HDL? Lets remember that anywhere you see multiplication replace that with an “AND” anywhere you see a negative symbol replace that with a “NOT”. Anywhere you see an addition symbol replace that with an “OR”. Like this:

sel(b) + -sel(a)  

(sel & b) Or (NOT(sel) & a)

This is a much simpler expression which can be rewritten in HDL as follows.

An image of some HDL code

Now if you run through any of the values from the truth table above into this formula you will find that they all magically work. Thus a triumph in combinational logic has led us to the creation of the useful mux chip.


Leave a Comment