Полином локатора ошибки
Полученный синдром описывает конфигурацию ошибки, но еще не говорит нам, какие именно символы полученного сообщения были искажены. Действительно, степень синдромного полинома, равная 2t, много меньше степени полинома сообщения, равной n, и межу их коэффициентами нет прямого соответствия. Полином, коэффициенты которого напрямую соответствуют коэффициентам искаженных символов, называется полиномом локатора ошибки и по общепринятому соглашению обозначается греческой буквой L (ламбда).
Если количество искаженных символов не превышает t, между синдромом и локатором ошибки существует следующее однозначное соответствие, выражаемое следующей формулой: НОД [xn – -1, E(x)] = L?(x) и вычисление локатора сводится к задаче нахождения наименьшего общего делителя, успешно решенной еще Евклидом и элементарно реализуемой как на программном, так и на аппаратном уровне. Правда, за простоту реализации нам приходиться расплачиваться производительностью, точнее непроизводительностью
данного алгоритма, и на практике обычно применяют более эффективный, но и более сложный для понимания алгоритм Берлекэмпа-Месси (Berlekamp-Massy), подробно описанный Кнутом во втором томе "Искусства программирования" (см. так же книгу "Теория и практика кодов, контролирующих ошибки" Блейхута) и сводящейся к задаче построения цепи регистров сдвига с линейной обратной связью и по сути своей являющегося разновидностью авторегрессионого фильтра, множители в векторах которого и задают полином L.
Декодер, построенный по такому алгоритму, требует не более 3t операций умножения в каждой из итерации, количество которых не превышает 2t. Таким образом, решение поставленной задачи укладывается всего в 6t2 операций умножения. Фактически, поиск локатора сводится к решению системы из 2t
уравнений — по одному уравнению на каждый символ синдрома, — c t неизвестными. Неизвестные члены и есть позиции искаженных символов в кодовом слове v. Легко увидетьвидеть, что если количество ошибок превышает t, то система уравнений становится неразрешима и восстановить разрушенную информацию в этом случае не представляется возможным.
Блок-схема алгоритма Берлекэмпа-Месси приведена на рис. 21.55, а его законченная программа реализация содержится в листинге 1.2.
Рис. 21.55. . 0x339 Структурная схема алгоритм Берлекэмпа-Месси