We develop methods for estimating the number of components in the Varshamov graph of a linear code and derive some new lower bounds on minimum distance for nonbinary codes.

We establish the existence and give constructions of two new classes of quasicyclic irreducible Goppa codes. We give simple numerical conditions on the degree of the Goppa polynomial and length of an irreducible Goppa code which are sufficient conditions for it to be a member of one of these classes.

We present a new algorithm for generic multiplicative computations of the form ab/c in GF(p/sup m/), including multiplication, inversion, squaring, and division. The algorithm is based on solving a sequence of congruences that are derived from the theory of Grobner bases in modules over the polynomial ring GF(p)[x]. Its corresponding hardware and software architectures can be successfully used in applications such as error control coding and cryptography. We describe a versatile circuit associated with the algorithm for the most important case p=2. The same hardware can be used for a range of field sizes thus permitting applications in which different levels of error control or of security are required by different classes of user. The operations listed are all performed by the hardware in the same number of clock cycles, which prevents certain side-channel attacks. The loss in performance by having 2m iterations for multiplication is compensated by the full parameterization of the Galois field and the ability to perform division and multiplication in parallel.

The standard decoding procedure for alternant codes over fields centers on solving a key equation which relates an error locator polynomial and an error evaluator polynomial by a syndrome sequence. We extend this technique to decode alternant codes over Galois rings. We consider the module M={(a, b): as/spl equiv/b mod x/sup r/} of all solutions to the key equation where s is the syndrome polynomial and r, is the number of rows in a parity-check matrix for the code. In decoding we seek a particular solution (/spl Sigma/, /spl Omega/)/spl isin/M which we prove can be found in a Grobner basis for M. We present an iterative algorithm which generates a Grobner basis modulo x/sup k+1/ from a given basis modulo x/sup k/. At the rth step, a Grobner basis for M is found, and the required solution recovered.

The use of backward error assertions combined with iterative refinement has been suggested for the correction of small fault induced errors in the floating point solution of linear systems. We extend this to the correction of large errors, typically caused by the failure of a single processor (or column of processors) in an array.

We consider the set M.>

The authors present a fault tolerant algorithm for the solution of linear systems of equations using matrix triangularization procedures suitable for implementation on array architectures. Gaussian elimination with partial or pairwise pivoting and QR decomposition are made fault tolerant against two transient errors occurring during the triangularization procedure. The extended Euclidean algorithm is implemented to solve for the locations and values of the errors defined appropriately using the theory of error correcting codes. The Sherman-Morrison Woodbury formula is then used to obtain the correct solution vector to the linear system of equations without requiring a valid decomposition.>

The extended Euclidean algorithm (XEA) is the basis of one of the methods used for solving the key equation which arises in decoding Reed-Solomon error correcting codes. The algorithm is implemented using an Advanced Micro Devices electrically programmable gate array (EPGA) development system. This PC based software uses ORCAD schematic entry and simulation in conjunction with an AMD interface. EPGAs were chosen for the circuit design because of the ease of obtaining a silicon prototype once the circuit has been verified. The facility for direct programming of the IC from the PC means circuit revisions in hardware are quickly realized; this, coupled with efficient entry and simulation package, gives a much speedier design cycle than conventional masked silicon approaches. The advantages of the algorithm over existing designs are noted.>

An n-dimensional linear recurring sequence ( sigma ) of elements from a field F, for n>or=1 is considered. An algorithm chi -BASE which determines a basis for the ideal characteristic polynomials of ( sigma ) under certain reasonable conditions is presented. This analysis applied to doubly periodic arrays in particular.>