IEICE TRANSACTIONS on Fundamentals
Linear Programming Decoding of Binary Linear Codes for Symbol-Pair Read Channel
Summary :
In this study, we develop a new algorithm for decoding binary linear codes for symbol-pair read channels. The symbol-pair read channel was recently introduced by Cassuto and Blaum to model channels with higher write resolutions than read resolutions. The proposed decoding algorithm is based on linear programming (LP). For LDPC codes, the proposed algorithm runs in time polynomial in the codeword length. It is proved that the proposed LP decoder has the maximum-likelihood (ML) certificate property, i.e., the output of the decoder is guaranteed to be the ML codeword when it is integral. We also introduce the fractional pair distance dfp of the code, which is a lower bound on the minimum pair distance. It is proved that the proposed LP decoder corrects up to ⌈dfp/2⌉-1 errors.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E99-A No.12 pp.2170-2178
- Publication Date
- 2016/12/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E99.A.2170
- Type of Manuscript
- Special Section PAPER (Special Section on Information Theory and Its Applications)
- Category
- Coding Theory and Techniques
Authors
Shunsuke HORII
Waseda University
Toshiyasu MATSUSHIMA
Waseda University
Shigeichi HIRASAWA
Waseda University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Shunsuke HORII, Toshiyasu MATSUSHIMA, Shigeichi HIRASAWA, "Linear Programming Decoding of Binary Linear Codes for Symbol-Pair Read Channel" in IEICE TRANSACTIONS on Fundamentals,
vol. E99-A, no. 12, pp. 2170-2178, December 2016, doi: 10.1587/transfun.E99.A.2170.
Abstract: In this study, we develop a new algorithm for decoding binary linear codes for symbol-pair read channels. The symbol-pair read channel was recently introduced by Cassuto and Blaum to model channels with higher write resolutions than read resolutions. The proposed decoding algorithm is based on linear programming (LP). For LDPC codes, the proposed algorithm runs in time polynomial in the codeword length. It is proved that the proposed LP decoder has the maximum-likelihood (ML) certificate property, i.e., the output of the decoder is guaranteed to be the ML codeword when it is integral. We also introduce the fractional pair distance dfp of the code, which is a lower bound on the minimum pair distance. It is proved that the proposed LP decoder corrects up to ⌈dfp/2⌉-1 errors.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E99.A.2170/_p
Copy
@ARTICLE{e99-a_12_2170,
author={Shunsuke HORII, Toshiyasu MATSUSHIMA, Shigeichi HIRASAWA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Linear Programming Decoding of Binary Linear Codes for Symbol-Pair Read Channel},
year={2016},
volume={E99-A},
number={12},
pages={2170-2178},
abstract={In this study, we develop a new algorithm for decoding binary linear codes for symbol-pair read channels. The symbol-pair read channel was recently introduced by Cassuto and Blaum to model channels with higher write resolutions than read resolutions. The proposed decoding algorithm is based on linear programming (LP). For LDPC codes, the proposed algorithm runs in time polynomial in the codeword length. It is proved that the proposed LP decoder has the maximum-likelihood (ML) certificate property, i.e., the output of the decoder is guaranteed to be the ML codeword when it is integral. We also introduce the fractional pair distance dfp of the code, which is a lower bound on the minimum pair distance. It is proved that the proposed LP decoder corrects up to ⌈dfp/2⌉-1 errors.},
keywords={},
doi={10.1587/transfun.E99.A.2170},
ISSN={1745-1337},
month={December},}
Copy
TY - JOUR
TI - Linear Programming Decoding of Binary Linear Codes for Symbol-Pair Read Channel
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2170
EP - 2178
AU - Shunsuke HORII
AU - Toshiyasu MATSUSHIMA
AU - Shigeichi HIRASAWA
PY - 2016
DO - 10.1587/transfun.E99.A.2170
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E99-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 2016
AB - In this study, we develop a new algorithm for decoding binary linear codes for symbol-pair read channels. The symbol-pair read channel was recently introduced by Cassuto and Blaum to model channels with higher write resolutions than read resolutions. The proposed decoding algorithm is based on linear programming (LP). For LDPC codes, the proposed algorithm runs in time polynomial in the codeword length. It is proved that the proposed LP decoder has the maximum-likelihood (ML) certificate property, i.e., the output of the decoder is guaranteed to be the ML codeword when it is integral. We also introduce the fractional pair distance dfp of the code, which is a lower bound on the minimum pair distance. It is proved that the proposed LP decoder corrects up to ⌈dfp/2⌉-1 errors.
ER -
English
