단계별 에러 관리를 위한 Rate-Compatible Low Density Parity Check

Ⅰ. 서 론

순방향 오류 제어(Forward Error Correction, FEC)는 신뢰할 수 없는 통신 채널을 통한 데이터 오류를 제어하기 위해서 송신자가 보내는 메시지에 더해서 메시지를 특정 인코딩 방법으로 인코딩하여 부가적인 데이터인 패리티(Parity)를 첨부하여 수신자에게 보내는 방식이다. 수신자는 수신받은 데이터에 오류가 있는지를 패리티의 검사로 확인할 수 있다. 이러한 FEC는 최근 통신이론, 정보이론뿐만 아니라 메모리 시스템 등 다양한 컴퓨터 시스템에 적용되고 있다[1]-[5]. 특히, 낸드 플래시 메모리와 같은 메모리 소자는 최근의 급격한 집적도의 증가와 셀 당 저장하는 비트 수의 증가로 인해서 셀 간 간섭이 심해서 에러 발생률이 현저히 증가하여 정보이론에 주로 사용되던 인코딩 기법이 적용 확대되고 있다.

또한, 낸드 플래시 메모리는 메모리 셀의 특성상 Program/Erase Cycle(P/E cycle)이 증가할수록, 즉, 사용 시간이 길어질수록 셀의 물리적 특성이 나빠져서 에러 발생률이 급격히 높아지게 되며 이는 낸드 플래시 메모리 기반의 컴퓨터 시스템의 수명에 한계를 주는 주요 요인이 된다[6][7]. 최근 3D 적층 기술의 발전으로 인해서 기존의 2D에 비해서 셀 간 간격의 확보가 상대적으로 쉬워 기존의 2D에 비해서 P/E cycle이 약간 증가하는 점이 있긴 하지만 여전히 P/E cycle이 1000 정도에 머물러 있어 낸드 플래시 메모리 기반의 컴퓨터 시스템의 치명적인 단점으로 작용하고 있다. 이러한 FEC 기반의 ECC를 생성하는 기법 중에서 LDPC(Low Density Parity Check) 기법이 최근에 많이 적용되고 있다[8]-[11]. LDPC[1]-[3]는 부호 패리티 검사 행렬(Parity Check Matrix, PCHK) 기반의 매트릭스 기반의 인코딩 기법이다. LDPC는 소스 데이터로부터 PCHK 또는 PCHK 대응 Generator Matrix에 대한 행렬연산을 통해서 패리티 데이터를 포함한 코드 워드(Codeword)를 생성한다. 데이터 부호율에 따라서 패리티 데이터의 양을 결정할 수 있다.

낸드 플래시 메모리의 쓰기 단위는 페이지(Page)라는 고유 단위를 사용하고 있는데, 페이지 쓰기가 발생할 때마다 해당 쓰기 데이터에 대해서 LDPC 인코딩을 적용하여 부가적인 ECC인 패리티를 생성하고, 패리티는 데이터와 별도의 공간에 저장된다. 일반적으로 LDPC는 플래시 메모리 컨트롤러에 하드웨어로 설계 및 구현이 되므로 LDPC의 부호율은 고정되게 된다. 그러나 이러한 고정된 LDPC의 부호율은 P/E cycle이 증가함에 따라 에러 발생률이 증가하는 낸드 플래시 메모리 특징에 적합하지 않으므로, P/E cycle 증가에 비례하여 단계적으로 패리티를 증가시키는 단계별 비율 호환적 LDPC 기법(Stepwise Rate-Compatible LDPC) 적용이 필요하다.

