Э. Таненбаум, Д. Уэзеролл - Компьютерные сети (1114668), страница 67
Текст из файла (страница 67)
Причина такой сложной нумерации бит данных и контрольных бит становится очевидной, если рассмотреть процесс декодирования. Когда230 Глава 3. Канальный уровеньприбывает кодовое слово, приемник повторяет вычисление контрольных бит, учитывая значения полученных контрольных бит. Их называют результатами проверки.Если контрольные биты правильные, то для четных сумм все результаты проверкидолжны быть равны нулю. В таком случае кодовое слово принимается как правильное.01 01A1000001p1 p2 m3 p4 m5 m6 m7 p8 m9 m10 m110 0 1 0 0 0 0 1 0 0 10 0 1 0 1 0 0 1 0 0 1A1000001Рис. 3.6.
Пример кода Хэмминга (11,7), исправляющего однобитную ошибкуЕсли не все результаты проверки равны нулю, это означает, что обнаружена ошибка. Набор результатов проверки формирует синдром ошибки (error syndrome), с помощью которого выделяется и исправляется ошибка. На рис. 3.6 в канале произошлаошибка в одном бите. Результаты проверки равны 0, 1, 0 и 1 для k = 8, 4, 2 и 1 соответственно. Таким образом, синдром равен 0101 или 4 + 1 = 5. Согласно схеме, пятыйбит содержит ошибку. Поменяв его значение (а это может быть контрольный бит илибит данных) и отбросив контрольные биты, мы получим правильное сообщение: букву«A» в кодах ASCII.Кодовые расстояния полезны для понимания блочных кодов, а коды Хэммингаприменяются в самокорректирующейся памяти.
Однако в большинстве сетей используются более надежные коды. Второй тип кода, с которым мы познакомимся,называется сверточным кодом. Из всех рассмотренных в данной книге только он неотносится к блочному типу. Кодировщик обрабатывает последовательность входныхбит и генерирует последовательность выходных бит. В отличие от блочного кода, никакие ограничения на размер сообщения не накладываются, также не существует граникодирования. Значение выходного бита зависит от значения текущего и предыдущихвходных бит — если у кодировщика есть возможность использовать память. Числопредыдущих бит, от которого зависит выход, называется длиной кодового ограничениядля данного кода.
Сверточные коды описываются в терминах кодовой нормы и длиныкодового ограничения.Сверточные коды широко применяются в развернутых сетях. Например, входятв мобильную телефонную систему GSM, спутниковые сети и сети 802.11. В качествепримера можно рассмотреть популярный сверточный код, показанный на рис. 3.7.
Онназывается сверточным кодом NASA с r = 1/2 и k = 7 (впервые этот код был использован при подготовке космического полета станции Voyager, запущенной в 1977 году).С тех пор он постоянно используется в других приложениях, таких как сети 802.11.На рис. 3.7 для каждого входного бита слева создается два выходных бита справа.Эти выходные биты получаются путем применения операции исключающего ИЛИк входному биту и внутреннему состоянию. Так как кодирование работает на уровнебит и использует линейные операции, это двоичный линейный сверточный код.
По-3.2. Обнаружение и исправление ошибок 231скольку один входной бит создает два выходных бита, кодовая норма r равна 1/2.Этот код не систематический, так как входные биты никогда не передаются на выходнапрямую, без изменений.Рис. 3.7. Двоичный сверточный код NASA применяется в сетях 802.11Внутреннее состояние хранится в шести регистрах памяти. При поступлении навход очередного бита значения в регистрах сдвигаются вправо. Например, если навход подается последовательность 111, а в первоначальном состоянии в памяти тольконули, то после подачи первого, второго и третьего бита оно будет меняться на 100000,110000 и 111000 соответственно. На выходе получатся значения 11, затем 10 и затем01.
Для того чтобы полностью подавить первоначальное состояние регистров (тогдаоно не будет влиять на результат), требуется семь сдвигов. Длина кодового ограничения для данного кода k, таким образом, равна 7.Декодирование сверточного кода осуществляется путем поиска последовательности входных битов, с наибольшей вероятностью породившей наблюдаемую последовательность выходных битов (включающую любые ошибки).
Для небольшихзначений k это делается с помощью широко распространенного алгоритма, разработанного Витерби (Forney, 1973). Этот алгоритм проходит по наблюдаемой последовательности, сохраняя для каждого шага и для каждого возможного внутреннего состояниявходную последовательность, которая породила бы наблюдаемую последовательностьс минимальным числом ошибок. Входная последовательность, которой соответствуетминимальное число ошибок, и есть наиболее вероятное исходное сообщение.Сверточные коды были очень популярны для практического применения, таккак в декодировании очень легко учесть неопределенность значения бита (0 или 1).Например, предположим, что –1 В соответствует логическому уровню 0, а +1 В соответствует логическому уровню 1.
Мы получили для двух бит значения 0,9 В и –0,1 В.Вместо того чтобы сразу определять соответствие — 1 для первого бита и 0 для второго, — можно принять 0,9 В за «очень вероятную единицу», а –0,1 В за «возможныйнуль» и скорректировать всю последовательность. Для более надежного исправленияошибок к неопределенностям можно применять различные расширения алгоритмаВитерби. Такой подход к обработке неопределенности значения бит называется декодированием с мягким принятием решений (soft-decision decoding).
И наоборот, еслимы решаем, какой бит равен нулю, а какой единице, до последующего исправленияошибок, то такой метод называется декодированием с жестким принятием решений(hard-decision decoding).232 Глава 3. Канальный уровеньТретий тип кода с исправлением ошибок, с которым мы познакомимся, называется кодом Рида—Соломона. Как и коды Хэмминга, коды Рида—Соломона относятсяк линейным блочным кодам; также многие из них систематические. Но в отличие откодов Хэмминга, которые применяются к отдельным битам, коды Рида—Соломонаработают на группах из m-битовых символов. Разумеется, математика здесь намногосложнее, так что применим аналогию.Коды Рида-Соломона основываются на том факте, что каждый многочлен n-й степени уникальным образом определяется n + 1 точкой.
Например, если линия задаетсяформулой ax + b, то восстановить ее можно по двум точкам. Дополнительные точки,лежащие на той же линии, излишни, но они полезны для исправления ошибок. Предположим, что две точки данных представляют линию. Мы отправляем по сети эти дветочки данных, а также еще две контрольные точки, лежащие на той же линии. Еслив значение одной из точек по пути закрадывается ошибка, то точки данных все равноможно восстановить, подогнав линию к полученным правильным точкам.
Три точкиокажутся на линии, а одна, ошибочная, будет лежать вне ее. Обнаружив правильноеположение линии, мы исправили ошибку.В действительности, коды Рида—Соломона определяются как многочлены наконечных полях. Для m-битовых символов длина кодового слова составляет 2m – 1символов. Очень часто выбирают значение m = 8, то есть одному символу соответствует один байт. Тогда длина кодового слова — 255 байт. Широко используется код(255,233), он добавляет 32 дополнительных символа к 233 символам данных.
Декодирование с исправлением ошибок выполняется при помощи алгоритма, разработанного Берлекэмпом и Мэсси, который эффективно осуществляет подгонку для кодовсредней длины (Massey, 1969).Коды Рида—Соломона широко применяются на практике благодаря хорошим возможностям по исправлению ошибок, особенно последовательных. Они используютсяв сетях DSL, в кабельных и спутниковых сетях, а также для исправления ошибок накомпакт-дисках, дисках DVD и Blu-ray. Поскольку работа идет на базе m-битных символов, однобитные ошибки и m-битные последовательные ошибки обрабатываютсяодинаково — как одна символьная ошибка. При добавлении 2t избыточных символовкод Рида—Соломона способен исправить до t ошибок в любом из переданных символов.
Это означает, например, что код (255,233) с 32 избыточными символами исправляет до 16 символьных ошибок. Так как символы могут быть последовательными, а размер их обычно составляет 8 бит, то возможно исправление последовательных ошибокв 128 битах.
Ситуация выглядит еще лучше, если модель ошибок связана с удалениемданных (например, царапина на компакт-диске, уничтожившая несколько символов).В таком случае возможно исправление до 2t ошибок.Коды Рида—Соломона часто используют в сочетании с другими кодами, напримерсверточными.
И вот почему. Сверточные коды эффективно обрабатывают изолированные однобитные ошибки, но с последовательностью ошибок они, скорее всего, несправятся, особенно если ошибок в полученном потоке бит слишком много. Добавиввнутрь сверточного кода код Рида—Соломона, вы сможете очистить поток бит от последовательностей ошибок. Таким образом, получившийся составной код обеспечитнадежную защиту как от одиночных, так и от массовых ошибок.3.2. Обнаружение и исправление ошибок 233Наконец, взглянем на код LDPC (Low-Density Parity Check, код с малой плотностью проверок на четность).
Коды LDPC — это линейные блочные коды, изобретенные Робертом Галлагером и описанные в его докторской диссертации (Gallagher,1962). Как и о большинстве других диссертаций, об этой вскоре позабыли. Однаков 1995 году, когда вычислительные мощности сделали огромный скачок вперед, представленный в ней код изобрели заново.В коде LDPC каждый выходной бит формируется из некоторого подмножествавходных бит. Это приводит нас к матричному представлению кода с низкой плотностью единиц — отсюда и название. Полученные кодовые слова декодируются алгоритмом аппроксимации, который последовательно улучшает наилучшее приближение,составленное из полученных данных, пока не получает допустимое кодовое слово.
Такосуществляется устранение ошибок.Коды LDPC удобно применять для блоков большого размера. Они превосходносправляются с ошибками — лучше, чем на практике удается многим другим кодам(включая те, с которыми мы уже познакомились). По этой причине коды LDPC быстро добавляются в новые протоколы. Они являются частью стандарта цифровоготелевидения, сетей Ethernet 10 Гбит/с, сетей, работающих по линиям электропитания,а также последней версии 802.11. Очевидно, что эти коды обязательно будут использоваться и в новых сетях, пока что находящихся на стадии разработки.3.2.2. Коды с обнаружением ошибокКоды с исправлением ошибок широко применяются в беспроводных системах связи, которые славятся зашумленностью среды передачи и, следовательно, большимколичеством ошибок по сравнению с системами на основе оптоволоконного кабеля.Передать что-либо, не используя исправление ошибок, было бы практически невозможно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
