A new algorithm is developed to facilitate faster decoding of the (47,24,11) quadratic residue (QR) code. This decoder, based on the idea first developed by Reed in a 1959 MIT Lincoln Laboratory Report, uses real channel data to estimate the individual bit-error probabilities in a received word. The algorithm then sequentially inverts the bits with the highest probability of error until one of the errors is canceled. The remaining errors are then corrected by the use of algebraic decoding techniques. This new algorithm, called the reliability-search algorithm, is a complete decoder that significantly reduces the decoding complexity in terms of CPU time while maintaining the same bit-error rate (BER) performance. In fact, this algorithm is an appropriate modification to the algorithm developed by Chase.

The (23,12,7) Golay code is a perfect linear error-correcting code that can correct all patterns of three or fewer errors in 23 bit positions. A simple BCH decoding algorithm, given in E. Berlekamp (1968), can decode the (23,12,7) Golay code provided there are no more than two errors. The shift-search algorithm, developed by Reed et a. (1990), sequentially inverts the information bits until the third error is canceled. It then utilizes the BCH decoding algorithm to correct the remaining two errors. In this paper a simplified decoding algorithm, called the reliability-search algorithm, is proposed. This algorithm uses bit-error probability estimates to cancel the third error and then uses the BCH decoding algorithm to correct the remaining two errors. Simulation results show that this new algorithm significantly reduces the decoding complexity for correcting the third error while maintaining the same BER performance.

A novel self-synchronizing receiver with a J-element antenna array is developed for asynchronous DS-CDMA multipath fading channels in this paper. The primary requirement is knowledge of the desired user's signature sequence. There's no training period of signal-free observations is required. Also, no information is presumed about the interfering users. Multipath diversity is exploited via two combining schemes, namely the maximal ratio combining (MRC) and the equal gain combining (ECG). A computationally efficient receiver was developed to utilize the concept of the truncated multistage Wiener filter (TMWF) introduced by Goldstein and Reed. This technique obviates the necessity of either a covariance matrix inversion or an eigen-decomposition. Moreover, this multistage scheme achieves a rapid adaptive convergence under limited observation-data support. Simulation results indicate that the proposed detector provides superior performance as an increasing function of the size of the J-element antenna array and is nearly independent on the number of signals.

An algebraic decoding method is proposed for the quadratic residue codes that utilize the Berlekamp-Massey (BM) algorithm. By applying a technique developed by R. He et al. (see IEEE Trans. Inf. Theory, vol.47, p.1181-6, 2001), one can express unknown syndromes as functions of known syndromes. An efficient algorithm is also developed to determine the unknown syndromes. With the appearance of unknown syndromes, one obtains the consecutive syndromes that are needed for the application of the inverse-free BM algorithm. The new decoding scheme can be used to implement the (79,40,15) quadratic residue (QR) code which has not been treated so far. It is verified by a computer program that uses the C++ language.

Recently, a new algebraic decoding algorithm for quadratic residue (QR) codes was proposed by Truong et al. Using that decoding scheme, we now develop three decoders for the QR codes with parameters (71, 36, 11), (79, 40, 15), and (97, 49, 15), which have not been decoded before. To confirm our results, an exhaustive computer simulation has been executed successfully.

Symbol and bit error rates of M-ary differentially encoded/differentially decoded phase-shift keying (MDPSK) and coherent M-ary phase-shift keying (M-PSK) over slow, flat, Rician fading channels are derived when linear diversity combining is applied to combat degradation due to fading. These closed-form solutions are general enough to cover several cases of nondiversity, additive white Gaussian noise (the nonfading mode), Rayleigh fading, mixtures of Rayleigh and Rician fading (the mixed mode), and Rician fading. The results presented here can also be applied to predict the error-rate performance when recent transmit diversity techniques are employed. The solutions for the nonuniform fading profile are included as well. Error probabilities are graphically displayed for both modulation schemes.

An adaptive near-far-resistant self-synchronizing detector for asynchronous DS-CDMA systems with a J-element antenna array is presented in this paper. The primary requirement is knowledge of the spreading-code sequence of the desired user. A low complexity version of the proposed detector is developed that utilizes the concept of the multistage reduced-rank Wiener filter introduced by Goldstein and Reed (1998). This results in a self-synchronizing detection criterion that requires no inversion or eigen-decomposition of a covariance matrix. It also achieves a rapid adaptive convergence under limited data support. Simulation results show that the proposed detector provides superior performance both as an increasing function of the size of the J-element antenna array and the amount of sample support.

A recursive linear detection algorithm is proposed for the detection of signals from an asynchronous direct-sequence code-division multiple-access (DS-CDMA) communication system. This algorithm works for short as well as long codes. Under some reasonable conditions, this algorithm is proved to be stable and converges to the ideal decorrelating detector (IDD) with a sufficiently large memory length. The performance of the algorithm is analyzed in some detail. Upper and lower bounds for the bit-error probabilities are developed. It is demonstrated that the two bounds converge to the bit-error probabilities of the IDD as the large memory length increases. Simulation results show that the recursive detector proposed outperforms the truncated decorrelating detector with less memory and less computational complexity.

An adaptive near-far resistant detector using multiple antennas for acquiring synchronization of an asynchronous DS-CDMA system is presented. The only requirement is the prior knowledge of the user-spreading sequence of interest. Also, there is no need of a training sequence and a training period. Synchronization acquisition of asynchronous DS-CDMA signals is treated as a binary-hypothesis test. Under the binary hypotheses, an adaptive generalized maximum likelihood ratio test (GLRT) is developed to acquire the multipath code timings of a single desired user in both a fading and a near-far interference environment. The synchronization is obtained by sliding a search window in a sample-by-sample manner to perform the adaptive GLRT with the non-constrained maximum likelihood estimator (MLE) of direction-of-arrival (DOA) during the symbol interval. The acquisition performance of the proposed detector is illustrated by computer simulations of an asynchronous BPSK DS-CDMA system and is shown to have potential against multipath fading and the problems of near-far interference.

The central problem in the implementation of a Reed-Solomon code is finding the roots of the error locator polynomial. In 1967, Berlekamp et al. found an algorithm for finding the roots of an affine polynomial in GF(2/sup m/) that can be used to solve this problem. In this paper, it is shown that this Berlekamp-Rumsey-Solomon (1967) algorithm, together with the Chien (1964) search method, makes possible a fast decoding algorithm in the standard-basis representation that is naturally suitable in a software implementation. Finally, simulation results for this fast algorithm are given.

