2010

Optimal Codes for the Burst Erasure Channel

This approach offers lower decoding complexity with better burst erasure protection.

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.

Inefficiency of Interleaved RS Codes is compared with other listed codes." class="caption" align="left">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.

This work was done by Jon Hamkins of Caltech for NASA’s Jet Propulsion Laboratory. For more information, contact iaofflce@jpl. nasa.gov.

The software used in this innovation is available for commercial licensing. Please contact Daniel Broderick of the California Institute of Technology at This email address is being protected from spambots. You need JavaScript enabled to view it. . Refer to NPO-46903.

White Papers

Electrical and Mechanical Integration in Aerospace Design
Sponsored by Mentor Graphics
Broadening the Scope of User Requirements When Selecting Valves for Medical Devices
Sponsored by B Braun
Changing Face of Robotics
Sponsored by Maplesoft
Connectors Outperform Fardwiring for Manufacturers and Their Customers
Sponsored by Harting
PICO xMOD Data Sheet
Sponsored by Nordson EFD
Oscilloscope Fundamentals Primer
Sponsored by Rohde and Schwarz

White Papers Sponsored By: