Э. Таненбаум, Д. Уэзеролл - Компьютерные сети (1114668), страница 66
Текст из файла (страница 66)
Вторая модель предполагает,что ошибки чаще возникают целыми последовательностями, а не по одиночке. Объясняется это физическими процессами, вызывающими неполадки, такими как глубокоезамирание беспроводного канала или временная электрическая помеха в кабельномканале.Обе модели имеют практическую значимость, но у каждой свои преимуществаи недостатки. Почему последовательность ошибок может быть лучше одиночных?Компьютер всегда отправляет данные блоками.
Предположим, что размер блока равен 1000 бит, а вероятность ошибки равна 0,001 на один бит. Если бы ошибки былинезависимыми, то почти в каждом блоке обнаруживалась бы ошибка. Однако есливозникнет целая последовательность ошибок, то в среднем из ста блоков только одинбудет поврежден. С другой стороны, последовательность ошибок исправить намногосложнее, чем изолированные ошибки.Существуют и другие типы ошибок. Иногда местоположение ошибки известно.Например, физический уровень получает аналоговый сигнал, значение которого намного отличается от ожидаемого нуля или единицы, и объявляет, что бит потерян.Такой канал называется каналом со стиранием (erasure channel).
В каналах со стиранием ошибки исправлять проще, чем в каналах, где значения битов меняются на3.2. Обнаружение и исправление ошибок 227противоположные: даже если значение бита утеряно, по крайней мере, нам известно,где притаилась ошибка. Тем не менее воспользоваться преимуществами стирающихканалов удается нечасто.Далее мы рассмотрим коды с исправлением ошибок и коды с обнаружением ошибок.
Прошу вас только не забывать о двух вещах. Во-первых, мы изучаем этот вопросна канальном уровне, так как это первое место, где перед нами встает проблема надежной пересылки группы битов. Однако коды используются весьма широко, так каквопрос надежности важен всегда и везде. Коды исправления ошибок можно встретитьна физическом уровне, особенно когда речь идет о зашумленных каналах, и на болеевысоких уровнях, особенно при рассылке мультимедийной информации в режимереального времени. Коды обнаружения ошибок применяются на канальном, сетевоми транспортном уровнях.Помимо этого, следует помнить, что коды ошибок относятся к прикладной математике.
Если только вы не крупный специалист по полям Галуа или свойствам слабозаполненных матриц, используйте надежные коды, полученные из проверенных источников, и не пытайтесь конструировать собственные. В действительности, так делаетсяво многих стандартных протоколах; одни и те же коды будут встречаться вам сноваи снова. Далее мы подробно изучим простой код, а затем коснемся нескольких болеесложных. Так вы сможете лучше понять преимущества и недостатки различных кодови познакомиться с кодами, применяемыми на практике.3.2.1. Коды с исправлением ошибокМы рассмотрим четырех разных кода с исправлением ошибок:1.
Коды Хэмминга.2. Двоичные сверточные коды.3. Коды Рида—Соломона.4. Коды с малой плотностью проверок на четность.Все эти коды добавляют к пересылаемой информации избыточные данные. Кадрсостоит из m бит данных (то есть информационных бит) и r избыточных или контрольных бит. В блочном коде r контрольных бит вычисляются как простая функциясвязанных с ними m бит данных, как если бы для этих m бит данных r контрольных битнаходились по огромной таблице соответствий. В систематическом коде m бит данных пересылаются напрямую вместе с контрольными битами и не кодируются передотправкой. В линейном коде r контрольных бит вычисляются как линейная функцияот m бит данных. Очень часто используется функция исключающего ИЛИ (XOR) илисуммирование по модулю 2.
Это означает, что для кодирования используются такиеоперации, как умножение матриц или простые логические схемы. Далее в этом разделе, если не указано иное, речь пойдет о линейных систематических блочных кодах.Пусть полная длина кадра равна n (то есть n = m + r). Будем обозначать это каккод (n,m). Набор из n бит, содержащий информационные и контрольные биты, частоназывают n-битовым кодовым словом или кодовой комбинацией. Кодовая норма(code rate) или просто норма — это часть кодового слова, несущая неизбыточнуюинформацию, или m/n. На практике значения нормы могут сильно отличаться.
На-228 Глава 3. Канальный уровеньпример, для шумного канала обычной нормой считается 1/2, то есть половина полученной информации будет избыточной. В хороших каналах норма близка к единице,и к большим сообщениям добавляются лишь несколько контрольных бит.Для того чтобы понять, как исправляются ошибки, сначала необходимо познакомиться с самим понятием ошибки. Если рассмотреть два кодовых слова, например10001001 и 10110001, можно определить число отличающихся в них соответствующихразрядов. В данном примере отличаются 3 бита. Для нахождения этого числа нужносложить два кодовых слова по модулю 2 (операция «исключающее или») и сосчитатьколичество единиц в результате, например:10001001+1011000100111000Количество бит, которыми отличаются два кодовых слова, называется кодовымрасстоянием или расстоянием между кодовыми комбинациями в смысле Хэмминга(Hamming, 1950).
Смысл этого числа состоит в том, что если два кодовых слова находятся на кодовом расстоянии d, то для преобразования одного кодового слова в другоепонадобится d ошибок в одиночных битах.Зная алгоритм формирования контрольных разрядов, можно построить полныйсписок всех допустимых кодовых слов и в этом списке найти такую пару кодовыхслов, кодовое расстояние между которыми будет минимальным.
Это расстояниеназывается минимальным кодовым расстоянием кода, или расстоянием всего кодав смысле Хэмминга.В большинстве приложений передачи данных все 2m возможных сообщений являются допустимыми, однако благодаря использованию контрольных бит не все 2n возможных кодовых слов используются. В действительности, если контрольных битов r,то допустимыми считаются лишь 2m/2n или 1/2r кодовых слов, а не все возможные 2m.Именно разреженность данных в пространстве кодовых слов позволяет получателюраспознавать и исправлять ошибки.Способности блочного кода по обнаружению и исправлению ошибок зависят от егоминимального кодового расстояния.
Для надежного обнаружения d ошибок необходимкод с минимальным кодовым расстоянием, равным d + 1, поскольку d однобитовыхошибок не смогут изменить одну допустимую комбинацию так, чтобы получиласьдругая допустимая комбинация. Когда приемник встречает запрещенную кодовуюкомбинацию, он понимает, что при передаче произошла ошибка. Аналогично, дляисправления d ошибок требуется код с минимальным кодовым расстоянием, равным2d + 1, так как в данном случае даже при d однобитовых ошибках результат окажетсяближе к исходному кодовому слову, чем к любому другому и, следовательно, его можнобудет однозначно восстановить.
Это означает, что исходное кодовое слово можно восстановить уникальным образом, основываясь на предположении, что возникновениебольшого числа ошибок менее вероятно.В качестве простейшего примера корректирующего кода рассмотрим код, у которого есть всего четыре допустимые кодовые комбинации:0000000000, 0000011111, 1111100000 и 11111111113.2.
Обнаружение и исправление ошибок 229Этот код имеет расстояние, равное 5, это означает, что он может исправлять двойные ошибки и обнаруживать четверные ошибки. Если приемник получит кодовоеслово 0000000111, ожидая только однобитные или двухбитные ошибки, он поймет,что оригинал должен быть равен 0000011111. Однако если тройная ошибка изменит0000000000 на 0000000111, ошибка будет исправлена неверно. Если ожидать всеперечисленные ошибки, то их можно распознавать.
Ни одно из полученных кодовыхслов не входит в список допустимых. Следовательно, произошла ошибка. Очевидно,что в данном примере невозможно одновременно исправлять двойные ошибки и распознавать четверные, потому что для этого полученное кодовое слово нужно будетинтерпретировать двумя разными способами.В нашем примере задачу декодирования, то есть поиск допустимого кодовогослова, наиболее похожего на полученное, можно выполнить простым осмотром. К сожалению, в более общем случае, когда в качестве кандидатов приходится оцениватьвсе кодовые слова, это заняло бы очень много времени. Вместо этого разрабатываютсяпрактические коды, которые по определенным подсказкам ищут наиболее подходящееисходное кодовое слово.Попробуем создать код, состоящий из m информационных и r контрольных бит,способный исправлять одиночные ошибки. Каждому из 2m допустимых сообщенийбудет соответствовать n недопустимых кодовых слов, отстоящих от сообщения нарасстояние 1.
Их можно получить инвертированием каждого из n бит n-битовогокодового слова. Таким образом, каждому из 2m допустимых сообщений должны соответствовать n + 1 кодовых комбинаций. Поскольку общее количество возможныхкодовых комбинаций равно 2n, получается, что (n + 1)2m ≤ 2n. Так как n = m + r, этотребование может быть преобразовано к виду:(m + r + 1) ≤ 2r.(3.1)При заданном m данная формула описывает нижний предел требуемого количестваконтрольных бит для возможности исправления одиночных ошибок.Этот теоретический нижний предел может быть достигнут на практике с помощьюметода Хэмминга (1950). В кодах Хэмминга биты кодового слова нумеруются последовательно слева направо, начиная с 1. Биты с номерами, равными степеням 2 (1, 2, 4,8, 16 и т. д.), являются контрольными.
Остальные биты (3, 5, 6, 7, 9, 10 и т. д.) заполняются m битами данных. Такой шаблон для кода Хэмминга (11,7) с 7 битами данныхи 4 контрольными битами показан на рис. 3.6. Каждый контрольный бит обеспечиваетсумму по модулю 2 или четность некоторой группы бит, включая себя самого.
Одинбит может входить в несколько вычислений контрольных бит. Чтобы определить,в какие группы контрольных сумм будет входить бит данных в k-й позиции, следуетразложить k по степеням числа 2. Например, 11 = 8 + 2 + 1, а 29 = 16 + 8 + 4 + 1. Каждый бит проверяется только теми контрольными битами, номера которых входят в этотряд разложения (например, 11-й бит проверяется битами 1, 2 и 8). В нашем примереконтрольные биты вычисляются для проверки на четность в сообщении, представляющем букву «A» в кодах ASCII.Расстояние этого кода равно 3, то есть он позволяет исправлять одиночные ошибки(или распознавать двойные).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
