[phyrrus9]

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)

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!

[JzJad]

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

[phyrrus9]

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.