รหัสไบนารี Golay แบบขยาย
เมทริกซ์ตัวสร้าง
ตั้งชื่อตาม	มาร์เซล เจ.อี. โกเลย์
การจำแนกประเภท
พิมพ์	รหัสบล็อกเชิงเส้น
ความยาวบล็อก	24
ความยาวของข้อความ	12
ประเมิน	12/24 = 0.5
ระยะทาง	8
ขนาดตัวอักษร	2
สัญกรณ์	${\displaystyle [24,12,8]_{2}}$-รหัส
วี ที อี

รหัสไบนารี Golay ที่สมบูรณ์แบบ
ตั้งชื่อตาม	มาร์เซล เจ.อี. โกเลย์
การจำแนกประเภท
พิมพ์	รหัสบล็อกเชิงเส้น
ความยาวบล็อก	23
ความยาวของข้อความ	12
ประเมิน	23/12 ~ 0.522
ระยะทาง	7
ขนาดตัวอักษร	2
สัญกรณ์	${\displaystyle [23,12,7]_{2}}$-รหัส
วี ที อี

ในคณิตศาสตร์และวิศวกรรมอิเล็กทรอนิกส์รหัสGolay แบบไบนารี เป็น รหัสแก้ไขข้อผิดพลาดเชิงเส้นชนิดหนึ่งที่ใช้ในการสื่อสารดิจิทัลรหัส Golay แบบไบนารีพร้อมกับรหัส Golay แบบไตรนารีมีความเชื่อมโยงอย่างลึกซึ้งกับทฤษฎีกลุ่มสปอราดิกจำกัดในคณิตศาสตร์^{[ 1 ]}รหัสเหล่านี้ตั้งชื่อเพื่อเป็นเกียรติแก่Marcel JE Golayซึ่งบทความในปี 1949 ของเขา^{[ 2 ]}ที่แนะนำรหัสเหล่านี้ได้รับการขนานนามโดยER Berlekampว่าเป็น "หน้าเดียวที่ตีพิมพ์ที่ดีที่สุด" ในทฤษฎีการเข้ารหัส^{[ 3 ]}

มีรหัส Golay แบบไบนารีสองแบบที่เกี่ยวข้องกันอย่างใกล้ชิด รหัส Golay แบบไบนารีแบบขยายG ₂₄ (บางครั้งเรียกว่า "รหัส Golay" ในทฤษฎีกลุ่มจำกัด) เข้ารหัสข้อมูล 12 บิตในคำ 24 บิตในลักษณะที่สามารถแก้ไขข้อผิดพลาด 3 บิตหรือตรวจจับข้อผิดพลาด 7 บิตได้ ส่วนอีกแบบคือรหัสGolay แบบไบนารีสมบูรณ์G ₂₃มีคำรหัสยาว 23 และได้มาจากการลบตำแหน่งพิกัดหนึ่งตำแหน่งออกจากรหัส Golay แบบไบนารีแบบขยาย (ในทางกลับกัน รหัส Golay แบบไบนารีแบบขยายได้มาจากการเพิ่มบิตพาริตี ในรหัส Golay แบบไบนารีสมบูรณ์ ) ในสัญกรณ์การเข้ารหัสมาตรฐาน รหัสเหล่านี้มีพารามิเตอร์ [24, 12, 8] และ [23, 12, 7] ซึ่งสอดคล้องกับความยาวของคำรหัสมิติของรหัส และระยะทางแฮมมิง ขั้นต่ำ ระหว่างคำรหัสสองคำ ตามลำดับ

ในทางคณิตศาสตร์ รหัสไบนารีแบบขยายของโกเลย์G ₂₄ประกอบด้วยปริภูมิย่อยเชิงเส้น 12 มิติ WของปริภูมิV = F²⁴ ₂W คือชุดคำ 24 บิต โดยที่องค์ประกอบสองตัวใดๆ ในWจะแตกต่างกันอย่างน้อย 8 พิกัด Wเรียกว่ารหัสเชิงเส้นเพราะเป็นปริภูมิเวกเตอร์ โดยรวมแล้วWประกอบด้วยองค์ประกอบ 4096 = ^{2¹² ตัว}

• องค์ประกอบของWเรียกว่ารหัสคำหรืออาจอธิบายได้ว่าเป็นเซตย่อยของเซตที่มี 24 องค์ประกอบ โดยการบวกหมายถึงการหาผลต่างสมมาตรของเซตย่อยเหล่านั้น
• ในรหัสไบนารีแบบขยายของ Golay คำรหัสทั้งหมดจะมีน้ำหนักแฮมมิง เท่ากับ 0, 8 , 12, 16 หรือ 24 คำรหัสที่มีน้ำหนัก 8 เรียกว่าoctadsและคำรหัสที่มีน้ำหนัก 12 เรียกว่าdodecads
• อ็อกแทดของรหัสG _{24 เป็นองค์ประกอบของ} ระบบสไตเนอร์ S(5,8,24) มี อ็อกแทดทั้งหมด 759 = 3 × 11 × 23และมีส่วนเติมเต็มอีก 759 ส่วน ดังนั้นจึงมีโดเดแคด ทั้งหมด 2576 = 2 ⁴ × 7 × 23
• กลุ่มเลขแปดสองกลุ่มจะตัดกัน (มีเลข 1 ร่วมกัน) ที่พิกัด 0, 2 หรือ 4 ในการแสดงเวกเตอร์ไบนารี (นี่คือขนาดการตัดกันที่เป็นไปได้ในการแสดงเซตย่อย) กลุ่มเลขแปดและกลุ่มเลขสิบสองจะตัดกันที่พิกัด 2, 4 หรือ 6
• นอกเหนือจากการกำหนดหมายเลขพิกัดใหม่แล้วWมีลักษณะเฉพาะตัว

รหัสไบนารีโกเลย์G ₂₃เป็นรหัสสมบูรณ์กล่าวคือ ทรงกลมรัศมีสามที่ล้อมรอบคำรหัสจะก่อให้เกิดการแบ่งส่วนของปริภูมิเวกเตอร์G _{23 เป็น} ปริภูมิย่อย 12 มิติของปริภูมิF²³ ₂.

กลุ่มออโตมอร์ฟิซึมของรหัสไบนารีสมบูรณ์ของโกเลย์G ₂₃ (หมายถึงกลุ่มย่อยของกลุ่มS ₂₃ของการเรียงสับเปลี่ยนพิกัดของF)²³ ₂ซึ่งทำให้G ₂₃ไม่เปลี่ยนแปลง) คือกลุ่ม Mathieu กลุ่มออโตมอร์ฟิซึมของรหัส Golay ไบนารีแบบขยายคือกลุ่ม Mathieuซึ่งมีอันดับ2 ¹⁰ × 3 ³ × 5 × 7 × 11 × 23มีคุณสมบัติทรานซิทีฟบนอ็อกแทดและบนโดเดแคด กลุ่ม Mathieu อื่นๆ เกิดขึ้นเป็นตัวรักษาเสถียรภาพ ขององค์ประกอบหนึ่งหรือหลาย ตัว ของW${\displaystyle M_{23}}$${\displaystyle M_{24}}$${\displaystyle M_{24}}$

มีคำหนึ่งคำที่มีน้ำหนัก 24 ซึ่งเป็นปริภูมิย่อยไม่เปลี่ยนแปลงแบบ 1 มิติดังนั้นจึงมีการแสดงแทนแบบลดทอนไม่ได้แบบ 11 มิติบนฟิลด์ที่มี 2 องค์ประกอบ นอกจากนี้ เนื่องจากรหัสโกเลย์ไบนารีเป็นปริภูมิย่อยแบบ 12 มิติของปริภูมิแบบ 24 มิติ จึงกระทำบน ปริภูมิผลหารแบบ 12 มิติด้วยซึ่งเรียกว่ารหัสโกเลย์ไบนารีคำในรหัสจะอยู่ในเซต เดียวกัน กับคำที่มีความยาว 0, 1, 2, 3 หรือ 4 ในกรณีสุดท้าย คำรหัส 6 คำ (ที่ไม่ซ้ำกัน) จะอยู่ในเซตเดียวกันทั้งหมด มีปริภูมิย่อยไม่เปลี่ยนแปลงแบบ 11 มิติ ซึ่งประกอบด้วยคำรหัสที่มีน้ำหนักคี่ ซึ่งให้การแสดงแทนแบบ 11 มิติที่สองบนฟิลด์ที่มี 2 องค์ประกอบ ${\displaystyle M_{24}}$${\displaystyle M_{24}}$${\displaystyle M_{24}}$

• รหัสแบบพจนานุกรม : เรียงลำดับเวกเตอร์ในVตามพจนานุกรม (กล่าวคือ ตีความว่าเป็นจำนวนเต็มไบนารี 24 บิตที่ไม่มีเครื่องหมาย และใช้ลำดับปกติ) เริ่มต้นด้วยw ₀ = 0 กำหนดw ₁ , w ₂ , ..., w ₁₂โดยใช้กฎที่ว่าw _n คือจำนวนเต็มที่เล็กที่สุดซึ่งแตกต่างจาก ผลรวมเชิงเส้นทั้งหมดขององค์ประกอบก่อนหน้าอย่างน้อยแปดพิกัด จากนั้นWสามารถกำหนดได้ว่าเป็นสแปนของw ₁ , ..., w ₁₂
• กลุ่ม Mathieu : Witt ตีพิมพ์ผลงานการสร้างกลุ่ม Mathieu ที่ใหญ่ที่สุดในปี พ.ศ. 2481 ซึ่งสามารถใช้สร้างรหัส Golay แบบไบนารีที่ขยายได้^{[ 4 ]}
• รหัสเศษเหลือกำลังสอง : พิจารณาเซตNของค่าที่ไม่ใช่เศษเหลือกำลังสอง (mod 23) ซึ่งเป็นเซตย่อย 11 องค์ประกอบของกลุ่มวัฏจักรZ /23 Zพิจารณาการแปลt + Nของเซตย่อยนี้ เพิ่มการแปลแต่ละครั้งเป็นเซต 12 องค์ประกอบS _tโดยการเพิ่มองค์ประกอบ ∞ จากนั้นกำหนดป้ายกำกับองค์ประกอบพื้นฐานของVด้วย 0, 1, 2, ..., 22, ∞, Wสามารถกำหนดได้ว่าเป็นช่วงของคำS _tรวมกับคำที่ประกอบด้วยเวกเตอร์พื้นฐานทั้งหมด (รหัสที่สมบูรณ์แบบได้มาจากการตัด ∞ ออก)
• ในฐานะรหัสแบบวงจร : รหัส G ₂₃ ที่สมบูรณ์แบบ สามารถสร้างขึ้นได้โดยการแยกตัวประกอบของฟิลด์ไบนารีGF(2) : เป็นรหัสที่สร้างขึ้นโดย[ ^{5 ] สามารถ}ใช้ตัวประกอบที่ไม่สามารถลดทอนได้ระดับ 11 ตัวใดตัวหนึ่งเพื่อสร้างรหัสได้^{[ 6 ]}${\displaystyle x^{23}+1}$$${\displaystyle x^{23}+1=(x+1)(x^{11}+x^{9}+x^{7}+x^{6}+x^{5}+x+1)(x^{11}+x^{10}+x^{6}+x^{5}+x^{4}+x^{2}+1).}$$${\displaystyle \left(x^{11}+x^{10}+x^{6}+x^{5}+x^{4}+x^{2}+1\right)}$
• การสร้างของ Turyn ในปี 1967 "การสร้างรหัส Golay แบบไบนารีอย่างง่าย" ซึ่งเริ่มต้นจากรหัส Hammingที่มีความยาว 8 และไม่ใช้เศษกำลังสอง mod 23 ^{[ 7 ]}
• จากระบบ Steiner S(5,8,24)ซึ่งประกอบด้วยเซตย่อย 759 เซตของเซต 24 หากตีความส่วนสนับสนุนของแต่ละเซตย่อยเป็นรหัสคำ 0-1 ที่มีความยาว 24 (โดยมีน้ำหนักแฮมมิง 8) สิ่งเหล่านี้คือ "อ็อกแทด" ในรหัสไบนารี Golay รหัส Golay ทั้งหมดสามารถหาได้โดยการหาผลต่างสมมาตรของเซตย่อยซ้ำๆ กล่าวคือ การบวกไบนารี วิธีที่ง่ายกว่าในการเขียนระบบ Steiner หรืออ็อกแทดคือMiracle Octad Generatorของ RT Curtis ซึ่งใช้การจับคู่แบบ 1:1 เฉพาะระหว่างการแบ่ง 35 ส่วนของเซต 8 ออกเป็นสองเซต 4 และการแบ่ง 35 ส่วนของปริภูมิเวกเตอร์จำกัดออกเป็น 4 ระนาบ^{[ 8 ]}ปัจจุบันมักใช้แนวทางที่กระชับของรหัสเฮกซาของ Conway ซึ่งใช้อาร์เรย์ 4×6 ของเซลล์สี่เหลี่ยม${\displaystyle \mathbb {F} _{2}^{4}}$
• ตำแหน่งที่ชนะในเกมคณิตศาสตร์โมกุล: ตำแหน่งในเกมโมกุลคือแถวของเหรียญ 24 เหรียญ แต่ละตาประกอบด้วยการโยนเหรียญตั้งแต่หนึ่งถึงเจ็ดเหรียญ โดยที่เหรียญซ้ายสุดที่โยนได้จะเปลี่ยนจากหัวเป็นก้อย ตำแหน่งที่แพ้คือตำแหน่งที่ไม่มีการเคลื่อนไหวที่ถูกต้อง หากตีความหัวเป็น 1 และก้อยเป็น 0 การเคลื่อนไหวไปยังรหัสคำจากรหัสไบนารี Golay แบบขยายจะรับประกันว่าจะสามารถบังคับให้ชนะได้
• เมทริกซ์กำเนิดสำหรับรหัส Golay แบบไบนารีคือIAโดยที่Iคือเมทริกซ์เอกลักษณ์ขนาด 12×12 และAคือเมทริกซ์ส่วนเติมเต็มของเมทริกซ์ประชิดของทรงยี่สิบหน้า

การใช้รูปแบบ " Miracle Octad Generator " นั้นสะดวกกว่า โดยใช้พิกัดในอาร์เรย์ 4 แถว 6 คอลัมน์ การบวกจะใช้ผลต่างสมมาตร คอลัมน์ทั้ง 6 คอลัมน์มีค่าเท่ากัน ซึ่งเท่ากับค่าของแถวบนสุด

การแบ่งคอลัมน์ทั้ง 6 คอลัมน์ออกเป็น 3 คู่ของคอลัมน์ที่อยู่ติดกัน ก่อให้เกิด ไตรโอ ( trio ) ซึ่งเป็นการแบ่งออกเป็น 3 เซตอ็อกทาด (octad) กลุ่มย่อยกลุ่มเชิงเส้นพิเศษเชิงโปร เจกทีฟ PSL(2,7) x S ₃ของกลุ่มย่อยไตรโอของ M ₂₄มีประโยชน์สำหรับการสร้างฐาน PSL(2,7) สลับอ็อกทาดภายในแบบขนาน S ₃สลับอ็อกทาดทั้ง 3 แบบ

พื้นฐานเริ่มต้นด้วยอ็อกแทด T:

0 1 1 1 1 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 

และกลุ่มแปดหลักที่คล้ายกันอีก 5 กลุ่ม ผลรวมNของคำรหัสทั้ง 6 คำนี้ประกอบด้วยเลข 1 ทั้งหมด การเพิ่ม N ให้กับคำรหัสจะสร้างคำเสริมของคำรหัสนั้น

Griess (หน้า 59) ใช้การติดฉลากดังนี้:

∞ 0 | ∞ 0 | ∞ 0 3 2 | 3 2 | 3 2 5 1 | 5 1 | 5 1 6 4 | 6 4 | 6 4 

PSL(2,7) เป็นกลุ่มเศษส่วนเชิงเส้นที่สร้างขึ้นโดยธรรมชาติจาก (0123456) และ (0∞)(16)(23)(45) วัฏจักร 7 กระทำต่อ T เพื่อให้ได้ปริภูมิย่อยที่รวมถึงองค์ประกอบพื้นฐานด้วย

0 1 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 1 1 1 0 0 0 0 

และ

0 1 1 0 1 0 0 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 

ปริภูมิย่อย 7 มิติที่ได้จะมีปริภูมิผลหาร 3 มิติ เมื่อละเว้นอ็อกทาด 2 อันหลัง

มีคำรหัสอีก 4 คำที่มีโครงสร้างคล้ายกัน ซึ่งรวมกันเป็นพื้นฐาน 12 คำรหัสสำหรับการแสดงตัวอักษร W นี้

W มีปริภูมิย่อยที่มีมิติ 4 ซึ่งสมมาตรภายใต้ PSL(2,7) x S ₃ซึ่งครอบคลุมโดย N และ 3 โดเดคาดที่ประกอบด้วยเซตย่อย {0,3,5,6}, {0,1,4,6} และ {0,1,2,5}

การแก้ไขข้อผิดพลาดมีความสำคัญต่อการส่งข้อมูลในยาน อวกาศ วอยเอเจอร์ 1 และ 2 โดยเฉพาะอย่างยิ่งเนื่องจากข้อจำกัดด้านหน่วยความจำกำหนดให้ต้องถ่ายโอนข้อมูลแทบจะในทันทีโดยไม่ให้โอกาสครั้งที่สอง ภาพถ่ายสีหลายร้อยภาพของดาวพฤหัสบดีและดาวเสาร์ในการบินผ่านในปี 1979, 1980 และ 1981 จะถูกส่งภายในแบนด์วิดท์การสื่อสารที่จำกัด การส่งภาพสีต้องใช้ข้อมูลมากกว่าภาพขาวดำถึงสามเท่า ดังนั้นรหัสReed–Muller ที่แก้ไขข้อผิดพลาด 7 ข้อ ซึ่งเคยใช้ในการส่งภาพขาวดำของ Mariner จึงถูกแทนที่ด้วยรหัส Golay (24,12,8) ที่มีอัตราข้อมูลสูงกว่ามาก^{[ 9 ]}

มาตรฐานทางทหารอเมริกัน MIL -STD-188สำหรับการสร้างลิงก์อัตโนมัติใน ระบบวิทยุ ความถี่สูงระบุการใช้รหัส Golay แบบขยาย (24,12) สำหรับการแก้ไขข้อผิดพลาดล่วงหน้า^{[ 10 ] [ 11 ]}

ในการสื่อสารทางวิทยุแบบสองทาง ระบบ ตัดเสียงรบกวนแบบเข้ารหัสดิจิทัล (DCS, CDCSS)ใช้รหัสคำ Golay 23 บิต (23,12) ซึ่งมีความสามารถในการตรวจจับและแก้ไขข้อผิดพลาดที่มี 3 บิตหรือน้อยกว่า

• ตาข่ายปลิง
• รหัสเชิงเส้น