Method and apparatus for digital Huffman encoding
AssigneeSRI International
InventorCharles S. Weaver
Life of this patent
Estimating the term…
Abstract
Coding and decoding method and apparatus are disclosed for implementation of a novel truncated Huffman type code using different length code words. Input signals to be encoded have different probabilities of occurance, and the most frequently occuring signals are assigned the shortest code words. Infrequently occuring input signals are labelled using one of the code words. The set of different length code words employed in the invention include a single binary 1 bit at the least significant bit position of each of the code words. Decoding simply includes means for counting the number of binary 0 bits between the 1 bits of the code word stream.
Claims21
An encoder for coding digital input signals for use in a digital recorder, transmitting, or like system comprising,
- a source of digital input signals of equal word length to be encoded, and
- means responsive to equal word length digital input signals from said source for coding those input signals which are within a predetermined signal range, said coding means comprising means for implementing a code comprising a plurality of different length code words, every which code word is of a length which is different from every other code word and each of which code words includes a single 1 bit at one end bit position of the code words, said single one bit being located at the same end of each of said code words.
In a method of encoding equal word length digital signals which includes converting those equal word length digital signals which are within a predetermined signal range to code words of different length and labeling those equal word length digital signals which are outside said predetermined signal range with a single code word which is of a length which is different than each of said different length code words, the improvement comprising,
- implementing the converting and labeling step by use of a code wherein each of the different length code words includes a single 1 bit at one end bit position thereof.
In an encoder for coding digital input signals for use in a digital recording, transmitting, or like system, comprising,
- a source of digital input signals to be encoded, and
- means responsive to digital input signals for coding those input signals which are within a predetermined signal range and for labeling those input signals which are outside of said predetermined signal range, the improvement wherein
- said coding and labeling means comprises means for implementing a code comprising a plurality of different length code words, every which code word is of a length which is different from every other code word, one of which code words comprises a label for said signals outside of said predetermined signal range, each said different length code word having a single 1 bit which 1 bit is included at one end bit position of said code word, said 1 bit being located at the same end of each of said code words.
A digital signal encoding-decoding combination for use in digital recording-reproducing systems, digital transmitter-receiver systems, or the like, comprising,
- a source of digital signals to be encoded,
- means responsive to digital input signals from said source for coding those input signals which are within a predetermined signal range, said coding means comprising means for implementing a code comprising a plurality of different length code words each of which code words includes a single 1 bit at one end bit position of the code word, and
- means responsive to code words produced by said coding means for decoding the same, said decoding means comprising means for counting the number of zero bits between 1 bits of the code words.
An encoder for converting fixed length digital words into variable length code words comprising,
- a memory unit addressed by said fixed length digital words to be encoded, said memory unit having stored therein a plurality of fixed length words having different numbers of 0's in adjacent bit positions of the words,
- a multiplexer connected to said memory unit for sequentially scanning outputs therefrom for generating said code words, said multiplexing scanning starting at an initial multiplexer address,
- means under control of the output from the multiplexer output for stopping multiplexer scanning when the output from the multiplexer is a 1's bit, and for returning to the initial multiplexer address in preparation for the next scanning operation.
A digital decoder for decoding a stream of encoded digital data words which have been encoded using a code comprising a plurality of different length code words each of which includes a single 1 bit at one end position of the code word and every which code word is of a length which is different from every other code word, said decoder comprising,
- means responsive to a stream of encoded digital data words for counting the number of zero bits between 1 bits, and
- means responsive to the contents of said counting means for regenerating the digital data words.
Dependencies are inferred from the claim text.