8. Error Detection & Correction

Types of Errors

Bit Error
: 전송(송신)된 비트 값이 수신 시에 바뀌어 도착하는 현상

Single‑bit Error

인접 비트에 영향 없이 오직 한 개의 비트만 반전되는 오류

원인 : 백색 잡음(white noise) 과 같은 랜덤 노이즈가
한 순간에 특정 비트만 왜곡시킬 때 발생

Burst Error

길이 B 비트의 연속 구간(contiguous sequence) 안에서
에러가 발생하는 경우

원인 :

• 임펄스 노이즈(impulse noise): 순간적인 전기적 충격
• 무선 페이딩(fading): 이동 통신 환경에서 순간적인 신호 감쇠

→ 다수 비트가 한꺼번에 오류가 나므로,
고속(높은 데이터율) 통신일수록 에러 구간이 길어질 가능성이 커짐

Error Control

BER(Bit Error Rate) : 전송된 비트 중 오류가 발생한 비트의 비율

• Copper wires (구리선): BER ≈ 10⁻⁶
• Optical fiber (광섬유): BER ≈ 10⁻⁹
• Wireless (무선): BER ≈ 10⁻³

Error Control : 오류를 검출·수정해서, 애플리케이션이 요구하는 신뢰도까지 데이터 전송 품질을 끌어올리는 기법

Error Control Approaches

ARQ (Automatic Repeat reQuest)

수신측이 수신한 프레임(Frame)마다 에러 검출 코드를 확인
오류가 있으면 송신측에 프레임을 다시 보내 달라고 재전송 요청

return 채널 필요 :
송신→수신 방향의 데이터 채널뿐 아니라,
수신→송신 방향으로도 제어 신호를 주고받을 수 있는 역방향 채널 필요

FEC (Forward Error Correction)

송신측에서 여분의 error correction code를 미리 메시지에 추가
수신측이 이 정정 코드만으로 재전송 없이 오류를 검출·수정

정정 가능 비트 수에 한계(bound)가 있으므로,
오류율이 너무 높으면 정정에 실패

return 채널 불필요
→ 대역폭 여유가 있거나, 재전송이 불가능·비용이 클 때 사용

Key Idea of Error Detection

Codeword의 패턴(pattern)
: 모든 송신 블록(코드워드)은 미리 정해진 형식이나 조건을 만족하도록 인코딩

수신 측에서의 패턴 검사
: 채널을 통해 비트 오류가 발생하면, 수신된 블록은 원래의 패턴을 벗어나게 됨

Redundancy(중복 정보)의 필요성
: 오류를 검출하기 위해서는, 원래 데이터에 추가 비트나 checksum 을 붙여 보내야 함

Blindspot(사각지대)
에러가 유효한 코드워드 A를 또 다른 유효한 코드워드 B로 변환해 버리는 경우

송신기 측 (Transmitter)

• 에러 검출 코드 생성 (E = f(data))
  f( ) : 에러 검출 코드 함수

• 실제 전송 비트 구성 (data + E)
  본래 k 비트 데이터 뒤에, 생성된 n−k 비트짜리 검사 비트를 덧붙여
  총 n 비트를 한 코드워드로 채널에 보냄

수신기 측 (Receiver)

• 수신된 블록 분리
  앞의 k 비트는 받은 데이터(data′), 뒤의 n−k 비트는 송신자가 붙여준 검사 코드(E)

• 검사 코드 재계산 (E′ = f(data′))
  수신된 데이터(data′)에 대해 동일한 함수 f를 적용하여 수신자가 직접 계산한 검사 코드(E′)를 만듦

• 비교(Compare)
  송신자가 보낸 검사 코드(E)와, 수신자가 계산한 코드(E′)를 비교
  같으면 → “에러 없음”
  다르면 → “에러 발생” (재전송 요청 혹은 알람)

Single Parity Check

원래 정보 비트
$b_1, b_2, \dots, b_k$

parity 비트 계산
$b_{k+1} = (b_1 + b_2 + \dots + b_k) \mod 2$

전송할 코드워드
$(b_1, b_2, \dots, b_k, b_{k+1})$

→ 전체 n=k+1비트 중, 항상 1의 개수가 짝수인 블록이 만들어짐

수신 측 검사

수신된 n비트 블록에서 1의 개수를 세어 본 뒤,
짝수이면 → 정상
홀수이면 → 오류 발생

홀수 개의 비트 오류는 검출 가능, 짝수 개의 비트 오류는 검출 불가능

Checkbits & Error Detection

How good is the single parity check code?

중복도 (Redundancy)

k개의 정보 비트마다 1개의 패리티 비트를 추가

Overhead = $\frac{\text{추가되는 비트 수}}{\text{총 전송 비트 수}} = \frac{1}{k+1}$

검출 범위 (Coverage)

홀수 개의 오류는 모두 탐지 가능
짝수 개의 오류는 탐지 불가

코드워드 길이가 n=k+1일 때,
가능한 모든 오류 패턴은 $2^n$ 가지
이 중 오류의 개수가 홀수인 패턴은 정확히 절반($2^{n−1}$)

→ single parity 코드는 전체 오류 패턴의 50%를 검출 가능

What is a good code?

코드워드 간 거리
채널 노이즈로 인해 비트 플립이 발생하면, 원래 코드워드 A가

• 유효한 다른 코드워드 B 로 바뀔 수도 있고
• 코드워드가 아닌 영역으로 벗어날 수 있음

Poor distance properties (나쁜 코드)

코드워드들이 서로 가까이 몰려 있음
몇 비트만 뒤집혀도 다른 코드워드 영역으로 넘어갈 확률이 높아짐
→ 탐지 실패(에러가 있어도 잡아내지 못함)

Good distance properties (좋은 코드)

코드워드(×)들을 서로 넓게 퍼뜨림
적은 수의 비트 오류(노이즈)로는 다른 코드워드로 넘어가지 않음
→ 오류가 발생해도 유효하지 않은(비코드워드) 영역으로 벗어남
→ 반드시 감지

최소 해밍 거리(minimum Hamming distance)

$d_{\min}$ = 코드워드 쌍 중 가장 가까운 해밍 거리
탐지 가능 오류 수 : $d_{\min} - 1$ 비트 오류까지는 무조건 탐지
정정 가능 오류 수 : $\lfloor (d_{\min} - 1) / 2 \rfloor$ 비트 오류까지 수정 가능

What if bit errors are random?

비트 에러 모델

가정: 각 비트는 서로 독립적으로, 확률 p 로만 뒤집힘

• 뒤집힐(1→0 또는 0→1) 확률 = p
• 오류가 나지 않을 확률 = 1−p

오류 패턴의 확률 계산

오류 패턴(error pattern) 벡터에서 :

• 1 = 해당 위치의 비트가 뒤집힘(에러)
• 0 = 정상(뒤집히지 않음)

• 패턴 10000000 (첫 비트만 오류)

• 패턴 11000000 (첫 두 비트만 오류)

오류가 w개 발생한 패턴 확률 : $p^w (1 - p)^{n-w}$

1개 오류가 2개 오류보다 더 자주 발생

실제 통신에서는 보통 p<0.5 이므로 p/(1−p)<1

따라서
$(1-p)^8 \left(\frac{p}{1-p}\right) > (1-p)^8 \left(\frac{p}{1-p}\right)^2$
→ 1비트 오류 패턴이 2비트 오류 패턴보다 자주 발생

Single parity check code with random bit errors

Single parity check에서
undetectable 오류가 실제로 얼마나 자주 발생하는지

검출 불가한 오류 패턴 확률 식

길이 n인 블록에서 오류 개수가 짝수일 때의 확률 합

$\binom{n}{w}$ : 오류가 w개 생길 위치 조합 수
$p^w$ : w개 비트가 모두 뒤집힐 확률
$(1-p)^{n-w}$ : 나머지 비트가 모두 정상일 확률

Two-Dimensional Parity Check

단일 패리티는 한 줄 안에서만 에러를 검출하기 때문에

• 2개 이상의 비트 오류가 같은 줄에서 동시에 발생하면 놓칠 수 있음
• 위치 파악은 전혀 못 함

2차원 패리티는 행(row)과 열(column) 모두에 패리티 비트를 달아서

• 검출 범위를 넓히고,
• 오류 위치 파악 가능

열별 패리티 비트 추가
각 열 j마다 짝수 패리티를 계산해서,
열 아래에 $p_j$ 를 덧붙여 열 검사용 패리티 행을 만듦

행별 패리티 비트 추가
각 행 i마다 짝수 패리티를 계산해서,
각 행 $i$ 에 $p_i$ 를 덧붙여 행 검사용 패리티 열을 만듦

최종 패리티 비트
맨 오른쪽 아래 코너 비트는 모든 행별·열별 패리티가 짝수가 되도록 함

Error-detecting capability

1 비트 에러

