กลับไปหน้าบทความ

อ่าน 8 นาที

รหัสคอนโวลูชัน

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

รหัสคอนโวลูชัน

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

ความสามารถในการถอดรหัสแบบ soft decision ที่มีความน่าจะเป็นสูงสุดอย่างประหยัดเป็นหนึ่งในข้อดีหลักของรหัสคอนโวลูชัน ซึ่งแตกต่างจากรหัสบล็อกแบบคลาสสิก ซึ่งโดยทั่วไปจะแสดงด้วย trellis ที่เปลี่ยนแปลงตามเวลา และดังนั้นจึงมักจะถอดรหัสแบบ hard-decision รหัสคอนโวลูชันมักจะมีลักษณะเฉพาะด้วยอัตราการเข้ารหัส พื้นฐาน และความลึก (หรือหน่วยความจำ) ของตัวเข้ารหัสอัตราการเข้ารหัสพื้นฐานมักจะกำหนดเป็น โดยที่kคืออัตราข้อมูลอินพุตดิบ และnคืออัตราข้อมูลของสตรีมที่เข้ารหัสช่องสัญญาณเอาต์พุต kน้อยกว่าnเนื่องจากการเข้ารหัสช่องสัญญาณจะแทรกความซ้ำซ้อนในบิตอินพุต หน่วยความจำมักเรียกว่า "ความยาวข้อจำกัด" Kโดยที่เอาต์พุตเป็นฟังก์ชันของอินพุตปัจจุบันรวมถึงอินพุต ก่อนหน้าด้วย [ 1 ]ความลึกอาจกำหนดเป็นจำนวนองค์ประกอบหน่วยความจำvในพหุนามหรือจำนวนสถานะที่เป็นไปได้สูงสุดของผู้เข้ารหัส (โดยทั่วไป: )

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

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

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

รหัสคอนโวลูชันถูกนำเสนอครั้งแรกในปี 1955 โดยปีเตอร์ เอเลียสเชื่อกันว่ารหัสคอนโวลูชันสามารถถอดรหัสได้ด้วยคุณภาพตามอำเภอใจ แต่ต้องแลกมาด้วยการคำนวณที่ซับซ้อนและเวลาหน่วง ในปี 1967 แอนดรูว์ วิเทอร์บีพบว่ารหัสคอนโวลูชันสามารถถอดรหัสด้วยวิธีความน่าจะเป็นสูงสุด (maximum-likelihood) ได้ด้วยความซับซ้อนที่เหมาะสม โดยใช้ตัวถอดรหัสแบบเทรลลิสที่ไม่เปลี่ยนแปลงตามเวลา — หรือที่เรียกว่าอัลกอริทึมวิเทอร์บีต่อมาได้มีการพัฒนาอัลกอริทึมตัวถอดรหัสแบบเทรลลิสอื่นๆ ขึ้นมา รวมถึงอัลกอริทึมการถอดรหัส BCJR ด้วย

รหัสคอนโวลูชันเชิงระบบแบบเรียกซ้ำถูกคิดค้นโดยClaude Berrou ประมาณปี 1991 รหัสเหล่านี้พิสูจน์แล้วว่ามีประโยชน์อย่างยิ่งสำหรับการประมวล ผลแบบวนซ้ำ รวมถึงการประมวลผลรหัสที่เชื่อมต่อกัน เช่นรหัสเทอร์โบ [ 2 ]

หากใช้ศัพท์เฉพาะทางด้าน "คอนโวลูชัน" รหัสคอนโวลูชันแบบคลาสสิกอาจถือได้ว่าเป็น ตัวกรองแบบ ตอบสนองแบบจำกัด (Finite Impulse Response : FIR) ในขณะที่รหัสคอนโวลูชันแบบวนซ้ำอาจถือได้ว่าเป็น ตัวกรอง แบบตอบสนองแบบไม่จำกัด (Infinite Impulse Response: IIR)

ที่ใช้รหัสคอนโวลูชัน

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

