Лекции 2010-го года (1130544), страница 36
Текст из файла (страница 36)
Обычнопередают слово за словом. Но мы поступим иначе, передадим слово длины k из первыхразрядов всех слов, затем - вторых, и т.д. После приема всех слов матрицавосстанавливается. Если мы хотим обнаруживать групповые ошибки размера k, то вкаждой строке восстановленной матрицы будет не более одной ошибки. А с одиночнымиошибками код Хемминга справится.3.2.2. Коды с обнаружением ошибокРассмотрение кодов, обнаруживающих ошибки, начнем с небольшого примера. Пусть унас есть канал с одиночными ошибками с частотой 10-6 на бит.
Если мы хотим исправлятьединичные ошибки при передаче блока в 1000 бит, то нам потребуется 10 контрольныхбит ((m+r+1) ≤ 2rr, где m =1000; (1001+r) ≤ 2rr, следовательно, r = 10).При передаче 1 Мбит данных потребуется 10 000 контрольных бит. В то же время дляобнаружения единичной ошибки достаточно одного бита четности. Поэтому, если мыприменим технику повторной передачи, то на передачу 1000 блоков надо будет потратить1001 бит дополнительно или с повторной передачей 2002 бит, вместо 10000 бит в случаекода с исправлением ошибки.Применение техники четности «в лоб» в случае групповых ошибок не даст нужногорезультата. Однако ее можно скорректировать. Пусть нам требуется передать n слов по kбит.
Расположим их в виде матрицы n х k. Для каждого столбца вычислим бит четности иразместим его в дополнительной строке. Матрица затем передается по строкам. Приполучении матрица восстанавливается, и если хоть один бит нарушен, то весь блокпередается повторно.Этот метод позволяет обнаружить групповые ошибки длины n. Против групповых ошибокдлины n+1 он бессилен.
В общем случае вероятность правильной передачи при длинегрупповой ошибки n равна 2-n. Поэтому на практике применяют другую технику, котораяназывается циклическим избыточным кодом (Cyclic Redundancy Code), или CRC-кодом.11CRC-коды построены на рассмотрении битовой строки как строки коэффициентовполинома. Битовую строку длины k рассматривают как коэффициенты полинома степениk-1. Самый левый бит строки - коэффициент при старшей степени.
Например, строка110001 представляет полином x5+x4+x0.Использование полиномиальных кодов при передаче заключается в следующем.Отправитель и получатель заранее договариваются о конкретном генераторе полиномовG(x), у которых коэффициенты при старшем члене и при младшем члене должны бытьравны 1. Пусть степень G(x) равна r. Для вычисления контрольной суммы блока из m битдолжно быть r<m. Идея состоит в том, чтобы добавить контрольную сумму кпередаваемому блоку, рассматриваемому как полином М(х), так, чтобы передаваемыйблок с контрольной суммой был кратен G(x). Когда получатель получает блок сконтрольной суммой, он делит его на G(x). Если есть остаток, то были ошибки припередаче.
Полиномиальная арифметика выполняется по модулю 2. Сложение и вычитаниепроисходит без переноса разрядов. Таким образом, обе эти операции эквивалентныEXCLUSIVE OR. Например,10011011001100111111000001010101+ 11001010 + 11001101 - 10100110 - 10101111----------- ---------- ----------- ----------01010001111111100101011011111010Деление выполняется, как обычно в двоичной системе, с той лишь разницей, чтовычитание выполняется по модулю два.Алгоритм вычисления контрольной суммы:Здесь r - степень G(x).1.2.3.Добавить r нулей в конец блока так, что он содержал m+r разрядов исоответствовал полиному xr M(x).Разделить по модулю 2 полином xr M(x) на G(x).Вычесть остаток (длина которого всегда не более r разрядов) из строки,соответствующей xr M(x), по модулю 2.
Результат и есть блок с контрольной суммой(назовем его Т(х)).Рисунок 3-7 показывает этот алгоритм для блока 1101011011 и G(x) = х4+х+1.Рисунок 3-7. Расчет контрольной суммы для полиномиального кода12Данный метод позволяет обнаруживать одиночные ошибки. Групповые ошибки длины неболее r. Нечетное число отдельных ошибок. Существует три международных стандарта навид G(x):121132• CRC-12 = x +x +x +x +x+116152• CRC-16 = x +x +x +116125• CRC-CCITT = x +x +x +1CRC-12 используется для передачи символов из 6 разрядов. Два остальных - для 8разрядных.
CRC-16 и CRC-CCITT ловят одиночные, двойные ошибки, групповые ошибкидлины не более 16 и нечетное число изолированных ошибок с вероятностью 99,997%.Раздел 3.3. Простейшие протоколы канала данныхРассмотрение протоколов уровня канала данных мы начнем с нескольких предположений.Будем предполагать, что физический уровень, уровень канала данных, сетевой уровень –реализованы в виде независимых процессов, взаимодействующих с помощью передачисообщений.
В некоторых случаях физический уровень и уровень канала данных могутвыполняться на некотором вспомогательном процессоре ввода-вывода, внешнем поотношению к основному процессору; в некоторых случаях все процессы могутвыполняться на основном процессоре. Возможны также разные реализации: физический иканальный уровни могут быть реализованы в виде процедур, вызываемых сетевым13уровнем, и т.д.
Однако мы будем предполагать, что все три уровня представлены какнезависимые процессы.Также мы предположим, что есть две машины: А и В. У машины А есть бесконечнодлинный набор данных, который надо передать машине В с помощью надежного сервиса,ориентированного на соединение. Передача всегда происходит от А к В, хотя позднее мыдопустим одновременную передачу от В к А. Также будем предполагать, что есликанальный уровень на машине А запрашивает данные для передачи от сетевого уровня, тоони всегда есть и нет задержки на их подготовку.Канальный уровень рассматривает данные, которые он получает от сетевого, какнеструктурированные, несмотря на то, что там есть хотя бы заголовок сетевого уровня.Все эти данные должны быть переданы равнозначному сетевому уровню. Когдаканальный уровень получает пакет, он погружает его в кадр, добавляя заголовок иконцевик.
Этот кадр затем передается по физическому уровню. Будем предполагать, чтоесть две библиотечные процедуры: from_physical_layer - для получения кадра сфизического уровня, и to_physical_layer - для передачи кадра на физический уровень.Предполагаем, что вычисление и добавление контрольных сумм происходит аппаратно.Изначально получатель просто ожидает, ничего не предпринимая, наступления какоголибо события. В наших примерах это будет выражаться в вызове процедурыwait_for_event(&event), где параметр event возвращает информацию о произошедшемсобытии. Ясно, что в действительности никто не будет ожидать в цикле (будутиспользованы прерывания), но мы для простоты будем считать так.Когда кадр поступает к получателю, контрольная сумма вычисляется аппаратно.
Если онаневерна, то канальному уровню сообщается: event=cksum_err. Если кадр поступил безповреждений, то канальный уровень информируется так: event=frame_arrivel.На рисунке 3-8 приведены многие структуры, используемые позднее. Там же указаныпроцедуры, которые используются при построении протоколов.Рисунок 3-8. Перечень функций, используемых в описании протокола канального уровня14Как мы уже отмечали, для того чтобы обнаруживать случаи потери кадров, уровеньканала, отправляя кадр, должен устанавливать таймер.
Если подтверждение не придетраньше, чем истечет время таймера, то считается, что кадр не дошел. В этом случаеevent=timeout. Процедуры start_timer и stop_timer используют для пуска и остановкитаймера. Процедуру запуска таймера можно вызывать, не ожидая окончания предыдущегозапуска. Подобное обращение будет означать перезапуск таймера на новый интервал.Процедуры start_act_timer и stop_act_timer используются для управления дополнительнымтаймером, используемым в определенных случаях для уведомления.Процедуры enable_network_layer и disable_network_layer используются в сложныхпротоколах, когда предполагается, что на сетевом уровне нет пакетов для передачи. Когдаканальный уровень разрешит сетевому уровню снова передавать пакеты, сетевойинформирует об этом событием event=network_layer_ready. Если канальный уровеньвыполнил процедуру disable_network_layer, то event=network_layer_ready может и непоследовать.
Таким способом канальный уровень может управлять потоком от сетевогоуровня.153.3.1. Симплекс-протокол без ограниченийНа рисунке 3-9 представлен простейший протокол канального уровня. Данные передаютсятолько в одном направлении. Получатель и отправитель всегда готовы к отправке иполучению данных. Время обработки данных игнорируется. Предполагается, что буфернеограниченного размера. Данные в канале не теряются и не искажаются.Рисунок 3-9. Симплексный протокол канального уровня3.3.2. Симплексный старт-стопный протоколТеперь снимем одно из ограничений предыдущего протокола - способность сетевогоуровня обрабатывать поступающие данные сколь угодно быстро. Все остальныепредположения остаются в силе: канал абсолютно надежный, трафик однонаправленный.Основная проблема - как предотвратить ситуацию, когда отправитель «заваливает»данными получателя.
Если получателю требуется время Δt, чтобы исполнитьfrom_physical_layer плюс to_network_layer, то отправитель должен передавать данные сосредней скоростью один кадр в Δt.Решением такой проблемы может быть введение коротких специальных служебныхсообщений. Получатель, получив один или несколько кадров, отправляет отправителюкороткий специальный кадр, означающий, что отправитель может передавать следующий.Это так называемый старт-стопный протокол, показанный на рисунке 3-10.16Рисунок 3-10.
Однонаправленный старт-стопный протокол канального уровня3.3.3. Симплексный протокол для канала с шумомОсновная проблема при передаче состоит в том, что кадр с подтверждением о полученииможет потеряться целиком. Как отличить кадр, переданный первый раз, от кадра,переданного повторно?Одно из очевидных решений - нумерация передаваемых кадров. Однако сколько местаотводить под эту нумерацию? Поскольку проблема различения стоит для кадров m и m+1,то достаточно одного разряда. 0 - для только что посланного кадра и 1 - для следующегоожидаемого.
Все кадры, не содержащие корректной нумерации, просто сбрасываются приприеме.На рисунке 3-11 показана программа для этого варианта протокола.Рисунок 3-11. Протокол с подтверждением и восстановлением17Раздел 3.4. Протоколы скользящего окнаВ рассмотренных выше протоколах канального уровня кадры передавались только водном направлении. Для передачи в обоих направлениях можно потребовать нафизическом уровне двух симплексных каналов. Один для передачи кадров, другой - дляпередачи подтверждений. Однако использование канала только для подтверждений довольно дорогое удовольствие. Можно смешивать кадры с данными и кадры сподтверждениями на одном канале.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
