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

อ่าน 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 ]คือ

n1 2 3 4 5 6 7 8 9 10 11 12 13 14
K 3 ( n ,1) 13592771-73 156-186 402-486 1060-1269 2854-3645 7832-9477 21531-27702 59049166610-177147
K 3 ( n ,2) 133815-17 26-34 54-81 130-219 323-555 7291919-2187 5062-6561 12204-19683
K 3 ( n ,3) 133611-12 14-27 27-54 57-105 117-243 282-657 612-1215 1553-2187

แอปพลิเคชัน

งานมาตรฐาน[ 5 ]เกี่ยวกับรหัสครอบคลุมระบุแอปพลิเคชันต่อไปนี้

  • เอกสารเกี่ยวกับรหัสการครอบคลุม
  • ขอบเขตบน
ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Covering_code&oldid=1323201326 "

สรุปเนื้อหา

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

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

ในทฤษฎีการเข้ารหัสรหัสครอบคลุม (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...