From: John Conover <firstname.lastname@example.org>
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 : 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. , "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.