HDL – Full Adder Schematic

This is a continuation of my FPGA series.  I’m going to show how to create a one-bit full adder circuit using a schematic diagram in Xilinx HDL language.  Then I’m going to send the compiled code to the Mimas V2 Spartan-6 board and test it.  This project is for the entry-level FPGA programmer.  If you just purchased the Mimas V2 board and you’re unsure how to get started, this short tutorial should help with some of the entry-level basics.

To start this project, you’ll need to download and install the Xilinx Design Suite by clicking here.  Follow the instructions, you’ll need to register and answer some questions and install the software.  Go to “All Programs -> Xilinx Design Tools -> ISE Design Suite 14.7 -> ISE Design Tools -> 64-Bit Project Navigator”, then click on the “New Project” button.  If you’ve already installed the tools and wish to start a new project, you’ll need to go to the File menu and close the project before starting a new project.

When the new project dialog starts, select “Schematic” as your top level project (I keep my FPGA projects in a directory on my D: drive):

Then give your project a name and click on the next button.  Then click next again.

You’ll need to create a schematic. Right click on the FPGA board designation node and select New Source:

Click on “Schematic” and Next, Next.

Now you can draw a schematic.  First you’ll need to find logic gates that you want to use.  If you click on the “Symbols” tab (bottom tab of the palette window):

You can find logic gates like and2 which is the 2-input AND gate.  Draw a full adder circuit.  The basic logic for a full adder is like this:

You can plot the XOR2, OR2 and AND2 gates first, then use the wire tool to connect outputs to inputs.  Next you’ll need to add connectors to the A, B, Cin, S and Cout points.  Your final circuit should look something like this:

I added three VCC connections to the enable pins of the LED displays since I won’t be using them. I also had to invert the outputs because the LEDs on the Mimas board are active low.  You can use an XNOR gate instead of an XOR and inverter and you can use a NOR gate instead of the OR and inverter.  I added inverters after I generated the code, sent it to the board and discovered that the LEDs lit opposite of what I expected.

The connectors (A, B, CARRY_IN, SUM, CARRY_OUT, EN1, EN2 and EN3 in the diagram above) can be added from the palette to indicate inputs and outputs.  You’ll need to give them a useful name so you can designate a physical pin to connect them to.  Double-click on the connector object and you’ll see this screen:

Now click on the name under the “Nets” branch and then change the “Name” to the value that you want.  You can also change the connector to be an input or output.

To define the connectors to a physical pin, you’ll need to add a ucf file to your project.  Right-click on the FPGA node again (under the Design tab) and add a New Source.  This time select an Implementation Constraints File:

Then add the following definitions to connect the circuit to your FPGA board:

NET "SUM" LOC = P15;
NET "CARRY_OUT" LOC = P16;

NET "A" PULLUP;
NET "B" PULLUP;
NET "CARRY_IN" PULLUP;
NET "EN1" PULLUP;
NET "EN2" PULLUP;
NET "EN3" PULLUP;

NET "A" LOC = F17;
NET "B" LOC = F18;
NET "CARRY_IN" LOC = E16;

NET "EN1" LOC = B3;
NET "EN2" LOC = A2;
NET "EN3" LOC = B2;

You can lookup the physical connection names for the MIMAS V2 board from this website: Mimas V2 Spartan 6 FPGA Development Board With DDR SDRAM.

Next, you’ll need to select your FPGA board node and then in the processes section, you can right-click on “Generate Programming File” and select “Process Properties”.  Make sure the “Create Binary file” check box is checked.  Then right-click “Generate Programming File” again and select “Rerun All”.  That will compile and generate all the files you’ll need for your board.

Now you can startup your Configuration tool.  This can be downloaded from here (Click on Downloads and download the Configuration Tool for Windows).

You’ll need to select the COM port that corresponds to the USB port that you are using for your board.  To find that, you can open the Windows “Device Manager” and look it up.  You’ll need to plug in your Mimas board for this to show up.  You’ll see an entry in the “Ports (COM & LPT)” section:

You can see the “Numato Lab Mimas…” line and it is using COM3.  So select the COM port that your computer is setup for in the Configuration Tool.

Next, click on the “Open File” button and navigate to your project folder and click on the “.bin” file.

Then Click the “Program” button and wait for the “Done” status.

Now you can use the dip switches to turn on/off the A, B and Carry in signals:

This is a view with A, B and Carry In set to a “1”.  The LEDs represent D1=Sum and D2=Carry.  As you can see, they are both lit.

 

Programming the GAL22V10

In previous blog posts I showed how the GAL16V8 operated and how to program it (see here and here).  In this blog post I’m going to discuss the differences between the 16V8 and the 22V10. Here’s the specification sheet for the GAL22V10: Lattice GAL22V10 Specifications.

On first inspection, both devices look identical, except for the increased number of inputs and outputs.  The specifications are straightforward once you know what to expect.  If you’re familiar with the 16V8 and have never used the 22V10, there are some confusing differences.

Here’s the full fuse map for the GAL22V10:

0 - 5807 matrix

5808 S0 for OLMC 0 (active low/high)
5809 S1 for OLMC 0 (registered/combinatorial)

5810 S0 for OLMC 1
5811 S1 for OLMC 1

5812 S0 for OLMC 2
5813 S1 for OLMC 2

5814 S0 for OLMC 3
5815 S1 for OLMC 3

5816 S0 for OLMC 4
5817 S1 for OLMC 4

5818 S0 for OLMC 5
5819 S1 for OLMC 5

5820 S0 for OLMC 6
5821 S1 for OLMC 6

5822 S0 for OLMC 7
5823 S1 for OLMC 7

5824 S0 for OLMC 8
5825 S1 for OLMC 8

5826 S0 for OLMC 9
5827 S1 for OLMC 9

5828 - 5891 Signature

No PTD Fuses

You’ll notice that there are no PTD (Product Term Disable) fuses.  This device doesn’t have any.

No Common Mode Bits

Next, the mode bits are missing (the GAL16V8 had 3 modes controlled by fuses 2192 and 2193).  The OLMC modes for the GAL22V10 are built into the S0 and S1 bits.  There are only two modes: Registered and Combinatorial, controlled by the S1 bit.  Each OLMC can be programmed separately, which means that you can designate which OLMCs are Registered and which are Combinatorial.  The S0 bit controls active high and active low outputs for each OLMC.

Variable Rows per OLMC

The next complication to this device is that the matrix of fuses that control the AND gates is variable in the number of rows.  The GAL16V8 had a simple arrangement of 8 rows for each OLMC.  In the 22V10, there are a variable number of rows for each OLMC starting with 8, then incrementing by 2 for each OLMC until 16 and then decrementing by 2 until the last OLMC has 8 inputs.  You can see the number of inputs for each OLMC in the functional block diagram:

If you have an equation with 13 terms like this arbitrary example:

OUT = A*B + C + /B + A*/C + D*E + C*D + A*D*E + A*/B*D + B*/D + /B*C*E + C*E*F + E*/F + /E*C*D

You’ll need to make sure it lines up with an OLMC that has more than 12 rows.  This equation will not fit on OLMC 0, 1, 2 or OMLC 7, 8 or 9.  What this means is that you will have to rearrange your output pins for circuits that use more than 8 rows because each OLMC is tied to a specific output pin.

The number of Fuses Per Row is 44

