Помехоустойчивое кодирование: различия между версиями

Нет описания правки
только этому уровню:
* реализация сервиса для сетевого уровня,
* разбиение потока бит на кадры,
* объединение битов, поступающих с физического уровня в кадры,
* обработка ошибок передачи, управление потоком кадров.,
* обработка ошибок передачи.
 
Основная задача канального уровня — обеспечить сервис сетевому уровню,
посылке данных.
 
<b>Контрольная сумма</b> - это, в общем смысле, функция от
содержательной части кадра (слова длины <math>m</math>), область
значений которой - слова фиксированной длины <math>r</math>.
 
Эти <i>r</i> бит добавляются обычно в конец кадра. При приёме
принято шесть и за ними следует ноль, то это управляющий сигнал:
начало или конец кадра, а в случае, когда подряд идут более шести
единиц, — сигнал ожидания или аварийного завершения.
единиц,
— сигнал ожидания или аварийного завершения.
 
 
 
(а) 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 0 1
 
Bit Stuffing. (a) исходные данные (б) посылаемые данные. Жирным отмечены вставленные нули.
 
 
Таким образом, кадр легко может быть распознан по
кадров тот может принять. Получатель сообщает ему определённое
число кадров. Отправитель после того, как передаст это число
кадров, должен приостановить передачу и снова спросить получателя, опять
как много кадров тот может принять, и&nbsp;т.д.
 
==Помехоустойчивое кодирование==
 
