User:Paul Murray/Reverse Logic Temp Page
3 input / 3 output reversible logic gates
[edit]There are 2^3 = 8 possible combinations of 3 binary inputs xor 3 binary outputs. This means that there are 8^8 = 2^24 possible truth tables, or about 16 million. However, the requirement for a reversible gate is that for each possible truth table output there is only one input which will result in it, and so this brings the number down to 8!, or about 40 thousand.
Many of these tables are equivalent in that the truth table is identical to another table with the three inputs and/or three outputs rearranged. Thus the identity gate:
| In 0 | 01010101 |
| In 1 | 00110011 |
| In 2 | 00001111 |
| Out 0 | 01010101 |
| Out 1 | 00110011 |
| Out 2 | 00001111 |
Is equivalent to this gate:
| In 0 | 01010101 |
| In 1 | 00110011 |
| In 2 | 00001111 |
| Out 0 | 00110011 |
| Out 1 | 01010101 |
| Out 2 | 00001111 |
By omitting the input lines and by treating columns as octal numbers and rows as hexadecimal numbers, the second table above may be abbreviated to [02134657=33:55:0F]. The first set of digits gives the output fror each possible input, and the second set gives the truth table for each of the three outputs. I will use this representation from now on.
Omitting duplicates gives us around 8000 possible gates. Surprisingly, it turns out that almost all of these are universal in the sense that with the addition of the constants true and false, there some arrangment of these gates that can give us any of the 256 possible truth tables on some output.
There are 269 exceptions. One of them is [04261537=F0:CC:AA], which is simply one incarnation of the "straight through" gate.
7 of them provide access to 8 possible truth tables. These are:
- [45670123=AA:CC:0F] is not universal - 8 truth tables acessible
- [46025713=F0:AA:33] is not universal - 8 truth tables acessible
- [46570213=CC:AA:0F] is not universal - 8 truth tables acessible
- [67234501=AA:0F:33] is not universal - 8 truth tables acessible
- [67452301=AA:33:0F] is not universal - 8 truth tables acessible
- [64752031=CC:55:0F] is not universal - 8 truth tables acessible
- [76543210=55:33:0F] is not universal - 8 truth tables acessible
These ones are those that provide a "not" operator. The 8 truth tables are the 8 ways you can not or not-not each of the 3 inputs.
The remaining exceptions all provide acess to 16 truth tables. One example is [75462013=C3:99:0F]. As you can see, this table performs an XOR, that is: with the input values 55, 33, and 0F, C3=~(0F XOR 33), and 99=~(55 XOR 33)). The 16 truth tables it and presumably all the others provide access to are
- True
- False
- the 3 inputs
- not the 3 inputs
- the 3 ways you can xor two inputs
- not the 3 ways you can xor 2 inputs
- the xor of all 3 inputs
- not the xor of all 3 inputs
In summary: almost all 3 input/3 output reversible logic gates are universal in the sense that a network of them can produce any desired output from the 2^2^3 three input truth tables. The exceptions are those that only copy their input, those that only perform a "not" on one or more of their inputs, and those that only perform some combination of "exclusive or" and "not" operations.