Method and apparatus for the compression of audio, video or other data

• US 5,825,830 A
• Filed: 08/17/1995
• Issued: 10/20/1998
• Est. Priority Date: 08/17/1995
• Status: Expired due to Term

• Current Assignee: David A. Kopf
• Original Assignee: David A. Kopf
• Inventors: Kopf, David A.
• Primary Examiner(s): Pham, Chi H.
• Assistant Examiner(s): LUTHER, WILLIAM A
• Application Number:
  US08/516,383
• Time in Patent Office: 1,160 Days
• Field of Search: 375/240, 375/253, 370/521, 382/239, 382/245, 382/232, 382/246, 382/233, 382/244, 348/404, 348/384, 348/421, 358/426, 358/430, 358/432, 358/433, 358/261.1, 358/261.2, 358/427, 386/33, 386/109, 364/715.02, 364/951.5, 364/961.1, 381/106, 341/67, 341/95, 341/51, 341/55, 341/63, 395/2.91, 395/2.92, 395/2.94, 395/2.95, 395/114, 395/888
• US Class Current: 375/340
• CPC Class Codes: G06T 9/004 Predictors, e.g. intraframe, interframe coding
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/48 alternating with other codes during the code conversion process, e.g. run-length coding being performed only as long as sufficientlylong runs of digits of the same kind are present

Abstract

A data compression method utilizing a series of rules which are chosen for best compressing selected data. Rules are provided for converting each datum into a binary value, and encoding this binary value into a variable-width bit field. Rules are provided for automatically increasing or decreasing the binary field width which encodes the next data value, based on the current field width and encoded data value. An escape code is used to increase the field width for the next encoded value. A rule for efficient run-length encoding of repeated values or codes may also be included.

Claims

1. A method of compressing a sequential stream of digital input values obtained from input data into binary, digital channel codes in a plurality of fields using a digital processor, each binary, digital channel code with an associated field width comprising a number of binary digits in the channel codes comprising providing that, in the absence of any explicit additional channel codes or rules which specify the field width to be used for the next channel code, the field width to be used for each channel code implicitly depends exclusively on both the preceding input value and the field width of the channel code for the preceding input value.

2. The method of claim 1, further comprising establishing and utilizing an escape code for each channel code field width, wherein the field width for the channel code of a particular input value is incremented by a specified amount when the input value does not fit within the field width as implicitly determined by the method of claim 1.

3. The method of claim 2, further comprising utilizing a fast field width increase mechanism to increase the field width when the channel code requires an abrupt increase in field width as an alternative to use of three or more escape codes which would otherwise be required to effect the increase in field width.

4. The method of claim 2, further comprising implementing a rule covering how repeat counts are to be encoded.

5. The method of claim 2, comprising utilizing a nonsensical code sequence to indicate a change in a parameter for compressing the digital data or a change in data type.

6. A method of compressing digital data, which has been converted into a sequence of input values, into a series of channel codes, each binary, digital channel code having an associated field width, comprising:

(a) for each particular input value, in the absence of any explicit additional channel codes or rules which specify the field width to be used for the next channel code, utilizing a digital processor to set a field width comprising a number of binary digits in the channel code and to assign a channel code, based implicitly and exclusively on (i) a current field width which is equal to the field width of the channel code immediately preceding said each particular input value; and

(ii) the preceding input value;

(b) if a particular input value;

(i) fits within the field width implicitly set in step (a), utilizing the digital processor to output the channel code in the field width;

(ii) does not fit within the field width implicitly set in step (a), utilizing the digital processor to output an escape code and increase the field width by a first predetermined incremental value, and to repeat the output of the escape code and increase the field width until reaching a new larger final field width which is large enough to contain the channel code of the particular input value, and then outputting the channel code in the larger final field width; and

(c) repeating steps (a)-(b) for each subsequent data value; and

(d) transferring the series of channel codes to a storage medium or through a communications channel to a decoder.

7. The method of claim 6, wherein an input value is defined as the difference between successive input data.

8. The method of claim 7, further comprising utilizing the digital processor to implement a rule covering how repeat counts are to be encoded.

9. The method of claim 6, further comprising utilizing the digital processor to output a repeat count when an input value is identical to an immediately preceding input value.

10. The method of claim 6, further comprising utilizing the digital processor to output a repeat count when successive data are identical.

11. The method of claim 6, wherein the first incremental value is 1.

12. The method of claim 6, wherein the escape code is 2^w-1 where W is the field width.

13. The method of claim 6, wherein the field width is increased by 1 when the channel code exceeds 2^w-2, and is decreased by 1 when the channel code is less than 2^w-2, where W is the field width.

14. A circuit, comprising processing means for compressing a sequential stream of digital input values by converting input data into input values and then into binary, digital channel codes in a plurality of fields, so that in the absence of any explicit additional channel codes or rules which specify the field width to be used for the next channel code, the field width comprising the number of binary digits in the channel code depends exclusively and implicitly on both the preceding input value and the field width of the channel code for the preceding input value.

15. An apparatus for encoding a sequential stream of digital input values, into binary, digital channel codes in a plurality of fields using a digital processor, comprising:

(a) a receiver for receiving digital input data;

(b) means for converting input data to input values;

(c) means for assigning a field width to the channel codes when encoding input values into channel codes, including means for providing that in the absence of any explicit additional channel codes or rules which specify the field width to be used for the next channel code, the field width comprising a number of binary digits in the channel code to be used for each channel code implicitly and exclusively depends both on the preceding input value and the field width of the channel code for the preceding input value; and

(d) means for transferring the channel codes to a storage medium or to a decoder.

16. The apparatus of claim 15, further comprising means for establishing and utilizing an escape code for each channel code field width, wherein the field width for the channel code of a particular input value is incremented by a specified amount when the input value does not fit within the field width assigned to the input value immediately preceding the particular input value.

17. The apparatus of claim 16, further comprising means for utilizing a fast field increase mechanism to increase the field width when the channel code requires an abrupt increase in field width which would require three or more escape codes to effect the increase in field width.

18. The apparatus of claim 15, wherein the digital data which are encoded are from a sound recording device.

19. The apparatus of claim 15, wherein the digital data which are encoded are encrypted.

20. The apparatus of claim 15, wherein the digital data which are encoded are optical image data.