ในทฤษฎีการเข้ารหัสอัลกอริทึมของฟอร์นีย์ (หรืออัลกอริทึมของฟอร์นีย์ ) คำนวณค่าข้อผิดพลาดที่ตำแหน่งข้อผิดพลาดที่ทราบแล้ว อัลกอริทึมนี้ใช้เป็นหนึ่งในขั้นตอนในการถอดรหัสBCHและรหัสรีด-โซโลมอน (ซึ่งเป็นรหัสย่อยของ BCH) จอร์จ เดวิด ฟอร์นีย์ จูเนียร์พัฒนาอัลกอริทึมนี้ในปี 1965 ^{[ 1 ]}

จำเป็นต้องแนะนำคำศัพท์และวิธีการตั้งค่า...

รหัสคำมีลักษณะคล้ายพหุนาม โดยตามการออกแบบ พหุนามตัวสร้างจะมีรากที่เรียงลำดับกันคือ α c ^, α ^{c +1} , ..., α ^{c + d −2}

กลุ่มอาการ

พหุนามตำแหน่งข้อผิดพลาด^{[ 2 ]}

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

ค่าศูนย์ของ Λ( x ) คือX ₁ ⁻¹ , ..., X _ν ⁻¹ค่าศูนย์เหล่านี้คือส่วนกลับของตำแหน่งข้อผิดพลาด ${\displaystyle X_{j}=\alpha ^{i_{j}}}$

เมื่อทราบตำแหน่งของข้อผิดพลาดแล้ว ขั้นตอนต่อไปคือการกำหนดค่าข้อผิดพลาด ณ ตำแหน่งเหล่านั้น จากนั้นจะนำค่าข้อผิดพลาดเหล่านั้นไปแก้ไขค่าที่ได้รับ ณ ตำแหน่งเหล่านั้น เพื่อกู้คืนรหัสคำเดิม

ในกรณีทั่วไป น้ำหนักความคลาดเคลื่อนe _jสามารถกำหนดได้โดยการแก้ระบบสมการเชิงเส้น

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

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

${\displaystyle \cdots \,}$

อย่างไรก็ตาม มีวิธีการที่มีประสิทธิภาพมากกว่าที่เรียกว่าอัลกอริทึม Forney ซึ่งอิงตามการแทรกสอดแบบ Lagrangeก่อนอื่นให้คำนวณพหุนามตัวประเมินข้อผิดพลาด^{[ 3 ]}

${\displaystyle \Omega (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}\,\Omega (X_{j}^{-1})}{\Lambda '(X_{j}^{-1})}}\,}$

ค่าcมักเรียกว่า "รากที่ต่อเนื่องตัวแรก" หรือ "fcr" บางโปรแกรมเลือกc = 1ดังนั้นนิพจน์จึงลดรูปเหลือดังนี้:

${\displaystyle e_{j}=-{\frac {\Omega (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เป็นจำนวนเต็มและ λ _iจะเป็นองค์ประกอบของฟิลด์จำกัดตัวดำเนินการ ⋅ แทนการคูณแบบธรรมดา (การบวกซ้ำๆ ในฟิลด์จำกัด) ซึ่งเหมือนกับตัวดำเนินการคูณ ของฟิลด์จำกัด นั่นคือ

${\displaystyle i\lambda =(1+\ldots +1)\lambda =\lambda +\ldots +\lambda .}$

ตัวอย่างเช่น ในลักษณะเฉพาะที่ 2 ขึ้นอยู่กับว่าiเป็นเลขคู่หรือเลขคี่ ${\displaystyle i\lambda =0,\lambda }$

การแทรกสอดแบบลากรางจ์

Gill (nd , หน้า 52–54) นำเสนอการพิสูจน์อัลกอริทึมของ Forney

กำหนดนิยามของพหุนามระบุตำแหน่งการลบ

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

โดยที่ตำแหน่งการลบจะกำหนดโดยj _iใช้ขั้นตอนที่อธิบายไว้ข้างต้น โดยแทนที่ Γ ด้วย Λ

หากมีทั้งข้อผิดพลาดและการลบ ให้ใช้พหุนามระบุตำแหน่งข้อผิดพลาดและการลบ

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

• รหัส BCH
• การแก้ไขข้อผิดพลาดของ Reed–Solomon