Treffer: On Decoding Irregular Tanner Codes With Local-Optimality Guarantees

Title:
On Decoding Irregular Tanner Codes With Local-Optimality Guarantees
Authors:
HALABI, Nissim, EVEN, Guy
Source:
IEEE transactions on information theory. 60(1):191-211
Publisher Information:
New York, NY: Institute of Electrical and Electronics Engineers, 2014.
Publication Year:
2014
Physical Description:
print, 37 ref
Original Material:
INIST-CNRS
Subject Terms:
Telecommunications, Télécommunications, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Telecommunications et theorie de l'information, Telecommunications and information theory, Théorie de l'information, du signal et des communications, Information, signal and communications theory, Théorie de l'information, Information theory, Théorie du signal et des communications, Signal and communications theory, Codage, codes, Coding, codes, Code correcteur erreur, Error correcting code, Código corrector error, Algorithme, Algorithm, Algoritmo, Approche crédibiliste, Credal approach, Enfoque credal, Borne inférieure, Lower bound, Cota inferior, Code binaire, Binary code, Código binario, Code contrôle parité, Parity check codes, Code linéaire, Linear code, Código lineal, Densité élevée, High density, Densidad elevada, Décodage itératif, Iterative decoding, Décodage maximum vraisemblance, Maximum likelihood decoding, Descodificación máxima verosimilitud, Envoi message, Message passing, Graphe de Tanner, Tanner graph, Grafo de Tanner, Maximum vraisemblance, Maximum likelihood, Maxima verosimilitud, Méthode combinatoire, Combinatorial method, Método combinatorio, Méthode itérative, Iterative method, Método iterativo, Programmation linéaire, Linear programming, Programación lineal, Code irrégulier, Irregular code, Error bounds, IDPC codes, Tanner codes, factor graphs, graph cover, linear programming (LP) decoding, local optimality, max-product algorithm, maximum-likelihood (ML) certificate, memoryless binary-input output-symmetric (MBIOS) channel, message-passing algorithms, min-sum algorithm, thresholds
Document Type:
Fachzeitschrift Article
File Description:
text
Language:
English
Author Affiliations:
School of Electrical Engineering, Tel-Aviv University, Tel-Aviv 69978, Israel
ISSN:
0018-9448
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=28149716
Rights:
Copyright 2015 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Telecommunications and information theory
Accession Number:
edscal.28149716
Database:
PASCAL Archive

Weitere Informationen

We consider decoding of binary linear Tanner codes using message-passing iterative decoding and linear-programming (LP) decoding in memoryless binary-input output-symmetric (MBIOS) channels. We present new certificates that are based on a combinatorial characterization for the local optimality of a codeword in irregular Tanner codes with respect to any MBIOS channel. This characterization is a generalization of (Arora et al., Proc. ACM Symp. Theory of Computing, 2009) and (Vontobel, Proc. Inf. Theory and Appl. Workshop, 2010) and is based on a conical combination of normalized weighted subtrees in the computation trees of the Tanner graph. These subtrees may have any finite height h (even equal or greater than half of the girth of the Tanner graph). In addition, the degrees of local-code nodes in these subtrees are not restricted to two (i.e., these subtrees are not restricted to skinny trees). We prove that local optimality in this new characterization implies maximum-likelihood (ML) optimality and LP optimality, and show that a certificate can be computed efficiently. We also present a new message-passing iterative decoding algorithm, called normalized weighted min-sum (NWMS). NWMS decoding is a belief-propagation (BP) type algorithm that applies to any irregular binary Tanner code with single parity-check local codes (e.g., low-density and high-density parity-check codes). We prove that if a locally optimal codeword with respect to height parameter h exists (whereby notably h is not limited by the girth of the Tanner graph), then NWMS decoding finds this codeword in h iterations. The decoding guarantee of the NWMS decoding algorithm applies whenever there exists a locally optimal codeword. Because local optimality of a codeword implies that it is the unique ML codeword, the decoding guarantee also provides an ML certificate for this codeword. Finally, we apply the new local-optimality characterization to regular Tanner codes, and prove lower bounds on the noise thresholds of LP decoding in MBIOS channels. When the noise is below these lower bounds, the probability that LP decoding fails to decode the transmitted codeword decays doubly exponentially in the girth of the Tanner graph.