[CS] No. 1 - Data Communication : Error Detection & Correction

NewPlus·2022년 6월 6일
0

Computer Science

목록 보기
1/3

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

  • modulo-2 연산
    0 + 0 = 0 0 - 0 = 0
    0 + 1 = 1 0 - 1 = 1
    1 + 0 = 1 1 - 0 = 1
    1 + 1 = 0 1 - 1 = 0

  • 연산 예시 - CRC 인코딩

  1. 만약, CRC 발생 코드 P(x)를 x^3 + x^2 + 1 이라 하면 이는 곧 1101임 -> 최고차 차수가 3 -> 000 준비
  2. 전송할 데이터 G(x)가 110010 이면 110010'000'이라고 준비된 000을 붙임
  3. 모듈로 연산을 통해 110010000 / 1101 을 함 -> 몫 : 100100, 나머지 : 100 (3비트)
  4. 최종적으로 전송하는 코드 = 정보코드(110010) + CRC(100, 나머지 값) = 110010100
  • 연산 예시 - CRC 디코딩
  1. 이번엔 전송 코드 110010100을 CRC 코드 1101로 나눔
  2. 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 김영천 교수님)

profile
매일 매일 새로워지는 나 자신을 꿈꾸며

0개의 댓글