KR20190138143A

KR20190138143A - 패리티 체크 행렬 생성 장치, 그것의 동작 방법 및 그것에 의해 생성된 패리티 체크 행렬을 사용하는 에러 정정 회로

Info

Publication number: KR20190138143A
Application number: KR1020180064319A
Authority: KR
Inventors: 김대성; 채철수
Original assignee: 에스케이하이닉스 주식회사
Priority date: 2018-06-04
Filing date: 2018-06-04
Publication date: 2019-12-12
Also published as: US10693498B2; CN110557125A; CN110557125B; US20190372592A1

Abstract

비이진 순환 순열 행렬을 포함하는 LDPC(Low Density Parity Check) 코드 패리티 체크 행렬의 생성 장치는 상기 비이진 순환 순열 행렬의 상기 패리티 체크 행렬 내에서 위치 정보인 제1 가중치를 저장하는 제1 메모리; 상기 비이진 순환 순열 행렬의 행렬 요소들의 순환 강도인 제2 가중치를 저장하는 제2 메모리; 상기 비이진 순환 순열 행렬의 행렬 요소들 중 비이진 행렬 요소의 크기를 결정하는 제3가중치를 저장하는 제3 메모리; 및 상기 비이진 순환 순열 행렬에 대응하는 크기를 가지는 이진 순환 순열 행렬의 행렬 요소들 중 1의 행렬 요소들에 비이진 값을 적용하고 상기 비이진 값에 상기 제1 내지 제3 가중치들 중 어느 하나 이상을 반영하여, 상기 비이진 순환 순열 행렬을 생성하는 행렬 생성 장치를 포함한다.

Description

패리티 체크 행렬 생성 장치, 그것의 동작 방법 및 그것에 의해 생성된 패리티 체크 행렬을 사용하는 에러 정정 회로{PARITY CHECK MATRIX GENERATING DEVICE, OPERATING METHOD THEREOF AND ERROR CORRECTION CIRCUIT USING PARITY CHECK MATRIX GENERATED BY THE SAME}

본 발명은 패리티 체크 행렬 생성 장치에 관한 것으로, 더욱 상세하게는 QC-LDPC(Quasi Cyclic Low Density Parity Check) 코드의 패리티 체크 행렬을 생성하는 장치에 관한 것이다.

메모리 시스템은 외부 장치로부터 제공된 데이터를 저장하고, 외부 장치의 요청에 의해 저장된 데이터를 외부 장치로 제공할 수 있다. 메모리 시스템은 저장된 데이터의 신뢰성을 강화하기 위해 에러 정정 회로를 포함할 수 있다. 에러 정정 회로는 데이터에 패리티 데이터를 부가함으로써 인코딩 동작을 수행하고, 메모리 시스템은 인코딩된 데이터를 저장할 수 있다. 또한, 에러 정정 회로는 패리티 데이터에 근거하여 데이터에 대해 디코딩 동작을 수행하고, 메모리 시스템은 디코딩 동작을 통해 정정된 데이터를 외부 장치로 제공할 수 있다.

본 발명의 실시 예는 개선된 성능을 제공하면서 작은 저장 용량을 요구하는 QC-LDPC 코드의 패리티 체크 행렬을 생성하는 패리티 체크 행렬 생성 장치, 그것의 동작 방법 및 패리티 체크 행렬을 사용하는 에러 정정 회로를 제공하는 데 있다.

본 발명의 실시 예에 따른 비이진 순환 순열 행렬을 포함하는 LDPC(Low Density Parity Check) 코드 패리티 체크 행렬의 생성 장치는 상기 비이진 순환 순열 행렬의 상기 패리티 체크 행렬 내에서 위치 정보인 제1 가중치를 저장하는 제1 메모리; 상기 비이진 순환 순열 행렬의 행렬 요소들의 순환 강도인 제2 가중치를 저장하는 제2 메모리; 상기 비이진 순환 순열 행렬의 행렬 요소들 중 비이진 행렬 요소의 크기를 결정하는 제3가중치를 저장하는 제3 메모리; 및 상기 비이진 순환 순열 행렬에 대응하는 크기를 가지는 이진 순환 순열 행렬의 행렬 요소들 중 1의 행렬 요소들에 비이진 값을 적용하고 상기 비이진 값에 상기 제1 내지 제3 가중치들 중 어느 하나 이상을 반영하여, 상기 비이진 순환 순열 행렬을 생성하는 행렬 생성 장치를 포함할 수 있다.

본 발명의 실시 예에 따른 QC-LDPC(Quasi Cyclic Low Density Parity Check) 코드의 패리티 체크 행렬 생성 장치의 동작 방법은 이진 패리티 체크 행렬에 포함된 이진 순환 순열 행렬들을 비이진 순환 순열 행렬들로 각각 변환함으로써 상기 비이진 순환 순열 행렬들을 포함하는 비이진 패리티 체크 행렬을 생성하는 단계를 포함하되, 상기 이진 순환 순열 행렬들을 변환하는 단계는, 이진 순환 순열 행렬의 행렬 특성에 근거하여 상기 이진 순환 순열 행렬에 대응하는 가중치를 계산하는 단계; 비이진 값에 상기 가중치를 적용함으로써 비이진 순환 순열 행렬의 원소들을 생성하는 단계를 포함할 수 있다.