본 논문에서는 P/E cycle을 몇 단계로 구분하여, 몇 단계의 스텝을 가지고 부호율을 변화시키는 Rate-Compatible LDPC 인코딩 기법을 설계하였다. 본 논문에서 설계한 기법은 Quasi-Cyclic(QC) LDPC[12] 기반으로 적용하였으며, 단계별로 계단적 변화가 가능한 LDPC 기법이다. 단계별로 추가되는 패리티가 기존의 패리티에 덧붙여져서 추가되는 방식인 Rate-Compatible 형태를 가지도록 설계되었다. 본 기법은 기존의 Rate-Compatible LDPC 방식과 비교해 베이스 PCHK에서 추가되는 부호율은 단계가 넓도록 구성되며, 확장되는 PCHK에 대한 편향을 줄였다. 이러한 방식은 P/E cycle에 따른 에러율 증가 및 페이지 단위의 입출력 방식을 가지는 낸드 플래시 메모리에 적합하다.

Ⅱ. 배경 지식

Ⅲ. Rate Compatible QC LDPC 설계

3.1 QC Matrix

앞서 설명한 바와 같이 LDPC의 PCHK는 소량의 1의 구성요소 값을 가지는 매트릭스이다. PCHK 기반으로 LDPC 인코딩 및 디코딩을 하기 위해서 Tanner Graph를 적용하는데, 이때 1의 구성요소가 특정 Row 또는 Column에 몰려있을 경우 Tanner Graph의 특성이 나빠질 수 있다. 이에 대해서 효율적인 1의 분포가 가능하도록 고안된 방법이 QC LDPC 방법이다. 그림 1과 같이 QC PCHK는 특정 단위행렬을 기본으로, 이후 추가된 행렬은 단위행렬의 열을 서로 바꾸어 확장하여 PCHK를 구성한다.

Fig. 1.

Example of PCHK for Quasi-cyclic LDPC

3.2 단계적인 Rate-Compatible QC PCHK 구조

QC 패턴을 적용하여 구성한 기본 PCHK의 구성도가 그림 2와 같이 나타나 있다. 그림의 PCHK는 M×(M+K) 매트릭스 구조이며, Message의 크기가 K 비트이며, check bit의 크기가 M 비트인 코드 워드를 생성할 수 있는 PCHK이다. 즉 Message와 PCHK의 행렬 곱 연산을 통해서 코드 워드를 생성해낸다. PCHK의 작은 단위는 QC 패턴의 확장으로 되어 있다. 이러한 PCHK는 A와 B 부분으로 나누어 구성되며, A는 M×M non-singular QC Matrix로 구성되며, B는 M×K QC Matrix이다. LDPC 인코더는 이렇게 구성한 PCHK를 기반으로 Generator Matrix를 생성해낼 수 있으며, Generator Matrix와 message bits의 Matrix Multiplication 연산을 통해서 메시지와 패리티로 구성된 (M+K)의 크기를 가지는 코드 워드를 생성해낸다.

Fig. 2.

Basic PCHK structure

Rate-Compatible LDPC를 구성하기 위해서, 기본 베이스 PCHK를 생성할 때 주의할 사항은 다음과 같다. 첫째, LDPC 인코딩을 통해서 코드 워드가 생성될 때 메시지 비트와 패리티 비트가 완벽히 분리되어야 한다. 둘째, Rate-Compatible 특징을 가지기 위해서는 A 매트릭스가 non-singular 특징을 가지도록 구성해야 한다는 것이다.

이러한 특징을 가지도록 기본 베이스 PCHK를 구성한 후, 단계적인 Rate-Compatible이 가능하도록 PCHK를 확장하는 방법이 그림 3에 나타나 있다. 그림 3은 기본 베이스 PCHK로부터 두 단계 Rate-Compatible PCHK를 확장하는 그림을 도식화한 것이다.

Fig. 3.

PCHK extension method for stepwise rate-compatible LDPC

