Чиен поиск

В абстрактной алгебре , поиск Чиена названный в честь Роберта Тьенвена Чиена , представляет собой быстрый алгоритм определения корней многочленов , определенных над конечным полем . Поиск Чиена обычно используется для поиска корней полиномов локаторов ошибок, встречающихся при декодировании кодов Рида-Соломона и кодов БЧХ .

Алгоритм

Задача состоит в том, чтобы найти корни многочлена $Λ(x)$ (над конечным полем $GF(q)$ ): $\Lambda (x)=\lambda _{0}+\lambda _{1}x+\lambda _{2}x^{2}+\cdots +\lambda _{t}x^{t}$

Корни можно найти с помощью грубой силы: существует конечное число $x$ , поэтому полином можно вычислить для каждого элемента $x i$ . Если многочлен равен нулю, то этот элемент является корнем.

Для тривиального случая $x = 0$ только коэффициент $λ 0$ необходимо проверять на ноль . Ниже единственное беспокойство будет касаться ненулевого $x i$ .

Непосредственная оценка полинома включает $O (t 2)$ общие умножения и $O (t)$ сложения. Более эффективная схема могла бы использовать метод Хорнера для $общих умножений O (t)$ и $сложений O (t)$ . Оба этих подхода могут оценивать элементы конечного поля в любом порядке.

Поиск Чиена улучшает описанное выше, выбирая определенный порядок для ненулевых элементов. В частности, конечное поле имеет (постоянный) образующий элемент $α$ . Чиен проверяет элементы в порядке генератора $α. 1, а 2, а 3, ....$ . Следовательно, для поиска Чиена требуется только $O (t)$ умножений на константы и $O (t)$ сложений. Умножения на константы менее сложны, чем обычные умножения.

Поиск Чиена основан на двух наблюдениях:

Каждый ненулевой $\beta$ может быть выражено как $\alpha ^{i_{\beta }}$ для некоторых $i_{\beta }$ , где $\alpha$ является примитивным элементом $\mathrm {GF} (q)$ , $i_{\beta }$ - это число степени примитивного элемента $\alpha$ . Таким образом, полномочия $\alpha ^{i}$ для $0\leq i<(q-1)$ покрыть все поле (за исключением нулевого элемента).
Существует следующая связь: ${\begin{array}{lllllllllll}\Lambda (\alpha ^{i})&=&\lambda _{0}&+&\lambda _{1}(\alpha ^{i})&+&\lambda _{2}(\alpha ^{i})^{2}&+&\cdots &+&\lambda _{t}(\alpha ^{i})^{t}\\&\triangleq &\gamma _{0,i}&+&\gamma _{1,i}&+&\gamma _{2,i}&+&\cdots &+&\gamma _{t,i}\\\Lambda (\alpha ^{i+1})&=&\lambda _{0}&+&\lambda _{1}(\alpha ^{i+1})&+&\lambda _{2}(\alpha ^{i+1})^{2}&+&\cdots &+&\lambda _{t}(\alpha ^{i+1})^{t}\\&=&\lambda _{0}&+&\lambda _{1}(\alpha ^{i})\,\alpha &+&\lambda _{2}(\alpha ^{i})^{2}\,\alpha ^{2}&+&\cdots &+&\lambda _{t}(\alpha ^{i})^{t}\,\alpha ^{t}\\&=&\gamma _{0,i}&+&\gamma _{1,i}\,\alpha &+&\gamma _{2,i}\,\alpha ^{2}&+&\cdots &+&\gamma _{t,i}\,\alpha ^{t}\\&\triangleq &\gamma _{0,i+1}&+&\gamma _{1,i+1}&+&\gamma _{2,i+1}&+&\cdots &+&\gamma _{t,i+1}\end{array}}$

Другими словами, мы можем определить каждое $\Lambda (\alpha ^{i})$ как сумма набора слагаемых $\{\gamma _{j,i}\mid 0\leq j\leq t\}$ , из которого можно получить следующий набор коэффициентов следующим образом: $\gamma _{j,i+1}=\gamma _{j,i}\,\alpha ^{j}$

Таким образом, мы можем начать с $i=0$ с $\gamma _{j,0}=\lambda _{j}$ и перебирать каждое значение $i$ до $(q-1)$ . Если на каком-либо этапе результирующее суммирование равно нулю, т.е. $\sum _{j=0}^{t}\gamma _{j,i}=0,$ затем $\Lambda (\alpha ^{i})=0$ также, так $\alpha ^{i}$ является корнем. Таким образом мы проверяем каждый элемент в поле.

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

Ссылки

Чиен, RT (октябрь 1964 г.), «Процедуры циклического декодирования кодов Бозе-Чаудхури-Хоквенгема», IEEE Transactions on Information Theory , IT-10 (4): 357–363, doi : 10.1109/TIT.1964.1053699 , ISSN 0018- 9448
Лин, Шу; Костелло, Дэниел Дж. (2004), Кодирование контроля ошибок: основы и приложения (второе изд.), Энглвуд Клиффс, Нью-Джерси: Прентис-Холл, ISBN 978-0130426727
Гилл, Джон (nd), Примечания EE387 № 7, Раздаточный материал № 28 (PDF) , Стэнфордский университет, стр. 42–45, заархивировано из оригинала (PDF) 30 июня 2014 г. , получено 21 апреля 2010 г.