I'm trying to understand the CRC (Cyclic Redundancy Check) algorithm and I'm having trouble identifying the polynomial used in a particular CRC implementation.
function[output_data]=ASK_AddCRC(input_data,crc_num)
input_num=length(input_data);
output_data=zeros(1,input_num+crc_num);
crcBit=zeros(1,crc_num);
regOut=zeros(1,crc_num);
switch crc_num
case 0
output_data=input_data;
case 8
for num=1:input_num;
regOut=crcBit;
crcBit(8)=xor(regOut(7),xor(regOut(8),input_data(num)));
crcBit(7)=regOut(6);
crcBit(6)=regOut(5);
crcBit(5)=xor(regOut(4),xor(regOut(8),input_data(num)));
crcBit(4)=xor(regOut(3),xor(regOut(8),input_data(num)));
crcBit(3)=regOut(2);
crcBit(2)=xor(regOut(1),xor(regOut(8),input_data(num)));
crcBit(1)=xor(regOut(8),input_data(num));
end
output_data(1,1:input_num)=input_data(1,1:input_num);
output_data(1,input_num+1:input_num+crc_num)=crcBit;
case 12
for num=1:input_num;
regOut=crcBit;
crcBit(12)=xor(regOut(11),xor(regOut(12),input_data(num)));
crcBit(11)=regOut(10);
crcBit(10)=regOut(9);
crcBit(9)=regOut(8);
crcBit(8)=regOut(7);
crcBit(7)=regOut(6);
crcBit(6)=regOut(5);
crcBit(5)=regOut(4);
crcBit(4)=xor(regOut(3),xor(regOut(12),input_data(num)));
crcBit(3)=xor(regOut(2),xor(regOut(12),input_data(num)));
crcBit(2)=xor(regOut(1),xor(regOut(12),input_data(num)));
crcBit(1)=xor(regOut(12),input_data(num));
end
output_data(1,1:input_num)=input_data(1,1:input_num);
output_data(1,input_num+1:input_num+crc_num)=crcBit;
case 16
for num=1:input_num;
regOut=crcBit;
crcBit(16)=regOut(15);
crcBit(15)=regOut(14);
crcBit(14)=regOut(13);
crcBit(13)=xor(regOut(12),xor(regOut(16),input_data(num)));
crcBit(12)=regOut(11);
crcBit(11)=regOut(10);
crcBit(10)=regOut(9);
crcBit(9)=regOut(8);
crcBit(8)=regOut(7);
crcBit(7)=regOut(6);
crcBit(6)=xor(regOut(5),xor(regOut(16),input_data(num)));
crcBit(5)=regOut(4);
crcBit(4)=regOut(3);
crcBit(3)=regOut(2);
crcBit(2)=regOut(1);
crcBit(1)=xor(regOut(16),input_data(num));
end
output_data(1,1:input_num)=input_data(1,1:input_num);
output_data(1,input_num+1:input_num+crc_num)=crcBit;
case 24
for num=1:input_num;
regOut=crcBit;
crcBit(24)=xor(regOut(23),xor(regOut(24),input_data(num)));
crcBit(23)=regOut(22);
crcBit(22)=regOut(21);
crcBit(21)=regOut(20);
crcBit(20)=regOut(19);
crcBit(19)=regOut(18);
crcBit(18)=regOut(17);
crcBit(17)=regOut(16);
crcBit(16)=regOut(15);
crcBit(15)=regOut(14);
crcBit(14)=regOut(13);
crcBit(13)=regOut(12);
crcBit(12)=regOut(11);
crcBit(11)=regOut(10);
crcBit(10)=regOut(9);
crcBit(9)=regOut(8);
crcBit(8)=regOut(7);
crcBit(7)=xor(regOut(6),xor(regOut(24),input_data(num)));
crcBit(6)=xor(regOut(5),xor(regOut(24),input_data(num)));
crcBit(5)=regOut(4);
crcBit(4)=regOut(3);
crcBit(3)=regOut(2);
crcBit(2)=xor(regOut(1),xor(regOut(16),input_data(num)));
crcBit(1)=xor(regOut(24),input_data(num));
end
output_data(1,1:input_num)=input_data(1,1:input_num);
output_data(1,input_num+1:input_num+crc_num)=crcBit;
otherwise
fprintf('error\n');
end
I'm not sure what polynomial is being used in this implementation. Could someone please help me identify it? Additionally, could you provide a explanation of the algorithm's principles?
have understood the principle of manual calculation of CRC and implementing by flipping the bits after finding a 1.
There are four CRCs there, not one. The CRC is selected by crc_num, which is also the number of bits in the CRC: 8, 12, 16, or 24. The output is the input message of input_num bits with a crc_num-bits CRC appended to it. (Case 0 is not a CRC. It just copies the input data and doesn't append anything to it.)
The CRC polynomials can be read off of the expressions, where it is a 0 for just copying the bit, or 1 for exclusive-oring the bit with the input bit and the high bit of the previous CRC value. Note that the bits are being shifted up by one each time.
Those are 10011011, 100000001111, 0001000000100001, and 100000000000000001100011. Each can be written as a polynomial by making each 1 bit a power of x for that position, and adding x raised to crc_num. So the first one is x8+x7+x4+x3+x+1.
In C, each step with one inputBit would be written thusly, using the 8-bit case as an example:
crcBit ^= inputBit << 7;
crcBit = crcBit & 0x80 ? (crcBit << 1) ^ 0x9b : crcBit << 1;