From: John Conover <john@email.johncon.com>
Subject: no subject (file transmission)
Date: Sat, 12 Jun 1993 23:49:46 -0700 (PDT)
Some Theory:
Consider an electronic system.
Let B = The number of registers in the system.
Let S = The number of states in the system.
Let I = The information in the system, (ie., Hartley Information.)
Then from Information Theory [1][2]:
B = ln (S) / ln (2) = I.
Or alternately (by solving for S):
S = e^(B * ln (2)) = e^(I * ln (2)).
Therefore, the number of states that the electronic system can
assume is exponential on the number of registers in the system.
(Call IEEE and tell them to hold the press on that one, huh?)
The questions is:
Does the engineering resources required to design the system
grow with the number of registers in the system, or the number
of states that the system can assume?
Some Discussion:
Obviously, a 4 bit counter is more difficult to design that a 4
bit data latch, because we have the 16 state transitions to
consider in the counter.
Consider 4 data latches. If the latches operate autonomously (as
in latching data on a buss,) adding a 5'th latch would take about
25% more design time, if the latches were designed individually,
(ie., the design resources would be linear on complexity.)
But, if the latches were not operated autonomously (as in a
counter, where the next state of the latches is determined by the
current state of the latches,) and we are required to analyze all
possible state transitions (in addition to designing the latches,)
then adding a 5'th latch would take twice the design time since we
have 32 state transitions to consider instead of 16 (ie., the
design resources would be exponential on complexity.)
The above Theory states something quite different. It says that,
at least in principle, design resources are linear on the number
of registers, and NOT on the number of states. What it says is
that, in general, a methodology exists (although it does not say
what the methodology is, obviously) that will require only linear
resources on the complexity of the design.
For example, consider a 4 bit data latch, whose Q outputs are
connected to the address lines of a rom, whose outputs are, in
turn, connected back to the D inputs of the latches. If the rom
outputs are always equal to the numeric value of the address lines
plus one, then the circuit will function as a counter (call IEEE
again.) The point is, that the the design resources required to do
this design will be linear on the design's complexity (assuming
that we have a machine that will generate the rom code in an
expedient manner,) and not exponential (ie., it is NOT obvious
that a 4 bit counter is more difficult to design than a 4 bit data
latch-BTW, I didn't say that it was a good design, just that the
resources to do the design are linear on the design's complexity.)
Isn't this the essence of Design Automation (ie., the
methodologies to handle complexity of design?)
1 Hartley, R. V. L. [1928], "Transmission of Information," The Bell
Systems Technical J., 7, pp. 535-563.
2 Klir, George J., Folger, Tina A., "Fuzzy Sets, Uncertainty, and
Information," Prentice Hall, Englewood Cliffs, New Jersey 07632, ISBN
0-13-345984-5 025, pp. 148-149.