Loop Based Taxonomy for Digital Systems
The complexity of digital systems domain asks for a specific and more
nuanced taxonomy than the simple taxonomy used for digital circuits
(combinational vs. sequential circuits).
I proposed a loop based taxonomy for digital systems in a
communication held at the Romanian Academy
in 1980 (published as [Stefan '83a]).
The main starting ideas are:
- the composition rule (see the definition of the partial recursive functions) is used to increase
the size of a digital system
- the loops which increase the autonomy are used to add new
features in a digital system.
Because the number of the loops including each other determine the
degree of autonomy in a digital system, it can be used to classify
digital systems. The resulting taxonomy is:
- 0OS: zero order systems - no-loop, combinational circuits
(ex.: multiplexors, decoders, adders, ALUs, ...)
- 1OS: first order systems - one-loop, memory circuits (ex.:
latches, master-slave flip-flops, RAMs, registers, ...)
- 2OS: second order systems - two-loop, automata systems (ex.: JK
flip-flop, finite automata, counters, LIFOs, FIFOs, ...)
- 3OS: third order systems - three-loop, processing systems (ex.:
stack automata, JK-based automata, processors, ...)
- 4OS: fourth order systems - four-loop, computing systems
(ex.: advanced processors, computers, ...)
- ...
- nOS: n-th order systems - the number of loops is in the same
magnitude order as the size of the system (ex.: register
implemented LIFO, cellular automata, ..., various self-organizing systems, ...)
References
[Stefan '83a] Gh. Stefan: "Structurari neechilibrate in sisteme
de prelucrare a informatiei" (Unbalanced Structures in Information
Processing Systems), in Inteligenta artificiala si robotica
(Artificial Intelligence and Robotics), Ed. Academiei RSR, Bucuresti,
1983. p. 129 - 140.
[Stefan '83b] 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