อ่าน 3 นาที
รหัสครอบคลุม
ในทฤษฎีการเข้ารหัสรหัสครอบคลุม (covering code ) คือเซตขององค์ประกอบ (เรียกว่ารหัสคำ ) ในปริภูมิหนึ่ง ซึ่งมีคุณสมบัติว่าทุกองค์ประกอบในปริภูมิจะอยู่ภายในระยะทางคงที่จากรหัสคำบางคำ
รหัสครอบคลุม
ในทฤษฎีการเข้ารหัสรหัสครอบคลุม (covering code ) คือเซตขององค์ประกอบ (เรียกว่ารหัสคำ ) ในปริภูมิหนึ่ง ซึ่งมีคุณสมบัติว่าทุกองค์ประกอบในปริภูมิจะอยู่ภายในระยะทางคงที่จากรหัสคำบางคำ
คำนิยาม
ให้, , เป็นจำนวนเต็มรหัสบนตัวอักษรQที่มีขนาด | Q | = qเรียกว่า รหัสq -ary R -covering ที่มีความยาว n ถ้าสำหรับทุกคำจะมีคำรหัส C ที่ ทำให้ระยะทางแฮมมิง . กล่าวอีกนัยหนึ่งทรงกลม (หรือลูกบอลหรือโดเมนของหมากรุก) ที่มีรัศมีR เมื่อเทียบกับเมตริก แฮม มิงรอบคำรหัสของCจะต้องครอบคลุมปริภูมิเมตริกจำกัด รัศมี การครอบคลุมของรหัสCคือR ที่เล็กที่สุด ที่ทำให้Cเป็น รหัส R -covering รหัสสมบูรณ์ทุก รหัส เป็นรหัสครอบคลุมที่มีขนาดเล็กที่สุด
ตัวอย่าง
C = {0134,0223,1402,1431,1444,2123,2234,3002,3310,4010,4341} เป็นรหัส 5-ary 2-covering ที่มีความยาว 4 [ 1 ]
ปัญหาการปกปิด
การกำหนดขนาดขั้นต่ำของ รหัส q -ary R -covering ที่มีความยาวnเป็นปัญหาที่ยากมาก ในหลายกรณี มีเพียงขอบเขตบนและล่าง เท่านั้น ที่ทราบ โดยมีช่องว่างขนาดใหญ่ระหว่างกัน การสร้างรหัส covering ทุกครั้งจะให้ขอบเขตบนของK q ( n , R ) ขอบเขตล่างรวมถึงขอบเขต covering ทรงกลมและขอบเขตของ Rodemich และ [ 2 ]ปัญหาcoveringเกี่ยวข้องอย่างใกล้ ชิดกับปัญหาpacking ในกล่าว คือการกำหนดขนาดสูงสุดของ รหัส q -ary e - error correctingที่มีความยาว n
ปัญหาเกี่ยวกับการพนันฟุตบอล
กรณีเฉพาะอย่างหนึ่งคือปัญหาการพนันฟุตบอล แบบพูล ซึ่ง มีเป้าหมายคือการคิดค้นระบบการพนันสำหรับ แมตช์ ฟุตบอลnแมตช์ ที่ไม่ว่าผลจะเป็นอย่างไร ก็จะมี "การพลาด" ไม่เกินRครั้ง ดังนั้น สำหรับ แมตช์ nแมตช์ที่มี "การพลาด" ไม่เกินหนึ่งครั้งจึงต้องการ การครอบคลุมแบบไตรภาค K 3 ( n ,1)
ถ้าเช่นนั้นจะต้องใช้ 3 n - kดังนั้นสำหรับn = 4, k = 2 จะต้องใช้ 9 ตัว; สำหรับn = 13, k = 3 จะต้องใช้ 59049 ตัว[ 3 ] ขอบเขตที่ดีที่สุดที่ทราบในปี 2011 [ 4 ]คือ
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| K 3 ( n ,1) | 1 | 3 | 5 | 9 | 27 | 71-73 | 156-186 | 402-486 | 1060-1269 | 2854-3645 | 7832-9477 | 21531-27702 | 59049 | 166610-177147 |
| K 3 ( n ,2) | 1 | 3 | 3 | 8 | 15-17 | 26-34 | 54-81 | 130-219 | 323-555 | 729 | 1919-2187 | 5062-6561 | 12204-19683 | |
| K 3 ( n ,3) | 1 | 3 | 3 | 6 | 11-12 | 14-27 | 27-54 | 57-105 | 117-243 | 282-657 | 612-1215 | 1553-2187 |
แอปพลิเคชัน
งานมาตรฐาน[ 5 ]เกี่ยวกับรหัสครอบคลุมระบุแอปพลิเคชันต่อไปนี้
- การบีบอัดพร้อมการบิดเบือน
- การบีบอัดข้อมูล
- ข้อผิดพลาด ในการถอดรหัสและการลบข้อมูล
- การออกอากาศในเครือข่ายเชื่อมต่อ
- พูลฟุตบอล[ 6 ]
- ความทรงจำที่เขียนเพียงครั้งเดียว
- เกมเบอร์เลแคมป์-เกล
- การเข้ารหัสเสียง
- การสื่อสารเคลื่อนที่
- ผลรวม ของเซตย่อยและกราฟเคย์ลีย์
ลิงก์ภายนอก
- เอกสารเกี่ยวกับรหัสการครอบคลุม
- ขอบเขตบน
สรุปเนื้อหา
ข้อมูลสำคัญจากบทความ
ข้อมูลสำคัญเกี่ยวกับ รหัสครอบคลุม
ในทฤษฎีการเข้ารหัสรหัสครอบคลุม (covering code ) คือเซตขององค์ประกอบ (เรียกว่ารหัสคำ ) ในปริภูมิหนึ่ง ซึ่งมีคุณสมบัติว่าทุกองค์ประกอบในปริภูมิจะอยู่ภายในระยะทางคงที่จากรหัสคำบางคำ
คำนิยาม
ให้, , เป็น จำนวนเต็ม รหัสบน ตัวอักษร Q ที่มีขนาด | Q | = q เรียกว่า รหัส q -ary R -covering ที่มีความยาว n ถ้าสำหรับทุกคำจะมี คำรหัส C ที่ ทำให้ ระยะทางแฮมมิง .
ตัวอย่าง
C = {0134,0223,1402,1431,1444,2123,2234,3002,3310,4010,4341} เป็นรหัส 5-ary 2-covering ที่มีความยาว 4 [ 1 ]
ปัญหาการปกปิด
การกำหนดขนาดขั้นต่ำของ รหัส q -ary R -covering ที่มีความยาว n เป็นปัญหาที่ยากมาก ในหลายกรณี มีเพียง ขอบเขตบนและล่าง เท่านั้น ที่ทราบ โดยมีช่องว่างขนาดใหญ่ระหว่างกัน การสร้างรหัส covering ทุกครั้งจะให้ขอบเขตบนของ K q ( n , R ) ขอบเขตล่างรวมถึงขอบเขต covering...