[Править] * Элементы теории передачи информации

Информационным каналом называется пара зависимых случайных величин , одна из них называется входом другая выходом канала. Если случайные величины дискретны и конечны, то есть имеют конечные множества событий:

то канал определяется матрицей условных вероятностей , r_ij — вероятность того, что на выходе будет значение y_i при условии, что на входе измерено значение x_j.

Входная случайная величина определяется распределением на Ω_in, а распределение на выходе вычисляется по формуле

Объединённое распределение на равно

P_ij = r_ijp_j.

Информация , передаваемая через канал, есть взаимная информация входа и выхода:

(eq:inf)

где

Если случайные величины ξ_in и ξ_out независимы (то есть P_ij = q_ip_j), то через канал невозможно передавать информацию и . Понять суть формулы ((eq:inf)) можно из следующего соображения: энтропия случайной величины равна информации, которую мы получаем при одном её измерении. H(ξ_in) и H(ξ_out) — информация, которая содержится по отдельности во входе и в выходе. Но часть этой информации общая, её нам и нужно найти. H({ξin,ξ_out}) равна величине объединённой информации. В теории меры^[1] есть выражение аналогичное ((eq:inf)):

Распределение входной случайной величины ξ_in мы можем варьировать и получать различные значения I. Её максимум называется пропускной способностью канала

(eq:cdef)

Эта функция есть решение задачи

Задача 1.

(task:shanon) Каково максимальное количество информации, которое можно передать с одним битом по каналу ?

Конец задачи.

{\slshape Итак, пропускная способность есть функция на множестве стохастических матриц^[2].}

Стандартный информационный канал это

Ω_in = Ω_out = {0,1}.

(eq:sm)

То есть канал с бинарным алфавитом и вероятностью помехи p (p — вероятность того, что бит будет случайно инвертирован). Его пропускная способность равна

C = 1 − H(p) = 1 + plog ₂p + (1 − p)log ₂(1 − p).

Эта функция является решением задачи на максимум ((eq:cdef)) для матрицы ((eq:sm)).

\begin{figure}[t!] \centering\includegraphics[clip=true, width=0.75\textwidth]{pictures/cideal.eps} \caption{ C(p) — Пропускная способность канала как функция вероятности инвертирования бита.} (fig:cideal) \end{figure}

Эта функция C(p) (рис. (fig:cideal)) определяет предел помехоустойчивого кодирования — если мы хотим с абсолютной надёжностью передать по каналу с пропускной способностью C сообщение длиной m, то минимальное количество бит, которое нам нужно будет передать . А точнее, всякое помехоустойчивое кодирование, обеспечивающее вероятность незамеченной ошибки в переданном слове меньше, чем ε, раздувает данные в k_ε(m,p) раз и

Кодирование, при котором в этом пределе достигается равенство, называется эффективным. Отметим, что абсолютно надёжного способа передачи конечного количества данных по каналу с помехами не существует: то есть

Задача дуальная (task:shanon) формулируется следующим образом

Задача 2.

(task:dual) Мы хотим передавать информацию со скоростью V по каналу с пропускной способностью C. Какова минимальная вероятность ошибочной передачи одного бита?

Конец задачи.

Решением будет функция заданная неявно

C / V = 1 + plog ₂p + (1 − p)log ₂(1 − p), если V / C > 1,

p(V / C) = 0, если

Оказывается, вероятность ошибки растет не так уж и быстро. Например, если по каналу передавать данных в два раза больше, чем его пропускная способность, то лишь 11 бит из ста будут переданы с ошибкой.

\begin{figure}[t!] \psfrag{v}{v} \psfrag{p}{ p(v)} \centering\includegraphics[clip=true, width=0.75\textwidth]{pictures/pv.eps} \caption{ p(v) — минимальная вероятность ошибки в одном бите как функция от отношения скорости передачи и пропускной способности v = V / C.} (fig:pv) \end{figure}

Построение конкретных способов кодирования, приближающихся по пропускной способности к теоретической границе — сложная математическая задача.