CSC 221 - Computer Logic and Organization

The Breadboard Kit and Class Project

Introduction

I recommend highly that you watch this intro video about how breadboards work, before you begin.  And, this video is a great set of hints for managing wire stripping and using a breadboard accurately.

Working on real hardware is an experience for which there is no substitute.  Nowadays, most hardware design uses software and various languages like VHDL, which effectively turn hardware design into programming.  Nonetheless, despite the bugs and challenges that come with real electronics, it is more fun to work with hardware.  And, in a liberal arts CS major, it is this class, or never, for hardware.  To have a chance for success with this project, you absolutely must work on it regularly and steadily throughout the semester.  It is routine for a tricky bug to linger for days or weeks.  There are five stages to complete, and the kit will make more and more sense as we progress with theory in class.  You should be finished with Stage 4 with at least 2-3 weeks to go, in order to have a chance to finish Stage 5.  There will be a 10 point short answer question on the final about your kit, so all the effort you put in will be worth it whether or not you finish.

Your project kit comes with a power supply, wires, integrated circuit (IC) chips, resistors, capacitors, LEDs, and a "breadboard" in which to insert these components.  A breadboard is a device with holes and channels allowing easy connection of wires to chips.  I will show how it all works in class.  Your group is responsible for the equipment that you use, and you must return it at the end of the semester exactly as you received it.  Damaged or lost kits will set you back $200; be responsible.   If anything gets broken, let me know, throw at the broken piece and I will give you a replacement.  Leave a post-it with any warnings if you find a defective breadboard or break a wire off in some pin, so that the next person who inherits your kit does not suffer.

Your project kit leads you through the design of a very simple computer.  The computer is very simple in function.  It has a simple ALU that just increments;  it uses RAM only for instructions, not for data;  it has two registers A and B to store data; and it has a mere four instructions: INCA, INCB, MOVAB, and MOVBA.  (Some of your kits include other instructions - but you do not need to implement these). Indeed, the computer kit does not have the power to do if-statements, loops, input/output, or use RAM for data.  Nonetheless, despite the simplicity of this machine, you will find debugging each stage a challenge, and you should plan to leave plenty of time for slow and steady progress.  Besides your own careless wiring errors or misunderstandings, there are also more difficult problems to debug such as breadboard defects, broken wires, power instability, or a malfunctioning chip.  Most bugs are fixed with patience, care, rereading, and/or rewiring.  For example, each chip can be tested separately to make sure it functions before incorporating it into the breadboard.  For a particularly severe bug, I may send you over to the Physics department to use an oscilloscope to pinpoint subtle errors. If a bug is caused by an unfixable defect in the kit, I will not hold you responsible;  I will always try to provide spare replacement parts when needed.

The kit comes with a manual, but the hints and details below based on classroom experience, offer you very useful supplementary information, not all of which can be found in the manual.  You may also find the designer's site Yunten Labs to be a useful reference.  Finally, it is worthwhile for each group to invest in a good pair of wire strippers and a magnifying glass with a light.

Grading and Getting Your Work Checked

The project has five stages, each one clearly indicated in your manual. There is a sixth stage that we do not implement.  It is a good idea to show me your progress after each "stage" of the project so that in case anything breaks late in the game, you still get credit for earlier work. If you wait until the end to show me everything and it doesn't work, I won't be able to tell how much you finished successfully.  Taking a movie on your cell phone is a quick way to record correct functionality.  Note:  If your hardware at any stage has bugs that do not allow you to get it working after your best efforts, you can still get partial credit (at most 10 out of 15) for that stage by wiring it up and explaining to me in writing what it is supposed to do.  The write-up for Stage 5 should include an explanation of all the control line formulas found in the description for Stage 5 below.

In this picture, a complete project through stage 6 is shown, but remember you need only complete stages 1 through 5.  Stage 6 includes the small breadboard on the right with five chips and it handles input and output and interrupt processing usually handled by the operating system.

Each of the five stages you must implement is comprised of a row of chips.  Leave space on the right side of the rows in stages 1 through 4 because stage 5 needs to use some space on the right side of two of these rows.  The function of each row of chips is summarized below:

The Five Stages and Testing

Stage 1 builds a clock.

Stage 1. (4 chips)  These chips simulate a clock that generates a ripple timing signal 0-9.  The original pulse is created using a purposeful glitch from three consecutive not gates.  The first six signals T_0 through T_5 are monitored by LEDs. 

To test this stage, you should see a ripple counter lighting six LED's on and off in order with a blank count of four (a total of ten ticks) before it cycles and starts again.  There is sometimes a glitch if you try to monitor all the chips' output in this stage.  In particular it is often difficult (impossible?) to monitor the 7490 counter chip accurately with LEDs.  Instead, just monitor the first chip (one blinking light) and the last chip.  Also, the T_0 coming out of the last chip will (eventually) need five splices, so make sure to move its output to a fresh column. 

Follow the manual carefully.  Depending on the chips you have, some require resistors to pull current effectively and some do not.  In particular, the outputs of the 75LS05 chips require resistors to pull-up the current.  Otherwise, you will not see the blinking lights on your LEDs from the rightmost 75LS05 chip on stage 1.

Occasionally, some students find erratic behavior in the circuit unless they touch the top of the capacitor with their finger!  I do not know why this glitch occurs, but be aware of that possibility.  Some students report being able to fix this glitch by adding a resister between the top of the capacitor and power. Others report success with a wire connecting ground to the top of the capacitor.  Either method is better than just using your finger.

Sometimes people have reported getting the clock to work correctly T0 through T3, but T4 and T5 are either not lighting at all or acting erratically.  Even this will be okay because we never use the timing signals after T4.  That is, only T0 through T3 are ever fed into any chips to control the computer, so if T4 and T5 are weird, it will not affect any part of the project.  Even more cool, is that even if your clock is all messed up, but you can get any 4 of the 6 signals T0 through T5 to fire consecutively in a cycle, then you can still finish the project 100%.  For example, say that T2, T3, and T5 are broken but T0, T1, T4, T6 are firing in a cycle reliable, then you can simply use T4 in place of T2 and T6 in place of T3 in a wiring that requires T2 and T3.

Video of Stage 1 working

Stages 2 and 3 implement the "fetch cycle" of this machine.  The fetch cycle is sequence of steps in hardware whereby the next machine language instruction is pulled from memory into the CPU, decoded by the control unit, and executed.  The program counter (PC) is a register that stores the location of the next instruction to be executed.  This location is sent to the memory address register (MAR) of the RAM, and the instruction stored in that location is returned from RAM.  After this is accomplished, the PC is incremented so you can perform the next fetch cycle and execute the next instruction.  Stage 2 increments the PC and sends PC to the MAR, and Stage 3 sends fetches the instruction in location MAR from memory.

Stage 2.  (5 chips)  These chips include a register holding the program counter (PC), an adder (ALU), and a side register to hold the result of the adder.  Each register connects to the bus via a buffer register, so that each register uses two chips. A bus is a highway of 4-bits.  Any chip can send stuff to the bus and any chip can read from the bus.  Notice that the buffer register chips (74LS126) are composed of four tri-state buffers, so that when you turn off these buffers, the chip is effectively disconnected from the bus.  Without these tri-state buffers on the 74LS126 chips, the design would never work.  You cannot simply add 0s and 1's to the same wire simultaneously.  That is, only one chip talks to the bus at a time.  On the other hand, any number of chips can read from the bus simultaneously.

The purpose of this part of the data path is to increment the PC.  The PC sends input to the ALU; the other input of the ALU  is set to 0000 (4 grounds); and  the carry_in is left to default high (1) and needs no connection (note this!).  Thus, the ALU effectively adds 1 to the PC.  This addition is done in two steps using the states T_0 and T_1.   At T_0, the PC (7475 chip register) value moves onto the bus through the buffer and into the adder, and at T_1, the incremented value moves back to the PC. The 74126 chips are 4-bit tri-state buffers which when activated pass its values onto the bus, and otherwise are disconnected from the bus.  The right register (7575 chip) receives the incremented value from the adder at T_0, and moves that value back through its buffer at T_1 to the bus and to the PC register for testing.  In stage 5, this right-side register/buffer will be connected to the control unit (not T_0 and T_1) and used to decode and execute specific instructions.

