{'fraction_non_alphanumeric': 0.05440511544532734, 'fraction_numerical': 0.014046071113251464, 'mean_word_length': 4.049307666328943, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Finite-Dimensional Bounds on Zm and Binary LDPC Codes with Belief Propagation Decoders

This paper focuses on finite-dimensional upper and lower bounds on decodable thresholds of Zm and binary low-density parity-check (LDPC) codes, assuming belief propagation decoding on memoryless channels. A concrete framework is presented, admitting systematic searches for new bounds. Two noise measures are considered: the Bhattacharyya noise parameter and the soft bit value for a maximum a posteriori probability (MAP) decoder on the uncoded channel. For Zm LDPC codes, an iterative m-dimensional bound is derived for m-ary-input/symmetric-output channels, which gives a sufficient stability condition for Zm LDPC codes and is complemented by a matched necessary stability condition introduced herein. Applications to coded modulation and to codes with non-equiprobable distributed codewords are also discussed. For binary codes, two new lower bounds are provided for symmetric channels, including a two-dimensional iterative bound and a one-dimensional non-iterative bound, the latter of which is the best known bound that is tight for binary symmetric channels (BSCs), and is a strict improvement over the bound derived by the channel degradation argument. By adopting the reverse channel perspective, upper and lower bounds on the decodable Bhattacharyya noise parameter are derived for non-symmetric channels, which coincides with the existing bound for symmetric channels.


I. INTRODUCTION
The belief propagation (BP)/sum-product algorithm [1] is one of the major components in modern capacity-approaching codes, including turbo codes [2], low-density parity-check (LDPC) codes [3], repeat accumulate (RA) codes [4], etc. The BP algorithm uses distributed local computation to approximate the global maximum likelihood in an efficient way [5]. The density evolution (DE) method is a tool for explicitly computing the asymptotic behavior under iterative decoding with the assumption of independently distributed messages, which can be justified by the cycle-free convergence theorem in [6]. In each iteration, the DE method focuses on the density of the log likelihood ratio 1 (LLR), which is of infinite dimension and is a sufficient statistic completely describing arbitrary binary-input memoryless channels.
Even after the efficient implementation of density evolution by moving into the LLR domain, a one-dimensional iterative formula (or at most finite-dimensional formulae) to approximate the density evolution is very appealing since it reduces significantly the computational complexity of code degree optimization [7]. Several approximation formulae have been proposed including Gaussian approximations [8], [9], binary erasure channel (BEC) approximations, reciprocal channel approximations [10], and the EXtrinsic Information Transfer (EXIT) chart analysis [11]. The finite dimensionality also helps in the analysis of the behavior of the message passing decoder [12], [13].
Contrary to the approximations, rigorous iterative upper and lower bounds generally sacrifice the threshold predictability for specific channel models in exchange for guaranteed universal performance for arbitrary channel models. Many results have been found for binary-input/symmetric-output (BI-SO) channels, including Burshtein et al. [13] on the soft bit value for the maximum a posteriori probability (MAP) decoder, Khandekar et al. [14] on the Bhattacharyya noise parameter, and Land et al. [15] and Sutskover et al. [16] on the mutual information. For binary-input/non-symmetricoutput (BI-NSO) channels, a loose one-dimensional iterative upper bound on the Bhattacharyya noise parameter is provided in [17], which was used to derive the stability condition of BI-NSO channels and to upper bound the asymptotic convergence rate of the bit error probability. Bennatan et al. [18] used an iterative upper bound to derive the stability conditions for GF(q)-based LDPC codes when q is a power of a prime number.
This paper is organized as follows. The necessary definitions and background knowledge will be provided in Section II, including the definitions of the symmetric channels, the noise measures of interest, and the LDPC code ensemble. Section III will provide the framework for the iterative bounding problem and review some existing results. A Bhattacharyya-noiseparameter bound and a pair of stability conditions will be provided for Z m LDPC codes in Section IV. For binary LDPC codes, Sections V and VI are devoted to the iterative and non-iterative bounds respectively, the former of which include a one-dimensional bound for BI-NSO channels and a twodimensional bound for BI-SO channels, while the latter of which provides the best (tightest) known bound for binary symmetric channels (BSCs). The existing bound based on the channel degradation argument [6] is also tight for BSCs, but is very loose for other channels, compared to which our bound is a strict improvement and generates much tighter results for other channel models. Performance comparisons are provided in Section VII. Section VIII concludes the paper.

II. FORMULATION
In this paper, we consider only memoryless channels with discrete input alphabets.
A. Symmetric Channels 1) Definition: A BI-SO X → Y channel is conventionally defined as a channel with binary 2 input set X = {0, 1} and real output set Y = R, such that P(Y = y|X = 0) = P(Y = −y|X = 1) where X and Y denote the (random) channel input and output, respectively. In the literature of LDPC codes (eg., [6]), an equivalent commonly-used definition is that the BI-SO channel satisfies dP (m) = e m dP (−m), where dP (m) is the density of the LLR messages, m := log P(Y |X=0) P(Y |X=1) , given X = 0.
Definition 1 (MI-SO Channels): For any function T : Y → Y, let denote the corresponding k-times self-composition of T . An m-ary-input channel Z m → Y is (circularly) symmetric if there exists a bijective transform T : Y → Y such that T m (y) = y, ∀y ∈ Y and ∀x ∈ Z m , F (dy|0) = F (T x (dy)|x), where F (dy|x) is the conditional distribution of Y ∈ dy given X = x. When m = 2, this definition collapses to that of the conventional BI-SO channel. Note: There is no constraint on Y, the range of the channel output. For example, in phase-shift keying (PSK) or quadrature amplitude modulation (QAM) scenarios, Y = R 2 .
This definition of "symmetric channels" coincides with the definition of the "matched signal set" in [19]. It is worth noting that belief propagation on LDPC codes is (circularly) symmetric, since the locally optimal BP decoder behaves identically under different transmitted codewords when the same circularly shifted error pattern is received. To be more explicit, assume that a non-zero codeword x = (x 1 , · · · , x n ) is transmitted and the received likelihood values are p(y) = (p(y 1 ), · · · , p(y n )), where each coordinate p(y i ) = (P (Y i = y i |X i = 0), P (Y i = y i |X i = 1), · · · , P (Y i = y i |X i = m − 1)) is a vector containing the likelihood values of x i after receiving y i . The circular symmetry of the belief propagation decoder is characterized by the fact that the decoding behavior under the codeword and likelihood pair (x, p(y)) is identical to the case in which the all-zero codeword 0 is transmitted W ∈ Z m (b) A symmetrized MI-NSO channel.
One immediate benefit of considering a symmetric channel LDPC codes is that all codewords have the same error probability under the BP decoder and we can use the all-zero codeword as a representative, which facilitates the simulation of codes with finite length. Further discussion on the BP decoder for Z m LDPC codes and on the representative allzero codeword can be found in [20] and in [19], [6], [17].
One advantage of Definition 1 is that we can immediately prove the channel symmetrizing argument as follows. Consider an m-ary-input/non-symmetric-output (MI-NSO) channel in Fig. 1(a) and a concatenated new channel in Fig. 1(b), sharing the same MI-NSO channel block. Since the receiver of the latter channel is able to use the received value of W to invert this concatenation, these two channels are equivalent from the detection point of view, which in turn implies that all reasonable noise measures of the two are identical, including but not limited to the channel capacities, the error probabilitiess and soft-bit values under the MAP decoder, and the Bhattacharyya noise parameters. The circular symmetry of this new equivalent channel X → (W, Y ) in Fig. 1(b) can then be verified by letting the bijective transform T : (Z m , Y) → (Z m , Y) in Definition 1 be T (w, y) = (w − 1, y). From the above discussion, Fig. 1(b) is an equivalent, symmetrized version of the original MI-NSO channel, and we can assume all channels are symmetric as long as the additional complexity of the channel symmetrizing 3 is bearable.
2) MSC Decomposition: One of the simplest MI-SO channels is the m-ary symmetric channel (MSC), which is a Z m → Z m channel and can be fully specified by a parameter vector MI-SO Channel p = (p 0 , p 1 , · · · , p m−1 ) such that the conditional probability P(Y = x + i|X = x) = p i , ∀x, i ∈ Z m . From Definition 1, it can be proved that any MI-SO channel can be uniquely expressed as a probabilistic combination of different MSCs, while p is observed by the receiver as side information. This decomposition is illustrated in Figs. 2(a) and 2(b), in which the probabilistic weight of different vectors p is denoted as dP (p), and a formal proof of this MSC decomposition is given in APPENDIX I. When m = 2, an MSC collapses to a BSC and the channel-specifying vector p equals (1 − p, p), where p is the crossover probability. For simplicity, we sometimes use the scalar parameter p rather than the vector p to specify a BSC.
Note: The probabilistic weight dP (p) does not depend on the a priori input distribution on X, but only depends on the channel model P(Y |X). This observation will be used in the proof of the non-iterative bound in Section VI.

