Эндрю Уэзеролл - Компьютерные сети. 5-е издание

В одной модели считается, что причина ошибок — экстремально высокие значения термального шума, которые изредка на короткие промежутки времени перекрывают сигнал, порождая изолированные однобитные ошибки. Вторая модель предполагает, что ошибки чаще возникают целыми последовательностями, а не по одиночке. Объясняется это физическими процессами, вызывающими неполадки, такими как глубокое замирание беспроводного канала или временная электрическая помеха в кабельном канале.

Обе модели имеют практическую значимость, но у каждой свои преимущества и недостатки. Почему последовательность ошибок может быть лучше одиночных? Компьютер всегда отправляет данные блоками. Предположим, что размер блока равен 1000 бит, а вероятность ошибки равна 0,001 на один бит. Если бы ошибки были независимыми, то почти в каждом блоке обнаруживалась бы ошибка. Однако если возникнет целая последовательность ошибок, то в среднем из ста блоков только один будет поврежден. С другой стороны, последовательность ошибок исправить намного сложнее, чем изолированные ошибки.

Существуют и другие типы ошибок. Иногда местоположение ошибки известно. Например, физический уровень получает аналоговый сигнал, значение которого намного отличается от ожидаемого нуля или единицы, и объявляет, что бит потерян. Такой канал называется каналом со стиранием( erasure channel). В каналах со стиранием ошибки исправлять проще, чем в каналах, где значения битов меняются на противоположные: даже если значение бита утеряно, по крайней мере, нам известно, где притаилась ошибка. Тем не менее воспользоваться преимуществами стирающих каналов удается нечасто.

Далее мы рассмотрим коды с исправлением ошибок и коды с обнаружением ошибок. Прошу вас только не забывать о двух вещах. Во-первых, мы изучаем этот вопрос на канальном уровне, так как это первое место, где перед нами встает проблема надежной пересылки группы битов. Однако коды используются весьма широко, так как вопрос надежности важен всегда и везде. Коды исправления ошибок можно встретить на физическом уровне, особенно когда речь идет о зашумленных каналах, и на более высоких уровнях, особенно при рассылке мультимедийной информации в режиме реального времени. Коды обнаружения ошибок применяются на канальном, сетевом и транспортном уровнях.

Помимо этого, следует помнить, что коды ошибок относятся к прикладной математике. Если только вы не крупный специалист по полям Галуа или свойствам слабо заполненных матриц, используйте надежные коды, полученные из проверенных источников, и не пытайтесь конструировать собственные. В действительности, так делается во многих стандартных протоколах; одни и те же коды будут встречаться вам снова и снова. Далее мы подробно изучим простой код, а затем коснемся нескольких более сложных. Так вы сможете лучше понять преимущества и недостатки различных кодов и познакомиться с кодами, применяемыми на практике.

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. На практике значения нормы могут сильно отличаться. Например, для шумного канала обычной нормой считается 1/2, то есть половина полученной информации будет избыточной. В хороших каналах норма близка к единице, и к большим сообщениям добавляются лишь несколько контрольных бит.