REGISTER  |  SIGN IN
United States Patent6038380
Wise , ; et al.March 14, 2000
Title
Data pipeline system and data encoding method
Abstract
A multi-standard video decompression apparatus has a plurality of stages interconnected by a two-wire interface arranged as a pipeline processing machine. Control tokens and DATA Tokens pass over the single two-wire interface for carrying both control and data in token format. A token decode circuit is positioned in certain of the stages for recognizing certain of the tokens as control tokens pertinent to that stage and for passing unrecognized control tokens along the pipeline. Reconfiguration processing circuits are positioned in selected stages and are responsive to a recognized control token for reconfiguring such stage to handle an identified DATA Token. A wide variety of unique supporting subsystem circuitry and processing techniques are disclosed for implementing the system.
Inventors:Wise; Adrian Philip (Bracknell, GB), Sotheran; Martin William  (Bristol, GB), Robbins; William Philip  (Bristol, GB)
Assignee:Discovision Associates (Irvine, CA)
Appl. No.:903969
Filed:July 31, 1997
Foreign Application Priority Data
Jun 30, 1992 [EP] 92306038
Mar 24, 1994 [GB] 9405914
Feb 28, 1995 [GB] 9504046
Current U.S. Class:712/200 382/246 
Current International Class:G06F 9/38 (20060101)
Field of Search:395/376 345/501 382/246
U.S. Patent Documents
3875391April 1975Shapiro et al.
3893042July 1975Whitman et al.
3962685June 1976Belle Isle
4107780August 1978Grimsdale et al.
4142205February 1979Iinuma
4149242April 1979Pirz
4196448April 1980Whitehouse et al.
4215369July 1980Iijima
4225920September 1980Stokes
4228497October 1980Gupta et al.
4302775November 1981Widergren et al.
4307447December 1981Provanzano et al.
4334246June 1982Saran
4433308February 1984Hirata
4437072March 1984Asami
4467409August 1984Potash et al.
4495629January 1985Zasio et al.
4540903September 1985Cooke et al.
4580066April 1986Berndt
4598372July 1986McRoberts
4617657October 1986Drynan et al.
4630198December 1986Yuan
4646151February 1987Welles, II et al.
4679163July 1987Arnould et al.
4710866December 1987Zolnowsky et al.
4747070May 1988Trottier et al.
4785349November 1988Keith et al.
4789927December 1988Hannah
4799677January 1989Frederiksen
4808159February 1989Sowa
4811214March 1989Nosenchuck et al.
4811413March 1989Kimmel
4814978March 1989Dennis
4823201April 1989Simon et al.
4829465May 1989Knauer et al.
4831440May 1989Borgers et al.
4841436June 1989Asano et al.
4855947August 1989Zymslowski et al.
4866510September 1989Goodfellow et al.
4866637September 1989Gonzalez-Lopez et al.
4885786December 1989Anderson et al.
4887224December 1989Okano et al.
4891784January 1990Kato et al.
4897803January 1990Calarco et al.
4903018February 1990Wiebach et al.
4912668March 1990Aubie et al.
4922341May 1990Strobach
4922418May 1990Dolecek
4924298May 1990Kitamura
4924308May 1990Feuchtwanger
4943916July 1990Asano et al.
4949280August 1990Littlefield
4953082August 1990Nomura et al.
4975595December 1990Roberts et al.
4985766January 1991Morrison et al.
4989138January 1991Radochonski
4991112February 1991Callemyn
5003204March 1991Cushing et al.
5014138May 1991Fischer et al.
5021947June 1991Campbell et al.
5027212June 1991Marlton et al.
5038209August 1991Hang
5043880August 1991Yoshida
5050166September 1991Cantoni et al.
5053985October 1991Friedlander et al.
5055841October 1991Cordell
5057793October 1991Cowley et al.
5057917October 1991Shalkauser et al.
5060242October 1991Arbeiter
5081450January 1992Lucas et al.
5086489February 1992Shimura
5091721February 1992Hamori
5107345April 1992Lee
5111292May 1992Kuriacose et al.
5113255May 1992Nagata et al.
5122873June 1992Golin
5122875June 1992Raychaudhuri et al.
5122948June 1992Zapolin
5124790June 1992Nakayama
5126842June 1992Andrews et al.
5129059July 1992Hannah
5130568July 1992Miller et al.
5134487July 1992Taguchi et al.
5134697July 1992Scheffler
5136371August 1992Savatier et al.
5142380August 1992Sakagami et al.
5146325September 1992Ng
5146326September 1992Hasegawa
5148271September 1992Kato et al.
5148524September 1992Harlin et al.
5151875September 1992Sato
5159449October 1992Allmendinger
5164819November 1992Music
5168356December 1992Acampora et al.
5168375December 1992Reisch et al.
5172011December 1992Leuthold et al.
5173695December 1992Sun et al.
5175617December 1992Wallace et al.
5179372January 1993West et al.
5182642January 1993Gersdorff et al.
5184124February 1993Molpus et al.
5184347February 1993Farwell et al.
5185819February 1993Ng et al.
5189526February 1993Sasson
5191548March 1993Balkanski et al.
5193002March 1993Guichard et al.
5201056April 1993Daniel et al.
5202847April 1993Bolton et al.
5203003April 1993Donner
5212549May 1993Ng et al.
5212742May 1993Normile et al.
5214507May 1993Aravind et al.
5214770May 1993Ramanujan et al.
5216724June 1993Suzuki et al.
5218436June 1993Sugiyama et al.
5223926June 1993Stone et al.
5226131July 1993Grafe et al.
5227863July 1993Bilbrey et al.
5227878July 1993Puri et al.
5228098July 1993Crinon et al.
5229863July 1993Kao et al.
5231484July 1993Gonzales et al.
5231486July 1993Acampora et al.
5233420August 1993Piri et al.
5233545August 1993Ho et al.
5233690August 1993Sherlock et al.
5237413August 1993Israelsen et al.
5241222August 1993Small et al.
5241383August 1993Chen et al.
5241635August 1993Papadopoulos et al.
5241658August 1993Masterson et al.
5247612September 1993Quinard
5249146September 1993Uramoto et al.
5253058October 1993Gharavi
5253078October 1993Balkanski et al.
5257213October 1993Kim et al.
5257223October 1993Dervisoglu
5257350October 1993Howard et al.
5258725November 1993Kinoshita
5260781November 1993Soloff et al.
5260782November 1993Hui
5261047November 1993Rivshin
5263136November 1993DeAguiar et al.
5267334November 1993Normille et al.
5276513January 1994van der Wal et al.
5276681January 1994Tobagi et al.
5276784January 1994Ohki
5278520January 1994Parker et al.
5278646January 1994Civanlar et al.
5278647January 1994Hingorani et al.
5283646February 1994Bruder
5287178February 1994Acampora et al.
5287193February 1994Lin
5287420February 1994Barrett
5289276February 1994Siracusa et al.
5289577February 1994Gonzales et al.
5293229March 1994Iu
5294894March 1994Gebara
5297263March 1994Ohtsuka et al.
5298896March 1994Lei et al.
5298992March 1994Pietras et al.
5299025March 1994Shirasawa
5300949April 1994Rodriguez et al.
5301019April 1994Citta
5301032April 1994Hong et al.
5301040April 1994Hoshi et al.
5301136April 1994McMillan, Jr. et al.
5301242April 1994Gonzales et al.
5301272April 1994Atkins
5301344April 1994Kolchinsky
5303342April 1994Edge
5304953April 1994Heim et al.
5305438April 1994MacKay et al.
5307449April 1994Kelley et al.
5309527May 1994Ohki
5309563May 1994Farrand et al.
5311309May 1994Ersoz et al.
5325092June 1994Allen et al.
5329313July 1994Keith
5329619July 1994Page et al.
5333212July 1994Ligtenberg
5333266July 1994Boaz et al.
5341371August 1994Simpson
5351047September 1994Behlen
5367636November 1994Colley et al.
5369405November 1994Choi et al.
5406279April 1995Anderson et al.
5412782May 1995Hausman et al.
5414813May 1995Shiobara
5421028May 1995Swanson
5442790August 1995Nosenchuck
5448310September 1995Kopet et al.
5450599September 1995Horvath et al.
5452006September 1995Auld
5457780October 1995Shaw et al.
5461679October 1995Normile et al.
5463699October 1995Wilkinson
5481689January 1996Stamm et al.
5487064January 1996Galand et al.
5490247February 1996Tung et al.
5495291February 1996Adams
5497498March 1996Taylor
5504869April 1996Uchida
5510857April 1996Kopet et al.
5517603May 1996Kelley et al.
5517670May 1996Allen et al.
5535290July 1996Allen et al.
5566089October 1996Hoogenboom
5574933November 1996Horst
5579052November 1996Artieri
5590283December 1996Hillis et al.
Foreign Patent Documents
0196911Oct., 1986EP
0255767Feb., 1988EP
0468480Jan., 1992EP
0572262Dec., 1993EP
0572263Dec., 1993EP
0576749Jan., 1994EP
0589734Mar., 1994EP
0618728Oct., 1994EP
0639032Feb., 1995EP
2045035Oct., 1980GB
2059724Apr., 1981GB
2171578Aug., 1986GB
2194085Feb., 1988GB
2268035Dec., 1993GB
2269070Jan., 1994GB
63-39040Jul., 1988JP
9425935Nov., 1994WO
Other References
Elliott J A et al: "Real-Time Simulation of Videophone Image Coding Algorithms on Reconfigurable Multicomputers," IEEE Proceedings E. Computers & Digital Techniques, vol. 139, No. 3 Part E., May 1, 1992, pp. 269-279, XP0000306411. .
Hong, Yang-Chang; T.H. Payne. A Hybrid Approach for Efficient Dataflow Computing, Computers and Communications, 1990 Int'l Phoenix Conference. IEEE Publications, May 1990 pp. 170-178. .
Kaoru, Uchida et al: "A Pipeline Dataflow Processor Architecture Based on a Variable Length Token Concept," Architecture, University Park, Aug. 15-19, 1988, vol. 1, Aug. 15,1988, Briggs F A, pp. 209-216, XP000079309. .
Kopet, Tom: "Programmable Architectures for Real-Time Video Compression," 4th International Conference on Signal Processing Applications & Technology, vol. 2, Sep. 28, 1993-Oct. 1, 1993, Santa Clara, California, USA, pp. 1031-1038. .
Mayer, A.C.: "The Architecture of a Single-Chip Processor Array for Videocompression," Proceedings of the International Conference on Consumer Electronics, Rosemont, Jun. 8-10, 1993, No. Conf. 12, Aug. 6, 1993, Institute of Electrical and Electronics Engineers, pp. 294-95, XP0000427624. .
Normile, James. Dan Wright, Image Compression Using Coarse Grain Parallel Processing, ICASSP 1991: Acoustics, Speech & Signal Processing Conference, IEEE Publications. Jul. 1991 pp. 1121-1124. .
Tokumichi Murakami et al: "A DSP Architectural Design for Low Bit-Rate Motion Video Codec," IEEE Transactions on Circuits and Systems, vol. 36, No. 10, Oct. 1, 1989, pp. 1267-1274, XP000085313. .
Yang, Kun-Min. VLSI Architecture Design of a Versatile Variable Length Decoding Chip for Real-Time Video CODECS, Tencon 1990 IEEE Region 10 Conference on Computer and Communication . . . , IEEE Publications Feb. 1990, pp. 551-554. .
Information Technology. Generic Coding of Moving Pictures and Associated Audio Information BS ISO/IEC 13818-2:1996 pp 1-202. .
MacInnis, Alexander G. "The MPEG Systems Coding Specification." Signal Processing: Image Communication 4 (1992) pp. 153-159. .
McCarthy, Charles L. "A Low-Cost Audio/Video Decoder Solution for MPEG System Streams." IEEE Jun. 21, 1994, pp. 312-313. .
Chong, "A Data Flow Architecture for Digital Image Processing," Wescon Tech. Papers No. 4/6, Oct. 30, 1984, Anaheim, California, USA, pp. 1-10. .
P. Yip, et al., "DIT and DIF Algorithm for Discrete Sine and Cosine Transforms" Proceedings of the International Symposium on Circuits and Systems, IEEE Press, New York, US, vol. 2/3, Jun. 5 1985, Kyoto, JP, pp. 941-944. .
Hsieh S. Hou, "A Fast Recursive Algorithm for Computing the Discrete Cosine Transform," IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 35, No. 10, Oct. 1987, IEEE Press, New York, US pp. 1455-1461. .
Komori et al., An Elastic Pipeline Mechanism By Self-Timed Circuits, IEEE Journal of Solid-State Circuits, vol. 23, No. 1, Feb. 1988, New York, NY, USA, pp. 111-117. .
A. Gupta et al., "A Fast Recursive Algorithm for the Discrete Sine Transform," IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 38, No. 3, Mar. 1990, IEEE Press, New York, US, pp. 553-557. .
H.R. Wu, et al., "A Two Dimensional Fast Cosine Transform Algorithm Based on Hou's Approach," IEEE Transaction on Acoustics, Speech, and Signal Processing, vol. 39, No. 2, Feb. 1991, IEEE Press, New York, US, pp. 544-546..~
Primary Examiner: Bowler; Alyssa H.
Assistant Examiner: Davis, Jr.; Walter D.
Attorney, Agent or Firm:Braun; Robert T. Bickel; Arthur S.
Parent Case Text


CROSS REFERENCE TO RELATED APPLICATIONS

This application is a continuation, of application Ser. No. 08/486,396, filed Jun. 7, 1995, now abandoned, which is a division of U.S. Ser. No. 08/400,397 filed on Mar. 7, 1995, which is a continuation-in-part of U.S. Ser. No. 08/382,958 filed on Feb. 2, 1995 (now abandoned), which is a continuation of U.S. Ser. No. 08/082,291 filed on Jun. 24, 1993 (now abandoned).
Claims

We claim:
1. In a pipeline machine, comprising a plurality of processing stages, the improvement characterized by:
two successive ones of said processing stages being connected by a two-wire link, wherein said two-wire link comprises: a sender, a receiver, and a clock connected to said sender and said receiver, wherein data is transferred from said sender to said receiver upon a transition of said clock only when said sender is ready and said receiver is ready;
wherein variable length tokens having data and control functions propagate across said two-wire link, said tokens each comprising a plurality of data words, each said word including an extension bit which indicates a presence or an absence of additional words in said token, a length of said token being determined by said extension bits; whereby said tokens are unlimited in length;
said processing stages comprising a spatial decoder accepting an encoded data stream having a plurality of video formats carried therein, said formats including at least an MPEG format:
a DRAM interface in said spatial decoder having a plurality of data buffers therein, and a RAM accepting data from said DRAM interface;
a coded data buffer;
a token generator, generating variable length tokens, a said variable length token comprising a PICTURE.sub.-- END token and a FLUSH token;
means responsive to said PICTURE.sub.-- END token for performing a stop-after-picture operation for achieving a clear end to picture data decoding, for indicating the end of a picture, and for clearing the pipeline; wherein responsive to said PICTURE.sub.-- END token, data is cleared from said data buffers of said DRAM interface, and data in said coded data buffer is presented to a Huffman decoder of said spatial decoder, and responsive to said FLUSH token a portion of said processing stages are reconfigured to await arrival of further data.

2. The machine according to claim 1, wherein at least one of said processing stages has a variable length DATA token stored therein, and responsive to said PICTURE.sub.-- END token, said one processing stage adds bits to a last word of said DATA token until said DATA token is padded to a predetermined size.

3. The machine according to claim 2, wherein responsive to said FLUSH token registers of said processing stages are reset to stand-by condition, and a STOP.sub.-- AFTER.sub.-- PICTURE state is established, wherein input to said processing stages is not accepted.

4. The machine according to claim 2, wherein a padded DATA token is written to said coded data buffer.

5. The machine according to claim 1, wherein said data buffers of said DRAM interface comprise a swing buffer.

6. The machine according to claim 5, further comprising:
a buffer manager for allocating buffers of said swing buffer;
a zero.sub.-- buffer register in said DRAM interface;
wherein responsive to a condition of said zero.sub.-- buffer register, an output of said buffer manager is ignored, whereby said data buffers of said DRAM are by-passed by data passing through said DRAM interface.

7. The machine according to claim 1, wherein responsive to a picture end point in said data stream, a last word of a variable length DATA token is padded by said token generator and written to said coded data buffer.
Description
The following U.S. patent applications have subject matter related to this Application: application Ser. Nos. 08/382,958, filed Feb. 2, 1995; 08/400,397, filed Mar. 7, 1995; 08/399,851 filed Mar. 7, 1995;
08/482,296, filed Jun. 7, 1995; 08/484,730, filed Jun. 7, 1995 (now U.S. Pat. No. 5,677,648); 08/479,279, filed Jun. 7, 1995; 08/483,020, filed Jun. 7, 1995; 08/487,224, filed Jun. 7, 1995; 08/400,722, filed Mar. 7, 1995 (now U.S. Pat. No.
5,596,517); 08/400,723, filed Mar. 7, 1995 (now U.S. Pat. No. 5,594,678); 08/404,067, filed Mar. 14, 1995 (now U.S. Pat. No. 5,590,067); 08/567,555, filed Dec. 5, 1995 (now U.S. Pat. No. 5,617,458); 08/396,834, filed Mar. 1, 1995; 08/473,813, filed Jun. 7, 1995; 08/484,456, filed Jun. 7, 1995; 08/476,814, filed Jun. 7, 1995; 08/481,561, filed Jun. 7, 1995; 08/482,381, filed Jun. 7, 1995; 08/479,910, filed Jun. 7, 1995; 08/475,729, filed Jun. 7, 1995; 08/484,578, filed Jun. 7, 1995;
08/473,615, filed Jun. 7, 1995; 08/487,356, filed Jun. 7, 1995; 08/487,134, filed Jun. 7, 1995; 08/481,772, filed Jun. 7, 1995; 08/481,785, filed Jun. 7, 1995 (now U.S. Pat. No. 5,703,793); 08/486,908, filed Jun. 7, 1995; 08/486,034, filed Jun.
7, 1995; 08/487,740, filed Jun. 7, 1995; 08/488,348, filed Jun. 7, 1995; 08/484,170, filed Jun. 7, 1995; 08/516,038, filed Aug. 17, 1995; 08/399,810, filed Mar. 7, 1995 (now U.S. Pat. No. 5,625,571); 08/400,201, filed Mar. 7, 1995 (now U.S. Pat. No. 5,603,012); 08/400,215, filed Mar. 7, 1995; 08/400,072, filed Mar. 7, 1995; 08/402,602, filed Mar. 7, 1995; 08/400,206, filed Mar. 7, 1995; 08/400,151, filed Mar. 7, 1995; 08/400,202, filed Mar. 7, 1995; 08/400,398, filed Mar. 7, 1995;
08/400,161, filed Mar. 7, 1995; 08/400,141, filed Mar. 7, 1995; 08/400,211, filed Mar. 7, 1995; 08/400,331, filed Mar. 7, 1995; 08/400,207, filed Mar. 7, 1995; 08/399,898, filed Mar. 7, 1995; 08/399,665, filed Mar. 7, 1995; 08/400,058, filed Mar.
7, 1995; 08/399,800, filed Mar. 7, 1995; 08/399,801, filed Mar. 7, 1995; 08/399,799, filed Mar. 7, 1995; 08/474,222, filed Jun. 7, 1995; 08/486,481, filed Jun. 7, 1995; 08/474,231, filed Jun. 7, 1995; 08/474,830, filed Jun. 7, 1995; 08/474,220, filed Jun. 7, 1995 (now U.S. Pat. No. 5,699,544); 08/473,868, filed Jun. 7, 1995; 08/474,603, filed Jun. 7, 1995; 08/485,242, filed Jun. 7, 1995 (now U.S. Pat. No. 5,689,313); 08/477,048, filed Jun. 7, 1995; and 08/485,744, filed Jun. 7, 1995.

