State machine architecture for concurrent processing of multiplexed data streams

• US 5,640,398 A
• Filed: 11/01/1995
• Issued: 06/17/1997
• Est. Priority Date: 11/01/1995
• Status: Expired due to Term

• Current Assignee: Pmc-Sierra Limited (Microchip Technology Incorporated)
• Original Assignee: PMC-Sierra Incorporated (Microchip Technology Incorporated)
• Inventors: Mok, Winston, Carr, Larrie
• Primary Examiner(s): HSU, ALPUS
• Application Number:
  US08/551,530
• Time in Patent Office: 594 Days
• Field of Search: 370/360, 370/375, 370/376, 370/503, 370/505, 370/516, 370/517, 370/518, 370/537, 370/907, 375/362, 375/365, 375/366, 375/371, 375/372, 375/373, 375/376
• US Class Current: 370/376
• CPC Class Codes: G06F 7/00 Methods or arrangements for processing data by operating upon the order or content of the data handled logic circuits H03K19/00
• CPC Class Codes: H04J 3/0623 Synchronous multiplexing systems, e.g. synchronous digital hierarchy/synchronous optical network (SDH/SONET), synchronisation with a pointer process

Abstract

A plurality of data streams time-division multiplexed into a single stream are concurrently processed. State vectors characteristic of each data stream are stored in unique read-write memory locations having known addresses. During an initial clock cycle the next sequential data word is received from the single data stream and an input state vector characteristic of the data stream in which the received data originated is retrieved from the memory. The data word and the input state vector are passed to state machine logic which, during one or more intermediate clock cycles, processes the data word and the input state vector to produce an output data word and an output state vector. During a final clock cycle the output data word is transferred to an outgoing data stream and the output state vector is stored in the memory location from which the input state vector was retrieved. The process repeats sequentially, with the next group of three clock cycles commencing immediately after the initial clock cycle of the immediately preceding group of three clock cycles.

Claims

1. Apparatus for concurrently processing a plurality of data streams time-division multiplexed into a single stream, each of said data streams containing a plurality of data words and having a characteristic state vector, said apparatus comprising:

a. read-write memory means having a plurality of addressable memory locations for storing said state vectors;

b. a pipeline for;

i. during an initial clock cycle;

(1) receiving an input data word from one of said data streams;

(2) receiving, from a predefined memory location address in said memory means, an input state vector characterizing said one data stream;

(3) receiving said predefined memory location address of said input state vector;

ii. during one or more intermediate clock cycles, processing said input data word and said input state vector to yield an output data word and an output state vector;

iii. during a final clock cycle;

(1) transferring said output data word to an outgoing data stream;

(2) transferring said output state vector to said predefined memory location address in said memory means; and

,

c. control means coupled to said memory means and to said pipeline for synchronizing operation thereof.

2. Apparatus as defined in claim 1, wherein said pipeline further comprises first delay means, second delay means and state machine logic means, wherein:

a. said first delay means is for;

i. delayed storage and output to said state machine logic means of said input data word and said input state vector;

ii. delayed storage and output to said second delay means of said predefined memory location address;

b. said state machine logic means performs said processing during said one or more intermediate clock cycles;

c. said second delay means is for;

i. delayed storage and output to said memory means of said output state vector and said predefined memory location address; and

,

ii. delayed storage and output of said output data word.

3. Apparatus as defined in claim 1, wherein:

a. said control means further comprises a clock having a selected clock cycle; and

,

b. said pipeline has a delay characteristic equal to one of said clock cycles.

4. Apparatus as defined in claim 1, wherein:

a. said control means further comprises a clock having a selected clock cycle; and

,

b. said pipeline has a delay characteristic equal to a selected multiple of said clock cycles.

5. Apparatus as defined in claim 1, wherein said memory means is a random access memory.

6. A method of concurrently processing a plurality of data streams time-division multiplexed into a single stream, said method comprising the steps of:

a. for each one of said data streams, storing a state vector characteristic of said one stream in a read-write memory location having a predefined address;

b. during an initial clock cycle;

i. receiving a next sequential data word from said single stream, said data word originating in one of said plurality of data streams;

ii. retrieving from one of said memory locations an input state vector characteristic of said originating one of said plurality of data streams;

c. after said initial clock cycle, delivering said data word and said input state vector to a state machine logic means and then, during one or more intermediate clock cycles following said initial clock cycle, processing said data word and said input state vector in said state machine logic means to produce an output data word and an output state vector;

d. during a final clock cycle following said one or more intermediate clock cycles;

i. transferring said output data word to an outgoing data stream;

ii. storing said output state vector in said memory location from which said input state vector was retrieved; and

,

e. sequentially repeating said steps b, c and d.

7. A method as defined in claim 6, further comprising performing said processing of said data word and said input state vector during one and only one of said intermediate clock cycles.

8. A method as defined in claim 6, further comprising performing said processing of said data word and said input state vector during a selected plurality of said intermediate clock cycles.

9. A method as defined in claim 6, further comprising, during said processing of said data word and said input state vector, preserving said address of said memory location from which said input state vector was retrieved.

10. A method as defined in claim 6, wherein said initial, intermediate and final clock cycles are repeated in endless, grouped succession such that a final clock cycle in a first such group occurs simultaneously with an intermediate clock cycle in a second such group immediately following said first group and simultaneously with an initial clock cycle in a third such group immediately following said second group, said method further comprising:

a. immediately after said initial clock cycle of said first group, initiating repetition of said steps 6(b) through 6(e) with respect to said second group; and

,

b. immediately after said initial clock cycle of said second group, initiating repetition of said steps 6(b) through 6(e) with respect to said third group.