Design and Implementation of LZW Data Compression Algorithm

Design and Implementation of LZW Data Compression Algorithm

• 1.
  International Journal ofInformation Sciences and Techniques (IJIST) Vol.2, No.4, July 2012 DOI : 10.5121/ijist.2012.2407 71 Design and Implementation of LZW Data Compression Algorithm Simrandeep kaur, Student1 ; V.Sulochana Verma ,Project Consultant2 Academic and Consultancy Services Division C-DAC Mohali, Punjab India Email: simrandeepkaur25@yahoo.com1; Email: suchivlsi@gmail.com2 Abstract LZW is dictionary based algorithm, which is lossless in nature and incorporated as the standard of the consultative committee on International telegraphy and telephony, which is implemented in this paper. Here, the designed dictionary is based on content addressable memory (CAM) array. Furthermore, the code for each character is available in the dictionary which utilizes less number of bits (5 bits) than its ASCII code. In this paper, LZW data compression algorithm is implemented by finite state machine, thus the text data can be effectively compressed. Accurate simulation results are obtained using Xilinx tools which show an improvement in lossless data compression scheme by reducing storage space to 60.25% and increasing the compression rate by 30.3%. Keywords Compression rate, LZW codes and Binary text. 1. Introduction Data compression is often referred to as coding, where coding is general term showing any special representation of data which satisfies a given need. Information theory is defined as the study of efficient coding. Data compression may be viewed as a branch of information theory in which the primary objective is to minimize the amount of data to be transmitted. Data compression has an important role in the area of transmission and storage. It plays a key role in information technology. The reduction of redundancies in data representation in order to decrease data storage requirement is defined as data compression. It used less usage of resources such as memory space or transmission capacity. Data compression is classified as lossless and lossy compression. Lossless compression is used for text and lossy compression for image. In 1980, Terry Welch invented LZW algorithm which became the popular technique for general- purpose compression systems. It was used in programs such as PKZIP as well as in hardware devices. Lempel-Ziv-Welch proposed a variant of LZ78 algorithms, in which compressor never outputs a character, it always outputs a code. To do this, a major change in LZW is to preload the
• 2.
  International Journal ofInformation Sciences and Techniques (IJIST) Vol.2, No.4, July 2012 72 dictionary with all possible symbols that can occur. LZW compression replaces string of characters with codes. LZW algorithm is a lossless data compression algorithm which is based on dictionaries [1]. This LZW compressor maintains records with characters that have been read from a file to be compressed. Each character is represented by an index number in the dictionary. In this paper, we proposed a improve scheme for data compression. By utilizing, content access memory dictionaries are built in the proposed system. Each character in dictionary is replaced with a code which is less number of bits than its ASCII code. The proposed LZW algorithm is evaluated by finite state machine technique in VHDL. This paper is organized as follow in section 2 an introduction to LZW algorithm is explained; in section 3, LZW data compression algorithm using finite state machine (FSM) is described. In section 4 experiments and results are shown. Finally conclusion is exposed in section 5. 1.1. Data Compression Model The block diagram of data compression model is described in figure 1. Input data Reduction Reduction of entropy Entropy encoding Compressed Data Figure 1: Data compression model A data compression model consists of three major stages which are redundancy, reduction in entropy and entropy encoding. 2. Data Compression Algorithm: LZW (Lempel-Ziv Welch) Algorithm There are many algorithms which have been used for data compression like Huffman and Lempel- Ziv-Welch (LZW), arithmetic coding.LZW algorithm is the most popular algorithm. LZW algorithm is just like a greedy approach and divides text into substrings. Like the LZW algorithm proposed in [2]. LZW algorithm has both compression and decompression techniques which is explained as below. 2.1.LZW Compression Algorithm LZW compression algorithm is dictionary based algorithm which always output a code for a character. Each character has a code and index number in dictionary. Input data which we want to
• 3.
  International Journal ofInformation Sciences and Techniques (IJIST) Vol.2, No.4, July 2012 73 compress is read from file. Initially data is entered in buffer for searching in dictionary to generate its code. If there is no matching character found in dictionary. Then it will be entered as new character in dictionary and assign a code. If character is in dictionary then its code will be generate. Output codes have less number of bits than input data. This technique is useful for both graphics images and digitized voice. String j, char c; j- get input character while (there is still input character) ch- transfer input string to ch . if (ch is in dictionary) Generate its codeword; else update ch and get next character to ch and again search data in dictionary; if ( it is not present in dictionary ) then add that string to dictionary; end if; Compression example: consider a string “BAABAABB” is given to LZW algorithm. Figure 2 shows the steps done by LZW to generate the output code is “1211211C”. In following example when input string (BAABAABBC) is given as a text to LZW compression algorithm. Initially every single character will save in buffer. When ‘B’ is move to buffer “parse string” then it will replace by 1. Character has its own ASCII code of 7 bit. In case of B, it has 65 as ASCII code. But in dictionary it will replace by 1. So, less number of bits will be used to represent character. Similarly, AA will move forward and generating its code which is also fewer bits than original. BAA is saved in buffer its code is generated from both AA and B’s codeword that is defined as 12. At last when full string has been searched in dictionary then its output will be generated as 1211211C. BAABAABBC 1 B B B BAABAABB C 1 2 B AA 1, AA AA AABAABBC 1 2 12 B AA BAA 1, 2, BAA BAA BAABBC 1 2 12 11C B AA BAA BBC 121211C BBC BBC 121211C COMPRESSED DATA PARSE STRING Figure 2: Example of LZW algorithm
• 4.
  International Journal ofInformation Sciences and Techniques (IJIST) Vol.2, No.4, July 2012 74 2.2.LZW Decompression Algorithm In LZW decompression algorithm, it needs to take the stream of code output from the compression algorithm, and use them to exactly recreate the input stream. Decompression algorithm is shown as: ch = output code while (there is still data to read) code =get input character; if (code is not in the dictionary) entry =get translation of code; else entry=get translation of output code; output entry; ch =first character in entry add output code + c to the dictionary output code = code; In decompression algorithm, code will be searched in dictionary and its character will be output. 3. Implementation of LZW Algorithm The proposed finite state machine diagram of LZW algorithm is shown in figure 3. S0 IDLE S1 IDLE1 S2 FILL BUFFER S3 READ STRING S4 WAIT S5 SEARCH IN DICT S6 WRITE TO QUEUE S8 S9 S7 WAIT FOR BUS ACK S10 INSERT CHARCTER S11 SEARCH ITS CODEWORD S12 GENERATE CODEWORD S8 NEW ENTRY S9 GENERATE CODEWORD Figure 3: Finite state machine Diagram of LZW algorithm
• 5.
  International Journal ofInformation Sciences and Techniques (IJIST) Vol.2, No.4, July 2012 75 LZW algorithm initially has idle state. New character has been added to dictionary when no longer match will found in search process. LZW algorithm is execute state S8 for performing adding operation in dictionary. Dictionary is based on content access memory technique which has both content as well as code in it. Content access memory is special type of memory used for fast accessing data from memory. In the proposed system, initialization of compression signal is done before to perform LZW algorithm. Input data is entered to LZW algorithm through file. The proposed algorithm shifted whole input data to buffer which is defined in S3 state. Every single character has been searched in content access memory. If match signal is ‘1’ then character was found in dictionary. Then code is transmitted to output buffer “de11”. LZW decompressor must construct same steps like compressor. Decompressor has reviewed same process since it is possible to have input codes for searching in dictionaries to recreate its original string. Individual character’s code can be also viewed in dictionary. Table 1: Specifications of FSM state for LZW Algorithm 3.1.Improvement of the dictionary storage method LZW algorithm is mainly used for compressing character but not numeric. Every character has ASCII code which is of 7 bits. But in our proposed algorithm we have to replace character with 5 bit code in dictionary to improving data compression rate. 4. Experimental Results LZW Compression algorithm is modelled in VHDL. The syntax of the RTL design is checked by using Xilinx tool. State Description S0 idle Initial state reset the system S1 idle1 Initialization of signal S2Fill buffer Transfer text from file to buffer S3Read string Read character by character for searching S4 wait For waiting S5 search in dict For searching in dictionary by signal character S6Write to queue Save output to output buffer S7 wait for ack Wait for Bus acknowledge S8New Entry Adding new entry S9Generate codeword To generate codes S10 Insert single character S11search its codeword Check in dictionary S12 generate codeword Display codeword Decompression For performing decompression
