[Algorithm] Check Sum

Data를 전송 할 때 data의 무결성을 검증하기 위해 사용하는 기법이다. Parity bit은 단순히 1의 개수가 홀수인지, 짝수인지를 확인하는데 이 때 data가 짝수개가 변경되면 parity bit을 통해서 무결성을 검증하기 어렵다. Check Sum은 Sender 쪽에서 전체 data에 특정 data를 심어놓고 Receiver에서 Check Sum value를 통해 무결성을 증명한다.

Check Sum 구하기

struct payload {
    unsigned short data0; 
    unsigned short data1;
    unsigned short data2;
    unsigned short checksum;
    unsigned int   addr;
};

만약 위 구조의 data를 전달한다고 했을 때, 각 data 및 address의 값이 임의의 값으로 전달된다고 가정하면, Check Sum 값을 구하기 위해선 우선 해당 값들을 모두 더한다.
결과를 보면 1이 carry가 발생했는데, 해당 값을 다시 더해주고 난 결과의 inversion을 시킨 결과가 Check Sum 값이다.

Decoding

그럼 Check Sum을 가지고 data 무결성을 확인하는 방법은, 1) 넘어온 data를 모두 동일하게 2 bytes 단위로 더해주고, 2) carry가 발생하면 data에 더해주고, 3) 모든 bit inversion을 해서 0으로 나오는지 확인한다.

이런 Check Sum에도 한계점이 있는데, 만약 data 중 하나의 data가 증가하고 또 다른 data가 감소의 값이 같을 경우, 즉 전체의 합에 변동이 없을 때는 error를 발견 할 수 없는 문제가 있다.