2022.06.06 학과공부. 데이터통신 chapter 6.
Error Detection and Correction
Summary
- Types of Errors
- Error detection
- Parity Check
- Internet Checksum
- Cyclic Redundancy Check
- Forward Error Correction
1. Types of Errors
- Error : 전송 중에 0이 1로, 1이 0으로 바뀌는 경우
- Single bit errors : 한개의 비트가 바뀐 Error by White noise -> 검출과 수정 easy(Parity bit)
- Burst errors : 에러가 연속적(두 개 이상의 비트)으로 발생한 경우의 Error by Impulse noise
2. Error detection
- Error는 설계(Design)에 관계 없이 발생한다.
- Error를 검출할 수 있는 Code를 전송체계에 추가한다.
- 재계산, Error check by Receiver -> Error check가 안될 수 있음.
- Ex) Parity Check 등
3. Parity Check
- Parity Check : 비트들의 수가 짝수인지 홀수인지를 체크하여 기준에 따라 1 혹은 0을 첨가하여 오류가 발생된지 여부를 체크하는 방식.
- Odd Parity : Synchronous에 쓰인다.
- Even Parity : Asynchronous에 쓰인다.
- 단점 : 짝수 개 오류(bit가 2n개 발생)는 검출이 어렵다. -> 더 강력한 방식이 필요함
4. Internet Checksum
- 많은 인터넷 표준 프로토콜(IP, TCP, UDP)들이 사용하는 Error detecting code이다.
- Ones-complement operation(1의 보수) : 0을 1로 바꾸고 1은 0으로 바꾸는 방식
- Ones-complement addition : 두 수를 binary integers로서 다루고, 더한다, 여기서 만약 가장 왼쪽 비트에서 carry(올림수)가 발생하면 합에 1을 더한다.
5. Cyclic Redundancy Check(CRC)
- 가장 보편적이고 강력한 Error detecting code임.
- k bit 블록이 주어졌을때, transmitter는 미리 약속된 숫자로 나눌 수 있는 (n-k) bit frame check sequence(FCS)를 발생시킨다.
- Receiver는 다음에 올 frame을 그 숫자로 나눈다.
CRC Process Example
- 만약, CRC 발생 코드 P(x)를 x^3 + x^2 + 1 이라 하면 이는 곧 1101임 -> 최고차 차수가 3 -> 000 준비
- 전송할 데이터 G(x)가 110010 이면 110010'000'이라고 준비된 000을 붙임
- 모듈로 연산을 통해 110010000 / 1101 을 함 -> 몫 : 100100, 나머지 : 100 (3비트)
- 최종적으로 전송하는 코드 = 정보코드(110010) + CRC(100, 나머지 값) = 110010100
- 이번엔 전송 코드 110010100을 CRC 코드 1101로 나눔
- 110010100 / 1101(CRC) = 몫 : 100100, 나머지 : 000(No Error) -> 오류 검출 완료
6. Forward Error Correction
- 일반적으로 오류가 감지되면 데이터 block을 재전송해야 한다. -> 무선에서는 이것이 부적절하다.
- 무선에서의 단점 : Bit error rate(BER)이 무선에서는 꽤 높음, Propagation delay가 single frame의 전송시간에 비해 매우 길다.
- 도착한 bits를 기반으로 오류를 수정해야 한다.
- Codeword : 전송의 끝에서 data의 각 k-bit block이 FEC Encoder를 사용하는 n-bit block에 매핑되어 있는 것
Block Code Principles
- Hamming distance : 두 개의 길이가 '같은' 문자열 사이의 거리를 측정 -> 몇 개의 문자를 바꿔야 두 문자열이 같아 지느냐? -> 1011 and 0111 : 2
- Redundancy of the code : 보내고자 하는 코드가 "12345125"라고 가정하자. 이를 그대로 전송하는 대신 {1 → "one", 2 → "two", 3 → "three", 4 → "four", 5 → "five"} 라는 규칙 아래 인코딩(encoding) -> "xne two thrae fqur frve one twl five"로 수신 -> "one two three four five one two five"로 충분히 해석 가능.( 반복되는 비트 대 대이터 비트의 비율 : (n-k)/k )
- Code Rate : 데이터 bits 대 전체 bits의 비율(k/n) -> 코드가 없는 경우와 동일한 데이터 속도로 데이터를 전송하는 데 필요한 추가 대역폭의 측정값.
출처 : Data and Computer Communication, 대학교 데이터통신 수업(by 김영천 교수님)