Adaptive combinatorial coding/decoding with specified occurrences for electrical computers and digital data processing systems

• US 7,791,513 B2
• Filed: 10/06/2008
• Issued: 09/07/2010
• Est. Priority Date: 10/06/2008
• Status: Expired due to Fees

• Current Assignee: Technology Value Group, LLC
• Original Assignee: Donald M. Monro
• Inventors: Monro, Donald Martin
• Primary Examiner(s): Barnie, Rexford N
• Assistant Examiner(s): Lauture, Joseph
• Application Number:
  US12/246,409
• Publication Number:
  US 20100085224A1
• Time in Patent Office: 701 Days
• Field of Search: 341/107, 341/108, 341/50, 341/51, 341/106, 341/59, 341/87, 375/240, 704/4, 710/68, 382/247
• US Class Current: 341/107
• CPC Class Codes: H03M 7/3082 Vector coding for television signals, see H04N19/94
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
• CPC Class Codes: H03M 7/4006 Conversion to or from arithmetic code

Abstract

Embodiments described herein may include example embodiments of a method, article and apparatus for compressing data utilizing a combinatorial encoder with specified occurrences which may be used for communicating between two or more components connected to an interconnection medium (e.g., a bus) within a single computer or digital data processing system, and/or for communication between computing platforms via a network or other interconnection medium.

Claims

1. A method comprising:

selecting a first specified number of occurrences of a symbol string based, at least in part, on a first estimated probability of said selected symbol string, said symbol string being selected from a portion of data to be encoded;

generating a first symbol string code indicative of a first length of data containing said first specified number of occurrences;

determining a first compressed data code based, at least in part, on said first symbol string code;

updating said estimated probability;

selecting a further specified number of occurrences of said symbol string based, at least in part, on said updated estimated probability;

generating a second symbol string code indicative of a second length of data containing said second specified number of occurrences; and

determining a second compressed data code based, at least in part, on said second symbol string code.

2. The method of claim 1, and further comprising:

generating a third symbol string code indicative of a pattern of occurrences of said selected symbol string in said first length of data; and

combining said first and third symbol strings into a first compressed data code.

3. The method of claim 2, and further comprising:

generating a fourth symbol string code indicative of a pattern of occurrences of said selected symbol string in said second length of data; and

combining said second and fourth symbol strings into a second compressed data code.

4. The method of claim 1, wherein said updating said estimated probability further comprises updating said estimated probability based, at least in part, on an actual number of occurrences of said selected symbol string.

5. The method of claim of 1, wherein said selecting said first or second specified number of occurrences is constrained by maximum and minimum numbers of occurrences.

6. The method of claim 1, wherein said updating said estimated probability further comprises applying a filter to at least a previous estimated probability of occurrence of said selected symbol string.

7. The method of claim 1, and further comprising:

partitioning a data set into one or more blocks of data;

selecting a block of data to compress; and

generating a compressed data code based on said selected block of data.

8. An article comprising:

a storage medium comprising machine-readable instructions stored thereon which, if executed by a computing platform, are adapted to direct said computing platform to;

select a first specified number of occurrences of a symbol string based, at least in part, on a first estimated probability of said selected symbol string, said symbol string being selected from a portion of data to be encoded;

generate a first symbol string code indicative of a first length of data containing said first specified number of occurrences;

determine a first compressed data code based, at least in part, on said first symbol string code;

update said estimated probability;

select a second specified number of occurrences of said symbol string based, at least in part, on said updated estimated probability;

generate a second symbol string code indicative of a second length of data containing said second specified number of occurrences;

determine a second compressed data code based, at least in part, on said second symbol string code.

9. The article of claim 8, wherein said instructions, if executed by said computing platform, are further adapted to direct said computing platform to:

generate a third symbol string code indicative of a pattern of occurrences of said selected symbol string in said first length of data; and

combine said first and third symbol strings into a first compressed data code.

10. The article of claim 9, wherein said instructions, if executed by said computing platform, are further adapted to direct said computing platform to:

generate a fourth symbol string code indicative of a pattern of occurrences of said selected symbol string in said second length of data; and

combine said second and fourth symbol strings into a second compressed data code.

11. The article of claim 8, wherein said instructions, if executed by said computing platform, are further adapted to direct said computing platform to update said estimated probability based, at least in part, on an actual number of occurrences of said selected symbol string.

12. The article of claim of 8, wherein said first or further specified number of occurrences is constrained by maximum and minimum numbers of occurrences.

13. The article of claim 8, wherein said instructions, if executed by said computing platform, are further adapted to direct said computing platform to update said estimated probability by applying a filter to at least a previous estimated probability of occurrence of said selected symbol string.

14. The article of claim 8, wherein said instructions, if executed by said computing platform, are further adapted to direct said computing platform to:

partition a data set into one or more blocks of data;

select a block of data to compress; and

generate a compressed data code based on said selected block of data.

15. An apparatus comprising:

a memory to store uncompressed data; and

an encoder, said encoder being adapted to;

select a first specified number of occurrences of a symbol string based, at least in part, on an estimated probability of said selected symbol string, said symbol string being selected from a portion of data to be encoded;

generate a first symbol string code indicative of a first length of data containing said specified number of occurrences;

determine a first compressed data code based, at least in part, on said first symbol string code;

update said estimated probability;

select a second specified number of occurrences of said symbol string based, at least in part, on said updated estimated probability;

generate a second symbol string code indicative of a second length of data containing said second specified number of occurrences; and

determine a second compressed data code based, at least in part, on said second symbol string code.

16. The apparatus of claim 15, wherein said encoder is further adapted to:

generate a third symbol string code indicative of a pattern of occurrences of said selected symbol string in said first length of data; and

combine said first and third symbol strings into a first compressed data code.

17. The apparatus of claim 16, wherein said encoder is further adapted to:

generate a fourth symbol string code indicative of a pattern of occurrences of said selected symbol string in said second length of data; and

combine said second and fourth symbol strings into a second compressed data code.

18. The apparatus of claim 15, wherein said encoder is further adapted to update said estimated probability based, at least in part, on an actual number of occurrences of said selected symbol string.

19. The apparatus of claim of 15, wherein said first or second specified number of occurrences is constrained by maximum and minimum numbers of occurrences.

20. The apparatus of claim 15, wherein said encoder is further adapted to update said estimated probability by applying a filter to at least a previous estimated probability of occurrence of said selected symbol string.

21. A method comprising:

receiving a first symbol string code associated with a first specified number of occurrences of a symbol string, said first specified number being selected based, at least in part, on an estimated probability of said selected symbol string;

receiving a second symbol string code associated with a second specified number of occurrences of said symbol string, said second specified number being selected based, at least in part, on an update of said estimated probability; and

decoding at least a portion of data based, at least in part, on said first and second specified numbers.

22. An apparatus comprising:

a decoder, said decoder being adapted to;

receive a first symbol string code associated with a first specified number of occurrences of a symbol string, said first specified number being selected based, at least in part, on an estimated probability of said selected symbol string;

receive a second symbol string code associated with a second specified number of occurrences of said symbol string, said second specified number being selected based, at least in part, on an update of said estimated probability; and

decode at least a portion of data based, at least in part, on said first and second specified numbers to provide uncompressed data; and

a memory to store said uncompressed data.