Data compression method and apparatus for waveforms having recurring features

• US 5,442,351 A
• Filed: 09/20/1993
• Issued: 08/15/1995
• Est. Priority Date: 09/20/1993
• Status: Expired due to Term

• Current Assignee: Harley Street Software Ltd.
• Original Assignee: Harley Street Software Ltd.
• Inventors: Horspool, Robert N. S., Windels, Warren J.
• Primary Examiner(s): Williams, Howard L.
• Application Number:
  US08/122,955
• Time in Patent Office: 694 Days
• Field of Search: 341/51, 341/87
• US Class Current: 341/51
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77

Abstract

An apparatus and method for compressing an input sequence of data items produced by sampling a periodic waveform compresses such input sequence by searching a history buffer operable to store consecutive data items, to locate a stored sequence of consecutive data items matching the input sequence. Matching is deemed to occur when each data item in the input sequence is within non-equal upper and lower limits of its corresponding data item in the stored sequence. When a stored sequence matching the input sequence is located compressed output data is produced to represent the stored sequence and the stored sequence is again stored in the history buffer to succeed the data items already stored therein. When a stored sequence matching the input sequence is not located, a representation of the first data item in the input sequence is produced and the first data item is stored in the history buffer to succeed the data items already stored therein. In addition, there is disclosed a system employing the above compression method in combination with a decompression method.

Claims

1. A method of compressing an input sequence of data items produced by sampling a periodic waveform, the method comprising the steps of:

a) searching a First History Buffer operable to store consecutive data items, to locate a stored sequence of consecutive data items matching said input sequence, said matching occurring when each data item in said input sequence is within non-equal upper and lower limits of its corresponding data item in said stored sequence; and

b) when a stored sequence matching said input sequence is located, producing compressed output data representing said stored sequence and storing said stored sequence in the First History Buffer to succeed the data items already in said First History Buffer; and

c) when a stored sequence matching said input sequence is not located, producing uncompressed output data including a representation of the first data item in said input sequence and storing said first data item in the First History Buffer to succeed the data items already stored in said First History Buffer.

2. A method as claimed in claim 1 wherein the step of searching includes, for each input data item in said input sequence, reading a plurality of storage locations in the First History Buffer until a stored data item matching said input data item is located.

3. A method as claimed in claim 2 wherein the step of searching includes maintaining a matching positions list of each history buffer storage location which contains input data values matching a current data item.

4. A method as claimed in claim 3 further including the step of, for each location identified in said matching positions list:

a) comparing a next input data item in said input sequence with the next data item in at least one stored sequence starting at said each location; and

b) removing from said matching positions list all history buffer storage locations for which the next input data item value is not within said non-equal upper and lower limits of the data item value in said stored sequence.

5. A method as claimed in claim 1 further including the step of determining the length of a longest stored sequence of data items which matches said input sequence, said compressed output data representing said longest stored sequence.

6. A method as claimed in claim 5, wherein the step of determining includes the step of, for each data item in said input sequence, incrementing a Match Length Counter each time a further input data item is within said non-equal upper and lower limits of a corresponding data item in said stored sequence, said Match Length Counter having a value representing the length of said longest stored sequence.

9. A method as claimed in claim 1 further including the step of varying at least one of said upper and lower limits such that data items are more closely matched over pre-defined portions of said periodic waveform.

12. An apparatus as claimed in claim 1 wherein said searching means includes maintaining means for maintaining a matching positions list of each First History Buffer storage location which contains input data values matching a current data item.

13. An apparatus as claimed in claim 12 wherein said searching means includes comparing means for comparing a next input data item in said input sequence with the a next data item in at least one stored sequence starting at said each location.

14. An apparatus as claimed in claim 13 wherein said searching means includes removing means for removing from said matching positions list all First History Buffer storage locations for which the next input data item value is not within said non-equal upper and lower limits of the corresponding data item value in said stored sequence.

7. A method, as claimed in 1, wherein the step of producing said compressed output data includes identifying the position of said stored sequence in said First History Buffer and identifying the length of said stored sequence.

8. A method, as claimed in claim 7, wherein the step of identifying the position of said stored sequence includes producing said a code representing a history buffer storage location identifying the beginning of said stored sequence.

10. An apparatus for compressing an input sequence of data items produced by sampling a periodic waveform, the apparatus including:

a) a First History Buffer operable to store consecutive data items in stored sequences;

b) searching means for searching said First History Buffer to locate a stored sequence of consecutive data items matching said input sequence, said matching occurring when each data item in said input sequence is within non-equal upper and lower limits of its corresponding data item in said stored sequence;

c) compressed output producing means for producing compressed output data representing said stored sequence when a stored sequence matching said input sequence is located;

d) storing means for storing said stored sequence represented by said compressed output data, in the First History Buffer, to succeed the data items already in said First History Buffer;

e) data output producing means for producing uncompressed output data including a representation of the first data item in said input sequence when a stored sequence matching said input sequence is not located; and

f) storing means for storing said first data item in the First History Buffer to succeed the data items already stored in said First History Buffer.

11. An apparatus as claimed in claim 10 wherein said searching means includes reading means for reading a plurality of storage locations in the First History Buffer until a stored data item matching said input data item is located.

19. An apparatus as claimed in claim 10 further including varying means for varying at least one of said upper and lower limits such that data items are more closely matched over pre-defined portions of said periodic waveform.

15. An apparatus as claimed in claim 1O further including determining means for determining the length of a longest stored sequence of data items which matches said input sequence, said compressed output data item representing said longest stored sequence.

16. An apparatus as claimed in claim 15 wherein said determining means includes a Match Length Counter and incrementing means for incrementing said Match Length Counter each time a further input data item is within said non-equal upper and lower limits of a corresponding data item in said stored sequence, said Match Length Counter having a value representing the length of said longest stored sequence.

17. An apparatus, as claimed in 10, wherein said compressed output data representing said stored sequence includes position data identifying the position of said stored sequence in said First History Buffer and length data identifying the length of said stored sequence.

18. An apparatus as claimed in claim 17, wherein said position data includes a code representing a First History Buffer storage location identifying the beginning of said stored sequence.

20. An apparatus for compressing an input sequence of data items produced by sampling a periodic waveform, the apparatus including:

a) a First History Buffer operable to store consecutive data items in stored sequences;

b) processing means for;

i) searching said First History Buffer to locate a stored sequence of consecutive data items matching said input sequence, said matching occurring when each data item in said input sequence is within non-equal upper and lower limits of its corresponding data item in said stored sequence; and

ii) when a stored sequence matching said input sequence is located, producing compressed output data representing said stored sequence and storing said stored sequence in the First History Buffer to succeed the data items already in said First History Buffer; and

iii) when a stored sequence matching said input sequence is not located, producing uncompressed output data including a representation of the first data item in said input sequence and storing said first data item in the First History Buffer to succeed the data items already stored in said First History Buffer.

21. An apparatus as claimed in claim 20 wherein said data processing means includes a central processing unit.

22. An apparatus as claimed in claim 21 wherein said central processing unit includes a microprocessor.

23. An apparatus as claimed in claim 20 wherein said First History Buffer includes Random Access Memory.

24. A method of handling input sequences of data derived from an analog source, the method comprising the steps of:

a) compressing said input sequences by;

i) searching a First History Buffer operable to store consecutive data items, to locate a stored sequence of consecutive data items matching said input sequence, said matching occurring when each data item in said input sequence is within non-equal upper and lower limits of its corresponding data item in said stored sequence; and

ii) when a stored sequence matching said input sequence is located, presenting to a transfer medium compressed output data representing said stored sequence and storing said stored sequence in the First History Buffer to succeed the data items already in said First History Buffer; and

