teaching machines

CS 352 Lecture 9 – Muxes, Demuxes, and HDL

September 26, 2016 by Chris Johnson. Filed under cs352, fall 2016, lectures.

Dear students,

We introduce today a couple of hardware components that will ultimately help us build memory. They are the multiplexer (or mux) and the demultiplexer (or demux). The mux takes in two inputs and a selector. The selector determines which of the two inputs feeds into the one output:

if sel == 0
  output a
else
  output b

Can we design a hardware component that supports this out of the simpler components we’ve already seen? Let’s construct a truth table and see:

Let’s build a Karnaugh map to minimize the logic. We end up with a && !sel || b && sel. Let’s build this in Logicly and verify that it does what we want! We’ll also package it up into an integrated circuit, so that we can operate at a higher level of abstraction.

The mux behaves like the ternary operator for bits: (sel ? b : a).

The demux operates in an inverse fashion. It takes in an input and a selector. It has two outputs. The selector chooses which output gets the input, with the other getting set to 0:

if sel == 0
  a = input
  b = 0
else
  a = 0
  b = input

Can we build this one of out of simpler components?

We don’t need a Karnaugh map here. Inspection shows that a = in && !sel and b = in && sel. Let’s build this one in Logicly as well.

To keep these two straight in your head, you can remember that muxes select an input and demuxes select an output.

It’ll be a bit before we have all the pieces to make a complete memory system, but we can get an idea for it by hardcoding a ROM. We’ll start with a 2 bit ROM, and then expand it to 4.

We’ve been using truth tables, boolean expressions, Karnaugh maps, and schematics to represent our hardware designs. These are useful on a small scale, but when our friends at Intel or Cray are designing a supercomputer, what do they use? Some sort of hardware description language (HDL). Hardware is designed first in software, using a declarative programming language. Two HDLs are in popular use: VHDL and Verilog. We will use neither. Instead, the authors of our textbook have designed one that conveys all the ideas that are important to us as computer scientists. Let’s see an example:

/*
 * This is the syntax of a chip in the textbook's HDL.
 * Another name for this chip is Buffer.
 */
CHIP DoubleNegater {
  // Use as many inputs as you need. Same with outputs.
  IN in;
  OUT out;

  PARTS:
  Not(in=in, out=notIn);
  Not(in=notIn, out=out);
}

Your next homework involves writing descriptions of hardware components like And, Or, Not, Xor, Mux, DMux, and so on. Let’s write a few of these together:

• Buffer/DoubleNegater
• And3
• Nor
• Shift
• Rotate

Here’s your TODO list:

• Fix any issues you had with the first homework and re-push before Wednesday.
• Read chapter 1 of your textbook, which essentially is the specification for homework 2. On a 1/4 sheet, write the HDL for the And chip using only two component parts.
• Start homework 2, which is due before Thursday, October 13.

See you next class!

Sincerely,

P.S. Here’s the code we wrote together in class…

Buffer.hdl

CHIP Buffer {
  IN in;
  OUT out;

  PARTS:
  Not(in=in, out=notIn);
  Not(in=notIn, out=out);
}

And3.hdl

CHIP And3 {
  IN a, b, c;
  OUT out;

  PARTS:
  And(a=a, b=b, out=aAndB);
  And(a=aAndB, b=c, out=out);
}

ShiftNibble.hdl

CHIP ShiftNibble {
  IN in[4]; 
  OUT out[4];

  PARTS:
  Buffer(in=in[1], out=out[0]);
  Buffer(in=in[2], out=out[1]);
  Buffer(in=in[3], out=out[2]);
}