한 비트 오류가 한 행과 한 열의 패리티만 깨뜨림

→ 어느 행과 열의 패리티가 깨졌는지 보고 정확히 위치를 파악 가능 (1비트 정정)

2 비트 에러

두 비트가 서로 다른 행과 다른 열에서 에러가 났을 때,
각 에러 비트마다 대응하는 그 행과 열 패리티가 깨짐

→ 두 개의 행과 두 개의 열에서 패리티 이상이 감지되어,
서로 교차하는 네 지점 중 두 지점이 후보
1비트 정정은 불가능하지만, 에러가 있다는 건 알 수 있음

3 비트 에러

홀수 개 에러가 발생한 모든 행·열은 parity가 깨짐
but 같은 line에 error 2개는 감지하기 어려움

4 비트 에러

네 비트가,
서로 짝수 개씩 한 행·한 열에 걸쳐 에러가 나면
행 패리티, 열 패리티 모두 짝수로 유지돼 버림
→ 패리티 검사기만으론 전혀 에러가 났는지 알 수 없음

• 4개가 흩어지면 → 검출 가능
• 직사각형 형태 → 검출 불가능

Other Error Detection Codes

1차원 parity : 오류확률(블라인드스팟)이 높음
2차원 parity : 오버헤드가 너무 큼

다른 에러 검출 코드

• Internet Checksum
• CRC Polynomial Codes

Internet Checksum

Internet Checksum
: IP, TCP, UDP 같은 인터넷 프로토콜에서

• IP에서는 헤더만
• TCP/UDP에서는 헤더+데이터에 대해

에러를 검출하기 위해 Checksum 필드를 둠

Checksum Calculation

Checksum 계산 방식

16비트 word 합산

헤더를 16비트 단위 워드 $b_0, b_1, \dots, b_{L-1}$ 로 나눠서
모두 더함

checksum word 생성

$b_L = -x \pmod{2^{16} - 1}$

수신측 검증 조건

수신된 헤더의 $L+1$개 워드 $\{b_0, \dots, b_{L-1}, b_L\}$ 을 모두 더했을 때

이 성립하면 오류 없음
그렇지 않으면 헤더 손상.

Internet Checksum Example

4비트 워드로 이루어진 헤더 워드 $b_0, b_1$에 대해 체크섬 $b_2$를 구하는 과정

모듈로 산술(Modulo Arithmetic)

1. 워드를 정수로 해석
   $b_0 = 1100_2 = 12$
   $b_1 = 1010_2 = 10$

2. 합산
   $x = b_0 + b_1 = 12 + 10 = 22$

3. 모듈로 $2^4−1=15$ 취하기
   $22 \mod 15 = 7$

4. 체크섬 정의
   $b_2 = -x \mod 15 = -7 \mod 15 = 8 \quad$

→ 즉, $b_2=8$이고 이걸 4비트로 쓰면 $1000_2$

1의 보수 덧셈(Binary Wrap‑around)

1. 워드 직접 더하기
   $1100_2 + 1010_2 = 10110_2$

2. 상위 캐리 비트(맨 앞 1) 래핑
   상위 비트 ‘1’을 버리지 않고, 하위 4비트 ‘0110’에 다시 더함:
   $0110_2 + 0001_2 = 0111_2$

3. 1의 보수(부호) 취하기
   $b_2 = 1000_2$

→ 정수로는 8

Polynomial Codes (CRC codes)

비트 벡터 대신 다항식으로 메시지를 표현하고,
덧셈·체크섬이 아니라 다항식 나눗셈을 이용해 에러를 검출하는 기법

강력한 에러 검출을 제공

Cyclic Redundancy Check (CRC)

목표

데이터 D에 r개의 CRC 비트 R를 덧붙여,

이 전체 비트열이 생성다항식 G(x) 으로 나눠떨어지도록 만드는 것.

→ 수신기도 G(x)로 같은 나눗셈을 수행해 나머지만 보면 오류 유무를 알 수 있음

구성 요소

데이터 비트 D : d비트 길이, 실제 전송하고 싶은 정보
생성비트 패턴 G(x) : 차수 r인 다항식 (비트 패턴 길이 = r+1)
정정비트 R : r비트, 인코더가 나눗셈 결과로 계산해 붙이는 나머지

Cyclic Redundancy Check (CRC): example

생성다항식 $G=1001_2$ (차수 r=3) 를 써서,
데이터 $D=101110_2$에 3비트 CRC R 를 구하는 과정

메시지 준비

