- •Основные характеристики
- •Аннотация
- •[Править] Канальный уровень
- •[Править] Разбиение на кадры
- •[Править] Контроль ошибок
- •[Править] Управление потоком
- •[Править] Помехоустойчивое кодирование [править] Характеристики ошибок
- •[Править] * Элементы теории передачи информации
- •[Править] Метод «чётности» и общая идея
- •[Править] Циклические коды
- •[Править] * Теоретический предел
- •[Править] Коды Хемминга
- •[Править] Анализ эффективности
- •[Править] Коды как линейные операторы
- •[Править] *Коды Рида-Соломона
- •[Править] Примеры протоколов канала данных [править] hdlc протокол
[Править] Анализ эффективности
Начнём c небольшого примера. Пусть у нас есть канал с уровнем ошибок p = 10 − 6. Если мы хотим исправлять единичные ошибки при передаче блоками по 1023 = 210 − 1 бит, то среди них потребуется 10 контрольных бит: 1, 2, \dots, 29. На один блок приходится 1013 бит полезной информации. При передаче 1000 таких блоков потребуется контрольных бит.
В тоже время для обнаружения единичной ошибки достаточно одного бита чётности. И если мы применим технику повторной передачи, то на передачу 1000 блоков надо будет потратить 1000 бит дополнительно и примерно из них придется пересылать повторно. То есть на 1000 блоков приходится один попорченый, и дополнительная нагрузка линии составляет , что меньше . Но это не значит, что код Хемминга плох для такого канала. Надо правильно выбрать длину блока — если n > 3444, то код Хемминга эффективен.
Рассмотрим этот вопрос подробнее. Пусть нам нужно передать информацию M бит. Разобьем её на L блоков по m = M / L бит и будем передавать двумя способами — с помощью кодов Хемминга и без них. При этом будем считать, что в обоих случаях осуществлено предварительное кодирование, позволяющее с вероятностью определять ошибочность передачи. Это осуществляется путем добавления «лишней» информации. Обозначим коэффициент раздувания для этого кодирования kε(m). После этого кодирования каждый блок несёт информацию m' = kε(m)m
1) Без кода Хемминга.
Если пересылать информацию блоками по m' бит с повторной пересылкой в случае обнаружения ошибки, то получим, что в среднем нам придётся переслать D бит:
Где Pr = (1 − (1 − p)m')(1 − ε) — вероятность повторной передачи равная вероятности ошибки умноженной на вероятность того, что мы её заметим. Коэффициент раздувания равен
2) С кодом Хемминга.
При кодировании методом Хемминга слова длины m' получается слово длины n бит:
(eq:hnm)
Для отдельного блока вероятность безошибочной передачи равна P0 = (1 − p)n. Вероятность одинарной ошибки P1 = np1(1 − p)n − 1. Вероятность того, что произошло более чем одна ошибка, и мы это заметили
Pr = (1 − P0 − P1)(1 − ε) = 1 − ε − (1 − ε)(1 − p)n − 1(np + 1 − p)
— в этом случае требуется повторная передача кадра. Количество передаваемых данных:
И коэффициент раздувания
где n(m) неявно определённая с помощью ((eq:hnm)) функция. Удобно записать соответствующие коэффициенты полезного содержания:
, m' = n − log 2(n + 1) (eq:kps)
Легко обнаружить что при n > 3444 и p = 10 − 6 код Хемминга оказывается эффективнее, то есть KPSH / KPS > 1
\begin{figure}[h!] \psfrag{knc}{кпс} \psfrag{n}{n} \centering\includegraphics[clip=true, width=0.48\textwidth]{pictures/kps.eps} \centering\includegraphics[clip=true, width=0.48\textwidth]{pictures/kps2.eps} \caption{ KPS(n,p,ε) — Коэффициент полезного содержания в канале с помехами как функция размера элементарного блока.} \parbox{0.85\textwidth}{\small Светлый график — без кодирования Хемминга;\\ Темный график — с кодированием Хемминга; \\Параметры: ; p = 10 − 6.} (fig:kps) \end{figure}
\begin{figure}[h!] \psfrag{C}{C} \psfrag{p}{p} \centering\includegraphics[clip=true, width=0.75\textwidth]{pictures/kpseff.eps} \caption{C(p,ε) — максимальный коэффициент полезного содержания в канале с помехами как функция уровня помех.} \parbox{0.97\textwidth}{ \small Светлый график — без кодирования Хемминга;\\ Темный график — с кодированием Хемминга;\\Тонкий график — теоретический предел, задаваемый функцией C(p)\\Параметры: ε = 10 − 6.} (fig:kpseff) \end{figure}
Значение KPSε(n) используемое в формулах ((eq:kps)) можно оценить как
Напомним, что ε есть параметр желаемой надёжности передачи — чем меньше ε, тем надёжнее передача. По определению ε = Pmiss / (1 − P0) — вероятности ошибочной передачи блока при условии, что «контрольная сумма сошлась» и кадр засчитан правильно переданным. Такое выражение для получается из формулы
Но это безусловно лишь оценочная формула. Оптимальное значение KPSε значительно сложнее и зависит от p.
Из графика на рисунке (fig:kps) хорошо видно, что при больших n код Хемминга начинает работать на пользу.
Но зависимость КПС от n не есть критерий эффективности кода. Эффективность кода определяется функцией
C(p,ε) = min nKPS(p,n,ε)
На рисунке (fig:kpseff) показан график этой функции и из него ясно, что код Хемминга можно использовать с пользой всегда — при любых ε и p, если у нас есть возможность выбирать подходящее n.