Posterior matching uses variable-length encoding controlled by noiseless feedback of the received symbols to achieve high rates for short average blocklengths. Traditionally, the feedback of a received symbol occurs before the next symbol is transmitted. The transmitter optimizes the next symbol transmission with full knowledge of every past received symbol.To move posterior matching closer to practical communication, this paper limits how often feedback can be sent. We focus on reducing the frequency of the feedback while still maintaining the high rates that posterior matching achieves with feedback after every symbol. As it turns out, the frequency of the feedback can be reduced significantly with no noticeable reduction in rate.

Free-space optical (FSO) links are sensitive to channel fading caused by atmospheric turbulence, varying weather conditions, and changes in the distance between the transmitter and receiver. To mitigate FSO fading, this paper applies linear and quadratic prediction to estimate fading channel conditions and dynamically select the appropriate low-density parity check (LDPC) code rate. This adaptivity achieves reliable communication while efficiently utilizing the available channel mutual information. Protograph-based Raptor-like (PBRL) LDPC codes supporting a wide range of rates are designed, facilitating convenient rate switching. When channel state information (CSI) is known without delay, dynamically selecting LDPC code rate appropriately maximizes throughput. This work explores how such prediction behaves as the feedback delay is increased from no delay to a delay of 4 ms for a channel with a coherence time of 10 ms.

For a two-variance model of the Flash read channel that degrades as a function of the number of program/erase cycles, this paper demonstrates that selecting write voltages to maximize the minimum page mutual information (MI) can increase device lifetime. In multi-level cell (MLC) Flash memory, one of four voltage levels is written to each cell, according to the values of the most-significant bit (MSB) page and the least-significant bit (LSB) page. In our model, each voltage level is then distorted by signal-dependent additive Gaussian noise that approximates the Flash read channel. When performing an initial read of a page in MLC flash, one (for LSB) or two (for MSB) bits of information are read for each cell of the page. If LDPC decoding fails after the initial read, then an enhanced-precision read is performed. This paper shows that jointly designing write voltage levels and read thresholds to maximize the minimum MI between a page and its associated initial or enhanced-precision read bits can improve LDPC decoding performance.

Convolutional codes have been widely studied and used in many systems. As the number of memory elements increases, frame error rate (FER) improves but computational complexity increases exponentially. Recently, decoders that achieve reduced average complexity through list decoding have been demonstrated when the convolutional encoder polynomials share a common factor that can be understood as a CRC or more generally an expurgating linear function (ELF). However, classical convolutional codes avoid such common factors because they result in a catastrophic encoder. This paper provides a way to access the complexity reduction possible with list decoding even when the convolutional encoder polynomials do not share a common factor. Decomposing the original code into component encoders that fully exclude some polynomials can allow an ELF to be factored from each component. Dual list decoding of the component encoders can often find the ML codeword. Including a fallback to regular Viterbi decoding yields excellent FER performance while requiring less average complexity than always performing Viterbi on the original trellis. A best effort dual list decoder that avoids Viterbi has performance similar to the ML decoder. Component encoders that have a shared polynomial allow for even greater complexity reduction.

With a sufficiently large list size, the serial list Viterbi algorithm (S-LVA) provides maximum likelihood (ML) decoding of a concatenated convolutional code (CC) and an expurgating linear function (ELF), which is similar in function to a cyclic redundancy check (CRC), but doesn't enforce that the code be cyclic. However, S-LVA with a large list size requires considerable complexity. This paper exploits linearity to reduce decoding complexity for tail-biting CCs (TBCCs) concatenated with ELFs.

This paper presents new achievability bounds on the maximal achievable rate of variable-length stop-feedback (VLSF) codes operating over a binary erasure channel (BEC) at a fixed message size${M}=2^{k}$. We provide bounds for two cases: The first case considers VLSF codes with possibly infinite decoding times and zero error probability. The second case limits the maximum (finite) number of decoding times and specifies a maximum tolerable probability of error. Both new achievability bounds are proved by constructing a new VLSF code that employs systematic transmission of the first$k$message bits followed by random linear fountain parity bits decoded with a rank decoder. For VLSF codes with infinite decoding times, our new bound outperforms the state-of-the-art result for BEC by Devassy et al. in 2016. We show that the backoff from capacity reduces to zero as the erasure probability decreases, thus giving a negative answer to the open question Devassy et al. posed on whether the 23.4% backoff to capacity at$k=3$is fundamental to all BECs. For VLSF codes with finite decoding times, numerical evaluations show that the systematic transmission followed by random linear fountain coding performs better than random linear coding in terms of achievable rates.

Recently, rate-$1/n$zero-terminated (ZT) and tail-biting (TB) convolutional codes (CCs) with cyclic redundancy check (CRC)-aided list decoding have been shown to closely approach the random-coding union (RCU) bound for short blocklengths. This paper designs CRC polynomials for rate-$(n-1)/n$ZT and TB CCs with short blocklengths. This paper considers both standard rate-$(n-1)/n$CC polynomials and rate-$(n-1)/n$designs resulting from puncturing a rate-$1/2$code. The CRC polynomials are chosen to maximize the minimum distance$d_{\min }$and minimize the number of nearest neighbors$A_{d_{\min }}$. For the standard rate-$(n-1)/n$codes, utilization of the dual trellis proposed by Yamada et al. lowers the complexity of CRC-aided serial list Viterbi decoding (SLVD). CRC-aided SLVD of the TBCCs closely approaches the RCU bound at a blocklength of 128. This paper compares the FER performance (gap to the RCU bound) and complexity of the CRC-aided standard and punctured ZTCCs and TBCCs. This paper also explores the complexity-performance trade-off for three TBCC decoders: a single-trellis approach, a multi-trellis approach, and a modified single-trellis approach with pre-processing using the wrap around Viterbi algorithm.

Recently, neural networks have improved MinSum message-passing decoders for low-density parity-check (LDPC) codes by multiplying or adding weights to the messages, where the weights are determined by a neural network. The neural network complexity to determine distinct weights for each edge is high, often limiting the application to relatively short LDPC codes. Furthermore, storing separate weights for every edge and every iteration can be a burden for hardware implementations. To reduce neural network complexity and storage requirements, this paper proposes a family of weight-sharing schemes that use the same weight for edges that have the same check node degree and/or variable node degree. Our simulation results show that node-degree-based weight-sharing can deliver the same performance requiring distinct weights for each node. This paper also combines these degree-specific neural weights with a reconstruction-computation-quantization (RCQ) decoder to produce a weighted RCQ (W-RCQ) decoder. The W-RCQ decoder with node-degree-based weight sharing has a reduced hardware requirement compared with the original RCQ decoder. As an additional contribution, this paper identifies and resolves a gradient explosion issue that can arise when training neural LDPC decoders.

Horstein, Burnashev, Shayevitz and Feder, Naghshvar et al. and others have studied sequential transmission of a k-bit message over the binary symmetric channel (BSC) with full, noiseless feedback using posterior matching. Yang et al. provide an improved lower bound on the achievable rate using martingale analysis that relies on the small-enough difference (SED) partitioning introduced by Naghshvar et al. SED requires a relatively complex encoder and decoder. To reduce complexity, this paper replaces SED with relaxed constraints that admit the small enough absolute difference (SEAD) partitioning rule. The main analytical results show that achievable-rate bounds higher than those found by Yang et al. (2021) are possible even under the new constraints, which are less restrictive than SED. The new analysis does not use martingale theory for the confirmation phase and applies a surrogate channel technique to tighten the results. An initial systematic transmission further increases the achievable rate bound. The simplified encoder associated with SEAD has a complexity below order$O(K^{2})$and allows simulations for message sizes of at least 1000 bits. For example, simulations achieve 99% of of the channel’s 0.50-bit capacity with an average block size of 200 bits for a target codeword error rate of$10^{-3}$.

This paper applies probabilistic amplitude shaping (PAS) to cyclic redundancy check (CRC)-aided tail-biting trellis-coded modulation (TCM). CRC-TCM-PAS produces practical codes for short block lengths on the additive white Gaussian noise (AWGN) channel. In the transmitter, equally likely message bits are encoded by a distribution matcher (DM) generating amplitude symbols with a desired distribution. A CRC is appended to the sequence of amplitude symbols, and this sequence is then encoded and modulated by TCM to produce real-valued channel input signals. This paper proves that the sign values produced by the TCM are asymptotically equally likely to be positive or negative. The CRC-TCM-PAS scheme can thus generate channel input symbols with a symmetric capacity-approaching probability mass function. The paper provides an analytical upper bound on the frame error rate of the CRC-TCM-PAS system over the AWGN channel. This FER upper bound is the objective function used for jointly optimizing the CRC and convolutional code. Additionally, this paper proposes a multi-composition DM, which is a collection of multiple constant-composition DMs. The optimized CRC-TCM-PAS systems achieve frame error rates below the random coding union (RCU) bound in AWGN and outperform the short-blocklength PAS systems with various other forward error correction codes studied in Coşkun et al. (2019).

We extend earlier work on the design of convolutional code-specific CRC codes to$Q$-ary alphabets, with an eye toward$Q$-ary orthogonal signaling. Starting with distance-spectrum optimal, zero-terminated,$Q$-ary convolutional codes, we design$Q$-ary CRC codes so that the CRC/convolutional concatenation is distance-spectrum optimal. The$Q$-ary code symbols are mapped to a$Q$-ary orthogonal signal set and sent over an AWGN channel with noncoherent reception. We focus on$Q=4$, rate-1/2 convolutional codes in our designs. The random coding union bound and normal approximation are used in earlier works as benchmarks for performance for distance-spectrum-optimal convolutional codes. We derive a saddlepoint approximation of the random coding union bound for the coded noncoherent signaling channel, as well as a normal approximation for this channel, and compare the performance of our codes to these limits. Our best design is within 0.6 dB of the RCU bound at a frame error rate of 10−4.

This paper derives a union bound on the frame error rate (FER) of a probabilistic amplitude shaping (PAS) system which uses a CRC-aided,$\text{ rate }-\frac{k}{k+1}$, systematic, recursive trellis-coded modulation (TCM). A tail-biting convolutional code (TBCC) provides the feed-forward error correction (FEC) code for the TCM. The system is referred as CRC-TCM-PAS [1]. In order to derive the union bound, we first prove that the concatenation of a CRC and a$\text{ rate }-\frac{k}{k+1}$convolutional code is equivalent to a new convolutional code. Then, we give the generating function of the new convolutional code using Biglieri's product-state-diagram approach. A union bound can be cal-culated using the generating function. Simulation results show that the derived union bound is tight in the high signal-to-noise ratio (SNR) regime and can be used to design the convolutional and CRC codes. Simulation results also show that the optimized CRC-TCM-PAS system exceeds the random coding union (RCU) bound and outperforms the PAS systems with various FEC codes studied in [2] for the same number of input bits and the same transmission rate.

This paper explores list decoding of convolutional and polar codes for short messages such as those found in the 5G physical broadcast channel. A cyclic redundancy check (CRC) is used to select a codeword from a list of likely codewords. One example in the 5G standard encodes a 32-bit message with a 24-bit CRC and a 512-bit polar code with additional bits added by repetition to achieve a very low rate of 32/864. This paper shows that optimizing the CRC length improves the Eb/N0performance of this polar code, where Eb/N0is the ratio of the energy per data bit to the noise power spectral density. Furthermore, even better Eb/ N0performance is achieved by replacing the polar code with a tail-biting convolutional code (TBCC) with a distance-spectrum-optimal (DSO) CRC. This paper identifies the optimal CRC length to minimize the frame error rate (FER) of a rate-1/5 TBCC at a specific value of Eb/ N0. We also show that this optimized TBCC/CRC can attain the same excellent Eb/ N0performance with the very low rate of 32/864 of the 5G polar code, where the low rate is achieved through repetition. We show that the proposed TBCC/CRC concatenated code outperforms the PBCH polar code described in the 5G standard both in terms of FER and decoding run time. We also explore the tradeoff between undetected error rate and erasure rate as the CRC size varies.

The Consultative Committee for Space Data Systems (CCSDS) 141.11-O-1 Line Product Code (LPC) provides a rare opportunity to compare maximum-likelihood decoding and message passing. The LPC considered in this paper is intended to serve as the inner code in conjunction with a (255,239) Reed Solomon (RS) code whose symbols are bytes of data. This paper represents the 141.11-O-1 LPC as a bipartite graph and uses that graph to formulate both maximum likelihood (ML) and message passing algorithms. ML decoding must, of course, have the best frame error rate (FER) performance. However, a fixed point implementation of a Neural-Normalized MinSum (N-NMS) message passing decoder closely approaches ML performance with a significantly lower complexity.

