이진 골레 부호

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
- 2.1. 이진 골레이 부호
- 2.2. 삼진 골레이 부호
3. 성질
- 3.1. 이진 골레이 부호
- 3.2. 삼진 골레이 부호
4. 구축
- 4.1. 이진 골레이 부호
- 4.2. 삼진 골레이 부호
5. 응용
- 5.1. 우주 탐사
- 5.2. 무선 통신
6. 역사
참조

1. 개요

이진 골레이 부호는 디지털 통신에서 사용되는 오류 정정 부호의 일종으로, 유한체 F2 위의 24차원 벡터 공간에서 정의된다. 확장 이진 골레이 부호는 12비트 데이터를 24비트 부호어로 부호화하며 3비트 오류 정정 및 4비트 오류 검출이 가능하며, [24, 12, 8] 선형 부호로 표현된다. 완전 이진 골레이 부호는 23비트 부호어를 사용하며, 3비트 오류 정정이 가능한 [23, 12, 7] 완전 블록 부호이다. 삼진 골레이 부호는 유한체 F3 위에서 정의되며, (11, 6, 5) 완전 삼진 선형 부호와 (12, 6, 6) 확장 삼진 선형 부호 두 종류가 있다. 이진 골레이 부호는 사전식 코드, 제곱 잉여 부호, 순환 부호, 미라클 옥타드 생성기(MOG) 등의 방법으로 구축될 수 있으며, 보이저 계획, 무선 통신 등 다양한 분야에 응용된다. 이진 골레이 부호의 옥타드는 1931년 로버트 대니얼 카마이클에 의해 최초로 발견되었고, 1949년 마르셀 쥘 에두아르 골레이에 의해 도입되었다.

더 읽어볼만한 페이지

부호 이론 - 해밍 거리
해밍 거리는 길이가 같은 두 문자열에서 서로 다른 기호의 개수를 나타내는 거리 척도로, 아벨 군에서는 벡터의 해밍 무게를 영벡터와의 해밍 거리로 정의하며, 오류 검출, 수정 부호 이론, 정보 이론, 계통학 등에서 활용된다.
부호 이론 - 선형 부호
선형 부호는 유한체 위의 벡터 공간의 부분 공간으로, 데이터 전송 및 오류 정정을 위해 사용되며, 길이, 차원, 최소 거리에 따라 표기되고, 부호어, 생성 행렬, 패리티 검사 행렬 등의 개념을 갖는다.
오류 검출 정정 - 부호 이론
부호 이론은 정보를 효율적으로 표현하고 오류를 감지 및 수정하는 기술을 연구하며, 소스 부호화, 채널 부호화, 암호 부호화 등으로 발전하여 CD, 모뎀, 휴대폰 등 다양한 분야에 응용된다.
오류 검출 정정 - 비터비 알고리즘
비터비 알고리즘은 잡음이 있는 통신 링크 상에서 길쌈 부호 해독에 사용되며, 확률과 관련된 극대화 문제에 동적 계획법을 적용하는 표준 용어로, 상태 기계를 기반으로 은닉 마르코프 모델에서 가장 가능성 높은 상태 시퀀스를 찾는 데 활용되어 통신, 자연어 처리, 생물정보학 등 다양한 분야에 적용되고 개선 방법이 연구되고 있다.
군론 - 점군
점군은 도형의 병진 조작을 제외한 대칭 조작들의 집합으로 군론의 공리를 만족하며, 쉐인플리스 기호나 허먼-모건 기호로 표기되고, 대칭 조작에 대응하는 행렬 표현은 가약 표현과 기약 표현으로 분해될 수 있다.
군론 - 파울리 행렬
파울리 행렬은 양자역학에서 스핀을 나타내는 데 사용되는 에르미트 행렬이자 유니타리 행렬로, 행렬식은 -1이고 대각합은 0이며, 리 대수의 생성원이자 파울리 벡터로 정의되어 다양한 물리학 분야에서 활용된다.

이진 골레 부호
개요
종류	선형 블록 부호
명명자	마르셀 J. E. 골레이
알파벳 크기	2
확장 이진 골레이 부호
부호 길이	24
메시지 길이	12
부호율	12/24 = 0.5
최소 거리	8
표기법	$[24,12,8]_2$ -부호
완전 이진 골레이 부호
부호 길이	23
메시지 길이	12
부호율	12/23 ~ 0.522
최소 거리	7
표기법	$[23,12,7]_2$ -부호
완전 부호 여부	완전 부호임
생성 행렬
생성 행렬

2. 정의

골레이 부호는 개발자인 마르셀 J. E. 골레이의 이름을 딴 오류 정정 부호로, 크게 이진 골레이 부호와 삼진 골레이 부호로 나뉜다.

