osp.chungbuk.ac.kr/2012년 강의자료

Presentation on theme: "osp.chungbuk.ac.kr/2012년 강의자료"— Presentation transcript:

1 osp.chungbuk.ac.kr/2012년 강의자료
정보 및 부호 이론 ’12-1 학기 담당교수 : 이봉운 osp.chungbuk.ac.kr/2012년 강의자료 ID: guest, PW: lee

2 제3장-II 채널 코딩 3.1 오류제어 기법 3.2 선형 블록 코드 3.3 인터리빙 3.4 블록 코드의 예
3.1 오류제어 기법 3.2 선형 블록 코드 3.3 인터리빙 3.4 블록 코드의 예 3.5 컨볼루션 코드 3.6 연습문제 본 강의자료는 김명진 저 “아날로그 및 디지털 통신 이론” 책 13장에서 전부 발췌하여 요약한 것입니다.

3 3.1 오류제어 기법(error control technique)-1
오류 검출만 가능한 방식 수신 측에서 오류를 검출하여 송신측에 데이터 재전송을 요구 장점 : 잉여(redundancy) 비트가 적고, 복호가 간단 단점 송신측과 수신측 사이에 양방향 링크가 필요 비트오류가 많이 발생하는 경우 빈번한 재전송으로 지연이 증대 실시간 처리보다 신뢰성이 중요한 데이터 전송에 주로 사용 오류 정정을 사용하는 방식 수신 측에서 독자적으로 오류 비트 정정이 가능 순방향 오류 정정(Forward Error Correction: FEC) 장점 : 역방향 링크가 불가/재전송 지연 문제 시 유리 단점 : 잉여 비트의 수가 많고, 복호가 복잡 실시간 처리가 중요한 경우에 사용 음성 서비스, 유도탄 제어

4 3.1 오류제어 기법(error control technique)-2
자동 반복 요구 방식(automatic repeat request: ARQ) 시스템 수신단에서 오류가 검출될 때마다 송신측에 보고 : 재전송 요구 수신 부호어가 무오류 : ACK (acknowledgement)를 송신측에 전송 부호어에 오류가 발생 : NAK (negative acknowledgement)를 전송 비트 오류가 적게 발생하는 환경에서 많이 사용 FEC 시스템과의 차이점 오류 검출만 필요 : 채널 코딩 과정에서 잉여 비트가 적음 오류의 검출을 보고하기 위해 역방향 링크가 필요 데이터를 여러 번 반복해서 전송 : 비트율에 여유가 필요 ARQ 방식의 종류 정지-대기(stop-and-wait) 방식 N-후진(Go-Back-N) 방식 선별-반복(selective repeat) 방식

5 3.1 오류제어 기법(error control technique)-3
ARQ 시스템(계속) 정지-대기(stop-and-wait) 방식 송신기가 하나의 부호어(code word)를 전송한 후 동작을 정지 수신기로부터 ACK/NAK 신호가 올 때까지 대기 오류가 미 검출 : ACK 신호를 송신측에 전송 ACK 신호가 오면 다음 부호어를 전송 오류가 검출 : NAK 신호를 송신측에 전송 NAK 신호가 오면 오류가 발생한 부호를 재전송 부호어와 부호어 사이에 쉬는 시간이 발생 최소 순방향 부호어 전송시간 + 역방향 ACK/NAK 전송시간 반이중(half duplex) 형태의 전송로로 사용 송신기와 수신기가 동시에 전송로를 사용하지 않음

6 3.1 오류제어 기법(error control technique)-4
ARQ 시스템(계속) N-후진(Go-Back-N) 방식 부호어와 부호어 사이에 쉬는 시간 없이 연속적으로 전송 송신기는 부호어를 일단 연속으로 전송하고 나중에 수신기로부터 확인 신호를 받은 후에 확인 확인 신호가 NAK인 경우 입력 버퍼에 있는 부호어 N개를 거슬러 올라가 오류가 발생한 부호어로부터 시작하여 다시 재전송 수신기는 오류가 검출된 부호어 다음의 N개 부호어를 버림 오류가 자주 발생할수록 버리는 부호어가 많아져 전송 효율이 감소 전이중(full duplex) 형태의 전송로가 필요 송신기와 수신기가 동시에 신호를 전송

7 3.1 오류제어 기법(error control technique)-5
ARQ 시스템(계속) 선별-반복(selective repeat) 방식 오류가 검출된 부호어만 선별해서 재전송하는 방식 송신기는 확인 신호를 기다리지 않고 부호어를 순서대로 계속 전송 NAK 신호를 받는 경우 송신기는 해당 부호어만 재전송한 다음 원래의 순서대로 돌아가서 그 다음 부호어를 전송 다른 두 방식에 비해 전송 효율이 가장 좋음 처리가 복잡하여 장비의 가격이 가장 비쌈 전이중(full duplex) 형태의 전송로가 필요

8 3.1 오류제어 기법(error control technique)-6
패리티 검사(parity check) 가장 간단하면서 자주 사용되는 방식 부호화 : 단일 패리티 검사 부호 각 부호어에 하나의 잉여 비트를 첨가 : k + 1 부호율 : k/(k + 1) 부호어에 들어 있는 1의 개수가 짝수/홀수가 되도록 지정 짝수 : 짝수 패리티(even parity) 홀수 : 홀수 패리티(odd parity) 복호화 : 수신된 부호어에서 1의 개수로 오류를 판정

9 3.1 오류제어 기법(error control technique)-7
패리티 검사(계속) 이진 대칭 채널(binary symmetric channel; BSC)에서 오류 확률 n 비트로 구성된 블록에서 j개의 비트가 오류를 발생할 확률 오류를 검출하지 못할 확률 짝수 패리티 검사 홀수 패리티 검사

10 3.1 오류제어 기법(error control technique)-8
순방향 오류 정정(FEC : forward error correction) 시스템 채널 손상에 대처할 수 있도록 전송되는 신호를 변형 오류 검출/정정이 가능 Eb/No가 고정되어 있을 때 BER를 감소시키거나 BER이 고정되어 있을 요구되는 Eb/No를 감소시킴 대역폭의 확장이 요구 오류 정정 능력이 있는 대신 부호율이 낮아짐 사각형 코드(rectangular code) 정보 비트를 사각형 블록에 행렬 형태로 배열 : M  N 행 단위 및 열 단위로 패리티 비트를 추가 : (M+1)  (N+1) 부호율 : r = k/n = MN/(M+1)(N+1) 오류 정정 능력은 1 : 한 비트까지의 오류를 정정

11 3.1 오류제어 기법(error control technique)-9
순방향 오류 정정(FEC) 시스템(계속) 사각형 코드(계속)

12 3.1 오류제어 기법(error control technique)-10
순방향 오류 정정(FEC) 시스템(계속) (n, 1) 반복 코드(repetition code) 정보 비트를 여러 번 반복해서 전송하는 방식 부호율 : r = 1/n n 비트의 부호어 중에서 1 또는 0의 개수가 많은 쪽으로 복호 n 비트 중에서 오류가 절반 이하 발생하면 오류 정정이 가능 예 : (3, 1) 반복 코드 부호어로 변경하여 전송 : 0 → 000, 1→111 1개 이하의 비트 오류가 발생하면 오류 정정이 가능 예 : (5, 1) 반복 코드 2개 이하의 비트 오류가 발생하면 오류 정정이 가능 반복 코드는 부호화/복호화 과정이 매우 간단 많은 잉여 비트 때문에 전송량이 크게 증가 우수한 채널 코딩 방식 : 적은 잉여 비트와 큰 오류 정정 능력

13 3.1 오류제어 기법(error control technique)-11
순방향 오류 정정(FEC) 시스템(계속) (n, k) 채널 코드에서 부호어 오류 확률 가정 : BSC 이며, 오류 정정 능력은 t개 n 비트 부호어 중에서 t 비트 이하의 오류가 발생하면 오류가 정정 오류를 정정하지 못해서 부호어 오류가 발생할 확률 일반화된 부호화 개념 채널 부호화(channel encoding) k 튜플(tuple) 메시지 벡터를 n 튜플 부호어 벡터로의 변환 과정 채널 복호화(channel decoding) 수신된 n 차원 데이터 벡터로부터 k 차원 메시지 벡터로의 복원 과정

14 3.1 오류제어 기법(error control technique)-12
순방향 오류 정정(FEC) 시스템(계속) 일반화된 부호화 개념(계속) 채널 코드의 설계 원칙 오류가 발생하더라도 옳은 부호와 가장 유사 부호어간의 큰 차이가 필요 k에 비하여 n이 클수록 부호어로 사용할 수 있는 선택 대상이 많아짐 채널 오류에 대해 강인할 수 있는 여지가 많음

15 3.1 오류제어 기법(error control technique)-13
순방향 오류 정정(FEC) 시스템(계속) 채널 코딩 방식의 분류 블록 코딩(block coding)과 컨볼루션 코딩(convolution coding) 블록 코딩(block coding) : (n, k) 블록 코드 블록 단위로 정보 데이터가 채널 부호화기에 입력되고 블록 단위로 부호어가 출력되어 전송 k 비트씩 그룹화되어 n 비트의 부호어로 생성 및 전송 현재의 k 비트 메시지어는 과거의 k 비트 메시지어와 무관 독립적으로 출력을 발생

16 3.1 오류제어 기법(error control technique)-14
순방향 오류 정정(FEC) 시스템(계속) 컨볼루션 코딩(convolution coding) : (n, k, K) 블록 코드 직렬로 채널 부호화기에 입력되고 전송량이 증가한 부호어 열이 직렬로 출력되어 전송 현재의 부호어 발생을 위해 현재의 k 비트 메시지와 과거의 메시지어도 필요 몇 개의 메시지어들이 관계되는지를 표현 : (n, k, K) 구속장(constraint length) : K n 비트의 부호어를 생성하기 위하여 필요한 메시지어의 개수 현재의 메시지어 1 개와 과거의 메시지어 K - 1개

17 3.1 오류제어 기법(error control technique)-15
순방향 오류 정정(FEC) 시스템(계속) 블록 코딩과 컨볼루션 코딩의 비교 블록 코딩의 경우 우수한 비트오율 성능개선 효과를 위해 보통 k의 값을 크게 선택 블록 크기가 크면 부호화 및 복호화 과정의 처리 지연이 길어짐 실시간 통신에 응용하는데 문제를 야기 컨볼루션 코딩의 경우 보통 k 의 값을 작게 해도 구속장 K 를 적절히 선택 : 보통 5~9 정도 큰 성능개선 효과를 달성 컨볼루션 코딩에서는 많은 경우 k = 1로 지정하여 부호화 메시지어를 1비트로 구성 처리 지연이 작음 실시간 통신이 중요시 되는 경우 컨볼루션 코딩이 많이 사용

18 3.1 오류제어 기법(error control technique)-16
오류 검출 및 정정 능력 (n, k) 채널 코딩 : (n - k)의 잉여 비트를 추가 부호어 벡터간의 차이를 크게 하여 전송오류를 검출/정정 거리(distance)의 개념을 사용 부호어 벡터 간의 차이 정도를 표현하는 정량적인 방법 해밍(Hamming) 거리를 가장 많이 사용 Hamming 거리 두 부호어 벡터 x와 y 사이의 거리 : d(x, y) 정의:두 벡터의 같은 위치에 있는 원소들 중 서로 다른 원소의 개수 예 : x = [ ], y = [ ], d(x, y) = 2 채널 코드의 설계 2n 개의 부호어 벡터 중에서 서로 해밍 거리가 큰 벡터들을 2k 선정 채널 코딩 시스템의 성능 유효한 부호어 벡터들 사이의 최소거리(dmin)에 의해 결정 최소거리는 시스템이 비트 오류를 검출/정정하는 능력과 직결

19 3.1 오류제어 기법(error control technique)-17
오류 검출 및 정정 능력(계속) (7, 4) Hamming 코드

20 3.1 오류제어 기법(error control technique)-18
오류 검출 및 정정 능력(계속) (7, 4) Hamming 코드(계속) 유효한 부호어 벡터 : 24 = 16 최소 거리를 구하기 위해 120번의 벡터 거리 연산이 필요 dmin = … = 120 최소 거리를 간단히 구하는 방법 : Hamming Weight를 사용 벡터의 무게(weight) : W() 이진 원소 벡터에 들어있는 1의 개수로 정의 예 : x = [101001] 부호어 벡터를 더하는 경우 원소가 다를 때만 해당 비트 위치에 1이 발생 두 부호어 벡터간의 거리는 두 벡터 합의 무게와 동일 예 : y = [000 0]

21 3.1 오류제어 기법(error control technique)-19
오류 검출 및 정정 능력(계속) (7, 4) Hamming 코드(계속) 최소 거리를 간단히 구하는 방법 : Hamming Weight를 사용(계속) 선형 부호의 특성 임의의 두 코드를 더하면 코드 집합 내의 다른 코드가 생성 부호어 벡터간의 최소거리 : 최소 해밍 거리 영 벡터가 아닌 코드 벡터의 무게 중 가장 작은 것 120번의 비교 연산 대신 단지 15번의 무게 계산만 필요 : dmin = 3 (7,4) Hamming 코드의 오류정정 능력

22 3.1 오류제어 기법(error control technique)-20
오류 검출 및 정정 능력(계속) 채널 코드의 예 (3, 2) 코드 : 00 → 000, 01 → 010, 10 → 101, 11 → 111 dmin = 1 하나의 비트에 오류가 발생하면 다른 부호어가 될 수 있음 복호기의 오류 검출이 불가 (5, 2) 코드 : 00 → 00000, 01 → 01110, 10 → 10101, 11 → 11011 dmin = 3 1 또는 2 비트가 오류를 일으키더라도 다른 부호어가 될 수 없음 [01] → c = [01110]이 전송 → 1 비트 오류 발생 → r = [01111] 수신 벡터와 가장 거리가 가까운 부호어 벡터를 출력 : c = [01110] 오류검출 능력 : 2 오류정정 능력 : 1

