삼진 골레 부호

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

1. 개요
2. 정의
- 2.1. 완전 삼진 골레 부호 (Perfect ternary Golay code)
- 2.2. 확장 삼진 골레 부호 (Extended ternary Golay code)
3. 성질
4. 역사
5. 응용
참조

1. 개요

삼진 골레 부호는 1949년 마르셀 쥘 에두아르 골레가 재발견한 선형 부호로, 통신 시스템 및 데이터 저장 장치에서 오류 정정에 사용된다. 확장 삼진 골레 부호는 [12, 6, 6]₃ 선형 부호로 3개의 오류를 정정하거나 5개의 오류를 발견할 수 있으며, 완전 삼진 골레 부호는 [11, 6, 5]₃ 선형 부호로 2개의 오류를 정정하거나 4개의 오류를 발견할 수 있다. 완전 삼진 골레 부호는 마티유 군 M₁₁을 자기 동형군으로 가지며, 확장 삼진 골레 부호는 마티유 군 M₁₂의 2차 중심 확대를 자기 동형군으로 갖는다. 이 부호는 핀란드의 축구 애호가 유나히 비르타칼리오가 1947년에 독립적으로 발견하여 축구 풀 베팅에 사용하려 했으나, 상금 문제로 인해 잊혀졌다. 최근에는 양자 컴퓨터의 내결함성 구현에 활용될 가능성이 연구되고 있다.

더 읽어볼만한 페이지

부호 이론 - 해밍 거리
해밍 거리는 길이가 같은 두 문자열에서 서로 다른 기호의 개수를 나타내는 거리 척도로, 아벨 군에서는 벡터의 해밍 무게를 영벡터와의 해밍 거리로 정의하며, 오류 검출, 수정 부호 이론, 정보 이론, 계통학 등에서 활용된다.
부호 이론 - 선형 부호
선형 부호는 유한체 위의 벡터 공간의 부분 공간으로, 데이터 전송 및 오류 정정을 위해 사용되며, 길이, 차원, 최소 거리에 따라 표기되고, 부호어, 생성 행렬, 패리티 검사 행렬 등의 개념을 갖는다.
유한체 - 이산 로그
이산 로그는 유한군에서 이산 거듭제곱의 지수를 찾는 역함수로, 소수 p를 법으로 하는 정수 모듈러 곱셈 그룹에서 계산적으로 풀기 어려운 문제이며, 현대 암호 시스템의 안전성 기반이지만 양자 알고리즘으로 효율적 해결이 가능하여 양자 내성 암호 연구가 필요하다.
유한체 - 순환 중복 검사
순환 중복 검사(CRC)는 데이터 전송 또는 저장 시 오류 검출을 위해 데이터를 다항식으로 간주하고 생성 다항식으로 나눈 나머지를 검사 값으로 사용하여 오류를 감지하는 기술이다.
군론 - 점군
점군은 도형의 병진 조작을 제외한 대칭 조작들의 집합으로 군론의 공리를 만족하며, 쉐인플리스 기호나 허먼-모건 기호로 표기되고, 대칭 조작에 대응하는 행렬 표현은 가약 표현과 기약 표현으로 분해될 수 있다.
군론 - 파울리 행렬
파울리 행렬은 양자역학에서 스핀을 나타내는 데 사용되는 에르미트 행렬이자 유니타리 행렬로, 행렬식은 -1이고 대각합은 0이며, 리 대수의 생성원이자 파울리 벡터로 정의되어 다양한 물리학 분야에서 활용된다.

삼진 골레 부호
개요
이름	완전 삼진 골레이 부호
영문명	Perfect ternary Golay code
부호 정보
유형	선형 블록 부호
블록 길이	11
메시지 길이	6
부호율	6/11 ~ 0.545
최소 거리	5
알파벳 크기	3
표기법	$[11,6,5]_3$ -code
관련 정보
이름	확장 삼진 골레이 부호
영문명	Extended ternary Golay code
유형	선형 블록 부호
블록 길이	12
메시지 길이	6
부호율	6/12 = 0.5
최소 거리	6
알파벳 크기	3
표기법	$[12,6,6]_3$ -code
인물
이름	마르셀 J. E. 골레이
영문명	Marcel J. E. Golay

