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

Коды Рида—Соломона часто используют в сочетании с другими кодами, например сверточными. И вот почему. Сверточные коды эффективно обрабатывают изолированные однобитные ошибки, но с последовательностью ошибок они, скорее всего, не справятся, особенно если ошибок в полученном потоке бит слишком много. Добавив внутрь сверточного кода код Рида—Соломона, вы сможете очистить поток бит от последовательностей ошибок. Таким образом, получившийся составной код обеспечит надежную защиту как от одиночных, так и от массовых ошибок.

Наконец, взглянем на код LDPC( Low-Density Parity Check, код с малой плотностью проверок на четность). Коды LDPC — это линейные блочные коды, изобретенные Робертом Галлагером и описанные в его докторской диссертации (Gallagher, 1962). Как и о большинстве других диссертаций, об этой вскоре позабыли. Однако в 1995 году, когда вычислительные мощности сделали огромный скачок вперед, представленный в ней код изобрели заново.

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

Коды LDPC удобно применять для блоков большого размера. Они превосходно справляются с ошибками — лучше, чем на практике удается многим другим кодам (включая те, с которыми мы уже познакомились). По этой причине коды LDPC быстро добавляются в новые протоколы. Они являются частью стандарта цифрового телевидения, сетей Ethernet 10 Гбит/с, сетей, работающих по линиям электропитания, а также последней версии 802.11. Очевидно, что эти коды обязательно будут использоваться и в новых сетях, пока что находящихся на стадии разработки.

3.2.2. Коды с обнаружением ошибок

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

Мы рассмотрим три кода с обнаружением ошибок. Все они относятся к линейным систематическим блочным кодам:

1. Код с проверкой на четность.

2. Код с контрольными суммами.

3. Циклический избыточный код.

Для того чтобы понять, в каких ситуациях обнаружение ошибок может быть эффективнее исправления, возьмем первый из перечисленных кодов. К отправляемым данным присоединяется единственный бит четности( parity bit), который выбирается так, чтобы число единичных битов в кодовом слове было четным (или нечетным). Это эквивалентно вычислению бита четности в виде суммы по модулю 2 для битов данных (или применению операции исключающего ИЛИ). Например, если отправляется кодовое слово 1011010 и число единиц должно быть четным, то в конце добавляется ноль, и последовательность превращается в 10110100. Если же число единиц должно быть нечетным, то последовательность устанавливается такая: 10110101. Кодовое расстояние кода с единственным битом четности равно двум, так как любая однобитная ошибка меняет четность кодового слова на неправильную. Это означает, что данный код позволяет распознавать однобитные ошибки.

Рассмотрим канал с изолированными ошибками, возникающими с вероятностью 10 -6на бит. Такое значение может показаться очень небольшим, но для длинного кабельного канала, в котором распознавать ошибки довольно сложно, оно в лучшем случае считается допустимым. Типичные локальные сети характеризуются вероятностью ошибки 10 -10. Пусть блок данных состоит из 1000 бит. Для создания кода, исправляющего однократные ошибки в 1000-битном блоке, как видно из представленного выше уравнения (3.1), потребуется 10 контрольных бит. Для 1 Мбит данных это составит 10 000 проверочных бит. Чтобы просто обнаруживать одиночную 1-битовую ошибку, достаточно одного бита четности на блок. На каждые 1000 блоков будет выявляться одна ошибка, и придется переслать повторно еще один блок (1001 бит), чтобы исправить ее. Таким образом, суммарные накладные расходы на обнаружение ошибки и повторную передачу составят всего 2001 бит на 1 Мбит данных против 10 000 бит, необходимых для кода Хэмминга.