Engineering Papers⌕ Search

SEARCH · Engineering Papers

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.

At least 325 records · Page 18

Soft Syndrome Decoding of Quantum LDPC Codes for Joint Correction of Data and Syndrome Errors

Quantum errors are primarily detected and corrected using the measurement of syndrome information which itself is an unreliable step in practical error correction implementations. Typically, such faulty or noisy syndrome measurements are modeled as a binary measurement outcome flipped with some probability. However, the measured syndrome is in fact a discretized value of the continuous voltage or current values obtained in the physical implementation of the syndrome extraction. In this paper, we use this "soft" or analog information without the conventional discretization step to benefit the iterative decoders for decoding quantum low-density parity-check (QLDPC) codes. Syndrome-based iterative belief propagation (BP) decoders are modified to utilize the syndrome-soft information to successfully correct both data and syndrome errors simultaneously, without repeated measurements. We demonstrate the advantages of extracting the soft information from the syndrome in our improved decoders, not only in terms of comparison of thresholds and logical error rates for quasi-cyclic lifted-product QLDPC code families, but also for faster convergence of iterative decoders. In particular, the new BP decoder with noisy syndrome performs as good as the standard BP decoder under ideal syndrome.

97 MATHEMATICS AND COMPUTING↗

Synchronization of Reed-Solomon codes

The synchronization capabilities of Reed-Solomon codes when an appropriate coset of the code is used instead of the code itself are examined. In this case an E-error correcting Reed-Solomon code is transformed into a code capable of determining that there are m symbols out of sync, if e symbol errors occurred, whenever m + e E. In the event that m = 0, i.e., the word is in sync, then decoder will correct any pattern of E - 1 on fewer symbol errors.

Miller, R. L.↗

Error coding simulations in C

When data is transmitted through a noisy channel, errors are produced within the data rendering it indecipherable. Through the use of error control coding techniques, the bit error rate can be reduced to any desired level without sacrificing the transmission data rate. The Astrionics Laboratory at Marshall Space Flight Center has decided to use a modular, end-to-end telemetry data simulator to simulate the transmission of data from flight to ground and various methods of error control. The simulator includes modules for random data generation, data compression, Consultative Committee for Space Data Systems (CCSDS) transfer frame formation, error correction/detection, error generation and error statistics. The simulator utilizes a concatenated coding scheme which includes CCSDS standard (255,223) Reed-Solomon (RS) code over GF(2(exp 8)) with interleave depth of 5 as the outermost code, (7, 1/2) convolutional code as an inner code and CCSDS recommended (n, n-16) cyclic redundancy check (CRC) code as the innermost code, where n is the number of information bits plus 16 parity bits. The received signal-to-noise for a desired bit error rate is greatly reduced through the use of forward error correction techniques. Even greater coding gain is provided through the use of a concatenated coding scheme. Interleaving/deinterleaving is necessary to randomize burst errors which may appear at the input of the RS decoder. The burst correction capability length is increased in proportion to the interleave depth. The modular nature of the simulator allows for inclusion or exclusion of modules as needed. This paper describes the development and operation of the simulator, the verification of a C-language Reed-Solomon code, and the possibility of using Comdisco SPW(tm) as a tool for determining optimal error control schemes.

Noble, Viveca K.↗

Bandwidth efficient CCSDS coding standard proposals

The basic concatenated coding system for the space telemetry channel consists of a Reed-Solomon (RS) outer code, a symbol interleaver/deinterleaver, and a bandwidth efficient trellis inner code. A block diagram of this configuration is shown. The system may operate with or without the outer code and interleaver. In this recommendation, the outer code remains the (255,223) RS code over GF(2 exp 8) with an error correcting capability of t = 16 eight bit symbols. This code's excellent performance and the existence of fast, cost effective, decoders justify its continued use. The purpose of the interleaver/deinterleaver is to distribute burst errors out of the inner decoder over multiple codewords of the outer code. This utilizes the error correcting capability of the outer code more efficiently and reduces the probability of an RS decoder failure. Since the space telemetry channel is not considered bursty, the required interleaving depth is primarily a function of the inner decoding method. A diagram of an interleaver with depth 4 that is compatible with the (255,223) RS code is shown. Specific interleaver requirements are discussed after the inner code recommendations.