The techniques needed to decode the (47,24,11) quadratic residue (QR) code differ from the schemes developed for cyclic codes. By finding certain nonlinear relations between the known and unknown syndromes for this special code, two methods are developed to decode up to the true minimum distance of the (47,24,11) QR code. These algorithms can be utilized to decode effectively the 1/2 -rate (48,24,12) QR code for correcting five errors and detecting six errors.

In this paper, a fast encoding algorithm is developed for fractal image compression. At each search entry in the domain pool, the mean square error (MSE) calculations of the given range block and the eight dihedral symmetries of the domain block are obtained simultaneously in the frequency domain, in which the redundant computations are all eliminated in the new encoding algorithm. It is shown in software simulation that the encoding time is about six times faster than that of the baseline method with almost the same PSNR for the retrieved image. The fast algorithm is performed to deal with the eight dihedral symmetries at each search entry. Therefore, it can be applied to various enhanced algorithms which are equipped with quadtree, classification, and other mechanisms.

A new cubic convolution spline interpolation (CCSI )for both one-dimensional (1-D) and two-dimensional (2-D) signals is developed in order to subsample signal and image compression data. The CCSI yields a very accurate algorithm for smoothing. It is also shown that this new and fast smoothing filter for CCSI can be used with the JPEG standard to design an improved JPEG encoder-decoder for a high compression ratio.

A new generalized statistical signal processing framework is introduced for optimal signal representation and compression. Previous work is extended by considering the multiple signal case, where a desired signal is observed only in the presence of other non-white signals. The solution to this multi-signal representation problem yields a generalization of the Karhunen-Loeve transform and generates a basis selection which is optimal for multiple signals and colored-noise random processes under the minimum mean-square error criterion. The important applications for which this model is valid include detection, prediction, estimation, compression, classification and recognition.

Closed-form solutions for the average error rate of MDPSK, coherent MPSK, and noncoherent MFSK over slow, flat, Rician fading are derived. The solutions are sufficiently simple so that no approximations are needed for the numerical computations and general enough so that it includes AWGN and Rayleigh fading as special cases. Error probabilities are graphically displayed for various values of M. The dependence of error rate on the channel specular-to-scatter ratio are plotted and examined. Performance comparisons for a range of values of the Rician parameter K, corresponding to the measured statistics of mobile and indoor wireless channels, are made for the different digital modulation schemes. The analytical results presented in this paper are expected to provide information that is important for radio systems design and the evaluation of performance over a fading channel.

The Wiener filter is analyzed for stationary complex Gaussian signals from an information theoretic point of view. A dual-port analysis of the Wiener filter leads to a decomposition based on orthogonal projections and results in a new multistage method for implementing the Wiener filter using a nested chain of scalar Wiener filters. This new representation of the Wiener filter provides the capability to perform an information-theoretic analysis of previous, basis-dependent, reduced-rank Wiener filters. This analysis demonstrates that the cross-spectral metric is optimal in the sense that it maximizes mutual information between the observed and desired processes. A new reduced-rank Wiener filter is developed based on this new structure which evolves a basis using successive projections of the desired signal onto orthogonal, lower dimensional subspaces. The performance is evaluated using a comparative computer analysis model and it is demonstrated that the low-complexity multistage reduced-rank Wiener filter is capable of outperforming the more complex eigendecomposition-based methods.

Automatic target recognition (ATR) generally refers to the autonomous or aided target detection and recognition by computer processing of data from a variety of sensors such as forward looking infrared (FLIR), synthetic aperture radar(SAR), inverse synthetic aperture radar (ISAR), laser radar (LADAR), millimeter wave (MMW) radar, multispectral/hyperspectral sensors, low-light television (LLTV), video, ete. It is an extremely important capability for targeting and surveillance missions of defense weapon systems operating from a variety of platforms.

Multispectral or hyperspectral sensors can facilitate automatic target detection and recognition in clutter since natural clutter from vegetation is characterized by a grey body, and man-made objects, compared with blackbody radiators, emit radiation more strongly at some wavelengths. Various types of data fusion of the spectral-spatial features contained in multiband imagery developed for detecting and recognizing low-contrast targets in clutter appear to have a common framework. A generalized hypothesis test on the observed data is formulated by partitioning the received bands into two groups. In one group, targets exhibit substantial coloring in their signatures but behave either like grey bodies or emit negligible radiant energy in the other group. This general observation about the data generalizes the data models used previously. A unified framework for these problems, which utilizes a maximum likelihood ratio approach to detection, is presented. Within this framework, a performance evaluation and a comparison of the various types of multiband detectors are conducted by finding the gain of the SNR needed for detection as well as the gain required for separability between the target classes used for recognition. Certain multiband detectors become special cases in this framework. The incremental gains in SNR and separability obtained by using what are called target-feature bands plus clutter-reference bands are studied. Certain essential parameters are defined that effect the gains in SNR and target separability.

This paper is concerned with the performance of reduced rank space-time adaptive processing (STAP) for radar signals. The motivation for rank reduction is that optimal full-rank STAP requires many more weights than can be supported on airborne and space-segment platforms. This paper compares the steady-state STAP performance for the fully adaptive joint domain (space-time) optimal processor, the partially adaptive factored time-space processor, the principal component technique, and the cross-spectral metric based processor. Data collected from the ARPA Mountaintop program is utilized to validate the results.

In Xu and Reed a matched-filter based detector was developed for the problem of detecting a 2-D target signal where prior information about the target pattern or template as well as the statistical properties of the clutter is limited. This was accomplished by an ad hoc substitution of the maximum likelihood estimate (MLE) of unknown clutter covariance matrix and the MLE's of the complex amplitudes of the significant features components of target into the matched filter test. The present paper provides a new approach for the problem based on the generalized likelihood ratio (GLR) principle which maximizes the GLR function over unknown clutter covariance matrix and the unknown significant feature components of target signal to be detected. This new GLR test is compared with the matched-filter based test in Xu and Reed for performance. The feature mapping and representation which can be incorporated into the test to characterize the unknown target pattern are various, including the short time Fourier transform, the discrete cosine transform, and the discrete wavelet transform.