'''이진 골레이 부호'''(Binary Golay code^영어)는 유한체 '''F'''₂ (두 원소 0, 1을 가짐) 상의 벡터 공간에서 정의된다.

'''확장 이진 골레이 부호'''(extended binary Golay code^영어) ''G''₂₄는 24차원 벡터 공간 '''F'''₂²⁴의 12차원 선형 부분 공간이다. 이 부호는 특정 수학적 규칙, 즉 기존에 선택된 부호들과의 해밍 거리가 최소 8 이상이 되도록 벡터들을 순차적으로 선택하여 구성할 수 있다. 표준 파라미터로는 [24, 12, 8]로 표기하며, 이는 부호어 길이 24, 정보 비트 수 12, 최소 거리 8을 의미한다.
'''완전 이진 골레이 부호'''(perfect binary Golay code^영어) ''G''₂₃은 확장 이진 골레이 부호 ''G''₂₄에서 특정 비트 하나를 제거하여 얻는 23차원 벡터 공간 '''F'''₂²³의 12차원 부분 공간이다. 표준 파라미터는 [23, 12, 7]이며, 이는 완전 부호의 조건을 만족시킨다.

'''삼진 골레이 부호'''(Ternary Golay code^영어)는 유한체 '''F'''₃ (세 원소 0, 1, 2를 가짐) 상에서 정의된다.

일반적으로 '''삼진 골레이 부호'''라 하면 [11, 6, 5] 파라미터를 갖는 완전 부호를 지칭한다.
'''확장 삼진 골레이 부호'''는 완전 삼진 골레이 부호에 패리티 비트를 추가하여 얻는 [12, 6, 6] 파라미터의 부호를 말한다.

각 부호의 구체적인 수학적 구조, 특징, 생성 방법 등은 하위 섹션에서 더 자세히 다룬다.

2. 1. 이진 골레이 부호

'''이진 골레이 부호'''(Binary Golay code^영어)는 디지털 통신에서 사용되는 오류 정정 부호의 한 종류이다. 이 부호는 유한체 '''F'''₂(두 개의 원소 0과 1을 갖는 체) 위의 벡터 공간에서 정의된다.

이진 골레이 부호에는 두 가지 주요 유형이 있다.

=== 확장 이진 골레이 부호 ===

'''확장 이진 골레이 부호'''(extended binary Golay code^영어) ''G''₂₄는 12비트의 데이터를 24비트의 부호어로 부호화한다. 이 부호는 [24, 12, 8] 파라미터를 갖는 선형 부호이다. 각 숫자는 다음을 의미한다.

24: 부호어의 총 길이 (비트 수)
12: 원본 데이터의 길이 (비트 수), 즉 부호 공간의 차원
8: 부호의 최소 거리 (두 부호어 간의 최소 해밍 거리)

최소 거리가 8이므로, 확장 이진 골레이 부호는 최대 3개의 오류를 정정할 수 있으며, 최대 7개의 오류를 검출할 수 있다.

수학적으로 ''G''₂₄는 24차원 벡터 공간 '''F'''₂²⁴의 12차원 선형 부분 공간이며, 이 부분 공간에 속하는 0이 아닌 모든 부호어(벡터)는 최소 8개의 1을 갖는다(즉, 해밍 무게가 8 이상이다). 확장 이진 골레이 부호의 부호어들은 0, 8, 12, 16, 24 중 하나의 해밍 무게를 갖는다.

무게 8인 부호어는 '''옥타드'''(octad)라고 불린다. 총 759개의 옥타드가 존재하며, 이는 슈타이너 시스템 S(5, 8, 24)의 블록(block)에 해당한다.
무게 12인 부호어는 '''도데카드'''(dodecad)라고 불린다.

확장 이진 골레이 부호는 스스로의 쌍대 부호와 같은 자기 쌍대 부호(''G''₂₄ = ''G''₂₄^⊥)라는 중요한 성질을 갖는다. 또한, 좌표의 순서를 바꾸는 변환까지 고려하면 확장 이진 골레이 부호는 유일하게 존재한다. 이 부호의 자기 동형군은 마티외 군 ''M''₂₄이다.

=== 완전 이진 골레이 부호 ===

'''완전 이진 골레이 부호'''(perfect binary Golay code^영어) ''G''₂₃은 확장 이진 골레이 부호 ''G''₂₄에서 특정 비트 위치 하나를 제거하여 얻어지는 23비트 부호어이다. (반대로, 완전 이진 골레이 부호에 적절한 패리티 비트를 추가하면 확장 이진 골레이 부호가 된다.)

이 부호는 [23, 12, 7] 파라미터를 갖는 선형 부호이다. 최소 거리가 7이므로, 최대 3개의 오류를 정정할 수 있으며, 최대 6개의 오류를 검출할 수 있다.

