4-way mux is a dick

classic Classic list List threaded Threaded
18 messages Options
Reply | Threaded
Open this post in threaded view
|

4-way mux is a dick

neekeri
How am I supposed to implement 4-way mux? I have done every other gate (except multiway dmux) fine using the truth-table -> boolean expression. With 4-way mux, should I draw the whole 64-line truth table, or is there an easier way, other than trial and error? I know you can implement 4-way mux using 3 muxe's, but how did we end in that conclusion?
Reply | Threaded
Open this post in threaded view
|

Re: 4-way mux is a dick

ybakos
Do you mean the Mux4Way16?

Think about this: there are two sel bits. A Mux16 has one sel bit.

If I gave you four things, and I wanted you to choose just one, imagine if I said "choose a and b or c and d first. Now choose the thing you want from either pair." As strange as I would sound, do you see how a Mux4Way16 must make its "decisions?"
Reply | Threaded
Open this post in threaded view
|

Re: 4-way mux is a dick

cadet1620
Administrator
In reply to this post by neekeri
neekeri wrote
How am I supposed to implement 4-way mux? I have done every other gate (except multiway dmux) fine using the truth-table -> boolean expression. With 4-way mux, should I draw the whole 64-line truth table, or is there an easier way, other than trial and error? I know you can implement 4-way mux using 3 muxe's, but how did we end in that conclusion?
You can implement 4-way mux from the truth table using canonical representation. There are 6 inputs, so the truth table will contain 2^6 = 64 rows and the canonical representation will be huge.


The 3 Muxes idea comes from binary decomposition.  Solve a larger problem by breaking it into two smaller problems. Solve each smaller problem by breaking it into two even smaller problems, etc.

It might help to think about Demux4Way first: SEL[1] routes IN to either group one or group 2. Then SEL[0] routes the signals in group 1 to either A or B and the signals in group 2 to either C or D. Mux4Way works the same way, only backwards.


Another approach is to think of And gates as having a data input and a control input. When the control input is True, the data can get through to the output; when the control is False, the data is blocked and the output is False.

You need the control signals that allow A, B, C and D to pass for the various select values. For instance the B control signal is True when SEL[1]=False and SEL[0]=True.

Since exactly one of the control signals is True for any select value, only one of the And gates' outputs will be passing a data signal and the other 3 will be False, so you can Or them together to get the final output.

--Mark
Reply | Threaded
Open this post in threaded view
|

Re: 4-way mux is a dick

ybakos
In reply to this post by neekeri
Also, Neekeri, draw this stuff on paper. I think you'll find it much easier to see.
Reply | Threaded
Open this post in threaded view
|

Re: 4-way mux is a dick

neekeri
In reply to this post by cadet1620
So, the only clever way is to use your brains. I was just worried that I didn't miss any formula
Reply | Threaded
Open this post in threaded view
|

Re: 4-way mux is a dick

neekeri
In reply to this post by neekeri
lol the shit got hard after the first chapter, way too hard
Reply | Threaded
Open this post in threaded view
|

Re: 4-way mux is a dick

ybakos
Keep working at it. I strongly recommend the book "CODE" by Charles Petzold. If you read the first thirteen chapters (they are short chapters) you'll find the shit is easier.
Reply | Threaded
Open this post in threaded view
|

Re: 4-way mux is a dick

gauze
I was just going to check on here to see if the solution to this one really required as many gates as it took me (80). :S
Reply | Threaded
Open this post in threaded view
|

Re: 4-way mux is a dick

cadet1620
Administrator
gauze wrote
I was just going to check on here to see if the solution to this one really required as many gates as it took me (80). :S
Just to be clear: the goal with Nand2Tetris is not to build your gates from Nands; the goal is to learn abstraction -- how to use the parts that you have already built to design more complex parts. The Hack Computer would require millions of Nands.

For Mux4Way16, the best solution from an abstraction point of view requires only 3 Mux16s.

Feel free to email me if you would like some more direct help in finding this 3 mux solution.

--Mark
 
Reply | Threaded
Open this post in threaded view
|

Re: 4-way mux is a dick

gauze
oh I should probably go back and refactor mux16 etc then
Reply | Threaded
Open this post in threaded view
|

Re: 4-way mux is a dick

cadet1620
Administrator
gauze wrote
oh I should probably go back and refactor mux16 etc then
Don't spend too much time reworking chips that you've already got working.  Just start applying more abstraction on the next chips you do.

Try to find a solution for Mux8Way16 that uses 2 Mux4Way16s and a Mux16.

As for too many Nand gates, check out this post and its sequel.

--Mark
Reply | Threaded
Open this post in threaded view
|

Re: 4-way mux is a dick

gauze
thanks for the links and the tips on building X gate from Y parts.
if you haven't seen it look up NandPuter, this guy I know on IRC built it, it's a lot of wires and 7400 ttls
Reply | Threaded
Open this post in threaded view
|

Re: 4-way mux is a dick

