친 검색

추상 대수학에서 로버트 티엔웬 치엔의 이름을 딴 치엔 검색은 유한한 분야에 걸쳐 정의된 다항식의 뿌리를 결정하기 위한 빠른 알고리즘이다.Chien 검색은 일반적으로 Reed-Solomon 코드와 BCH 코드를 해독할 때 발생하는 오류 로케이터 다항식의 뿌리를 찾는 데 사용된다.

알고리즘.

문제는 다항식 λ(x)의 뿌리를 찾는 것이다(유한계 GF(q)를 넘어).

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

뿌리는 brute 힘으로 찾을 수 있다: x의 수가 한정되어 있기 때문에 각 원소 x에_i 대해 다항식을 평가할 수 있다. 다항식이 0으로 평가하면 그 원소는 뿌리가 된다.

사소한 경우 x = 0의 경우 계수 λ만₀ 0으로 테스트하면 된다.아래에서, 유일한 관심사는 0이 아닌_i x에 대한 것일 것이다.

다항식의 간단한 평가에는 O(t²) 일반 승수와 O(t) 추가가 포함된다.더 효율적인 계획은 O(t) 일반 승수와 O(t) 추가에 호너의 방법을 사용할 것이다.이 두 가지 접근법 모두 어떤 순서로든 유한 영역의 요소를 평가할 수 있다.

Chien 검색은 0이 아닌 원소에 대한 특정 순서를 선택하여 위에서 개선한다.특히 유한장은 (정수)발생원소 α를 가지고 있다.치엔은 발전기 순서 α¹, α², α³, ..의 원소를 시험한다.따라서, Chien 검색은 상수와 O(t) 추가에 의한 O(t) 곱하기만을 필요로 한다.상수에 의한 승수는 일반 승수에 비해 덜 복잡하다.

Chien 검색은 다음 두 가지 관찰을 기반으로 한다.

• Each non-zero ${\displaystyle \beta }$ may be expressed as ${\displaystyle \alpha ^{i_{\beta }}}$ for some ${\displaystyle i_{\beta }}$, where ${\displaystyle \alpha }$ is a primitive element of ${\displaystyle \mathrm {GF} (q)}$, ${\displaystyle i_{\beta }}$ is the p원시 원소의 적은 수 $\alpha {\displaystyle }$ ${\displaystyle \alpha }$따라서 < (- $){\displaystyle 0\leq$ i$<(q-1)}$에 대한 $\alpha {\displaystyle {}^{}}$ ${\displaystyle i^{}}$ ${\$는 전체 필드(0원소 제외)를 포괄한다.
• 다음과 같은 관계가 존재한다.

${\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 _ᆲ(\alpha ^{i+1})&, +&, \lambda _ᆳ(\alpha ^{i+1})^{2}&, +&, \cdots &, +&, \lambda _ᆵ(\alpha ^{i+1})^{t}\\&, =&, \lambda _{0}&, +&.심장;\lambda _ᆪ(\alpha ^{나는})\,\alpha&+&,\lambda _ᆫ(\alpha ^{나는})^{2}\,\alpha ^{2}&, +&, \cdots &, +&amp을 말한다.\lambda _{t}(\reason ^{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 {\displaystyle \mathrm{}}$(${\displaystyle {\alpha }^{}}$ i${\displaystyle {}^{}}$) ${\displaystyle \Lambda(\alpha ^{i})$를 {${\displaystyle {}_{}}$ ${\displaystyle j_{}}$, ${\displaystyle i_{}}$ ${\displaystyle 0{}_{}\mathrm{}}$ ${\displaystyle \le }$ ${\displaystyle j}$ ${\displaystyle \le }$ ${\displaystyle t\}}$ ${\displaystyle \{\gamma \{\j,i} 0\leq j\leq t$의 합으로 정의할$$ 수 있다.

${\displaystyle \cHB_{j,i+1}=\cHB_{j,i}\,\cHB ^{j}}}$

In this way, we may start at ${\displaystyle i=0}$ with ${\displaystyle \gamma _{j,0}=\lambda _{j}}$, and iterate through each value of ${\displaystyle i}$ up to ${\displaystyle (q-1)}$. If at any stage the resultant summation is zero, i.e.

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

그렇다면 $\alpha {\displaystyle \mathrm{}}$ i${\displaystyle {}^{}{}^{}}$ ${\displaystyle i^{}}$ )${\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle \Lambda(\alpha ^{i}=0})$도 마찬가지여서 $\alpha {\displaystyle {}^{}}$ ${\displaystyle i^{}}${\$displaystyle \alpha$^{$i}}$는 뿌리가 된다$$.이렇게 해서 현장의 모든 요소를 점검한다.

하드웨어에서 구현될 때, 이 접근법은 복잡성을 현저하게 감소시킨다. 모든 승수는 무차별적인 접근법에서와 같이 두 개의 변수가 아니라 하나의 변수와 하나의 상수로 구성되기 때문이다.

참조

• Chien, R. T. (October 1964), "Cyclic Decoding Procedures for the Bose-Chaudhuri-Hocquenghem Codes", IEEE Transactions on Information Theory, IT-10 (4): 357–363, doi:10.1109/TIT.1964.1053699, ISSN 0018-9448
• Lin, Shu; Costello, Daniel J. (2004), Error Control Coding: Fundamentals and Applications (second ed.), Englewood Cliffs, NJ: Prentice-Hall, ISBN 978-0130426727
• Gill, John (n.d.), EE387 Notes #7, Handout #28 (PDF), Stanford University, pp. 42–45, archived from the original (PDF) on 2014-06-30, retrieved April 21, 2010