iii) when a stored sequence matching said input sequence is not located, presenting to said transfer medium uncompressed output data including a representation of the first data item in said input sequence and storing said first data item in the First History Buffer to succeed the data items already stored in said First History Buffer; and

b) decompressing said output data item by retrieving data from said transfer medium and;

i) when compressed output data is retrieved locating the corresponding stored sequence in a Second History Buffer operable to store sequences of data items and providing to an output medium said stored sequence and storing said stored sequence in said Second History Buffer to succeed the data items already in said Second History Buffer; and

ii) when uncompressed data is retrieved, providing to said output medium said first data item and storing said first data item in the Second History Buffer to succeed the data items already stored in said Second History Buffer.

25. A method as claimed in claim 24 wherein the step of searching includes, for each input data item in said input sequence, reading a plurality of storage locations in the First History Buffer until a stored data item matching said input data item is located.

26. A method as claimed in claim 25 wherein the step of searching includes maintaining a matching positions list of each First History Buffer storage location which contains input data values matching a current data item.

27. A method as claimed in claim 26 further including the step of, for each location identified in said matching positions list:

a) comparing a next input data item in said input sequence with the next data item in at least one stored sequence starting at said each location; and

b) removing from said matching positions list all First History Buffer storage locations for which the next input data item is not within said non-equal upper and lower limits of the corresponding data item in said stored sequence.

28. A method as claimed in claim 24 further including the step of determining the length of a longest stored sequence of data items which matches said input sequence, said compressed output data item representing said longest stored sequence.

29. A method as claimed in claim 28, wherein the step of determining includes the step of, for each data item in said input sequence, incrementing a Match Length Counter each time a further input data item is within said non-equal upper and lower limits of a corresponding data item in said stored sequence, said Match Length Counter having a value representing the length of said longest stored sequence.

32. A method as claimed in claim 24 further including the step of varying at least one of said upper and lower limits.

30. A method, as claimed in 24, wherein the step of producing said compressed output data includes identifying the position of said stored sequence in said First History Buffer and identifying the length of said stored sequence.

31. A method, as claimed in claim 30, wherein the step of identifying the position of said stored sequence includes producing said a code representing a First History Buffer storage location identifying the beginning of said stored sequence.

33. An apparatus for handling input sequences of data derived from an analog source, apparatus including:

a) compressing means for compressing said sequences of data, said compressing means including;

i) a First History Buffer operable to store consecutive data items in stored sequences;

ii) searching means for searching said First History Buffer to locate a stored sequence of consecutive data items matching said input sequence, said matching occurring when each data item in said input sequence is within non-equal upper and lower limits of its corresponding data item in said stored sequence;

iii) compressed output producing means for presenting to a transfer medium compressed output data representing said stored sequence when a stored sequence matching said input sequence is located;

iv) storing means for storing said stored sequence represented by said compressed output data item, in the First History Buffer, to succeed the data items already in said First History Buffer;

v) uncompressed data output producing means for applying to said transfer medium a representation of the first data item in said input sequence when a stored sequence matching said input sequence is not located; and

vi) storing means for storing said first data item in the First History Buffer to succeed the data items already stored in said First History Buffer;

b) decompressing means for decompressing data from said transfer medium, said decompressing means including;

i) retrieving means for retrieving data from said transfer medium;

ii) a Second History Buffer operable to store sequences of data items;

iii) locating means for locating said stored sequence in a Second History Buffer when a compressed output data item representing said stored sequence is retrieved by said retrieving means;

iv) sequence output means for providing to an output medium said stored sequence; and

v) sequence storing means for storing said stored sequence in said Second History Buffer to succeed the data items already in said Second History Buffer; and

vi) data output means for providing to said output medium said first data item when uncompressed data is retrieved by said retrieving means; and

vii) data storing means for storing said uncompressed data item in the Second History Buffer to succeed the data items already stored in said Second History Buffer.

