AND, And16, OR, NOT, Not16, XOR, Or16, Or8way, Mux, Mux16, Mux4Way16, Mux8Way16, DMux, DMux4Way, DMux8way.
Given a set of inputs either a 1 or 0, each chip has to produce an output based on the input. For example the NOT gate if given a 1 has to output a 0. For the AND gate if given two 1s then the output will be 1. Every other combination should produce a 0. For example 1 - 0 would output a 0. Each chip as their own outputs and each chip usually uses the chip made before it to acheive the end results.
Using the hardware emulator provided and a language called HDL(Hardware descriptive language) I was able to successfully produce all the required chips.
The NAND chip will produce a 0 only if both inputs are 1. Otherwise it will output a 1. Its function looks like: If a=b=1 then out = 0 else out=1
First chip I created was the NOT gate, also known as the converter. This is a single input chip and is used to flip the bit from a 1 to a 0 or a 0 to a 1. The function looks like this "If in = 0 then out = 1 else out=0. Completed this by "soldering" the a and b inputs of the NAND gate together. After each chip configuration the chip was loaded into the hardware simulator to test every possible input yields the desired output. In HDL it looks like this:
CHIP Not {
IN in;
OUT out;
PARTS:
Nand(a=in, b=in, out=out);
}
Next was the AND gate. The function is:
If a=b=1 then out =1 else out=0
Since this is the opposite of a NAND gate this is achieved by simply swapping the output of the NAND gate by attaching the NOT gate to the output of the NAND gate.
CHIP And {
IN a, b;
OUT out;
PARTS:
Nand(a=a, b=b, out=w1);
Not(in=w1, out=out);
}
OR The Or function returns 1 when at least one of its inputs is 1, and 0 otherwise. The OR gate was achieved using 2 NOT gates and a NAND:
CHIP Or {
IN a, b;
OUT out;
PARTS:
Not(in=a, out=nota);
Not(in=b, out=notb);
Nand(a=nota, b=notb, out=out);
}
Xor The Xor function, also known as “exclusive or,” returns 1 when its two inputs have opposing values, and 0 otherwise. For this I had to learn something called canonical expression. Basically this means getting a list of the possible inputs and outputs. also known as a "Truth table" and listing out all the combinations of the outputs that resulted in a 1. This technique is called "Product of sums". The truth table for a XOR gate is:
| a | b | out |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Calculating the Product of sums:
| a | b | out |
| 0 | 0 | 0 |
| 0 | 1 | 1 | ('a b)
| 1 | 0 | 1 | (a 'b)
| 1 | 1 | 0 |
'a means notA as 0 does not equal the output of 1. This shows that we need to use 2 AND gates and OR them together using a NOT gate for the inputs that are notA. The full expression looks like:
('ab) + (a'b)
In english: (notA b) + (a notB).
CHIP Xor {
IN a, b;
OUT out;
PARTS:
And(a=nota, b=b, out=w1);
Not(in=a, out=nota);
And(a=a, b=notb, out=w2);
Not(in=b, out=notb);
Or(a=w1, b=w2, out=out);
}
The Multiplexer took some learning how to shrink down the canonical expression to a smaller equation. The Mux chip takes 3 inputs and has 1 output. Its truth table is:
| a | b | sel | out |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Using the Product of sums we get the canonical expression of:
('a b sel) + (a 'b 'sel) + (a b 'sel) + (a b sel)
Using 4 AND gates all ORed together is a lot of chips and this is why it should be shrunk down to yield the smallest amount possible. To shink it down I learnt a teqnique called "karnaugh maps".
http://en.wikipedia.org/wiki/Karnaugh_map
http://en.wikipedia.org/wiki/Karnaugh_map
Using the karnaugh map I was able to get the expression down to:
(a 'sel) + (b sel)
So 2 AND gates ORed together and a NOT gate.
(a 'sel) + (b sel)
So 2 AND gates ORed together and a NOT gate.
CHIP Mux {
IN a, b, sel;
OUT out;
PARTS:
And(a=a, b=notb, out=w1);
And(a=b, b=sel, out=w2);
Not(in=sel, out=notb);
Or(a=w1, b=w2, out=out);
}
IN a, b, sel;
OUT out;
PARTS:
And(a=a, b=notb, out=w1);
And(a=b, b=sel, out=w2);
Not(in=sel, out=notb);
Or(a=w1, b=w2, out=out);
}
The DMux chip was a pain to figure out but eventually figured out that as it has 2 outputs and 2 inputs I simply split the truth table into 2.
| in | sel | a | b |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Split into 2:
| in | sel | a |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
| in | sel | b |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Using canonical expression on both of the tables it resulted in the below config:
CHIP DMux {
IN in, sel;
OUT a, b;
PARTS:
And(a=in, b=notb, out=a);
And(a=in, b=sel, out=b);
Not(in=sel, out=notb);
}
Not16 chip was completed by simply using 16 Not chips to create a 16bit NOT chip:
CHIP Not16 {
IN in[16];
OUT out[16];
PARTS:
Not(in=in[0], out=out[0]);
Not(in=in[1], out=out[1]);
Not(in=in[2], out=out[2]);
Not(in=in[3], out=out[3]);
Not(in=in[4], out=out[4]);
Not(in=in[5], out=out[5]);
Not(in=in[6], out=out[6]);
Not(in=in[7], out=out[7]);
Not(in=in[8], out=out[8]);
Not(in=in[9], out=out[9]);
Not(in=in[10], out=out[10]);
Not(in=in[11], out=out[11]);
Not(in=in[12], out=out[12]);
Not(in=in[13], out=out[13]);
Not(in=in[14], out=out[14]);
Not(in=in[15], out=out[15]);
}
The AND16 chip was the exact same technique:
CHIP And16 {
IN a[16], b[16];
OUT out[16];
PARTS:
And(a=a[0], b=b[0], out=out[0]);
And(a=a[1], b=b[1], out=out[1]);
And(a=a[2], b=b[2], out=out[2]);
And(a=a[3], b=b[3], out=out[3]);
And(a=a[4], b=b[4], out=out[4]);
And(a=a[5], b=b[5], out=out[5]);
And(a=a[6], b=b[6], out=out[6]);
And(a=a[7], b=b[7], out=out[7]);
And(a=a[8], b=b[8], out=out[8]);
And(a=a[9], b=b[9], out=out[9]);
And(a=a[10], b=b[10], out=out[10]);
And(a=a[11], b=b[11], out=out[11]);
And(a=a[12], b=b[12], out=out[12]);
And(a=a[13], b=b[13], out=out[13]);
And(a=a[14], b=b[14], out=out[14]);
And(a=a[15], b=b[15], out=out[15]);
}
OR 16 used the exact same method:
CHIP Or16 {
IN a[16], b[16];
OUT out[16];
PARTS:
Or(a=a[0], b=b[0], out=out[0]);
Or(a=a[1], b=b[1], out=out[1]);
Or(a=a[2], b=b[2], out=out[2]);
Or(a=a[3], b=b[3], out=out[3]);
Or(a=a[4], b=b[4], out=out[4]);
Or(a=a[5], b=b[5], out=out[5]);
Or(a=a[6], b=b[6], out=out[6]);
Or(a=a[7], b=b[7], out=out[7]);
Or(a=a[8], b=b[8], out=out[8]);
Or(a=a[9], b=b[9], out=out[9]);
Or(a=a[10], b=b[10], out=out[10]);
Or(a=a[11], b=b[11], out=out[11]);
Or(a=a[12], b=b[12], out=out[12]);
Or(a=a[13], b=b[13], out=out[13]);
Or(a=a[14], b=b[14], out=out[14]);
Or(a=a[15], b=b[15], out=out[15]);
}
Same thing for the Mux16
CHIP Mux16 {
IN a[16], b[16], sel;
OUT out[16];
PARTS:
Mux(a=a[0], b=b[0], sel=sel, out=out[0]);
Mux(a=a[1], b=b[1], sel=sel, out=out[1]);
Mux(a=a[2], b=b[2], sel=sel, out=out[2]);
Mux(a=a[3], b=b[3], sel=sel, out=out[3]);
Mux(a=a[4], b=b[4], sel=sel, out=out[4]);
Mux(a=a[5], b=b[5], sel=sel, out=out[5]);
Mux(a=a[6], b=b[6], sel=sel, out=out[6]);
Mux(a=a[7], b=b[7], sel=sel, out=out[7]);
Mux(a=a[8], b=b[8], sel=sel, out=out[8]);
Mux(a=a[9], b=b[9], sel=sel, out=out[9]);
Mux(a=a[10], b=b[10], sel=sel, out=out[10]);
Mux(a=a[11], b=b[11], sel=sel, out=out[11]);
Mux(a=a[12], b=b[12], sel=sel, out=out[12]);
Mux(a=a[13], b=b[13], sel=sel, out=out[13]);
Mux(a=a[14], b=b[14], sel=sel, out=out[14]);
Mux(a=a[15], b=b[15], sel=sel, out=out[15]);
}
The OR8way chip has 8 inputs and only 1 output. I chained a bunch of ORs together to get this working:
CHIP Or8Way {
IN in[8];
OUT out;
PARTS:
Or(a=in[0], b=in[1], out=w1);
Or(a=in[2], b=in[3], out=w2);
Or(a=in[4], b=in[5], out=w3);
Or(a=in[6], b=in[7], out=w4);
Or(a=w1, b=w2, out=w5);
Or(a=w2, b=w3, out=w6);
Or(a=w3, b=w4, out=w7);
Or(a=w5, b=w6, out=w8);
Or(a=w6, b=w7, out=w9);
Or(a=w8, b=w9, out=out);
}
The Mux 4 way 16 bit chip takes 5 inputs and one 16bit output. Things started getting really tricky here but I got this working using only 3 Mux16 chips created earlier:
CHIP Mux4Way16 {
IN a[16], b[16], c[16], d[16], sel[2];
OUT out[16];
PARTS:
Mux16(a=a, b=b, sel=sel[0], out=w1);
Mux16(a=c, b=d, sel=sel[0], out=w2);
Mux16(a=w1, b=w2, sel=sel[1], out=out);
}
After this point the logic of building ontop of smaller chips started to sink in and the rest came about quite easily:
Mux 8 way 16 is the same principle as the last except now I can use the Mux4way and the Mux16 to create the Mux8way:
CHIP Mux8Way16 {
IN a[16], b[16], c[16], d[16],
e[16], f[16], g[16], h[16],
sel[3];
OUT out[16];
PARTS:
Mux4Way16(a=a, b=b, c=c, d=d, sel[0..1]=sel[0..1], out=w1);
Mux4Way16(a=e, b=f, c=g, d=h, sel[0..1]=sel[0..1], out=w2);
Mux16(a=w1, b=w2, sel=sel[2], out=out);
}
The last two chips are the DMux4way and the DMux 8Way. Both use the same logic as all the other chips so it was quite easy to figure it out using the same principles. It did take some playing around though just to get it perfect:
CHIP DMux4Way {
IN in, sel[2];
OUT a, b, c, d;
PARTS:
DMux(in=in, a=nota, sel=sel[1], b=notb);
DMux(in=nota, sel=sel[0], a=a, b=b);
DMux(in=notb, sel=sel[0], a=c, b=d);
}
CHIP DMux8Way {
IN in, sel[3];
OUT a, b, c, d, e, f, g, h;
PARTS:
DMux(in=in, a=nota, b=notb, sel=sel[2]);
DMux4Way(in=nota, a=a, b=b, c=c, d=d, sel[0..1]=sel[0..1]);
DMux4Way(in=notb, a=e, b=f, c=g, d=h, sel[0..1]=sel[0..1]);
}
That is the end of Chapter 1. At first look this seemed like an impossible task but slowly searching the Internet and using YouTube videos and the forum provided for students it all started making sense. Im not sure how im going to go with the rest of the course as this definitely challenged me but with enough persistence im sure I can get through the rest...
