Associative Theory of Digital Circuits, Arithmetic and 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 modelling 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-Bartee
1970: Modern Applied Algebra, Hartmanis-Stearns
1970: 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, see appx-A; in essence: the importance of the unifying algebra
of function composition (viz. semigoup theory) for
the practical characterisation of the three main functions in computers, namely
sequential logic (state-machines), arithmetic and combinational (Boolean)
logic. -- Table of Contents of
"Associative Theory of Digital Circuits . . . "
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 modelled 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 behaviour 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
behaviour (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 BF_n
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 favourably 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 : sciencedirect.com - my 12 papers on FSM (State Machines), Finite
Semigroups, ...
... Arithmetic (Fermat, Waring, Goldbach,
Log-arithmetic) and Logic (Boolean)
... [Elsevier publishers: free register & login, and search for 'benschop']
. . . . Nico
F. Benschop , May 2008 . . . .
. . . . . . . Amspade Research -- Geldrop
-- The
Acknowledgements:
Greatly ackowledged
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. Nick
Coleman (Univ. Newcastle
prof. J.Kadlec (UTIA,