''Первый'' заключается в добавлении в передаваемый блок
данных нескольких &laquo;«лишних&raquo;» битов так, чтобы, анализируя
полученный блок, можно было бы сказать есть в переданном
блоке ошибки или нет. Это, так называемые, '''коды с
<math>\{p_1,\dots,p_a\}</math> на <math>\Omega_{in}</math>, а распределение на
выходе вычисляется по формуле
 
 
:<math>q_i=\sum_{j=1}^{a}r_{ij}p_j.</math>
Объединённое распределение на
<math>\Omega_{in}\times\Omega_{out}</math> равно
 
 
:<math>P_{ij}=r_{ij}p_j.</math>
 
 
Информация <math>I(\{\xi_{in},\,\xi_{out}\})</math>, передаваемая через
где
:<math>H(\xi_{in})=-\sum_{i=1}^ap_i\log_2 p_i,</math>
 
 
:<math>H(\xi_{out})=-\sum_{i=1}^aq_i\log_2 q_i,</math>
 
 
:<math>H(\{\xi_{in},\,\xi_{out}\})=-\sum_{i,j}P_{ij}\log_2 P_{ij}.</math>
 
 
Если случайные величины <math>\xi_{in}</math> и <math>\xi_{out}</math> независимы (то
равна величине объединённой информации. В теории
меры{{ref|note1}} есть выражение
аналогичное (\ref{<b>(eq:inf})</b>):
 
:<math>\mu(A\wedge B)=\mu(A)+\mu(B)-\mu(A\vee B).</math>
 
 
 
Распределение входной случайной величины <math>\xi_{in}</math> мы можем
 
Эта функция есть решение задачи
 
\begin{task}
<div class="task"><b>Задача 1.</b>
 
<b>(task:shanon)</b> Каково максимальное количество информации,
которое можно передать с одним битом по каналу
<math>\{\xi_{in},\,\xi_{out}\}</math>?
 
\end{task}
<b>Конец задачи.</b></div>
 
{\slshape Итак, пропускная способность есть функция на
 
:<math>\Omega_{in}=\Omega_{out}=\{0,1\}.</math>
 
 
 
:<math>
:<math>C= 1-H(p)=1+p\log_2p+(1-p)\log_2{(1-p)}.</math>
 
Эта функция является решением задачи на максимум (\ref{<b>(eq:cdef})</b>)
для матрицы&nbsp;(\ref{<b>(eq:sm})</b>).
 
\begin{<div align="center}">
\begin{figure}[t!]
\centering\includegraphics[clip=true,
width=0.75\textwidth]{pictures/cideal.eps} \caption{ <math>C(p)</math> —
Пропускная способность канала как функция вероятности
инвертирования бита.} \label{<b>(fig:cideal})</b>
\end{figure}
</div>
\end{center}
 
Эта функция <math>C(p)</math> (рис.&nbsp;\ref{<b>(fig:cideal})</b>) определяет предел
помехоустойчивого кодирования — если мы хотим с абсолютной
надёжностью передать по каналу с пропускной способностью <i>C</i>
незамеченной ошибки в переданном слове меньше, чем <math>\varepsilon</math>,
раздувает данные в <math>k_{\varepsilon}(m,p)</math> раз и
 
 
:<math>\lim_{\varepsilon\to 0}\lim_{m\to\infty}k_{\varepsilon}(m,p)\geqslant {1/C(p)}.</math>
<math>k_0(m,p)=\infty.</math>
 
Задача дуальная \ref{<b>(task:shanon})</b> формулируется следующим
образом
 
\begin{task}
<div class="task"><b>Задача 2.</b>
\label{task:dual}
 
<b>(task:dual)</b>
Мы хотим передавать информацию со скоростью <i>V</i> по каналу с
пропускной способностью <i>C</i>. Какова минимальная вероятность
ошибочной передачи одного бита?
 
\end{task}
<b>Конец задачи.</b></div>
 
Решением будет функция заданная неявно
 
ста будут переданы с ошибкой.
 
\begin{<div align="center}">
\begin{figure}[t!]
\psfrag{v}{<i>v</i>} \psfrag{p}{ <math>p(v)</math>}
минимальная вероятность ошибки в одном бите как функция от
отношения скорости передачи и пропускной способности <math>v=V/C</math>.}
\label{<b>(fig:pv})</b>
\end{figure}
</div>
\end{center}
 
Построение конкретных способов кодирования, приближающихся
по пропускной способности к теоретической границе —
сложная математическая задача.
 
===Метод &laquo;«чётности&raquo;» и общая идея===
Простым примером
кода с обнаружением одной ошибки является код с битом чётности.
позволяет обнаружить групповые ошибки длины <math>\leqslant n</math>.
 
<div class="task"><b>Задача 3.</b>
\begin{task}
 
Слово длиной <i>n</i> с чётным количеством единиц передано по каналу с
уровнем шума <i>p</i>. Покажите, что вероятность того, что при
 
Например, при <math>n=1000</math> и <math>p=10^{-6}</math> получаем <math>P_{miss}\approx 4.99\cdot 10^{-7}</math>
 
\end{task}
<b>Конец задачи.</b></div>
 
Следующая задача повышенной сложности.
 
<div class="task"><b>Задача 4.</b>
\begin{task}[*]
 
\label{task:errmod} Пусть у нас есть возможность контролировать
[*]
<b>(task:errmod)</b> Пусть у нас есть возможность контролировать
сумму единичек по модулю&nbsp;<i>d</i>. Тогда вероятность нефиксируемых
ошибок в слове длиной <i>n</i> при передаче его по каналу с шумом <i>p</i>
вероятность <math>P_{miss}</math>, тем меньше коэффициент содержания
полезной информации.
 
\end{task}
<b>Конец задачи.</b></div>
 
Итак, с помощью одного бита чётности мы повышаем надёжность
:<math>\rho_H(10001001,10110001)=3.</math>
 
<div class="task"><b>Задача 5.</b>
 
\begin{task}
Докажите, что <math>\rho_H</math> метрика.
 
\end{task}
<b>Конец задачи.</b></div>
 
Если два слова находятся на расстоянии <i>r</i> по Хеммингу,
между двумя различными допустимыми кодовыми словами
называется ''расстоянием Хемминга данного кода''.
 
 
Элементарный пример помехоустойчивого кода — это код, у
 
:<math>0000000000,\; 0000011111,\; 1111100000,\; 1111111111.</math>
 
 
Расстояние по Хеммингу у этого кода 5, следовательно он может
Здесь мы подошли к довольно трудной задаче —
минимизировать коэффициент раздувания для требуемой
надёжности передачи. Она рассматривается в \ref{<b>(theory})</b>.
 
===Циклические коды===
Полином <math>G(x)</math> тем лучше, чем больше среднее расстояние Хемминга
на парах допустимых полиномов.
 
 
Есть два очевидных способа кодирования сообщения в полином,
Отправитель и получатель заранее договариваются
о конкретном ''полиноме-генераторе'' <math>G(x)</math>. Пусть степень
<math>G(x)</math> равна <i>l</i>. Тогда длина блока &laquo;«конторольной суммы&raquo;» также
равна <i>l</i>.
 
# ''Разделить полином <math>x^r\cdot W(x)</math> на <math>G(x)</math> и вычислить остаток от деления <math>R(x)</math> :<math>x^r W(x)=G(x)Q(x)+R(x);</math> ''
# ''Вычесть остаток (вычитание в <math>\mathbb{F}_2</math> то же самое, что и сложение) из полинома <math>x^r\cdot W(x):</math> :<math>T(x)=x^r W(x)-R(x)=x^r W(x)+R(x)=G(x)Q(x).</math> Слово, которое соответствует полиному <math>T(x)</math>, и есть результат.''
Рис.&nbsp;\ref{<b>(fig:crc})</b> иллюстрирует этот алгоритм для блока
<i>1101011011</i> и <math>{G(x)=x^4+x+1}</math>.
 
width=0.75\textwidth]{pictures/crc2.eps}
\caption{CRC — полиномиальное кодирование}
\label{<b>(fig:crc})</b>
\end{figure}
 
одиночные, двойные ошибки, групповые ошибки длины не более 16 и
нечётное число изолированных ошибок с вероятностью <i>0.99997</i>.
 
 
===* Теоретический предел===
\label{<b>(theory})</b> В примечании
к задаче&nbsp;\ref{<b>(task:errmod})</b> было указано как можно получить
значение коэффициента содержания полезной информации (КПС) на
один бит, если передавать данные по каналу с шумом <i>p</i> словами
абсолютной точностью.
 
<div class="task"><b>Задача 6.</b>
\begin{task}
 
\label{task:err}
<b>(task:err)</b>
Мы хотим передавать информацию блоками, которые содержали
бы <i>m</i> бит полезной информации, так, чтобы
вероятность ошибки в одном бите равнялась <i>p</i>, а
правильность передачи &laquo;«фиксировалось контрольной суммой&raquo;». Найти
минимальный размер блока <math>n(m,p)</math> и коэффициент раздувания
<math>k=\frac{n(m)}{m}</math>.
 
\end{task}
<b>Конец задачи.</b></div>
 
''Решение.''
Для передачи <i>m</i> бит с вероятностью ошибки в отдельном бите
<i>p</i> требуется передать <math>m C(p)</math> бит
(см.&nbsp;задачу&nbsp;\ref{<b>(task:dual})</b>). Кроме того мы хотим сообщать
об ошибке в передаче. Её вероятность равна <math>(1-p)^m</math>, а
значит информация, заложенная в этом сообщении,
 
Понятно, что данная теоретическая оценка занижена.
 
 
===Коды Хемминга===
слов и эти множества не должны пересекаться. Так как общее число
слов <math>2^n</math>, то
 
 
:<math>
\end{array}
</math>
 
 
Этот теоретический предел достижим при использовании
\end{array}
</math> <b>(eq:hem)</b>
 
 
Код Хемминга оптимален при <math>n=2^r-1</math> и <math>m=n-r</math>. В общем случае
\lefteqn{b_{15}}\hphantom{1}
\end{array}</math>
 
 
 
Получив слово,
\centering\includegraphics[clip=true,
width=0.65\textwidth]{pictures/hem.eps} \caption{Кодирование
Хемминга} \label{<b>(fig:hem})</b>
\end{figure}
 
<div class="task"><b>Задача 7.</b>
 
\begin{task}
Покажите, что <math>KPS_{Hem(n,m)}\to 1</math> при <math>n\to
\infty</math>.
\end{task}
 
<b>Конец задачи.</b></div>
 
Код Хемминга может исправлять только единичные ошибки. Однако,
кодирование, позволяющее с вероятностью <math>1-\varepsilon</math>
определять ошибочность передачи. Это осуществляется путем
добавления &laquo;«лишней&raquo;» информации. Обозначим коэффициент
раздувания для этого кодирования <math>k_\varepsilon(m)</math>. После
этого кодирования каждый блок несёт информацию
 
:<math>k(m,p,\varepsilon)=\frac{D}{M}=\frac{k_{\varepsilon}(m)}{\varepsilon+(1-\varepsilon)(1-p)^{k_{\varepsilon}(m)m}}</math>
 
 
2) '''С кодом Хемминга.'''\\ При кодировании методом
\end{array}
</math> <b>(eq:hnm)</b>
 
 
Для отдельного блока вероятность
\over m\bigl(\varepsilon+(1-\varepsilon)(1-p)^{n-1}(np+1-p)\bigr)},</math>
 
где <math>n(m)</math> неявно определённая с помощью (\ref{<b>(eq:hnm})</b>)
функция. Удобно записать соответствующие коэффициенты
полезного содержания:
\\[0.5mm] m'=n-\log_2{(n+1) \end{array}
</math> <b>(eq:kps)</b>
 
 
 
Легко обнаружить что при <math>n>3444</math> и <math>p=10^{-6}</math> код Хемминга
оказывается эффективнее, то есть <math>KPS_H/KPS>1</math>
 
\begin{<div align="center}">
\begin{figure}[h!]
\psfrag{knc}{кпс} \psfrag{n}{<i>n</i>}
Темный график — ''с кодированием Хемминга'';
\\Параметры: <math>\varepsilon=10^{-6}\;</math>; <math>p=10^{-6}.</math>}
\label{<b>(fig:kps})</b>
\end{figure}
</div>
\end{center}
 
\begin{center}
<div align="center">
\begin{figure}[h!]
\psfrag{C}{<i>C</i>} \psfrag{p}{<i>p</i>}
\parbox{0.97\textwidth}{ \small Светлый график — ''без кодирования Хемминга'';\\ Темный график — ''с кодированием Хемминга'';\\Тонкий график — теоретический
предел, задаваемый функцией&nbsp;<math>C(p)</math>\\Параметры:
<math>\varepsilon=10^{-6}</math>.} \label{<b>(fig:kpseff})</b>
\end{figure}
</div>
\end{center}
 
Значение <math>KPS_{\varepsilon}(n)</math> используемое в
формулах (\ref{<b>(eq:kps})</b>) можно оценить как
 
 
:<math>KPS_{\varepsilon}(n)={\log_2{\left(1-\varepsilon(2^n-1)\right)} \over n}</math>
 
 
Напомним, что <math>\varepsilon</math> есть параметр желаемой
— чем меньше <math>\varepsilon</math>, тем надёжнее передача.
По определению <math>\varepsilon=P_{miss}/(1-P_{0})</math> — вероятности
ошибочной передачи блока при условии, что &laquo;«контрольная сумма
сошлась&raquo;» и кадр засчитан правильно переданным.
Такое выражение для <math>KPS_{\varepsilon}(p,n)=\frac{m}{n}</math>
получается из формулы
 
 
:<math>\varepsilon=\frac{2^m-1}{2^n-1}</math>
 
 
Но это безусловно лишь оценочная формула. Оптимальное
зависит от <i>p</i>.
 
Из графика на рисунке&nbsp;\ref{<b>(fig:kps})</b> хорошо видно, что при
больших <i>n</i> код Хемминга начинает работать на пользу.
 
:<math>C(p,\varepsilon)=\min_{n}{KPS(p,n,\varepsilon)}</math>
 
На рисунке&nbsp;<b>(fig:kpseff)</b> показан график этой функции и из
 
На рисунке&nbsp;\ref{fig:kpseff} показан график этой функции и из
него ясно, что код Хемминга можно использовать с пользой
всегда — при любых <math>\varepsilon</math> и <i>p</i>, если у нас есть
позволяет осуществлять алгебраические интерпретации кодирования.
Заметим, в частности, что как коды Хемминга, так и циклические
коды ''линейны'':\\ 1) отношения (\ref{<b>(eq:hem})</b>) на
с.&nbsp;\pageref{eq:hem}, связывающие контрольные биты кода Хемминга с
другими линейны,\\ 2) остаток от деления суммы многочленов на
<math>G\mathbb{F}(2)^n</math>. Поясним на примерах. Ниже представлена
матрица кода Хемминга <math>Hem(7,4)</math> (см.
соотношения&nbsp;(\ref{<b>(eq:hem})</b>)). Исходное слово есть
<math>{\mathbf{w}_{in}=\overline{b_3b_5b_6b_7}}</math>, а результирующее
<math>{\mathbf{w}_{out}=\overline{b_1b_2b_3b_4b_5b_6b_7}=\mathbf{A}_{Hem(7,4)}\mathbf{w}_{in}}</math>
(слова мы будем воспринимать как столбцы).
 
 
:<math>
0&0&0&1
\end{array}</math>
 
 
Процесс выявления ошибок тоже линейная операция, она
<math>\mathbf{s}</math> называется ''синдромом ошибки''. <i>i</i>-ый разряд
слова <math>\mathbf{s}</math> контролирует <i>i</i>-ое соотношение в
(\ref{<b>(eq:hem})</b>) и, таким образом, <math>\mathbf{s}</math> равно сумме номеров
бит в которых произошла ошибка, как векторов в <math>G\mathbb{F}(2)^3</math>.
 
 
:<math>\mathbf{H}_{Hem(7,4)}=\begin{array}{||ccccccc||}
\end{array}.
</math>
 
 
Кроме рабочей и проверочной матриц есть ещё множество ''порождающих матриц <math>\mathbf{G}</math>'' и ''декодирующих матриц
строчками. Матрицы&nbsp;<math>\mathbf{A}</math>, <math>\mathbf{H}</math> и <math>\mathbf{G}</math>
всегда удовлетворяют отношениям
 
 
:<math>\mathbf{H}\cdot \mathbf{A}=\mathbf{0}_{rm},\;
таким свойством может быть несколько. Множество декодирующих
матриц определяется рабочей матрицей:
 
 
:<math>\mathbf{D}\cdot \mathbf{A}=\mathbf{E}_m,</math>
линейную комбинацию строчек из проверочной матрицы. Следует
отметить, что процесс исправления ошибок для кодов Хемминга
нелинеен и его нельзя &laquo;«внедрить&raquo;» в декодирующую матрицу.
 
Сформулируем теперь основные моменты, касающиеся линейных кодов.
уровня групповые ошибки.
 
<div class="task"><b>Задача 8.</b>
\begin{task}
 
Для данной проверочной матрицы постройте рабочую и декодирующую
матрицу. Докажите, что кодовое расстояние равно 4.
2) Кодовое расстояние равно минимальному количеству линейно
зависимых столбцов в <math>\mathbf{H}</math>.
\end{task}
 
<b>Конец задачи.</b></div>
\begin{task}
 
<div class="task"><b>Задача 9.</b>
 
Посторойте декодирующую и проверочную матрицу для циклического
кода с <math>G(x)=x^{3}+x+1</math> и <math>m=4</math> при условии, что в качестве
\end{array}.</math>
 
<b>Конец задачи.</b></div>
 
\end{task}
 
===*Коды Рида-Соломона===
битов. Различия между ними незначительные.
 
\begin{<div align="center}">
\begin{figure}[h!]
\centering\includegraphics[clip=true,
width=0.88\textwidth]{pictures/frame.eps} \caption{Типовая
структура кадра} \label{<b>(fig:frame})</b>
\end{figure}
</div>
\end{center}
 
На рис.&nbsp;<b>(fig:frame)</b> показана типовая структура кадра.
 
На рис.&nbsp;\ref{fig:frame} показана типовая структура кадра.
Поле адреса используется для адресации терминала, если их
несколько на линии. Для линий точка-точка это поле
используется для различия команды от ответа.
 
 
* Поле <i>Control</i> используется для последовательных номеров кадров, подтверждений и других нужд.
 
Организация поля <i>Control</i> для этих трех видов кадров показана на
рис.&nbsp;\ref{<b>(fig:cfield})</b>. Как видно из размера поля <i>Seq</i> в окне
отправителя может быть до <i>7</i> неподтверждённых кадров. Поле
<i>Next</i> используется для посылки подтверждения вместе с
первого не переданного кадра. Какой вариант будет использован —
это параметр.
 
\begin{center}
<div align="center">
\begin{figure}[h!]
\centering\includegraphics[clip=true,
(б) Управляющий кадр (<math>Supervisory</math>)\\(в) Ненумерованный
кадр (<i>Unnumbered</i>) }
\label{<b>(fig:cfield})</b>
\end{figure}
</div>
\end{center}
 
 
Разряд <math>P/F</math> использует при работе с группой терминалов.
 
<math>Supervisory</math> кадры имеют четыре типа кадров.
 
 
* Тип 0 — уведомление в ожидании следующего кадра (RECEIVE READY). Используется когда нет встречного трафика, чтобы передать уведомление в кадре с данными.
481

правка