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.
A table form for one input would have the four functions from above with for lines, one for each "function" where each binary digit represents the output with particular input values. So the first column here is when the input is zero, and the second when one. So we have the four functions of one input:
00 Always 0 (False)
01 Identity (same as input)
10 NOT
11 Always 1 (True)
So, lets look at all sixteen (Digits AB: 00, 01, 10 11)
0000 Always False
0001 A ANDNOT B
0011 A
0010 A AND NOT B
0110 A XOR B = NOT (A EQ B)
0111 OR
0101XORB -- NEQ
0100 NOT A ANDNOT B
1100 NOT A
1101NANDNOT --(A AND NOT AB) OR= NOT A OR B
1111 Always true
1110 NOT (A ANDNOT B) -- NOTCalled ANAND OR B
1010XNORNOT -B EQ
1011 NOT (NOT A AND B)--= A OR NOT B
1001NOTA EQ B = NOT (A XOR B)
1000 NOT (A OR B) -- Called NOR
YouFrom shouldLogic beto ableGates
Logic as above is the abstraction, the math you want your digital circuit to compute. A fact passed over above is that gates are not technically restricted to binary logic, but as a practical matter they are. We build almost everything with binary, synchronous (and we'll get into that when we talk more about timing andtestclocks anylater) logic. So the math is all Boolean Algebra as in the brief introduction above.
You won't need to know that much about how logic functions are implemented as gates (transistors) at the circuit level unless you are a specialist working for a silicon manufacturer. There are many interesting things to learn about all of that, but thesewithdays if you are designing custom logic for a fewproject, built-inyou gates,are andeither part of a big design team producing custom chips, or you canare seedesigning howwith some form of programable array logic. In these mighttechnologies beyou optimizedcan whenget Ithousands needand toeven computemillions oneof simple gates and medium scale modules either as a chip or moreon ofa thesesystem functions,chip with a processor, memory and thatother itstandard mightinterface logic.
You should beaable littleto differentbuild and test any of the simple logic functions in differentany technologies.gate Antechnology. [[FPLA]]You elementcan mighteasily loadshow fourthat bitsany tomore programcomplex logic function can be made from a generalsufficient set of one and two elementinput gate,gates. NAND or INOR mighton betheir ableown are sufficient as are either AND or OR paired with NOT. Different gate implementation may present opportunities to programoptimize that are somewwhat specific to the inputsimplementation, but in general you can compute and crossoversN bit to M bit logic function with any sufficient set of anlogic [[Logic Array|NxM logic array]].gates and there are straightforward ways to optimize for space and speed. Because of this much of this work is automated in the form of hardware compilers that can compile hardware either directly onto a custom chip or into "standard" FPGA chips and systems.
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.]]
There is a lot more, of course. Next you'll need to lean about flip-flops, simple circuits that hold state, and that will lead to clocks, timing and synchronous systems. At the edges, they blend into analog functions that implement an interface between [[synchonous logic]] and a [[Storage Media|storage]] or [[Transission Media|transmission medium.]]
If there is something not already covered, do what I do, [[Google it.]] Propose your own excercises and real problems, document your work, identify and collect resources and write lessons and knowledge dumps. Use this site as a home to build a shared knowledge base.
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.
A table form for one input would have the four functions from above with for lines, one for each "function" where each binary digit represents the output with particular input values. So the first column here is when the input is zero, and the second when one. So we have the four functions of one input:
00 Always 0 (False)
01 Identity (same as input)
10 NOT
11 Always 1 (True)
So, lets look at all sixteen (Digits AB: 00, 01, 10 11)
0000 Always False
0001 A AND
0011 A
0010 A AND NOT B
0110 A XOR B = NOT (A EQ B)
0111 OR
0101
0100 NOT A AND
1100 NOT A
1101
1111 Always true
1110 NOT (A AND
1010
1011 NOT (NOT A AND B)
1001
1000 NOT (A OR B) -- Called NOR
Logic as above is the abstraction, the math you want your digital circuit to compute. A fact passed over above is that gates are not technically restricted to binary logic, but as a practical matter they are. We build almost everything with binary, synchronous (and we'll get into that when we talk more about timing and
You won't need to know that much about how logic functions are implemented as gates (transistors) at the circuit level unless you are a specialist working for a silicon manufacturer. There are many interesting things to learn about all of that, but these
You should be
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.]]
There is a lot more, of course. Next you'll need to lean about flip-flops, simple circuits that hold state, and that will lead to clocks, timing and synchronous systems. At the edges, they blend into analog functions that implement an interface between [[synchonous logic]] and a [[Storage Media|storage]] or [[Transission Media|transmission medium.]]
If there is something not already covered, do what I do, [[Google it.]] Propose your own excercises and real problems, document your work, identify and collect resources and write lessons and knowledge dumps. Use this site as a home to build a shared knowledge base.