KR101437396B1

KR101437396B1 - 레이턴시를 줄일 수 있는 에러 정정 블록을 포함하는메모리 시스템 및 그것의 에러 정정 방법

Info

Publication number: KR101437396B1
Application number: KR1020080017972A
Authority: KR
Inventors: 조남필; 윤대한
Original assignee: 삼성전자주식회사
Priority date: 2008-02-27
Filing date: 2008-02-27
Publication date: 2014-09-05
Anticipated expiration: 2028-02-27
Also published as: US20090217140A1; KR20090092628A; TWI447732B; US8301986B2; TW200943300A

Abstract

본 발명에 따른 에러 정정 디코더는, 독출 데이터의 신드롬을 계산하는 신드롬 계산 블록; 상기 독출 데이터에 싱글-비트 에러가 존재하는 경우, 상기 싱글-비트 에러의 위치를 상기 신드롬의 원소들 간의 나눗셈 연산을 이용하여 계산하는 에러 정정 연산 블록; 및 상기 에러의 위치를 참조하여 상기 독출 데이터의 에러를 정정하는 에러 정정 회로를 포함한다.

상술한 에러 정정 연산 블록을 통하여 싱글-비트 에러에 대해서 KES 연산 및 치엔 서치 연산을 생략할 수 있어, 레이턴시를 최소화할 수 있다.

Description

레이턴시를 줄일 수 있는 에러 정정 블록을 포함하는 메모리 시스템 및 그것의 에러 정정 방법{MEMORY SYSTEM COMPRISING ECC BLOCK FOR REDUCING A LATENCY AND ERROR CORRECTION METHOD THEREOF}

본 발명은 반도체 메모리 장치에 관한 것으로, 좀 더 구체적으로는 불휘발성 메모리 장치의 독출 에러를 줄일 수 있는 방법 및 독출 에러를 줄일 수 있는 메모리 시스템에 관한 것이다.

반도체 메모리 장치는 크게 휘발성 반도체 메모리 장치(Volatile semiconductor memory device)와 불휘발성 반도체 메모리 장치(Non-volatile semiconductor memory device)로 구분된다. 휘발성 반도체 메모리 장치는 읽고 쓰는 속도가 빠르지만 외부 전원 공급이 끊기면 저장된 내용이 사라져 버리는 단점이 있다. 반면에 불휘발성 반도체 메모리 장치는 외부 전원 공급이 중단되더라도 그 내용을 보존한다. 그러므로 불휘발성 반도체 메모리 장치는 전원이 공급되었는지의 여부에 관계없이 보존되어야 할 내용을 기억시키는 데 쓰인다. 불휘발성 반도체 메모리 장치로는 마스크 롬(Mask read-only memory, MROM), 프로그램 가능한 롬(Programmable read-only memory, PROM), 소거 및 프로그램 가능한 롬(Erasable programmable read-only memory, EPROM), 전기적으로 소거 및 프로그램 가능한 롬(Electrically erasable programmable read-only memory, EEPROM) 등이 있다.

일반적으로, MROM, PROM 및 EPROM은 시스템 자체적으로 소거 및 쓰기가 자유롭지 못해 일반 사용자들이 기억 내용을 갱신하기가 용이하지 않다. 이에 반해 EEPROM은 전기적으로 소거 및 쓰기가 가능하기 때문에, 계속적인 갱신이 필요한 시스템 프로그래밍(System programming)이나 보조 기억 장치로의 응용이 확대되고 있다. 특히 플래시(Flash) EEPROM은 기존의 EEPROM에 비해 집적도가 높아, 대용량 보조 기억 장치로의 응용에 매우 유리하다. 플래시 EEPROM 중에서도 낸드형(NAND-type) 플래시 EEPROM(이하, '낸드형 플래시 메모리'라 칭함)은 다른 플래시 EEPROM에 비해 집적도가 매우 높은 장점을 가진다.

최근 들어 메모리 장치에 대한 고집적 요구가 증가함에 따라, 하나의 메모리 셀에 멀티 비트 데이터를 저장하는 멀티-비트 메모리 장치들이 보편화되고 있다. 멀티-비트 플래시 메모리 장치의 메모리 셀들은 문턱 전압 분포들 간의 간격이 조밀하게 제어되어야 한다. 조밀한 문턱 전압 분포의 제어를 위해서 멀티-비트 플래시 메모리 장치는 프로그램 동작시에 정밀한 제어 동작과 그에 대응하는 시간의 소모가 요구된다. 그러나 이러한 제어 방식은 프로그램 속도를 저하시켜 효율적이지 못하다. 따라서, 한정된 자원을 가지고 최대의 성능을 구현하기 위해 일반적으로 멀티-비트 플래시 메모리 장치는 독출 동작을 제어한다. 독출 동작시, 호스트와 플래시 메모리 장치 간에 인터페이싱을 제공하는 메모리 컨트롤러는 플래시 메모리 장치로부터 독출된 데이터에 포함되는 에러(Error)를 정정(Correct)한다.

메모리 컨트롤러에 포함되는 에러 정정 블록(Error Correction Code Block: 이하, 'ECC 블록'이라 칭함) 또는 에러 정정 디코더는 상술한 독출 데이터(Read data)에 포함된 에러를 검출(Detect)하고 정정(Correct)한다. 하나의 메모리 셀에 점점 많은 수의 비트가 저장될수록 에러의 발생 확률은 증가한다. 따라서, 고집적화가 진척될수록 ECC 블록의 고성능화가 요구된다. 독출된 데이터에 포함되는 에러를 정정하는 에러 정정 연산은 상대적으로 긴 시간을 요구한다. 에러 정정 연산에도 불구하고 독출 데이터를 고속으로 호스트에 제공하기 위해서는, 에러 정정 연산에 소요되는 시간을 줄이는 것이 필요하다.

도 1은 독출 데이터 R(x)의 에러를 검출 및 정정하는 메모리 시스템을 보여주는 블록도이다. 도 1을 참조하면, 플래시 메모리 장치(10)로부터의 독출 데이터(Read data) R(x)는 ECC 블록(20)으로 전달된다. ECC 블록(20)에는 독출 데이터 R(x)를 일시적으로 저장하는 내부 버퍼(25)가 포함된다. 그리고 ECC 블록(20)은 독출 데이터 R(x)로부터 에러 정정 벡터 E(x)를 생성하기 위한 신드롬 계산 블록(21), KES 블록(22), 치엔 서치 블록(23)을 포함한다.

신드롬 계산 블록(21)은 독출 데이터 R(x)를 제공받아 신드롬 S(x)를 계산한다. 예를 들면, 신드롬 S(x)는 제공되는 독출 데이터 R(x)에 패리티 검출 다항식 H(x)를 곱함으로써 계산된다. 패리티 검출 다항식 H(x)은 생성 다항식 G(x)의 근을 적용하여 만들어진다. 신드롬 S(x)을 통해서, 독출 데이터 R(x)의 에러 존재 여부가 검출된다. 신드롬 S(x)은 독출 데이터 R(x)에 대한 제반 에러 정보를 포함한다. 즉, 에러의 위치와 패턴 및 에러의 크기까지 포함된다. 따라서, 신드롬 S(x)를 통 해서 독출 데이터 R(x)에 대한 제반 에러 비트의 검출, 에러의 정정 가능성 판단, 에러의 정정 연산이 이루어질 수 있다. 신드롬 계산 블록(21)에 의해서 계산된 신드롬 S(x)는 KES 블록(Key Equation Solver Block, 22)으로 전달된다.

KES 블록(22)은 신드롬 S(x)로부터 에러 위치 다항식(Error Location Polynomial) σ(x)와 에러 패턴 다항식(Error Pattern Polynomial) ω(x)를 구한다. 일반적으로 KES 블록(22)은 유클리드 알고리즘(Euclidean Algorithm: EA), ME(Modified Euclidean) 또는 BM(Berlecamp-Massay) 알고리즘들을 이용하여 구현할 수 있다.

치엔 서치 블록(23)은 에러 위치 다항식 σ(x)와 에러 패턴 다항식 ω(x)을 참조하여 에러 위치 다항식의 근을 계산한다. 그리고 에러 위치 다항식을 통해서 검색된 에러 위치들 각각에 대응하는 오류 크기를 계산한다. 치엔 서치 블록(23)은 치엔 서치 알고리즘(Chien Search Algorithm)을 통해 독출 데이터 R(x)의 에러 위치와 에러 크기를 구하면, 이러한 에러를 정정하기 위한 에러 정정 벡터 E(x)를 출력한다.

내부 버퍼(25)는 독출 데이터 R(x)를 저장하는 버퍼 메모리이다. 일반적으로, 내부 버퍼(25)는 선입 선출(FIFO) 방식의 메모리로 구성된다.

에러 정정 회로(24)는 내부 버퍼(25)에 저장된 독출 데이터 R(x)에 치엔 서치 블록(23)에 의해서 계산된 에러 정정 벡터 E(x)를 곱함으로써 독출 데이터 R(x)에 포함된 에러를 정정한다. 에러가 정정된 독출 데이터 C(x)는 호스트(Host)로 전달된다.

