The Associative Structure of State Machines

An Associative Algebra Approach to Logic,  Arithmetic and Automata

Nico F. Benschop

--- Amspade  Research --- The Netherlands

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. "

Book: "The Associative Structure of State machines. "

[Ch.8  Fermat, elementary proof FLT]  (p169-184),

[Ch.9  Goldbach]

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 : - 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 Netherlands.

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, Prague).

Free counter and web stats