expand_less
In this unit we learn about the atomic bits of computation. Many things have been tried, that is the history course, all modern systems are composed of subsystems that are built with logic blocks described by [[Boolean Algebra]]. We will start with simple static logic circuits, and you will learn to use [[Logisim]] and other tools to build complex logic elements from nested modules that can be realized as physical circuits [[Chips and Boards|directly]] or programmed into an [[FPLA.]]
Simple Gates
Abstractly, a gate maps some number of inputs into a single output, and sometimes we generalize to compute multiple outputs from a set of inputs. Starting from the simplest, refer to the Simple Gates circuit in the examples, we have the 1 to 1 functions, and we can see there are exactly four of them or 2<sup>2</sup>, then 2 to 1 with 16 possible functions, including the three examples (or 2<sup>2*N</sup>). In any given circuit technology, we only have to implement a small number of gates and we can build the rest from them.
One input is either just a wire (no change), or it is NOT, where the output is the opposite value to the input. Well, lets back up a sec, actually there are 4 functions of two inputs, but two of them are degenerate in the sense of really being zero input funtions, that is always true (1) and always false (0).
Also, sometimes a technology will have a [[fanout limit]], but we can still get around that by putting in two NOT gates back to back to in effect re-amplify the input so it can drive more loads. There could also be a multistage amplifier at the edge of the microscopic parts of a chip and the pads the lead out to the [[chips and boards|board]] and the rest of the world. But lets not worry about that in thinking about logic. We can rely on [[standards and modules]] to interface with the analog and digital protocols that will integrate our logic elements with other systems and networks.
Let that be the first lesson, sometimes even one bit of logic is complicated, and entire systems can exchange data in multi-layered protocols. But as logic, there are two tables:
0 -> 0, 1 -> 1 and 0 -> 1, 1 -> 0
Then on two inputs, we have a table with four binary values, so there are 16 possible functions. (add example tables as graphics) Lets see how that can work. For one bit in, I have a table with two rows, one for each input value, and it has two bits in it, one table entry for each row. In that table, 00 and 11 are the always true cases and 01 and 10 are the other two, but we have to now what order they are to know which is whiich. If 0 is first, the 01 is the itentity function and 10 is NOT. If the sixteen are described in four bits, one for each combination of values of A and B, then again some are reducable to zero or one input gates if you assume a simpler gate where one or more inputs isn't connected to anything. We often will use [[hamming code]] order, so the coding of ABCD bits below will match AB-00,01,11,10. You can examine these in the simulator by grounding or pulling up an input.
So, lets look at all sixteen
0000 Always False (reduce to zero)
0001 A AND NOT B
0011 A (reduce to one)
0010 AND -- NOT (A OR B)
0110 B
0111NOROR -- NOT A AND NOT B
0101 XOR -- NEQ
0100NOT A AND NOT B
1100 NOT A (reduce one)
1101 NOR -- NOT A AND NOT B
1111 Always true
1110 NOT (A AND NOT B) -- NOT A OR B
1010 XNOR - EQ
1011 NOT (NOT A AND B) -- A OR NOT B
1001 NOT B
1000 NAND
You should be able to build and test any of these with a few built-in gates, and you can see how these might be optimized when I need to compute one or more of these functions, and that it might be a little different in different technologies. An [[FPLA]] element might load four bits to program a general two element gate, or I might be able to program the inputs and crossovers of an [[Logic Array|NxM logic array]].
We know about six of them, two zero degenerates, two one degenerates times two because there are two inputs. Then we have the six symetric operations, AND, OR and XOR and their negations, NAND, NOR and XNOR (which you could call EQUAL, since it is true when the two inputs are the same. If you invert one of the inputs, there are for more, two ANDs and two ORs. XOR is missing, why? That's all 16. Note that the two forms on many of the lines are application of [[https://en.wikipedia.org/wiki/De_Morgan%27s_laws|De Morgan's law.]]
Simple Gates
Abstractly, a gate maps some number of inputs into a single output, and sometimes we generalize to compute multiple outputs from a set of inputs. Starting from the simplest, refer to the Simple Gates circuit in the examples, we have the 1 to 1 functions, and we can see there are exactly four of them or 2<sup>2</sup>, then 2 to 1 with 16 possible functions, including the three examples (or 2<sup>2*N</sup>). In any given circuit technology, we only have to implement a small number of gates and we can build the rest from them.
One input is either just a wire (no change), or it is NOT, where the output is the opposite value to the input. Well, lets back up a sec, actually there are 4 functions of two inputs, but two of them are degenerate in the sense of really being zero input funtions, that is always true (1) and always false (0).
Also, sometimes a technology will have a [[fanout limit]], but we can still get around that by putting in two NOT gates back to back to in effect re-amplify the input so it can drive more loads. There could also be a multistage amplifier at the edge of the microscopic parts of a chip and the pads the lead out to the [[chips and boards|board]] and the rest of the world. But lets not worry about that in thinking about logic. We can rely on [[standards and modules]] to interface with the analog and digital protocols that will integrate our logic elements with other systems and networks.
Let that be the first lesson, sometimes even one bit of logic is complicated, and entire systems can exchange data in multi-layered protocols. But as logic, there are two tables:
0 -> 0, 1 -> 1 and 0 -> 1, 1 -> 0
Then on two inputs, we have a table with four binary values, so there are 16 possible functions. (add example tables as graphics) Lets see how that can work. For one bit in, I have a table with two rows, one for each input value, and it has two bits in it, one table entry for each row. In that table, 00 and 11 are the always true cases and 01 and 10 are the other two, but we have to now what order they are to know which is whiich. If 0 is first, the 01 is the itentity function and 10 is NOT. If the sixteen are described in four bits, one for each combination of values of A and B, then again some are reducable to zero or one input gates if you assume a simpler gate where one or more inputs isn't connected to anything. We often will use [[hamming code]] order, so the coding of ABCD bits below will match AB-00,01,11,10. You can examine these in the simulator by grounding or pulling up an input.
So, lets look at all sixteen
0000 Always False
0001 A AND NOT B
0011 A
0010 AND
0110 B
0111
0101 XOR -- NEQ
0100
1100 NOT A
1101 NOR -- NOT A AND NOT B
1111 Always true
1110 NOT (A AND NOT B) -- NOT A OR B
1010 XNOR - EQ
1011 NOT (NOT A AND B) -- A OR NOT B
1001 NOT B
1000 NAND
You should be able to build and test any of these with a few built-in gates, and you can see how these might be optimized when I need to compute one or more of these functions, and that it might be a little different in different technologies. An [[FPLA]] element might load four bits to program a general two element gate, or I might be able to program the inputs and crossovers of an [[Logic Array|NxM logic array]].
We know about six of them, two zero degenerates, two one degenerates times two because there are two inputs. Then we have the six symetric operations, AND, OR and XOR and their negations, NAND, NOR and XNOR (which you could call EQUAL, since it is true when the two inputs are the same. If you invert one of the inputs, there are for more, two ANDs and two ORs. XOR is missing, why? That's all 16. Note that the two forms on many of the lines are application of [[https://en.wikipedia.org/wiki/De_Morgan%27s_laws|De Morgan's law.]]