Constrained codes for intercell interference mitigation and dynamic thresholding in flash memories

• Main Author: Vu, Van Khu
• Other Authors: Chee Yeow Meng
• Format: Theses and Dissertations
• Language: English
• Published: 2018
• Subjects: DRNTU::Science::Mathematics::Applied mathematics::Information theory
• Online Access: http://hdl.handle.net/10356/73918
• Institution: Nanyang Technological University

In coding theory and information theory, constrained codes have been studied actively for numerous applications in data recording and data communication systems. Recently, various types of one-dimensional and two-dimensional constrained codes have gained attention owing to their applications for flash memories. Flash memories, a popular non-volatile information storage technology, face some challenges to reliable data recording and retrieval: namely inter-cell interference, charge leakage and over-programming. Our interest is to investigate coding techniques to deal with these challenges. In this dissertation, we design optimal one dimensional constant composition constrained codes associated with efficient encoding/decoding algorithms and investigate some generalizations of these codes such as semi-constrained codes and two dimensional constrained codes. Constrained coding is one effective approach to mitigate the inter-cell interference in flash memories. When used with a dynamic threshold scheme, $q$-ary balanced codes and binary composition codes can mitigate both inter-cell interference and charge leakage. Generalising previous known results, we propose the use of $q$-ary constant-composition constrained codes to mitigate effects of inter-cell interference, charge leakage and over-programming. Our first contribution is a closed formula for the maximal size of these constrained codes. Then we determine the asymptotic rates of these codes for any $q$ and any given constant composition ratio. In addition, we also find the optimal constant composition ratio such that the asymptotic rates of these constant composition constrained codes achieve the constrained channel capacity. For illustration, the numerical results are computed and shown in this work. Consequently, we recover known results and answer some open problems. Our codes are optimal and can be encoded/decoded efficiently. However, avoiding all the problematic patterns reduces the storage capacity. Hence, we look at semi-constrained codes where each codeword contains a small number of problematic patterns. We present the class of q-ary constant-composition semi-constrained codes whose codewords have constant composition and allow some specific patterns to appear a certain number of times. As before, we derive results in terms of maximal size, asymptotic rates, and optimal composition ratio. Consequently, we show that by allowing some problematic patterns to appear with very low frequency, the $q$-ary constant composition semi-constrained codes can achieve full capacity $\log_2 q$. We also present efficient encoding/decoding algorithms of these codes. In two-dimensional (2D) flash memories, cells are arranged in rectangle arrays. Thus, the data is stored as a two-dimensional array and the inter-cell interference can affect the victim cell in horizontal, vertical and diagonal directions. Therefore, two-dimensional constrained codes, called 2D ICI-free codes, have been proposed and investigated for mitigation of inter-cell interference. In this dissertation, we initiate the study of 2D constant composition ICI-free codes, where codewords avoid a specified set of patterns and each row has constant composition.