Search

In this paper, we introduce a fundamental principle for optimal communication over general memoryless channels in the presence of noiseless feedback, termed posterior matching. Using this principle, we devise a (simple, sequential) generic feedback transmission scheme suitable for a large class of memoryless channels and input distributions, achieving any rate below the corresponding mutual information. This provides a unified framework for optimal feedback communication in which the Horstein scheme (BSC) and the Schalkwijk-Kailath scheme (AWGN channel) are special cases. Thus, as a corollary, we prove that the Horstein scheme indeed attains the BSC capacity, settling a longstanding conjecture. We further provide closed form expressions for the error probability of the scheme over a range of rates, and derive the achievable rates in a mismatch setting where the scheme is designed according to the wrong channel model. Several illustrative examples of the posterior matching scheme for specific channels are given, and the corresponding error probability expressions are evaluated. The proof techniques employed utilize novel relations between information rates and contraction properties of iterated function systems. [ABSTRACT FROM PUBLISHER]

It has been known since [Zyablov and Pinsker, 1982] that a random q-ary code of rate 1-Hq(\rho )- \varepsilon (where 0< \rho < 1-1/q, \varepsilon >0 is small enough and Hq(\cdot ) is the q-ary entropy function) with high probability is a (\rho ,1/ \varepsilon )-list decodable code (that is, every Hamming ball of radius at most \rho n has at most 1/ \varepsilon codewords in it). In this paper, the “converse” result is proven. In particular, it is proven that for every 0< \rho < 1-1/q, a random code of rate 1-Hq(\rho )- \varepsilon , with high probability, is not a (\rho ,L)-list decodable code for any L \leqslant c\over \varepsilon , where c is some constant that depends only on \rho and q. A similar lower bound is also shown for random linear codes. Previously, such a tight lower bound on the list size was only known for the case when \rho \geqslant 1-1/q-O(\sqrt \varepsilon ) for small enough \varepsilon >0 [Blinovsky, 1986, 2005, 2008; Guruswami and Vadhan, 2005]. A lower bound is known for all constant 0< \rho < 1-1/q independent of \varepsilon , though the lower bound is asymptotically weaker than our bound [Blinovsky, 1986, 2005, 2008]. These results, however, are not subsumed by ours as these other results hold for arbitrary codes of rate 1-Hq(\rho )- \varepsilon . [ABSTRACT FROM PUBLISHER]

In this paper, we present results on the equivalence of some coding strategies for the general relay channel. Cover & El Gamal described two basic coding strategies for the relay channel, more commonly known as decode-and-forward and compress-and-forward. These two strategies were combined in a mixed strategy that employed irregular encoding and successive forward decoding to give a tighter lower bound for the capacity of the general relay channel. Recently, the authors presented two different mixed strategies, SeqBack decoding and SimBack decoding, that make use of regular encoding and backward decoding. We identify a termination problem in SeqBack/SimBack decoding and present a simple fix. Next, we compare the rates achievable with the various mixed strategies. We first show that SeqBack decoding and SimBack decoding achieve the same rate. We then present alternative characterizations, without feasibility constraints, for the rates achievable with the various mixed strategies. Comparing the alternative characterizations, we note that the rate of SeqBack/SimBack decoding contains the rate of Cover & El Gamal's mixed strategy since there is a more relaxed inequality in the rate expression. We also prove that simultaneously decoding all unknown quantities in each block at the receiver does not increase the achievable rate for backward decoding. Hence, successive decoding in each block proves to be just as effective as simultaneous decoding. Finally, we present a sliding-window decoding strategy that achieves the same rate as SeqBack/SimBack decoding. The sliding-window decoding strategy also avoids the aforementioned termination problem as the receiver commences decoding after three block decoding delay. [ABSTRACT FROM PUBLISHER]

