การเข้ารหัสแบบเทอร์โบพร้อมการถอดรหัสแบบวนซ้ำ
- ผู้เสนอ
- 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) ที่เชื่อถือได้
- การสื่อสารโทรมาตรทางการแพทย์: อุปกรณ์ชีวการแพทย์ส่งข้อมูลผู้ป่วยที่สำคัญผ่านลิงก์ไร้สายที่มีสัญญาณรบกวน
วิธีการทำงาน
วิธีการทำงาน
บิตข้อมูลจะถูกเข้ารหัสเป็นสองรหัสคำ (codewords) แบบขนาน โดยใช้ตัวเข้ารหัสคอนโวลูชันที่เหมือนกัน (RSC: recursive systematic convolutional)
ระหว่างตัวเข้ารหัสทั้งสอง ตัวสลับลำดับบิตแบบสุ่มเทียมจะทำการสลับลำดับของบิตข้อมูล สิ่งนี้ทำให้แน่ใจว่ารหัสคำทั้งสองมีรูปแบบน้ำหนัก (weight distributions) ที่แตกต่างกันสำหรับข้อมูลเดียวกัน
บิตที่เข้ารหัสแล้ว (ทั้งบิตข้อมูลและบิตพาริตีจากตัวเข้ารหัสทั้งสอง) จะถูกส่งผ่านช่องสัญญาณซึ่งถูกรบกวนด้วยสัญญาณรบกวน
ที่ตัวรับ ตัวถอดรหัสแบบอินพุตแบบอ่อน-เอาต์พุตแบบอ่อน (SISO: soft-input soft-output) จะทำงานแบบวนซ้ำ: ตัวถอดรหัสที่ 1 ใช้สัญญาณที่ได้รับและข้อมูลส่วนเกิน (extrinsic information) จากตัวถอดรหัสที่ 2 เพื่อปรับปรุงการประมาณค่าของตนเอง ตัวถอดรหัสที่ 2 ก็ทำเช่นเดียวกัน ตัวสลับลำดับบิต/ตัวสลับลำดับบิตย้อนกลับ (De-interleaver/interleaver) จะส่งต่อข้อมูลระหว่างตัวถอดรหัส
หลังจากการวนซ้ำจำนวนครั้งที่กำหนด (เช่น 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 ต่ำ จำเป็นต้องมีการวนซ้ำมากขึ้น การวนซ้ำแบบปรับได้ (ตรวจสอบการลู่เข้า หยุดก่อนกำหนดหากเสร็จสิ้น) จะช่วยสร้างสมดุลระหว่างความล่าช้าและประสิทธิภาพ
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
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คัดลอกแล้ว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คัดลอกแล้ว