Fractional Brownian motion (fBm) provides a useful model for processes with strong long-term dependence, such as 1/f/sup /spl beta// spectral behavior. However, fBm's are nonstationary processes so that the interpretation of such a spectrum is still a matter of speculation. To facilitate the study of this problem, another model is provided for the construction of fBm from a white-noise-like process by means of a stochastic or Ito integral in frequency of a stationary uncorrelated random process. Also a generalized power spectrum of the nonstationary fBm process is defined. This new approach to fBm can be used to compute all of the correlations, power spectra, and other properties of fBm. In this paper, a number of these fBm properties are developed from this model such as the T/sup H/ law of scaling, the power law of fractional order, the correlation of two arbitrary fBm's, and the evaluation of the fractal dimension under various transformations. This new treatment of fBm using a spectral representation is extended also, for the first time, to two or more topological dimensions in order to analyze the features of isotropic n-dimensional fBm.>

It is shown that any Reed-Solomon (RS) decoder which corrects both errors and erasures also can be used as an encoder for the RS code. This technique eliminates the need of a separate subsystem, namely the RS encoder in either two-way digital communication systems or storage devices which use RS encoding and decoding. As a consequence a single RS decoder chip which corrects both errors and erasures can be mass-manufactured for use in all two-way communication systems and storage devices such as a digital video-cassette recorder (VCR) or a write-once, read-many, (WORM) optical disk drive.>

This paper provides two theorems for decoding all types of cyclic codes. It is shown that from a polynomial ideal point of view, the decoding problems of cyclic codes are closely related to the monic generators of certain polynomial ideals. This conclusion is also generalized to the decoding problems of algebraic geometry codes.>

A general algebraic method for decoding all types of binary cyclic codes is presented. It is shown that such a method can correct t=[(d-1)/2] errors, where d is the true minimum distance of the given cyclic code. The key idea behind this decoding technique is a systematic application of the algorithmic procedures of Grobner bases to obtain the error-locator polynomial L(z). The discussion begins from a set of syndrome polynomials F and the ideal T(F) generated by F. It is proved here that the process of transforming F to the normalized reduced Grobner basis of I(F) with respect to the "purely lexicographical" ordering automatically converges to L(z). Furthermore, it is shown that L(z) can be derived from any normalized Grobner basis of I(F) with respect to any admissible total ordering. To illustrate this new approach, the procedures for decoding certain BCH codes and quadratic residue codes are demonstrated.>

The 1/2-rate binary quadratic residue (QR) codes, using binary phase-shift keyed (BPSK) modulation and hard decoding, are presented as an efficient system for reliable communication. Performance results of error correction are obtained both theoretically and by means of computer calculations for a number of binary QR codes. These results are compared with the commonly used 1/2-rate convolutional codes with constraint lengths from 3 to 7 for the hard-decision case. The binary QR codes of different lengths are shown to be equivalent in error-correction performance to some 1/2-rate convolutional codes, each of which has a constraint length K that corresponds to the error-control rate d/n and the minimum distance d of the QR codes.>

The class of binary quadratic residue (QR) codes of length n=8m-1 contains two perfect codes. These are the (7,4,3) Hamming code and the (23,12,7) Golay code. However, it is proved in the present paper that there are no quasi-perfect QR codes of length 8m-1. Finally, this result is generalized to all binary self-dual codes of length N>72.>

This paper deals with the problem of combining equalization with decoding in channels which have severe intersymbol interference. A multilayer neural net structure is proposed to achieve the process of equalization and decoding simultaneously. Experimental examples show that this method results in a substantial improvement over the more conventional methods of performing equalization and decoding.

The Karhunen-Loeve transform (KLT) is known to be the optimal transform for data compression. However, since it is signal dependent and lacks a fast algorithm, it is not used in practice. In this paper, a fast approximate Karhunen-Loeve transform (AKLT) is presented. This new transform is derived using perturbation theory of linear operators. Both the forward and inverse AKLT are analytically derived in closed forms. In addition, fast computational algorithms are developed for both the forward and inverse transforms. The order of computational complexity for the AKLT is N log2 N, which is the same as that of the DCT, the transform presently used in industrial practice. Performance comparisons reveal for a first-order Markov sequence that the AKLT performs better than the DCT in its energy compaction and signal decorrelation capabilities. Experiments on real images also demonstrate a definite superiority of the AKLT over the DCT when an adaptive scheme is used.

A new type of perfect reconstruction filter bank is presented in this paper., This new class of filter bank has the following distinct features at the same time: linear-phase, distortion-free, IIR-FIR filter pair, closed form expression, orthogonal projection, and factorization-free. In contrast, the other existing filter banks do not possess all these properties simultaneously. For example, the classic Quadrature Mirror Filter (QMF) does not have the perfect reconstruction nature. Another example is the Conjugate Quadrature Filter (CQF), which lacks the linear- phase property. A qualitative comparison of different types of filter banks is also included. This newly developed perfect reconstruction IIR-FIR filter bank is then extended to the 2-D case. Both separable and non-separable filters are considered. In addition, both rectangular downsampling and non-rectangular downsampling schemes are discussed. Numerical optimization procedures are used to compute the optimal filter coefficients. The results are listed in tables for quick reference.

Picking up exactly one member from each of the nonperiodic cyclic equivalence classes of an (n, k+1) Reed-Solomon code E over GF(q) gives a code, E", which has bounded Hamming correlation values and the self-synchronizing property. The exact size of E" is shown to be (1/n) Sigma /sub d mod n/ mu (d)q/sup 1+k/d/, where mu (d) is the Mobius function, (x) is the integer part of x, and the summation is over all the divisors d of n=q-1. A construction for a subset V of E is given to prove that mod E" mod >or= mod V mod =(q/sup k+1/-q/sup k+1-N/)/(q-1) where N is the number of integers from 1 to k which are relatively prime to q-1. A necessary and sufficient condition for mod E" mod = mod V mod is proved and some special cases are presented with examples. For all possible values of q>2, a number B(q) is determined such that mod E" mod = mod V mod for 1mod V mod for k>B(q).>

