Breaking the Computational Bottleneck: Probabilistic Optimization of High-Memory Spatially-Coupled Codes

2022-01-01
Yang, Siyi
Hareedy, Ahmed
Calderbank, Robert
Dolecek, Lara
IEEESpatially-coupled (SC) codes, known for their threshold saturation phenomenon and low-latency windowed decoding algorithms, are ideal for streaming applications and data storage systems. SC codes are constructed by partitioning an underlying block code, followed by rearranging and concatenating the partitioned components in a convolutional manner. The number of partitioned components determines the memory of SC codes. In this paper, we investigate the relation between the performance of SC codes and the density distribution of partitioning matrices. While adopting higher memories results in improved SC code performance, obtaining finite-length, high-performance SC codes with high memory is known to be computationally challenging.We break this computational bottleneck by developing a novel probabilistic framework that obtains (locally) optimal density distributions via gradient descent. Starting from random partitioning matrices abiding by the obtained distribution, we perform low-complexity optimization algorithms that minimize the number of detrimental objects to construct high-memory, high-performance quasi-cyclic SC codes. We apply our framework to various objects of interest, from the simplest short cycles, to more sophisticated objects such as concatenated cycles aiming at finer-grained optimization. Simulation results show that codes obtained through our proposed method notably outperform state-of-the-art SC codes with the same constraint length and optimized SC codes with uniform partitioning. The performance gain is shown to be universal over a variety of channels, from canonical channels such as additive white Gaussian noise and binary symmetric channels, to practical channels underlying flash memory and magnetic recording systems.
IEEE Transactions on Information Theory

Suggestions

GRADE-AO: Towards Near-Optimal Spatially-Coupled Codes with High Memories
Yang, Siyi; Hareedy, Ahmed; Venkatasubramanian, Shyam; Calderbank, Robert; Dolecek, Lara (2021-07-12)
Spatially-coupled (SC) codes, known for their threshold saturation phenomenon and low-latency windowed decoding algorithms, are ideal for streaming applications and data storage systems. SC codes are constructed by partitioning an underlying block code, followed by rearranging and concatenating the partitioned components in a 'convolutional' manner. The number of partitioned components determines the 'memory' of SC codes. While adopting higher memories results in improved SC code performance, obtaining opti...
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...
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, ...
Belief propagation decoding of polar codes under factor graph permutations
Peker, Ahmet Gökhan; Yücel, Melek Diker; Department of Electrical and Electronics Engineering (2018)
Polar codes, introduced by Arıkan, are linear block codes that can achieve the capacity of symmetric binary-input discrete memoryless channels with low encoding and decoding complexity. Polar codes of block length N are constructed by channel polarization method, which consists of channel combining and splitting operations to obtain N polarized subchannels from N copies of binary-input discrete memoryless channels. As N grows, symmetric channel capacities of the polarized subchannels converge to either 0 or...
Citation Formats
S. Yang, A. Hareedy, R. Calderbank, and L. Dolecek, “Breaking the Computational Bottleneck: Probabilistic Optimization of High-Memory Spatially-Coupled Codes,” IEEE Transactions on Information Theory, pp. 0–0, 2022, Accessed: 00, 2022. [Online]. Available: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85139386445&origin=inward.