Advanced coding techniques for next generation storage device = 차세대 저장매체를 위한 오류정정부호
서명 / 저자 Advanced coding techniques for next generation storage device = 차세대 저장매체를 위한 오류정정부호 / Ji Eun Oh.
저자명 Oh, Ji Eun ; 오지은
발행사항 [대전 : 한국과학기술원, 2015].
Online Access 원문보기 원문인쇄





학술문화관(문화관) 보존서고

DEE 15020

휴대폰 전송






In recent years, a great deal of research attention has been paid to reducing the unit cost of data storage to meet fast growing demand for storage. However, the rate of storage demand has grown faster than the decreasing unit cost of storage. In addition, types of user data have been widely diversified, ranging from massive multimedia data to tiny data packets exchanged between wearable devices. To cope with the unprecedented rate of storage demand and the variety of user data, future data storage devices, in addition to the traditional requirements such as low latency, long endurance, and high reliability, must also support low bit cost and/or fast data transactions. As one of the key enabling technologies for the development of future storage devices, novel error-control systems for next generation solid-state storage devices (SSDs) using NAND flash memories and high density magnetic tape storages are investigated in this study. In this dissertation, we first consider an error-control system for NAND flash memory in which Trellis Coded Modulation (TCM) and Reed-Solomon (RS) codes are concatenated as the inner and outer codes, respectively. For NAND flash memory, the performance is usually measured in terms of Word Error Rate (WER); the target WER ($10^{-16}$ in our work) is set extremely low. Such a low WER is mainly determined by the occurrence of long burst errors from the inner TCM, which can be coped by using a powerful outer code with a growing number of redundant bits and/or a long interleaver across many TCM blocks. The growing number of redundant bits in turn results in not only poorer storage density but also higher decoder complexity. Meanwhile, the interleaving across many TCM blocks requires intolerably long latency and buffer size. In this paper, we propose a novel error-control system in which two RS codes individually protect the coded bits and uncoded bits in a TCM block. On the decoder side, multi-stage decoding is carried out in such a way that the decoder for the coded bits first corrects burst errors in the output from an ML decoder for the coded bits in a TCM block. Assuming there is no error in the results of the first stage, the decoder for the other RS code finds errors in the uncoded bits. The main idea behind the proposed system is to confine the burst error only to the coded bits, which prevents error propagation to the uncoded bits. We claim that the proposed system, without resorting to a long interleaver, achieves the target WER with a much smaller number of redundant bits than is possible when using systems with BCH and RS codes. Our claims are confirmed by analyzing the error probabilities of the two-stage decoding and comparing the analytic results with simulations. In particular, the performances of the proposed system is compared with those of systems with BCH, RS, and low-density parity-check codes; the comparison results show that the proposed system, at much reduced complexity, provides performances comparable to that of a system with Low Density Parity Check codes (LDPC codes). Second, a new concatenated coding scheme of RS coding with outer non-binary LDPC codes is investigated for magnetic tape channels. In magnetic tape storage systems, the data is recorded along multiple tracks. This structure induces a tape specific error type of long erasure dropouts, in addition to random errors with short fades. Two-dimensional block-wise concatenated codes are proposed to handle different types of error individually. In detail, the inner RS code corrects errors from random noise with short fades and converts channel into a mixture of clean, erased and noisy symbols. Then, the decoding algorithm of the outer nonbinary LDPC codes can be simplified by effectively removing the edges connected to the clean symbols. This simplified decoder allows faster convergence, in addition to several inherited advantages of nonbinary LDPC codes. Simulation results show that the proposed scheme outperforms conventional RS-RS concatenation in various channel conditions. Furthermore, the error performance of the proposed scheme is also evaluated at low error rates using a mixed simulation-analytic method. It is shown that the proposed scheme exhibits highly favorable performance vs. complexity tradeoffs for high-density tape storage systems.

