JPH01276221A - Electronic controller connectable to external system - Google Patents

Abstract

PURPOSE: To realize a career operation by placing a circuit network in a substraight and adding plural numbers of electric connection in the substraight which connects logic circuit networks for providing one-to-one correspondence between a state and the circuit network. CONSTITUTION: In the layout of a figure, a tree is divided into plural parts (that is, the logic circuit network) in accordance with the number of vertexes, the respective parts are a linear array shape so as to be executed an layout in terms of recurrent along the individual part of the sub-straight and a removed end edge is horizontally placed upwards in order to connect the plural parts in accordance with the hierarchy of different levels and states. Thus, the whole logic circuit networks are executed the layout in the linear array shape consisting of a single line, that is, a base line. But the front surface area of a chip sub-straight to be get is used so that its linear array can be divided into plural linear parts, for example, two or more separated parallel lines or returning lines.

Description

DETAILED DESCRIPTION OF THE INVENTION Field of the Invention This invention relates to electronic control devices, and more particularly to a new class of electronic control devices based on the use of state diagrams as abstract models.

BACKGROUND OF THE INVENTION State diagrams are a recently proposed visual formalism for explaining the behavior of complex systems. They are based on D. Burrell's ``State Diagrams: A Visual Approach to Complex Systems'', The Science of Computer Programming (also published by Wytmann Institute of Science, C384-05, December 1984).
! (revised February 984). They extend standard state diagrams in several critical ways, allowing modular, hierarchical descriptions of system behavior in a top-down, bottom-up, or mixed manner.

State diagrams have been suggested as a useful formalism to describe the behavior of reactive hardware components, allowing powerful hierarchical representations and flexible concurrency and synchronization accounts.

State diagrams are a classic form of state diagrams that have been widely used in digital control units as abstract models, as widely described in C. Mead and L. Conway's Introduction to VLSI Systems, Co., Ltd. (1980). Seems like a natural extension to media known in the art (also known as finite state machines - FSM).

Two known variants of finite state models are Moore and Meeley machines, with typical implementations using PLAs (Programmable Logic Arrays) for the implementation of combinatorial logic. PLA allows for a simple and conventional implementation of control binary, but at the cost of being very space consuming as the number of states increases. This causes them to consume more power resulting in larger delays forcing designers to reduce clock frequencies.

The large PLA problem has motivated the development of several techniques for PLA optimization. Two examples of such optimizations are: (1) PLA Folding in C;-D. Haktil, "Techniques for Programmable Logic Array Folding," 19th Design and Automation Conference, June 1982, No. 147; -155 pages and (2) J.D. Ullman's "
vLSI Computation Aspects, PLA Division, Computer Science Press, 1984. Both techniques are NP-complete, considering them quite universally, so they require a heuristic to work in practice. An attempt to reduce PLA dimensions using hierarchies is presented in R. Ayer's "Hierarchical Use of Silicon Compilation and PLAs," 16th Design Automation Conference, 1.
Found in June 979, pages 314-326, it utilizes a fairly low level of descriptive language. Although hierarchies are promoted as a technique for reducing system design complexity in the C-Mead and Lψ Conway publications cited above, they are used only in a limited manner in conventional computers. .

Another major issue with FSM models is D. Durusinski and D. Burrell, “Using State Diagrams to Explain Hardware,” Weimann Institute of Science, C385-06.
, June 1985, is its limited ability to handle simultaneity, a feature that has been widely discussed.

[Summary of the invention]

The invention is based on the idea of using state diagrams as an alternative abstract model for designing electronic control devices.

In accordance with the present invention, an electronic control device is provided which is connectable to an external system and includes a plurality of logic circuitry, each circuitry capable of assuming a plurality of different states, and wherein any transition between two states is Placed by different network hierarchies by different state hierarchies with a one-to-one mapping between states and networks so as to affect two associated networks and their respective lower-order networks. and each of the logic networks includes a storage element for storing its state, a means for determining its next state, and an immediately above level logic network for determining their respective states. and means for receiving control signals from or outputting control signals from immediately below-level logic circuitry, at least some of which logic circuitry receives control signals from or outputs control signals from an external system. a means for outputting a control signal, the logic circuitry being disposed on the substrate, and a plurality of electrical connections on the substrate providing a one-to-one correspondence between the states and the circuitry; Connect the logic network as shown.

