KR20030095249A

KR20030095249A - 리드-솔로몬 디코더

Info

Publication number: KR20030095249A
Application number: KR10-2003-0035677A
Authority: KR
Inventors: 알렉산더 크라브트첸코
Original assignee: 톰슨 라이센싱 소시에떼 아노님
Priority date: 2002-06-07
Filing date: 2003-06-03
Publication date: 2003-12-18
Also published as: EP1370003A1; JP2004032737A; TWI227599B; TW200308149A; CN1467918A; US20030229841A1

Abstract

본 발명은 리드-솔로몬 디코더에 관한 것으로, 상기 리드-솔로몬 디코더는,

- 신드롬 다항식(syndrome polynomial){S(x)} 및 소거 위치자 다항식(erasure locator polynomial){}을 계산하기 위한 수단과;

- 변형 신드롬 다항식{}을 계산하기 위한 수단으로서, 여기서 t는 리드-솔로몬 코드의 심볼-에러 정정 성능인, 계산 수단과;

- 에러 위치자 다항식{} 및 에러 평가자 다항식(error evaluator polynomial){}을 계산하기 위해 유클리드 알고리듬(Euclid's algorithm)을 수행하기 위한 수단과;

- 제 2 에러/소거 위치자 다항식{}을 계산하기 위한 수단과;

- 병렬 치엔 검색(parallel Chien search)을 수행하기 위한 수단과;

- 포르네이 방정식(Forney's equation)에 따라 에러 크기를 직렬로 계산하기 위한 수단을 포함한다.

본 발명은 에러 위치 및 에러 값을 계산하기 위해 필요한 사이클의 수를 감소시키고, 동시에, 비교적 작은 복잡도만을 갖는 하드웨어를 필요로 한다.

Description

리드-솔로몬 디코더{REED-SOLOMON DECODER}

본 발명은 일반적으로 에러 검출/정정에 관한 것으로, 더 상세하게는, 리드-솔로몬 디코더에서 사용되는 시스템 및 방법에 관한 것이다.

일반적으로 사용되는 에러 정정 기술은 리드-솔로몬 에러 정정 코드이다. 리드-솔로몬(RS) 기술을 사용하면, 고정-길이 (n) 코드워드가 전송되는데, 각각의 코드워드는 k 개의 정보 심볼과 n-k 개의 첨부된 에러 정정 (패리티) 심볼을 포함한다. 각각의 심볼은 s개의 비트를 포함한다. RS 디코더는 코드워드에 에러를 포함하고 있는 최대 (n-k)/2 개까지의 심볼을 정정할 수 있다.

그런 정정가능한 심볼 각각은 다중 비트-에러를 포함하고 있을 수 있기 때문에, 다중 연속 비트에 영향을 주는 버스트 에러에 대해서는 RS 인코딩 기술이 특별히 매우 적합하다. 일반적인 RS 인코딩 방식은 255 개의 8비트 심볼로 이루어진 코드워드를 사용하는데, 그 중 223 개의 심볼은 정보 심볼이고, 나머지 32 개의 심볼은 에러 정정용 패리티 심볼이다. 그러한 인코딩 방식은 매 255 비트 코드워드에서 최대 16 개까지의 에러가 있는 심볼을 정정할 것이고, 그로 인해 '수신되는' 비트 에러율에 있어서 실질적으로 상당한 향상을 제공한다.

RS 인코딩 방식은 또한 알려진 위치에서의 에러인 '소거(erasure)'를 검출할 것이며, 보다 적은 정보를 정정할 필요가 있을 것이다. RS 디코더가 정정할 수 있는 에러 수의 두 배와 소거 수의 합은 (n-k)/2이다.

참조하기 쉽도록 하기 위해서, 용어 '에러'는, 이후로는, 알려지지 않은 위치의 에러나 알려진 위치의 소거 중 어느 하나를 지칭하기 위해 사용된다.

도 1은 종래 RS 디코더(100)의 블록도에 대한 예를 도시한다. 디코더(100)는 각각의 코드워드{r(x)}(101)를 수신한 후, 정정된 코드워드{c(x)}(151)를 생성한다. 신드롬 계산기(syndrome calculator)(110)는 대응하는 신드롬 다항식{S_i(x)}(111)를 생성하기 위해서 코드워드(101)를 처리한다. 각각의 코드워드는 n-k 개의 신드롬을 갖는데, 그 신드롬은 에러에만 의존하고 전송된 코드워드에는 의존하지 않는다. 그러한 신드롬(111)으로부터, 에러 위치자 다항식{}(121)이 생성된다. 비록 버르레캄프-마세이 알고리듬(Berlekamp-Massey algorithm)과 같은 다른 기술도 사용될 수 있지만, 에러 위치자 다항식(121)과 에러 크기 다항식{}(122)를 제공하기 위한 유클리드 알고리듬(Euclid's algorithm)(120)이 도시되어 있다. 각각의 RS 코드는 그 RS 코드를 위해 선택되는 갈로아 필드(GF : Galois Field)의 원시 원소인 파라미터 ''를 갖는다. 에러 위치자 다항식은, 에러가 p인 지점에서 발생하는 경우에가 에러 다항식의 근(root)이 되도록 구성된다(p는 '0'부터 n-1까지로 인덱싱된다).

X_k ^-1에서 에러 위치자 다항식(121)의 근인를 결정하기 위해서 코드워드의 각 위치(p)에 대한의 각 값을 테스트하는데는 반복적인 해결방법이 전통적으로 적용되고 있다. 그러한 반복적인 테스트를 위해 일반적으로 사용되는 알고리듬은 치엔 에러 위치자(Chien error locator)(130)이다. 치엔 위치자(130)도 또한, 블록(140)에 도시된 바와 같이, 전형적으로 포르네이 에러 결정 알고리듬(Forney error determination algorithm)을 통해, 에러 크기(141)의 결정을 용이하게 하는 관련된 에러 미분 항(132)를 제공한다.

에러 결정기(140)는 찾아진 에러 심볼에 대응하는 에러 크기 다항식(122)을 평가한다. 에러 위치자(130)가 위치하는 각각의 에러에 대해서, 에러 정정기(150)는 그 에러의 위치(131) 및 크기(141)에 기초해서 정정된 코드워드{c(x)}(151)를 결정한다. 만약 정해진 심볼에 대해서 에러가 검출되지 않는다면, 그 평가된 위치에서의 정정된 코드워드{c(x)}(151) 내의 심볼은 수신된 코드워드{r(x)}(101) 내의 심볼과 동일하다.

WO-A-01/39378호에서는 에러 크기 다항식 및 에러 위치자 다항식의 m 개의 근을 동시에 검색하는 리드-솔로몬 디코더가 도시되어 있다. 다항식 평가자는 다항식의 각 항에 대응하는 복수의 슬라이스 원소(slice element)를 구비한다. 각각의 슬라이스 원소는 상이한 값에 대한 항을 평가하도록 구성되는 복수의 계수 곱셈기를 구비함으로써, 그러한 상이한 값 각각에서 다항식의 동시적인 평가를 실행한다.

US-B-6 279 137호에서는 저장-효율적인 병렬 치엔 검색(storage-efficient parallel Chien search)을 위한 시스템 및 방법이 도시되어 있다. 그 시스템은, 치엔 검색을 구현하고 필요한 저장의 양을 감소시키는 병렬 구조를 사용하여 다항식의 근을 결정한다.

코드워드에서 에러의 위치는 에러 위치자 다항식의 근으로부터 유도될 수 있다. 치엔 검색의 성능은 병렬 구조에 의해 향상되고, 에러의 위치는 사이클 카운트(cycle count), 병행(parallelism), 및 근을 나타내는 곱셈기/합산기 랭크의 인덱스를 바람직하게도 포함하는 간단한 계산을 사용하여 쉽게 결정될 수 있다. 다중 랭크의 곱셈기는 데이터 저장 유닛으로 이루어진 단일 어레이에 저장된 데이터를 수신한다. 각 곱셈기의 곱셈기 값은 갈로아 필드의 원소에 기초한다.

EP-A-1 102 406호에는 리드-솔로몬 코드를 디코딩하는데 사용되는 디코더 회로가 도시되어 있다. 수신되는 코드워드에 대한 에러 위치자 다항식을 결정하는 치엔 검색 및 에러 패턴을 계산하는 포르네이 알고리듬의 동시 실행을 수행하는 디코더가 제공된다.

US-B-6 347 389호에는 파이프라인식 리드-솔로몬 에러/소거 디코더가 다중 코드 워드를 파이프라인 형태로 처리하는 것이 도시되어 있다.

그 파이프라인식 리드-솔로몬 에러/소거 디코더는 간단한 반복성의 변형 신드롬 처리를 통해 소거뿐만 아니라 에러를 처리함으로써 디지털 시스템 내의 손상되어진 리드-솔로몬 인코딩 워드를 처리하도록 설계된다.

본 발명에 의해서 해결될 과제는 향상된 리드-솔로몬 디코더와 향상된 리드-솔로몬 디코딩 방법을 제공하는 것이다. 또한, DVD 시스템과 같은, 리드-솔로몬 디코더를 구비하는 향상된 전자 시스템을 제공하는 것이다.

그러한 과제는 근본적으로 독립항의 특징을 응용함으로써 해결된다. 본 발명의 바람직한 실시예는 종속항에서 제공된다.

본질적으로, 본 발명은 병렬 치엔 검색(parallel Chien search)을 변형 직렬 포르네이 계산(modified serial Forney's computation)과 결합함으로써 향상된 리드-솔로몬 디코딩을 제공한다. 그것은 디코더의 필수적인 하드웨어 복잡도를 감소시키는 반면에 디코더의 성능은 증가시킬 수 있다.

본 발명에 따라, 병렬 치엔 검색 블록에서는 에러 지점만이 계산된다. CD 또는 DVD 시스템에서, 소거 위치는 이미 CD 또는 DVD 시스템의 복조 블록으로부터 알려져 있기 때문에 치엔 검색에서 계산될 필요가 없다.

일반적으로 "근(root)"으로서 지칭되고 있는 소거 위치가 알려져 있기 때문에, 병렬 치엔 검색 논리의 복잡도를 감소시키는 것이 가능하다. 그것은, 치엔 검색 논리가 에러 위치자 다항식{}을 평가하기만 하면 된다는 것을 의미한다.

에러 위치 및 그러한 에러 위치에 대응하는 근은 에러 위치자 다항식의 평가 이후에 알려진다. 바람직하게는, 근은 쉬프트 레지스터에 저장된다.

변형 직렬 포르네이 알고리듬을 사용함으로써 하드웨어 복잡도는 더욱 감소된다. 결합된 치엔 블록과 포르네이 블록의 높은 성능은 다중-통과 에러 정정을 수행할 수 있고, 이는 본질적으로 출력 에러율을 감소시킨다.

본 발명의 리드-솔로몬 디코더는 DVD 시스템이나 다른 광 또는 자기 저장 시스템과 같은 많은 전자 시스템에서 사용될 수 있다.

대체로, 본 발명의 방법은 리드-솔로몬 디코딩에 적합하며,

- 신드롬 다항식{S(x)} 및 소거 위치자 다항식{}을 계산하는 단계와;

- 변형 신드롬 다항식{}을 계산하는 단계로서, 여기서 t는 리드-솔로몬 코드의 심볼-에러 정정 성능인, 계산 단계와;

- 에러 위치자 다항식{} 및 에러 평가자 다항식{}을 계산하기 위해 유클리드 알고리듬을 수행하는 단계와;

- 병렬 치엔 검색을 수행하고, 동시에 에러/소거 위치자 다항식{}을 계산하는 단계와;

- 포르네이 방정식에 따라 에러 크기를 직렬로 계산하는 단계를 포함한다.

대체로, 본 발명의 리드-솔로몬 디코더는,

- 신드롬 다항식{S(x)} 및 소거 위치자 다항식{}을 계산하기 위한 수단과;

- 에러 위치자 다항식{} 및 에러 평가자 다항식{}을 계산하기 위해 유클리드 알고리듬을 수행하기 위한 수단과;

- 에러/소거 위치자 다항식{}을 계산하기 위한 수단과;

- 병렬 치엔 검색을 수행하기 위한 수단과;

- 포르네이 방정식에 따라 에러 크기를 직렬로 계산하기 위한 수단을 포함한다.

본 발명의 유리한 추가 실시예가 각각의 종속항에서 개시된다.

본 발명의 예시적인 실시예가 첨부 도면을 참조하여 설명된다.

도 1은 종래의 에러 정정 디코더에 대한 블록도의 예를 나타내는 도면.

도 2는 본 발명에 따른 병렬 치엔 검색 회로(parallel Chien search circuit)에 대한 블록도의 예를 나타내는 도면.

도 3은 본 발명에 따른 포르네이 방정식(Forney's equation)을 직렬로 계산하기 위한 회로의 블록도에 대한 예를 나타내는 도면.

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

ADD : 가산기 COM : 비교기

MUL : 곱셈기 REG : 레지스터

GFC : 갈로아 필드 카운터 SHR : 쉬프트 레지스터

아래에 기재된 정의가 사용된다:

에러 위치자 다항식(Error locator polynomial) :

소거 위치자 다항식(Erasure locator polynomial) :

에러/소거 위치자 다항식 :

에러 지점(Error position) : i_l,...,i_v

에러 위치(Error location) :

에러 값 : e_k,0 ≤k ＜ n

소거 지점 : j_l,...,j_f

소거 위치자 :

소거 값 : f_k,0 ≤k ＜ n

리드-솔로몬 디코딩은 5 단계를 사용하는 것으로 고려될 수 있다.

단계 1 :

리드-솔로몬 디코딩은 신드롬 다항식(syndrome polynomial){S(x)}를 계산하는 것으로 시작한다:

또한, 소거 위치자 다항식{}이 계산되고, 여기서

이다.

그로 인해, 소거 위치{근(root)}가 구해진다.

단계 2 :

변형 신드롬 다항식{}이 계산되는데, 여기서 t는 리드-솔로몬 코드의 심볼-에러 정정 성능이다.

단계 3 :

유클리드 알고리듬(Euclid's algorithm)이 사용되는데, 그 유클리드 알고리듬은 두 다항식의 최대 공약수를 구하기 위한 방법이다{참조 : 1975년 1월, "Information and Control"(제 27권, 87 내지 89쪽)에, Y.M. 쓰기야마(Y.M. Sugiyama), S.H. 까사하라(S.H. Kasahara), 및 T. 나메까와(T. Namekawa)에 의해서 기재된 "A Method for Solving the key Equation for Decoding of Goppa Codes"}.

에러 위치자 다항식{}과 에러 평가자 다항식{} 둘 모두는 유클리드 알고리듬을 사용하여 계산될 수 있다. 유클리드 알고리듬은 종래 기술 분야로부터 알려져 있는 것이다{참조 : 1994년 IEEE 정기 간행물의 스티븐 B. 윅커(Steven B. Wicker) 및 비자이 K. 브하르가바(Vijay K. Bhargava}에 의한 "Reed-Solomon codes and their applications"}.

단계 4 :

다음으로는, 병렬 치엔 블록을 사용하여 에러 위치가 계산된다. 그와 동시에, RS 디코더의 성능을 증가시키기 위해서 새로운 에러/소거 위치자 다항식{}이 계산된다. 그것은 본 발명의 특별한 장점이다.

단계 5 :

새로운 에러/소거 다항식의 계수가 직렬 포르네이 블록의 레지스터에 로딩되고, 에러/소거 크기 값이 계산된다.

소거 위치(근)는 단계 1을 실행한 후에 이미 알려져 있거나, CD 또는 DVD 시스템의 복조 블록을 통해 획득된다. 그러므로, 소거 위치는 단계 5의 치엔 검색에서 계산될 필요가 없다. 유리하게도, 소거 위치가 알려져 있기 때문에, 병렬 치엔 검색 논리의 복잡도를 감소시킬 수 있다. 즉, 치엔 검색 논리는 에러 위치자 다항식{}만을 평가할 필요가 있다. 유리하게도, 에러 위치자 다항식{}은 9 개의 계수만을 갖는다. 에러 위치 및 그 에러 위치에 대응하는 근은 그러한 에러 위치자 다항식의 평가 이후에 알려진다.

도 2는 4 개의 랭크를 포함하는 병렬 치엔 검색 논리를 도시하고 있다. 치엔 검색 논리의 각 사이클은 대응하는 4 개의 시험 근(trial root)을 병렬식으로 검사할 것이다:

치엔 검색 논리의 랭크(0)는 필드 원소 시퀀스(,...)에 의해 정의되는 매 4번째 필드 원소{즉, 코드 워드에서 에러 위치(0, 4, 8,...)}에서 근을 검색한다.

치엔 검색 논리의 랭크(1)는 필드 원소 시퀀스(...)에 의해 정의되는 매 4번째 필드 원소{즉, 코드 워드에서 에러 위치(3, 7, 11,...)}에서 근을 검색한다.

치엔 검색 논리의 랭크(2)는 필드 원소 시퀀스(...)에 의해 정의되는 매 4번째 필드 원소{즉, 코드 워드에서 에러 위치(2, 6, 10,...)}에서 근을 검색한다.

치엔 검색 논리의 랭크(3)는 필드 원소 시퀀스(...)에 의해정의되는 매 4번째 필드 원소{즉, 코드 워드에서 에러 위치(1, 5, 9,...)}에서 근을 검색한다.

갈로아 필드 카운터(GFC : Galois Field counter)는 GF 원소의 파워(power)를 정의한다. 초기화 동안에,원소가 레지스터에 로딩된다. 각각의 사이클{클록(CLK)}에서, 카운터(GFC)는 카운트 다운된다. 만약 비교기(comp1)가 '0'을 나타내면, 카운터(GFC)로부터의 커런트 파워(current power)와원소의 곱셈기(MUL33)에서의 곱셈 결과 값이 에러 위치자 다항식의 근이다. 만약 비교기(comp2)가 '0'을 나타내면, 카운터(GFC)로부터의 커런트 파워와원소의 곱셈기(MUL34)에서의 곱셈 결과 값은 에러 위치자 다항식의 근이다. 만약 비교기(comp3)가 '0'을 나타내면, 카운터(GFC)로부터의 커런트 파워와원소의 곱셈기(MUL35)에서의 곱셈 결과 값이 에러 위치자 다항식의 근이다. 만약 비교기(comp4)가 '0'을 나타내면, 카운터(GFC)는 근을 정의한다.

(도 3에서) 쉬프트 레지스터(SHR1)는 소거 또는 에러 위치에 대응하는 근을 기억하기 위해 사용된다. 디코딩 처리의 단계 1 동안에, 소거 위치에 대응하는 근은 SHR1 레지스터에 기억된다. SHR1 레지스터의 길이(depth)는 16이다. 그 길이는 CD 또는 DVD 시스템의 RS 코드워드로 디코딩되는 모든 에러 및 소거를 기억하기에 충분하다.

단계 3 동안에, 에러 위치자 다항식{}이 계산되고, 그것의 9 개의 계수가 도 2에 도시된 병렬 치엔 검색 블록의 레지스터(REG1 내지 REG9)에 로딩된다.그러한 레지스터들은 클럭(CLK)에 의해 클럭킹된다. 그 레지스터들의 출력 값은, 4 개의 랭크 각각에서, 가산기(ADD*) 및 곱셈기(MUL*)로 이루어진 체인(chain)에 제공된다. 랭크(3) 체인의 출력은 비교기(comp1)에 제공된다. 랭크(2) 체인의 출력은 비교기(comp2)에 제공된다. 랭크(1) 체인의 출력은 비교기(comp3)에 제공된다. 랭크(0) 체인의 출력은 비교기(comp4)에 제공된다. 레지스터(REG1 내지 REG8)의 출력은, 각각의 경우에, 곱셈기(MUL32 내지 MUL25)를 통해 각각 제공되는데, 상기 곱셈기는 각각의 경우에 인자(,,,,...,)를 각각 적용한다.

에러 위치자가 치엔 검색에서 에러 위치자 다항식을 평가하는 동안에 구해진다. 에러 위치자의 역수 값(value of the inverse)이 MUL33, MUL34, MUL35, 및 GF 카운터로부터 출력된다. 에러의 그러한 위치가 위의 SHR1 레지스터에 로딩된다.

도 3은 여러 심볼 지점에서 에러 및 소거 크기 값을 계산하여 에러 또는 소거 패턴을 산출하기 위한 블록을 도시한다. 그 블록은 변형 포르네이 알고리듬을 구현한다(직렬 구현). 변형 포르네이 알고리듬에 의해서 주어지는 에러 크기 값과 소거 크기 값은 수학식 1과 같다:

여기서,는에서 평가되는 에러 평가자 다항식{}이고,는에서 평가되는 에러/소거 위치자 다항식{ PSI`` (x)}의 형식적인 도함수{}이고, 또는, 여기서는에서 평가되는 에러 평가자 다항식{}이다.

및다항식은 수학식 2 및 3으로 표현된다:

에러 평가자 다항식의 계수(내지)는 각각의 레지스터(REG0 내지 REG15)에 로딩된다. 에러/소거 다항식{}의 일계도함수{}의 계수(내지)가 각각의 레지스터(REG16 내지 REG23)에 로딩된다. 레지스터(REG0 내지 REG15)뿐만 아니라 그러한 레지스터들은 클럭(CLK)에 의해서 클럭킹된다.

그런 후에, 소거 또는 에러 위치에 대응하는 근(x)이 레지스터(SHR1)로부터 출력되어 포르네이 블록에 입력된다. 곱셈기(MUL0 내지 MUL13)로 이루어진 체인에서는, x의 차수(x¹, x², x³,..., x¹⁵)가 x로부터 계산된다. 계수(내지)는 각각의 곱셈기(MUL14 내지 MUL29)를 사용하여 커런트 근(x)의 각 차수(x¹, x², x³,..., x¹⁵)와 곱해진다. 각각의 사이클에서는, 15 개의 결과 값 세트가 각각의 가산기(ADD2 내지 ADD15)에 의해서 합산된다. 또한, ADD1에서는,의 값이 첫 번째곱셈 결과 값에 더해진다. 가산기(ADD15)의 출력은 커런트 근()에서 에러 평가자 다항식{}의 평가 결과이다.

계수()는 각각의 곱셈기(MUL30 내지 MUL37)에 의해서 커런트 근(x)의 대응하는 차수(x¹, x³, x⁵,..., x¹⁵)와 곱해진다. 클럭(CLK)의 각 사이클에서, 그러한 곱셈기의 결과 값 세트는 각각의 가산기(ADD16 내지 ADD22)에 의해서 합산된다. ADD22의 출력은 커런트 근()에서 에러/소거 다항식{}의 평가 결과이다.

만약, 수학식 1에서 나눗셈 대신에 곱셈이 사용된다면, 그 수학식 1은 수학식 4와 같이 된다:

가산기(ADD22) 출력으로부터의 곱셈 결과 값{}은 GF 인버터(GFI)에서 역수로 된 후에 가산기(ADD15)의 상기 출력 값과 곱셈기(MUL38)에서 곱해져서, 에러 크기() 및 소거 크기()를 각각 산출한다. 계산된 소거 또는 에러 크기 값은 곱셈기(MUL38)로부터 출력되어 레지스터(SHR2)에 저장된다. 그 레지스터는 레지스터(SHR1)와 동일한 길이(depth)를 갖는다.

레지스터(SHR1)에 저장된 모든 근은 포르네이 블록에서 동일한 방식으로 처리된다. 계산된 크기 값은 레지스터(SHR2)에 기억된다.

유리하게도, DVD 시스템에서 에러 위치 및 에러 값을 결정하기 위해 사용되는 본 발명의 치엔&포르네이 스테이지는 다음과 같은 최소의 하드웨어만을 필요로 한다:

치엔 검색 블록 : 36 개의 곱셈기, 32 개의 가산기, 9 개의 레지스터, 4 개의 비교기, 및 1 개의 GF 카운터.

포르네이 블록 : 38 개의 곱셈기, 22 개의 가산기, 24 개의 레지스터 및 1 개의 GF 인버터.

반면에 알려져 있는 치엔&포르네이 스테이지는 다음과 같은 최소의 하드웨어를 필요로 한다:

치엔 검색 블록 : 34 개의 곱셈기, 31 개의 가산기, 33 개의 레지스터, 1 개의 비교기, 1 개의 카운터, 및 1 개의 인버터.

포르네이 블록 : 136 개의 곱셈기, 124 개의 가산기, 33 개의 레지스터, 4 개의 비교기, 4 개의 카운터 및 4 개의 인버터.

본 발명에서는, 외코드(outer code)를 위한 단지 67 사이클과 내코드(inner code)를 위한 단지 62 사이클이 에러/소거 위치 및 에러/소거 크기를 계산하는데 필요하다. 그것은 종래의 치엔 및 포르네이 블록에 비교했을 때 훨씬 더 빠르다.

본 발명은 CD, DVD, 블루-레이저 DVD(blue-laser DVD){블루-레이(Blu-Ray)} 또는 다른 저장 시스템과 같이, 에러 결정 및/또는 정정을 필요로 하는 임의의 전자 시스템을 위해서 사용될 수 있다. 본 발명은 에러 위치 및 에러 값을 계산하기 위해 필요한 사이클의 수를 감소시킬 수 있고, 동시에, 비교적 작은 복잡도만을 갖는 하드웨어를 필요로 한다.

상술된 바와 같이, 본 발명은 향상된 리드-솔로몬 디코더와 리드-솔로몬 디코딩을 위한 향상된 방법을 제공하며, DVD 시스템과 같이, 리드-솔로몬 디코더를 구비하는 향상된 전자 시스템을 제공한다.

Claims

- 신드롬 다항식(syndrome polynomial){S(x)} 및 소거 위치자 다항식(erasure locator polynomial){}을 계산하기 위한 수단(110)과;

- 변형 신드롬 다항식{}을 계산하기 위한 수단으로서, 여기서 t는 리드-솔로몬 코드의 심볼-에러 정정 성능인, 계산 수단과;

- 에러 위치자 다항식{} 및 에러 평가자 다항식(error evaluator polynomial){}을 계산하기 위해 유클리드 알고리듬(Euclid's algorithm)을 수행하기 위한 수단(120)과;

- 에러/소거 위치자 다항식{}을 계산하기 위한 수단과;

- 병렬 치엔 검색(parallel Chien search)을 수행하기 위한 수단(도 2)과;

- 포르네이 방정식(Forney's equation)에 따라 에러 크기를 직렬로 계산하기 위한 수단(도 3)을

포함하는, 리드-솔로몬 디코더.
제 1항에 있어서, 에러 값() 및 소거 값()을 계산하기 위한 변형 포르네이 방정식인

이 상기 에러 크기를 직렬로 계산하기 위해 사용되는, 리드-솔로몬 디코더.
제 1항에 있어서, 에러 값() 및 소거 값()을 계산하기 위한 변형 포르네이 방정식인

이 상기 에러 크기를 직렬로 계산하기 위해 사용되는, 리드-솔로몬 디코더.
제 1항 내지 제 3항 중 어느 한 항에 있어서, 병렬 치엔 검색을 수행하기 위한 상기 수단은 n 개의 시험 근(trial root)을 병렬로 검사하기 위해 다수의 n 랭크를 구비하는, 리드-솔로몬 디코더.
제 1항 내지 제 4항 중 어느 한 항에 있어서, 포르네이 방정식에 따라 상기 에러 크기를 직렬로 계산하기 위한 상기 수단은 병렬 치엔 검색을 수행하기 위한 상기 수단에 의해서 결정된 근을 저장하기 위해서 쉬프트 레지스터 수단(SHR1)을 포함하는, 리드-솔로몬 디코더.
제 1항 내지 제 5항 중 어느 한 항에 있어서, 포르네이 방정식에 따라 상기 에러 크기를 직렬로 계산하기 위한 상기 수단은 곱셈 결과 값{}을 역수로 하기 위한 갈로아 필드 인버터(GFI : Galois Fields inverter) 수단을 포함하는, 리드-솔로몬 디코더.
- 신드롬 다항식{S(x)} 및 소거 위치자 다항식{}을 계산하는 단계(110)와;

- 변형 신드롬 다항식{}을 계산하는 단계로서, 여기서 t는 리드-솔로몬 코드의 심볼-에러 정정 성능인, 계산 단계와;

- 에러 위치자 다항식{} 및 에러 평가자 다항식{}을 계산하기 위해 유클리드 알고리듬을 수행하는 단계(120)와;

- 병렬 치엔 검색을 수행하고(도 2), 동시에 에러/소거 위치자 다항식{}을 계산하는 단계와;

- 포르네이 방정식에 따라 에러 크기를 직렬로 계산하는 단계(도 3)를

포함하는, 리드-솔로몬 디코딩 방법.
제 7항에 있어서, 에러 값() 및 소거 값()을 계산하기 위한 변형 포르네이 방정식인

이 상기 에러 크기를 직렬로 계산하기 위해 사용되는, 리드-솔로몬 디코딩 방법.
제 7항에 있어서, 에러 값() 및 소거 값()을 계산하기 위한 변형 포르네이 방정식인

이 상기 에러 크기를 직렬로 계산하기 위해 사용되는, 리드-솔로몬 디코딩 방법.
제 7항 내지 제 9항 중 어느 한 항에 있어서, n 개의 시험 근이 n 개의 랭크를 통해 병렬로 검사되는, 리드-솔로몬 디코딩 방법.
제 7항 내지 제 10항 중 어느 한 항에 있어서, 포르네이 방정식에 따른 상기 에러 크기의 직렬 계산은 곱셈 결과 값{}을 역수로 하기 위한 갈로아 필드 인버터(GFI) 수단에 의해 수행되는, 리드-솔로몬 디코딩 방법.
CD, DVD, 블루-레이저 DVD(blue-laser DVD) 또는 다른 광 또는 자기 저장 시스템과 같은, 전자 시스템으로서,

제 1항 내지 제 6항 중 어느 한 항에 따른 리드-솔로몬 디코더를 포함하는, 전자 시스템.