INTRODUCTION

The present invention is directed to improvements in methods and apparatus for decompression which operates to decompress and/or decode a plurality of differently encoded input signals. The illustrative embodiment chosen for description hereinafter relates to the decoding of a plurality of encoded picture standards. More specifically, this embodiment relates to the decoding of any one of the well known standards known as JPEG, MPEG and H.261.

A serial pipeline processing system of the present invention comprises a single two-wire bus used for carrying unique and specialized interactive interfacing tokens, in the form of control tokens and data tokens, to a plurality of adaptive decompression circuits and the like positioned as a reconfigurable pipeline processor.

PRIOR ART

One prior art system is described in U.S. Pat. No. 5,216,724. The apparatus comprises a plurality of compute modules, in a preferred embodiment, for a total of four compute modules coupled in parallel. Each of the compute modules has a processor, dual port memory, scratch-pad memory, and an arbitration mechanism. A first bus couples the compute modules and a host processor. The device comprises a shared memory which is coupled to the host processor and to the compute modules with a second bus.

U.S. Pat. No. 4,785,349 discloses a full motion color digital video signal that is compressed, formatted for transmission, recorded on compact disc media and decoded at conventional video frame rates. During compression, regions of a frame are individually analyzed to select optimum fill coding methods specific to each region. Region decoding time estimates are made to optimize compression thresholds. Region descriptive codes conveying the size and locations of the regions are grouped together in a first segment of a data stream. Region fill codes conveying pixel amplitude indications for the regions are grouped together according to fill code type and placed in other segments of the data stream. The data stream segments are individually variable length coded according to their respective statistical distributions and formatted to form data frames. The number of bytes per frame is withered by the addition of auxiliary data determined by a reverse frame sequence analysis to provide an average number selected to minimize pauses of the compact disc during playback, thereby avoiding unpredictable seek mode latency periods characteristic of compact discs. A decoder includes a variable length decoder responsive to statistical information in the code stream for separately variable length decoding individual segments of the data stream. Region location data is derived from region descriptive data and applied with region fill codes to a plurality of region specific decoders selected by detection of the fill code type (e.g., relative, absolute, dyad and DPCM) and decoded region pixels are stored in a bit map for subsequent display.

U.S. Pat. No. 4,922,341 discloses a method for scene-model-assisted reduction of image data for digital television signals, whereby a picture signal supplied at time is to be coded, whereby a predecessor frame from a scene already coded at time t-1 is present in an image store as a reference, and whereby the frame-to-frame information is daptively acquired quad-tree division structure. Upon nitialization of the system, a uniform, prescribed gray cale value or picture half-tone expressed as a defined luminance value is written into the image store of a coder at the transmitter and in the image store of a decoder at the receiver store, in the same way for all picture elements (pixels). Both the image store in the coder as well as the image store in the decoder are each operated with feed back to themselves in a manner such that the content of the image store in the coder and decoder can be read out in blocks of variable size, can be amplified with a factor greater than or less than 1 of the luminance and can be written back into the image store with shifted addresses, whereby the blocks of variable size are organized according to a known quad tree data structure.

U.S. Pat. No. 5,122,875 discloses an apparatus for encoding/decoding an HDTV signal. The apparatus includes a compression circuit responsive to high definition video source signals for providing hierarchically layered codewords CW representing compressed video data and associated codewords T, defining the types of data represented by the codewords CW. A priority selection circuit, responsive to the codewords CW and T, parses the codewords CW into high and low priority codeword sequences where in the high and low priority codeword sequences correspond to compressed video data of relatively greater and lesser importance to image reproduction respectively. A transport processor, responsive to the high and low priority codeword sequences, forms high and low priority transport blocks of high and low priority codewords, respectively. Each transport block includes a header, codewords CW and error detection check bits. The respective transport blocks are applied to a forward error check circuit for applying additional error check data. Thereafter, the high and low priority data are applied to a modem wherein quadrature amplitude modulates respective carriers for transmission.

U.S. Pat. No. 5,146,325 discloses a video decompression system for decompressing compressed image data wherein odd and even fields of the video signal are independently compressed in sequences of intraframe and interframe compression modes and then interleaved for transmission. The odd and even fields are independently decompressed. During intervals when valid decompressed odd/even field data is not available, even/odd field data is substituted for the unavailable odd/even field data. Independently decompressing the even and odd fields of data and substituting the opposite field of data for unavailable data may be used to advantage to reduce image display latency during system start-up and channel changes.

U.S. Pat. No. 5,168,356 discloses a video signal encoding system that includes apparatus for segmenting encoded video data into transport blocks for signal transmission. The transport block format enhances signal recovery at the receiver by virtue of providing header data from which a receiver can determine re-entry points into the data stream on the occurrence of a loss or corruption of transmitted data. The re-entry points are maximized by providing secondary transport headers embedded within encoded video data in respective transport blocks.

U.S. Pat. No. 5,168,375 discloses a method for processing a field of image data samples to provide for one or more of the functions of decimation, interpolation, and sharpening. This is accomplished by an array transform processor such as that employed in a JPEG compression system. Blocks of data samples are transformed by the discrete even cosine transform (DECT) in both the decimation and interpolation processes, after which the number of frequency terms is altered. In the case of decimation, the number of frequency terms is reduced, this being followed by inverse transformation to produce a reduced-size matrix of sample points representing the original block of data. In the case of interpolation, additional frequency components of zero value are inserted into the array of frequency components after which inverse transformation produces an enlarged data sampling set without an increase in spectral bandwidth. In the case of sharpening, accomplished by a convolution or filtering operation involving multiplication of transforms of data and filter kernel in the frequency domain, there is provided an inverse transformation resulting in a set of blocks of processed data samples. The blocks are overlapped followed by a savings of designated samples, and a discarding of excess samples from regions of overlap. The spatial representation of the kernel is modified by reduction of the number of components, for a linear-phase filter, and zero-padded to equal the number of samples of a data block, this being followed by forming the discrete odd cosine transform (DOCT) of the padded kernel matrix.

U.S. Pat. No. 5,175,617 discloses a system and method for transmitting logmap video images through telephone line band-limited analog channels. The pixel organization in the logmap image is designed to match the sensor geometry of the human eye with a greater concentration of pixels at the center. The transmitter divides the frequency band into channels, and assigns one or two pixels to each channel, for example a 3 KHz voice quality telephone line is divided into 768 channels spaced about
3.9 Hz apart. Each channel consists of two carrier waves in quadrature, so each channel can carry two pixels. Some channels are reserved for special calibration signals enabling the receiver to detect both the phase and magnitude of the received signal. If the sensor and pixels are connected directly to a bank of oscillators and the receiver can continuously receive each channel, then the receiver need not be synchronized with the transmitter. An FFT algorithm implements a fast discrete approximation to the continuous case in which the receiver synchronizes to the first frame and then acquires subsequent frames every frame period. The frame period is relatively low compared with the sampling period so the receiver is unlikely to lose frame synchrony once the first frame is detected. An experimental video telephone transmitted 4 frames per second, applied quadrature coding to 1440 pixel logmap images and obtained an effective data transfer rate in excess of 40,000 bits per second.

U.S. Pat. No. 5,185,819 discloses a video compression system having odd and even fields of video signal that are independently compressed in sequences of intraframe and interframe compression modes. The odd and even fields of independently compressed data are interleaved for transmission such that the intraframe even field compressed data occurs midway between successive fields of intraframe odd field compressed data. The interleaved sequence provides receivers with twice the number of entry points into the signal for decoding without increasing the amount of data transmitted.

