NL9000380A - SEQUENTIAL FINITE STATE MACHINE SWITCHING AND INTEGRATED SWITCHING WITH SHIFTING. - Google Patents

Description

Sequential finite state machine circuit, as well as integrated circuit provided with the circuit.

The invention relates to a sequential finite state machine circuit, comprising a set of N bistable elements (FF (1), ..., FF (N)> and an associated set of combinatorial logic, the combination of logic values of the bistable elements defines a state of the circuit, which represents a state of a finite state machine, at which times, determined by a clock signal, under the influence of the combinational logic, of the current state of the circuit and of an input signal, the circuit changes in a next state, wherein the set of combinatorial logic realizes transitions between states of the finite state machine in the circuit.

Such a circuit is known from German Offenlegungsschrift DE-3719181-A1.

The invention further relates to an integrated circuit provided with such a circuit.

A finite state machine (FSM) is a widely used model for displaying logical systems. Unlike continuous or analog machines, the FSM works with discrete information. FSMs can be divided into combinatorial (without memory; the input signals unambiguously determine the output signals) and sequential (with memory; the actual content thereof and the input signals unambiguously determine the new content of the memory and the output signals).

An FSM can be implemented in an FSM circuit: combinational logic with flip-flops fed back to the logic, with input or control signals and a clock signal (synchronous FSM), where the logic transitions between states of the FSM (represented by the content of the flip-flops) in the circuit.

An FSM can have a state that is absorbent, that is to say: from all possible states this so-called quiescent state is reached, provided that the input or control signal has assumed a certain series of values. This makes the FSM self-initiating: supplying the determined sequence of values of the input signal ensures that the FSM is then in the absorbing state.

When a model of such an FSM is simulated using a logic digital simulator, this self-initiating behavior of the circuit cannot be found: the simulator assumes an unknown state at the start of the simulation, and is event driven (i.e. calculates from state to state), so that only the current state is known to the simulator. Due to this lack of history for the simulator, initializations via a sequence of input values cannot be simulated.

This problem could be solved by forcing the FSM into a known state at the start of a simulation. However, this is not a reflection of reality, which should be as close as possible to the simulation. Moreover, this intervention in the circuit presents practical problems, due to the difficult accessibility of internal points of the circuit.

Among other things, it is an object of the invention to provide a sequential finite state machine circuit, with self-initiating behavior that is simulable. To this end, a sequential finite state circuit according to the invention is characterized in that by a given sequence of X values of the input signal, (c (0), c (1), ..., c (X-1)>, starting with c (0), a quiescent state is reached from each state, in which every partial sequence (c (0), c (1), ..., c (J-1)} of length J of the given sequence of X values of the input signal, where 1 <= J <= X, or a sub sequence of length J derived therefrom, is stored in the circuit.

This allows the simulator to make the transition from an unknown state to the known absorbent state step by step.

According to an embodiment, a sequential finite state machine circuit according to the invention is characterized in that the N bistable elements are presettable and that the circuit is provided with (X-1) further bistable elements, coupled as a shift register, for storing the (X -1) most recent values of the input signal or values derived therefrom, and further includes decoding logic, fed by the input signal and the (X-1) bistable elements of the shift register, which are a detection signal for the occurrence of the given sequence of X values of the input signal and applies this as a bias signal to the N bias bistable elements.

A detection signal for the occurrence of the given sequence is provided by the decoding logic, which evaluates the shift register and the input signal.

According to a further embodiment, a sequential finite state machine circuit, wherein X> = N, according to the invention is characterized in that the circuit is provided with (XN) further bistable elements FF (N + 1), ..., FF (X) , and of additional combinatorial logic which, when a partial sequence ic (0), c (1), ..., c (J-1)> occurs, of length J from the given sequence of X values of the input signal, where 1 <= J <= X, each time the first J bistable elements FF (1), ..., FF (J) assume a sequence of J values derived from this partial sequence, whereby the assignment of representations to states of the finite state machine is such that the states are represented by combinations of logical values of the bistable elements that correspond to the derived sequences of J values in the first J values.

For this type of FSM circuit, where the length of the given sequence of the input signal is greater than the number of bistable elements (such as, for example, set / reset flip-flops), the advantage now arises that a minimum of additional bistable elements is required and that the bistable elements used do not have to be presettable. When the entire sequence occurs, the circuit is automatically initialized by storing the occurrence of partial sub-sequences.

According to a preferred embodiment, a sequential finite state machine circuit, wherein X> = N, according to the invention is characterized in that the circuit is provided with (XN) further bistable elements, for storing the (XN) most recent values of the input signal or derived values thereof, the circuit further comprising additional logic which, when a partial sequence (c (0), c (1), ..., c (J-1)} occurs, of length J from the given sequence of X values of the input signal, where XN <J <= X, each time the first J-X + N bistable elements FF (1), ...,

FF (J-X + N) any sequence of J-X + N derived from this partial sequence

values, where the assignment of representations to states of the finite state machine is such that the states are represented by combinations of logical values of the bistable elements corresponding to the derived sequences of the first J-X + N values J-X + N values.

This FSM also has the additional advantage that no unused states can occur in the flip-flops of the circuit.

According to a further embodiment, a sequential finite state machine circuit, wherein X <N, according to the invention is characterized in that the circuit is provided with additional logic which occurs when a partial sequence {c (0), c (1), .. ., c (J-1)} of length J from the given sequence of X values of the input signal, where 1 <= J <= X, each time the first J bistable elements FF (1), ..., FF (J ) assumes a sequence of J values derived from this partial sequence, wherein the assignment of representations to states of the finite state machine is such that the states are represented by combinations of logical values of the bistable elements that correspond with respect to the first J values with the derived sequences of J values, wherein the additional logic upon the occurrence of the entire sequence of X values of the input signal makes the bistable elements FF (X + 1), ..., FF (N) values corresponding to the logical values of the resting state.

For this type of circuit, where the length of the given sequence of the input signal is less than the number of flip-flops, this has the advantage that initialization is performed without additional flip-flops.

All this will be explained and clarified in the figure description.

Figure 1 shows the state transition diagram of a finite state machine; Figure 2 shows an associated circuit; Figure 3 shows an FSM circuit according to a first embodiment of the invention; Figure 4 shows an FSM circuit according to a preferred embodiment of the invention; Figure 5 shows a table with an assignment of representations to states of the finite state machine; Figure 6 shows an FSM circuit with a possible implementation of the additional logic; Figure 7 shows a digital integrated circuit provided with a circuit according to the invention.

The invention will be explained in more detail with reference to the sequential finite state machine, the state transition diagram of which is shown in figure 1. The FSM has 16 states, and several transitions between them which are controlled by a clock signal and an input signal. The input signal in this case is bivalent ("O" or "1"). In general, an input signal can also consist of several bits. At times determined by the clock signal, for example at each rising edge, the finite state machine switches to the next state. The state with number 1 is absorbing with a sequence of 5 consecutive input signals with the value "1": from each state the rest state 1 is reached after at most 5 ones of the input signal. The given sequence of X values of the input signal <c (0), c (1), ..., c (X-1)} therefore looks as follows: Γ1 "," 1 "," 1 "," 1 "," 1 "}; X = 5 and N = 4. Of course these values are chosen as an example, other choices are quite possible. This sequential finite state machine can be implemented in a circuit using 4 bistable elements or flip-flops (2 to the power of 4 is 16 possible states), and a set of combinatorial logic that realizes the correct transitions between the states.

The exact composition of the required combination of combinatorial logic can be generated and optimized automatically, for example with the software package LOCAM from PRAXIS Systems PLC, 20 Manversstreet Bath BA1 IPX, United Kingdom.

The FSM circuit is shown in Figure 2: 4 flip-flops, numbered FF (1) through FF (4), are connected and fed back with a set of combinational logic CL, which is also fed with an input signal CS, with clock signal CK controls the rate of state transitions.

The circuit can be simulated using a logic digital simulator, for example with the QUICKSIM from Mentor Graphics B.V., Marsstraat 9, 2132 HR Hoofddorp, The Netherlands, as described in the User's Manual, ref. No. 14773, May 1988.

The simulator is fed with information about the circuit: flip-flops, connections and logic, states and possible transitions. On this basis, the simulator mimics the behavior of the circuit. At the start of a simulation (power up), the FSM can be in any state; the content of the flip-flops is unknown to the simulator. The simulator cannot "remember" previous control signals: it has too little data to get out of the unknown state. Thus, the state of the FSM remains unknown after a subsequent clock signal. Thus, the self-initiating behavior cannot be simulated. The reason for this limited simulation capability is that a simulator has three logical states: low ("0"), high ("1"), unknown ("X"). The number of unknown values “X” can be reduced, for example when a “0” and an “X” are applied to an AND gate: the result is definitely a “0.” Also when a “1” and an “X” are applied to an OR gate: the result is definitely a "1". However, an "1" and an "X" applied to an AND gate yields an "X" again.

Of course, the FSM can be set to a certain known state at the start of a simulation, by forcing signals at internal points of the circuit. However, physical access to these internal points is often very difficult. In addition, the user must then know that the FSM must be initialized and how to do it.

The problem that the simulator does not accurately reflect the actual behavior of the FSM can therefore be better solved by adjusting the hardware: the (temporary) storage of occurring partial sequences (c (0), ..., c (J— 1)> with 1 <= J <= X, or partial sequences derived from it (for example, the logical complement), the simulator provides additional information that enables it to realize the transition from an unknown to a known state step by step. the various options for this will be explained in the FSM defined above.

An embodiment of an FSM circuit according to the invention is illustrated in figure 3. 4 additional flip-flops SRF (1), ..., SRF (4) have been added to the circuit of figure 2, coupled to a shift register, in which the 4 previous values of the input signal CS can be stored. The outputs of the additional flip-flops SRF (1), ..., SRF (4) and the actual input signal of input CS are applied to a decoding sub-circuit (here consisting of a NAND gate), which forms a detection signal SET for the occurrence of the given sequence of input signals (here: logic "0" if and only if all 5 inputs are logic "1"). This detection signal SET is applied as a preset signal to the flip-flops FF (1), .. ., FF (4) containing the state of the circuit These flip-flops must be presettable to this end Any solution of X, N and the sequence leading to absorption can be used.

In practice, the value of X will often be greater than or equal to the value of N. For circuits that meet this, there is also another solution. By appropriately assigning binary representations to FSM states and additional logic, occured partial sequences can be "implicitly" stored in the existing flip-flops. As can be seen from Figure 1, the current state of the FSM after the occurrence of a first logic "1" as an input signal can only be one of the states 1, 3, 4, 9, 10, 13, 14, 15 or 16. After a second logic "1" as the input signal, the state is 1, 3, 4, 15 or 16. After a third logic "1" as the input signal, the state is 1, 3 or 4. After a fourth logic "Γ as the input signal, the state 1 or 4, and after a fifth logic "1" as input signal the state is definitely state 1. 1 flip-flop FF (5) is added: XN = 5-4 = 1. By now adding additional logic that causes the value of flip-flop FF (J) to be logic "1" after at least J logic ones as the input signal, for 1 <= J <= X = 5, the contents of the flip-flops automatically "11111" after five ones as the input signal. The derived sequence here is therefore the subsection that has occurred itself. The assignment of the binary representations to the states of the FSM now becomes as follows: states that can be reached after at least J ones as the input signal start with J ones, for example state 15 becomes "11000". This assignment ensures that the additional logic does not involve any unauthorized transitions of state: the transitions created by the additional logic now fit exactly with the represented FSM. By successively supplying ones as an input signal, the values "X" are converted into values known to the simulator. Any further "1" as an input signal ensures that the simulator knows that a subsequent flip-flop no longer has the value "unknown", but has the value "1." So after five ones as an input signal, the flip-flops for the simulator the values "1111Γ: the self-initialization is a fact. Of course, the numbering of the collection of bistable elements is irrelevant. The logic that realizes the associated transitions can again be generated automatically. That this initialization can be accomplished without having to store input signals longer than 1 clock period can be seen as follows: FF (1) is "1" after at least one "1" as the input signal; FF (2) is "1" after at least two logic ones as an input signal; FF (5) is "1" after at least five logic ones as an input signal; is equivalent to: FF (1) is "1" after actual input signal 1; FF (2) is "1" after current input signal 1 and FF (1) is "1"; FF (5) is "1" after actual input signal 1 and FF (1) is "Γ and FF (2) is" 1 "and ... and FF (4) is" Γ.

The simulator can therefore derive the initialization from the current values of the flip-flops and the input signal as well as the given state transitions.

With 5 flip-flops instead of the original 4, the circuit can now be simulated. By using 5 flip-flops there are now unused states, so the logic that realizes the transitions must also work for the unused states.

A combination of both solutions mentioned above is illustrated in figure 4. One additional flip-flop FF (0) (because XN = 1) has been added to the circuit of figure 2. Connected to the clock signal CK, with the input signal CS as input and with the output c (0) connected to the combinational logic CL, this additional flip-flop FF (0) serves to store the value of the input signal in the previous clock period. With other choices of X or N, especially if X> N + 1, more flip-flops are added (X-N> 1); in that case they are used to store the most recent values of the input signal. The additional combinatorial logic and the assignment of binary representations to the states of the FSM are such that an occured partial sequence (i.e. 1 or more consecutive logical ones here) is stored in the additional flip-flop (s) and, if that, the partial sequence. can no longer contain, further in the original flip-flops. The derived sequence here is therefore again the partial sequence itself.

Figure 5 shows a table with a possible assignment of representations to states of this FSM: the absorbing state 1 gets the representation "1111", state 4 becomes "1110", state 3 becomes "1101" (may also be "1100" ), states 15 and 16 are resp. "1011" and "1010" (must at least start with a logical 1). There are no restrictions for the other states.

This satisfies: FF (1) is "1" after 2 ones as the input signal; FF (2) is "1" after 2 ones as the input signal and FF (1) is "1"; FF (3) is "1" after 2 ones as the input signal and FF (1) is "1" and FF (2) is "1"; FF (4) is "1" after 2 ones as the input signal and FF (1) is "Γ and FF (2) is" 1 "and FF (3) is" 1 ".

Thus, after 5 ones as the input signal, the content of the flip-flops for the simulator is automatically "1111": self-initialization.

The logic that realizes the associated transitions can again be generated and optimized automatically.

This embodiment has the following advantages: no pre-settable flip-flops required, no decoding logic required, fewer additional flip-flops required than with the first solution; no unused states and therefore no additional requirements for the combinatorial logic.

It should be noted that for a given sequence of the form "11111" for the input signal, the requirements for assigning the representations imposed by the additional logic are not heavy: the number of states that can be reached after at least J 1's, must not exceed: two to the power (XJ).

It should also be noted that with another FSM an alternating sequence leading to absorption is also possible: for example "101010 ...", where an EXOR gate determines when the absorbing state is exited.

Figure 6 shows a possible implementation of the required additional logic: (for convenience, the connections to the clock signal are omitted) input signal CS is applied to FF (0) for storing the previous input signal. The outputs of FF (0) and CS are applied to AND gate A1, the output of which is connected to OR gate E1, whose input is further connected to an output of the block combinational logic CL. The output of gate E1 is connected to the input of FF (4), the output of which, together with the output of A1, is applied to AND gate A2. Its output is applied to OR gate E2, whose input is further connected to CL. The output of gate E2 is applied to FF (3). This construction has been continued completely analogously for the other flip-flops. A first "1" as an input signal is stored in FF (0), a second "1" gives a "1" at the output of port A1, ie in FF (4), regardless of the value of the other input of port E1. A third "Γ as input signal also gives a" 1 "in FF (3), while FF (4) and FF (0) also retain the value" Γ ". A fourth and fifth "1" also make the last two flip-flops "1".

It should be noted that after adding this additional logic, the total amount of logic can be automatically regenerated and optimized again.

Figure 7 shows a digital integrated circuit provided with a circuit according to the invention. The digital IC includes terminals for supplying a control or input signal CS, a clock signal CK, and a test data input TDI as well as a test data output TDO. The circuit further includes a register of bistable elements BIST and a scan register SCAN, connected to combinatorial logic (shaded area), and Boudary Scan cells BSC, further registers INST, BYP and ID, a multiplexer MUX, as well as a finite state machine circuit FSM according to the invention. For more information about Boundary Scan Test, reference is made to Offenlegungsschrift DE-3727723-A1. The FSM determines state transitions in the registers. Testability with such ICs, implemented in Surface Mounted Technology, is essential.

By adding a small amount of redundant logic and a smart assignment of representations to the states, which hardly limits the transition logic, the finite state machine circuit has become fully simulable. In an integrated circuit this can be realized with only a little extra chip surface.

Claims (6)

Sequential finite state machine circuit, comprising a set of N bistable elements {FF (1), ..., FF (N)} and an associated set of combinatorial logic, the combination of logic values of the bistable elements forming a state of the circuit, which represents a state of a finite state machine, wherein at times determined by a clock signal, under the influence of the combinational logic, of the current state of the circuit and of an input signal, the circuit changes into a next state, wherein the set of combinatorial logic realizes transitions between states of the finite state machine in the circuit, characterized in that by a given sequence of X values of the input signal, {c (0), c (1), .. ., c (X-1)>, starting with c (0), a quiescent state is reached from each state, with each occurring partial sequence <c (0), c (1), ..., c (J-1) } of length J of the given sequence ie of X values of the input signal, where 1 <= J <= X, or a partial sequence of length J derived therefrom, is stored in the circuit. Sequential finite state machine circuit according to claim 1, characterized in that the N bistable elements are presettable and in that the circuit is provided with (X-1) further bistable elements, coupled as a shift register, for storing the (X -1) most recent values of the input signal or values derived therefrom, and further includes decoding logic, fed by the input signal and the (X-1) bistable elements of the shift register, which are a detection signal for the occurrence of the given sequence of X values of the input signal and applies this as a bias signal to the N bias bistable elements. Sequential finite state machine circuit according to claim 1, wherein X> = N, characterized in that the circuit comprises (XN) further bistable elements FF (N + 1), ..., FF (X), and of additional combinatorial logic which, when a partial sequence {c (0), c (1), ..., c (J-1)} occurs, of length J from the given sequence of X values of the input signal, where 1 < = J <= X, each time the first J bistable elements FF (1), ..., FF (J) assume a sequence of J values derived from this sub-sequence, whereby the assignment of representations to states of the finite state machine is that the states are represented by combinations of logical values of the bistable elements that correspond to the derived sequences of J values in the first J values. Sequential finite state machine circuit according to claim 1, wherein X> = N, characterized in that the circuit comprises (XN) further bistable elements, for storing the (XN) most recent values of the input signal or derivative values thereof, the circuit further comprising additional logic which, when a partial sequence {c (0), c (1}, ..., c (J-1)> occurs, of length J from the given sequence of X values of the input signal, where XN <J <= X, each time the first J-X + N bistable elements FF (1), ..., FF (J-X + N) a sequence of J-X derived from this partial sequence + N values, where the assignment of representations to states of the finite state machine is such that the states are represented by combinations of logical values of the bistable elements that correspond to the derivative in terms of the first J-X + N values sequences of J-X + N values. Sequential finite state machine circuit according to claim 1, wherein X <N, characterized in that the circuit is provided with additional logic which occurs when a partial sequence {c (0), c (1), ..., occurs. c (J-1)} of length J from the given sequence of X values of the input signal, where 1 <= J <= X, each time the first J bistable elements FF (1), ..., FF (J) have a assume sequence of J values derived from this sub-sequence, wherein the assignment of representations to states of the finite state machine is such that the states are represented by combinations of logical values of the bistable elements which correspond with respect to the first J values derived sequences of J values, in which the additional logic causes the bistable elements FF (X + 1), ..., FF (N) to correspond to the logic when the entire sequence of X values of the input signal occurs. values of the resting state. Integrated circuit comprising a sequential finite state machine circuit according to any one of claims 1 to 5.