이진 골레 부호

틀:위키데이터 속성 추적 군론과 컴퓨터 과학에서 이진 골레 부호(二進Golay符號, 틀:Llang)는 마티외 군을 자기 동형군으로 갖는 이진 선형 부호이다. 매우 높은 최소 거리를 가져, 널리 응용된다.

정의

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

$w_i=\min \{v\in {𝔽}_2^{24}:{\mathrm{d}}_{\mathrm{H}}(v,c)\ge 8\mathrm{\forall }c\in {\mathrm{Span}}_{{𝔽}_2}\{w_1,\dots ,w_{i-1}\}\}(1\le i\le 12)$

여기서

• ${\mathrm{d}}_{\mathrm{H}}:{𝔽}_2^{24}\times {𝔽}_2^{24}\to \{0,1,\dots ,24\}$는 해밍 거리이다.
• $\min$은 사전식 순서에서의 최소 원소이다.
• ${\mathrm{Span}}_{{𝔽}_2}\varnothing =\{(0,0,\dots ,0)\}$

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

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

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

$G_{24}={\mathrm{Span}}_{{𝔽}_2}\{w_1,w_2,\dots ,w_{12}\}⊊{𝔽}_2^{24}$

을 (확장) 이진 골레 부호(擴張二進Golay符號, 틀:Llang)라고 한다.

24개의 비트 가운데, 아무 한 비트를 삭제하면, 완전 골레 부호(完全Golay符號, 틀:Llang) $G_{23}⊊{𝔽}_2^{23}$를 얻는다.

성질

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

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

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

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

이다.

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

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

부호어

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

해밍 무게	수	안정자군	안정자군의 크기	용어	비고
0	1	대칭군 $\mathrm{Sym}(24)$	24!	영벡터
8	759=3×11×23	$\mathrm{IGL}(4;{𝔽}_2)\cong {𝔽}_2^4⋊\mathrm{GL}(4;{𝔽}_2)$ ($\mathrm{GL}(4;{𝔽}_2)\cong \mathrm{Alt}(8)$ 교대군)	32560	옥타드(틀:Llang)
12	2576=23×3×7×23	마티외 군 $M_{12}$	95040	도데카드(틀:Llang)	항상 두 옥타드의 합
16	759=3×11×23	$\mathrm{IGL}(4;{𝔽}_2)$	32560	헥사데카드(틀:Llang)	옥타드의 비트 여원
24	1	$\mathrm{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 {𝔽}_2^{24}$의 각 옥타드는 집합 $\{1,2,\dots ,24\}$의, 크기 8의 부분 집합으로 여길 수 있다. 이에 따라, 확장 이진 골레 부호의 옥타드의 집합은 (5,8,24)-슈타이너 계를 이루며, 이를 비트 설계(Witt設計, 틀:Llang)라고 불린다.

도데카드

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

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

이다.

대칭

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

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

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

여기서

• $M_{24}$와 $M_{23}$은 각각 마티외 군이다.
• $\mathrm{Sym}(n)$은 $n$차 대칭군이다.
• 순열 $\sigma \in \mathrm{Sym}(n)$의 ${𝔽}_2^n$ 위의 작용은 $\sigma \cdot (s_0,s_1,\dots ,s_{n-1})=(\sigma (s_0),\sigma (s_1),\dots ,\sigma (s_{n-1}))$이다.

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

생성 행렬

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

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

역사

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

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

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

같이 보기

• 리치 격자
• 선형 부호

외부 링크

• 틀:Eom
• 틀:매스월드
• 틀:Nlab
• 틀:수학노트
• 틀:수학노트
• 틀:웹 인용
• 틀:웹 인용