Э. Таненбаум - Компьютерные сети. (4-е издание) (DJVU) (1130092), страница 63
Текст из файла (страница 63)
АЗСП Контрольные биты Символ 1001000 а 1100001 ги 1101101 1101101 Порядок ивредачн бит Рнс. 3.7. Корректирующий код Хэммннга Коды Хэмминга позволяют исправлять только одиночные ошибки. Однако один не слишком хитрый трюк позволяет исправлять при помоШи этого кода и наборы ошибок. Для этого последовательность Ф кодовых слов организуется в виде матрицы, по одному кодовому слову в ряду. Обычно данные передаются по кодовым словам, слева направо. Но чтобы иметь воэможность исправлять наборы ошибок, данные из этой таблицы следует передавать по столбцу за один при- ! 1101001 п 1101110 0 1100111 0100000 с 1100011 о 1101111 о 1100100 е 1100101 00110010000 10111001001 11101010101 11101010101 01101011001 01101010110 01111001111 10011000000 11111000011 10101011111 11111001100 00111000101 236 Глава 3.
Уровень передачи данных ем слева направо. То есть сначала передается первая слева колонка. После передачи всех л битов отправляется вторая слева колонка, и т. д., как показано на рис. 3.7. Когда кадр приходит к получателю, матрица восстанавливается также столбец за столбцом. Если на блок данных наложится пакет ошибок, инвертирующий й соседних битов, она затронет не более 1 бита в каждом кодовом слове. А поскольку код Хэмминга может исправлять одиночные ошибки, то можно будет восстановить весь блок. Данный метод использует 1:г проверочных битов, благодаря которым блок из Ьл битов данных может выдержать один пакет ошибок длиной не более 1 бит. Коды с обнаружением ошибок Коды с исправлением ошибок широко применяются в беспроводных системах связи, которые славятся зашумленностью среды передачи и, следовательно, большим количеством ошибок по сравнению с системами с медным или оптоволоконным кабелем. Передать что-либо, не используя исправление ошибок, было бы практически невозможно.
Однако в системах, где информация передается по проводу, уровень сшибок гораздо ниже, поэтому обнаружение ошибок и повторная передача являются более подходящим методом. В качестве примера рассмотрим канал с изолированными ошибками, возникающими с вероятностью 10 ' на бпт. Пусть блок данных состоит из 1000 бит. Для создания кода, исправляющего однократные ошибки, потребуется 10 дополнительных битов на блок. Для мегабита данных это составит 10 000 проверочных бптов.
Чтобы просто обнаруживать одиночную 1-битовую ошибку, достаточно одного бита четности на блок. На каждые 1000 блоков придется переслать повторно в среднем еще один блок (1001 бит). Таким образом, суммарные накладные расходы на обнаружение ошибки и повторную перелачу составят всего 2001 бит на мегабит данных против 10 000 битов, необходимых для кода Хэмминга. Если к блоку добавлять всего один бит четности, то в случае возникновения пакета ошибок вероятность обнаружения ошибки будет всего лишь 0,5, что абсолютно неприемлемо. Этот недостаток может быть исправлен, если рассматривать каждый посылаемый блок как прямоугольную матрицу и бит шириной и А бит высотой (принцип ее построения был описан ранее).
Бит четности должен вычисляться отдельно для каждого столбца и добавляться к матрице в качестве последней строки. Затем матрица передается построчно. Когда блок прибывает, приемник проверяет все биты четности. Если хотя бы один из них неверен, он запрашивает повторную отсылку всего блока.
Этот процесс может циклически продолжаться до тех пор, пока весь блок не будет принят без ошибок в битах четности. Такой метод позволяет обнаружить одиночный пакет ошибок длиной не более п, так как в этом случае будет изменено не более 1 бита в каждом столбце. Однако пакет ошибок длиной и + 1 не будет обнаружен, если будут инвертированы первый и последний биты, а все остальные биты останутся неизменными. (Пакет ошибок не предполагает, ч1о все биты неверны, предполагается только, Обнаружение и исправление ошибок 237 что по меньшей мере первый и последний биты инвертированы.) Если в блоке при передаче возникнет длинный пакет ошибок или несколько одиночных ошибок вероятность того, что четность любого из п столбцов будет верной (или неверной), равна 0,5, поэтому вероятность необнаружения ошибки будет равна 2 ", Хотя приведенная схема в некоторых случаях может быть приемлемой, на практике широко используется другой метод — полиномиальный код, также известный как СКС (Сус!(с Кедипдапсу Сйес)г — циклический избыточный код).
В основе полиномиальных кодов лежит представление битовых строк в виде многочленов с коэффициентами, равными только 0 или 1. Кадр из (' бит рассматривается как список коэффициентов многочлена степени 1 — 1, состоящего из л членов от х' ' до х', Старший (самый левый) бит кадра соответствует коэффициенту при х~ ', следующий бит — коэффициенту прн х ', и т. д. Например, число 110001 состоит из 6 бит и, следовательно, представляется в виде многочлена пятой степени с коэффициентами 1, 1, О, О, 0 и 1; х' е хк ~- х'.
С данными многочленами осуществляются арифметические действия по модулю 2 в соответствии с алгебраической теорией поля. При этом перенос при сложении и заем при вычитании не производится. И сложение, и вычитание эквивалентны исключающему ИЛИ (ХОК): 10011011 00110011 11110000 01010101 шы1но "~1саио~ — нноио — ~оеш~ 01010001 11111110 01010110 11111010 Деление чисел осуществляется так же, как и деление обычных двоичных чисел, с той разницей, что вычитание производится по модулю 2, как показано выше.
При использовании циклического кода отправитель и получатель должны сначала договориться насчет образующего многочлена, С(х). Старший и младший биты образующего многочлена должны быть равны 1. Для вычисления контрольной суммы для некоторого кадра из т бит, соответствующего полиному М(х), необходимо, чтобы этот кадр был длиннее образующего многочлена. Идея состоит в добавлении контрольной суммы в конец кадра таким образом, чтобы получившийся многочлен делился на образующийся многочлен С(х) без остатка.
Получатель, приняв кадр, содержащий контрольную сумму, пытается разделить его на 6(х). Ненулевой остаток от деления означает ошибку. Алгоритм вычисления контрольной суммы при этом может быть следующим: 1. Пусть г — степень многочлена 6(х). Добавим г нулевых битов в конец кадра так, чтобы он содержал т + г бит и соответствовал многочлену х"М(х). 2. Разделим по модулю 2 битовую строку, соответствующую многочлену х"М(х), на битовую строку, соответствующую образующему многочлену 6(х). 3. Вычтем по модулю 2 остаток от деления (он должен быть не более г бит) из битовой строки, соответствующей многочлену х'М(х). Результат и будет передаваемым кадром, который мы будем называть многочленом Т(х). На рис.
3.8 показаны вычисления для кадра 1101011011 и образующего многочлена б(х) = х" + х е 1. 238 Глава 3. Уровень передачи данных Кадр: 1101011011 Образующий многочлен: 10011 Сообщение лоследобавления 4 нулввыхбитов: 11 01 011 011 0000 1100001010 10011 11010110110000 1ОО11~ 10011 10011 0000 00000 00010 00000 00101 00000 01011 00000 10110 10011 01010 00000 10100 10011 01110 Остаток 1110 Передаваемый кадр: 11 01011 0111110 Рис. З.В. Вычисление контрольной суммы циклического кода Должно быть очевидно, что многочлен Т(х) делится (по модулю 2) на С(х) без остатка.
В любом случае, если вы уменьшите делимое на остаток, то результат должен делиться без остатка. Например, в десятичной системе счисления, если разделить 210 278 на 10 941, то остаток от деления будет равен 2399. Если вычесть 2399 из 210 278, то результат (207 879) будет делиться на 10 941 без остатка. Теперь проанализируем возможности этого метода. Какие ошибки сможет он обнаруживать? Представим, что произошла ошибка при передаче кадра, так что вместо многочлена Т(х) получатель принял Т(х) + Е(х), Каждый единичный бит многочлена Е(х) соответствует инвертированному биту в пакете. Если в много- Обнаружение и исправление ошибок 239 члене Е(х) А бит равны 1, зто означает, что произошло А единичных ошибок.
Единичный пакет ошибок характеризуется первой единицей, смесью нулей и единиц и конечной единицей, а остальные биты равны О. Получатель делит принятый кадр с контрольной суммой на образующий многочлен С(х), то есть он вычисляет 1Т(х) + Е(х))/С(х). Т(х)/С(г) равно О, поэтому результат вычислений просто равен Е(х)/С(х). Ошибки, которые случайно окажутся кратными образующему многочлену С(х), останутся незамеченными, остальные ошибки будут обнаружены. Если происходит единичная ошибка, то Е(х) = К где 1 означает номер ошибочного бита.
Если образующий многочлен С(х) содержит два или более членов, то Е(х) никогда не будет делиться на него без остатка, поэтому будут обнаружены все единичные ошибки. В случае двух изолированных однобитовых ошибок Е(х) = х' + .К где 1 >7', зто можно также записать в виде Е(х) = х'(х' ' + 1). Если предположить, что образующий многочлен С(х) не делится на х, то достаточным условием обнаружения всех двойных ошибок будет неделимость на С(х) многочлена х" + 1 для любого я от 1 до максимального значения(-/, то есть до максимальной длины кадра. Известны простые многочлены с небольшими степенями, обеспечивающие защиту для длинных кадров. Например, многочлен х + х + 1 не является делителем 15 и для х" + 1 для любого 1 от 1 до 32 768. Если ошибка затронет нечетное количество битов в кадре, многочлен Е(х) будет содержать нечетное число членов (например, х' + х'+ 1, но не хл е 1).
Интересно, что в системе арифметических операций по модулю 2 многочлены с нечетным числом членов не делятся на х + 1. Если в качестве образующего выбрать многочлен, делящийся на х + 1, то с его помощью можно обнаружить все ошибки, состоящие из нечетного количества инвертированных битов. Чтобы показать, что никакой многочлен с нечетным количеством членов не делится на х + 1, предположим, что многочлен Е(х) содержит нечетное количество членов и делится на х+ 1. Таким образом, Е(х) может быть представлен в виде произведения Е(х) = (х + 1)Я(х).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
