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

Аннотация

Здесь мы рассмотрим основные принципы и методы надёжной и эффективной передачи данных между двумя машинами, соединёнными каналом. Под каналом следует понимать любую физическую среду передачи данных. Посредством этой физической среды нужно научиться передавать биты так, чтобы они безошибочно принимались получателем точно в той последовательности, в какой они были переданы.

Канальный уровень

На уровне канала данных решается ряд проблем, присущих только этому уровню:

• реализация сервиса для сетевого уровня,
• разбиение потока бит на кадры,
• управление потоком кадров,
• обработка ошибок передачи.

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

Разбиение на кадры

Сервис, создаваемый канальным уровнем для сетевого, опирается на сервис, создаваемый физическим уровнем. На физическом уровне протекают потоки битов. Значение посланного бита не обязательно равно принятому, и количество посланных битов не обязательно равно количеству принятых. Всё это требует специальных усилий на канальном уровне по обнаружению и исправлению ошибок.

Типовой подход к решению этой проблемы — разбиение потока битов на кадры и подсчёт контрольной суммы для каждого кадра при посылке данных.

Контрольная сумма — это, в общем смысле, функция от содержательной части кадра (слова длины $m$), область значений которой — слова фиксированной длины $r$.

Эти r бит добавляются обычно в конец кадра. При приёме контрольная сумма вычисляется заново и сравнивается с той, что хранится в кадре. Если они различаются, то это признак ошибки передачи. Канальный уровень должен принять меры к исправлению ошибки, например, сбросить плохой кадр, послать сообщение об ошибке тому кто прислал этот кадр. Разбиение потока битов на кадры — задача не простая. Один из способов — делать временную паузу между битами разных кадров. Однако, в сети, где нет единого таймера, нет гарантии, что эта пауза сохранится или, наоборот, не появятся новые. Так как временные методы ненадёжны, то применяются другие. Здесь мы рассмотрим три основных:

• счетчик символов;
• вставка специальных стартовых и конечных символов или последовательностей бит;
• специальная кодировка на физическом уровне.

Первый метод очевиден. В начале каждого кадра указывается сколько символов в кадре. При приёме число принятых символов подсчитывается опять. Однако, этот метод имеет существенный недостаток — счётчик символов может быть искажён при передаче. Тогда принимающая сторона не сможет обнаружить границы кадра. Даже обнаружив несовпадение контрольных сумм, принимающая сторона не сможет сообщить передающей какой кадр надо переслать, сколько символов пропало. Этот метод ныне используется редко.

Второй метод построен на вставке специальных символов. Обычно для этого используют управляющие последовательности: последовательность $DLESTX$ для начала кадра и $DLEETX$ для конца кадра. $DLE$ — Data Link Escape; $STX$ — Start TeXt, $ETX$ — End TeXt. При этом методе если даже была потеряна граница текущего кадра, надо просто искать ближайшую последовательность $DLE$ $STX$ или $DLE$ $ETX$. Но нужно избегать появления этих комбинаций внутри самого тела кадра. Это осуществляется дублированием комбинаций $DLE$, встречающихся внутри тела кадра, и удаление дублей после получения кадра. Недостатком этого метода является зависимость от кодировки (кодозависимость).

По мере развития сетей эта связь становилась все более и более обременительной и был предложен новый очевидный кодонезависимый метод — управляющие последовательности должны быть бит-ориентированными. В частности, в протоколе $HDLC$ каждый кадр начинается и заканчивается со специального флаг-байта: 01111110. Посылающая сторона, встретив последовательно 5 единиц внутри тела кадра, обязательно вставит 0. Принимающая сторона, приняв 5 последовательных единиц обязательно удалит следующий за ними 0, если таковой будет. Это называется bit-stuffing. Если принято шесть и за ними следует ноль, то это управляющий сигнал: начало или конец кадра, а в случае, когда подряд идут более шести единиц, — сигнал ожидания или аварийного завершения.

 (а) 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 0 1
 (б) 0 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 0 0 1

 Bit Stuffing. (a) исходные данные (б) посылаемые данные. Жирным отмечены вставленные нули.

Таким образом, кадр легко может быть распознан по флаг-байту. Если граница очередного кадра по какой-то причине была потеряна, то все что надо делать — ловить ближайший флаг-байт.

И наконец, последний метод используется там, где конкретизирована физическая среда. Например, в случае проводной связи для передачи одного бита используется два импульса. 1 кодируется как переход высокое-низкое, 0 — как низкое-высокое. Сочетания низкое-низкое или высокое-высокое не используются для передачи данных, и их используют для границ кадра.

На практике используют, как правило, комбинацию этих методов. Например, счётчик символов с флаг-байтами. Тогда, если число символов в кадре соответствует кодировке границы кадра, кадр считается переданным правильно.

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

Решив проблему разбиения на кадры, мы приходим к следующей проблеме: как обеспечить, чтобы кадры, пройдя по физическому каналу с помехами, попадали на сетевой уровень по назначению, в надлежащей последовательности и в надлежащем виде?

Частичное решение этой проблемы осуществляется посредством введения обратной связи между отправителем и получателем в виде кадра подтверждения, а также специального кодирования, позволяющего обнаруживать или даже исправлять ошибки передачи конкретного кадра.

Если кадр-подтверждение несет положительную информацию, то считается что переданные кадры прошли нормально, если там сообщение об ошибке, то переданные кадры надо передать заново.

Однако, возможны случаи когда из-за ошибок в канале кадр исчезнет целиком. В этом случае получатель не будет реагировать никак, а отправитель будет сколь угодно долго ждать подтверждения. Для решения этой проблемы на канальном уровне вводят таймеры. Когда передаётся очередной кадр, то одновременно устанавливается таймер на определённое время. Этого времени должно хватать на то, чтобы получатель получил кадр, а отправитель получил подтверждение. Если отправитель не получит подтверждение раньше, чем истечёт время, установленное на таймере то он будет считать, что кадр потерян и повторит его еще раз.

Однако, если кадр-подтверждение был утерян, то вполне возможно, что один и тот же кадр получатель получит дважды. Как быть? Для решения этой проблемы каждому кадру присваивают порядковый номер. С помощью этого номера получатель может обнаружить дубли.

Итак, таймеры, нумерация кадров, флаг-байты, кодирование и обратная связь — вот основные средства на канальном уровне, обеспечивающие надёжную доставку каждого кадра до сетевого уровня в единственном экземпляре. Но и с помощью этих средств невозможно достигнуть стопроцентной надёжности передачи.

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

