The Algorithmic Complexity & Digital Circuits
In mid '80s Ileana Streinu held weekly seminars on the theory of
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
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.
- the amount of physical resources involved in building the actual circuit
- how to describe efficiently the circuit in order to be simulated, designed, verified, implemented or tested
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.
- Simple circuits: adders, memories.
- Complex circuits: instruction decoders, finite automata.
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
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).
[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,
[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