본 발명의 실시 예에 따른 에러 정정 회로는 QC-LDPC(Quasi Cyclic Low Density Parity Check) 코드의 패리티 체크 행렬을 생성하도록 구성된 패리티 체크 행렬 생성부; 및 상기 패리티 체크 행렬에 근거하여 코드워드에 대한 디코딩 동작을 수행하도록 구성된 디코더를 포함하되, 상기 패리티 체크 행렬 생성부는, QC-LDPC 코드의 이진 패리티 체크 행렬에 포함된 이진 순환 순열 행렬들의 행렬 특성들을 저장하고, 상기 행렬 특성들에 근거하여 비이진 순환 순열 행렬들을 생성함으로써 상기 비이진 순환 순열 행렬들을 포함하는 상기 패리티 체크 행렬을 상기 디코더로 제공할 수 있다.

본 발명의 실시 예에 따른 QC-LDPC 코드의 패리티 체크 행렬 생성 장치 및 그것의 동작 방법은 개선된 성능을 제공하면서 작은 저장 용량을 요구하는 패리티 체크 행렬을 생성할 수 있다.

본 발명의 실시 예에 따른 에러 정정 회로는 개선된 성능으로 동작하면서 패리티 체크 행렬을 위해 작은 저장 용량을 필요로 할 수 있다.

도1은 본 발명의 실시 예에 따른 비이진 순환 순열 행렬을 포함하는 LDPC(Low Density Parity Check) 코드의 패리티 체크 행렬 생성 장치를 도시한 블록도,
도2는 이진 패리티 체크 행렬의 구성을 설명하기 위한 도면,
도3은 이진 패리티 체크 행렬에 포함되는 이진 순환 순열 행렬의 구성을 설명하기 위한 도면,
도4는 본 발명의 실시 예에 따라 다양한 가중치 계산 규칙들을 통해 생성된 비이진 순환 순열 행렬들을 도시하는 도면,
도5는 본 발명의 실시 예에 따라 제3 가중치를 더 고려한 가중치 계산 규칙을 통해서 비이진 순환 순열 행렬을 생성하는 방법을 도시하는 도면,
도6은 본 발명의 실시 예에 따른 에러 정정 회로를 도시한 블록도,
도7은 본 발명의 실시 예에 따른 메모리 시스템을 도시한 블록도이다.

이하, 도면들을 참조하여 본 발명의 실시 예에 대해 상세히 설명하기로 한다.

도1은 본 발명의 실시 예에 따른 비이진 순환 순열 행렬을 포함하는 LDPC 코드의 패리티 체크 행렬 생성 장치(10)를 도시한 블록도이다.

도1을 참조하면, 패리티 체크 행렬 생성 장치(10)는 이진 패리티 체크 행렬(HM1)을 변환하여 비이진 패리티 체크 행렬(HM2)을 생성할 수 있다. 비이진 패리티 체크 행렬(HM2)은 QC-LDPC 코드에 근거한 인코딩 동작 및 디코딩 동작에서 사용될 수 있다. 인코딩 동작에서 데이터는 비이진 패리티 체크 행렬(HM2)에 근거하여 인코딩됨으로써 코드워드로 생성될 수 있다. 디코딩 동작에서 코드워드는 비이진 패리티 체크 행렬(HM2)에 근거하여 패리티 체크 검사됨으로써 에러를 포함하는지 여부를 체크받을 수 있다.

패리티 체크 행렬 생성 장치(10)는 이진 패리티 체크 행렬(HM1)에 포함된 이진 순환 순열 행렬들을 비이진 패리티 체크 행렬(HM2)에 포함된 비이진 순환 순열 행렬들로 변환할 수 있다. 패리티 체크 행렬 생성 장치(10)는 비이진 순환 순열 행렬들 각각을, 대응하는 이진 순환 순열 행렬의 이진 패리티 체크 행렬(HM1)에서의 위치와 동일한 위치에 배치할 수 있다. 비이진 순환 순열 행렬에 대응하는 이진 순환 순열 행렬이란, 비이진 순환 순열 행렬로 변환되는 데 기초가 된 이진 순환 순열 행렬일 것이다. 이진 순환 순열 행렬은 비이진 순환 순열 행렬과 동일한 크기를 가질 수 있다.

이진 패리티 체크 행렬(HM1)은 소정 에러 정정 능력을 가지도록 설계된 QC-LDPC 코드의 이진 패리티 체크 행렬일 수 있다. 즉, 이진 패리티 체크 행렬(HM1)의 이진 순환 순열 행렬들 각각은 1 및 0으로 구성될 수 있다.

