Data pipeline system and data encoding method

• US 5,907,692 A
• Filed: 02/24/1997
• Issued: 05/25/1999
• Est. Priority Date: 06/30/1992
• Status: Expired due to Term

• Current Assignee: Coases Investments Bros LLC (Intellectual Ventures LLC)
• Original Assignee: Discovision Associates (Pioneer Corporation)
• Inventors: Wise, Adrian Philip, Robbins, William Philip, Sotheran, Martin William
• Primary Examiner(s): Donaghue, Larry D.
• Assistant Examiner(s): Davis, Jr., Walter D.
• Application Number:
  US08/804,620
• Time in Patent Office: 820 Days
• Field of Search: 395/800.01, 395/800.16, 395/800.18, 395/376, 395/377, 395/500, 348/441, 382/232
• US Class Current: 712/201
• CPC Class Codes: G06F 9/3871 Asynchronous instruction pipeline, e.g. using handshake signals between stages
• CPC Class Codes: G06F 9/3873 Variable length pipelines, e.g. elastic pipeline
• CPC Class Codes: G06F 9/4494 data driven
• CPC Class Codes: H04N 19/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• CPC Class Codes: H04N 19/42 characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation H04N19/635 takes precedence
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding

Abstract

A pipeline structure processes data in a series of stages, each of which has a data input latch (LDIN) and passes it on to the next stage in the pipeline via a data output latch (LDOUT). The stages are preferably connected to two non-overlapping clock phases (PH0, PH1). Adjacent stages are also connected via a validation line (IN_-- VALID, OUT_-- VALID) and an acceptance line (IN_-- ACCEPT, OUT_-- ACCEPT), and in some embodiments also via an extension bit line (IN_-- EXTN, OUT_-- EXTN). Input data is transferred from any stage to the following device on every complete period of both clock signals only if both the validation and acceptance signals in the respective latch are in an affirmative state, whereby data is transferred between stages regardless of the state of the validation and acceptance signals in other stages. A two-wire interface is thus formed between the stages. Address decoding circuitry may also be included in any of the stages so that a stage manipulates the input data stream only when one or more current data words have a predetermined bit pattern. The extension bit line conveys an extension bit that separates fields of different data blocks in the data stream. The invention also includes a method for uniquely encoding data blocks so that only intended pipeline stages are activated, with others simply passing input data through.

Claims

1. In a data pipeline system for processing data, the system having a plurality of sequential pipeline stages, an input data storage device (LDIN) and an output data storage device (LDOUT) in each stage, with the output data storage device of each pipeline stage connected to the input data storage device of the next successive pipeline stage, the combination comprising:

electrical validation circuitry in each stage to generate a validation signal (IN_-- VALID, OUT_-- VALID) for a first state when data stored in said stage is valid and for a second state when data stored in said stage is invalid, said state defining said stage'"'"'s ability to accept data, said validation circuitry including at least one validation storage device (LVOUT) to store said validation signal for the corresponding pipeline stage;

an acceptance signal connecting each adjacent pair of pipeline stages and conveying an acceptance signal (IN_-- ACCEPT, OUT_-- ACCEPT) indicative of the ability of said successive pipeline stage to load data stored in the preceding pipeline stage; and

enabling circuitry connected to said data storage devices (LDOUT) for generating an enabling signal to enable loading of data and validation signals into the respective storage devices, wherein;

said data storage devices include a primary data storage device (LDOUT) and a secondary data storage device (LDIN);

said data is loaded into said respective primary data storage devices (LDOUT) and said validation signals are loaded into respective primary validation storage devices (LVOUT) at the same time;

data is loaded into each respective primary data storage device (LDOUT) when said acceptance signal assumes an enabling state; and

said acceptance signal assumes said enabling state only when the acceptance signal associated with the data storage device of said next successive pipeline stage is in said enabling state or said data in said data storage device of said next successive pipeline stage is invalid.

2. A data pipeline system as recited in claim 1, wherein said acceptance signal (IN_-- ACCEPT, OUT_-- ACCEPT) constitutes said enabling signal for said data and validation storage devices.

3. A data pipeline system as recited in claim 1 or claim 2, wherein:

said input data storage device (LDIN) of each stage forms a secondary data storage device and a secondary validation storage device (LVIN) is included in each stage; and

a primary acceptance storage device (LAOUT) is included in each stage to store the state of the acceptance signal (OUT_-- ACCEPT) of said next successive pipeline stage.

4. A data pipeline system as recited in claim 3, wherein:

said primary data and validation storage devices are formed as sections of a single primary storage unit and said secondary data and validation storage devices are formed as sections of a single secondary storage unit.

5. A pipeline system as recited in claim 3, wherein, a secondary acceptance storage device (LAIN) is included in each stage;

and

each stage is connected to a multi-phase, non-overlapping clock (PH0, PH1).

6. A pipeline system as set forth in claim 5, wherein:

said primary data storage device (LDOUT), said primary validation storage device (LVOUT) and said secondary acceptance storage device (LAIN) are enabled by a first clock phase signal (PH1) and said secondary data storage device (LDOUT), said secondary validation storage device (LVOUT) and said primary acceptance storage device (LAIN) are enabled by a second clock phase signal (PH0).

