정보이론

응용 분야

정보이론은 암호학이나 언어에 응용되어왔다. 정보이론에서 사용하는 개념들이 암호학의 공식화에 이용 가능하며 언어학에서는 한 언어 안에서 단어들의 발생빈도와 길이의 분포 등의 연구가 되어왔다. 언어학의 연구 결과들은 언어가 계속되는 효과적인 통신을 통하여 진화한다는 것을 알려준다(→ 통신 시스템).

심리학자들은 자극 속에 있는 정보의 양과 자극에 대한 반작용 시간의 재미있는 관계를 밝혔다. 이러한 연구들은 인간이 어떤 조건하에서 정보를 다루는데 정보이론에서 사용하는 부호나 방법들에 적응하게 될 수 있다는 것을 암시한다.

정보측정

개요

정보의 전달에 있어 정보의 의미는 관련이 없다.

일련의 무의미한 기호들을 전송하는 것이나 문장을 그대로 전송하는 것이나 똑같이 어렵다. 전송의 입장에서 정보의 중요한 면은 여러 가지 가능한 메시지들 중 어떤 한 가지가 선택된다는 점이다(우연성). 이때 꼭 전송되어야 할 것은 정보원에 의해 선택된 메시지의 명세서다. 원정보(原情報)는 명확한 명세서가 전달되어야만 수신지에서 재형성될 수 있다. 그래서 정보이론에 의한 정보라는 것은 여러 가능한 메시지들로부터 어느 한 메시지를 선택하는 것으로 생각된다.

가장 간단한 것으로 이진선택(binary choice)이 있다(2진법). 이것은 동전 던지기처럼 확률이 각각 1/2로 같은 2개의 가능성 중에서 하나를 선택하는 것이다.

이러한 방법의 선택에 의해 발생한 정보를 비트(bit)라는 기본 단위로 나타낸다. 만약 N개의 가능성이 있다고 한다면 정보의 양은 log₂N으로 나타난다. 만약 확률이 동등하지 않다면, 메시지들은 그들에 연관된 다른 양의 정보를 갖게 된다.

각각의 가능한 가능성의 확률을 p₁, p₂,……, p_N이라고 하면 첫 메시지와 관련된 정보의 양은 log₂(1/p₁), 2번째는 log₂(1/p₂)이 된다. 기대되는 정보의 양은 엔트로피 H로 나타내며 다음과 같은 식 ①로 나타난다.

H=p₁log₂ (1/P₁)＋p₂log₂(1/p₂)＋……＋p_Nlog₂(1/p_N) ①

엔트로피는 하나의 메시지가 항상 일어날 경우, 즉 확률이 1이 되는 경우에 최소가 된다.

반대로 메시지가 각각 동등하게 나타날 경우에 최대가 된다. 정보이론에서 엔트로피에 대한 수학적인 표현은 통계역학에서 엔트로피를 나타내는 것과 유사하며 여러 가지 면에서 많은 연관이 있다.

대부분의 정보원은 단 하나의 선택이 아니라 일련의 선택들로 되어 있다. 영어 문장들은 선택의 처리라고 볼 수 있다. 즉 첫 단어를 선택하고 이것에 의존하는 2번째 단어를 선택하는 것과 같다. 이와 같은 통계적 처리를 추계처리(推計處理)라고 한다.

정보원 또는 추계처리에 의해 보다 일반적인 수식이 주어질 수 있다. 일반적인 영어 작문에서 정보율은 글자당 대략 1비트를 넘지 않는다. 이러한 현상은 글자의 조합, 서로 다른 글자들의 불규칙한 발생빈도, 자주 쓰이는 단어나 절의 존재 여부 등에 의존한다. 한 언어에 관련된 통계적 데이터들은 언어의 통계적 구조라고 부른다. 만약 26글자와 빈 칸이 각각 1/27의 발생빈도를 가지고 다른 글자의 발생에 영향을 미치지 않는다고 하면 정보율은 log₂27, 즉 글자당 4.76비트가 된다.

영어는 80％의 중복률을 갖는다고 한다. 중복성은 독자로 하여금 문장의 뜻을 잃지 않게 하며 많은 글자를 생략할 수 있게 한다. 다음은 문장에서 모음을 생략한 예이다.

MST PPL HV LTTL

DFFCLTY N RDNG THS SNTNC.

정보의 왜곡측정

음성·텔레비전 같은 많은 정보원과 물리적 성질들은 불연속적인 것으로 간주되지 않는다.

이러한 정보원들의 불확실성과 엔트로피를 정의하려 할 때 심각한 문제가 발생한다. 각각의 가능한 출력 정보원을 u라 하고, 수신지에서 출력 정보원을 나타내는 각각의 가능한 신호를 v라고 하면, 왜곡측정 D(u, v)는 신호 v로 출력 정보원 u를 나타내는 비용으로 정의되며 음수가 아닌 수로 표시된다. 왜곡은 근사 에러의 제곱으로 주어진다(⑤). 만약 출력 정보원이 연속적으로 변하는 신호 u이고 v(t)가 u(t)에 대한 근사이면 왜곡측정은 시간에 대한 함수로 나타난다(⑥). 근사는 2진열을 표본단계로 표본단계를 시변화 신호로 사상시킴으로써 이루어진다.

근사는 정량화에 의한 에러에 의해 출력 정보원과 다르게 된다.

D(μ,υ)＝(μ,υ)² ⑤

D[μ(t), υ(t)]＝[μ(t)－υ(t)]² ⑥

왜곡측정은 수신지에 출력 정보원의 중요성이나 의미를 반영하기 위해 선택될 수 있다.

예를 들면 음성전송에 있어서 귀는 음성신호의 위상왜곡에 대해서는 상대적으로 무감각하므로 적당한 왜곡측정은 위상왜곡보다 진폭왜곡을 더 잘 측정한다. 말투와 함께 발음자의 인식에 대한 명확성의 상대적인 중요성과 음질도 측정될 수 있다. 음성과 같은 정보원에 대한 적당한 왜곡측정의 선택은 매우 어렵고 정보이론의 응용을 제한한다. 왜곡수준 D에 대한 정보원의 비 R는 출력 정보원을 부호화하는 데 요구되는 단위 시간당 최소의 2진숫자로 정의된다.

이때 출력 정보원과 최종 근사 사이의 평균왜곡이 D 정도는 돼야 한다. 이 정의에 의해 정보원의 비는 평균왜곡을 허용하는 함수 R(D)가 된다. 허용왜곡 D가 커질수록 요구되는 2진숫자의 수는 적어진다. 정보원을 허용된 왜곡에 대해 2진열로 부호화하는 최적의 방법을 찾는 것은 적어도 잡음 채널의 좋은 에러 수정 기술을 찾는 것만큼 어렵다.

검출·추정·예측

정보이론의 분야에서 또다른 형태의 문제점은 잡음이 섞인 신호로부터 메시지를 뽑아내기 위한 장치를 결정하는 것이다.

만약 메시지가 불연속적인 선택들로부터의 한 선택을 나타낸다면 잡은 신호로부터 메시지를 뽑아내는 과정을 검출(detection)이라고 한다(검파). 만약 메시지가 연속적인 범위의 값에 대한 하나 또는 그 이상의 요소들의 명세서를 나타낸다면 잡음신호로부터 메시지를 뽑아내는 것을 추정(estimation)이라고 한다.

보다 일반적으로 추정에는 메시지가 시간에 대한 함수만이 아니라 시간과 공간의 함수로 연속적으로 변한다. 예측(prediction)은 메시지가 어느 정도 미래의 시간에 불규칙 신호의 값인 때의 추정의 중요한 특별한 경우이다. 미래 값은 지금까지 일어난 불규칙 신호의 부분들로부터 추정된다.

검출문제는 베이스 공식화로 다룬다(베이스 계산법). 0,1,2,……, n－1의 n개의 메시지가 확률 p₀, p₁,……, p_n－1로 발생한다고 하고, 수신된 잡음이 섞인 신호에 알려진 확률분포가 있다고 각 메시지를 조건짓자. 마지막으로 메시지 i가 존재할 때 메시지 j를 검출하는데 C_ij의 비용이 든다고 하자. 이러한 공식화에서 최적의 검출기는 틀린 결정에 대한 기대되는 비용을 최소화하는 검출기로 정의된다.

이러한 최적의 검출기는 우도비(likelihood ratios)라 하는 n－1쌍을 계산함으로써 쉽게 얻어지고 우도비에 기초한 결정을 할 수 있게 된다. i번째 우도비는 메시지 i에 제한된 수신된 잡음 메시지의 확률과 메시지 0에 수신된 잡음 메시지의 확률의 비로 정의된다.

이 우도비는 메시지가 발생할 확률 또는 비용함수 C_ij에 의존하지 않는다. 이러한 이유로 우도비는 메시지의 확률이나 비용함수에 관한 가정을 할 수 없을 때 검출문제의 다른 공식화에 기본적인 것이다. 추정을 위한 공식화도 검출에서처럼 베이스 공식화를 따른다. 여기에서 메시지와 수신된 신호 모두 완전한 확률적 표현이 가능하다고 가정한다. 에러 값의 제공과 같은 비용함수는 메시지와 메시지 추정 사이에서 명확하게 된다면 최적의 추정기는 기대되는 비용을 최소화하는 것으로 정의된다.

위 공식화의 고전적인 경우는 메시지와 잡음이 가우스 처리에 의해 결합되는 때이다.