2. 정의

표준형 생성 행렬

: $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}$

으로 정의되는, $\mathbb F_3^{12}$ 속의 삼진 선형 부호

: $\operatorname{im}G\subsetneq\mathbb F_3^{12}$

를 '''(확장) 삼진 골레 부호'''((extended) ternary Golay code^영어) $G_{12}$ 라고 한다.

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

패리티 검사 행렬은 다음과 같다.

: $\left[\begin{array}{cccccc|ccccc}2 & 2 & 2 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0\\2 & 2 & 1 & 2 & 0 & 1 & 0 & 1 & 0 & 0 & 0\\2 & 1 & 2 & 0 & 2 & 1 & 0 & 0 & 1 & 0 & 0\\2 & 1 & 0 & 2 & 1 & 2 & 0 & 0 & 0 & 1 & 0\\2 & 0 & 1 & 1 & 2 & 2 & 0 & 0 & 0 & 0 & 1\end{array}\right].$

생성 행렬은 다음과 같다.

: $\left[\begin{array}{cccccc|ccccc}1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1\\0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 2 & 2 & 0\\0 & 0 & 1 & 0 & 0 & 0 & 1 & 2 & 1 & 0 & 2\\0 & 0 & 0 & 1 & 0 & 0 & 2 & 1 & 0 & 1 & 2\\0 & 0 & 0 & 0 & 1 & 0 & 2 & 0 & 1 & 2 & 1\\0 & 0 & 0 & 0 & 0 & 1 & 0 & 2 & 2 & 1 & 1\\\end{array}\right].$

2. 1. 완전 삼진 골레 부호 (Perfect ternary Golay code)

완전 삼진 골레 부호는 [11, 6, 5]₃ 선형 부호이며, 11개의 삼진 심볼(0, 1, 2)로 구성된 코드워드 중 6개의 정보 심볼과 5의 최소 해밍 거리를 갖는다. 모든 오류를 2개까지 정정할 수 있고, 4개까지 발견할 수 있다. 삼진 골레 부호는 3⁶ = 729개의 부호어로 구성된다. 서로 다른 두 부호어는 최소 5개의 위치에서 다르다. 길이가 11인 모든 삼진 단어는 정확히 하나의 부호어로부터 최대 2의 해밍 거리를 갖는다.

이 부호는 또한 유한체 '''F'''₃ (''즉,'')上的 길이 11인 이차 잉여 부호로 구성할 수 있다. GF(3) ).

11개의 경기와 함께 축구 풀에서 사용되는 삼진 골레 부호는 729개의 베팅에 해당하며, 최대 2개의 잘못된 결과가 있는 베팅을 정확히 하나 보장한다.

해밍 가중치 5를 갖는 부호어 집합은 3-(11,5,4) 설계이다.

패리티 검사 행렬은 다음과 같다.

:

\left[\begin{array}{cccccc|ccccc}2 & 2 & 2 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0\\2 & 2 & 1 & 2 & 0 & 1 & 0 & 1 & 0 & 0 & 0\\2 & 1 & 2 & 0 & 2 & 1 & 0 & 0 & 1 & 0 & 0\\2 & 1 & 0 & 2 & 1 & 2 & 0 & 0 & 0 & 1 & 0\\2 & 0 & 1 & 1 & 2 & 2 & 0 & 0 & 0 & 0 & 1\end{array}\right].

Golay (1949, Table 1.)가 제공한 생성 행렬은 다음과 같다.

:

\left[\begin{array}{cccccc|ccccc}1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1\\0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 2 & 2 & 0\\0 & 0 & 1 & 0 & 0 & 0 & 1 & 2 & 1 & 0 & 2\\0 & 0 & 0 & 1 & 0 & 0 & 2 & 1 & 0 & 1 & 2\\0 & 0 & 0 & 0 & 1 & 0 & 2 & 0 & 1 & 2 & 1\\0 & 0 & 0 & 0 & 0 & 1 & 0 & 2 & 2 & 1 & 1\\\end{array}\right].