패리티 체크 행렬 생성 장치(10)는 실질적으로 이진 순환 순열 행렬의 1의 위치들에 비이진 원소들을 배치함으로써 비이진 순환 순열 행렬을 생성할 수 있다. 이때, 패리티 체크 행렬 생성 장치(10)는 소정의 비이진 값에 가중치를 지수로서 적용하여 비이진 원소들을 생성할 수 있다.

구체적으로 살펴보면, 패리티 체크 행렬 생성 장치(10)는 제1 메모리(101), 제2 메모리(102), 제3 메모리(103) 및 행렬 생성 장치(104)를 포함할 수 있다. 우선 비이진 패리티 체크 행렬(HM2)에 포함된 임의의 비이진 순환 순열 행렬에 대해 제1 내지 제3 메모리들(101~103) 및 행렬 생성 장치(104)의 구성 및 동작 방법을 설명하면 아래와 같다.

제1 메모리(101)는 제1 가중치를 저장할 수 있다. 제1 가중치는 비이진 순환 순열 행렬의 비이진 패리티 체크 행렬(HM2) 내에서 위치 정보일 수 있다. 한편, 상술한 바와 같이, 비이진 순환 순열 행렬은 대응하는 이진 순환 순열 행렬과 동일한 위치에 배치되기 때문에, 비이진 순환 순열 행렬의 비이진 패리티 체크 행렬(HM2) 내에서 위치 정보는 이진 패리티 체크 행렬(HM1) 내에서 위치 정보와 동일할 수 있다.

제2 메모리(102)는 제2 가중치를 저장할 수 있다. 제2 가중치는 비이진 순환 순열 행렬의 행렬 요소들의 순환 강도일 수 있다. 비이진 순환 순열 행렬의 행렬 요소들의 순환 강도는 비이진 순환 순열 행렬에 대응하는 이진 순환 순열 행렬의 순환 강도와 동일할 수 있다.

제3 메모리(103)는 제3 가중치를 저장할 수 있다. 제3 가중치는 비이진 순환 순열 행렬의 행렬 요소들 중 비이진 행렬 요소의 크기를 결정할 수 있다.

행렬 생성 장치(104)는 비이진 순환 순열 행렬에 대응하는 크기를 가지는 이진 순환 순열 행렬의 행렬 요소들 중 1의 행렬 요소들에 소정의 비이진 값을 적용하고 비이진 값에 제1 내지 제3 가중치들 중 어느 하나 이상을 반영하여, 비이진 순환 순열 행렬을 생성할 수 있다. 행렬 생성 장치(104)는 제1 내지 제3 가중치들 중 하나 이상에 대해 사칙 연산을 수행함으로써 최종 가중치를 생성하고 비이진 값에 반영할 수 있다. 제1 내지 제3 가중치들 중 어떤 가중치를 적용하고, 사칙 연산들 중 어떤 연산들을 적용할 것인지에 따라 다양한 가중치 계산 규칙이 적용될 수 있다.

이러한 방식으로, 행렬 생성 장치(104)는 비이진 패리티 체크 행렬(HM2)에 포함된 비이진 순환 순열 행렬들을 각각 생성함으로써 비이진 패리티 체크 행렬(HM2)을 생성할 수 있다.

따라서, 에러 정정 회로가 설계될 때, 패리티 체크 행렬 생성 장치(10)는 다양한 가중치 계산 규칙들에 따라 다양한 비이진 패리티 체크 행렬들(HM2)을 생성할 수 있다. 패리티 체크 행렬 생성 장치(10)에 의해 일단 생성된 비이진 패리티 체크 행렬들(HM2)은 에러 정정 회로에 적용되기 위해 그 성능이 테스트될 수 있다.

한편, 행렬 생성 장치(104)는 이진 패리티 체크 행렬(HM1)의 이진 순환 순열 행렬들에 각각 대응하는 제1 내지 제3 가중치들을 동일한 가중치 계산 규칙에 따라 계산할 수 있다.

본 발명에 따른 비이진 패리티 체크 행렬(HM2)은 이진 패리티 체크 행렬(HM1)보다 개선된 성능을 제공할 수 있다. 또한, 비이진 패리티 체크 행렬(HM2)은 패리티 체크 행렬 생성 장치(10)에서 실질적으로 이진 패리티 체크 행렬(HM1)의 위치 정보, 순환 강도 및 0이 아닌 행렬 요소의 위치 정보에 근거하여 생성될 수 있다. 따라서, 비이진 패리티 체크 행렬(HM2)에 근거하여 설계된 에러 정정 회로는 이진 패리티 체크 행렬(HM1)의 위치 정보, 순환 강도 및 0이 아닌 행렬 요소의 위치 정보만을 저장함으로써 비이진 패리티 체크 행렬(HM2)을 생성하여 사용할 수 있다. 즉, 비이진 패리티 체크 행렬(HM2)은 기존 비이진 패리티 체크 행렬이 필요로 하던 저장 용량 대비 작은 저장 용량을 필요로 할 수 있다.

도2는 이진 패리티 체크 행렬(HM1)의 구성을 설명하기 위한 도면이다.

도2를 참조하면, 이진 패리티 체크 행렬(HM1)은 이진 순환 순열 행렬들(C11~C34)로 구성될 수 있다. 이진 패리티 체크 행렬(HM1)에 포함된 이진 순환 순열 행렬들(C11~C34)의 개수는 예시적인 것이다. 이진 순환 순열 행렬들(C11~C34)은 동일한 크기의 정방행렬들일 수 있다. 이진 순환 순열 행렬들(C11~C34) 각각은 n개의 행들과 n개의 열들로 구성될 수 있다. 이진 패리티 체크 행렬(HM1)이 전체 M개의 행들과 전체 N개의 열들로 구성될 때, 이진 패리티 체크 행렬(HM1)은 M/n개의 행 구간들과 N/n개의 열 구간들로 구성될 수 있다. 각 행 구간은 N/n개의 이진 순환 순열 행렬들로 구성되는 행일 수 있다. 각 열 구간은 M/n개의 이진 순환 순열 행렬들로 구성된 열일 수 있다.

이진 순환 순열 행렬들(C11~C34)의 위치들 중 일부에는 영행렬이 배치될 수 있다. 영행렬은 본 발명에 따라 비이진 순환 순열 행렬로 변환되는 대상이 아니다. 즉, 이진 패리티 체크 행렬(HM1)에 포함되는 영행렬은 비이진 패리티 체크 행렬(HM2)에서도 동일한 위치에 배치될 수 있다. 이진 패리티 체크 행렬(HM1)은 사실상 많은 영행렬들을 포함할 수 있으나, 이하에서는 설명을 간편하게 하기 위해 이진 순환 순열 행렬들(C11~C34)은 영행렬이 아닌 것으로 가정할 것이다.

이진 순환 순열 행렬들(C11~C34) 각각은 대응하는 위치 정보, 즉, 행 값(i) 및 열 값(j)에 의해 특정될 수 있다. 어떤 이진 순환 순열 행렬의 행 값(i)은 이진 패리티 체크 행렬(HM1)에서 해당 이진 순환 순열 행렬이 포함된 행 구간의 차수일 수 있다. 예를 들어, 행 값(i)은 1 이상 M/n이하의 자연수일 수 있다. 또한, 어떤 이진 순환 순열 행렬의 열 값(j)은 이진 패리티 체크 행렬(HM1)에서 해당 이진 순환 순열 행렬이 포함된 열 구간의 차수일 수 있다. 예를 들어, 열 값(j)은 1이상 N/n이하의 자연수일 수 있다.

예를 들어, 이진 순환 순열 행렬(C24)의 행 값(i)은 2이고, 열 값(j)은 4일 수 있다.

도3은 이진 패리티 체크 행렬(HM1)에 포함되는 이진 순환 순열 행렬의 구성을 설명하기 위한 도면이다. 도3에 도시된 이진 순환 순열 행렬들(Ci, Ci1, Ci2) 각각의 크기, 즉, 3X3은 예시일 뿐이고, 이진 순환 순열 행렬은 설계에 따라 다양한 크기를 가질 수 있지만, 이하에서 이진 순환 순열 행렬은 3X3의 크기를 가지는 것으로 가정할 것이다.

이진 순환 순열 행렬(Ci)은 항등 행렬일 수 있다. 따라서, 이진 순환 순열 행렬(Ci)의 순환 강도(k)는 0일 수 있다.

이진 순환 순열 행렬(Ci1)은 이진 순환 순열 행렬(Ci)을 오른쪽으로 1만큼 순환 시프트함으로써 생성될 수 있다. 따라서, 이진 순환 순열 행렬(Ci1)의 순환 강도(k)는 1일 수 있다.

이진 순환 순열 행렬(Ci2)은 이진 순환 순열 행렬(Ci)을 오른쪽으로 2만큼 순환 시프트함으로써 생성될 수 있다. 따라서, 이진 순환 순열 행렬(Ci2)의 순환 강도(k)는 2일 수 있다.

즉, 어떤 이진 순환 순열 행렬이 항등 행렬(Ci)을 오른쪽으로 x만큼 순환 시프트함으로써 생성될 때, x는 해당 이진 순환 순열 행렬의 순환 강도(k)로 정의될 것이다.

도2를 다시 참조하면, 이진 패리티 체크 행렬(HM1)의 이진 순환 순열 행렬들(C11~C34)은 서로 다른 순환 강도들을 각각 가질 수 있다.

결과적으로, 이진 순환 순열 행렬들(C11~C34) 각각은 고유의 행렬 특성, 즉, 위치 정보와 순환 강도를 가질 수 있다. 따라서, 에러 정정 회로가 이진 패리티 체크 행렬(HM1)을 저장할 때는, 이진 순환 순열 행렬들(C11~C34)의 행렬 특성들을 대신 저장하더라도 이진 패리티 체크 행렬(HM1)을 복원할 수 있다. 이진 패리티 체크 행렬(HM1)은 이진 순환 순열 행렬들(C11~C34)의 특성들에 의해 특정되는 위치들에 행렬 요소 1들을 배치함으로써 복원될 수 있다. 따라서, 이진 패리티 체크 행렬(HM1)은 매우 작은 저장 용량만을 필요로 하게 된다.

