Linear representation of Boolean logic

We already know that it is possible to simulate these logical operations by analogy. Modern computers are still no more than analogy-machines. Digital values are little more than electronic `buckets' which `fill up' with voltage or current and overflow at certain thresholds: pour in one bucket, nothing happens, but pour in 1+1, it overflows and water runs down the drain. e.g.

$$C = \theta (A+B - 3/2)$$ (11)

where $\theta$ is the Heaviside step function, defined in the first lecture. In modern electronic computers, electrons have to run down `the drain' to Earth in order to simulate these switching operations. It requires actual transport of matter. The resistance in the environment means that this energy is dissipated as heat. Computers get very hot! Indeed, at 100 MHz speeds, they dissipate $W\times 10^8\times kT$ Joules per second, where $kT\sim 5eV$, and W is the number of bits per register (`word size').

But do we need to simulate Boolean logic so crudely, by a transport process? Suppose we could find a mapping onto a linear Markov model (logic by matrix multiplication), then this would not require any energy to be dumped at all. It would simply be a symmetry transformation (group theory), on a set of states, like all the fundamental physical systems. Moreover, if such a logic matrix were invertible (i.e. it had a non-zero determinant) then the system would then be reversible, and would therefore be representable directly by fundamental physical law.

The first thing we notice is that the operations are not all one to to mappings.

All invertible matrices generate bijective (invertible 1:1) mappings, so this tells us that we need to find a completely 1:1 formulation of Boolean logic, if we are to be able to find a group theoretical formulation which can be used to map computation onto physical law.

If we were only interested in representation theory, then we would represent the individual operations minimally. We could ask: what general invariant representations can be made which give 2:1 mappings? We have for instance, mappings from $A,B\rightarrow C$:

$$C = A^i\,{\cal O}_{ij} B^j$$ (12)

for any symmetric matrix ${\cal}_{ij}$. This does not result in a new vector, however, thus once we have evaluated the simple result, we can go no further, unless we reconstruct the entire problem artificially. What we need is an operation which takes two vectors and provides a new vector. We could write

$$C^k = A^i B^j {\cal O}^{ijk}.$$ (13)

But with only zeroes and ones as values, to work with, this object cannot have sufficient linearly independent rows and columns to make an invertible object.

Example: Choose a 2-dimensional vector representation:, given by:

$${\bf 1} = \left( \begin{array}{c} 1\\ 0 \end{array}\right) ~~~~~~~~ {\bf0} = \left( \begin{array}{c} 0\\ 1 \end{array}\right)$$ (14)

with

$$~{\rm\bf NOT}\,= \left( \begin{array}{cc} 0 & 1\\ 1 & 0\\ \end{array}\right)$$ (15)

It is easy to see that the $~{\rm\bf NOT}\,$ function has the desired properties. Using an inner-product matrix multiplication

$${\rm Result} = (a,b)\left(\begin{array}{cc} o_1 & o_2\\ o_3 & o_4\\ \end{array}\right) \left( \begin{array}{c} c\\ d \end{array}\right)$$ (16)

the two to one operations may be found as $2\times 2$ matrices:

$$~{\rm\bf AND}~= \left( \begin{array}{cc} 1 & 0\\ 0 & 0\\ \end{a... ...~ ~{\rm\bf XOR}~= \left( \begin{array}{cc} 0 & 1\\ 1 & 0\\ \end{array}\right)$$ (17)

We can show sensible properties such as $~{\rm\bf OR}~= ~{\rm\bf AND}~+~{\rm\bf XOR}~$ and so on, but this is not useful for further calculation because half of the operations result in scalar numbers, i.e. they do not return objects of the same type the originals. They are not 1:1. Information is lost, and no further useful computation can be made. Note also that the operations are not invertible.

Can a Boolean mapping ever be made to work without loss of information, i.e. invertibly? Consider the $~{\rm\bf AND}~$gate. Does any mapping

$${\bf0} {\bf0} \rightarrow {\bf0}$$ (18)

$${\bf0} {\bf 1} \rightarrow {\bf0}$$ (19)

$${\bf 1} {\bf0} \rightarrow {\bf0}$$ (20)

$${\bf 1} {\bf 1} \rightarrow {\bf 1}$$ (21)

exist without loss of information? The information flow in these 2:1 gates: is

$$-\sum_i p_i \log_2 p_i$$ H_LHS =

$$- 4\times \frac{1}{4}\log_2 \frac{1}{4} = 2~ {\rm bits}$$ =

$$- \frac{3}{4}\log_2 \frac{3}{4} - \frac{1}{4}\log_2\frac{1}{4}$$ H_RHS =

$$\sim 1 {\rm bit}.$$ = (22)

Clearly there is intrinsic information loss.

Rather than guessing representations, we use information theoretical ideas to look for a new strategy which might give a 1:1 representation. Any n:m mapping where $n\not= m$ is going to give us problems. The solution is to view this as a coding problem, a protocol, in which we symmetrize n:m by combining n:m with m:n, giving a new m+n : m+n mapping.

Example: combine the Boolean 2:1 with a redundant 1:2 mapping:

$$\left( \begin{array}{c} 2\\ 1 \end{array}\right) \rightarrow \left( \begin{array}{c} 1\\ 2 \end{array}\right)$$ (23)

The result is a 3:3 mapping, where we can ignore part of the result. If a coding can be found which allows this process to be repeated over multiple operations, it will allow complex logical operations to be evaluated.

Looking at the logic operations we wish to represent and counting degrees of freedom, we see that both A and B have four possibilities, and thus there are 8 bits of input, meaning we need at least an eight row vector, and $8\times 8$ matrices which perform the transformations. Alternatively, we can see that the mapping of 2 inputs to 1 output, must be replaced by a mapping from 3 inputs to 3 outputs, meaning that 2³=8 bits are needed to code all binary possibilities.

We take an $8\times 8$ representation, and allow it to act on vectors which are will represent the values of the inputs:

$$\begin{array}{ccc} A & B & C\\ \hline 0 & 0 & 0\\ 0 & 0 & 1\\ ... ...\ 0 & 1 & 1\\ 1 & 0 & 0\\ 1 & 0 & 1\\ 1 & 1 & 0\\ 1 & 1 & 1\\ \end{array}$$ (24)

These form three column vectors, or simply one $8\times 3$ matrix. This is a minimal (irreducible) representation, in the sense that it is the smallest representation which satisfies all the conditions. Note that, the eight combinations of inputs cannot be represented in any other way, in an eight-dimensional representation. We could change the order of the input or output combinations, but not the combinations of ones and zeroes, since these simply count from 0-7 in binary.

The transformation we are looking for must preserve information, if it is to be reversible, so that also means that exactly the same combinations of ones and zeroes must also be produced by the output, otherwise there would have to be some repetition and therefore loss of information (linearly dependent rows implies non-invertibility).

This implies that the only operations which a matrix operator can perform on a vector composed on only 1's and 0's, without loss of data, are row permutations or column permutations.

Note that the Boolean algebra is represented here as a sub-algebra of a larger one, with a fundamental representation in GL(R,8) (the general linear group of all real, $8\times 8$matrices). Once again, this is simply a matter of representation.