선형 부호

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

1. 개요

선형 부호는 유한체 위의 벡터 공간의 부분 공간으로, 데이터를 효율적으로 전송하고 오류를 정정하기 위해 사용되는 수학적 개념이다. 길이, 차원, 최소 거리에 따라 [n, k, d]q-선형 부호로 표기되며, 부호어, 생성 행렬, 패리티 검사 행렬 등의 개념을 갖는다. 선형 부호는 오류 정정, 데이터 전송 등 다양한 분야에 응용되며, 해밍 부호, 아다마르 부호, 골레 부호 등이 대표적인 예시이다. 한국에서는 정보통신 기술 발전에 기여하며, ISBN과 같은 분야에도 활용된다.

더 읽어볼만한 페이지

부호 이론 - 해밍 거리
해밍 거리는 길이가 같은 두 문자열에서 서로 다른 기호의 개수를 나타내는 거리 척도로, 아벨 군에서는 벡터의 해밍 무게를 영벡터와의 해밍 거리로 정의하며, 오류 검출, 수정 부호 이론, 정보 이론, 계통학 등에서 활용된다.
부호 이론 - 리드 솔로몬 부호
리드 솔로몬 부호는 어빙 S. 리드와 구스타브 솔로몬이 개발한 오류 정정 부호로, 통신 및 데이터 저장 시 오류를 정정하기 위해 잉여 정보를 추가하며, 바코드, CD, DVD, 데이터 전송 등 다양한 분야에서 활용되고, 특히 버스트 오류에 강하고 다양한 디코딩 알고리즘을 통해 오류 정정 능력을 향상시킬 수 있다.
유한체 - 이산 로그
이산 로그는 유한군에서 이산 거듭제곱의 지수를 찾는 역함수로, 소수 p를 법으로 하는 정수 모듈러 곱셈 그룹에서 계산적으로 풀기 어려운 문제이며, 현대 암호 시스템의 안전성 기반이지만 양자 알고리즘으로 효율적 해결이 가능하여 양자 내성 암호 연구가 필요하다.
유한체 - 순환 중복 검사
순환 중복 검사(CRC)는 데이터 전송 또는 저장 시 오류 검출을 위해 데이터를 다항식으로 간주하고 생성 다항식으로 나눈 나머지를 검사 값으로 사용하여 오류를 감지하는 기술이다.
선형대수학 - 벡터 공간
벡터 공간은 체 위의 가군으로 정의되는 대수적 구조로, 벡터 덧셈과 스칼라 곱셈 연산을 가지며 특정 공리들을 만족하고, 기저, 차원, 선형 사상 등의 개념을 통해 수학과 물리학 등 다양한 분야에서 활용된다.
선형대수학 - 선형 결합
선형 결합은 벡터 공간에서 벡터들의 스칼라 곱의 합으로 표현되는 식으로, 벡터 집합의 선형 독립성 판단 및 부분 공간 생성과 관련되며, 계수 제약을 통해 다양한 종류의 결합을 정의할 수 있고, 위상 벡터 공간이나 가군으로 일반화될 수 있다.

선형 부호
개요
종류	부호 이론
분야	정보 이론, 수학, 컴퓨터 과학, 공학
연구	오류 검출 및 수정
정의
설명	'선형 블록 부호는 부호어(codeword)의 선형 조합이 또 다른 유효한 부호어가 되는 블록 부호이다. 선형 부호는 비선형 부호보다 쉽게 부호화 및 복호화할 수 있다. 선형 부호는 전산학, 정보 이론, 부호화 이론에서 오류 정정 부호로 널리 사용된다.'
특징	'길이 $n$ 의 선형 부호에서 부호어는 $n$ 차원 벡터 공간의 부분 공간을 형성하므로, 이러한 부호는 부분 공간의 차원 $k$ 로 특징지어지며 $(n, k)$ 부호라고 부른다. 부호어는 $n$ 개의 기호로 구성되지만, 메시지를 나타내는 데 사용되는 기호는 $k$ 개뿐이다. 따라서 선형 $(n, k)$ 부호는 $k$ 개의 기호를 취하여 $n$ 개의 기호로 매핑하여 각 기호는 $q$ 개의 기호가 있는 필드에서 가져온다. 기호가 이진수인 경우 $q=2$ 이며, 이는 기호가 비트임을 의미한다.'
장점	'선형 부호의 주요 이점은 부호화 및 복호화 알고리즘을 단순화할 수 있다는 것이다. 선형 부호는 생성 행렬과 패리티 검사 행렬로 완전히 설명될 수 있기 때문이다.'
예시	'선형 부호의 예로는 해밍 부호, 리드-솔로몬 부호, 이진 골레이 부호, 순환 부호, BCH 부호 등이 있다.'
수학적 정의
정의	'F를 유한체라고 하자. F에 대한 길이 n의 선형 부호 C는 F^n의 선형 부분공간이다. 이러한 부호는 n과 그 차원 k로 특징지어지며, 이는 그것이 (n, k) 부호라고 말해진다.'
부호화 및 복호화
설명	'선형 부호는 생성 행렬 G를 곱하여 부호화할 수 있으며, 이는 메시지 m을 부호어 c = mG로 변환한다. 복호화는 패리티 검사 행렬 H를 사용하여 수행할 수 있으며, 이는 수신된 단어 r의 신드롬 s = rH^T를 계산한다. 신드롬이 0이면 오류가 발생하지 않았을 가능성이 높으며, 그렇지 않으면 신드롬을 사용하여 오류를 수정할 수 있다.'

