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

==Аннотация==

 

значений которой - слова фиксированной длины <math>r</math>.

 

контрольная сумма вычисляется заново и сравнивается с той, что

храниться в кадре. Если они различаются, то это признак ошибки

нет единого таймера, нет гарантии, что эта пауза сохраниться или,

наоборот, не появятся новые. Так как временные методы ненадёжны,

* счетчик символов;

* вставка специальных стартовых и конечных символов или последовательностей бит;

Второй метод построен на вставке специальных символов.

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

для конца кадра. <math>DLE</math> — Data Link Escape; <math>STX</math> — Start

TeXt, <math>ETX</math> — End TeXt. При этом методе если даже была

 

===Контроль ошибок===

Решив проблему разбиения на кадры, мы приходим к следующей

проблеме: как обеспечить, чтобы кадры, пройдя по физическому

надлежащей последовательности и в надлежащем виде?

 

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

виде кадра подтверждения, а также специального кодирования,

заново.

 

кадр исчезнет целиком. В этом случае получатель не будет

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

считать, что кадр потерян и повторит его еще раз.

 

тот же кадр получатель получит дважды. Как быть? Для решения

этой проблемы каждому кадру присваивают порядковый номер. С

 

===Управление потоком===

Другая важная проблема, которая решается на канальном уровне

— управление потоком. Вполне может

 

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

===Характеристики ошибок===

Физическая среда, по которой передаются данные не может быть

абсолютно надёжной. Более того, уровень шума бывает очень

 

Основной характеристикой ''интенсивности помех'' в канале

вероятности инвертирования бита, при условии что, он был

передан по каналу и получен на другом конце.

битами.

 

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

1000 бит, а уровень ошибки 0,001 на бит. Если ошибки

1-0.999^{1000}</math>) блоков будут содержать ошибки. Если же они

возникают группами по 100 сразу, то ошибки будут содержать

 

и есть возможность их исправить. Групповые ошибки портят

кадр безвозвратно. Требуется его повторная пересылка, но в

Для надёжной передачи кодов было предложено два основных метода.

 

данных нескольких &laquo;лишних&raquo; битов так, чтобы, анализируя

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

 

Такое деление условно. Более общий вариант — это коды

<math>l<k</math>.

 

===* Элементы теории передачи информации===

''Информационным каналом'' называется пара ''зависимых''

случайных величин <math>\{\xi_{in},\,\xi_{out}\}</math>, одна из них

называется входом другая выходом канала. Если случайные величины

дискретны и конечны, то есть имеют конечные множества событий:

то канал определяется матрицей условных вероятностей

<math>\|r_{ij}\|</math>, <math>r_{ij}</math> — вероятность того, что на выходе

выходе вычисляется по формуле

 

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

<math>\Omega_{in}\times\Omega_{out}</math> равно

 

 

Информация <math>I(\{\xi_{in},\,\xi_{out}\})</math>, передаваемая через

 

:<math>

I(\{\xi_{in}\,\xi_{out}\})=H(\xi_{in})+H(\xi_{out})-H(\{\xi{in},\xi_{out}\}),

 

Если случайные величины <math>\xi_{in}</math> и <math>\xi_{out}</math> независимы (то

<math>\{\xi_{in},\,\xi_{out}\}</math> невозможно передавать информацию и

<math>I(\{\xi_{in},\,\xi_{out}\})=0</math>. Понять суть формулы

величины равна информации, которую мы получаем при одном её

измерении. <math>H(\xi_{in})</math> и <math>H(\xi_{out})</math> — информация, которая

меры{{ref|note1}} есть выражение

аналогичное (\ref{eq:inf}):

 

 

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

называется пропускной способностью канала

 

:<math>

C(\|r_{ij}\|)=\max_{p_i}I(\{\xi_{in}\,\xi_{out}\}).

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

\begin{task}

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

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

 

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

 

 

:<math>

\|r_{ij}\|=\begin{array}{||cc||} 1-p &p\\ p& 1-p

\end{array}\;.

инвертирован). Его пропускная способность равна

