У. Питерсон - Коды, исправляющие ошибки (1267328), страница 91
Текст из файла (страница 91)
Блок с номером О принятого слова декодируется в блок с номером О ближайшего кодового слова. Поскольку для декодирования и» символов требуется !!ь действий, эта систематическая поисковая процедура декодирования по максимуму правдоподобия может быть применена лишь к коротким кодам и кодам с низкими скоростями. Несколько более длинные коды можно декодировать с использованием метода Витерби (312). Рассмотрим сверточный код со скоростью Цп» и основной блоковой длиной' и». Пусть длина кодового ограничения обозначена через и, = т„,п», и пусть й,, = пг,йр— количество информационных символов на длине кодового ограничения. В дереве, соответствующем коду, набор длины й„который! должен быть закодирован, определяет один из д"» путей по дереву, содержащий т, ветвей.
Из каждой вершины дерева исходят д» ветвей, каждой ветви сопоставлен набор длины и». Пусть а», аь ... — входная информационная последовательность, а!— набор длины й» из элементов поля 6Р(д). Пусть через с = с»» с»! ... с»( с, =см св ... с,(,1, с»=с!,с»...с » е ! (» е-!)» (» е-!)! ' (» е !)(», !1 обозначены !у кодовых слов длины п соответствующих путям дерева. Символом см обозначен д-ичный набор длины и». Декодер вычисляет для принятой последовательности г = ь = г»г, ...
!! ' значений расстояния »!»- ! »((с!, г)= Х г((с!и г!), !'=О, 1, ..., !у» — 1, (13.12) где г! — д-ичный набор длины п». Обычно в качестве расстояния берется расстояние Хзмминга, хотя можно использовать и другие метрики. Сравниваются расстояния, соответствующие д» путям, для которых равны последние гп,— 1 информационных блоков нь ам ..., а ь Путь с наименьшим расстоянием называется вы. жившим. В этом и состоит первый этап декодирования, На втором этапе вычисляются расстояния между принятой последовательностью г и д~ паборамн длины лч(т+ 1), образовав- ными удлинением на одну ветвь каждого выжившего пути. Снова сравниваются расстояния, соответствующие дм путям, для которых последние т,— 1 информационных блоков совпадают„и для каждого случая называется выжившим путь, наиболее близкий к принятой последовательности.
На каждом этапе этой процедуры выполняется д ~ действий. Декодер должен хранить информационные последовательности„ ь-ь соответствующие д ° ' выжившим путям, и расстояния для этих путей. Пусть через т обозначено количество ветвей, которые должен хранить декодер, и пусть и = тп,. Обычно и, ограничение длины при декодировании, в несколько раз больше, чем длина кодового ограничения. На (т — и, + 1)-м этапе рассматриваются пути длины т и до предела используются возможности памяти декодера. Теперь, если все д ~ а выживших путей имеют одинаковые информационные символы в блоке О, то блок декодируется в эти символы.
Если же согласованй не все выжившие пути, то декодер либо обнаруживает ошибку, либо некоторым способом, например голосованием по большинству выживших путей, угадывает значепне а,. После декодирования, если ошибки исправлены, значения расстояний для выживших путей должны быть уменьшены на количество исправленных ошибок. Деревья, соответствующие сверточному коду, являютпя периодическими; это было использовано Форин (92] для построения упрощенной диаграммы, названной решеткои. Схема кодера сверточного кода с й ячейками, показанная на фиг.
13.2, содержит (и, — 1)йз = А, — Аа внутренних элементов памяти и, следовательно, д(' '1~' состояний. Произвольный набор длины й, на входе изменяет состояние этого линейного автомата с конечным числом состояний, иа выходе которого появляется набор длины пь Решетчатая диаграмма графически представляет последовательность внутренних состояний и выходов при всевозможных входных последовательностях. Пример. Двоичный систематический сверточный (12,6)-код с порождающей матрицей 11 01 00 01 00 01 11 01 00 01 00 11 01 00 01 11 01 00 11 01 11 (13.
И) ,рнг. !ЗЛЫ Кодер несистематического сверточного кода с А ячейками ,'(О! = ! + И+ и да !О! = ! + Оа. имеет расстояние Хзмминга 5. Сложение строк с номерами ! и 1+ 2, ! = 1, 2, 3, 4, дает матрицу 11 01 11 00 00 ОО 11 01 11 00 00 11 01 11 00 11 01 11 !1 О! 11 которая порождает эквивалентный несистематический код с и, = 6.
При и) 12 он исправляет все комбинации веса 2, а при и !О некоторые двойные ошибки не исправляются. Для этого кода д1 (Р) = 1 + Р + Ра, да(Р) = 1 + Ра, т. е. д = 1 1 О 1 1 1 О О .... Схема кодера для этого кода дана на фиг. !3.!1, а его решетчатая диаграмма — на фнг. 13.12. Первоначальное состояние кодера 00. Когда в регистр поступает символ О, состояние кодера изменяется, как показано сплошной линией; при поступлении символа 1 состояние меняется в соответствии с пунктирной линией.
Выходной набор длины ло = 2 при соответствующих комбинациях входа и состояния указан на ветвях решетки. Пусть передается нулевая последовательность, а на выходе принимается последовательность 1 1, 0 О, 0 О, .... Декодирование с использованием алгоритма Витерби состоит в нахождении 2а-а'= выживших путей для каждой вершины дерева, приведенного на фиг.
13.13. На фиг. 13.14 изображена соответствующая решетчатая диаграмма. После девятого шага все выжившие пути начинаются с 00; следовательно, первый блок декодируется правильно, и исправляются две ошибки. Для кода из приведенного примера требуется ограничение длины при декодировании, равное 22 символам, чтобы исправить комбинацию ошибок ! 100 ..., хотя на самом деле эта длина достаточна, чтобы исправить все комбинации из двух ошибок.
Вообще 00 1а риг. 13.12. Решетчатая диаграмма для кода с порождающими миогочлеиами и, (В) = 1+ В+ Вв, ив 1В) = 1+ Р'. -О нв входе. "— — — 1 нв входе. аеа„, оо '~11 ао оа 11 оо а! 00 оа Ях их оо оа !1х оа 11х 00 Ях 1х 11х [Я [41 [б] М И 01 оо а Ю ю ! х !Ох о1 х а1к о!к ОО 10 х ох юх юк а1 х 01 0!к йес Хэлопинеп йлп пупш,нопйплее Б и цвплейнпгп оп прпвильнпго 6 7 7 6 Фиг. 13.!н. Йерево декодера Витерби при исправлении двух ошибок (Л= ! 1О 1110 ...1 10 11 01х !1 !Ох Эпгпн [13 И ок о! о! оо ю оа ю о! 11 Оа !о х 1!к ох 'а! Оа [а и 1! 01 Оа„ юх ю ох 01х аак Фиг.
43.14, Решетчатая диаграмма декодера Витерби при цспраалеиик комбинации ошибок 11ООО..., д 110111ОО.... для кодов со скоростью 1т = 0,5 ограничение длины при декодировании, превышающее в 3 — 4 раза длину кодового ограничения, достаточно для исправления всех комбинаций ошибок с весами, меньшими чем Ы/2, Поскольку никакой обратной связи здесь нет, декодер Витерби является дефинитным и в нем не происходит размножения ошибок, Пусть К вЂ” число запоминающих устройств, содержащихся в кодере.
В двоичном случае для запоминания выживших путей декодер Витерби должен хранить К2к двоичных символов, а для определения расстояний необходимо несколько меньше чем 2к(оа,п двоичных символов. Кроме того, па каждом этапе декодирования должно быть проделано 2к действий. Поэтому ясно, что следует делать К столь малым, сколь это возможно для данного кода. Для кодов с Н: 0,5 удобнее использовать кодеры с А ячейками. Как отмечалось в предыдущем примере, обычно длина кодового ограничения для несистематического кода значительно меньше, чем для эквивалентного систематического кода [93), поэтому для таких и несколько больших скоростей следует использовать несистематические коды.
Если имеется систематический код с высокой скоростью передачи, то можно применить кодер с л — й ячейками, что приведет к декодеру с минимальной памятью. Сверточный код с длиной кодового ограничения л, = лет, и ограничением длины при декодировании в = пст « л, является пространством строк матрицы б из равенства (13.1), где б = б,„,~, = ... = б , = О. Пусть через а„ обозначено минимальное расстояние кода. При фиксированных бь 1 = О, 1, ..., т, — 1, где б.; = 0 для 1«т„увеличением т может быть получена последовательность кодов.
Величина 11ш д„=д„ (13,14) называется свободным расстоянием последовательности кодов или, проще, свободным расстоянием кода. Пример. Увеличение с ростом т минимального расстояний кода, рассмотренного в предыдущем примере„у которого д = = 11011100 ..., показано ниже: т пд„ 3 6 3 4 3 4 5 104 «6 «12 5 гаким образом, для этого кода а„ = 5, 'и 6 Фиг. 13.1З.
Диаграмма состояний (а) и модифицированная диаграмма состояний (б) для кода, иороятдаемого последовательностью и= 1 101 1100..., а, б-состоянне кодере; — — — ! нв входе; -' — О нв вводе. Для алгоритма декодирования Витерби свободное расстояние имеет важное значение, так как сложность декодера слабо зависит от длины ограничения при декодировании, а вероятность ошибки сильно зависит от свободного расстояния.
Свободное расстояние, количество кодовых слов данного веса и некоторые другие характеристики кода можно довольно просто найти из диаграммы состояний кодера. Эта диаграмма содержит д ' вершин, которые соответствуют состояниям кодера, и да ориентированных ветвей, исходящих из каждой вершины. т)-ичный набор длины ло изменяет состояние кодера и приводит к появлению на его выходе набора длины ло. Каждой ветви диаграммы состояний ставится в соответствие набор длины ло на выходе и набор длины йо на входе. Диаграмма состояний для кода из предыдущих примеров приведена на фиг. 13.!5, а. Произвольное ненулевое кодовое слово соответствует замкнутому пути, начинающемуся и кончающемуся в вершине О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
