GB2461649A

GB2461649A - Programmable communicating finite state machines with mealy communication behaviour

Info

Publication number: GB2461649A
Application number: GB0913420A
Authority: GB
Inventors: Thomas Schlipf; Rolf Fritz; Christopher S Smith; Ulrich Mayer; Jan Van Lunteren
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 2009-08-03
Filing date: 2009-08-03
Publication date: 2010-01-13
Anticipated expiration: 2029-08-03
Also published as: GB0913420D0; GB2461649B

Abstract

Preventing a communication loop in communicating finite state machines by providing two tables, an output next state (OTNS) table and a communication output (COUT) table. The OTNS table is divided into two array data structures, an input compare vector (ICVT1) and an output next state next address table (ONNT). The COUT table is divided into two array data structures, an input compare vector (ICVT2) and a communication output table (COMCONT). Input compare vectors in the ICVT1 are retrieved and fed into comparators. The comparators compare the retrieved input compare vectors with an input signal. When a match is found, a corresponding comparator sets a corresponding selection signal to a pre-determined value to generate an offset value through a multiplexer. An adder adds the offset value and a value stored in a current state start address (CSSA) register, and generates an adding result. The adding result is used as an address to access a row in the ONNT. There is state transition information in that row of the ONNT.

Description

PROGRAMMABLE COMMUNICATING FINITE STATE MACHINES WITH

MEALY COMMUNICATION BEHAVIOR

BACKGROUND

The present invention relates generally to Finite State Machines and more particularly to at least two Finite State Machines adapted to communicate with each other.

1 0 Referring to Figs. 2 and 3, a prior art programmable Finite State Machine (FSM) 20 (i.e., a finite state machine that can be configured to transition to a next state from a current state in response to an input vector; the transition can be dynamically changed upon changing transition rules) consists of a Transition Rule Memory (TRM) 26 comprising a table 26 having all the transition rules that define the FSM. In an example implementation, rules 1 5 Ri. . .R4 are contained in each row of the TRM and these rules are presented in parallel to Rule Selector logic 24. Rule Selector logic compares a test part 28 of each rule (see Figure 3) with a value held in a current state register (CS) 25 and an Input Vector. Upon finding a matching rule in TRM, an output vector in a result part 29 of the matching rule is sent to the output of the FSM. Also, a next state value in the result part 29 of the matching rule is loaded into the current state register 25.

An address generator 27 generates an address for enabling access to the TRM 26 from the value of the CS register 25 and the Input Vector using a hashing scheme. The bits that are selected from the register 25 and the bits that are selected from the input vector are defined by a hash mask 22. According to an exemplary embodiment, a hash mask bit of i defines that a corresponding input bit is selected as an address bit, and a hash mask bit of 0 defines that a corresponding current state bit is selected as an address bit. This Hash mask can be identical for all the states of the FSM or it can depend on a current state of the FSM. In the latter case, the hash mask needs to be a part of an output of the rule selector logic 24 as shown in Fig. 2.

In the former case, the hash mask 22 is statically defined and is set up at initialization time.

Referring to Fig. 3, there is shown an exemplary transition rule format of a prior art FSM. A rule consists of a single array data structure. The array data structure may have at least 6 columns such as a current state column, an input vector column, a colunm containing input mask data which will be used to mask of "Don't care" input values, a next state column, an output vector column.

A network of communicating finite state machines consists of a set of finite state machines which communicate with each other. One type of finite state machine is known as a Mealy type finite state machine. The Mealy type finite state machine uses an input action, i.e., the output depends on an input and a current state. Frequently, when two finite state machines are connected to communicate with each other, they are Mealy type FSM. The advantage of a Mealy type finite state machine is a reduction of the number of states. But, when Mealy type 1 0 finite state machines are connected to communicate with each other, there can be a problem with a combinational loop that is introduced between the two machines.

