李晩榮 서울대학교 工學士 (B. S. E. E.) 미국 콜로라도 대학교工學碩士 ( M. S.E . E.) 工 學博 士 (Ph . D. ) 미국 버지니아 주립대학교 공대교수 미국 캘리포니아 I 大 JPL 연구원 국방과학연구소 부소장 한국전자통신 사장 삼성반도체통신 사장 한양대학교 부총장 현재 한양대학교 명예교수 저서 Error Correcti ng Codin g The or y, McGraw- Hi ll, New York, 198 9.

BCH 부호와 Reed-Solomon 부호

,.¢. ,. 广．혼 \—\( .lm\ i.'\ 떠. ' ‘ g[—Eg )- ,`i건七 Fl. ` ` .-. ;. \. 5‘·. .. r:. ~b ..r 一} . - . f一t - ?.,f'I .`,. '·.3f1. `,··.'I1 ’ .

BCH 부호와 Reed- So lomon 부호

책 머리에 디지탈 통신 시스템의 도입이 거 의 모 든 동신망 에 확산됨 에 따라 통 신 채널에서 발생하는 오류 를 효율 적 으로 제 어 하기 위한 오 류정정 아 론은 이 제 더 이상 부호 이론가 둘 의 전 유 물 이 아니 라 동신 시스템 설계 시 반 드 시 고려되어야 할 매우 중요한 기 술분 야로 정착되 었다. 또한 V LSI 기 법 의 발전, 새로운 서비스에 대한 사용 자 의 일정 수 준 이상의 전송 품질 의 요구, 광대역 전송기법 및 전 송매 체 의 개발 등은 오 류정 정 부호 의 디지 탈 시스템 통신에의 도입을 가속화시 킬 것 이다 . 따라서 이 책 에서 는 통 신 망 에서 발생하는 오류를 효율적으로 제 어하기 위해 통 신 시 스템 에 현재 널 리 이용되고 있거나 도입될 예정인 alge braic 부호 (BCH , RS 부호 ) 에 대 해 1980 년 이후 소개된 복호기법을 자세히 기술하며, al g ebra i c 부호 의 복호기 설계시 필연적으로 소요되는 승산기 (multip li c a ti on circ uit ), 제산 기 (div i s i o n circ uit ) , 가산기 (addit ion cir c uit ) , 역 산기 (inv ersio n cir c uit ) 등 의 연산기 기본구조 및 설계이론을 제시한다. 이 책의 1 장에서는 오류정정이론의 통신망에 있어서의 역할, 역사, 오 류정정부호의 종류, 발전단계, 그리고 기술 발전추이 등을 개괄적으로 고찰하고, 2 장에서는 al g ebra ic부호의 부호기 및 복호기 설계시 소요되는 승산기, 제산기, 가산기, 역산기 그리고 이중근 및 자승기회로 (s q uare root and squ arin g circ uit s ) 등의 여 러 연산기 에 대 해 Galois 체 상에 서 의 표준기 지 (sta n dard basis ) , 정 규기 지 (normal basis ) , 쌍대 기 지 (dual basis ) 그리 고 지 수표현 (exp o nenti al rep re senta t i on ) 등을 이 용하여 기 본 이 론을 분석하고 관련 하드웨어 구조를 제시한다. 또한 이 를 실제로 부호기 및

복호기 설계시 널리 이용될 수 있도록 관련 회로를 설계한다• 3 장에서는 다수개의 오류 를 정정할 수 있는 BCH 부호에 대한 여러 복 호기법웅 소 개한다. BCH 부호의 복호시 가장 중요한 복호단계는 오류위 치 다항식의 계수를 구하는 것이다. 이 를 위하여 지금까지 발표된 I3crlekam p의 반복 알고리즘, Pe t erson 의 직접 복호 알고리즘, 오류위치 다항식의 근윤 쉽게 결정할 수 있는 Chie n 알고리즘, 그리고 오류위치 다항식 의 근옹 병 련로 계 산할 수 있는 ROM (Read Only Memory ) 을 이 용 한 복호 안고 리 즘 등 여러 복호기법의 기본 이론을 분석하고 관련 알고 리 즘을 이용 했운 때의 복호 기 구조를 제시한다. 이 책 의 4 장 에서 는 비 2 원 BCH 부호의 일종이고 십벌 단위로 오류정정 이 가능하여 현대의 유선 및 무선 통신 시스템에 널리 이용되고 있는 Reed-Solomon 부호의 복호 기 법을 소개 한다. 여 기 에서 소개한 복호기 법 은 Pe t erson-Gorens t e i n-Z i eler 의 복호 알고리 즘, Berlekam p의 반복 복 호 알고리즘 , Fourie r 변환 영역에서의 복호 알고리즘, VLSI 의 파이프 라인 구조에 적합한 변형된 Eucl i d 의 알고리즘을 이용한 복호 알고리즘, 그리고 콤퓨 터의 메모리 시스템에 이용 가능한 아중오류정정_삼중오류겁 출 RS 부호에 대한 간단한 복호 알고리즘 등의 기본 이론을 분석하고 관 련 알고리즘 실현시의 복호기 구조를 제시한다. 이 책에서는 디지탈 통신 시스템, 암호 통신 시스템, 콤퓨터의 메모리 시스템, 광 통신 시스템, 비데오 통신 시스템 그리고 CD(Comp a ct Dis k ) , DAT (Digital Audio Tape ) 등의 가전제 품 분야를 포함한 거 의 모 든 통신 시스템에 널리 이용될 수 있는 alge braic 오류정정부호의 부호화 및 복호기법을 자세히 분석하고 제시하였다. 이 책은 대학원 석 • 박사 과정의 학생, 콤퓨터 및 통신 시스템 분야의 경력 과학 기술자 그리고 관련 분야의 연구원들을 위하여 쓰여졌으며 오 류정정부호의 부호기 및 복호기 설계시 널리 이용될 수 있을 것이다. 1990 년 3 월 이만영

차례 / BCH 부호와 Reed-Solomon 부호

3-6 Chien의 직접복호법 • 75

제 1 장 개요 동 신 시 스 템에서 통신로 를 통한 디지탈 데이터 전송은 콤퓨터 기억장 치 에 서 의 데이터 저장과 많은 유사점을 갖고 있다. 통신로나 데이터 저 장 시스 템은 여러 형태의 잡음, 왜곡, 그리고 간섭 등에 영향을 받아 전 송중 발 생하는 오류로 인해 일반적으로 수신 데이터는 송신 데이터와 서 로 다 릅 수 있다. 따라서 통신 시스템이나 데이터 저장 시스템에서 처리 되 는 광대한 양의 데이터에 대한 오류제어의 필요성은 두말할 나위도 없 다. 오류정정부호나 정정알고리즘은 이와 같은 필요성을 만족시키기 위 해 발전되어 왔으며 현대의 많은 통신 시스템 또는 데이터 저장 시스템 에 응용되고 있다. 더구나 반도체 집적화 기법의 급속한 발전은 지금까 지 제안된 부호 및 복호알고리즘을 이용하여 오류정정용 부호기와 복호 기를 하나의 IC( Int e g rat e d C i rcu it)로 설계하고 제작할 수 있게 하였다. 오류정정부호이론은 고유한 역사와 연산 시스템을 갖는 특별한 학문 분야로서 데이터 전송시나 저장시에 발생되는 오류로부터 디지탈 데이터 를 보호하기 위해서 제안되고 발전되어 왔다. 지금까지 수많은 오류정정 알고리즘이 제안되어 왔고 실제 시스템에 적용되어 옹용되고 있으므로 이제 오류정정이론은 통신 시스템에 없어서는 안될 분야로 정착되었다.

1-1 디지탈 부호화 시스템의 모델 부호화된 통신 시스템은 그림 1.1에서 나타낸 바와 같 이 데이터 소스 (source), 채널부호기 그리고 변조기, 통신채널 또는 저장장치` 복소기 등으로 구성된 디지탈 통신채널, 채널복호기 및 데이터 싱크 (s i nk) 로 크 게 구성되어 있다. 그립 1.1의 각 블럭 사이의 정보교환은 오류제어옵 위 해 디지탈 형태로 이루어져야 한다• 정보원과 소스부호기로 구성되어 있는 데이터 소스에서는 정보원으로 부터의 신호를 2 원 (b i na ry)형태의 디지탈 데이터로 변환한다. 죽 소스부 호기는 정보원의 출력 신호 를 2 원정보계열 d 로 변환하는 역할을 수행한 다. 한편, 정보원의 출력은 연속적인 파형이거나 이산계열의 심볼 형태 이다. 아날로그 출력인 경우 소스부호기는 PCM(Pulse Code Modulati on )

i「- - --------- --- ----- --- ---、 ,---- ---- -- --- --~ --7

그림 1.1 디지탈 부호화 시스템의 블럭도

과 같은 아 날로그-디 지 탈 변 환 (AD : Analog to Dig ital Conversio n ) 기 능을 수행한다 . 채널부호기는 정보 계열 d 를 부호계열 c 로 변환하는 기능을 갖는다. 일반적으로 부호어는 오류정정을 위한 패리티 겁사 심볼과 정보계열로 구성되야 정보계열 d 의 길 이보다 크다는 것을 쉽게 알 수 있다. 부호어 에서 각각의 심봉은 2 원 비트 또는 2 원 비트의 군으로 표현될 수 있다. 채 \ ! - 't-r』 －호 기로부터 부호어 각각의 심볼은 변조기에 입력되어 통신채널 에 적합한 형 태의 신호로 변환된다. 따라서, 변조기는 심볼을 전송하기 위해 주 기 T 동안 부호어 각각의 심볼을 적당한 형태의 신호로 변환하 는 기 능을 수행하고 있다. 변조기법의 대표적인 예는 BPSK(Bi na 11· Phase Sh if t Ke y in g ) 또는 FSK (Freq u ency Shif t Key in g ) 변조 방식 등이 있다. 통신 시 스템 의 경우 채널은 유선 또는 우선의 통신채널이고, 데이 터 저장 시 스 템의 경우 채널은 데이터 저장 매개체가 될 것이다. 변조기 의 출력 파형은 채널을 통과하는 동안 여러 형태의 잡음에 의해 왜곡 또 는 변조된다. 일반적으로 디지 탈 통신채널은 변조기, 통신채널, 복조기 로 구성된다 . 통산 시스템의 경우 디지탈 통신채널은 · 전화선, 마이크로 파 링크, 고주파 무선 링크, 텔리메터리 링크, 위성 링크 등을 들 수 있 고 , 데이터 저장 시스템의 경우 저장 매개체는 코아 메모리, 자기 테이 프 , 드럼 , 디스크 파일과 광메고리 유닛 등을 들 수 있다. 위에 나열한 각각의 통신채널은 여러 형태의 잡음으로 인해 간섭받고 있다. 따라서 심볼 파형에는 산발 또는 연집 형태의 잡음이 부과된다. 이와 같은 형태의 잡음은 일반적으로 부가 Gauss i an 형태로 모델화된다. 또한 통신채널은 그 특성에 따라 오류의 형태가 각 심볼에 서로 무관하 게 발생 하는 무기 억 통신 채 널 (memoryl e ss channel) 과 오류가 각 심 볼에 서로 영향을 미치는 기억 동신채널 (memo ry channel) 로 구분된다. 무기억 통신채널로는 가시 전송 링크, 인공위성 링크 그리고 우주통신 링크 등 을 들 수 있고 기억 통신채널로는 다경로 신호 전송으로 인해 신호에 페 이 딩 (fad in g ) 현상이 발생하는 무선통신 링크, 스위 치 잡음 또는 선로간의 간섭현상으로 인해 영향받는 전화회선 그리고 디스크의 표면손상, 또는 표면상의 먼지 등으로 인해 발생되는 자기 기억장치 등을 들 수 있다. 물론 산발 또는 연집 형태의 오류가 복합적으로 발생되는 채널 또한 존

재한다. 채널을 동과한 수신 신호 는 먼저 복 조기 에 의해 처리된 후 다음 채널 복호기에 의해 원래의 정보계열로 복호된다. 복조기는 주기 T 동안 어떤 심볼이 실 제로 전송되었는가 를 결정한다 . 복조기의 출력 신호를 수신 부호어 r 이라고 한다. 이 수신 부호어 r 은 일반적으로 전송 오류로 인해 송신 부호어와 서로 다르고 복조기의 출력 은 일반적으로 2 원 디지탈 신호 형태 를 갖는다. 복조기는 출력 수신 부 호어 r 이 송신 부호어 c 로 가장 찰 추정될 수 있도 록 선 계되어 있지만 채널에서 발생된 잡음으로 인해 잘못 추정할 경우도 있다. 위와 간은 겅 우의 확률은 신호대 잡음비, 과도한 필터링, 또는 비선 형 목 성으로 인한 신호 왜곡, 그리고 검출 방법 등에 따라 달라질 수 없다. 채널복호기는 수신 부호어 r 을 정보어 d 로 변환하는 기능을 수행한 다. 채널복호기는 과도한 오류로 인해 수신 부호 어에 오류 를 부가하는 경우가 발생될 수 있으므로 복호 오류확 률 이 최소화될 수 있도 록 설계되 어야 한다. 또한, 채널복호기는 수신 부호어에서의 오류 를 정정하기 위 해 수신 부호어로부터의 오중을 이용하여 복호한 후 , 정보어 d 를 결정한다 . 소스복호기는 추정된 정보어 d 로부터 원래 형태의 신호 몰 재생하여, 이를 사용자에 전달하는 기능을 수행한다. 이 책에서는 . BCH 부호 및 RS 부호의 부호기와 복호기에 대해 분석하 고, 설계하며, 이를 장치화하는 기법을 제시한다. 소스부호기나 복호기 에서 수행되는 데이터 압축기법은 취급되지 않으며 정보와 소스부호기는 출력이 d 인 디지탈 데이터 소스로 합쳐지며 변조기, 통신채널(또 는 저장 매개체) 그리고 복조기는 입력이 C 이고 출력이 r 인 부호채널로 합쳐지 고 소스복호기와 사용자는 디지탈 데이터 싱크로 합쳐진다. 따라서 이 책에서는 채널부호기와 채널복호기를 단순히 부호기 또는 복호기로 지칭 하였다. 1-2 오류정정부호의 체계 오류정정부호는 크게 블럭부호 (block code) 와 길쌈부호 (convolu ti onal

cod e ) 로 나 누 어져 발전 되어 왔다. 불럭부호의 모 든 데이터 는 〈 1 〉 과 〈 O 〉 의 2 원계열로 표현된다. 블럭부호의 부호기 는 정보 계 열 이 k 비 트로 구성된 정보어 를 n 바트로 구성된 부호어로 변환하 는 기능을 수 행한다. 따라서 각각의 정보어는 k 차 벡터 형태로 표 현된 수 있 으 며 , 이 는 d= (do, d,, …, dk - 1) 로 표현된다. 따라서 정보어에 는 전체 2k 가지 의 서로 다 른 정보계열 을 가질 수 있다. 부호기는 이 k 비 트 의 정보 어 d 웅 n 차 부호 어 c 로 변환한다• 한편 c 는 C = (co, C1, •••. C11 - 1) 로 표현되고 부호어 각각의 요소는 q개 의 요 소강 갖 는 알파벳으 로 부 터 선 택된다. q = 2 인 경우 2 원불럭부호, q > 2 인 경우 비 2 원 문 러부호 라 한 다. 따라서 2 원 불 럭부호에는 모두 2n 개의 부호 어 가 존 재 하지만 그중 간 개 를 뽑아서 2 원블럭부호를 형성한다. 따라 서 k 정보계열은 부호 기에 의해 길이가 n 인 2 원 부호어로 사상 (ma ppi n g) 된 다 . 한편 (11, k) 블럭부호는 길 이가 n 인 간 개의 부호어로 구성되어 있다. 여가 서 부호화율 R 은 R = k /n 이다. 따라서 n 비트의 부호어 c 는 k 비트 의 정보 어 d 에만 영향 을 받으므로 부호기는 조합논리회로 (comb i na ti onal log ic c i r c u it) 로 구현될 수 있다. 블럭부호의 경우 n-k 비트의 용장 (r e dund a nc y) 을 k 비트의 정보어에 첨가함으로써 부호어를 형성하므로, 이 용 장 비 트 를 이용하여 채널에서 발생하는 오류를 정정한다. 따라서 용 장 n - k 비트 를 패리티 검사 비트라 한다. 오 류 정정부호에 있어서 또 하나의 중요한 변수는 부호어의 중 (we ig h t) 으 로써 이는 각 부호어에서 영이 아닌 성분의 갯수를 나타낸다. 일반적 으로 각각의 부호어는 자신의 중을 가지고 있다. 따라서 부호의 중의 집 합은 부호의 중 분포를 형성한다. 두 부호어 사이의 거리는 대응되는 성 분 중 서로 다른 성분 쌍의 갯수로 정의된다. 이를 Hamm i n g거리라 하 며 간부호어에 대한 Hamm i n g거리의 집합 중 가장 작은 것이 그 부호의 최소거리 dm1n 이라 정의한다. 최소거리가 dm1n 인 (12, k) 선형부호는 t =L(dm i n-1) ／미개 이하의 오류 룰 정정할 수 있다. 여기서 Lx 」 는 x 이하의 최대정수이다. 한편, 선형블럭부호의 복호시 Group , Ri ng , Galo i s 체와 같은 추상 대수 학 분야가 이용되며 이 책의 2 장에서는 Galo i s 체를 이용한 연산을 수행

했을 때 쉽게 장치화하는 기법들에 대해 기술하였다 한편, 오류정정부호의 또 다른 분야인 길쌈부호는 m 단의 치환레지스 터와 n 개의 modulo ― 2 가산기, 그리고 다중화기 (multip l exer) 등으로 구 성된 부호기에 의해 생성된다. 일반적으로 최우길쌈부호의 복호기법은 Vi ter bi 알고 리 즘 을 이 용 한 최 우 복 호 법 (maxim um-lik l ih o od decodin g ) , Fano 혹은 스택 (sta c k) 알고리즘을 이용한 축차복호법 (seq u enti al decod- ing ) 그리고 대수학적 특성을 이용한 임계 또는 다수결복호기법 동이 있 다. 1967 년 제안된 Vi ter bi 알고리즘은 길쌈부호의 도형적 구조에서 최소 경로(p a t h) 를 찾는 알고리즘으로 최우복호기법이라 하며, 비교적 구속장 (constr a in t len gt h) 의 길이가 짧은 길쌈부호의 복호시 능 률 적인 복호법으 로 평가되고 있다. 그러나 구속장의 길이가 큰 경우는 복호기의 복잡도 (com p lex ity)가 기하급수적으로 증가한다는 단점이 있다. 1961 년 Wozencra ft에 의해 제안된 축차복호법은 그후 25 년여 동안 계 속해서 연구되어 왔다. 1963 년 Fano 는 Fano 알고리즘이라 불리는 새로운 축차복호법을 제안했고 1966 년과 1969 년에 Z ig an gi rov 와 J e li nek 가 각각 제안한 ZJ 또는 스택 알고리즘도 축차복호법의 한 부류이다. 축차복호 법은 비교적 구속장이 큰 길쌈부호의 복호시 널리 이용되고 있으나, 한 프레임에서 발생하는 잡음이 많은 경우 계산량이 급격히 증가하여 복호 시간이 상한치를 초과하여 데이터가 유실되는 단점이 있다. 1963 년 Masse y는 대수학적 특성을 이용하여 길쌈부호에도 적용될 수 있는 다수결 또는 임 계 치 복호법 (thr eshold decodin g algo rit hm ) 을 제 안하였 는데 이 기법의 성능은 축차 또는 최우복호법에 비해 약간 떨어지나 장 치화가 간단하다는 장점이 있다• 1-3 부호이론의 역사 1948 년 Claud Shannonol 발표한 통신이론에 관한 논문은 비록 통신채 널상에서 발생한 오류를 정정하기 위한 구체적인 부호 선정방법에 대해

서는 제시하지 못했지만 그의 논문이 발단이 되어 이후 많은 부호학자들 에 의해 부호의 성질, 부호 구성법, 부호기 및 복호기 설계, 효율적인 복호알고리즘 등에 관한 다수의 연구가 발표되었다. 1950 년대에서의 부호이론은 대수학적 특칭을 이용한 불러부호에 초접 이 맞춰져 연구되어졌으며, 이중 대표적인 부호가 단일오류정정이 가능 한 Hamm i n g부호이 다. 1960 년대의 부호이론은 복호 후 오류확률을 현저히 줄일 수 있는 길이 가 긴 부호 을 발전하고 관련 부호의 부호알고리즘을 개발하는 데 초점이 맞추어졌다. 이 중의 대표적인 경우가 Bose, Chaudhuri( 1 960) 그리고 Hoc q uen g hem(1959) 에 의해 각각 재안된 다중오류정정이 가능한 BCH 부호의 발견이다. 다수의 오류정정에 효율적인 BCH 부호에 대해 이후 Pe t erson(1960) 은 보다 실질적인 복호알고리즘을 제안하였고 Gorenste i n 과 Zie r ler ( 1961 ) 가 이 를 발전시 켰으며 Berlekamp , Massey, Chie n , Forney 등에 의해 이를 확대 적용시켰다. 또 한 가지 중요한 발전은 Reed 와 Solomon(1960) 이 제안한 연집 형태의 오류를 정정 가능케 한 비 2 원 BCH 부호의 일종인 RS 부호의 발견이다. 이 RS 부호는 산발 또는 연집 형태의 오류를 모두 정정할 수 있으며 실제 널리 이용되고 있는 매 우 중요한 부호로서 이후 수많은 부호이론가에 의해 연구되어 있고 지금 까지 계속 연구되고 있다. Me ggit에 의해 제안된 순회부호의 복호법인 오류포착복호법 (error-tr a p ping decodin g ) 역 시 Kasami , Mi tch el, Rudolph 등에 의해 발전되었는데, 이 복호법은 길고 부호화율이 큰 부호의 경우 비효율적안 단점이 있다. 한편 Masse y (1963) 는 순회부호 또는 길쌈부호 에 대한 다수결논리복호법을 제안하였다. 1955 년 E li as 에 의해 제안된 길쌈부호에 대해, 1961 년 Wozencra ft가 축차복호법을, 1963 년 Fano 가 축차복호법을 발전시킨 알고리즘을, · Zig a ng iro v(1966), J e li nek(1969) 는 각각 스택알고리즘을 제안하였다. 그 리고 1967 년 V it erb i는 최우복호법인 Vi ter bi 알고리즘을 제안하였고 이 후 Om ti ra(1969) 와 Fome y (l972-1974) 가 구속장이 작은 길쌈부호의 최우 복호법이 Vi ter bi 알고리즘을 이용한 복호법임을 증명하였다. 한편 1963 년 Masse y는 임 계복호법을 제 안하였다. 또한 Berlekamp ( 1964), Prep a rata ( l964), Massey (1 965), lwadare(196s), Kohlenberg 와 Forney

(1968), Gallag e r(1968), Tong ( 1910) 그리고 Fergu s on(191 1 ) 등이 길쌈부 호를 이용하여 연집 특성의 오류 를 정정할 수 있는 복호법 등을 제안하 고 발전시켰다. 1970 년대의 부호이론은 1960 년대에 제안된 복호알고리즘을 개선하고 이를 실제 통신 시스템 및 데이터 저장 시스템에 응용하는 방향으 로 방 전되어 왔다. 그 대표적인 경우는 Forne y (1912-1974) 가 Vi ter bi 알고리즘 울 이용하여 복호기를 설계한 것이고, 이 복호법은 우주봉신 멋 위성동 신 분야의 디지탈 통신 시스템에 널리 적용되고 있다. 한편 실제적으로 통신 시스템에 널리 이용되어 온 RS 부호 에 대 한 복 호알고리즘에 대한 연구는 Murakami , Reed, Welch(1977) 에 의해 1977 년 제안된 변환 복호알고리즘을 들 수 있으며, 이는 오류추정다항식 을 구하 지 않고 오류를 정정하는 복호알고리즘이다. 또한 RS 부호의 복호시 중 요한 복호과정 중에 하나인 오류위치다항식을 구하기 위해 종전의 Berlekamp -M assey 알고리즘보다 훨씬 개념적으로 간단한 Euclid 알고리 즘을 이용한 새로운 복호법이 Mandelbaum(1977) 에 의해 제안되었다. 1980 년대에 접어들면서 부호이론은 더 이상 일부 부호이론가 들 의 전유 물로 남아 있지 않게 되었으며 이 부호 및 복호알고리즘 을 이용한 새 로 운 복호법들이 계속 제안되었으며, 1960 년대와 1970 년대에 제안된 알고 리즘을 효율적으로 이용하여 실제 통산 시스템에 적용 가능케 하기 위한 연구가 현재까지 계속 진행되고 있다. 이 책에서는 1980 년도에 수행된 BCH 부호 및 RS 부호의 새로운 복호 알고리즘과 관련 장치화이론, 그리 고 이둘 부호에 중요한 소자로서 기능을 발휘하는 연산기의 구조 및 관 련 이론에 대해 집중척으로 분석하고 부호기 및 복호기의 구조를 제안하 였다. 1- 4 부호의 응용 오류정정부호에 대한 연구는 주로 통신 시스템에서 발생되는 문제를 해결하기 위해 추전되었다. 예를 들어 대부분의 경우 통신 시스템은 송

신 출력 에 제한이 있으며, 이 경우를 위해 오류정정부호 를 이용한 통신 시스템은 미약한 수신 신호가 수신단에 도착하였을 때에도 신뢰성 있는 통신 이 가능하기 때 문 에 송신 출력 제한을 효율적으로 극복할 수 있다. 오류정정부호는 콥퓨터 메모리 시 스 템, 마그네틱 테이프, 또는 디스크 저장 시 스 템 등 에 이용되 고 있으며 또한 디지탈 논리회로의 고장 진단을 위해서도 응용되고 있다. 선-러부호 는 주로 통신 시스템뿐만 아니라 콤퓨터 메모리 시스템에서 밍생하 는 오류 · 강 정정하는 데 이용되고 있으며, 길쌈부호는 산발오류 특 성이 강한 우 주 및 위성동신 분야에 응용되고, 특 히 RS 부호와 쇄상시켜 산발오 류 뿐만 아니라 연집오류 를 모두 정정 가능한 지상 무선통신 분야, 유선통신 분야, 광 파이 버 링크 그리고 암호통신 분야에 널리 이용되고 있다. 단일오류정정- 이 중오류검출 Hammi ng 부호는 IBM 시스템 360 과 370 의 자기 메모리에서 발생하는 오류 를 정정하기 위해 이용되고 있다. 반도체 메모리는 일반적 으 로 코아 메모리보다 속도는 빠르나 신뢰성이 떨어지므 로 이 들 시스템 에 오류정정부호의 도입이 요구되었다. 이들 분야에 널리 이용되고 있는 부호는 연집오류의 정정이 가능한 F i re 부호나 연집뿐만 아니라 산발오류를 모두 정정 가능한 RS 부호를 둘 수 있다. 왜냐하면 자기 데이 프 나 디스크에서 발생되는 오류 형태는 자기 네이프나 디스크 표면 의 손상 또는 먼지 등으로 인해 발생되는 연집오류이기 때문이다. 한편 , 소스부호 화 기술의 발달로 인해 비데오 신호를 부호화하여 얻은 비데오 데이터 를 유선 또는 무선통신 채널을 통해 전송할 때 발생되는 오류 를 정정하기 위해 CCITT 또는 관련 표준화 기구에서 BCH 부호 또 는 RS 부호의 도입이 적극 검토되고 있다. 그리고 CD(Comp a ct Dis k ), DAT (Digital Audio Tape ) 그리 고 TV 문자 다중방송 분야에 도 BCH 부호 또는 RS 부호가 도입되어 채널에서 발생되는 오류를 정정하고 있다. 길쌈부호는 많은 우주 또는 위성통신 시스템에 이용되고 있다. 예를 들어 화성, 목성, 토성을 람사하기 위한 Vo y a g er 호 (1977) 에 (2,1,6) 길쌈 부호를 이용했으며 길쌈부호는 주로 RS 부호와 쇄상시켜 V it erb i복호법 울 이용하여 설계된 복호알고리즘을 이용하여 위성통신 분야에 널리 이 용되고 있다. 한편, 위성통신 채널을 이용하여 음성 데이터를 전송하기

위 한 SCPC (Sin g le Channel Per Carrie r ) 시 스템 에 임 계 복호법 을 이 용한 (8,7,4 7 ) 자기직교길쌈부호가 적용되고 있다. NASA 의 태양계 추적 우주 선 Pio n eer 9 은 1968 년 발사된 오류정 정 부호를 이 용한 최 초의 우주선 이 다. 여기서 이용된 부호는 (2,1,24) 길쌈부호로써 축차복호 알고리즘을 기 초로 한 복호기법을 사용하였다. 이와 같은 응용 영역을 갖는 오류정정부호는 앞으로 시분할 다중 시 스 템, 패킷 스위칭 시스템, 디지탈 레이다 신호처리 시스템, 이동 동 신 시 스템, 스프레드 스펙트럼 시스템, 그리고 암호 시스템 등 대부분의 동신 시스템과 콤퓨터의 기억장치, CD 그리고 DAT 분야에도 널리 이용될 것 이다. 따라서 오류정정부호이론은 통신채널에서 발생되는 오류 를 정정하 기 위한 매우 중요한 분야가 될 것이다.

제 2 장 유한체 연산 유한체 (fini t e fiel d) 의 연산은 오류정 정 부호 (error-correcti ng codes) , 스 위 칭 이 론 (swi tch in g the ory ) 및 암호이 론 (cry ptog rap h y) 등 많은 분야에 적 용되고 있다. 예를 들어 오류정정부호인 BCH 부호나 Reed-Solomon 부 호의 복호과정에서는 GF(2 기상의 연산을 이용하여 관련 알고리즘을 실 현한다. 그러므로 유한체 연산의 간소화는 전체 복호회로의 복잡성에 매 우 큰 영향을 미친다. 이 장에서는 유한체 중에서 실질적으로 부호기와 복호기에 널리 적용되고 있는 GF(2 이상에서의 연산에 관하여 고찰해 보 기로한다. 원소의 개수가 2m 개 인 유한체 GF(2m) 상의 각 원소들의 표현방법은 크 게 벡 터 표현 (vecto r rep r esenta t i on ) 과 지 수표현 (exp o nent rep r esenta t i on ) 의 두 가지로 나눌 수 있다. 일반적으로 벡터표현에 의한 연산에서 가산 (addit ion ) 은 용이 한 반면 승산 (multip lica ti on ) 및 제 산 (div i s i o n ) 이 어 렵 고 지수표현에 의한 연산에서는 승산 및 제산이 비교적 쉬운 반면 가산은 매우 복잡하게 된다. 2-1 과 2-2 에서는 벡터표현과 지수표현에 의한 표준기지 (sta n dard basis ) 룰 이용한 연산들을, 2-3 에서는 벡터표현 중 정규기지 (normal bas i s) 를 이용한 연산에 대하여 설명하기로 한다.

2-1 벡터표현에 의한 연산 a 를 GF(2m) 상의 원시원(p r i m iti ve elemen t)이라 할 때에 0 원 ( ze ro elemen t)을 제의한 2m_1 개의 모든 유한체 원소(fi eld e lem e n t) 들 은 a 의 멱(p ower) 으로써 표시된다. 또 이 a 가 차수가 m 인 원시다 항 식 . P (x) =Po+P1X+… + Pm - 1X m -l+ xm p,- EGF(2), O b 匡 m ― 1 (2. 1) 의 근이라 하면 P (a) =Om 이므로 a m =Po+P1a+ … +Pm - la m - I 가 되어 GF(2 이상의 각 원소들을 차수가 m-l 이하인 a 의 다항식들로 표 현할 수있다. 이와 같은 표현방법을 다항식표현(p ol y nom i al re p resen t a ti on) 이라 하며 이 다항식들의 계수들만으로 표현하는 방법을 벡터표현이라 한 다. 예 를­ 둘어 CF( 한)상에서 원시다항식을 p(x ) =I+x 2 +x5 라 할 때 CF( 안)상 의 모든 원소들을 다항식표현과 벡터표현으로 나타내면 표 2.1 과 같 이 된 다. GF(2 이상이 임의의 두 원소 A 와 B 를 다항식표현으로 나타내면 A= ao+ a1a+ …+ am-lam- I (2.2) B=bo+b1a+… + bm-1am-i (2.3 ) 가 되고 이 두 원소의 합을 H라 하면 H=A+B= (ao+bo) + (a1+b1) a+… + (am- 1 +bm-1) am- I (2.4 ) 이므로 벡터표현에 의한 가산은 각 비트별로 EX-OR 함으로써 쉽게 수 행할 수 있다.

표 2.1 p(x ) =1+x2 十균일 때의 유한체 GF(2 이 다항식표현 벡터표현 다항식표현 벡터표현 。 00000 a15 = 1 + a +a2+a3+a ◄ 1 1 1 1 1 ao 10000 a16 = 1 + a + · a3+a ◄ 1 1 0 1 1 a I 0 l O O 0 a11 = 1 + a +a ◄ 1 1 0 0 1 a’ 2 0 0 l O 0 a1e = 1 + a 1 1 0 0 0 a 3 0 0 0 l 0 a19 = a +az 0 11 0l ' a4 0 0 0 0 l a20 = a2+a3 0 0 1 1 0 a 5 = 1 + a2 l O l O 0 a21 = a3+a ◄ 0 0 0 1 1 a6 = a +a3 0 l O l 0 a22 = 1 +같 +a• 1 0 1 0 1 aa 87 == 1 + aa22 + a3 + a• Ol OO ll Ol 01 aa2” ◄ == 1 +aa ++aa22++aa33 +a ◄ 01 11 11 11 01 a9 = a’ +a3+a• 0 1 0 1 1 a25 = 1 +a3+a ◄ 1 0 0 1 1 a10 = 1 +a• l O O O 1 a26 = 1 + a + a2 + a• 1 1 1 0 1 a11 = 1 + a + a2 1 1 1 0 0 a21 = 1 + a +a3 1 1 0 1 0 a12 = a+a2+ a 3 0 1 1 1 0 a28 = a+a2 +a• 0 1 1 0 1 a13 = a2+a3+a• 0 0 1 1 1 a29 = 1 +a3 1 0 0 1 0 a” = 1 +갑 +a3+a• l O 1 1 1 a3o = a +a• 0 1 0 0 1 2-1-1 조합논리회로 (comb in a ti onal log ic c iruit)를 이용한 승산기 GF(2m) 상의 임의의 두 원소 A 와 B 의 곱을 생각해 보자. A 와 B 를 각각 A=ao+a1a+ … +am-1«m-l= 접다 (2·5(`2·`,6' ` `,' m-1 B=bo+b1a+···+bm-1«m-i= ;~~o b,a' 이라 할 때 두 원소의 곱 Z 는 다음과 같이 쓸 수 있다. m-1 m-1 Z=A·B=A· ~ b;ai= ~-bi( Aa;) (2.7) i= O i= O

위 식을 행렬 (ma t r i x) 로 표현하면 다음과 같다. A (zo z,···zm-1) = (bo 싸 •• 도) I AAaa2 (2.8) Aa'-1 예를 들어 p (x)=l+x2+x5 인 GF( 한)상에서의 임의의 두 원소 A,B 간의 승산을 생각해 보자. 식 (2 . 7) 의 Aa' 는 A = ao+ a1a+ a2a2+ a3a3+a.a4 Aa= aoa+ a1a2+ a2a3+ a3a4+ a4 (1 +a2) = a ◄ + aoa+ (a1 +a ◄) a2+a2a3+ a3a4 Aa2= a3+a ◄ a+ (a 。 +a3) a2+ (a1 + a ◄) a3+ a2a4 Aa3= a2+a3a+ (a2+a ◄ )a 나 (ao+a3) a 포 (a1+a.) a• Aa 두 (a1+a ◄) +a2a+ (a1+a3+a ◄) a 나 (a2+ a ◄) a 나 (a 。+ a3) a• 이므로 행렬로 표현하면 (zoZ1Z2Z3Z4) = (bob1b2b3b.) a 。 a1 a2 a3 a4 a4 a 。 (a1+a.) a2 a3 a3 a. (ao+a3) (a1 + a.) a2 (2.9) a2 a3 (a2+ a4) (ao+aa) (a1+a.) (a1+a.) a2 (a1+a3+a.) (ai, + as) (ao+ a3) 가 된다. 위 식을 풀어쓰면 다음과 같다. zo= aobo+a,b1+aab i+fh.ba + (a1 + a,) b, Z1 = a1bo+ aob1+ a.l>i + aaba + thh , z2= thb o+ (a1 +a.) bi + (ao+aa) &+ (th+ a,) ha+ (a1 +as+ a.) b,

Z3 = a3& + a2b 汗 (a1 + a.) b-z + (ll-0 + aa) ~ + (a2 + a.) b. z. = a.bo + aab1 + a2b -z + (a1 + a.) ~ + (ll-0 + aa) b. (2.10) 이 식을 이용하여 GF(25) 상의 승산기를 설계하면 그립 2.1 과 같다. 그립 에서 보듯이 이와 같은 승산기는 '.5 X '.5개의 2 입력 AND 게이트와 2 '.5개의 2 입력 EX-OR 로 구성할 수 있다. 조합논 리회로 를 이용한 승산기는 승산에 소요되는 지연시간이 매우 짧

a, a,

그림 2.1 조합논리회로를 이용한 GF(25) 의 승산기

은 반면 회로연결 (w i re rou ti n g)이 불규칙적아고 m 이 커지면 회로가 복잡 해지는 단점을 가지고 있다. 2-1-2 순차논리회로 (se q uen ti al log ic ci rcu it)를 이용한 승산기 승산 지연 시간이 매우 짧아야 할 필요가 없는 경우 치환 레지스터 (shif t reg iste r ) 를 이 용하면 조합회 로를 이 용한 승산기 보다 간단하고 경 제 적인 승산기를 구성할 수 있다. 식 (2.7) 에서와 같이 두 원소의 곱 Z 는 다음과 같이 나타낼 수 있다. m-1 Z=A·B= ~ b;(Aa;) i= O = [… [[b 。 (A) + b1 (Aa)] +b2 (Aa2) ]+ …]+ bm-1 (Aam-l) (2.11) 위 식에서 살펴보면 A 와 B 의 곱 Z 는 A 에 a 를 계속 곱하면서 거기에 B 의 계수들을 차례로 곱하여 계속 더해 나가면 구할 수 있다. 그러면 먼저 임의의 원소 A 에 a 를 곱해 나가는 회로를 생각해 보자. A= a, +a1a+ … am-1am-l 이고 p( a) =O 에서 am=Po+P1a+ … +Pm-1a'-1 이므로 Aa= a,a +a1a2+… am-lam = a,a + a1a2+… + am-1 (p。 +P1a+… + Pm-1am-l) (2.12) = am-1Po+ (t1o+ am-1P1) a+ (a, + am-1P2) a2+··· + (am-2+am-1Pm-1) am 키 가 된다. 이 식을 이용하여 회로를 구성하면 그립 2.2 와 같다.

그림 2.2 유한체 원소 A에 a 를 곱하는 희로

그림 2.3 순차논리회로 를 이용한 승산기 I

그립 2.2 를 이용하여 식 (2 . 11) 를 구현하면 그립 2.3 과 같은 승산기를 얻 을 수 있다. CF( 안)상에서 p(x ) =1+x2+x5 일 때 식 (2.11) 은 Z=A·B = [[[bo (A) +b1 (Aa)]+b i (Aa2)]+ ~ (Aa3)]+b.Aa4 (2.13) 가 되며 이 식을 이용하여 승산기를 설계하면 그립 2 .4와 같다. 또한 식 (2 . 11) 을 다음과 같이 변형하면 다론 형태의 승산기를 구성할 수있다. Z=A·B= m:l-!1 (b;A) a; i= O = (… ( (bm-1A) a+ bm-2A) a + …) a+ boA (2.14) 죽 bm-1A 에 a 를 곱하여 bm-2A 와 더 하고 그 결과에 다시 a 를 곱하고

그림 2.4 순차논리회로를 이용한 GF(25) 의 승산기 I

그림 2.5 순차논리회로를 이용한 승산기 I

그럼 2.6 순차논리회로를 이용한 GF( 양)의 승산기 Il

bm-3A 와 더하고 이런 식으로 m 번을 계속 수행하면 A 와 B 의 곱 Z 를 얻을 수 있다. 이상을 그림으로 나타내면 그립 2 . 5 와 같다. 예 를 들어 GF(25) 상에서 p(x ) =l+x2+x5 일 때 식 (2.14) 는 Z=A·B= ( ( ((b.A) a+~A) a+i> zA ) a+b iA ) a+boA (2.15) 가 되며 이 식을 이용한 GF(25) 의 승산기는 그립 2.6 과 같다. 이상의 순차논리회로를 이용한 승산기는 회로가 비교적 간단한 반면 승 산을 수행하는데 m clock 의 시간이 지연되는 단접이 있다. 2-1-3 • Cellular -A rray 승산기 앞에서 설명하였듯이 순차회로를 이용한 승산기는 GF(2m) 상에서 임의 의 두 원소를 곱하는 데 있어서 m clock 의 시간이 소요된다. 이러한 지 연 시간을 줄이고 회로연결을 규칙화하여 LSI 화에 적합하게 하기 위하여

z a

그림 2.7 Cellular-Array 승산기의 기본적인 cell

Law 러 Rus hfo rth는 그림 2.5 와 같은 승산기를 조합논리회로를 이용하 여 각 비트별로 cell 로 만든 다음 이 cell 둘을 공간적으로 나열한 Cellular-Array 승산기를 제안하였다. 그립 2.7 에 이 cell 을 나타내었다. 그립 2.7 에서 a 와 b 는 입력 비트이고 z 에는 한 행 전, 한 열 옆의 출 력이, 1/ 1 에는 한 행 전의 fee dback t erm 이 연결된다. Cellula~-Arra y승 산기는 이 cell 둘을 m 행 m 렬로 배치하여 승산을 수행한다. 그립 2.8 의 Cellular-Arra y승산기에서는 첫행에서 식 (2.14) 의 bm-1A 의 연산이 수행되며 각 cell 둘의 출력들은 오른쪽으로 한 열씩 이동되어

a 。 a 1 am- I

그림 2.8 Cellular-Array 승산기

다음 행으로 연결되므로 두번째 행에서는 (bm - 1A)a+bm-2A 가 나타난 다. 이러한 과정을 m 번 계속함으로써 A 와 B 의 곱 Z 가 Z 레지스터에 저 장되게 된다. 그림 2.7 의 기본적인 cell 를 pi =0 일 경우와 pi =1 일 경우의 두 가지 형태로 나누어 보면 그림 2 . 9 와 같이 된다. 예를 들어 GF(25) 상에서 p( x) =l+ 났 +x5 인 경우 Cellular- f:rr a y승 산기를 구성하면 그립 2.10 과 같다 .

z a

(a) P1 = O 인 경우

z a

그림 2.9 변형 된 cell

a, a, a, a, a.

그립 2.1 0 GF( 산)의 Cellular-Array 승산기

2-1-4 재산회로 GF(2m) 상의 임의의 두 원소 A 와 B 에서 A 를 B 로 나누는 경우를 생 각해 보자. A 를 B 로 나눈 결과를 Y 라 할 때 이 Y 는 다음과 같이 쓸 수있다.

Y=A/B=A·B- 1 (2 .16) 죽 Y 를 구하기 위해서는 B 의 역원(i nverse elemen t)을 구하여 A 에 곱하 면 된다. GF(2 이상에서 임의의 한 원소 B 의 역원을 구하는 방법은 B2m 기 =1 (2.17) 이므로 이 식의 양변에 B-1 을 곱하면 s-1 =B2m-2 (2.1 8 ) 가 된다. 여기에서 2m-2 =2+22+23+… + 2m-1 (2.19) 이므로 B 의 역원 B-1 은 다음과 같이 쓸 수 있다. B-1 = (B2) (B22) (B”) …( B2m-l) (2.2 0 ) 이 식을 이용하여 GF(2m) 상의 임의의 한 원소에 대한 역원 계산기 를 설 계하면 그립 2.11 과 같다. 그림 2.11 에서 SW(sw it ch) 들을 초기 상태에서 SWl 은 B 에 SW2 는

B 제곱기

그립 2.1 1 역원 계산기

표 2.2 CF( 간)상의 역원 계산 과정 단계 제곱기 입력 제곱기 출력 승산기 입력 승산기 출력 1 B B2 B2•1 = B2 2 B2 B• B••B2 = B6 3 B' B8 Bs·B6 = B 4 B8 B16 B16•B14 = B30 5 AB30 = AB-1 1= (00···1) 에 연 결 되어 있다가 다음 단계부터는 각 f eedback 에 연결된다. 예 를 들어 CF( 선)상의 임의의 원소 B 의 역원은 식 (2.18) 에 의하여 s-1 = B3o = (B2) (B2') (B2') (B2 ') (2.21) 가 된다. 이 계산 과정을 표로 나타내면 표 2 . 2 와 같다. 표 2.2 에서 보듯이 임의의 한 원소에 대한 역원을 구하는 데는 m-1 clolck 의 지연이 생긴다. 2-1-5 제곱 및 제곱근회로 GF(2') 상에서 임의의 한 원소 A 의 재곱을 S 라 할 때 S=A 도 (ll<)+ a1a+… + am-1am-l)2 =~+a1 (a) 나… +am-1(am 크 )2 (2.2 2 ) 가 된다. 이 식을 행렬표현으로 나타내면 다음과 같다. (aO) 2 (al)2 (S0S1… S m-1) = (0oa1:· ·a m,--1) • I (a2)2 (2.23) (am-1)2 예를 들어 GF(25) 상에서 p (x)=l+x 나갔라 할 때

(aO) 2 = 1 (a1)2=a2 (a2)2=a• (a3)2= 간 =a+a3 (a•)2= aa= 1 +a2+ a3 이므로 식 (2.23) 은 다음과 같이 쓸 수 있다. 10000 00100 (soS1SzS3S4) = ((1-0 a1aza 이 • 10 0 0 0 1 (2.24) 0 1 0 1 0 1 0 1 1 0

그림 2.12 GF( 산)상의 제곱기

여기서 So = a。 +a. s1=a3 s2 = a1 + a. (2.25) s3=a3+a. s.=a2 위 식을 이용하여 CF( 산)상이 제곱기를 구성하면 그립 2.12 와 갇다. GF(2m) 상의 임의의 한 원소 A 의 제곱근을 R 이라 하면 R=IA=A½= (~+a1a+ … +am-1am-l) 승 (2.26) = ~ (aO)½+ a1 (a1) 살+ …+ am-I (am-I) 승 가 되며 행렬로 표현하면 (a0)2I (a 답 (ror1·Ym-1) = (GQ a1am-1) • I (a 캬 (2.27) (am-I) 승 가된다. 예를 들어 GF(25) 상에서 p(x ) =l+x 나갔이라 할 때 (aO)tI = l (al) 송= ac31+1>12= a16= 1 +a+a3+a' (a2)tI = a (a 답= a<31+3>12 = a11 = i + a + a' (a')tI = a2 이므로 식 (2 . 27) 은 다음과 같이 쓸 수 있다.

10000 (rmr品 ) = (a.a, a,a,a,) • I: : : : : (2.28) 1 1 0 0 1 00100 여기서 r。 = ao + a1 + as r1 = a1 + a2 + as r2=a. (2.2 9 ) rrs.==aa11 +as

그립 2.13 GF( 산)상의 제곱근기

위 식을 이용하여 제곱근의 회로를 구성하면 그림 2 . 13 과 같다. 2-2 지수표현에 의한 연산 CF(2 기상에서 0 원을 제의한 모든 원소들은 원시원 a 의 멱으로 나타 낼 수 있다. 이 a 의 멱을 2 진수로 표시한 것을 CF(2m) 상의 원소들의 지 수표현 (exp o nent rep re senta ti on ) 이 라 한다. 지수표현으로 나타낼 경우 ao 원소와 0 원소와의 구별이 요구되는데 다 음과 같은 두 가지 방법으로 나타낼 수 있다. (방법 •1) {0a°- 一(1 (100… … 1 )0 ) (방법 .2) { oa0-(-o(1o1… … 0 )1 ) 예 를 들어 p(x ) =1+ 났 +x5 인 GF(25) 상의 원소들을 지수표현으로 나 타내 면 표 2.3 과 갇다. GF(2 이상의 벡터표현에서 지수표현으로의 변환이나 그 역변환은 m 비 트 address 와 m 비트 ou tp u t을 갖는 ROM 으로 처리할 수 있다. 지수표현에 의해서 연산을 하는 경우 승산과 제산은 지수표현들의 2 진 덧셈과 뺄셈으로 쉽게 수행할 수 있는 반면 가산은 매우 복잡하게 된다. 2-2-1 승산회로 GF(2 기상의 0 원이 아닌 임의의 두 원소 A 와 B 를 각각 a', a; 라 할 때두원소의곱 Z 는 Z=A •B = ai • aj = ai+ J(m od2•-1) (2.30) 가 된다. 그러므로 Z=A•B 를 구하기 위하여는 A 와 B 를 지수표현으로 바꾼 다음 2 진 덧셈을 하면 된다.

(방법 .1) 의 경우 mod(2m-1) 은 carr y가 생성될 때와 2 진 합이 모두 1 일 경우에 수행된다. carr y가 생성될 경우에는 2 전 합의 최하위 비트에 carr y를 더함으로써, 또 2 진 합이 모두 1 일 경우에는 최하위 비트에 1 을 더함으로써 mod(2m-1) 을 수행할 수 있다. 예) GF(2 이상에서 a's.a2o=a‘ 이다. 0 1 1 1 1 --+a15 의 지 수표현 + 1 0 1 0 0 --+a” 의 지수표현 0 0 0 1 1 + 1 0 0 1 0 0 -+a' 의 지수표현 또한 a1s.a1s=ao 이다. 0 1 1 1 1 -+a” 의 지수표현 + 1 0 0 0 0 --+al6 의 지수표현 1 1 1 1 1 + 1 0 0 0 0 0 -+ao 의 지수표현 두 원소 A 와 B 중에서 한 원소만이라도 0 원일 경우 두 원소의 곱 Z

i+j

그립 2.14 지수표현에 의한 승산회로 1

는 0 원이 된다. 그러므로 이와 같은 경우 승산회로는 2 전 덧셈을 하지 않고 0 원을 출력하여야 한다. 이상과 같은 방법으로 승산기를 구성해 보 면 그립 2 . 14 와 같다 . 그립 2 . 14 에서 FA1(fu ll adder 1) 은 두 원소의 지수표현을 2 진 덧셈하는 것이고 FA2 는 mod(2m-1) 을 수행하기 위한 m 비트 전 가산기이다. A1 D(all 1 de t ec t or) 는 i와 j가 모두 1 인가, 죽 O 원소인가를 검출하는 것으 로 m 입력 AND g a t e 로 실현할 수 있다. 또한 AIO(all1 ou tp u t)는 지수 표현의 0 원 , 즉 모두 1 을 출력하는 회로이다. 그러나 (방법 •2) 의 경우 2 진 합이 모두 1 일 경우, 예를 들어 GF(25) 상에서 a” 와 a” 을 곱할 경우 2 전 합이 모두 1 이 되는데 이것이 바로 ao 원을 나타내므로 최하위 비트에 1 을 더해 줄 필요가 없게 된다. 0 1 1 1 1 .-.a15 의 지수표현 + 1 0 0 0 0 .-.a16 의 지수표현 1 1 1 1 1 -a0 의 지수표현 그러므로 이와 같은 방법으로 승산기를 구성하면 그립 2.15 와 같다. 그립 2.15 에서 AZD(all zero de t ec t or) 는 0 원의 지수표현, 죽 여기에서 는 (00 … 0) 를 검출하는 회로이며 m 입력 NOR g a te..5드 실현할 수 있다.

FA 2 i+j

그림 2.1 5 지수표현에 의한 승산기 n

AZO(all zero ou tp u t)은 0 원, 즉 모두 0 을 출력하는 회로이다. 그립 2.15 에서 보듯이 (방법 •2) 로 지수표현을 나타내는 경우 2 진 합이 모두 1 일 때 mod(2m-1) 을 수행하는 회로를 생략할 수 있어 간략화할 수 있는 장점이 있다. 2-2-2 제산회로 GF(2m) 상의 임의의 두 원소 A 와 B 를 a i와 a j라 할 때 A 를 B 로 나 누면 y= AlB=aiI aj= ai- j(mo d2f fl- 1) (2.31) 과 같이 된다. 그러므로 Y 를 구하기 위해서는 A 와 B 를 지수표현으로 바꾼 다음 2 진 뺄셈을 하면 된다. 2 진 뺄 셈은 빼는 수 j에 1 의 보수 (l's com p lemen t)을 취하여 더해 주는 것으로 제산회로는 승산회로와 비슷하 게 된다• 그림 2.16 에 제산회로를 나타내었다. 여기에서 지수표현은 (방 법 •2) 를 택하였다. 그립 2.16 에서 1c (l's com plemen t)는 j에 1 의 보수를 취하는 회로이며 DE 는 분모가 0 일 때 불능을 나타내 주는 회로이다.

DE j亨i-j

그립 2.16 지수표현에 의한 제산회로

2-2-3 가산회로 벡터표현일 경우 가산은 각 비트들간의 EX ― OR 로 간단하게 수행할 수 있는 반면 지수표현일 경우에는 여러 연산 중에서 가장 복잡한 것이 가산이다. 지수표현에 의한 가산은 다음과 갈이 승산과 제산의 형태로 변형하여 수행할 수 있다. 임의의 두 원소 A 와 B 의 합을 H라 하면 H =A+B = a;+ a; =ai ( ai- ;+ 1) (2.32) 그립 2.17 에서 0 은 그림 2.16 의 제산기를, 修은 그립 2.15 의 승산기를 나타낸다. ROM 에서는 (aE j +1) 의 지수표현을 출력하여 DE 는 a j가 0 원일 경우 a1 만을 출력하기 위한 selec t or 의 신호선으로 이용된다.

선택기 H

그림 2.17 지수표현에 의한 가산기

2-2- 4 제곱 및 제곱근회로 GF(2m) 상의 임 의의 한 원소 A 를 a’라 할 때 A 의 제곱을 S 라 하면 S = A2 = a2i( m 0d2'-l) (2.33) 가 된다. 여기에서 A=a; 의 지수표현을 (&g ··am-l) 이라 하면 i = ao + a12 + ai. 2 나 …+ a'-12'-1 (2.34) 이고 2i (m od 2' 一 1) 은 2' ＝ 1 의 관계를 이용하면 2i = a'-1 +ao2+a122+ …+ am-22'-1 (2.35)

am aa-3 。I 二..... a 。 aa 。1 디aaam21 - 2

그림 2.1 8 제 곱 및 제 곱 근 회로

가 된다• 그러므로 S=a 2’ 의 지수표현은 (am -I (i-O • •• a m - 2 ) 이다. 죽 임의 의 한 원소의 제곱은 그 원소의 지수표현의 비트 를 오 른 쪽으로 한 번 순 최치환한 것이 된다. A 의 제곱근을 R 이라 하면 R = IA= R= ai /2 (m o d2 '- 1 ) (2 .3 6 ) 가 되고 1=2m 이므로 식 (2.3 4 ) 에서 i/2 = a1 + 1222+… + am - 12m- 2+ ao2m- 1 (2. 37 ) 가 된다. 그러므로 R=a i 1 2 의 지수표현은 (a1( h. .. •am-I tJo)가 된다. 죽 임 의의 한 원소의 제곱근은 그 원소의 지수표현의 비트 를 왼 쪽 으로 한 번 순회치환한 것이 된다. 이상에서 설명한 제곱 및 제곱근회로를 그림 2 . 18 에 나타내었다. 2-3 정규기지에 의한 연산 2-3-1 정규기지 GF(2m) 상의 m 개의 선형독립(li nearl y i nde p enden t)인 원소들의 집합을

GF (2 기 의 기 지 (basis ) 라 한다. a 를 차수가 m인 원시다항식 p (x) 의 근이라 할 때 {a-}, O~k~m-I 은 GF(2 기의 기지이다. 이 기지를 GF(2m) 의 표준기지 (sta n dard basis ) 라한다. GF(2 기상에서 {a, a2, a 핫 …, a2m - 1} 가 선형독립이면 이들은흩 GF(2m) 의 기지가 되는데 이러한 기지를 정규기지 (normal bas i s) 라 한다. 예 를 들어 CF( 간)상에서 p (x)=1+x2+x5 라 하면 a+a2+ a •+a8+a16= a+a2+a•+ (1+a2+a3) + (I+a+a3+a4) =O (2.38) 이므로 {a, a2, a4 , a8, a16} 은 GF(25) 의 기지가 되지 못한다. p( x) =1+ 났 +x3+x•+x5 를 택하면 a+ a2 +a 4+a8+ a16=a+a2+a•+ (a2+a3+a4) + (1+a+a3) =1 (2.39) 가 되어 {a, a2, a4, 군, al6} 이 선형독립이므로 CF( 건)의 정규기지가 될 수있다. 표준기지에서 정규기지로의 변환을 생각하여 보자. CF( 간)상의 임의 의 한 원소 A 를 A= ao+a1a+( ha 2+a3a3+~a• (2.4 0 ) 이라 할 때 표준기지 (a0, a1, a2, a3, a~) 를 정규기지로 바꾸면 a0 = a1 + a2+a ◄ +a8+ a16 같 =al a2= a2 (2.4 1 ) a3= a2+a+as a•= a• 가 되므로 A 를 정규기지로 바꾸면 다음과 갇이 된다. A= ao (a+a2+a•+a8+a16) +a1a+a 꿉 +a3(a2+a4+ 군) +a4a4

표 2.4 GF(25) 의 정규기지 표현 멱 표준기지 표현 정규기지 표현 멱 표준기지 표현 정규기지 표현 。 00000 00000 alS 1 1 0 1 1 0 0 1 0 1 ao 1 0 0 0 0 1 1 1 1 1 al6 1 1 0 1 0 0 0 0 0 1 al 01000 10000 al1 0 l l O l l l l O 0 a2 00100 01000 a18 1 0 0 0 1 l l O l l a3 0 0 0 1 0 0 1 1 1 0 a19 1 1 1 1 1 0 l l O l a' 00001 0 0 1 0 0 a20 1 1 0 0 0 0 I I I I a5 1011. .1 1 1 1 0 1 a2 1 0 1 1 0 0 1 1 0 0 0 a6 l l l O 0 0 0 1 1 1 a2 2 00110 0 0 1 1 0 a1 fl 1 1 1 0 1 0 1 1 0 a2 3 0 0 0 l l 0 1 0 1 0 a8 0 0 1 1 1 0 0 0 1 0 a2 • 1 0 1 1 0 l l O O l a9 1 0 1 0 0 1 0 1 1 1 a25 0 1 0 1 1 1 1 0 1 0 alO 0 1 0 1 0 1 1 1 1 0 a2 6 1 0 0 1 0 1 0 0 0 1 all 0 0 1 0 1 01100 a2 1 0 1 0 0 1 1 0 1 0 0 al2 1 0 1 0 1 1 0 0 1 1 a28 1 0 0 1 1 1 0 I O I al3 1 1 1 0 1 0 0 0 11 a29 1 l l l 0 0 1 0 0 1 a” 1 1 0 0 1 0 1 0 1 1 a3o 0 1 1 1 1 1 0 0 1 0 = (ao+a1) a+ (ao +a2+ a3) a 나 (ao+a3+a.) a4+ (ao + a3) a 나 aoa16 (2.4 2 ) 위 식을 이용하여 p(x ) =1+ .x 2+ .x 3+ .x나+.X S 일 때 GF(25) 의 정규기지 표 현을 표 2 .4에 나타내 었다. 2-3-2 제곱 및 제곱근회로 GF(2m) 상에서 임의의 한 원소 A 를 정규기지로 표현하면 다음과 갇 다. A=~a+a1a2+… + am-1a2m-l (2.4 3 ) 여기에서 A의 제곱을 S 라 하면

a。 aI a2 •••• •>

그립 2.19 정규기지 표현을 이용한 제곱회로

S=A2= (aoa+a1a2+… + am-1a2m-1)2 = am-1 a + aoa2 + a1 a4 + …+ am-2a2'-• (2.4 4 ) 가 된다. 즉 A 의 제곱은 A 의 정규기지 표현(a.i a1 … am-1) 을 오른쪽으로 한 번 순회치환한 S = (am-h {lo, a1, …, am-2) (2. 4,) 가 된다. 따라서 GF(2 이상에서 임의의 한 원소 A 의 제곱 A2 의 장치화 는 치환 레지스터를 사용하여 그립 2.19 와 갇이 장치화할 수 있다. A 의 제곱근을 R 이라 하면 R= (A) i1 2= (aoa+a1a 도 .. +am-1a2'-')112 = a1a+ 0-2.a 2+… + am-1a2 .. -'+aoa2. . _, (2.4 6 ) 가 된다. 죽 A 의 제곱근 R 은 A 의 정규기지 표현 (ao,a1, … ,am-I) 을 왼 쪽으로 한 번 순회치환한 R= (a1, ai, …, am-h llo) (2.4 7 ) 가된다. 2-3-3 승산회로 GF(2m) 상에서 임의의 두 원소 A 와 B 를 정규기지 표현으로 나타내면 다음과같다. A= 0oa+a1a2+···+am-1a2 .. -I B = boa+ b1a 나··· + bm-1a2•-•

이 두 원소 A 와 B 의 곱을 Z 라 하고 Z 롤 정규기지 표현으로 나타내면 Z=A • B=zoa+z1a 도 .. +zm -1 a2m- l (2. 5 0) 가 된다. 죽 다시 쓰면 Z=A·B= (~. a1, …, am-1) • (ho, b1, …, bm -1 ) = (Zo , Z1, …, Zm-1) (2.51) 로 쓸 수 있으며 여기에서 Z 의 마지막번째 계수 Zm - 1 은 A 와 B 의 계수 둘의 2 진 함수이므로 다음 식과 같이 나타낼 수 있다. Zm-1=/(~. a1, ···, am-I ; bo, b1, …, bm-1) (2.52) 식 (2 .4 5) 에서 보듯이 제곱은 한 번의 순회치환을 의미하므로 Z2=A2•B2= (am-i. C4i, a1, …, am -2) • (bm -1, bo, b1, …, bm-2) = (Zm-1, Zo, Z1, …, Zm-2) (2.53) 과 갇이 된다. 여기에서 마지막번째 계수 Zm-2 는 식 (2.52) 와 같이 Zm-2 =I(am-1, ao, a1, …, am-2 ; bm-1, ho, b1, …b m-2) (2.54) 가 된다. 이런 식으로 계속 제곱해 나가면 A 와 B 의 곱 Z 의 모든 계수 들을 차례로 얻을 수 있다. Zm-1=I(ao, a1, …, am-I ; bo, bi, …, bm-1) Zm-2=/(am-t, flo, a1, …, am- 2 ; bm-1, bo, b1, …, bm-2) (2.5 5 ) zo=f (a 1%, …, am-1' % ; h, &, …, bm-i, bo) 그러므로 식 (2.55) 를 이용하면 그립 2.20 과 갈은 승산기를 구성할 수 있다. 예를 둘어 p(x ) =l+x2+ 났 +x•+x5 인 GF( 산)상의 승산기를 구성해 보자. a 가 P(x) 의 근일 때 {a, a2, a\ a8, a16} 은 GF( 안)상의 정규기지이 다. GF(25) 상의 임의의 두 원소 A 와 B 의 곱 Z 는 다음과 같다. Z=A·B= (aoa+a1a 포(h. a 나如군 +a.a16) • (boa+ bi a 나 &a 나 &as+b,al&) =zoa+Z1a2+Zza4+z3a8+z.a18 (2.56)

a 。 a, ... a m- I

그립 2.20 정규기지를 이용한 승산기

표 2 .4를 이용하여 A 와 B 를 서로 곱한 다음 갇은 항별로 모으면 Z 의 계 수 Zi, O~ i ~4 은 다음과 같이 구해전다. z, = a3f h+ a2ba+ aobz + a2b, + a,bz + a3ba+ aob3 + a3bz + a2b3 + a,b, + a,b, + a,bz + a2b, + a,lh + a3b, Z3 = a2bz+ a,ba+ aab, +a2b1 + a,bz + a3ba + aolh + a3b1 +a1lh + a3bz + a2lh + a,b, + a,b, +a,bz+a2b, z2 = a1 b1 + a, ba + ao b, + a2 ba + ao bz + a2 b1 + a1 bz + a3 ba + ao lh + a3 b1 + a1 lh + a,ba + aob, + a,bz + a2b, Z1 = aoba+ a1ba+aab1+a2ba+ aobz + a3b1 + a1lh +a,ba + aob, + a,b1 + a1b, + a,bz + 0,zb , + a,lh + a3b, Zo = a,b, + a2ba +aobz +a3ba + aolh + a3b1 + a1lh + a3bz +a2lh + a,ba+ aob, + a,b1 +a,b, + a,lh+ a3b, (2.57) 가 된다. 그러므로 그립 2.20 의 논리함수 (Lo gi c function ) f는 식 (2.57) 과 같이 15 개의 AND 게이트와 14 개의 EX-OR 게이트로 구성할 수 있다. 논리함수 f를 구성하는데 있어서 원시다항식 p (x) 를 적철히 선택하면 게이트 수를 줄일 수 있다. 예를 들어 GF( 산)에서 p(x ) =l+x+ 났+/

표 2.5 p(x ) =l+x+x2+x•+x5 일 때 GF( 간)의 정규기지 표현 멱 표준기지 표현 정규기지 표현 멱 표준기지 표현 정규기지 표현 。 00000 00000 alS 1 0 1 0 1 1 0 0 1 1 ao 10000 1 1 1 1 1 a” 1 0 1 1 1 0 0 0 0 l al 01000 1 o.o O0 a11 1 0 1 1 0 0 0 1 0 1 a2 00100 01000 alB 0 1 0 1 1 0 0 1 1 0 a3 00010 10010 a19 11000 0 1 1 1 1 a• 00001 00100 a20 0 1 1 0 0 1 1 0 0 0 a5 1 11 0 1 0 0 0 11 a21 0 0 1 1 0 l l O l 0 a6 1 0 0 1 1 0 1 0 0 1 a22 0 0 0 1 1 1 0 1 1 0 a7 1 0 1 0 0 1 0 1 11 a23 1 1 1 0 0 0 0 1 1 1 aB 0 1 0 10 00010 a2• 0 1 1 1 0 0 1 0 1 0 a9 0 0 1 0 1 01100 a2s 0 0 1 1 1 l l l l 0 alD 1 1 1 1 1 10001 a26 111 1 0 1 0 1 0 1 all 1 0 0 1 0 0 1 1 0 1 a21 0 11 1 1 0 1 1 1 0 al2 0 1 0 0 1 1 0 1 0 0 a28 1 1 0 1 0 1 1 1 0 1 al3 1 1 0 0 1 0 1 0 1 1 a29 0 11 0 1 1 1 1 0 0 a” 1 0 0 0 1 11 0 1 1 a30 1 1 0 1 1 1 1 0 0 1 +xs 를 택하면 각 원소들은 표 2.5 와 같이 표현되는데 이 표를 이용하여 식 (2.56) 의 각 계수들을 구해 보면 다음과 같이 된다. Z4 = a3&+ {h.b.,+ aobz+ a2b i +a1bz+ asb1 + a1l> .i +a.ho +aob. zs = a2bz + a1 bo + aob i + {h.b., + tzob z + a.bi + a1 b. + a.l>.i + asb• z2 = a1b1 +야&+ %& + asbz+a2l> .i+ a.ho+aob.+ a.bi + a1b• Z1 = %&+{h.bi + a1bz+ asbo+tz ol>.i+ a.b i+ {h.b . +a.l>.i +asb• Zo = a•b• + a1bo +tzob 1 + asb i + a1l> .i + asbz + th.l>.i + a.bi + a2b• (2.5 8 ) 죽 식 (2.58) 에서 보듯이 P(x) =l+x+x2+x•+x5 로 생성되는 정규기지 표현을 이용하면 논리함수 f가 9 개의 AND 게이트와 B 개의 EX-OR 게이 트로 구성되는 그립 2.21 과 같은 직렬형승산기 (se q uen ti al-mul tipli er) 를 구 성할 수 있다. 한편 그립 2 . 22 의 병렬형승산기는 5 개의 논리함수 f를 사 용하여 Z 의 원소 Z;(O~ i ~4) 를 동시에 계산할 수 있도록 한 것이다.

기산승 형렬직 한용 이 를 지기규정 의상)6 2 (F G .212 립그

二 三

그림 2.22 GF( 잔)상의 정규기지롤 이용한 병렬형 승산기

2-3- 4 역원 계산기 유한체 GF(2m) 상에서 임의의 한 원소 B 의 역원은 식 (2.18) 과 같이 B-1 =B2m-2=B< 2+ 2 사 ... +2m-1J = (B2) (B2') (B2•) … (B2m-1) (2.59)

B

그립 2.23 정규기지를 이용한 GF(25) 상의 역원 계산기

로 쓸 수 있다. 정규기지 표현에 의하면 B” 는 B 를 j번 순회치환시킨 것 과 동일하므로 식 (2 . 59) 를 이용하여 CF( 안)상에서 그립 2 . 11 과 같은 역 원 계산기를 구성하면 그림 2.23 과 같다. 그림 2.23 에서 selec t or 는 초기 상태에서 각각 B 와 1 에 연결되어 있다 가 다음 단계부터는 각 fe edback 에 연결된다.

제 3 장 BCH 부호의 복호법 BCH (Bose-Chaudhuri- H oq u eng h em) 부호는 블럭 부호 (block codes) 인 순 회 부호 (cy cl ic codes) 의 일종으로 매 우 강력 한 오류 정 정 능력 을 갖는 부 호로서 콤퓨터 기 억 장치 , 광 디스크, DAT (Di gital Audio Tape ) 등과 같 은 디지탈 정보 저장 시스템은 물론 위성통신, 우주통신, 암호통신 및 이동 무선전화와 같은 디지탈 통신 시스템에 널리 사용되고 있다. 2 원 BCH 부호의 효과적인 복호알고리즘은 1960 년 Pe t erson 에 의하여 처음 제안되었으며 이 알고리즘은 1961 년 Gorens t e i n 과 Z i erler 에 의해서 개선되어 비 2 원 BCH 부호에까지 적용될 수 있게 일반화되었다. 또한 BCH 부호의 복호알고리즘으로 가장 보편적으로 알려져 있는 Berlekamp -Masse y의 반복알고리 즘이 있다. 이 장에서는 2 원 BCH 부호의 부호화 방법 및 여러가지 복호알고리즘들 을 연구 분석하고 그리고 장치화의 관점에서 비교적 상세하게 설명하기 로한다. 3-1 순회부호의 표현 부호장이 n 이고 정보장이 k 인 (n,k) 순회부호의 생성다항식을 g( x)=

go+ g1 X+ …+g n-kXn-k 이라 할 때 d(x) =d。 +d1x+ … +dk - !Xk - l 을 부호 화될 정보다항식이라 하면 부호다항식 c(x) 는 다음과 같은 비조직형으로 표현된다. c (x) = d(x) •g( x) = Co+ C1X+C2X2+… +Cn- 1 Xn- l (3.1 ) 조직형 (n, k) 순회부호의 부호어는 다음과 같이 d(x) 에 Xn - k 룹 곱하 여 g (x) 로 나누면 구할 수 있다. xn-1id (x) =q( x) • g( x) +p( x) (3.2) 여기에서 q (x) 는 몫 다항식이고 나머지 P(x) 는 (n ― k ― 1) 차 이하의 패 리티검사 다항식이다. 그러므로 조직형 부호다항식은 다음과 같 이 표 현된다. c(x) =P (x) +xn-kd(x) =Po+P1X+ … +Pn-k-1Xn- k -l + doxn-k+ d1xn- k +I + … + dk-1Xn- l (3. 3) 이것은 다음의 부호어에 대응된다. C = (Po, P1, …, Pn-k-I, do, dI, …, dk-1) (3.4 } 식 (3 .4)로부터 부호어는 n_k 개의 패리티검사 디지트들과 k 개의 정보 디지트들로 구성된다. 조적형 생성행렬 G 는 다음과 같이 xn-k” 를 g (x) 로 나눔으로써 구할 수있다. xn-Hi =q;( x) g( x)+p ;( x), O£:i £ :k— 1 (3.5 ) c,·( x )=p i(x )+xn-k+i, 0 스i스 k ― 1 (3.6) 그러므로 이 k 개의 다항식들은 kXn 행렬의 행으로 나열하면 다음과 같 은 조직형 생성행렬 G 를 구할 수 있다. g。 Poo Po1 Po,n-k.- 1 1 0 0 … O G=1 g\ = pIO pII P1,n-1t- 1 o 1 o … O (3.7) g1,.-1 P1c-1,o P1c-1,1 … pk- In-k-IO O O … 1

그러므로 부호어 c 는 c = (co, c,, C2, …, Cn- I) = (do, d,, d2, …, dk- 1 ) •[go, g,, g2 , …, gk _ ,] T (3.8) o] 다. 3-2 BCH 부호의 구조와 부호화 [72] 부호장이 n=2m- 1 인 2 원 t중 오류정정 BCH 부호의 생성다항식 g( x) 는 근 a, a2 . …, a” 에 대응하는 최소다항식 m i( x), I~ i ~2 t의 곱으로 이루어진다. 여기서 a E GF(2m) 는 원시다항식 p (x) 의 근이다. 2 원 기호 {0 , 1} 을 계수로 하는 c(x) = co + c1x+c2 x2 + … +Cn - 1Xn - l 을 부호다항식이 라 할 때, 부호다항식 c(x) 가 a,a 러… ,a” 을 근으로 갖는다면 c(x) 는 이러한 근들에 대응하는 최소다항식 m1(x), mi (x), …대Zit (x) 로 나누어 떨 어지므로 t중 오류정정 BCH 부호의 생성다항식 g (x) 는 이들 최소다항 식 의 최 소공배 수 (lea st common multip le ) 이 어 야 한다. 죽 g (x) =LCM{m1 (x) , 1n2 (x) , …, 1n2, (x) } (3.9) 그러나 a 의 모든 우멱지수는 같은 최소다항식을 갖기 때문에 식 (3.9) 는 다음과 갇이 표현된다. g (x) = LCM.{ m 1 (x) , m.i (x) , …, 11Zit- l (X) } (3.1 0 ) 이는 부호다항식 c(x) 가 a,a 3, · · ·,a21 - 1 을 근으로 가질 때 한해서 부호어 가 된다는 것을 의미하며 각 최소다항식의 차수는 m 이하이므로 g (x) 의 차수는 m t 이하가 된다. 따라서 BCH 부호는 mt 이하인 검사 디지트 수 를 갖는다 .. 죽 n-k£,_mt . [예제 3. 디 생성다항식이 g (x) = m1 (x) ms (x) ms (x) (3.1 1 ) 인 3 중 오류정정 (31,16) BCH 부호를 생각해 보자. a 를 표 2.1 에서 주어

전 GF(25) 의 원시원이라 할 때 a, a3 , a5 에 대응하는 최소다항식들은 표 2.1 을 이용하여 다음과 같이 쉽게 구할 수 있다. m, (x) = (x+a) (x+a2) (x+a4) (x+ 군) (x+a16) = l +x2+xs 같은 방법으로 ms(x) =1+x2+x3+x•+x5 ms(x) =1+x+ 났 +x•+x5 식 (3.11) 에 이들 m;(x), i =I,3,5 를 대입하면 g( x) =I+x+ 났 +x3+x5+x 나갔 +x9+x10+x11+x15 (3.12) 가 된다. 생성행렬 G 를 만들기 위해서 x15+’ 를 g (x) 로 나누면 x1s+i =q; (x)g ( x) +P; (x) 또는 C;(x)=p ;( x)+x15+i , O~i ~ 15 (3.13) 가 되고 이들 16 개의 부호다항식을 16X31 행렬의 행으로 배열함으로써 조직형 생성행렬을 얻을 수 있고 이는 다음과 같다. 1111010111110001000000000000000 0111101011111000100000000000000 0011110101111100010000000000000 0001111010111110001000000000000 1111101010101110000100000000000 1000100010100110000010000000000 1011000110100010000001000000000 1010110100100000000000100000000 G= 0101011010010000000000010000000 (3.14) 0010101101001000000000001000000 0001010110100100000000000100000

000010101~010010000000000010000 1111000010011000000000000001000 0111100001001100000000000000100 0011110000100110000000000000010 1110101111100010000000000000001 따라서 이 부호의 부호어는 정보벡터 d= (rk, d1, …, d15) 가 주어졌을 때 c= (co, C1, C2, …, c30) (3.15) = (do, d,, d2, …, d,s) • G 에 의해 얻어진다. 이때 식 (3.15) 에서 생성행렬 G 는 식 (3.14) 로 주어진 다. 예를 들어 d(x) =1 이라 하면 부호어는 c(x) =I+x+x2+x3+x5+x1 +x 나갔 +x10+x11+x15 이 된다. 식 (3.15) 를 이용하여 3 중 오류정정 (31,16) BCH 부호의 병렬부호기를 설계하면 그립 3.1 과 같다. a;, 1 같b, 2 t가 c(x) 의 근이면 c(ai) =Co+c,(ai) 1+C2(a;)2+ ... +en 一 I(a;)n~1=0 이 되고 이는 다음과 같이 행렬 형태로 표현할 수 있 다.

d(x) { l .: | ,,,, 기 EX•••- 0 R ••• >/ ` fc (x)

그림 3.1 3 중 오류정정 (31,16) BCH 부호의 병렬부호기에 대한 불럭도

(a'.) ° (ai) I (co,C1,C2,… , Cn-1) ./ (ai) 2 /=O, l~i ~ 2t (3.16) (ai) n-1 식 (3.16) 은 c = (co, c,, C2, …, Cn-1) 이 t증 오류정정 BCH 부호의 부호 어이므로 c •HT=o 인 관계가 성립함을 나타낸다. 따라서 이 부호의 검사 행렬 H 는 H=[(a i )o(a i )'(a i )2 … (a i )n 기] , 1 같 £2 t (3.17) 로 되고 H의 각 요소들은 GF(2 기의 원소들로 구성된다. 식 (3.17) 에서 a 의 멱둘은 2 t차원 열벡터로 표현되며 길이가 2 t(또는 tfo -1) 인 모두 영 이 아닌 H 의 열로 나타내면 다음과 같다. 1 a a2 … an-I 1 a2 (a2) 2 (a2) n-1 H=I I a3 (a3)2 (a3) n-1 (3.18) 1 a21 (a21)2 … (a2t ) n 기 H 의 각 요소를 GF(2) 상의 m 차원 열벡터로 대치하면 이는 BCH 부호 의 2 원 검사행렬 H 가 될 것이다. 그러나 H의 임의의 2 t개 열이 1 차 종 속이 되어서는 안되므로 t중 오류정정 BCH 부호의 최소거리는 적어도 2 t +1 이어야 한다. 따라서 식 (3.18) 로 주어진 H의 2t 이하 어떤 열들의 합도 0 이 되지 않는다. a;, j= 2i ,4 i, …를 임의의 i에 대한 a’의 공액근 들이라 하면 a’는 c(x) 의 근이므로 c(ai) =O 이 된다. 따라서 H 의 우수 행 (even nwnber rows) 은 식 (3.18) 로부터 제거된다. [예제 3. 기 최소거리가 dm;n=1 인 3 중 오류정정 (31,-16) BCH 부호를 다 시 생각해 보자. 식 (3.18) 과 표 2.1 을 이용하면 이 부호의 검사행렬 H 는 다음과 같다.

[1 al a2 a3 a4 a5 a6 a1 군 a9 硏 all 硏 a” a” a15 H= 11 aJ as a9 a12 a1s at e a21 a2• a21 alo a2 as 간 a11 au 1 as a10 a's a20 a2s alo a' 건 au a19 a2• a29 al 군 a13 aa1lBs aa1213 aa21Be a#1 9 aa210 aa2l12 ad22 aa2232 aa2z7• aa 2s aa26s aa2l1l aa216e aa2 이9 a니30 a11 azo a23 a2s a29 a a• a1 a10 at l a1s a19 a22 a2s a2e (3.19) 식 (3.19) 의 모든 요소는 Galo i s 체 CF( 안)의 원소들이다. 표 2.1 로부 터 F 의 각 요소는 이에 대응되는 5 비트 열벡터로 대치될 수 있다. 따라 서 이 부호의 검사행렬 H 는 다음과 같은 15X31 행렬로 된다. 1000010010110011111000110111010 0100001001011001111100011011101 0010010110011111000110111010100 0001001011001111100011011101010 0000100101100111110001101110101 1000011001001111101110001010110 0011111011100010101101000011001 H= I o o o o 11 o o 1 o o 11111 o 111 o o o 1 o 1 o 11 o 1 (3.20) 0 1 1 1 1 1 0 1 1 1 0 0 0 1 O· 1 0 1 1 0 1 0 0 0 0 1 1 0 0 1 0 0001010110100001100100111110111 1111010001001010110000111001101 0001001010110000111001101lll101 0101100001110011011111010001001 0001110001011111010001001010110 0011011111010001ooi o 10110000111 3-3 오중 계산 [72) 복호의 첫단계는 수신어 r(x) 로부터 오중 s(x) 를 계산하는 것이다. t

중 오류정 정 BCH 부호를 복호하는데 2 t차원 오중 (sy n drome) 은 s = (s1, s2, …, s21) = r • Hr (3.2 1 ) 로 표시된다. 여기서 검사행렬 H 는 식 (3.18) 로 주어진다. 부호어 c(x) 를 전송했을 때 수신어 r(x) 는 오류 형태 e(x) =ea+e.x+… + en - 1X n- l 로 인해 r(x) =c(x) +e(x) (3.2 2 ) 가된다. 실제로 l/개의 오류가 e (x) = AL)=1! I xh , Obh b n-1 (3.2 3 ) 와 같이 임의의 위치 jA, l~ ,1~l/에서 발생하였다고 가정하자. a, a2, …, a” 가 이 부호의 각 부호다항식의 근이므로 c(ai) = o, I~ i ~2 t가 된다. 따라서 식 (3.22) 은 r(ai) =e(ai) , i= l,2,… , 2t (3. 24 ) 이다. 한편, 오중요소들은 r(x) 를 a- 의 최소다항식 m,,,(x), I~k~2 t로 나 눔으로써, 죽 r(x) =Q1i(x ) m11(x) +s11(x) (3.25) 으로부터 구해진다. 여기서 x=a 일 때 나머지 (remain d er) s,.(a) 는 mk( 간) =0 으로 인해 오중요소 (s yn drome comp on ent) s,. 가 된다. 그러 므로 일반적으로 r(a i)를 계산한다는 것은 s,.(a;) 를 계산하는 것과 일치 한다. 따라서 식 (3.24) 와 함께 오중요소는 s,.=s,.( 건 )=r(a)=e(a), l~k~2t (3.26) 와 같은 관계식으로 표현된다. 식 (3.26) 로부터 오중 s 는 오류형태 e 에 의존함을 알수 있다. [예제 3.3] 3 중 오류정정 (31, 16) BCH 부호를 행각해 보자. 모든 요소

가 영인 부호계열 c(x) 를 전송했을 때 수신계열이 r(x) =x2+x11+x” 이 라 하면 2 t =6 이므로 이에 대응되는 오중은 s=(sI,S2,S3,s4,s5,S6) 와 갇 다. 한편, 예제 3.1 에서 구한 최소다항식은 각각 m1 (x) = l+x2+x5, ma(x) =l+x2+x3+x•+x5, ms(x) =l+x+x2+x 나갔이므로 r(x) 를 m1(x) 로 나눈 나머지는 ,1(x)=1+x+x2+ 났가 되고 이때의 오중요소는 S1 = ,1 (a) = l+a+a2+a3=a23 S2= 11 (a2) =1 +a+a2+a3+a4=a15 s.= ,1 (a 이 = a+a•=a30 로 구해진다. 같은 방법의 의해 r(x) 를 1n3(x) 로 나눈 나머지는 r3(x) = 1+x+/ 가 되어 x=a3 과 군에 대한 오증요소는 각각 S3 = r3 (a3) = 1 + a+a2= a11 s6 = r3 (a5) = 1+a2+a•= a22 이다. 끝으로 r(x) 를 ms(x) 로 나눈 나머지 rs(x) =l+x+ 갔으로부터 ss=rs( 감) =1+a+a3+a'=a11 가 된다. 따라서 구하고자 하는 6 차원 오중은 s = (a23,a1s,a11,a3o,a16 ,a 22) 와같다. 3- 4 BCH 복호 BCH 부호의 복호에 관한 알고리즘과 기법은 1964 년 이래 여러 편의 논 문이 발표되었지만 각 복호기법은 정정 가능한 오류의 갯수에 따라 장단 점을 지니고 있다. 식 (3.26) 에서와 같이 각각의 오중요소 s& 는 오류형태 e(x) 를 x=a 에서 계산한 값과 같다• 따라서 이는 GF(2m) 의 원소로 표현된자. 11(1

스J.1스t)개의 오류가 미지의 위치 jU J.2, …, j ll 에서 발생했다고 가정하자. 그러면 오류형태는 e (x) = LII! xi, , O~h~n-1 (3.27) A= I 가 된다. 식 (3.26) 과 (3.27) 로부터 오중요소는 s,,= A2=! I (간)j A= A2= I (aj A) k= A2= I (8A) k (3.2 8 ) 이 되며 이 식은 오중요소 Sk, l~k~2t와 오류위치번호 /3A =aJA , l~ ,-l 스 v 간의 결합된 방정식 집합을 만든다. 죽 s1 = ~µ /3A A= l S2 = Lu! (/3A ) 2 (3.2 9 ) A= l :. S2 t = L”! (/3A ) 2t A= l 이러한 2 t개의 방정식을 오증방정식 또는 멱합대칭함수라 한다. BCH 부 호의 복호기법은 이러한 오중방정식을 푸는 방법과 오중요소로부터 오류 위치번호 a1•, ,.\=1,2,… , v 를 찾아내는 것이다. 四죽t인 오류가 발생했다 고 가정하자. 오류위치다항식은 6(x) =야+아 x+ 아갔+… Gux = (1+P1x) (1+/3 ix ) …( 1+P11x) (3.3 0 ) 이며 이때 오류위치번호의 역수가 근이 된다. 식 (3 . 30) 에서 계수 6,, 0~ 로 v 는 오류위치번호의 기초 대칭함수로 주어지며 다음과 같다. ~=1 II 아 =Ei= 8l i 야= viE=- 1l B iB i+ 1 (3.3 1 ) : (J11 = /31 & …/311

여기서 /3，는 a(x) 의 근 /3 ;1 의 역수가 되는 ai i, O~ i ~v 이다. 위 BCH 복호를 위한 주요 단계는 다음과 같다. 1) 수신어 r(x) 로부터 오중 s 를 계산 2) 오중 s 로부터 오류위치다항식 a(x) 의 계수 a 를· 결정 3) a(x) 의 근을 구함으로써 오류위치번호 /3;, O~ i ~v 를 결정 4) 오류위치번호가 나타내는 위치에서 r(x) 의 오류를 정정 다음 절에서는 이미 발표된 여섯 가지 다른 복호법에 대해 설명하고 이에 따른 적절한 예를 둘어 본다. 3-5 Pete r son, Gorenst ei n , Z i erler 의 직 접 복호기 (28) 2 원 BCH 부호에 대한 Pet er son 알고리즘 (1960) 은 Gorens t e i n 과 Zie r ler (1961) 에 의해 비 2 원 BCH 부호로 확장되었다. 그러면 이 절에서는 BCH 부호뿐만 아니라 Reed-Solomon( 이하 RS) 부호의 복호에도 적용할 수 있 는 일반적인 경우에 대해 고찰한다. l/ be t이고 계수들이 O(zero) 이 아닌 오류다항식 e(x) =ea+e1x+… +en - 1Xn-l 은 j A(1 스 A 스기 위치에서 오류가 무작위로 발생하였다면 e (x) = e;1x'1 + e;.x12+ … + eju xIv (3.32 ) 이 된다. 여기서 e j A 는 jA 위치에서의 오류치 (error value) 라 한다. 실제로 2 원 BCH 부호의 경우는 e;;=1 이 되지만 RS 부호와 같은 비 2 원인 경우에는 오류위치 x'A 와 오류치 e;A 를 모두 계산해야만 한다. 일반적으로 오증요소 S 1,는 수신다항식 r(x) 로부터 구해지며 k=l 일 때, S1 은 s1 = r(a) =e (a) = e;. 건 + ej2 aJ 2 + … + eju aJI J (3.33) = Y1f3 1 + Y2& + … + Yl) /31) 가 된다. 여기서 f3A =aJA , 1 스 A 스y는 오류 위치 번호이고 YA=e;A, 1 스 A

~v 는 오류치를 나타낸다. 일반적으로 오중요소 Si ,., l~k~2 t는 s.=r(a 시 =e(a시 = Y1f1 ~+ Y2 않+…+ YJ 3t, l tt,_k tt, _ 2t (3.34) 가 되며, 식 (3.34) 로부터 미지수 8A 와 YA, 1 스 A 스 U 를 갖는 간개의 방정 식은 다음과 같다. s1 = Y1/3 ; + Y2!3 i + •• • + Yv /311 S2 = Y1/3 ?+ Y2/3 g+ … + Y11/3 t ss := Y1/3 ~ + Y2 /:3방 + … + Y11/:3 1 /3 (3.35) S21= Y1 /3안+ Y2 /3점나 .. + y碑 식 (3 . 35) 의 연립방정식을 풀어 적어도 하나의 해를 구해야 한다. 오류위치다항식 a(x) 가 6(x) =1+ 아 x+ 야갔 +···+6 /,I x /,I = (1 +/31x ) (1 +gx ) … (1 +/3/,Ix) (3.3 6 ) 일 때, 식 (3 . 36) 의 양변에 Y7 f3?+＂를 곱하고 x= f3 r1 라 놓으면

S11< J.,+ s11+ 1< J11 - 1 + … + S211 - 1 아 = -S 211 로 되며 이 식은 a(x) 의 계수와 오중이 결합된 선형연립방정식으로 New t on 의 항등식이라 한다. 식 (3 .4 0) 을 행렬식으로 표현하면 SS12 SS23 SS43 •• •• •• SS1 111 - 1 SS1 111 + 1 a61II1 -1 I= I -—s1S11+1 +12 (3.4 1 ) S11S11+ 1 S11+ 2 ••• S211- 2 S211- 1 아 -s2v 또는 :6I: I =M I 〔l—s二2l / 一 (3.4 2 ) 와 같다. 여기서 S1 S2 S3 ••• S11-1 S11 M= S2 S3 S4 ••• S11 S11+ 1 (3.4 3 ) S11 S11+1 S11+2 ... S211-2S211-1 이다. 따라서 a(x) 의 계수 야, l~ i ~II 는 M 이 비특이 (nons i n gul ar) 일 경 우 이에 대한 역행렬로부터 구할 수 있다. 복호알고리즘을 적용할 첫번째 과정은 식 (3 .4 1) 로부터 실제로 발생한 오류의 갯수 J/를 결정하는 것이다. 만일 t=J/이라면 오증행렬 M 은 비특 이가 되나 J/

반복하여 |Ml ct= o 이 되는 u 값을 구해야 한다. 식 (3 .4 3) 에서와 갇이 우선 M 의 역행렬을 구하여 6,, 1 스”다를· 결정 한다. 그다음 오류위치다항식 a(x) 를 구하여 오류위치번호를 결정하기 위해 a(x) 의 근을 구한다. [예제 3 . 산 생성다항식이 g( x) =1+x+x2+x3+x5+x7+x8+x9+x10 +Xll+XIS 인 3 중 오류정정 (31,16) BCH 부호에 대해 생각해보자. 복호 알고리즘을 수행하기 위해서는 우선 오중요소를 다음과 같이 계산하여야 한다. 모든 요소가 영인 부호다항식 c(x) 에 대한 수신다항식이 r(x) =x +x12+x2s 이라 하자. 결국 이는 오류 다항식 e(x) 와 갇고 예제 3 . 1 로부 터 a,a3 과 a5 에 대한 최소다항식은 각각 다음과 같다. m1 (x} =1+ 갔 +x5 11¾ (x) = 1+X 탸갔 +x•+x5 ms(x) =l+x+x2+x 나갔 오중요소는 r(x) 를 최소다항식 m.(x), k=l,3,5 로 나눈 나머지이므로 결국 오중요소는 s1 = I +a2+ a'= a22 s2=I+a'+a8=a13 S3 = 1+a5+a9= a10 s, = 1+as+a1s= a2s Ss = a10+ a1s = a12 Ss = 1 + a12+ a1s = a20 와 같이 쉽게 구해진다. 따라서 r(x) 의 오중은 s = (a22, a1a, a10, a2&, a12, a20) 이 된다. 그리고 그립 3.2 는 이 부호의 오중계산회로이다. 이제 앞에서 언급했던 바와 같이 Pete r son 알고리즘을 적용하기 위한 오류위차다항식

S,

그립 3.2 (31,1 6 ) BCH 부호에 대한 오중 계산회로

M = _Si525_S2SSS s_s &&—— slsa_ 22a13aaI 130al 2a0 a106a - 26 a12 - 一 이 되며 M 의 행렬식은 IMI=[ aa1232 硏a1 3 aa1260〔 국 13+a12+a7+a30=a7 a10 a26 a12 이므로 영이 아니다. |Ml -:t: o 이기 때문에 11=3 은 정확한 값임을 알 수 있 다. 다음은 M 의 역행렬 M-1 을 구하는 것으로 M 됴?〔 ;:3 ::: ::: ]=[::4 ::6 :::] 이 된다. 따라서 식 (3 .4 2) 로[부:터] = M [:: ] =[:::: : ::: ::}[::,] 가 되어 오류위치다항식 a(x) 은 다음과 같이 표현된다. <1( x) =l+a22x+x2+a1x3 (3.4 4 )

a(x) 의 근을 구하는 데는 두 가지 방법이 있는데 하나는 GF(2 키의 모 든 근 ai , O !f.. i!f.. 30 을 식 (3 .4 4) 에 대입하는 것이고 다른 하나는 Chie n 의 담지법에 의한 것이다. 그러므로 a(x) 의 근은 위 방법 중 하나를 택 하여 구하면 a30,a19’ 간뿐이며, 오류위치번호는 이 근들의 역수이므로 1/a3o=a, 1/a'9=a'2, 1/a6=a 2 s 가 된다. 따라서 오류형태는 이 부호가 2 원 부호이므로 오류치가 〈1 〉이기 때문에 e(x) =x+x12+x25 가 됨을 알 수 있다. [예제 3.5 ] (31,16) BCH 부호를 이용하여 2 중 오류롤 정정하는 경우에 대해 생각해보자. 전송된 부호다항식이 c(x)=O 이고, 수신다항식이 r(x) ＝갔 +x28 이라면 x5 과 x28 위치에 두 개의 오류가 발생한 것이다. 식 (3.3 4 ) 로부터 오중은 다음과 갇이 구해 진다. S1 = r(a) =as+a2s=a11 s2=r(a2)=a3 S3=r(a3) =a15+a22=a6 s.=r(a•)=a6 ss = r(as) =a2s+a11 =a S6= r( 감) =al2 이때 11=2 라 놓으면 식 (3 .4 3) 로부터 M =[:: ::]=[::길 가 된다. 또한 IMI=a23+as=as 이므로 M 의 역행렬 M-1 은 M 기 =事 :1: ]=[:29 :::] 이다. 식 (3 .4 2) 로부터 오류위치다항식

[:]=[:29 :::] • [::]=[::7] 따라서 오류위치다항식은

A

그림 3.3 Ch i en 의 담지회로

환기의 출력은 〈 1 〉이며 버퍼레지스터에서 출력되는 rn-1 디지트를 복호한 후 다시 ak 국농산기를 동작시켜 그. 합을 검토한다. 만일 합이 〈 O 〉이면 버 퍼레지스터에서 나오는 오류 비트 rn-2 는 2 원 변환기에 의해 정정된다. 따라서 탐지회로는 이런 방식으로 수신어를 버퍼레지스터 출력으로 완전 히 읽혀질 때까지 바트 대 비트 단위로 r(x) 를 복호한다. [예제 3. 이 다시 3 중 오류정정 (31,16) BCH 부호에서 c(x) =O 일 때 r (x) =x+x12+x2s 인 경우를 생각해보자. 예제 3 .4로부터 오류위치다항식 은

입력

그림 3.4 3 중 오류정정 (31,1 6 ) BCH 부호에 대한 Ch i en 의 탐지회로

이므로 다음과 같이 a, a2, a3 을 곱하는 세 개의 승산기가 필요하다. a/3 =b .+boa+ (bi +b.) a2+/; za 3+baa• a2/3 =& +b.a+ (bo+ba) a2+ (b1+b.)a 나 &a4 a3/3 =& +&a+ (l;z +b.) a 나 (l;z+ ba) a 난 (bi +b.) a• 이 세 가지 승산울 이용하여 3 중 오류정정 (31 .16 ) BCH 부호에 대한 Ch i en 의 탐지회로를 장치화한 것이 그립 3 .4에 나타나 있다. 한편, a(x) =l+a22x+x2+a1x8 의 근을 구하는 데는 대입법 (substi tu-

tion me t hod) 이 있다. 이는 GF(25) 의 원소 air , l~k~31 을 a(x) 에 대입 하여 a(ak) =O 을 만족하는 근을 찾는 것으로 이 경우는 a6, a”, a 임을 알 수 있다. 따라서 오류위치번호는 이 근들의 역수를 취함으로써 쉽게 구해지며 각각 a2s, a12, a 이다. 그러므로 오류형태는 e(x) =x+x12+x1s 가 되고 이 오류형태 e(x) 에 수신다항식 r(x) 를 더함으로써 모든 성분 이 영인 전송된 부호어를 얻을 수 있다. 3-6 Ch i en 의 직 접복호법 (13) Ch i en 에 의해 제안된 직접복호법은 3-5 에서 설명한 Pe t erson 의 방법 과는 약간 다르나 여러가지 면에서 어느 정도 유사한 점이 있다. 수신다항식 r(x)=ro+r1X+ … +Yn-1Xn-l 로부터 오증요소(또는 멱합) S ; 는 S;=r(ai) , i= l,3,S,… ,2t - 1 (3.4 7 ) 가 되므로 오류위치다항식 a(x) 의 계수(또는 기초대칭함수) 야, k=l,2, …, t는 오중요소 s i로부터 계산할 수 있다. sl· 로부터 야를 구하기 위해 서는 2 전 BCH 부호에 대한 Ne wt on 의 항등식이 필요하며 이는 다음과 갇다. S1+ 아 =O S3+ 아 S2+~S1+ 야 =O (3.4 8 ) S5 + 아 s, + ~S3 + 야 S2 + <1,S 1 + as =O 여기서 a,., k=l,2,… , t는 미지수이다. 식 (3 .4 8) 을 다시 행렬로 표현하 면 A ··< J = B (3.4 9 ) 이 되며, 여기서

1 。 。 ... 0 S2 S1 1 ... 0 A=I s, S3 S2 ... 0 (3.50) S2t - 2 S2 t一 3 Sz t-4 ••• St - I 아 S1 6 = 68 B=I SS3s at S21-1 이다. 행렬식 |A| 이 영이 아니면, 식 (3 .4 9) 는

임을 알 수 있다. 그러므로 야, k=l,2, …,t는 야=―I'A1 lli.-!J<_ ; ;' l A i ,kS2 i-lt k= l,2,… ,t (3.'.5 3 ) 으로 표현되며, 여기서 A;,,., l~k~ t는 |Al 의 여인자 (co fac t or) 이다. a(x) 를 오류위치다항식이라 하면 a(x) =1+ 아 x+ 아갔+… +6 갑 = (1 +/3ix) (l +Szx) … (1 +/31X ) (3.5 4 ) 이 되며 a(x) 의 근을 찾는 한 가지 방법은 a(a•) =o 이 되도록 모든 원 소갑를 대입하는 것이다. 이것은 다음 식들 중 a(a)=O 을 검사함으로 써 가능하다.

.Ll,=t !I iL=t !I A ;,1,.S 2i -!+ IAl=o (3.57) 이 되며 식 (3.57) 을 전개하면 다음과 같다. (A1,1 + A1.2 +… +A1,1) S1 + (A2,1 +A2,2 +… + A2,1 ) S3 +…+ (A1,1 +A1,2 +… +At ,t) S2 t- l =IAI (3.5 8 ) 따라서 젊 접 A;, 1t S2 i-1 +IAl=IAI+ (A1,1 + A1,2 +··· +A1,1) S1 + (A2 .1 +A2.2 +… +A2,t) s3+… + (A1,1 +A1.2+ · .....+ A,.,) S21- 1 =0 (3.59) 임을 알 수 있다. 이제 식 (3.59) 가 행렬식 4 를 0 으로 놓은 것과 정확히 같다는 것을 보이자. 죽 1 11s1 0 ·~··1 00 ~~

S2 S1 1 。 +…+ S:.4 S3 S2 。 =A1.1+A,.2 +… +A1,1 S21- 2 S2t _ 3 S2t - 4 … S t L13 = A2.1 + A2.2 + …+ A2,t : 42t - 1 =Am+At ,2 +… + At ,t 이다. 4,. i =0,1,3, … ,2 t― 1 를 식 (3 . 60) 에 대 입하고 식 (3 . 58) 을 이용 하면 LJ= IAl+s, (A,.,+A1.2+… + A,.1) +S3(A2,1+A2 ,2+… A 교 +… +s21-1 (A1., +A1,2 + … + At ,t ) =o (3.61) 이 됨을 알 수 있다. 식 (3.59) 와 식 (3.60) 을 비교하면 LI= k~I= l i~=t lA i , kS 2i - 1+IAl=o (3.62) 이 입증된다. 이러한 오류정정 과정과 장치화는 다음 예제를 통해서 상 세히 설명한다. 〔예제 3 기 t =3 인 (31,16) BCH 부호의 복호기를 앞에서 설명된 직접 복호법을 이용하여 설계해 보자. 식 (3.60) 에서 t =3 일 경우 4 는 다음과 같다. 1 111 01 01 LJ= I S1 S3 S2 S1 Ss S4 S3 S2 = S1S2 + S3 + s!s2 + S1Ss + S1S 웅+ S1S4+ S2Ss + Ss + S1°S 2 S3 +sis . +si+ S 1Ss 식 (3.28) 로부터 s2=s i이고 s,=s t이므로 4 는 LJ= (1+ s1 +sn s~+ (l+ s1+sf+ sf+ S s) Ss+ (l+s1) Ss

가 된다. 수신어가 r(x) =:x +x12+x2s 인 경우, 오중요소 S1, S2, … s2 t는 각각 S1 = r (a) = a+a12+a25= 1 +a2+ a4= a22 s2 = r (a2) = sf = a13 S3= r(a3) =a3+a5+a13= 1+a•= a10 s.= r(a•) =s 덩 =a26 (3.63) Ss = r (a5) =a5+ a29+a= a+ a2+a3= a12 s6= r (감) = s:= a20 이다. 이제 4=0 인 조건을 만족하는지 검사하는 것이 필요한데 다음 표 에 의해 오류위치 x,x12,x2s 에서 4=0 임을 검사할 수 있다. 위치번호 31 30 29 28 27 26 25 24 …1 3 12 11 …2 1 0 SI a22 a23 a a25 a26 a27 a28 a29 a9 al0 aII a20 a21 a22 Sa a10 a1s a1s a'g a22 a2s a2s 갑 a5 군 a• a1 a10 Ss a12 a17 a22 a27 a a6 aII a16 …a 9 a a” …a 2 a7 al2 우선 위치번호가 25 인 경우 s1=a28, Ss=a28, Ss=a11 이므로 4 의 값 은

L1 = (l + a21 + a63) as3 + (l + a21 + a•2 + as3 + a1) a1+ (l + a21) a1 =a11+a1o+a=O 이 된다. 따라서 x 역시 오류위치이므로 오류형태는 e(x) =x+x12+x25 가 됨을 알 수 있다. 이제 (31,16) BCH 부호의 복호기를 구성해 보자. 식 (3.50) 을 이용하여 t= 3 또는 2 인 경우 행렬식 |Al 는 1s0sS 0S1 s A = 24 13 2 = S1 S2 + S3 = sf + S3 가 된다. 만일 IAl =l= O 이면 두 개 또는 세 개의 오류가 발생한 것이 되는 데, 그 이유는 S; 가 t= 3 또는 2 인 서로 다른 근의 멱합이기 때문이다. 이런 경우에 복호를 하기 위해서는 4=0 인지를 검사해야 한다. 죽 1 1 1 1 LJ= I S-1· 1 0 0 I =O 또는 *O S3 S2S1 1 Ss S4 S3 S2 IAl=o 이면 s i가 t -2=1 의 멱합이므로 단일오류 또는 오류가 발생하지 않았음을 알 수 있다. 이 경우 역시 |Al:::/=0 일 때와 마찬가지로 L1=0 인지 룰 검사한다. 4= Sl : I =s1+1=0 또는 *O 따라서 이상에서 언급한 복호법에 의해서 (31,16) BCH 부호의 복호기를 구성하면 그립 3,5 와 같다.

)(cx

로 회호복 접직 한대 에 호부CH B 31(1,) 6 , 3. 립그

3-7 Berlekamp 알고리즘에 의한 BCH 부호의 복호 Pete r son(3-5) 또는 Ch i en(3-6) 이 제안한 직접 복호법은 오류정정 능력 t가 5 보다 적은 오류형태의 경우에 이상적이며 적합한 복호방법이다. 이 기법은 오류위치다항식을 구하는 Berlekam p의 반복알고리즘을 사용하지 않고 오 중 으로부터 직접 오류위치번호를 구하도록 설계되어 있다. 그러 나 많은 오류 를 정정해야 할 경우 이 직접 복호법은 계산해야 하는 승산 과 제산의 횟수가 많아지기 때문에 복잡하고 비효율적이다. 이 철에서는 Berlekam p가 제안하고 Masse y와 Pe t erson 이 발전시킨 일반적인 반복알고리즘을 소개한다. 3-7-1 Berlekam p의 반복알고리 즘 (3 1( 72) 오류위치다항식을 구하기 위한 방법으로 Berlekam p의 반복알고리즘을 소개한다. 앞에서 기술한 바와 같이 2 원 BCH 부호어의 경우 오류 형태가 커지면 오중요소로부터 직접 a(x) 의 계수를 구하는 방법이 비현실적임을 알 수 있다. 그 대신 1967 년에 Berlekam p가 발전시킨 반복알고리즘을 채택하는 것이 보다 효과적일 것이다. 직접 복호법꽈 마찬가지로 이 방 법은 정정해야 하는 오류의 수가 증가함에 따라서 계산은 복잡해지나 어 떠한 오류형태에도 적용시킬 수 있다는 장접이 있다. 오류위치다항식 · a(x) 의 최소해를 구하는 문제는 반복과정을 수행하는 것으로 반복되는 각 단계마다 이 알고리즘은 반드시 New t on 의 항등식을 만족하는 계수를 갖는 최소해와 불합도 (d i scre panc y)와 연관된 교정항 (correcti on ter m) 을 유지 해 야만 한다. 이제 Pe t erson 이 발전시킨 Berlekam p의 반복알고리즘을 기술하면 다 음과같다. 1. 초기 조건 a<-1>(x) =l, l-1=0, d-1=1

(x)=a(x), ln+ 1 =ln 3. dn -=l= O 인 경우, 6(n)(x) 를 구하기에 앞서 dm -=t= O, 1~m~n 이고 m -lm 이 최대치가 되는 6(m)(x) 를 구한다. 이 6(m)(x) 를 이용하면 6(n+1) (x) = 6(n) (x) —dn dm-lxn-m< Jm ( x) ln+1 = max[ln, lm + n-m ] 이 된다. 4. dn=O 또는 dn -=l= O 인 경우에 두 경우 모두 n+1 번째 불합도는 dn+l = Sn+2+ Sn+1aln+I)+ …+ Sn+2-ln+ 1(1 / n+\n+I) 이고, 여기서

l1 =max[o, o+o+ 1]= 1 d1 = S2 + S1< 1\ 1> = 0 1-/1=1-1=0 2 단계 6(2)(x) =6(I)(x) =1+a22x h=!1=l 3 단계 d62(3_ =)l ( 2xS=3) +2= S—a2 (<2l 1)\= 2(> x=l) 1— d2d 갑군(J (Ol (X) 2

표 3.1 a(x) 를 구하는 반복 과정 n 6(n)(x) dn In n— ln 一 · 1 1 。 -1 。 1 a22 。。 1 1+a22x 。。 2 1+a22x 1 1 3 1 + a22x + a9x2 。 2 1 4 1+a22x+a9 갔 a16 2 2 5 1+a22x +x2+a1x3 。 3 2 6 1+a22x+x2+a1x3 e (x) =x+x12+X25 로 되고 이 e(x) 를 수신다항식 r(x) 에 더함으로써 전송된 부호다항식 c(x) =O 을 얻을 수 있다. 그리고 a(x) 를 구하기 위한 반복 절차를 요약 하면 표 3.1 과 같다. a(x) 를 구하기 위한 Berlekam p알고리즘은 또 다른 형태로 나타낼 수 있다. 오증 s 의 벡터 성분을 s;= r(a1+i) , O~ i~ 2t -1 (3.64) 로 정의하자. 여기서 r(a1+i) =c(a1+i) +e(a1+ i)이다. a1+i , o;t ;, i;t;,2 t -1 는 c(x) 의 근이므로 식 (3 . 64) 는 s;=e(a1+ i), O£,i £ ,2t - l (3.65) 가 된다. v~L(dm i n 크 )/2 」인 오류가 전송 도중 발생했다고 가정한다. 그래서 j=j1,j2, … ,j ll 울 제의한 나머지 오류 성분은 e;=O 이 된다. 따라 서 오류형태는 e (x) =x11+x12+… + xJII (3.66) 가 되므로 각오중 성분은 s;= (a1H)i• + (ai+ • )h+… + (a1+’)JI I

= 2u! (aI+i) JA, 0~i ~ 2t— 1 (3.67) A= l 로 표현된다. 한편, n 번째 반복시 결정되는 최소다항식 해를 6(n)(x) =1+6\n}x+ a~n)x2 + … +6 i인 Xln 이라 하면 불합도는 dn = sn+ 2n 6}n)Sn-· (3.6 8 ) i= l 가 되며 alnl, 1,f , i,f, ln 는 6(n)(x) 의 계수이다. 또한 dn=O 이면 n+1 번 반복시 동일한 기억 내용을 유지하지만 dn -:t- o 일 때는 정확하게 Sn 을 생 성하도록 6(n)(x) 에 교정항을 첨가한다. Berlekam p에 의 한 또 다른 알고리즘에 대하여 요약하면 다음과 칸다. 1. n=O 일 때부터 다음의 초기 조건으로 시작한다. a<- 1)(x)=1, /_,=o, d-1=1 a<0>(x)=1, lo=O, ~=-1 2. dn=O 인 경우 a=l lnn 일일 때때 4. dn =I= 0 이거나 dn=O 일 때 n+l 번째 불합도는 d1 ,n +1 = S,.n+ 1 + l<~n + l at n+ lS1

이다. 상세한 복호철차를 다음 예제를 통해 알아보자 . [예제 3 . 이 예제 3 . 8 에서 기술한 3 중 오류정정 (31,16) BCH 부호를 다 시 생각해 보자. 위에 기술된 반복알고리즘을 적용하여 오류위치다항식 a(x) 를 구하라. 오중 성분 so=a22, s,=a13, s2=a10, S3=a26, s.=a12 와 ss=a20 을 이 용하면, a(x) 를 구하기 위한 반복 철차는 다음과 같다. 1 단계 n=O 을 취할 때 6(I) (x) = 6(O) (x) 一 dodkolx-ko (J ( k o) (x) 인데 do = So + i2=。 ! l a f 0s 1,, 0 - i = a22 d,,,0=d-1=l 이므로 a lo 이므로 k1=0 。 d,., = s,., + i~= l a}0>s,.o-i = So = a22 d1 = s1 + a1<1>so = a13 + a13 = 0 이다. 2 단계 n=l 을 취할 때, d1=0 이므로 6(2) (x) = 6(1) (x) = 1 + a22x h=l1=1, k,z= k1=o 이며

., d,.2=s,.2+ i~= l 어 ”lS&- i= So=a22 2 d2 = S2 + i~= l a?>S2-i = S2 + a~2>S1 + a~2>So = a•o+ a22,a13= a10+ a4= 1 이다. 3 단계 n=2 를 취할 때, d2 -:f=. O 이므로 6(3) (x) = 6(2) (x) _ d2d g1 x2-k26 山) (x) = 1 + a22x + (a22)-1x2 = l+a22x+a9 균 /3 =max[1,2]=2 이다. 그리고 la > '2이므로 /¾=2 이고 d,.3= sk,+ iZ&= l ai& ) s&-i= s2+ i고=2 l 어 2)s2- i = s2+a\2>s1 =a10+a 도 1 d3 = s 3 + i=i3J l a 13> s 3 -; = s s + a pi s 2 + ag3 )s I = a26+a+a22=0 이다. 4 단계 n=3 을 취할 때, d3=0 이므로 60) (x) = 6(3) (x) = 1 + a22x + a9 갔 l,=ls=2 k,=ks=2

이고 dk‘= sk,+ i2k= ,l a}&)S&-i = S2 +ai2> s1 = a10+ a'= 1 d4 = s4 + i2=4 l a}4)s4-I. = s4 + ai 4)s3 + 6i 4)s2 = a12+ a11+ a19= a16 이다. 5 단계 n=4 를 취할 때, d건 =0 이므로 6(5)(x) =aU)(x)-d4d 갔갔＿바꾼 4)(x) = 1 + a22x + a9 났 + a16 갔 (1 + a22x) = 1 + a22x + 났 + a7x3 k=max[l4, 4— (2 -h)]=max[2,3]=3 이다. 그리고 ls>L 이므로 ks=4 이다. 따라서 dko.= S ko + i~k= •-l a f •s k. 규 4 = s, + i~= l 어 4)s4- i = al2+ 6i 4)s3 + o&4)s2 = a16 d5 = s5 + iZ=5 l 6{5)s5 기 = s5 + 6i 5)& + 6i 5)s3 + 6i 5)s2 = a2o + aa + a2s + a11 = o 이 된다. 6 단계 n=5 를 취할 때, d5=0 이므로 6 번째 반복에서 최소차 다항

표 3.2 a(x) 를 구하는 반복 과정 n 6(n)(x) ln dn kn dkn -1 。 1 。 1 。 a22 -1 1 1 1+ a22x 1 。 。 a22 2 1+ a22x 。 a22 3 1+a22x+a9 났 2 。 2 1 4 1+ a22x + a9x2 2 a16 2 1 5 1+a22x+x2+a7x3 3 。 4 al6 6 1+ a22x +xz+ a1xl 식은 결국 a<6>(x) =a(x) =l+a22x+x2+a1x3 으로 구해지며, 이 식이 바로 오류위치다항식이며 예제 3 . 8 에서 얻은 해 와 동일하다. a(x) =a(6)(x) 의 근은 a6 , a19, a” 이므로 오류위치번호는 각각 a25' a12, a 가 된다. 그러므로 오류형태는 e (x) =x+x12+X25 이며 결국 복호기의 출력은 c(x)=r(x)+e(x)=O 가 되어 복호가 완료됨 을 알 수 있다. 이 부호의 a(x) 를 구하는 자세한 과정은 표 3.2 와 같다. 3-7-2 복호기 의 장치화 BCH 부호의 복호과정을 다음과 갇이 요약할 수 있다. 1, 수신어 r(x) 로부터 오중 S=(So,S1, … ··,S 2t)를 계산한다. 2. 반복알고리즘을 이용하여 오중요소 S;, 1£. i £.2 t로부터 오류위치다 항식 a(x) 를 구한다. 3. a(x) 의 근을 구함으로써 오류위치번호를 결정한다. 4. 오류형태 e(x) 를 결정하고 c(x)=r(x)+e(x) 에 의해 오류를 정정

입력