KR100330642B1

KR100330642B1 - 오류정정방법및오류정정장치

Info

Publication number: KR100330642B1
Application number: KR1019980001287A
Authority: KR
Inventors: 하치로 후지타; 히데오 요시다
Original assignee: 미쓰비시덴키 가부시키가이샤
Priority date: 1997-05-01
Filing date: 1998-01-17
Publication date: 2002-08-17
Anticipated expiration: 2018-01-17
Also published as: KR19980086482A; JPH1117557A; TW427077B; US6145112A; CN1201296A; CN1103143C

Abstract

신드롬의 값만으로 정정 불가능한 오류 패턴을 검출할 수 없으며, 또한, 2중 오류의 검출 조건도 번잡한 등의 과제가 있었다. 신드롬의 값만으로 오류 정정 불가능성을 판정하는 동시에 연산식(B)만으로 2중 오류를 추정하고, 또한 신드롬의 값만으로 오류 정정 불가능성을 판정할 수 없는 특수한 경우에 연산식의 값만으로도 오류 정정 불가능한 것을 판정한다.

Description

오류 정정 방법 및 오류 정정 장치

본 발명은 디지탈 기기나 디지탈 통신에서 발생하는 오류를 정정하는 오류 정정 방법 및 오류 정정 장치에 관한 것이다.

(종래의 기술)

컴팩트 디스크(CD)나 디지탈 오디오 테이프(DAT) 등을 사용한 디지탈 기기나 디지탈 통신에서 발생하는 오류의 정정 방법은, 복호할 부호중의 오류의 개수에 따라 각각에 적합한 오류 정정 방법이 구별되어 사용되고 있다. 이러한 오류의 정정 부호중, 1부호중의 바이트 단위의 오류를 정정하는 오류 정정 부호로는 종래부터 리드·솔로몬(Reed-Solomon) 부호(이하「RS 부호」라고 약기함)가 널리 사용되고 있다.

RS 부호의 복호법으로는, 피터슨(Peterson)법, 버레캄프(Berlekamp), 유클리드(Euclid)법 등이 알려져 있지만, 정정 능력이 작은 것(1중 내지 2중)에 대해서는 계산이 용이하므로 피터슨법이 사용되는 경우가 많다.

피터슨법의 복호 과정은 크게 나눠 이하의 4개의 스텝으로 이루어진다.

1. 수신어로부터 신드롬(syndrome)을 계산한다.

2. 오류 개수를 추정하고, 오류 위치 방정식을 구한다.

3. 구한 오류 위치 방정식의 근을 구한다.

4. 구한 근에 대응하는 오류 위치에서의 오류 수치를 계산한다.

이상의 4개의 스텝중 3. 의 스텝은 통상, 오류 위치 방정식에 갈루아체(Galois field)의 원을 대입하여 근을 차례로 조사하는 방법(체인·서치법)에 의해서 실행된다.

이러한 피터슨법의 일예로서, 예컨대 일본 특공평 4-7848호 공보에 상기 순서에 따른 이하의 알고리즘이 개시되어 있다.

우선 수신어로부터 신드롬(S0,S1,S2,S3)을 계산하고, 또한 연산식(A,B,C)을 다음 식에 따라서 계산한다.

A = S0 S2 + S1²

B = S1 S2 + S0 S3

C = S1 S3 + S2²

이로부터, 다음과 같이 오류 개수를 추정하여 정정을 행한다.

(1) A = B = C = 0, S0 = S3 = 0일 때

오류 없음으로 추정한다.

(2) A = B = C = 0, S0 ≠ 0, S3 ≠ 0일 때

1중 오류 발생으로 추정한다. 이때, 오류 위치(i) 및 오류 수치(e)는

αⁱ= S1/S0 e = S0

의 관계를 만족한다. 단 α는 기약 방정식 F(x) = 0을 만족하는 근이다. 오류 위치는 오류 위치(i)와 αⁱ의 대응 표를 ROM에 미리 기록해 두고, S1/S0의 값으로 ROM을 검색함으로써 구한다. 또한, 오류 수치는 S0이다.

(3) A ≠ 0, B ≠ 0, C ≠ 0일 때

2중 오류 발생으로 추정한다. 이때, 오류 위치 방정식은,

Ax²+ Bx + C = 0

가 된다. 이 2근을 αⁱ, α^j(0≤i<j≤n-1)로 하면,

αⁱ+ α^j= D

αⁱα^j= E

가 된다. 단, D = B/A, E = C/A 이다.

2개의 오류 위치의 차, 즉 2근(αⁱ,α^j)의 차를 t(t = j-i)로 하면,

D = αⁱ(1 + α^t)

E = α^{2i + t}

로 변형될 수 있다. 따라서,

D²/E = α^t+ α^-t

가 얻어진다. ROM에 t(l≤t≤n-l)에 대응하는 α^t+ α^-t의 값을 미리 기록해 두고,

D²/E의 값으로 ROM을 검색함으로써 차(t)를 구할 수 있다.

이로부터,

X = 1 + α^t

Y = 1 + α^-t= D²/E + X

를 구함으로써,

αⁱ= D/X

α^j= D/Y

가 얻어진다. 따라서, 1중 오류일 때와 마찬가지로 D/X, D/Y의 값으로 ROM을 검색함으로써 오류 위치(i,j)를 구할 수 있다. 또한, 오류 위치(i,j)에서의 오류 수치(e_i,e_j)는 각각 하기와 같이 구한다.

e_i= (α^jS0 + S1) /D

e_j= (αⁱS0 + S1) /D

종래의 오류 정정 방법은 상기와 같이 구성되어 있으므로, 수신어(receivedword)로부터 신드롬(S0,S1,S2,S3)의 값을 계산하면, 이어서 바로 연산식(A,B,C)의 계산을 행하고 있다. 그런데도 불구하고, 수신어중에는 처음부터 오류의 정정이 불가능한 것도 있으며, 이러한 수신어에 대하여 연산식(A,B,C)의 계산을 행하는 것은 불필요한 계산 처리를 행하는 것이 되며, 처음부터 오류 정정이 불가능한 것으로 판별되기까지 장시간이 요구되는 경우가 있다는 과제가 있었다.

또한, 신드롬(S0,S1,S2,S3)의 값 및 연산식(A,B,C)에 기초하여 오류 정정의 가부를 판정하는 것이고, 신드롬(S0,S1,S2,S3)의 값만으로부터 정정 불가능한 오류 패턴을 검출할 수 없으며, 오류 정정 가부의 판정 동작 자체도 번잡하다고 하는 과제가 있었다.

또한, 2중 오류는 3개의 연산식(A,B,C)의 값에 기초하여 검출하는 것으로, 검출 조건이 번잡하다고 하는 과제가 있었다.

또한, 오류 정정을 행하는 경우에 있어서는, 먼저 오류 위치에 대응하는 갈루아체의 원αⁱ를 구하고, 또한 ROM에서 검색함으로써 오류 위치(i)를 구하지 않으면 안되며, 복호 지연이 커지고, 또한, ROM을 사용하므로 회로 규모가 커지는 등의 과제가 있었다.

