KR101854954B1

KR101854954B1 - 치환 소행렬의 합을 사용하는 체크섬

Info

Publication number: KR101854954B1
Application number: KR1020147004642A
Authority: KR
Inventors: 에란 샤론; 이단 알로드
Original assignee: 샌디스크 테크놀로지스 엘엘씨
Priority date: 2011-07-29
Filing date: 2012-07-26
Publication date: 2018-05-04
Also published as: US8880987B2; WO2013019560A2; EP2737630A2; WO2013019560A3; TW201319800A; KR20140078610A; US20130031440A1

Abstract

데이터 비트들을 인코딩하기 위한 방법으로서, 이 방법은 데이터 비트들에 근거하여 체크섬 패리티 비트들을 계산하는 것을 포함한다. 데이터 비트들과 체크섬 패리티 비트들이 만족시키는 방정식들의 세트는 조밀 패리티-체크 행렬에 대응한다. 조밀 패리티-체크 행렬은 치환 소행렬들의 합을 포함한다.

Description

치환 소행렬의 합을 사용하는 체크섬{CHECKSUM USING SUMS OF PERMUTATION SUB-MATRICES}

관련 출원에 대한 상호-참조

본 출원은 미국 가특허 출원 번호 제61/513,186호(출원일: 2011년 7월 29일)에 대한 우선권을 주장하는바, 상기 미국 출원은 그 전체가 참조로 본 명세서에 통합된다.

본 개시내용은 일반적으로 데이터를 인코딩(encoding)하는 것 및 데이터를 디코딩(decoding)하는 것에 관한 것이다.

플래시 메모리는 최근 점점더 널리 사용되고 있다. 플래시 메모리는 모바일 전화기, 디지털 카메라, 뮤직 플레이어 및 다른 많은 애플리케이션을 포함하는 수 많은 애플리케이션에서 사용된다. 새롭게 출현한 주요 애플리케이션은 플래시 메모리를 솔리드 스테이트 디스크(Solid State Disc, SSD)로서 사용한다. 이러한 메모리들은 고급 에러 정정 코딩(Error Correction Coding, ECC) 방식과 같은 리던시(redundancy)를 갖는 고밀도 멀티-레벨 셀(Multi-Level Cell, MLC) 메모리들을 사용하여 구현될 수 있다. 예를 들어, 고급 ECC 방식은 저밀도 패리티-체크(Low-Density Parity-Check, LDPC) 혹은 터보 코드(Turbo codes)에 근거하는 반복적 코딩 방식을 포함한다.

에러 정정 코드들은, 프로그래밍 혹은 판독 동안 또는 저장 동안 물리적 매체의 의해 야기되는 에러들을 처리함으로써, 데이터 신뢰성 및 무결성을 제공하기 위해 메모리에 공통적으로 사용된다. 에러 정정 코드는 소정의 제약 세트를 만족시키는 코드워드(codeword)들의 세트이다. 에러 정정 코드들의 하나의 공통적으로 사용되는 클래스(class)는 바이너리 선형 블록 코드들(binary linear block codes)의 클래스인바, 여기서 코드는 코드워드 비트들에 관한 패리티-체크 제약 세트를 통해 정의된다. 달리 말하면, 바이너리 선형 블록 코드는 유효 코드워드가 만족시켜야만 하는 2-원소 갈로아 필드(Galois field) GF(2)에 걸쳐 1차 방정식들의 세트에 의해 정의된다. 1차 방정식들의 세트는

개의 행(row)들을 갖는 패리티-체크 행렬(parity-check matrix)

를 통해 편리하게 서술될 수 있는바, 이에 따라 행렬의 각각의 행은 하나의 패리티-체크 제약을 정의하며 워드(word)

는 만약 (GF(2)에 걸쳐)

이기만 한다면 유효 코드워드를 구성한다. 벡터

는 워드

와 관련된 신드롬 벡터(syndrome vector)로서 일반적으로 알려져 있다. 이러한 신드롬은 다른 신드롬, "순환 리던던시 체크(Cyclic Redundancy Check, CRC)" 혹은 "체크섬(checksum)" 신드롬과 구분하기 위해 "에러 정정(error correction)" 신드롬으로서 지칭될 수 있다. 신드롬 벡터의 각각의 원소는 패리티 체크 방정식들 중 하나와 관련되며, 원소의 값은

가 만족시키는 방정식에 대해서는 0이고

가 만족시키지 못하는 방정식에 대해서는 1이다. 신드롬 벡터의 원소들은 또한, 본 명세서에서 신드롬 벡터의 "비트(bit)들"로 지칭된다. 신드롬 가중치(

)는 신드롬 벡터

에 의해 표현되는 만족되지 못한 방정식들의 개수이다. 그래서 워드가 유효 코드워드가 되기 위해서, 워드와 관련된 신드롬 벡터는 모두 0이어야 하거나 그 신드롬 가중치가 0이어야 한다.

에러 정정 코드들은 LDPC 및 터보 코드들과 같은 반복적 코딩 방식에 근거할 수 있다. 반복적 코딩 방식에서, 코딩은 반복 알고리즘을 사용하여 수행되는바, 반복 알고리즘은 알고리즘이 유효 코드워드로 수렴할 때까지 코드워드 비트들의 추정들을 반복적으로 업데이트한다. 반복적으로 업데이트되는 추정들은 "하드(hard)" 추정(1 대 0)이거나 혹은 "소프트(soft)" 추정인바, 소프트 추정은 추정된 값이 맞을 확률을 표시하는 추정의 어떤 신뢰도 측정치와 함께 비트의 값(1 또는 0)을 추정하는 것으로 이루어진다. 일반적으로 사용되는 소프트 추정은 로그 우도비(Log Likelihood Ratio, LLR)인바, 이는 비트가 1일 확률에 대한 비트가 0일 확률의 비율을 나타낸다. 양의 LLR(positive LLR)은 비트가 1보다는 0이 될 확률이 더 높을 것으로 추정됨을 의미한다. 음의 LLR(negative LLR)은 비트가 0보다는 1이 될 확률이 더 높을 것으로 추정됨을 의미한다. LLR의 절대값은 추정의 확실성(certainty)의 표시이다. 비트의 추정은 "플립핑(flipping)"일 수 있는데, 이것이 의미하는 바는 비트 추정의 값이 변경됨을 의미하는바, 예를 들어 하드 추정은 0에서 1로 변경되거나 혹은 1에서 0으로 변경되며, 또는 LLR의 부호가 양에서 음으로 변경되거나 혹은 음에서 양으로 변경된다. (유사하게, 신드롬 벡터의 비트를 "플립핑(flipping)"하는 것은 비트를 1에서 0으로 변경하는 것 혹은 0에서 1로 변경하는 것을 표시한다.) 검출기는 비트들의 초기 선험적(a- priori)(가능하게는 "소프트") 추정들로 초기화된다. 이러한 추정들은 반복적으로 프로세싱 및 업데이트된다. 고정된 횟수의 반복 이후에 디코딩은 종료될 수 있다. 대안적으로, 수렴 검출 메커니즘(convergence detection mechanism)은 현재 비트 추정들이 모든 패리티 체크 제약을 만족시키는 경우 디코딩을 종료시킬 수 있다.

이른 디코딩 종료를 위한 또 하나의 다른 옵션은 "발산(divergence)" 검출 메커니즘에 의한 것인바, 이 메커니즘은 디코더 수렴에 대한 확률이 낮은지, 따라서 현재 디코딩 시도를 종료하고 디코더 초기화 값들을 업데이트한 이후 디코딩을 재시도하는 것이 더 효과적인지를 검출한다. 이러한 발산 검출을 수행하기 위한 하나의 옵션은 만족되지 못한 패리티-체크 제약들의 현재 개수가 너무 많은지에 근거한다. 발산 검출을 위한 또 하나의 다른 옵션은 디코딩 동안의 만족되지 못한 패리티-체크들의 개수의 발전(evolution)에 근거한다. 이러한 이른 종료의 경우, 디코딩은, 메모리 판독 임계치들 혹은 판독 분해능(reading resolution)과 같은 특정 파라미터들을 변경시킨 이후에, 업데이트된 초기화 값들로 반복될 수 있고, 이에 따라 그 반복되는 시도에서의 성공적인 디코딩 수렴의 확률은 증가하게 된다.

반복적 디코딩 프로세스의 유효 코드워드로의 수렴 이후에, 디코딩 프로세스가 올바르지 않은 코드워드에 수렴했는지 여부를 결정하기 위해 최종 코드워드에 관한 체크섬이 수행될 수 있다. 예를 들어, 코드워드는 데이터 비트들에 대응하는 CRC 패리티 비트들과 함께 데이터 비트들을 인코딩할 수 있다. 그러나, 반복적 디코딩 프로세스로부터 일어나게 되는 코드워드에 관해 CRC 프로세싱을 수행하는 것은 추가의 디코딩 지연을 유발시킬 수 있다.

반복 이후 디코딩 지연을 유발시킴 없이 "온-더-플라이(on-the-fly)" 체크섬 계산을 가능하게 체크섬 구조가 개시된다. 체크섬은, 효율적으로 발생될 수 있으며, 준-순환 LDPC(Quasi-Cyclic LDPC, QC-LDPC) 코드들을 위한 LDPC 디코더의 데이터 경로와 호환가능하다. 더욱이, 체크섬은 LDPC 디코더에 의해 검출되지 않는 에러들을 검출함에 있어 종래의 CRC만큼 효과적일 수 있다.

첨부되는 도면을 참조하여 단지 예시적으로 다양한 실시예들이 본 명세서에서 설명되는바, 도면에서,
도 1은 반복적 디코더의 블록도이다.
도 2는 실시간 디코더 수렴 검출을 위한 회로의 제 1 실시예를 나타낸다.
도 3은 실시간 디코더 수렴 검출을 위한 디코더의 제 1 실시예를 나타낸다.
도 4는 도 3의 신드롬 벡터 업데이트 블록이 신드롬 벡터를 초기화시키기 위해 어떻게 사용될 수 있는지를 예시한다.
도 5는 실시간 디코더 수렴 검출을 위한 디코더의 제 2 실시예를 나타낸다.
제 6은 체크섬과 ECC를 모두 사용하는 인코더의 블록도이다.
도 7은 실시간 디코더 수렴 검출과 체크섬 계산을 조인트시키기 위한 확장된 행렬을 나타낸다.
도 8은 CRC 프로세싱을 수행하도록 구성된 코딩 유닛을 포함하는 데이터 저장 디바이스가 포함된 시스템을 나타내는바, 여기서 CRC 프로세싱은 치환 행렬들의 합에 근거한다.

도면을 참조하면, 도 1은 반복적 디코더(10)의 블록도를 제시한다. 초기 비트 추정들은 비트 추정 랜덤 액세스 메모리(Random Access Memory, RAM)(12)에 저장된다. 판독-전용 메모리(Read-Only Memory, ROM)(14)는 코드 서술(code description)을 저장하기 위해 사용된다. 예를 들어, ROM(14)은 각각의 패리티 체크 제약에 어떤 비트들이 관여하고 있는지의 표시를 저장할 수 있다(즉, ROM(14)은 코드를 정의하는 패리티 체크 행렬

를 저장한다). 비트 추정들은 비트 추정 RAM(12)으로부터 라우팅 계층(routing layer)(16)을 통해 수 개의 프로세싱 유닛들(18)로 판독된다. 코드 서술 ROM(14)은 비트 추정들을 프로세싱 유닛들(18)로 라우팅시키는 것을 제어한다. 프로세싱 유닛들(18)은 비트들이 만족시켜야만 하는 패리티-체크 제약들에 근거하여 비트 추정들을 업데이트한다. 스크래치패드 RAM(scratchpad RAM)(20)은 비트 추정들을 업데이트하는 데 필요한 일시적 데이터를 저장하기 위해 프로세싱 유닛들(18)에 의해 사용될 수 있다. 비트 추정들의 업데이트는 반복적으로 행해지는바, 한번에 하나 이상의 비트 추정들에 대해 행해지고, 여기서 반복은 비트 추정들이 만족시켜야만 하는 모든 패리티-체크 제약들에 근거하여 비트 추정들을 업데이트하는 것(즉, 코드 서술 ROM(14)을 한 차례 "트래버싱(traversing)"하는 것)을 포함할 수 있다. 수렴 검출 블록(22)이 (예를 들어, 신드롬 가중치(syndrome weight)가 0인지 여부를 테스팅(testing)함으로써) 현재 비트 추정들에 의해 모든 패리티 체크 제약들이 만족된다고 검출하는 경우, 디코딩은 미리 결정된 횟수의 반복들 이후에 혹은 수렴 검출 블록(22)에 의해 발생된 수렴 신호에 따라 종료될 수 있다.

