Програмно-апаратні засоби паралельного обчислення CRC-кодів в системах передачі даних

Abstract

В магістерській роботі розроблені теоретичні основи паралельних кодів CRC за допомогою теорії лінійних послідовнісних схем (ЛПС). Проведено порівняльний аналіз послідовного, кортежно-паралельного і символьно-паралельного способу обчислення CRC. Запропоновано спосіб прискореного обчислення контрольних сум на основі темпоральних моделей. Детально показано особливості використання CRC в пристроях пам’яті (оперативної памяті, жорстких дисках, флеш-пам'яті,), а також в мережі Ethernet, архіваторах (RAR, ZIP,7Z) і системах RAID. А також описані дві версії апаратної реалізації прискорення CRC-кодів: – паралельна передача даних на основі темпоральних моделей ЛПС типу Галуа; – паралельна передача даних на основі темпоральних моделей ЛПС типу Фібоначчі. Описано автоматно-аналітичну і автоматно-графову моделі циклічного коду. Розглянуто два основні типи ЛПС: – рекурсивна ЛПС типу Галуа; – рекурсивна ЛПС типу Фібоначчі. Описано способи швидкого обчислення CRC для реверсивних каналів передачі даних на основі симетрії часу. Де було представлено два типи ЛПС: пряма (базова) і обернена (реверсивна). Також представлена апаратна реалізація контролю даних у флеш-пам’яті, за допомогою кодів CRC, для прискорення формування контрольної інформації, та зменшення кількості операцій стирань та запису у флеш-пам’ять.

In master's thesis the theoretical bases of parallel CRC codes by means of theory of the linear finite‐state machine (LFSM) are done. A comparative analysis of a successive, a tuple-parallel and a symbol-parallel methods of CRC calculation is conducted. The method of the fast calculation of check sum on based of the temporal models is suggested. In detail the features of the use of CRC in the memory devices (RAM, hard drives, flash memory), as well as Ethernet, archivers (RAR, ZIP, 7Z) and RAID systems are shown in detail. Two versions of hardware implementation of acceleration of CRC-codes are also described: - parallel transmission of data based on the temporal models of LPS type Galois; - Parallel data transfer on the basis of temporal models of LPI type Fibonacci. The automaton-analytical and automaton-graph model of the cyclic code is described. Two main types of LPS are considered: - recurrent LPS type Galois; - Fibonacci type recursive FPS. The methods of rapid CRC calculation for reversible data transmission channels based on time symmetry are described. Where two types of LPS were presented: direct (basic) and inverse (reversal). Also provided hardware implementation of data control in flash memory, using CRC codes, to accelerate the formation of control information, and reduce the number of erase operations and write to flash memory.