A new algorithm which solves a Toeplitz system having t unknowns with computational complexity of 0(t2) is proposed. The solving algorithm is based upon iterative solutions of Toeplitz systems for sub-Toeplitz-matrices of the given Toeplitz matrix and works well even when some of the sub-Toeplitz-matrices is singular. That is, the solving algorithm is a generalized version of the Levinson algorithm in the sense that its solving process is quite similar to that of the Levinson algorithm and it overcomes the defect which the Levinson algorithm possesses. We may expect that the accuracy of the new solving algorithm is superior to those of the Brent-Gustavson-Yun algorithm and the solving algorithm based upon Euclid algorithm, when the given Toeplitz matrix is a type of matrices such as a covariance matrix, since the former algorithm uses sub-Toeplitz-matrices and the latter algorithms use sub-Hankel-matrices.

An algorithm for solving a discrete-time Wiener-Hopf equation is presented based upon Euclid's algorithm. The discrete-time Wiener-Hopf equation is a system of linear inhomogeneous equations with a given Toeplitz matrix M, a given vector b, and an unknown vector\lambdasuch thatM\lambda = b. The algorithm is able to find a solution of the discrete-time Wiener-Hopf equation for any type of Toeplitz matrices except for the all-zero matrix, while the Levinson algorithm and the Trench algorithm are not available when at least one of the principal submatrices of the Toeplitz matrixMis singular. The algorithm gives a solution, if one exists, even when the Toeplitz matrixMis singular, while the Brent-Gustavson-Yun algorithm only states that the Toeplitz matrixMis singular. The algorithm requiresO(t^{2})arithmetic operations fortunknowns, in the sense that the number of multiplications or divisions is directly proportional tot^{2}, like the Levinson and Trench algorithms. Furthermore, a faster algorithm is also presented based upon the half greatest common divisor algorithm, and hence it requiresO(t \log^{2} t)arithmetic operations, like the Brent-Gustavson-Yun algorithm.

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

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

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

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

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

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

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

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

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

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