Open Access Open Access  Restricted Access Subscription or Fee Access

BITSTREAMS Compression of RLE with Bitstuffing

J. Satheesh Kumar, G. Saravana Kumar, R.S. Madhunica, K. Prakash, E. Deepa, K. Rajesh

Abstract


Recent technological breakthrough in high speed processing units and communication devices have enabled the development of high data compression schemes. This paper presents a modified scheme for Run length encoding (RLE). Run length encoding algorithm performs compression of input data based on sequences of identical values. RLE is having some limitations and they have been highlighted and discussed in detail in this paper. In RLE largest number of sequences may increase the number of bits to represents the length of each run, which may increase the size of memory stack which may results in performance degradation. For n-bit run it requires 2n memory stack. If run is greater than n bits we require 2n+1 memory stack to store the run value. An efficient coding technique, Bitstuffing has been suggested in this paper. A new bit different from the original sequence is added in between reduces the repeat length, thereby with the same stack we can represent length as well. This technique is described using VHDL and is implemented on Saprtan3 FPGA


Keywords


Bit Stuffing, Compression, Memory Stack and Run Length Encoding (RLE)

Full Text:

PDF

References


new Data Compression Algorithm for Wireless Sensor Network,‖ in Proc Third International Conference on Sensor Technologies and Applications, 2009

James A. Storer, ―Data Compression methods and theory Computer Science Press, 1988

C. E. Shannon, ―A mathematical theory of communication,‖ Bell Syst. Tech. J., vol. 27, no. 3 and 4, pp. 379–423, July and Oct. 1948.

S. Tate. Complexity Measures. In K. Sayood, editor, Lossless Compression Handbook, pages 35–54. Academic Press, 2003.

N. Faller. An Adaptive System for Data Compression. In Record of the 7th Asilomar Conference on Circuits, Systems, and Computers, pages 593–597. IEEE, 1973.

S. Hauck, Z. Li, and E. Schwabe, “Configuration compression for the Xilinx XC6200 FPGA,” IEEE Trans. on CAD, vol. 18, no. 8, pp. 1107–1113, 1999.

D. A. Huffman, “A method for the construction of minimum-redundancy codes,” Proceedings of the IRE, vol. 40, no. 9, pp. 1098–1101, 1952.

A. Moffat, R. Neal, and I. H. Witten, “Arithmetic coding revisited,” in Proc. of Data Compression Conference, 1995, pp. 202–211.

A. Khu, Xilinx FPGA Configuration Data Compression and Decompression, WP152 ed., Xilinx, 2001.

M. Huebner, M. Ullmann, F. Weissel, and J. Becker, “Real-time configuration code decompression for dynamic FPGA self-reconfiguration,” in Proc. of International Parallel and Distributed Processing Symposium, 2004, pp. 138–143.

R. Stefan and S. Cotofana, “Bitstream compression techniques for Virtex 4 FPGAs,” in Proc. of International Conference on Field Programmable Logic and Applications, 2008, pp. 323–328.

J. Nikara, S. Vassiliadis, J. Takala, and P. Liuha, “Multiple-symbol parallel decoding for variable length codes,” IEEE Trans. on VLSI, vol. 12, no. 7, pp. 676–685, July 2004.


Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.