Intro to CPU design [Part 6: Multiplexers and Demultiplexers] 12-24-2014, 09:14 PM
#1

If you have not already read part 5 of this series, PLEASE do so now.

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)

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:

And remember, 4 gates per chip, so the chip usage is:

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

Now, let's make a sum of products:

And then, Add in our inputs:

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:

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:

And continue, all the way down the line:

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:

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!

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

Code:

`OR :1`

AND:2

NOT:1

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)

)

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!