In this paper, the impact of noncoordinated interfering signals on a point to point communication is addressed. While the transmitter has no information about the other users' messages, the receiver has full knowledge of the codebooks of the interfering users and can potentially decode some part of the interference. A simple coding strategy is proposed for this channel. Assuming its own data is decoded successfully, the receiver partitions the set of interfering users into two disjoint subsets, namely the set of decodable users and the set of nondecodable users. Then the transmitter's rate is chosen such that the intended signal can be jointly decoded with the set of decodable users. It is proved that the proposed strategy achieves the capacity of the additive Gaussian channel with Gaussian interfering users. A polynomial time algorithm is proposed to compute the achievable rate of the scheme. This algorithm is based a subroutine which separates the set of interfering users into decodable and nondecodable users in polynomial time. The proposed scheme is also applied to the case of M-user interference channel and some achievable points are characterized by successive maximization of users' rates. [ABSTRACT FROM PUBLISHER]

Though the entanglement-assisted formalism provides a universal connection between a classical linear code and an entanglement-assisted quantum error-correcting code (EAQECC), the issue of maintaining large amount of pure maximally entangled states in constructing EAQECCs is a practical obstacle to its use. It is also conjectured that the power of entanglement-assisted formalism to convert those good classical codes comes from massive consumption of maximally entangled states. We show that the above conjecture is wrong by providing families of EAQECCs with an entanglement consumption rate that diminishes linearly as a function of the code length. Notably, two families of EAQECCs constructed in the paper require only one copy of maximally entangled state no matter how large the code length is. These families of EAQECCs that are constructed from classical finite geometric LDPC codes perform very well according to our numerical simulations. Our work indicates that EAQECCs are not only theoretically interesting, but also physically implementable. Finally, these high performance entanglement-assisted LDPC codes with low entanglement consumption rates allow one to construct high-performance standard QECCs with very similar parameters. [ABSTRACT FROM PUBLISHER]

Motivated by a problem of transmitting supplemental data over broadcast channels (Birk and Kol, INFOCOM 1998), we study the following coding problem: a sender communicates with n receivers R1,\ldots ,Rn. He holds an input x \in \ 0,1 \ ^n and wishes to broadcast a single message so that each receiver Ri can recover the bit xi. Each Ri has prior side information about x, induced by a directed graph G on n nodes; Ri knows the bits of x in the positions \j \mid (i,j) ~is~an~edge~of~ G\. G is known to the sender and to the receivers. We call encoding schemes that achieve this goal indexcodes for \ 0,1 \^n with side information graph G. In this paper we identify a measure on graphs, the minrank, which exactly characterizes the minimum length of linear and certain types of nonlinear index codes. We show that for natural classes of side information graphs, including directed acyclic graphs, perfect graphs, odd holes, and odd anti-holes, minrank is the optimal length of arbitrary index codes. For arbitrary index codes and arbitrary graphs, we obtain a lower bound in terms of the size of the maximum acyclic induced subgraph. This bound holds even for randomized codes, but has been shown not to be tight. [ABSTRACT FROM PUBLISHER]

This work addresses the computational complexity of achieving the capacity of a general network coding instance. It has been shown [Lehman and Lehman, SODA 2005] that determining the “scalar linear” capacity of a general network coding instance is NP-hard. In this paper we address the notion of approximation in the context of both linear and nonlinear network coding. Loosely speaking, we show that given an instance of the general network coding problem of capacity C, constructing a code of rate \alpha C for any universal (i.e., independent of the size of the instance) constant \alpha \leq 1 is “hard”. Specifically, finding such network codes would solve a long standing open problem in the field of graph coloring. Our results refer to scalar linear, vector linear, and nonlinear encoding functions and are the first results that address the computational complexity of achieving the network coding capacity in both the vector linear and general network coding scenarios. In addition, we consider the problem of determining the (scalar) linear capacity of a planar network coding instance (i.e., an instance in which the underlying graph is planar). We show that even for planar networks this problem remains NP-hard. [ABSTRACT FROM AUTHOR]

