KR880000426B1

KR880000426B1 - 이중 부호화 리드 솔로몬 코드에 대한 복호화 방법 및 장치

Info

Publication number: KR880000426B1
Application number: KR1019840006733A
Authority: KR
Inventors: 히로오 오가모도; 마사하루 고바야시; 히로고기 기무라; 다가하루 노꾸찌; 다가오 아라이
Original assignee: 가부시기 가이샤 히다찌세이 사꾸쇼; 미쓰다 가쓰시게
Priority date: 1983-10-31
Filing date: 1984-10-29
Publication date: 1988-03-22
Also published as: EP0140381A3; JPS6095640A; JPH0812612B2; US4646301A; CA1220869A; DE3484223D1; ATE61494T1; EP0140381A2; EP0140381B1; KR850003096A

Abstract

내용 없음.

Description

이중 부호화 리드 솔로몬 코드에 대한 복호화 방법 및 장치

제1도는 이중 부호화된 에러 정정 코드의 데이타 배열을 나타낸 도면.

제2도는 C₁복호화의 순서도.

제3도는 C 복호화의 1예의 순서도.

제4도와 제5도는 4개의 플래그를 갖는 C₂블럭을 위한 에러 패턴을 나타낸 도면.

제6도는 본 발명의 C₂복호화의 순서도.

제7도와 제8도는 C₂블럭에 대한 잘못 정정 및 정정 불능정정에러 패턴을 나타낸 도면.

제9도는 제6도의 상세도.

제10도는 본 발명의 또 다른 실시예에 대한 순서도.

제11도는 제10도의 방법을 실현하기 위한 장치의 1실시예의 블럭도.

제12도는 이중 부호화된 에러 정정 코드의 또 다른 예이다.

제13도는 본 발명이 제12도의 코드에 적용될 때의 C₂복호화의 순서도.

제14도는 본 발명의 에러 정정 회로의 1실시예의 블럭도.

제15도는 DAD에 적용된 본 발명의 실시예에 대한 순서도.

제16도는 제15도를 상세히 나타낸 순서도.

제17도는 제15도와 제16도의 실시예의 에러 검출 능력과 에러 정정 능력에 대한 종래의 장치와 비교한 장치의 비교 특성 곡선을 나타낸 도면.

이 출원은 오가모도 히로오, 고바야시 마사하루, 니시무라겐조, 노꾸찌 다가하루, 아라이 다가오, 시부야 도시후미의 "에러 정정 방법 및 장치"라는 명칭으로 1984년 6월 22일에 출원된 미국 특허 출원번호 No. 622,711에 관하여 이는 1983년 6월 22일에 제출된 No. 110931/83과 1983년 6월 20일에 출원된 No. 130839/83과 1983년 11월 11일에 출원된 No. 210858/83인 일본 특허출원에 기초를 두고 있으며, 본 출원에 참조로 하여 통합시킨 것이다.

본 발명은 디지탈 신호 재생에서의 에러 정정, 특히 이중 부호화 리드 솔로몬(Reed Solomon)코드와 같은 에러정정 코드의 복호화에 적합한 에러 정정 방법 및 장치에 관한 것이다.

디지탈 신호를 전송하는 많은 경우에, 검사워드는 송신국에서 붙여지고, 전송될 데이타의 에러는 전송계에서 발생된 데이타 에러를 정정하기 위해 검사워드를 써서 수신국에서 검출, 정정된다. 대부분의 경우, 효율적이며, 복호화하기 쉬운 BCH코드중의 하나인 리드 솔로몬 코드가 검사워드로서 사용된다. 이중 부호화 리드 솔로몬 코드는 에러 정정 능력이 높고, 디지탈 오디오 디스크(DAD)와 PCM 녹음기에서 사용된다.

제1도는 이중 부호화 리드 솔로몬 코드의 1예이다.

(1)은 정보워드, (2)는 제1의 검사워드, (3)은 제2의 검사워드이다. 부호화에서는 제1의 검사워드 Q₀, Q₁, Q₂, Q₃가 12개의 정보워드 W₀-W₁₁에 부가된다.

12개의 정보워드와 4개의 제1의 검사워드로 구성된 블럭을 C₂블럭(5)라고 한다. C₂블럭(5)의 워드들은 제1도에 도시한 배열 사이에 끼워진다. 제2의 검사워드 P₀와 P₁이 C₂블럭(5)의 정보워드 W₀-W₁₁와 제1의 검사워드 Q₀, Q₁, Q₂, Q₃에 부가된다. 12개의 정보워드와 제1의 4개의 검사워드, 제2의 2개의 검사워드로 구성된 블럭을 C₁블럭이라고 한다. 복호화에서는, C₁블럭에 대한 에러 검출과 정정을 하여 복호화 신호가 빼내어지고, C₂블럭에 대한 에러 검출과 정정을 하여 이 복호화된 신호가 출력된다.

이중 부호화 장치에서는, 두 개의 다른 코드 블럭(C₁과C₂)에 대해 2번 이상 복호화 함으로써 정정 능력이 향상된다. 이와같은 이러 정정 장치는 1984년 3월 13일에 사코(Sako)에 의하여 미국 특허 4,437,185로 등록되었다(영국 특허 GB 2079993A). 그러나 위와같은 복화호 장치에서는, 단지 하나 또는 두 단어만이 정정되며, 그 코드의 고유의 정정 능력이 충분히 사용되지 않았다. 에러 검출 플래그가 두번째 복호화에서 충분히 사용되지 않았기 때문에, 그 코드의 정정이 감소된다.

본 발명의 목적은 이중 부호화된 에러 정정 코드의 고유의 에러 검출 및 정정 능력을 충분히 활용할 수 있는 에러 정정 방법 및 장치를 마련하는데 있다.

본 발명의 한 결해에 의하면, 에러의 수는 이중 부호화된 에러 정정 부호의 제2복호화에서 검출되고, 소실과 에러 정정은 검출 결과에 따라 잘못 정정할 확률이 작을 때에만 영향을 받는 에러 정정 방법 및 장치를 마련하는 것이다.

본 발명의 또 다른 견해에 따르면, 에러의 확률이 높고 에러가 적을 때 이중 부호화된 에러 정정의 제2의 두번째 복호화에서 하나의 에러가 정정되며, 에러의 확율이 작은 에러는 순차적으로 검출되고, 소실에 대한 정정 횟수는 여러 검출 및 정정 능력을 증가시키기 위해서 제1의 복호화 결과 나타나는 플래그의 상태와 검출 능력 결과에 따라 증가되는 에러 정정 방법 및 장치를 마련하는 것이다.

본 발명의 또 다른 견해에 따르면, 이중 부호화된 리드 솔로몬 코드와 같은 에러 정정 코드는 디지탈 오디오 시스템의 디지탈 신호를 재생하는데 사용되며, 제1의 복호화와의 상태를 나타내는 플래그가 부가되며, 신호는 에러 워드의 위치와 에러 패턴을 결정하여 플래그를 사용하는 것에 의해 제2의 복호화에서 한번 이상 복호되며, 원하는 조건에 합당한 결과가 그 워드에 있는 에러를 정정하기 위하여 선택되는에러 정정 방법 및 장치를 마련하는 것이다.

본 발명의 개요는 다음과 같다.

제1의 복호화는 이중 부호화된 에러 정정 부호에 따르고, 복호 상태를 나타내는 플래그가 부가된다. 제2의 복호화에서, 복호는 플래그를 사용하여 한번 이상 영향을 받으며, 최적 복호화 방법이 복호 결과에 따라 결정되며, 그 최적 복호화 방법에 의한 복호 결과에 따라 에러 정정이 행하여진다. 따라서 에러 검출 및 정정 능력은 향상된다.

제2의 복호화 방법에 대한 선택 평가기준은 제1의 복호화에서 부가된 플래그 발생확률, 에러 검출의 실패의 확률, 제2의 복호화에서 코드 정정의 무능의 확률과 검출무능의 확률에 의해 결정되는 정정 및 검출능력에 대한 조건이나 절충에 의하여 결정된다.

본 발명의 실시예 전에 본 발명의 이해를 쉽게하기 위하여 관련된 미국 출원번호 622,711의 발명을 간단히 설명한다. 관련된 발명은 본 발명 이전에는 공개되지 않았으며 종래의 기술로서 인용되지 않았다. 본 명세서의 참고로서 삽입하였다.

관련된 출원에서는(1984년 6월 20일에 출원된 유럽 특허 출원번호 84107110. 3). 제1도의 복호화 방법은 C₁블럭에서 코드 길이가 18, 2개의 검사 헤드와 해밍(Hamming)거리 3이고, C₂블럭에서 코드 길이가 16, 4개의 검사워드의 해밍거리 5인 리드 솔로몬 코드를 사용하였다. 따라서, C₁복호화에서는 하나의 에러 워드 정정이 가능하고, C₂복호화에서는 에러의 위치를 알 수 없는 S에러와 에러의 위치를 알 수 있는 E에러에 대해서 2S + E

4의 범위에서 4의 정정이 가능하다(이하, 전자를 에러로 후자를 소실로 한다).

따라서, C₁복호화에서는 에러의 검출과 하나의 워드 정정을 행하며, 복호화 조건을 나타내는 플래그가 각각의 워드에 부가되고, C₂복호화에서는 각 워드에 부가되는 플래그의 조건에 따라 다음의 세가지 복호화중 하나를 행하는 것에 의해 오차 교정의 능력을 높일 수가 있다.

(1) S=2 E=0 : 2개까지의 오차를 정정.

(2) S=1 E=2 : 하나의 정정과 2개의 소실을 정정.

(3) S=0 E=4 : 4개의 소실을 정정.

제2도는 C₁복호화에 대한 순서도이다. N(E)는 C₁복호화에서 에러가 하나일때 검출된 에러의 수이고, 하나의 워드 정정이 수행된다. F₀플래그와 F₁플래그는 C₁복호화에서 복호화 상태를 나타내는 플래그로서 사용된다. F₀플래그는 에러가 검출되었을때 "1"로 세트되고, F₁플래그는 둘 이상의 에러가 있어 정정을 할 수 없을 때 "1"로 세트된다. 제3도는 C₂복호화에 대한 순서도이다. N(F₀)는 F₀플래그의 수를 N(F₁)은 F₁플래그의 수를 나타낸다. C₂복호화에서 블럭의 플래그 수와 일치하는 에러 상태를 추측하여 최적의 복호화 방법을 결정하고 선택한다. 예를들면 N(F₀)=4일 때, 즉, F₀플래그의 수(F₁플래그가 부가되어 있는 것도 포함)가 4일 때, 플래그가 부가된 위치는 에러의 위치(에러의 위치를 알고 있는 에러)로서 추측하고 공식(3)으로 소실 정정을 한다. 제4도는 하나의 C₂블럭에 세개의 에러가 포함된 경우의 예를 나타낸다. (6)은 C₁블럭을 나타내고, (7)은 C₂블럭을, (8)은 플래그된 에러 워드를, (9)는 실제로 정정하는 플래그된 워드를 나타낸다. 이는 단어(9)가 있는 C₁블럭에서 에러가 있음을 나타낸다.

C₁복호화에서 에러가 검출되면, 블럭에 있는 모든 워드(심벌들)에 플래그가 부가된다. 하나의 워드에 에러가 있을 때에는 C₁복호화로 정정된다. 둘 또는 그 이상의 워드에 오차가 있을 때에는, 맞는 워드와 에러 워드가 있으므로, 그에 따라 플래그된 맞는 워드와 플래그된 에러 워드가 있게 된다.

공식(3)의 소실 정정에서는 4개의 플래그된 에러워드까지 정정될 수 있다. 그러나, 에러 위치 검출 능력 F₁플래그 C₂블력이 없으므로 제5도의 블럭 7에서 워드 x로 표시된 것처럼 플래그되지 않은 에러가 있을 경우 틀리게 정정될 수도 있다. 왜냐하면, x위치에 있는 워드는 에러워드로 인식되지 않은채 소실 정정이 되기 때문이다. 제5도에 도시한 예를보면, (10)은 플래그 되지 않은 에러를 나타내는데 C₁복호화 과정에서 에러가 검출되지 않았기 때문이다. 따라서, 제1도에 도시한 P₀와 P₁과같이 C₁의 검사워드의 수가 작고 에러의 검출 능력이 충분하게 마련되지 않은 경우 문제가 발생한다. 제1도에서는 검사워드의 수가2(P₀, P₁)이므로 3개나 그 이상의 에러가 있으면 검출을 못할 수도 있다. 검출을 실패했을 때의 잘못 정정을 막기 위해서 N(F₀)=4일때 에러 정정(1)이 실시된다. 이 경우는 검출 실패에 의해 플래그되지 않은 에러가 검출될 수 있고, 하나의 플래그된 워드가 하나 이하라면 정정한다. 그러나, C₁복호화 후에 에러 정정(1) (S

2, E=0)을 하면, 제4도처럼 3개 이상의 에러가 있을때 에러는 정정되지 않는다. 본 발명은 이러한 정정 능력의 한계를 개선하기 위한 해결책을 제시한 것이다.

본 발명의 1실시예는 제1도에 도시한 에러 정정 코드를 참고로하여 설명한다.

상술한 바와같이, 제1도의 에러 정정 코드를 복호화하는 데에 있어서, 하나의 워 드에 러는 C₁복호화서 정정되고, 2워드의 정정, 1워드의 정정과 2워드의 소실 정정, 또는 4워드의 소실 정정은 C₂복호화에서 한다.

C₁복호화에서, 에러의 검출과 하나의 워드의 정정은 제2도와 같은 방법으로 이루어지고, 에러가 검출되면 F₀플래그가 부가되고, 에러가 정정 불능이면, 각각의 워드에 F₁플래그가 부가된다.

C₂복호화에 대한 순서도가 있는 제6도와 제9도를 참고로 C₂복호화 과정을 설명하기로 한다.

제9도는 제6도에 도시한 본 발명의 에러 정정 방법을 상세히 나타낸 것이다. L(F₀)와 L(F₁)은 C₂복호화와 F₀로 플래그되거나 F₁으로 플래그된 위치에 의해 검출된 에러 위치의 일치된 수이다. F는 정정 불능워드에 부가된 정정 불능 플래그이다. F=1이면 C₂블럭의 모든 워드가 플래그되고, F=F₀이면 F₀로 플래그된 워드만이 플래그된다. F로 플래그된 워드에 대해서는 평균 보간법으로 재생시 에러가 은폐된다.

(1) 우선, S=2, E=0로 복호화를 행한다. 임의의 위치에서 2워드의 에러까지 검출할 수 있다.

에러의 수가 2개 이하이면, 잘못 정정의 확률은 블럭의 플래그수와 에러의 위치에 부가되는 플래그에 따라 결정되고, 그 확률이 작으면 정정을 실행된다. 잘못 정정의 확률이 높으면 에러는 정정할 수 없다. 예를 들면, 검출된 에러의 수가 하나(N(E)=1)일때, F₁플래그가 검출된 에러 위치에 부가되었는지 검사한다. 그것이부가되었다면 (L(F)=1), 복호화된 결과는 옳고 에러 정정이 실행된다. F₁플래그가 부가되지 않았다면 (L(F)=0), F₁플래그의 수를 검사한다. F₁플래그의 수가 3이하(N(F₁)=3)이면, 복호화된 결과는 옳고 에러 정정이 실행된다. F₁플래그의 수가 3보다 크면(N(F)＞3), 잘못 정정할 확률이 높아서 정정을 실행할 수 없다.

