การสร้างและตรวจสอบเมทริกซ์ของรหัสแฮมมิ่ง การสร้างเมทริกซ์ของรหัสบล็อก การตรวจจับข้อผิดพลาดและรหัสการแก้ไข

เมทริกซ์กำเนิดรหัสเชิงเส้นเรียกว่าเมทริกซ์ขนาด ซึ่งแถวเป็นเวกเตอร์พื้นฐาน

ตัวอย่างเช่น,

คือเมทริกซ์กำเนิดของรหัสสองคำ (000, 011)

กำลังสร้างโค้ด B จากตัวอย่างที่ 6.3

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

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

มาดูปัญหาของการถอดรหัสกันเถอะ

สมมติว่าสำหรับเวกเตอร์ไบนารีบางตัว codewords ทั้งหมดของ -code ,ตอบสนองตัวตน

โดยที่แสดงถึงผลคูณสเกลาร์ของเวกเตอร์ และ

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

โปรดทราบว่า (6.2) ใช้ได้กับโค้ดเวิร์ดทั้งหมด หากใช้ได้กับเวกเตอร์พื้นฐาน เช่น ถ้า

โดยที่ตัวยก T หมายถึงการขนย้าย

ยิ่งเราพบ "การตรวจสอบ" ดังกล่าวมากเท่าใด เราก็ยิ่งสามารถตรวจจับและแก้ไขข้อผิดพลาดได้มากขึ้นเท่านั้น

แบบฝึกหัด 6.4. พิสูจน์ว่าเช็คสร้างช่องว่างเชิงเส้น

เราเรียกสเปซนี้ว่าสเปซตั้งฉากกับโค้ดเชิงเส้นหรือ พื้นที่ทดสอบ.

แบบฝึกหัด 6.5. ค้นหามิติของปริภูมิเชิงเส้นของเช็ค

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

ผลที่ตามมาของการพิจารณาเหล่านี้คือทฤษฎีบท

ทฤษฎีบท.ขนาดของพื้นที่ทดสอบของรหัสเชิงเส้นเท่ากับ

เราเขียนพื้นฐานของพื้นที่ทดสอบเป็นเมทริกซ์

เรียกว่า ตรวจสอบเมทริกซ์รหัส.

เมทริกซ์ตรวจสอบและตัวกำเนิดมีความสัมพันธ์กันโดยความสัมพันธ์

จากความสัมพันธ์นี้ เราจะเห็นว่าสำหรับโค้ดเวิร์ดใดๆ เรามี

ข้อมูลประจำตัวนี้สามารถใช้เป็นเกณฑ์สำหรับลำดับตามอำเภอใจที่จะเป็นของรหัส เช่น เพื่อตรวจหาข้อผิดพลาด

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

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

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

เมทริกซ์เอกลักษณ์ของคำสั่งอยู่ที่ไหน และเมทริกซ์ของขนาดคืออะไร

เมทริกซ์ของรูปแบบ (6.6) เรียกว่าเมทริกซ์การสร้างที่ลดลง มุมมองอย่างเป็นระบบและรหัสที่เกี่ยวข้องจะถูกเรียก อย่างเป็นระบบ. การเข้ารหัสสำหรับรหัสที่เป็นระบบนั้นง่ายกว่ารหัสทั่วไปเล็กน้อย:

, (6.7)

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

สำหรับรหัสที่เป็นระบบที่มีเมทริกซ์ตัวสร้างในรูปแบบ (6.6) สามารถคำนวณเมทริกซ์ตรวจสอบได้โดยสูตร

แบบฝึกหัด 6.6. ตรวจสอบ (6.7) คำแนะนำ: ในการทำเช่นนี้ ให้แทนที่ (6.8) และ (6.6) เป็น (6.4)

จะหาเมทริกซ์ตรวจสอบสำหรับรหัสที่ไม่เป็นระบบได้อย่างไร?

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

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

ให้เราตั้งกฎ (การสร้าง) อย่างเป็นทางการตามที่มีการเข้ารหัส เช่น การแปลงลำดับข้อมูลเป็นโค้ดเวิร์ด

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

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

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

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

บล็อกเชิงเส้น(n, /c)-code ถูกกำหนดโดยเมทริกซ์ G ของขนาดอย่างสมบูรณ์ ถึงเอ็กซ์ พีด้วยองค์ประกอบเมทริกซ์ไบนารี ในกรณีนี้ โค้ดเวิร์ดแต่ละชุดเป็นการรวมแถวของเมทริกซ์ G เชิงเส้น และการรวมแถว G เชิงเส้นแต่ละชุดคือโค้ดเวิร์ด

รหัสบล็อกเชิงเส้นที่กำหนดโดยการสร้างเมทริกซ์จะถูกเรียก รหัสเมทริกซ์การแสดงเมทริกซ์การสร้างตามปกติ (บัญญัติ) มีลักษณะดังนี้:

ตัวอย่างเช่น สำหรับโค้ด (4, 3) ที่ง่ายที่สุดที่มีการตรวจสอบพาริตี เมทริกซ์การสร้างจะมีลักษณะดังนี้:

อนุญาต ที -(เ1; เสื้อ 2 , ..., ทีเค)จะเป็นบล็อกข้อความที่จะเข้ารหัสโดยใช้รหัสที่กำหนด

จากนั้นรหัสคำที่เกี่ยวข้อง ยูจะ

โดยคำนึงถึงโครงสร้างของเมทริกซ์ ชสัญลักษณ์โค้ดเวิร์ด และจะเป็นดังนี้:

กล่าวอีกนัยหนึ่ง ถึงสัญลักษณ์ซ้ายสุดของคำรหัสตรงกับสัญลักษณ์ของลำดับข้อมูลที่เข้ารหัสและส่วนที่เหลือ (n - ถึง)สัญลักษณ์เป็นการรวมกันเชิงเส้นของสัญลักษณ์ลำดับข้อมูล

ตัวอย่างเช่น ถ้าลำดับการป้อนข้อมูลตัวเข้ารหัส เสื้อ == (10 1) จากนั้นใช้เมทริกซ์สร้าง รหัสจะถูกสร้างขึ้นดังนี้:

8 ผู้บังคับบัญชาส่งหน่วยสอดแนมสามคนไปตามถนนสายแรก สาม - ไปตามทางที่สอง สอง - ไปตามทางที่สาม ไปตามทางที่สี่ เขาไปเอง เขียนเมทริกซ์การสร้างรหัสดังกล่าว

คำตอบ:ตามเนื้อเรื่องของภารกิจ ข้อความที่ผู้บัญชาการได้รับเป็นการส่วนตัวไม่สามารถบิดเบือนได้ ดังนั้นเราจึง จำกัด ตัวเองให้ศึกษาข้อมูลที่นักสู้ส่งมา ในกลุ่มที่ออกเดินทางไปตามถนนสายใดสายหนึ่ง นักสู้แต่ละคนจะต้องรายงานต่อผู้บังคับบัญชาเกี่ยวกับการพบวัตถุ (เราหมายถึงรายงานดังกล่าวเป็น "1") หรือเกี่ยวกับการไม่มีวัตถุ ("0") . ในกรณีที่ไม่มีการบิดเบือน รายงานของนักสู้แต่ละคนจากกลุ่มเดียวกันจะต้องตรงกัน เพราะฉะนั้น:

เมทริกซ์สามารถลดลงเป็นรูปแบบที่ยอมรับได้โดยการเรียงลำดับนักสู้ใหม่ เช่น ในเส้นทางแรก เขาส่งคนแรก สี่ และห้า บนเส้นทางที่สอง - ที่สอง หก และเจ็ด บนเส้นทางที่สาม - นักสู้ที่สามและแปด เราได้รับเมทริกซ์การสร้างต่อไปนี้:

รหัสที่กำหนดจึงเรียกว่า บล็อกเชิงเส้นอย่างเป็นระบบ(พี/cj รหัสที่มีการตรวจสอบพาริตี้ทั่วไป

ในระบบการสื่อสาร มีหลายกลยุทธ์ในการจัดการกับข้อผิดพลาด:

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

การตรวจจับข้อผิดพลาดและรหัสการแก้ไข

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

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

กับ รหัสแก้ไขข้อผิดพลาด, เชื่อมโยงอย่างใกล้ชิด รหัสตรวจจับข้อผิดพลาด. ซึ่งแตกต่างจากในอดีต หลังสามารถสร้างข้อผิดพลาดในข้อมูลที่ส่งเท่านั้น แต่ไม่สามารถแก้ไขได้

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

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

รหัสบล็อก

ให้ข้อมูลที่เข้ารหัสถูกแบ่งออกเป็นส่วนย่อยของความยาว เคบิตที่ถูกแปลงเป็น รหัสคำยาว นนิดหน่อย. จากนั้นรหัสบล็อกที่เกี่ยวข้องมักจะแสดงแทน ( น,เค) . เบอร์โทร ความเร็วรหัส.

ถ้าของเดิม เครหัสบิตไม่เปลี่ยนแปลงและเพิ่ม น − เค การตรวจสอบรหัสดังกล่าวเรียกว่า อย่างเป็นระบบ, มิฉะนั้น ไม่มีระบบ.

คุณสามารถตั้งรหัสบล็อกได้หลายวิธี รวมถึงตารางที่แต่ละชุดของ เคแมปบิตข้อมูล นรหัสคำบิต อย่างไรก็ตาม โค้ดที่ดีควรเป็นไปตามเกณฑ์ต่อไปนี้เป็นอย่างน้อย:

• ความสามารถในการแก้ไขข้อผิดพลาดให้ได้มากที่สุด
• ซ้ำซ้อนน้อยที่สุดเท่าที่จะทำได้
• ความสะดวกในการเข้ารหัสและถอดรหัส

เป็นเรื่องง่ายที่จะเห็นว่าข้อกำหนดเหล่านี้ขัดแย้งกัน นั่นเป็นเหตุผลว่าทำไมจึงมีรหัสจำนวนมากซึ่งแต่ละรหัสเหมาะสำหรับงานต่างๆ

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

ช่องว่างเชิงเส้น

เมทริกซ์กำเนิด

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

การตรวจสอบเมทริกซ์

ซึ่งหมายความว่าการดำเนินการเข้ารหัสสอดคล้องกับการคูณของต้นฉบับ เค-บิตเวกเตอร์บนเมทริกซ์ที่ไม่ใช่เอกพจน์ ชเรียกว่า สร้างเมทริกซ์.

อนุญาต เป็นพื้นที่ย่อยมุมฉากที่เกี่ยวกับ ค, ก ชมเป็นเมทริกซ์ที่กำหนดพื้นฐานของพื้นที่ย่อยนี้ สำหรับเวกเตอร์ใด ๆ จะเป็นจริง:

.

สมบัติและทฤษฎีบทที่สำคัญ

ระยะทางขั้นต่ำและความสามารถในการแก้ไข

ตอกโค๊ดและโค้ดที่สมบูรณ์แบบ

ให้มีบล็อกไบนารี ( น,เค) รหัสแก้ไข ที. แล้วความไม่เท่าเทียมกัน (เรียกว่า ขีดเส้นแบ่งเขตแดน):

.

รหัสที่ตอบสนองขอบเขตความเท่าเทียมกันนี้เรียกว่า มุ่งมั่น. รหัสที่สมบูรณ์แบบ ได้แก่ รหัส Hamming รหัสที่มีอำนาจแก้ไขขนาดใหญ่ซึ่งมักใช้ในทางปฏิบัติ (เช่น รหัสรีด-โซโลมอน) นั้นไม่สมบูรณ์แบบ

ได้รับพลังงาน

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

เนื่องจากการเข้ารหัสแก้ไขข้อผิดพลาดทำให้สามารถแก้ไขข้อผิดพลาดได้ แอปพลิเคชันจึงสามารถลดพลังงานของเครื่องส่งสัญญาณ ทำให้อัตราข้อมูลไม่เปลี่ยนแปลง การเพิ่มพลังงานหมายถึงความแตกต่างระหว่างอัตราส่วน s/n เมื่อมีและไม่มีการเข้ารหัส

แอปพลิเคชัน

ตรวจสอบเมทริกซ์- - [L.G. สุเมงโก. พจนานุกรมเทคโนโลยีสารสนเทศภาษาอังกฤษภาษารัสเซีย M.: GP TsNIIS, 2003.] หัวข้อ เทคโนโลยีสารสนเทศโดยทั่วไป EN ตรวจสอบเมทริกซ์ ... คู่มือนักแปลทางเทคนิค

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

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

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

- (รหัส LDPC จากภาษาอังกฤษ รหัสตรวจสอบความเท่าเทียมกันความหนาแน่นต่ำ รหัส LDPC รหัสความหนาแน่นต่ำ) รหัสที่ใช้ในการส่งข้อมูล กรณีพิเศษของรหัสบล็อกเชิงเส้นที่มีการตรวจสอบความเท่าเทียมกัน คุณลักษณะคือความหนาแน่นต่ำของนัยสำคัญ ... ... Wikipedia

รหัสที่มีการตรวจสอบความเท่าเทียมกันความหนาแน่นต่ำ (รหัส LDPC จากภาษาอังกฤษ รหัสตรวจสอบความเท่าเทียมกันความหนาแน่นต่ำ รหัส LDPC รหัสความหนาแน่นต่ำ) รหัสที่ใช้ในการส่งข้อมูล กรณีพิเศษของรหัสบล็อกเชิงเส้นที่มีการตรวจสอบความเท่าเทียมกัน คุณลักษณะ ... ... วิกิพีเดีย

รหัส Reed-Solomon เป็นรหัสวงจรที่ไม่ใช่ไบนารีที่ให้คุณแก้ไขข้อผิดพลาดในบล็อกข้อมูล องค์ประกอบของเวกเตอร์รหัสไม่ใช่บิต แต่เป็นกลุ่มของบิต (บล็อก) รหัสรีดโซโลมอนเป็นเรื่องธรรมดามาก ... ... Wikipedia

วงจรใด ๆ ( n, k) – รหัสสามารถกำหนดได้ตามคำจำกัดความ 2 การสร้างพหุนาม ก(x)หรือตรวจสอบพหุนาม

การรู้พหุนามเหล่านี้ทำให้เราสามารถสร้างเมทริกซ์กำเนิดและเมทริกซ์ตรวจสอบได้ สำหรับวงจร ( n, k) – โค้ดมีวิธีหาง่ายๆ เคการรวมรหัสอิสระเชิงเส้นสร้างเมทริกซ์การสร้าง วิธีนี้มีดังนี้ มีการเขียนพหุนามที่สร้าง ก(x). ตามคำจำกัดความ 2 การรวมกันที่สอดคล้องกับการสร้างพหุนามเป็นของวงจร ( n, k) - รหัส ตามคำจำกัดความ 1 การเปลี่ยนแปลงแบบวนรอบของชุดค่าผสมที่สอดคล้องกับ ก(x)ต้องเป็นรหัสเดียวกันด้วย ในทางพีชคณิต การเปลี่ยนแปลงสอดคล้องกับการคูณโค้ดเวิร์ดด้วย เอ็กซ์. ตั้งแต่รับปริญญา ก(x)เท่ากับ n-kในทำนองเดียวกันเราจะได้รับชุดค่าผสมของรหัส

เป็นการง่ายที่จะตรวจสอบว่าการผสมรหัสเหล่านี้เป็นอิสระเชิงเส้น หากเพียงเพราะองศาของพหุนามเหล่านี้ต่างกัน ดังนั้นพหุนามชุดนี้จึงสามารถใช้เป็น:

.

โดยการแปลงเบื้องต้น เมทริกซ์นี้สามารถลดลงเป็นรูปแบบบัญญัติ

ในทำนองเดียวกัน การใช้เช็คพหุนาม เราสามารถสร้างเช็คเมทริกซ์ได้

.

ตัวอย่าง 6.4 สำหรับรหัสวงจร (7,4) ที่มีพหุนามสร้าง (ดูตัวอย่างที่ 6.3) สร้างเมทริกซ์ตัวสร้าง

ดังนั้นเมทริกซ์ตัวสร้างสำหรับรหัสนี้มีรูปแบบ:

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

ทรัพย์สิน 6.1. ผลคูณของการรวมรหัสของรหัสวงจรโดยพหุนามโดยพลการทำให้ได้รหัสที่รวมกันของรหัสวงจรเดียวกัน

แน่นอน และผลิตภัณฑ์ใด ๆ ประเภทนี้มีค่าเท่ากับศูนย์ เช่น เป็นของพื้นที่ย่อยรหัส (ส่วน 6.2)

หลักฐานเบื้องต้นเพิ่มเติม:

ผลรวมที่ได้คือผลรวมของการเปลี่ยนแปลงแบบวนรอบของการรวมรหัส ซึ่งตามคุณสมบัติการปิดของรหัสกลุ่ม ควรให้รหัสแบบวนรอบเดียวกัน

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

ค่าสัมประสิทธิ์ที่ เอ็กซ์ทำงาน เท่ากับ

ข้อกำหนดที่มี ปรากฏขึ้นเนื่องจากข้อกำหนดในผลิตภัณฑ์ที่มี แต่เนื่องจาก เช่น , ที่ . ความเท่าเทียมกันสำหรับสามารถแสดงเป็นผลิตภัณฑ์สเกลาร์:

ในผลิตภัณฑ์นี้ เวกเตอร์แรกสอดคล้องกับ โอ้). เวกเตอร์ที่สองประกอบด้วยค่าสัมประสิทธิ์ ข(x), จัดเรียงในลำดับย้อนกลับและเลื่อนตามวัฏจักร เจ+1 องค์ประกอบทางด้านขวา

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

