포니 알고리즘

코딩 이론에서, Forney 알고리즘(또는 Forney의 알고리즘)은 알려진 오류 위치에서 오류 값을 계산한다.BCH 코드와 Reed-Solomon 코드(BCH 코드의 하위 클래스) 디코딩 단계 중 하나로 사용된다.George David Forney Jr.는 이 알고리즘을 개발했다.^[1]

절차

용어와 설정 도입 필요...

코드 단어들은 다항식처럼 보인다.설계상 발전기 다항식은 연속된 뿌리가^c α^c+1, α, ..., α이다^c+d−2.

신드롬

오류 위치 다항식^[2]

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

λ(x)의 0은 X₁⁻¹, ..., X이다_ν⁻¹. 0은 오류 위치 $X{\displaystyle {}_{}}$ ${\displaystyle j_{}}$= ${\displaystyle {}^{}}$ ${\displaystyle {i{}_{}}^{}}$ ${\displaystyle {j_{}}^{}}$ ${\$의 왕복선이다$.$

일단 오류 위치가 알려지면 다음 단계는 해당 위치에서 오류 값을 결정하는 것이다.그런 다음 오류 값을 사용하여 해당 위치에서 수신된 값을 수정하여 원래 코드 단어를 복구한다.

보다 일반적인 경우, 오류 가중치 e는_j 선형 시스템을 풀어서 결정할 수 있다.

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

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

$\displaystyle \cdots \,}$

그러나 라그랑주 보간법을 기반으로 하는 포니 알고리즘으로 알려진 보다 효율적인 방법이 있다.먼저 오류 평가자 다항식^[3] 계산

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

여기서 S(x)는 부분 증후군 다항식이다.^[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}\,\Oomega(X_{j}^{-1}){\Lambda '(X_{j}^{-1}}}}}}}}},}},}$

c 값은 흔히 "첫 번째 연속 루트" 또는 "fcr"로 불린다.일부 코드는 c = 1을 선택하므로 표현식은 다음과 같이 단순화된다.

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

형식파생상품

λ'(x)는 오류 로케이터 다항식 λ(x)의 공식 파생 모델이다.^[3]

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

위의 표현에서 나는 정수이며, λ은_i 유한장의 요소일 것이라는 점에 유의한다.연산자 ·는 유한장의 곱셈 연산자가 아닌, 통상적인 곱셈(한정된 장에 반복된 덧셈)을 나타낸다.

파생

라그랑주 보간법

Gill(n.d, 페이지 52–54)은 Forney 알고리즘의 파생어를 제공한다.

지우개

삭제 로케이터 다항식 정의

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

j가_i 삭제 위치를 제공하는 위치.위에서 설명한 절차를 적용하여 γ을 λ으로 대체한다.

오류와 지우기가 모두 있는 경우 오류 및 삭제 로케이터 다항식을 사용하십시오.

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

참고 항목

• BCH 코드
• 리드-솔로몬 오차 보정

참조

• Forney, G. (October 1965), "On Decoding BCH Codes", IEEE Transactions on Information Theory, 11 (4): 549–557, doi:10.1109/TIT.1965.1053825, ISSN 0018-9448
• Gill, John (n.d.), EE387 Notes #7, Handout #28 (PDF), Stanford University, pp. 42–45, archived from the original (PDF) on June 30, 2014, retrieved April 21, 2010
• W. 웨슬리 피터슨의 책