Эта функция является решением задачи на максимум (\ref{eq:cdef})

для матрицы&nbsp;(\ref{eq:sm}).

Эта функция <math>C(p)</math> (рис.&nbsp;\ref{fig:cideal}) определяет предел

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

нужно будет передать&nbsp;<math>n\geqslant m/C</math>. А точнее, всякое

помехоустойчивое кодирование, обеспечивающее вероятность

раздувает данные в <math>k_{\varepsilon}(m,p)</math> раз и

 

Кодирование, при котором в этом пределе достигается

равенство, называется ''эффективным''. Отметим, что

\begin{task}

\label{task:dual}

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

\end{task}

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

Оказывается, вероятность ошибки растет не так уж и быстро.

Например, если по каналу передавать данных в два раза

\begin{center}

\begin{figure}[t!]

\centering\includegraphics[clip=true,

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

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

 

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

Конструкция его такова: к исходному слову добавляется бит

 

В случае вероятных групповых ошибок эту технику можно

каждого столбца вычислим бит чётности и разместим его в

дополнительной строке. Матрица затем передается по строкам. По

 

\begin{task}

передаче произошли ошибки и мы их не заметили равна

Что можно привести к виду

\begin{array}{l @{} l}

P_{miss}(2,n,p)&={{((1-p)+p)^n+((1-p)-p)^n -2(1-p)^n}\over 2}=\\

&={{1-2(1-p)^n+(1-2p)^n}\over 2}.

\end{array}

Например, при <math>n=1000</math> и <math>p=10^{-6}</math> получаем <math>P_{miss}\approx

4.99\cdot 10^{-7}</math>

\begin{task}[*]

\label{task:errmod} Пусть у нас есть возможность контролировать

равна <math>P_{miss}(d,n,p)</math>:

\begin{array}{r@{}c@{}l}

P_{miss}(2,n,p)&=&{1+(1-2p)^n-2(1-p)^n \over 2},\\

2}\cos(n\arctan{p\over (1-p)})-4(1-p)^n \over 4}.

\end{array}

''Примечание.'' Интерес здесь представляет неявно

заданная функция <math>n(d,P_{miss},p)</math>, а точнее даже коэффициент

содержания полезной информации

бит как функция от величины шума и вероятности незамеченных

ошибок. Чем выше желаемая надёжность передачи, то есть чем меньше

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

передачи, и вероятность незамеченной ошибки равна

При <math>n=2</math> получаем <math>P_{miss}(2,2,p)=p^2</math>, это соответствует

дублированию каждого бита. Рассмотрим общую идею того, как с

высокой надёжности передачи.

 

метрика Хемминга: расстояние Хемминга между двумя словами

равно количеству несовпадающих бит. Например,

\begin{task}

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

\end{task}

преобразовать одно слово в другое. В описанном ниже

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

находятся на расстоянии <math>\rho_H\geqslant 3</math>. Если мы хотим

от друга на расстояние <math>\geqslant d+1</math>. Если мы хотим

исправлять ошибки, то надо чтобы кодослова отстояли друг от

друга на <math>\geqslant 2d+1</math>. Действительно, даже если

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

слову, чем к какому-либо еще, и следовательно можно

которого есть только четыре ''допустимых кодовых

слова'':\\

 

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

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

 

Отметим что имеет смысл говорить о двух коэффициентах:\\

\begin{tabular}{l}

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

<math>k(m)=\frac{n(m)}{m}</math> — коэффициент раздувания информации

\end{tabular}\\

 

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

 

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

