1. Introduction

1.1 Binary Elements

A binary element will be defined as a physical entity which may exist in one of only two states. Consider two examples from modern physics, an electron at rest in a magnetic field, and the nucleon. In the first case the electron-magnetic field combination is characterized by two states due to the interaction between the electron magnetic moment and the field. The energy of interaction is

where C is a constant involving the Bohr magneton and the magnetic field strength. The two energy states are determined by the variable M, the spin component quantum number. The nucleon is a generic term for the neutron and proton. The latter may be considered two charge states of the nucleon with charges q = 0 and e respectively. The energy states are associated with the rest mass energies which satisfy m_nc²>m_pc². For both elements a transformation may be made to a generic variable x, sufficient to describe the states of the element. For both elements the two energy states may be generically described as E_L and E_U=E_L+DE for lower and upper states respectively. For the electron in a magnetic field, let

so that x is restricted to the values 0 and 1. The electron energy states can then be written

For the nucleon let x=q/e so the nucleon energy states depend on x as

The variable x is referred to as a logical variable, and may be used to describe the state of any binary element. It is common to refer to the state described by x=1 to be the active state. For the electron in a magnetic field the active state is the high energy state a situation referred to as active high. For the nucleon the reverse situation obtains, referred to as active low.

In practical terms the binary element is usually associated with an electrical potential at a particular point in a circuit. Nominally, only two values of potential can exist at the point, V_L and V_H with V_H=V_L+DV corresponding to the higher voltage. Active high or low situations correspond to the cases where the potential V(x) is related to the logical variable x via equations analogous to Eqn(1.3) and Eqn(1.4) respectively, obtained by substituting voltage for energy. Again, in practice it is not possible to employ exact electric potentials and the two quantities V_L and V_H correspond to upper and lower limits respectively. For the active high convention therefore, x=0 corresponds to V<V_L and x=1 corresponds to V>V_H.

1.2 Logical Functions

A logical variable is a distinct mathematical entity and functions of such variables must be defined. Only one non-trivial function of one variable exists, the complement or NOT function, designated by

which transforms from active high to active low. Thus when x is 0, NOT(x) is 1 and when x is 1, NOT(x) is 0.

There are three fundamental functions of two or more variables, AND, OR and XOR (exclusive OR). They may be defined via truth tables which list the function value for all possible combinations of inputs. This is summarized in table 1.1

Only two of the above functions are independent and it is easy to see that

Similarly,

It is common practice to treat the XOR function as a derived function with AND and OR as the basis. The terminology is straightforward: the AND function is 1 only for the condition x AND y both equal 1, while the OR function is one whenever x OR y is 1. While the use of brackets as in Eqn(1.7) makes the order of operations unambiguous, when brackets are not used the AND takes precedence in the same way as multiplication takes precedence over addition in arithmetic. Thus

The NOT, AND and OR functions may be combined to produce a large variety of logical expressions such as Eqn(1.6). Of especial importance are the complements of AND and OR, referred to as NAND and NOR respectively to denote NOT(AND) and NOT(OR). The truth table for these two functions is shown in the table below.

Also shown in the table are alternate forms of NAND and NOR, relationships referred to as de Morgan's theorem,

Extension of the basic functions to more than two variables is straightforward. Thus xyz = (xy)z is one only when all three variables are 1 and xvyvz = (xvy)vz is one when at least one of the three variables is in the one state.

1.3 Logical Gates

A logical gate is a device with output equal to a logical function of the inputs. The latter are logical signals representing logical variables. While the physical arrangements constituting the devices may vary widely, for example from relays to pneumatic valve systems to transistors, the functional behaviour is completely described by the appropriate truth table. The basic gate symbols are summarized in the figure.

As can be seen by comparison of the AND and NAND gates, or equivalently the OR and NOR gates, an open circle, or bubble, is conventionally used to designate complementation. Bubbles may also be placed at inputs. For example the following figure illustrates deMorgan's first theorem in terms of the gate symbols.

Combinations of the basic functions lead to logical expressions. Such logical expressions are realized by corresponding combinations of gates. For example, in experiments determining the characteristics of mu-mesic X-rays, a target containing the atoms of interest is situated in a beam generated by a high energy synchrotron. The beam consists of a mixture of particles. Cerenkov counters are used to detect the passage of a particle of a specific type. One Cerenkov detector is placed in front of the target, providing an output signal as logical variable µ₁ while a second detector placed behind the target is associated with logical variable µ₂. X-rays are detected from the target by a gamma-ray detector. In addition a calibration g-ray is also beamed onto the target and its detection is associated with a logical variable . Only those events are analysed either when a mu-meson is detected entering and stopping in the target or the event corresponds to a calibration. The logical expression to be realized is thus

The arrangement of gates realizing the above expression is called a combinational circuit.

1.4 Registers

