순환 중복 검사 수행하기

라이브 스크립트 열기

이 예제에서는 숫자의 비트에서 순환 중복 검사(CRC)를 수행하는 방법을 보여줍니다. CRC는 디지털 시스템에서 데이터 전송 시 오류를 감지하는 데 사용됩니다. 데이터 조각 전송 시 간단한 검사 값이 데이터에 추가됩니다. 검사 값은 데이터의 비트에 대해 다항식 나눗셈을 수행하여 구할 수 있습니다. 데이터가 수신되면 다항식 나눗셈이 반복되고 그 결과가 검사 값과 비교됩니다. 결과가 서로 다르면 전송 중에 데이터가 손상된 것입니다.

수동으로 검사 값 계산하기

전송하려는 메시지인 16비트 이진수로 시작해 보겠습니다.

1101100111011010

검사 값을 구하려면 이 숫자를 다항식 $x^{3} + x^{2} + x + 1$ 로 나누십시오. 이 다항식은 계수 1111로 표현할 수 있습니다.

나눗셈은 단계적으로 수행되며 각 단계 후에는 다항식 제수가 숫자의 가장 왼쪽의 1에 맞춰 정렬됩니다. 4개 항이 있는 다항식으로 나눈 결과에 3개의 비트가 있으므로(일반적으로 길이 $n + 1$ 의 다항식으로 나누면 길이 $n$ 의 검사 값이 생성됨), 나머지를 계산하려면 숫자에 000을 추가하십시오. 각 단계에서 결과는 연산 중인 4개 비트에 대해 비트별 XOR을 사용한 것이며 다른 모든 비트는 변경되지 않습니다.

첫 번째 나눗셈은 다음과 같습니다.

1101100111011010 000
1111
----------------
0010100111011010 000

연속되는 각 나눗셈은 이전 단계의 결과에 대해 연산을 수행하기 때문에 두 번째 나눗셈은 다음과 같습니다.

0010100111011010 000
  1111
----------------
0001010111011010 000

피제수가 모두 0이 되면 나눗셈이 완료됩니다. 위의 두 단계를 포함하여 전체 나눗셈은 다음과 같습니다.

1101100111011010 000
1111
0010100111011010 000
  1111
0001010111011010 000
   1111
0000101111011010 000
    1111
0000010011011010 000
     1111
0000001101011010 000
      1111
0000000010011010 000
        1111
0000000001101010 000
         1111
0000000000010010 000
           1111
0000000000001100 000
            1111
0000000000000011 000
              11 11
0000000000000000 110

이 메시지에 대한 검사 값은 나머지 비트 110입니다.

프로그래밍 방식으로 검사 값 계산하기

MATLAB®에서 비트별 연산으로 같은 작업을 수행하여 검사 값을 구할 수 있습니다. 먼저 메시지와 다항식 제수에 대한 변수를 정의합니다. 나머지에 추가 비트를 사용할 수 있도록 부호 없는 32비트 정수를 사용해 보겠습니다.

message = 0b1101100111011010u32;
messageLength = 16;
divisor = 0b1111u32;
divisorDegree = 3;

다음으로 다항식 제수를 초기화합니다. dec2bin을 사용하여 결과의 비트를 표시합니다.

divisor = bitshift(divisor,messageLength-divisorDegree-1);
dec2bin(divisor)

ans = 
'1111000000000000'

이제 정확한 개수의 비트(메시지는 16비트, 나머지는 3비트)를 갖도록 제수와 메시지를 시프트합니다.

divisor = bitshift(divisor,divisorDegree);
remainder = bitshift(message,divisorDegree);
dec2bin(divisor)

ans = 
'1111000000000000000'

dec2bin(remainder)

ans = 
'1101100111011010000'

for 루프를 사용하여 CRC의 나눗셈 단계를 수행합니다. for 루프는 각 단계마다 항상 한 비트씩 전진하므로, 현재 숫자가 1인지 검사하는 부분을 포함하십시오. 현재 숫자가 1이면 나눗셈 단계가 실행되고 그렇지 않으면 루프는 한 비트 전진하여 계속 진행합니다.

for k = 1:messageLength
    if bitget(remainder,messageLength+divisorDegree)
        remainder = bitxor(remainder,divisor);
    end
    remainder = bitshift(remainder,1);
end

나머지의 비트를 오른쪽으로 시프트하여 연산에 대한 검사 값을 구합니다.

CRC_check_value = bitshift(remainder,-messageLength);
dec2bin(CRC_check_value)

ans = 
'110'

메시지 무결성 확인하기

검사 값을 사용하여 동일한 나눗셈 연산을 반복함으로써 메시지 무결성을 확인할 수 있습니다. 하지만 나머지 000을 사용하여 시작하는 대신, 검사 값 110을 사용하십시오. 메시지에 오류가 없으면 나눗셈 결과가 0이 됩니다.

나머지 변수를 재설정하고 비트별 OR을 사용하여 나머지 비트에 CRC 값을 추가합니다. bitset를 사용하여 비트 값 중 하나를 뒤집어 메시지에서 오류를 발생시킵니다.

remainder = bitshift(message,divisorDegree);
remainder = bitor(remainder,CRC_check_value);
remainder = bitset(remainder,6);
dec2bin(remainder)

ans = 
'1101100111011110110'

CRC 나눗셈 연산을 수행한 다음, 결과가 0인지 확인합니다.

for k = 1:messageLength
    if bitget(remainder,messageLength+divisorDegree)
        remainder = bitxor(remainder,divisor);
    end
    remainder = bitshift(remainder,1);
end
if remainder == 0
    disp('Message is error free.')
else
    disp('Message contains errors.')
end

Message contains errors.

참고 문헌

[1] Sklar, Bernard. Digital Communications: Fundamentals and Applications. Englewood Cliffs, NJ: Prentice Hall, 1988.

[2] Wicker, Stephen B. Error Control Systems for Digital Communication and Storage. Upper Saddle River, NJ: Prentice Hall, 1995.

참고 항목

bitshift | bitxor