이진 골레 부호

위키백과, 우리 모두의 백과사전.
둘러보기로 가기 검색하러 가기

군론컴퓨터 과학에서, 이진 골레 부호(二進Golay符號, 영어: binary Golay code 바이너리 골레이 코드[*])는 마티외 군자기 동형군으로 갖는 이진 선형 부호이다.[1][2] 매우 높은 최소 거리를 가져, 널리 응용된다.

정의[편집]

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

여기서

  • 해밍 거리이다.
  • 사전식 순서에서의 최소 원소이다.

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

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

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

(확장) 이진 골레 부호(擴張二進Golay符號, 영어: (extended) binary Golay code)라고 한다.

24개의 비트 가운데, 아무 한 비트를 삭제하면, 완전 골레 부호(完全Golay符號, 영어: perfect Golay code) 를 얻는다.

성질[편집]

확장 이진 골레 부호 는 [24,12,8]2-선형 부호이다. 즉,

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

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

이다.

완전 이진 골레 부호 는 [23,12,7]2-선형 부호이며, 완전 블록 부호이다. 즉,

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

부호어[편집]

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

해밍 무게 안정자군 안정자군의 크기 용어 비고
0 1 대칭군 24! 영벡터
8 759=3×11×23 ( 교대군) 32560 옥타드(영어: octad)
12 2576=23×3×7×23 마티외 군 95040 도데카드(영어: dodecad) 항상 두 옥타드의 합
16 759=3×11×23 32560 헥사데카드(영어: hexadecad) 옥타드의 비트 여원
24 1 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의 수)이다.

옥타드[편집]

확장 이진 골레 부호 의 각 옥타드는 집합 의, 크기 8의 부분 집합으로 여길 수 있다. 이에 따라, 확장 이진 골레 부호의 옥타드의 집합은 (5,8,24)-슈타이너 계를 이루며, 이를 비트 설계(Witt設計, 영어: Witt design)라고 불린다.

도데카드[편집]

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

이다.

대칭[편집]

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

여기서

  • 은 각각 마티외 군이다.
  • 대칭군이다.
  • 순열 위의 작용이다.

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

생성 행렬[편집]

이진 골레 부호의 표준형 생성 행렬 전치 행렬은 다음과 같다.

BinaryGolayCode.svg

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

역사[편집]

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

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

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

참고 문헌[편집]

  1. Conway, John Horton; Sloane, Neil J. A. (1999). 《Sphere packings, lattices and groups》. Grundlehren der Mathematischen Wissenschaften (영어) 290 3판. Springer-Verlag. ISBN 978-1-4419-3134-4. MR 0920369. Zbl 0915.52003. doi:10.1007/978-1-4757-6568-7. 
  2. 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. Zbl 0545.94016. 
  3. Griess, Robert L. Jr. (1998). 《Twelve sporadic groups》. Springer Monographs in Mathematics (영어). Springer-Verlag. ISBN 978-3-642-08305-1. ISSN 1439-7382. doi:10.1007/978-3-662-03516-0. 
  4. Carmichael, Robert Daniel (1931). “Tactical configurations of rank two”. 《American Journal of Mathematics》 (영어) 53: 217–240. JSTOR 10.2307/2370885. doi:10.2307/2370885. 
  5. Witt, Ernst (1938). “Die 5-Fach transitiven Gruppen von Mathieu”. 《Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg》 (독일어) 12: 256–264. doi:10.1007/BF02948947. 
  6. 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. 

외부 링크[편집]