Further features of this invention are described in more detail below, along with the many advantages provided by this invention.

The invention will now be described with reference to the accompanying drawings.

[DESCRIPTION OF THE INVENTION] Design Methodology As briefly explained above, the basic idea is that instead of a single machine realizing a finite state machine (FSM), as in the traditional approach, It is the use of a machine network, or a logic network that implements a state diagram. Simply put, this means that each layer has a different layer of circuitry.
and a hierarchy of different states, by arranging logic circuitry that can take on a plurality of different states, and provides a one-to-one correspondence between states and circuitry.

Continue to explain the design methodology used. This description assumes the degree bounds of the state diagram tree. In other words, "parent"
This is the limit on the number of children a state can have.

The first step is to assemble the basic machine.

All states at all levels of the hierarchy are placed in the F immediately below the level so that there is a one-to-one correspondence between states and networks.
Represented by a machine that executes SM. in this way,
Any transition between two states affects the two associated circuitry and their respective lower order circuitry.

Figures 1a and 1b each schematically illustrate a Moore machine. For each to remember its state,
Memory element 2. 2', means 4.4' for determining their next state, and means 6.6' for receiving control signals from other logic networks and outputting control signals in order to determine their respective states. 8, 8'.

FIG. 2 illustrates a state diagram illustration of a controller consisting of a plurality of such FSMs. Figures 3a to 3d are
3 illustrates an individual FSM for the control device of FIG. 2; FIG. In Figures 3a-3d, the output along the transition is produced by the transition itself. In Figures 2 and 3a-3d, the outgoing signal is the negation of the incoming signal.

In other words, for the state diagram in Figure 2, the four F's in Figure 3
Four machines will be assembled to realize SM. The mechanical connection is illustrated in FIG. The event "entering
is produced when it reaches . Therefore, the best state encoding appears to be a one-bit code, with each state having its only representation bit, so that little logic is required for decoding and encoding. The "out" signal is actually the negation of the "in" signal, informing lower level machines to move to their dormant state. "Out" signals running between machines are produced by lower level states to notify their predecessors of their termination. For example, A2 notifies A in FIGS. 2 and 3. Simultaneity is achieved in a natural manner, as illustrated in Figures 5a and 5b.

This "horizontal" coding scheme seems to be exponentially more expensive compared to the usual "vertical" coding scheme, but since this coding is per machine (each of limited dimensions)
, its cost is limited. On the other hand, the area of PLA is
It is mainly determined by the number of minterm lines, of the order of B2 (n is the number of states), one minterm for each transition of the FSM. Thus, even without considering input/output lines, the expected PLA area would be O(B21 og (n)). On the other hand, according to the methodology of the present invention, the number of minterms is determined by the maximum submachine area and intramachine connections. The input alphabet is ignored in this connection. This is because they are many times smaller in constant size compared to the number of states.

The advantages of this hierarchical implementation methodology are reduced space and power consumption, state diagram concurrency and synchronization accounting capabilities, and a natural implementation mechanism for history operators (using local state storage to hold return addresses). Contains an average increased clock frequency based on the reduced clock period required for small PLAs. These advantages are discussed in more detail below. .

Timing Issues Several timing issues may arise in the examples of FIGS. 2-4. A natural choice is to implement each individual FSM using a Moore machine.

