Channel Coding (Block Codes)

error을 알아내는 것과 고치는 것은 다른 문제

Information Theory and Channel Coding

Shannon's noisy channel coding theorem

: 전송률 R이 채널 용량 C 이하일 때, 적절한 제어된 중복성을 추가하면 비트 오류율(BER)을 낮출 수 있음.

→ 채널의 용량을 초과하지 않는 범위 내에서 추가적인 데이터를 첨부하여
(= 중복을 추가하여) 데이터 전송 시 발생할 수 있는 오류를 감소시킬 수 있음.

오류 제어 코딩 (ECC)

: 중복성을 사용하여 채널의 오류를 탐지하고 수정

• 중복성을 추가하여 수신기가 이를 활용하여 오류를 탐지하고 수정
• 신호를 더 강하게 보내는 대신에, 데이터를 더 효율적으로 전송할 수 있도록 오류 제어를 하여 필요한 송신 전력 감소

Example

전화선을 통한 데이터 전송:
link bandwidth: 3 kHz
모뎀의 성능: 최대 3,600 bps(비트/초) 속도로 동작
오류 확률(q_e): 8×10^−4

목표 (Target):
데이터를 1,200 bps 속도로 전송
최대 출력 SNR은 13 dB, 이때의 오류 확률(P_e)은 10^−4

채널 용량(Channel Capacity)

Shannon의 공식:

SNR을 dB에서 선형 값으로 변환:

SNR=20
B = 3000 Hz (3 kHz)

오류 확률 (Error Probability)

코딩 없이, 오류 확률 q_e는 8×10^−4
→ Error Control Coding 필요

Repetition Code

: 각 비트를 여러 번 반복하여 전송하는 방법

• 전송된 비트를 수신할 때 다수결 원칙(majority-voting)을 사용해 원래의 데이터를 복원
: 수신된 코드워드에서 가장 많이 등장하는 비트를 선택하여 원래 데이터를 복원

• 잡음 때문에 일부 비트가 바뀌는 error가 발생할 수 있음

Repetition Code 적용했을 때의 오류 확률

비트 3개를 전송했을 때 :

q : 비트가 오류가 발생할 확률

채널 잡음의 영향

: 채널 잡음이 매우 클 때, P_e는 0.5로 수렴
→ 이런 경우에는 채널 코딩을 해도 신뢰성이 크게 개선되지 않으며, 결국 무작위 추측과 다를 바가 없음.

Channel Coding

: 데이터를 전송할 때 발생할 수 있는 오류를 수정하고 검출하기 위해 사용

블록 코드 (Block Code)

: 메모리가 없는 코드 (과거가 영향을 안 미침)

• 정보 시퀀스가 길이 k의 블록으로 나누어짐.
• 각 블록의 k개의 정보 비트가 길이 n의 코드 비트로 인코딩됨
• no memory from one block to another block
= 이전 블록의 정보가 다음 블록에 영향을 미치지 않음
= 각각의 블록은 독립적으로 인코딩됨

컨벌루션 코드 (Convolutional Code)

: 메모리가 있는 코드 (과거가 영향을 미침)

• 길이 k_0L의 시프트 레지스터(shift register)를 사용하여 데이터를 인코딩
• 정보 비트는 한 번에 k_0 비트씩 시프트 레지스터에 입력되고, 이후 n_0 개의 코드 비트가 생성됨
• 생성된 코드 비트가 최근 입력된 비트뿐만 아니라 이전의 여러 비트들에도 의존
→ 과거의 비트들이 현재의 출력에 영향을 미침

Block Codes

(n, k) block 코드

: 길이 n의 코드워드를 가지는 코드 집합, 총 M=2^k 개의 코드워드를 포함

k : information 비트의 수
n : 코드워드의 전체 길이
r : 검사 비트 (check bits)

→ n = r + k

선형성 (Linear Code)

선형 블록 코드라고 불리기 위해서는 :
두 코드워드 c_i 와 c_j가 있을 때, 이들의 합 c_i+c_j 도 항상 코드워드가 되어야 함.

Code Rate

= 전송 효율성(rate efficiency),
원래 정보 비트가 전체 코드워드에서 차지하는 비율 (k/n)

