Digital Network Theory Guide, Meaning , Facts, Information and Description
Associative Digital Network Theory is a book by .
Its subtitle is :
An Associative Algebra Approach to Logic, Arithmetic and State Machines.
New book (Oct.2004: 12 chapters, 3 appendices, bibliography, ca. 200 pgs):
Engineering synthesis of State-Machines, Arithmetic and Logic.
Formal approach (Semigroup structure) - Background: Industrial Research.
Access per chapter via authors homepage
Total ca. 1.1 MB of PDF files.
Relevant subjects are:
- Computer Science: Basic structure of algorithms, software, hardware, Automaton , finite state machine (FSM) : Sequential logic.
- Finite transformation semigroup: Associative Algebra, Algebraic structure , Function Composition, Residue Arithmetic, Boolean Algebra : Combinational logic.
- Electrical Engineering: Digital circuit design, Combinational and Sequential logic, Finite Log-arithmetic with single- and dual bases.
[1]. Birkhoff-Bartee 1970 - Modern Applied Algebra
[2]. Clifford-Preston (1960) - Algebraic Theory of Semigroups
Summary :
The basic ideas of algebra relating to the structure of sequential and combinational logic, although well known from discrete mathematics [1][2], will be recalled briefly and, for practical state machine design purposes, interpreted in terms of the original
additive and multiplicative arithmetic principles from which they developed in the nineteenth century (essentially the 1840's - Boole, Hamilton, Grassmann)
The subsequent three parts follow the developments in reverse historical order:
I . Sequential logic (state machines),
II. Combinational logic (Boolean algebra), and
III. Arithmetic.
The respective disciplines: CS/EE/NT (computer science/ electrical engineering digital circuit design/ number theory) are merged under one heading:
- - Finite Associative Algebra = Finite transformation Semigroups - - including:
-- Non-commutative function composition, for sequential logic
-- Commutative arithmetic (+, x) for residues and integers
-- Commutative and Idempotent for combinational logic (binary, Boolean)
Structured Design : The original motivation for this work appears in appendix A , which is a report on the state of the art of computing science in 1973 (ICS73 Davos) regarding a controversy about the existence of a software crisis, and the need for more attention to ’structure’ in programming and design. In matters of abstract mathematical material with practical applications, there is
the usual dilemma of how to present it:
— either top down : starting with an abstract concise definition of the essential concepts involved and developing the consequences, ending up with corollaries, as selected examples of important special cases;
— or bottom up : by appealing to practical (engineering) intuition and experience, to begin with special essential examples and applications, and gradually extracting their abstract essence to develop the general theory.
This dilemma is here resolved by alternating these two approaches, with a preference for starting bottom-up. By familiar examples in arithmetic, digital circuits or state machines, the essence of a formal viewpoint is introduced, as basis for computer aided design (CAD) synthesis algorithms in practice. Synthesis is taken to mean: efficient binary coding of a - functionally specified - symbolic description of desired sequential or combinational logic behaviour.
Intro : Essential concepts and their engineering interpretation are introduced in a practical fashion with examples, e.g:
- The known 5 non-isomorphic semigroups of order 2 as the elementary components of sequential behaviour (the 5 basic state machine types)
- Any finite semigroup S is the sequential closure of a state Machine, uniquely decomposable as a coupled network of the 5 basic machine types.
- Two of the five basic component types are non-commutative (branch- and reset- machines), the other three occur in residue arithmetic semigroups.
- Excluding these non-comm've components, non-commutativity of S can be modeled by coupling - with combinational logic functions - between components (which does not occur if S is commutative).
- Finite Group Decomposition (of any permutation machine) requires only right-congruence(s), thus proper subgroups suffice. Hence also a non-trivial simple group (like A5, without normal subgroup, resp. full congruence) can be decomposed as a coupled network of prime cycle machines, contrary to Krohn-Rhodes' decomposition which uses only 2 of the 5 basic machine types (reset- and permutation machines) and has the rather complex non-trivial simple groups (minimal order 60) as indecomposable components.
- Binary Residue Arithmetic : each k-bit odd residue is a unique signed power of 3. So each residue n == +/- 3^i.2^j mod 2^k for unique natural pair i<2^(k-2), j
- Fault Tolerant Logic by Error Correcting Codes : the known Hamming-code and Product-code methods for reliable transmissions can also be applied to (non-linear) Boolean combinational logic circuits. Practical examples show the trade-off between protection performance and cost.
- Planar Boolean Functions : a new representation of BFn (n-input Boolean functions) uses the concept of (rank-) spectrum as an ordered sequence of n+1 natural numbers that characterizes a circuit. An essential algebraic composition property holds : the Spectrum of a (disjoint) product of BF's is the product of their Spectra : Sp(F1 * F2) = Sp(F1) x Sp(F2) , where disjoint means: no common input(s).
-- The 12 chapters and 3 appendices are all in PDF format.
Preface + table of contents
External links
Author's WWW page : Amspade Research.
This is an Article on Digital Network Theory. Page Contains Information, Facts Details or Explanation Guide About Digital Network Theory