U.S. Pat. No. 5,212,742 discloses an apparatus and method for processing video data for compression/decompression in real-time. The apparatus comprises a plurality of compute modules, in a preferred embodiment, for a total of four compute modules coupled in parallel. Each of the compute modules has a processor, dual port memory, scratch-pad memory, and an arbitration mechanism. A first bus couples the compute modules and host processor. Lastly, the device comprises a shared memory which is coupled to the host processor and to the compute modules with a second bus. The method handles assigning portions of the image for each of the processors to operate upon.

U.S. Pat. No. 5,231,484 discloses a system and method for implementing an encoder suitable for use with the proposed ISO/IEC MPEG standards. Included are three cooperating components or subsystems that operate to variously adaptively pre-process the incoming digital motion video sequences, allocate bits to the pictures in a sequence, and adaptively quantize transform coefficients in different regions of a picture in a video sequence so as to provide optimal visual quality given the number of bits allocated to that picture.

U.S. Pat. No. 5,267,334 discloses a method of removing frame redundancy in a computer system for a sequence of moving images. The method comprises detecting a first scene change in the sequence of moving images and generating a first keyframe containing complete scene information for a first image. The first keyframe is known, in a preferred embodiment, as a "forward-facing" keyframe or intraframe, and it is normally present in CCITT compressed video data. The process then comprises generating at least one intermediate compressed frame, the at least one intermediate compressed frame containing difference information from the first image for at least one image following the first image in time in the sequence of moving images. This at least one frame being known as an interframe. Finally, detecting a second scene change in the sequence of moving images and generating a second keyframe containing complete scene information for an image displayed at the time just prior to the second scene change, known as a "backward-facing" keyframe. The first keyframe and the at least one intermediate compressed frame are linked for forward play, and the second keyframe and the intermediate compressed frames are linked in reverse for reverse play. The intraframe may also be used for generation of complete scene information when the images are played in the forward direction. When this sequence is played in reverse, the backward-facing keyframe is used for the generation of complete scene information.

U.S. Pat. No. 5,276,513 discloses a first circuit apparatus, comprising a given number of prior-art image-pyramid stages, together with a second circuit apparatus, comprising the same given number of novel motion-vector stages, perform cost-effective hierarchical motion analysis (HMA) in real-time, with minimum system processing delay and/or employing minimum system processing delay and/or employing minimum hardware structure. Specifically, the first and second circuit apparatus, in response to relatively high-resolution image data from an ongoing input series of successive given pixel-density image-data frames that occur at a relatively high frame rate (e.g., 30 frames per second), derives, after a certain processing-system delay, an ongoing output series of successive given pixel-density vector-data frames that occur at the same given frame rate. Each vector-data frame is indicative of image motion occurring between each pair of successive image frames.

U.S. Pat. No. 5,283,646 discloses a method and apparatus for enabling a real-time video encoding system to accurately deliver the desired number of bits per frame, while coding the image only once, updates the quantization step size used to quantize coefficients which describe, for example, an image to be transmitted over a communications channel. The data is divided into sectors, each sector including a plurality of blocks. The blocks are encoded, for example, using DCT coding, to generate a sequence of coefficients for each block. The coefficients can be quantized, and depending upon the quantization step, the number of bits required to describe the data will vary significantly. At the end of the transmission of each sector of data, the accumulated actual number of bits expended is compared with the accumulated desired number of bits expended, for a selected number of sectors associated with the particular group of data. The system then readjusts the quantization step size to target a final desired number of data bits for a plurality of sectors, for example describing an image. Various methods are described for updating the quantization step size and determining desired bit allocations.

The article, Chong, Yong M., A Data-Flow Architecture for Digital Image Processing, Wescon Technical Papers: No. 2 October/November 1984, discloses a real-time signal processing system specifically designed for image processing. More particularly, a token based data-flow architecture is disclosed wherein the tokens are of a fixed one word width having a fixed width address field. The system contains a plurality of identical flow processors connected in a ring fashion. The tokens contain a data field, a control field and a tag. The tag field of the token is further broken down into a processor address field and an identifier field. The processor address field is used to direct the tokens to the correct data-flow processor, and the identifier field is used to label the data such that the data-flow processor knows what to do with the data. In this way, the identifier field acts as an instruction for the data-flow processor. The system directs each token to a specific data-flow processor using a module number (MN). If the MN matches the MN of the particular stage, then the appropriate operations are performed upon the data. If unrecognized, the token is directed to an output data bus.

The article, Kimori, S. et al. An Elastic Pipeline Mechanism by Self-Timed Circuits, IEEE J. of Solid-State Circuits, Vol. 23, No. 1, February 1988, discloses an elastic pipeline having self-timed circuits. The asynchronous pipeline comprises a plurality of pipeline stages. Each of the pipeline stages consists of a group of input data latches followed by a combinatorial logic circuit that carries out logic operations specific to the pipeline stages. The data latches are simultaneously supplied with a triggering signal generated by a data-transfer control circuit associated with that stage. The data-transfer control circuits are interconnected to form a chain through which send and acknowledge signal lines control a hand-shake mode of data transfer between the successive pipeline stages. Furthermore, a decoder is generally provided in each stage to select operations to be done on the operands in the present stage. It is also possible to locate the decoder in the preceding stage in order to pre-decode complex decoding processing and to alleviate critical path problems in the logic circuit. The elastic nature of the pipeline eliminates any centralized control since all the interworkings between the submodules are determined by a completely localized decision and, in addition, each submodule can autonomously perform data buffering and self-timed data-transfer control at the same time. Finally, to increase the elasticity of the pipeline, empty stages are interleaved between the occupied stages in order to ensure reliable data transfer between the stages.

U.S. Pat. No. 5,278,646 discloses an improved technique for decoding wherein the number of coefficients to be included in each sub-block is selectable, and a code indicating the number of coefficients within each layer is inserted in the bitstream at the beginning of each encoded video sequence. This technique allows the original runs of zero coefficients in the highest resolution layer to remain intact by forming a sub-block for each scale from a selected number of coefficients along a continuous scan. These sub-blocks may be decoded in a standard fashion, with an inverse discrete cosine transform applied to square sub-blocks obtained by the appropriate zero padding of and/or discarding of excess coefficients from each of the scales. This technique further improves decoding efficiency by allowing an implicit end of block signal to separate blocks, making it unnecessary to decode an explicit end of block signal in most cases.

U.S. Pat. No. 4,903,018 discloses a process and data processing system for compressing and expanding structurally associated multiple data sequences. The process is particular to data sets in which an analysis is made of the structure in order to identify a characteristic common to a predetermined number of successive data elements of a data sequence. In place of data elements, a code is used which is again decoded during expansion. The common characteristic is obtained by analyzing data elements which have the same order number in a number of data sequences. During expansion, the data elements obtained by decoding the code are ordered in data series on the basis of the order number of these data series on the basis of the order number of these data elements. The data processing system for performing the processes includes a storage matrix (26) and an index storage (28) having line addresses of the storage matrix (26) in an assorted line sequence.

U.S. Pat. No. 4,334,246 discloses a circuit and method for decompressing video subsequent to its prior compression for transmission or storage. The circuit assumes that the original video generated by a raster input scanner was operated on by a two line one shot predictor, coded using run length encoding into code words of four, eight or twelve bits and packed into sixteen bit data words. This described decompressor, then, unpacks the data by joining together the sixteen bit data words and then separately the individual code words, converts the code words into a number of all zero four bit nibbles and a terminating nibble containing one or more one bits which constitutes decoded data, inspects the actual video of the preceding scan line and the previous video bits of the present line to produce depredictor bits and compares the decoded data and depredictor bits to produce the final actual video.

U.S. Pat. No. 5,060,242 discloses an image signal processing system DPCM encodes the signal, then Huffman and run length encodes the signal to produce variable length code words, which are then tightly packed without gaps for efficient transmission without loss of any data. The tightly packed apparatus has a barrel shifter with its shift modulus controlled by an accumulator receiving code word length information. An OR gate is connected to the shifter, while a register is connected to the gate. Apparatus for processing a tightly packed and decorrelated digital signal has a barrel shifter and accumulator for unpacking, a Huffman and run length decoder, and an inverse DCPM decoder.

U.S. Pat. No. 5,168,375 discloses a method for processing a field of image data samples to provide for one or more of the functions of decimation, interpolation, and sharpening is accomplished by use of an array transform processor such as that employed in a JPEG compression system. Blocks of data samples are transformed by the discrete even cosine transform (DECT) in both the decimation and interpolation processes, after which the number of frequency terms is altered. In the case of decimation, the number of frequency terms is reduced, this being followed by inverse transformation to produce a reduced-size matrix of sample points representing the original block of data. In the case of interpolation, additional frequency components of zero value are inserted into the array of frequency components after which inverse transformation produces an enlarged data sampling set without an increase in spectral bandwidth. In the case of sharpening, accomplished by a convolution or filtering operation involving multiplication of transforms of data and filter kernel in the frequency domain, there is provided an inverse transformation resulting in a set of blocks of processed data samples. The blocks are overlapped followed by a savings of designated samples, and a discarding of excess samples from regions of overlap. The spatial representation of the kernel is modified by reduction of the number of components, for a linear-phase filter, and zero-padded to equal the number of samples of a data block, this being followed by forming the discrete odd cosine transform (DOCT) of the padded kernel matrix.