Also, since there are more inputs, then there are also more columns in the matrix.  The number of columns is 44, which is not a round binary number.  The number of columns is determined by the total number of inputs and feedback wires.  Each input and feedback takes 2 columns (the signal and the inverse of the signal.

Preset and Reset Lines

Two extra lines can be used to control reset and set for all registers (assuming you use the registered mode).  The reset line causes the starting fuse of the first OLMC to be 44 instead of zero.  The purpose of the reset line is to reset all the registers used in the device.  You can connect any logic to the reset line to perform reset via a pin, or some combination of logic.  The same goes for the preset line, which is the line that is positioned after the last matrix row starting at fuse 5764 (row 131).

Other Differences

The clock pin is still pin 1 as in the GAL16V8.  The difference is that in the GAL16V8, the clock pin is not used at all in modes that don’t use the registers.  So pin 1 feeds fuse columns 2 and 3.  In the GAL22V10, the clock can control zero or more registered outputs because registered outputs can be selected per OLMC.  Therefore the clock pin is wired to fuse columns 0 and 1 and to the register clock inputs.

The active high/low logic is performed on the output of the D-flip/flop of the GAL22V10, where it is on the input of the GAL16V8 (controlled by an XOR gate).

Using PALASM for DOS

PALASM4 for DOS is still around.  You can to this website and scroll to the bottom to download the RAR file: S100 Computers.  This article is rather old, but it still works.  Here’s the steps I took to get this working:

  1. Make sure you have DOSBOX installed.
  2. Download the RAR file from the article above.
  3. You can use 7-zip to unzip the RAR file.  Right-click on the RAR file and use extract files.  That will maintain the directory structure.  I used d:\palasm.
  4. Start DOSBOX.
  5. Type: “MOUNT c d:\palasm
  6. Type: C:
  7. Type: SET PALASM=c:\
  8. Type: PALASM

Now you should see this screen (after the intro screen):

Select “Retrieve existing design” and type in your filename (I’m assuming you created a file, or you can copy one of the .pds files in the EXAMPLES directory.  Hit the F10 button, then use the right-arrow to select the RUN menu and hit enter (Compilation is the first choice).  Then just hit F10 to compile your PDS file.  You’ll see some processing and then it should end with no errors or warnings:

You can hit ESC to return control to the menus.  Switch back to your directory in windows and you can see that an XPT and JED file were created.  Open your JED file to see the fuse map results:

Finally…

PALs and GALs are obsolete and the digital world has moved onto FPGAs.  These devices are still available and are still useful for hobby purposes.  They can be purchased through Jameco or DigiKey.  PALASM is also obsolete, hence the reason that it only exists in FORTRAN and DOS versions.  If you’re still using these devices, leave me a comment or hit the like button.

 

Building an ALU From EPROM – The Circuit

When I wrote my blog post about building an ALU from an EPROM, I intended to use an EPROM from my old bag of parts.  Unfortunately, none of my old UV erasable PROMs worked with the programmer.  I’m assuming they are old and not usable.  So I purchased a pair of 28C64’s from Jameco Electronics.  These are Electrically Erasable PROMs, so I don’t need to drag out my UV light and wait 30 minutes (or so) for them to erase before reprogramming them.

After I programmed the EEPROM, I had to make a diagram of the pins.  The pin out for the memory chip is organized by address lines and data lines and I’m pretending that the address lines are inputs and the data lines are just outputs (technically they are bi-directional).  Here’s a diagram of what I ended up with:

Technically, I can re-arrage the pins by reprogramming the data and pretending that pins 21, 23-25 are carry in and the function selectors.  Then all the A0-A3 and B0-B3 could be arranged on the left side of the chip.  It really only matters if you are concerned about circuit board layout.  At the moment, I just want to show that it can be done.

Next, I decided to use my 7-segment hex display driver with a 7-segment display to show the output from F0-F3.  This took a bit of extra wiring, but it’s easier to read than 4 LED lights.  Here’s the chip pinout using the GAL16V8 from this blog post (click here):

All that is needed is a breadboard, resistors, a 7-segment display and a bunch of wires.  This is my quick-and-dirty circuit:

For this circuit, I set S0-S2 to the ADD mode (S0=H, S1=H, S2=L).  The small chip in the lower right is the GAL that I programmed in an earlier article.  I also set the carry in as H (represents zero) and set A0 and B0 to H, with all other An and Bn to L.  As you can see 1 + 1 = 2.

One of the reasons I’m demonstrating this idea of using a ROM to represent a circuit is that a simple logical circuit can be temporarily represented as a memory chip.  Then a real circuit can be designed to be substituted.  I have not tested all possible inputs and outputs of this circuit and, more importantly, I have not tested the limits of the speed that this circuit would operate it.  I already know that the answer to my speed question is going to be “disappointingly slow”.

Purpose

Knowing that this will be a slow circuit, what’s the purpose?  The first purpose would be to create a prototype of a circuit that you plan to build.  If you’re building a machine that will require some programming, then it might be best to create a slow version of the machine so another programmer can create and test the software before the machine is complete.

This type of circuit design can also be used for educational purposes.  You can prepare EEPROMs with the circuits you’ll need for class instruction to support your lecture.  The EEPROM represents a black box of the circuit that your class can use without actually building a complete circuit.  In this instance an ALU.  The circuit could then be reprogrammed for a different purpose in a future lecture.

 

Vintage Hardware – Arcade Games

In my last Vintage post I talked about the first commercially available fully assembled PCs and ended with the Space Invaders video game console.  In this blog post I’m going to talk about a few other video games.

Galaga

I spent so many quarters on Galaga that I probably bought the company owner his/her yacht.  I went searching around the Web looking for schematics (which didn’t take too long) and stumbled onto this site (click here).  The schematic for Galaga is a PDF that you can download by clicking here.  When I first opened the schematic I immediately noticed that the CPU board contained three Z-80 CPUs.  These guys were serious!  At that time, this game probably cost a lot to manufacture.

You can learn a lot about the original video game from people who collect and repair these games.  Here’s a website that has some interesting material on Galaga: Galaga Information.  The best site on the design of the game is at the Computer Archeology site.  This site has the assembly code from the EPROMs used by all 3 CPUs and indicates that CPU1 and 2 control the game while CPU3 is the sound processor.  All three processors share 8k of static RAM (using 2147 memories).

There are custom chips on the boards that are used for various functions.  One function is the bus driver chips that interface between each CPU and the common data bus.

There are three of these chips used and I’m assuming that the logic connecting to them is used to interlock between the three so that only one can access the main bus at a time.  What I’m uncertain of is how the bus is shared.  There is a 6Mhz clock signal that is fed into all three chips, so maybe each CPU gets 1 or 2 clock cycle each turn?  The Z80 chips are normally clocked at 1Mhz, so it would make sense to run the bus at 3x or in this case 6x the CPU frequency and then do a round-robin.  Each CPU can be programmed as though it had complete control of the address and data bus.

For information on the custom chips, I found this site: The Defender Project.

Finally, here’s a blog describing an arcade emulator that Paolo Severini built using javascript:

Galaga: an Arcade machine emulator for Windows and HTML5

Defender

This video game was a horizontal shooter game with a video resolution of 360 x 240 pixels at 16 colors from a palette of 256 total colors (according to the manual, which can be found here). Here’s a snippet of the color RAM circuit:

The TTL 7489 is a 16 bit memory used to store the palette information.  You can see where the 8 outputs from the ram (4 bits from each chip) feed the analog Red, Green and Blue circuits used by the monitor.  It appears that the blue gets the least amount of control with only 2 bits, or 4 levels, while the Red and Green receive 3 bits or 8 levels of information.  The 74LS257 at the left of the circuit diagram is a multiplexer.  The job of that circuit is to allow the microprocessor to access the 7489s (and use the MPU data bus to load data) or allow the video circuitry to access the memory to display on the video monitor.  The microprocessor can only write to the memory during a monitor blanking operation.

At the top of the Red, Green, Blue amplifier circuits is another transistor.  This transistor shuts off the power to all three amplifiers and is controlled from the horizontal blank signal.  If you’re not familiar with the old video tubes, basically, there is a beam of electrons that are fired at the front of the screen.  The inside of the tube is coated with phosphor and it glows when electrons hit it.  The beam is “steered” by magnets on the neck of the tube.  The beam is moved in a horizontal line pattern starting from the top left of the screen and ending at the bottom right.  When the beam returns to light up the next line of phosphor, it has to be shut off, otherwise an angled beam would be drawn on the screen.  The beam is also shut off when it returns to the top left from the bottom right.

Unlike Galaga, Defender uses only one CPU and it’s a 6809 processor.  The game program is stored in ROM like other video game boards (no need for a hard drive).   There are two versions of Defender and both versions contained 26k of ROM (in different configurations of 4k and 2k ROM chips).  There are three banks of RAM used for video memory and scratch pad memory.  All RAM used is the 4116 dynamic RAM organized as 16k by 1 bit.  If you look at the schematic it appears that banks 1 and 2 are just 8 chips (4L-4S), but the diagram represents two chips per location (5L-5S).  Bank 3 is wired a bit different from banks 1 and 2.  The data bus is connected through a multiplexer.

The video RAM is fed into 4 8-bit serial shift registers.  All three banks of memory go into these shift registers at one time.

The TTL 74165 is a parallel load, serial out shift register circuit.  According to the circuit above, 6 bits are loaded at a time into each shift register.  Two bits from each bank per shift register.

If you read through the manual, you’ll stumble onto the E and Q generator.  These are 1Mhz clock signals that are out of phase from each other.  The purpose is to interleave the CPU and video access to the video memory.  During one clock cycle the CPU (call MPU in the manual) can read and write to the memory banks.  During the other clock cycle, the video timing circuit reads the memory banks into the shift registers.

Here are some other sites with information about Defender:

Asteroids and Battlezone

The unique aspect of these two games is that they use vector graphics.  If you don’t know what vector graphics are, you can think of it as a bunch of lines drawn on a screen instead of a grid of pixels.  The maximum number of lines that can be drawn on the screen depends on the speed that lines can be drawn in 1/60th of a second, which is the refresh rate of the video screen.  The circuitry for generating the images seems pretty simple: Run down a list of 2D vectors and output the x,y coordinates to the screen.  Video tubes operated on a X and Y or horizontal and vertical magnets that “steer” the electron beam to the phosphor coating in the front.  The circuitry to run this is a bit more complicated.  Basically the vector graphics are driven by a digital to analog circuit that is independent of the CPU.  This circuit calculates all the intermediate values of x and y for each line that is rendered on the screen.  There is a state machine that performs all of this logic, which is detailed in this document: The hitch-hacker’s guide to the Atari Digital Vector Generator.  The last page shows the states:

The DVG was a special purpose processor built out of discrete TTL components in order to run a vector graphics system.  The DVG had 7 operation codes:

  1. VCTR – draw long vector
  2. LABS – load absolute x,y coords
  3. HALT
  4. JSRL – jump to subroutine
  5. RTSL – return from subroutine
  6. JMPL – jump
  7. SVEC – draw short vector

There is also a “Z” axis circuit.  This determines if the beam is on or off and there are also different intensities to represent different shades.  Both games are black and white, so there is no color.  Here’s the intensity scaling circuitry:

The intensity has a range from 1volt to 4 volts and can be any of the 16 shades in-between. Scale0 through Scale3 are bits of a 4-bit word.  The bottom part of the circuit above is the blanking circuit.  This is controlled by the BLANK signal, or the BVLD which means beam valid.  If either signal indicates that the beam should be off, then Q8 will turn on and force Q9 to turn off and block any signal coming from the intensity circuit.

You can get a more detailed (and clean) schematic and description of the DVG by clicking here.

There’s an interesting article on the making of asteroids by Ed Logg, Howard Delman and Lyle Rains, the people who created the game (click here).  You can click here to download the schematics for Asteroids and click here to download the schematics to Battlezone.  If you want to know more about the software side of Asteroids you can go to the Computer Archeology site.  This site shows the data that the ROMs contained describing the vector shapes of things like the asteroids, the flying saucer, the ships, etc:

The CPU used for both games is the faster 1.5Mhz 6502A.  Only a single CPU is used for the game.  There is a small amount of RAM using 2114 static RAM chips.  There are two sets of ROMs used.  One set contains the vector shapes as described above (4k) and the other ROMs contain the program to run the game (8k?).

When these video games were designed, microcomputers were not very powerful and it required a PDP-11 to create the program that would be used by Asteroids and Battlezone.  This program was punched onto a paper tape and then loaded into an emulator.  Paper tape was like a cheap floppy disk.  Networks were not very common in the late 70’s, early 80’s, so a cheap method of copying programs was needed.  While PC began to use 5 1/4″ drives, there was also an 8″ drive that came out (the 8″ came out in the mid-70’s just before the 5 1/4″ drive).  Here is a very interesting article about the day to day work environment at Atari while working on coin-op arcade games: Pay No Attention to those Folks Behind the Curtain.  This article also includes emails from Jed Margolin, who worked for Atari and Atari Games for 13 years.

For those who have never seen paper tape or punch tape readers, they were used by the military in the 80’s.  The machine could punch 8 holes wide (there are other tape formats) to represent a byte of data:

The image above is from the crypto museum.  When the machine punched the tape the little holes were punched out at high speed like a paper punch tool.  This leaves a bunch of round circle “holes” that go into a collection bucket for emptying.  That bucket is called the “bit bucket”:

By Retro-Computing Society of Rhode Island – Own work, CC BY-SA 3.0

 

Building an ALU from an EPROM

This blog post is a “what-if” scenario, rather than a practical application.  Still, if EPROMs ever become super fast, this is a viable option.

I’ve discussed Arithmetic Logic Units in previous posts.  I have the circuit for the TTL 74381 and 74382 chips.  The circuit is easy to find on the internet and it’s included in the TTL logic book.  Unfortunately, the chips can not be purchased and are probably discontinued.  So I analyzed the circuit and was attempting to design a GAL equivalent.  Unfortunately, the GAL22V10 doesn’t have enough circuits to emulate the 74381.  I’ll need something more sophisticated.  I’m looking at CPLD devices and FPLAs.  These are probably overkill for an ALU, but I could code something that is 32 bits wide all on one chip.

So I scratched my head and thought, what if I used an EPROM?  First, I counted the inputs and outputs for the circuit.  Here’s the circuit:

The total number of inputs is 12 and, fortunately, the number of outputs is 8.  So this will fit really nice on an AMD 2732.  The 2732 is 4k x 8.  Doing the math on the inputs shows that 2^12 = 4096 or 4k.  So we’ll get an EPROM that has 12 address lines and 8 data lines.

Now for the bummer about EPROM memory… It’s slow.  Typically to the tune of 250ns.  Which is painful compared to the specs for the TTL 74381 running with a max delay time of 33ns.  Jameco has a One Time Programmable PROM that runs at 45ns.  That’s pretty close for an experimental circuit.  Making this a feasible stand-in for the TTL 74381 and 74382.

So now for the dirty part: Convert all inputs into outputs.  I was going to use my logic simulator to simulate all possible inputs, but it runs too slow.  The emulator was designed to study delays not pump out all combinations of inputs.  I had to create a new program to simulate my logic.  This turned out to be easy.

If you click on the diagram above, you’ll see that each gate is uniquely numbered.  That’s how I translated this circuit into my simulator.  For the quick logic I used boolean for inputs and outputs, then I created a run circuit method that ran the circuit for the given inputs and set the outputs accordingly.  Translating a diagram like this is easy because I purposely arranged my numbering to start from the inputs and work through the circuit sequentially until I reached an output.  So I started inputting logical statements like this:

bool gate0 = !S0;

This is for gate 0’s output.  Basically gate0 will invert the input S0 (which is a boolean variable I created as a getter/setter).  Continuing on:

bool gate1 = !gate0;
bool gate2 = !S1;
bool gate3 = !gate2;
bool gate4 = !S2;
bool gate5 = !gate4;
bool gate6 = gate4 && gate2 && gate1;

And so on, until I ended up with all the outputs like F0 equal to the exclusive nor of gate63 and gate 71.

I then copied my unit tests from my simulator and and translated all 0 and 5volts into false and true.  It took a little debugging but I quickly had the unit tests working and was satisfied with my results.  Next I wrote a console application to feed all the possible inputs.  At first, I thought I could just keep it stupid easy and just do nested loops, but that was a pain, so I decided to do one for loop consisting of the range of 0 to 4095 and then treat each bit of the integer as one of the inputs.  That was pretty easy.

My next task was to figure out what format my EPROM programmer saved its files in.  This turned out to be Intel Hex.  Never heard of it.  It was only lucky that the save box indicated that it was Intel Hex, otherwise, I would have had a tough time figuring out what all the addressing hex represented:

There is a wiki for Intel Hex.  It’s very descriptive and was handy in figuring out how to compute the checksum and addressing information.  So I coded that and spit out the data for my EPROM programmer.  Unfortunately, the EPROMs that I have are old and seem to be defective (the don’t take the program), so I ordered a new EEPROM from Jameco Electronics.  With the EEPROM I can erase the chip from my programmer instead of using my UV light.

Converting a circuit into an EPROM is feasible if there are no latching mechanisms, timing circuits or feedback paths.  In this case the 74381 is just straight logic, so it can be represented with memory very easy.  The 7-segment hex display decoder I did with the GAL16v8 could also be represented as an EPROM.  That circuit needed 8 outputs as well and it uses 6 inputs.  So a tiny 64 x 8 memory would work.

Where to Download the Code

You can download my code and generate your own Intel Hex file by going to my GitHub account here.  Click here to download the hex file I generated.

 

Generic Array Logic Hexadecimal Display

I’ve always wanted a decoder that did more than the TTL 7447 BCD to seven segment display decoder did.  I wanted the full hexadecimal output.  One of my first real projects for the GAL was to create such a chip.  I have an old PAL databook that was published by National Semiconductor in 1982.  I pulled the book off my shelf, just to see what information was in it and to my surprise was a hex display “Application suggestion”.  What luck!  Here’s a picture of the page in the book (click for larger image):

What I didn’t realize when I started this project was that it was going to be a real learning experience.  At first, the chip did not produce any outputs at all.  Then I had issues with several of the segments lighting all the time.  Typing the data into the JEDEC file was tedious and verifying that the fuses were correct was more tedious.  The first problems I found were due to my translation to the .JED file.  I expected that to occur, so I went over the file several times in detail.  Once I determined that I typed it in as it was shown in the book, I began to suspect that the book was wrong (that turned out to be an understatement).

I found a few typos in the diagram above.  First, the PTD fuses were not all correct.  There’s a pattern that they followed when the fuses were set and I noticed that some of the PTD fuses (the “X”s on the AND gates to the right side of the diagram) were not “X”d when the row was empty.  I fixed those and obtained some results.

In order to fix the segment problems I took a look at these two pages:

The page on top is the design page with PALASM logic formulas.  The bottom page is the segment diagram showing which segments will light up given a set of inputs D0-D3.  Both diagrams have mistakes.  I printed a bunch of segment display diagrams so I could work out the logic formulas and determine which formula would cause each segment to light up.  That appeared to be the way the fuses were laid out in the chip.  I focused on the D segment first:

The logic formula for the D segment was listed as follows (ignoring the RBO and LT lines):

/D = /D1*D3 + /D0*/D2*/D3 + D0*D1*/D2 + /D0*D1*D2 + D0*/D1*D2

What this translates to is that the D output (inverted) will be equal to the not D1 AND D3, or the not D0 AND not D2 AND not D3, etc.  As you can tell by my hand writing the /D1*D3 causes all the D segments to light for the binary combinations where D1 is zero and D3 is a one.  I wrote a 25 next to each of those because this logic is used on line 25 of the fuse map.  Unfortunately, this combination occurs for 1001, which should be segments ABCFG (no D segment).  To fix this, I added a /D0 to the equation:

/D = /D1*D3*/D0 + /D0*/D2*/D3 + D0*D1*/D2 + /D0*D1*D2 + D0*/D1*D2

That fixed the D segment.

I noticed an issue with the G segment.  This turned out to be a bug in their segment diagram.  If you look at the numbers 5 and 6, you’ll see that G is not listed.  Sigh.

While I was attempting to reverse engineer the formulas for this chip, I decided to add a simulation of this chip to my logic simulator.  I added code to allow me to read the .JED file in and set fuses according to the fuse map.  My intention was to verify that I had the right fuses set.  Of course, this turned into a different set of problems, all programming related, that I had to troubleshoot in order to make that work correctly.  The simulation software will pay dividends when I start to setup my next GAL circuit, because I can simulate the whole thing before I burn it to the chip and wire it to a circuit.

One lesson I learned is that it is very time consuming to type in the individual fuses.  It’s easier to build a set of formulas.  The number of formulas you can use is a maximum of 7 ORd terms for each output.  In other words, the D segment has 5 terms and they are setup for rows 26 through 29.  There is also a lamp test (LT).  So that’s a total of 6 terms.  One other input is the IC, which is connected to the enable lines for each OLMC.  What this means is that one row is not used and needs to be shut off.  So the PTD line for 31 should shut off that line (the fuse on line 31 actually belongs on line 30 to keep the pattern of fuses consistent).

The bottom line is that you have to get creative on your formulas.  Each segment can be lit for more than 7 different combinations of inputs, so it’s not possible to setup this circuit using terms of 4 like this:

/D = /D0*/D1*/D2*/D3 + /D0*D1*/D2*/D3 + etc.

Some combinations and minimization is required.  This also means that there are limits to what circuits the GAL16V8 can represent.

Here’s a picture of the actual circuit with a “2”, “A” and “F”:

Final Circuit

If you want a copy of the JEDEC file you can download it by clicking here.  You can download the logic simulator project by going to my GitHub account here.  Be aware that this software is still a work in progress.  So there will be changes in the near future.

Update

I was looking at this page:

I noticed that the “9” has the the “D” segment lit.  So the original logic formula in the book was correct.  However, that means that the segment list for “9” was wrong.  Here’s the correct segment list (for the diagram above):

 

Digital Electronics for the Beginner

Let’s say you’re a programmer and your experience in digital electronics involves that one class you were required to take in college.  Or…you’re a young person who is interested in learning this cool stuff, because, well… it seems cool.  One option is to buy one of those learning kits and go through the tutorials.  If you’re on a budget, you can start with one of these:

electronic_snap_circuitsI’ve played with this kit myself and I would recommend any parent that wants to introduce their kid to electronics, this is a good buy.  It has a card for each project that explains the circuit as well as the parts used by the circuit.  There are troubleshooting instructions and warnings about how to build a circuit without burning up components.

Let’s pretend that we wanted to just focus on some digital circuits and jump right into integrated circuits.  Here’s a list of what you’ll need to get started:

  1. Breadboard
  2. Power supply
  3. Wire
  4. IC assortment
  5. LEDs
  6. Resistors

Let’s start with the breadboard.  This is a large plastic “board” that has a lot of holes in it.  You use it to plug your wires, IC’s, LEDs and resistors into.  Integrated circuits are rather tiny, so attempting to wire them with alligator clips or twisting wire to the leads is not a good solution.  Radio Shack used to be my go-to place for stuff like breadboards, but they don’t sell much electronic stuff these days (assuming you can find a Radio Shack).  Jameco Electronics is my current go-to place to find anything I need.  Here’s a typical breadboard from Jameco (and a good starter one):

breadboardIf you’re on a really tight budget you can get one of the really small ones for under $5.00:

cheap_breadboardThe small breadboard above will probably fit 3 or 4 integrated circuits.  The Jameco brand one above will hold about 20 ICs.

Next, you’ll need a power supply.  I would recommend sticking to TTL logic circuits since they are more durable than any other integrated circuits (I’ll get to the details of this soon).  So you’ll need a stable 5v power supply to power your circuits.  This is probably the most expensive part.  If you’re comfortable with wiring a plug to a power supply you can go cheap and get something like this (for around $20):

cheap_power_supplyDon’t let the picture fool ya, it has a cover (you can see it in the spec sheet).  For a young adult, I would recommend spending more money and obtain a safer power supply, like this one:

power_supplyThis power supply has an adjustable output and costs around $67 at Amazon (click here).

I’m going to ignore the fact that you might need a meter to troubleshoot.  Technically, if you’re building TTL circuits, all you really need is a resistor and an LED.  So you can get a variety pack of resistors at Jameco for around $5 (click here):

resistor_assortmentFor a pack of LEDs, I would just by 10 of these, which are about 12 cents each (click here):

ledThe last boring component you’ll need is wire.  Just buy a roll of 22-guage solid wire.  Jameco has several colors available in 100 foot rolls for $8 (click here).

Now for the reason you’re doing this, the integrated circuits.  Jameco has some Grab Bags that are cheap, but they contain random TTL circuits and most are not very useful for an experimenter.  They also have component kits that contain known quantities of each type of TTL circuit, but those are really expensive.  So I would recommend buying this variety (filter to the 74LS series, they’re cheaper):

  • 2 inverters (74LS04)
  • 4 NAND gates (74LS00)
  • 2 NOR gates (74LS02)
  • 2 AND gates (74LS08)
  • 2 OR gates (74LS32)

The total for those should be under $6.

Let’s Build a Circuit

OK, you’re first circuit.  Let’s make this as easy as possible.  Here’s a circuit diagram of what we will build:

and_gate_circuit

Basically, it’s just an AND gate with both inputs set to zero and an LED output.  We will be switching our input wires to simulate a 1 or a 0 for inputs and see what the LED does.

Your first step is to install an AND gate (74LS08) into your breadboard.  To do this, you’ll need to identify pin 1.  There is usually a marking at one end of the chip and sometimes a small dot in the upper left corner.  The dot represents pin 1 and you should orient this chip on your breadboard with the dot facing up.  Here’s an example:

chip_insertedNotice how the IC straddles the groove in the breadboard.  The groove is a break in the contacts formed by the breadboard circuit.  Each line of holes run horizontally.  The numbers you see are the row numbers of each set of holes.  For line 30 (above), there are 5 holes in a horizontal row on the left and 5 holes on the right of the groove that are connected together.  For an in-depth explanation of how breadboards work, I would recommend reading this: How to use a breadboard.  Armed with this knowledge, I’ll continue with the circuit.

Next, you’ll need to go to your favorite search engine and find a tech sheet for the 7408 TTL circuit.  TTL can come in L, S, LS or normal package types.  The circuit number will always be “74” followed by an optional letter or pair of letters and then 2 or 3 digits like “08”.  So a 2-input AND gate can come in packages marked as 74LS08, 74L08, 74S08 or just 7408 (there are other types as well).  The package type is meaningless to this exercise so you can ignore which type of package you own (if you bought from the list above, you’ll have all “LS” type TTL circuits).  You can also ignore anything that comes before the “74”.  These characters represent the manufacturer.  So search the Internet for “TTL 7408” and you’ll stumble onto a PDF like this:

Quadruple 2-input Positive AND Gates

Now that your chip is properly inserted into the breadboard and you have a spec sheet, you’ll need to wire your power.  To form a complete circuit, each chip needs +5 volts and ground (or zero volts).  The spec sheet has a package diagram showing the pins of the chip:

ttl7408specYou’ll connect your +5 volts to the VCC pin (pin 14) and your ground or zero volts to the GND pin (pin 7).  Your breadboard should have some power runs along the side.  The Jameco board has red and blue stripes next to these power runs.  Connect your positive power supply to the red run and the ground to the blue run.  Then you can connect your chip like this:

power_connected

Next, you can connect an LED to the output.  First, let’s look at the spec sheet again and identify one AND gate that we can use.  If you examine the logic diagram you’ll see how the inputs and outputs of each AND gate is marked:

and_gate_logic_diagramThere are 4 AND gates on this chip, but we only need one.  So we’ll use the first one.  The first AND gate uses inputs 1A and 1B.  The output to this gate is 1Y.  In the pin-out diagram shown earlier, the inputs correspond to pins 1 and 2.  The output is on pin 3.  So let’s insert an LED and connect pin 3 to one side of the LED:

output_connected

LEDs are one-way devices, so when you insert the LED, make sure the long lead is connected to your wire.  If the circuit doesn’t work you can pull out the LED and reverse it.  Inserting an LED in backwards will not hurt anything.

The next step is very important because LEDs are sensitive to too much current.  So we’ll need a resistor to limit how much current is drawn by the LED.  If you don’t use a resistor you’ll hear a popping sound and you might smell something burning.  That would be the end of your LED.  If this happens, just throw it away, turn off your power, correctly wire a resistor (as I’ll describe next) and install a new LED.  As my high-school electronics professor used to say “no-burn, no-learn!”

On the short lead to your LED, connect one side of a 100 ohm resistor and connect the other side of the resistor to the blue bus bar (or ground).  To identify a 100 ohm resistor the colored stripes should be brown-black-brown (ignore the gold or silver stripe):

100_ohm_resistorResistors come in a variety of sizes.  To identify resistor sizes, you can go to this excellent website and memorize your color code (and it also includes a color code calculator).  Now your circuit should look something like this:

resistor_wired

Next, connect pins 1 and 2 to ground (or the blue bus):

circuit_done

Now, connect your power supply (plus lead connects to both red buses and the ground lead connects to both blue buses).  Adjust the voltage to +5 volts (if your power supply is adjustable).  Then turn it on… and… nothing happens.  This is the expected output.  So let’s make the LED light.  In order to do that, we’ll need to make both inputs a 1 or +5 volts.  Or do we?

TTL logic is wired in such a way that most circuits will treat an open input as a 1 or high.  So just remove the two input wires.  You can pull those wires while the circuit is on.  Notice how the LED lights up:

circuit_active

If your LED does not light, then you’ll need to troubleshoot.

  • Double-check to make sure all your wires are connected to the right pins.
  • You can see in the picture above that my IC is inserted between rows 56 to 62.  Row 56 on the right side is the positive connection.  Make sure the red bus on the right side is connected to the positive power supply lead.
  • Check the blue bus on the right side to make sure it is connected to ground.  Then check both the blue and red buses on the left, they will also need to be connected to the power supply.
  • Disconnect the wire from pin 3 of your AND gate and connect it right to the red bus.  Did the LED light up?  If not, then you need to check that the LED and resistor are wired correctly.  Maybe the LED is in backwards?
  • Make sure pin 14 (upper right) of your chip is wired to positive power and it is +5 volts.
  • Make sure pin 7 (lower left) is wired to ground (or the blue bus).
  • If the LED lights, but your circuit still doesn’t work, the chip could be bad (not likely, but you never know).  Turn off your power supply, remove the chip from the breadboard and insert another 74LS08 chip.  Make sure the pins are lined up exactly as the previous chip was lined up.

If your circuit is working, then you should experiment with all the combinations of inputs for your AND gate.  There are 4 possible inputs to a digital circuit that has two inputs.  Here’s a truth table of what the 4 inputs are for an AND gate:

and_gate_truth_tableAs you can see the circuit will only light if both inputs are a 1 or open.  If either input is a zero, then the light will go off.

The 74LS00 NAND gate can be substituted for your AND gate.  Make sure you turn off your power supply before removing one chip and inserting a new one.  Also be careful to line up the pins the same.

If you successfully tried the NAND gate, the NOR and OR gates are also identically pinned.  The inverter, however, is not.  So don’t attempt to wire the inputs and outputs the same because the inverter only has one input.  So pin 1 is the input and pin 2 is an output.  Feel free to connect the output of your 7404 to the LED (pin 2) and try pin 1 with high and low inputs.

Review

So what did we learn?

  • LEDs will burn out if we don’t limit the current they draw with a resistor.
  • LEDs go one way and the long lead is wired to the positive supply.
  • TTL chips are marked to identify pin 1.
  • TTL logic treats an open input as a 1 or a high.
  • We learned the resistor color code scheme.
  • We learned how to find and read a TTL IC spec sheet.
  • We learned how a breadboard works.
  • We learned how to wire power to a TTL chip.
 

Digital Logic Simulator Progress

Summary

In this post I’m going to talk more about creating simulation software and the difficulties of inventing something new.

Writing Software is Like Working in a Sausage Factory

Writing new software is more of an art than a science.  Sure, we call ourselves scientists and we have methods and proven algorithms for getting things done “right.”  At the end of the day, it’s a bit of trial and error.  Sometimes a software development project contains a lot of unknowns.  As an advanced software engineer, my daily routine consists of mostly “unknowns.”  I’m the guy who has to “figure it out.”  That’s my job and that’s what I enjoy doing.  When I create software for my hobbies, I run into the same problem.

I start a project with all kinds of great ideas about how the software will work, what algorithms I’ll use and all I need to do is type in the code.  Then I have to troubleshoot.  First I’ll find some simple bugs.  Then I’ll dig into deeper bugs and hopefully, what I’ve built works as expected.  Otherwise, I might spend an enormous amount of time trying to find a bug that turns out to be a flaw in my initial assumptions.  This will be followed by a re-design and a lot of refactoring.  On really rare occasions, I’ll throw out my code and start over.  Actually, I don’t throw anything away these days.  There’s version control, unlimited cheap storage, etc.  No need to throw it out, just archive for future review (if I need to).

Once the program works, then I have to do some cleanup work.  There is usually some dead-code that needs to be removed.  Also, code formatting might take a back-seat when I’m trying to figure out an algorithm.  That needs to get cleaned up.  Then there are “TODO:” notes littered all over the place.  I’m really bad about getting back to those.  They can be handy, but they can multiply quickly.

My development process usually goes like this:

  1. Create a library to contain my code.
  2. Create a test project to unit test my library code.
  3. Create a shell of the first object and create one or more empty unit tests (with Assert.Fail() or something similar in the body of the test method) of features that I’ll need.
  4. Create code for the first feature, add code to the unit test that applies.
  5. Make the unit test pass.
  6. Repeat

Sometimes I create a console application so I can use logging to do my troubleshooting.  This occurs when things get more complicated and I need to integrate pieces together.  If I want web output, I’ll create a website project and if I want a windows graphical screen output, I’ll just create a Windows Application project (all in the same solution).  I can switch which project is the startup project, so I just keep all the projects together where I know they are related.

Of course, this is the Sausage Factory.  It get messy inside and it’s not for the faint of heart (aka, non-technical).  For those who have never written a program, it just appears that I’m a zombie at a keyboard typing in strange words and characters.  For those who have written more than an introduction-level program, they’ll just nod and smile.

The Digital Logic Simulator

One type of program that usually starts with the most unknowns is the simulator program.  A simulator program is an abstract representation of something in the real world.  The Digital Logic simulator just simulates physical logic circuits that can be built with TTL (Transistor-Transistor Logic) circuits.  This simulator is not intended to be electrically accurate, only accurate in the sense that I can simulate the timing of real circuits.  There are already software packages on the market that are electrically accurate and some are extremely good (and they have the price tag to go with them).  I’m doing this as a hobby, so I expect to gain some knowledge and I’m also doing this as a blogging subject so I can pass along my knowledge to anyone who wants to learn more about digital logic and simulators.

When I setup this simulator, I created arrays (or lists) of voltages that are applied to inputs and outputs.  Each array cell represents a voltage sample for 1 nanosecond of time.  So far I’ve kept the voltages to 5 volts and zero volts and assumed that there are no voltages in-between.  Will I exploit the capability of setting any sample to any voltage?  I’m not sure yet.  My current concern is the timing aspect of it all.

To simulate the operation of a circuit, I have to translate inputs into outputs.  So input voltages are copied to the outputs of simulated wires (since a wire just conducts the voltage to the other end).  Logic gates can require anywhere from 1 to dozens of inputs in order to determine what the output voltage is.  So I have written objects and methods to represent how a gate will handle inputs.  Then I have setup special connection objects that can translate from one gate output to other gate inputs.  In order to make it all work I have created a circuit object that begins with the input data and attempts to propagate the voltages from the inputs through all the wires and gates until the outputs are known.  This algorithm works…. to a point.

One of the first problems I ran into using the input to output algorithm is that there could be unknown inputs to gates.  This happens because two different input signals to a gate might travel through different numbers of other gates.  Like this:

sample_1

As you can see the signal from input “A” will arrive at gate 1 before the result of gate 0 arrives (because inputs B and C need to be processed through gate 0 first).  So if the circuit algorithm tries to process gate 1 before gate 0, then one of the inputs is still unknown.  My solution (for now) is to mark all outputs as “unknown”, then attempt to process each gate.  If the inputs to a gate are all known, then process the gate and translate the output.  Then I run through the circuit again to see if I can determine more gate solutions.  This can continue up to 10 times, in which I assume the circuit cannot be solved.

The next big problem was the flip-flop.  This was a very difficult problem because the flip-flop is a chicken-and-the-egg problem.  The outputs are fed back into the inputs of the opposite NAND gate.  So the inputs are always unknown.  As I mentioned in one of my earlier blog posts, I can get around this type of problem by being able to compute the output of a gate with some unknown inputs as long as I have one or more inputs that can determine the output.  In other words, if an AND gate contains one input that is a zero, then it doesn’t matter what the other inputs equal, the output will always be zero.  With this assumption, I can determine outputs with minimal inputs and get around the flip-flop issue.

Next, I discovered that one of my virtual circuits contained a missing input connection.  I decided to create some test methods that I can use in my unit tests to determine if the circuit is valid to start with.  First, I need to make sure there are no open inputs on any gates.  So I have a method to test this.  Then I needed to make sure there are no two or more outputs connected together.  That would be a short circuit.  Last, I needed to determine if, at the end of a circuit run, there were any wires that contained voltages at the source end that were different from the termination end.  This would be an invalid circuit configuration and cannot happen in the real world.  So after running a circuit, I check the wires and if that passes, then I’m on to unit testing the known inputs with the outputs to determine if the circuit is correct.

I can create very complicated circuits out of gates.  My next trick will be to create circuits of circuits.  I’ve tried a couple of algorithms to make this work.  I’m hoping to come up with a plan that would allow me to connect circuits together and treat the whole thing the same way I treat a circuit.  Unfortunately, this is not as easy as I had hoped.  One of the problems is that I have to run a circuit in order to get the outputs.  So I connected two Full Adder circuits together into a two-bit adder like this:two_bit_adderI know what the logic table looks like, so I created the unit test for this circuit before I built it.  Then I built the circuit and I ran into a problem.  The bottom adder requires the carry out from the top adder in order to perform its calculations.  In addition to the sequence of operations problem, there is also the fact that the output of the first adder has a connector object that must copy the voltage from one end of the wire to the other.  Before anything starts though, the inputs must all be copied to the circuit inputs.  Fun times.

The program is rather slow already.  I’m OK with the simulation running slow, I’m not looking to run this in real-time or to produce a lot of data in a short amount of time.  However, the slowness is going to compound when I get to the circuit of circuit level (and beyond).  So I’m re-thinking my algorithm.

New Circuit Algorithm Ideas

One algorithm I’ve been thinking about involves starting with an output and working backwards recursively to find enough inputs to satisfy a known signal.  In the case of the two-bit adder, I can start with the output S0.  This output will require Cin (which is hard-wired to zero volts), A0 and B0.  For S1, I’ll need Cin, which requires the result of Cout of the other adder circuit.  Then I’d need to find out that output first and so on.  This algorithm will work except for one tiny problem.  The timing of it all.

To obtain the timing, I’ll need to go forward through the circuit.  There are a few ways I can implement this.  First, I can just run my recursive backward seeking algorithm until I get to the inputs and just unroll my recursions and fill in the arrays as I go.

Another idea I have in my head involves the same algorithm, trace from output to input recursively, but just store the paths that the electrical signal must follow.  Then trace the signals from inputs to outputs using the order setup by the recorded paths from the recursive algorithm.  This would be a two-step algorithm.  Find the paths then translate the signals.

Some pitfalls to watch for:

  • These circuits could become really large and recursion can get slow.  If recursion becomes a problem, I’ll be forced to use a stack.
  • Another issue will involve infinite recursion.  This I know will happen in situations like the Flip-Flop. I’ll need to design in a safety cut-off before I start using recursion for anything.  I’ll also have to see what I can use for a cut-off in a Flip-Flop circuit.
  • Testing recursion can be difficult.  I’ll need to think about how I’m going to test this thing.

Fortunately, I already have a few circuits in the solution that I know work.  So I can setup my new algorithm and run some existing unit tests to verify that the new algorithm works properly.  I can also retain my circuit verification methods since that will not need to change.

One other assumption that my circuits make is that wires are perfect.  There is no delay calculated for wires.  Wires are represented by the wire object and the connection object so I can add delay time to these.  However, the delay time for a wire depends on it’s diameter and length.  Both of these are not normally known until a physical design is determined.  For now, I’m going to continue to assume a delay of zero, but anyone using this code to simulate a circuit should be aware of this limitation.

I guess it’s time for me to get to work…

 

The ALU

Summary

I’ve added the 74181 ALU TTL circuit to my logic simulator.  This blog post will discuss the differences between this ALU and the 74381 that I discussed about in a previous blog post.

The 74381

I added the 74381 ALU (Arithmetic Logic Unit) circuit to the logic simulator a few weeks ago and then I decided to build some real circuits to experiment with.  I mentioned in my previous blog post that the 74381 was not available for purchase (at least I haven’t found a supplier yet).  I decided to add the 74181 circuit to the emulator.  This circuit has a few quirks.  First, there are two truth tables in my logic book: Active High Data and Active Low Data.  The same circuit can be represented as though the outputs are inverted or not.  The difference is that the logic functions that are used are in a different order in the logic table.  For instance: In the active high version the A plus B function is activated by S0-S3 equal to H,L,L,H and the carry in must be H.  In the active low version, the s0-s3 are identical but the carry in must be L.  For the F = 0 function in active high, S0-S3 must equal L,L,H,H and M equals H.  For active low S0-S3 must equal H,H,L,L and M equals H.  Oh what fun.  So I chose the active high table and just setup my unit tests to assume that the outputs match that setup.  The fact that this chip can represent active high or active low means that there are 4 select bits or what seems like 16 functions.  However, there are functions in active high that are useless because the selector is used for active low functions.

The functions that are supported by the 74381 are also on the 74181:

  • Clear
  • B – A
  • A – B
  • A plus B
  • A + B (OR)
  • AB (AND)
  • A xor B
  • Preset (all 1’s)

The 74181 also supports not A, not B and A = B.
Here’s the circuit for the 74181 (click to see full sized image):

ttl_74181

I had a lot of fun creating that circuit in Visio.  I opted to create gate 57 as a special negated input OR gate instead of using two inverters on the input.  I’m only testing this circuit with the “perfect” TTL circuit.  I might have to do some fancy foot-work to make the timing come out right for the real circuit.  My point in mentioning this is that the reason why gates are represented with negated inputs instead of showing two inverters is that the circuit inside the chip is created with transistors and it was designed as a special negative input OR gate to cut the delay time.  If an additional transistor is used on each input as inverters, then the circuit path for gate 57 will be slower.  It appears that this circuit was designed to equalize the delay time from the inputs (a0-a3 and b0-b3) to the inputs (f0-f3) and to reduce any transients that can occur if one path is longer than another.  Although the inverter on b0-b3 probably causes a delay between the a and b inputs.  As you can see by the next diagram there are 7 levels of gates that a signal must pass through (no feed back paths):

ttl74181_critical_pathGates 34 through 36 appear to be behind the row of AND/NAND gates in zone 4, but they are at the same level of circuitry.  No signal goes from level 4 to level 5 without passing through a gate.  There is even a one-input NAND gate to ensure that the signal delay through gate 37 is equal to all other signals arriving at gate 53.

One thing I discovered while researching ALUs is that this circuit shows up in a lot of class exercises for electronic engineering classes.  I’ve found some pretty good power point slides showing the basics of half and full adders up to the 74181 circuit itself.

Here’s some history of the 74181 that explains why it’s so popular: http://apollo181.wixsite.com/apollo181/about.  The 74181 also has it’s own Wiki: https://en.wikipedia.org/wiki/74181.  One thing to note is that there are two circuits shown for this chip.  The TTL logic book has the circuit that I translated into Visio above and many of the on-line references, including the wiki page, show a slightly different circuit.  When you look at the circuit diagram in the Wiki article you’ll see an AND gate and an inverter instead of an XOR gate.  This is not a direct substitution as you can see from this:

xor_vs_and_inverter

I have not investigated the reason for this difference and it could be a correct circuit with a difference in the selection of the functions used by the chip.  I also stumbled across a data sheet for a Motorola brand 74181 and it had a wiring mistake on the circuit diagram:

motorola_datasheet_mistakeConnecting two inputs to the same wire would be a short-circuit.  If you go to the Wiki article you’ll notice that the M wire should be inverted and should connect to the other wire of the NAND gate at the bottom.  The Cn wire should connect directly to the NAND gate where it currently connects (after the inverter).

The circuit above came from my Logic Databook, which was published by National Semiconductor in 1981.  That circuit works correctly according to the unit tests that I setup (using the Active High Data truth table).

Where to get the Code

You can go to my GitHub account to get the latest and greatest code (click here).  This project is still in the research phase so there will be changes coming.  You can get the specific version of this code for this article by downloading this version: (click here).

 

Simulating TTL Circuits

Summary

I’m going to continue with my logic simulator project in this post.  This project has turned into a serious obsession, ahem, hobby.  My final goal is to be able to simulate a full computer circuit.

TTL Logic

As I’ve mentioned in my previous posts, there is a wiki page for TTL logic that lists all the 7400 series circuit numbers (click here).  Once you find the right package number you can search for the actual data sheet.  For example, the 7408 is a quad AND gate circuit.  Here’s a data sheet for the 7408 chip manufactured by Texas Instruments (click here).  To simulate a 7408 circuit, I created an object that has a super-class of the AND gate that I used earlier.  I also fixed the number of inputs to 2, since the 7408 contains only 2-input AND gates.  Technically, I should put 4 distinct AND gates inside the 7408, but for now I’m just going to create package names for the common circuits.  Any TTL package that is directly represented by a circuit I created before will become a trivial setup just like the AND gate / 7408 circuit.  For more complex circuits, I’m going to wire up entire circuits.

The first circuit I attempted was the 74157.  This is a selector/multiplexer circuit.  The reason I chose this circuit is because it has a simple connection pattern:

74157_circuit

In order to create the circuit, I numbered the gates that would be needed, then I created connections for each output, starting with the labelled inputs.  So A1 connects to AND gate 0, input number 0.  AND gate zero connects to OR gate 8 input 0.  Etc.

I setup some unit tests to make sure the circuit operated correctly.  The unit tests are not exhaustive, so there could be a wiring error, but it looks good for now.

Next up is the 7447.  This is a BCD to 7-segment decoder circuit.  The 7447 is the common anode version (there’s a common cathode version as well).  What that means is that the 7-segment outputs are reversed.  If the output is a zero, then the LED is on and if the output is a 5-volt output, then the LED is off.  Anyway, here’s the circuit:

ttl7447

The 7447 took some effort to troubleshoot.  One of the complexities of this circuit is the feedback into gate 9.  I was forced to rewrite the circuit emulator to make this work better.  The current algorithm runs like this:

  1. Propagate the input signals to the gates that they connect to.
  2. For each gate, in order, attempt to compute the output with the inputs given, then propagate to the next inputs.
  3. At the end of processing all gates, if there are unknown signals, go through the list of gates again.
  4. If, after 10 attempts to process all gates yields unknown signals, then go to the first signal and set it to a zero (this is for flip-flops).
  5. Attempt to process all gates again.

Some issues came up because I missed a connection.  This can cause a gate to have a missing input and the circuit never completes.  So I wrote a method called VerifyAllGateInputsConnected().  This method will make sure all inputs have at least one connection.  The purpose is only to verify the circuit is wired.  In the real world TTL inputs normally act as a high or 5 volt signal.  It’s not good practice to leave an input connection open.

Another check I perform is the CheckValidConnections check.  This method will make sure the source and termination of each signal is the same voltage after a circuit is run.  If these are different, then the signal was not propagated.  The only time this happens is when there is a feed-back circuit (like the feed-back to gate 9 above) that flips the output of the gate, but the new output is not propagated.

The last check that I will be coding (and have not completed yet) will involve the verification that there are no pair of outputs connected together.  One aspect of logic circuit is that one output can go to multiple inputs.  However, if the outputs of two gates get connected together, you form a short-circuit when one gate goes to 0 volts and the other goes to 5 volts.  So I’ll need to create a verify method that can test to see if two outputs go to the same gate input.

Feeling bold, I continued on to the next circuit.  The 74381 4-bit arithmetic logic unit.  This is a beast, and it took me 3 days to type in the connections between gates (and 2 days to fix the bugs).  Here’s the circuit:

ttl74381

Technically, there are two different chips here, the 74381 and 74382, but I just added both circuits to the same chip so I can use them interchangeably.  I have created unit tests for the mode selector (s0, s1 and s3 decoder) that is at the top of the circuit.  This unit test only checks to the outputs of the gates 19 through 22 and 14, 15 and 16:

ttl74381_mode_decoder

This was necessary in order to break the task of troubleshooting down to something that was bite-sized.  The truth-table to the left of the circuit is my hand-computed logic of what gates 19, 20, 21, 14, 15, 16, 22 would produce for different combinations of S0, S1 and S2 inputs.  This was used for the unit test inputs and expected outputs.

Once that circuit was tested, I proceeded to test one pair of inputs (starting with a0 and b0) for the ADD mode only.  Here’s a close-up:

one_add_circuit

I’m using Visio for my circuit, so I can change the color of my lines to red to represent a 1 (or 5-volts).  I set the corresponding outputs of gate 19 through 22 for the ADD mode.  I also set the carry input (Cn) to zero.  Then I used all 4 possible combinations of A0 and B0 to test each output of gate 63 and gate 64.  Gate 63 is the sum of the A and B inputs.  Gate 64 represents the possible carry.  So this circuit behaves like a full-adder circuit.  Therefore I know what the expected outputs should be:

adder_truth_table

One of the problems with the 74381 is that it’s not easy to find.  Jameco electronics doesn’t seem to sell them.  My real-world solution is to use a PLD or Programmable Logic Device.  Technically, I could incorporate multiple 74381s into a complete circuit of an 8, 16 or 32 bit ALU.  Before I build such a thing, I want to perform more simulations to determine what it would take to create the circuit.

One other thing of note: I have not tested this circuit with normal gate timing.  These TTL circuits are only tested from the unit tests using a perfect gate (i.e. no delay timing).  I’ll need to setup some signaling and run a normal TTL gate to see how the outputs behave in the real world.  I should also wire-up a few of these circuits and see if they behave identically.  This is how a simulation is normally validated.

I added a GateOutput method to the circuit object for troubleshooting purposes.  The first parameter is used to define which gate to read and the second parameter is the timing number (normally zero).  This allows me to read any gate output in a circuit for unit testing purposes.  That’s how I was able to unit test the sub-circuits above.

More Troubleshooting Needed

The current code (version 748a78f on GitHub) has a new bug with the JK Toggle.  This shows up in two unit tests that fail (jk_toggle_once and jk_toggle_twice).  I also noticed that there is an anomaly in the starting state of the Master/Slave Flip-Flop as you can see in this output waveform:

jk_flip_flop_anomaly

The Q and QBar should always be opposite.  It seems that the startup of the circuit did not propagate the gate outputs properly.  I’m assuming this is due to the connections being valid, but the gate outputs are not.  I think Flip-Flops are going to be the death of me!

What’s Next?

That’s a good question.  I have several ideas in my head:

  • Create a static RAM circuit and and EPROM circuit.  This will enable me to build a small simulated CPU.
  • Create more TTL circuits so I have a full library to work with.
  • Enhance the interface to show inputs and outputs.  Maybe some LED lights or 7-segment displays or even 16-segment displays.  I could also simulate a dot matrix output like a digital display device (color or black and white).
  • Complete the circuit-to-circuit capability.  I want to be able to wire circuits to each other and create larger circuits.
  • Create programmable gate array circuits.  I could feed a program mask as a set the fuses before running the circuit.
  • Store a circuit definition to a file and read it in when needed instead of creating new objects.

Where to get the code

You can go to my GitHub account by clicking here and download the latest version.  This project is in progress, so a newer version might be uploaded by the time you read this blog post.