%% Perform Cyclic Redundancy Check
% This example shows how to perform a cyclic redundancy check (CRC) on the bits of a number. CRCs are used to detect errors in the transmission of data in digital systems. When a piece of data is sent, a short check value is attached to it. The check value is obtained by polynomial division with the bits in the data. When the data is received, the polynomial division is repeated, and the result is compared with the check value. If the results differ, then the data was corrupted during transmission.
%
%% Calculate Check Value by Hand
% Start with a 16-bit binary number, which is the message to be transmitted:
% 1101100111011010
% To obtain the check value, divide this number by the polynomial x^3 +x^2 +x+1. You can represent this polynomial with its coefficients: 1111.
% The division is performed in steps, and after each step the polynomial divisor is aligned with the left-most 1 in the number. Because the result of dividing by the four term polynomial has three bits (in general dividing by a polynomial of length n+1 produces a check value of length n), append the number with 000 to calculate the remainder. At each step, the result uses the bit-wise XOR of the four bits being operated on, and all other bits are unchanged.
% The first division is
% 1101100111011010 000
% 1111
% ----------------
% 0010100111011010 000
% Each successive division operates on the result of the previous step, so the second division is
% 0010100111011010 000
%   1111
% ----------------
% 0001010111011010 000
% The division is completed once the dividend is all zeros. The complete division, including the above two steps, is
% 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
% The remainder bits, 110, are the check value for this message.
%
%% Calculate Check Value Programmatically
% In MATLAB®, you can perform this same operation to obtain the check value using bit-wise operations. First, define variables for the message and polynomial divisor. Use unsigned 32-bit integers so that extra bits are available for the remainder.

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

%
% Next, initialize the polynomial divisor. Use dec2bin to display the bits of the result.

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

%
% Now, shift the divisor and message so that they have the correct number of bits (16 bits for the message and 3 bits for the remainder).

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

%
% Perform the division steps of the CRC using a for loop. The for loop always advances a single bit each step, so include a check to see if the current digit is a 1. If the current digit is a 1, then the division step is performed; otherwise, the loop advances a bit and continues.

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

% Shift the bits of the remainder to the right to get the check value for the operation.

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

%
%% Check Message Integrity
% You can use the check value to verify the integrity of a message by repeating the same division operation. However, instead of using a remainder of 000 to start, use the check value 110. If the message is error free, then the result of the division will be zero.
% Reset the remainder variable, and add the CRC check value to the remainder bits using a bit-wise OR. Introduce an error into the message by flipping one of the bit values with bitset.

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

% Perform the CRC division operation and then check if the result is zero.

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

%
% Copyright 2019 The MathWorks, Inc.