On Decoding Interleaved Chinese Remainder Codes

Wenhui Li; Vladimir Sidorenko; Johan Sebastian Rosenkilde Nielsen

doi:10.1109/ISIT.2013.6620387

On Decoding Interleaved Chinese Remainder Codes

Wenhui Li
, Vladimir Sidorenko
, Johan Sebastian Rosenkilde Nielsen

Department of Applied Mathematics and Computer Science

Ulm University

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

702 Downloads (Orbit)

Abstract

We model the decoding of Interleaved Chinese Remainder codes as that of finding a short vector in a Z-lattice. Using the LLL algorithm, we obtain an efficient decoding algorithm, correcting errors beyond the unique decoding bound and having nearly linear complexity. The algorithm can fail with a probability dependent on the number of errors, and we give an upper bound for this. Simulation results indicate that the bound is close to the truth. We apply the proposed decoding algorithm for decoding a single CR code using the idea of “Power” decoding, suggested for Reed-Solomon codes. A combination of these two methods can be used to decode low-rate Interleaved Chinese Remainder codes.

Original language	English
Title of host publication	2013 IEEE International Symposium on Information Theory Proceedings (ISIT)
Publisher	IEEE
Publication date	2013
Pages	1052-1056
ISBN (Print)	978-1-4799-0446-4
DOIs	https://doi.org/10.1109/ISIT.2013.6620387
Publication status	Published - 2013
Event	2013 IEEE International Symposium on Information Theory - Istanbul, Turkey Duration: 7 Jul 2013 → 12 Jul 2013 http://www.isit2013.org/

Conference

Conference	2013 IEEE International Symposium on Information Theory
Country/Territory	Turkey
City	Istanbul
Period	07/07/2013 → 12/07/2013
Internet address	http://www.isit2013.org/

Access to Document

10.1109/ISIT.2013.6620387

ISITAccepted author manuscript, 308 KB

OpenUrl availability

Check availability in DTU Findit

Cite this

@inproceedings{8db69ebab1174e8dbd7dfea2f8dae196,

title = "On Decoding Interleaved Chinese Remainder Codes",

abstract = "We model the decoding of Interleaved Chinese Remainder codes as that of finding a short vector in a Z-lattice. Using the LLL algorithm, we obtain an efficient decoding algorithm, correcting errors beyond the unique decoding bound and having nearly linear complexity. The algorithm can fail with a probability dependent on the number of errors, and we give an upper bound for this. Simulation results indicate that the bound is close to the truth. We apply the proposed decoding algorithm for decoding a single CR code using the idea of “Power” decoding, suggested for Reed-Solomon codes. A combination of these two methods can be used to decode low-rate Interleaved Chinese Remainder codes.",

author = "Wenhui Li and Vladimir Sidorenko and Nielsen, \{Johan Sebastian Rosenkilde\}",

year = "2013",

doi = "10.1109/ISIT.2013.6620387",

language = "English",

isbn = "978-1-4799-0446-4",

pages = "1052--1056",

booktitle = "2013 IEEE International Symposium on Information Theory Proceedings (ISIT)",

publisher = "IEEE",

address = "United States",

note = "2013 IEEE International Symposium on Information Theory, ISIT 2013 ; Conference date: 07-07-2013 Through 12-07-2013",

url = "http://www.isit2013.org/",

}

TY - GEN

T1 - On Decoding Interleaved Chinese Remainder Codes

AU - Li, Wenhui

AU - Sidorenko, Vladimir

AU - Nielsen, Johan Sebastian Rosenkilde

PY - 2013

Y1 - 2013

N2 - We model the decoding of Interleaved Chinese Remainder codes as that of finding a short vector in a Z-lattice. Using the LLL algorithm, we obtain an efficient decoding algorithm, correcting errors beyond the unique decoding bound and having nearly linear complexity. The algorithm can fail with a probability dependent on the number of errors, and we give an upper bound for this. Simulation results indicate that the bound is close to the truth. We apply the proposed decoding algorithm for decoding a single CR code using the idea of “Power” decoding, suggested for Reed-Solomon codes. A combination of these two methods can be used to decode low-rate Interleaved Chinese Remainder codes.

AB - We model the decoding of Interleaved Chinese Remainder codes as that of finding a short vector in a Z-lattice. Using the LLL algorithm, we obtain an efficient decoding algorithm, correcting errors beyond the unique decoding bound and having nearly linear complexity. The algorithm can fail with a probability dependent on the number of errors, and we give an upper bound for this. Simulation results indicate that the bound is close to the truth. We apply the proposed decoding algorithm for decoding a single CR code using the idea of “Power” decoding, suggested for Reed-Solomon codes. A combination of these two methods can be used to decode low-rate Interleaved Chinese Remainder codes.

U2 - 10.1109/ISIT.2013.6620387

DO - 10.1109/ISIT.2013.6620387

M3 - Article in proceedings

SN - 978-1-4799-0446-4

SP - 1052

EP - 1056

BT - 2013 IEEE International Symposium on Information Theory Proceedings (ISIT)

PB - IEEE

T2 - 2013 IEEE International Symposium on Information Theory

Y2 - 7 July 2013 through 12 July 2013

ER -

On Decoding Interleaved Chinese Remainder Codes

Abstract

Conference

Access to Document

OpenUrl availability

Fingerprint

Cite this