Fast and small serial variable length encoder with an optimally high rate for encoding including huffman encoding
OwnerRobert Allen Freking, Keshab K. Parhiinventors
Life of this patent
Estimating the term…
Abstract
A processing means is described for the variable-length encoding of digital signals. The resultant serial encoder admits symbols at data-dependent intervals and progressively releases one bit of encoded output each cycle. The encoder comprises storage, a shifter and a simple pattern tester. Excepting the pattern tester, no arithmetic operations are involved. These three parts are arranged such that processing speed is limited by the greater of the retrieval delay from storage and the delay of the pattern tester. This arrangement is made feasible by an implicit means of codeword length storage. Optimal encoding rates for a serial encoder may hereby be obtained.
Claims6
A machine for processing digital data into variable-length encoded data, comprising:
- (a) storage, storing a plurality of data, each of a predetermined fixed length and comprising:
- (1) a variable-length datum aligned at a predetermined edge,
- (2) punctuation, comprising at least one bit, appending said datum on the unaligned edge, and
- (3) padding bits, distinguishable from said punctuation, of a quantity that is the difference between said predetermined fixed length and the sum of the length of said punctuation and the length of said variable-length datum,
- (b) a translator which:
- (I) translates a fixed-length datum recalled from said storage by a predetermined number of bits per iteration, and
- (II) replaces evacuated bit positions with values distinguishable from said punctuation,
- (c) a pattern detector, which monitors said translator for the presence of padding bits over a predetermined range of bit positions,
- whereby said variable-length datum is extracted from said fixed-length datum without explicit storage of the length of variable-length datum thereof, and
- whereby variable-length encoding is effected.
A method of processing digital data into variable-length data comprising:
- (a) storing a plurality of data, each of a predetermined fixed length and comprising:
- (1) a variable-length datum aligned at a predetermined edge,
- (2) punctuation, comprising at least one bit, appending said datum on the unaligned edge, and
- (3) padding bits, distinguishable from said punctuation, of a quantity that is the difference between said predetermined fixed length and the sum of the length of said punctuation and the length of said variable-length datum,
- (b) translating a recalled fixed-length data by a predetermined number of bits per iteration, replacing evacuated bit positions with values distinguishable from said punctuation,
- (c) detecting patterns resulting from said translating for the presence of padding bits over a predetermined range of bit positions,
- whereby said ariable-length datum is extracted from said fixed-length datum without explicit storage of the length of variable-length datum thereof, and
- whereby variable-length encoding is effected.
A method of processing digital data into variable-length data comprising:
- (a) storing a plurality of data, each of a predetermined fixed length, prepared by a method comprising:
- (b) aligning a variable-length datum at a predetermined edge,
- (c) punctuating said variable-length datum on the unaligned edge with a punctuating datum at least one bit long, and
- (d) padding with a quantity of bits, distinguishable from said punctuating datum, that is the difference between said predetermined fixed length and the sum of the length of said punctuating datum and the length of said variable-length datum,
- (e) translating a recalled fixed-length data by a predetermined number of bits per iteration, replacing evacuated bit positions with values distinguishable from said punctuating datum,
- (f) detecting patterns resulting from said translating for the presence of bits admitted by said padding over a predetermined range of bit positions,
- whereby said variable-length datum is extracted from said fixed-length datum without explicit storage of the length of variable-length datum thereof, and
- whereby variable-length encoding is effected.
Dependencies are inferred from the claim text.