Modified statistical coding of digital signals
DC CAFCFirst Claim
1. A statistical encoder for encoding a digitized signal for transmission over a channel, said signal comprising a plurality of different conditions, each condition having a different frequency of occurrence in said signal, said encoder comprising:
- first means responsive to said signal for generating a first set of codewords, each representing a different signal condition lying in a range of frequencies of occurrences, the codewords having lengths such that the less frequently occurring words generally are longest and the most frequently occurring words generally are shortest;
second means responsive to said signal for generating a second set of codewords, each word of said second set of words representing a signal condition whose frequency of occurrence is less than the frequency of occurrence of said less frequently occurring words, said second set comprising a number of members whose combined frequency of occurrence is statistically organized in a certain order with said range of frequencies of occurrences, each codeword of said second set including a common codeword portion of a length which is statistically based on said combined frequency of occurrence relative to said range of frequencies of occurrences; and
third means for causing said codewords of said first and second sets to be generated in accordance to the frequency of occurrence of the corresponding conditions of said signal.
4 Assignments
Litigations
0 Petitions
Reexamination
Accused Products
Abstract
A ROM includes a single dictionary of variable length codewords wherein Huffman codewords are assigned all members of the dictionary set, including one key codeword being assigned as a prefix codeword segment for a relatively large subgroup of the set, based on the combined probability of occurrence of the subgroup as compared to the individual probabilities of occurrences of the remaining members of the dictionary set. The key codeword is an indication of a departure from straightforward Huffman coding, to prepare an alternative coding scheme for developing a longer codeword which uses the key codeword as a prefix portion of that longer codeword. A unique suffix codeword segment follows the key codeword prefix for particularly identifying each member of the subgroup. The combined probability of occurrence of a member of the subgroup is higher than the probability of occurrence of codewords of shorter length, but the individual probabilities are significantly lower. The subgroup members can be assigned codeword lengths significantly shorter than codewords that would be assigned in straightforward Huffman coding.
177 Citations
23 Claims
-
1. A statistical encoder for encoding a digitized signal for transmission over a channel, said signal comprising a plurality of different conditions, each condition having a different frequency of occurrence in said signal, said encoder comprising:
-
first means responsive to said signal for generating a first set of codewords, each representing a different signal condition lying in a range of frequencies of occurrences, the codewords having lengths such that the less frequently occurring words generally are longest and the most frequently occurring words generally are shortest; second means responsive to said signal for generating a second set of codewords, each word of said second set of words representing a signal condition whose frequency of occurrence is less than the frequency of occurrence of said less frequently occurring words, said second set comprising a number of members whose combined frequency of occurrence is statistically organized in a certain order with said range of frequencies of occurrences, each codeword of said second set including a common codeword portion of a length which is statistically based on said combined frequency of occurrence relative to said range of frequencies of occurrences; and third means for causing said codewords of said first and second sets to be generated in accordance to the frequency of occurrence of the corresponding conditions of said signal. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. Apparatus for encoding a digitized signal for transmission over a channel, said signal comprising a plurality of different values, each value having a given probability of occurrence in said signal, said apparatus comprising:
-
memory means for grouping a plurality of different codewords of different codelengths into first and second groups, each codeword representing a different signal value, said first group of said codewords being organized in a first given order in which at least generally the shortest codeword length manifests that signal value having the greatest probability of occurrence and the greatest codeword length at least generally manifests that signal value having the lowest probability of occurrence, said second group of different codewords comprising a prefix keyword and a suffix code, each codeword being of a given codelength, said prefix keyword of said second group having a length such that the combined probability of occurrence value of all of the signal values represented by the second group is organized with said first given order generally according to said combined probability value regardless the relative codeword length of said second group including the prefix and suffix codes as compared to the codeword length of the next adjacent codes of the first group; and first means responsive to successive values of said digitized signal applied as an input thereto for selecting from said memory means to output respective codewords descriptive of said digitized signal. - View Dependent Claims (8, 9, 10, 11, 12)
-
-
13. A statistical encoder for encoding a digitized signal for transmission over a channel, said signal comprising a plurality of different conditions, each condition having a different frequency of occurrence in said signal, said encoder comprising:
-
first means responsive to said signal for generating a first set of codewords, each representing more commonly occurring zero run length values and non-zero values;
the codewords having lengths according to a statistical rule such that the at least generally less commonly occurring words are longest and the at least generally most commonly occurring words are shortest; andsecond means responsive to said signal for generating a second set of codewords, each word of said second set of words representing less commonly occurring zero run length values, the codewords of the second set each comprising the same prefix keyword code having a length assigned according to the statistical rule with said first set of codewords and a suffix of such length that the prefix and suffix together have length outside said statistical rule
-
-
14. Apparatus for encoding a digitized signal for transmission over a channel, said signal comprising a plurality of different conditions, each condition having a given frequency of occurrence in said signal, said apparatus comprising:
-
first means for grouping, for a first given number of members, a first plurality of codewords representing a first plurality of signal conditions, each codeword representing a different condition, according to a first range of frequencies of occurrence of the condition of said signal, said first plurality comprising codewords of differing lengths, the shortest codeword occurring most frequently, the largest codeword occurring least frequently; and second means for grouping, for a second given number of members, a second plurality of codewords representing a second plurality of signal conditions, each second plurality of codeword representing a different condition according to a second range of frequencies of occurrence of the conditions of said signal, the second range of frequency of occurrence having a combined frequency of occurrence lying in the first range, all said codewords of said first and second pluralities being different, each codeword of the second plurality having a common codeword portion length which is statistically based on said combined frequency of occurrence relative to said first range. - View Dependent Claims (15, 16, 17)
-
-
18. A method for encoding a digitized signal for transmission over a channel, said signal comprising a plurality of different conditions, each condition having a given probability of occurrence in said signal, said method comprising:
-
grouping a plurality of different codewords of different codelengths into first and second groups, each codeword representing a different signal value, a first group of said codewords being organized statistically in a first given order in which at least generally the shortest codeword length manifests that signal condition having the greatest probability of occurrence and at least generally the greatest codeword length manifests that signal condition having the lowest probability of occurrence; a second group of different codewords having a codeword portion length such that the combined probability of occurrence value of all of the signal conditions represented by the second group is organized statistically with said first given order codeword length based on said combined probability value regardless the relative codeword lengths of said second group codewords as compared to the codeword length of the next adjacent codewords of the first group; and causing a memory means in response to the conditions of said digitized signal applied as an input thereto to output that codeword corresponding to the input digitized signal condition. - View Dependent Claims (19, 20)
-
-
21. A method for encoding a digitized signal for transmission over a channel, said signal comprising a plurality of different values, each value having a given frequency of occurrence in said signal, said method comprising:
-
grouping a first plurality of codewords representing a first plurality of signal values, each codeword representing a different value, according to a first range of frequencies of occurrence of the values of said signal, said first plurality comprising codewords of differing lengths according to a statistical rule, wherein the shorter codewords generally occur more frequently and the longer codewords generally occur less frequently; and grouping a second plurality of codewords representing a second plurality of signal values, each second plurality of codewords representing a different value, according to a second range of frequencies of occurrence of the values of said signal, the second range of frequency of occurrence having a combined frequency of occurrence statistically lying in the first range, the codewords of the second group each having the same codeword portion of a length according to said statistical rule and a total length differing from said statistical rule. - View Dependent Claims (22, 23)
-
Specification