Алгоритм Форни

В теории кодирования алгоритм Форни (или алгоритм Форни ) вычисляет значения ошибок в известных местах ошибок. Он используется как один из этапов декодирования кодов BCH и кодов Рида – Соломона (подкласс кодов BCH). Джордж Дэвид Форни-младший . Алгоритм разработал

Процедура

Необходимо ввести терминологию и настройку...

Кодовые слова выглядят как полиномы. По задумке генераторный полином имеет последовательные корни α ^с , а ^{с +1} , ..., а ^{с + д -2} .

Синдромы

Полином местоположения ошибки

$\Lambda (x)=\prod _{i=1}^{\nu }(1-x\,X_{i})=1+\sum _{i=1}^{\nu }\lambda _{i}\,x^{i}$

Нули Λ( x ) равны X ₁ ⁻¹ , ..., Х _н ⁻¹ . Нули являются обратными местами ошибок. $X_{j}=\alpha ^{i_{j}}$.

Как только места ошибок станут известны, следующим шагом будет определение значений ошибок в этих местах. Значения ошибок затем используются для исправления полученных значений в этих местах для восстановления исходного кодового слова.

В более общем случае веса ошибок e _j можно определить путем решения линейной системы

$s_{0}=e_{1}\alpha ^{(c+0)\,i_{1}}+e_{2}\alpha ^{(c+0)\,i_{2}}+\cdots \,$

$s_{1}=e_{1}\alpha ^{(c+1)\,i_{1}}+e_{2}\alpha ^{(c+1)\,i_{2}}+\cdots \,$

$\cdots \,$

Однако существует более эффективный метод, известный как алгоритм Форни, основанный на интерполяции Лагранжа . Сначала вычислите полином оценщика ошибок.

$\Omega (x)=S(x)\,\Lambda (x){\pmod {x^{2t}}}\,$

Где S ( x ) — полином частичного синдрома:

$S(x)=s_{0}x^{0}+s_{1}x^{1}+s_{2}x^{2}+\cdots +s_{2t-1}x^{2t-1}.$

Затем оцените значения ошибок:

$e_{j}=-{\frac {X_{j}^{1-c}\,\Omega (X_{j}^{-1})}{\Lambda '(X_{j}^{-1})}}\,$

Значение c часто называют «первым последовательным корнем» или «fcr». Некоторые коды выбирают c = 1 , поэтому выражение упрощается до:

$e_{j}=-{\frac {\Omega (X_{j}^{-1})}{\Lambda '(X_{j}^{-1})}}$

Формальная производная

Основная статья: Формальная производная

Λ'( x ) является формальной производной полинома локатора ошибок Λ( x ):

$\Lambda '(x)=\sum _{i=1}^{\nu }i\,\cdot \,\lambda _{i}\,x^{i-1}$

Обратите внимание, что в приведенном выше выражении i — целое число, а λ _i будет элементом конечного поля. Оператор ⋅ представляет собой обычное умножение (повторяющееся сложение в конечном поле), которое совпадает с оператором умножения конечного поля, т.е.

$i\lambda =(1+\ldots +1)\lambda =\lambda +\ldots +\lambda .$

Например, в характеристике 2 $i\lambda =0,\lambda$ в зависимости от того, четный я или нечетный.

Вывод

Интерполяция Лагранжа

Гилл (nd , стр. 52–54) дает вывод алгоритма Форни.

Стирания

Определите полином локатора стирания

$\Gamma (x)=\prod (1-x\,\alpha ^{j_{i}})$

Где места стирания заданы j _i . Примените описанную выше процедуру, заменив Γ на Λ.

Если присутствуют и ошибки, и стирания, используйте полином локатора ошибок и стираний.

$\Psi (x)=\Lambda (x)\,\Gamma (x)$

См. также

• Код BCH
• Исправление ошибок Рида – Соломона

Ссылки

• Форни, Г. (октябрь 1965 г.), «О декодировании кодов BCH», IEEE Transactions on Information Theory , 11 (4): 549–557, doi : 10.1109/TIT.1965.1053825 , ISSN   0018-9448
• Гилл, Джон (nd), Примечания EE387 № 7, Раздаточный материал № 28 (PDF) , Стэнфордский университет, стр. 42–45, заархивировано из оригинала (PDF) 30 июня 2014 г. , получено 21 апреля 2010 г.
• У. Уэсли Петерсона Книга