23 3.1 오류제어 기법(error control technique)-21
오류 검출 및 정정 능력(계속) 최소 거리와 오류 검출 능력과의 관계 c1과 c2는 가장 거리가 가까운 두 부호어 벡터 : 8 비트 그림 예에서 dmin = 7 오류의 개수가 dmin보다 적은 경우 수신 벡터는 유효한 부호어 벡터 집합의 어떤 벡터와도 같지 않음 오류 검출이 가능 c1에서 오류가 dmin 개 발생한 경우 수신 벡터는 유효한 부호어 벡터 c2가 될 수 있음 오류 검출이 불가 오류검출 능력 : q = dmin- 1

24 3.1 오류제어 기법(error control technique)-22
오류 검출 및 정정 능력(계속) 최소 거리와 오류 정정 능력과의 관계 c1을 전송했을 때 오류의 개수가 dmin/2보다 적으면 c1로 복구 가능 오류 정정이 가능 오류검출정정 능력 : t < dmin/2 를 만족하는 정수

25 3.1 오류제어 기법(error control technique)-23
오류 검출 및 정정 능력(계속) 최소 거리와 오류 검출 및 정정 능력과의 관계 예 채널 코딩을 하지 않는 경우 : 부호어와 정보어가 동일 dmin = 1 : 오류 검출이 불가 한 비트라도 오류가 생기면 다른 유효한 부호가 되기 때문 (n, k) 채널 코드를 사용하는 경우 : n-k 개의 잉여비트가 추가 dmin 의 상한값은 n-k+1 잉여 비트 수를 증가하면 부호율은 감소, 오류정정 능력은 향상

26 3.1 오류제어 기법(error control technique)-24
FEC 시스템의 비트오율(BER) 성능 오류정정 능력이 t =1인 (7, 4) 블록 코드를 사용한 경우 한 비트 데이터의 오류 확률 : pu = 0.001 통신 채널에서 비트 오류가 발생할 확률 : pc = 0.001 채널 코딩을 하지 않는 경우 채널 코딩을 한 경우 부호어 7비트 중 2비트 이상 오류가 발생하면 패킷에서 오류 발생 코딩을 한 패킷오류 확률이 크게 감소

27 3.1 오류제어 기법(error control technique)-25
FEC 시스템의 비트오율(BER) 성능(계속) 오류정정 능력이 t =1인 (7, 4) 블록 코드를 사용한 경우(계속) pu와 pc가 같기 위해서는 동일 전송 에너지가 필요 비트오류 확률은 변조 방식에 의해 결정 AWGN 채널에서 BPSK 변조의 경우 채널 코딩을 하는 경우 부호어의 비트오율은 다소 증가하나 오류정정 능력에 의해 패킷오류 확률은 낮아짐 예 : pc = 0.01, pu = 일 때 PMc  < PMu  0.004

28 3.1 오류제어 기법(error control technique)-26
FEC 시스템의 비트오율(BER) 성능(계속) 오류정정 능력이 t 인 (n, k) 블록 코드를 사용한 경우 통신 채널에서 부호어의 비트 오류 확률 : pc << 1 대부분의 부호어 오류는 t+1 개의 비트 오류에 의한 것을 의미 메시지어 비트로 환산하면 평균 (t + 1)k/n 비트의 오류로 근사화 각 부호어는 k비트의 메시지어에 대응 FEC 시스템의 비트오율

29 3.1 오류제어 기법(error control technique)-27
FEC 시스템의 비트오율(BER) 성능(계속) 오류정정 능력이 t 인 (n, k) 블록 코드를 사용한 경우(계속) FEC 시스템의 비트오율(계속) BPSK 변조를 사용하는 경우 코딩 이득(coding gain) 주어진 비트오율에 대해 채널 코딩에 의해 얻어진 Eb/No로 정의 채널 코딩에 의하여 비트오율 성능은 개선되지만 전송 대역폭은 n/k배 증가

30 3.1 오류제어 기법(error control technique)-28
FEC 시스템의 비트오율(BER) 성능(계속) FEC 시스템의 비트오율과 코딩 이득

31 3.1 오류제어 기법(error control technique)-29
FEC 시스템의 비트오율(BER) 성능(계속) FEC 시스템의 비트오율과 코딩 이득(계속)

32 3.1 오류제어 기법(error control technique)-30
FEC 시스템의 비트오율(BER) 성능(계속) 코딩 시스템과 비코딩 시스템의 BER 성능 비교 일반적으로 코딩 시스템의 성능이 더 우수 : 항상 좋은 것은 아님 Eb/No 값이 어느 정도 크면 코딩 시스템의 성능이 더 우수하나 Eb/No 값이 작으면 비코딩 시스템의 성능보다 더 열악 채널 코딩은 Eb/No 값을 감소시켜 BER이 증가 코딩에 의한 잉여 비트로 전송량이 증가 비트 당 에너지가 감소 BER이 너무 크지 않다면 잉여 비트의 효과에 의해 오류 정정이 가능 부호어 오류 확률의 감소가 가능 Eb/N0가 너무 작은 경우 오류정정 능력 이상으로 부호어에 비트오류가 발생 오류정정 효과는 거의 없고, 잉여 비트는 에너지만 더 낭비 잉여 비트는 오류정정의 기능을 제대로 하지 않으면서 정보 비트와 함께 전송되는 ‘짐’으로만 작용 FEC 시스템은 어느 정도 이상의 Eb/N0가 필요

33 3.1 오류제어 기법(error control technique)-31
예제13.1 : 코딩 시스템과 비코딩 시스템의 성능 비교 BPSK 변조 시스템 : 정보 비트율 Rb = 4,800 bps Eb/N0 = 9.6 dB 오류정정 능력이 1비트인 (15,11) 코드를 사용

34 3.1 오류제어 기법(error control technique)-32
예제13.1 : 코딩 시스템과 비코딩 시스템의 성능 비교(계속)

35 3.2 선형 블록 코드(linear block code)-1
블록 코드 : (n, k) 부호기는 k개의 입력 심볼을 n개의 출력 심볼로 변환 통상적으로 입력과 출력 심볼은 0 또는 1 예외 : Reed-Solomom 코드는 입력과 출력이 M진(M-ary) 잉여 심볼이 발생 : j = n - k 코드율 : r = k/n r이 작은 경우 : 잉여 심볼이 많음 r이 큰 경우 : 잉여 심볼이 적음 대표적인 값 n : 20 ~ 1,000 r : 0.25 ~ 1 대표적인 블록 코드 : Hamming code

36 3.2 선형 블록 코드(linear block code)-2
(7, 4) Hamming 코드의 부호화 및 복호화 과정의 개념 예 : u = [ ]인 경우

37 3.2 선형 블록 코드(linear block code)-3
(7, 4) Hamming 코드의 부호화 및 복호화 과정의 개념(계속) 메시지어 u 코드어 v u1 u2 u3 u4 v1 v2 v3 v4 v5 v6 v7 1

