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

การเข้ารหัสแบบเทอร์โบพร้อมการถอดรหัสแบบวนซ้ำ

ผู้เสนอ
Claude Berrou, Alain Glavieux, and Punya Thitimajshima
ปี
1993
ประเภท
iterative error-correcting code
กลุ่มวิธี
Coding theory

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

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

ใช้ทำอะไร?

รหัสเทอร์โบ (Turbo codes) ซึ่งถูกนำเสนอโดย Berrou, Glavieux และ Thitimajshima ในปี 1993 ถือเป็นหมุดหมายสำคัญในประวัติศาสตร์ของการเข้ารหัสช่องสัญญาณ รหัสเทอร์โบสามารถให้ประสิทธิภาพใกล้เคียงกับขีดจำกัดของ Shannon (Shannon limit) ซึ่งเป็นขีดจำกัดทางทฤษฎีสำหรับการสื่อสารที่เชื่อถือได้ โดยมีค่าความคลาดเคลื่อนเพียง 0.5 dB ซึ่งเคยเป็นสิ่งที่คิดว่าเป็นไปไม่ได้ด้วยความซับซ้อนที่ใช้งานได้จริง รหัสเทอร์โบใช้การเข้ารหัสแบบคอนโวลูชัน (convolutional codes) ที่ต่อกัน (concatenated) พร้อมกับตัวสลับลำดับบิต (interleaver) และการถอดรหัสแบบวนซ้ำ (iterative decoding) ผ่านการแพร่กระจายความน่าเชื่อถือ (belief propagation) รหัสเทอร์โบถูกนำไปใช้ในระบบ 3G (UMTS) และยังคงมีความสำคัญในระบบ 4G/5G ควบคู่ไปกับรหัส LDPC

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

รหัสแก้ไขข้อผิดพลาดมาตรฐานจะเพิ่มความซ้ำซ้อนเพื่อป้องกันข้อมูล แต่โดยทั่วไปแล้วต้องใช้การถอดรหัสที่ซับซ้อน (เช่น การถอดรหัสแบบ Maximum Likelihood ซึ่งมีความซับซ้อนเพิ่มขึ้นแบบทวีคูณตามความยาวของรหัส) รหัสเทอร์โบกลับปัญหาในทางตรงกันข้าม: ใช้ตัวเข้ารหัสที่เรียบง่าย (ตัวเข้ารหัสคอนโวลูชันสองตัวขึ้นไป) แบบขนาน โดยคั่นด้วยตัวสลับลำดับบิตแบบสุ่มเทียม (pseudo-random interleaver) และให้ตัวถอดรหัสแลกเปลี่ยนข้อมูลแบบวนซ้ำ ตัวสลับลำดับบิตจะทำให้แน่ใจว่าข้อผิดพลาดที่ยากสำหรับรหัสหนึ่ง จะเป็นเรื่องง่ายสำหรับอีกรหัสหนึ่ง (เนื่องจากการสลับตำแหน่ง) ดังนั้นการปรับปรุงแบบวนซ้ำจะลู่เข้าสู่ข้อความที่แท้จริง 'ปรากฏการณ์เทอร์โบ' (Turbo effect) นี้ (ซึ่งเป็นที่มาของชื่อ) ทำให้เกิดประสิทธิภาพที่ดีขึ้นแบบทวีคูณเมื่อเทียบกับการถอดรหัสแบบผ่านครั้งเดียว และเข้าใกล้ขีดจำกัดทางทฤษฎี

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

รหัสเทอร์โบถูกประกาศในงาน ICC ปี 1993 สร้างความตกตะลึงให้กับชุมชนทฤษฎีการเข้ารหัสด้วยประสิทธิภาพที่ใกล้เคียงขีดจำกัดของ Shannon รหัสเทอร์โบเป็นแรงขับเคลื่อนสำคัญในการนำระบบ 3G (UMTS, cdma2000) มาใช้ในช่วงปลายทศวรรษ 1990 การทำความเข้าใจรหัสเทอร์โบนำไปสู่ทฤษฎีการถอดรหัสแบบวนซ้ำที่กว้างขึ้น และการฟื้นคืนชีพในการทำความเข้าใจรหัสแบบดั้งเดิม (เช่น รหัส Hamming ถูกแสดงว่ามีโครงสร้างแบบวนซ้ำ) ในช่วงปี 2000 รหัส LDPC (ที่ค้นพบใหม่โดย Gallager, 1962) ได้กลายเป็นคู่แข่งที่มีประสิทธิภาพใกล้เคียงกันและมีสถาปัตยกรรมที่ง่ายกว่า รหัสโพลาร์ (Polar codes, Arikan, 2009) ให้ความเป็นเลิศทางทฤษฎีในขีดจำกัด มาตรฐานสมัยใหม่ (5G NR) รองรับทั้งสามตระกูล รหัสเทอร์โบเป็นเทคโนโลยีเก่าแต่มีการใช้งานอย่างแพร่หลาย

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

รหัสเทอร์โบมีความโดดเด่นในช่องสัญญาณที่มีการเฟดอย่างรุนแรงหรือมีสัญญาณรบกวนสูง ซึ่งต้องการการแก้ไขข้อผิดพลาดที่แข็งแกร่ง (เช่น การสื่อสารผ่านดาวเทียม, อวกาศลึก, ใต้น้ำ) ควรใช้การเข้ารหัสเทอร์โบเมื่ออัตราความผิดพลาดของบิต (BER: bit-error rate) ต่ำ (BER < 10^-6) เป็นสิ่งสำคัญ และความล่าช้า (latency) ที่เกิดจากการถอดรหัสแบบวนซ้ำ (ไม่กี่มิลลิวินาที) สามารถยอมรับได้ รหัสเทอร์โบไม่เหมาะสำหรับแอปพลิเคชันที่ต้องการอัตราการส่งข้อมูลสูง หรือแพ็กเก็ตที่สั้นมาก (เนื่องจากตัวสลับลำดับบิตและสถานะของตัวถอดรหัสมีผลต่อโอเวอร์เฮด) ด้วยการเกิดขึ้นของรหัส LDPC และรหัสโพลาร์ (Polar codes) (ซึ่งมีประสิทธิภาพดีกว่าเล็กน้อยและสถาปัตยกรรมง่ายกว่า) รหัสเทอร์โบจึงกลายเป็นเทคโนโลยีเก่า (legacy) ในมาตรฐานใหม่หลายฉบับ แม้ว่าจะยังคงใช้ในชั้นความเข้ากันได้ (compatibility layers) ก็ตาม

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

  • การถอดรหัสแบบวนซ้ำทำให้เกิดความล่าช้า (หลายสิบมิลลิวินาทีสำหรับตัวสลับลำดับบิตที่ยาว)
  • ประสิทธิภาพมีความอ่อนไหวต่อการออกแบบตัวสลับลำดับบิต การเลือกที่ไม่ดีจะบั่นทอนปรากฏการณ์เทอร์โบ
  • ข้อผิดพลาดมีแนวโน้มที่จะแพร่กระจายเป็นกลุ่ม (error floor) ที่ BER ต่ำมาก ต้องมีการปรับแต่งรหัสเพื่อลดผลกระทบ
  • ความซับซ้อนในการถอดรหัสเป็นสัดส่วนกับความยาวข้อมูล (ไม่ใช่แบบทวีคูณ แต่ก็ยังสูง)
  • แพ็กเก็ตสั้นได้รับผลกระทบจากโอเวอร์เฮดของตัวสลับลำดับบิตและความลึกของการวนซ้ำที่ไม่เพียงพอต่อการลู่เข้า

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

จุดแข็ง

  • ประสิทธิภาพใกล้เคียงขีดจำกัดของ Shannon เพียง 0.5 dB ด้วยความซับซ้อนที่ใช้งานได้จริง
  • ทำงานได้ดีในช่วงอัตราส่วนสัญญาณต่อสัญญาณรบกวน (SNR) ที่กว้าง โดยไม่มีปรากฏการณ์ขีดจำกัด (threshold phenomenon) เหมือนรหัสแบบดั้งเดิม
  • การถอดรหัสแบบวนซ้ำช่วยเพิ่มประสิทธิภาพในแต่ละรอบการวนซ้ำ ทำให้สามารถควบคุมอัตราการส่งข้อมูลได้ด้วยจำนวนรอบการวนซ้ำ
  • การออกแบบที่แยกส่วนได้: สามารถใช้รหัสคอนโวลูชันใดก็ได้ ทำให้มีความยืดหยุ่น
  • ทนทานต่อข้อผิดพลาดแบบกลุ่ม (burst errors) เนื่องจากตัวสลับลำดับบิตกระจายข้อผิดพลาด

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

  • เครือข่ายเซลลูลาร์ 3G/4G (UMTS, LTE): ช่องทางการรับส่งข้อมูลขาขึ้นและขาลงโดยใช้รหัสเทอร์โบเพื่อให้ได้ประสิทธิภาพใกล้เคียงขีดจำกัดของ Shannon
  • การสื่อสารผ่านดาวเทียม: ภารกิจอวกาศลึก (เช่น ยานสำรวจดาวอังคาร) ใช้รหัสเทอร์โบเพื่อกู้คืนข้อมูลที่เชื่อถือได้จากสัญญาณรบกวนที่รุนแรง
  • การสื่อสารทางทหารแบบเข้ารหัส: การส่งข้อมูลที่เข้ารหัสด้วยการแก้ไขข้อผิดพลาดที่แข็งแกร่งในสภาพแวดล้อมที่ไวต่อการก่อกวน (jamming-prone environments)
  • เครือข่ายเซ็นเซอร์ไร้สาย: โหนดพลังงานต่ำใช้รหัสเทอร์โบสั้นสำหรับการส่งต่อข้อมูลแบบหลายช่วง (multi-hop forwarding) ที่เชื่อถือได้
  • การสื่อสารโทรมาตรทางการแพทย์: อุปกรณ์ชีวการแพทย์ส่งข้อมูลผู้ป่วยที่สำคัญผ่านลิงก์ไร้สายที่มีสัญญาณรบกวน

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

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

1

บิตข้อมูลจะถูกเข้ารหัสเป็นสองรหัสคำ (codewords) แบบขนาน โดยใช้ตัวเข้ารหัสคอนโวลูชันที่เหมือนกัน (RSC: recursive systematic convolutional)

2

ระหว่างตัวเข้ารหัสทั้งสอง ตัวสลับลำดับบิตแบบสุ่มเทียมจะทำการสลับลำดับของบิตข้อมูล สิ่งนี้ทำให้แน่ใจว่ารหัสคำทั้งสองมีรูปแบบน้ำหนัก (weight distributions) ที่แตกต่างกันสำหรับข้อมูลเดียวกัน

3

บิตที่เข้ารหัสแล้ว (ทั้งบิตข้อมูลและบิตพาริตีจากตัวเข้ารหัสทั้งสอง) จะถูกส่งผ่านช่องสัญญาณซึ่งถูกรบกวนด้วยสัญญาณรบกวน

4

ที่ตัวรับ ตัวถอดรหัสแบบอินพุตแบบอ่อน-เอาต์พุตแบบอ่อน (SISO: soft-input soft-output) จะทำงานแบบวนซ้ำ: ตัวถอดรหัสที่ 1 ใช้สัญญาณที่ได้รับและข้อมูลส่วนเกิน (extrinsic information) จากตัวถอดรหัสที่ 2 เพื่อปรับปรุงการประมาณค่าของตนเอง ตัวถอดรหัสที่ 2 ก็ทำเช่นเดียวกัน ตัวสลับลำดับบิต/ตัวสลับลำดับบิตย้อนกลับ (De-interleaver/interleaver) จะส่งต่อข้อมูลระหว่างตัวถอดรหัส

5

หลังจากการวนซ้ำจำนวนครั้งที่กำหนด (เช่น 8-20 ครั้ง) จะทำการตัดสินใจแบบแข็ง (hard decision) ครั้งสุดท้ายโดยการเปรียบเทียบอัตราส่วนความน่าจะเป็น (likelihood ratio) กับเกณฑ์ การลู่เข้าสามารถติดตามได้ผ่าน 'หน้าผาเทอร์โบ' (turbo cliff): ประสิทธิภาพจะลดลงอย่างรวดเร็วเมื่ออัตราส่วนสัญญาณต่อสัญญาณรบกวน (SNR) ข้ามเกณฑ์ที่การวนซ้ำเริ่มลู่เข้า

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

  • การใช้ตัวสลับลำดับบิตแบบกำหนดตายตัวหรือสั้นเกินไป ความสุ่มเทียมเป็นสิ่งจำเป็นสำหรับกำไรจากการวนซ้ำ
  • การสมมติว่าจำนวนรอบการวนซ้ำคงที่นั้นเหมาะสมที่สุด ประสิทธิภาพแปรผันตาม SNR การใช้จำนวนรอบการวนซ้ำแบบปรับได้จะดีกว่า
  • การละเลย error floor รหัสเทอร์โบสามารถแสดงขีดจำกัด (turbo cliff) ซึ่งต่ำกว่านั้นประสิทธิภาพจะลดลงอย่างรวดเร็ว
  • การใช้รหัสเทอร์โบกับบล็อกข้อมูลที่สั้นมาก (<100 บิต) โอเวอร์เฮดสัมพัทธ์จะสูงเกินไป
  • การไม่คำนึงถึงความล่าช้าของผลป้อนกลับในการถอดรหัสแบบวนซ้ำ จำเป็นต้องมีการกำหนดเวลาที่สอดคล้องกันระหว่างตัวถอดรหัส

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

คำว่า 'เทอร์โบ' ในรหัสเทอร์โบหมายถึงอะไร?

ชื่อนี้หมายถึงกระบวนการถอดรหัสแบบวนซ้ำที่คล้ายกับเครื่องยนต์เทอร์โบ: ตัวถอดรหัสแต่ละตัวจะ 'เพิ่มกำลัง' สัญญาณให้กับตัวถอดรหัสถัดไป กำไรด้านประสิทธิภาพแบบทวีคูณในแต่ละรอบการวนซ้ำบางครั้งเรียกว่าปรากฏการณ์เทอร์โบ มันไม่ได้เกี่ยวข้องโดยตรงกับเทอร์โบชาร์จเจอร์

ทำไมตัวสลับลำดับบิตจึงมีความสำคัญมาก?

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

หน้าผาเทอร์โบ (turbo cliff) คืออะไร?

รหัสเทอร์โบแสดงขีดจำกัดที่ชัดเจน: ต่ำกว่า SNR ที่วิกฤต การถอดรหัสแบบวนซ้ำจะไม่สามารถลู่เข้าได้ และ BER จะต่ำ ในทางกลับกัน เมื่อ SNR สูงกว่าขีดจำกัด BER จะลดลงอย่างรวดเร็ว นี่คือหน้าผาเทอร์โบ สำหรับการออกแบบระบบ SNR ต้องอยู่เหนือหน้าผาอย่างปลอดภัย การทำงานที่ต่ำกว่าหน้าผาเล็กน้อยจะทำให้เกิดความล้มเหลวอย่างรุนแรง แม้ว่า SNR จะดูเหมือนเพียงพอ

ต้องใช้การวนซ้ำกี่ครั้ง?

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

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

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

  1. Berrou, C., Glavieux, A., & Thitimajshima, P. (1993). Near Shannon limit error-correcting coding and decoding: Turbo-codes. In Proceedings of the IEEE International Conference on Communications (ICC), 1064-1070.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. Richardson, T. J., & Urbanke, R. L. (2002). The capacity of low-density parity-check codes under message-passing decoding. IEEE Transactions on Information Theory, 47(2), 599-618.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว