Викиучебник

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

Интерактивная навигация по истории
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
мНет описания правки
Строка 1:
{{Википедия|Коды, исправляющие ошибки}}
==Аннотация==▼
 
▲== Аннотация ==
Здесь мы рассмотрим основные принципы и методы надёжной и
эффективной передачи данных между двумя машинами, соединёнными
Строка 10:
в какой они были переданы.
 
== Канальный уровень ==
 
На уровне канала данных решается ряд проблем, присущих
только этому уровню:
Строка 17 ⟶ 16 :
* разбиение потока бит на кадры,
* управление потоком кадров,
* обработка ошибок передачи.
 
Основная задача канального уровня  — обеспечить сервис сетевому уровню,
а это значит помочь передать данные с сетевого уровня одной машины на
сетевой уровень другой машины.
 
=== Разбиение на кадры ===
Сервис, создаваемый канальным уровнем для сетевого, опирается на
сервис, создаваемый физическим уровнем. На физическом уровне
Строка 31 ⟶ 30 :
канальном уровне по обнаружению и исправлению ошибок.
 
Типовой подход к решению этой проблемы  — разбиение потока битов
на кадры и подсчёт <i>''контрольной суммы</i>'' для каждого кадра при
посылке данных.
 
<b>'''Контрольная сумма</b> ''' — это, в общем смысле, функция от
содержательной части кадра (слова длины <math>m</math>), область
значений которой  — слова фиксированной длины <math>r</math>.
 
Эти <i>''r</i>'' бит добавляются обычно в конец кадра. При приёме
контрольная сумма вычисляется заново и сравнивается с той, что
хранится в кадре. Если они различаются, то это признак ошибки
Строка 45 ⟶ 44 :
ошибки, например, сбросить плохой кадр, послать сообщение об
ошибке тому кто прислал этот кадр. Разбиение потока битов на
кадры  — задача не простая. Один из способов  — делать
временную паузу между битами разных кадров. Однако, в сети, где
нет единого таймера, нет гарантии, что эта пауза сохранится или,
Строка 51 ⟶ 50 :
то применяются другие. Здесь мы рассмотрим три основных:
* счетчик символов;
* вставка специальных стартовых и конечных символов или последовательностей бит;
* специальная кодировка на физическом уровне.
 
Строка 57 ⟶ 56 :
символов в кадре. При приёме число принятых символов
подсчитывается опять. Однако, этот метод имеет существенный
недостаток  — счётчик символов может быть искажён при передаче.
Тогда принимающая сторона не сможет обнаружить границы кадра.
Даже обнаружив несовпадение контрольных сумм, принимающая
Строка 66 ⟶ 65 :
Обычно для этого используют управляющие последовательности:
последовательность <math>DLE STX</math> для начала кадра и <math>DLE ETX</math>
для конца кадра. <math>DLE</math>  — Data Link Escape; <math>STX</math>  — Start
TeXt, <math>ETX</math>  — End TeXt. При этом методе если даже была
потеряна граница текущего кадра, надо просто искать
ближайшую последовательность <math>DLE</math> <math>STX</math> или <math>DLE</math> <math>ETX</math>. Но
Строка 78 ⟶ 77 :
По мере развития сетей эта связь становилась все более и более
обременительной и был предложен новый очевидный кодонезависимый
метод  — управляющие последовательности должны быть
бит-ориентированными. В частности, в протоколе <math>HDLC</math> каждый кадр
начинается и заканчивается со специального флаг-байта: 01111110.
Строка 84 ⟶ 83 :
кадра, обязательно вставит&nbsp;0. Принимающая сторона, приняв 5
последовательных единиц обязательно удалит следующий за ними 0,
если таковой будет. Это называется <i>''bit-stuffing</i>''. Если
принято шесть и за ними следует ноль, то это управляющий сигнал:
начало или конец кадра, а в случае, когда подряд идут более шести
единиц,  — сигнал ожидания или аварийного завершения.
 
(а) 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 0 1
Строка 96 ⟶ 95 :
Таким образом, кадр легко может быть распознан по
флаг-байту. Если граница очередного кадра по какой-то
причине была потеряна, то все что надо делать  — ловить
ближайший флаг-байт.
 
Строка 102 ⟶ 101 :
физическая среда. Например, в случае проводной связи для передачи
одного бита используется два импульса. 1&nbsp;кодируется как переход
высокое-низкое, 0  — как низкое-высокое. Сочетания низкое-низкое
или высокое-высокое не используются для передачи данных, и их
используют для границ кадра.
Строка 111 ⟶ 110 :
считается переданным правильно.
 
=== Контроль ошибок ===
Решив проблему разбиения на кадры, мы приходим к следующей
проблеме: как обеспечить, чтобы кадры, пройдя по физическому
Строка 145 ⟶ 144 :
 
{\slshape Итак, таймеры, нумерация кадров, флаг-байты,
кодирование и обратная связь  — вот основные средства на канальном уровне,
обеспечивающие надёжную доставку каждого кадра до сетевого
уровня в единственном экземпляре. Но и с помощью этих
Строка 151 ⟶ 150 :
передачи.}
 
=== Управление потоком ===
Другая важная проблема, которая решается на канальном уровне
— управление потоком. Вполне может
Строка 165 ⟶ 164 :
кадров тот может принять. Получатель сообщает ему определённое
число кадров. Отправитель после того, как передаст это число
кадров, должен приостановить передачу и снова спросить получателя,
как много кадров тот может принять, и&nbsp;т.д.
 
== Помехоустойчивое кодирование ==
=== Характеристики ошибок ===
Физическая среда, по которой передаются данные не может быть
абсолютно надёжной. Более того, уровень шума бывает очень
высоким, например в беспроводных системах связи и телефонных
системах. Ошибки при передаче  — это реальность, которую
надо обязательно учитывать.
 
В разных средах ''характер помех'' разный. Ошибки могут быть
одиночные, а могут возникать группами, сразу по несколько. В
результате помех могут исчезать биты или наоборот  — появляться
лишние.
 
Основной характеристикой ''интенсивности помех'' в канале
является параметр шума  — <i>''p</i>''. Это число от 0 до 1, равное
вероятности инвертирования бита, при условии что, он был
передан по каналу и получен на другом конце.
 
Следующий параметр  — <math>p_2</math>. Это вероятность того же
события, но при условии, что предыдущий бит также был
инвертирован.
Строка 193 ⟶ 192 :
теории. Но, в принципе, можно было бы учитывать аналогичные
вероятности для исчезновения бита, а также ипользовать полную
информацию о пространственной корреляции ошибок,  — то есть
корреляции соседних ошибок, разделённых одним, двумя или более
битами.
Строка 200 ⟶ 199 :
заключаются в следующем. Пусть данные передаются блоками по
1000 бит, а уровень ошибки 0,001 на бит. Если ошибки
изолированные и независимые, то 63 % (<math>0.63\approx
1-0.999^{1000}</math>) блоков будут содержать ошибки. Если же они
возникают группами по 100 сразу, то ошибки будут содержать
1 % (<math>0.01\approx 1-0.999^{10}</math>) блоков.
 
Зато, если ошибки не группируются, то в каждом кадре они невелики,
и есть возможность их исправить. Групповые ошибки портят
кадр безвозвратно. Требуется его повторная пересылка, но в
некоторых системах это в принципе невозможно,  — например,
в телефонных системах, использующие цифровое кодирование,
возникает эффект пропадания слов/слогов.
Строка 214 ⟶ 213 :
Для надёжной передачи кодов было предложено два основных метода.
 
''Первый''  — добавить в передаваемый блок данных нескольких «лишних» бит так, чтобы, анализируя
полученный блок, можно было бы сказать есть в переданном
блоке ошибки или нет. Это, так называемые, '''коды с обнаружением ошибок'''.
 
''Второй''  — внести избыточность настолько, чтобы,
анализируя полученные данные, можно не только замечать
ошибки, но и указать, где именно возникли искажения. Это
'''коды, исправляющие ошибки'''.
 
Такое деление условно. Более общий вариант  — это коды,
обнаруживающие <i>''k</i>'' ошибок и исправляющие <i>''l</i>'' ошибок, где
<math>l \le k</math>.
 
=== * Элементы теории передачи информации ===
''Информационным каналом'' называется пара ''зависимых''
случайных величин <math>\{\xi_{in},\,\xi_{out}\}</math>, одна из них
Строка 233 ⟶ 232 :
дискретны и конечны, то есть имеют конечные множества событий:
 
: <math>\Omega_{in}=\{x_1,\dots, x_a\},\;\Omega_{out}=\{y_1,\dots, y_b\},</math>
 
то канал определяется матрицей условных вероятностей
<math>\|r_{ij}\|</math>, <math>r_{ij}</math>  — вероятность того, что на выходе
будет значение <math>y_i</math> при условии, что на входе измерено
значение <math>x_j</math>.
 
Входная случайная величина определяется распределением
<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>
 
I(\{\xi_{in}\,\xi_{out}\})=H(\xi_{in})+H(\xi_{out})-H(\{\xi{in},\xi_{out}\}),
</math> <b>'''(eq:inf)</b>'''
 
где
: <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> независимы (то
Строка 270 ⟶ 269 :
<math>\{\xi_{in},\,\xi_{out}\}</math> невозможно передавать информацию и
<math>I(\{\xi_{in},\,\xi_{out}\})=0</math>. Понять суть формулы
(<b>'''(eq:inf)</b>''') можно из следующего соображения: энтропия случайной
величины равна информации, которую мы получаем при одном её
измерении. <math>H(\xi_{in})</math> и <math>H(\xi_{out})</math>  — информация, которая
содержится по отдельности во входе и в выходе. Но часть этой
информации общая, её нам и нужно найти. <math>H(\{\xi{in},\xi_{out}\})</math>
равна величине объединённой информации. В теории
меры{{ref|note1}} есть выражение
аналогичное (<b>'''(eq:inf)</b>'''):
 
: <math>\mu(A\wedge B)=\mu(A)+\mu(B)-\mu(A\vee B).</math>
 
Распределение входной случайной величины <math>\xi_{in}</math> мы можем
варьировать и получать различные значения <i>''I</i>''. Её максимум
называется пропускной способностью канала
 
: <math>
 
C(\|r_{ij}\|)=\max_{p_i}I(\{\xi_{in}\,\xi_{out}\}).
</math> <b>'''(eq:cdef)</b>'''
 
Эта функция есть решение задачи
 
<div class="task"><b>'''Задача 1.</b>'''
 
<b>'''(task:shanon)</b>''' Каково максимальное количество информации,
которое можно передать с одним битом по каналу
<math>\{\xi_{in},\,\xi_{out}\}</math>?
 
<b>'''Конец задачи.</b>'''</div>
 
{\slshape Итак, пропускная способность есть функция на
Строка 305 ⟶ 304 :
Стандартный информационный канал это
 
: <math>\Omega_{in}=\Omega_{out}=\{0,1\}.</math>
 
: <math>
 
\|r_{ij}\|=\begin{array}{||cc||} 1-p &p\\ p& 1-p
\end{array}\;.
</math> <b>'''(eq:sm)</b>'''
 
То есть канал с бинарным алфавитом и вероятностью помехи <i>''p</i>''
(<i>''p</i> '' — вероятность того, что бит будет случайно
инвертирован). Его пропускная способность равна
 
: <math>C= 1-H(p)=1+p\log_2p+(1-p)\log_2{(1-p)}.</math>
 
Эта функция является решением задачи на максимум (<b>'''(eq:cdef)</b>''')
для матрицы&nbsp;(<b>'''(eq:sm)</b>''').
 
<div align="center">
Строка 327 ⟶ 326 :
width=0.75\textwidth]{pictures/cideal.eps} \caption{ <math>C(p)</math> —
Пропускная способность канала как функция вероятности
инвертирования бита.} <b>'''(fig:cideal)</b>'''
\end{figure}
</div>
 
Эта функция <math>C(p)</math> (рис.&nbsp;<b>'''(fig:cideal)</b>''') определяет предел
помехоустойчивого кодирования  — если мы хотим с абсолютной
надёжностью передать по каналу с пропускной способностью <i>''C</i>''
сообщение длиной <i>''m</i>'', то минимальное количество бит, которое нам
нужно будет передать&nbsp;<math>n\geqslant m/C</math>. А точнее, всякое
помехоустойчивое кодирование, обеспечивающее вероятность
Строка 340 ⟶ 339 :
раздувает данные в <math>k_{\varepsilon}(m,p)</math> раз и
 
: <math>\lim_{\varepsilon\to 0}\lim_{m\to\infty}k_{\varepsilon}(m,p)\geqslant {1/C(p)}.</math>
 
Кодирование, при котором в этом пределе достигается
Строка 348 ⟶ 347 :
<math>k_0(m,p)=\infty.</math>
 
Задача дуальная <b>'''(task:shanon)</b>''' формулируется следующим
образом
 
<div class="task"><b>'''Задача 2.</b>'''
 
<b>'''(task:dual)</b>'''
Мы хотим передавать информацию со скоростью <i>''V</i>'' по каналу с
пропускной способностью <i>''C</i>''. Какова минимальная вероятность
ошибочной передачи одного бита?
 
<b>'''Конец задачи.</b>'''</div>
 
Решением будет функция заданная неявно
 
<math>C/V=1+p\log_2p+(1-p)\log_2(1-p)</math>, если <math>V/C>1</math>,
 
<math>p(V/C)=0</math>, если <math>V/C\leqslant 1</math>
 
Оказывается, вероятность ошибки растет не так уж и быстро.
Строка 373 ⟶ 372 :
<div align="center">
\begin{figure}[t!]
\psfrag{v}{<i>''v</i>''} \psfrag{p}{ <math>p(v)</math>}
\centering\includegraphics[clip=true,
width=0.75\textwidth]{pictures/pv.eps} \caption{ <math>p(v)</math> —
минимальная вероятность ошибки в одном бите как функция от
отношения скорости передачи и пропускной способности <math>v=V/C</math>.}
<b>'''(fig:pv)</b>'''
\end{figure}
</div>
Строка 386 ⟶ 385 :
сложная математическая задача.
 
=== Метод «чётности» и общая идея ===
Простым примером
кода с обнаружением одной ошибки является код с битом чётности.
Конструкция его такова: к исходному слову добавляется бит
чётности. Если в исходном слове число единичек чётно, то значение
этого бита 0, если нечётно  — 1. Таким образом допустимые слова
этого кода имеют чётное количество единичек. Если получено слово
с нечётным количеством единичек, то при передаче произошла ошибка.
 
В случае вероятных групповых ошибок эту технику можно
скорректировать. Разобъём передаваемые данные на <i>''n</i>'' слов по <i>''k</i>''
бит и расположим их в виде матрицы&nbsp;<math>n\cdot k</math> (<i>''n</i>''&nbsp;столбцов). Для
каждого столбца вычислим бит чётности и разместим его в
дополнительной строке. Матрица затем передается по строкам. По
Строка 404 ⟶ 403 :
позволяет обнаружить групповые ошибки длины <math>\leq n</math>.
 
<div class="task"><b>'''Задача 3.</b>'''
 
Слово длиной <i>''n</i>'' с чётным количеством единиц передано по каналу с
уровнем шума <i>''p</i>''. Покажите, что вероятность того, что при
передаче произошли ошибки и мы их не заметили равна
 
: <math>P_{miss}(2,n,p)=C^2_np^2(1-p)^{n-2}+C^4_np^4(1-p)^{n-4}+\dots+C^{2k}_np^{2k}(1-p)^{n-2k}+\dots
</math>
 
Что можно привести к виду
: <math>
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}.
</math>
Строка 420 ⟶ 419 :
Например, при <math>n=1000</math> и <math>p=10^{-6}</math> получаем <math>P_{miss}\approx 4.99\cdot 10^{-7}</math>
 
