ในทฤษฎีสารสนเทศและทฤษฎีการเข้ารหัสรหัสReed–Solomonเป็นกลุ่มของรหัสแก้ไขข้อผิดพลาดที่Irving S. ReedและGustave Solomon นำเสนอ ในปี พ.ศ. 2503 ^{[ 1 ]} รหัส เหล่านี้มีการใช้งานมากมาย รวมถึงเทคโนโลยีสำหรับผู้บริโภค เช่นMiniDiscs , CDs , DVDs , Blu-ray discs, รหัส QR , Data Matrix , เทคโนโลยี การส่งข้อมูลเช่นDSLและWiMAX , ระบบ กระจายเสียงเช่น การสื่อสารผ่านดาวเทียมDVBและATSCและระบบจัดเก็บข้อมูล เช่นRAID 6

รหัสรีด-โซโลมอนทำงานกับบล็อกข้อมูลที่ถือว่าเป็นชุดของ องค์ประกอบ ฟิลด์จำกัดที่เรียกว่าสัญลักษณ์ รหัสรีด-โซโลมอนRS( n , k )สามารถตรวจจับและแก้ไขข้อผิดพลาดของสัญลักษณ์ได้หลายตัว โดยการเพิ่ม สัญลักษณ์ตรวจสอบ t = n − k ตัว ลงในข้อมูล รหัสรีด-โซโลมอนสามารถตรวจจับ (แต่ไม่แก้ไข) การรวมกันของสัญลักษณ์ที่ผิดพลาดได้ มากถึง t ตัวหรือค้นหาและแก้ไขสัญลักษณ์ที่ผิดพลาดได้มากถึง⌊t /2⌋ ตัวในตำแหน่งที่ไม่ทราบ ในฐานะที่เป็นรหัสลบมันสามารถแก้ไขการลบได้มากถึงtครั้งในตำแหน่งที่ทราบและจัดเตรียมไว้ให้กับอัลกอริทึม หรือสามารถตรวจจับและแก้ไขข้อผิดพลาดและการลบแบบผสมผสานกันได้ รหัสรีด-โซโลมอนยังเหมาะสำหรับใช้เป็นรหัสแก้ไขข้อผิดพลาดบิตแบบหลายชุดเนื่องจากลำดับของ ข้อผิดพลาดบิตต่อเนื่อง b  + 1ตัวสามารถส่งผลกระทบต่อสัญลักษณ์ขนาดb ได้มากที่สุดสองตัว การเลือกค่าtขึ้นอยู่กับผู้ออกแบบรหัสและสามารถเลือกได้ภายในขอบเขตที่กว้าง

ในบทความนี้มีวิธีการเข้ารหัส Reed-Solomon สองแบบที่แตกต่างกัน คือแบบมุมมองดั้งเดิมและแบบมุมมอง BCH ส่วนประวัติความเป็นมาจะอธิบายถึงที่มาของวิธีการนี้

รหัส Reed–Solomon ได้รับการพัฒนาในปี 1960 โดยIrving S. ReedและGustave Solomonซึ่งในขณะนั้นเป็นเจ้าหน้าที่ของMIT Lincoln Laboratoryบทความสำคัญของพวกเขามีชื่อว่า "Polynomial Codes over Certain Finite Fields" ^{[ 1 ]}รูปแบบการเข้ารหัสเดิมที่อธิบายไว้ในบทความของ Reed และ Solomon ใช้พหุนามตัวแปรตามข้อความที่จะเข้ารหัส โดยที่ตัวเข้ารหัสและตัวถอดรหัสทราบเพียงชุดค่าคงที่ (จุดประเมิน) ที่จะเข้ารหัสเท่านั้น ตัวถอดรหัสเชิงทฤษฎีเดิมสร้างพหุนามที่เป็นไปได้โดยอิงจากเซตย่อยของค่าk (ความยาวข้อความที่ยังไม่ได้เข้ารหัส) จาก ค่า n (ความยาวข้อความที่เข้ารหัส) ของข้อความที่ได้รับ โดยเลือกพหุนามที่ได้รับความนิยมมากที่สุดเป็นพหุนามที่ถูกต้อง ซึ่งไม่สามารถนำไปใช้ได้จริงยกเว้นในกรณีที่ง่ายที่สุด ในขั้นต้น ปัญหานี้ได้รับการแก้ไขโดยการเปลี่ยนรูปแบบเดิมไปเป็น รูปแบบที่เข้ากันได้ กับรหัส BCHโดยใช้พหุนามคงที่ที่ทั้งตัวเข้ารหัสและตัวถอดรหัสทราบ แต่ต่อมาได้มีการพัฒนาตัวถอดรหัสที่ใช้งานได้จริงโดยใช้รูปแบบเดิม แม้ว่าในตอนแรกจะทำงานช้ากว่ารูปแบบ BCH ก็ตาม ผลที่ตามมาคือ รหัสรีด-โซโลมอนมีสองประเภทหลัก ได้แก่ รหัสที่ใช้รูปแบบการเข้ารหัสเดิม และรหัสที่ใช้รูปแบบการเข้ารหัส BCH

นอกจากนี้ ในปี 1960 ตัวถอดรหัสพหุนามคงที่ที่ใช้งานได้จริงสำหรับรหัส BCHซึ่งพัฒนาโดยDaniel Gorensteinและ Neal Zierler ได้รับการอธิบายใน รายงานของ MIT Lincoln Laboratoryโดย Zierler ในเดือนมกราคม 1960 และต่อมาในบทความในเดือนมิถุนายน 1961 ^{[ 2 ]}ตัวถอดรหัส Gorenstein–Zierler และงานที่เกี่ยวข้องกับรหัส BCH ได้รับการอธิบายไว้ในหนังสือ "Error-Correcting Codes" โดยW. Wesley Peterson (1961) ^{[ 3 ]}ภายในปี 1963 (หรืออาจจะก่อนหน้านั้น) JJ Stone (และคนอื่นๆ) ตระหนักว่ารหัส Reed–Solomon สามารถใช้รูปแบบ BCH ของการใช้พหุนามตัวสร้างคงที่ ทำให้รหัสดังกล่าวเป็นรหัส BCH ประเภทพิเศษ^{[ 4 ]}แต่รหัส Reed–Solomon ที่อิงตามรูปแบบการเข้ารหัสเดิมไม่ใช่รหัส BCH ประเภทหนึ่ง และขึ้นอยู่กับชุดของจุดประเมินผล รหัสเหล่านั้นอาจไม่ใช่รหัสแบบ วนรอบด้วย ซ้ำ

ในปี 1969 เอลวิน เบอร์เลแคมป์และเจมส์ แมสซีย์ได้พัฒนาตัวถอดรหัสแบบ BCH ที่ได้รับการปรับปรุงและตั้งแต่นั้นมาก็เป็นที่รู้จักกันในชื่ออัลกอริทึมการถอดรหัสเบอร์เลแคมป์-แมสซีย์

ในปี พ.ศ. 2518 Yasuo Sugiyama ได้พัฒนาตัวถอดรหัสแบบ BCH ที่ได้รับการปรับปรุงอีกตัวหนึ่งโดยอิงจากอัลกอริทึม Euclidean ที่ขยายเพิ่มเติม^{[ 5 ]}

ในปี 1977 รหัสรีด-โซโลมอนถูกนำมาใช้ในโครงการวอยเอเจอร์ในรูปแบบของรหัสแก้ไขข้อผิดพลาดแบบต่อกันการใช้งานเชิงพาณิชย์ครั้งแรกในผลิตภัณฑ์สำหรับผู้บริโภคที่ผลิตจำนวนมากปรากฏขึ้นในปี 1982 กับแผ่นซีดี ซึ่ง ใช้รหัสรีด-โซโลมอนสอง รหัส แบบสลับกัน ปัจจุบัน รหัสรีด-โซโลมอนถูกนำไปใช้อย่างแพร่หลายในอุปกรณ์ จัดเก็บข้อมูลดิจิทัลและ มาตรฐาน การสื่อสารดิจิทัลแม้ว่าจะค่อยๆ ถูกแทนที่ด้วยรหัสโบส-เชาดูรี-ฮอคเควนเก็ม (BCH)ก็ตาม ตัวอย่างเช่น รหัสรีด-โซโลมอนถูกใช้ใน มาตรฐาน การออกอากาศวิดีโอดิจิทัล (DVB) DVB-Sร่วมกับรหัสภายในแบบคอนโวลูชัน แต่รหัส BCH ถูกใช้ร่วมกับLDPC ในมาตรฐาน DVB-S2ซึ่ง เป็นรุ่นต่อมา

ในปี 1986 ได้มีการพัฒนา ตัวถอดรหัสรูปแบบใหม่ที่เรียกว่า อัลกอริทึม Berlekamp–Welch ขึ้นมา

ในปี 1996 Madhu Sudan และคนอื่นๆ ได้พัฒนาตัวถอดรหัสแบบต่างๆ ที่ดัดแปลงมาจากแบบแผนดั้งเดิม เรียกว่า ตัวถอดรหัสแบบรายการ หรือ ตัวถอดรหัสแบบอ่อน และงานวิจัยเกี่ยวกับตัวถอดรหัสประเภทนี้ยังคงดำเนินต่อไป (ดูอัลกอริทึมการถอดรหัสแบบรายการของ Guruswami–Sudan )

ในปี พ.ศ. 2545 Shuhong Gao ได้พัฒนาตัวถอดรหัสแบบแผนดั้งเดิมอีกตัวหนึ่งโดยอิงจาก อัลกอริทึมยู คลิดแบบขยาย^{[ 6 ]}

ประมาณปี 2015 ได้มีการพัฒนาระบบถอดรหัสแบบซินโดรมตามแบบแผนดั้งเดิม (ผู้เขียนไม่ทราบชื่อ) ^{[ 7 ]}

การเข้ารหัสแบบรีด-โซโลมอนถูกนำมาใช้กันอย่างแพร่หลายใน ระบบ จัดเก็บข้อมูลขนาดใหญ่เพื่อแก้ไขข้อผิดพลาดแบบเบิร์สต์ที่เกิดจากข้อบกพร่องของสื่อบันทึกข้อมูล

การเข้ารหัส Reed–Solomon เป็นส่วนประกอบสำคัญของแผ่นซีดีนับเป็นการใช้การเข้ารหัสแก้ไขข้อผิดพลาดที่แข็งแกร่งเป็นครั้งแรกในผลิตภัณฑ์สำหรับผู้บริโภคที่ผลิตในปริมาณมาก และDATกับDVD ก็ใช้รูปแบบที่คล้ายกัน ในแผ่นซีดี การเข้ารหัส Reed–Solomon สองชั้นที่คั่นด้วย ตัวสลับข้อมูลแบบคอนโวลู ชัน 28 ทางทำให้ได้รูปแบบที่เรียกว่า การเข้ารหัส Reed–Solomon แบบสลับไขว้ ( CIRC ) องค์ประกอบแรกของตัวถอดรหัส CIRC คือรหัส Reed–Solomon ภายในที่ค่อนข้างอ่อน (32,28) ซึ่งย่อมาจากรหัส (255,251) ที่มีสัญลักษณ์ 8 บิต รหัสนี้สามารถแก้ไขข้อผิดพลาดได้สูงสุด 2 ไบต์ต่อบล็อก 32 ไบต์ ที่สำคัญกว่านั้นคือ มันจะทำเครื่องหมายบล็อกที่ไม่สามารถแก้ไขได้ เช่น บล็อกที่มีข้อผิดพลาดมากกว่า 2 ไบต์ ว่าเป็นการลบ บล็อกขนาด 28 ไบต์ที่ถอดรหัสแล้ว พร้อมด้วยตัวบ่งชี้การลบ จะถูกกระจายโดยตัวแยกการเรียงข้อมูลไปยังบล็อกต่างๆ ของรหัสภายนอก (28,24) ด้วยกระบวนการแยกการเรียงข้อมูล บล็อกขนาด 28 ไบต์ที่ถูกลบจากรหัสภายในจะกลายเป็นไบต์ที่ถูกลบเพียงไบต์เดียวในแต่ละบล็อกของรหัสภายนอกจำนวน 28 บล็อก รหัสภายนอกสามารถแก้ไขปัญหานี้ได้อย่างง่ายดาย เนื่องจากสามารถจัดการกับการลบได้ถึง 4 ครั้งต่อบล็อก

ผลลัพธ์คือ CIRC ที่สามารถแก้ไขข้อผิดพลาดแบบระเบิดได้อย่างสมบูรณ์แบบถึง 4000 บิต หรือประมาณ 2.5 มม. บนพื้นผิวแผ่นดิสก์ รหัสนี้มีความแข็งแกร่งมากจนข้อผิดพลาดในการเล่นซีดีส่วนใหญ่เกือบจะเกิดจากข้อผิดพลาดในการติดตามที่ทำให้เลเซอร์กระโดดข้ามแทร็ก ไม่ใช่จากข้อผิดพลาดแบบระเบิดที่ไม่สามารถแก้ไขได้^{[ 8 ]}

ดีวีดีใช้รูปแบบที่คล้ายกัน แต่มีบล็อกที่ใหญ่กว่ามาก คือ รหัสภายใน (208,192) และรหัสภายนอก (182,172)

การแก้ไขข้อผิดพลาดแบบ Reed–Solomon ยังใช้ใน ไฟล์ parchiveซึ่งมักถูกโพสต์พร้อมกับไฟล์มัลติมีเดียบนUSENETบริการจัดเก็บข้อมูลออนไลน์แบบกระจายWuala (ซึ่งยุติการให้บริการในปี 2015) ก็ใช้ Reed–Solomon ในการแบ่งไฟล์เช่นกัน

บาร์โค้ดสองมิติเกือบทั้งหมด เช่นPDF-417 , MaxiCode , Datamatrix , QR Code , Aztec CodeและHan Xin Codeใช้การแก้ไขข้อผิดพลาดแบบ Reed–Solomon เพื่อให้สามารถอ่านได้อย่างถูกต้องแม้ว่าส่วนใดส่วนหนึ่งของบาร์โค้ดจะเสียหาย เมื่อเครื่องสแกนบาร์โค้ดไม่สามารถจดจำสัญลักษณ์บาร์โค้ดได้ มันจะถือว่าส่วนนั้นถูกลบไป

การเข้ารหัสแบบ Reed–Solomon พบได้น้อยในบาร์โค้ดแบบหนึ่งมิติ แต่ถูกนำมาใช้ในระบบสัญลักษณ์ PostBar

รหัสรีด-โซโลมอนรูปแบบพิเศษ โดยเฉพาะCauchy -RS และVandermonde -RS สามารถนำมาใช้เพื่อเอาชนะข้อจำกัดด้านความน่าเชื่อถือของการส่งข้อมูลผ่านช่องทางการลบ ข้อมูล ได้ กระบวนการเข้ารหัสจะใช้รหัส RS( N ,  K ) ซึ่งส่งผลให้เกิด คำรหัส Nคำที่มีความยาวNสัญลักษณ์ โดยแต่ละคำจะเก็บ ข้อมูล Kสัญลักษณ์ จากนั้นจึงส่งข้อมูลเหล่านั้นผ่านช่องทางการลบข้อมูล

การรับรหัสคำ Kชุดใดๆ ก็ตาม ที่ปลายอีกด้านหนึ่งนั้นเพียงพอที่จะสร้าง รหัสคำNทั้งหมดขึ้นมาใหม่ได้ โดยทั่วไปแล้ว อัตราการเข้ารหัสจะถูกตั้งไว้ที่ 1/2 เว้นแต่ว่าความน่าจะเป็นของการลบข้อมูลในช่องสัญญาณนั้นสามารถจำลองได้อย่างเหมาะสมและพบว่ามีค่าน้อยกว่านั้น สรุปได้ว่าNมักจะเป็น2Kซึ่งหมายความว่าอย่างน้อยครึ่งหนึ่งของรหัสคำทั้งหมดที่ส่งไปจะต้องได้รับการรับกลับมาเพื่อที่จะสร้างรหัสคำทั้งหมดที่ส่งไปขึ้นมาใหม่ได้

รหัสรีด-โซโลมอนยังถูกใช้ใน ระบบ xDSLและข้อกำหนดโปรโตคอลการสื่อสารในอวกาศของCCSDSในรูปแบบหนึ่งของการแก้ไขข้อผิดพลาดล่วงหน้าด้วย

หนึ่งในแอปพลิเค ชัน ที่สำคัญของการเข้ารหัส Reed–Solomon คือการเข้ารหัสภาพดิจิทัลที่ส่งกลับมาจากโครงการ Voyager

ยานวอยเอเจอร์ได้นำเสนอการเข้ารหัสแบบรีด-โซโลมอนที่เชื่อมต่อกับการเข้ารหัสแบบคอนโวลู ชัน ซึ่งเป็นวิธีการที่แพร่หลายอย่างมากในอวกาศห้วงลึกและการสื่อสารผ่านดาวเทียม (เช่น การออกอากาศดิจิทัลโดยตรง)

ตัวถอดรหัส Viterbiมักเกิดข้อผิดพลาดเป็นช่วงสั้นๆ การแก้ไขข้อผิดพลาดเหล่านี้เป็นวิธีที่ดีที่สุดโดยใช้รหัส Reed–Solomon แบบสั้นหรือแบบง่าย

การเข้ารหัสแบบคอนโวลูชันที่ถอดรหัสด้วย Reed–Solomon/Viterbi เวอร์ชันสมัยใหม่ถูกนำมาใช้และยังคงใช้ใน ภารกิจ Mars Pathfinder , Galileo , Mars Exploration RoverและCassiniซึ่งมีประสิทธิภาพใกล้เคียงกับขีดจำกัดสูงสุด คือ ความจุของ Shannon โดยมีค่า ความคลาดเคลื่อน ไม่เกิน 1–1.5 dB

รหัสที่ต่อกันเหล่านี้กำลังถูกแทนที่ด้วยรหัสเทอร์โบ ที่มีประสิทธิภาพมากขึ้นแล้ว :

รหัสรีด-โซโลมอนแท้จริงแล้วเป็นกลุ่มของรหัส โดยแต่ละรหัสมีลักษณะเฉพาะด้วยพารามิเตอร์สามตัว ได้แก่ขนาดตัวอักษรq ความยาวบล็อก n และความยาวข้อความkโดยที่เซตของสัญลักษณ์ตัวอักษรถูกตีความว่าเป็นฟิลด์จำกัดที่มีอันดับและดังนั้นต้องเป็นกำลังของจำนวนเฉพาะในการกำหนดพารามิเตอร์ที่มีประโยชน์ที่สุดของรหัสรีด-โซโลมอน ความยาวบล็อกมักจะเป็นค่าคงที่คูณกับความยาวข้อความ นั่นคืออัตราเป็นค่าคงที่ และนอกจากนี้ ความยาวบล็อกจะเท่ากับขนาดตัวอักษรหรือน้อยกว่าหนึ่ง นั่นคือ หรือ${\displaystyle k<n\leq q}$${\displaystyle F}$${\displaystyle q}$${\displaystyle q}$${\displaystyle R={\frac {k}{n}}}$${\displaystyle n=q}$${\displaystyle n=q-1}$