디코딩 "반복(iteration)"은, 코드를 정의하는 패리티-체크 방정식들 각각을 고려하는 것, 그리고 모든 패리티 체크 방정식들이 고려될 때까지 특정 스케쥴에 따라 각각의 패리티-체크 방정식과 관련된 코드워드 비트들의 추정들을 업데이트하는 것으로서 정의될 수 있다. 예를 들어, LDPC 디코딩은 일반적으로 "태너 그래프(Tanner graph)"의 노드들 간의 메시지 패싱(message passing)으로서 나타내질 수 있는바, 여기서 태너 그래프의 에지(edge)들은 코드워드 비트들을 나타내는 노드들을 코드워드 비트들이 만족시켜야만 하는 패리티-체크들을 나타내는 노드들과 연결시킨다. 태너 그래프 상에서의 LDPC 디코딩을 위한 메시지-패싱 스케쥴의 예는 다음과 같은 것을 포함한다.

1. 모든 패리티-체크 노드들을 트래버싱함(이것은 메시지들을 각각의 패리티-체크 노드로부터 그 패리티-체크 노드가 그래프의 에지들에 의해 연결된 코드워드 비트 노드들로 패싱하는 것). 코드워드 비트 노드들에서 수신된 메시지들에 따라 코드워드 비트 추정들을 업데이트함. 그 다음에, 모든 코드워드 비트 노드들을 트래버싱함(이것은 메시지들을 각각의 코드워드 비트 노드로부터 그 코드워드 비트 노드가 그래프의 에지들에 의해 연결된 패리티-체크 노드들로 패싱하는 것). 패리티-체크 노드들에서 수신된 메시지들에 따라 패리티-체크 비트 추정들을 업데이트함.

2. 모든 코드워드 노드들을 트래버싱함(이것은 메시지들을 각각의 코드워드 비트 노드로부터 그 코드워드 비트 노드가 그래프의 에지들에 의해 연결된 패리티-체크 노드들로 패싱하는 것). 패리티-체크 노드들에서 수신된 메시지들에 따라 패리티-체크 비트 추정들을 업데이트함. 그 다음에, 모든 패리티-체크 노드들을 트래버싱함(이것은 메시지들을 각각의 패리티-체크 노드로부터 그 패리티-체크 노드가 그래프의 에지들에 의해 연결된 코드워드 비트 노드들로 패싱하는 것). 코드워드 비트 노드들에서 수신된 메시지들에 따라 코드워드 비트 추정들을 업데이트함.

3. 모든 패리티-체크 노드들을 트래버싱함. 각각의 패리티-체크 노드에서, 메시지들을 그래프의 에지들에 의해 패리티 체크 노드에 연결된 코드워드 비트 노드들로부터 패리티-체크 노드로 패싱하고, 패리티-체크 노드에서 수신된 메시지들에 따라 패리티-체크 비트 추정을 업데이트하고, 패리티-체크 노드로부터 이러한 코드워드 비트 노드들로 다시 메시지들을 전송하고, 그리고 패리티 체크 노드로부터 수신된 메시지들에 따라 이러한 코드워드 비트 노드들에서 코드워드 비트 추정들을 업데이트함.

4. 모든 코드워드 비트 노드들을 트래버싱함. 각각의 코드워드 비트 노드에서, 메시지들을 그래프의 에지들에 의해 코드워드 비트 노드에 연결된 패리티-체크 노드들로부터 코드워드 비트 노드로 패싱하고, 코드워드 비트 노드에서 수신된 메시지들에 따라 코드워드 비트 추정을 업데이트하고, 코드워드 비트 노드로부터 이러한 패리티-체크 노드들로 다시 메시지들을 전송하고, 그리고 코드워드 비트 노드로부터 수신된 메시지들에 따라 이러한 패리티-체크 노드들에서 패리티-체크 비트 추정들을 업데이트함.

"반복(iteration)"은 그 관련된 스케쥴이 완료될 때까지 계속된다.

SSD 및 모바일과 같은 애플리케이션들에 대해 의도된 플래시 메모리들은 매운 높은 랜덤 입출력(Input/Output)(I/O) 성능을 요구할 수 있다. 판독 동안, 이것은 매우 빠른 ECC 디코더들의 사용을 시사한다. 반복적 코딩 방식에서 빠른 디코딩을 달성하기 위해, 빠른 수렴 검출 장치 제공될 수 있다. 수렴 검출 블록(22)은 (이른 종료로 인한) 더 빠른 디코딩 시간을 가능하게 하며 디코더(10)에 의한 더 낮은 에너지 소비를 가능하게 한다.

반복적 디코더들에서의 수렴 검출은, 각각의 디코딩 반복의 끝에서 신드롬 벡터

를 계산하는 것(여기서

는 반복의 끝에서 비트 추정들의 벡터임), 그리고 모든 패리티-체크들이 만족되는지 여부(즉, 신드롬 가중치가 0인지 여부)를 체크하는 것을 포함할 수 있다. 신드롬 벡터를 계산하기 위해 각각의 반복의 끝에서 전용 프로세싱이 수행될 수 있는바, 이는 디코딩 반복들의 디코딩 시간 비용을연장시킬 수 있다.

코드의 패리티-체크 방정식들이 차례로 프로세싱되는 직렬 스케쥴에 근거하는 반복적 디코더들은 세미-온-더-플라이 수렴 검출(semi-on-the-fly convergence detection)을 수행할 수 있다. 이러한 접근법에 따르면, 만족되는 패리티-체크들의 개수를 보유하고 있는 카운터(counter)가 유지된다. 디코딩의 시작시, 이러한 카운터는 0으로 설정된다. 디코딩 동안 코드의 패리티-체크들은 직렬로 그리고 반복적으로 트래버싱되고, 비트 추정들은 패리티-체크들 각각에 근거하여 업데이트된다. 디코딩 프로세스의 일부로서, 각각의 패리티-체크의 신드롬 비트는 패리티-체크가 트래버싱될 때 계산된다. 만약 신드롬 비트가 0이라면(즉, 패리티-체크가 만족된다면), 카운터는 증분되고, 만약 그렇지 않다면 카운터는 0으로 재설정된다. 카운터는 또한 코드워드 비트들 중 하나가 값을 변경시킬 때마다 0으로 재설정되는데, 이는 이전에 계산된 신드롬 비트들이 이제 더 이상 유효하지 않기 때문이다. 카운터가

에 도달하는 경우(

은 코드워드가 만족시켜야만 하는 패리티-체크 방정식들의 개수이며, 이는

의 차원(dimension)임을 상기하기 바람), 수렴이 검출되고 디코딩은 종료된다.

이러한 세미-온-더-플라이 수렴 검출 메커니즘은 약간의 추가적인 복잡함을 유발한다. 그러나, 디코더가 유효 코드워드로 수렴한 이후 전체 반복에 대해서 수렴을 검출하기 때문에 이것은 지연된 수렴 검출을 제공한다. 그 이유는, 만족된 패리티-체크들의 전체 개수가, 플립핑될 마지막 비트가 자신의 값을 플립핑시킨 이후 카운팅되기 때문이다(값의 플립핑은 카운터를 재설정하기 때문임). 데이터가 저장된 이후 그리고/또는 플래시 메모리가 다수의 기입/소거 싸이클들을 겪은 이후 오래된 후에 플래시 메모리로부터 판독된 데이터를 디코딩하는 것과 같이 에러가 높은 상황에서, 수 번의 반복들(예를 들어, 10번 이상의 반복들)이 수렴을 위해 요구될 수 있고, 이에 따라 마지막 비트가 플립핑된 이후 한 번의 반복을 더 추가하는 것은 수렴 시간을 10% 혹은 그 이하로 증가시킬 수 있다. 그러나, 갱신된 플래시 메모리와 같은 에러가 낮은 상황에서, 한번 혹은 두 번의 반복들은 코드워드를 디코딩하기에 충분할 수 있는바, 이에 따라 마지막 비트가 플립핑된 이후 전체 반복을 추가하는 것은 디코딩 시간을 50% 내지 100% 증가시킬 수 있다.

실시간, "온-더-플라이(on-the-fly), 수렴 테스팅이 제공될 수 있다. 이러한 실시간 수렴 테스팅은 판독 쓰루풋(read throughputs)을 향상시키기 위해 SSD 및 i-NAND와 같은 애플리케이션들에 대해 사용될 수 있다. 실시간 수렴 테스팅은 매우 빠른 디코더들로부터 혜택을 받을 수 있는 랜덤 I/O 성능에서 사용될 수 있다. 더욱이, 랜덤 I/O 성능은 플래시 메모리가 갱신되고(낮은 싸이클링) 그 에러율이 낮을 때 측정될 수 있다. 이러한 경우에, 디코더는 단지 한 번 혹은 두 번의 반복들 이후에만 유효한 코드워드로 수렴할 수 있다. 이 경우에 있어서, 세미-온-더-플라이 수렴 검출 방법과 같은 수렴 검출 방법을 사용하는 것은 대략 한 번의 반복의 지연을 유발시키는바, 이것은 디코딩 시간을 대략 50% 내지 100%만큼 증가시키고, 이는 랜덤 I/O 성능을 저하시킬 수 있다.

복수의 코드워드 비트들을 포함하는 코드워드의 표현을 디코딩하는 방법은: (a) 코드워드 비트들의 각각의 추정들이 스케쥴에 따라 업데이트되는 반복적 디코딩 알고리즘의 적어도 한 번의 반복 동안, 알고리즘의 종료 표시를 계산하는 것, 그리고 (b) 디코딩을 종료할지 여부를 결정하기 위해 종료 표시를 테스팅하는 것을 포함할 수 있는바, 여기서 종료 표시의 테스팅은 스케쥴의 바로 이전 트래버싱 동안 플립핑된 코드워드 비트들의 각각의 추정들 중 적어도 하나의 추정에도 불구하고 디코딩의 종료 여부를 제시한다.

복수의 코드워드 비트들을 포함하는 코드워드의 표현을 디코딩하기 위한 디코더는: (a) 코드워드 비트들의 각각의 추정들이 스케쥴에 따라 업데이트되는 반복적 디코딩 알고리즘의 적어도 한 번의 반복 동안, 알고리즘의 종료 표시를 계산하는 것, 그리고 (b) 디코딩을 종료할지 여부를 결정하기 위해 종료 표시를 테스팅하는 것을 행하기 위한 회로를 포함할 수 있는바, 여기서 종료 표시의 테스팅은 스케쥴의 바로 이전 트래버싱 동안 플립핑된 코드워드 비트들의 각각의 추정들 중 적어도 하나의 추정에도 불구하고 디코딩의 종료 여부를 제시한다.

복수의 코드워드 비트들을 포함하는 코드워드의 표현을 디코딩하는 방법은, 반복적 디코딩 알고리즘의 적어도 한 번의 반복 각각 동안: 코드워드 비트들 중 적어도 하나의 코드워드 비트의 각각의 추정의 플립핑에 응답하여: (a) 코드워드 비트들의 추정들의 신드롬에 따라 달라지는 종료 표시를 업데이트하는 것(여기서 신드롬은 복수의 신드롬 비트들을 포함함); 그리고 (b) 종료 표시를 테스팅하는 것을 포함할 수 있다.

복수의 코드워드 비트들을 포함하는 코드워드의 표현을 디코딩하기 위한 디코더는, 반복적 디코딩 알고리즘의 적어도 한 번의 반복 각각 동안: 코드워드 비트들 중 적어도 하나의 코드워드 비트의 각각의 추정의 플립핑에 응답하여: (a) 코드워드 비트들의 추정들의 신드롬에 따라 달라지는 종료 표시를 업데이트하는 것(여기서 신드롬은 복수의 신드롬 비트들을 포함함); 그리고 (b) 종료 표시를 테스팅하는 것을 행하기 위한 회로를 포함할 수 있다.

복수의 코드워드 비트들의 포함하는 코드워드의 표현이 디코딩될 수 있다. 디코딩되는 것은 코드워드의 "표현(representation)"이지, 실제 코드워드가 아닌데, 왜냐하면 디코딩되는 것은 노이즈로 오염될 수 있는 코드워드이기 때문이며, 이에 따라 이제 더 이상 유효한 코드워드가 아니기 때문이다. 예를 들어, 플래시 메모리와 같은 비휘발성 메모리에 하나 이상의 코드워드들로서 저장되어 있지만, 시간 경과에 따라 플래시 메모리의 저하로 인해 변경되거나 혹은 메모리로부터 데이터를 판독하는 프로세스에 의해 변경된, 데이터를 복원하기 위한 애플리케이션이 존재할 수 있다. 노이즈가 있는 전송 채널을 통해 전송된 코드워드에 누적된 에러들을 정정하기 위한 또 다른 애플리케이션이 존재할 수 있다. 만약 이러한 방법들에 대한 입력이 유효 코드워드라면, 디코딩의 필요성이 없을 수 있다.

