- •Основные характеристики
- •Аннотация
- •[Править] Канальный уровень
- •[Править] Разбиение на кадры
- •[Править] Контроль ошибок
- •[Править] Управление потоком
- •[Править] Помехоустойчивое кодирование [править] Характеристики ошибок
- •[Править] * Элементы теории передачи информации
- •[Править] Метод «чётности» и общая идея
- •[Править] Циклические коды
- •[Править] * Теоретический предел
- •[Править] Коды Хемминга
- •[Править] Анализ эффективности
- •[Править] Коды как линейные операторы
- •[Править] *Коды Рида-Соломона
- •[Править] Примеры протоколов канала данных [править] hdlc протокол
[Править] * Элементы теории передачи информации
Информационным каналом называется пара зависимых случайных величин , одна из них называется входом другая выходом канала. Если случайные величины дискретны и конечны, то есть имеют конечные множества событий:
то канал определяется матрицей условных вероятностей , rij — вероятность того, что на выходе будет значение yi при условии, что на входе измерено значение xj.
Входная случайная величина определяется распределением на Ωin, а распределение на выходе вычисляется по формуле
Объединённое распределение на равно
Pij = rijpj.
Информация , передаваемая через канал, есть взаимная информация входа и выхода:
(eq:inf)
где
Если случайные величины ξin и ξout независимы (то есть Pij = qipj), то через канал невозможно передавать информацию и . Понять суть формулы ((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 2p + (1 − p)log 2(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 2p + (1 − p)log 2(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}
Построение конкретных способов кодирования, приближающихся по пропускной способности к теоретической границе — сложная математическая задача.