<b>'''Конец задачи.</b>'''</div>
 
Следующая задача повышенной сложности.
 
<div class="task"><b>'''Задача 4.</b>''' <b>'''(task:errmod)</b>''' Пусть у нас есть возможность контролировать
сумму единичек по модулю&nbsp;<i>''d</i>''. Тогда вероятность нефиксируемых
ошибок в слове длиной <i>''n</i>'' при передаче его по каналу с шумом <i>''p</i>''
равна <math>P_{miss}(d,n,p)</math>:
 
: <math>
P_{miss}(2,n,p)={1+(1-2p)^n-2(1-p)^n \over 2},
</math>
 
: <math>
P_{miss}(3,n,p)={1+(1-p+e^{\frac{2\pi}{3}\mathbf{i}} p)^n+(1-p+e^{-\frac{2\pi}{3}\mathbf{i}} p)^n-3(1-p)^n\over 3},
</math>
 
: <math>
P_{miss}(4,n,p)={1+(1-p+e^{\frac{\pi}{2}\mathbf{i}} p)^n+(1-p+e^{\frac{2\pi}{2}\mathbf{i}} p)^n+1-p+e^{\frac{3\pi}{2}\mathbf{i}} p)^n-4(1-p)^n \over 4}=
</math>
: <math>
={1+(1-2p)^n + 2((1-p)^2+p^2)^{n \over 2}\cos(n\arctan{p\over (1-p)})-4(1-p)^n \over 4}.
</math>
Строка 447 ⟶ 446 :
заданная функция <math>n(d,P_{miss},p)</math>, а точнее даже коэффициент
содержания полезной информации
<math>KPS(n,P_{miss},p)={n-\log_2 d \over n}</math> в переданных <i>''n</i>''
бит как функция от величины шума и вероятности незамеченных
ошибок. Чем выше желаемая надёжность передачи, то есть чем меньше
Строка 453 ⟶ 452 :
полезной информации.
 
<b>'''Конец задачи.</b>'''</div>
 
Итак, с помощью одного бита чётности мы повышаем надёжность
передачи, и вероятность незамеченной ошибки равна
<math>P_{miss}(2,n,p)</math>. Это вероятность уменьшается с уменьшением <i>''n</i>''.
При <math>n=2</math> получаем <math>P_{miss}(2,2,p)=p^2</math>, это соответствует
дублированию каждого бита. Рассмотрим общую идею того, как с
Строка 463 ⟶ 462 :
высокой надёжности передачи.
 
''Общая идея'' На множестве слов длины <i>''n</i>'' определена
метрика Хемминга: расстояние Хемминга между двумя словами
равно количеству несовпадающих бит. Например,
 
: <math>\rho_H(10001001,10110001)=3.</math>
 
<div class="task"><b>'''Задача 5.</b>'''
 
Докажите, что <math>\rho_H</math> метрика.
 
<b>'''Конец задачи.</b>'''</div>
 
Если два слова находятся на расстоянии <i>''r</i>'' по Хеммингу,
это значит, что надо инвертировать ровно <i>''r</i>'' разрядов, чтобы
преобразовать одно слово в другое. В описанном ниже
кодировании Хемминга любые два различных допустимых слова
находятся на расстоянии <math>\rho_H\geq 3</math>. Если мы хотим
обнаруживать <i>''d</i>'' ошибок, то надо, чтобы слова отстояли друг
от друга на расстояние <math>\geq d+1</math>. Если мы хотим
исправлять ошибки, то надо чтобы кодослова отстояли друг от
друга на <math>\geq 2d+1</math>. Действительно, даже если
переданное слово содержит <i>''d</i>'' ошибок, оно, как следует из
неравенства треугольника, все равно ближе к правильному
слову, чем к какому-либо еще, и следовательно можно
Строка 491 ⟶ 490 :
называется ''расстоянием Хемминга данного кода''.
 