코드워드 비트들의 추정들을 업데이트하기 위해 앞서 설명된 바와 같은 스케쥴을 따르는 반복적 디코딩 알고리즘의 한 번 이상의 반복들 동안, 알고리즘의 종료 표시가 계산될 수 있다. 종료 표시가 반복 "동안" 계산된다는 것의 의미는, 종료 표시를 발생시키는 계산들 중 적어도 일부가 반복의 모든 스케쥴링된 코드워드 비트 추정 업데이트들이 완료되기 전에 수행됨을 의미한다. 코드워드 비트 추정을 "업데이트"하는 것의 의미는, 추정을 향상시키도록 의도된 추정에 관한 동작들을 수행하는 것을 의미한다.

이러한 동작들은 추정을 플립핑시킬 수 있거나 혹은 플립핑시키지 않을 수 있다. 예를 들어, LLR 추정을 업데이트하는 것은 추정의 부호를 변경시킴 없이 오로지 추정의 크기만을 변경시킬 수 있다.

종료 표시는 알고리즘이 수렴하지 않을 확률이 높은지 여부를 결정하기 위해 테스팅되는 발산 표시 혹은 유효 코드워드를 생성함으로써 알고리즘이 수렴했는지 여부를 결정하기 위해 테스팅되는 수렴 표시일 수 있다. 종료 표시의 계산은, 테스팅을 바로 진행시키는 스케쥴의 트래버싱 동안 코드워드 비트 추정들 중 하나 이상이 플립핑되었음에도 불구하고 디코딩을 종료할지 여부를 테스팅이 제시하도록 하는 그러한 것이다. 스케쥴의 "트래버싱"은 스케쥴 내의 임의의 포인트에서 시작하여 해당 스케쥴 내의 바로 그 포인트로 되돌아오는 것을 의미한다. 만약 포인트가 스케쥴의 끝에 혹은 시작에 있다면, 트래버싱은 반복과 동등하며, 만약 그렇지 않다면 트래버싱은 두 번의 반복들 사이의 경계(boundary)를 크로싱(crossing)한다.

종료 표시가 수렴 표시인 경우에, 종료 표시는 반복 이후가 아닌 반복 동안에 계산될 수 있다. 코드워드 비트 추정들 중 하나 이상의 코드워드 비트 추정의 최근 플립핑들에도 불구하고 수렴이 표시될 수 있다.

만약 종료 표시의 테스팅이 알고리즘이 수렴함을 표시한다면, 디코딩은 종료될 수 있다. 추가적으로 혹은 대안적으로, 종료 표시의 테스팅이 알고리즘이 수렴하지 않을 확률이 높음을 표시하는 경우, 디코딩은 종료될 수 있다.

반복 동안 종료 표시의 테스팅은 적어도 코드워드 비트 추정이 플립핑될 때마다 실행될 수 있다.

종료 표시의 계산은 에러 정정 신드롬의 복수의 비트들 모두에 대해 OR 연산을 행하는 것을 포함할 수 있다.

만약 코드워드가, 코드워드 비트 추정들의 에러 정정 신드롬이 정의되는, 바이너리 선형 블록 코드와 같은, 코드의 코드워드라면, 종료 표시는 에러 정정 신드롬의 가중치를 포함할 수 있다. 종료 표시의 테스팅은 에러 정정 신드롬의 가중치를 임계치와 비교하는 것을 포함할 수 있다. 수렴 검출에 대해, 임계치는 0이다.

종료 표시의 계산은, 코드워드 비트 추정들 중 하나의 코드워드 비트 추정이 플립핑된 것에 응답하여, 그 코드워드 비트 추정에 의해 영향을 받은 에러 정정 신드롬의 모든 비트를 플립핑시키는 것을 포함할 수 있다. 에러 정정 신드롬 비트는 코드워드 비트 추정에 의해 영향을 받는다(만약 코드워드 비트가 그 에러 정정 신드롬 비트의 패리티 체크 방정식에 관여하고 있다면). 종료 표시의 계산은, 코드워드 비트 추정들 중 하나의 코드워드 비트 추정이 플립핑된 것에 응답하여, 플립핑된 코드워드 비트 추정에 의해 영향을 받은 에러 정정 신드롬 비트들의 플립핑들에 따라 에러 정정 신드롬 가중치를 업데이트하는 것을 포함할 수 있다. 코드워드 비트 플립핑에 의해 영향을 받은 에러 정정 신드롬의 비트(들)의 플립핑, 그리고/또는 에러 정정 신드롬 가중치의 업데이트는, 에러 정정 신드롬 가중치의 업데이트를 트리거(trigger)시키는 코드워드 비트 플립핑과 실질적으로 동시에 일어날 수 있다. 대안적으로, 코드워드 비트 플립핑에 의해 영향을 받은 에러 정정 신드롬의 비트(들)의 플립핑, 그리고/또는 에러 정정 신드롬 가중치의 업데이트는, 에러 정정 신드롬의 업데이트를 트리거시키는 코드워드 비트 플립핑 이후에 후속하여 실행되도록 스케쥴링될 수 있다. 이러한 스케쥴링은 코드워드 비트 플립핑에 의해 영향을 받은 모든 에러 정정 신드롬 비트를 플립핑시키도록 하는 요청을 FIFO 버퍼와 같은 큐잉 버퍼(queuing buffer)에 저장하는 것을 포함할 수 있다. 만약 큐잉 버퍼가 오버플로우(overflow)된다면, 디코딩 방법은 앞서 설명된 디코딩 종료 방법들 중 또 다른 것으로 리버팅(reverting)할 수 있다. 에러 정정 신드롬은 알고리즘의 반복들 중 임의의 반복 이전에 초기화될 수 있다. 대안적으로, 종료 표시가 계산되는 동안인 반복들은 알고리즘의 제 1 반복 이후에 모두 존재할 수 있고, 에러 정정 신드롬은 알고리즘의 제 1 반복 동안 초기화될 수 있다. 이러한 초기화는 제 1 반복에서의 코드워드 비트 추정들의 플립핑에 응답하여, 에러 정정 신드롬 비트들의 사전에 스케쥴링된 플립핑과 결합될 수 있고 이러한 플립핑과 실질적으로 동시에 일어날 수 있다.

종료 표시가 계산되는 동안인 각각의 반복 동안, 코드워드 비트 추정들의 체크섬 신드롬의 적어도 부분적 업데이트가 계산될 수 있다.

복수의 코드워드 비트들을 포함하는 코드워드의 표현을 디코딩하기 위한 방법을 구현하는 디코더는 이러한 방법을 구현하기 위한 회로를 포함할 수 있다.

이러한 회로는 에러 정정 신드롬의 복수의 비트들 모두를 계산하기 위한 복수의 XOR 게이트들, 그리고 XOR 게이트들의 출력들을 결합시키기 위한 OR 게이트를 포함할 수 있다.

코드워드 비트 추정들의 에러 정정 신드롬이 정의되는, 바이너리 선형 블록 코드와 같은 그러한 코드에 대해, 종료 표시는 에러 정정 신드롬의 가중치를 포함할 수 있다. 종료 표시의 테스팅은, 에러 정정 신드롬의 가중치를 임계치와 비교하는 것을 포함할 수 있고, 종료 표시의 계산은, 코드워드 비트 추정들 중 하나의 코드워드 비트 추정이 플립핑된 것에 응답하여, 그 코드워드 비트 추정에 의해 영향을 받은 에러 정정 신드롬의 모든 비트의 부호를 변경시키는 것을 포함할 수 있다. 수렴 검출에 대해, 임계치는 0이다. 회로는 코드워드 비트 추정들의 플립핑에 응답하여 에러 정정 신드롬의 가중치와 에러 정정 신드롬의 비트들 양쪽 모두를 업데이트하기 위한 에러 정정 신드롬 업데이트 블록을 포함할 수 있다. 회로는 에러 정정 신드롬의 비트들을 저장하기 위한 복수의 레지스터(register)들을 포함할 수 있고, 이에 따라 에러 정정 신드롬 비트들의 업데이트 및 에러 정정 신드롬 가중치의 업데이트는 코드워드 비트들의 업데이트와 동시에 일어날 수 있다. 대안적으로, 회로는 에러 정정 신드롬의 비트들을 저장하기 위해 이러한 레지스터들 대신에 랜덤 액세스 메모리를 포함할 수 있고, 그리고 에러 정정 비트들의 업데이트와 에러 정정 신드롬 가중치의 업데이트를 스케쥴링하기 위해 FIFO 버퍼와 같은 큐잉 버퍼를 포함할 수 있는데, 왜냐하면 만약 코드워드 비트 추정들의 단지 작은 부분만이 업데이트시 플립핑될 것으로 예측된다면, 에러 정정 신드롬 비트들의 업데이트 및 에러 정정 신드롬 가중치의 업데이트가 코드워드 비트들의 업데이트와 비교하여 지연될 수 있기 때문이다.

디코더는, 종료 표시가 계산되는 디코딩 알고리즘의 각각의 반복 동안, 코드워드 비트 추정들의 체크섬 신드롬의 적어도 부분적 업데이트를 실행시키기 위한 회로를 포함할 수 있다.

코드워드 비트 추정들의 신드롬에 따라 달라지는 종료 표시를 업데이트함으로써, 그리고 업데이트된 종료 표시를 테스팅함으로써, 반복적 디코딩 알고리즘의 반복 동안 코드워드 비트의 추정의 플립핑에 응답할 수 있다. 종료 표시는 알고리즘이 수렴하지 않을 확률이 높은지 여부를 결정하기 위해 테스팅되는 발산 표시 혹은 유효 코드워드를 생성함으로써 알고리즘이 수렴했는지 여부를 결정하기 위해 테스팅되는 수렴 표시일 수 있다. 종료 표시가 수렴 표시인 경우에, 수렴 표시는 반복을 끝내는 것에 응답하는 것이 아니라 코드워드 비트 플립핑에 응답하여 업데이트될 수 있으며, 수렴 표시는 코드워드 비트 플립핑에 응답하여 재설정되는 것이 아니라 업데이트될 수 있다.

만약 테스팅이 알고리즘이 수렴함을 제시한다면, 디코딩은 종료될 수 있다. 추가적으로 혹은 대안적으로, 테스팅이 알고리즘이 수렴할 확률이 낮음을 표시하는 경우, 디코딩은 종료될 수 있다.

종료 표시는 코드워드 비트 추정의 플립핑, 그리고 그 코드워드 비트 추정에 의해 영향을 받은 각각의 신드롬 비트의 플립핑 이전에, 신드롬의 가중치에 따라 달라질 수 있다.

업데이트 및 테스팅은 반복을 계속 행하기 이전에 실행될 수 있다. 예를 들어, 만약 반복적 디코딩 알고리즘이, 각각의 반복에서 모든 패리티-체크 노드들을 트래버싱하는 LDPC 메시지 패싱 알고리즘이라면, 그리고 코드워드 비트 추정이 패리티-체크 노드들 중 하나와 관련된 메시지 패싱의 결과로서 플립핑될 수 있다면, 임의의 메시지가 임의의 후속 패리티-체크 노드들로부터 패싱되기 이전에 종료 표시는 업데이트 및 테스팅된다.

실시간 수렴 검출은 반복적 디코더들 내에서 구현될 수 있다. 신드롬 벡터 및 신드롬 가중치의 디코딩 동안 플립핑된 각각의 코드워드 비트의 영향은 플립핑된 비트가 관여하고 있는 패리티 체크들에 대응하는 모든 신드롬 비트들을 플립핑시킴으로써 실시간으로(혹은 거의 실시간으로) 계산될 수 있다.

실시간 수렴 검출의 구현이 도 2에서 제시된다. 각각의 패리티 체크 방정식이 XOR 게이트(30)에 의해 표현되는바, XOR 게이트(30)의 입력들은 패리티-체크 방정식에 관여하고 있는 비트들의 현재 비트 추정들(도 2에서 원(circles)으로서 표현됨)이다. 각각의 체크 방정식 XOR 게이트(30)는 신드롬 비트들 중 하나를 출력한다. 수렴 검출 신호를 생성하기 위해 신드롬 비트들에 관한 OR 연산이 수행된다. 수렴 검출 신호가 0과 동일하게 되는 경우, 비트 추청들은 유효 코드워드를 구성하고 디코딩은 종료될 수 있다.

