際際滷

際際滷Share a Scribd company logo

Huffman data compression-decompression

Download as PPTX, PDF
D
dipugovind

This document presents a selective Huffman coding scheme for efficient test vector compression. It begins with an introduction discussing the challenges of testing increasingly complex SOC designs. It then describes Huffman coding and the proposed selective Huffman coding approach, which only encodes the most frequently occurring test vectors. Experimental results show the selective Huffman scheme achieves nearly the same compression ratio as standard Huffman coding but with a simpler decoder requiring fewer logic elements.

1 of 20
Downloaded 117 times
An Efficient Test Vector Compression Scheme Using Selective Huffman Coding Under the guidance of Prof.Aarthi Presented By Dipu P 12MVD0060 Venketa Ramesh E 12MVD0062 HarshaVardhan B 12MVD0063
INTRODUCTION: A SOC based design provide several design challenges These chips are composed of several reusable intellectual property (IP) cores The volume of test data for a SOC is growing rapidly as IP cores become more complex Extreme challenges to current tools and methodologies
1/2 In present days the complexity of SOC is keep on increasing, so for testing those ICs requires huge cost Various factors of ATE are limitations to a testing technique and methodology Various techniques available for reducing the test data They are BIST and Test Data Compression
1/3 Various methods i) code based schemes ii) Linear-decompression based schemes iii) Broad cast based schemes Code Based Schemes 1) Fixed to Fixed 2) Fixed to Variable 3) Variable to fixed 4) Variable to Variable
Huffman Encoding Scheme 1/4 Building up of Huffman Tree Selective Huffman Compression Ratio 1 0010 0010 0010 0001 1100 2 0100 0100 0110 0100 1000 3 4 5 6 0010 0010 0010 0010 0100 0110 0110 0010 0111 0111 0000 0000 0010 0010 0010 0010 0110 0100 0010 0010 7 1011 0010 0100 0111 0111 Test File under consideration 8 9 10 11 12 0100 0100 0110 0111 0111 0010 0110 0010 0100 0010 0100 0010 0010 0100 0100 0110 0010 1000 1000 1111 0010 0000 0101 0101 0011
ENCODING SCHEME 2/4 0010010000100110000000101 0110100001001000110011010 1011010101011000001110000 1111000001101010101010000 SORTED TEST VECTORS HUFFMAN TREE 0010 Algorithm of Huffman Encoder Feed the Test File Divide in to set of four bits Sorting the 4-bit block descending order of their occurrence(frequency) Tree Development Encoding
3/4 Feed the Test File. Divide in to set of four bits. Sorting the 4-bit block descending order of their occurrence(frequency). Select the most frequently occurring bit sets. (Those having High Frequency). Huffman Coding For the Selected Set. Set MSB=1 for the Selected encoded bits. Set MSB=0 for unselected bit sets. Zero tag indicate no need of decompression .
4/4 Comparison Between Huffman And Selective Huffman
Huffman data compression-decompression
Huffman data compression-decompression
Huffman data compression-decompression
Huffman data compression-decompression
Huffman data compression-decompression
Huffman data compression-decompression
Selective Huffman Decoding-Look Up Table Method
1/2 RESULTS-Decoded Output and Comparison Huffman Selective Huffman Total Combinational functions 102 73 Total Registers 41 40 % of Compression= % of Compression=19.166 Decoded output for a given serial input
2/2 Total no of bits=240 Compressed bits for Huffman=178 Compressed bits for Huffman=194
CONCLUSION Importance of compression and decompression in testing field. Huffman Compression-Decompression Selective Huffman Compression-Decompression Simple-Decoder with Lesser Logic Elements. Results indicate that the proposed scheme can provide test data compression nearly equal to that of an optimum Huffman code with much less area overhead for the decoder.
REFERENCES [1] Xrysovalantis Kavousianos, Emmanouil Kalligeros, and Dimitris Nikolos Optimal Selective Huffman Coding for Test-Data Compression IEEE TRANSACTIONS ON COMPUTERS, VOL. 56, NO. 8, AUGUST 2007 [2] Abhijit Jas, Jayabrata Ghosh-Dastidar, Mom-Eng Ng, and Nur A. ToubaAn Efficient Test Vector Compression Scheme Using Selective Huffman Coding IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMSJUNE 2003. [3] J. Aerts and E. J. Marinissen, Scan chain design for test time reduction in core-based ICs, in Proc. Int. Test Conf., 1998, pp. 448457. [4] I. Bayraktaroglu and A. Orailoglu, Test volume and application time reduction through scan chain concealment, in Proc. Design Automation Conf., 2001, pp. 151155. [5] M. L. Bushnell and V. D. Agrawal, Essentials of Electronic Testing For Digital, Memory, And MixedSignal VLSI Circuits. Norwell, MA Kluwer, 2000. [6] Ji-Han Jiang*, Chin-Chen Chang*, and Tung-Shou Chen An Efficient Huffman Decoding Method Based onPattern Partition and Look-up Table [7] Kinjal A. Bhavsar Analysis of Test Data Compression Techniques Based on Complementary Huffman Coding International Journal of Engineering Science and Technology (IJEST)
THANK YOU