완전 이진 골레이 부호는 이름 그대로 완전 부호이다. 이는 부호 공간 '''F'''₂²³ 내에서 각 부호어를 중심으로 하고 반지름이 3인 해밍 공들이 서로 겹치지 않으면서 전체 공간을 빈틈없이 채운다는 의미이다 (즉, 해밍 상계를 등호로 만족시킨다). 완전 이진 골레이 부호의 자기 동형군은 마티외 군 ''M''₂₃이다.

=== 생성 방법 ===

이진 골레이 부호는 여러 가지 방법으로 생성될 수 있다.

사전식 부호: 벡터들을 사전식 순서로 배열하고, 기존 부호들과의 해밍 거리가 최소 8 이상이 되도록 기저 벡터들을 재귀적으로 선택하여 생성한다.
제곱 잉여 부호: 유한체 '''F'''₂₃의 제곱 잉여와 비잉여 집합을 이용하여 생성한다.
순환 부호: 다항식 ''x''²³ - 1의 인수분해를 이용하여 생성한다. 생성 다항식 중 하나는 ''x''¹¹ + ''x''¹⁰ + ''x''⁶ + ''x''⁵ + ''x''⁴ + ''x''² + 1이다.
기적의 팔원 생성기(Miracle Octad Generator^영어): R. T. Curtis가 고안한 방법으로, 4x6 배열을 사용하여 옥타드(무게 8 부호어)를 생성하고 이들의 대칭차 연산을 통해 모든 부호어를 얻는다.

2. 2. 삼진 골레이 부호

삼진 골레이 부호(Ternary Golay code^영어)는 서로 관련된 두 종류의 오류 정정 부호이다. 일반적으로 삼진 골레이 부호라고 하면, 완전 부호인 (11, 6, 5) 삼진 선형 부호를 가리킨다. 이는 유한체 '''F'''₃ 위에서 정의되며, 길이 11, 차원 6, 최소 거리 5를 갖는다.
확장 삼진 골레이 부호(extended ternary Golay code)는 (12, 6, 6) 선형 부호이며, 완전 삼진 골레이 부호 (11, 6, 5)에 제로섬 체크 디지트를 추가하여 얻는다. 즉, 부호어의 모든 성분의 합이 0이 되도록 패리티 비트를 추가한 것이다.

확장 삼진 골레이 부호의 가중치 다항식은 다음과 같다.

:

x^{12}+y^{12}+z^{12}+22(x^6y^6+y^6z^6+z^6x^6)+220(x^6y^3z^3+y^6z^3x^3+z^6x^3y^3)

완전 삼진 골레이 부호는 유한체 '''F'''₃ 상의 길이 11 제곱 잉여 부호로 구성할 수 있다.

확장 삼진 골레이 부호는 유한체 '''F'''₃ 상의 12차 아다마르 행렬의 행 벡터들이 생성하는 벡터 공간으로 구성할 수도 있다.

확장 삼진 골레이 부호의 자기 동형군은 2.''M''₁₂ 이다. 여기서 ''M''₁₂는 매튜 군이다.

확장 삼진 골레이 부호에서 무게가 6인 (즉, 0이 아닌 성분이 6개인) 부호어들을 생각해보면, 0이 아닌 성분들의 위치 집합은 슈타이너 계 S(5, 6, 12)를 형성한다.

3. 성질

이진 골레 부호는 뛰어난 오류 정정 능력을 가지는 것으로 알려져 있다. 특히 확장 이진 골레 부호와 완전 이진 골레 부호는 수학적으로 흥미로운 여러 성질을 지닌다.

확장 이진 골레 부호 $G_{24}$ 는 유한체 $\mathbb F_2$ 위의 24차원 벡터 공간 $\mathbb F_2^{24}$ 의 12차원 선형 부분 공간으로, 총 4096개의 부호어를 포함한다. 이 부호는 [24, 12, 8]₂ 선형 부호로 표기되며, 최소 해밍 거리는 8이다. 이 거리 덕분에 각 블록에서 최대 3개의 오류를 정정하고 최대 7개의 오류를 검출할 수 있다.^[1] $G_{24}$ 의 중요한 성질은 스스로의 쌍대 선형 부호와 같다는 점( $G_{24} = G_{24}^\perp$ )이며, 좌표의 순서를 바꾸는 것을 제외하면 유일하다.^[1] 부호어들이 가질 수 있는 해밍 가중치는 0, 8, 12, 16, 24로 제한되며, 가중치가 8인 부호어는 '''옥타드'''(octad^영어), 가중치가 12인 부호어는 '''도데카드'''(dodecad^영어)라고 불린다.^[1] 759개의 옥타드는 S(5,8,24) 슈타이너 시스템의 블록을 형성한다.^[1] 확장 이진 골레 부호의 자기 동형군은 마티외 군 $M_{24}$ 이다.^[1]