Recently, rate-1/ω zero-terminated and tail-biting convolutional codes (ZTCCs and TBCCs) with cyclic-redundancy-check (CRC)-aided list decoding have been shown to closely approach the random-coding union (RCU) bound for short blocklengths. This paper designs CRC polynomials for rate-(ω – 1)/ω CCs with short blocklengths, considering both the ZT and TB cases. The CRC design seeks to optimize the frame error rate (FER) performance of the code resulting from the concatenation of the CRC code and the CC. Utilization of the dual trellis proposed by Yamada et al. lowers the complexity of CRC-aided serial list Viterbi decoding (SLVD) of ZTCCs and TBCCs. CRC-aided SLVD of the TBCCs closely approaches the RCU bound at blocklength of 128.

This paper applies probabilistic amplitude shaping (PAS) to a cyclic redundancy check (CRC) aided trellis coded modulation (TCM) to achieve the short-blocklength random coding union (RCU) bound. In the transmitter, the equally likely message bits are first encoded by a distribution matcher to generate amplitude symbols with the desired distribution. The binary representations of the distribution matcher outputs are then encoded by a CRC code. Finally, the CRC-encoded bits are encoded and modulated by Ungerboeck’s TCM scheme, which consists of a systematic $\frac{{{k_0}}}{{{k_0} + 1}}$ tail-biting convolutional code and a mapping function that maps coded bits to channel signals with capacity-achieving distribution. This paper proves that, for the proposed transmitter, the CRC bits have uniform distribution and that the channel inputs have symmetric distribution. In the receiver, the serial list Viterbi decoding (S-LVD) is used to estimate the information bits. Simulation results show that, for the proposed CRC-TCM-PAS system with 87 input bits and 65-67 8-AM coded output symbols, the decoding performance under additive white Gaussian noise channel achieves the RCU bound with properly designed CRC and convolutional codes.

This paper presents a method for computing a finite-blocklength converse for the rate of fixed-length codes with feedback used on discrete memoryless channels (DMCs). The new converse is expressed in terms of a stochastic control problem whose solution can be efficiently computed using dynamic programming and Fourier methods. For channels such as the binary symmetric channel (BSC) and binary erasure channel (BEC), the accuracy of the proposed converse is similar to that of existing special-purpose converse bounds, but the new converse technique can be applied to arbitrary DMCs. We provide example applications of the new converse technique to the binary asymmetric channel (BAC) and the quantized amplitude-constrained AWGN channel.

In this paper, we are interested in the performance of a variable-length stop-feedback (VLSF) code with m optimal decoding times for the binary-input additive white Gaussian noise channel. We first develop tight approximations to the tail probability of length-n cumulative information density. Building on the work of Yavas et al., for a given information density threshold, we formulate the integer program of minimizing the upper bound on average blocklength over all decoding times subject to the average error probability, minimum gap and integer constraints. Eventually, minimization of locally optimal upper bounds over all thresholds yields the globally minimum upper bound and the above method is called the two-step minimization. Relaxing to allow positive real-valued decoding times activates the gap constraint. We develop gap-constrained sequential differential optimization (SDO) procedure to find the optimal, gap-constrained, real-valued decoding times. In the error regime of practical interest, Polyanskiy's scheme of stopping at zero does not help. In this region, the achievability bounds estimated by the two-step minimization and gap-constrained SDO show that Polyanskiy’s achievability bound for VLSF codes can be approached with a small number of decoding times.

This paper compares the accuracy and complexity of Raghavan and Baum’s Reliability Output Viterbi Algorithm (ROVA), Polyanskiy’s accumulated information density (AID), and Fricke and Hoeher’s lower complexity approximation of ROVA. It turns out that AID is far less accurate than ROVA in practice. This paper proposes codeword information density (CID), which modifies AID to improve its accuracy and leads to a lower-complexity implementation of ROVA. The paper includes an analytical expression for the random variable describing the correct decoding probability computed by ROVA and uses this expression to characterize how the probabilities of correct decoding, undetected error, and negative acknowledgement behave as a function of the selected threshold for reliable decoding. This paper examines both the complexity and the simulation time of ROVA, CID, AID, and the Fricke and Hoeher approximation to ROVA. This paper also derives an expression for the union bound on the frame error rate for zero-terminated trellis codes with punctured symbols and uses it to optimize the order of symbol transmission in an incremental retransmission scheme. This paper concludes by comparing the performance of an incremental retransmission scheme using ROVA as a stopping condition to one that uses a CRC as a stopping condition.

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.

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 thedistance-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.

In this paper, we consider variable-length coding over the memoryless binary asymmetric channel (BAC) with full noiseless feedback, including the binary symmetric channel (BSC) as a special case. In 2012, Naghshvar et al. introduced a coding scheme, which we refer to as the small-enough-difference (SED) coding scheme. For symmetric binary-input channels, the deterministic variable-length feedback (VLF) code constructed with the SED coding scheme asymptotically achieves both capacity and Burnashev’s optimal error exponent. Building on the work of Naghshvar et al., this paper extends the SED coding scheme to the BAC and develops a non-asymptotic VLF achievability bound that is shown to achieve both capacity and the optimal error exponent. For the specific case of the BSC, we develop an additional non-asymptotic VLF achievability bound using a two-phase analysis that leverages both a submartingale synthesis and a Markov chain time of first passage analysis. Numerical evaluations show that both new VLF achievability bounds outperform Polyanskiy’s achievability bound for variable-length stop-feedback codes.

Non-uniform message quantization techniques such as reconstruction-computation-quantization (RCQ) improve error-correction performance and decrease hardware complexity of low-density parity-check (LDPC) decoders that use a flooding schedule. Layered MinSum RCQ (L-msRCQ) enables message quantization to be utilized for layered decoders and irregular LDPC codes. We investigate field-programmable gate array (FPGA) implementations of L-msRCQ decoders. Three design methods for message quantization are presented, which we name the Lookup, Broadcast, and Dribble methods. The decoding performance and hardware complexity of these schemes are compared to a layered offset MinSum (OMS) decoder. Simulation results on a (16384, 8192) protograph-based raptor-like (PBRL) LDPC code show that a 4-bit L-msRCQ decoder using the Broadcast method can achieve a 0.03 dB improvement in error-correction performance while using 12% fewer registers than the OMS decoder. A Broadcast-based 3-bit L-msRCQ decoder uses 15% fewer lookup tables, 18% fewer registers, and 13% fewer routed nets than the OMS decoder, but results in a 0.09 dB loss in performance.

Traditional communication systems transmit a code-word only after all message bits are available at the transmitter. This paper joins Guo & Kostina and Lalitha et al. in developing approaches for causal encoding, where the transmitter may begin transmitting codeword symbols as soon as the first message bit arrives. Building on the posterior matching encoders of Horstein, Shayevitz & Feder, and Naghshvar et al., this paper extends our computationally efficient systematic encoder to progressively encode using only the message bits that are causally available. Systematic codes work well with posterior matching on a channel with feedback, and they provide an immediate benefit when causal encoding is employed instead of traditional encoding. Our algorithm captures additional gains in the interesting region where the transmission rate$\mu$is higher than the source rate$\lambda$at which message bits become available. In this region, we improve performance further through the transmission of additional, non-systematic symbols before a traditional encoder would have even begun transmission.

This paper proposes a finite-precision decoding method for low-density parity-check (LDPC) codes that features the three steps of Reconstruction, Computation, and Quantization (RCQ). Unlike Mutual-Information-Maximization Quantized Belief Propagation (MIM-QBP), RCQ can approximate either belief propagation or Min-Sum decoding. MIM-QBP decoders do not work well when the fraction of degree-2 variable nodes is large. However, sometimes a large fraction of degree-2 variable nodes is used to facilitate a fast encoding structure, as seen in the IEEE 802.11 standard and the DVB-S2 standard. In contrast to MIM-QBP, the proposed RCQ decoder may be applied to any off-the-shelf LDPC code, including those with a large fraction of degree-2 variable nodes. Simulations show that a 4-bit Min-Sum RCQ decoder delivers frame error rate (FER) performance within 0.1 dB of floating point belief propagation (BP) for the IEEE 802.11 standard LDPC code in the low SNR region. The RCQ decoder actually outperforms floating point BP and Min-Sum in the high SNR region were FER less than 10-5. This paper also introduces Hierarchical Dynamic Quantization (HDQ) to design the time-varying non-uniform quantizers required by RCQ decoders. HDQ is a low-complexity design technique that is slightly sub-optimal. Simulation results comparing HDQ and optimal quantization on the symmetric binary-input memoryless additive white Gaussian noise channel show a mutual information loss of less than 10-6bits, which is negligible in practice.

The new 5G communications standard increases data rates and supports low-latency communication that places constraints on the computational complexity of channel decoders. 5G low-density parity-check (LDPC) codes have the so-called protograph-based raptor-like (PBRL) structure which offers inherent rate-compatibility and excellent performance. Practical LDPC decoder implementations use message-passing decoding with finite precision, which becomes coarse as complexity is more severely constrained. Performance degrades as the precision becomes more coarse. Recently, the information bottleneck (IB) method was used to design mutual-information-maximizing lookup tables that replace conventional finite-precision node computations. The IB approach exchanges messages represented by integers with very small bit width. This paper extends the IB principle to the flexible class of PBRL LDPC codes as standardized in 5G. The extensions include puncturing and rate-compatible IB decoder design. As an example of the new approach, a 4-bit information bottleneck decoder is evaluated for PBRL LDPC codes over a typical range of rates. Frame error rate simulations show that the proposed scheme outperforms offset min-sum decoding algorithms and operates very close to double-precision sum-product belief propagation decoding.

Building on the work of Horstein, Shayevitz and Feder, and Naghshvar et al., this paper presents algorithms for low-complexity sequential transmission of a k-bit message over the binary symmetric channel (BSC) with full, noiseless feedback. To lower complexity, this paper shows that the initial k binary transmissions can be sent before any feedback is required and groups messages with equal posteriors to reduce the number of posterior updates from exponential in k to linear in k. Simulation results demonstrate that achievable rates for this full, noiseless feedback system approach capacity rapidly as a function of average blocklength, faster than known finite-blocklength lower bounds on achievable rate with noiseless active feedback and significantly faster than finite-blocklength lower bounds for a stop feedback system.

Cyclic redundancy check (CRC) codes combined with convolutional codes yield a powerful concatenated code that can be efficiently decoded using list decoding. To help design such systems, this paper presents an efficient algorithm for identifying the distance-spectrum-optimal (DSO) CRC polynomial for a given tail-biting convolutional code (TBCC) when the target undetected error rate (UER) is small. Lou et al. found that the DSO CRC design for a given zero-terminated convolutional code under low UER is equivalent to maximizing the undetected minimum distance (the minimum distance of the concatenated code). This paper applies the same principle to design the DSO CRC for a given TBCC under low target UER. Our algorithm is based on partitioning the tail-biting trellis into several disjoint sets of tail-biting paths that are closed under cyclic shifts. This paper shows that the tail-biting path in each set can be constructed by concatenating the irreducible error events (IEEs) and circularly shifting the resultant path. This motivates an efficient collection algorithm that aims at gathering IEEs, and a search algorithm that reconstructs the full list of error events with bounded distance of interest, which can be used to find the DSO CRC. Simulation results show that DSO CRCs can significantly outperform suboptimal CRCs in the low UER regime.

In this paper, we consider the problem of sequential transmission over the binary symmetric channel (BSC) with full, noiseless feedback. Naghshvar et al. proposed a one-phase encoding scheme, for which we refer to as the small-enough difference (SED) encoder, which can achieve capacity and Burnashev's optimal error exponent for symmetric binary-input channels. They also provided a non-asymptotic upper bound on the average blocklength, which implies an achievability bound on rates. However, their achievability bound is loose compared to the simulated performance of SED encoder, and even lies beneath Polyanskiy's achievability bound of a system limited to stop feedback. This paper significantly tightens the achievability bound by using a Markovian analysis that leverages both the submartingale and Markov properties of the transmitted message. Our new non-asymptotic lower bound on achievable rate lies above Polyanskiy's bound and is close to the actual performance of the SED encoder over the BSC.