To test this stage, monitor the data lines of the PC.  You can do this by monitoring the bus using LEDs with (or without) resistors - try both ways if you have errors.  You should see the PC increment in binary after every complete 6 cycles.  The change occurs in the first two cycles (T_0 and T_1).  You should see blank lights during the other cycles (or all lit if you use resistors).

Video of Stage 2 working

Note that in later stages of the project, the SUM_in and SUM_out signals on the Sum register and the output buffer to its right, which now come from T_0 and T_1, will eventually come from Or gates and not directly from the clock's T_0 and  T_1.  Later on, in cycles T_2 through T_5, more interesting things will occur, depending on the instruction being executed.  (actually T_4 and T_5 are never used, but T_2 and T_3 are used for execution of instructions.)  Right now, we are only controlling the incrementing of the PC which will happen with every instruction independent of what the instruction does.

As is the case in Stage 1, sometimes Stage 2 will not work correctly if you simultaneously monitor the signals from Stage 1.  So, if you are at your wit's end, always try to remove all LEDs except the ones monitoring the section you are testing.

Stage 3.  (6 chips)  These chips are three registers with associated buffers connected to the bus.  They are the MAR, and two side registers A and B that are used to hold data results of instructions. This computer does not use RAM for data (only for program instructions).  The MAR sends its 4 bits directly to RAM.  The RAM buffer never feeds the bus, so you could just leave the MAR buffer chip out completely.  The data path of this stage is used to read instructions from memory.  This fetching occurs during T_0 and T_1, simultaneously with the PC increment..

To test this stage, monitor the data lines of the MAR, and you should see it mimicking the binary values on the PC.  The MAR values should be behind the PC values by one complete set of 6 cycles.  Note that in this stage the "out" control signals on MAR, A, and B should be grounded to prevent these buffers from spilling values onto the bus.  Only one buffer should ever output to the bus at a time, and this will be controlled in stage 5 by the control unit.  Now, however, you need to manually ground these lines to keep them off the bus.  The MAR_out signal (if you used the buffer chip) stays grounded throughout the project.  This is because MAR never sends any signal to the bus;  it only feeds the RAM directly.  However, A_out and B_out will eventually be fed from logic gates in the control unit of stage 5.  

Finally, MAR_in should be connected to T_0.  Note that MAR_in is not shown explicitly on the 7475 chip diagram, MAR_in (marked red) should be connected to pins 4 and 13 (also marked red) to activate all 4 (flip-flops) bits.  You can connect 4 and 13 together to manage this.  Finally, A_in and B_in should be left open for now.  They too will eventually get signals fed from the control unit. In general, it does not hurt to leave the "in" control lines open (disconnected is default open) because they can all read from the bus simultaneously without any errors.  However, it would be a disaster to have more than one chip write to the bus at the same time.  That is why we make sure to have at most one of the "out" control lines on, and ground the rest when testing this stage.

Video of Stage 3 working

Stages 4 and 5 implement the Control Unit and Execution of the various instructions.

Stage 4.  (4 chips) This stage includes a 16 4-bit memory (RAM) chip, two dip-switches to control the input to the RAM, and three chips (two inverters and one decoder) to generate control signals from the instructions coming from RAM.  Recall, that this computer does not store "data" in the RAM;  it stores only program instructions in RAM.  When your computer runs. the MAR sends an address to the RAM and the RAM sends out the contents of that address in binary.  The contents represent an instruction.  These binary instructions are decoded into unary and a particular instruction will fire one of the Isig lines, Isig_0, Isig_1, Isig_2, Isig_3.  Note that Isig_4,  Isig_5, and any higher Isig lines do not get used. Note that the MAR lines should not be connected to the RAM until you have stored instructions into the RAM and you are ready to execute them.

