A fundamental parallel procedure of implementing certain algorithms is by means of trees and arrays. A method of generating any function defined by a power series in a fast, efficient parallel-acting manner using trees and arrays is described. The power series considered can be written as f(Y)=a/sub 0/+a/sub 1/Y+a/sub 2/Y/sup 2/+...where Y=v/sub 1/x+V/sub 2/x/sup 2/+...+v/sub k/x/sup k/,v/sub i/=(0, 1), is a binary fraction when x=1/2. The power series must be expanded into individual terms cx/sup 1/. These terms are then transformed into weighted binary terms. Two methods are given to obtain all the individual terms (including coefficients) associated with each power of x. The hardware required for implementation is a tree similar to a Wallace or Dadda tree used for parallel multiplication of two binary numbers. Despite the multiplicity of terms required, Boolean logic methods reduce the tree dimensions in many cases so that the total tree required is smaller than an existing multiplier tree. In that case, Schwarz and Flynn (1993), have shown that the required tree can be superimposed on the existing multiplier tree in a multiplexed manner with relatively little increase in hardware. The generation of the logarithmic function is described in detail. Comparisons with other methods are made for the case of 11 bit accuracy of the logarithm. Using a figure of merit of latency times area (number of transistors), estimates show that the superposition scheme gives the best (smallest) figure of merit. For 11 bit accuracy, the superposition scheme requires only about 480 additional gates to be superimposed upon a 41 bit or larger multiplier, and the speed of operation is that of the multiplier.

Two trees are used sequentially to calculate an approximation to 1/A, where 1/spl les/A>

A variation of a division method previously presented by the author (1990) is described. The method is of the SRT type. This present scheme is based upon a system of recursion equations derived from the equation 1/A=Q. Its advantages are presented.>

It is shown that, if a division is described by AQ=C, where A is the divisor, Q is the quotient, and C is the dividend, then the bit variables involved in a set of equations, each of which determines a leading bit of C, gives an approximation for Q that an be used in a SRT division scheme. The results of an exhaustive statistical simulation, using all possible combinations of two pairs of integers 12 b in length, in normalized form, representing A and C are presented to validate the method.>

Iterative arrays are described which implement the extended Euclidean algorithm over finite fields with characteristic two and are designed to have throughputs in the area of hundreds of megabits per second. A special form of the Euclidean algorithm is the basis of these arrays, which can be used for error decoding. The propagation time through the array is derived as a function of the degree of the input polynomials.>

It is reported that two optimal type-B1 burst correcting convolutional codes of rate 4/5 were found by computer search. The B/sub 0/ matrices of these codes are given. In octal, the columns are written as (53,357,756,1555,1000) and (53,357,1555,1203,1000), respectively.>

A property of subsequences in arithmetic or decimal sequences is proved. This property has a somewhat similar counterpart for linear-feedback shift register (LFSR) sequences discovered by J.L. Massey (1969). However, it is proved in a different manner, and the limit bound is two units away from the corresponding LFSR property. This property holds for any radix, but the conditions depend somewhat on the radix.>

It is shown how the use of relatively sparse polynomials, including p-polynomials and trace polynomials, can be used as intermediate divisors in the Goertzel transform over a finite field to reduce the number of additions. The number of multiplications can also be reduced if the characteristic of the field is larger than two. These methods can also be used in preliminary stages of a finite-field Winograd transform. Applications are for the decoding of Reed-Solomon and Bose-Chaudhuri-Hocquenghen codes in the spectral mode.

The Berlekamp algorithm used for generating convergents (polynomial fractions) to a polynomial sequence is altered for use with binary numbers. This provides an alternative to continued fraction generation of convergents, and the proposed algorithm uses no division. However optimality has not been proved unlike the case for the Berlekamp algorithm with polynomial sequences.

A method is presented for decoding erasures and errors in Reed-Solomon (RS) codes over GF(q). It uses fewer operations when the code is of medium or low rate, when the number of erasures is relatively large, and whenq-1is prime. This method can be used in conjunction with the customary method of decoding RS codes and can decrease the maximum number of operations needed to decode certain codes. This procedure is also applicable to generalized RS codes of lengthqover GF(q).

A more accurate designed distance bound is given for a subclass of narrow-sense primitive Bose-Chaudhuri-Hocquenghem (BCH) codes for which Mann has found the number of information digits. It is also determined when two consecutive odd integers are in the same cyclotomic coset.

A generalized and unified method of interpolation and transformation is used to generate all known maximal distance codes and important subfield subcodes. Some powerful tools for the analysis and synthesis of maximal distance codes are presented, as well as a generalization of the Mattson-Solomon polynomial and Lagrange and Fourier transforms to more general functions. In certain cases new codes can be obtained by differentiating a kernel function. Some further generalizations of Srivastava codes are constructed. A general method of decoding is given which can be used for complete decoding of ali coset leaders.

In a previous correspondence, a decoding procedure which uses continued fractions and which is applicable to a wide class of algebraic codes including Goppa codes was presented. The efficiency of this method is significantly increased.

A decoding algorithm for a class of multiple error-correcting arithmetic residue codes can be made siginificantly more efficient.

It is shown how the theory of continued fractions for polynomials can be used for the decoding of a class of codes which contains Goppa codes.

Multiple-error-correcting arithmetic codes which are nonlinear are constructed by residue encoding. A simple algorithm is given for correcting multiple errors which makes use of continued fractions.

It is shown that Goppa codes can be derived by means of the Chinese remainder theorem from codes previously constructed.

A method is proposed that utilizes punctured Reed-Solomon (RS) block codes for adaptive coding. Part of the redundancy of the RS codewords is used in a convolutional coding framework. This enables some codewords to use more redundancy for correcting errors, while other adjacent codewords use less redundancy.

A feedback decision scheme is proposed in which a punctured codeword is initially transmitted. If an uncorrectable error is detected, the receiver signals the transmitter to send another increment of redundancy. This procedure is continued if the aggregated word is still uncorrectable.

Rate\frac{3}{4}optimal type-B1burst-error-correcting convolutional codes have been discovered. Optimal codes of rate1/n_oand\frac{2}{3}are also given. A method of decoding is described.

A binary double-phased-burst-error-correcting block code of rate 1/2 has been discovered by computer search. This code is quasi-cyclic, has a total burst-length-to-redundancy asymptotic ratio of 2/5, and is quite easily decodable. It can correct two phased-burst errors, each of length two digits or less. To correct larger nonphased bursts, interleaving is required.

It is shown how to detect or correct synchronization slippage in cyclic codes by using a prefix that incorporates the Fibonacci encoding technique developed by Kautz. Comparison with other methods shows that in many cases it seems to be more efficient. Implementation is simple. It is also shown how a similar technique can be used in comma-free codes. The resulting codes can be constructed algorithmic, ally from arbitrary information digits, that is, no table lookup is necessary. These codes seem to be the most efficient among those that require no code table.

A class of quasi-cyclic multiple-burst-error-correcting codes are constructed in which threshold decoding is used. These codes resemble the interlaced self-orthogonal quasi-cyclic random-error-correcting codes constructed by Townsend and Weldon, but the interlacing depends on the parity-check equations used. These parity-check equations are based on difference triangles that were introduced by Robinson and Bernstein in connection with convolutional codes. A restriction on these codes is that the maximum error burst length allowable is a multiple of a subperiodn_oof the codes. It is shown that in many cases these codes have shorter length than the equivalent interlaced random-error-correcting quasi-cyclic codes.

In this correspondence some classes of unequal protection codes are constructed utilizing difference sets or triangles. These codes use threshold decoding.

An extension of Tong's burst-trapping technique is presented that allows usage in more complex channels. In particular, the guard space after a burst need not be error free, but must contain a smaller number of random errors than normal. Special types of codes are needed for this method, such that some redundancy can be discarded and the remaining word can still correct for errors on a reduced scale. Examples are given.

It is shown how nonsystematic Reed-Solomon (RS) codes encoded by means of the Chinese remainder theorem can be decoded using the Berlekamp algorithm. The Chien search and calculation of error values are not needed but are replaced by a polynomial division and added calculation in determining the syndrome. It is shown that for certain cases of low-rate RS codes, the total decoding computation may be less than the usual method used with cyclic codes. Encoding and decoding for shorter length codes is presented.

Arithmetic codes are error-correcting or detecting codes implemented by ordinary arithmetic operations. Arithmetic codes with large distance, and therefore, capable of multierror correction are constructed. These codes are analogous to the finite field codes corresponding to maximal recurring sequences generated by shift registers whose characteristic polynomial is a primitive polynomial. These arithmetic codes are generated by the recurring sequence formed by the inverse of a prime having two as a primitive root. The distance as well as the redundancy increases with the code length. These codes have large redundancy but may be useful in specialized cases. Since the difference between a cyclic shift of a code word and the code word itself is another code word, a two-level function can be formed and the code used as an acquirable code. They can detect error bursts whose length is half the code length. A generalized burst-error correcting code is constructed and it is pointed out that the above large distance codes may be utilized in the construction of this burst-error code.