지연과 예측간격을 갖는 최적의 추정기는 미국과 소련에서 각각 독립적으로 발견되었다. 그후 적당하게 선택된 선형 필터임을 알게 되었다. 메시지와 잡음처리가 가우스형이 아니고 추정기가 선형으로 제한되었을 때에도 같은 결과가 나온다. 그리고 대부분의 추정문제는 정확하게 풀리는 것이 아니라 근사해로 만족해야 한다.

정보의 부호화

개요

정보 H의 측정의 중요한 측면은 정보의 통계적인 면 때문에 적당한 부호화를 통해 전송시간을 절약한다는 것이다.

글자 A,B,C,D가 각각 1/2, 1/4, 1/8, 1/8의 확률을 갖는다고 하자. 이것을 2진법으로 표시하면 A＝00, B＝01, C＝10, D＝11로 부호화할 수 있다. 그러나 적당한 통계적 방법에 의해 A＝00, B＝01, C＝110, D＝111로 부호화된다.

이것은 평균적으로 사용되는 2진부호의 수를 보다 적게 하며 (1) 1/2＋(2) 1/4 ＋(3) 1/8＋(3) 1/8＝1 3/4이 된다. 간단한 계산에 의해 1¾은 H가 된다.

H(글자당 비트 수)가 정보원의 엔트로피라고 하면 2진부호화에는 H개의 2진숫자가 필요하다. 평균 2진숫자의 수가 H에 가까워질수록 부호화는 복잡하게 된다. 그래서 1개의 글자마다 2진숫자열로 부호화하기 보다 일련의 글자를 2진숫자열로 사상(寫像 map)시키는 것이 요구된다.

이와 같은 것 때문에 H는 언어나 정보를 0이나 1로 부호화할 때 요구되는 2진숫자의 수와 같게 해석된다. 데이터를 최소의 비트 수를 이용해 부호화하는 실제적인 기술을 데이터 압축이라고 한다.

에러 수정을 위한 부호화

에러를 줄이기 위한 대부분의 기술들은 패리티 검사(parity check)의 개념에 기초한다.

2진숫자들의 패리티(p)는 1의 개수가 홀수개이면 0으로, 그렇지 않을 경우는 1로 정의한다. 111의 패리티는 1이 되고 110은 0이 된다. 어떤 하나의 숫자의 변화로 패리티는 변하게 된다.

패리티 검사를 이용하여 에러를 줄이는 방법은 다음과 같다. 4개의 정보원 숫자를 s₁, s₂, s₃, s₄라고 하고 이것의 패리티 검사 숫자를 p₁, p₂, p₃, p₄라고 하면 각 패리티는 다음 식 ②와 같이 정의한다.

p₁＝P(s₁, s₂, s₃)

p₂＝P(s₁, s₂, s₄) ②

p₃＝P(s₁, s₃, s₄)

그러면 정보원 1001은 식 ②에 의해 1001100으로 부호화된다.

만약 첫 정보원 s₁에만 에러가 수반되어 수신되면 수신된 패리티 검사는 수신된 정보원에 의한 패리티 검사와 일치하지 않는다. 이처럼 각 정보원 숫자와 패리티 숫자는 그 자신의 독특한 불일치 양상을 보이게 되고 7개의 숫자 중에서 어느 1개의 에러 발생을 수정할 수 있으나 여러 개의 에러는 이 방법으로는 수정할 수 없다.

위와 같은 블록식 부호의 예로써 정보원에 있는 부호를 일정한 길이로 분할하고 각 정보열을 일정한 길이의 채널 숫자열로 전송한다.

블록 길이는 채널 열의 길이에 대한 정보열의 길이로 정의한다. 위의 예의 경우 부호율은 4/7가 된다. 부호와 이론은 채널 용량에 가까운 부호율을 갖는 블록식 부호와 0에 가까운 에러 발생률이 가능하다고 한다. 그러나 필요한 블록 길이는 부호율이 용량에 가까울수록, 에러율이 0에 가까울수록 증가한다. 이러한 에러 수정을 위한 부호와 방식은 콤팩트 디스크의 정밀기술과 자료망에서 사용된다.

블록식 부호보다 실용적인 부호와 방식으로 콘벌루션 부호(convolution code)가 있다.

콘벌루션 부호에서는 정보원과 패리티를 s₁, p₁, s₂, p₂, s₃, p₃ …… 순서로 나타내고, 각 패리티 검사 숫자는 앞의 두 정보원의 숫자의 패리티로 나타낸다(③).

P_n＝P(s_n, s_n－1) ③

정보원이 1011이라고 하면 전송 숫자는 11011110이 된다(정보원은 기울임체임). 잡음이 정보원의 숫자 하나를 바꾸었다고 하면 패리티는 연속되는 2개의 패리티 검사 숫자를 확인하지 않는다.