Low-density parity-check (LDPC) convolutional codes are capable of achieving excellent performance with low encoding and decoding complexity. In this paper, we discuss several graph-cover-based methods for deriving families of time-invariant and time-varying LDPC convolutional codes from LDPC block codes and show how earlier proposed LDPC convolutional code constructions can be presented within this framework. Some of the constructed convolutional codes significantly outperform the underlying LDPC block codes. We investigate some possible reasons for this “convolutional gain,” and we also discuss the—mostly moderate—decoder cost increase that is incurred by going from LDPC block to LDPC convolutional codes. [ABSTRACT FROM AUTHOR]

Soft-decision decoding of Reed–Solomon codes delivers significant coding gains over classical minimum distance decoding. In this paper, we present architectures for polynomial interpolation and factorization, the two main steps of the soft-decoding algorithm. We introduce an algorithmic transformation for reducing the iterations required in generating the interpolation polynomial and present efficient architectures by sharing computations. We also describe algorithmic transformations for further reducing the interpolation and factorization latency. An area efficient, folded-pipelined version of the interpolation architecture is also described. Finally, we present an example of a Reed–Solomon soft decoder utilizing the presented architectures, having a 250 Mbps throughput. [ABSTRACT FROM AUTHOR]

Turbo codes and the iterative algorithm for decoding them sparked a new era in the theory and practice of error control codes. Turbo equalization followed as a natural extension to this development, as an iterative technique for detection and decoding of data that has been both protected with forward error correction and transmitted over a channel with intersymbol interference (ISI). In this paper, we review the turbo equalization approach to coded data transmission over ISI channels, with an emphasis on the basic ideas, some of the practical details, and many of the research directions that have arisen from this offshoot, introduced by Douillard, of the original turbo decoding algorithm. The subsequent relaxation of the maximum a posteriori (MAP) equalization algorithm to include linear and other simpler receivers sparked a decade and a half of research into iterative algorithms, spanning research problems ranging from trellis coded modulation to underwater acoustic communications. [ABSTRACT FROM AUTHOR]

An efficient algorithm which synthesizes all shortest skew-feedback shift-registers (defined in the paper) generating L sequences of varying length over a field is derived and its correctness is proved. It generalizes the Berlekamp–Massey algorithm and some other algorithms, and has time complexity \cal O(LN^2), where N is the length of a longest sequence. The proposed algorithm can be applied for efficiently solving the key equation when decoding interleaved (or direct sum of) Gabidulin codes beyond half minimum distance. Those codes have many applications and, as shown by Kötter and Kschischang, can be used for random network coding. [ABSTRACT FROM AUTHOR]

One popular approach to soft-decision decoding of Reed–Solomon (RS) codes is based on using multiple trials of a simple RS decoding algorithm in combination with erasing or flipping a set of symbols or bits in each trial. This paper presents a framework based on rate-distortion (RD) theory to analyze these multiple-decoding algorithms. By defining an appropriate distortion measure between an error pattern and an erasure pattern, the successful decoding condition, for a single errors-and-erasures decoding trial, becomes equivalent to distortion being less than a fixed threshold. Finding the best set of erasure patterns also turns into a covering problem that can be solved asymptotically by RD theory. Thus, the proposed approach can be used to understand the asymptotic performance-versus-complexity tradeoff of multiple errors-and-erasures decoding of RS codes. This initial result is also extended a few directions. The rate-distortion exponent (RDE) is computed to give more precise results for moderate blocklengths. Multiple trials of algebraic soft-decision (ASD) decoding are analyzed using this framework. Analytical and numerical computations of the RD and RDE functions are also presented. Finally, simulation results show that sets of erasure patterns designed using the proposed methods outperform other algorithms with the same number of decoding trials. [ABSTRACT FROM AUTHOR]