Элементарный пример помехоустойчивого кода  — это код, у
которого есть только четыре ''допустимых кодовых слова'':
 
: <math>0000000000,\; 0000011111,\; 1111100000,\; 1111111111.</math>
 
Расстояние по Хеммингу у этого кода 5, следовательно он может
исправлять двойные ошибки и замечать 4 ошибки. Если получатель
получит слово <i>''0001010111</i>'', то ясно, что исходное слово имело
вид <i>''0000011111</i>''. Коэффициент раздувания равен&nbsp;5. То есть
исходное слово длины <i>''m</i>'' будет кодироваться в слово длины <math>n=5m</math>
 
Отметим что имеет смысл говорить о двух коэффициентах:
* <math>KPS(n)=\frac{m(n)}{n}</math>  — коэффициент содержания полезной информации
* <math>k(m)=\frac{n(m)}{m}</math>  — коэффициент раздувания информации
 
Первый есть функция от переменной <i>''n</i>'', а второй, обратный
ему,  — от переменной <i>''m</i>''.
 
Здесь мы подошли к довольно трудной задаче —
минимизировать коэффициент раздувания для требуемой
надёжности передачи. Она рассматривается в разделе <b>'''(theory)</b>'''.
 
=== Циклические коды ===
На практике активно применяются полиномиальные коды
или циклические избыточные коды ('''Cyclic Redundancy Code
— <i>''CRC</i>''''').
 
<i>''CRC</i>'' коды построены на рассмотрении битовой строки как
строки коэффициентов полинома. <i>''k</i>''-битовая строка
соответствует полиному степени <math>k-1</math>. Самый левый бит строки
— коэффициент при старшей степени. Например, строка <i>''110001</i>''
представляет полином <math>x^5+x^4+x^0</math>. Коэффициенты полинома
принадлежат полю <math>G\mathbb{F}(2)</math> вычетов по модулю&nbsp;2.
 
Основная идея заключена в том, чтобы пересылать только такие
Строка 535 ⟶ 534 :
 
Есть два очевидных способа кодирования сообщения в полином,
который делится на <math>G(x)</math>  — это либо умножить полином исходного
сообщения на <math>G(x)</math>, либо добавить к нашему сообщению некоторое
количество бит так, чтобы результирующий полином делился на
<math>G(x)</math>. В <i>''CRC</i>'' используется второй способ.
 
Отправитель и получатель заранее договариваются
о конкретном ''полиноме-генераторе'' <math>G(x)</math>. Пусть степень
<math>G(x)</math> равна <i>''l</i>''. Тогда длина блока «конторольной суммы» также
равна <i>''l</i>''.
 
Мы добавляем контрольные <i>''l</i>'' бит в конец передаваемого
блоку так, чтобы получился полином кратный генератору
<math>G(x)</math>. Когда получатель получает блок с контрольной суммой,
он проверяет его делимость на <i>''G</i>''. Если есть остаток <math>\neq
0</math>, то были ошибки при передаче.
 
''Алгоритм кодирования <i>''CRC</i>'':''
 
''Дано слово <i>''W</i>'' длины <i>''m</i>''. Ему соответствует полином <math>W(x)</math>.''
 
# ''Добавить к исходному слову <i>''W</i>'' справа <i>''r</i>'' нулей. Получится слово длины <math>n=m+r</math> и полином :<math>x^r\cdot W(x);</math> ''
# ''Разделить полином <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;<b>'''(fig:crc)</b>''' иллюстрирует этот алгоритм для блока
<i>''1101011011</i>'' и <math>{G(x)=x^4+x+1}</math>.
 
\begin{figure}[h!]
Строка 569 ⟶ 568 :
\end{tabular}}
\centering\includegraphics[clip=true,
width=0.75\textwidth]{pictures/crc2.eps}
\caption{CRC  — полиномиальное кодирование}
<b>'''(fig:crc)</b>'''
\end{figure}
 
Строка 581 ⟶ 580 :
* <math>CRC-12 = x^{12} + x^{11}+x^3+x^2+x+1</math>
* <math>CRC-16 =x^{16}+x^{15}+x^2+1</math>
* <math>CRC-CCITT = x^{16}+x^{12}+x^5+1</math>
 
<math>CRC-12</math> используется для передачи символов из <i>''6</i>'' разрядов.
Два остальных  — для <i>''8</i>'' разрядных. <math>CRC-16</math> и <math>CRC-CCITT</math> ловят
одиночные, двойные ошибки, групповые ошибки длины не более 16 и
нечётное число изолированных ошибок с вероятностью <i>''0.99997</i>''.
 
=== * Теоретический предел ===
<b>'''(theory)</b>''' В примечании
к задаче&nbsp;<b>'''(task:errmod)</b>''' было указано как можно получить
значение коэффициента содержания полезной информации (КПС) на
один бит, если передавать данные по каналу с шумом <i>''p</i>'' словами
длиной <i>''n</i>'' бит, при условии, чтобы вероятность незамеченной
ошибки была меньше&nbsp;<math>P_{miss}</math>.
 
Строка 606 ⟶ 605 :
абсолютной точностью.
 
<div class="task"><b>'''Задача 6.</b>'''
 
<b>'''(task:err)</b>'''
Мы хотим передавать информацию блоками, которые содержали
бы <i>''m</i>'' бит полезной информации, так, чтобы
вероятность ошибки в одном бите равнялась <i>''p</i>'', а
правильность передачи «фиксировалось контрольной суммой». Найти
минимальный размер блока <math>n(m,p)</math> и коэффициент раздувания
<math>k=\frac{n(m)}{m}</math>.
 
<b>'''Конец задачи.</b>'''</div>
 
''Решение.''
Для передачи <i>''m</i>'' бит с вероятностью ошибки в отдельном бите
<i>''p</i>'' требуется передать <math>m C(p)</math> бит
(см.&nbsp;задачу&nbsp;<b>'''(task:dual)</b>'''). Кроме того мы хотим сообщать
об ошибке в передаче. Её вероятность равна <math>(1-p)^m</math>, а
значит информация, заложенная в этом сообщении,
<math>H((1-p)^m)</math>. В итоге получаем <math>n=mC(p)+H((1-p)^m)</math> и
 