รหัสคอนโวลูชันถูกนำมาใช้อย่างกว้างขวางเพื่อให้การถ่ายโอนข้อมูลที่เชื่อถือได้ในแอปพลิเคชันต่างๆ มากมาย เช่นวิดีโอดิจิทัลวิทยุการสื่อสารเคลื่อนที่ (เช่น ในเครือข่าย GSM, GPRS, EDGE และ 3G (จนถึง 3GPP รุ่น 7)) [ 4 ] [ 5 ] ) และการสื่อสารผ่านดาวเทียม[ 6 ]รหัสเหล่านี้มักถูกนำไปใช้ร่วมกับรหัสการตัดสินใจแบบแข็ง โดยเฉพาะอย่างยิ่งReed–Solomonก่อนที่จะมีรหัสเทอร์โบโครงสร้างดังกล่าวมีประสิทธิภาพมากที่สุด ใกล้เคียงกับขีดจำกัดของ Shannonมาก ที่สุด

การเข้ารหัสแบบคอนโวลูชัน

ในการเข้ารหัสข้อมูลแบบคอนโวลูชัน เริ่มต้นด้วยรีจิสเตอร์หน่วยความจำk ตัว แต่ละตัวเก็บบิตอินพุตหนึ่งบิต เว้นแต่จะระบุไว้เป็นอย่างอื่น รีจิสเตอร์หน่วยความจำทั้งหมดเริ่มต้นด้วยค่า 0 ตัวเข้ารหัสมี ตัว บวกโมดูลัส 2 จำนวน n ตัว (ตัวบวกโมดูลัส 2 สามารถสร้างได้ด้วยเกต XOR แบบ บูลีน ตัวเดียว โดยตรรกะคือ: 0+0 = 0 , 0+1 = 1 , 1+0 = 1 , 1+1 = 0 ) และพหุนามตัวสร้างจำนวนn ตัว — หนึ่งตัวสำหรับตัวบวกแต่ละตัว (ดูรูปด้านล่าง) บิตอินพุตm 1จะถูกป้อนเข้าไปในรีจิสเตอร์ซ้ายสุด โดยใช้พหุนามตัวสร้างและค่าที่มีอยู่แล้วในรีจิสเตอร์ที่เหลือ ตัวเข้ารหัสจะส่งออก สัญลักษณ์จำนวน nตัว สัญลักษณ์เหล่านี้อาจถูกส่งหรือถูกเจาะ ขึ้นอยู่กับอัตราการเข้ารหัสที่ต้องการ จากนั้นเลื่อนบิตของค่าในรีจิสเตอร์ทั้งหมดไปทางขวา ( m 1ย้ายไปที่m 0 , m 0ย้ายไปที่m −1 ) และรอรับบิตอินพุตถัดไป หากไม่มีบิตอินพุตเหลืออยู่ ตัวเข้ารหัสจะเลื่อนต่อไปจนกว่ารีจิสเตอร์ทั้งหมดจะกลับสู่สถานะศูนย์ (การสิ้นสุดบิตแบบฟลัช)

ภาพที่ 1. ตัวเข้ารหัสคอนโวลูชันแบบไม่เรียกซ้ำและไม่เป็นระบบ อัตรา 1/3 พร้อมความยาวข้อจำกัด 3

รูปด้านล่างเป็นตัวเข้ารหัสอัตรา1/3 ( m / n )ที่มีความยาวข้อจำกัด ( k )เท่ากับ 3 พหุนามตัวสร้างคือG1 = (1,1,1), G2 = (0,1,1)และG3 = (1,0,1) ดังนั้น บิตเอาต์พุตจึงคำนวณ (โมดูลัส 2) ได้ดังนี้:

n 1 = m 1 + m 0 + m −1
n 2 = m 0 + m −1
n 3 = m 1 + m −1 .

รหัสคอนโวลูชันสามารถเป็นได้ทั้งแบบมีระบบและไม่มีระบบ:

  • การเข้ารหัสแบบเป็นระบบจะทำซ้ำโครงสร้างของข้อความก่อนการเข้ารหัส
  • การเปลี่ยนแปลงที่ไม่เป็นระบบต่อโครงสร้างเริ่มต้น

รหัสคอนโวลูชันที่ไม่เป็นระบบได้รับความนิยมมากกว่าเนื่องจากมีความต้านทานต่อสัญญาณรบกวนที่ดีกว่า ซึ่งเกี่ยวข้องกับระยะห่างอิสระของรหัสคอนโวลูชัน[ 7 ]

โค้ดแบบเรียกซ้ำและแบบไม่เรียกซ้ำ

ตัวเข้ารหัสในภาพด้านบนเป็น ตัวเข้ารหัสแบบ ไม่ใช้การเรียกซ้ำนี่คือตัวอย่างของตัวเข้ารหัสแบบใช้การเรียกซ้ำ ซึ่งรองรับโครงสร้างการป้อนกลับ:

ภาพที่ 2. ตัวเข้ารหัสคอนโวลูชันแบบระบบเรียกซ้ำ 8 สถานะ อัตรา 1/2 ใช้เป็นรหัสส่วนประกอบใน 3GPP 25.212 Turbo Code

ตัวเข้ารหัสตัวอย่างนี้เป็นแบบเป็นระบบเนื่องจากข้อมูลอินพุตถูกนำไปใช้ในสัญลักษณ์เอาต์พุตด้วย (เอาต์พุต 2) รหัสที่มีสัญลักษณ์เอาต์พุตที่ไม่รวมข้อมูลอินพุตเรียกว่า แบบไม่เป็นระบบ

โดยทั่วไปแล้ว โค้ดแบบเรียกซ้ำมักเป็นระบบ ในทางกลับกัน โค้ดที่ไม่ใช้การเรียกซ้ำมักไม่มีระบบ นี่ไม่ใช่ข้อกำหนดที่เคร่งครัด แต่เป็นวิธีปฏิบัติทั่วไป

ตัวอย่างตัวเข้ารหัสในภาพที่ 2 เป็นตัวเข้ารหัสแบบ 8 สถานะ เนื่องจากรีจิสเตอร์ทั้ง 3 ตัวจะสร้างสถานะตัวเข้ารหัสที่เป็นไปได้ 8 สถานะ (2 3 ) โดยทั่วไปแล้ว วงจรถอดรหัสที่สอดคล้องกันก็จะใช้ 8 สถานะเช่นกัน

รหัสคอนโวลูชันเชิงระบบแบบเรียกซ้ำ (RSC) ได้รับความนิยมมากขึ้นเนื่องจากการนำไปใช้ใน Turbo Code รหัสเชิงระบบแบบเรียกซ้ำยังถูกเรียกว่ารหัสเชิงระบบเทียมอีกด้วย

รหัส RSC อื่นๆ และตัวอย่างการใช้งาน ได้แก่:

ภาพที่ 3. รหัสคอนโวลูชันเชิงระบบแบบเรียกซ้ำสองสถานะ (RSC) หรือเรียกอีกอย่างว่า 'ตัวสะสม'

มีประโยชน์สำหรับ การใช้งานรหัส LDPCและเป็นรหัสองค์ประกอบภายในสำหรับรหัสคอนโวลูชันแบบอนุกรมต่อกัน (SCCC)

ภาพที่ 4. รหัสคอนโวลูชันเชิงระบบแบบเรียกซ้ำสี่สถานะ (RSC)

มีประโยชน์สำหรับ SCCC และรหัสเทอร์โบแบบหลายมิติ

ภาพที่ 5. รหัสคอนโวลูชันเชิงระบบแบบเรียกซ้ำ 16 สถานะ (RSC)

มีประโยชน์ในฐานะรหัสส่วนประกอบในรหัสเทอร์โบที่มีอัตราข้อผิดพลาดต่ำสำหรับแอปพลิเคชันต่างๆ เช่น การเชื่อมต่อผ่านดาวเทียม นอกจากนี้ยังเหมาะสำหรับใช้เป็นรหัสภายนอกของ SCCC ด้วย

