Data compression

• US 7,845,571 B2
• Filed: 06/19/2006
• Issued: 12/07/2010
• Est. Priority Date: 06/19/2006
• Status: Active Grant

• Current Assignee: Mineral Lassen LLC (Intellectual Ventures LLC)
• Original Assignee: Essex PA LLC (Intellectual Ventures LLC)
• Inventors: Monro, Donald M.
• Primary Examiner(s): Trail; Allyson N
• Application Number:
  US11/425,138
• Publication Number:
  US 20070290898A1
• Time in Patent Office: 1,632 Days
• Field of Search: 235/494, 341/51, 341/60, 341/67, 341/83, 707/5, 707/37, 707/102
• US Class Current: 235/494
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code

Abstract

Briefly, in accordance with one embodiment, a method of data compression is disclosed.

Claims

1. A method comprising:

generating, by a processing device, a code sequence using Golomb coding of data, such that a code within the code sequence includes E_i, wherein i is an integer equal to or greater than 1 representing a position of the code within the code sequence; and

generating, by the processing device, a position code in which positions, i, of respective E_i'"'"'s having a same value are adjacent each other in the position code and separated by a spacer code.

2. The method of claim 1, further comprising using an End Of Group (EOG) symbol as the spacer code.

3. The method of claim 1, further comprising:

using E₁=A, E₂=B as the code sequence, such that A and B are integers equal to or greater than 0; and

using 1EOG2EOG as the position code, such that EOG is the spacer code.

4. The method of claim 3, further comprising using A=B, such that the position code comprises 12EOG.

5. The method of claim 1, further comprising using a residual R_i for the each code within the code sequence.

6. The method of claim 5, further comprising interleaving the residual R_i in the position code.

7. The method of claim 6, further comprising interleaving the residual R_i after the spacer code corresponding to E_i.

8. The method of claim 1, wherein the generating the position code comprises generating the position code in which a difference between positions in the code sequence of the similar respective values of the i positions are adjacent each other in the position code and separated by the spacer code.

9. The method of claim 1, wherein the generating the position code further comprises omitting the respective values of the i positions that have already been coded.

10. The method of claim 1, further comprising further coding the position code.

11. The method of claim 10, further comprising Golomb coding the position code.

12. The method of claim 1, further comprising storing or transmitting the position code.

13. The method of claim 1, further comprising using a known length for the code sequence.

14. The method of claim 1, further comprising prefixing to the position code a maximum value of E_i.

15. The method of claim 1, further comprising prefixing to the position code a minimum value of E_i.

16. The method of claim 1, further comprising post-fixing to the position code a maximum value of E_i.

17. The method of claim 1, further comprising post-fixing to the position code a minimum value of E_i.

18. The method of claim 1, further comprising combining both maximum and minimum values of E_i with the position code.

19. The method of claim 1, further comprising using a No More Groups signal to indicate end of the position code.

20. The method of claim 1, further comprising prefixing to the position code a length of the code sequence.

21. The method of claim 1, further comprising using non-numerical data symbols for the data and before the generating the code sequence the method further comprises:

converting the non-numerical data symbols into numerical data by mapping.

22. The method of claim 21, further comprising using symbolic data for the non-numerical data symbols.

23. A system, comprising:

an analyzer configured to;

use Golomb coding of data to generate a code sequence, such that a code within the code sequence includes E_i, wherein i is an integer equal to or greater than 1 representing a position of the code within the code sequence; and

generate a position code in which positions, i, of respective E_i'"'"'s having a same value are adjacent each other in the position code and separated by a spacer code.

24. A method comprising:

for data comprising a numeric data symbol V_i;

determining, by a processing device, a largest integral value of an exponent E_i for which b^Ei does not exceed V_i, where b is a fixed modulo value; and

calculating, by the processing device, a residual R_i=V_i−

b^Ei;

generating, by the processing device, a code sequence, such that a code within the code sequence includes the exponent E_i, wherein i is an integer equal to or greater than 1 representing a position of the code within the code sequence; and

generating, by the processing device, a position code in which positions, i, of respective E_i'"'"'s having a same value are adjacent each other in the position code and separated by a spacer code.

25. A tangible computer-readable medium having stored thereon computer-executable instructions execution of which by a computing device causes the computing device to perform a method comprising:

using Golomb coding of data to generate a code sequence, such that a code within the code sequence includes E_i, wherein i is an integer equal to or greater than 1 representing a position of the code within the code sequence; and

generating a position code in which positions, i, of respective E_i'"'"'s having a same value are adjacent each other in the position code and separated by a spacer code.

26. A computer program product comprising a tangible computer-useable medium having instructions stored thereon, the instructions comprising:

a computer program module that, when executed, uses Golomb coding of data to generate a code sequence, such that a code within the code sequence includes E_i, wherein i is an integer equal to or greater than 1 representing a position of the code within the code sequence; and

a computer program module that, when executed, generates a position code in which positions, i, of respective E_i'"'"'s having a same value are adjacent each other in the position code and separated by a spacer code.

27. A computer program product comprising a tangible computer-useable medium having instructions stored thereon, the instructions comprising:

for data comprising a numeric data symbol V_i;

a computer program module that, when executed, determines a largest integral value of an exponent E_i for which b^Ei does not exceed V_i, where b is a fixed modulo value; and

a computer program module that, when executed, calculates a residual R_i=V_i−

b^Ei;

a computer program module that, when executed, generates a code sequence, such that a code within the code sequence includes the exponent E_i, wherein i is an integer equal to or greater than 1 representing a position of the code within the code sequence; and

a computer program module that, when executed, generates a position code in which positions, i, of respective E_i'"'"'s having a same value are adjacent each other in the position code and separated by a spacer code.