바이너리 골레이 코드

확장 바이너리 골레이 코드
제너레이터 매트릭스
이름을 따서 명명됨	마르셀 J. E. 골레이
분류
유형	선형블록코드
블록 길이	24
메시지 길이	12
등급	12/24 = 0.5
거리	8
알파벳 크기	2
표기법	${\displaystyle [}$ ${\displaystyle 24,}$ ${\displaystyle 12,}$ ${\displaystyle 8}$ ${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$}} -code$$
v t

퍼펙트 바이너리 골레이 코드
이름을 따서 명명됨	마르셀 J. E. 골레이
분류
유형	선형블록코드
블록 길이	23
메시지 길이	12
등급	12/23 ~ 0.522
거리	7
알파벳 크기	2
표기법	${\displaystyle [}$ ${\displaystyle 23,}$ ${\displaystyle 12,}$ ${\displaystyle 7}$ ${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$}} -code$$
v t

수학과 전자공학에서 바이너리 골레이 코드는 디지털 통신에 사용되는 선형 오류 수정 코드의 일종이다. 2진법 골레이 코드는 3진법 골레이 코드와 함께 수학에서 유한한 산발적 집단 이론과 특히 깊고 흥미로운 연관성을 가지고 있다.^[1] 이 코드들은 1949년 그것들을 소개하는 논문이^[2] 부름받은 마르셀 J. E. Golay를 기리기 위해 코드 이론에서 "최고의 단일 출판 페이지"인 E. R. Berlekamp에 의해 명명되었다.^[3]

골레이 코드에는 밀접한 관련이 있는 두 개의 이진 코드가 있다. 확장 바이너리 골레이 코드 G₂₄(유한집단 이론에서 '골레이 코드'라고 부르기도 한다)는 어떤 3비트 오류라도 수정하거나 7비트 오류를 검출할 수 있도록 12비트의 데이터를 24비트 단어로 암호화한다. 다른 하나는 완벽한 바이너리 골레이 코드 G는₂₃ 길이 23의 코드 워드를 가지고 있으며 하나의 좌표 위치를 삭제하여 확장된 바이너리 골레이 코드에서 얻는다(반대로 확장된 바이너리 골레이 코드는 패리티 비트를 추가하여 완벽한 바이너리 골레이 코드에서 얻음). 표준 코딩 표기법에서 코드는 각각 코드의 길이, 코드의 치수 및 두 코드 사이의 최소 해밍 거리에 해당하는 파라미터[24, 12, 8]와 [23, 12, 7]를 가진다.

수학적 정의

수학적 측면에서 확장된 2진수 골레이₂₄ 코드 G는 공간 V²⁴
₂ = 24비트 단어의 F의 12차원 선형 아공간 W로 구성되며, W의 두 개의 구별되는 요소가 적어도 8개의 좌표에서 차이가 난다. W는 벡터 공간이기 때문에 선형 코드라고 불린다. 전체적으로 W는 4096 = 2개의¹² 원소로 구성된다.

• W의 요소들을 코드 워드라고 부른다. 또한 24개 요소 집합의 하위 집합으로 설명될 수 있으며, 여기서 추가는 하위 집합의 대칭적 차이를 취하는 것으로 정의된다.
• 확장 바이너리 골레이 코드에서 모든 코드 워드는 해밍 가중치가 0, 8, 12, 16 또는 24이다. 무게 8의 코드 워드는 옥타드, 무게 12의 코드 워드는 도데카드라고 불린다.
• 코드 G의₂₄ 8진수는 S(5,8,24) Steiner 시스템의 요소들이다. 759 = 3 × 11 × 23 옥타드와 그 보완 759가 있다. 이어 2576 = 2⁴ × 7 × 23 도데카드가 있다.
• 두 옥타드는 이진 벡터 표현에서 0, 2 또는 4 좌표로 교차(공통 1개 포함)한다(이들은 부분 집합 표현에서 가능한 교차점 크기임). 옥타드와 도데카드는 2, 4, 6좌표에서 교차한다.
• 좌표를 다시 샘플링할 때까지 W는 독특하다.

바이너리 골레이 코드, G는₂₃ 완벽한 코드다. 즉, 코드 단어 주위에 있는 반경 3의 구들은 벡터 공간의 구획을 형성한다. G는₂₃ 공간 F의²³
₂ 12차원 아공간이다.

완벽한¹⁰ 바이너리 골레이 코드 G의₂₃ 오토모르피즘 그룹은 마티유 그룹 M ${\displaystyle {23}_{}}$ ${\$ 확장 바이너리 골레이 코드의 오토모르피즘 그룹은 2 × 3 × 5³ × 7 × 11 × 23의 마티유 그룹 $M{\displaystyle {}_{}}$ ${\displaystyle {24}_{}}$ ${\$이다. ${\displaystyle M_{}}$ ${\displaystyle {24}_{}}$ ${\$은(는) 옥타드와 도데카드에 전이된다. 다른 마티외 그룹은 W의 하나 또는 여러 요소의 안정제로 발생한다.

시공

• 사전 코드: 벡터를 V 사전순으로 정렬하십시오(즉, 벡터를 부호 없는 24비트 이진 정수로 해석하고 일반적인 순서를 취함). w₀ = 0으로 시작하여 w가_n 최소 8좌표에서 이전 원소의 모든 선형 조합과 다른 최소 정수라는 규칙으로 w₁, w₂, w, ..., w를₁₂ 정의한다. 그러면 W는 w₁, ..., w의₁₂ 범위로 정의할 수 있다.
• 마티외 그룹: 1938년 Witt는 확장된 바이너리 골레이 코드를 구성하는 데 사용될 수 있는 가장 큰 마티외 그룹의 구성을 발표했다.^[4]
• 2차 잔류물 코드: 2차 비잔차(mod 23)의 N 집합을 고려한다. 이것은 주기 그룹 Z/23Z의 11-element subset이다. 이 부분 집합의 번역 t+N을 고려하십시오. 요소 ∞을 추가하여 각 요소를 12-element set S로_t 변환한다. 그런 다음 V의 기본 요소에 0, 1, 2, ..., 22, ∞, W를 모든 기본 벡터로 구성된 단어와 함께 S의_t 범위로 정의할 수 있다. (완벽한 코드는 leaving을 생략하여 얻음).
• 순환 코드로: 완벽한 G₂₃ 코드는 이진 필드 GF(2)를$$ 통해 x ${\displaystyle {23}^{}}$- ${\displaystyle 1}$ ${\displaystyle x^{23}-1}$의 인자화를 통해 구성할 수 있다.

${\displaystyle x^{23}-1=(x-1)(x^{11}+x^{9)}}+x^{7}+x^{6}+x^{5}+x^{5}+x+1)(x^{11}+x^{10}+x^{6}+x^{5}+x^{4}+x^{2}+1)}$

$({\displaystyle {\mathrm{x11}}^{}}$+ ${\displaystyle {}^{}}$ ${\displaystyle {10}^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle {6\mathrm{}}^{}}$+ x ${\displaystyle {5\mathrm{}}^{}}$+ ${\displaystyle {x\mathrm{}}^{}}$ ${\displaystyle {}^{}}$+ ${\displaystyle 2{}^{}}$+ 1${\displaystyle }$) ${\$에 의해 생성된 코드로서$,$^[5] 코드 생성에는 11개의 불가요인자를 사용할 수 있다.^[6]

• 투린이 1967년에 건설한 "이항 골레이 코드의 단순 건설"은 길이 8의 해밍 코드에서 시작하여 2차 잔류물 모드의 23을 사용하지 않는다.^[7]
• Steiner System S(5,8,24)로부터, 24세트의 759 서브셋으로 구성된다. 각 서브셋의 지원을 길이 24의 0-1 코드 워드(해밍-무게 8)로 해석하면, 이것들은 이진 골레이 코드의 "옥타드"이다. 전체 골레이 코드는 하위 집합의 대칭적 차이, 즉 이진 덧셈을 반복해서 취함으로써 얻을 수 있다. Steiner 시스템을 다시 기록할 수 있는 더 쉬운 방법. 옥타드는 R. T. 커티스의 미라클 옥타드 제너레이터로$,$ 두 개의 4세트로 된 8세트의 35개 파티션과 $4평면$으로 된$$ 유한 $벡터$ 공간$F{\displaystyle {\mathbb{}}_{}^{}}$ $4$의 35개 파티션 사이에 $특정$한 1:1 대응성을 사용한다.^[8] 오늘날에는 4×6의 사각 셀 배열을 사용하는 콘웨이의 육각형의 콤팩트한 접근법이 종종 사용된다.
• 모굴의 수학 게임에서 승자: 모굴에서 승자는 24개의 동전으로 이루어진 줄이다. 각 턴은 동전 1개에서 7개까지 플립하는 것으로 구성되어 있으며, 이렇게 플립된 동전의 가장 왼쪽이 머리에서 꼬리까지 가게 된다. 패소 직위는 법적 움직임이 없는 사람들이다. 헤드가 1로, 꼬리가 0으로 해석될 경우 확장된 바이너리 골레이 코드에서 코드 워드로 이동하면 승리를 강제할 수 있다.
• 2진수 골레이 코드의 발전기 행렬은 I A이고, 여기서 나는 12×12 아이덴티티 행렬이며, A는 이코사헤드론의 인접 행렬의 보완이다.

편리한 표현

4열, 6열로 구성된 배열의 좌표를 가진 '기적의 옥타드 생성기' 형식을 사용하면 편리하다. 추가는 대칭적인 차이를 가져가는 것이다. 6개의 열은 모두 같은 패리티를 가지며, 이는 상위 행과 동일하다.

6개의 기둥을 3쌍의 인접한 기둥으로 분할하면 3중주가 된다. 이것은 3옥타드 세트로 분할된 것이다. M의₂₄ 3인조 부분군의 투영 특수 선형군 PSL(2,7) x S는₃ 기초 생성을 위해 유용하다. 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개. 이 6개의 코드 단어들의 합 N은 모두 1의 것으로 구성된다. 코드 워드에 N을 추가하면 그 보완점이 생성된다.

그리이스(p.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차원 아공간은 후자의 2옥타드를 무시했을 때 3차원 몫의 공간을 가진다.

W의 이 표현에 대한 12개의 코드 워드의 기초를 완성하는 유사한 구조의 다른 4개의 코드 워드가 있다.

W는 PSL(2,7) x S에₃ 따라 대칭인 차원 4의 하위 공간을 가지며, 하위 집합 {0,3,5,6}, {0,1,4,6}, {0,1,2,5}로 구성된 3개의 도데카드에 의해 확장된다.

골레이 코드의 실용화

NASA 심우주 임무

Voyager 1, 2 우주선에서 데이터 전송에 오류 보정은 특히 메모리 제약으로 인해 데이터가 사실상 즉시 오프로드되어 두 번째 기회가 없기 때문에 필수적이었다. 1979년, 1980년, 1981년대의 목성과 토성의 수백 장의 컬러 사진이 제한된 통신 대역폭 내에서 전송될 것이다. 컬러 영상 전송은 흑백 영상보다 3배 많은 양의 데이터가 필요했기 때문에 흑백 마리너 영상을 전송하는 데 사용됐던 리드-뮬러 코드를 수정하는 7오류가 훨씬 높은 데이터 전송률 골레이(24,12,8) 코드로 대체됐다.^[9]

무선 통신

MIL-STD-188 고주파 무선 시스템에서 자동 링크 설정을 위한 미군 표준은 전방 오류 수정을 위해 확장(24,12) 골레이 코드를 사용하도록 명시한다.^[10][11]

참고 항목

• 리치 격자

참조

원천

• Conway, John Horton; Sloane, Neil J. A. (1999), Sphere Packings, Lattices and Groups, Grundlehren der Mathematischen Wissenschaften, vol. 290 (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-0-387-98585-5, MR 0920369
• Curtis, R. T. (1976). "A new combinatorial approach to M₂₄". Mathematical Proceedings of the Cambridge Philosophical Society. 79: 25–42. doi:10.1017/S0305004100052075.
• Greferath, Marcus (2003). "Golay Codes". In Proakis, John G. (ed.). Encyclopedia of Telecommunications. Wiley. doi:10.1002/0471219282.eot371. ISBN 0471219282.
• Griess, Robert L. (1998). Twelve Sporadic Groups. Springer. p. 167. ISBN 978-3-540-62778-4.
• Pless, Vera (1998), Introduction to the Theory of Error-Correcting Codes (3rd ed.), John Wiley & Sons, ISBN 978-0-471-19047-9
• Roman, Steven (1996), Coding and Information Theory, Graduate Texts in Mathematics #134, Springer-Verlag, ISBN 0-387-97812-7
• Thompson, Thomas M. (1983). From Error Correcting Codes through Sphere Packings to Simple Groups. Carus Mathematical Monographs. Vol. 21. Mathematical Association of America. ISBN 978-0-88385-023-7.
• Turyn, Richard J.; et al. (1967). Research to Develop the Algebraic Theory of Codes (Section VI) (PDF) (Report). Air Force Cambridge Research Laboratories. Archived from the original (PDF) on October 30, 2018.