(원래의) 삼진 골레 부호의 자기 동형 사상군은 마티유 군 ''M''₁₁이며, 이는 불규칙적인 단순군 중 가장 작다.

2. 2. 확장 삼진 골레 부호 (Extended ternary Golay code)

확장 삼진 골레 부호는 선형 부호 [12, 6, 6]₃이며, 완전 삼진 골레 부호에 하나의 패리티 검사 심볼을 추가하여 얻어진다. 이 부호는 3개의 오류를 정정할 수 있고, 5개까지 발견할 수 있다.

확장 삼진 골레 부호의 전체 가중치 열거자는 다음과 같다.

:

x^{12}+y^{12}+z^{12}+22\left(x^6y^6+y^6z^6+z^6x^6\right)+220\left(x^6y^3z^3+y^6z^3x^3+z^6x^3y^3\right).

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

체 '''F'''₃ 위에서 12차 Hadamard 행렬의 행들의 span으로 구성될 수 있다. 0이 아닌 숫자 6개를 갖는 확장 부호의 모든 부호어를 고려하면, 이 0이 아닌 숫자들의 위치 집합은 Steiner system S(5, 6, 12)를 형성한다.

확장 삼진 골레 부호에 대한 생성 행렬은 다음과 같다.

:

\left[\begin{array}{cccccc|cccccc}1 & 0 & 0 & 0 & 0 & 0  &  0 & 1 & 1 & 1 & 1 & 1 \\0 & 1 & 0 & 0 & 0 & 0  &  1 & 0 & 1 & 2 & 2 & 1 \\0 & 0 & 1 & 0 & 0 & 0  &  1 & 1 & 0 & 1 & 2 & 2 \\0 & 0 & 0 & 1 & 0 & 0  &  1 & 2 & 1 & 0 & 1 & 2 \\0 & 0 & 0 & 0 & 1 & 0  &  1 & 2 & 2 & 1 & 0 & 1 \\0 & 0 & 0 & 0 & 0 & 1  &  1 & 1 & 2 & 2 & 1 & 0 \\\end{array}\right] = [I_6|B].

이 생성 행렬에 해당하는 패리티 검사 행렬은

[-B|I_6]^T

이며, 여기서

T

는 행렬의 전치를 나타낸다.

다른 생성 행렬은 다음과 같다.

:

\left[\begin{array}{rrrrrr|rrrrrr}1 & 0 & 0 & 0 & 0 & 0  &  0 &  1 &  1 &  1 &  1 &  1 \\0 & 1 & 0 & 0 & 0 & 0  &  1 &  0 &  1 & -1 & -1 &  1 \\0 & 0 & 1 & 0 & 0 & 0  &  1 &  1 &  0 &  1 & -1 & -1 \\0 & 0 & 0 & 1 & 0 & 0  &  1 & -1 &  1 &  0 &  1 & -1 \\0 & 0 & 0 & 0 & 1 & 0  &  1 & -1 & -1 &  1 &  0 &  1 \\0 & 0 & 0 & 0 & 0 & 1  &  1 &  1 & -1 & -1 &  1 &  0 \\\end{array}\right] = [I_6|B_{\mathrm{alt}}].

그리고 해당 패리티 검사 행렬은

[-B_{\mathrm{alt}}|I_6]^T

이다.

기저 유한체의 세 가지 요소는 {0, 1, -1}/{0,1,-1}^영어로 표현되며, {0, 1, 2}/{0,1,2}^영어가 아니다.

2=1+1=-1

(즉, 1의 덧셈 역원)이고

-2=(-1)+(-1)=1

로 이해된다. 이러한 유한체 요소들의 곱은 정수들의 곱과 동일하다. 행과 열의 합은 모듈로 3으로 계산된다.

생성 행렬의 행들의 선형 결합, 즉 벡터 덧셈은 부호에 포함된 모든 가능한 단어를 생성한다. 이것을 행들의 span이라고 한다. 생성 행렬의 임의의 두 행의 내적은 항상 0으로 합산된다. 이러한 행 또는 벡터는 직교라고 한다.

생성 행렬과 패리티 검사 행렬의 행렬 곱

