Компьютерные сети. 6-е изд.

Чтобы определить, какой метод лучше подойдет в конкретной ситуации, нужно понять, какой тип ошибок более вероятен. Но ни одна из стратегий не позволит справиться со всеми возможными ошибками, поскольку дополнительные биты, передаваемые для повышения надежности, также могут быть повреждены в пути. Было бы неплохо, если бы каналы передачи могли отличать такие биты от битов полезных данных, но это невозможно. Для канала все биты одинаковы. Поэтому, чтобы избежать необнаруженных ошибок, необходимо использовать достаточно надежные коды, чтобы успешно справляться со всеми прогнозируемыми ошибками.

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

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

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

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

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

3.2.1. Корректирующие коды

Мы рассмотрим четыре разных корректирующих кода:

1. Коды Хэмминга.

2. Двоичные сверточные коды.

3. Коды Рида — Соломона.

4. Коды с малой плотностью проверок на четность.

Все эти коды добавляют к отправляемой информации избыточные данные. Фрейм состоит из битов данных, то есть информационных битов (m), и избыточных, или контрольных, битов (r). В блочном коде (block code) r вычисляется как простая функция от m: r и m связаны друг с другом, как если бы они находились в огромной таблице соответствий. В систематическом коде (systematic code) m пересылается напрямую вместе с r и не кодируется перед отправкой. В линейном коде (linear code) r вычисляется как линейная функция от m. Очень часто используется функция исключающего ИЛИ (XOR) или суммирование по модулю 2. Это означает, что для кодирования используются такие операции, как умножение матриц или простые логические схемы. Далее в этом разделе речь пойдет о линейных систематических блочных кодах (если не будет указано иное).