Другая важная проблема, которая решается на канальном уровне — управление потоком. Вполне может случиться, что отправитель будет слать кадры столь часто, что получатель не будет успевать их обрабатывать(например, если машина-отправитель более мощная или загружена слабее, чем машина-получатель). Для борьбы с такими ситуациями вводят управления потоком. Это управление предполагает обратную связь между отправителем и получателем, которая позволяет им урегулировать такие ситуации. Есть много схем управления потоком и все они в основе своей имеют следующий сценарий: прежде, чем отправитель начнёт передачу, он спрашивает у получателя сколько кадров тот может принять. Получатель сообщает ему определённое число кадров. Отправитель после того, как передаст это число кадров, должен приостановить передачу и снова спросить получателя, как много кадров тот может принять, и т.д.

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

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

Физическая среда, по которой передаются данные, не может быть абсолютно надёжной. Более того, уровень шума бывает очень высоким, например в беспроводных системах связи и телефонных системах. Ошибки при передаче — это реальность, которую надо обязательно учитывать.

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

Основной характеристикой интенсивности помех в канале является параметр шума — p. Это число от 0 до 1, равное вероятности инвертирования бита, при условии, что он был передан по каналу и получен на другом конце.

Следующий параметр — $p_{2}$. Это вероятность того же события, но при условии, что предыдущий бит также был инвертирован.

Этими двумя параметрами вполне можно ограничиться при построении теории. Но, в принципе, можно было бы учитывать аналогичные вероятности для исчезновения бита, а также использовать полную информацию о пространственной корреляции ошибок, — то есть корреляции соседних ошибок, разделённых одним, двумя или более битами.

У групповых ошибок есть свои плюсы и минусы. Плюсы заключаются в следующем. Пусть данные передаются блоками по 1000 бит, а уровень ошибки 0,001 на бит. Если ошибки изолированные и независимые, то 63 % ($0.63\approx 1-0.999^{1000}$) блоков будут содержать ошибки. Если же они возникают группами по 100 сразу, то ошибки будут содержать 1 % ($0.01\approx 1-0.999^{10}$) блоков.

Зато, если ошибки не группируются, то в каждом кадре они невелики, и есть возможность их исправить. Групповые ошибки портят кадр безвозвратно. Требуется его повторная пересылка, но в некоторых системах это в принципе невозможно, — например, в телефонных системах, использующие цифровое кодирование, возникает эффект пропадания слов/слогов.

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

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

Второй — внести избыточность настолько, чтобы, анализируя полученные данные, можно не только замечать ошибки, но и указать, где именно возникли искажения. Это коды, исправляющие ошибки.

Такое деление условно. Более общий вариант — это коды, обнаруживающие k ошибок и исправляющие l ошибок, где $l\leq k$.

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

Информационным каналом называется пара зависимых случайных величин $\{\xi _{in},\,\xi _{out}\}$, одна из них называется входом другая выходом канала. Если случайные величины дискретны и конечны, то есть имеют конечные множества событий:

$\Omega _{in}=\{x_{1},\dots ,x_{a}\},\;\Omega _{out}=\{y_{1},\dots ,y_{b}\},$

то канал определяется матрицей условных вероятностей $\|r_{ij}\|$, $r_{ij}$ — вероятность того, что на выходе будет значение $y_{i}$ при условии, что на входе измерено значение $x_{j}$.

Входная случайная величина определяется распределением $\{p_{1},\dots ,p_{a}\}$ на $\Omega _{in}$, а распределение на выходе вычисляется по формуле

$q_{i}=\sum _{j=1}^{a}r_{ij}p_{j}.$

Объединённое распределение на $\Omega _{in}\times \Omega _{out}$ равно

$P_{ij}=r_{ij}p_{j}.$

Информация $I(\{\xi _{in},\,\xi _{out}\})$, передаваемая через канал, есть взаимная информация входа и выхода:

$I(\{\xi _{in}\,\xi _{out}\})=H(\xi _{in})+H(\xi _{out})-H(\{\xi _{in},\xi _{out}\}),$ (eq:inf)

где

$H(\xi _{in})=-\sum _{i=1}^{a}p_{i}\log _{2}p_{i},$

$H(\xi _{out})=-\sum _{i=1}^{a}q_{i}\log _{2}q_{i},$

$H(\{\xi _{in},\,\xi _{out}\})=-\sum _{i,j}P_{ij}\log _{2}P_{ij}.$

Если случайные величины $\xi _{in}$ и $\xi _{out}$ независимы (то есть ${P_{ij}=q_{i}p_{j}}$), то через канал $\{\xi _{in},\,\xi _{out}\}$ невозможно передавать информацию и $I(\{\xi _{in},\,\xi _{out}\})=0$. Понять суть формулы ((eq:inf)) можно из следующего соображения: энтропия случайной величины равна информации, которую мы получаем при одном её измерении. $H(\xi _{in})$ и $H(\xi _{out})$ — информация, которая содержится по отдельности во входе и в выходе. Но часть этой информации общая, её нам и нужно найти. $H(\{\xi _{in},\xi _{out}\})$ равна величине объединённой информации. В теории меры^[1] есть выражение аналогичное ((eq:inf)):

$\mu (A\wedge B)=\mu (A)+\mu (B)-\mu (A\vee B).$

Распределение входной случайной величины $\xi _{in}$ мы можем варьировать и получать различные значения I. Её максимум называется пропускной способностью канала

$C(\|r_{ij}\|)=\max _{p_{i}}I(\{\xi _{in}\,\xi _{out}\}).$ (eq:cdef)

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

Задача 1.

(task:shanon) Каково максимальное количество информации, которое можно передать с одним битом по каналу $\{\xi _{in},\,\xi _{out}\}$?

Конец задачи.

Итак, пропускная способность есть функция на множестве стохастических матриц^[2].

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

$\Omega _{in}=\Omega _{out}=\{0,1\}.$

$\|r_{ij}\|={\begin{array}{||cc||}1-p&p\\p&1-p\end{array}}\;.$ (eq:sm)

То есть канал с бинарным алфавитом и вероятностью помехи p (p — вероятность того, что бит будет случайно инвертирован). Его пропускная способность равна

$C=1-H(p)=1+p\log _{2}p+(1-p)\log _{2}{(1-p)}.$

