У. Питерсон - Коды, исправляющие ошибки (1267328), страница 5
Текст из файла (страница 5)
Помимо того, что блоковые коды используются при решении задач теории связи, они находят применение также в нескольких других областях. Блоковые коды являются основой для распределения нагрузок при помощи переключательных матриц (47, 55, 203, 294), которые не только более эффективны, чем обычные системы адресов ячеек памяти, но и позволяют автоматически исправлять сбои отдельных компонент.
По математической структуре опи аналогичны некоторым планам статистических экспериментов 126, 183, 2001. Кроме того, предлагалось использовать эти коды в системах поиска документов [5Ц, для уплотнения данных 1161 и в специальных типах вычислительных машин. 1,5, Древовидные коды В отличие от блоковых кодов коды, рассматриваемые в этом разделе, не связаны с разбиением на блоки информационной последовательности и последующей независимой их обработкой. Напротив, при древовидном кодировании каждой информационной последовательности ставится в соответствие (возможно, полубесконечная) кодовая последовательность. Правила, устанавливающие это соответствие, проще всего описать посредством древовидного графа.
Пример двоичного древовидного графа приведен на фиг. 1.6. Вертикальные линии называются узлами, горизонтальные линии — ветвями. В общем случае каждая ветвь представляет собой д-ичную последовательность, состоящую из аю символов; из каждого узла выходит д" ветвей, где йв ( пм (Можно определить также деревья, у которых число символов последовательности, соответствующей каждой ветви, и число ветвей, выходящих из каждого узла, не постоянны, но они не играют значительной роли в теории кодирования.) Далее, при заданной информапионной последовательности древовидный граф следующим образом используется для определения кодовой последовательности. Во-первых, д-ичная информационная последовательность разбивается на блоки длины йм Затем первый блок используется для выбора в соответствии с некоторым предварительным указанным правилом одной из ветвей, выходящих из первого узла.
Аналогично второй информационный блок нь' йо используется для выбора в соответствии с тем же самым длины правилом Р илом одной из ветвей, выходящих нз второго узла, и т. д. ао оа О» 1а Оа ао О! а! 10 Веогнь 10 аннл 00 аа а! аа 01 а! !о !а аа о! ВибР ! г З О З 0 У 666!ва Фиг. 1.6. часть полубесконечного двоичного дерева для кода с тг='5~.
Жирная линия соответствует информационной последовательности ! 01 ! ООО ....) 11 о! !о 10 а- фиг. Кт. Кодер для древовилвого кода с кликой блока ле и скоростью Эв,~ло. Таким способом однозначно определяется путь по дереву. Совокупность наборов длины йо, определяемых выбранным путем, образует кодовую последовательность, сопоставляемую информационной последовательности. Скорость 1! такого кода равна Ао~ла. На фиг. 1.7 изображен кодер в общем виде для древовидного кода.
Пример Пусть на кодер поступает информационная последовательность 1 0 1 1 0 0 1 0 ... и используется двоичный древовидный код, изображенный на фиг. 1.6. Для этого кода д = 2, йо = 1, по = 2 и поэтому !г = О,б. Заданная последовательность определяет единственный путь по дереву, который выделен на фнг.
!.6. Соответствующая полубесконечная кодовая последовательность начинается символами 110111100100.. (Заметим, что информационному символу 0 на узле соответствует шаг вверх, а 1 — шаг вниз. Мы всегда будем придерживаться этого правила.) Здесь так же, как в случае блоковых кодов, декодирование за. ключается в выборе «наилучшей гипотезы» относительно того, какая именно кодовая последовательность в результате искажения шумом в канале могла привести к полученной последовательности.
Для того чтобы принять наилучшее возможное решение при декодировании, декодер блокового кода должен исследовать только п полученных символов. Однако благодаря природе древовидного кода теперь в распоряжении декодера для исследовании имеется очень длинная последовательность полученных символов. Чтобы для древовидного кода было применимо декодирование по методу максима ксимального правдоподобия, необходимо ввести определенные аг анич коде ом Раничення. Всюду дальше предполагается, что одновременно дедером может обрабатываться только фиксированное число и подпоследовательностей длины па полученной последовательности.
Величина тиг называется длиной кодового ограничения и обозначается через п. Предполагается также, что декодер не может возвращаться назад. Другими словами, после того как символ покидает декодер, он безвозвратно теряется. Так же, как и при кодировании, при декодировании древовидного кода за один раз обрабатывается одна ветвь (илн набор длины па). В определенный момент времени все предшествующие ветви уже декодированы, и декодер находится в определенном узле дерева. На основании и предыдущих символов, которые в нем содержатся, декодер должен принять решение относительно того, какая из д" ветвей, выходящих из данного узла, является правильной.
После того как выбор сделан, выдается информационный блок из йг символов, соответствующий выбранной ветви, и следующий блок из аа символов полученной последовательности поступает на декодер. Правила, которыми руководствуются в процессе принятия решения, определяются в основном структурой канала. Например, в случае двоичного симметричного канала хороший декодер выбирает ветвь, принадлежащую тому пути, расстояние Хэмминга которого от полученной последовательности является наименьшимм. Пример. Предположим, что во втором разряде полученной последовательности в предыдущем примере произошла ошибка.
Другими словами, пусть полученная последовательность имеет вид: 1 0 0 1 1 ! .... Возможные кодовые последовательности (пути) могут начинаться с О О О О..., О О 1 1 ..., ! 1 О 1 ..., 1 1 1 О .... Очевидно, третий путь, который отличается от полученной последовательности единственным символом, является наилучшим. Информационная последовательность для этого пути начинается с 1 О. Таким образом, единственная ошибка исправлена. Теперь предположим, что ошибка произошла во втором и третьем разрядах полученной последовательности. Ближайший путь должен начинаться с 0 0 1 1, и на выходе декодера должна появиться информационная последовательность, начинающаяся с 0 1, а не с 1 О, как в случае, если бы не было ошибок. Таким образом, декодер примет ошибочное решение.
В этом примере декодер исследует подпоследовательности длины 4 полученной последовательности. Этого достаточно для исправления единственной ошибки, но не двух. Разумно считать, что чем больше длина кодового ограничения, тем больше ошибок можно исправить. Для древовидных кодов такое утверждение обычно верно, однако в рассматриваемом примере это не так— комбинация из двух ошибок не может быть однозначно исправлена независимо от того, сколь большим выбрано и. Причиной этого является периодичность выбранного дерева.
(См.задачу 1.7.) и данной книге кодовым словом древовидного кода называется набор длины и, связанный с гп-й ветвью пути. При таком определении понятия минимального расстояния между кодовыми словами, таблицы декодирования и т. д., ранее введенные для блоках кодов, переносятся на случай древовидных кодов, хотя и не без некоторых изменений. древовидный код со скоростью г! = йс!п„для которого используется декодер, способный одновременно обрабатывать т ветвей, содержит дь' =де кодовых слов. Очевидно, что только дма =д„ возможных полученных слов следует рассматривать. Как и прежде, таблица декодирования содержит совокупность всех полученных слов, расположенных в да столбцах, в первой строке каждого нз которых стоит кодовое слово. Каждый столбец состоит из полученных слов, которые декодируются в кодовое слово, стоящее в первой строке столбца.
Однако в случае древовидного кода не имеет смысла делать различие мегкду кодовыми словами, па первых символов которых совпадают,— для этих да* слов на выходе декодера получается одинаковый результат. Таким образом, естественно сгруппировать столбцы таблицы декодирования в оь' подмножеств, первое из которых называется правильным подмножеством. !Остальные подмножества являются неправильными подмножествами.) Легко видеть, что каждое из этих подмножеств содержит дв-м столбцов. При декодировании требуется только определить, в какое подмножество входит полученное слово. Пример.
Код из предыдущего примера может быть декодирован с помощью декодера, обрабатывающего две ветви, Р!так, и = 4. Таблица декодирования для первого блока показана на фнг. 1.8. Из этой таблицы видно, что, если имеет место одна ошибка, декодирование дает правильный результат, поскольку каждое из четырех полученных при этом слов принадлежит тому же подмножеству, что и переданное кодовое слово, т.
е. правильному подмножеству, а две ошибки приводят к ошибкам при декодировании. Правильное ~ Неправильное 1 подмножество ~ подмножество Кодовыеслова 0000 0011ю 1101 1110 ! 1000 10111010! 0110 010О 0!!!' !00! 10!О пРини""""""" ! 0 0 ! 0 0 0 0 1 ' 01! 1!!! 1100 Реаультат 1 декодирования Ф иг. !.а.
Таб ~ого на фиг. !.б. аблица декодирования для двоичного древовидного кода, иаображен- Однако некоторые тройные ошибки будут исправлены при декодировании. Например, если передавалось кодовое слово 00 00 и получено слово 01 1 1, то на выходе декодера появится О, как и должно быть. Но эти ошибки приведут к неправильному декодированию второго блока, поскольку если не появилось дополнительных ошибок и третий переданный блок равен также 00, то полученным словом будет 1 1 0 О.
Это слово является ближайшим к кодовому слову 1 1 1 О, в результате чего вторым символом на выходе декодера будет 1 вместо О. Практическая применимость таблицы декодирования для древовидного кода оказывается до некоторой степени ограниченной, поскольку, вообще говоря, для каждого узла дерева может оказаться необходимой отдельная таблица. Читатель может заметить, например, что для древовидного кода, изображенного на фиг.
1.6, необходимы две различные таблицы. (См. задачу 1.6.) К счастью, для всех древовидных кодов, рассматриваемых в последующих главах, т. е, для сверточных или рекуррентных кодов, это различие несущественно и достаточно одной таблицы декодирования. Минимальное расстояние Хэмминга 0 для древовидного кода определяется как минимальное по всему дереву расстояние между кодовыми словами в различных подмножествах.
Вообще говоря, для древовидных кодов это не очень полезное понятие. Однако для важного подкласса сверточных кодов все узлы обладают одинаковыми свойствами, связанными с понятием расстояния. Так для этих кодов г! просто равно наименьшему расстоянию между кодовыми словами из различных подмножеств таблицы декодирования. В любом случае код может исправлять все ошибочные последовательности с ! или меньшим числом ошибок в любых т смежных блоках по аа символов тогда и только тогда, когда о ) 2! + 1. Кроме того, любая ошибочная последовательность с и' — 1 илн меньшим числом ошибок в т последовательных блоках будет обнаружена тогда и только тогда, когда минимальное кодовое расстояние равно д. 3адача определения вероятности правильного декодирования для древовидных кодов является значительно более трудной, чем для блоковых кодов. Для двоичного симметричного канала, например, операции последовательного декодирования слов блокового кода являются независимыми событиями, и нетрудно, по крайней мере теоретически, просуммировать вероятности по всем исправленным комбинациям ошибок.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
