오류정정기법 FEC, BEC
태그 :
- 개념
- 송신한 데이터가 제대로 도달되지 않거나, 전송도중 오류 발생시 검출하고 오류를 수정하는 기능
I. Data Link 계층과 Transport 계층의 오류제어 기법
가. Data Link 계층의 오류제어 기법
개념 |
송신한 데이터가 제대로 도달되지 않거나, 전송도중 오류 발생시 검출하고 오류를 수정하는 기능 |
|||
기법 분류 |
후진오류수정 (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개 오류 비트 수정) |
|||
상승코드 |
한계 값(경계 값), 순차적 디코딩을 이용하여 오류가 발생한 오류 비트를 모두 수정할 수 있는 방식 |
나. Transport 계층의 오류제어 기법
개념 |
전송된 세그먼트에 오류가 있는 경우, 오류처리 기능을 수행 |
||
기법
|
세그먼트 재전송 기법
|
||
송신측 |
- 송신측이 보낸 프레임에 대해 ACK 수신여부를 통해 확인 - 확인 응답, 시간 초과 여부를 사용하여 오류제어 * RTO : Retransmission Time Out |
||
수신측 |
- CRC를 이용 오류검사 - 오류 발생한 프레임 재전송 요청 |
II. Data Link 계층의 오류 검출 기법
가. 패리티 검사(Parity Check)
개념 |
데이터의 끝에 한 비트를 추가하여 1의 개수로 오류 유무 판단 |
|
종류 |
- 짝수 패리티(Even Parity) : 1의 전체 개수가 짝수 개가 되게 함 - 홀수 패리티(Odd Parity) : 1의 전체 개수가 홀수 개가 되게 함 |
|
동작과정 |
송신측 |
- 패리티 유형에 따라 패리티 비트 생성 - ASCII(7bit) + 패리티비트(1bit) 전송 |
수신측 |
- 1의 개수를 세어 오류 유무 판단(짝수 또는 홀수) - 맞지 않으면, 재전송 요구 |
|
단점 |
짝수개의 오류는 검출 불가 |
|
예시 |
나. 블록합(Block Sum) 검사
개념 |
이차원 패리티 검사, 가로와 세로로 두번 검사 다중 비트 오류와 폭주 에러를 검출할 가능성을 높임 |
동작과정 |
- 데이터를 일정 크기의 블록으로 묶음 - 각 블록을 배열의 열로 보고 패리티 비트를 계산하여 추가 - 각 블록의 행에 대한 패리티 비트를 추가한 후 재전송 |
단점 |
하나의 블록에서 두 개의 에러가 생기고 다른 블록의 동일한 위치에서 두개처럼 에러가 발생한 경우 검출 불가능 |
예시 |
다. 순환중복검사(CRC, Cyclic Redundancy Check)
개념 |
이진 나눗셈 연산을 기반으로 오류를 검출하는 방식 성능이 우수하며, 여러 비트에서 발생하는 집단 오류(burst error)도 검출 가능 |
|
계산방법 |
- Modulo-2 나눗셈 기반
* Modulo-2 연산의 덧셈과 뺄셈은 XOR 연산과 같음 |
|
송신측 |
- 전송하고자 하는 데이터 뒤에 n개의 0을 삽입 - 사전에 약속하여 결정된 n+1 비트의 수로 이진나눗셈을 수행하여 나머지를 구함 - 데이터+나머지 값을 전송 |
|
수신측 |
- 전송 받은 데이터에 이진 나눗셈 적용 - 연산 결과, 나머지가 0이면 오류 없음 |
|
예시 |
라. 검사합(Check Sum) 검사
개념 |
전송 데이터의 맨 마지막에 앞서 보낸 모든 데이터를 다 합한 합계를 보수화하여 전송, 수신 측에서는 모든 수를 합산하여 검사하는 방법 |
|
동작과정 |
송신측 |
- 데이터 단위를 n 비트의 여러 세그먼트로 나눔 - 세그먼트 들의 전체 길이도 n 비트가 되도록 유지하면서 Checksum 생성 - 1의 보수 연산을 이용하여 전체 Checksum을 보수화함 - 원래 데이터의 끝에 삽입하여 네트워크를 통해 전송 |
수신측 |
- Checksum을 포함하여 모든 세그먼트들을 더했을 때 모든 비트가 1이 나오면 정상, 그렇지 않으면 오류 |
|
예시 |
송신측 |
전송하고자 하는 데이터 : (11100101, 01100110, 11100110) 최종 데이터 : (11100101, 01100110, 11100110, 11001110) |
수신측 |
수신 받은 데이터 : (11100101, 01100110, 11100110, 11001110) 최종 합이 1이므로, 오류 없음 |
III. Data Link 계층의 오류 정정 기법
가. 해밍코드(Hamming Code)
1) 개념
- 필요한 수 만큼의 패리티 비트를 정해진 위치에 두어 오류가 발생했을때 오류 발생 비트를 알아내어 정정이 가능하도록 하는 오 류 정정 코드
- 단일 오류 검출 및 정정
2) 패리티 비트의 개수와 위치
개수 |
데이터 비트의 수가 m 개이라면 패리티 비트 수 p는 2p >= m + p + 1 관계식에 의해 결정 |
|||||||
위치 |
해밍코드의 왼쪽부터 1, 2, 4, 8, …, 2n-1번 자리 |
|||||||
사례 |
데이터 비트 수가 4라면 패리티 비트 수는 3이 되고, 다음과 같이 1, 2, 4번 자리에 패리티 비트가 위치
|
3) 해밍코드 구성 방법
구성 방법 |
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 |
4) 해밍코드 오류 검출 및 정정 방법
검출 방법 |
각 패리티 비트에 대한 체크를 수행하여 오류가 없으면 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이 되고, 이 값에 따라(십진수로 변환) 네 번째 자리에 오류가 발생 하였음을 검출하고 정정 가능 |
나. ARQ (Auto Repeat request, 자동 반복요청)
1) 개념
- 수신 측에서 오류 프레임에 대한 재전송 요구 또는 에러 정정을 하는 기법
- 흐름 제어 (Flow Control) 기능과도 연계
2) 종류
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 길이를 동적으로 변경하여 전송 |
- 파이프라인(Pipeline)된 프로토콜의 2가지 접근방법으로 Go-Back-N, Selective Repeat 분류 가능