Variable length code detection in a signal processing system

• US 5,821,886 A
• Filed: 10/18/1996
• Issued: 10/13/1998
• Est. Priority Date: 10/18/1996
• Status: Expired due to Term

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Son, Jae Cheol
• Primary Examiner(s): Gaffin, Jeffrey A.
• Assistant Examiner(s): JEAN PIERRE, PEGUY
• Application Number:
  US08/731,339
• Time in Patent Office: 725 Days
• Field of Search: 341/67, 341/65, 341/63, 341/106, 341/60, 341/51, 348/390, 348/423
• US Class Current: 341/67
• CPC Class Codes: H03M 7/425 for the decoding process only
• 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 group of incoming data stream bits having packed variable length code ("VLC") words is applied to an entropy code bit length searching module. The group of bits is replicated within a plurality of matching modules selectively distributed among entropy code bit length searching logic units. Each unit of entropy code bit length searching logic supports a VLC word table as characterized by, for example, standard compression formats such as MPEG-1, MPEG-2, H.261, and H.263. The matching modules are divided into groups within the entropy code bit length searching logic units. A group of matching modules is allocated to each VLC bit length represented in the associated VLC word supported table. A number of matching modules are allocated to each bit length equal to a minimum number of patterns unique to VLC words of a particular bit length. The matching modules compare an incoming data group to respective patterns. A detected match is indicated by an appropriately set group output signal. Each entropy code bit length searching logic unit includes a bit length encoder that receives the group output signals. The set group output signal indicates the bit length of a current VLC, and the bit length encoder encodes this information into a bit length code output signal. The bit length code signal is utilized by a shifter to parse a corresponding bit length of current data. The parsed current data may be directly applied to an address generator which generates an output signal for a decoding look up table.

Claims

1. An apparatus to detect a current entropy code word in a group of bits, and the current entropy code word having a bit length, wherein a predetermined number of possible bit lengths of the current entropy code word is t+1, the apparatus comprising:

a plurality of matching modules, wherein the matching modules each receive the group of bits and each attempts to determine the bit length of the current entropy code word in the group of bits, and one of the matching modules determines the bit length of the current entropy code word in the group of bits and provides a unique output signal with respect to output signals of the remaining matching modules; and

t+1 matching module groups wherein each of the t+1 matching module groups includes a predetermined number of matching modules, and each of the t+1 matching module groups represents one of the t+1predetermined number of possible bit lengths of the current entropy code word, wherein each of the t+1 matching module groups has an output signal, and the one of the t+1 matching module groups having the matching module having the unique output signal has a unique output signal, with respect to output signals of the remaining t+1matching module groups, that indicates the bit length of the current entropy code word.

2. The apparatus of claim 1 wherein each matching module comprises:

an n bit buffer having the group of bits;

an (n-1)-x pattern bit buffer having a bit pattern, wherein the bit pattern matches the most significant n-x bits of at least one possible entropy code word of one possible bit length; and

a comparator coupled to the n bit buffer and the (n-1)-x pattern bit buffer to compare the most significant n-x bits of the n bit buffer to the n-x bits of the (n-1)-x pattern bit buffer, wherein if a match occurs the matching module provides the unique output signal.

3. The apparatus of claim 2 wherein the bit pattern has a number of bits corresponding to a minimum number of bits uniquely associated with at least one possible entropy code word of one possible bit length.

4. The apparatus of claim 2 wherein the bit patterns are programmable.

5. The apparatus of claim 1 wherein the number of matching modules in each of the t+1 matching module groups equals the minimum number of bit patterns necessary to uniquely identify each of the predetermined entropy code words for the bit length represented by a respective t+1 matching module group.

6. The apparatus of claim 1 further comprising:

an encoder coupled to the output signals of the t+1 matching module groups, wherein the encoder detects the one of the t+1 matching module groups having a unique output signal and provides a unique code representing the bit length of the current entropy code word.

7. The apparatus of claim 1 wherein the t+1 matching module groups are allocated among N+1 entropy code bit length searching modules, wherein each entropy code bit length searching module represents a predetermined table of entropy code words.

8. The apparatus of claim 1 wherein the predetermined number of possible bit lengths of the current entropy code word is characterized by a standard format from a group consisting of MPEG-1, MPEG-2, H.261, or H.263.

9. The apparatus of claim 1 further comprising:

a multimedia signal processor that includes the plurality of matching modules and t+1 matching module groups.

10. The apparatus of claim 1 wherein t equals eight.

11. The apparatus of claim 1 further comprising:

a multiplexer having an input terminal to receive the unique output signal from the matching module which determines the bit length of the current entropy code word;

a shifter coupled to an output terminal of the multiplexer;

an address generator coupled to the shifter;

a look up table, coupled to the address generator, to decode the entropy code word; and

a control state machine coupled to a select terminal of the multiplexer to select the unique output signal, wherein the shifter is capable of shifting the current entropy code word to the address generator, and the address generator is capable of generating an address of the entropy code word in the look up table.