That is, for example, for event 3 of A2 (the third
(a), propagates up to the machine in E (Fig. 3d) and causes a delay in the transition to state , which is at odds with the intuition that such transitions should be instantaneous in a synchronous system. It will take several cycles. A lower level machine moves its state after its parent moves it.
(For example, in Figure 2, when C enters the state A
B enters B1 after moving from A to B), or when lower level states are terminated by transitions from their parents (e.g., AI, A2°A3 is terminated by transition 2 from A to B), or when lower level states are terminated by transitions from their parents (e.g. ), a similar time delay would occur. These timing issues become extremely important in examples such as Figures 6a and 6b.

There, the time it takes for D to get the message to finish may be so large that it may cause a situation where D is active after E becomes active.

Various solutions can be found to these problems. Two of them are described below.

The first is a machine that combines a Mie machine with a Moore machine.
The purpose is to implement a basic FSM, which is illustrated in FIG. The machine is in reality a Moore machine with asynchronous "out" and "in" (input and output) signals that can propagate up or down the hierarchy using asynchronous logic rippling. Probably. No spikes (worthless output signal caused by some unsynchronized input signal transitions) will occur. This solution solves the above timing problem at the overall cost of reducing clock frequency, so that such an asynchronous signal can propagate up or down the entire hierarchy in one cycle. Dew. That is, the clock period should be O(n log(n)) for the two conventional layouts described below in connection with FIGS. 8-12.

A much larger asymptotic delay (0(n2))) is found in conventional PLAs due to their long wires.

The second solution is rather straightforward and involves connecting each ``out'' or ``in'' wire to all associated successors, incurring a larger layout area and reducing delay.

Layout The manner of laying out a simple tree state diagram will first be described. Using the above methodology, E.L. Lyserson's "Area-Efficient VLSI Computation" MIT Press 1983
A tree with an O(n) area layout (where n is the number of vertices (nodes) in the tree) is created using the layout algorithm of 2008. However, this layout is not very regular in the PLA's output lines, which are not considered in its general structure and algorithm (although it is possible to slice through the layout and route those wires around). Another important factor related to this layout is the model used, where the basic machinery and wiring are of the same width, causing considerable waste.

A preferred layout may be obtained using Lyserson's shapeable layout. Its layout is area 0(n
d log2 (n), where d is the maximum degree found in the tree, as illustrated in FIGS. 8-11. All vertices (
machines or processors) are arranged in a row on the bottom line,
Those connections run vertically. 0 (log2 (
n)) Horizontal wires are parallel to the bottom line (each such temporary wire can be a pair of "outgoing" and "incoming" wires).

The top 0 (log (n)) wire runs across the layout. The next O(log(n)) wiring is cut off in the middle, etc. The actual connections are made at selected intersection points, for example by "solder points". This method divides any finite tree with n vertices and limited degree d into two sets [n/2][n/2] by cutting O(log(n)) edges. It can be bisected into vertices. - Once the cut set is determined, the vertices of the two sets can be recursively laid out and the edges of the cut set laid out.

A regular O(n log(n)) layout can also be achieved using the tree-1-section theorem, as described in Lyserson (supra). This is illustrated in FIG. Using this theorem, the tree is bisected into two sets by removing 0(1) edges, each with 1/4 n
It consists of 3/4 n vertices. Each set is then laid out portrait-wise along the bottom line, with the removed edges placed horizontally on top.

For both of the above layout techniques, the path between two nodes will be of dimension 0(n), and more specifically for any layout technique it will be (n/log(n)). The final result is that any layout (Cn/l
og (n) ) cannot have an edge shorter than
This means that a constant C exists. For both techniques, the constant of o(...) is determined by the maximum degree d allowed in the state diagram. It determines both the maximum dimensions of the basic machine and the maximum cut set in both the recursive procedure.

The clock periods for the last two layout techniques are determined by the previously mentioned 0(n) distance between two nodes and the 0(l
og (n)) level, so 0 (nlog(n))
It is.

Some of the favorable properties of such a strategy are as follows.

(1) Input and output wiring to the control unit does not need to be routed inside the layout.

Because machines are all around us.

(2) Individual PLAs can be laid out within a block in a completely normal manner similar to the way it is done in normal PLAs, with specific answers for ground, voltage and clock wiring. do not require.

(3) Each individual machine is small and fast, with connections consisting only of wiring. That is, the area is ill in machine units.
not defined, but rather measured in conventional units.

