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

• US 7,786,907 B2
• Filed: 10/06/2008
• Issued: 08/31/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): Mai, Lam T
• Application Number:
  US12/246,392
• Publication Number:
  US 20100085218A1
• Time in Patent Office: 694 Days
• Field of Search: 341 50- 70, 341/107, 714/784, 375/E7.13, 375/E7.202, 707/101, 707/E17.08, 707/E17.039
• US Class Current: 341/107
• 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

Abstract

Embodiments described herein may include example embodiments of a method, article and apparatus for compressing data utilizing combinatorial coding 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, at an encoder:

obtaining one or more signals representing a selected symbol string;

estimating a probability associated with the selected symbol string;

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

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

determining one or more signals representing a compressed data code based, at least in part, on said first symbol string code.

2. The method of claim 1, wherein said determining one or more signals representing said compressed data code further comprises:

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

combining said first and second symbol strings into said compressed data code.

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

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

5. The method of claim 1, wherein said specified number of occurrences is dynamically determined.

6. The method of claim 1, wherein said specified number of occurrences is predetermined.

7. The method of claim 1, wherein said generating said first symbol string code comprises applying an arithmetic, Huffman, Golomb, Huffman/Golomb hybrid or adaptive encoding scheme.

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

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

selecting at least one of said one or more blocks of data to compress; and

generating said compressed data code based, at least in part, on said selected at least one of said blocks of data.

9. An article comprising:

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

retrieve one or more signals representing a selected symbol string;

estimate a probability associated with said selected symbol string;

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

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

determine one or more signals representing a compressed data code based, at least in part, on said first symbol string code.

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

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

combine said first and second symbol strings into said compressed data code.

11. The article of claim of 9, wherein said specified number of occurrences is constrained by maximum and minimum numbers of occurrences.

12. The article of claim 9, wherein said instructions are further executable by said computing platform to generate said first symbol string code by application of an arithmetic, Huffman, Golomb, Huffman/Golomb hybrid or adaptive encoding scheme.

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

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

select at least one of said blocks of data to compress; and

generate said compressed data code based on said selected block one or more blocks of data.

14. An apparatus comprising:

a memory to store uncompressed data; and

an encoder, said encoder being adapted to;

estimate a probability associated with a selected symbol string;

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

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

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

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

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

combine said first and second symbol strings into said compressed data code.

16. The apparatus of claim of 14, wherein said specified number of occurrences is constrained by maximum and minimum numbers of occurrences.

17. The apparatus of claim 14, wherein said encoder is further adapted to generate said first symbol string code by application of an arithmetic, Huffman, Golomb, Huffman/Golomb hybrid or adaptive encoding scheme.

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

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

select at least one of said blocks of data to compress; and

generate a compressed data code based on said selected one or more blocks of data.

19. A method comprising, at a decoder:

associating one or more signals representing a compressed data code with a first symbol string code; and

associating said first symbol string code with a length of data containing a number of occurrences of a selected symbol string, wherein said number of occurrences is based, at least in part, on an estimated probability associated with said selected symbol string.

20. An apparatus comprising:

a decoder, said decoder being adapted to;

associate a compressed data code with a first symbol string code,

associate said first symbol string code with a length of data containing a number of occurrences of a selected symbol string, wherein said number of occurrences is based, at least in part, on an estimated probability associated with said selected symbol string, and

provide uncompressed data based, at least in part, on said length of data containing said number of occurrences of said selected symbol string; and

a memory to store said uncompressed data.