Теория и практика CRC кодов: новые результаты на основе автоматных моделей

The theoretical foundations of CRC codes based on the mathematical apparatus of linear finite-state machine (LFSM) were considered.A mathematical analysis of two interpretations of CRC was performed. Interpretation of CRC as Cyclic Redundancy Check means computing the stream hash function or checksum of the given information message I. It is shown that CRC will be an effective hash function (checksum) under the following conditions: CRC generator polynomial must be primitive, of degree r ≥ 16 and the message length must be equal to nw ≤ 2r-1. Cyclic Hamming codes meet such requirements.Interpretation of CRC as Cyclic Redundancy Code means the search for errors by the rules of shortened cyclic code. Using the automaton-graph model, it is shown that generator polynomials of the Abramson code in the form of g(x=(1+x)p(x)), where p(x) is primitive polynomial have the best error detection properties.Only specified Hamming and Abramson codes are proposed to consider as CRC codes and recommendations for the optimal selection of generator polynomials for them were given.A method for parallel CRC computation with the reduction in the number of iterations by ρ (ρ≤r) times for a random polynomial of degree r was proposed.