Э. Таненбаум - Компьютерные сети. (4-е издание) (PDF) (1130118), страница 60
Текст из файла (страница 60)
Однакоодин не слишком хитрый трюк позволяет исправлять при помощи этого кодаи наборы ошибок. Для этого последовательность k кодовых слов организуется ввиде матрицы, по одному кодовому слову в ряду. Обычно данные передаются покодовым словам, слева направо. Но чтобы иметь возможность исправлять наборы ошибок, данные из этой таблицы следует передавать по столбцу за один при-236Глава 3. Уровень передачи данныхем слева направо. То есть сначала передается первая слева колонка. После передачи всех k битов отправляется вторая слева колонка, и т.
д., как показано нарис. 3.7. Когда кадр приходит к получателю, матрица восстанавливается такжестолбец за столбцом. Если на блок данных наложится пакет ошибок, инвертирующий к соседних битов, она затронет не более 1 бита в каждом кодовом слове.А поскольку код Хэмминга может исправлять одиночные ошибки, то можно будет восстановить весь блок. Данный метод использует кг проверочных битов,благодаря которым блок из km битов данных может выдержать один пакет ошибок длиной не более к бит.Коды с обнаружением ошибокКоды с исправлением ошибок широко применяются в беспроводных системахсвязи, которые славятся зашумленностью среды передачи и, следовательно, большим количеством ошибок по сравнению с системами с медным или оптоволоконным кабелем.
Передать что-либо, не используя исправление ошибок, было быпрактически невозможно. Однако в системах, где информация передается по проводу, уровень ошибок гораздо ниже, поэтому обнаружение ошибок и повторнаяпередача являются более подходящим методом.В качестве примера рассмотрим канал с изолированными ошибками, возникающими с вероятностью 1(Г6 на бит. Пусть блок данных состоит из 1000 бит.Для создания кода, исправляющего однократные ошибки, потребуется 10 дополнительных битов на блок. Для мегабита данных это составит 10 000 проверочных битов.
Чтобы просто обнаруживать одиночную 1-битовую ошибку, достаточно одного бита четности на блок. На каждые 1000 блоков придется переслатьповторно в среднем еще один блок (1001 бит). Таким образом, суммарные накладные расходы на обнаружение ошибки и повторную передачу составят всего2001 бит на мегабит данных против 10 000 битов, необходимых для кода Хэмминга.Если к блоку добавлять всего один бит четности, то в случае возникновенияпакета ошибок вероятность обнаружения ошибки будет всего лишь 0,5, что абсолютно неприемлемо. Этот недостаток может быть исправлен, если рассматривать каждый посылаемый блок как прямоугольную матрицу п бит шириной ик бит высотой (принцип ее построения был описан ранее). Бит четности долженвычисляться отдельно для каждого столбца и добавляться к матрице в качествепоследней строки. Затем матрица передается построчно.
Когда блок прибывает,приемник проверяет все биты четности. Если хотя бы один из них неверен, онзапрашивает повторную отсылку всего блока. Этот процесс может циклическипродолжаться до тех пор, пока весь блок не будет принят без ошибок в битахчетности.Такой метод позволяет обнаружить одиночный пакет ошибок длиной не более п, так как в этом случае будет изменено не более 1 бита в каждом столбце.Однако пакет ошибок длиной п + 1 не будет обнаружен, если будут инвертированы первый и последний биты, а все остальные биты останутся неизменными.(Пакет ошибок не предполагает, что все биты неверны, предполагается только,Обнаружение и исправление ошибок237что по меньшей мере первый и последний биты инвертированы.) Если в блокепри передаче возникнет длинный пакет ошибок или несколько одиночных ошибок, вероятность того, что четность любого из п столбцов будет верной (или неверной), равна 0,5, поэтому вероятность необнаружения ошибки будет равна 2~".Хотя приведенная схема в некоторых случаях может быть приемлемой, на практике широко используется другой метод — полиномиальный код, также известныйкак CRC (Cyclic Redundancy Check — циклический избыточный код).
В основеполиномиальных кодов лежит представление битовых строк в виде многочленовс коэффициентами, равными только 0 или 1. Кадр из к бит рассматривается какхсписок коэффициентов многочлена степени к - 1, состоящего из k членов от х*~к хдо х°. Старший (самый левый) бит кадра соответствует коэффициенту при х ~ ,к 2следующий бит — коэффициенту при х ~ , и т. д. Например, число 110001 состоит из 6 бит и, следовательно, представляется в виде многочлена пятой степени с54коэффициентами 1, 1, 0, 0, 0 и 1: х + х + х°.С данными многочленами осуществляются арифметические действия по модулю 2 в соответствии с алгебраической теорией поля. При этом перенос присложении и заем при вычитании не производится.
И сложение, и вычитание эквивалентны исключающему ИЛИ (XOR):10011011001100111111000001010101+ 11001010+11001101-10100110-1010111101010001111111100101011011111010Деление чисел осуществляется так же, как и деление обычных двоичных чисел, с той разницей, что вычитание производится по модулю 2, как показано выше.При использовании циклического кода отправитель и получатель должнысначала договориться насчет образующего многочлена, G(x). Старший и младший биты образующего многочлена должны быть равны 1. Для вычисления контрольной суммы для некоторого кадра из т бит, соответствующего полиномуМ(х), необходимо, чтобы этот кадр был длиннее образующего многочлена.
Идеясостоит в добавлении контрольной суммы в конец кадра таким образом, чтобыполучившийся многочлен делился на образующийся многочлен G(x) без остатка. Получатель, приняв кадр, содержащий контрольную сумму, пытается разделить его на G(x). Ненулевой остаток от деления означает ошибку.Алгоритм вычисления контрольной суммы при этом может быть следующим:1. Пусть г — степень многочлена G(x).
Добавим г нулевых битов в конец кадратак, чтобы он содержал тп + г бит и соответствовал многочлену х?М(х).2. Разделим по модулю 2 битовую строку, соответствующую многочлену x'Mix),на битовую строку, соответствующую образующему многочлену G{x).3. Вычтем по модулю 2 остаток от деления (он должен быть не более г бит) избитовой строки, соответствующей многочлену хгМ(х). Результат и будет передаваемым кадром, который мы будем называть многочленом Т(х).На рис. 3.8 показаны вычисления для кадра 1101011011 и образующего многочлена G(x) = хА + х + 1.238Глава 3.
Уровень передачи данныхКадр:Обнаружение и исправление ошибок1 1 0 10 1 1 0 11Образующий многочлен:10 0 11Сообщение после добавления 4 нулевых битов:1100111101011011000010 0 0 0 10 101 1 0 1 0 1 1 0 1 1 0 0 0 010 0 1 1 I10 0 1110 0 110 0 0 0 10 0 0 0 00 0 0 100 0 0 0 00 0 10 10 0 0 0 00 10 110 0 0 0 010 1 1 010 0 110 10 100 0 0 0 010 10 010 0 110 1 1 1 00 0 0 0 01110Передаваемый кадр:• Остаток11010110111110Рис.
3.8. Вычисление контрольной суммы циклического кодабез^стТткя 6 R I T b Г е В И Д Н ° ' ЧТ° М н о г о ч л е н Г<*> Делится (по модулю 2) на G(x)оес остатка, а любом случае, если вы уменьшите делимое на остаток то результат должен Делиться без остатка. Например, в десятичной системе счисленияa 10941>тоостатокотделениябудетравен2399 ЕслиTZ!"f3^Zo^вычесть 2399 из 210 278, то результат (207 879) будет делиться на 10 941 без ос-татка.Теперь проанализируем возможности этого метода. Какие ошибки сможет оноонаруживать.' Представим, что произошла ошибка при передаче кадра, так чтовместо многочлена Т(х) получатель принял Т(х) + Е(х).
Каждый единичный битмногочлена Ь(х) соответствует инвертированному биту в пакете. Если в много-239члене Е(х) k бит равны 1, это означает, что произошло k единичных ошибок. Единичный пакет ошибок характеризуется первой единицей, смесью нулей и единици конечной единицей, а остальные биты равны 0.Получатель делит принятый кадр с контрольной суммой на образующиймногочлен G(x), то есть он вычисляет [Т(х) + E(x)]/G(x). T(x)/G(x) равно 0, поэтому результат вычислений просто равен E(x)/G(x). Ошибки, которые случайно окажутся кратными образующему многочлену G(x), останутся незамеченными, остальные ошибки будут обнаружены.Если происходит единичная ошибка, то Е(х) = х1, где i означает номер ошибочного бита. Если образующий многочлен G(x) содержит два или более членов,то Е(х) никогда не будет делиться на него без остатка, поэтому будут обнаружены все единичные ошибки.В случае двух изолированных однобитовых ошибок Е(х) =х* + х1, где i >j, этоможно также записать в виде Е(х) = х'(х'~-' +1).
Если предположить, что образующий многочлен G(x) не делится на х, то достаточным условием обнаружениявсех двойных ошибок будет неделимость на G(x) многочлена х* + 1 для любого kот 1 до максимального значения i - j, то есть до максимальной длины кадра. Известны простые многочлены с небольшими степенями, обеспечивающие защитудля длинных кадров. Например, многочлен х15 + хи + 1 не является делителемдля х* + 1 для любого k от 1 до 32 768.Если ошибка затронет нечетное количество битов в кадре, многочлен Е(х) будет содержать нечетное число членов (например, х5 + х*+ 1, но не х2 + 1).
Интересно, что в системе арифметических операций по модулю 2 многочлены с нечетным числом членов не делятся на х + 1. Если в качестве образующего выбратьмногочлен, делящийся на х + 1, то с его помощью можно обнаружить все ошибки, состоящие из нечетного количества инвертированных битов.Чтобы показать, что никакой многочлен с нечетным количеством членов неделится нах + 1, предположим, что многочлен Е(х) содержит нечетное количество членов и делится на х + 1. Таким образом, Е(х) может быть представлен в виде произведения Е(х) = (х + l)Q(x).
Вычислим значение данного многочлена длях= 1: £(1) = (1 + l)Q(l). Поскольку 1 + 1 = 0 (по модулю 2), то £(1) должен бытьравен 0. Однако если многочлен Е(х) содержит нечетное количество членов, тозамена всех х на 1 будет всегда давать в результате 1. Следовательно, не существует многочлена с нечетным количеством членов, делящегося на х + 1.И наконец, что наиболее важно, полиномиальный код с г контрольными битами будет обнаруживать все пакеты ошибок длиной < г.
Пакет ошибок длиной kможет быть представлен в виде многочлена х^х*"1 +...+ 1), где i определяет, насколько далеко от правого конца кадра располагается пакет ошибок. Если образующий многочлен G(x) содержит член х°, то х1 не будет его множителем, поэтомуесли степень выражения в скобках меньше степени G(x), то остаток от деленияникогда не будет нулевым.Если длина пакета ошибок равна г + 1, то остаток от деления будет нулевымтогда и только тогда, когда пакет ошибок будет идентичен G(x).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
