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


Yang S., HAREEDY A., Calderbank R., Dolecek L.

IEEE Transactions on Information Theory, vol.69, no.2, pp.886-909, 2023 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 69 Issue: 2
  • Publication Date: 2023
  • Doi Number: 10.1109/tit.2022.3207321
  • Journal Name: IEEE Transactions on Information Theory
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, PASCAL, Aerospace Database, Applied Science & Technology Source, Business Source Elite, Business Source Premier, Communication Abstracts, Compendex, Computer & Applied Sciences, INSPEC, MathSciNet, Metadex, zbMATH, Civil Engineering Abstracts
  • Page Numbers: pp.886-909
  • Keywords: Codes, Optimization, Parity check codes, Memory management, Partitioning algorithms, Probabilistic logic, Convolutional codes, LDPC codes, spatially-coupled codes, absorbing sets, edge distribution, gradient descent, near-optimal partitioning, data storage, flash memories, magnetic recording, communications, LDPC CONVOLUTIONAL-CODES, ABSORBING SETS, THRESHOLD SATURATION, PERFORMANCE, DESIGN
  • Middle East Technical University Affiliated: Yes

Abstract

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.