The Algorithmic Complexity & Digital Circuits

In mid '80s Ileana Streinu held weekly seminars on the theory of computation complexity in the Functional Electronics Laboratory of Politehnica University of Bucharest. Algorithmic Information Theory (AIT) was one of the most interesting topics for me. The algorithmic complexity theory developed in AIT by Gregory Chaitin triggered the subjects listed below. For G. Chaitin the information contained in a binary string is related with the shortest program used to generate it.

I was inspired to develop few interesting topics connecting the concept of algorithmic complexity with hot problems in digital circuit design. Some of them are shortly introduced below.

1. Size vs. Complexity in Digital Circuits

Usual textbooks use, refering to digital circuits, the terms size and complexity with the same meaning: the number of components used to build a digital circuit. But, when the number of components increases we are faced with two distinct problems: Indeed, for a big number of components there are two actual extreme configurations: (a) a very regular repetitive patern built by few components, or (b) a patternless configuration of circuits. The first is very simple to be described even if it contains millions of components. But, the second will have a very big and "ugly" description, because each component must be mentioned with its description and connections.

Chaitin's algorithmic complexity of a binary string gawe me the hint to use the minimum description length as the quantitative evaluation of the circuit complexity, while for the amount of physical resources to use the term circuit size.

Definition 1. The size of a digital circuit, is given by the number of CMOS pairs (the equivalence in 2-input inverting gates can be also accepted) used to build it.

Definition 2. The complexity of a digital circuit is proportional with the size of its shortest description.

Definition 3. A simple circuit has the magnitude order of size bigger than the magnitude order of its complexity.

Definition 4. A complex circuit has the magnitude order of its size in the same order as the magnitude order of its complexity.

Examples:

2. Apparent Complexity

Sometimes simple things are hidden "inside" complex ones. The mixture of complex and simple things, when the simple things are not emphasized, is a complex thing because its description ignores the simplicity it contains.

The complexity of an object containing simple but hidden, un-emphasized sub-objects is only apparently big. If the simple parts are segregated from the complex ones, then the overall description is shorter and the evaluated complexity is the real one. Else, a bigger apparent complexity is considered.

The scientific knowlege process is a process of continuously reducing the apparent complexity. It is a (continuous) convergent process toward the real complexity of the investigated object.

Reducing the apparent complexity means to disclose hidden structures. But sometimes this is not a simple task. For example: the apparent complexity of a fractal can be very big if its simple generative rule is unknown, but once the rule is disclosed its complexity is given by the size of the rule's description.

3. Loops & Complexity

Autonomous, loop controlled circuits in digital design allow simpler control.

Example: usually, designing a finite automaton with "smart registers" of JK-FFs leads to a smaller sized complex combinational loop. (The overall size of the resulting circuit increases sometimes, but the complexity is for sure reduced.) For details see the chapter Processors, Third order, 3-loop digital circuits in [Stefan 'in never ending progress] subsection Automata with JK “registers”

Another example: is easier to control an adder having a loop through the carry FF. For details see the cahpter Processors, Third order, 3-loop digital circuits in [Stefan 'in never ending progress] subsection Loops closed through memories

In Giga Gates per Chip Era the main problem is to keep the complexity under contol, while reducing the size is a secondary problem.

4. Functional Segregation

Loops closed in digital systems support the functional segreggation between structures associated with simple functions and structures involved in supporting complex functions.

Example: the two AND gates used to transform an RS-FF into an JK-FF represent the simple parts from the random loop of the D-FF finite automaton when it is reimplemented using JK-FF registers.

Another example: in a programmed digital structure the third loop allows to segregate the complex microprogram from the simple associated circuit. (Similar: the fourth loop allows the segregation between complex programs and simple processors.)

Main consequence: the overall complexity of a digital system is reduced.

Related to the non technical environment a computer is considered an open loop system. But, a big improvement is expected if the computation will consider also the natural loop closed through the human mind as a basic mechanism supporting computation. Computer + human mind represents a stronger computation tool because the formal aspects and the imaginative aspects of computation are perfect segregated.

5. The Circuit Complexity of a Binary String

Definition 1. An Universal Circuit (UC) is a combinational circuit which computes an n-input Boolean function if it is programmed by an m-bit binary string, where m = 2n.

The actual UC is an n-bit selection input multiplexor. The program is an m-bit string applied on the selected input, while the input variable is an n-bit string applied on the selection input.

The simplest string generator is an UC receiving as input variable (on its selection input) the output of an n-bit counter and being programmed (on its selected input) by the string to be generated. If the counter starts to count from 0, then the output will generate the desired string: bit by bit the program starting from the least significant bit.

For the specific program prog UC can be minimized to the size Suc(prog).

Definition 2. The circuit complexity of the m-bit binary string string(m) is Suc(string(m)) + S counter(n).

Because the smallest n-bit counter has the size in O(n), the smallest circuit complexity of an m-bit binary string is in O(log m).

References

[Stefan '83] Gh. Stefan: "Structurari neechilibrate in sisteme de prelucrare a informatiei" (Unballanced Structures in Information Processing Systems), in Inteligenta artificiala si robotica (Artificial Intelligence and Robotics), Ed. Academiei RSR, Bucuresti, 1983. p. 129 - 140.
[Stefan '83] Gh. Stefan, I. Draghici, T. Muresan, E. Barbu: Circuite integrate digitale (Digitale Integrated Circuits), Ed. Didactica si pedagogica, Bucuresti, 1983.
[Stefan '91] Gh. Stefan,: Functie si structura in sistemele digitale (Function and Structure in Digital Systems), Ed. Academiei Romane, Bucuresti, 1991.
[Stefan '93] Gh. Stefan: Circuite integrate digitale (Digital Integrated Circuits), Ed. Denix, Bucuresti, 1993.
[Stefan '97] Gh. Stefan: Circuit Complexity, Recursion, Grammars and Information. Multiple Morphisms, Ed. Transilvania University of Brasov, 1997.
[Stefan '00] Gh. Stefan: Circuite si sisteme digitale, Ed. tehnica, 2000.
[Stefan work in endless progress] Gh. Stefan: Loops & Complexity in Digital Systems. Lecture Notes on Digital Design in the Giga-Gate/Chip Era