chevron_left chevron_right

• 0 Vote(s) - 0 Average

 Tutorial Intro to CPU design [Part 6: Multiplexers and Demultiplexers] filter_list Linear Mode Threaded Mode View a Printable Version Author Message
Intro to CPU design [Part 6: Multiplexers and Demultiplexers] #1

Okay, this is where things get a little bit more advanced. If we want to read and write, we are going to want to keep our cost down and the number of wires we have to run low. How can we read from 64 different bits but only use 4 of them? Simple! We use a multiplexer.

What is a multiplexer? @JzJad posted this below, and I think it describes it pretty well:

Theory
Multiplexers take all of the possible inputs, with additional select inputs, and output only the desired outputs.

Formulas:
Alright, let's make a basic 4-bit multiplexer. The formulas get long.
Inputs:
A, B, C, D
Selects:
S0, S1 (in the order S0S1)

Outputs:
Q (selected bit)

Table: (for the table, G=S0, H=S1)
Code:
```G|H|Q 0|0|A 0|1|B 1|0|C 1|1|D```

Seems simple enough.
G=S0, H=S1
Q=(AG'H')+(BGH')+(CG'H)+(DGH)

It looks pretty complicated, bit it is not. We can do a simple sum of products for this:

G'H' = 00
G'H = 01
GH' = 10
GH = 11

And then, just assign which numbers we want to each select by adding in the inputs:

G'H'A = 00
G'HB = 01
GH'C = 10
GHD = 11

And there you have it. Now simply or them all together and we have
(AG'H')+(BGH')+(CG'H)+(DGH)

This is close enough to simplest form. Now, let's figure out how much waste we have. Remember, we only use gates that take two inputs, and we have 4 that need 3 and 1 that needs 4. So we need to rewrite it:

((A(G'H'))+(B(GH')))+((C(G'H))+(D(GH)))
Okay, so lets make the tally:
Code:
```OR  :3 AND:8 NOT:4```
And remember, 4 gates per chip, so the chip usage is:
Code:
```OR  :1 AND:2 NOT:1```
And the waste is 1 OR gate. That is actually pretty good. We used 4 chips for this multiplexer.

Now, we will be using multiplexers that take a 4-bit select, and take in 64 other bits. How do we do that? Simple. We take n=64/4=16. That is the number of bits each multiplexer has to take in, and we need 4 of those (one for each bit).

Inputs:
a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p
Selects:
A, B, C, D
Outputs:
Q
Code:
```ABCDQ 0000a 0001b 0010c 0011d 0100e 0101f 0110g 0111h 1000i 1001j 1010k 1011l 1100m 1101n 1110o 1111p```

Now, let's make a sum of products:
Code:
```Q = (A'B'C'D') + (A'B'C'D) + (A'B'CD') + (A'B'CD) + (A'BC'D') + (A'BC'D) + (A'BCD') + (A'BCD) + (AB'C'D') + (AB'C'D) + (AB'CD') + (AB'CD) + (ABC'D') + (ABC'D) + (ABCD') + (ABCD)```

And then, Add in our inputs:

Code:
```Q = (aA'B'C'D') + (bA'B'C'D) + (cA'B'CD') + (dA'B'CD) + (eA'BC'D') + (fA'BC'D) + (gA'BCD') + (hA'BCD) + (iAB'C'D') + (jAB'C'D) + (kAB'CD') + (lAB'CD) + (mABC'D') + (nABC'D) + (oABCD') + (pABCD)```

Now, that is in NO way simplified... So, we can take out some of the work by first splitting it into two groups: Aset and Aunset. Aunset is from a-h inclusive, and Aset is from i-p inclusive.

We can then factor out an A' from Aset and an A from Aunset:
Code:
```Q = A'(   (aB'C'D') +   (bB'C'D) +   (cB'CD') +   (dB'CD) +   (eBC'D') +   (fBC'D) +   (gBCD') +   (hBCD) ) + A(   (iB'C'D') +   (jB'C'D) +   (kB'CD') +   (lB'CD) +   (mBC'D') +   (nBC'D) +   (oBCD') +   (pBCD) )```
Look, getting better already. Let's go ahead and re-order Aset and Aunset so that we group them both into Bset and Bunset the same way:

Code:
```Q = A'(   B'(     (aC'D') +     (bC'D) +     (cCD') +     (dCD)   )   +   B(     (eC'D') +     (fC'D) +     (gCD') +     (hCD)   ) ) + A(   B'(     (iC'D') +     (jC'D) +     (kCD') +     (lCD)   )   +   B(     (mC'D') +     (nC'D) +     (oCD') +     (pCD)   ) )```

And continue, all the way down the line:

Code:
```Q = A'(   B'(     C'(       (aD') +       (bD)     ) + C(       (cD') +       (dD)     )   ) + B(     C'(       (eD') +       (fD)     ) + C(       (gD') +       (hD)     )   ) ) + A(   B'(     C'(       (iD') +       (jD)     ) + C(       (kD') +       (lD)     )   ) + B(     C'(       (mD') +       (nD)     ) + C(       (oD') +       (pD)     )   ) )```

Okay, but now it is looking pretty messy. Just keep swimming.. Simplifying the equation will save our costs later. At this point though, it cannot be simplified any further. We can now do some equation compression:

Code:
```Q = A'(B'(C'((aD') + (bD)) + C((cD') + (dD))) + B(C'((eD') + (fD)) + C((gD') + (hD)))) + A(B'(C'((iD') + (jD)) + C((kD') + (lD) )) + B(C'((mD') + (nD)) + C((oD') + (pD))))```

Yeah, doesn't that look pretty! But, there you have it, the equations for the multiplexer that we will actually be using. We will name that block 16MUX. And we will use 4 16MUX's in each memory block, and then we will use the 4-bit multiplexer from the beginning of this thread as 4MUX. We might not ever use that, but who knows.

Demultiplexer: theory
Demultiplexers will take the outputs and determine the select lines. I won't go into any more depth on those, we won't be using them as far as I know in this tutorial.

Well, there you have it! We can start putting some of the components together in part 7!

RE: Intro to CPU design [Part 6: Multiplexers and Demultiplexers] #2
I was waiting for this part.... just for this joke, I'd assume you find it quit comical.
http://wisevishvesh.files.wordpress.com/...plexer.jpg

RE: Intro to CPU design [Part 6: Multiplexers and Demultiplexers] #3
Ahh, that is actually pretty amusing. If you want sexy, draw me a 7-segment display controller using ONLY LS7402 chips (NOR gates) and minimize the waste.

@JzJad I hope you don't mind, but I am going to use that in the tutorial. I love it.

Users browsing this thread: 1 Guest(s)