: <math>k(m,p)=C(p)+\frac{H((1-p)^m)}{m}.</math>
 
''Конец решения.''
 
Заметим, что <math>k(1,p)=1</math>  — когда блок имеет размер один бит,
сообщение об ошибке в нём равносильно передаче самого бита.
 
Если передавать эти сообщения по каналу с уровнем помех <i>''p</i>'', то
количество бит на одно сообщение равно <math>m k(m,p)/C(p)</math>, то есть
теоретическая оценка для количества лишних бит равна
 
: <math>\frac{H((1-p)^m)}{C(p)}</math>
 
Понятно, что данная теоретическая оценка занижена.
 
=== Коды Хемминга ===
Элементарный пример кода исправляющего ошибки был показан на
странице&nbsp;\pageref{simplecode}. Его обобщение очевидно. Для
Строка 647 ⟶ 646 :
3</math>. Оказывается это число можно сделать сколь угодно близким к
единице с помощью кодов Хемминга. В частности, при кодировании
<i>''11</i>'' бит получается слово длинной <i>''15</i>'' бит, то есть
<math>KPS=\frac{11}{15}</math>.
 
Оценим минимальное количество контрольных
разрядов, необходимое для исправления одиночных ошибок. Пусть
содержательная часть составляет <i>''m</i>'' бит, и мы добавляем ещё <i>''r</i>''
контрольных. Каждое из <math>2^m</math> правильных сообщений имеет <math>n=m+r</math>
его неправильных вариантов с ошибкой в одном бите. Такими
Строка 659 ⟶ 658 :
слов <math>2^n</math>, то
 
: <math>
\begin{array}{c}
(n+1)2^m \leqslant 2^n\\ (m+r+1)\leqslant 2^r.
Строка 667 ⟶ 666 :
Этот теоретический предел достижим при использовании
метода, предложенного Хеммингом. Идея его в следующем: все
биты, номера которых есть степень <i>''2</i>'',  — контрольные,
остальные  — биты сообщения. Каждый контрольный бит
отвечает за чётность суммы некоторой группы бит. Один и тот
же бит может относиться к разным группам. Чтобы определить
какие контрольные биты контролируют бит в позиции <i>''k</i>'' надо
разложить <i>''k</i>'' по степеням двойки: если <math>k=11=8+2+1</math>, то этот
бит относится к трём группам  — к группе, чья чётность
подсчитывается в 1-ом бите, к группе 2-ого и к группе 8-ого
бита. Другими словами в контрольный бит с номером <math>2^k</math>
Строка 679 ⟶ 678 :
в разложении по степеням двойки степень <math>2^k</math>:
 
: <math>
 
\begin{array}{l}
Строка 687 ⟶ 686 :
b_8=b_9+b_{10}+b_{11}+b_{12}+b_{13}+b_{14}+b_{15}\dots \\
\end{array}
</math> <b>'''(eq:hem)</b>'''
 
Код Хемминга оптимален при <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> (хотя
<i>''n</i>'' однозначно определяет <i>''m</i>'').
 
Пример для <math>Hem(15,11)</math>:
 
: <math>
\fbox{10110100111}\to
\fbox{\fbox{0}\fbox{0}1\fbox{1}011\fbox{0}0100111}
</math>
: <math>
\hphantom{\fbox{10110100111}\to}\;\;
\lefteqn{\,b_1}\hphantom{\fbox{0}}
Строка 714 ⟶ 713 :
получатель проверяет каждый контрольный бит на предмет
правильности чётности и складывая номера контрольных бит, в
которых нарушена чётность. Полученное число, есть <i>''XOR</i>'' номеров
бит, где произошла ошибка. Если ошибка одна, то это число есть
просто номер ошибочного бита.
Строка 727 ⟶ 726 :
\centering\includegraphics[clip=true,
width=0.65\textwidth]{pictures/hem.eps} \caption{Кодирование
Хемминга} <b>'''(fig:hem)</b>'''
\end{figure}
 
<div class="task"><b>'''Задача 7.</b>'''
 
Покажите, что <math>KPS_{Hem(n,m)}\to 1</math> при <math>n\to
\infty</math>.
 
<b>'''Конец задачи.</b>'''</div>
 
Код Хемминга может исправлять только единичные ошибки. Однако,
есть приём, который позволяет распространить этот код на случай
групповых ошибок. Пусть нам надо передать <i>''k</i>'' кодослов.
Расположим их в виде матрицы одно слово  — строка. Обычно,
передают слово за словом. Но мы поступим иначе, передадим слово
длины <i>''k</i>'', из 1-ых разрядов всех слов, затем  — вторых и  т. д. По
приёме всех слов матрица восстанавливается. Если мы хотим
обнаруживать групповые ошибки размера <i>''k</i>'', то в каждой строке
восстановленной матрицы будет не более одной ошибки. А с
одиночными ошибками код Хемминга справится.
 
=== Анализ эффективности ===
Начнём c небольшого примера. Пусть у нас есть канал с уровнем
ошибок <math>p=10^{-6}</math>. Если мы хотим исправлять единичные ошибки при
передаче блоками по <math>1023=2^{10}-1</math> бит, то среди них потребуется
<i>''10</i>'' контрольных бит: <i>''1</i>'', <i>''2</i>'', \dots, <math>2^9</math>. На один блок
приходится <i>''1013</i>'' бит полезной информации. При передаче <i>''1000</i>''
таких блоков потребуется <math>\Delta=10\,000</math> контрольных бит.
 
В тоже время для обнаружения единичной ошибки достаточно одного
бита чётности. И если мы применим технику повторной передачи, то
на передачу <i>''1000</i>'' блоков надо будет потратить <i>''1000</i>'' бит
дополнительно и примерно <math>0.001\approx
p_{1014}=1-(1-10^{-6})^{1014}</math> из них придется пересылать
повторно. То есть на <i>''1000</i>'' блоков приходится один попорченый, и
дополнительная нагрузка линии составляет <math>\Delta\approx
1000+1001</math>, что меньше <math>10\,000</math>. Но это не значит, что код
Хемминга плох для такого канала. Надо правильно выбрать длину
блока  — если <math>n>3444</math>, то код Хемминга эффективен.
 
Рассмотрим этот вопрос подробнее. Пусть нам нужно передать
информацию <i>''M</i>'' бит. Разобьем её на <i>''L</i>'' блоков по <math>m=M/L</math> бит
и будем передавать двумя способами
— с помощью кодов Хемминга и без них. При этом будем
Строка 779 ⟶ 778 :
<math>m'=k_\varepsilon(m)m</math>
 
