Computer network: crc(cyclic redundancy check)

📑 CRC(Cyclic Redundancy Check)

---

1️⃣ CRC 개요

CRC(Cyclic Redundancy Check)는 디지털 통신 및 데이터 저장 분야에서 오류 검출을 위해 널리 사용되는 코드입니다.
송신 측에서 데이터 비트스트림을 특정한 생성 다항식(Generator Polynomial)로 나눗셈(Modulo-2 Arithmetic)을 수행해 나머지(R, FCS)를 구한 후, 이를 데이터 뒤에 붙여 전송하며, 수신 측에서는 동일한 생성 다항식으로 검증하여 오류를 판별합니다.

---

2️⃣ CRC 계산 과정

✍️ 송신 측

1️⃣ 데이터(Message, M) 준비

• 송신자가 전송하려는 실제 데이터 비트스트림.

2️⃣ 데이터 뒤에 생성 다항식 P(x)의 차수(n)만큼 0을 붙임

T = M × 2ⁿ

3️⃣ Modulo-2 나눗셈 수행

T ÷ P(x) = Q (몫), R (나머지)

• 여기서 R이 바로 CRC 나머지(FCS)입니다.

4️⃣ 전송 데이터 생성

T* = T + R

• XOR 연산(Modulo-2 덧셈)으로 붙임.

---

✍️ 수신 측

1️⃣ T* 수신 후 동일한 P(x)로 나눗셈 수행**

T* ÷ P(x) = Q', R'

• R’ = 0 → 오류 없음.
• R’ ≠ 0 → 오류 발생.

---

3️⃣ Modulo-2 연산의 특징

• 덧셈(+)과 뺄셈(-)이 XOR로 동일.
  • 예) 1+1=0, 1+0=1, 0+0=0
• 나눗셈은 반복적인 XOR 연산으로 구현.
• 따라서 CRC 계산은 디지털 회로와 프로그램 모두에서 효율적으로 수행 가능.

---

4️⃣ 1비트 오류 검출

데이터 전송 중 단일 비트가 뒤집히는 오류(예: 1→0 또는 0→1)가 발생하면 오류 다항식 E(x)=xᵏ로 나타낼 수 있다.

• 송신자가 전송한 데이터 T*는 설계상 P(x)로 나누어떨어지도록 만들어져 있어 수신자가 나눴을 때 나머지가 0이다.
• 1비트 오류가 발생하면:

  T*' = T* + E(x)
  

  (T*' ÷ P(x)) = (T* ÷ P(x)) + (E(x) ÷ P(x)) = 0 + (E(x) ÷ P(x))
  

• E(x)는 단일항이므로 P(x)로 나누어떨어지지 않음 → R’ ≠ 0 → 오류 검출.

✅ CRC는 단일 비트 오류를 100% 검출한다.

---

5️⃣ 2비트 및 3비트 오류 검출

CRC 다항식의 구조에 따라 2비트, 3비트 오류 검출력이 결정된다.

• 대부분의 잘 설계된 CRC 다항식은 거의 모든 2비트 오류를 검출 가능.
• 일부 CRC 다항식은 3비트 오류도 높은 검출률을 보장.
• Burst Error(연속된 비트 오류)도 CRC 차수에 따라 특정 길이까지 100% 검출이 가능.

✅ CRC의 오류 검출 능력은 생성 다항식 P(x)의 설계에 달려있다.

---

6️⃣ CRC 다항식의 중요성

• 생성 다항식 P(x)가 1(x⁰)이라면 어떤 데이터든 나머지가 항상 0 → 오류 검출 불가능.
• 따라서 CRC 설계에서는 반드시 차수가 1 이상인 다항식을 선택해 검출력을 확보.
• 예시:
  • CRC-4: x⁴ + x + 1 (0b10011)
  • CRC-8: x⁸ + x² + x + 1 (0x07)
  • CRC-16: x¹⁶ + x¹² + x⁵ + 1 (0x1021)
  • CRC-32: x³² + … + 1 (0x04C11DB7)

이러한 다항식들은 IEEE, ITU 등 표준화 기관에서 오류 검출 성능을 수학적으로 분석한 후 채택된 것이다.

---

7️⃣ CRC의 수학적 표현 요약

단계	수식
송신 데이터 준비	T = M × 2ⁿ
나머지 계산	R = T mod P(x)
전송 데이터	T* = T + R
수신자 검증	T* ÷ P(x) = R’
오류 판별	R’ = 0 → 정상, R’ ≠ 0 → 오류

---

8️⃣ 결론

✅ CRC는 Modulo-2 연산을 사용하여 데이터 전송 중 발생할 수 있는 단일 비트 오류, 다중 비트 오류(2비트, 3비트) 및 Burst Error를 검출하는 강력한 방식이다.
✅ CRC가 오류를 잘 검출하는 이유는 생성 다항식 P(x)를 어떻게 선택하느냐에 달려있으며, 표준 CRC 다항식은 이러한 오류 검출 능력을 극대화하도록 설계되었다.
✅ 따라서 CRC는 네트워크 통신, 데이터 저장 장치, 무선 통신 등에서 데이터 무결성을 검증하는 데 매우 중요한 역할을 수행한다.

---

필요하다면 실제 예제(Modulo-2 나눗셈)나 특정 CRC 다항식 설계 과정까지 자세히 추가로 다룰 수 있어요. 언제든 댓글이나 문의주세요! 🚀