Previously, dynamic-assignment Blahut-Arimoto (DAB) was used to find capacity-achieving probability mass functions (PMFs) for binomial channels and molecular channels. As it turns out, DAB can efficiently identify capacity-achieving PMFs for a wide variety of channels. This paper applies DAB to power-constrained (PC) additive white Gaussian Noise (AWGN) Channels and amplitude-constrained (AC) AWGN Channels.This paper modifies DAB to include a power constraint and finds low-cardinality PMFs that approach capacity on PC-AWGN Channels. While a continuous Gaussian PDF is well-known to be capacity-achieving on the PC-AWGN channel, DAB identifies low-cardinality PMFs within 0.01 bits of the mutual information provided by a Gaussian PDF. Recall the results of Ozarow and Wyner requiring a constellation cardinality of ⌈2C+1⌉ to approach capacity C to within the asymptotic shaping loss of 1.53 dB at high SNR. PMF’s found by DAB approach capacity with essentially no shaping loss with cardinality less than 2C+1.2. As expected, DAB’s numerical approach identifies PMFs with better mutual information vs. SNR performance than the analytical approaches to finite-support constellations examined by Wu and Verdu.This paper also uses DAB to find capacity-achieving PMFs with small cardinality support sets for AC-AWGN Channels. The resulting evolution of capacity-achieving PMFs as a function of SNR is consistent with the approximate cardinality transition points of Sharma and Shamai.

This paper uses convolutional codes (CCs) with distance-spectrum optimal (DSO) cyclic redundancy checks (CRCs) and the serial list Viterbi algorithm (S-LVA) to approach the random coding union (RCU) bound with low decoding complexity at the target FER. We show, for example, that a 64-state zero-terminated CC with a DSO CRC can achieve performance within 0.5 dB of the RCU bound for information blocklength k=64 at FER of 10-3. We also show that a tail-biting CC with a DSO CRC can achieve even better performance, within 0.05 dB of the RCU bound at FER of 10-4for a 256-state CC with k=64. This paper provides analysis of decoding complexity, which for S-LVA depends on the expected list size. We show that if the target FER is low enough, the expected list size approaches one so that the average complexity of S-LVA approaches that of standard soft Viterbi on the CC, i.e., with no list decoding. We also provide DSO CRCs for CCs with k=64 and rates of 1/2, 1/3, 1/6 and 1/12 for the 5G new radio control channel and compare their performance with polar codes.

This paper develops a paradigm for optimizing progressive reads for flash memory cells that maximize the conditional mutual information (MI) given previous reads and shows that some progressive reads provide substantially more MI than others. We study two flash storage techniques: 1) the common practice of independently encoding each bit of a cell into a separate codeword and 2) jointly encoding all the bits in the cell into the same codeword. We quantify the MI gap between joint and independent encoding and show that this gap becomes negligible when progressive reads are available. The paper provides LDPC simulations that confirm the MI analysis.

This paper provides a reduced-complexity approach to maximum likelihood (ML) decoding of cyclic codes. A cyclic code with generator polynomial gcyclic(x) may be considered a terminated convolutional code with a nominal rate of 1. The trellis termination redundancy lowers the rate from 1 to the actual rate of the cyclic code. The proposed decoder represents gcyclic(x) as the product of two polynomials, a convolutional code (CC) polynomial gcc(x) and a cyclic redundancy check (CRC) polynomial gcrc(x), i.e., gcyclic(x) = gcc(x)gcrc(x). This representation facilitates serial list Viterbi algorithm (S-LVA) decoding. Viterbi decoding is performed on the natural trellis for gcc(x), and gcrc(x) is used as a CRC to determine when the S-LVA should conclude. At typical target frame error rates, the expected list size of S-LVA is small, and the average decoding complexity is dominated by the trellis complexity of gcc(x) rather than gcyclic(x). Some high-rate binary Bose-Chaudhuri- Hocquenghem (BCH) examples show that the proposed use of S-LVA via factorization significantly lowers complexity as compared to using the minimum-complexity trellis representation of gcyclic(x) for soft ML decoding.

Let Xnbe a uniformly distributed n-dimensional binary vector, and Ynbe the result of passing Xnthrough a binary symmetric channel (BSC) with crossover probability α. A recent conjecture postulated by Courtade and Kumar states that I(f(Xn); Yn) ≤ 1 - H(α). Although the conjecture has been proved to be true in the dimension-free high noise regime by Samorodnitsky, here we present a calculus-based approach to show a dimension-dependent result by examining the second derivative of H(α) - H(f(Xn)|Yn) at α = 1/2. Along the way, we show that the dictator function is the most informative function in the high noise regime.

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.

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.

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.

This paper considers a channel coding paradigm that enables high throughput by using many variable-length codes in parallel, where each of the parallel codes has a short average blocklength. The inter-frame coding of Zeineddine and Mansour provides variable- length codes with incremental redundancy from a common pool of redundancy in a way that does not require feedback. A probability- based derivation of a generalized peeling decoder extends the results of Luby et al. to the inter-frame scenario. A new expression characterizes the probability that a variable-length decoder in the inter-frame system will fail. Additionally, the three causes for throughput loss as compared to the original feedback system are identified, yielding a new and far simpler design methodology for the right degree distribution of the inter-frame code. The inter-frame paradigm can apply to any communication channel, but this paper uses the additive white Gaussian noise channel to demonstrate the concepts.

Variable-length (VL) coding sends an initial codeword followed by subsequent transmissions of incremental redundancy (IR) sent when the decoder indicates through feedback that it has not yet identified a reliable codeword. VL coding is a staple of modern communication to handle fading, and recent theoretical analysis and applications have demonstrated its value on non-fading channels for applications that require short blocklengths. To maximize throughput in a VL setting, the length of each IR transmission should be optimized. Sequential differential optimization (SDO) computes transmission lengths that optimize throughput by minimizing average blocklength. SDO produces a family of solutions that each maximize throughput for a specified maximum number of transmissions. This paper considers the average number of feedback transmissions per message as an alternative metric for the cost of the feedback resource. A Lagrangian approach provides a new SDO solution that jointly minimizes both the average blocklength and the average number of feedback transmissions associated with a message. The mapping of real-valued SDO solutions to the necessarily integer transmission lengths is also addressed.

This paper analyzes the serial list Viterbi algorithm (S-LVA) used in conjunction with optimal CRC codes that minimize probability of undetected error by maximizing the minimum distance between convolutional codewords that pass the CRC check, following Lou et al. In particular, the paper identifies such optimal CRC codes for the 3GPP standard convolutional code (561,753). As SNR varies and the maximum list size L ranges from one to its maximum, this paper uses bounds, approximations, and simulation to characterize decoding complexity and the trade-off between erasure probability and undetected error probability. The complexity of S-LVA is captured by the expected value of the number of decoding attempts required before a CRC check passes or L codewords have been examined. For S-LVA with a degree-m CRC and maximum possible L, which is the cardinality of the set of all possible convolutional codewords, the expected value of the number of decoding attempts converges to one as SNR increases and to 2m(1 - ϵ), for a small ϵ > 0, as SNR decreases. For S-LVA with the maximum possible L, the erasure probability is zero. As L decreases from this maximum, the erasure probability increases and the TIE probability decreases to that of L = 1, for which TIE probability is well approximated by a nearest-neighbor bound.

As sensing and instrumentation play an increasingly important role in systems controlled over wired and wireless networks, the need to better understand delay-sensitive communication becomes a prime issue. Along these lines, this article studies the operation of data links that employ incremental redundancy as a practical means to protect information from the effects of unreliable channels. Specifically, this work extends a powerful methodology termed sequential differential optimization to choose near-optimal block sizes for hybrid ARQ over erasure channels. Furthermore, results show that the impact of the coding strategy adopted and the propensity of the channel to erase symbols naturally decouple when analyzing throughput. Overall, block size selection is motivated by normal approximations on the probability of decoding success at every stage of the incremental transmission process. This novel perspective, which rigorously bridges hybrid ARQ and coding, offers a pragmatic means to select code rates and blocklengths for incremental redundancy.

A rate-compatible (RC) code first transmits a set of symbols corresponding to the highest rate. These symbols form the highest-rate code (HRC). If requested by the receiver, the transmitter subsequently sends symbols that lower the rate of the code. Additional symbols are sent until the decoder decodes to a codeword or all symbols of the RC code are exhausted. Consider linear, RC low-density parity-check (LDPC) codes constructed using extending variable nodes of degree 1. That is, every symbol of incremental redundancy (IR) is a linear combination only of symbols of the HRC. We study the convergence of such codes under iterative decoding. We show that the convergence criterion considered after each iteration need only check whether the HRC variable nodes have converged to a codeword. Specifically, there is no need to consider whether the parity checks that generate the IR symbols are satisfied. We substantiate these claims with simulation results of protograph-based raptor-like LDPC (PBRL) codes, which are a family of protograph RC-LDPC codes with the extending structure under consideration. Furthermore, we demonstrate using examples that this extending structure for protograph RC codes is not very far from the optimal extension for a protograph RC code by providing examples of iterative decoding thresholds for PBRL protographs and protographs extended using the optimal degrees for incremental variable nodes.

Protograph-based Raptor-like low-density parity-check codes (PBRL codes) are a recently proposed family of easily encodable and decodable rate-compatible LDPC (RC-LDPC) codes. These codes have an excellent iterative decoding threshold and performance across all design rates. 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 RC code family at various design rates. In this work, we propose a design method to obtain better quasi-cyclic (QC) RC-LDPC codes with PBRL structure for short block-lengths (of a few hundred bits). We achieve this by maximizing an upper bound on the minimum distance of any QC-LDPC code that can be obtained from the protograph of a PBRL ensemble. The obtained codes outperform the original PBRL codes at short block-lengths by significantly improving the error floor behavior at all design rates. Furthermore, we identify a reduction in complexity of the design procedure, facilitated by the general structure of a PBRL ensemble.

Variable-length codes with incremental redundancy controlled by feedback allow a system to approach capacity with short average blocklengths and thus relatively low-complexity decoders. This paper shows how to use those same variable-length codes with incremental redundancy to approach capacity without feedback. The general principle is to provide a common pool of redundancy that can be accessed by exactly the variable-length codes that need it. We provide example implementations using both regular and irregular low-density generator matrix (LDGM) codes to provide this common pool of redundancy, utilizing the inter-frame coding approach that Zeineddine and Mansour used to combat rate variation due to fading in broadcast transmissions. Obtaining the LDGM degree distributions requires a new design methodology involving differential evolution for a generalized peeling decoder. Monte-Carlo simulations using a 2dB binary-input additive white Gaussian noise channel confirm the feasibility of this new approach. For a frame error rate of 10-3, the irregular LDGM code achieves 96% of the throughput of the corresponding feedback system.

This paper uses a case study of a tail-biting convolutional code (with successful decoding indicated by the reliability output Viterbi algorithm) to present an information density approach for analyzing and optimizing the throughput of systems using incremental redundancy controlled by feedback. Polyan-skiy's normal approximation combined with a linear model for the information gap of a rate-compatible code family provides a simple and accurate characterization of the behavior of feedback systems employing practical codes, such as convolutional or low-density parity-check codes. Especially for short message lengths on the order of k <; 50 message bits, the newly proposed model is more accurate than Vakilinia's model in which the rate of first successful decoding has a Gaussian probability density function.

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.

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.

The read channel of a Flash memory cell degrades after repetitive program and erase (P/E) operations. This degradation is often modeled as a function of the number of P/E cycles. In contrast, this paper models the degradation as a function of the cumulative effect of the charge written and erased from the cell. Based on this modeling approach, this paper dynamically allocates voltage using lower voltage write thresholds at the beginning of the device lifetime and increasing the thresholds as needed to maintain the mutual information of the read channel in the face of degradation. This paper introduces the technique in an idealized setting and then removes ideal assumptions about channel knowledge and available voltage resolution to conclude with a practical scheme with performance close to that of the idealized setting.

We propose an approach where each user independently seeks to minimize the amount of time that they occupy the channel. Essentially, we seek to minimize the number of transmitted symbols required to communicate a packet assuming variable-length coding with feedback. Users send a pilot sequence to estimate the channel quality and decide whether to proceed with a transmission or wait for the next opportunity. Thus a user may choose to leave the channel even though it has already gained access, in order to increase the network throughput and also save its own energy resources. This paper optimizes the number of pilots and the channel identification threshold to minimize the total number of transmitted symbols (including pilots) required to communicate the packet. We prove a sufficient condition for the optimal pilot length and the channel identification threshold. This optimal parameter pair is solved numerically and the reduction in channel occupancy is shown for various channel settings.

