We consider the permanent of a square matrix with non-negative entries. A tractable approximation is given by the so-called Bethe permanent that can be efficiently computed by running the sum-product algorithm on a suitable factor graph. While the ratio of the permanent of a matrix to its Bethe permanent is, in the worst case, upper and lower bounded by expressions that are exponentially far apart in the matrix size, in practice it is observed for many ensembles of matrices of interest that this ratio is strongly concentrated around some value that depends only on the matrix size. In this paper, for an ensemble of block-structured matrices where entries in a block take the same value, we numerically study the ratio of the permanent of a matrix to its Bethe permanent. It is observed that also for this ensemble the ratio is strongly concentrated around some value depending only on a few key parameters of the ensemble. We use graph-cover-based approaches to explain the reasons for this behavior and to quantify the observed value.

Approximating the permanent of a complex-valued matrix is a fundamental problem with applications in Boson sampling and probabilistic inference. In this paper, we extend factor-graph-based methods for approximating the permanent of non-negative-real-valued matrices that are based on running the sum-product algorithm (SPA) on standard normal factor graphs, to factor-graph-based methods for approximating the permanent of complex-valued matrices that are based on running the SPA on double-edge normal factor graphs. On the algorithmic side, we investigate the behavior of the SPA, in particular how the SPA fixed points change when transitioning from real-valued to complex-valued matrix ensembles. On the analytical side, we use graph covers to analyze the Bethe approximation of the permanent, i.e., the approximation of the permanent that is obtained with the help of the SPA. This combined algorithmic and analytical perspective provides new insight into the structure of Bethe approximations in complex-valued problems and clarifies when such approximations remain meaningful beyond the non-negative-real-valued settings.

For various classes of graphical models it has been observed that the ratio of the partition sum to its Bethe approximation is often close to being the square of the ratio of the partition sum to its degree-2 Bethe approximation. This is of relevance because the latter ratio can often better be analyzed and/or quantified than the former ratio. In this paper, we give some justifications for the observed relationship between these two ratios and then analyze these ratios for two classes of log-supermodular graphical models.

Various computational problems can be reduced to computing the marginals and the partition function of a suitably defined standard factor graph (S-FG). The sum-product algorithm (SPA) is an efficient iterative method for approximating these quantities, resulting in the so-called Bethe approximation of these quantities. In previous work, Vontobel proved that for an S-FG whose partition function equals the permanent of a nonnegative square matrix, the Bethe free energy function associated with the S-FG is a convex function and the SPA efficiently finds the minimum of the Bethe free energy function, from which the Bethe approximation of the permanent can be computed. We extend Vontobel's results by considering a class of bipartite S-FGs where each local function is defined based on a (possibly different) multi-affine homogeneous real stable polynomial. This class of S-FGs covers various combinatorial problems, including computing a generalization of the matrix permanent and determining the number of binary contingency tables with prescribed marginals. Results by Straszak and Vishnoi for a slightly larger class of S-FGs (they do not assume homogeneity of the polynomials) show that these S-FGs have the property that the Bethe partition function lower bounds the partition function. In this paper we prove, with the help of results for real stable polynomials and results from matroid theory, various statements for the class of S-FGs under consideration: we show that a certain projection of the local marginal polytope equals the convex hull of the set of valid configurations, that the Bethe free energy function possesses some convexity properties, and, for the typical case where the S-FG has an SPA fixed point consisting of positive-valued messages only, that the SPA finds the value of the Bethe partition function exponentially fast.

The permanent of a non-negative square matrix can be well approximated by finding the minimum of the Bethe free energy function associated with some suitably defined factor graph; the resulting approximation to the permanent is called the Bethe permanent. Vontobel gave a combinatorial characterization of the Bethe permanent via degree-MBethe permanents, which is based on degree-Mcovers of the underlying factor graph. In this paper, we prove a degree-M-Bethe-permanent-based lower bound on the permanent of a non-negative matrix, which solves a conjecture proposed by Vontobel in [IEEE Trans. Inf. Theory, Mar. 2013]. We also prove a degree-M-Bethe-permanent-based upper bound on the permanent of a non-negative matrix. In the limitM→ ∞, these lower and upper bounds yield known Bethe-permanent-based lower and upper bounds on the permanent of a non-negative matrix. Moreover, we prove similar results for an approximation to the permanent known as the (scaled) Sinkhorn permanent.

The permanent of a non-negative square matrix can be well approximated by finding the minimum of the Bethe free energy functions associated with some suitably defined factor graph; the resulting approximation to the permanent is called the Bethe permanent. Vontobel gave a combinatorial characterization of the Bethe permanent via degree-M Bethe permanents, which is based on degree-M covers of the underlying factor graph.In this paper, we prove a degree- M-Bethe-permanent-based lower bound on the permanent of a non-negative matrix, which solves a conjecture proposed by Vontobel in [IEEE Trans. Inf. Theory, Mar. 2013]. We also prove a degree- M-Bethe-permanent-based upper bound on the permanent of a non-negative matrix. In the limit $M \to \infty$, these lower and upper bounds yield known Bethe-permanent-based lower and upper bounds on the permanent of a non-negative matrix. Moreover, we prove similar results for an approximation to the permanent known as the (scaled) Sinkhorn permanent.

We consider reliable and secure communication over intersymbol interference wiretap channels (ISI-WTCs). In particular, we first derive an achievable secure rate for ISI-WTCs without imposing any constraints on the input distribution. Afterwards, we focus on the setup where the input distribution of the ISI-WTC is constrained to be a time-invariant finite-order Markov chain. Optimizing the parameters of this Markov chain toward maximizing the achievable secure rates is a computationally intractable problem in general, and so, toward finding a local maximum, we propose an iterative algorithm that at every iteration replaces the secure rate function with a suitable surrogate function whose maximum can be found efficiently. Although the secure rates achieved in the unconstrained setup are potentially larger than the secure rates achieved in the constrained setup, the latter setup has the advantage of leading to efficient algorithms for estimating and optimizing the achievable secure rates, and also has the benefit of being the basis of efficient coding schemes.

We consider sparse regression codes (SPARCs) for the multiple-input multiple-output (MIMO) detection problem. Specifically, we introduce normals with unknown variances (NUV) priors to represent one-hot vectors in SPARCs and derive the corresponding NUV-EM algorithm accordingly. Then, we apply this algorithm to MIMO detection problems. In order to tackle issues arising from the proposed NUV-EM algorithm, a (Hadamard-based) Gaussian generalized approximate message passing (GAMP) algorithm, along with a simple rejection technique, is proposed. Simulation results show that our proposed algorithms work well over various channels.

The sum-product algorithm (SPA) is a popular algorithm for efficiently approximating the marginals and the partition function of a factor graph. Some key results for this algorithm were established by Yedidia et al., who proved that, roughly speaking, fixed points of the SPA correspond to stationary points of the Bethe free energy function. However, some of their results were only for factor graphs where the local functions take on strictly positive values. They also conjectured that similar results hold for factor graphs where the local functions take on non-negative values. In this paper we make progress toward resolving this conjecture. In particular, we present examples where the results of Yedidia et al. generalize and examples where their results do not generalize. Finally, we present a general framework for analyzing fixed-points of the SPA based on a suitable dualization of the Bethe free energy function.

The permanent of a non-negative matrix appears naturally in many information processing scenarios. Because of the intractability of the permanent beyond small matrices, various approximation techniques have been developed in the past. In this paper, we study the Bethe approximation of the permanent and add to the body of literature showing that this approximation is very well behaved in many respects. Our main technical tool are topological double covers of the normal factor graph whose partition function equals the permanent of interest, along with a transformation of these double covers.

Quantum mass functions (QMFs), which are tightly related to decoherence functionals, were introduced by Loeliger and Vontobel [IEEE Trans. Inf. Theory, 2017, 2020] as a generalization of probability mass functions toward modeling quantum information processing setups in terms of factor graphs. Simple quantum mass functions (SQMFs) are a special class of QMFs that do not explicitly model classical random variables. Nevertheless, classical random variables appear implicitly in an SQMF if some marginals of the SQMF satisfy some conditions; variables of the SQMF corresponding to these “emerging” random variables are called classicable variables. Of particular interest are jointly classicable variables. In this paper we initiate the characterization of the set of marginals given by the collection of jointly classicable variables of a graphical model and compare them with other concepts associated with graphical models like the sets of realizable marginals and the local marginal polytope. In order to further characterize this set of marginals given by the collection of jointly classicable variables, we generalize the CHSH inequality based on the Pearson correlation coefficients, and thereby prove a conjecture proposed by Pozsgay et al. A crucial feature of this inequality is its nonlinearity, which poses difficulties in the proof.

In previous work, we have shown that pseudocodewords can be used to characterize the behavior of decoders not only for classical codes but also for quantum stabilizer codes. With the insights obtained from this pseudocodewords-based analysis, we have also introduced a two-stage decoder based on pseudocodewords for quantum cycle codes that leads to improved decoding performance. In this paper, we consider quantum (stabilizer) color codes and propose a two-stage decoder that is a generalization of the pseudocodeword-based decoder for quantum cycle codes. Our decoder has local operations w.r.t. the underlying graphs, syndrome-weight-dependent computational complexity, and better decoding performance compared with previous approaches for quantum color codes.

We consider reliable and secure communication over intersymbol interference wiretap channels (ISI-WTCs). In particular, we first examine the setup where the source at the input of an ISI-WTC is unconstrained and then, based on a general achievability result for arbitrary wiretap channels, we derive an achievable secure rate for this ISI-WTC. Afterwards, we examine the setup where the source at the input of an ISI-WTC is constrained to be a finite-state machine source (FSMS) of a certain order and structure. optimizing the parameters of this FSMS toward maximizing the secure rate is a computationally intractable problem in general, and so, toward finding a local maximum, we propose an iterative algorithm that at every iteration replaces the secure rate function by a suitable surrogate function whose maximum can be found efficiently.

We consider sparse regression codes (SPARCs) over complex AWGN channels. Such codes can be efficiently decoded by an approximate message passing (AMP) decoder, whose performance can be predicted via so-called state evolution in the large-system limit. In this paper, we mainly focus on how to use concatenation of SPARCs and cyclic redundancy check (CRC) codes on the encoding side and use list decoding on the decoding side to improve the finite-length performance of the AMP decoder for SPARCs over complex AWGN channels. Simulation results show that such a concatenated coding scheme works much better than SPARCs with the original AMP decoder and results in a steep waterfall-like behavior in the bit-error rate performance curves. Furthermore, we apply our proposed concatenated coding scheme to spatially coupled SPARCs. Besides that, we also introduce a novel class of design matrices, i.e., matrices that describe the encoding process, based on circulant matrices derived from Frank or from Milewski sequences. This class of design matrices has comparable encoding and decoding computational complexity as well as very close performance with the commonly-used class of design matrices based on discrete Fourier transform (DFT) matrices, but gives us more degrees of freedom when designing SPARCs for various applications.

For standard factor graphs (S-FGs), i.e., factor graphs with local functions taking on non-negative real values, Vontobel gave a characterization of the Bethe approximation to the partition function in terms of the partition function of finite graph covers. The proof of that statement heavily relied on the method of types. In this paper we give a similar characterization for so-called double-edge factor graphs (DE-FGs), which are a class of factor graphs where local functions take on complex values and have to satisfy some positive semi-definiteness constraints. Such factor graphs are of interest in quantum information processing. In general, approximating the partition function of DE-FGs is more challenging than for S-FGs because the partition function is a sum of complex values and not just a sum of non-negative real values. In particular, for proving the above-mentioned characterization of the Bethe approximation in terms of finite graph covers, one cannot use the method of types anymore. We overcome this challenge by applying the loop-calculus transform by Chertkov and Chernyak, along with using the symmetricsubspace transform, a novel technique for factor graphs that should be of interest beyond proving the main result of this paper. Currently, the characterization of the Bethe approximation of the partition function of DE-FGs is for DE-FGs satisfying an (easily checkable) condition. However, based on numerical results, we suspect that the characterization holds more broadly.

We consider sparse superposition codes (SPARCs) over complex AWGN channels. Such codes can be efficiently decoded by an approximate message passing (AMP) decoder, whose performance can be predicted via so-called state evolution in the large-system limit. In this paper, we mainly focus on how to use concatenation of SPARCs and cyclic redundancy check (CRC) codes on the encoding side and use list decoding on the decoding side to improve the finite-length performance of the AMP decoder for SPARCs over complex AWGN channels. Simulation results show that such a concatenated coding scheme works much better than SPARCs with the original AMP decoder and results in a steep waterfall-like behavior in the bit-error rate performance curves.

We consider the scenario of classical communication over a finite-dimensional quantum channel with memory using a separable-state input ensemble and local output measurements. We propose algorithms for estimating the information rate of such communication setups, along with algorithms for bounding the information rate based on so-called auxiliary channels. Some of the algorithms are extensions of their counterparts for (classical) finite-state-machine channels. Notably, we discuss suitable graphical models for doing the relevant computations. Moreover, the auxiliary channels are learned in a data-driven approach; i.e., only input/output sequences of the true channel are needed, but not the channel model of the true channel.

In prior work, we have shown how the basic concepts and terms of quantum mechanics relate to factorizations and marginals of complex-valued quantum mass functions, which are generalizations of joint probability mass functions. In this paper, using quantum mass functions, we discuss the realization of measurements in terms of unitary interactions and marginalizations. It follows that classical measurement results strictly belong to local models, i.e., marginals of more detailed models. Classical variables that are created by marginalization do not exist in the unmarginalized model, and different marginalizations may yield incompatible classical variables. These observations are illustrated by the Frauchiger-Renner paradox, which is analyzed (and resolved) in terms of quantum mass functions. Throughout, the paper uses factor graphs to represent quantum systems/models with multiple measurements at different points in time.

We are interested in classical communication over a quantum channel with memory, in particular, we are interested in quantum-auxiliary-channel-based upper and lower bounds on the information rate. Toward improving these bounds, we propose efficient algorithms for optimizing the auxiliary channel. From a practical perspective, the lower bounds are of significant interest because they represent mismatched information rates, i.e., information rates that are achievable by a communication system where the decoder is matched to the auxiliary channel, instead of the original channel. Moreover, the auxiliary channels are learned in a data-driven approach, i.e., only input/output sequences of the true channel are needed, but not the channel model of the true channel.

It has been shown that graph-cover pseudocodewords can be used to characterize the behavior of sum-product algorithm (SPA) decoding of classical codes. In this paper, we leverage and adapt these results to analyze SPA decoding of quantum stabilizer codes. We use the obtained insights to formulate modifications to the SPA that overcome some of its weaknesses.

Coded computation is an emerging research area that leverages concepts from erasure coding to mitigate the effect of stragglers (slow nodes) in distributed computation clusters, especially for matrix computation problems. In this work, we present a class of distributed matrix-vector multiplication schemes that are based on codes in the Rosenbloom-Tsfasman metric and universally decodable matrices. Our schemes take into account the inherent computation order within a worker node. In particular, they allow us to effectively leverage partial computations performed by stragglers (a feature that many prior works lack). An additional main contribution of our work is a companion-matrix-based embedding of these codes that allows us to obtain sparse and numerically stable schemes for the problem at hand. Experimental results confirm the effectiveness of our techniques.

Linear programming (LP) decoding is an approach for decoding classical codes, especially for decoding low-density parity-check codes. In this paper, we initiate the study of LP decoding for stabilizer quantum error-correction codes. In particular, we formulate different polytope relaxations, we introduce pseudoweights to analyze the effect of pseudocodewords, and we give theoretical guarantees of the decoding ability of the LP decoder for the quantum depolarizing channel and for the quantum erasure channel.

Algebraic topology studies topological spaces with the help of tools from abstract algebra. The main focus of this paper is to show that many concepts from algebraic topology can be conveniently expressed in terms of (normal) factor graphs. As an application, we give an alternative proof of a classical duality result of Kramers and Wannier, which expresses the partition function of the 2-D Ising model at a low temperature in terms of the partition function of the 2-D Ising model at a high temperature. Moreover, we discuss analogous results for the 3-D Ising model and the Potts model.

We consider the problem of transmitting classical information over a time-invariant channel with memory. A popular class of time-invariant channels with memory are finite-state-machine channels, where a classical state evolves over time and governs the relationship between the classical input and the classical output of the channel. For such channels, various techniques have been developed for estimating and bounding the information rate. In this paper we consider a class of time-invariant channels where a quantum state evolves over time and governs the relationship between the classical input and the classical output of the channel. We propose algorithms for estimating and bounding the information rate of such channels. In particular, we discuss suitable graphical models for doing the relevant computations.

Some of the most interesting quantities associated with a factor graph are its marginals and its partition sum. For factor graphs without cycles and moderate message-update complexities, the sum-product algorithm (SPA) can be used to efficiently compute these quantities exactly. Moreover, for various classes of factor graphs with cycles, the SPA has been successfully applied to efficiently compute good approximations to these quantities. Note that in the case of factor graphs with cycles, the local functions are usually non-negative real-valued functions. In this paper we introduce a class of factor graphs, called double-edge factor graphs (DE-FGs), which allow local functions to be complex-valued and only require them, in some suitable sense, to be positive semi-definite kernel functions. We discuss various properties of the SPA when running it on DE-FGs and we show promising numerical results for various example DE-FGs, some of which have connections to quantum information processing.

A factor-graph representation of quantum-mechanical probabilities (involving any number of measurements) is proposed. Unlike standard statistical models, the proposed representation uses auxiliary variables (state variables) that are not random variables. All joint probability distributions are marginals of some complex-valued function q, and it is demonstrated how the basic concepts of quantum mechanics relate to factorizations and marginals of q.

We study the size (or volume) of balls in the metric space of permutations, Sn, under the infinity metric. We focus on the regime of balls with radius r = p · (n-1), p ∈ [0, 1], i.e., a radius that is a constant fraction of the maximum possible distance. We provide new lower bounds on the size of such balls. These new lower bounds reduce the asymptotic gap to the known upper bounds to at most 0.029 bits per symbol. Additionally, they imply an improved ball-packing bound for error-correcting codes, and an improved upper bound on the size of optimal covering codes.

We study the problem of estimating the pattern maximum likelihood (PML) distribution for time-homogeneous discrete-time Markov chains (DTMCs). The PML problem for memoryless sources has been well studied in the literature and we propose an extension of the same for DTMCs. For memoryless sources, Acharya et al. have shown that plug-in estimators obtained from the PML estimate yield good estimates for symmetric functionals of the distribution. We show that this holds for the PML estimate of DTMCs as well. Finally, we express the PML estimate for DTMCs as the double minimization of a certain free energy function and discuss some mean-field approximations to approximate the PML estimate efficiently.

In the light of the recent interest in approximating the partition function of the Ising model using the dual normal factor graph, we revisit the classical duality result of Kramers and Wannier, where the dual normal factor graph may be viewed as an intermediate step in establishing such a result.

Recent empirical results have demonstrated that generalized belief propagation (GBP) can be used to closely estimate the capacity of certain 2D runlength-limited constraints. We provide a partial analytical validation of these observations by showing that GBP yields a lower bound on the partition function of 2D Ising models with restricted grid size. While previous papers have proved that belief propagation (BP) can be used to obtain a lower bound on the partition function of 2D Ising models, this paper is the first work that analyzes GBP-based partition function approximations of 2D Ising models.

We study the size (or volume) of balls in the metric space of permutations, Sn, under the infinity metric. We focus on the regime of balls with radius r = ρ · (n-1), ρ ∈ [0, 1], i.e., a radius that is a constant fraction of the maximum possible distance. We provide new bounds on the size of such balls. These bounds reduce the asymptotic gap between the upper and lower bound to at most 0.06 bits per symbol.

Motivated by coding-theoretic questions that arise in the context of flash-memory-based data storage, we consider the problem of (approximately) counting the number of sequences of length n that are balanced and that avoid certain patterns. We do this by formulating a suitable factor graph whose total sum represents the desired quantity, by computing the Bethe approximation of the total sum, and by bounding the difference between the total sum and its Bethe approximation via the loop calculus technique. Although there are alternative techniques for counting the above-mentioned sequences, the presented counting technique has the potential to generalize more easily to other setups.

We design low-complexity error correction coding schemes for channels that introduce different types of errors and erasures: on the one hand, the proposed schemes can successfully deal with symbol errors and erasures, and, on the other hand, they can also successfully handle phased burst errors and erasures.

For an arbitrary binary cycle code, we show that sum-product algorithm (SPA) decoding after infinitely many iterations equals symbolwise graph-cover decoding. We do this by characterizing the Bethe free energy function of the underlying normal factor graph (NFG) and by stating a global convergence proof of the SPA. We also show that the set of log-likelihood ratio vectors for which the SPA converges to the all-zero codeword is given by the region of convergence of the edge zeta function associated with the underlying NFG. The results in this paper justify the use of graph-cover pseudo-codewords and edge zeta functions to characterize the behavior of SPA decoding of cycle codes. These results have also implications for the analysis of attenuated sum-product and max-product algorithm decoding of low-density parity-check (LDPC) codes beyond cycle codes.

We design low-complexity error correction coding schemes for channels that introduce different types of errors and erasures: on the one hand, the proposed schemes can successfully deal with symbol errors and erasures, and, on the other hand, they can also successfully handle phased burst errors and erasures.

Linear Programming (LP) decoding of Low-Density Parity-Check (LDPC) codes has attracted much attention in the research community in the past few years. LP decoding has been derived for binary and nonbinary linear codes. However, the most important problem with LP decoding for both binary and nonbinary linear codes is that the complexity of standard LP solvers such as the simplex algorithm remains prohibitively large for codes of moderate to large block length. To address this problem, two low-complexity LP (LCLP) decoding algorithms for binary linear codes have been proposed by Vontobel and Koetter, henceforth called the basic LCLP decoding algorithm and the subgradient LCLP decoding algorithm. In this paper, we generalize these LCLP decoding algorithms to nonbinary linear codes. The computational complexity per iteration of the proposed nonbinary LCLP decoding algorithms scales linearly with the block length of the code. A modified BCJR algorithm for efficient check-node calculations in the nonbinary basic LCLP decoding algorithm is also proposed, which has complexity linear in the check node degree. Several simulation results are presented for nonbinary LDPC codes defined over Z4, GF(4), and GF(8) using quaternary phase-shift keying and 8-phase-shift keying, respectively, over the AWGN channel. It is shown that for some group-structured LDPC codes, the error-correcting performance of the nonbinary LCLP decoding algorithms is similar to or better than that of the min-sum decoding algorithm.

It has recently been observed that the permanent of a nonnegative square matrix, i.e., of a square matrix containing only nonnegative real entries, can very well be approximated by solving a certain Bethe free energy function minimization problem with the help of the sum–product algorithm. We call the resulting approximation of the permanent the Bethe permanent. In this paper, we give reasons why this approach to approximating the permanent works well. Namely, we show that the Bethe free energy function is convex and that the sum–product algorithm finds its minimum efficiently. We then discuss the fact that the permanent is lower bounded by the Bethe permanent, and we comment on potential upper bounds on the permanent based on the Bethe permanent. We also present a combinatorial characterization of the Bethe permanent in terms of permanents of so-called lifted versions of the matrix under consideration. Moreover, we comment on possibilities to modify the Bethe permanent so that it approximates the permanent even better, and we conclude the paper with some observations and conjectures about permanent-based pseudocodewords and permanent-based kernels.

We present a combinatorial characterization of the Bethe entropy function of a factor graph, such a characterization being in contrast to the original, analytical, definition of this function. We achieve this combinatorial characterization by counting valid configurations in finite graph covers of the factor graph. Analogously, we give a combinatorial characterization of the Bethe partition function, whose original definition was also of an analytical nature. As we point out, our approach has similarities to the replica method, but also stark differences. The above findings are a natural backdrop for introducing a decoder for graph-based codes that we will call symbolwise graph-cover decoding, a decoder that extends our earlier work on blockwise graph-cover decoding. Both graph-cover decoders are theoretical tools that help toward a better understanding of message-passing iterative decoding, namely blockwise graph-cover decoding links max-product (min-sum) algorithm decoding with linear programming decoding, and symbolwise graph-cover decoding links sum-product algorithm decoding with Bethe free energy function minimization at temperature one. In contrast to the Gibbs entropy function, which is a concave function, the Bethe entropy function is in general not concave everywhere. In particular, we show that every code picked from an ensemble of regular low-density parity-check codes with minimum Hamming distance growing (with high probability) linearly with the block length has a Bethe entropy function that is convex in certain regions of its domain.

A factor-graph representation of quantum-mechanical probabilities is proposed. Unlike standard statistical models, the proposed representation uses auxiliary variables (state variables) that are not random variables.

Very often, constrained coding schemes impose nonlinear constraints on arrays and therefore it is usually nontrivial to determine how many arrays satisfy the given constraints. In this paper we show that there are non-trivial constrained coding scenarios where the number of constrained arrays can be estimated to a surprisingly high accuracy with the help of the sum-product algorithm, despite the fact that the underlying factor graphs have many short cycles, and we investigate the reasons why this is the case. These findings open up interesting possibilities for determining the number of constrained arrays also for scenarios where other counting and bounding techniques are not readily available.

Among all memoryless source distributions, the pattern maximum likelihood (PML) distribution is the distribution which maximizes the probability that a memoryless source produces a string with a given pattern. Equivalently, the PML distribution maximizes the permanent of a certain non-negative matrix. We reformulate this maximization problem as a double minimization problem of a suitable Gibbs free energy function. Because finding the minimum of this function appears intractable for practically relevant problem sizes, one must look for tractable approximations. One approach is to approximately find a minimum (or at least a local minimum) of the Gibbs free energy function by applying an alternating minimization algorithm where the steps are based on quantities that are obtained by Markov chain Monte Carlo sampling. One can show that this approach is equivalent to an algorithm that was proposed by Orlitsky et al. An alternative approach is to replace the Gibbs free energy function by a tractable approximation like the Bethe free energy function and to apply an alternating minimization algorithm to this function. As it turns out, empirically, this latter approach gives very good approximations to the PML distribution (or at least a locally optimal PML distribution), and, for the same level of accuracy, is two to three orders of magnitude faster than the former approach for practically relevant problem sizes. Moreover, the above free energy framework allows us to simplify some earlier proofs of properties of the PML distribution and to derive some new properties of the PML distribution, along with obtaining similar results for its Bethe approximation.

We present a mathematical connection between channel coding and compressed sensing. In particular, we link, on the one hand, channel coding linear programming decoding (CC-LPD), which is a well-known relaxation of maximum-likelihood channel decoding for binary linear codes, and, on the other hand, compressed sensing linear programming decoding (CS-LPD), also known as basis pursuit, which is a widely used linear programming relaxation for the problem of finding the sparsest solution of an underdetermined system of linear equations. More specifically, we establish a tight connection between CS-LPD based on a zero-one measurement matrix over the reals and CC-LPD of the binary linear channel code that is obtained by viewing this measurement matrix as a binary parity-check matrix. This connection allows the translation of performance guarantees from one setup to the other. The main message of this paper is that parity-check matrices of “good” channel codes can be used as provably “good” measurement matrices under basis pursuit. In particular, we provide the first deterministic construction of compressed sensing measurement matrices with an order-optimal number of rows using high-girth low-density parity-check codes constructed by Gallager.

Quasi-cyclic (QC) low-density parity-check (LDPC) codes are an important instance of proto-graph-based LDPC codes. In this paper we present upper bounds on the minimum Hamming distance of QC LDPC codes and study how these upper bounds depend on graph structure parameters (like variable degrees, check node degrees, girth) of the Tanner graph and of the underlying proto-graph. Moreover, for several classes of proto-graphs we present explicit QC LDPC code constructions that achieve (or come close to) the respective minimum Hamming distance upper bounds. Because of the tight algebraic connection between QC codes and convolutional codes, we can state similar results for the free Hamming distance of convolutional codes. In fact, some QC code statements are established by first proving the corresponding convolutional code statements and then using a result by Tanner that says that the minimum Hamming distance of a QC code is upper bounded by the free Hamming distance of the convolutional code that is obtained by “unwrapping” the QC code.

Inspired by some new advances on normal factor graphs (NFGs), we introduce NFGs as a simple and intuitive diagrammatic approach towards encoding some concepts from linear algebra. We illustrate with examples the workings of such an approach and settle a conjecture of Peterson on the Pfaffian.

Factor graphs are graphical models with origins in coding theory. The sum-product, the max-product, and the min-sum algorithms, which operate by message passing on a factor graph, subsume a great variety of algorithms in coding, signal processing, and artificial intelligence. This paper aims at extending the field of possible applications of factor graphs to Lagrangian and Hamiltonian dynamics. The starting point is the principle of least action (more precisely, the principle of stationary action). The resulting factor graphs require a new message-passing algorithm that we call the stationary-sum algorithm. As it turns out, some of the properties of this algorithm are equivalent to Liouville's theorem. Moreover, duality results for factor graphs allow to easily derive Noether's theorem. We also discuss connections and differences to Kalman filtering.

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.

Let the induced Bethe entropy of a pseudo-codeword be the Bethe entropy of the pseudo-marginal that, among all pseudo-marginals that correspond to this pseudo-codeword, has the maximal Bethe entropy. The aim of the present paper is to discuss a connection between the induced Bethe entropy of a cycle code and the edge zeta function of the same code. Namely, we show the equivalence of, on the one hand, the directional derivative of the induced Bethe entropy at the origin in the direction of a pseudo-codeword, and, on the other hand, the growth rate of the coefficients of the monomials that appear in the Taylor series expansion of the edge zeta function and that correspond to this pseudo-codeword. This connection is established via the entropy rate of some random walk that is associated with this pseudo-codeword, this random walk being an object of interest by itself.

Let n be an even positive integer and F be the field GF(2). A word in Fnis called balanced if its Hamming weight is n/2. A subset C ¿ Fnis called a balancing set if for every word y ¿ Fnthere is a word x ¿ C such that y + x is balanced. It is shown that most linear subspaces of Fnof dimension slightly larger than 3/2 log2n are balancing sets. An application of linear balancing sets is presented for designing efficient error-correcting coding schemes in which the codewords are balanced.

The linear-programming decoding performance of a binary linear code crucially depends on the structure of the fundamental cone of the parity-check matrix that describes the code. Towards a better understanding of fundamental cones and the vectors therein, we introduce the notion of absdet-pseudo-codewords and perm-pseudo-codewords: we give the definitions, we discuss some simple examples, and we list some of their properties.

A generalization of the Reiger bound is presented for the list decoding of burst errors. It is then shown that Reed–Solomon codes attain this bound.

We consider the problem of minimizing upper bounds and maximizing lower bounds on information rates of stationary and ergodic discrete-time channels with memory. The channels we consider can have a finite number of states, such as partial response channels, or they can have an infinite state space, such as time-varying fading channels. We optimize recently proposed information rate bounds for such channels, which make use of auxiliary finite-state machine channels (FSMCs). Our main contribution in this paper is to provide iterative expectation-maximization (EM) type algorithms to optimize the parameters of the auxiliary FSMC to tighten these bounds. We provide an explicit, iterative algorithm that improves the upper bound at each iteration. We also provide an effective method for iteratively optimizing the lower bound. To demonstrate the effectiveness of our algorithms, we provide several examples of partial response and fading channels where the proposed optimization techniques significantly tighten the initial upper and lower bounds. Finally, we compare our results with results obtained by the conjugate gradient optimization algorithm and an improved variation of the simplex algorithm, called Soblex. While the computational complexities of our algorithms are similar to the conjugate gradient method and less than the Soblex algorithm, our algorithms robustly find the tightest bounds. Interestingly, from a channel coding/decoding perspective, optimizing the lower bound is related to increasing the achievable mismatched information rate, i.e., the information rate of a communication system where the decoder at the receiver is matched to the auxiliary channel, and not to the original channel.

Message-passing iterative decoders for low-density parity-check (LDPC) block codes are known to be subject to decoding failures due to so-called pseudocodewords. These failures can cause the large signal-to-noise ratio (SNR) performance of message-passing iterative decoding to be worse than that predicted by the maximum-likelihood (ML) decoding union bound.

A generalization of the Reiger bound is presented for the list decoding of burst errors. It is then shown that Reed-Solomon codes attain this bound.

The classical Blahut-Arimoto algorithm (BAA) is a well-known algorithm that optimizes a discrete memoryless source (DMS) at the input of a discrete memoryless channel (DMC) in order to maximize the mutual information between channel input and output. This paper considers the problem of optimizing finite-state machine sources (FSMSs) at the input of finite-state machine channels (FSMCs) in order to maximize the mutual information rate between channel input and output. Our main result is an algorithm that efficiently solves this problem numerically; thus, we call the proposed procedure the generalized BAA. It includes as special cases not only the classical BAA but also an algorithm that solves the problem of finding the capacity-achieving input distribution for finite-state channels with no noise. While we present theorems that characterize the local behavior of the generalized BAA, there are still open questions concerning its global behavior; these open questions are addressed by some conjectures at the end of the paper. Apart from these algorithmic issues, our results lead to insights regarding the local conditions that the information-rate-maximizing FSMSs fulfill; these observations naturally generalize the well-known Kuhn-Tucker conditions that are fulfilled by capacity-achieving DMSs at the input of DMCs.

In this paper we study the iterative decoding behavior of time-invariant and time-varying LDPC convolutional codes derived by unwrapping QC LDPC block codes. In particular, for a time-varying LDPC convolutional code, we show that the minimum pseudo-weight of the convolutional code is at least as large as the minimum pseudo-weight of the underlying QC code. We also prove that the unwrapped convolutional codes have fewer short cycles than the QC codes. These results taken together lead to improved BER performance in the low-to-moderate SNR region, where the decoding behavior is influenced by the complete pseudo-codeword spectra and by the Tanner graph cycle histogram, with the time-varying convolutional codes outperforming both the underlying QC block codes and their time-invariant convolutional counterparts.

We consider the problem of optimizing information rate upper and lower bounds for communication channels with (possibly large) memory. A recently proposed auxiliary-channel- based technique allows one to efficiently compute upper and lower bounds on the information rate of such channels. Towards tightening these bounds, we propose iterative expectation- maximization (EM) type algorithms to optimize the parameters of the auxiliary finite-state machine channel (FSMC). From a channel coding perspective, optimizing the lower bound is related to increasing the achievable mismatched information rate, i.e. the information rate of a communication system where the maximum-likelihood decoder at the receiver is matched to the auxiliary channel and not to the true channel. We provide explicit solutions for optimizing the upper bound and the difference between the upper and the lower bound and we discuss a method for the optimization of the lower bound for data-controllable channels with memory. We discuss examples of channels with memory, for which application of the developed theory results in noticeably tighter information rate bounds.

Universally decodable matrices (UDMs) can be used for coding purposes when transmitting over slow fading channels. These matrices are parameterized by positive integers L and N and a prime power q. The main result of this correspondence is that the simple condition L = q + 1 is both necessary and sufficient for (L, N, q)-VDMs to exist. The existence proof is constructive and yields a coding scheme that is equivalent to a class of codes that was proposed by Rosenbloom and Tsfasman. Our work resolves an open problem posed recently in the literature.

We consider coded data transmission over a binary-input output-symmetric memoryless channel using a binary linear code. In order to understand the performance of maximum-likelihood (ML) decoding, one studies the codewords, in particular the minimal codewords, and their Hamming weights. In the context of linear programming (LP) decoding, one's attention needs to be shifted to the pseudo-codewords, in particular, to the minimal pseudo-codewords and their pseudo-weights. In this paper, we investigate some families of codes that have good properties under LP decoding, namely certain families of low-density parity-check (LDPC) codes that are derived from projective and Euclidean planes: we study the structure of their minimal pseudo-codewords and give lower bounds on their pseudo-weight. Besides this main focus, we also present some results that hold for pseudo-codewords and minimal pseudo-codewords of any Tanner graph, and we highlight how the importance of minimal pseudo-codewords under LP decoding varies depending on which binary-input output-symmetric memoryless channel is used.