B. Noise Measures
1) Binary Input Channels: For a binary channel X = {0, 1} → Y, we use p(x|y) to denote the a posteriori probability P(X = x|Y = y), and consider the following two noise measures: wherex denotes the complement of the binary input x.
A discussion of the CB parameter in turbo-like codes can be found in [22]. With uniformly distribution on X, CB can be related to the cutoff rate R 0 by R 0 = 1 − log 2 (CB + 1).
which was used in the bounds of [13].
Each of the above noise measures has the property that the condition CB = 0 (or SB = 0), represents the noise-free channel, while CB = 1 (or SB = 1), implies the noisiest channel in which the output is independent of the input. It is worth noting that both CB and SB are well defined even for BI-NSO channels with non-uniform input distributions. Most of our theorems are derived based on the assumption of uniformly distributed X, and special notes will be given when non-uniform a priori distributions are considered. For BSCs with uniformly distributed X, CB = 2 p(1 − p) and SB = 4p(1 − p) where p is the crossover probability. By the BSC decomposition argument in Section II-A.2, the value of CB or SB for any BI-SO channel is simply the probabilistic average of the corresponding values of the constituent BSCs, that is, for uniformly distributed X The above formulae will be extensively used in our derivation of finite dimensional bounds. In the context of density evolution [6], CB and SB with uniformly distributed X can be expressed as where m := log P(Y|X=0) P(Y|X=1) is the passed LLR message and dP (m) := dP(m|X = 0) is the density of m given X = 0. With the assumption of uniformly distributed X, the CB and SB values of some common channel models are given as follows (listed in order from the most BSC-like to the most BEC-like 4 ): 1) The BSC with crossover probability p: 4 The order is obtained by plotting the (CB, SB) values of different channel models of the same capacity in a two-dimensional plane, similar to Fig. 7. The channel models are then sorted according to their distances related to the points corresponding to a BSC and a BEC.
2) The binary-input Laplace channel (BiLC) with variance 2λ 2 , i.e. p L (y) = 1 2λ exp − |y| λ : 3) The binary-input additive white Gaussian channel (Bi-AWGNC) with noise variance σ 2 : 4) The binary-input Rayleigh fading channel with unit input energy and noise variance σ 2 , i.e. the density function of the output amplitude is p A (a) = 2a exp(−a 2 ) and the additve noise distribution is N (0, σ 2 ): 5) The BEC with erasure probability ǫ: 2) m-ary Input Channels: For m-ary-input channels, we define the pairwise Bhattacharyya noise parameter from x to x ′ as follows: Considering any MI-SO channel with uniformly distributed input X, we immediately have By stationarity, we can then use CB := {CB(0 → x ′ )} x ′ ∈Zm as the representing vector for all CB(x → x ′ ). Also assuming the uniform distribution on X, the cutoff rate R 0 and CB can be related as follows [23]: Example: • For an MSC with parameter p and uniformly distributed X, we have When m = 2, the representing vector becomes CB = (1, CB(p)), where CB(p) = 2 p(1 − p) is the traditional Bhattacharyya noise parameter for BSCs.

C. Error Probability vs. CB vs. SB
Let p e = P X =X MAP (Y ) denote the error probability of the MAP decoder. The relationship between p e and the above noise measures CB (or CB) and SB are stated by the following lemmas.
Lemma 1: For general BI-NSO channels and arbitrary input distributions, we have and SB ≤ CB ≤ √ SB.
Lemma 2: For any MI-SO channel with uniform input distribution, we have Lemma 1 guarantees that the three statements: p e → 0, CB → 0, and SB → 0 are equivalent. Lemma 2 guarantees p e → 0 is equivalent to the statement that ∀x ∈ Z m \{0}, CB(0 → x) → 0. Detailed proofs of Lemmata 1 and 2 are provided in APPENDIX II.

D. The Equiprobable Graph Ensemble for LDPC Codes
Throughout this paper, we consider only the equiprobable graph ensemble for LDPC codes [6], where each element corresponds to the Tanner graph of the parity check matrix. The construction of the equiprobable graph ensemble is as follows. Consider two finite sets of nodes: variable nodes and check nodes, in which each node is assigned a degree deg(v) Assign deg(v) sockets to each variable node v and index all variable sockets from 1 to n e . Assign deg(c) sockets to each check node c and index all check sockets from 1 to n e . Let π(·) be an arbitrary permutation of the integers 1, · · · , n e . Construct an edge connecting variable socket i and check socket j iff i = π(j). The above procedure results in a bipartite graph and the equiprobable graph ensemble is constructed by letting π(·) being drawn from a uniform random permutation ensemble.
Based on this construction, we can define the edge-degree polynomials λ(x) = k λ k x k−1 and ρ(x) = k ρ k x k−1 , where λ k (or ρ k ) is the percentage of the edges connecting to a variable (or check) node of degree k. This code ensemble can then be uniquely specified by the degree polynomials λ and ρ and the codeword length n, and is denoted by C n (λ, ρ). We will sometimes use C(λ, ρ) to denote the asymptotic ensemble in the limit of large n. Further discussion of the asymptotic ensemble can be found in [6].

A. The Support Tree Channel
Due to the inherent nature of message-exchanging during each iteration, the result of a BP decoder after l iterations depends only on the neighbors (of the target variable node) within a distance of 2l. With the assumption that there is no cycle of length less than 2l in the corresponding Tanner graph, which holds for sufficiently large codeword length n in probability, the BP decoder on LDPC codes can be broken down into a tree structure of depth 2l as shown in [6] and demonstrated in Fig. 3, which considers the simplest case with target variable x 1 and l = 1. The arrows in Fig. 3(b) represent the message flow in the decoding process.
By the MSC decomposition argument, the tree structure can be viewed as in Fig. 4, which is a Z m → ([0, 1] m × Z m ) 3 vector channel. The arrows are now pointing in the opposite direction since they now represent the data flow during transmission. Due to its optimality when applied to a cyclefree inference network, the BP decoder is in essence an efficient version of a MAP decoder on the tree structure. Therefore, it is more convenient to focus on the behavior of general MAP decoders on this tree-like vector channel, instead of considering the message passing behavior of the BP decoder. It is worth emphasizing that throughout this paper, only independently and identically distributed channels are considered, and all dP 1 , dP 5 , dP 6 and their corresponding MSCs are independent.
Our target problem is to find bounds on the noise measures of the Z m → ([0, 1] m × Z m ) 3 vector output channel, given constraints of finite-dimensional noise measures on the constituent channel distribution dP i (p), i = 1, 5, 6. To simplify the problem further, we consider the variable node and the check node channels respectively as in Figs. 5(a) and 5(b), in which the new constituent X 1 → (q, Y ′ ) channel in Fig. 5(a) represents the entire X 1 → (p 5 , Y 5 ) × (p 6 , Y 6 ) vector channel in Fig. 5(b). Once the noise measure of the X 1 → (p 5 , Y 5 ) × (p 6 , Y 6 ) check node channel is bounded given the constraints on X 5 → (p 5 , Y 5 ) and X 6 → (p 6 , Y 6 ), this newly obtained bound for Fig. 5(b) can serve as a constraint on the constituent channel, X 1 → (q, Y ′ ), of the variable node channel in Fig. 5(a). When considering the behavior after infinitely many iterations, we can iteratively apply these check/variable node bounding techniques by switching the roles of "bounds on the vector output channel" and "constraints on the constituent channels" as in the aforementioned example. Given an initial constraint on the finite-dimensional noise measure of the constituent channels, whether the LDPC code is decodable can be determined by testing whether the noise measure converges to zero or is bounded away from zero as iterations proceed, which in turn gives us finite-dimensional lower/upper bounds on the decodable threshold.
For variable/check nodes with degrees d > 3, if we take the marginal approach (focusing on one input constituent channel while leaving other constituent channels fixed), all the effects of the fixed inputs can be grouped into a single input message. Therefore, it is as if we take the marginal approach on a variable/check node with degree equal to three. The analysis of nodes of degree one or two is trivial. As a result, throughout this paper, only nodes of degree d = 3 will be discussed in detail, and the variable/check node channels of interest are illustrated in Figs. 5(c) and 5(d) with inputs/outputs relabelled for easier reference.

