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

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

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

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

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

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

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

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

3.2.1. Коды с исправлением ошибок

Мы рассмотрим четырех разных кода с исправлением ошибок:

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

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

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

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