Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Decoder”

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 631 records · Page 35

Bit error probability calculations for convolutional codes with short constraint lengths on very noisy channels

A technique for estimating convolutional code performance on very noisy channels is considered. Specifically, the performance of short constraint length codes operating near the channel cutoff rate is estimated. Decoding convolutional codes with a sliding window decoder (SWD) are considered. This decoder is an optimal (maximum likelihood) symbol decoder as the window size grows toward infinity, while the Viterbi decoder is the maximum-likelihood sequence estimator. The difference in the decoded BERs (bit error rates) between the two decoders is very small and approaches zero asymptotically as the channel BER decreases. Therefore, an estimate on the decoded BER for the SWD can also be used as an estimate of the decoded BER for Viterbi decoding.

Herro, Mark A.↗

High rate concatenated coding systems using bandwidth efficient trellis inner codes

High-rate concatenated coding systems with bandwidth-efficient trellis inner codes and Reed-Solomon (RS) outer codes are investigated for application in high-speed satellite communication systems. Two concatenated coding schemes are proposed. In one the inner code is decoded with soft-decision Viterbi decoding, and the outer RS code performs error-correction-only decoding (decoding without side information). In the other, the inner code is decoded with a modified Viterbi algorithm, which produces reliability information along with the decoded output. In this algorithm, path metrics are used to estimate the entire information sequence, whereas branch metrics are used to provide reliability information on the decoded sequence. This information is used to erase unreliable bits in the decoded output. An errors-and-erasures RS decoder is then used for the outer code. The two schemes have been proposed for high-speed data communication on NASA satellite channels. The rates considered are at least double those used in current NASA systems, and the results indicate that high system reliability can still be achieved.

Deng, Robert H.↗

NISQ+: Boosting quantum computing power by approximating quantum error correction

Quantum computers are growing in size, and design decisions are being made now that attempt to squeeze more computation out of these machines. In this spirit, we design a method to boost the computational power of near-term quantum computers by adapting protocols used in quantum error correction to implement "Approximate Quantum Error Correction (AQEC)." By approximating fully-fledged error correction mechanisms, we can increase the compute volume (qubits × gates, or "Simple Quantum Volume (SQV)") of near-term machines. The crux of our design is a fast hardware decoder that can approximately decode detected error syndromes rapidly. Specifically, we demonstrate a proof-of-concept that approximate error decoding can be accomplished online in near-term quantum systems by designing and implementing a novel algorithm in Single-Flux Quantum (SFQ) superconducting logic technology. This avoids a critical decoding backlog, hidden in all offline decoding schemes, that leads to idle time exponential in the number of T gates in a program. Our design utilizes one SFQ processing module per physical qubit. Employing state-of-the-art SFQ synthesis tools, we show that the circuit area, power, and latency are within the constraints of contemporary quantum system designs. Under pure dephasing error models, the proposed accelerator and AQEC solution is able to expand SQV by factors between 3,402 and 11,163 on expected near-term machines. The decoder achieves a 5% accuracy-threshold and pseudo-thresholds of ~ 5%,4.75%,4.5%, and 3.5% physical error-rates for code distances 3,5,7, and 9. Decoding solutions are achieved in a maximum of ~20 nanoseconds on the largest code distances studied. By avoiding the exponential idle time in offline decoders, we achieve a 10x reduction in required code distances to achieve the same logical performance as alternative designs.

97 MATHEMATICS AND COMPUTING↗

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↗

Error control techniques for satellite and space communications

High rate concatenated coding systems with trellis inner codes and Reed-Solomon (RS) outer codes for application in satellite communication systems are considered. Two types of inner codes are studied: high rate punctured binary convolutional codes which result in overall effective information rates between 1/2 and 1 bit per channel use; and bandwidth efficient signal space trellis codes which can achieve overall effective information rates greater than 1 bit per channel use. Channel capacity calculations with and without side information performed for the concatenated coding system. Concatenated coding schemes are investigated. In Scheme 1, the inner code is decoded with the Viterbi algorithm and the outer RS code performs error-correction only (decoding without side information). In scheme 2, the inner code is decoded with a modified Viterbi algorithm which produces reliability information along with the decoded output. In this algorithm, path metrics are used to estimate the entire information sequence, while branch metrics are used to provide the reliability information on the decoded sequence. This information is used to erase unreliable bits in the decoded output. An errors-and-erasures RS decoder is then used for the outer code. These two schemes are proposed for use on NASA satellite channels. Results indicate that high system reliability can be achieved with little or no bandwidth expansion.

