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

Пробую автоматически получить из TeXa викиразметку
(Пробую автоматически получить из TeXa викиразметку)
 
==sdfga dfg <math>a=\{\begin{array} \end{array}</math> ==
 
 
==Аннотация==
 
значений которой - слова фиксированной длины <math>r</math>.
 
Эти <i>r</i> бит добавляются обычно в конец кадра. При приёме
контрольная сумма вычисляется заново и сравнивается с той, что
храниться в кадре. Если они различаются, то это признак ошибки
нет единого таймера, нет гарантии, что эта пауза сохраниться или,
наоборот, не появятся новые. Так как временные методы ненадёжны,
то применяются другие. Здесь мы рассмотрим четыретри основных:
* счетчик символов;
* вставка специальных стартовых и конечных символов или последовательностей бит;
Второй метод построен на вставке специальных символов.
Обычно для этого используют управляющие последовательности:
последовательность <math>DLE\; STX</math> для начала кадра и <math>DLE\; ETX</math>
для конца кадра. <math>DLE</math> — Data Link Escape; <math>STX</math> — Start
TeXt, <math>ETX</math> — End TeXt. При этом методе если даже была
 
===Контроль ошибок===
 
Решив проблему разбиения на кадры, мы приходим к следующей
проблеме: как обеспечить, чтобы кадры, пройдя по физическому
надлежащей последовательности и в надлежащем виде?
 
Частичное решение этой проблемы осуществляется посредством
введения обратной связи между отправителем и получателем в
виде кадра подтверждения, а также специального кодирования,
заново.
 
Однако, возможны случаи когда из-за ошибок в канале
кадр исчезнет целиком. В этом случае получатель не будет
реагировать никак, а отправитель будет сколь угодно долго ждать
считать, что кадр потерян и повторит его еще раз.
 
Однако, если кадр-подтверждение был утерян, то вполне возможно, что один и
тот же кадр получатель получит дважды. Как быть? Для решения
этой проблемы каждому кадру присваивают порядковый номер. С
 
===Управление потоком===
 
Другая важная проблема, которая решается на канальном уровне
— управление потоком. Вполне может
 
==Помехоустойчивое кодирование==
 
===Характеристики ошибок===
 
Физическая среда, по которой передаются данные не может быть
абсолютно надёжной. Более того, уровень шума бывает очень
 
Основной характеристикой ''интенсивности помех'' в канале
является параметр шума — <i class="formula">p</i>. Это число от 0 до 1, равное
вероятности инвертирования бита, при условии что, он был
передан по каналу и получен на другом конце.
битами.
 
У групповых ошибок есть свои плюсы и минусы. Плюсы
заключаются в следующем. Пусть данные передаются блоками по
1000 бит, а уровень ошибки 0,001 на бит. Если ошибки
изолированные и независимые, то 63\% (<math>0.63\approx
1-0.999^{1000}</math>) блоков будут содержать ошибки. Если же они
возникают группами по 100 сразу, то ошибки будут содержать
1\% (<math>0.01\approx 1-0.999^{10}</math>) блоков.
 
Зато, если ошибки не группируются, то в каждом кадре они невелики,
и есть возможность их исправить. Групповые ошибки портят
кадр безвозвратно. Требуется его повторная пересылка, но в
Для надёжной передачи кодов было предложено два основных метода.
 
''Первый'' заключается в добавлении в передаваемый блок
данных нескольких &laquo;лишних&raquo; битов так, чтобы, анализируя
полученный блок, можно было бы сказать есть в переданном
 
Такое деление условно. Более общий вариант — это коды
обнаруживающие <i class="formula">k</i> ошибок и исправляющие <i class="formula">l</i> ошибок, где
<math>l<k</math>.
 
===* Элементы теории передачи информации===
 
''Информационным каналом'' называется пара ''зависимых''
случайных величин <math>\{\xi_{in},\,\xi_{out}\}</math>, одна из них
называется входом другая выходом канала. Если случайные величины
дискретны и конечны, то есть имеют конечные множества событий:
 
<i class="formula"></i>\Omega_{in}={x_1,\dots, x_a},\;\Omega_{out}={y_1,\dots, y_b},<i class="formula"></i>
:<math>\Omega_{in}=\{x_1,\dots, x_a\},\;\Omega_{out}=\{y_1,\dots, y_b\},</math>
 
то канал определяется матрицей условных вероятностей
<math>\|r_{ij}\|</math>, <math>r_{ij}</math> — вероятность того, что на выходе
выходе вычисляется по формуле
 
 
<i class="formula"></i>q_i=\sum_{j=1}^{a}r_{ij}p_j.<i class="formula"></i>
:<math>q_i=\sum_{j=1}^{a}r_{ij}p_j.</math>
 
Объединённое распределение на
<math>\Omega_{in}\times\Omega_{out}</math> равно
 
 
<i class="formula"></i>P_{ij}=r_{ij}p_j.<i class="formula"></i>
:<math>P_{ij}=r_{ij}p_j.</math>
 
 
Информация <math>I(\{\xi_{in},\,\xi_{out}\})</math>, передаваемая через
 
:<math>
 
\label{eq:inf}
I(\{\xi_{in}\,\xi_{out}\})=H(\xi_{in})+H(\xi_{out})-H(\{\xi{in},\xi_{out}\}),
</math> <b>(eq:inf)</b>
 
где <i class="formula"></i>H(\xi_{in})=-\sum_{i=1}^ap_i\log_2 p_i,<i class="formula"></i>
где
<i class="formula"></i>H(\xi_{out})=-\sum_{i=1}^aq_i\log_2 q_i,<i class="formula"></i>
:<i class="formula"></imath>H({\xi_{in},\,\xi_{out}})=-\sum_{i,j}P_{ij=1}^ap_i\log_2 P_{ij}.<i class="formula">p_i,</imath>
 
 
:<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> независимы (то
<math>\{\xi_{in},\,\xi_{out}\}</math> невозможно передавать информацию и
<math>I(\{\xi_{in},\,\xi_{out}\})=0</math>. Понять суть формулы
(\ref{<b>(eq:inf})</b>) можно из следующего соображения: энтропия случайной
величины равна информации, которую мы получаем при одном её
измерении. <math>H(\xi_{in})</math> и <math>H(\xi_{out})</math> — информация, которая
меры{{ref|note1}} есть выражение
аналогичное (\ref{eq:inf}):
 
<i class="formula"></i>\mu(A\wedge B)=\mu(A)+\mu(B)-\mu(A\vee B).<i class="formula"></i>
:<math>\mu(A\wedge B)=\mu(A)+\mu(B)-\mu(A\vee B).</math>
 
 
 
Распределение входной случайной величины <math>\xi_{in}</math> мы можем
варьировать и получать различные значения <i class="formula">I</i>. Её максимум
называется пропускной способностью канала
 
:<math>
 
\label{eq:cdef}
C(\|r_{ij}\|)=\max_{p_i}I(\{\xi_{in}\,\xi_{out}\}).
</math> <b>(eq:cdef)</b>
 
Эта функция есть решение задачи
\begin{task}
\label{<b>(task:shanon})</b> Каково максимальное количество информации,
которое можно передать с одним битом по каналу
<math>\{\xi_{in},\,\xi_{out}\}</math>?
 
Стандартный информационный канал это
 
<i class="formula"></i>\Omega_{in}=\Omega_{out}={0,1}.<i class="formula"></i>
:<math>\Omega_{in}=\Omega_{out}=\{0,1\}.</math>
 
 
 
:<math>
 
\label{eq:sm}
\|r_{ij}\|=\begin{array}{||cc||} 1-p &p\\ p& 1-p
\end{array}\;.
</math> <b>(eq:sm)</b>
 
То есть канал с бинарным алфавитом и вероятностью помехи <i class="formula">p</i>
То есть канал с бинарным алфавитом и вероятностью помехи <i>p</i>
(<i class="formula">p</i> — вероятность того, что бит будет случайно
(<i>p</i> — вероятность того, что бит будет случайно
инвертирован). Его пропускная способность равна
 
<i class="formula"></i>C= 1-H(p)=1+p\log_2p+(1-p)\log_2{(1-p)}.<i class="formula"></i>
:<math>C= 1-H(p)=1+p\log_2p+(1-p)\log_2{(1-p)}.</math>
 
Эта функция является решением задачи на максимум (\ref{eq:cdef})
для матрицы&nbsp;(\ref{eq:sm}).
Эта функция <math>C(p)</math> (рис.&nbsp;\ref{fig:cideal}) определяет предел
помехоустойчивого кодирования — если мы хотим с абсолютной
надёжностью передать по каналу с пропускной способностью <i class="formula">C</i>
сообщение длиной <i class="formula">m</i>, то минимальное количество бит, которое нам
нужно будет передать&nbsp;<math>n\geqslant m/C</math>. А точнее, всякое
помехоустойчивое кодирование, обеспечивающее вероятность
раздувает данные в <math>k_{\varepsilon}(m,p)</math> раз и
 
 
<i class="formula"></i>\lim_{\varepsilon\to 0}\lim_{m\to\infty}k_{\varepsilon}(m,p)\geqslant {1/C(p)}.<i class="formula"></i>
:<math>\lim_{\varepsilon\to 0}\lim_{m\to\infty}k_{\varepsilon}(m,p)\geqslant {1/C(p)}.</math>
 
Кодирование, при котором в этом пределе достигается
равенство, называется ''эффективным''. Отметим, что
\begin{task}
\label{task:dual}
Мы хотим передавать информацию со скоростью <i class="formula">V</i> по каналу с
пропускной способностью <i class="formula">C</i>. Какова минимальная вероятность
ошибочной передачи одного бита?
\end{task}
Решением будет функция заданная неявно
 
<i class="formula"></i>C/V=1+p\log_2p+(1-p)\log_2(1-p),\mbox{ если <math>V/C>1</math>},<i class="formula"></i>
<i class="formula"math><C/i>V=1+p\log_2p+(V/C1-p)=0,\mbox{log_2(1-p)</math>, если <math>V/C\leqslant >1</math>}.<i class="formula"></i>,
 
<math>p(V/C)=0</math>, если <math>V/C\leqslant 1</math>
 
Оказывается, вероятность ошибки растет не так уж и быстро.
Например, если по каналу передавать данных в два раза
\begin{center}
\begin{figure}[t!]
\psfrag{v}{<i class="formula">v</i>} \psfrag{p}{ <math>p(v)</math>}
\centering\includegraphics[clip=true,
width=0.75\textwidth]{pictures/pv.eps} \caption{ <math>p(v)</math> —
сложная математическая задача.
 
===Метод &laquo;чётности&raquo; и общая идея=== Простым примером
Простым примером
кода с обнаружением одной ошибки является код с битом чётности.
Конструкция его такова: к исходному слову добавляется бит
 
В случае вероятных групповых ошибок эту технику можно
скорректировать. Разобъём передаваемые данные на <i class="formula">n</i> слов по <i class="formula">k</i>
бит и расположим их в виде матрицы&nbsp;<math>n\cdot k</math> (<i class="formula">n</i>&nbsp;столбцов). Для
каждого столбца вычислим бит чётности и разместим его в
дополнительной строке. Матрица затем передается по строкам. По
 
\begin{task}
Слово длиной <i class="formula">n</i> с чётным количеством единиц передано по каналу с
уровнем шума <i class="formula">p</i>. Покажите, что вероятность того, что при
передаче произошли ошибки и мы их не заметили равна
 
<i class="formula"></i>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>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
<i class="formula"></i>
</math>
 
Что можно привести к виду
 
<i class="formula"></i>
:<math>
\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>
<i class="formula"></i>
 
Например, при <math>n=1000</math> и <math>p=10^{-6}</math> получаем <math>P_{miss}\approx
4.99\cdot 10^{-7}</math>
\begin{task}[*]
\label{task:errmod} Пусть у нас есть возможность контролировать
сумму единичек по модулю&nbsp;<i class="formula">d</i>. Тогда вероятность нефиксируемых
ошибок в слове длиной <i class="formula">n</i> при передаче его по каналу с шумом <i class="formula">p</i>
равна <math>P_{miss}(d,n,p)</math>:
 
<i class="formula"></i>
:<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>
<i class="formula"></i>
 
''Примечание.'' Интерес здесь представляет неявно
заданная функция <math>n(d,P_{miss},p)</math>, а точнее даже коэффициент
содержания полезной информации
<math>\mbox{КПС}KPS(n,P_{miss},p)={n-\log_2 d \over n}</math> в переданных <i class="formula">n</i>
бит как функция от величины шума и вероятности незамеченных
ошибок. Чем выше желаемая надёжность передачи, то есть чем меньше
Итак, с помощью одного бита чётности мы повышаем надёжность
передачи, и вероятность незамеченной ошибки равна
<math>P_{miss}(2,n,p)</math>. Это вероятность уменьшается с уменьшением <i class="formula">n</i>.
При <math>n=2</math> получаем <math>P_{miss}(2,2,p)=p^2</math>, это соответствует
дублированию каждого бита. Рассмотрим общую идею того, как с
высокой надёжности передачи.
 
''Общая идея'' На множестве слов длины <i class="formula">n</i> определена
метрика Хемминга: расстояние Хемминга между двумя словами
равно количеству несовпадающих бит. Например,
 
<i class="formula"></i>\rho_H(10001001,10110001)=3.<i class="formula"></i>
:<math>\rho_H(10001001,10110001)=3.</math>
 
\begin{task}
Докажите, что <math>\rho_H</math> метрика.
\end{task}
Если два слова находятся на расстоянии <i class="formula">r</i> по Хеммингу,
это значит, что надо инвертировать ровно <i class="formula">r</i> разрядов, чтобы
преобразовать одно слово в другое. В описанном ниже
кодировании Хемминга любые два различных допустимых слова
находятся на расстоянии <math>\rho_H\geqslant 3</math>. Если мы хотим
обнаруживать <i class="formula">d</i> ошибок, то надо, чтобы слова отстояли друг
от друга на расстояние <math>\geqslant d+1</math>. Если мы хотим
исправлять ошибки, то надо чтобы кодослова отстояли друг от
друга на <math>\geqslant 2d+1</math>. Действительно, даже если
переданное слово содержит <i class="formula">d</i> ошибок, оно, как следует из
неравенства треугольника, все равно ближе к правильному
слову, чем к какому-либо еще, и следовательно можно
которого есть только четыре ''допустимых кодовых
слова'':\\
 
<i class="formula"></i>0000000000,\; 0000011111,\; 1111100000,\; 1111111111.<i class="formula"></i>
:<math>0000000000,\; 0000011111,\; 1111100000,\; 1111111111.</math>
 
 
Расстояние по Хеммингу у этого кода 5, следовательно он может
исправлять двойные ошибки и замечать 4 ошибки. Если получатель
получит слово <i class="formula">0001010111</i>, то ясно, что исходное слово имело
вид <i class="formula">0000011111</i>. Коэффициент раздувания равен&nbsp;5. То есть
исходное слово длины <i class="formula">m</i> будет кодироваться в слово длины <math>n=5m</math>
 
Отметим что имеет смысл говорить о двух коэффициентах:\\
\begin{tabular}{l}
<math>\mbox{КПС}KPS(n)=\frac{m(n)}{n}</math> — коэффициент содержания
полезной информации\\
<math>k(m)=\frac{n(m)}{m}</math> — коэффициент раздувания информации
\end{tabular}\\
Первый есть функция от переменной <i class="formula">n</i>, а второй, обратный
ему, — от переменной <i class="formula">m</i>.
 
Здесь мы подошли к довольно трудной задаче —
 
===Циклические коды===
На практике активно применяются полиномиальные коды
 
На практике активно применяются полиномиальные коды
или циклические избыточные коды ('''Cyclic Redundancy Code
— <mathi>CRC</mathi>''').
 
<mathi>CRC</mathi> коды построены на рассмотрении битовой строки как
строки коэффициентов полинома. <i class="formula">k</i>-битовая строка
соответствует полиному степени <math>k-1</math>. Самый левый бит строки
— коэффициент при старшей степени. Например, строка <i class="formula">110001</i>
представляет полином <math>x^5+x^4+x^0</math>. Коэффициенты полинома
принадлежат полю <math>G\mathbb{F}(2)</math> вычетов по модулю&nbsp;2.
сообщения на <math>G(x)</math>, либо добавить к нашему сообщению некоторое
количество бит так, чтобы результирующий полином делился на
<math>G(x)</math>. В <mathi>CRC</mathi> используется второй способ.
 
Отправитель и получатель заранее договариваются
о конкретном ''полиноме-генераторе'' <math>G(x)</math>. Пусть степень
<math>G(x)</math> равна <i class="formula">l</i>. Тогда длина блока &laquo;конторольной суммы&raquo; также
равна <i class="formula">l</i>.
Мы добавляем контрольные <i class="formula">l</i> бит в конец передаваемого
блоку так, чтобы получился полином кратный генератору
<math>G(x)</math>. Когда получатель получает блок с контрольной суммой,
он проверяет его делимость на <i class="formula">G</i>. Если есть остаток <math>\neq
0</math>, то были ошибки при передаче.
 
''Алгоритм кодирования <mathi>CRC</mathi>:''
 
''Дано слово <i class="formula">W</i> длины <i class="formula">m</i>. Ему соответствует полином
<math>W(x)</math>.''
\begin{enumerate}
* ''Добавить к исходному слову <i class="formula">W</i> справа <i class="formula">r</i> нулей.
Получиться слово длины <math>n=m+r</math> и полином
<i class="formula"></i>x^r\cdot W(x);<i class="formula"></i>''
* ''Разделить полином <math>x^r\cdot W(x)</math> на <math>G(x)</math> и
вычислить остаток от деления <math>R(x)</math>
<i class="formula"></i>x^r W(x)=G(x)Q(x)+R(x);<i class="formula"></i>''
* ''Вычесть остаток (вычитание в <math>\mathbb{F}_2</math> то же
самое, что и сложение) из полинома <math>x^r\cdot W(x):</math>
 
''Дано слово <i>W</i> длины <i>m</i>. Ему соответствует полином <math>W(x)</math>.''
<i class="formula"></i>T(x)=x^r W(x)-R(x)=x^r W(x)+R(x)=G(x)Q(x).<i class="formula"></i>
 
# ''Добавить к исходному слову <i>W</i> справа <i>r</i> нулей. Получиться слово длины <math>n=m+r</math> и полином :<math>x^r\cdot W(x);</math> ''
Слово, которое соответствует полиному <math>T(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> ''
\end{enumerate}
# ''Вычесть остаток (вычитание в <math>\mathbb{F}_2</math> то же самое, что и сложение) из полинома <math>x^r\cdot W(x):</math> :<math>T(x)=x^r W(x)-R(x)=x^r W(x)+R(x)=G(x)Q(x).</math> Слово, которое соответствует полиному <math>T(x)</math>, и есть результат.''
Рис.&nbsp;\ref{fig:crc} иллюстрирует этот алгоритм для блока
<i class="formula">1101011011</i> и <math>{G(x)=x^4+x+1}</math>.
 
\begin{figure}[h!]
\end{tabular}}
\centering\includegraphics[clip=true,
width=0.75\textwidth]{pictures/crc2.eps} \caption{CRC —
\caption{CRC — полиномиальное кодирование} \label{fig:crc}
\label{fig:crc}
\end{figure}
 
 
Существует три международных стандарта на вид <math>G(x)</math>:
\begin{itemize}
* <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>
\end{itemize}
 
* <math>CRC-12 = x^{12} + x^{11}+x^3+x^2+x+1</math>
<math>CRC-12</math> используется для передачи символов из <i class="formula">6</i> разрядов.
* <math>CRC-16 =x^{16}+x^{15}+x^2+1</math>
Два остальных — для <i class="formula">8</i> разрядных. <math>CRC-16</math> и <math>CRC-CCITT</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 class="formula">0.99997</i>.
 
 
===* Теоретический предел=== \label{theory} В примечании
\label{theory} В примечании
к задаче&nbsp;\ref{task:errmod} было указано как можно получить
значение коэффициента содержания полезной информации (КПС) на
один бит, если передавать данные по каналу с шумом <i class="formula">p</i> словами
длиной <i class="formula">n</i> бит, при условии, чтобы вероятность незамеченной
ошибки была меньше&nbsp;<math>P_{miss}</math>.
 
\label{task:err}
Мы хотим передавать информацию блоками, которые содержали
бы <i class="formula">m</i> бит полезной информации, так, чтобы
вероятность ошибки в одном бите равнялась <i class="formula">p</i>, а
правильность передачи &laquo;фиксировалось контрольной суммой&raquo;. Найти
минимальный размер блока <math>n(m,p)</math> и коэффициент раздувания
\end{task}
\pb''Решение''
Для передачи <i class="formula">m</i> бит с вероятностью ошибки в отдельном бите
<i class="formula">p</i> требуется передать <math>m C(p)</math> бит
(см.&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> и
 
<i class="formula"></i>k(m,p)=C(p)+\frac{H((1-p)^m)}{m}.\pe<i class="formula"></i>
:<math>k(m,p)=C(p)+\frac{H((1-p)^m)}{m}.\pe</math>
 
Заметим, что <math>k(1,p)=1</math> — когда блок имеет размер один бит,
сообщение об ошибке в нём равносильно передаче самого бита.
 
Если передавать эти сообщения по каналу с уровнем помех <i class="formula">p</i>, то
количество бит на одно сообщение равно <math>m k(m,p)/C(p)</math>, то есть
теоретическая оценка для количества лишних бит равна
 
<i class="formula"></i>\frac{H((1-p)^m)}{C(p)}<i class="formula"></i>
:<math>\frac{H((1-p)^m)}{C(p)}</math>
 
Понятно, что данная теоретическая оценка занижена.
 
 
===Коды Хемминга===
 
Элементарный пример кода исправляющего ошибки был показан на
странице&nbsp;\pageref{simplecode}. Его обобщение очевидно. Для
3</math>. Оказывается это число можно сделать сколь угодно близким к
единице с помощью кодов Хемминга. В частности, при кодировании
<i class="formula">11</i> бит получается слово длинной <i class="formula">15</i> бит, то есть
<math>\mbox{КПС}KPS=\frac{11}{15}</math>.
 
Оценим минимальное количество контрольных
разрядов, необходимое для исправления одиночных ошибок. Пусть
содержательная часть составляет <i class="formula">m</i> бит, и мы добавляем ещё <i class="formula">r</i>
контрольных. Каждое из <math>2^m</math> правильных сообщений имеет <math>n=m+r</math>
его неправильных вариантов с ошибкой в одном бите. Такими
слов <math>2^n</math>, то
 
 
<i class="formula"></i>
:<math>
\begin{array}{c}
(n+1)2^m \leqslant 2^n\\ (m+r+1)\leqslant 2^r.
\end{array}
</math>
<i class="formula"></i>
 
 
Этот теоретический предел достижим при использовании
метода, предложенного Хеммингом. Идея его в следующем: все
биты, номера которых есть степень <i class="formula">2</i>, — контрольные,
остальные — биты сообщения. Каждый контрольный бит
отвечает за чётность суммы некоторой группы бит. Один и тот
же бит может относиться к разным группам. Чтобы определить
какие контрольные биты контролируют бит в позиции <i class="formula">k</i> надо
разложить <i class="formula">k</i> по степеням двойки: если <math>k=11=8+2+1</math>, то этот
бит относится к трём группам — к группе, чья чётность
подсчитывается в 1-ом бите, к группе 2-ого и к группе 8-ого
 
:<math>
 
\label{eq:hem}
\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> <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 class="formula">n</i> однозначно определяет <i class="formula">m</i>).
 
Пример для <math>Hem(15,11)</math>:
 
<i class="formula"></i>\begin{array}{c}
:<math>\begin{array}{c}
\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}
\end{array}<i class="formula"></imath>
 
 
 
Получив слово,
получатель проверяет каждый контрольный бит на предмет
правильности чётности и складывая номера контрольных бит, в
которых нарушена чётность. Полученное число, есть <mathi>XOR</mathi> номеров
бит, где произошла ошибка. Если ошибка одна, то это число есть
просто номер ошибочного бита.
 
Например, если в контрольных разрядах 1, 2, 8 обнаружено
несовпадение чётности, то ошибка в 11 разряде, так как
только он связан одновременно с этими тремя контрольными
 
\begin{task}
Покажите, что <math>\mbox{КПС}_KPS_{Hem(n,m)}\to 1</math> при <math>n\to
\infty</math>.
\end{task}
Код Хемминга может исправлять только единичные ошибки. Однако,
есть приём, который позволяет распространить этот код на случай
групповых ошибок. Пусть нам надо передать <i class="formula">k</i> кодослов.
Расположим их в виде матрицы одно слово — строка. Обычно,
передают слово за словом. Но мы поступим иначе, передадим слово
длины <i class="formula">k</i>, из 1-ых разрядов всех слов, затем — вторых и т.д. По
приёме всех слов матрица восстанавливается. Если мы хотим
обнаруживать групповые ошибки размера <i class="formula">k</i>, то в каждой строке
восстановленной матрицы будет не более одной ошибки. А с
одиночными ошибками код Хемминга справиться.
 
===Анализ эффективности===
 
Начнём c небольшого примера. Пусть у нас есть канал с уровнем
ошибок <math>p=10^{-6}</math>. Если мы хотим исправлять единичные ошибки при
передаче блоками по <math>1023=2^{10}-1</math> бит, то среди них потребуется
<i class="formula">10</i> контрольных бит: <i class="formula">1</i>, <i class="formula">2</i>, \dots, <math>2^9</math>. На один блок
приходится <i class="formula">1013</i> бит полезной информации. При передаче <i class="formula">1000</i>
таких блоков потребуется <math>\Delta=10\,000</math> контрольных бит.
 
В тоже время для обнаружения единичной ошибки достаточно одного
бита чётности. И если мы применим технику повторной передачи, то
на передачу <i class="formula">1000</i> блоков надо будет потратить <i class="formula">1000</i> бит
дополнительно и примерно <math>0.001\approx
p_{1014}=1-(1-10^{-6})^{1014}</math> из них придется пересылать
повторно. То есть на <i class="formula">1000</i> блоков приходится один попорченый, и
дополнительная нагрузка линии составляет <math>\Delta\approx
1000+1001</math>, что меньше <math>10\,000</math>. Но это не значит, что код
 
Рассмотрим этот вопрос подробнее. Пусть нам нужно передать
информацию <i class="formula">M</i> бит. Разобьем её на <i class="formula">L</i> блоков по <math>m=M/L</math> бит
и будем передавать двумя способами
— с помощью кодов Хемминга и без них. При этом будем
блоками по <math>m'</math> бит с повторной пересылкой в случае
обнаружения ошибки, то получим, что в среднем нам придётся
переслать <i class="formula">D</i> бит:
 
<i class="formula"></i>D=L m'{1 \over 1-P_{r}}<i class="formula"></i>
:<math>D=L m'{1 \over 1-P_{r}}</math>
 
Где <math>P_{r}=(1-(1-p)^{m'})(1-\varepsilon)</math> — вероятность
повторной передачи равная вероятности ошибки умноженной на
вероятность того, что мы её заметим. Коэффициент раздувания
равен
 
<i class="formula"></i>k(m,p,\varepsilon)=\frac{D}{M}=\frac{k_{\varepsilon}(m)}{\varepsilon+(1-\varepsilon)(1-p)^{k_{\varepsilon}(m)m}}<i class="formula"></i>
:<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 class="formula">n</i> бит:
 
:<math>
 
\label{eq:hnm}
\begin{array}{c}
2^n=2^{m'}(n+1),\mbox{ то есть}\\
k_{\varepsilon}(m)m= n-\log_2(n+1)
\end{array}
</math> <b>(eq:hnm)</b>
 
 
Для отдельного блока вероятность
безошибочной передачи равна <math>{P_0=(1-p)^n}</math>. Вероятность
одинарной ошибки <math>{P_1=n p^1(1-p)^{n-1}}</math>. Вероятность того,
что произошло более чем одна ошибка, и мы это заметили
 
<i class="formula"></i>P_{r}={(1-P_0-P_1)}{(1-\varepsilon)}={1-\varepsilon-(1-\varepsilon)(1-p)^{n-1}(np+1-p)}<i class="formula"></i>
:<math>P_{r}={(1-P_0-P_1)}{(1-\varepsilon)}={1-\varepsilon-(1-\varepsilon)(1-p)^{n-1}(np+1-p)}</math>
 
— в этом случае требуется повторная передача кадра.
Количество передаваемых данных:
 
<i class="formula"></i>D_{H}=L n{1 \over 1-P_{r}}={L n \over \varepsilon+(1-\varepsilon)(1-p)^{n-1}(np+1-p)}<i class="formula"></i>
:<math>D_{H}=L n{1 \over 1-P_{r}}={L n \over \varepsilon+(1-\varepsilon)(1-p)^{n-1}(np+1-p)}</math>
И коэффициент раздувания <i class="formula"></i>k_H(m,p,\varepsilon)={ n
 
\over m\bigl(\varepsilon+(1-\varepsilon)(1-p)^{n-1}(np+1-p)\bigr)},<i class="formula"></i>
И коэффициент раздувания
:<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> неявно определённая с помощью (\ref{eq:hnm})
функция. Удобно записать соответствующие коэффициенты
 
:<math>
 
\label{eq:kps}
\begin{array}{l}
\mbox{КПС}KPS= \mbox{КПС}_KPS_{\varepsilon}\bigl(n\bigr)\bigl(\varepsilon+(1-\varepsilon)(1-p)^n\bigr)\\
\\[0.8mm]
\mbox{КПС}_HKPS_H={\mbox{КПС}_KPS_{\varepsilon}\bigl(m'\bigr)\frac{m'}{n}\bigl(\varepsilon+(1-p)^{n-1}(np+1-p)(1-\varepsilon)\bigr)},
\\[0.5mm] \mbox{ где }m'=n-\log_2{(n+1) \end{array}.
</math> <b>(eq:kps)</b>
\end{array}
 
</math>
 
 
Легко обнаружить что при <math>n>3444</math> и <math>p=10^{-6}</math> код Хемминга
оказывается эффективнее, то есть <math>\mbox{КПС}_HKPS_H/\mbox{КПС}KPS>1</math>
 
\begin{center}
\begin{figure}[h!]
\psfrag{knc}{кпс} \psfrag{n}{<i class="formula">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>\mbox{КПС}KPS(n,p,\varepsilon)</math> — Коэффициент полезного содержания
в канале с помехами как функция размера элементарного блока.}
\parbox{0.85\textwidth}{\small Светлый график — ''без кодирования Хемминга'';\\
\begin{center}
\begin{figure}[h!]
\psfrag{C}{<i class="formula">C</i>} \psfrag{p}{<i class="formula">p</i>}
\centering\includegraphics[clip=true,
width=0.75\textwidth]{pictures/kpseff.eps}
\end{center}
 
Значение <math>\mbox{КПС}_KPS_{\varepsilon}(n)</math> используемое в
формулах (\ref{eq:kps}) можно оценить как
 
 
<i class="formula"></i>\mbox{КПС}_{\varepsilon}(n)={\log_2{\left(1-\varepsilon(2^n-1)\right)} \over n}<i class="formula"></i>
:<math>KPS_{\varepsilon}(n)={\log_2{\left(1-\varepsilon(2^n-1)\right)} \over n}</math>
 
 
Напомним, что <math>\varepsilon</math> есть параметр желаемой
ошибочной передачи блока при условии, что &laquo;контрольная сумма
сошлась&raquo; и кадр засчитан правильно переданным.
Такое выражение для <math>\mbox{КПС}_KPS_{\varepsilon}(p,n)=\frac{m}{n}</math>
получается из формулы
 
 
<i class="formula"></i>\varepsilon=\frac{2^m-1}{2^n-1}<i class="formula"></i>
:<math>\varepsilon=\frac{2^m-1}{2^n-1}</math>
 
 
Но это безусловно лишь оценочная формула. Оптимальное
значение <math>\mbox{КПС}_KPS_{\varepsilon}</math> значительно сложнее и
зависит от <i class="formula">p</i>.
 
Из графика на рисунке&nbsp;\ref{fig:kps} хорошо видно, что при
больших <i class="formula">n</i> код Хемминга начинает работать на пользу.
 
Но зависимость КПС от <i class="formula">n</i> не есть критерий эффективности
кода. Эффективность кода определяется функцией
 
<i class="formula"></i>C(p,\varepsilon)=\min_{n}{\mbox{KПС}(p,n,\varepsilon)}<i class="formula"></i>
:<math>C(p,\varepsilon)=\min_{n}{KPS(p,n,\varepsilon)}</math>
 
 
На рисунке&nbsp;\ref{fig:kpseff} показан график этой функции и из
него ясно, что код Хемминга можно использовать с пользой
всегда — при любых <math>\varepsilon</math> и <i class="formula">p</i>, если у нас есть
возможность выбирать подходящее <i class="formula">n</i>.
 
===Коды как линейные операторы===
 
То, что на множестве {0,1} есть структура числового поля,
позволяет осуществлять алгебраические интерпретации кодирования.
(слова мы будем воспринимать как столбцы).
 
 
<i class="formula"></i>
:<math>
\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
\end{array}<i class="formula"></imath>
 
 
Процесс выявления ошибок тоже линейная операция, она
<math>\mathbf{s}=\overline{s_1s_2s_3}=\mathbf{H}\mathbf{w'}_{out}</math> в
случае правильной передачи должно быть равно 000. Значение
<math>\mathbf{s}</math> называется ''синдромом ошибки''. <i class="formula">i</i>-ый разряд
слова <math>\mathbf{s}</math> контролирует <i class="formula">i</i>-ое соотношение в
(\ref{eq:hem}) и, таким образом, <math>\mathbf{s}</math> равно сумме номеров
бит в которых произошла ошибка, как векторов в <math>G\mathbb{F}(2)^3</math>.
 
 
<i class="formula"></i>\mathbf{H}_{Hem(7,4)}=\begin{array}{||ccccccc||}
:<math>\mathbf{H}_{Hem(7,4)}=\begin{array}{||ccccccc||}
1&0&1&0&1&0&1\\ 0&1&1&0&0&1&1\\0&0&0&1&1&1&1
\end{array}<i class="formula"></imath>
 
Заметим, что столбцы проверочной матрицы представляют собой
последовательно записанные в двоичной форме натуральные
Вычиcление рабочей матрицы для циклических кодов
основывается на значениях <math>G_n(x)=x^n\; mod\; G(x)</math>. Верхняя
её часть равна единичной, так <i class="formula">m</i> бит сообщения помещаются
без изменения в начало слова, а нижние <i class="formula">r</i> строчек есть <i class="formula">m</i>
столбцов высоты <i class="formula">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> и
 
<i class="formula"></i>
:<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}
</math>
<i class="formula"></i>
 
Рабочая и проверочная матрицы равны
 
<i class="formula"></i>\mathbf{A}=\left\|\begin{array}{c} E_4\\G_6
:<math>\mathbf{A}=\left\|\begin{array}{c} E_4\\G_6
G_5 G_4 G_3
\end{array}\right\| , \mbox{ и }quad \mathbf{H}=\|G_6G_5G_4G_3E_3\|,<i class="formula"></imath> то есть
то есть
<i class="formula"></i>
 
:<math>
\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>
<i class="formula"></i>
 
 
Кроме рабочей и проверочной матриц есть ещё множество ''порождающих матриц <math>\mathbf{G}</math>'' и ''декодирующих матриц
порождающей. В частности, рабочая матрица является порождающей.
Способность обнаруживать и исправлять ошибки однозначно
определяется подпространством <i class="formula">L</i>. Порождающих, рабочих и
проверочных матриц соответствующих <i class="formula">L</i> несколько.
 
Действительно, в порождающей и рабочей матрицах можно осуществлять
всегда удовлетворяют отношениям
 
 
<i class="formula"></i>\mathbf{H}\cdot \mathbf{A}=\mathbf{0}_{rm},\;
:<math>\mathbf{H}\cdot \mathbf{GA}=\mathbf{0}_{rm},<i class="formula"></i> где\;
\mathbf{H}\cdot \mathbf{G}=\mathbf{0}_{rm},</math>
где
<math>\mathbf{0}_{rm}</math> — нулевая матрица <math>r\times m</math>.\\ Любая
порождающая матрица может использоваться как
матриц определяется рабочей матрицей:
 
 
<i class="formula"></i>\mathbf{D}\cdot \mathbf{A}=\mathbf{E}_m,<i class="formula"></i>
:<math>\mathbf{D}\cdot \mathbf{A}=\mathbf{E}_m,</math>
 
где <math>\mathbf{E}_m</math> — единичная матрица <math>m\times m</math>. На
подпространстве <i class="formula">L</i> все декодирующие матрицы действуют одинаково.
Они отличаются на подпространстве ортогональном <i class="formula">L</i>. Приведём
декодирующую матрицу для <math>Hem(7,4)</math> и <math>CRC_{n=7,\;m=7}</math>:
 
<i class="formula"></i>
:<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>
<i class="formula"></i>
 
К каждой строчке декодирующей матрицы можно добавить любую
линейную комбинацию строчек из проверочной матрицы. Следует
Сформулируем теперь основные моменты, касающиеся линейных кодов.
 
# Процесс кодирования и декодирования — линейные операторы. :<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 class="formula"></i>\mathbf{w}_{out}=\mathbf{A}\mathbf{w}_{in},\; \; \mbox{канал}:\mathbf{w}_{out}\mapsto \mathbf{w}'_{out},\;\; \mathbf{w}'_{in}=\mathbf{D}\mathbf{w}'_{out}<i class="formula"></i>
# В случае, когда векторы подпространства <i>L</i> достаточно удалены друг от друга в смысле метрики Хемминга, есть возможность обнаруживать и исправлять некоторые ошибки. В частности, значение синдрома ошибки в случае кода Хемминга равно векторной сумме номеров бит, где произошла ошибка.
# Обнаружение ошибок равносильно проверке принадлежности
# Комбинация (композиция) линейных кодов есть снова линейный код.
полученного слова подпространству <i class="formula">L</i> допустимых слов. Для этого
необходимо найти проекцию <math>\mathbf{s}</math> (синдром ошибки)
полученного слова на <math>L^{\perp}</math> — тоже линейная операция. Для
правильно переданного слова&nbsp;<math>\mathbf{s}=\mathbf{0}</math>.
<i class="formula"></i>\mathbf{s}=\mathbf{H}\mathbf{w}'_{out}<i class="formula"></i>
# В случае, когда векторы подпространства <i class="formula">L</i> достаточно удалены друг от друга
в смысле метрики Хемминга, есть возможность обнаруживать и
исправлять некоторые ошибки. В частности, значение синдрома ошибки
в случае кода Хемминга равно векторной сумме номеров бит, где
произошла ошибка.
# Комбинация (композиция) линейных кодов есть снова
линейный код.
 
 
Практические методы помехоустойчивого кодирования все основаны на
линейных кодах. В основном это модифицированные <mathi>CRC</mathi>, коды
Хемминга и их композиции. Например <math>Hem(7,4)</math> плюс проверка на
чётность. Такой код может исправлять уже две ошибки. Построение
Для данной проверочной матрицы постройте рабочую и декодирующую
матрицу. Докажите, что кодовое расстояние равно 4.
 
<i class="formula"></i>\mathbf{H}=\begin{array}{||cccccccc||}
:<math>\mathbf{H}=\begin{array}{||cccccccc||}
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{array}<i class="formula"></imath>
 
''Подсказка ''\\
1) Это проверочная матрица <math>Hem(7,4)</math> плюс условие на чётность
кода с <math>G(x)=x^{3}+x+1</math> и <math>m=4</math> при условии, что в качестве
рабочей матрицы использовалась матрица
 
<i class="formula"></i>\mathbf{A}=
:<math>\mathbf{A}=
\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{array}.<i class="formula"></imath>
 
 
\end{task}
 
===*Коды Рида-Соломона===
 
После перехода на язык линейной алгебры естественно возникает
желание изучить свойства линейных кодов над другими конечными
Рида-Соломона.
 
{{info|\slshape Коды Рида-Соломона являются циклическими кодами над числовым полем отличным от <math>G\mathbb{F}(2)</math>.}}
числовым полем отличным от <math>G\mathbb{F}(2)</math>.}
 
Напомним, что существует бесконечное количество конечных полей, и
таким числом элементов, которое обозначается как
<math>G\mathbb{F}(n)</math>. Простейшая реализация этого поля — множество
многочленов по модулю неприводимого{{ref|note3}} многочлена <math>p(x)</math> степени <i class="formula">k</i> над
полем <math>\mathbb{F}_{q}</math> вычетов по модулю&nbsp;<i class="formula">q</i>. В случае
многочленов с действительными коэффициентами неприводимыми
многочленами являются только квадратные многочлены с
 
==Примеры протоколов канала данных==
===<i>HDLC</i> протокол===
 
===<math>HDLC</math> протокол===
Здесь мы познакомимся с группой протоколов давно известных, но
по-прежнему широко используемых. Все они имеют одного
предшественника – <mathi>SDLC</mathi> (Synchronous Data Link Control) –
протокол управления синхронным каналом, предложенным фирмой <mathi>IBM</mathi>
в рамках <mathi>SNA</mathi>. <mathi>ISO</mathi> модифицировала этот протокол и выпустила
под названием <mathi>HDLC</mathi> — High level Data Link Control. <mathi>MKTT</mathi>
модифицировала <mathi>HDLC</mathi> для X.25 и выпустила под именем <mathi>LAP</mathi> –
Link Access Procedure. Позднее он был модифицирован в <mathi>LAPB</mathi>.
 
Все эти протоколы построены на одних и тех же принципах. Все
 
 
* Поле <mathi>Control</mathi> используется для последовательных номеров кадров, подтверждений и других нужд.
* Поле <i>Data</i> может быть сколь угодно большим и используется для передачи данных. Надо только иметь ввиду, что чем оно длиннее тем, больше вероятность повреждения кадра на линии.
кадров, подтверждений и других нужд.
* Поле <i>Checksum</i> — это поле используется <i>CRC</i> кодом.
* Поле <math>Data</math> может быть сколь угодно большим и используется
для передачи данных. Надо только иметь ввиду, что чем оно
длиннее тем, больше вероятность повреждения кадра на линии.
* Поле <math>Checksum</math> — это поле используется <math>CRC</math> кодом.
 
Флаговые последовательности <i class="formula">01111110</i> используются для
разделения кадров и постоянно передаются по незанятой линии
в ожидании кадра. Существуют три вида кадров: <math>Information</math>,
<math>Supervisory</math>, <mathi>Unnumbered</mathi>.
 
Организация поля <mathi>Control</mathi> для этих трех видов кадров показана на
рис.&nbsp;\ref{fig:cfield}. Как видно из размера поля <mathi>Seq</mathi> в окне
отправителя может быть до <i class="formula">7</i> неподтверждённых кадров. Поле
<mathi>Next</mathi> используется для посылки подтверждения вместе с
передаваемым кадром. Подтверждение может быть в форме номера
последнего правильно переданного кадра, а может быть в форме
первого не переданного кадра. Какой вариант будет использован —
это параметр.
 
\begin{center}
\begin{figure}[h!]
\centering\includegraphics[clip=true,
width=0.88\textwidth]{pictures/cfield.eps} \caption{Cтруктура поля <math>Control</math>}
<i>Control</i>}
\parbox{0.66\textwidth}{\small (а) Информационный кадр (<math>Information</math>)\\
(б) Управляющий кадр (<math>Supervisory</math>)\\(в) Ненумерованный
кадр (<mathi>Unnumbered</mathi>) }
\label{fig:cfield}
\end{figure}
Разряд <math>P/F</math> использует при работе с группой терминалов.
Когда компьютер приглашает терминал к передаче он
устанавливает этот разряд в <i class="formula">P</i>. Все кадры, посылаемые
терминалами имеют здесь <i class="formula">P</i>. Если это последний кадр,
посылаемый терминалом, то здесь стоит <i class="formula">F</i>.
 
<math>Supervisory</math> кадры имеют четыре типа кадров.
 
 
* Тип 0 — уведомление в ожидании следующего кадра (RECEIVE READY). Используется когда нет встречного трафика, чтобы передать уведомление в кадре с данными.
* Тип 1 — негативное уведомление (REJECT) — указывает на ошибку при передаче. Поле <i>Next</i> указывает номер кадра, начиная с которого надо перепослать кадры.
READY). Используется когда нет встречного трафика, чтобы
* Тип 2 — RECEIVE NOT READY. Подтверждает все кадры, кроме указанного в Next. Используется, чтобы сообщить источнику кадров об необходимости приостановить передачу в силу каких-то проблем у получателя. После устранения этих проблем получатель шлет RECEIVE REDAY, REJECT или другой надлежащий управляющий кадр.
передать уведомление в кадре с данными.
* Тип 3 — SELECTIVE REJECT — указывает на необходимость перепослать только кадр, указанный в Next. <i>LAPB</i> и <i>SDLC</i> не используют этого типа кадров.
* Тип 1 — негативное уведомление (REJECT) — указывает
на ошибку при передаче. Поле <math>Next</math> указывает номер кадра,
начиная с которого надо перепослать кадры.
* Тип 2 — RECEIVE NOT READY. Подтверждает все кадры,
кроме указанного в Next. Используется, чтобы сообщить
источнику кадров об необходимости приостановить передачу в силу каких-то проблем
у получателя. После устранения этих проблем получатель шлет RECEIVE REDAY, REJECT или другой надлежащий управляющий кадр.
* Тип 3 — SELECTIVE REJECT — указывает на необходимость
перепослать только кадр, указанный в Next. <math>LAPB</math> и <math>SDLC</math>
не используют этого типа кадров.
 
Третий класс кадров — <i>Unnubered</i>. Кадры этого класса иногда
 
Третий класс кадров — <math>Unnubered</math>. Кадры этого класса иногда
используются для целей управления, но чаще для передачи данных
при ненадёжной передаче без соединения.
повреждение управляющего кадра.
 
# {{note|note1}} Идея рассмотрения информации как меры на множестве ещё не до конца исчерпала себя — такой меры ещё не построено. Однако доказано, что с помощью этой аналогии можно доказывать неравенства, например <math>{I(\{\xi_{in}\,\xi_{out}\})\geqslant 0}</math>.
 
# {{note|note2}} Матрица называется ''стохастической'', если все её элементы неотрицательны и сумма элементов в каждом столбце равна единице.
# {{note|note1}} Идея рассмотрения информации как меры на множестве
# {{note|note3}} Многочлен называется ''неприводимым'', если он не разлагается в произведение многочленов меньшей степени.
ещё не до конца исчерпала себя
— такой меры ещё не построено. Однако доказано, что с помощью
этой аналогии можно доказывать неравенства, например
<math>{I(\{\xi_{in}\,\xi_{out}\})\geqslant 0}</math>.
# {{note|note2}} Матрица называется
''стохастической'', если все её элементы неотрицательны и
сумма элементов в каждом столбце равна единице.
# {{note|note3}} Многочлен называется
''неприводимым'', если он не разлагается в произведение
многочленов меньшей степени.
481

правка