도 2에 도시된 구현예는 신드롬 비트들을 계산하는 복합 상호연결 계층(complex interconnect layer)(이것은 긴 코드들에 대해 구현하기 어려울 수 있음)을 포함할 수 있다. 반복적 코딩 방식들에서 사용되는 코드들은 일반적으로 희소 패리티 체크 행렬들(sparse parity check matrices)에 근거하고 있음(따라서, 그 명칭이 "저밀도(Low-Density)" 패리티-체크 코드들(Parity-Check codes)임)에 유의해야 한다. 이것이 의미하는 바는 각각의 비트가 작은 개수의 패리티-체크 방정식들(대게 평균적으로 3개 내지 6개의 패리티 체크들)에 관여하고 있음을 의미한다. 이것은 또한 신드롬 비트들을 계산하기 위해 사용되는 상호연결 계층을 간략화시킨다. 반면, 반복적 코딩 방식들은 일반적으로, 매우 긴 코드들에 기반을 두고 있다. 따라서, 전체적으로, 상호연결 계층은 도 2에 예시된 구현예에 대해서 너무 복합적일 수 있다.

도 2의 복합 상호연결 계층을 요구하지 않는, 실시간 수렴 검출 블록을 구현하기 위한 회로가 도 3에 제시된다. 도 3의 디코더(40)는 도 2의 수렴 검출 블록(22) 대신에 수렴 검출 블록(42)이 사용되었다는 점을 제외하고 도 1의 디코더(10)와 동일할 수 있다.

가 비트들(이들의 "소프트(soft)" 비트 추정들은 디코더의

개의 프로세싱 유닛들(18)에 의해 현재 업데이트됨)의 세트의 인덱스들(indices)을 표시한다고 하자.

및

는, 프로세싱 유닛들에 의한 업데이트 이전 및 업데이트 이후, 이러한 비트들의 "소프트" 비트 추정들을 각각 나타낸다고 하자.

및

는,

및

의 그 대응하는 "하드(hard)" 결정들(즉, 0/1 비트 값들)을 각각 나타낸다고 하자.

는 비트 플립핑 표시자(bit flip indicator)들(즉, 대응하는 비트가 그 값을 플립핑한 경우

이고, 그렇지 않으면 0임)의 열 벡터(column vector)를 나타낸다고 하자.

는 (열 벡터로서) 신드롬 벡터를 나타내고,

는 신드롬 가중치 카운터를 나타낸다고 하자. 수렴 검출 블록(42)은 다음과 같이 동작한다:

(1) 신드롬 벡터

및 신드롬 가중치 카운터

는 디코딩 이전에 0으로 재설정된다.

(2) 초기 선험적 비트 추정들에 근거하여 디코더 초기화 동안 초기 신드롬 벡터 및 초기 신드롬 가중치가 계산된다.

비트 추정들의 새로운 세트가 프로세싱 유닛들(18)에 계산될 때마다(예를 들어 각각의 클럭(clock)마다), 신드롬 벡터

및 신드롬 가중치 카운터

가 이에 따라 업데이트된다. 이것은 신드롬 벡터 업데이트 블록(44)에 의해 행해지는바, 이 블록(44)은 (

내에서의 인덱스들을 갖는) 비트들의 현재 세트가 관여하고 있는 패리티-체크 제약들에 대응하는 신드롬 비트들의 관련 세트를 업데이트한다.

신드롬 벡터는 (임의 개수의 신드롬 비트들의 액세스 및 업데이트를 동시에 허용하기 위해) 레지스터들의 어레이(array)(46)에 저장된다. S-ROM(48)은 코드의 패리티-체크 행렬

의 열(columns)을 저장한다. 이러한 경우에, 신드롬 벡터 업데이트 블록(44)은

와 같은 신드롬 벡터를 업데이트하는바, 여기서

는 코드의 패리티-체크 행렬

의

소행렬이며, 이것은

내에서의 인덱스들을 갖는 열(column)만을 포함한다. 대안적으로,

인바, 여기서

은 부호를 플립핑한 비트들(즉,

인 비트들))의 인덱스들만을 포함하는 인덱스 세트

의 서브세트이다.

반복적 코딩 방식에 있어서, LDPC 코드들에 근거하는 것들처럼, 패리티-체크 행렬

는 희소 행렬이고,

의 열에서의 1의 평균 개수는 적으며(전형적으로는 3개 내지 6개), 반면,

의 차원

은 몇백 혹은 몇천이거나 그 이상일 수 있음(즉, 비트는 코드의

개의 패리티-체크들 중에서 3개 내지 6개의 패리티 체크들에만 평균적으로 관여함)에 유의해야 한다. 따라서, S-ROM(48)에

의 열들을 저장하는 대신에, 각각의 코드워드 비트가 관여하는 신드롬 비트들의 인덱스들만을 저장하는 것이 두 가지 측면(즉, S-ROM 크기 그리고 신드롬 벡터 업데이트 복잡도)에서 더 효율적일 수 있다. 이처럼, 코드워드 비트 인덱스들의 세트

가 주어지는 경우, S-ROM(48)은 (코드워드 비트들이 관여하는 패리티-체크들에 대응하는) 신드롬 비트 인덱스들의 세트

를 출력한다. 더욱이, LDPC 코드들(예를 들어, 준-순환 LDPC 코드들)을 사용하는 것이 일반적인바, 이것의 패리티-체크 행렬

는 동시에 프로세싱되는 비트들의 각각의 세트가 공통 패리티-체크들에 관여하지 않도록 정렬된다. 달리 말하면,

인 경우

이다. 이러한 경우에, 신드롬 벡터 업데이트는

과 같은 관련 신드롬 비트들을 플립핑시킴으로써 간단히 행해질 수 있는바, 여기서

는 인덱스들

를 갖는

에서의 신드롬 비트들의 서브세트를 나타낸다.

신드롬 가중치는 신드롬 벡터의 업데이트와 함께 업데이트된다. 신드롬 가중치는 신드롬 벡터의 원소들의 합이다. 신드롬 가중치는 점진적 방식:

으로 업데이트될 수 있는바, 여기서

은 현재 신드롬 벡터 업데이트 단계에서 0에서 1로 플립핑된 신드롬 비트들의 개수이고,

은 현재 신드롬 벡터 업데이트 단계에서 1에서 0으로 플립핑된 신드롬 비트들의 개수이다.

이 되는 경우, 이것은 신드롬 벡터가 0으로 됨을 표시함과 아울러 디코더가 유효 코드워드로 수렴함을 표시하기 때문, 디코딩은 종료된다.

신드롬 벡터의 초기화는 다음과 같이 수행될 수 있는바, 즉 디코딩 이전에 신드롬 벡터가 0으로 재설정 및 초기화된다. 그 다음에, 초기 신드롬 벡터가 디코더 초기화 동안 계산될 수 있고, 비트 추정 RAM(12)은 초기 선험적 "소프트" 비트 추정들로 채워지게 된다. 이것은 도 4에서 제시된 바와 같이 도 3의 신드롬 벡터 업데이트 블록(44)을 사용하여 행해질 수 있다. 초기화 동안, 신드롬 벡터 업데이트 블록(44)은 선험적 비트 추정들의 벡터에 의해 구동되고, 디코딩 동안, 신드롬 벡터 업데이트 블록(44)은 비트 플립핑들의 벡터에 의해 구동된다. 도 4와 관련하여 모든 비트 인덱스들

는 "현재(current)" 비트 인덱스들임에 유의해야 한다. 도 4와 관련하여 또한 유의해야 하는 것으로, 파라미터 "

"는 비트 추정 RAM(12)에 동시에 로딩(loading)되는 선험적 "소프트" 비트 추정들의 개수를 나타낸다.

도 3의 실시간 수렴 검출 블록(42)은 도 2의 실시간 수렴 검출 회로보다 더 적은 전력을 소비하고 덜 복잡하다. 그러나 수렴 검출 블록(42)은 또한 여전히 상대적으로 높은 구현 복잡도를 가질 수 있다. 주된 이유는 많은 신드롬 비트들이 동시에 업데이트될 필요가 있을 수 있기 때문이다. 결과적으로, 신드롬 벡터는 (동시에 하나 혹은 최대 두 개의 어드레스에 대한 액세스 허용하는) 저비용 RAM에 저장돼서는 안 되며, 대신에,

개의 레지스터들의 어레이(46)에 저장돼야 한다(여기서

은 대략 몇백 혹은 몇천이거나 그 이상일 수 있음). 더욱이, 다수 개의 동시에 수행되는 XOR 연산들이 필요하다(최대

개의 XOR 연산들을 요구하는

). 대안적으로, 소수 개의 동시에 수행되는 NOT 연산들이 수행될 수 있지만(

), 전체

개의 신드롬 비트들 중에서 소수 개의 신드롬 비트들(이것의 인덱스들은

임)을 선택하기 위한 커다란 먹싱 계층(MUXing layer)이 구현돼야만 한다.

도 3의 실시간 수렴 검출 블록(42)의 복잡도 및 전력 소비를 감소시키기 위해, 도 5에서 제시되는 다른 시스템이 사용될 수 있다. 도 5의 디코더(50)는 수렴 검출 블록(42) 대신에 수렴 검출 블록(52)이 사용되었다는 점을 제외하고 도 3의 디코더(40)와 동일할 수 있다. 희소 패리티-체크 행렬의 디코딩 동안, 비트 플립핑들의 평균 빈도는 매우 낮다. 평균적으로, 플래시 메모리들에서의 일반적인 비트 에러율에서. 비트는 매 10 내지 20개의 디코딩 클럭마다 한번 플립핑될 수 있다. 여전히 수 개의 비트들이 동시에(즉, 단일 클럭에서 혹은 연속적인 클럭에서) 플립핑되는 버스트(burst)가 존재할 수 있지만, 이러한 일이 일어날 확률은 낮다. 이제, 신드롬 벡터가 업데이트된 상태를 유지시키기 위해 각각의 비트 플립핑은 (패리티-체크 행렬의 희소성(sparseness)으로 인해) 몇 개의 신드롬 비트들만을 업데이트할 것을 요구한다. 따라서, 비트 플립핑들이 낮은 빈도에서 일어나기 때문에, FIFO 버퍼(54)는 비트 플립핑 "요청(requests)"을 저장 및 관리하기 위해 사용될 수 있고, 이에 따라 신드롬 벡터 업데이트는 낮은 빈도로 행해진다(한 번에 하나 혹은 몇 개(예를 들어,

개)의 신드롬 비트들이 업데이트됨). 이러한 접근법의 장점은 복잡도가 매우 낮고 전력 소비도 낮은 실시간 수렴 검출이다. 더 구체적으로, 도 5에 도시된 해법은 레지스터들의 어레이에 신드롬 벡터를 저장하지 않는바, 한 개 혹은 몇 개(

개)의 비트들이 한번에 업데이트되기 때문에 신드롬 벡터는 (도 5에서 S-RAM(56)으로서 도시된) 저비용 RAM에 저장될 수 있다. 더욱이, 단지 한 개 혹은 몇 개(예를 들어,

개)의 신드롬 비트들만이 한번에 플립핑되기 때문에, 커다란 머싱 계층이 필요 없고, 로직(logic)의 양은 매우 낮다. 수렴 검출 블록(52)의 신드롬 벡터 업데이트 블록(45)은, 레지스터들(46) 대신에, FIFO 버퍼(54)로부터의 요청들에 응답하여 SRAM(56)에서의 신드롬 비트들을 조작하기 위해 수정된, 수렴 검출 블록(42)의 신드롬 벡터 업데이트 블록(44)이다.

도 5의 수렴 검출 블록(52)에 따르면, 프로세싱 유닛들(18)에 의해 업데이트된

개 소프트 비트 추정들의 세트 내에서 비트 플립핑이 식별될 때마다, 적절한 신드롬 비트들을 플립핑하기 위한 요청이 FIFO 버퍼(54)에 삽입된다. 이러한 요청은 요청을 발생시킨 비트들의 현재 그룹의 인덱스들(혹은 인덱스)과, 그리고 플립핑된

개 비트들(예를 들어,

개의 표시자 비트들) 중 어떤 것의 사양(specification)을 포함한다. 신드롬 벡터 업데이트 블록(45)은 FIFO 버퍼(54)가 비어 않는 경우, 하나씩 FIFO 버퍼(54)내의 요청을 핸들링(handling)한다. 각각의 요청은 수 개의 프로세싱 클럭에서 핸들링될 수 있다. 예를 들어, 만약 요청을 발생시킨 플립핑된 비트(혹은

개의 동시에 프로세싱된 비트들의 세트 내에서의 플립핑된 비트들)가

개 패리티-체크들에 관여하고 있다며, 요청은

개의 클럭에서 핸들링될 수 있고, 이에 따라 각각의 클럭에서 S-ROM(48)은 S-RAM(56) 내의 하나의 신드롬 비트(혹은

개의 신드롬 비트들의 일 세트)의 어드레스

를 출력하게 되는바, 이는 비트(들)가 관여하는

개 패리티-체크들 중 하나에 대응한다. 어드레스(들)에서의 신드롬 비트(들)는 FIFO 버퍼(54)에 저장된 표시자 벡터에 따라 업데이트된다(예를 들어,

). 추가적으로, 신드롬 가중치는 점진적으로(

) 업데이트되는바, 여기서

은 업데이트된 S-RAM 어드레스(들)

에서 0에서 1로 플립핑된 신드롬 비트들의 개수이고,

은 업데이트된 S-RAM 어드레스(들)

에서 1에서 0으로 플립핑된 신드롬 비트들의 개수이다.

비트 플립핑 요청들(이들 각각은 프로세싱을 위해 수 개의 클럭을 요구할 수 있음)의 "버스트(burst)"의 경우에 있어, FIFO 버퍼(54)의 오버플로우를 피하기 위해서, 충분히 큰 FIFO 버퍼(54)가 할당돼야만 한다. 대안적으로, 더 작은 FIFO 버퍼(54)가 사용될 수 있으며, FIFO 버퍼(54)의 오버플로우가 일어나는 경우(확률은 낮음), 실시간 수렴 검출 블록(52)은 비활성화될 수 있다. 이러한 경우에, 디코더(50)는 최대 횟수의 반복까지 실행될 수 있거나 또 하나의 다른 종래의 수렴 검출 방법으로 리버팅할 수 있다.

S-RAM(56) 내에서의 신드롬 벡터의 초기화는 디코더(50)의 초기화 동안 도 4에서 제시된 바와 같이 행해질 수 있고, 비트 추정 RAM(12)은 초기 선험적 "소프트" 비트 추정들로 채워지게 된다. 초기 신드롬 벡터는 제 1 디코딩 반복 동안 한 개 혹은 몇 개(예를 들어,

개)의 신드롬 비트들에 대해 한번에 계산될 수 있는데, 왜냐하면 제 1 디코딩 반복 동안 모든 패리티-체크들이 어떻게 해서든 프로세싱되기 때문이다. 예를 들어, 직렬 업데이트 스케쥴에 따라 동작하는 디코더를 고려하는 경우, 여기서, 코드의 패리티-체크들은

개의 패리티-체크들의 일 세트씩 차례로 프로세싱되고, 이에 따라

개의 비트들을 포함하는 패리티-체크는

개의 클럭에서 프로세싱되게 된다. 이러한 경우에, 신드롬 벡터 초기화 다음과 같이 행해지는 바, 즉 디코딩 이전에 신드롬 벡터 저장소(즉, S-RAM(56))가 0으로 초기화된다. 그 다음에 제 1 디코딩 반복 동안, 각각의

개 클럭 이후에

개의 신드롬 비트들의 추가적인 세트(도 5에서의

)가 계산되고, 신드롬 벡터 및 신드롬 가중치 카운터가 이에 따라 업데이트된다. 즉,

인바, 여기서

은 매

개의 클럭마다 하나씩 증분되는 직렬 어드레스 카운터이다. 제 1 반복 동안 S-RAM(56)은 두 개의 소스들: (1) 신드롬 비트 발생 소스(generate syndrome bits source)(

) 및 (2) 플립핑 비트 추적 소스(track flip bits source)(

)에 의해 업데이트됨에 유의해야 한다. 제 1 반복이 끝나는 경우, 신드롬 벡터 및 신드롬 가중치 카운터는 유효하다. 그 포인트로부터 계속해서, 플립핑 비트 추적 소스만이 신드롬 벡터 및 신드롬 가중치 카운터를 업데이트하고, 신드롬 가중치 카운터가 0에 도달하는 경우 수렴이 검출되고 디코딩은 종료된다.

제 1 디코딩 반복 동안 신드롬 벡터를 업데이트시키는 두 개의 소스들이 존재하기 때문에, 플립핑 비트 추적 소스는 이전에 프로세싱된 패리티-체크들의 신드롬 비트들만을 업데이트해야 한다는 것에 유의해야 한다. 제 2 반복으로부터 시작하여 디코딩 종료까지, 플립핑 비트 추적 소스는 모든 신드롬 비트들을 업데이트한다.

이러한 낮은 복잡도의 신드롬 벡터 초기화 접근법에 따라, 수렴 검출 블록(52)은 제 1 디코딩 반복이 끝난 이후에만 빠른 수렴 검출기로서 유효하게 된다. 그러나, 디코더(50)는 어쨌든 (에러들의 개수가 0 혹은 거의 0이 아니라면) 하나의 반복보다 더 적은 반복에서 수렴할 것으로 예측되지 않는다.

지금까지, 수렴 검출 블록들(42 및 52)의 사용은, 이들의 명칭이 시사하는 바와 같이, 수렴의 이른 검출을 위해 설명되었다. 수렴 검출 블록들(42 및 52)을 수정하면 이들은 발산 검출 블록들이 된다.

를 0과 비교하는 대신에,

는 0이 아닌 임계치와 비교된다. 전형적으로, 이러한 임계치는 바로 이전 반복에서 대응하는 포인트에서의

의 값이다. 대안적으로, 이러한 임계치는, 반복적 디코딩이 수렴할 것으로 예측되는 경우 반복적 디코딩에서

가 소정의 포인트에서 초과하지 않을 것으로 예측되는 값일 수 있다.

도 1 내지 도 5의 시스템들은 또한 체크섬의 빠른 테스팅을 위해 사용될 수 있다. 체크섬은 에러 검출을 위해 사용되는 코드이다. 에러 정정 코드(Error Correcting Codes)와 함께 구현되는 경우, 시스템은 검출된 에러에 대해서는 10^-14보다 작은 에러율을 달성할 수 있고, 비검출된 에러에 대해서는 10^-20보다 작은 에러율을 달성할 수 있다. 체크섬 및 ECC를 사용하는 인코더가 도 6에 예시된다. 도 6에서, 체크섬 인코더의 출력은 체크섬과 서로 연결된 정보 비트들로 구성된 부분적 코드워드이고, ECC 인코더의 출력은 ECC 패리티 비트들과 서로 연결된 부분적 코드워드로 구성된 전체 코드워드이다.

체크섬은 순환 리던던시 코드(Cyclic Redundancy Code, CRC)를 사용하여 구현될 수 있다. CRC는 에러의 특정 패턴들의 검출을 보장하는 순환 코드이다. CRC에 의해 검출된 패턴들은 모든 홀수 개의 에러들, 소정의 버스트 길이까지의 버스트 에러, 하나 이상의 다른 타입의 에러, 또는 이들의 임의의 조합을 포함할 수 있다.

CRC는, 다항식(polynomial)

에 정보 비트들을 인베딩(embedding)시키고, 코드 다항식

를 발생시키기 위해 특정 다항식 링(polynomial ring) 내에서 생성 다항식(generator polynomial)

에 의한 곱셈(multiplying)을 행함으로써 인코딩될 수 있다.

CRC는 신드롬을 계산함으로써 에러 검출을 위해 사용될 수 있는바, 이는 코드 다항식(code polynomial)

의 표현과 체크 다항식(check polynomial)

을 곱하는 것으로 간략하게 수행되며, 만약 (다항식 링에서)

이라면 성공(success)이 선언(declare)된다. 다항식 곱셈을 통해 CRC의 신드롬을 계산하는 프로세스는 종래의 ECC 디코딩 동안 온-더-플라이로 수행될 수 없다. 대신에 이것은 ECC 디코더가 끝난 이후 수행될 수 있으며, 이에 따라 추가적인 디코딩 레이턴시(decoding latency)를 발생시킨다. 이러한 추가적인 레이턴시를 피하기 위해, 본 명세서에서 설명되는 실시간 신드롬 계산 방법이 실시간, 온-더-플라이, 체크섬 계산에 적용될 수 있다.

ECC 패리티-체크 행렬

가 코드워드(도 6의 ECC 인코더의 출력)에 대해 정의되는 것과 같이, 그렇게 체크섬 패리티-체크 행렬도 도 6의 체크섬 인코더로부터 출력된 부분적 코드워드에 대해 정의될 수 있다. 실시간 에러 검출을 행하기 위해, 체크섬 패리티-체크 행렬은 ECC의 패리티-체크 행렬에 덧붙여진다. 달리 말하면, ECC의 패리티-체크 행렬은 체크섬의 패리티-체크 행렬과 관련된 행(rows)을 추가시킴으로써 확장된다. ECC 패리티 비트들은 체크섬 코드에 관여하지 않기 때문에, ECC 패리티 비트들과 관련된 모든 값들은 체크섬과 관련된 그 추가된 행에서 0이다. 확장된 행렬은 도 7에서 제시되는 형태를 갖는다.

단일의 통합된 패리티-체크 행렬이 체크섬 및 ECC에 대해 정의될 수 있고, 앞서 설명된 방법은 체크섬과 ECC 모두에 대한 조인트 신드롬 벡터(joint syndrome vector)를 계산하기 위해 사용될 수 있다. 조인트 신드롬 벡터의 제1의

개의 원소들은 ECC 신드롬 벡터

를 구성한다. 조인트 신드롬 벡터의 나머지 원소들은 CRC 신드롬 벡터를 구성한다. ECC 신드롬 벡터는 "에러 정정(error correction)" 신드롬으로 지칭될 수 있고, CRC 신드롬 벡터는 "체크섬(checksum)" 신드롬으로 지칭될 수 있다. 반복적 코딩 방식에서 ECC 패리티-체크 행렬은 일반적으로 희소 행렬이고, 반면 체크섬 패리티-체크 행렬은 조밀 행렬이어야 함에 유의해야 한다. 따라서, ECC 신드롬 벡터를 업데이트하기 위해서 도 5에 제시된 메커니즘을 사용하는 것이 효율적일 수 있고(왜냐하면 이것은 패리티-체크 행렬의 희소성에 근거하기 때문), CRC 신드롬 벡터를 업데이트하기 위해서 도 3에 제시된 메커니즘을 사용하는 것이 효율적일 수 있다.

체크섬을 구현하는 디코더 디바이스의 회로는 준-순환 LDPC(QC-LDPC) ECC 코드들과 함께 사용되는 경우 특정 체크섬 구조에 근거하여 간략하게 될 수 있다. 이러한 코드들은 통신 및 저장 애플리케이션들에서의 사용에 적합할 수 있다. 특정 체크섬 구조는 인코더/디코더 데이터 경로를 재사용하는 것을 허용하고, 이에 따라 매우 낮은 구현 복잡도를 갖는다. 더욱이, 이것은 LDPC 디코더에 의해 검출되지 않은 에러들을 검출함에 있어서 종래의 CRC만큼 효과적일 수 있다.

디코딩 행렬을

로 나타낸다. 바람직하게는,

의 ECC 관련 부분은 LDPC 코드의 저밀도 패리티-체크 행렬이다. 또한, LDPC 코드는 QC-LDPC 코드일 수 있고, 이에 따라 저밀도 패리티-체크는 블록 행렬(block matrix)이며, 여기서 각각의 블록은 정방 행렬(square matrix)이고, 각각의 정방 행렬은 0이거나 순환 치환 행렬(혹은 특정 QC-LDPC 코드 패밀리(code families) 내의 순환 치환 행렬들의 합)이다. 순환 치환 행렬은

형태의 행렬이며,

이고, 여기서

이다.

이러한 구조(즉, 각각의 블록은 정방 행렬이고 각각의 정방 행렬은 0이거나 순환 치환 행렬인 블록 행렬)는 LDPC 디코더의 매우 효율적인 하드웨어 구현을 가능하게 하는데, 왜냐하면 이것은 LDPC 코드 정보를 저장하는 메모리들로부터 LDPC 디코딩 동안 정보를 프로세싱하는 계산 유닛들로 정보(메시지 패싱 디코딩 알고리즘에서의 메시지들)를 라우팅하는 것을 간략하게 하기 때문이다. 실제로, 오늘날 산업 표준(통신 및 스토리지 애플리케이션들 모두)에서 사용되는 대부분의 LDPC 코드들은 QC-LDPC 코드들에 근거하고 있을 수 있다.

의 체크섬 관련 부분이 효율적인 체크섬 계산을 위해 동일한 하드웨어 구조를 사용하기 위해서,

의 체크섬 관련 부분은 또한, 블록 구조를 가질 수 있는바, 여기서 각각의 블록 원소는

이거나

형태의 행렬들의 합이다. 예를 들어,

