블록 부호

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

1. 개요

블록 부호는 데이터를 고정된 크기의 블록으로 나누어 처리하는 부호화 방식이다. 신뢰할 수 없는 통신 채널을 통해 디지털 데이터를 신뢰성 있게 전송하는 데 사용되며, 오류 정정 부호의 한 종류이다. 블록 부호는 메시지를 부호어(블록)로 인코딩하고, 수신자는 손상된 블록에서 원래 메시지를 복구하기 위해 디코딩 메커니즘을 사용한다. 블록 부호는 알파벳으로 구성된 문자열을 부호화하며, 해밍 결합 도식과 일반 결합 도식에서 정의된다. 블록 부호의 성질로는 오류 감지 및 수정 능력이 있으며, 전송률, 최소 거리, 상대 거리 등의 개념을 사용해 설명한다. 대표적인 예시로는 해밍 부호, 리드-솔로몬 부호 등이 있으며, 싱글턴 상계, 해밍 상계, 맥윌리엄스 부등식 등의 수학적 개념과 관련이 있다.

블록 부호

개요

종류	오류 정정 코드
속성	선형 비선형

특징

부호화 방법	고정 길이 블록
복호화 방법	다양한 알고리즘 사용 가능
주요 응용	데이터 저장 통신 시스템

성능 지표

부호율	정보 비트 수 / 전체 비트 수
최소 거리	오류 정정 능력 측정

종류

선형 블록 부호	해밍 부호 리드-솔로몬 부호 이진 골레이 부호 순환 부호
비선형 블록 부호	헤딩 부호

📚 더 읽어볼만한 페이지

부호 이론 - 해밍 거리
해밍 거리는 길이가 같은 두 문자열에서 서로 다른 기호의 개수를 나타내는 거리 척도로, 아벨 군에서는 벡터의 해밍 무게를 영벡터와의 해밍 거리로 정의하며, 오류 검출, 수정 부호 이론, 정보 이론, 계통학 등에서 활용된다.
부호 이론 - 선형 부호
선형 부호는 유한체 위의 벡터 공간의 부분 공간으로, 데이터 전송 및 오류 정정을 위해 사용되며, 길이, 차원, 최소 거리에 따라 표기되고, 부호어, 생성 행렬, 패리티 검사 행렬 등의 개념을 갖는다.

1. 개요
2. 정의
- 2.1. 해밍 결합 도식 속의 블록 부호
- 2.2. 일반 결합 도식 속의 블록 부호
3. 성질
- 3.1. 블록 부호를 사용한 데이터의 전송
- 3.2. 블록 부호가 존재할 필요 조건
4. 예
5. 역사

2. 정의

블록 부호는 데이터를 고정된 크기의 블록으로 나누어 처리하는 부호화 방식이다.

블록 부호 $(\Sigma,n,k,C)$ 는 다음과 같이 구성된다.

* 알파벳(alphabet^영어) $\Sigma$ : 유한 집합이다.
* 블록 길이(block length^영어) $n$ : 양의 정수이다. $\Sigma^n$ 의 원소를 블록(block^영어)이라고 한다.
* 부호어(符號語, codeword^영어) $C$ : 부분 집합 $C\colon \Sigma^k\to\Sigma^n$ 의 원소인 블록이다.

블록 부호의 전송률(電送率, rate^영어)은 $R=\frac1n\log_{|\Sigma}/n$ 이며, 항상 $0\le R\le 1$ 이다. 블록 부호의 상대 길이(相對-, relative distance^영어)는 유리수 $\delta=d/n$ 이며, 1 이하의 양의 유리수이다.

$\Sigma^n$ 위에 해밍 거리를 정의하면, 이는 거리 공간을 이룬다. 블록 부호의 최소 거리(最小距離, minimum distance^영어)는 다음과 같다.

: $d=\min_{a,b\in\Sigma^k,\;a\ne b}\operatorname{d_H}(C(a),C(b))$

최소 거리가 $d$ 인 블록 부호는 $[n,\log_{\Sigma}|C|,d]_$