A programmable approach-response system is a system that is repeatedly stimulated by the outside world and whose role is to constantly respond to external inputs. It is distinguished from a transformation system, which generally receives inputs, performs transformations on them, and produces outputs. Figures 13 and 14 illustrate two types of these systems. Real-time controllers are good examples of digital reaction systems; some of them are graphic display controllers,
These are a disk control device and a signal control device described below.

There is a need for a reaction system description language that will effectively, easily and quickly realize a desired system from its description. When used as such a language and combined with programmable components such as those described below,
State diagrams allow desired realization.

FIG. 15 illustrates the mechanical geometry of the chip after it has been programmed to form a hierarchical mechanical tree. Hierarchical machine trees behave differently than traditional ones. Here, each machine realizes a superstate of the state diagram, and the machines connected below realize its children. Of course, any transition from a superstate will cause the appropriate machine and its successor to stop. The difference between this programmable and the previously presented methodology is that each superstate (which would be realized as an FSM) would be programmed into memory rather than being hardwired. be. As in the original machine tree, each machine can be a conventional phono-Neumann machine, with local memory and data connections between machines (and state diagram hierarchy timing), as shown in Figure 15. (even with local timers for the notation). However, there will also be a control connection between the machine and its successor. This connection consists of enter, exit and exit signals (and pause and active signals for runtime realization) that are part of the methodology described earlier.

A different possibility would be to make the machines of the machine tree only finite state machines that produce signals to the normal processing and data units, so that only the control lines would appear in Figure 15.

In the above methodology, the machines were hardwired together, but here the machines shown are programmable. Programmers may wish to define different tree structures. Therefore, the most convenient layout of the chip is 0(n d log2 (n)
) layout, the schematic shape of which is shown in FIG.

This technique allows the fabricator to create a universal chip in which the specific mechanical structure can be easily determined by adding appropriate contact cuts. Dynamic (runtime) machine-structure programming, which would allow the realization of several state diagrams in one machine, can be achieved using switches instead of permanent contact cuts.

Simultaneity in the shape of orthogonal states is achieved by programming the chip so that two or 2.3 machines are mapped together as one substate.

That is, the layout technique allows flexible machine definitions, including hierarchical relationships, concurrency, and even shared state, by connecting machines to their 2.3 predecessors.

As mentioned above, the chip can operate in both a synchronous and self-timed manner. However, since a particular machine tree can be an unbalanced tree of height close to n, the best implementation for the largest chips is a self-time realization, or at least one where the clock frequency is determined by the structure of the particular tree. It will probably be realized at the same time.

Programming the chip consists of three main stages. The first step is to 'define the precise contact cut (or switch state for dynamic ones).
It is to program the mechanical structure. The second stage is
The conversion program part is executed in the same way as a conventional processor. The third and final step is to generate a mechanical open signal. The last two stages are performed in the following manner.

Each superstate is programmed into a machine as a flat finite state diagram. That is, all of its transition and conversion commands will be performed as in a conventional phono-Neumann machine. Additionally, the processor machine language will have special instructions for producing machine variable control signals such as those mentioned above.

These signals run between the machines in the layout programmed in the first stage. All these programming details can be automatically extracted from the state diagram description by the compiler.

It is shown in FIG. 15 that there are at most d 3-tuple control connections for each machine (5-tuples for self-time realization). Each 3-tuple is an in/out/out control signal, and there are d such tuples, one for each sub-state of the machine.

Although this "horizontal" coding scheme was chosen for its simplicity, a "vertical" coding scheme could be implemented instead. Additionally, there may be more than eight possible states for each machine. Of these, d will have substates. However, the "horizontal" coding mechanism described above allows for non-deterministic behavior in the following manner. If 2 from active state
If two events occur simultaneously that cause two different transitions, two next state machines can be activated due to the "horizontal" encoding mechanism.

Finally, the chip has incoming and outgoing control signals, thus allowing its use in large units.

DESCRIPTION OF THE PREFERRED EMBODIMENT FIGS. 17-23 illustrate a preferred embodiment of the invention in the form of a signal control device. FIG. 17 illustrates the input/output interface for the signal controller. FIG. 18 illustrates a machine tree for the signal controller.