Эта функция является решением задачи на максимум ((eq:cdef)) для матрицы ((eq:sm)).

\begin{figure}[t!] \centering\includegraphics[clip=true, width=0.75\textwidth]{pictures/cideal.eps} \caption{ $C(p)$ — Пропускная способность канала как функция вероятности инвертирования бита.} (fig:cideal) \end{figure}

Эта функция $C(p)$ (рис. (fig:cideal)) определяет предел помехоустойчивого кодирования — если мы хотим с абсолютной надёжностью передать по каналу с пропускной способностью C сообщение длиной m, то минимальное количество бит, которое нам нужно будет передать $n\geqslant m/C$. А точнее, всякое помехоустойчивое кодирование, обеспечивающее вероятность незамеченной ошибки в переданном слове меньше, чем $\varepsilon$, раздувает данные в $k_{\varepsilon }(m,p)$ раз и

$\lim _{\varepsilon \to 0}\lim _{m\to \infty }k_{\varepsilon }(m,p)\geqslant {1/C(p)}.$

Кодирование, при котором в этом пределе достигается равенство, называется эффективным. Отметим, что абсолютно надёжного способа передачи конечного количества данных по каналу с помехами не существует: то есть $k_{0}(m,p)=\infty .$

Задача дуальная (task:shanon) формулируется следующим образом

Задача 2.

(task:dual) Мы хотим передавать информацию со скоростью V по каналу с пропускной способностью C. Какова минимальная вероятность ошибочной передачи одного бита?

Конец задачи.

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

$C/V=1+p\log _{2}p+(1-p)\log _{2}(1-p)$, если $V/C>1$,

$p(V/C)=0$, если $V/C\leqslant 1$

Оказывается, вероятность ошибки растет не так уж и быстро. Например, если по каналу передавать данных в два раза больше, чем его пропускная способность, то лишь 11 бит из ста будут переданы с ошибкой.

\begin{figure}[t!] \psfrag{v}{v} \psfrag{p}{ $p(v)$} \centering\includegraphics[clip=true, width=0.75\textwidth]{pictures/pv.eps} \caption{ $p(v)$ — минимальная вероятность ошибки в одном бите как функция от отношения скорости передачи и пропускной способности $v=V/C$.} (fig:pv) \end{figure}

Построение конкретных способов кодирования, приближающихся по пропускной способности к теоретической границе — сложная математическая задача.

Метод «чётности» и общая идея

Простым примером кода с обнаружением одной ошибки является код с битом чётности. Конструкция его такова: к исходному слову добавляется бит чётности. Если в исходном слове число единичек чётно, то значение этого бита 0, если нечётно — 1. Таким образом допустимые слова этого кода имеют чётное количество единичек. Если получено слово с нечётным количеством единичек, то при передаче произошла ошибка.

В случае вероятных групповых ошибок эту технику можно скорректировать. Разобъём передаваемые данные на n слов по k бит и расположим их в виде матрицы $n\cdot k$ (n столбцов). Для каждого столбца вычислим бит чётности и разместим его в дополнительной строке. Матрица затем передается по строкам. По получению матрица восстанавливается, и если обнаруживется несоответствие, то весь блок передается повторно. Этот метод позволяет обнаружить групповые ошибки длины $\leq n$.

Задача 3.

Слово длиной n с чётным количеством единиц передано по каналу с уровнем шума p. Покажите, что вероятность того, что при передаче произошли ошибки и мы их не заметили равна

$P_{miss}(2,n,p)=C_{n}^{2}p^{2}(1-p)^{n-2}+C_{n}^{4}p^{4}(1-p)^{n-4}+\dots +C_{n}^{2k}p^{2k}(1-p)^{n-2k}+\dots$

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

$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}.$

Например, при $n=1000$ и $p=10^{-6}$ получаем $P_{miss}\approx 4.99\cdot 10^{-7}$

Конец задачи.

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

Задача 4. (task:errmod) Пусть у нас есть возможность контролировать

сумму единичек по модулю d. Тогда вероятность нефиксируемых ошибок в слове длиной n при передаче его по каналу с шумом p равна $P_{miss}(d,n,p)$:

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

$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},$

$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}=$

$={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}.$

Примечание. Интерес здесь представляет неявно заданная функция $n(d,P_{miss},p)$, а точнее даже коэффициент содержания полезной информации $KPS(n,P_{miss},p)={n-\log _{2}d \over n}$ в переданных n бит как функция от величины шума и вероятности незамеченных ошибок. Чем выше желаемая надёжность передачи, то есть чем меньше вероятность $P_{miss}$, тем меньше коэффициент содержания полезной информации.

Конец задачи.

Итак, с помощью одного бита чётности мы повышаем надёжность передачи, и вероятность незамеченной ошибки равна $P_{miss}(2,n,p)$. Это вероятность уменьшается с уменьшением n. При $n=2$ получаем $P_{miss}(2,2,p)=p^{2}$, это соответствует дублированию каждого бита. Рассмотрим общую идею того, как с помощью специального кодирования можно добиться сколь угодно высокой надёжности передачи.

Общая идея На множестве слов длины n определена метрика Хемминга: расстояние Хемминга между двумя словами равно количеству несовпадающих бит. Например,

$\rho _{H}(10001001,10110001)=3.$

Задача 5.

Докажите, что $\rho _{H}$ метрика.

Конец задачи.

Если два слова находятся на расстоянии r по Хеммингу, это значит, что надо инвертировать ровно r разрядов, чтобы преобразовать одно слово в другое. В описанном ниже кодировании Хемминга любые два различных допустимых слова находятся на расстоянии $\rho _{H}\geq 3$. Если мы хотим обнаруживать d ошибок, то надо, чтобы слова отстояли друг от друга на расстояние $\geq d+1$. Если мы хотим исправлять ошибки, то надо чтобы кодослова отстояли друг от друга на $\geq 2d+1$. Действительно, даже если переданное слово содержит d ошибок, оно, как следует из неравенства треугольника, все равно ближе к правильному слову, чем к какому-либо еще, и следовательно можно определить, исходное слово. Минимальное расстояние Хемминга между двумя различными допустимыми кодовыми словами называется расстоянием Хемминга данного кода.

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

$0000000000,\;0000011111,\;1111100000,\;1111111111.$