Costello, Daniel J., Jr.↗

Shift register generators and applications to coding

The most important properties of shift register generated sequences are exposed. The application of shift registers as multiplication and division circuits leads to the generation of some error correcting and detecting codes.

Morakis, J. C.↗

Turbo codes for deep-space communications

Turbo codes were recently proposed by Berrou, Glavieux, and Thitimajshima, and it has been claimed these codes achieve near-Shannon-limit error correction performance with relatively simple component codes and large interleavers. A required E(b)/N(o) of 0.7 dB was reported for a bit error rate of 10(exp -5), using a rate 1/2 turbo code. However, some important details that are necessary to reproduce these results were omitted. This article confirms the accuracy of these claims, and presents a complete description of an encoder/decoder pair that could be suitable for deep-space applications, where lower rate codes can be used. We describe a new simple method for trellis termination, analyze the effect of interleaver choice on the weight distribution of the code, and introduce the use of unequal rate component codes, which yield better performance.

Divsalar, D.↗

Extensions and improvements on XTRAN3S

Improvements to the XTRAN3S computer program are summarized. Work on this code, for steady and unsteady aerodynamic and aeroelastic analysis in the transonic flow regime has concentrated on the following areas: (1) Maintenance of the XTRAN3S code, including correction of errors, enhancement of operational capability, and installation on the Cray X-MP system; (2) Extension of the vectorization concepts in XTRAN3S to include additional areas of the code for improved execution speed; (3) Modification of the XTRAN3S algorithm for improved numerical stability for swept, tapered wing cases and improved computational efficiency; and (4) Extension of the wing-only version of XTRAN3S to include pylon and nacelle or external store capability.

Borland, C. J.↗

Reliability and throughput analysis of a concatenated coding scheme

The performance of a concatenated coding scheme for error control in ARQ systems is analyzed for both random-noise and burst-noise channels. In particular, the probability of undetected error and the system throughput are calculated. In this scheme, the inner code is used for both error correction and error detection, and the outer code is used for error detection only. Interleaving/deinterleaving is assumed within the outer code. A retransmission is requested if either the inner code or the outer code detects the presence of errors. Various coding examples are considered. The results show that concatenated coding can provide extremely high system reliability (i.e., low probability of undetected error) and high system throughput.

Deng, Robert H.↗

The black hole interior from non-isometric codes and complexity

Quantum error correction has given us a natural language for the emergence of spacetime, but the black hole interior poses a challenge for this framework: at late times the apparent number of interior degrees of freedom in effective field theory can vastly exceed the true number of fundamental degrees of freedom, so there can be no isometric (i.e. inner-product preserving) encoding of the former into the latter. In this paper we explain how quantum error correction nonetheless can be used to explain the emergence of the black hole interior, via the idea of “non-isometric codes protected by computational complexity”. We show that many previous ideas, such as the existence of a large number of “null states”, a breakdown of effective field theory for operations of exponential complexity, the quantum extremal surface calculation of the Page curve, post-selection, “state-dependent/state-specific” operator reconstruction, and the “simple entropy” approach to complexity coarse-graining, all fit naturally into this framework, and we illustrate all of these phenomena simultaneously in a soluble model.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗

Bayesian homodyne and heterodyne tomography

Continuous-variable (CV) photonic states are of increasing interest in quantum information science, bolstered by features such as deterministic resource state generation and error correction via bosonic codes. Data-efficient characterization methods will prove critical in the fine-tuning and maturation of such CV quantum technology. Although Bayesian inference offers appealing properties—including uncertainty quantification and optimality in mean-squared error—Bayesian methods have yet to be demonstrated for the tomography of arbitrary CV states. Here we introduce a complete Bayesian quantum state tomography workflow capable of inferring generic CV states measured by homodyne or heterodyne detection, with no assumption of Gaussianity. As examples, we demonstrate our approach on experimental coherent, thermal, and cat state data, obtaining excellent agreement between our Bayesian estimates and theoretical predictions. Our approach lays the groundwork for Bayesian estimation of highly complex CV quantum states in emerging quantum photonic platforms, such as quantum communications networks and sensors.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Uniform codes.

Existence of q-ary uniform convolutional codes where q is any prime-power, noting error- correcting ability comparable to familiar maximal- length block codes

ENCODING↗

Analysis of a Coded, M-ary Orthogonal Input Optical Channel with Random-gain Photomultiplier Detection

Performance of two coding systems is analyzed for a noisy optical channel with M(=2(L)-ary orthogonal signaling and random gain photomultiplier detection. The considered coding systems are the Reed Solomon (RS) coding with error only correction decoding and the interleaved binary convolutional system with soft decision Viterbi decoding. The required average number of received signal photons per information bit, N sub b, for a desired bit error of 0.000001 is found for a set of commonly used parameters and with a high background noise level. We find that the interleaved binary convolutional coding system is preferable to the RS coding system in performance complexity tradeoffs.

Lee, P. J.↗

Erasure decoding in burst-error channels

A proven means of communicating reliably in a burst-error channel is the code interleaving scheme. Code symbols from a number of component codes are interleaved before being sent through the channel. This method effectively distributes the error detection and correction burden among the component codes and makes errors occurring in a codeword from each component code more or less independent. Erasure decoding techniques allow further refinement on the code interleaving concept. Their application leads to improved overall code performance when the symbol depth of the lead code is shallow compared to the average error-burst length of the channel. Theoretical formulations derived for predicting the performance of separate decoding and erasure decoding schemes are valuable in providing reasonably good estimates on redundancy requirements of the component codes.

Leung, K. S.↗

The proposed coding standard at GSFC

As part of the continuing effort to introduce standardization of spacecraft and ground equipment in satellite systems, NASA's Goddard Space Flight Center and other NASA facilities have supported the development of a set of standards for the use of error control coding in telemetry subsystems. These standards are intended to ensure compatibility between spacecraft and ground encoding equipment, while allowing sufficient flexibility to meet all anticipated mission requirements. The standards which have been developed to date cover the application of block codes in error detection and error correction modes, as well as short and long constraint length convolutional codes decoded via the Viterbi and sequential decoding algorithms, respectively. Included are detailed specifications of the codes, and their implementation. Current effort is directed toward the development of standards covering channels with burst noise characteristics, channels with feedback, and code concatenation.

Morakis, J. C.↗

Error analysis and correction of discrete solutions from finite element codes

Many structures are an assembly of individual shell components. Therefore, results for stresses and deflections from finite element solutions for each shell component should agree with the equations of shell theory. This paper examines the problem of applying shell theory to the error analysis and the correction of finite element results. The general approach to error analysis and correction is discussed first. Relaxation methods are suggested as one approach to correcting finite element results for all or parts of shell structures. Next, the problem of error analysis of plate structures is examined in more detail. The method of successive approximations is adapted to take discrete finite element solutions and to generate continuous approximate solutions for postbuckled plates. Preliminary numerical results are included.

Thurston, G. A.↗

On the decode error probability for Reed-Solomon codes

Upper bounds on the decoder error probability for Reed-Solomon codes are derived. By definition, decoder error occurs when the decoder finds a codeword other than the transmitted codeword; this is in contrast to decoder failure, which occurs when the decoder fails to find any codeword at all. The results imply, for example, that for a t error correcting Reed-Solomon code of length q - 1 over GF(q), if more than t errors occur, the probability of decoder error is less than 1/t! In particular, for the Voyager Reed-Solomon code, the probability of decoder error given a word error is smaller than 3 x 10 to the minus 14th power. Thus, in a typical operating region with probability 100,000 of word error, the probability of undetected word error is about 10 to the minus 14th power.

Mceliece, R. J.↗

On the decoder error probability for Reed-Solomon codes

Upper bounds on the decoder error probability for Reed-Solomon codes are derived. By definition, decoder error occurs when the decoder finds a codeword other than the transmitted codeword; this is in contrast to decoder failure, which occurs when the decoder fails to find any codeword at all. The results imply, for example, that for a t error-correcting Reed-Solomon code of length q - 1 over GF(q), if more than t errors occur, the probability of decoder error is less than 1/t. In particular, for the Voyager Reed-Solomon code, the probability of decoder error given a word error is smaller than 3 x 10 to the minus 14th power. Thus, in a typical operating region with probability 100,000 of word error, the probability of undetected word error is about 10 to the minus 14th power.

Mceliece, Robert J.↗