The extended Euclidean algorithm (EEA) for polynomial greatest common divisors is commonly used in solving the key equation in the decoding of Reed-Solomon (RS) codes, and more generally in BCH decoding. For this particular application, the iterations in the EEA are stopped when the degree of the remainder polynomial falls below a threshold. While determining the degree of a polynomial is a simple task for human beings, hardware implementation of this stopping rule is more complicated. This paper describes a modified version of the EEA that is specifically adapted to the RS decoding problem. This modified algorithm requires no degree computation or comparison to a threshold, and it uses a fixed number of iterations. Another advantage of this modified version is in its application to the errors-and-erasures decoding problem for RS codes where significant hardware savings can be achieved via seamless computation.

Error-control coding is commonly used to achieve reliable communication over noisy channels, but the small error rates thus obtained are usually at the expense of considerable delay in delivering the transmitted information to its destination. This paper discusses some simple alternative implementations of encoders and decoders that allow for a reduction in the delay in an error-control system. Such a reduction in the delay also reduces the memory requirements of the encoder and decoder.

Many high-throughput two-dimensional architectures for finite field inversion and division are based on reformulations of the extended Euclidean algorithm (EEA). These reformulated EEAs usually keep track of two pairs of data polynomials (or registers), and the operations of the reformulated EEAs are only within each pair of polynomials. In this paper, we propose a new reformulated EEA wherein the operations within the two pairs of polynomials are identical. Hence, the two pairs of polynomials in our new reformulated EEA can be concatenated into one pair. By utilizing some inherent properties of the EEA, we further reduce the computational complexity of our reformulated EEA by 25%. Based on our reformulated EEA, we propose new two-dimensional inversion and division architectures. How much hardware saving the reduced computational complexity translates into depends on how control mechanisms are implemented. Regardless of the implementation of control signals, our new architectures require smaller numbers of gates and latches while achieving comparable or better throughput, latency, and critical path delay in comparison to the best architectures in the literature.

The author points out that several of the results in the paper by D. Peng and P. Fan (see ibid., vol.50, no.9, p.2149-54, Sep. 2004) have been published previously

Universal Reed-Solomon decoders allow flexibility in some or all of the code parameters,and hence lend themselves to applications wherein adaptability and reconfigurability are important considerations. In this paper,we consider universal finite field arithmetics using either canonical polynomial basis or shifted polynomial basis, and propose a high-speed universal Reed-Solomon decoder by modifying the high-speed decoder proposed in [10 ].

Based on a new reformulation of the extended Euclidean algorithm, systolic architectures suitable for VLSI implementations are proposed for finite field inversion and division in this paper. The architectures proposed in this paper can achieve O(m2) area-time complexity, O(m) latency, and critical path delays of two logic gates. These architectures show improved performances when compared with previously proposed architectures.

We present two systolic architectures for inversion and division in GF(2/sup m/) based on a modified extended Euclidean algorithm. Our architectures are similar to those proposed by others in that they consist of two-dimensional arrays of computing cells and control cells with only local intercell connections and have O(m/sup 2/) area-time product. However, in comparison to similar architectures, both our architectures have critical path delays that are smaller, gate counts that range from being considerably smaller to only slightly larger, and latencies that are identical for inversion but somewhat larger for division. One architecture uses an adder or an (m+l)-bit ring counter inside each control cell, while the other architecture distributes the ring counters into the computing cells, thereby reducing each control cell to just two gates.

New high-speed VLSI architectures for decoding Reed-Solomon codes with the Berlekamp-Massey algorithm are presented in this paper. The speed bottleneck in the Berlekamp-Massey algorithm is in the iterative computation of discrepancies followed by the updating of the error-locator polynomial. This bottleneck is eliminated via a series of algorithmic transformations that result in a fully systolic architecture in which a single array of processors computes both the error-locator and the error-evaluator polynomials. In contrast to conventional Berlekamp-Massey architectures in which the critical path passes through two multipliers and 1+[log/sub 2/,(t+1)] adders, the critical path in the proposed architecture passes through only one multiplier and one adder, which is comparable to the critical path in architectures based on the extended Euclidean algorithm. More interestingly, the proposed architecture requires approximately 25% fewer multipliers and a simpler control structure than the architectures based on the popular extended Euclidean algorithm. For block-interleaved Reed-Solomon codes, embedding the interleaver memory into the decoder results in a further reduction of the critical path delay to just one XOR gate and one multiplexer, leading to speed-ups of as much as an order of magnitude over conventional architectures.

The "alternative derivation" proposed in the Letter referenced in the title (see ibid., vol.42, p.2224, 1994) is incorrect. The correct derivation gives a result that agrees with previous computations. Hence, the claims and conclusions based on the apparent difference in the results are not valid.

The authors investigate methods for the parallel acquisition of a PN sequence in a baseband direct sequence spread spectrum system. Four different schemes are considered: the optimal estimation scheme, the maximum-likelihood estimation scheme, a hypothesis-testing scheme that searches over all shifts, and a locally optimum detection scheme. Approximate expressions for the probability of error are derived for the first and last of these schemes and compared with the actual error probabilities obtained via Monte Carlo simulation. Monte Carlo simulation is also used to obtain the error probabilities of the other two schemes and the results for all the schemes are compared. Since the obvious methods of implementing a parallel acquisition scheme require large amounts of hardware or excessive computation, they outline a technique that can be used to reduce the amount of computation.>

The use of a sequential probability ratio test (SPRT) for the acquisition of pseudonoise (PN) sequences in chip synchronous direct-sequence spread-spectrum (DS/SS) systems is considered. The out-of-phase sequence is modeled as a random sequence and the probabilities of error and expected sample sizes for the corresponding test are derived. A different (and very commonly used) test is obtained if the out-of-phase sequence is modeled as a zero sequence. The probabilities of error and the expected sample sizes of both SPRT's are compared, and it is shown that the latter test has a significantly larger probability of type I error. Numerical evaluation of the performance of both tests applied to a PN sequence of period 210- 1 gives results in agreement with the analytical results. We conclude that a random sequence is an excellent model for a PN sequence, and that significant degradation in performance can be expected if the test design is based on the zero sequence model rather than on the random sequence model.

Most versions of the Peterson-Gorenstein-Zierler (PGZ) decoding algorithm are not true bounded distance decoding algorithms in the sense that when a received vector is not in the decoding sphere of any codeword, the algorithm does not always declare a decoding failure. For a t-error-correcting BCH code, if the received vector is at distance i, i/spl les/t from a codeword in a supercode with BCH distance t+i+1, the decoder will output that codeword from the supercede. If that codeword is not a member of the t-error-correcting code, then decoder malfunction is said to have occurred. We describe the necessary and sufficient conditions for decoder malfunction, and show that malfunction can be avoided in the PGZ decoder by checking t-/spl nu/ equations, where /spl nu/ is the number of errors hypothesized by the decoder. A formula for the probability of decoder malfunction is also given, and the significance of decoder malfunction is considered for PGZ decoders and high-speed Berlekamp-Massey decoders.>

Time-hopping and frequency-hopping multiple-access (TH/FHMA) packet communication systems are proposed and investigated. In TH/FHMA communication systems, a message packet is encoded into several subpackets via a Reed-Solomon error correcting code. The subpackets are transmitted over the channel using time-hopping and frequency-hopping patterns. It is assumed that the channel is noiseless and the side information is perfect so that all subpacket collisions can be correctly detected. Slot-synchronous and totally asynchronous TH/FHMA systems are analyzed in detail, and they are shown to have excellent throughputs at small packet erasure rates. Various time-hopping techniques which significantly reduce the multiple-access interference are developed.>

The optimum detection of M orthogonal equiprobable equal-energy signals in additive white Gaussian noise is considered, and two upper bounds for the probability of error are derived. The behavior of these bounds is discussed and they are compared with previously known bounds for various values of signal-to-noise ratio and M. Some numerical results are presented.>

The (n, k) pseudocyclic maximum-distance-separable (MDS) codes modulo (x/sup n/-a) over GF(q) are considered. Suppose that n is a divisor of q+1. If n is odd, pseudocyclic MDS codes exist for all k. However, if n is even, nontrivial pseudocyclic MDS codes exist for odd k (but not for even k) if a is a quadratic residue in GF(q), and they exist for even k (but not for odd k) if a is not a quadratic residue in GF(q). Also considered is the case when n is a divisor of q-1, and it is shown that pseudocyclic MDS codes exist if and only if the multiplicative order of a divides (q-1)/n, and that when this condition is satisfied, such codes exist for all k. If the condition is not satisfied, every pseudocyclic code of length n is the result of interleaving a shorter pseudocyclic code.>

