BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Henry D. Pfister

Henry D. Pfister appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Information Theorymath.ITMachine Learningeess.SPquant-ph

Catalog footprint

What is connected

41works
5topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

41 published item(s)

preprint2022arXiv

An Information-Theoretic Perspective on Successive Cancellation List Decoding and Polar Code Design

This work identifies information-theoretic quantities that are closely related to the required list size on average for successive cancellation list (SCL) decoding to implement maximum-likelihood decoding over general binary memoryless symmetric (BMS) channels. It also provides upper and lower bounds for these quantities that can be computed efficiently for very long codes. For the binary erasure channel (BEC), we provide a simple method to estimate the mean accurately via density evolution. The analysis shows how to modify, e.g., Reed-Muller codes, to improve the performance when practical list sizes, e.g., $L\in[8, 1024]$, are adopted. Exemplary constructions with block lengths $N\in\{128,512\}$ outperform polar codes of 5G over the binary-input additive white Gaussian noise channel. It is further shown that there is a concentration around the mean of the logarithm of the required list size for sufficiently large block lengths, over discrete-output BMS channels. We provide the probability mass functions (p.m.f.s) of this logarithm, over the BEC, for a sequence of the modified RM codes with an increasing block length via simulations, which illustrate that the p.m.f.s concentrate around the estimated mean.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Belief Propagation with Quantum Messages for Symmetric Classical-Quantum Channels

Belief propagation (BP) is a classical algorithm that approximates the marginal distribution associated with a factor graph by passing messages between adjacent nodes in the graph. It gained popularity in the 1990's as a powerful decoding algorithm for LDPC codes. In 2016, Renes introduced a belief propagation with quantum messages (BPQM) and described how it could be used to decode classical codes defined by tree factor graphs that are sent over the classical-quantum pure-state channel. In this work, we propose an extension of BPQM to general binary-input symmetric classical-quantum (BSCQ) channels based on the implementation of a symmetric "paired measurement". While this new paired-measurement BPQM (PMBPQM) approach is suboptimal in general, it provides a concrete BPQM decoder that can be implemented with local operations.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Reinforcement Learning with Neural Networks for Quantum Multiple Hypothesis Testing

Reinforcement learning with neural networks (RLNN) has recently demonstrated great promise for many problems, including some problems in quantum information theory. In this work, we apply RLNN to quantum hypothesis testing and determine the optimal measurement strategy for distinguishing between multiple quantum states $\{ ρ_{j} \}$ while minimizing the error probability. In the case where the candidate states correspond to a quantum system with many qubit subsystems, implementing the optimal measurement on the entire system is experimentally infeasible. We use RLNN to find locally-adaptive measurement strategies that are experimentally feasible, where only one quantum subsystem is measured in each round. We provide numerical results which demonstrate that RLNN successfully finds the optimal local approach, even for candidate states up to 20 subsystems. We additionally demonstrate that the RLNN strategy meets or exceeds the success probability for a modified locally greedy approach in each random trial. While the use of RLNN is highly successful for designing adaptive local measurement strategies, in general a significant gap can exist between the success probability of the optimal locally-adaptive measurement strategy and the optimal collective measurement. We build on previous work to provide a set of necessary and sufficient conditions for collective protocols to strictly outperform locally adaptive protocols. We also provide a new example which, to our knowledge, is the simplest known state set exhibiting a significant gap between local and collective protocols. This result raises interesting new questions about the gap between theoretically optimal measurement strategies and practically implementable measurement strategies.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Polar Codes for Channels with Insertions, Deletions, and Substitutions

This paper presents a coding scheme for an insertion deletion substitution channel. We extend a previous scheme for the deletion channel where polar codes are modified by adding "guard bands" between segments. In the new scheme, each guard band is comprised of a middle segment of '1' symbols, and left and right segments of '0' symbols. Our coding scheme allows for a regular hidden-Markov input distribution, and achieves the information rate between the input and corresponding output of such a distribution. Thus, we prove that our scheme can be used to efficiently achieve the capacity of the channel. The probability of error of our scheme decays exponentially in the cube-root of the block length.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Model-Based Machine Learning for Joint Digital Backpropagation and PMD Compensation

In this paper, we propose a model-based machine-learning approach for dual-polarization systems by parameterizing the split-step Fourier method for the Manakov-PMD equation. The resulting method combines hardware-friendly time-domain nonlinearity mitigation via the recently proposed learned digital backpropagation (LDBP) with distributed compensation of polarization-mode dispersion (PMD). We refer to the resulting approach as LDBP-PMD. We train LDBP-PMD on multiple PMD realizations and show that it converges within 1% of its peak dB performance after 428 training iterations on average, yielding a peak effective signal-to-noise ratio of only 0.30 dB below the PMD-free case. Similar to state-of-the-art lumped PMD compensation algorithms in practical systems, our approach does not assume any knowledge about the particular PMD realization along the link, nor any knowledge about the total accumulated PMD. This is a significant improvement compared to prior work on distributed PMD compensation, where knowledge about the accumulated PMD is typically assumed. We also compare different parameterization choices in terms of performance, complexity, and convergence behavior. Lastly, we demonstrate that the learned models can be successfully retrained after an abrupt change of the PMD realization along the fiber.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Polar Codes for the Deletion Channel: Weak and Strong Polarization

This paper presents the first proof of polarization for the deletion channel with a constant deletion rate and a regular hidden-Markov input distribution. A key part of this work involves representing the deletion channel using a trellis and describing the plus and minus polar-decoding operations on that trellis. In particular, the plus and minus operations can be seen as combining adjacent trellis stages to yield a new trellis with half as many stages. Using this viewpoint, we prove a weak polarization theorem for standard polar codes on the deletion channel. To achieve strong polarization, we modify this scheme by adding guard bands of repeated zeros between various parts of the codeword. This gives a scheme whose rate approaches the mutual information and whose probability of error decays exponentially in the cube-root of the block length. We conclude by showing that this scheme can achieve capacity on the deletion channel by proving that the capacity of the deletion channel can be achieved by a sequence of regular hidden-Markov input distributions.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Revisiting Efficient Multi-Step Nonlinearity Compensation with Machine Learning: An Experimental Demonstration

Efficient nonlinearity compensation in fiber-optic communication systems is considered a key element to go beyond the "capacity crunch''. One guiding principle for previous work on the design of practical nonlinearity compensation schemes is that fewer steps lead to better systems. In this paper, we challenge this assumption and show how to carefully design multi-step approaches that provide better performance--complexity trade-offs than their few-step counterparts. We consider the recently proposed learned digital backpropagation (LDBP) approach, where the linear steps in the split-step method are re-interpreted as general linear functions, similar to the weight matrices in a deep neural network. Our main contribution lies in an experimental demonstration of this approach for a 25 Gbaud single-channel optical transmission system. It is shown how LDBP can be integrated into a coherent receiver DSP chain and successfully trained in the presence of various hardware impairments. Our results show that LDBP with limited complexity can achieve better performance than standard DBP by using very short, but jointly optimized, finite-impulse response filters in each step. This paper also provides an overview of recently proposed extensions of LDBP and we comment on potentially interesting avenues for future work.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Successive Cancellation Inactivation Decoding for Modified Reed-Muller and eBCH Codes

A successive cancellation (SC) decoder with inactivations is proposed as an efficient implementation of SC list (SCL) decoding over the binary erasure channel. The proposed decoder assigns a dummy variable to an information bit whenever it is erased during SC decoding and continues with decoding. Inactivated bits are resolved using information gathered from decoding frozen bits. This decoder leverages the structure of the Hadamard matrix, but can be applied to any linear code by representing it as a polar code with dynamic frozen bits. SCL decoders are partially characterized using density evolution to compute the average number of inactivations required to achieve the maximum a-posteriori decoding performance. The proposed measure quantifies the performance vs. complexity trade-off and provides new insight into dynamics of the number of paths in SCL decoding. The technique is applied to analyze Reed-Muller (RM) codes with dynamic frozen bits. It is shown that these modified RM codes perform close to extended BCH codes.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A Single-Letter Upper Bound on the Feedback Capacity of Unifilar Finite-State Channels

An upper bound on the feedback capacity of unifilar finite-state channels (FSCs) is derived. A new technique, called the $Q$-contexts, is based on a construction of a directed graph that is used to quantize recursively the receiver's output sequences to a finite set of contexts. For any choice of $Q$-graph, the feedback capacity is bounded by a single-letter expression, $C_\text{fb}\leq \sup I(X,S;Y|Q)$, where the supremum is over $P_{X|S,Q}$ and the distribution of $(S,Q)$ is their stationary distribution. It is shown that the bound is tight for all unifilar FSCs where feedback capacity is known: channels where the state is a function of the outputs, the trapdoor channel, Ising channels, the no-consecutive-ones input-constrained erasure channel and for the memoryless channel. Its efficiency is also demonstrated by deriving a new capacity result for the dicode erasure channel (DEC); the upper bound is obtained directly from the above expression and its tightness is concluded with a general sufficient condition on the optimality of the upper bound. This sufficient condition is based on a fixed point principle of the BCJR equation and, indeed, formulated as a simple lower bound on feedback capacity of unifilar FSCs for arbitrary $Q$-graphs. This upper bound indicates that a single-letter expression might exist for the capacity of finite-state channels with or without feedback based on a construction of auxiliary random variable with specified structure, such as $Q$-graph, and not with i.i.d distribution. The upper bound also serves as a non-trivial bound on the capacity of channels without feedback, a problem that is still open.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Comparing the Bit-MAP and Block-MAP Decoding Thresholds of Reed-Muller Codes on BMS Channels

The question whether RM codes are capacity-achieving is a long-standing open problem in coding theory that was recently answered in the affirmative for transmission over erasure channels [1], [2]. Remarkably, the proof does not rely on specific properties of RM codes, apart from their symmetry. Indeed, the main technical result consists in showing that any sequence of linear codes, with doubly-transitive permutation groups, achieves capacity on the memoryless erasure channel under bit-MAP decoding. Thus, a natural question is what happens under block-MAP decoding. In [1], [2], by exploiting further symmetries of the code, the bit-MAP threshold was shown to be sharp enough so that the block erasure probability also converges to 0. However, this technique relies heavily on the fact that the transmission is over an erasure channel. We present an alternative approach to strengthen results regarding the bit-MAP threshold to block-MAP thresholds. This approach is based on a careful analysis of the weight distribution of RM codes. In particular, the flavor of the main result is the following: assume that the bit-MAP error probability decays as $N^{-δ}$, for some $δ>0$. Then, the block-MAP error probability also converges to 0. This technique applies to transmission over any binary memoryless symmetric channel. Thus, it can be thought of as a first step in extending the proof that RM codes are capacity-achieving to the general case.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Density Evolution for Deterministic Generalized Product Codes with Higher-Order Modulation

Generalized product codes (GPCs) are extensions of product codes (PCs) where coded bits are protected by two component codes but not necessarily arranged in a rectangular array. It has recently been shown that there exists a large class of deterministic GPCs (including, e.g., irregular PCs, half-product codes, staircase codes, and certain braided codes) for which the asymptotic performance under iterative bounded-distance decoding over the binary erasure channel (BEC) can be rigorously characterized in terms of a density evolution analysis. In this paper, the analysis is extended to the case where transmission takes place over parallel BECs with different erasure probabilities. We use this model to predict the code performance in a coded modulation setup with higher-order signal constellations. We also discuss the design of the bit mapper that determines the allocation of the coded bits to the modulation bits of the signal constellation.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Deterministic and Ensemble-Based Spatially-Coupled Product Codes

Several authors have proposed spatially-coupled (or convolutional-like) variants of product codes (PCs). In this paper, we focus on a parametrized family of generalized PCs that recovers some of these codes (e.g., staircase and block-wise braided codes) as special cases and study the iterative decoding performance over the binary erasure channel. Even though our code construction is deterministic (and not based on a randomized ensemble), we show that it is still possible to rigorously derive the density evolution (DE) equations that govern the asymptotic performance. The obtained DE equations are then compared to those for a related spatially-coupled PC ensemble. In particular, we show that there exists a family of (deterministic) braided codes that follows the same DE equation as the ensemble, for any spatial length and coupling width.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Reed-Muller Codes Achieve Capacity on Erasure Channels

We introduce a new approach to proving that a sequence of deterministic linear codes achieves capacity on an erasure channel under maximum a posteriori decoding. Rather than relying on the precise structure of the codes our method exploits code symmetry. In particular, the technique applies to any sequence of linear codes where the blocklengths are strictly increasing, the code rates converge, and the permutation group of each code is doubly transitive. In other words, we show that symmetry alone implies near-optimal performance. An important consequence of this result is that a sequence of Reed-Muller codes with increasing blocklength and converging rate achieves capacity. This possibility has been suggested previously in the literature but it has only been proven for cases where the limiting code rate is 0 or 1. Moreover, these results extend naturally to all affine-invariant codes and, thus, to extended primitive narrow-sense BCH codes. This also resolves, in the affirmative, the existence question for capacity-achieving sequences of binary cyclic codes. The primary tools used in the proof are the sharp threshold property for symmetric monotone boolean functions and the area theorem for extrinsic information transfer functions.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The Replica-Symmetric Prediction for Compressed Sensing with Gaussian Matrices is Exact

This paper considers the fundamental limit of compressed sensing for i.i.d. signal distributions and i.i.d. Gaussian measurement matrices. Its main contribution is a rigorous characterization of the asymptotic mutual information (MI) and minimum mean-square error (MMSE) in this setting. Under mild technical conditions, our results show that the limiting MI and MMSE are equal to the values predicted by the replica method from statistical physics. This resolves a well-known problem that has remained open for over a decade.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Reed-Muller Codes Achieve Capacity on Erasure Channels

This paper introduces a new approach to proving that a sequence of deterministic linear codes achieves capacity on an erasure channel under maximum a posteriori decoding. Rather than relying on the precise structure of the codes, this method requires only that the codes are highly symmetric. In particular, the technique applies to any sequence of linear codes where the blocklengths are strictly increasing, the code rates converge to a number between 0 and 1, and the permutation group of each code is doubly transitive. This also provides a rare example in information theory where symmetry alone implies near-optimal performance. An important consequence of this result is that a sequence of Reed-Muller codes with increasing blocklength achieves capacity if its code rate converges to a number between 0 and 1. This possibility has been suggested previously in the literature but it has only been proven for cases where the limiting code rate is 0 or 1. Moreover, these results extend naturally to affine-invariant codes and, thus, to all extended primitive narrow-sense BCH codes. The primary tools used in the proof are the sharp threshold property for monotone boolean functions and the area theorem for extrinsic information transfer functions.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A Simple Proof of Maxwell Saturation for Coupled Scalar Recursions

Low-density parity-check (LDPC) convolutional codes (or spatially-coupled codes) were recently shown to approach capacity on the binary erasure channel (BEC) and binary-input memoryless symmetric channels. The mechanism behind this spectacular performance is now called threshold saturation via spatial coupling. This new phenomenon is characterized by the belief-propagation threshold of the spatially-coupled ensemble increasing to an intrinsic noise threshold defined by the uncoupled system. In this paper, we present a simple proof of threshold saturation that applies to a wide class of coupled scalar recursions. Our approach is based on constructing potential functions for both the coupled and uncoupled recursions. Our results actually show that the fixed point of the coupled recursion is essentially determined by the minimum of the uncoupled potential function and we refer to this phenomenon as Maxwell saturation. A variety of examples are considered including the density-evolution equations for: irregular LDPC codes on the BEC, irregular low-density generator matrix codes on the BEC, a class of generalized LDPC codes with BCH component codes, the joint iterative decoding of LDPC codes on intersymbol-interference channels with erasure noise, and the compressed sensing of random vectors with i.i.d. components.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On the Performance of Short Block Codes over Finite-State Channels in the Rare-Transition Regime

As the mobile application landscape expands, wireless networks are tasked with supporting different connection profiles, including real-time traffic and delay-sensitive communications. Among many ensuing engineering challenges is the need to better understand the fundamental limits of forward error correction in non-asymptotic regimes. This article characterizes the performance of random block codes over finite-state channels and evaluates their queueing performance under maximum-likelihood decoding. In particular, classical results from information theory are revisited in the context of channels with rare transitions, and bounds on the probabilities of decoding failure are derived for random codes. This creates an analysis framework where channel dependencies within and across codewords are preserved. Such results are subsequently integrated into a queueing problem formulation. For instance, it is shown that, for random coding on the Gilbert-Elliott channel, the performance analysis based on upper bounds on error probability provides very good estimates of system performance and optimum code parameters. Overall, this study offers new insights about the impact of channel correlation on the performance of delay-aware, point-to-point communication links. It also provides novel guidelines on how to select code rates and block lengths for real-time traffic over wireless communication infrastructures.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Threshold Saturation for Spatially-Coupled LDPC and LDGM Codes on BMS Channels

Spatially-coupled low-density parity-check (LDPC) codes, which were first introduced as LDPC convolutional codes, have been shown to exhibit excellent performance under low-complexity belief-propagation decoding. This phenomenon is now termed threshold saturation via spatial coupling. Spatially-coupled codes have been successfully applied in numerous areas. In particular, it was proven that spatially-coupled regular LDPC codes universally achieve capacity over the class of binary memoryless symmetric (BMS) channels under belief-propagation decoding. Recently, potential functions have been used to simplify threshold saturation proofs for scalar and vector recursions. In this paper, potential functions are used to prove threshold saturation for irregular LDPC and low-density generator-matrix (LDGM) codes on BMS channels, extending the simplified proof technique to BMS channels. The corresponding potential functions are closely related to the average Bethe free entropy of the ensembles in the large-system limit. These functions also appear in statistical physics when the replica method is used to analyze optimal decoding.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A Proof of Threshold Saturation for Spatially-Coupled LDPC Codes on BMS Channels

Low-density parity-check (LDPC) convolutional codes have been shown to exhibit excellent performance under low-complexity belief-propagation decoding [1], [2]. This phenomenon is now termed threshold saturation via spatial coupling. The underlying principle behind this appears to be very general and spatially-coupled (SC) codes have been successfully applied in numerous areas. Recently, SC regular LDPC codes have been proven to achieve capacity universally, over the class of binary memoryless symmetric (BMS) channels, under belief-propagation decoding [3], [4]. In [5], [6], potential functions are used to prove that the BP threshold of SC irregular LDPC ensembles saturates, for the binary erasure channel, to the conjectured MAP threshold (known as the Maxwell threshold) of the underlying irregular ensembles. In this paper, that proof technique is generalized to BMS channels, thereby extending some results of [4] to irregular LDPC ensembles. We also believe that this approach can be expanded to cover a wide class of graphical models whose message-passing rules are associated with a Bethe free energy.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A Simple Proof of Threshold Saturation for Coupled Scalar Recursions

Low-density parity-check (LDPC) convolutional codes (or spatially-coupled codes) have been shown to approach capacity on the binary erasure channel (BEC) and binary-input memoryless symmetric channels. The mechanism behind this spectacular performance is the threshold saturation phenomenon, which is characterized by the belief-propagation threshold of the spatially-coupled ensemble increasing to an intrinsic noise threshold defined by the uncoupled system. In this paper, we present a simple proof of threshold saturation that applies to a broad class of coupled scalar recursions. The conditions of the theorem are verified for the density-evolution (DE) equations of irregular LDPC codes on the BEC, a class of generalized LDPC codes, and the joint iterative decoding of LDPC codes on intersymbol-interference channels with erasure noise. Our approach is based on potential functions and was motivated mainly by the ideas of Takeuchi et al. The resulting proof is surprisingly simple when compared to previous methods.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A Simple Proof of Threshold Saturation for Coupled Vector Recursions

Convolutional low-density parity-check (LDPC) codes (or spatially-coupled codes) have now been shown to achieve capacity on binary-input memoryless symmetric channels. The principle behind this surprising result is the threshold-saturation phenomenon, which is defined by the belief-propagation threshold of the spatially-coupled ensemble saturating to a fundamental threshold defined by the uncoupled system. Previously, the authors demonstrated that potential functions can be used to provide a simple proof of threshold saturation for coupled scalar recursions. In this paper, we present a simple proof of threshold saturation that applies to a wide class of coupled vector recursions. The conditions of the theorem are verified for the density-evolution equations of: (i) joint decoding of irregular LDPC codes for a Slepian-Wolf problem with erasures, (ii) joint decoding of irregular LDPC codes on an erasure multiple-access channel, and (iii) general protograph codes on the BEC. This proves threshold saturation for these systems.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Delay-Sensitive Communication over Fading Channel: Queueing Behavior and Code Parameter Selection

This article examines the queueing performance of communication systems that transmit encoded data over unreliable channels. A fading formulation suitable for wireless environments is considered where errors are caused by a discrete channel with correlated behavior over time. Random codes and BCH codes are employed as means to study the relationship between code-rate selection and the queueing performance of point-to-point data links. For carefully selected channel models and arrival processes, a tractable Markov structure composed of queue length and channel state is identified. This facilitates the analysis of the stationary behavior of the system, leading to evaluation criteria such as bounds on the probability of the queue exceeding a threshold. Specifically, this article focuses on system models with scalable arrival profiles, which are based on Poisson processes, and finite-state channels with memory. These assumptions permit the rigorous comparison of system performance for codes with arbitrary block lengths and code rates. Based on the resulting characterizations, it is possible to select the best code parameters for delay-sensitive applications over various channels. The methodology introduced herein offers a new perspective on the joint queueing-coding analysis of finitestate channels with memory, and it is supported by numerical simulations.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

First-Passage Time and Large-Deviation Analysis for Erasure Channels with Memory

This article considers the performance of digital communication systems transmitting messages over finite-state erasure channels with memory. Information bits are protected from channel erasures using error-correcting codes; successful receptions of codewords are acknowledged at the source through instantaneous feedback. The primary focus of this research is on delay-sensitive applications, codes with finite block lengths and, necessarily, non-vanishing probabilities of decoding failure. The contribution of this article is twofold. A methodology to compute the distribution of the time required to empty a buffer is introduced. Based on this distribution, the mean hitting time to an empty queue and delay-violation probabilities for specific thresholds can be computed explicitly. The proposed techniques apply to situations where the transmit buffer contains a predetermined number of information bits at the onset of the data transfer. Furthermore, as additional performance criteria, large deviation principles are obtained for the empirical mean service time and the average packet-transmission time associated with the communication process. This rigorous framework yields a pragmatic methodology to select code rate and block length for the communication unit as functions of the service requirements. Examples motivated by practical systems are provided to further illustrate the applicability of these techniques.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Code Design for the Noisy Slepian-Wolf Problem

We consider a noisy Slepian-Wolf problem where two correlated sources are separately encoded (using codes of fixed rate) and transmitted over two independent binary memoryless symmetric channels. The capacity of each channel is characterized by a single parameter which is not known at the transmitter. The goal is to design systems that retain near-optimal performance without channel knowledge at the transmitter. It was conjectured that it may be hard to design codes that perform well for symmetric channel conditions. In this work, we present a provable capacity-achieving sequence of LDGM ensembles for the erasure Slepian-Wolf problem with symmetric channel conditions. We also introduce a staggered structure which enables codes optimized for single user channels to perform well for symmetric channel conditions. We provide a generic framework for analyzing the performance of joint iterative decoding, using density evolution. Using differential evolution, we design punctured systematic LDPC codes to maximize the region of achievable channel conditions. The resulting codes are then staggered to further increase the region of achievable parameters. The main contribution of this paper is to demonstrate that properly designed irregular LDPC codes can perform well simultaneously over a wide range of channel parameters.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On the Iterative Decoding of High-Rate LDPC Codes With Applications in Compressed Sensing

This paper considers the performance of $(j,k)$-regular low-density parity-check (LDPC) codes with message-passing (MP) decoding algorithms in the high-rate regime. In particular, we derive the high-rate scaling law for MP decoding of LDPC codes on the binary erasure channel (BEC) and the $q$-ary symmetric channel ($q$-SC). For the BEC, the density evolution (DE) threshold of iterative decoding scales like $Θ(k^{-1})$ and the critical stopping ratio scales like $Θ(k^{-j/(j-2)})$. For the $q$-SC, the DE threshold of verification decoding depends on the details of the decoder and scales like $Θ(k^{-1})$ for one decoder. Using the fact that coding over large finite alphabets is very similar to coding over the real numbers, the analysis of verification decoding is also extended to the the compressed sensing (CS) of strictly-sparse signals. A DE based approach is used to analyze the CS systems with randomized-reconstruction guarantees. This leads to the result that strictly-sparse signals can be reconstructed efficiently with high-probability using a constant oversampling ratio (i.e., when the number of measurements scales linearly with the sparsity of the signal). A stopping-set based approach is also used to get stronger (e.g., uniform-in-probability) reconstruction guarantees.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

An Iterative Joint Linear-Programming Decoding of LDPC Codes and Finite-State Channels

In this paper, we introduce an efficient iterative solver for the joint linear-programming (LP) decoding of low-density parity-check (LDPC) codes and finite-state channels (FSCs). In particular, we extend the approach of iterative approximate LP decoding, proposed by Vontobel and Koetter and explored by Burshtein, to this problem. By taking advantage of the dual-domain structure of the joint decoding LP, we obtain a convergent iterative algorithm for joint LP decoding whose structure is similar to BCJR-based turbo equalization (TE). The result is a joint iterative decoder whose complexity is similar to TE but whose performance is similar to joint LP decoding. The main advantage of this decoder is that it appears to provide the predictability of joint LP decoding and superior performance with the computational complexity of TE.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Analysis of Verification-based Decoding on the q-ary Symmetric Channel for Large q

We discuss and analyze a list-message-passing decoder with verification for low-density parity-check (LDPC) codes on the q-ary symmetric channel (q-SC). Rather than passing messages consisting of symbol probabilities, this decoder passes lists of possible symbols and marks some lists as verified. The density evolution (DE) equations for this decoder are derived and used to compute decoding thresholds. If the maximum list size is unbounded, then we find that any capacity-achieving LDPC code for the binary erasure channel can be used to achieve capacity on the q-SC for large q. The decoding thresholds are also computed via DE for the case where each list is truncated to satisfy a maximum list size constraint. Simulation results are also presented to confirm the DE results. During the simulations, we observed differences between two verification-based decoding algorithms, introduced by Luby and Mitzenmacher, that were implicitly assumed to be identical. In this paper, we provide an analysis of the node-based algorithms from that paper and verify that it matches simulation results. The probability of false verification (FV) is also considered and techniques are discussed to mitigate the FV. Optimization of the degree distribution is also used to improve the threshold for a fixed maximum list size. Finally, the proposed algorithm is compared with a variety of other algorithms using both density evolution thresholds and simulation results.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Convergence of Weighted Min-Sum Decoding Via Dynamic Programming on Trees

Applying the max-product (and belief-propagation) algorithms to loopy graphs is now quite popular for best assignment problems. This is largely due to their low computational complexity and impressive performance in practice. Still, there is no general understanding of the conditions required for convergence and/or the optimality of converged solutions. This paper presents an analysis of both attenuated max-product (AMP) decoding and weighted min-sum (WMS) decoding for LDPC codes which guarantees convergence to a fixed point when a weight parameter, β, is sufficiently small. It also shows that, if the fixed point satisfies some consistency conditions, then it must be both the linear-programming (LP) and maximum-likelihood (ML) solution. For (dv,dc)-regular LDPC codes, the weight must satisfy β(dv-1) \leq 1 whereas the results proposed by Frey and Koetter require instead that β(dv-1)(dc-1) < 1. A counterexample which shows a fixed point might not be the ML solution if β(dv-1) > 1 is also given. Finally, connections are explored with recent work by Arora et al. on the threshold of LP decoding.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Joint Decoding of LDPC Codes and Finite-State Channels via Linear-Programming

This paper considers the joint-decoding (JD) problem for finite-state channels (FSCs) and low-density parity-check (LDPC) codes. In the first part, the linear-programming (LP) decoder for binary linear codes is extended to JD of binary-input FSCs. In particular, we provide a rigorous definition of LP joint-decoding pseudo-codewords (JD-PCWs) that enables evaluation of the pairwise error probability between codewords and JD-PCWs in AWGN. This leads naturally to a provable upper bound on decoder failure probability. If the channel is a finite-state intersymbol interference channel, then the joint LP decoder also has the maximum-likelihood (ML) certificate property and all integer-valued solutions are codewords. In this case, the performance loss relative to ML decoding can be explained completely by fractional-valued JD-PCWs. After deriving these results, we discovered some elements were equivalent to earlier work by Flanagan on LP receivers. In the second part, we develop an efficient iterative solver for the joint LP decoder discussed in the first part. In particular, we extend the approach of iterative approximate LP decoding, proposed by Vontobel and Koetter and analyzed by Burshtein, to this problem. By taking advantage of the dual-domain structure of the JD-LP, we obtain a convergent iterative algorithm for joint LP decoding whose structure is similar to BCJR-based turbo equalization (TE). The result is a joint iterative decoder whose per-iteration complexity is similar to that of TE but whose performance is similar to that of joint LP decoding. The main advantage of this decoder is that it appears to provide the predictability of joint LP decoding and superior performance with the computational complexity of TE. One expected application is coding for magnetic storage where the required block-error rate is extremely low and system performance is difficult to verify by simulation.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Spatially-Coupled Codes and Threshold Saturation on Intersymbol-Interference Channels

Recently, it has been observed that terminated low-density-parity-check (LDPC) convolutional codes (or spatially-coupled codes) appear to approach capacity universally across the class of binary memoryless channels. This is facilitated by the "threshold saturation" effect whereby the belief-propagation (BP) threshold of the spatially-coupled ensemble is boosted to the maximum a-posteriori (MAP) threshold of the underlying constituent ensemble. In this paper, we consider the universality of spatially-coupled codes over intersymbol-interference (ISI) channels under joint iterative decoding. More specifically, we empirically show that threshold saturation also occurs for the considered problem. This can be observed by first identifying the EXIT curve for erasure noise and the GEXIT curve for general noise that naturally obey the general area theorem. From these curves, the corresponding MAP and the BP thresholds are then numerically obtained. With the fact that regular LDPC codes can achieve the symmetric information rate (SIR) under MAP decoding, spatially-coupled codes with joint iterative decoding can universally approach the SIR of ISI channels. For the dicode erasure channel, Kudekar and Kasai recently reported very similar results based on EXIT-like curves.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Universal Codes for the Gaussian MAC via Spatial Coupling

We consider transmission of two independent and separately encoded sources over a two-user binary-input Gaussian multiple-access channel. The channel gains are assumed to be unknown at the transmitter and the goal is to design an encoder-decoder pair that achieves reliable communication for all channel gains where this is theoretically possible. We call such a system \emph{universal} with respect to the channel gains. Kudekar et al. recently showed that terminated low-density parity-check convolutional codes (a.k.a. spatially-coupled low-density parity-check ensembles) have belief-propagation thresholds that approach their maximum a-posteriori thresholds. This was proven for binary erasure channels and shown empirically for binary memoryless symmetric channels. It was conjectured that the principle of spatial coupling is very general and the phenomenon of threshold saturation applies to a very broad class of graphical models. In this work, we derive an area theorem for the joint decoder and empirically show that threshold saturation occurs for this problem. As a result, we demonstrate near-universal performance for this problem using the proposed spatially-coupled coding system.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Universality for the Noisy Slepian-Wolf Problem Via Spatial Coupling

We consider a noisy Slepian-Wolf problem where two correlated sources are separately encoded and transmitted over two independent binary memoryless symmetric channels. Each channel capacity is assumed to be characterized by a single parameter which is not known at the transmitter. The receiver has knowledge of both the source correlation and the channel parameters. We call a system universal if it retains near-capacity performance without channel knowledge at the transmitter. Kudekar et al. recently showed that terminated low-density parity-check (LDPC) convolutional codes (a.k.a. spatially-coupled LDPC ensembles) can have belief-propagation thresholds that approach their maximum a-posteriori thresholds. This was proven for binary erasure channels and shown empirically for binary memoryless symmetric channels. They also conjectured that the principle of spatial coupling is very general and the phenomenon of threshold saturation applies to a very broad class of graphical models. In this work, we derive an area theorem for the joint decoder and empirically show that threshold saturation occurs for this problem. As a result, we demonstrate near-universal performance for this problem using the proposed spatially-coupled coding system. A similar result is also discussed briefly for the 2-user multiple-access channel.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

A Rate-Distortion Exponent Approach to Multiple Decoding Attempts for Reed-Solomon Codes

Algorithms based on multiple decoding attempts of Reed-Solomon (RS) codes have recently attracted new attention. Choosing decoding candidates based on rate-distortion (R-D) theory, as proposed previously by the authors, currently provides the best performance-versus-complexity trade-off. In this paper, an analysis based on the rate-distortion exponent (RDE) is used to directly minimize the exponential decay rate of the error probability. This enables rigorous bounds on the error probability for finite-length RS codes and leads to modest performance gains. As a byproduct, a numerical method is derived that computes the rate-distortion exponent for independent non-identical sources. Analytical results are given for errors/erasures decoding.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

IMP: A Message-Passing Algorithmfor Matrix Completion

A new message-passing (MP) method is considered for the matrix completion problem associated with recommender systems. We attack the problem using a (generative) factor graph model that is related to a probabilistic low-rank matrix factorization. Based on the model, we propose a new algorithm, termed IMP, for the recovery of a data matrix from incomplete observations. The algorithm is based on a clustering followed by inference via MP (IMP). The algorithm is compared with a number of other matrix completion algorithms on real collaborative filtering (e.g., Netflix) data matrices. Our results show that, while many methods perform similarly with a large number of revealed entries, the IMP algorithm outperforms all others when the fraction of observed entries is small. This is helpful because it reduces the well-known cold-start problem associated with collaborative filtering (CF) systems in practice.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

LDPC Code Design for Transmission of Correlated Sources Across Noisy Channels Without CSIT

We consider the problem of transmitting correlated data after independent encoding to a central receiver through orthogonal channels. We assume that the channel state information is not known at the transmitter. The receiver has access to both the source correlation and the channel state information. We provide a generic framework for analyzing the performance of joint iterative decoding, using density evolution. Using differential evolution, we design punctured systematic LDPC codes to maximize the region of achievable channel conditions, with joint iterative decoding. The main contribution of this paper is to demonstrate that properly designed LDPC can perform well simultaneously over a wide range of channel parameters.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Message-Passing Inference on a Factor Graph for Collaborative Filtering

This paper introduces a novel message-passing (MP) framework for the collaborative filtering (CF) problem associated with recommender systems. We model the movie-rating prediction problem popularized by the Netflix Prize, using a probabilistic factor graph model and study the model by deriving generalization error bounds in terms of the training error. Based on the model, we develop a new MP algorithm, termed IMP, for learning the model. To show superiority of the IMP algorithm, we compare it with the closely related expectation-maximization (EM) based algorithm and a number of other matrix completion algorithms. Our simulation results on Netflix data show that, while the methods perform similarly with large amounts of data, the IMP algorithm is superior for small amounts of data. This improves the cold-start problem of the CF systems in practice. Another advantage of the IMP algorithm is that it can be analyzed using the technique of density evolution (DE) that was originally developed for MP decoding of error-correcting codes.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

On Multiple Decoding Attempts for Reed-Solomon Codes: A Rate-Distortion Approach

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 which can be solved asymptotically by rate-distortion theory. Thus, the proposed approach can be used to understand the asymptotic performance-versus-complexity trade-off 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.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

On the Joint Decoding of LDPC Codes and Finite-State Channels via Linear Programming

In this paper, the linear programming (LP) decoder for binary linear codes, introduced by Feldman, et al. is extended to joint-decoding of binary-input finite-state channels. In particular, we provide a rigorous definition of LP joint-decoding pseudo-codewords (JD-PCWs) that enables evaluation of the pairwise error probability between codewords and JD-PCWs. This leads naturally to a provable upper bound on decoder failure probability. If the channel is a finite-state intersymbol interference channel, then the LP joint decoder also has the maximum-likelihood (ML) certificate property and all integer valued solutions are codewords. In this case, the performance loss relative to ML decoding can be explained completely by fractional valued JD-PCWs.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

The Capacity of Finite-State Channels in the High-Noise Regime

This paper considers the derivative of the entropy rate of a hidden Markov process with respect to the observation probabilities. The main result is a compact formula for the derivative that can be evaluated easily using Monte Carlo methods. It is applied to the problem of computing the capacity of a finite-state channel (FSC) and, in the high-noise regime, the formula has a simple closed-form expression that enables series expansion of the capacity of a FSC. This expansion is evaluated for a binary-symmetric channel under a (0,1) run-length limited constraint and an intersymbol-interference channel with Gaussian noise.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

The Effect of Spatial Coupling on Compressive Sensing

Recently, it was observed that spatially-coupled LDPC code ensembles approach the Shannon capacity for a class of binary-input memoryless symmetric (BMS) channels. The fundamental reason for this was attributed to a "threshold saturation" phenomena derived by Kudekar, Richardson and Urbanke. In particular, it was shown that the belief propagation (BP) threshold of the spatially coupled codes is equal to the maximum a posteriori (MAP) decoding threshold of the underlying constituent codes. In this sense, the BP threshold is saturated to its maximum value. Moreover, it has been empirically observed that the same phenomena also occurs when transmitting over more general classes of BMS channels. In this paper, we show that the effect of spatial coupling is not restricted to the realm of channel coding. The effect of coupling also manifests itself in compressed sensing. Specifically, we show that spatially-coupled measurement matrices have an improved sparsity to sampling threshold for reconstruction algorithms based on verification decoding. For BP-based reconstruction algorithms, this phenomenon is also tested empirically via simulation. At the block lengths accessible via simulation, the effect is quite small and it seems that spatial coupling is not providing the gains one might expect. Based on the threshold analysis, however, we believe this warrants further study.

0 citations0 reviewsNo code linkedOpen access