Морские информационно-управляющие системы Апрель 2016, № 9 | Seite 58

синдромного многочлена. На определенном шаге очередной символ уже не будет генерироваться. В этот момент нужно изменить регистр таким образом, чтобы он:

• правильно предсказывал следующий символ;

• не менял предсказание предыдущих символов;

• увеличивал длину регистра на минимально возможную величину.

Процесс вычисления продолжается до тех пор, пока не будут порождены первые 2t символов синдрома.

Алгоритм строится на основе итеративной процедуры. При каждой итерации должны сохраняться как многочлен связей Ʌ( x), так и добавка B( x). Для каждого нового члена S( x) предусматривается проверка правильности предсказания этого символа текущим многочленом связи. Если предсказание правильно, то многочлен связей не меняется, а добавка умножается на x. Если предсказание неверно( невязка ∆r ≠ 0), то изменяют текущий многочлен связей, прибавляя к нему добавку. После этого проверяют, увеличилась ли длина регистра. Если она не увеличилась, то текущую добавку оставляют без изменений. Если длина регистра возрастает, то лучшей добавкой считают предыдущий многочлен связей. Для недвоичных полей добавку нормируют, чтобы невязка стала равной 1. Далее

2t синдром

Приемник C( x) = f( x) + e( x)

Искаженные данные

Вычисление компонентов синдрома S j = C( α j) j = 1,..., 2t

Вычисление полинома локаторов ошибок( стираний)( x) с помощью алгоритма Берлекэмпа-Месси

Локаторы искажений

Нахождение корней полинома( x) по алгоритму Ченя

X l =( l = 1,..., v)

Начальные значения r = 0,( x) = 1, L = 0, B( x) = 1, Ω( x) = 0, A( x) = 1

Вычисление ошибки в следующем компоненте синдрома L ∆r = j · S r-j j = 0

Генерирует ли существующий регистр сдвига следующий компонент синдрома?

Надо ли увеличивать длину регистра? r ← r + 1

∆r = 0?

2L ≤ r-1?

Да, отводы обратной связи остаются без изменений

Нет, отводы обратной связи необходимо изменить

Вычисление нового многочлена связей, для которого ∆r = 0 M( x) =( x) + ∆r · х · B( x)

Нет( x) ← M( x)

Определение характера ошибки на основе алгоритма Форни

B( x) ← ∆ r

-1

· B( x)

( x) ← M( x) L ← r – L

Да

Сохранение прежнего регистра после нормализации Модификация регистра сдвига Изменение длины регистра

B( x) ← x · B( x)

Ω( x) = S( x) ·( x) ·( mod x 2t)

Многочлен значений ошибок, соответствующий r( x): Ω r( x) ← Ω r-1( x) + ∆r · A r-1( x)

L r – L r-1 = 0?

Да A r( x) ← x · A r-1( x)

Y l =

Ω( X l

-1

)

'( X l

-1

)

e l = Y l · X l

Нет

Вычисление новой добавки для Ω( x): A r( x) ← ∆ r

-1

· x · Ω r-1( x)

Рис. 1. Схема быстрого декодирования кодов Рида-Соломона Рис. 2. Алгоритм Берлекэмпа-Месси

56 Морские информационно-управляющие системы, 2016 / No. 1( 9)