38 3.2 선형 블록 코드(linear block code)-4
발생기 행렬(generator matrix) 발생기의 행렬 연산 G : 크기가 k  n 인 발생기 행렬 Hamming 코드는 부호어 내에 메시지어가 원형 그대로 보존 조직적인 코드(systematic code) k개의 메시지어 비트와 n - k 개의 패리티 비트로 구성 p = [p1, p2, …, p3] : j = n – k개의 잉여 비트로 구성된 패리티 검사 벡터 조직적인 코드를 사용하면 부호화 과정이 간단 앞으로는 조직적인 선형 블록 코드에 대해서만 고려

39 3.2 선형 블록 코드(linear block code)-5
발생기 행렬(계속) 조직적인 선형 블록 코드의 발생기 행렬 구조 Ik : k  k 크기의 단위 행렬(identity matrix) P : k  j 크기의 2진수 부행렬(submatrix)로서 패리티를 생성 벡터와 행렬의 연산 : mod-2 연산 곱셈 : 논리 연산 AND 덧셈 : 논리 연산 Exclusive-OR

40 3.2 선형 블록 코드(linear block code)-6
발생기 행렬(계속) 조직적인 선형 블록 코드의 발생기 행렬 구조(계속) 부호어 벡터의 생성 예 : (7, 4) Hamming 코드 발생기 행렬

41 3.2 선형 블록 코드(linear block code)-7
발생기 행렬(계속) 예제13.2 : 채널 부호화 (5, 3) 블록 코드 발생기 행렬 : 가능한 부호어를 나열하고, 최소거리 및 오류검출/정정 능력은? 부호어 간의 최소거리 : dmin = 2 오류검출 능력 : q = 1 오류정정 능력 : t = 0

42 3.2 선형 블록 코드(linear block code)-8
패리티 검사 행렬(parity check matrix) (n, k) 채널 코드 발생기 행렬 G : k  n 패리티 검사 행렬(parity check matrix) : H 수신기에서 전송된 패리티 비트를 검사하기 위해 사용되는 행렬 G의 행과 H의 행이 서로 직교

43 3.2 선형 블록 코드(linear block code)-9
패리티 검사 행렬(계속) 수신기에서 패리티 검사 메시지어 벡터 u로부터 생성된 부호어 벡터 : v = uG 오류가 없이 전송되는 경우 패리티 검사는 수신 부호어 벡터와 패리티 검사 행렬의 곱 수신 부호어 벡터는 송신 부호어 벡터 v와 동일 오류가 발생하여 수신되는 경우 비트 오류를 정정하는데 사용

44 3.2 선형 블록 코드(linear block code)-10
신드롬 검사(syndrome testing) 수신된 부호어 벡터 e : 통신 채널의 영향으로 발생한 오류 벡터 가능한 오류 패턴의 개수 : 2n – 1 영 벡터는 오류가 아니므로 제외 수신된 부호어 벡터에 대하여 패리티 검사를 시행 : 신드롬 신드롬은 수신 부호어가 유효한 부호어 중의 하나인지를 판단 신드롬이 영 벡터이면 r이 유효한 부호어 벡터를 의미 신드롬이 영 벡터가 아니면 r이 검출 가능한 오류를 포함 r이 정정 가능한 오류를 포함하고 있다면 신드롬은 어떤 특정한 오류 패턴을 제공

45 3.2 선형 블록 코드(linear block code)-11
신드롬 검사(계속) 신드롬의 다른 표현 수신 부호어 벡터에 대한 패리티 검사 오류 벡터에 대한 패리티 검사와 동일 수신기의 복호기 수신 부호어 벡터에 대해 신드롬을 검사 : 신드롬이 0인 경우 ARQ 시스템 : 재전송을 요청 FEC 시스템 : 오류의 위치를 찾아내어 오류를 정정 정정 가능한 오류 패턴과 신드롬 간에는 일대일 대응 관계를 유지 선형 블록 코드의 중요한 성질

46 3.2 선형 블록 코드(linear block code)-12
신드롬 검사(계속) 정정 가능한 오류 패턴 예 : 전송 중에 한 개의 오류가 i 번째 비트에서 발생한 경우 수신기에서 계산한 신드롬은 HT의 i 번 째 행이 됨 HT에서 동일한 행이 존재하는 경우 신드롬과 오류 벡터가 일 대 일 관계를 성립하지 않음 오류 정정이 불가 HT의 i 번 째 행이 모두 0인 경우 신드롬은 0 벡터가 되어 오류가 발생하지 않은 경우와 구별이 불가 오류 검출이 불가 오류 정정을 위한 패리티 검사 행렬의 조건 HT의 모든 행(H의 모든 열)은 서로 달라야 한다. HT의 어떠한 행(H의 어떠한 열)도 영 벡터가 되어서는 안 된다.

47 3.2 선형 블록 코드(linear block code)-13
예제13.3 : (7, 4) Hamming 코드에서의 신드롬 검사 u = [1010], v = [ ] 한 비트의 오류가 발생한 경우 : r = [ ] 신드롬으로부터 오류 비트 위치를 알 수 있고, 오류 정정이 가능

48 3.2 선형 블록 코드(linear block code)-14
예제13.3 : (7, 4) Hamming 코드에서의 신드롬 검사(계속) 두 비트의 오류가 발생한 경우 : r = [ ] 처음 두 비트에서 발생한 오류의 신드롬은 6번째 비트 오류의 신드롬과 동일 신드롬만 가지고 발생한 오류의 구별이 불가 HT의 두 행을 더하여 만들어진 벡터가 HT의 다른 행에 속하면 오류 정정이 불가능 (7, 4) 해밍 코드는 한 비트 오류 정정만 가능

49 3.2 선형 블록 코드(linear block code)-15
오류 정정(error correction) (n, k) 블록코드에서 가능한 n-비트 오류 벡터의 수 : 2n – 1 가지 신드롬 : 1  (n – k) 벡터 오류를 진단할 수 있는 신드롬의 수 : 2j – 1, j = n – k 주어진 신드롬에 대해 원인이 되는 오류 패턴이 한 개뿐인 경우 오류 정정에 의한 복호기의 구현 주어진 신드롬에 대해 원인이 되는 오류 패턴이 여러 개인 경우 최대 가능성 복호화(maximum-likelihood decoding) 방법을 이용 오류 패턴 중에서 가장 가능성이 높은 오류 패턴을 진단 오류 비트 수가 가능한 한 작은 경우에 해당 정정된 부호어 오류가 생긴 수신 부호어와 가장 짧은 거리에 있는 부호어를 선택

50 3.2 선형 블록 코드(linear block code)-16
오류 정정(계속) 최대 가능성 복호기 구현 방법 가장 발생 가능성이 높은 오류 벡터를 구함 : 2j–1 개의 신드롬에 대해 신드롬 참조표(look-up table)를 제작 복호기에 입력되는 수신 부호어 벡터 r로부터 신드롬 s를 계산 표를 참조하여 계산한 신드롬과 짝을 이루는 오류 벡터를 발견 수신 벡터와 더하여 오류를 정정 정정된 부호어에 대응하는 메시지어를 출력

