# fast CRC computation

I have two implementations of the crc calculation. The crc_classic is based on the typical implementation you can find for example on Wikipedia

The second one might be found in D.3.2 here IO-Link

I'm looking for an explanation why the second one does the same as the first one. The second one is typically considered faster. It uses a running calculation, while the first one uses an in-place calculation on the input data. So far so good. But I find it hard to see why this is the same. I would never have found the second implementation myself.

Is there maybe a transformation from one into the other? Or another good explanation or proof why they give the same output?

def crc_classic(input_bitstring, polynomial_bitstring):
len_input = len(input_bitstring)

initial_padding = (len(polynomial_bitstring) - 1) * '0'

while '1' in input_padded_array[:len_input]:

for i in range(len(polynomial_bitstring)):
input_padded_array[cur_shift + i] = str(int(polynomial_bitstring[i] != input_padded_array[cur_shift + i]))

def crc_running(input_bitstring, polynomial_bitstring):
len_input = len(input_bitstring)

result = '000'

for n in range(len_input):
if result[0] != input_bitstring[n]:
result = result[1:] + '0'
result = ''.join(str(int(polynomial_bitstring[i+1] != result[i])) for i in range(len(result)))
else:
result = result[1:] + '0'
return result

def main():
input_bitstring = '11010011101100'
polynomial_bitstring = '1011' #must have a leading 1
print(crc_classic(input_bitstring, polynomial_bitstring))
print(crc_running(input_bitstring, polynomial_bitstring))

main()

• Do you understand what CRC actually means, as a polynomial division in $GF(2)$? Commented Apr 27 at 12:10
• Could you please provide more details on the second implementation? Providing a link to a 178 page PDF is a serious impediment to reviewing the second implementation (I'm assuming the implementation doesn't requires 100+ pages of reading). Commented Apr 27 at 12:45
• @MotiNK It is in chapter D.3.2. That is all the information I got so far. I have seen implementations of this algorithm and I know it is correctly working. Commented Apr 27 at 18:03
• @Pseudonym I think I don't fully understand what GF(2) means, but I understand the Computation as described by Wikipedia. Commented Apr 27 at 18:07