# US 4,396,906 A · Method and apparatus for digital Huffman encoding > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 4,396,906 A - Document ID: US4396906A - Status: Granted - Kind: A - Application number: 06/207,728 - Filed: 1980-11-17 - Granted: 1983-08-02 - Earliest claimed: 1980-10-31 - Assignees: SRI International - Inventors: Charles S. Weaver - Web page: https://patentgrep.com/patent/US4396906A ## CPC - H03M 7/42: using table look-up for the coding or decoding process, e.g. using read-only memory {(H03M7/4006 takes precedence)} - H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C) ## 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. ## Claims ### Claim 1 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. ### Claim 2 (depends on 1) An encoder as defined in claim 1 wherein the single 1 bit of the code words is located at the least significant bit position thereof. ### Claim 3 (depends on 1) An encoder as defined in claim 1 wherein said coding means comprises, a memory addressable by said input signals and having a plurality of output lines, shift register means, means operable from a starting position for sequentially connecting said output lines from said memory to said shift register, and means responsive to a 1 bit output from said sequential connecting means for returning said connecting means to said starting position. ### Claim 4 (depends on 3) An encoder as defined in claim 3 wherein said sequential connecting means comprises a digital multiplexer having input channels connected to the output lines from said memory, and an output channel connected to said shift register means. ### Claim 5 (depends on 4) An encoder as defined in claim 4 wherein said returning means includes a counter having an output connected to address inputs of said digital multiplexer for control thereof, which counter includes a reset input for resetting the counter, means connecting the multiplexer output channel to said reset input for resetting the counter whenever a 1 bit is present at said multiplexer output channel. ### Claim 6 (depends on 1) An encoder as defined in claim 1 wherein said source of digital input signals includes digital compression filter means to which digital sample signals are supplied, the output from said digital compression filter means being supplied to said coding means. ### Claim 7 (depends on 6) An encoder as defined in claim 6 wherein said source of digital input signals also includes analog to digital converter means to which analog signals are supplied and from which digital sample signals are obtained. ### Claim 8 (depends on 7) An encoder as defined in claim 7 wherein analog ECG signals are supplied to said analog to digital converter means. ### Claim 9 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. ### Claim 10 (depends on 9) In a method of encoding digital signals as defined in claim 9 wherein the single 1 bit of the code words is located at the least significant bit position thereof. ### Claim 11 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. ### Claim 12 (depends on 11) In an encoder as defined in claim 11 wherein the single 1 bit of the code words is located at the least significant bit position thereof. ### Claim 13 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. ### Claim 14 (depends on 13) A digital signal encoding-decoding combination as defined in claim 13 wherein said single 1 bit of the code words is located at the least significant but position thereof. ### Claim 15 (depends on 13) A digital signal encoding-decoding combination as defined in claim 13 wherein said decoding means comprises means for converting the output from said counting means to digital signals corresponding to those producing said code words. ### Claim 16 (depends on 15) A digital signal encoding-decoding combination as defined in claim 15 wherein said converting means includes a memory addressable by the output from said counter, said memory including a plurality of output lines from which said digital signals corresponding to those producing the code words are read out. ### Claim 17 (depends on 13) A digital signal encoding-decoding combination as defined in claim 13 wherein said source of digital signals to be encoded includes, a source of analog signals, analog to digital converter means for converting the analog signals to digital form, a compression filter responsive to the output from the analog to digital converter means, the compression filter output being supplied to said coding means for coding thereof. ### Claim 18 (depends on 17) A digital signal encoding-decoding combination as defined in claim 17 wherein ECG signals comprise said analog signal source. ### Claim 19 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. ### Claim 20 (depends on 19) An encoder as defined in claim 19 including, a shift register into which said multiplexer output is shifted for holding variable length code words from the multiplexer. ### Claim 21 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.