Siyi Yang

GRADE-AO: A Probabilistic Framework to Optimize Spatially-Coupled Codes with High Memories

Spatially-coupled (SC) codes, known for their threshold saturation phenomenon and low-latency windowed decoding algorithms, are ideal for streaming applications. They also find applications in various data storage systems and quantum communications because of their excellent performance. 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 optimal SC codes with high memory is known to be hard. Existing algorithmic solutions do not have performance guarantees. This project is aimed at devising efficient solutions with theoretically provable performance guarantees for constructing near-optimal SC codes with high memories.

The performance of LDPC codes are typically limited by the existence of detrimental objects (structured subgraphs in the Tanner graphs of LDPC codes). For SC-LDPC codes, we found that there exist closed-form representations of the expected number of objects with any topologies in SC-LDPC ensembles with respect to the density distribution of partitioning matrices. Moreover, the gradients of those representations are also derivable, which motivates a probabilistic framework that obtains (locally) optimal density distributions via gradient descent: we refer to this process as gradient descent distributor (GRADE). Starting from random partitioning matrices abiding by the obtained distribution, we perform low complexity optimization algorithms, referred to as algorithmic optimizer (AO) over the cycle properties to construct high memory, high performance quasi-cyclic SC codes. Simulation results show that codes obtained through the GRADE-AO framework notably outperform state-of-the-art SC codes with the same constraint length and codes with uniform partitioning, in both the error-floor region and the waterfall region.

This method can be universally applied to more sophisticated base matrices, which enables efficient constructions of near-optimal codes such as multi-dimensional (MD) SC-LDPC codes and SC-irregular repeat-accumulate (IRA) codes by applying GRADE-AO to SC-LDPC codes and IRA codes, respectively. Our methods can be naturally extended to finer-grained optimization on objects instead of cycles only, which allows us to better exploit the power of spatial-coupling while cycles are not necessarily the smallest units that fully determines the performance of LDPC codes. In this regard, our framework has potential to provide more accurate performance prediction of error-floor regions of SC-LDPC ensembles. We are currently working towards the theoretical explanation of the threshold gain observed from non-uniformly coupled LDPC codes, which can universally unveil the unknown reason of the performance gain obtained from GRADE-AO and MD-SC codes.

Hierarchical Codes with Scalability and Flexibility: Cloud Storage and Next-Generation Memories

I proposed a novel construction of codes offering hierarchical localities that is based on so-called Extended Cauchy (EC) codes; the proposed construction is the first solution in this area to be shown to possess both scalability, heterogeneity, and flexibility, which are critical for practical storage systems. Heterogeneity is the property that data lengths and error rates at different local blocks can differ. Flexibility refers the ability to split a local block into smaller pieces if it becomes of higher demand. Scalability is the ability to accommodate additional workload without revamping the existing infrastructure. I further extended this idea to decentralized cloud storage with arbitrary topologies, where no central node controls all the processing. Decentralization is the major concept of blockchain, and has been adopted by various applications nowadays, to increase better data privacy and lower costs. While erasure correction is sufficient for cloud storage, hybrid error/erasure correction is needed for memory devices: I have designed an efficient decoding algorithm for the proposed coding solution.

Permutation Codes for Rank Modulation

Generalized transposition errors are encountered in various applications, such as synchronizing modified copies of ordered dataset across different devices through the cloud, and rank modulation in flash memories and DNA storage. These errors can be appropriately modeled by the generalized Cayley metric and corrected by the permutation codes. I proposed a coding scheme of order-optimal codes in this metric, and extended the result by developing a construction of systematic permutation codes in this metric that is also order-optimal. These codes have been proved to be more rate efficient than the existing permutation codes based on interleaving. This work was nominated for the Memorable Paper Award at NVMW 2018.