Чиен поиск - Chien search

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

Алгоритм

Проблема состоит в том, чтобы найти корни многочлена Λ (Икс) (над конечным полем GF (q)):

${\displaystyle \ \Lambda (x)=\lambda _{0}+\lambda _{1}x+\lambda _{2}x^{2}+\cdots +\lambda _{t}x^{t}}$

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

Для тривиального случая Икс = 0, только коэффициент λ₀ нужно проверить на ноль. Ниже мы будем беспокоиться только о ненулевом Икс_я.

Прямое вычисление полинома включает О(т²) общие умножения и О(т) дополнения. Более эффективная схема будет использовать Метод Хорнера за О(т) общие умножения и О(т) дополнения. Оба этих подхода могут оценивать элементы конечного поля в любом порядке.

Поиск Chien улучшает вышеупомянутое, выбирая определенный порядок для ненулевых элементов. В частности, конечное поле имеет (постоянный) образующий элемент α. Чиен проверяет элементы в порядке генератора α¹, α², α³, ..... Следовательно, поиску Chien нужно только О(т) умножения на константы и О(т) дополнения. Умножение на константы менее сложное, чем обычное умножение.

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

• Каждый ненулевой ${\displaystyle \beta }$ может быть выражено как ${\displaystyle \alpha ^{i_{\beta }}}$ для некоторых ${\displaystyle i_{\beta }}$, куда ${\displaystyle \alpha }$ это примитивный элемент из ${\displaystyle \mathrm {GF} (q)}$, ${\displaystyle i_{\beta }}$ число степени примитивного элемента ${\displaystyle \alpha }$. Таким образом, полномочия ${\displaystyle \alpha ^{i}}$ за ${\displaystyle 0\leq i<(q-1)}$ покрыть все поле (исключая нулевой элемент).
• Существуют следующие отношения:

${\displaystyle {\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}}}$

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

${\displaystyle \ \gamma _{j,i+1}=\gamma _{j,i}\,\alpha ^{j}}$

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

${\displaystyle \ \sum _{j=0}^{t}\gamma _{j,i}=0,}$

тогда ${\displaystyle \Lambda (\alpha ^{i})=0}$ также так ${\displaystyle \alpha ^{i}}$ это корень. Таким образом мы проверяем каждый элемент в поле.

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

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

• Чиен, Р. Т. (октябрь 1964 г.), "Процедуры циклического декодирования для кодов Бозе-Чаудхури-Хоквенгема", IEEE Transactions по теории информации, ИТ-10 (4): 357–363, Дои:10.1109 / TIT.1964.1053699, ISSN  0018-9448
• Линь, Шу; Костелло, Дэниел Дж. (2004), Кодирование с контролем ошибок: основы и приложения (второе изд.), Englewood Cliffs, NJ: Prentice-Hall, ISBN  978-0130426727
• Джилл, Джон (нет данных), EE387 Заметки № 7, Раздаточный материал № 28 (PDF), Стэнфордский университет, стр. 42–45, заархивировано оригинал (PDF) на 2014-06-30, получено 21 апреля, 2010