12. A method of detecting a current entropy code word in a group of bits, and the current entropy code word having a bit length, wherein a predetermined number of possible bit lengths of the current entropy code word is t+1, the method comprising the steps of:

receiving the group of bits in t+1 matching module groups, wherein each of the t+1 matching module groups includes a predetermined number of matching modules, each matching module includes a predetermined bit pattern, and each of the t+1 matching module groups represents one of the t+1 predetermined number of possible bit lengths of the current entropy code word;

comparing the respective bit pattern of each matching module to a respective segment of the group of bits, wherein each bit pattern is associated with only one of the possible t+1 bit lengths of the current entropy code;

determining which bit pattern matches the respective segment of the group of bits; and

providing an output signal, responsive to the bit pattern determined to match the respective segment of the group of bits, that identifies the bit length of the current entropy code word.

13. The method of claim 12 further comprising the step of:

storing the group of bits in a memory; and

parsing the current entropy code word from the stored group of bits in accordance with the output signal that identifies the bit length of the current entropy code word.

14. The method of claim 13 further comprising the step of:

utilizing the parsed current entropy code word to decode the entropy code word.

15. The method of claim 14 wherein the step of utilizing comprises the steps of:

generating an address with the an address generator from the parsed entropy code word for a look up table (LUT); and

decoding the entropy code word with information in the LUT using the generated address.

16. The method of claim 13 further comprising the step of:

providing the output signal to an accumulator to keep track of previously parsed bits in the memory.

17. The method of claim 12 further comprising the step of:

receiving the group of bits in N respective entropy code searching logic modules, wherein each of the N entropy code searching logic modules includes the t+1 respective matching module groups, wherein N represents a number of format tables supported by a multimedia signal processor, and t for each respective matching module group of each entropy code searching logic module is determined by the format table represented by the respective entropy code searching logic module.

18. The method of claim 12 further comprising:

programming the bit patterns for each matching module.

19. A method comprising the steps of:

transmitting a group of bits to a plurality of matching modules in t+1 matching module groups, wherein the group of bits includes a current entropy code word, the current entropy code word has a bit length, and each of the t+1 matching module groups represents one of the t+1 predetermined number of possible bit lengths of the current entropy code word;

determining the bit length of the current entropy code word in the group of bits with one of the matching modules; and

providing a unique output signal with respect to output signals of the remaining matching modules from the matching module which determined the bit length of the current entropy code word in the group of bits that indicates the bit length of the current entropy code word.

20. The method of claim 19 further comprising the steps of:

providing the entropy code word from the group of bits to an address generator;

providing an address from the address generator in response to the provided entropy code word; and

decoding the entropy code word in response to the provided address.

21. The method of claim 20 further comprising the step of:

providing the decoded entropy code word to a digital signal processor.

22. The method of claim 20 wherein the step of providing the entropy code word comprises the step of:

shifting a number of bits from a register equal to the bit length of the current entropy code word.

23. The method of claim 19 wherein the step of transmitting a group of bits to a plurality of matching modules comprises the step of:

transmitting n bits to an n bit buffer of each matching module; and

wherein the step of determining the bit length of the current entropy code word comprises the step of;

comparing the most significant n-x bits in the n bit buffer of each matching module to respective (n-1)-x pattern bits of each matching module;

providing the unique output signal if a match occurs in the comparing step.

24. The method of claim 23 further comprising the step of:

minimizing the number of bit patterns necessary to accurately determine the bit length of the current entropy code word in the group of bits with one of the matching modules.

25. The method of claim 19 wherein the predetermined number of possible bit lengths of the current entropy code word is characterized by a standard format from a group consisting of MPEG-1, MPEG-2, H.261, or H.263.

26. A multimedia multiprocessor system further comprising:

a host processor;

a bus coupled to the host processor;

system memory coupled to the host processor; and

a multimedia signal processor to detect a current entropy code word in a group of bits, and the current entropy code word having a bit length, wherein a predetermined number of possible bit lengths of the current entropy code word is t+1, the multimedia signal processor comprising a bitstream processor, wherein the bitstream processor further comprises;

a plurality of matching modules, wherein the matching modules each receive the group of bits and each attempts to determine the bit length of the current entropy code word in the group of bits, and one of the matching modules determines the bit length of the current entropy code word in the group of bits and provides a unique output signal with respect to output signals of the remaining matching modules; and

t+1 matching module groups wherein each of the t+1 matching module groups includes a predetermined number of matching modules, and each of the t+1 matching module groups represents one of the t+1 predetermined number of possible bit lengths of the current entropy code word, wherein each of the t+1 matching module groups has an output signal, and the one of the t+1 matching module groups having the matching module having the unique output signal has a unique output signal, with respect to output signals of the remaining t+1 matching module groups, that indicates the bit length of the current entropy code word.