또한, 종래의 오류 정정 방법에서는, 2중 정정을 행하는 경우에 나눗셈을 7회 행할 필요가 있는데, 나눗셈은 계산량이 많고 복호 지연에 많은 영향을 미친다.

도 1은 본 발명의 실시 형태 1에 따른 오류 정정 방법의 흐름도.

도 2는 도 1의 스텝(ST3)의 오류 개수 추정 스텝의 상세한 순서를 나타낸 흐름도.

도 3은 본 발명의 실시 형태 2에 따른 오류 정정 방법의 흐름도.

도 4는 본 발명의 실시 형태 3에 따른 오류 정정 방법의 흐름도.

도 5는 실시 형태 3에 있어서의 갈루아체의 원과 다항식 기저를 나타낸 도면.

도 6은 실시 형태 3에 있어서의 각 심벌의 저장되는 주소를 나타낸 도면.

도 7은 본 발명의 실시 형태 6에 따른 오류 정정 장치를 나타낸 구성도.

도 8은 실시 형태 6의 오류 개수 추정 수단의 구성을 상세하게 나타낸 구성도.

도 9는 본 발명의 실시 형태 7에 따른 오류 정정 장치를 나타낸 구성도.

도 10은 본 발명의 실시 형태 8에 따른 오류 정정 장치를 나타낸 구성도.

도 11은 실시 형태 8의 기억 수단의 상세한 구성을 나타낸 구성도.

도 12는 실시 형태 8의 수신어의 입력부의 구성을 나타낸 구성도.

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

10: 신드롬 생성 수단(신드롬 생성 수단, 정정 불가능성 판정 수단)

11: 연산식 생성 수단 12: 오류 개수 추정 수단

13: 오류 위치·오류 수치 계산 수단 15: 오류 정정 수단

23: 랜덤 액세스 메모리(메모리) 24: 주소 생성 수단

본 발명은 상기한 바와 같은 과제를 해결하기 위해서 이루어진 것으로, 신드롬만으로부터 오류 정정의 불가능성을 판정할 수 있는 오류 정정 방법 및 오류 정정 장치를 얻는 것을 목적으로 한다.

또한, 간편하게 오류가 2중인 것을 검출할 수 있는 오류 정정 방법 및 오류 정정 장치를 얻는 것을 목적으로 한다.

또한, ROM을 검색하지 않고, 오류 위치를 갈루아체의 원으로부터 바로 계산하여 정정할 수 있으며, 오류 위치를 단시간에 계산할 수 있는 동시에, 검색용 ROM이 불필요한 오류 정정 방법 및 오류 정정 장치를 얻는 것을 목적으로 한다.

또한, 2중 정정을 행하는 경우, 1회의 나눗셈을 행하는 것만으로 정정할 수 있으며, 고속으로 오류 정정이 가능한 오류 정정 방법 및 오류 정정 장치를 얻는 것을 목적으로 한다.

(과제를 해결하기 위한 수단)

본 발명에 따른 오류 정정 방법은 신드롬 생성 스텝에서 생성된 신드롬에 기초하여 3중 오류 이상의 오류를 정정 불가능하다고 판정하는 제1정정 불가능성 판정 스텝을 설정한 것이다.

본 발명에 따른 오류 정정 방법은 제1정정 불가능성 판정 스텝에 있어서, 신드롬을 한 방향으로 배열하였을 때 인접하는 신드롬 또는 하나 건너 인접하는 신드롬이 모두 0일 때에 오류의 정정이 불가능한 것으로 판정하는 것이다.

본 발명에 따른 오류 정정 방법은 오류 개수 추정 스텝에 있어서, 신드롬을 한 방향으로 배열하였을 때, 제2위치가 되는 신드롬과 제3위치가 되는 신드롬의 곱과, 제1위치가 되는 신드롬과 제4위치가 되는 신드롬의 곱의 합으로 이루어진 연산식이 0이 아닐 때에 수신어중에 2중 오류가 발생한 것으로 추정하는 것이다.

본 발명에 따른 오류 정정 방법은 연산식에 기초하여 오류의 정정이 불가능하다고 판정하는 제2정정 불가능성 판정 스텝을 또한 설정한 것이다.

본 발명에 따른 오류 정정 방법은 오류 개수 추정 스텝에 있어서 수신어중에 2중 오류가 발생하고 있다고 추정한 경우, 오류 위치 방정식의 차수가 최대 변수의 계수인 연산식의 값을 차수가 다음으로 큰 변수의 계수인 연산식의 값으로 나눈 값과 각 신드롬만으로 이루어지는 다항식을 생성하는 다항식 생성 스텝을 또한 설정하여, 오류 위치·오류 수치 계산 스텝에 있어서, 상기 다항식에 오류 위치 방정식의 근을 대입함으로써 오류 수치를 구하는 것이다.

본 발명에 따른 오류 정정 방법은 갈루아체의 원시원(原始元)에 기초하여 수신어의 각 심벌의 주소를 생성하는 주소 생성 스텝과, 해당 주소 생성 스텝에 있어서 생성한 상기 주소에 상기 각 심벌을 저장하는 저장 스텝과, 오류 위치·오류 수치 계산 스텝에 있어서 계산한 오류 위치 및 오류 수치에 기초하여 상기 저장 스텝에 있어서 저장된 상기 각 심벌을 읽어내어 상기 수신어의 오류를 정정하는 오류 정정 스텝을 포함하고 있는 것이다.

본 발명에 따른 오류 정정 장치는 신드롬 생성 수단이 생성한 신드롬에 기초하여 3중 오류 이상의 오류를 정정 불가능하다고 판정하는 정정 불가능성 판정 수단을 설치한 것이다.

본 발명에 따른 오류 정정 장치는 갈루아체의 원시원에 기초하여 수신어의 각 심벌의 주소를 생성하는 주소 생성 수단과, 해당 주소 생성 수단이 생성한 상기주소에 상기 각 심벌을 저장하는 메모리와, 오류 위치·오류 수치 계산 수단이 계산한 오류 위치 및 오류 수치에 기초하여 상기 메모리의 상기 오류 위치에 대응하는 주소에 저장된 상기 각 심벌을 판독하여 상기 수신어의 오류를 정정하는 오류 정정 수단을 구비한 것이다.

이하, 본 발명의 실시의 한 형태를 설명한다.

실시 형태 1

도 1은 본 발명의 실시 형태 1에 따른 오류 정정 방법의 순서를 나타낸 흐름도이다. 이 실시 형태 1에서는 부호화되어 송신된 RS 부호를 복호하는 과정에서 수신어중의 오류를 정정하는 것을 목적으로 한다.

도 1에 있어서, ST1은 수신어로부터 신드롬(S0,S1,S2,S3)을 계산하는 스텝이고, ST2는 연산식,

A = S0 S2 + S1²

B = S1 S2 + S0 S3

C = S1 S3 + S2²