• 6.
  International Journal ofInformation Sciences and Techniques (IJIST) Vol.2, No.4, July 2012 76 4.1.Simulation Results In the proposed work, the simulations results are done using Xilinx ISE Simulator. Simulation results show an improvement in lossless data compression scheme. In addition to this, the proposed technique results in reduced storage space by 60.25% and increased compression rate by 30.3%. 4.2.LZW Compressor Result Figure 4 shows that input is given to LZW Compressor through text file. “Connect the input to logic one & two & three++*”string is entered to it. Input string having collection of special characters, alphabets. Whole text will transfer to buffer “data read “when data_write=1, load=1, clear=1.Rd_b=0, wr_b=1, data_write=0 and lzw_search=1 are given to start searching process to find longest match in content access memory arrays. There are two main counters which are used for searching process. “Count1” is used for searching character in dictionary. If character is present in dictionary then its code is saved in other buffer that is “de11”. “Count” buffer is shifted to next value and start to point next character present in input data. All searched characters will save in “check” buffer. Once the content of check buffer is equal to content of“data read” buffer then searching process indicate to completed and their codes will save in “de11” buffer which is shown in figure5compressed output isgenerated through file shown in figure 7. Input text – connect the input to logic one & two & three. Outputtext-12114514615730171419514251522372152315551482 Figure 4: Enter data through file which we want to compress Given Input text – connect the input to logic one & two & three
• 7.
  International Journal ofInformation Sciences and Techniques (IJIST) Vol.2, No.4, July 2012 Input is given by text file which is input as a collection of characters in one clock cycle. Figure 5: Searching process Simulation for LZW Compression algorithm LZW compression algorithm .then it is transmitted to 119 bits and cloc ps. Figure 6: Complete data compression process International Journal of Information Sciences and Techniques (IJIST) Vol.2, No.4, July 2012 is given by text file which is one of the data type of vhdl language. File is used for giving input as a collection of characters in one clock cycle. : Searching process (Searching each character from dictionary) for LZW Compression algorithm observed on Xilinx tool. When 350 bits entered to LZW compression algorithm .then it is transmitted to 119 bits and clock rate for simulation is 493 Figure 6: Complete data compression process International Journal of Information Sciences and Techniques (IJIST) Vol.2, No.4, July 2012 77 is used for giving from dictionary) When 350 bits entered to k rate for simulation is 493
• 8.
  International Journal ofInformation Sciences and Techniques (IJIST) Vol.2, No.4, July 2012 Figure 7 Output text-121145146157301714 4.3. RTL view of LZW Compressor Figure This RTL view shows the signal Reset, clock, start_compression used wr_b, rd_b are signals used for dictionary. The signal description of this International Journal of Information Sciences and Techniques (IJIST) Vol.2, No.4, July 2012 Figure 7: Compressed output generate on file 12114514615730171419514251522372152315551482 iew of LZW Compressor Figure-8: RTL view of LZW Compressor signals which are used for proposed LZW data compression algorithm compression used for initialization of data compression. Load, _b are signals used for buffer in LZW algorithm. Search_lzw is for searchi ption of this proposed algorithm is shown in table 2. International Journal of Information Sciences and Techniques (IJIST) Vol.2, No.4, July 2012 78 LZW data compression algorithm. oad, data_write, searching data in
• 9.
  International Journal ofInformation Sciences and Techniques (IJIST) Vol.2, No.4, July 2012 79 4.3.1. Signal description of LZW Compressor Table 2: Input/output signals with Remarks Name Description Reset To reset Clock Provide clock Start_compression Signal for start compression Data_write Signal for write data Load For data load in buffer Clear Clear buffer Wr_b Signal for write and read Rd_b Signal for write and read Search_lzw For searching Add_new_entry For adding new data Data_in Enter value 4.3.2. Analysis of compression rate with different bit size Table 3: Analysis of compression rate Word Size Compression Rate Compressed Bit Size Original Bit Size 4 53.125 17 28 10 33.75 27 70 38 30.11 95 265 50 29.75 119 350 4.3.3.Verification and Synthesis For system verification, we successfully execute proposed LZW algorithm. Test case for finite state machine is generated in VHDL. The synthesis result of LZW compression algorithm is summarized in table 4. The synthesis report shows device utilization summary. Table 4: Device Utilization Summary Number of Slices 3606 out of 6144 58% Number of Slice Flip Flops 4097 out of 12288 33% Number of 4 input LUTs 4190 out of 12288 34% Number of IOs: 30 Number of bonded IOBs: 30 out of 240 12% IOB Flip Flops: 1
