1
$\begingroup$

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'
    input_padded_array = list(input_bitstring + initial_padding)

    while '1' in input_padded_array[:len_input]:
        cur_shift = input_padded_array.index('1')

        for i in range(len(polynomial_bitstring)):
            input_padded_array[cur_shift + i] = str(int(polynomial_bitstring[i] != input_padded_array[cur_shift + i]))
    return ''.join(input_padded_array)[len_input:]


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()
$\endgroup$
4
  • $\begingroup$ Do you understand what CRC actually means, as a polynomial division in $GF(2)$? $\endgroup$
    – Pseudonym
    Commented Apr 27 at 12:10
  • $\begingroup$ 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). $\endgroup$
    – MotiNK
    Commented Apr 27 at 12:45
  • $\begingroup$ @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. $\endgroup$ Commented Apr 27 at 18:03
  • $\begingroup$ @Pseudonym I think I don't fully understand what GF(2) means, but I understand the Computation as described by Wikipedia. $\endgroup$ Commented Apr 27 at 18:07

1 Answer 1

2
$\begingroup$

If I remember right, CRC is defined for sequences of bits, but you can take an input byte and pre-calculate what the next 8 operations would be, and what their effect would be. So with a table of 256 .= 2^8 values you can process eight bits at a time. Or with a table wit 65,536 entries, it’s 16 bits at a time.

And with Python it depends on the actual implementation of your code, so you need to measure the speed. And to be honest, you are better off with a library written in C. And using character arrays representing bits with ‘0’ and ‘1’ makes me cringe.

$\endgroup$
1
  • $\begingroup$ The implementation in Python is only for illustration. I might use C or C++. I may have been unclear, but the question which one is faster or using a table, isn't of particular interest at the moment. The question really boils down to why both implementations do the same. $\endgroup$ Commented Apr 27 at 18:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.