Method and apparatus for chaotic opportunistic lossless compression of data

• US 7,286,670 B2
• Filed: 03/26/2002
• Issued: 10/23/2007
• Est. Priority Date: 11/09/1999
• Status: Expired due to Fees

• Current Assignee: ONMOBILE LIVE, INC. (Onmobile Global Limited)
• Original Assignee: Groove Mobile, Inc. (Live Microsystems, Inc.)
• Inventors: Short, Kevin M.
• Primary Examiner(s): Moise, Emmanuel L.
• Assistant Examiner(s): Gergiso, Techane J.
• Application Number:
  US10/106,696
• Publication Number:
  US 20020154770A1
• Time in Patent Office: 2,037 Days
• Field of Search: 380/263, 380/217, 380/269, 379/88.1, 704/504, 710/68, 345/555
• US Class Current: 380/263
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H04L 2209/30 Compression, e.g. Merkle-Damgard construction
• CPC Class Codes: H04L 9/001 using chaotic signals

Abstract

The present invention is a compression method for compressing digital data. The data is strings of digital values, which can be broken down to a series of 1'"'"'s and 0'"'"'s. The present inventive method uses a chaotic system to compress the data. The first step in the inventive method is generating a plurality of periodic orbits that correspond to a plurality of control bit strings. Each of the periodic orbits is formed with a series of numeric values. The next step is to convert the numeric values of the periodic orbits to digital data values, similar in form to the data to be compressed. The digital data values of the periodic orbits are then organized to identically match the original digital data values. Then the control bit strings corresponding to the organized digital data values of the periodic orbits are identified and saved in order, such that applying the control bit strings to the chaotic system will regenerate the original data.

Claims

1. A compression method for compressing data having original digital data values, said method using a chaotic system, said method comprising the steps of:

generating a plurality of periodic orbits corresponding to a plurality of control bit strings, said periodic orbits having numeric values;

converting the numeric values of the plurality of periodic orbits to generated digital data values;

matching generated digital data values to original digital data values;

identifying the control bit strings that correspond to the matching generated digital data values; and

reducing at least one control bit string in the plurality of control bit strings to a smaller substring whereby the smaller substring is substituted in place of the control bit string.

2. The compression method of claim 1 further comprising decompressing, which comprises the steps of:

receiving the identified control bit strings;

regenerating the plurality of periodic orbits corresponding to the identified control bit strings;

and converting the numeric values of the plurality of periodic orbits to original digital data values.

3. The method of claim 2 wherein the step of decompressing is accomplished without access to a compression dictionary.

4. The method of claim 3 wherein the step of converting further comprises adding numeric values of the at least two separate generated digital data values to construct a matching generated digital data value for the outlying digital data value.

5. The method of claim 3 wherein the step of converting further comprises using the at least two separate generated digital data values to each represent a portion of a matching generated digital data value for the outlying digital data value.

6. The method of claim 1 wherein the step of matching further comprises:

finding an outlying digital data value in the original digital data values whereby a single matching generated digital data value does not exist; and

combining at least two separate generated digital data values to construct a matching generated digital data value for the outlying digital data value.

7. The method of claim 3 wherein the step of converting the numeric values of the plurality of periodic orbits to generated digital data values further comprises:

setting a threshold value;

making any orbit value in a periodic orbit greater than the threshold value a one; and

making any remaining orbit value a zero.

8. The method of claim 1 wherein the step of converting the numeric values of the plurality of periodic orbits to generated digital data values further comprises:

setting a threshold value;

making any orbit section value in a periodic orbit greater than the threshold value a one; and

making any remaining orbit section value a zero.

9. The method of claim 1 wherein the step of converting the numeric values of the plurality of periodic orbits to generated digital data values further comprises:

labeling different sections of the chaotic system with digital labels; and

concatenating digital labels of sections of the chaotic system visited during the periodic orbit by the digital labels thereby generating the generated digital data values.

10. The method of claim 1 further comprising saving the identified control bit strings that correspond to the matching generated digital data values.

11. The method of claim 1 further comprising transmitting the identified and reduced control bit strings to a receiver.

12. A system for compressing data having original digital data values, said system using a chaotic system, said system comprising:

a plurality of periodic orbits corresponding to a plurality of control bit strings, said plurality of periodic orbits having numeric values;

a converting means for using the numeric values of the plurality of periodic orbits to generate a set of generated digital data values;

a matching arrangement of generated digital data values matching the set of generated digital data values to original digital data values;

an ordered arrangement of the control bit strings correspond to the matching arrangement of generated digital data values; and

a reduction means for reducing each control bit string in the plurality of control bit strings to a smaller substring whereby the smaller substring is then used in place of the control bit string.

13. The system of claim 12 wherein:

the original digital data values further comprises an outlying digital data value in the original digital data values whereby no individual member of the set of generated digital data values matches the outlying digital data value; and

the matching arrangement of generated digital data values further comprises a generated digital data value combination consisting of a plurality of individual members of the set of generated digital data values.

14. The system of claim 13 wherein the generated digital data value combination further consists of a sum of the plurality of individual members of the set of generated digital data values to construct part of the matching arrangement of generated digital data values for the outlying digital data value.

15. The system of claim 13 wherein the generated digital data value combination further consists of a concatenation of the plurality of individual members of the set of generated digital data values.

16. The system of claim 12 wherein the converting means further comprises:

a threshold value;

a one bit value for any orbit value in a periodic orbit greater than the threshold value; and

a zero bit value for any remaining orbit value a zero.

17. The system of claim 12 wherein the converting means further comprises:

a threshold value;

a one bit value for any orbit section value in a periodic orbit greater than the threshold value; and

a zero bit value for any remaining orbit section value.

18. The system of claim 12 wherein the converting means further comprises:

a plurality of digital labels for sections of the chaotic system; and

a digital label concatenation of the chaotic system sections visited during periodic orbit.

19. The system of claim 12 further comprising a storage location in which the ordered arrangement of the substrings are stored.

20. The system of claim 12 further comprising a transmitter for transmitting the ordered arrangement of the substrings to a receiver whereby the receiver only requires a mathematically identical chaotic system to decompress the ordered arrangement of the substrings.