cadet1620
Administrator
This post was updated on .
gauze wrote
thanks for the links and the tips on building X gate from Y parts.
if you haven't seen it look up NandPuter, this guy I know on IRC built it, it's a lot of wires and 7400 ttls
Wow, he sure did that the hard way. It looks like he didn't use any of the TTL parts except N-input Nand gates. This is another excellent example of the advantage of abstraction and encapsulation.

For example his 16-bit program counter requires 2 PC boards and about 120 ICs.  He could have used 4 74LS161 4-bit counters with load and clear (basically 1/4 of a Hack PC) and 2 74LS244 8-bit bus drivers if he needed additional fanout.

--Mark
Reply | Threaded
Open this post in threaded view
|

Re: 4-way mux is a dick

bellis
In reply to this post by ybakos
I think my biggest issue is understanding how to use hdl.  I'm reading the book "code" as a suplement and whenever I look at what the gates are supposed to do, I completely get it.  The truths tables all make sense, but whenever I go to build the gates I get completely lost with the language.  I've studied the appendix and survival guide...It makes no sense to me.  Trying to get through 4wayMux16 now...not even sure how I got through the others.


Reply | Threaded
Open this post in threaded view
|

Re: 4-way mux is a dick

cadet1620
Administrator
This post was updated on .
For more complex circuits, I find it helps to draw out the circuit and label all the chip I/O's (IN and OUT statements), and the I/O's in every part used in the circuit. Also assign names to the internal wires that connect the parts.

Example:
    CHIP Foo {
        IN q, r, s, t[2];
        OUT x, y;
    PARTS:
        ...
    }
I don't know what the Foo part is good for, but here's its circuit diagram:
Foo circuit diagram
The left side of the '=' is fixed for all parts; it must match that part's IN and OUT declaration. That means that the Foo chip's parts section will look like:
    PARTS:
        And (a=___, b=___, out=___);
        Or (a=___, b=___, out=___);
        Xor (a=___, b=___, out=___);
        Mux (a=___, b=___, sel=___, out=___);
        Mux (a=___, b=___, sel=___, out=___);
(The order of the Part lines, and the order of the connections in each part line, does not matter since HDL is just a description of the schematic diagram.)

Now all you need to do is fill in the blanks.
    CHIP Foo {
        IN q, r, s, t[2];
        OUT x, y;
    PARTS:
        And (a=q, b=r, out=f);
        Or (a=r, b=s, out=g);
        Xor (a=q, b=s, out=h);
        Mux (a=f, b=g, sel=t[0], out=x);
        Mux (a=q, b=h, sel=t[1], out=y);
    }

It often helps to mark the wires on your drawing as you make the connections since the Chip I/O's normally use similar names to the Part I/O pins.

(To help avoid confusion, I intentionally used non-conflicting pin names in the above example.  If Chip Foo's I/O's were the normal a, b, c, sel and out, it would have looked like this:)
    CHIP Foo {
        IN a, b, c, sel[2];
        OUT out, other;
    PARTS:
        And (a=a, b=b, out=f);
        Or (a=b, b=c, out=g);
        Xor (a=a, b=c, out=h);
        Mux (a=f, b=g, sel=sel[0], out=out);
        Mux (a=a, b=h, sel=sel[1], out=other);
    }

If you want specific help with Mux4Way16, or more help with HDL in general, email me directly.

--Mark

Reply | Threaded
Open this post in threaded view
|

Re: 4-way mux is a dick

Jack Draak
Just to add a couple cents to the discussion... I was trying to solve my Mux4Way with K-maps and Boolean Algebra, and the best I was coming up with was a moderately complex design modeled directly on the equation (or some variation of it) --

out = a.s1'.s2' + b.s1'.s2 + c.s1.s2' + d.s1.s2

So, literally 3 Or chips, 2 Inverters, and 8 And chips.  

It's interesting, to me, how different ways of trying to solve these problem sets come up with solutions that can be so divergent in form. After completing the first 6 sections, I've gone back and re-worked this and a couple other chips. This one dropped from 27 Nand to 12 in my re-design. I understand "fewest gates" or "fewest Nand's" isn't always the "best" design, but going from 13 gates to 3 while also eliminating so many Nand's feels like a win. It certainly makes the HDL more "readable", a not insubstantial consideration, methinks.
Reply | Threaded
Open this post in threaded view
|

Re: 4-way mux is a dick

xedover
I've only just learned Boolean Algebra myself, though that part is not so hard, but K-maps are super confusing... I find it easier to just work straight off the truth tables. Simplification of the equations is another story though.

But I totally agree with cadet1620... draw the circuit out. That helped me more than anything. Yeah, the Mux4Way was kinda tricky, but a lot easier once I drew the circuit on paper (or a whiteboard). The DMux was a lot tougher for me (until I got to the ALU and CPU -- the CPU was the only one I had to actually ask for help on)
Reply | Threaded
Open this post in threaded view
|

Re: 4-way mux is a dick

MultiplexorMan
In reply to this post by cadet1620
@Cadet1620
Thanks for the idea to build the Mux8way16 chip using two Mux4way16's and one Mux16. I was on such a rush solving these problems I built my Mux8way16 using seven Mux16's.