Figures 19a and 19b show two F of the signal control device.
FIG. FIG. 20 illustrates a complete state diagram of the signal controller. 21-23 illustrate three implementations of a signal control device based on the abstract model of the state diagram of FIG. 20 in accordance with the present invention.

Each machine in this embodiment consists of a memory (containing a local finite state program) and a control (which fetches the next instruction from local memory). In FIG. 18, each communication line represents the control signals mentioned above and two "control buses." These buses have substates with several possible inputs,
Used if the bus holds the appropriate input number or sends a signal with substate 2.3 to its parent.

SIGNAL CONTROL DEVICE OPERATION The signal control device illustrated in FIGS. 17 and 18 includes two sets of lights. One is located on the main road entering the intersection (MA I N), the other on the secondary road (MAIN)
SEC). During the day (D/N-1), the control device operates according to one of two possible programs. Program A (PROG-1) alternately gives 2 minutes to the MAIN vehicle and 1/2 minute to the SEC vehicle, and Program B (PROG-0) gives the 5EC-FULL signal - once high. Give the SEC car 30 seconds. Night (D/
N-0), the controller grants priority to the MAIN car until one of two possibilities occurs.

(1) If MAIN turns blue and a pedestrian wants to cross MAIN (PD-MAIN full 1) or a new car appears at SEC (NEW-CAR-8EC-1)
), 2 minutes have passed, or (2) 3 cars have already appeared at the SEC. Once one of these conditions occurs, the SEC vehicle is given 30 seconds.

The control device can also be operated manually (A/M-0). In this mode, whenever POLICE goes to 1 (a police officer presses a button), the transition is from MAIN to SEC.
or vice versa. This manual operation and
All transitions from day to night and vice versa are marked with 5 yellow lights.
Must be accompanied by a flash of light for seconds, then MA
IN receives blue illumination.

The hidden camera can only be operated by the control device when it is in AUTOMAT IC mode.

When a car enters an intersection from MA I N while MA I N is red (ENTER-M-1), MA to the intersection
The camera will take a picture of the IN entrance by issuing the FMAIN signal. The same process is also performed for the entrances of S and EC (using the ENTER-3 signal and issuing the FSEC signal).

The control device allows the ambulance to
-1) or from the SEC (DMAIN-0), an ambulance signal (AMB-1) can be received informing the controller that it is approaching an intersection. Then it should synchronize the lighting according to the direction of the ambulance and ignore all other events. - Once the ambulance enters the intersection, the controller should be notified (AMBJ-1) and return to the original operating mode, ie DAY or NIGHT.

The controller can receive an error message (ERRIN-1) and must then flash both yellow lights. Another possibility of error is that the control device may
Occurs when operated manually for more than 5 minutes, then ERR
An OUT signal should be issued. The RESET signal resets the controller to the AUTOMATIC state.

The foregoing operation of the signal controller illustrated in FIGS. 17 and 18 is more specifically explained in the FSMs of FIGS. 19a-19o.

Regarding the FSM illustrated in these figures, (ER
Some input conditions (such as RIN) are accompanied by an upward arrow (↑). This indicates that the FSM moves its state by appropriate events. For example, in FIG. 19d illustrating the FSM of the signal controller TLC, instead of ERRIN inputting the TLC, the event rERRINJ should be input. For the FSM illustrated in FIG. 19f for the controller, exiting normal operation 1 is caused by a manual pause and exiting normal operation 2 is caused by the D/N or A/M signal. 19g illustrating the FSM in normal operation
Regarding the figure, a "history operation" is implemented using two dummy states that cause an "out" signal to the appropriate child, from which a "start" signal will cause a return by the "history operation".

In Figure 19h, each input to M and M2 causes a control event that resets the timer.

State Diagram Explanation of Control Device (FIG. 20) The signal control device is illustrated in the state diagram of FIG. The state diagram shows an exclusive (“or”) state (e.g. D
AY and NIGHT) and orthogonal (“AND”) states (eg, AUTOMATIC and CAMERA). Also, failure to enter (e.g. WA in MANUAL
entry into IT) and admission by background (event AMB
Also included is a return from AMBULANCE on J to only one level backwards by history, i.e. to AUTOMATIC or MANUAL, then by default). Furthermore, it also includes the temporal boundaries of the duration of being in a state (e.g., exactly 5 seconds for 6 LIGHTS states and no more than 1 second for 2 MANUAL states).
5 minutes).

The state diagram of Figure 20 also includes conditional connectors (e.g., D
/N), and up and down arrows that make condition changes an event (for example, D/N~ is an event that occurs when D/N changes from 0 to 1). ) is illustrated.

Action is a Mealy automatic.
) can appear along transitions as in (e.g.,
Occurs when making a transition between two states of MANUAL, triggered by a POLICE event). They can also appear in a state, as in a Moore machine, in which case a convention causes them to be executed when entering the state (eg, red and blue illumination are made clear when entering ERROR).

Signal controllers, including the ability to provide hierarchical explanations, where events affecting one state automatically result in all substates, and the ability to account for simultaneous activity at any hierarchical level, during any time interval. The advantage of explaining the phase diagram of
This will be clear from Figure 20. These and further advantages are fully explained by the publications associated with the state diagrams mentioned at the beginning of this specification.

State Diagram Realization of a Control Device (Figures 33-35) Figures 21-23 are based on the use of state diagrams as abstract models, in accordance with design methodologies, and more particularly in accordance with the layout techniques described above. 3 illustrates three implementations of a signal control device.

FIG. 21 specifically illustrates the matrix technique described in connection with FIG. In this technique, all logic circuitry is placed in a linear array extending along a first axis (horizontal axis) on the substrate. The electrical connections to the logic network include a first group of spaced electrical conductors connected to the logic network and extending parallel to each other along a vertical axis and a first group of spaced electrical conductors extending parallel to each other along a horizontal axis. , including a second group of spaced apart electrical conductors intersecting the first group of conductors.

As shown in FIG. 21, the horizontal conductors include a first plurality of conductors P, furthest from the linear array of the logic network and extending unobstructed the length of the linear array, and a first plurality of conductors P, which are closer to the linear array. , a second plurality of conductors P2 extending across the length of the linear array but intersecting at the one-half point; and a fourth plurality of conductors P, which also extend for the length of the linear array of the network, but which interrupt at the one-eighth point. Electrical connections, such as solder points, are provided at the intersections of selected ones of the first and second groups of conductors according to a hierarchy of different network levels and states, as illustrated in the tree of FIG. It will be done.

As mentioned above with respect to FIG. 11, this method
Any finite tree with J vertices and limited degree rdJ is bisected into two sets of n/2 and n/2 vertices by cutting the 0(log(n)) edges. Once the disconnected set is determined,
It is based on the fact that the two sets of vertices can be laid out recursively and combined with the edges of the cut sets placed on the horizontal line of the layout.

It will therefore be shown that the electrical connections to the processor of FIG. 21 follow the same hierarchical arrangement as in the machine tree illustrated in FIG.

That is, the processor MA I N performs signal control (TLC
) processor, while the TLC processor in turn connects the ERROR processor and the LIGHTS and C0NT
Connected to R0L processor L+C. That is, M.A.
Any event that affects the IN processor will automatically affect processors TLC, ERROR, and L+C.

Similarly, any event that affects processor TLC will simultaneously affect processors ERROR and L+C.

The LIGHTS processor directly controls various lights and a 5 second timer. Processor C0NTR0L directly controls processor No. (NORMAL 0PERATION), and the latter processor controls processor MANUA
L, directly controls AUTOMATIC and CAMERA. Processor AUTOMATI C is processor N
Controls IGHT and DAY. Processor NIGET controls a two minute timer.

The operation of the signal control device illustrated in FIG.
This is explained more specifically in the FSM of Figures 19o and the state diagram of Figure 20.