или циклические избыточные коды ('''Cyclic Redundancy Code

 

соответствует полиному степени <math>k-1</math>. Самый левый бит строки

представляет полином <math>x^5+x^4+x^0</math>. Коэффициенты полинома

принадлежат полю <math>G\mathbb{F}(2)</math> вычетов по модулю&nbsp;2.

сообщения на <math>G(x)</math>, либо добавить к нашему сообщению некоторое

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

 

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

блоку так, чтобы получился полином кратный генератору

<math>G(x)</math>. Когда получатель получает блок с контрольной суммой,

0</math>, то были ошибки при передаче.

 

 

 

Рис.&nbsp;\ref{fig:crc} иллюстрирует этот алгоритм для блока

 

\begin{figure}[h!]

\end{tabular}}

\centering\includegraphics[clip=true,

\end{figure}

 

 

Существует три международных стандарта на вид <math>G(x)</math>:

 

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

 

 

к задаче&nbsp;\ref{task:errmod} было указано как можно получить

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

ошибки была меньше&nbsp;<math>P_{miss}</math>.

 

\label{task:err}

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

правильность передачи &laquo;фиксировалось контрольной суммой&raquo;. Найти

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

\end{task}

\pb''Решение''

(см.&nbsp;задачу&nbsp;\ref{task:dual}). Кроме того мы хотим сообщать

об ошибке в передаче. Её вероятность равна <math>(1-p)^m</math>, а

значит информация, заложенная в этом сообщении,

<math>H((1-p)^m)</math>. В итоге получаем <math>n=mC(p)+H((1-p)^m)</math> и

Заметим, что <math>k(1,p)=1</math> — когда блок имеет размер один бит,

сообщение об ошибке в нём равносильно передаче самого бита.

 

количество бит на одно сообщение равно <math>m k(m,p)/C(p)</math>, то есть

теоретическая оценка для количества лишних бит равна

Понятно, что данная теоретическая оценка занижена.

 

 

===Коды Хемминга===

Элементарный пример кода исправляющего ошибки был показан на

странице&nbsp;\pageref{simplecode}. Его обобщение очевидно. Для

3</math>. Оказывается это число можно сделать сколь угодно близким к

единице с помощью кодов Хемминга. В частности, при кодировании

 

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

контрольных. Каждое из <math>2^m</math> правильных сообщений имеет <math>n=m+r</math>

его неправильных вариантов с ошибкой в одном бите. Такими

слов <math>2^n</math>, то

 

\begin{array}{c}

(n+1)2^m \leqslant 2^n\\ (m+r+1)\leqslant 2^r.

\end{array}

 

метода, предложенного Хеммингом. Идея его в следующем: все

остальные — биты сообщения. Каждый контрольный бит

отвечает за чётность суммы некоторой группы бит. Один и тот

же бит может относиться к разным группам. Чтобы определить

бит относится к трём группам — к группе, чья чётность

подсчитывается в 1-ом бите, к группе 2-ого и к группе 8-ого

 

:<math>

\begin{array}{l}

b_1=b_3+b_5+b_7+\dots \\

b_8=b_9+b_{10}+b_{11}+b_{12}+b_{13}+b_{14}+b_{15}\dots \\

\end{array}

 

Код Хемминга оптимален при <math>n=2^r-1</math> и <math>m=n-r</math>. В общем случае

<math>m=n-[\log_2(n+1)]</math>, где <math>[x]</math> — ближайшее целое число

<math>\leqslant x</math>. Код Хемминга мы будем обозначать <math>Hem(n,m)</math> (хотя

 

Пример для <math>Hem(15,11)</math>:

\fbox{10110100111}\to

\fbox{\fbox{0}\fbox{0}1\fbox{1}011\fbox{0}0100111}\\

\lefteqn{b_9}\hphantom{010011}

\lefteqn{b_{15}}\hphantom{1}

 

 

получатель проверяет каждый контрольный бит на предмет

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

бит, где произошла ошибка. Если ошибка одна, то это число есть

просто номер ошибочного бита.

 

несовпадение чётности, то ошибка в 11 разряде, так как

только он связан одновременно с этими тремя контрольными

 

\begin{task}

\infty</math>.

\end{task}

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

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

Расположим их в виде матрицы одно слово — строка. Обычно,

передают слово за словом. Но мы поступим иначе, передадим слово

приёме всех слов матрица восстанавливается. Если мы хотим

восстановленной матрицы будет не более одной ошибки. А с

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

 

===Анализ эффективности===

Начнём c небольшого примера. Пусть у нас есть канал с уровнем

ошибок <math>p=10^{-6}</math>. Если мы хотим исправлять единичные ошибки при

передаче блоками по <math>1023=2^{10}-1</math> бит, то среди них потребуется

таких блоков потребуется <math>\Delta=10\,000</math> контрольных бит.

 

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

бита чётности. И если мы применим технику повторной передачи, то

дополнительно и примерно <math>0.001\approx

p_{1014}=1-(1-10^{-6})^{1014}</math> из них придется пересылать

дополнительная нагрузка линии составляет <math>\Delta\approx

1000+1001</math>, что меньше <math>10\,000</math>. Но это не значит, что код

 

Рассмотрим этот вопрос подробнее. Пусть нам нужно передать

и будем передавать двумя способами

— с помощью кодов Хемминга и без них. При этом будем

блоками по <math>m'</math> бит с повторной пересылкой в случае

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

Где <math>P_{r}=(1-(1-p)^{m'})(1-\varepsilon)</math> — вероятность

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

вероятность того, что мы её заметим. Коэффициент раздувания

равен

 

2) '''С кодом Хемминга.'''\\ При кодировании методом

 

:<math>

\begin{array}{c}

k_{\varepsilon}(m)m= n-\log_2(n+1)

\end{array}

 

безошибочной передачи равна <math>{P_0=(1-p)^n}</math>. Вероятность

одинарной ошибки <math>{P_1=n p^1(1-p)^{n-1}}</math>. Вероятность того,

что произошло более чем одна ошибка, и мы это заметили

— в этом случае требуется повторная передача кадра.

Количество передаваемых данных:

где <math>n(m)</math> неявно определённая с помощью (\ref{eq:hnm})

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

 

:<math>

\begin{array}{l}

\\[0.8mm]

 

Легко обнаружить что при <math>n>3444</math> и <math>p=10^{-6}</math> код Хемминга

 

\begin{center}

\begin{figure}[h!]

\centering\includegraphics[clip=true,

width=0.48\textwidth]{pictures/kps.eps}

\centering\includegraphics[clip=true,

width=0.48\textwidth]{pictures/kps2.eps} \caption{

в канале с помехами как функция размера элементарного блока.}

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

\begin{center}

\begin{figure}[h!]

\centering\includegraphics[clip=true,

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

\end{center}

 

формулах (\ref{eq:kps}) можно оценить как

 

 

Напомним, что <math>\varepsilon</math> есть параметр желаемой

ошибочной передачи блока при условии, что &laquo;контрольная сумма

сошлась&raquo; и кадр засчитан правильно переданным.

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

 

 

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

 

 

кода. Эффективность кода определяется функцией

 

На рисунке&nbsp;\ref{fig:kpseff} показан график этой функции и из

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

 

===Коды как линейные операторы===

То, что на множестве {0,1} есть структура числового поля,

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

(слова мы будем воспринимать как столбцы).

 

\mathbf{A}_{Hem(7,4)}=\begin{array}{||cccc||}

1&1&0&1\\ 1&0&1&1\\ 1&0&0&0\\ 0&1&1&1\\ 0&1&0&1\\ 0&0&1&0\\

0&0&0&1

 

Процесс выявления ошибок тоже линейная операция, она

<math>\mathbf{s}=\overline{s_1s_2s_3}=\mathbf{H}\mathbf{w'}_{out}</math> в

случае правильной передачи должно быть равно 000. Значение

(\ref{eq:hem}) и, таким образом, <math>\mathbf{s}</math> равно сумме номеров

бит в которых произошла ошибка, как векторов в <math>G\mathbb{F}(2)^3</math>.

 

1&0&1&0&1&0&1\\ 0&1&1&0&0&1&1\\0&0&0&1&1&1&1

Заметим, что столбцы проверочной матрицы представляют собой

последовательно записанные в двоичной форме натуральные

Вычиcление рабочей матрицы для циклических кодов

основывается на значениях <math>G_n(x)=x^n\; mod\; G(x)</math>. Верхняя

<math>G_n</math>, <math>G_{n-1}</math>,

\dots, <math>G_{n-r}</math>. Например, для <math>G(x)=x^3+x+1</math> и <math>m=4</math> имеем

<math>r=3</math>, <math>n=7</math> и

\begin{array}{|c|c|c|c|c|c|c|c|}

G_0&G_1&G_2&G_3&G_4&G_5&G_6&G_7\\

001&010&100&011&110&111&101&001

\end{array}

Рабочая и проверочная матрицы равны

G_5 G_4 G_3

\mathbf{A}=\begin{array}{||cccc||}

1&0&0&0\\ 0&1&0&0\\ 0&0&1&0\\ 0&0&0&1\\ 1&1&1&0\\

1&1&1&0&1&0&0\\ 0&1&1&1&0&1&0\\1&1&0&1&0&0&1

\end{array}.

 

Кроме рабочей и проверочной матриц есть ещё множество ''порождающих матриц <math>\mathbf{G}</math>'' и ''декодирующих матриц

порождающей. В частности, рабочая матрица является порождающей.

Способность обнаруживать и исправлять ошибки однозначно

 

Действительно, в порождающей и рабочей матрицах можно осуществлять

всегда удовлетворяют отношениям

 

<math>\mathbf{0}_{rm}</math> — нулевая матрица <math>r\times m</math>.\\ Любая

порождающая матрица может использоваться как

матриц определяется рабочей матрицей:

 

где <math>\mathbf{E}_m</math> — единичная матрица <math>m\times m</math>. На

декодирующую матрицу для <math>Hem(7,4)</math> и <math>CRC_{n=7,\;m=7}</math>:

\mathbf{D}_{H_{7,4}}=\begin{array}{||ccccccc||} 0&0&1&0&0&0&0\\

0&0&0&0&1&0&0\\0&0&0&0&0&1&0\\0&0&0&0&0&0&1

0&1&0&0&0&0&0\\0&0&1&0&0&0&0\\0&0&0&1&0&0&0

\end{array}.

К каждой строчке декодирующей матрицы можно добавить любую

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

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

 

 

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

Хемминга и их композиции. Например <math>Hem(7,4)</math> плюс проверка на

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

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

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

1&0&1&0&1&0&1&0\\

0&1&1&0&0&1&1&0\\0&0&0&1&1&1&1&0\\1&1&1&1&1&1&1&1

''Подсказка ''\\

1) Это проверочная матрица <math>Hem(7,4)</math> плюс условие на чётность

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

рабочей матрицы использовалась матрица

\begin{array}{||cccc||}

0&0&0&1\\0&0&1&0\\0&1&0&1\\1&0&1&1\\0&1&1&0\\1&1&0&0\\1&0&0&0

\end{task}

 

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

После перехода на язык линейной алгебры естественно возникает

желание изучить свойства линейных кодов над другими конечными

Рида-Соломона.

 

 

Напомним, что существует бесконечное количество конечных полей, и

таким числом элементов, которое обозначается как

<math>G\mathbb{F}(n)</math>. Простейшая реализация этого поля — множество

многочленов с действительными коэффициентами неприводимыми

многочленами являются только квадратные многочлены с

 

==Примеры протоколов канала данных==

Здесь мы познакомимся с группой протоколов давно известных, но

по-прежнему широко используемых. Все они имеют одного

 

Все эти протоколы построены на одних и тех же принципах. Все

 

 

 

разделения кадров и постоянно передаются по незанятой линии

в ожидании кадра. Существуют три вида кадров: <math>Information</math>,

 

передаваемым кадром. Подтверждение может быть в форме номера

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

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

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

\begin{center}

\begin{figure}[h!]

\centering\includegraphics[clip=true,

\parbox{0.66\textwidth}{\small (а) Информационный кадр (<math>Information</math>)\\

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

\label{fig:cfield}

\end{figure}

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

Когда компьютер приглашает терминал к передаче он

 

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

 

 

 

используются для целей управления, но чаще для передачи данных

при ненадёжной передаче без соединения.

повреждение управляющего кадра.