2025. 12. 10. 16:03ㆍIT 용어
1. CRC란
CRC는 데이터 전송/저장 중 우연한 오류를 빠르게 검출하기 위한 체크값으로 단순한 합계나 XOR 체크섬보다 오류 검출 성능이 훨씬 좋아 시리얼 통신, 산업용 프로토콜, 네트워크, 파일 포멧 등에서 널리 사용된다.
2. CRC의 개념
CRC는 데이터를 이진 다항식(Polynomial)으로 보고, 약속된 생성다항식(generator polynomial)으로 나눗셈을 수행했을때 나머지를 체크값으로 사용하는 방식이다.
단순 합계나 XOR 체크섬은 특정 패턴의 오류에 취약하고 바이트가 서로 바뀌거나 일부가 상쇄되면 못잡는 경우가 생긴다.
1. 단순 체크섬
데이터를 바이트 단위로 보고 모든 바이트 값을 더한 뒤, 정해진 비트 폭(보통 8비트 또는 16비트)에 맞게 잘라서(mod) 체크값으로 쓰는 방식이다
[ 0x10, 0x20, 0x30 ]만약 데이터가 위처럼 들어왔을 경우 이를 10 진수로 바꾸면 아래와 같고
16 32 48이를 합치면 checksum은 96, 0x60이 된다.
이는 8비트 체크섬에서 오버플로우가 없는 경우이고 오버 플로우가 있는 경우는 데이터가 아래와 같고
[ 0xF0, 0x30, 0x50 ]이를 10진수로 변환하면 아래와 같고
240 48 80이를 합치면 368이 되고 이걸 비트로 보여주면 아래와 같은 그림이 된다.
368(10) = 0b1 0111 0000
^ ^^^^^^^^^
| |
9번째 비트 하위 8비트여기서 하위 8비트를 남기고 상위 비트를 제거하면 112가 남는다
0b0111 0000 = 2^6 + 2^5 + 2^4 = 64 + 32 + 16 = 112
^^^^ ^^^^
|
하위 8비트112는 0x70으로 체크섬은 0x70이 된다.
여기서 문제는 상쇄 오류, 바이트 순서 교체등의 문제에는 확인이 불가능하다는 것이다.
1) 상쇄오류
상쇄 오류는 값이 서로 보정되어 합이 동일해져 다른 데이터지만 체크섬의 값이 동일한 경우이다.
먼저
[ 0x10, 0x20 ]일때
16 32로 합하면 48, 0x30이 된다.
근데 만약
[ 0x11, 0x1F ]
↓
17 31와 같이 나왔을때 합은 동일하게 48, 0x30이 나오게 되면서 데이터는 다르나 체크은 같은 경우가 발생하게 된다.
이게 SUM 체크섬의 대표적인 구조적 약점이다.
2) 바이트 순서 교체(필드 스왑)
만약 원본 데이터의 경우가
[ 0x01, 0x02, 0x03 ]
↓
1 2 3와 같이 나왔을때 체크섬은 6, 0x06이 나오는데 오류로 인해서 바이트의 위치가 바뀐 경우
[ 0x02, 0x01, 0x03 ]
↓
2 1 3이 경우도 여전히 체크섬은 6, 0x06이 나오게 된다.
만약 프레임의 구조가
[ LEN, CMD, DATA1, DATA2 ]와 같이 되어 있을 경우 원본이 아래처럼 전송될때
[ 0x04, 0x10, 0x20, 0x30 ]
↓
4 16 32 48체크섬은 100, 0x64가 된다
그런데 만약 오류가 나서
[ 0x05, 0x10, 0x1F, 0x30 ]
↓
5 16 31 48와 같이 전달 될 경우도 동일한 체크섬으로 오류 검출이 불가능해진다.
2. XOR 체크섬
XOR체크섬은 모든 바이트를 XOR로 누적한 값을 체크값으로 쓰는 방식이다.
바이트로 보자면
[ 0x10, 0x20, 0x30 ]이런 데이터가 온다면
0x10 XOR 0x20 =
0x10 = 0001 0000
0x20 = 0010 0000
XOR = 0011 0000 = 0x30
0x30 XOR 0x30 =
0x10 = 0110 0000
0x10 = 0110 0000
XOR = 0000 0000 = 0x00과 같이 순서대로 XOR한 값의 결과로 0x00이 체크섬 값이 나온다.
XOR 체크섬은 바이트 순서 교체에 취약하고 두 바이트가 같은 방식으로 변경되면 상쇄된다.
또한 짝수 개의 동일 비트 오류에 취약한 성격이 강하다.
1) 바이트 순서 교체에 취약
[ 0x12, 0x34, 0x56 ]의 데이터가 오류로 인해서 아래처럼 바뀐다면
[ 0x34, 0x12, 0x56 ]XOR는 순서에 무관해서 체크썸이 동일하다.
그렇기에 필드 위치가 의미를 갖고 있는 프레임의 경우는 위험할 수 있다.
2) 두 바이트가 같은 방식으로 변하면 상쇄됨
[ A, B ]
CHECKSUM = A XOR B이렇게 되어 있는 데이터가 어떤 오류로 인해서 같은 마스크인 X로 동시에 변형되었다면
[ A XOR X, B XOR X ]새로운 체크섬은
(A XOR X) XOR (B XOR X)
= A XOR B XOR X XOR X
= A XOR B변형 이전의 체크섬과 동일하게 나타난다.
XOR는 같은 위치의 비트가 짝수번 뒤집히면 XOR의 결과가 원래대로 돌아가기에 동일한 비트 자리에서 오류가 두번 생기면 XOR 입장에서는 변화가 사라질 수 있다는 점이 중요하다.
CRC는 생성 다항식 기반 구조 때문에 1 비트 오류, 다수의 짧은 오류, 특히 버스트 오류(연속 비트 오류)에 대해서 검출 성능이 뛰어나다.
산업용 시리얼, 네트워크 환경은 노이즈로 인해서 연속적/구간적 오류가 흔하기에 이런점이 강점이 된다.
3. CRC의 종류
CRC는 길이에 따라서 CRC-8, CRC-16, CRC-24, CRC-32 등으로 나뉜다.
여기서 추가로 어떤 파라미터의 조합으로 CRC를 사용하느냐에 따라서 계산법 및 결과가 달라진다.
- Poly
- Init
- Refln / RefOut
- XorOut
- CRC 바이트 전송 순서(High/Low)
- CRC 계산 범위(프레임 어디부터 어디까지)
등의 파라미터가 존재하며 이 조합에 따라 종류가 명확하게 나뉘게 된다.
그렇기에 CRC는 아래와 같이 작성해야 명확한 종류를 확인할 수 있다.
CRC-16/XXXX
Width: 16
Poly: 0xYYYY
Init: 0xZZZZ
RefIn: T/F
RefOut: T/F
XorOut: 0xWWWW
계산 범위: 예) LEN~PAYLOAD
전송 순서: 예) Low byte first
그런데 CRC-16/XXXX의 XXXX의 표준적인 형태가 있기에 이렇게만 써도 어느정도는 어떤 식으로 이걸 해석해야하는지 알 수 있게 된다.
4. CRC-16의 계산
CRC를 계산 할때는 먼저 어디부터 어디까지 계산할지가 결정 되어 있어야한다.
내가 나중에 할 프로젝트를 기준으로하면 기본적인 프레임은 아래와 같은 구조로 되어 있고
STX | LEN | CMD | DATA | ETX | CLC_H | CLC_L
(시작바이트) (CMD+DATA의 길이) (명령어) (실 내용) (종료바이트) (CLC의 앞 1바이트) (CLC의 뒤 1바이트)여기서 STX - ETX까지를 계산한다, 혹은 LEN - DATA까지를 계산한다, 이런식으로 전달하게 될것이다.
여기에 추가로 이전에 말했던 생성다항식, Poly라고 하는걸 송수신측이 정할 텐데 보통은 0x1021로 하는 경우가 많다.
이건 둘 사이의 규약이기에 어느정도 표준은 있으나 서로 지정하기 나름으로 보인다.
이 생성다항식 또한 계산에서 사용된다.
STX - ETX를 기준으로 계산해보자면 먼저 실 데이터가 아래와 같이 구성되어 있다면
STX | LEN | CMD | DATA[0] - DATA[1] | ETX | CLC_H | CLC_L
02 03 10 AA 55 03 ?? ??여기서 우리는 CLC_H-CLC_L을 구하는 것이다.
이걸 계산할때는 먼저 STX부터 하나씩 바이트를 갖고가면서 계산을 시작한다
STX부터 계산을 해보면 가장 먼저 STX의 값을 8비트 왼쪽으로 shift해준 후에
STX = 0000 0010
↓ (STX << 8)
STX = 0000 0010 0000 0000송수신측에서 결정한 CLC의 최초값(여기선 0x0000으로 함)을 XOR해준다.
STX<<8 = 0000 0010 0000 0000
crc:
0000 0000 0000 0000
XOR 0000 0010 0000 0000
-----------------------------------
= 0000 0010 0000 0000 (0x0200)
이렇게 계산한 공식은 아래와 같이 나온다.
CRC ^= (b << 8)
이제 합쳐진 CRC를 8번 왼쪽으로 shift 할텐데 중요한건 최상위 비트(MSB; Most Significant Bit)의 값이 1인지를 확인하고 만약 MSB가 1일 경우는 위에서 말했던 생성다항식, poly를 XOR해주고 shift해준다.
과정을 보자면 먼저 CRC를 8회 왼쪽으로 shift하는데
bit0: 0000 0010 0000 0000 -> 0000 0100 0000 0000 (shift)
bit1: 0000 0100 0000 0000 -> 0000 1000 0000 0000 (shift)
bit2: 0000 1000 0000 0000 -> 0001 0000 0000 0000 (shift)
bit3: 0001 0000 0000 0000 -> 0010 0000 0000 0000 (shift)
bit4: 0010 0000 0000 0000 -> 0100 0000 0000 0000 (shift)
bit5: 0100 0000 0000 0000 -> 1000 0000 0000 0000 (shift)
bit6: 1000 0000 0000 0000 => (###MSB가 1임)보면 5번째 shift한 후에 MSB가 1이 되는 상황이 온다.
이때 poly를 XOR 해준 후에 shift를 해준다.
bit6: 1000 0000 0000 0000
MSB=1 이므로 shift 후 poly XOR
shift: 1000 0000 0000 0000 -> 0000 0000 0000 0000
XOR : 0000 0000 0000 0000 ^ 0001 0000 0010 0001
= 0001 0000 0010 0001 (0x1021)
bit7: 0001 0000 0010 0001 -> 0010 0000 0100 0010 (shift)최종적으로 CRC는
crc = 0010 0000 0100 0010 (0x2042)이런 값이 나오게 된다.
그럼 이제 이 CRC를 기반으로 다시 LEN을 계산해준다.
방법은 동일하고 최초에 LEN을 8비트 shift 해주고 CRC와 XOR해준다.
CRC = 0010 0000 0100 0010 (0x2042)
LEN<<8 = 0000 0011 0000 0000 (0x0300)
CRC:
0010 0000 0100 0010
XOR 0000 0011 0000 0000
---------------------------------
= 0010 0011 0100 0010 (0x2342)
그리고 동일하게 8비트 shift 하면서 MSB를 확인해서 poly를 XOR 해준다.
bit0: 0010 0011 0100 0010 -> 0100 0110 1000 0100 (shift)
bit1: 0100 0110 1000 0100 -> 1000 1101 0000 1000 (shift)
bit2:
MSB=1
shift: 1000 1101 0000 1000 -> 0001 1010 0001 0000
XOR : 0001 1010 0001 0000 ^ 0001 0000 0010 0001
= 0000 1010 0011 0001 (0x0A31)
bit3: 0000 1010 0011 0001 -> 0001 0100 0110 0010 (shift)
bit4: 0001 0100 0110 0010 -> 0010 1000 1100 0100 (shift)
bit5: 0010 1000 1100 0100 -> 0101 0001 1000 1000 (shift)
bit6: 0101 0001 1000 1000 -> 1010 0011 0001 0000 (shift)
bit7:
MSB=1
shift: 1010 0011 0001 0000 -> 0100 0110 0010 0000
XOR : 0100 0110 0010 0000 ^ 0001 0000 0010 0001
= 0101 0110 0000 0001 (0x5601)이렇게 ETX까지 진행하고 나서
after 0x02 -> 0x2042
after 0x03 -> 0x5601
after 0x10 -> 0x2902
after 0xAA -> 0xA3EB
after 0x55 -> 0x64D9
after 0x03 -> 0xC541결정된 CRC는 0xC541로 이걸 상위 1바이트, 0xC5와 하위 1바이트 0x41로 나눠 CRC_H, CRC_L로 작성하면
STX | LEN | CMD | DATA[0] - DATA[1] | ETX | CLC_H | CLC_L
02 03 10 AA 55 03 C5 41로 완성된 프레임이 된다.
이걸 코드로 작성하면
for _ in range(8):
if crc & 0x0001:
crc = (crc >> 1) ^ poly
else:
crc >>= 1이 된다.
(CRC는 16비트를 유지해야하는데 파이썬의 int는 C의 uint_t처럼 16비트로 고정되어 초과되는 분이 짤리지 않고 계속 늘어나기 때문에 CRC에 AND로 0xFFFF를 해서 16비트를 유지할 수 있게 CRC&=0xFFFF를 해줘야만 한다.)
for _ in range(8):
if crc & 0x8000: # MSB 검사
crc = ((crc << 1) ^ poly) & 0xFFFF
else:
crc = (crc << 1) & 0xFFFF이게 CRC의 계산방법이다.
주의해야할점은 CRC의 범위, 최초 CRC값, Poly의 값 등의 옵션들이 맞지 않으면 CRC도 맞지 않기에 이런 부분을 송수신측이 맞춰서 계산할 수 있어야한다.