복호화된 결과의 진위를 검사하는 플래그 수의 임계치는 L(F₁)과 N(F₁)의 다양한 값에 대한 잘못 정정의 확률을 미리 계산함으로써 결정된다.

확률을 계산하는 방법은 히데끼 이마이와 야수지 나가사카의 "이중 부호화 시스템의 복호화 방법" Journal of Association of Electronics and Electrical Communication of JAPAN, Vol. J65-A, No. 12, Page 1254-1261.

December 1982와 야시로의 "리드-솔로몬 코드의 상호 삽입법에 관한 복호화 특성", (앞과 동일 잡지) J66-A, No. 3, pp. 284-285, March 1983에 기술되어 있다.

5의 해밍 거리를 갖는 리드 솔로몬 코드에, e + N(E)

0일때 잘못 정정의 확률은 높다(여기에서 e는 실제의 에러수이다). N(E)=1이고 하나의 워드의 에러가 정정되었을 때, 블럭에 4개 이상의 에러가 포함되어 있으면 잘못 정정이 발생한다. N(F₁)＞3이면, 4개 이상의 에러가 포함될 확률은 더 높아지고, 제7도에 도시한 것과 같이 잘못 정정을 실행하게 된다. 제7도에서, (90)은 잘못 정정에 의한 에러로서 맞는 심벌이나 워드가 결정되는 경우를 나타낸 것이다.

(2) 3개 이상의 에러가 (1)에서 검출되고 F₀플래그의 수가 3이면, F₀플래그에 부가되어 있는 세워드중 두 개가 소실되고 S=1, E=2인 복호화가 실행된다. 플래그된 워드들에서만 에러가 검출되었을 경우에는 복호화 결과를 사용하여 정정을 실행한다.

(3) 3개 이상의 에러가 (1)에서 검출되고 F₀플래그의 수가 4이면, 4개의 플래그된 워드들은 소실되고 S=0과 E=4인 복호화가 실행되어 4개의 워드 정정이 이루어진다.

(4) 3개 이상의 에러가(1)에서 검출되고 F₀플래그의 수가 5 이상이고 F₁플래그의수가 3이면 F₁플래그에 부가되어 있는 3개의 워드중 2개가 소실되고, S=1과 E=2인 복호화가 실행된다. F₁으로 플래그된 워드들에서만 에러가 검출되면, 복호화된 결과를 사용하여 정정을 행한다.

(5) 2 내지 3개의 에러가 (1)에서 검출되고 (2)-(4)의 정정 조건에 맞지 않으면, 에러는 정정 불능이 된다.

서로 다른 복호화 방법으로 두번 복호화함으로써 복호화를 한번했을 경우 발생하는 정정 불능이나 잘못 정정된 에러를 바로 잡을 수 있다. 예를들면, 제4도의 에는(3)의 방법으로 정정이 가능하고 제5도의 에는 (1)의 방법으로 바로 잡을 수 있다. N(F₀)=0, 즉, 제8도에 도시한 바와같이 2개 이상의 플래그된 에러를 포함하고 플래그되지 않은 에러도 포함하는 경우에는(1)-(5)까지의 방법으로 에러는 정정 불능이다. 그러한 경우에도 소실위치를 바꾸면서 복호화 횟수를 증가시키고 S=1과 E=2인 복호화를 실행함으로써, 3개의 에러까지는 정정이 된다. (1)-(5)에서 복호화가 두번 실행되는 동안, 동시에 서로 다른 복호화를 할 수 있고, 복호화를 수행한 후에 최적의 복호화 방법의 결정 할 수 있고, 최적 복호화 방법에 의한 복호화 결과를 사용하여 에러 정정을 할 수 있다.

제9도에 도시한 바와같이, C₁복호화에 기부된 F₁플래그와 F₀플래그를 사용하여 복호화 결과를 검사할 수 있으므로, 잘못 정정의 확률이 낮아지고 에러 검출과 정정 능력을 개선하여 훨씬 효율적으로 에러를 정정할 수 있다.

제10도는 동시에 실행되는 2개의 다른 C₂복호화의 순서도이다. "복호화 1"에서는 S=2와 E=0인 복호화(1)이 실행되고, 검출된 에러의 수가 2개 이하이면 복호화 결과를 사용하여 정정이 되고, 2개 이상이면 정정을 할 수 없다. 이 경우, CS는 "1"로 세트된다. "복호화 2"에서는, S=1과 E=2인 복호화(2) 또는 S=0과 E=4인 복호화(3)이 실행되고, CS=1이면 복호화 결과를 사용하여 정정을 할 수 있다. 제10도의 방법에서, 동시에 실행하는 2개의 다른 복호화 회로를 사용하는 복호기 2개를 써야 하지만, 복호화 시간은 단축할 수 있다.

