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

только этому уровню:

* реализация сервиса для сетевого уровня,

 

Основная задача канального уровня — обеспечить сервис сетевому уровню,

посылке данных.

 

содержательной части кадра (слова длины <math>m</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) исходные данные (б) посылаемые данные. Жирным отмечены вставленные нули.

 

Таким образом, кадр легко может быть распознан по

кадров тот может принять. Получатель сообщает ему определённое

число кадров. Отправитель после того, как передаст это число

 

==Помехоустойчивое кодирование==

 

''Первый'' заключается в добавлении в передаваемый блок

полученный блок, можно было бы сказать есть в переданном

блоке ошибки или нет. Это, так называемые, '''коды с

<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}} есть выражение

 

:<math>\mu(A\wedge B)=\mu(A)+\mu(B)-\mu(A\vee B).</math>

 

Распределение входной случайной величины <math>\xi_{in}</math> мы можем

 

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

<b>(task:shanon)</b> Каково максимальное количество информации,

которое можно передать с одним битом по каналу

<math>\{\xi_{in},\,\xi_{out}\}</math>?

 

{\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>

 

 

\begin{figure}[t!]

\centering\includegraphics[clip=true,

width=0.75\textwidth]{pictures/cideal.eps} \caption{ <math>C(p)</math> —

Пропускная способность канала как функция вероятности

\end{figure}

 

помехоустойчивого кодирования — если мы хотим с абсолютной

надёжностью передать по каналу с пропускной способностью <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>

 

образом

Мы хотим передавать информацию со скоростью <i>V</i> по каналу с

пропускной способностью <i>C</i>. Какова минимальная вероятность

ошибочной передачи одного бита?

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

 

ста будут переданы с ошибкой.

 

\begin{figure}[t!]

\psfrag{v}{<i>v</i>} \psfrag{p}{ <math>p(v)</math>}

минимальная вероятность ошибки в одном бите как функция от

отношения скорости передачи и пропускной способности <math>v=V/C</math>.}

\end{figure}

Построение конкретных способов кодирования, приближающихся

по пропускной способности к теоретической границе —

сложная математическая задача.

 

Простым примером

кода с обнаружением одной ошибки является код с битом чётности.

позволяет обнаружить групповые ошибки длины <math>\leqslant n</math>.

 

Слово длиной <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>

 

Следующая задача повышенной сложности.

 

сумму единичек по модулю&nbsp;<i>d</i>. Тогда вероятность нефиксируемых

ошибок в слове длиной <i>n</i> при передаче его по каналу с шумом <i>p</i>

вероятность <math>P_{miss}</math>, тем меньше коэффициент содержания

полезной информации.

 

Итак, с помощью одного бита чётности мы повышаем надёжность

:<math>\rho_H(10001001,10110001)=3.</math>

 

 

Докажите, что <math>\rho_H</math> метрика.

 

Если два слова находятся на расстоянии <i>r</i> по Хеммингу,

между двумя различными допустимыми кодовыми словами

называется ''расстоянием Хемминга данного кода''.

 

Элементарный пример помехоустойчивого кода — это код, у

 

:<math>0000000000,\; 0000011111,\; 1111100000,\; 1111111111.</math>

 

Расстояние по Хеммингу у этого кода 5, следовательно он может

Здесь мы подошли к довольно трудной задаче —

минимизировать коэффициент раздувания для требуемой

 

===Циклические коды===

Полином <math>G(x)</math> тем лучше, чем больше среднее расстояние Хемминга

на парах допустимых полиномов.

 

Есть два очевидных способа кодирования сообщения в полином,

Отправитель и получатель заранее договариваются

о конкретном ''полиноме-генераторе'' <math>G(x)</math>. Пусть степень

равна <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>, и есть результат.''

<i>1101011011</i> и <math>{G(x)=x^4+x+1}</math>.

 

width=0.75\textwidth]{pictures/crc2.eps}

\caption{CRC — полиномиальное кодирование}

\end{figure}

 

одиночные, двойные ошибки, групповые ошибки длины не более 16 и

нечётное число изолированных ошибок с вероятностью <i>0.99997</i>.

 

===* Теоретический предел===

значение коэффициента содержания полезной информации (КПС) на

один бит, если передавать данные по каналу с шумом <i>p</i> словами

абсолютной точностью.

 

Мы хотим передавать информацию блоками, которые содержали

бы <i>m</i> бит полезной информации, так, чтобы

вероятность ошибки в одном бите равнялась <i>p</i>, а

минимальный размер блока <math>n(m,p)</math> и коэффициент раздувания

<math>k=\frac{n(m)}{m}</math>.

''Решение.''

Для передачи <i>m</i> бит с вероятностью ошибки в отдельном бите

<i>p</i> требуется передать <math>m C(p)</math> бит

об ошибке в передаче. Её вероятность равна <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{Кодирование

\end{figure}

 

 

Покажите, что <math>KPS_{Hem(n,m)}\to 1</math> при <math>n\to

\infty</math>.

 

 

Код Хемминга может исправлять только единичные ошибки. Однако,

кодирование, позволяющее с вероятностью <math>1-\varepsilon</math>

определять ошибочность передачи. Это осуществляется путем

раздувания для этого кодирования <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>

 

функция. Удобно записать соответствующие коэффициенты

полезного содержания:

\\[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{figure}[h!]

\psfrag{knc}{кпс} \psfrag{n}{<i>n</i>}

Темный график — ''с кодированием Хемминга'';

\\Параметры: <math>\varepsilon=10^{-6}\;</math>; <math>p=10^{-6}.</math>}

\end{figure}

\begin{figure}[h!]

\psfrag{C}{<i>C</i>} \psfrag{p}{<i>p</i>}

\parbox{0.97\textwidth}{ \small Светлый график — ''без кодирования Хемминга'';\\ Темный график — ''с кодированием Хемминга'';\\Тонкий график — теоретический

предел, задаваемый функцией&nbsp;<math>C(p)</math>\\Параметры:

\end{figure}

 

Значение <math>KPS_{\varepsilon}(n)</math> используемое в

 

:<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> — вероятности

Такое выражение для <math>KPS_{\varepsilon}(p,n)=\frac{m}{n}</math>

получается из формулы

 

:<math>\varepsilon=\frac{2^m-1}{2^n-1}</math>

 

Но это безусловно лишь оценочная формула. Оптимальное

зависит от <i>p</i>.

 

больших <i>n</i> код Хемминга начинает работать на пользу.

 

:<math>C(p,\varepsilon)=\min_{n}{KPS(p,n,\varepsilon)}</math>

 

него ясно, что код Хемминга можно использовать с пользой

всегда — при любых <math>\varepsilon</math> и <i>p</i>, если у нас есть

позволяет осуществлять алгебраические интерпретации кодирования.

Заметим, в частности, что как коды Хемминга, так и циклические

с.&nbsp;\pageref{eq:hem}, связывающие контрольные биты кода Хемминга с

другими линейны,\\ 2) остаток от деления суммы многочленов на

<math>G\mathbb{F}(2)^n</math>. Поясним на примерах. Ниже представлена

матрица кода Хемминга <math>Hem(7,4)</math> (см.

<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>-ое соотношение в

бит в которых произошла ошибка, как векторов в <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>

линейную комбинацию строчек из проверочной матрицы. Следует

отметить, что процесс исправления ошибок для кодов Хемминга

 

Сформулируем теперь основные моменты, касающиеся линейных кодов.

уровня групповые ошибки.

 

Для данной проверочной матрицы постройте рабочую и декодирующую

матрицу. Докажите, что кодовое расстояние равно 4.

2) Кодовое расстояние равно минимальному количеству линейно

зависимых столбцов в <math>\mathbf{H}</math>.

 

Посторойте декодирующую и проверочную матрицу для циклического

кода с <math>G(x)=x^{3}+x+1</math> и <math>m=4</math> при условии, что в качестве

\end{array}.</math>

 

 

===*Коды Рида-Соломона===

битов. Различия между ними незначительные.

 

\begin{figure}[h!]

\centering\includegraphics[clip=true,

width=0.88\textwidth]{pictures/frame.eps} \caption{Типовая

\end{figure}

 

Поле адреса используется для адресации терминала, если их

несколько на линии. Для линий точка-точка это поле

используется для различия команды от ответа.

 

* Поле <i>Control</i> используется для последовательных номеров кадров, подтверждений и других нужд.

 

Организация поля <i>Control</i> для этих трех видов кадров показана на

отправителя может быть до <i>7</i> неподтверждённых кадров. Поле

<i>Next</i> используется для посылки подтверждения вместе с

первого не переданного кадра. Какой вариант будет использован —

это параметр.

\begin{figure}[h!]

\centering\includegraphics[clip=true,

(б) Управляющий кадр (<math>Supervisory</math>)\\(в) Ненумерованный

кадр (<i>Unnumbered</i>) }

\end{figure}

 

Разряд <math>P/F</math> использует при работе с группой терминалов.

 

<math>Supervisory</math> кадры имеют четыре типа кадров.

 

* Тип 0 — уведомление в ожидании следующего кадра (RECEIVE READY). Используется когда нет встречного трафика, чтобы передать уведомление в кадре с данными.