인터넷의 발전과 휴대용 통신기기의 발전에 힘입어 전세계적으로 생산, 소비되는 디지털 데이터의 양은 급속도로 증가하고 있는 추세이다. 이에 따라 과거 그 어느 때보다 고성능, 고집적도의 저장매체에 대한 연구가 요구되는 시점이다. 낸드 플래시 메모리 (NAND Flash Memory) 기반의 고체저장장치 (Solid State Drive)는 저전력 고속동작 및 물리적 충격에 강인한 장점을 가지고 있어 디지털 카메라, MP3 플레이어, 태블릿 피시 (Tablet PC)등과 같은 다양한 디지털 장치에 널리 사용되고 있다. 반면, 자기 테이프 (Magnetic Tape) 저장장치는 저장된 데이터의 접근횟수는 적으나 많은 양의 데이터를 오랜 시간 안전하게 저장하는 데에 가장 적합하다. 이러한 차세대 저장매체의 경쟁력을 높이기 위해 매체의 집적도를 증가시켜 단위면적당 더 많은 데이터를 저장하기 위한 연구가 계속되고 있다. 저장밀도의 증가는 데이터의 신뢰성을 악화시키고 수명을 단축시키므로 이를 효과적으로 처리하기 위한 오류정정부호 기술이 매체의 집적도 증가와 함께 뒷받침되어야 한다. 현재의 상용화된 저장매체에서 사용하는 오류정정부호는 복호과정에서 경판정 (hard-decision)결과값을 이용한다. 현재 사용되는 저장매체에서는 원비트오류 (Raw Bit Error Rate) 값이 낮아서 높은 부호율을 가지는 오류정정 부호를 사용하는 것만으로 충분하다. 한편, 이러한 환경에서는 경판정 값과 연판정(soft-decision)값을 가지는 경우를 비교하면 채널용량 (channel capacity)의 차이가 미미하여 연판정 값을 사용하는 오류정정 부호를 사용함으로써 얻는 이득이 거의 없어, BCH부호와 같은 경판정 결과를 이용하여 동작하는 오류정정부호를 사용하는 것이 실용적인 측면에서 적절하다. 하지만 미래의 저장매체는 높은 원비트 오류율을 가질 것으로 예상되며 경판정 값과 연판정 값의 채널용량이 큰 차이를 보이게 됨으로 연판정 기반의 오류정정 부호를 사용할 수 밖에 없을 것으로 예상된다. 본 고에서는 차세대 저장매체에 발생하는 오류의 원인과 특성을 알아보고 이를 효과적으로 정정하기 위한 오류정정부호를 제안하였다. 본 연구에서는 먼저, 대역폭이 제한된 환경에서 높은 부호화 이득을 가지는 격자 부호(Trellis Coded Modulation)를 내부 부호로 하고, 매우 작은 오류정정능력의 RS 부호를 외부 부호로는 하는 연접부호를 제안하였다. 내부 격자 부호는 셀 내 프로그래밍 단계를 증가시킴으로써 여분 비트를 저장하기 위한 셀을 추가로 요구하지 않으면서 부호화 이득을 얻을 수 있는 장점이 있다. 또한 복호 복잡도가 부호 길이에 대해 선형적이므로, 긴 부호길이를 가지는 낸드 플래시 메모리 환경에 적합하다. 격자 부호는 전체 격자를 격자 내부의 변조 점들간 유클리드 거리가 최대화 되는 방향으로 몇 개의 부분 격자로 분할(partition) 한다. 이때, 정보비트의 일부를 길쌈부호화 하여 부분 격자를 선택하는 용도로 사용하고, 남은 정보 비트들을 이용하여 선택된 부분 격자 내부의 변조 점을 선택하는 용도로 사용한다. 길쌈 부호는 일반적으로 Viterbi 복호기를 이용하여 복호 한다. 하지만, Viterbi복호시 발생하는 복호 오류는 연집(burst)된 오류 특성을 가지기 때문에 RS 부호를 이용하여 잔류 오류를 수정하게 된다. 본 연구에서는 부분 격자 선택정보에 대한 오류를 먼저 복호한 후 변조점 정보에 대한 오류를 정정하는 순차적 복호 방식을 고려하여 오류전파 (error-propagation)를 막고 정정해야 할 오류의 개수를 최소화 하였다. 또한, 부분 격자 선택 정보와 내부 변조점 선택정보를 같은 체(field)에서 정의된 RS부호를 사용하여 오류를 정정함으로서 전체 복호기의 복잡도를 간략화 하였다. 제안된 오류정정 시스템의 성능을 분석함에 있어서, 낸드 플래시 메모리는 매우 낮은 워드 오류율(Word Error Rate)을 요구함으로 해당 워드 오류율은 실험으로 측정하기 어려운 문제를 가지고 있다. 이러한 문제점을 본 연구에서는 내부 부호의 부호 오류율의 정확한 상계(upper bound)를 해석함으로서 해결하였다. 특히, 부분격자 선택 부분의 오류발생 행태는 변형된 마르코브 연쇄(Markov chain)로 모형화하였고, 변조점 선택 부분은 오류 전파의 제거로, 격자 심벌 간 독립성을 유지함으로, 이러한 특성을 활용하여 상계를 계산하였다. 제시된 오류 분석을 통하여 제안된 연접 부호가 기존의 BCH부호 또는 RS 부호만 사용하는 오류정정 시스템과 비교하여 약 50$\%$와 66$\%$이상의 여분 셀을 절약하면서도 동일한 워드 오류율을 얻는 것을 확인하였다. 또한, 높은 부호율과 저 복잡도로, 두 부호보다 채널용량에 각각 1.2 dB, 1.8 dB 접근하는 것을 확인하였다. 자기 테이프 저장매체는 여러 개의 리드헤드(read head)가 여러 트랙으로부터 동시에 기록된 정보를 읽어온다. 이때, 헤드와 미디어 사이에 공간이 벌어지거나 읽어오는 시점을 놓침으로써 매우 긴 길이에 걸쳐 기록된 정보와 전혀 다른 값이 테이프 드라이브로 입력되는 현상이 발생한다. 여기에 더하여, 데이터에는 미디어에 기록된 신호가 이퀄라이저(Equalizer)를 거치면서 발생하는 연집오류와 그밖의 랜덤한 오류들이 더해진다. 이러한 자기테이프 신호의 오류들은 두 계층 (Layer) 오류정정부호와 여러 트랙에 걸친 인터리버 (interleaver)를 통해 복원된다. 본 연구에서는 연집오류에 강인한 RS 내부부호와 비이진 저밀도 패리티 체크 부호 (Low Density Parity Check Codes, LDPC codes)를 외부부호로 연접시킨 두 계층 오류정정부호를 제안하였고, 복호시 내부부호와 외부부호간의 반복복호를 수행하도록 하였다. 비이진 LDPC 부호는 연집 오류와 소실채널(Erasure Channel)에서 높은 성능을 보임에도 불구하고 그 복잡도가 지수적으로 증가하는 단점을 가지고 있다. 본 고에서는 내부 RS부호와의 연접을 통하여 비이진 LDPC 부호의 입력을 오류가 없는 심볼과 소실 심볼, 그리고 오류심볼이 섞인 입력으로 전환 후 이를 효과적으로 이용하여 복호기의 연산을 간략화하는 방식을 제안하였다. 저복잡도 log-SPA 복호기에서는 정확한 값의 심볼에 연결된 에지(edge)를 가상으로 제거시킴으로서 지수적인 복잡도의 연산을 간략화 하는 것이 가능하다. 제안하는 부호의 성능은 실제 복호 알고리즘의 상계이지만 해석이 가능학 알고리즘을 제시하여 매우 낮은 오류율을 획득함을 보였다. 먼저, 첫번째 내외부 복호를 실험으로 진행 후, 두번째 복호시 내부 복호기의 입력중 복호 실패한 심벌에 상응하는 바이트(Byte)를 채널로부터의 결정값으로 대체하였다. 그 후, 실패한 부호의 심벌들의 정보를 소실(erased)시키고, 비이진 LDPC 복호기는 erasure 복호를 실행한다. 실험으로부터 제안하는 부호가 기존의 부호에 대해 백색잡음채널과 자기테이프채널에 대하여 각각 1.6dB와 1.1dB의 부호화 이득을 얻는 것을 확인하였고 $10^{-19}$이라는 낮은 오류율을 얻을 수 있음을 확인하였다.


청구기호 {DEE 15020
형태사항 vii, 70 p. : 삽도 ; 30 cm
언어 영어
일반주기 저자명의 한글표기 : 오지은
지도교수의 영문표기 : Jeong Seok Ha
지도교수의 한글표기 : 하정석
수록잡지명 : "IEEE Transactions". IEEE Transactions on communications, v. 61, no. 5, 1674-1683(2013)
Including Appendix
학위논문 학위논문(박사) - 한국과학기술원 : 전기및전자공학과,
서지주기 References : p.
주제 Channel codes
NAND flash memories
Magnetic tape
Trellis-coded modulation
LDPC codes
자기 테이프
저밀도 패리티 체크 부호
QR CODE qr code