System and method for data compression using multiple codewords and transmitted indices

Claim 1

A data compression system for operating upon input data sequences comprising A. an encoder for receiving each input sequence, said encoder including two or more quantizer stages, each having a memory for storing an established set of codewords preselected such that the sum of different combinations of codewords, one from each stage, is representative of likely to occur input data sequences, each codeword of each stage having a respective index associated therewith, means for selecting a codeword from at least two of the stages such that the sum of the selected codewords is a closer match to said each input sequence than any other sum of codewords formed from the selected stages, means for retrieving the selected codewords' indices, means for operating upon the retrieved indices, and B. a decoder coupled to the operating means, said decoder including a decoder memory for storing said established sets of codewords with respective indices, means for retrieving from the decoder memory the codewords whose respective indices are operated upon by the operating means, means for adding the retrieved codewords to produce a reproduction data sequence representing an approximation of the said each input data sequence, and c. wherein said established sets of codewords comprise codewords determined by (a) means for storing a training set of data sequences statistically representative of likely to occur input data sequences, (b) means for storing current sets of codewords, one set for each stage (c) means for forming equivalent codewords by adding together different combinations of one codeword from each current set, each equivalent codeword thus being comprised by the sum of a unique combination of constituent codewords, (d) means for forming subsets of the training set of data sequences, one for each equivalent codeword, including in each subset those training set data sequences which match the said each equivalent codeword more closely than any other equivalent codeword, (e) means for computing and storing a first distortion measure between the training set data sequences and their closest equivalent codewords, (f) means for establishing the current sets of codewords as the said established sets of codewords if the distortion measure is less than a predetermined threshold, otherwise continuing to next step, (g) means for, for each stage, replacing the current set of codewords with a computed set of codewords, each computed set being formed for each current codeword of the corresponding stage including means for selecting all equivalent codewords of which the said each current codeword is a constituent, said each current codeword thus associating with a corresponding group of equivalent codewords and their associated subsets of training sequences, means for subtracting from each training sequence of the said associated subsets of each current codeword the difference of the associated subsets' corresponding equivalent codeword and said each current codeword to thereby form a set of residual training sequences, means for averaging the said set of residual training sequences to form a computed codeword, means for replacing said each current codeword by said computed codeword, (h) means for forming new equivalent codewords from the computed codewords, and computing and storing a second distortion measure between the new equivalent codewords and the existing training sequences of the corresponding associated subsets, and operating the means for forming subsets of the training set of data sequences if the second distortion measure is less than a second predetermined threshold, otherwise operating the means for replacing the current set of codewords with a computed set of codewords.

Claim 22

A method for operating upon input data sequences to compress the data using an apparatus comprising (A) an encoder for receiving each input sequence, said encoder including: (a A ) two or more quantizer stages, each having a memory for storing an established set of codewords preselected such that the sum of different combinations of codewords, one from each stage, is representative of likely to occur input data sequences, each codeword of each stage having a respective index associated therewith, (b A ) means for selecting a codeword from at least two of the stages such that the sum of the selected codewords is a closer match to said each input sequence than any other sum of codewords formed from the selected stages, (c A ) means for retrieving the selected codewords' indices, (d A ) means for operating upon the retrieved indices, and (B) a decoder coupled to the operating means, said decoder including (a B ) a decoder memory for storing said established sets of codewords with respective indices, (b B ) means for retrieving from the decoder memory the codewords whose respective indices are operated upon by the operating means, (c B ) means for adding the retrieved codewords to produce a reproduction data sequence representing an approximation of the said each input data sequence, wherein the method comprises a method of establishing sets of codewords determined by (a) storing a training set of data sequences statistically representative of likely to occur input data sequences, (b) storing current sets of codewords, one set for each stage (c) forming equivalent codewords by adding together different combinations of one codeword from each current set, each equivalent codeword thus being comprised by the sum of a unique combination of constituent codewords, (d) forming subsets of the training set of data sequences, one for each equivalent codeword, including in each subset those training set data sequences which match the said each equivalent codeword more closely than any other equivalent codeword, (e) computing and storing a first distortion measure between the training set data sequences and their closest equivalent codewords, (f) establishing the current sets of codewords as the said established sets of codewords if the distortion measure is less than a predetermined threshold, otherwise continuing to next step, (g) for each stage, replacing the current set of codewords with a computed set of codewords, each computed set being formed for each current codeword of the corresponding stage by selecting all equivalent codewords of which the said each current codeword is a constituent, said each current codeword thus associating with a corresponding group of equivalent codewords and their associated subsets of training sequences, subtracting from each training sequence of the said associated subsets of each current codeword the difference of the associated subsets' corresponding equivalent codeword and said each current codeword to thereby form a set of residual training sequences, averaging the said set of residual training sequences to form a computed codeword, replacing said each current codeword by said computed codeword, (h) forming new equivalent codewords from the computed codewords, and computing and storing a second distortion measure between the new equivalent codewords and the existing training sequences of the corresponding associated subsets, and (i) returning to step (d) if the second distortion measure is less than a second predetermined threshold, otherwise repeating step (g).