A robust multi-spectral adaptive object detection algorithm is derived for a multiple spatial resolution and orientation decomposition image mode by using a wavelet transform. The second-order statistical moments of the wavelet transform are computed for a random image field and then used to develop a generalized maximum likelihood ratio test and to analyze detection performance. The computational cost of the new detector can be reduced substantially when compared to conventional spatial size and orientation matched filter-bank approach by using a coarse-to-fine spatial matching strategy.>

A systolic Viterbi decoder for convolutional codes is developed which uses the trace-back method to reduce the amount of data needed to be stored in registers. It is shown that this new algorithm requires a smaller chip size and achieves a faster decoding time than other existing methods.>

A new algebraic approach for decoding the quadratic residue (QR) codes, in particular the (41, 21, 9) QR code, is presented. The key ideas behind this decoding technique are a systematic application of the Sylvester resultant method to the Newton identities associated with the syndromes to find the error-locator polynomial, and next a method for determining error locations by solving certain quadratic, cubic, and quartic equations over GF(2/sup m/) in a new way which uses Zech's logarithms for the arithmetic. The logarithms developed for Zech's logarithms save a substantial amount of computer memory by storing only a table of Zech's logarithms. These algorithms are suitable for implementation in a programmable microprocessor or special-purpose VLSI chip. It is expected that the algebraic methods developed can apply generally to other codes such as the BCH and Reed-Solomon codes.>

The aim of a neural net is to partition the data space into near optimal decision regions. Learning such a partitioning solely from examples has proven to be a very hard problem (Blum and Rivest 1988; Judd 1988). To remedy this, we use the idea of supplying hints to the network-as discussed by Abu-Mostafa (1990). Hints reduce the solution space, and as a consequence speed up the learning process. The minimum Hamming distance between the patterns serves as the hint. Next, it is shown how to learn such a hint and how to incorporate it into the learning algorithm. Modifications in the net structure and its operation are suggested, which allow for a better generalization. The sensitivity to errors in such a hint is studied through some simulations.

The arithmetic Fourier transform (AFT) is a number-theoretic approach to Fourier analysis which has been shown to perform competitively with the classical fast Fourier transform (FFT) in terms of accuracy, complexity and speed. Theorems developed previously for the AFT algorithm are used to derive the original AFT algorithm which Bruns found in 1903. This is shown to yield an algorithm of less complexity and of improved performance over certain recent AFT algorithms. A computationally balanced AFT algorithm for Fourier analysis and signal processing is developed. This algorithm does not require complex multiplications. A VLSI architecture is suggested for this amplified AFT algorithm. This architecture uses a butterfly structure which reduces the number of additions by 25% over that used by the direct method. This efficient AFT algorithm is shown to be identical to Brun's original AFT algorithm.>

An arithmetical approach to Fourier analysis, called the arithmetic Fourier transform (AFT), is developed for a two-dimensional (2D) signal. This 2D AFT algorithm is based on the arithmetical approach that H. Bruns originated in 1903. It uses alternating arithmetic averages of 2n samples over a period. The use of alternating arithmetic averages yields an algorithm of low complexity. The number of multiply operations, which compose a major part of the architecture, is reduced. This algorithm features parallel processing which can be effectively implemented with VLSI techniques or optical processors. As a consequence, it is expected that this arithmetic algorithm can compete in complexity and speed with the conventional 2D fast Fourier transform algorithm. Simulation of the algorithm for equally space 2D data is accomplished by using zero-order interpolation. Computer simulation demonstrates that the errors in the Fourier coefficients are tolerable for many applications.>

An algebraic decoding algorithm for the 1/2-rate (32, 16, 8) quadratic residue (QR) code is found. The key idea of this algorithm is to find the error locator polynomial by a systematic use of the Newton identities associated with the code syndromes. The techniques developed extend the algebraic decoding algorithm found recently for the (32, 16, 8) QR code. It is expected that the algebraic approach developed here and by M. Elia (1987) applies also to longer QR codes and other BCH-type codes that are not fully decoded by the standard BCH decoding algorithm.>

The authors describe the VLSI implementation of a general sidelobe cancellor (GSC) using powers-of-two arithmetic. The chip needed for this design carries six multiplications and seven additions. The layout of this chip is based on the standard cell and regular structure approach. To reduce the propagation delay of its carry-save addition unit, a fast ripple carry adder which has a single NAND gate delay for carry propagation is designed. This adder is designed to reduce the propagation delay of carries by a factor of two.>

Three different finite-field multipliers are presented: (1) a dual-basis multiplier due to E.R. Berlekamp (1982); the Massey-Omura normal basis multiplier; and (3) the Scott-Tavares-Peppard standard basis multiplier. These algorithms are chosen because each has its own distinct features that apply most suitably in particular areas. They are implemented on silicon chips with NMOS technology so that the multiplier most desirable for VLSI implementation can readily be ascertained.>

A novel VLSI design for a pipeline Reed-Solomon decoder is presented. The transform decoding technique used in a previous study is replaced by a time-domain algorithm through a detailed comparison of their VLSI implementations. An architecture that implements the time-domain algorithm permits efficient pipeline processing with reduced circuitry. Erasure correction capability is also incorporated with little additional complexity. By using multiplexing technique, an implementation of Euclid's algorithm maintains the throughput rate with less circuitry. Some improvements result in both enhanced capability and significant reduction in silicon area, making it possible to build the decoder on a single chip.>

A conventional prime factor discrete Fourier transform (DFT) algorithm of the Winograd type is used to realize a discrete Fourier-like transform on the finite field GF(q/sup /n). A pipeline structure is used to implement this prime-factor DFT over GF(q/sup /n). This algorithm is developed to compute cyclic convolutions of complex numbers and to aid in decoding the Reed-Solomon codes. Such a pipeline fast prime-factor DFT algorithm over GF(q/sup /n) is regular, simple, expandable, and naturally suitable for most implementation technologies. An example illustrating the pipeline aspect of a 30-point transform over GF(q/sup /n) is presented.>

A quadratic-polynomial Fermat residue number system (QFNS) can be used to compute the complex multiplications needed to perform a DFT. The advantage of such a QFNS is that complex multiplication can be accomplished with only two integer multiplications. In this paper, it is shown that a new set of numbers of the form Tn = 22n + 1 can be used in place of the set of Fermat numbers. This new quadratic residue number system can be used also to compute a complex multiplication with only two integer multiplications.

