Лекции 2010-го года (1130544), страница 35
Текст из файла (страница 35)
Этотметод прозрачен для сетевого уровня так же, как и метод вставки байтов.Рисунок 3-5. Замена шестой единицы нулемТаким образом, кадр легко может быть распознан по флаг-байту. Если граница очередногокадра по какой-то причине была потеряна, то все что надо делать – «ловить» ближайшийфлаг-байт.Последний метод - нарушение кодировки используется там, где применяется специальнаякодировка битов на физическом уровне. Например, пусть для передачи одного битаиспользуется два импульса. «1» кодируется как переход «высокое-низкое», «0» - какпереход «низкое-высокое».
Сочетания «низкое-низкое» или «высокое-высокое» неиспользуются для передачи данных. Их и используют для границ кадра. Так делают встандарте IEEE 802 для ЛВС, который мы рассмотрим позже.На практике используют, как правило, комбинацию этих методов. Например, счетчиксимволов с одним из выше перечисленных. Тогда, если число символов в кадре совпадаетс кодировкой границы кадра, кадр считается переданным правильно.3.1.3.
Обнаружение ошибокРешив проблему разбиения на кадры, мы приходим к следующей проблеме: какобеспечить, чтобы кадры попадали на сетевой уровень в надлежащейпоследовательности? Если для отправляющей стороны все равно, в какойпоследовательности поступают кадры, то этой проблемы нет. Например, если нам нуженсервис без уведомления и без соединения. Однако как быть, если нам нужен сервис суведомлением и с соединением?7Для решения этой проблемы устанавливают обратную связь между отправителем иполучателем в виде кадра подтверждения.
Если кадр-подтверждение несетположительную информацию, то считается, что переданные кадры прошли нормально,если же в нем сообщение об ошибке, то переданные кадры надо передать заново.Однако возможны ситуации, когда из-за ошибок в канале кадр исчезнет целиком. В этомслучае получатель не будет никак реагировать, а отправитель будет сколь угодно долгождать подтверждения. Для решения этой проблемы на канальном уровне вводят таймеры.Когда передается очередной кадр, то одновременно устанавливается таймер наопределенное время.
Этого времени должно хватать на то, чтобы получатель получилкадр и отправил уведомление, а отправитель получил его.Если отправитель не получит уведомление раньше, чем истечет время, установленное натаймере, то он будет считать, что кадр потерян и повторит его еще раз.Однако если кадр-подтверждение был утерян, то вполне возможно, что один и тот же кадрполучатель получит дважды. Как быть? Для решения этой проблемы каждому кадруприсваивают порядковый номер. С помощью этого номера получатель может обнаружитьдубли.Итак, таймеры и нумерация кадров - основные средства на канальном уровне,обеспечивающие доставку каждого кадра до сетевого уровня в единственном экземпляреи в нужном порядке.3.1.4.
Управление потокомДругая важная проблема, которую надо решать на канальном уровне - управлениепотоком. Вполне может случиться, что отправитель будет посылать кадры столь часто,что получатель не будет успевать их обрабатывать. Это может произойти, если, например,машина-отправитель более мощная или загружена слабее, чем машина-получатель.Для борьбы с такими ситуациями вводят специальный механизм управления потоком.Этот механизм предполагает обратную связь между отправителем и получателем, котораяпозволяет им урегулировать темп передачи.Существует много схем управления потоком, но все они в основе своей используютследующий сценарий.
Прежде чем отправитель начнет передачу, он спрашивает уполучателя, сколько кадров тот может принять. Получатель сообщает ему определенноечисло. Отправитель, после того как передаст это число кадров, должен приостановитьпередачу и спросить у получателя еще раз, сколько кадров тот может принять, и т.д.Позднее на примерах мы познакомимся с конкретными механизмами управления потоком.Раздел 3.2. Обнаружение и исправление ошибокПри рассмотрении физической среды мы отмечали, что у беспроводных систем связи ианалоговых каналов, например, абонентской линии в телефонных сетях, достаточновысокий уровень ошибок в канале. Поэтому ошибки при передаче на физическом уровне это реальность, которую надо обязательно учитывать.В разных средах характер ошибок разный.
Ошибки могут быть одиночные, а могутвозникать группами, сразу по несколько штук. У групповых ошибок есть своидостоинства и недостатки. Достоинство заключается в следующем. Пусть данные8передаются блоками по 1000 бит, а частота ошибки - 10-3 на бит, т.е. одна на каждые 1000бит.Если ошибки изолированные и независимые, то практически каждый блок в среднембудет содержать ошибку. Если же они возникают группами по 100 сразу, то ошибки будутсодержать в среднем 1-2 блока из каждых 100. Недостатком групповых ошибок являетсято, что их труднее обнаруживать и исправлять, чем одиночные.3.2.1. Коды с исправлением ошибокДля надежной передачи кодов было предложено два основных метода.
Первый - внестиизбыточность в форме дополнительных битов в передаваемый блок данных так, чтобы,анализируя полученный блок, можно было бы указать, где возникли искажения. Это такназываемые коды с исправлением ошибок. Второй метод - внести избыточность, но лишьнастолько, чтобы, анализируя полученные данные, можно было сказать: есть впереданном блоке ошибки или нет. Это так называемые коды с обнаружением ошибок.Пусть данные занимают m разрядов, и мы добавляем r избыточных, контрольныхразрядов. Нам необходимо передать слово длины n = m+r, которое называют n-битовымкодословом.
Пусть у нас есть два кодослова - 10001001 и 10110001. С помощью операцииEXCLUSIVE OR легко определить число различных разрядов в двух кодословах. Вданном случае таких разрядов 3. Количество разных битов в двух кодословах называетсярасстоянием Хемминга между этими словами. Поэтому, если два кодослова находятся нарасстоянии d по Хеммингу, это значит, что надо преобразовать ровно d разрядов, чтобыпреобразовать одно кодослово в другое.В силу того, что избыточные контрольные разряды могут принимать только вполнеопределенные значения, то не все 2n кодовых слов возможны. Зная алгоритм установкиконтрольных разрядов, мы можем вычислить минимальное расстояние по Хеммингумежду двумя правильными кодословами.Способен код исправлять ошибки или только обнаруживать их - зависит от расстояниямежду кодословами по Хеммингу.
Если мы хотим обнаруживать d ошибок, тонеобходимо, чтобы два кодослова отстояли друг от друга на расстоянии d+1. Тогда, еслипринятый код отстоит на расстоянии k<d, то принятое кодослово содержит k ошибок.Если мы хотим исправлять d ошибок, то нужно, чтобы кодослова отстояли друг от другана 2d+1. Поэтому, даже если переданное кодослово содержит d ошибок, оно все равноближе к правильному кодослову, чем к какому-либо еще, и, таким образом, можноопределить исходное слово.Простым примером кода с обнаружением одной ошибки является код с битом четности.Конструкция его такова: к исходному кодослову добавляется бит четности.
Если числоединиц в исходном кодослове четно, то значение этого бита - 0. Если нечетно, то - 1.Кодослова с битом четности имеют расстояние Хемминга 2, так как любая ошибка водном бите породит ошибку четности. Однако, если возможны двойные ошибки, то битчетности проблему не решит.Для примера кода с исправлением ошибки рассмотрим код, у которого есть только четыреправильных кодослова: 0000000000, 0000011111, 1111100000, 1111111111. Расстояние поХеммингу у этого кода 5, следовательно, он может исправлять двойные ошибки.
Еслиполучатель получит слово 0000000111, то ясно, что исходное слово имело вид90000011111. Однако, если допустимы тройные ошибки, то 0000000111 может означать0000000000.Оценим минимальное количество контрольных разрядов, необходимое для исправленияодиночных ошибок. Пусть у нас есть код из m бит сообщения и r контрольных бит.Каждое из 2n правильных сообщений имеет n неправильных кодослов на расстоянии 1.Таким образом, с каждым из 2m кодослов связано n+1 кодослов. Так как общее числокодослов - 2n, то (n+1)2m≤2, учитывая, что n=m+r, получаем:(m+r+1) ≤ 2rДля заданного m эта формула задает минимальное число контрольных разрядов,необходимых для исправления единичных ошибок. Этот теоретический предел достижимпри использовании метода, предложенного Хеммингом. Идея его в следующем:• Разряды кодослова нумеруются слева направо, начиная с 1.• Все биты, номера которых являются степенью 2 (1, 2, 4, 8, 16 и т.д.) - контрольные,остальные - биты сообщения.• Каждый контрольный бит отвечает за четность группы битов, включая себя.
Чтобыопределить группу битов, за четность которой отвечает определенныйконтрольный бит, нужно представить номер позиции каждого бита по степенямдвойки. Те биты, в номера которых входит степень двойки, равная номеруконтрольного бита, и есть искомая группа. Например, 11=1+2+8, 39=1+2+4+32.Таким образом, бит в позиции 11 входит в группу, контролируемую битом впозиции 2.Получив кодослово, получатель устанавливает специальный счетчик в ноль.
Затем онпроверят каждый контрольный бит на предмет правильности четности. Если четностьнарушена, то порядковый номер этого бита заносится в счетчик. Если после этойпроверки счетчик на нуле, то все в порядке. Если нет, то он содержит номернеправильного разряда. Например, если 1, 2, 8 - ошибочные контрольные разряды, тоошибка содержится в 11-м разряде, так как только он связан одновременно с этимиконтрольными разрядами.На рисунке 3-6 показан 7-разрядный ASCII-код и соответствующий ему 11-разрядный кодХемминга.
В этом коде Хемминга разряды 1, 2, 4, 8 - контрольные. 3-й разряд в этом кодесоответствует 1-му разряду исходного кода, разряды 5, 6, 7, 9, 10, 11 - разрядам 2, 3, 4, 5,6, 7 соответственно. 1-й разряд в коде Хемминга контролирует группу, в которую входятразряды с номерами 3, 5, 7, 9, 11, что соответствует разрядам 1, 2, 4, 5, 7 в исходном коде.Так как число 1 в этих разрядах в исходном коде четно, то 1-й разряд в коде Хеммингаравен 0. Аналогично определяем значение остальных контрольных разрядов.Рисунок 3-6. Использование кода Хемминга для исправления ошибок передачи10Код Хемминга может исправлять только одиночные ошибки. Однако есть прием, которыйпозволяет распространить идеи Хемминга на случай групповых ошибок. Пусть нам надопередать k кодослов. Расположим их в виде матрицы: одно слово - строка.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
