오류정정기법 FEC, BEC

개념

송신한 데이터가 제대로 도달되지 않거나, 전송도중 오류 발생시 검출하고 오류를 수정하는 기능

기법

분류

후진오류수정

(Backward Error

Correction, BEC)

전송된 데이터에 오류가 발생된 경우, 송신 측에 오류 사실을 알려 재전송으로 복원하는 방식

오류

검출

방식

- 패리티 검사(Parity Check) 방식

- 블럭합 검사(Block Sum) 방식

- 순환중복 검사(CRC) 방식

  - 검사합 검사(Check Sum) 방식

자동

반복

요청

(ARQ)

  - Stop and Wait 방식

  - Go-back-N 방식

  - Selective-Repeat 방식

  - Adaptive ARQ 방식

전진오류수정

(Forward Error

Correction, FEC)

수신 측에서 오류를 스스로 검출/복원할 수 있는 방법으로 송신 시 오류복구를 위한 잉여 비트를 추가하여 전송하는 방식

해밍코드

수신측에서 오류가 발생한 비트를 찾아 재전송을 요구하지 않고 자신이 직접 오류를 수정(1개 오류 비트 수정)

상승코드

한계 값(경계 값), 순차적 디코딩을 이용하여 오류가 발생한 오류 비트를 모두 수정할 수 있는 방식

개념

전송된 세그먼트에 오류가 있는 경우, 오류처리 기능을 수행

기법

세그먼트 재전송 기법

송신측

- 송신측이 보낸 프레임에 대해 ACK 수신여부를 통해 확인

- 확인 응답, 시간 초과 여부를 사용하여 오류제어

* RTO : Retransmission Time Out

수신측

- CRC를 이용 오류검사

- 오류 발생한 프레임 재전송 요청

개념

데이터의 끝에 한 비트를 추가하여 1의 개수로 오류 유무 판단

종류

- 짝수 패리티(Even Parity) : 1의 전체 개수가 짝수 개가 되게 함

- 홀수 패리티(Odd Parity) : 1의 전체 개수가 홀수 개가 되게 함

동작과정

송신측

- 패리티 유형에 따라 패리티 비트 생성

- ASCII(7bit) + 패리티비트(1bit) 전송

수신측

- 1의 개수를 세어 오류 유무 판단(짝수 또는 홀수)

- 맞지 않으면, 재전송 요구

단점

짝수개의 오류는 검출 불가

예시

개념

이차원 패리티 검사, 가로와 세로로 두번 검사

다중 비트 오류와 폭주 에러를 검출할 가능성을 높임

동작과정

- 데이터를 일정 크기의 블록으로 묶음

- 각 블록을 배열의 열로 보고 패리티 비트를 계산하여 추가

- 각 블록의 행에 대한 패리티 비트를 추가한 후 재전송

단점

하나의 블록에서 두 개의 에러가 생기고 다른 블록의 동일한 위치에서 두개처럼 에러가 발생한 경우 검출 불가능

예시

개념

이진 나눗셈 연산을 기반으로 오류를 검출하는 방식

성능이 우수하며, 여러 비트에서 발생하는 집단 오류(burst error)도 검출 가능

계산방법

- Modulo-2 나눗셈 기반

* Modulo-2 연산의 덧셈과 뺄셈은 XOR 연산과 같음

송신측

- 전송하고자 하는 데이터 뒤에 n개의 0을 삽입

- 사전에 약속하여 결정된 n+1 비트의 수로 이진나눗셈을 수행하여 나머지를 구함

- 데이터+나머지 값을 전송

수신측

- 전송 받은 데이터에 이진 나눗셈 적용

- 연산 결과, 나머지가 0이면 오류 없음

예시

개념

전송 데이터의 맨 마지막에 앞서 보낸 모든 데이터를 다 합한 합계를 보수화하여 전송, 수신 측에서는 모든 수를 합산하여 검사하는 방법

동작과정

송신측

- 데이터 단위를 n 비트의 여러 세그먼트로 나눔

- 세그먼트 들의 전체 길이도 n 비트가 되도록 유지하면서 Checksum 생성

- 1의 보수 연산을 이용하여 전체 Checksum을 보수화함

- 원래 데이터의 끝에 삽입하여 네트워크를 통해 전송

수신측

- Checksum을 포함하여 모든 세그먼트들을 더했을 때 모든 비트가 1이 나오면 정상, 그렇지 않으면 오류

예시

송신측

전송하고자 하는 데이터 : (11100101, 01100110, 11100110)

최종 데이터 : (11100101, 01100110, 11100110, 11001110)

수신측

수신 받은 데이터 : (11100101, 01100110, 11100110, 11001110)

최종 합이 1이므로, 오류 없음

개수

데이터 비트의 수가 m 개이라면 패리티 비트 수 p는 2^p >= m + p + 1 관계식에 의해 결정

위치

해밍코드의 왼쪽부터 1, 2, 4, 8, …, 2^n-1번 자리

사례

데이터 비트 수가 4라면 패리티 비트 수는 3이 되고, 다음과 같이 1, 2, 4번 자리에 패리티 비트가 위치

