The authors develop a coding theory approach to error control in residue number system product codes. Based on this coding theory framework, computationally efficient algorithms are derived for correcting single errors, double errors, and multiple errors, and simultaneously detecting multiple errors and additive overflow. These algorithms have lower computational complexity than previously known algorithms by at least an order of magnitude. In addition, it is noted that all the literature published thus far deals almost exclusively with single error correction.>

Errors caused by the finite wordlength of the computer in several popular algorithms in linear prediction are studied. Both the classical algorithms and the split cases of the classical algorithms are superior to other algorithms since the errors of computation at each stage propagate more slowly than in the Levinson and Schur cases. The results of the Levinson and Schur algorithms are almost the same. For the split cases, the errors accumulate much faster than in the classical situations since the three-term recurrence is used.>

The authors explore the numerical stability properties of the split Levinson algorithm for computing the predictor polynomial associated with a positive-definite real symmetric Toeplitz matrix. Various bounds on the residual vector are derived for the fixed-point and floating-point implementation of the algorithm. These bounds are similar in form to the bounds derived by G. Cybenko (1980) for the Levinson algorithm and are obtained by converting a three-term recurrence for the error vector to an equivalent two-term recurrence. The split Levinson algorithm is shown to be weakly stable.>

The mathematical structure associated with the split algorithms for computing the reflection coefficients for a given real symmetric positive-definite Toeplitz matrix is analyzed. A novel form of three-term recurrence relation is derived and computationally efficient alternatives to the Levinson-Durbin, Schur, and lattice algorithms are obtained. The computational complexity of the proposed algorithms is the same as those of the split algorithms described in recent literature. These algorithms provide further insight into the mathematical properties of the structurally rich Toeplitz matrices.>

The stepup (stepdown) procedure is an algorithm for computing the predictor polynomial (reflection) coefficients from the knowledge of the reflection coefficients (predictor polynomial). Here, both real as well as complex cases are considered, and several computationally efficient algorithms for the stepup and stepdown computations are presented. They are intimately related to recently reported alternative algorithms for computing the predictor polynomial associated with real, symmetric, and Hermitian Toeplitz matrices.>

The computational aspects of the algorithms for testing the strict sense and wise sense stability of discrete-time systems are studied. These algorithms are based on the computation of the reflection coefficients for a given real polynomial. The algorithms presented require one-half the number of multiplications and the same number of additions as compared to previously known similar algorithms.>

The author describes an algorithm for computing the characteristic polynomial of a tridiagonal matrix. It is quite general and consists in the application of the divide-and-conquer technique to the evaluation of a three-term recurrence relation. The algorithm developed requires O(n log/sup 2/n) arithmetic operations as compared to the classical algorithm that requires O(n/sup 2/) arithmetic operations.>

This work extends, unifies and generalizes the relationships between classical polynomial and matrix theory as it relates to the Levinson recurrence for a Hermitian Toeplitz operator. Several new classes of computationally efficient algorithms are presented for the Levinson recurrence on polynomial spaces satisfying certain symmetry properties. This approach also leads to new algorithms for solving systems of linear equations when the coefficient matrix is Hermitian Toeplitz. These algorithms lead to significant improvements in the computational complexity as compared to the previously best known recursive algorithms. They also provide further insight into the mathematical properties of the structurally rich Toeplitz matrices.

This paper introduces the concept of a generalized hybrid ARQ (GH-ARQ) scheme for adaptive error control in digital communication systems. This technique utilizes the redundant information available upon successive retransmissions in an efficient manner so as to provide high throughput during poor channel conditions. A new class of linear codes is proposed for the GH-ARQ system application. The main feature of this class of codes is that the encoder/decoder configuration does not change as the length of the code is varied. As a result, the receiver uses the same decoder for decoding the received information after every retransmission while the error correcting capability of the code increases, thereby leading to an improved performance and minimum complexity for the overall system implementation.

In this work, we study restoration of digital images degraded by white and colored noise using the Wiener filtering technique. It has been established that the Karhunen-Loeve transform (KLT) of the covariance matrix of a first order Markov process can be closely approximated by the discrete cosine transform (DCT) [1]. This property is used to establish that the Wiener filtering equations for an (n × n) image (a linear system of order n2) degraded by white noise can be transformed using the DCT to obtainnsets of linear equations, each of ordern. The solution for each of thensystems can be computed inO(n)computations. Thus, the complete algorithm requiresO(2n^{2}\log_{2}n)computations, which is approximately half of the computations required for the previously described algorithms [2]. Also, it is shown that the approximation of the KLT by DCT may be interpreted as a modification in one of the boundary conditions (horizontal or vertical) of the noisy image. The algorithms obtained are generalized to include the case of images degraded by colored noise. The rise in computational complexity of the algorithm for such a case is marginal.

A new iterative image restoration method is presented which incorporates a priori knowledge concerning the image and noise statistics directly in the iterative procedure. The iterative algorithm is computationally efficient in that only a small number of computations per pixel are required and appears to exhibit neither high noise sensitivity nor significant loss of resolution. It is demonstrated that for image signal-to-noise ratio,L, greater than someL_{\min}, the procedure converges to the best mean-square estimate of the image. The value ofL_{\min}is derived and shown to depend on the correlation parameters of the image model. The basic iterative algorithm is then modified so that the modified algorithm converges to the best mean-square estimate of the image for all values of L. An interesting feature of this technique is that the noisy observed image is taken as the initial approximation to the best estimate. In general, an attractive advantage of iterative algorithms for image restoration is that they readily facilitate man-machine interaction.

In general, the direct solution of an n-dimensional system of linear, equations requires O(n3) arithmetic operations. Frequently in high data rate signal processing, fast algorithms of complexity order3are required to solve a large system of linear equations. In several interesting applications, the specific structure of the coefficient matrix associated with the linear system may be used to reduce the required number of operations. Fast algorithms have been developed when the coefficient matrix is a Toeplitz matrix, a Hankel matrix, or when it can be represented as a sum of Toeplitz and Hankel matrices. The arithmetic complexity associated with these fast algorithms is O(n2). In this paper, fast algorithms of O(n) are presented that can be used for a class of matrices called diagonal innovation matrices (DIM). Previous results for this class of matrices require an arithmetic complexity of O(n2). A number of results are presented regarding the linear problems in signal processing with such matrices and several special cases are studied. The effect of recursively increasing the order of the coefficient matrix on the number of operations is studied and some observations are made.