Current generation Flash devices experience significant read-channel degradation from damage to the oxide layer during program and erase operations. Information about the read-channel degradation drives advanced signal processing methods in Flash to mitigate its effect. In this context, channel estimation must be ongoing since channel degradation evolves over time and is a function of the number of program/erase (P/E) cycles. This paper proposes a framework for on-line model-based channel estimation using limited channel measurements (reads). This paper uses a channel model characterizing degradation as a function of retention time and the amount of charge programmed and erased. For channel histogram measurements, equal-probability (equal-height) bin placement yields a good approximation to the original distribution using only ten bins (i.e. nine reads). With the channel model and binning strategy in place, this paper explores candidate numerical least squares channel estimation algorithms and ultimately demonstrates the effectiveness of the Levenberg-Marquardt algorithm, which provides both speed and accuracy, in an algorithm for voltage allocation.

We consider the problem of constructing (3,L) quasi-cyclic low-density parity-check (LDPC) codes from complete protographs. A complete protograph is a small bipartite graph with two disjoint vertex sets such that every vertex in the variable-node set is connected to every vertex in the check-node set by a unique edge. This paper analyzes the required lifting factor for achieving girths of six or eight in the resulting quasi-cyclic codes with constraints on lifting. The required lifting factors provide lower bounds on the block-length of such codes.

This paper uses an extension of Reciprocal Channel Approximation (RCA) to accurately and efficiently predict the frame error rate (FER) performance of polar codes by analyzing the probability density function (p.d.f) of log likelihood ratios (LLR) associated with information bits. A feedback scheme uses the RCA to predict the p.d.f of LLRs in conjunction with a repetition coding system to decrease the blocklength required for a target FER by a factor of 16. Using a rate-0.5 128-bit polar code as the initially transmitted code, the FER of the system with feedback is obtained by theoretical analysis and verified by simulation. Including the additional incremental transmissions the average blocklength for the system with feedback is 137.55 bits and the rate is 0.4653. Without feedback, a polar code with blocklength 2048 is required to achieve a comparable FER at a comparable rate. Intuitively, feedback allows the polar code to use fewer frozen bits in the initial transmission and then uses repetition codes to provide the needed reliability to resolve unreliable unfrozen bits identified by feedback.

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 block-lengths. 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.

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.

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.

This paper considers finite-blocklength achievability for rate-compatible codes. For a fixed number of messages, random coding analysis determines a sequence of achievable error probabilities for a sequence of blocklengths. However, traditional random coding achievability draws each code independently so that it does not show that a family of rate-compatible codes achieves that same sequence of error probabilities. Using random code extension, this paper shows achievable error probabilities for rate-compatible channel codes with finite blocklengths. This paper also shows that for a class of input-invariant channels, the rate-compatible constraint does not affect the achievability bounds on error rates when a threshold decoder is used.

This paper studies variable-length coding with noise-less feedback for discrete memoryless channels. Yamamoto and Itoh's two-phase scheme achieves the optimal error-exponent, but due to the block-coding nature it is not optimal in the expansion of the message size logM. Polyanskiy et al. showed that with feedback, the back-off from capacity is logarithmic in the expected latency ℓ. The O(log ℓ) back-off is achieved by using an incremental redundancy (IR) scheme that only utilizes feedback to determine the stopping time. However, the achievable error-exponent of the IR scheme is not optimal. This paper shows that a two-phase coding scheme where each phase uses an IR scheme achieves the optimal error-exponent while maintaining an expansion on the message size that yields the O(log ℓ) back-off.

Following Poulliat et al.'s design of (2, dc) nonbinary LDPC (NB-LDPC) codes, this paper designs high-rate irregular NB-LDPC codes by addressing the problem of minimum symbol distance. The design procedure first identifies all stopping sets up to weight five in an LDPC code and enumerates them via a message passing algorithm. For each identified stopping set, careful labeling forces its corresponding parity-check sub-matrix to be full rank, thereby preventing the stopping set from being a sub-code and ensuring a minimum distance of at least six symbols. Simulation results for codes designed through this procedure show a significant improvement in the error-floor region over randomized labeling.

One advantage of feedback in a point-to-point memoryless channel is the reduction of the average blocklength required to approach capacity. This paper presents a communication system with feedback that uses carefully designed non-binary LDPC (NB-LDPC) codes and incremental transmissions to achieve 92–94% of the idealized throughput of rate-compatible sphere-packing with maximum-likelihood decoding (RCSP-ML) for average blocklengths of 150–450 bits. The system uses active feedback by carefully selecting each bit of additional incremental information to improve the reliability of the least reliable variable node. The system uses post processing in the decoder to further improve performance. The average blocklengths of 150–450 bits are small enough that feedback provides a throughput advantage but also large enough that overhead that might be associated with transmitter confirmation is more easily tolerated.

One advantage of incremental transmissions with feedback in point-to-point memoryless channels is a reduction in average blocklength required to approach capacity. This paper optimizes the size of each incremental transmission for non-binary (NB) LDPC codes to maximize throughput in VLFT and two-phase VLF settings. The optimization problem uses an approximation based on the inverse-Gaussian p.d.f. of the blocklength required for successful decoding. By using the optimized incremental transmission lengths (with an average blocklength of less than 500 bits), NB-LDPC codes for VLFT setting limited to 5 transmissions achieve a throughput greater than 96% of that obtained by an unlimited-transmission VLFT scheme with the same average blocklength. With a similar average blocklength, a two-phase VLF system limited to five transmissions (with optimized lengths) using the binary image of NB-LDPC codes achieves greater than 90% of the capacity of binary-input AWGN channel with SNR=2 dB. Two-phase VLF does not match the throughput of VLFT, but it is more practical than VLFT because it does not assume noiseless transmitter confirmation.

Multiple reads of the same Flash memory cell with distinct word-line voltages provide enhanced precision for LDPC decoding. In this paper, the word-line voltages are optimized by maximizing the mutual information (MI) of the quantized channel. The enhanced precision from a few additional reads allows frame error rate (FER) performance to approach that of full-precision soft information and enables an LDPC code to significantly outperform a BCH code. A constant-ratio constraint provides a significant simplification in the optimization with no noticeable loss in performance. For a well-designed LDPC code, the quantization that maximizes the mutual information also minimizes the FER in our simulations. However, for an example LDPC code with a high error floor caused by small absorbing sets, the MMI quantization does not provide the lowest frame error rate. The best quantization in this case introduces more erasures than would be optimal for the channel MI in order to mitigate the absorbing sets of the poorly designed code. The paper also identifies a trade-off in LDPC code design when decoding is performed with multiple precision levels; the best code at one level of precision will typically not be the best code at a different level of precision.

We present extensions to Raghavan and Baum's reliability-output Viterbi algorithm (ROVA) to accommodate tail-biting convolutional codes. These tail-biting reliability-output algorithms compute the exact word-error probability of the decoded codeword after first calculating the posterior probability of the decoded tail-biting codeword's starting state. One approach employs a state-estimation algorithm that selects the maximum a posteriori state based on the posterior distribution of the starting states. Another approach is an approximation to the exact tail-biting ROVA that estimates the word-error probability. A comparison of the computational complexity of each approach is discussed in detail. The presented reliability-output algorithms apply to both feedforward and feedback tail-biting convolutional encoders. These tail-biting reliability-output algorithms are suitable for use in reliability-based retransmission schemes with short blocklengths, in which terminated convolutional codes would introduce rate loss.

Consider a connected network of n nodes that all wish to recover k desired packets. Each node begins with a subset of the desired packets and exchanges coded packets with its neighbors. This paper provides necessary and sufficient conditions that characterize the set of all transmission strategies that permit every node to ultimately learn (recover) all k packets. When the network satisfies certain regularity conditions and packets are randomly distributed, this paper provides tight concentration results on the number of transmissions required to achieve universal recovery. For the case of a fully connected network, a polynomial-time algorithm for computing an optimal transmission strategy is derived. An application to secrecy generation is discussed.

Theoretical analysis has long indicated that feedback improves the error exponent but not the capacity of single user memoryless channels. Recently Polyanskiy et al. studied the benefit of variable-length feedback with termination (VLFT) codes in the non-asymptotic regime. In that work, achievability is based on an infinite-length random code and decoding is attempted at every symbol. The coding rate backoff from capacity due to channel dispersion is greatly reduced with feedback, allowing capacity to be approached with surprisingly small expected latency. This paper is concerned with VLFT codes based on finite-length codes and decoding attempts only at certain specified decoding times. Note that with an underlying finite-length code, the transmitter may have to repeat code symbols. The penalties of using a finite block-length N and a sequence of specified decoding times are studied. This paper shows that properly scaling N with the expected latency can achieve the same performance up to second order terms as with N =∞. The penalty introduced by limiting the decoding is a constant term and hence the performance approaches capacity as expected latency increases as long as the interval between periodic decoding times grows sub-linearly with the expected latency.

This paper presents a reliability-based decoding scheme for variable-length coding with feedback and demonstrates via simulation that it can achieve higher rates than Polyanskiy et al.'s random coding lower bound for variable-length feedback (VLF) coding on both the BSC and AWGN channel. The proposed scheme uses the reliability output Viterbi algorithm (ROVA) to compute the word error probability after each decoding attempt, which is compared against a target error threshold and used as a stopping criterion to terminate transmission. The only feedback required is a single bit for each decoding attempt, informing the transmitter whether the ROVA-computed word-error probability is sufficiently low. Furthermore, the ROVA determines whether transmission/decoding may be terminated without the need for a rate-reducing CRC.

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.

Consider a memoryless degraded broadcast channel (DBC) in which the channel output is a single-letter function of the channel input and the channel noise. As examples, for the Gaussian broadcast channel (BC), this single-letter function is real scalar addition and for the binary-symmetric BC, this single-letter function is modulo-two addition. This paper identifies several classes of discrete memoryless DBCs for which a relatively simple encoding scheme, which we call natural encoding, achieves capacity. Natural encoding (NE) combines symbols from independent codebooks (one for each receiver) using the same single-letter function that adds distortion to the channel. The alphabet size of each NE codebook is bounded by that of the channel input. This paper also defines the input-symmetric DBC, introduces permutation encoding for the input-symmetric DBC, and proves its optimality. Because it is a special case of permutation encoding, NE is capacity achieving for the two-receiver group-operation DBC. Combining the broadcast Z channel and group-operation DBC results yields a proof that NE is also optimal for the discrete multiplication DBC. Along the way, the paper also provides explicit parametric expressions for the two-receiver binary-symmetric DBC and broadcast Z channel.

This paper presents a new construction of punctured-node protograph-based Raptor-like (PN-PBRL) codes that is suitable for long-blocklength applications. As with the Raptor codes, additional parity bits can be easily produced by exclusive-OR operations on the precoded bits, providing extensive rate compatibility. The new construction provides low iterative decoding thresholds that are within 0.45 dB of the capacity for all code rates studied, and the construction is suitable for long blocklengths. Comparing at the same information block size of k = 16368 bits, the PN-PBRL codes are as good as the best known AR4JA codes in the waterfall region. The PN-PBRL codes also perform comparably to DVB-S2 LDPC codes even though the DVBi-S2 codes have longer blocklength and outer BCH codes.

Recent work by Polyanskiy et al. and Chen et al. has excited new interest in using feedback to approach capacity with low latency. Polyanskiy showed that feedback identifying the first symbol at which decoding is successful allows capacity to be approached with surprisingly low latency. This paper uses Chen's rate-compatible sphere-packing (RCSP) analysis to study what happens when symbols must be transmitted in packets, as with a traditional hybrid ARQ system, and limited to relatively few (six or fewer) incremental transmissions. Numerical optimizations find the series of progressively growing cumulative block lengths that enable RCSP to approach capacity with the minimum possible latency. RCSP analysis shows that five incremental transmissions are sufficient to achieve 92% of capacity with an average block length of fewer than 101 symbols on the AWGN channel with SNR of 2.0 dB. The RCSP analysis provides a decoding error trajectory that specifies the decoding error rate for each cumulative block length. Though RCSP is an idealization, an example tail-biting convolutional code matches the RCSP decoding error trajectory and achieves 91% of capacity with an average block length of 102 symbols on the AWGN channel with SNR of 2.0 dB. We also show how RCSP analysis can be used in cases where packets have deadlines associated with them (leading to an outage probability).

