이진 골레 부호

군론과 컴퓨터 과학에서 **이진 골레 부호**(二進Golay符號, 바이너리 골레이 코드)는 마티외 군을 자기 동형군으로 갖는 이진 선형 부호이다.언어=enurl-status=dead 매우 높은 최소 거리를 가져, 널리 응용된다.
# 정의
유한체 \mathbb F_2 위의 24차원 벡터 공간 \mathbb F_2^{24}의 원소를 사전식 순서로 배열하자. 즉, 0에서 224−1까지의 자연수들의 이진법 표기로 여기자. 이제, 다음과 같은 벡터열을 재귀적으로 정의한다. :w_i=\min\left\\{v\in\mathbb F_2^{24}\colon\operatorname{d_H}(v,c)\ge8\forall c\in\operatorname{Span}_{\mathbb F_2}\\{w_1,\dotsc,w_{i-1}\\}\right\\}\qquad(1\le i\le12) 여기서 * \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)\\} 이렇게 얻는 수열은 (벡터를 이진법 표기 자연수로 여겼을 때) 다음과 같다. 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]2-선형 부호이다. 즉, * 각 블록에 4개 이하의 오류가 존재한다고 가정할 때, 항상 오류를 교정할 수 있다. * 각 블록에 7개 이하의 오류가 존재한다고 가정할 때, 항상 오류의 존재를 발견할 수 있다. 또한, 확장 이진 골레 부호는 스스로의 쌍대 선형 부호이다. 즉, :G_{24}=G_{24}^\perp 이다. 완전 이진 골레 부호 G_{23}\subseteq\mathbb F_2^{23}는 [23,12,7]2-선형 부호이며, 완전 블록 부호이다. 즉, * 각 블록에 3개 이하의 오류가 존재한다고 가정할 때, 항상 오류를 교정할 수 있다. * 각 블록에 6개 이하의 오류가 존재한다고 가정할 때, 항상 오류의 존재를 발견할 수 있다. * 해밍 상계를 포화시킨다.
## 부호어
확장 이진 골레 부호의 부호어들의 종류는 다음과 같다. {| class=wikitable ! 해밍 무게 !! 수 !! 안정자군 !! 안정자군의 크기 !! 용어 !! 비고 |- | 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! || || 영벡터의 비트 여원 |} {| class=wikitable |+ 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개이다.언어=en38, 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_24\\}\cong M_{24} :\operatorname{Aut}(G_{23})=\\{\sigma\in\operatorname{Sym}(24)\colon \sigma\cdot G_{23}=G_23\\}\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년에 로버트 대니얼 카마이클이 최초로 발견하였으며,언어=en 에른스트 비트가 1938년에 마티외 군을 연구하던 도중 재발견하였다.언어=de 이후 스위스의 수학자 마르셀 쥘 에두아르 골레(Marcel Jules Édouard Golay, 1902~1989)가 1949년에 1쪽도 채 되지 않는 “논문”에서 이진 골레 부호를 (삼진 골레 부호와 함께) 도입하였다.언어=en 1979~1981년에 보이저 1호와 보이저 2호는 목성과 토성의 천연색 사진을 전송하기 위하여 확장 이진 골레 부호를 사용하였다. (흑백 사진은 아다마르 부호를 사용하여 전송되었다.)