조금은 느리게 살자: 오류 제어용 채널 부호화(Channel Coding for Error Control)

[경고] 아래 글을 읽지 않고 "오류 제어용 채널 부호화"를 보면 바보로 느껴질 수 있습니다.

(a) 집합 형태로 시각화

(b) 비트 배치도

[그림 1] 패리티 비트(parity bit) 3개, 자료 비트(data bit) 4개를 가진 $(n, m)$ = (7, 4) 해밍 부호(Hamming code)의 표현법(출처: wikipedia.org)

통신 경로인 채널(channel)에는 항상 잡음(noise)이 존재하기 때문에 이진 정보(binary information)를 보내면 오류(error)가 생길 수 있다. 채널 전송에 생기는 오류를 검출(detection)하거나 정정(correction)할 때는 채널 부호화(channel coding)를 사용한다. 잡음을 생각하지 않는 원천 부호화(source coding)와 다르게, 채널 부호화는 정보를 담고 있지 않지만 오류 제어에 쓰이는 비트를 인위적으로 추가한다. 채널 부호화에는 오류 검출 부호(error detection code, EDC)와 오류 정정 부호(error correction code, ECC)를 활용한다. 오류 검출이나 정정에 쓰이는 대표적인 부호는 [그림 1]에 소개한 해밍 부호(Hamming code)이다[1], [2]. 해밍 부호는 패리티 비트 혹은 동등성 비트(parity bit)를 써서 오류 검출과 정정을 처리한다. 이진수 비트의 나열에서 패리티 혹은 동등성은 1의 개수를 항상 짝수 혹은 홀수에 맞춘 결과를 뜻한다. 주어진 이진수에 패리티를 담당하는 비트를 하나 넣어서 1의 개수를 언제나 짝수 및 홀수로 조정하면 각각 짝수 패리티(even parity)와 홀수 패리티(odd parity)로 부른다. [그림 1]처럼 통상적으로는 짝수 패리티가 많이 쓰인다. 이를테면 [그림 1]에서 패리티 비트 $p_1$은 $p_1$ = $\text{rem}(d_1+d_2+d_4,2)$로 연산해서 짝수 패리티를 결성한다. 여기서 $\text{rem}(n,2)$는 나머지(remainder) 함수이면서 홀수 판별식(discriminant of odd number)이다. 비슷하게 $p_2$ = $\text{rem}(d_1+d_3+d_4,2)$, $p_3$ = $\text{rem}(d_2+d_3+d_4,2)$를 배정한다.

해밍 부호처럼 채널 부호화에 쓰이는 채널 부호(channel code)를 분류할 때는 부호어(codeword) 비트수 $n$, 자료 비트수 $m$, 여분(redundancy) 비트수 $r$을 조사한다. 여기서 여분은 정보가 없지만 오류 제어에 쓰이는 부분, 부호어는 $n$ = $m+r$과 같이 자료와 여분으로 구성된다. 이를 통해 채널 부호화에 활용되는 여분 $r$과 부호율(code rate) $R_n$을 정의한다.

(1)

여기서 $N$ = $2^n$, $M$ = $2^m$이다. 식 (1)과 같은 특성을 가진 채널 부호는 $(n, m)$ 채널 부호라 이름 붙인다. 예를 들어, 해밍 부호는 패리티가 여분을 담당하므로 [그림 1]은 $n$ = $7$, $m$ = $4$인 $(7, 4)$ 해밍 부호가 된다.

패리티 비트로 오류 정정을 할 때는 모든 패리티 비트를 조합해서 만든 징후(syndrome) 혹은 오류 징후(error syndrome) 개념을 사용한다. 징후는 패리티 비트를 활용해 오류가 생긴 비트 위치를 나타내는 이진수 표현식이다. [그림 1]에서는 $p_1, p_2, p_3$의 짝수 판별식(discriminant of even number)으로 징후를 만든다. 예를 들어, 한 비트에서만 오류가 생긴 경우 패리티 비트의 짝수 판별식과 그 징후는 다음처럼 표시된다.

$d_1$에 오류: $p_1$ = $F$, $p_2$ = $F$, $p_3$ = $P$ $\Rightarrow$ 징후 = 011$_2$ = 3
$d_2$에 오류: $p_1$ = $F$, $p_2$ = $P$, $p_3$ = $F$ $\Rightarrow$ 징후 = 101$_2$ = 5
$d_3$에 오류: $p_1$ = $P$, $p_2$ = $F$, $p_3$ = $F$ $\Rightarrow$ 징후 = 110$_2$ = 6
$d_4$에 오류: $p_1$ = $F$, $p_2$ = $F$, $p_3$ = $F$ $\Rightarrow$ 징후 = 111$_2$ = 7
$p_1$에 오류: $p_1$ = $F$, $p_2$ = $P$, $p_3$ = $P$ $\Rightarrow$ 징후 = 001$_2$ = 1
$p_2$에 오류: $p_1$ = $P$, $p_2$ = $F$, $p_3$ = $P$ $\Rightarrow$ 징후 = 010$_2$ = 2
$p_3$에 오류: $p_1$ = $P$, $p_2$ = $P$, $p_3$ = $F$ $\Rightarrow$ 징후 = 100$_2$ = 4
오류 없음: $p_1$ = $P$, $p_2$ = $P$, $p_3$ = $P$ $\Rightarrow$ 징후 = 000$_2$ = 0

여기서 $P, F$는 패리티 연산(parity operation)의 통과(pass: 짝수 패리티)와 실패(fail: 횰수 패리티)를 뜻한다. 위에 표현된 징후를 이진수로 생각해서, 징후가 나타내는 위치를 그린 결과가 [그림 1(a)]이다. 그러면 징후가 정상적으로 동작하기 위한 부호어 비트수 $n$과 패리티 비트수 $r$의 부등식 관계는 다음과 같다.

(2)