원본 데이터 $D=101110$ 뒤에 r=3개의 0을 붙여 준비

생성다항식 G=1001 로 나눗셈

XOR 나눗셈 방식으로, 맨 왼쪽부터 1001 을 반복해서 빼나감

• XOR : 이진수 각 비트를 서로 비교해 서로 다르면 1, 같으면 0 을 출력

• 현재 상위 4비트 영역이 1xxx 이면, 그 자리에 1001 을 XOR
• 그렇지 않으면 그냥 내려가서 다음 비트로 이동

나머지 R 추출

마지막에 남은 3비트(차수 r)가 나머지

→ R=011 을 원래 데이터 101110 뒤에 붙여 전송하면,
수신기에서 다시 1001 로 나눌 때 나눠떨어지는(divisible) 코드워드

Shift-Register Circuit for CRC

생성다항식 g(x)를 하드웨어로 구현

Binary Polynomial Arithmetic

binary 벡터를 GF(2) 다항식으로 해석했을 때의 덧셈·곱셈 규칙

벡터⇄다항식 대응

길이 k짜리 binary 벡터 $(i_{k-1}, i_{k-2}, \dots, i_1, i_0)$를

라고 생각

ex. 1101001은 $x^6 + x^5 + x^2 + 1$

덧셈 (Addition)

다항식을 계수별로 mod 2하여 더함
$(x^7 + x^6 + 1) + (x^6 + x^5) = x^7 + (x^6 + x^6) + x^5 + 1$
$= x^7 +x^5 + 1$

동일한 차수 항이

• 짝수 개 있으면 제거(0)
• 홀수 개이면 남음(1)

곱셈 (Multiplication)

다항식 곱셈 후, 계수는 mod 2 로 처리

ex. $(x + 1)(x^2 + x + 1)$

$(x^3 + x^2 + x) + (x^2 + x + 1)$
$= x^3 + (x^2 + x^2) + (x + x) + 1 = x^3 + 0 + 0 + 1 = x^3 + 1$

곱한 뒤에
동일 차수 항의 합은 mod 2 로 취급해 겹치는 항을 지움

Binary Polynomial Division

Polynomial Division
: XOR(=mod2 뺄셈) 하고, 다음 차수 항을 내려서(내림) 계속 XOR
→ 몫 다항식·나머지 다항식 구함

Polynomial Coding

생성다항식 g(x)

코드 전체 길이가 n, 정보 비트가 k일 때,
$g(x) = x^{n-k} + g_{n-k-1}x^{n-k-1} + \dots + g_1x + 1$

정보다항식 i(x)

k개의 정보 비트 $(i_{k-1}, \dots, i_0)$를
$i(x) = i_{k-1}x^{k-1} + \dots + i_1x + i_0$
라는 차수 k−1 다항식으로 표현

나머지 다항식 r(x) 계산

먼저 i(x)를 $x^{n-k}$만큼 밀어올린
$x^{n-k} i(x)$를 $g(x)$로 나눔

코드워드 다항식 b(x) 구성

전송할 코드워드는,
“밀어 올린 정보” + “나머지” 를 합쳐서

→ 이렇게 하면 b(x)가 g(x)의 배수(divisible) 가 되어,
수신측에서 $b(x) \mod g(x) = 0$ 이면 정상, 그렇지 않으면 오류로 감지

Polynomial example: k=4, n=7, n–k=3

정보다항식과 밀어 올리기

정보 비트 (1,1,0,0)
→ $i(x) = 1 \cdot x^3 + 1 \cdot x^2 + 0 \cdot x + 0 = x^3 + x^2$

$x^{n-k} = x^3$배
→ $x^3 i(x) = x^3 (x^3 + x^2) = x^6 + x^5$

생성다항식 g(x) 로 나눗셈

첫 단계

$\frac{x^6 + x^5}{x^3 + x + 1} \longrightarrow \text{몫 항 } x^3, \quad x^3 \cdot g(x) = x^6 + x^4 + x^3$

XOR 하면 남는 부분
: $(x^6 + x^5) \oplus (x^6 + x^4 + x^3) = x^5 + x^4 + x^3$

두 번째 단계

$(x^5 + x^4 + x^3) \oplus (x^5 + x^3 + x^2) = x^4 + x^2$

세 번째 단계

$(x^4 + x^2) \oplus (x^4 + x^2 + x) = x$

최종 코드워드

“밀어 올린 정보” + “나머지”
$b(x) = x^3 i(x) + r(x) = (x^6 + x^5) + x = x^6 + x^5 + x$

