In this paper, we propose a knapsack cryptosystem based on three knapsacks. Although one of the three secret knapsacks is superincreasing, the other two are non-superincreasing. On the encryption, a ciphertext is formed by multiplying the two non-superincreasing knapsacks together and then adding it to the superincreasing knapsack. Due to this structure of the cipher text, our knapsack cryptosystem is thought to be secure against all existing attacks, i.e., the low density attack and Shamir attack.

Biometric person authentication has been attracting considerable attention in recent years. Conventional biometric person authentication systems, however, simply store each user's template as-is on the system. If registered templates are not properly protected, the risk arises of template leakage to a third party and impersonation using biometric data restored from a template. We propose a technique that encrypts and stores the user template and uses a “fuzzy vault scheme” to generate secret data from the user template and the query biometric data. It incorporates a measure to prevent the secret data and the user template used to obtain the secret data from being recovered from information stored in the system, and it enables the secret data to be generated from the user's biometric data. In this paper, we introduce this technique and evaluate template security with it by simulating a fingerprint authentication system.

We discuss a lower bound on the minimum distance of a q-ary image of q/sup m/-ary cyclic code, based on its concatenated structure due to Jensen (see ibid., vol.31, no.6, p.788-93, 1985) and Seguin (see ibid., vol.41, no.2, p.387-99, 1995). An explicit estimate for the minimum distance of the outer codes, which is analogous to the BCH bound, is derived. Complete lists of the values obtained from the lower hound are given for binary images of 2/sup 5/-ary and 2/sup 6/-ary Reed-Solomon codes.

An efficient multicast hybrid ARQ scheme is proposed by incorporating the generalized minimum distance (GRID) decoding of maximum distance separable (MDS) codes with Metzner's (1984) scheme. Erroneous frames are stored in the receiver buffer and recovered after receiving one or more redundant frames. The throughput and the average transmission delay of the proposed scheme are analyzed on memoryless symmetric channels. The proposed scheme can circumvent the degradation of the throughput due to an increase of the number of receivers, which is the most serious defect in the conventional multicast ARQ schemes, at the expense of the transmission delay.

A key equation of the remainder decoding algorithm is presented. It is noted that the key equation presents a general relationship between the errors on the received codeword and the coefficients of the remainder polynomial. It is shown that several key equations proposed by L. Welch and E.R. Berlekamp (1983) and others can be derived from the proposed key equation. Useful properties of the key equations in fast decoding of Reed-Solomon codes are given.>

Discrete-time Wiener-Hopf equations (DTWHEs) over finite fields are considered. It is shown that solving the DTWHE is equivalent to performing division over finite fields. The proof provides a new interpretation of the relationship between bit-serial multiplication and DTWHEs. The interpretation enables bit-serial multiplication over GF(2/sup m/) to be understood more easily. As an example, bit-serial multiplication methods for multiplying any two elements that can be done without performing any transformation, or with only a simple transformation of the bases, are presented.>

A hybrid automatic repeat request (ARQ) system (HARQ-II) with parity retransmission for error correction, which combines ARQ and forward error correction is discussed, and the successful application of these codes to HARG-II is illustrated. A method of constructing the codes whereby conventional BCH codes can be changed into separable codes is proposed. A scheme is presented that has the advantages that, the code lengths are always made equal and that even in parity retransmission new information symbols can be sent along with the necessary parity-check symbols. The performance of the proposed schemes on the binary symmetric channel is discussed. The numerical results show that they outperform conventional schemes.>

By modifying product codes, a new coding scheme and its decoding method are proposed. Compared to a product codeA, the first stage codeA_{1}of the new codeA_{M}is constructed in the same way as that of the codeAexcept that it has at least one subcode, while the second stage codesA_{2}^{(j)}of the codeA_{M}are a set of codes With the same length and different rates. The new coding scheme has a smaller upper bound on the probability of decoding error than the original product coding scheme for any given nonzero rate less than the capacity of a binary symmetric channel. An example is given for which the rate is increased compared With the original product code, at a fixed probability of decoding error, for a relatively short code length.

The asymptotic performance of variance-mismatched vector quantizers is presented. It is demonstrated by both asymptotic analysis and computer simulations that well-designed vector quantizers are inherently more invulnerable to mismatch than are conventional scalar quantizers. A generalized exponential density function is considered as a statistical model of sources. As an example, the asymptotic performance is derived and applied to the memoryless Laplacian source with the squared-error distortion measure.

We interpret Reed-Muller codes in terms of superimposition and present a new decoding algorithm for Reed-Muller codes. Before presenting this algorithm, we propose a decoding algorithm for a class of simple iterated codes (SI codes) that will play an important role in our new decoding algorithm. Finally, we compare our algorithm with the conventional algorithm for the cyclic Reed-Muller codes from the standpoint of decoding delay.

