Benschop

Nico F. Benschop

Geldrop (Noord Brabant) - The Netherlands

Researcher at Philips Research Labs (Eindhoven) 1970 - 2002
Prof. (part-time) TU-Delft /EE: Digital VLSI Design 1981 - 1987
Retired nov-2002.

Subjects - Digital IC design methods :
. . . State-Machines, Arithmetic, Logic circuits
. . . Book The Associative Structure of State Machines , see Abstract:
http://en.wikipedia.org/wiki/Digital_Network_Theory

Education :
HBS-B . . highschool (Ede, Enschede) 1952 - 1957
HTS-EE . . . . . (Enschede - denHaag) 1957 - 1960
Mil.Serv. AirForce . (Breda - Ypenburg) 1960 -1962
TU-Delft . . . . . . . . . . . . . MSc/EE 1966
Univ-Waterloo, Canada . . PhD/EE 1970

Homepage : http://home.claranet.nl/users/benschop
Hobbies, see http://home.claranet.nl/users/benschop/play.htm
Favorite links http://home.claranet.nl/users/benschop/links.htm

Abstract

The Associative Structure of State Machines by Nico F. Benschop.

Subtitle: An Associative Algebra Approach to Logic, Arithmetic and Automata.

Book (Feb 2011: 11 chapters, bibliography, 217 pgs):
http://abc.nl/search/detailed.php?isbn=9789491030031&valuta=g
Engineering synthesis of State-Machines, Arithmetic and Logic.
Formal approach (Semigroup structure) - Background: Industrial Research.

http://home.claranet.nl/users/benschop/preface.htm

ACM Computer Review: - http://home.claranet.nl/users/benschop/ACMreview.txt by Prof. Harvey Cohn (CUNY)

Relevant subjects are Associative algebra , Algebraic structure and:

• Computer Science: Basic structure of algorithms, software, hardware, Automaton , finite state machine (FSM) : Sequential logic.
  
• Finite transformation semigroup: 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.
  

Purpose : 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..
[1]. Birkhoff-Bartee (1970) - Modern Applied Algebra
[2]. Clifford-Preston (1960) - Algebraic Theory of Semigroups (part I)
[3]. Hartmanis-Stearns (1970) - Algebraic structure of Sequential Machines

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 modelled 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<k, yielding an efficient dual base for log-arithmetic (US patent #5923888).
• 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, based on counting paths (minterms) in an orthogonal XY grid onto which a BFn is mapped. 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).
• Residue Arithmetic (mod m_k): The additive structure of multiplicative residue arithmetic semigroup S(*) [mod m_k] is analysed, for two characteristic moduli: m_k = p^k (prime power), and m_k = \prod{p_k} (the product of the first k primes). This yields insight into notoriously difficult representation theorems of Fermat, Waring and Goldbach (for integers, by controlled extension of residues with a carry, constructively breaking the Hensel lift ).

For the initial motivation of structured design, see appx-A.

-- The 11 chapters (PDF format):
Preface + Table of Contents + 2 Reviews --- http://home.claranet.nl/users/benschop/preface.pdf