Run-length coding extensions for high performance hardware data compression

Access Full Text

Run-length coding extensions for high performance hardware data compression

For access to this article, please select a purchase option:

Buy article PDF
£12.50
(plus tax if applicable)
Add to cart
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)
Add to cart

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IEE Proceedings - Computers and Digital Techniques — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

IEE
Published

The optimal placement of a run-length coding extension to a dictionary-based lossless data compression algorithm is investigated. A hardware implementation of the proposed extension is completed and integrated into an existing design. The new hardware is benchmarked against commercially available software and hardware compression methods. Run-length coding replaces repetitive, identical sequences of a symbol with a pair formed by a code indicating the repeating symbol plus a code indicating the length or number of repetitions that occurred. This method of coding is of limited use for general compression due to its relatively poor performance. However, good results can be achieved when used as an extension to a general lossless data compression algorithm where it can improve compression, targeting the coding of repetitive data formats such as zeroes in memory or fax pages or a uniform colour in image backgrounds. It is shown that the run-length coding method can be extended to support more complex repeating patterns with little extra cost in terms of hardware or speed but providing significant superior compression performance.

Inspec keywords: computational complexity; data compression; encoding

Other keywords: dictionary-based lossless data compression; coding; repetitive data formats; run-length coding extensions; high performance hardware data compression

Subjects: Information theory; Computational complexity; Data handling techniques; Codes

References

    1. 1)
      • ‘AHA3580 80 Mbytes/s ALDC Data Compression Coprocessor IC’, Product Brief, Advanced Hardware Architectures Inc, 2635 Hopkins Court, Pullman, WA, 2001.
    2. 2)
      • M. Nelson . (1991) The Data Compression Book.
    3. 3)
      • ‘AHA3211 40 Mbytes/s DCLZ Data Compression Coprocessor IC’, Product brief, Advanced Hardware Architectures Inc, 2635 Hopkins Court, Pullman, WA, 1997.
    4. 4)
      • R.B. Tremaine , P.A. Franaszek , J.T. Robinson , C.O. Schulz , T.B. Smith , M.E. Wazlowski , P.M. Bland . IBM Memory Expansion Technology (MXT). IBM J. Res. Dev. , 2 , 271 - 285
    5. 5)
      • VanDuine: ‘Integrated Storage’ Technical Paper, IBM Corporation, 3605 North Highway 52, Rochester, MN, 2000.
    6. 6)
      • J. Ziv , A. Lempel . Compression of Individual Sequences Via Variable Rate Coding. IEEE Trans. Inf. Theory , 530 - 536
    7. 7)
      • Núñez, J.L., and Jones, S.: ‘Gbit/Second Lossless Data Compression Hardware’, Accepted for publication at IEEE Trans. VLSI Syst..
    8. 8)
    9. 9)
    10. 10)
      • ‘How LZS Compression Works’, Application Note, Hi/fn Inc, 750 University Avenue, Los Gatos, CA, 1996.
    11. 11)
      • ‘9600 Data Compression Processor’, Data Sheet, Hi/fn Inc, 750 University Avenue, Los Gatos, CA, 1999.
    12. 12)
      • ‘Data Compression AIM for the Cisco 2600 Series’, Cisco Product Catalogue, Cisco Systems Inc, 170 West Tasman Drive, San Jose, CA, December 2000.
    13. 13)
      • J. Ziv , A. Lempel . A Universal Algorithm for Sequential Data Compression. IEEE Trans. Inf. Theory , 337 - 343
    14. 14)
      • D.C. Cressman . Analysis of Data Compression in the DLT2000 Tape Drive. Digit. Tech., J. , 2 , 62 - 71
    15. 15)
      • M. Kjelso , M. Gooch , S. Jones . Performance Evaluation of Computer Architectures with Main Memory Data Compression. J. Syst. Archit. , 571 - 590
    16. 16)
      • D.A. Huffman . A Method for the Construction of Minimum Redundancy Codes. Proc. IRE , 1098 - 1101
    17. 17)
      • B. Jung , W.P. Burlesson . Performance Optimization of Wireless Local Area Networks Through VLSI Data Compression. Wirel. Netw. , 27 - 39
    18. 18)
      • P.A. Franaszek , P. Heidelberger , D.E. Poff , J.T. Robinson . Algorithms and Data Structures for Compressed-memory Machines. IBM J. Res. Dev. , 2 , 245 - 257
    19. 19)
      • Mogul, J.C., Douglis, F.: `Potential Benefits of Delta Encoding and Data Compression for HTTP', Proc. ACM SIGCOMM Symp., Cannes, France, 16–18 September 1997.
    20. 20)
      • D.J. Craft . A Fast Hardware Data Compression Algorithm and Some Algorithmic Extensions. IBM J. Res. Dev. , 6 , 733 - 745
    21. 21)
      • ‘Primer: Data Compression Lempel-Ziv (DCLZ)’, Application Note, Advanced Hardware Architectures Inc, 2635 Hopkins Court, Pullman, WA, 1996.
    22. 22)
      • Cheng, J.M., Duyanovich, L.M.: `Fast and Highly Reliable IBMLZ1 Compression Chip and Algorithm for Storage', Proc. Hot chips Symp., Stanford, CA, 14–15 August 1995, p. 155–165.
    23. 23)
      • K. Dickson . (2000) Cisco IOS Data Compression.
    24. 24)
      • Bloom, C.: ‘Solving the Problems of Context Modelling’, Available from: http://www.data-compression.info/Algorithms/AdaptiveModel/adaptivemodel.htm, 1998.
    25. 25)
      • Núñez, J.L., Jones, S.: `Lossless Data Compression Programmable Hardware for High-Speed Data Networks', Proc. IEEE Int. Conf. on Field-programmable technology (FPT), 16–18th December 2002, p. 290–293.
    26. 26)
      • ‘Data Compression Analysis in Data Communications’, Application Note, Hi/fn Inc, 750 University Avenue, Los Gatos, CA, 1997.
    27. 27)
      • T.C. Bell , J.G. Cleary , I.H. Witten . (1990) Text Compression.
    28. 28)
      • J. Cleary , I. Witten . Data Compression Using Adaptive Coding and Partial String Matching. IEEE Trans. Commun. , 4 , 396 - 402
    29. 29)
      • Lee, J.S., Hong, W.K., Kim, S.D.: `Design and Evaluation of a Selective Compressed Memory System', Proc. IEEE Int. Conf. on Computer design, Austin, TX, 10–13 October 1999, p. 184–191.
http://iet.metastore.ingenta.com/content/journals/10.1049/ip-cdt_20030750
Loading

Related content

content/journals/10.1049/ip-cdt_20030750
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading