Chapter 06. (오류 탐지 및 수정)

에러의 종류

전송과 수신 사이에서 비트가 변경되는 경우를 "비트 오류"라고 합니다.

 

• Binary 1이 전송되고 Binary 0이 수신됨: 전송 중 1이 0으로 바뀌는 오류
• Binary 0이 전송되고 Binary 1이 수신됨: 전송 중 0이 1로 바뀌는 오류

[오류의 2가지 일반적인 유형]

1. 단일 비트 오류(Sigle-Bit Error) : 한 개의 비트만 변경되고 주변 비트에는 영향을 미치지 않는 상태

2. 버스트 오류 (Burst Error) : 연속된 비트 시퀀스에서 첫 번째와 마지막 비트를 포함하여 중간에 여러 비트가 잘못 수신되는 에러, 일반적으로 처리하기가 더 어려움

 

프레임 : 데이터 전송 과정에서 사용되는 기본 단위로, 하나 이상의 연속된 비트 시퀀스로 구성된 데이터 블록

• 헤더 : 프레임의 시작 부분에 위치, 송신자와 수신자 정보 또는 데이터 처리에 필요한 제어 정보를 담고 있음
• 페이로드 : 실제 전송되는 데이터의 본체, 사용자가 필요로 하는 주요 데이터가 포함됨
• 트레일러 : 프레임의 끝을 나타내며, 에러 검출 및 수정용 정보를 포함

프레임 에러 확률

1. 단일 비트 에러 확률이 증가하면, 프레임이 에러 없이 도착할 확률은 감소합니다.
   단일 비트 에러가 발생할 가능성이 높아질수록, 프레임 내에서 에러 없는 상태로 도달할 확률이 낮아집니다.
2. 프레임 길이가 길어질수록, 프레임이 에러 없이 도착할 확률은 감소합니다.
   프레임이 길어질수록 포함된 비트의 수가 증가하고, 이 중 하나라도 에러가 발생할 확률이 높아지기 때문입니다.

 

• Pb​: 비트가 에러로 수신될 확률 (Bit Error Rate, BER) :
  단일 비트가 잘못 수신될 확률로, 비트 에러율
• P1​: 프레임이 비트 에러 없이 도착할 확률 :
  프레임 내의 모든 비트가 정확히 수신되어 에러가 발생하지 않을 확률
• P2​: 에러 탐지 알고리즘이 사용되는 경우, 하나 이상의 비트 에러가 탐지되지 않은 상태로 프레임이 도착할 확률, 잔여 에러율(residual error rate) :
  에러 탐지 알고리즘의 한계로 인해 일부 에러가 탐지되지 않고 프레임이 전달될 확률
• P3​: 에러 탐지 알고리즘이 사용되는 경우, 하나 이상의 비트 에러가 탐지되었지만 탐지되지 않은 에러는 없는 확률 :
  에러 탐지 알고리즘이 모든 에러를 탐지하여 정확히 처리한 상황의 확률

패리티 비트

가장 간단한 에러 탐지 방식은 데이터 블록의 끝에 "패리티 비트"를 추가하는 것

패리티 비트의 동작 원리

• 패리티 값 설정
  데이터 블록의 1의 개수를 기준으로 패리티 비트를 설정합니다:
  • 짝수 패리티(even parity): 데이터 블록 내 1의 개수가 짝수가 되도록 패리티 비트를 추가합니다. , 동기 전송
  • 홀수 패리티(odd parity): 데이터 블록 내 1의 개수가 홀수가 되도록 패리티 비트를 추가합니다. , 비동기 전송

인터넷 체크섬

IP, TCP, UDP와 같은 인터넷 프로토콜에서 데이터의 무결성을 확인하기 위해 사용되는 에러 탐지 코드, 이 방식은 데이터를 일정한 크기의 워드(일반적으로 16비트)로 나누고, 1의 보수 덧셈과 1의 보수 연산을 조합하여 계산

1의 보수 연산 (Ones-complement operation)

• 정의:
  이진수의 모든 비트를 반전시킵니다.
  • 0 → 1, 1 → 0으로 변환
  • 예:
    입력: 1010 → 출력: 0101

---

1의 보수 덧셈 (Ones-complement addition)

1. 이진수 덧셈:
   • 두 숫자를 부호 없는 이진 정수로 간주하여 더합니다.
2. 캐리 발생 시 처리 (End-around carry):
   • 덧셈 결과에서 최상위 비트에서 캐리(carry)가 발생하면, 이 캐리 값을 다시 최하위 비트에 더함.
   • 예:
     1110 + 0011 = 10001 →  캐리 발생 → 0001+1=0010

순환 중복 검사(CRC)

송신된 데이터의 무결성을 확인하기 위해 다항식 나눗셈을 사용하는 에러 탐지 코드

 

• 송신 측:
  • 데이터를 특별한 숫자(생성기)로 나누고 나머지 값을 계산합니다.
  • 이 나머지를 데이터 끝에 붙여 함께 전송합니다.
• 수신 측:
  • 받은 데이터를 같은 숫자로 다시 나눕니다.
  • 나머지가 0이면 에러가 없고, 0이 아니면 에러가 발생한 것으로 간주합니다.

transmitter는 k비트의 블록을 기반으로 n-k의 FCS(Frame Check Frame)를 생성함. 즉 k비트 블록에 n-k의 FCS를 더해서 프레임 n으로 만든다. 이 프레임은 3가지 방식으로 정확히 나눠지도록 만들어진다. 

• Modulo 2 Arithmetic : 2로 나누는 방식으로 XOR연산(같으면 0 다르면 1) 처리(나누려고하는 애의 차수만큼 0을 추가)
• Polynomials : 모든 값을 더미 변수 X와 이진 계수를 사용하여 다항식으로 표현, 나누기(나누려고 하는애의 차수만큼 곱하기)
• Digital Logic : CRC는 XOR gate와 shift register로 구성된 나눗셈 회로로 구현, shift register는 1비트가 저장된 장치의 연속이다. 일정한 시간마다 shift register의 모든 값이 동시에 이동하며, 전체 레지스터가 1비트씩 오른쪽으로 이동함. 그래서 고속의 실시간 오류검출 가능

 FCS는 나머지 값, Polynomial은 나누는 값

 

 

 

전방 오류 수정(Forward Error Correction)

• 재전송이 필요 x - 전송 지연 최소화
• wireless application에는 부적합 - wireless link에서는 BER(Bit Error Rate)이 높기 때문에 재전송을 많이 해야 해서
• 비트 단위의 오류 수정 - 수신된 비트를 기반으로 찾고 수정
• 전송할 때 k비트 데이터 브록을 n비트 codeword와 매핑함(n > k) 추가된 비트들은 오류검출, 수정을 위한 정보를 가짐

FEC는 주로 신뢰성 있는 전송이 중요한 곳에서 사용하고 재전송이 어려운 무선 통신, 위성통신에서 사용

블록 코드 원칙

1. 해밍 거리 (Hamming Distance)

• 정의:
  두 이진 시퀀스(예: v1​, v2)에서 서로 다른 비트의 개수를 나타냅니다.
  • 예: v1=10101, v2=10011 → 서로 다른 비트는 두 번째와 네 번째.
  • 해밍 거리 d(v1,v2)=2
• 의미:
  해밍 거리가 클수록 에러 탐지와 수정 능력이 더 좋아집니다.

---

2. 코드의 여분성 (Redundancy of the Code)

• 정의:
  데이터 전송을 위해 추가된 여분 비트의 비율을 나타냅니다.
  • 계산식: n−k/k
    n = 총 비트 수, k = 데이터 비트 수.
• 예:
  • 데이터 비트 k=4, 총 비트 n=7이라면:
    n−k/k= 7-4/4 = 0.75
  • 여분성이 높으면 에러 수정 능력이 좋아지지만, 효율이 낮아질 수 있습니다.

---

3. 코드율 (Code Rate)

• 정의:
  데이터 비트가 전체 비트에서 차지하는 비율을 나타냅니다.
  • 계산식: k/n
    k = 데이터 비트 수, n = 총 비트 수.
• 예:
  • 데이터 비트 k=4, 총 비트 n=7이라면:
    k/n = 4/7 ~0.57
• 의미:
  코드율이 낮을수록 추가 비트가 많아 더 많은 대역폭이 필요하지만, 에러 수정 능력은 좋아집니다.