기존의 비이진 패리티 체크 행렬은 모든 원소들의 값들을 저장해야 하므로 매우 큰 저장 용량을 필요로 할 수 있다. 그러나, 본 발명에 따라 생성된 비이진 패리티 체크 행렬(HM2)은 비이진 패리티 체크 행렬이지만 원소들의 값들을 모두 저장할 필요가 없다. 즉, 비이진 패리티 체크 행렬(HM2)은 이진 패리티 체크 행렬(HM1)의 행렬 특성들에 근거하여 생성되므로, 에러 정정 회로에서도 이진 패리티 체크 행렬(HM1)의 행렬 특성들로부터 복원될 수 있다. 따라서, 비이진 패리티 체크 행렬(HM2)은 작은 저장 용량만을 필요로 하고 더욱 개선된 성능을 보일 수 있다.

도4는 본 발명의 실시 예에 따라 다양한 가중치 계산 규칙들을 통해 생성된 비이진 순환 순열 행렬들(C21~C27)을 도시하는 도면이다. 도4는 가중치 계산 규칙들 각각을 통해 이진 순환 순열 행렬(C1)에 대응하는 최종 가중치가 계산되고, 최종 가중치가 비이진 값 a에 적용됨으로써 비이진 순환 순열 행렬(C2)이 생성되는 과정을 도시한다.

도4를 참조하면, 우선, 행렬 특성 중 순환 강도 k가, 예를 들어 1인 이진 순환 순열 행렬(C1)이 도시된다, 이진 순환 순열 행렬(C1)은 또한 행 값(i) 및 열 값(j)을 가질 수 있다. 이진 순환 순열 행렬(C1)은 다양한 가중치 계산 규칙들에 따라 비이진 순환 순열 행렬들(C21~C27)로 변환될 수 있다.

이와 같이 생성된 비이진 순환 순열 행렬(C2)은 비이진 패리티 체크 행렬(HM2)에서 이진 순환 순열 행렬(C1)과 동일한 행 구간 및 열 구간에 위치할 수 있다. 즉, 비이진 순환 순열 행렬(C2)은 비이진 패리티 체크 행렬(HM2)에서 i번째 행 구간과 j번째 열 구간에 위치할 수 있다.

이하에서 이진 순환 순열 행렬(C1)을 비이진 순환 순열 행렬(C2)로 변환하는 방법을 구체적으로 살펴보면 다음과 같다.

비이진 순환 순열 행렬(C2)에서 최종 가중치가 적용될 a는 소정의 비이진 값일 수 있다. 어떤 가중치 계산 규칙에 따르더라도 a는 이진 순환 순열 행렬(C1)의 1의 위치에 배치될 수 있다. 즉, a는 이진 순환 순열 행렬(C1)의 순환 강도 1에 따라 위치가 결정될 수 있다. 그리고 계산된 최종 가중치가 a에 지수로서 적용될 수 있다.

최종 가중치는 이진 순환 순열 행렬(C1)의 행 값(i), 열 값(j) 및 순환 강도(k) 중 하나 이상에 덧셈을 적용함으로써 계산될 수 있다. 예를 들어, 비이진 순환 순열 행렬(C24)의 가중치 i+j는 행 값(i) 및 열 값(j)을 덧셈함으로써 계산될 수 있다. 한편, 이진 순환 순열 행렬의 행 값(i), 열 값(j) 및 순환 강도(k) 중 하나의 변수만이 선택될 때, 즉, 비이진 순환 순열 행렬들(C21~C23)의 가중치들을 계산할 때, 덧셈은 실질적으로 수행되지 않을 수 있다.

한편, 도4의 가중치 계산 규칙은, 예시적으로 덧셈만을 사용하지만, 실시 예에 따라, 다른 연산들, 즉, 뺄셈, 곱셈 및 나눗셈도 사용할 수 있다. 또한, 가중치 계산 규칙은 한 가지의 연산만 사용하지 않고 둘 이상의 연산들의 조합을 사용할 수 있다.

어떤 가중치 계산 규칙을 적용할 것인지는 결국 목표로 설정된 패리티 체크 행렬의 성능에 따라 결정될 것이다. 다양한 가중치 계산 규칙들이 테스트되면서 가장 최고의 성능을 제공하는 비이진 패리티 체크 행렬(HM2)이 생성될 수 있다.

도5는 본 발명의 실시 예에 따라 제3 가중치를 더 고려한 가중치 계산 규칙을 통해서 비이진 순환 순열 행렬(C3)을 생성하는 방법을 도시하는 도면이다.

도5를 참조하면, 비이진 순환 순열 행렬(C3)은 이진 순환 순열 행렬(C1)로부터 변환될 수 있다. 도4를 참조하여 설명한 바와 같이, 비이진 순환 순열 행렬(C3)은 비이진 값 a에 최종 가중치가 적용됨으로써 생성될 수 있다. 비이진 순환 순열 행렬(C3)의 최종 가중치는, 예를 들어, 이진 순환 순열 행렬(C1)의 제1 가중치, 즉, 행 값(i) 및 열 값(j)에 제3 가중치를 더 고려하여 계산될 수 있다.

