The Associative Structure of State Machines
An Associative Algebra Approach to Logic, Arithmetic and
Automata
Nico F. Benschop
--- Amspade Research ---
The
Summary : This book is intended for researchers
at industrial laboratories, teachers and students at technical universities, in
electrical engineering, computer science and applied mathematics departments,
interested in new developments of modeling and designing digital networks ( DN
: combinational and sequential logic, arithmetic) in general, as a combined
math/engineering discipline. As background an undergraduate level of modern
applied algebra will suffice ( Birkhoff-Bartee1970: Modern
Applied Algebra, Hartmanis-Stearns1970: Algebraic Structure of
Sequential Machines ). Essential concepts and their engineering
interpretation are introduced in a practical fashion with examples. For the initial motivation of structured design. In
essence: the importance of the unifying algebra of function composition (viz. semigroup theory) for
the practical characterization of the three main functions in computers,
namely sequential logic (state-machines), arithmetic and combinational
(Boolean)logic. -- Table of Contents of "The Associative
Structure of State machines. "
[Ch.8 Fermat]
http://pc2.iam.fmph.uniba.sk/amuc/_vol74n2.html (p169-184),
[Ch.9 Goldbach] http://arxiv.org/abs/math.GM/0103091
Preface:
Known principles of discrete mathematics, especially finite semigroups,
residue arithmetic and Boolean logic (lattices) are interpreted in terms of
practical DN design issues. The main three levels of state machine synthesis
form a natural 'top down' hierarchy of associative algebras :
Application Algebra type Syntax Objects Operations ---------------- ------------ -------- -------- ----------- sequential logic associative (ab)c=a(bc) functions sequencing arithmetic commutative ab=ba numbers (+) (.) combinat'l logic idempotent aa=a sets or and
Historically non-commutative and
idempotent algebras diverged from arithmetic in the nineteenth century. Our aim
is to emphasize again their arithmetic nature, for practical engineering
purposes such as efficient synthesis of binary logic and state machines.
The 'static' ( combinational, idempotent x2=
x ) and 'iterative' ( commutative, xi+1 = xi.x
= x.xi) aspects can be modeled by
finite residue arithmetic. Apart from the two non-commutative components of
memory type (branch- and reset- machines, shown to be each others dual),
non-commutative aspects of sequential behavior can be represented by coupling
functions between components.
Part 1. In the first of three parts, on
state machines, an introductory chapter recalls basic principles in theory and
practice. The five basic components of sequential behavior (with
indecomposable semigroup) are derived, with ways to
couple them efficiently - only required in the non-commutative case. They
define the five basic types of state machines for network composition.
Part 2. In the second part, on
combinational (Boolean) logic, the concept of spectrum as a
characteristic sequence of numbers, is borrowed from Fourier analysis for
order-independent (symmetric) synthesis of Boolean functions (BF ). A useful arithmetic compositional rule holds:
the spectrum of a product of functions (of disjoint inputs) is the product of
the respective spectra. In fact Boole (1854) introduced his algebra - a
calculus of binary properties - as an idempotent form of arithmetic. This
allows convolution-like composition rules (as in linear filters), to be
developed.
Symmetric BF's
are implemented as a crossing-free and compact orthogonal grid network of MOS
transistors in the silicon plane, to obtain a regularly structured VLSI
implementation. Simply removing transistors from such grid yields planar
BF's with the desired crossing-free property,
covering a majority of Boolean functions. It is shown that, by properly
permuting the n inputs, each BFn of
at most four inputs is planar. A fast O(n^2) algorithm for symmetric
logic synthesis is applied to optimize fault-tolerant logic using Hamming- or
product- codes for error correction,
with synthesized gate count as cost criterium.
Part 3. The third and last part, on
arithmetic, analyses residue arithmetic with the two extremal
types of prime related moduli : prime power pk
and the product of the first k primes : mk
= p1 p2... pk
typical for 'sequential' resp. 'parallel' arithmetic. By expanding residues r
mod m with a 'carry' c as multiple of modulus m: n=cm+r, integer arithmetic obtains a dual focus on closure-
and generative properties of residues and carry, as independent resp.
dependent network components.
This balanced approach to arithmetic
provides new insights into old and well known problems in finite additive number
theory, with practical engineering results. For instance each odd residue mod 2k
is a unique signed power of 3. Thus 3 is a semi-primitive root of 1 mod 2k,
allowing efficient log-arithmetic over the two bases 2 and 3 (US patent
5923888). Moreover, a binary log-arithmetic microprocessor (32 bits, in 0.18 /u
CMOS technology) is described, designed as part of a European Esprit
project (Esprit 33544 HSLA,1999-2002, main contractor Univ. Newcastle, dpt.ECE -UK) comparing favorably with the known floating
point arithmetic.
The chapters are self-contained and
have their own local references (also included in the global bibliopraphy).
Much of the presented material is
new, and was published in recent years.
See related e-Preprints at : de.arXiv.org - my 8 papers on FSM (State Machines), Finite Semigroups, ...
... Arithmetic (Fermat, Waring, Goldbach,
Log-arithmetic) and Logic (Boolean).
. . . . Nico F..
Benschop ,
May 2010 . . . .
. . . . . . . Amspade
Research -- Geldrop-- The
Acknowledgements:
Greatly acknowledged are the contributions, to chapters 6 and 11, of
colleagues Richard Kleihorst, René van der Vleuten (Philips
Research Lab),
G.Muurling and prof. J.Simonis (TU Delft), and of Esprit project co-workers
Chris Softley, dr. NickColeman (Univ. Newcastle UK)
and R.Matousek,
prof. J.Kadlec (UTIA,