7. A data pipeline system as set forth in claim 1 or claim 2, wherein:

each of said pipeline stages includes predetermined processing circuitry having an active and an inactive mode; and

an output from each secondary data storage device (LDIN) is connected as an input to said primary data storage device (LDOUT) of said corresponding stage via arbitrary logic circuitry.

8. A pipeline system as recited in claim 7, wherein:

predetermined ones of said pipeline stages include a data decoding circuit connected to said output of said secondary data storage device (LDIN), and said processing circuitry of each pipeline stage assumes said active state only when said secondary data storage device contains input data having a predetermined stage activation pattern.

9. A pipeline system as set forth in claim 8, wherein:

each pipeline stage includes a present extension bit input latch (LEIN) and an extension bit output latch (LEOUT) for loading an extension bit under the control of said first clock phase signal (PH0), with said extension bit being transferred from a preceding device via an extension bit conductor (IN_-- EXTN;

OUT_-- EXTN);

said output from said present extension bit input latch (LEIN) being connected to said input of said extension bit output latch (LEOUT);

the loading of said extension bit into said present extension bit input latch (LEIN) being enabled by said first clock signal (PH0) and the loading of said extension bit into said extension bit output latch being enabled by said second clock signal (PH1), said extension bit output latch loading said value of said extension bit previously loaded into said extension bit input latch;

each pipeline stage including a previous extension bit latch (LEPREV) for loading said output from said extension bit output latch (LEOUT) under the control of said first clock signal (PH0);

said extension bit being transferred from said preceding device via said extension bit conductor (IN_-- EXTN;

OUT_-- EXTN) to said input of said present extension bit latch (LEIN); and

said processing circuitry of each pipeline stage assuming said active state only when said previous extension bit, loaded in said previous extension bit latch (LEPREV), is in a predetermined one of two logical states.

10. In a data pipeline system for processing data, comprising:

a plurality of sequential pipeline stages;

an input data storage device (LDIN) and an output data storage device (LDOUT) in each stage, with the output data storage device of each stage connected to the following input data storage device of the next successive stage; and

each stage including predetermined processing circuitry with an active state, which it enters when data entering said stage has a predetermined activation pattern, and an inactive state, in which said stage passes data to said following stage without processing;

at least one of said stages comprising a state machine having a current state and a previous state, and having means for maintaining said previous state;

wherein said stage is activated upon recognition of said predetermined activation pattern only upon a predetermined transition from said previous state to said current state, and

each stage has an unblocked state, in which it is able to receive data without loss of previously stored valid data, and a blocked state, in which said stage contains valid data that cannot be transferred from said corresponding data storage device;

data being transferred into a current one of said pipeline stages even when at least one other pipeline stage following said current stage is in said blocked state; and

each pipeline stage generating an acceptance signal to the immediately preceding pipeline stage with a first state when said stage does not contain valid data and when said stage contains valid data that can be transferred to a following data storage device, and generating a second state when said stage contains valid data that cannot be passed to said data storage device of the next successive stage;

said state machine of said one stage including a present extension bit input latch (LEIN) and an extension bit output latch (LEOUT) for loading an extension bit under the control of a first clock phase signal (PH0), with said extension bit being transferred from a preceding device via an extension bit conductor (IN_-- EXTN;

OUT_-- EXTN);

said output from said present extension bit input latch (LEIN) being connected to said input of said extension bit output latch (LEOUT);

the loading of said extension bit into said present extension bit input latch (LEIN) being enabled by said first clock signal (PH0) and the loading of said extension bit into said extension bit output latch being enabled by a second clock signal (PH1), said extension bit output latch loading said value of said extension bit previously loaded into said extension bit input latch.

11. A pipeline system as set forth in claim 10, wherein

each pipeline stage includes a previous extension bit latch (LEPREV) for loading said output from said extension bit output latch (LEOUT) under the control of said first clock signal (PH0), said extension bit being transferred from said preceding device via said extension bit conductor (IN_-- EXTN;

OUT_-- EXTN) to said input of said present extension bit latch (LEIN); and

said processing circuitry of each pipeline stage assumes said active state only when said previous extension bit, loaded in said previous extension bit latch (LEPREV), is in a predetermined one of two logical states.

12. A method of encoding digital data in a pipeline including a plurality of stages, each stage having an active mode, in which it transforms corresponding work data, and a passive mode, the method comprising the steps of:

a) applying a series of data words as a data stream to a first one of said pipeline stages in the form of digital signals;

b) generating and assigning to predetermined ones of said pipeline stages, respectively, predetermined, unique data activation words, so that each stage assumes its active state only upon receipt of said corresponding data activation word;

c) for a plurality of input data blocks, including in the data stream a sequence of address signals and, for each data word, an extension bit, a series of address bits, and data bits, said extension bit having a first and a second logical state;

d) setting said extension bit to said first logical state for a selected boundary word in each data block and to said second logical state for every other data word in said data block;

e) detecting a predetermined transition of said extension bit between said first logical state and said second logical state, and