• 10.
  International Journal ofInformation Sciences and Techniques (IJIST) Vol.2, No.4, July 2012 80 4.4.Comparison of the Results with the Previous Work The results achieved are compared with the reference work is shown in table 5. It is concluded that enhancement in the performance of LZW Data Compression algorithm by using less number of bits than their ASCII code, utilizing content addressable memory arrays. Thus the text data can be effectively compressed and compared with previous work. In addition to this, the proposed research work, results show the reduction in storage space by 60.25% and increase the compression rate by 30.3%. Comparison of this work with previous work is described in table 5 shown as: Table 5: Comparison between this research works with previous work Input Size Compressed bit with previous work Compressed bit with Improved LZW 112 104 70 144 96 90 152 100 95 184 156 115 360 296 225 5. Conclusions In order to get better compression rate, the proposed dictionary based LZW algorithm can replace their codes with 5 bits instead of 7 bits ASCII code. LZW algorithm is evaluated by finite state machine technique. With this technique we have observed that storage space is reduced up to 60.25% and compression rate improved up to 30.3%.Weanalyze compression rate with different number of input bits on Xilinx tool. 6. References [1] Parvinder Singh,ManojDuhan and Priyanka(2006)“Enhancing LZW Algorithm to Increase Overall Performance”, Annual IEEE Indian Conference,pp1-4. [2] Ming-Bo Lin, Jang-Feng Lee, G. E. Jan,( 2006)“ALossless Data Compression and Decompression Algorithm and Its Hardware Architecture” VLSI IEEE Transactions ,Vol.14,pp925-936. [3] YiCao, Guoging Wu, Huawei Wang,( 2011) “A Smart Compression Scheme for GPU-Accelerated Volume Rendering of Time-Varying Data.” Virtual Reality and Visualization (ICVRV) conference.pp205-210 [4] Guolv.Tan, Yujun Wang,( 2009) “A Compression Error and Optimize Compression Algorithm for vector Data.”, Environmental Science and Information application technology,vol.2,pp522-525. [5] Parvinder Singh, Sudhir Batra, and HR Sharma,( 2005) “Evaluating the performance of message hidden in 1st and 2nd bit plane", WSEAS Trans. on Information Science an Applications, vol 2, pp 1220-1227. [6] Ozsoy, A. Swany, “LZSS Lossless Data Compression on CUDA”,( 2011) “IEEE international conference on Cluster computing (CLUSTER),pp403-411. [7] Mateosian , R, “Introduction to Data Compression” (1996), vol.16. [8] Henriques and N. Ranganathan,(2005) “A parallel architecture for data compression,” IEEE Symp .on parallel and distributed processing Parallel. Distribution, pp260-266.
• 11.
  International Journal ofInformation Sciences and Techniques (IJIST) Vol.2, No.4, July 2012 81 [9] Huan Zhang, Xiao-ping Fan, Shao-qiang Liu Zhi Zhong “Design and Realization of Improved LZW Algorithm for Wireless Sensor Networks”,International Conference on Information Science and Technology,pp671-675. 6. Bibliographies Simrandeep Kaur received the B.Tech degree in Computer Science Engineering from the Punjab technical university, Punjab in 2010, and pursuing M.Tech degree in VLSI Design from Centre of Development and Advance Computing Mohali, Punjab .Currently, she is doing her thesis work on data compression technique. Her topic of interest is data compression, security system, data structure and embedded system.Email- simrandeepkaur25@yahoo.com VemuSulochana has obtained her Bachelor of Technology degree in Electronics & Communication Engineering from JNTU Kakinada and Master of Technology degree in VLSI Design Automation & Techniques from NIT, Hamirpur in 2004 and 2009 respectively. She is working as a Project consultant at C-DAC, Mohali to conduct innovative research in the area of VLSI design. Her research interests include low power VLSI design, Computer-aided design (CAD), Digital & Analog VLSI Desig n. She enjoys teaching VLSI design, Device modelling, Low-power VLSI Design, Analog & mixed sign al VLSI Design. Email-id is suchivlsi@gmail.com