→ code rate이 높을수록 전송 효율이 좋지만 오류 검출 및 수정 능력은 줄어들고, code rate이 낮을수록 오류에 더 강하지만 전송 효율은 떨어짐.

행렬 표현 (Matrix Description)

코드워드 c:

메시지 비트 m:

블록 코드는 Generator Matrix (G)을 사용하여 생성

Generator Matrix (G) : 크기가 k×n인 행렬 = encoder

: 메시지 벡터 m와 생성 행렬 G를 곱하여 코드워드 c를 얻음.

Generator Matrix G의 구성

I_k : identity matrix로, 크기가 k인 정사각 행렬

• 단위 행렬 : 대각선 요소가 모두 1이고, 나머지는 0인 행렬,
정보 비트를 코드워드에 그대로 포함시키기 위한 역할.

P : parity matrix, information 비트를 바탕으로 parity bit를 생성하여 코드워드의 오류 검출 및 수정을 가능하게 함.

Block Codes - Systematic Codes

Systematic Codes

: 코드워드의 구조에서 첫 번째 k개의 요소에 원래 정보 비트가 그대로 존재하는 형태로 구성되는 코딩 방식 (원래 자기 코드 포함)

• 정보 비트와 검사 비트가 명확하게 구분되어 있어,
디코딩 과정도 더 빠르게 처리될 수 있음.
→ 코드의 구현이 용이하고, 오류 검출 및 수정 시 필요한 룩업 테이블 조회도 간단

• 모든 linear code가 동일한 성능을 가지는 systematic code로 변환될 수 있음.

Example: Hamming Code

: 데이터를 전송할 때 발생할 수 있는 단일 비트 오류를 검출하고 수정하기 위해 설계된 linear block code

Hamming code의 구조

: (n,k) linear block 코드

• 코드워드 길이 (n):

• 메시지 비트의 수 (k):

• parity check bits의 수 (r):

해밍 코드의 최소 거리 (d_min)

d_min = 3
: 두 코드워드를 서로 구분하려면 최소한 3개의 비트가 달라야 함.
= codewords의 hamming distance

(7, 4) Hamming code

: 길이 7비트의 코드워드를 만들기 위해 4비트의 메시지 비트를 사용

4 input bits → 7 output bits

• 생성 행렬 (G)

• 메시지 비트 (m)와 코드워드 생성 (c)

: 원래 메시지 비트(1, 1, 1, 1)와 생성된 패리티 비트(1, 1, 1)를 결합하여 생성된 7비트의 코드워드.

Parity Check Matrix

Parity check matrix H

: Generator Matrix (생성 행렬) G가 주어지면, 이 행렬과 대응하는 Parity Check Matrix H를 찾을 수 있음.

Parity check 행렬의 역할

: 코드워드가 올바르게 생성되었는지 검증하는 데 사용

Parity check 행렬의 형태

codeword 검증

: 수신된 코드워드 c와 parity check matrix H의 전치 행렬을 곱해서 결과가 0이 나오면, 그 코드워드는 오류 없이 전송된 것

Error Syndrome

수신된 코드워드 : r = c + e

c: 원래의 코드워드
e: 오류 벡터 (오류가 발생한 위치를 나타내는 벡터),
오류가 발생한 비트 위치에 1을 가지며, 오류가 없는 위치에는 0을 가짐.

ex)
원래 코드워드 :
c = [1,0,1,0]

수신된 코드워드 :
r = [1,1,0,0]

오류 벡터 :
e = [0,1,1,0]

Error Syndrome

: 수신된 코드워드가 올바른지 확인하고 오류가 발생한 경우 그 위치를 파악하기 위해 사용

r : 수신된 코드워드

Error Syndrome의 역할

• 신드롬 값이 0일 때 (s=0)
: r=c, 즉 수신된 코드워드가 원래의 코드워드와 동일
수신된 코드워드에서 앞의 k개 비트를 추출하여 메시지 비트 (m)로 사용할 수 있음.

• 신드롬 값이 0이 아닐 때 (s≠0)
: s가 H 전치행렬의 j번째 행과 같다면, 이는 수신된 코드워드의 j번째 위치에 오류가 있다는 것을 나타냄

Example: (7,4) Hamming Code

