This paper presents a new compression technique for testing the intellectual property (IP) cores in system-on-chips. The pattern run-length compression applies the well-known run-length coding to equal and complementary consecutive patterns of the precomputed test data. No structural information of the IP cores is required by the encoding procedure. A data-independent decompressor can be realized by the embedded processor or on-chip circuitry. The decompressed test set can be flexibly applied to a single-scan or multiple-scan chain of each core-under-test. Experiments on ISCAS-89 benchmarks show that the new technique results in superior compression performance. The test application time is also significantly reduced

Signed-binary representations of integer k with symmetric digit set /spl Dscr//sub s/ - {-(2/sup w/ - 1 ),-(2/sup w/-3),... ,-1,0,1,... ,2/sup w/ - 3,2/sup w/ - 1} may have lower weight than the unsigned-binary expansion of k. The "weight" is the number of nonzero digits in a binary expansion. Lower weight leads to fewer number of addition operations in the scalar multiplication, kP, of elliptic curve cryptosystems. Here P is a point on an elliptic curve. On the other hand, computing the minimum-weight signed-binary representation from left (most significant bit) to right (least significant bit) significantly reduces memory requirements because intermediate results do not need to be stored. Since the size of /spl Dscr//sub s/ is 2/sup w/ + 1, a (w + 1)-bit data bus is necessary to represent the 2/sup w/ + 1 elements in /spl Dscr/ /sub s/. This is inefficient because a (w + 1)-bit bus is capable of denoting 2/sup w+1/ cases. We present a new signed-binary recoding algorithm with asymmetric digit set /spl Dscr//sub a/ - {-(2/sup w/ - 1),-(2/sup w/ - 3),...,-1, 0,1,...,2/sup w/ - 3}. For w = 2, our simulation results show that the average weight of signed-binary numbers with digit set {- 3,-1,0,1} is 0.285 times the length of their unsigned-binary expansions. For the optimal representations with {-1,0,1} the average ratio is 0.333. The number of additions is decreased by 14.4%. The encoding circuit requires 7 flip-flops and 22 gates to realize.

We consider using Shannon-Fano-Elias codes for data encryption. In many applications both compression and security are required. If the cryptanalyst knows the code construction rule and the probability mass function of the source, then Huffman code provides no ambiguity, but Shannon-Fano-Elias coding is a good candidate since the ordering of symbols can be arbitrary in the encoding process, which produces super-exponential complexity for deciphering. Unfortunately, the conventional Shannon-Fano-Elias code has relatively large code length that makes it inefficient. In this paper, we propose two simple algorithms to reduce the expected length of Shannon-Fano-Elias codes. Experimental results on English text show that the proposed methods reduce the length by as much as 23.4%

We present a new source coding scheme with smaller expected length than Shannon-Fano-Elias codes. The ordering of source symbols input to the proposed encoding algorithm can be arbitrary. We show that this property leads to exponential complexity for eavesdropping even though an adversary knows the code construction rule and the probability mass function of the source.

In this paper, we present a new description of the X-Code, a class of MDS array code, using skews, named S-Code. The X-Codes result in codewords that are arrays of size n /spl times/ n, where n is prime. Our new description does not require n to be prime but requires n to be an odd number with smallest prime factor greater than 3. We prove that the S-Codes result in a distance-3 MDS code. We also give a description of which slopes other than 1 and -1 can be used to construct S-Codes.

Data compression techniques such as Shannon-Fano-Elias coding are often used in conjunction with cryptography. We discuss using Shannon-Fano-Elias codes for encryption. We focus mainly on the problem of deciphering a binary sequence that has been Shannon-Fano-Elias encoded. We show that if a cryptanalyst knows the source symbols and the probability mass function (PMF), then the Shannon-Fano-Elias coded sequences may be deciphered within a finite amount of time by exhaustive search. A simple strategy is introduced to prevent this type of eavesdropping.

The common computation in elliptic curve cryptography (ECC), aP + bQ, is performed by extending Shamir's method for the computation of the product of powers of two elements in a group. The complexity of computing aP + bQ is dependent on the joint weight of the binary expansion of positive integers a and b. We give a method of finding a minimum joint weight signed-binary representation of a pair of integers. Our method examines the integers a and b from left to right, thereby making the conversion to signed-binary form compatible with Shamir's method. This reduces the memory required to perform the computation of aP + bQ.

An algorithm for computing the binary signed-digit representation of N integers is introduced. The algorithm operates from left to right (i.e., from the most significant bit to the least significant bit) and the resulting representation has minimum joint weight. Such an algorithm is useful in elliptic curve cryptosystems (ECC).