Skip to content
กลับไปยังผลการค้นหา

รหัสโพลาร์ที่ถอดรหัสแบบตัดออกต่อเนื่อง (Polar Codes with Successive Cancellation Decoding)

ผู้เสนอ
Erdal Arikan
ปี
2009
ประเภท
recursive error-correcting code
กลุ่มวิธี
Coding theory

ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ

ขนาดตัวอักษร

ใช้ทำอะไร?

รหัสโพลาร์ (Polar codes) ซึ่งเสนอโดย Erdal Arikan ในปี 2009 เป็นตระกูลแรกของรหัสที่มีวิธีสร้างอย่างชัดแจ้ง (explicit construction) ซึ่งได้รับการพิสูจน์แล้วว่าสามารถบรรลุค่า Shannon capacity ของช่องสัญญาณแบบสมมาตรที่มีอินพุตเป็นเลขฐานสองและไม่มีหน่วยความจำได้ รหัสเหล่านี้ใช้การสร้างแบบเวียนซ้ำ (recursive construction) และการถอดรหัสแบบ successive cancellation ซึ่งเป็นอัลกอริทึมแบบโลภ (greedy algorithm) ที่เรียบง่ายพร้อมการรับประกันทางทฤษฎี รหัสโพลาร์ได้รับการนำไปใช้ใน 5G NR สำหรับการเข้ารหัสช่องสัญญาณควบคุม และกำลังมีการศึกษาสำหรับระบบ 6G ในอนาคต ซึ่งแตกต่างจากรหัส turbo และ LDPC (ซึ่งเป็นไปตามการสังเกตเชิงประจักษ์) รหัสโพลาร์มีพื้นฐานทางทฤษฎีที่เข้มงวด

แนวคิดเบื้องหลังวิธีการ

รหัสโพลาร์มีพื้นฐานมาจากแนวคิดของ channel polarization: การใช้การแปลงแบบเวียนซ้ำที่เฉพาะเจาะจงกับชุดของช่องสัญญาณอิสระที่เหมือนกัน จะสร้างชุดใหม่ที่ช่องสัญญาณบางส่วนกลายเป็นช่องสัญญาณที่ไม่มีสัญญาณรบกวนอย่างมีประสิทธิภาพ (capacity 1) และช่องสัญญาณอื่นๆ กลายเป็นช่องสัญญาณที่ไร้ประโยชน์อย่างมีประสิทธิภาพ (capacity 0) บิตข้อมูลจะถูกวางไว้บนช่องสัญญาณที่ไม่มีสัญญาณรบกวน; บิตแช่แข็ง (frozen bits) (ที่ผู้รับทราบ) จะเติมเต็มช่องสัญญาณที่ไร้ประโยชน์ การถอดรหัสใช้ successive cancellation: ถอดรหัสทีละบิตตามลำดับ โดยใช้บิตที่ถอดรหัสไปแล้วเพื่อปรับปรุงค่าประมาณของบิตที่เหลือ โครงสร้างแบบเวียนซ้ำทำให้มั่นใจได้ว่าความซับซ้อนในการถอดรหัสเป็นเชิงเส้นตามความยาวรหัส และคุณสมบัติ polarization รับประกันประสิทธิภาพการบรรลุค่า capacity เชิงเส้นกำกับ

ประวัติศาสตร์

เอกสารปี 2009 ของ Arikan เกี่ยวกับ channel polarization เป็นจุดเปลี่ยน: เป็นครั้งแรกที่ตระกูลรหัสที่มีวิธีสร้างอย่างชัดแจ้งได้รับการพิสูจน์ว่าสามารถบรรลุค่า capacity ได้ด้วยความซับซ้อนแบบพหุนาม งานวิจัยต่อมาได้พัฒนาตัวถอดรหัสที่ใช้งานได้จริง (belief propagation, list decoding) เพื่อแก้ไขปัญหา error floor ที่ SNR ปานกลาง รหัสโพลาร์ได้รับการนำไปใช้ใน 3GPP 5G NR Release 15 สำหรับช่องสัญญาณควบคุม (เช่น PBCH, DCI) แทนที่รหัส turbo สำหรับช่องสัญญาณข้อมูล LDPC ได้รับการเลือกเนื่องจากประสิทธิภาพเชิงประจักษ์ที่ดีกว่าที่ความยาวบล็อกปานกลาง Arikan ได้รับรางวัล IEEE Information Theory Society paper award และรหัสโพลาร์ยังคงเป็นหัวข้อวิจัยที่สำคัญ

ควรใช้เมื่อใด

รหัสโพลาร์เหมาะอย่างยิ่งสำหรับความยาวแพ็กเก็ตสั้นถึงปานกลาง (100-1000 บิต) และข้อกำหนดด้านความหน่วง (latency) ที่เข้มงวด (ไม่มีการถอดรหัสแบบวนซ้ำ) ใช้รหัสโพลาร์สำหรับช่องสัญญาณควบคุมใน 5G/6G หรือสถานการณ์ใดๆ ที่ให้ความสำคัญกับการรับประกันการบรรลุค่า capacity ที่พิสูจน์ได้ หลีกเลี่ยงรหัสโพลาร์สำหรับ codeword ที่ยาวมาก (>10k บิต) ซึ่งความยืดหยุ่นของ LDPC เป็นข้อได้เปรียบ รหัสโพลาร์มีความโดดเด่นในช่องสัญญาณแบบ block-fading; ใน flat fading จะไม่มีข้อได้เปรียบที่เฉพาะเจาะจงเหนือ LDPC

ข้อจำกัดและข้อควรพิจารณา

  • Successive cancellation มีการแพร่กระจายข้อผิดพลาดแบบเอกซ์โพเนนเชียลที่ SNR ต่ำ (error floor)
  • การออกแบบบิตแช่แข็งจำเป็นต้องทราบ SNR ของช่องสัญญาณล่วงหน้า; จำเป็นต้องมีการปรับตัว
  • ประสิทธิภาพที่ความยาวบล็อกสั้นด้อยกว่า LDPC/turbo หากไม่มีการปรับเปลี่ยนที่ชาญฉลาด
  • Belief propagation หรือ list decoding (เพื่อลด error floor) เพิ่มความซับซ้อน เข้าใกล้ LDPC
  • ระบบนิเวศการใช้งานยังไม่สมบูรณ์เท่ารหัส turbo และ LDPC

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

จุดแข็ง

  • ตระกูลรหัสแรกที่มีการพิสูจน์เชิงโครงสร้างว่าบรรลุ Shannon capacity
  • การถอดรหัสแบบ successive cancellation ที่เรียบง่าย; ความซับซ้อนเชิงเวลาแบบเกือบเชิงเส้น O(N log N)
  • โครงสร้างแบบเวียนซ้ำช่วยให้สามารถนำไปใช้งานได้อย่างมีประสิทธิภาพในฮาร์ดแวร์
  • ไม่มีการประมวลผลแบบวนซ้ำ; ความหน่วง (latency) ที่แน่นอน (สำคัญสำหรับระบบเรียลไทม์)
  • กรอบการทำงานทางทฤษฎีสำหรับการวิเคราะห์ประสิทธิภาพและการหาค่าเหมาะที่สุดของการสร้างรหัส
  • การปรับตัวโดยธรรมชาติผ่านการเลือกบิตแช่แข็งสำหรับ SNR และความยาวบล็อกที่แตกต่างกัน

การประยุกต์ใช้

  • ช่องสัญญาณควบคุม 5G NR (PBCH, DCI): การส่งข้อมูลแพ็กเก็ตสั้นที่เชื่อถือได้พร้อมข้อจำกัดด้านความหน่วง (latency) ที่เข้มงวด
  • การสื่อสารผ่านดาวเทียม: การเข้ารหัสที่มีโครงสร้างพร้อมความหน่วง (latency) ในการถอดรหัสที่แน่นอนสำหรับลิงก์ที่สำคัญต่อภารกิจ
  • การกระจายคีย์ควอนตัม: ความปลอดภัยทางทฤษฎีร่วมกับการแก้ไขข้อผิดพลาดที่ใช้งานได้จริง
  • Telemetry การบินและอวกาศ: การสื่อสารยานอวกาศที่มีความน่าเชื่อถือสูงพิเศษและความล่าช้าในการถอดรหัสที่จำกัด
  • การสื่อสารด้วยแสง: ระยะสั้นแต่ลิงก์ความเร็วสูงที่ต้องการการถอดรหัสแบบกำหนดเวลาที่รวดเร็ว

วิธีการทำงาน

วิธีการทำงาน

1

บิตข้อมูล (รวมถึงบิตแช่แข็ง) จะประกอบกันเป็น codeword ผ่านเมทริกซ์ตัวก่อกำเนิด (generator matrix) ที่สร้างขึ้นแบบเวียนซ้ำ (โครงสร้างแบบ Kronecker product)

2

เมทริกซ์ตัวก่อกำเนิด G ถูกสร้างขึ้นโดยการทำ Kronecker product ซ้ำๆ ของ [[1,0],[1,1]]; สิ่งนี้จะสร้างโครงสร้าง polarization แบบเวียนซ้ำ

3

บิตที่เข้ารหัสจะถูกส่งออกไป; บิตที่ได้รับจะเป็นค่าแบบ soft (log-likelihood ratios จากช่องสัญญาณ)

4

ตัวถอดรหัสแบบ successive cancellation จะประมวลผลบิตตามลำดับ: สำหรับบิต i มันจะคำนวณ conditional log-likelihood ratio โดยพิจารณาจากบิตที่ถอดรหัสก่อนหน้าทั้งหมดและการสังเกตช่องสัญญาณ

5

บิตแต่ละบิตจะถูกถอดรหัสโดยการตัดค่า LLR (ค่าบวก -> 1, ค่าลบ -> 0) หากบิต i เป็นบิตแช่แข็ง จะใช้ค่าที่ทราบ บิตที่ถอดรหัสจะถูกป้อนไปข้างหน้าเพื่อปรับปรุงค่าประมาณ LLR สำหรับบิตที่เหลือ

ข้อผิดพลาดที่พบบ่อย

  • การใช้ successive cancellation พื้นฐานที่ SNR ต่ำ; จำเป็นต้องใช้ belief propagation หรือ list decoding เพื่อให้ได้ BER ที่สมเหตุสมผล
  • การออกแบบชุดบิตแช่แข็งสำหรับสภาพช่องสัญญาณที่ไม่ถูกต้อง; ประสิทธิภาพจะลดลงหาก SNR จริงแตกต่างจาก SNR ที่ออกแบบ
  • การสันนิษฐานความซับซ้อนในการถอดรหัสเชิงเส้นหมายถึงการถอดรหัสที่รวดเร็ว; บิตแต่ละบิตยังคงต้องการการคำนวณ LLR ซึ่งรวมกันเป็น O(N log N) ทั้งหมด
  • การละเลยผลจากการควอนไทซ์; การควอนไทซ์ LLR แบบ fixed-point (โดยเฉพาะการตัดสินใจแบบแยกสาขา) ส่งผลต่อ error floor
  • การไม่ใช้ประโยชน์จากการปรับตัว; การเลือกชุดบิตแช่แข็งใหม่ตามการตอบสนอง CSI สามารถปรับปรุงประสิทธิภาพได้อย่างมาก

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

Channel polarization คืออะไร และช่วยให้รหัสที่บรรลุค่า capacity ได้อย่างไร?

Channel polarization แปลงช่องสัญญาณที่เหมือนกัน N ช่อง ให้เป็น N ช่องที่มีค่า capacity ที่แบ่งขั้ว: บางช่องเข้าใกล้ 1 (ไม่มีสัญญาณรบกวน) บางช่องเข้าใกล้ 0 (ไร้ประโยชน์) บิตข้อมูลบนช่องสัญญาณที่มี capacity สูงจะได้รับการปกป้อง ช่องสัญญาณที่มี capacity ต่ำจะถูกแช่แข็ง เมื่อ N เพิ่มขึ้น สัดส่วนของช่องสัญญาณที่มี capacity สูงจะเข้าใกล้ Shannon capacity โครงสร้างนี้ช่วยให้การถอดรหัสแบบ successive cancellation ที่เรียบง่ายสามารถบรรลุค่า capacity ได้

เหตุใด successive cancellation จึงมี error floor ที่ SNR ต่ำ?

Successive cancellation ถอดรหัสทีละบิตโดยใช้ค่าประมาณบิตก่อนหน้า หากบิตแรกๆ ถูกถอดรหัสผิดพลาด ข้อผิดพลาดจะแพร่กระจายไปยังบิตที่ตามมาทั้งหมด ทำให้เกิดข้อผิดพลาดต่อเนื่อง Error floor นี้เกิดจากความขึ้นอยู่กับการตัดสินใจในอดีต Belief propagation หรือ list decoding ช่วยลดปัญหานี้โดยการสำรวจทางเลือกต่างๆ และเลื่อนการตัดสินใจแบบ hard decision

บิตแช่แข็งถูกเลือกอย่างไร?

บิตแช่แข็งจะถูกวางไว้บนช่องสัญญาณที่มีค่า mutual information โดยประมาณต่ำ (capacity ต่ำ) วิธีหนึ่งคือการจำลองกระบวนการ polarization สำหรับ SNR และความยาวบล็อกเป้าหมาย โดยจัดอันดับช่องสัญญาณตามค่า capacity จากนั้นจึงแช่แข็งช่องสัญญาณที่มี capacity ต่ำที่สุด K ช่อง สิ่งนี้จำเป็นต้องทราบ SNR ล่วงหน้า รหัสโพลาร์แบบปรับตัวได้สามารถอัปเดตชุดบิตแช่แข็งตามการตอบสนองหรือการประมาณค่า CSI

List decoding สำหรับรหัสโพลาร์คืออะไร?

แทนที่จะทำการตัดสินใจแบบ hard decision เพียงครั้งเดียวในแต่ละขั้นตอน list decoding จะเก็บรายการของ partial codewords ที่เป็นไปได้และสำรวจหลายเส้นทาง หลังจากประมวลผลบิตทั้งหมดแล้ว จะเลือกเส้นทางที่ดีที่สุด (ตาม likelihood) สิ่งนี้ช่วยลด error floor ได้อย่างมาก แต่เพิ่มความซับซ้อนเป็น O(L N log N) โดยที่ L คือขนาดของ list ขนาด list 8-32 เป็นเรื่องปกติ ซึ่งเป็นสมดุลที่ดีระหว่างประสิทธิภาพและความซับซ้อน

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Arikan, E. (2009). Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels. IEEE Transactions on Information Theory, 55(7), 3051-3073.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. Sasoglu, E., Telatar, I., & Yildirim, E. (2011). Polarization for arbitrary discrete memoryless channels. In Proceedings of the IEEE Information Theory Workshop (ITW), 144-148.

    เปิดเอกสารอ้างอิงสิ่งพิมพ์
    คัดลอกแล้ว