를 계산하는 스텝이며, ST3은 상기 신드롬(S0,S1,S2,S3) 및 연산식(A,B,C)으로부터 오류 개수를 추정하는 스텝이고, ST4는 오류 위치·오류 수치를 계산하는 스텝이며, ST5는 오류 정정을 행하는 스텝이다.

다음에 동작에 대해 설명한다.

먼저, 수신어(R)와 패리티 행렬(H)을 각각,

R = (r_n-1r_n-2… r₁r₀)

로 할 때 (α는 갈루아체의 원시원, j는 임의의 정수, r은 수신 신호의 각 심벌의 값을 나타냄).

의 연산에 의해 신드롬(S0,S1,S2,S3)을 계산하고(스텝 ST1), 이를 이용하여 연산식(A,B,C)을 계산한다(스텝 ST2).

다음에, 신드롬(S0,S1,S2,S3) 및 연산식(A,B,C)으로부터 오류 개수를 추정한다(스텝 ST3).

도 2는 스텝(ST3)의 오류 개수 추정 스텝의 상세한 순서를 나타낸 것이다. 도 2에 나타낸 바와 같이, 스텝(ST3)에서는 오류 개수를 아래와 같이 추정한다.

즉, 먼저 S0 = S1 = S2 = S3 = 0일 때(스텝(ST31)), 오류가 없다고 추정한다.

이 추정의 기초는 다음과 같다.

즉, 수신어중에 오류가 없으면, 그 수신어는 패리티 행렬(H)의 고유치(0)의 고유 벡터가 된다. 따라서, 위에 기재한 패리티 행렬(H)과 수신어(R)의 전치 행렬과의 곱은 0이 되며, 신드롬(S0,S1,S2,S3)은 모두 0이 된다. 이에 의해, 오류가 없으면 모든 신드롬이 0이라고 할 수 있으며, 이 모든 신드롬이 0인 것이 「오류 없음」의 판정 조건이 된다.

다음에, S0 = S1 = S2 = S3 = 0 이 아닌 S0 = S1 = 0 또는 S1 = S2 = 0 또는 S2 = S3 = 0 또는 S3 = S1 = 0 또는 S0 = S2 = 0 일 때(스텝(ST32)), 3중 이상의 오류가 발생하여, 오류의 정정이 불가능하다고 추정한다.

이와 같이 추정할 수 있는 이유를 S0 = S1 = 0 인 경우를 예로 들어 귀류법을 이용하여 설명한다.

이때, S0 = S1 = S2 = S3 = 0이 아니고 S0 = S1 = 0이므로, 물론 S2 ≠ 0 또는 S3 ≠ 0이 성립한다.

처음에 1중 오류가 발생한 것으로 가정한다. 그 오류 위치를 i, 오류 수치를 e_i라고 하면, S0 = e_i이지만, S0 = 0 이므로 e_i= 0을 얻는다.

따라서,

S2 = e_iα²ⁱ= 0 S3 = e_iα³ⁱ= 0

이 되며, 조건 S2 ≠ 0 또는 S3 ≠ 0에 반한다.

다음에, 2중 오류가 발생하였다고 가정한다. 그 오류 위치를 i, j, 오류 수치를 e_i, e_j라고 하면,

S0 = e_i+ e_jS1 = e_iαⁱ+ e_jα^j

이지만, S0 = S1 = 0 이므로,

e_i+ e_j= 0 e_iαⁱ+ e_jα^j= 0

이 되며, 이 두 식을 e_i, e_j에 대해 풀면, e_i= e_j= 0이 얻어진다.

한편,

S2 = e_iα²ⁱ+ e_jα^2jS3 = e_iα³ⁱ+ e_jα^3j

이므로, S2 = S3 = 0이 되며, 조건 S2 ≠ 0 또는 S3 ≠ 0에 반한다.

이상으로부터, S0 = S1 = S2 = S3 = 0 이 아닌 S0 = S1 = 0인 경우에는 2중 이하의 오류가 발생하였다고 가정하면 모순이 생기므로, 3중 이상 오류가 발생하였다고 추정할 수 있다. 마찬가지로, S0 = S1 = S2 = S3 = 0 이 아닌 S1 = S2 = 0 또는 S2 = S3 = 0 또는 S3 = S1 = 0 또는 S0 = S2 = 0 일 때에도, 3중 이상 오류가 발생하였다고 추정할 수 있다.

또, S0 = S3 = 0 일 때는 3중 이상 오류가 발생하고 있다고는 한정하지 않는다. 이를 이하에서 갈루아체 GF(2⁴)의 부호 길이 15, 정보기호수 11의 2중 정정 RS 부호를 이용하여 설명한다.

수신어 R = (r₁₄, r₁₃, … r₁, r₀)의 위치(5,10)에 크기가 같은 오류 e₅= e₁₀= e (≠ 0)가 발생한 경우를 고려한다. α를 갈루아체의 원시원(원시다항식 x4 + x + 1 = 0의 근)이라고 하면, 신드롬(S0,S3)은,

S0 = e₅+ e₁₀= e + e = 0

S3 = e₅α^3*5+ e₁₀α^3*10

= eα¹⁵eα³⁰= e + e = 0

로 계산되며, S0 = S3 = 0이 얻어진다. 여기에서, 원시원(α)의 성질α¹⁵α³⁰= 1을 이용하였다.

또한, 신드롬(S1, S2)은,

S1 = e₅α⁵+ e₁₀α¹⁰= e (α⁵+ α¹⁰) = e

S2 = e₅α^2*5+ e₁₀α^2*10= eα¹⁰+ eα²⁰= e

로 계산되고, 모두 0이 아니다. 여기에서, 원시원(α)의 성질(α⁵+ α¹⁰= 1)을 이용하였다.

이상으로부터, 조건 S0 = S3 = 0을 만족하는 2중 오류의 오류 패턴이 존재하는 것이 증명되었다. 아울러, 이 경우에 연산식(A,B,C)은,

A = S0 S2 + S1²= e²

B = S1 S2 + S0 S3 = e²

C = S1 S3 + S2²= e²

이고, 조건 B ≠ 0이 성립하므로, 2중 오류가 발생하고 있는 것을 검출하는 것이 가능하다.

일반적인 갈루아체 GF (2^m) (m은 자연수) 상의 2중 정정 RS 부호에 대해서는 이하의 의론을 할 수 있다.

2중 이하의 오류가 발생하고, 조건 S0 = S3 = 0을 만족하는 것으로 가정한다. 그 2중 오류의 위치를 i, j (i≠j)로 하고, 오류의 크기를 e_i, e_j로 한다.

이때, S0 = S3 = 0으로부터 다음 행렬 관계가 얻어진다. 단, α은 갈루아체 GF (2^m)의 원시원이다.

이 관계를 만족시키는 자명하지 않는 (e_i, e_j)가 존재하기 위한 조건은 다음 행렬식(△)이 0이 된 것이다.