그림 3에서 e와 e’는 각각 첫 번째 확장과 두 번째 확장을 나타낸다. 그림에서 나타난 바와 같이 기본 베이스 PCHK로부터 기존의 코드 워드와 분리된 n_e개의 패리티 데이터를 추가로 생성하기 위한 Rate-Compatible한 PCHKe를 확장하기 위해서는 기존의 [AB]로 구성된 PCHK에 O_e, D_e, I_e, E_e를 그림 3과 같은 위치에 추가하여 주면 된다. 여기서 O는 영행렬, I는 단위행렬을 각각 나타낸다. D_e와 E_e는 기본적으로 A와 B에 적용된 QC Matrix의 구조를 가지도록 구성되어야 하며, 추가로 D_e의 경우는 A와 결합하여 non-singular Matrix가 되도록 구성해주어야 한다.

이렇게 구성된 PCHK_e에 대해서, 마찬가지로 Rate-Compatible한 특성을 가지도록 PCHE_e'로 확장하는 방식은 그림 3에서 나타난 바와 같이 PCHKe에 O_e', I_e', D_e', E_e'를 적절한 위치에 추가하는 것이다. 이때, 역시 D_e'와 E_e'의 경우는 QC Matrix의 확장으로 구성하며, D_e'는 A와 D_e와 결합하여 non-singular Matrix가 되도록 구성해주어야 한다.

그림 4는 단계적인 Rate-Compatible PCHK의 확장들을 이용하여 LDPC 인코딩을 수행하여 생성한 코드 워드에 관한 결과를 도식화한 것이다. 그림에서 나타난 바와 같이 베이스 PCHK 및 이를 기반으로 한 PCHK 확장 버전을 이용한 Rate-Compatible LDPC를 이용할 경우, 원본 메시지 데이터와 패리티 데이터를 분리해낼 수 있으며, 인코딩을 확장하더라도 패리티가 섞이지 않도록 생성해낼 수 있다.

Fig. 4.

Codeword configuration according to expansion of parity data encoded by stepwise rate-compatible LDPC

Ⅳ. 시뮬레이션 성능평가

본 논문에서 설계한 단계별 비율 호환적 LDPC는 LDPC 시뮬레이터[15]를 이용하여 성능평가를 하였다. 사용한 소프트웨어 시뮬레이터 공개 소스로 공개된 LDPC 인코딩 및 디코딩을 지원하는 시뮬레이터로써 원하는 형태의 PCHK를 정의할 수 있으며, PCHK로부터 생성된 Generator Matrix를 이용하여 메시지 데이터를 인코딩 및 디코딩할 수 있다.

먼저, 본 논문에서 설계한 단계별 비율 호환적 QC LDPC의 확장성 및 에러 보정 기능을 테스트하기 위해서, 4×20 PCHK를 기본으로 하여 두 단계로 확장한 PCHK, 즉 8×24 PCHK_e, 12×28 PCHK_e’를 생성하여 인코딩 및 디코딩에 대한 에러율 실험을 진행하였다. 4×20 PCHK는 16bits의 message와 4bits의 parity로 총 코드 워드의 길이는 20bits를 생성하는 PCHK이다. 마찬가지로 8×24와 12×28는 16bits의 message에 parity가 각각 8bits, 12bits로 늘어난 코드 워드를 생성하도록 확장된 PCHK이다. 만약 4KB의 message 크기를 가지는 낸드 플래시 메모리 page의 경우, 4KB 데이터를 16bits씩 나누어서 LDPC 인코딩을 적용하여 parity를 별도로 분리해낼 수 있다. 이와 같은 방식으로 본 논문에서 제안한 방식으로 두 단계 Rate-Compatible QC LDPC를 위한 PCHK를 생성하였다.

Fig. 5.

PCHK case 1 configured for two stepwise rate-compatible QC LDPC

Fig. 6.

PCHK case 2 configured for two stepwise rate-compatible QC LDPC