51 3.2 선형 블록 코드(linear block code)-17
오류 정정(계속) (7, 4) Hamming 코드의 예 j = n – k = 3 : 신드롬은 1  3 벡터로 모두 8가지(영 벡터 포함) dmin = 3 : 오류정정 능력은 1 비트 가능한 오류 패턴 : 2n -1 = 127 7개의 서로 다른 신드롬을 만들어내는 발생 빈도가 높은 오류 패턴 발생 빈도가 가장 높은 오류 패턴 : 7개의 한 비트 오류 발생 패턴 한 비트 오류 패턴에 해당하는 신드롬 : HT의 각 행 HT의 모든 행은 서로 상이 신드롬 참조표

52 3.2 선형 블록 코드(linear block code)-18
예제13.4 : 조직적인 (6, 3) 블록 코드에서의 오류정정 u = [u1, u2, u3], v = [u1, u2, u3, p1, p2, p3] 오류정정 능력은? dmin = 3 : 오류정정 능력은 1 비트

53 3.2 선형 블록 코드(linear block code)-19
예제13.4 : 조직적인 (6, 3) 블록 코드에서의 오류정정(계속) 패리티 검사 행렬은? 신드롬 참조표를 작성 j = n – k = 3 : 신드롬은 1  3 벡터로 모두 8가지(영 벡터 포함) dmin = 3 : 오류정정 능력은 1 비트 가능한 오류 패턴 : = 63 8개의 신드롬 발생 오류가 없는 신드롬 벡터 : [000] 1 비트만 오류 : 6개(e1, e2, …e6) 2 비트의 오류를 할당 : [111] 할당하는 여러 방법이 존재 예 : HT의 3행과 5행을 가산 → 111 예 : HT의 1행과 6행을 가산 → 111

54 3.2 선형 블록 코드(linear block code)-20
예제13.4 : 조직적인 (6, 3) 블록 코드에서의 오류정정(계속) 신드롬 참조표를 작성(계속) 오류 패턴 신드롬 s

55 3.3 인터리빙(interleaving)-1 블록 코드가 적합한 통신 환경 백색 잡음이 적합하지 않은 통신 환경
비트 오류가 균일하고 불규칙하게 분포 비트간의 오류가 독립적 전송로에 백색잡음이 부가되는 경우에 해당 예 : 유선 전화선로 백색 잡음이 적합하지 않은 통신 환경 무선 전송 중에 번개가 치는 경우 상당히 큰 잡음이 짧은 시간에 집중적으로 발생 이동 통신의 경우 다중 경로 신호들의 위상이 불일치 신호의 크기가 변화 : 페이딩 현상이 발생 신호의 크기가 일정 시간 동안 작은 상태로 지속 가능 비트 오류가 연속적으로 발생 CD의 표면이 긁힌 경우 : 비트 오류가 한 데 몰려 발생

56 3.3 인터리빙(interleaving)-2 연집 오류(burst error)의 문제점/해결책
오류가 연집 형태로 발생하면 채널 코딩 효과가 무의미 비트 오류가 오류정정 능력보다 크기 때문 연집 오류 문제 해결을 위해 인터리빙 방법을 사용 연집 형태의 오류를 분산 한 부호어 내에 비트 오류가 오류정정 능력 이하로 만들어 줌 페이딩 환경에서 연집 오류가 발생하는 예

57 3.3 인터리빙(interleaving)-3 인터리빙 방법 데이터의 순서를 뒤바꾸는 것
한 블록의 데이터를 열 단위로 써서 채우고 다 채워지면 행 단위로 읽어서 비워나가는 방식으로 구현 데이터의 순서를 여러 형태로 뒤바꾸는 방법이 존재 블록 인터리빙(block interleaving) 한 블록의 데이터를 메모리 행렬에 채우고 비우는 방식 역인터리빙(deinterleaving) 행 단위로 쓰고 열 단위로 읽어서 전송 데이터를 복구

58 3.3 인터리빙(interleaving)-4 인터리빙의 원리 예 : 간단한 (3, 1) 반복 코드를 사용한 경우
오류정정 능력 : 1

59 3.3 인터리빙(interleaving)-5 인터리빙에서 블록의 크기 블록이 큰 경우
처리 과정에서 필요한 메모리 크기가 증가 행렬을 채우고 비우는 과정에서 처리 지연이 증가 실시간 처리가 중요시되는 응용에서는 크기가 고려되어야 함 인터리빙의 깊이(depth) : MN 행렬에서 열의 개수 N 깊이가 클수록 지속구간이 긴 페이딩에 강인하나 채널 부호기/복호기 앞 단에서 처리 시간이 증가 응용 환경의 페이딩 특성을 조사하여 인터리빙의 깊이를 결정 인터리빙의 폭(span) : MN 행렬에서 행의 개수 M 폭은 채널 코드의 길이 이상으로 선택 예 : 한 번의 연집 오류로 인한 수신 부호어 내의 오류의 개수 N을 페이딩으로 인한 연집 오류의 길이보다 크게 선택하고 M을 채널 코드의 길이보다 크게 선택한 경우에 수신기에서 역인터리빙 했을 때 오류의 개수는 1개 이하

60 3.3 인터리빙(interleaving)-6 인터리빙에서 블록의 크기(계속) 155 블록 인터리버의 예

61 3.4 블록 코드의 예-1 Hamming 코드 가장 간단한 종류의 블록 코드
구조 : (n, k) = (2j – 1, 2j – 1 –j), j = 2, 3, … 잉여 비트의 수 : n – k = j 최소 거리가 dmin = 3으로 고정 한 비트의 오류 정정이 가능 두 비트까지 오류 검출이 가능 해밍 코드의 구조 예

62 3.4 블록 코드의 예-2 Hamming 코드(계속) 해밍 코드의 성능 : AWGN과 BPSK를 가정
잉여 비트 수 j 에 따라 성능이 개선 블록 크기가 클수록 코딩 이득이 증가 비트오류 확률(BER) 부호화된 비트오류 확률 잉여 비트 수가 증가할수록 부호율이 증가 부호화된 비트의 오류 확률 pc는 감소

63 3.4 블록 코드의 예-3 BCH(Bose-Chadhuri-Hocqunghem) 코드 해밍 코드를 확장시킨 코드
여러 비트의 오류정정이 가능하도록 확장시킨 코드 해밍 코드는 BCH 코드 군의 한 부분 집합 BCH 코드의 구조는 매우 다양 블록 길이, 메시지 길이, 부호율, 오류정정 능력 해밍 코드는 매우 제한적인 구조 블록 길이만 허용되면 어떤 개수의 오류정정도 가능 BCH (127, 64) 코드 : 10 비트의 오류정정이 가능 BCH (1023, 11) 코드 : 255 비트의 오류정정이 가능 해밍 코드는 항상 한 비트의 오류정정 능력을 제공 전반적으로 BCH 코드가 해밍 코드에 비해 성능이 우수하나 블록 크기가 커서 지연이 증가 잉여 비트가 많을수록 성능이 좋은 것은 아님 예 : BCH (127, 64)와 BCH (127, 36)

64 3.4 블록 코드의 예-4 BCH(Bose-Chadhuri-Hocqunghem) 코드(계속) 블록 코드의 성능 비교
BCH (127, 64) 코드는 BCH (127, 36) 코드보다 잉여 비트 수가 적으나 코딩 이득은 더 큼 주어진 블록 크기에 대하여 성능은 부호율에 따라 상이 최대 코딩 이득은 부호율이 1/3 ~ 3/4 사이에서 달성

65 3.4 블록 코드의 예-5 BCH(Bose-Chadhuri-Hocqunghem) 코드(계속)
부호율에 따른 BCH 코드의 성능 : r  ¾ 일 때

66 3.4 블록 코드의 예-6 BCH(Bose-Chadhuri-Hocqunghem) 코드(계속)
부호율에 따른 BCH 코드의 성능 : r  ½ 일 때

67 3.4 블록 코드의 예-7 BCH(Bose-Chadhuri-Hocqunghem) 코드(계속)
부호율에 따른 BCH 코드의 성능 : r  ¼ 일 때

68 3.5 컨벌루션 코드(convolution code)-1
블록 코딩 정보 비트열을 k 비트 메시지 단위로 블록을 분할 블록 단위로 부호화하여 n 비트의 부호어를 생성 한 블록의 부호화는 다른 블록의 부호화와 독립적 한 블록의 정보들은 다른 블록의 부호화에 영향을 미치지 않음 다른 블록의 부호화를 위하여 정보들의 저장이 불필요 컨벌루션 코딩 정보 비트열이 직렬로 채널 부호화기에 입력 전송량이 증가한 부호어 열이 직렬로 출력되어 전송 현재 정보의 생성 현재와 과거 블록의 정보 비트들이 필요 몇 개의 메시지어 블록이 관계되는지의 표현이 요구 : (n, k, K) K : 부호어를 생성하는데 필요한 메시지어의 개수 현재의 메시지어 1 개와 과거의 메시지어 K-1 개 K : 구속장(constraint length)

69 3.5 컨벌루션 코드(convolution code)-2
컨벌루션 코딩(계속) 코드 발생기에는 K-1 개의 메시지어를 저장할 메모리가 필요 통상 컨벌루션의 코드 길이는 블록 코드에 비해 매우 짧음 흔히 한 1 비트 길이를 갖는 코드를 사용 : k = 1 특별한 언급이 없으면 k = 1인 코드를 가정 컨볼루션 코딩을 사용한 통신 시스템의 블럭도

70 3.5 컨벌루션 코드(convolution code)-3
컨볼루션 코딩을 사용한 통신 시스템의 블록도(계속) 코딩과 잉여 비트 수와의 관계 블록 코딩의 경우 오류정정 효과를 높이기 위해 잉여 비트 수가 크게 설계 : j = n – k j의 증가는 부호율 r = k/n 이 작아져서 전송 효율을 감소시킴 전송 효율을 높이기 위해 n과 k를 큰 값으로 선택한 경우 부호화/복호화 과정의 처리 지연이 증가 : 실시간 통신에 곤란 우려 컨볼루션 코딩의 경우 k의 값을 작게 해도 높은 오류정정 효과를 달성 구속장을 적절히 선택 : 보통 5 ~ 9 정도 처리 지연이 작음 : 실시간 통신에 많이 사용 콘볼루션 코드의 성질 Good for AWGN channel Good for burst error channel if interleaved Easy soft decision decoding useful for real-time applications: continuously encoded/decoded

71 3.5 컨벌루션 코드(convolution code)-4
컨볼루션 부호화기 K 단 시프트 레지스터와 n개의 이진 덧셈기로 구성 이진 덧셈기의 출력은 선형 조합으로 표현

72 3.5 컨벌루션 코드(convolution code)-5
컨볼루션 부호화기(계속) 부호어의 생성 현재 부호화기의 상태 값과 입력 값에 의해 결정 부호화기의 상태(state) 시프트 레지스터에 저장된 K-1 개의 과거 메시지어 비트를 의미 메모리 소자와 이진 덧셈기의 연결 방법에 따라 부호어가 결정 연결 방법을 잘 선택하면 부호어 비트열간의 거리가 길어짐 오류정정 성능이 향상 구속장 K가 주어졌을 때 연결 방법을 찾는 문제는 매우 복잡 일반적인 해법은 존재하지 않으나 K < 20 일 때 컴퓨터에 의해 성능이 우수한 코드가 발견됨

73 3.5 컨벌루션 코드(convolution code)-6
컨볼루션 부호화기(계속) (2, 1, 3) 컨벌루션 부호화기의 예 : r =k/n= 0.5 k = 1 : 한 비트씩 정보 비트가 입력 n = 2 : 합 비트의 입력에 대해 두 비트의 부호어가 출력 K = 3 : 한 개의 현 정보 비트와 두 개의 과거 정보 비트를 조합 출력의 비트율 : 2Rb

74 3.5 컨벌루션 코드(convolution code)-7
컨볼루션 부호화기(계속) 상태 값의 초기화 메시지 비트가 처음 입력될 때 부호화기의 상태는 모두 0 정보 비트는 K 개의 클럭 시간 동안 시프트 레지스터에 체류 출력 부호어의 생성에 영향을 미침 마지막 메시지 비트가 입력되는 순간 부호화가 종료되는 경우 마지막 비트는 한 클럭 시간 외에는 부호어 생성에 작용 불가 K – 1 클럭 시간 동안 부호어 생성을 위해 더미 비트가 필요 부호화기 꼬리 비트(encoder tail bit) 더미(dummy) 비트인 K – 1 개의 0 비트 컨벌루션 코드를 사용하는 통신 시스템에서 꼬리 비트 사용 예 정보 비트열을 프레인 단위로 분할하여 전송 데이터 프레임: 정보 비트+꼬리 비트인 K – 1 개의 0 비트로 구성 다음 프레임이 시작 되기 전에 자연스럽게 초기 상태가 유지

75 3.5 컨벌루션 코드(convolution code)-8
컨볼루션 부호화기(계속) (2, 1, 3) 컨벌루션 부호화기의 예 : r = ½ = 0.5

76 3.5 컨벌루션 코드(convolution code)-9
컨볼루션 부호화기의 표현 부호화기 연결 벡터나 K - 1 차의 발생 다항식으로 표현이 가능 부호화기에 대한 연결 벡터 예 발생 다항식의 예 컨벌루션 코드 해석 방법 상태 천이도(state transition) 코드 계보(code tree) 코드 트렐리스 다이어그램(code trellis diagram)

77 3.5 컨벌루션 코드(convolution code)-10
컨볼루션 부호화기의 표현(계속) 상태 천이도(state transition) 그림3.18의 부호화기를 고려 : K = 3 메시지 비트(꼬리 비트 포함) : 부호화기의 상태 수 : 2K – 1 = 4 개 상태의 표현 : a = 00, b = 10, c = 01, d = 11 상태 천이 과정 : 표 13.6 상태 입력

78 3.5 컨벌루션 코드(convolution code)-11
컨볼루션 부호화기의 표현(계속) 상태 천이도(state transition)(계속) 부호화기의 상태 천이도 : 레지스터 초기값이 모두 0일 때 현재 상태에서 천이할 수 있는 다음 상태는 오직 2개뿐임 장점 : 매우 간결하게 표현 단점 : 시간에 따라 상태의 천이와 출력 코드의 생성 추적이 곤란

79 3.5 컨벌루션 코드(convolution code)-12
컨볼루션 부호화기의 표현(계속) 상태 천이도(state transition)(계속) 부호화기의 상태 천이도 : 레지스터 초기값이 다를 때

80 3.5 컨벌루션 코드(convolution code)-13
컨볼루션 부호화기의 표현(계속) 코드 계보(code tree) 상태 천이도에 시간 차원을 추가 입력 비트가 0이면 위로, 1 이면 아래로 천이 장점 : 입력 비트열에 따라 부호화기에서 코드가 순차적으로 표현 단점 : 메시지에 따라 가지가 지수적으로 증가 그림으로 계속 그려나가기 곤란 코드 트렐리스 다이어그램으로 코드 계보 방식의 단점을 보완

81 3.5 컨벌루션 코드(convolution code)-14
컨볼루션 부호화기의 표현(계속) 코드 계보(code tree)(계속)

82 3.5 컨벌루션 코드(convolution code)-15
컨볼루션 부호화기의 표현(계속) 코드 트렐리스 다이어그램(code trellis diagram) 3번의 가지 분할 후에 t4부터는 동일한 가지 분할 과정이 반복 초기 상태로부터 K 번의 가지 분할 이후에 동일 가지 분할이 반복 트렐리스 다이어그램은 반복성 구조를 이용하여 격자형으로 표현

83 3.5 컨벌루션 코드(convolution code)-16
블록 코드의 복호(decoding) 오류가 있는 수신 부호어 벡터를 유효한 부호어 벡터들과 비교 길이 n 비트의 고정된 부호어 벡터의 거리를 비교 거리가 제일 가까운 부호어 벡터를 송신된 부호어로 판단 블록 단위로 부호화 및 복호화가 독립적으로 수행 컨볼루션 코드의 복호 메시지어 단위로 독립적인 부호화가 이루어지지 않음 메시지어 비트는 연속적으로 부호어 생성에 영향을 미침 최우(maximum likelihood : ML) 복호를 사용 전송 프레임 전체를 블록 길이로 설정 가능한 모든 메시지 비트열에 의한 상태 천이도를 따라 유효한 부호어 비트열 집합을 만들어 저장 수신 부호어 비트열과 유효한 부호어 비트열들의 거리를 비교 최단 거리의 부호어 비트열을 선택하는 방법을 사용

84 3.5 컨벌루션 코드(convolution code)-17
컨볼루션 코드의 복호(계속) 컨벌루션 코드의 최우(ML) 복호 코드 계보나 코드 트렐리스를 따라 모든 가능한 경로를 수신 부호 비트열과 비교하여 가능성이 제일 높은 경로를 선택하는 것 문제점 프레일 길이가 크면 부호어 길이가 너무 크므로 저장하거나 비트열들을 비교하는 것이 곤란 비터비(Viterbi) 복호 알고리즘 ML 복호를 위해 연산량을 줄이는 효율적인 방법을 제시 모든 가능한 코드열의 집합을 찾는 것이 아니라 한 번에 한 단씩 가장 가능성이 높은 코드열을 탐색 각 상태로 들어오는 트렐리스 경로들과 수신 코드열의 거리를 비교 최우 경로의 가능성이 없는 경로는 고려 대상에서 제거

85 3.5 컨벌루션 코드(convolution code)-18
컨볼루션 코드의 복호(계속) 비터비(Viterbi) 복호 알고리즘(계속) 생존 경로(surviving path) 어떤 상태로 들어오는 경로가 2 개가 있을 때 수신 코드열과 거리가 더 짧은 경로를 의미 복호 과정에서는 상태별로 생존 경로만 남기고 다른 경로를 제거 연산량을 감소 수신된 코드 비트열과 최단 거리인 코드 비트열의 탐색 과정 가능성이 있는 코드 경로 후보 집합을 만들어 가면서 가능성이 없는 경로는 삭제하고 적은 수의 생존 경로 중에서 최종 복조 경로를 선택 비터비 복호의 예 (2, 1, 3) 부호화기에 메시지어가 입력 : u = 전송되는 코드열 : v = 채널을 통해 수신된 코드열 : z =

86 3.5 컨벌루션 코드(convolution code)-19
컨볼루션 코드의 복호(계속) 비터비 복호의 예(계속) 부호화기 및 복호기 트렐리스 다이어그램

87 3.5 컨벌루션 코드(convolution code)-20
컨볼루션 코드의 복호(계속) 비터비 복호의 예(계속) 부호화기 트렐리스 : 상태천이 가지 위에 부호어를 표기 복호기 트렐리스 상태천이 가지 위에 그 가지의 부호어와 수신 부호어의 거리를 표시 복호 과정 각 단 ti에서 누적 해밍 경로 거리(path metric)를 계산 경로를 형성하는 가지들의 거리를 모두 더한 값 어떤 상태에 이르는 경로가 두 개일 때 짧은 경로만 남기고 제거

88 3.5 컨벌루션 코드(convolution code)-21
컨볼루션 코드의 복호(계속) 구체적인 비터비 복호 과정 각 단에는 2K-1 = 4 개의 상태가 존재 : a = 00, b = 10, c = 01, d = 11 각 상태에 이르는 경로에 대한 경로 거리 : λa, λb, λc, λd 시간 t1 에서의 처리과정 모든 코드는 00의 상태에서 출발 t1 에서의 상태는 00 = a 시간 t2 에서의 처리과정 a 에서 천이할 수 있는 상태 : a, b a → a, a → b 의 경로만 가능 a → a 의 가지의 거리 : 2 a → a 의 가지에 대한 코드 : 00 a → a 의 수신 코드 : 11 a → b 의 가지의 거리 : 0 a → b 의 가지에 대한 코드 : 11 a → b 의 수신 코드 : 11 00 11 z =

89 3.5 컨벌루션 코드(convolution code)-22
컨볼루션 코드의 복호(계속) 구체적인 비터비 복호 과정(계속) 시간 t3 에서의 처리과정 4개의 모든 상태에 도달하는 경로가 가능 a 에 도달하는 경로 : a → a → a b 에 도달하는 경로 : a → a → b c 에 도달하는 경로 : a → b → c d 에 도달하는 경로 : a → b → d 모든 경로가 생존 경로임 각 상태에 들어오는 경로는 한 개뿐이므로 a → a → a 의 가지의 거리 : 3 a → a → b 의 가지의 거리 : 3 a → b → c 의 가지의 거리 : 2 a → b → d 의 가지의 거리 : 0 00 11 10 01 z =

90 3.5 컨벌루션 코드(convolution code)-23
컨볼루션 코드의 복호(계속) 구체적인 비터비 복호 과정(계속) 시간 t4 에서의 처리과정 4개의 모든 상태에 도달하는 경로가 가능 a 의 경로 : a → a → a → a, a → b → c → a b 의 경로 : a → a → a → b, a → b → c → b c 의 경로 : a → a → b → c, a → b → d → c d 의 경로 : a → a → b → d, a → b → d → d 생존 경로를 선택 : 짧은 가지 거리를 선택 a → a → a → a : 4 > a → b → c → a : 3 a → a → a → b : 4 > a → b → c → b : 3 a → a → b → c : 5 > a → b → d → c : 0 a → a → b → d : 3 > a → b → d → d : 2 t1 과 t2 사이의 생존 경로는 단 1개 첫 번째 복호 비트 출력을 의미 생존 경로가 점선이므로 메시지 비트는 1 첫 번째 출력이 나올 때 까지의 지연시간 고정된 값이 아니라 보통 구속장의 5배 정도

91 3.5 컨벌루션 코드(convolution code)-24
컨볼루션 코드의 복호(계속) 구체적인 비터비 복호 과정(계속) 시간 t5 에서의 처리과정 4개의 모든 상태에 도달하는 경로가 가능 a 의 경로 : ab → c → a → a, ab → d → c → a b 의 경로 : ab → c → a → b, ab → d → c → b c 의 경로 : ab → c → b → c, ab → d → d → c d 의 경로 : ab → c → b → d, ab → d → d → d 생존 경로를 선택 : 짧은 가지 거리를 선택 ab → c → a → a : 4 > ab → d → c → a : 1 ab → c → a → b : 4 > ab → d → c → b : 1 ab → c → b → c : 3 < ab → d → d → c : 4 ab → c → b → d : 5 > ab → d → d → d: 2 t2 과 t3 사이의 생존 경로는 2개 두 번째 복호 비트 출력은 미 결정

92 3.5 컨벌루션 코드(convolution code)-25
컨볼루션 코드의 복호(계속) 구체적인 비터비 복호 과정(계속) 시간 t6 에서의 처리과정 생존 경로를 선택 : 짧은 가지 거리를 선택 ab → c → b → c → a : 4 > ab → d → c → a → a : 2 ab → c → b → c → b : 4 > ab → d → c → a → b : 2 ab → d → c → b → c : 3 > ab → d → d → d → c : 2 ab → d → c → b → d : 1 < ab → d → d → d → d : 4 t2 과 t3 사이의 생존 경로는 단 1개 두 번째 복호 비트 출력을 결정 생존 경로가 점선이므로 메시지 비트는 1

93 3.5 컨벌루션 코드(convolution code)-26
컨볼루션 코드의 복호(계속) 비터비 복호기의 복잡도 메시지 비트의 수에 무관 상태의 개수에 비례 복잡도는 구속장의 지수승에 비례 컨벌루션 코드의 성능 구속장이 커짐에 따라 좋아짐 복잡도와 성능에서의 타협이 요구 많은 경우 구속장을 5 ≤ K ≤9 정도의 범위에서 사용

94 3.5 컨벌루션 코드(convolution code)-27
디지털 변조 및 복조 채널 부호화기에서 출력된 부호어 비트열을 변조하여 전송 수신된 신호를 비트열로 복조하여 채널 복호기에 입력 경판정 복호와 연판정 복호 방법이 사용

95 3.5 컨벌루션 코드(convolution code)-28
경판정 복호(hard decision decoding) 비트 구간마다 복조기에서 1/0을 판정하여 채널 복호기에 입력 결정변수(정합필터 출력)이 문턱 값보다 큰지 작은 지만 인식 문턱 값에 얼마나 근접한지에 대한 정보를 미 제공 잡음이 없는 경우 결정변수는 문턱 값에 비해 상당히 떨어져 있음 복조기의 판정에 신뢰도가 높다는 것을 의미 잡음이 많이 있는 경우 결정변수는 문턱 값에 근접 비트 판정의 신뢰도가 낮음을 의미 : 판정 오류 초래 우려

96 3.5 컨벌루션 코드(convolution code)-29
연판정 복호(soft decision decoding) 비트 판정과 함께 판정에 대한 신뢰도 정보를 복호기에 제공 결정변수의 값과 문턱 값의 떨어져 있는 정도에 대한 정보 제공 연판정에서는 정합필터의 출력 영역을 여러 개로 분할 어떤 영역에 속해 있는가를 표현 8개 영역으로 분할한 경우 : 3비트를 사용 000, 111 : 높은 신뢰도를 표현 011, 100 : 낮은 신뢰도를 표현 결정변수의 영역을 2개로 분할하면 경판정과 동일 연판정 복호는 복조기의 판정 결과에 대한 신뢰도를 제공 비트오율 성능이 개선 3 비트 연판정 복호기는 경판정 복호기보다 약 2.75 dB 를 개선 분할 비트 수를 크게 할수록 성능은 향상되나 메모리 크기가 증가 약 3 dB 정도의 성능 개선이 얻어지기 때문에 통상 3 비트를 사용

97 3.5 컨벌루션 코드(convolution code)-30
경판정과 연판정

98 3.5 컨벌루션 코드(convolution code)-31
연판정 복호(계속) 연판정 복호는 보통 블록 코드와 같이 사용하지 않음 연판정 복호를 사용하면 연산의 복잡도가 크게 증가 : 구현이 곤란 연판정 복호는 컨벌루션 코딩에서 많이 사용 비터비 복호기에 심볼 단위의 부호어가 입력되더라도 연산의 복잡도는 크게 증가하지 않음

99 3.5 컨벌루션 코드(convolution code)-32
경판정 복호의 성능 부호율이 ½인 컨벌루션 코드

100 3.5 컨벌루션 코드(convolution code)-33
연판정 복호의 성능 부호율이 ½인 컨벌루션 코드

101 3.5 컨벌루션 코드(convolution code)-34
컨벌루션 코드의 응용 위성통신 : VSAT, DBS(HDTV), INMARSAT NASA r = ½, K = 7 인 표준 컨벌루션 코드를 사용 IS-54 TDMA Cellular Standard r = ½, K = 6 인 컨벌루션 코드를 사용 GSM Cellular Standard r = ½, K = 7 인 컨벌루션 코드를 사용 IS-95 CDMA Cellular Standard 순방향 채널 : r = ½, K = 9 인 컨벌루션 코드를 사용 역방향 채널 : r = ⅓ , K = 9 인 컨벌루션 코드를 사용

102 과제-1 부호율이 1/3과 1/5인 반복 코드를 사용하는 시스템이 있다.이진대칭채널(BSC)을 가정하고 부호화된 비트가 채널을 통해 전송될 때 오류가 발생할 확률이 p이다. 두 시스템의 부호어오류 확률과 비트오류 확률을 구하라. (3, 1, 3) 컨벌루션 부호화기의 발생 다항식이 다음과 같을 때 상태 천이도, 코드 계보, 트렐리스 다이어그램을 그려라. 정보 데이터가 일 때 부호화기 꼬리 비트를 포함하여 정보비트가 부호화기에 입력될 때 출력 부호어를 구하라. 쉬프트 레제스터의 내용은 초기 상태가 모두 0이라고 가정한다.