제11도는 제10도의 방법에 따른 에러를 정정하기 위한 에러 정정 장치의 1실시에이다. (100)과 (101)은 14제도에 상세히 도시한 에러 정정 회로를 나타낸 것이다. 회로(100)은 "복호화 1"의 복호화를 실행하고, 회로(101)은 "복호화 2"의 복호화를 실행한다. (102)는 입출력 제어회로, (103)은 래지스터, (104)는 입력버퍼, (105)는 출력버퍼, (106)은 AND회로를, 그리고 (107)은 인버터(inverter)를 나타낸다.

에러 정정 회로(100)과 (101)에 수신 신호가 동시에 가해진다. "복호화 1"과 "복호화 2"의 복호화는 나란히 실행된다. "복호화 1"에서 검출된 에러의 수가 2개 이하이면, 레지스터(103)에 "0"이 로드(load)되고, 에러의 수가 2개 이상이면 레지스터(103)에 "1"이 로드된다. 레지스터(103)의 내용이 "0"이 될때, 에러 정정 회로(100)의 출력 버퍼는 에러 정정 모드로 선택되고, "복호화 1"의 결과에 따라 에러가 정정되거나 정정 불능 플래그가 세트된다.

본 발명의 에러 정정 방법은 또한 제1도에 도시한 것 이외의 다른 이중 부호화된 에러 정정 코드에도 적용할 수 있다. 제12도와 제13도는 본 발명의 에러 정정 방법의 또 다른 실시예를 나타낸 것이다. (11)은 정보 워드, (12)는 제1의 검사워드, (13)은 제2의 검사워드를 나타낸다. 부호화는 즉, 24개의 정보워드 W_i ⁰~W_i23(i=0~29)에 대하여 제1의 검사 워드 W_io~W_i7를 부가하여 C₂블럭(15)를 형성한다. 그 다음 제2의 검사워드 P_0j~W_29j(j=0~23)는 30개의 정보 워드 W_0j~W_29j(j=0~23) 또는 30개의 제1의 검사워드 Q_0k~Q_29k(k=0~7)를 부가하여 C₁블럭(14)를 형성한다. 복호화는, C₁블럭에서 에러의 검출과 정정이 실행된 후 C₂블럭에서 에러의 검출과 정정이 수행된다.

C₁블럭은 코드 길이 32, 2개의 검사 워드, 해밍 거리 3을 갖는 리드 솔로몬 코드를 사용한다. 따라서, 1워드 에러 정정이 가능하고 C₁의 복호화는 제2도에 도시한 것과 동일하게 된다. C₂블럭은 코드 길이 32, 8개의 검사워드 해밍 거리 9를 갖는 리드 솔로몬 코드를 사용한다.

그에 따라 2S + E

8의 범위내에서 오차를 정정할 수가 있다. C₂복호화 과정은 제10도에 도시한 순서도에 따라서 설명한다.

(1) S=4와 E=0으로 복호화를 행하므로 4개의 에러 워드 위치까지를 검출할 수 있다. 검출된 에러의 수가 3개 이하이거나, 에러의 수가 4개이고 잘못 정정할 확률이 낮을 경우에는, 3개나 4개의 에러 워드가 정정된다.

(2) (1)에서 검출된 에러의 수가 5개 이상이고 F₀플래그의 수가 4개인 경우, F₀로 플래그된 4개의 워드가 소실되고, S=2와 E=4인 복호화가 실행된다. 검출된 에러의 수가 2개이면 4개에서 6개까지의 에러 워드가 정정된다.

(3) (1)에서 검출된 에러의 수가 5개 이상이고 F₀플래그의 수가 5개이면, F₀로 플래그된 5개의 워드가 소실되고, 검출된 에러의 수가 1개 이하이면 5개에서 6개까지의 에러 워드가 정정된다.

(4) (1)에서 검출된 에러의 수가 5개 이상이고 F₀플래그의 수가 6개이면, F₀로 플래그된 5개의 워드가 소실되고, S=1과 E=6인 복호화가 실행된다. 검출된 에러의 수가 1개 이하이면 6개 내지 7개의 에러 워드가 정정된다.

(5) (1)에서 검출된 에러의 수가 5개 이상이고 F₀플래그의 수가 7개이면, F₀로 플래그된 6개의 워드가 소실되고 S=1과 E=6인 복호화가 실행된다. 플래그된 워드들 사이에서만 에러가 발생하면, 6개 내지 7개의 에러 워드가 정정된다.

(6) (1)에서 검출된 에러의 수가 5개 이상이고 F₀플래그의 수가 8개이면, F₀로 플래그된 8개의 워드가 소실되고 S=0와 S=8인 복호화가 실행되어 8개의 에러 워드가 정정된다.

(7) (1)~(6)까지의 정정 조건에 해당하지 않는 경우, 에러는 정정불능이다(F=1, F=F₀).

본 발명의 에러 정정 방법을 사용한 에러 정정 장치에 대해서 제14도에 의해 설명한다.

제14도는 에러 정정 장치의 블럭도이다. (17)-(16)는 버스라인, (20)은 신드롬(syndrom)발생기, (21)과 (22)는 ROM, (24)는 논리 연산부, (25), (27) 및 (29)는 RAM, (26)은 계수기, (28)은 비교기, (30)은 점프(jump)조건 판단 회로, (31)은 프로그램 ROM, (32)는 어드레스 계수기를 나타낸다.

본 회로는 3개의 버스라인, 버스라인에 연결된 회로와 프로그램에 의해 회로의 동작을 제어하는 제어회로로 구성된다. 버스라인(17)은 수신된 신호와 에러 패턴(pattern) 등의 데이타를 교환하기 위한 데이타 버스, 버스라인(18)은 데이타 위치등의 데이타를 교환하기 위한 위치(location)버스, 버스라인(19)는 데이타에 부가되는 플래그 데이타를 교환하는 플래그 버스이다. 데이타 입출력 단자(38), 어드레스 입출력 단자(39), 플래그 입출력 단자(40)은 각각의 버스에 연결되어 있다.

신드롬 발생기(20)은 데이타 입출력 단자(38)에 수신된 신호로 신드롬을 발생한다.

논리연산부(24)는 신드롬 발생기에서 나온 신드롬에 의해 에러 위치와 에러 패턴을 결정한다. 연산논리부(24)는 갈로이스(Galois)필드(2⁸)에서 곱셈 나눗셈 그리고 덧셈을 실행한다.

RAM(25)는 신드롬과 연산논리부(24)의 연산결과를 기억한다. (23)은 데이타 버스(17)에 있는 데이타가 0인지 아닌지를 결정하는8입력 OR회로를 표시한다.

ROM(21)과 (22)는 데이타 버스17(i와 α)과 위치 버스(18)의 데이타를 변환한다. 데이타버스상에서 데이타는 벡버로 표시되고, 위치 버스상에서 데이타는 거듭 제곱 형태로 표시된다. 따라서 데이타를 데이타버스(17)과 위치버스(18)사이에서 교환하고자 할때, 데이타는 ROM(21)이나 (22)에 의해 i에서 또는 αⁱ에서 i로 변환을 행할 필요가 있다.

계수기(26)은 1개의 블럭내에 있는 플래그의 수를 계수한다. 제2의 복호화에서, 계수기(26)은 F₀와 F₁의 수를 계수하고, 그 수를 비교기(28)에 의해서 소정의 수와 비교하고 어떤 워드의 정정을 행하는가, 또는 정정을 행하는가 정정을 행하지 않는 정정 불능으로 하는가 등의 판단을 행한다.

RAM(27)은 계수기(26)에 의해 계수된 플래그의 수와 에러의 위치를 기억한다. 비교기(28)은 위에서 설명한 바와 같이 소정의 수와 플래그의 수를 비교하고 복호화 과정에서의 데이타와 상수의 비교로 사용된다.

RAM(29)는 제2의 복호화에 있어서 데이타에 부가되어 있는 제1의 복호화의 결과를 나타내는 플래그 F₀, F₁을 기억한다. RAM(29)에 기억되어 있는 플래그의 상태는 복호화로 결정된 에러 위치에서 플래그의 유무를 검사할때 사용된다.

점프조건 판단회로(30)은 프로그램의 분기(branch)가 OR회로(23)과 비교기(28)에 의해 결정된 결과와 RAM(29)에 기억되어 있는 플래그 상태에 따라서 실행될 것인지를 결정한다.

프로그램ROM(31)은 복호화를 실행하는 상기 회로를 제어하는 프로그램을 기억한다. (33)은 버스라인과 비교기에 입력되는 상수와 RAM 어드레스를 결정하는 명령 신호를 표시한다. (34)는 프로그램 분기의 조건을 결정하는 명령신호를 나타낸다. 점프조건 판단회로(30)에서는 신호(34)의 내용과 OR회로(23), 비교기(28), RAM(29) 등의 상황을 비교하여 분기를 행하는가 아닌가를 결정한다. (35)는 분기하는 경우 분기 어드레스를 결정하기 위한 명령 신호이고, (36)은 버스 라인에 연결되어 있는 버퍼와 레지스터를 제어하기 위한 신호를 표시한다.

계수기(32)는 프로그램 어드레스를 제어한다.

계수기(32)는 주 클럭 입력(41)로부터 공급되는 클럭에 의해 프로그램ROM(31)의 어드레스를 진행하여 프로그램을 실행되도록 한다. 프로그램이 분기될때, 어드레스(35)로의 분기는 분기명령(37)에 의해 계수기(32)에 로드하여 프로그램을 분기시킨다. 입력단자(42)는 프로그램이 시작될때 계수기(32)를 리세트하는 신호를 입력하는 것이다.

에러를 정정하는데에 있어서, 수신신호를 입력하고 신드롬의 발생을 행하여 C₂복호화 과정에서 플래그의 수가 계수되고, 플래그의 상태는RAM(29)에 기억된다. 다음에 복호화는 그 프로그램에 의해 실행되고, 에러 위치 및 에러 패턴은 논리연산부에 의해 결정되며 에러가 있는 데이타는 정정이 된다. C₁복호화와 C₂복호화에서 정정 불능이면, 플래그 입출력(40)으로부터 데이타에 부가된 플래그를 출력한다.

상술한 바와같이, 본 실시예의 에러 정정 장치에 따르면, 회로는 프로그램에 의하여 제어되며, 제15도와 제16도의 실시예에 유사하게 적용될 수 있다. 따라서, 회로의 크기는 작아질 수 있으며, 다른 에러 정정 코드의 복호화는 단지 프로그램을 변경만으로 할 수 있다.

제15도와 제16도는 디지탈 오디오 디스크에 사용된 상호 삽입 리드 솔로몬 코드(영국 특허명세서 GB 2076569A)에 적용된 본 발명의 실시예를 나타낸 것이다. 이 코드는 C₁블럭에 대하여 리드 솔로몬 코드를 사용하는데, 코드 길이는 32, 검사어의 수는 4, 해밍 거리는 5이고, C₂블럭에 대한 리드 솔로몬 코드는 코드 길이가 28, 검사어의 수는 4, 해밍 거리는 5이다.

상호 삽입 리드 솔로몬 코드의 복호 회로는 재생신호 입력단, C₁복호기, 제거회로, C₂복호기와 출력신호단으로 구성한다. 복호화에서, 32워드 재생신호는 C₁복호화된 것이다. C₁복호화한 후에 24-워드 정보와 C₂검사워드는 제거되고, 복호 결과로서 24워드 정보를 만들기 위하여 C₂-복호화된다.

제15도는 C₁복호화의 순서도이다. 상술한 바와같이, C₁코드는 최소거리 5를 갖는 리드 솔로몬 코드를 사용한다. 따라서 1워드 또는 2워드 에러 정정이 될 수 있다.

C₁복호화에서, 3 또는 그 이상의 에러 워드 때문에 에러가 없거나, 1워드 정정,2워드 정정 혹은 정정 불능 에러가 생길 수 있다. 표1에 도시한 3개의 플래그 F₀, F₁, F₂는 4가지 형태를 나타내는 플래그로서 C₁블럭상에 워드로 부가된다. 실제로 C₁플래그 정보는 블럭당 2-비트정보로서 다루어질 수 있다.

[표 1]

C₁플래그

제16도는 C₂복호화의 순서도이다. C₂복호화에서, C₁복호화에 플래그가 부가되던 워드는 소실되며, 소실 정정이 실행된다. 따라서, 에러 정정이 제9도에서 행하여 졌던 것과 같이 2S + 4E

4의 범위내에서 행하여진다.

복호화(1) : 2워드 에러 정정.

복호화(2) : 2워드 소실+1워드 정정.

복호화(3) : 4워드 소실 정정.

에러 정정 능력을 증가시키기 위하여 복호화(2)와 복호화(3)에 의하여 많은 에러를 정정하는 것이 필요하다. 그러나, 소실 정정은 검출 능력이 낮으며, 정정 능력이 선택된 소실에 따라서 감쇄된다. 에러 정정 능력과 검출 능력을 증가시키기 위하여 복호화(2) 또는 복호화(3)이 잘못 정정 확율이 낮을 때에만 영향을 받도록 복호화 알고리즘(algorithm)이 사용될 수 있다.

C₂복호화를 위한 특수 알고리즘은 제16도를 참고로하여 설명한다.

(1). S=2이고 E=0인 복호화가 첫번째로 실행된다.

그래서, 임의 위치에서 2워드 에러까지 검출될 수 있다. 검출된 에러의 수가 2 이하일 때, 블럭에서 플래그 수와 에러위치에 부가된 플래그의 존재 유무의 판단에 따라 잘못 정정의 확율이 낯을 때 정정이 된다. 잘못 정정의 확율이 높으면, 에러는 정정할 수 없다.

(2). (1)에서 검출된 에러의 수가 3이상이고 F₁플래그의 수가 3개이라면, 2 또는 3개의 F₀로 플래그로된 워드들이 소실되고 S=1이고 E=2인 복호화가 실행된다.

단지 플래그된 워드들에서 에러가 검출된다면, 복호화 결과를 사용하여 정정이 된다.

(3). (1)에서 검출된 에러의 수가 3개이상이고, F₁플래그의 수가 3개 이상이면 F₂플래그의 수가 2 또는 3개라면, 2개의 F₂로 플래그된 워드가 소실되고, S=1이고 E=2인 복호화가 실행된다. 만일 F₁으로 플래그된 워드에서만 에러가 검출된다면, 복호화 결과를 사용하여 정정이 된다.

(4). (1)에서 검출된 에러의 수가 3개 이상이고 정정조건(2)나 (3)이 맞지 않는다면, 에러는 정정 불능이다.

제17도는 제15도와 제16도에 도시한 본 발명의 실시예와 종래의 장치에서의 에러 정정 능력과 에러 검출 능력의 비교를 도시한 것이다. 제17도에서, 가로축은 워드 에러비율이고, 세로축은 에러 정정후의 에러 확율을 나타낸다.

곡선Ⅰ는 사코(Sako) 등에 의하여 미국 특허 443785에서 공개된 종래의 장치에서의 교정 능력과 검출 능력을 나타낸다. 이 정정 방법에서는, 단지 하나의 플래그(포인터(pointer)코드 신호)가 제1의 C₁복호화에서의 각 워드 신호에 부가되고, 2개의 에러가 다음의 C₂복호화에서 정정될 수 있다. 곡선 Ⅱ는 위와 관련된 출원에서 공개된 정정 방법에 의한 정정 능력과 검출 능력을 나타낸다. 이 방법에서, C₂복호화는 3개의 복호화, 즉 에러 정정, 에러 및 소실 정정과 소실 정정에 의한 정정 과정을 사용한다. 곡선Ⅲ은 본 발명의 실시예에 대한 정정 능력과 검출 능력을 나타낸다. 위와 관련된 출원의 정정 과정은 정정 능력을 향상시키기 위하여 더욱 개선이 된다.

제17도의 특성 곡선에서, 검출 능력은 실제적으로 Ⅰ-Ⅲ의 각 경우와 동일하다. 반면에, 워드 에러 비율이 10^-3에서의 특성 곡선 Ⅱ의 정정 능력은 특성 곡선 Ⅰ의 정정 능력보다 2차수가 높으며, 특성 곡선 Ⅲ의 정정 능력은 특성 곡선 Ⅰ의 능력보다 4차수가 높다.

Claims

(정정) 제1의 배열에 배열된 여러개의 정보 워드와 상기 정보 워드에 대하여 해밍 거리 d₁를 갖는 코드에 의해 생성한 여러개의 제1의 검사 워드를 포함하는 제1의 코드블럭과, 제2의 배열에 배열된 여러개의 정보 워드, 각각 다른 상기 제1의 블럭에 속하는 여러개의 정보 워드와 제1의 검사 워드를 갖는 여러개의 제1의 검사워드와 상기 여러개의 정보워드와 상기 여러개의 제1의 검사워드에 대하여 해밍 거리 d₂를 갖는 코드에 의해 생성된 여러개의 제2의 검사 워드를 포함하는제2의 코드 블럭을 갖는 복호화 코드 워드에 있어서, (a). 제1의 복호화 단ㅇ서, 적어도 상기 제2의 코드 블럭에 대한 에러를 검출하고 적어도 복호화 상태를 나타내는 플래그의 한 형태를 부가하는 공정과, (b). 제2의 복호화 단에서, 상기 제1의 코드 블럭에 대한 에러를 검출하고 2S₂+E
d₁-1을 만족하는 S₂워드 에러와 E워드 소실을 정정하는 것에서, S₂는 위치를 모르는 워드 에러의 수이고 E는 소실된 수이며, 여러개의 S₂와 E의 조합에 대하여 에러의 위치와 패턴을 결정하며, 여러개의 결정된 에러의 위치와 에러 패턴에 따라 정정의 고능력과 잘못 정정의 저확률을 갖는 S₂와 E의 조합을 결정하고, S₂와 E의 선택된 조합의 에러 위치와 에러 패턴에 따라 제2의 복호화 단에서 워드에러를 정정하는 공정을 포함하는 에러 정정방법.
(정정) 특허청구의 범위 제1항에 있어서, 적어도 에러를 검출하는 공정은, 2S₁
d₂-1에서, S₁워드에 대한 에러 검출과 에러 정정을 포함하는 에러 정정 방법.
(정정) 특허청구의 범위 제1항에 있어서, 상기 제2의 복호화 단에서, 에러 위치와 에러 패턴들이 2S₂+E
d₁-1을 만족하는 S₂와 E의 여러개의 조합에 대하여 병렬로 또는 순차적으로 결정하는 에러 정정 방법.
(정정) 특허청구의 범위 제1항에 있어서, 상기 코드 워드는 이중 부호화된 리드 솔로몬 코드인 에러 정정 방법.
(정정) 특허청구의 범위 제1항에 있어서, 상기 코드 워드는 이중 부호화된 주기적 중복 검사 코드인 에러 정정 방법.
(정정) 특허청구의 범위 제1항에 있어서, 단일 블럭에서 플래그의 수와 복호화 결과에 의하여 결정된 잘못 정정의 최소 확률을 갖는 S₂와 E으이 조합의 복호 결과가 에러 위치와 에러 패턴에 대한 여러개의 복호 결과로부터 선택되고, 워드 에러는 선택된 복호 결과에 따라 정정되는 에러 정정 방법.
(정정) 특허청구의 범위 제1항에 따른 에러 정정 방법에 있어서, 입력 신호로부터 신드롬을 발생하기 위한 신드롬 발생기, 갈로이스 필드에서 덧셈, 나눗셈과 곱셈을 실행하기 위한 논리 연산부, 갈로이스 영역의 임의 차원 αi에서 αi를 i 또는 i를 αi로 변환하기 위한 변환회로, 입력 워드에 부가되는 여러개의 형태의 플래그를 계수하기 위한 계수기, 상기 신드롬 발생기에 의하여 발생된 신드롬, 상기 논리연산부의 결과, 상기 변환회로의 변환결과, 상기 계수기에 의해 계수되는 플래그된 입력 워드의 플래그의 수와 상기 입력 신호에 부가된 플래그들을 기억하기 위한 기억 회로. 논리 연산회로, 상기 변환회로, 상기 기억회로를 제어하여 에러 정정 동작을 행하는 프로그램을 저장하기 위한 프로그램 기억회로와, 상기 프로그램과 플래그의 상태에 따라 상기 프로그램 기억회로의 어드레스를 제어하기 위한 제어회로를 포함하는 에러 정정 장치.