 Search: Lycos Tripod Planet Share This Page Report Abuse Edit your Site Browse Sites  « »  # Chapter 4 - AND-OR networks and Computer ROM

## AND-OR networks

An AND-OR network consists of a series of inputs, some possibly connected to inverters first, feeding into AND gates. The outputs of these AND gates are then fed into an OR gate. The diagram below shows an example of a simple AND-OR network: In this diagram, you will notice that inputs are duplicated - just assume that both the lines marked A are joined together, and so on for the other two inputs.

 Let's consider what input would cause the first AND gate to produce a 1 output. The AND gate only produces a 1 output when all its inputs are 1. This only happens when A and B are both 1 and C is 0 (because the input to the AND gate from C passes through an inverter first). In other words, for this gate to produce a 1 output, A = B = 1 and C = 0. All other combinations of A, B and C will cause this gate to produce a 0 output.  What about the other (lower) AND gate? In this case, all the inputs to the AND gate are 1 only when A and C are both 1, and B is 0 (since the input B passes through an inverter before it reaches the AND gate). In other words, for this gate to produce a 1 output, A = C = 1 and B = 0. All other combinations of A, B and C will cause this gate to produce a 0 output.

However, the outputs of both these AND gates are then passed through an OR gate. This will produce a 1 output if either of the two AND gates produces a 1 output. (Theoretically, of course, it would also produce a 1 output if both AND gates produced a 1 at the same time, but this can't happen since each responds to a different combination of inputs). The OR gate therefore produces a 1 output when either A = B = 1 and C = 0, or A = C = 1 and B = 0. All other combinations of inputs cause the OR gate to produce 0.

We can summarise this in the form of a truthtable. I have included columns for the two AND gates as well as a column for the final output of the network:

 A B C Upper AND gate Lower AND gate Final output 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 0 1 0 1 1 1 1 0 1 0 1 1 1 1 0 0 0

If you compare the final column of the truthtable with the circuit, you will see that each of the two AND gates corresponds to a line in the truthtable which produces a 1 output. In fact, it is possible to represent any truthtable using just an AND-OR network, with each line in the truthtable corresponding to a 1 output represented by its own AND gate. Each of the outputs from these AND gates is then fed into a multi-input OR gate which then produces a 1 output whenever one of the special combinations of inputs appears at the input to the AND gates, and 0 otherwise. The following diagram, for instance, shows an AND-OR network with 4 inputs (called, rather unimaginatively, A, B, C and D). The first (upper) AND gate responds to the combination A = C = D = 1 and B = 0. The middle AND gate responds to the combination A = D = 0 and B = C = 1. The third (lower) gate responds to the combination of inputs when all the inputs are 0. Work through the circuit for yourself to satisfy yourself that this is indeed the case.

It is rather inconvenient to reproduce all those inverter gates, so for convenience, we sometimes write them simply as circles on the inputs to the gates. The diagram above could just as easily have been drawn as follows: An AND-OR network is not necessarily the most efficient way of constructing the circuit. It may be possible to build an equivalent circuit with fewer gates, or using gates with fewer connections. You may already have spotted that the circuit that you saw at the top of this section (the one with the three inputs A, B and C) could actually have been written more succinctly as follows: This is true since the circuit should only produce a 1 when both A = 1 and B and C are different (as given by the XOR gate). Although the AND-OR network does not necessarily produce the most efficient solution, it does at least show that it is possible to construct a circuit for any truthtable with any number of inputs you care to mention. In the chapter concerned with Karnaugh maps we will deal with a method to improve the efficiency of AND-OR networks to remove some of the redundant gates and inputs.

To construct an AND-OR table to fit a given truthtable, follow these steps:

1. Draw one AND gate for each of the lines in the table for which the output of the truthtable is 1. Each of these AND gates should have the same number of inputs as there are on the truthtable.

2. For each AND gate, draw its inputs connecting to the labelled inputs in the truthtable, putting an inverter in between if that input is specified as 0 at that point in the truthtable.

3. Draw an OR gate with as many inputs are there are AND gates. Each input of the OR gate is fed from the output of a different AND gate.

## The equivalence between AND-OR and NAND-NAND

The following diagram shows an AND-OR network on the left and an equivalent circuit on the right. If you work out the truthtables for both these circuits (as I have done below), then you will find out that they are exactly the same: A B C D AND-OR output NAND-NAND output 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 1 1 0 1 0 0 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 0 0 1 0 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1

The same would be true if we had more inputs than shown in the diagram. In general, you can prove (using something called de Morgan's law, which we will meet in a later chapter) that any AND-OR network can have all its AND gates and OR gates replaced by NAND gates, with no rewiring of the connections, and it will still have exactly the same truthtable.

This is an advantage as it means that AND-OR networks (or NAND-NAND networks as I should really call them) can be constructed using only one type of logic gate - the NAND gate. Producing silicon chips containing only NAND gates is a lot simpler and cheaper than producing silicon chips with a mixture of AND and OR gates on them.

## Computer Read-Only Memory (ROM)

Read-Only Memory is so-called because it can be read by the computer's processor (i.e. its contents is accessed) but it cannot be overwritten or altered. We can implement it using chips containing logic gates sure in the knowledge that once the circuit on the chips has been set up it will never need to be altered. The same cannot be said of the other type of computer memory - Random-Access Memory (or Read-Write Memory) - which the computer needs to access and change, and that sort of memory requires more complicated silicon chips.

Let's consider memory for a moment. A computer's memory consists of a series of slots which can hold binary numbers. The size of the binary numbers is usually a power of two. For instance, old computers had 8-bit memory, which could hold binary numbers specified by 8 bits, i.e. from 00000000 to 11111111. Later computers had 16-bit memory (0000000000000000 to 1111111111111111) and nowadays we have computers with 32-bit memory (no, I'm not going through all that again!) There is no specific reason why computers should have memory widths which are only powers of 2. It is perfectly possible for a computer to have memory which is 5 bits wide, or 13 bits, or 106 bits for that matter. However, powers of 2 seem to be preferred.

Each of the slots in memory has an "address", which allows the computer to specify which slot it is interested in. The address is specified on a series of wires (called an address bus) in the form of 1s and 0s, so 00000010 would represent address 2, 10100000 would represent address 160 etc. (Any of this sound familiar?) Again, the total number of addresses that you can specify on the address bus is always a power of 2.

Memory chips are sold according to how many "bits" (binary digits) they contain. An 8k memory, for instance, contains 8 kilobits (not kilobytes in this case) of memory. This means 8192 bits. However, simply knowing how many bits there are in a memory chip is not enough. You need to know how many output bits there are.

One possible arrangement for the 8k memory chip is for it to consist of 1024 memory locations, each of which stores and produces an 8-bit value, as shown in the following schematic diagram: 1024 memory locations require 10 address wires (as 210 = 1024), so there are 10 address lines and 8 data lines. There is also one control wire called an Enable signal. When this wire holds a 1 signal (as opposed to a 0 signal), it indicates to the memory chip that it is supposed to wake up and deal with the address on the address bus (i.e. read a value into or out of a specified memory slot). A couple more connections provide the power to the chip, but I have missed these out from the diagram for simplicity. You'll notice that the address lines have arrows that point into the chip (as the memory chip receives address requests from the processor), whereas the data lines have arrows that point away from the chip, as the memory provides the data for the processor. Had the memory been of the read-write variety, then the arrows on the data lines would point both ways.

Another possibility is for the 8192 bits to be arranged in the form of 2048 memory locations each containing a 4-bit number. The most common form is for them to be arranged in the form of 8192 address (specified by 13 address lines, as 213 = 8192) each holding only one bit of data, as shown in the following diagram: Now, it may seem to you that this is rather a silly option. After all, who is going to be interested in memory where all the numbers are only one binary digit, 1 or 0? Well, these chips aren't used in isolation. They are grouped together to form 8-, 16-, 32-bit numbers etc. (or other values such as 23-bit or 17-bit numbers if you insist!): In the diagram above, the address bus is connected to each of the chips, so each one gets the same 13-bit address. (Yes, I know 13 bits isn't a power of 2, but I started talking about 8k chips above so I had better continue it to the bitter end). Because there are eight chips, each producing 1 data bit, next to each other, then together they produce an 8-bit data number. Of course, if you then decide that you want your memory to be 20 bits wide, or 32, or 64, then you just add more memory chips of the same type next to those you already have, and make sure that each one is wired into the address bus. You must also make sure that all the Chip Enable wires are connected together and to the same control signal. In this way, when the computer wakes up one memory chip, they all wake up, and all contribute to the same data item.

You may, by now, be wondering why I am mentioning this in the middle of a tutorial about Digital Electronics. Well, each of these memory chips consists of a series of inputs in the form of the 13 address lines, and a single output in the form of the data bit. This can easily be done with an AND-OR network programmed into the chip. This network would have 13 inputs, and would be programmed so that it produced the correct output for every possible combination of inputs. Providing all the memory chips were programmed properly, then when they were all connected to the address lines, they would co-operate in producing the correct data patterns for each of the 8192 addresses that could be specified on the address bus.

## The Uncommitted Logic Array

This is a type of memory chip which is also known as a PLA (Programmable Logic Array). PLA chips are a version of ROM that can be programmed by the user and then inserted into a computer. The memory patterns that the chip is supposed to produce are "burned" into the chip using a special piece of equipment, and then the chip is identical in function to normal ROM.

PLA chips are manufactured usually using NAND-NAND technology as this provides all the gates needed for an AND-OR circuit. The basic AND-OR circuit is equivalent to a NAND-NAND circuit as we have seen above, and the inverters needed for some of the inputs can be made from NAND gates by connecting their inputs together (A NAND gate with both its inputs connected together and connected to the same input digit acts just like an inverter - prove this to yourself).

When it is sold the PLA consists of all the possible connections in place. The equipment used to program a PLA then "burns out" the connections that are not required, leaving only the connections needed to produce the required truthtable. The equipment is controlled by a computer program, so the user simply enters the required patterns of 1s and 0s to be produced for all the addresses using a simple editor program, and the computer does the job of turning these into the required voltages for burning the PLA.