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

Slides:



Advertisements
Similar presentations
1 2 장. 데이터 통신. 2 데이터 통신망 형태  점대점 (point-to-point)  통신망 (communication network)  전화망 (PSTN: Public Switched Telephone Network)  LAN(Local Area Network)
Advertisements

오류 검출 및 정정  정보 전송시 발생하는 오류 검출 및 정정 코드  오류 검출 : 패리티비트, CRC 코드  오류 검출 및 정정 : 해밍코드  오류 검출 - 패리티비트 (parity bit)  비트 1 의 개수가 짝수 또는 홀수가 되도록 조절  간단한 오류.
1 비동기와 동기 전송 (Asynchronous and Synchronous Transmission) 전송링크를 통해 전송하기 위해 두 장치 사이의 긴밀한 협조와 동의가 필요 — 송 수신기간에 동기 (synchronize ) 를 맞추기 위한 비트들의 Timing( 전송률,
EMLAB Modeling of Digital Communication Systems using Simulink Chap2. Sinusoidal Simulink Model Chap3. Digital Communications BER Performance in AWGN (BPSK.
MINI 프로토콜 아날라이저 사용설명서 Ver1.1.
for Low Voltage Automatic Meter Reading System
제 3 호 농촌 어메니티 관광개발 정보 -농어촌체험 ∙ 휴양마을 지정제도- 농 촌 진 흥 청 농촌자원과.
11 장 데이터 링크 프로토콜 11.1 비동기식 프로토콜 11.2 동기식 프로토콜 11.3 문자-중심 프로토콜
7~9월 프로그램 광산구드림스타트 호 소식지 신체 / 건강 인지/언어 정서/행동
CDMA 이동통신시스템과 부호이론.
[새문안교회 정보화 사역 계획(안)] 2007년도 영상선교부
연구활동종사자 교육ㆍ훈련 수강방법 사무처 안전관리실
Hamming Code 이근용. 2 Error Control Error Detection Parity Check CRC Check Error Correction Hamming Code.
Young-Tae Han 데이터 링크 제어 Young-Tae Han
11 장 데이터 링크 프로토콜 11.1 비동기 프로토콜 11.2 동기 프로토콜 11.3 문자-중심 프로토콜
4 통신 프로토콜과 표준화, 최근 표준화 협력 방향.
Chapter 13 전송층 개요.
사용자 메뉴얼 차량용 4CH 블랙박스 매뉴얼 버전 : Version 2.1 Hardware Version : 2.0
*노동문제 * -비정규직 유효림 박지희 전향숙 황연두.
10장 오류 검출과 오류 정정 (Error Detection and Correction)
극동대학교 전자결재 구축 그룹웨어 결재자 교육.
2011년도 식품안전관리 지침 설명 자료.
제4장 채용관리 채용관리의 중요성과 기본전략 모 집 선 발 채용 형태의 변화 채용관리.
제 9 장의 구성 9.1 원천부호화 (Source Coding) 9.2 채널부호화 (Channel Coding) 연습문제
제 9 장의 구성 9.1 원천부호화(source coding) 9.2 채널부호화(channel coding)
2 Part 전자계산기 구조 1. 논리 회로 2. 자료 표현 및 연산 3. 명령어 및 프로세서 4. 명령 수행 및 제어 5.
4 컴퓨터에서 활용되는 디지털 논리회로 IT CookBook, 컴퓨터 구조와 원리 2.0.
3 디지털 코드 IT CookBook, 디지털 논리회로.
7장 목차 7.1 멀티미디어 네트워킹 응용 7.5 다양한 서비스 클래스 제공 7.2 스트리밍 저장 오디오 및 비디오
Chapter 11 Data Link Control.
발표제목 발표제목 둘째 줄 2000년 11월 송 홍 엽 연세대학교 전기전자공학과 송 홍 엽
WCDMA 기반 3G 이동통신 시스템   물리계층 전송방식 및 성능분석.
6장 무선과 이동 네트워크.
Chapter 5 링크 계층.
Data Communications 제 10 장 오류 제어와 흐름 제어.
PART 02 프로토콜 컴퓨터 네트워크 chapter 06 트랜스포트 계층 임효택.
PPP (Point-to-Point Protocol)
하드웨어 구현 - A/D 변환기(A/D converter) - 샘플링 주파수(Sampling frequency)
무선통신 기본지식 김 상 철.
Lecture #6 멀티미디어 데이터 압축 & 복원.
5 Part 정보 통신 개론 1. 정보 전송 이론 2. 데이터 전송 제어 3. 통신 회선 공유 4. 데이터 회선망 5.
Gamma(감마) 발표일 : 발표자 : 임정환.
6장 무선과 이동 네트워크.
오류정정부호 Viterbi decoder의 이해 및 Convolutional encoder 설계
osp.chungbuk.ac.kr/2012년 강의자료
(Error Detection and Correction)
재난 관리를 위한 위성정보 시스템의 활용방안 류 동 원 ㈜ 아이에스에스 P47.
Chapter 03. 디지털 코드.
Serial 통신(RS-232) 2 김성환 기계설계 자동화 공학부 비주얼베이직의 기초사항을 공부합니다.
제3장 채널코딩(Channel Coding)
담당교수 : 이봉운 디지털 통신공학 ’11-2 학기 담당교수 : 이봉운
디지털-아날로그 부호화.
Chapter 15 Transmission Control Protocol (TCP).
Chapter 03. 네트워크 통신.
소 방 안 전 교 육 (초등학교) 남 원 소 방 서.
논리회로 설계 및 실험 3주차.
AT-DMB Baseband decoder LP path IP 기술이전 자료
Transmission Control Protocol (TCP)
Young-Tae Han 오류 검출과 오류 정정 Young-Tae Han
10 장 데이터 링크 제어(Data Link Control)
2015 한국연구재단 글로벌박사 양성사업 변경사항 안내
디지털통신 시스템 설계 최대가능도(ML) 수신기.
CHAPTER 04 파일 설계(FiLE Design).
어떤 금속이 열전도가 빠른지 찾기 평택여자중학교 김수민.
공 학 입 문 경성현 금영섭.
K Nearest Neighbor.
수학 8나 대한 64쪽 II.도형의 성질 2. 사각형의 성질 §1. 평행사변형 (17/24) 평행사변형이 되는 조건.
<정보이론(Information Theory)> 제8장 채널의 특성과 상호정보
관리자 페이지에서 관리자 승인 1. 정기권 신규고객 1. 로그인 화면 2. 차량등록여부 확인 3. 개인정보 활용 동의
신입사원 OJT교육.
Presentation transcript:

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

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

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

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) 방식

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

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

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

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

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

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 : 한 비트까지의 오류를 정정

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

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개 이하의 비트 오류가 발생하면 오류 정정이 가능 반복 코드는 부호화/복호화 과정이 매우 간단 많은 잉여 비트 때문에 전송량이 크게 증가 우수한 채널 코딩 방식 : 적은 잉여 비트와 큰 오류 정정 능력

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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의 모든 행은 서로 상이 신드롬 참조표

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 = 11 01 01 10 01 01

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 = 11 01 01 10 01 01

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배 정도

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개 두 번째 복호 비트 출력은 미 결정

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

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

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

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

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

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

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

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

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

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 인 컨벌루션 코드를 사용

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