Claim 23

A method for operating upon input data sequences to compress the data using an apparatus comprising (A) an encoder for receiving each input sequence, said encoder including: (a A ) two or more quantizer stages, each having a memory for storing an established set of codewords preselected such that the sum of different combinations of codewords, one from each stage, is representative of likely to occur input data sequences, each codeword of each stage having a respective index associated therewith, (b A ) means for selecting a codeword from at least two of the stages such that the sum of the selected codewords is a closer match to said each input sequence than any other sum of codewords formed from the selected stages, (c A ) means for retrieving the selected codewords' indices, (d A ) means for operating upon the retrieved indices, and (B) a decoder coupled to the operating means, said decoder including (a B ) a decoder memory for storing said established sets of codewords with respective indices, (b B ) means for retrieving from the decoder memory the codewords whose respective indices are operated upon by the operating means, (c B ) means for adding the retrieved codewords to produce a reproduction data sequence representing an approximation of the said each input data sequence, wherein the method comprises a method of establishing sets of codewords determined by (a) storing a training set of data sequences statistically representative of likely to occur input data sequences, (b) storing current sets of codewords, one set for each stage (c) forming equivalent codewords by adding together different combinations of one codeword from each current set, each equivalent codeword thus being comprised by the sum of a unique combination of constituent codewords, (d) forming subsets of the training set of data sequences, one for each equivalent codeword, including in each subset those training set data sequences which match the said each equivalent codeword more closely than any other equivalent codeword, (e) computing and storing a first distortion measure between the training set data sequences and their closest equivalent codewords, (f) establishing the current sets of codewords as the said established sets of codewords if the distortion measure is less than a predetermined threshold, otherwise continuing to next step, (g) for each stage, replacing the current set of codewords with a computed set of codewords, each computed set being formed for each current codeword of the corresponding stage by selecting all equivalent codewords of which the said each current codeword is a constituent, said each current codeword thus associating with a corresponding group of equivalent codewords and their associated subsets of training sequences, subtracting from each training sequence of the said associated subsets of each current codeword the difference of the associated subsets' corresponding equivalent codeword and said each current codeword to thereby form a set of residual training sequences, averaging the said set of residual training sequences to form a computed codeword, replacing said each current codeword by said computed codeword, (h) forming new equivalent codewords from the computed codewords, and computing and storing a second distortion measure between the new equivalent codewords and the existing training sequences of the corresponding associated subsets, and (i) returning to step (d) if the second distortion measure is less than a second predetermined threshold, otherwise repeating step (g).

Claim 43

