1. Logic Synthesis (LS) [ aa = a ]
Especially of the Permutation -
invariant kind (PiLS), with symmetric Boolean Function components,
such as Threshold-logic cells (Theory and Application):
' Symmetric Logic Synthesis ' = Arithmetization of Logic
[ G.Boole: "The Laws of Thought" (1854):
x^2=x --> x.(x-1)=0 --> x=0,1 (binary), and: x.y=y.x ]
. . . . commutative arithmetic > idempotent logic.
***
Did you know that Boole developed his logic to check the
God-existence proofs of Spinoza and Clark ?
(turned out to be cyclic).
-- Some 84 years later C.Shannon (1938, M.Sc thesis MIT) noted the
isomorphism between Boole's algebra and switching circuits :
series(*) / parallel(+) : the begin of formal logic design.
[sci.math ref]
2. Digital Arithmetic (DA) [ ab = ba ]
Addition and multiplication. Array multipliers in IC's are much
too powerfull for their purpose
(for n x n bits: only a fraction 2^{2n}
of all 2^{n.n} bit patterns are applied to be added, to obtain the 2n-bit result).
So I dig into the algebraic structure of (+), (.) and (^) to find more efficient
algorithms and hardware for arithmetic.
For instance the 3* (3-star) property, as follows :
***
Did you know that each odd residue (mod 2^k) is a signed power of 3:
. . . Odd = +/- 3^i mod 2^k for unique i<2^{k-2} :
. . 3 is a semi-primitive root of unity mod 2^k.
3. Finite State Machines (FSM) [ ab.c = a.bc ]
The efficient binary coding of symbolic states
- their transitions define sequential logic behaviour.
Similar to the application of Boolean Algebra to combinational logic
design by Shannon,
this too can be analysed in an algebraic way.
Here a function (= machine input) is a mapping of a state-set Q into
itself (Q-transformation) then we have :
. . . The associative algebra of function composition = FSM-semigroups > arithmetic > logic.
***
Did you know that there are just five Basic State Machines (C U H L R) . . [2]:
. . . . . namely the 5 sequential closures (semigroup) of order 2 (and prime cycles Cp).
. . . . . Digital Networks (DN) and Linear Networks (R L C Trafo Gyrator)
. . . . . both have 5 basic components. . . . Coincidence?
Math = the Art of separating Necessity from Coincidence.
Life = . . make the Best of Necessity, using Coincidence.
" van de Nood een Deugd maken " ( = Engineering )
<^>---------------- My aim ---------------<^>
. . . . . FSM (seq-control) synthesis using :
Associative Digital Network Theory
<------> Coupled Network of the 5 basic FSM types
My book on --- " Associative Digital Network Theory
--- (Preface.htm)
an Associative Algebra Approach to Logic, Arithmetic and State Machines."
Subject: Quatorze Juillet (14 july): Vive la Representation Finite
Date: Fri, 14 Jul 2000 11:52:44 GMT
From: Nico Benschop
Org'n: Research
Newsgrp: sci.math
----------------------
Just for fun (205 years ago, hardly 10 generations;-)
"Leve eindige Representaties" --
There's more Structure, and more Fun, in the Finite.
"Wie het kleine niet eert, is het Grote niet weerd"
(who does not honor [take seriously] the Small,
does not deserve the Large) .. from FST to FLT (;-)
The Carry makes the Difference: breaking the Hensel Lift.
Dual precision: mod p^k _and_ mod p^{3k+1}
"Vive la Representation Finite" - On finite Computers & the Carry
(English translation almost verbatim;( owing much to French;-)
Re: Integer State Machines (ISM),
and their Sequential (Associative) Closure
(Specify and design sequential behaviour = CS / CE =
Specify & Generate and factorize Finite Semigroups)
Extend associative commutative idempotent (Boolean/Set) algebra,
to associative commutative (Digital/Binary) arithmetic,
to associative (Function composition) algebra (= Semigroups;-)
...finally, for APP (All Practical Purposes)... Happy Birthday!
--
Ciao, Nico Benschop -- http://home.iae.nl/users/benschop/ism.htm
(What -ism you mean? Integer State Machines; uncountable {a,b}* vs a* )
http://home.iae.nl/users/benschop/fewago.htm
(Powersums and Primesums: Fermat, Waring, Goldbach - revisited ;(
http://home.iae.nl/users/benschop/cantor.htm
(His Discrete Table with Diagonal: must have been square w x w ;-)
and E.T.Bell on Maths: http://home.iae.nl/users/benschop/quotes.htm
|
|
Ad.3 --- Sequential Logic synthesis : by Finite Semigroups
Re: Question for Mathematics PhDs . . . sci.math (22jan99)
Subject: Re: Question for Mathematics PhDs
Author: Nico Benschop
Organization: AmSpade Research
news:sci.math Fri, 22 Jan 1999 14:26:19 GMT
Stephen Montgomery-Smith wrote:
>
> Kevin Benko wrote:
>>
>> I have a question for those who have done PhD work in Mathematics:
>>
>> How did you come about to focus on your chosen branch of Mathematics?
>> Why/how your particular area of study [within Mathematics] rather
>> than some other [within Mathematics]? Was it intentional all along,
>> or was it something that you just "fell into"?
>>
>> When one is studying Mathematics, and is approaching the point to
>> start specializing, how does one choose?
>>
>> I'm tending towards classical analysis, but I want to be certain...
Certainty you will not find anywhere, nor should you expect it;-)
What is required is enthusiasm (and a wise experienced adviser..)
I heard, long ago, this anecdote (a bit black/white though):
Student comes to professor and asks for a PhD subject.
Answers professor: "Young man, after many years of study,
you _still_ don't know where to dig in?
I'm afraid I can't help you then..."
If I were at the graduate student age, choosing a subject would be
very easy (in discrete math, that is): finite semigroup structure,
especially finite transformation semigroups (= sequential closure
of finite state machines = the general model of deterministic seq_
behaviour = "computers").
So much has, since the sixties, been left aside, or rather ignored,
that I sometimes think: (discrete) mathematicians sit on a goldmine
(semigroups = associative algebra = function composition) without
realizing it. It may be difficult, though, to find a supervisor,
because it's an abandoned (yet full) mine - the bandwagons have gone on
in their great hurry... (Category theory, &c)... The finite seems to
have no appeal. (but: reflections occur *only* in the finite! ):
Note: we live, since some 50 years, in the "Digital Age", yet there
still is no general "Digital Network Theory" = sequential logic
synthesis = FSM structure theory, based on the Internal State Model
(comparable to "Linear Network Theory" as based on Fourier Spectrum &
Convolution, or: Boolean Algebra for combinational logic synthesis).
And finite semigroup structure (in general & full detail!-) is the clue.
But don't listen to me, make up your own mind;-)
Re: I am disappointed in God (Pertti Lounesto, Clifford Algebra's)
. . . sci.math (23aug2000)
[... on the limited use of symmetry groups, not modelling dissipation ...]
Well, Pertti, all you mention are symmetries and their closure (groups),
and a special case for R^8. Now don't get me wrong: this may be very
exciting stuff, and I guess related to the space we live in;-)
But do you really think this covers all?
You seem to suggest we reached 'The End' ... far from it, because:
... ever heard of 'dissipation' in this universe? Nothing goes without
friction & loss of original purpose. This is NOT modelled by any theory
of symmetries, which is a 'conservative' approach, viz. conserving
energy. While completely ignoring dissipative (like thermal) effects.
The entropy law in physics is indicative of that for continuous_
variable modelling, and semigroups (for instance of state_
transformations) in discrete dynamic modelling (FSM): hardly explored
yet (stuck at Boolean logic synthesis, & 'cripple' heuristic sequential
logic synthsis that include the 'internal-state' concept, cq 'memory'.
So why not generalize (symmetry-) groups, and go for semigroups ..
of function composition, allowing merging of states, hence going beyond
conservation models, being more 'real'. -- And probably a necessary step
to even think of the opposite: 'anti_entropy' = the creative process of
which we are the long-term result, starting with the creation of heavy
elements in supernovae (towards our Atmosphere & DNA building) -- note:
out of thermal chaos! ;-)
|
|
Ad.1 -- Boolean Functions: Symmetric Logic Synthesis
Re: Symmetric Boolean Functions . . . sci.math (20may99)
Subject: Re: Symmetric Boolean Functions
Author: Nico Benschop
Date: 20 May 99 10:43:22 -0400 (EDT) -- sci.math
[**-----------------------------------------------------------------
Hankel O'Fung
on Tue, 18 May 1999 14:44:03 -0700 asked:
Sorry for crossposting, but I wish to hear suggestions from
a wider audience basis.
Does anybody know what are the applications of symmetric
boolean functions and shift-invariant boolean functions of
n (>=3) boolean variables?
Here, a function f: {0,1}^n --> {0,1} or f: {0,1}^n --> (0,1)
is called symmetric if f(x1, ..., xn) = f(sigma(x1), ..., sigma(xn))
for any permutation sigma, and is called shift-invariant if
f(x1, x2, ..., xn) = f(x2, x3, ..., x1) = ... = f(xn, x1, x2, ...,
x_{n-1}).
I am particularly interested in any applications of these functions
with n>=3. Thanks in advance. -- Regards, Hanke.
-------------------------------------------------------------**]
Symmetric BF's (SF) are most interesting in logic synthesis of
combinational logic circuits. They have not had the attention one
would expect. For instance, they are essential in binary arithmetic
(computing), because an SF(x1..xn) = 1 independent of permuting the
n inputs -- which implies it "counts" the number of ones (high inps),
e.g: a Full Adder (#1's of 3 inputs are binary coded to 2 outputs)
has a sum (S) and carry (C) output, where S=1 iff (#1)=1 mod 2
(parity on 3 inps), and C=1 iff (#1)=2 or 3.
This means that any SF is characterized by the subset of input
"weights" w (# 1's) it 'recognizes' (activate the output to SF=1).
Now with n inputs, there are n+1 wieghts possible, from 0 to n,
so there are 2^{n+1} distinct SF's of n inputs.
Wellknown examples are:
AND_n (w=n: all inputs are 1),
OR_n (w>0: at least one 1),
XOR_n (w mod 2 = 1: parity function),
Carry_3 (w>1).
and in general the Threshold functions TF_n(k): w >= k,
with threshold k anywhere at 1 to n.
In fact, any BF can be decomposed into an (optimal;-) network
of SF's coupled by inverters (extreme case: NAND_2 cells).
And each SF is a sum-of-products of TF's in an obvious way.
(recall the weights: in intervals...)
Hope this helps. -- BTW: Shannon in his original paper AIEE'38
on Boolean Algebra as tool for Relay Circuit design,
had a special chapter on the importance of SF's (!)
Ciao, Nico Benschop -- http://home.iae.nl/users/benschop
Amspade Research - IAE - Institute of Advanced Engineering
|