비이진 순환 순열 행렬(C3)의 원소들은 제3가중치들 0, 1 및 2에 각각 대응할 수 있다. 제3가중치는 비이진 순환 순열 행렬(C3)의 행들에 대해 0부터 순차적으로 증가하도록 적용될 수 있다. 제3 가중치는 비이진 순환 순열 행렬의 행렬 요소들 중 비이진 행렬 요소의 크기를 결정할 수 있다. 이와 같이, 이진 순환 순열 행렬(C1)의 행렬 특성에 제3가중치가 더 적용될 때, 비이진 순환 순열 행렬(C3)의 최종 가중치들은 행마다 다를 수 있다. 제3 가중치는 순환 가중치일 수 있다.

한편, 도5의 가중치 계산 규칙은, 예시적으로 덧셈만을 사용하지만, 실시 예에 따라, 다른 연산들, 즉, 뺄셈, 곱셈 및 나눗셈도 사용할 수 있다. 또한, 가중치 계산 규칙은 한 가지의 연산만 사용하지 않고 둘 이상의 연산들의 조합을 사용할 수 있다.

또한, 도5의 가중치 계산 규칙은 이진 순환 순열 행렬(C1)의 행렬 특성 중 행 값(i) 및 열 값(j)만을 변수로 사용하지만, 도4를 참조하여 설명한 바와 같이, 변수들의 다양한 조합들을 사용할 수 있다.

정리하면, 도4 및 도5의 비이진 순환 순열 행렬들(C2, C3)의 가중치는 이진 순환 순열 행렬(C1)의 행렬 특성만 알고 있다면 소정의 가중치 계산 규칙을 통해 계산될 수 있다. 그리고, 비이진 순환 순열 행렬들(C2, C3)의 원소들은 소정의 비이진 값에 가중치를 적용함으로써 생성될 수 있다. 따라서, 비이진 순환 순열 행렬들(C2, C3)을 위한 저장 용량은 이진 순환 순열 행렬을 저장하기 위한 저장 용량 대비 실질적으로 증가하지 않을 수 있다.

도6은 본 발명의 실시 예에 따른 에러 정정 회로(20)를 도시한 블록도이다.

에러 정정 회로(20)는 패리티 체크 행렬 생성부(21) 및 디코더(22)를 포함할 수 있다.

패리티 체크 행렬 생성부(21)는 QC-LDPC 코드의 패리티 체크 행렬(HM)을 생성할 수 있다. 패리티 체크 행렬(HM)은 도1 내지 도5를 참조하여 설명된 방법에 따라 생성된 비이진 패리티 체크 행렬(HM2)일 수 있다. 패리티 체크 행렬 생성부(21)는 도1의 패리티 체크 행렬 생성 장치(10)와 실질적으로 유사하게 구성될 수 있다. 패리티 체크 행렬 생성부(21)는 도1의 패리티 체크 행렬 생성 장치(10)가 비이진 패리티 체크 행렬(HM2)을 생성한 방법과 실질적으로 유사하게 패리티 체크 행렬(HM)을 생성하여 디코더(22)로 제공할 수 있다. 즉, 패리티 체크 행렬 생성부(21)는 소정의 특성들(CM_IF)에 대해 소정의 가중치 계산 규칙을 적용함으로써 패리티 체크 행렬(HM)을 생성할 수 있다. 특성들(CM_IF)은 패리티 체크 행렬 생성 장치(10)에서 패리티 체크 행렬(HM)을 생성하는데 기초가 된 이진 패리티 체크 행렬에 관한 것일 수 있다. 즉, 특성들(CM_IF)은 이진 패리티 체크 행렬의 이진 순환 순열 행렬의 제1 가중치, 제2 가중치, 및 제3 가중치를 포함할 수 있다.

패리티 체크 행렬 생성부(21)가 사용하는 가중치 계산 규칙은 패리티 체크 행렬 생성 장치(10)를 통해 패리티 체크 행렬(HM)을 생성하고 시험함으로써 선택된 것일 수 있다.

디코더(22)는 패리티 체크 행렬(HM)에 근거하여 코드워드(CW)에 대한 디코딩 동작을 수행하고 에러 정정된 코드워드(CCW)를 출력할 수 있다.

도7은 본 발명의 실시 예에 따른 메모리 시스템(100)을 도시한 블록도이다.

메모리 시스템(100)은 외부 장치의 라이트 요청에 응답하여, 외부 장치로부터 제공된 데이터를 저장하도록 구성될 수 있다. 또한, 메모리 시스템(100)은 외부 장치의 리드 요청에 응답하여, 저장된 데이터를 외부 장치로 제공하도록 구성될 수 있다.

