Theory and Practice of Non-binary Graph-based Codes

Download or read book Theory and Practice of Non-binary Graph-based Codes written by Behzad Amiri and published by . This book was released on 2015 with total page 127 pages. Available in PDF, EPUB and Kindle. Book excerpt: We are undergoing a revolution in data. The ever-growing amount of information in our world has created an unprecedented demand for ultra-reliable, affordable, and resource-efficient data storage systems. Error-correcting codes, as a critical component of any memory device, will play a crucial role in the future of data storage. One particular class of error-correcting codes, known as graph-based codes, has drawn significant attention in both academia and in industry. Graph-based codes offer superior performance compared to traditional algebraic codes. Recently, it has been shown that non-binary graph-based codes, which operate over finite fields rather than binary alphabets, outperform their binary counterparts and exhibit outstanding overall performance. For this reason, these codes are particularly suitable for emerging data storage systems. In this dissertation, we present a comprehensive combinatorial analysis of non-binary graph-based codes. We perform both finite-length and asymptotic analyses for these codes, providing a systematic framework to evaluate and optimize various families of non-binary graph-based codes. In the finite-length case, we provide a mathematical characterization of the error floor problem, including a general definition of absorbing sets over non-binary alphabets. We consider several structured low-density parity-check (LDPC) codes, including quasi-cyclic and spatially-coupled codes, as well as unstructured LDPC codes. We offer design guidelines for non-binary LDPC codes with outstanding performance in extremely low error-rate regimes; making them excellent candidates for data storage applications. In the asymptotic case, we provide a novel toolbox for the evaluation of families of non-binary graph-based codes. By utilizing insights from graph theory and combinatorics, we establish enumerators for a general family of graph-based codes which are constructed based on protographs. We provide asymptotic distributions of codewords and trapping sets for the family of protograph-based codes. Furthermore, we present an asymptotic enumeration of binary and non-binary elementary absorbing sets for regular code ensembles. The contributions of this dissertation can potentially impact a broad range of data storage and communication technologies that require excellent performance in high-reliability regimes.