Обнаружение ошибок
Решив проблему разбиения на кадры, мы приходим к следующей проблеме: как обеспечить, чтобы кадры попадали на сетевой уровень по назначению и в надлежащей последовательности? Если для отправляющей стороны все равно в какой последовательности поступают кадры, то этой проблемы нет. Например, если нам нужен сервис без уведомления и соединения, но если нам нужен сервис с подтверждением и с соединением, то как быть?
Для решения этой проблемы устанавливают обратную связь между отправителем и получателем в виде кадра подтверждения. Если кадр-подтверждение несет положительную информацию, то считается что переданные кадры прошли нормально, если там сообщение об ошибке, то переданные кадры надо передать заново.
Однако, возможны случаи когда из-за ошибок в канале кадр исчезнет целиком. В этом случае получатель не будет реагировать ни как, а отправитель будет сколь угодно долго ждать подтверждения. Для решения этой проблемы на канальном уровне вводят таймеры. Когда передается очередной кадр, то одновременно устанавливается таймер на определенное время. Этого времени должно хватать на то, чтобы получатель получил кадр, а отправитель получил подтверждение. Если отправитель не получит подтверждение раньше, чем истечет время, установленное на таймере, то он будет считать, что кадр потерян и повторит его еще раз.
Однако, если кадр-подтверждение был утерян, то вполне возможно, что один и тот же кадр получатель получит дважды. Как быть? Для решения этой проблемы каждому кадру присваивают порядковый номер. С помощью этого номера получатель может обнаружить дубли.
Итак, таймеры и нумерация кадров - вот основные средства на канальном уровне, обеспечивающие доставку каждого кадра до сетевого уровня в единственном экземпляре.
Управление потоком
Другой важной проблемой, которая решается на канальном уровне - управление потоком. Дело в том, что вполне может случиться, что отправитель будет слать кадры столь часто, что получатель не будет успевать их обрабатывать. Это может случиться если, например, машина-отправитель более мощная или загружена слабее, чем машина-получатель.
Для борьбы с такими ситуациями вводят управления потоком. Это управление предполагает обратную связь между отправителем и получателем, которая позволяет им урегулировать такие ситуации. Есть много схем управления потоком, но все они в основе своей используют следующий сценарий. Прежде чем отправитель начнет передачу он спрашивает у получателя сколько кадров тот может принять. Получатель сообщает ему определенное число кадров. Отправитель после того как передаст это число кадров, должен приостановить передачу и спросить получателя опять получателя опять как много кадров тот может принять и т.д. Позднее на конкретных примерах мы познакомимся с конкретными механизмами управления потоком.
Обнаружение и исправление ошибок
В рассмотрении физической среды мы отмечали, что у беспроводных систем связи, аналоговых каналов, например, петля в телефонных системах, достаточно высокий уровень ошибок в канале. Поэтому ошибки при передаче- это реальность, которую надо обязательно учитывать.
В разных средах характер ошибок разный. Ошибки могут быть одиночные, а могут возникать группами, сразу по несколько. У групповых ошибок есть свои достоинства и недостатки. Достоинство заключается в следующем. Пусть данные передаются блоками по 1000 бит, а уровень ошибки 0,001 на бит. Если ошибки изолированные и независимые, то практически каждый блок будет содержать ошибку в среднем. Если же они
возникают группами по 100 сразу, то ошибки будут содержать 1-2 блока из каждых 100 в среднем. Недостатком групповых ошибок является то, что их труднее обнаруживать и исправлять, чем одиночные.
Коды с исправлением ошибок
Для надежной передачи кодов было предложено два основных метода. Первый - внести избыточность в форме дополнительных битов в передаваемый блок данных так, чтобы, анализируя полученный блок, можно было бы указать где возникли искажения. Это, так называемые, коды с исправлением ошибок. Второй - внести избыточность, но лишь настолько, чтобы, анализируя полученные данные, можно было сказать есть в переданном блоке ошибки или нет. Это, так называемые, коды с обнаружением ошибок.
Пусть данные занимают  разрядов и мы добавляем  разрядов как контрольные разряды. Нам надо передать слово длины  , которое называют n-битовым кодословом. Пусть у нас есть два кодослова 10001001 и 10110001. С помощью операции EXCLUSIVE OR легко определить число различных разрядов. В данном случае их 3. Количество разных битов в двух кодословах называется расстоянием Хемминга. Поэтому если два кодослова находятся на расстоянии  по Хеммингу, это значит, что надо преобразовать ровно разрядов, чтобы преобразовать одно кодослово в другое.
В силу избыточности не все  комбинаций возможны. Зная алгоритм установки контрольных разрядов, мы можем вычислить минимальное расстояние по Хеммингу между допустимыми кодословами. Способен код исправлять ошибки или только обнаруживать зависит от расстояния между его кодословами по Хеммингу. Если мы хоти обнаруживать ошибок, то надо чтобы кодослова отстояли друг от друга на расстояние  . Тогда если принятый код отстоит на расстояние  , то принятое кодослово содержит k ошибок. Если мы хотим исправлять ошибки, то надо чтобы кодослова отстояли друг от друга на  . Поэтому даже если переданное кодослово содержит ошибок, оно все равно ближе к правильному кодослову, чем к какому-либо еще, и следовательно можно определить, исходное слово.
Простым примеров кода с обнаружением одной ошибки является код с битом четности. Конструкция его такова: к исходному кодослову добавляется бит четности. Если число 1 в исходном кодослове четно, то значение этого бита 0. Если нечетно, то 0. Кодослова с битом четности имеют расстояние хемминга 2.
Для примера кода с исправлением ошибки рассмотрим код, у которого есть только четыре правильных кодослова: 0000000000, 0000011111, 11111100000, 11111111111. Расстояние по хеммингу у этого кода 5, следовательно он может исправлять двойные ошибки. Если получатель получит слово 0000000111, то ясно, что исходное слово имело вид 0000011111.
Оценим минимальное количество контрольных разрядов, необходимое для исправления одиночных ошибок. Пусть у нас есть код из бит сообщения и контрольных бит. Каждое из  правильных кодослов имеет  неправильных кодослов на расстоянии 1. Такими образом, с каждым из кодослов связано  кодослов. Так как общее число кодослов , то
 , учитывая что получаем 
