Relationship Between Entropy and Test Data Compression

The entropy of a set of data is a measure of the amount of information contained in it. Entropy calculations for fully specified data have been used to get a theoretical bound on how much that data can be compressed. This paper extends the concept of entropy for incompletely specified test data (i.e., that has unspecified or don't care bits) and explores the use of entropy to show how bounds on the maximum amount of compression for a particular symbol partitioning can be calculated. The impact of different ways of partitioning the test data into symbols on entropy is studied. For a class of partitions that use fixed-length symbols, a greedy algorithm for specifying the don't cares to reduce entropy is described. It is shown to be equivalent to the minimum entropy set cover problem and thus is within an additive constant error with respect to the minimum entropy possible among all ways of specifying the don't cares. A polynomial time algorithm that can be used to approximate the calculation of entropy is described. Different test data compression techniques proposed in the literature are analyzed with respect to the entropy bounds. The limitations and advantages of certain types of test data encoding strategies are studied using entropy theory

I. Introduction

One of the main challenges in very large scale integration testing has been the rapid increase in test data volume especially in system-on-a-chip designs [2]. More test data volume leads to higher tester memory requirements and longer test times when the testing is performed using conventional external testers, i.e., automated test equipment. This directly affects the test costs of a chip. Reducing the test data volume by compression techniques is an attractive approach for dealing with this problem. The test data are stored in compressed form on the tester and transferred to the chip where it is decompressed using an on-chip decompressor.