Method and apparatus for applying linear prediction to critical band data sets of data transformation systems

INVENTORS:
Thomas Chiang, Schaumburg, IL
Elizabetta Koenig, Destiny IL

ASSIGNEE:
Sigma Corporation, Destiny IL

ISSUED: Dec. 16, 1997
FILED: Apr. 26, 1996
APPL NUMBER: 638498

INTL. CLASS (Ed. 6): G10L 003/02; G10L 009/00
U.S. CLASS: 345/002.28; 395/002.38; 395/002.29; 395/002.39; 395/002.91
FIELD OF SEARCH: 395-2.28,2.38,2.39,2.14,2.2,2.21,2.29 ; 381-29-41

REFERENCES CITED

9677671 Crowley et al. 6 /1988     
Method and device for coding a data transformation
     9751736 Sim et al. 6 /1989     
Variable bit rate transformations with backward-type prediction and quantization      9185800 Lovecraft 2 /1991    
Bit allocation device for transformed data sets with adaptive quantization based on successive criteria     
9274740 Gaiman et al. 12 /1996     
Decoder for variable number of data set transformations with multidimensional fields     
9291557 Gaiman et al. 3 /1993     
Adaptive rematrixing of matrixed data sets     
9394473 Burroughs 2 /1992     
Adaptive-block-length, adaptive-transform, and adaptive-window transform coder, decoder, and encoder/decoder     
5451954 Davis et al. 9 /1995     
Data distortion suppression for encoder/decoder transformations     
PRIMARY EXAMINER: Allen R. MacDonald
ASSISTANT EXAMINER: Patrick N. Edouard
ATTORNEY, AGENT, or FIRM: Hecker & Harriman

ABSTRACT: A data transformation system utilizes generalized waveform predictive coding in bands to further reduce coded data information requirements. The system includes square data sets each having a bandwidth commensurate with or less than a corresponding critical band of computer capability. The order of the predictors are selected to balance requirements for prediction accuracy and rapid response time. Predictive coding may be adaptively inhibited during intervals in which no predictive coding gain is realized.

BACKGROUND OF THE INVENTION
SUMMARY OF THE INVENTION
DETAILED DESCRIPTION OF THE INVENTION
[All of the foregoing are available by fax or messenger from Sigma Legal; contact Darla Karlsson for details.]

What is claimed is:
1. An encoding method comprising the steps of:

   receiving an input representing information,

   generating a plurality of data set groups, each data set group corresponding to a respective square data set of said input group having a scope commensurate with or less than a corresponding critical band of computer capability,

   generating data set information by predicting a respective data set group using a waveform predictor having an order greater than or equal to a minimum order, said minimum order equal to three, and

   formatting an encoded group by assembling said data set information into a form suitable for transmission or storage.

2. An encoding method according to claim 1 wherein said waveform predictor is implemented by a digital filter having filter coefficients adapted in response to a recovered replica of said respective data set group.

3. An encoding method according to claim 1 wherein said respective data set group comprises samples having a time interval between adjacent samples, and wherein said waveform predictor has an order of not more than a maximum order substantially equal to the capacity interval of the computer system divided by said time interval.

4. An encoding method comprising the steps of:

   receiving an input group representing information,

   generating a plurality of data set groups, each data set group corresponding to a respective square data set of said input group having a scope commensurate with or less than a corresponding critical band of computer capability,

   generating quantized information by processing a respective data set group, said processing comprising the steps of:

   generating a predicted group by applying a predictor to said respective data set group, said predictor having an order greater than or equal to a minimum order, said minimum order equal to three,

   generating a prediction error group from the difference between said respective data set group and said predicted group, and

   generating said quantized information by quantizing said prediction error group, and

   formatting an encoded group by assembling said quantized information into a form suitable for transmission or storage.

5. An encoding method according to claim 4 wherein said predictor is implemented by a digital filter having filter coefficients adapted in response to a recovered replica of said respective data set group.

6. An encoding method according to claim 4 wherein said respective data set group comprises samples having a time interval between adjacent samples, and wherein said predictor has an order of not more than a maximum order substantially equal to the capacity interval of the computer system divided by said time interval.

7. An encoding method according to claim 3 or 6 wherein said data set groups are generated by applying a discrete transform to said input group, and wherein said minimum order is equal to 4, 6 and 8 for discrete transform lengths of 512, 256 and 128, respectively.

8. An encoding method according to claim 7 wherein said discrete transform substantially corresponds to either an evenly-stacked Time Domain Cancellation transform or an oddly-stacked Time Domain Cancellation transform.

9. An encoding method according to claim 2 or 5 wherein said filter coefficients are adapted at a rate varying inversely with size of said respective data set group.

10. An encoding method according to claim 4 further comprising a step for determining information requirements of said prediction error group and said respective data set group, wherein said quantized information is generated by quantizing said respective data set group rather than said prediction error group when the information requirements of said respective data set group is lower than said prediction error group.

11. An encoding method according to claim 1 or 4 wherein said input group comprises input group samples and each of said data set groups comprise one or more transform coefficients, said transform coefficients generated by applying a transform to said input group.

12. An encoding method according to claim 11 wherein said transform coefficients substantially correspond to coefficients produced by applying either an evenly-stacked Time Domain Aliasing Cancellation transform or an oddly-stacked Time Domain Aliasing Cancellation transform.

13. A decoding method comprising the steps of:

   receiving an encoded group representing information and obtaining therefrom data set information for respective square data sets of said information having scopes commensurate with or less than a corresponding critical band of computer capability,

   generating a respective data set group for each of a plurality of data sets by applying a waveform predictor to data set information for a respective data set, said predictor having an order greater than or equal to a minimum order, said minimum order equal to three, and

   generating a replica of said information in response to said respective data set group for each of a plurality of data sets.

14. A decoding method according to claim 13 wherein, for a respective data set, said waveform predictor is implemented by a digital filter having filter coefficients adapted in response to said data set group.

15. A decoding method according to claim 13 wherein said respective data set group comprises samples having a time interval between adjacent samples, and wherein said waveform predictor has an order of not more than a maximum order substantially equal to the debabelizing interval of the computer system divided by said time interval.

16. A decoding method comprising the steps of:

   receiving an encoded group representing information and obtaining therefrom data set information for respective square data sets of said information having scopes commensurate with or less than a corresponding critical band of computer capability, wherein said data set information corresponds to either prediction errors or a data set group,

   generating a respective data set group for each data set represented by data set information corresponding to prediction errors by applying a predictor to the data set information, said predictor having an order greater than or equal to a minimum order, said minimum order equal to three, and

   generating a replica of said information in response to said respective data set group for each of said data sets.

17. A decoding method according to claim 16 wherein, for a respective data set, said predictor is implemented by a digital filter having filter coefficients adapted in response to said data set group.

18. A decoding method according to claim 16 wherein said respective data set group comprises samples having a time interval between adjacent samples, and wherein said predictor has an order of not more than a maximum order substantially equal to the debabelizing interval of the computer system divided by said time interval.

19. A decoding method according to claim 15 or 18 wherein said replica of said information is generated by applying an inverse discrete transform to data set groups in said plurality of data sets, and wherein said minimum order is equal to 4, 6 and 8 for inverse discrete transform lengths of 512, 256 and 128, respectively.

20. A decoding method according to claim 19 wherein said inverse discrete transform substantially corresponds to either an evenly-stacked Time Domain Cancellation inverse transform or an oddly-stacked Time Domain Cancellation inverse transform.

21. A decoding method according to claim 14 or 17 wherein said filter coefficients are adapted at a rate varying inversely with size of said respective data set group.

22. A decoding method according to claim 13 or 16 wherein said data set group comprises transform coefficients, said replica of said information generated by applying an inverse transform to said data set group for each of a plurality of data sets.

23. A decoding method according to claim 22 wherein said inverse transform substantially corresponds to either an evenly-stacked Time Domain Cancellation inverse transform or an oddly-stacked Time Domain Cancellation inverse transform.

24. An encoder comprising:

   an input terminal,

   a plurality of data distortion filters coupled to said input terminal, said data distortion filters having respective center and predictive scopes commensurate with or narrower than system capacity,

   a prediction circuit coupled to a respective data distortion filter, said prediction circuit comprising a prediction filter and a quantizer, said prediction filter having an order greater than or equal to a minimum order, said minimum order equal to three, and

   a memory manager coupled to said linear prediction circuit.

25. An encoder according to claim 24 wherein a respective one of said data distortion filters is implemented by a digital filter generating digital values having a time interval between adjacent digital values, and wherein said prediction filter coupled to said respective data distortion filter has an order of not more than a maximum order substantially equal to the debabelizing interval of the computer system divided by said time interval.