그림 7과 그림 8은 생성된 PCHK의 두 상자에 대해서 각각 도식화한 것이다. 이렇게 생성한 PCHK를 기반으로 인코딩 및 디코딩 실험을 진행하였다. 즉, 두 단계 단계별 비율 호환적 QC LDPC를 적용한 두 개의 테스트케이스에 대해서, 총 메시지 길이 4096 Bytes에 대한 인코딩 및 디코딩을 시행했으며, 그 실험 결과를 그림 8과 그림 9에 각각 도식화하였다. 그림 5에서 x축은 메시지 데이터의 각 비트가 에러가 날 확률인 RBER(Raw Bit Error Rate)를 나타내며, y축은 LDPC 디코딩으로 메시지가 에러 복원되지 않을 확률인 UBER(Uncorrectable Bit Error Rate)를 로그 스케일로 나타낸 값이다. 즉, 그래프의 x축은 오른쪽으로 갈수록 인코딩할 메시지에 에러가 많이 발생하는 것을 뜻하는 것이며, y축은 값이 작을수록 발생한 에러를 복원할 확률이 높다는 것이다.

Fig. 7.

Simulation results for uncorrectable frame error rate for two stepwise rate-compatible QC LDPC case 1

Fig. 8.

Simulation results for uncorrectable frame error rate for two stepwise rate-compatible QC LDPC case 2

Fig. 9.

Experimental results of error compensation rate of step-compatible LDPC and conventional LDPC

그림 5의 두 경우에서 보는 바와 같이 PCHK를 확장할수록 UFER이 낮으므로 에러 보정 확률이 높아짐을 확인할 수 있다. 즉, 단계별 비율 호환적 QC LDPC의 설계방식에 의해서 생성된 PCHK에 대한 에러정정이 어느 정도 잘 이루어진다고 볼 수 있다. 이와 동시에 Rate-Compatible 한 특징을 가지므로 단계적으로 생성되는 추가 패리티를 적절히 잘 분리해낼 수 있다.

두 번째로, 단계별 비율 호환적 QC LDPC의 에러 보정률과 기존의 방식을 적용한 LDPC의 인코딩 디코딩 시 에러 보정률을 비교해보았다. 이 실험에서는 단계별 비율 호환적 QC LDPC의 경우 메시지의 에러 발생률이 특정 단계를 넘어설 때마다 단계별로 확장된 PCHK가 적용된다고 가정하였다. 메시지 에러를 의미하는 RBER이 증가한다는 것을 낸드 플래시 메모리의 특성에 비추어보면, 낸드 플래시 메모리에서 P/E cycle이 증가하는 것을 의미한다. 즉, 낸드 플래시 메모리의 P/E cycle이 증가할수록 플래시 메모리의 특성이 나빠져서 셀당 에러가 날 확률인 RBER이 증가하게 된다. 본 실험에서 특정한 특정 단계는 전체 보장 P/E cycle을 100%로 잡았을 경우, P/E cycle 대비 40%, 80%에 도달했을 때 각각 확장된 PCHK가 적용되는 것으로 하였다.

그림 6은 단계별 Rate-Compatible LDPC를 적용한 두 가지 경우와 4×20 PCHK, 8×24 PCHK, 12×28 PCHK를 가지는 기존 LDPC와 에러 보정률을 비교하여 도식화한 것이다. 성능 비교 대상으로는 비율 호환적이지 않도록 생성한 4×20 PCHK, 8×24 PCHK, 12×28 PCHK에 대해서 각각 인코딩 및 디코딩을 적용한 에러 보정률과 성능 비교를 해보았다.

가장 에러 보정률이 낮은 것은 4x20 부호율을 가지는 기존 LDPC이며 가장 높은 에러 보정률은 12x28 부호율을 가진 기존 LDPC이다. 그림 6에서 알 수 있는 바와 같이, 같은 부호율에 대해서 기존 LDPC와 Rate-Compatible QC LDPC의 에러 보정률을 비교해보았을 때는 기존 LDPC가 조금 더 높은 에러 보정률을 보이는 것을 확인할 수 있다. 이는 Rate-Compatible QC LDPC를 적용하면 기본 베이스 PCHK에 비율 호환이 가능하도록 확장하기 위해서 추가되는 행과 열의 값에 0 또는 1이 치우쳐져서 추가될 확률이 높으므로 1의 값이 고르게 분포되지 않는다. 이러한 특성은 LDPC 디코딩 성능을 떨어뜨리는 요인으로 작용하기 때문에 단계별 Rate-Compatible QC LDPC 기법이 기존 LDPC보다는 에러 보정률이 낮을 수 있다.

그러나 본 논문에서 설계한 Rate-Compatible QC LDPC의 경우는 메시지에 대한 에러 발생률이 높아짐에 따라서 낮은 부호율에 대한 인코딩을 호환적으로 높은 부호율로 확장할 수 있는 장점이 있으므로 에러 발생이 높아짐에 따라서 높은 부호율을 바로 적용함으로써 에러 보정률을 높일 수 있다.

또한, 기존의 낮은 부호율로 생성한 패리티 데이터를 높은 부호율에 대해서도 그대로 활용할 수 있으므로 패리티에 대한 재사용률을 높일 수 있다.

이러한 방식은 낸드 플래시 메모리와 같은 메모리 시스템의 읽기/쓰기 방식에 효율적으로 활용될 수 있다. 그림 6에서도 알 수 있듯이, 단계별 비율 호환적 QC LDPC의 경우, 메시지의 에러 발생률이 높아짐에 따라서 호환적으로 부호율을 높여서 단계적으로 에러 보정률을 높여나감으로써 낮은 부호율의 기존 LDPC 기법보다 높은 에러 보정률을 보일 수 있다.

Ⅴ. 결론 및 향후 과제

LDPC는 최근 주목받고 있는 FEC를 통한 에러 보정 방법으로써 통신 채널뿐만 아니라 낸드 플래시 메모리 같은 메모리 시스템에서 널리 활용되고 있다. 특히 낸드 플래시 메모리와 같은 연산방법이 페이지와 같이 특정 크기 단위로 정해져 있는 시스템에서 P/E cycle의 증가에 따른 에러 발생률이 증가하는 경우, 이에 비례하여 에러 보정률을 높일 수 있는 Rate-Compatible 한 에러 정정기법이 필요하다.

본 논문에서는 에러 발생률이 단계적으로 증가하는 메시지에 대해서, 에러 발생 단계를 몇 단계로 구분하여 몇 단계의 스텝을 가지고 부호율을 변화시켜서 확장할 수 있는 단계별 비율 호환적 LDPC 인코딩 기법을 설계하였다.

본 논문에서 설계한 기법은 QC LDPC 기반으로 적용하였으며, 단계별로 계단적 변화가 가능한 LDPC 기법이다. 본 논문에서 설계한 LDPC 기법을 활용할 경우, 단계적으로 에러 발생률이 증가하는 시스템에서 단계별로 부호율 확장 가능한 LDPC의 인코딩 및 디코딩 기법을 통하여 단계에 맞는 적절한 부호율을 가지는 에러 보정 기법을 호환적으로 적용할 수 있다. 낸드 플래시 메모리와 같이 사용 시간이 증가함에 따라서 점차 에러 발생확률이 높아지는 메모리 시스템에 적용하면 시간 증대에 따른 에러 발생률 증가를 낮출 수 있어 수명을 증대시킬 수 있을 것이다. 그러나 부호율을 낮추어서 패리티 데이터를 증가시키면 증가한 패리티 데이터를 저장할 공간이 별도로 필요하게 되므로, 부호율 단계를 높일 때마다 저장공간의 효율성은 감소하게 된다. 저장공간과 에러 보정률 및 사용 시간 증대에 관한 상호 연관성을 분석할 필요가 있다.

또한, 인코딩 및 디코딩 시간의 증가로 인해서 데이터 처리 성능이 떨어질 수 있다. 이에 대한 보완은 패리티 데이터를 DRAM 메모리에 캐싱함으로써 보완할 수 있다. 이에 관한 연구는 추후 과제로 진행할 예정이다.

Acknowledgments

이 연구는 한국외국어대학교 교내학술연구비의 지원에 의하여 이루어진 것임.

This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIP) (NRF-2019R1F1A1057503).

References

• David J. C. MacKay, "Information theory, Inference and Learning Algorithms", Cambridge University Press, ISBN 0-521-64298-1, 2003.
• Todd K. Moon, "Error Correction Coding, Mathematical Methods and Algorithms", Wiley, ISBN 0-471-64800-0, 2005.
• Robert G. Gallager, "Low Density Parity Check Codes", Monograph, M.I.T. Press. 1963. [https://doi.org/10.7551/mitpress/4347.001.0001]
• J. Ha, J. Kim, and S. McLaughlin, "Rate-compatible puncturing of lowdensity parity-check codes", IEEE Transactions on Information Theory, Vol. 50, No. 11, pp. 2824-2836, Nov. 2004. [https://doi.org/10.1109/TIT.2004.836667]
• J. Thorpe, "Low-density parity-check (LDPC) codes constructed from protographs", Jet Propulsion Lab., California Institute of Technology, Pasadena, CA, USA, Technical Report, pp. 42-154, Aug. 2003.
• N. Mielke and Todd Marquart, et al., "Bit error rate in NAND Flash memories", 2008 IEEE International Reliability Physics Symposium, Phoenix, AZ, USA, pp. 9-19, Apr. 2008. [https://doi.org/10.1109/RELPHY.2008.4558857]
• Yu Cai and Onur Mutlu, et al., "Program interference in MLC NAND flash memory: Characterization, modeling, and mitigation", IEEE 31st International Conference on Computer Design (ICCD), Asheville, NC, USA, pp. 123-130, Oct. 2013. [https://doi.org/10.1109/ICCD.2013.6657034]
• Hongbin Sun and Wenzhe Zhao, et al, "Exploiting intracell bit-error characteristics to improve min-sum LDPC decoding for MLC NAND flash-based storage in mobile device", IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 24, No. 8, pp. 2654-2664, Aug. 2016. [https://doi.org/10.1109/TVLSI.2016.2535224]
• K. Haymaker and C. A. Kelley, "Structured bit-interleaved LDPC codes for MLC flash memory", IEEE Journal on Selected Areas in Communications, Vol. 32, No. 5, pp. 870-879, May 2014. [https://doi.org/10.1109/JSAC.2014.140507]
• Shunzhuo Wang and Fei Wu, et al., "Lifetime adaptive ECC in NAND flash page management", Design, Automation & Test in Europe Conference & Exhibition (DATE), Lausanne, Switzerland, pp. 1253-1256, Mar. 2017.
• Pingping Chen, et al. "Rate-Adaptive Protograph LDPC Codes for Multi-Level-Cell NAND Flash Memory", IEEE Communications Letters, Vol. 22, No. 6, pp. 1112-1115, Jun. 2018. [https://doi.org/10.1109/LCOMM.2018.2814985]
• Yuan-hua Liu, "Rate-compatible QC-LDPC codes based on PEXIT", Electronics Letters, Vol. 54, No. 19, pp. 1120-1122, Sep. 2018. [https://doi.org/10.1049/el.2018.0915]
• Thuy Van Nguyen, Aria Nosratinia, and Dariush Divsalar, "The Design of Rate-Compatible Protograph LDPC Codes", IEEE Transactions on Communications, Vol. 60, No. 10, pp. 2841-2850, Oct. 2012. [https://doi.org/10.1109/TCOMM.2012.081012.110010]
• Y. Zhang, K. Peng, Z. Chen, and J. Song, "Construction of rate-compatible raptor-like quasi-cyclic LDPC code with edge classification for IDMA based random access", IEEE Access, Vol. 7, pp. 30818-30830, Mar. 2019. [https://doi.org/10.1109/ACCESS.2019.2902884]
• Radford M. Neal, "Software for Low Density Parity Check codes", https://github.com/radfordneal/LDPC-codes, , Feb. 11, 2012.