상술한 ECC 블록(20)에 대한 기술이 U.S. Patent No. 6,209,115에 "REED -SOLOMON DECODER AND VLSI IMPLEMENTATION THEREOF"라는 제목으로, U.S. Patent No. 4,694,455에 "DECODING METHOD FOR MULTIPLE BIT ERROR CORRECTION BCH CODES"라는 제목으로 각각 기재되어 있으며, 이 출원의 레퍼런스에 포함된다.

그러나, 상술한 기술들에서는 메모리 시스템으로부터 읽혀진 데이터는 내부 버퍼(24)를 경유하는 버퍼링 경로와 에러의 검출 및 정정을 수행하기 위한 에러 정정 경로를 포함한다. 독출 데이터의 전송에서 발생하는 레이턴시(Latency)는 에러 정정 경로에서 발생하는 레이턴시에 의해서 결정된다. 따라서, 데이터 전송 속도를 높이기 위한 에러 정정 경로의 레이턴시를 최소화하기 위한 기술이 절실히 요구되고 있는 실정이다.

본 발명의 목적은 상술한 제반 문제점을 해결하기 위해 제안된 것으로, 에러 정정 연산에 소요되는 레이턴시를 최소화하여 고속으로 에러 정정된 독출 데이터를 제공할 수 있는 메모리 시스템 및 에러 정정 방법을 제공하는 데 있다.

상기 목적을 달성하기 위한 본 발명에 따른 에러 정정 디코더는, 독출 데이터의 신드롬을 계산하는 신드롬 계산 블록; 상기 독출 데이터에 싱글-비트 에러가 존재하는 경우, 상기 싱글-비트 에러의 위치를 상기 신드롬의 원소들 간의 나눗셈 연산을 이용하여 계산하는 에러 정정 연산 블록; 및 상기 에러의 위치를 참조하여 상기 독출 데이터의 에러를 정정하는 에러 정정 회로를 포함한다. 따라서, 본 발명의 에러 정정 디코더는 1-비트 에러에 대해서 KES 연산과 치엔 서치 연산을 생략할 수 있어 레이턴시를 획기적으로 줄일 수 있다.

상기 목적을 달성하기 위한 본 발명에 따른 블록 코드 데이터의 에러 정정 방법은, (a) 독출 데이터의 신드롬을 계산하는 단계; (b) 상기 신드롬을 참조하여, 상기 독출 데이터의 에러 포함 여부와 상기 에러가 1-비트 에러인지를 판단하는 단계; (c) 상기 독출 데이터에 포함된 에러가 1-비트인 경우, 상기 신드롬의 연속되는 원소들의 나눗셈 연산을 이용하여 에러 위치를 구하는 단계; 및 (d) 상기 에러 위치를 참조하여 상기 독출 데이터의 에러를 정정하는 단계를 포함한다.

상기 목적을 달성하기 위한 본 발명에 따른 메모리 시스템은, 불휘발성 메모리 장치; 및 상기 불휘발성 메모리 장치의 독출 데이터로부터 에러를 제거하기 위한 에러 정정 블록을 포함하는 메모리 컨트롤러를 포함하되, 상기 에러 정정 블록은: 상기 불휘발성 메모리 장치로부터 전송되는 독출 데이터로부터 신드롬을 계산하는 신드롬 계산 블록; 상기 독출 데이터에 싱글-비트 에러가 존재하는 경우, 상기 싱글-비트 에러의 위치를 상기 신드롬의 원소들 간의 나눗셈 연산을 이용하여 계산하는 에러 정정 연산 블록; 및 상기 에러의 위치를 참조하여 상기 독출 데이터의 에러를 정정하는 에러 정정 회로를 포함한다.

이상과 같은 본 발명에 따른 장치 및 방법에 따르면, 싱글-비트 수의 에러 발생 시에 고속의 에러 정정 연산이 가능하며, 따라서, 독출 동작의 속도를 획기적 으로 높일 수 있다.

앞의 일반적인 설명 및 다음의 상세한 설명 모두 예시적이라는 것이 이해되어야 하며, 청구된 발명의 부가적인 설명이 제공되는 것으로 여겨져야 한다. 참조 부호들이 본 발명의 바람직한 실시 예들에 상세히 표시되어 있으며, 그것의 예들이 참조 도면들에 표시되어 있다. 가능한 어떤 경우에도, 동일한 참조 번호들이 동일한 또는 유사한 부분을 참조하기 위해서 설명 및 도면들에 사용된다.

이하에서는, 낸드형(NAND type) 플래시 메모리 장치가 본 발명의 특징 및 기능을 설명하기 위한 한 예로서 사용된다. 하지만, 이 기술 분야에 정통한 사람은 여기에 기재된 내용에 따라 본 발명의 다른 이점들 및 성능을 쉽게 이해할 수 있을 것이다. 본 발명은 다른 실시 예들을 통해 또한, 구현되거나 적용될 수 있을 것이다. 게다가, 상세한 설명은 본 발명의 범위, 기술적 사상 그리고 다른 목적으로부터 상당히 벗어나지 않고 관점 및 응용에 따라 수정되거나 변경될 수 있다. 이하, 본 발명에 따른 실시예를 첨부된 도면을 참조하여 상세히 설명한다. 본 발명에서는 에러 정정 연산을 설명하기 위하여 신드롬 값들을 벡터를 나타내는 알파벳 표현들로 나타내었다.

도 2는 본 발명의 에러 정정 블록(100)의 구성을 보여주는 블록도이다. 도 2를 참조하면, 본 발명의 에러 정정 블록(100)은 에러 비트 수에 따라 다른 방식의 에러 정정 알고리즘을 적용하여 에러 정정 효율을 높일 수 있다. 즉, 본 발명의 에러 정정 블록(100)은 1-비트 에러(또는, 싱글-비트 에러)의 경우와 2-비트 이상의 멀티-비트 에러에 대해서 다른 에러 정정 방법을 적용한다. 이러한 에러 정정 방식에 따라 고속으로 독출 데이터 R(x)의 에러를 제거하여 호스트(Host)로 제공할 수 있다.

플래시 메모리(미도시됨)에서 읽혀진 독출 데이터 R(x)는 에러 검출 및 정정 연산이 수행되는 지연 시간 동안 내부 버퍼(170)에 저장된다. 내부 버퍼(170)는 독출 데이터 R(x)를 선입선출(FIFO) 방식으로 저장하여 출력하게 될 것이다. 에러 정정 블록(100)은 에러 정정 벡터 E(x)를 생성한다. 에러 정정 벡터 E(x)의 생성을 위해서, 독출 데이터 R(x)가 신드롬 계산 블록(Syndrome Computation Block, 110)으로 전달된다. 신드롬 계산 블록(110)은 독출 데이터 R(x)에 패리티 검출 다항식 H(x)를 곱하여 에러 정보인 신드롬 S(x)를 계산한다. 신드롬 S(x)에는 독출 데이터 R(x)에 포함되는 에러의 검출 및 정정을 위한 제반 정보들이 포함된다. 따라서, 신드롬 S(x)를 통해서 독출 데이터 R(x)에 에러가 존재하는지의 여부가 검출된다. 본 발명의 신드롬 계산 블록(110)은 독출 데이터 R(x)에 대응하는 부호어(Code word)에 대한 신드롬 S(x)를 계산하여 출력한다.

신드롬 S(x)를 참조하여 에러 정정을 위한 연산을 수행하는 구성으로는 싱글-비트 에러 정정 블록(120)과 멀티-비트 에러 정정 블록(130)이 있다. 싱글-비트 에러 정정 블록(120)은 독출 데이터 R(x)에 1-비트 에러가 존재하는 경우에 활성화된다. 1-비트 에러는 에러의 위치만을 파악하는 것으로 정정될 수 있다. 따라서, 싱글-비트 에러는 비교적 간단한 에러 정정 연산에 의하여 정정될 수 있다. 싱글-비트 에러 정정 블록(120)은 독출 데이터 R(x)에 포함되는 1-비트 에러를 정정하기 위한 에러 정정 벡터 E_S(x)를 생성한다.

멀티-비트 에러 정정 블록(130)은 독출 데이터 R(x)에 2-비트 이상의 에러가 존재하는 것으로 검출되는 시점에 활성화될 것이다. 멀티-비트 에러 정정 블록(130)은 멀티-비트 에러에 대한 에러 위치 다항식(Error Location Polynomial) 및 에러 평가 다항식(Error Evaluation Polynomial)을 구한다. 멀티-비트 에러 정정 블록(130)은 에러 위치 및 에러 평가 다항식을 참조하여 독출 데이터 R(x)에 포함되는 에러를 정정하기 위한 에러 정정 벡터 E_M(x)를 출력한다.

멀티플렉서(140)는 제어부(160)의 제어에 따라 에러 정정 벡터들 E_S(x)과 E_M(x) 중 어느 하나를 선택한다. 선택된 에러 정정 벡터는 에러 정정 회로(150)에 제공되며, 내부 버퍼(170)에 저장된 독출 데이터 R(x)와 가산된다.