여기에서, △ = α³ⁱ+ α^3j= (αⁱ+ α^j) (α²ⁱ+ αⁱα^j+ α^2j)로부터, △ = 0이 되는 조건은 αⁱ≠ α^j를 고려하면, α²ⁱ+ αⁱα^j+ α^2j= 0이다. 이 조건은 갈루아체 GF (2^m)상에서 방정식 x²+ x + 1 = 0이 근을 가지는 것과 같다. 그런데,이 방정식이 근을 가지기 위한 조건은 m이 짝수라는 것이 알려져 있다. 따라서, m이 짝수인 경우, 조건 S0 = S3 = 0을 만족하는 2중 오류가 존재하는 것을 알 수 있다. 상술한 예는 m = 4 인 경우이었다. 한편, m이 홀수인 경우, 조건 S0 = S3 = 0을 만족하는 2중 이하의 오류는 존재하지 않음을 알 수 있다.

이상 의론을 정리하면, 갈루아체 GF (2^m)상의 2중 정정 RS 부호에 있어서, m이 짝수 홀수임에 따라 이하의 분류가 얻어진다.

m이 짝수일 때

S0 = S3 = 0 을 제외하고 2개의 신드롬이 0이면 3중 이상의 오류가 발생하였다고 추정할 수 있다.

m이 홀수일 때

2개의 신드롬이 0일 때 3중 이상의 오류가 발생하였다고 추정할 수 있다.

따라서, m이 짝수로 S0 = S3 = 0이 성립하는 경우에는 3중 이상의 오류가 발생하고 있다고는 한정할 수 없다.

신드롬(S0,S1,S2,S3)이 도 2의 스텝(ST32)의 어느 관계도 만족하지 않을 때에는 연산식(B)이 B ≠ 0인지의 여부를 판정하여(스텝(ST3)3), B ≠ 0 일 때, 2중 오류가 발생하였다고 추정한다.

이 추정의 기초에 대해 귀류법을 이용하여 설명한다.

먼저, 상술한 연산식(A,B,C)을 이용하여 다음의 오류 위치 방정식이 얻어진다.

Ax²+ Bx + C = 0

이 오류 위치 방정식에 있어서, 연산식 B = 0을 가정하면, 오류 위치 방정식은,

Ax²+ C = 0

이 되며, 이 방정식은 겨우 1근 밖에 근을 가지지 않는다. 이는 B ≠ 0일 때에 2중 오류가 발생함을 나타낸다.

B가 0일 때에는 연산식(A,B,C)이 A = B = C = 0 인지의 여부를 판정하여(스텝(ST34)), A = B = C = 0 일 때, 1중 오류가 발생하였다고 추정한다.

이에 대해 다음에 설명한다.

1중 오류가 발생한 경우에, 그 오류 위치를 i, 오류 수치를 e_i로 하면, S0 = e_i, S1 = e_iα_i, S2 = e_iα²ⁱ, S3 = e_iα³ⁱ이다.

이로부터,

A = S0 S2 + S1²= e_i(e_iα²ⁱ) + (e_iαⁱ)²= 0

이 되며 A = 0이 나타난다. B = C = 0도 동일하게 나타난다.

이상으로부터, A = B = C = 0일 때에 1중 오류가 발생하였다고 추정된다.

신드롬(S0,S1,S2,S3) 및 연산식(A,B,C)이 상기의 어느 관계식도 만족하지 않을 때에는, 3중 이상의 오류가 발생하였다고 추정한다.

상기 추정에 있어서, 오류 없음이라고 추정되었을 때는 수신어를 그대로 출력한다. 1중 또는 2중 오류가 발생하였다고 추정되었을 때는 오류 위치 및 오류 수치를 계산하고(스텝(ST4)), 오류를 정정하며(스텝(ST5)), 정정 결과를 출력한다. 3중 이상의 오류가 발생하였다고 추정되었을 때는 오류 검출 플래그와 동시에 정정 불가능한 취지를 나타낸 추정 결과를 출력하여 이후의 정정 동작을 중지한다.

즉, 이 실시 형태 1에 있어서는, 오류 개수 추정 스텝(ST3)에 있어서, 먼저, 신드롬(S0 내지 S3)의 값만으로써, 오류 정정이 불가능한 것을 판정하여, 오류 정정이 불가능한 경우에는 이후의 연산식(A 내지 C)의 계산을 중지하며, 오류 정정이 가 가능한 경우에는 연산식(A 내지 C)을 구하여, B가 0이 아니면 2중 오류라고 판정하고, A,B,C가 전부 0인 경우는 1중 오류라고 판정한다.

상기와 같이, 이 실시 형태 1에 의하면, 신드롬만으로써 오류 정정이 불가능한 것을 판정하여, 이후의 오류 정정을 위한 일련의 처리를 불필요로 할 수 있으며, 따라서, 오류의 정정이 불가능한 경우에 불필요한 계산 처리를 하지 않고, 단시간에 다음 수신어의 처리에 착수할 수 있다는 효과가 얻어진다.

또한, 감산식(B)만으로 2중 오류를 검출할 수 있다. 이에 의해, 2중 오류의 검출을 단시간에 행할 수 있는 효과가 얻어진다.

실시 형태 2

도 3은 본 발명의 실시 형태 2에 따른 오류 정정 방법의 순서를 나타낸 흐름도이고, 도면에 있어서, 도 1의 흐름도와 유사한 동작을 나타낸 스텝에는 도 1의 스텝에 붙인 것과 동일한 스텝 번호를 붙인다.

도 3에 있어서, ST6은 오류 위치를 계산하는 스텝이고, ST7은 오류 수치를 계산하는 스텝이며, ST8은 다항식,

e (x) = a/b (S0 x + S1) + S0

을 계산하는 스텝이다.

다음에 동작에 대해 설명한다.

수신어(R)와 패리티 행렬(H)을 각각,

R = (r_n-1r_n-2… r₁r₀)

로 할 때(α는 갈루아체의 원시원),

의 연산에 따라 신드롬(S0,S1,S2,S3)을 계산하고(스텝(ST1)), 계산한 신드롬(S0,S1,S2,S3)에 의해 오류 개수를 추정하며(스텝(ST3)), 오류 위치 및 오류 수치를 계산하여(스텝(ST6, ST7)), 오류 정정을 행한다(스텝(ST5)).

스텝(ST3)의 오류 개수 추정에 있어서, 2중 오류라고 추정되었을 때, 오류 위치 방정식이 ax²+ bx + c = 0으로 주어지며, 이 방정식이 0이 아닌 상이한 2근(u, v)을 가진다고 한다(그렇지 않을 때는 2중 오류가 아니므로, 오류 검출에 멈춘다). 여기에서, A,B,C는 갈루아체의 원이다.

이때, 2근(u,v)에 대응하는 오류 수치를 각각 e_u, e_v라고 하면, 오류 수치(e_u,e_v)는,

[수학식 1]

[수학식 2]

를 만족한다. 수학식 1, 수학식 2로부터, uS0 + S1 = e_v(u + v)를 얻을 수 있지만, u + v = b/a를 이용하면,

e_v= a/b (uS0 + S1)

로 구해진다. 따라서, 수학식 1로부터

e_u= a/b (uS0 + S1) + S0

로 구해진다. 마찬가지로,

e_v= a/b (vS0 + S1) + S0

가 구해진다. 2중 오류가 생겼다고 추정되었을 때는 다항식,

