Variable length codeword packer

• US 5,446,916 A
• Filed: 03/26/1993
• Issued: 08/29/1995
• Est. Priority Date: 03/26/1993
• Status: Expired due to Fees

• Current Assignee: General Instrument Corporation (CommScope Holding Company, Inc.)
• Original Assignee: The GI Company Incorporated
• Inventors: Derovanessian, Henry, Liu, Vincent
• Primary Examiner(s): Bowler, Alyssa H.
• Assistant Examiner(s): Davis, Jr., Walter D.
• Application Number:
  US08/031,011
• Time in Patent Office: 886 Days
• Field of Search: 395/800, 341/67, 341/65, 341/50, 341/60, 364/DIG. 1, 364/239.3, 375/25, 375/122
• US Class Current: 709/236
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code

Abstract

A variable length codeword packer communicates codeword data in successive m-bit bytes. A binary sum is accumulated indicative of a total number of codeword bits received over time. A byte pointer is derived from at least one most significant bit of the binary sum. A bit pointer is derived from a plurality of least significant bits of the binary sum. A first data storage array has a plurality of m-bit first storage bytes and is responsive to the byte pointer for storing received codeword data in the first storage bytes. A second data storage array has a plurality of m-bit second storage bytes and is responsive to the byte and bit pointers for filling the second storage bytes with codeword data from the first data storage array. m-bit bytes of codeword data are output from each filled second storage byte to provide successive m-bit bytes of codeword data. The use of a multistage approach in packing variable length codewords substantially reduces the complexity as compared to single stage designs.

Claims

1. A variable length codeword packer for use in communicating codeword data in successive m-bit bytes comprising:

means for accumulating a binary sum indicative of a total number of codeword bits received over time;

means for deriving a byte pointer from at least one most significant bit of said binary sum;

means for deriving a bit pointer from a plurality of least significant bits of said binary sum;

a first data storage array having a plurality of m-bit first storage bytes and responsive to said byte pointer for storing full variable length codewords among designated ones of said first storage bytes;

a second data storage array having a plurality of m-bit second storage bytes and responsive to said byte and bit pointers for filling said second storage bytes with codeword data from said first data storage array;

clock means for;

clocking said codeword data into said first data storage array one codeword at a time.

inputting said byte, pointer to said first data storage array when a corresponding codeword is clocked therein,

clocking said codeword data from said first data storage array into said second data, storage array one codeword at a time, and

inputting said byte and bit pointers to said second data storage array when a corresponding codeword is clocked therein; and

means for outputting an m-bit byte of codeword data from each filled second storage byte to provide successive m-bit bytes of codeword data;

wherein;

incoming variable length codewords are successively stored in said first data storage array, each codeword commencing at the beginning of a particular first storage byte identified by said byte pointer based on the binary sum of preceding codeword bit lengths, and

each of the variable length codewords stored in said first data storage array is transferred to said second data storage array commencing at a location within a second storage byte identified by said byte pointer and bit pointer based on the binary sum of preceding codeword bit lengths.

2. A variable length codeword packer in accordance with claim 1 wherein said incoming codewords are grouped in sets containing a plurality of codewords, said codeword packer further comprising:

means for resetting said accumulating means to zero at the beginning of each new set of codewords.

3. A variable length codeword packer in accordance with claim 1 wherein said codewords have a maximum length of n bits, each of said first and second data storage arrays comprise k storage bytes, and each storage byte contains m cells, where

4. A variable length codeword packer in accordance with claim 3 wherein said accumulating means comprise a q-bit accumulator with the p least significant bits thereof forming said bit pointer and the remaining (q-p) most significant bits forming said byte pointer, where p is the number of bits required to identify any one of m cells in a storage byte and (q-p) is the number of bits required to identify any one of k storage bytes.

5. A variable length codeword packer in accordance with claim 4 wherein the codeword data is clocked into said second data storage array one clock cycle after it is clocked into said first data storage array, said codeword packer further comprising:

means for delaying the inputting of said byte and bit pointers to said second data storage array by one clock cycle.

6. A variable length codeword packer in accordance with claim 1 wherein said outputting means are responsive to an incrementing of said byte pointer for outputting data from a second storage byte that has been filled.

7. A variable length codeword packer in accordance with claim 1 wherein the codeword data is clocked into said second data storage array one clock cycle after it is clocked into said first data storage array, said codeword packer further comprising:

means for delaying the inputting of said byte and bit pointers to said second data storage array by one clock cycle.

8. A variable length codeword packer in accordance with claim 7 wherein said incoming codewords are grouped in sets containing a plurality of codewords, said codeword packer further comprising:

means for resetting said accumulating means to zero at the beginning of each new set of codewords.

9. A variable length codeword packer in accordance with claim 8 wherein said outputting means are responsive to an incrementing of said byte pointer for outputting data from a second storage byte that has been filled.