รหัสตรวจสอบพาริตีแบบความหนาแน่นต่ำ (LDPC)
- ผู้เสนอ
- Robert Gallager
- ปี
- 1962
- ประเภท
- linear error-correcting code
- กลุ่มวิธี
- Coding theory
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
รหัส LDPC ซึ่งประดิษฐ์โดย Robert Gallager ในปี 1962 และถูกค้นพบอีกครั้งในทศวรรษ 1990 โดย MacKay เป็นรหัสแก้ไขข้อผิดพลาดเชิงเส้นที่กำหนดโดยเมทริกซ์ตรวจสอบพาริตีแบบเบาบาง รหัสเหล่านี้ให้ประสิทธิภาพใกล้เคียงขีดจำกัดของ Shannon เพียง 0.4 dB ด้วยการถอดรหัสแบบแพร่กระจายความเชื่อแบบวนซ้ำ และได้กลายเป็นมาตรฐานสำหรับระบบไร้สายสมัยใหม่ (WiFi-6, 5G NR, Digital Video Broadcasting) ซึ่งแตกต่างจากรหัสเทอร์โบ รหัส LDPC มีโครงสร้างทฤษฎีกราฟที่สง่างามกว่าและการวิเคราะห์เชิงทฤษฎีที่สมบูรณ์กว่า
แนวคิดเบื้องหลังวิธีการ
รหัสเชิงเส้นมาตรฐานใช้เมทริกซ์ตรวจสอบพาริตีแบบหนาแน่น ทำให้การถอดรหัสต้องใช้การคำนวณสูง รหัส LDPC กลับกัน: เมทริกซ์ตรวจสอบพาริตีจะเบาบาง (ส่วนใหญ่เป็นศูนย์) ดังนั้นการตรวจสอบพาริตีแต่ละครั้งจึงเกี่ยวข้องกับบิตเพียงไม่กี่บิต ที่ตัวรับ จะมีการสร้างกราฟสองส่วน โดยโหนดตัวแปรแทนบิตที่ส่ง และโหนดตรวจสอบแทนข้อจำกัดพาริตี การถอดรหัสจะกลายเป็นการส่งข้อความแบบวนซ้ำบนกราฟนี้: โหนดตัวแปรแต่ละโหนดจะรวบรวมข้อมูลจากเพื่อนบ้าน อัปเดตความเชื่อเกี่ยวกับค่าบิต และส่งค่าประมาณที่ปรับปรุงแล้วกลับไป ความเบาบางช่วยให้การลู่เข้าเร็วและประสิทธิภาพใกล้เคียง Shannon
ประวัติศาสตร์
Gallager ประดิษฐ์รหัส LDPC ในปี 1962 แต่ทฤษฎีตามหลังการใช้งานจริง ในปี 1995 MacKay ค้นพบอีกครั้งและแสดงให้เห็นถึงประสิทธิภาพใกล้เคียง Shannon ผ่านการจำลอง การวิจัยอย่างกว้างขวางในช่วงปี 2000 ได้พัฒนาอัลกอริทึมการเข้ารหัส การถอดรหัส และการสร้างกราฟที่มีประสิทธิภาพ รหัส LDPC ถูกนำมาใช้ใน WiFi-6 (802.11ax, 2021) และมาตรฐาน 5G NR (2018) รหัสเหล่านี้ได้กลายเป็นที่แพร่หลายมากกว่ารหัสเทอร์โบในระบบใหม่เนื่องจากประสิทธิภาพที่ดีกว่าและโครงสร้างที่ชัดเจนกว่า
ควรใช้เมื่อใด
รหัส LDPC เป็นที่นิยมมากกว่ารหัสเทอร์โบในระบบสมัยใหม่เนื่องจากประสิทธิภาพที่ดีกว่าและสถาปัตยกรรมที่ง่ายกว่า ใช้ LDPC สำหรับช่วง SNR กว้าง (ไม่มีพฤติกรรมหน้าผาของค่าขีดจำกัด); ทำงานได้ดีตั้งแต่ SNR ต่ำถึงสูง LDPC เป็นมาตรฐานสำหรับ WiFi-6, ดาวเทียม และ 5G NR หลีกเลี่ยง LDPC เฉพาะเมื่อความเข้ากันได้แบบเดิมต้องการรหัสเทอร์โบ LDPC ยังเหมาะสำหรับแพ็กเก็ตสั้นมาก (>30 บิต) เนื่องจากโครงสร้างรหัสสามารถแยกส่วนได้
ข้อจำกัดและข้อควรพิจารณา
- การสร้างกราฟและการจัดเก็บเมทริกซ์มีความซับซ้อนสำหรับรหัสที่ยาวมาก (>10k บิต)
- ประสิทธิภาพไวต่อโครงสร้างกราฟขนาดเล็ก (วงรอบ, เซตดูดซับ); ต้องการการออกแบบอย่างระมัดระวัง
- การแพร่กระจายความเชื่อสมมติว่ากราฟมีวงรอบ แต่กราฟมีวงจร; การลู่เข้าสู่ผลเฉลยที่เหมาะสมที่สุดไม่รับประกัน
- ความหน่วงในการถอดรหัส (จำนวนรอบ) เพิ่มขึ้นตามลอการิทึมของ SNR; ไม่ใช่การหน่วงเวลาเป็นศูนย์เหมือนรหัสคลาสสิกบางชนิด
- การควอนไทซ์ข้อความ (ในฮาร์ดแวร์เลขฐานสิบหก) ส่งผลต่อประสิทธิภาพ; ต้องการการจัดสรรบิตอย่างระมัดระวัง
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- ประสิทธิภาพใกล้เคียงขีดจำกัด Shannon เพียง 0.4 dB (ดีกว่ารหัสเทอร์โบเล็กน้อย)
- โครงสร้างทฤษฎีกราฟที่ง่ายกว่า; การวิเคราะห์เชิงทฤษฎีที่ชัดเจนกว่ารหัสเทอร์โบ
- การถอดรหัสแบบวนซ้ำหลีกเลี่ยงพฤติกรรมค่าขีดจำกัดที่เหมือนหน้าผา (ต่างจากเทอร์โบ)
- การออกแบบรหัสที่ยืดหยุ่นผ่านการสร้างกราฟ; ง่ายต่อการปรับให้เหมาะกับการใช้งานเฉพาะ
- ฮาร์ดแวร์ถอดรหัสแบบขนานที่มีประสิทธิภาพ; การส่งข้อความเหมาะกับการใช้งาน VLSI/GPU
- ทำงานได้ดีสำหรับทั้งรหัสคำยาวและรหัสคำสั้นปานกลาง
การประยุกต์ใช้
- WiFi-6 (802.11ax): เครือข่ายท้องถิ่นไร้สายที่มีอัตราการส่งข้อมูลสูง โดย LDPC ให้การส่งข้อมูลที่เชื่อถือได้
- 5G NR: การเข้ารหัสช่องสัญญาณสำหรับทั้งช่องสัญญาณข้อมูลและช่องสัญญาณควบคุม แทนที่รหัสเทอร์โบจาก 4G
- การสื่อสารผ่านดาวเทียม: การแพร่ภาพวิดีโอดิจิทัล (DVB-S2) และภารกิจในอวกาศลึกโดยใช้ LDPC รหัสคำยาว
- การสื่อสารผ่านสายไฟฟ้า (PLC): การส่งข้อมูลที่ทนทานผ่านโครงข่ายไฟฟ้าที่มีสัญญาณรบกวน
- ระบบหน่วยความจำแฟลช: การแก้ไขข้อผิดพลาดสำหรับที่เก็บข้อมูลแฟลช NAND โดยไม่เกิดการสึกหรอจากการรีเฟรชบ่อยครั้ง
วิธีการทำงาน
วิธีการทำงาน
บิตข้อมูลจะถูกเข้ารหัสโดยใช้เมทริกซ์ตรวจสอบพาริตีแบบเบาบาง H; บิตที่เข้ารหัสคือผลเฉลยของ H*c = 0 (mod 2) โดยที่ c คือรหัสคำ (codeword)
เมทริกซ์ตรวจสอบพาริตี H ถูกจัดโครงสร้างให้เบาบาง (เช่น แต่ละแถว/คอลัมน์มีน้ำหนักต่ำคงที่ 3-5) โครงสร้างนี้ถูกนำมาใช้ประโยชน์สำหรับการเข้ารหัสที่มีประสิทธิภาพ
บิตที่เข้ารหัสจะถูกส่งผ่านช่องสัญญาณที่มีสัญญาณรบกวน บิตที่ได้รับจะเป็นค่าแบบอ่อน (อัตราส่วนความเป็นไปได้ หรืออัตราส่วนล็อกความเป็นไปได้)
มีการสร้างกราฟสองส่วน: โหนดซ้าย = โหนดตัวแปร (บิต), โหนดขวา = โหนดตรวจสอบ (สมการพาริตี) เส้นเชื่อมโยงตัวแปรเข้ากับส่วนตรวจสอบที่ปรากฏอยู่
การแพร่กระจายความเชื่อแบบวนซ้ำ: โหนดตัวแปรจะรวบรวมข้อความจากโหนดตรวจสอบ อัปเดตค่าประมาณบิต และส่งข้อความที่ปรับปรุงแล้วกลับไป หลังจากการวนซ้ำ จะมีการตัดสินใจแบบแข็ง (hard decision) หากการตรวจสอบพาริตีเป็นที่พอใจ การถอดรหัสจะสำเร็จ
ข้อผิดพลาดที่พบบ่อย
- การใช้กราฟเบาบางที่ออกแบบไม่ดีซึ่งมีวงรอบสั้น; วงรอบสั้นทำให้การแพร่กระจายความเชื่อเกิดการแกว่ง
- การวนซ้ำมากเกินไปหลังจากการลู่เข้า; การวนซ้ำที่ไม่จำเป็นทำให้สิ้นเปลืองพลังงานโดยไม่มีการปรับปรุง
- การสมมติว่าการถอดรหัสแบบ min-sum ดีเท่ากับ sum-product; การประมาณค่ามีการสูญเสียประสิทธิภาพ โดยเฉพาะอย่างยิ่งที่ SNR ต่ำ
- การละเลยผลกระทบความยาวจำกัด; กราฟที่ออกแบบมาสำหรับการวิเคราะห์เชิงเส้นอาจมีประสิทธิภาพต่ำกว่าสำหรับแพ็กเก็ตสั้น
- การไม่คำนึงถึงการควอนไทซ์ในการใช้งานฮาร์ดแวร์; การจำลองแบบเลขทศนิยมแตกต่างจากความเป็นจริงแบบเลขฐานสิบหก
คำถามที่พบบ่อย
อะไรทำให้การถอดรหัส LDPC มีประสิทธิภาพมากเมื่อเทียบกับรหัสเชิงเส้นทั่วไป?
ความเบาบางของเมทริกซ์ตรวจสอบพาริตีหมายความว่าบิตแต่ละบิตมีส่วนร่วมในการตรวจสอบพาริตีเพียงไม่กี่ครั้ง ในระหว่างการถอดรหัส การส่งข้อความบนกราฟสองส่วนเป็นเชิงเส้นตามจำนวนเส้นเชื่อม ไม่ใช่ความยาวรหัส สำหรับรหัสที่หนาแน่น การถอดรหัสจะต้องใช้การผกผันเมทริกซ์ ซึ่งเป็นกำลังสามของความยาวรหัส ความเบาบางทำให้การถอดรหัสเกือบเป็นเชิงเส้นและใช้งานได้จริงสำหรับรหัสยาว
เซตดูดซับ (absorbing set) คืออะไร และทำไมจึงสำคัญ?
เซตดูดซับคือส่วนย่อยของกราฟที่สามารถกักการถอดรหัสแบบแพร่กระจายความเชื่อ ทำให้ไม่สามารถลู่เข้าสู่ผลเฉลยที่ถูกต้องได้ เซตเหล่านี้เป็นสาเหตุหลักของข้อผิดพลาด (การลดลงของ BER ที่ไม่เป็นแบบเอกซ์โพเนนเชียลที่ SNR ต่ำ) ผู้ออกแบบรหัสจะหลีกเลี่ยงเซตดูดซับสั้นๆ ผ่านการสร้างกราฟอย่างระมัดระวัง เครื่องมือวิเคราะห์ (เช่น การวิเคราะห์เซตหยุด) จะระบุโครงสร้างที่มีปัญหา
LDPC เปรียบเทียบกับรหัสโพลาร์อย่างไร?
ทั้งสองให้ประสิทธิภาพใกล้เคียง Shannon รหัสโพลาร์มีโครงสร้างแบบเวียนซ้ำและมีประสิทธิภาพที่พิสูจน์ได้ภายใต้การถอดรหัสแบบต่อเนื่อง (successive cancellation) ที่ความยาวรหัสอนันต์ รหัส LDPC มีความยืดหยุ่นมากกว่าและมีประสิทธิภาพความยาวจำกัดที่ดีกว่าตามประสบการณ์ 5G NR ใช้รหัสโพลาร์สำหรับช่องสัญญาณควบคุม (แพ็กเก็ตสั้น) และ LDPC สำหรับช่องสัญญาณข้อมูล (แพ็กเก็ตยาว) โดยใช้ประโยชน์จากจุดแข็งของแต่ละรหัส
เหตุใดวงรอบของกราฟ (girth) จึงมีความสำคัญในรหัส LDPC?
วงรอบของกราฟคือความยาวของวงจรที่สั้นที่สุดในกราฟสองส่วน วงรอบสั้น (girth < 6) ทำให้การแพร่กระจายความเชื่อใช้ข้อมูลที่สัมพันธ์กัน (ข้อความวนกลับ) ทำให้ประสิทธิภาพลดลง รหัสที่มีวงรอบยาว (girth ≥ 6) จะแยกความสัมพันธ์ได้ดีกว่า รหัสมักถูกออกแบบมาเพื่อเพิ่มวงรอบสูงสุดภายใต้ข้อจำกัดด้านความเบาบาง
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Gallager, R. G. (1962). Low-density parity-check codes. IRE Transactions on Information Theory, 8(1), 21-28.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้วRichardson, T. J., & Urbanke, R. L. (2001). The capacity of low-density parity-check codes under message-passing decoding. IEEE Transactions on Information Theory, 47(2), 599-618.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้ว