이진 골레 부호 문서 원본 보기

{{위키데이터 속성 추적}}
[[군론]]과 [[컴퓨터 과학]]에서 '''이진 골레 부호'''(二進Golay符號, {{llang|en|binary Golay code|바이너리 골레이 코드}})는 [[마티외 군]]을 [[자기 동형군]]으로 갖는 [[이진 선형 부호]]이다.<ref>{{서적 인용|성=Conway|이름=John Horton|저자링크=존 호턴 콘웨이|성2=Sloane|이름2=Neil J. A.|날짜=1999|제목=Sphere packings, lattices and groups|총서=Grundlehren der Mathematischen Wissenschaften|권=290|판=3|출판사=Springer-Verlag|isbn=978-1-4419-3134-4|doi=10.1007/978-1-4757-6568-7|mr=0920369|zbl=0915.52003|언어=en}}</ref><ref>{{서적 인용|성=Thompson|이름=Thomas M.|날짜=1983|제목=From error correcting codes through sphere packings to simple groups|총서=Carus Mathematical Monographs|권=21|출판사=Mathematical Association of America|isbn=978-0-88385-023-7|url=http://www.cambridge.org/us/academic/subjects/mathematics/discrete-mathematics-information-theory-and-coding/error-correcting-codes-through-sphere-packings-simple-groups|zbl=0545.94016|언어=en|확인날짜=2017-05-19|보존url=https://web.archive.org/web/20170208141322/http://www.cambridge.org/us/academic/subjects/mathematics/discrete-mathematics-information-theory-and-coding/error-correcting-codes-through-sphere-packings-simple-groups#|보존날짜=2017-02-08|url-status=dead}}</ref> 매우 높은 최소 거리를 가져, 널리 응용된다.

== 정의 ==
[[유한체]] <math>\mathbb F_2</math> 위의 24차원 [[벡터 공간]] <math>\mathbb F_2^{24}</math>의 원소를 [[사전식 순서]]로 배열하자. 즉, 0에서 2<sup>24</sup>−1까지의 [[자연수]]들의 [[이진법]] 표기로 여기자. 이제, 다음과 같은 벡터열을 재귀적으로 정의한다.
:<math>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)</math>
여기서
* <math>\operatorname{d_H}\colon\mathbb F_2^{24}\times\mathbb F_2^{24}\to\{0,1,\dotsc,24\}</math>는 [[해밍 거리]]이다.
* <math>\min</math>은 [[사전식 순서]]에서의 [[최소 원소]]이다.
* <math>\operatorname{Span}_{\mathbb F_2}\varnothing=\{(0,0,\dotsc,0)\}</math>
이렇게 얻는 수열은 (벡터를 [[이진법]] 표기 자연수로 여겼을 때) 다음과 같다. {{OEIS|A75941}}
:255, 3855, 13107, 21845, 38505, 197462, 329059, 591418, 1118584, 2167325, 4265038, 8460068

그렇다면, 이들을 [[기저 (선형대수학)|기저]]로 하는 12차원 부분 벡터 공간
:<math>G_{24}=\operatorname{Span}_{\mathbb F_2}\{w_1,w_2,\dotsc,w_{12}\}\subsetneq\mathbb F_2^{24}</math>
을 '''(확장) 이진 골레 부호'''(擴張二進Golay符號, {{llang|en|(extended) binary Golay code}})라고 한다.

24개의 비트 가운데, 아무 한 비트를 삭제하면, '''완전 골레 부호'''(完全Golay符號, {{llang|en|perfect Golay code}}) <math>G_{23}\subsetneq\mathbb F_2^{23}</math>를 얻는다.

== 성질 ==
확장 이진 골레 부호 <math>G_{24}\subseteq\mathbb F_2^{24}</math>는 [24,12,8]<sub>2</sub>-[[선형 부호]]이다. 즉,
* 각 블록에 4개 이하의 오류가 존재한다고 가정할 때, 항상 오류를 교정할 수 있다.
* 각 블록에 7개 이하의 오류가 존재한다고 가정할 때, 항상 오류의 존재를 발견할 수 있다.
또한, 확장 이진 골레 부호는 스스로의 쌍대 선형 부호이다. 즉,
:<math>G_{24}=G_{24}^\perp</math>
이다.

완전 이진 골레 부호 <math>G_{23}\subseteq\mathbb F_2^{23}</math>는 [23,12,7]<sub>2</sub>-[[선형 부호]]이며, [[완전 블록 부호]]이다. 즉,
* 각 블록에 3개 이하의 오류가 존재한다고 가정할 때, 항상 오류를 교정할 수 있다.
* 각 블록에 6개 이하의 오류가 존재한다고 가정할 때, 항상 오류의 존재를 발견할 수 있다.
* [[해밍 상계]]를 포화시킨다.

=== 부호어 ===
확장 이진 골레 부호의 부호어들의 종류는 다음과 같다.
{| class=wikitable
! [[해밍 무게]] !! 수 !! [[안정자군]] !! [[안정자군]]의 크기 !! 용어 !! 비고
|-
| 0 || 1 || [[대칭군 (군론)|대칭군]] <math>\operatorname{Sym}(24)</math> || 24! || 영벡터 ||
|-
| 8 || 759=3×11×23 || <math>\operatorname{IGL}(4;\mathbb F_2)\cong\mathbb F_2^4\rtimes\operatorname{GL}(4;\mathbb F_2)</math> (<math>\operatorname{GL}(4;\mathbb F_2)\cong\operatorname{Alt}(8)</math> [[교대군]]) || 32560 || 옥타드({{llang|en|octad}}) ||
|-
| 12 || 2576=2<sup>3</sup>×3×7×23 || [[마티외 군]] <math>M_{12}</math>|| 95040 || 도데카드({{llang|en|dodecad}}) || 항상 두 옥타드의 합
|-
| 16 || 759=3×11×23 || <math>\operatorname{IGL}(4;\mathbb F_2)</math>|| 32560 || 헥사데카드({{llang|en|hexadecad}}) || 옥타드의 비트 여원
|-
| 24 || 1 || <math>\operatorname{Sym}(24)</math> || 24! || || 영벡터의 비트 여원
|}

{| class=wikitable style="text-align: center"
|+ <math>G_{24}</math>에서, 부호어가 교차하는 비트의 수
! !! 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의 수)이다.

==== 옥타드 ====
확장 이진 골레 부호 <math>G_{24}\subseteq\mathbb F_2^{24}</math>의 각 옥타드는 집합 <math>\{1,2,\dotsc,24\}</math>의, 크기 8의 [[부분 집합]]으로 여길 수 있다. 이에 따라, 확장 이진 골레 부호의 옥타드의 집합은 (5,8,24)-[[슈타이너 계]]를 이루며, 이를 '''비트 설계'''(Witt設計, {{llang|en|Witt design}})라고 불린다.

==== 도데카드 ====
각 옥타드에 대하여, 2개의 비트가 교차하는 옥타드의 수는 448개이다. 모든 도데카드는 (서로 2개의 비트가 교차하는) 두 옥타드의 합으로 나타내어지며, 이러한 표현의 수는 (두 옥타드의 순서를 무시하면) 66개이다.<ref>{{서적 인용|제목=Twelve sporadic groups|이름=Robert L. Jr.|성=Griess|날짜=1998|doi= 10.1007/978-3-662-03516-0|isbn= 978-3-642-08305-1|출판사=Springer-Verlag|총서= Springer Monographs in Mathematics |issn=1439-7382|언어=en}}</ref>{{rp|38, Theorem 5.8}} 즉, 도데카드의 수는
:<math>\frac{759\times 448}{2\times 66} = 2576</math>
이다.

=== 대칭 ===
확장 이진 골레 부호와 완전 이진 골레 부호의 [[자기 동형군]]은 각각 다음과 같다.
:<math>\operatorname{Aut}(G_{24})=\{\sigma\in\operatorname{Sym}(24)\colon \sigma\cdot G_{24}=G_24\}\cong M_{24}</math>
:<math>\operatorname{Aut}(G_{23})=\{\sigma\in\operatorname{Sym}(24)\colon \sigma\cdot G_{23}=G_23\}\cong M_{23}</math>
여기서
* <math>M_{24}</math>와 <math>M_{23}</math>은 각각 [[마티외 군]]이다.
* <math>\operatorname{Sym}(n)</math>은 <math>n</math>차 [[대칭군 (군론)|대칭군]]이다.
* [[순열]] <math>\sigma\in\operatorname{Sym}(n)</math>의 <math>\mathbb F_2^n</math> 위의 [[군의 작용|작용]]은 <math>\sigma\cdot(s_0,s_1,\dotsc,s_{n-1})=(\sigma(s_0),\sigma(s_1),\dotsc,\sigma(s_{n-1}))</math>이다.

<math>M_{24}</math>의, 옥타드 집합 위의 [[군의 작용|작용]]은 [[추이적 작용]]이다. 마찬가지로, <math>M_{24}</math>의, 도데카드 집합 위의 [[군의 작용|작용]] 역시 [[추이적 작용]]이다.

=== 생성 행렬 ===
이진 골레 부호의 표준형 생성 행렬 <math>G\in\operatorname{Mat}(24,12;\mathbb F_2)</math>의 [[전치 행렬]]은 다음과 같다.
:[[파일:BinaryGolayCode.svg|250px]]
여기서 <span style="color: red">⊙</span>은 1을, <span style="color: blue">○</span>은 0을 뜻한다.

== 역사 ==
이진 골레 부호의 옥타드의 집합은 비트 설계는 1931년에 [[로버트 대니얼 카마이클]]이 최초로 발견하였으며,<ref>{{저널 인용|last=Carmichael|first=Robert Daniel|저자링크=로버트 대니얼 카마이클|title=Tactical configurations of rank two|journal=American Journal of Mathematics|volume=53|pages=217–240|year=1931|jstor=10.2307/2370885|doi=10.2307/2370885|언어=en}}</ref> [[에른스트 비트]]가 1938년에 [[마티외 군]]을 연구하던 도중 재발견하였다.<ref>{{저널 인용|last=Witt|first=Ernst|authorlink=에른스트 비트|title=Die 5-Fach transitiven Gruppen von Mathieu|journal=Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg|volume=12|pages=256–264|날짜=1938|doi=10.1007/BF02948947|언어=de}}</ref>

이후 스위스의 수학자 마르셀 쥘 에두아르 골레({{llang|fr|Marcel Jules Édouard Golay}}, 1902~1989)가 1949년에 1쪽도 채 되지 않는 “논문”에서 이진 골레 부호를 ([[삼진 골레 부호]]와 함께) 도입하였다.<ref>{{저널 인용|성=Golay|이름=Marcel Jules Édouard|날짜=1949-06|제목=Correspondence. Notes on digital coding|저널=Proceedings of the Institute of Radio Engineers|권=37|호=6|쪽=657–657|doi=10.1109/JRPROC.1949.233620|언어=en}}</ref>

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

== 같이 보기 ==
* [[리치 격자]]
* [[선형 부호]]
== 각주 ==
{{각주}}

== 외부 링크 ==
* {{eom|title=Golay code}}
* {{매스월드|id=GolayCode|title=Golay code|이름= Ed, Jr.|성=Pegg}}
* {{nlab|id=binary Golay code|title=Binary Golay code}}
* {{수학노트|title=골레이 코드 (Golay code)}}
* {{수학노트|title=슈타이너 시스템 S(5, 8, 24)}}
* {{웹 인용|url=http://blogs.ams.org/visualinsight/2015/12/01/golay-code/|제목=Golay code|날짜=2015-12-01|웹사이트=Visual Insight|이름=John|성=Baez|출판사=American Mathematical Society|언어=en|확인날짜=2017-05-18|보존url=https://web.archive.org/web/20171201131520/https://blogs.ams.org/visualinsight/2015/12/01/golay-code/|보존날짜=2017-12-01|url-status=dead}}
* {{웹 인용|url=http://finitegeometry.org/sc/24/MOG.html|제목=The Miracle Octad Generator (MOG) of R. T. Curtis|이름=Steven H.|성=Cullinane|날짜=2005-11-30|언어=en}}

[[분류:부호 이론]]
[[분류:군론]]
[[분류:오류 검출 정정]]