A register consists of several binary elements grouped together so as to be considered a single unit. A register consisting of N binary elements is said to be of length N, or is referred to as an N-bit register. The unit bit refers to the information content of a single binary element. Since each element can consist in one of two states, there are 2^N states associated with an N-bit register.

The diagram illustrates the situation for 3-bit registers based upon the two physical binary elements discussed in section 1.1, the electron spin and the nucleon. There are eight distinct states for both systems. Note that if the physical states are represented by triplets of logical variables as shown in the central column, they become indistinguishable. This is an important point. Registers based upon vastly different physical binary elements have identical state structures.

The triplet of logical variables associated with a given state constitutes an entity in its own right referred to as a 3-bit word.

In defining this entity an important philosophical step is taken. While it is possible to associate a register state with each word, it is also possible to consider the word as a representative of information transcending the register. It is from this point of view that a register becomes an information storage device. A register in a given state is said to contain the word associated with that state. A procedure designed to ascertain the state of the register is said to read the contents of the register. Manipulation of the device to force it into a particular state is thought of as writing the associated word into the register.

In general an N-bit word X is an N-tuple of logical variables and may be designated X={x_i,i=1,N}. Of course the N-tuple is a 1xN array of logical variables and is often referred to as a vector. The terminology of word rather than vector will be used here since it provides a succinct distinction with real vectors and also because in physics the term vector implies certain transformation properties not normally associated with a word.

The set of 2^N words associated with a register of length N constitutes the register set R_N. The bit corresponding to i=1, x₁ is referred to as the most significant bit (MSB) while x_N is the least significant bit (LSB). The reader is warned not to read too much into this identification but to simply take the definition at face value as a method of identifying the left-most and right-most bits of the word.

Consider next the register set based upon a system of three nucleons illustrated in the right hand column of the figure. Assume the three nucleons are assembled into a nucleus. In this case the register length corresponds to the mass number. The state associated with 000 is the tri-neutron and is not a physically stable structure. The states 001, 010, and 100 all correspond to the mass 3 isotope of hydrogen atomic number 1, ³H. Similarly the states 011, 101, and 110 correspond to the mass 3 isotope of helium (Z=2),³He. Finally, the state 111 would correspond to the physically unstable triproton. Disregarding stability there are four nuclear configurations designated by the atomic number, Z=0,1,2,3. These groupings represent arrangements with a fixed number of protons, regardless of the order in which the neutrons and protons are arranged. An analogous attribute for the spin system is the total spin component which takes on the values -3/2,-1/2,1/2, and 3/2 for the state groupings above. In terms of the corresponding word the analogous attribute is the weight, which is numerically equal to the atomic number in the above example. The weight of a word is equal to the number of ones in a word. In terms of the vector analogy, the weight can be viewed as the square of the length of the vector. Formally the weight w(X) of an N-bit word X may be defined by the equivalent expressions

The set of all N-bit words of a given weight constitutes a subset of R_N. The latter may be decomposed into the union of N+1 such subsets corresponding to weights ranging from 0 to N. The number N_W of words in the subset consisting of weight W is given by

Only one word of weight 0, (all bits 0) and one word of weight N (all bits 1) occur. These will be designated F and U respectively.

The Hamming distance between two words is equivalent to the square of the geometrical distance between the points in N-dimensional space represented by the corresponding N-tuples. Thus the Hamming distance d(X,Y) between words X={x_i,i=1,N} and Y={y_i,i=1,N} is

Logical operations may be applied to words as a whole in which case it is implied that the resultant word is an N-tuple of logical variables each of which is the result of the operation on the corresponding bits of the operands. Letting OP be a generic representation of a logical function, if Z={z_i,i=1,N}, X={x_i,i=1,N} and Y={y_i,i=1,N} then

implies

A common example involves the process called masking. In this case one word, referred to as the mask, is constant, while the second is variable, ie may change with time as the result of various manipulations. The operation is AND. The word Z=XY will have a zero in each bit for which x_i=0. The corresponding bits of Y are then said to be masked off. The bits z_k for which x_k=1 will equal the corresponding bits y_k of the variable word Y. In a sense these bits are then selected or filtered by the mask.

1.5 Modulo Arithmetic

Modulo arithmetic generally arises in the treatment of cyclic processes. The classic example is the angular polar co-ordinate of a particle in a circular orbit. While formally the angle increases by b=2p after each circuit, the physical position is determined only by the excess, ie the position for 10^o, 370^o, 730^o etc is identical. The values are all related by

where b is the base and r is the residue. Any number p satisfying Eqn(1.20) is said to be related to r according to

An everyday example in which Eqn 1.21 is used is in the representation of time. The total number of hours p from any starting point is represented by r mod 12. For the case of base 2, obviously all even numbers are 0 mod 2 and all odd numbers are 1 mod 2. It also follows that if x and y are logical variables then

Eqn(1.22) may be extended to any number of variables.