Search

We consider the concatenation of a convolutional code (CC) with an optimized cyclic redundancy check (CRC) code as a promising paradigm for good short blocklength codes. The resulting CRC-aided convolutional code naturally permits the use of serial list Viterbi decoding (SLVD) to achieve maximum-likelihood decoding. The convolutional encoder of interest is of rate- $1/\omega $ and the convolutional code is either zero-terminated (ZT) or tail-biting (TB). The resulting CRC-aided convolutional code is called a CRC-ZTCC or a CRC-TBCC. To design a good CRC-aided convolutional code, we propose the distance-spectrum optimal (DSO) CRC polynomial. A DSO CRC search algorithm for the TBCC is provided. Our analysis reveals that the complexity of SLVD is governed by the expected list rank which converges to 1 at high SNR. This allows a good performance to be achieved with a small increase in complexity. In this paper, we focus on transmitting 64 information bits with a rate-1/2 convolutional encoder. For a target error probability $10^{-4}$ , simulations show that the best CRC-ZTCC approaches the random-coding union (RCU) bound within 0.4 dB. Several CRC-TBCCs outperform the RCU bound at moderate SNR values. [ABSTRACT FROM AUTHOR]

This paper uses the reconstruction-computation-quantization (RCQ)paradigm to decode low-density parity-check (LDPC) codes. RCQ facilitates dynamic non-uniform quantization to achieve good frame error rate (FER) performance with very low message precision. For message-passing according to a flooding schedule, the RCQ parameters are designed by discrete density evolution. Simulation results on an IEEE 802.11 LDPC code show that for 4-bit messages, a flooding Min Sum RCQ decoder outperforms table-lookup approaches such as information bottleneck (IB) or Min-IB decoding, with significantly fewer parameters to be stored. Additionally, this paper introduces layer-specific RCQ, an extension of RCQ decoding for layered architectures. Layer-specific RCQ uses layer-specific message representations to achieve the best possible FER performance. For layer-specific RCQ, this paper proposes using layered discrete density evolution featuring hierarchical dynamic quantization (HDQ) to design parameters efficiently. Finally, this paper studies field-programmable gate array (FPGA) implementations of RCQ decoders. Simulation results for a (9472, 8192) quasi-cyclic (QC) LDPC code show that a layered Min Sum RCQ decoder with 3-bit messages achieves more than a 10% reduction in LUTs and routed nets and more than a 6% decrease in register usage while maintaining comparable decoding performance, compared to a 5-bit offset Min Sum decoder. [ABSTRACT FROM AUTHOR]

Variable-length (VL) coding with feedback is a commonly used technique that can approach point-to-point Shannon channel capacity with a significantly shorter average codeword length than fixed-length coding without feedback. This paper uses the inter-frame coding of Zeineddine and Mansour, originally introduced to address varying channel-state conditions in broadcast wireless communication, to approach capacity on point-to-point channels using VL codes without feedback. The per-symbol complexity is comparable to decoding the VL code with feedback (plus the additional complexity of a small peeling decoder amortized over many VL codes) and presents the opportunity for encoders and decoders that utilize massive parallel processing, where each VL decoder can process simultaneously. This paper provides an analytical framework and a design process for the degree distribution of the inter-frame code that allows the feedback-free system to achieve 96% or more of the throughput of the original VL code with feedback. As examples of VL codes, we consider non-binary (NB) low-density parity-check (LDPC), binary LDPC, and convolutional VL codes. The NB-LDPC VL code with an 8-bit CRC and an average codeword length of 336 bits achieves 85% of capacity with four rounds of ACK/NACK feedback. The proposed scheme using shared incremental redundancy without feedback achieves 97% of that performance or 83% of the channel capacity. [ABSTRACT FROM AUTHOR]

Protograph-based Raptor-like low-density parity-check codes (PBRL codes) are a family of easily encodable rate-compatible low-density parity-check (LDPC) codes. PBRL codes have an excellent performance across all design rates. Quasi-cyclic (QC) PBRL code families permit high-speed decoder implementations. PBRL codes designed thus far, for both long and short block-lengths, have been based on optimizing the iterative decoding threshold of the protograph of the PBRL family at various design rates. This paper introduces a design method to obtain better QC PBRL code families at short block-lengths (of a few hundred bits) for low frame error rate (FER) requirements. We first select a protomatrix for the highest design rate. To add a new row to lower the rate, we keep all the previously obtained rows of the PBRL protomatrix fixed and select the new row that maximizes an upper bound on the minimum distance of any QC-LDPC code that can be obtained from the protomatrix. The new QC PBRL code families outperform the original PBRL codes at short block-lengths by providing a significantly better low-FER performance. The standard approach to computing the aforementioned upper bounds requires complexity that grows exponentially with the size of the protomatrix. However, we show that the structure of the PBRL protomatrix lets us obtain the upper bounds with complexity that grows only linearly with the size of the PBRL protomatrix. Using the complexity reduction results, we also establish an equivalence between the exhaustive search to design a new row for the PBRL protomatrix according to the new design method and an integer linear program. [ABSTRACT FROM AUTHOR]

