오차 정정 방식

■ 오차 정정 방식의 개요

♠ C.E. Shannon

통신 채널이 주어지면 이 채널이 가질수 있는 최대 정보 전송률 C가 있     음을 증명.

♠ 오차 제어 방식

① 전방 오차 제어(FEC) : 단방향 시스템에서의 오차 제어 방식

블록 부호와 컨벌루션 부호로 구분

② 데이터 재전송 방식(ARQ) : 양방향 시스템에서의 오차 제어 방식

정지 대기 ARQ, 연속 ARQ(GBN ARQ, 선택적 반복 ARQ)

■ 블록 신호(Matlab Commnications Toolbox 참고)

● 선형 블록 부호

♠ 생성행렬

부호화 과정이 단순한 조사표를 이용해서 하는 것이라면, 그렇게 많은 부     호 벡터를 저장하기 위하여 메모리의 크기는 아주 커야할 것이다. 그러나     많은 부호 벡터를 저장하는 대신에 생성 행렬을 이용하여 필요한 부호      벡터를 생성함으로써 메모리의 크기를 줄일수가 있다.

♠ 체계적 선형 블록 부호

체계적 생성행렬을 쓰면, 그 배열의 항등행렬 부분을 저장할 필요가 없으     므로, 부호화의 복잡도를 줄여준다.

♠ 신드롬 테스트

① r(수신된 부호벡터)이 유효한 부호어인지를 결정하기 위해 r에 패리티        검정을 수행한 결과이다.

② 복호화 과정에 기초하여 선형 블록 부호의 중요한 성질은 정정 가능        한 오차 패턴과 신드롬을 일대일로 대응시킬 수 있다는 것이다.

♠ 오차정정

오차를 검출하는것뿐 아니라 이 검출된 오차 패턴을 이용하여 오차를 정     정할 수 있다.

● 부호화 능력

♠ 한 종류의 부호가 가지는 오차 정정 능력은 부호의 구조를 정의 하므로     써 조사할 수가 있다.

♠ 해밍 웨이트

해밍 웨이트 w(V)는 V(벡터)의 0이 아닌 디지트들의 개수로 정의된다.

♠ 해밍 거리

서로다른 요소들의 개수들로 정의

♠ 오차 검출과 정정

오차가 발생한 수신 벡터에 대해 오차의 검출은 가능하지만 정정은 항상     가능한 것이 아니라는 것을 분명히 알 수 있다.

● 순환 부호

♠ 궤환 천이 레지스터를 이용하여 쉽게 구현할 수 있으며, 신드롬도 이와      비슷한 궤환 천이 레지스터를 이용하여 쉽게 계산할 수 있다.

♠ 이진 순환부호의 성질

생성 행렬을 이용하여 블록 부호를 생성해냈던 것과 마찬가지 방법으로     생성 다항식을 이용하므로써 순환 부호를 만들 수 있다.

♠ 체계적 형식의 부호화

체계적 형식을 도입하면 복잡도가 줄어든다.

● 그 밖의 중요한 블록 부호

♠ 해밍 부호

최소거리 3을 가지며 한 블록내에 있는 1개의 모든 오차를 정정할 수 있     고, 2개 이하의 모든 오차를 검출할 수 있다.

♠ BCH 부호

다수의 오차 정정을 가능하게 하는 해밍 부호의 일반화된 부호방식

몇 백의 블록 길이에서 같은 블록 길이와 부호율을 갖는 부호 방식에       비해 더 좋은 성능을 나타낸다.

♠ Reed-Solomon 부호

같은 부호기 입력과 출력 블록 길이를 갖는 선형 부호에 대해 가능한 최     대 부호 길이와 최소 거리를 갖는다.

■ 컨벌루션 부호(Convolutional decoding)

♠ 컨벌루션 부호는 세가지 정수 n, k, K에 의해 표현될 수 있다.

♠ 컨벌루션 부호의 특성

블록부호와 달리 기억소자를 가지므로 k 튜플의 입력뿐만 아니라 이전의     (K-1)개의 k 튜플 입력에 관련되어 n 튜플의 출력을 발생시킨다.

● 컨벌루션 부호기의 표현

♠ 연결 벡터 및 다항식

♠ 상태도

상태도의 박스는 부호화기의 상태를 나타내며 상태 사이의 경로들은 부     호화기의 상태 천이로 인해 발생할 수 있는 출력부호어의 가지를 나타낸     다.

♠ 트리도