Iterative message-passing decoders for low-density parity-check (LDPC) block codes are known to be subject to decoding failures due to so-called pseudo-codewords. These failures can cause the large signal-to-noise ratio performance of message-passing decoding to be worse than that predicted by the maximum-likelihood decoding union bound. In this paper we study the pseudo-codeword problem for the class of LDPC convolutional codes decoded continuously using an iterative, sliding window, message-passing decoder. In particular, for an LDPC convolutional code derived by unwrapping a quasi-cyclic LDPC block code, we show that the free pseudo-weight of the convolutional code is at least as large as the minimum pseudo-weight of the underlying quasi-cyclic code. This result parallels the well-known relationship between the free Hamming distance of convolutional codes and the minimum Hamming distance of their quasi-cyclic counterparts. Finally, simulation results are included that show improved performance for unwrapped LDPC convolutional codes compared to their underlying quasi-cyclic codes

Whereas many results are known about thresholds for ensembles of low-density parity-check codes under message-passing iterative decoding, this is not the case for linear programming decoding. Towards closing this knowledge gap, this paper presents some bounds on the thresholds of low-density parity-check code ensembles under linear programming decoding.

The information rate of finite-state source/channel models can be accurately estimated by sampling both a long channel input sequence and the corresponding channel output sequence, followed by a forward sum–product recursion on the joint source/channel trellis. This method is extended to compute upper and lower bounds on the information rate of very general channels with memory by means of finite-state approximations. Further upper and lower bounds can be computed by reduced-state methods.

Consider data transmission over a binary-input additive white Gaussian noise channel using a binary low-density parity-check code. We ask the following question: Given a decoder that takes log-likelihood ratios as input, does it help to modify the log-likelihood ratios before decoding? If we use an optimal decoder then it is clear that modifying the log-likelihoods cannot possibly help the decoder's performance, and so the answer is "no." However, for a suboptimal decoder like the linear programming decoder, the answer might be "yes": In this paper we prove that for certain interesting classes of low-density parity-check codes and large enough SNRs, it is advantageous to truncate the log-likelihood ratios before passing them to the linear programming decoder

In order to understand the performance of a code under maximum-likelihood (ML) decoding, it is crucial to know the minimal codewords. In the context of linear programming (LP) decoding, it turns out to be necessary to know the minimal pseudo-codewords. This paper studies the minimal codewords and minimal pseudo-codewords of some families of codes derived from projective and Euclidean planes. Although our numerical results are only for codes of very modest length, they suggest that these code families exhibit an interesting property. Namely, all minimal pseudo-codewords that are not multiples of a minimal codeword have an AWGNC pseudo-weight that is strictly larger than the minimum Hamming weight of the code. This observation has positive consequences not only for LP decoding but also for iterative decoding

Factor graphs (FG) are graphical models with origins in coding theory. The sum-product and the max-product algorithms (SPA/MPA), which operate by message passing in an FG, subsume a great variety of algorithms in coding, signal processing, and artificial intelligence. This paper aims at showing that it is possible to give an FG/SPA interpretation of one of the best data compression algorithms, namely the context-tree weighting (CTW) method. An arithmetic encoder/decoder needs the conditional probabilities of the next symbol can be obtained by performing the SPA on the FG which represents the joint pmf/pdf of all occuring random variables. Once the CTW algorithm is formulated in the FG/SPA-framework, new extensions of the algorithm become readily apparent.

In the past, several authors have considered quasicyclic LDPC codes whose circulant matrices in the parity-check matrix are cyclically shifted identity matrices. By composing a parity-check matrix not only with such matrices but also with sums of two cyclically shifted identity matrices and with zero matrices, one can increase the minimum distance while keeping the same regularity. Specifically, whereas for (3, 4)-regular codes in the first class the best minimum distance is 24, the best minimum distance in the second class is 32. We give examples of codes that achieve these bounds.

This paper discusses the two techniques for obtaining lower bounds on the (AWGN channel) pseudo-weight of binary linear codes. Whereas the first bound is based on the largest and second-largest eigenvalues of a matrix associated with the parity-check matrix of a code, the second bound is given by the solution to a linear program.

Cycle codes are a special case of low-density parity-check (LDPC) codes and as such can be decoded using an iterative message-passing decoding algorithm on the associated Tanner graph. The existence of pseudo-codewords is known to cause the decoding algorithm to fail in certain instances. In this paper, we draw a connection between pseudo-codewords of cycle codes and the so-called edge zeta function of the associated normal graph and show how the Newton polytope of the zeta function equals the fundamental cone of the code, which plays a crucial role in characterizing the performance of iterative decoding algorithms.

Factor graphs are graphical models with origins in coding theory. The sum-product and the max-product algorithms, which operate by message passing on a factor graph, subsume a great variety of algorithms in coding, signal processing, and artificial intelligence. The paper aims at extending the field of possible applications to dynamical electrical networks (i.e., networks that contain capacitors and inductors as well as static components). Interestingly, the resulting factor graphs have a structure very much akin to a Kalman filter.

We discuss how interleavers for parallel concatenated turbo codes with good minimum distance can be derived from graphs having large girth, i.e. graphs whose length of the shortest cycle is large.

A method for computing upper bounds on capacity for a class of time-invariant indecomposable finite state channels is presented. It extends a result for finite-input memoryless channels. Numerical results are provided for selected channels having memory and constraint (binary) input.