완전 이진 골레 부호 $G_{23}$ 는 [23, 12, 7]₂ 선형 부호이며, 최소 해밍 거리는 7이다. 이를 통해 각 블록에서 최대 3개의 오류를 정정하고 최대 6개의 오류를 검출할 수 있다.^[1] 이름처럼 $G_{23}$ 는 완전 부호인데, 이는 부호 이론의 해밍 상계를 포화시킨다는 의미이다.^[1] 즉, $\mathbb F_2^{23}$ 공간에서 각 부호어를 중심으로 하는 반지름 3의 해밍 구들이 서로 겹치지 않으면서 전체 공간을 빈틈없이 채운다.^[1] 완전 이진 골레 부호의 자기 동형군은 마티외 군 $M_{23}$ 이다.^[1]

3. 1. 이진 골레이 부호

'''이진 골레이 부호'''(Binary Golay code^영어)는 디지털 통신에서 사용되는 전방 오류 정정 부호의 한 종류이다. 이 부호는 수학적으로 흥미로운 구조와 뛰어난 오류 정정 능력을 가진다.

이진 골레이 부호에는 두 가지 주요 유형이 있다: '''확장 이진 골레이 부호'''(extended binary Golay code^영어)와 '''완전 이진 골레이 부호'''(perfect binary Golay code^영어)이다.

=== 확장 이진 골레이 부호 (G₂₄) ===

확장 이진 골레이 부호

G_{24}

는 유한체

\mathbb F_2

위의 24차원 벡터 공간

\mathbb F_2^{24}

의 12차원 선형 부분 공간이다. 이는 4096(= 2¹²)개의 부호어(부호어)를 포함한다. 이 부호의 중요한 특징은 서로 다른 두 부호어 간의 해밍 거리가 최소 8이라는 점이다. 즉, 0이 아닌 부호어는 최소 8개의 0이 아닌 좌표(즉, 해밍 무게가 최소 8)를 가진다.

확장 이진 골레이 부호는 [24, 12, 8]₂-선형 부호로 표기된다. 이는 다음을 의미한다:

부호어의 길이는 24비트이다.
정보 비트의 수는 12비트이다 (즉, 12비트 데이터를 24비트 부호어로 부호화한다).
최소 해밍 거리는 8이다.

이러한 특성 덕분에 확장 이진 골레이 부호는 다음과 같은 오류 정정 및 검출 능력을 가진다:

각 블록(부호어)에서 최대 3개의 오류를 항상 정정할 수 있다.
각 블록에서 최대 7개의 오류를 항상 검출할 수 있다.

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

G_{24} = G_{24}^\perp

). 이는 부호 이론에서 매우 특별한 성질이다. 좌표 재명명(relabeling)을 고려하면

G_{24}

는 유일하다.

확장 이진 골레이 부호의 부호어들은 특정 해밍 무게 값만 가진다. 각 해밍 무게에 따른 부호어의 종류와 수는 다음과 같다.

해밍 무게	부호어 수	안정자군	안정자군 크기	용어	비고
0	1	대칭군 $\operatorname{Sym}(24)$	24!	영벡터
8	759	$\operatorname{IGL}(4;\mathbb F_2)\cong\mathbb F_2^4\rtimes\operatorname{GL}(4;\mathbb F_2)$	322560	옥타드 (octad^영어)	$\operatorname{GL}(4;\mathbb F_2)\cong\operatorname{Alt}(8)$ 교대군. S(5,8,24) 슈타이너 시스템의 블록.
12	2576	마티외 군 $M_{12}$	95040	도데카드 (dodecad^영어)	항상 두 옥타드의 합 (대칭 차이)
16	759	$\operatorname{IGL}(4;\mathbb F_2)$	322560	헥사데카드 (hexadecad^영어)	옥타드의 비트 여원(complement)
24	1	$\operatorname{Sym}(24)$	24!	모든 비트가 1인 벡터	영벡터의 비트 여원

해밍 무게가 8인 부호어, 즉 '''옥타드'''는 특히 중요하다. 759개의 옥타드는 집합 $\{1, 2, \dots, 24\}$ 의 크기 8인 부분 집합으로 볼 수 있으며, 이들은 (5, 8, 24)-슈타이너 계를 형성한다. 이를 '''비트 설계'''(Witt design^영어)라고도 부른다. 두 옥타드는 0, 2, 또는 4개의 위치에서 교차할 수 있다.

확장 이진 골레이 부호의 자기 동형군은 마티외 군 $M_{24}$ 이며, 이 군은 옥타드와 도데카드 위에서 전이적으로 작용한다. 다른 마티외 군들은 $G_{24}$ 의 특정 원소들의 안정자군으로 나타난다.

=== 완전 이진 골레이 부호 (G₂₃) ===

완전 이진 골레이 부호 $G_{23}$ 는 확장 이진 골레이 부호 $G_{24}$ 에서 특정 한 비트 위치를 제거하여 얻어진다. 반대로, 완전 이진 골레이 부호에 적절한 패리티 비트를 추가하면 확장 이진 골레이 부호를 얻을 수 있다.

완전 이진 골레이 부호는 [23, 12, 7]₂-선형 부호이다.

부호어 길이는 23비트이다.
정보 비트 수는 12비트이다.
최소 해밍 거리는 7이다.

오류 정정 및 검출 능력은 다음과 같다:

각 블록에서 최대 3개의 오류를 항상 정정할 수 있다.
각 블록에서 최대 6개의 오류를 항상 검출할 수 있다.

완전 이진 골레이 부호는 이름처럼 완전 부호이다. 이는 해밍 상계를 등호로 만족시킨다는 의미이며, 부호어를 중심으로 하는 반지름 3의 해밍 구들이 전체 벡터 공간

\mathbb F_2^{23}

을 빈틈없이 채운다는 뜻이다.

완전 이진 골레이 부호의 자기 동형군은 마티외 군

M_{23}

이다.

=== 구성 방법 ===

이진 골레이 부호는 여러 가지 방법으로 구성될 수 있다.

# '''사전식 부호'''(Lexicographic code^영어): 24비트 벡터들을 사전식 순서로 배열하고, 이전 벡터들과의 해밍 거리가 최소 8이 되도록 12개의 기저 벡터

w_1, \dots, w_{12}

를 탐욕적으로 선택하여 그들의 생성(span)으로 부호를 정의한다.

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\}

(단,

\operatorname{Span}_{\mathbb F_2}\varnothing = \{0\}

).

# '''제곱 잉여 부호'''(Quadratic residue code^영어): 유한체

\mathbb F_{23}

의 제곱 잉여와 제곱 비잉여 집합

N

을 이용하여 구성한다.

N

의 평행이동

t+N

에 원소

\infty

를 추가하여 집합

S_t

를 만들고, 이들을 기저로 사용하여 부호를 생성한다. 완전 부호는

\infty

를 제외하여 얻는다.

# '''순환 부호'''(Cyclic code^영어): 완전 골레이 부호

G_{23}

는 다항식

x^{23}-1

의 인수분해를 통해 생성 다항식

x^{11}+x^{10}+x^6+x^5+x^4+x^2+1

을 갖는 순환 부호로 구성될 수 있다.

# '''미라클 옥타드 생성기'''(Miracle Octad Generator^영어): R. T. Curtis가 고안한 4×6 배열을 사용하여 옥타드를 생성하고, 이들의 대칭차 연산을 통해 모든 부호어를 얻는 방법이다.

# '''수학 게임 Mogul''': 24개의 동전을 이용하는 게임 Mogul의 특정 승리 패턴이 확장 이진 골레이 부호의 부호어와 일치한다.

3. 2. 삼진 골레이 부호

'''삼진 골레이 부호'''(Ternary Golay code^eng)는 서로 관련된 두 종류의 오류 정정 부호이다. 일반적으로 '''삼진 골레이 부호'''는 완전 부호인 (11, 6, 5) 삼진 선형 부호를 의미한다. 이 부호는 유한체 '''F'''₃ 상에서 길이가 11인 제곱 잉여 부호로 만들 수 있다.

'''확장 삼진 골레이 부호'''(extended Ternary Golay code^eng)는 (12, 6, 6) 선형 부호이며, 완전 삼진 골레이 부호 (11, 6, 5)에 제로섬 체크 디지트를 추가하여 얻는다. 확장 삼진 골레이 부호는 유한체 '''F'''₃ 상의 12차 아다마르 행렬의 행들의 스팬으로부터 구축 가능하다.

확장 삼진 골레이 부호의 부호어들의 무게 분포는 특정 다항식(가중치 다항식)으로 표현된다. 이 부호의 자기 동형군은 2.''M''₁₂ 형태이며, 여기서 ''M''₁₂는 매튜 군 중 하나이다. 또한, 확장 삼진 골레이 부호에서 0이 아닌 자릿수가 정확히 6개인 모든 부호어를 살펴보면, 그 0이 아닌 자릿수들의 위치 집합은 슈타이너 계 S(5, 6, 12)의 블록(block)을 형성한다.

4. 구축

이진 골레 부호는 여러 가지 독특하고 흥미로운 수학적 방법을 통해 구축될 수 있다. 주요 구성 방법으로는 사전식 부호 생성 방식, 마티외 군 $M_{24}$ 의 특정 작용을 이용하는 방식^[4], 제곱 잉여 집합을 활용한 제곱 잉여 부호 방식, 특정 다항식을 생성 다항식으로 사용하는 순환 부호 방식^[5]^[6], 해밍 부호와 제곱 잉여를 결합한 터린(Turyn)의 방식^[7], 슈타이너 시스템 S(5,8,24)의 블록(옥타드)을 이용하는 방식, 그리고 이를 시각적으로 표현하는 미라클 옥타드 생성기(MOG)^[8] 등이 있다. 또한, 특정 수학 게임인 모굴(Mogul)의 승리 전략이나 이십면체 그래프의 인접 행렬을 이용한 생성 행렬 구성 등 다양한 관점에서 접근할 수 있다.