Models for noncoherent error control in random linear network coding (RLNC) and store and forward (SAF) have been recently proposed. In this paper, we model different types of random network communications as the transmission of flats of matroids. This novel framework encompasses RLNC and SAF and allows us to introduce a novel protocol, referred to as random affine network coding (RANC), based on affine combinations of packets. Although the models previously proposed for RLNC and SAF only consider error control, using our framework, we first evaluate and compare the performance of different network protocols in the error-free case. We define and determine the rate, average delay, and throughput of such protocols, and we also investigate the possibilities of partial decoding before the entire message is received. We thus show that RANC outperforms RLNC in terms of data rate and throughput thanks to a more efficient encoding of messages into packets. Second, we model the possible alterations of a message by the network as an operator channel, which generalizes the channels proposed for RLNC and SAF. Error control is thus reduced to a coding-theoretic problem on flats of a matroid, where two distinct metrics can be used for error correction. We study the maximum cardinality of codes on flats in general, and codes for error correction in RANC in particular. We finally design a class of nearly optimal codes for RANC based on rank metric codes for which we propose a low-complexity decoding algorithm. The gain of RANC over RLNC is thus preserved with no additional cost in terms of complexity. [ABSTRACT FROM AUTHOR]

Protograph-based LDPC and generalized LDPC (G-LDPC) codes have the advantages of a simple design procedure and highly structured encoders and decoders. The design of such “protograph-based codes” relies on what is effectively a computer-based search. As such, following Gallager, it is prudent to restrict the search to a “good ensemble,” for example, an ensemble whose minimum distance grows linearly with codeword length. A good ensemble can also mean one with good stopping set, trapping set, or pseudocodeword properties. In this paper, ensemble codeword weight enumerators for finite-length LDPC and G-LDPC codes based on protographs were derived, and then the asymptotic case was considered. The asymptotic results allow us to determine whether or not the typical relative minimum distance in the ensemble grows linearly with codeword length. Then, the codeword weight enumerator technique is adapted to yield ensemble stopping set, trapping set, and pseudocodeword enumerators for protograph LDPC and G-LDPC codes. In this case, the asymptotic results allow us to determine whether or not the typical relative smallest stopping set size, trapping set size, and pseudoweight grows linearly with codeword length. Trapping set enumerators for G-LDPC code ensembles represent a more complex problem which we do not consider here. [ABSTRACT FROM AUTHOR]

The error-pattern correcting code (EPCC) is a code designed to correct frequently observed error cluster patterns of the intersymbol interference (ISI) channel. This paper focuses on developing theoretical understanding of the performance of serial concatenation of the EPCC with an outer recursive systematic convolutional code (RSCC) in ISI channel environments. To analyze the performance of this EPCC-RSCC concatenation, an upper union bound on the maximum-likelihood (ML) bit-error rate (BER), averaged over all possible interleavers, is derived which offers crucial insights into the error floor behavior of the matching turbo decoder. The ML bound is also used to compare the performance of EPCC-RSCC to that of a stand-alone RSCC in serial concatenation to precoded and nonprecoded ISI channels. This comparison shows that by targeting the low Hamming-weight interleaved errors of the RSCC, which result in low Euclidean distance error events in the channel detector, EPCC-RSCC exhibits a much lower BER floor compared to conventional schemes, especially for high rate applications and short interleaver lengths. The error rate performance of an iterative suboptimal turbo equalizer (TE), called TE-EPCC, is also demonstrated to converge close to the ML bound at high SNR. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of recovering sparse or compressible signals from uniformly quantized measurements. We present a new class of convex optimization programs, or decoders, coined Basis Pursuit DeQuantizer of moment p (BPDQ_p), that model the quantization distortion more faithfully than the commonly used Basis Pursuit DeNoise (BPDN) program. Our decoders proceed by minimizing the sparsity of the signal to be reconstructed subject to a data-fidelity constraint expressed in the \ell_p-norm of the residual error for 2\leqslant p\leqslant \infty. [ABSTRACT FROM AUTHOR]

The problem of network coding for multicasting a single source to multiple sinks has first been studied by Ahlswede, Cai, Li, and Yeung in 2000, in which they have established the celebrated max-flow min-cut theorem on nonphysical information flow over a network of independent channels. On the other hand, in 1980, Han has studied the case with multiple correlated sources and a single sink from the viewpoint of polymatroidal functions in which a necessary and sufficient condition has been demonstrated for reliable transmission over the network. This paper presents an attempt to unify both cases, which leads to establish a necessary and sufficient condition for reliable transmission over a network for multicasting multiple correlated sources to multiple sinks. Here, the problem of separation of source coding and network coding is also discussed. [ABSTRACT FROM AUTHOR]