[I_6|B_{\mathrm{alt}}]\,[-B_{\mathrm{alt}}|I_6]^T

는 모든 0으로 구성된

6\times6

행렬이며, 의도된 바이다.

3. 성질

확장 삼진 골레 부호는 [12,6,6]₃-선형 부호이다. 즉, 각 블록마다 3개 이하의 오류가 발생한다고 가정하면, 모든 오류를 교정할 수 있으며, 5개 이하의 오류가 발생한다고 가정하면, 모든 오류를 발견할 수 있다.

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

확장 삼진 골레 부호는 729개의 부호어를 가진다. 완전 삼진 골레 부호와 확장 삼진 골레 부호는 각각 해밍 상계를 포화시키는 완전 부호(perfect code)이다.

3. 1. 부호어 (Codewords)

확장 삼진 골레 부호는 729개의 부호어를 가지며, 그 부호어의 해밍 무게는 0, 6, 9, 12 중 하나이다. 각 해밍 무게를 갖는 부호어의 수는 다음과 같다.

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

마찬가지로, 완전 삼진 골레 부호는 729개의 부호어를 가지며, 그 부호어의 해밍 무게는 0, 5, 6, 8, 9, 11 중 하나이다. 각 해밍 무게를 갖는 부호어의 수는 다음과 같다.

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

3. 2. 대칭 (Symmetry)

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

M_{11}

이다. 확장 삼진 골레 부호의 자기 동형군은 마티외 군

M_{12}

의 2차 중심 확대(2.M₁₂)이다. 즉, 다음과 같은 군 짧은 완전열이 존재한다.

:

1\to\operatorname{Cyc}(2)\hookrightarrow\operatorname{Aut}(G_{12})\twoheadrightarrow M_{12}\to1

또한

\operatorname{Cyc}(2)\le\operatorname Z(\operatorname{Aut}(G_{12}))

이다.

3. 3. 생성 행렬 (Generator Matrix)

3. 4. 패리티 검사 행렬 (Parity Check Matrix)

4. 역사

핀란드의 축구 애호가 유나히 비르타칼리오(Junahi Virtakallio^fi, 필명 유카/Jukka^fi)가 1947년에 토토칼초를 짜기 위하여 토토칼초 잡지 《베이카야》(Veikkaaja^fi)에 기고한 글에 삼진 골레 부호가 이미 수록되었다.^[2]^[3]^[4] 비르타칼리오는 729개의 열(부호어)로 구성된 도박 체계를 개발하였는데, 당시에는 상금이 너무 낮아 매주 사용하지 않으면 투자금을 회수할 수 없어 출판되지 못하고 잊혀졌다고 밝혔다. 이후 1949년에 스위스의 수학자 마르셀 쥘 에두아르 골레(Marcel Jules Édouard Golay^프랑스어, 1902~1989)가 이진 골레 부호와 함께 삼진 골레 부호를 재발견하였다.^[5] 삼진 골레이 부호는 매직 상태 증류로 알려진 양자 컴퓨터의 내결함성 접근 방식에 유용하다는 것이 밝혀졌다.^[1]

5. 응용

삼진 골레 부호는 통신 시스템, 데이터 저장 장치 등에서 오류 정정을 위해 사용된다. 1949년 마르셀 J. E. 골레이가 발표하였다.^[1] 2년 전인 1947년에는 핀란드의 축구 풀 애호가 유하니 비르타칼리오가 독립적으로 발견하여 축구 잡지 ''Veikkaaja''에 게재하기도 했다.^[1] 최근에는 양자 컴퓨터의 내결함성 구현을 위한 매직 상태 증류에 활용될 가능성이 연구되고 있다.^[1]

참조

_[1] 논문 Magic state distillation with the ternary Golay code 2020-09
_[2] 간행물 1947-08-01
_[3] 서적 Covering codes https://www.elsevier[...] North-Holland 1997-04-14
_[4] 간행물 At the dawn of the theory of codes http://eng.umd.edu/~[...]
_[5] 간행물 Correspondence. Notes on digital coding 1949-06

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

문의하기 : help@durumis.com