Associative Digital Network Theory

To be published by Springer Verlag (due apr. 2009): announcement

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 charcterisation of the three main functions in computers, namely sequential logic (state-machines), arithmetic and combinational (Boolean) logic. -- Table of Contents of "Associative Digital Network Theory"

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 x² = x ) and 'iterative' ( commutative, xⁱ⁺¹ = xⁱ.x = x.xⁱ ) 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 p^k and the product of the first k primes : m_k = p₁ p₂ ... p_k 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 2^k is a unique signed power of 3. Thus 3 is a semi- primitive root of 1 mod 2^k, 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 Netherlands.

Acknowledgements:
The author is greatful to Philips Research (Eindhoven) for allowing
him to publish this material, developed during his 32 years there.
Also greatfully 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 UK) and R.Matousek,
prof. J.Kadlec (UTIA, Prague).