A new VLSI design of a pipeline Reed-Solomon decoder is presented. The transform decoding technique used in a previous design is replaced by a simple time domain algorithm. A new architecture which realizes such algorithm permits efficient pipeline processing with a minimum of circuits. A systolic array is also developed to perform erasure corrections in the new design. A modified form of Euclid's algorithm is developed with a new architecture which maintains a real-time throughput rate with less transistors. Such improvements results in both an enhanced capability and significant reduction in silicon area, thereby making it possible to build a pipeline (255,223) RS decoder on a single VLSI chip.

In this paper a recursive algorithm using the error-trellis decoding technique is developed to decode certain convolutional codes (CC's). An example, illustrating the VLSI architecture of such a decoder, is given for a dual-k CC. It is demonstrated that such a decoder can be realized readily on a single chip with NMOS technology.

In this correspondence, the complex integer multiplier and adder over the direct sum of two copies of finite field developed in [1] is specialized to the direct sum of the rings of integers modulo Fermat numbers. Such multiplication over the rings of integers modulo Fermat numbers can be performed by means of two integer multiplications, whereas the complex integer multiplication requires three integer multiplications. Such multiplications and additions can be used in the implementation of a discrete Fourier transform (DFT) of a sequence of complex numbers. The advantage of the present approach is that the number of multiplications needed to compute a systolic array of the DFT can be reduced substantially. The architectural designs using this approach are regular, simple, expandable and, therefore, naturally suitable for VLSI implementation.

Multiplication is central in the implementation of Fermat number transforms (FNT) and other residue number algorithms. There is need for a good multiplication algorithm which can be realized easily on a VLSI chip. In this paper, the Leibowitz multiplier [1] is modified to realize multiplication in the ring of integers modulo a Fermat number. The advantage of this new algorithm over Leibowitz's algorithm is that Leibowitz's algorithm takes modulo after the product of multiplication is obtained. Hence time is wasted. In this new algorithm, modulo is taken in every bit operation when performing multiplication. Therefore no time is wasted in this respect. Furthermore, this algorithm requires only a sequence of cyclic shifts and additions. The design for this new multiplier are regular, simple, expandable and therefore, suitable for VLSI implementation.

Multiplication is central in the implementation of Fermat Number Transforms (FNT) and other residue number algorithms. There is need for a good multiplication algorithm which can be realized easily on a VLSI chip. In this paper, the Leibowitz multiplier [1] is modified to realize multiplication in the ring of integers modulo a Fermat number. The advantage of this new algorithm over Leibowitz's algorithm is that Leibowitz's algorithm takes modulo after the product of multiplication is obtained. Hence time is wasted. In this new algorithm, modulo is taken in every bit operation when performing multiplication. Therefore no time is wasted in this respect. Furthermore, this algorithm requires only a sequence of cyclic shifts and additions. The design for this new multiplier are regular, simple, expandable and therefore, suitable for VLSI implementation.

A pipeline structure of a transform decoder similar to a systolic array is developed to decode Reed-Solomon (RS) codes. The error locator polynomial is computed by a modified Euclid's algorithm which avoids computing inverse field elements. The new decoder is regular and simple, and naturally suitable for VLSI implementation.

A pipeline structure of a transform decoder similar to a systolic array is developed to decode Reed-Solomon (RS) codes. An important ingredient of this design is a modified Euclidean algorithm for computing the error-locator polynomial. The computation of inverse field elements is completely avoided in this modification of Euclid's algorithm. The new coder is regular and simple, and naturally suitable for VLSI implementation. An example illustrating both the pipeline and systolic array aspects of this decoder structure is given for a RS code.

Finite field arithmetic logic is central in the implementation of Reed-Solomon coders and in some cryptographic algorithms. There is a need for good multiplication and inversion algorithms that can be easily realized on VLSI chips. Massey and Omura recently developed a new multiplication algorithm for Galois fields based on a normal basis representation. In this paper, a pipeline structure is developed to realize the Massey-Omura multiplier in the finite field GF(2m). With the simple squaring property of the normal basis representation used together with this multiplier, a pipeline architecture is developed for computing inverse elements in GF(2m). The designs developed for the Massey-Omura multiplier and the computation of inverse elements are regular, simple, expandable, and therefore, naturally suitable for VLSI implementation.

Berlekamp has developed for the California Institute of Technology Jet Propulsion Laboratory (JPL) a bit-serial multiplication algorithm for the encoding of Reed-Solomon (RS) codes, using a dual basis over a Galois field. The conventional RS encoder for long codes often requires lookup tables to perform multiplication of two field elements. Berlekamp's algorithm requires only shifting and EXCLUSIVE OR operations. It is shown in this paper that the new dual-basis (255,223) RS encoder can be realized readily on a single VLSI chip with NMOS technology.

Two systolic architectures are developed for performing the product–sum computation AB + C in the finite field GF(2m) of 2melements, where A, B, and C are arbitrary elements of GF(2m). The first multiplier is a serial-in, serial-out one-dimensional systolic array, while the second multiplier is a parallel-in, parallel-out two-dimensional systolic array. The first multiplier requires a smaller number of basic cells than the second multiplier. The second multiplier heeds less average time per computation than the first multiplier if a number of computations are performed consecutively. To perform single computations both multipliers require the same computational time. In both cases the architectures are simple and regular and possess the properties of concurrency and modularity. As a consequence they are well suited for use in VLSI systems.

In this paper a parallel architecture is developed to realize a digital filter. First a systolic array is used to compute a 248-point complex number-theoretic transform (CNT). Next an algorithm is developed to realize a digital filter that uses 248-point CNT's and a generalization of the overlap-save method. This algorithm solves the conflict between long transform lengths and a wide dynamic range associated with the number-theoretic transform. Finally this algorithm is mapped to a parallel architecture. This architecture is simple, regular and expandable, and, hence, is suitable for VLSI implementation.

In this paper, a parallel-pipeline, radix-2 architecture is proposed to implement the fast polynomial transform (FPT). It is shown that such a structure can be used to efficiently compute a two-dimensional convolution of d1× d2complex number points, where d1 = 2m-r+1and d2= 2mfor 1 ≤ r ≤ m.

In this correspondence, a parallel architecture is developed to compute the linear convolution of two sequences of arbitrary lengths using the Fermat number transform (FNT). In particular, a pipeline structure is designed to compute a 128-point FNT. In this FNT, only additions and bit rotations are required.

Recently,1 the authors proposed a hybrid algorithm for computing the discrete Fourier transform (DFT) of certain long transform lengths. In that technique, a Winograd-type algorithm was used in conjunction with the Mersenne prime-number theoretic transform to perform a DFT. Even though this technique requires fewer multiplications than either the standard fast Fourier transform (FFT) or Winograd's more conventional algorithm, it increases the number of additions considerably. In this letter it is proposed to use Winograd's algorithm for computing the Mersenne prime-number theoretic transform in the transform portion of the hybrid algorithm. It is shown that this can reduce significantly the number of additions while still maintaining about the same number of multiplications.

In this paper for certain long transform lengths, Winograd's algorithm for computing the discrete Fourier transform (DFT) is extended considerably. This is accomplisbed by performing the cyclic convolution, required by Winograd's method, with the Mersenne prime number-theoretic transform developed originally by Rader. This new algorithm requires fewer multiplications than either the standard fast Fourier transform (FFT) or Winograd's more conventional algorithm. However, more additions are required.

It is shown in this paper that the fundamental structure of Galois switching functions follows naturally from that of Boolean switching functions. An expanded formula for deriving multinomial Galois switching functions is provided with illustrations of its application.

The inner product computer is a special-purpose computational unit intended to be used as an adjunct to a general-purpose digital computer to perform numerical processing tasks which previously exceeded the capacity of the general-purpose computer. The algorithmic structure of the inner product is briefly reviewed in the first section of this paper. Methods are described for computing the inner product of complex vectors with a series of four real inner products. Several hardware implementations of the inner product computer are described and then compared in terms of speed and complexity; a figure of merit is developed to simplify the comparison. The utility of this computational unit is demonstrated via the examination of a large-scale numerical problem, computerized three-dimensional x-ray reconstruction (computerized tomography) arising in the biomedical sciences. Finally, a comparison is given of the size of a general-purpose computer required to execute a large-scale processing task with that of an inner product computer to execute the same task. The inner product computer greatly reduces computational costs for the solution of a large class of problems, including computerized tomography, image restoration, weather forecasting, and economic modeling.

Classes of codes for a multichannel communication system are considered. A fast algorithm is developed to calculate syndromes of multichannel linear systematic codes, including both block and convolutional codes, by using a direct sum of Galois fields.

It is shown that Reed-Solomon (RS) codes can be decoded by using a fast Fourier transform (FFT) algorithm over finite fieldsGF(F_{n}), whereF_{n}is a Fermat prime, and continued fractions. This new transform decoding method is simpler than the standard method for RS codes. The computing time of this new decoding algorithm in software can be faster than the standard decoding method for RS codes.

It is shown that\sqrt\[8]{2}is an element of order2^{n+4}inGF(F_{n}), whereF_{n}=2^{2^{n}}+1is a Fermat prime forn=3,4. Hence it can be used to define a fast Fourier transform (FFT) of as many as2^{n+4}symbols inGF(F_{n}). Since\sqrt[8]{2}is a root of unity of order2^{n+4}inGF(F_{n}), this transform requires fewer muitiplications than the conventional FFT algorithm. Moreover, as Justesen points out [1], such an FFT can be used to decode certain Reed-Solomon codes. An example of such a transform decoder for the casen=2, where\sqrt{2}is inGF(F_{2})=GF(17), is given.

A transform analogous to the discrete Fourier transform is defined on the Galois field GF(p), where p is a prime of the form k X 2n + 1, where k and n are integers. Such transforms offer a substantial variety of possible transform lengths and dynamic ranges. The fast Fourier transform (FFT) algorithm of this transform is faster than the conventional radix-2 FFT. A transform of this type is used to filter a two-dimensional picture (e.g., 256 X 256 samples), and the results are presented with a comparison to the standard FFT. An absence of roundoff errors is an important feature of this technique.

It is shown that a high-radix fast Fourier transform (FFT) with generator\gamma = 3over GF(F_{n}), whereF_{n} = 2^{2}^{n'} + 1is a Fermat prime, can be used for encoding and decoding of Reed-Solomon (RS) codes of length2^{2}^{n}. Such an RS decoder is considerably faster than a decoder using the usual radix 2 FFT. This technique applies most ideally to a 16-error-correcting, 256-symbol RS code of 8 bits being considered currently for space communication applications. This special code can be encoded and decoded rapidly using a high-radix FFT algorithm over GF(F_{3}).

Recursive filter design techniques are described and developed for finite impulse filters using finite field arithmetic. The finite fields considered have the formGF(q^{2}), the Galois field ofq^{2}elements, and are analogous to the field of complex numbers whenqis a prime such that(-1)is not a quadratic residue. These filters can be designed to yield either a desired finite impulse or finite frequency response function. This filtering technique has other possible applications, including the encoding or decoding of information and signal design. Infinite signal trains can be decomposed naturally into orthogonal sequences which may be useful in the encoding and decoding process and may provide another approach to convolutional coding. Since the recursive filters developed here do not have the accumulation of round-off or truncation error that one might expect in recursive computations, such filters are noise-free transducers in the sense of Shannon.

Encoding and decoding algorithms for Reed-Solomon codes based on Fourier-like transforms on finite field and finite rings are discussed. Classes of codes are proposed for two different types of multiple-user communication systems: a multichannel communication system and a multiaccess communication system. For the first system, a fast decoding algorithm is developed that uses transforms on a finite ring which is isomorphic to a direct sum of Galois fields. For the second system, an efficient (in terms of information rate) coding scheme is proposed which utilizes a direct sum of Galois fields.

The Boolean difference expansion of Boolean algebra is generalized to finite (Galois) fields. A systematic method is provided for calculating the coefficients of this type of multivariable polynomial expansion. It is applied then to the synthesis functions. Applications include multivalued logics as well as binary-valued logics.

A Fourier-like transform is defined over a ring of quadratic integers modulo a prime numberqin the quadratic fieldR(\sqrt{m}), wheremis a square-free integer. Ifqis a Fermat prime, one can utilize the fast Fourier transform (FFT) algorithm over the resulting finite fields to yield fast convolutions of quadratic integer sequences inR(\sqrt{m}). The theory is also extended to a direct sum of such finite fields. From these results, it is shown that Fourier-like transforms can also be defined over the quadratic integers inR( \sqrt{m})modulo a nonprime Fermat number.

A transform is defined in the Galois field ofq^2elementsGF(q^2), a finite field analogous to the field of complex numbers, whenqis a prime such that (--1) is not a quadratic residue. It is shown that the action of this transform overGF(q^2)is equivalent to the discrete Fourier transform of a sequence of complex integers of finite dynamic range. Ifqis a Mersenne prime, one can utilize the fast Fourier transform (FFT) algorithm to yield a fast convolution without the usual roundoff problem of complex numbers.

In this paper, the dynamic range of Fourier-like transforms over the Galois fieldGF(q^2), whereqis a Mersenne prime, is extended. It is shown that transforms over a direct sum of such Galois fields can be used to compute quite accurately discrete Fourier transforms of complex numbers without roundoff error.

Properties of arithmetic norms of integers are applied to the study of arithmetic BN modulo A codes. Some new properties of such codes are established. Bounds on the size of such codes are derived and an efflcient algorithm for finding the optimal single and double error-correcting BN modulo A codes is developed.

A tool employed in automated fault diagnosis is emphasized: path sensitization by partial Boolean difference analysis. Motivated by the analogy between a test system and a communication system, a model for fault detection of a logic net is outlined from the standpoint of information theory. The classical ``path sensitizing'' technique is made systematic using the partial Boolean difference. This technique is based on a new theorem on the partial Boolean difference. Finally, a programmable fault detection algorithm is presented along with an example.

A synthesis procedure for failure-tolerant sequential circuits using error-correcting codes is presented. Coding redundancy is then compared with replication as to circuit complexity and reliability improvement. Using appropriate assumptions, it is shown that for a specified ability to tolerate failures, replication yields better circuit reliability than coding redundancy. When circuit complexity as well as reliability are taken into consideration, it is shown that schemes based on orthogonizable codes generally provide a greater improvement in reliability for a given complexity than replication. As in any redundant scheme, these results presuppose reasonably good reliabilities for irredundant circuits.

A systematic procedure for constructing one member of each cyclic equivalence class of an(n, k + 1)Reed-Solomon code is presented. It is shown that if the procedure is modified to exclude those codewords that do not have maximum period, the resulting set of codewords constitutes a synchronizable code having comma freedom of degreen - 2k.

This paper delineates an application of two classes of parity-check codes to the design for failure-tolerant counters. They are 1) a modified first-order Reed-Muller code and 2) the perfect Hamming code. The first code employs a majority element for implementing the error-correcting scheme while the second one makes use of a variable 2j-2+1-out-of-2j-1+1 majority element. These coding techniques can be applied in principle to other logic hardware to increase its reliability.

An equivalence between the rank permutation codes and a new class of binary codes has been observed. A binary code may be generated by direct transformation of a permutation code. The binary codes are usually nonlinear and may be decoded by the inverse transformation and rank correlation of the equivalent permutation.

Properties of integers, related to the generation of the arithmetic AN codes, are investigated in this paper. A programmable algorithm for the computation of the binary norm of an arbitrary integer is developed. A table of norms of the natural numbers is generated and from this the distribution of integers of a given norm is found. These results are used to compute bounds on the size of ane-fold or less error-correcting AN code and to derive some further properties of single- and double-error-correcting AN codes.

article Free AccessA Generalization of Shift-Register Sequence Generators Authors: I. S. Reed The Rand Corporation, Santa Monica, California The Rand Corporation, Santa Monica, CaliforniaView Profile , Rein Turn The Rand Corporation, Santa Monica, California The Rand Corporation, Santa Monica, CaliforniaView Profile Authors Info & Claims Journal of the ACMVolume 16Issue 3July 1969 pp 461–473https://doi.org/10.1145/321526.321535Published:01 July 1969Publication History 3citation460DownloadsMetricsTotal Citations3Total Downloads460Last 12 Months7Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

In a coherent search rader, the pulse-to-pulse Doppler shift of a signal is generally not known a priori. Given the distribution of this parameter, the best test variable for detection is the average of the likelihood ratio with respect to target Doppler frequency. Most coherent search radars employ a maximum-likelihood ratio detector, that is, a bank of independent Doppler filters, for detection. The average-likelihood and maximum-likelihood tests are compared here for a target with the Rayleigh amplitude distribution. It is shown that, over a wide range of detection and false-alarm probabilities, the performances of the two tests do not differ significantly. For this target model, the likelihood ratio has the Pareto distribution, which arises in some statistical problems in economics. The new results obtained here for the distribution of the sum of two or more Pareto-distributed variables are of considerable general interest.