Этот теоретический предел достижим при использовании метода, предложенного Хеммингом. Идея его в следующем: все биты, номера которых есть степень 2 (1,2,4,8,16 и т.д.) - контрольные, остальные - биты сообщения. Каждый контрольный бит отвечает за четность группы битов, включая себя. Один и тот же бит может относиться к разным группам. Значение бита сообщения определяется по значениям контрольных битов. Чтобы определить какие контрольные биты контролируют бит в позиции k надо представить значение k по степеням двойки. Например,  , а  .
Получив кодослово, получатель устанавливает специальный счетчик в ноль. Затем он проверят каждый контрольный бит на предмет правильности четности. Если четность нарушена, то порядковый номер этого бита заноситься в счетчик. Если после этой проверки счетчик ноль, то все в порядке. Если нет, то он содержит номер неправильного разряда. Например, 1, 2, 8 - ошибочные контрольные разряды, то ошибка в 11 разряде, так как только он связан одновременно с этими контрольными разрядами.
Код хемминга может исправлять только единичные ошибки. Однако, есть прием, который позволяет распространить идеи Хемминга на случай групповых ошибок. Пусть нам надо передать k кодослов. Расположим их в виде матрицы одно слово - строка. Обычно, передают слово за словом. Но мы поступим иначе, передадим слово длины  , из 1-ых разрядов всех слов, затем - вторых и т.д. По приеме всех слов матрица восстанавливается. Если мы хотим обнаруживать групповые ошибки размера , то в каждой строке восстановленной матрицы будет не более одной ошибки. А с одиночными ошибками код хемминга справиться.
Коды обнаруживающие ошибки
Начнем а небольшого примера. Пусть у нас есть канал с единичными ошибкой с частотой 10-6 на бит. Если мы хотим исправлять единичные ошибки при передаче блока в 1000 бит, то нам потребуется 10 контрольных бит. При передаче 1 Мбит данных, потребуется 10 000 контрольных бит. В тоже время для обнаружения единичной ошибки достаточно одного бита четности. Поэтому, если мы применим технику повторной передачи, то на передачу 1000 блоков надо будет потратить 1001 бит дополнительно или с повторной передачей 2002 бит, вместо 10,000 бит в случае кода с исправлением ошибки.
Применение техники четности "в лоб" в случае групповых ошибок не даст нужного результата. Однако, ее можно скорректировать. Пусть нам надо передать слов по бит. Расположим их в виде матрицы  . Для каждого столбца вычислим бит четности и разместим его в дополнительной строке. Матрица затем передается по строкам. По получению матрица восстанавливается и если хоть один бит нарушен, то весь блок передается повторно.
Этот метод позволяет обнаружить групповые ошибки длины . Против групповых ошибок длины  он бессилен. В общем случае вероятность правильной передачи при длине групповой ошибке , равна  .
Поэтому на практике применяют другую технику, которая называется полиномиальными кодами или циклическим избыточным кодом (Cyclic Redundancy Code) или CRC кодом.
CRC коды построены на рассмотрении битовой строки как строки коэффициентов полинома. битовая строка - коэффициенты полинома степени  . Самый левый бит строки - коэффициент при старшей степени. Например, строка 110001 представляет полином .
Полиномиальная арифметика выполняется по модулю 2. Сложение и вычитание происходит без переноса разрядов. Так, что обе это операции эквивалентны EXCLUSIVE OR. Например,
   
Деление выполняется как обычно в двоичной системе с той лишь разницей, что вычитание выполняется по модулю два.
Использование полиномиальных кодов при передаче заключается в следующем. Отправитель и получатель заранее договариваются о конкретном генераторе полиномов  , у него коэффициенты при старшем члене и при младшем члене должны быть равны 1. Пусть степень равна r. Для вычисления контрольной суммы блока из m бит надо чтобы обязательно  . Идея состоит в том, чтобы добавить контрольную сумму к передаваемому блоку, рассматриваемому как полином  так, чтобы передаваемый блок с контрольной суммой был кратен . Когда получатель получает блок с контрольной суммой, он делит его на . Если есть остаток, то были ошибки при передаче.
Алгоритм вычисления контрольной суммы:
Добавить нулей в конец блока так, что он теперь содержит m+r разрядов и соответствует полиному  ;
Разделить по модулю 2 полином на ;
Вычесть остаток ( длина которого всегда не более r разрядов) из строки, соответствующей , по модулю 2. Результат и есть блок с контрольной суммой ( назовем его  ).
Этот метод позволяет отлавливать одиночные ошибки. Групповые ошибки длины не более . Нечетное число отдельных ошибок.
Существует три международных стандарта на вид :
 .
CRC-12 используется для передачи символов из 6 разрядов. Два остальных - для 8 разрядных. CRC-16 и CRC-CCITT ловят одиночные, двойные ошибки, групповые ошибки длины не более 16 и нечетное число изолированных ошибок с вероятностью 99,997%.
|