Расстояние по Хеммингу у этого кода 5, следовательно он может исправлять двойные ошибки и замечать 4 ошибки. Если получатель получит слово 0001010111, то ясно, что исходное слово имело вид 0000011111. Коэффициент раздувания равен 5. То есть исходное слово длины m будет кодироваться в слово длины $n=5m$

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

• $KPS(n)={\frac {m(n)}{n}}$ — коэффициент содержания полезной информации
• $k(m)={\frac {n(m)}{m}}$ — коэффициент раздувания информации

Первый есть функция от переменной n, а второй, обратный ему, — от переменной m.

Здесь мы подошли к довольно трудной задаче — минимизировать коэффициент раздувания для требуемой надёжности передачи. Она рассматривается в разделе (theory).

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

На практике активно применяются полиномиальные коды или циклические избыточные коды (Cyclic Redundancy Code — CRC).

CRC коды построены на рассмотрении битовой строки как строки коэффициентов полинома. k-битовая строка соответствует полиному степени $k-1$. Самый левый бит строки — коэффициент при старшей степени. Например, строка 110001 представляет полином $x^{5}+x^{4}+x^{0}$. Коэффициенты полинома принадлежат полю $G\mathbb {F} (2)$ вычетов по модулю 2.

Основная идея заключена в том, чтобы пересылать только такие сообщения, полиномы которых делятся на некоторый фиксированный полином $G(x)$. Если мы получаем сообщение, чей полином не делится на $G(x)$, значит при передаче сигнал был искажен. Мы не заметим ошибок, если они один допустимый полином (то есть полином делящийся на $G(x)$) преобразовали в другой допустимый полином. Полином $G(x)$ тем лучше, чем больше среднее расстояние Хемминга на парах допустимых полиномов.

Есть два очевидных способа кодирования сообщения в полином, который делится на $G(x)$ — это либо умножить полином исходного сообщения на $G(x)$, либо добавить к нашему сообщению некоторое количество бит так, чтобы результирующий полином делился на $G(x)$. В CRC используется второй способ.

Отправитель и получатель заранее договариваются о конкретном полиноме-генераторе $G(x)$. Пусть степень $G(x)$ равна l. Тогда длина блока «конторольной суммы» также равна l.

Мы добавляем контрольные l бит в конец передаваемого блоку так, чтобы получился полином кратный генератору $G(x)$. Когда получатель получает блок с контрольной суммой, он проверяет его делимость на G. Если есть остаток $\neq 0$, то были ошибки при передаче.

Алгоритм кодирования CRC:

Дано слово W длины m. Ему соответствует полином $W(x)$.

1. Добавить к исходному слову W справа r нулей. Получится слово длины $n=m+r$ и полином :$x^{r}\cdot W(x);$
2. Разделить полином $x^{r}\cdot W(x)$ на $G(x)$ и вычислить остаток от деления $R(x)$ :$x^{r}W(x)=G(x)Q(x)+R(x);$
3. Вычесть остаток (вычитание в $\mathbb {F} _{2}$ то же самое, что и сложение) из полинома $x^{r}\cdot W(x):$ :$T(x)=x^{r}W(x)-R(x)=x^{r}W(x)+R(x)=G(x)Q(x).$ Слово, которое соответствует полиному $T(x)$, и есть результат.

Рис. (fig:crc) иллюстрирует этот алгоритм для блока 1101011011 и ${G(x)=x^{4}+x+1}$.

\begin{figure}[h!] \psfrag{Remainder}{Остаток} \centering\parbox{0.66\textwidth}{ \begin{tabular}{lcl} Слово&:&1101011011 \\$G(x)$&:&10011\\ Результат&:&11010110111110 \end{tabular}} \centering\includegraphics[clip=true, width=0.75\textwidth]{pictures/crc2.eps} \caption{CRC — полиномиальное кодирование} (fig:crc) \end{figure}

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

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

• $CRC-12=x^{12}+x^{11}+x^{3}+x^{2}+x+1$
• $CRC-16=x^{16}+x^{15}+x^{2}+1$
• $CRC-CCITT=x^{16}+x^{12}+x^{5}+1$

$CRC-12$ используется для передачи символов из 6 разрядов. Два остальных — для 8 разрядных. $CRC-16$ и $CRC-CCITT$ ловят одиночные, двойные ошибки, групповые ошибки длины не более 16 и нечётное число изолированных ошибок с вероятностью 0.99997.

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

(theory) В примечании к задаче (task:errmod) было указано как можно получить значение коэффициента содержания полезной информации (КПС) на один бит, если передавать данные по каналу с шумом p словами длиной n бит, при условии, чтобы вероятность незамеченной ошибки была меньше $P_{miss}$.

Но ясно, что указанная там функция дает лишь оценку снизу оптимального значения КПС — возможно, существует другие методы контролирования ошибок, для которых он выше. Теория информации позволяет нам найти точное значение этого коэффициента.

Сформулируем задачу о кодировании, обнаруживающем ошибки. Для начала предположим, что наличие ошибки фиксируется с абсолютной точностью.

Задача 6.

(task:err) Мы хотим передавать информацию блоками, которые содержали бы m бит полезной информации, так, чтобы вероятность ошибки в одном бите равнялась p, а правильность передачи «фиксировалось контрольной суммой». Найти минимальный размер блока $n(m,p)$ и коэффициент раздувания $k={\frac {n(m)}{m}}$.

Конец задачи.

Решение. Для передачи m бит с вероятностью ошибки в отдельном бите p требуется передать $mC(p)$ бит (см. задачу (task:dual)). Кроме того мы хотим сообщать об ошибке в передаче. Её вероятность равна $(1-p)^{m}$, а значит информация, заложенная в этом сообщении, $H((1-p)^{m})$. В итоге получаем $n=mC(p)+H((1-p)^{m})$ и

$k(m,p)=C(p)+{\frac {H((1-p)^{m})}{m}}.$

Конец решения.

Заметим, что $k(1,p)=1$ — когда блок имеет размер один бит, сообщение об ошибке в нём равносильно передаче самого бита.

Если передавать эти сообщения по каналу с уровнем помех p, то количество бит на одно сообщение равно $mk(m,p)/C(p)$, то есть теоретическая оценка для количества лишних бит равна

${\frac {H((1-p)^{m})}{C(p)}}$

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

Коды Хэмминга

Элементарный пример кода исправляющего ошибки был показан на странице \pageref{simplecode}. Его обобщение очевидно. Для подобного кода, обнаруживающего одну ошибку, КПС равен $1 \over 3$. Оказывается это число можно сделать сколь угодно близким к единице с помощью кодов Хемминга. В частности, при кодировании 11 бит получается слово длинной 15 бит, то есть $KPS={\frac {11}{15}}$.

Оценим минимальное количество контрольных разрядов, необходимое для исправления одиночных ошибок. Пусть содержательная часть составляет m бит, и мы добавляем ещё r контрольных. Каждое из $2^{m}$ правильных сообщений имеет $n=m+r$ его неправильных вариантов с ошибкой в одном бите. Такими образом, с каждым из $2^{m}$ сообщений связано множество из $n+1$ слов и эти множества не должны пересекаться. Так как общее число слов $2^{n}$, то

${\begin{array}{c}(n+1)2^{m}\leqslant 2^{n}\\(m+r+1)\leqslant 2^{r}.\end{array}}$

Этот теоретический предел достижим при использовании метода, предложенного Хеммингом. Идея его в следующем: все биты, номера которых есть степень 2, — контрольные, остальные — биты сообщения. Каждый контрольный бит отвечает за чётность суммы некоторой группы бит. Один и тот же бит может относиться к разным группам. Чтобы определить какие контрольные биты контролируют бит в позиции k надо разложить k по степеням двойки: если $k=11=8+2+1$, то этот бит относится к трём группам — к группе, чья чётность подсчитывается в 1-ом бите, к группе 2-ого и к группе 8-ого бита. Другими словами в контрольный бит с номером $2^{k}$ заносится сумма (по модулю 2) бит с номерами, которые имеют в разложении по степеням двойки степень $2^{k}$:

${\begin{array}{l}b_{1}=b_{3}+b_{5}+b_{7}+\dots \\b_{2}=b_{3}+b_{6}+b_{7}+b_{10}+b_{11}+b_{14}+b_{15}\dots \\b_{4}=b_{5}+b_{6}+b_{7}+b_{12}+b_{13}+b_{14}+b_{15}\dots \\b_{8}=b_{9}+b_{10}+b_{11}+b_{12}+b_{13}+b_{14}+b_{15}\dots \\\end{array}}$ (eq:hem)

Код Хемминга оптимален при $n=2^{r}-1$ и $m=n-r$. В общем случае $m=n-[\log _{2}(n+1)]$, где $[x]$ — ближайшее целое число $\leqslant x$. Код Хемминга мы будем обозначать $Hem(n,m)$ (хотя n однозначно определяет m).

Пример для $Hem(15,11)$:

Невозможно разобрать выражение (SVG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «http://localhost:6011/ru.wikibooks.org/v1/»:): {\displaystyle \fbox{10110100111}\to \fbox{\fbox{0}\fbox{0}1\fbox{1}011\fbox{0}0100111} }

Невозможно разобрать выражение (неизвестная функция «\fbox»): {\displaystyle \hphantom{\fbox{10110100111}\to}\;\; \lefteqn{\,b_1}\hphantom{\fbox{0}} \lefteqn{\,b_2}\hphantom{\fbox{0}} \lefteqn{b_3}\hphantom{1} \lefteqn{\;b_4}\hphantom{\fbox{1}011} \lefteqn{\,b_8}\hphantom{\fbox{0}} \lefteqn{b_9}\hphantom{010011} \lefteqn{b_{15}}\hphantom{1} }

Получив слово, получатель проверяет каждый контрольный бит на предмет правильности чётности и складывая номера контрольных бит, в которых нарушена чётность. Полученное число, есть XOR номеров бит, где произошла ошибка. Если ошибка одна, то это число есть просто номер ошибочного бита.

Например, если в контрольных разрядах 1, 2, 8 обнаружено несовпадение чётности, то ошибка в 11 разряде, так как только он связан одновременно с этими тремя контрольными разрядами.

\begin{figure}[h!] \psfrag{Check bits}{\hspace{-12mm}Контрольные биты} \centering\includegraphics[clip=true, width=0.65\textwidth]{pictures/hem.eps} \caption{Кодирование Хемминга} (fig:hem) \end{figure}

Задача 7.

Покажите, что $KPS_{Hem(n,m)}\to 1$ при $n\to \infty$.

Конец задачи.

Код Хемминга может исправлять только единичные ошибки. Однако, есть приём, который позволяет распространить этот код на случай групповых ошибок. Пусть нам надо передать k кодослов. Расположим их в виде матрицы одно слово — строка. Обычно, передают слово за словом. Но мы поступим иначе, передадим слово длины k, из 1-ых разрядов всех слов, затем — вторых и т. д. По приёме всех слов матрица восстанавливается. Если мы хотим обнаруживать групповые ошибки размера k, то в каждой строке восстановленной матрицы будет не более одной ошибки. А с одиночными ошибками код Хемминга справится.

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

Начнём c небольшого примера. Пусть у нас есть канал с уровнем ошибок $p=10^{-6}$. Если мы хотим исправлять единичные ошибки при передаче блоками по $1023=2^{10}-1$ бит, то среди них потребуется 10 контрольных бит: 1, 2, \dots, $2^{9}$. На один блок приходится 1013 бит полезной информации. При передаче 1000 таких блоков потребуется $\Delta =10\,000$ контрольных бит.

В тоже время для обнаружения единичной ошибки достаточно одного бита чётности. И если мы применим технику повторной передачи, то на передачу 1000 блоков надо будет потратить 1000 бит дополнительно и примерно $0.001\approx p_{1014}=1-(1-10^{-6})^{1014}$ из них придется пересылать повторно. То есть на 1000 блоков приходится один попорченый, и дополнительная нагрузка линии составляет $\Delta \approx 1000+1001$, что меньше $10\,000$. Но это не значит, что код Хемминга плох для такого канала. Надо правильно выбрать длину блока — если $n>3444$, то код Хемминга эффективен.

Рассмотрим этот вопрос подробнее. Пусть нам нужно передать информацию M бит. Разобьем её на L блоков по $m=M/L$ бит и будем передавать двумя способами — с помощью кодов Хемминга и без них. При этом будем считать, что в обоих случаях осуществлено предварительное кодирование, позволяющее с вероятностью $1-\varepsilon$ определять ошибочность передачи. Это осуществляется путем добавления «лишней» информации. Обозначим коэффициент раздувания для этого кодирования $k_{\varepsilon }(m)$. После этого кодирования каждый блок несёт информацию $m'=k_{\varepsilon }(m)m$

1) Без кода Хемминга.

