nach oben

Designs, Codes and Cryptography

Erschienen in:

23.03.2018

Pseudocodeword-free criterion for codes with cycle-free Tanner graph

verfasst von: Wittawat Kositwattanarerk

Erschienen in: Designs, Codes and Cryptography | Ausgabe 12/2018

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Iterative decoding and linear programming decoding are guaranteed to converge to the maximum-likelihood codeword when the underlying Tanner graph is cycle-free. Therefore, cycles are usually seen as the culprit of low-density parity-check codes. In this paper, we argue in the context of graph cover pseudocodeword that, for a code that permits a cycle-free Tanner graph, cycles have no effect on error performance as long as they are a part of redundant rows. Specifically, we characterize all parity-check matrices that are pseudocodeword-free for such class of codes.

Vorheriger Artikel A ring-like cascade connection and a class of NFSRs with the same cycle structures

Nächster Artikel Speeding up Huff form of elliptic curves

Axvig N., Dreher D., Morrison K., Psota E., Perez L.C., Walker J.L.: Analysis of connections between pseudocodewords. IEEE Trans. Inform. Theory 55(9), 4099–4107 (2009).MathSciNetCrossRef

Barahona F., Grötschel M.: On the cycle polytope of a binary matroid. J. Comb. Theory Ser. B 40, 40–62 (1986).MathSciNetCrossRef

Etzion T., Trachtenberg A., Vardy A.: Which codes have cycle-free Tanner graphs? IEEE Trans. Inform. Theory 45(6), 2173–2181 (1999).MathSciNetCrossRef

Feldman J., Wainwright M.J., Karger D.R.: Using linear programming to decode binary linear codes. IEEE Trans. Inform. Theory 51(3), 954–972 (2005).MathSciNetCrossRef

Guichard D.: An Introduction to Combinatorics and Graph Theory. https://www.whitman.edu/mathematics/cgt_online/cgt.pdf.

Kashyap N.: A decomposition theory for binary linear codes. IEEE Trans. Inform. Theory 54(7), 3035–3058 (2008).MathSciNetCrossRef

Kelley C., Sridhara D.: Pseudocodewords of Tanner graphs. IEEE Trans. Inform. Theory 53(11), 4013–4038 (2007).MathSciNetCrossRef

Koetter R., Li W.-C.W., Vontobel P.O., Walker J.: Characterizations of pseudo-codewords of (low-density) parity-check codes. Adv. Math. 213(1), 205–229 (2007).MathSciNetCrossRef

Kositwattanarerk W., Matthews G.L.: Lifting the fundamental cone and enumerating the pseudocodewords of a parity-check code. IEEE Trans. Inform. Theory 57(2), 898–909 (2011).MathSciNetCrossRef

10.

Kou Y., Lin S., Fossorier M.P.C.: Low-density parity-check codes based on finite geometries: a rediscovery and new results. IEEE Trans. Inform. Theory 47(7), 2711–2736 (2001).MathSciNetCrossRef

11.

Kschischang F.R., Frey B.J., Loeliger H.-A.: Factor graphs and the sum-product algorithm. IEEE Trans. Inform. Theory 47(2), 498–519 (2001).MathSciNetCrossRef

12.

Lechner G.: The effect of cycles on binary message-passing decoding of LDPC codes. In: Proc. Comm. Theory Workshop, Australia, IEEE (2010).

13.

MacKay D.J.C., Neal R.M.: Near Shannon limit performance of low density parity check codes. Electron. Lett. 32, 1645–1646 (1996).CrossRef

14.

Richardson T., Shokrollahi A., Urbanke R.: Design of capacity-approaching irregular low-density parity-check codes. IEEE Trans. Inform. Theory 47(2), 619–637 (2001).MathSciNetCrossRef

15.

Seymour P.D.: Decomposition of regular matroids. J. Comb. Theory Ser. B 52, 305–359 (1980).MathSciNetCrossRef

16.

Tian T., Jones C.R., Villasenor J.D., Wesel R.D.: Selective avoidance of cycles in irregular LDPC code construction. IEEE Trans. Commun. 52, 1242–1247 (2004).CrossRef

17.

Wiberg N.: Codes and decoding on general graphs. Ph.D. thesis, Linköping University, Linköping (1996).

18.

Xia S.-T., Fu F.-W.: Minimum pseudoweight and minimum pseudocodewords of LDPC codes. IEEE Trans. Inform. Theory 54, 480–485 (2008).MathSciNetCrossRef

19.

Xu J., Chen L., Djurdjevic I., Lin S., Abdel-Ghaffar K.: Construction of regular and irregular LDPC codes: geometry decomposition and masking. IEEE Trans. Inform. Theory 53, 121–134 (2007).MathSciNetCrossRef

20.

Zumbragel J., Skachek V., Flanagan M.F.: On the pseudocodeword redundancy of binary linear codes. IEEE Trans. Inform. Theory 58, 4848–4861 (2012).MathSciNetCrossRef

Titel: Pseudocodeword-free criterion for codes with cycle-free Tanner graph
verfasst von: Wittawat Kositwattanarerk
Publikationsdatum: 23.03.2018
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 12/2018
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-018-0476-3

Springer Professional

Pseudocodeword-free criterion for codes with cycle-free Tanner graph

Abstract

Premium Partner

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 12/2018

Constructions of complete permutation polynomials

Frame difference families and resolvable balanced incomplete block designs

Group invariant weighing matrices

A ring-like cascade connection and a class of NFSRs with the same cycle structures

Non-symmetric 2-designs admitting a two-dimensional projective linear group

A note on the weight spectrum of the Schubert code

Premium Partner