Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Linear Programming Decoding of Spatially Coupled Codes
 
research article

Linear Programming Decoding of Spatially Coupled Codes

Bazzi, Louay
•
Ghazi, Badih
•
Urbanke, Ruediger L.
2014
Ieee Transactions On Information Theory

For a given family of spatially coupled codes, we prove that the linear programming (LP) threshold on the binary-symmetric channel (BSC) of the tail-biting graph cover ensemble is the same as the LP threshold on the BSC of the derived spatially coupled ensemble. This result is in contrast with the fact that spatial coupling significantly increases the belief propagation threshold. To prove this, we establish some properties related to the dual witness for LP decoding. More precisely, we prove that the existence of a dual witness, which was previously known to be sufficient for LP decoding success, is also necessary and is equivalent to the existence of certain acyclic hyperflows. We also derive a sublinear (in the block length) upper bound on the weight of any edge in such hyperflows, both for regular low-density parity-check (LPDC) codes and spatially coupled codes and we prove that the bound is asymptotically tight for regular LDPC codes. Moreover, we show how to trade crossover probability for LP excess on all the variable nodes, for any binary linear code.

  • Details
  • Metrics
Type
research article
DOI
10.1109/Tit.2014.2325903
Web of Science ID

WOS:000342413600017

Author(s)
Bazzi, Louay
Ghazi, Badih
Urbanke, Ruediger L.
Date Issued

2014

Publisher

Ieee-Inst Electrical Electronics Engineers Inc

Published in
Ieee Transactions On Information Theory
Volume

60

Issue

8

Start page

4677

End page

4698

Subjects

Linear programming (LP) decoding

•

spatially-coupled codes

•

binary-symmetric channel (BSC)

•

low-density parity-check (LDPC) codes

•

factor graphs

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LTHC  
Available on Infoscience
October 23, 2014
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/107799
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés