SSD (Solid State Drive) based on NAND flash memories has been increasingly dominating the global storage market due to its high capacity and speed, low latency time, allowance of random access and lightweight. Therefore, recent research activities for higher density and/or more reliable NAND flash memories have been ever growing. On one hand, the growth of the density of NAND flash memory is successfully driven by an aggressive technology scaling and high-density memory cell. On the other hand, the continuous technology scaling makes NAND flash memories increasingly subject to worse raw storage reliability. In this thesis, a concatenated coding scheme with inner TCM (Trellis Coded Modulation) and outer RS (Reed-Solomon) code is investigated as a solution to the reliability issue in future high density NAND flash memories since it pro-vides powerful error-correcting capability at relatively modest coding/decoding complexity. The reasons to adopt TCM as the inner code are as follows; 1) the bandwidth efficient TCM provides a large coding gain without spending extra memory cells for storing redundant bits, 2) it has linear complexity in terms of code word length, and 3) by carefully designing multi-dimensional signal constellation of TCM, we can avoid some signal combinations causing cell-to-cell interference. In NAND flash memory devices, the basic element, called cell, contains information bits in the form of stored charges. Certain combinations of stored charges in two physically adjacent cells interfere each other and may result in errors when the information bits are retrieved. This technical challenge is alleviated by introducing multi-dimensional TCM technique that represents the levels of stored charges in a group of cells as a constellation in a multi-dimensional signal space. The trellis structure in TCM is utilized to avoid the problematic combinations of stored charges in two physically adjacent cells. Simple RS code with low error correction capability has been applied for the outer code in or-der to correct residual errors, which guarantees a very low PER (Page Error Rate), $10^{-16}$ in our work. Since the PER cannot be evaluated with Monte Carlo simulations, we extensively study and derive a very tight upper bound on the performance of the proposed coding. In particular, the errors produced by Viterbi decoder for the inner code are modeled using a modified Markov chain in which the transition probabilities are estimated from Monte Carlo simulations. Our evaluations at a target PER, $10^{-16}$, show that the proposed coding scheme can save the extra memory cells more than 50% and 66 % as compared to BCH and RS codes, respectively. In a different view, the proposed coding scheme reduces the gaps from capacity by 1.2 dB and 1.8 dB as compared to conventional BCH and RS codes, respectively.
낸드 플래시 메모리 소자는 미세 공정의 사용으로 따른 미세화와 셀 당 저장 비트수의 증가로 인한 다치화로 인하여 그 저장 밀도가 계속 증가하는 추세이다. 저장 밀도의 증가는 셀 간 결합(Coupling)과 수평전하의 확산(lateral charge spreading)을 증대시켜 소자의 신뢰성을 악화시키고 수명을 단축시키게 되었다. 이러한 부작용에 기인한 데이터 오류의 증가로, 오류 개수에 대해 지수적인 복잡도와 많은 여분 비트를 요하는 기존의 BCH부호나 RS (Reed-Solomon) 부호를 대체할 새로운 오류 정정 부호의 필요성이 증대되었다. 본 연구에서는 대역폭이 제한된 환경에서 높은 부호화 이득을 가지는 격자 부호(Trellis Coded Modulation)를 내부 부호로 하고, 매우 작은 오류정정능력의 RS 부호를 외부 부호로는 하는 연접부호를 제안하였다. 내부 격자 부호는 셀 내 프로그래밍 단계를 증가시킴으로써 여분 비트를 저장하기 위한 셀을 추가로 요구하지 않으면서 부호화 이득을 얻을 수 있는 장점이 있다. 또한 복호 복잡도가 부호 길이에 대해 선형적이므로, 긴 부호길이를 가지는 낸드 플래시 메모리 환경에 적합하다. 본 연구에서는 격자부호의 이러한 장점들을 이용하는 것과 함께, 내부 격자 부호에서 셀 간 결합, 수평전하의 확산의 주요 원인이 되는 오류 패턴을 최소화 하는 방식을 제시하였다. 격자 부호는 전체 격자를 격자 내부의 변조 점들간 유클리드 거리가 최대화 되는 방향으로 몇 개의 부분 격자로 분할(partition) 한다. 이때, 정보비트의 일부를 길쌈부호화 하여 부분 격자를 선택하는 용도로 사용하고, 남은 정보 비트들을 이용하여 선택된 부분 격자 내부의 변조 점을 선택하는 용도로 사용한다. 길쌈 부호는 일반적으로 Viterbi 복호기를 이용하여 복호 한다. 하지만, Viterbi복혹시 발생하는 복호 오류는 연집(burst)된 오류 특성을 가지기 때문에 RS 부호를 이용하여 잔류 오류를 수정하게 된다. 본 연구에서는 부분 격자 선택 정보와 내부 변조점 선택정보를 같은 체(field)에서 정의된 RS부호를 사용하여 오류를 정정함으로서 전체 복호기의 복잡도를 간략화 하였다. 또한, 부분 격자 선택정보에 대한 오류를 먼저 복호한 후 변조점 정보에 대한 오류를 정정하는 순차적 복호 방식을 고려하여 오류전파 (error-propagation)를 막고 정정해야 할 오류의 개수를 최소화 하였다. 제안된 오류정정 시스템의 성능을 분석함에 있어서, 낸드 플래시 메모리는 매우 낮은 페이지 오류율을 요구함으로 해당 페이지 오류율은 실험으로 측정하기 어려운 문제를 가지고 있다. 이러한 문제점을 본 연구에서는 내부 부호의 부호 오류율의 정확한 상계(upper bound)를 해석함으로서 해결하였다. 특히, 부분격자 선택 부분의 오류발생 행태는 변형된 마르코브 연쇄(Markov chain)로 모형화하였고, 변조점 선택 부분은 오류 전파의 제거로, 격자 심벌 간 독립성을 유지함으로, 이러한 특성을 활용하여 상계를 계산하였다. 제시된 오류 분석을 통하여 제안된 연접 부호가 기존의 BCH부호 또는 RS 부호만 사용하는 오류정정 시스템과 비교하여 약 50%와 66%이상의 여분 셀을 절약하면서도 동일한 페이지 오류율을 얻는 것을 확인하였다. 또한, 높은 부호율과 저 복잡도로, 두 부호보다 채널용량에 각각 1.2 dB, 1.8 dB 접근하는 것을 확인하였다.