U.S. Pat. No. 5,231,486 discloses a high definition video system processes a bitstream including high and low priority variable length coded Data words. The coded Data is separated into packed High Priority Data and packed Low Priority Data by means of respective data packing units. The coded Data is continuously applied to both packing units. High Priority and Low Priority Length words indicating the bit lengths of high priority and low priority components of the coded Data are applied to the high and low priority data packers, respectively. The Low Priority Length word is zeroed when high Priority Data is to be packed for transport via a first output path, and the High Priority Length word is zeroed when Low Priority Data is to be packed for transport via a second output path.

U.S. Pat. No. 5,287,178 discloses a video signal encoding system includes a signal processor for segmenting encoded video data into transport blocks having a header section and a packed data section. The system also includes reset control apparatus for releasing resets of system components, after a global system reset, in a prescribed non-simultaneous phased sequence to enable signal processing to commence in the prescribed sequence. The phased reset release sequence begins when valid data is sensed as transmitting the data lines.

U.S. Pat. No. 5,124,790 to Nakayama discloses a reverse quantizer to be used with image memory. The inverse quantizer is used in the standard way to decode differential predictive coding method (DPCM) encoded data.

U.S. Pat. No. 5,136,371 to Savatier et al. is directed to a de-quantizer having an adjustable quantizational level which is variable and determined by the fullness of the buffer. The applicants state that the novel aspect of their invention is the maximum available data rate that is achieved. Buffer overflow and underflow is avoided by adapting the quantization step size the quantizer 152 and the de-quantizer 156 by means of a quantizational level which is recalculated after each block has been encoded. The quantization level is calculated as a function of the amount of already encoded data for the frame, compared with the total buffer size. In this manner, the quantization level can advantageously be recalculated by the decoder and does not have to be transmitted.

U.S. Pat. No. 5,142,380 to Sakagami et al. discloses an image compression apparatus suitable for use with still images such as those formed by electronic still cameras using solid state image sensors. The quantizer employed is connected to a memory means from which threshold values of a quantization matrix for the laminate signal, Y, and rom 15 stores threshold values of a quantization matrix for the crominant signals I and Q.

U.S. Pat. No. 5,193,002 to Guichard et al. disclosed an apparatus for coding/decoding image signals in real time in conjunction with the CCITT standard H.261. A digital signal processor carries out direct quantization and reverse quantization.

U.S. Pat. No. 5,241,383 to Chen et al. describes an apparatus with a pseudo-constant bit rate video coding achieved by an adjustable quantization parameter. The qunatization parameter utilized by the quantizer 32 is periodically adjusted to increase or decrease the amount of code bits generated by the coding circuit. The change in quantization parameters for coding the next group of pictures is determined by a deviation measure between the actual number of code bits generated by the coding circuits for the previous group of pictures in an estimate number of code bits for the previous group of pictures. The number of code bits generated by the coding circuit is controlled by controlling the quantizer step sizes. In general smaller quantizer step sizes result in more code bits in larger quantizer step sizes result in fewer code bits.

U.S. Pat. Nos. 5,113,255 to Nagata et al; 5,126,842 to Andrews et al; 5,253,058 to Gharavi; 5,260,782 to Hui; and 5,212,742 to Normile et al are included for background and as a general description of the art.

The present invention relates to an improved pipeline system having an input, an output and a plurality of processing stages between the input and the output, the plurality of processing stages being interconnected by a two-wire interface for conveyance of tokens along the pipeline, and control and/or DATA tokens in the form of universal adaptation units for interfacing with all of the processing stages in the pipeline and interacting with selected stages in the pipeline for control data and/or combined control-data functions among the processing stages, so that the processing stages in the pipeline are afforded enhanced flexibility in configuration and processing. In accordance with the invention, the processing stages may be configurable in response to recognition of at least one token. One of the processing stages may be a Start Code Detector which receives the input and generates and/or converts the tokens.

The present invention also relates to an improved pipeline system having a spatial decoder system for video data including a Huffman decoder, an index to data and an arithmetic logic unit, and a microcode ROM having separate stored programs for each of a plurality of different picture compression/decompression standards, such programs being selectable by a token, whereby processing for a plurality of different picture standards is facilitated. The present invention may also include tokens in the form of a PICTURE.sub.-- START code token for indicating that the start of a picture will follow in the subsequent DATA token, a PICTURE.sub.-- END token for indicating the end of an individual picture, a FLUSH token for clearing buffers and resetting the system, and a CODING.sub.-- STANDARD token for conditioning the system for processing in a selected one of a plurality of picture compression/decompression standards. The present invention also relates to an improved pipeline system for decoding video data and having a Huffman decoder, an index to data (ITOD) stage, an arithmetic logic unit (ALU), and a data buffering means immediately following the system, whereby time spread for video pictures of varying data size can be controlled. Also in accordance with the invention, a processing stage receives the input data stream, the stage including means for recognizing specified bit stream patterns, whereby the processing stage facilitates random access and error recovery. The invention may also include a means for performing a stop-after-picture operation for achieving a clear end to picture data decoding, for indicating the end of a picture, and for clearing the pipeline.

The improved pipeline system may also include a fixed size, fixed width buffer, and means for padding the buffer to pass an arbitrary number of bits through the buffer. The present invention also relates to a data stream including run length code, and an inverse modeller means active upon the data stream from a token for expanding out the run level code to a run of zero data followed by a level, whereby each token is expressed with a specified number of values. The invention also includes an inverse modeller stage, an inverse discrete cosine transform stage, and a processing stage, positioned between the inverse modeller stage and the inverse discrete cosine transform stage, responsive to a token table for processing data.

In addition, the present invention relates to an improved pipeline system having a Huffman decoder for decoding data words encoded according to the Huffman coding provisions of either H.261, JPEG or MPEG standards, the data words including an identifier that identifies the Huffman code standard under which the data words were coded, means for receiving the Huffman coded data words, means for reading the identifier to determine which standard governed the Huffman coding of the received data words, if necessary, in response to reading the identifier that identifies the Huffman coded data words as H.261 or MPEG Huffman coded, means operably connected to the Huffman coded data words receiving means for generating an index number associated with each JPEG Huffman coded data word received from the Huffman coded data words receiving means, means for operating a lookup table containing a Huffman code table having the format used under the JPEG standard to transmit JPEG Huffman table information, including an input for receiving an index number from the index number generating means, and including an output that is a decoded data word corresponding to the index number.

Examples and further explanation of the present invention will now be described with reference to the drawings.

DESCRIPTION OF THE DRAWINGS

FIG. 1 illustrates six cycles of a six-stage pipeline for different combinations of two internal control signals;

FIGS. 2a and 2b illustrate a pipeline in which each stage includes auxiliary data storage. They also show the manner in which pipeline stages can "compress" and "expand" in response to delays in the pipeline;

FIGS. 3a(1), 3a(2), 3b(1) and 3b(2) illustrate the control of data transfer between stages of a preferred embodiment of a pipeline using a two-wire interface and a multi-phase clock;

FIG. 4 is a block diagram that illustrates a basic embodiment of a pipeline stage that incorporates a two-wire transfer control and also shows two consecutive pipeline processing stages with the two-wire transfer control;

FIGS. 5a and 5b taken together depict one example of a timing diagram that shows the relationship between timing signals, input and output data, and internal control signals used in the pipeline stage as shown in FIG. 4;

FIG. 6 is a block diagram of one example of a pipeline stage that holds its state under the control of an extension bit;

FIG. 7 is a block diagram of a pipeline stage that decodes stage activation data words;

FIGS. 8a and 8b taken together form a block diagram showing the use of the two-wire transfer control in an exemplifying "data duplication" pipeline stage;

FIGS. 9a and 9b taken together depict one example of a timing diagram that shows the two-phase clock, the two-wire transfer control signals and the other internal data and control signals used in the exemplifying embodiment shown in FIGS. 8a and
8b.

FIG. 10 is a block diagram of a reconfigurable processing stage;

FIG. 11 is a block diagram of a spatial decoder;

FIG. 12 is a block diagram of a temporal decoder;

FIG. 13 is a block diagram of a video formatter;

FIGS. 14a-c show various arrangements of memory blocks used in the present invention:

FIG. 14a is a memory map showing a first arrangement of macroblocks;

FIG. 14b is a memory map showing a second arrangement of macroblocks;

FIG. 14c is a memory map showing a further arrangement of macroblocks;

FIG. 15 shows a Venn diagram of possible table selection values;

FIG. 16 shows the variable length of picture data used in the present invention;

FIG. 17 is a block diagram of the temporal decoder including the prediction filters;

FIG. 18 is a pictorial representation of the prediction filtering process;

FIG. 19 shows a generalized representation of the macroblock structure;

FIG. 20 shows a generalized block diagram of a Start Code Detector;

FIG. 21 illustrates examples of start codes in a data stream;

FIG. 22 is a block diagram depicting the relationship between the flag generator, decode index, header generator, extra word generator and output latches;