의 체크섬 관련 부분은 다수의 블록 원소들의 어레이일 수 있다. 각각의 블록 원소는 정방 행렬일 수 있다. 각각의 정방 행렬은 정방 행렬 내의 모든 원소에 대해 0의 값을 가질 수 있거나(즉, "

" 블록 원소), 혹은 그 대신

형태의 행렬들의 합일 수 있다. (서로 같은 차원을 갖는 2개의 정방 행렬들의 합은 동일한 차원을 갖는 정방 행렬이다.) 만약 체크섬에 대응하는 행렬("체크섬 행렬")이 QC-LDPC 패리티-체크 행렬과 동일한 구조를 갖는다면, 이것은 체크섬 행렬이 희소 행렬일 것으로 예측될 수 있음을 시사할 수 있다. 그러나, 체크섬 행렬이 ECC에 의해 검출되지 않은 에러 패턴들(특히, LDPC 디코더에 의해 검출될 수 없는 소수의 에러들을 갖는 패턴들)을 높은 확률로 검출할 수 있도록 하기 위해서, 체크섬 행렬은 비-희소 행렬(non-sparse matrix)이어야만 한다. 그러나, 이러한 명백하게 상반되는 요건들은 본 명세서에서 설명되는 바와 같이 해결될 수 있다.

예를 들어, 32개의 행(rows)(32개의 체크(checks))으로 구성된 체크섬 행렬을 고려한다.

LDPC 코드의 길이는 1000이고, LDPC 코드가 "최소 코드워드 가중치(minimal codeword weight)" 20을 갖는다(즉, LDPC 코드는 값이 1인 20개의 비트들만을 갖는 코드워드를 갖는다)고 가정한다.

만약 LDPC 디코더가 적법 코드

워드로 수렴하지만 원하는 코드워드

로 수렴하는데 실패했다면, 가장 가능성 있는 것으로 디코더는 코드워드

=

로 수렴하는데, 여기서

는, 가중치

를 갖는, 코드의 낮은 가중치 코드워드이다. 예를 들어, '

'는 (비록 코드 길이가 1000일지라도) 단지

의 가중치를 가질 수 있다.

ECC 디코더가 틀린 코드워드로 수렴함에 따라, 이러한 이벤트는 체크섬에 의해 "캐칭(catching)"되는 것이 바람직하다. 체크섬이 이전의 에러 정정에 의해 비검출된 에러를 검출할 때, 비검출된 에러를 캐칭한 체크섬 행렬의 성공이 선언된다. 달리 말하면, 코드워드가 체크섬 조건을 만족시키지 못할 때 성공이 선언된다. 체크섬 행렬의 실패는 체크섬 행렬 계산 이후에도 에러들이 비검출된 상태로 있는 경우에 일어난다. 이것은 오류가 있는 코드워드가 체크섬 행렬 계산을 만족시키는 경우에는 언제나 일어난다.

가 적법 코드워드이기 때문에, 이것은 체크섬 패리티-체크 방정식을 만족시킨다. 따라서, 체크섬은 만약 에러 패턴

가 또한 32개의 체크섬 패리티-체크 방정식 모두를 만족시킨다면 에러 검출에 실패한다.

이러한 이벤트의 확률은 다음과 같이 결정될 수 있다.

길이

그리고 최소 가중치

인 워드

는

인 경우

가 1인 랜덤 패리티-체크

를 만족시키지 않으며, 여기서

는

의 비트들이고(이러한 비트들의

는 1, 다른 것들은 0),

는 체크 비트들이다(이러한 체크 비트들의

는 1이고 다른 것들은 0).

확률

는 다음과 같이 계산될 수 있다.

1. 각각의

에 대해(이에 대한

), 확률

은 다음과 같이 주어진다.

2. 개개의 좌표가 1이 될 확률이 독립적이라고 가정한다. 작은

에 대해, 이것은 좋은 근사화다. 이 경우, 패리티-체크가 만족되지 않을 확률(즉,

)은 (값이 1일 수 있는

개의 항(terms) 중에서) 값이 1인 홀수 개의

항을 가질 확률로서 계산될 수 있다. 이러한 확률은 다음과 같이 주어진다.

확률

는 다음과 같은 클로즈드 폼(closed form)으로 계산될 수 있다.

그리고

만약

이라면, (임의의

에 대해)

.

만약

이고

이라면, 결과는 여전히 0.5로부터 멀리 벗어나지 않는다.

그러나,

이 더 작아짐에 따라, 패리티-체크가 랜덤 에러 패턴에 의해 만족되지 않을 확률은 감소하기 시작하고, 0.5보다 훨씬 더 낮아질 수 있다. 예를 들어,

및

에 대해,

개의 패리티-체크들을 갖는 체크섬이 에러를 오검출(miss-detecting)할 확률은 체크섬의

개의 패리티-체크들 모두가 만족될 확률이며, 다음과 같이 주어진다.

체크섬 오검출의 확률 =

=32개의 패리티-체크들(이들 각각은

=1000개의 비트들 중에서

=100개의 1을 가짐)을 갖는 체크섬에 대해, 가중치

=20인 경우 에러 패턴을 오검출할 확률은,

=32개의 패리티-체크들(이들 각각은

=1000개의 비트들 중에서

=10개의 1을 가짐)을 갖는 체크섬에 대해, 가중치

=20인 경우 에러 패턴을 오검출할 확률은,

이것이 의미하는 바는 매우 낮은 오검출 확률을 갖기 위해서는 비-희소 패리티-체크들(즉, 다량의 1을 갖는 패리티-체크들)이 사용돼야만 함을 의미한다.

그러나, 효율적인 하드웨어 구현을 위해 그리고 QC-LDPC 디코더 데이터 경로의 재사용을 위해, QC-LDPC 행렬 구조가 체크섬을 위해 사용될 수 있으며, 종래의 QC-LDPC 행렬들은 희소 행렬이다.

체크섬 행렬을 위해 사용될 수 있고 이에 따라 고밀도 행렬을 가질 요건과 QC-LDPC 구조를 가질 요건 모두를 만족시킬 수 있는 조밀 QC-LDPC 행렬 구조가 구성될 수 있다(즉, 치환 행렬들에 근거하는 블록 행렬).

체크섬 행렬은 치환 소행렬들의 합인 소행렬들로 구성된 블록 행렬로서 발생될 수 있다. 치환 소행렬들은 순환 치환 소행렬들(cyclic permutation sub-matrices)일 수 있는바, 즉 항등 행렬(identity matrix)의 순환 시프트된 버전(cyclically shifted version)들이다. 따라서, 앞서 서술된 문제는 다수의 희소한 QC 구조화 체크 섬들(sparse QC structured check sums)을 결합시킴으로써 해결되는바, 이러한 결합은 그 결합 내의 각각의 원소가 여전히 희소함과 아울러 복잡도가 낮은 하드웨어를 사용할 수 있도록 행해지며, 그리고 다수의 이러한 원소들을 결합시키는 것은 전체 결합이 조밀해지게 한다.

더 형식적으로 살펴보면, 체크섬 행렬은 다음과 구성될 수 있다.

가, 제안된 체크섬과 함께 사용될 QC-LDPC ECC 코드의 순환 치환 블록 크기(이것은 또한 리프팅 팩터(lifting factor)로서 알려져 있음)를 나타낸다고 하자.

가, 사용될 QC-LDPC ECC(즉,

개의 정보 비트들을 갖는 ECC)의 정보 서브 블록들의 수를 나타낸다고 하자. 그 다음에, 차수(order)가

인 체크섬 행렬

은

로서 구성될 수 있는바, 이것은

개의 소행렬들

로 이루어지며, 여기서 소행렬

은

개의 행렬들

의 합으로서 정의되는바, 다음과 같은 방정식에 의해 정의되며,

여기서,

는 차수가

인 미리 정의된 행렬이고,

는 미리 정의된 정수이며, 숫자

는 미리 정의된 수 혹은 무작위로 선택된 정수이다. 일부 실시예들에서,

가 너무 조밀해지는 것을 피하기 위해

이다. 만약

이라면,

는 0 행렬이다. 특정 실시예에서,

는

치환 행렬이다. 일부 실시예들에서,

는 항등

행렬이고, 이에 따라

는 (순환 치환 행렬에 대응하는) 항등 행렬의 순환 버전이다.

제안된 체크섬 행렬에 근거하여 인코딩이 수행될 수 있는바, 이러한 인코딩은,

개의 인코딩된 데이터 비트들의 세트를 발생시키기 위해 조밀 체크섬 행렬

를 패리티 체크 행렬로서 사용하여

개의 데이터 비트들을 인코딩함으로써 행해질 수 있는바, 여기서 마지막 '

'개의 비트들은 체크섬 비트들을 구성한다. 제1의 인코딩된 데이터 비트들은 패리티 체크 행렬

를 사용하여 더 인코딩될 수 있는바, 여기서

는 차수가

인 소행렬들

로 이루어진 희소 행렬이고, 소행렬들 각각은 0 행렬이거나 혹은 어떤 정수

에 대해

형태의 행렬이거나, 혹은 정수들

의 세트에 대해

형태의 합이다.

체크섬 행렬

는 QC-LDPC 구조를 갖도록(하지만 고밀도를 갖도록) 발생될 수 있다. 각각의 패리티-체크 방정식에서 1의 개수(

로서 나타내짐)는 체크섬 행렬

를 정의하는 정수들

에 의해 결정될 수 있다. 앞서 제공된 분석에 따라, 파라미터

는 요구된 체크섬 검출 확률, 체크섬 패리티-체크들의 개수(

), 그리고 LDPC 코드의 예측된 최소 코드워드 가중치(

)에 근거하여 계산될 수 있다.

예를 들어, 1KB 정보(

=8192)에 대해

=20이고,

=32,

,

에 대해

이며

=32인 경우, 체크섬 오검출 확률은 3×10^-10일 수 있다. 여기서

는

을 만족시키는

중에서

원소들의 개수이다.

체크섬 행렬은 LDPC 패리티-체크 행렬보다 더 높은 밀도를 가짐에 또한 유의해야 한다. (즉, LDPC 패리티-체크 행렬(

)의 패리티-체크에서 1의 개수가

이라면

이다.) 예시적 구현예에서

이다.

도 7에서 예시되는 통합된 패리티 행렬은 체크섬 패리티-체크 행렬의 단일 "스트립(strip)"을 포함할 수 있는바, 즉, 체크섬 패리티-체크 행렬은

개의 행을 가지며, 0이 아닌 원소들로 된

개의 열을 가질 수 있다. "체크섬 섹션(checksum section)"은 CRC 패리티 비트들에 대응할 수 있고, 따라서 치환 행렬들의 합이 아니라

개의 항등 행렬일 수 있다. 도 7의 체크섬 패리티 행렬의 나머지

개의 블록들 각각은 희소 ECC 패리티-체크 행렬과 비교해 조밀할 수 있다. 대안적으로, 통합된 패리티 행렬은 예를 들어 2

개의 행, 3

개의 행, 혹은 그 이상의 행을 가짐으로써, 체크섬 패리티-체크 행렬의 다수의 "스트립"을 포함할 수 있다. 체크섬 패리티-체크 행렬 내에서의 하나 이상의 소행렬들은 희소 행렬(혹은 0 행렬)일 수 있으며 실질적인 체크섬 세기(checksum strength)를 계속 제공할 수 있다. 예를 들어, 만약 제 1 체크섬 패리티-체크 스트립이 제 1 위치에서 0 소행렬을 가지고, 제 2 체크섬 패리티-체크 스트립이 (제 1 위치와 동시에 일어나지 않는) 제 2 위치에서 0 소행렬을 가지고 있다면(즉, 두 개의 체크섬 패리티 스트립들의 0 위치들이 겹치지(overlap) 않는다면), 제 1 체크섬 패리티-체크 스트립과 제 2 체크섬 패리티-체크 스트립을 포함하는 체크섬 패리티-체크 행렬은 특정 구현을 위한 CRC 오검출 확률 요건을 만족시킴에 있어 전체적으로 충분히 조밀할 수 있다.

도 8을 참조하며, 시스템(800)의 특정 실시예가 제시된다. 시스템(800)은 데이터 저장 디바이스(802)를 포함한다. 데이터 저장 디바이스(802)는 제어기(806)에 결합되는 메모리(804)를 포함한다. 메모리(804)(예를 들어, NAND 플래시 메모리)는 저장 소자들(822)의 대표적인 그룹과 같은 저장 소자들을 포함한다. 저장 소자들(822)의 그룹의 예는 멀티레벨 셀(MultiLevel Cell, MLC) 워드 라인이다. 데이터 저장 디바이스(802)는 대표적인 호스트 디바이스(830)에 선택적으로 연결된다.

데이터 저장 디바이스(802)는 솔리드 스테이트 디스크(SSD) 디바이스일 수 있다. 데이터 저장 디바이스(802)는 메모리 카드일 수 있는바, 예를 들어, 시큐어 디지털(Secure Digital, SD®) 카드, 마이크로SD 카드(microSD® card), 미니SD 카드(miniSD.TM card)(미국 델라웨어 주 윌밍턴에 소재한 SD-3C LLC의 상표), 멀티미디어카드(MultiMediaCard.TM, MMC.TM) 카드(MMC 카드)(미국 버지니아 주 알링톤에 소재한 JEDEC 솔리드 스테이트 테크놀로지 어소시에이션(JEDEC Solid State Technology Association)의 상표), 혹은 콤팩트플래시(CompactFlash®, CF) 카드(미국 캘리포니아 주 밀피타스에 소재한 샌디스크 코포레이션(SanDisk Corporation)의 상표)가 있다. 대안적으로, 데이터 저장 디바이스(802)는 호스트 디바이스(830) 내의 임베디드 메모리(embedded memory)일 수 있는바, 예를 들면, 예시적 사례로서, eMMC®(미국 버지니아 주 알링톤에 소재한 JEDEC 솔리드 스테이트 테크놀로지 어소시에이션의 상표) 및 eSD가 있다.

제어기(806)는 치환 행렬들의 합에 근거하여 체크섬들(예컨대, CRC)을 수행하도록 구성된 코딩 유닛(808)이 포함된 메모리 제어기일 수 있다. 제어기(806)는 호스트 디바이스(830)로부터 저장을 위해 사용자 데이터(832)를 수신할 수 있고, 메모리(804)로부터 데이터를 검색할 수 있으며, 호스트 디바이스(830)에 의해 요청된 사용자 데이터(832)를 전달할 수 있다. 따라서, 제어기(806)는 호스트 디바이스(830)와 그리고 메모리(804)와 통신할 수 있다.

코딩 유닛(808)은 디코더이거나 인코더일 수 있다. 코딩 유닛(808)은 치환 행렬들(812)의 합을 사용하여 CRC 계산을 수행하도록 구성된 CRC 컴포넌트(810)를 포함한다. 예를 들어, 치환 행렬들(812)은 순환 치환 행렬들일 수 있다. CRC 컴포넌트(810)는 도 7에 관해 설명된 체크섬 패리티-체크 행렬을 포함할 수 있다. 코딩 유닛(808)은 또한, QC-LDPC 컴포넌트(814)로서 예시된, LDPC 컴포넌트와 같은 ECC 컴포넌트를 포함할 수 있다. 치환 행렬들(812)은 QC-LDPC 컴포넌트(814)에 의해 그리고 CRC 컴포넌트(810)에 의해 사용될 수 있다.

예로서, 코딩 유닛(808)은 도 1의 디코더(10)에서 예시된 아키텍처를 구현할 수 있고, RAM, ROM, 그리고 하드웨어 프로세싱 디바이스들과 같은 컴포넌트들을 포함할 수 있다. 일부 구현예들에서, 코딩 유닛(808)은 도 2 내지 도 5 중 어느 하나 혹은 이들의 임의의 조합에 관하여 설명된 바와 같이 수렴 검출을 수행하도록 구성될 수 있다. 다른 구현예들에서, 코딩 유닛(808)은 도 2 내지 도 5 중 어느 하나에 관하여 설명된 바와 같이 수렴 검출을 수행하도록 구성되지 않을 수 있다.

코딩 유닛(808)은 메모리(804)에 데이터를 저장하기 전에 데이터 인코딩을 수행하도록 구성될 수 있다. 예를 들어, 코딩 유닛(808)은, 사용자 데이터(832)를 위한 CRC 패리티를 발생시키기 위해, 치환 행렬들(812) 중 하나 이상의 치환 행렬의 합에 근거하는 CRC 행렬을 수신된 사용자 데이터(832)에 적용할 수 있다. 코딩 유닛(808)은 메모리(804)에 전송되어 저장될 ECC 코드워드를 발생시키기 위해 예를 들어, QC-LDPC 컴포넌트(814)를 통해, 사용자 데이터(832) 및 CRC 패리티의 ECC 인코딩을 수행할 수 있다.

대안적으로, 혹은 추가적으로 코딩 유닛(808)은 메모리(804)로부터 수신된 데이터의 디코딩을 수행하도록 구성될 수 있다. 코딩 유닛(808)은 예를 들어, QC-LDPC 컴포넌트(814)를 통해, ECC 디코딩 연산을 적용할 수 있으며, QC-LDPC 컴포넌트(814)는 반복적 디코딩 프로세스의 수렴으로부터 발생된 데이터 워드를 리턴(return)할 수 있다. 데이터 워드는 CRC 컴포넌트(810)에 제공될 수 있고, 이에 따라 데이터 워드 내의 CRC 패리티는 데이터 워드의 사용자 데이터 부분에 근거하여 발생된 CRC 패리티와 비교되게 된다. 대안적으로, CRC 패리티는 도 5에 관하여 설명된 바와 같이 온-더-플라이로 발생될 수 있다. 예를 들어, 제어기(806)는, 데이터 비트들 중 적어도 하나의 데이터 비트의 값의 추정이 변경되었다는 결정에 응답하여 코드워드의 표현의 반복적인 에러 정정 코딩(ECC) 디코딩 동작의 반복 동안 체크섬 신드롬 값들을 업데이트하도록 구성될 수 있다. 제어기(806)는, 코드워드의 표현을 디코딩하는 것과 관련된 모든 CRC 신드롬 비트들 및 모든 ECC 신드롬 비트들이 0의 값을 갖는다는 것에 응답하여, 수렴 신호를 발생시키도록 구성된 수렴 검출기(예를 들어, 도 5의 수렴 검출기(52))를 포함할 수 있다.

코딩 유닛(808)이 QC-LDPC 컴포넌트(814)와 같은 ECC 컴포넌트를 포함하는 것으로서 예시되고 있지만, 다른 실시예들에서 코딩 유닛(808)은 ECC 컴포넌트를 또한 구현함이 없이 치환 행렬들(812) 중 하나 이상의 치환 행렬의 합에 근거하는 CRC 컴포넌트(810)를 포함할 수 있음을 이해해야 한다.

데이터 저장 디바이스(802)의 코딩 유닛(808)과 같은 메모리 디바이스의 코딩 유닛에서, 데이터 비트들을 인코딩하기 위한 방법이 수행될 수 있다. 이 방법은 데이터 비트들에 근거하여 체크섬 패리티 비트들을 계산하는 것을 포함할 수 있다. 데이터 비트들 및 체크섬 패리티 비트들이 만족시키는 방정식들의 세트는 조밀 패리티-체크 행렬에 대응한다. 예를 들어, 차수가

인 체크섬 행렬

가

개의 소행렬들

에 근거하여

로서 구성될 수 있고, 여기서 각각의 소행렬

은

개의 행렬들

의 합으로서 정의된다. 조밀 패리티-체크 행렬은 치환 소행렬들의 합을 포함한다. 치환 소행렬은 순환 치환 소행렬일 수 있다(예를 들어, 각각의 소행렬

은

개의 행렬들

의 합으로서 정의될 수 있음).

특정 실시예에서, 행렬은, 0이 아닌 값들을 갖는 행렬의 원소들의 일정 퍼센티지 혹은 비율이 임계치를 초과하는 것에 응답하여, "조밀한(dense)" 것으로 고려될 수 있다. 임계치는 예시적인 비한정적 예로서, 10%, 혹은 1/3, 혹은 1/2일 수 있다. 예를 위해서, 패리티-체크 행렬의 밀도는 0이 아닌 값들을 가진 행렬 원소들의 일정 퍼센티지에 대응할 수 있다. 예를 들어, 조밀 패리티-체크 행렬은 다수의 원소들을 포함할 수 있다. 조밀 패리티-체크 행렬은 0이 아닌 원소들의 개수가 적어도 10%인 것에 대응하는 밀도를 가질 수 있다. 또 다른 예로서, 조밀 패리티-체크 행렬은 0이 아닌 원소들의 개수가 적어도 1/3인 것에 대응하는 밀도를 가질 수 있다. 또 다른 예로서, 조밀 패리티-체크 행렬은 0이 아닌 원소들의 개수가 실질적으로 1/2인 것에 대응하는 밀도를 가질 수 있다.

또 하나의 다른 실시예에서, 행렬은, 행렬의 각각의 블록을 발생시키기 위해 합산되는 치환 소행렬들의 수가 임계치보다 더 큰 것(예를 들어, 모든 소행렬

에 대해

)에 응답하여 "조밀한" 것으로 고려될 수 있다. 예시적인 비한정적 예로서, 임계치는 1 혹은 2와 같은 수일 수 있거나, 혹은 소행렬 차원에 근거할 수 있다(예를 들어,

또는

). 예를 들어, 조밀 패리티-체크 행렬은 치환 소행렬들 중 적어도 두 개의 치환 소행렬들의 합인 치환 소행렬들의 합 각각에 대응하는 밀도를 가질 수 있다. 또 하나의 다른 예로서, 조밀 패리티-체크 행렬은 치환 소행렬들 중 적어도 두 개보다 많은 치환 소행렬들의 합인 치환 소행렬들의 합 각각에 대응하는 밀도를 가질 수 있다. 또 하나의 다른 예로서, 조밀 패리티-체크 행렬은 다수의 치환 소행렬들의 합인 치환 소행렬들의 합 각각에 대응하는 밀도를 가질 수 있는바, 여기서 치환 소행렬들의 수는 치환 소행렬들 중 하나의 치환 소행렬의 차원의 실질적으로 반(half)이다.

또 하나의 다른 실시예에서, 행렬은, 원소들의 총 개수에 대비된 0이 아닌 원소들의 개수의 비율이 밀도 임계치를 초과하는 것에 응답하여 "조밀한" 것으로 고려될 수 있다. 예를 들어, 조밀 패리티-체크 행렬은, 조밀 패리티-체크 행렬의 원소들의 총 개수에 대비된 조밀 패리티-체크 행렬의 0이 아닌 원소들의 개수의 비율에 대응하는 밀도를 가질 수 있는바, 그 비율은 밀도 임계치를 초과한다. 예로서, 밀도 임계치는 대략 0.4일 수 있다. 조밀 패리티-체크 행렬은 또한 총 원소들에 대한 0이 아닌 원소들의 비율이 대략 0.6보다 작도록 제약을 받을 수 있다.

에러 정정 코딩(ECC) 패리티 비트들은 데이터 비트들 및 체크섬 패리티 비트들에 근거하여 계산될 수 있다. 데이터 비트들, 체크섬 패리티 비트들, ECC 패리티 비트들이 만족시키는 방정식들의 제 2 세트(즉, 도 7의 ECC 패리티 체크 행렬에 대응하는 것)는 희소 패리티-체크 행렬에 대응할 수 있다. 희소 패리티-체크 행렬은 치환 소행렬들 및 0 소행렬들로 한정될 수 있다.

특정 실시예에서, 행렬은 또 하나의 다른 행렬과의 비교에 근거하여 "조밀한" 것으로 고려될 수 있다. 예를 들어, 조밀 패리티-체크 행렬은 희소 패리티-체크 행렬의 밀도의 적어도 두 배인 밀도를 가질 수 있다. 또 하나의 다른 예로서, 조밀 패리티-체크 행렬은 희소 패리티-체크 행렬의 밀도의 적어도 3배인 밀도를 가질 수 있다.

희소 패리티-체크 행렬은 희소 패리티-체크 행렬의 원소들의 총 개수에 대비된 희소 패리티-체크 행렬의 0이 아닌 원소들의 개수의 비율에 대응하는 밀도를 가질 수 있다. 이러한 비율은 희소도 임계치보다 더 작을 수 있다. 예를 들어, 희소도 임계치는 대략 0.1일 수 있다.

데이터 비트들을 인코딩하는 방법은 다음과 같은 패리티 체크 행렬을 구성하는 것을 포함하는바,

여기서,

의 차수는

이고,

는

개의 소행렬

을 포함하며,

및

는 정수이고, 각각의 소행렬

는 아래 식과 같이

개의 행렬들

의 합으로서 정의되는데,

,

여기서,

는 차수가

인 미리 정의된 행렬이고, 각각의

는 미리 정의된 정수이며, 숫자

는 미리 정의된 수 혹은 무작위로 선택된 정수이다. 이 방법은 또한,

개의 제1의 인코딩된 데이터 비트들의 세트를 발생시키기 위해 패리티 체크 행렬

를 사용하여

개의 데이터 비트들을 인코딩하는 것을 포함할 수 있다. 이 방법은 도 8의 코딩 유닛(808)에서와 같은 데이터 저장 디바이스의 코딩 유닛에서 수행될 수 있다.

이 방법은 또한, 패리티 체크 행렬

를 사용하여 제1의 인코딩된 데이터 비트들을 인코딩하는 것을 포함할 수 있으며, 여기서

는 차수가

인 소행렬들

를 포함한다. 소행렬들

각각은 0 행렬이거나

형태의 행렬일 수 있다(

는 정수임).

는 차수가

인 항등 행렬의 행(row)들 혹은 열(column)들에 순환 치환(cyclic permutation)을 적용함으로써 발생될 수 있다. 일부 실시예들에서,

는

와 같거나 이보다 크고,

는 0.4와 같거나 이보다 큰 미리 정의된 수이다. 일부 실시예에서,

는 10과 같거나 이보다 클 수 있다. 행렬

의 원소들의 총 개수에 대비된 행렬

에서의 0이 아닌 원소들의 개수의 비율은 0.1보다 작을 수 있다.

비록 도 8이 플래시 메모리 카드와 같은 데이터 저장 디바이스 내에서 치환 행렬들의 합을 사용하는 CRC의 구현을 제시하고 있지만, 다른 실시예들에서는 치환 행렬들의 합을 사용하는 CRC가 다른 시스템 내에서 구현될 수 있다. 예를 들어, 송신기는, 통신 시스템을 통해(예를 들어, 무선 네트워크를 통해, 혹은 유선 네트워크를 통해, 혹은 이들의 임의의 조합을 통해) 메시지를 전송하기 위해 (QC-LDPC 인코딩과 같은 ECC 인코딩을 수행함과 함께, 혹은 수행함이 없이) 치환 행렬들의 합을 사용하여 CRC 패리티를 발생시킬 수 있다. 수신기는 수신된 메시지의 무결성을 (QC-LDPC 디코딩과 같은 ECC 디코딩을 수행함과 함께, 혹은 수행함이 없이) 체크하기 위해 CRC 신드롬을 발생시킬 수 있다.

본 명세서에서 제시되는 다양한 컴포넌트들이 블록 컴포넌트들로서 예시되고 일반적인 용어로 서술되고 있지만, 이러한 컴포넌트들은, 컴포넌트들(예를 들어, 도 8의 코딩 유닛(808))로 하여금 해당 컴포넌트에 속한 특정 기능을 수행할 수 있도록 구성된 하나 이상의 마이크로프로세서, 상태 머신, 혹은 다른 회로들을 포함할 수 있다. 예를 들어, CRC 컴포넌트(810)는 코딩 유닛(808)으로 하여금 하나 이상의 치환 행렬들의 합을 사용하여 CRC 동작을 수행할 수 있도록 하는 물리적 컴포넌트(예를 들어, 하드웨어 제어기, 상태 머신, 로직 회로, 혹은 다른 구조)를 나타낼 수 있다.

코딩 유닛(808)은 CRC 컴포넌트(810)를 구현하기 위해 전용 하드웨어(즉, 회로)를 포함할 수 있다. 대안적으로, 혹은 추가적으로, 코딩 유닛(808)은 도 1에서 예시된 프로세서들(18)과 같은 하나 이상의 하드웨어 프로세싱 유닛들을 사용하여 CRC 컴포넌트(810)를 구현할 수 있다. 특정 실시예에서, 코딩 유닛(808)은 프로세서들(18) 혹은 다른 프로세서들에 의해 실행되는 명령들을 포함하고, 명령들은 메모리(804)에 저장된다. 대안적으로, 혹은 추가적으로, 코딩 유닛(808) 내에 포함될 수 있는 프로세서에 의해 실행되는 명령들은 메모리(804)의 일부분이 아닌 별개의 메모리 위치에 저장될 수 있는바, 예를 들어, 판독-전용 메모리(ROM)에 저장될 수 있다.

특정 실시예에서, 코딩 유닛(808)을 포함하는 데이터 저장 디바이스(802)는 하나 이상의 외부 디바이스에 선택적으로 결합되도록 구성된 휴대용 디바이스에서 구현될 수 있다. 그러나, 다른 실시예들에서, 코딩 유닛(808)을 포함하는 데이터 저장 디바이스(802)는 하나 이상의 호스트 디바이스 내에, 예를 들어, 호스트 휴대용 통신 디바이스의 하우징 내에, 부착(attach)되거나 임베드(embed)될 수 있다. 예를 들어, 코딩 유닛(808)을 포함하는 데이터 저장 디바이스(802)는 패키징된 장치 내에 존재할 수 있는바, 예를 들어, 무선 전화기, 개인 휴대 정보 단말기(Personal Digital Assistant, PDA), 게이밍 디바이스 혹은 콘솔, 휴대용 네비게이션 디바이스, 또는 내부 비휘발성 메모리를 사용하는 다른 디바이스 내에 존재할 수 있다. 특정 실시예에서, 코딩 유닛(808)은, 비휘발성 메모리, 예를 들어, 삼차원(three-dimensional)(3D) 메모리, 플래시 메모리(예컨대, NAND, NOR, 멀티-레벨 셀(Multi-Level Cell, MLC)), 분할된 비트-라인 NOR(Divided bit-line NOR, DINOR), AND, 고용량 커플링율(high capacitive coupling ratio, HiCR), 비대칭 무접점 트랜지스터(Asymmetrical Contactless Transistor, ACT), 혹은 다른 플래시 메모리), 소거가능하고 프로그래밍가능한 판독-전용 메모리(Erasable Programmable Read-Only Memory, EPROM), 전기적으로 소거가능하고 프로그래밍가능 판독-전용 메모리(Electrically-Erasable Programmable Read-Only Memory, EEPROM), 판독-전용 메모리(Read-Only Memory, ROM), 일회 프로그래밍가능 메모리(One-Time Programmable memory, OTP), 또는 임의의 다른 타입의 메모리에 결합될 수 있거나 혹은 이와 관련되어 사용될 수 있다.