More Related Content

Huffman data compression-decompression

  • 1. An Efficient Test Vector Compression Scheme Using Selective Huffman Coding Under the guidance of Prof.Aarthi Presented By Dipu P 12MVD0060 Venketa Ramesh E 12MVD0062 HarshaVardhan B 12MVD0063
  • 2. INTRODUCTION: A SOC based design provide several design challenges These chips are composed of several reusable intellectual property (IP) cores The volume of test data for a SOC is growing rapidly as IP cores become more complex Extreme challenges to current tools and methodologies
  • 3. 1/2 In present days the complexity of SOC is keep on increasing, so for testing those ICs requires huge cost Various factors of ATE are limitations to a testing technique and methodology Various techniques available for reducing the test data They are BIST and Test Data Compression
  • 4. 1/3 Various methods i) code based schemes ii) Linear-decompression based schemes iii) Broad cast based schemes Code Based Schemes 1) Fixed to Fixed 2) Fixed to Variable 3) Variable to fixed 4) Variable to Variable
  • 5. Huffman Encoding Scheme 1/4 Building up of Huffman Tree Selective Huffman Compression Ratio 1 0010 0010 0010 0001 1100 2 0100 0100 0110 0100 1000 3 4 5 6 0010 0010 0010 0010 0100 0110 0110 0010 0111 0111 0000 0000 0010 0010 0010 0010 0110 0100 0010 0010 7 1011 0010 0100 0111 0111 Test File under consideration 8 9 10 11 12 0100 0100 0110 0111 0111 0010 0110 0010 0100 0010 0100 0010 0010 0100 0100 0110 0010 1000 1000 1111 0010 0000 0101 0101 0011
  • 6. ENCODING SCHEME 2/4 0010010000100110000000101 0110100001001000110011010 1011010101011000001110000 1111000001101010101010000 SORTED TEST VECTORS HUFFMAN TREE 0010 Algorithm of Huffman Encoder Feed the Test File Divide in to set of four bits Sorting the 4-bit block descending order of their occurrence(frequency) Tree Development Encoding
  • 7. 3/4 Feed the Test File. Divide in to set of four bits. Sorting the 4-bit block descending order of their occurrence(frequency). Select the most frequently occurring bit sets. (Those having High Frequency). Huffman Coding For the Selected Set. Set MSB=1 for the Selected encoded bits. Set MSB=0 for unselected bit sets. Zero tag indicate no need of decompression .
  • 8. 4/4 Comparison Between Huffman And Selective Huffman
  • 16. 1/2 RESULTS-Decoded Output and Comparison Huffman Selective Huffman Total Combinational functions 102 73 Total Registers 41 40 % of Compression= % of Compression=19.166 Decoded output for a given serial input
  • 17. 2/2 Total no of bits=240 Compressed bits for Huffman=178 Compressed bits for Huffman=194
  • 18. CONCLUSION Importance of compression and decompression in testing field. Huffman Compression-Decompression Selective Huffman Compression-Decompression Simple-Decoder with Lesser Logic Elements. Results indicate that the proposed scheme can provide test data compression nearly equal to that of an optimum Huffman code with much less area overhead for the decoder.
  • 19. REFERENCES [1] Xrysovalantis Kavousianos, Emmanouil Kalligeros, and Dimitris Nikolos Optimal Selective Huffman Coding for Test-Data Compression IEEE TRANSACTIONS ON COMPUTERS, VOL. 56, NO. 8, AUGUST 2007 [2] Abhijit Jas, Jayabrata Ghosh-Dastidar, Mom-Eng Ng, and Nur A. ToubaAn Efficient Test Vector Compression Scheme Using Selective Huffman Coding IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMSJUNE 2003. [3] J. Aerts and E. J. Marinissen, Scan chain design for test time reduction in core-based ICs, in Proc. Int. Test Conf., 1998, pp. 448457. [4] I. Bayraktaroglu and A. Orailoglu, Test volume and application time reduction through scan chain concealment, in Proc. Design Automation Conf., 2001, pp. 151155. [5] M. L. Bushnell and V. D. Agrawal, Essentials of Electronic Testing For Digital, Memory, And MixedSignal VLSI Circuits. Norwell, MA Kluwer, 2000. [6] Ji-Han Jiang*, Chin-Chen Chang*, and Tung-Shou Chen An Efficient Huffman Decoding Method Based onPattern Partition and Look-up Table [7] Kinjal A. Bhavsar Analysis of Test Data Compression Techniques Based on Complementary Huffman Coding International Journal of Engineering Science and Technology (IJEST)