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

{{위키데이터 속성 추적}}
[[군론]]과 [[컴퓨터 과학]]에서 '''삼진 골레 부호'''(三進Golay符號, {{llang|en|ternary Golay code|터너리 골레이 코드}})는 [[마티외 군]]을 [[자기 동형군]]으로 갖는 [[삼진 선형 부호]]이다.

== 정의 ==
표준형 생성 행렬
:<math>
G=\begin{pmatrix}
1&0&0&0&0&0\\
0&1&0&0&0&0\\
0&0&1&0&0&0\\
0&0&0&1&0&0\\
0&0&0&0&1&0\\
0&0&0&0&0&1\\
0&1&1&1&1&1\\
1&0&1&2&2&1\\
1&1&0&1&2&2\\
1&2&1&0&1&2\\
1&2&2&1&0&1\\
1&1&2&2&1&0
\end{pmatrix}</math>
으로 정의되는, <math>\mathbb F_3^{12}</math> 속의 [[삼진 선형 부호]]
:<math>\operatorname{im}G\subsetneq\mathbb F_3^{12}</math>
를 '''(확장) 삼진 골레 부호'''({{llang|en|(extended) ternary Golay code}}) <math>G_{12}</math>라고 한다.

확장 삼진 골레 부호에서, 임의의 한 성분을 삭제하면, '''완전 삼진 골레 부호'''({{llang|en|perfect ternary Golay code}}) <math>G_{11}</math>를 얻는다.

== 성질 ==
확장 삼진 골레 부호는 [12,6,6]<sub>3</sub>-선형 부호이다. 즉,
* 만약 각 블록마다 3개 이하의 오류가 발생한다고 가정하면, 모든 오류를 교정할 수 있다.
* 만약 각 블록마다 5개 이하의 오류가 발생한다고 가정하면, 모든 오류를 발견할 수 있다.

완전 삼진 골레 부호는 [11,6,5]<sub>3</sub>-선형 부호이며, [[완전 블록 부호]]이다. 즉,
* 만약 각 블록마다 2개 이하의 오류가 발생한다고 가정하면, 모든 오류를 교정할 수 있다.
* 만약 각 블록마다 4개 이하의 오류가 발생한다고 가정하면, 모든 오류를 발견할 수 있다.
* [[해밍 상계]]를 포화시킨다.

=== 부호어 ===
확장 삼진 골레 부호는 <math>3^6=729</math>개의 부호어를 가지며, 그 부호어의 [[해밍 무게]]는 <math>\{0, 6, 9, 12\}</math>의 원소이다. 각 [[해밍 무게]]를 갖는 부호어의 수는 다음과 같다. {{OEIS|A105683}}
:{| class=wikitable
|+ 확장 삼진 골레 부호의 부호어
|-
! [[해밍 무게]] !! 부호어의 수 !! 부호어에서 값이 +1인 성분의 수
|-
| 0 || 1 || 0
|-
| 6 || 264 || 0, 1, 2, 3, 4, 5, 6
|-
| 9 || 440 || 2, 3, 4, 5, 6, 7
|-
| 12 || 24 || 1, 5, 7, 11
|}
예를 들어, [[해밍 무게]]가 12인 부호어에서, 값이 0인 성분은 <math>12-12=0</math>개이며, 값이 1인 성분은 1개 또는 5개 또는 7개 또는 11개이며, 값이 2인 성분은 <math>12-1=11</math>개 또는 <math>12-5=7</math>개 또는 <Math>12-7=5</math>개 또는 <math>12-11=1</math>개이다.

마찬가지로, 완전 삼진 골레 부호는 <math>3^6=729</math>개의 부호어를 가지며, 그 부호어의 [[해밍 무게]]는 <math>\{0, 5, 6, 8, 9, 11\}</math>의 원소이다. 각 [[해밍 무게]]를 갖는 부호어의 수는 다음과 같다. {{OEIS|A105684}}
:{| class=wikitable
|+ 완전 삼진 골레 부호의 부호어
! [[해밍 무게]] !! 부호어의 수 !! 부호어에서 값이 +1인 성분의 수
|-
| 0 || 1 || 0
|-
| 5 || 132 || 0, 1, 2, 3, 4, 5
|-
| 6 || 132 || 0, 1, 2, 3, 4, 5, 6
|-
| 8 || 330 || 1, 2, 3, 4, 5, 6, 7
|-
| 9 || 110 || 2, 3, 4, 5, 6, 7
|-
| 11 || 24 || 1, 4, 5, 6, 7, 10
|}

=== 대칭 ===
확장 삼진 골레 부호의 [[자기 동형군]]
:<math>\operatorname{Aut}(G_{12})\le\operatorname{Sym}(12)</math>
은 [[마티외 군]] <math>M_{12}</math>의 2차 [[중심 확대]]이다. 즉, 다음과 같은 [[군 (수학)|군]] [[짧은 완전열]]이 존재한다.
:<math>1\to\operatorname{Cyc}(2)\hookrightarrow\operatorname{Aut}(G_{12})\twoheadrightarrow M_{12}\to1</math>
또한 <math>\operatorname{Cyc}(2)\le\operatorname Z(\operatorname{Aut}(G_{12}))</math>이다.

완전 삼진 골레 부호의 [[자기 동형군]]은 다음과 같은 [[마티외 군]]이다.
:<math>M_{11}\cong\operatorname{Aut}(G_{12})\le\operatorname{Sym}(11)</math>

== 역사 ==
삼진 골레 부호는 이미 1947년에 [[핀란드]]의 축구 애호가 유나히 비르타칼리오({{llang|fi|Junahi Virtakallio}}, 필명 {{llang|fi|Jukka|유카}})가 [[토토칼초]]를 짜기 위하여 한 [[토토칼초]] 잡지 《베이카야》({{llang|fi|Veikkaaja}})에 기고한 글에 수록되었다.<ref>{{저널 인용|저자=Jukka|날짜=1947-08-01|저널=Veikkaaja|언어=fi}}</ref><ref name="CHLL">{{서적 인용|제목=Covering codes|이름=G.|성=Cohen|이름2=I.|성2=Honkala|이름3=S.|성3=Litsyn|이름4=A.|성4=Lobstein|url=https://www.elsevier.com/books/covering-codes/cohen/978-0-444-82511-7|isbn=978-044482511-7|출판사=North-Holland|총서=North-Holland Mathematical Library|권=54|doi=10.1016/S0924-6509(13)70001-1|날짜=1997-04-14|언어=en|확인날짜=2017-05-19|보존url=https://web.archive.org/web/20130624191328/http://www.elsevier.com/books/covering-codes/cohen/978-0-444-82511-7|보존날짜=2013-06-24|url-status=dead}}</ref>{{rp|401, §15.3}}
<ref name="Barg">{{저널 인용 | last1=Barg | first1=Alexander | title=At the dawn of the theory of codes | doi=10.1007/BF03025254 | mr=1199273 | year=1993 | journal=The Mathematical Intelligencer | url=http://eng.umd.edu/~abarg/reprints/dawn.pdf | issn=0343-6993 | volume=15 | issue=1 | pages=20–26 | 언어=en }}{{깨진 링크|url=http://eng.umd.edu/~abarg/reprints/dawn.pdf }}</ref>{{rp|25}} 이 글에서 비르타칼리오는 다음과 같이 적었다.
{{인용문2|
한동안 [[토토칼초]] 상금이 낮았던 시기에 나는 다음과 같은 729개의 열[<nowiki>=</nowiki>부호어]로 구성된 도박 체계를 개발하였습니다. 당시에는 상금이 너무 낮아서, 이를 매주 사용하지 않으면 필요한 투자금을 수복할 수 없었기 때문에, 이 체계는 출판되지 못했으며 다른 체계들과 함께 잊혀져 있었습니다. 지난 겨울에 [[토토칼초]] 상금이 절정에 달했을 때, 나는 본 잡지[《베이카야》]의 편집부와 이에 대하여 얘기를 나눴지만, 729개의 열이 너무 많아서 출판되지 못했습니다. 이제서야 나는 공간을 절약하는 방법을 발견하였으며, 이 체계가 도박사들의 도박 가능성(그리고 희망컨대 도박사들의 지갑)을 더 풍족하게 하기를 바랍니다.<br>
{{lang|en|The following system with 729 columns [<nowiki>=</nowiki>codewords] was born in my brains during a period of depression in football pool prizes. Because the prizes were too small at that time to compensate the investments that would have been required if the system had been used week after week, the system remained unpublished and was forgotten among other systems. When during the last winter the football pool prizes reached a peak, there was talk with the editors [of the magazine ''Veikkaaja''] about publishing the system but fitting in the 729 columns in the magazine did not succeed. Only now, when I discovered a method of obtaining the required saving of space, this system gets a chance to enrich the possibilities of players and a chance to make some players rich, too.}}|<ref name="CHLL"/>{{rp|401–402}}<ref name="Barg"/>{{rp|25}}
}}

이후 스위스의 수학자 마르셀 쥘 에두아르 골레({{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>

== 같이 보기 ==
* [[이진 골레 부호]]
== 각주 ==
{{각주}}

== 외부 링크 ==
* {{eom|title=Golay code}}
* {{매스월드|id=GolayCode|title=Golay code|이름= Ed, Jr.|성=Pegg}}

[[분류:부호 이론]]
[[분류:군론]]
[[분류:유한체]]