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
© 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, exacerbate the error floor problem by widening the spectrum of problematic objects that contribute to the error floor of an NB-LDPC code. In a recent research, the weight consistency matrix (WCM) framework was introduced as an effective combinatorial NB-LDPC code optimization methodology that is suitable for modern Flash memory and magnetic recording (MR) systems. The WCM framework was used to optimize codes for asymmetric Flash channels, MR channels that have intrinsic memory, in addition to canonical symmetric additive white Gaussian noise channels. In this paper, we provide an in-depth theoretical analysis needed to understand and properly apply the WCM framework. We focus on general absorbing sets of type two (GASTs) as the detrimental objects of interest. In particular, we introduce a novel tree representation of a GAST called the unlabeled GAST tree, using which we prove that the WCM framework is optimal in the sense that it operates on the minimum number of matrices, which are the WCMs, to remove a GAST. Then, we enumerate WCMs and demonstrate the significance of the savings achieved by the WCM framework in the number of matrices processed to remove a GAST. Moreover, we provide a linear-algebraic analysis of the null spaces of WCMs associated with a GAST. We derive the minimum number of edge weight changes needed to remove a GAST via its WCMs, along with how to choose these changes. In addition, we propose a new set of problematic objects, namely oscillating sets of type two (OSTs), which contribute to the error floor of NB-LDPC codes with even column weights on asymmetric channels, and we show how to customize the WCM framework to remove OSTs. We also extend the domain of the WCM framework applications by demonstrating its benefits in optimizing column weight 5 codes, codes used over Flash channels with additional soft information, and spatially coupled codes. The performance gains achieved via the WCM framework range between 1 and nearly 2.5 orders of magnitude in the error floor region over interesting channels.
IEEE Transactions on Information Theory


Non-Binary LDPC Codes for Magnetic Recording Channels: Error Floor Analysis and Optimized Code Design
Hareedy, Ahmed; Amiri, Behzad; Galbraith, Rick; Dolecek, Lara (2016-08-01)
© 2016 IEEE.In this paper, we provide a comprehensive analysis of the error floor along with code optimization guidelines for structured and regular non-binary low-density parity-check (NB-LDPC) codes in magnetic recording (MR) applications. While the topic of the error floor performance of binary LDPC codes over additive white Gaussian noise (AWGN) channels has recently received considerable attention, very little is known about the error floor performance of NB-LDPC codes over other types of channels, des...
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...
Finite-length construction of high performance spatially-coupled codes via optimized partitioning and lifting
Esfahanizadeh, Homa; Hareedy, Ahmed; Dolecek, Lara (2019-01-01)
© 1972-2012 IEEE.Spatially-coupled (SC) codes are a family of graph-based codes that have attracted significant attention, thanks to their capacity approaching performance and low decoding latency. An SC code is constructed by partitioning an underlying block code into a number of components and coupling their copies together. In this paper, we first introduce a general approach for the enumeration of detrimental combinatorial objects in the graph of finite-length SC codes. Our approach is general in the se...
Linear codes from weakly regular plateaued functions and their secret sharing schemes
Mesnager, Sihem; Özbudak, Ferruh; Sinak, Ahmet (2019-03-01)
Linear codes, the most significant class of codes in coding theory, have diverse applications in secret sharing schemes, authentication codes, communication, data storage devices and consumer electronics. The main objectives of this paper are twofold: to construct three-weight linear codes from plateaued functions over finite fields, and to analyze the constructed linear codes for secret sharing schemes. To do this, we generalize the recent contribution of Mesnager given in (Cryptogr Commun 9(1):71-84, 2017...
A General Non-Binary LDPC Code Optimization Framework Suitable for Dense Flash Memory and Magnetic Storage
Hareedy, Ahmed; Lanka, Chinmayi; Dolecek, Lara (2016-09-01)
© 2017 IEEE.Transmission channels underlying modern dense storage systems, e.g., Flash memory and magnetic recording (MR) systems, significantly differ from canonical channels, like additive white Gaussian noise (AWGN) channels. While existing low-density parity-check (LDPC) codes optimized for symmetric, AWGN-like channels are being actively considered for Flash applications, we demonstrate that, due to channel asymmetry, such approaches are inadequate. We introduce a refined definition of absorbing sets, ...
Citation Formats
A. Hareedy, C. Lanka, N. Guo, and L. Dolecek, “A Combinatorial Methodology for Optimizing Non-Binary Graph-Based Codes: Theoretical Analysis and Applications in Data Storage,” IEEE Transactions on Information Theory, vol. 65, no. 4, pp. 2128–2154, 2019, Accessed: 00, 2022. [Online]. Available: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85053344950&origin=inward.