Channel Coding (Convolutional Code)

convolutional vs. block

code rate k/n, 입력 비트가 k개 → n개의 출력 비트

Convolutional Codes

컨볼루션 코드는 메모리를 가지고 있음.
→ 과거 입력을 참조하면서 새로운 비트를 생성하는 방식

Convolutional Encoding

Convolutional Encoder의 구조

code rate이 k/n 인 (information bits/coded bit) 컨볼루션 인코더는

• 제약 길이 K를 가짐.

제약 길이 K: constraint length, Encoder가 과거 몇 개의 입력 비트를 참조하는지 나타냄. 값이 클수록 더 많은 메모리가 필요

• (k⋅K) 단계의 시프트 레지스터로 구성되어 있으며, (n mod 2) 개의 adders를 포함.

각 시간 단위마다 발생하는 동작

• 첫 번째 단계에서: k 비트가 shift 레지스터의 첫 번째 k 단계로 이동.
• 모든 비트: 레지스터 내 모든 비트가 오른쪽으로 k 단계씩 이동.
• adders의 출력: n개의 가산기 출력이 순차적으로 샘플링되어 코드 비트로 변환.

code rate

k개의 메시지 비트에 대해 n개의 코드 비트를 생성
코드율 R = k / n (information bit / coded bit)

Convolutional Encoding - Structure

컨볼루션 인코딩의 기본 구조

입력 시퀀스 m = m1 , m2, m3, ...는 한 번에 k 비트씩 shift
k : 한 번에 인코더에 입력되는 비트의 수

ex) k=1, K=3일때
처음 비트 m_1 이 들어오면, 레지스터 첫 번째 위치에 m_1이 저장됨.
다음 비트 m_2가 들어오면, m_1은 오른쪽으로 한 단계 이동하고, 첫 번째 위치에는 m_2 가 저장.
세 번째 비트 m_3가 들어오면, 이전 비트들은 모두 한 단계씩 오른쪽으로 이동하며, 첫 번째 위치에는 m_3가 저장.
→ 한 비트씩 이동하고 저장되는 것이 시프트 레지스터의 기본 동작 방식

K=3이면, 인코더는 현재 비트 + 이전의 두 개의 비트도 사용하여 인코딩을 수행.
but 입력 비트가 들어올 때마다 인코더는 새로운 코드워드를 생성.

Code word sequence

출력 코드워드 시퀀스 U = U1 , U2 ,…, Uj, …
: 각 입력에 대해 생성된 코드 비트들의 집합

각 코드워드 $U_j$ = u_1,j ,u_2,j , … , u_n,j은 여러 개의 비트로 구성

$U_j$ 는 j 번째 입력에 대응하는 코드워드이고,
u_n,j 는 j 번째 코드워드에서 n 번째 비트를 의미.
→ 출력 코드 심볼은 매번 n개 생성됨

• 일반적으로 이진 코드 (k=1)가 사용됨.
• 주로 코드율 1/n인 코드가 고려됨. → 입력 비트 하나당 n개의 코드 비트를 생성

과정 요약

1. 비트 입력: 입력 비트들이 한 번에 k개씩 시프트 레지스터로 입력.
2. 시프트 및 저장: 입력된 비트는 레지스터의 첫 번째 위치에 저장되고, 기존에 저장된 비트들은 오른쪽으로 한 단계씩 이동.
3. 인코딩: 레지스터에 저장된 현재 비트와 이전 비트들을 이용해 출력 비트를 생성. 이 과정에서 adder들이 XOR 연산을 통해 여러 개의 출력 비트를 만듦.
4. 출력 (코드워드 생성): 생성된 출력 비트들이 모여 하나의 코드워드를 구성.

Convolutional Encoding - Representation

Convolution code를 표현하기 위해서는
→ information sequence (m)와 출력된 coded sequence (U) 간의 관계를 특성화하는 인코딩 함수를 설명

컨볼루션 코드의 4가지 주요 표현 방법 :

Connection Pictorial and Connection Polynomials (연결 그림 및 연결 다항식)

: 보통 인코더에서 사용.
ex) 1+D+D^2

State Diagram (상태 다이어그램)

: 보통 디코더에서 사용. not 시간관련

Tree Diagram (트리 다이어그램)

: 보통 디코더에서 사용

Trellis Diagram (트렐리스 다이어그램)

: 보통 디코더에서 사용. 시간 관련 정보가 있음

Convolutional Encoding - Connection Representation

Connection vector 지정 ($g_i$)

n개의 mod-2 adder 각각에 대해 n개의 Connection vector ($g_i$)를 정의
각 벡터는 해당 adder가 시프트 레지스터의 어떤 비트와 연결되어 있는지를 나타냄.

Connection vector의 차원

각 연결 벡터의 차원은 kK.
kK : 인코더의 시프트 레지스터에 있는 전체 비트 수

벡터의 각 요소의 의미

• 1이 있는 경우
: 해당 시프트 레지스터의 특정 비트가 mod-2 adder에 연결되어 있음
• 0이 있는 경우
: 해당 비트가 adder와 연결되지 않음을 의미

ex)

k=1, K=3인 경우, 전체 시프트 레지스터는 3개의 스테이지로 구성.
n=2개의 출력 비트를 생성한다고 가정.

첫 번째 연결 벡터가 [1,0,1]
→ 첫 번째와 세 번째 비트가 첫 번째 adder와 연결되어 있으며, XOR 연산을 통해 해당 출력 비트를 계산하는 데 사용됨.

두 번째 연결 벡터가 [0,1,1]
→ 두 번째와 세 번째 비트가 두 번째 adder와 연결되어 XOR 연산을 통해 두 번째 출력 비트를 생성.

Example: K = 3, Rate 1/2

• 연결 벡터 $g_1$ 과 $g_2$
: 각각 출력 비트 $U_1$, $U_2$ 를 생성하는데 사용되는 연결

• 초기 상태 및 입력 시퀀스
: 초기 레지스터 내용 = 0,0,0
입력 시퀀스: 1,0,0이 입력됨.

• 출력 시퀀스
첫 번째 입력 (m_1=1)이 들어왔을 때:
U_1 = 1 ⊕ 0 ⊕ 0 = 1
U_2 = 1 ⊕ 0 = 1
→ 첫 번째 코드워드 출력 = (1,1)

두 번째 입력 (m_2=0)이 들어왔을 때:
U_1 = 0 ⊕ 1 ⊕ 0 = 1
U_2 = 0 ⊕ 0 = 0
→ 두 번째 코드워드 출력 = (1,0)

세 번째 입력 (m_3=0)이 들어왔을 때:
U_1 = 0 ⊕ 0 ⊕ 1 = 1
U_2 = 0 ⊕ 1 = 1
→ 세 번째 코드워드 출력 = (1,1)

최종 출력 시퀀스: 11,10,11

State Diagram Representation

: Encoder의 내부 상태와 상태 간의 전이를 시각적으로 나타냄

current state

시프트 레지스터의 오른쪽 K−1 단계의 내용(또는 과거의 K−1 비트)이 현재 상태로 간주. (K-1; 첫번째껀 input)
총 가능한 상태의 수는 2^(K−1)

상태와 다음 출력

현재 상태와 다음 입력을 알면 다음 출력과 다음 상태를 결정할 수 있음.

각 상태에서의 transitions

각 상태마다 2개의 transitions가 존재
→ 새로운 입력이 0일 때, 1일 때

transitions의 시각적 표현

transitions는 상태 다이어그램에서 path로 나타냄,
각 transition 경로 위에는 출력 코드워드를 표시

ex)

k=1, K=3인 경우
첫 번째 연결 벡터 = [1,0,1], 두 번째 연결 벡터 = [0,1,1]

현재 상태는 (00).
입력 비트가 1이라면 새로운 상태는 (10)이 됨.
transition 동안 출력 코드워드가 생성 : $U_1$ = 1, $U_2$ = 1
→ output = (11)

전체 State diagram

초기 가정

• 입력 비트 m = 1, 1, 0, 1, 1 뒤에 K−1개의 0이 입력됨.
→ K−1개의 0은 시프트 레지스터를 완전히 비우기 위해 추가된 것

• 초기 시프트 레지스터의 모든 비트는 0으로 설정 (초기 상태 = 0)

output 시퀀스 U

Trellis Diagram

: convolution code를 시간의 흐름에 따라 시각적으로 표현한 다이어그램

Trellis Diagram은 State Diagram과 비슷하지만, 시간의 흐름이 더해짐.
→ 각 상태와 그 전이 과정을 시간에 따라 연결함으로써, 입력 비트가 시퀀스를 형성하면서 상태 변화와 어떤 출력이 생성되는지를 시각적으로 볼 수 있음.

입력 시퀀스와 경로

모든 입력 시퀀스 (m1, m2, m3, ...) 는 Trellis Diagram에서 하나의 경로에 해당.
→ input에 따른 path가 생김

초기 상태 $s_0$ = 00,

• input 시퀀스가 m1, m2, m3 =0,0,0일 경우:
출력은 (00,00,00)로, 이 경우 state는 계속 00,00,00,00으로 유지

• input 시퀀스가 m1, m2, m3 =1,0,0일 경우:
출력은 (11,10,11)로, state는 00,10,01,00

Decoding of Convolutional Codes

Convolutional Code로 인코딩된 데이터를 수신한 후, 오류를 수정하고 올바른 원래 데이터로 복원하기 위해 사용되는 디코딩 방법들

Maximum Likelihood Decoding

: 수신된 데이터가 실제로 전송된 데이터일 가능성이 가장 높은 경로를 찾는 것

Viterbi Algorithm

: Trellis Diagram을 통해 모든 가능한 경로를 고려하되, 불필요한 경로를 가지치기(Pruning)하면서 최적 경로를 찾음.

Transfer Function

: 입력 시퀀스가 출력 시퀀스로 변환되는 과정을 함수 형태로 표현한 것

Maximum Likelihood Decoding

코드 시퀀스 전송

: coded sequence U^(m)를 전송.
m : message sequence
→ 디지털 변조 방식 (예: BPSK, QPSK 등)을 이용해 전송

수신된 sequence (z) : 채널의 잡음 등으로 인해 변형된 형태로 수신된 데이터

Maximum Likelihood Decoder

: 가장 가능성 높은 coded sequence를 찾는 것이 목표

가능한 모든 전송된 코드 시퀀스
U^(m)들에 대해 수신된 신호 z가 나타날 가능성 P(z∣U^(m))을 계산하고,
그 중에서 가장 큰 값을 찾는 것

→ 수신된 신호 z가 가장 잘 설명되는 코드 시퀀스가 무엇인지, 즉 그 가능성이 최대인 U^(j)을 찾음

Examples

• AWGN 채널에서 Maximum Likelihood(ML) Decoder는 수신된 시퀀스와 가장 가까운 유클리드 거리(물리적 거리)를 가지는 경로를 선택.

• Binary Symmetric Channel에서 ML Decoder는 최소 해밍 거리를 사용하는 디코더로 작동.

Maximum Likelihood Decoding Procedure

• branch metric 계산:
각 브랜치 (i)에 대해 브랜치 메트릭을 계산
branch metric : 브랜치에서 발생한 오류 정도(수신된 신호와 예상된 신호 사이의 차이)

출력 비트 {u_1,i , u_2,i , …, u_n,i}와 해당 브랜치와 관련된 수신된 심볼 {z_1,i , z_2,i , …, z_n,i} 간의 차이를 계산

• path metric 계산:
path metric : 해당 경로를 따라 이어지는 모든 브랜치 메트릭의 합
경로 메트릭이 minimum인 경로 = 오류가 가장 적고 가능성이 높은 경로

경로의 수가 지수적으로 증가
→ 최적의 알고리즘은 Viterbi Decoding Algorithm

Viterbi Decoding (R=1/2, K=3)

입력 및 수신 시퀀스

Input data sequence (m): 전송된 원래의 데이터 시퀀스.
Coded sequence (U): 입력 데이터를 인코딩한 후 채널로 전송되는 코드 시퀀스.
Received sequence (z): 수신된 신호로, 전송 과정에서 잡음 등으로 인해 오류가 발생할 수 있음.

• QPSK 사용. 한 번에 두 비트 전송.

브랜치 메트릭 (Branch Metric)

: $z_i$ 와 인코딩된 값의 차이로 브랜치 메트릭을 계산
ex) 01(Received sequence)과 00(인코딩된 코드 시퀀스)과의 차이 (=해밍 거리)
→ (수신된 신호와 예상된 신호 사이의 차이)

최적 경로 선택

: 경로들 중에서 각 브랜치 메트릭의 합이 가장 작은 경로를 선택
• 가지치기(pruning) : Viterbi 알고리즘은 Trellis Diagram 내에서 각 시간 단계마다 불필요한 경로를 가지치기(pruning)하여, 가장 가능성이 높은 경로만을 남김.

Viterbi Decoder

Viterbi 디코더의 기본 아이디어

• 두 경로가 동일한 상태로 합쳐질 때 :
Trellis Diagram에서 두 경로가 하나의 동일한 상태로 합쳐지는 경우, 둘 중 하나는 최적의 경로가 아니므로 항상 제거

• 누적 경로 메트릭 (Cumulative Path Metric) :
특정 시간 $t_i$에서 해당 경로를 따라 모든 브랜치 메트릭의 합
→ 누적 경로 메트릭이 작을수록 해당 경로가 오류가 적고, 가능성이 높은 경로로 간주

• future output은 현재 상태에만 의존 :
Viterbi 알고리즘에서 미래의 출력은 현재의 상태에만 의존하며 이전 상태에는 의존하지 않음. = 현재 시점에서 경로 메트릭이 더 작은 경로를 선택하며 나아감.

합쳐지는 경로 (Merging Paths)

Viterbi 알고리즘은 각 시간 단계마다 합쳐지는 경로가 있을 경우, 누적 경로 메트릭이 더 큰 경로를 가지치기하여 제거하고, 가능성이 높은 경로만을 유지.

Viterbi Decoder의 주요 아이디어와 절차

• trellis의 상태 수 :
시간 단계 $t_i$에서 Trellis에는 2^(K−1)개의 상태가 존재.
제약 길이 (K) : 인코딩 과정에서 현재 상태가 참고하는 과거 단계 수.

• 각 상태로의 진입 경로 :
각 상태는 두 개의 경로를 통해 진입.

• Viterbi Decoding 절차 :
Viterbi Decoding은 각 시간 단계마다 두 개의 경로가 동일한 상태로 진입하는 경우, 두 경로의 메트릭을 비교하고 하나를 제거하는 방식으로 진행.

Viterbi Decoder - Example

다음 인코더를 통해 convolution code 생성 :

수신된 신호 z=[110111000110].
→ Viterbi 알고리즘을 사용하여 디코딩하고, 원래의 메시지 시퀀스와 코드워드를 찾아냄.

2비트씩 나눠서 처리

인코더의 구조에 따라 출력 비트가 2비트씩 생성되므로, 수신된 비트 시퀀스를 2비트 단위로 나누어 분석해야 함.

Trellis Diagram

Example 1

수신된 심볼 시퀀스 z=[11,01,11,00,01,10] 일 경우,

복원된 메시지 시퀀스 m=101110
path에서 : 아래-위-아래-아래-아래-위

Example 2

rate = 2/3, Generator Matrix가 다음과 같은 경우,
• Generator Matrix : 입력 시퀀스와 곱해져서 출력 시퀀스를 생성

input/output labeling

: 입력 비트 2개에 대해 출력 비트 3개를 생성

수신된 심볼 시퀀스 z = [010,110,111,000,000,000,000] 이면,

입출력 관계 (Input-Output Relationship)

$u_1$(D)= $m_1$
$u_2$(D)= D$m_1$ +$m_2$
$u_3$(D)= $m_1$ + D$m_1$ + $m_2$ + D$m_2$

• 지연된 입력 비트 : D$m_1$, D$m_2$
D$m_1$ : 이전 시간 단계에서의 $m_1$ 값
D$m_2$ : 이전 시간 단계에서의 $m_2$ 값

Convolutional Encoder Circuit

두 개의 입력 비트를 사용하고 세 개의 출력 비트를 생성하는 다변수 관계를 상태 다이어그램으로 표현하는 것은 매우 복잡. → state diagram 그리는게 도움되지 않음

Trellis Diagram

state diagram 은 상태 간 전이를 보여주기는 하지만, 시간이 흐르면서 변화하는 상태들을 연속적으로 표현하는 데 한계가 있음.
→ 시간의 축을 따라 최적 경로를 찾기 위해서는 Trellis Diagram이 더 유용.

ex ) 00 상태에서 $m_1$, $m_2$= 01 이 인코더에 들어오면:
$u_1$(D)= $m_1$ = 0
$u_2$(D)= D$m_1$ +$m_2$ = 0 + 1 = 1
$u_3$(D)= $m_1$ + D$m_1$ + $m_2$ + D$m_2$ = 0 + 0 + 1 + 0 = 1

The Viterbi decoding

Viterbi 알고리즘은 수신된 비트 시퀀스와 현재 경로의 출력 비트를 비교하여 오류의 수를 계산
→ 최적의 경로를 선택한 결과 : 00,11,10,01,00,00,00

Example: IEEE 802.11ax (WiFi 6E)