Компьютерные сети. 6-е изд. - Эндрю Таненбаум
Шрифт:
Интервал:
Закладка:
Коды Рида — Соломона часто используются в сочетании с другими кодами, например сверточными, и вот почему. Сверточные коды эффективно обрабатывают изолированные однобитные ошибки, но с последовательностью ошибок они, скорее всего, не справятся, особенно если ошибок в полученном потоке битов слишком много. Добавив внутрь сверточного кода код Рида — Соломона, можно очистить поток битов от последовательностей ошибок. Таким образом, получившийся составной код обеспечит надежную защиту как от одиночных, так и от массовых ошибок.
Наконец, рассмотрим код LDPC (Low-Density Parity Check — код с малой плотностью проверок на четность). Коды LDPC — это линейные блочные коды, изобретенные Робертом Галлагером и описанные в его докторской диссертации (Gallager, 1962). О ней быстро забыли, как и о большинстве других диссертаций. Однако в 1995 году, когда вычислительные мощности сделали огромный скачок вперед, представленный в ней код был изобретен заново.
В коде LDPC каждый выходной бит формируется из некоторого подмножества входных битов. Это приводит нас к матричному представлению кода с низкой плотностью единиц — отсюда и название. Полученные кодовые слова декодируются алгоритмом аппроксимации, который итеративно ищет наилучшее приближение, составленное из полученных данных, пока не получает допустимое кодовое слово. Так происходит устранение ошибок.
Коды LDPC удобно применять для блоков большого размера. Они превосходно справляются с ошибками — лучше, чем многие другие коды (включая те, с которыми мы уже познакомились). По этой причине коды LDPC активно добавляются в новые протоколы. Они являются частью стандарта цифрового телевидения, сетей Ethernet 10 Гбит/с, ЛЭП, а также последней версии 802.11. Очевидно, что эти коды обязательно будут использоваться и в новых сетях, которые еще находятся на стадии разработки.
3.2.2. Коды для обнаружения ошибок
Корректирующие коды широко применяются в беспроводных системах связи, известных зашумленностью и ненадежностью по сравнению с оптоволокном. Передать что-либо, не используя эти коды, практически невозможно. Однако при отправке данных по оптоволокну или высококачественному медному проводу уровень ошибок гораздо ниже, поэтому их обнаружение и повторная передача данных — более подходящий метод.
Мы рассмотрим три кода для обнаружения ошибок. Все они относятся к линейным систематическим блочным кодам:
1. Код с проверкой на четность.
2. Код с контрольными суммами.
3. Циклический избыточный код.
Чтобы понять, в каких ситуациях обнаружение ошибок эффективнее их исправления, рассмотрим первый из перечисленных кодов. К отправляемым данным присоединяется единственный бит четности (parity bit), который выбирается так, чтобы число единичных битов в кодовом слове было четным (или нечетным). Это аналогично вычислению бита четности в виде суммы по модулю 2 для битов данных (или применению операции XOR). Например, если отправляется комбинация 1011010 и число единиц должно быть четным, то в конце добавляется ноль и последовательность превращается в 10110100. Если же число единиц должно быть нечетным, то комбинация превращается в 10110101. Расстояние Хэмминга у кода с единственным битом четности равно двум, так как любая однобитовая ошибка меняет четность кодового слова на неправильную. Это означает, что данный код позволяет распознавать однобитовые ошибки.
Рассмотрим канал с изолированными ошибками, возникающими с вероятностью 10–6 на бит. Такое значение может показаться очень небольшим, но для длинного кабельного канала, в котором распознавать ошибки довольно сложно, оно в лучшем случае считается допустимым. Типичные LAN характеризуются вероятностью ошибки 10–10. Пусть блок данных состоит из 1000 бит. Как видно из представленного выше уравнения (3.1), чтобы создать код, исправляющий однократные ошибки в 1000-битном блоке, потребуется 10 контрольных битов. Для 1 Мбит данных это составит 10 000 проверочных бит. Чтобы просто обнаружить одиночную однобитную ошибку, достаточно одного бита четности на блок. На каждые 1000 блоков будет выявляться одна ошибка, и придется переслать повторно еще один блок (1001 бит), чтобы исправить ее. Таким образом, суммарные накладные расходы на обнаружение ошибки и повторную передачу составят всего 2001 бит на 1 Мбит данных против 10 000 бит, необходимых для кода Хэмминга.
Проблема данной схемы в том, что если к блоку добавлять всего один бит четности, то гарантированно распознаваться будет только одна однобитовая ошибка в блоке. В случае возникновения длинной последовательности ошибок вероятность обнаружения ошибки будет всего лишь 0,5, что абсолютно неприемлемо. Этот недостаток может быть исправлен, если рассматривать каждый посылаемый блок как прямоугольную матрицу n бит шириной и k бит высотой (принцип ее построения был описан выше). Если вычислить и отправить один бит четности для каждой строки, то можно гарантированно обнаружить до k однобитных ошибок (если в каждой строке будет не больше одной ошибки).
Однако можно сделать кое-что еще, чтобы повысить уровень защиты от последовательностей ошибок, — биты четности можно вычислять в порядке, отличном от того, в каком данные отправляются по каналу связи. Этот способ называется чередованием (interleaving). В нашем примере мы будем вычислять бит четности для каждого из n столбцов, но биты данных будут отправляться в виде k строк в обычном порядке: сверху вниз и слева направо. В последней строке отправим n бит четности. На илл. 3.8 порядок пересылки показан для n = 7 и k = 7.
Илл. 3.8. Чередование битов четности для обнаружения последовательностей ошибок
С помощью чередования код, обнаруживающий (или исправляющий) изолированные ошибки, преобразуется в код, обнаруживающий (или исправляющий) пакеты ошибок. На илл. 3.8 мы видим, что при возникновении таких пакетов длиной n = 7 ошибочные биты находятся в разных столбцах. (Последовательность ошибок не предполагает, что все биты в ней неправильные; подразумевается, что ошибки есть как минимум в первом и последнем битах. На илл. 3.8 из семи сбойных битов на самом деле изменено значение только четырех.) В каждом из n столбцов повреждено будет не больше одного бита, поэтому биты четности в них помогут выявить ошибку. В данном методе n бит четности в блоках из kn бит данных применяются для обнаружения одной последовательности ошибок длиной