e(x) = a/b (S0 x + S1) + S0

를 계산하고(스텝(ST8)), u, v를 대입함으로써 오류 수치(eu,ev)를 계산한다(스텝(ST7)).

상기와 같이, 이 실시 형태 2에 의하면, 시간의 이러한 나눗셈 연산을 단지 1회(a/b) 행하는 것만으로 오류를 정정할 수 있어, 오류 정정 시간을 단축할 수 있다는 효과가 얻어진다.

실시 형태 3

도 4는 본 발명의 실시 형태 3에 따른 오류 정정 방법의 순서를 나타낸 흐름도이고, 도면에 있어서, 도 1의 흐름도와 유사한 동작을 나타낸 스텝에는 도 1의 스텝에 붙인 것과 동일한 스텝 번호를 붙인다. 도 4에 있어서, ST9는 수신어의 메모리로의 저장을 나타낸 스텝이다.

다음에 동작에 대하여 설명한다.

수신어(R)와 패리티 행렬(H)을 각각,

R = (r_n-1r_n-2… r₁r₀)

로 할 때(α는 갈루아체의 원시원, j는 임의의 정수),

의 연산에 의해 신드롬(S0,S1,S2,S3)을 계산하고(스텝(ST1)), 이 신드롬(S0,S1,S2,S3)으로부터 오류 개수를 추정한다(스텝(ST3)). 이 추정에 기초하여 오류 위치·오류 수치를 계산하여(스텝 ST4), 오류를 정정한다(스텝(ST5)).

수신어의 메모리 할당 방법을 m = 4, n = 15의 경우를 예를 들어 설명한다. 단, m은 수신어(R)의 각 심벌(r_n-1, r_n-2, …r₁, r₀)을 구성하는 피트수이며, n은 수신어(R)를 구성하는 심벌수이다. 이때, 갈루아체는 GF(16)이고, 그 원시 15승 근(α)은 x⁴+ x + 1 = 0의 근으로 주어진다.

다항식 기저를 이용하여, α^k(k = 0,1,2,…,14)를 다항식 표현하여,

α^k= a_k,3α³+ a_k,2α²+ a_k,1α + a_k,0

로 나타낸다. 이를 도 5에 나타낸다. 수신어(R)를,

R = (r₁₄r₁₃… r₁r₀)

로 하면, 각 심벌은 도 6과 같이 메모리에 저장된다(스텝(ST9)).

상기에서 이용한 기저는 다항식 기저에 한정되지 않으며, 정규 기저 등의 기저라면 어떠한 것이라도 가능하지만, 갈루아체의 연산은 그 정해진 기저상에서 행하지 않으면 안된다.

스텝(ST3)에 있어서의 오류 개수의 추정의 결과, 1중 오류가 발생하였다고 추정되면, 오류 위치(i)와 오류 수치(e)는,

αⁱ= S1/S0 e = S0

의 관계를 만족한다. 이때 오류를 포함하는 심벌은 ri이고, 이것은 메모리의주소αⁱ, 즉, S1/S0에 저장된 데이타이다. 이 데이타에 신드롬(S0)을 가산함에 의해 스텝(ST5)의 오류 정정을 행한다.

2중 오류가 발생하였다고 추정되면, 오류 위치 방정식이

ax²+ bx + c = 0

로 주어지며, 이 방정식이 0이 아닌 상이한 2근(u = αⁱ, v = α^j)을 가진다고 한다(그렇지 않을 때는 2중 오류가 아니므로, 오류 검출을 정지함). 이때, 오류를 포함하는 심벌은 r_i와 r_j이며, 메모리의 주소(αⁱ와 α^j), 즉, 2근(u,v)에 저장된 데이타이다. 이 데이타에 각각, 오류 수치(e_u, e_v)를 가산함에 의해 오류의 정정을 행한다.

상기와 같이, 이 실시 형태 3에 의하면, 오류 위치 방정식의 근을 수신어의 심벌의 주소로 함으로써, 종래와 같이 ROM을 검색하지 않고, 오류 위치를 갈루아체의 원으로부터 바로 계산하여 정정할 수 있어, 오류 위치를 단시간에 계산할 수 있는 동시에, 검색하기 위한 ROM이 불필요해진다는 효과가 얻어진다.

실시 형태 4

이 실시 형태 4는 도 3에 나타낸 실시 형태 2에서 사용한 오류 정정 방법의 순서에 있어서, 오류 개수의 추정 스텝(스텝(ST3))에 실시 형태 1의 방법을 사용한 것으로, 오류 검출율을 높이며, 또한 복호 지연의 개선을 도모한 것이다.

다음에 동작에 대하여 설명한다.

수신어(R)와 패리티 행렬(H)을 각각,

R = (r_n-1r_n-2… r₁r₀)

로 할 때(α는 갈루아체의 원시원),

의 연산에 의해 신드롬(S0,S1,S2,S3)을 계산하고(스텝(ST1)), 계산한 신드롬(S0,S1,S2,S3)에 의해 오류 개수를 추정하고(스텝(ST3)), 오류 위치 및 오류 수치를 계산하여(스텝 ST6, ST7) 오류 정정을 행한다(스텝(ST5)).

스텝(ST3)의 오류 개수 추정에 있어서,

A = S0 S2 + S1²

B = S1 S2 + S0 S3

C = S1 S3 + S2²

를 연산하여, 실시 형태 1의 방법에 의해 오류 개수를 추정하여, 2중 오류라고 추정되었을 때, 오류 위치 방정식을,

Ax²+ Bx + C = 0

로 주어지고, 이 방정식이 0이 아닌 상이한 2근(u,v)을 가진다고 할 때, 대응하는 오류 수치를 각각 e_u, e_v로 하면, 실시 형태 2와 동일하게 하여 2중 오류가 발생하였다고 추정되었을 때는 다항식,

e (x) = A/B (S0 x + S1) + S0

를 계산하여, 2근(u,v)을 대입함에 의해 오류 수치(e_u,e_v)를 계산한다.

상기와 같이, 이 실시 형태 4에 의하면, 오류 검출율이 높아지고, 또한 복호 지연이 개선되는 효과가 얻어진다.

실시 형태 5

이 실시 형태 5는 도 4에 나타낸 실시 형태 3에서 사용한 오류 정정 방법의 순서에 있어서, 오류 개수의 추정 스텝(스텝(ST3))에 실시 형태 1의 방법을, 오류 위치·오류 수치의 계산 스텝(스텝 ST4)에서 2중 오류라고 추정된 경우에 실시 형태 2의 방법을 사용한 것으로, 오류 검출율을 높이고, 복호 지연을 개선하며, 또한 회로 규모를 간소화할 수 있는 것이다.

다음에 동작에 대하여 설명한다.

수신어(R)와 패리티 행렬(H)을 각각,

R = (r_n-1r_n-2… r₁r₀)

로 할 때(α는 갈루아체의 원시원)

