오류 제어용 채널 부호화(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. 채널 용량과 정보 전송의 한계

표면파(Surface Wave)

[경고] 아래 글을 읽지 않고 "표면파"를 보면 바보로 느껴질 수 있습니다.

1. 프레넬 방정식

[확인] 본 페이지는 exp(jωt) 시간 약속을 사용하고 있습니다.

[그림 1] 마이크로스트립 선로(microstrip line)의 굽힘(출처: wikipedia.org)

[그림 2] 표면파의 전력 분포(출처: [1])

[그림 1]과 같이 서로 다른 유전체층을 가진 전송선로에 불연속이 존재하면 필연적으로 표면파(surface wave)가 발생한다. 표면파는 [그림 2]처럼 서로 다른 매질의 경계면에 붙어서 전자파 전력을 전송할 수 있다. 마이크로스트립 선로(microstrip line)처럼 공기에 비해 상대적으로 유전율이 높은 영역에 전력이 분포되며, 공기층에서는 전자파 전력이 지수적으로 감소한다. 대부분의 응용에서 표면파는 불필요하게 전자파 전력을 뺏어서 삽입 손실(insertion loss)을 높이는 원인이 된다. 그래서 초고주파 회로를 설계할 때 표면파를 최대한 줄이는 방향으로 최적화한다.

[그림 3] 표면파 통신의 장점(출처: [1])

FSC: 자유 공간 통신(free-space communication), SWC: 표면파 통신(surface wave communication)

최근에는 표면파를 회피하지 않고 표면파가 가진 저손실 특성을 극대화함으로써 표면파가 존재하는 근처에서만 효율적으로 통신할 수 있는 표면파 통신(surface wave communication, SWC)이 다양하게 연구되고 있다[1]. 이때 표면파는 전력이 표면에만 존재하므로 전자파의 전송 관점에서는 거의 2차원 분포에 해당한다. 이로 인해 전기장은 $1/\sqrt{\rho}$, 전자파 전력은 $1/\rho$ 비율로 감소해서 자유 공간 대비 손실에 강점을 가진다. 여기서 $\rho$은 송수신 사이의 거리이다.

[참고문헌]

[1] K.-K. Wong, K.-F. Tong, Z. Chu, and Y. Zhang, "A vision to smart radio environment: Surface wave communication superhighways," IEEE Wirel. Commun., vol. 28, no. 1, pp. 112–119, Feb. 2021.

통신을 지배하는 상호 정보(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.

[3] 조정효, "머신러닝과 정보이론: 작동원리의 이해", HORIZON, 2021년 8월. (방문일 2025-01-03)

[다음 읽을거리]

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

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