มีขั้นตอนการเข้ารหัสที่แตกต่างกันสำหรับรหัส Reed–Solomon และด้วยเหตุนี้จึงมีวิธีการอธิบายชุดของคำรหัสทั้งหมดที่แตกต่างกัน ในมุมมองดั้งเดิมของ Reed และ Solomon คำรหัสทุกคำของรหัส Reed–Solomon คือลำดับของค่าฟังก์ชันของพหุนามที่มีดีกรีน้อยกว่า[ ^{1 ] เพื่อ}ให้ได้คำรหัสของรหัส Reed–Solomon สัญลักษณ์ข้อความ (แต่ละสัญลักษณ์ภายในตัวอักษรขนาด q) จะถูกพิจารณาว่าเป็นสัมประสิทธิ์ของพหุนามที่มีดีกรีน้อยกว่าบนฟิลด์จำกัดที่มีองค์ประกอบ ในทางกลับกัน พหุนามจะถูกประเมินที่ชุดของจุดที่แตกต่างกันในลำดับใดก็ได้ของฟิลด์ และลำดับของค่าจะ เป็น คำรหัสที่สอดคล้องกัน ตัวเลือกทั่วไปสำหรับชุดของจุดประเมิน ได้แก่, , หรือ สำหรับ, , ... โดยที่เป็นองค์ประกอบดั้งเดิมของ${\displaystyle k}$${\displaystyle p}$${\displaystyle k}$${\displaystyle F}$${\displaystyle q}$${\displaystyle p}$${\displaystyle n\leq q}$${\displaystyle a_{1},\dots ,a_{n}}$${\displaystyle F}$${\displaystyle \{0,1,2,\dots ,n-1\}}$${\displaystyle \{0,1,\alpha ,\alpha ^{2},\dots ,\alpha ^{n-2}\}}$${\displaystyle n<q}$${\displaystyle \{1,\alpha ,\alpha ^{2},\dots ,\alpha ^{n-1}\}}$${\displaystyle \alpha }$${\displaystyle F}$

ในทางทฤษฎี เซตของรหัสคำของรหัสรีด-โซโลมอนถูกกำหนดดังนี้: เนื่องจากพหุนามสอง ตัว ที่แตกต่างกันซึ่งมีดีกรีน้อยกว่าจะตรงกันอย่างมากที่สุดที่จุด นั่นหมายความว่ารหัสคำสองคำใดๆ ของรหัสรีด-โซโลมอนจะไม่ตรงกันอย่างน้อยที่ตำแหน่ง ยิ่งไปกว่านั้น มีพหุนามสองตัวที่ตรงกันที่จุด แต่ไม่เท่ากัน ดังนั้นระยะทางของรหัสรีด-โซโลมอนจึงเท่ากับ พอดีดังนั้น ระยะทางสัมพัทธ์คือโดยที่คืออัตรา การแลกเปลี่ยนระหว่างระยะทางสัมพัทธ์และอัตรานี้ถือว่าเหมาะสมที่สุดในเชิงอะซิมโทติก เนื่องจากตามขอบเขตของซิงเกิลตันรหัสทุกตัวจึงเป็นไปตาม เงื่อนไข เนื่องจากเป็นรหัสที่บรรลุการแลกเปลี่ยนที่เหมาะสมที่สุดนี้ รหัสรีด-โซโลมอนจึงอยู่ในกลุ่มของ รหัสที่แยก ได้ ด้วยระยะทางสูงสุด${\displaystyle \mathbf {C} }$$${\displaystyle \mathbf {C} ={\Bigl \{}\;{\bigl (}p(a_{1}),p(a_{2}),\dots ,p(a_{n}){\bigr )}\;{\Big |}\;p{\text{ เป็นพหุนามเหนือ }}F{\text{ ที่มีดีกรี }}<k\;{\Bigr \}}\,.}$$${\displaystyle k}$${\displaystyle k-1}$${\displaystyle n-(k-1)=n-k+1}$${\displaystyle k-1}$${\displaystyle d=n-k+1}$${\displaystyle \delta =d/n=1-k/n+1/n=1-R+1/n\sim 1-R}$${\displaystyle R=k/n}$${\displaystyle \delta +R\leq 1+1/n}$

ในขณะที่จำนวนพหุนามที่แตกต่างกันที่มีดีกรีน้อยกว่าkและจำนวนข้อความที่แตกต่างกันนั้นเท่ากันและดังนั้นข้อความทุกข้อความสามารถแมปไปยังพหุนามดังกล่าวได้อย่างไม่ซ้ำกัน แต่ก็มีวิธีการเข้ารหัสที่แตกต่างกัน การสร้างดั้งเดิมของ Reed & Solomon ตีความข้อความxเป็นสัมประสิทธิ์ของพหุนามpในขณะที่การสร้างในภายหลังตีความข้อความเป็นค่าของพหุนามที่จุดk แรก และได้พหุนามpโดยการประมาณค่าเหล่านี้ด้วยพหุนามที่มีดีกรีน้อยกว่าk ขั้น ตอนการเข้ารหัสแบบหลังนี้ แม้จะมีประสิทธิภาพน้อยกว่าเล็กน้อย แต่ก็มีข้อดีคือทำให้เกิดรหัสที่เป็นระบบนั่นคือ ข้อความดั้งเดิมจะถูกบรรจุเป็นลำดับย่อยของคำรหัส เสมอ ^{[ 1 ]}${\displaystyle q^{k}}$${\displaystyle a_{1},\dots ,a_{k}}$

ในการสร้างดั้งเดิมของ Reed และ Solomon ข้อความจะถูกแมปไปยังพหุนามที่มี รหัสคำของได้รับจากการประเมิน^{ที่จุดต่าง ๆ ของฟิลด์ [ 1 ]}ดังนั้นฟังก์ชันการ^{เข้ารหัสแบบ}คลาสสิกสำหรับรหัส Reed–Solomon จึงถูกกำหนดดังนี้: ${\displaystyle m=(m_{0},\dots ,m_{k-1})\in F^{k}}$${\displaystyle p_{m}}$$${\displaystyle p_{m}(a)=\sum _{i=0}^{k-1}m_{i}a^{i}=m_{0}+m_{1}a+m_{2}a^{2}+\cdots +m_{k-1}a^{k-1}}$$${\displaystyle m}$${\displaystyle p_{m}}$${\displaystyle n}$${\displaystyle a_{0},\dots ,a_{n-1}}$${\displaystyle F}$${\displaystyle C:F^{k}\to F^{n}}$$${\displaystyle C(m)={\begin{bmatrix}p_{m}(a_{0})&p_{m}(a_{1})&\cdots &p_{m}(a_{n-1})\end{bmatrix}}}$$

ฟังก์ชันนี้เป็นการแมปเชิงเส้น กล่าวคือ เป็นไปตามเงื่อนไขสำหรับเมทริกซ์ n ต่อไปนี้ ที่มีองค์ประกอบจาก ${\displaystyle C}$${\displaystyle C(m)=mA}$${\displaystyle k\times n}$${\displaystyle A}$${\displaystyle F}$

$${\displaystyle C(m)=mA={\begin{bmatrix}m_{0}&m_{1}&m_{2}&\cdots &m_{k-1}\end{bmatrix}}{\begin{bmatrix}1&1&1&\dots &1\\a_{0}&a_{1}&a_{2}&\dots &a_{n-1}\\a_{0}^{2}&a_{1}^{2}&a_{2}^{2}&\dots &a_{n-1}^{2}\\\vdots &\vdots &\vdots &\ddots &\vdots \\a_{0}^{k-1}&a_{1}^{k-1}&a_{2}^{k-1}&\dots &a_{n-1}^{k-1}\end{bmatrix}}}$$

เมทริกซ์นี้คือเมทริกซ์แวนเดอร์มอนด์เหนือ กล่าวอีกนัยหนึ่ง รหัสรีด-โซโลมอนเป็นรหัสเชิงเส้นและในขั้นตอนการเข้ารหัสแบบคลาสสิกเมทริกซ์กำเนิด ของมัน คือ${\displaystyle F}$${\displaystyle A}$

มีวิธีการเข้ารหัสทางเลือกอื่นที่สร้างรหัส Reed–Solomon ที่เป็นระบบ วิธีหนึ่งใช้ การประมาณค่าแบบ Lagrangeเพื่อคำนวณพหุนามโดยที่ จากนั้นจึงประเมินค่าที่จุดอื่นๆ ${\displaystyle p_{m}}$$${\displaystyle p_{m}(a_{i})=m_{i}{\text{ for all }}i\in \{0,\dots ,k-1\}.}$$${\displaystyle p_{m}}$${\displaystyle a_{k},\dots ,a_{n-1}}$

$${\displaystyle C(m)={\begin{bmatrix}p_{m}(a_{0})&p_{m}(a_{1})&\cdots &p_{m}(a_{n-1})\end{bmatrix}}}$$

ฟังก์ชันนี้เป็นการแมปเชิงเส้น ในการสร้างเมทริกซ์การเข้ารหัสเชิงระบบ G ที่สอดคล้องกัน ให้คูณเมทริกซ์ A ด้วยเมทริกซ์ผกผันของเมทริกซ์ย่อยสี่เหลี่ยมจัตุรัสด้านซ้ายของ A ${\displaystyle C}$

$${\displaystyle G=(A{\text{'s left square submatrix}})^{-1}\cdot A={\begin{bmatrix}1&0&0&\dots &0&g_{1,k+1}&\dots &g_{1,n}\\0&1&0&\dots &0&g_{2,k+1}&\dots &g_{2,n}\\0&0&1&\dots &0&g_{3,k+1}&\dots &g_{3,n}\\\vdots &\vdots &\vdots &&\vdots &\vdots &&\vdots \\0&\dots &0&\dots &1&g_{k,k+1}&\dots &g_{k,n}\end{bmatrix}}}$$

${\displaystyle C(m)=mG}$สำหรับเมทริกซ์ ต่อไปนี้ ที่มีองค์ประกอบจาก. ${\displaystyle k\times n}$${\displaystyle G}$${\displaystyle F}$$${\displaystyle C(m)=mG={\begin{bmatrix}m_{0}&m_{1}&m_{2}&\cdots &m_{k-1}\end{bmatrix}}{\begin{bmatrix}1&0&0&\dots &0&g_{1,k+1}&\dots &g_{1,n}\\0&1&0&\dots &0&g_{2,k+1}&\dots &g_{2,n}\\0&0&1&\dots &0&g_{3,k+1}&\dots &g_{3,n}\\\vdots &\vdots &\vdots &&\vdots &\vdots &&\vdots \\0&\dots &0&\dots &1&g_{k,k+1}&\dots &g_{k,n}\end{bmatrix}}}$$

การแปลงฟูริเยร์แบบไม่ต่อเนื่องนั้นโดยพื้นฐานแล้วเหมือนกับขั้นตอนการเข้ารหัส กล่าวคือ มันใช้พหุนามตัวสร้างเพื่อแปลงชุดจุดประเมินผลไปเป็นค่าข้อความดังที่แสดงไว้ข้างต้น: ${\displaystyle p_{m}}$$${\displaystyle C(m)={\begin{bmatrix}p_{m}(a_{0})&p_{m}(a_{1})&\cdots &p_{m}(a_{n-1})\end{bmatrix}}}$$

สามารถใช้การแปลงฟูริเยร์ผกผันเพื่อแปลงชุด ค่าข้อความ n < q ที่ปราศจากข้อผิดพลาด กลับไปเป็นพหุนามการเข้ารหัสที่ มีสัมประสิทธิ์ kตัว โดยมีข้อจำกัดว่าเพื่อให้วิธีการนี้ได้ผล ชุดจุดประเมินที่ใช้ในการเข้ารหัสข้อความจะต้องเป็นชุดของกำลังของα ที่เพิ่มขึ้นเรื่อย ๆ $${\displaystyle a_{i}=\alpha ^{i}}$$$${\displaystyle a_{0},\dots ,a_{n-1}=\{1,\alpha ,\alpha ^{2},\dots ,\alpha ^{n-1}\}}$$

อย่างไรก็ตาม การแทรกสอดแบบลากรางจ์ (Lagrange interpolation) ทำการแปลงแบบเดียวกันโดยไม่มีข้อจำกัดเกี่ยวกับชุดจุดประเมินหรือข้อกำหนดของชุดค่าข้อความที่ปราศจากข้อผิดพลาด และใช้สำหรับการเข้ารหัสอย่างเป็นระบบ และในขั้นตอนหนึ่งของตัวถอดรหัสเกา (Gao decoder )

โปรดทราบว่ารหัส BCHและการใช้งานมุมมอง BCH ส่วนใหญ่จะเรียงลำดับพจน์ที่มีค่ามากที่สุดก่อน ในมุมมองนี้ ข้อความจะถูกตีความว่าเป็นสัมประสิทธิ์ของพหุนาม: ${\displaystyle m(x)}$

$${\displaystyle m(x)=m_{k-1}x^{k-1}+m_{k-2}x^{k-2}+\cdots +m_{1}x+m_{0}}$$

พหุนามตัวสร้าง (Generator polynomial) ถูกนิยามว่าเป็นพหุนามที่มีรากเป็นกำลังเรียงลำดับของพหุนามพื้นฐานของฟิลด์กาโลอิส (Galois field primitive) สำหรับ "รหัสความหมายแคบ" (narrow sense code) นั้น ${\displaystyle g(x)}$${\displaystyle \alpha }$$${\displaystyle g(x)=\left(x-\alpha ^{i}\right)\left(x-\alpha ^{i+1}\right)\cdots \left(x-\alpha ^{i+n-k-1}\right)=x^{n-k}+g_{n-k-1}x^{n-k-1}+\cdots +g_{1}x+g_{0}}$$${\displaystyle i=1}$

การเข้ารหัสจะคำนวณพหุนามรหัสคำซึ่งเป็นผลคูณที่แน่นอนของ${\displaystyle c(x)=c_{n-1}x^{n-1}+c_{n-2}x^{n-2}+\cdots +c_{1}x+c_{0}}$${\displaystyle g(x)}$

ผู้ส่งคำนวณพหุนามที่เกี่ยวข้อง ซึ่งมี ดีกรีโดยที่และส่งพหุนามนั้นพหุ นามนี้สร้างขึ้นโดยการคูณพหุนามข้อความซึ่งมีดีกรีกับพหุนามตัวสร้างที่มีดีกรีซึ่งทั้งผู้ส่งและผู้รับทราบ${\displaystyle c(x)}$${\displaystyle n-1}$${\displaystyle n\leq q-1}$${\displaystyle c(x)}$${\displaystyle c(x)}$${\displaystyle m(x)}$${\displaystyle k-1}$${\displaystyle g(x)}$${\displaystyle n-k}$${\displaystyle c(x)=m(x)g(x)}$

ฟังก์ชันนี้เป็นการแมปเชิงเส้น กล่าวคือ เป็นไปตามเงื่อนไขสำหรับเมทริกซ์ n ต่อไปนี้ ที่มีองค์ประกอบจาก ${\displaystyle C}$${\displaystyle C(m)=mA}$${\displaystyle k\times n}$${\displaystyle A}$${\displaystyle F}$

$${\displaystyle A={\begin{bmatrix}1&g_{n-k-1}&\cdots &g_{1}&g_{0}&0&\cdots &\cdots &0\\0&1&g_{n-k-1}&\cdots &g_{1}&g_{0}&0&\cdots &0\\\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots \\0&\cdots &0&1&g_{n-k-1}&\cdots &g_{1}&g_{0}&0\\0&\cdots &\cdots &0&1&g_{n-k-1}&\cdots &g_{1}&g_{0}\\\end{bmatrix}}}$$

${\displaystyle C(m)=mA}$สำหรับเมทริกซ์ ต่อไปนี้ ที่มีองค์ประกอบจาก. ${\displaystyle k\times n}$${\displaystyle G}$${\displaystyle F}$

$${\displaystyle c(x)=mA={\begin{bmatrix}m_{k-1}&\cdots &m_{1}&m_{0}\end{bmatrix}}{\begin{bmatrix}1&g_{n-k-1}&\cdots &g_{1}&g_{0}&0&\cdots &\cdots &0\\0&1&g_{n-k-1}&\cdots &g_{1}&g_{0}&0&\cdots &0\\\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots \\0&\cdots &0&1&g_{n-k-1}&\cdots &g_{1}&g_{0}&0\\0&\cdots &\cdots &0&1&g_{n-k-1}&\cdots &g_{1}&g_{0}\\\end{bmatrix}}}$$

ขั้นตอนการเข้ารหัสสำหรับมุมมอง BCH ของรหัส Reed–Solomon สามารถปรับเปลี่ยนเพื่อให้ได้ขั้นตอนการเข้ารหัสที่เป็นระบบซึ่งแต่ละคำรหัสจะมีข้อความอยู่เป็นคำนำหน้า และเพียงแค่เพิ่มสัญลักษณ์แก้ไขข้อผิดพลาดเป็นส่วนต่อท้าย ในที่นี้ แทนที่จะส่งตัวเข้ารหัสจะสร้างพหุนามที่ส่งโดยที่สัมประสิทธิ์ของเอกนามที่ใหญ่ที่สุดเท่ากับสัมประสิทธิ์ที่สอดคล้องกันของ และสัมประสิทธิ์ลำดับต่ำกว่าของจะถูกเลือกในลักษณะที่หารลงตัวด้วยจากนั้นสัมประสิทธิ์ของจะเป็นลำดับย่อยของสัมประสิทธิ์ของเพื่อให้ได้รหัสที่เป็นระบบโดยรวม เราสร้างพหุนามข้อความโดยตีความข้อความว่าเป็นลำดับของสัมประสิทธิ์ของมัน ${\displaystyle c(x)=m(x)g(x)}$${\displaystyle c(x)}$${\displaystyle k}$${\displaystyle m(x)}$${\displaystyle c(x)}$${\displaystyle c(x)}$${\displaystyle g(x)}$${\displaystyle m(x)}$${\displaystyle c(x)}$${\displaystyle c(x)}$

ตามหลักการแล้ว การสร้างจะทำโดยการคูณด้วยเพื่อให้มีที่ว่างสำหรับสัญลักษณ์ตรวจสอบ จากนั้นหารผลลัพธ์นั้นด้วยเพื่อหาเศษเหลือ และชดเชยเศษเหลือนั้นโดยการลบออกสัญลักษณ์ตรวจสอบจะถูกสร้างขึ้นโดยการคำนวณเศษเหลือ: ${\displaystyle c(x)}$${\displaystyle x^{t}}$${\displaystyle t=n-k}$${\displaystyle g(x)}$${\displaystyle t}$${\displaystyle r(x)}$$${\displaystyle r(x)=c(x)\cdot x^{t}\ {\bmod {\ }}g(x).}$$

ส่วนที่เหลือมีดีกรีสูงสุดเพียง ในขณะที่สัมประสิทธิ์ของในพหุนามเป็นศูนย์ ดังนั้น นิยามของรหัสคำต่อไปนี้จึงมีคุณสมบัติที่ว่าสัมประสิทธิ์ตัวแรกเหมือนกับสัมประสิทธิ์ของ: ${\displaystyle t-1}$${\displaystyle x^{t-1},x^{t-2},\dots ,x^{1},x^{0}}$${\displaystyle c(x)\cdot x^{t}}$${\displaystyle c(x)}$${\displaystyle k}$${\displaystyle c(x)}$$${\displaystyle c(x)=m(x)\cdot x^{t}-r(x)\,.}$$

ดังนั้น จึงหารลงตัวพอดีด้วย: ^{[ 11 ]}${\displaystyle c(x)}$${\displaystyle g(x)}$

$${\displaystyle c(x)\equiv m(x)\cdot x^{t}-r(x)\equiv r(x)-r(x)\equiv 0\mod g(x)\,.}$$

ฟังก์ชันนี้เป็นการแมปเชิงเส้น ในการสร้างเมทริกซ์การเข้ารหัสเชิงระบบ G ที่สอดคล้องกัน ให้คูณเมทริกซ์ A ด้วยเมทริกซ์ผกผันของเมทริกซ์ย่อยสี่เหลี่ยมจัตุรัสด้านซ้ายของ A (หรือกำหนดให้เมทริกซ์ย่อยสี่เหลี่ยมจัตุรัสด้านซ้ายของ G เท่ากับเมทริกซ์เอกลักษณ์ แล้วเข้ารหัสแต่ละแถว) ${\displaystyle C}$

$${\displaystyle G=(A{\text{'s left square submatrix}})^{-1}\cdot A={\begin{bmatrix}1&0&0&\dots &0&g_{1,k+1}&\dots &g_{1,n}\\0&1&0&\dots &0&g_{2,k+1}&\dots &g_{2,n}\\0&0&1&\dots &0&g_{3,k+1}&\dots &g_{3,n}\\\vdots &\vdots &\vdots &&\vdots &\vdots &&\vdots \\0&\dots &0&\dots &1&g_{k,k+1}&\dots &g_{k,n}\end{bmatrix}}}$$

${\displaystyle C(m)=mG}$สำหรับเมทริกซ์ ต่อไปนี้ ที่มีองค์ประกอบจาก. ${\displaystyle k\times n}$${\displaystyle G}$${\displaystyle F}$

$${\displaystyle c(x)=mG={\begin{bmatrix}m_{k-1}&\ldots &m_{1}&m_{0}\end{bmatrix}}{\begin{bmatrix}1&0&0&\dots &0&g_{1,k+1}&\dots &g_{1,n}\\0&1&0&\dots &0&g_{2,k+1}&\dots &g_{2,n}\\0&0&1&\dots &0&g_{3,k+1}&\dots &g_{3,n}\\\vdots &\vdots &\vdots &&\vdots &\vdots &&\vdots \\0&\dots &0&\dots &1&g_{k,k+1}&\dots &g_{k,n}\end{bmatrix}}}$$

รหัส Reed–Solomon เป็นรหัส [ n , k , n − k + 1] กล่าวคือ เป็นรหัสบล็อกเชิงเส้นที่มีความยาวn (เหนือF ) ที่มีมิติkและระยะห่างแฮมมิ งต่ำสุด รหัส Reed–Solomon เป็นรหัสที่ดีที่สุดในแง่ที่ว่าระยะห่างต่ำสุดมีค่าสูงสุดที่เป็นไปได้สำหรับรหัสเชิงเส้นขนาด ( n ,  k ) ซึ่งเรียกว่าขอบเขตซิงเกิลตันรหัสดังกล่าวเรียกอีกอย่างว่ารหัสแยกได้ด้วยระยะห่างสูงสุด (MDS ) ${\textstyle d_{\min }=n-k+1.}$

ความสามารถในการแก้ไขข้อผิดพลาดของรหัสรีด-โซโลมอนนั้นถูกกำหนดโดยระยะห่างขั้นต่ำ หรือเทียบเท่ากับค่า ซึ่งเป็นมาตรวัดความซ้ำซ้อนในบล็อก หากไม่ทราบตำแหน่งของสัญลักษณ์ที่ผิดพลาดล่วงหน้า รหัสรีด-โซโลมอนสามารถแก้ไขสัญลักษณ์ที่ผิดพลาดได้สูงสุด ตัว นั่นคือ สามารถแก้ไขข้อผิดพลาดได้ครึ่งหนึ่งของจำนวนสัญลักษณ์ที่ซ้ำซ้อนที่เพิ่มเข้ามาในบล็อก บางครั้งตำแหน่งของข้อผิดพลาดเป็นที่ทราบล่วงหน้า (เช่น "ข้อมูลเสริม" ในอัตราส่วนสัญญาณต่อสัญญาณรบกวนของตัวถอดรหัส ) ซึ่งเรียกว่าการลบ (erasures ) รหัสรีด-โซโลมอน (เช่นเดียวกับรหัส MDS ใดๆ ) สามารถแก้ไขการลบได้เป็นสองเท่าของข้อผิดพลาด และสามารถแก้ไขข้อผิดพลาดและการลบได้ทุกรูปแบบตราบใดที่ความสัมพันธ์2 E + S ≤ n − kเป็นจริง โดยที่คือจำนวนข้อผิดพลาด และคือจำนวนการลบในบล็อก ${\displaystyle n-k}$${\displaystyle (n-k)/2}$${\displaystyle E}$${\displaystyle S}$

ขอบเขตข้อผิดพลาดทางทฤษฎีสามารถอธิบายได้โดยใช้สูตรต่อไปนี้สำหรับ ช่องสัญญาณ AWGNสำหรับFSK : ^{[ 12 ]} และสำหรับรูปแบบการมอดูเลชั่นอื่นๆ: โดยที่, , , คืออัตราข้อผิดพลาดของสัญลักษณ์ในกรณี AWGN ที่ไม่ได้เข้ารหัส และคือลำดับการมอดูเลชั่น $${\displaystyle P_{b}\approx {\frac {2^{m-1}}{2^{m}-1}}{\frac {1}{n}}\sum _{\ell =t+1}^{n}\ell {n \choose \ell }P_{s}^{\ell }(1-P_{s})^{n-\ell }}$$$${\displaystyle P_{b}\approx {\frac {1}{m}}{\frac {1}{n}}\sum _{\ell =t+1}^{n}\ell {n \choose \ell }P_{s}^{\ell }(1-P_{s})^{n-\ell }}$$${\textstyle t={\frac {1}{2}}(d_{\min }-1)}$${\displaystyle P_{s}=1-(1-s)^{h}}$${\displaystyle h={\frac {m}{\log _{2}M}}}$${\displaystyle s}$${\displaystyle M}$

สำหรับการใช้งานจริงของรหัสรีด-โซโลมอน มักใช้ฟิลด์จำกัดที่มีสมาชิกจำนวนหนึ่ง ในกรณีนี้ แต่ละสัญลักษณ์สามารถแทนด้วยค่า n บิต ผู้ส่งจะส่งจุดข้อมูลเป็นบล็อกที่เข้ารหัส และจำนวนสัญลักษณ์ในบล็อกที่เข้ารหัสคือดังนั้น รหัสรีด-โซโลมอนที่ทำงานกับสัญลักษณ์ 8 บิตจะมี สัญลักษณ์ต่อบล็อก (ค่านี้เป็นที่นิยมมากเนื่องจากระบบคอมพิวเตอร์ แบบไบต์เป็นที่แพร่หลาย) จำนวนโดยที่ คือจำนวน สัญลักษณ์ ข้อมูลในบล็อกเป็นพารามิเตอร์การออกแบบ รหัสที่ใช้กันทั่วไปจะเข้ารหัสสัญลักษณ์ข้อมูล 8 บิตบวกสัญลักษณ์พาริตี 8 บิต 32 ตัวในบล็อก n สัญลักษณ์ ซึ่งเรียกว่ารหัส และสามารถแก้ไขข้อผิดพลาดของสัญลักษณ์ได้สูงสุด 16 ตัวต่อบล็อก ${\displaystyle F}$${\displaystyle 2^{m}}$${\displaystyle m}$${\displaystyle n=2^{m}-1}$${\displaystyle n=2^{8}-1=255}$${\displaystyle k}$${\displaystyle k<n}$${\displaystyle k=223}$${\displaystyle n=255}$${\displaystyle (n,k)=(255,223)}$

คุณสมบัติของรหัสรีด-โซโลมอนที่กล่าวถึงข้างต้น ทำให้รหัสนี้เหมาะอย่างยิ่งสำหรับแอปพลิเคชันที่เกิดข้อผิดพลาดเป็นช่วงๆเนื่องจากรหัสนี้ไม่สนใจว่าจะมีบิตผิดพลาดกี่บิตในสัญลักษณ์ หากบิตหลายบิตในสัญลักษณ์เสียหาย จะนับเป็นข้อผิดพลาดเพียงข้อเดียว ในทางกลับกัน หากกระแสข้อมูลไม่ได้มีลักษณะเป็นข้อผิดพลาดเป็นช่วงๆ หรือขาดหาย แต่เป็นข้อผิดพลาดแบบสุ่มทีละบิต รหัสรีด-โซโลมอนมักจะเป็นตัวเลือกที่ไม่ดีนักเมื่อเทียบกับรหัสไบนารี

รหัสรีด-โซโลมอน เช่นเดียวกับรหัสคอนโวลูชันเป็นรหัสโปร่งใส หมายความว่า หากสัญลักษณ์ในช่องสัญญาณถูกกลับด้านที่ใดที่หนึ่งในสายส่ง ตัวถอดรหัสก็จะยังคงทำงานได้ ผลลัพธ์ที่ได้จะเป็นการกลับด้านของข้อมูลดั้งเดิม อย่างไรก็ตาม รหัสรีด-โซโลมอนจะสูญเสียความโปร่งใสเมื่อรหัสถูกย่อ ( ดู 'หมายเหตุ' ในตอนท้ายของส่วนนี้ ) บิตที่ "หายไป" ในรหัสที่ย่อแล้วจะต้องถูกเติมด้วยศูนย์หรือหนึ่ง ขึ้นอยู่กับว่าข้อมูลนั้นถูกกลับด้านหรือไม่ (กล่าวอีกนัยหนึ่ง หากสัญลักษณ์ถูกกลับด้าน การเติมศูนย์จะต้องถูกกลับด้านเป็นการเติมหนึ่ง) ด้วยเหตุนี้ จึงจำเป็นอย่างยิ่งที่จะต้องระบุความหมายของข้อมูล (เช่น ข้อมูลจริงหรือข้อมูลที่ถูกกลับด้าน) ก่อนที่จะถอดรหัสรีด-โซโลมอน

รหัส Reed–Solomon จะเป็นแบบวัฏจักรหรือไม่นั้นขึ้นอยู่กับรายละเอียดปลีกย่อยของการสร้าง ในมุมมองดั้งเดิมของ Reed และ Solomon ซึ่งรหัสคำเป็นค่าของพหุนาม เราสามารถเลือกลำดับของจุดประเมินค่าในลักษณะที่ทำให้รหัสเป็นแบบวัฏจักรได้ โดยเฉพาะอย่างยิ่ง ถ้าเป็นรากปฐมภูมิของฟิลด์แล้วตามคำนิยามแล้ว สมาชิกที่ไม่เป็นศูนย์ทั้งหมดของจะอยู่ในรูปแบบสำหรับโดยที่พหุนามแต่ละตัวเหนือจะให้รหัสคำเนื่องจากฟังก์ชันก็เป็นพหุนามที่มีดีกรีเดียวกัน ฟังก์ชันนี้จึงให้รหัสคำเนื่องจากเป็นจริง รหัสคำนี้จึงเป็นการเลื่อนซ้ายแบบวัฏจักรของรหัสคำดั้งเดิมที่ได้มาจากดังนั้นการเลือกลำดับของกำลังรากปฐมภูมิเป็นจุดประเมินค่าทำให้รหัส Reed–Solomon ในมุมมองดั้งเดิมเป็นแบบวัฏจักร รหัส Reed–Solomon ในมุมมอง BCH เป็นแบบวัฏจักรเสมอเพราะรหัส BCH เป็นแบบวัฏจักร ${\displaystyle \alpha }$${\displaystyle F}$${\displaystyle F}$${\displaystyle \alpha ^{i}}$${\displaystyle i\in \{1,\dots ,q-1\}}$${\displaystyle q=|F|}$${\displaystyle p}$${\displaystyle F}$${\displaystyle (p(\alpha ^{1}),\dots ,p(\alpha ^{q-1}))}$${\displaystyle a\mapsto p(\alpha a)}$${\displaystyle (p(\alpha ^{2}),\dots ,p(\alpha ^{q}))}$${\displaystyle \alpha ^{q}=\alpha ^{1}}$${\displaystyle p}$

นักออกแบบไม่จำเป็นต้องใช้ขนาด "ตามธรรมชาติ" ของบล็อกรหัส Reed–Solomon เทคนิคที่เรียกว่า "การย่อ" สามารถสร้างรหัสที่เล็กลงได้ตามต้องการจากรหัสที่ใหญ่กว่า ตัวอย่างเช่น รหัส (255,223) ที่ใช้กันอย่างแพร่หลายสามารถแปลงเป็นรหัส (160,128) ได้โดยการเติมส่วนที่ไม่ได้ใช้ของบล็อกต้นฉบับด้วยเลขศูนย์ไบนารี 95 ตัวและไม่ส่งเลขศูนย์เหล่านั้น ที่ตัวถอดรหัส ส่วนเดียวกันของบล็อกจะถูกโหลดด้วยเลขศูนย์ไบนารีในพื้นที่

รหัส QR เวอร์ชัน 3 (29×29) ใช้บล็อกแบบสลับกัน ข้อความมีข้อมูล 26 ไบต์และเข้ารหัสโดยใช้บล็อกรหัส Reed-Solomon สองบล็อก แต่ละบล็อกเป็นรหัส Reed Solomon (255,233) ที่ย่อเป็นรหัส (35,13)

ทฤษฎีบท Delsarte–Goethals–Seidel ^{[ 13 ]}แสดงให้เห็นตัวอย่างของการประยุกต์ใช้รหัส Reed–Solomon ที่สั้นลง ควบคู่ไปกับการย่อให้สั้นลง เทคนิคที่เรียกว่าการเจาะช่วยให้สามารถละเว้นสัญลักษณ์พาริตีที่เข้ารหัสบางส่วนได้

ตัวถอดรหัสที่อธิบายไว้ในส่วนนี้ใช้มุมมอง BCH ของรหัสคำเป็นลำดับของสัมประสิทธิ์ โดยใช้พหุนามตัวสร้างคงที่ซึ่งทั้งตัวเข้ารหัสและตัวถอดรหัสทราบ

Daniel Gorenstein และ Neal Zierler ได้พัฒนาตัวถอดรหัสที่อธิบายไว้ในรายงานของ MIT Lincoln Laboratory โดย Zierler ในเดือนมกราคม พ.ศ. 2503 และต่อมาในบทความในเดือนมิถุนายน พ.ศ. 2504 ^{[ 14 ] [ 15 ]}ตัวถอดรหัส Gorenstein–Zierler และงานที่เกี่ยวข้องกับรหัส BCH ได้รับการอธิบายไว้ในหนังสือError Correcting CodesโดยW. Wesley Peterson (พ.ศ. 2504) ^{[ 3 ]}

ข้อความที่ส่งนั้นถือเป็นสัมประสิทธิ์ของพหุนาม ${\displaystyle (c_{0},\ldots ,c_{i},\ldots ,c_{n-1})}$$${\displaystyle s(x)=\sum _{i=0}^{n-1}c_{i}x^{i}.}$$

จากผลของกระบวนการเข้ารหัส Reed–Solomon ทำให้s ( x ) หารลงตัวด้วยพหุนามตัวสร้าง โดยที่αเป็นองค์ประกอบดั้งเดิม $${\displaystyle g(x)=\prod _{j=1}^{n-k}(x-\alpha ^{j}),}$$

เนื่องจากs ( x ) เป็นผลคูณของตัวสร้างg ( x) ดังนั้น s( x ) จึง "สืบทอด" รากทั้งหมดของตัวสร้าง g(x) ได้: ด้วยเหตุนี้ $${\displaystyle s(x){\bmod {(}}x-\alpha ^{j})=g(x){\bmod {(}}x-\alpha ^{j})=0.}$$$${\displaystyle s(\alpha ^{j})=0,\ j=1,2,\ldots ,n-k.}$$

พหุนามที่ส่งมานั้นถูกเปลี่ยนแปลงระหว่างทางด้วยพหุนามผิดพลาด ทำให้ได้พหุนามที่ได้รับ $${\displaystyle e(x)=\sum _{i=0}^{n-1}e_{i}x^{i}}$$$${\displaystyle r(x)=s(x)+e(x).}$$

สัมประสิทธิ์e _iจะเป็นศูนย์หากไม่มีข้อผิดพลาดที่กำลังx นั้น และจะมีค่าไม่เป็นศูนย์หากมีข้อผิดพลาด หากมี ข้อผิดพลาด νข้อผิดพลาดที่กำลังi _k ที่แตกต่างกัน ของxแล้ว $${\displaystyle e(x)=\sum _{k=1}^{\nu }e_{i_{k}}x^{i_{k}}.}$$

เป้าหมายของตัวถอดรหัสคือการหาจำนวนข้อผิดพลาด ( ν ) ตำแหน่งของข้อผิดพลาด ( ik ) และค่าข้อผิดพลาด ณ ตำแหน่งเหล่านั้น ( eik ) จากนั้นจึงคำนวณe ( _x ) และลบออกจาก r ( _x )เพื่อ ให้ได้ข้อความที่ส่งมาแต่เดิมs ( _x )

ตัวถอดรหัสเริ่มต้นด้วยการประเมินพหุนามที่ได้รับ ณ จุดต่างๆเราเรียกผลลัพธ์ของการประเมินนั้นว่า "ซินโดรม" S _jซึ่งกำหนดไว้ดังนี้ โปรด ทราบว่าเนื่องจากมีรากที่ดังที่แสดงในส่วนก่อนหน้า ${\displaystyle \alpha ^{1}\dots \alpha ^{n-k}}$$${\displaystyle {\begin{aligned}S_{j}&=r(\alpha ^{j})=s(\alpha ^{j})+e(\alpha ^{j})=0+e(\alpha ^{j})\\&=e(\alpha ^{j})\\&=\sum _{k=1}^{\nu }e_{i_{k}}{(\alpha ^{j})}^{i_{k}},\quad j=1,2,\ldots ,n-k.\end{aligned}}}$$${\displaystyle s(\alpha ^{j})=0}$${\displaystyle s(x)}$${\displaystyle \alpha ^{j}}$

ข้อดีของการพิจารณาซินโดรมคือ พหุนามของข้อความจะหายไป กล่าวคือ ซินโดรมจะเกี่ยวข้องกับข้อผิดพลาดเท่านั้น และไม่ได้รับผลกระทบจากเนื้อหาจริงของข้อความที่กำลังส่ง หากซินโดรมทั้งหมดเป็นศูนย์ อัลกอริทึมจะหยุดทำงานและรายงานว่าข้อความไม่เสียหายระหว่างการส่ง

เพื่อความสะดวก ให้กำหนดตัวระบุตำแหน่งข้อผิดพลาดX _kและค่าข้อผิดพลาดY _kดังนี้ $${\displaystyle X_{k}=\alpha ^{i_{k}},\quad Y_{k}=e_{i_{k}}.}$$

จากนั้นสามารถเขียนกลุ่มอาการต่างๆ โดยใช้ตัวระบุตำแหน่งข้อผิดพลาดและค่าข้อผิดพลาดเหล่านี้ได้ดังนี้ $${\displaystyle S_{j}=\sum _{k=1}^{\nu }Y_{k}X_{k}^{j}.}$$

คำจำกัดความของค่ากลุ่มอาการนี้เทียบเท่ากับคำจำกัดความก่อนหน้านี้เนื่องจาก ${\displaystyle {(\alpha ^{j})}^{i_{k}}=\alpha ^{j\cdot i_{k}}={(\alpha ^{i_{k}})}^{j}=X_{k}^{j}}$

กลุ่มอาการดังกล่าวให้ระบบสมการn − k ≥ 2 νสมการใน 2 ν ตัวแปร ที่ไม่ทราบค่า แต่ระบบสมการนั้นเป็นแบบไม่เชิงเส้นในX _kและไม่มีคำตอบที่ชัดเจน อย่างไรก็ตาม หาก ทราบค่า X _k (ดูด้านล่าง) สมการกลุ่มอาการจะให้ระบบสมการเชิงเส้น ซึ่งสามารถแก้หาค่าความคลาดเคลื่อน Y _{k ได้อย่างง่ายดาย}$${\displaystyle {\begin{bmatrix}X_{1}^{1}&X_{2}^{1}&\cdots &X_{\nu }^{1}\\X_{1}^{2}&X_{2}^{2}&\cdots &X_{\nu }^{2}\\\vdots &\vdots &\ddots &\vdots \\X_{1}^{n-k}&X_{2}^{n-k}&\cdots &X_{\nu }^{n-k}\\\end{bmatrix}}{\begin{bmatrix}Y_{1}\\Y_{2}\\\vdots \\Y_{\nu }\end{bmatrix}}={\begin{bmatrix}S_{1}\\S_{2}\\\vdots \\S_{n-k}\end{bmatrix}},}$$

ดังนั้น ปัญหาจึงอยู่ที่การหาค่าX _kเพราะถ้าเป็นเช่นนั้น เมทริกซ์ด้านซ้ายสุดก็จะทราบแล้ว และทั้งสองข้างของสมการก็สามารถคูณด้วยเมทริกซ์ผกผันได้ ทำให้ได้ค่า Y _k

ในรูปแบบของอัลกอริธึมนี้ที่ทราบตำแหน่งของข้อผิดพลาดอยู่แล้ว (เมื่อใช้เป็นรหัสแก้ไข_ข้อ ผิดพลาด ) นี่คือจุดสิ้นสุด ตำแหน่งของข้อผิดพลาด ( Xk ) เป็นที่ทราบอยู่แล้วด้วยวิธีอื่น (ตัวอย่างเช่น ในการส่งสัญญาณ FM ส่วนที่บิตสตรีมไม่ชัดเจนหรือถูกรบกวนสามารถกำหนดได้โดยใช้การวิเคราะห์ความถี่ ) ในสถานการณ์นี้สามารถแก้ไขข้อผิดพลาดได้ มากถึง${\displaystyle n-k}$

ส่วนที่เหลือของอัลกอริธึมทำหน้าที่ระบุตำแหน่งของข้อผิดพลาด และจะต้องใช้ค่าซินโดรมสูงสุดถึงแทนที่จะใช้เพียงค่าที่ใช้มาจนถึงปัจจุบัน นี่คือเหตุผลที่ต้องเพิ่มสัญลักษณ์แก้ไขข้อผิดพลาดเป็นสองเท่าของจำนวนสัญลักษณ์ที่สามารถแก้ไขได้โดยไม่ทราบตำแหน่งของข้อผิดพลาดเหล่านั้น ${\displaystyle 2\nu }$${\displaystyle \nu }$

มีความสัมพันธ์เวียนเกิด เชิงเส้น ที่ก่อให้เกิดระบบสมการเชิงเส้น การแก้สมการเหล่านั้นจะ ระบุ ตำแหน่งข้อผิดพลาดX _{k เหล่านั้น}

กำหนดพหุนามระบุตำแหน่งข้อผิดพลาดΛ( x )ดังนี้ $${\displaystyle \Lambda (x)=\prod _{k=1}^{\nu }(1-xX_{k})=1+\Lambda _{1}x^{1}+\Lambda _{2}x^{2}+\cdots +\Lambda _{\nu }x^{\nu }.}$$

ค่าศูนย์ของΛ( x )คือส่วนกลับซึ่งเป็นผลมาจากการสร้างสัญลักษณ์ผลคูณข้างต้น เนื่องจากถ้าแล้วพจน์ที่คูณกันตัวใดตัวหนึ่งจะเป็นศูนย์ทำให้พหุนามทั้งหมดมีค่าเป็นศูนย์: ${\displaystyle X_{k}^{-1}}$${\displaystyle x=X_{k}^{-1}}$${\displaystyle (1-X_{k}^{-1}\cdot X_{k})=1-1=0}$$${\displaystyle \Lambda (X_{k}^{-1})=0.}$$

ให้เป็นจำนวนเต็มใดๆ ที่คูณทั้งสองข้างด้วยแล้วผลลัพธ์ก็ยังคงเป็นศูนย์: ${\displaystyle j}$${\displaystyle 1\leq j\leq \nu }$${\displaystyle Y_{k}X_{k}^{j+\nu }}$$${\displaystyle {\begin{aligned}&Y_{k}X_{k}^{j+\nu }\Lambda (X_{k}^{-1})=0,\\&Y_{k}X_{k}^{j+\nu }(1+\Lambda _{1}X_{k}^{-1}+\Lambda _{2}X_{k}^{-2}+\cdots +\Lambda _{\nu }X_{k}^{-\nu })=0,\\&Y_{k}X_{k}^{j+\nu }+\Lambda _{1}Y_{k}X_{k}^{j+\nu }X_{k}^{-1}+\Lambda _{2}Y_{k}X_{k}^{j+\nu }X_{k}^{-2}+\cdots +\Lambda _{\nu }Y_{k}X_{k}^{j+\nu }X_{k}^{-\nu }=0,\\&Y_{k}X_{k}^{j+\nu }+\Lambda _{1}Y_{k}X_{k}^{j+\nu -1}+\Lambda _{2}Y_{k}X_{k}^{j+\nu -2}+\cdots +\Lambda _{\nu }Y_{k}X_{k}^{j}=0.\end{aligned}}}$$

เมื่อรวมค่าkตั้งแต่ 1 ถึงνแล้ว ผลลัพธ์ก็ยังคงเป็นศูนย์: $${\displaystyle \sum _{k=1}^{\nu }(Y_{k}X_{k}^{j+\nu }+\Lambda _{1}Y_{k}X_{k}^{j+\nu -1}+\Lambda _{2}Y_{k}X_{k}^{j+\nu -2}+\cdots +\Lambda _{\nu }Y_{k}X_{k}^{j})=0.}$$

รวมแต่ละพจน์เข้ากับผลรวมของมันเอง: $${\displaystyle \left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j+\nu }\right)+\left(\sum _{k=1}^{\nu }\Lambda _{1}Y_{k}X_{k}^{j+\nu -1}\right)+\left(\sum _{k=1}^{\nu }\Lambda _{2}Y_{k}X_{k}^{j+\nu -2}\right)+\cdots +\left(\sum _{k=1}^{\nu }\Lambda _{\nu }Y_{k}X_{k}^{j}\right)=0.}$$

ดึงค่าคงที่ที่ไม่ได้รับผลกระทบจากการรวมผลออกมา: ${\displaystyle \Lambda }$$${\displaystyle \left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j+\nu }\right)+\Lambda _{1}\left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j+\nu -1}\right)+\Lambda _{2}\left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j+\nu -2}\right)+\cdots +\Lambda _{\nu }\left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j}\right)=0.}$$

ผลรวมเหล่านี้เทียบเท่ากับค่าซินโดรม ซึ่งเรารู้และสามารถแทนค่าได้ ดังนั้นจึงลดรูปเหลือดังนี้ $${\displaystyle S_{j+\nu }+\Lambda _{1}S_{j+\nu -1}+\cdots +\Lambda _{\nu -1}S_{j+1}+\Lambda _{\nu }S_{j}=0.}$$

ลบออกจากทั้งสองข้างจะได้ ${\displaystyle S_{j+\nu }}$$${\displaystyle S_{j}\Lambda _{\nu }+S_{j+1}\Lambda _{\nu -1}+\cdots +S_{j+\nu -1}\Lambda _{1}=-S_{j+\nu }.}$$

โปรดจำไว้ว่าjถูกเลือกให้เป็นจำนวนเต็มใดๆ ระหว่าง 1 ถึงvรวมทั้งสองค่า และความเท่าเทียมกันนี้เป็นจริงสำหรับค่าทั้งหมดดังกล่าว ดังนั้น เราจึงมี สมการเชิงเส้น vสมการ ไม่ใช่แค่สมการเดียว ระบบสมการเชิงเส้นนี้จึงสามารถแก้หาค่าสัมประสิทธิ์ Λ _iของพหุนามตำแหน่งข้อผิดพลาดได้: ข้างต้นถือว่าตัวถอดรหัสรู้จำนวนข้อผิดพลาดνแต่จำนวนนั้นยังไม่ได้ถูกกำหนด ตัวถอดรหัส PGZ ไม่ได้กำหนดνโดยตรง แต่จะค้นหาโดยการลองค่าต่างๆ ต่อเนื่องกัน ตัวถอดรหัสจะสมมติค่าที่มากที่สุดสำหรับการทดลองν ก่อน แล้วตั้งค่าระบบเชิงเส้นสำหรับค่านั้น หากสามารถแก้สมการได้ (เช่น ดีเทอร์มิแนนต์ของเมทริกซ์ไม่เป็นศูนย์) ค่าทดลองนั้นก็คือจำนวนข้อผิดพลาด หากไม่สามารถแก้ระบบเชิงเส้นได้ ค่าทดลองνจะลดลงหนึ่งค่า และจะตรวจสอบระบบที่เล็กกว่าถัดไป^{[ 16 ]}$${\displaystyle {\begin{bmatrix}S_{1}&S_{2}&\cdots &S_{\nu }\\S_{2}&S_{3}&\cdots &S_{\nu +1}\\\vdots &\vdots &\ddots &\vdots \\S_{\nu }&S_{\nu +1}&\cdots &S_{2\nu -1}\end{bmatrix}}{\begin{bmatrix}\Lambda _{\nu }\\\Lambda _{\nu -1}\\\vdots \\\Lambda _{1}\end{bmatrix}}={\begin{bmatrix}-S_{\nu +1}\\-S_{\nu +2}\\\vdots \\-S_{\nu +\nu }\end{bmatrix}}.}$$

ใช้สัมประสิทธิ์ Λ _iที่พบในขั้นตอนที่แล้วเพื่อสร้างพหุนามระบุตำแหน่งข้อผิดพลาด รากของพหุนามระบุตำแหน่งข้อผิดพลาดสามารถหาได้โดยการค้นหาอย่างละเอียด ตัวระบุตำแหน่งข้อผิดพลาดX _kคือส่วนกลับของรากเหล่านั้น ลำดับของสัมประสิทธิ์ของพหุนามระบุตำแหน่งข้อผิดพลาดสามารถกลับด้านได้ ในกรณีนี้ รากของพหุนามที่กลับด้านนั้นจะเป็นตัวระบุตำแหน่งข้อผิดพลาด(ไม่ใช่ส่วนกลับของมัน) การค้นหาแบบ Chienเป็นวิธีที่มีประสิทธิภาพในการดำเนินการขั้นตอนนี้ ${\displaystyle X_{k}}$${\displaystyle X_{k}^{-1}}$

เมื่อทราบตำแหน่งข้อผิดพลาดX _kแล้ว ก็สามารถกำหนดค่าข้อผิดพลาดได้ โดยสามารถทำได้โดยการหาค่าY _k โดยตรง จาก เมทริกซ์ สมการข้อผิดพลาดที่ให้ไว้ข้างต้น หรือโดยใช้ อัลกอริ ทึม ของ Forney

คำนวณค่าi _kโดยใช้ลอการิทึมฐานของX _kโดยทั่วไปจะทำโดยใช้ตารางค้นหา ที่คำนวณไว้ ล่วงหน้า ${\displaystyle \alpha }$

สุดท้ายe ( x ) จะถูกสร้างขึ้นจากi _kและe _{i k}จากนั้นจะถูกลบออกจากr ( x ) เพื่อให้ได้ข้อความที่ส่งมาแต่เดิมs ( x ) โดยแก้ไขข้อผิดพลาดแล้ว

พิจารณาโค้ด Reed–Solomon ที่กำหนดไว้ในGF (929)โดยที่α = 3และt = 4 (ซึ่งใช้ใน บาร์โค้ด PDF417 ) สำหรับโค้ด RS(7,3) พหุนามตัวสร้างคือ ถ้าพหุนามข้อความคือp ( x ) = 3 x ² + 2 x + 1แล้วคำรหัสที่เป็นระบบจะถูกเข้ารหัสดังนี้: ข้อผิดพลาดในการส่งอาจทำให้ได้รับสิ่งนี้แทน: ซินโดรมคำนวณโดยการประเมินrที่กำลังของα : ทำให้ได้ระบบ $${\displaystyle g(x)=(x-3)(x-3^{2})(x-3^{3})(x-3^{4})=x^{4}+809x^{3}+723x^{2}+568x+522.}$$$${\displaystyle s_{r}(x)=p(x)\,x^{t}{\bmod {g}}(x)=547x^{3}+738x^{2}+442x+455,}$$$${\displaystyle s(x)=p(x)\,x^{t}-s_{r}(x)=3x^{6}+2x^{5}+1x^{4}+382x^{3}+191x^{2}+487x+474.}$$$${\displaystyle r(x)=s(x)+e(x)=3x^{6}+2x^{5}+123x^{4}+456x^{3}+191x^{2}+487x+474.}$$$${\displaystyle S_{1}=r(3^{1})=3\cdot 3^{6}+2\cdot 3^{5}+123\cdot 3^{4}+456\cdot 3^{3}+191\cdot 3^{2}+487\cdot 3+474=732,}$$$${\displaystyle S_{2}=r(3^{2})=637,\quad S_{3}=r(3^{3})=762,\quad S_{4}=r(3^{4})=925,}$$$${\displaystyle {\begin{bmatrix}732&637\\637&762\end{bmatrix}}{\begin{bmatrix}\Lambda _{2}\\\Lambda _{1}\end{bmatrix}}={\begin{bmatrix}-762\\-925\end{bmatrix}}={\begin{bmatrix}167\\004\end{bmatrix}}.}$$

โดยใช้การ กำจัดแบบเกาส์เซียน จะ ได้รากx ₁ = 757 = 3 ⁻³และx ₂ = 562 = 3 ⁻⁴สามารถสลับสัมประสิทธิ์ได้ เพื่อให้ได้ราก 27 = 3 ³และ 81 = 3 ⁴ที่มีเลขชี้กำลังเป็นบวก แต่โดยทั่วไปแล้วจะไม่ใช้ ค่าลอการิทึมของรากที่กลับด้านจะสอดคล้องกับตำแหน่งของข้อผิดพลาด (จากขวาไปซ้าย ตำแหน่ง 0 คือพจน์สุดท้ายในรหัสคำ) $${\displaystyle {\begin{bmatrix}001&000\\000&001\end{bmatrix}}{\begin{bmatrix}\Lambda _{2}\\\Lambda _{1}\end{bmatrix}}={\begin{bmatrix}329\\821\end{bmatrix}},}$$$${\displaystyle \Lambda (x)=329x^{2}+821x+001,}$$$${\displaystyle R(x)=001x^{2}+821x+329,}$$

ในการคำนวณค่าความคลาดเคลื่อน ให้ใช้อัลกอริทึมของ Forney : $${\displaystyle \Omega (x)=S(x)\Lambda (x){\bmod {x}}^{4}=546x+732,}$$$${\displaystyle \Lambda '(x)=658x+821,}$$$${\displaystyle e_{1}=-\Omega (x_{1})/\Lambda '(x_{1})=074,}$$$${\displaystyle e_{2}=-\Omega (x_{2})/\Lambda '(x_{2})=122.}$$

การลบออกจากพหุนามที่ได้รับr ( x ) จะสร้างคำรหัสเดิมs ขึ้นมา ใหม่ ${\displaystyle e_{1}x^{3}+e_{2}x^{4}=74x^{3}+122x^{4}}$

อัลกอริทึม Berlekamp–Masseyเป็นวิธีการวนซ้ำทางเลือกสำหรับการหาพหุนามระบุตำแหน่งข้อผิดพลาด ในแต่ละรอบการวนซ้ำ จะคำนวณความคลาดเคลื่อนโดยอิงจากอินสแตนซ์ปัจจุบันของ Λ( x ) โดยมีจำนวนข้อผิดพลาดที่สมมติไว้e จาก นั้นปรับ Λ( x ) และeเพื่อให้ Δ ที่คำนวณใหม่เป็นศูนย์ บทความเรื่องอัลกอริทึม Berlekamp–Masseyมีคำอธิบายโดยละเอียดเกี่ยวกับกระบวนการนี้ ในตัวอย่างต่อไปนี้C ( x ) ถูกใช้เพื่อแทน Λ( x ) $${\displaystyle \Delta =S_{i}+\Lambda _{1}\ S_{i-1}+\cdots +\Lambda _{e}\ S_{i-e}}$$

โดยใช้ข้อมูลชุดเดียวกับตัวอย่าง Peterson Gorenstein Zierler ด้านบน:

ค่าสุดท้ายของCคือพหุนามระบุตำแหน่งข้อผิดพลาด Λ( x )

อีกวิธีหนึ่งที่ใช้การวนซ้ำในการคำนวณทั้งพหุนามระบุตำแหน่งข้อผิดพลาดและพหุนามค่าข้อผิดพลาดนั้น อิงตามการดัดแปลงอัลกอริธึมยุคลิดแบบขยาย ของซูกิยา มะ

กำหนดS ( x ), Λ( x ) และ Ω( x ) สำหรับ ซินโดรม tและ ข้อผิดพลาด e : $${\displaystyle {\begin{aligned}S(x)&=S_{t}x^{t-1}+S_{t-1}x^{t-2}+\cdots +S_{2}x+S_{1}\\[1ex]\Lambda (x)&=\Lambda _{e}x^{e}+\Lambda _{e-1}x^{e-1}+\cdots +\Lambda _{1}x+1\\[1ex]\Omega (x)&=\Omega _{e}x^{e}+\Omega _{e-1}x^{e-1}+\cdots +\Omega _{1}x+\Omega _{0}\end{aligned}}}$$

สมการสำคัญคือ: $${\displaystyle \Lambda (x)S(x)=Q(x)x^{t}+\Omega (x)}$$

สำหรับt = 6 และe = 3: $${\displaystyle {\begin{bmatrix}\Lambda _{3}S_{6}&x^{8}\\\Lambda _{2}S_{6}+\Lambda _{3}S_{5}&x^{7}\\\Lambda _{1}S_{6}+\Lambda _{2}S_{5}+\Lambda _{3}S_{4}&x^{6}\\S_{6}+\Lambda _{1}S_{5}+\Lambda _{2}S_{4}+\Lambda _{3}S_{3}&x^{5}\\S_{5}+\Lambda _{1}S_{4}+\Lambda _{2}S_{3}+\Lambda _{3}S_{2}&x^{4}\\S_{4}+\Lambda _{1}S_{3}+\Lambda _{2}S_{2}+\Lambda _{3}S_{1}&x^{3}\\S_{3}+\Lambda _{1}S_{2}+\Lambda _{2}S_{1}&x^{2}\\S_{2}+\Lambda _{1}S_{1}&x\\S_{1}\end{bmatrix}}={\begin{bmatrix}Q_{2}x^{8}\\Q_{1}x^{7}\\Q_{0}x^{6}\\0\\0\\0\\\Omega _{2}x^{2}\\\Omega _{1}x\\\Omega _{0}\end{bmatrix}}}$$

ค่าตรงกลางเป็นศูนย์เนื่องจากความสัมพันธ์ระหว่าง Λ และกลุ่มอาการ

อัลกอริทึมยุคลิดแบบขยายสามารถค้นหาอนุกรมของพหุนามในรูปแบบดังกล่าวได้

โดยที่ระดับของRจะลดลงเมื่อiเพิ่มขึ้น เมื่อระดับของR _i ( x ) < t /2 แล้ว

ไม่จำเป็นต้องบันทึก B ( x ) และQ ( x ) ดังนั้นอัลกอริทึมจึงเป็นดังนี้:

R −1  := x t R 0  := S ( x ) A −1  := 0 A 0  := 1 i  := 0 ในขณะที่ดีกรีของR i ≥ t /2 i  := i + 1 Q  := R i -2 / R i -1 R i  := R i -2 - Q R i -1 A i  := A i -2 - Q A i -1