2. 정의 및 기본 개념

두 자연수 $n,k\in\mathbb N$ 및 소수의 (양의 정수 지수) 거듭제곱 $q\in\{2,3,4,5,7,8,9,11,\dotsc\}$ 가 주어졌다고 하자.

'''길이 $n$ 의 $k$ 차원 $q$ 진 선형 부호'''(- $k$ 次元 $q$ 進線型符號, $k$ -dimensional $q$ -ary linear code with length $n$ ^영어)는 유한체 $\mathbb F_q$ 위의 $n$ 차원 벡터 공간 $\mathbb F_q^n$ 속의 $k$ 차원 $\mathbb F_q$ -부분 벡터 공간

: $C\subseteq\mathbb F_q^n$

이다. 이는 블록 부호

: $C\colon\mathbb F_q^k\to\mathbb F_q^n$

으로 생각할 수 있다.

''q'' = 2 또는 ''q'' = 3인 경우, 부호는 각각 '''이진 부호''' 또는 '''삼진 부호'''로 불린다.

$\mathbb{F}_q^n$ 에 표준 기저를 부여하고자 한다. 이는 각 좌표가 작은 전송 오류 확률(이진 대칭 채널)로 "잡음 채널"을 통해 전송되는 "비트"를 나타내기 때문이다. 다른 기저가 사용되면 이 모델을 사용할 수 없으며, 해밍 거리는 전송 중 오류 수를 측정하지 못한다.

2. 1. 선형 부호

유한체

\mathbb F_q

위의

n

차원 벡터 공간

\mathbb F_q^n

속의

k

차원

\mathbb F_q

-부분 벡터 공간을 의미하며, 블록 부호로 생각할 수 있다.^[10]

선형 부호

C

의 원소는 '''부호어'''(符號語, codeword^영어)라고 한다.

C

위에 해밍 거리를 부여하면, 이는 거리 공간을 이룬다. 해밍 거리는

\operatorname{d_H}(-,-)

로 표기한다.

선형 부호

C

의 '''최소 거리'''(最小距離, minimum distance^영어)

d

는 그 부호어 가운데 0이 아닌 것의 최소 해밍 무게이다. 이는

C

의 서로 다른 두 원소 사이의 거리의 최솟값과 같다.

:

d=\min_{c\in C}\operatorname{d_H}(c,0)=\min_{c,c'\in C,\;c\ne c'}\operatorname{d_H}(c,c')

최소 거리

d

의, 길이

n

의,

k

차원

q

진 선형 부호를 '''

[n,k,d]_q

-선형 부호'''라고 표기한다. (

q=2

인 경우

q

가 흔히 생략된다.)

길이 ''n''과 차원 ''k''를 갖는 선형 부호는

\mathbb{F}_q

가 ''q''개의 원소를 갖는 유한체일 때, 벡터 공간

\mathbb{F}_q^n

의 차원이 ''k''인 선형 부분 공간 ''C''이다. 이러한 부호를 ''q''진 부호라고 하며, ''q'' = 2 또는 ''q'' = 3인 경우, 부호는 각각 '''이진 부호''' 또는 '''삼진 부호'''로 불린다.

\mathbb{F}_q^n

의 선형 부분 공간으로서, 전체 코드 ''C''는

k

개의 코드워드 집합의 스팬으로 나타낼 수 있다(선형대수에서 기저로 알려져 있음). 이 기저 코드워드는 코드 ''C''에 대한 '''생성 행렬'''로 알려진 행렬 G의 행에 종종 수집된다. G가 블록 행렬 형태

\boldsymbol{G} = [I_k \mid P]

를 가질 때, 여기서

I_k

는

k \times k

항등 행렬을 나타내고 P는 어떤

k \times (n-k)

행렬을 나타내며, G가 '''표준 형식'''이라고 한다.

선형 함수

\phi : \mathbb{F}_q^n\to \mathbb{F}_q^{n-k}

를 나타내는 행렬 ''H''는 그 커널이 ''C''인 경우, ''C''의 '''검사 행렬'''(또는 때로는 패리티 검사 행렬)이라고 한다. ''C''가 표준 형식의 생성 행렬 ''G''를 갖는 코드인 경우,

\boldsymbol{G} = [I_k \mid P]

이면,

\boldsymbol{H} = [-P^T \mid I_{n-k} ]

는 C에 대한 검사 행렬이다. ''H''에 의해 생성된 코드는 C의 '''쌍대 코드'''라고 한다. G는

k \times n

행렬이고, H는

(n-k) \times n

행렬이다.

선형성은 코드워드 ''c''₀와 다른 코드워드 ''c'' ≠ ''c''₀ 사이의 최소 해밍 거리 ''d''가 ''c''₀에 독립적임을 보장한다.

''k'' = dim_''F'' ''C''일 때, 선형 부호 ''C''를 (''n'', ''k'') 선형 부호라고 한다.^[10] ''k''차원 부분 공간 ''C''는 그 기저 ''g''₁, …, ''g''_''k'' ∈ ''Fⁿ''를 지정하면 정해진다. 이들을 나열한 ''k''×''n'' 행렬 ''G'' = (''g''₁^''t'', …, ''g''_''k''^''t'')^''t''를 선형 부호 ''C''의 '''생성 행렬'''이라고 한다.

:

C = \{\, xG \mid x \in F^k \,\}

''k''차원 부분 공간 ''C''는 연립 일차 방정식으로 지정해도 정해진다.

:

C = \{\, y \in F^n \mid yH^t = 0 \,\}

가 되는 (''n'' − ''k'')×''n'' 행렬 ''H''를 선형 부호 ''C''의 '''패리티 검사 행렬'''이라고 한다. 정의로부터 ''GH^t'' = 0이 성립한다. 이들 행렬은 적절하게 선형 부호 ''C''의 기저를 다시 선택함으로써,

:

G = (I | P), \quad H = (-P^t | I)

형태로 만들 수 있다. 이러한 ''G'', ''H''를 '''조직 부호 형식'''이라고 한다.

2. 2. 생성 행렬과 패리티 확인 행렬

[n,k,d]_q

-선형 부호

C\subseteq\mathbb F_q^n

의 '''생성 행렬'''(生成行列, generator matrix^영어)은

C

를 선형 생성하는

k

개의 열벡터로 구성된

n\times k

행렬이며, 흔히

G

로 표기된다. 전체 코드 C는

k

개 코드워드 집합의 스팬으로 나타낼 수 있다.

[n,k,d]_q

-선형 부호

C\subseteq\mathbb F_q^n

의 '''패리티 확인 행렬'''(parity check matrix^영어)은

C=\ker H

를 만족하는

n-k\times n

행렬이다. 즉,

H

의 열벡터는

C^\perp

를 선형 생성하며, 주로

H

로 표기된다.^[10]

만약

H

가

H=(B_{n-k\times k}|1_{n-k\times n-k})

꼴이면,

H

를 '''표준형 패리티 확인 행렬'''(標準型parity確認行列, standard-form parity check matrix^영어)이라고 한다. 모든 선형 부호는 표준형 패리티 확인 행렬을 갖는다.

\boldsymbol{G} = [I_k \mid P]

형태일 때 (여기서

I_k

는

k \times k

항등 행렬, P는

k \times (n-k)

행렬), G는 '''표준 형식'''이다.

''H''로 생성된 코드는 C의 '''쌍대 코드'''이다. G는

k \times n

행렬, H는

(n-k) \times n

행렬이다.

선형 코드 ''C''의 거리 ''d''는 검사 행렬 ''H''에서 선형 종속적인 열의 최소 개수와 같다.

다음은 2원체

\mathbb{F}_2

위 (7, 4) 선형 부호의 예이다.

:

G = \begin{pmatrix}1 & 0 & 0 & 0 & 0 & 1 & 1 \\0 & 1 & 0 & 0 & 1 & 0 & 1 \\0 & 0 & 1 & 0 & 1 & 1 & 0 \\0 & 0 & 0 & 1 & 1 & 1 & 1\end{pmatrix},\quadH = \begin{pmatrix}0 & 1 & 1 & 1 & 1 & 0 & 0 \\1 & 0 & 1 & 1 & 0 & 1 & 0 \\1 & 1 & 0 & 1 & 0 & 0 & 1\end{pmatrix}

(7, 4) 선형 부호 ''C''의 신드롬 표
코셋 리더 v	신드롬 vH^t
(0, 0, 0, 0, 0, 0, 0)	(0, 0, 0)
(1, 0, 0, 0, 0, 0, 0)	(0, 1, 1)
(0, 1, 0, 0, 0, 0, 0)	(1, 0, 1)
(0, 0, 1, 0, 0, 0, 0)	(1, 1, 0)
(0, 0, 0, 1, 0, 0, 0)	(1, 1, 1)
(0, 0, 0, 0, 1, 0, 0)	(1, 0, 0)
(0, 0, 0, 0, 0, 1, 0)	(0, 1, 0)
(0, 0, 0, 0, 0, 0, 1)	(0, 0, 1)

3. 선형 부호의 연산

선형 부호는 쌍대 선형 부호 연산을 할 수 있다.

3. 1. 쌍대 선형 부호

:

C\subseteq\mathbb F_q^n

의 직교 여공간

:

C^\perp =\{v\in \mathbb F_q^n\colon \langle u,v\rangle=0\qquad\forall u\in C\}

을

C

의 '''쌍대 선형 부호'''(dual linear code^영어)라고 한다. 만약

C

가

[n,k,d]_q

-선형 부호라면,

C^\perp

은

[n,n-k,d']_q

-선형 부호이다. 일반적으로

d'

은

(n,k,d,q)

로부터 결정되지 않는다.

'''예:'''

:

\operatorname{Span}_{\mathbb F_2}\{(1,0,0),(0,1,0)\}

:

\operatorname{Span}_{\mathbb F_2}\{(1,0,0),(0,1,1)\}

은 둘 다 [3,2,1]₂-선형 부호이지만, 그 쌍대 선형 부호

:

(\operatorname{Span}_{\mathbb F_2}\{(1,0,0),(0,1,0)\})^\perp=\operatorname{Span}_{\mathbb F_2}\{(0,0,1)\}

:

(\operatorname{Span}_{\mathbb F_2}\{(1,0,0),(0,1,1)\})^\perp=\operatorname{Span}_{\mathbb F_2}\{(0,1,1)\}

는 각각 [3,1,1]₂-선형 부호 및 [3,1,2]₂-선형 부호이다.

선형 함수

\phi : \mathbb{F}_q^n\to \mathbb{F}_q^{n-k}

를 나타내는 행렬 ''H''가 ''C''의 검사 행렬(패리티 검사 행렬)이 되려면, ''H''의 커널이 ''C''이어야 한다. 동등하게, ''H''는 그 영 공간이 ''C''인 행렬이다. ''C''가 표준 형식의 생성 행렬 ''G'' = [

I_k \mid P

]를 갖는 코드이면,

\boldsymbol{H} = [-P^T \mid I_{n-k} ]

는 ''C''의 검사 행렬이다. ''H''로 생성된 코드는 ''C''의 쌍대 코드이다. ''G''는

k \times n

행렬이고, ''H''는

(n-k) \times n

행렬이다.^[1]

4. 선형 부호의 종류

선형 부호는 다양한 종류가 있으며, 각각 다른 특징과 응용 분야를 가진다. 주요 선형 부호는 다음과 같다.

자명한 부호: 가장 기본적인 선형 부호로, 오류 정정 및 발견 능력이 없어 실제 데이터 전송에는 사용되지 않는다.
해밍 부호: 오류 정정을 위해 개발된 최초의 선형 부호 중 하나로, 1비트 오류를 정정할 수 있다. 디지털 통신 시스템에서 널리 사용된다.
아다마르 부호: 많은 오류를 정정할 수 있는 선형 부호이다. 리드-뮬러 부호의 특수한 경우이며, 해밍 부호와 쌍대 관계를 가지는 심플렉스 부호를 얻을 수 있다.
골레 부호: 이진 골레 부호와 삼진 골레 부호가 있으며, 마티외 군의 군론적 성질을 사용하여 구성된다.

이 외에도 다음과 같은 다양한 선형 부호들이 존재한다.

반복 부호
패리티 부호
순회 부호
BCH 부호
리드-솔로몬 부호
리드-뮬러 부호
대수 기하 부호
이진 고파 부호
저밀도 패리티 검사 부호
익스팬더 부호
다차원 패리티 검사 부호
토릭 부호
터보 부호
지역 복구 부호

4. 1. 자명한 부호

임의의 소수 거듭제곱

q

및 두 양의 정수

1\le k\le n

에 대하여, 자명한 선형 부호

:

C=\{(a_1,a_2,\dotsc,a_k,0,0,\dotsc,0)\}\subseteq\mathbb F_q^n

를 정의할 수 있다. 이는

[n,k,1]_q

-선형 부호이다. 즉, 이 자명한 선형 부호는 각 부호어마다

0개의 오류를 교정할 수 있으며,
0개의 오류를 발견할 수 있다.

다시 말해, 이 자명한 부호는 실제 데이터의 송신에는 쓸모가 없다.

4. 2. 해밍 부호

임의의 2 이상의 정수

r

에 대하여,

r

-이진 해밍 부호는

[2^r-1,2^r-r-1,3]_2

-선형 부호이다. 예를 들어,

r=2

일 때 2-이진 해밍 부호는 [3,1,3]₂-선형 부호이며, 3-이진 해밍 부호는 [7,4,3]₂-선형 부호이다.

최소 해밍 무게가 3이므로, 이진 해밍 부호는 각 부호어마다

1개 이하의 오류를 교정할 수 있으며,
2개 이하의 오류를 발견할 수 있다.

2-이진 해밍 부호는 최대 거리 분리 선형 부호이지만,

r\ge3

일 경우

r

-이진 해밍 부호는 최대 거리 분리 선형 부호가 아니다.

오류 정정 목적으로 개발된 최초의 선형 부호인 해밍 부호는 디지털 통신 시스템에서 널리 사용되어 왔다. 임의의 양의 정수

r \ge 2

에 대해

[2^r-1, 2^r-r-1,3]_2

해밍 부호가 존재한다.

d=3

이므로, 이 해밍 부호는 1비트 오류를 정정할 수 있다.

'''예시:''' 다음 생성 행렬과 패리티 검사 행렬을 갖는 선형 블록 부호는

[7,4,3]_2

해밍 부호이다.

:

\boldsymbol{G}=\begin{pmatrix} 1& 0& 0& 0& 1& 1& 0 \\ 0& 1& 0& 0& 0& 1& 1 \\ 0& 0& 1& 0& 1& 1& 1 \\ 0& 0& 0& 1& 1& 0& 1 \end{pmatrix}   ,

\boldsymbol{H}=\begin{pmatrix} 1& 0& 1& 1& 1& 0& 0 \\ 1& 1&\ 1& 0& 0& 1& 0 \\ 0& 1& 1& 1& 0& 0& 1  \end{pmatrix}

4. 3. 아다마르 부호

정수

r

에 대하여, '''아다마르 부호'''(Hadamard code^영어)는

[2^r,r,2^{r-1}]_2

-선형 부호이다. 예를 들어,

r=1

일 때 1-아다마르 부호는 [2,1,1]₂-선형 부호이며, 2-아다마르 부호는 [4,2,2]₂-선형 부호이고, 3-아다마르 부호는 [8,2,4]₂-선형 부호이다.^[1]

하드마르 코드는

[2^r, r, 2^{r-1}]_2

선형 부호이며, 많은 오류를 정정할 수 있다. 하드마르 코드는 열 단위로 구성될 수 있는데,

i^{th}

열은 정수

i

의 이진수 표현의 비트이다. 하드마르 코드는 최소 거리

2^{r-1}

를 가지므로

2^{r-2}-1

개의 오류를 정정할 수 있다.^[1]

'''예시:''' 다음 생성 행렬을 갖는 선형 블록 코드는

[8,3,4]_2

하드마르 코드이다.^[1]

\boldsymbol{G}_\mathrm{Had}=\begin{pmatrix} 0& 0& 0& 0& 1&\ 1&1& 1\\ 0& 0& 1& 1& 0& 0& 1& 1\\ 0& 1& 0& 1& 0& 1& 0& 1\end{pmatrix}

하드마르 코드는 리드-뮬러 부호의 특수한 경우이다.

\boldsymbol{G}_\mathrm{Had}

에서 첫 번째 열(모두 0인 열)을 제거하면

[7,3,4]_2

''단순 코드''를 얻게 되는데, 이는 해밍 부호의 ''쌍대 코드''이다.^[1]

4. 4. 골레 부호

이진 골레 부호는 [24,12,8]₂-선형 부호이며, 삼진 골레 부호는 [12,6,6]₃-선형 부호이다. 이들은 마티외 군의 군론적 성질을 사용하여 구성된다.

4. 5. 기타 선형 부호

반복 부호
패리티 부호
순회 부호
BCH 부호
리드-솔로몬 부호
리드-뮬러 부호
대수 기하 부호
이진 고파 부호
저밀도 패리티 검사 부호
익스팬더 부호
다차원 패리티 검사 부호
토릭 부호
터보 부호
지역 복구 부호

5. 선형 부호의 응용: 데이터 전송

선형 부호는 데이터 전송 과정에서 오류를 검출하고 정정하는 데 사용된다. 이진 해밍 부호를 사용한 데이터 전송은 다음과 같다. 먼저, 생성 행렬을 사용하여 데이터를 부호화한다. 전송 중 오류 발생 여부를 확인하기 위해 패리티 확인 행렬을 사용한다. 오류가 없다면 패리티 확인 행렬과 수신된 데이터의 곱은 0벡터가 된다. 1비트 오류가 발생한 경우, 이 곱을 통해 오류 발생 위치를 알 수 있다.

2진 선형 부호는 전자 기기나 기억 매체 등에서 널리 사용된다. 콤팩트 디스크에는 리드-솔로몬 부호가 사용되며, 10자리 ISBN도 선형 부호의 일종이다.

5. 1. 데이터 부호화

데이터

p=\begin{pmatrix}1\\0\\1\\1\end{pmatrix}

를

r=3

이진 해밍 부호로 전송하는 경우를 살펴보자.

r=3

이진 해밍 부호의 생성 행렬은 다음과 같다.

:

G = \begin{pmatrix}1 & 0 & 0 & 0 \\0 & 1 & 0 & 0 \\0 & 0 & 1 & 0 \\0 & 0 & 0 & 1 \\0 & 1 & 1 & 1 \\1 & 0 & 1 & 1 \\1 & 1 & 0 & 1 \\\end{pmatrix}

이 생성 행렬을 이용하여 데이터를 부호화하면 다음과 같다.

:

x=Gp = \begin{pmatrix}1 & 0 & 0 & 0 \\0 & 1 & 0 & 0 \\0 & 0 & 1 & 0 \\0 & 0 & 0 & 1 \\0 & 1 & 1 & 1 \\1 & 0 & 1 & 1 \\1 & 1 & 0 & 1 \\\end{pmatrix}\begin{pmatrix} 1 \\ 0 \\ 1 \\ 1 \end{pmatrix}=\begin{pmatrix} 1 \\ 0 \\ 1 \\ 1 \\ 0 \\ 1 \\ 0 \end{pmatrix}

\mathbb{F}_q^n

의 선형 부분 공간인 전체 코드 ''C''는

k

개 코드워드 집합의 스팬(선형대수에서 기저라고 함)으로 나타낼 수 있다. 이 기저 코드워드는 '''생성 행렬''' ''G''의 행에 모인다. ''G''가

\boldsymbol{G} = [I_k \mid P]

형태(

I_k

는

k \times k

항등 행렬, P는

k \times (n-k)

행렬)를 가지면, ''G''는 '''표준 형식'''이라고 한다.

5. 2. 오류 검출 및 정정

선형 부호에서 오류 검출은 패리티 검사 행렬을 사용하여 수행된다. 수신된 데이터에 패리티 검사 행렬을 곱하여 결과가 0 벡터인지 확인한다. 0 벡터라면 오류가 없는 것이고, 그렇지 않다면 오류가 발생한 것이다.

1비트 오류가 발생한 경우, 패리티 검사 행렬을 곱한 결과는 오류가 발생한 비트의 위치를 나타낸다. 예를 들어, 다음과 같이 주어진 벡터를 보자.

:

r=\begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 0 \\ 1 \\ 0 \end{pmatrix}

그리고 다음을 계산한다.

:

Hr = \begin{pmatrix}0 & 0 & 0 & 1 & 1 & 1 & 1 \\0 & 1 & 1 & 0 & 0 & 1 & 1 \\1 & 0 & 1 & 0 & 1 & 0 & 1 \\\end{pmatrix}\begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 0 \\ 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix}

위의 결과에 따라서, 둘째 비트에서 오류가 발생했음을 알 수 있다.

신드롬 복호는 수신된 벡터의 신드롬을 계산하고, 신드롬 표를 이용하여 해당 신드롬에 대응하는 코셋 리더를 찾아 오류를 정정하는 방법이다.

선형 코드 ''C''의 거리 ''d''는 검사 행렬 ''H''의 선형적으로 종속적인 열의 최소 개수와 같다.

하드마르 코드는

[2^r, r, 2^{r-1}]_2

선형 부호이며, 많은 오류를 정정할 수 있다. 최소 거리

2^{r-1}

를 가지므로

2^{r-2}-1

개의 오류를 정정할 수 있다.

'''예시:''' 다음 생성 행렬을 갖는 선형 블록 코드는

[8,3,4]_2

하드마르 코드이다.

:

\boldsymbol{G}_\mathrm{Had}=\begin{pmatrix} 0& 0& 0& 0& 1&\ 1&1& 1\\ 0& 0& 1& 1& 0& 0& 1& 1\\ 0& 1& 0& 1& 0& 1& 0& 1\end{pmatrix}

.

이는 리드-뮬러 코드의 특수한 경우로,

\boldsymbol{G}_\mathrm{Had}

에서 첫 번째 열(모두 0인 열)을 제거하면

[7,3,4]_2

''단순 코드''를 얻게 되는데, 이는 해밍 부호의 ''쌍대 코드''이다.

최근접 이웃 디코딩 알고리즘은 수신된 벡터를 중심으로 하는 반경을 점차 늘려가며 가장 가까운 부호어를 찾는 방식으로 오류를 정정한다.

5. 2. 1. 오류 없음의 확인

데이터

:

x=\begin{pmatrix} 1 \\ 0 \\ 1 \\ 1 \\ 0 \\ 1 \\ 0 \end{pmatrix}

를 수신하였다고 가정했을 때, 이 데이터가 오류 없이 수신되었는지 확인하기 위해 패리티 확인 행렬을 사용한다. 다음을 계산하여 확인한다.

:

Hx = \begin{pmatrix}0 & 1 & 1 & 1 & 1 & 0 & 0 \\1 & 0 & 1 & 1 & 0 & 1 & 0 \\1 & 1 & 0 & 1 & 0 & 0 & 1  \\\end{pmatrix}\begin{pmatrix} 1 \\ 0 \\ 1 \\ 1 \\ 0 \\ 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}