반면 잡음이 패리티 검사 숫자의 하나를 바꾸면 오직 하나의 패리티만이 확인할 수 없게 된다. 그래서 적어도 3개의 정확한 숫자를 전후하여 에러율을 얻기 위해서는 패리티 검사 구역이 보다 많은 숫자들에 대해서 확장되어야 한다.

정보전송

개요

정보의 전송시에 잡음이 없고 수신지에서 충실하게 복원되면 전송된 정보는 정보원의 것과 같고 전송된 정보의 평균은 정보원의 엔트로피와 같다.

잡음이 있는 경우는 더욱 복잡해진다. 가장 간단한 것으로 2원 소실 통신로(binary erasure channel)가 있다. 0과 1의 같은 확률의 2진수로 표현된 정보원의 전송에서 전송 중 10％의 시간 동안 잡음에 의해 정보가 지워지면 이때는 정보의 전송이 없다고 하며, 나머지 90％의 시간 동안은 정보의 전송이 있다고 한다. 이것은 메시지당 평균 90％의 전송을 보인다.

다른 경우는 2원 대칭 통신로(binary symmetric channel)이다.

0이 전송될 때 0이 수신될 확률은 9/10이고 1이 수신될 확률은 1/10이다. 1이 전송될 때도 같다. 정보원이 0과 1을 동등하게 발생한다고 하면 정보의 엔트로피 또는 평균 불확실성은 1이 된다. 그러므로 0을 수신할 정보원의 불확실성은 ⁹/₁₀log₂ ¹⁰/₉＋¹/₁₀log₂10, 즉 약 0.47비트가 된다. 1도 같은 방법을 통해 얻는다.

두 경우의 차이점은 매우 크다. 두 경우 모두 90％가 정확하게 전송되었지만 어떤 숫자가 의심스러운지 모르는 2원 대칭 통신로는 의심스러운 숫자가 삭제된 기호로 덮인 2원 소실 통신로보다 적은 정보를 전송한다. 출력 채널을 주는 입력 채널의 조건화된 엔트로피는 출력기호의 확률에 의해 측정되는 불확실성의 평균이다. 평균 전송정보는 입력 엔트로피와 출력을 주는 그 입력의 조건화된 엔트로피와의 차이이다.

입력이 출력에 의해 명확히 되는 특별한 경우에 조건화된 엔트로피는 0이고, 전송 정보는 입력 자체의 불확실성과 비슷하다.

통신로에서 가장 중요한 것은 용량이며 한 통신로에 대한 최대의 평균 정보로 정의된다. 위의 2원 소실 통신로와 2원 대칭 통신로의 용량은 각각 0.9, 0.53이다. 통신로 용량과 정보원의 엔트로피는 잡음채널 부호와 정의에 의해 연결된다.

정보원 엔트로피(단위 시간당 비트 수)가 통신로용량(단위 시간당 비트 수)보다 적으면 부호기와 해독기를 수신지에서 정보원이 원하는 만큼 작은 에러율로 복원할 수 있게 만들 수 있다(오차). 정보원 엔트로피가 용량보다 많다면 에러율은 작게 할 수 없다.

대역폭 제한 채널

전송 매체의 물리적 제한과 다른 채널과의 간섭을 피하기 위해 전송되는 신호는 주어진 주파수대 W(㎐)로 제한된다.

표본화 이론에 의하면 이러한 형태의 신호는 초당 표본화 지점의 적당한 선택에 의한 2W의 열에서의 값으로 표시된다. 만약 이러한 채널에 잡음이 없다면 각 표본에 대하여 무한히 많은 진폭을 구별해낼 수 있다. 즉 용량 C가 무한대가 되는 것이다.

이 경우도 전송력 P가 무한대이면 용량은 무한하게 된다. 잡음이 존재하고 전송력이 제한되면 용량은 유한하게 된다. 이때 용량은 잡음의 통계적 구조와 전력을 제한하는 성질에 따라 다르게 된다.

가장 간단하고 여러 가지 면에서 가장 기본적인 잡음의 형태는 가우스 잡음이다. 이것은 전기 저항의 열효과에 의해 발생하여 주파수의 형태로 전파되며, 주파수당 평균전력으로 계산되는 N으로 표시된다.

채널의 입력신호가 전력 제한 P와 대역폭 제한 W를 갖고 있는 출력신호가 입력신호와 백색 가우스 잡음 N(Power/㎐)의 합이라고 하면 채널의 용량은 W와 신호대 잡음률 P/N의 단순 증가 함수가 된다.

송신기와 수신기의 적당한 설계를 통해 초당 C 2진 숫자를 전송할 수 있다.

그러나 초당 C 2진숫자 이상은 작은 에러율로 전송할 수 없다.