อ่าน 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, 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/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) รหัสที่มีสัญลักษณ์เอาต์พุตที่ไม่รวมข้อมูลอินพุตเรียกว่า แบบไม่เป็นระบบ
โดยทั่วไปแล้ว โค้ดแบบเรียกซ้ำมักเป็นระบบ ในทางกลับกัน โค้ดที่ไม่ใช้การเรียกซ้ำมักไม่มีระบบ นี่ไม่ใช่ข้อกำหนดที่เคร่งครัด แต่เป็นวิธีปฏิบัติทั่วไป
ตัวอย่างตัวเข้ารหัสในภาพที่ 2 เป็นตัวเข้ารหัสแบบ 8 สถานะ เนื่องจากรีจิสเตอร์ทั้ง 3 ตัวจะสร้างสถานะตัวเข้ารหัสที่เป็นไปได้ 8 สถานะ (2 3 ) โดยทั่วไปแล้ว วงจรถอดรหัสที่สอดคล้องกันก็จะใช้ 8 สถานะเช่นกัน
รหัสคอนโวลูชันเชิงระบบแบบเรียกซ้ำ (RSC) ได้รับความนิยมมากขึ้นเนื่องจากการนำไปใช้ใน Turbo Code รหัสเชิงระบบแบบเรียกซ้ำยังถูกเรียกว่ารหัสเชิงระบบเทียมอีกด้วย
รหัส RSC อื่นๆ และตัวอย่างการใช้งาน ได้แก่:

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

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

มีประโยชน์ในฐานะรหัสส่วนประกอบในรหัสเทอร์โบที่มีอัตราข้อผิดพลาดต่ำสำหรับแอปพลิเคชันต่างๆ เช่น การเชื่อมต่อผ่านดาวเทียม นอกจากนี้ยังเหมาะสำหรับใช้เป็นรหัสภายนอกของ 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" ได้)
การเปลี่ยนสถานะที่เป็นไปได้ทั้งหมดสามารถแสดงได้ดังต่อไปนี้:

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

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

มี อัลกอริธึมหลายแบบสำหรับการถอดรหัสคอนโวลูชัน สำหรับค่าk ที่ค่อนข้างเล็ก อัลกอริธึม Viterbiเป็นที่นิยมใช้กันอย่างแพร่หลาย เนื่องจากให้ ประสิทธิภาพ ความน่าจะเป็นสูงสุดและสามารถประมวลผลแบบขนานได้สูง ดังนั้น ตัวถอดรหัส Viterbi จึงง่ายต่อการใช้งานใน ฮาร์ดแวร์ VLSIและในซอฟต์แวร์บน CPU ที่มีชุดคำสั่ง SIMD
รหัสที่มีข้อจำกัดความยาวมากขึ้นนั้น สามารถถอดรหัสได้ง่ายกว่าด้วย อัลกอริธึมการ ถอดรหัสแบบลำดับ หลายแบบ ซึ่ง อัลกอริธึม Fanoเป็นที่รู้จักกันดีที่สุด ต่างจากการถอดรหัส Viterbi การถอดรหัสแบบลำดับไม่ใช่การหาค่าความน่าจะเป็นสูงสุด แต่ความซับซ้อนของมันเพิ่มขึ้นเพียงเล็กน้อยเมื่อความยาวของข้อจำกัดเพิ่มขึ้น ทำให้สามารถใช้รหัสที่มีข้อจำกัดความยาวมากและมีความเข้มงวดได้ รหัสเหล่านี้ถูกใช้ในโครงการ Pioneerในช่วงต้นทศวรรษ 1970 เพื่อสำรวจดาวพฤหัสบดีและดาวเสาร์ แต่ต่อมาได้ถูกแทนที่ด้วยรหัสที่สั้นกว่าซึ่งถอดรหัสด้วย Viterbi โดยปกติจะต่อท้ายด้วย รหัส แก้ไขข้อผิดพลาด Reed–Solomon ขนาดใหญ่ ซึ่งจะทำให้เส้นโค้งอัตราข้อผิดพลาดบิตโดยรวมชันขึ้น และสร้างอัตราข้อผิดพลาดที่ตรวจไม่พบที่เหลืออยู่ต่ำมาก
ทั้งอัลกอริธึมการถอดรหัสแบบ Viterbi และแบบลำดับจะให้ผลลัพธ์ที่เป็นการตัดสินใจแบบตายตัว: คือบิตที่ประกอบกันเป็นรหัสคำที่มีความเป็นไปได้มากที่สุด สามารถเพิ่มค่าความเชื่อมั่นโดยประมาณให้กับแต่ละบิตได้โดยใช้อัลกอริธึม Soft output Viterbi ส่วนการ ตัดสินใจแบบอ่อน (Soft decision) ที่มีค่าสูงสุดภายหลัง (MAP) สำหรับแต่ละบิตนั้น สามารถหาได้โดยใช้ อัลกอริธึ ม BCJR
รหัสคอนโวลูชันที่เป็นที่นิยม


ในความเป็นจริง โครงสร้างรหัสคอนโวลูชันที่กำหนดไว้ล่วงหน้าซึ่งได้มาจากการวิจัยทางวิทยาศาสตร์นั้นถูกนำไปใช้ในอุตสาหกรรม ซึ่งเกี่ยวข้องกับความเป็นไปได้ในการเลือกใช้รหัสคอนโวลูชันที่ก่อให้เกิดข้อผิดพลาดจำนวนมาก (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 ]
รหัสคอนโวลูชันที่ถูกเจาะ

สามารถออกแบบรหัสคอนโวลูชันที่มีอัตราการเข้ารหัสใดๆ ก็ได้โดยอาศัยการเลือกพหุนาม[ 16 ]อย่างไรก็ตาม ในทางปฏิบัติ มักใช้กระบวนการเจาะรูเพื่อให้ได้อัตราการเข้ารหัสที่ต้องการการเจาะรูเป็นเทคนิคที่ใช้ในการสร้าง รหัสอัตรา m / nจากรหัสอัตราต่ำ "พื้นฐาน" (เช่น 1/ n ) โดยทำได้โดยการลบบิตบางส่วนในเอาต์พุตของตัวเข้ารหัส บิตจะถูกลบตามเมทริกซ์การเจาะรู เมทริกซ์การเจาะรูต่อไปนี้เป็นเมทริกซ์ที่ใช้บ่อยที่สุด:
| อัตราโค้ด | เมทริกซ์การเจาะ | ระยะทางอิสระ (สำหรับรหัสคอนโวลูชันมาตรฐาน K=7 ของ NASA) | ||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1/2 (ไม่มีรูปร่าง) |
| 10 | ||||||||||||||
| 2/3 |
| 6 | ||||||||||||||
| 3/4 |
| 5 | ||||||||||||||
| 5/6 |
| 4 | ||||||||||||||
| 7/8 |
| 3 |
ตัวอย่างเช่น หากเราต้องการสร้างรหัสที่มีอัตรา 2/3 โดยใช้เมทริกซ์ที่เหมาะสมจากตารางด้านบน เราควรนำเอาเอาต์พุตของตัวเข้ารหัสพื้นฐานมาใช้ และส่งบิตแรกจากสาขาแรกและบิตแรกจากสาขาที่สอง ลำดับการส่งข้อมูลที่เฉพาะเจาะจงนั้นถูกกำหนดโดยมาตรฐานการสื่อสารที่เกี่ยวข้อง
รหัสคอนโวลูชันแบบเจาะรูถูกนำมาใช้กันอย่างแพร่หลายในการสื่อสารผ่านดาวเทียมตัวอย่างเช่น ใน ระบบ Intelsatและการออกอากาศวิดีโอดิจิทัล
รหัสคอนโวลูชันแบบมีรูพรุนเรียกอีกอย่างว่า "แบบมีรูพรุน"
รหัสเทอร์โบ: การแทนที่รหัสคอนโวลูชัน

รหัสคอนโวลูชันแบบง่ายๆ ที่ถอดรหัสด้วย 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.
สรุปเนื้อหา
ข้อมูลสำคัญจากบทความ
ข้อมูลสำคัญเกี่ยวกับ รหัสคอนโวลูชัน
ในด้าน โทรคมนาคม รหัส คอนโวลูชัน เป็น รหัสแก้ไขข้อผิดพลาด ชนิดหนึ่งที่สร้างสัญลักษณ์พาริตีโดยใช้การประยุกต์ใช้ ฟังก์ชัน พหุนามบูลีนแบบ เลื่อน กับกระแสข้อมูล...
ประวัติศาสตร์
รหัสคอนโวลูชันถูกนำเสนอครั้งแรกในปี 1955 โดย ปีเตอร์ เอเลียส เชื่อกันว่ารหัสคอนโวลูชันสามารถถอดรหัสได้ด้วยคุณภาพตามอำเภอใจ แต่ต้องแลกมาด้วยการคำนวณที่ซับซ้อนและเวลาหน่วง ในปี 1967 แอนดรูว์ วิเทอร์บี พบว่ารหัสคอนโวลูชันสามารถถอดรหัสด้วยวิธีความน่าจะเป็นสูงสุด...
ที่ใช้รหัสคอนโวลูชัน
รหัสคอนโวลูชันถูกนำมาใช้อย่างกว้างขวางเพื่อให้การถ่ายโอนข้อมูลที่เชื่อถือได้ในแอปพลิเคชันต่างๆ มากมาย เช่น วิดีโอดิจิทัล วิทยุ การสื่อสารเคลื่อนที่ (เช่น ในเครือข่าย GSM, GPRS, EDGE และ 3G (จนถึง 3GPP รุ่น 7)) [ 4 ] [ 5 ] ) และการ สื่อสารผ่านดาวเทียม [ 6 ]...
การเข้ารหัสแบบคอนโวลูชัน
ในการเข้ารหัสข้อมูลแบบคอนโวลูชัน เริ่มต้นด้วย รีจิสเตอร์หน่วยความจำ k ตัว แต่ละตัวเก็บบิตอินพุตหนึ่งบิต เว้นแต่จะระบุไว้เป็นอย่างอื่น รีจิสเตอร์หน่วยความจำทั้งหมดเริ่มต้นด้วยค่า 0 ตัวเข้ารหัสมี ตัว บวกโมดูลัส 2 จำนวน n ตัว (ตัวบวกโมดูลัส 2 สามารถสร้างได้ด้วย...