Search NASA⌕ Search

Engineering topics

Lim, R. S.

Publications and source records attributed to Lim, R. S..

10 records
All sourcesNASA NTRSDOE OSTI
NASA NTRS1979

Concurrent error detecting codes for arithmetic processors

A method of concurrent error detection for arithmetic processors is described. Low-cost residue codes with check-length l and checkbase m = 2 to the l power - 1 are described for checking arithmetic operations of addition, subtraction, multiplication, division complement, shift, and rotate. Of the three number representations, the signed-magnitude representation is preferred for residue checking. Two methods of residue generation are described: the standard method of using modulo m adders and the method of using a self-testing residue tree. A simple single-bit parity-check code is described for checking the logical operations of XOR, OR, and AND, and also the arithmetic operations of complement, shift, and rotate. For checking complement, shift, and rotate, the single-bit parity-check code is simpler to implement than the residue codes.

Lim, R. S.↗
NASA NTRS1979

NASF transposition network: A computing network for unscrambling p-ordered vectors

The viewpoints of design, programming, and application of the transportation network (TN) is presented. The TN is a programmable combinational logic network that connects 521 memory modules to 512 processors. The unscrambling of p-ordered vectors to 1-ordered vectors in one cycle is described. The TN design is based upon the concept of cyclic groups from abstract algebra and primitive roots and indices from number theory. The programming of the TN is very simple, requiring only 20 bits: 10 bits for offset control and 10 bits for barrel switch shift control. This simple control is executed by the control unit (CU), not the processors. Any memory access by a processor must be coordinated with the CU and wait for all other processors to come to a synchronization point. These wait and synchronization events can be a degradation in performance to a computation. The TN application is for multidimensional data manipulation, matrix processing, and data sorting, and can also perform a perfect shuffle. Unlike other more complicated and powerful permutation networks, the TN cannot, if possible at all, unscramble non-p-ordered vectors in one cycle.

Lim, R. S.↗
NASA NTRS1979

A /31,15/ Reed-Solomon Code for large memory systems

This paper describes the encoding and the decoding of a (31,15) Reed-Solomon Code for multiple-burst error correction for large memory systems. The decoding procedure consists of four steps: (1) syndrome calculation, (2) error-location polynomial calculation, (3) error-location numbers calculation, and (4) error values calculation. The principal features of the design are the use of a hardware shift register for both high-speed encoding and syndrome calculation, and the use of a commercially available (31,15) decoder for decoding Steps 2, 3 and 4.

Lim, R. S.↗
NASA NTRS1978

A decoding procedure for the Reed-Solomon codes

A decoding procedure is described for the (n,k) t-error-correcting Reed-Solomon (RS) code, and an implementation of the (31,15) RS code for the I4-TENEX central system. This code can be used for error correction in large archival memory systems. The principal features of the decoder are a Galois field arithmetic unit implemented by microprogramming a microprocessor, and syndrome calculation by using the g(x) encoding shift register. Complete decoding of the (31,15) code is expected to take less than 500 microsecs. The syndrome calculation is performed by hardware using the encoding shift register and a modified Chien search. The error location polynomial is computed by using Lin's table, which is an interpretation of Berlekamp's iterative algorithm. The error location numbers are calculated by using the Chien search. Finally, the error values are computed by using Forney's method.

Lim, R. S.↗
NASA NTRS1977

Fault tolerant computing: A preamble for assuring viability of large computer systems

The need for fault-tolerant computing is addressed from the viewpoints of (1) why it is needed, (2) how to apply it in the current state of technology, and (3) what it means in the context of the Phoenix computer system and other related systems. To this end, the value of concurrent error detection and correction is described. User protection, program retry, and repair are among the factors considered. The technology of algebraic codes to protect memory systems and arithmetic codes to protect memory systems and arithmetic codes to protect arithmetic operations is discussed.

Lim, R. S.↗
NASA NTRS1977

UNICON Laser Memory: Interlaced Codes for Multi-burst-Error Correction

Interlaced binary BCH codes are described for multiple-burst-error correction for the UNICON 690 laser memory. Other multiple-burst-error-correcting codes, such as Reed-Solomon codes and Product codes, are also briefly mentioned. In particular, an interlaced (31, 21) t = 2 BCH code is selected as an outer code for UNICON double-burst-error correction. This code is shortened to (26,16) and interlaced to degree X = 16. Decoding is implemented by table lookup. This method not only avoids all computations in GF(2(exp 5)), it also offers a decoding time of less than 1 ps. The inner code is an existing (80,64) Fire code capable of correcting a single-burst error of length b less than or equal to 6.

Lim, R. S.↗
NASA NTRS1974

Augmented burst-error correction for UNICON laser memory

A single-burst-error correction system is described for data stored in the UNICON laser memory. In the proposed system, a long fire code with code length n greater than 16,768 bits was used as an outer code to augment an existing inner shorter fire code for burst error corrections. The inner fire code is a (80,64) code shortened from the (630,614) code, and it is used to correct a single-burst-error on a per-word basis with burst length b less than or equal to 6. The outer code, with b less than or equal to 12, would be used to correct a single-burst-error on a per-page basis, where a page consists of 512 32-bit words. In the proposed system, the encoding and error detection processes are implemented by hardware. A minicomputer, currently used as a UNICON memory management processor, is used on a time-demanding basis for error correction. Based upon existing error statistics, this combination of an inner code and an outer code would enable the UNICON system to obtain a very low error rate in spite of flaws affecting the recorded data.

Lim, R. S.↗
NASA NTRS1974

Quasi-perfect FIFO: Synchronous or asynchronous with application in controller design for the UNICON laser memory

The first-in-first-out memory buffer (FIFO), is an elastic digital memory whose main application is in data buffering between devices operating at different rates. Data written into the top is moved autonomously down toward the bottom of the FIFO to the lowest unoccupied location, and data read from the bottom of the FIFO will cause data from the top to move autonomously down toward the bottom. The FIFO is available in MOS LSI asynchronous form with data rate in the 1 MHz region. The FIFO described yields a simple high-speed iterative implementation, either synchronous of asynchronous. Because of this simple iterative structure, the FIFO is expandable in both number of words and bits per word, and it is attractive from the viewpoint of integrated-circuit production. For the synchronous FIFO, a model was built and successfully used in the controller for the UNICON laser memory. For the asynchronous FIFO, a model was built and also successfully used in a high-performance magnetic tape controller.

Lim, R. S.↗
NASA NTRS1970

Rapid method for interconversion of binary and decimal numbers

Decoding tree consisting of 40-bit semiconductor read-only memories interconverts binary and decimal numbers 50 to 100 times faster than current methods. Decimal-to-binary conversion algorithm is based on a divided-by-2 iterative equation, binary-to-decimal conversion algorithm utilizes multiplied-by-2 iterative equation.

Lim, R. S.↗