이 값이 0이므로 오류가 발생하지 않았음을 알 수 있다.

5. 2. 2. 오류의 교정

해밍 부호는 전송 과정에서 발생한 1비트 오류를 정정할 수 있는 선형 부호이다. 디지털 통신 시스템에서 널리 사용되어 왔으며, 임의의 양의 정수

r \ge 2

에 대해

[2^r-1, 2^r-r-1,3]_2

해밍 부호가 존재한다.

d=3

이므로, 이 해밍 부호는 1비트 오류를 정정할 수 있다.

'''예시:''' 다음 생성 행렬과 패리티 검사 행렬을 갖는 선형 블록 부호는

[7,4,3]_2

해밍 부호이다.

:

\boldsymbol{G}=\begin{pmatrix} 1& 0& 0& 0& 1& 1& 0 \\ 0& 1& 0& 0& 0& 1& 1 \\ 0& 0& 1& 0& 1& 1& 1 \\ 0& 0& 0& 1& 1& 0& 1 \end{pmatrix}   ,

\boldsymbol{H}=\begin{pmatrix} 1& 0& 1& 1& 1& 0& 0 \\ 1& 1&\ 1& 0& 0& 1& 0 \\ 0& 1& 1& 1& 0& 0& 1  \end{pmatrix}

다음은 (7, 4) 선형 부호 ''C''의 신드롬 표 예시이다.

