Bit-flipping (BF) algorithm is useful low-density parity-check (LDPC) code decoding algorithm for SSD such as NAND flash memory due to its fast decoding speed and low complexity for hardware implementation. However, there have been researches to improve the BF algorithm because of its poor error correcting capability. In this thesis, we propose the pattern-based BF algorithm (PBFA) that adaptively determines the flipping threshold by analyzing the local maximum patterns of the flipping functions.
The flipping thresholds are determined by creating the mapping from the local maximum patterns to the thresholds of the genie-aided BF algorithm, which adaptively chooses the threshold in order to minimize the error probability at each iteration. This proposed algorithm outperforms the existing BF algorithm and the other adaptive threshold choosing BF algorithm at the low maximum iteration. In addition, the better error correcting performance is achievable by applying the backtracking strategy to the investigated local maximum patterns causing the decoding failure.
비트 반전 알고리즘은 복호 처리 속도가 우수하고 하드웨어에서 구현하기에 낮은 복잡도를 가지고 있어서 낸드 플래시 메모리와 같은 SSD 분야에 적용시키기에 적합한 저밀도 패리티 검사 복호 알고리즘이다.
그러나 오류 정정 능력이 떨어진다는 단점을 가지고 있어서 이를 개선하기 위한 연구가 계속 진행되고 있다.
본 논문에서는 반전 함숫값의 국소 최댓값의 패턴을 분석하여 매번 반전 문턱값을 적응적으로 설정하는 패턴 기반 비트 반전 알고리즘을 제안하였다. 반전 문턱값의 설정 방법은 매번 오류율을 최소화 시키는 문턱값을 적응적으로 선택하는 genie-aided 비트 반전 알고리즘의 국소 최댓값의 패턴을 분석하여 국소 최댓값과 반전 문턱값 사이의 함수를 설정한다. 이 복호 알고리즘은 기존의 비트 반전 알고리즘, 그리고 문턱값을 적응적으로 선택하는 기법을 사용한 다른 복호 알고리즘과 비교해서 낮은 최대 반복 횟수에서 우수한 성능을 보이고 있다. 그리고 패턴 기반 알고리즘에서 복호가 실패하도록 만드는 국소 최댓값의 패턴을 조사하여 되추적법을 적용시켜서 더 좋은 오류 정정 능력을 얻을 수 있다.