การแก้ไขข้อผิดพลาดแบบ Reed–Solomon

ชื่ออื่น: รหัส Reed-Solomon, รหัส RS, Reed-Solomon code

คำนิยาม

การแก้ไขข้อผิดพลาดแบบ Reed–Solomon คือคณิตศาสตร์ที่ทำให้ QR Code ที่เสียหายยังสแกนติด เพิ่มโค้ดเวิร์ดตรวจสอบเข้ากับข้อมูล เพื่อให้เครื่องอ่านสร้างไบต์ที่หายหรือผิดกลับมาได้ ภายในขีดจำกัดที่กำหนด

ตรวจสอบโดยทีม AriaQR ·

ดูตอนนี้ · 2:06Why Damaged QR Codes Still Scan: Error Correction Levels Explained
การแก้ไขข้อผิดพลาดแบบ Reed–Solomon

ที่มาและการใช้ในวงกว้าง

Irving S. Reed และ Gustave Solomon อธิบายรหัส Reed–Solomon ในปี 1960 รหัสนี้ทำงานกับสัญลักษณ์ทั้งชุด ซึ่งมักเป็นไบต์ ไม่ใช่ทีละบิต จึงเก่งในการจัดการความเสียหายที่ติดกันเป็นกลุ่ม เช่นรอยขีดข่วนหรือรอยเปื้อน

รหัสตระกูลเดียวกันนี้ปกป้องข้อมูลบนแผ่น CD, DVD และ Blu-ray ในโทรทัศน์ดิจิทัลและลิงก์ดาวเทียมบางระบบ และในบาร์โค้ด 2 มิติอื่น ๆ รวมถึง Data Matrix ECC 200, Aztec Code และ PDF417

QR Code ใช้อย่างไร

QR Code ถือว่าโค้ดเวิร์ด 8 บิตแต่ละตัวเป็นสมาชิกของฟีลด์จำกัด GF(256) ที่สร้างด้วยพหุนามพื้นฐาน x^8 + x^4 + x^3 + x^2 + 1 (เลขฐานสิบหก 0x11D) โค้ดเวิร์ดข้อมูลถูกหารด้วยพหุนามตัวกำเนิด และเศษที่เหลือกลายเป็นโค้ดเวิร์ดแก้ไขข้อผิดพลาดที่ต่อท้ายข้อมูล

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

แก้ได้แค่ไหน

เมื่อมีโค้ดเวิร์ดแก้ไขข้อผิดพลาด n ตัวในบล็อก ตัวถอดรหัสแก้ได้สูงสุด n/2 โค้ดเวิร์ดที่ไม่รู้ตำแหน่ง หรือสูงสุด n โค้ดเวิร์ดที่รู้ตำแหน่ง เรียกว่า erasure กรณีผสมเป็นไปตามกฎว่าข้อผิดพลาดแต่ละตัวนับสองและ erasure แต่ละตัวนับหนึ่ง

นี่คือเหตุที่โค้ดที่มีพื้นที่เรียบสะอาดถูกโลโก้บังยังสแกนได้ เครื่องอ่านที่ฉลาดอาจถือว่าพื้นที่ที่ถูกบังเป็น erasure ขณะที่ความเสียหายแบบสุ่มแก้ยากกว่า เพราะตัวถอดรหัสต้องหาให้เจอก่อน

  • ข้อผิดพลาดที่ไม่รู้ตำแหน่ง: สูงสุดครึ่งหนึ่งของจำนวนโค้ดเวิร์ด EC
  • Erasure (รู้ตำแหน่ง): สูงสุดเท่าจำนวนโค้ดเวิร์ด EC
  • ฟีลด์: GF(256) พหุนาม 0x11D
  • สอดแทรกบล็อกเพื่อกระจายความเสียหายที่ติดกัน

คำถามที่พบบ่อย

Reed–Solomon ใน QR Code คืออะไร

คือวิธีแก้ไขข้อผิดพลาดที่เพิ่มโค้ดเวิร์ดเสริมเข้ากับข้อมูล เครื่องสแกนใช้โค้ดเวิร์ดเหล่านั้นสร้างโค้ดเวิร์ดที่เสียหายหรืออ่านไม่ได้กลับมา

ใครคิดค้นรหัส Reed–Solomon

Irving S. Reed และ Gustave Solomon ซึ่งเผยแพร่ในปี 1960 ปัจจุบันรหัสนี้ใช้ในแผ่นออปติคัล การสื่อสาร และบาร์โค้ด 2 มิติส่วนใหญ่

ทำไม QR Code ที่มีโลโก้ตรงกลางยังใช้ได้

โลโก้บังโมดูลที่การแก้ไขข้อผิดพลาดแบบ Reed–Solomon สร้างกลับมาได้ ใช้ได้ตราบที่พื้นที่ที่ถูกบังยังอยู่ในความสามารถของการแก้ไขข้อผิดพลาด และ Finder Pattern ยังโล่ง

แหล่งที่มาและมาตรฐาน

คำศัพท์ทั้งหมด