오류 제어용 채널 부호화(Channel Coding for Error Control)

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

1. 재미나는 정보량의 정의

2. 엔트로피로 불리는 평균 정보량

3. 통신을 지배하는 상호 정보

(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)

여기서 징후가 오류 위치를 잘 지시하려면 부호어 개수 $n$과 함께 오류 없음의 상태까지 추가로 나타내야 한다. [그림 1]에 보인 (7, 4) 해밍 부호는 $n$ = $7$, $r$ = $3$이라서 식 (2)의 부등식을 $2^3 \ge 7+1$과 같이 만족한다.

(a) 3비트: 3차원

(b) 4비트: 4차원

[그림 2] 해밍 부호의 기하학적 구성: 같은 색깔은 해밍 거리가 서로 1(출처: wikipedia.org)

[그림 2]와 같은 기하학적 구성으로 $n$비트 해밍 부호를 더 쉽게 이해할 수 있다.

[참고문헌]

[1] R. W. Hamming, "Error detecting and error correcting codes," Bell Syst. Tech. J., vol. 29, no. 2, pp. 147–160, Apr. 1950.

[2] R. W. Hamming, Coding and Information Theory, 2nd ed., Englewood Cliffs, NJ, USA: Prentice-Hall, 1986.

[다음 읽을거리]

1. 채널 용량과 정보 전송의 한계

통신을 지배하는 상호 정보(Mutual Information That Governs Communication)

[경고] 아래 글을 읽지 않고 "통신을 지배하는 상호 정보"를 보면 바보로 느껴질 수 있습니다.

1. 재미나는 정보량의 정의

2. 엔트로피로 불리는 평균 정보량

[그림 1] 통신 채널(communication channel) 관점으로 본 조건부 엔트로피(conditional entropy)와 상호 정보(mutual information)(출처: wikipedia.org)

누구나 아는 확률(probability)과 정보(information)를 연결해서 정보를 정량화하는 정보량(information content) $I(X)$ 개념을 새롭게 만들 수 있다. 그러면 베이즈 정리(Bayes' theorem)에 사용되는 조건부 확률(conditional probability)을 추가해서 정보량에 조건 특성을 덧붙이면 어떻게 될까? 여기에 해답을 제공하는 중요한 인식이 바로 상호 정보(mutual information) $I(x_i; y_j)$이다. 이 상호 정보를 통신 시스템과 연결하기 위해 송신기에서 송신 기호(Tx symbol) 혹은 입력 기호(input symbol) $x_i$를 보낼 때 수신기에서 받는 수신 기호(Rx symbol) 혹은 출력 기호(output symbol)를 $y_j$라 한다. 여기서 송신기에서 수신기로 가는 통신 경로를 채널(channel)이라 이름 붙이고 채널에는 항상 잡음(noise)이 존재한다고 생각한다. 이에 따라 송신 기호 $x_i$는 수신기에서 원래 기호인 $x_i$로 검출되지 않고, 잡음에 의해 기호(symbol)가 무작위로 바뀔 수 있는 수신 기호 $y_j$로 전달된다. 채널 잡음으로 인해 송신 기호 개수 $m$보다 수신 기호 개수 $n$이 대부분 커서 $m \le n$으로 둘 수 있다. 만약 채널에 잡음이 없다면, 정보는 정보원(information source)이 만드는 기호의 평균 정보량인 엔트로피(entropy) $H(X)$에 의존한다. 이 엔트로피는 섀넌의 원천 부호화 정리(Shannon's source coding theorem)에 지배를 받는다. 그래서 잡음이 없어서 보낸 기호 $x_i$가 변함없이 $x_i$로 받아지는 섀넌의 원천 부호화 정리를 무잡음 부호화 정리(noiseless coding theorem)로 명하기도 한다.

이런 조건을 바탕으로 상호 정보(mutual information) $I(x_i; y_j)$는 송신 기호 $x_i$가 가진 정보량 $I(x_i)$에서 수신 기호 $y_j$를 알 때 $x_i$가 가진 조건부 정보량(conditional information content) $I(x_i | y_j)$로 정의한다.

                          (1)

여기서 $p(x)$는 기호 $x$가 나올 확률, $p(x, y)$는 기호 $x, y$가 동시에 나올 확률 혹은 교집합의 확률이다. 상호 정보 $I(x_i; y_j)$에 대비되게 채널에 무관하게 있는 정보량 $I(x_i)$를 정보원의 자기 정보(self-information)라 칭하기도 한다. 상호 정보 $I(x_i; y_j)$는 다음 성질을 가지고 있다.

[상호 정보(mutual information)의 성질]

(a) 대칭성: $I(x_i; y_j)$ = $I(y_j; x_i)$

(b) 상호 정보의 한계: $I(x_i; y_j) \le I(x_i)$

(c) 독립 사건: $X, Y$가 독립일 때는 $I(x_i; y_j)$ = $0$

[증명]

명제 (a)는 식 (1)의 최종 결과가 $x_i, y_j$에 대해 대칭이어서 쉽게 증명된다. 명제 (b)는 정보량과 상호 정보를 빼주면 나온다.

                          (2)

독립 사건에서는 $p(x_i|y_j)$ = $p(x_i)$이기 때문에 $I(x_i; y_j)$ = $0$이 유도된다.

______________________________

상호 정보가 가진 성질로부터 상호 정보는 송신과 수신을 이어주는 채널의 연결도를 의미한다. 상호 정보의 대칭성은 채널이 가역적(reciprocal)이어서 송신과 수신을 바꾸어도 됨을 나타낸다. 채널에서 잡음이 생기면, 보낸 송신 기호가 원하지 않는 여러 수신 기호로 나누어진다. 그러면 실제 측정 가능한 수신 기호로부터 송신 기호를 추정할 때는 결정론이 아닌 확률 과정이 되어서 조건부 정보량이 생긴다. 이 조건부 정보량은 잡음이 커질수록 송신 추정의 무작위성이 증가해서 채널의 연결도를 떨어뜨린다. 반대로 수신 기호로 송신 추정이 잘 되면 불확실성이 크게 감소해서 조건부 정보량은 작아진다. 그래서 채널 연결도를 정량적으로 나타내는 상호 정보를 식 (1)처럼 정립한다. 극단적으로 채널이 전부 잡음으로 가득 찬 전잡음 채널(all-noise channel)에서는 채널이 끊어진 상태 혹은 송수신이 서로 독립인 모습이라서 상호 정보는 0으로 설정된다.

송수신 과정을 확률로 처리할 때는 채널 천이 행렬(channel transition matrix) ${\bf T}(Y|X)$를 도입하면 편하다.

                          (3)

여기서 채널 확률(channel probability)은 $p_{ji}$ = $p(y_j | x_i)$, $y_j$는 상호 배반(mutually exclusive) 및 공동 포괄(collectively exhaustive), 어떤 $x_i$이든지 모든 $y_j$중의 하나에 전달되어서 $\sum_j p_{ji}$ = $\sum_j p(y_j | x_i)$ = $1$[증명은 전체 확률의 법칙(law of total probability)]이다. 채널 천이 행렬의 원소를 $p_{ij}$ = $p(y_j | x_i)$로 선택하는 사례도 빈번하지만, 행렬 곱셈과 짝 맞춤을 위해 $p_{ji}$ = $p(y_j | x_i)$로 선택한다.

송신 및 수신 기호에 대한 평균을 취해서 선험적 상호 정보(a priori mutual information) $I(X; y_j)$와 후험적 상호 정보(a posteriori mutual information) $I(x_i; Y)$를 각각 정의할 수 있다.

                          (4a)

