advertisement

SUBMITTED TO IEEE TRANSACTIONS ON INFORMATION THEORY 1 On the Pseudocodeword Redundancy of Binary Linear Codes arXiv:1103.3641v2 [cs.IT] 6 Mar 2012 Jens Zumbrägel, Member, IEEE, Vitaly Skachek, Member, IEEE, and Mark F. Flanagan, Senior Member, IEEE Abstract—The AWGNC, BSC, and max-fractional pseudocodeword redundancies of a binary linear code are defined to be the smallest number of rows in a parity-check matrix such that the corresponding minimum pseudoweight is equal to the minimum Hamming distance of the code. It is shown that most codes do not have a finite pseudocodeword redundancy. Also, upper bounds on the pseudocodeword redundancy for some families of codes, including codes based on designs, are provided. The pseudocodeword redundancies for all codes of small length (at most 9) are computed. Furthermore, comprehensive results are provided on the cases of cyclic codes of length at most 250 for which the eigenvalue bound of Vontobel and Koetter is sharp. Index Terms—LDPC codes; Fundamental cone; Pseudocodewords; Pseudoweight; Pseudocodeword redundancy. I. I NTRODUCTION P SEUDOCODEWORDS represent the intrinsic mechanism of failure of binary linear codes under linearprogramming (LP) or message-passing (MP) decoding (see, e.g., [1], [2]). The concept of pseudoweight of a pseudocodeword was introduced in [3] and [4] (see also [2]) as an analog to the pertinent parameter in the maximum likelihood (ML) decoding scenario, i.e., the signal Euclidean distance in the case of the additive white Gaussian noise channel (AWGNC), or the Hamming distance in the case of the binary symmetric channel (BSC). Accordingly, for a binary linear code C and a parity-check matrix H of C, the (AWGNC or BSC) minimum pseudoweight wmin(H) may be considered as a first-order measure of decoder error-correcting performance for LP or MP decoding. Another closely related measure is the maxfractional weight, which we sometimes also call pseudoweight in order to simplify statements; it serves as a lower bound on both AWGNC and BSC pseudoweights. In order to minimize the decoding error probability under LP (or MP) decoding, one might want to select a matrix H This work was supported in part by Science Foundation Ireland (Grants 06/MI/006, 08/IN.1/I1950, and 07/SK/I1252a). The work of V. Skachek was also supported in part by the National Research Foundation of Singapore (Research Grant NRF-CRP2-2007-03). The material in this paper was presented in part at the IEEE International Symposium on Information Theory, Austin, TX, USA, June 2010, and at the 19th International Symposium on Mathematical Theory of Networks and Systems, Budapest, Hungary, July 2010. J. Zumbrägel and M. F. Flanagan are with the Claude Shannon Institute, University College Dublin, Belfield, Dublin 4, Ireland. E-mails: jens.zumbragel@ucd.ie, mark.flanagan@ieee.org. V. Skachek is with the Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, 1308 W. Main Street, Urbana, IL 61801, USA. E-mail: vitalys@illinois.edu. The work of this author was done in part while he was with the Claude Shannon Institute, University College Dublin, Belfield, Dublin 4, Ireland, and with the Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, 21 Nanyang Link, 637371 Singapore. which maximizes the minimum pseudoweight of the code for the given channel. Adding redundant rows to the paritycheck matrix introduces additional constraints on the so-called fundamental cone, and thus may improve the performance of LP decoding and increase the minimum pseudoweight.1 However, such additions increase the decoding complexity under MP decoding, especially since linear combinations of low-density rows may not yield a low-density result. On the other hand, there exist classes of codes for which sparse paritycheck matrices exist with many redundant rows, e.g., [5]. For the AWGNC, BEC (binary erasure channel), BSC, and max-fractional pseudoweights, define ρAWGNC (C), ρBEC (C), ρBSC (C), and ρmax-frac (C), respectively, to be the minimum number of rows in any parity-check matrix H such that the minimum pseudoweight of C with respect to this matrix is equal to the code’s minimum Hamming distance d. For the sake of simplicity, we sometimes use the notation ρ(C) when the type of channel is clear from the context. The value ρ(C) is called the (AWGNC, BEC, BSC, or max-fractional) pseudocodeword redundancy (or pseudoredundancy) of C. If for the code C there exists no such matrix H, we say that the pseudoredundancy is infinite. The BEC pseudocodeword redundancy, which is equivalent to the stopping redundancy, is studied in [6], where it is shown that for any linear code the BEC pseudoredundancy is finite; the paper also contains bounds on ρBEC (C) for general binary linear codes, and for some specific families of codes. These bounds were subsequently improved, for instance in [7]. The study of BSC pseudoredundancy was initiated in [8], where the authors presented bounds on ρBSC (C) for various families of codes. In this work, we further investigate pseudoredundancy for the AWGNC, BSC, and max-fractional pseudoweight. We show that for most codes there exists no H such that the minimum pseudoweight (with respect to H) is equal to d, and therefore the AWGNC, BSC, and max-fractional pseudocodeword redundancy (as defined above) is infinite for most codes. For some code families for which the pseudoredundancy is finite, we provide upper bounds on its value. We consider in particular constructions of new codes from old and codes based on designs. Furthermore, we compute the pseudocodeword redundancies for all codes of small length (at most 9), and we investigate cyclic codes for which the eigenvalue bound of Vontobel and Koetter [9] is sharp. 1 We note that for message-passing iterative decoding, apart from the case of decoding over the binary erasure channel there is no general statement that additional parity-checks are beneficial. 2 SUBMITTED TO IEEE TRANSACTIONS ON INFORMATION THEORY The outline of the paper is as follows. In Section II we provide detailed definitions and some background information on LP decoding, pseudocodewords, the minimum pseudoweight, and the pseudocodeword redundancy; we also discuss related notions appearing in the literature. Subsequently, we show in Section III that the pseudocodeword redundancy for random codes is infinite with high probability. The next four sections are concerned with upper bounds on the pseudoredundancy for some particular classes of codes; we investigate punctured codes and codes of dimension 2 in Section IV, constructions of codes from other codes in Section V, parity-check matrices of row-weight 2 in Section VI, and codes based on designs in Section VII. The final two sections are devoted to experimental results; Section VIII examines the pseudocodeword redundancy for all codes of small length, and Section IX deals with cyclic codes that meet the eigenvalue bound on the minimum AWGNC pseudoweight by Vontobel and Koetter. a subset of {0, 1}n ⊂ Rn , one can then express ML decoding as the minimization problem △ x̂ = arg min hx, γi . x∈C This is equivalent to the linear programming problem △ x̂ = arg min hx, γi , x∈conv(C) where conv(C) denotes the convex hull of C in Rn . However, since the number of defining hyperplanes of conv(C) usually grows exponentially with the block length, this minimization problem becomes impractical. Instead one might consider a relaxation of the above minimization problem (see [10], [11], [2]), where the convex hull conv(C) is replaced by the so-called fundamental polytope P(H) to be defined next. For j ∈ J , let hj denote the j-th row of the parity-check matrix H, and consider the local code II. G ENERAL S ETTINGS Cj = {c ∈ Fn2 | hj cT = 0} Let F2 be the binary field and let R be the field of real numbers. Addition and multiplication (including matrix-vector and matrix-matrix multiplication) are carried out in F2 when the operands are defined over F2 , and in R when the operands are defined over the reals. Occasionally, we will explicitly convert elements in F2 into real numbers; in this case we identify 0 ∈ F2 with 0 ∈ R and 1 ∈ F2 with 1 ∈ R. Let C be a code of length n ∈ N over the binary field F2 , defined by consisting of all T binary vectors satisfying the j-th parity-check, △ so that C = j∈J Cj . Then the fundamental polytope P = P(H) is defined as \ △ P= conv(Cj ) , C = ker H = {c ∈ Fn2 | HcT = 0T } j∈J where again Cj is viewed as a subset of Rn . Now LP decoding of a binary linear code C with parity-check matrix H can be expressed as the minimization problem △ x̂ = arg min hx, γi , (1) x∈P where H is an m × n parity-check matrix over F2 of the code C. Obviously, the code C may admit more than one paritycheck matrix, and all the codewords form a linear vector space of dimension k ≥ n−m. We say that k is the dimension of the code C. We denote by d(C) (or just d) the minimum Hamming distance (also called the minimum distance) of C. The code C may then be referred to as an [n, k, d] linear code over F2 . Denote the set of column indices and the set of row indices of the parity-check matrix H by I = {1, . . . , n} and J = {1, . . . , m}, respectively. For any row index j ∈ J we let △ Ij = {i ∈ I | Hj,i 6= 0} denote the set of the column indices where the parity-check matrix is nonzero; similarly for any △ column index i ∈ I we let Ji = {j ∈ J | Hj,i 6= 0} denote the corresponding set of row indices. The matrix H is said to be (wc , wr )-regular if |Ji | = wc for all i ∈ I and |Ij | = wr for all j ∈ J ; a (w, w)-regular matrix is also called simply w-regular. A. LP decoding We give a brief review of LP decoding. Consider data transmission over a memoryless binary-input output-symmetric channel with channel law pY |X (y|x). Based on the received vector y = (y1 , . . . , yn ) we can define the log-likelihood-ratio △ vector γ = (γ1 , . . . , γn ) ∈ Rn by γi = log(pY |X (yi |0)) − log(pY |X (yi |1)) for i ∈ I. Viewing the code C canonically as where P = P(H) denotes the fundamental polytope. We note that conv(C) ⊆ P, where the inclusion is usually proper. However, the number of defining hyperplanes of P is typically much smaller than for conv(C), in particular for LDPC codes, so that the corresponding linear programming problem becomes tractable. If P is strictly larger than conv(C) then it may happen that the decoding rule (1) outputs a vertex2 of P that is not a vertex of conv(C), i.e., not a codeword. Such vertices, called pseudocodewords, are the reason for the suboptimality of LP decoding with respect to ML decoding. Note that the fundamental polytope P(H) is dependent on the parity-check matrix H rather than the code C itself, but we always have P(H) ∩ {0, 1}n = C, cf. [10], [11]. B. The fundamental cone and pseudoweights When analyzing LP decoding, we may assume without loss of generality that the zero codeword 0 has been sent; then, given this assumption, the probability of correct LP decoding depends only on the conic hull of the fundamental polytope rather than on the fundamental polytope itself (see [10], [11], [2]). The conic hull of the fundamental cone P(H) is called 2 The set of optimal solutions contains a vertex, and one may assume that the output is a vertex. ZUMBRÄGEL, SKACHEK, AND FLANAGAN: ON THE PSEUDOCODEWORD REDUNDANCY the fundamental cone K(H). More concretely, K(H) is given as the set of vectors x ∈ Rn that satisfy X xi , (2) ∀j ∈ J , ∀ℓ ∈ Ij : xℓ ≤ i∈Ij \{ℓ} ∀i ∈ I : xi ≥ 0 . (3) The vectors x ∈ K(H ) are called pseudocodewords3 of C with respect to the parity-check matrix H. Note again that the fundamental cone K(H) depends on the parity-check matrix H rather than on the code C itself. At the same time, the fundamental cone is independent of the underlying communication channel. Example 2.1: Let C be the [7, 4, 3] Hamming code with parity-check matrix H = 1 0 1 1 1 1 0 1 1 0 0 1 0 0 0 0 1 1 1 0 1 . Then the fundamental cone inequalities read: x1 ≤ x2 + x3 + x5 x2 ≤ x3 + x4 + x6 x3 x2 ≤ x1 + x3 + x5 x3 ≤ x2 + x4 + x6 x4 x3 ≤ x1 + x2 + x5 x4 ≤ x2 + x3 + x6 x5 x5 ≤ x1 + x2 + x3 x6 ≤ x2 + x3 + x4 x7 0 ≤ x1 0 ≤ x2 0 ≤ x3 0 ≤ x4 0 ≤ x5 ≤ x4 + x5 + x7 ≤ x3 + x5 + x7 ≤ x3 + x4 + x7 ≤ x3 + x4 + x5 0 ≤ x6 0 ≤ x7 The influence of a nonzero pseudocodeword on the decoding performance will be measured by its pseudoweight, which depends on the channel at hand. The BEC, AWGNC, BSC pseudoweights, and max-fractional weight of a nonzero pseudocodeword x ∈ K(H ) were defined in [4] and [2] as follows: △ wBEC (x) = |supp(x)| , 2 P △ i∈I xi wAWGNC (x) = P 2 . i∈I xi Let x′ be a vector in Rn with the same components as x but in non-increasing order. For i − 1 < ξ ≤ i, where 1 ≤ i ≤ n, △ △ Rξ let φ(ξ) = x′i . Define Φ(ξ) = 0 φ(ξ ′ ) dξ ′ and wBSC (x) = 2 Φ−1 (Φ(n)/2) . △ Finally, the max-fractional weight of x is defined as P △ i∈I xi . wmax-frac (x) = maxi∈I xi Additionally, the pseudoweight of the all-zero vector is usually defined to be zero, i.e., w(0) = 0, for all four pseudoweights w, but this is inessential for this paper. Note that for binary vectors x ∈ {0, 1}n \ {0} we have wBSC (x) = wAWGNC (x) = wBSC (x) = wmax-frac (x) = wH (x) , where wH (x) denotes the Hamming weight of x. Example 2.2: Let C and H be as in Example 2.1. The vector x = (0, 0, 1, 0, 1, 1, 2) is a pseudocodeword 3 Some authors consider only the vertices of the fundamental polytope P(H) as pseudocodewords, but we will use this more general definition which includes all vectors of the fundamental cone K(H). 3 in K(H) with weights wBEC (x) = |supp(x)| = 4 and P 2 P wAWGNC (x) = / i∈Ix2i = 25/7. Furthermore, i i∈I x P −1 wBSC (x) = 2 Φ ( i∈I xi )/2 = 2 Φ−1 (5/2) = 3, ′ where x = (2, 1, 1, 1, 0, 0, 0), and finally, wmax-frac (x) = P i∈I xi / maxi∈I xi = 5/2. We define the BEC minimum pseudoweight of the code C with respect to the parity-check matrix H as △ BEC wmin (H) = min x∈K(H)\{0} wBEC (x) . AWGNC BSC max-frac The quantities wmin (H), wmin (H) and wmin (H) are defined similarly. We note that the considered pseudoweights are invariant under scaling by a positive scalar, and that a minimum is indeed attained on K(H) \ {0} (see [2, Sect. 6]). When the type of pseudoweight is clear from the context, we sometimes use the notation wmin (H). Note that all four minimum pseudoweights are upper bounded by d, the code’s minimum distance. C. Pseudocodeword redundancy Given a code C we will define the pseudocodeword redundancy as the minimum number of rows in a paritycheck matrix H for C such that the corresponding minimum pseudoweight equals the minimum distance. So for a binary linear [n, k, d] code C we define the BEC pseudocodeword redundancy of the code C as △ BEC ρBEC (C) = inf{#rows(H) | ker H = C , wmin (H) = d} , △ where inf ∅ = ∞, and similarly we define the pseudocodeword redundancies ρAWGNC (C), ρBSC (C), and ρmax-frac (C) for the AWGNC and BSC pseudoweights, and the max-fractional weight. When the type of pseudocodeword redundancy is clear from the context, we sometimes use the notation ρ(C). We remark that all pseudocodeword redundancies satisfy △ ρ(C) ≥ r = n − k. Example 2.3: Let C be the [7, 4, 3] Hamming code. Then: ρmax-frac (C) = 7 ≥ ρAWGNC (C) = 3 ≥ ρBEC (C) = 3 ρmax-frac (C) = 7 ≥ ρBSC (C) = 4 ≥ ρBEC (C) = 3 The following matrices H 3 , H 4 , and H 7 are examples for parity-check matrices with a minimum number of rows such BEC AWGNC BSC that wmin (H 3 ) = wmin (H 3 ) = 3, wmin (H 4 ) = 3, and max-frac wmin (H 7 ) = 3 holds. H3 = H4 = H7 = 1 0 1 1 1 1 0 1 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 1 1 0 0 1 0 0 1 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 1 1 1 0 1 0 0 0 1 1 1 0 1 0 0 1 0 0 1 0 1 1 1 1 0 1 1 0 0 1 0 0 1 1 1 1 1 0 1 1 0 0 1 0 0 1 0 1 1 4 SUBMITTED TO IEEE TRANSACTIONS ON INFORMATION THEORY These matrices were found by computer search, see Section VIII. We describe the behavior of the pseudocodeword redundancy and the minimum pseudoweight for a given binary linear [n, k, d] code C by introducing four classes of codes: (class 0) ρ(C) is infinite, i.e., there is no parity-check matrix H with d = wmin (H), (class 1) ρ(C) is finite, but ρ(C) > r, (class 2) ρ(C) = r, but C is not in class 3, (class 3) d = wmin (H) for every parity-check matrix H of C. Note that if a code has infinite pseudocodeword redundancy, then LP decoding for this code can never achieve the ML decoding performance; on the other hand, if a code’s pseudocodeword redundancy is finite, its value gives a (very approximate) indication of the LP decoding complexity required to achieve this bound. Note that this is a fundamental complexity associated with the code, and not tied to a particular parity-check matrix. We leave it as a direction for further research to provide more general definitions which capture the average complexity-performance tradeoff of LP decoding as more redundant rows are added to the parity-check matrix. D. Basic Connections The different minimum pseudoweights are related as follows. This result is taken from [2]. Lemma 2.4: Let C be a binary linear code with the paritycheck matrix H. Then, max-frac AWGNC BEC wmin (H) ≤ wmin (H) ≤ wmin (H) , max-frac BSC BEC wmin (H) ≤ wmin(H) ≤ wmin (H) . As a straightforward corollary we obtain the following theorem, which relates the different pseudoredundancies. Theorem 2.5: Let C be a binary linear code. Then, ρmax-frac (C) ≥ ρAWGNC (C) ≥ ρBEC (C) , a characterization of all geometrically perfect codes: a binary linear code C is geometrically perfect if and only if C does not contain as a minor4 any code equivalent to certain codes C1 , C2 , C3 with parameters [7, 3, 4], [10, 5, 4], and [10, 4, 4], respectively. It is easy to see that for geometrically perfect codes all four pseudocodeword redundancies are finite. Smarandache and Vontobel [15] define the pseudoweight spectrum gap for a binary linear code C given by a paritycheck matrix H as follows. The set M(H) of all minimal pseudocodewords is defined as the set of all vectors x ∈ Rn that lie on an edge of the fundamental cone K(H). Now let M′ (H) denote the set of all minimal pseudocodewords that are not scalar multiples of codewords c ∈ C, and let w be any of the BEC, AWGNC, BSC, or max-fractional pseudoweight. Then the pseudoweight spectrum gap is the quantity △ g(H) = III. P SEUDOREDUNDANCY OF R ANDOM C ODES In this section we show that for most binary linear codes the AWGNC and BSC pseudoredundancies are infinite. We begin with the following lemma. Lemma 3.1: For a binary linear code C of length n, let d⊥ be the minimum distance of the dual code. Then, the minimum AWGNC pseudoweight of C (with respect to any parity-check matrix H) satisfies AWGNC wmin ≤ As mentioned in the introduction, Schwartz and Vardy consider in [6] the so-called stopping distance of a binary linear code given by a parity-check matrix, and the stopping redundancy of a binary linear code. With [2, Proposition 51] it is easy to see that the stopping distance equals the minimum BEC pseudoweight, and thus the stopping redundancy is equivalent to the BEC pseudocodeword redundancy. Besides pseudocodewords, the notion of trapping set [12] is another concept for analyzing the performance of binary linear codes under MP decoding. In [13] the trapping redundancy for binary linear codes is introduced as a generalization of the stopping redundancy, and several upper bounds are presented. In [14] a binary linear code C is called geometrically perfect if it admits a parity-check matrix H such that the fundamental polytope equals the convex hull of the code, i.e., P(H) = conv(C). In this case ML decoding can be exactly described as an instance of LP decoding. Kashyap [14, Theorem VI.2] gave w(x) − d(C) . It is apparent that g(H) ≥ wmin(H) − d(C), and we have wmin (H) = d(C) if and only if g(H) ≥ 0. If the pseudoweight spectrum gap g(H) is strictly positive then the LP decoding performance approaches ML decoding performance as the signal-to-noise ratio goes to infinity. To date, only few examples of interesting codes with positive pseudoweight spectrum gap are known; these include the codes based on the Euclidean plane or the projective plane [15, Theorem 8]. ρmax-frac (C) ≥ ρBSC (C) ≥ ρBEC (C) . E. Related Notions min x∈M′ (H) (n + d⊥ − 2)2 . (d⊥ − 1)2 + (n − 1) (4) Proof: Consider the pseudocodeword x = △ (x1 , x2 , . . . , xn ) = (d⊥ − 1 , 1 , . . . , 1). Since d⊥ is the minimum distance of the dual code, every row in H has weight at least d⊥ . Therefore, all inequalities (2) and (3) are satisfied for this x, and so it is indeed a legal pseudocodeword. Finally, observe that the AWGNC pseudoweight of x is given by the right-hand side of (4). In the sequel, we use the term random code for a binary linear code C whose k × n generator matrix contains independently and uniformly distributed random entries from F2 . The following result is known as the Gilbert-Varshamov bound. If we pick a code by selecting the generator matrix entries at random, the resulting code C has rate R = k/n and relative minimum distance δ, such that δ ≥ H−1 2 (1 − R) − ǫ , 4 A minor of a code C is any code obtained from C by a (possibly empty) sequence of shortening and puncturing operations. ZUMBRÄGEL, SKACHEK, AND FLANAGAN: ON THE PSEUDOCODEWORD REDUNDANCY with probability approaching 1 as n → ∞, for any fixed small ǫ > 0, where H−1 2 (·) is the inverse of the binary entropy function H2 (p) = −p log2 p − (1 − p) log2 (1 − p) for p ∈ [0 , 1/2]. A similar result also holds when the code C is defined by selecting the parity-check matrix entries (independently and uniformly) at random. Let R = k/n be fixed. Then, if we select at random a k × n matrix over F2 , which corresponds to a code C, the relative minimum distance of C is at least H−1 2 (1 − R) − ǫ (with probability approaching 1 as n → ∞) and the relative minimum distance of the dual code of C is at least H−1 2 (R)−ǫ (again, with probability approaching 1 as n → ∞). By taking the intersection of these two events, both the code and the dual code have relative minimum distances which are ǫ-close to the Gilbert-Varshamov bound with probability approaching 1 as n → ∞. (The reader can refer to [16, Theorems 4.4, 4.5, and 4.10] and to [17, Theorem 8 and Exercise 3].) To this end, we take a random binary linear code C of arbitrary length n (for n → ∞) with R = k/n. The dual code C ⊥ of C, with probability close to one, has rate R⊥ = 1 − R and relative minimum distance δ ⊥ = d⊥ /n that attains the Gilbert-Varshamov bound −1 ⊥ δ ⊥ ≥ µ = H−1 2 (1 − R ) − ǫ = H2 (R) − ǫ , △ Note that (4) may be written in terms of the relative minimum distance δ ⊥ of the dual code as follows: AWGNC wmin ≤ (δ ⊥ − (1 + δ ⊥ − 2/n)2 . 1/n)2 + (1/n − 1/n2 ) (5) Hence, for large n, the minimum pseudoweight of the code C is bounded from above by (1 + 1/δ ⊥ )2 + ǫ′ ≤ (1 + 1/µ)2 + ǫ′ for some small ǫ′ > 0, and this bound does not depend on n. On the other hand, C is a random code and so its minimum distance satisfies the Gilbert-Varshamov bound, namely d ≥ H−1 2 (1 − R) − ǫ · n , which increases linearly with n for a fixed R. This immediately establishes the following theorem. Theorem 3.2: Let 0 < R < 1 be fixed. For a random binary linear code C of length n and rate R, there is, with probability approaching 1 as n tends to infinity, a gap between the minimum AWGNC pseudoweight (with respect to any parity-check matrix) and the minimum distance. Therefore, the AWGNC pseudoredundancy is infinite for most codes. Remark 3.3: The result in Theorem 3.2 is different from, but related to, the results in Propositions 49 and Corollary 50 in [2], where it was shown that the minimum AWGN pseudoweight of ensembles of regular LDPC codes grows sublinearly in the code length. Indeed, there are three fundamental differences between our results and [2]: (i) We do not assume anything about the density of the parity-check matrix H. We also use the fact that the dual code of the random code is asymptotically good; for a regular LDPC code this is not true. (ii) We consider the fundamental cone, which is formed by all possible linear combinations of the rows of H; by contrast, the authors of [2] consider only the case when the column weight of H is smaller than its row weight. (iii) We show that the minimum pseudoweight of the considered ensemble 5 is bounded from above by a constant, while in [2] this quantity is shown to be bounded by a sublinear function. The following lemma is a counterpart of Lemma 3.1 for the BSC. Lemma 3.4: Let C be a binary linear code of length n, and let d⊥ be the minimum distance of the dual code. Then, the minimum BSC pseudoweight of C (with respect to any paritycheck matrix H) satisfies BSC wmin ≤ 2⌈n/d⊥ ⌉ . Proof: Consider the pseudocodeword x = (x1 , x2 , . . . , xn ) = (d⊥−1, . . . , d⊥−1 , 1, . . . , 1) , {z } | {z } | △ τ n−τ for some positive integer τ . This vector x is then a legal pseudocodeword; since d⊥ is the minimum distance of the dual code, every row in H has a weight of at least d⊥ , and so, all inequalities (2) and (3) are satisfied by this x. If τ (d⊥ − 1) ≥ n − τ then by the definition of the BSC pseudoweight wBSC (x) ≤ 2τ . This condition is equivalent to τ d⊥ ≥ n. Therefore, we set τ = ⌈n/d⊥ ⌉. For the corresponding vector x, the pseudoweight is less or equal to 2τ = 2⌈n/d⊥ ⌉. Similarly to the AWGNC case, let C be a random binary linear code of length n with R = k/n. The parameters R⊥ and δ ⊥ of its dual code C ⊥ attain with high probability the Gilbert-Varshamov bound δ ⊥ ≥ µ. From Lemma 3.4, for all n, the pseudoweight of the code C is bounded from above by 2⌈n/d⊥ ⌉ < 2/δ ⊥ + 2 ≤ 2/µ + 2 , which is a constant. On the other hand, C is a random code and its minimum distance also satisfies the GilbertVarshamov bound, so it increases linearly with n. This proves the following theorem. Theorem 3.5: Let 0 < R < 1 be fixed. For a random binary linear code C of length n and rate R, there is, with probability approaching 1 as n tends to infinity, a gap between the minimum BSC pseudoweight (with respect to any paritycheck matrix) and the minimum distance. Therefore, the BSC pseudoredundancy is infinite for most codes. The last theorem disproves the conjecture in [8] that the BSC pseudoredundancy is finite for all binary linear codes.5 Example 3.6: Consider the [23,12] Golay code having minimum distance d = 7. The minimum distance of its dual code is d⊥ = 8. We can take a pseudocodeword x as in the proof of Lemma 3.4 with τ = ⌈n/d⊥ ⌉ = 3. We have wBSC (x) ≤ 2τ = 6, thus obtaining that the minimum distance is not equal to the minimum pseudoweight. Similarly, for the [24,12] extended Golay code we have d = d⊥ = 8, and by taking τ = ⌈n/d⊥ ⌉ = 3 we obtain wBSC (x) ≤ 2τ = 6. Note however that the presented techniques do not answer the question of whether these Golay codes have finite AWGNC pseudoredundancy. 5 We note that a slightly different definition of BSC pseudoweight was given in [8], but the statement of Lemma 3.4 and thus Theorem 3.5 hold with the same proof also with respect to this definition. 6 SUBMITTED TO IEEE TRANSACTIONS ON INFORMATION THEORY In the context of the extended Golay code we mention that there other interesting graphical representations of codes than by Tanner graphs; in particular, a minimal tail-biting trellis has been constructed for the extended Golay code in [18]. The pseudoweights of its pseudocodewords are investigated in [4], where it is shown that there are pseudocodewords with a BSC pseudoweight of 6; on the other hand, as far as we know, it is still unknown whether there are nonzero pseudocodewords of the tail-biting trellis with an AWGNC pseudoweight of less than 8. We have seen in this section that the AWGNC pseudoredundancy and the BSC pseudoredundancy of a random binary linear code is infinite. From Theorem 2.5 it follows that this holds also for the pseudoredundancy with respect to the maxfractional weight. IV. BASIC U PPER B OUNDS Whereas a random code has infinite pseudoredundancy for the AWGNC and the BSC, there are several families of codes for which the pseudoredundancy is finite. Sections IV, V, VI, and VII deal with upper bounds on the pseudoredunancy for some particular classes of codes. We start with this section considering two basic situations, namely the puncturing of zero coordinates and codes of minimum distance 2. The following results hold with respect to the BEC, AWGNC, and BSC pseudoweights, and the maxfractional weight. Lemma 4.1: Let C be an [n, k, d] code having t zero coordinates, and let C ′ be the [n − t, k, d] code obtained by puncturing C at these coordinates. Then ρ(C ′ ) ≤ ρ(C) ≤ ρ(C ′ ) + t . Proof: For notational purposes, we identify Rn with RI , ′ and for x ∈ RI and some subset I ′ ⊆ I we let x|I ′ ∈ RI ′ be the projection of x onto the coordinates in I . Let I ′ ⊆ I be the set of nonzero coordinates of the code C. To prove the first inequality, let H be a ρ × n parity-check matrix for C. Consider its ρ × (n − t) submatrix H ′ consisting of the columns corresponding to I ′ . Then H ′ is a parity-check matrix for C ′ , and K(H ′ ) = {x|I ′ | x ∈ K(H), x|I\I ′ = 0} . Therefore, wmin (H ′ ) ≥ wmin (H), and this proves ρ(C ′ ) ≤ ρ(C). For the second inequality, let H ′ be a ρ′ × (n − t) paritycheck matrix for C ′ . Now we consider a (ρ′ + t) × n matrix H with the following properties: The upper ρ′ × n submatrix of H consists of the columns of H ′ at positions I ′ and of zero-columns at positions I \I ′ , and the lower t×n submatrix consists of rows of weight 1 that have 1s at the positions I \I ′ . Then C = ker H and K(H) = {x ∈ RI | x|I ′ ∈ K(H ′ ), x|I\I ′ = 0} . Consequently, wmin (H) = wmin(H ′ ), and this proves ρ(C) ≤ ρ(C ′ ) + t. Lemma 4.2: Let C be a code of minimum distance d ≤ 2. Then d = wmin (H) for any parity-check matrix H of C, i.e., C is in class 3 (for BEC, AWGNC, BSC, and max-fractional pseudoweight). Proof: By Lemma 2.4 it suffices to prove this lemma for the max-fractional weight w = wmax-frac . Since w(x) ≥ 1 holds for all nonzero pseudocodewords, we always have wmin (H) ≥ 1, which proves the result in the case d = 1. Let d = 2 and H be a parity-check matrix for C. Let x ∈ K(H) and let xℓ be the largest coordinate. Since d = 2 there is no zero column in a row j with PH and thus there exists P ℓ ∈ Ij . Then xℓ ≤ i∈I\{ℓ} xi , hence 2xℓ ≤ i∈I xi , and thus w(x) ≥ 2. It follows wmin(H) ≥ 2 and the lemma is proved. V. C ONSTRUCTIONS OF CODES FROM OTHER CODES The following results consider the pseudoredundancy of codes obtained from other codes by the direct sum or the (u u) construction. They are analogs of Theorems 7 and 8 in [6], and Theorems 4.1 and 4.2 in [8], for the case of the maxfractional weight and the AWGNC pseudoweight. Our proofs in each case follow the exposition of these earlier proofs. Theorem 5.1: Let C1 and C2 be [n1 , k1 , d1 ] and [n2 , k2 , d2 ] binary linear codes, respectively. Then the direct sum C3 = {(u v) | u ∈ C1 , v ∈ C2 } is an [n1 + n2 , k1 + k2 , min{d1 , d2 }] code with ρmax-frac (C3 ) ≤ ρmax-frac (C1 ) + ρmax-frac (C2 ) , ρAWGNC (C3 ) ≤ ρAWGNC (C1 ) + ρAWGNC (C2 ) . Proof: Without loss of generality, we may assume that both ρ(C1 ) and ρ(C2 ) are finite, for otherwise the statement to be proved is trivial. For i = 1, 2, let H i be a parity-check matrix for Ci having ρ(Ci ) rows and such that w(x) ≥ di for all x ∈ K(H i ) \ {0}. Then H1 0 H3 = 0 H2 is a parity-check matrix for C3 with ρ(C1 ) + ρ(C2 ) rows. Let p = (q r) ∈ K(H 3 ) \ {0}, where the vectors q and r in the concatenation have lengths n1 and n2 respectively. Then, we may assume q ∈ K(H 1 ) \ {0} and r ∈ K(H 2 ) \ {0}, and therefore w(q) ≥ d1 and w(r) ≥ d2 . (Note that in the case where either q or r is equal to 0, the result is trivial since for any q 6= 0, w(q 0) = w(q) for both the max-fractional weight and the AWGNC pseudoweight.) We consider the two cases of max-fractional weight and AWGNC pseudoweight separately. Max-fractional weight: Assume without loss of generality that max{qi } ≥ max{ri }. Then P P P qi + ri pi = wmax-frac (p) = max{pi } max{qi } P qi > ≥ d1 ≥ min{d1 , d2 } max{qi } which proves the result. AWGNC pseudoweight: Assume without loss of generality that wAWGNC (q) ≥ wAWGNC (r); this condition may be written as 2 X X 2 X X n2 n1 n2 n1 2 2 (6) ri . qi ri ≥ qi i=1 i=1 i=1 i=1 ZUMBRÄGEL, SKACHEK, AND FLANAGAN: ON THE PSEUDOCODEWORD REDUNDANCY To establish the result, we need only to prove that wAWGNC (p) ≥ wAWGNC (r). Now, since the entries of q and r are nonnegative, we have X X X n2 n2 n1 2 ri ≥ 0 . (7) ri qi 2 i=1 i=1 Pn2 2 Pn2 i=1 2 Adding i=1 ri to both sides of (7) and adding i=1 ri the resulting inequality to inequality (6) yields X X 2 X 2 X n1 n2 n2 n2 n1 n2 X X 2 2 2 qi + ri ri ri ≥ qi + ri i=1 i=1 i=1 i=1 i=1 (a) There is an equivalence relation on the set I of column indices of H such that for a vector x ∈ Rn with nonnegative coordinates we have x ∈ K(H ) if and only if x has equal coordinates within each equivalence class. (b) The minimum distance of C is equal to its minimum BEC, AWGNC, BSC, and max-fractional pseudoweights with respect to H, i.e., d(C) = wmin (H). Proof: For (a), define the required relation R as follows: For i, i′ ∈ I let (i, i′ ) ∈ R if and only if i = i′ or there exists an integer ℓ ≥ 1, column indices i = i0 , i1 , . . . , iℓ−1 , iℓ = i′ ∈ I and row indices j1 , . . . , jl ∈ J such that i=1 which may be rearranged as wAWGNC (p) ≥ wAWGNC (r), as desired. Theorem 5.2: Let C1 be an [n, k, d] binary linear code. Then C2 = {(u u) | u ∈ C1 } is a [2n, k, 2d] code with ρmax-frac (C2 ) ≤ ρmax-frac (C1 ) + n , ρAWGNC (C2 ) ≤ ρAWGNC (C1 ) + n . Proof: As before, without loss of generality, we may assume that ρ(C1 ) is finite. Let H 1 be a parity-check matrix for C1 with ρ(C1 ) rows and such that w(x) ≥ d1 for all x ∈ K(H 1 ) \ {0}. Then H1 0 H2 = In In is a parity-check matrix for C2 with ρ(C1 ) + n rows (here I n denotes the n × n identity matrix). Let p = (q r) ∈ K(H 2 ) \ {0}, where the vectors q ∈ K(H 1 ) and r in the concatenation both have length n. Then, for i = 1, 2, . . . , n, from the fundamental cone inequalities for row n + i we get qi ≤ ri ≤ qi , so we have p = (q q). Now, since q ∈ K(H 1 ) \ {0}, we have w(q) ≥ d1 . Since w((q q)) = 2 w(q) for both the max-fractional weight and the AWGNC pseudoweight, we have w(p) ≥ 2d, and the result follows. Remark 5.3: Theorem 9 in [6] and Theorem 4.3 in [8] state that if C is an [n, k, 3] binary linear code then the extended [n+1, k, 4] code C ′ satisfies ρ(C ′ ) ≤ 2ρ(C), for the BEC pseudoweight and the BSC pseudoweight, respectively. Regarding the corresponding results for the case of the max-fractional weight and the AWGNC pseudoweight, we mention here only that the analogous result in fact does not hold for the case of the max-fractional weight. As a counterexample, consider the [7, 4, 3] Hamming code C1 which satisfies ρ(C1 ) ≤ 23 − 1 = 7 (cf. Proposition 7.7). On the other hand, the [8, 4, 4] extended Hamming code C2 satisfies ρmax-frac (C2 ) = ∞ (cf. Section VIII-B). VI. PARITY- CHECK 7 MATRICES WITH ROWS OF WEIGHT 2 In this section we consider the pseudoredundancy of codes with a parity-check matrix consisting of rows of weight 2 and at most one additional row. The results are then applied to upper-bound the pseudoredundancy for codes of dimension 2. The basic case is dealt with in the following lemma. Lemma 6.1: Let H be a parity-check matrix of C such that every row in H has weight 2. Then: {i0 , i1 } = Ij1 , {i1 , i2 } = Ij2 , . . . , {iℓ−1 , iℓ } = Ijℓ . This is an equivalence relation, and it defines equivalence classes over I. It is easy to check that inequalities (2) imply that x ∈ K(H) if and only if xi = xi′ for any (i, i′ ) ∈ R. In order to prove (b), we note that the minimum (BEC, AWGNC, BSC or max-fractional) pseudoweight is always bounded above by the minimum distance of C, so we only have to show that the minimum pseudoweight is bounded below by the minimum distance. Let S = {S1 , S2 , . . . , St } be the set of equivalence classes of R, and let dS = |S| for S ∈ S. It is easy to see that the minimum distance of C is d = minS∈S dS (since the minimum weight nonzero codeword of C has non-zeros in the coordinates corresponding to a set S ∈ S of minimal size and zeros everywhere else). Now let x ∈ K(H). Since the coordinates xi , i ∈ I, depend only on the equivalence classes, we may use the notation xS , S ∈ S. Let xT , T ∈ S, be the largest coordinate. Then: P P xi xi ≥ i∈T = |T | = dT ≥ d . wmax-frac (x) = i∈I xT xT max-frac Therefore, wmin (H) ≥ d, and by using Lemma 2.4, we get BEC AWGNC BSC wmin (H) ≥ d, wmin (H) ≥ d, and wmin (H) ≥ d. The following proposition is a stronger version of Lemma 6.1. Proposition 6.2: Let H be an m × n parity-check matrix of C, and assume that the m − 1 first rows in H have c the (m − 1) × n matrix consisting weight 2. Denote by H of these rows, consider the equivalence relation of Lemma 6.1 c and assume that Im intersects each (a) with respect to H, equivalence class in at most one element. Then, the minimum distance of C is equal to its minimum BEC, AWGNC, BSC, and max-fractional pseudoweights with respect to H, i.e., d(C) = wmin (H). Proof: Let S be the set of classes of the aforementioned equivalence relation on I, and let dS = |S| for S ∈ S. Let S ′ = {S ∈ S | |S ∩ Im | = 1} . Also let S ′′ = S \ S ′ , so that S ∩ Im = ∅ for all S ∈ S ′′ . Let x ∈ K(H) \ {0}. As before, since the coordinates xi , i ∈ I, depend only on the equivalence classes, we may use the notation xS , S ∈ S. The fundamental cone constraints (2) and (3) may then be written as xS ≥ 0 for all S ∈ S and X xS , (8) ∀R ∈ S ′ : xR ≤ S∈S ′ \{R} 8 SUBMITTED TO IEEE TRANSACTIONS ON INFORMATION THEORY respectively, and the max-fractional weight of x ∈ K(H )\{0} is given by P dS xS wmax-frac (x) = S∈S . (9) maxS∈S xS Suppose x ∈ K(H) \ {0} has minimal max-fractional weight. Let xT be its largest coordinate. First note that if there exists R ∈ S ′′ \ {T } with xR > 0, setting xR to zero results in a new pseudocodeword with lower max-fractional weight, which contradicts the assumption that x achieves the minimum. Therefore xR = 0 for all R ∈ S ′′ \ {T }. We next consider two cases. Case 1: T ∈ S ′′ . If there exists R ∈ S ′ with xR > 0, setting all such xR to zero results in a new pseudocodeword with lower max-fractional weight, which contradicts the minimality of the max-fractional weight of x. Therefore xT is the only positive coordinate of x, and by (9) the max-fractional weight of x is dT . Case 2: T ∈ S ′ . In this case xR = 0 for all R ∈ S ′′ . From inequality (8) for R = T we obtain X xS . xT ≤ S∈S ′ \{T } △ With d0 = minS∈S ′ \{T } dS it follows that X X d0 xS ≤ d0 xT ≤ dS xS . S∈S ′ \{T } S∈S ′ \{T } Consequently, (dT + d0 )xT ≤ X dS xS , S∈S and thus wmax-frac (x) ≥ dT +d0 . We conclude that the minimum max-fractional weight is given by max-frac wmin (H) = min min {dS + dT } , min′′ {dS } . ′ S,T ∈S ,S6=T S∈S But this is easily seen to be equal to the minimum distance d of the code. BEC Finally, by using Lemma 2.4, we obtain that wmin (H) = d, AWGNC BSC wmin (H) = d and wmin (H) = d. Remark 6.3: The requirement that all i ∈ Im belong c in Proposition 6.2 is to different equivalence classes of H necessary. Indeed, consider the matrix H= 1 0 1 1 0 1 0 0 1 1 0 1 1 1 0 1 . c One can see that there are two equivalence classes for H: S1 = {1, 2, 3}, S2 = {4}. The minimum distance of the corresponding code C is 4 (since (1, 1, 1, 1) is the only nonzero codeword). However, x = (1, 1, 1, 3) ∈ K(H) is a pseudocodeword of max-fractional weight 2. Corollary 6.4: Let C be a code of length n and dimension 2. Then ρ(C) = n − 2, i.e., C is of class at least 2 (for BEC, AWGNC, BSC, and max-fractional pseudoweight). Proof: We consider two cases. Case 1: C has no zero coordinates. Let c1 and c2 be two linearly independent codewords of C. Define the following subsets of I: S1 = △ {i ∈ I | i ∈ supp(c1 ) and i ∈ / supp(c2 )} S2 △ = {i ∈ I | i ∈ / supp(c1 ) and i ∈ supp(c2 )} S3 △ {i ∈ I | i ∈ supp(c1 ) and i ∈ supp(c2 )}. = The sets S1 , S2 , and S3 are pairwise disjoint. Since C has no zero coordinates, I = S1 ∪ S2 ∪ S3 . The ordering of the elements in I implies an ordering on the elements in each of S1 , S2 , and S3 . Assume that S1 = {i1 , i2 , · · · , i|S1 | } and i1 < i2 < · · · < i|S1 | . If S1 6= ∅, let m1 = i1 be the minimal 1 ) element in S1 , and define an (|S1 |−1)×n matrix H 1 = (Hj,ℓ as follows: 1 if ij = ℓ or ij+1 = ℓ , 1 j = 1, 2, · · · , |S1 | − 1 , Hj,ℓ = 0 otherwise . Similarly, define (|S2 | − 1) × n and (|S3 | − 1) × n matrices H 2 and H 3 , with respect to S2 and S3 . (Some of the Si s might be equal to ∅, in which case the corresponding H i is not defined.) Let m2 and m3 be minimal elements of S2 and S3 , respectively (if S2 6= ∅ and S3 6= ∅). Subcase 1-a: One of S1 , S2 , S3 is empty. Without loss of generality we may assume that S3 = ∅, i.e., that c1 and c2 have disjoint support; indeed, if for example S1 = ∅, then supp(c1 ) ⊆ supp(c2 ) and we can replace c2 by c1 +c2 . Define △ an (n − 2) × n matrix H by H T = [ H T1 | H T2 ]. It is easy to see that all rows of H are linearly independent, and so its rank is n − 2. It is also straightforward that for all c ∈ C we have c ∈ ker(H). Therefore, H is a parity-check matrix of C. The matrix H has a form as in Lemma 6.1, and thus ρ(C) = n − 2. Subcase 1-b: Neither of S1 , S2 , S3 is empty. Define a 1 × n 4 matrix H 4 = (Hj,ℓ ), where 4 H1,ℓ = 1 0 if Sj 6= ∅ and mj = ℓ for j = 1, 2, 3 , otherwise . Additionally, define an (n − 2) × n matrix H by H T = [ H T1 | H T2 | H T3 | H T4 ]. Similarly to the previous case, all rows of H are linearly independent, its rank is n − 2. For all c ∈ C we have c ∈ ker(H). Therefore, H is a parity-check matrix of C. The matrix H has a form as in Proposition 6.2 (where S1 , S2 , and S3 are corresponding equivalence classes over I), and therefore ρ(C) = n − 2. Case 2: C has t > 0 zero coordinates. Consider a code C ′ of length n−t obtained by puncturing C in these t zero coordinates. From Case 1 (with respect to C ′ ), ρ(C ′ ) = n − t − 2. By applying the rightmost inequality in Lemma 4.1, we have ρ(C) ≤ n− 2. Since k = 2, we conclude that ρ(C) = n − 2. △ ZUMBRÄGEL, SKACHEK, AND FLANAGAN: ON THE PSEUDOCODEWORD REDUNDANCY VII. C ODES BASED ON D ESIGNS Among the codes with finite pseudoredundancy an interesting class of codes is based on designs. In this section we consider partial designs, which include the common BIBDs (also called 2-designs). We present a principal lower bound on the minimum pseudoweight for codes, when the parity-check matrix is the block-point incidence matrix of a partial design. We apply this bound to the Hamming codes and the simplex codes and deduce that their pseudoredundancy is finite. Definition 7.1: A partial (wc , λ) design is a block design consisting of an n-element set V (whose elements are called points) and a collection of m subsets of V (called blocks) such that every point is contained in exactly wc blocks and every 2-element subset of V is contained in at most λ blocks. The incidence matrix of a design is an m × n matrix H whose rows correspond to the blocks and whose columns correspond to the points, and that satisfies Hj,i = 1 if block j contains point i, and Hj,i = 0 otherwise. If each block contains the same number wr of points and every 2-element subset of V is contained in exactly λ blocks, the design is said to be an (n, wr , λ) balanced incomplete block design (BIBD), or 2-design. In the following we avoid the trivial cases n ≤ 1 and λ = 0. For a BIBD we have n wc = m wr and also wc (wr − 1) = λ (n − 1) (see, e.g., [19, p. 60]), so (n, wr , λ) determines the other parameters wc and m by wc = n−1 n (n − 1) λ and m = λ. wr − 1 wr (wr − 1) (10) Note that [20] and [21] consider parity-check matrices based on BIBDs; these matrices are the transpose of the incidence matrices defined here. We have the following general result for codes based on partial (wc , λ) designs. Theorem 7.2: Let C be a code with parity-check matrix H, such that a subset of the rows of H forms the incidence matrix for a partial (wc , λ) design. Then the minimum max-fractional weight of C with respect to H is lower bounded by wc max-frac wmin ≥1+ . (11) λ For the case of an (n, wr , λ) BIBD, the lower bound in (11) may also be written as n−1 ; wr − 1 the alternative form follows directly from (10). Proof: Consider the subset of the rows of H which forms the incidence matrix for a partial (wc , λ) design. Let x be a nonzero pseudocodeword and let xℓ be a maximal coordinate of x (ℓ ∈ I). For all j ∈ Jℓ , sum inequalities (2). We have X xi , wc xℓ ≤ λ max-frac wmin ≥1+ i∈I\{ℓ} and thus X wc xℓ ≤ xi . 1+ λ i∈I (12) 9 max-frac . The result now easily follows from the definition of wmin Theorem 7.3: Let C be a code with parity-check matrix H, such that a subset of the rows of H forms the incidence matrix for a partial (wc , λ) design. Then, wc AWGNC , wmin ≥1+ λ w c BSC wmin ≥1+ . λ Proof: Apply Lemma 2.4 and Theorem 7.2. Results similar to Theorem 7.2 and Theorem 7.3 were also presented and proven by Xia and Fu [22] in the AWGNC case. Remark 7.4: Under the conditions of Theorem 7.3, if x ∈ K(H) is a nonzero pseudocodeword such that wAWGNC (x) = 1 + wλc holds then it follows that x is a scalar multiple of a binary vector. This can be easily seen by considering the proof of the inequality wAWGNC (x) ≥ wmax-frac (x) (see [2, Lemma 44]) and examining when equality wAWGNC (x) = wmax-frac (x) holds. Furthermore it can be shown that in this case x is actually a scalar multiple of a codeword (see [22, Theorem 3]). It follows that the AWGNC pseudocodeword spectrum gap is positive, provided that d(C) = 1 + wλc holds. Another tool for proving lower bounds on the minimum AWGNC pseudoweight is provided by the following eigenvalue-based lower bound by Vontobel and Koetter [9]. Proposition 7.5 (cf. [9]): The minimum AWGNC pseudoweight for a (wc , wr )-regular parity-check matrix H whose corresponding Tanner graph is connected is bounded below by AWGNC wmin ≥n· 2wc − µ2 , µ1 − µ2 (13) where µ1 and µ2 denote the largest and second largest eigen△ value (respectively) of the matrix L = H T H; here, L and the matrix multiplication are to be considered over the reals. In the case where H is equal to the incidence matrix for an (n, wr , λ) BIBD, the bound of Proposition 7.5 becomes wc AWGNC , (14) wmin ≥1+ λ so that in this case the bound of Proposition 7.5 coincides with that of Theorem 7.3 (for the case of the AWGNC only). To see why (13) becomes (14), denote the column i ∈ I of H by hi and denote the matrix L = (Li,ℓ )i,ℓ∈I = H T H. From the properties of a BIBD we get ( wc if i = ℓ , T Li,ℓ = hi hℓ = λ if i 6= ℓ . Now, L has largest eigenvalue µ1 = wr wc and only one other eigenvalue µ2 = wc − λ, whose multiplicity is n − 1, since one can write L = λ1 + (wc − λ)I, where 1 and I denote the all-ones and the identity matrices, respectively. Now we have 2wc − µ2 = wc + λ and µ1 − µ2 = wr wc − wc + λ = nλ, so wc c −µ2 that n · 2w µ1 −µ2 = 1 + λ . Remark 7.6: Prominent examples for codes based on designs are codes based on Euclidean or projective geometries, in particular the [4s − 1 , 4s − 3s , 2s + 1] code based on the Euclidean plane EG(2, 2s ) as well as the [4s + 2s + 1 , 4s − 3s + 2s , 2s + 2] code based on the projective plane PG(2, 2s ) (see [5], [15]). Theorem 7.3 and 10 SUBMITTED TO IEEE TRANSACTIONS ON INFORMATION THEORY Remark 7.4 apply to these codes, as their standard paritycheck matrices form the incidence matrix for a partial design with parameters (wc , λ) = (2s , 1) and (wc , λ) = (2s + 1 , 1), respectively6; in particular these codes have finite pseudoredundancy. We next apply the bounds of Theorems 7.2 and 7.3 to some other examples of codes derived from designs. Proposition 7.7: For m ≥ 2, the [2m − 1 , 2m − 1 − m , 3] Hamming code has BEC, AWGNC, BSC, and max-fractional pseudocodeword redundancies ρ(C) ≤ 2m − 1 . Proof: For m ≥ 2, consider the binary parity-check matrix H whose rows are exactly the nonzero codewords of the dual code C ⊥ , in this case the [2m − 1 , m , 2m−1 ] simplex code. This H is the incidence matrix for a BIBD with parameters (n, wr , λ) = (2m − 1 , 2m−1 , 2m−2 ). Theorem 7.2 gives wmax-frac (x) ≥ 3, leading to ρmax-frac (C) ≤ 2m − 1. The result for BEC, AWGNC, and BSC follows by applying Theorem 2.5. In the next example, we consider simplex codes. Straightforward application of the previous reasoning does not lead to the desired result. However, more careful selection of the matrix H, as described below, leads to a new bound on the pseudoredundancy. Proposition 7.8: For m ≥ 2, the [2m − 1 , m , 2m−1 ] simplex code has BEC, AWGNC, BSC, and max-fractional pseudocodeword redundancies ρ(C) ≤ (2m − 1) (2m−1 − 1) . 3 Proof: For m ≥ 2, consider the binary parity-check matrix H whose rows are exactly the codewords of the dual code C ⊥ (in this case the [2m − 1 , 2m − 1 − m , 3] Hamming code) with Hamming weight equal to 3. This H is the incidence matrix for a BIBD with parameters (n, wr , λ) = max-frac (2m − 1 , 3 , 1). Theorem 7.2 gives wmin ≥ 2m−1 . Note that the number of codewords of weight 3 in the [2m − 1 , 2m − 1 − m , 3] Hamming code equals (2m − 1)(2m−1 − 1)/3. One can show this, e.g., by considering the full sphere-packing of the perfect Hamming code and observing that each codeword of weight 3 covers exactly 3 vectors of weight 2, of which there are (2m − 1)(2m − 2)/2 in total. Next, we justify the claim that H is a parity-check matrix of C. A theorem of Simonis [23] states that if there exists a linear [n, k, d] code then there also exists a linear [n, k, d] code whose codewords are spanned by the codewords of weight d. Since the Hamming code is unique for the parameters [2m − 1 , 2m − 1 − m , 3], this implies that the Hamming code itself is spanned by the codewords of weight 3, so the rowspace of H equals C. The result for BEC, AWGNC, and BSC follows again by applying Theorem 2.5. 6 In the latter case the partial design is even a BIBD with parameters (4s +2s +1 , 2s +1 , 1). We remark that the bounds of Propositions 7.7 and 7.8 are sharp at least for the case m = 3 and the max-fractional weight, see Section VIII-B. The following proposition proves that the AWGNC, BSC, and max-fractional pseudocodeword redundancies are finite for all codes C with minimum distance at most 3. Proposition 7.9: Let C be a [n, k, d] code with d ≤ 3. Then ρmax-frac (C) is finite. Moreover, we have ρmax-frac (C) = n − k in the case d ≤ 2. Proof: By using Lemma 4.2 we may assume d = 3. Denote by H the parity-check matrix whose rows consist of all codewords of the dual code of C. Note that for a code of minimum distance d, a parity-check matrix H consisting of all rows of the dual code C ⊥ is an orthogonal array of strength d − 1. In the present case d = 3, and this implies that in any pair of columns of H, all length-2 binary vectors occur with equal multiplicities (cf. [19, p. 139]). Thus the matrix H is an incidence matrix for a partial block design with parameters (wc , λ) = (2r−1 , 2r−2 ), where r = n − k. Therefore for this matrix H the code has minimum (AWGNC, BSC, or maxfractional) pseudoweight at least 1 + wc /λ = 3, and it follows that the pseudocodeword redundancy is finite for any code with d = 3. We remark that Proposition 7.9 implies the results for the Hamming codes (Proposition 7.7). However, we present the two proofs, since they use different methods. We have considered in this section several families of codes based on designs, which have finite pseudocodeword redundancy. As noted in Section II-E, finiteness of pseudoredundancy would also follow if one can show that the codes are geometrically perfect. However, this is not the case for the examined codes in general. For example, the [2m − 1 , 2m − 1 − m , 3] Hamming code is not geometrically perfect for m ≥ 4; this follows from the characterization of geometrically perfect codes, as the [7, 3, 4] simplex code can be obtained from the Hamming code by repeated shortening, when m ≥ 4. VIII. T HE P SEUDOCODEWORD R EDUNDANCY OF S MALL L ENGTH FOR C ODES In this section we compute the AWGNC, BSC, and maxfractional pseudocodeword redundancies for all codes of small length. By Lemma 4.2 it is sufficient to examine only codes with minimum distance at least 3. Furthermore, in light of Lemma 4.1 we will consider only codes without zero coordinates, i.e., codes that have a dual minimum distance of at least 2. Finally, we point out to Corollary 6.4 for codes of dimension 2, by which we may focus on codes with dimension at least 3. A. The Algorithm To compute the pseudocodeword redundancy of a code C we have to examine all possible parity-check matrices for the code C, up to equivalence. Here, we say that two parity-check matrices H and H ′ for the code C are equivalent if H can be transformed into H ′ by a sequence of row and column permutations. In this case, wmin (H) = wmin (H ′ ) holds for ZUMBRÄGEL, SKACHEK, AND FLANAGAN: ON THE PSEUDOCODEWORD REDUNDANCY TABLE I T HE N UMBER OF B INARY [n, k, d] C ODES WITH d ≥ 3 AND WITHOUT Z ERO C OORDINATES n=5 6 7 8 9 k=1 2 3 4 5 1 1 1 1 1 1 3 4 6 8 1 4 10 23 1 5 23 5 the BEC, AWGNC, BSC, and max-fractional pseudoweights. The enumeration of codes and parity-check matrices can be described by the following algorithm. Algorithm 8.1: Input: Parameters n (code length), k (code dimension), ρ (number of rows of the output parity-check matrices), where △ ρ ≥ r = n − k. Output: For all codes of length n, dimension k, minimum distance d ≥ 3, and without zero coordinates, up to code equivalence: a list of all ρ × n parity-check matrices, up to parity-check matrix equivalence. 1) Collect the set X of all r × n matrices such that • they have different nonzero columns, ordered lexicographically, • there is no non-empty F2 -sum of rows which has weight 0 or 1 (this way, the matrices are of full rank and the minimum distance of the row space is at least 2). 2) Determine the orbits in X under the action of the group GLr (2) of invertible r × r matrices over F2 (this enumerates all codes with the required properties, up to equivalence; the codes are represented by parity-check matrices). 3) For each orbit XC , representing a code C: a) Determine the suborbits in XC under the action of the symmetric group Sr (this enumerates all parity-check matrices without redundant rows, up to equivalence). b) For each representative H of the suborbits, collect all matrices enlarged by adding ρ − r different redundant rows that are F2 -sums of at least two rows of H. Let XC,ρ be the union of all such ρ×n matrices. c) Determine the orbits in XC,ρ under the action of the symmetric group Sρ , and output a representative for each orbit. This algorithm was implemented in the C programming language. The minimum pseudoweights for the various paritycheck matrices were computed by using Maple 12 and the Convex package [24]. B. Results We considered all binary linear codes up to length n with minimum distance d ≥ 3 and without zero coordinates, up to code equivalence. The number of those codes for given length n and dimension k is shown in Table I. 11 1) AWGNC pseudoweight: The following results were found to hold for all codes of length n ≤ 9. • There are only two codes C with ρAWGNC (C) > r, i.e., in class 0 or 1 for the AWGNC. – The [8, 4, 4] extended Hamming code is the shortest code C in class 1. We have ρAWGNC (C) = 5 > 4 = r and out of 12 possible parity-check matrices (up to equivalence) with one redundant row there is exactly AWGNC one matrix H with wmin (H) = 4, namely H= 0 1 0 0 1 1 0 0 1 1 1 0 1 0 1 0 1 0 1 0 0 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 . AWGNC There is exactly one matrix H with wmin (H) = 25/7, and for the remaining matrices H we have AWGNC wmin (H) = 3. For this code, also ρBEC (C) = 5 > 4, and it is the only code of length n ≤ 9 with ρBEC (C) > r. – Out of the four [9, 4, 4] codes there is one code C in class 1. We have ρAWGNC (C) = 6 > 5 = r and out of 2526 possible parity-check matrices (up to equivalence) with one redundant row there are 13 AWGNC matrices H with wmin (H) = 4. • For all codes C of minimum distance d ≥ 3 and for all AWGNC parity-check matrices H of C we have wmin (H) ≥ 3; in particular, if d = 3, then C is in class 3 for the AWGNC. • For the [7, 3, 4] simplex code there is (up to equivalence) only one parity-check matrix H without redundant rows AWGNC such that wmin (H) = 4, namely H= 1 1 0 1 0 0 0 0 0 1 0 1 1 0 1 1 0 0 1 0 0 0 0 0 1 1 0 1 . It is the only parity-check matrix with constant row weight 3. 2) BSC pseudoweight: We computed the pseudocodeword redundancy for the BSC for all codes of length n ≤ 8. • The shortest codes with ρBSC (C) > r, i.e., in class 0 or 1 for the BSC, are the [7, 4, 3] Hamming code C and its dual code C ⊥ , the [7, 3, 4] simplex code. We have ρBSC (C) = 4 > 3 and ρBSC (C ⊥ ) = 5 > 4. There are two codes of length 8 with ρBSC (C) > r. These are the [8, 4, 4] extended Hamming code, for which ρBSC (C) = 6 > 4 holds, and one of the three [8, 3, 4] codes, which satisfies ρBSC (C) = 6 > 5. 3) Max-fractional weight: We computed the pseudocodeword redundancy with respect to the max-fractional weight for all codes of length n ≤ 8. • The shortest code with ρmax-frac (C) > r is the unique [6, 3, 3] code C. We have ρmax-frac (C) = 4 > 3. • • There are two codes of length 7 with ρmax-frac (C) > r. These are the [7, 4, 3] Hamming code and the [7, 3, 4] simplex code, which have both pseudocodeword redundancy 7. In 12 SUBMITTED TO IEEE TRANSACTIONS ON INFORMATION THEORY both cases, there is, up to equivalence, a unique paritycheck matrix H with seven rows that satisfies d(C) = max-frac wmin (H). This demonstrates that Propositions 7.7 and 7.8 are sharp for the max-fractional weight, and that the parity-check matrices constructed in the proofs are unique in this case. • For the [8, 4, 4] extended Hamming code C we have ρmax-frac (C) = ∞, and thus the code is in class 0 for the max-fractional weight. It is the shortest code with infinite max-fractional pseudoredundancy. (It can be checked that x = [1, 1, 1, 1, 1, 1, 1, 3] is a pseudocodeword in K(H), where the rows of H consist of all dual codewords; since wmax-frac (x) = 10 3 < 4, we max-frac have wmin (H) < 4.) There are two other codes of length 8 with ρmax-frac (C) > r, namely two of the three [8, 3, 4] codes, having pseudocodeword redundancy 6 and 8, respectively. 4) Comparison: Comparing the results for the AWGNC and BSC pseudoweights, and the max-fractional weight, we can summarize the results as follows. • For the [7, 4, 3] Hamming code C we have ρAWGNC (C) = r = 3 , ρBSC (C) = 4 , and ρmax-frac (C) = 7. • • For the [7, 3, 4] simplex code C we have ρAWGNC (C) = r = 4 , ρBSC (C) = 5 , and ρmax-frac (C) = 7. • For the [8, 4, 4] extended Hamming code C we have ρAWGNC (C) = 5 , ρBSC (C) = 6 , and ρmax-frac (C) = ∞. This code C is the shortest one such that ρAWGNC (C) > r, and also the shortest one such that ρmax-frac (C) = ∞. If d ≥ 3 then for every parity-check matrix H we have AWGNC wmin (H) ≥ 3. This is not true for the BSC and the max-fractional weight. These observations show that there is some significant difference between the various types of pseudocodeword redundancies. It is also interesting to note that the [7, 4, 3] Hamming code is geometrically perfect, while the [7, 3, 4] code and the [8, 4, 4] code are not (cf. Section II-E). • IX. C YCLIC C ODES M EETING THE E IGENVALUE B OUND In this last section we apply the eigenvalue-based lower bound on the minimum AWGNC pseudoweight by Vontobel and Koetter [9], see Proposition 7.5. We investigate for which cyclic codes of short length this bound is sharp with respect to the minimum Hamming distance, for in this case, the codes have finite AWGNC pseudoredundancy. We consider binary cyclic codes with full circulant paritycheck matrices, defined as follows: Let C be a binary P cyclic code of length n with check polynomial h(x) = i∈I hi xi (cf. [19], p. 194). Then the full circulant parity-check matrix for C is the n × n matrix H = (Hj,i )i,j∈I with entries Hj,i = hj−i . Here, all the indices are modulo n, so that I = {0, 1, . . . , n − 1}. P Since such a matrix is w-regular, where w = i∈I hi , we may use the eigenvalue-based lower bound of Proposition 7.5 to examine the AWGNC pseudocodeword redundancy: If the right hand side equals the minimum distance d of the code C, then ρAWGNC (C) ≤ n. Note that the largest eigenvalue of the matrixP L = H T H is 2 µ1 = w , since every row weight of L equals i,j∈I hi hj = w2 . Consequently, the eigenvalue bound is AWGNC wmin ≥n· 2w − µ2 , w 2 − µ2 where µ2 is the second largest eigenvalue of L. We remark further that L = (Lj,i )i,j∈IPis a symmetric circulant matrix, with Lj,i = ℓj−i and ℓi = k∈I hk hk+i . The eigenvalues of L are thus given by X X X λj = ℓi ζnij = Re ℓi ζnij = ℓi cos(2πij/n) i∈I i∈I i∈I for j ∈ I, where ζn = exp(2πi/n) is the n-th primitive root of unity and i2 = −1 (see, e.g., [25], Theorem 3.2.2). We also consider quasi-cyclic codes of the form given in the following remark. This code construction is only introduced for completeness towards classifying the results; the resulting codes are not interesting for applications, as the minimum Hamming distance is at most 2 for m ≥ 2. Remark 9.1: Denote by 1m the m × m matrix with all entries equal to 1. If H is a w-regular circulant n × n matrix △ then the Kronecker product H̃ = H ⊗ 1m will be a w-regular circulant mn×mn-matrix and defines a quasi-cyclic code. We have T L̃ = H̃ H̃ = H T H ⊗ 1Tm 1m = L ⊗ (m1m ) , and the eigenvalues of m1m are m2 and 0. Thus, the largest eigenvalues of L̃ are µ̃1 = m2 µ1 = m2 w2 and µ̃2 = m2 µ2 , and the eigenvalue bound of Proposition 7.5 becomes AWGNC wmin ≥ mn · 2w − mµ2 2mw − m2 µ2 =n· . m 2 w 2 − m 2 µ2 w 2 − µ2 We carried out an exhaustive search on all cyclic codes C up to length n ≤ 250 and computed the eigenvalue bound in all cases where the Tanner graph of the full circulant parity-check matrix is connected, by using the following algorithm. Algorithm 9.2: Input: Parameter n (code length). Output: For all divisors of xn − 1, corresponding to cyclic codes C with full circulant parity-check matrix, such that the Tanner graph is connected: the value of the eigenvalue bound. 1) Factor xn − 1 over F2 into irreducibles, using Cantor and Zassenhaus’ algorithm (cf. [26], Section 14.3). 2) For each divisor f (x) of xn − 1: P a) Let f (x) = i hi xi and H = (hj−i )i,j∈I . b) Check that the corresponding Tanner graph is connected (i.e., that the greatest common divisor of the indices i with hi = 1 together with n is 1). T c) Compute P the eigenvalues of L = H H: Let ℓP i = k∈I hk hk+i and for j ∈ I compute i ℓi cos(2πij/n). d) Determine the second largest eigenvalue µ2 and output n · (2ℓ0 − µ2 )/(ℓ20 − µ2 ). ZUMBRÄGEL, SKACHEK, AND FLANAGAN: ON THE PSEUDOCODEWORD REDUNDANCY TABLE II B INARY C YCLIC C ODES UP TO L ENGTH 250 WITH d = 2 M EETING THE E IGENVALUE B OUND parameters w-regular [2n, 2n−m, 2] [2n, 2n−m−1, 2] [42, 32, 2] [146, 118, 2] [170, 153, 2] 2m 2m −2 10 18 42 constituent code Hamming c., n = 2m −1, m = 2 . . . 6 Hamming c. with overall parity-check projective geometry code P G(2, 4) projective geometry code P G(2, 8) a certain [85, 68, 6] 21-regular code (the eigenvalue bound is 5.2) TABLE III B INARY C YCLIC C ODES UP TO L ENGTH 250 WITH d ≥ 3 M EETING THE E IGENVALUE B OUND parameters w-regular [n, 1, n] [n, n−m, 3] [7, 3, 4] [15, 7, 5] [21, 11, 6] [63, 37, 9] [73, 45, 10] 2 2m−1 3 4 5 8 9 comments repetition code, n = 3 . . . 250 Hamming c., n = 2m −1, m = 3 . . . 7 dual of the [7, 4, 3] Hamming code Euclidean geometry code EG(2,4) projective geometry code PG(2,4) Euclidean geometry code EG(2,8) projective geometry code PG(2,8) 13 Finally, we apply Proposition 7.5 to get 2 (2m−1 −1) − 2m−2 (2m−1 −1)2 − 2m−2 m (2 −1) 2 (2m−1 −1) − 2m−2 ) = (2m −1 (2m−2 −1) 3 (2m−2 −1) + 1 , = 2m−2 − 1 AWGNC wmin ≥ (2m −1) which proves the result. ACKNOWLEDGMENTS The authors are indebted to the anonymous reviewers for their worthwhile suggestions and recommendations, which significantly improved the exposition of the work, and also to Pascal Vontobel for carefully handling the manuscript. In addition, they would like to thank Nigel Boston, Christine Kelley, and Olgica Milenkovic for helpful discussions. R EFERENCES This algorithm was implemented in the C programming language. Tables II and III give a complete list of all cases in which the eigenvalue bound equals the minimum Hamming distance d, for the cases d = 2 and d ≥ 3, respectively. In particular, the AWGNC pseudoweight equals the minimum Hamming distance in these cases and thus we have for the pseudocodeword redundancy ρAWGNC (C) ≤ n. All examples of minimum distance 2 are actually quasi-cyclic codes as in Remark 9.1 with parity-check matrix H̃ = H ⊗ 12 . We list here the constituent code given by the parity-check matrix H. We conclude this section by proving a result which was observed by the experiments. Lemma 9.3: Let m ≥ 3 and let C be the intersection of a Hamming code of length n = 2m − 1 with a simple paritycheck code of length n, which is a cyclic [n , n − m − 1 , 4] code. Consider its full circulant parity-check matrix H. Then 1 AWGNC wmin (H) ≥ 3 + m−2 >3. 2 −1 In particular, if m = 3 then C is the [7, 3, 4] code and the AWGNC result implies wmin (H) = 4 and ρAWGNC (C) ≤ 7. Proof: Let H be the w-regular full circulant parity-check matrix for C. We claim that w = 2m−1 − 1. Indeed, each row h of H is a codeword of the dual code C ⊥ , and since C ⊥ consists of the codewords of the simplex code and their complements, the weight of h and thus w must be 2m−1 −1, 2m−1 , or 2m − 1. But w cannot be even, for otherwise all codewords of C ⊥ would be of even weight. As w = 2m −1 is clearly impossible, it must hold w = 2m−1 −1. Next, we show that the second largest eigenvalue of L = H T H = (Lj,i )i,j∈I equals µ2 = 2m−2 . Indeed, let h1 and h2 be different rows of H, representing codewords of C ⊥ . As their weight is equal, their Hamming distance is even, and thus it must be 2m−1 . Hence, the size of the intersection of the supports of h1 and h2 is 2m−2−1. This implies that Li,i = w and Lj,i = 2m−2 − 1, for i 6= j. Consequently, L has an eigenvalue of multiplicity n − 1, namely w − (2m−2 − 1) = 2m−2 , and thus µ2 must be 2m−2 . [1] R. Koetter, W.-C. W. Li, P. O. Vontobel, and J. L. Walker, “Characterizations of pseudo-codewords of (low-density) parity-check codes,” Advances in Mathematics, vol. 213, pp. 205–229, Aug. 2007. [2] P. O. Vontobel and R. Koetter, “Graph-cover decoding and finite-length analysis of message-passing iterative decoding of LDPC codes,” CoRR, http://arxiv.org/abs/cs/0512078, Dec. 2005. [3] N. Wiberg, “Codes and decoding on general graphs,” Ph.D. dissertation, Linköping University, Linköping, Sweden, 1996. [4] G. D. Forney, Jr., R. Koetter, F. R. Kschischang, and A. Reznik, “On the effective weights of pseudocodewords for codes defined on graphs with cycles,” in Codes, Systems, and Graphical Models, IMA workshop, Minneapolis, USA, Aug. 1999. New York, USA: Springer, 2001, pp. 101– 112. [5] Y. Kou, S. Lin, and M. P. C. Fossorier, “Low-density parity-check codes based on finite geometries: A rediscovery and new results,” IEEE Trans. Inform. Theory, vol. 47, no. 7, pp. 2711–2736, Nov. 2001. [6] M. Schwartz and A. Vardy, “On the stopping distance and the stopping redundancy of codes,” IEEE Trans. Inform. Theory, vol. 52, no. 3, pp. 922–932, Mar. 2006. [7] J. Han and P. H. Siegel, “Improved upper bounds on stopping redundancy,” IEEE Trans. Inform. Theory, vol. 53, no. 1, pp. 90–104, Jan. 2007. [8] C. Kelley and D. Sridhara, “On the pseudocodeword weight and paritycheck matrix redundancy of linear codes,” in Proc. IEEE Information Theory Workshop (ITW 2007), Lake Tahoe, USA, Sep. 2007. [9] P. O. Vontobel and R. Koetter, “Lower bounds on the minimum pseudoweight of linear codes,” in Proc. IEEE International Symposium on Information Theory (ISIT 2004), Chicago, USA, Jun./Jul. 2004, p. 67. [10] J. Feldman, “Decoding error-correcting codes via linear programming,” Ph. D. dissertation, MIT, Cambridge, USA, 2003. [11] J. Feldman, M. J. Wainwright, and D. R. Karger, “Using linear programming to decode binary linear codes,” IEEE Trans. Inform. Theory, vol. 51, no. 3, pp. 954–972, Mar. 2005. [12] T. Richardson, “Error-floors of LDPC codes,” in Proc. 41st Annual Allerton Conference on Communication, Control, and Computing, Monticallo, USA, Sep. 2003, pp. 1426–1435. [13] S. Laendner, T. Hehn, O. Milenkovic, and J. B. Huber, “The trapping redundancy of linear block codes,” IEEE Trans. Inform. Theory, vol. 55, no. 1, pp. 53–63, Jan. 2009. [14] N. Kashyap, “A decomposition theory for binary linear codes,” IEEE Trans. Inform. Theory, vol. 54, no. 7, pp. 3035–3058, Jul. 2008. [15] R. Smarandache and P. O. Vontobel, “Pseudo-codeword analysis of Tanner graphs from projective and Euclidean planes,” IEEE Trans. Inform. Theory, vol. 53, no. 7, pp. 2376–2393, Jul. 2007. [16] R. M. Roth, Introduction to Coding Theory, Cambridge, United Kingdom: Cambridge University Press, 2006. [17] V. Guruswami, Introduction to Coding Theory, Course Notes, Notes 2. Available: http://www.cs.cmu.edu/∼ venkatg/teaching/codingtheory/notes/notes2.pdf 14 [18] A. R. Calderbank, G. D. Forney, Jr., and A. Vardy, “Minimal tail-biting trellises: the Golay code and more,” IEEE Trans. Inform. Theory, vol. 45, no. 5, pp. 1435–1455, Jul. 1999. [19] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Amsterdam, The Netherlands: North-Holland, 1978. [20] B. Vasic and O. Milenkovic, “Combinatorial constructions of low-density parity-check codes for iterative decoding,” IEEE Trans. Inform. Theory, vol. 50, no. 6, pp. 1156–1176, Jun. 2004. [21] N. Kashyap and A. Vardy, “Stopping sets in codes from designs,” in Proc. IEEE International Symposium on Information Theory (ISIT 2003), Yokohama, Japan, Jun./Jul. 2003, p. 122. SUBMITTED TO IEEE TRANSACTIONS ON INFORMATION THEORY [22] S.-T. Xia and F.-W. Fu, “Minimum pseudo-codewords of LDPC codes,” in Proc. IEEE Information Theory Workshop (ITW ’06), Chengdu, China, Oct. 2006, pp. 109–113. [23] J. Simonis, “On generator matrices of codes,” IEEE Trans. Inform. Theory, vol. 38, no. 2, p. 516, Mar. 1992. [24] M. Franz, Convex – a Maple package for convex geometry, 2009. Available: http://www-fourier.ujf-grenoble.fr/∼ franz/convex [25] P. J. Davis, Circulant Matrices, New York, USA: John Wiley & Sons, 1979. [26] J. von zur Gathen and J. Gerhard, Modern Computer Algebra (2nd ed.), Cambridge, United Kingdom: Cambridge University Press, 2003.