(7, 4) 선형 부호 ''C''의 신드롬 표
코셋 리더 v	신드롬 vH^t
(0, 0, 0, 0, 0, 0, 0)	(0, 0, 0)
(1, 0, 0, 0, 0, 0, 0)	(0, 1, 1)
(0, 1, 0, 0, 0, 0, 0)	(1, 0, 1)
(0, 0, 1, 0, 0, 0, 0)	(1, 1, 0)
(0, 0, 0, 1, 0, 0, 0)	(1, 1, 1)
(0, 0, 0, 0, 1, 0, 0)	(1, 0, 0)
(0, 0, 0, 0, 0, 1, 0)	(0, 1, 0)
(0, 0, 0, 0, 0, 0, 1)	(0, 0, 1)

예를 들어, 송신하고 싶은 정보 계열 ''x'' = (0, 1, 0, 1)는 ''xG'' = (0, 1, 0, 1, 0, 1, 0)으로 부호화된다. 여기서 부호어 ''xG'' 중 꼬리 부분의 (0, 1, 0)가 패리티 검사 기호이다. 통신 중에 맨 앞에서 오류가 발생하여 수신어가 ''y'' = (1, 1, 0, 1, 0, 1, 0)이 되었다면, 그 신드롬은 ''yH^t'' = (0, 1, 1)이다. 위의 신드롬 표에서 대응하는 코셋 리더 ''v'' = (1, 0, 0, 0, 0, 0, 0)을 찾아 ''xG'' = ''y'' - ''v''로 복호할 수 있다. 생성 행렬 ''G''는 조직 부호 형식이므로 원래의 정보 계열은 그 맨 앞 (0, 1, 0, 1)을 읽어 알 수 있다.

이 부호 ''C''는 1947년에 리처드 해밍에 의해 처음 발견된 오류 정정 부호 중 하나이다.

6. 신드롬 복호

(''n'', ''k'') 선형 부호를 ''C'', 그 패리티 검사 행렬을 ''H''라고 하자. 수신어 ''y'' ∈ ''Fⁿ''에 대해 ''yH^t''를 '''신드롬'''이라고 한다. 몫 공간 ''Fⁿ''/''C''의 완전 대표계 {''v''₁, …, ''v''_{''q''^{''n'' − ''k''}}}에서 각 ''v_i''가 잉여류 ''v_i'' + ''C'' 내에서 최소의 가중치를 가질 때, '''코셋 리더'''라고 한다. 이때 수신어 ''y'' ∈ ''Fⁿ''는 ''yH^t'' = ''vH^t''가 되는 코셋 리더 ''v''를 선택하면, 부호어 ''y'' − ''v'' ∈ ''C''로 복호화된다. 이것을 '''신드롬 복호'''라고 한다.

다음 행렬 ''G''를 생성 행렬, 또는 ''H''를 패리티 검사 행렬로 하는 2원체 $\mathbb{F}_2$ 위의 (7, 4) 선형 부호를 ''C''라고 한다.

: $G = \begin{pmatrix}1 & 0 & 0 & 0 & 0 & 1 & 1 \\0 & 1 & 0 & 0 & 1 & 0 & 1 \\0 & 0 & 1 & 0 & 1 & 1 & 0 \\0 & 0 & 0 & 1 & 1 & 1 & 1\end{pmatrix},\quadH = \begin{pmatrix}0 & 1 & 1 & 1 & 1 & 0 & 0 \\1 & 0 & 1 & 1 & 0 & 1 & 0 \\1 & 1 & 0 & 1 & 0 & 0 & 1\end{pmatrix}$