4. 1. 이진 골레이 부호

유한체

\mathbb F_2

위의 24차원 벡터 공간

\mathbb F_2^{24}

의 12차원 선형 부분 공간 ''W''를 '''확장 이진 골레 부호'''(extended binary Golay code^영어)

G_{24}

라고 한다. 이 부호의 핵심 특징은 ''W''에 속하는 서로 다른 두 부호어(codeword)는 최소 8개의 좌표에서 서로 다르다는 점이다(즉, 해밍 거리가 최소 8이다). ''W''는 벡터 공간이므로 선형 부호이며, 총

2^{12} = 4096

개의 부호어를 포함한다. 좌표의 순서를 바꾸는 것을 제외하면, ''W''는 유일하다.

''W''의 원소인 부호어는 24개 요소 집합의 부분 집합으로도 설명될 수 있으며, 덧셈 연산은 대칭차로 정의된다.
확장 이진 골레 부호의 모든 부호어는 해밍 가중치가 0, 8, 12, 16, 24 중 하나이다. 가중치 8인 부호어는 '''옥타드'''(octad), 가중치 12인 부호어는 '''도데카드'''(dodecad)라고 부른다.
$G_{24}$ 의 옥타드는 슈타이너 시스템 S(5,8,24)의 블록(크기 8인 부분 집합)에 해당하며, 총 759개가 존재한다. 이들의 여집합(complement) 역시 759개 존재한다. 따라서 도데카드는 총 $2576 = 2^4 \times 7 \times 23$ 개가 존재한다.
두 옥타드는 0, 2, 또는 4개의 좌표에서 교차한다(부분 집합 표현에서의 교차 크기). 옥타드와 도데카드는 2, 4, 또는 6개의 좌표에서 교차한다.

확장 이진 골레 부호

G_{24}

에서 임의의 한 좌표 위치를 제거하면 '''완전 골레 부호'''(perfect Golay code^영어)

G_{23}

를 얻는다. 이는

\mathbb{F}_2

상의 23차원 벡터 공간

\mathbb{F}_2^{23}

의 12차원 부분 공간이다.

G_{23}

는 완전 부호인데, 이는 부호어를 중심으로 하는 반지름 3의 구(해밍 구)들이 전체 벡터 공간을 빈틈없이 채우기 때문이다(해밍 한계를 만족).

=== 자기 동형군 ===

자기 동형 군은 부호를 보존하는 좌표의 순열(permutation) 집합이다.

완전 이진 골레 부호 $G_{23}$ 의 자기 동형군은 마티외 군 $M_{23}$ 이다.
확장 이진 골레 부호 $G_{24}$ 의 자기 동형군은 마티외 군 $M_{24}$ 이며, 그 크기는 $2^{10} \times 3^3 \times 5 \times 7 \times 11 \times 23$ 이다. $M_{24}$ 는 옥타드 집합과 도데카드 집합 위에서 전이적으로 작용한다. 다른 마티외 군들은 ''W''의 특정 원소들을 고정시키는 안정화 부분군(stabilizer subgroup)으로 나타난다.

=== 구성 방법 ===

이진 골레 부호를 구성하는 방법은 여러 가지가 알려져 있다.

'''사전식 부호''': 벡터를 사전식 순서로 배열하고(즉, 0부터 $2^{24}-1$ 까지의 정수로 간주), $w_1, \dots, w_{12}$ 를 재귀적으로 선택한다. 각 $w_i$ 는 이전에 선택된 $w_1, \dots, w_{i-1}$ 들의 모든 선형 결합과 최소 8의 해밍 거리를 가지는 가장 작은 정수(벡터)이다. $G_{24}$ 는 이 $w_1, \dots, w_{12}$ 로 생성된(spanned) 공간이다. 이 기저 벡터들을 10진수로 나타내면 다음과 같다: 255, 3855, 13107, 21845, 38505, 197462, 329059, 591418, 1118584, 2167325, 4265038, 8460068.
'''제곱 잉여 부호''': 법 23에 대한 제곱 비잉여들의 집합 $N \subset \mathbb{Z}/23\mathbb{Z}$ (크기 11)을 이용한다. 각 평행 이동(translate) $t+N$ 에 무한대 기호 $\infty$ 를 추가하여 12원소 집합 $S_t$ 를 만든다. 벡터 공간의 기저 원소들을 $0, 1, \dots, 22, \infty$ 로 이름 붙이면, $G_{24}$ 는 모든 $S_t$ 와 모든 기저 벡터를 포함하는 벡터들로 생성된다. 완전 골레 부호 $G_{23}$ 는 $\infty$ 좌표를 제외하여 얻는다.
'''순환 부호''': 완전 골레 부호 $G_{23}$ 는 다항식 $x^{23}-1$ 을 $\mathbb{F}_2$ 상에서 인수분해하여 구성할 수 있다.

