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

• US 7,786,903 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): Barnie, Rexford N
• Assistant Examiner(s): Lauture, Joseph
• Application Number:
  US12/246,357
• Publication Number:
  US 20100085219A1
• Time in Patent Office: 694 Days
• Field of Search: 341/52, 341/51, 341/87, 341/106, 707/100, 708/203
• US Class Current: 341/52
• 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:

determining a length of data containing a specified number of occurrences of a selected symbol string;

generating a first symbol string code indicative of the determined length;

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 to provide a compressed data code.

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

3. The method of claim 1, wherein a final occurrence of said selected symbol string is at a final position in said determined length of data.

4. The method of claim 1, and further comprising encoding beyond said length of data if there are fewer than said specified occurrences in said length of data.

5. The method of claim 1, and further comprising encoding a plurality of lengths of data into an associated plurality of compressed data codes.

6. The method of claim 5, and further comprising generating the first and second symbol string code taking account of a number of known symbol strings to be skipped.

7. The method of claim 1, wherein an order of repeated symbol strings comprises one or more of a predetermined order, a dynamically created order based upon previously used symbol strings, an order based upon a frequency of symbol strings in a generalized set and/or an order based upon a frequency of symbol strings in a data set to be compressed.

8. 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.

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

10. 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.

11. 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;

determine a length of data containing a specified number of occurrences of a selected symbol string;

generate a first symbol string code indicative of the determined length;

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 to provide a compressed data code.

12. The article of claim 11, wherein said instructions, if executed by said computing platform, are further adapted to direct said computing platform to encode a plurality of lengths of data into an associated plurality of compressed data codes.

13. The article of claim 12, wherein said instructions, if executed by said computing platform, are further adapted to generate the first and second symbol string code taking account number of known symbol strings to be skipped.

14. The article of claim 11, wherein said instructions, if executed by said computing platform, are further adapted to direct said computing platform to generate said first symbol string code by application of an arithmetic, Huffman, Golomb, Huffman/Golomb hybrid or adaptive encoding scheme.

15. The article of claim 11, 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.

16. An apparatus comprising:

a memory to store uncompressed data; and

an encoder, said encoder being adapted to;

determine a length of data from said uncompressed data containing a specified number of occurrences of a selected symbol string;

generate a first symbol string code indicative of the determined length;

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 to provide a compressed data code.

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

partition a data set of said uncompressed data 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.

18. The apparatus of claim 16, wherein said encoder is further adapted to encode a plurality of lengths of data into an associated plurality of compressed data codes.

19. The apparatus of claim 18, wherein said encoder is further adapted to take account of a number of known symbol strings to be skipped.

20. The apparatus of claim 16, 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.

21. An apparatus comprising:

a decoder, said decoder being adapted to;

partition a compressed data code into first and second symbol string codes,

associate said first symbol string code with a length of data containing a specified number of occurrences of a selected symbol string, and

associate said second symbol string with a pattern of occurrences of said selected symbol string in said length of data,

provide uncompressed data based, at least in part, on said pattern of occurrences and said length of data; and

a memory to store said uncompressed data.