메모리 시스템(100)은 PCMCIA(Personal Computer Memory Card International Association) 카드, CF(Compact Flash) 카드, 스마트 미디어 카드, 메모리 스틱, 다양한 멀티 미디어 카드(MMC, eMMC, RS-MMC, MMC-micro), SD(Secure Digital) 카드(SD, Mini-SD, Micro-SD), UFS(Universal Flash Storage) 또는 SSD(Solid State Drive) 등으로 구성될 수 있다.

메모리 시스템(100)은 컨트롤러(110) 및 비휘발성 메모리 장치(120)를 포함할 수 있다.

컨트롤러(110)는 메모리 시스템(100)의 제반 동작을 제어할 수 있다. 컨트롤러(110)는 외부 장치로부터 전송된 라이트 요청에 응답하여 비휘발성 메모리 장치(120)에 데이터를 저장하고, 외부 장치로부터 전송된 리드 요청에 응답하여 비휘발성 메모리 장치(120)에 저장된 데이터를 리드하여 외부 장치로 출력할 수 있다.

컨트롤러(110)는 에러 정정부(111)를 포함할 수 있다. 에러 정정부(111)는 비휘발성 메모리 장치(120)로부터 리드된 코드워드(CW)에 대해 QC-LDPC 코드의 패리티 체크 행렬에 근거하여 디코딩 동작을 수행할 수 있다. 에러 정정부(111)는 도7에 도시된 에러 정정 회로(20)와 실질적으로 동일하게 구성되고 동작할 수 있다. 에러 정정부(111)는 비휘발성 메모리 장치(120)에 저장된 특성들(CM_IF)을, 예를 들어, 동작 개시 시에 로드하고, 내부의 패리티 체크 행렬 생성부(미도시)에 저장하고 패리티 체크 행렬을 생성하는데 사용할 수 있다.

비휘발성 메모리 장치(120)는 컨트롤러(110)의 제어에 따라, 컨트롤러(110)로부터 전송된 데이터를 저장하고, 저장된 데이터를 리드하여 컨트롤러(110)로 전송할 수 있다. 비휘발성 메모리 장치(120)는특성들(CM_IF) 및 코드워드(CW)를 저장할 수 있다.

비휘발성 메모리 장치(120)는 낸드 플래시(NAND Flash) 또는 노어 플래시(NOR Flash)와 같은 플래시 메모리 장치, FeRAM(Ferroelectrics Random Access Memory), PCRAM(Phase-Change Random Access Memory), MRAM(Magnetic Random Access Memory) 또는 ReRAM(Resistive Random Access Memory) 등을 포함할 수 있다.

한편, 도7은 메모리 시스템(100)이 1개의 비휘발성 메모리 장치(120)를 포함하는 것으로 도시하나, 메모리 시스템(100)에 포함되는 비휘발성 메모리 장치들의 개수는 이에 제한되지 않는다.

본 발명이 속하는 기술분야의 통상의 기술자는 본 발명이 그 기술적 사상이나 필수적 특징을 변경하지 않고서 다른 구체적인 형태로 실시될 수 있으므로, 이상에서 기술한 실시 예들은 모든 면에서 예시적인 것이며 한정적인 것이 아닌 것으로서 이해해야만 한다. 본 발명의 범위는 상기 상세한 설명보다는 후술하는 특허청구범위에 의하여 나타내어지며, 특허청구범위의 의미 및 범위 그리고 그 등가개념으로부터 도출되는 모든 변경 또는 변형된 형태가 본 발명의 범위에 포함되는 것으로 해석되어야 한다.

10: 패리티 체크 행렬 생성 장치
101: 제1 메모리
102: 제2 메모리
103: 제3 메모리
104: 행렬 생성 장치

Claims