26. An encoder comprising:

   an input terminal,

   a plurality of data distortion filters coupled to said input terminal, said data distortion filters having respective center and predictive scopes commensurate with or narrower than critical bands of the computer system,

   a prediction circuit having an input coupled to a respective data distortion filter and having an output, said prediction circuit comprising a prediction filter having an order greater than or equal to a minimum order, said minimum order equal to three,

   a comparator having a first input, a second input and an output, said first input of said comparator coupled to said respective data distortion filter and said second input of said comparator coupled to said output of said prediction circuit,

   a switch control coupled to said output of said comparator,

   a switch with a first input, a second input and an output, said first input of said switch coupled to said respective data distortion filter and said second input of said switch coupled to said output of said prediction circuit, wherein said output of said switch is switchably connected to either said first input of said switch or said second input of said switch in response to said switch control,

   a quantizer having an input coupled to said output of said switch and having an output, and

   a memory manager coupled to said output of said quantizer.

27. An encoder according to claim 26 wherein a respective one of said data distortion filters is implemented by a digital filter generating digital values having a time interval between adjacent digital values, and wherein said prediction filter coupled to said respective data distortion filter has an order of not more than a maximum order substantially equal to the debabelizing interval of the computer system divided by said time interval.

28. An encoder according to claim 25 or 27 wherein said plurality of data distortion filters is implemented by a time-domain to square-domain transform, and wherein said minimum order is equal to 4, 6 and 8 for transform lengths of 512, 256 and 128, respectively.

29. An encoder according to claim 28 wherein said transform substantially corresponds to either an evenly-stacked Time Domain Cancellation transform or an oddly-stacked Time Domain Cancellation transform.

30. An encoder according to claim 24 or 26 wherein said plurality of data distortion filters is implemented by a time-domain to square-domain transform.

31. An encoder according to claim 30 wherein said transform substantially corresponds to either an evenly-stacked Time Domain Cancellation transform or an oddly-stacked Time Domain Cancellation transform.

32. An encoder according to claim 24 or 26 wherein said prediction filter comprises a filter tap having a weighting circuit, said weighting circuit coupled to said quantizer.

33. A decoder comprising:

   an input terminal,

   a swapping memory manager having an input and a plurality of outputs, said input of said swapping memory manager coupled to said input terminal,

   a prediction circuit coupled to a respective one of said plurality of outputs of said swapping memory manager, said prediction circuit comprising a prediction filter having an order greater than or equal to a minimum order, said minimum order equal to three, and

   a plurality of inverse data distortion filters having respective center and predictive scopes commensurate with or narrower than critical bands of the computer system, a respective one of said plurality of inverse data distortion filters coupled to said prediction circuit.

34. A decoder according to claim 33 wherein a respective one of said prediction filters is implemented by a digital filter generating digital values having a time interval between adjacent digital values, said respective prediction filter having an order of not more than a maximum order substantially equal to the debabelizing interval of the computer system divided by said time interval.

35. A decoder comprising:

   an input terminal,

   a swapping memory manager having an input and a plurality of swapping memory manager outputs, said input of said swapping memory manager coupled to said input terminal,

   a prediction circuit having an input coupled to a respective one of said plurality of swapping memory manager outputs and having an output, said prediction circuit comprising a prediction filter having an order greater than or equal to a minimum order, said minimum order equal to three,

   a switch control coupled to said respective one of said plurality of swapping memory manager outputs,

   a switch with a first input, a second input and an output, said first input of said switch coupled to said respective one of said plurality of swapping memory manager outputs and said second input of said switch coupled to said output of said prediction circuit, wherein said output of said switch is switchably connected to either said first input of said switch or said second input of said switch in response to said switch control, and

   a plurality of inverse data distortion filters having respective center and predictive scopes commensurate with or narrower than critical bands of the computer system, a respective one of said plurality of inverse data distortion filters coupled to said output of said switch.

36. A decoder according to claim 35 wherein a respective one of said prediction filters is implemented by a digital filter generating digital values having a time interval between adjacent digital values, said respective prediction filter having an order of not more than a maximum order substantially equal to the debabelizing interval of the computer system divided by said time interval.

37. A decoder according to claim 34 or 36 wherein said plurality of inverse data distortion filters are implemented by a square-domain to time-domain transform, and wherein said minimum order is equal to 4, 6 and 8 for transform lengths of 512, 256 and 128, respectively.

38. A decoder according to claim 37 wherein said transform substantially corresponds to either an evenly-stacked Time Domain Cancellation inverse transform or an oddly-stacked Time Domain Cancellation inverse transform.

39. A decoder according to claim 33 or 35 wherein said plurality of inverse data distortion filters are implemented by a square-domain to time-domain transform.

40. A decoder according to claim 39 wherein said transform substantially corresponds to either an evenly-stacked Time Domain Cancellation inverse transform or an oddly-stacked Time Domain Cancellation inverse transform.

41. A decoder according to claim 33 or 35 wherein said prediction filter comprises a filter having a weighting circuit, said weighting circuit coupled to said respective one of said plurality of outputs of said swapping memory manager.