본 명세서에서 설명되는 실시예들의 예는 다양한 실시예들의 포괄적인 이해를 제공하도록 의도되었다. 다른 실시예들이 본 개시내용으로부터 활용 및 도출될 수 있으며, 이에 따라 구조적 및 논리적 대체물들 그리고 변경들이 본 개시내용의 사상으로부터 벗어남이 없이 만들어질 수 있다. 본 개시내용은 다양한 실시예의 임의의 모든 후속 채택 혹은 변형을 포괄하도록 의도되었다. 이에 따라, 본 개시내용 및 도면들은 한정적 의미가 아닌 예시적 의미로서 고려돼야 한다.

앞서 설명된 주된 내용은 한정적 의미가 아닌 예시적 의미로서 고려돼야 하는바, 첨부되는 특허청구범위는 본 개시내용의 사상 내에 있는 이러한 모든 수정예, 개선예, 및 다른 실시예를 포괄하도록 의도되었다. 따라서, 법이 허용하는 최대 범위까지, 본 발명의 범위는 다음의 특허청구범위와 그 등가물의 허용가능한 최광의 해석으로 결정돼야만 하며, 앞서의 상세한 설명에 의해 제한을 받거나 한정돼서는 안 된다.

Claims

데이터 저장 디바이스의 코딩 유닛(coding unit)에서, 데이터 비트들(data bits)에 근거하여 체크섬 패리티 비트들(checksum parity bits)을 계산(computing)하는 것을 포함하는 방법으로서, 상기 데이터 비트들과 상기 체크섬 패리티 비트들이 만족시키는 방정식들의 세트는 조밀 패리티 체크 행렬(dense parity-check matrix)에 대응하고, 상기 조밀 패리티 체크 행렬은 항등 행렬(identity matrix)의 행(row)들 혹은 열(column)들에 순환 치환(cyclic permutation)을 적용함으로써 발생되는 치환 소행렬들(permutation sub-matrices)의 합(sums)을 포함하는 것을 특징으로 하는 방법.
제1항에 있어서,
상기 데이터 비트들 및 상기 체크섬 패리티 비트들에 근거하여 에러 정정 코딩(Error Correction Coding, ECC) 패리티 비트들을 계산하는 것을 더 포함하고, 상기 데이터 비트들과 상기 체크섬 패리티 비트들과 상기 ECC 패리티 비트들이 만족시키는 방정식들의 제 2 세트는 희소 패리티 체크 행렬(sparse parity-check matrix)에 대응하는 것을 특징으로 하는 방법.
제1항에 있어서,
상기 조밀 패리티 체크 행렬은, 상기 조밀 패리티 체크 행렬의 원소들의 총 개수에 대비된 상기 조밀 패리티 체크 행렬의 0이 아닌 원소들의 개수의 비율에 대응하는 밀도를 가지며, 상기 비율은 밀도 임계치(density threshold)를 초과하는 것을 특징으로 하는 방법.
제3항에 있어서,
상기 밀도 임계치는 0.4인 것을 특징으로 하는 방법.
제4항에 있어서,
상기 비율은 0.6보다 작은 것을 특징으로 하는 방법.
제1항에 있어서,
상기 데이터 저장 디바이스는 또한, 상기 코딩 유닛에 결합되는 3차원(3D) 메모리를 포함하는 것을 특징으로 하는 방법.
데이터 비트들을 인코딩(encoding)하는 방법으로서,
데이터 저장 디바이스의 코딩 유닛에서,
패리티 체크 행렬
을 구성하는 단계와; 그리고

