Modified statistical coding of digital signals

DC CAFC

US 4,813,056 A
Filed: 12/08/1987
Issued: 03/14/1989
Est. Priority Date: 12/08/1987
Status: Expired due to Term

- Alert
- Pin

Associated Cases

Associated Defendants

First Claim

Patent Images

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 all claims

4 Assignments

Timeline View

Assignment View

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)
- - 2. The encoder of claim 1 wherein said digitized signal is a difference signal produced by a predictive system.
  - 3. The encoder of claim 1 wherein said first and second means include means for generating said first and second sets of codewords from one table wherein said second set comprises codewords having a prefix code assigned according to said statistical certain order and a suffix code assigned according to a non-statistical order.
  - 4. The encoder of claim 3 wherein said statistical order is based on the ordinal position of the combined frequency of occurrence of the second group as compared to the frequency of occurrence of the codewords of the first group.
  - 5. The encoder of claim 4 wherein the members of the second group have fixed length codewords.
  - 6. The encoder of claim 1 wherein said first set of codewords represent non-zero values and more likely to occur zero run lengths of said digitized signal and said second set of codewords represent less likely to occur run lengths of zero value of said signal.

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)
- - 8. The apparatus of claim 7 wherein said memory means includes means for organizing the first and second groups so that said combined probability value is significantly smaller than the combined probability of occurrence of all of the signal values represented by the first group, and is higher than the probability of occurrence of each codeword of a certain portion of the first group.
  - 9. The apparatus of claim 7 wherein said memory means includes means arranged so that said first group is organized in a given assigned statistical code order and said second group is organized in codewords of certain lengths, the initial n bit keyword length portion of each codeword of the second group comprising an assigned codeword of the given statistical code order generally according to the combined probability of occurrence of the signal values of said second group in said given statistical order.
  - 10. The apparatus of claim 7 wherein said first means includes second means for generating an n-bit code representing the detection of a member of said first and second groups of signal values, third means responsive to the detection of a member of the first group for applying said digitized signal representing said first group member as an address to said memory means, fourth means in response to the detection of a member of the second group for determining the run length value of said detected member of the second group and using the determined run length as an address to said memory means.
  - 11. The apparatus of claim 7 wherein said first means includes first logic means for detecting a non-zero level in said digitized signal and a second logic means for detecting a zero level in said digitized signal, and means responsive to said first and second logic means for causing the non-zero level to access the memory means and for counting the zero levels and causing the zero count to access the memory means to generate said output codeword.
  - 12. The apparatus of claim 7 wherein said memory means includes means arranged so that said first group represents non-zero values and more likely to occur run lengths of zero values for said signal and said second group represents less likely to occur run lengths of zero values for said signal.

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; and
  
  second 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)
- - 15. The apparatus of claim 14 wherein said signal conditions represents run length values zero and non-zero values, said apparatus including means for generating an n-bit code signal representing non-zero values and zero run length values and means responsive to said n-bit code signal to cause said first and second means to generate a codeword corresponding to the non-zero value and zero run length value.
  - 16. The apparatus of claim 14 wherein each signal condition represents zero and non-zero values, said apparatus further including address means for accessing said first and second means with an address code comprising the digital values of said signal.
  - 17. The apparatus of claim 14 including switch means for applying an address signal to said first and second means to output a codeword corresponding to the condition of said signal and n-bit code means responsive to said digitized signal for counting run lengths representing one condition in said digitized signal and for determining the conditions of said signal other than the one condition for generating a switch signal for operating said switch means.

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)
- - 19. The method of claim 18 wherein said grouping includes organizing the first and second groups so that the combined probability value of the second group is significantly smaller than the combined probability of occurrence of all of the signal values represented by the first group and is higher than the probability of occurrence of each codeword of a certain portion of the first group.
  - 20. The method of claim 18 wherein said grouping includes grouping the first group into a plurality of codewords representing more likely to occur run lengths of zero values and non-zero values and grouping the second group into a plurality of codewords representing less likely to occur zero run length values.

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)
- - 22. The method of claim 21 wherein said grouping of the second plurality of codewords values includes assigning codewords of m-bits to the second plurality of codewords codes whose prefix n-bit portion falls within the statistical rule and whose remaining suffix m-n bit portion falls outside said statistical rule.
  - 23. The method of claim 21 wherein the first plurality grouping step includes grouping the most likely to occur zero run length values and non-zero values into said first plurality of codewords and said second plurality grouping step includes grouping the less likely to occur zero run length values.

Specification

Resources

Litigation Campaign Assessment

Litigation Data

Current Assignee
Princeton Digital Image Corporation (Princeton Digital)
Original Assignee
General Electric Company
Inventors
Fedele, Nicola J.
Primary Examiner(s)
Safourek, Benedict V.
Assistant Examiner(s)
Chin, Stephen

Application Number

US07/130,379
Time in Patent Office

462 Days
Field of Search

375/27, 375/30, 375/122, 375/25, 358/133, 358/135, 358/261, 382/56, 340/347 DD
US Class Current

375/246
CPC Class Codes

H03M 7/42   using table look-up for the...

H04N 19/152   by measuring the fullness o...

H04N 19/50   using predictive coding H04...

H04N 19/93   Run-length coding

Modified statistical coding of digital signals

First Claim

4 Assignments

Litigations

0 Petitions

Reexamination

Accused Products

Abstract

177 Citations

23 Claims

Specification

Use Cases

Quick Links

Others

Modified statistical coding of digital signals

First Claim

4 Assignments

Subscription Required

Subscription Required

Litigations

0 Petitions

Subscription Required

Reexamination

Accused Products

Subscription Required

Abstract

177 Citations

23 Claims

Specification

Subscription Required

Use Cases

Quick Links

Others