• Efficient Implementation of Li...

Result: Efficient Implementation of Linear Programming Decoding

Title:
Efficient Implementation of Linear Programming Decoding
Authors:
TAGHAVI, Mohammad H, SHOKROLLAHI, Amin, SIEGEL, Paul H
Source:
IEEE transactions on information theory. 57(9):5960-5982
Publisher Information:
New York, NY: Institute of Electrical and Electronics Engineers, 2011.
Publication Year:
2011
Physical Description:
print, 27 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, Codage, Coding, Codificación, Code contrôle parité, Parity check codes, Contrôle parité, Parity check, Control paridad, Décodage adaptatif, Adaptive decoding, Envoi message, Message passing, Equation linéaire, Linear equation, Ecuación lineal, Evaluation performance, Performance evaluation, Evaluación prestación, Flexibilité, Flexibility, Flexibilidad, Implémentation, Implementation, Implementación, Méthode adaptative, Adaptive method, Método adaptativo, Méthode analytique, Analytical method, Método analítico, Méthode gradient conjugué, Conjugate gradient method, Método gradiente conjugado, Méthode itérative, Iterative method, Método iterativo, Méthode point intérieur, Interior point method, Método punto interior, Programmation linéaire, Linear programming, Programación lineal, Préconditionnement, Preconditioning, Precondicionamiento, Simulation ordinateur, Computer simulation, Simulación computadora, Adaptive linear programming (LP) decoding, conjugate-gradient method, interior-point methods, low-density parity-check (LDPC) codes, preconditioning
Document Type:
Academic journal Article
File Description:
text
Language:
English
Author Affiliations:
Qualcomm, Inc., San Diego, CA 92121, United States
School of Basic Sciences and School of Computer Science and Communications, Ecole Polytechnique Fédérale de Lausanne (EPFL), 1015 Lausanne, Switzerland
Electrical and Computer Engineering Department and the Center for Magnetic Recording Research, University of California, San Diego, La Jolla, CA 92093-0401, United States
ISSN:
0018-9448
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=24554470
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.24554470
Database:
PASCAL Archive

Further Information

While linear programming (LP) decoding provides more flexibility for finite-length performance analysis than iterative message-passing (IMP) decoding, it is computationally more complex to implement in its original form, due to both the large size of the relaxed LP problem and the inefficiency of using general-purpose LP solvers. This paper explores ideas for fast LP decoding of low-density parity-check (LDPC) codes. By modifying the previously reported Adaptive LP decoding scheme to allow removal of unnecessary constraints, we first prove that LP decoding can be performed by solving a number of LP problems that each contains at most one linear constraint derived from each of the parity-check constraints. By exploiting this property, we study a sparse interior-point implementation for solving this sequence of linear programs. Since the most complex part of each iteration of the interior-point algorithm is the solution of a (usually ill-conditioned) system of linear equations for finding the step direction, we propose a preconditioning algorithm to facilitate solving such systems iteratively. The proposed preconditioning algorithm is similar to the encoding procedure of LDPC codes, and we demonstrate its effectiveness via both analytical methods and computer simulation results.