Abstract:

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 . It is shown that CRC will be an effective hash function (checksum) under the following conditions: CRC generator polynomial must be primitive, of degree  and the message length must be equal to . 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 , where  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  () times for a random polynomial of degree  was proposed. Author Biography Василий Петрович Семеренко, Vinnytsia National Technical University Khmelnytske shose 95, Vinnytsia, Ukraine, 21021 PhD, Associate Professor Department of computer technique

Keywords: