Constructions and Decoding of Cyclic Codes Over $b$ -Symbol Read Channels
Authors:
Top Cited Papers
- 27 January 2016
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 62 (4) , 1541-1551
Abstract
Symbol-pair read channels, in which the outputs of the read process are pairs of consecutive symbols, were recently studied by Cassuto and Blaum. This new paradigm is motivated by the limitations of the reading process in high density data storage systems. They studied error correction in this new paradigm, specifically, the relationship between the minimum Hamming distance of an error correcting code and the minimum pair distance, which is the minimum Hamming distance between symbol-pair vectors derived from codewords of the code. It was proved that for a linear cyclic code with minimum Hamming distance d H , the corresponding minimum pair distance is at least d H +3. In this paper, we show that, for a given linear cyclic code with a minimum Hamming distance d H , the minimum pair distance is at least d H + (dH/2). We then describe a decoding algorithm, based upon a bounded distance decoder for the cyclic code, whose symbol-pair error correcting capabilities reflect the larger minimum pair distance. Finally, we consider the case where the read channel output is a larger number, b ≥3, of consecutive symbols, and we provide extensions of several concepts, results, and code constructions to this setting.Keywords
Funding Information
- ISEF Foundation, the Lester Deutsch Fellowship, the University of California Laboratory Fees Research Program (09-LR-06-118620-SIEP)
- National Science Foundation (CCF-1116739, CCF-1405119)
- Center for Magnetic Recording Research, University of California at San Diego
- NSF Expeditions in Computing Program (CCF-0832824)
- Electrical Engineering Department, California Institute of Technology, Pasadena, CA, USA
- Technion, within the Fellowship from the Lady Davis Foundation and by a Viterbi Research Fellowship
This publication has 17 references indexed in Scilit:
- Maximum Distance Separable Codes for Symbol-Pair Read ChannelsIEEE Transactions on Information Theory, 2013
- Information Theory of DNA Shotgun SequencingIEEE Transactions on Information Theory, 2013
- On the uncertainty of information retrieval in associative memories2012
- Information theory for DNA sequencing: Part I: A basic model2012
- Decoding of cyclic codes over symbol-pair read channels2012
- Error graphs and the reconstruction of elements in groupsJournal of Combinatorial Theory, Series A, 2009
- Correcting errors and erasures via the syndrome varietyJournal of Pure and Applied Algebra, 2005
- Efficient Reconstruction of Sequences from Their Subsequences or SupersequencesJournal of Combinatorial Theory, Series A, 2001
- On error-and-erasure decoding of cyclic codesIEEE Transactions on Information Theory, 1992
- Detecting and correcting multiple bursts for binary cyclic codes (Corresp.)IEEE Transactions on Information Theory, 1970