Costello, D. J., Jr.↗

Multi-dimensional modulation codes for fading channel

Some new codes are presented which have good performance on Rician fading channel with small decoding complexities. A new M-way partition chain is proposed for the L x MPSK (L less than or equal to M) signal set which maximizes the intra-set distance of each subset at each partition level. Based on this partition chain, a class of asymptotical optimum codes was found. For M = 4, these codes have both large symbol distances and product distances. Multi-level coding scheme allows to construct a code by hand such that the code meets some desired parameters, e.g., symbol distance, product distance, etc. In design of a multi-level code, all factors were considered which affect the performance and complexity of the code, such as, the decoding scheme, decoding complexity, and performance under the decoding scheme, e.g., if the multi-stage decoding scheme is used, the performance degradation due to the suboptimum decoding is taken into consideration. The performance for most of the presented codes was simulated on Rayleigh fading channel, and the results show that these codes have good performance with small decoding complexities.

Lin, Shu↗

Circuit Design Approaches for Implementation of a Subtrellis IC for a Reed-Muller Subcode

In this research, we have proposed the (64, 40, 8) subcode of the third-order Reed-Muller (RM) code to NASA for high-speed satellite communications. This RM subcode can be used either alone or as an inner code of a concatenated coding system with the NASA standard (255, 233, 33) Reed-Solomon (RS) code as the outer code to achieve high performance (or low bit-error rate) with reduced decoding complexity. It can also be used as a component code in a multilevel bandwidth efficient coded modulation system to achieve reliable bandwidth efficient data transmission. This report will summarize the key progress we have made toward achieving our eventual goal of implementing a decoder system based upon this code. In the first phase of study, we investigated the complexities of various sectionalized trellis diagrams for the proposed (64, 40, 8) RM subcode. We found a specific 8-trellis diagram for this code which requires the least decoding complexity with a high possibility of achieving a decoding speed of 600 M bits per second (Mbps). The combination of a large number of states and a high data rate will be made possible due to the utilization of a high degree of parallelism throughout the architecture. This trellis diagram will be presented and briefly described. In the second phase of study which was carried out through the past year, we investigated circuit architectures to determine the feasibility of VLSI implementation of a high-speed Viterbi decoder based on this 8-section trellis diagram. We began to examine specific design and implementation approaches to implement a fully custom integrated circuit (IC) which will be a key building block for a decoder system implementation. The key results will be presented in this report. This report will be divided into three primary sections. First, we will briefly describe the system block diagram in which the proposed decoder is assumed to be operating and present some of the key architectural approaches being used to implement the system at high speed. Second, we will describe details of the 8-trellis diagram we found to best meet the trade-offs between chip and overall system complexity. The chosen approach implements the trellis for the (64, 40, 8) RM subcode with 32 independent sub-trellises. And third, we will describe results of our feasibility study on the implementation of such an IC chip in CMOS technology to implement one of these subtrellises.

Lin, Shu↗

Circuit Design Approaches for Implementation of a Subtrellis IC for a Reed-Muller Subcode

In his research, we have proposed the (64, 40, 8) subcode of the third-order Reed-Muller (RM) code to NASA for high-speed satellite communications. This RM subcode can be used either alone or as an inner code of a concatenated coding system with the NASA standard (255, 233, 33) Reed-Solomon (RS) code as the outer code to achieve high performance (or low bit-error rate) with reduced decoding complexity. It can also be used as a component code in a multilevel bandwidth efficient coded modulation system to achieve reliable bandwidth efficient data transmission. This report will summarize the key progress we have made toward achieving our eventual goal of implementing a decoder system based upon this code. In the first phase of study, we investigated the complexities of various sectionalized trellis diagrams for the proposed (64, 40, 8) RM subcode. We found a specific 8-trellis diagram for this code which requires the least decoding complexity with a high possibility of achieving a decoding speed of 600 M bits per second(Mbps). The combination of a large number of states and a high data rate will be made possible due to the utilization of a high degree of parallelism throughout the architecture. This trellis diagram will be presented and briefly described. In the second phase of study which was carried out through the past year, we investigated circuit architectures to determine the feasibility of VLSI implementation of a high- speed Viterbi decoder based on this 8-section trellis diagram. We began to examine specific design and implementation approaches to implement a fully custom integrated circuit (IC) which will be a key building block for a decoder system implementation. The key results will be presented in this report. This report will be divided into three primary sections. First, we will briefly describe the system block diagram in which the proposed decoder is assumed to be operating and present some of the key architectural approaches being used to implement the system at high speed. Second, we will describe details of the 8-trellis diagram we found to best meet the trade-offs between chip and overall system complexity. The chosen approach implements the trellis for the (64, 40, 8) RM subcode with 32 independent sub-trellises. And third, we will describe results of our feasibility study on the implementation of such an IC chip in CMOS technology to implement one of these subtrellises.

Lin, Shu↗

Bubble domain circuit organization

An on-chip bubble domain circuit organization. One or more storage registers are connected to a propagation path whereby data in the form of magnetic bubble domains (bubbles) may be transferred into and out of the storage registers. The propagation path includes a generator for producing the initial bubbles which are expanded into any desired number of new bubbles by a unique multiple output replicator. A unique input decoder is utilized to determine to which storage register the bubbles from the replicator will be directed along the propagation path. Those bubbles not selected may be annihilated. An output decoder utilizing essentially the same decoding scheme as the input decoder, selectively receives bubbles from the storage register. A transfer and replicate switch is utilized between the storage register and output decoder to selectively transfer bubbles to the output decoder. The output decoder may collapse all of the bubbles from certain storage registers so that only the information from the selected storage register reaches the detector. The detectors in turn produce the chip output signal. External control electronics are utilized to control the selective operation of the various devices utilized in the propagation path.

Chen, Thomas T.↗

Implementation of a Coded Modulation for Deep Space Optical Communications

We present a field programmable gate array code (FPGA) implementation of a turbo-like decoder for a serially concatenated pulse-position modulation (SCPPM) code. NASA a developed this coded modulation scheme for deep space communications from Mars. Under a nominal mission condition, the decoder complexity by iteratively decoding the modulation and SCPPM coded system can operate within a one dB signal energy gap from capacity. The structure of SCPPM makes direct application of the conventional turbo decoding algorithm very inefficient. Here, we describe techniques to increase the throughput and performance of a hardware SCPPM decoder. using our optimizations, we demonstrate a 6 mega-bits per second (Mbps) decoder realization on a single FPGA. Extension toa higher data rate decoder using multiple FPGAs is readily achievable. Similar codes designed for the optical channel can benefit from our optimization techniques.

modulation↗

Prioritized LT Codes

The original Luby Transform (LT) coding scheme is extended to account for data transmissions where some information symbols in a message block are more important than others. Prioritized LT codes provide unequal error protection (UEP) of data on an erasure channel by modifying the original LT encoder. The prioritized algorithm improves high-priority data protection without penalizing low-priority data recovery. Moreover, low-latency decoding is also obtained for high-priority data due to fast encoding. Prioritized LT codes only require a slight change in the original encoding algorithm, and no changes at all at the decoder. Hence, with a small complexity increase in the LT encoder, an improved UEP and low-decoding latency performance for high-priority data can be achieved. LT encoding partitions a data stream into fixed-sized message blocks each with a constant number of information symbols. To generate a code symbol from the information symbols in a message, the Robust-Soliton probability distribution is first applied in order to determine the number of information symbols to be used to compute the code symbol. Then, the specific information symbols are chosen uniform randomly from the message block. Finally, the selected information symbols are XORed to form the code symbol. The Prioritized LT code construction includes an additional restriction that code symbols formed by a relatively small number of XORed information symbols select some of these information symbols from the pool of high-priority data. Once high-priority data are fully covered, encoding continues with the conventional LT approach where code symbols are generated by selecting information symbols from the entire message block including all different priorities. Therefore, if code symbols derived from high-priority data experience an unusual high number of erasures, Prioritized LT codes can still reliably recover both high- and low-priority data. This hybrid approach decides not only "how to encode" but also "what to encode" to achieve UEP. Another advantage of the priority encoding process is that the majority of high-priority data can be decoded sooner since only a small number of code symbols are required to reconstruct high-priority data. This approach increases the likelihood that high-priority data is decoded first over low-priority data. The Prioritized LT code scheme achieves an improvement in high-priority data decoding performance as well as overall information recovery without penalizing the decoding of low-priority data, assuming high-priority data is no more than half of a message block. The cost is in the additional complexity required in the encoder. If extra computation resource is available at the transmitter, image, voice, and video transmission quality in terrestrial and space communications can benefit from accurate use of redundancy in protecting data with varying priorities.