Referring to Fig. 1, there is shown two Mealy type programmable Finite State Machines 170 and 172 connected to communicate with each other. During normal communication between the two machines, information from machine 170 leaves machine 170 at out port 173, travels along path 175 to in port 177 of Finite State Machine 172. In a similar manner, information from machine 172 leaves machine 172 at out port 179, travels along path 181 to in port 183 of Finite State Machine 170. If the machines 170 and 172 are fully programmable then a combinational loop will result if the array data structures have no clocked behavior during read access (e.g if a Read Address is applied to the array data structure then the read data will be available after some read access delay; no clock transition is involved). Combinational loop means that there is no storing element in a path like a latch or flip-flop. If this is the case (i.e., there is no storing element in the path), then a typical automatic test paftem algorithm (i.e., an algorithm testing a FSM by providing test vectors) does not work, because such algorithm first relies on the fact that there is no combinational loop; not only during a functional behavior test but also during a physical test (i.e., a test for physical failures after manufacturing). Referring to Fig. 1, a combinational loop is shown as a dotted loop 185 and is formed if an internal path is formed between the out port and the in port in each machine. If the two Mealy type finite state machines are hardwired, the synthesis results can be modified such that the combinational loop can be eliminated by removing the dependencies from Communication output signals (i.e., output signals provided to other FSMs; e.g., Cout signals 110-111 shown in Fig. 1) and Communication input signals (i.e., input signals provided from other FSMs; e.g., On signals 112-113). When, however, Mealy type finite state machines (FSMs) are programmable, there is no mechanism which removes the combinational loop between the FSMs.

The present invention is directed to addressing a mechanism to remove a combinational loop between programmable Mealy type FSMs.

BRIEF SUMMARY

According to one embodiment, in each finite state machine the communication signals need to be dependent only from the current state and the input of that machine, not from the communication inputs of the other machine. In this embodiment, a programmable Finite State Machine which can be connected to communicate with another programmable Finite State Machine is provided where each machine has at least two small array data structures (tables) of data where the two array data structures in each programmable finite state machine have been used to prevent a combinational loop between the two machines, e.g., by generating a communication output vector (i.e., an output signal provided to other FSM) which does not depend on a communication input vector (i.e., an input signal provided from other FSM). In each programmable Finite State Machine, one of the small array data structures stores input compare vectors (i.e., input compare vectors are data patterns which may be applied to the FSM as an input vector) ; and the second array data structure stores output vectors (i.e., output signals), next state vectors (i.e., signals indicating next states) and next state start address (i.e., a starting address of a set of rows in a table such as the TRM; the set of rows are devoted to the next state).

In an embodiment there is disclosed a method of controlling a programmable Finite State Machine, the method comprising: providing a first array data structure and a second array data structure, the first array data structure only storing input compare vectors corresponding to external input vectors and communication input vectors, the second array data structure storing output vectors, next state values and first next state start addresses, a first next state start address pointing to a beginning of a set of rows describing state transitions of a corresponding next state of the FSM; accessing a row of the first array data structure according to a current state value stored in a first register; retrieving the input compare vectors in the row of the first array data structure; comparing, at at least one comparator, each of the input compare vectors from the first array data structure with an input signal representing a concatenation of an external input vector and a communication input vector; setting a corresponding selection signal to a pre-determined value if a comparator finds a match between an input compare vector from the first array data structure and the input signal; operating a first multiplexer according to the corresponding selection signal; generating a first offset value from the first multiplexer in response to the corresponding selection signal; adding, at a first adder, the first offset value with a current state start address stored in a second register, the current state start address representing an address of the second array data structure which corresponds to a beginning of a set of rows describing state transitions of a current state of the FSM; accessing a row in the second array data structure based on a result from the first adder; loading a next state value from the row in the second array data structure into a first register; loading a first next state start address from the row in the second array data structure into second register; and providing an output vector in the row in the second array data structure as an output.

In a ftirther embodiment, the method further comprises: providing a third array data structure and a fourth array data structure, the third array data structure only storing input compare vectors only corresponding to the external input vectors and the fourth array data structure storing the communication output vectors and second next state addresses.