FIG. 22 illustrates another implementation of a signal controller using the state diagram of FIG. 20 as an abstract model. Second
The layout of Figure 2 utilizes the tree break theorem described in Lyserson, as discussed above with respect to Figure 12.

Using this theorem, the tree is divided into two parts, each divided by 1/4 by removing the 0(1) edges.
Consists of n to 3/4 n vertices (ie, the number of logic networks). Then each part is in the shape of a linear array,
Recursively laid out along separate parts of the substrate, removed edges are used to connect the two parts according to a hierarchy of different levels and states, as illustrated in the tree of FIG. placed horizontally on top.

That is, the signal control device shown in FIG.
The same hierarchical levels of control are provided as described above with respect to the diagrams and as illustrated in the state diagram of FIG.

FIG. 23 illustrates a further layout of the signal control device according to the tree of FIG. 18. In the layout of Figure 23, the tree is divided into parts (i.e., logic networks) according to the number of vertices, each part in the form of a linear array, recursive along a separate part of the substrate. The edges laid out and removed are placed horizontally on top to connect multiple parts according to different levels and status hierarchies.

In the arrangement illustrated in FIGS. 21 to 23,
Although the logic network is laid out entirely in the form of a linear array of single lines, or bottom lines, to take advantage of the surface area of the available chip substrate,
It will be appreciated that the linear array may be divided into multiple linear sections, eg, two or more separate parallel lines, or folded lines.

Summary of Advantages The above technique of using state diagrams as abstract models for constructing stored state devices provides a number of important advantages. The layout area is On21 for PLA
ag(n)) can be reduced to 0(n log(n)) or even 0(n), and the overall performance is reduced to (balance ) 0 (n l
og (n)) clock cycles. The technology also includes other features. One is that the design is based on several locally programmable ROM counters instead of one central PC, eliminating the traditional "Vono-Neumann" failure (the direction of which is currently being investigated) and having individual state memory. This is the possibility of using as a history to realize the history operation. The methodology also deals with concurrency, synchronization and real-time issues in a normal and natural manner. Furthermore, the technique may be implemented in the form of a node-wired system or in a programmable chip in which both the reaction and conversion portions of the reaction system can be programmed.

Although this invention has been described with respect to one particular application, namely a signal control system, it is understood that this application has been described for purposes of illustration only and that the invention may be used advantageously in many other applications. will be done.

[Brief explanation of the drawing]

Figures 1a and 1b illustrate two realizations of a finite state machine (FSM) model. FIG. 2 illustrates an example of a state diagram. Figures 3a-3d illustrate the individual FSMs of the example state diagram of Figure 2, where the outputs along the transitions are produced by the transitions themselves. FIG. 4 illustrates the mechanical geometry of the example of FIGS. 2 and 3a-3d. FIGS. 5a and 5b illustrate an illustration and realization, respectively, of the orthogonal state of the mechanical geometry of FIG. 4. FIGS. Figures 6a and 6b illustrate example state diagrams and processor connections for timing problems, respectively. FIG. 7 illustrates a programmable logic array (PLA) implementation of the Mealy/Moore machine. FIG. 8 illustrates another example state diagram. FIGS. 9a-9e illustrate finite state machines (FSMs) for the example state diagram of FIG. 101st! SO is shown in Figures 8 and 9a to 9e.
Figure 3 illustrates the example processor attachment scheme of the figure. 11 and 12 show two of the processors in FIG. 10.
Figure 2 illustrates two alternative layouts. 13 to 15 illustrate the mechanical geometry of the reactive system, the conversion system, and the programmed chip, respectively; these figures illustrate the described programmable approach to the state diagram implementation of the controller. It will help you understand. FIG. 16 illustrates a generic tree layout to a programmable approach. FIG. 17 illustrates the input/output (I 10) interface of one particular implementation in the form of a signal controller. 18 illustrates the machine tree of the signal control device of FIG. 17. FIGS. 19a to 19o each illustrate the FSM of the signal control device of FIG. 18. FIG. Figures 21-23 each illustrate a state diagram of the signal controller of Figure 18 based on using the state diagram of Figure 20 as an abstract model; Connecting the three examples, Patent Applicant Yeta Research and Development ψ Company Figure 1a Moore Yagura Fuhachi Figure 1b Me V Isofu J Figure 3b B/) FSM Figure 3d E/IFsM Fourth Figure 5b Figure 6a Figure 7 Figure 98 A+FSM Figure 9b Az FS
MFigure 9C FSM of C Figure 9d F of B
SM Fig. 9e FSM of D Fig. 13 Fig. 14 Fig. 15 '1'' Button Fig. 19c MAIN trouble FSM Fig. 19d TLCnFSM Fig. 19c FSX for ERROR 7 Mo-Country M2◆ M3Σ Out 19h Ward Island-FSM 5 Main Shogun: Listening to the nine points, the bar is missing... 7 points n7 ↑〉' Bow IS3 2nd. Fig. 19i FSM for M2◆M3 Fig. 19 For A"C FSM

Claims (1)

[Scope of Claims] (1) Contains a plurality of logic circuit networks, each capable of assuming a plurality of different states, and any transition between two states causes the connection between the two associated circuit networks and their respective arranged according to a hierarchy of different states, with a one-to-one correspondence between states and circuits, so as to affect the underlying circuitry, each of said logic networks having a one-to-one correspondence between states and circuits; storage elements for storing and means for determining their next state and control from logic circuitry at the level immediately above and logic circuitry at the level immediately below to determine their respective states; means for receiving signals from or outputting control signals thereto, at least some of said circuitry for receiving control signals from or outputting control signals thereto; means, the circuitry being disposed on a substrate, a plurality of electrical connections on the substrate connecting the logic circuitry to provide the one-to-one correspondence between states and the circuitry; Further including: an electronic control unit connectable to external systems; 2. The electronic control device of claim 1, wherein the logic circuitry is disposed on a substrate in the form of at least one linear array of circuitry. (3) all of the logic networks are aligned and extend along a first axis on the substrate, and the electrical connections are connected to the logic networks and are perpendicular to the first axis. the second of
a first group of spaced apart electrical conductors extending parallel to each other along an axis of the first plurality of electrical conductors; a second group of electrical conductors located at the intersection of selected ones of said first and second groups of conductors to provide said one-to-one correspondence between states and circuit networks; Claim 1 comprising a connection
The electronic control device described. (4) a first group in which the linear array extends along one orthogonal axis on the substrate, and the electrical connections are connected to the logic circuitry and extend parallel to each other along a second orthogonal axis; a second group of spaced electrical conductors extending parallel to each other along the first axis relative to the length of the linear array; a first plurality of electrical conductors further from the linear array of logic circuitry and extending unobstructed over the length of the linear array; and a first plurality of electrical conductors closer to the linear array than the first plurality. , a second plurality of electrical conductors extending for the length of the linear array but interrupting at a one-eighth point; and a second plurality of electrical conductors closer to the linear array than the second plurality for the length of the linear array; a third plurality of electrical conductors extending but interrupting at one-eighth points; 2. The control device according to claim 1, wherein the control device is located at an intersection of objects. (5) said logic network is divided into two parts, each containing 1/4 to 3/4 of the total number of logic networks, and each of the two parts is a separate part of the substrate in the form of a linear array; 2. The control device of claim 1, wherein the electrical connections connect two parts of a logic network according to the one-to-one correspondence between states and networks, laid out recursively along the sections. (6) said logic network is divided into a plurality of parts corresponding to the number of immediate substates of the hierarchy, each part recursively along a distinct part of the substrate in the form of a linear array; 2. The control device of claim 1, wherein the electrical connections connect multiple portions of logic circuitry according to the one-to-one correspondence between states and circuitry. 7. The control device of claim 1, wherein each of the different network levels is implemented with hard-wired circuitry. 8. The controller of claim 1, wherein each of said different network levels is programmed into memory. (9) The control device is a signal control device that controls a first set of lights positioned on a main road and a second set of lights positioned on a secondary road intersecting the main road. The control device according to item 1.