Recent results by Chen et al. and Polyanskiy et al. explore using feedback to approach capacity with short blocklengths. This paper explores Chernoff bounding techniques to extend the rate-compatible sphere-packing (RCSP) analysis proposed by Chen et al. to scenarios involving numerous retransmissions and different step sizes in each incremental retransmission. Williamson et al. employ exact RCSP computations for up to six transmissions. However, exact RCSP computation with more than six retransmissions becomes unwieldy because of joint error probabilities involving numerous chi-squared distributions. This paper explores Chernoff approaches for upper and lower bounds on the error probability to provide support for computations involving more than six transmissions. We present two versions of upper and lower bounds on the error probability for the two-transmission case. One of the versions is extended to the general case of m transmissions where m ≥ 1. Computing the bounds for general m requires minimization of exponential functions with the auxiliary parameters. The numerical results, however, show that weakening the bounds by considering marginal probabilities and the case of two transmissions is already tight. These bounds also provide good estimates of the expected throughput and expected latency, which are useful for optimization purposes.

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.

This paper presents a new class of rate-compatible LDPC codes, protograph-based Raptor-like (PBRL) codes. The proposed PBRL codes are jointly decodable with an iterative belief propagation decoder. As with Raptor codes, additional parity bits can be easily produced by exclusive-or operations on the precoded bits, providing extensive rate compatibility. This paper provides a design procedure that optimizes this class of rate- compatible LDPC codes. The new PBRL codes outperform 3GPP rate-compatible turbo codes with the same short blocklength at high SNR and show no sign of an error floor at the FER region of 10-7.

This paper explores protograph-based and ACE-based methods for constructing q-ary low-density parity-check (LDPC) matrices. The ACE approach maximizes approximate cycle extrinsic message degree, explicitly avoiding small q-ary stopping sets and implicitly avoiding small absorbing sets. In addition to ACE, this paper applies linear-dependent-set maximization (LDSM) to the binary image of the q-ary LDPC matrix. Performance is studied for binary and q-ary instances of erasure channels and additive white Gaussian noise channels. The combination of the ACE approach and LDSM provides dramatic error floor improvement for the binary erasure channel and both binary and q-ary AWGN channels.

High-capacity NAND flash memory can achieve high density storage by using multi-level cells (MLC) to store more than one bit per cell. Although this larger storage capacity is certainly beneficial, the increased density also increases the raw bit error rate (BER), making powerful error correction coding necessary. Traditional flash memories employ simple algebraic codes, such as BCH codes, that can correct a fixed, specified number of errors. This paper investigates the application of low-density parity-check (LDPC) codes which are well known for their ability to approach capacity in the AWGN channel. We obtain soft information for the LDPC decoder by performing multiple cell reads with distinct word-line voltages. The values of the word-line voltages (also called reference voltages) are optimized by maximizing the mutual information between the input and output of the multiple-read channel. Our results show that using this soft information in the LDPC decoder provides a significant benefit and enables us to outperform BCH codes over a range of block error rates.

Theoretical analysis has long indicated that feedback improves the error exponent but not the capacity of memoryless Gaussian channels. Recently, Chen et al. demonstrated that an incremental redundancy scheme can use noiseless feedback to help short convolutional codes deliver the bit-error-rate performance of a long blocklength turbo code, but with much lower latency. Such a latency improvement is suggested by the error-exponent analysis, but there is no theoretical work that estimates how much latency improvement is possible with feedback for practical blocklengths and rates. This paper provides a code-independent analysis that quantifies the latency benefits possible by using modified incremental redundancy with feedback (MIRF). A sphere-packing analysis yields the throughput vs. latency performance of both a baseline ACK/NACK scheme and MIRF. The sphere-packing analysis matches well with simulations using turbo and convolutional codes, showing that the analysis has a practical predictive value.

Regular LDPC codes tend to have better error-floor behavior than irregular LDPC codes. However, for moderate block lengths and high rates, the error floor remains a concern even for regular LDPC codes. This is especially the case for applications such as memory media that require very low frame error rates (FERs). This paper focuses on a class of regular LDPC codes: separable, circulant-based (SCB) codes. For a specified circulant matrix, SCB codes all share a common mother matrix and include array-based LDPC codes as well as many common quasi-cyclic codes. SCB codes retain standard properties of quasi-cyclic LDPC codes such as girth, code structure, and compatibility with existing high-throughput hardware implementations. This paper introduces a cycle consistency matrix (CCM) for each possible absorbing set in an SCB LDPC code. For an absorbing set to be present in an SCB LDPC code, the associated CCM must not be full column-rank. Using this novel observation, a new code construction approach selects rows and columns from the SCB mother matrix to systematically eliminate dominant absorbing sets by forcing the associated CCMs to be full column-rank. Simulation results demonstrate that the new codes have steeper error-floor slopes and provide at least one order of magnitude of improvement in the low FER region. Identifying absorbing-set-spectrum equivalence classes within the family of SCB codes with a specified circulant matrix significantly reduces the search space of possible code matrices.

In this paper, we consider a class of multiterminal source coding problems, each subject to distortion constraints computed using a specific, entropy-based, distortion measure. We provide the achievable rate distortion region for two cases and, in so doing, we demonstrate a relationship between the lossy multiterminal source coding problems with our specific distortion measure and (1) the canonical Slepian-Wolf lossless distributed source coding network, and (2) the Ahlswede-Körner-Wyner source coding with side information problem in which only one of the sources is recovered losslessly.

This paper focuses on controlling the absorbing set spectrum for a class of regular LDPC codes known as separable, circulant-based (SCB) codes. For a specified circulant matrix, SCB codes all share a common mother matrix, examples of which are array-based LDPC codes and many common quasi-cyclic codes. SCB codes retain the standard properties of quasi-cyclic LDPC codes such as girth, code structure, and compatibility with efficient decoder implementations. In this paper, we define a cycle consistency matrix (CCM) for each absorbing set of interest in an SCB LDPC code. For an absorbing set to be present in an SCB LDPC code, the associated CCM must not be full column-rank. Our approach selects rows and columns from the SCB mother matrix to systematically eliminate dominant absorbing sets by forcing the associated CCMs to be full column-rank. We use the CCM approach to select rows from the SCB mother matrix to design SCB codes of column weight 5 that avoid all low-weight absorbing sets (4; 8), (5; 9), and (6; 8). Simulation results demonstrate that the newly designed code has a steeper error-floor slope and provides at least one order of magnitude of improvement in the low error rate region as compared to an elementary array-based code.

For a block-fading channel, this paper optimizes the allocation of redundancy between packet-level erasure coding (which provides additional packets to compensate for packet loss) and physical layer channel coding (which lowers the probability of packet loss). After some manipulation, standard optimization techniques determine the trade-off between the amount of packet-level erasure coding and physical-layer channel coding that minimizes the transmit power required to provide reliable communication. Our results indicate that the optimal combination of packet-level erasure coding and physical-layer coding provides a significant benefit over pure physical-layer coding when no form of channel diversity is present within a packet transmission. However, the benefit of including packet-level erasure coding diminishes as more diversity becomes available within a packet transmission. Even with no diversity within a packet transmission, this paper shows that as the total redundancy becomes large the optimal redundancy for packet-level erasure coding reaches a limit while the optimal redundancy for physical-layer coding continues to increase. Hence providing limitless redundancy at the packet-level with rateless codes such as fountain codes is not the best use of limitless redundancy for block-fading channels.

Low-Density Parity-Check (LDPC) codes are usually decoded by running an iterative belief-propagation (BP), or message-passing, algorithm over the factor graph of the code. The traditional message-passing scheduling, called flooding, consists of updating all the variable nodes in the graph, using the same pre-update information, followed by updating all the check nodes of the graph, again, using the same pre-update information. Recently, several studies show that sequential scheduling, in which messages are generated using the latest available information, significantly improves the convergence speed in terms of number of iterations. Sequential scheduling introduces the problem of finding the best sequence of message updates. We propose Informed Dynamic Scheduling (IDS) strategies that select the message-passing schedule according to the observed rate of change of the messages. In general, IDS strategies require computation to select the message to update but converge in fewer message updates because they focus on the part of the graph that has not converged. Moreover, IDS yields a lower error-rate performance than either flooding or sequential scheduling because IDS strategies overcome traditional trapping-set errors. This paper presents IDS strategies that address several issues including performance for short-blocklength codes, complexity, and implementability.

Rateless coding ensures reliability by providing ever-increasing redundancy, traditionally at the packet level (i.e. the application layer) through erasure coding. This paper explores whether additional redundancy for wireless channels is most helpful at the packet level through erasure coding or at the physical layer through lower-rate channel coding. This cross-layer trade-off is explored in a traditional wireless setting where the communication of a message consisting of a fixed number of packets takes place over a Rayleigh fading channel. The examined scenarios include both a single receiver and multiple cooperating receivers allowing the results to be extended to situations where selection diversity is available in the system. For several interesting scenarios, this paper determines the optimal trade-off between the amount of packet-level erasure coding and physical-layer channel coding required to provide reliable communication over the widest range of operating SNR's. Our results indicate that packet-level erasure coding can provide a significant benefit when no other form of diversity is available. In many cases, the amount of redundancy that should be allocated to such erasure coding is nearly constant, and further redundancy (i.e. any rateless coding) should be applied to the physical layer.

Certain degraded broadcast channels (DBCs) have the property that the boundary of the capacity region can be achieved by an encoder that combines independent codebooks (one for each receiver) using the same single-letter function that adds distortion to the channel. We call this the natural encoder for the DBC. Natural encoders are known to achieve the capacity region boundary of the broadcast Gaussian channel, and the broadcast binary-symmetric channel. Recently, they have also been shown to achieve the capacity region of the broadcast Z channel. This paper shows that natural encoding achieves the capacity region boundary for discrete multiplicative DBCs. The optimality of the natural encoder also leads to a relatively simple expression for the capacity region for discrete multiplicative DBCs.

This paper describes and analyzes low-density parity-check code families that support variety of different rates while maintaining the same fundamental decoder architecture. Such families facilitate the decoding hardware design and implementation for applications that require communication at different rates, for example to adapt to changing channel conditions. Combining rows of the lowest-rate parity-check matrix produces the parity-check matrices for higher rates. An important advantage of this approach is that all effective code rates have the same blocklength. This approach is compatible with well known techniques that allow low-complexity encoding and parallel decoding of these LDPC codes. This technique also allows the design of programmable analog LDPC decoders. The proposed design method maintains good graphical properties and hence low error floors for all rates.

The design of LDPC decoders with low complexity, high throughput, and good performance is a critical task. A well-known strategy is to design structured codes such as quasi- cyclic LDPC (QC-LDPC) that allow partially-parallel decoders. Sequential schedules, such as Layered Belief-Propagation (LBP), converge faster than the traditional flooding schedule while allowing parallel decoding of QC-LDPC codes. In this paper, we propose a novel low-complexity sequential schedule called Zigzag LBP (Z-LBP). Current LBP schedules do not allow partially- parallel architectures in the regime of high-rate codes with small- to-medium blocklengths. Our proposed algorithm can still be implemented in a partially-parallel manner in this regime. Z-LBP provides the same benefits as LBP including faster convergence speed and lower frame error rates than flooding.

Parallel concatenated trellis coded modulation (PC- TCM) has been traditionally designed using parallel concatenated convolutional codes with a bits-to-symbol mapper. However, this paper shows that for higher-order modulations using linear codes is too restrictive. Parallel Concatenated Nonlinear Trellis Coded Modulation (PC-NLTCM) that directly assigns constellation points as output-labels to the branches of the trellis can outperform PC-TCM. Simulation results are shown for a 2 bits/s/Hz 16-state nonlinear turbo code with 8PSK. This code is less than 0.43 dB away from the Shannon limit at a BER = 10 5 with an interleaver length of 10000 bits, and outperforms previous published linear turbo code by around 0.2 dB. This paper also provides an extension of Benedetto's uniform interleaver analysis for nonlinear constituent codes, which accurately predicts the BER of the PC-NLTCM at high SNR.

This paper presents serially concatenated trellis coded modulations (SCTCMs) that perform consistently close to the available mutual information for periodic erasure channel (PEC), periodic fading channel (PFC) and the 2 times 2 compound matrix channel. We use both the maximum-likelihood decoding criteria and iterative decoding criteria to design universal SCTCMs for the PEC and the PFC. For the space-time channel, by demultiplexing the symbols across the antennas, the proposed universal SCTCMs for the period-2 PFC deliver consistent performance over the eigenvalue skew of the matrix channel. Within the family of channels having the same eigenvalue skew, a time-varying linear transformation (TVLT) is used to mitigate the performance variation over different eigenvectors. The proposed space-time SCTCMs of 1.0, 2.0 and 3.0 bits per transmission require excess mutual information in the ranges 0.11-0.15, 0.23- 0.26 and 0.35-0.53 bits per antenna, respectively. Because of their consistent performance over all channels, the proposed codes will have good frame-error-rate (FER) performance over any quasi-static fading distribution. In particular, the codes provide competitive FER performance in quasi-static Rayleigh fading.