In this paper biorthogonal codes are generalized in a natural way to a class of codes, calledN-orthogonal codes.N-orthogonal codes consist ofN^{M}signals divided intoN^{M-1}disjoint sets ofNsignals where signals in different sets are uncorrelated or orthogonal. One instance of theN-orthogonal codes is realized as a class of polyphase, constant-power modulated signals, the admissible phase set being denoted byN^{th}roots of unity. Matched filter receiver criteria for the Gaussian channel are developed and simplified integral expressions for the probability of error are derived.

A method is developed for the design of arbitrary length counters using three-input majority elements. The iterative nature of the design leads to circuits of extreme simplicity and regularity. The system is dc triggered, hence operating correctly regardless of the rise time or width of the clock signal. As the method does not utilize master-slave techniques, only a single-phase clock is required. A practical embodiment of the system is presented, giving correct operation at clock rates in excess of 50 Mc/s. With more sophisticated high-speed circuitry, correct operation at clock rates in excess of 100 Mc/s should be readily attainable.

The importance of designing a radar (or communications) receiver to operate effectively in the presence of spatial noise creates the necessity for determining the space-time cross-correlation functions between antenna array elements. A representation of a general, polarized, nonisotropic noise process is used to determine the cross-spectral densities and cross-correlation functions between arbitrarily oriented dipole antenna array elements in the presence of a noise field only. Several examples have been worked out for isotropic noise to show the variation of the cross-correlated noise function vs. the spatial separation of the dipoles. One important result is that the noise cross correlation is shown to be a function of the receiver element spatial orientation when the elements are dipoles. For certain spatial orientations between dipoles it is possible to reduce the noise cross correlation between these antenna array elements to zero.

