Изучение методов помехоустойчивого кодирования и декодирования информации с помощью циклических блочных кодов Боуза-Чоудхури-Хоквингвема, страница 4

, где  - количество произошедших ошибок;  и перестраивает свою структуру в зависимости от возможной ошибки в структуре формируемого сигнала.

Рис. 1

Для нахождения полинома локатора ошибок используется итерационная процедура. На каждой итерации вычисляется модель регистра с обратными связями, генерирующего первые r компонентов синдрома, где r – номер этапа. Длина регистра на r-м этапе обозначается . На r-м этапе оценка  r-й компоненты синдрома равна:

, где - весовые коэффициенты на -м предыдущем этапе.

Ошибка (невязка) вычислений  определяется как

.

Если , то параметры модели не меняются

.

Если , то параметры модели меняются по правилу

, где  - веса;  - некоторое целое число;  - элемент поля.

Новая невязка может быть вычислена как 

.

Определим величины  так, чтобы новая невязка была равна нулю. Выберем следующие значения  так, чтобы  и . После подстановки получаем, что . В этом случае новая модель регистра сдвига будет генерировать последовательность . Если выберем , то получим регистр с обратной связью минимальной длины.

Теорема Берлекэмпа –Месси. Пусть заданы компоненты синдрома  из некоторого поля, тогда при начальных условиях ; ;  выполняются следующие рекуррентные равенства, использующиеся для вычисления :                             1.          ;

2.  ;

3. ,

где  и   .

При выполнении таких условий полином  является многочленом наименьшей степени, коэффициенты которого удовлетворяют равенству

, где    .

Граф-схема алгоритма Берлекэмпа–Месси приведена на рис. 2. 

Процедура Ченя. Для вычисления инверсии корней полинома ошибок удобно  использовать следующий алгоритм. Воспользуемся тем свойством, что сумма только в том случае, если символ, располагающийся на -й позиции оказывается ошибочным. Если определить , тогда , а . В итоге получается простая переборная схема вычислителя корней (рис.3).

Рис. 3

Алгоритм Форни.Позволяет оценить величины ошибок . Известно, что  =. Полином локатора ошибок имеет вид =, где  - корни полинома. Составим ключевое уравнение . Если в ключевое уравнение подставить выражения для S(x), s(x) и решить его относительно , то получим оценку величины ошибки:

 , где  - формальная производная полинома.

Пример. Троичный БЧХ-код (7, 3) формируется над полем , , для которого ; ; ; ; ; ; . Порождающий полином имеет вид

.

Предположим, что на вход декодера поступает сигнал

, компоненты синдрома ошибок равны  ;  ;  ;  .

Алгоритм Берлекэмпа–Месси вычисляет полином локатора ошибок:

,   , который имеет следующие корни: , . Тогда номера позиций ошибок определятся как 3 и 5. Ключевое уравнение запишется как

Откуда

;

; .

Оценка вектора ошибки равна . Оценка кодового слова равна: .

2.4. Нумератор весов кода

Рассмотрим весовые характеристические функции линейного кода, содержащие полную информацию о структуре кода. Используются каналы, вносящие независимые ошибки в передаваемые символы с вероятностью p₀ . Безошибочно символы принимаются с вероятностью (1 – p₀).

Пусть задан линейный -код, символы которого принадлежат q-ичному множеству из , и пусть этот код содержит  векторов веса i. Тогда совокупность чисел  называют распределением весов, а многочлен  называют характеристической функцией или нумератором весов кода C. На рис. 4 приведено распределение нумераторов веса для кода БЧХ.

Рис. 4  

Если выполняется неравенство 2t + 1 £ d_min и декодер исправляет все конфигурации ошибок, вес которых не превышает t, то вероятность ошибочного декодирования равна

, где N(l, h, s) – число конфигураций ошибок веса h, находящихся на расстоянии s от кодового слова веса l.