34. An apparatus as claimed in claim 33 wherein said searching means includes reading means for reading a plurality of storage locations in the First History Buffer until a stored data item matching said input data item is located.

35. An apparatus as claimed in claim 34 wherein said searching means includes maintaining means for maintaining a matching positions list of each First History Buffer storage location which contains input data values matching a current data item.

36. An apparatus as claimed in claim 35 wherein said searching means includes comparing means for comparing a next input data item in said input sequence with a next data item in at least one stored sequence starting at said each location.

37. An apparatus as claimed in claim 36 wherein said searching means includes removing means for removing from said matching positions list all First History Buffer storage locations for which the next input data item is not within said non-equal upper and lower limits of the data item in said stored sequence.

38. An apparatus as claimed in claim 33 further including determining means for determining the length of a longest stored sequence of data items which matches said input sequence, said compressed output data item representing said longest stored sequence.

39. An apparatus as claimed in claim 38 wherein said determining means includes a Match Length Counter and incrementing means for incrementing said Match Length Counter each time a further input data item is within said non-equal upper and lower limits of a corresponding data item in said stored sequence, said Match Length Counter having a value representing the length of said longest stored sequence.

42. An apparatus as claimed in claim 33 further including varying means for varying at least one of said upper and lower limits.

43. An apparatus as claimed in claim 33 wherein said transfer medium includes a mass storage device.

44. An apparatus as claimed in claim 33 wherein said transfer medium includes a communications channel.

45. An apparatus as claimed in claim 33 wherein said input sequences include data samples of an analog waveform provided by said analog source.

40. An apparatus, as claimed in 33, wherein said output data item representing said stored sequence includes position data identifying the position of said stored sequence in said First History Buffer and length data identifying the length of said stored sequence.

41. An apparatus as claimed in claim 40, wherein said position data includes a code representing a First History Buffer storage location identifying the beginning of said stored sequence.

46. An apparatus for handling input sequences of data derived from an analog source, the apparatus comprising:

a) compressing means for compressing said input sequences said compressing means including first data processing means for;

i) searching a First History Buffer operable to store consecutive data items, to locate a stored sequence of consecutive data items matching said input sequence, said matching occurring when each data item in said input sequence is within non-equal upper and lower limits of its corresponding data item in said stored sequence; and

ii) when a stored sequence matching said input sequence is located, presenting to a transfer medium compressed output data representing said stored sequence and storing said stored sequence in the First History Buffer to succeed the data items already in said First History Buffer; and

iii) when a stored sequence matching said input sequence is not located, presenting to said transfer media output a representation of the first data item in said input sequence and storing said first data item in the First History Buffer to succeed the data items already stored in said First History Buffer; and

b) decompressing means for decompressing data from said transfer medium, said decompressing means including second data processing means for;

i) retrieving data from said transfer medium and;

i) when a compressed output data item representing said stored sequence is retrieved, locating said stored sequence in a Second History Buffer operable to store sequences of data items and providing to an output medium said stored sequence and storing said stored sequence in said Second History Buffer to succeed the data items already in said Second History Buffer; and

ii) when uncompressed output data is retrieved, providing to said output media said uncompressed output data item and storing said uncompressed data item in the Second History Buffer to succeed the data items already stored in said Second History Buffer.

47. An apparatus as claimed in claim 46 wherein said first and second data processing means include first and second central processing units respectively.

48. An apparatus as claimed in claim 47 wherein said first and second central processing units includes first and second microprocessors respectively.

49. An apparatus as claimed in claim 46 wherein said first and second data processing means are implemented in the same central processing unit.

50. An apparatus as claimed in claim 49 wherein said central processing unit includes a microprocessor.

51. An apparatus as claimed in claim 46 wherein said transfer medium includes a mass storage device.

52. An apparatus as claimed in claim 46 wherein said transfer medium includes a communications channel.

53. An apparatus as claimed in claim 46 wherein said input sequences include data samples of an analog waveform provided by said analog source.