Если пересылать информацию блоками по $m'$ бит с повторной пересылкой в случае обнаружения ошибки, то получим, что в среднем нам придётся переслать D бит:

$D=Lm'{1 \over 1-P_{r}}$

Где $P_{r}=(1-(1-p)^{m'})(1-\varepsilon )$ — вероятность повторной передачи равная вероятности ошибки умноженной на вероятность того, что мы её заметим. Коэффициент раздувания равен

$k(m,p,\varepsilon )={\frac {D}{M}}={\frac {k_{\varepsilon }(m)}{\varepsilon +(1-\varepsilon )(1-p)^{k_{\varepsilon }(m)m}}}$

2) С кодом Хемминга.

При кодировании методом Хемминга слова длины $m'$ получается слово длины n бит:

$2^{n}=2^{m'}(n+1),\;\;k_{\varepsilon }(m)m=n-\log _{2}(n+1)$ (eq:hnm)

Для отдельного блока вероятность безошибочной передачи равна ${P_{0}=(1-p)^{n}}$. Вероятность одинарной ошибки ${P_{1}=np^{1}(1-p)^{n-1}}$. Вероятность того, что произошло более чем одна ошибка, и мы это заметили

$P_{r}={(1-P_{0}-P_{1})}{(1-\varepsilon )}={1-\varepsilon -(1-\varepsilon )(1-p)^{n-1}(np+1-p)}$

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

$D_{H}=Ln{1 \over 1-P_{r}}={Ln \over \varepsilon +(1-\varepsilon )(1-p)^{n-1}(np+1-p)}$

И коэффициент раздувания

$k_{H}(m,p,\varepsilon )={n \over m{\bigl (}\varepsilon +(1-\varepsilon )(1-p)^{n-1}(np+1-p){\bigr )}},$

где $n(m)$ неявно определённая с помощью ((eq:hnm)) функция. Удобно записать соответствующие коэффициенты полезного содержания:

$KPS=KPS_{\varepsilon }{\bigl (}n{\bigr )}{\bigl (}\varepsilon +(1-\varepsilon )(1-p)^{n}{\bigr )}$

$KPS_{H}={KPS_{\varepsilon }{\bigl (}m'{\bigr )}{\frac {m'}{n}}{\bigl (}\varepsilon +(1-p)^{n-1}(np+1-p)(1-\varepsilon ){\bigr )}},$, $m'=n-\log _{2}(n+1)$ (eq:kps)

Легко обнаружить что при $n>3444$ и $p=10^{-6}$ код Хемминга оказывается эффективнее, то есть $KPS_{H}/KPS>1$

\begin{figure}[h!] \psfrag{knc}{кпс} \psfrag{n}{n} \centering\includegraphics[clip=true, width=0.48\textwidth]{pictures/kps.eps} \centering\includegraphics[clip=true, width=0.48\textwidth]{pictures/kps2.eps} \caption{ $KPS(n,p,\varepsilon )$ — Коэффициент полезного содержания в канале с помехами как функция размера элементарного блока.} \parbox{0.85\textwidth}{\small Светлый график — без кодирования Хемминга;\\ Темный график — с кодированием Хемминга; \\Параметры: $\varepsilon =10^{-6}\;$; $p=10^{-6}.$} (fig:kps) \end{figure}

\begin{figure}[h!] \psfrag{C}{C} \psfrag{p}{p} \centering\includegraphics[clip=true, width=0.75\textwidth]{pictures/kpseff.eps} \caption{$C(p,\varepsilon )$ — максимальный коэффициент полезного содержания в канале с помехами как функция уровня помех.} \parbox{0.97\textwidth}{ \small Светлый график — без кодирования Хемминга;\\ Темный график — с кодированием Хемминга;\\Тонкий график — теоретический предел, задаваемый функцией $C(p)$\\Параметры: $\varepsilon =10^{-6}$.} (fig:kpseff) \end{figure}

Значение $KPS_{\varepsilon }(n)$ используемое в формулах ((eq:kps)) можно оценить как

$KPS_{\varepsilon }(n)={\log _{2}{\left(1-\varepsilon (2^{n}-1)\right)} \over n}$

Напомним, что $\varepsilon$ есть параметр желаемой надёжности передачи — чем меньше $\varepsilon$, тем надёжнее передача. По определению $\varepsilon =P_{miss}/(1-P_{0})$ — вероятности ошибочной передачи блока при условии, что «контрольная сумма сошлась» и кадр засчитан правильно переданным. Такое выражение для $KPS_{\varepsilon }(p,n)={\frac {m}{n}}$ получается из формулы

$\varepsilon ={\frac {2^{m}-1}{2^{n}-1}}$

Но это безусловно лишь оценочная формула. Оптимальное значение $KPS_{\varepsilon }$ значительно сложнее и зависит от p.

Из графика на рисунке (fig:kps) хорошо видно, что при больших n код Хемминга начинает работать на пользу.

Но зависимость КПС от n не есть критерий эффективности кода. Эффективность кода определяется функцией

$C(p,\varepsilon )=\min _{n}{KPS(p,n,\varepsilon )}$

На рисунке (fig:kpseff) показан график этой функции и из него ясно, что код Хемминга можно использовать с пользой всегда — при любых $\varepsilon$ и p, если у нас есть возможность выбирать подходящее n.

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

То, что на множестве {0,1} есть структура числового поля, позволяет осуществлять алгебраические интерпретации кодирования. Заметим, в частности, что как коды Хемминга, так и циклические коды линейны:\\ 1) отношения ((eq:hem)) на с. \pageref{eq:hem}, связывающие контрольные биты кода Хемминга с другими линейны,\\ 2) остаток от деления суммы многочленов на третий равен сумме остатков.\\ То есть кодирование в этих двух случаях есть линейное отображение из $G\mathbb {F} (2)^{m}$ в $G\mathbb {F} (2)^{n}$. Поясним на примерах. Ниже представлена матрица кода Хемминга $Hem(7,4)$ (см. соотношения ((eq:hem))). Исходное слово есть ${\mathbf {w} _{in}={\overline {b_{3}b_{5}b_{6}b_{7}}}}$, а результирующее ${\mathbf {w} _{out}={\overline {b_{1}b_{2}b_{3}b_{4}b_{5}b_{6}b_{7}}}=\mathbf {A} _{Hem(7,4)}\mathbf {w} _{in}}$ (слова соответствуют столбцам).

$\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\\0&0&0&1\end{Vmatrix}}$

Процесс выявления ошибок тоже линейная операция, она осуществляется с помощью проверочной матрицы $\mathbf {H}$. Пусть принято слово $\mathbf {w'} _{out}$. Слово $\mathbf {s} ={\overline {s_{1}s_{2}s_{3}}}=\mathbf {H} \mathbf {w'} _{out}$ в случае правильной передачи должно быть равно 000. Значение $\mathbf {s}$ называется синдромом ошибки. i-ый разряд слова $\mathbf {s}$ контролирует i-ое соотношение в ((eq:hem)) и, таким образом, $\mathbf {s}$ равно сумме номеров бит в которых произошла ошибка, как векторов в $G\mathbb {F} (2)^{3}$.

$\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\end{Vmatrix}}$

Заметим, что столбцы проверочной матрицы представляют собой последовательно записанные в двоичной форме натуральные числа от 1 до 7.

Вычиcление рабочей матрицы для циклических кодов основывается на значениях $G_{n}(x)=x^{n}\;\mathop {mod} \;G(x)$. Верхняя её часть равна единичной, так m бит сообщения помещаются без изменения в начало слова, а нижние r строчек есть m столбцов высоты r состоящие из коэффициентов многочленов $G_{n}$, $G_{n-1}$, \dots, $G_{n-r}$. Например, для $G(x)=x^{3}+x+1$ и $m=4$ имеем $r=3$, $n=7$ и

${\begin{vmatrix}G_{0}&G_{1}&G_{2}&G_{3}&G_{4}&G_{5}&G_{6}&G_{7}\\1&x^{1}&x^{2}&x+1&x^{2}+x&x^{2}+x+1&x^{2}+1&1\\001&010&100&011&110&111&101&001\end{vmatrix}}$

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

$\mathbf {A} =\left\|{\begin{array}{c}E_{4}\\G_{6}G_{5}G_{4}G_{3}\end{array}}\right\|,\quad \mathbf {H} =\|G_{6}G_{5}G_{4}G_{3}E_{3}\|,$

то есть

$\mathbf {A} ={\begin{Vmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\\1&1&1&0\\0&1&1&1\\1&1&0&1\end{Vmatrix}},\;\;\;\mathbf {H} ={\begin{Vmatrix}1&1&1&0&1&0&0\\0&1&1&1&0&1&0\\1&1&0&1&0&0&1\end{Vmatrix}}.$

Кроме рабочей и проверочной матриц есть ещё множество порождающих матриц $\mathbf {G}$ и декодирующих матриц $\mathbf {D}$. Понятно, что в случае линейных кодов допустимые слова образуют линейное подпространство $L\subset G\mathbb {F} (2)^{n}$ равное $\mathbf {Im(A)}$. Любая матрица, столбцы которой образуют базис этого подпространства, называется порождающей. В частности, рабочая матрица является порождающей. Способность обнаруживать и исправлять ошибки однозначно определяется подпространством L. Порождающих, рабочих и проверочных матриц соответствующих L несколько.

Действительно, в порождающей и рабочей матрицах можно осуществлять элементарные операции со столбцами, а в проверочной — со строчками. Матрицы $\mathbf {A}$, $\mathbf {H}$ и $\mathbf {G}$ всегда удовлетворяют отношениям

$\mathbf {H} \cdot \mathbf {A} =\mathbf {0} _{rm},\;\mathbf {H} \cdot \mathbf {G} =\mathbf {0} _{rm},$

где $\mathbf {0} _{rm}$ — нулевая матрица $r\times m$.

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

Декодирующая матрица $\mathbf {D}$ должна декодировать: $\mathbf {w} _{in}=\mathbf {D} \cdot \mathbf {w} _{out}$. Матриц с таким свойством может быть несколько. Множество декодирующих матриц определяется рабочей матрицей:

$\mathbf {D} \cdot \mathbf {A} =\mathbf {E} _{m},$

где $\mathbf {E} _{m}$ — единичная матрица $m\times m$. На подпространстве L все декодирующие матрицы действуют одинаково. Они отличаются на подпространстве ортогональном L. Приведём декодирующую матрицу для $Hem(7,4)$ и $CRC_{n=7,\;m=7}$:

$\mathbf {D} _{H_{7,4}}={\begin{Vmatrix}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\end{Vmatrix}},\;\;\;\mathbf {D} _{C_{7,4}}={\begin{Vmatrix}1&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&0&0\end{Vmatrix}}.$

К каждой строчке декодирующей матрицы можно добавить любую линейную комбинацию строчек из проверочной матрицы. Следует отметить, что процесс исправления ошибок для кодов Хемминга нелинеен и его нельзя «внедрить» в декодирующую матрицу.

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

1. Процесс кодирования и декодирования — линейные операторы. :$\mathbf {w} _{out}=\mathbf {A} \mathbf {w} _{in},\;\;channel:\mathbf {w} _{out}\mapsto \mathbf {w} '_{out},\;\;\mathbf {w} '_{in}=\mathbf {D} \mathbf {w} '_{out}$
2. Обнаружение ошибок равносильно проверке принадлежности полученного слова подпространству L допустимых слов. Для этого необходимо найти проекцию $\mathbf {s}$ (синдром ошибки) полученного слова на $L^{\perp }$ — тоже линейная операция. Для правильно переданного слова $\mathbf {s} =\mathbf {0}$. :$\mathbf {s} =\mathbf {H} \mathbf {w} '_{out}$
3. В случае, когда векторы подпространства L достаточно удалены друг от друга в смысле метрики Хемминга, есть возможность обнаруживать и исправлять некоторые ошибки. В частности, значение синдрома ошибки в случае кода Хемминга равно векторной сумме номеров бит, где произошла ошибка.
4. Комбинация (композиция) линейных кодов есть снова линейный код.

Практические методы помехоустойчивого кодирования все основаны на линейных кодах. В основном это модифицированные CRC, коды Хемминга и их композиции. Например $Hem(7,4)$ плюс проверка на чётность. Такой код может исправлять уже две ошибки. Построение эффективных и удобных на практике задача сходная с творчеством художника. На практике важны не только корректирующая способность кода, но и вычислительная сложность процессов кодирования и декодирования, а также спектральная характеристика результирующего аналогового сигнала. Кроме того, важна способность исправлять специфические для данного физического уровня групповые ошибки.

Задача 8.

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

$\mathbf {H} ={\begin{Vmatrix}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\end{Vmatrix}}$

Подсказка

1. Это проверочная матрица $Hem(7,4)$ плюс условие на чётность числа единичек в закодированном слове вместе с дополнительным восьмым контрольным битом.
2. Кодовое расстояние равно минимальному количеству линейно зависимых столбцов в $\mathbf {H}$.

Конец задачи.

Задача 9.

Посторойте декодирующую и проверочную матрицу для циклического кода с $G(x)=x^{3}+x+1$ и $m=4$ при условии, что в качестве рабочей матрицы использовалась матрица

$\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}}.$