The lower bound m the error exponent for the generalized version of concatenated codes is shown to be improved at low rates for binary-input memoryless channels.

New coding and decoding schemes based on concatenated codes are proposed. The new coding schemes are potentially superior to Forney's original concatenation scheme in the sense that for discrete memoryless channels the former has a smaller upper bound on the probability of decoding error for the same order of decoding complexity.

Binary block codes are constructed that are capable of correcting successive timing errors such as the deletion or insertion ofsbits(s\leq D)within a single additive burst of errors of lengthbor less(b=f+g+2D), wherefandDare the design parameters that specify the length of correctable successive timing errors andgis the length of the correctable additive burst. A decoding algorithm is given and the efficiency of these codes is discussed.

A family of codes of lengthn=q^{s+l}over GF(q), with2s \leq qare presented which are constructed by superimposing concatenated codes on a concatenated code. The raterand the distance ratio\deltaof the new codes satisfy the relationr=1-\delta+\delta \ln (\delta)for sufficiently large values ofnandq/s. The new codes are superior to the comparable Bose-Chaudhuri-Hocquenghem (BCH) codes, fors\geq 3, in the sense that they contain more codewords. An asymptotically good code constructed using these new codes has a distance ratio greater than those of other asymptotically good codes known to the authors for rates smaller than 0.007.

Error control techniques in the various digital data transmission systems can be divided into three classes, i.e., classes of forward error correction (FEC), automatic repeat request (ARQ), and FEC embedded within ARQ (Hybrid). We exactly analyze and compare the performances of these error control techniques in both independenterror and dependent-error channels. It is shown that among the various error control techniques the Go-Back-2 ARQ system offers the best performances over a wide range of the channel error rate, i.e.,P_{e} \lsim 10^{-4}, regardless of the type of the channel. The various numerical results are shown graphically along with the discussions.

A new class of asymptotically good codes is constructed by iteratively superimposing Justesen codes on a Justesen code. The lower bound for the new codes lies above the Zyahlov bound for rater, 0.31 < r < 1.

A simple Markov chain model for differentially encoded CPSK Channels faciliates the calculation of the probability of the occurrence of several most probable error patterns in a given codeword. Several error correcting codes which can efficiently correct several most-probable error patterns are proposed and their error performances are analyzed.

Finite-state Markov chain models are proposed to represent the process of the occurrence of errors in differential phase-shift-keying (DPSK) systems and also in coherent phase-shift-keying (CPSK) systems with differential coding-and-decoding schemes. A simple and general formula is derived for the probabilityP(m,n)of the occurrence of m errors in a sequence ofndigits which is the fundamental error statistic required to evaluate random-error-correcting codes applied to these channels.

We present new classes of binary codes that are constructed on the basis of concatenated codes and product codes. We discuss the random-error-correction capabilities of these codes. Some examples of the codes for the correction of random errors are given which have at least as many codewords as the best codes previously known (to the authors) with the same minimum distance and same number of check symbols. The burst-error-correction capabilities of the codes are also discussed. Several examples of the codes for the correction of both random errors and burst errors are given. A decoding algorithm for the codes is also described.

An erasures-and-errors decoding algorithm for Goppa codes is presented. Given the Goppa polynomial and the modified syndrome polynomial, a modified key equation is solved using Euclid's algorithm to determine the error locator polynomial and the errata evaluator polynomial.

It is shown that Goppa codes with Goppa polynomial\{g(z)\}^{q}have the parameters: lengthn \leq q^{m} - s_{o}, number of check symbolsn - k \leq m (q - 1) (\deg g), and minimum distanced \geq q (\deg g) + 1, whereqis a prime power,mis an integer,g(z )is an arbitrary polynomial overGF(q^{m}), and so is the number of roots ofg(z)which belong toGF(q^{m}). It is also shown that all binary Goppa codes of lengthn \leq 2^{m} - s_{o}satisfy the relationn - k \leq m (d - 1)/2. A new class of binary codes withn \leq 2^{ m} + ms _{0}, n - k \leq m (\deg g) + s_{0}, andd \leq 2(\deg g) + 1is constructed, as well as another class of binary codes with slightly different parameters. Some of those codes are proved superior to the best codes previously known. Finally, a decoding algorithm is given for the codes constructed which uses Euclid's algorithm.

In this correspondence, we present a new class of binary codes that are constructed on the basis of BCH codes. Some examples of these codes are given, having more codewords than the best codes previously known (to the authors) with the same minimum distance and number of check symbols. A decoding algorithm for the codes is also described.

In this correspondence, we construct a new class of binary codes by exploiting the symmetry properties of the parity check matrix of the Srivastava codes. The construction is a generalization of Goppa's construction [1]. A number of the binary codes constructed are proved equal, or superior, to the best codes previously known.