👆

좌우로 밀어서 보기

-블록 부호라고 불린다.

오류 정정 부호는 신뢰할 수 없는 통신 채널을 통해 채널 잡음에 노출된 디지털 데이터를 신뢰성 있게 전송하는 데 사용된다. 송신자는 긴 데이터 스트림을 고정된 크기의 조각(메시지)으로 나누고, 각 메시지를 블록 부호로 부호어(블록)로 인코딩하여 전송한다. 수신자는 이를 디코딩하여 원본 메시지를 복구한다.

블록 부호는 다음과 같은 단사 함수이다.

:

C:\Sigma^k \to \Sigma^n

여기서

\Sigma

는 유한하고 비어 있지 않은 집합이며,

k

와

n

은 정수이다.

2.1. 해밍 결합 도식 속의 블록 부호

결합 도식 $(X,\partial\colon X^2\to D)$ 와 $D$ 의 부분 집합 $E\subseteq D$ 가 주어졌을 때, $X$ 의 부분 집합 $C\subseteq X$ 가 다음 조건을 만족하면 $E$ -블록 부호라고 한다.

* 임의의 $x,y\in C$ 에 대하여, $\partial(x,y)\not\in E$

$X$ 속의 블록 부호는 $\varnothing$ -블록 부호를 의미한다.

만약 $X=\Sigma^n$ 이 $\Sigma$ 위의 $n$ 차원 해밍 결합 도식이면, $\partial=\operatorname{d_H}$ 는 해밍 거리가 되며, 이 경우 위의 기초적 정의로 귀결된다.

결합 도식 $X$ 속의 블록 부호 $C\subseteq X$ 에 대하여,

* $X$ 의 원소를 블록이라고 한다.
* $C$ 의 원소를 부호어라고 한다.
* $C$ 의 전송률은 $R=\ln C/\ln X$ 이다. 이는 $0\le R\le 1$ 인 실수이다.
* $X$ 의 이항 관계가 $(R_i\subseteq X^2)_{i\in I}$ 라고 할 때, $C$ 의 내부 분포(inner distribution^영어)는 다음과 같은 유리수열이다.
*: $\alpha_i=\frac$

👆

좌우로 밀어서 보기

👆

좌우로 밀어서 보기

특히,

:

\sum_i\alpha_i=|C|

가 성립한다.

만약 거리 함수의 공역

D

가 전순서 집합일 때, 마찬가지로 최소 거리

:

d=\min_{x,y\in C}\partial(x,y)

를 정의할 수 있다.

2.2. 일반 결합 도식 속의 블록 부호

결합 도식을 사용하여 블록 부호의 정의를 일반화할 수 있다.

다음과 같은 요소들이 주어졌다고 가정한다.

* 결합 도식 $(X,\partial\colon X^2\to D)$
* $D$ 의 부분 집합 $E\subseteq D$

이 경우, $X$ 의 부분 집합 $C\subseteq X$ 가 다음 조건을 만족하면, $E$ -블록 부호( $E$ -block code^영어)라고 한다.

* 임의의 $x,y\in C$ 에 대하여, $\partial(x,y)\not\in E$

$X$ 속의 블록 부호는 $\varnothing$ -블록 부호를 의미한다.

만약 $X=\Sigma^n$ 이 $\Sigma$ 위의 $n$ 차원 해밍 결합 도식일 경우, $\partial=\operatorname{d_H}$ 는 해밍 거리가 되며, 이 경우 위의 기초적 정의로 귀결된다.

결합 도식 $X$ 속의 블록 부호 $C\subseteq X$ 에 대하여, 다음과 같은 개념들이 정의된다.

* $X$ 의 원소: 블록
* $C$ 의 원소: 부호어
* $C$ 의 전송률: $R=\ln C/\ln X$ (단, $0\le R\le 1$ 인 실수)
* $X$ 의 이항 관계가 $(R_i\subseteq X^2)_{i\in I}$ 일 때, $C$ 의 내부 분포(inner distribution^영어)는 다음과 같은 유리수열이다.
* $\alpha_i=\frac$