Woo, Simon S.↗

The Limits of Coding with Joint Constraints on Detected and Undetected Error Rates

We develop a remarkably tight upper bound on the performance of a parameterized family of bounded angle maximum-likelihood (BA-ML) incomplete decoders. The new bound for this class of incomplete decoders is calculated from the code's weight enumerator, and is an extension of Poltyrev-type bounds developed for complete ML decoders. This bound can also be applied to bound the average performance of random code ensembles in terms of an ensemble average weight enumerator. We also formulate conditions defining a parameterized family of optimal incomplete decoders, defined to minimize both the total codeword error probability and the undetected error probability for any fixed capability of the decoder to detect errors. We illustrate the gap between optimal and BA-ML incomplete decoding via simulation of a small code.

Undetected Error Rate↗

The impact of mismatch on the performance of coded narrow-band FM with limiter/discriminator detection

An examination of the impact of mismatch on the performance of convolutionally encoded/Viterbi decoded narrow-band FM with limiter/discriminator detection is presented. Attention was given to the potential gain available by the combination of this type of system in terms of hard and soft decision decoding. Soft decision decoding was demonstrated to offer only approximately 0.3 dB better performance than hard decision coding. It was also shown, through a technique involving the number of clicks occurring in each detection interval, that both soft and hard decision decoding bit error probability performance could be improved. It is concluded that the mismatch between the coding channel and the decoding metric of the Viterbi algorithm is responsible for reducing the difference between hard and soft decoding metrics.

Simon, M. K.↗

A VLSI decomposition of the deBruijn graph

A new Viterbi decoder for convolutional codes with constraint lengths up to 15, called the Big Viterbi Decoder, is under development for the Deep Space Network. It will be demonstrated by decoding data from the Galileo spacecraft, which has a rate 1/4, constraint-length 15 convolutional encoder on board. Here, the mathematical theory underlying the design of the very-large-scale-integrated (VLSI) chips that are being used to build this decoder is explained. The deBruijn graph B sub n describes the topology of a fully parallel, rate 1/v, constraint length n+2 Viterbi decoder, and it is shown that B sub n can be built by appropriately wiring together (i.e., connecting together with extra edges) many isomorphic copies of a fixed graph called a B sub n building block. The efficiency of such a building block is defined as the fraction of the edges in B sub n that are present in the copies of the building block. It is shown, among other things, that for any alpha less than 1, there exists a graph G which is a B sub n building block of efficiency greater than alpha for all sufficiently large n. These results are illustrated by describing a special hierarchical family of deBruijn building blocks, which has led to the design of the gate-array chips being used in the Big Viterbi Decoder.

Collins, O.↗

Bandwidth efficient coding for satellite communications

An error control coding scheme was devised to achieve large coding gain and high reliability by using coded modulation with reduced decoding complexity. To achieve a 3 to 5 dB coding gain and moderate reliability, the decoding complexity is quite modest. In fact, to achieve a 3 dB coding gain, the decoding complexity is quite simple, no matter whether trellis coded modulation or block coded modulation is used. However, to achieve coding gains exceeding 5 dB, the decoding complexity increases drastically, and the implementation of the decoder becomes very expensive and unpractical. The use is proposed of coded modulation in conjunction with concatenated (or cascaded) coding. A good short bandwidth efficient modulation code is used as the inner code and relatively powerful Reed-Solomon code is used as the outer code. With properly chosen inner and outer codes, a concatenated coded modulation scheme not only can achieve large coding gains and high reliability with good bandwidth efficiency but also can be practically implemented. This combination of coded modulation and concatenated coding really offers a way of achieving the best of three worlds, reliability and coding gain, bandwidth efficiency, and decoding complexity.

Lin, Shu↗

Coset Codes Viewed as Terminated Convolutional Codes

In this paper, coset codes are considered as terminated convolutional codes. Based on this approach, three new general results are presented. First, it is shown that the iterative squaring construction can equivalently be defined from a convolutional code whose trellis terminates. This convolutional code determines a simple encoder for the coset code considered, and the state and branch labelings of the associated trellis diagram become straightforward. Also, from the generator matrix of the code in its convolutional code form, much information about the trade-off between the state connectivity and complexity at each section, and the parallel structure of the trellis, is directly available. Based on this generator matrix, it is shown that the parallel branches in the trellis diagram of the convolutional code represent the same coset code C(sub 1), of smaller dimension and shorter length. Utilizing this fact, a two-stage optimum trellis decoding method is devised. The first stage decodes C(sub 1), while the second stage decodes the associated convolutional code, using the branch metrics delivered by stage 1. Finally, a bidirectional decoding of each received block starting at both ends is presented. If about the same number of computations is required, this approach remains very attractive from a practical point of view as it roughly doubles the decoding speed. This fact is particularly interesting whenever the second half of the trellis is the mirror image of the first half, since the same decoder can be implemented for both parts.

Fossorier, Marc P. C.↗

Coupled Receiver/Decoders for Low-Rate Turbo Codes

been proposed for receiving weak single- channel phase-modulated radio signals bearing low-rate-turbo-coded binary data. Originally intended for use in receiving telemetry signals from distant spacecraft, the proposed receiver/ decoders may also provide enhanced reception in mobile radiotelephone systems. A radio signal of the type to which the proposal applies comprises a residual carrier signal and a phase-modulated data signal. The residual carrier signal is needed as a phase reference for demodulation as a prerequisite to decoding. Low-rate turbo codes afford high coding gains and thereby enable the extraction of data from arriving radio signals that might otherwise be too weak. In the case of a conventional receiver, if the signal-to-noise ratio (specifically, the symbol energy to one-sided noise power spectral density) of the arriving signal is below approximately 0 dB, then there may not be enough energy per symbol to enable the receiver to recover properly the carrier phase. One could solve the problem at the transmitter by diverting some power from the data signal to the residual carrier. A better solution . a coupled receiver/decoder according to the proposal . could reduce the needed amount of residual carrier power. In all that follows, it is to be understood that all processing would be digital and the incoming signals to be processed would be, more precisely, outputs of analog-to-digital converters that preprocess the residual carrier and data signals at a rate of multiple samples per symbol. The upper part of the figure depicts a conventional receiving system, in which the receiver and decoder are uncoupled, and which is also called a non-data-aided system because output data from the decoder are not used in the receiver to aid in recovering the carrier phase. The receiver tracks the carrier phase from the residual carrier signal and uses the carrier phase to wipe phase noise off the data signal. The receiver typically includes a phase-locked loop (PLL) or Costas loop that requires no delay or perhaps a single sample delay. The lower part of the figure depicts a basic coupled receiver/decoder . a data-aided system that would implement an iterative receiving/decoding process. The receiver would include a PLL or a Wiener filter that, to the extent possible, would track the residual carrier signal, wipe phase noise off the data signal, then send the result to the turbo decoder. Recovery of timing could be effected by, for example, a digital transition tracking loop (DTTL) or other, similar loop. The first iteration of turbo decoding would yield soft data symbols, which would be sent back to the receiver for use in softly wiping off the data signal in an effort to recover the residual carrier signal. The wiped signal would contain a relatively large carrier-phase component that could be tracked by use of a second Wiener filter.

Hamkins, Jon↗

Serial-Turbo-Trellis-Coded Modulation with Rate-1 Inner Code

Serially concatenated turbo codes have been proposed to satisfy requirements for low bit- and word-error rates and for low (in comparison with related previous codes) complexity of coding and decoding algorithms and thus low complexity of coding and decoding circuitry. These codes are applicable to such high-level modulations as octonary phase-shift keying (8PSK) and 16-state quadrature amplitude modulation (16QAM); the signal product obtained by applying one of these codes to one of these modulations is denoted, generally, as serially concatenated trellis-coded modulation (SCTCM). These codes could be particularly beneficial for communication systems that must be designed and operated subject to limitations on bandwidth and power. Some background information is prerequisite to a meaningful summary of this development. Trellis-coded modulation (TCM) is now a well-established technique in digital communications. A turbo code combines binary component codes (which typically include trellis codes) with interleaving. A turbo code of the type that has been studied prior to this development is composed of parallel concatenated convolutional codes (PCCCs) implemented by two or more constituent systematic encoders joined through one or more interleavers. The input information bits feed the first encoder and, after having been scrambled by the interleaver, enter the second encoder. A code word of a parallel concatenated code consists of the input bits to the first encoder followed by the parity check bits of both encoders. The suboptimal iterative decoding structure for such a code is modular, and consists of a set of concatenated decoding modules one for each constituent code connected through an interleaver identical to the one in the encoder side. Each decoder performs weighted soft decoding of the input sequence. PCCCs yield very large coding gains at the cost of a reduction in the data rate and/or an increase in bandwidth.

Divsalar, Dariush↗