Error-Floor Lowering Data-Shortening Schemes and Analysis of Check-Node Merging Decoding for LDPC Codes

Abstract

This dissertation contains two contributions to the research topics on low-density parity-check(LDPC) codes and one contribution to signal processing techniques to Multi-Level Cell(MLC) NAND flash memory:

Lowering error floors of systematic LDPC codes using data-shortening

Analysis of check-node merging decoding

Channel modification of MLC NAND flash memory using density mirroring and EM algorithm

First, data-shortening methods for lowering error floors of systematic LDPC codes are proposed. Rather than attempting to analyze trapping (or stopping) sets of a given LDPC code rigorously, we search information bits associated with dominant trapping (or stopping) sets of systematic LDPC codes through simulation under various channels. Then, before encoding, proper information bits forming dominant trapping (or stopping) sets are selected and known values are assigned to them to weaken the effect of dominant trapping (or stopping) sets. To decode codewords, fixed known values are assigned to the selected information bits, which gives rise to the disconnection of some edges in dominant trapping (or stopping) sets. Through simulation, it is shown that the proposed schemes result in a remarkably better performance, especially at the error floor region, than the base LDPC codes under various channels with negligible loss of code rate. In the second part of this dissertation, we introduce and analyze a new decoding scheme of punctured LDPC codes with dual-diagonal parity structure by merging check nodes connected to the punctured parity nodes. This decoding algorithm is based on the fact that two check nodes can be merged if they are connected to the same punctured parity nodes. By applying this to a Tanner graph of a punctured LDPC code with the dual-diagonal parity structure, we we are able to derive a new Tanner graph without the use of punctured parity nodes. The check-node merging decoding is the sum-product decoding over this new Tanner graph. It has better FER performance under a small number of iterations and faster convergence speed than that of the conventional erasure decoding. Therefore, we compare the check-node merging and the conventional erasure decoding schemes of the punctured LDPC codes with dual-diagonal parity structure by using the recovery tree and analyze these decoding algorithms by using the density evolution over AWGN channels. Furthermore, the computational complexity per iterations of the two decoding algorithms are compared. Finally, we utilize two signal processing techniques for designing binary error correction codes for MLC NAND flash memory. MLC NAND flash memory saves the non-binary symbol at each cell and shows an asymmetric channel log-likelihood ratio (LLR) $l$-density which makes it difficult to design soft-decision binary error correction codes such as LDPC codes and Polar codes. Therefore, the density mirroring and EM algorithm can be applied for approximating the MLC NAND flash memory channel to the binary-input memoryless channel. The density mirroring processes channel LLRs to roughly satisfy all-zero codeword assumptions, and then EM algorithm is applied to l-density after density mirroring for approximating it to mixture of symmetric Gaussian densities. These two signal processing techniques make it possible to use conventional code design algorithms, such as density evolution and EXIT chart, for MLC NAND flash memory channel.|본 논문은 저밀도 패리티 체크(LDPC) 부호의 오류 마루 개선을 위한 절단 기법과 체트 노드 병합 복호 알고리즘의 분석에 관한 두 가지 LDPC 부호의 연구 결과와 멀티 레벨 낸드(MLC NAND) 플래시 메모리 채널의 신호 처리에 관한 연구 결과를 포함하며, 다음과 같이 요약된다.

LDPC 부호의 오류 마루 현상을 개선하기 위한 절단 기법 체크 노드 병합 복호 알고리즘의 분석 밀도 미러링과 EM 알고리즘을 적용한 MLC NAND 플래시 메모리 채널의 조절 기법

먼저 시스테메틱(systematic) LDPC 부호의 오류 마루 개선을 위한 절단 기법을 제안한다. 주어진 시스테메틱 LDPC 부호의 트래핑 세트를 정확히 분석하기 보다는, 여러 가지 채널 환경에서 주요 트래핑 세트에 연관된 정보 비트 위치를 모의 실험을 통해서 찾는다. 그리고 나서, 선택된 정보 비트 위치에 특정 비트 값을 할당하여 부호화를 수행한다. 복호시에는, 부호화 단계에서 선택된 정보 비트 위치에 특정 비트 값을 사용하였기 때문에, 사용된 특정 비트 값에 대응되는 로그 우도 값을 할당하여 복호를 수행한다. 이는 주요 트래핑 세트 내에 존재하는 에지를 제거하여 트래핑 세트의 영향을 줄임으로써 오류 마루 현상을 개선하는 효과를 낳는다. 제안된 절단 기법을 이용하면 약간의 부호율 손해를 보더라고, 오류 마루 현상을 개선하여 더 좋은 오류율 성능을 얻을 수 있다.