1) '''Без кода Хемминга.'''
 
Если пересылать информацию
блоками по <math>m'</math> бит с повторной пересылкой в случае
обнаружения ошибки, то получим, что в среднем нам придётся
переслать <i>''D</i>'' бит:
 
: <math>D=L m'{1 \over 1-P_{r}}</math>
 
Где <math>P_{r}=(1-(1-p)^{m'})(1-\varepsilon)</math>  — вероятность
повторной передачи равная вероятности ошибки умноженной на
вероятность того, что мы её заметим. Коэффициент раздувания
равен
 
: <math>k(m,p,\varepsilon)=\frac{D}{M}=\frac{k_{\varepsilon}(m)}{\varepsilon+(1-\varepsilon)(1-p)^{k_{\varepsilon}(m)m}}</math>
 
2) '''С кодом Хемминга.'''
 
При кодировании методом Хемминга слова длины <math>m'</math> получается слово длины <i>''n</i>'' бит:
 
: <math>
2^n=2^{m'}(n+1), \;\; k_{\varepsilon}(m)m= n-\log_2(n+1)
</math> <b>'''(eq:hnm)</b>'''
 
Для отдельного блока вероятность
Строка 808 ⟶ 807 :
что произошло более чем одна ошибка, и мы это заметили
 
: <math>P_{r}={(1-P_0-P_1)}{(1-\varepsilon)}={1-\varepsilon-(1-\varepsilon)(1-p)^{n-1}(np+1-p)}</math>
 
— в этом случае требуется повторная передача кадра.
Количество передаваемых данных:
 
: <math>D_{H}=L n{1 \over 1-P_{r}}={L n \over \varepsilon+(1-\varepsilon)(1-p)^{n-1}(np+1-p)}</math>
 
И коэффициент раздувания
: <math>k_H(m,p,\varepsilon)={ n
\over m\bigl(\varepsilon+(1-\varepsilon)(1-p)^{n-1}(np+1-p)\bigr)},</math>
 
где <math>n(m)</math> неявно определённая с помощью (<b>'''(eq:hnm)</b>''')
функция. Удобно записать соответствующие коэффициенты
полезного содержания:
 
: <math>
KPS= KPS_{\varepsilon}\bigl(n\bigr)\bigl(\varepsilon+(1-\varepsilon)(1-p)^n\bigr)
</math>
 
: <math>
KPS_H={KPS_{\varepsilon}\bigl(m'\bigr)\frac{m'}{n}\bigl(\varepsilon+(1-p)^{n-1}(np+1-p)(1-\varepsilon)\bigr)},
</math>, <math>m'=n-\log_2(n+1)</math> <b>'''(eq:kps)</b>'''
 
Легко обнаружить что при <math> n > 3444 </math> и <math>p=10^{-6}</math> код Хемминга
Строка 836 ⟶ 835 :
<div align="center">
\begin{figure}[h!]
\psfrag{knc}{кпс} \psfrag{n}{<i>''n</i>''}
\centering\includegraphics[clip=true,
width=0.48\textwidth]{pictures/kps.eps}
\centering\includegraphics[clip=true,
width=0.48\textwidth]{pictures/kps2.eps} \caption{
<math>KPS(n,p,\varepsilon)</math>  — Коэффициент полезного содержания
в канале с помехами как функция размера элементарного блока.}
\parbox{0.85\textwidth}{\small Светлый график  — ''без кодирования Хемминга'';\\
Темный график  — ''с кодированием Хемминга'';
\\Параметры: <math>\varepsilon=10^{-6}\;</math>; <math>p=10^{-6}.</math>}
<b>'''(fig:kps)</b>'''
\end{figure}
</div>
Строка 852 ⟶ 851 :
<div align="center">
\begin{figure}[h!]
\psfrag{C}{<i>''C</i>''} \psfrag{p}{<i>''p</i>''}
\centering\includegraphics[clip=true,
width=0.75\textwidth]{pictures/kpseff.eps}
\caption{<math>C(p,\varepsilon)</math>  — максимальный коэффициент полезного
содержания в канале с помехами как функция уровня помех.}
\parbox{0.97\textwidth}{ \small Светлый график  — ''без кодирования Хемминга'';\\ Темный график  — ''с кодированием Хемминга'';\\Тонкий график  — теоретический
предел, задаваемый функцией&nbsp;<math>C(p)</math>\\Параметры:
<math>\varepsilon=10^{-6}</math>.} <b>'''(fig:kpseff)</b>'''
\end{figure}
</div>
 
Значение <math>KPS_{\varepsilon}(n)</math> используемое в
формулах (<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>  — вероятности
ошибочной передачи блока при условии, что «контрольная сумма
сошлась» и кадр засчитан правильно переданным.
Строка 877 ⟶ 876 :
получается из формулы
 
: <math>\varepsilon=\frac{2^m-1}{2^n-1}</math>
 
Но это безусловно лишь оценочная формула. Оптимальное
значение <math>KPS_{\varepsilon}</math> значительно сложнее и
зависит от <i>''p</i>''.
 
Из графика на рисунке&nbsp;<b>'''(fig:kps)</b>''' хорошо видно, что при
больших <i>''n</i>'' код Хемминга начинает работать на пользу.
 
Но зависимость КПС от <i>''n</i>'' не есть критерий эффективности
кода. Эффективность кода определяется функцией
 
: <math>C(p,\varepsilon)=\min_{n}{KPS(p,n,\varepsilon)}</math>
 
На рисунке&nbsp;<b>'''(fig:kpseff)</b>''' показан график этой функции и из
него ясно, что код Хемминга можно использовать с пользой
всегда  — при любых <math>\varepsilon</math> и <i>''p</i>'', если у нас есть
возможность выбирать подходящее <i>''n</i>''.
 
=== Коды как линейные операторы ===
То, что на множестве {0,1} есть структура числового поля,
позволяет осуществлять алгебраические интерпретации кодирования.
Заметим, в частности, что как коды Хемминга, так и циклические
коды ''линейны'':\\ 1) отношения (<b>'''(eq:hem)</b>''') на
с.&nbsp;\pageref{eq:hem}, связывающие контрольные биты кода Хемминга с
другими линейны,\\ 2) остаток от деления суммы многочленов на
Строка 907 ⟶ 906 :
<math>G\mathbb{F}(2)^n</math>. Поясним на примерах. Ниже представлена
матрица кода Хемминга <math>Hem(7,4)</math> (см.
соотношения&nbsp;(<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>
\mathbf{A}_{Hem(7,4)}=\begin{Vmatrix}
1&1&0&1\\ 1&0&1&1\\ 1&0&0&0\\ 0&1&1&1\\ 0&1&0&1\\ 0&0&1&0\\
Строка 923 ⟶ 922 :
<math>\mathbf{s}=\overline{s_1s_2s_3}=\mathbf{H}\mathbf{w'}_{out}</math> в
случае правильной передачи должно быть равно 000. Значение
<math>\mathbf{s}</math> называется ''синдромом ошибки''. <''i>i</i>''-ый разряд
слова <math>\mathbf{s}</math> контролирует <''i>i</i>''-ое соотношение в
(<b>'''(eq:hem)</b>''') и, таким образом, <math>\mathbf{s}</math> равно сумме номеров
бит в которых произошла ошибка, как векторов в <math>G\mathbb{F}(2)^3</math>.
 
: <math>\mathbf{H}_{Hem(7,4)}=
\begin{Vmatrix}
1&0&1&0&1&0&1\\ 0&1&1&0&0&1&1\\0&0&0&1&1&1&1
Строка 939 ⟶ 938 :
Вычиcление рабочей матрицы для циклических кодов
основывается на значениях <math>G_n(x)=x^n\; \mathop{mod}\; G(x)</math>. Верхняя
её часть равна единичной, так <i>''m</i>'' бит сообщения помещаются
без изменения в начало слова, а нижние <i>''r</i>'' строчек есть <i>''m</i>''
столбцов высоты <i>''r</i>'' состоящие из коэффициентов многочленов
<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> и
 
: <math>
\begin{vmatrix}
G_0&G_1&G_2&G_3&G_4&G_5&G_6&G_7\\
Строка 956 ⟶ 955 :
Рабочая и проверочная матрицы равны
 
: <math>\mathbf{A}=\left\|\begin{array}{c} E_4\\G_6
G_5 G_4 G_3
\end{array}\right\| , \quad \mathbf{H}=\|G_6G_5G_4G_3E_3\|,</math>
то есть
 
: <math>
\mathbf{A}=\begin{Vmatrix}
1&0&0&0\\ 0&1&0&0\\ 0&0&1&0\\ 0&0&0&1\\ 1&1&1&0\\
Строка 979 ⟶ 978 :
порождающей. В частности, рабочая матрица является порождающей.
Способность обнаруживать и исправлять ошибки однозначно
определяется подпространством <i>''L</i>''. Порождающих, рабочих и
проверочных матриц соответствующих <i>''L</i>'' несколько.
 
Действительно, в порождающей и рабочей матрицах можно осуществлять
элементарные операции со столбцами, а в проверочной  — со
строчками. Матрицы&nbsp;<math>\mathbf{A}</math>, <math>\mathbf{H}</math> и <math>\mathbf{G}</math>
всегда удовлетворяют отношениям
 
: <math>\mathbf{H}\cdot \mathbf{A}=\mathbf{0}_{rm},\; \mathbf{H}\cdot \mathbf{G}=\mathbf{0}_{rm},</math>
где
<math>\mathbf{0}_{rm}</math>  — нулевая матрица <math>r\times m</math>.
 
Любая порождающая матрица может использоваться как
Строка 999 ⟶ 998 :
матриц определяется рабочей матрицей:
 
: <math>\mathbf{D}\cdot \mathbf{A}=\mathbf{E}_m,</math>
 
где <math>\mathbf{E}_m</math>  — единичная матрица <math>m\times m</math>. На
подпространстве <i>''L</i>'' все декодирующие матрицы действуют одинаково.
Они отличаются на подпространстве ортогональном <i>''L</i>''. Приведём
декодирующую матрицу для <math>Hem(7,4)</math> и <math>CRC_{n=7,\;m=7}</math>:
 
: <math>
\mathbf{D}_{H_{7,4}}=
\begin{Vmatrix}
Строка 1030 ⟶ 1029 :
Сформулируем теперь основные моменты, касающиеся линейных кодов.
 
# Процесс кодирования и декодирования  — линейные операторы. :<math>\mathbf{w}_{out}=\mathbf{A}\mathbf{w}_{in},\; \; channel:\mathbf{w}_{out}\mapsto \mathbf{w}'_{out},\;\; \mathbf{w}'_{in}=\mathbf{D}\mathbf{w}'_{out}</math>
# Обнаружение ошибок равносильно проверке принадлежности полученного слова подпространству <i>''L</i>'' допустимых слов. Для этого необходимо найти проекцию <math>\mathbf{s}</math> (синдром ошибки) полученного слова на <math>L^{\perp}</math>  — тоже линейная операция. Для правильно переданного слова&nbsp;<math>\mathbf{s}=\mathbf{0}</math>. :<math>\mathbf{s}=\mathbf{H}\mathbf{w}'_{out}</math>
# В случае, когда векторы подпространства <i>''L</i>'' достаточно удалены друг от друга в смысле метрики Хемминга, есть возможность обнаруживать и исправлять некоторые ошибки. В частности, значение синдрома ошибки в случае кода Хемминга равно векторной сумме номеров бит, где произошла ошибка.
# Комбинация (композиция) линейных кодов есть снова линейный код.
 
Практические методы помехоустойчивого кодирования все основаны на
линейных кодах. В основном это модифицированные <i>''CRC</i>'', коды
Хемминга и их композиции. Например <math>Hem(7,4)</math> плюс проверка на
чётность. Такой код может исправлять уже две ошибки. Построение
Строка 1047 ⟶ 1046 :
уровня групповые ошибки.
 
<div class="task"><b>'''Задача 8.</b>'''
Для данной проверочной матрицы постройте рабочую и декодирующую
матрицу. Докажите, что кодовое расстояние равно 4.
 
: <math>\mathbf{H}=\begin{Vmatrix}
1&0&1&0&1&0&1&0\\
0&1&1&0&0&1&1&0\\
Строка 1062 ⟶ 1061 :
# Кодовое расстояние равно минимальному количеству линейно зависимых столбцов в <math>\mathbf{H}</math>.
 
<b>'''Конец задачи.</b>'''</div>
 
<div class="task"><b>'''Задача 9.</b>'''
 
Посторойте декодирующую и проверочную матрицу для циклического
Строка 1070 ⟶ 1069 :
рабочей матрицы использовалась матрица
 
: <math>\mathbf{A}=
\begin{Vmatrix}
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{Vmatrix}.</math>
 
<b>'''Конец задачи.</b>'''</div>
 
=== *Коды Рида-Соломона ===
После перехода на язык линейной алгебры естественно возникает
желание изучить свойства линейных кодов над другими конечными
Строка 1091 ⟶ 1090 :
найдётся единственное с точностью до изоморфности конечное поле с
таким числом элементов, которое обозначается как
<math>G\mathbb{F}(n)</math>. Простейшая реализация этого поля  — множество
многочленов по модулю неприводимого{{ref|note3}} многочлена <math>p(x)</math> степени <i>''k</i>'' над
полем <math>\mathbb{F}_{q}</math> вычетов по модулю&nbsp;<i>''q</i>''. В случае
многочленов с действительными коэффициентами неприводимыми
многочленами являются только квадратные многочлены с
отрицательным дискриминантом. Поэтому существует только
квадратичное расширение действительного поля  — комплексные
числа. А над конечным полем существуют неприводимые многочлены
любой степени. В частности, над <math>\mathbb{F}_{2}</math> многочлен
Строка 1103 ⟶ 1102 :
модулю&nbsp;<math>g(z)</math> образуют поле из <math>2^{3}=8</math> элементов.
 
== Примеры протоколов канала данных ==
 
===<i> ''HDLC</i>'' протокол ===
Здесь мы познакомимся с группой протоколов давно известных, но
по-прежнему широко используемых. Все они имеют одного
предшественника — – <i>''SDLC</i>'' (Synchronous Data Link Control) –-
протокол управления синхронным каналом, предложенным фирмой <i>''IBM</i>''
в рамках <i>''SNA</i>''. <i>''ISO</i>'' модифицировала этот протокол и выпустила
под названием <i>''HDLC</i> '' — High level Data Link Control. <i>''MKTT</i>''
модифицировала <i>''HDLC</i>'' для X.25 и выпустила под именем <i>''LAP</i>'' –-
Link Access Procedure. Позднее он был модифицирован в <i>''LAPB</i>''.
 
Все эти протоколы построены на одних и тех же принципах. Все
Строка 1122:
\centering\includegraphics[clip=true,
width=0.88\textwidth]{pictures/frame.eps} \caption{Типовая
структура кадра} <b>'''(fig:frame)</b>'''
\end{figure}
</div>
 
На рис.&nbsp;<b>'''(fig:frame)</b>''' показана типовая структура кадра.
Поле адреса используется для адресации терминала, если их
несколько на линии. Для линий точка-точка это поле
используется для различия команды от ответа.
 
* Поле <i>''Control</i>'' используется для последовательных номеров кадров, подтверждений и других нужд.
* Поле <i>''Data</i>'' может быть сколь угодно большим и используется для передачи данных. Надо только иметь ввиду, что чем оно длиннее тем, больше вероятность повреждения кадра на линии.
* Поле <i>''Checksum</i> '' — это поле используется <i>''CRC</i>'' кодом.
 
Флаговые последовательности <i>''01111110</i>'' используются для
разделения кадров и постоянно передаются по незанятой линии
в ожидании кадра. Существуют три вида кадров: <math>Information</math>,
<math>Supervisory</math>, <i>''Unnumbered</i>''.
 
Организация поля <i>''Control</i>'' для этих трех видов кадров показана на
рис.&nbsp;<b>'''(fig:cfield)</b>'''. Как видно из размера поля <i>''Seq</i>'' в окне
отправителя может быть до <i>''7</i>'' неподтверждённых кадров. Поле
<i>''Next</i>'' используется для посылки подтверждения вместе с
передаваемым кадром. Подтверждение может быть в форме номера
последнего правильно переданного кадра, а может быть в форме
Строка 1153:
\centering\includegraphics[clip=true,
width=0.88\textwidth]{pictures/cfield.eps} \caption{Cтруктура поля
<i>''Control</i>''}
\parbox{0.66\textwidth}{\small (а) Информационный кадр (<math>Information</math>)\\
(б) Управляющий кадр (<math>Supervisory</math>)\\(в) Ненумерованный
кадр (<i>''Unnumbered</i>'') }
<b>'''(fig:cfield)</b>'''
\end{figure}
</div>
Строка 1163:
Разряд <math>P/F</math> использует при работе с группой терминалов.
Когда компьютер приглашает терминал к передаче он
устанавливает этот разряд в <i>''P</i>''. Все кадры, посылаемые
терминалами имеют здесь <i>''P</i>''. Если это последний кадр,
посылаемый терминалом, то здесь стоит <i>''F</i>''.
 
<math>Supervisory</math> кадры имеют четыре типа кадров.
 
* Тип 0  — уведомление в ожидании следующего кадра (RECEIVE READY). Используется когда нет встречного трафика, чтобы передать уведомление в кадре с данными.
* Тип 1  — негативное уведомление (REJECT)  — указывает на ошибку при передаче. Поле <i>''Next</i>'' указывает номер кадра, начиная с которого надо перепослать кадры.
* Тип 2  — RECEIVE NOT READY. Подтверждает все кадры, кроме указанного в Next. Используется, чтобы сообщить источнику кадров об необходимости приостановить передачу в силу каких-то проблем у получателя. После устранения этих проблем получатель шлет RECEIVE REDAY, REJECT или другой надлежащий управляющий кадр.
* Тип 3  — SELECTIVE REJECT  — указывает на необходимость перепослать только кадр, указанный в Next. <i>''LAPB</i>'' и <i>''SDLC</i>'' не используют этого типа кадров.
 
Третий класс кадров  — <i>''Unnubered</i>''. Кадры этого класса иногда
используются для целей управления, но чаще для передачи данных
при ненадёжной передаче без соединения.
 
Все протоколы имеют команду DISConnect для указания о разрыве
соединения, SNRM и SABM  — для установки счётчиков кадров в ноль,
сброса соединения в начальное состояние, установки
соподчинённости на линии. Команда FRMR  — указывает на
повреждение управляющего кадра.
 
# {{note|note1}} Идея рассмотрения информации как меры на множестве ещё не до конца исчерпала себя  — такой меры ещё не построено. Однако доказано, что с помощью этой аналогии можно доказывать неравенства, например <math>{I(\{\xi_{in}\,\xi_{out}\})\geqslant 0}</math>.
# {{note|note2}} Матрица называется ''стохастической'', если все её элементы неотрицательны и сумма элементов в каждом столбце равна единице.
# {{note|note3}} Многочлен называется ''неприводимым'', если он не разлагается в произведение многочленов меньшей степени.
Источник — https://ru.wikibooks.org/wiki/Помехоустойчивое_кодирование