블록부호(block code)

블록부호는 일반적으로 고정된 수의 비트를 갖는 단어의 집합으로 구성된다. 이러한 블록부호에 속하는 단어를 특별히 부호어(codeword)라고 칭한다. 아래 그림과 같이 고정된 수의 정보 비트와 패리티 비트를 갖는 블록형태를 갖는다.

n비트인 블록부호는 k비트의 정보비트와 n-k비트의 패리티 비트로 구성되며 이를 (n,k) 블록 부호라 칭한다.
(n,k) 블록부호인 경우 부호기에 입력되는 k 비트 정보에 n-k비트의 패리티가 추가되어 총 길이 n의 부호어가 된다. 이러한 과정을 부호화라고 부른다.

• (n,k) 블록부호의 k비트의 입력 정보어는 다음과 같이 표기한다.

  $m = (m_0,m_1,...,m_{k-1})$
  $m_i = 0$ 또는 1의 값을 가지며, $0\leq i\leq k-1$ 사이의 정수이다.

• 여기에 (n - k) 비트의 패리티가 더해진 경우에 블록 부호어는 다음과 같이 표기한다.

  $c = (c_0,c_1,...,c_{n-1}) = (p_0,p_1,...,p_{n-k-1}, m_0,m_1...,m_{k-1})$
  $c_i = 0$ 또는 1의 값을 가지며, $0\leq i \leq n-1$ 사이의 정수이다.

정보비트의 길이 k가 고정되고 부호어 길이 n이 길어지면 자연히 패리티 비트의 길이 n-k가 늘어나므로 오류 검출과 정정을 보다 더 잘할 수 있다.

이러한 부호어와 정보비트 길이 비율은 다음과 같은 부호율(code rate)로 정의한다.

$R = k/n$

부호율은 $0\leq R \leq1$ 사이의 값을 가진다.

송신 부호어에는 오류벡터 $e = (e_0, e_1,...,e_{n-1})$가 추가되어 수신되는데, 이러한 경우에 수신 부호어는 다음과 같은 수신 벡터로 표기된다.

$r(수신부호어) = c(송신부호어) + e(오류벡터)$
$= (c_0,c_1,...,c{n-1})+(e_0, e_1,...,e_{n-1})$
$= (c_0 + e_0, c_1 + e_1,...,c_{n-1} + e_{n-1})$
$=(r_0,r_1,...,r_{n-1})$

오류벡터에서 $e_i =1$이면 i번째 비트 위치에서 오류가 발생한 것을 나타내고, 그렇지 않으면 오류가 발생하지 않은 것을 나타낸다. 만약 수신단에서 오류가 발생한 위치와 값을 정확하게 추정할 수 있다면, 즉 오류벡터를 안다면, 원래의 정보를 정확히 추출할 수 있다.

수신단에서 추정한 오류벡터를 $e' = (e'_0, e'_1,...,e'_{n-1})$라고 하면, $c' = r - e' = r + e'$이다.
여기서 $r-e' = r + e'$인 이유는 이진 부호에서 1-1=0, 0-0=0, 1-0=1, 0-1=1이기 때문이다. 따라서 수신된 코드 $r$에서 오류벡터 $e'$를 빼거나 더하는 것은 동일한 결과(추정 송신 부호어 $c'$)를 가져온다.

(n,k)블록부호인 경우에 길이가 n인 $2^n$개의 부호 중에서 $2^k$개는 부호어로 사용되며, 나머지 $2^n - 2^k$개는 부호어로 사용되지 않는다. 이러한 사용되지 않은 부호가 있음으로 인하여 오류를 검출 및 정정할 수 있다.

해밍중, 해밍거리

해밍중(Hamming Weight)

길이가 n인 부호어 $c = (c_0,c_1,...,c_{n-1})$의 해밍중은 부호어 내의 영이 아닌 성분의 개수이며 $w(c)$로 표기한다.

c = (1110010) 부호어의 해밍중은 $w(c) = 4$이다.

해밍거리(Hamming Distance)

길이가 n인 부호어 $u = (u_0,u_1,...,u_{n-1})$와 $v = (v_0,v_1,...,v_{n-1})$ 사이의 해밍거리는 두 부호어의 대응 성분 중 서로 다른 성분 쌍의 개수이며, 다음과 같은 식으로 정의된다.

$d(u,v) = |\{ i|u_i \neq v_i, i = 0,1,...,n-1\}|$

여기서 $|\{⋅ \}|$은 해당 집합의 원소 개수를 나타내며, 위의 식에서는 u와 v 부호어의 서로 다른 비트 인덱스의 개수를 세는 것이다.
예를 들어 u = (11001100) 이고 v = (10101010)이라 할 때 서로 다른 비트 인덱스 i = 1, 2, 5, 6로 4이다.

• $d(u,v) \geq 0$이며, 등호는 u=v일 때 성립한다.
• $d(u,v) = d(v,u)$
• $d(u,v) + d(v,w) \geq d(u,w)$

최소거리(minimum distance)

선형부호 C에서 서로 다른 부호어 사이의 해밍거리 중에서 가장 작은 최소치를 최소거리라하며, $d_{min}$으로 표기한다.

패리티 검사부호

패리티 검사부호는 전체 비트에서 1의 개수가 짝수인지 홀수인지에 따라 짝수 및 홀수 패리티 검사부호로 나뉘어진다.

• 짝수 패리티 검사부호는 정보비트가 $m = (m_0, m_1,...,m_{n-1})$일 때, 부호어 $c = (m_0, m_1,...,m_{k-1},b)$의 마지막 비트를 $b = \displaystyle\sum_{i=0}^{k-1}{m_i}$로 만든다.

• 홀수 패리티 검사부호는 마지막 비트를 $b = \displaystyle\sum_{i=0}^{k-1}{m_i + 1}$로 만든다.

여기서 더하기는 이원가산(modulo-2 addition)을 의미한다.

• 짝수 패리티 검사부호인 경우에 수신 부호어의 모든 n비트를 이원가산한 결과가 짝수, 즉 0이면, 오류가 발생하지 않은 것으로 판단한다.
• 홀수 패리티 검사 부호인 경우에 수신 부호어의 모든 n비트를 이원가산한 결과가 홀수, 즉 1이면 오류가 발생하지 않은 것으로 판단한다.

단지 한 비트의 패리티 비트를 추가하여 오류를 검출할 수 있는 능력을 갖게 되는 것은 매우 의미있지만, 어느 위치에서 오류가 발생한지를 알 수 없고, 1개 이상의 오류가 발생한다면 정보를 잘못 복호할 수 있다.