이진 골레 부호

군론과 컴퓨터 과학에서 이진 골레 부호(二進Golay符號, 영어: binary Golay code 바이너리 골레이 코드^[*])는 마티외 군을 자기 동형군으로 갖는 이진 선형 부호이다. 매우 높은 최소 거리를 가져, 널리 응용된다.

정의

유한체 $\mathbb {F} _{2}$ 위의 24차원 벡터 공간 $\mathbb {F} _{2}^{24}$의 원소를 사전식 순서로 배열하자. 즉, 0에서 2²⁴−1까지의 자연수들의 이진법 표기로 여기자. 이제, 다음과 같은 벡터열을 재귀적으로 정의한다.

$w_{i}=\min \left\{v\in \mathbb {F} _{2}^{24}\colon \operatorname {d_{H}} (v,c)\geq 8\forall c\in \operatorname {Span} _{\mathbb {F} _{2}}\{w_{1},\dotsc ,w_{i-1}\}\right\}\qquad (1\leq i\leq 12)$

여기서

• $\operatorname {d_{H}} \colon \mathbb {F} _{2}^{24}\times \mathbb {F} _{2}^{24}\to \{0,1,\dotsc ,24\}$는 해밍 거리이다.
• $\min$은 사전식 순서에서의 최소 원소이다.
• $\operatorname {Span} _{\mathbb {F} _{2}}\varnothing =\{(0,0,\dotsc ,0)\}$

이렇게 얻는 수열은 (벡터를 이진법 표기 자연수로 여겼을 때) 다음과 같다. (OEIS의 수열 A75941)

255, 3855, 13107, 21845, 38505, 197462, 329059, 591418, 1118584, 2167325, 4265038, 8460068

그렇다면, 이들을 기저로 하는 12차원 부분 벡터 공간

$G_{24}=\operatorname {Span} _{\mathbb {F} _{2}}\{w_{1},w_{2},\dotsc ,w_{12}\}\subsetneq \mathbb {F} _{2}^{24}$

을 (확장) 이진 골레 부호(擴張二進Golay符號, 영어: (extended) binary Golay code)라고 한다.

24개의 비트 가운데, 아무 한 비트를 삭제하면, 완전 골레 부호(完全Golay符號, 영어: perfect Golay code) $G_{23}\subsetneq \mathbb {F} _{2}^{23}$를 얻는다.

성질

확장 이진 골레 부호 $G_{24}\subseteq \mathbb {F} _{2}^{24}$는 [24,12,8]₂-선형 부호이다. 즉,

• 각 블록에 4개 이하의 오류가 존재한다고 가정할 때, 항상 오류를 교정할 수 있다.
• 각 블록에 7개 이하의 오류가 존재한다고 가정할 때, 항상 오류의 존재를 발견할 수 있다.

또한, 확장 이진 골레 부호는 스스로의 쌍대 선형 부호이다. 즉,

$G_{24}=G_{24}^{\perp }$

이다.

완전 이진 골레 부호 $G_{23}\subseteq \mathbb {F} _{2}^{23}$는 [23,12,7]₂-선형 부호이며, 완전 블록 부호이다. 즉,

• 각 블록에 3개 이하의 오류가 존재한다고 가정할 때, 항상 오류를 교정할 수 있다.
• 각 블록에 6개 이하의 오류가 존재한다고 가정할 때, 항상 오류의 존재를 발견할 수 있다.
• 해밍 상계를 포화시킨다.

부호어

확장 이진 골레 부호의 부호어들의 종류는 다음과 같다.

해밍 무게	수	안정자군	안정자군의 크기	용어	비고
0	1	대칭군 $\operatorname {Sym} (24)$	24!	영벡터
8	759=3×11×23	$\operatorname {IGL} (4;\mathbb {F} _{2})\cong \mathbb {F} _{2}^{4}\rtimes \operatorname {GL} (4;\mathbb {F} _{2})$ ($\operatorname {GL} (4;\mathbb {F} _{2})\cong \operatorname {Alt} (8)$ 교대군)	32560	옥타드(영어: octad)
12	2576=23×3×7×23	마티외 군 $M_{12}$	95040	도데카드(영어: dodecad)	항상 두 옥타드의 합
16	759=3×11×23	$\operatorname {IGL} (4;\mathbb {F} _{2})$	32560	헥사데카드(영어: hexadecad)	옥타드의 비트 여원
24	1	$\operatorname {Sym} (24)$	24!		영벡터의 비트 여원

$G_{24}$에서, 부호어가 교차하는 비트의 수

	0	8	12	16	24
0	0	0	0	0	0
8		0, 2, 4, 8	2, 4, 6	0, 4, 6, 8	8
12			0, 4, 8, 12	6, 8, 10	12
16				8, 10, 12, 16	16
24					24

여기서, “교차하는 비트의 수”란 두 벡터의 AND를 취한 것의 해밍 무게(비트 1의 수)이다.

옥타드

확장 이진 골레 부호 $G_{24}\subseteq \mathbb {F} _{2}^{24}$의 각 옥타드는 집합 $\{1,2,\dotsc ,24\}$의, 크기 8의 부분 집합으로 여길 수 있다. 이에 따라, 확장 이진 골레 부호의 옥타드의 집합은 (5,8,24)-슈타이너 계를 이루며, 이를 비트 설계(Witt設計, 영어: Witt design)라고 불린다.

도데카드

각 옥타드에 대하여, 2개의 비트가 교차하는 옥타드의 수는 448개이다. 모든 도데카드는 (서로 2개의 비트가 교차하는) 두 옥타드의 합으로 나타내어지며, 이러한 표현의 수는 (두 옥타드의 순서를 무시하면) 66개이다.^{:38, Theorem 5.8} 즉, 도데카드의 수는

${\frac {759\times 448}{2\times 66}}=2576$

이다.

대칭

확장 이진 골레 부호와 완전 이진 골레 부호의 자기 동형군은 각각 다음과 같다.

$\operatorname {Aut} (G_{24})=\{\sigma \in \operatorname {Sym} (24)\colon \sigma \cdot G_{24}=G_{2}4\}\cong M_{24}$

$\operatorname {Aut} (G_{23})=\{\sigma \in \operatorname {Sym} (24)\colon \sigma \cdot G_{23}=G_{2}3\}\cong M_{23}$

여기서

• $M_{24}$와 $M_{23}$은 각각 마티외 군이다.
• $\operatorname {Sym} (n)$은 $n$차 대칭군이다.
• 순열 $\sigma \in \operatorname {Sym} (n)$의 $\mathbb {F} _{2}^{n}$ 위의 작용은 $\sigma \cdot (s_{0},s_{1},\dotsc ,s_{n-1})=(\sigma (s_{0}),\sigma (s_{1}),\dotsc ,\sigma (s_{n-1}))$이다.

$M_{24}$의, 옥타드 집합 위의 작용은 추이적 작용이다. 마찬가지로, $M_{24}$의, 도데카드 집합 위의 작용 역시 추이적 작용이다.

생성 행렬

이진 골레 부호의 표준형 생성 행렬 $G\in \operatorname {Mat} (24,12;\mathbb {F} _{2})$의 전치 행렬은 다음과 같다.

여기서 ⊙은 1을, ○은 0을 뜻한다.

역사

이진 골레 부호의 옥타드의 집합은 비트 설계는 1931년에 로버트 대니얼 카마이클이 최초로 발견하였으며, 에른스트 비트가 1938년에 마티외 군을 연구하던 도중 재발견하였다.

이후 스위스의 수학자 마르셀 쥘 에두아르 골레(프랑스어: Marcel Jules Édouard Golay, 1902~1989)가 1949년에 1쪽도 채 되지 않는 “논문”에서 이진 골레 부호를 (삼진 골레 부호와 함께) 도입하였다.

1979~1981년에 보이저 1호와 보이저 2호는 목성과 토성의 천연색 사진을 전송하기 위하여 확장 이진 골레 부호를 사용하였다. (흑백 사진은 아다마르 부호를 사용하여 전송되었다.)

외부 링크

• “Golay code”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Pegg, Ed, Jr. “Golay code”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• “Binary Golay code”. 《nLab》 (영어). 
• 이철희. “골레이 코드 (Golay code)”. 《수학노트》. 
• 이철희. “슈타이너 시스템 S(5, 8, 24)”. 《수학노트》. 
• Baez, John (2015년 12월 1일). “Golay code”. 《Visual Insight》 (영어). American Mathematical Society. 2017년 12월 1일에 원본 문서에서 보존된 문서. 2017년 5월 18일에 확인함. 
• Cullinane, Steven H. (2005년 11월 30일). “The Miracle Octad Generator (MOG) of R. T. Curtis” (영어).