의 연산에 의해 신드롬(S0,S1,S2,S3)을 계산하고(스텝(ST1)), 계산된 신드롬(S0,S1,S2,S3)으로부터 실시 형태 1과 동일하게 하여 오류 개수를 추정한다(스텝(ST3)). 이때 2중 오류로 추정된 경우, 실시 형태 2와 같은 오류 추정의 처리를 행하며(스텝(ST3, ST8)), 이 추정에 기초하여 오류를 정정한다 (스텝(ST5)).

실시 형태 3과 같이 수신어의 메모리 할당 방법을 m = 4, n = 15 인 경우를 예로 들어 설명한다. 이때, 갈루아체는 GF(16)이고, 그 원시 15 승 근(α)은 X⁴+ X + 1 = 0의 근으로 주어진다. 다항식 기저를 이용하여, α^k(k = 0,1,2,…,14)을 다항식 표현하여,

α^k= α_k,3α³+ a_k,2α²+ a_k,1α + a_k,0

로 나타낸다. 수신어(R)를,

R = (r₁₄r₁₃… r₁r₀)

로 하면, 각 심벌은 실시 형태 3에서 나타낸 도 6과 같이 메모리에 저장된다.

상기에서 이용한 기저는 다항식 기저에 한정되는 것이 아니고, 정규 기저 등의 기저이면 어떤 것이라도 가능하며, 갈루아체의 연산은 그 정한 기저상에서 행하지 않으면 안된다.

1중 오류가 발생하였다고 추정하면, 오류 위치(i)와 오류 수치(e)는

αⁱ= S1/S0 e = S0

의 관계를 만족한다. 이때 오류를 포함하는 심벌은 r_i이고, 이것은 메모리의 주소αⁱ, 즉, S1/S0에 저장된 데이타이다. 이 데이타에 S0을 가산함에 의해 정정을 행한다.

2중 오류가 발생하였다고 추정한다. 오류 위치 방정식이,

Ax²+ Bx + C = 0

로 주어지며, 이 방정식이 0이 아닌 상이한 2근(u = αⁱ, v = α^j)을 가진다고 한다(그렇지 않을 때는 오류 검출을 정지함). 이때, 오류를 포함하는 심벌은 r_i와 r_j이고, 메모리의 주소(αⁱ과 α^j), 즉, u와 v에 저장된 데이타이다. 이 데이타에 각각, 오류 수치(e_u,e_v)를 가산함에 의해 정정을 행한다.

상기와 같이, 이 실시 형태 5에 의하면, 오류 검출율을 높이고, 복호 지연을 개선하며, 또한 회로 규모를 간소화할 수 있는 효과가 얻어진다.

실시 형태 6

도 7은 본 발명의 실시 형태 6에 따른 오류 정정 장치를 나타낸 구성도이고,도면에 있어서, 10은 입력된 수신어로부터 신드롬(S0,S1,S2,S3)을 생성하는 신드롬 생성 수단(신드롬 생성 수단, 정정 불가능성 판정 수단)(11)은 신드롬 생성 수단(10)에 있어서 계산된 신드롬(S0,S1,S2,S3)으로부터, 연산식,

A = S0 S2 + S1²

B = S1 S2 + S0 S3

C = S1 S3 + S2²

를 생성하는 연산식 생성 수단이고, 12는 신드롬 및 연산식으로부터 수신어중의 오류 개수를 추정하는 오류 개수 추정 수단이며, 13은 오류 개수 추정 수단(12)에 있어서 1중 또는 2중 오류가 발생하였다고 추정하였을 때 오류 위치 및 오류 수치를 계산하는 오류 위치·오류 수치 계산 수단이고, 14는 입력되는 수신어를 기억하기 위한 메모리로 형성되는 기억 수단이며, 15는 수신어의 오류를 정정하는 오류 정정 수단이다.

도 8은 오류 개수 추정 수단(12)의 구성을 상세하게 나타낸 구성도이며, 도면에서 19는 각 신드롬(S0,S1,S2,S3)이 모두 0인지의 여부(즉 S0 = S1 = S2 = S3 = 0인지의 여부)를 검출하는 제1검출 수단, 20은 각 신드롬(S0,S1,S2,S3)이 S0 = S1 = 0 또는 S2 = S3 = 0 또는 S3 = S1 = 0 또는 S0 = S2 = 0인지의 여부를 검출하는 제2검출 수단이며, 21은 연산식(B)이 0이 아닌지의 여부(즉 B≠0인지의 여부)를 검출하는 제3검출 수단, 22는 연산식(A,B,C)이 모두 0인지의 여부(즉, A = B = C = 0인지의 여부)를 검출하는 제4검출 수단이다.

다음에 동작에 대하여 설명한다.

먼저, 수신어가 신드롬 생성 수단(10) 및 기억 수단(14)에 입력되고, 신드롬 생성 수단(10)에서는 수신어의 신드롬이 생성된다. 또한, 기억 수단(14)에서는 수신어가 그대로 기억된다.

다음에, 연산식 생성 수단(11)에 있어서, 신드롬 생성 수단(10)에서 생성된 신드롬으로부터 연산식이 생성되고, 이를 오류 개수 추정 수단(12)에 입력한다. 오류 개수 추정 수단(12)에서는 상기 제 1검출 수단에서부터 제4검출 수단에 의해서 검출된 중에서 작은 번호부터 우선적으로 검출하고, 그 번호가 제1일 때는 오류 없음이라고 추정하고, 제2일 때는 3중 이상의 오류가 발생하였다고 추정하며, 제3일때는 2중 오류가 발생하였다고 추정하고, 제4일 때는 1중 오류가 발생하였다고 추정하며, 제1에서부터 제4중 아무 것도 없을 때는 3중 이상의 오류가 발생하였다고 추정한다.

오류 개수 추정 수단(12)에서 오류 없음이라고 추정되었을 때는 수신어를 그대로 출력하며, 1 또는 2중 오류가 발생하였다고 추정되었을 때는 오류 위치·오류 수치 검출 수단(13)에서 오류 위치 및 오류 수치를 계산하고, 오류 정정 수단(15)에서 오류를 정정하여 출력하며, 3중 이상 오류가 발생하였다고 추정되었을 때는 오류 검출 플래그와 동시에 출력한다.

상기와 같이, 이 실시 형태 6에 의하면, 신드롬만으로부터 오류 정정의 불가능성을 판정할 수 있는 동시에, 연산식(B)만으로부터 2중 오류를 추정할 수 있으며, 또한 신드롬만으로서는 오류 정정의 불가능성이 판정할 수 없는 특수한 경우에도 연산식에 의해 정정의 불가능성이 판정할 수 있는 효과가 얻어진다.

실시 형태 7

도 9는 본 발명의 실시 형태 7에 따른 오류 정정 장치를 나타낸 구성도이고, 도면에 있어서 도 7의 실시 형태 6의 구성 요소와 동일한 구성 요소에는 동일 부호를 붙이고, 그 설명을 생략한다.

도 9에 있어서, 16은 1중 오류 또는 2중 오류가 발생된 것으로 추정되었을 때, 오류 위치를 계산하는 오류 위치 계산 수단이고, 17은 오류 수치를 계산하는 오류 수치 계산 수단이다. 18은 2중 오류로 추정된 때, 다항식,

