It’s logic and design all over again!
Deductive mathematical system, takes two boolean inputs, produces a single boolean output. Bools are either true or false.
There are binary operators AND and OR, and unary operator NOT. In our case, since we only have two elements, this boolean algebra is a field and follows the field axioms.
There are an infinite number of boolean functions, but they are not unique. In other words, they can be simplified down using the rules of logic. This is because when you have a finite number of terms, you must have a finite number of unique functions that logically combine these terms. The number of unique functions is ${latex.inline2^{2^{n}}} and there are some nice ways to express these functions as bit strings.
For example, suppose we have three inputs, A, B, C. We have ${latex.inline2^{2^{n}}} unique functions, in this case 2^8. Well, this means all of the functions can be mapped to a number in the range of 0-255, which means we can hold the function number in a single byte.
How do we map from function to function number in a uniform way?
Well, we write truth tables and then convert the values to something useful. Example as follows:
C B A Result 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1
This is the truth table for function AB + C. Notice that the bit strings CBA with C being HO bit, A being LO bit outline the numbers 0-7. Then the result bit is the result of applying the function to the inputs. We can get the function number by mapping the bit string of CBA to the bit number of the result bit string, and setting the bit in that position to the result value. So the function number would be:
11111000
Note that because there are finite numbers of unique boolean functions with n input variables, yet infinite numbers of possible expressions for each of the unique function, we came up with a standard known as canonical form.
There are a bunch of canonical forms, pick one and use it. We use sum of minterms. A term is a single literal or a product of several different literals. A minterm is a product of containing exactly n literals, where n is the number of input variables.
for example, when we have two input variables A, B, the minterms are AB, A’B, AB’, A’B’ because all the terms have 2 literals. The set of minterms is easy to generate because it lines up nicely with the binary value bit string. A’B’C’ = 000 for example. This is what makes it powerful. You take the truth table shown by the bit string mentioned above and add together the minterms that give a result of true. It’s trivial to go from form to truth table, or from truth table to canonical form.
This means it’s really easy to go from function to canonical form too. Just do the truth table, then build out the form.
Oh man, the map method of simplifying to optimal form. A classic, throwback to logic and design. Not important to go over now, but can always look it up later. Truth maps instead of truth tables :D.
In the real world just use a computer to do this.
The key point: any algorithm you write in software can be directly implemented in hardware by turning your code into boolean equations and mapping those to gates, which are representations of boolean operations in hardware. It’s also cool to know that all hardware operations can map to software.
A computers cpu is built from combinatorial circuits, which are circuits that take some inputs, and produce several outputs. The key to know is that each output of a combinatorial circuit is the output of a DIFFERENT boolean function(so inputs must be multiplexed?)
Decoders are some of the most important circuits.
One drawback of combinatorial circuits is that they are memoryless. In other words, if one of the inputs changes, the output immediately changes. There is no way to remember the old output.
We fix this using sequential and clocked logic. The way to do this is through flip flops of which there are a few kinds: set/reset, d flip flops, etc. The D flip flop works using a clock signal. Concatenating several D flip flops together forms a register. If there is a new value to write to the register, a clock pulse writes it.
Flip flops are cool, so are these circuits, but what is really important is how all this applies to cpu design and how that applies to assembly and c/cpp.