이때, 코셋 리더 ''v''와 그 신드롬 ''vH^t''는 다음과 같다.

(7, 4) 선형 부호 ''C''의 신드롬 표
코셋 리더 v	신드롬 vH^t
(0, 0, 0, 0, 0, 0, 0)	(0, 0, 0)
(1, 0, 0, 0, 0, 0, 0)	(0, 1, 1)
(0, 1, 0, 0, 0, 0, 0)	(1, 0, 1)
(0, 0, 1, 0, 0, 0, 0)	(1, 1, 0)
(0, 0, 0, 1, 0, 0, 0)	(1, 1, 1)
(0, 0, 0, 0, 1, 0, 0)	(1, 0, 0)
(0, 0, 0, 0, 0, 1, 0)	(0, 1, 0)
(0, 0, 0, 0, 0, 0, 1)	(0, 0, 1)

예를 들어, 송신하고 싶은 정보 계열을 ''x'' = (0, 1, 0, 1)로 하면 ''xG'' = (0, 1, 0, 1, 0, 1, 0)로 부호화된다. 여기서 부호어 ''xG'' 중 꼬리 부분의 (0, 1, 0)가 패리티 검사 기호이다. 통신 중에 맨 앞에서 오류가 발생하여 수신어가 ''y'' = (1, 1, 0, 1, 0, 1, 0)이 되었다고 하면, 그 신드롬은 ''yH^t'' = (0, 1, 1)이다. 그래서 위의 신드롬 표에서 대응하는 코셋 리더 ''v'' = (1, 0, 0, 0, 0, 0, 0)을 읽어냄으로써 ''xG'' = ''y'' - ''v''로 복호할 수 있다. 생성 행렬 ''G''는 조직 부호 형식이므로 원래의 정보 계열은 그 맨 앞 (0, 1, 0, 1)을 읽어냄으로써 알 수 있다. 이 부호 ''C''는 1947년에 리처드 해밍에 의해 처음 발견된 오류 정정 부호 중 하나이다.

7. 선형 부호의 특성

선형 부호는 벡터 공간의 부분 공간으로서, 여러 가지 중요한 특성을 가진다.

선형 부호에서 부호어의 '''가중치'''는 0이 아닌 원소의 수를 의미하고, 두 부호어 간의 '''거리'''는 해밍 거리로 측정된다. 즉, 두 부호어에서 서로 다른 원소의 개수가 거리이다. 선형 부호의 거리 ''d''는 0이 아닌 부호어의 최소 가중치와 같으며, 서로 다른 부호어 간의 최소 거리와도 같다. 이러한 [''n'',''k'',''d''] 부호에서 ''n''은 길이, ''k''는 차원, ''d''는 거리를 나타낸다.

선형 부호의 파라미터 ''d''는 오류 정정 능력과 밀접하게 관련되어 있다. $\mathbb{F}_q^n$ 에서 수신된 벡터 ''v''가 주어졌을 때, ''v''에 가장 가까운 부호어 ''w''를 찾는 과정을 통해 오류를 정정할 수 있다. 이 과정은 ''t'' 값을 증가시키면서 ''v''를 중심으로 하는 반경 ''t''의 공 안에 있는 모든 벡터 ''w''에 대해 ''w''가 부호어인지 확인하는 방식으로 진행된다. 만약 $t \le (d-1)/2$ 이면, 최대 하나의 부호어만이 해당 공 안에 존재하게 되어 오류를 정정할 수 있게 된다. 따라서 선형 부호는 $t < d/2$ 개의 오류를 정정할 수 있다.^[2]

선형 부호의 최소 해밍 거리 ''d''와 최소 해밍 무게 ''w''는 일치한다.^[2]

7. 1. 싱글톤 한계

모든 선형 [''n'',''k'',''d''] 부호 C는

k+d \leq n+1