x^{23} - 1 = (x-1)(x^{11} + x^9+x^7+x^6+x^5+x+1)(x^{11}+x^{10}+x^6+x^5+x^4+x^2+1).

G_{23}

는 두 개의 11차 기약 인수 중 하나, 예를 들어

g(x) = x^{11}+x^{10}+x^6+x^5+x^4+x^2+1

를 생성 다항식으로 하는 순환 부호이다.^[5]^[6]

'''슈타이너 시스템 S(5,8,24)''': 이 슈타이너 시스템의 759개 블록(크기 8인 부분 집합, 옥타드)을 $G_{24}$ 의 가중치 8 부호어로 간주한다. 전체 부호 $G_{24}$ 는 이 옥타드들의 대칭차(벡터 덧셈)를 반복적으로 취하여 생성된다.
'''미라클 옥타드 생성기 (MOG)''': R. T. 커티스가 개발한 방법으로, 옥타드를 시각적으로 쉽게 구성하고 표현하는 방법이다. 4x6 배열의 셀을 사용하며, 특정 규칙에 따라 옥타드를 생성한다.^[8] 존 콘웨이가 제안한 '''헥사코드'''(hexacode) 표현도 이와 유사하게 4x6 배열을 사용한다.
'''수학 게임 모굴(Mogul)''': 24개의 동전이 놓인 상태에서 진행하는 게임이다. 특정 규칙에 따라 동전을 뒤집으며, 합법적인 수가 없는 플레이어가 패배한다. 앞면을 1, 뒷면을 0으로 간주할 때, 확장 이진 골레 부호의 부호어에 해당하는 상태가 승리 위치가 된다.
'''생성 행렬''': $G_{24}$ 의 생성 행렬은 $[I_{12} | A]$ 형태로 만들 수 있다. 여기서 $I_{12}$ 는 12x12 단위 행렬이고, $A$ 는 이십면체 그래프의 인접 행렬의 여집합(complement)이다.

4. 2. 삼진 골레이 부호

삼진 골레이 부호(Ternary Golay code^영어)는 서로 관련된 두 종류의 오류 정정 부호이다. 일반적으로 삼진 골레이 부호라고 하면, 완전 부호인 (11, 6, 5) 삼진 선형 부호를 가리킨다. 확장 삼진 골레이 부호(extended ternary Golay code^영어)는 (12, 6, 6) 선형 부호이며, (11, 6, 5) 부호에 제로섬 체크 디지트를 추가하여 만든다.

확장 삼진 골레이 부호의 가중치 다항식은 다음과 같다.

:

x^{12}+y^{12}+z^{12}+22(x^6y^6+y^6z^6+z^6x^6)+220(x^6y^3z^3+y^6z^3x^3+z^6x^3y^3)

완전 삼진 골레이 부호는 유한체

\mathbb F_3

상의 길이 11 제곱 잉여 부호로 구축할 수 있다.

확장 삼진 골레이 부호의 자기 동형군은 2.''M''₁₂ 이며, 여기서 ''M''₁₂는 매튜 군이다.

확장 삼진 골레이 부호는 유한체

\mathbb F_3

상의 12차 아다마르 행렬의 행들의 스팬으로부터 구축할 수 있다.

0이 아닌 6개의 자릿수를 가진 확장 삼진 골레이 부호의 모든 부호어를 고려했을 때, 그 0이 아닌 자릿수의 위치 집합은 슈타이너 계 S(5, 6, 12)를 형성한다.

5. 응용

이진 골레 부호는 데이터 전송 과정에서 발생하는 오류를 효과적으로 정정하는 능력 덕분에 다양한 분야에서 중요한 역할을 수행한다. 대표적인 예로, 데이터 재전송이 극히 어려운 심우주 탐사 분야에서 활용되었다. 1970년대 말과 1980년대 초 보이저 계획의 우주선들은 목성과 토성의 컬러 이미지를 지구로 전송할 때 제한된 통신 환경 속에서 데이터의 신뢰성을 확보하기 위해 확장 이진 골레 부호(확장 골레 부호 (24, 12, 8))를 사용했다.^[9]^[12] 이는 기존에 사용되던 부호보다 더 높은 데이터 전송률을 가능하게 했다.

또한 골레 부호는 무선 통신 분야에서도 널리 사용된다. 미국 군사 표준인 MIL-STD-188에서는 고주파(HF) 무선 시스템의 자동 링크 설정(ALE) 과정에서 순방향 오류 수정(FEC)을 위해 확장 (24, 12) 골레 부호를 사용하도록 명시하고 있다.^[10]^[11] 이 외에도 양방향 무전기 통신에서 사용되는 디지털 코드 스켈치(DCS) 시스템은 완전 (23, 12) 골레 부호를 이용하여 통신 중 발생할 수 있는 오류를 감지하고 수정한다.

5. 1. 우주 탐사

1979년부터 1981년까지 보이저 계획의 보이저 1호와 보이저 2호는 목성과 토성 근접 비행 중 다수의 천연색 사진을 지구로 전송해야 했다. 당시 우주 탐사선은 메모리 제약으로 데이터를 즉시 전송해야 했고 재전송 기회가 없었기에, 오류 정정 부호의 역할이 매우 중요했다.^[9]

컬러 이미지는 흑백 이미지보다 3배 더 많은 데이터를 필요로 했기 때문에, 기존 마리너 계획의 흑백 이미지 전송에 사용되었던 7-오류 정정 리드-뮬러 부호는 컬러 이미지 전송에 적합하지 않았다. 이에 보이저 탐사선은 컬러 이미지 전송을 위해, 아다마르 부호보다 데이터 전송률이 높은 확장 이진 골레 부호(코드 파라미터 [24, 12, 8])를 채택했다. 이 부호는 임의의 3비트 오류를 정정할 수 있었다.^[9]^[12] 한편, 보이저 탐사선의 흑백 사진 전송에는 아다마르 부호가 사용되었다.^[9]

5. 2. 무선 통신

MIL-STD-188 미국 군사 표준은 자동 링크 설정의 고주파 무선 시스템에서 순방향 오류 수정을 위해 확장 (24, 12) 골레이 부호 사용을 명시하고 있다.^[10]^[11] 이 방식은 12비트의 원본 데이터를 24비트 부호어로 변환하며, 임의의 3비트 오류를 정정할 수 있다.

또한, 양방향 무전기 통신에서 사용되는 디지털 코드 스켈치(DCS, CDCSS) 시스템은 23비트 길이의 완전 (23, 12) 골레이 부호를 사용한다. 이 부호는 3비트 이하의 오류를 감지하고 수정할 수 있는 능력을 가지고 있다.

6. 역사

이진 골레 부호의 옥타드의 집합, 즉 비트 설계는 1931년에 로버트 대니얼 카마이클이 처음으로 발견하였다.^[16] 이후 에른스트 비트가 1938년에 마티외 군을 연구하던 중 이를 다시 발견하였다.^[17]

스위스의 수학자 마르셀 쥘 에두아르 골레( Marcel Jules Édouard Golay^프랑스어, 1902~1989)는 1949년에 발표한 짧은 논문에서 이진 골레 부호를 삼진 골레 부호와 함께 소개하였다.^[18]

1979년부터 1981년까지 보이저 1호와 보이저 2호는 목성과 토성의 천연색 사진을 지구로 전송하는 데 확장 이진 골레 부호를 사용하였다. 참고로 흑백 사진 전송에는 아다마르 부호가 사용되었다.

참조

_[1] 서적 1983
_[2] 논문 Notes on Digital Coding https://pierre-hyver[...]
_[3] 서적 Key Papers in the Development of Coding Theory I.E.E.E. Press
_[4] 논문 Construction and Simplicity of the Large Mathieu Groups http://scholarworks.[...] 2011
_[5] 서적 1996
_[6] 서적 1998
_[7] 서적 1967
_[8] 웹사이트 The Miracle Octad Generator http://finitegeometr[...]
_[9] 웹사이트 Combinatorics in Space - The Mariner 9 Telemetry System http://www-math.ucde[...] University of Colorado Denver 2012-06-06
_[10] 웹사이트 An Efficient Golay Codec for MIL-STD-188-141A and FED-STD-1045 http://tracebase.nms[...] 1991-02-24
_[11] 웹사이트 Military Standard: Planning and Guidance Standard for Automated Control Applique for HF Radio http://everyspec.com[...] 1994-04-04
_[12] 웹사이트 Combinatorics in Space - The Mariner 9 Telemetry System http://www-math.ucde[...] University of Colorado Denver 2005-12-04
_[13] 서적 Sphere packings, lattices and groups Springer-Verlag 1999
_[14] 서적 From error correcting codes through sphere packings to simple groups http://www.cambridge[...] Mathematical Association of America 1983
_[15] 서적 Twelve sporadic groups Springer-Verlag 1998
_[16] 저널 Tactical configurations of rank two
_[17] 저널 Die 5-Fach transitiven Gruppen von Mathieu 1938
_[18] 저널 Correspondence. Notes on digital coding 1949-06

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com