In this paper, the role of cooperation in managing interference—a fundamental feature of the wireless channel—is investigated by studying the two-user Gaussian interference channel where the source nodes can both transmit and receive in full duplex. The sum capacity of this channel is obtained within a gap of a constant number of bits. The coding scheme used builds up on the superposition scheme of Han and Kobayashi for the two-user interference channel without cooperation. New upperbounds on the sum capacity are also derived. The same coding scheme is shown to obtain the sum capacity of the symmetric two-user Gaussian interference channel with noiseless feedback within a constant gap. [ABSTRACT FROM AUTHOR]

In this paper, we consider scaling laws for maximal energy efficiency of communicating a message to all the nodes in a wireless network, as the number of nodes in the network becomes large. Two cases of large wireless networks are studied—dense random networks and constant density (extended) random networks. In addition, we also study finite size regular networks in order to understand how regularity in node placement affects energy consumption. We first establish an information-theoretic lower bound on the minimum energy per bit for multicasting in arbitrary wireless networks when the channel state information is not available at the transmitters. Upper bounds are obtained by constructing a simple flooding scheme that requires no information at the receivers about the channel states or the locations and identities of the nodes. The gap between the upper and lower bounds is only a constant factor for dense random networks and regular networks, and differs by a poly-logarithmic factor for extended random networks. Furthermore, we show that the proposed upper and lower bounds for random networks hold almost surely in the node locations as the number of nodes approaches infinity. [ABSTRACT FROM AUTHOR]

The Grassmannian space \cal Gq (n,k) is the set of all k-dimensional subspaces of the vector space \BBF q^{n}. Recently, codes in the Grassmannian have found an application in network coding. The main goal of this paper is to present efficient enumerative encoding and decoding techniques for the Grassmannian. These coding techniques are based on two different orders for the Grassmannian induced by different representations of k-dimensional subspaces of \BBF q^{n}. One enumerative coding method is based on a Ferrers diagram representation and on an order for \cal Gq (n,k) based on this representation. The complexity of this enumerative coding is O(k^5/2 (n-k)^5/2) digit operations. Another order of the Grassmannian is based on a combination of an identifying vector and a reduced row echelon form representation of subspaces. The complexity of the enumerative coding, based on this order, is O(nk(n-k)\log n\log \log n) digit operations. A combination of the two methods reduces the complexity on average by a constant factor. [ABSTRACT FROM AUTHOR]

In this paper, new sequences (\lambda ^n,\rho ^n) of capacity achieving low-density parity-check (LDPC) code ensembles over the binary erasure channel (BEC) is introduced. These sequences include the existing sequences by Shokrollahi as a special case. For a fixed code rate R, in the set of proposed sequences, Shokrollahi's sequences are superior to the rest of the set in that for any given value of n, their threshold is closer to the capacity upper bound 1- R. For any given \delta , 0 < \delta < 1-R, however, there are infinitely many sequences in the set that are superior to Shokrollahi's sequences in that for each of them, there exists an integer number n0, such that for any n > n0, the sequence (\lambda ^n,\rho ^n) requires a smaller maximum variable node degree as well as a smaller number of constituent variable node degrees to achieve a threshold within \delta -neighborhood of the capacity upper bound 1-R. Moreover, it is proven that the check-regular subset of the proposed sequences are asymptotically quasi-optimal, i.e., their decoding complexity increases only logarithmically with the relative increase of the threshold. A stronger result on asymptotic optimality of some of the proposed sequences is also established. [ABSTRACT FROM PUBLISHER]

We generalize the Gel'fand-Pinsker model to encompass the setup of a memoryless multiple-access channel (MAC). According to this setup, only one of the encoders knows the state of the channel (noncausally), which is also unknown to the receiver. Two independent messages are transmitted: a common message and a message transmitted by the informed encoder. We find explicit characterizations of the capacity region with both noncausal and causal state information. Further, we study the noise-free binary case, and we also apply the general formula to the Gaussian case with noncausal channel state information, under an individual power constraint as well as a sum power constraint. In this case, the capacity region is achievable by a generalized writing-on-dirty-paper scheme. [ABSTRACT FROM AUTHOR]