f) thereupon setting said address bits equal to corresponding bits of said activation pattern for said pipeline stage for which said data bits in said same data block are work data for said corresponding stage.

13. A system for providing a controlled passage of data, comprising:

a plurality of stages coupled to one another in a pipeline arrangement;

first means in each of said stages in said pipeline arrangement for storing data;

second means in each individual one of said stages in said pipeline arrangement for determining at each instant whether a successive stage in said pipeline arrangement is able at that instant to receive a transfer to said successive stage of the data stored in such individual stage at that instant;

third means in each individual one of said stages in said pipeline arrangement for determining at each instant whether such stage is able at that instant to pass data to said successive stage in said pipeline arrangement;

fourth means in each individual one of said stages in said pipeline arrangement for passing the data stored in such stage at each instant to said successive stage in said pipeline arrangement in accordance with the determination provided at that instant by said third means for such individual stage and for said second means for said successive stage in said pipeline arrangement;

fifth means for providing an individual address for each of said different stages in said pipeline arrangement, each of said addresses being formed by an individual sequence of binary bits with a different number of binary bits in said sequence than said number of binary bits in said sequence for other stages in said pipeline arrangement, said binary bits for each progressive number of binary bits in each sequence being different from said binary bits for such progressive number of binary bits in said sequences for the other stages in said pipeline arrangement;

means in each stage in said pipeline arrangement for responding to said individual address for such stage; and

means for passing each of said addresses in said pipeline arrangement sequentially through said successive stages in said pipeline arrangement to said stage responsive in said pipeline arrangement to such individual address;

the operation of said fourth means for each stage in said pipeline arrangement at each instant being independent of the operation of said fourth means for said other stages in said pipeline arrangement at that instant to provide for the passage of data at each instant of data from individual ones of said stages in said pipeline arrangement at that instant to said stages adjacent to such individual stages in said pipeline arrangement without the passage at such instant of data from other stages in said pipeline arrangement to said stages adjacent to such other stages in said pipeline arrangement.

14. A system as set forth in claim 13, and further including:

means for resetting at least alternate stages in said pipeline arrangement to provide for subsequent passage of information to each stage from said previous stage in said pipeline arrangement.

15. A system as set forth in claim 13, and further including:

fifth means for providing clock signals;

said first means in each stage in said pipeline arrangement including first latching means;

said second means in each stage in said pipeline arrangement including second latching means;

third means in each stage in said pipeline arrangement including third latching means; and

said first, second and third latching means being synchronized in their operation in accordance with said clock signals from said fifth means.

16. A system as set forth in claim 13, and further including:

fifth means for providing an individual address for each of said different stages in said pipeline arrangement, each of said addresses being formed by an individual sequence of binary bits with a different number of binary bits in said sequence than said number of binary bits in said sequence for other stages in said pipeline arrangement, said binary bits for each progressive number of binary bits in each sequence being different from said binary bits for such progressive number of binary bits in said sequences for the other stages in said pipeline arrangement;

means in each stage in said pipeline arrangement for responding to said individual address for such stage; and

means for passing each of said addresses in said pipeline arrangement sequentially through said successive stages in said pipeline arrangement to said stage responsive in said pipeline arrangement to such individual address.

17. In a data pipeline system for processing data, the system having a plurality of sequential pipeline stages, an input data storage device (LDIN) and an output data storage device (LDOUT) in each stage, with the output data storage device of each pipeline stage connected to the input data storage device of the next successive pipeline stage, the combination comprising:

electrical validation circuitry in at least one stage to generate a validation signal (IN_-- VALID, OUT_-- VALID) for a first state when data stored in said stage is valid and for a second state when data stored in said stage is invalid, said state defining said stage'"'"'s ability to accept data, said validation circuitry including at least one validation storage device (LVOUT) to store said validation signal for the corresponding pipeline stage;

an acceptance signal connecting an adjacent pair of pipeline stages and conveying an acceptance signal (IN_-- ACCEPT, OUT_-- ACCEPT) indicative of the ability of said successive pipeline stage to load data stored in the preceding pipeline stage; and

enabling circuitry connected to said data storage devices (LDOUT) for generating an enabling signal to enable loading of data and validation signals into the respective storage devices, wherein;

said data storage devices include a primary data storage device (LDOUT) and a secondary data storage device (LDIN);

said data is loaded into said respective primary data storage devices (LDOUT) and said validation signal is loaded into a respective primary validation storage device (LVOUT) at the same time;

data is loaded into said respective primary data storage device (LDOUT) when said acceptance signal assumes an enabling state; and

said acceptance signal assumes said enabling state only when the acceptance signal associated with the data storage device of said next successive pipeline stage is in said enabling state or said data in said data storage device of said next successive pipeline stage is invalid.

18. A data pipeline system as recited in claim 17, wherein:

said input data storage device (LDIN) of each stage forms a secondary data storage device and a secondary validation storage device (LVIN) is included in each stage; and

a primary acceptance storage device (LAOUT) is included in each stage to store the state of the acceptance signal (OUT_-- ACCEPT) of said next successive pipeline stage.