FIG. 23 is a block diagram of the Spatial Decoder DRAM interface;

FIG. 24 is a block diagram of a write swing buffer;

FIG. 25 is a pictorial diagram illustrating prediction data offset from the block being processed;

FIG. 26 is a pictorial diagram illustrating prediction data offset by (1,1);

FIG. 27 is a block diagram illustrating the Huffman decoder and parser state machine of the Spatial Decoder.

FIG. 28 is a block diagram illustrating the prediction filter.

______________________________________ FIGS. ______________________________________ FIG. 29 shows a typical decoder system; FIG. 30 shows a JPEG still picture decoder; FIG. 31 shows a JPEG video decoder; FIG. 32 shows a multi-standard video decoder; FIG. 33 shows the start and the end of a token; FIG. 34 shows a token address and data fields; FIG. 35 shows a token on an interface wider than 8 bits; FIG. 36 shows a macroblock structure; FIG. 37 shows a two-wire interface protocol; FIG. 38 shows the location of external two-wire interfaces; FIG. 39 shows clock propagation; FIG. 40 shows two-wire interface timing; FIG. 41 shows examples of access structure; FIG. 42 shows a read transfer cycle; FIG. 43 shows an access start timing; FIG. 44 shows an example access with two write transfers; FIG. 45 shows a read transfer cycle; FIG. 46 shows a write transfer cycle; FIG. 47 shows a refresh cycle; FIG. 48 shows a 32 bit data bus and a 256 kbit deep DRAMs (9 bit row address); FIG. 49 shows timing parameters for any strobe signal; FIG. 50 shows timing parameters between any two strobe signals; FIG. 51 shows timing parameters between a bus and a strobe; FIG. 52 shows timing parameters between a bus and a strobe; FIG. 53 shows an MPI read timing; FIG. 54 shows an MPI write timing; FIG. 55 shows organization of large integers in the memory map; FIG. 56 shows a typical decoder clock regime; FIG. 57 shows input clock requirements; FIG. 58 shows the Spatial Decoder; FIG. 59 shows the inputs and outputs of the input circuit; FIG. 60 shows the coded port protocol; FIG. 61 shows the start code detector; FIG. 62 shows start codes detected and converted to Tokens; FIG. 63 shows the start codes detector passing Tokens; FIG. 64 shows overlapping MPEG start codes (byte aligned); FIG. 65 shows overlapping MPEG start codes (not byte aligned); FIG. 66 shows jumping between two video sequences; FIG. 67 shows a sequence of extra Token insertion; FIG. 68 shows decoder start-up control; FIG. 69 shows enabled streams queued before the output; FIG. 70 shows a spatial decoder buffer; FIG. 71 shows a buffer pointer; FIG. 72 shows a video demux; FIG. 73 shows a construction of a picture; FIG. 74 shows a construction of a 4:2:2 macroblock; FIG. 75 shows a calculating macroblock dimension from pel ones; FIG. 76 shows spatial decoding; FIG. 77 shows an overview of H.261 inverse quantization; FIG. 78 shows an overview of JPEG inverse quantization; FIG. 79 shows an overview of MPEG inverse quantization; FIG. 80 shows a quantization table memory map; FIG. 81 shows an overview of JPEG baseline sequential structure; FIG. 82 shows a tokenised JPEG picture; FIG. 83
shows a temporal decoder; FIG. 84 shows a picture buffer specification; FIG. 85 shows an MPEG picture sequence (m=3); FIG. 86 shows how "I" pictures are stored and output; FIG. 87 shows how "P" pictures are formed, stored and output; FIG. 88 shows how "B" pictures are formed and output; FIG. 89 shows P picture formation; FIG. 90 shows H.261 prediction formation; FIG. 91 shows an H.261 "sequence"; FIG. 92 shows a hierarchy of H.261 syntax; FIG. 93 shows an H.261 picture layer; FIG. 94 shows an H.261 arrangement of groups of blocks; FIG. 95 shows an H.261 "slice" layer; FIG. 96 shows an H.261 arrangement of macroblocks; FIG. 97 shows an H.261 sequence of blocks; FIG. 98 shows an H.261 macroblock layer; FIG. 99 shows an H.261
arrangement of pels in blocks; FIG. 100 shows a hierarchy of MPEG syntax; FIG. 101 shows an MPEG sequence layer; FIG. 102 shows an MPEG group of pictures layer; FIG. 103 shows an MPEG picture layer; FIG. 104 shows an MPEG "slice" layer; FIG. 105
shows an MPEG sequence of blocks; FIG. 106 shows an MPEG macroblock layer; FIG. 107 shows an "open GOP"; FIG. 108 shows examples of access structure; FIG. 109 shows access start timing; FIG. 110 shows a fast page read cycle; FIG. 111 shows a fast page write cycle; FIG. 112 shows a refresh cycle; FIG. 113 shows extracting row and column address from a chip address; FIG. 114 shows timing parameters for any strobe signal; FIG. 115 shows timing parameters between any two strobe signals; FIG.
116 shows timing parameters between a bus and a strobe; FIG. 117 shows timing parameters between a bus and a strobe; FIG. 118 shows a Huffman decoder and parser; FIG. 119 shows an H.261 and an MPEG AC Coefficient Decoding Flow Chart; FIG. 120
shows a block diagram for JPEG (AC and DC) coefficient decoding; FIG. 121 shows a flow diagram for JPEG (AC and DC) coefficient decoding; FIG. 122 shows an interface to the Huffman Token Formatter; FIG. 123 shows a token formatter block diagram; FIG. 124 shows an H.261 and an MPEG AC Coefficient Decoding; FIG. 125 shows the interface to the Huffman ALU; FIG. 126 shows the basic structure of the Huffman ALU; FIG. 127 shows the buffer manager; FIG. 128 shows an imodel and hsppk block diagram; FIG. 129 shows an imex state diagram; FIG. 130 illustrates the buffer start-up; FIG. 131 shows a DRAM interface; FIG. 132 shows a write swing buffer; FIG. 133 shows an arithmetic block; FIG. 134 shows an iq block diagram; FIG. 135 shows an iqca state machine; FIG. 136 shows an IDCT 1-D Transform Algorithm; FIG. 137 shows an IDCT 1-D Transform Architecture; FIG. 138 shows a token stream block diagram; FIG. 139 shows a standard block structure; FIG. 140 is a block diagram showing; microprocessor test access; FIG. 141 shows 1-D Transform Micro-Architecture; FIG. 142 shows a temporal decoder block diagram; FIG. 143 shows the structure of a Two-wire interface stage; FIG. 144 shows the address generator block diagram; FIG. 145
shows the block and pixel offsets; FIG. 146 shows multiple prediction filters; FIG. 147 shows a single prediction filter; FIG. 148 shows the 1-D prediction filter; FIG. 149 shows a block of pixels; FIG. 150 shows the structure of the read rudder; FIG. 151 shows the block and pixel offsets; FIG. 152 shows a prediction example; FIG. 153 shows the read cycle; FIG. 154 shows the write cycle; FIG. 155 shows the top-level registers block diagram with timing references; FIG. 156 shows the control for incrementing presentation numbers; FIG. 157 shows the buffer manager state machine (complete); FIG. 158 shows the state machine main loop; FIG. 159 shows the buffer 0 containing an SIF (22 by 18 macroblocks) picture; FIG. 160 shows the SIF component 0 with a display window; FIG. 161 shows an example picture format showing storage block address; FIG. 162 shows a buffer 0 containing a SIF (22 by 18 macroblocks) picture; FIG. 163 shows an exaiuple address calculation; FIG. 164 shows a write address generation state machine; FIG. 165 shows a slice of the datapath; FIG. 166 shows a two cycle operation of the datapath; FIG. 167 shows mode 1 filtering; FIG. 168 shows a horizontal up-sampler datapath; and FIG. 169 shows the structure of the color-space converter. ______________________________________

SUMMARY OF THE INVENTION

Briefly, and in general terms, the present invention provides an input, an output and a plurality of processing stages between the input and the output, the plurality of processing stages being interconnected by a two-wire interface for conveyance of tokens along a pipeline, and control and/or DATA tokens in the form of universal adaptation units for interfacing with all of the stages in the pipeline and interacting with selected stages in the pipeline for control, data and/or combined control-data functions among the processing stages, whereby the processing stages in the pipeline are afforded enhanced flexibility in configuration and processing.

Each of the processing stages in the pipeline may include both primary and secondary storage, and the stages in the pipeline are reconfigurable in response to recognition of selected tokens. The tokens in the pipeline are dynamically adaptive and may be position dependent upon the processing stages for performance of functions or position independent of the processing stages for performance of functions.

In a pipeline machine, in accordance with the invention, the tokens may be altered by interfacing with the stages, and the tokens may interact with all of the processing stages in the pipeline or only with some but less than all of said processing stages. The tokens in the pipeline may interact with adjacent processing stages or with non-adjacent processing stages, and the tokens may reconfigure the processing stages. Such tokens may be position dependent for some functions and position independent for other functions in the pipeline.

The tokens, in combination with the reconfigurable processing stages, provide a basic building block for the pipeline system. The interaction of the tokens with a processing stage in the pipeline may be conditioned by the previous processing history of that processing stage. The tokens may have address fields which characterize the tokens, and the interactions with a processing stage may be determined by such address fields.

In an improved pipeline machine, in accordance with the invention, the tokens may include an extension bit for each token, the extension bit indicating the presence of additional words in that token and identifying the last word in that token. The address fields may be of variable length and may also be Huffman coded.

In the improved pipeline machine, the tokens may be generated by a processing stage. Such pipeline tokens may include data for transfer to the processing stages or the tokens may be devoid of data. Some of the tokens may be identified as DATA tokens and provide data to the processing stages in the pipeline, while other tokens are identified as control tokens and only condition the processing stages in the pipeline, such conditioning including reconfiguring of the processing stages. Still other tokens may provide both data and conditioning to the processing stages in the pipeline. Some of said tokens may identify coding standards to the processing stages in the pipeline, whereas other tokens may operate independent of any coding standard among the processing stages. The tokens may be capable of successive alteration by the processing stages in the pipeline.

In accordance with the invention, the interactive flexibility of the tokens in cooperation with the processing stages facilitates greater functional diversity of the processing stages for resident structure in the pipeline, and the flexibility of the tokens facilitates system expansion and/or alteration. The tokens may be capable of facilitating a plurality of functions within any processing stage in the pipeline. Such pipeline tokens may be either hardware based or software based. Hence, the tokens facilitate more efficient uses of system bandwidth in the pipeline. The tokens may provide data and control simultaneously to the processing stages in the pipeline.

The invention may include a pipeline processing machine for handling plurality of separately encoded bit streams arranged as a single serial bit stream of digital bits and having separately encoded pairs of control codes and corresponding data carried in the serial bit stream and employing a plurality of stages interconnected by a two-wire interface, further characterized by a start code detector responsive to the single serial bit stream for generating control tokens and DATA tokens for application to the two-wire interface, a token decode circuit positioned in certain of the stages for recognizing certain of the tokens as control tokens pertinent to that stage and for passing unrecognized control tokens along the pipeline, and a reconfigurable decode and parser processing means responsive to a recognized control token for reconfiguring a particular stage to handle an identified DATA token.

The pipeline machine may also include first and second registers, the first register being positioned as an input of the decode and parser means, with the second register positioned as an output of the decode and parser means. One of the processing stages may be a spatial decoder, a second of the stages being a token generator for generating control tokens and DATA tokens for passage along the two-wire interface. A token decode means is positioned in the spatial decoder for recognizing certain of the tokens as control tokens pertinent to the spatial decoder and for configuring the spatial decoder for spatially decoding DATA tokens following a control token into a first decoded format.

A further stage may be a temporal decoder positioned downstream in the pipeline from the spatial decoder, with a second token decode means positioned in the temporal decoder for recognizing certain of the tokens as control tokens pertinent to the temporal decoder and for configuring the temporal decoder for termporally decoding the DATA tokens following the control token into a first decoded format. The temporal decoder may utilize a reconfigurable prediction filter which is reconfigurable by a prediction token.

Data may be moved along the two-wire interface within the temporal decoder in 8.times.8 pel data blocks, and address means may be provided for storing and retrieving such data blocks along block boundaries. The address means may store and retrieve blocks of data across block boundaries. The address means reorders said blocks as picture data for display. The data blocks stored and retrieved may be greater and/or smaller than 8.times.8 pel data blocks. Circuit means may also be provided for either displaying the output of the temporal decoder or writing the output back into a picture memory location. The decoded format may be either a still picture format or a moving picture format.

The processing stage may also include, in accordance with the invention, a token decoder for decoding the address of a token and an action identifier responsive to the token decoder to implement configuration of the processing stage. The processing stages reside in a pipeline processing machine having a plurality of the processing stages interconnected by a two-wire interface bus, with control tokens and DATA tokens passing over the two-wire interface. A token decode circuit is positioned in certain of the processing stages for recognizing certain of the tokens as control tokens pertinent to that stage and for passing unrecognized control tokens along the pipeline. A first input latch circuit may be positioned on the two-wire interface preceding the processing stage and a second output latch circuit may be positioned on the two-wire interface succeeding the processing stage. The token decode circuit is connected to the two-wire interface through the first input latch. Predetermined processing stages may include a decoding circuit connected to the output of a predetermined data storage device, whereby each processing stage assumes the active state only when the stage contains a predetermined stage activation signal pattern and remains in the activation mode until the stage contains a predetermined stage deactivation pattern.

In accordance with the invention, one of the stages is a Start Code Detector for receiving the input and being adapted to generate and/or convert the tokens. The Start Code Detector is responsive to data to create tokens, searches for and detects start codes and produces tokens in response thereto, and is capable of detecting overlapping start codes, whereby the first start code is ignored and the second start code is used to create start code tokens.

The Start Code Detector stage is adapted to search an input data stream in a search mode for a selected start code. The detector searches for breaks in the data stream, and the search may be made of data from an external data source. The Start Code Detector stage may produce a START CODE token, a PICTURE.sub.-- START token, a SLICE.sub.-- START token, a PICTURE.sub.-- END token, a SEQUENCE.sub.-- START token, a SEQUENCE.sub.-- END token, and/or a GROUP.sub.-- START token. The Start Code Detector stage may also perform a padding function by adding bits to the last word of a token.

The Start Code Detector may provide, in a machine for handling a plurality of separately encoded bit streams arranged as a serial bit stream of digital bits and having separately encoded pairs of start codes and data carried in the serial bit stream, a Start Code Detector subsystem having first, second and third registers connected in serial fashion, each of the registers storing a different number of bits from the bit stream, the first register storing a value, the second register and a first decode means identifying a start code associated with the value contained in said first register. Circuit means shift the latter value to a predetermined end of the third register, and a second decode means is arranged for accepting data from the third register in parallel.

A memory may also be provided which is responsive to the second decode means for providing one or more control tokens stored in the memory as a result of the decoding of the value associated with the start code. A plurality of tag shift registers may be provided for handling tags indicating the validity of data from the registers. The system may also include means for accessing the input data stream from a microprocessor interface, and means for formatting and organizing the data stream.

In accordance with the invention, the Start Code Detector may identify start codes of varying widths associated with differently encoded bit streams. The detector may generate a plurality of DATA Tokens from the input data stream. Further in accordance with the invention, the system may be a pipeline system and the Start Code Detector may be positioned as the first processing stage in the pipeline.

The present invention also provides, in a digital picture information processing system, means for selectively configuring the system to process data in accordance with a plurality of different picture compression/decompression standards. The picture standards may include JPEG, MPEG, and/or H.261, or any other standards and any combination of such picture standards, without departing in any way from the spirit and scope of the invention. In accordance with the invention, the system may include a spatial decoder for video data and having a Huffman decoder, an index to data and an arithmetic logic unit with a microcode ROM having separate stored programs for each of a plurality of different picture compression/decompression standards, such programs being selectable by an interfacing adaptation unit in the form of a token, so that processing for a plurality of picture standards is facilitated. A multi-standard system in accordance with the invention, may utilize tokens for its operation regardless of the selected picture standard, and the tokens may be utilized as a generic communication protocol in the system for all of the various picture standards. The system may be further characterized by a multi-standard token for mapping differently encoded data streams arranged on a single serial stream of data onto a single decoder using a mixture of standard dependent and standard independent hardware and control tokens. The system may also include an address generation means for arranging macroblocks of data associated with different picture standards into a common addressing scheme.

The present invention also provides, in a system having a plurality of processing stages, a universal adaptation unit in the form of an interactive interfacing token for control and/or data functions among the processing stages, the token being a PICTURE.sub.-- START code token for indicating that the start of a picture will follow in the subsequent DATA token.

The token may also be a PICTURE.sub.-- END token for indicating the end of an individual picture.

The token may also be a FLUSH token for clearing buffers and resetting the system as it proceeds down the system from the input to the output. In accordance with the invention, the FLUSH token may variably reset the stages as the token proceeds down the pipeline.

The token may also be a CODING.sub.-- STANDARD token for conditioning the system for processing in a selected one of a plurality of picture compression/decompression standards.

The CODING.sub.-- STANDARD token may designate the picture standard as JPEG, and/or any other appropriate picture standard. At least some of the processing stages reconfigure in response to the CODING.sub.-- STANDARD token.

One of the processing stages in the system may be a Huffman decoder and parser and, upon receipt of a CODING.sub.-- STANDARD control token, the parser is reset to an address location corresponding to the location of a program for handling the picture standard identified by the CODING.sub.-- STANDARD control token. A reset address may also be selected by the CODING.sub.-- STANDARD control token corresponding to a memory location used for testing the Huffman decoder and parser.

The Huffman decoder may include a decoding stage and an Index to Data stage, and the parser stage may send an instruction to the Index to Data Unit to select tables needed for a particular identified coding standard, the parser stage indicating whether the arriving data is inverted or not.

The aforedescribed tokens may take the form of an interactive metamorphic interfacing token.

The present invention also provides a system for decoding video data, having a Huffman decoder, an index to data (ITOD) stage, an arithmetic logic unit (ALU), and a data buffering means immediately following the system, whereby time spread for video pictures of varying data size can be controlled.

