Abstract:

A theoretical representation of the CRC codes with the aid of the finite automata in the Galois fields is proposed –linear finite-state machine (LFSM). We examined three types of LSC, which are distinguished by its characteristic matrices: type 1, type 2, and type 3. Three methods of the parallel CRC computation are proposed. The theorems are proven about the estimation of duration of the CRC computation by tuple-parallel method for three types of LFSM. We presented algorithms for the CRC tuple-parallel computation by the tables lookup for different types of LFSM and demonstrated their hardware implementation. For the symbolic-parallel and symbolic-tuple-parallel methods of CRC computation, symbolic LFSM over the non-binary Galois fields are applied. In contrast to the known approaches, which consider the problem of high speed only, present article stresses the need for taking into account a capability to detect errors with the aid of generator polynomials of the CRC codes. We proposed the Hamming codes and the Abramson codes in the binary and non-binary Galois fields for this purpose. Within the framework of single mathematical apparatus – theory of LFSM – it is possible to solve two important tasks simultaneously: to carry out mathematical substantiation of performance efficiency of the methods for parallel CRC computation and to estimate the detection and correction capability of the CRC codes based on LFSM graph models. Such comprehensive approach is relevant in the practice of various data transmission, storage and compression systems.  Author Biography Vasyl Semerenko, Vinnytsia National Technical University Khmelnytske highway, 95, Vinnytsia, Ukraine, 21021 PhD, Associate Professor Department of computer technique

Keywords: