삼진 골레 부호
군론과 컴퓨터 과학에서 삼진 골레 부호(三進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개의 열이 너무 많아서 출판되지 못했습니다. 이제서야 나는 공간을 절약하는 방법을 발견하였으며, 이 체계가 도박사들의 도박 가능성(그리고 희망컨대 도박사들의 지갑)을 더 풍족하게 하기를 바랍니다. |
” |
이후 스위스의 수학자 마르셀 쥘 에두아르 골레(프랑스어: Marcel Jules Édouard Golay, 1902~1989)가 1949년에 1쪽도 채 되지 않는 “논문”에서 이진 골레 부호와 함께 삼진 골레 부호를 재발견하였다.[4]
같이 보기
[편집]각주
[편집]- ↑ Jukka (1947년 8월 1일). 《Veikkaaja》 (핀란드어).
|제목=
이(가) 없거나 비었음 (도움말) - ↑ 가 나 Cohen, G.; Honkala, I.; Litsyn, S.; Lobstein, A. (1997년 4월 14일). 《Covering codes》. North-Holland Mathematical Library (영어) 54. North-Holland. doi:10.1016/S0924-6509(13)70001-1. ISBN 978-044482511-7. 2013년 6월 24일에 원본 문서에서 보존된 문서. 2017년 5월 19일에 확인함.
- ↑ 가 나 Barg, Alexander (1993). “At the dawn of the theory of codes” (PDF). 《The Mathematical Intelligencer》 (영어) 15 (1): 20–26. doi:10.1007/BF03025254. ISSN 0343-6993. MR 1199273.[깨진 링크(과거 내용 찾기)]
- ↑ 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.
외부 링크
[편집]- “Golay code”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4.
- Pegg, Ed, Jr. “Golay code”. 《Wolfram MathWorld》 (영어). Wolfram Research.