เนื่องจากความเฉพาะเจาะจงนี้ จึงจำเป็นต้องเขียนค่าสัมประสิทธิ์ของเมทริกซ์ตรวจสอบในคำอธิบายเมทริกซ์ของรหัสในลำดับย้อนกลับ ในกรณีนี้เงื่อนไข

ตัวอย่าง 6.5 สร้างเมทริกซ์ของการตรวจสอบสำหรับวงจร (7,4) - รหัสจากตัวอย่างก่อนหน้า m ซึ่งเป็นตัวประกอบของทวินาม และไม่ใช่ตัวประกอบของทวินามใดๆ ที่มีดีกรีน้อยกว่า รากของพหุนามเหล่านี้มีลำดับ 2 ม. -1 เช่น พวกมันเป็นองค์ประกอบดั้งเดิมของฟิลด์ GF(2ม.).ซึ่งหมายความว่าการสร้างพหุนามของรหัส Hamming จะสร้างฟิลด์ GF(2ม.).

ให้เราตกลงในรหัสวัฏจักรก่อน n-kองค์ประกอบของการรวมรหัสนั่นคือค่าสัมประสิทธิ์ที่ ใช้เป็นองค์ประกอบในการทดสอบและสุดท้าย เคองค์ประกอบนั่นคือค่าสัมประสิทธิ์ที่ , - เป็นข้อมูล (รูปที่ 6.0)

ก 0 ก, ….., ก n-1 = ก 0 x 0 +a 1 x 1 + …. + ก n-1 x n+1

x 0 x 1 x 2 x n-k-1 x n-k x n-2 x n-1

ให้ x1, x2, ..., xk แสดงคำของบิตข้อมูล k ที่อินพุตของตัวเข้ารหัส ซึ่งเข้ารหัสเป็นรหัส n บิตคำ C:

อินพุตตัวเข้ารหัส: เอ็กซ์=[x 1, x 2, ...,xk]

เอาต์พุตตัวเข้ารหัส: ค=[ค 1, ค 2, ..., ซีเอ็น]

ให้สร้างเมทริกซ์พิเศษ จี เอ็น , เค,

การกำหนดรหัสบล็อก ( น,เค).

แถวเมทริกซ์ จี เอ็น , เคจะต้องเป็นอิสระเชิงเส้น

จากนั้นรหัสที่อนุญาต คตรงกับคำที่เข้ารหัส เอ็กซ์:

ค=x 1 กรัม 1 + x 2 กรัม 2 + ... + x ก ก ก.

รูปแบบที่เป็นระบบ (บัญญัติ) ของเมทริกซ์การสร้าง ชขนาด เค x น :

เมทริกซ์กำเนิดของรหัสที่เป็นระบบสร้างรหัสบล็อกเชิงเส้นซึ่งตัวแรก เคบิตของคำรหัสใด ๆ จะเหมือนกันกับบิตข้อมูล และส่วนที่เหลือ ร=น-เคบิตของคำรหัสใด ๆ คือการรวมกันเชิงเส้น เคบิตข้อมูล

การตรวจสอบเมทริกซ์ เอช เอ็น เคมันมี ร x นองค์ประกอบและเป็นความจริง:

ค x เอช ที = 0.

นิพจน์นี้ใช้เพื่อตรวจสอบการรวมรหัสที่ได้รับ หากไม่พอใจความเท่ากับศูนย์ เราก็จะได้เมทริกซ์แถว || ค 1 , ค 2 , ..., ร|| เรียกว่ากลุ่มอาการผิดพลาด

ตอกโค้ด. ความสามารถในการแก้ไขและนักสืบ กฎสำหรับการเลือกอัตราส่วนระหว่างความยาวของคำรหัสและจำนวนบิตข้อมูล การก่อตัวของการสร้างและการตรวจสอบเมทริกซ์ของรหัส Hamming การตีความกลุ่มอาการผิดพลาด

พิจารณารหัส Hamming ด้วยระยะทางรหัส ง=3 ซึ่งช่วยให้คุณแก้ไขข้อผิดพลาดเดียว ( ง=2คิวแม็กซ์+1).

จำนวนรหัสที่อนุญาตสำหรับรหัสที่มี ง=3 สำหรับรหัส Hamming อย่างเคร่งครัดเท่ากับ 2 น/(น+1). อันดับแรก เคบิตของการรวมรหัสของรหัสถูกใช้เป็นข้อมูลและจำนวนของรหัสนั้นเท่ากับ

เค= บันทึก 2 (2 น/(น+1)] = น- บันทึก 2 ( น+1).

สมการนี้มีคำตอบเป็นจำนวนเต็ม เค= 0, 1, 4, 11, 26 ซึ่งกำหนดรหัส Hamming ที่สอดคล้องกัน: (3,1)-รหัส, (7,4)-รหัส, (15,11)-รหัส เป็นต้น (เสมอ น=2ว‑1).

การตรวจสอบเมทริกซ์ ชมตอกโค้ด ( ร=n-kเส้นและ นคอลัมน์): สำหรับรหัสไบนารี (n,k) n=2 w -1 คอลัมน์ประกอบด้วยเวกเตอร์ไบนารีที่เป็นไปได้ทั้งหมดที่มีองค์ประกอบ r=n-k ยกเว้นเวกเตอร์ที่มีองค์ประกอบเป็นศูนย์ทั้งหมด.

มันง่ายที่จะตรวจสอบว่า ช x เอช ที= 0 (ศูนย์เมทริกซ์ของขนาด เค x รองค์ประกอบ).

ตัวอย่าง.ตรวจสอบการทำงานของรหัสเมื่อส่งข้อความ เอ็กซ์=1011. การรวมรหัสที่ส่งจะสร้างเป็นชุดค่าผสมเชิงเส้น (การบวกโมดูโล 2) ของแถวที่ 1, 3, 4 ของเมทริกซ์ ช 7,4:

เราคิดว่าสำหรับคำรหัสที่ส่ง คข้อผิดพลาด 0000100 ได้รับผลกระทบ ส่งผลให้ฝ่ายรับได้รับคำนั้น ค"=10111 10.

จากนั้นเมื่อคูณ C" ด้วยเมทริกซ์ตรวจสอบ เอช ทีเราได้แถวเมทริกซ์ของกลุ่มอาการผิดพลาดที่สอดคล้องกับคอลัมน์นั้นของเมทริกซ์ตรวจสอบ ชมด้วยหมายเลขบิตที่มีข้อผิดพลาด

การเปรียบเทียบซินโดรมที่เกิดกับสตริง ชม T , เราได้บิต #5 ทางซ้ายนั้นผิด

ตัวถอดรหัส Hamming สามารถทำงานได้สองอย่าง แยกกันไม่ออกโหมด:

โหมดแก้ไขข้อผิดพลาด (แก้ไข) (เพราะ งนาที = 3 จากนั้นจะอนุญาตให้คุณแก้ไขข้อผิดพลาดเดียว);

โหมดตรวจจับข้อผิดพลาด (เพราะ งนาที = 3 จากนั้นตรวจพบข้อผิดพลาดหลายหลาก ถาม 2 ปอนด์) หากซินโดรมไม่เท่ากับ 0 แสดงว่าตัวถอดรหัสส่งสัญญาณข้อผิดพลาด

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

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

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

ความยาวรหัสเพิ่มขึ้นจาก 2 ว-1 ถึง 2 วซึ่งสะดวกในแง่ของการถ่ายโอนข้อมูลและการจัดเก็บ

ระยะทางขั้นต่ำ งรหัส Hamming ที่ขยายเพิ่มขั้นต่ำคือ 4 ซึ่งทำให้สามารถตรวจจับ (!) ข้อผิดพลาด 3 เท่าได้

ความเท่าเทียมกันเพิ่มเติมช่วยให้สามารถใช้ตัวถอดรหัสในโหมดไฮบริดใหม่ - การตรวจจับและแก้ไขข้อผิดพลาด

พิจารณาส่วนขยายของ (7,4,3) Hamming code

เวกเตอร์รหัสแต่ละตัว ค a ได้มาจากเวกเตอร์โค้ด c โดยการเพิ่มแพริตีบิตพิเศษ ค ก = ( ค 1 , ..., ค 7, ค 8) โดยที่ .

การตรวจสอบเมทริกซ์ ชมรหัส (8,4) ได้มาจากเมทริกซ์ตรวจสอบของรหัส (7,4) ในสองขั้นตอน:

เพิ่มคอลัมน์ศูนย์ในเมทริกซ์ของรหัส (7,4)

เมทริกซ์ผลลัพธ์จะเสริมด้วยแถวที่ประกอบด้วยเมทริกซ์ทั้งหมด

เราได้รับ:

ด้วยการถอดรหัสซินโดรมิก

ส" = ค"Ä ชมที ,

และส่วนประกอบทั้งหมดของ s" ต้องเท่ากับ 0

ด้วยข้อผิดพลาดเดียว s "(4) = 1 ตามค่าของซินโดรม (3 บิตล่าง) เราจะค้นหาและแก้ไข (กลับด้าน) บิตที่ผิดพลาด

ด้วยองค์ประกอบข้อผิดพลาดสองเท่า s "(4) = 0 และซินโดรมไม่ใช่ศูนย์ ตรงกันข้ามกับรหัส Hamming มาตรฐาน สถานการณ์นี้ ตรวจพบแล้วแต่ไม่ได้รับการแก้ไข (มีการร้องขอให้ส่งคำซ้ำ เป็นต้น)

ดังนั้น ตัวถอดรหัส Hamming แบบขยายสามารถใช้ในโหมดใดโหมดหนึ่งจากสองโหมดที่ใช้ร่วมกันไม่ได้:

เพื่อแก้ไขข้อผิดพลาดเดี่ยวและตรวจหาข้อผิดพลาดซ้ำ

เพื่อตรวจหาข้อผิดพลาดสามข้อ