This paper provides an explicit expression for the capacity region of the two-user broadcast Z channel and proves that the optimal boundary can be achieved by independent encoding of each user. Specifically, the information messages corresponding to each user are encoded independently and the OR of these two encoded streams is transmitted. Nonlinear turbo codes that provide a controlled distribution of ones and zeros are used to demonstrate a low-complexity scheme that operates close to the optimal boundary.

This paper presents a design criteria for arbitrarily low-rate parallel concatenated convolutional codes (PCCCs). The purpose of this work is to find a family of turbo codes that work as close to the ultimate low-rate Shannon limit Eb/Nosime -1.59 dB as possible, given a certain constraint in the number of states of the constituent trellis codes and in the interleaver-length. We propose an optimization criteria and reduce the turbo-design problem to the design of block codes for the assignment of output sequences to the trellis branches of the constituent encoders. We show that BCH codes concatenated with repetition codes are optimal for labeling. Moreover, we show that for a fixed number of trellis states these codes achieve arbitrarily low rates, and hence arbitrarily low SNRs, with practically the same performance in terms of Eb/No. Simulation results are shown for 8-state and 16-state turbo codes with rates as low as 1/505, which with an interleaver-length of 8192 provide a BER sime 10-5at an SNR sime -27.6 dB (Eb/Nosime -0.55 dB), around 1 dB away from the ultimate low-rate Shannon limit.

Low-density parity-check (LDPC) codes are usually decoded by running an iterative belief-propagation, or message-passing, algorithm over the factor graph of the code. The traditional message-passing schedule consists of updating all the variable nodes in the graph, using the same pre-update information, followed by updating all the check nodes of the graph, again, using the same pre-update information. Recently several studies show that sequential scheduling, in which messages are generated using the latest available information, significantly improves the convergence speed in terms of number of iterations. Sequential scheduling raises the problem of finding the best sequence of message updates. This paper presents practical scheduling strategies that use the value of the messages in the graph to find the next message to be updated. Simulation results show that these informed update sequences require significantly fewer iterations than standard sequential schedules. Furthermore, the paper shows that informed scheduling solves some standard trapping set errors. Therefore, it also outperforms traditional scheduling for a large numbers of iterations. Complexity and implementability issues are also addressed.

Root and Varaiya proved the existence of a code that can communicate reliably over any linear Gaussian channel for which the channel mutual information level exceeds the transmitted rate. This paper provides several examples of scalar (single-input single-output) fading channels and shows that on these channels the performance of low-density parity-check (LDPC) codes lies in close proximity to the performance limits identified by Root and Varaiya. Specifically, we consider periodic fading channels and partial-band jamming (PBJ) channels. A special case of periodic fading is the variation of signal-to-noise ratio across orthogonal frequency division modulation subchannels. The robustness of LDPC codes to periodic fading and PBJ across parameterizations of these different channels is demonstrated through the consistency of the required mutual information to provide a specified bit error rate. For the periodic fading case, the Gaussian approximation to density evolution has been adapted such that asymptotic threshold measures can be compared to simulated code performance in various periodic fading scenarios

Based on random codes and typical set decoding, an alternative proof of Root and Varaiya's compound channel coding theorem for linear Gaussian channels is presented. The performance limit of codes with finite block length under a compound channel is studied through error bounds and simulation. Although the theorem promises uniform convergence of the probability of error as the block length approaches infinity, with short block lengths the performance can differ considerably for individual channels. Simulation results show that universal performance can be a practical goal as the block lengths become large.

Though it promises high bandwidths, the optical medium is not popular in local area networks. This is because current optical networks do not offer the ease of use and setup that an uncoordinated multiple access network such as Ethernet offers. By careful design and implementation of high speed channel coding architectures, we show that it is possible for optical networks to exhibit these desirable properties while maintaining high optical transmission rates. This paper presents an interleaver-division multiple access (IDMA) architecture implemented with a rate 1/20, 64-state Viterbi decoder and a word-based interleaver. These structures allowed us to achieve optical data rates of 2Gbps in FPGA implementation and 5.4Gbps for 0.18mum ASIC implementation. The techniques presented can be adapted for other similar architectures

This paper presents an interleaver-division multiple access (IDMA) based architecture with single-user decoding using parallel concatenated non-linear trellis codes (PC-NLTCs). These PC-NLTCs are designed specifically for the Z-Channel that arises in a multiple-user OR channel when each user treats the other users as noise. Over the OR multiple access channel (OR-MAC) single-user decoding permits operation at about 70% of the full multiple access channel sum capacity. In order to reach the sum capacity of the OR-MAC, these codes employ a ones density of much less than 50%. A union bound technique that predicts the performance of these codes under maximum- likelihood (ML) decoding is presented. The uniform interleaver analysis presented in this paper can be applied to any asymmetric channel, as long as an additive distance can be defined. Results for different numbers of users and a sum-rate of 60% are presented.

In this paper, we propose serially concatenated trellis coded modulations (SCTCMs) that perform consistently close to the available mutual information for the 2-by-2 compound matrix channel. The proposed SCTCMs use universal SCTCMs for the period-2 periodic fading channel in order to deliver consistent performance over eigenvalue skew. Within the family of channels having the same eigenvalue skew, a time-varying linear transformation (TVLT) is used to mitigate the performance variation over different eigenvectors. The proposed SCTCMs of 1, 2 and 3 bits per transmission require excess mutual information in the ranges 0.11- 0.15, 0.23-0.26 and 0.35-0.53 bits per antenna, respectively. Because of their consistent performance over all channels, the proposed codes will have good frame-error-rate (FER) performance over any quasi- static fading distribution. In particular, the codes provide competitive FER performance in quasi-static Rayleigh fading.

This paper presents trellis codes for the Z channel designed to maintain a relatively low ones density. These codes have applications in pulse-position modulation systems and as a solution for uncoordinated communication on the binary OR multiple-access channel (MAC). In this paper we consider the latter application to demonstrate the performance of the codes. The OR channel provides an unusual opportunity where single-user decoding permits operation at about 70% of the full multiple-access channel sum capacity. The interleaver-division multiple access technique applied in this paper should approach that performance with turbo solutions. However, the current paper focuses on very low latency codes with simple decoding, intended for very high speed (gigabits per second) applications. Namely, it focuses on nonlinear trellis codes that provide about 30% of the full multiple-access sum capacity at high speeds and with very low latency. These trellis codes are designed specifically for the Z-Channel that arises in a multiple-user OR channel, when the other users are treated as noise. In order to optimize the sum-capacity of the OR-MAC, the trellis code transmits codewords with a ones density much less than 50%. Also, a union bound technique that predicts the performance of these codes is presented. Results from simulations and a working FPGA implementation are shown.

In broadcast scenarios or in the absence of accurate channel probability distribution information, code design for consistent channel-by-channel performance, rather than average performance over a channel distribution, may be desirable. Root and Varaiya's compound channel theorem for linear Gaussian channels promises the existence of universal codes that operate reliably whenever the channel mutual information (MI) is above the transmitted rate. This paper presents 2-D trellis codes that provide such universal performance over the compound linear vector Gaussian channel when demultiplexed over two, three, and four transmit antennas. The presented trellis codes are found by an exhaustive search that guarantees consistent performance on every matrix channel that supports the information transmission rate with an MI gap that is similar to the capacity gap of a well-designed additive white Gaussian noise (AWGN)-specific code on the AWGN channel. As a result of their channel-by-channel consistency, the universal trellis codes presented here also deliver comparable, or in some cases, superior frame-error rate and bit-error rate performance under quasi-static Rayleigh fading to trellis codes of similar complexity that are designed specifically for the quasi-static Rayleigh fading scenario.

In broadcast scenarios or in the absence of accurate channel probability distribution information, code design for consistent channel-by-channel performance, rather than average performance over a channel distribution, may be desirable. Root and Varaiya's compound channel theorem for linear Gaussian channels promises the existence of universal codes that operate reliably whenever the channel mutual information (MI) is above the transmitted rate. This paper presents two-dimensional trellis codes that provide such universal performance over the compound linear vector Gaussian channel when demultiplexed over two, three, and four transmit antennas. The presented trellis codes, found by exhaustive search, guarantee consistent performance on every matrix channel that supports the information transmission rate with an MI gap that is similar to the capacity gap of a well-designed additive white Gaussian noise (AWGN)-specific code on the AWGN channel. As a result of their channel-by-channel consistency, the universal trellis codes presented here also deliver comparable, or, in some cases, superior, frame-error rate and bit-error rate performance under quasi-static Rayleigh fading, as compared with trellis codes of similar complexity that are designed specifically for the quasi-static Rayleigh-fading scenario

In this paper, we propose a dual-mode decoding technique for product codes in which the rows and columns may comprise either Reed-Solomon (RS) codewords or LDPC codewords. The first decoding mode uses standard hard-decision decoding algorithms on the rows and columns, after which a maximum-likelihood (ML) packet-erasure decoding algorithm is employed for the column code in a second decoding mode. For the second mode, the column code takes on a different character in which "slices" of the row code are treated as packets which are symbols in the column code. The ML decoder for this packet-level column code resolves the erroneous packets (erasures) flagged by the row code or a packet-level CRC code during the first decoding mode. By exploring an application to tape storage, we demonstrate that this dual-mode decoding method can dramatically improve the performance of a product code. Moreover, the complexity added by the second mode is manageable.

Array codes are error-correcting codes of very low complexity that were initially used for burst and erasure correction in redundant arrays of inexpensive disks (RAID) architectures and other storage applications. The structure of these codes allows a very simple encoding and decoding mechanism. Although they are very high-rate codes, they do not achieve the maximum possible rate given their design constraints. In fact Hamming codes maximize the possible rate given these design constraints. This paper compares the rate and complexity of array codes when compared to Hamming codes.

We study the maximum flow possible between a single-source and multiple terminals in a weighted random graph (modeling a wired network) and a weighted random geometric graph (modeling an ad-hoc wireless network) using network coding. For the weighted random graph model, we show that the network coding capacity concentrates around the expected number of nearest neighbors of the source and the terminals. Specifically, for a network with a single source, l terminals, and n relay nodes such that the link capacities between any two nodes is independent and identically distributed (i.i.d.) /spl sim/X, the maximum flow between the source and the terminals is approximately nE[X] with high probability. For the weighted random geometric graph model where two nodes are connected if they are within a certain distance of each other we show that with high probability the network coding capacity is greater than or equal to the expected number of nearest neighbors of the node with the least coverage area.

In the absence of accurate channel probability distribution information or in broadcast scenarios, code design for consistent channel-by-channel performance, rather than average performance, may be desirable. Root and Varaiya's compound channel theorem promises the existence of universal codes that operate with a consistent proximity to channel mutual information on any instance of the compound linear vector Gaussian channel that is similar to the capacity gap of an AWGN-specific code with similar complexity on the AWGN channel. This study presents single-dimensional trellis codes such that when multiplexed over two, three and four transmit antennas, provide universal performance over the compound linear vector Gaussian channel. As a result of their channel-by-channel consistency, the universal trellis codes presented here deliver comparable or in some cases superior frame-error-rate and bit-error-rate performance under quasistatic Rayleigh fading to trellis codes of similar complexity that are designed specifically for the quasistatic Rayleigh fading scenario.

A channel-eigenvector invariant space-time constellation (CEI-STC) is a set of matrices such that the product of any pairwise difference matrix and its complex conjugate transpose is a scalar matrix. The pairwise error probability of a multi-antenna system equipped with the CEI-STC does not depend on the eigenvectors of the channel matrix. It may, however, depend on the eigenvalues of the channel. The maximum cardinality of a CEI-STC whose entries are restricted to a finite set is studied. A lower bound and an upper bound on the maximum cardinality are obtained.

We present a construction algorithm for short block length irregular low-density parity-check (LDPC) codes. Based on a novel interpretation of stopping sets in terms of the parity-check matrix, we present an approximate trellis-based search algorithm that detects many stopping sets. Growing the parity check matrix by a combination of random generation and the trellis-based search, we obtain codes that possess error floors orders of magnitude below randomly constructed codes and significantly better than other comparable constructions.