Sequential analysis has been used in the literature for analyzing a radar search system. The procedure is to continually sample a given range "bin" until a yes-no decision concerning the presence of a target is made. The results, however, do not provide for the possibility of a target emerging into the bin during the sampling process. In this report we consider a likelihood-ratio test for detecting emerging targets by sequential sampling. It is shown that the decisioning threshold must be continually increased in order to maintain a fixed false alarm rate at each sample. An upper bound on the average number of samples required to detect an emerging target is computed, and the results are significant in that this bound may become quite large. A test using a fixed threshold in which the average false alarm rate is constrained is investigated and shown to be inferior to the variable threshold test. A suboptimum test using only a finite number of past samples is also considered. The results of this study are equally applicable to the converse problem, i.e., detecting when a known target exits from the bin, which is important in target tracking.

An approximate distribution is computed for the envelope of sine wave plus noise after passage through a wide-band filter, limiter, and narrow-band filter. It is shown that as the input bandwidth to the limiter increases, the output envelope distribution converges to the usual sine wave in noise envelope distribution, without limiting, but with a definite1.04db loss. First-order correction terms are supplied which make it possible to compute first-order statistics for the output envelope when the output signal-to-noise ratio is on the order of one.

Abstract : Consideration is given to a simple sequential test for the presence of a signal known except for one parameter i. This parameter may assume only one of k discrete values, k < infinity. The distribution of the true parameter value is assumed to be uniform over the parameter space. It is shown that the test is almost a maximum likelihood test. Next it is shown how to set the test parameters in order to achieve desired conditional error probabilities, and an approximate expression is obtained for the distribution of the test termination time. (Author)

In this paper we define a subclass of comma-free codes which has a property called path invariance. The main advantage of codes in this subclass lies in the ease of establishing the positions of the divisions between words. Certain path-invariant comma-free dictionaries usingKsymbols to form n-symbol words are developed and their properties are studied. The number of words in these dictionaries is determined to beL(K-L)^{[n/2]}K^{[(n-1)/2]}whereLis a parameter which equals one whenn \geq 4K/3, and[x]denotes the integral part ofx. That this is the maximum obtainable dictionary size is proved for a special case. The ability of these codes to correct registration (synchronization) errors whennconsecutive symbols are available (as opposed to the2nconsecutive symbols required by general fixed-word-length comma-free codes) is demonstrated. A comparison of dictionary sizes is made for path-invariant comma-free codes, general fixed-word-length comma-free codes, and codes using one symbol as a comma. In the rangeK \leq 6andn \leq 9the path-invariant dictionaries are about\frac{1}{2}to\frac{3}{4}the size of the corresponding general comma-free dictionaries. Asymptotic dictionary sizes are obtained forK \rightarrow \inftyand forn \rightarrow \infty.

A general theorem is provided for the moments of a complex Gaussian video process. This theorem is analogous to the well-known property of the multivariate normal distribution for real variables, which states that annth order central product moment is zero ifnis odd and is equal to a sum of products of covariances whennis even.

In determining location in a previously mapped region by map-matching, there arises the question of minimum submap size relative to the size of the complete map of the region for unambiguous determination of position. A lower bound for the size of the submap is obtained for quantized binary maps. It is shown that there exist maps (called perfect) such that this lower bound is realized. Of special interest is the construction of a doubly periodic4 \times 4perfect map for a2 \times 2submap. The two-dimensional analogy of perfect maps to shift register codes suggests a possible development of planar error-correcting codes and an application to the two-dimensional range-velocity ambiguity problem of radar.

A class of procedures for detection of a pulsed signal having unknown frequency shift is described. From this class, procedures can be selected whose detection performance approximates that of coherent detection arbitrarily closely. Such procedures do not require the construction of a filter bank; on the other hand, they do not yield information as to the magnitude of the frequency shift of a detected signal. Envelope detection followed by video integration, and Reed's so-called semicoherent procedure are elements of this class of detection procedures. An iterative method for obtaining successively better approximations to coherent detection is described, the implementation of which would require a large number of mixing and delay operations. The number of iterations required to insure any given degree of approximation to coherent detection, for any number of integrated pulses, is estimated. Finally, the possible application of these ideas to reception of signals by array antennas is described.

As a consequence of a recent communication from D.G. Lampard of Sidney, Australia, the author wishes to make a correction in his recent paper ("On the use of Laguerre polynomials in treating the envelope and phase components of narrow-band Gaussian noise," IRE Transactions on Information Theory, vol. IT-5, pp. 102-105; September, 1959) in which the following sentence appears: "Eq. (4) does not seem to have been observed before except by Levin6 whose formula is in error." Mr. Lampard kindly points out that (4) has been observed before by several other authors, including himself.

The joint probability density of the envelope of a Gaussian process at two different times is expanded by the use of Hardy's identity into a series involving Laguerre polynomials. It is shown how this result may be used to estimate the cross-correlation function of the output of two quite general envelope-distorting filters. A generalization of this result, involving the use of the associated Laguerre polynomials, is obtained and applied to the calculation of a cross-correlation function which involves both the phase and envelope of the process at two points in time.

An analysis of the detection and location of repetitive signals in noise by digital techniques is made. The problem of location of the center of signals, herein denoted as beam-splitting, is explored. A Monte Carlo method employing a high speed digital computer was used to obtain quantitative results for a variety of digital detectors. A method of mathematical analysis is described and used to check computed results. The work described differs from much of the previous literature on detection or statistical decision theory in that an estimate of signal location is demanded.

linear error-correcting codes used in communications. (14) I. S. Reed, “A class of multiple-errorcorrecting codes and the decoding scheme,” IRE. Trans. A class of multiple-error-correcting codes and the decoding scheme. more. less. I. Reed · Details · Authors · Fields of science · Bibliography · Quotations · Similar. linear error correcting codes used in communications (2).For bit study is to device a coding scheme which is able to detect and correct such errors (6). (8) Reed, I. S., 'Class of multiple error correcting codes and their decoding scheme'.