To read and write instructions into RAM manually, the wire connected to ME is always grounded; this enables RAM.  The wire connected to WE enables writing to RAM; when it is grounded you can write to RAM, when it is in power it lets you read, but not write. When you are writing instructions to memory, only the address dip switch lines connect to the RAM address pins;  the MAR at this point should be disconnected.  When you run your program in Stage 5, disconnect the address dip switches AD_0 through AD_3. The address-line dip switches are used as input to the memory chip only when programming the computer.  When the program runs, the inputs to the memory chip comes from the MAR.

This stage can and should be tested independently of the other stages.  That is, you must power just this row when testing this stage.  Indeed, it can be tested correctly even if you have a bug in one of the earlier stages.  You should be able to store program instructions (4 bits) into any of the 16 RAM locations, and observe that these instructions are indeed stored correctly.  Be careful to press the dip-switches in firmly.  If they pop up, the data (instruction) and address values will default to high and ruin your test.  You can monitor the RAMs outputs after the first inverter or after the decoder to check that it is storing values correctly.  The inverter will send out 4 bits opposite what you stored, and the decoder will send out a single light on the unary line equal to the binary value coming out of the inverter.  The RAMs outputs are difficult to monitor directly out of the chip, but sometimes that works too.  Sometimes the RAM monitoring works but the inverter leaves all the values looking high. Using (or not using) pull-up resistors also can affects the monitoring. The bugs here can be mysterious.

If the RAM stage does not work, you can bypass the RAM entirely and still test Stage 5 by hard-wiring an instruction line to 1:  either INCA, INCB, MOVAB, or MOVBA, and then letting the computer execute that instruction.

Video of Stage 4 working.

Stage 5.  (4 chips) The fifth project is the control unit, and in contrast to the other stages, does not appear in its own row.  Instead it is distributed on the right side of the first four rows.  There are four chips in this stage consisting of two ANDs and two ORs that allow you to generate control signals to registers A and B, the MAR, the SUM register, the PC register, and their buffers.  Your computer should implement the four instructions:  INCA, INCB, MOVAB, and MOVBA.  It is this stage that will finally send signals to all the open control lines left from earlier stages (that is, A_in, B_in, A_out, B_out, SUM_in, and SUM_out).  Remember to remove any grounded inputs that had been connected temporarily to these control lines.  Notice that the INCA and INCB instructions get implemented in cycles T_2 and T_3, and the MOVAB and MOVBA instructions in just T_2. You will need both AND and OR gates to implement the final control signals.  For example, SUM_in = T0 + T2(INCA + INCB) = T0 + T2(INCA) + T2(INCB) (The T0 comes from stage 2 - incrementing PC).   The other control outputs also have Boolean formulas in terms of the timing signals and the instruction codes.  Recall that PC_in, PC_out, and MAR_in receive signals from T_0 or T_1 as described back in stages 2 and 3.   You can design the entire control unit for all four instructions with 8 OR gates (2 chips) and 6 AND gates (2 chips).

Note: Some kit manuals list only three instructions: INCA, MOVBA, and SyncRead.  These manuals leave out the details for INCB and MOVAB.  You should implement the four instructions INCA, INCB, MOVAB, and MOVBA, but not SyncRead.  INCB and MOVAB are very similar to INCA and MOVBA.  If you are not sure how to do all four, please ask me for help.

You decide the op-code values for the instructions, and you should use 00, 01, 10, and 11.  Thus, you use binary signals Isig_0, Isig_1, Isig_2, and Isig_3 for the four different instructions. For example, you could have MOVAB, MOVBA, INCA, INCB be 00, 01, 10, and 11, respectively, and then Isig_0 would represent MOVAB.  You would connect this Isig_0 signal to the MOVAB arrow on pin 1 of the 7408 AND gate.

Here are the formulas for all control line outputs.  If you do a write-up for this stage, you should explain the reasoning behind each of these formulas.

PC_in = T_1
PC_out = T_0
MAR_in = T_0
A_in = (IncA)(T_3) + (MovBA)(T_2)
A_out = (IncA)(T_2) + (MovAB)(T_2)
B_in = (IncB)(T_3) + (MovAB)(T_2)
B_out = (IncB)(T_2) + (MovBA)(T_2)
SUM_in = T_0 + (IncB)(T_2) + (IncA)(T_2)
SUM_out = T_1 + (IncB)(T_3) + (IncA)(T_3)