This paper focuses on the design and evaluation of pragmatic schemes for delay-sensitive communication. Specifically, this contribution studies the operation of data links that employ incremental redundancy as a means to shield information bits from the degradation associated with unreliable channels. While this inquiry puts forth a general methodology, exposition centers around erasure channels because they are well suited for analysis. Nevertheless, the goal is to identify both structural properties and design guidelines that are broadly applicable. Conceptually, this paper leverages a methodology, termed sequential differential optimization, aimed at identifying near-optimal block sizes for hybrid ARQ. This technique is applied to erasure channels and it is extended to scenarios where throughput is maximized subject to a constraint on the feedback rate. The analysis shows that the impact of the coding strategy adopted and the propensity of the channel to erase symbols naturally decouple when maximizing throughput. Ultimately, block size selection is informed by approximate distributions on the probability of decoding success at every stage of the incremental transmission process. This novel perspective, which rigorously bridges hybrid automatic repeat request and coding, offers a computationally efficient framework to select code rates and blocklengths for incremental redundancy. These findings are supported through numerical results. [ABSTRACT FROM AUTHOR]

A transmitter sends a packetized message over a fading channel using packet-level erasure coding and physical-layer channel coding of each resultant packet. Given an overall code rate, this paper finds the optimal rates of the erasure code and the channel code to minimize the transmit power required for a certain message error probability. This paper considers a practically important fading model in which the number of block fades in a transmitted channel codeword increases with the codeword length. Such a model applies, for example, in a time-varying channel with a fixed coherence time. The rate at which diversity grows with codeword length plays an important role in the optimization problem. If the diversity growth factor is large enough, then the erasure code plays a minor role, having an optimal rate that is essentially nondecreasing with decreasing overall rate. We prove analytically that, on a channel with linear growth in diversity, as overall rate decreases, the optimal erasure code rate eventually increases to its maximum possible value (e.g., a rate of 1 for an erasure code with no overhead). Additionally, we also consider the optimization problem of minimizing the message error probability given a transmit power. Numerical results again show that erasure coding is not necessary when overall code rates are sufficiently low. [ABSTRACT FROM PUBLISHER]

This paper presents a general approach for optimizing the number of symbols in increments (packets of incremental redundancy) in a feedback communication system with a limited number of increments. This approach is based on a tight normal approximation on the rate for successful decoding. Applying this approach to a variety of feedback systems using nonbinary (NB) low-density parity-check (LDPC) codes shows that greater than 90% of capacity can be achieved with average blocklengths fewer than 500 transmitted bits. One result is that the performance with ten increments closely approaches the performance with an infinite number of increments. The paper focuses on binary-input additive-white Gaussian noise (BI-AWGN) channels but also demonstrates that the normal approximation works well on examples of fading channels as well as high-SNR AWGN channels that require larger QAM constellations. This paper explores both variable-length feedback codes with termination (VLFT) and the more practical variable length feedback (VLF) codes without termination that require no assumption of noiseless transmitter confirmation. For VLF, we consider both a two-phase scheme and CRC-based scheme. [ABSTRACT FROM AUTHOR]

Cyclic redundancy check (CRC) codes check if a codeword is correctly received. This paper presents an algorithm to design CRC codes that are optimized for the code-specific error behavior of a specified feedforward convolutional code. The algorithm utilizes two distinct approaches to computing undetected error probability of a CRC code used with a specific convolutional code. The first approach enumerates the error patterns of the convolutional code and tests if each of them is detectable. The second approach reduces complexity significantly by exploiting the equivalence of the undetected error probability to the frame error rate of an equivalent catastrophic convolutional code. The error events of the equivalent convolutional code are exactly the undetectable errors for the original concatenation of CRC and convolutional codes. This simplifies the computation because error patterns do not need to be individually checked for detectability. As an example, we optimize CRC codes for a commonly used 64-state convolutional code for information length k=1024, demonstrating significant reduction in undetected error probability compared to the existing CRC codes with the same degrees. For a fixed target undetected error probability, the optimized CRC codes typically require 2 fewer bits. [ABSTRACT FROM PUBLISHER]

