Engineering topics

Reed, I. S.

Publications and source records attributed to Reed, I. S..

At least 37 records · Page 2

NASA NTRS1987

A VLSI architecture of a binary updown counter

A pipeline binary updown counter with many bits is developed which can be used in a variety of applications. One such application includes the design of a digital correlator for very long baseline interferometry (VLBI). The advantage of the presently conceived approach over the previous techniques is that the number of logic operations involved in the design of the binary updown counter can be reduced substantially. The architecture design using these methods is regular, simple, expandable and, therefore, naturally suitable for VLSI implementation.

Reed, I. S.↗

NASA NTRS1986

Techniques for computing the discrete Fourier transform using the quadratic residue Fermat number systems

The complex integer multiplier and adder over the direct sum of two copies of finite field developed by Cozzens and Finkelstein (1985) 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.

Truong, T. K.↗

NASA NTRS1986

The VLSI design of an error-trellis syndrome decoder for certain convolutional codes

A recursive algorithm using the error-trellis decoding technique is developed to decode convolutional codes (CCs). An example, illustrating the very large scale integration (VLSI) architecture of such a decode, is given for a dual-K CC. It is demonstrated that such a decoder can be realized readily on a single chip with metal-nitride-oxide-semiconductor technology.

Reed, I. S.↗

NASA NTRS1986

A VLSI architecture for performing finite field arithmetic with reduced table look-up

A new table look-up method for finding the log and antilog of finite field elements has been developed by N. Glover. In his method, the log and antilog of a field element is found by the use of several smaller tables. The method is based on a use of the Chinese Remainder Theorem. The technique often results in a significant reduction in the memory requirements of the problem. A VLSI architecture is developed for a special case of this new algorithm to perform finite field arithmetic including multiplication, division, and the finding of an inverse element in the finite field.

Hsu, I. S.↗

NASA NTRS1986

A new VLSI complex integer multiplier which uses a quadratic-polynomial residue system with Fermat numbers

A quadratic-polynomial Fermat residue number system (QFNS) has been used to compute complex integer multiplications. The advantage of such a QFNS is that a complex integer multiplication requires only two integer multiplications. In this article, a new type Fermat number multiplier is developed which eliminates the initialization condition of the previous method. It is shown that the new complex multiplier can be implemented on a single VLSI chip. Such a chip is designed and fabricated in CMOS-pw technology.

Truong, T. K.↗

NASA NTRS1986

VLSI Architectures for Computing DFT's

Simplifications result from use of residue Fermat number systems. System of finite arithmetic over residue Fermat number systems enables calculation of discrete Fourier transform (DFT) of series of complex numbers with reduced number of multiplications. Computer architectures based on approach suitable for design of very-large-scale integrated (VLSI) circuits for computing DFT's. General approach not limited to DFT's; Applicable to decoding of error-correcting codes and other transform calculations. System readily implemented in VLSI.

Truong, T. K.↗

NASA NTRS1986

Simplified Decoding of Convolutional Codes

Some complicated intermediate steps shortened or eliminated. Decoding of convolutional error-correcting digital codes simplified by new errortrellis syndrome technique. In new technique, syndrome vector not computed. Instead, advantage taken of newly-derived mathematical identities simplify decision tree, folding it back on itself into form called "error trellis." This trellis graph of all path solutions of syndrome equations. Each path through trellis corresponds to specific set of decisions as to received digits. Existing decoding algorithms combined with new mathematical identities reduce number of combinations of errors considered and enable computation of correction vector directly from data and check bits as received.

Truong, T. K.↗

NASA NTRS1986

A VLSI pipeline design of a fast prime factor DFT on a finite field

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

Truong, T. K.↗

NASA NTRS1986

Single-Chip VLSI Reed-Solomon Encoder

Reed-Solomon (RS) encoder based on Berlekamp bit-serial multiplier algorithm. RS code standard, based on code words of 255 8-bit symbols, of which 223 symbols convey information and remaining 32 are check symbols. This code enables correction of up to 16 erroneous information symbols per word. Berlekamp algorithm based on code-generating polynomial with 32 roots that occur in reciprocal pairs. Choice of algorithm permits compact design.

Truong, T. K.↗

NASA NTRS1986

A single chip VLSI Reed-Solomon decoder

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 time domain algorithm. A new architecture that implements such an algorithm permits efficient pipeline processing with minimum circuitry. A systolic array is also developed to perform erasure corrections in the new design. A modified form of Euclid's algorithm is implemented by a new architecture that maintains the throughput rate with less circuitry. Such improvements result in both enhanced capability and a significant reduction in silicon area, therefore making it possible to build a pipeline (31,15)RS decoder on a single VLSI chip.

Shao, H. M.↗

NASA NTRS1985

A VLSI single chip (255,223) Reed-Solomon encoder

A description of a working single chip implementation of a Reed-Solomon encoder. The code used is the Consultative Committee on Space Data Systems (CCSDS) standard (255,223) code. The architecture that leads to this single very large scale integration chip design makes use of a bit-serial finite field multiplication algorithm of E. R. Berlekamp.

Deutsch, L. J.↗

NASA NTRS1985

The VLSI design of error-trellis syndrome decoding for convolutional codes

Reed, I. S.↗

NASA NTRS1985

Techniques for Computing the DFT Using the Residue Fermat Number Systems and VLSI

The integer complex multiplier and adder over the direct sum of two copies of a finite field is specialized to the direct sum of the rings of integers modulo Fermat numbers. 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 for the DFT can be reduced substantially over the previous approach. The architectural designs using this approach are regular, simple, expandable and, therefore, naturally suitable for VLSI implementation.

Truong, T. K.↗

NASA NTRS1985

A VLSI design of a pipeline Reed-Solomon decoder

A pipeline structure of a transform decoder similar to a systolic array was 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 decoder is regular and simple, and naturally suitable for VLSI implementation.

Shao, H. M.↗

NASA NTRS1985

Simplified Convolution Codes

Simple recursive algorithm efficiently calculates minimum-weight error vectors using Diophantine equations. Recursive algorithm uses general solution of polynomial linear Diophantine equation to determine minimum-weight error polynomial vector in equation in polynomial space.

Truong, T. K.↗

NASA NTRS1985

Error-trellis syndrome decoding techniques for convolutional codes

An error-trellis syndrome decoding technique for convolutional codes is developed. This algorithm is then applied to the entire class of systematic convolutional codes and to the high-rate, Wyner-Ash convolutional codes. A special example of the one-error-correcting Wyner-Ash code, a rate 3/4 code, is treated. The error-trellis syndrome decoding method applied to this example shows in detail how much more efficient syndrome decordig is than Viterbi decoding if applied to the same problem. For standard Viterbi decoding, 64 states are required, whereas in the example only 7 states are needed. Also, within the 7 states required for decoding, many fewer transitions are needed between the states.

Reed, I. S.↗

NASA NTRS1985

Reed-Solomon Encoder

Report presents mathematical principles of Berlekamp bit serial multiplier algorithm and its application to design of very-large-scale integrated (VLSI) encoders for Reed-Solomon error-correcting codes. Structure made readily on single chip of negatively doped channel metal oxide semiconductor.

Troung, T. K.↗

NASA NTRS1984

Sequential Syndrome Decoding of Convolutional Codes

The algebraic structure of convolutional codes are reviewed and sequential syndrome decoding is applied to those codes. These concepts are then used to realize by example actual sequential decoding, using the stack algorithm. The Fano metric for use in sequential decoding is modified so that it can be utilized to sequentially find the minimum weight error sequence.

Reed, I. S.↗