선험적 상호 정보는 수신된 $y_j$를 보고 수신전에 선제적으로 송신된 $x_i$의 평균 상호 정보이다. 당연히 후험적 상호 정보는 이미 송신된 $x_i$를 기준으로 송신후에 경험적으로 수신되는 $y_j$의 평균 상호 정보를 뜻한다. 식 (4a)를 다시 평균해서 시스템 상호 정보(system mutual information) $I(X; Y)$도 만든다.

                          (4b)

시스템 상호 정보는 송수신 채널이 평균적으로 연결되는 수준인 평균 연결도로 쉽게 생각할 수 있다. 식 (4b)에 나온 시스템 상호 정보는 상호 정보와 비슷한 특성이 있다.

[시스템 상호 정보(system mutual information)의 성질]

(a) 대칭성: $I(X; Y)$ = $I(Y; X)$

(b) 양의 시스템 상호 정보: $I(X; Y) \ge 0$

[증명]

명제 (a)는 식 (4b)으로 쉽게 도출된다. 명제 (b)의 증명에는 유명한 기브스의 부등식(Gibbs's inequality)이 꼭 필요하다.

                          (5)

여기서 $\sum_{i,j} a_{ij}$ = $\sum_{i,j} b_{ij}$ = $1$이다.

______________________________

시스템 상호 정보의 최소값은 송수신 기호가 서로 독립일 때 혹은 전잡음 채널에서 0이 나온다. 시스템 상호 정보를 설명하는 발상으로 평균 정보량인 엔트로피도 유용하다. 식 (4a)처럼 선험적 조건부 엔트로피(a priori conditional entropy) $H(Y|X)$와 후험적 조건부 엔트로피(a posteriori conditional entropy) $H(X|Y)$를 수립한다.

                           (6a)

                           (6b)

결합 확률(joint probability) $p(x_i, y_j)$는 결합 엔트로피(joint entropy) $H(X, Y)$도 생성한다.

                          (6c)

                          (6d)

만약 $X, Y$가 서로 독립이라면 결합 엔트로피는 각 엔트로피의 합이다.

                          (6e)

식 (6)을 시스템 상호 정보에 넣어서 새로운 관계식을 제안한다.

[시스템 상호 정보와 결합 엔트로피의 관계]

                          (7)

[증명]

식 (4b)의 로그 함수 내부에 있는 곱셈을 로그 함수의 합으로 분해하고 식 (6)으로 교체한다. 

______________________________

선험적 조건부 엔트로피 $H(Y|X)$는 먼저 보내지는 송신 기호 $x_i$에 대해 수신 기호 $y_j$가 가진 평균 정보량이다. 만약 채널이 잘 연결되어 $X, Y$가 결정론적이면  $H(Y|X)$는 정보량이 없어져서 0이 된다. 반대로 채널이 단절된 독립 조건에서는 $H(Y|X)$는 $H(Y)$와 같다. 이를 시스템 상호 정보와 연결하면, $H(Y|X)$는 송신 기호를 수신기로 보낼 때에 발생하는 채널의 잡음도 혹은 손실도가 된다. 즉, 수신 기호의 엔트로피 $H(Y)$에서 채널의 잡음도인 $H(Y|X)$를 뺀 값은 채널의 연결도인 시스템 상호 정보 $I(X, Y)$가 된다. 다시 말해 수신 기호의 온전한 엔트로피 $H(Y)$에서 잡음으로 인해 발생한 쓸모 없는 선험적 조건부 엔트로피 $H(Y|X)$를 빼야 시스템이 실제로 활용할 수 있는 평균적인 상호 정보가 된다. 이런 이유로 선험적 조건부 엔트로피 $H(Y|X)$를 잡음 엔트로피(noise entropy)로 축약해 부를 수 있다. 시스템 상호 정보는 항상 0보다 크거나 같으므로, 선험적 조건부 엔트로피는 수신 기호의 엔트로피보다 작아야 한다.

                          (8)

다른 관점으로 수신 기호의 엔트로피는 채널 연결도인 시스템 상호 정보와 채널 잡음도인 선험적 조건부 엔트로피의 합이다.

송신 기호의 확률 변수 혹은 송신 확률 변수를 $X_1, X_2$로 두고 $X_1, X_2$가 독립 사건(independent event)이라면, 결합 엔트로피는 각 독립 사건으로 나누어진다.

    (9a)

여기서 $x_{1,i} \in X_1$, $x_{2,k} \in X_2$, $y_{1,j} \in Y_1$, $y_{2,l} \in Y_2$; 수신 기호의 확률 변수 혹은 수신 확률 변수인 $Y_1, Y_2$는 채널을 통과한 $X_1, X_2$로 결정하며, 독립인 $X_1, X_2$는 수신 확률 변수 $Y_1, Y_2$도 서로 독립으로 만든다. 식 (9a)를 식 (7)에 넣어서 독립인 $X_1, X_2$가 만드는 시스템 상호 정보 $I(X_1, X_2; Y_1, Y_2)$를 개별적인 시스템 상호 정보 $I(X_1; Y_1)$과 $I(X_2; Y_2)$로 표현할 수 있다.

                          (9b)

이산 신호(discrete signal)가 아닌 연속 신호(continuous signal)를 다룰 때는 확률 질량 함수(probability mass function, PMF) $p(x)$ 대신 확률 밀도 함수(probability density function, PDF) $p_X(x)$를 이용해서 연속 엔트로피(continuous entropy) $H_c(X)$와 연속 신호의 시스템 상호 정보(system mutual information) $I_c(X; Y)$를 재정의한다.

                          (10a)

                          (10b)

여기서 $X, Y$는 연속 확률 변수(continuous random variable)이다. 이산 채널(discrete channel)의 시스템 상호 정보 $I(X;Y)$에 해당하는 연속 채널(continuous channel)용 제안이 식 (10b)에 재정의한 연속 신호의 시스템 상호 정보 $I_c(X;Y)$이다. 이 상호 정보는 연속 신호가 지나가는 연속 채널이 평균적으로 연결되는 정도를 의미한다.

[참고문헌]

[1] C. E. Shannon, "A mathematical theory of communication", Bell System Tech. J., vol. 27, pp. 379–423, 623–656, Jul., Oct. 1948.

[2] R. W. Hamming, Coding and Information Theory, 2nd ed., Englewood Cliffs, NJ, USA: Prentice-Hall, 1986.

[다음 읽을거리]

1. 오류 제어용 채널 부호화

2. 채널 용량과 정보 전송의 한계

차분 방정식(差分方程式, Difference Equation)

[경고] 아래 글을 읽지 않고 "차분 방정식"을 보면 바보로 느껴질 수 있습니다.

1. 수치 미분

2. 미분 방정식의 의미

[그림 1] 함수 $f(x)$의 차분 모습(출처: wikipedia.org)

임의 수열 $f_n$의 차이를 이용해서 $f_n$ = $a f_{n-1} + b f_{n-2} + \cdots$ 등과 같은 형태로 표현한 수식을 차분 방정식(差分方程式, Difference Equation)이라 부른다. 차분 방정식의 대표적인 예는 등비 급수(geometric series)이다.

                  (1)

여기서 $f_0$ = $a_0$은 초기값(initial value), $r$은 공비(common ratio)이다. 식 (1)은 $f_n$을 기준으로 차분이 하나만 있어서 일계 차분 방정식(the first order difference equation)이 된다. 식 (1)을 확장해서 이계 차분 방정식(the second order difference equation)도 쉽게 생성할 수 있다.

                  (2)

여기서 $a, b$는 상수, $f_0, f_1$은 이미 주어진 초기값이다. 식 (2)를 풀기 위해, 식 (1)처럼 $f_n$ = $r^n$이라 가정한다. 그러면 차분 방정식은 통상적인 2차 방정식으로 간략화된다.

                  (3)

식 (2)의 해법인 식 (3)에 나온 오른쪽 식은 차분 방정식을 규정하는 특성 방정식(characteristic equation)이다. 식 (3)에 나온 특성 방정식을 풀어서 나온 공비를 $r_1$, $r_2$라고 하면, 식 (2)의 일반해(general solution)는 미분 방정식처럼 $r_1^n$과 $r_2^n$의 선형 결합으로 구한다.

                  (4)

여기서 $c_1, c_2$는 초기값으로부터 결정한다.

상미분 방정식(ordinary differential equation)처럼 다음과 같은 형태로 기술된 $m$계 차분 방정식($m$th order difference equation)은 해의 존재성과 유일성이 쉽게 증명된다[1].

                  (5)

여기서 ${\bf x}_{n-1}$은 $m$차원을 가진 수열 벡터(vector), $f_0, f_1, \cdots, f_{m-1}$은 이미 알고 있는 초기값, 초기값 벡터는 ${\bf x}_{m-1}$ = $[f_0~f_1~\cdots~f_{m-1}]$이다. 식 (5)에 초기값 벡터 ${\bf x}_{m-1}$부터 차례로 ${\bf x}_{m}, {\bf x}_{m+1}$ 등을 대입하면, 함수값은 $f_{m}$, $f_{m+1}$, $f_{m+2}$ 등으로 유일하게 나온다. 즉, 식 (5)에 ${\bf x}_{m+k-1}$을 넣으면, $f_{m+k}$가 출력되고 그 다음 입력 벡터 ${\bf x}_{m+k}$도 구성된다. 그러면 $n$ = $0, 1, \cdots, m+k$에 대해 $f_0, f_1, \cdots, f_{m+k}$를 출력하는 함수 $f(x)$를 다항 함수 보간(polynomial interpolation) 등으로 만들 수 있다. 여기서 $f_n$ = $f(x)|_{x=n}$은 $0 \le x \le m+k$에서 성립한다. 그 다음 단계로 $x$의 범위를 늘리기 위해, 이전에 생성한 $f(x)$를 식 (5)에 넣어서 $m+k \le x \le m+k+1$에서도 $f(x)$가 정의되게 한다. 여기서 이전 범위에서 변하는 $f(x)$를 ${\bf x}_{n-1}$의 성분에 대입해 연속으로 바꿈으로써 식 (5)의 좌변은 자동적으로 $m+k \le x \le m+k+1$에서 연속이다. 이 과정은 계속 될 수 있으므로, 식 (5)의 차분 방정식은 항상 해를 가진다. 식 (5)와 같은 차분 방정식의 해가 유일하다는 증명도 쉽다. 만약 $n$ = $k$부터 $f(k)$와 함수값이 다른 $g(k)$가 있다고 가정한다. 그러면 식 (5)에 따라 $g(k)$ = $F({\bf x}_{k-1})$ = $f(k)$가 되므로, $g(k)$는 $f(k)$와 다를 수 없어서 모순이다. 해의 존재성과 유일성으로 인해 차분 방정식을 다양한 방식으로 풀 수 있다. 예를 들어, 식 (2)를 풀 때에 Z 변환(Z-transform)을 써도 된다.

                  (6)

차분 방정식은 미분 방정식(differential equation)을 근사적으로 풀 때 매우 유용하다. 수학적 미분을 수치 미분으로 교체해서 미분 방정식을 차분 방정식으로 바꾸어 푸는 방식은 유한 차분법(finite difference method, FDM)이라 부른다. 유한 차분법에서는 해의 수렴성을 꼭 확인해서 풀어야 한다. 왜냐하면 수치 미분으로 인해 반복적인 연산이 들어가므로, 차분 방정식의 해가 미분 방정식의 해로 수렴한다는 확인이 꼭 필요하기 때문이다.

[참고문헌]

[1] S. Tauber, "Existence and uniqueness theorems for solutions of difference equations," Am. Math. Mon., vol. 71, no. 8, pp. 859–862, Oct. 1964.

[2] S. Elaydi, An Introduction to Difference Equations, 3rd ed., New York, USA: Springer, 2005.

[다음 읽을거리]

1. Z 변환

2. 이산 푸리에 변환