The system may include a spatial decoder having a two-wire interface intercon-necting processing stages, the interface enabling serial processing for data and parallel processing for control.

As previously indicated, the system may further include a ROM having separate stored programs for each of a plurality of picture standards, the programs being selectable by a token to facilitate processing for a plurality of different picture standards.

The spatial decoder system also includes a token formatter for formatting tokens, so that DATA tokens are created.

The system may also include a decoding stage and a parser stage for sending an instruction to the Index to Data Unit to select tables needed for a particular identified coding standard, the parser stage indicating whether the arriving data is inverted or not. The tables may be arranged within a memory for enabling multiple use of the tables where appropriate.

The present invention also provides a pipeline system having an input data stream, and a processing stage for receiving the input data stream, the stage including means for recognizing specified bit stream patterns, whereby said stage facilitates random access and error recovery. In accordance with the invention, the processing stage may be a start code detector and the bit stream patterns may include start codes. Hence, the invention provides a search-mode means for searching differently encoded data streams arranged as a single serial stream of data for allowing random access and enhanced error recovery.

The present invention also provides a pipeline machine having means for performing a stop-after-picture operation for achieving a clear end to picture data decoding, for indicating the end of a picture, and for clearing the pipeline, wherein such means generates a combination of a PICTURE.sub.-- END token and a FLUSH token.

The present invention also provides, in a pipeline machine, a fixed size, fixed width buffer and means for padding the buffer to pass an arbitrary number of bits through the buffer. The padding means may be a start code detector.

Padding may be performed only on the last word of a token and padding insures uniformity of word size. In accordance with the invention, a reconfigurable processing stage may be provided as a spatial decoder and the padding means adds to picture data being handled by the spatial decoder sufficent additional bits such that each decompressed picture at the output of the spatial decoder is of the same length in bits.

The present invention also provides, in a system having a data stream including run length code, an inverse modeller means active upon the data stream from a token for expending out the run level code to a run of zero data followed by a level, whereby each token is expressed with a specified number of values. The token may be a DATA token.

The inverse modeller means blocks tokens which lack the specified number of values, and the specified number of values may be 64 coefficients in a presently preferred embodiment of the invention.

The practice of the invention may include an expanding circuit for accepting a DATA token having run length codes and decoding the run length codes. A padder circuit in communication with the expanding circuit checks that the DATA token has a predetermined length so that if the DATA token has less than the predetermined length, the padder circuit adds units of data to the DATA token until the predetermined length is achieved. A bypass circuit is also provided for bypassing any token other than a DATA token around the expanding circuit and the padding circuit.

In accordance with the invention, a method is provided for data to efficiently fill a buffer, including providing first type tokens having a first predetermined width, and at least one of the following formats:

Format A--ExxxxxxLLLLLLLLLLL

Format B--ERRRRRRLLLLLLLLLLL

Format C--E000000LLLLLLLLLLL

where E=extention bit; F=specifics format; R=run bit; L=length bit or non-data token; x="don't care" bit, splitting format A tokens into a format 0a token having a form of ELLLLLLLLLLL, splitting format B tokens into a format 1 token having the form of FRRRRRR00000 and a format 0a data token, splitting format C tokens into a format 0 token having the form of FLLLLLLLLLLL, and packing format 0, format 0a and format 1 tokens into a buffer, having a second predetermined width.

The invention also provides an apparatus for providing a time delay to a group of compressed pictures, the pictures corresponding to a video compression/decompression standard, wherein words of data containing compressed pictures are counted by a counter circuit and a microprocessor, in communication with the counter circuit and adapted to receive start-up information consistent with the standard of video decompression, communicates the start-up information to the counter circuit.

An inverse modeller circuit, for accepting the words of data and capable of delaying the words of data, is in communication with a control circuit intermediate the counter circuit and the inverse modeller circuit, the control circuit also communicating with the counter circuit which compares the start-up information with the counted words of data and signals the control circuit. The control circuit queues the signals in correspondence to the words of data that have met the start-up criterion and controls the inverse modeller delay feature.

The present invention also provides in a pipeline system having an inverse modeller stage and an inverse discrete cosine transform stage, the improvement characterized by a processing stage, positioned between the inverse modeller stage and the inverse discrete cosine transform stage, responsive to a token table for processing data.

In accordance with the invention, the token may be a QUANT.sub.-- TABLE token for causing the processing stage to generate a quantization table.

The present invention also provides a Huffman decoder for decoding data words encoded according to the Huffman coding provisions of either H.261, JPEG or MPEG standards, the data words including an identifier that identifies the Huffman code standard under which the data words were coded, and comprising means for receiving the Huffman coded data words, means for reading the identifier to determine which standard governed the Huffman coding of the received data words, means for converting the data words to JPEG Huffman coded data words, if necessary, in response to reading the identifier that identifies the Huffman coded data words as H.261 or MPEG Huffman coded, means operably connected to the Huffman coded data words receiving means for generating an index number associated with each JPEG Huffman coded data word received from the Huffman coded data words receiving means, and means for operating a lookup table containing a Huffman code table having the format used under the JPEG standard to transmit JPEG Huffman table information, including an input for receiving an index number from the index number generating means, and including an output that is a decoded data word corresponding to the index number.

The invention further relates, in varying degrees of scope, to a method for decoding data words encoded according to the Huffman coding provisions of either H.261, JPEG or MPEG standards, the data words including an identifier that identifies the Huffman code standard under which the data words were coded, such steps comprising receiving the Huffman coded data words, including reading the identifier to determine which standard governed the Huffman coding of the received data words, if necessary, in response to reading the identifier that identifies the Huffman coded data words as H.261 or MPEG Huffman coded, generating an index number associated with each JPEG Huffman coded data word received, operating a lookup table containing a Huffman code table having the format used under the JPEG standard to transmit JPEG Huffman table information, including receiving an index number, and generating a decoded data word corresponding to the received index number.

The above and other objectives and advantages of the invention will become apparent from the following more detailed description.

In the ensuing description of the practice of the invention, the following terms are frequently used and are generally defined by the following glossary:

GLOSSARY

BLOCK: An 8-row by 8-column matrix of pels, or 64 DCT coefficients (source, quantized or dequantized).

CHROMINANCE (COMPONENT): A matrix, block or single pel representing one of the two color difference signals related to the primary colors in the nanner defined in the bit stream. The symbols used for the color difference signals are Cr and Cb.

CODED REPRESENTATION: A data element as represented in its encoded form.

CODED VIDEO BIT STREAM: A coded representation of a series of one or more pictures as defined in this specification.

CODED ORDER: The order in which the pictures are transmitted and decoded. This order is not necessarily the same as the display order.

COMPONENT: A matrix, block or single pel from one of the three matrices (luminance and two chrominance) that make up a picture.

COMPRESSION: Reduction in the number of bits used to represent an item of data.

DECODER: An embodiment of a decoding process.

DECODING (PROCESS): The process defined in this specification that reads an input coded bitstream and produces decoded pictures or audio samples.

DISPLAY ORDER: The order in which the decoded pictures are displayed. Typically, this is the same order in which they were presented at the input of the encoder.

ENCODING (PROCESS): A process, not specified in this specification, that reads a stream of input pictures or audio samples and produces a valid coded bitstream as defined in this specification.

INTRA CODING: Coding of a macroblock or picture that uses information only from that macroblock or picture.

LUMINANCE (COMPONENT): A matrix, block or single pel representing a monochrome representation of the signal and related to the primary colors in the manner defined in the bit stream. The symbol used for luminance is Y.

MACROBLOCK: The four 8 by 8 blocks of luminance data and the two (for 4:2:0 chroma format) four (for 4:2:2 chroma format) or eight (for 4:4:4 chroma format) corresponding 8 by 8 blocks of chrominance data coming from a 16 by 16 section of the luminance component of the picture. Macroblock is sometimes used to refer to the pel data and sometimes to the coded representation of the pel values and other data elements defined in the macroblock header of the syntax defined in this part of this specification. To one of ordinary skill in the art, the usage is clear from the context.

MOTION COMPENSATION: The use of motion vectors to improve the efficiency of the prediction of pel values. The prediction uses motion vectors to provide offsets into the past and/or future reference pictures containing previously decoded pel values that are used to form the prediction error signal.

MOTION VECTOR: A two-dimensional vector used for motion compensation that provides an offset from the coordinate position in the current picture to the coordinates in a reference picture.

NON-INTRA CODING: Coding of a macroblock or picture that uses information both from itself and from macroblocks and pictures occurring at other times.

PEL: Picture element.

PICTURE: Source, coded or reconstructed image data. A source or reconstructed picture consists of three rectangular matrices of 8-bit numbers representing the luminance and two chrominance signals. For progressive video, a picture is identical to a frame, while for interlaced video, a picture can refer to a frame, or the top field or the bottom field of the frame depending on the context.

PREDICTION: The use of a predictor to provide an estimate of the pel value or data element currently being decoded.

RECONFIGURABLE PROCESS STAGE (RPS): A stage, which in response to a recognized token, reconfigures itself to perform various operations.

SLICE: A series of macroblocks.

TOKEN: A universal adaptation unit in the form of an interactive interfacing messenger package for control and/or data functions.

START CODES [SYSTEM AND VIDEO]: 32-bit codes embedded in a coded