In this paper, we study basic properties of linear network error correction codes, their construction and error correction capability for various kinds of errors. Our discussion is restricted to the single-source multicast case. We define the minimum distance of a network error correction code. This plays the same role as it does in classical coding theory. We construct codes that can correct errors up to the full error correction capability specified by Singletons bound for network error correction codes recently established by Cai and Yeung. We propose, a decoding principle for network error correction codes, based on which we introduce two decoding algorithms and analyze their performance. We formulate the global kernel error correction problem and characterize the error correction capability of codes for this kind of error. [ABSTRACT FROM AUTHOR]

In multiple-input multiple-output (MIMO) systems, maximum-likelihood (ML) decoding is equivalent to finding the closest lattice point in an N-dimensional complex space. In general, this problem is known to be NP-hard. In this paper, a quasi-ML algorithm based on semi-definite programming (SDP) is proposed. We introduce several SDP relaxation models for MIMO systems, with increasing complexity. We use interior-point methods for solving the models and obtain a near-ML performance with polynomial computational complexity. Lattice basis reduction is applied to further reduce the computational complexity of solving these models. The proposed relaxation models are also used for soft output decoding in MIMO systems. [ABSTRACT FROM AUTHOR]

This paper discusses the Slepian-Wolf problem of distributed near-lossless compression of correlated sources. We introduce practical new tools for communicating at all rates in the achievable region. The technique employs a simple ‘source-splitting’ strategy that does not require common sources of randomness at the encoders and decoders. This approach allows for pipelined encoding and decoding so that the system operates with the complexity, of a single user encoder and decoder. Moreover, when this splitting approach is used in conjunction with iterative decoding methods, it produces a significant simplification of the decoding process. We demonstrate this approach for synthetically generated data. Finally, we consider the Slepian-Wolf problem when linear codes are used as syndrome-formers and consider a linear programming relaxation to maximum-likelihood (ML) sequence decoding. We note that the fractional vertices of the relaxed polytope compete with the optimal solution in a manner analogous to that observed when the ‘min-sum’ iterative decoding algorithm is applied. This relaxation exhibits the ML-certificate property: if an integral solution is found, it is the ML solution. For symmetric binary joint distributions, we show that selecting easily constructable ‘expander’-style low-density parity check codes (LDPCs) as syndrome-formers admits a positive error exponent and therefore provably good performance. [ABSTRACT FROM AUTHOR]

We consider a three-terminal state-dependent relay channel with the channel state available noncausally at only the source. Such a model may be of interest for node cooperation in the framework of cognition, i.e., collaborative signal transmission involving cognitive and noncognitive radios. We study the capacity of this communication model. One principal problem is caused by the relay's not knowing the channel state. For the discrete memoryless (DM) model, we establish two lower bounds and an upper bound on channel capacity. The first lower bound is obtained by a coding scheme in which the source describes the state of the channel to the relay and destination, which then exploit the gained description for a better communication of the source's information message. The coding scheme for the second lower bound remedies the relay's not knowing the states of the channel by first computing, at the source, the appropriate input that the relay would send had the relay known the states of the channel, and then transmitting this appropriate input to the relay. The relay simply guesses the sent input and sends it in the next block. The upper bound accounts for not knowing the state at the relay and destination. For the general Gaussian model, we derive lower bounds on the channel capacity by exploiting ideas in the spirit of those we use for the DM model; and we show that these bounds are optimal for small and large noise at the relay irrespective to the strength of the interference. Furthermore, we also consider a relay model with orthogonal channels from the source to the relay and from the source and relay to the destination in which the source input component that is heard by the relay does not depend on the channel states. We establish a better upper bound for both DM and Gaussian cases and we also characterize the capacity in a number of special cases. [ABSTRACT FROM PUBLISHER]

We correct two errors that appeared in the paper by Kaneko [ABSTRACT FROM PUBLISHER]