Before you run a "program," you should first test each instruction separately. This can be done by hard-wiring one of the unary instruction outputs to power, and disconnecting the MAR from RAM.  Then run your computer and it will execute that one instruction over and over.  You can monitor the A and B registers and see if the instructions works. This allows you to test Stage 5 even if Stage 4 is not working.

Testing this stage completely requires you to power up the whole computer and have all the other stages working.  Make sure that you disconnect the dip-switches from memory when you run your computer.  There can only be one input to the RAM address pins at a time. When you program the computer (stage 4) the connections are from the dip-switches, but when you run the computer, the connections are from the MAR.  You can disconnect the dip-switches by simply removing the switches from the breadboard.  The manual suggests disconnecting the dip switches by setting them all to 1, which effectively disconnects them too, but that is not the simplest way.

The Complete Project

  A complete project will implement all four instructions INCA, INCB, MOVAB, and MOVBA.  and be able to execute any program composed of these instructions such as:

INCA INCA MOVAB INCB INCB INCB MOVBA

which increments register A from 0000 to 0001 to 0010, moves 0010 into register B, increments register B to 0011 to 0100 to 0101, and then moves 0101 back to register A.  It isn't Halo or League of Legends, but even so, it sure is cool to get it all to work. 

It is a good idea to place your instructions starting at address 0001 rather than 0000, just to make sure that the first instruction is picked up the control unit.  If the MAR is not sending consistent signals, you may still be able test Stage 5 by wiring the PC directly to the RAM address pins.

Here is a Video of Stage 5 Working and running the following program: INCA INCA INCA INCA INCB MOVBA. 

Here is another complete video of a different program.

To test the entire project, replicate the animated DEMO program at the Yunten site, namely:  INCB INCB INCB MOVBA INCB MOVAB, and monitor the data lines of A and B using LEDs in order to check whether the program works.

General Tips and Hints - Very Helpful:

• LEDs burn out easily and frequently.  Always test them before you assume that your circuit is faulty.  Despite the needy resistor in the cartoon below, some LEDs need resistors and some do not, depending on where you are inserting them and what you are monitoring.  Never plug an LED directly into high without anything in between.  I have heard of LEDs burning out with an explosive pop in some cases.

• Outputs of normal chips do not need resistors, while outputs of LS chips require a "pull-up" resistor.  This resistor is connected to high on one end and the chip's output on the other end.  You can read about pull-up resistors. The explanation is from analog circuit theory, and generally part of a black box from the perspective for our "digital" course.  Basically, a pull-up resistor makes sure that the outputs of certain chips stay away from the no-man's land voltages that are neither high nor low.

• Chips and capacitors can also fail.  Swap out equivalent parts and test to make sure each piece works.

• Be careful where you power and ground a chip.  A hot chip is almost always a sign that you did something very wrong. 

• If you ever get a piece of wire stuck in a hole and cannot extract it, then do not use the column -- it may be shorted.  Mark a note on the board where the broken wire is so someone after you knows to avoid that column.

• Note that in some breadboards, the rows are disconnected in the middle, and you will need to bridge them to run power and ground across the entire row.

• Leave space on the right side of the rows in stages 1 through 4 because stage 5 needs to use some space on the right side of two of these rows.

• The wires from the DC power supply are not symmetrical.  Make sure that the one marked red is actually high and the one marked black is low.

• Test every chip's functionality independent of the complete circuit before you include it in the larger circuit.  You can test adders, flip-flops and tristate buffer chips all independently.  This is important if you are at you wit's end and checked all connections are correct, and still the board is glitchy.  Sometimes, rarely, a chip burns out or malfunctions...  especially if you ever accidentally connected it backwards to power and burned it out.

• In general, when splitting a wire's signal, you can run it into a column and run extra wires from this column.  However, you should never run two or more wires into the same column and try to run a single wire out of the column.  Two or more wires would need to first run through some chip before getting a reliable output.  This is why you need "or" gates for the stage 5 output signals.

