no subject (file transmission)

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.



Copyright © 1993 John Conover, john@email.johncon.com. All Rights Reserved.
Last modified: Fri Mar 26 18:52:43 PST 1999 $Id: 930811061313.707.html,v 1.0 2001/11/17 23:05:50 conover Exp $
Valid HTML 4.0!