Search

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

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

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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 Ml 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. [ABSTRACT FROM AUTHOR]

We study the maximum How 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.) ∼ 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. [ABSTRACT FROM AUTHOR]

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 2vx-state trellis code, the new technique reduces the 22vx state diagram to vq diagram where 0 ≤ Vq ≤ Vx. The particular value of Vq depends on the constellation labeling and the convolutional encoder. For standard rate-k / (k +1) set-partitioned trellis codes, Vq = 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 Vq < Vx). For 8-phase-shift-keying trellis codes, the new technique always yields vq = 0. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

This correspondence gives practical examples of space-time trellis codes performing as predicted by Root and Varaiya's compound channel theorem. Specifically, 32-state and 64-state 2 × 2 space-time trellis codes are presented that provide a bit-error rate (BER) of 10[sup -5] on all 2 × 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 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 correspondence 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 × 2 channel using the distances of the code on singular and unitary channels. This bound is extended to the more general n[sub T] × n[sub R] scenario. [ABSTRACT FROM AUTHOR]

Presents information on a study which described the bandwidth-efficient speech transmission systems using rate-compatible channel coders and variable bitrate embedded source coders. Description of the perceptually-based and embedded subband coder; Design of an adaptive multirate source-channel coding scheme for the subband coder; Conclusions.

Presents a study which investigated optimal constellation labeling for a standard trellis-coded modulation in the context of the edge profile. Examination of constellation labeling and trellis codes; Labelings with undominated edge profiles; Details on cross constellations.

Presents a method for parallel concatenated trellis-coded modulation. Design of constituent encoders; Information on the interleaver design; Simulation results.

Examines the Tomlinson-Harashima precoding (THP) on discrete-time channels having intersymbol interference and additive white Gaussian noise. How THP feedforward and feedback filters are indicated; Feedforward and feedback filter selection; Information rates for THP; Performance comparisons.

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

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. [ABSTRACT FROM PUBLISHER]