을 만족한다. ''k'' +''d'' = ''n'' + 1을 만족하는 부호 ''C''는 '''최대 거리 분리'''(Maximum Distance Separable, MDS)라고 한다. 이러한 부호는 존재할 경우 어떤 면에서는 최상의 부호이다.

(''n'', ''k'') 선형 부호의 최소 거리 ''d''는 ''d'' ≤ ''n'' − ''k'' + 1 를 만족한다.^[1] 이를 싱글톤 한계식이라고 한다.^[1]

7. 2. 등거리 선형 부호

임의의 서로 다른 두 부호어 사이의 거리가 상수 ''d''인 경우, 해당 부호는 '''등거리'''라고 정의된다.^[4] 1984년 아리고 보니솔리(Arrigo Bonisoli)는 유한체에 대한 선형 단일 가중치 부호의 구조를 결정하고, 모든 등거리 선형 부호가 일련의 쌍대 부호 해밍 부호임을 증명했다.^[5]

8. 한국과 선형 부호

선형 부호 이론은 1950년 리처드 해밍이 해밍 부호를 발견하면서 시작되었다. 해밍은 1940년대 벨 연구소에서 릴레이 회로로 만들어진 컴퓨터인 벨 모델 V(Bell Model V^영어)를 이용해 작업을 했다. 이 컴퓨터는 천공 카드를 통해 자료를 입력받았는데, 이 때문에 오류가 발생할 가능성이 있었다. 주중에는 컴퓨터 관리자가 오류를 직접 수정할 수 있었지만, 주말에는 오류가 발생한 채 프로그램이 중단되고 다음 작업으로 넘어가는 일이 빈번했다.

해밍은 이러한 문제를 해결하기 위해 노력했고, 몇 년 동안 오류 수정 방법에 대해 연구하면서 효율적인 알고리즘을 개발하여 1950년에 해밍 부호를 발표했다.^[11]

이진 골레 부호는 마르셀 골레(Marcel Jules Édouard Golay^프랑스어)가 도입하였다. 아다마르 부호는 자크 아다마르의 이름을 따서 지어졌으며, 아다마르 행렬을 사용하여 구성된다.

10자리 ISBN ''a''₁ … ''a''₁₀은 (X = 10으로 간주) 11원체 상의 일차 방정식

: 1a₁ + 2a₂ + ⋯ + 10a₁₀ ≡ 0 (mod 11)

으로 정해지는 선형 부호이다.

8. 1. 역사

선형 부호 이론은 1950년에 해밍 부호의 발견으로부터 시작된다. 리처드 해밍은 1940년대 벨 연구소에서 벨 모델 V(Bell Model V^영어)라는 컴퓨터를 이용해서 작업을 했다. 이 컴퓨터는 릴레이 회로로 만들어졌으며 입력은 천공 카드를 이용했다. 천공 카드를 이용했으므로 컴퓨터에 입력되는 자료들은 필연적으로 오류의 가능성이 있었다. 주중에는 컴퓨터 관리자가 입력에 오류가 발생했다는 경고등이 켜지면 직접 수정할 수 있었으나, 관리자가 없는 주말에는 에러가 발생한 채 프로그램이 실행되지 않고 다음 작업으로 넘어가기 일쑤였다.

해밍은 이런 문제로 인해 여러 차례 고생한 후에, 이 문제를 근본적으로 해결하기 위해 노력했다. 그 후 몇 년 동안 오류를 수정하는 방법에 대해서 연구하면서 이와 관련된 여러가지의 효율적인 알고리즘을 만들어냈고 마침내 1950년에 해밍 부호를 발표했다.^[11]

이진 골레 부호는 마르셀 골레(Marcel Jules Édouard Golay^프랑스어)가 도입하였다. 아다마르 부호는 자크 아다마르의 이름을 땄으며, 그 구성에 아다마르 행렬이 등장하므로 이러한 이름이 붙었다.

8. 2. ISBN

10자리 ISBN ''a''₁ … ''a''₁₀은 (X = 10으로 간주하여) 11원체 상의 일차 방정식

: 1a₁ + 2a₂ + ⋯ + 10a₁₀ ≡ 0 (mod 11)

으로 정해지는 선형 부호이다.

참조

_[1] 서적 Channel Codes: Classical and Modern https://archive.org/[...] Cambridge University Press
_[2] 서적 Information Theory, Inference, and Learning Algorithms http://www.inference[...] Cambridge University Press
_[3] 서적 Elements of Information Theory https://archive.org/[...] John Wiley & Sons, Inc
_[4] arXiv Equidistant codes in the Grassmannian
_[5] 간행물 Every equidistant linear code is a sequence of dual Hamming codes
_[6] 서적 Gröbner Bases, Coding, and Cryptography Springer Science & Business Media
_[7] 웹사이트 Encyclopedia of Mathematics https://www.encyclop[...]
_[8] 서적 Introduction to Coding Theory https://archive.org/[...] Springer
_[9] 서적 Noncommutative Rings and Their Applications American Mathematical Soc.
_[10] 문서 (''n'', ''k'', ''d'') 線型符号ということもある。ここで ''d'' は最小[[ハミング距離|距離]]を表す。なお、長さ ''n''、サイズ ''r''、最小距離 ''d'' の非線型符号を [''n'', ''r'', ''d''] と表記することもあるが、これと混同しないよう注意が必要である。
_[11] 저널 Error detecting and error correcting codes 1950-04

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

문의하기 : help@durumis.com