An efficient pcm error correction and synchronization code
Frame synchronization and error correction by pulse-code modulated systems
SYNCHRONIZATION↗
SEARCH · Search NASA
Results for “error correcting 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.
Asymmetric Memory Circuit Would Resist Soft Errors
Some nonlinear error-correcting codes more efficient in presence of asymmetry. Combination of circuit-design and coding concepts expected to make integrated-circuit random-access memories more resistant to "soft" errors (temporary bit errors, also called "single-event upsets" due to ionizing radiation). Integrated circuit of new type made deliberately more susceptible to one kind of bit error than to other, and associated error-correcting code adapted to exploit this asymmetry in error probabilities.
Buehler, Martin G.↗
The Utilization Profiles of the CCSDS Unified Space Link Protocol (USLP)
The purpose of this paper is to identify the utilization profiles for interfacing the Data Protocol Sublayer using the Unified Space Link Protocols (USLP) (reference 1) with the space link coding procedures as specified in the CCSDS Coding & Synchronization Blue Books (references 2 through 5), used in both telecommand and telemetry applications. This paper describes how the USLP Protocol utilizes the coding and synchronization sublayer to support: a. Direct to Earth (DTE) telemetry links for engineering and science data b. Direct to Earth (DTE) telemetry links for very high rate science data c. Direct from Earth (DFE) command, sequencing and flight software loads d. Space to Space Links (Proximity) utilized by orbiters for data exchange to/from surface bound assets. The CCSDS has divided the functions of the Data Link Layer into two sublayers: the Data Link Protocol Sublayer (DLP-SL) and the Coding and Synchronization Sublayer (CS-SL). The Data Link Protocol Sublayer (DLP-SL) interfaces to the users, accepting the data that is to be transported, on the sending side of the link, and delivering that data on the receiving end. The Transfer Frame is the data unit that is transferred across the Data Link Protocol Sublayer and the Coding and Synchronization Sublayer boundary. The Coding and Synchronization Sublayer (CS-SL) provides the encoding, randomization, and frame synchronization functions that prepares the USLP Transfer Frame for transport across the space link. The CS-SL is divided into 2 processes: 1) The Frame Interface Processes (FIP) performs the interface functions required to prepare the data for delivery to the Coding/Decoding Process (CDP). This process includes prepending a Frame Start Marker to the provided frame, when management has designated that the frame is not to be aligned to the codeblock or when there is no block code used. 2) The Coding/Decoding Process (CDP) performs the forward error correction processes that are used to optimize the performance of the link and minimize the error rate. The CDP creates the symbol stream that is delivered to the Physical Layer. The transfer of the USLP transfer frames across different types of space links is the focus of this paper. The Protocol Data Unit (PDU) that is passed in both directions between the Data Link Protocol Sublayer (DLP-SL) and Coding and Synchronization Sublayer (CS-SL) is the transfer frame. The USLP frame structure provides flexibility that can be constrained by the functions utilized within the CS-SL that prepare the transfer frame for transit. For example, the USLP transfer frame contains a length field that enables the frame to be of variable length but CS-SL under certain conditions may constrain the frame to be fixed in length. This paper describes 5 operational modes available for use by the Data Link Layer to provide data exchange across the USLP space link. These modes are different because different operational requirements apply to vastly different types of space links and thus the communications implementation requirements differ. The environmental issues include the power or energy available, the distance between the end points of the link, the complexity of the equipment available at those end points, the atmospheric conditions and radiometric frequency selection. The CS-SL utilizes different forward error correcting codes supported by specific operational modes to configure the data for transit. This paper describes all of the operational modes in a series of data models which decompose the functionality between the Data Link Protocol Sublayer and the Coding and Synchronization sublayer. The operational modes described are: 1. Uncoded Mode: has been used for short links that contain significant available power to provide an acceptable frame error rate. The frames in this mode can be variable in length and typically use an error detection algorithm (i.e., CRC) to determine if there are errors in the received frame. 2. Convolutional Only Mode: is currently the prime forward error correction coding used for the proximity links. The frames in this mode can be variable in length and typically use an error detection algorithm (i.e., CRC) to determine if there are errors in the received frame. 3. Variable Length Frame Aligned to Variable Length Codeblock (TC): is used for Direct from Earth links were power levels are high and the simple, least complex code i.e., the BCH code is used. This mode has been in use since the early 1970s. The BCH code is a short code and the decoder is easy to implement. 4. Fixed Length Frame Aligned to Fixed Length Codeblock (AOS/TM): was introduced when the concatenated Convolutional and Reed-Solomon Code was formulated to provide significant reduction in link data error rate and the ability to determine if there was an error in the decoded codeblock. The frame is aligned to the codeblock so that there is a one to one relationship of frame errors to codeblock errors without additional error detection coding being added. This mode requires the protocol frames to be the exact size of the message portion of the codeblock. 5. Frames Unaligned to Fixed Length Codeblocks (Currently used for very high rates and space to space links): This mode is currently used for missions that have a very high data rate that can be controlled adaptively as the environment changes and as the next generation operating mode for the proximity link. This mode from a coded data stream point of view is exactly like that described in 4. above, except that the frame need not be aligned to the codeblock. There is no requirement on frame length when using this mode. Thus when using USLP it can be used to support links that require short or long frames. There is also no mandatory requirement that frames cannot be separated by idle data reducing the tight data rate connection requirements between the data link protocol sublayer and the coding & synchronization sublayer. In conclusion, how these operational modes can be put to use in mission operational scenarios is described for Direct from Earth links (DFE), Direct to Earth links (DTE), and Proximity links.
Greenberg, E.↗
Coded Modulation in C and MATLAB
This software, written separately in C and MATLAB as stand-alone packages with equivalent functionality, implements encoders and decoders for a set of nine error-correcting codes and modulators and demodulators for five modulation types. The software can be used as a single program to simulate the performance of such coded modulation. The error-correcting codes implemented are the nine accumulate repeat-4 jagged accumulate (AR4JA) low-density parity-check (LDPC) codes, which have been approved for international standardization by the Consultative Committee for Space Data Systems, and which are scheduled to fly on a series of NASA missions in the Constellation Program. The software implements the encoder and decoder functions, and contains compressed versions of generator and parity-check matrices used in these operations.
Hamkins, Jon↗
LDPC Codes with Minimum Distance Proportional to Block Size
Low-density parity-check (LDPC) codes characterized by minimum Hamming distances proportional to block sizes have been demonstrated. Like the codes mentioned in the immediately preceding article, the present codes are error-correcting codes suitable for use in a variety of wireless data-communication systems that include noisy channels. The previously mentioned codes have low decoding thresholds and reasonably low error floors. However, the minimum Hamming distances of those codes do not grow linearly with code-block sizes. Codes that have this minimum-distance property exhibit very low error floors. Examples of such codes include regular LDPC codes with variable degrees of at least 3. Unfortunately, the decoding thresholds of regular LDPC codes are high. Hence, there is a need for LDPC codes characterized by both low decoding thresholds and, in order to obtain acceptably low error floors, minimum Hamming distances that are proportional to code-block sizes. The present codes were developed to satisfy this need. The minimum Hamming distances of the present codes have been shown, through consideration of ensemble-average weight enumerators, to be proportional to code block sizes. As in the cases of irregular ensembles, the properties of these codes are sensitive to the proportion of degree-2 variable nodes. A code having too few such nodes tends to have an iterative decoding threshold that is far from the capacity threshold. A code having too many such nodes tends not to exhibit a minimum distance that is proportional to block size. Results of computational simulations have shown that the decoding thresholds of codes of the present type are lower than those of regular LDPC codes. Included in the simulations were a few examples from a family of codes characterized by rates ranging from low to high and by thresholds that adhere closely to their respective channel capacity thresholds; the simulation results from these examples showed that the codes in question have low error floors as well as low decoding thresholds. As an example, the illustration shows the protograph (which represents the blueprint for overall construction) of one proposed code family for code rates greater than or equal to 1.2. Any size LDPC code can be obtained by copying the protograph structure N times, then permuting the edges. The illustration also provides Field Programmable Gate Array (FPGA) hardware performance simulations for this code family. In addition, the illustration provides minimum signal-to-noise ratios (Eb/No) in decibels (decoding thresholds) to achieve zero error rates as the code block size goes to infinity for various code rates. In comparison with the codes mentioned in the preceding article, these codes have slightly higher decoding thresholds.
Divsalar, Dariush↗
Asymmetric soft-error resistant memory
A memory system is provided, of the type that includes an error-correcting circuit that detects and corrects, that more efficiently utilizes the capacity of a memory formed of groups of binary cells whose states can be inadvertently switched by ionizing radiation. Each memory cell has an asymmetric geometry, so that ionizing radiation causes a significantly greater probability of errors in one state than in the opposite state (e.g., an erroneous switch from '1' to '0' is far more likely than a switch from '0' to'1'. An asymmetric error correcting coding circuit can be used with the asymmetric memory cells, which requires fewer bits than an efficient symmetric error correcting code.
Buehler, Martin G.↗
LDPC-PPM Coding Scheme for Optical Communication
In a proposed coding-and-modulation/demodulation-and-decoding scheme for a free-space optical communication system, an error-correcting code of the low-density parity-check (LDPC) type would be concatenated with a modulation code that consists of a mapping of bits to pulse-position-modulation (PPM) symbols. Hence, the scheme is denoted LDPC-PPM. This scheme could be considered a competitor of a related prior scheme in which an outer convolutional error-correcting code is concatenated with an interleaving operation, a bit-accumulation operation, and a PPM inner code. Both the prior and present schemes can be characterized as serially concatenated pulse-position modulation (SCPPM) coding schemes. Figure 1 represents a free-space optical communication system based on either the present LDPC-PPM scheme or the prior SCPPM scheme. At the transmitting terminal, the original data (u) are processed by an encoder into blocks of bits (a), and the encoded data are mapped to PPM of an optical signal (c). For the purpose of design and analysis, the optical channel in which the PPM signal propagates is modeled as a Poisson point process. At the receiving terminal, the arriving optical signal (y) is demodulated to obtain an estimate (a^) of the coded data, which is then processed by a decoder to obtain an estimate (u^) of the original data.
Barsoum, Maged↗
On codes with multi-level error-correction capabilities
In conventional coding for error control, all the information symbols of a message are regarded equally significant, and hence codes are devised to provide equal protection for each information symbol against channel errors. However, in some occasions, some information symbols in a message are more significant than the other symbols. As a result, it is desired to devise codes with multilevel error-correcting capabilities. Another situation where codes with multi-level error-correcting capabilities are desired is in broadcast communication systems. An m-user broadcast channel has one input and m outputs. The single input and each output form a component channel. The component channels may have different noise levels, and hence the messages transmitted over the component channels require different levels of protection against errors. Block codes with multi-level error-correcting capabilities are also known as unequal error protection (UEP) codes. Structural properties of these codes are derived. Based on these structural properties, two classes of UEP codes are constructed.
Lin, Shu↗
Optimizing Parameters for Deep-Space Optical Communication
A paper discusses the optimization of the parameters of a high-rate, deep-space optical communication link that utilizes pulse-position modulation (PPM) and an error-correcting code (ECC). The parameters in question include the PPM order (number of pulse time slots in one symbol period), the ECC rate, and the uncoded symbol error rate. In simple terms, the optimization problem is to choose the combination of these parameters that maximizes the throughput data rate at a given bit-error-rate (BER), subject to several constraints, including limits on the average and peak power and possibly a limit on the uncoded symbol error rate. This is a complex, multidimensional optimization problem, the solution of which involves computation of channel capacities for various combinations of the parameters. The paper presents extensive theoretical analyses and numerical predictions that elucidate the many facets of the optimization problem. It shows how a nearly optimum solution can be obtained by choosing the optimum PPM order for the desired number of bits per slot and concatenating the PPM mapping with an error-correction code so that the decoded bits satisfy some BER threshold.
Moison, Bruce↗
Polar Coding for Forward Error Correction in Space Communications
Presentation for Polar Coding for Forward Error Correction in Space Communications paper for IAC
Safavi, Haleh↗
The CCSDS Next Generation Space Data Link Protocol (NGSLP)
The CCSDS space link protocols i.e., Telemetry (TM), Telecommand (TC), Advanced Orbiting Systems (AOS) were developed in the early growth period of the space program. They were designed to meet the needs of the early missions, be compatible with the available technology and focused on the specific link environments. Digital technology was in its infancy and spacecraft power and mass issues enforced severe constraints on flight implementations. Therefore the Telecommand protocol was designed around a simple Bose, Hocquenghem, Chaudhuri (BCH) code that provided little coding gain and limited error detection but was relatively simple to decode on board. The infusion of the concatenated Convolutional and Reed-Solomon codes5 for telemetry was a major milestone and transformed telemetry applications by providing them the ability to more efficiently utilize the telemetry link and its ability to deliver user data. The ability to significantly lower the error rates on the telemetry links enabled the use of packet telemetry and data compression. The infusion of the high performance codes for telemetry was enabled by the advent of digital processing, but it was limited to earth based systems supporting telemetry. The latest CCSDS space link protocol, Proximity-1 was developed in early 2000 to meet the needs of short-range, bi-directional, fixed or mobile radio links characterized by short time delays, moderate but not weak signals, and short independent sessions. Proximity-1 has been successfully deployed on both NASA and ESA missions at Mars and is planned to be utilized by all Mars missions in development. A new age has arisen, one that now provides the means to perform advanced digital processing in spacecraft systems enabling the use of improved transponders, digital correlators, and high performance forward error correcting codes for all communications links. Flight transponders utilizing digital technology have emerged and can efficiently provide the means to make the next leap in performance for space link communications. Field Programmable Gate Arrays (FPGAs) provide the capability to incorporate high performance forward error correcting codes implemented within software transponders providing improved performance in data transfer, ranging, link security, and time correlation. Given these synergistic technological breakthroughs, the time has come to take advantage of them in applying them to both on going (e.g., command, telemetry) and emerging (e.g., space link security, optical communication) space link applications. However one of the constraining factors within the Data Link Layer in realizing these performance gains is the lack of a generic transfer frame format and common supporting services amongst the existing CCSDS link layer protocols. Currently each of the four CCSDS link layer protocols (TM, TC, AOS, and Proximity-1) have unique formats and services which prohibits their reuse across the totality of all space link applications of CCSDS member space agencies. For example, Mars missions. These missions implement their proximity data link layer using the Proximity-1 frame format and the services it supports but is still required to support the direct from Earth (TC) protocols and the Direct To Earth (AOS/TM) protocols. The prime purpose of this paper, is to describe a new general purpose CCSDS Data Link layer protocol, the NGSLP that will provide the required services along with a common transfer frame format for all the CCSDS space links (ground to/from space and space to space links) targeted for emerging missions after a CCSDS agency-wide coordinated date. This paper will also describe related options that can be included for the Coding and Synchronization sub-layer of the Data Link layer to extend the capacities of the link and additionally provide an independence of the transfer frame sub-layer from the coding sublayer. This feature will provide missions the option of running either the currently performed synchronous coding and transfer frame data link or an asynchronous coding/frame data link, in which the transfer frame length is independent of the block size of the code. The benefits from the elimination of this constraint (frame synchronized to the code block) will simplify the interface between the transponder and the data handling equipment and reduce implementation costs and complexities. The benefits include: inclusion of encoders/decoders into transmitters and receivers without regard to data link protocols, providing the ability to insert latency sensitive messages into the link to support launch, landing/docking, telerobotics. and Variable Coded Modulation (VCM). In addition the ability to transfer different sized frames can provide a backup for delivering stored anomaly engineering data simultaneously with real time data, or relaying of frames from various sources onto a trunk line for delivery to Earth.
Kazz, Greg J.↗
Coding for Communication Channels with Dead-Time Constraints
Coding schemes have been designed and investigated specifically for optical and electronic data-communication channels in which information is conveyed via pulse-position modulation (PPM) subject to dead-time constraints. These schemes involve the use of error-correcting codes concatenated with codes denoted constrained codes. These codes are decoded using an interactive method. In pulse-position modulation, time is partitioned into frames of Mslots of equal duration. Each frame contains one pulsed slot (all others are non-pulsed). For a given channel, the dead-time constraints are defined as a maximum and a minimum on the allowable time between pulses. For example, if a Q-switched laser is used to transmit the pulses, then the minimum allowable dead time is the time needed to recharge the laser for the next pulse. In the case of bits recorded on a magnetic medium, the minimum allowable time between pulses depends on the recording/playback speed and the minimum distance between pulses needed to prevent interference between adjacent bits during readout. The maximum allowable dead time for a given channel is the maximum time for which it is possible to satisfy the requirement to synchronize slots. In mathematical shorthand, the dead-time constraints for a given channel are represented by the pair of integers (d,k), where d is the minimum allowable number of zeroes between ones and k is the maximum allowable number of zeroes between ones. A system of the type to which the present schemes apply is represented by a binary- input, real-valued-output channel model illustrated in the figure. At the transmitting end, information bits are first encoded by use of an error-correcting code, then further encoded by use of a constrained code. Several constrained codes for channels subject to constraints of (d,infinity) have been investigated theoretically and computationally. The baseline codes chosen for purposes of comparison were simple PPM codes characterized by M-slot PPM frames separated by d-slot dead times.
Moision, Bruce↗
Link Analysis for Space Communication Links Using ARQ Protocol
In space communications, standard link analysis assumes that messages are sent once. For a communication link that uses an error-correction coding scheme, bit-error-rate (BER) or frame-error-rate (FER), and link margins are common metrics that characterize the quality of a link, and they are used to determine the supportable data rate. With the advent of Automatic Repeat-reQuest (ARQ) protocols, when messages are corrupted during transmission, they can be resent multiple times automatically until they are correctly received and acknowledged. The concept of BER, FER, and link margin cannot be directly applied, and the link analysis approach for ARQ links needs to be re-examined.
Cheung, Kar-Ming↗
Accumulate-Repeat-Accumulate-Accumulate Codes
Accumulate-repeat-accumulate-accumulate (ARAA) codes have been proposed, inspired by the recently proposed accumulate-repeat-accumulate (ARA) codes. These are error-correcting codes suitable for use in a variety of wireless data-communication systems that include noisy channels. ARAA codes can be regarded as serial turbolike codes or as a subclass of low-density parity-check (LDPC) codes, and, like ARA codes they have projected graph or protograph representations; these characteristics make it possible to design high-speed iterative decoders that utilize belief-propagation algorithms. The objective in proposing ARAA codes as a subclass of ARA codes was to enhance the error-floor performance of ARA codes while maintaining simple encoding structures and low maximum variable node degree.
Divsalar, Dariush↗
Sub-baud coding
In a spread-spectrum communication system, a data sequence of +1's and -1's is expanded into a sequence of +x's (bottom bar) and -x's (bottom bar) where x (bottom bar) is a length n sequence of +1's and -1's. A sub-baud code is the assignment of a different such baud sequence to each of M users with the objective of reducing interference between users. It is shown that this interference can be described in terms of the even and odd correlation functions between pairs of sequences. A technique for deriving sub-baud codes from cyclic error-correcting codes is given, and a theorem proved which bounds the quality of the resultant code. A specific such cyclic code construction procedure is given which, for any M, yields a sub-baud code for which the mutual interference can be made arbitrarily small by choosing n sufficiently large.
Massey, J. L.↗
Constructing LDPC Codes from Loop-Free Encoding Modules
A method of constructing certain low-density parity-check (LDPC) codes by use of relatively simple loop-free coding modules has been developed. The subclasses of LDPC codes to which the method applies includes accumulate-repeat-accumulate (ARA) codes, accumulate-repeat-check-accumulate codes, and the codes described in Accumulate-Repeat-Accumulate-Accumulate Codes (NPO-41305), NASA Tech Briefs, Vol. 31, No. 9 (September 2007), page 90. All of the affected codes can be characterized as serial/parallel (hybrid) concatenations of such relatively simple modules as accumulators, repetition codes, differentiators, and punctured single-parity check codes. These are error-correcting codes suitable for use in a variety of wireless data-communication systems that include noisy channels. These codes can also be characterized as hybrid turbolike codes that have projected graph or protograph representations (for example see figure); these characteristics make it possible to design high-speed iterative decoders that utilize belief-propagation algorithms. The present method comprises two related submethods for constructing LDPC codes from simple loop-free modules with circulant permutations. The first submethod is an iterative encoding method based on the erasure-decoding algorithm. The computations required by this method are well organized because they involve a parity-check matrix having a block-circulant structure. The second submethod involves the use of block-circulant generator matrices. The encoders of this method are very similar to those of recursive convolutional codes. Some encoders according to this second submethod have been implemented in a small field-programmable gate array that operates at a speed of 100 megasymbols per second. By use of density evolution (a computational- simulation technique for analyzing performances of LDPC codes), it has been shown through some examples that as the block size goes to infinity, low iterative decoding thresholds close to channel capacity limits can be achieved for the codes of the type in question having low maximum variable node degrees. The decoding thresholds in these examples are lower than those of the best-known unstructured irregular LDPC codes constrained to have the same maximum node degrees. Furthermore, the present method enables the construction of codes of any desired rate with thresholds that stay uniformly close to their respective channel capacity thresholds.
Divsalar, Dariush↗
The statistical significance of error probability as determined from decoding simulations for long codes
The very low error probability obtained with long error-correcting codes results in a very small number of observed errors in simulation studies of practical size and renders the usual confidence interval techniques inapplicable to the observed error probability. A natural extension of the notion of a 'confidence interval' is made and applied to such determinations of error probability by simulation. An example is included to show the surprisingly great significance of as few as two decoding errors in a very large number of decoding trials.
Massey, J. L.↗