การตอบสนองต่อแรงกระตุ้น ฟังก์ชันถ่ายโอน และความยาวข้อจำกัด

ตัวเข้ารหัสแบบคอนโวลูชัน (Convolutional Encoder) ได้ชื่อเช่นนั้นเพราะมันทำการคอนโวลูชันของกระแสข้อมูลขาเข้ากับผลตอบสนองแบบอิมพัลส์ ของตัวเข้ารหัส :

โดยที่xคือลำดับอินพุต, y jคือลำดับจากเอาต์พุตj , h jคือการตอบสนองแบบอิมพัลส์สำหรับเอาต์พุตjและหมายถึงการคอนโวลูชัน

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

ฟังก์ชันถ่ายโอนสำหรับตัวเข้ารหัสตัวแรก (ที่ไม่ใช่แบบเรียกซ้ำ) มีดังนี้:

ฟังก์ชันถ่ายโอนสำหรับตัวเข้ารหัสตัวที่สอง (แบบเรียกซ้ำ) มีดังนี้:

กำหนดค่าmโดย

โดยที่สำหรับฟังก์ชันตรรกยะ ใด ๆ

.

ดังนั้นmคือค่าสูงสุดของดีกรีพหุนามของ

และความยาวของข้อจำกัดถูกกำหนดเป็นตัวอย่างเช่น ในตัวอย่างแรก ความยาวของข้อจำกัดคือ 3 และในตัวอย่างที่สอง ความยาวของข้อจำกัดคือ 4

แผนภาพเทรลลิส

ตัวเข้ารหัสแบบคอนโวลูชันเป็นเครื่องสถานะจำกัดตัวเข้ารหัสที่มีเซลล์ไบนารีn เซลล์จะมีสถานะ 2 <sup>n</sup>สถานะ

ลองนึกภาพว่าตัวเข้ารหัส (แสดงในภาพที่ 1 ด้านบน) มี ค่า '1' ในเซลล์หน่วยความจำด้านซ้าย ( m0 ) และค่า '0' ในเซลล์ด้านขวา ( m-1) (m1 ไม่ใช่เซลล์หน่วยความจำจริง ๆ เพราะมันแสดงค่าปัจจุบัน) เราจะกำหนดสถานะนี้เป็น "10" ตามบิตอินพุต ตัวเข้ารหัสสามารถเปลี่ยนสถานะในรอบถัดไปเป็น "01" หรือ "11" ได้ จะเห็นได้ว่าไม่ใช่ทุกการเปลี่ยนสถานะจะเป็นไปได้ (เช่น ตัวถอดรหัสไม่สามารถเปลี่ยนจากสถานะ "10" เป็น "00" หรือแม้แต่คงอยู่ในสถานะ "10" ได้)

การเปลี่ยนสถานะที่เป็นไปได้ทั้งหมดสามารถแสดงได้ดังต่อไปนี้:

ภาพที่ 6 แผนภาพเทรลลิสสำหรับตัวเข้ารหัสในภาพที่ 1 เส้นทางผ่านเทรลลิสแสดงด้วยเส้นสีแดง เส้นทึบแสดงการเปลี่ยนสถานะเมื่อป้อนค่า "0" และเส้นประแสดงการเปลี่ยนสถานะเมื่อป้อนค่า "1"

ลำดับการเข้ารหัสจริงสามารถแสดงเป็นเส้นทางบนกราฟนี้ได้ เส้นทางที่ถูกต้องเส้นหนึ่งแสดงด้วยสีแดงเป็นตัวอย่าง

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

ระยะทางอิสระและการกระจายข้อผิดพลาด

กราฟอัตราความผิดพลาดของบิตตามทฤษฎีของการเข้ารหัส QPSK (แบบเรียกซ้ำและไม่เรียกซ้ำ การตัดสินใจแบบอ่อน) สำหรับช่องสัญญาณรบกวนแบบเกาส์เซียนสีขาว กราฟมีความแตกต่างกันเล็กน้อยเนื่องจากระยะห่างอิสระและน้ำหนักใกล้เคียงกัน

ระยะทางอิสระ[ 8 ] ( d ) คือระยะทางแฮมมิ งขั้นต่ำ ระหว่างลำดับที่เข้ารหัสต่างกันความสามารถในการแก้ไข ( t ) ของรหัสคอนโวลูชันคือจำนวนข้อผิดพลาดที่สามารถแก้ไขได้โดยรหัส สามารถคำนวณได้ดังนี้

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

ระยะห่างอิสระสามารถตีความได้ว่าเป็นความยาวขั้นต่ำของ "กลุ่มข้อผิดพลาด" ที่เอาต์พุตของตัวถอดรหัสแบบคอนโวลูชัน ข้อเท็จจริงที่ว่าข้อผิดพลาดปรากฏเป็น "กลุ่มข้อผิดพลาด" ควรนำมาพิจารณาเมื่อออกแบบรหัสแบบต่อกันที่มีรหัสคอนโวลูชันภายใน วิธีแก้ปัญหาที่นิยมใช้คือการแทรกข้อมูลก่อนการเข้ารหัสแบบคอนโวลูชัน เพื่อให้บล็อกภายนอก (โดยปกติคือ รหัส Reed–Solomon ) สามารถแก้ไขข้อผิดพลาดส่วนใหญ่ได้

การถอดรหัสคอนโวลูชัน

เส้นโค้งอัตราข้อผิดพลาดบิตสำหรับรหัสคอนโวลูชันที่มีตัวเลือกการมอดูเลชันดิจิทัลที่แตกต่างกัน ( QPSK, 8-PSK , 16-QAM, 64-QAM ) และอัลกอริธึมLLR [ 9 ] [ 10 ] (แบบแม่นยำ[ 11 ]และแบบประมาณ[ 12 ] ) บนช่องสัญญาณรบกวนเกาส์เซียนสีขาวแบบบวก

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

รหัสที่มีข้อจำกัดความยาวมากขึ้นนั้น สามารถถอดรหัสได้ง่ายกว่าด้วย อัลกอริธึมการ ถอดรหัสแบบลำดับ หลายแบบ ซึ่ง อัลกอริธึม Fanoเป็นที่รู้จักกันดีที่สุด ต่างจากการถอดรหัส Viterbi การถอดรหัสแบบลำดับไม่ใช่การหาค่าความน่าจะเป็นสูงสุด แต่ความซับซ้อนของมันเพิ่มขึ้นเพียงเล็กน้อยเมื่อความยาวของข้อจำกัดเพิ่มขึ้น ทำให้สามารถใช้รหัสที่มีข้อจำกัดความยาวมากและมีความเข้มงวดได้ รหัสเหล่านี้ถูกใช้ในโครงการ Pioneerในช่วงต้นทศวรรษ 1970 เพื่อสำรวจดาวพฤหัสบดีและดาวเสาร์ แต่ต่อมาได้ถูกแทนที่ด้วยรหัสที่สั้นกว่าซึ่งถอดรหัสด้วย Viterbi โดยปกติจะต่อท้ายด้วย รหัส แก้ไขข้อผิดพลาด Reed–Solomon ขนาดใหญ่ ซึ่งจะทำให้เส้นโค้งอัตราข้อผิดพลาดบิตโดยรวมชันขึ้น และสร้างอัตราข้อผิดพลาดที่ตรวจไม่พบที่เหลืออยู่ต่ำมาก

ทั้งอัลกอริธึมการถอดรหัสแบบ Viterbi และแบบลำดับจะให้ผลลัพธ์ที่เป็นการตัดสินใจแบบตายตัว: คือบิตที่ประกอบกันเป็นรหัสคำที่มีความเป็นไปได้มากที่สุด สามารถเพิ่มค่าความเชื่อมั่นโดยประมาณให้กับแต่ละบิตได้โดยใช้อัลกอริธึม Soft output Viterbi ส่วนการ ตัดสินใจแบบอ่อน (Soft decision) ที่มีค่าสูงสุดภายหลัง (MAP) สำหรับแต่ละบิตนั้น สามารถหาได้โดยใช้ อัลกอริธึ ม BCJR

รีจิสเตอร์เลื่อนสำหรับพหุนามรหัสคอนโวลูชัน (7, [171, 133]) สาขา: , . การดำเนินการทางคณิตศาสตร์ทั้งหมดควรทำโดยใช้โมดูลัส 2
กราฟอัตราความผิดพลาดของบิตตามทฤษฎีของการเข้ารหัส QPSK (การตัดสินใจแบบอ่อน) ในช่องสัญญาณรบกวนแบบเกาส์เซียนสีขาวแบบเพิ่ม ความยาวของข้อจำกัดที่มากขึ้นจะสร้างรหัสที่มีประสิทธิภาพมากขึ้น แต่ความซับซ้อนของอัลกอริทึม Viterbi จะเพิ่มขึ้นแบบทวีคูณตามความยาวของข้อจำกัด ทำให้รหัสที่มีประสิทธิภาพมากขึ้นเหล่านี้ถูกจำกัดไว้สำหรับภารกิจในอวกาศห้วงลึก ซึ่งประสิทธิภาพที่เพิ่มขึ้นนั้นคุ้มค่ากับความซับซ้อนของตัวถอดรหัสที่เพิ่มขึ้น

ในความเป็นจริง โครงสร้างรหัสคอนโวลูชันที่กำหนดไว้ล่วงหน้าซึ่งได้มาจากการวิจัยทางวิทยาศาสตร์นั้นถูกนำไปใช้ในอุตสาหกรรม ซึ่งเกี่ยวข้องกับความเป็นไปได้ในการเลือกใช้รหัสคอนโวลูชันที่ก่อให้เกิดข้อผิดพลาดจำนวนมาก (catastrophic convolutional codes)

รหัสคอนโวลูชันที่ถอดรหัสด้วย Viterbi ซึ่งเป็นที่นิยมเป็นพิเศษและถูกใช้มาอย่างน้อยตั้งแต่โครงการ Voyagerมีความยาวข้อจำกัดKเท่ากับ 7 และอัตราrเท่ากับ 1/2 [ 13 ]

ยานสำรวจ ดาวอังคาร Pathfinder , Mars Exploration Roverและยาน Cassini ที่ส่งไปยังดาวเสาร์ ใช้ค่าKเท่ากับ 15 และอัตรา 1/6 โดยรหัสนี้มีประสิทธิภาพดีกว่ารหัสที่เรียบง่ายกว่าประมาณ 2 dB แต่มีความซับซ้อนในการถอดรหัสมากกว่าถึง 256 เท่า (เมื่อเทียบกับรหัสของภารกิจ Voyager)

รหัสคอนโวลูชันที่มีความยาวจำกัด 2 และอัตรา 1/2 ถูกใช้ในGSMเป็นเทคนิคการแก้ไขข้อผิดพลาด[ 14 ]

รหัสคอนโวลูชันที่ถูกเจาะ

รหัสคอนโวลูชันที่มีอัตราการเข้ารหัส 1/2 และ 3/4 (และความยาวข้อจำกัด 7 การตัดสินใจแบบอ่อน 4-QAM / QPSK / OQPSK) [ 15 ]

สามารถออกแบบรหัสคอนโวลูชันที่มีอัตราการเข้ารหัสใดๆ ก็ได้โดยอาศัยการเลือกพหุนาม[ 16 ]อย่างไรก็ตาม ในทางปฏิบัติ มักใช้กระบวนการเจาะรูเพื่อให้ได้อัตราการเข้ารหัสที่ต้องการการเจาะรูเป็นเทคนิคที่ใช้ในการสร้าง รหัสอัตรา m / nจากรหัสอัตราต่ำ "พื้นฐาน" (เช่น 1/ n ) โดยทำได้โดยการลบบิตบางส่วนในเอาต์พุตของตัวเข้ารหัส บิตจะถูกลบตามเมทริกซ์การเจาะรู เมทริกซ์การเจาะรูต่อไปนี้เป็นเมทริกซ์ที่ใช้บ่อยที่สุด:

อัตราโค้ด เมทริกซ์การเจาะ ระยะทางอิสระ (สำหรับรหัสคอนโวลูชันมาตรฐาน K=7 ของ NASA)
1/2 (ไม่มีรูปร่าง)
1
1
10
2/3
1 0
1 1
6
3/4
1 0 1
1 1 0
5
5/6
1 0 1 0 1
1 1 0 1 0
4
7/8
1 0 0 0 1 0 1
1 1 1 1 0 1 0
3

ตัวอย่างเช่น หากเราต้องการสร้างรหัสที่มีอัตรา 2/3 โดยใช้เมทริกซ์ที่เหมาะสมจากตารางด้านบน เราควรนำเอาเอาต์พุตของตัวเข้ารหัสพื้นฐานมาใช้ และส่งบิตแรกจากสาขาแรกและบิตแรกจากสาขาที่สอง ลำดับการส่งข้อมูลที่เฉพาะเจาะจงนั้นถูกกำหนดโดยมาตรฐานการสื่อสารที่เกี่ยวข้อง

รหัสคอนโวลูชันแบบเจาะรูถูกนำมาใช้กันอย่างแพร่หลายในการสื่อสารผ่านดาวเทียมตัวอย่างเช่น ใน ระบบ Intelsatและการออกอากาศวิดีโอดิจิทัล

รหัสคอนโวลูชันแบบมีรูพรุนเรียกอีกอย่างว่า "แบบมีรูพรุน"

รหัสเทอร์โบ: การแทนที่รหัสคอนโวลูชัน

รหัสเทอร์โบที่มีรหัสส่วนประกอบ 13, 15 [ 17 ]รหัสเทอร์โบได้ชื่อนี้เพราะตัวถอดรหัสใช้การป้อนกลับ เหมือนกับเครื่องยนต์เทอร์โบ การเรียงสับเปลี่ยนมีความหมายเหมือนกับการสลับ C1 และ C2 เป็นรหัสคอนโวลูชันแบบเรียกซ้ำ รหัสคอนโวลูชันแบบเรียกซ้ำและแบบไม่เรียกซ้ำไม่ได้แตกต่างกันมากนักในด้านประสิทธิภาพ BER อย่างไรก็ตาม รหัสแบบเรียกซ้ำถูกนำไปใช้ในรหัสคอนโวลูชันเทอร์โบเนื่องจากคุณสมบัติการสลับที่ดีกว่า[ 18 ]

รหัสคอนโวลูชันแบบง่ายๆ ที่ถอดรหัสด้วย Viterbi กำลังถูกแทนที่ด้วยรหัสเทอร์โบซึ่งเป็นรหัสคอนโวลูชันแบบสั้นที่ทำซ้ำหลายครั้งรูปแบบใหม่ ที่เข้าใกล้ขีดจำกัดทางทฤษฎีที่กำหนดโดยทฤษฎีบทของแชนนอนมากขึ้น โดยมีความซับซ้อนในการถอดรหัสน้อยกว่าอัลกอริทึม Viterbi บนรหัสคอนโวลูชันแบบยาวที่จำเป็นเพื่อให้ได้ประสิทธิภาพเดียวกันการต่อท้ายด้วยรหัสพีชคณิตภายนอก (เช่นReed–Solomon ) ช่วยแก้ปัญหาเรื่องค่าความคลาดเคลื่อนต่ำสุดที่เกิดขึ้นโดยธรรมชาติในการออกแบบรหัสเทอร์โบ

ดูเพิ่มเติม

  • หนังสือเรียนออนไลน์เรื่อง "ทฤษฎีสารสนเทศ การอนุมาน และอัลกอริธึมการเรียนรู้"โดยเดวิด เจซี แมคเคย์กล่าวถึงรหัสคอนโวลูชันในบทที่ 48
  • หน้าโค้ดแก้ไขข้อผิดพลาด (ECC)
  • คำอธิบายเกี่ยวกับ Matlab
  • หลักการพื้นฐานของตัวถอดรหัสแบบคอนโวลูชันเพื่อการสื่อสารดิจิทัลที่ดีขึ้น
  • รหัสคอนโวลูชัน (MIT)
  • เอกสารเรื่อง "ทฤษฎีสารสนเทศและการเข้ารหัส" (มหาวิทยาลัยเทคโนโลยีอิลเมเนา) ถูกเก็บถาวรเมื่อวันที่ 30 สิงหาคม 2017 ในWayback Machineซึ่งกล่าวถึงรหัสคอนโวลูชันในหน้า 48

อ่านเพิ่มเติม

สิ่งพิมพ์

  • Francis, Michael. "การถอดรหัสบล็อกตัวถอดรหัส Viterbi - การสิ้นสุดแบบ Trellis และการกัดหาง" Xilinx XAPP551 v2.0, DD (2005): 1-21.
  • Chen, Qingchun, Wai Ho Mow และ Pingzhi Fan. "ผลลัพธ์ใหม่บางประการเกี่ยวกับรหัสคอนโวลูชันแบบเรียกซ้ำและการประยุกต์ใช้" การประชุมเชิงปฏิบัติการทฤษฎีสารสนเทศ ปี 2006 ITW'06 เฉิงตู IEEE. IEEE, 2006.
  • Fiebig, UC. และ Patrick Robertson. "การถอดรหัสแบบตัดสินใจอ่อนและการลบในระบบกระโดดความถี่เร็วด้วยรหัสคอนโวลูชัน เทอร์โบ และรีด-โซโลมอน" IEEE Transactions on Communications 47.11 (1999): 1646-1654.
  • Bhaskar, Vidhyacharan และ Laurie L. Joiner. "ประสิทธิภาพของรหัสคอนโวลูชันแบบเจาะรูในการสื่อสาร CDMA แบบอะซิงโครนัสภายใต้เงื่อนไขการติดตามเฟสที่สมบูรณ์แบบ" Computers & Electrical Engineering 30.8 (2004): 573-592
  • Modestino, J. และ Shou Mui. "ประสิทธิภาพของรหัสคอนโวลูชันในช่องสัญญาณเฟดดิ้งแบบริเชียน" IEEE Transactions on Communications 24.6 (1976): 592-606.
  • Chen, Yuh-Long และ Che-Ho Wei. "การประเมินประสิทธิภาพของรหัสคอนโวลูชันด้วย MPSK บนช่องสัญญาณเฟดแบบ Rician" IEE Proceedings F-Communications, Radar and Signal Processing. Vol. 134. No. 2. IET, 1987.
ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Convolutional_code&oldid=1353119167 "

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ รหัสคอนโวลูชัน

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

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

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

ที่ใช้รหัสคอนโวลูชัน

รหัสคอนโวลูชันถูกนำมาใช้อย่างกว้างขวางเพื่อให้การถ่ายโอนข้อมูลที่เชื่อถือได้ในแอปพลิเคชันต่างๆ มากมาย เช่น วิดีโอดิจิทัล วิทยุ การสื่อสารเคลื่อนที่ (เช่น ในเครือข่าย GSM, GPRS, EDGE และ 3G (จนถึง 3GPP รุ่น 7)) [ 4 ] [ 5 ] ) และการ สื่อสารผ่านดาวเทียม [ 6 ]...

การเข้ารหัสแบบคอนโวลูชัน

ในการเข้ารหัสข้อมูลแบบคอนโวลูชัน เริ่มต้นด้วย รีจิสเตอร์หน่วยความจำ k ตัว แต่ละตัวเก็บบิตอินพุตหนึ่งบิต เว้นแต่จะระบุไว้เป็นอย่างอื่น รีจิสเตอร์หน่วยความจำทั้งหมดเริ่มต้นด้วยค่า 0 ตัวเข้ารหัสมี ตัว บวกโมดูลัส 2 จำนวน n ตัว (ตัวบวกโมดูลัส 2 สามารถสร้างได้ด้วย...