This paper presents a variable-length decision-feedback coding scheme that achieves high rates at short blocklengths. This scheme uses the reliability-output Viterbi algorithm (ROVA) to determine when the receiver's decoding estimate satisfies a given error constraint. We evaluate the performance of both terminated and tail-biting convolutional codes at average blocklengths less than 300 symbols, using the ROVA and the tail-biting ROVA, respectively. Comparing with recent results from finite-blocklength information theory, simulations for both the BSC and the AWGN channel show that the reliability-based decision-feedback scheme can surpass the random-coding lower bound on throughput for feedback codes at some blocklengths less than 100 symbols. This is true both when decoding after every symbol is permitted and when decoding is limited to a small number of increments. Finally, the performance of the reliability-based stopping rule with the ROVA is compared with retransmission decisions based on CRCs. For short blocklengths where the latency overhead of the CRC bits is severe, the ROVA-based approach delivers superior rates. [ABSTRACT FROM AUTHOR]

This paper proposes protograph-based Raptor-like (PBRL) codes as a class of rate-compatible low-density parity-check codes for binary-input AWGN channels. As with the Raptor codes, exclusive-OR operations on precoded bits produce additional parity bits providing extensive rate compatibility. Unlike Raptor codes, each additional parity bit in the protograph is explicitly designed to optimize the density evolution threshold. During the lifting process, approximate cycle extrinsic message degree (ACE) and circulant progressive edge growth (CPEG) constraints are used to avoid undesirable graphical structures. Some density-evolution performance is sacrificed to obtain lower error floors, particularly at short blocklengths. Simulation results are shown for information block sizes of k=1032\ \and\ 16\,384. For a target frame error rate of 10^-5, at each rate, the k=1032\ \and \ 16\,384 code families perform within 1 dB and 0.4 dB of both the Gallager bound and the normal approximation, respectively. The 16 384 code family outperforms the best known standardized code family, namely, the AR4JA codes. The PBRL codes also outperform DVB-S2 codes that have the advantages of longer blocklengths and outer BCH codes. Performance is similar to RC code families designed by Nguyen et al. that do not constrain codes to have the PBRL structure and involve simulation in the optimization process at each rate. [ABSTRACT FROM PUBLISHER]

For low-density parity-check (LDPC) codes operating over additive white Gaussian noise channels and decoded using message-passing decoders with limited precision, absorbing sets have been shown to be a key factor in error floor behavior. Focusing on this scenario, this paper introduces the cycle consistency matrix (CCM) as a powerful analytical tool for characterizing and avoiding absorbing sets in separable circulant-based (SCB) LDPC codes. SCB codes include a wide variety of regular LDPC codes such as array-based LDPC codes as well as many common quasi-cyclic codes. As a consequence of its cycle structure, each potential absorbing set in an SCB LDPC code has a CCM, and an absorbing set can be present in an SCB LDPC code only if the associated CCM has a nontrivial null space. CCM-based analysis can determine the multiplicity of an absorbing set in an SCB code, and CCM-based constructions avoid certain small absorbing sets completely. While these techniques can be applied to an SCB code of any rate, lower rate SCB codes can usually avoid small absorbing sets because of their higher variable-node degree. This paper focuses attention on the high-rate scenario in which the CCM constructions provide the most benefit. Simulation results demonstrate that under limited-precision decoding the new codes have steeper error-floor slopes and can provide one order of magnitude of improvement in the low-frame-error-rate region. [ABSTRACT FROM PUBLISHER]

This paper presents a practical technique that uses Ping's interleave(r)-division multiple access and single-user decoding to provide uncoordinated access for a family of binary-input binary-output multiple-access channels (MACs) including the OR-MAC where users' binary transmissions are combined with the logical OR operation. Information theoretic calculations provide the achievable sum-rates and optimal ones densities for these MACs. Because the required ones densities are significantly less than 50%, new nonlinear trellis code analysis and design techniques are introduced to provide the needed codes. Union bound techniques that predict the performance of these codes are also presented. Simulation results and a working FPGA implementation verify the performance and feasibility of the proposed nonlinear codes and overall multiple access scheme. [ABSTRACT FROM AUTHOR]