e(x) = a/b (S0 x + S1) + S0

을 생성하는 다항식 생성 수단이다.

다음에 동작에 대해 설명한다.

먼저 수신어가 신드롬 생성 수단(10) 및 기억 수단(14)에 입력된다. 신드롬 생성 수단(10)에서 수신어의 신드롬이 생성된다. 또한, 기억 수단(14)에 수신어가 그대로 기억된다.

다음에, 오류 개수 추정 수단(12)에서 2중 오류가 발생된 것으로 추정된 때, 오류 위치 계산 수단(16)에 있어서, 오류 위치 방정식,

ax²+ bx + c = 0

으로부터, 2근(u,v)을 구함과 동시에, 다항식 생성 수단(18)에서 다항식,

e(x) = a/b (S0 x + S1) + S0

을 생성한다. 오류 수치 계산 수단(17)에서는, 이것에 2근(u,v)을 대입하여 대응하는 오류 수치(e_u,e_v)를 계산한다.

상기와 같이, 이 실시 형태 7에 따르면, 나눗셈(a/b)을 단지 1회 행하는 것만으로 오류를 정정할 수 있다는 효과가 얻어진다.

실시 형태 8

도 10은 본 발명의 실시 형태 8에 따른 오류 정정 장치를 나타낸 구성도이며, 도면에 있어서 도 7의 실시 형태 6의 구성 요소와 동일한 구성 요소에는 동일 부호를 붙이고, 그 설명을 생략한다. 도 11은 도 10의 기억 수단(14)의 상세한 구성을 나타낸 구성도이다.

도 11에 있어서, 23은 랜덤 액세스 메모리(메모리)이고, 24는 주소 신호를 생성하는 주소 생성 수단이다.

다음에 동작에 대하여 설명한다.

도 10에서는, 먼저, 수신어가 신드롬 생성 수단(10) 및 기억 수단(14)에 입력된다. 신드롬 생성 수단(10)에 있어서 수신어의 신드롬이 생성된다.

이때, 기억 수단(14)에서는 수신어의 각 심벌이 주소 생성 수단(24)에 입력되어 주소가 생성되고, 생성된 주소에 기초하여, 각 심벌이 랜덤 액세스 메모리(23)에 저장된다.

수신어의 메모리 할당 방법을 m = 4, n = 15의 경우를 예를 들어 설명한다. 이때, 갈루아체는 GF(16)이고, 그 원시 15 승 근(α)은 x⁴+ x + 1 = 0의 근으로 주어진다. 다항식 기저를 이용하여, α^K(k = 0,l,2, …,14)을 다항식으로 표현하여,

α^K= a_k.3α³+ a_k.2α²+ a_k.1α + a_k.2

로 된다. 이것은 도 5에 나타낸 것과 동일하다.

수신어(R)를,

R = (r₁₄r₁₃… r₁r₀)

로 한다.

도 12는 수신어의 입력부의 구성을 나타낸 구성도이고, 도면에 있어서, 25는 버퍼이며, 26은 α^-1승산기이다.

심벌은 최상위 심벌(r₁₄)로부터 차례로 메모리(23)에 저장된다. 각 심벌은 한번 버퍼(25)에 저장되며, α^-1승산기(26)에서 지정된 주소에 저장된다.

오류 개수 추정 수단(12)에서 1중 오류가 발생된 것으로 추정되면, 오류 정정 수단(15)에서는 메모리의 주소(S1/S0)에 저장된 데이타에 신드롬(S0)을 가산함으로써 정정을 행한다.

오류 개수 추정 수단(12)에서 2중 오류가 발생된 것으로 추정되면, 오류 위치·오류 수치 계산 수단(13)에서 오류 위치 방정식,

ax²+ bx + c = 0

의 2근(u,v) 및 오류 수치(e_u,e_v)를 계산하고, 오류 정정 수단(15)에서 메모리의 주소(u,v)에 저장된 데이타에 각각 e_u, e_v를 가산함으로써 정정을 행한다.

상기와 같이, 이 실시 형태 8에 따르면, 오류 정정에 있어서, ROM을 검색하지 않고, 오류 위치를 갈루아체의 원으로부터 바로 계산하여 정정할 수 있으며, 오류 위치를 단시간에 계산할 수 있는 동시에, 검색용 ROM이 필요없게 된다는 효과가 얻어진다.

실시 형태 9

도 9에 나타낸 실시 형태 7에 따른 오류 정정 장치에서, 오류 개수 추정 수단(12)에 실시 형태 1의 오류 정정 방법을 적용함으로써, 오류 검출율을 높이며, 또한 복호 지연의 개선을 도모한 오류 정정 장치가 얻어진다.

다음에 동작에 대하여 설명한다.

먼저, 수신어가 신드롬 생성 수단(10) 및 기억 수단(14)에 입력된다. 신드롬 생성 수단(10)에서 수신어의 신드롬이 생성된다. 또한, 기억 수단(14)에 수신어가 그대로 기억된다.

다음에, 오류 개수 추정 수단(12)에 있어서, 실시 형태 1과 같이 감산식,

A = S0 S2 + S1₂

B = S1 S2 + S0 S3

C = S1 S3 + S2²

를 생성하며, (S0 = S1 = S2 = S3 = 0)을 검출하는 제1검출 수단, (S0 = S1 = 0 또는 S1 = S2 = 0 또는 S2 = S3 = 0 또는 S3 = S1 = 0 또는 S0 = S2 = 0)을 검출하는 제2검출 수단, (B ≠ 0)을 검출하는 제3검출 수단, (A = B = C = 0)을 검출하는 제4검출 수단으로부터, 제1검출 수단부터 우선적으로, 신드롬(S0,S1,S2,S3) 또는 연산식(A,B,C)의 상태를 검출하고, 상기 각 상태를 검출한 검출 수단의 번호가 제1일 때는 오류 없음으로 추정하고, 제2일 때는 3중 이상 오류가 발생한 것으로 추정하며, 제3일 때는 2중 오류가 발생한 것으로 추정하고, 제4일 때는 1중 오류가 발생한 것으로 추정하며, 제1검출 수단에서부터 제4검출 수단중 어떠한 검출 수단도 상기 각 상태를 검출하지 못할 때에는 3중 이상의 오류가 발생된 것으로 추정한다.

상기 오류 개수 추정 수단(12)에서 2중 오류가 발생된 것으로 추정된 때, 오류 위치 계산 수단(16)에서, 오류 위치 방정식,

Ax²+ Bx + C = 0

으로부터, 2근(u,v)을 구함과 동시에, 다항식 생성 수단(18)에 다항식,

e (x) = A/B (S0x + S1) + S0

을 생성한다. 오류 수치 계산 수단(17)에서는, 이것에 u, v를 대입하여 대응하는 오류 수치(e_u,e_v)를 계산한다.

상기와 같이, 이 실시 형태 9에 따르면, 신드롬과 연산식으로부터 바로 오류 개수를 정확히 추정할 수 있고, 또한 나눗셈(A/B)을 단지 1회 행하는 것만으로 오류를 정정할 수 있는 효과가 얻어진다.