In a ftirther embodiment, the method further comprises: accessing a row of the third array data structure according to the current state value stored in the first register; retrieving input compare vectors in the row of the third array data structure; comparing, at a comparator, each of the input compare vectors from the third array data structure with the external input vector; setting a corresponding selection signal to a pre-determined value if a comparator finds a match between an input compare vector from the third array data structure and the external input vector; operating a second multiplexer according to the corresponding selection signal; generating a second offset value from the second multiplexer in response to the corresponding selection signal; adding, at a second adder, the second offset value with a third value stored in a third register, the third value indicating a current state start address associated with the fourth array data structure; accessing a row in the fourth array data structure based on a result from the second adder; loading a next state start address in the row in the fourth array data structure to third register; and providing an communication output vector in the row in the fourth array data structure as a communication output.

In an embodiment there is disclosed a system of controlling a programmable Finite State Machine, the system comprising: means for accessing a row of the first array data structure according to a current state value stored in a first register; means for retrieving the input compare vectors in the row of the first array data structure; at least one comparator comparing each of the input compare vectors from the first array data structure with an input signal representing a concatenation of an external input vector and a communication input vector; means for setting a corresponding selection signal to a pre-determined value if a comparator finds a match between an input compare vector from the first array data structure and the input signal; a first multiplexer operating according to the corresponding selection 1 0 signal and generating a first offset value in response to the corresponding selection signal; a first adder adding the first offset value with a current state start address stored in a second register, the current state start address representing an address of the second array data structure which corresponds to a beginning of a set of rows describing state transitions of a current state of the FSM; means for accessing a row in the second array data structure based 1 5 on a result from the first adder; means for loading a next state value from the row in the second array data structure into a first register; means for loading a first next state start address from the row in the second array data structure into second register; and means for providing an output vector in the row in the second array data structure as an output.

The foregoing has outlined, rather broadly, the preferred feature of the present invention so that those skilled in the art may better understand the detailed description of the invention that follows. Additional features of the invention will be described hereinafter that form the subject of the claim of the invention. Those skilled in the art should appreciate that they can readily use the conception and specific embodiment as a base for designing or modifying the structures for carrying out the same purposes of the present invention and that such other features do not depart from the spirit and scope of the invention in its broadest form.

BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS

Other aspects, features, and advantages of the present invention will become more fully apparent from the following detailed description, the appended claims, and the accompanying drawings in which similar elements are given similar reference numerals.

Fig. 1 illustrates a diagram showing presence of a combinational loop between two programmable finite state machines connected to communicate with each other in accordance

with a prior art;

Fig. 2 illustrates a prior art FSM mechanism which can create a combinational loop between two communicating programmable finite state machines; Fig. 3 illustrates a transition rule format for the prior art mechanism described in Fig. 2; 1 0 Fig. 4 illustrates two tables, an OTNS table and a COUT table, for use in an FSM, according to one embodiment of the present invention.

Fig. 5 illustrates splitting the OTNS table from Fig. 4 into two array data structures for use in the FSM according to one embodiment of the present invention; Fig. 6 illustrates splitting the COUT table from Fig. 4 into two array data structures for use in the FSM according to one embodiment of the present invention; Fig. 7 illustrates a block diagram of an FSM according to one embodiment of the present invention utilizing the two array data structures illustrated in Fig. 5; Fig. 8 illustrates a block diagram of an FSM according to one embodiment of the present invention utilizing the two array data structures illustrated in Fig. 6; Fig. 9 illustrates a data processing system configured in accordance with an embodiment of the present invention.

DETAILED DESCRIPTION

Fig. 4 illustrates that communicating Finite State machines are specified in order to distinguish communicating signals such as Cm and Cout signals in Fig. 1 from normal input/output signals such as ml, 1n2, Out 1 and Out2 in Fig. 1. In the prior art, a state transition table of a FSM consists of a Current State column, an Tnput Vector column, an Output Vector column, and a Next State column. However, according to one embodiment of the present invention, as shown in Figs. 4 and 9, a computing system 200 provides two tables, an OTNS (OuTput Next State) table 41 and COUT (Communication OUTput) table 46. The OTNS table 41 is very similar to a traditional state transition table. Thus, the OTNS table 41 has at least five columns such as a current state column 42 indicating a current state of the FSM, two input vector columns (an external input vector 43 provided from other components except other FSMs and a communication input vector 47 provided from other FSMs), an output vector column 44 indicating an output signal of the FSM at a next clock cycle, a next state column 45 indicating a next state of the FSM at a next clock cycle. In the COUT table 46, there are at least three columns such as a current state column 48 indicating a current state of the FSM, an input vector column 49 indicating an external input vector (i.e., an external input vector 43) and a communication output vector 50 indicating communication output signals sent from the FSM to other FSMs.