👆

좌우로 밀어서 보기

👆

좌우로 밀어서 보기

* 특히, 다음이 성립한다.
*

\sum_i\alpha_i=|C|

만약 거리 함수의 공역

D

가 전순서 집합일 경우, 최소 거리는 다음과 같이 정의된다.

:

d=\min_{x,y\in C}\partial(x,y)

블록 부호는 알파벳

S

로 구성된 문자열을 부호화하는 것이다. 부호어는

S

내의 각 문자마다 존재한다.

(k_1,k_2,\ldots,k_m)

을

|S|

미만의 자연수의 나열이라고 하고,

S={s_1,s_2,\ldots,s_n}

라고 하자. 어떤 단어

W

의 철자가

W=s_{k_1}s_{k_2}\ldots s_{k_m}

일 때,

W

를 부호화한 것

C(W)

는 다음과 같다.

:

C(W) = C(s_{k_1})C(s_{k_2})\ldots C(s_{k_m})

3. 성질

블록 부호는 데이터 전송 중 발생하는 오류를 감지하고 정정하는 데 사용된다.

거리 또는 최소 거리는 블록 부호에서 서로 다른 두 개의 부호어가 서로 다른 위치의 최소 개수이며, 상대 거리 $\delta$ 는 $d/n$ 이다.

구체적으로, 수신된 단어 $c_1, c_2 \in \Sigma^n$ 에 대해 $\Delta(c_1, c_2)$ 는 $c_1$ 과 $c_2$ 사이의 해밍 거리를 나타내며, 이는 $c_1$ 과 $c_2$ 가 서로 다른 위치의 수이다. 부호 $C$ 의 최소 거리 $d$ 는 다음과 같이 정의된다.

: $d := \min_{m_1,m_2\in\Sigma^k\atop m_1\neq m_2} \Delta[C(m_1),C(m_2)]$ .

모든 부호는 단사 함수여야 하므로, 임의의 두 부호어는 적어도 한 위치에서 서로 다르다. 따라서 모든 부호의 거리는 최소 $1$ 이다. 또한, 거리는 선형 블록 부호의 최소 가중치와 같다.

: $\min_{m_1,m_2\in\Sigma^k\atop m_1\neq m_2} \Delta[C(m_1),C(m_2)] = \min_{m_1,m_2\in\Sigma^k\atop m_1\neq m_2} \Delta[\mathbf{0},C(m_2)-C(m_1)] = \min_{m\in\Sigma^k\atop m\neq\mathbf{0}} w[C(m)] = w_\min$ .

거리가 클수록 오류 정정 및 탐지가 더 많이 가능하다. 예를 들어, 전송된 부호어의 기호를 변경할 수 있지만 절대로 지우거나 추가하지 않는 오류만 고려하는 경우, 오류의 수는 전송된 부호어와 수신된 단어가 서로 다른 위치의 수이다. 거리 $d$ 를 가진 부호는 수신기가 최대 $d-1$ 개의 전송 오류를 감지할 수 있게 해준다. 왜냐하면 부호어의 $d-1$ 개 위치를 변경하는 것은 실수로 다른 부호어를 생성할 수 없기 때문이다. 또한, $(d-1)/2$ 개 이하의 전송 오류가 발생하면 수신기는 수신된 단어를 부호어로 고유하게 디코딩할 수 있다. 이는 모든 수신된 단어가 거리 $(d-1)/2$ 에서 최대 하나의 부호어를 갖기 때문이다. $(d-1)/2$ 개 이상의 전송 오류가 발생하면 수신기는 일반적으로 수신된 단어를 고유하게 디코딩할 수 없는데, 여러 가능한 부호어가 있을 수 있기 때문이다. 이 경우 리스트 디코딩을 사용하여 특정 반경 내의 모든 부호어 목록을 출력할 수 있다.

부호어 $c \in \Sigma^n$ 는 $n$ 차원 공간 $\Sigma^n$ 의 한 점으로 간주될 수 있으며, 부호 $\mathcal{C}$ 는 $\Sigma^n$ 의 부분 집합이다. 부호 $\mathcal{C}$ 가 거리 $d$ 를 갖는다는 것은 $\forall c\in \mathcal{C}$ 에 대해, $c$ 를 중심으로 하고 반경이 $d-1$ 인 해밍 볼 안에 다른 부호어가 없다는 것을 의미하며, 이는 $c$ 와의 해밍 거리가 $d-1$ 이하인 $n$ 차원 단어들의 집합으로 정의된다.

(최소) 거리 $d$ 를 갖는 부호 $\mathcal{C}$ 는 다음과 같은 속성을 가진다.

* $\mathcal{C}$ 는 $d-1$ 개의 오류를 감지할 수 있다. 부호어 $c$ 는 자신을 중심으로 하고 반경이 $d-1$ 인 해밍 볼 안의 유일한 부호어이기 때문에, $d-1$ 개 이하의 오류 패턴은 하나의 부호어를 다른 부호어로 변경할 수 없다. 수신기가 수신된 벡터가 $\mathcal{C}$ 의 부호어가 아님을 감지하면 오류가 감지된다(하지만 수정이 보장되지는 않음).
* $\mathcal{C}$ 는 $\textstyle\left\lfloor {{d-1} \over 2}\right\rfloor$ 개의 오류를 수정할 수 있다. 부호어 $c$ 는 자신을 중심으로 하고 반경이 $d-1$ 인 해밍 볼 안의 유일한 부호어이기 때문에, 서로 다른 두 부호어를 중심으로 하고 반경이 $\textstyle\left \lfloor {{d-1} \over 2}\right \rfloor$ 인 두 해밍 볼은 서로 겹치지 않는다. 따라서 오류 수정을 수신된 단어 $y$ 에 가장 가까운 부호어를 찾는 것으로 간주하면, 오류 수가 $\textstyle\left \lfloor {{d-1} \over 2}\right \rfloor$ 이하인 한, $y$ 를 중심으로 하고 반경이 $\textstyle\left \lfloor {{d-1} \over 2}\right \rfloor$ 인 해밍 볼 안에 부호어가 하나만 있으므로 모든 오류를 수정할 수 있다.
* $(d-1)/2$ 개 이상의 오류가 있는 경우 리스트 디코딩 또는 최대 가능성 디코딩을 사용할 수 있다.
* $\mathcal{C}$ 는 $d-1$ 개의 지우기를 수정할 수 있다. 지우기는 지워진 기호의 위치가 알려져 있다는 것을 의미한다. 수정은 $q$ 통과 디코딩으로 수행할 수 있다. $i$ 번째 통과에서는 지워진 위치가 $i$ 번째 기호로 채워지고 오류 수정이 수행된다. 오류 수가 $\textstyle\left \lfloor {{d-1} \over 2}\right \rfloor$ 이하인 통과가 하나 있어야 하므로 지우기를 수정할 수 있다.

효율(전송률)과 정정 능력의 트레이드 오프를 나타내는 지표로서, 부호어의 길이와 정정 능력(해밍 거리 $d$ 로 표시)을 고정했을 때의 최대 부호어 수가 사용된다. 부호어 길이 $n$ 과 해밍 거리 $d$ 인 경우의 최대 부호어 수를 A[n,d]로 표기한다.

2진 블록 부호 $C$ 의 부호어 수를 $A$ , 부호어 길이를 n이라고 할 때, $C$ 의 정보 전송률은 다음과 같이 정의된다.

: $\frac{\!log_{2}(A)}{n}$

부호어 중 k 비트가 독립 정보 비트인 경우, 정보 전송률은 $\frac{k}{n}$ 이다.

블록 부호는 구면 채움과 밀접하게 관련되어 있다. 2차원이라면 시각화하기 쉽다. 같은 동전을 여러 개 테이블에 놓고 평평하게 하면 벌집 모양의 육각형 패턴이 나타난다. 그러나 블록 부호의 차원은 더 높아서 쉽게 시각화할 수 없다. 부호 이론에서는 N차원 구 모델을 사용한다. 예를 들어 우주 공간에서의 통신에 사용된 고레이 부호는 24차원의 구면 채움에 기반하고 있다. 이진 부호의 경우, 이 차원은 앞서 언급한 부호어 길이와 같다.

3.1. 블록 부호를 사용한 데이터의 전송

오류 정정 부호는 잡음이 있는 통신 채널을 통해 데이터를 전송할 때 발생할 수 있는 오류를 정정하는 데 사용된다. 블록 부호는 데이터를 특정 길이의 블록(부호어)으로 나누어 전송하는 방식이다.

$[n,k,d]_q$ -블록 부호 $C\subseteq\Sigma^n$ 가 주어지고, $k$ 가 정수라고 가정하면, 임의의 전단사 함수
: $f\colon\Sigma^k\to C\subseteq \Sigma^c$
를 선택할 수 있다. 이를 부호화 함수라고 한다.

데이터를 전송할 때, 채널에 노이즈가 있으면 오류가 발생할 수 있다. 즉, 전송 중인 벡터 $v\in\Sigma^n$ 의 $n$ 개 성분 중 일부가 다른 값으로 바뀔 수 있다.

문자열 $v\in\Sigma^n$ 를 수신했을 때, 다음과 같은 알고리즘을 사용하여 데이터를 교정한다.

* 만약 $\min_{c\in C}\operatorname{d_H}(v,c) 라면, v 를 \operatorname{d_H}(v,f(c)) 인 유일한 원소 c\in\Sigma^k 로 교정한다.$
* 만약 $\min_{c\in C}\operatorname{d_H}(v,c)\ge d/2$ 라면, 데이터 교정은 실패한다.

이러한 방법을 통해,
* $n$ 개의 성분 가운데 $\lceil d/2-1\rceil$ 개 이하가 잘못되었다면, 수신된 데이터를 오류 없이 교정할 수 있다.
* $n$ 개의 성분 가운데 $d-1$ 개 이하가 잘못되었다면, 데이터 송신 중 오류 발생 여부를 항상 확인할 수 있다. (그러나 이 오류를 항상 교정할 수 있는 것은 아니다.)

3.2. 블록 부호가 존재할 필요 조건

모든 $[n,k,d]_q$ -블록 부호는 다음 두 조건을 만족시킨다.

: $k\le n+1-d$ (싱글턴 상계, Singleton bound^영어)
: $k\le n-\log_q\left(\sum_{i=0}^{\lfloor(d-1)/2\rfloor}\binom ni(q-1)^i\right)$ (해밍 상계, Hamming bound^영어)

싱글턴 상계를 포화시키는 (즉, $k+d=n+1$ 인) 블록 부호를 최대 거리 분리 부호(最大距離分離符號, maximum-distance-separable code^영어, 약자 MDS 부호)라고 한다.

해밍 상계를 포화시키는 블록 부호를 완전 부호(完全符號, perfect code^영어)라고 한다.

최소 거리가 $d$ 인 블록 부호 $C\subseteq\Sigma^n$ 가 주어졌다고 하자. 그렇다면, 모든 부호어에서 처음 $d-1$ 개의 성분들을 삭제하여 블록 부호
: $C'\subseteq\Sigma^{n-d+1}$
: $C'=\{(s_1,s_2,\dotsc,s_{n-d+1})\colon s\in C\}$
를 정의할 수 있다. 따라서,
: $|C|=|C'|\le q^{n-d+1}$
이다.

일반적으로, 임의의 결합 도식 $(X,\partial)$ 이 주어졌다고 하자. $X$ 의 복소수 계수 보스-메스너 대수는 복소수 반단순 대수이며, 그 최소 멱등원들을
: $E_0,E_1,\dotsc,E_p$
라고 하자. 여기서 $E_0=|X|^{-1}\mathsf J_$

👆

좌우로 밀어서 보기

이며,

\mathsf J_

👆

좌우로 밀어서 보기

는 모든 성분이 1인 행렬(아다마르 곱의 항등원)이다. 또한,
:

E_a=\sum_iQ_{ai}D_i

라고 하자 (

D_i

는 각 이항 관계

R_i\subseteq X^2

의 인접 행렬).

이제,

X

속의 블록 부호

C\subseteq X

가 주어졌다고 하고, 그 내부 분포
:

\alpha_i=\frac

👆

좌우로 밀어서 보기

👆

좌우로 밀어서 보기

를 생각하자. 그렇다면, 쌍대 내부 분포(雙對內部分布, dual inner distribution^영어)는 다음과 같은 수열이다.
:

\beta_a=\sum_iQ_{ai}\alpha_i

그렇다면, 다음과 같은 맥윌리엄스 부등식(MacWilliams不等式, MacWilliams inequality^영어)이 성립한다.
:

0\le\beta_a\le|C|\qquad\forall a

\sum_a\beta_a=|C|

각

E_a

는 멱등원이므로, 그 고윳값은 0 또는 1이다. 따라서, 임의의

x,y\in X

에 대하여,

\langle x|y\rangle=\delta_{xy}

이므로,
:

0\le\langle x|E_a|y\rangle\le 1\qquad\forall a

이다. (

\delta_{xy}

는 크로네커 델타이다.)

이에 따라,
:

\begin{aligned}\beta_a&=\sum_iQ_{ai}\alpha_i\\&=\frac1

👆

좌우로 밀어서 보기

\sum_iQ_{ai}|C^2\cap R_i|\\&=\frac1

👆

좌우로 밀어서 보기

\sum_{x,y\in C}\sum_iQ_{ai}\langle x|D_i|y\rangle\\&=\frac1

👆

좌우로 밀어서 보기

\sum_{x,y\in C}\langle x|E_a|y\rangle\end{aligned}
이므로,
:

0\le\beta_a\le |C|

\sum_a\beta_a=\frac1

👆

좌우로 밀어서 보기

\sum_{x,y\in C}\langle x|\left(\sum_aE_a\right)|y\rangle=\frac1

👆

좌우로 밀어서 보기

\sum_{x,y\in C}\langle x|y\rangle=|C|
이다.

4. 예

최초의 오류 정정 부호는 1950년 리처드 해밍이 개발한 해밍(7,4) 부호이다. 이 부호는 4비트 메시지를 3개의 패리티 비트를 추가하여 7비트 부호어로 변환하며, $[7,4,3]_2$ 부호로 표기할 수 있다.

리드-솔로몬 부호는 $d=n-k+1$ 이고 $q$ 가 소수 거듭제곱인 $[n,k,d]_q$ 부호의 일종이다. 랭크 오류 정정 부호는 $d \leq n-k+1$ 인 $[n,k,d]_q$ 부호의 일종이며, 아다마르 부호는 $n=2^{k-1}$ 이고 $d=2^{k-2}$ 인 $[n,k,d]_2$ 부호의 일종이다.

4.1. 자명한 부호

$n=k$ 이고 $C$ 가 순열인 경우, 최소 거리는 1이다. 즉, 이 부호는 최고의 송신률 $k/n=1$ 을 갖지만, 아무런 오류를 교정하지 못한다.

마찬가지로, 어떤 임의의 $\alpha\in\Sigma$ 에 대하여
: $C\colon (s_1,s_2,\dotsc,s_k)\mapsto (s_1,s_2,\dotsc,s_k,\underbrace{\alpha,\alpha,\dotsc,\alpha}^{n-k})$
를 생각하면, 그 효율은 $k/n$ 이지만, 이 부호 역시 최소 거리가 1이므로, 아무런 오류를 교정하지 못한다.

4.2. 반복 부호

반복 부호는 동일한 데이터를 여러 번 반복하여 전송하는 방식으로, 오류 정정 능력을 향상시키는 부호이다. 임의의 알파벳 $\Sigma$ ( $|\Sigma|=q$ )와 양의 정수 $k\in\mathbb Z^+$ 및 양의 정수 $m$ 에 대하여, $[mk,k,m]_q$ -블록 부호를 얻을 수 있다.

이는 다음과 같이 정의된다.
: $C\colon\Sigma^k\to\Sigma^{mk}$
: $C\colon (s_1,s_2,\dotsc,s_k)\mapsto (\underbrace{s_1,\dotsc,s_1}_m,\underbrace{s_2,\dotsc,s_2}_m,\dotsc,\underbrace{s_k,\dotsc,s_k}_m)$

이를 $m$ 중 반복 부호(m-tuple repetition code^영어)라고 한다. 특히, $(k,m,q)=(1,3,2)$ 일 경우 이는 $r=2$ 이진 해밍 부호와 같다.

2진 블록 부호 $C$ 의 부호어 수를 $A$ , 부호어 길이를 n이라고 할 때, $C$ 의 정보 전송률은 다음과 같이 정의된다.

: $\frac{\!log_{2}(A)}{n}$

부호어 중 k 비트가 독립 정보 비트인 경우, 정보 전송률은 다음과 같다.

: $\frac{\!log_{2}(2^k)}{n}=\frac{k}{n}$

4.3. 선형 부호

선형 부호는 유한체 Σ 위에서 정의되는 선형 변환 C:Σ^k→Σⁿ을 통해 부호어를 생성하는 부호이다.

선형 부호의 예로는 해밍 부호와 이진 골레 부호가 있다. 최초의 오류 정정 부호는 1950년 리처드 해밍이 개발한 해밍(7,4) 부호이다. 이 부호는 4비트 메시지를 3개의 패리티 비트를 추가하여 7비트 부호어로 변환하며, 선형 부호이자 거리가 3인 [7,4,3]₂ 부호이다.

리드-솔로몬 부호는 d = n - k + 1이고 q가 소수 거듭제곱인 [n,k,d]_q 부호이다. 랭크 오류 정정 부호는 d ≤ n-k+1 인 [n,k,d]_q 부호이며, 아다마르 부호는 n=2^k-1 이고 d=2^k-2인 [n,k,d]₂ 부호이다.

2진 블록 부호 C의 부호어 개수를 A, 부호어 길이를 n이라 할 때, 정보 전송률은 다음과 같이 정의된다.

: $\frac{\!log_{2}(A)}{n}$

만약 부호어 중 k 비트가 독립 정보 비트라면, 정보 전송률은 다음과 같다.

: $\frac{\!log_{2}(2^k)}{n}=\frac{k}{n}$

블록 부호는 구면 채움과 밀접하게 관련되어 있다. 2차원에서는 동전을 이용해 벌집 모양의 육각형 패턴을 만드는 것처럼 시각화할 수 있지만, 블록 부호는 더 높은 차원을 가지므로 시각화가 어렵다. 부호 이론에서는 N차원 구 모델을 사용하며, 예를 들어 우주 통신에 사용되는 고레이 부호는 24차원 구면 채움을 기반으로 한다. 이진 부호에서 이 차원은 부호어 길이와 같다.

5. 역사

리처드 해밍이 해밍 상계를 증명하였다. 1964년에 리처드 콜럼 싱글턴(Richard Collom Singleton^영어)이 싱글턴 상계를 증명하였다.

종류	오류 정정 코드
속성	선형 비선형

특징

부호화 방법	고정 길이 블록
복호화 방법	다양한 알고리즘 사용 가능
주요 응용	데이터 저장 통신 시스템

성능 지표

부호율	정보 비트 수 / 전체 비트 수
최소 거리	오류 정정 능력 측정

종류

선형 블록 부호	해밍 부호 리드-솔로몬 부호 이진 골레이 부호 순환 부호
비선형 블록 부호	헤딩 부호