순환 중복 검사
From IT Wiki
- CRC, Cyclic Redundancy Check
CRC는 데이터 통신에서 오류를 탐지하는 대표적인 방법으로, 데이터 전송 중 발생한 오류를 효과적으로 검출하기 위해 사용된다. CRC는 주로 네트워크 통신과 디지털 저장 장치에서 데이터 무결성을 검사하는 데 사용된다.
기본 개념
CRC는 생성 다항식(Generator Polynomial)이라는 고정된 값을 사용하여 데이터를 다항식처럼 취급하고, 이를 나눗셈 연산을 통해 오류를 검출한다. 송신 측에서 데이터를 전송할 때, 그 데이터를 생성 다항식으로 나눈 나머지를 함께 전송한다. 수신 측은 동일한 방식으로 계산된 나머지를 확인하여 전송 중 오류가 발생했는지 판단한다.
생성 다항식
Generator Polynomial
생성 다항식은 특정 다항식을 이진수로 표현한 값이다. CRC 계산에서 이 다항식은 송신된 데이터를 나누기 위한 나눗셈의 제수 역할을 한다.
- 다항식의 길이는 사용하는 CRC의 종류에 따라 다르며, 대표적인 생성 다항식에는 CRC-8, CRC-16, CRC-32 등이 있다.
예를 들어, 1011이라는 다항식은 다음과 같이 해석된다.
- 다항식: x3+x+1 → 이진수: 1011
- 여기서 x3, x, 1에 해당하는 자리에 1이 있고, 나머지 자리는 0으로 채운다.
CRC 동작 과정
- 생성 다항식 선택: 송신 및 수신 측에서 동일한 생성 다항식을 미리 정의한다. 예시에서는 생성 다항식으로 1011을 사용한다고 가정한다.
- 송신 측에서 CRC 코드 생성:
- 데이터를 이진수로 표현한 후, 생성 다항식을 사용해 나눗셈을 수행한다.
- 데이터를 전송하기 전에 데이터 뒤에 생성 다항식의 길이에 해당하는 0을 붙여 나머지를 구한다.
- 나머지가 CRC 코드가 되며, 이 코드를 데이터 뒤에 덧붙여 전송한다.
- 수신 측에서 오류 검출:
- 수신된 데이터에 대해 동일한 생성 다항식으로 나눗셈을 수행한다.
- 그 결과가 0이면 오류 없이 정확하게 전송된 것으로 간주하고, 0이 아니면 오류가 발생한 것으로 판단한다.
CRC 예시
데이터: 1101, 생성 다항식: 1011
- 데이터 뒤에 3개의 0 추가
- 데이터 길이가 4비트, 생성 다항식이 4비트(다항식 차수 + 1)이므로, 데이터 뒤에 000을 추가한다.
- 데이터는 이제 1101000이 된다.
- 데이터를 생성 다항식으로 나눗셈
- 데이터를 생성 다항식으로 나눗셈하여 나머지를 구한다. XOR 연산을 사용하여 수행한다.
- 최종 나머지 값은 100이다.
- 나머지를 데이터에 추가
- 계산된 나머지인 100을 원래 데이터인 1101 뒤에 붙여 1101100을 전송한다.
수신 측에서 검증
- 수신 측에서는 1101100을 받는다.
- 동일한 생성 다항식 1011으로 나눗셈을 수행하여 나머지를 계산한다.
- 나머지가 0이면 오류 없이 정확히 전송된 것으로 간주된다.
CRC의 특징
- 오류 검출률: CRC는 단일 비트 오류, 두 비트 오류, 연속적인 비트 오류 등을 감지할 수 있으며, 높은 오류 검출 확률을 가지고 있다.
- 빠른 계산: XOR 연산을 사용하여 연산 속도가 빠르고, 하드웨어 및 소프트웨어에서 효율적으로 구현 가능하다.
- 오류 수정 불가: CRC는 오류 탐지에 특화되어 있으며, 오류를 수정할 수는 없다. 오류가 발견되면 데이터를 재전송하는 방식으로 대응한다.