According to one embodiment of the present invention, as shown in Fig. 5, the computing 1 5 system 200 splits the OTNS table 41 into two array data structures, an Input Compare Vector Table 1 (57) and an ONNT (Output Next state Next address Table) table 52. The Input Compare Vector Table (ICVT) 1 (57) stores Input Compare Vectors. A bit width of an Input Compare Vector in the first array data structure (ICVT 1) is the sum of the number of bits of a corresponding External Input Vector and the number of bits of a corresponding Communication Input Vector. An Input Compare Vector defines a bit pattern which might occur on inputs signals representing the External Input Vector and the Communication Input Vector. For example, an input compare vector at the first row and the first column of the IICVT 1(57) is designated as ilO cil_0. ilO cilO represents a concatenation of an external input vector (ilO) and a communication input vector (cilO). The ICVT 1 (57) may be indexed and accessed using a current state value stored in a current state (CS) register (e.g., the CS register 146 in Fig. 7). A row of the ICVT 1 (57) stores all possible input signal patterns (i.e., all possible input compare vectors) for a single state. For example, the second row (58) of the ICVT 1 (57) is devoted to state S2 and therefore stores four input compare vectors i20 ci2O to i2_3 ci2_3.

The ONNT table 52 includes, but is not limited to, three columns, an output vector column 53 indicating an output signal at a next clock cycle, a next state column 52 indicating a next state at a next clock cycle and a next state start address (NSSA) column 55. The NSSA is loaded into a Current State Start Address register (e.g., a CSSA register 40 in Fig.7) in the same way that a next state value is loaded to the CS register (e.g., a CS register 146 in Fig. 7). As illustrated in Fig. 5, the NSSA points to a beginning of a set of rows describing state transitions of a corresponding next state of the FSM. For example, a third row (59) of the ONNT table 52 stores a value "6" as an NSSA value. (The ONNT table 52 has 8 rows (a 0th row to 7th row). The third row (59) indicates S3 as a next state. The 6th row (60) of the ONNT table 52 is the first row describing a state transition of a state S3. Thus, the third row (59) has a value of "6" in the NSSA column.

The OTNS table 41 in Fig. 5 includes three different states, 51, S2 and S3. However, the OTNS table 41 can include a plurality different states. For example, the OTNS table 41 illustrated in Fig. 5 shows four transitions from state S2. Corresponding external input vectors are designated as i20, i21, i22 and i2_3. However, the OTNS table 41 can include a plurality of state transitions from a state, and can include a plurality of external input vectors.

If a FSM operates according to the OTNS table 41 in Fig. 5, the FSM is in state S2, an 1 5 external input vector matches i2_1, and a communication input vector matches ci2l, then the FSM would produce an output vector o21 and goes to state S3 in a next clock cycle.

Adjacent rows in the OTNS table 41 may belong to the same current state. For example, the 0th row and 1st row are devoted for a state transition description for state Si. The 2'' row to row are devoted for state transition descriptions for state S2. The 6thi row and 7th row are devoted to describe state transitions for state S3.

Referring to Fig. 6, the computing system 200 divides the COUT table 46 of Fig. 4 into two array data structures designated as an Tnput Compare Vector Table 2 (ICVT 2) (62) and a communication output table (COM-CONT) 72. Vectors stored in the ICVT2 (62) are input compare vectors only corresponding to external input vectors to an FSM machine. The ICVT2 (62) does not include any input compare vector corresponding to a communication input vector. The COM-CONT table 72 stores communication output vectors and next state start addresses associated with the COM-CONT 72. For example, the COUT table 46 includes three different external input vectors, ii 0, i20 and i2_ 1 (x refers to don't care signal and can be considered either of the external input vectors.). A row of the ICVT2 (62) describes all possible input signal patterns (i.e., all possible input compare vectors) for a state. For example, a row (61) of the ICVT2 (62) is devoted for state S2 and therefore describes two external input vectors, i20 and i21. Tn the COM-CONT table 72, a communication output vector corresponds to the communication output vector in the COUT table 46. A next state start address in the COM-CONT table 72 points to a beginning of a set of rows which are devoted to a single state. For example, a row 63 of the COM-CONT table 72 includes a communication output vector co2_1, which is generated when a current state is S2 and an external input vector is i21. According to the OTNS table 41 in Fig. 5, when the current state is S2, the external input vector is i2_1, and the communication input vector is ci2l, the next state becomes S3. Tn the COM-CONT 72 in Fig. 6, an address of row(s) devoted to state S3 starts at 3rd row (64). Thus, the row 63 of the COM-CONT table 72 includes "3" in the next state start address column.

Referring to Figs. 7 and 8, following is a description of an operation of one embodiment of the present invention. Fig. 7 illustrates a block diagram of an exemplary FSM configured to implement state transitions and generate outputs without causing a combinational loop. As shown in Fig. 7, the present invention does not require a hashing scheme to generate an address to access a table. The present invention compares a new external input vector and each input compare vector. In the present invention, there is no comparison based on a current state or a next state.

In Fig. 7, it is assumed that a finite state machine (FSM) is in state S2 and that a CSSA (Current State Start Address) 1 register 40 has a value of 2 because a first state transition to state S2 is described in the 2'" row of the ONNT 52. The CSSA 1 register 40 stores a current state start address representing an address of the ONNT 52 which corresponds to a beginning of a set of rows describing state transitions of a current state of the FSM. Upon starting a state transition execution, the computing system 200 accesses the 1st row 71 of the ICVT1 table addressed by the CS register 146. The CS register 146 may store S2 as a current state value and a state transition of S2 is described at 1st row 71 of the ICVT1 table. The computing system 200 accesses the 1st row 71 of the ICVT1 by calculating an accessing address, e.g., by executing a current state "value-I". Then, the computing system 200 retrieves four input compare vectors cv2O to cv2_3 from the 1St row 71 of the ICVT 1.

The retrieved four input compare vectors are input to a set of comparators C0-C3. The computing system 200 also receives an external input vector from a component other than a FSM and a communication input vector, and provides an input signal (79) that is a concatenation of the external input vector and the communication input vector as another input of the comparators.

It is further assumed that the input signal (79) includes a value that matches with an input compare vector cv2l (box 73 in 71). Then, based on this assumption, a comparator Cl (74) would have a match condition and set a corresponding selection signal Ci Sel 75 to a pre-determined value, (e.g., 1). All other comparators will not have a match condition and corresponding selection signals Cx_Sel will be zero. The computing system 200 provides these selection signals as inputs to a multiplexer 50. The multiplexer 50 associates each selection signal with an offset value. For example, an offset value 0 is associated with Comparator 0, an offset value 1 is associated with comparator Cl and so on. In this example, the multiplexer 50 generates an offset value of 1, because the selection signal C iSel is 1.

1 0 Then, the multiplexer 50 feds the generated offset value of 1 to an adder 48. The adder 48 also receives, for example, a value of"2" from a CSSA1 register 40 as another input. A result of the adder 48 will, therefore, have a value of 2+1=3. The computing system 200 uses the value of 3 as an address of the ONNT table 52 to point to a 3' row (76) of the ONNT table 52. The row (76) stores state transition information associated with a current state S2 and an input 1 5 compare vector cv2l (i.e., an external input vector i21 and a communication input vector ci2_ 1). In other words, the row (76) indicates that the FSM makes a transition to state S3 and outputs o2_1 as an output signal at a next clock cycle when a current state is S2 and an input compare vector cv2_ 1 is matched with an external input vector i2_ 1 and/or a communication input vector ci2l. Thus, the computing system 200 provides the output vector o2_1 in the row (76) to an output port of the FSM. The computing system 200 loads a next state value S3 in the row (76) into the CS register 146. The computing system 200 also loads a next state start address "6" into the CSSA1 register 40 during a next clock cycle.

Fig. 8 illustrates a block diagram for generating a communication output vector according to one embodiment of the present invention. The computing system 200 accesses a row of the ICVT2 (62) based on the current state value stored in the CS register 146. As assumed above, the FSM is in state S2. The 1st row (87) of the ICVT2 (62) describes all the possible input compare vectors that are relevant for generating a communication output signal if the FSM is in state S2. In this example, the computing system 200 access the 1st row (87) of the ICVT2 (62). Then, the computing system applies the external input vectors (80) as the first input to a set of comparators (64) and applies the Input Compare Vectors from the 1st row (87) of the ICVT 2 (62) as the second input to the comparators.

It is further assumed that the external input vector includes a value that matches with the input compare vector value i20 from the TCVT2 (62). Then, in this case a comparator CO would have a match condition and set a corresponding selection signal CO_Se! to a pre-determined value, e.g., 1. All other comparators will not have a match condition and the corresponding selection signals Cx Sel will be zero. The computing system 200 provides these selection signals as inputs to a multiplexer 81. The multiplexer 81 associates each selection signal with an offset value. For example, an offset value of "0" is associated with Comparator 0, an offset value of"1" is associated with comparator Cl and so on. In this example, the multiplexer 81 generates an offset value of 0, because only the selection signal CO_Sel is 1.

1 0 Then, the multiplexer 81 inputs the generated offset value of "0" to an adder 68. The adder 68 also receives, for example, a value of "2" from CSSA (Current State Start Address) 2 register 86 as another input. The CSSA2 register 86 stores an address of COM-CONT 72 which corresponds to a first row describing a current state of the FSM. A result of the adder 48 will, therefore, have a value of 2+0=2. The computing system 200 uses the value of "2" as an address of the COM-CONT 72 to point to a 2nd row (85) of the COM-CONT table 72. The row (85) stores state transition information associated with a current state S2. The computing system 200 provides a communication output vector co2_1 in the row (85) to a communication output port of the FSM. The computing system 200 loads a next state start address "3" into the CSSA2 register 86 during a next clock cycle.

A computer-based system is depicted in Fig. 9 herein by which the method of the present invention may be carried out. Computer system includes a processing unit, which houses a processor, memory and other systems components that implement a genera! purpose processing system or computer that may execute a computer program product. The computer program product may comprise media, for example a compact storage medium such as a compact disc, which may be read by the processing unit through a disc drive, or by any means known to the skilled artisan for providing the computer program product to the general purpose processing system for execution thereby.

The computer program product comprises all the respective features enabling the implementation of the methods described herein, and which -when loaded in a computer system -is able to carry out these methods. Computer program, software program, program, or software, in the present context means any expression, in any language, code or notation, of a set of instructions intended to cause a system having an information processing capability to perform a particular function either directly or after either or both of the following: (a) conversion to another language, code or notation; and/or (b) reproduction in a different material form.

The computer program product may be stored on hard disk drives within processing unit (as mentioned) or may be located on a remote system such as a server (not shown), coupled to processing unit, via a network interface such as an Ethernet interface. Monitor, mouse and keyboard are coupled to the processing unit, to provide user interaction. Printer is shown coupled to the processing unit via a network connection, but may be coupled directly to the processing unit.

More specifically, as shown in Fig. 9, the computer system 200, includes one or more processors or processing units 210, a system memory 250, and an address/data bus structure 201 that connects various system components together. For instance, the bus 201 connects the processor 210 to the system memory 250. The bus 201 can be implemented using any kind of bus structure or combination of bus structures, including a memory bus or memory controller, a peripheral bus, an accelerated graphics port, and a processor or local bus using any of a variety of bus architectures such as ISA bus, an Enhanced ISA (EISA) bus, and a Peripheral Component Interconnects (PCI) bus or like bus device. Additionally, the computer system 200 includes one or more monitors 219 and, operator input devices such as a keyboard, and a pointing device (e.g., a "mouse") for entering commands and information into computer, data storage devices, and implements an operating system such as Linux, various Unix, Macintosh, MS Windows OS, or others.

The computing system 200 additionally includes: computer readable media, including a variety of types of volatile and non-volatile media, each of which can be removable or non-removable. For example, system memory 250 includes computer readable media in the form of volatile memory, such as random access memory (RAM), and non-volatile memory, such as read only memory (ROM). The ROM may include an input/output system (BIOS) that contains the basic routines that help to transfer information between elements within computer device 200, such as during start-up. The RAIVI component typically contains data and/or program modules in a form that can be quickly accessed by processing unit. Other kinds of computer storage media include a hard disk drive (not shown) for reading from and writing to a non-removable, non-volatile magnetic media, a magnetic disk drive for reading from and writing to a removable, non-volatile magnetic disk (e.g., a "floppy disk"), and an optical disk drive for reading from and/or writing to a removable, non-volatile optical disk such as a CD-ROM, DVD-ROM, or other optical media. Any hard disk drive, magnetic disk drive, and optical disk drive would be connected to the system bus 201 by one or more data media interfaces (not shown). Alternatively, the hard disk drive, magnetic disk drive, and optical disk drive can be connected to the system bus 201 by a SCSI interface (not shown), or other coupling mechanism. Although not shown, the computer 200 can include other types of computer readable media. Generally, the above-identified computer readable media provide non-volatile storage of computer readable instructions, data structures, program modules, and 1 0 other data for use by computer 200. For instance, the readable media can store an operating system (O/S), one or more application programs, such as video editing client software applications, and/or other program modules and program data for enabling video editing operations via Graphical User Interface (GUi).

Input/output interfaces 245 are provided that couple the input devices to the processing unit 210. More generally, input devices can be coupled to the computer 200 through any kind of interface and bus structures, such as a parallel port, serial port, universal serial bus (USB) port, etc. The computer environment 200 also includes the display device 219 and a video adapter card 235 that couples the display device 219 to the bus 201. In addition to the display device 219, the computer environment 200 can include other output peripheral devices, such as speakers (not shown), a printer, etc. I/O interfaces 245 are used to couple these other output devices to the computer 200.

As mentioned, computer system 200 is adapted to operate in a networked environment using logical connections to one or more computers, such as a server device that may include all of the features discussed above with respect to computer device 200, or some subset thereof Tt is understood that any type of network can be used to couple the computer system 200 with the server device, such as a local area network (LAN), or a wide area network (WAN) (such as the Internet). When implemented in a LAN networking environment, the computer 200 connects to local network via a network interface or adapter 229. When implemented in a WAN networking environment, the computer 200 connects to the WAN via a high speed cable/dsl modem 280 or some other connection means. The cable/dsl modem 280 can be located internal or external to computer 200, and can be connected to the bus 201 via the I/O interfaces 245 or other appropriate coupling mechanism. Although not illustrated, the computing environment can provide wireless communication functionality for connecting computer 200 with remote computing device, e.g., an application server (e.g., via modulated radio signals, modulated infrared signals, etc.).

Although a few examples of the present invention have been shown and described, it would be appreciated by those skilled in the art that changes might be made in these embodiments without departing from the principles and spirit of the invention, the scope of which is defined in the claims and their equivalents.

Claims

CLAIMS1. A method of controlling a programmable Finite State Machine (FSM), the method comprising: providing a first array data structure and a second array data structure, the first array data structure only storing input compare vectors corresponding to external input vectors and communication input vectors, the second array data structure storing output vectors, next state values and first next state start addresses, a first next state start address pointing to a beginning of a set of rows describing state transitions of a corresponding next state of the FSM; accessing a row of the first array data structure according to a current state value stored in a first register; retrieving the input compare vectors in the row of the first array data structure; comparing, at at least one comparator, each of the input compare vectors from the first 1 5 array data structure with an input signal representing a concatenation of an external input vector and a communication input vector; setting a corresponding selection signal to a pre-determined value if a comparator finds a match between an input compare vector from the first array data structure and the input signal; operating a first multiplexer according to the corresponding selection signal; generating a first offset value from the first multiplexer in response to the corresponding selection signal; adding, at a first adder, the first offset value with a current state start address stored in a second register, the current state start address representing an address of the second array data structure which corresponds to a beginning of a set of rows describing state transitions of a current state of the FSM; accessing a row in the second array data structure based on a result from the first adder; loading a next state value from the row in the second array data structure into a first register; loading a first next state start address from the row in the second array data structure into second register; and providing an output vector in the row in the second array data structure as an output.
2. The method of claim 1 further comprising: providing a third array data structure and a fourth array data structure, the third array data structure only storing input compare vectors only corresponding to the external input vectors and the fourth array data structure storing the communication output vectors and second next state addresses.
3. The method of claim 2, further comprising: accessing a row of the third array data structure according to the current state value stored in the first register; 1 0 retrieving input compare vectors in the row of the third array data structure; comparing, at a comparator, each of the input compare vectors from the third array data structure with the external input vector; setting a corresponding selection signal to a pre-determined value if a comparator finds a match between an input compare vector from the third array data structure and the 1 5 external input vector; operating a second multiplexer according to the corresponding selection signal; generating a second offset value from the second multiplexer in response to the corresponding selection signal; adding, at a second adder, the second offset value with a third value stored in a third register, the third value indicating a current state start address associated with the fourth array data structure; accessing a row in the fourth array data structure based on a result from the second adder; loading a next state start address in the row in the fourth array data structure to third register; and providing an communication output vector in the row in the fourth array data structure as a communication output.
4. A system of controlling a programmable Finite State Machine, the system comprising: means for providing a first array data structure and a second array data structure, the first array data structure only storing input compare vectors corresponding to external input vectors and communication input vectors, the second array data structure storing output vectors, next state values and first next state start addresses, a first next state start address pointing to a beginning of a set of rows describing state transitions of a corresponding next state of the FSM; means for accessing a row of the first array data structure according to a current state value stored in a first register; means for retrieving the input compare vectors in the row of the first array data structure; at least one comparator comparing each of the input compare vectors from the first array data structure with an input signal representing a concatenation of an external input vector and a communication input vector; 1 0 means for setting a corresponding selection signal to a pre-determined value if a comparator finds a match between an input compare vector from the first array data structure and the input signal; a first multiplexer operating according to the corresponding selection signal and generating a first offset value in response to the corresponding selection signal; 1 5 a first adder adding the first offset value with a current state start address stored in a second register, the current state start address representing an address of the second array data structure which corresponds to a beginning of a set of rows describing state transitions of a current state of the FSM; means for accessing a row in the second array data structure based on a result from the first adder; means for loading a next state value from the row in the second array data structure into a first register; means for loading a first next state start address from the row in the second array data structure into second register; and means for providing an output vector in the row in the second array data structure as an output.
5. The system of claim 4 further comprising: means for providing a third array data structure and a fourth array data structure, the third array data structure only storing input compare vectors only corresponding to the external input vectors and the fourth array data structure storing the communication output vectors and second next state addresses.
6. The system of claim 5, further comprising: means for accessing a row of the third array data structure according to the current state value stored in the first register; means for retrieving input compare vectors in the row of the third array data structure; at least one comparator comparing each of the input compare vectors from the third array data structure with the external input vector; means for setting a corresponding selection signal to a pre-determined value if a comparator finds a match between an input compare vector from the third array data structure and the external input vector; a second multiplexer operating according to the corresponding selection signal and generating a second offset value in response to the corresponding selection signal; a second adder adding the second offset value with a third value stored in a third register, the third value indicating a current state start address associated with the fourth array data structure; 1 5 means for accessing a row in the fourth array data structure based on a result from the second adder; means for loading a next state start address in the row in the fourth array data structure to third register; and means for providing a communication output vector in the row in the fourth array data structure as a communication output.