개의 제1의 인코딩된 데이터 비트들의 세트를 발생시키기 위해 상기 패리티 체크 행렬
를 사용하여
개의 데이터 비트들을 인코딩하는 단계를 포함하여 구성되며,
여기서
의 차수(order)는
이고,
는
개의 소행렬
을 포함하며,
및
는 자연수이고, 각각의 소행렬
는 아래 식과 같이
개의 행렬들
의 합으로서 정의되고,

,
여기서
는 차수가
인 미리 정의된 행렬이고, 각각의
는 미리 정의된 자연수이며, 숫자
는 미리 정의된 수 혹은 무작위로 선택된 자연수이며,
는 차수가
인 항등 행렬의 행(row)들 혹은 열(column)들에 순환 치환을 적용함으로써 발생되는 것을 특징으로 하는 데이터 비트들을 인코딩하는 방법.
제7항에 있어서,
패리티 체크 행렬
를 사용하여 상기 제1의 인코딩된 데이터 비트들을 인코딩하는 단계를 더 포함하며, 여기서
는 차수가
인 소행렬들
를 포함하고, 상기 소행렬들
각각은 0 행렬이거나
형태의 행렬이며,
는 자연수인 것을 특징으로 하는 데이터 비트들을 인코딩하는 방법.
제7항에 있어서,

는
보다 크거나
와 같고, 여기서
는 0.4보다 크거나 0.4와 같은 미리 정의된 수인 것을 특징으로 하는 데이터 비트들을 인코딩하는 방법.
제7항에 있어서,

는 10보다 크거나 10과 같은 것을 특징으로 하는 데이터 비트들을 인코딩하는 방법.
제8항에 있어서,
상기 행렬
의 원소들의 총 개수에 대비된 상기 행렬
에서의 0이 아닌 원소들의 개수의 비율은 0.1보다 작은 것을 특징으로 하는 데이터 비트들을 인코딩하는 방법.
제7항에 있어서,
상기 데이터 저장 디바이스는 또한, 상기 코딩 유닛에 결합되는 3차원(3D) 메모리를 포함하는 것을 특징으로 하는 데이터 비트들을 인코딩하는 방법.
데이터 저장 디바이스로서,
메모리와; 그리고
상기 메모리에 결합된 제어기를 포함하여 구성되며,
상기 제어기는 데이터 비트들에 근거하여 체크섬 패리티 비트들을 계산하도록 되어 있고, 상기 데이터 비트들과 상기 체크섬 패리티 비트들이 만족시키는 방정식들의 세트는 조밀 패리티 체크 행렬에 대응하며, 상기 조밀 패리티 체크 행렬은 치환 소행렬들의 합을 포함하고,
상기 제어기는 또한, 상기 데이터 비트들 중 적어도 하나의 데이터 비트의 값의 추정(estimation)이 변경되었다는 결정에 응답하여, 코드워드(codeword)의 표현(representation)의 반복적인 에러 정정 코딩(ECC) 디코딩 동작의 반복 동안 체크섬 신드롬 값들(checksum syndrome values)을 업데이트하도록 되어 있는 것을 특징으로 하는 데이터 저장 디바이스.
제13항에 있어서,
상기 제어기는 수렴 검출기(convergence detector)를 포함하고, 상기 수렴 검출기는 상기 코드워드의 상기 표현을 디코딩하는 것과 관련된 모든 순환 리던던시 체크(Cyclic Redundancy Check, CRC) 신드롬 비트들 및 모든 ECC 신드롬 비트들이 0의 값을 갖는 것을 검출함에 응답하여 수렴 신호(convergence signal)을 발생시키도록 되어 있는 것을 특징으로 하는 데이터 저장 디바이스.
제13항에 있어서,
상기 메모리는 3차원(3D) 메모리를 포함하는 것을 특징으로 하는 데이터 저장 디바이스.