A system for compressing input data sequences comprising A. an encoder for receiving each input sequence, said encoder including two or more quantizer stages, each having a memory for storing an established set of codewords preselected such that the sum of different combinations of codewords, one from each stage, is representative of likely to occur input data sequences, each codeword of each stage having a respective index associated therewith, means for selecting a codeword from at least two of the stages such that the sum of the selected codewords is a closer match to said each input sequence than any other sum of codewords formed from the selected stages, means for retrieving the selected codewords' indices, means for operating upon the retrieved indices, and B. a decoder coupled to the operating means, said decoder including a decoder memory for storing said established sets of codewords with respective indices, means for retrieving from the decoder memory the codewords whose respective indices are operated upon by the operating means, means for adding the retrieved codewords to produce a reproduction data sequence representing an approximation of the said each input data sequence, and C. wherein said established sets of codewords comprise codewords determined (a) storing a training set of data sequences statistically representative of likely to occur input data sequences, (b) storing current sets of codewords, one set for each stage (c) forming equivalent codewords by adding together different combinations of one codeword from each current set, each equivalent codeword thus being comprised by the sum of a unique combination of constituent codewords, (d) forming subsets of the training set of data sequences, one for each equivalent codeword, including in each subset those training set data sequences which match the said each equivalent codeword more closely than any other equivalent codeword, (e) computing and storing a first distortion measure between the training set data sequences and their closest equivalent codewords, (f) establishing the current sets of codewords as the said established sets of codewords if the distortion measure is less than a predetermined threshold, otherwise continuing to next step, (g) for each stage, replacing the current set of codewords with a computed set of codewords, each computed set being formed for each current codeword of the corresponding stage by selecting all equivalent codewords of which the said each current codeword is a constituent, said each current codeword thus associating with a corresponding group of equivalent codewords and their associated subsets of training sequences, subtracting from each training sequence of the said associated subsets of each current codeword the difference of the associated subsets' corresponding equivalent codeword and said each current codeword to thereby form a set of residual training sequences, averaging the said set of residual training sequences to form a computed codeword, replacing said each current codeword by said computed codeword, (h) forming new equivalent codewords from the computed codewords, and computing and storing a second distortion measure between the new equivalent codewords and the existing training sequences of the corresponding associated subsets, and (i) returning to step C.(d) if the second distortion measure is less than a second predetermined threshold, otherwise repeating step C.(g).

Claim 44

A system for compressing input data sequences comprising A. an encoder for receiving each input sequence, said encoder including two or more quantizer stages, each having a memory for storing an established set of codewords preselected such that the sum of different combinations of codewords, one from each stage, is representative of likely to occur input data sequences, each codeword of each stage having a respective index associated therewith, means for selecting a codeword from at least two of the stages such that the sum of the selected codewords is a closer match to said each input sequence than any other sum of codewords formed from the selected stages, means for retrieving the selected codewords' indices, means for operating upon the retrieved indices, and B. a decoder coupled to the operating means, said decoder including a decoder memory for storing said established sets of codewords with respective indices, means for retrieving from the decoder memory the codewords whose respective indices are operated upon by the operating means, means for adding the retrieved codewords to produce a reproduction data sequence representing an approximation of the said each input data sequence, and C. wherein said established sets of codewords comprise codewords determined (a) storing a training set of data sequences statistically representative of likely to occur input data sequences, (b) storing current sets of codewords, one set for each stage (c) forming equivalent codewords by adding together different combinations of one codeword from each current set, each equivalent codeword thus being comprised by the sum of a unique combination of constituent codewords, (d) forming subsets of the training set of data sequences, one for each equivalent codeword, including in each subset those training set data sequences which match the said each equivalent codeword more closely than any other equivalent codeword, (e) computing and storing a first distortion measure between the training set data sequences and their closest equivalent codewords, (f) establishing the current sets of codewords as the said established sets of codewords if the distortion measure is less than a predetermined threshold, otherwise continuing to next step, (g) for each stage, replacing the current set of codewords with a computed set of codewords, each computed set being formed for each current codeword of the corresponding stage by selecting all equivalent codewords of which the said each current codeword is a constituent, said each current codeword thus associating with a corresponding group of equivalent codewords and their associated subsets of training sequences, subtracting from each training sequence of the said associated subsets of each current codeword the difference of the associated subsets' corresponding equivalent codeword and said each current codeword to thereby form a set of residual training sequences, averaging the said set of residual training sequences to form a computed codeword, replacing said each current codeword by said computed codeword, (h) forming new equivalent codewords from the computed codewords, and computing and storing a second distortion measure between the new equivalent codewords and the existing training sequences of the corresponding associated subsets, and (i) returning to step C.(d) if the second distortion measure is less than a second predetermined threshold, otherwise repeating step C.(g).