→ 비트열로 쓰면 b=(1,1,0,0,0,1,0).

The Pattern in Polynomial Coding

폴리노미얼 부호화(ex.CRC)에서는
전송되는 모든 코드워드가 생성다항식 g(x)의 배수여야 함

코드워드는 항상 g(x)의 배수

인코더가

1. 정보다항식 i(x)을 $x^{n-k}i(x)$로 밀어 올리고
2. 생성다항식 g(x)로 나눠 나온 나머지 r(x)를 붙이면
3. 결과 코드워드 $b(x) = x^{n-k}i(x) + r(x)$는
   $b(x) \mod g(x) = 0$ 성립

Basic ARQ with CRC

CRC를 이용한 기본 ARQ(Automatic Repeat reQuest) 시스템

정보 프레임(Information Frame) 전송

송신측(Station A) 에서
[헤더 + 페이로드] + CRC 정보 프레임을 만들어
채널을 통해 수신측(Station B) 으로 전송

수신측에서 CRC 검사

수신측은 들어온 정보 프레임에 대해

• 나머지가 0 이면 → “정상 수신”
• 0이 아니면 → “에러 발생”

제어 프레임(Control Frame) 전송

수신측은 검사 결과를 제어 프레임(ACK/NACK)으로 돌려보냄

• ACK(Positive ACK): 정상적으로 받았음을 알림
• NACK(Negative ACK): 오류가 있으니 재전송해 달라는 요청

→ 제어 프레임에도 헤더와 CRC 비트를 붙여,
제어 프레임 자체의 무결성도 보장

송신측에서 재전송 또는 다음 패킷

송신측은 제어 프레임을 받아

• ACK 이면 → 다음 패킷을 송출
• NACK 이면 → 해당 패킷을 재전송

End-to-End vs. Hop-by-Hop

End‑to‑End 방식

송신지(Source)와 최종 목적지(Destination) 사이에만
오류 제어·흐름 제어 프로토콜을 적용

• 단순 : 네트워크 내부(라우터·스위치)는 오로지 패킷 포워딩만
• 최종 신뢰성 : 오직 종단 간 검사(ACK/NACK 등)로 전송 오류 감지·재전송
• 지연 발생 : 오류가 발생하면 패킷이 목적지까지 간 뒤 재전송 요청

Hop‑by‑Hop 방식

네트워크의 각 hop(인접 노드 쌍)마다 오류 제어·흐름 제어를 수행

• 복구 : 홉 간에 작은 단위로 오류를 잡아내고 즉시 재전송
• 지연 최소화: 오류가 발생해도 해당 홉에서만 재전송
• 오버헤드 증가 : 각 라우터·스위치에 버퍼링·제어 로직 필요
  → 복잡도·자원 소모

Error Control in Transport Layer

전송 계층(Transport Layer) 에서 수행하는 end‑to‑end 오류 제어

전송 계층의 역할

애플리케이션이 주고받고자 하는 메시지(Messages) 를

• 세그먼트(segments) 로 분할한 뒤,
• 네트워크(Internet)를 통해 목적지까지 전송

프로토콜 스택 전반의 신뢰성 보장

데이터 링크 계층 : hop 간 프레임 전송을 신뢰성 있게 처리
전송 계층 : “종단 간” 세그먼트를 신뢰성 있게 처리

End-to-End Approach Preferred

Hop‑by‑Hop

각 홉(hop)마다
노드 1→2, 2→3, 3→4, 4→5 구간마다
Data + ACK/NAK로 재전송을 즉시 처리

장점

• 빠른 복구: 오류가 생긴 홉에서만 국소적으로 재전송

단점

• 종단 간(end‑to‑end) 무결성 보장 불가:
  각 홉이 개별적으로 복구하더라도,
  전체 경로상의 버그(ex. 잘못된 변환·버퍼 오버플로우)가 누적될 수 있음
• 네트워크 내부 복잡화: 모든 라우터·스위치에 오류 제어 로직 필요

End‑to‑End

송신지→노드 1→2→3→4→5→수신지 구간을
중간 노드들은 단순 포워딩만,
ACK/NAK 은 “송신지 ⇄ 수신지” 종단 간에만 주고받음

장점

• 네트워크 내부 단순화
• 종단 간 무결성 보장: 송신 앱과 수신 앱 사이를 온전히 보호

단점

• 오류가 목적지까지 도달해야 재전송 → 지연 커질 수 있음