Алгоритм Форни - Forney algorithm

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

Процедура

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

Кодовые слова выглядят как полиномы. По замыслу порождающий полином имеет последовательные корни α^c, α^c+1, ..., α^c+d−2.

Синдромы

Многочлен определения места ошибки^[2]

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

Нули Λ (Икс) находятся Икс₁⁻¹, ..., Икс_ν⁻¹. Нули - это обратные значения местоположений ошибок. ${\displaystyle X_{j}=\alpha ^{i_{j}}}$.

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

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

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

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

${\displaystyle \cdots \,}$

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

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

Где S(Икс) - полином частичного синдрома:^[4]

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

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

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

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

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

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

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

Λ '(Икс) это формальная производная полинома локатора ошибок Λ (Икс):^[3]

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

В приведенном выше выражении обратите внимание, что я - целое число, а λ_я был бы элементом конечного поля. Оператор · представляет собой обычное умножение (повторное сложение в конечном поле), а не оператор умножения конечного поля.

Вывод

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

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

Стирания

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

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

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

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

${\displaystyle \Psi (x)=\Lambda (x)\,\Gamma (x)}$

Смотрите также

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

Рекомендации

1. Форни 1965
2. Гилл н.д., п. 24
3. Гилл н.д., п. 47
4. Гилл (без даты., п. 48)

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

внешняя ссылка