Mode switched adaptive combinatorial coding/decoding for electrical computers and digital data processing systems

• US 7,864,086 B2
• Filed: 10/06/2008
• Issued: 01/04/2011
• 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): Lauture, Joseph
• Application Number:
  US12/246,426
• Publication Number:
  US 20100085221A1
• Time in Patent Office: 820 Days
• Field of Search: 341/107, 341/106, 341/65, 341/67, 341/50, 341/51, 382/233, 382/234, 382/239, 382/247, 382/303, 382/304, 348/387
• 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 adaptive combinatorial encoding with either specified occurrences or specified data length 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 symbol string to encode from a portion of data to encode;

determining an estimated probability of said selected symbol string; and

selecting an encoding technique for encoding at least part of said selected symbol string from among two or more encoding techniques based, at least in part, on said estimated probability, said encoding techniques include at least one combinatorial encoding technique, wherein if a combinatorial encoding technique is selected for encoding said at least part of said symbol string, the method further comprises;

generating a first symbol string code;

generating a second symbol string code indicative of a pattern of occurrences of said selected symbol string; and

combining said first and second symbol string codes into a compressed data code.

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

selecting from among encoding techniques including Huffman and Golomb encoding techniques if a combinatorial encoding technique is not be used for encoding said selected symbol string.

3. The method of claim 1, wherein said generating said first symbol string code comprises:

determining a selected length of data from said portion of data; and

determining a number of occurrences of said selected symbol string in said selected length of data,

and wherein said second symbol string code is indicative of said number of occurrences.

4. The method of claim 3, and further comprising selecting said selected length of data based, at least in part, on said probability.

5. The method of claim 1, wherein said generating said first symbol string code comprises:

determining a specified number of occurrences of said selected symbol string in said selected data length; and

determining a length of data of said selected portion containing said specified number of occurrences of said selected symbol string,

and wherein said second symbol string code is indicative of said length of data.

6. The method of claim 5, and further comprising selecting said specified number of occurrences based, at least in part, on said probability.

7. The method of claim 1, wherein said selected symbol string comprises binary symbols.

8. An article comprising:

a storage medium comprising machine-readable instructions stored thereon which are executable by a computing platform to;

select a symbol string to encode from a portion of data to encode;

determine an estimated probability of said selected symbol string;

select an encoding technique for encoding at least part of said selected symbol string from among two or more encoding techniques based, at least in part, on said estimated probability, said encoding techniques include at least one combinatorial encoding technique; and

if a combinatorial encoding technique is selected for encoding said at least part of said symbol string said instructions;

generate a first symbol string code;

generate a second symbol string code indicative of a pattern of occurrences of said selected symbol string; and

combine said first and second symbol string codes into a compressed data code.

9. The article of claim 8, wherein said instructions are further executable by said computing platform to:

select from among encoding techniques including Huffman and Golomb encoding techniques if a combinatorial encoding technique is not be used for encoding said selected symbol string.

10. The article of claim 9, wherein said instructions are further executable by said computing platform to:

determine a specified number of occurrences of said selected symbol string in said selected data length; and

determine a length of data of said selected portion containing said specified number of occurrences of said selected symbol string,

and wherein said second symbol string code is indicative of said length of data.

11. The article of claim 10, wherein said instructions are further executable by said computing platform to select said specified number of occurrences based, at least in part, on said probability.

12. The article of claim 8, wherein said instructions are further executable by said computing platform to:

determine a selected length of data from said portion of data; and

determine a number of occurrences of said selected symbol string in said selected length of data,

and wherein said second symbol string code is indicative of said number of occurrences.

13. The article of claim 8, wherein said selected symbol string comprises binary symbols.

14. An apparatus comprising:

a memory to store uncompressed data; and

an encoder, said encoder being adapted to;

select a symbol string to encode from a portion of data to encode;

determine an estimated probability of said selected symbol string;

select an encoding technique for encoding at least part of said selected symbol string from among two or more encoding techniques based, at least in part, on said estimated probability, said encoding techniques include at least one combinatorial encoding technique, wherein if a combinatorial encoding technique is selected for encoding said at least part of said symbol string said instructions, said encoder is further adapted to;

generate a first symbol string code;

generate a second symbol string code indicative of a pattern of occurrences of said selected symbol string; and

combine said first and second symbol string codes into a compressed data code.

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

select from among encoding techniques including Huffman and Golomb encoding techniques if a combinatorial encoding technique is not be used for encoding said selected symbol string.

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

determine a selected length of data from said portion of data; and

determine a number of occurrences of said selected symbol string in said selected length of data,

and wherein said second symbol string code is indicative of said number of occurrences.

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

determine a specified number of occurrences of said selected symbol string in said selected data length; and

determine a length of data of said selected portion containing said specified number of occurrences of said selected symbol string,

and wherein said second symbol string code is indicative of said length of data.

18. The apparatus of claim 17, wherein said encoder is further adapted to select said specified number of occurrences based, at least in part, on said probability.

19. A method comprising:

receiving an encoded symbol string;

determining which encoding technique of a plurality of encoding techniques is used to encode said encoded symbol string, said plurality of encoding techniques including at least one combinatorial encoding technique, wherein said encoding technique is selected based, at least in part, on a probability associated with said symbol string; and

decoding at least a portion of said encoded symbol string based, at least in part, on said determined encoding technique, wherein if a combinatorial encoding technique is used to encode said encoded symbol string said decoding further comprising;

identifying first and second symbol string codes in a compressed data code in said encoded symbol string; and

associating a pattern of occurrences of a selected symbol string associated with at least one of said first and second symbol string codes.

20. An apparatus comprising:

a decoder, said decoder being adapted to;

determine which encoding technique of a plurality of encoding techniques is used to encode said encoded symbol string, said plurality of encoding techniques including at least one combinatorial encoding technique, wherein said encoding technique is selected based, at least in part, on a probability associated with said symbol string, and

decode at least a portion of said encoded symbol string based, at least in part, on said determined encoding technique, wherein if a combinatorial encoding technique is used to encode said encoded symbol string said decoder is further adapted to;

identify first and second symbol string codes in a compressed data code in said encoded symbol string; and

associate a pattern of occurrences of a selected symbol string associated with at least one of said first and second symbol string codes; and

a memory to store uncompressed data based, at least in part, on said decoded portion of said encoded symbol string.