• 수신된 codeword r=[1,1,1,1,1,1,1] 일 경우 :

s=r $H^T$ =[0,0,0]
s=0이므로, 수신된 코드워드는 오류가 없음
message=[1,1,1,1] (k=4)

• 수신된 codeword r=[1,1,1,1,1,1,0] 일 경우 :

s=[0,0,1]은 $H^T$의 마지막 행과 동일하므로, 마지막 비트에서 오류가 발생했음을 의미.

Cyclic Codes

Cyclic code가 되기 위한 조건 :

코드워드가 순환적으로 한 칸씩 오른쪽으로 이동한,
새로운 코드워드 역시 원래 코드 집합에 포함되어야 함.

Cyclic Code의 특징

: 순환 이동(한 칸씩 shift)해도 여전히 유효한 코드워드
→ 효율적인 인코딩과 디코딩이 가능.

ex. (7,4) Hamming code is cyclic

Important Parameters

: 코드의 오류 검출 및 수정에 쓰이는 매개변수

해밍 거리 (Hamming Distance)

d($c _i$ ,$c_j$) : $c _i$와 $c_j$이 서로 다른 비트 위치의 개수

해밍 무게 (Hamming Weight)

w($c _i$) : 코드워드 $c _i$에서 0이 아닌 비트의 개수
→ 코드워드에서 1로 설정된 비트의 개수

최소 해밍 거리 (Minimum Hamming Distance)

d_min : 코드 집합에서 서로 다른 두 코드워드 간의 최소 해밍 거리

d_min = min d($c_i$ ,$c_j$) for all i ≠ j

✓ 코드의 오류 검출 및 수정 능력을 평가하는 데 중요한 매개변수
d_min 일때,

• 최대 d_min−1 개의 오류를 검출

: 코드워드 간의 최소 해밍 거리가 d_min이라면, 최소한 d_min개의 비트가 달라야 코드워드가 다른 유효한 코드워드로 변함.
→ d_min비트 미만의 오류는 기존의 코드워드와 어떤 유효한 코드워드와도 일치하지 않으므로, 이는 오류가 발생했음을 확실하게 검출할 수 있음.

• 최대 ⌊(d_min−1)/2⌋ 개의 오류를 수정

: 오류를 수정하기 위해서는 최소한의 거리보다 절반 이하의 오류가 발생해야 원래의 코드워드를 복원할 수 있음.

최소 무게 (Minimum Weight)

w_min : 코드 집합 내의 코드워드 중 해밍 무게를 계산한 후, 그중에서 가장 작은 값

w_min = min w($c_i$)for all $c_i$ ≠ 0

Theorem

선형 코드에서 모든 코드워드 간의 Minimum Hamming Distance와 Minimum Weight가 동일

Error Correction Capability

코드가 최소 해밍 거리 (d_min)를 가질 때,

오류 검출 능력

최대 d_min−1 개의 오류를 검출
코드워드 간의 거리가 최소 d_min이기 때문에, 최대 d_min−1개의 오류가 발생하더라도 다른 코드워드와 일치하지 않음을 보장할 수 있음.

오류 수정 능력 (t)

• 오류 수정 가능 영역
오류 수정 가능 범위 t : 코드워드를 중심으로 한 반경 t 내의 영역
→ 오류가 발생하더라도 r이 $c_i$ 로부터 t 이하의 거리에 있으면,
이를 원래 코드워드로 복원할 수 있음.

• 오류 수정 불가능한 경우

r이 $c _i$ ,$c_j$ 사이의 겹쳐진 영역에 위치하면, 어느 코드워드가 원래 코드워드였는지를 정확히 알 수 없기 때문에 수정이 불가능.

오류 검출의 조건

: 오류를 검출하려면 해밍 거리가
d_min ≥ e +1 이어야 함.

e개의 오류를 검출하려면 코드 간의 거리가 e보다 최소 1은 더 커야 함

오류 수정의 조건

: 오류를 수정하려면
해밍 거리가 d_min ≥ 2t + 1 이어야 함
(t = 수정할 수 있는 최대 오류의 개수)

Major Classes of Block Codes

• Repetition Code
• Hamming Code
• Golay Code
• BCH Code
• Reed-Solomon Codes
• Walsh Codes
• LDPC Codes