junyeokk
Blog
Network·2025. 06. 14

Error detection, Error correction

%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA_2025-06-04_%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB_1.10.36.png
  • 데이터가 전송되는 과정에서 신호 약화나 잡음 때문에 비트가 바뀌는 오류가 발생할 수 있음
  • 링크 계층에서는 이러한 비트 오류를 탐지해서 잘못된 데이터를 버리거나 재전송을 요청함
  • 오류 검출은 100% 완벽하지 않음
    • 아주 드물지만 감지되지 않는 오류도 있을 수 있음
    • 하지만 EDC 필드가 클수록 오류 검출률은 높아짐
    • 즉, 더 많은 체크 비트를 사용하면 더 정밀하게 오류를 잡아낼 수 있음
  • 에러가 감지되면 보통 프레임을 폐기하고, 상위 계층이 재전송을 유도하거나, 무선 링크라면 링크 계층에서 자체 재전송을 할 수도 있음

오류 검출의 기본 구조

  • D (Data)
    • 오류 검출을 적용할 데이터
    • 보통은 실제 데이터 비트와 헤더 일부까지 포함됨
  • EDC (Error Detection and Correction bits)
    • 오류 검출을 위한 추가 비트들
    • 패리티 비트, 체크섬, CRC 등

프레임 전송 전 구조

  • D + EDC → 송신자가 전송

수신 시 구조

  • D’ + EDC’ → 수신자가 오류가 있는지 확인
  • 수신자가 D’의 모든 비트가 유효한지 확인
    • 유효하면 OK
    • 오류가 발견되면, 오류 감지되고 프레임 폐기 또는 재전송 요청

Parity Checking (패리티 검사)

%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA_2025-06-04_%E1%84%8B%E1%85%A9%E1%84%92%E1%85%AE_12.36.53.png

전송 데이터에 추가적인 비트(패리티 비트)를 붙여서, 전송 중 오류가 발생했는지 확인하는 방식

단일 비트 패리티 (single-bit parity)

  • 데이터를 전송할 때, 1의 개수가 짝수/홀수인지에 따라 패리티 비트를 추가함
  • 짝수 패리티라면, 데이터의 1의 개수가 짝수가 되도록 패리티 비트를 설정
    • 수신 측에서는 다시 1의 개수를 세고, 짝수가 아니면 오류 발생 감지
    • 간단하고 계산이 빠르지만, 짝수 개의 비트 오류는 감지하지 못함
  • 오류를 감지만 하고 수정은 할 수 없음

이차원 패리티 (two-dimensional bit parity)

  • 데이터를 행렬처럼 정렬하고, 각 행과 각 열에 대해 각각 패리티 비트를 붙이는 방식
  • 행과 열 양쪽에 패리티를 붙이므로 오류가 생긴 위치를 정확히 찾을 수 있음
  • 특정 행과 특정 열의 패리티 오류가 동시에 발생하면 그 교차점에 오류가 있다고 판단함
  • 단일 비트 오류는 검출, 수정 가능
  • 이중 오류 이상에서는 오류 위치 파악이 힘들고, 오버헤드(패리티 비트 수)가 늘어남

Internet checksum

%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA_2025-06-04_%E1%84%8B%E1%85%A9%E1%84%92%E1%85%AE_12.51.24.png

전송 중 비트가 뒤바뀌는 오류(flip)를 감지하는 것이 Internet checksum의 목적

송신 측 (sender)

  • UDP 세그먼트 전체를 16비트 정수 단위로 쪼갬
    • 세그먼트의 데이터뿐 아니라 UDP 헤더, 필요시 IP 주소도 포함
    • 16비트씩 읽어서 계산함
  • 1의 보수 합(one’s complement sum)을 구함
    • 일반적인 덧셈과 비슷하지만, 합이 16비트를 넘어가면 넘친 비트를 다시 더해줌
      • 전파된 비트를 한 번 더 더해주므로, 전송 중 발생할 수 있는 일부 오류에 대해서도 검출할 수 있도록 함
  • 계산된 체크섬 값을 UDP 헤더의 checksum 필드에 기록

수신 측 (receiver)

  • 받은 세그먼트를 동일하게 16비트 단위로 나눔
  • 다시 1의 보수 합을 계산
  • 결과가 0xFFFF이면 OK, 아니면 오류가 감지됨

Cyclic Redundancy Check (CRC)

%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA_2025-06-04_%E1%84%8B%E1%85%A9%E1%84%92%E1%85%AE_1.10.33.png

데이터를 다항식으로 간주하고, 특정 생성 다항식(G)을 기준으로 나머지를 계산해서 오류를 검출하는 방식

  • 복잡한 오류도 잘 잡아냄
  • 모든 ‘burst error’가 r + 1 비트 미만일 경우 100% 검출 가능
  • Ethernet, Wi-Fi (802.11), HDLC 등 다양한 프로토콜에서 실제 사용

송신 측

  • D (Data)
    • 보낼 데이터 비트를 2진수 숫자로 간주
  • G (Generator)
    • r + 1 비트 길이의 생성 다항식
    • 미리 정해져있음
    • r비트의 CRC(R)을 계산해야 함
      • D에 r개의 0을 덧붙인 D⋅2rD·2^r을 G로 나눈 나머지(R)를 구함
      • 이 R을 데이터 뒤에 붙여서 보냄
    • 전송되는 데이터 = <D, R>
      • 이 전체 비트 시퀀스가 G로 나누어 떨어지도록 구성

수신 측

  • <D, R>을 그대로 받아서 같은 G로 나눔
  • 나머지가 0이면 OK, 나머지가 0이 아니면 오류 발생
%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA_2025-06-04_%E1%84%8B%E1%85%A9%E1%84%92%E1%85%AE_1.16.39.png
  • D⋅2r XOR R≡0 (mod G)D·2^r \space XOR \space R ≡ 0 \space (mod \space G)
    • 즉, 전송 비트가 GG로 나누어 떨어지게 만드는 RR을 찾아야 함
  • D⋅2r=101110000, G=1001D·2^r = 101110000, \space G = 1001
  • 101110000÷1001101110000 ÷ 1001 → 나머지 R=011R =011
  • 전송 데이터 = 1001+0111001 + 011