Полный курс лекций 2009-го года (1130357), страница 36
Текст из файла (страница 36)
Те биты, в номера которых входит степень двойки, равная номеруконтрольного бита, и есть искомая группа. Например, 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. Использование кода Хемминга для исправления ошибок передачиКод Хемминга может исправлять только одиночные ошибки.
Однако есть прием, который позволяетраспространить идеи Хемминга на случай групповых ошибок. Пусть нам надо передать k кодослов.Расположим их в виде матрицы: одно слово - строка. Обычно передают слово за словом. Но мы поступиминаче, передадим слово длины 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-кодом.CRC-коды построены на рассмотрении битовой строки как строки коэффициентов полинома.
Битовуюстроку длины k рассматривают как коэффициенты полинома степени k - 1. Самый левый бит строки коэффициент при старшей степени. Например, строка 110001 представляет полином x5+x4+x0.Использование полиномиальных кодов при передаче заключается в следующем. Отправитель иполучатель заранее договариваются о конкретном генераторе полиномов G(x), у которых коэффициентыпри старшем члене и при младшем члене должны быть равны 1.
Пусть степень G(x) равна r. Длявычисления контрольной суммы блока из m бит должно быть r < m. Идея состоит в том, чтобы добавитьконтрольную сумму к передаваемому блоку, рассматриваемому как полином М(х), так, чтобыпередаваемый блок с контрольной суммой был кратен G(x). Когда получатель получает блок с контрольнойсуммой, он делит его на G(x). Если есть остаток, то были ошибки при передаче. Полиномиальнаяарифметика выполняется по модулю 2.
Сложение и вычитание происходит без переноса разрядов. Такимобразом, обе эти операции эквивалентны EXCLUSIVE OR. Например,1001101100110011+ 11001010 + 11001101----------01010001----------1111000001010101- 10100110- 10101111-----------11111110-----------0101011011111010Деление выполняется, как обычно в двоичной системе, с той лишь разницей, что вычитаниевыполняется по модулю два.Алгоритм вычисления контрольной суммы:Здесь r - степень G(x).1.Добавить r нулей в конец блока так, что он содержал m+r разрядов и соответствовал полиному xr M(x).2.Разделить по модулю 2 полином xr M(x) на G(x).3.Вычесть остаток (длина которого всегда не более r разрядов) из строки, соответствующей xr M(x), помодулю 2.
Результат и есть блок с контрольной суммой (назовем его Т(х)).Рисунок 3-7 показывает этот алгоритм для блока 1101011011 и G(x) = х4+х+1.Рисунок 3-7. Расчет контрольной суммы для полиномиального кодаДанный метод позволяет обнаруживать одиночные ошибки. Групповые ошибки длины не более r.Нечетное число отдельных ошибок. Существует три международных стандарта на вид G(x):§CRC-12 = x12+x11+x3+x2+x+1§CRC-16 = x16+x15+x2+1§CRC-CCITT = x16+x12+x5+1CRC-12 используется для передачи символов из 6 разрядов. Два остальных - для 8-разрядных. CRC16 и CRC-CCITT ловят одиночные, двойные ошибки, групповые ошибки длины не более 16 и нечетноечисло изолированных ошибок с вероятностью 99,997%.3.3.
Простейшие протоколы канала данныхРассмотрение протоколов уровня канала данных мы начнем с нескольких предположений. Будемпредполагать, что физический уровень, уровень канала данных, сетевой уровень – реализованы в виденезависимых процессов, взаимодействующих с помощью передачи сообщений. В некоторых случаяхфизический уровень и уровень канала данных могут выполняться на некотором вспомогательномпроцессоре ввода-вывода, внешнем по отношению к основному процессору; в некоторых случаях всепроцессы могут выполняться на основном процессоре.
Возможны также разные реализации: физический иканальный уровни могут быть реализованы в виде процедур, вызываемых сетевым уровнем, и т.д. Однакомы будем предполагать, что все три уровня представлены как независимые процессы.Также мы предположим, что есть две машины: А и В. У машины А есть бесконечно длинный наборданных, который надо передать машине В с помощью надежного сервиса, ориентированного насоединение. Передача всегда происходит от А к В, хотя позднее мы допустим одновременную передачу отВ к А. Также будем предполагать, что если канальный уровень на машине А запрашивает данные дляпередачи от сетевого уровня, то они всегда есть и нет задержки на их подготовку.Канальныйуровеньрассматриваетданные,которыеонполучаетотсетевого,какнеструктурированные, несмотря на то, что там есть хотя бы заголовок сетевого уровня. Все эти данныедолжны быть переданы равнозначному сетевому уровню.
Когда канальный уровень получает пакет, онпогружает его в кадр, добавляя заголовок и концевик. Этот кадр затем передается по физическомууровню. Будем предполагать, что есть две библиотечные процедуры: from_physical_layer - для получениякадра с физического уровня, и to_physical_layer - для передачи кадра на физический уровень.Предполагаем, что вычисление и добавление контрольных сумм происходит аппаратно.Изначально получатель просто ожидает, ничего не предпринимая, наступления какого-либо события.В наших примерах это будет выражаться в вызове процедуры wait_for_event(&event), где параметр eventвозвращает информацию о произошедшем событии. Ясно, что в действительности никто не будет ожидатьв цикле (будут использованы прерывания), но мы для простоты будем считать так.Когда кадр поступает к получателю, контрольная сумма вычисляется аппаратно. Если она неверна,то канальному уровню сообщается: event=cksum_err.
Если кадр поступил без повреждений, то канальныйуровень информируется так: event=frame_arrivel.На рисунке 3-8 приведены многие структуры, используемые позднее. Там же указаны процедуры,которые используются при построении протоколов.Рисунок 3-8. Перечень функций, используемых в описании протоколаканального уровняКак мы уже отмечали, для того чтобы обнаруживать случаи потери кадров, уровень канала,отправляя кадр, должен устанавливать таймер. Если подтверждение не придет раньше, чем истечет времятаймера, то считается, что кадр не дошел. В этом случае 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 может и не последовать. Таким способом канальный уровень может управлятьпотоком от сетевого уровня.3.3.1. Симплекс-протокол без ограниченийНа рисунке 3-9 представлен простейший протокол канального уровня. Данные передаются только водном направлении. Получатель и отправитель всегда готовы к отправке и получению данных.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
