Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Erasure Codes”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 19 records
All sourcesNASA NTRSDOE OSTI
NASA NTRS2010

Optimal Codes for the Burst Erasure Channel

Deep space communications over noisy channels lead to certain packets that are not decodable. These packets leave gaps, or bursts of erasures, in the data stream. Burst erasure correcting codes overcome this problem. These are forward erasure correcting codes that allow one to recover the missing gaps of data. Much of the recent work on this topic concentrated on Low-Density Parity-Check (LDPC) codes. These are more complicated to encode and decode than Single Parity Check (SPC) codes or Reed-Solomon (RS) codes, and so far have not been able to achieve the theoretical limit for burst erasure protection. A block interleaved maximum distance separable (MDS) code (e.g., an SPC or RS code) offers near-optimal burst erasure protection, in the sense that no other scheme of equal total transmission length and code rate could improve the guaranteed correctible burst erasure length by more than one symbol. The optimality does not depend on the length of the code, i.e., a short MDS code block interleaved to a given length would perform as well as a longer MDS code interleaved to the same overall length. As a result, this approach offers lower decoding complexity with better burst erasure protection compared to other recent designs for the burst erasure channel (e.g., LDPC codes). A limitation of the design is its lack of robustness to channels that have impairments other than burst erasures (e.g., additive white Gaussian noise), making its application best suited for correcting data erasures in layers above the physical layer. The efficiency of a burst erasure code is the length of its burst erasure correction capability divided by the theoretical upper limit on this length. The inefficiency is one minus the efficiency. The illustration compares the inefficiency of interleaved RS codes to Quasi-Cyclic (QC) LDPC codes, Euclidean Geometry (EG) LDPC codes, extended Irregular Repeat Accumulate (eIRA) codes, array codes, and random LDPC codes previously proposed for burst erasure protection. As can be seen, the simple interleaved RS codes have substantially lower inefficiency over a wide range of transmission lengths.

Hamkins, Jon↗
NASA NTRS2006

Protograph LDPC Codes for the Erasure Channel

This viewgraph presentation reviews the use of protograph Low Density Parity Check (LDPC) codes for erasure channels. A protograph is a Tanner graph with a relatively small number of nodes. A "copy-and-permute" operation can be applied to the protograph to obtain larger derived graphs of various sizes. For very high code rates and short block sizes, a low asymptotic threshold criterion is not the best approach to designing LDPC codes. Simple protographs with much regularity and low maximum node degrees appear to be the best choices Quantized-rateless protograph LDPC codes can be built by careful design of the protograph such that multiple puncturing patterns will still permit message passing decoding to proceed

long erasure codes↗
NASA NTRS1972

Error-erasure decoding of product codes.

Two error-erasure decoding algorithms for product codes that correct all the error-erasure patterns guaranteed correctable by the minimum Hamming distance of the product code are given. The first algorithm works when at least one of the component codes is majority-logic decodable. The second algorithm works for any product code. Both algorithms use the decoders of the component codes.

Wainberg, S.↗
NASA NTRS2006

Protograph LDPC Codes Over Burst Erasure Channels

In this paper we design high rate protograph based LDPC codes suitable for binary erasure channels. To simplify the encoder and decoder implementation for high data rate transmission, the structure of codes are based on protographs and circulants. These LDPC codes can improve data link and network layer protocols in support of communication networks. Two classes of codes were designed. One class is designed for large block sizes with an iterative decoding threshold that approaches capacity of binary erasure channels. The other class is designed for short block sizes based on maximizing minimum stopping set size. For high code rates and short blocks the second class outperforms the first class.

protgraph based codes↗
NASA NTRS1997

Investigation of the Use of Erasures in a Concatenated Coding Scheme

A new method for declaring erasures in a concatenated coding scheme is investigated. This method is used with the rate 1/2 K = 7 convolutional code and the (255, 223) Reed Solomon code. Errors and erasures Reed Solomon decoding is used. The erasure method proposed uses a soft output Viterbi algorithm and information provided by decoded Reed Solomon codewords in a deinterleaving frame. The results show that a gain of 0.3 dB is possible using a minimum amount of decoding trials.

Kwatra, S. C.↗
NASA NTRS1985

Error and erasure probabilities for Galileo uplink code

