Меркулов В.И., Дрогалин В.В. Авиационные системы радиоуправления. Том 3 (2004) (1151999), страница 15
Текст из файла (страница 15)
В этой роли элементы поля называются локаторами и обозначаются Хг=а'. Полагаем, что известны длина п=ц -1 кода для некоторого ш, число 1 ошибок, которые необходимо исправить„и количество Ч элементов поля Галуа ОР(Ч). Синдромный многочлен 3(х), используемый для декодирования принятого кода, представляет собой остаток от деления многочлена т(х) на порождающий многочлен я(х) Я(х)=Ка(х)[ч(х)]=К (х)1с(х)+е(х)]=К (х)1е(х)].
(19.11) Предположим далее, что на самом деле произошло к ошибок, 0<к>1 и что этим ошибкам соответствуют неизвестные позиции )ь 1п ..., ',. Тогда многочлен ошибок можно записать в виде: е(х)=ецх' +ецх' +...+е;„х'", (19.12) где ея- величина 1-й ошибки (в двоичном случае е,г1). Обратим внимание на то, что неизвестны не только п...)„и еп...е;„, но и число к. Для исправления ошибок нужно вычислить все эти числа. Чтобы получить)- ю компоненту синдрома (19.11), надо найти значение принятого много- члена т(х) в точке а'.
3)=у(а))=с(а')+е(а )=е(а'), 1=2,2с, э)=е11(ап)1+е12(а"))+...+е;,(а ")'. (19.13) Для сокращения записи введем новые обозначения. Определим для всех ! = 1, ч величины ошибок У~=ел и локаторы ошибок Х~=а', где 4 — элемент поля, отождествляемый с этим положением. Поскольку порядок элемента а равен п>т, то все локаторы рассматриваемой конфигурации ошибок различны. На основе (19.13) получим следующую систему из 21 уравнений относительно т неизвестных локаторов Хь..Х„и т неизвестных величин ошибок т'ь..., т'„. 81 У1Х1+У2Х2+- +У Х Я;-У1Х1'+У2Х2'+...+У,Х„', (19.14) 82~=У1Х1 '+У2Х2 '+...+У„Х„'.
22 Для вычисления неизвестных по заданным компонентам синдрома необходимо решить систему нелинейных уравнений (19.14). Однако эту систему трудно решать непосредственно, поэтому пользуются искусственным приемом, определив некоторые промежуточные переменные, по которьпи можно вычислить затем локаторы ошибок (14). Для этого вводится многочлен от Х Л(х)=Л„Х'+Л„!Х" ~+...+Л!Х+1, (19.15) известный под названием многочлена локаторов ошибок и определяемый как многочлен, корнями которого являются обратные к локаторам ошибок величины Х!' для 1=1,...,т . Если коэффициенты многочлена (19.15) известны, то для вычисления локаторов ошибок нужно найти его корни.
Можно показать (32), что существует система линейных уравнений, связывающих компоненты синдрома с коэффициентами миогочлена Л(Х). Эта система уравнений имеет вид 8ч+! 8ч+2 8ч+3 8, 82 8, ... 8ч, 8„ 82 83 84 8ч 8чы 83 84 85 8~ч.! 8ч+2 Лч л,, Лч-2 (19.16) 8ч 8ч+1 8ч+2 82ч-2 82ч-! л, 82» 73 Если матрица, составленная из компонент синдрома 8; с индексами от 1 до 2ч-1, невырожденная, то систему (19.16) можно решить путем обращения матрицы. Решение данной системы представляет определенные трудности, так как, во-первых, число ч неизвестно, а вовторых, при больших значениях ч для обращения матрицы размера тхч необходимо произвести порядка ч' действий. Поэтому был разработан специальный итерационный метод, позволяющий существенно упростить связанные с нахождением вектора Л вычисления, хотя сама процедура вычислений становится сложнее в понимании, чем простое обращение матрицы.
При разработке Берлекэмпом [13) указанного метода задача обращения матрицы была переформулирована в задачу построения системы с использованием регистров сдвига с линейной обратной связью. Предположим, что вектор Л известен. Тогда первая строка системы (19.16) определяет значение 8,! через значения 8ь8м...,8 вторая строка определяет 8„! через 8ь83,,,.,8, ! и т.д. Этот последовательный процесс описывается уравнением Б) = — ~„Л!Б) !, )=ч+1,...,2з. (19.17) Для фиксированного Л уравнение (19.17) приводит к авторегрессионному -Л, -Л, .
-Л„, -Л, фильтру, относящемуся к ...Бз,Б2,Б клас у ре«урр нтных. Он 3 2' ! может быть реализован как 1-У регистр сдвига с линейной обратной связью, множитеРис. 19.16 ли в отводах которого задаются вектором Л. Пере- формулированная таким образом задача сводится к построению изображенного на рис. !9.16 регистра сдвига с линейной обратной связью, генерирующего известную последовательность компонент синдрома. Задача состоит в том (13, 14), чтобы среди большого числа таких регистров найти регистр сдвига с наименьшей длиной. Это позволит определить вектор ошибок минимального веса в принятом слове, или, что то же самое, определить многочлен Л(Х) наименьшей степени. Процедура построения авторегрессионного фильтра является также методом решения матричного уравнения (19.16) относительного вектора Л Рассмотрим основные положения алгоритма Берлекэмпа.
Вначале находится самый короткий регистр сдвига, порождающий Яз и Я!. Далее проверяется, порождает ли этот регистр также Зь Если порождает, то этот регистр по-прежнему остается наилучшим решением, и нужно продолжать проверять, порождает ли он следующие символы синдрома. На каком-то шаге очередной символ уже не будет порождаться. В этот момент времени нужно изменить регистр таким образом, чтобы он правильно предсказывал следующий символ, не меняя предсказание предыдущих символов и увеличивал длину регистра на минимально возможную величину.
Этот процесс нужно продолжать до тех пор, пока не будут порождены первые 2! символов синдрома. Теперь можно дать формальное описание алгоритма Берлекэмпа, предварительно введя следующие обозначения: л — номер шага в алгоритме; ч„— степень полинома Л„(х)=Л„х +Л„!х +...+Л„!хьЛ„я, характеризующего многочлен связей при п-ой итерации; ܄— длина соответствующего регистра сдвига; )г„— положение старшего символа регистра сдвига, изменяющегося в момент появления ошибки сдвига; 0„— добавка на и-ом шаге к многочлену полинома локатора.
В качестве начальных условий принимают о=О; 1со=1. Ь0=0; Ла(х)=Лс,о=1; (зо(х)=х. В соответствии с итерационным алгоритмом Берлекэмпа необходимо [52]: 74 Ь Увеличить и на единицу; » 2. Вычислить невязку по формуле б„= ~~1Л„1„8» 1, а также ыо много»лен Ль(х)=Л„.1-4 0„.1(х); 3. Оценить величину и: если и=21, то перейти к п.7, при и л1 — к п.4; Ьп и если И„= О, 4. Принять Ь„= шах(Ь„1п-1-к„1), еслиб„еО; 5.
Вычислить 1Э„(х) и к„в зависимости от выпсвнения следующих условий: если1 =Ь„.ь то 0„(х)=х(З„.1(х); )с„=к 1; если Ь„>Ь„1, то О„(х)=хЛ,,1(х)Я„; 1с„=п-1-Ь„-1; б. Вернуться к п. П 7. Закончить вычисления при условии, что искомый полинам есть Л(х)=Ли(х). После получения полинома локаторов ошибок Л(х) необходимо найти корни многочлена Л(х). Простейшим способом отыскания этих корней в случае, когда число элементов поля конечно, является метод проб и ошибок, известный как процедура Ченя, состоящая в последовательном вычислении Л(а') для каждого ) и проверке полученных значений на равенство нулю. Наиболее простой способ вычисления значения Л(х) в точке 1) дает схема Горнера: Лф)=(...(((Л»~)+Л» 1)+Л» з)Р+Л» з)~3+".+Ло) (19 18) Процедура декодирования для двоичных кодов на этом заканчивается, так как для исправления ч(х) достаточно лишь указать наличие или отсутствие ошибки в каждой позиции.
Однако для недвоичных кодов, например, кодов Рида-Соломона, следует еще определить значение ошибок. Для этого обратимся к уравнениям (19.14), определяющим компоненты синдрома 81...8з» Поскольку локаторы ошибок известны, то получается система из 21 линейных уравнений с» неизвестными значениями ошибок. Первые » уравнений могут быть решены относительно значений ошибок, так как определитель матрицы коэффициентов этих уравнений не равен нулю, но для этого требуется обратить матрицу размером»хч. Обращение матрицы можно обойти, если воспользоваться процедурой, носящей название алгоритма Форин.
Определим многочлен значений ошибок 1е(х)=Б(х)Л(х) (шос(21). (19.19) Его связь с локаторами и значениями ошибок устанавливается формулой [13): (19.20) е<(х) = ,">„У Х, П(1 - Хе" ) . ьч ка Уравнение (19.19) является «ключем» к решению задачи декодирования и обычно называется ключевым уравнением. Значение ошибок получается из равенства (алгоритм Форин) х а(х ) а(х-,') П(1 — Х1Х-,') Л'(Х-,') лн (19.21) У Вычисление Реыение ключевого НРйьнения СИНДРОМй з<х> *<к> = >2<к> ее РЕЫЕНИЕ НРйВНЕНИЙ локйтойов А<к>=О <нйкожаение ЕЕ ПОЗИЦИЙ ОЫИБОК> РЕЬ>ЕНИЕ СИСТЕМЫ ЛИНЕйнык ВРЙВНЕНИЙ <ВЫЧИСЛЕНИЕ Ем ЗНЛЧЕНИЙ ОЫИБОК> ПЕРВИЧНЫЙ код извлечение СООБЫЕНИЯ ЗЛДЕРЖКй КОРРЕКЦИЯ Рис.
19.17 Алгоритм Форин обладает существенным преимуществом перед обращением матрицы, но использует деление, хотя возможны решения, нсключаюшие деление. Нахождение многочлена ошибок может выполняться согласно (19.!9) после вычисления полиномов З(х) и Л(х), либо это может осуществляться аналогично процедуре определения многочлена Л(х). Так, для решения ключевого уравнения (19.19) разработан метод ТренчаБерлекэмпа-Месси (ТБМ) (52], позволяюший по Зь З>,...Зв синдромного полинома З(х)=З><ха ~+...+З,к+3< одновременно найти полиномы Л(х) и Й(х) в рамках одной процедуры. Далее по найденным полнномам Л(х) и й(х) определяются позиции ошибок и значения ошибок.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