구성

방법

7 비트 해밍코드에 대해 짝수 패리티를 수행한다고 했을 경우, 각 패리티 비트에 다음과 같이 패리티 체크를 수행하여 "1" 또는 "0"을 할당

- P1 : 1, 3, 5, 7 비트 자리에 대해 짝수 패리티 체크를 수행

- P2 : 2, 3, 6, 7 비트 자리에 대해 짝수 패리티 체크를 수행

- P3 : 4, 5, 6, 7 비트 자리에 대해 짝수 패리티 체크를 수행

사례

짝수 패리티로서 1001에 대한 해밍 코드

- P1=0, P2=0, P3=1

- 해밍코드 : 0011001

검출

방법

각 패리티 비트에 대한 체크를 수행하여 오류가 없으면 0, 오류가 있으면 1을 기록

사례

원래의 코드가 0011001이고, 짝수 패리티를 수행한다고 했을 때, 전송 후 에러가 발생하여  0010001이 수신

- P1은 비트 자리 1, 3, 5, 7을 점검하여 두 개의 1이 있으므로 오류가 없고, 따라서 0이 됨

- P2는 비트 자리 2, 3, 6, 7을 점검하여 두 개의 1이 있으므로 오류가 없고, 따라서 0이 됨

- P3는 비트 자리 4, 5, 6, 7을 점검하여 한 개의 1이 있으므로 오류가 발생하였고, 따라서 1이 됨

- 결과적으로 만들어진 2진 숫자는 P3P2P1 자리 순으로 하면 100이 되고, 이 값에 따라(십진수로 변환) 네 번째 자리에 오류가 발생 하였음을 검출하고 정정 가능

Stop-and-Wait ARQ

1. 개념

- 송신측이 하나의 프레임을 전송

- 수신측에서는 해당 프레임의 에러유무를 판단

- 에러가 없을 경우 송신측에게 ACK (Acknowledgement) 를 전송

- 에러가 있는 경우 NAK (Negative ACK) 를 전송하여 재전송 유도

2. 특징

- 흐름제어 방식 중에 가장 간단한 형태

- 한번에 한 개의 프레임만 전송

: Works well for a few large frames

- Destination can stop flow by not sending ACK

3. 단점

- 전송되는 프레임의 수가 한 개이므로 송신 측이 기다리는 시간이 길어져 전송효율 저하

- 송ㆍ수신측 간의 거리가 멀수록 각 프레임 사이에서 응답을 기다리는 데에 낭비되는 시간 때문에 효율 저하

4. 동작 과정

송신측은 데이터 전송후 ACK, NAK를 받을 때 까지 대기

- 수신측은 수신 프레임에 대하여 에러검사를 수행

 에러가 없으면 ACK를 송신, 에러가 있으면 NAK를 송신

- 송신측에서 NAK를 수신할 경우 프레임을 재전송

5. 예시

Sliding Window

ARQ

1. 개념

 - Continuous ARQ 이라고도 알려짐

 - 송신 측의 ACK를 받지 않고 전송 할 수 있는 Frame 수 N개를 하나의 블록으로 고정해 전송

 - Sliding-window

  variable-size window that allows a sender to transmit a specified number of frames before     an acknowledgement is received

  Sender must also keep a buffer of all frames which have been sent, but have not yet been     acknowledged.

2. 특징

 - 프레임의 송,수신은 순차적

 - 프레임에 순서번호를 삽입

 - 수신응답 대기의 오버헤드 감소

 - 수신측으로부터 응답 메시지가 없더라도 미리 약속한 윈도우의 크기만큼의 데이터 프레임을     전송

블록 전송 ARQ

(Go-Back-N)

1. 개념

 - Sliding-window ARQ 의 일종

 - Sender에서 에러 발생 확인은 Stop-and-wait 방식과 동일

 - Sender에서 Receiver가 보낸 NAK 수신

 - Sender에서 일정 Timer 동안 ACK or NAK을 수신 못함

 - 에러 발생 프레임부터 Sliding-window 사이즈 내의 Frame들 재전송

 - Receiver는 에러가 발생한 Frame 이후의 모든 Frame을 Discard

2. 동작 과정

 - 수신측이 4번 프레임이 잘못되었음을 인지하고 NAK를 전송

 - 송신측은 4번부터 Sliding-window 사이즈 내의 Frame들 재전송

선택적 재전송

(Selective Repeat)

1. 개념

 - Sliding-window ARQ 의 일종

 - 프레임 도착의 순서에 영향을 받지 않음

 - 에러가 발생한 프레임만 재전송

2. 특징

송신측과 수신측은 동일한 크기의 Sliding-window를 보유

 - 수신측은 프레임의 순서에 상관없이 수신

 - 반드시 각각의 프레임에 대한 수신확인을 수행

3. 동작 과정

 - 에러가 발생한 4번 프레임만 재전송

적응적 ARQ

(Adaptive ARQ)

 -전송 효율을 고려하여 데이터 오류 발생 확률에 따라 Frame 길이를 동적으로 변경하여 전송