Circuits and 2-adic numbers, a new vision of time-space exchange

Synchronous circuits allow you to work in both time and space. The simplest example is theSerialAdder in figure 3. Input numbers are presented as low-order first, i.e. a 0, then a 1, then 0s for the number 2. The Combinatorics FullAdder adds on each cycle, with the register propagating the carry from one cycle to the next. A pair of input bits produces a sum bit every cycle on the circuit's output lead. Addition takes place in time rather than space, as in the previous lecture.

Three other serial addition circuits are shown in Fig. 4. The one on the left interweaves time and space by processing 2 bits at each cycle: even-numbered bits are carried in space, odd-numbered bits in time. The middle adder is more subtle, as register doubling interleaves two independent additions in time: that of numbers composed of even-order bits at even cycles, and that of numbers composed of odd-order bits at odd cycles. We call it a stereo adder, in reference to the interleaved processing of the right and left channels of a stereo recording. Its principle can be applied to any sequential circuit. The one on the right uses a fundamental optimization technique based on space-time exchange, the pipeline. Combinatorics operations are cut by rows of registers, which increases clock speed at the cost of increased surface area and latency(the delay between the supply of inputs to the circuit and the supply of outputs by the circuit). This is analogous to the method introduced by Henry Ford for the automotive industry, with registers ensuring the movement of objects on the assembly line.

2-adic numbers as a model for sequential circuits

Unlike the Combinatorics adder, the serial adder has no problem handling infinite bit strings, as the carry propagates in the time direction. Numbers written in base p with an infinite number of decimal places but low initial weight are fundamental in mathematics, where they are called p-adic integers. Our infinite sequences of bits are therefore 2-adic numbers. 2-adics have the advantage of unifying logic and arithmetic, as they also encode the characteristic functions of sets of integers, taking as elements of a set the ranks of the 1's in the bit sequence of the 2-adic number. The point-to-point extensions of the Boolean operations ~ (negation), ∧ and ∨ calculate the complementation, intersection and union of sets.

Note the 2-adic numbers in bold and their infinite binary development with an initial index 2, the first bit being of rank 0. The number 0, which also denotes the empty set, is written ₂₀₀₀... As it is periodic, we also write it with the period in brackets: 0 = 2(0) = ∅. Then we have 1 = 210000... = 21(0) = {0}, 2 = 201000... = 201(0) = {1}, 3 = 211000... = 211(0)= {0,1}, etc. Addition is performed from left to right, propagating the carry to infinity, i.e. in the direction of writing. This is achieved by the SerialAdder circuit shown in figure 3. Multiplication is also achieved by extending classical multiplication to infinity. These two operations give 2-adic numbers a ring structure (we won't use the 2-adic body structure here).

Opposites are calculated by "infinite 2-completion":-1 = 211111... = 2(1) = {0,1,2,...}, since 1+(-1) = 0, then-2 = 201111... = 20(1) = {1,2,3,...}, etc. Periodic numbers correspond to rationals with odd denominators. For example, for x = _2101010... = 2(10) = {i | i even}, we can write x = _2100000...+ _2001010, so x = 1 + 4x since adding 00 to the head of a 2-adic is equivalent to multiplying it by 4, hence x =-1/3.

A fundamental 2-adic relationship is the arithmetical-logical relationship∀x. x + ~x= -1, which is obvious because x and ~x are added without a carry. If we pose y = ~(-1/3)= _2010101... = ₂(01) = {i | i odd}, it's easy to see that we have y = -2/3 since-1/3 + y=-1 according to the arithmetico-logical identity. I leave it to the reader to check that every rational number -p/q has a 2-adic expansion, which is not true for even-denominator rational numbers: 1/2 is not representable, as its first bit b would have to verify b+b = 1, which is impossible.

The remarkable work of Jean Vuillemin [2] establishes the relationship between 2-adics and circuits. The key points are summarized in Figure 5. Firstly, the FullAdder circuit finds in 2-adics a far more interesting definition than its purely Combinatorics definition in Fig. 1. If we denote a, b, c, s,r, the sequences of adder inputs and outputs over time seen as 2-adics, then FullAdder verifies the 2-adic invariant a + b + c = s + 2r, which advantageously replaces Boolean computation by numerical computation. The second point is that a register is a multiplier by 2 for 2-adics, since it outputs an initial 0 and then the delayed input bits. If we add a Boolean negation on each side of the register, represented by a circle, the resulting "ear register" calculates 1+2x for input x.

This formalization makes trivial proofs that would be difficult by following the bits one by one. For example, it's trivial for the circuit on the left in figure 6 to calculate z = x-y: the FullAdder invariant gives x + ~y + c = z + 2r, and the ear register invariant gives c = 1+2r. So x + ~y+ 1 = z simplified by 2r, and x-y= z since~y+ 1 = -yaccording to the arithmetic-logic identity. The proof is trivial, but it doesn't really say anything about what's going on at the bit level!

The lecture presented superb circuits for calculating 3x and x/3, generalizable to any odd p, the quasi-division 1/1-2x, and, as a highlight, the square quasi-root √(1-8x), whose 5-line proof is dizzying. I refer to the videos and slides for details.

The 2-adic integers also form a compact topological space with 2-adicnorm║x║= ^2-n if n = min{i| _xi = 1}. The associated distance is defined by d(x,y) = ║x-y║. In other words, two 2-adic integers x and y are at distance ^2-n if and only if the common initial segment of their development is of length n. J. Vuillemin proved the following fundamental theorem:

Theorem: a function f : 2z → 2z is computable by a synchronous circuit (possibly of infinite memory) if and only if it is contracting for the 2-adic distance: ∀x, y. d(f(x),f(y)) ≤ d(x,y).

Any function calculated by a synchronous circuit is trivially contracting, since the inequality expresses that outputs are equal on the first n bits if inputs are equal on the first n bits. The much more subtle reciprocal constructs a normal form known as the Sequential Decision Diagram (SDD), based on a representation in time and space of the function's truth table.

A constantly used but rarely proven result is that any output can always be looped back to any input if any path from an input to an output is intersected by a register. This is in fact just a consequence of Banach's theorem saying that any Lipschitzian function on a compact has a unique fixed point: to say that any path is cut is equivalent to saying d(f(x),f(y)) < d(x,y), equivalent to d(f(x),f(y)) < 0.6 d(x,y) by the definition of distance, CQFD.

The lecture introduced other fundamental properties of the 2-adic interpretation: the fact that we can implement continuous functions and not just synchronous ones by working with validity-value thread pairs, thus making time elastic as explained later; the fact that we can linearize Vuillemin's SDD normal form into a 2-adic number that represents the truth table in time and space of the function ; the result of seeing this number as defining a formal series, which is algebraic if and only if the function can be implemented by a finite-memory circuit; the extraordinary fact that, seen as a real number by prefixing it with "0," this number is either rational or transcendental, and so on. A lot of work remains to be done in this magnificent but, for my taste, little-known field.