상태도로 부호화기의 특성을 나타낼 수 있지만 시간에 대한 표현이 불가     능하기 때문에 상태도에 시간의 차원을 부가한 트리도를 사용한다.

♠ 트렐리스도

반복적인 구조를 이용하므로 트리도보다 부호화기의 표현에 더많이 이용     된다.

● 컨벌루션 복호

♠ 비터비 복호 알고리듬

① 1967년에 개발되었고, 최대 근사 복호화를 수행하는 최적화 복호 방식        이지만 하드웨어 구성이 어려우므로 모든 응용에 최상의 방법은 아니        다.

② 비터비 복호화의 장점은 복호기의 복잡도가 부호열의 심볼 수에는

무관하다는 것이다.

③ 유사성 척도를 계산하여 가장좋은 매트릭을 가진 하나를 선택한다.

→ 생존경로

④ 최적 경로를 선택한다는 것은 최대 근사 매트릭 또는 최소 거리 매트        릭을 가진 부호어를 선택하는 것이다.

■ ARQ(Automatic Repear Request)

● 정지대기 ARQ

♠ 송신기에서 수신기로 부호어를 전송하고 나서 수신기로부터의 ACK 응답     신호를 기다리는 방식으로 만약 수신단에서 오차가 검출되면 NAK 신호     를 전송하고 송신단은 ACK 신호가 들어올때까지 기다린다.

♠ 정지 대기 ARQ 방식은 각 전송된 부호어에 대하여 인식 신호를 기다리     는 휴지시간 때문에 비효율적인 면을 가진다.

♠ ARQ시스템의 성능을 평가하는 방법

전송효율 : 단위 시간당 전송된 디지트 수에 대한 수신기에서 성공적으로                받아들인 평균 정보 디지트수의 비로써 정의한다.

♠ 위성통신과 같이 왕복 지연 시간이 길고 전송 속도가 빠른 경우에는 적     합하지 않다.

● GBN ARQ

♠ 송신단에서 부호어를 전송하고 난 후 그 부호어에 대한 응답신호를 기다     리지 않고 다음 부호어를 연속적으로 전송한다.

♠ 부호어를 연속저긍로 전송 및 재전송하기 때문에 전지 대기 ARQ방식에     비해 더 효율적이고 적절한 비용으로 실현될 수 있다.

♠ 채널 오차율이 작고 왕복 지연 시간이 작은 경우에는 만족할 만한 전송     효율을 얻는다.

● 선택적 재전송 ARQ 방식

♠ 부호어를 GBN ARQ시스템과 마찬가지로 연속적으로 전송하지만 NAK가     발생하였을 경우 송신단은 그 부호어만 재전송하게 된다.

♠ 오차가 검출된 부호어만을 선별해서 재전송하므로 부호어가 올바른 순서     로 수신자에게 전달되기 위해서는 오차가 검출된 부호어 다음에 들어온     부호어 중에서 오차가 없는 부호어를 저장하기위한 버퍼가 반드시 필요     하다. (무한대에 가까운 버퍼가 필요)

♠ 세가지 ARQ 방식중 가장 효율적이지만 시스템의 제어가 복잡하여 구현     이 어렵다.

♠ 선택적 재전송 ARQ시스템의 전송 효율은 채널 오차율에 의하여 결정되     므로 위성 통신과 같이 왕복 지연 시간이 길고 정보 전송 속도가 빠른      경우에 좋은 특성을 나타낸다.

● 하이브리드 ARQ 방식

♠ FEC 방식과 ARQ 방식을 적절히 결합

♠ FEC만 사용한 시스템에 비하여 신뢰도를 높이고, ARQ만 사용하는 시스     템에 비하여 전송 효율을 높인 결과가 발생하게 된다.

♠ 하이브리드 ARQ 방식의 분류

① 오차 검출과 정정을 동시에 수행하는 부호를 사용함으로서 오차 검출        만을 시도하는 ARQ 방식에서 사용하는 부호보다 더 많은 패리티 비        트를 필요로 한다. 따라서 채널 오차율이 낮은 경우에는 오히려 더 나        쁜 전송 효율을 나타낸다.

② 수신단에서 필요로 할 때만 오차 정정을 위한 패리티 디지트를 전송        하는 개념.

첫 번째 유형보다 복호가 다소 복잡해지지만 오차가 거의 없는 채널        에서는 여분의 패리티 비트의 낭비가 없으므로 효율적인 적응 방식이        된다.