Checksum

Checksum은 데이터 블록 전체로부터 계산한 값을 덧붙여, 수신 측이 같은 계산을 반복해 값이 어긋나면 오류로 판정하는 방식이다. Parity Bit가 데이터 하나마다 1비트만 검사하는 것과 달리, 체크섬은 블록 전체에 여러 비트를 할당해 검출 능력을 높인다. 계산 방식은 여러 가지가 쓰인다.

가장 단순한 방식은 LRC(Longitudinal Redundancy Check)로, 데이터를 바이트·워드 단위로 XOR한 값을 체크섬으로 쓴다[1].

또 다른 방식은 모든 데이터를 바이트·워드 단위로 더한 뒤 그 합의 보수를 체크섬으로 쓰는 합 기반 체크섬이다. 덧셈에서 자리 올림(carry)이 생기면 최하위 비트에 다시 더하는 end-around carry로 처리하고 최종 합을 반전(1의 보수)한다 — 수신 측이 받은 데이터의 합에 이 체크섬을 같은 방식으로 다시 더했을 때 전 비트가 1인 값이 나오면 정상으로 판정한다[2].

Example

LIN은 이 합 기반 체크섬을 데이터 바이트에만 적용하는 classic checksum과, 여기에 PID(Protected Identifier) 바이트까지 포함하는 enhanced checksum으로 나눠 쓴다. 데이터 0x4A, 0x55, 0x93, 0xE5를 end-around carry로 더하면 0x19가 되고, 이를 반전한 0xE6이 체크섬이 된다 — 수신 측이 받은 데이터의 합(0x19)에 수신한 체크섬(0xE6)을 더해 0xFF가 나오면 정상이다[3].

체크섬은 패리티보다 더 많은 비트를 오류 검출에 쓰지만, 단순 합 기반 방식은 워드·바이트의 순서가 뒤바뀌는 오류를 검출하지 못한다는 약점이 있다[4]. Fletcher’s checksum은 이 약점을 보완하도록 설계된 대안이며[5], Adler-32는 zlib 압축 포맷이 채택한 또 다른 변형이다[6]. 이런 한계를 다항식 나눗셈으로 근본적으로 줄인 방식이 CRC다.

참고문헌

[1]

ISO, “ISO 1155:1978 — Information processing — Use of longitudinal parity to detect errors in information messages”, 1978.

[2]

R. Braden, D. Borman and C. Partridge, “RFC 1071 — Computing the Internet Checksum”. 1988. [Online]. Available at: https://www.rfc-editor.org/rfc/rfc1071

[3]

LIN Consortium, “LIN Specification Package, Revision 2.2A”, 2010.

[4]

J. Zweig and C. Partridge, “RFC 1146 — TCP Alternate Checksum Options”. 1990. [Online]. Available at: https://www.rfc-editor.org/rfc/rfc1146

[5]

J. G. Fletcher, “An Arithmetic Checksum for Serial Transmissions”, IEEE Transactions on Communications, vol 30, no. 1, pp 247–252, 1982.

[6]

P. Deutsch and J.-L. Gailly, “RFC 1950 — ZLIB Compressed Data Format Specification version 3.3”. 1996. [Online]. Available at: https://www.rfc-editor.org/rfc/rfc1950