삼진 골레 부호

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

군론컴퓨터 과학에서, 삼진 골레 부호(三進Golay符號, 영어: ternary Golay code 터너리 골레이 코드[*])는 마티외 군자기 동형군으로 갖는 삼진 선형 부호이다.

정의[편집]

표준형 생성 행렬

으로 정의되는, 속의 삼진 선형 부호

(확장) 삼진 골레 부호(영어: (extended) ternary Golay code) 라고 한다.

확장 삼진 골레 부호에서, 임의의 한 성분을 삭제하면, 완전 삼진 골레 부호(영어: perfect ternary Golay code) 를 얻는다.

성질[편집]

확장 삼진 골레 부호는 [12,6,6]3-선형 부호이다. 즉,

  • 만약 각 블록마다 3개 이하의 오류가 발생한다고 가정하면, 모든 오류를 교정할 수 있다.
  • 만약 각 블록마다 5개 이하의 오류가 발생한다고 가정하면, 모든 오류를 발견할 수 있다.

완전 삼진 골레 부호는 [11,6,5]3-선형 부호이며, 완전 블록 부호이다. 즉,

  • 만약 각 블록마다 2개 이하의 오류가 발생한다고 가정하면, 모든 오류를 교정할 수 있다.
  • 만약 각 블록마다 4개 이하의 오류가 발생한다고 가정하면, 모든 오류를 발견할 수 있다.
  • 해밍 상계를 포화시킨다.

부호어[편집]

확장 삼진 골레 부호는 개의 부호어를 가지며, 그 부호어의 해밍 무게의 원소이다. 각 해밍 무게를 갖는 부호어의 수는 다음과 같다. (OEIS의 수열 A105683)

확장 삼진 골레 부호의 부호어
해밍 무게 부호어의 수 부호어에서 값이 +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인 성분은 개이며, 값이 1인 성분은 1개 또는 5개 또는 7개 또는 11개이며, 값이 2인 성분은 개 또는 개 또는 개 또는 개이다.

마찬가지로, 완전 삼진 골레 부호는 개의 부호어를 가지며, 그 부호어의 해밍 무게의 원소이다. 각 해밍 무게를 갖는 부호어의 수는 다음과 같다. (OEIS의 수열 A105684)

완전 삼진 골레 부호의 부호어
해밍 무게 부호어의 수 부호어에서 값이 +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

대칭[편집]

확장 삼진 골레 부호의 자기 동형군

마티외 군 의 2차 중심 확대이다. 즉, 다음과 같은 짧은 완전열이 존재한다.

또한 이다.

완전 삼진 골레 부호의 자기 동형군은 다음과 같은 마티외 군이다.

역사[편집]

삼진 골레 부호는 이미 1947년에 핀란드의 축구 애호가 유나히 비르타칼리오(핀란드어: Junahi Virtakallio, 필명 핀란드어: Jukka 유카[*])가 토토칼초를 짜기 위하여 한 토토칼초 잡지 《베이카야》(핀란드어: Veikkaaja)에 기고한 글에 수록되었다.[1][2]:401, §15.3 [3]:25 이 글에서 비르타칼리오는 다음과 같이 적었다.

한동안 토토칼초 상금이 낮았던 시기에 나는 다음과 같은 729개의 열[=부호어]로 구성된 도박 체계를 개발하였습니다. 당시에는 상금이 너무 낮아서, 이를 매주 사용하지 않으면 필요한 투자금을 수복할 수 없었기 때문에, 이 체계는 출판되지 못했으며 다른 체계들과 함께 잊혀져 있었습니다. 지난 겨울에 토토칼초 상금이 절정에 달했을 때, 나는 본 잡지[《베이카야》]의 편집부와 이에 대하여 얘기를 나눴지만, 729개의 열이 너무 많아서 출판되지 못했습니다. 이제서야 나는 공간을 절약하는 방법을 발견하였으며, 이 체계가 도박사들의 도박 가능성(그리고 희망컨대 도박사들의 지갑)을 더 풍족하게 하기를 바랍니다.
The following system with 729 columns [=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.

 
[2]:401–402[3]:25

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

참고 문헌[편집]

  1. Jukka (1947년 8월 1일). 《Veikkaaja》 (핀란드어).  |제목=이(가) 없거나 비었음 (도움말)
  2. Cohen, G.; Honkala, I.; Litsyn, S.; Lobstein, A. (1997년 4월 14일). 《Covering codes》. North-Holland Mathematical Library (영어) 54. North-Holland. ISBN 978-044482511-7. doi:10.1016/S0924-6509(13)70001-1. 
  3. Barg, Alexander (1993). “At the dawn of the theory of codes” (PDF). 《The Mathematical Intelligencer》 (영어) 15 (1): 20–26. ISSN 0343-6993. MR 1199273. doi:10.1007/BF03025254. 
  4. Golay, Marcel Jules Édouard (1949년 6월). “Correspondence. Notes on digital coding”. 《Proceedings of the Institute of Radio Engineers》 (영어) 37 (6): 657–657. doi:10.1109/JRPROC.1949.233620. 

외부 링크[편집]