비이진 순환 순열 행렬을 포함하는 LDPC(Low Density Parity Check) 코드 패리티 체크 행렬의 생성 장치로서,
상기 비이진 순환 순열 행렬의 상기 패리티 체크 행렬 내에서 위치 정보인 제1 가중치를 저장하는 제1 메모리;
상기 비이진 순환 순열 행렬의 행렬 요소들의 순환 강도인 제2 가중치를 저장하는 제2 메모리;
상기 비이진 순환 순열 행렬의 행렬 요소들 중 비이진 행렬 요소의 크기를 결정하는 제3가중치를 저장하는 제3 메모리; 및
상기 비이진 순환 순열 행렬에 대응하는 크기를 가지는 이진 순환 순열 행렬의 행렬 요소들 중 1의 행렬 요소들에 비이진 값을 적용하고 상기 비이진 값에 상기 제1 내지 제3 가중치들 중 어느 하나 이상을 반영하여, 상기 비이진 순환 순열 행렬을 생성하는 행렬 생성 장치를 포함하는 패리티 체크 행렬 생성 장치.
제1항에 있어서,
상기 행렬 생성 장치는 상기 제1 내지 제3 가중치들 중 상기 어느 하나 이상에 대해 연산하고, 연산된 값을 상기 비이진 값에 지수로서 적용하는 패리티 체크 행렬 생성 장치.
제1항에 있어서,
상기 비이진 순환 순열 행렬의 상기 행렬 요소들은 상기 순환 강도에 근거하여 상기 비이진 순환 순열 행렬에서 배치되는 패리티 체크 행렬 생성 장치.
제1항에 있어서,
상기 비이진 순환 순열 행렬들 각각은, 대응하는 이진 순환 순열 행렬의 상기 이진 패리티 체크 행렬에서의 위치와 동일한 위치에 배치되는 패리티 체크 행렬 생성 장치.
이진 패리티 체크 행렬에 포함된 이진 순환 순열 행렬들을 비이진 순환 순열 행렬들로 각각 변환함으로써 상기 비이진 순환 순열 행렬들을 포함하는 비이진 패리티 체크 행렬을 생성하는 단계를 포함하되,
상기 이진 순환 순열 행렬들을 변환하는 단계는,
이진 순환 순열 행렬의 행렬 특성에 근거하여 상기 이진 순환 순열 행렬에 대응하는 가중치를 계산하는 단계; 및
비이진 값에 상기 가중치를 적용함으로써 비이진 순환 순열 행렬의 원소들을 생성하는 단계를 포함하는 QC-LDPC(Quasi Cyclic Low Density Parity Check) 코드의 패리티 체크 행렬 생성 장치의 동작 방법.
제5항에 있어서,
상기 가중치를 계산하는 단계는,
상기 행렬 특성에 포함된 행 값, 열 값 및 순환 강도 중 하나 이상에 근거하여 상기 가중치를 계산하는 단계를 포함하는 패리티 체크 행렬 생성 장치의 동작 방법.
제5항에 있어서,
상기 가중치를 계산하는 단계는,
상기 행렬 특성에 포함된 행 값, 열 값 및 순환 강도 중 하나 이상과 순환 가중치에 근거하여 상기 가중치를 계산하는 단계를 포함하는 패리티 체크 행렬 생성 장치의 동작 방법.
제5항에 있어서,
상기 이진 순환 순열 행렬들은, 동일한 가중치 계산 규칙에 따라 계산되는 가중치들에 각각 대응하는 패리티 체크 행렬 생성 장치의 동작 방법.
제5항에 있어서,
상기 가중치를 적용하는 단계는,
상기 비이진 값에 상기 가중치를 지수로서 적용하는 단계를 포함하는 패리티 체크 행렬 생성 장치의 동작 방법.
제5항에 있어서,
상기 비이진 순환 순열 행렬을 생성하는 단계는,
상기 원소들을 상기 행렬 특성에 포함된 순환 강도에 근거하여 배치하는 단계를 더 포함하는 패리티 체크 행렬 생성 장치의 동작 방법.
제5항에 있어서,
상기 비이진 패리티 체크 행렬을 생성하는 단계는,
상기 비이진 순환 순열 행렬들 각각을, 대응하는 이진 순환 순열 행렬의 상기 이진 패리티 체크 행렬에서의 위치와 동일한 위치에 배치하는 단계를 포함하는 패리티 체크 행렬 생성 장치의 동작 방법.
QC-LDPC(Quasi Cyclic Low Density Parity Check) 코드의 패리티 체크 행렬을 생성하도록 구성된 패리티 체크 행렬 생성부; 및
상기 패리티 체크 행렬에 근거하여 코드워드에 대한 디코딩 동작을 수행하도록 구성된 디코더를 포함하되,
상기 패리티 체크 행렬 생성부는, QC-LDPC 코드의 이진 패리티 체크 행렬에 포함된 이진 순환 순열 행렬들의 행렬 특성들을 저장하고, 상기 행렬 특성들에 근거하여 비이진 순환 순열 행렬들을 생성함으로써 상기 비이진 순환 순열 행렬들을 포함하는 상기 패리티 체크 행렬을 상기 디코더로 제공하는 에러 정정 회로.
제12항에 있어서,
상기 패리티 체크 행렬 생성부는, 이진 순환 순열 행렬의 행렬 특성에 근거하여 상기 이진 순환 순열 행렬에 대응하는 가중치를 계산하고, 비이진 값에 상기 가중치를 적용함으로써 비이진 순환 순열 행렬의 원소들을 생성하는 에러 정정 회로.
제13항에 있어서,
상기 패리티 체크 행렬 생성부는, 상기 행렬 특성에 포함된 행 값, 열 값 및 순환 강도 중 하나 이상에 근거하여 상기 가중치를 계산하는 에러 정정 회로.
제13항에 있어서,
상기 패리티 체크 행렬 생성부는, 상기 행렬 특성에 포함된 행 값, 열 값 및 순환 강도 중 하나 이상과 순환 가중치에 근거하여 상기 가중치를 계산하는 에러 정정 회로.
제13항에 있어서,
상기 패리티 체크 행렬 생성부는, 상기 원소들을 상기 행렬 특성에 포함된 순환 강도에 근거하여 배치하는 에러 정정 회로.
제12항에 있어서,
상기 패리티 체크 행렬 생성부는, 상기 비이진 순환 순열 행렬들 각각을, 대응하는 이진 순환 순열 행렬의 상기 이진 패리티 체크 행렬에서의 위치와 동일한 위치에 배치하는 에러 정정 회로.