The rotationally invariant space time constellation (RISTC) is defined. Both linear and affine constellations are studied. The RISTC is shown to be generalization of space time codes from the orthogonal design. A space time constellation is said rotationally invariant if for any pair in the set, the squared Euclidean distance is independent of the eigenvectors.

This work presents a rigorous analysis of an algorithm proposed by Tian et al. (2003) for the construction of irregular LDPC codes with reduced stopping sets and low error floors. Computation of the expected number of stopping sets of a given size proves that the algorithm significantly outperforms a random construction. We show that the algorithm provably reduces the expected number of stopping sets up to a certain size (based on the input parameters). The expected number of cycles of a given size is computed for both constructions.

For trellis codes, generating function techniques provide the distance spectrum and a union bound on bit-error rate. The computation of the generating function of a trellis code may be separated into two stages. The first stage reduces the number of states as much as possible using low-complexity approaches. The second stage produces the generating function from the reduced-state diagram through some form of matrix inversion, which has a relatively high complexity. In this paper, we improve on the amount of state reduction possible during the low-complexity first stage. We also show that for a trellis code that is a linear convolutional code followed by a signal mapper, the number of states may always be reduced from N/sup 2/ to ((N/sup 2/-N)/2)+1 using low-complexity techniques. Finally, we analytically compare the complexity of various matrix inversion techniques and verify through simulation that the two-stage approach we propose has the lowest complexity. In an example, the new technique produced the union bound in about half the time required by the best algorithm already in the literature.

Bergmans and Cover identified the capacity region of the Gaussian degraded broadcast channel, where different receivers observe the transmitted signal with different signal-to-noise ratios. This letter presents a superposition turbo-coding scheme that performs within 1 dB of the capacity region boundary of the degraded broadcast channel at a bit-error rate of 10/sup -5/.

This letter explains the effect of graph connectivity on error-floor performance of low-density parity-check (LDPC) codes under message-passing decoding. A new metric, called extrinsic message degree (EMD), measures cycle connectivity in bipartite graphs of LDPC codes. Using an easily computed estimate of EMD, we propose a Viterbi-like algorithm that selectively avoids small cycle clusters that are isolated from the rest of the graph. This algorithm is different from conventional girth conditioning by emphasizing the connectivity as well as the length of cycles. The algorithm yields codes with error floors that are orders of magnitude below those of random codes with very small degradation in capacity-approaching capability.

This paper presents a symmetry-based technique for trellis-code state-diagram reduction that has more general applicability than the quasi-regularity technique of Rouanne et al. and Zehavi et al. for trellis codes using standard constellations and labelings. For a 2/sup /spl nu/x/-state trellis code, the new technique reduces the 2/sup 2/spl nu/x/ state diagram to 2/sup /spl nu/x+/spl nu/q/-state diagram where 0/spl les//spl nu//sub q//spl les//spl nu//sub x/. The particular value of /spl nu//sub q/ depends on the constellation labeling and the convolutional encoder. For standard rate-k/(k+1) set-partitioned trellis codes, /spl nu//sub q/=0, and the overall number of states is the same with the new technique as with quasi-regularity. For codes that are not quasi-regular (and thus not amenable to the quasi-regularity technique), the new technique often provides some improvement (when /spl nu//sub q/

This paper extends the near-capacity performance of serially-concatenated convolutional codes under AWGN to periodically time-varying channels. In particular, we propose serially-concatenated trellis-coded modulations (SCTCMs) that perform consistently close to channel capacity under periodic erasures as well as under AWGN, without sacrificing AWGN channel performance. The proposed 0.5 bits/symbol and 1.5 bits/symbol SCTCM schemes are robust with respect to periodic time-variations with a period of two-symbols.

Biglieri showed that a diagram with N/sup 2/ states can be used to compute the generating function for any trellis code with N states. Rouanne & Costello and Zehavi & Wolf showed that for quasi-regular trellis codes, an N-state diagram produces the correct generating function. Schlegel showed that application of a standard FSM (finite-state-machine) minimization algorithm reduces quasi-regular trellis code diagrams to at most N states and often reduces the number of states for non-quasi-regular trellis codes as well. In this paper we show that performing iteratively both a forward and a backward application of Schlegel's state reduction operation can further reduce the diagram produced by Schlegel's algorithm. We also found that the maximum required diagram size for linear trellis codes to be [(N/sup 2/ - N)/2] + 1.

Bergmans and Cover identified the capacity region of the Gaussian degraded broadcast channel, where different receivers observe the transmitted signal to noise ratios. This paper presents a superposition turbo coding scheme that performs within 1 dB of the capacity region boundary of the degraded broadcast channel at BER of 10/sup -5/. Performance is consistent over the entire useful range of the power allocation parameter /spl alpha/. Coding for the degraded broadcast channel is equivalent to coding for unequal error protection. Adjusting /spl alpha/ changes the transmitter constellation of our encoder, and changes the degree to which error protection is unequal. When /spl alpha/ is selected to provide equal error protection, the code is essentially a multilevel turbo trellis-coded-modulation schemes with the advantage of the potential for flexible unequal error protection as /spl alpha/ is varied.

This work explains the relationship between cycles, stopping sets, and dependent columns of the parity check matrix of low-density parity-check (LDPC) codes. Furthermore, it discusses how these structures limit LDPC code performance under belief propagation decoding. A new metric called extrinsic message degree (EMD) measures cycle connectivity in bipartite graph. Using an easily computed estimate of EMD, we propose a Viterbi-like algorithm that selectively avoids cycles and increases stopping set size. This algorithm yields codes with error floors that are orders of magnitude below those of girth-conditional codes.

This article gives practical examples of space-time trellis codes performing as predicted by Root and Varaiya's (1968) compound channel theorem. Specifically, 32-state and 64-state 2/spl times/2 space-time trellis codes are presented that provide a bit-error rate (BER) of 10/sup -5/ on all 2/spl times/2 matrix channels with an excess mutual information (MI) within 8% of the excess MI required by standard trellis codes of the same complexity operating only in additive white Gaussian noise (AWGN). Not surprisingly, the universal space-time trellis-coded modulations (ST-TCMs) provide average bit- and frame-error rates in quasi-static Rayleigh fading (QRF) that are comparable to those achieved by ST-TCMs designed specifically for QRF as well as standard TCMs followed by the Alamouti (1998) space-time block code. However, all of these other schemes require more excess MI in the worst case, and some have a significantly wider variation in the required excess MI. The article also compares the universal and quasi-static Rayleigh fading design approaches analytically and bounds the worst case distance of a trellis code on a 2/spl times/2 channel using the distances of the code on singular and unitary channels. This bound is extended to the more general n/sub T//spl times/n/sub R/ scenario.

Root and Variya (1968) proved the existence of codes that can communicate reliably over any member of a set of linear Gaussian channels where each member exceeds a given amount of mutual information. In this paper we show that LDPC codes are such codes and that their performance lies within 0.1 bits of the Root and Variya capacity for a large family of periodic Gaussian channels. specifically, the robustness of LDPC codes to periodic fading is demonstrated through the consistency of their mutual information performance across period-2 and period-256 fading profiles. The latter case implies that these codes are ideal candidates for coding in OFDM.

The compound channel theorem for linear Gaussian vector channels indicates that a single code can provide reliable communication on all channels that induce a minimum amount of mutual information. This paper discusses the search for space-time trellis codes that deliver such consistently good performance on every matrix channel that has a proximity to channel capacity similar to standard trellis codes in AWGN. By characterizing the minimum distance of an error event transformed by the channel as a function of the eigenvalues of the channel matrix, we search for codes having the largest such worst-case distance for systems with two transmit antennas. Proposed trellis codes found by exhaustive search guarantee coded performance on every matrix channel without sacrificing error performance under quasistatic Rayleigh fading.

Foschini's (1996) diagonally layered space-time transmission system known as D-BLAST is an advanced architecture designed for a Rayleigh fading environment using multiple element antenna arrays at both the transmit and receive sites to achieve very high spectral efficiencies. In this paper we examine the performance of trellis codes that are designed to have a distance structure that is matched to the periodic signal-to-noise ratio variation of the channel created by D-BLAST, under the assumption that the channel is static during one burst but may change from burst to burst. We show that trellis coding comes within 2 dB of the best theoretical outage curve possible with D-BLAST.

We present a structure for reduced complexity iterative demodulation and decoding of partial response continuous phase modulation (CPM) when serially concatenated with a convolutional code. The proposed receiver uses a single front-end filter and a 2 or 4 state trellis for decoding the inner CPM code. This can yield a significant savings, as the complexity of the optimal demodulator increases exponentially with the length of the CPM frequency pulse. Simulations show that for GMSK with BT = 1/6, the performance penalty for simplified iterative demodulation and decoding is less than 0.25 dB, compared to the receiver which performs optimal demodulation (which requires 32 filters and a 64 state inner trellis).

This paper presents bandwidth-efficient speech transmission systems using rate-compatible channel coders and variable bitrate embedded source coders. Rate-compatible punctured convolutional codes (RCPC) are often used to provide unequal error protection (UEP) via progressive bit puncturing. RCPC codes are well suited for constellations for which Euclidean and Hamming distances are equivalent (BPSK and 4-PSK). This paper introduces rate-compatible punctured trellis codes (RCPT) where rate compatibility and UEP are provided via progressive puncturing of symbols in a trellis. RCPT codes constitute a special class of codes designed to maximize residual Euclidean distances (RED) after symbol puncturing. They can be designed for any constellation, allowing for higher throughput than when restricted to using 4-PSK. We apply RCPC and RCPT to two embedded source coders: a perceptual subband coder and the ITU embedded ADPCM G.727 standard. Different operating modes with distinct source/channel bit allocation and UEP are defined. Each mode is optimal for a certain range of AWGN channel SNRs. Performance results using an 8-PSK constellation clearly illustrate the wide range of channel conditions at which the adaptive scheme using RCPT can operate. For an 8-PSK constellation, RCPT codes are compared to RCPC with bit interleaved coded modulation codes (RCPC-BICM). We also compare performance to RCPC codes used with a 4-PSK constellation.

We consider the problem of binary hypothesis testing using binary decisions from independent and identically distributed (i.i.d). sensors. Identical likelihood-ratio quantizers with threshold /spl lambda/ are used at the sensors to obtain sensor decisions. Under this condition, the optimal fusion rule is known to be a k-out-of-n rule with threshold k. For the Bayesian detection problem, we show that given k, the probability of error is a quasi-convex function of /spl lambda/ and has a single minimum that is achieved by the unique optimal /spl lambda//sub opt/. Except for the trivial situation where one hypothesis is always decided, we obtain a sufficient and necessary condition on /spl lambda//sub opt/, and show that /spl lambda//sub opt/ can be efficiently obtained via the SECANT algorithm. The overall optimal solution is obtained by optimizing every pair of (k, /spl lambda/). For the Neyman-Pearson detection problem, we show that the use of the Lagrange multiplier method is justified for a given fixed k since the objective function is a quasi-convex function of /spl lambda/. We further show that the receiver operating characteristic (ROC) for a fixed k is concave downward.

This paper compares bit versus symbol interleaving for parallel-concatenated trellis-coded turbo codes, employing the turbo encoder structure proposed in Benedetto et al., (1996). To compare systems optimized with the same techniques, the paper extends the turbo-encoder design procedure proposed in Fragouli et al. (2001), to bit-interleaved systems. We discuss a method to jointly design the multiple required interleavers for the bit-interleaved system, and a procedure to select constituent encoders that can take advantage of the interleaver structure to achieve a low error floor. Simulation results for the designed bit-interleaved system show better performance than bit-interleaved performance reported in the literature. The symbol-interleaved system though achieves an earlier convergence, especially with an increased number of decoder iterations, but at the cost of a slightly higher error floor.

This paper compares the performance of two schemes for joint channel estimation and turbo-decoding of high-rate trellis turbo-codes in flat Rayleigh fading, where antenna diversity is available at the receiver. The first method relies on iterative quantized phase estimation, and the second on optimum filtering of pilot and coded symbols. For Doppler rates of practical interest, simulations indicate that optimum pilot filtering is superior to approximating the channel phase with a quantized Markov model. The optimum filtering approach also has lower complexity. For an absolute measure of performance, proximity to channel capacity is also discussed. Iterative joint channel estimation and turbo-decoding with either method is demonstrated to achieve almost all the capacity gain due to receiver antenna diversity.