Конец задачи.

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

После перехода на язык линейной алгебры естественно возникает желание изучить свойства линейных кодов над другими конечными числовыми полями. С помощью такого обобщения появились коды Рида-Соломона.

Коды Рида-Соломона являются циклическими кодами над числовым полем отличным от $G\mathbb {F} (2)$.

Напомним, что существует бесконечное количество конечных полей, и количество элементов в конечном поле всегда равно степени простого числа. Если мы зафиксируем число элементов $n=q^{k}$, то найдётся единственное с точностью до изоморфности конечное поле с таким числом элементов, которое обозначается как $G\mathbb {F} (n)$. Простейшая реализация этого поля — множество многочленов по модулю неприводимого^[3] многочлена $p(x)$ степени k над полем $\mathbb {F} _{q}$ вычетов по модулю q. В случае многочленов с действительными коэффициентами неприводимыми многочленами являются только квадратные многочлены с отрицательным дискриминантом. Поэтому существует только квадратичное расширение действительного поля — комплексные числа. А над конечным полем существуют неприводимые многочлены любой степени. В частности, над $\mathbb {F} _{2}$ многочлен $g(z)=z^{3}+z+1$ неприводим и множество многочленов по модулю $g(z)$ образуют поле из $2^{3}=8$ элементов.

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

HDLC протокол

Здесь мы познакомимся с группой протоколов давно известных, но по-прежнему широко используемых. Все они имеют одного предшественника — SDLC (Synchronous Data Link Control) - протокол управления синхронным каналом, предложенным фирмой IBM в рамках SNA. ISO модифицировала этот протокол и выпустила под названием HDLC — High level Data Link Control. MKTT модифицировала HDLC для X.25 и выпустила под именем LAP - Link Access Procedure. Позднее он был модифицирован в LAPB.

Все эти протоколы построены на одних и тех же принципах. Все используют технику вставки специальных последовательностей битов. Различия между ними незначительные.

\begin{figure}[h!] \centering\includegraphics[clip=true, width=0.88\textwidth]{pictures/frame.eps} \caption{Типовая структура кадра} (fig:frame) \end{figure}

На рис. (fig:frame) показана типовая структура кадра. Поле адреса используется для адресации терминала, если их несколько на линии. Для линий точка-точка это поле используется для различия команды от ответа.

• Поле Control используется для последовательных номеров кадров, подтверждений и других нужд.
• Поле Data может быть сколь угодно большим и используется для передачи данных. Надо только иметь ввиду, что чем оно длиннее тем, больше вероятность повреждения кадра на линии.
• Поле Checksum — это поле используется CRC кодом.

Флаговые последовательности 01111110 используются для разделения кадров и постоянно передаются по незанятой линии в ожидании кадра. Существуют три вида кадров: $Information$, $Supervisory$, Unnumbered.

Организация поля Control для этих трех видов кадров показана на рис. (fig:cfield). Как видно из размера поля Seq в окне отправителя может быть до 7 неподтверждённых кадров. Поле Next используется для посылки подтверждения вместе с передаваемым кадром. Подтверждение может быть в форме номера последнего правильно переданного кадра, а может быть в форме первого не переданного кадра. Какой вариант будет использован — это параметр.

\begin{figure}[h!] \centering\includegraphics[clip=true, width=0.88\textwidth]{pictures/cfield.eps} \caption{Cтруктура поля Control} \parbox{0.66\textwidth}{\small (а) Информационный кадр ($Information$)\\ (б) Управляющий кадр ($Supervisory$)\\(в) Ненумерованный кадр (Unnumbered) } (fig:cfield) \end{figure}

Разряд $P/F$ использует при работе с группой терминалов. Когда компьютер приглашает терминал к передаче он устанавливает этот разряд в P. Все кадры, посылаемые терминалами имеют здесь P. Если это последний кадр, посылаемый терминалом, то здесь стоит F.

$Supervisory$ кадры имеют четыре типа кадров.

• Тип 0 — уведомление в ожидании следующего кадра (RECEIVE READY). Используется когда нет встречного трафика, чтобы передать уведомление в кадре с данными.
• Тип 1 — негативное уведомление (REJECT) — указывает на ошибку при передаче. Поле Next указывает номер кадра, начиная с которого надо перепослать кадры.
• Тип 2 — RECEIVE NOT READY. Подтверждает все кадры, кроме указанного в Next. Используется, чтобы сообщить источнику кадров об необходимости приостановить передачу в силу каких-то проблем у получателя. После устранения этих проблем получатель шлет RECEIVE REDAY, REJECT или другой надлежащий управляющий кадр.
• Тип 3 — SELECTIVE REJECT — указывает на необходимость перепослать только кадр, указанный в Next. LAPB и SDLC не используют этого типа кадров.

Третий класс кадров — Unnubered. Кадры этого класса иногда используются для целей управления, но чаще для передачи данных при ненадёжной передаче без соединения.

Все протоколы имеют команду DISConnect для указания о разрыве соединения, SNRM и SABM — для установки счётчиков кадров в ноль, сброса соединения в начальное состояние, установки соподчинённости на линии. Команда FRMR — указывает на повреждение управляющего кадра.

1. ^  Идея рассмотрения информации как меры на множестве ещё не до конца исчерпала себя — такой меры ещё не построено. Однако доказано, что с помощью этой аналогии можно доказывать неравенства, например ${I(\{\xi _{in}\,\xi _{out}\})\geqslant 0}$.
2. ^  Матрица называется стохастической, если все её элементы неотрицательны и сумма элементов в каждом столбце равна единице.
3. ^  Многочлен называется неприводимым, если он не разлагается в произведение многочленов меньшей степени.