실시 형태 10

도 10에 나타낸 실시 형태 8에 따른 오류 정정 장치에서, 오류 개수 추정 수단(12) 및 오류 위치·오류 수치 계산 수단(13)에 실시 형태 9와 동일한 구성을 사용함에 따라 오류 검출율을 높이고, 복호 지연을 개선하며, 또한 회로 규모를 간소화시키는 오류 정정 장치를 실현할 수 있다.

즉, 연산식(A,B,C)을 생성하고, 제1내지 제4검출 수단에 의해 오류의 개수를 추정하며, 오류 위치 방정식의 2근을 다항식에 대입하여 대응하는 오류 수치를 얻도록 한다.

상기와 같이, 이 실시 형태 10에 따르면, 오류 검출율을 높이고 복호 지연을 개선하며, 또한 회로 규모를 간소화할 수 있다는 효과가 얻어진다.

이상과 같이, 본 발명에 따르면, 신드롬만에 의해 오류를 정정하는 것이 불가능한지를 판정하므로, 오류의 정정이 불가능한 경우에 불필요한 계산을 행하지 않고 신속하게 다음 수신어의 처리에 착수할 수 있다고 하는 효과가 있다.

Claims

오류 정정 방법에 있어서,

수신어로부터 4개의 신드롬(S0,S1,S2,S3)을 생성하는 신드롬 생성 단계;

상기 모든 신드롬이 제로이면 오류가 발생하지 않았다고 추정하고, 상기 신드롬에 기초하여, 3중 오류가 발생하면 상기 수신어의 오류 정정이 불가능하다고 추정하는 제 1 단계;

상기 신드롬들에 기초하여,인 세개의 연산식 A, B 및 C를 생성하는 연산식 생선 단계;

상기 제 1 단계가 3중 오류가 아닌 오류가 발생하였다고 추정하면, 상기 연산식들에 기초하여 상기 수신어 중의 오류 개수를 추정하는 제2단계로, 오류 개수의 추정은, 상기 모든 연산식이 제로일 때 상기 수신어에 단일 오류가 발생했다고 추정하고, B가 제로가 아닐 때 수신어에 2중 오류가 발생했다고 추정하고, B가 제로이고 A 또는 C가 제로가 아니면 수신어에 3중 오류가 발생했다고 추정하는 식으로 이루어지는 제2단계;

상기 단일 오류 또는 2중 오류가 발생했을 때 오류 위치와 오류 값을 계산하는 계산 단계; 및

상기 계산 단계에서 계산된 오류 위치와 오류 값에 기초하여 상기 오류를 정정하는 정정 단계를 포함하는 오류 정정 방법.
제1항에 있어서, 수신어 중에 2중 오류가 발생한 것으로 추정되는 경우에 상기 신드롬들과 상기 연산식들에 기초하여인 오류 위치 다항식과인 오류 값 다항식 Q(X)을 생성하는 다항식 생성 단계;

상기 오류 위치 다항식 P(X)의 근을 구함으로써 오류 위치를 결정하기 위한 오류 위치 결정 단계; 및

상기 오류 위치 다항식 P(X)의 근을 상기 오류 값 다항식 Q(X)에 대입함으로써 오류 값을 결정하는 오류 값 결정 단계를 더 포함하는 오류 정정 방법.
갈루아체(Galois field)의 원시인(primitive element)에 기초하여 수신어의 각 심벌의 주소를 생성하는 주소 생성 단계;

상기 주소 생성 단계에서 생성된 상기 주소에서 상기 각 심벌을 저장하는 저장 단계;

상기 수신어로부터 신드롬을 생성하는 신드롬 생성 단계;

상기 신드롬 생성 단계에서 생성된 상기 신드롬에 기초하여 연산식을 생성하는 연산식 생성 단계;

상기 연산식 생성 단계에서 생성된 연산식으로부터 상기 수신어중의 오류 개수를 추정하는 오류 개수 추정 단계;

상기 오류 개수 추정 단계에서 오류가 발생한 것으로 추정한 경우에 발생된오류의 위치 및 수치를 계산하는 오류 위치·오류 값 계산 단계;

상기 오류 위치·오류 값 계산 단계에서 계산된 상기 오류 위치 및 오류 값에 기초하여 상기 저장 단계에서 저장된 상기 각 심벌을 판독하여 상기 수신어의 오류를 정정하는 오류 정정 단계를 포함하는 오류 정정 방법.
오류 정정 장치에 있어서,

수신어로부터 4개의 신드롬(S0,S1,S2,S3)을 생성하는 신드롬 생성 수단;

상기 모든 신드롬이 제로이면 오류가 발생하지 않았다고 추정하고, 상기 신드롬들에 기초하여, 3중 오류가 발생하면 상기 수신어의 정정이 불가능하다고 추정 하는 제 1 수단;

상기 신드롬에 기초하여인 3개의 연산식 A,B 및 C를 생성하는 연산식 생성 수단;

상기 제 1 수단이 3중 오류가 아닌 오류가 발생하였다고 추정하면, 상기 연산식들에 기초하여 상기 수신어 중의 오류 개수를 추정하는 제 2 수단으로, 오류 개수의 추정은, 상기 모든 연산식이 제로 일때 상기 수신어에 단일 오류가 발생했다고 추정하고 B가 제로가 아닐 때 수신어에 2중 오류가 발생했다고 추정하고, B가 제로이고 A 또는 C가 제로가 아니면 수신어에 3중 오류가 발생했다고 추정하는 식으로 이루어지는 제2수단;

상기 단일 오류 또는 2중 오류가 발생했을 때 오류 위치와 오류 값을 계산하는 계산 수단; 및

상기 계산 수단에서 계산된 오류 위치와 오류 값에 기초하여 상기 오류를 정정하는 정정 수단을 포함하는 오류 정정 장치.
갈루아체의 원시인에 기초하여 수신어의 각 심벌의 주소를 생성하는 주소 생성 수단;

상기 주소 생성 수단에 의해 생성된 상기주소에 상기 각 심벌을 저장하는 메모리;

상기 수신어로부터 신드롬을 생성하는 신드롬 생성 수단;

상기 신드롬 생성 수단에 의해 생성된 상기 신드롬에 기초하여 연산식을 생성하는 연산식 생성 수단;

상기 연산식 생성 수단에 의해 생성된 상기 연산식으로부터 상기 수신어중의 오류 개수를 추정하는 오류 개수 추정 수단;

상기 오류 개수 추정 수단에 의해 오류가 발생한 것으로 추정되는 경우에, 발생된 오류의 위치 및 수치를 계산하는 오류 위치·오류 값 계산 수단; 및

상기 오류 위치·오류 값 계산 수단에 의해 계산된 상기 오류 위치 및 오류 값에 기초하여 상기 메모리의 상기 오류 위치에 대응하는 주소에 저장된 상기 각 심벌을 판독하여 상기 수신어의 오류를 정정하는 오류 정정 수단을 구비하는 오류 정정 장치.