State machines5774738Abstract State machines having a hierarchical arrangement of machines as between a parent state machine 10 and sibling state machines 11, 12, and 14. The parent state machine 10 generates a plurality of outputs constituting its output state as based upon its input state defined by inputs N and its internal state. Part of the input state is defined by a set of inputs 15 which include asynchronous signals such as reset and interrupts. The parent state machine 10 defines or partially defines input states as applied to the respective sibling state machines 11, 12, and 14 by producing a series of output states in response to input states as applied thereto and independent upon an existing internal state. This system enables machine design time to be reliably shortened by virtue of easier validation of tasks assigned to the sibling machines. Claims What is claimed is: Description BACKGROUND OF THE INVENTION
______________________________________
If (reset.sub.-- active) next.sub.-- parent.sub.-- state = PARENT.sub.--
CLEAR:
else
If (sync.sub.-- lost)next.sub.-- parent.sub.-- state = PARENT.sub.--
ALARM;
else
case (current.sub.-- parent.sub.-- state)
PARENT.sub.-- CLEAR
: If (sibling.sub.-- task.sub.-- complete)
next.sub.-- parent.sub.-- state =
PARENT IDLE;
else next.sub.-- parent.sub.-- state =
PARENT CLEAR;
PARENT.sub.-- IDLE
: if (counter = HEADER.sub.-- TRIGGER)
next.sub.-- parent.sub.-- state =
PARENT HEADER;
else next.sub.-- parent.sub.-- state =
PARENT IDLE;
PARENT.sub.-- HEADER
: if (sibling.sub.-- task.sub.-- complete)
next.sub.-- parent.sub.-- state =
PARENT.sub.-- HEADER;
else next.sub.-- parent.sub.-- state =
PARENT.sub.-- HEADER;
PARENT.sub.-- DATA
: if (sibling.sub.-- task.sub.-- complete)
next.sub.-- parent.sub.-- state =
PARENT IDLE;
else next.sub.-- parent.sub.-- state =
PARENT DATA;
PARENT.sub.-- ALARM
: if (sibling.sub.-- task.sub.-- complete)
next.sub.-- parent.sub.-- state =
PARENT IDLE;
else next.sub.-- parent.sub.-- state =
PARENT ALARM;
endcase
______________________________________
Note that the parent is sensitive to asynchronous inputs such as the device reset and the sync lost alarm, regular events such as a counter reaching a trigger value indicative of a transmission time slot, and responses from sibling tasks. When the overall device is to be reset, the parent goes into CLEAR mode. This activates the clear sibling state machine once the reset is removed. Then the parent waits in this mode until the task is removed. Then the parent waits in this mode until the task completes, when it switches into IDLE mode. In this condition, no tasks are active. In the IDLE state, when the counter reaches the HEADER.sub.-- TRIGGER value, the header task is woken. Upon completion of the header task, the parent immediately invokes the data task and waits for that to end. After this has completed, the parent returns to IDLE. Note that if at any stage the sync-lost signal becomes true, the parent will go immediately to the ALARM state, and invoke the alarm task. This will automatically switch off any other task which may be active. In this way, priorities for task ordering can easily be seen and changed if necessary, without the need to consider the details of the operation of each individual task. For the purposes of this example, the CLEAR sibling task will be considered in more detail. The task may be expressed as follows:
______________________________________
if (reset.sub.-- active OR clear.sub.-- task.sub.-- inactive) next.sub.--
clear.sub.-- state =
CLEAR.sub.-- SLEEP;
else
case (current clear.sub.-- state)
CLEAR.sub.-- SLEEP : next.sub.-- clear.sub.-- state = CLEAR.sub.-- INIT;
CLEAR.sub.-- INIT : begin
next.sub.-- memory.sub.-- input = 0;
load.sub.-- memory.sub.-- input = TRUE;
next.sub.-- memory.sub.-- address = 0;
load.sub.-- memory.sub.-- address = TRUE;
increment.sub.-- memory.sub.-- address = FALSE;
next.sub.-- loop.sub.-- counter = MEMORY.sub.-- ADDRESS.sub.-- LIMIT;
load.sub.-- loop.sub.-- counter = TRUE;
increment.sub.-- loop.sub.-- counter = FALSE;
next.sub.-- clear.sub.-- state = CLEAR.sub.-- WRITE;
end
CLEAR.sub.-- WRITE : begin
write.sub.-- request = 1;
if (NOT write acknowledge)
nest.sub.-- clear.sub.-- state = CLEAR.sub.-- WRITE:
else
begin
if (loop.sub.-- counter <> 0)
begin
load.sub.-- memory.sub.-- address = TRUE;
increment.sub.-- memory.sub.-- address = TRUE;
next.sub.-- clear.sub.-- state = CLEAR.sub.-- WRITE;
end else
begin
clear.sub.-- task.sub.-- complete = TRUE;
next.sub.-- clear.sub.-- state = CLEAR.sub.-- IDLE;
end
end
end
end
CLEAR.sub.-- IDLE : next.sub.-- clear.sub.-- state = CLEAR.sub.-- IDLE;
endcase
______________________________________
The above state machine represents a task which simply clears the entire memory address space. It is in SLEEP mode until the parent wakes it up using the clear.sub.-- task.sub.-- inactive signal, and all outputs default to being reset. Once activated, it goes into INIT state, and forces the ram address and data input to zero and the loop counter to the number of addresses to be cleared. From there it passes to the write request state, where a request is made to the memory access controller to write the memory.sub.-- input value to the memory-address. Once this has been done, a decision is made based upon the loop.sub.-- counter value; if it is non-zero, more values are to be written, and a signal that the memory.sub.-- address value is to be incremented is set. This uses the incrementer/adder/decrementer/subtractor in a common block to save space. The loop.sub.-- counter is decremented in the same manner. Once the loop.sub.-- counter reaches zero, the state is set to IDLE, and the parent is signalled that the task has completed. Finally, the clear task waits in IDLE until the parent has changed state and reset the task active line once more. It will be appreciated that this concept may be extended from this very simple example to a more complex sequence generator, and how different functions can be allocated to different sibling tasks, for instance loading of selectable sections of coefficient store into RAM, sorting date tables in RAM any many others. The parent state machine can then be thought of as calling subroutines in a given order and the design concept moves up from addresses to tasks, in a similar manner to a piece of software. For sufficiently generalised state machine tasks, a compiler could be used to speed the design task even more. It will be further appreciated that a task which is a sibling task of a parent state machine may itself constitute a parent with respect to a further sibling task. In the embodiment described thus for the sibling tasks are essentially alternative tasks (i.e. they are invoked one at a time with the parent machine acting as a sequence and there is a single completion line 107 common to all tasks). The siblings may however be arranged to be invoked in parallel, and an embodiment of such a state machine is shown in FIG. 3. Where parts are the same or equivalent to those of FIG. 2, common reference numbers have been used. An example of a parent state machine arranged to invoke sibling tasks in parallel will now be given.
______________________________________
'define wake.sub.-- up.sub.-- read.sub.-- source.sub.-- A
3'b001
'define wake.sub.-- up.sub.-- read.sub.-- source.sub.-- B
3'b010
'define wake.sub.-- up.sub.-- read.sub.-- source.sub.-- C
3'b100
'define.sub.-- kill.sub.-- read.sub.-- source.sub.-- A
3'b110
'define.sub.-- kill.sub.-- read.sub.-- source.sub.-- B
3'b101
'define.sub.-- kill.sub.-- read.sub.-- source.sub.-- C
3'b011
if (reset.sub.-- active)
next.sub.-- woken.sub.-- up.sub.-- list = 3'b000;
if (request.sub.-- from.sub.-- source.sub.-- A)
next.sub.-- woken.sub.-- up.sub.-- list = woken.sub.-- up.sub.-- list
.vertline. 'wake.sub.-- up.sub.-- read.sub.-- source.sub.-- A;
if (request.sub.-- from.sub.-- source.sub.-- B)
next.sub.-- woken.sub.-- up.sub.-- list = woken.sub.-- up.sub.-- list
.vertline. 'wake.sub.-- up.sub.-- read.sub.-- source.sub.-- B;
if (request.sub.-- from.sub.-- source.sub.-- C)
next.sub.-- woken.sub.-- up.sub.-- list = woken.sub.-- up.sub.-- list
.vertline. 'wake.sub.-- up.sub.-- read.sub.-- source.sub.-- C;
if (source.sub.-- A.sub.-- read.sub.-- complete)
next.sub.-- woken.sub.-- up.sub.-- list = woken.sub.-- up.sub.-- list &
'kill.sub.-- read.sub.-- source.sub.-- A;
if (source.sub.-- B.sub.-- read.sub.-- complete)
next.sub.-- woken.sub.-- up.sub.-- list = woken.sub.-- up.sub.-- list &
'kill.sub.-- read.sub.-- source.sub.-- B;
if (source C.sub.-- read.sub.-- complete)
next.sub.-- woken.sub.-- up.sub.-- list = woken.sub.-- up.sub.-- list &
'kill.sub.-- read.sub.-- source.sub.-- C;
if (source.sub.-- A.sub.-- error Or source.sub.-- B.sub.-- error Or
source.sub.-- C.sub.-- error)
begin
next.sub.-- woken.sub.-- up.sub.-- list = 3'b000;
source.sub.-- error.sub.-- warning : = 'SET;
end
______________________________________
In the above example, 3'b001 means the bit binary value "1001". The current output state of the parent machine (the invocation lines of the siblings) is given by a 3-bit binary value defined as "next.sub.-- woken.sub.-- up.sub.-- list". To invoke a task the present value is logically ORed with a 3-bit binary value dependent upon the task to be invoked, for example, to invoke task B the present value is ORed with the 3-bit binary value "010". Equally, to reset the task, the present value is logically ANDed with the masking value "101". In the example, both the invocation values and the termination values are defined as variables. It will be noted that in this example, the number of tasks which may be activated at any one time is anything from zero (as in a reset period), to all 3 if required. It will also be noted that in this case, each sibling task which can be woken up in parallel has its own signal line (FIG. 2) to the parent state machine so that the parent can determine which task has completed. Note also that the number of communication channels between parent and sibling is not necessarily restricted just to start/stop. In the above example, an extra "error" condition is generated by each task, and the behaviour of the parent is modified by these reports, thus in this example sibling returns to the parent include information other than simply completion as was the case in the simpler example. The sibling state machines may be designed to be autonomous if desired. However, if similar task portions exist in more than one sibling, resource storing is possible. For example, in the case of an address generator incrementing an address value is a common task portion. A single incrementer which serves to receive, increment and return an incremented value may be arranged to be shared between tasks. In the case of a parent which invokes one sibling at a time, no conflict in respect of the shared resource can arise. In a paralleled arrangement, a scheduler may be employed to ensure correct allocation of shared resources. Thus it will be realised that known state machine design and efficiency techniques, including interlocking wherein linked state machines signal each other, may be applied to the state machine and parent and sibling machines of the present invention. The code fragments describing example state machines within the context of the examples have been written in the "Verilog" hardware description language. This is for illustration only, and the description could be in any other suitable hardware description language such as VHDL, or in the form of a Programmable Logic Array truth table, or ROM contents, etc. In one design fabrication procedure, Verilog source code is used to simulate the behaviour of the state machine hierarchy, and then used with the Synopsys Design Compiler (TM) to generate an Application Specific Integrated Circuit netlist which can be layed out, fabricated and packaged by a silicon vendor. It is envisaged that a state machine hierarchy in accordance with the present invention may be realised by means of a design tool which receives specifications of the parent and sibling tasks in a high level language in the format of a main routine and a plurality of sub routines. The design tool is arranged further to identify routines which themselves may constitute sibling tasks. A compiler may then be used to translate from the high level language to a suitable hardware description format. In the course of the use of such a design tool, many state machines to perform sibling tasks will be created. Some existing tasks may be made available to the user of the design tool as pre-existing sub routines in a library. In this way, inefficiency caused by the new to design state machines from scratch for every application are reduced. Whatever the design methodology, however, a typical result is an assembly of interconnected logic gates and latches. The required connectivity may be applied to a standardised physical arrangement of logic devices as might be made available as part of a substantially preexisting integrated circuit layout. The character of the state machine may therefore be applied to an uncommitted device by establishing a device interconnection pattern defining the machine itself. This approach brings the benefits of volume integrated circuit technology to bear on application specific state machine fabrication. Particular advantage is possible if the complier approach it adapted best to exploit the resources of the pre-existing layout. It will be appreciated that the present invention has thereby provided a means of designing and realising state machines that does not involve any classical hardware design. Since the design is now comprised of a plurality of relatively less complex state machines, the task of ensuring that the transition table is completely specified is eased. Moreover, when changes are made, validation of the appropriate sibling only is required. A complete validation is unnecessary. The state machines described thus far as embodiments of the invention may be used in a cordless telephone, a portion of the arrangement of which is shown in FIG. 3. In the arrangement, the purpose is to transmit data via a transmission channel 30. Data to be so transmitted is assembled into a random access memory 31 via the various peripherals shown. Data is then relayed to the transmission channel 30 via an encryption arrangement (32, 33). Control of the data transmission is by means of a state machine 37, such as the embodiments of the invention which have been thus far described. The system is synchronised to a clock 34 recovered from a reception channel such that data may be transmitted in a time slot allocated to the particular telephone. The start of the transmission time slot is detected by a counter 36 which provides an input to the state machine 37. The state machine is arranged to provide a sequence of addresses which are fed to the memory area 31 so that the data to be transmitted may be correctly assembled together with its coding, heading and control information. In the arrangement shown, the state machine 37 provides two alternative address sequences via address generators 38 and 39 depending upon whether stored data is being received or transmitted via the radio channel in accordance with the Digital European Cordless Telephone standard (address generator 38), or transferred to or from a coder as Adaptive Digital Pulse Code Modulation data (address generator 39). From the foregoing, the following advantages at least of the present invention will be appreciated. Machine design time can be shortened with greater confidence in integrity by virtue of easier validation of sibling tasks. Reliable modification of tasks and their invocation sequence and timing is facilitated hence interalia variant machines may be speedily realised. Alteration of sequence, which in prior art machine would involve, for example, the movement of a potential large portion of code from one place to another and a consequent re-validation, can be achieved by a much simpler and easily verifiable modification of the controlling parent machine. Hence, testability is improved not only for design verification, but also at device level since test vectors to test the entire arrangement may be more straightforwardally generated Incorporation of asynchronous (non clock linked) events is more straightforward since the effect of such an event on only the affected task needs to be considered.
|
Same subclass Same class Consider this |
||||||||||