• Never re-wire with power connected... (even if you see me do it occasionally).  It is a bad bad habit and I pay for it all the time.  Be careful!  You might fry a chip or LED by mistake.

• Chips are oriented by the "notch" and the pins are numbered consecutively in counterclockwise order with the notch at the top.  Make sure to insert all chips with the correct orientation.  If you put a chip in reverse, and thereby connect power to the wrong end, you can burn out the chip and it will no longer function. It is challenging to debug a malfunctioning chip.

• Your power supply, LEDs, and (sometimes) capacitors are NOT symmetric.  LEDs have long wire to power and short to ground.  Power supply has a hot wire and a ground wire - make sure the hot wire is marked red by testing it on an LED.  Capacitors (if asymmetric) will have a mark pointing to the ground.

• It is good style to test all wires before using them, because sometimes they break inside the insulation.  It is a simple matter to set up an LED and resistor in series between power (PWR) and a hole, with the wire to be tested connected between another hole in that column and ground (GND).

• It is also good style (when possible) to run wires around chips rather than over them.  The picture here shows an example.  This allows for easy tracing of the wires, and for convenient replacement, insertion, or removal of a chip without having to remove wires - a crucial tool in debugging errors.

• Always double check that no resistors or LEDs or wires accidentally hit each other.  The implications of even a slight touch are very unpredictable and hard to debug.

• Sometimes a breadboard is flaky, and can be made to work by a little tap.  Small pieces of wires can become lodged in holes, and internal disconnections caused by dropping the board contribute to making breadboard malfunctions inconsistent and hard to diagnose. Breadboards are not expensive, so if you really feel yours is faulty, it can be replaced.

• There is a breadboard simulator here.  If you have trouble getting your hardware to work, you can test your project on the simulator! 

• Note that even if you have a bug in one of the first three stages, stage 4 (instruction-RAM) can and should be implemented and tested independently.

• It is a good idea to store your program starting in memory location 0001 rather than 0000 to make sure that the first instruction is picked up by the fetch cycle.

• If the MAR stops providing consistent counter signals, you may be able to still test a complete program by wiring the PC directly to the RAM.

Perspective and Summary of the Entire Design

In class we design three computers:  my machine, EC-1 from the text, and EC-2 from the text.  EC-1 and EC-2  are implemented as Moore machines. These Moore machines are represented by finite state machines and implemented using standard techniques of flip-flops for the state, a next-state feedback circuit, and a combinational circuit for output lines.

For my machine, we consider two designs for the control unit:

a. A Moore machine that uses all the states in the finite state machine, and

b. A Mealy machine that compresses the number of states to six, but adds more complexity to the output circuits.

The Moore can be implemented just like EC-1 and EC-2 using standard finite state machine techniques. The Mealy machine could also use these finite state machine techniques but since the 6 states of the Mealey machine just cycle around in a simple predictable way, we can implement the states more simply with a 6-cycle ripple counter T_0 through T_5.  When using the ripple counter instead of flip-flops, the rest of the control unit is implemented with a decoder for the op-codes generating binary instruction signals,  and a combinatorial circuit for the control outputs that uses the signals T_0 through T_5, and the instruction signals. See class handout.

Your kit is our fourth computer.  Building it and studying its design will help you understand the ideas of this course more deeply. The machine designed in your kit is similar to EC-1 in that it has just four instructions. It is similar to my computer in that it is naturally implemented as a Mealey machine using a 6-cycle ripple counter.  While my machine had eight instructions, the kit uses only four binary instruction signals :Isig_0 through Isig_3,which represent INCA, INCB, MOVAB, and MOVBA in some order chosen by you.  The kit effectively uses just four states T_0 through T_3.  Nothing happens in states T_4 and T_5. 

T_0:  PC goes to bus and gets incremented.  MAR gets old value of PC from bus.

T_1:  PC gets new value.  Instruction at location PC is fetched from memory. 

T_2 - T_3:  The instruction is decoded by the control unit and executed. 

MOVAB and MOVBA each only need one cycle, namely T_2, while INCA and INCB each need two cycles, T_2 and T_3.

T_4 - T_5: Nothing happens.

Happy Wiring!