This paper investigates encoders optimization for the Hamming weight after periodic puncturing, and discusses minimality issues that may affect the performance of the punctured encoders. Periodically puncturing a minimal encoder produces a higher rate encoder that may or may not be minimal. If it is not minimal, it may have a zero-output loop and it may be catastrophic. A code search can use a fast algorithm to determine whether an encoder's state diagram has a zero-output loop under periodic symbol puncturing, and a proposed method to assess the performance of codes with a zero-output loop that are not catastrophic. As an example, the paper optimizes rate-1/4 unpunctured codes for Hamming weight under both bit-wise and symbol-wise periodic puncturing. Code tables and simulation results are included.

This paper presents parallel concatenated turbo codes that employ a non-uniform constellation to achieve shaping gain. The output signal approximates the Gaussian distribution by using equally likely signals with unequal spacing (a non-uniform constellation). The small distance of points near the center of the constellation may lead to a small overall free distance and thus a high error floor for turbo codes. We avoid this situation by a two-step design procedure, that first creates an interleaver, and then identifies the constituent encoders that maximize the turbo code free distance. Simulation results for 4 bits/sec/Hz show that this use of shaping can offer an improvement of approximately 0.2 dB for turbo codes.

This paper presents a worst-case pairwise codeword error probability analysis, under arbitrary block fading, for wireless communication systems with multiple transmit and receive antennas. Our results generalize the Rayleigh-fading space-time code design criteria (full rank and maximum determinant) to arbitrary fading.

In wireless systems supporting slowly moving users, adaptive trellis-coded modulation (TCM) schemes have demonstrated large bandwidth efficiency gains over their nonadaptive counterparts. In systems with highly mobile users, the adaptive bit-interleaved coded modulation (BICM) achieves a moderate bandwidth efficiency gain over previously proposed adaptive schemes and nonadaptive schemes with similar complexity. However, adaptive BICM requires a bit interleaver, which results in long latency. In this paper, adaptive coded modulation (ACM) schemes which do not employ interleaving and do not use uncoded bits are considered for time-varying channels. Two such ACM schemes are proposed. One of the ACM schemes uses a forward trellis search algorithm (FTS) to adapt to the current channel fading. Numerical results demonstrate that the proposed FTS-ACM scheme achieves a comparable bandwidth efficiency gain to adaptive BICM. FTS-ACM is particularly attractive for low latency transmission applications.

We consider the performance of a turbo code with 2 transmit antennas and 2 receive antennas for flat fading channels. We consider robustness within and among families of channels with the same singular values (SVs). When the two SVs are similar, the bit error rate performance is robust in terms of proximity to the channel capacity. When the 2 SVs differ significantly, robust performance can be achieved by a time-varying linear transformation (TVLT). Iterative decoding is the same as for standard parallel concatenated convolutional codes, except that the extrinsic information about encoder outputs are also exchanged.

This paper addresses the design and performance evaluation with respect to capacity of M-PSK turbo-coded systems operating in frequency-flat time-selective Rayleigh fading. The receiver jointly performs channel estimation and turbo decoding, allowing the two processes to benefit from each other. To this end, we introduce a suitable Markov model with a finite number of states, designed to approximate both the values and the statistical properties of the correlated flat fading channel phase, which poses a more severe challenge to PSK transmission than amplitude hiding. Then, the forward-backward algorithm determines both the maximum a posteriori probability (MAP) value for each symbol in the data sequence and the MAP channel phase in each iteration. Simulations show good performance in standard correlated Rayleigh fading channels. A sequence of progressively tighter upper bounds to the capacity of a simplified Markov-phase channel is derived, and performance of a turbo code with joint iterative channel estimation and decoding is demonstrated to approach these capacity bounds.

This paper addresses turbo-encoder design for coding with high spectral efficiency using parallel concatenated trellis-coded modulation and symbol interleaving. The turbo-encoder design involves the constituent encoder design and the interleaver design. The constituent encoders are optimized for symbol-wise effective free distance, and each has an infinite symbol-wise impulse response. We identify the canonical structures for the constituent encoder search space. In many cases of practical interest, the optimal structure for these constituent encoders connects the memory elements in a single row. This single row generally applies to turbo code constituent encoders for parallel concatenation and is not restricted to symbol interleaving. To lower the error floor, a new semi-random interleaver design criteria and a construction method extends the spread-interleaver concept introduced by Divsalar and Pollara (1995). Simulation results show that the proposed system employing symbol interleaving can converge at a lower signal-to-noise ratio than previously reported systems. We report simulation results between 0.5 and 0.6 db from constrained capacity for rates of 2 and 4 bits/s/Hz.

Adaptive coded modulation is a powerful method for achieving a high spectral efficiency over fading channels. Previously proposed adaptive schemes have employed set-partitioned trellis-coded modulation (TCM) and have adapted the number of uncoded bits on a given symbol based on the corresponding channel estimate. However, these adaptive TCM schemes do not perform well in systems where channel estimates are unreliable, since uncoded bits are not protected from unexpected finding. In this paper, adaptive bit-interleaved coded modulation (BICM) is introduced. Adaptive BICM schemes remove the need for parallel branches in the trellis-even when adapting the constellation size, thus making these schemes robust to errors made in the estimation of the current channel fading value. This motivates the design of adaptive BICM schemes, which will lead to adaptive systems that can support users with higher mobility than those considered in previous work. In such systems, numerical results demonstrate that the proposed schemes achieve a moderate bandwidth efficiency gain over previously proposed adaptive schemes and conventional (nonadaptive) schemes of similar complexity.

We present a technique to find the optimal threshold /spl tau/ for the binary hypothesis detection problem with n identical and independent sensors. The sensors all use an identical and single threshold /spl tau/ to make local decisions, and the fusion center makes a global decision based on the n local binary decisions. For generalized Gaussian noise and some non-Gaussian noise distributions, we show that for any admissible fusion rule, the probability of error is a quasi-convex function of threshold /spl tau/. Hence, the problem decomposes into a series of n quasi-convex optimization problems that may be solved using well-known techniques. Assuming equal a priori probability, we give a sufficient condition of the non-Gaussian noise distribution g(x) for the probability of error to be quasi-convex. Furthermore, this technique is extended to Bayes risk and Neyman-Pearson criteria. We also demonstrate that, in practice, it takes fewer than twice as many binary sensors to give the performance of infinite precision sensors in our scenario.

This paper investigates optimal constellation labeling in the context of the edge profile. A constellation's edge profile lists the minimum-distance edge for each binary symbol error. The paper introduces the symmetric-ultracomposite (SU) labeling structure and shows that this structure provides undominated edge profiles for 2/sup n/-PSK, 2/sup n/-PAM, and 2/sup 2n/-point square QAM. The SU structure is a generalization of the commonly used reflected binary Gray code. With the proper choice of basis vectors, SU labeling can support either set-partition or Gray-code labeling of 2/sup n/-PSK, 2/sup n/-PAM, and 2/sup 2n/-point square QAM. Notably, there are Gray-code and set-partition labelings that do not have the SU structure. These labelings yield inferior edge profiles. The SU structure does not apply to cross constellations. However, for any standard cross constellation with 32 or more points, a quasi-SU labeling structure can approximate the SU structure. With the correct choice of basis, quasi-SU labelings produce quasi-Gray labelings. However, the quasi-SU structure cannot support set-partition labeling. In fact, the quasi-SU structure provides a better edge profile than standard set-partition labeling. Thus, for cross constellations there is a choice between edge profile optimality and the group structure provided by set-partitioning. Here, the correct choice depends on whether the encoder trellis has parallel branches.

This paper addresses the problem of adaptive channel tracking and equalization for multi-input multi-output (MIMO) time-variant frequency-selective channels. A finite-length minimum-mean-squared-error decision-feedback equalizer (MMSE-DFE) performs the equalization task, while a Kalman filter tracks the MIMO channel, which models the corrupting effects of inter-symbol interference (ISI), inter-user interference (IUI), and noise. The Kalman tracking is aided by previous hard decisions produced by the DFE, with a decision delay /spl Delta/>0, which causes the Kalman filter to track the channel with a delay. A channel prediction module bridges the time gap between the channel estimates produced by the Kalman filter and those needed for the DFE adaptation. The proposed algorithm offers good tracking behavior for multi-user fading ISI channels at the expense of higher complexity.

Structurally distinct constellation labeling exists within both the Gray code and the set-partitioning paradigm. Different labeling choices within either paradigm can provide different bit error rates, especially at low SNR. This paper demonstrates that symmetric ultracomposite (SU) labeling, an extension of the binary reflected Gray code, provides undominated edge profiles for all standard PSK, PAM and square QAM constellations. (The edge profile lists the minimum distance for each binary symbol error) The SU structure can accomodate either the Gray code or the set-partitioning paradigm. It is the clear labeling choice for standard PSK, PAM and square QAM constellations. An extension of SU labeling provides quasi-SU (QSU) labeling for all 2/sup 2n+1/-cross constellations for n>1. QSU labeling satisfies the quasi-Gray property for cross constellations. For cross constellations, set-partitioning and QSU labeling structures are distinct. For 32-cross, QSU labeling has a superior edge profile and is preferred when the trellis does not have parallel branches. Despite its inferior profile, set-partitioned 32-cross is still preferred when the trellis has parallel branches.

There are several ways to use iterative decoding techniques with coded continuous phase modulation (CPM). This paper presents a method using parallel concatenation of convolutionally-coded CPM. All CPM schemes can be decomposed into a ring convolutional code and a memoryless signal mapper. This allows a properly designed convolutional code trellis to be combined with the CPM trellis, producing the joint trellis of a constituent code. Parallel concatenation of such constituent codes combined with iterative decoding yields very good performance. We present the results of code searches for two binary CPM schemes, each using bit interleaving and symbol interleaving. Simulation results using various length interleavers are also provided. Low complexity encoders are shown to perform better using bit interleaving, whereas encoders with higher complexity perform better with symbol interleaving.

This paper describes techniques for the design and analysis of trellis codes that provide reliable communication over every channel in a specified set of possible channels, where each channel is characterized by additive white Gaussian noise with a distinct periodic variation in signal-to-noise ratio. An important practical application for such trellis codes is the periodic erasure channel produced by partial-band interference dispersed by a block interleaver. We present trellis codes that provide reliable communication over all periodic erasure patterns of a given period for which the number of unerased coded bits per period is at least equal to the number of information bits per period.

This paper presents an embedded joint source-channel coding scheme of speech. The source coder is an embedded variable bit rate perceptually based sub-band coder producing bits with different error sensitivities. The channel encoder is a rate compatible punctured trellis code (RCPT) which permits rate variability and unequal error protection by puncturing symbols. Furthermore, RCPT code design naturally incorporates large constellations, allowing high information rate per symbol. The embedded speech coder and the rate compatible puncturing of symbols provide the embeddibility of the joint coding scheme. The coder is robust to acoustic noise and produces good quality speech for a wide range of channel conditions (AWGN or fading), allowing digital transmission of speech with analog-like graceful degradation.

This article examines Tomlinson-Harashima precoding (1971, 1972) on discrete-time channels having intersymbol interference and additive white Gaussian noise. An exact expression for the maximum achievable information rate of zero-forcing (ZF) THP is derived as a function of the channel impulse response, the input power constraint, and the additive white Gaussian noise variance. Information rate bounds are provided for the minimum mean-square error (MMSE) THP. The performance of ZF-THP and MMSE-THP relative to each other and to channel capacity is explored in general and for some example channels. The importance of symbol rate to ZF-THP performance is demonstrated.

This paper examines two vector quantization algorithms which can combine the tasks of compression and classification: Bayes risk weighted vector quantization (BRVQ) proposed by Oehler et al. (1991), and optimized learning vector quantization 1 (OLVQ1) proposed by Kohonen et al. (1988). BRVQ uses a parameter /spl lambda/ to control the tradeoff between compression and classification. BRVQ performance is studied for a range of /spl lambda/ values for four classification problems. Increasing the /spl lambda/ parameter in BRVQ is intended to improve classification performance. However, for two of the problems studied, increasing /spl lambda/ degraded classification performance. A majority rule reclassification of the final codebook (using only the training set) greatly improves high-/spl lambda/ BRVQ performance for these cases. Finally, we compare the classification performance and mean square error (MSE) performance of BRVQ to that of OLVQ1 for four classification problems. BRVQ with codebook reclassification is found to have a lower MSE than OLVQ1 while maintaining comparable, but slightly inferior, classification performance.>