B. Existing Results on Binary LDPC Codes
For BI-SO channels, the best way to explain the existing results in [13], [14], [15], and [16] is using the idea of "transfer functions" and the convexity/concavity analysis. In this subsection, we will consider only the noise measure CB for example, which will lead to the iterative upper bound in [14] and a new iterative lower bound. Similar arguments can be used to derive the results in [13] or in [15], [16], if we substitute either SB or the conditional entropy for the noise measure CB.
1) Check Nodes: For a check node as in Fig. 5(d), the problem of finding an iterative upper/lower bound can be cast as an optimization problem as follows.
CB chk (p, q) denotes the value of CB for the tree-like check node channel if both the constituent channels are BSCs with parameters p and q respectively, and CB 1 (p) and CB 2 (q) denote the CB values of the constituent BSCs with parameters p and q. Using some simple algebra, it can be shown that for fixed p and q, the (8) follows. Furthermore, by omitting the input parameters p and q, we can rewrite CB chk (p, q) in terms of CB 1 (p) and CB 2 (q) by which is the CB-based "transfer function" of the check node. Since CB chk is a convex function of CB 1 , this maximization/minimization problem is straightforward. The maximizing distribution dP * (p) is obtained by letting all probability weights concentrate on both extreme ends p = 0 and p = 1/2, that is Note: dP * is a probabilistic combination of a noise-free channel and a noisiest channel with output completely independent of the input, which corresponds to a BEC with erasure probability ǫ = CB in,1 . One visualization of this maximizing solution can be obtained by fixing CB 2 and plotting all possible values of (CB 1 , CB chk ) on a two dimensional plane, which form a convex curve. Connecting a string between both ends gives us the upper part of the convex hull of (CB 1 , CB chk )'s. Therefore, the probabilistic combination of any (CB 1 , CB chk ) lies within the convex hull and is upper bounded by the string. Since dP * (p) is a probabilistic weight such that the averaged CB 1 equals the constraint CB in,1 and the averaged CB chk touches the string, dP * (p) must be a maximizing solution. By Jensen's inequality, the minimizing distribution dP † (p) is obtained by letting all probability weights concentrate on a single point with the same CB in,1 , that is Note: dP † corresponds to a BSC. The same arguments can be applied to find dQ * and dQ † . By replacing both dP and dQ in (7) with the maximizing dP * and dQ * , we prove that for general constituent BI-SO channels, By replacing both dP and dQ in (7) with the minimizing dP † and dQ † , we also have By a straightforward extension to check nodes of higher degree d c ≥ 3, a similar upper bound can be obtained by replacing all (d c − 1) constituent channels 5 with BECs having the same values of CB in,i . The resulting upper bound is A similar lower bound can be obtained by replacing all (d c −1) constituent channels with BSCs having the same values of CB in,i . The resulting lower bound is 5 A different bounding method is to represent a check node with dc > 3 as a concatenation of (dc − 2) degree 3 check nodes and iteratively apply the bound derived for dc = 3, the resulting bound of which is strictly looser than the bound constructed by direct replacement. For instance, [15] iteratively bounds the entropy by concatenating many degree 3 nodes, while [16] takes an approach similar to that in this paper and replaces all channels simultaneously, which results in tighter upper/lower bounds.
2) Variable Nodes: For a variable node as shown in Fig. 5(c), the problem of finding an iterative upper/lower bound can be cast as an optimization problem as follows.
max or min CB out = CB var (p, q)dP (p)dQ(q) subject to CB in,1 = CB 1 (p)dP (p) where CB var (p, q) denotes the value of CB for the treelike variable node channel if both the constituent channels are BSCs with parameters p and q respectively. By the definition of CB in (1), we have Omitting the input arguments p and q, CB var can then be rewritten as which is the CB-based "transfer function" of the variable node. Since CB var is a concave 6 function of CB 1 , this maximization/minimization problem is straightforward and similar to the check node case. By Jensen's inequality, the maximizing distribution dP * (p) is obtained by letting all probability weights concentrate on a single point with the same CB in,1 , that is which corresponds to a BSC. The minimizing distribution dP † (p) is obtained by letting all probability weights concentrate on both extreme ends p = 0 and p = 1/2, that is , which corresponds to a BEC. As a result, by replacing all constituent BI-SO channels with BSCs having the same values of CB in,j , we obtain an upper bound for the variable node: By replacing all constituent channels with BECs having the same values of CB in,j , we obtain a lower bound for the variable node: 3) Combined Results: Consider BI-SO channels and the irregular code ensemble with degree polynomials λ and ρ. By combining (10) and (14) and averaging over the degree distributions, we have where CB (l) is the value of CB after l iterations, namely, the value of CB for the support tree of depth 2l. This is the result of Khandekar et al. in [14]. By combining (11) and (15) and averaging over (λ, ρ), we have a new iterative lower bound.
Theorem 1: For BI-SO channels, As stated in Section III-A, by checking whether CB (l) converges to zero by (16) or by (17), one can derive a lower/upper bound of the decodable threshold based on the CB (0) of the channel of interest. Closed form solutions for those thresholds can also be obtained following similar approaches as in [12], [16].
Similar arguments can be applied to other types of noise measures. In each iteration, replacing constituent channels of a check node with BECs/BSCs having the same value of SB, and replacing variable node constituent channels with BSCs/BECs having the same value of SB, we can reproduce the iterative upper/lower bound on SB found in [13]. By considering the conditional entropy instead of SB, we can reproduce the iterative upper/lower bound on the mutual information found in [15], [16]. This paper will focus on developing new bounds or strengthening existing bounds for the cases in which the simple convexity/concavity analysis of the transfer function does not hold.

A. Code Ensemble
The Z m -based LDPC code ensemble can be described as follows. The value of non-zero entries in the parity check matrix H are limited to one, and the random parity check matrix ensemble is identical to the ensemble of binary LDPC codes introduced in Section II-D. The only difference is that the parity check equation Hx = 0 is now evaluated in Z m . A further deviation from the binary code ensemble is the GF(q)based code ensemble. Besides evaluating Hx = 0 in GF(q), the non-zero entries in H are uniformly distributed between {1, 2, · · · , q − 1}. Further discussion of the Z m and GF(q) LDPC code ensembles can be found in [18], [24].
B. Iterative Bounds 1) Variable Nodes: As discussed in Section III-A, we focus on a variable node with degree d v = 3 as in Fig. 5(c). We will first consider p and q being fixed (non-random) parameters and then extend our analysis to accommodate the random parameter generators dP (p) and dQ(q).
By grouping the outputs Y 1 and Y 2 into a 2-dimensional vector Y = (Y 1 , Y 2 ), the variable node becomes a Z m → Z 2 m channel, and it can be verified by definition that it is still symmetric. By definition (4), the resulting CB var (0 → x) for the vector output channel with uniformly distributed 7 X becomes A compact vector representation using the component-wise product "•" then becomes By iteratively applying the above inequality for variable nodes with d v ≥ 3, we have where the represents the component-wise product. Consider general MI-SO constituent channels with random parameter generators dP j (p j ), where p j denotes the parameter vector for the j-th constituent channel and its distribution is denoted as dP j (·). Since the parameter vectors p j are independently distributed for different values of j, the probabilistic average of the product in (18) is the product of individual averages. This implies that (18) holds for general MI-SO channels as well.
2) Check Nodes: Consider a check node with degree d c = 3, namely, two constituent MSCs with parameters p and q, as illustrated in Fig. 5 m channel is given as follows: 7 By the linearity of the Zm parity check code, the marginal distribution of any X i , ∀i ∈ {1, · · · , n} is either uniform or concentrated on {0}. The latter case is of little interest since those bits can then be punctured without affecting the performance.
Each summand in (19) can be upper bounded by where the inequality follows from the fact that By combining (19) and (20), we have where (21) follows from the change of variables: w ′ = w − y and z ′ = z −y. A compact vector representation using circular convolution "⊗" then becomes By iteratively applying the above inequality and noting the monotonicity of the convolution operator (given all operands are component-wise non-negative), we have the following inequality for the cases d c > 3: Since the circular convolution is a summation of products and the p j are independently distributed for different values of j, the probabilistic average of the circular convolution in (23) is the circular convolution of individual averages. This implies that (23) holds for general MI-SO channels as well.
3) Combined Results: Consider general MI-SO channels and the irregular code ensemble with degree polynomials λ and ρ. By combining (18) and (23) and averaging over the degree distributions, we have proved the following theorem.
Theorem 2: Let CB (l) denote the value of CB for the support tree channel after l iterations. Then we have where the scalar products within λ(·) are replaced by component-wise products, and the scalar products within ρ(·) are replaced by circular convolutions. For a Z m code ensemble with degree polynomials (λ, ρ), we can first fix an arbitrary 8 CB * , let CB (0) = CB * , and iteratively compute the upper bound by (24) 9 . Suppose that, for all x = 0, lim l→∞ CB (l) (0 → x) = 0. By Lemma 2, any MI-SO channel with CB ≤ CB * is guaranteed to be decodable by the BP algorithm when sufficiently long codes are used. Unlike the two-dimensional case, the thresholds determined herein for m > 2 cases do not admit straightforward closed form solutions due to the lack of ordering. Some further research is necessary to determine the closed form threshold "envelope" of the decodable CB vectors.

C. Stability Conditions
The sufficient stability condition for Z m LDPC codes can be obtained as a corollary to Theorem 2.
Corollary 1 (Sufficient Stability Condition): Consider any MI-SO channel with noise measure CB and any Z m LDPC code ensemble with degree polynomials (λ, ρ). If ) Furthermore, the convergence rate of CB (l) (0 → x) is exponential or superexponential depending on whether λ 2 > 0 or λ 2 = 0.
Proof: Define f (l) Without loss of generality, we can assume f (l) CB = ǫ. Using the fact that CB (l) (0 → 0) = 1 for all l ∈ N, and the monotonicity of the convolution operator when all coordinates are possitive, it can be shown that ∀x ∈ Z m \{0}, where "⊗" represents the convolution product. Similarly, for the component-wise product, one can show that Using the above two inequalities and (24), we have Since CB . With a fixed choice of δ, (25) is satisfied for sufficiently small ǫ. (26) also shows that Hence the convergence rate is exponential or super exponential depending on whether λ 2 = 0. The proof is thus complete. A matching necessary stability condition can be proved as follows.
Theorem 3 (Necessary Stability Condition): Consider any MI-SO channel with noise measure CB and any Z m LDPC code ensemble with degree polynomials (λ, ρ). If A detailed proof using channel degradation argument similar to [6], [18] is provided in APPENDIX III.
We close this subsection by showing the stability results for GF(q) LDPC codes in [18] can be derived as a corollary to the above stability conditions for Z m LDPC codes.
Consider a MI-SO channel with noise measure CB, and a GF(q)-based LDPC code with degree polynomials (λ, ρ), where q is a prime number. The following stability conditions for GF(q) LDPC codes can be derived as direct corollaries to Corollary 1 and Theorem 3, which were first presented in [18].

Corollary 2 (Sufficient Stability Condition):
If then this GF(q) code is stable under the BP decoder.

Corollary 3 (Necessary Stability Condition):
If then this GF(q) code is not stable under the BP decoder.
Since the stability conditions of the Z m LDPC codes rely only on the pairwise error probability and the multiplication of the uniformly distributed edge weight w ∈ GF(q)\{0} is equivalent to a uniform permutation of all non-zero entries, the stability conditions of a GF(q) code are equivalent to those of a Z m code with the pairwise "error pattern" averaged over all non-zero entries. As a result, all results for Z m codes involving only CB(0 → x) hold for GF(q) codes as well with each CB(0 → x) being replaced by the average The above corollaries then become simply the restatement of the stability conditions for Z m LDPC codes.

D. Applications
We close this section with a non-comprehensive list of practical applications based on higher order LDPC codes and some corresponding references.
1) Improving the code performance [25]: By grouping two bits into a GF(4) symbol, the finite length performance of codes can be enhanced by the resulting higher dimensional codes. 2) Higher order coded modulation. Berkmann used higher order codes for coded modulation with the natural codeto-symbol mapping [26], [27]. By exhaustively searching for the optimal code-to-symbol mapper over all 8! possible mappers, our simulation shows that the asymptotic threshold of the regular Z 8 -based (3,9) code can be improved to within 0.63dB of the channel capacity of the 8PSK constellation with no additional cost. The simple structure of the (3,9) code and the better word-error probability make it an appealing alternative to turbo coded modulation or LDPC-coded bit-interleaved coded modulation (BICM).
In addition to having lower decoding complexity, one argument that the BICM is favorable over Z m -based coded modulation is the higher cutoff rate of BICM [23], which leads to a common belief that it is easier to design good codes for BICM than for high order coded modulations. The higher cutoff rate of BICM can be better explained by the fact that the origin of the cutoff rate can be traced to the pairwise union bound (the Gallager bound) over different symbols, which results in the summation operation over all possible CB(0 → x) values in (6). Our stability conditions show that the "effective" value of CB (in terms of the code performance) is the maximum of all CB(0 → x) rather than their summation. This result demonstrates that the cutoff rate, involving the sum rather than the maximum of CB(0 → x), is not a good benchmark between channels with different orders of alphabets. The above argument also gives a partial reasoning of the performance improvements after moving to a higher dimensional code in terms of the effective CB value, since the max CB(0 → x) can be reduced by a good coded-alphabet to transmitting-symbol mapper, and a greater stability region can be obtained. Note: Another advantage of the higher order coded modulation over BICM is that a matched spectral null code can be concatenated as an inner code to improve the performance when in inter-symbol interference (ISI) environments [21].
3) Constructing mutual-information-achieving codes with non-uniform coded bit distribution by converting Z m codes with uniform symbol distributions into nonuniformly distributed binary codes using "symbol mappers" [28]. Among the applications here are the following.
• Constructing codes for cases in which the capacityachieving a priori distribution is not uniform [28], [24].
• Designing optimal superposition codes for broadcasting channels. • Designing codes for optical channels with cross talk [29]. Other references on higher order LDPC codes can be found in [30], [9] V. ITERATIVE BOUNDS ON BINARY CHANNELS In this section, we will first show that the existing CB-based iterative bounds for BI-SO channels also hold for BI-NSO channels. Then we will strengthen the existing CB-based and SB-based bounds by providing a two-dimensional (CB, SB)based iterative upper bound for BI-SO channels.

A. CB-based Bounds on BI-NSO Channels
The definition of CB in (1) is applicable to BI-NSO channels with either uniform or non-uniform prior distributions. For the following, we will show that the inequalities (16) and (17) hold for BI-NSO channels as well by assuming a uniform prior distribution on X = {0, 1} and by adopting the reverse channel perspective. A uniform prior distribution is commonly assumed in all existing work on iterative bounds of LDPC code performance [13], [14], [15], [16], which can be justified by the perfect projection condition in [31].
Proof: We will first focus on the simplest binaryinput/binar-ouput non-symmetric channel, which is illustrated in Fig. 6(a) and is denoted as BNSC (in contrast to BSC). Since any BI-NSO channel can be regarded as the probabilistic combination of many BNSCs, our results for BNSC can then be generalized to arbitrary BI-NSO channels.
Any BNSC can be specified by two scalar parameters p 0→1 and p 1→0 , where p z→z ′ denotes the conditional probability P(Y = z ′ |X = z). CB thus becomes We can also represent this X → Y BNSC from the reverse channel perspective Y → X as in Fig. 6(b), such that where r z→z ′ := P(X = z ′ |Y = z) and R(y) = P(Y = y).
Then by definition, we have in which CB(p) ∆ = 2 p(1 − p) computes the value of CB for a BSC with crossover probability p. This representation separates the previous entangled expression of CB in (28) so that it is as if there are two BSCs with parameters r 0→1 and r 1→0 respectively, and these two BSCs are probabilistically combined with coefficients R(0) and R(1). We use For a variable node of degree d v = 3, by definition and after some simple algebra, we have · P (X 1 = X 2 = x|Y = (y 1 , y 2 ), X 1 = X 2 ).
Note that (30) possesses the same form as in (7) and (9). Thus, each BNSC in (30) has the same effect as a BI-SO channel corresponding to a probabilistic combination of two BSCs with parameters r 0→1 , r 1→0 (or s 0→1 , s 1→0 ) and weights R(0) and R(1) (or S(0) and S(1)). Since (10) and (11) hold for general BI-SO channels, they also hold for this particular combination of two BSCs, which in turn implies that they hold for BNSCs as well. By taking the probabilistic combination of many BNSCs, we have shown that (10) and (11) hold for general BI-NSO channels as well.
Since our previous analyses for both variable and check nodes (with BI-SO channels) hold for BI-NSO channels as well, we have proved Theorem 4.

B. A Two-Dimensional Upper Bound on BI-SO Channels
In this section, we develop a two-dimensional upper bound on the (CB, SB) pair of a BI-SO channel, for which convexity/concavity analysis of the transfer function is not sufficient.
Similar to the one-dimensional results in Section III-B, we consider variable node and check nodes separately.

1) Check Nodes:
Suppose the check node channel has two constituent BSCs with crossover probabilities p ∈ [0, 1/2] and q ∈ [0, 1/2] as shown in Fig. 5(d), where p and q have distributions dP (p) and dQ(q), respectively. Let CB in,1 and SB in,1 denote upper bounds on the values of CB and SB for the first constituent channel and let CB in,2 and SB in,2 denote corresponding upper bounds for the second constituent channel. We would like to develop an upper bound on the pair (CB, SB) for the support tree channel. This iterative bounding problem thus becomes: where CB chk (p, q) is defined in (8) and Using some simple algebra, we can show that the optimum value SB * out satisfies SB * out = SB in,1 + SB in,2 − SB in,1 SB in,2 . The remaining problem reduces to the maximization of CB out subject to two input constraints on each of dP and dQ. Solving this optimization problem, the maximizing dP * and dQ * can be expressed as follows.
dQ * can be obtained by replacing CB in,1 , SB in,1 , and p in the above equation with CB in,2 , SB in,2 , and q, respectively. A proof of the optimality of dP * and dQ * is given in APPENDIX IV. By substituting all constituent BI-SO channels with channels of the same form as dP * , we obtain an upper bound on (CB, SB) in check node iterations as follows.
Corollary 4: For the check node iteration of any (λ, ρ) irregular LDPC codes, we have Note: By incorporating the SB in constraint, the CB bound (32) is now tight for both the BEC and BSC cases, which is a strict improvement over the CB-only bound (10). (The bound (10) is obtained by connecting the two ends of the CB-based transfer function curve and is tight for the BEC case but loose for the BSC case.) 2) Variable Nodes: We consider a variable node of degree d v = 3. Given that the (CB, SB) values of the constituent channels are upper bounded by (CB in,1 , SB in,1 ) and (CB in,2 , SB in,2 ), respectively, the iterative upper bounding problem becomes max CB out = CB var (p, q)dP (p)dQ(q) (33) where CB var (p, q) is defined in (12) and .
By some simple algebra, it can be shown that the optimum value CB * out satisfies CB * out = CB in,1 CB in,2 . Unfortunately, for the remaining maximization problem on SB out , the maximizing distribution dP * depends on both (CB in,1 , SB in,1 ) and (CB in,2 , SB in,2 ). The simple replacement of each constituent channel with a maximizing counterpart does not work this time. To circumvent this difficulty, we provide an upper bounding distribution dP * * depending only on (CB in,1 , SB in,1 ), such that the objective value of any feasible solutions dP and dQ is no larger than the objective value obtained from dP * * and dQ. The distinction between the upper bounding distribution dP * * and the maximizing distribution dP * is that dP * * may not be feasible and thus may serve merely the bounding purpose.
For simplicity, we express dP * * by dropping the subscript 1 in the vector constraint (CB in,1 , SB in,1 ). where otherwise .
The upper bounding distribution dQ * * for the second constituent channel can be obtained by symmetry. A derivation of dP * * is included in APPENDIX V. It is worth noting that when there is no constraint on CB in (namely, when CB in = √ SB in by Lemma 1), dP * * collapses to a BSC, which coincides with the SB-based bound in [13]. Hence the upper bound distribution dP * * is a strict improvement over the existing SB-based bound.
Using this upper bounding distribution dP * * , an upper bound for (CB, SB) for variable node iterations is given as follows.
Theorem 6 (U B CB,SB in Variable Node Iterations): Suppose the variable node degree is d v , the input (CB, SB) pair is upper bounded by (CB in , SB in ), and the uncoded channel has noise measures (CB 0 , SB 0 ). Then, the output of the variable node iteration is upper bounded by where Φ dv−1 computes the value of SB for a variable node channel with one constituent Ch 0 channel and (d v − 1) constituent Ch in channels. Here, Ch in and Ch 0 are of the form of dP * * and can be uniquely specified by (CB in , SB in ) and (CB 0 , SB 0 ) respectively.
Corollary 5: For the variable node iteration of any (λ, ρ) irregular LDPC codes, we have An explicit expression for Φ k−1 involves a direct sum of various terms, the complexity of which grows at the order of k 3 . A more practical, fast implementation is via the fast Fourier transform (FFT), which is similar to that used in density evolution. We first calculate the LLR message distribution dP (m) for Ch 0 and Ch in from the upper bounding distribution dP * * (p) in (34). Since the output LLR is the summation of input LLRs, the distribution of the output LLR is the convolution of the input LLRs, which can be calculated by FFT. At the end, we can use (3) to compute the corresponding output SB value.

3) Two-dimensional Iterative Upper Bound U B CB,SB :
By combining the aforementioned upper bounds for the variable node and the check node iterations, we obtain a twodimensional iterative upper bound U B CB,SB . Since this twodimensional bound is based on separate analysis of variable nodes and parity check nodes, it can be applied to any LDPClike codes with graph-based ensembles without modification, including regular/irregular repeat accumulate (RA) codes [4], and joint-edge-distribution LDPC codes [32].
We omit the explicit expression for this two-dimensional bound since it is a direct concatenation of Theorems 5 and 6. By iteratively computing the upper bound (CB (l) , SB (l) ) and testing whether it converges to (0, 0), we can lower bound the decodable threshold for general BI-SO channels. The performance comparison of this procedure to existing results will be discussed in Section VII.

C. Some Notes on Searching for High-Dimensional Bounds
Under the framework proposed in the previous sections, the problem of constructing iterative upper/lower bounds is equivalent to solving a corresponding optimization problem, within which the "variables" correspond to the probabilistic weight, dP (p), of the corresponding BI-SO channel. Since most of the common noise measures of a BI-SO channel can be computed by the probabilistic average over the corresponding measures of the consitituent BSCs, both the constraints and the objective functions are generally linear with respect to dP (p). The optimization of interest becomes a linear programming (LP) problem, of which the methods of finding optimal solutions ares well studied. Two notes about searching for upper/lower bounds are worth mentioning. First, when considering high-dimensional objective functions, the corresponding LP problem generally does not admit a uniform optimizer, as shown in our (CB, SB) analysis in the previous sub-section, which hampers the use of simple channel replacement for bounding purpose. Second, the closed form solutions become more and more difficult to obtain when complicated constraints are applied, as demonstrated in (34). An alternative route is to use a commercial LP solver to numerically find bounds for each iteration. The closed form solution on the other hand is computationally much more efficient and provides better insight when compared to the numerical method. Since an iterative upper bound guarantees the minimum decodable threshold and is of higher importance from both the practical and theoretical perspectives, we use the two-dimensional upper bound to demonstrate this new framework and leave the two-dimensional lower bound for future research.

VI. A ONE-DIMENSIONAL NON-ITERATIVE BOUND ON BI-SO CHANNELS
In this section, we construct a non-iterative upper bound, which is the best known bound that is tight for BSCs.
First we introduce some new notation. Let p (l) e denote the bit error probability of the belief propagation after l iterations. To distinguish between the types of BI-SO channels on which we are focusing, we append an argument F C to the end of p (l) e . That is, p (l) e (F C ) denotes the bit error probability after l iterations with the conditional distribution of the BI-SO channel being F C := {f (y|x)}. In a similar fashion, we define CB (l) (F C ) as the Bhattacharyya noise parameter after l iterations with the BI-SO channel being F C , and SB (l) (F C ) is defined similarly. Following this definition, CB(F C ) := CB (0) (F C ) denotes the Bhattacharyya noise parameter of the uncoded BI-SO channel F C . For simplicity, we use F BSC,p to denote the F C of a BSC with crossover probability p, and similarly we define F BEC,ǫ . Suppose for some F BSC,p , the LDPC code ensemble is decodable. By the channel degradation argument in [6], one can show that all BI-SO channels F C with p (0) e (F C ) ≤p are also decodable, a formal statement of which is as follows.
Theorem 7 (The Channel Degradation Argument in [6]): Suppose F C is a BI-SO channel and F BSC,p is a BSC. If p e (F C ) = p e (F BSC,p ), then for any l ∈ N and any irregular (λ, ρ) LDPC codes, The above inequality holds as well when subsituting p (l) e (·) by other common noise measures including CB (l) (·), SB (l) (·), and the conditional entropy.
This result, though being tight for BSCs, generally gives a very loose bound for other channels. We strengthen this result by providing a strictly tighter bound in the following theorems.
Theorem 8: Suppose F C is a BI-SO channel and F BSC,p is a BSC. If SB(F C ) = SB(F BSC,p ), then for any l ∈ N and any irregular (λ, ρ) LDPC codes, which is different from the result using the channel degradation argument.
Proof: For any symmetric channel F C with SB(F C ) ≤ SB(F BSC,p * ), we consider a F BSC,p such that SB(F BSC,p ) = SB(F C ). Since F BSC,p * is physically degraded w.r.t. F BSC,p , F BSC,p is also decodable, namely, lim l→∞ p (l) e (F BSC,p ) = 0. By the relationship between p e and CB in Lemma 1 and by Theorem 8, we have This completes the proof. Corollary 6 can be used as a tight one-dimensional upper bound, which is denoted by U B * SB . A proof of Theorem 8 is given in APPENDIX VI. We close this section by providing a lemma showing that Theorem 8 is a strict improvement over Theorem 7, the channel degradation argument.
Lemma 3: Suppose F C is a BI-SO channel and F BSC,p is a BSC. If p e (F C ) = p e (F BSC,p ), then SB(F C ) ≤ SB(F BSC,p ). Therefore, Proof: Let dP FC (p) denote the probabilistic weight of the BSCs corresponding to the BI-SO channel F C . Since SB(F C ) = 4p(1 − p)dP FC (p), p e (F C ) = p dP FC (p), and 4p(1 − p) is a concave function of p, Lemma 3 is a simple result of Jensen's inequality.

VII. PERFORMANCE COMPARISONS
In this section, we compare the tightness of various lower bounds on the asymptotic decodable thresholds, obtained from the existing results and our results of Sections V-A, V-B, and VI.
Three existing results are included in TABLE I, including one based on the Bhattacharyya noise parameter [14], denoted as U B CB , one on the soft bit value [13], denoted as U B SB , and one on the conditional entropy H(X|Y ) [15], [16], denoted as U B inf o . U B CB,SB denotes the two-dimensional (CB, SB)-based bound provided in Section V-B, and U B * SB denotes the non-iterative tight bound given in Section VI. The DE column lists the asymptotic decodable thresholds obtained from density evolution [6]. In Section V-A, U B CB has been generalized for arbitrary BI-NSO channels. Therefore, the nonsymmetric z-channel 10 is also included for comparison, in which the asymptotic threshold is obtained from the generalized density evolution method for BI-NSO channels [17].
As proved in Section V-B and evidenced in TABLE I, the two dimensional bound U B CB,SB provides strict improvement over U B CB and U B SB . For channels that are neither BSC-like nor BEC-like, e.g. BiAWGNC and BiLC, the bound U B inf o found by Sutskover et al., is tighter than U B CB,SB while the two dimensional U B CB,SB is tighter at both extreme ends. This phenomenon can be explained by the convexity/concavity analysis of the transfer functions. For U B CB the bounding inequality resides in the check node iteration, in which BECs attain the equality. Therefore, U B CB is the tightest when channels are BEC-like. For U B SB , the bounding inequality resides in the variable node iteration, in which BSCs attain the equality, so U B SB is preferred for BSC-like channels. U B CB,SB thus has better performance in both extreme cases. On the other hand, U B inf o invokes bounding inequalities in both the variable node and the check node iterations. We observe that the absolute values of the curvatures of the transfer function is generally smaller when expressed in terms of the mutual information. Therefore, for the sake of insight, better predictability is obtained when the 10 The z-channel is a BNSC such that p 1→0 > 0 and p 0→1 = 0.
Comparisons of lower bounds on decodable thresholds. channel of interest is neither BSC nor BEC-like, e.g., the BiAWGN channel.
By Lemma 1, the feasible (CB, SB) pairs satisfy CB ≥ SB and (CB) 2 ≤ SB. By plotting general BI-SO channels according to their (CB, SB) values, the set of decodable channels forms a "decodable region" and Fig. 7 demonstrates the decodable region of regular (3,6) codes. The decodable region is plotted with a thicker boundary using the channels considered in TABLE I. The density evolution method does not guarantee that all channels with (CB, SB) inside the region are decodable. It is possible that two types of channels have the same (CB, SB) values but one is decodable while the other is not.
The vertical line in Fig. 7 marked by U B CB represents the inner bound of the decodable CB threshold [14]. The horizontal line marked by U B SB represents the inner bound of the decodable SB threshold. Our results on the twodimensional bound and the non-iterative tight bound greatly push the inner bounds of the decodable region toward its boundary (the curve marked U B CB,SB and the horizontal line marked by U B * SB ). These bounds guarantee that all BI-SO channels with (CB, SB) within the inner bounds are decodable under belief propagation decoding. In Section V-A, we have shown that the vertical line U B CB holds as an inner bound even for BI-NSO channels.
It is worth noting that all bounds for binary-input channels in Sections V and VI, are obtained by simple channel replacement. Our proofs show that replacement of any one of the constituent channels will result in a new upper/lower bounding tree channel, and the replacement of all constituent channels gives us an upper/lower bound admitting closed form solutions, as those shown in the previous sections. In some situations, it is more advantageous to replace only part of the constituent channels, which results in tighter bounds at the expense of more complicated/channel-dependent solutions. For example, Theorem 1 in [13] provides a different iterative upper bounding formula by substituting all (d v − 1) Ch in channels of a variable node with the corresponding maximizing BSCs while leaving the observation channel Ch 0 intact. The result is a channel-dependent iterative formula with tighter performance than the U B SB obtained by the replacement of all channels. The benefit of using selective channel replacement is also pointed out in [16].
A tight outer bound of the decodable region was proved by Burshtein et al. [13], illustrated by the horizontal line marked by LB SB in Fig. 7. Based on the mathematical symmetry between CB and SB in variable node and check node iterations, we conjecture the existence of a tight outer bound in terms of CB, which remains an open problem.

VIII. CONCLUSIONS
Finite dimensional bounds on the decodable thresholds find applications in both theoretical analysis and practical approximations. In this paper, we have developed a new iterative upper bound for Z m -based LDPC codes on MI-SO channels, which leads to a sufficient stability condition and provides insight into the analytical structure of general LDPC codes. Combined with a matching necessary stability condition proved herein, our stability condition pair can be used to derive the existing stability conditions for GF(q)-based LDPC codes.
Two new bounds for binary codes on BI-SO channels have also been constructed based on two types of noise measures, the Bhattacharyya noise parameter CB and the soft bit value SB. These bounds push the existing inner bounds of the decodable region toward its boundary. An iteration-based bound for general memoryless BI-NSO channels, which finds applications in optical channels or magnetic storage channels, has also been derived.
Throughout this paper, a new framework enabling systematic searches for more finite-dimensional bounds has been provided, under which we have modelled the iterative bounding problem by considering its probabilistic decomposition. The performance discrepancy among various bounds can be explained by the tightness of different bounds during the variable node and the check node iterations. Besides the implied uniform good performance over all types of channels, these new finite dimensional bounds and the proposed framework provide a useful tool for studying the behavior of iterative decoding.

APPENDIX I PROOF OF THE MSC DECOMPOSITION
Proposition 1: Any MI-SO channel, as illustrated in Fig. 8(a), can be converted to a probabilistic combination of many MSCs as in Fig. 8(c), the latter of which is equivalent to the original MI-SO channel from a detection point of view.
Proof: Without loss of generality, we assume Y, the set of possible received values, is discrete. Since the original channel Z m → Y is symmetric, by Definition 1, there exists a bijective transformation T : Y → Y such that T m (y) = y and ∀x ∈ Z m , F (dy|0) = F (T x (dy)|x). Using T , Y can be partitioned into many equivalence classes Y j ⊆ Y, j ∈ N, such that two elements y 1 and y 2 belong to the same class Y j if and only if there exists an x ∈ Z m such that y 1 = T x (y 2 ). The original MI-SO channel can then be converted to an equivalent x → (j, y) channel as in Fig. 8(b) such that y ∈ Y j and j ∈ N. Comparing Figs. 8(b) and (c), it remains to show that dP (j|x) does not vary for different values of x, and for any j, there exists a MSC(p) with parameter p such that F (dy|x, j) and the MSC(p) have the same distributions of the a posteriori probabilities regardless what type of the a priori distribution P (X) is considered. Since the a posteriori probabilities are the sufficient statistics of any detection problem, the latter statement implies that Figs. 8(b) and (c) are equivalent channels from the detection point of view.
We first show that dP (j|x) is not a function of x. By the construction of Y j and by Definition 1, we have where (a) follows from the fact that Y j is an equivalence class derived from the bijective transformation T .
The second statement says that for every value j of the channel output in Fig. 8(b), there exists a side information value p in Fig. 8(c) such that the posterior distribution P(x|Y j , j) from Fig. 8(b) is identical to the posterior distribution P(x|Y, p) from Fig. 8(c). To this end, we first let y 0 denote a "fixed" representative element of the non-empty 11 class Y j from Fig. 8(b). We then define y i = T i (y 0 ). For Fig. 8(c), consider a MSC(p) with its parameter vector p = (p 0 , · · · , p m−1 ) 11 Without loss of generality, we may assume Y j is non-empty, since an empty class is of little interest. defined as follows: where "∝" means p i is proportional to the right-hand side while satisfying i∈Zm p i = 1. The prior distribution of X is the same for all models in Fig. 8 and is denoted by P(X = i) = χ i , ∀i ∈ Z m . In the following proofs, it should be clear from the context which channel model in Fig. 8 we are considering.
Suppose y i0 ∈ Y j is received for Fig. 8(b). Then the a posteriori probabilities of X = 0, 1, · · · , m−1 given Y j and j are proportional to (P(y i0 |0, j)χ 0 , P(y i0 |1, j)χ 1 , · · · , P(y i0 |m − 1, j)χ m−1 ). Again by the symmetry of the original channel, the a posteriori probabilities can be rewritten as By noting that the last equation also specifies the a posteriori probabilities given Y = i 0 from a MSC(p) with p specified in (36), it is proven that with y i0 and i 0 being the received values respectively, the partitioned channel Z m → Y j in Fig. 8(b) has the same a posteriori probabilities as the MSC(p) in Fig. 8(c). To complete the proof that the partitioned channel F (dy|x, j) has the same distribution of the a posteriori probabilities as the MSC(p), we need only to prove that the probability that y i0 ∈ Y j is received (in the partitioned channel F (dy|x, j)) is the same as the probability that i 0 ∈ Z m is received (in the MSC(p)).
First consider the case in which y i = y i0 ∀i = i 0 , and we then have |Y j | = m. Therefore instead of being only proportional to the right-hand side. We then have For the case in which ∃i = i 0 such that y i = y i0 , unfortunately, P(Y = y i0 |Y ∈ Y j ) does not equal P(the output of the MSC(p) is i 0 ). However, it can be shown that all such i's with y i = y i0 will result in the same a posteriori probabilities. Furthermore, one can prove that P(Y = y i0 |Y ∈ Y j ) = P(the output i of the MSC(p) satisfies y i = y i0 ).
From the above discussion, the distribution of the a posteriori probabilities are the same for the partitioned channel F (dy|x, j) and the MSC(p). The proof is thus complete.
APPENDIX II PROOF OF THE RELATIONSHIP AMONG CB, SB, AND p e Without loss of generality, we assume the conditional probability P(Y |X) is discrete, and all our derivations can be easily generalized to continuous/mixed situations.
Proof of Lemma 1: We use q x,y := P(X = x, Y = y) to denote the joint probability of X = x and Y = y. By definition, we have p e = y∈Y min(q 0,y , q 1,y ) CB = 2 y∈Y √ q 0,y q 1,y SB = 2 y∈Y 2q 0,y q 1,y q 0,y + q 1,y .

Proof of Lemma 2:
Define p e,0↔x as the bit error probability of the MAP detector given that the input X is uniformly distributed on {0, x}, namely, where P X∈uA (·) denotes the probability assuming X is evenly distributed on A ⊆ Z m . We note that X ∈ u {0, x} is equivalent to a binary-input channel with input alphabet {0, x}.
From the above inequalities, the proof of Lemma 2 can be completed by proving We need only to prove the result for the MSC case, and the proof for general MI-SO channels then follows by taking the probabilistic average of the constituent MSCs. For an MSC with the parameter vector p = {p 0 , · · · , p m−1 }, we have p e = 1 − max(p 0 , p 1 , · · · , p m−1 ).
Without loss of generality, we may assume p 0 is the maximum entry in p and p e = 1−p 0 . Then for any x = 0, we can rewrite p e,0↔x as and the first half of Ineq. (40) is proved. Also by Eq. (41) and the assumption that p 0 is the maximal component of p, we have Summing over all possible x ∈ Z m \{0}, the second half of (40) is also proved.
APPENDIX III NECESSARY STABILITY CONDITION FOR Z m LDPC CODES An x-erasure MSC can be defined by specifying its parameter vector p as p 0 = 1/2, p x = 1/2 and p z = 0, ∀z / ∈ {0, x}. Consider an x-erasure Z m → Z m MSC, and suppose 0 ∈ Z m is received. From these specified conditional probabilities, p 0 , · · · , p m−1 , it is impossible for the receiver to determine whether the transmitting signal is X = 0 or X = −x when a receiving value is Y = 0, which is as if we are facing a BEC, for which all information regarding X = 0 and X = −x is erased. However, there is a fundamental difference between an x-erasure MSC and a BEC such that if we use X = {0, −x ′ } for tranmission instead, the xerasure MSC becomes a noiseless perfect channel assuming x ′ = x. In this section, we will use e x to denote this particular parameter p. An x-erasure decomposition lemma is given as follows.
Lemma 4 (x-erasure Decomposition): Consider any MI-SO channel with pairwise MAP error p e,0↔x defined in (39). This MI-SO channel can be written as a degraded channel MI-SO Channel of a probabilistic composition of two MSCs, of which the probabilistic weight dQ e (q) is defined as follows: .

Proof:
We need only to prove Lemma 4 for an MSC with arbitrary parameter p. By taking the average over dP (p), the same result holds for general MI-SO channels.
We first note that dQ e (·) can be viewed as a Z m → ({0, 1} × Z m ) channel, where the first output component is 1 iff q = e x . Let p denote the parameter of the original MSC. We would like to show that there exists another channel F such that after concatenating dQ e (·) and F , we can reproduce the probability law p of the original MSC. To be more explicit, F is a ({0, 1} × Z m ) → Z m channel such that the concatenation Z m → ({0, 1} × Z m ) → Z m becomes an MSC with parameter p. We prove the existence of F by explicitly specifying its probability law.
When the first component of the input of F is given, say 0 or 1, let the remaining Z m → Z m channel be an MSC with parameter r or with parameter s (depending on the first component being 0 or 1). Define, ∀i ∈ Z m , .
It is easy to check that both r and s are valid parameter vectors. It is also straightforward to check that the end-to-end dQ e • F channel is an MSC. By noting that 2p e,0↔x = z∈Zm min(p z , p z+x ), we can verify that the end-to-end channel has the same parameter p as the original MSC.
Another necessary lemma is stated as follows. e,0↔x > 0. Proof: As l grows, the support tree gives more information by providing additional observations. As a result, the MAP error p (l) e,0↔x is non-increasing as a function of l. For the second statement, we break one iteration into its check node part and its variable node part. Since a check node channel is a degraded channel with respect to each of its constituent channels, we have p e,0↔x is the pairwise error probability of the support tree of depth 2l + 1 (after incorporating the check node). For variable nodes, by the equation CB var = CB in,1 • CB in,2 , we have p e,0↔x0 } l∈N is a strictly positive sequence with limit 0. Therefore, for a sufficiently small ǫ > 0, there exists an l 0 such that p (l0) e,0↔x0 < ǫ. Without loss of generality, we may assume p (l0) e,0↔x0 = ǫ > 0. By Lemma 4, we can replace a supporting tree channel of depth 2l 0 by a probabilistic combination of a perfect channel and an x 0 -erasure channel with weights (1 − 2ǫ, 2ǫ), which is denoted by dQ e (q). Similarly, for a supporting tree channel of depth 2(l 0 + ∆l), we can replace each of its youngest subtrees of depth 2l 0 by a dQ e (q) channel, so that after subsititution, the new channel becomes a supporting tree channel with depth 2∆l and all its youngest descendants are dQ e (q) channels. We then use p For notational simplicity, we define the output of an x 0erasure channel to be +0 if the output satisfies Y = X + 0. Similarly, an x 0 -erasure channel outputs +x 0 if the output satisfies Y = X + x 0 . For ∆l = 1, we consider the new support tree channel of depth 2, namely, only one iteration of check node and variable node is considered. Readers are referred to Fig. 4 for illustration of a regular (2,3) LDPC code, in which both dP 5 and dP 6 should have the form of dQ e (q). Each check node constituent channel (CNCC), that is dP 5 or dP 6 in Fig. 4, can be either a noiseless perfect channel (with probability 1 − 2ǫ) or an x 0 -erasure (with probability 2ǫ). If none of the check node constituent channels (CNCCs) is x 0erasure, we can successfully decode the original input X with no error. The cases that more than two CNCCs are x 0 -erasure only happen with probability O(ǫ 2 ), and are of less importance in the asymptotic analysis. Therefore we focus only on the case in which one and only one CNCC is x 0 -erasure. Furthermore, since the input X and the input of the individiual CNCC satisfy a parity check equation, the only sub-case in which there is no additional information (from the CNCCs) distinguishing X = x 0 from X = 0 is when the x 0 -erasure CNCC has an output providing no information for detecting −x 0 from 0. We then have (42).
The inequality (a) in (42) follows from the fact that +0 is an output that the x 0 -erasure CNCC cannot distinguish −x 0 from 0. Therefore, the event of misdetecting X = 0 by X = x 0 contains the case in which the CNCC outputs +0 given X = 0. Similarly, +x 0 is an output providing no information distinguishing 0 from x 0 , which is thus contained by the event of misdetecting X = x 0 by X = 0. 2ǫλ 2 ρ ′ (1) is the probability that one and only one CNCC is x 0 -erasure, and 2ǫλ2ρ ′ (1) 2 corresponds to the probability for which the x 0erasure channel outputs +0 (or +x 0 ). m x = log P(Y =y|X=0) is the LLR between X = 0 and X = x, and dP x (·) is the density of the initial LLR message m x given X = 0. Equality (b) in (42) follows from the fact that with the only x 0 -erasure CNCC providing no information, misdectection happens when the original channel observation also provides an incorrect LLR message.
Note: If x 0 = −x 0 in Z m , the inequality becomes an equality. If x 0 = −x 0 in Z m , then q (1) e,0↔x0 equals twice the right-hand side of the above expression.

APPENDIX IV THE MAXIMIZING DISTRIBUTION FOR CHECK NODES
WITH CONSTRAINTS ON (CB in , SB in ) Proof: We take the approach of considering the marginal dP first and assuming that dQ is a point mass, i.e., dQ concentrates all its probability on a fixed q 0 . To simplify the notation, we let a := 2 p(1 − p) and b := 2 q 0 (1 − q 0 ), and drop the subscript 1 in (CB in,1 , SB in,1 ) to (CB in , SB in ). The original problem (31) becomes a linear programming problem on dP : Note: From the BSC decomposition perspective, dP (·) denotes the probabilistic weight for different BSCs, which can be indexed by p or by a = 2 p(1 − p) at one's will. Previously, dP (·) denotes the probabilistic weight for different BSCs indexed by p. Here the notation is slightly abused so that dP (·) also denotes the probabilistic weight for different BSCs indexed by a = 2 p(1 − p).
The corresponding dual problem is min y0,y1,y2 It is easy to check that both y * 1 , y * 2 ≥ 0. By Lemma 6 (stated at the end of this proof), y * ∆ = (y * 0 , y * 1 , y * 2 ) is a feasible solution. Let It can be verified that the duality gap between the two feasible solutions y * and dP * is zero. By the weak duality theorem of linear programming, dP * is the maximizing distribution when dQ concentrates on q 0 . Since dP * does not depend on b (and thus does not depend on q 0 ), dP * is the universal maximizer for general dQ. Lemma 6: y * 0 + ay * 1 + a 2 y * 2 ≥ a 2 (1 − b 2 ) + b 2 for all a, b ∈ [0, 1].
We take the approach of assuming dQ concentrates on a fixed q 0 . Let a := 2 p(1 − p) and b := 2 q 0 (1 − q 0 ) and drop the subscript 1 in (CB in,1 , SB in,1 ) to write (CB in , SB in ). The original problem (33) becomes a linear programming problem with the primal and dual representations as follows.
For convenience, we define t := SB in /CB in and r b (a) := Unlike the check node channel case, this time the optimal primal solution dP * (a) depends on the value of b, and different values of b will lead to different closed form solutions of the optimizer dP * (a). The effect of different b's can be summarized as three different cases in which b belongs to one of the following three intervals, 0, 1+t 2 , and t 2 1+t 2 , 1 , respectively.
, the maximizing dP * (a) and the optimum values are as follows.
Proof: It is easy to check that the specified dP (a) is feasible. We then note that r b (0) = 0, and 1 2 b 2 1−b 2 ·a is the only tangent line of r b (a) passing through the origin (with the contact point a t = b 2 is the convex hull of r b (a). By Jensen's inequality, Since dP * (a) in (44) achieves the upper bound in (46), it is indeed the maximizing distribution.
1+t 2 , the maximizing dP * (a) and the optimum values are as follows.
Proof: It is easy to check that the specified dP * (a) is feasible. By again invoking Jensen's inequality on u b (a) defined in (45), we have Since dP * (a) in (47) achieves the upper bound in (48), it is indeed the maximizing distribution.
1+t 2 , 1 , the maximizing dP * (a) and the optimum values are as follows.
Proof: It is easy to check that the specified dP * (a) is feasible. By choosing we have ξ * = SBinb 2 t 2 (1−b 2 )+b 2 = ζ * . So it remains to show that y * = (y * 0 , y * 1 , y * 2 ) is feasible for all b ∈ [0, 1]. Let g(a) := ay * 1 + a 2 y * 2 − r b (a). By the following observations , which can be proved by exactly the same argument as in the proof of Lemma 6. We then consider the case a ∈ [ 1−b 2 , 1]. From the above reasoning, we have g(a) ≥ 0 for all a, b ∈ [0, 1], and thus y * is feasible and the proposition follows.
From Propositions 2 to 4, we have the following tight upper bound: Hereafter, we will show that the b-value-independent dP * * (a) in (34) is an upper bounding distribution, such that dP * * (a) may not be feasible, but the resulting r b (a)dP * * (a) is no smaller than s(CB in , SB in , b) for all b ∈ [0, 1].
Lemma 7: r b (a)dP * * (a) ≥ s(CB in , SB in , b) for all b ∈ [0, = a 2 = 4p(1 − p) for different BSCs and dP (α) now denotes the corresponding probabilistic weight for BSCs indexed by α, which is different from the dP (p) and dP (a) discussed previously. We can rewrite r b (a) with respect to the new index α such that it becomes r b (α) = αb 2 α(1−b 2 )+b 2 , the SB value when the constituent BSCs are indexed by α and b respectively.
It can be shown that d 2 r b (α) dα 2 ≤ 0 and r b (α) is a concave function of α. By noting that αdP * * (α) = SB in and the weights in dP * * (α) are concentrated only on three points α = CB 2 in , SB in , and t 2 in an increasing order, we have r b (α)dP * * (α) ≥ A 1 , where A 1 is the intersection of the vertical line α = SB in and the chord connecting CB 2 in , r b (CB 2 in ) and t 2 , r b (t 2 ) . We also notice that s(CB in , SB in , b) is the intersection of the vertical line α = SB in and the chord connecting (0, r b (0)) and t 2 , r b (t 2 ) . By the concavity of r b (α), we conclude r b (α)dP * * (α) ≥ A 1 ≥ s(CB in , SB in , b).

APPENDIX VI PROOF OF Theorem 8
We provide a proof of a more general theorem, which includes general error correcting codes and multiuser detection as special cases and is formally stated as follows.
As in Fig. 9, consider any deterministic/randomized sequence mapper 12 C : {0, 1} → {0, 1} n and W = C(X). Each coordinate W i of W is passed through independent BI-SO channels F i := {f i (y|w)} to generate the observation Y i , i ∈ {1, 2, · · · , n}. LetX(Y) be the MAP detector, and define where for any i,p i satisfies 4p i (1 −p i ) = 4p(1 − p)dP i (p). The integrator dP i (p) is the equivalent probabilistic weight in the BSC decomposition of channel F i as described in Section II-A.2. Theorem 8 is a special case of Theorem 9 obtained by letting X → C(X) be the binary-input/vector-output support tree channel.
By repeatedly applying this CB-increasing channel replacement until all constituent channels F i are replaced by F BSC,pi , the proof of Theorem 9 is complete.
Proposition 5: For any constants a, b, c, d ≥ 0 and p ∈ [0, 1/2], we have (a(1 − p) + cp) (b(1 − p) + dp) is a concave function of β := 4p(1 − p). Proof: This proof involves several changes of variables. It is worth noting that this proposition is a pure algebraic statement and the notations involved herein are irrelevant to those of the LDPC code problem.
We first let X = 1 − 2p, A = a+c |a−c| , and B = b+d |b−d| . Then the problem becomes to prove that both are concave functions of β = 1 − X 2 , for all A, B ∈ [1, ∞] and X ∈ [0, 1]. We focus on the concavity of f (X) first. Using the chain rule, Since d 2 f (X) To show f 2 (X) ≥ 0, we first note that f 2 (0) = 0. Its first derivative is By Lemma 10 (stated at the end of this proof), we have df2(X) dX ≥ 0. Thus f 2 (X) ≥ 0, which implies that f (X) is concave as a function of β.
For g(X), we have Since To show g 2 (X) ≥ 0, we first note that g 2 (0) = 0. Its first derivative is By Lemma 10, we have dg2(X) dX ≥ 0, which implies that g(X) is concave as a function of β. This completes the proof of Proposition 5.
For the second inequality, without loss of generality, we assume a ≤ b. We then observe that Considering (53), after multiplying the non-negative second term (b+c)−a (b+c)a by a larger factor This completes the proof.