The Galileo uplink Frame Erasure probability and Undetected Frame Error probability are derived. The performance meets desired specification under normal operations. The Galileo command system will work well even in an emergency condition, where the bit error rate into the command decoder is 1.00 X 0.001 (although Galileo's command threshold error rate is 1.00 X 0.00001).

Berner, J. B.↗
NASA NTRS1978

A simplified algorithm for correcting both errors and erasures of R-S codes

Using the finite field transform and continued fractions, a simplified algorithm for decoding Reed-Solomon (R-S) codes is developed to correct erasures caused by other codes as well as errors over the finite field GF (q(m), where q is a prime and m is an integer. Such an R-S decoder can be faster and simpler than a decoder that uses more conventional methods.

Reed, I. S.↗
NASA NTRS1979

Decoding of B.C.H. and R.S. codes with errors and erasures using continued fractions

Through the use of continuing fractions, a simplified algorithm for decoding B.C.H. and R.S. codes is developed that corrects both erasures and errors on a finite field GF(q to the m). It is noted that the decoding method is a modification of the Forney-Belekamp technique. Finally, it is believed that the present scheme is both simpler to understand and to implement than more conventional algorithms.

Reed, I. S.↗
NASA NTRS1979

Simplified algorithm for correcting both errors and erasures of Reed-Solomon codes

Using a finite-field transform, a simplified algorithm for decoding Reed-Solomon codes is developed to correct erasures as well as errors over the finite-field GF(q to the m power), where q is a prime and m is an integer. If the finite-field transform is a fast transform, this decoder can be faster and simpler than a decoder that uses more conventional methods.

Reed, I. S.↗
NASA NTRS1987

A simplified procedure for correcting both errors and erasures of a Reed-Solomon code using the Euclidean algorithm

It is well known that the Euclidean algorithm or its equivalent, continued fractions, can be used to find the error locator polynomial and the error evaluator polynomial in Berlekamp's key equation needed to decode a Reed-Solomon (RS) code. A simplified procedure is developed and proved to correct erasures as well as errors by replacing the initial condition of the Euclidean algorithm by the erasure locator polynomial and the Forney syndrome polynomial. By this means, the errata locator polynomial and the errata evaluator polynomial can be obtained, simultaneously and simply, by the Euclidean algorithm only. With this improved technique the complexity of time domain RS decoders for correcting both errors and erasures is reduced substantially from previous approaches. As a consequence, decoders for correcting both errors and erasures of RS codes can be made more modular, regular, simple, and naturally suitable for both VLSI and software implementation. An example illustrating this modified decoding procedure is given for a (15, 9) RS code.

Truong, T. K.↗
NASA NTRS1978

An upper bound for codes in a two-access binary erasure channel

A method for determining an upper bound for the size of a code for a two-access binary erasure channel is presented. For uniquely decodable codes, this bound gives a combinatorial proof of a result by Liao. Examples of the bound are given for codes with minimum distance 4.

Van Tilborg, H. C. A.↗
NASA NTRS1980

Efficient program for decoding the /255, 223/ Reed-Solomon code over GF/2 to the 8th/ with both errors and erasures, using transform decoding

The paper deals with a method developed for decoding a (255, 223) Reed-Solomon code over GF(2 to the 8th) with both errors and erasures. The matrix of decoding times for correcting errors and erasures of the code using a simplified decoder is presented. It is shown that the algorithm proposed is faster by a factor of from three to seven.

Miller, R. L.↗
NASA NTRS2008

Prioritized Luby Transform (LT) Codes

This viewgraph presentation describes a prioritized Luby Transform coding scheme that seeks to decode high priority data with high reliability, when decoders fail.

Luby Transform (LT) codes↗
NASA NTRS1988

The decoding of Reed-Solomon codes

Reed-Solomon (RS) codes form an important part of the high-rate downlink telemetry system for the Magellan mission, and the RS decoding function for this project will be done by DSN. Although the basic idea behind all Reed-Solomon decoding algorithms was developed by Berlekamp in 1968, there are dozens of variants of Berlekamp's algorithm in current use. An attempt to restore order is made by presenting a mathematical theory which explains the working of almost all known RS decoding algorithms. The key innovation that makes this possible is the unified approach to the solution of the key equation, which simultaneously describes the Berlekamp, Berlekamp-Massey, Euclid, and continued fractions approaches. Additionally, a detailed analysis is made of what can happen to a generic RS decoding algorithm when the number of errors and erasures exceeds the code's designed correction capability, and it is shown that while most published algorithms do not detect as many of these error-erasure patterns as possible, by making a small change in the algorithms, this problem can be overcome.

Mceliece, R. J.↗
NASA NTRS1987

The design plan of a VLSI single chip (255, 223) Reed-Solomon decoder

The very large-scale integration (VLSI) architecture of a single chip (255, 223) Reed-Solomon decoder for decoding both errors and erasures is described. A decoding failure detection capability is also included in this system so that the decoder will recognize a failure to decode instead of introducing additional errors. This could happen whenever the received word contains too many errors and erasures for the code to correct. The number of transistors needed to implement this decoder is estimated at about 75,000 if the delay for received message is not included. This is in contrast to the older transform decoding algorithm which needs about 100,000 transistors. However, the transform decoder is simpler in architecture than the time decoder. It is therefore possible to implement a single chip (255, 223) Reed-Solomon decoder with today's VLSI technology. An implementation strategy for the decoder system is presented. This represents the first step in a plan to take advantage of advanced coding techniques to realize a 2.0 dB coding gain for future space missions.

Hsu, I. S.↗
NASA NTRS1990

Pipeline Time- And Transform-Domain Reed-Solomon Decoders

Modification of decoding algorithms leads to simplified conceptual designs for time- and transform-domain Reed-Soloman (RS) decoders suitable for implementation as very-large-scale integrated (VLSI) circuits. New conceptual decoders determine simultaneously errata-locator and errata-evaluator polynomials as part of simplified scheme for corrections of errors and erasures in RS codes. Highly suitable for implementation in both VLSI circuitry and in software on general-purpose computer.

Hsu, In-Shek↗