Homepage of Coding Theory

(Error Correcting Codes and Combinatorics)

Hong-Yeop Song (Yonsei University, Seoul, Korea)

서론

오류정정부호이론은 디지털 통신 시스템의 중요한 한 부분인 채널코드에 대하여 연구하는 분야입니다. 채널코드의 목적은 적당량의 추가정보를 송신데이터에 덧붙여서 채널에서 발생하는 오류를 정정하고자 함에 있습니다. 크게 분류하면 block code와 trellis code로 나눌 수 있습니다.

블록 부호(block code)는 일정한 길이의 송신데이터 비트 (예를 들어 k 비트)에 r 비트의 추가비트를 삽입합니다. k+r=n이라 두면 k비트의 정보를 보내기 위하여 n비트의 부호어를 보내게 됩니다. 베이스밴드 송수신인 경우와 달리 변조가 필요한 경우 이를 반송파에 실어 보내는 과정을 디지털 변조과정이라 합니다. 수신기는 디지털 복조과정을 거쳐서 수신 부호어를 결정하고 이를 복호하여 송신부호어를 추출합니다. 제대로만 이루어지면 여기에서 k비트의 정보를 온전히 추출할 수 있습니다. 문제는 오류정정능력인데, 이를 크게 하고 싶으면 r이 증가해야 한다는 점입니다. 즉, 원하는 오류정정능력을 유지하면서 가능한 조금만 추가비트를 첨가할 수 있다면 가장 좋은 결과를 가져올 것입니다.

트렐리스 부호(trellis code)의 대표적인 예는 흔히 convolution code, 혹은 길쌈부호라고 합니다. 여기에서는 보내고자 하는 송신 데이터 sequence를 블록으로 나누어 처리하지 않고 shift register에 순서대로 입력시켜 몇 가지 혼합된 logic을 거쳐 출력 부호 sequence를 만들어냅니다. 이때, 입력 비트당 출력 비트의 수를 부호율이라 하는데, 대개, 1/2, 1/3, 혹은 1/4 등으로 표시합니다. 이 경우 입력 1비트당 출력 비트의 수가 2, 3, 혹은 4비트인 셈입니다. 오류정정능력을 높이기 위해서는 부호율이 작아져야 하는데, 이점도 중요한 설계 issue입니다. 수신기는 디지털 복조 후에 송신 데이터 sequence를 결정하고 이를 복호하여 원하는 송신 데이터를 추출합니다. 현재 가장 널리 알려져 있는 복호방식은 Viterbi Algorithm입니다. 이는 ML관점에서 최적이라고 증명되었고, 블록부호보다 처리가 간단하여 많은 디지털 모뎀 (디지털 위성통신, 디지털 이동통신)에서 이를 사용하고 있는 실정입니다.

블록 부호의 복호 방식은 부호화방식에 따라 달라지는데, 대표적으로 Hamming 부호, BCH 부호, Reed-Muller 부호, Reed-Solomon 부호 등이 있으며, 이들의 복호방식에 관한 꾸준한 발전이 이루어져 이제는 많이 실제로 사용되고 있습니다. BCH부호의 특별한 경우에 해당하는 Reed-Solomon부호는 deep space satellite communication modem에 길쌈부호와 연결하여 강력한 오류정정능력을 갖춘 직렬연쇄부호로 구성되어 태양계 탐사 위성체에서 각종 사진자료를 전송하는데 이용되고 있으며, 또한 compact disc에 응용되어 고전음악과 rock음악을 망라하여 충실도 높은 저장/재생에 이용되고 있습니다. 향후, 음악뿐만 아니라 영화 등의 영상정보와 기타 문자 데이터를 기록할 DVD등에도 이용하기 위하여 연구/개발 중에 있으며, 수신 신뢰도를 향상시키기 위하여 디지털 라디오방송과 TV방송에도 적용되어 연구/개발되고 있습니다. 문제는 이들의 부호화/복호화 과정을 이해하기 위해서는 꽤 복잡해 보이는 대수학적인 개념을 먼저 이해해야 합니다. 그 이유는, 한 블록의 부호어를 가지고 덧셈과 뺄셈 그리고 곱셈과 나눗셈 등을 수행가능해야 하기 때문이며, 대수학적 기초 개념은 이러한 연산이 정의되는 유한집합에 대한 개념을 이해하는 것으로부터 출발합니다.

앞으로, 이 페이지에 블록부호에 관한 기초적인 내용과 대수학적인 특성에 대하여 기록할 예정이니, 필요한 부분을 잘 참조하여서 실제품 설계와 시스템을 이해함에 많은 도움을 받기 바랍니다.

Introduction

Binary (n,M,d) code
Hamming Distance and Hamming Weight
Concept of Error Detection
Concept of Error Correction
Minimum Distance and Error Detection Capability
Weight Enumerator
Minimum Distance and Error Correction Capability
Minimum Distance Decoding is Maximum Likelihood Decoding
Complete Decoding VS Incomplete Decoding
Why coding in Digital Communication Systems
Advantages and Disadvantages of Coding
Hamming Bound
Singleton Bound
Plotkin Bound
Fundamental Problem of Coding Theory
Combining Two Binary codes into One -I
Combining Two Binary codes into One -II

Linear Binary Codes

Linear Binary [n,k,d] code
Generator matrix
Dual Code (= Orthogonal Complement)
Parity check matrix
Binary Hamming code
Dual of Hamming code
McWilliams Identity for Weight Enumerator
Decoding of Binary Hamming code
Standard Array Decoding is Minimum Distance Decoding
Hamming, Singleton, Plotkin Bounds
Gilbert-Varshamov Bound
Fundamental Problem of Linear Coding Theory
Six Modifications to a Linear Binary Code

Cyclic Binary Codes (Linear)

Polynomial Rings
Quotient Rings mod p(x)
Generator Polynomial
Parity check Polynomial
Cyclic Redundancy Check Codes for Error Detection
Meggit Decoder for Error Correction
Hamming Code as Cyclic Code
Example of Meggit Decoder for Binary [15,11,3] Hamming Code for 1-error-correction
Example of Meggit Decoder for Binary [15,8,5] Code for 2-error-correction
Performance(BER) of BPSK+[7,4,3]Hamming over AWGN
Performance(BER) of QPSK+[7,4,3]Hamming over AWGN

Summary : Theory of Finite Fields

Existence and Definition
Additive Structure
Multiplicative Structure
Polynomials over GF(q)
Irreducible Polynomials over GF(2) -- An Extensive Table
Cyclotomic Polynomials
Minimum Polynomials of a over GF(2)
Factoring Polynomials over GF(2ⁿ)
Trace

BCH Codes and Reed-Solomon Codes : Description

Definition
Shortened RS codes
Binary-mapped RS codes over GF(2ⁿ) and its Burst Error Correction Capability

BCH Codes and Reed-Solomon Codes : Encoding/Decoding

Peterson's Algorithm
BerleKamp's Algorithm
Transform Domain Encoding/Decoding of RS codes

Perfect Codes

Definition
Binary Hamming Code is Perfect
Binary Golay code and Ternary Golay code
So far

Optimum Linear Codes

Griesmer Bound and Definition
Some Constructions
So far

Back to Hong-Yeop Song's Home
Back to Coding & IT Lab Home
Back to Engineering School Home
Back to Yonsei Univ. Home