A t-error-correcting bounded-distance decoder either produces the codeword nearest the received vector (if there is a codeword at distance no more than t) or indicates that no such codeword exists. However, BCH decoders based on the Peterson-Gorenstein-Zierler algorithm or the Euclidean algorithm can malfunction and produce output vectors that are not codewords at all. For any integer i no greater than t/2, if the received vector is at distance at most t-2i from a codeword belonging to a (t-i)-error-correcting BCH supercode, then the BCH decoder output is that codeword from the supercode.>

A direct-sequence spread-spectrum multiple-access (SSMA) communication system that assigned a set of M-orthogonal sequences to each user is analyzed. An accurate model is incorporated for the impulsive noise that characterizes the LF and MF bands, so that the SSMA receiver operates in a combination of multiple-access interference and impulsive (atmospheric) noise. The performance of a linear receiver operating in such an environment is analyzed, and probability-of-error curves are presented. The presence of impulsive noise motivates the derivation and analysis of a nonlinear receiver that use a variable-gain stage to suppress noise impulses. This receiver is effectively optimum when the signal amplitudes are below a certain bound and when the noise and interference samples are independent, or nearly so. However, the gain stage of this nearly optimum receiver depends on the noise model parameters including the various user delays. Consequently, a nonparametric receiver that incorporates a simple clipper is also analyzed. The asymptotic relative efficiency of both receivers is determined.>

Time-hopping patterns can be constructed from simple difference sets. By studying such constructions, it has been proven that whenever n-2, n-1, or n+1 is a prime power, then time-hopping patterns that have n terms can be constructed and are of length less than n/sup 2/. By computation it is shown that such patterns can have length less than n/sup 2/-n/sup 1.44/ for all n>

This paper analyzes a direct-sequence, spread-spectrum, multiple-access (SSMA) communication system which assigns a set ofMorthogonal sequences to each user. With all direct sequence SSMA systems,Kusers share a channel by phase modulating their transmissions with signature sequences. However, the users of our system transmitlog_{2}Mbits of information/sequence. This contrasts classical SSMA schemes which use a pair of antipodal sequences and transmit 1 bit/sequence. In this paper, we assume that the channel noise is a combination of additive white Gaussian noise (AWGN) and multiple-access interference. We employ the optimum (single-user) demodulator for orthogonal signals in Gaussian noise. The multiple-user performance of this receiver is analyzed. We obtain approximations for the multiuser probability of error by using a Gaussian approximation for the multiple-access interference. We also obtain an upper bound on the exact probability by using characteristic functions. Our SSMA system is Well suited for application at the lower radio frequencies. Therefore, a companion paper describes a realistic model for low-frequency radio noise, modifies the receiver to include a zero-memory nonlinearity, and studies the performance of the nonlinear receiver.

In this paper, we investigate the performance of a nearoptimum receiver in a frequency-hopped multiple-access (FHMA) differential phase-shift-keyed (DPSK) spread-spectrum communication system. We obtain upper bounds on the bit error rates (BER's) for the chipsynchronous system and the chip-asynchronous system in the presence of a single interfering signal which interferes in one time-chip. We also obtain upper bounds on the BER for the chip-synchronous system with multiple-user interference, for the special case where each time-chip has at most one interfering signal of the same power as the desired signal. We find that, for the chip-synchronous system, the upper bound on the BER when one time-chip has two interfering signals is larger than the upper bound on the BER when each of the two time-chips has a single interfering signal. We also discuss system performance for a large number of simultaneous users, and examine the additive white Gaussian noise (AWGN) approximation for the multiple-user interference. Finally, results for the chip-synchronous system with single interference in one time-chip over a Rayleigh fading channel are presented.

Nearly all previous analytical results on the performance of direct-sequence spread-spectrum multiple-access (DS/SSMA) communication systems are restricted to systems in which the periodpof the signature sequence is equal to the numberNof chips per data symbol. In many applications, however, it is necessary to employ signature sequences whose periodpis much larger thanN. Thus, successiveN-chip segments of the signature sequence are used to phase-code the carrier during the transmission of successive data symbols. The performance of such systems depends on the partial correlation properties of the signature sequences (rather than the aperiodic correlation properties as in the case whenN=p). In this paper, we consider the performance of a DS/SSMA system for arbitrary values ofpandN. As special cases of our results, we delermine the effects of partial correlation in three classes of systems: those for whichN =p, those for whichNandpare relatively prime, and those for whichNis a divisor ofp. We also provide two methods for the design of sequences for systems for whichNis a divisor ofp.

This paper studies constructions for quadriphase sequences that are suitable for use as signature sequences in quadriphase spread-spectrum multiple-access communications. Quadriphase sequences are closely related to biphase (i.e., binary) sequences, and many of the properties of the former can be expressed in terms of properties of the latter. Methods of construction are presented which obtain sets of quadriphase sequences from sets of biphase sequences. Methods of construction of quadriphase sequences are provided based upon the properties of the multiplicative characters of the finite field GF(q)whereq \equiv 1 \mod 4. These methods use codewords from low-rate Reed-Solomon codes, which are mapped onto the fourth roots of unity.2q + 2sequences of periodq - 1are constructed, for which the maximum magnitudes of the periodic cross correlation and the periodic out-of-phase autocorrelation are bounded by3 \sqrt{q} + 5.

The magnitude of the out-of-phase aperiodic autocorrelation function for a maximal-length linear feedback shift register sequence of periodNis at most1 + (2/ \pi)(N + 1)^{1/2} \ln(4N/ \pi). Previously, the best upper bound was(N + 1)^{1/2} \ln (eN).

A recent paper by Chu [J.ACM 28, 2 (Apt 1981), 265-269] proposes a scheme for double error detecuon which ~s based on nawe and unrealistic assumptions about the data communication system.Under more realistic conditions, the scheme fails to work as claimed.Suitably modified versions of Chu's scheme do work: they are also well known in the coding literature as Reed-Solomon coding schemes!Categories and Subject Descriptors: B.4.5

Upper and lower bounds on the average probability of error are obtained for direct-sequence spread-spectrum multiple-access communications systems with additive white Gaussian noise channels. The bounds, which are developed from convexity properties of the error probability function, are valid for systems in which the maximum multiple-access interference does not exceed the desired signal and the signature sequence period is equal to the duration of the data pulse. The tightness of the bounds is examined for system with a small number of simultaneously active transmitters. This is accomplished by comparisons of the upper and lower bounds for several values of the system parameters. The bounds are also compared with an approximation based on the signal-to-noise ratio and with the Chernoff upper bound.

Banta has recently proposed a class of nonlinear codes that use the logical Hadamard transform for encoding and decoding. The same performance can be achieved by class of linear codes exhibited in this correspondence. The decoder for these linear codes is simpler than the decoder for the Banta codes, while the encoder is almost trivial.

New techniques are presented for the design of sequences with good correlation properties. These methods can he used to construct sequences with out-of-phase periodic autocorrelation values of zero, sequences that are uncorrelated, and long impulse-equivalent sequences.

An algorithm which computes the Fourier transform of a sequence of length n over GF(2m) using approximately 2nm multiplications and n2+ nm additions is developed. The number of multiplications is thus considerably smaller than the n2multiplications required for a direct evaluation, though the number of additions is slightly larger. Unlike the fast Fourier transform, this method does not depend on the factors of n and can be used when n is not highly composite or is a prime.

An analysis of the code sequence parameters that are most important to the communication performance of an asynchronous phase-coded spread-spectrum multiple-access communication system is presented. Previously known bounds and computational techniques for such parameters are surveyed. Some new results on mean-square correlation are included.

The selection of sets of periodic sequences with good correlation parameters is an important problem in many areas of communication theory. Although algorithms have been proposed for selecting sets of sequences, the amount of computation required is often prohibitive. Several autocorrelation and cross-correlation parameters are investigated such as those which characterize the performance of asynchronous phase-coded spread-spectrum multiple-access communication systems. New analytical results are provided which permit significant reduction in the amount of computation needed to evaluate these correlation parameters.

It is shown that i) erasures-and-errors decoding of Goppa codes can be done usingO(n \log^{2} n)arithmetic operations, ii) long primitive binary Bose-Chaudhuri-Hocquenghem (BCH) codes can be decoded usingO(n \log n)arithmetic operations, and iii) Justesen's asymptotically good codes can be decoded usingO(n^{2})bit operations. These results are based on the application of efficient computational techniques to the decoding algorithms recently discovered by Sugiyama, Kasahara, Hirasawa, and Namekawa.