제어부(160)는 신드롬 계산 블록(110)으로부터 신드롬 S(x)를 제공받아, 독출 데이터 R(x)에 에러가 포함되었는지를 판단한다. 만일, 독출 데이터 R(x)에 에러가 포함된 것으로 판정되면, 제어부(160)는 싱글-비트 에러인지 또는 멀티-비트 에러인지를 검출한다. BCH 코드나 RS 코드와 같은 블록 코드의 경우, 신드롬 값에서 다음의 수학식이 성립하는 경우에는 1-비트 에러가 존재하는 것으로 판정한다.

(단, S₁≠0)

제어부(160)는 신드롬 계산 블록(110)으로부터 제공되는 신드롬 S(x)의 원소 들이 수학식 1의 조건을 만족하면, 싱글-비트 에러가 존재하는 것으로 판단한다. 그리고 싱글-비트 에러 정정 블록(120)을 활성화하여 에러 위치를 계산하기 위한 동작을 수행하도록 제어한다. 에러 위치가 계산되면, 제어부(160)는 싱글-비트 에러를 제거하기 위한 에러 정정 벡터 Es(x)를 출력하도록 멀티플렉서(140)를 제어한다.

이상의 구성에 따르면, 본 발명의 에러 정정 블록(100)은 싱글-비트 에러가 발생하는 경우에는 KES 연산과 치엔 서치 연산(Chien Search Operation)을 생략하고 에러 위치를 신드롬 원소들 간의 나눗셈 연산을 통해서 직접 계산한다. 즉, 1-비트 에러의 위치 및 에러 패턴에 대한 정보는 신드롬 원소들의 나눗셈 연산 'S_i ₊₁/S_i'을 통해서 구할 수 있다. 이러한 에러 연산은 간단한 연산 수단이나 알고리즘을 통해서 쉽게 구현될 수 있다. 따라서, 본 발명의 에러 정정 블록(100)은 1-비트 에러 발생시에는 에러 정정 연산을 신속히 수행하며, 레이턴시(Latency)를 최소화할 수 있다.

도 3은 도 2의 싱글-비트 에러 정정 블록(120)의 구성을 보여주는 블록도이다. 싱글-비트 에러 정정 블록(120)은 독출 데이터 R(x)에 1-비트 에러가 존재하는 시점에 활성화된다. 도 3을 참조하면, 싱글-비트 에러 정정 블록(120)은 신드롬 S(x)로부터 KES 알고리즘(Key Equation Solver Algorithm) 및 치엔 서치 연산(Chien Search Operation)을 수행하지 않고 1-비트 에러를 정정하기 위한 에러 정정 벡터 E_S(x)를 생성한다. 즉, 싱글-비트 에러 정정 블록(120)은 에러 위치 다항 식이나 에러 평가 다항식의 생성 및 그 해를 이용하지 않고 신드롬 원소 값만으로 에러의 위치를 계산한다. 에러 정정 연산에서 레이턴시의 대부분을 차지하는 KES 연산과 치엔 서치 연산의 생략이 가능하기 때문에, 1-비트 에러 정정 연산의 속도를 높일 수 있고, 독출 데이터 R(x)의 독출 속도를 높일 수 있다. 좀더 자세히 설명하면 다음과 같다.

역 갈로아-필드 모듈(121)은 계산된 신드롬 값 'Si' 각각의 역수를 계산하기 위한 기능 블록이다. 즉, 갈로아-필드(Galois-Field) 내의 원소 개수에 대응하는 숫자의 룩-업 테이블(Look-up Table)로 구성될 수 있다. 신드롬 'Si'의 역수 '1/Si'를 고속으로 계산하기 위해 고속의 연산기를 사용할 수도 있음은 물론이다. 역 갈로아-필드 모듈(121)은, 예를 들어, 데이터를 512-바이트(Byte)씩 오류 정정 부호화기에서 부호화하는 경우, 512-바이트(Byte)에 오류검출과 정정을 위한 패리티 비트(Parity bits)가 추가되어 총 (512 ×2 × 2³ = 2¹³ )비트 즉, 8192 개의 원소를 가지는 갈로아-필드가 필요하다. 따라서, 13-비트 길이 신드롬의 경우, 역 갈로아-필드 모듈(121)은 미리 8192(=2¹³)개의 인버스 필드(Inverse Field)를 구해놓고, 룩-업 테이블(Look-up Table) 방식으로 신드롬 'S_i'에 대응하는 역수 '1/S_i'를 검색하여 출력할 수 있다.

갈로아-필드 승산기(122)는 신드롬 'S_i'의 역수인 '1/S_i'와 신드롬 'S_i ₊₁'와의 곱셈을 수행한다. 원래 신드롬만으로 에러 위치를 검출하기 위해서 'S_i ₊₁/S_i'를 계산 해야 하나, 나눗셈 연산의 번거로움을 피하기 위하여 갈로아-필드 승산기(122)가 제공된다. 갈로아-필드 승산기(122)에서 출력되는 'S_i ₊₁/S_i' 값은 컨버터(123)에 전달된다. 1-비트 에러의 경우, 신드롬 원소만을 이용한 에러 위치 값은 아래의 수학식 2와 같이 나타낼 수 있다.

, (단, S_i≠0, j는 에러 위치, α는 원시 다항식의 해)

컨버터(123)는 'S_i ₊₁/S_i' 값을 치엔 서치 블록(134)에서 생성되는 에러 위치 및 에러 패턴(L(x), P(x))으로 전환한다. 전환된 에러 패턴은 에러 정정 회로에서 독출 데이터 R(x)의 1-비트 에러를 제거하기 위한 에러 정정 벡터 E_S(x)로 제공된다.

상술한 싱글-비트 에러 정정 블록(120)에서 수행되는 신드롬의 나눗셈 연산 'S_i+1/S_i'은 룩-업 테이블 방식으로 제공된다. 즉, 역 갈로아-필드 모듈(121)은 신드롬 S_i의 역수를 롬 테이블(ROM table)에 저장하고, 저장된 값을 이용하여 나눗셈을 곱셈으로 계산한다. 하드웨어로의 구현이 복잡하고 까다로운 나눗셈기(Divider)의 역할을 롬 테이블과 곱셈기(Multiplier)를 사용하여 계산하기 때문에 고속의 에러 정정 동작을 지원할 수 있다.

도 4는 상술한 도 3의 역 갈로아-필드 모듈(121)의 실시예를 간략히 보여주는 블록도이다. 도 4를 참조하면, 역 갈로아-필드 모듈(121)은 플래시 메모리(미도시됨)와 호스트를 인터페이싱하기 위한 메모리 컨트롤러(미도시됨)의 내부에 포함되는 하드웨어로 구성될 수 있다. 즉, 롬 테이블은 신드롬의 전체 원소들에 대한 역수 값을 저장하고, 입력되는 신드롬 'S_i'값의 역수가 출력되도록 제어된다. 좀더 자세히 설명하면 다음과 같다.

계산된 신드롬 값들이 신드롬 계산 블록(110, 도 2 참조)으로부터 전달되면, i번째 신드롬 'S_i'에 대응하는 역 원소 '1/S_i'가 롬 테이블에서 선택된다. 역 원소는 모든 가능한 신드롬의 필드 값들(8192 = 2¹³개) 각각에 대해서 1:1로 롬 테이블에서 미리 구비된 값들로써 제공된다. 만일 신드롬 'S₃'가 제공되는 경우, 신드롬 'S₃'의 역 원소 '1/S₃'의 값이 출력되도록 롬 테이블이 제어될 것이다.

상술한 롬 테이블을 이용하여 역 원소를 제공하기 위한 역 갈로아-필드 모듈(121)의 구동 알고리즘은 예시적으로 아래의 표와 같이 제공될 수 있다.

always @(Si) begin
case(Si) // synopsys parallel_case full_case
13'b0000000000000: result = 13'b0000000000000;
13'b0000000000001: result = 13'b0000000000001;
13'b0000000000010: result = 13'b1000000001101;
13'b0000000000011: result = 13'b1111111110110;
.
.
13'b1111111111110: result = 13'b1100100010101;
13'b1111111111111: result = 13'b1011101000001;
endcase
end

상술한 알고리즘은 입력되는 신드롬 'S_i' 각각에 대응하는 역 원소 '1/S_i'가 롬 테이블에 저장되어 있는 경우, 'case()' 문을 이용하여 대응하는 역수 값을 출력하도록 결과값(result)들이 지정되어 있다.

도 5는 싱글-비트 에러 정정 블록(120)의 다른 실시예를 보여주는 블록도이다. 싱글-비트 에러 정정 블록(120)은 독출 데이터 R(x)에 1-비트 에러가 존재하는 시점에 활성화된다. 도 5를 참조하면, 싱글-비트 에러 정정 블록(120)은 신드롬으로부터 KES 알고리즘이나 치엔 서치 연산(Chien Search Operation)을 수행하지 않고 1-비트 에러를 정정하기 위한 에러 정정 벡터 E_S(x)를 생성한다. 즉, 싱글-비트 에러 정정 블록(120)은 신드롬만으로 에러의 위치 및 패턴을 계산한다. 도 5의 실시예에서는, 신드롬 연산 'S_i ₊₁/S_i'를 나눗셈(Division) 연산으로 처리한다. 나눗셈 연산을 위한 별도의 나눗셈기(Divider, 124)를 추가하여 나눗셈 연산 'S_i ₊₁/S_i'를 직접 계산하도록 싱글-비트 에러 정정 블록(120)이 구성될 수도 있다. 나눗셈기(124)는 신드롬 'S_i ₊₁'을 피제수(Dividend)로, 그리고 신드롬 'S_i'를 제수(Divisor)로 하여 신드롬 연산을 수행한다. 나눗셈의 결과인 'S_i ₊₁/S_i'는 신드롬만으로 구해지는 에러 위치를 나타낸다. 따라서, 'S_i ₊₁/S_i' 값은 컨버터(123)에 전달되어 에러 위치와 에러 패턴을 나타내는 통상의 에러 정정 벡터 포맷으로 전환될 것이다.

도 6은 나눗셈 연산 'S_i ₊₁/S_i'를 소프트웨어에서 계산해서 에러 정정 블록으 로 돌려주는 방법을 간략히 도시한 실시예의 도면이다. 도 6을 참조하면, 에러 정정 블록의 로드(Load)를 최소화하고, 자원(Resource)의 분배가 가능하다. 신드롬 계산 블록(110)으로부터 입력된 신드롬을 통해서 정정 가능한 에러가 존재하고, 그 에러가 싱글-비트 에러로 판정되면, 인터럽트(Interrupt)에 따라 신드롬은 CPU(125)로 전달된다. CPU(125)는 다음과 같은 알고리즘에 따라서 전달된 신드롬에 대한 나눗셈 연산 'S_i ₊₁/S_i'을 수행한다.

g_num[0] = 0, j = 1;
for(i=1; i<2^13; i++) {
g_num[i] = j;
if(j & 0x1000) {
j <<= 1;
j ^= 0x001b;
} else {
j <<= 1;
}
j &= 0x1fff;
}

for(i=0; i<2^13; i++) {
for(j=0; j<2^13; j++) {
if(i==g_num[j] {
if(j==0) inv = 0;
else if(j==8191) inv = 2^13 -1;
else inv = 2^13 -j -1;
}
}
}

CPU(125)에 의한 상술한 알고리즘 연산이 완료되면, 그 결과 값은 일시 저장되고, 에러 위치를 나타내는 값으로써 에러 정정 블록으로 되돌려진다. 그리고, 에러 위치를 나타내는 연산 결과값 'S_i ₊₁/S_i'는 컨버터(123)에 전달되어, 에러 위치와 에러 패턴을 나타내는 통상의 에러 정정 벡터 포맷으로 전환될 것이다.

이상에서, 신드롬의 나눗셈 연산을 통해 직접 1-비트 에러의 위치를 계산하 기 위한 다양한 연산 방법 및 장치들이 실시예들을 통해서 설명되었다. 하지만, 싱글-비트 에러 정정 블록(120)의 구현 방식은 본 실시예들에만 국한되지는 않으며 다양한 변형이 가능함은 이 분야에서 통상의 지식을 습득한 자들에게는 자명하다.

도 7은 2-비트 이상의 에러가 존재하는 경우에 활성화되는 멀티-비트 에러 정정 블록(130)의 구성을 간략히 보여주는 블록도이다. 도 7을 참조하면, 순방향 치엔 서치(Forward Chien Search)를 수행하여, 치엔 서치와 동시에 에러 정정된 데이터를 출력할 수 있도록 구성되었다. 즉, 백워드 치엔 서치(Backward Chien Search)의 경우, 치엔 서치 동작이 완료된 이후에 독출 데이터를 출력할 수 있다. 그러나 순방향 치엔 서치의 경우, 시드 값 A(x)의 제공으로 하나의 부호어(Code word)에 대한 치엔 서치 검색이 완료되지 않더라도 치엔 서치 검색된 에러 정정 벡터 데이터를 파이프라인 방식으로 출력할 수 있다.

KES 블록(Key Equation Solver Block, 131)은 신드롬 S(x)로부터 에러 위치 다항식 σ(x)와 에러 패턴 다항식 ω(x)를 계산한다. RS(Reed-solomon)방식의 복호에서의 KES 블록(131)은 유클리드 알고리즘(Euclidean Algorithm: EA), ME(Modified Euclidean) 또는 BM(Berlecamp-Massay) 알고리즘들을 이용하여 구현할 수 있으며, Division-free ME 그리고 고속 ME 구조들이 각각 제안되어 있다.

시드 생성기(132)는 치엔 서치 블록(134)에서의 에러 위치 다항식 및 에러 패턴 다항식의 해를 구하는 동작에서 순방향 치엔 서치 동작이 가능하도록 시드값을 미리 제공하기 위한 구성이다. 순방향 치엔 서치 동작을 위해서, 시드 생성기(132)는 부호어(Code word) 즉, 독출 데이터 R(x)의 길이 정보인 (n, k)에 대응 하는 초기 시드 값을 제공하기 위한 구성이다.

갈로아-필드 승산기(133)는 KES 블록(131)으로부터 제공되는 에러 위치 다항식 Λ(x)과 시드 생성기(132)로부터 출력되는 시드 값 A(x)를 곱하여 새로운 에러 위치 다항식 Σ(x)를 생성한다.

치엔 서치 블록(134)은 시드 값 A(x)에 의해서 생성된 새로운 에러 위치 다항식 Σ(x)을 참조하여 순방향 치엔 서치 알고리즘을 실시한다. 이때, 순방향 치엔 서치 알고리즘에 따라 생성되는 에러 정정 벡터는 치엔 서치 동작과 동시에 출력 가능하다. 치엔 서치 동작이 완료된 이후에 에러 정정 벡터의 출력이 가능한 역방향 치엔 서치 동작과 달리, 순방향 치엔 서치 동작에서는 치엔 서치 동작과 동시에 독출 데이터에 대한 에러의 정정 및 출력이 가능하다. 따라서, 치엔 서치 알고리즘을 수행하기 위한 레이턴시를 줄일 수 있다. 치엔 서치 블록(134)에 의한 순방향 치엔 서치 알고리즘에 따라 독출 데이터 R(x)의 에러 위치와 에러 크기가 계산되면, 이러한 에러를 정정하기 위한 에러 정정 벡터 E_M(x)로 출력된다.

이상의 도 3 내지 도 7을 통해 싱글-비트 에러 정정 블록(120)과 멀티-비트 에러 정정 블록(130)의 에러 정정 연산이 설명되었다. 신드롬 S(x)를 통해서 에러의 존재 및 에러 비트 수의 검출이 완료되면, 제어부(160, 도 2참조)는 싱글-비트 에러 정정 블록(120)과 멀티-비트 에러 정정 블록(130) 중 어느 하나를 선택적으로 활성화한다. 그리고, 제어부(160)는 선택된 블록의 계산 결과를 에러 정정 벡터로 출력한다. 출력된 에러 정정 벡터 E(x)는 내부 버퍼(170)에 선입선출 방식으로 저 장된 독출 데이터 R(x)와 가산된다. 모듈러-2 가산(Modular-2 Addition) 방식으로 더해짐으로써, 독출 데이터 R(x)에 포함된 1-비트 에러 또는 2-비트 이상의 멀티-비트 에러는 정정된다. 에러가 정정된 독출 데이터 C(x)는 호스트로 제공될 것이다.

도 8은 상술한 도 2의 제어부(160)에 의해서 수행되는 에러 정정 동작을 간략히 보여주기 위한 흐름도이다. 도 8을 참조하면, 본 발명에 따른 에러 정정 블록은 싱글-비트 에러의 경우에는 신드롬의 나눗셈 연산 'S_i ₊₁/S_i'으로 에러 위치를 계산하여 에러를 정정한다. 멀티-비트 에러인 경우에는, 본 발명의 에러 정정 블록은 순방향 치엔 서치(Forward Chien Search) 방식에 따라 에러 위치 및 에러 패턴을 계산한다. 따라서, 1-비트 에러가 에러의 상당부분을 차지하는 메모리 시스템의 경우라면, 독출 동작의 레이턴시를 획기적으로 줄일 수 있다. 이하에서는 본 발명의 에러 정정 방법이 도 2에서 설명된 구성들에 의거하여 상세히 설명될 것이다.

독출 데이터 R(x)가 전달되면, 에러의 검출 및 정정을 위한 제반 동작들이 시작된다. 독출 데이터 R(x)가 에러 정정 블록에 전달되기 시작하면, 독출 데이터 R(x)에 대한 신드롬 계산이 동시에 수행된다(S10). 신드롬 계산 블록(110)에서 생성되는 신드롬 S(x)를 통해서 제어부(160)는 독출 데이터 R(x)의 에러가 존재하는 지를 판단한다. 즉, 신드롬 S(x)의 값이 모두 0이면 에러가 없는 경우를 의미하고, 기타의 경우에는 독출 데이터 R(x)에 에러가 존재하는 것으로 판단한다. 에러가 존재하지 않으면, 에러 정정 블록의 에러 정정 동작은 종료한다. 그러나, 신드롬 S(x)가 0이 아닌 경우, 제어부(160)는 에러가 존재하는 것으로 판단하고 에러 정정을 위한 단계로 절차를 이동한다(S20). 에러가 존재하는 경우, 제어부(160)는 신드롬 S(x)의 값을 이용하여 싱글-비트 에러인지 또는 멀티-비트 에러인지를 판단한다. 즉, 제어부(160)는 신드롬 S(x)가 수학식 1의 조건을 만족하는지를 검사하고 판단한다. 만일, 신드롬 S(x)가 수학식 1의 조건을 만족하면, 절차는 본 발명의 신드롬만으로 에러 위치를 계산하기 위한 단계 (S40)로 이동한다. 그러나, 신드롬 S(x)의 값이 2-비트 이상의 에러가 존재하는 것으로 판단되면, 절차는 본 발명의 순방향 치엔 서치(Forward Chien Search)에 의한 에러 위치 및 에러 패턴을 구하기 위한 단계(S60)로 이동된다.

우선, 독출 데이터 R(x)에 1-비트 에러가 존재하는 경우에 대해서 설명하기로 한다. 독출 데이터 R(x)에 1-비트 에러가 존재하면, 계산된 신드롬 S(x)의 원소들 중 연속되는 신드롬 원소의 나눗셈 'S_i ₊₁/S_i'값을 구한다. 신드롬 연산 'S_i ₊₁/S_i'를 수행하기 위한 방법으로 이미 롬 테이블에 신드롬 원소들 각각에 대응하는 역 원소들을 저장하여 사용하는 도 4의 실시예에 대해서 설명하였다. 그리고, 나눗셈기(Divider) 및 하드웨어 인터럽트 방식에 따라 소프트웨어에서 계산해서 에러 정정 블록으로 돌려주는 실시예에 대해서도 설명되었다(S41). 상술한 신드롬의 나눗셈 결과값을 참조하여 컨버터(123)는 통상의 에러 정정 회로에서 에러 정정 연산시에 사용하는 에러 위치 및 패턴 정보(L(x), P(x))로 전환한다(S42). 에러 패턴과 에러 위치 계산이 완료되면, 싱글-비트 에러를 정정하는 동작이 진행된다(S50).

만일, 신드롬 S(x)의 값이 멀티-비트 에러를 지시하면, 순방향 치엔 서치를 사용하는 에러 정정 연산이 시작된다. 순방향 치엔 서치 동작을 위해서 에러 위치 다항식 및 에러 패턴 다항식을 구하기 위한 KES 동작이 KES 블록(131)에서 수행된다. 또한, 부호의 길이 정보 (n, k)를 참조하여 시드(Seed) 값이 계산 및 선택된다(S60). 시드 값과 에러 위치 다항식 및 에러 패턴 다항식을 참조하여, 치엔 서치 블록(134)은 결과값을 출력하는 서치 동작과 파이프라인 방식으로 이루어지는 순방향 치엔 서치 동작을 수행한다(S70). 순방향 치엔 서치 동작은 에러 위치 다항식의 차수(deg σ)와 에러 패턴 다항식의 차수(deg ω)가 동일할 때까지 계속된다. 만일, 에러 위치 다항식의 차수(deg σ)와 에러 패턴 다항식의 차수(deg ω)가 동일한 경우에는 에러 정정이 가능한 경우를 의미한다. 이때에는 에러 정정 회로가 에러를 정정하도록 에러 정정 벡터를 제공한다. 반면에, 에러 위치 다항식의 차수(deg σ)와 에러 패턴 다항식의 차수(deg ω)가 다른 경우에는 에러의 정정이 불가함을 의미한다. 이때에는 에러 정정 연산을 종료하여 전달된 독출 데이터 R(x)에 대한 에러 정정 연산을 종료한다(S80).

이상의 동작에 따르면, 본 발명은 싱글-비트 에러의 경우에는 신드롬만으로 에러 패턴을 구하여 에러 정정이 가능하다. 그리고, 멀티-비트 에러의 발생시에는 순방향 치엔 서치 동작이 가능하도록 부호의 길이 정보 (n, k)를 참조하여 시드를 생성한다. 따라서, 본 발명의 에러 정정 알고리즘에 따르면 고속의 에러 정정 기능이 지원될 수 있다.

도 9는 상술한 도 2에서 설명한 본 발명의 에러 정정 블록의 동작을 보여주 는 타이밍도이다. 도 9를 참조하면, 1-비트 에러의 경우에도 동일하게 KES 연산과 치엔 서치 연산을 수행하는 종래 기술과 1-비트 에러의 경우에는 신드롬만으로 에러 패턴을 구하는 본 발명의 동작 타이밍이 도시되어 있다. 1-비트 에러가 포함된 독출 데이터 R(#1, #2) 및 멀티-비트 에러를 포함하는 독출 데이터 R(#3)에 대해서 내부 동작에 따른 레이턴시(Latency) 크기가 상세히 도시되어 있다.

종래의 경우, 1-비트 에러가 존재하는 독출 데이터 R(x)가 전달되면 구간 (T1~T2)에서 신드롬 계산이 이루어진다. 그리고 독출 데이터(#1)에 대한 신드롬을 참조하여 KES 동작(KES Op.), 치엔 서치 동작(Chien Search), 에러 정정 연산(Error Corr.)이 완료된 이후에 호스트로 에러 정정된 독출 데이터 C(#1)의 전송이 시작된다. 따라서, 에러 정정 연산을 위한 KES 동작(KES Op.), 치엔 서치 동작(Chien Search), 에러 정정 연산(Error Corr.)에 소요되는 지연 시간 (ΔT) 만큼의 전체 레이턴시(Total Latency)가 발생한다. 에러 정정 블록의 성능(Performance)은 에러 정정 연산을 위한 KES 동작(KES Op.), 치엔 서치 동작(Chien Search), 에러 정정 연산(Error Corr.)에 소요되는 지연 시간 (ΔT)의 길이에 의해서 결정된다.

본 발명(Present Invention)에 따르면, 플래시 메모리(미도시됨)로부터 독출 데이터 R(#1)의 전송이 시작됨과 동시에 전송된 데이터들에 대한 신드롬 계산이 수행된다. 1-비트 에러가 존재하는 것으로 판단되면, 제어부(160)는 싱글-비트 에러 정정 블록(120)을 활성화한다. 그러면 싱글-비트 에러 정정 블록(120)은 신드롬 원 소들을 이용하여 나눗셈 연산 'S_i ₊₁/S_i'을 수행한다. 이 경우에는 많은 사이클이 소요되는 KES 동작 및 치엔 서치 동작이 생략됨으로써 전체 레이턴시를 (ΔT1) 수준으로 줄일 수 있다. 즉, 에러 정정 연산이 5-사이클(시스템 클록) 이내에 수행될 수 있다. 독출 데이터 R(#2)에서도 이러한 에러 정정 방법은 동일하게 적용된다. 독출 데이터 R(#3)에는 멀티-비트 에러가 포함되어 있다. 따라서, KES 블록(131) 및 치엔 서치 블록(134)의 구동이 필수적이다. 그러나, 순방향 치엔 서치 동작을 통해서 에러 정정 연산에 대응하는 레이턴시를 최소화할 수 있다. 즉, 3-비트 에러가 포함되는 독출 데이터 R(#3)의 입력 이후 에러 정정된 독출 데이터 C(#3)이 전송되는 시점까지의 전체 레이턴시는 (ΔT2) 정도가 소요될 것이다.

이상의 타이밍도에서 설명된 본 발명의 에러 정정 기능에 따르면, 1-비트 에러의 발생시에는 KES 동작, 치엔 서치 동작이 비활성화되고, 신드롬으로부터 수 사이클 이내에 에러 패턴이 결정된다. 따라서, 에러 정정 연산에 의한 레이턴시를 최소화할 수 있다.

도 10은 본 발명의 다른 실시예를 간략히 보여주는 블록도이다. 도 10을 참조하면, 본 발명의 에러 정정 블록(200)은 신드롬 S(x)를 참조하여 에러 비트 수에 따라 에러 정정 알고리즘을 다르게 적용할 수 있다. 즉, 본 발명의 에러 정정 블록(200)은 1-비트 에러(또는, 싱글-비트 에러)의 경우와 2-비트 이상의 멀티-비트 에러에 대해서 다른 에러 정정 방법을 적용한다. 이러한 에러 정정 방식에 따라 고속으로 독출 데이터 R(x)의 에러를 제거하여 호스트(Host)로 제공할 수 있다.

독출 데이터 R(x)는 에러 검출 및 정정 연산이 수행되는 지연 시간 동안 내부 버퍼(290)에 저장된다. 내부 버퍼(290)는 독출 데이터 R(x)를 선입선출(FIFO) 방식으로 저장하여 출력하게 될 것이다. 버퍼링 동작과 동시에, 신드롬 계산 블록(210)은 입력되는 독출 데이터 R(x)의 신드롬 S(x)를 계산한다. 신드롬 계산 블록(210)은 독출 데이터 R(x)에 패리티 검출 다항식 H(x)를 곱하여 에러 정보인 신드롬 S(x)를 계산한다. 계산된 신드롬 S(x)는 제어부(270)와 순방향 정정 블록(260) 특히, KES 블록(220)에 전달된다.

순방향 정정 블록(260)은 멀티-비트 에러의 경우에는 KES 동작 및 순방향 치엔 서치 동작을 수행한다. 그러나, 싱글-비트 에러의 경우에는 KES 동작이 생략되고 순방향 치엔 서치 동작만이 활성화되어 에러 위치 다항식 및 에러 패턴 다항식의 근을 계산한다. 순방향 정정 블록(260)은 KES 블록(220), 시드 발생기(230), 갈로아-필드 승산기(240) 및 치엔 서치 블록(250)이 포함된다.

KES 블록(Key Equation Solver Block, 220)은 신드롬 S(x)로부터 에러 위치 다항식(Error Location Polynomial) σ(x)와 에러 패턴 다항식(Error Pattern Polynomial) ω(x)를 계산한다. RS(Reed-solomon)방식의 복호에서의 KES 블록(220)은 유클리드 알고리즘(EA), ME(Modified Euclidean), BM(Berlecamp-Massay) 알고리즘들을 이용하여 구현할 수 있다. 그러나, KES 블록(220)은 싱글-비트 에러의 경우에 비활성화(Inactivate) 되도록 설정될 것이다.

시드 생성기(230)는 치엔 서치 블록(250)에서의 에러 위치 다항식 및 에러 패턴 다항식의 해를 구하는 동작에서 순방향 치엔 서치 동작이 가능하도록 시드 값 을 미리 제공하기 위한 구성이다. 순방향 치엔 서치 동작을 위해서, 시드 생성기(230)는 부호어(Code word) 즉, 독출 데이터 R(x)의 길이 정보인 (n, k)에 대응하는 초기 시드 값을 제공한다.

갈로아-필드 승산기(240)는 KES 블록(220)으로부터 제공되는 에러 위치 다항식 Λ(x)과 시드 생성기(230)로부터 출력되는 시드 값 A(x)를 곱하여 새로운 에러 위치 다항식 Σ(x)를 생성한다.

치엔 서치 블록(250)은 시드 값 A(x)에 의해서 생성된 새로운 에러 위치 다항식 Σ(x)을 참조하여 순방향 치엔 서치 알고리즘을 실행한다. 이때, 순방향 치엔 서치 알고리즘에 따라 생성되는 에러 정정 벡터는 치엔 서치 동작과 동시에 에러 정정 벡터의 출력이 가능하다. 따라서, 치엔 서치 동작이 완료되어야 하는 역방향 치엔 서치 알고리즘과는 달리 치엔 서치 알고리즘을 수행하기 위한 레이턴시가 절감될 수 있다. 치엔 서치 블록(250)에 의한 순방향 치엔 서치 알고리즘에 따라 독출 데이터 R(x)의 에러 위치와 에러 크기가 계산되면, 이러한 에러를 정정하기 위한 에러 정정 벡터 E(x)로 출력된다. 치엔 서치 블록(250)은 신드롬을 통해서 검출된 에러가 싱글-비트이든 멀티-비트이든 상관없이 활성화된다.

에러 정정 회로(270)는 내부 버퍼(290)로부터의 독출 데이터 R(x)의 에러를 에러 정정 벡터 E(x)를 통해서 정정한다. 그리고 제어부(280)는 신드롬 S(x)를 통하여 독출 데이터 R(x)에 포함되는 에러가 싱글-비트 인지 또는 멀티-비트인지를 판단하여 KES 블록(220)의 활성화 여부를 결정 및 제어한다.

이상의 도 10에 의해서 설명된 실시예에 따르면, 싱글-비트 에러가 검출되는 경우에 싱글-비트 에러를 정정하기 위한 별도의 구성을 추가적으로 구성하지 않고서도 KES 동작에 따른 레이턴시를 줄일 수 있다.

도 11은 상술한 도 10의 에러 정정 블록(280)에서 수행되는 에러 정정 동작을 간략히 보여주기 위한 흐름도이다. 도 11을 참조하면, 본 발명의 다른 실시예에 따른 에러 정정 블록은 싱글-비트 에러의 경우에는 KES 동작을 생략하고, 2-비트 이상의 에러의 경우에는 KES 동작과 순방향 치엔 서치 동작을 수행한다. 이하에서는 본 발명의 에러 정정 방법이 도 10에서 설명된 구성들에 의거하여 상세히 설명될 것이다.

독출 데이터 R(x)가 전달되면, 에러의 검출 및 정정을 위한 제반 동작들이 시작된다. 독출 데이터 R(x)가 에러 정정 블록에 전달되기 시작하면, 독출 데이터 R(x)에 대한 신드롬 계산이 동시에 수행된다(S110). 신드롬 계산 블록(210)에서 생성되는 신드롬 S(x)를 통해서 제어부(280)는 독출 데이터 R(x)의 에러가 존재하는 지를 판단한다. 즉, 신드롬 S(x)의 값이 0이면 에러가 없는 경우를 의미하고, 기타의 경우에는 독출 데이터 R(x)에 에러가 존재하는 것으로 판단한다. 에러가 존재하지 않으면, 에러 정정 블록의 에러 정정 동작은 종료한다. 그러나, 신드롬 S(x)가 0이 아닌 경우, 제어부(280)는 에러가 존재하는 것으로 판단하고 에러 정정을 위한 단계로 절차를 이동한다(S120). 에러가 존재하는 경우, 제어부(280)는 신드롬 S(x)의 값을 이용하여 싱글-비트 에러인지 또는 멀티-비트 에러인지를 판단한다. 즉, 제어부(280)는 신드롬 S(x)가 수학식 1의 조건을 만족하는지를 검사하고 판단한다. 만일, 신드롬 S(x)가 수학식 1의 조건을 만족하면, 절차는 KES 동작 없이 순방향 치엔 서치 동작만을 수행하기 위한 단계 (S140)로 이동한다. 그러나, 신드롬 S(x)의 값이 2-비트 이상의 에러가 존재하는 것으로 판단되면, 절차는 KES 동작 및 순방향 치엔 서치에 의한 에러 위치 및 에러 패턴을 구하기 위한 단계(S170)로 이동된다.

우선, 독출 데이터 R(x)에 1-비트 에러가 존재하는 경우에 대해서 설명하기로 한다. 독출 데이터 R(x)에 1-비트 에러가 존재하면, 순방향 치엔 서치 동작을 지원하기 위한 시드 값 A(x)가 계산된다. 시드 값 A(x)는 부호의 길이 정보 (n, k)를 참조하여 선택될 수 있다. 그러나, KES 동작을 통한 에러 위치 다항식 및 에러 패턴 다항식의 계산은 생략된다(S140). 시드 값 A(x)가 제공되면, 치엔 서치 블록(250)은 순방향 치엔 서치 동작을 실시한다(S150). 이후에는 순방향 치엔 서치 동작을 통해서 제공되는 에러 패턴을 이용하여 독출 데이터 R(x)에 포함되는 싱글-비트 에러가 정정된다(S160).

만일, 신드롬 S(x)의 값이 멀티-비트 에러를 지시하면, 순방향 치엔 서치를 사용하는 에러 정정 연산이 시작된다. 순방향 치엔 서치 동작을 위해서 에러 위치 다항식 및 에러 패턴 다항식을 구하기 위한 KES 동작이 KES 블록(220)에서 수행된다. 또한, 부호 길이 정보 (n, k)를 참조하여 시드 값 A(x)가 계산 또는 선택된다(S170). 시드 값과 에러 위치 다항식 및 에러 패턴 다항식을 참조하여, 치엔 서치 블록(250)은 치엔 서치 동작과 동시에 파이프라인 방식으로 이루어지는 순방향 치엔 서치 동작을 수행한다(S180). 그리고 계산된 에러 패턴으로 에러 정정이 가능한지를 판단하기 위해, 에러 위치 다항식의 차수(deg σ)와 에러 패턴 다항식의 차 수(deg ω)가 비교된다. 만일, 에러 위치 다항식의 차수(deg σ)와 에러 패턴 다항식의 차수(deg ω)가 동일한 경우에는 에러 정정이 가능한 경우를 의미한다. 이때에는 에러 정정 회로가 에러를 정정하도록 에러 정정 벡터를 제공한다. 반면에, 에러 위치 다항식의 차수(deg σ)와 에러 패턴 다항식의 차수(deg ω)가 다른 경우에는 에러의 정정이 불가함을 의미한다. 이때에는 에러 정정 연산을 종료하여 전달된 독출 데이터 R(x)에 대한 에러 정정 연산을 종료한다(S190).

이상의 동작에 따르면, 본 발명은 싱글-비트 에러의 경우에는 KES 블록의 동작을 비활성화하고 순방향 치엔 서치 동작만을 수행한다. 반면에, 멀티-비트 에러의 발생시에는 KES 블록의 동작을 활성화하고, KES 동작을 통해서 생성된 에러 위치 다항식 및 에러 패턴 다항식을 순방향 치엔 서치 방식으로 구하는 동시에 에러를 정정한다. 따라서, 본 발명의 에러 정정 알고리즘에 따르면 고속의 에러 정정 기능이 지원될 수 있다.

도 12는 상술한 도 11의 동작을 간략하게 보여주는 타이밍도이다. 도 12를 참조하면, 본 발명 에러 정정 블록은 싱글-비트 에러의 경우에는 KES 동작을 생략하고 순방향 치엔 서치 동작을 통해서 1-비트 에러를 정정한다. 도 11의 동작을 1-비트 에러 포함되는 독출 데이터 R(#1, #2) 및 멀티-비트 에러가 포함되는 독출 데이터 R(#3)가 연속적으로 입력되는 경우를 가정하여 설명하기로 한다.

종래의 경우, 1-비트 에러가 존재하는 독출 데이터 R(x)가 전달되면 구간 (T1~T2)에서 신드롬 계산이 이루어진다. 그리고 독출 데이터(#1)에 대한 신드롬을 참조하여 KES 동작(KES Op.), 치엔 서치 동작(Chien Search), 에러 정정 연 산(Error Corr.)이 완료된 이후에 호스트로 에러 정정된 독출 데이터 C(#1)의 전송이 시작된다. 따라서, 에러 정정 연산을 위한 KES 동작(KES Op.), 치엔 서치 동작(Chien Search), 에러 정정 연산(Error Corr.)에 소요되는 지연 시간 (ΔT) 만큼의 전체 레이턴시(Total Latency)가 발생한다. 에러 정정 블록의 성능(Performance)은 에러 정정 연산을 위한 KES 동작(KES Op.), 치엔 서치 동작(Chien Search), 에러 정정 연산(Error Corr.)에 소요되는 지연 시간 (ΔT)의 길이에 의해서 결정된다.

본 발명(Present Invention)에 따르면, 1-비트 에러가 포함되는 독출 데이터 R(#1, #2) 및 연속되는 3-비트 에러가 포함되는 독출 데이터 R(#3)가 제공되는 경우를 가정하고 설명하기로 한다. 먼저, 플래시 메모리(미도시됨)로부터 독출 데이터 R(#1)의 전송이 시작됨과 동시에 전송된 데이터들에 대한 신드롬 계산이 연속적으로 수행된다. 1-비트 에러의 존재하는 것으로 판단되면, 제어부(280)는 KES 블록(220)을 비활성화하고, 시드 값 A(x)에 따른 순방향 치엔 서치 동작을 실시한다. 따라서, 1-비트 에러의 정정을 위해서는 KES 동작에 소요되는 시간 지연이 사라진다. 1-비트 에러의 경우 상대적으로 짧은 전체 레이턴시 (ΔT3)가 발생한다. 이러한 시간 지연은 1-비트 에러를 포함하는 독출 데이터 R(#1, #2)에 동일하게 적용된다. 그러나, 독출 데이터 R(#3)에는 3-비트의 멀티-비트 에러가 포함되어 있다. 따라서, KES 동작(KES Op.) 및 순방향 치엔 서치(Forward Chien Search) 동작이 필수적이다. 그러나, 순방향 치엔 서치 동작을 통해서 에러 정정 연산에 대응하는 레이턴시를 최소화할 수 있다. 즉, 3-비트 에러가 포함되는 독출 데이터 R(#3)의 입력 이후 에러 정정된 독출 데이터 C(#3)이 전송되는 시점까지의 전체 레이턴시는 (ΔT2) 정도가 소요될 것이다.

이상의 타이밍도에서 설명된 본 발명의 에러 정정 기능에 따르면, 1-비트 에러의 발생시에는 KES 동작이 비활성화되고, 순방향 치엔 서치 동작만으로 에러 패턴을 결정한다. 따라서, 1-비트 에러를 정정하기 위한 구성을 별도로 추가하지 않고도 레이턴시를 감소시킬 수 있다.

도 13은 본 발명의 에러 정정 블록을 구비하는 메모리 시스템(300)의 일예를 간략히 보여주는 블록도이다. 본 발명의 메모리 시스템(300)은 메모리 카드 또는 반도체 디스크 장치(Solid State Disk: SSD)로 구성될 수 있다. 도 13을 참조하면, 고용량의 데이터 저장 능력을 지원하기 위한 메모리 시스템(300)은 본 발명의 에러 정정 블록(324)을 포함하는 메모리 컨트롤러(320)와 불휘발성 메모리 장치(310)를 포함한다. 불휘발성 메모리 장치(310)로부터의 독출 데이터는 메모리 컨트롤러(320)의 에러 정정 블록(324)에서 에러 정정 연산을 거친 후에 호스트로 제공될 것이다.

SRAM(321)은 프로세싱 유닛(322)의 동작 메모리로써 사용된다. 호스트 인터페이스(323)는 메모리 시스템(300)과 접속되는 호스트의 데이터 교환 프로토콜을 구비한다. 에러 정정 블록(324)은 불휘발성 메모리 장치(310)로부터 독출된 데이터에 포함되는 에러를 검출 및 정정한다. 에러 정정 블록은 본 발명의 도 2 또는 도 10에서 설명한 에러 정정 블록과 동일한 기능을 갖는다. 메모리 인터페이스(325)는 본 발명의 불휘발성 메모리 장치(310)와 인터페이싱 한다. 프로세싱 유닛(322)은 메모리 컨트롤러(320)의 데이터 교환을 위한 제반 제어 동작을 수행한다. 비록 도면에는 도시되지 않았지만, 본 발명에 따른 메모리 시스템(300)은 호스트(Host)와의 인터페이싱을 위한 코드 데이터를 저장하는 ROM(미도시됨) 등이 더 제공될 수 있음은 이 분야의 통상적인 지식을 습득한 자들에게 자명하다.

또한, 상술한 불휘발성 메모리 장치(310)는 플래시 메모리 장치(Flash Memory Device)로 구성될 수 있으며, PRAM(Phase Change Random Access Memory)이나 RRAM(Resistance Random Access Memory)과 같은 저항 메모리(Resistive Memory)로 구성될 수 있다. 뿐만 아니라, 불휘발성 메모리 장치(310)는 NFGM(Nano Floating Gate Memory), PoRAM(Polymer Random Access Memory), MRAM(Magnetic Random Access Memory), FRAM(Ferroelectric Random Access Memory) 등을 기억 소자들 중 어느 하나를 사용하는 메모리 장치로 구성될 수 있다. 도면에서 불휘발성 메모리 장치(310)는 하나의 패키지에 하나의 칩이 포함되는 싱글 칩 또는 복수의 불휘발성 메모리 장치들을 하나의 패키지에 장착하는 멀티 칩 패키지(MCP) 형태로 구성될 수 있음은 이 분야에서 통상의 지식을 습득한 자들에게는 자명하다.

상술한 메모리 시스템(300)은 반도체 디스크 장치(SSD)로 구성될 수 있으며, 이 경우 반도체 디스크 장치(SSD)의 고용량화를 용이하게 구현할 수 있다. 비록 도면에는 도시되지 않았지만, 본 발명에 따른 메모리 시스템(300)은 응용 칩셋(Application Chipset), 카메라 이미지 프로세서(Camera Image Processor:CIS), 모바일 디램 등과 결합하여 고용량의 데이터를 교환할 수 있는 정보 처리 기기의 저장 장치로 제공될 수 있음은 이 분야의 통상적인 지식을 습득한 자들에게 자명하 다. 본 발명의 메모리 시스템(300)은 MMC 카드(Multimedia Card), SD 카드(Secure Digital Card), 마이크로 SD 카드, 메모리 스틱(Memory Stick), ID 카드, PCMCIA 카드, 칩 카드(Chip Card), USB 카드, 스마트 카드(Smart Card), CF 카드(Compact Flash Card) 등으로 더 구성될 수 있다.

또한, 본 발명에 따른 메모리 시스템(300)은 다양한 형태들의 패키지로 실장 될 수 있다. 예를 들면, 본 발명에 따른 메모리 시스템은 PoP(Package on Package), Ball grid arrays(BGAs), Chip scale packages(CSPs), Plastic Leaded Chip Carrier(PLCC), Plastic Dual In-Line Package(PDIP), Die in Waffle Pack, Die in Wafer Form, Chip On Board(COB), Ceramic Dual In-Line Package(CERDIP), Plastic Metric Quad Flat Pack(MQFP), Thin Quad Flatpack(TQFP), Small Outline(SOIC), Shrink Small Outline Package(SSOP), Thin Small Outline(TSOP), Thin Quad Flatpack(TQFP), System In Package(SIP), Multi Chip Package(MCP), Wafer-level Fabricated Package(WFP), Wafer-Level Processed Stack Package(WSP) 등과 같은 방식으로 패키지화되어 실장될 수 있다.

도 14는 본 발명에 따른 메모리 시스템을 장착하는 컴퓨팅 시스템(400)을 간략히 보여주는 블록도이다. 도 14를 참조하면, 모바일 기기나 데스크 톱 컴퓨터와 같은 정보 처리 시스템에 본 발명의 메모리 시스템(410)이 장착된다. 본 발명에 따른 컴퓨팅 시스템(400)은 메모리 컨트롤러(411) 및 불휘발성 메모리 장치(412)로 구성되는 메모리 시스템(410)과 각각 버스(460)에 전기적으로 연결된 중앙처리장치(420), 램(430), 유저 인터페이스(440), 모뎀(450)을 포함한다. 메모리 시스 템(410)은 앞서 언급된 메모리 카드 또는 메모리 시스템과 실질적으로 동일하게 구성될 것이다. 불휘발성 메모리 장치(412)에는 유저 인터페이스(440)를 통해서 제공되거나 또는, 중앙처리장치(420)에 의해서 처리된 데이터가 메모리 컨트롤러(411)를 통해 저장된다. 여기서, 메모리 시스템(410)을 장착하는 호스트에 대응하는 중앙처리장치(420) 및 기타 구성들은 고신뢰성을 갖는 데이터를 메모리 시스템(410)으로부터 제공받을 수 있다. 상술한 컴퓨팅 시스템(400)은 데스크 탑 컴퓨터, 노트북 컴퓨터, 휴대 전화와 같은 모바일 기기에 장착되어 데이터 저장 수단으로 사용될 수 있다.

도시되지 않았지만, 본 발명에 따른 컴퓨팅 시스템(400)에는 응용 칩셋(Application Chipset), 카메라 이미지 프로세서(Camera Image Processor: CIS) 등이 더 제공될 수 있음은 이 분야의 통상적인 지식을 습득한 자들에게 자명하다.

이상에서와 같이 도면과 명세서에서 최적 실시예가 개시되었다. 여기서 특정한 용어들이 사용되었으나, 이는 단지 본 발명을 설명하기 위한 목적에서 사용된 것이지 의미 한정이나 특허청구범위에 기재된 본 발명의 범위를 제한하기 위하여 사용된 것은 아니다. 그러므로 본 기술 분야의 통상의 지식을 가진 자라면 이로부터 다양한 변형 및 균등한 타 실시예가 가능하다는 점을 이해할 것이다. 따라서, 본 발명의 진정한 기술적 보호 범위는 첨부된 특허청구범위의 기술적 사상에 의해 정해져야 할 것이다.

도 1은 에러 정정 블록의 간략한 구성을 보여주는 블록도;

도 2는 본 발명의 일 실시예에 따른 에러 정정 블록을 보여주는 블록도;

도 3은 도 2의 싱글-비트 에러 정정 블록의 구성을 보여주는 블록도;

도 4는 도 3의 싱글-비트 에러 정정 블록의 구현 예를 보여주는 블록도;

도 5는 도 2의 싱글-비트 에러 정정 블록의 다른 예를 보여주는 블록도;

도 6은 도 2의 싱글-비트 에러 정정 블록의 또 다른 예를 보여주는 블록도;

도 7은 도 2의 멀티-비트 에러 정정 블록의 구현 예를 보여주는 블록도;

도 8은 본 발명의 에러 정정 동작을 보여주는 순서도;

도 9는 본 발명의 에러 정정 동작을 보여주는 타이밍도;

도 10은 본 발명의 다른 실시예에 따른 에러 정정 블록을 보여주는 블록도;

도 11은 도 10의 에러 정정 블록의 동작을 보여주는 순서도;

도 12는 도 10의 에러 정정 블록의 동작을 보여주는 타이밍도;

도 13은 본 발명의 메모리 시스템을 간략히 보여주는 블록도; 및

도 14는 본 발명의 컴퓨팅 시스템을 간략히 보여주는 블록도.

*도면의 주요 부분에 대한 부호의 설명*

10 : 플래시 메모리 20, 100, 200 : 에러 정정 블록

21, 110, 210 : 신드롬 계산 블록 22, 131, 220 : KES 블록

23, 134, 250 : 치엔 서치 블록 24, 150, 270 : 에러 정정 회로

25, 170, 290 : 내부 버퍼 120 : 싱글-비트 에러 정정 블록

121 : 역 갈로아-필드 모듈 122, 133, 240 : 갈로아-필드 승산기

123 : 컨버터 124 : 나눗셈기

130 : 멀티-비트 에러 정정 블록 132, 230 : 시드 발생기

140 : 멀티플렉서 160, 280 : 제어부

300 : 메모리 시스템 310 : 플래시 메모리

320 : 메모리 컨트롤러 321 : 에스램

322 : 프로세싱 유닛 323 : 호스트 인터페이스

324 : 에러 정정 블록 325 : 메모리 인터페이스

400 : 컴퓨팅 시스템 410 : 메모리 시스템

411 : 메모리 컨트롤러 412 : 플래시 메모리

420 : CPU 430 : RAM

440 : 유저 인터페이스 450 : 모뎀

Claims

독출 데이터의 신드롬을 계산하는 신드롬 계산 블록;

상기 신드롬을 이용한 순방향 치엔 서치 동작을 수행하여 에러의 위치 및 에러 패턴을 계산하는 멀티-비트 에러 정정 블록과 상기 신드롬의 원소들 간의 나눗셈 연산을 수행하여 상기 에러의 위치를 계산하는 싱글-비트 에러 정정 블록을 포함하는 에러 정정 연산 블록; 및

상기 에러의 위치를 참조하여 상기 독출 데이터의 에러를 정정하는 에러 정정 회로를 포함하되,

상기 독출 데이터에 싱글-비트 에러가 존재하는 경우, 상기 에러 정정 연산 블록은 상기 싱글-비트 에러 정정 블록만을 이용하여 상기 에러의 위치를 계산하는 에러 정정 디코더.
삭제
삭제
제 1 항에 있어서,

상기 싱글-비트 에러 정정 블록은:

상기 신드롬의 제 1 원소(S_i)의 역원소(1/S_i)를 제공하는 인버스 갈로아-필드 모듈; 및

상기 역원소(1/S_i)와 상기 신드롬의 제 2 원소(S_i+1)의 갈로아-필드 곱셈을 수행하여 에러 위치 함수(S_i+1/S_i)로 출력하는 갈로아-필드 승산기를 포함하는 에러 정정 디코더.
삭제
삭제
제 4 항에 있어서,

상기 인버스 갈로아-필드 모듈은 상기 신드롬의 모든 원소들 각각에 대응하 는 역원 값을 갖는 롬 테이블을 포함하며, 상기 롬 테이블은 상기 제 1 원소(S_i)의 크기에 응답하여 상기 역원소(1/S_i)의 값을 제공하는 룩-업 테이블 방식으로 구동되는 에러 정정 디코더.
제 4 항에 있어서,

상기 인버스 갈로아-필드 모듈은 갈로아-필드 상에서의 상기 제 1 원소(S_i)의 역원소(1/S_i)를 계산하는 소프트웨어 모듈로 제공되는 에러 정정 디코더.
제 1 항에 있어서,

상기 싱글-비트 에러 정정 블록은:

상기 신드롬의 제 1 원소(S_i)를 젯수(Divisor)로, 상기 신드롬의 제 2 원소(S_i+1)를 피젯수(Dividend)로 하여 갈로아-필드 나눗셈을 수행하는 나눗셈기; 및

상기 나눗셈기의 출력인 에러 위치 함수(S_i+1/S_i)를 상기 독출 데이터의 에러를 제거하기 위한 에러 정정 데이터의 포맷으로 변환하는 컨버터를 포함하는 에러 정정 디코더.
제 1 항에 있어서,

상기 멀티-비트 에러 정정 블록은:

상기 신드롬으로부터 에러 위치 다항식과 에러 평가 다항식을 생성하는 KES 블록;

상기 독출 데이터의 부호 길이 정보(n, k)를 참조하여 치엔 서치 동작을 위한 시드 값을 생성하는 시드 생성기; 및

상기 시드 값을 참조하여 상기 에러 위치 다항식과 에러 평가 다항식의 해를 순방향 치엔 서치 방식으로 계산하는 치엔 서치 블록을 포함하는 에러 정정 디코더.
삭제
제 1 항에 있어서,

상기 독출 데이터는 블록 코드(Block code) 방식의 에러 정정 코드를 포함하는 에러 정정 디코더.
삭제
삭제
삭제
삭제
삭제
삭제
삭제
불휘발성 메모리 장치; 및

상기 불휘발성 메모리 장치의 독출 데이터로부터 에러를 제거하기 위한 에러 정정 블록을 포함하는 메모리 컨트롤러를 포함하되,

상기 에러 정정 블록은:

상기 불휘발성 메모리 장치로부터 전송되는 독출 데이터로부터 신드롬을 계산하는 신드롬 계산 블록;

상기 신드롬을 이용한 순방향 치엔 서치 동작을 수행하여 에러의 위치 및 에러 패턴을 계산하는 멀티-비트 에러 정정 블록과 상기 신드롬의 원소들 간의 나눗셈 연산을 수행하여 상기 에러의 위치를 계산하는 싱글-비트 에러 정정 블록을 포함하는 에러 정정 연산 블록; 및

상기 에러의 위치를 참조하여 상기 독출 데이터의 에러를 정정하는 에러 정정 회로를 포함하고,

상기 독출 데이터에 싱글-비트 에러가 존재하는 경우, 상기 에러 연산 블록은 상기 싱글-비트 에러 정정 블록만을 이용하여 상기 에러의 위치를 계산하는 메모리 시스템.
삭제
삭제
삭제
삭제
삭제