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