The Secret Arithmetic of Patterns: A General Method for Designing Constrained Codes Based on Lexicographic Indexing

Download

index.pdf

Date

2022-01-01

Author

Hareedy, Ahmed
Dabak, Beyza
Calderbank, Robert

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

107
views

32
downloads

IEEEConstrained codes are used to prevent errors from occurring in various data storage and data transmission systems. They can help in increasing the storage density of magnetic storage devices, in managing the lifetime of solid-state storage devices, and in increasing the reliability of data transmission over wires. Over the years, designing practical (complexity-wise) capacity-achieving constrained codes has been an area of research gaining significant interest. We recently designed various constrained codes based on lexicographic indexing. We introduced binary symmetric lexicographically-ordered constrained (S-LOCO) codes, q-ary asymmetric LOCO (QA-LOCO) codes, and a class of two-dimensional LOCO (TD-LOCO) codes. These families of codes achieve capacity with simple encoding and decoding, and they are easy to reconfigure. We demonstrated that these codes can contribute to notable density and lifetime gains in magnetic recording (MR) and Flash systems, and they find application in other systems too. In this paper, we generalize our work on LOCO codes by presenting a systematic method that guides the code designer to build any constrained code based on lexicographic indexing once the finite set of data patterns to forbid is known. In particular, we connect the set of forbidden patterns directly to the cardinality of the LOCO code and most importantly to the rule that uncovers the index associated with a LOCO codeword. By doing that, we reveal the secret arithmetic of patterns, and make the design of such constrained codes significantly easier. We give examples illustrating the method via codes based on lexicographic indexing from the literature. We then design optimal (rate-wise) constrained codes for the new two-dimensional magnetic recording (TDMR) technology. Over a practical TDMR model, we show notable performance gains as a result of solely applying the new codes. Moreover, we show how near-optimal constrained codes for TDMR can be designed and used to further reduce complexity and error propagation. All the newly introduced LOCO codes are designed using the proposed general method, and they inherit all the desirable properties in our previously designed LOCO codes.

Subject Keywords

Codes, Constrained codes, data storage, Decoding, Flash memories, general method, Indexing, isolation patterns, lexicographic indexing, lexicographic ordering, Magnetic recording, reconfigurable codes, Symbols, Systematics, two-dimensional magnetic recording

URI

https://hdl.handle.net/11511/97704

Journal

IEEE Transactions on Information Theory

DOI

https://doi.org/10.1109/tit.2022.3170692

Collections

Department of Electrical and Electronics Engineering, Article

Suggestions

OpenMETU
Core

A Channel-Aware Combinatorial Approach to Design High Performance Spatially-Coupled Codes Hareedy, Ahmed; Wu, Ruiyi; Dolecek, Lara (2020-08-01) Because of their capacity-approaching performance and their complexity/latency advantages, spatially-coupled (SC) codes are among the most attractive error-correcting codes for use in modern dense data storage systems. SC codes are constructed by partitioning an underlying block code and coupling the partitioned components. Here, we focus on circulant-based SC codes. Recently, the optimal overlap (OO), circulant power optimizer (CPO) approach was introduced to construct high performance SC codes for additiv...
A Combinatorial Methodology for Optimizing Non-Binary Graph-Based Codes: Theoretical Analysis and Applications in Data Storage Hareedy, Ahmed; Lanka, Chinmayi; Guo, Nian; Dolecek, Lara (2019-04-01) © 2018 IEEE.Non-binary (NB) low-density parity-check (LDPC) codes are graph-based codes that are increasingly being considered as a powerful error correction tool for modern dense storage devices. Optimizing NB-LDPC codes to overcome their error floor is one of the main code design challenges facing storage engineers upon deploying such codes in practice. Furthermore, the increasing levels of asymmetry incorporated by the channels underlying modern dense storage systems, e.g., multi-level Flash systems, exa...
The Development and hardware implementation of a dynamically reconfigurable and area optimized cyclic redundancy check architecture Yurt, Özcan; Schmidt, Şenan Ece; Department of Electrical and Electronics Engineering (2013) The Cyclic Redundancy Check (CRC) calculation for data communication protocols is implemented by hardware calculators in several systems due to increasing throughput requirements of data communication protocols. Furthermore CRC is employed in many small scale embedded systems with different types of data communication interfaces that are implemented on FPGA. Resource utilization of these systems is frequently a critical parameter with regards to cost. In many cases, limited logic units of an FPGA have to be...
A Theoretical Performance Bound for Joint Beamformer Design of Wireless Fronthaul and Access Links in Downlink C-RAN Kadan, Fehmi Emre; Yılmaz, Ali Özgür (2021-01-01) It is known that data rates in standard cellular networks are limited due to inter-cell interference. An effective solution to this problem is to use the multi-cell cooperation idea. In Cloud Radio Access Network (C-RAN), which is a candidate solution in 5G and future communication networks, cooperation is applied by means of central processors (CPs) connected to simple remote radio heads with finite capacity fronthaul links. In this study, we consider a downlink C-RAN with a wireless fronthaul and aim to m...
The Concatenated Structure of Quasi-Cyclic Codes and an Improvement of Jensen's Bound Guneri, Cem; Özbudak, Ferruh (2013-02-01) Following Jensen's work from 1985, a quasi-cyclic code can be written as a direct sum of concatenated codes, where the inner codes are minimal cyclic codes and the outer codes are linear codes. We observe that the outer codes are nothing but the constituents of the quasi-cyclic code in the sense of Ling-Sole. This concatenated structure enables us to recover some earlier results on quasi-cyclic codes in a simple way, including one of our recent results which says that a quasi-cyclic code with cyclic constit...

Citation Formats

A. Hareedy, B. Dabak, and R. Calderbank, “The Secret Arithmetic of Patterns: A General Method for Designing Constrained Codes Based on Lexicographic Indexing,” IEEE Transactions on Information Theory, pp. 0–0, 2022, Accessed: 00, 2022. [Online]. Available: https://hdl.handle.net/11511/97704.