두 번째로, 이중 대각 패리티 구조를 가지는 천공된 LDPC 부호에 적용가능한 체트 노드 병합 복호 알고리즘을 소개하고 분석한다. 천공된 패리티 비트는 복호 알고리즘에 아무런 영향을 주지 않기 때문에, 인접한 체크 노드를 병합할 수 있다. 체크 노드 병합을 통해서 천공된 패리티 비트가 제거된 새로운 Tanner 그래프를 얻을 수 있고, 새롭게 얻어진 Tanner 그래프 상에서 합곱 알고리즘을 이용하여 복호를 수행할 수 있다. 이를 체크 노드 병합 복호 알고리즘이라 한다. 체크 노드 병합 복호 알고리즘은 천공된 패리티 비트를 제거하고 복호 알고리즘을 수행함으로써, 적은 수의 반복 횟수에서도 빠른 수렴 속도를 보이며, 동시에 낮은 계산 복잡도를 가진다. 본 논문에서는 체크 노드 병합 복호 알고리즘과 기존의 소거 복호 알고리즘의 수렴 속도를 회복 트리 구조를 이용하여 비교, 설명하고 가우시안 채널에서 밀도 진화 알고리즘을 사용하여 비교, 분석한다. 또한 두 복호 알고리즘의 계산 복잡도를 구하고 비교한다.

마지막으로, 멀티 레벨 플래시 메모리 채널에 밀도 미러링과 EM 알고리즘을 적용하는 채널을 조절하는 신호 처리 기법을 소개한다. 멀티 레벨 낸드 플래시 메모리는 한 셀에 $2$ 비트 이상의 정보를 저장하는 구조이고, 비트 위치별 채널 LLR의 밀도 함수 $l$-밀도가 비대칭 특성을 가지고 있다. 이런 특성은 이진 무기억 대칭 채널 조건에서 설계되어진 오류 정정 부호의 성능이 제대로 발휘되지 못하게 할 뿐만 아니라, 멀티 레벨 낸드 플래시 메모리용 연판정 복호를 수행하는 이진 오류 정정 부호의 설계도 어렵게 한다. 본 논문에서 밀도 미러링과 EM 알고리즘을 이용하여 멀티 레벨 낸드 플래시 메모리 채널의 특성을 고려한 오류 정정 부호 설계 방법을 소개한다. 밀도 미러링은 EM 알고리즘을 적용하기 전에 영 부호어를 전송한 경우로 가정할 수 있도록 하기 위해서 채널 LLR을 처리하는 과정이고, 이후 채널 $l$-밀도를 EM 알고리즘을 적용하여 $K$ 개의 성분으로 이루어진 대칭 가우시안 혼합 밀도로 근사화하는 방법을 소개한다.; This dissertation contains two contributions to the research topics on low-density parity-check(LDPC) codes and one contribution to signal processing techniques to Multi-Level Cell(MLC) NAND flash memory:

Lowering error floors of systematic LDPC codes using data-shortening

Analysis of check-node merging decoding

Channel modification of MLC NAND flash memory using density mirroring and EM algorithm

First, data-shortening methods for lowering error floors of systematic LDPC codes are proposed. Rather than attempting to analyze trapping (or stopping) sets of a given LDPC code rigorously, we search information bits associated with dominant trapping (or stopping) sets of systematic LDPC codes through simulation under various channels. Then, before encoding, proper information bits forming dominant trapping (or stopping) sets are selected and known values are assigned to them to weaken the effect of dominant trapping (or stopping) sets. To decode codewords, fixed known values are assigned to the selected information bits, which gives rise to the disconnection of some edges in dominant trapping (or stopping) sets. Through simulation, it is shown that the proposed schemes result in a remarkably better performance, especially at the error floor region, than the base LDPC codes under various channels with negligible loss of code rate. In the second part of this dissertation, we introduce and analyze a new decoding scheme of punctured LDPC codes with dual-diagonal parity structure by merging check nodes connected to the punctured parity nodes. This decoding algorithm is based on the fact that two check nodes can be merged if they are connected to the same punctured parity nodes. By applying this to a Tanner graph of a punctured LDPC code with the dual-diagonal parity structure, we we are able to derive a new Tanner graph without the use of punctured parity nodes. The check-node merging decoding is the sum-product decoding over this new Tanner graph. It has better FER performance under a small number of iterations and faster convergence speed than that of the conventional erasure decoding. Therefore, we compare the check-node merging and the conventional erasure decoding schemes of the punctured LDPC codes with dual-diagonal parity structure by using the recovery tree and analyze these decoding algorithms by using the density evolution over AWGN channels. Furthermore, the computational complexity per iterations of the two decoding algorithms are compared. Finally, we utilize two signal processing techniques for designing binary error correction codes for MLC NAND flash memory. MLC NAND flash memory saves the non-binary symbol at each cell and shows an asymmetric channel log-likelihood ratio (LLR) $l$-density which makes it difficult to design soft-decision binary error correction codes such as LDPC codes and Polar codes. Therefore, the density mirroring and EM algorithm can be applied for approximating the MLC NAND flash memory channel to the binary-input memoryless channel. The density mirroring processes channel LLRs to roughly satisfy all-zero codeword assumptions, and then EM algorithm is applied to l-density after density mirroring for approximating it to mixture of symmetric Gaussian densities. These two signal processing techniques make it possible to use conventional code design algorithms, such as density evolution and EXIT chart, for MLC NAND flash memory channel.