«Актуальные вопросы развития инновационно-
информационных технологий на транспорте» АВРИИТТ-2022
I-
Республиканская научно-техническая конференция
(Ташкент, 21-22 ноября 2022 года)
118
ОЦЕНКА ЭФФЕКТИВНОСТИ ОБНАРУЖЕНИЯ
ОШИБОК МЕТОДА CRC4
О.А. Турдиев,
Ташкентский государственный транспортный университет Ассистент
кафедры «Информационные системы и технологии на транспорте»
А.А. Азимов,
Ташкентский государственный транспортный университет Ассистент
кафедры «Информационные системы и технологии на транспорте»
https://doi.org/10.47689/978-9943-7818-0-1-v2-pp118-122
Аннотация. Под эффективностью понимается возможность
выявления и исправления ошибок [1-4]. Для рассматриваемого способа
генерации CRC было написано приложение на языке высокого уровня Java,
позволяющее получить результаты и статистику обнаружения ошибок
в передаваемых данных [5, 6].
Ключевые слова: энергоэффективная сеть, проверка, циклический
избыточный (CRC), коды, технологий, метод, эффективность.
Введение
Статистика показывает обнаружение и необнаружение ошибки [7, 8]. Для
написания приложения использованы программное обеспечение Java
Development Kit версии 1.8 и среда разработки Net Beans IDE 8.0.2 [9].
Эксперимент проводился с помощью следующих аппаратных и программных
ресурсов:
•
операционная система Windows 10 (64-разрядная);
•
двухъядерный процессор Intel Core i3-3217U с тактовой частотой 1,8 Ггц;
•
16 Гб оперативной памяти;
•
жесткий диск объемом 1 Тб.
Программа предназначена для определения целостности передаваемых
данных с использованием метода CRC (Cyclic Redundancy Check, циклический
избыточный код) [10-12].
Программа имитирует процесс передачи данных между источником
(рис. 3) и приемником (рис. 4), а также обеспечивает выполнение следующих
функций:
1.
Задание исходных данных вручную (кнопка «FromText», рис. 3) или
при помощи генератора псевдослучайных символов (кнопка «Random», рис. 3)
или метода класса Random() (создает генератор чисел, использующий
уникальное начальное число) [13].
2.
Конвертацию исходных данных в шестнадцатеричную, восьмеричную
и двоичную системы счисления (поля «hex», «oct», «bin», рис. 3).
3.
По полученным исходным данным проводится подсчет контрольных
сумм CRC циклических избыточных кодов (поле «CRC», рис. 3).
4.
Дополнительно на усмотрение пользователя можно вносить
одиночные или многократные ошибки (кнопка «Random Error», рис. 3)
в исходные данные (в данном случае были использованы двойные ошибки).
«Актуальные вопросы развития инновационно-
информационных технологий на транспорте» АВРИИТТ-2022
I-
Республиканская научно-техническая конференция
(Ташкент, 21-22 ноября 2022 года)
119
Основная часть
После имитации процесса передачи данных [14, 15], заново
производится подсчет контрольных сумм CRC циклических избыточных кодов,
которые впоследствии сравниваются с ранее рассчитанными для выявления
факта искажения передаваемых данных (рис. 4); поле «CRC_TEST»
указывает на обнаруженную ошибку посредством флагов «true» («истина»,
«1», данные верны) и «false» («ложь», «0», данные содержат ошибку).
Рис. 3. Пример отправления случайных битов пакета и CRC4
Рис. 4. Пример обнаружения ошибок CRC4
Анализ результатов обнаружения ошибок методом CRC4
CRC-
коды обладают высокой достоверностью обнаружения искажений.
Доля
0
P
обнаруживаемых искажений не зависит от длины защищаемого
массива данных, а определяется только разрядностью
𝑅
контрольного
кода [6]:
𝑃
0
= 1 − 2
−𝑅
Таким образом для CRC4
4
0
1 2
0.9375
P
−
= −
=
. Исходя из того, что
разрядность контрольной суммы CRC4 составляет 4 бита, очень высока
вероятность возникновения коллизий. Максимально допустимое число
комбинаций контрольной суммы
4
4
2
16.
CRC
=
=
Для оценки вероятности не обнаружения искаженных битов и выявления
факта коллизий был сымитирован процесс передачи данных с ошибочными
битами. Результаты имитации приведены на рисунке 5.
«Актуальные вопросы развития инновационно-
информационных технологий на транспорте» АВРИИТТ-2022
I-
Республиканская научно-техническая конференция
(Ташкент, 21-22 ноября 2022 года)
120
Таблица 2
Результат обнаружения ошибок методом CRC4
№
Передаваемый
символ, char
Шестнадцатеричное
представление
символа, hex
Восьмеричное
представление
символа, oct
Бинарное
представление
символа, bin
Отправлено
0
30
60
01100
0
0 111
1
Получено
2
32
62
01100
1
0 111
0
Из таблицы 2 следует, что при передаче символа 0, искажение может
возникнуть как в передаваемом символе, так и в самой контрольной сумме,
таким образом, что при получении искаженного символа и искаженной
контрольной суммы полученный символ будет восприниматься как
корректный.
Поскольку в эксперименте участвует 12 бит (8 бит под исходный символ
и 4 бита контрольной суммы CRC4), то вероятность искажения отдельного
бита определяется по формуле:
𝑝 =
1
𝑛
= 0.08
,
где
n
– число бит, представляющих передаваемые символы.
Вероятность безошибочной передачи всех n бит [7]:
Рис. 5. Пример необнаружения ошибок CRC4
Рис. 6. Результат определения ошибок алгоритмом CRC4
0
0
1
1
2
6
11
21
36
77
0
10
20
30
40
50
60
70
80
90
1
2
4
8
16
32
64
128
256
512
Кол
ич
ес
тв
о
бит
-пак
ет
ов
с
н
еобнар
уж
енн
ой
ош
и
бк
ой
Количество отправленных ошибочных бит-пакетов
«Актуальные вопросы развития инновационно-
информационных технологий на транспорте» АВРИИТТ-2022
I-
Республиканская научно-техническая конференция
(Ташкент, 21-22 ноября 2022 года)
121
Заключение
В статье рассмотрен способ формирования контрольного суммирования
циклического избыточного кода CRC4. Основная проблема со всеми
проверками CRC4 состоит в возможном появлении коллизий, если в исходные
данные были внесены двукратные или многократные ошибки [16].
Этот факт подтверждается собранной на рисунке 6 статистикой. В силу
небольшой избыточности алгоритм рекомендуется использовать для
значительной экономии памяти и при малых исходных данных, однако стоит
понимать, что вероятность появления коллизии достаточно высока.
БИБЛИОГРАФИЧЕСКИЕ ССЫЛКИ:
1. Halsall F. Fifth edition, computer networks and the Internet / F. Halsall.
–
Addison-
Wesley: Pearson Education, 2005. ‒ P. 803.
2. Lin S. and Costello D.J. Jr. Error Control Coding: Fundamentals and
Applications. Prentice-Hall, Inc., EnglewoodCliffs, N. J., 1983.
3.
Олифер В.Г. Компьютерные сети. Принципы, технологии, протоколы /
В.Г. Олифер, Н.А. Олифер. ‒ СПб.: Питер, 2008. ‒ C. 958.
4. Halsall F. Data communications, computer networks and open systems /
F. Halsall.
– Addison-Wesley: Pearson Education, 1996. ‒ P. 907.
5.
Турдиев О.А., Хомоненко А.Д., Гофман М.В. Сравнение моделей
вероятного кода числа pnc и циклического избыточного кода crc. / Вестник
Российского нового университета. Серия: Сложные системы: модели, анализ
и управление. 2021. – № 4. – С. 119–131.
6. Turdiev O.A., Smagin V.A., Kustov V.N. Investigation of the computational
complexity of the formation of checksums for the cyclic redundancy code Algorithm
depending on the width of the generating polynomial /
В сборнике: CEUR
Workshop Proceedings. Proceedings of Models and Methods of Information
Systems Research Workshop 2020. St. Petersburg, 2020.
– С. 129–135.
7.
Турдиев О.А.,
Клименко С.В.,
Тухтаходжаев А.Б.
Оценки
эффективности обнаружения ошибок контрольного суммирования (crc)
передаваемых данных. / Известия СПбГЭТУ ЛЭТИ. 2019. – № 8. – С. 54–58.
8.
Алиев Р.М. Концепция разработки бесстыковых рельсовых цепей //
Интерактивная наука. – 2021. – №. 6. – С. 56–57.
9. Aliev R. et al. Research the length of the braking distance for speed and
high-speed trains on railway sections // International Journal.
– 2020. – Т. 9. – №. 5.
10. Aliev R.M., Tokhirov E.T., Aliev M.M. The Mathematical Model of the
Sensor for Monitoring the State of the Track Section with Current Receivers //
International Journal of Recent Technology and Engineering (IJRTE).
– 2020. –
Т. 8. – №. 5. – С. 5634–5637.
11. Aliev M. et al. Four-pole rail coefficients of the jointless track circuit in the
presence of one of the ends track circuit insulating joints // Chemical Technology,
Control and Management.
– 2019. – Т. 2019. – №. 4. – С. 89–92.
12. Guliamova M.K., Aliev R.M. Database Concept, Relevance and Expert
Systems // Scientific and Educational Areas Under Modern Challenges.
– 2021. –
С. 125–127.
«Актуальные вопросы развития инновационно-
информационных технологий на транспорте» АВРИИТТ-2022
I-
Республиканская научно-техническая конференция
(Ташкент, 21-22 ноября 2022 года)
122
13. Aliev R. A Rail line model with distributed parameters of track circuit //
IOP Conference Series: Materials Science and Engineering.
– IOP Publishing,
2021.
– Т. 1152. – №. 1. – С. 012018.
14. Tashmetov K. et al. Expert system for diagnosing faults railroad switch
of automation and telemechanic systems // AIP Conference Proceedings.
–
AIP Publishing LLC, 2022.
– Т. 2432. – №. 1. – С. 030083.
15. Aliev R., Aliev M. Methods calculation for station tonal rail circuits
with current receiver // Transportation Research Procedia.
– 2022. – Т. 63. –
С. 401–411.
16. Aliev R.M., Aliev Marat Mukhamedovich, Tokhirov E.T. Improvement
Sensors of System Crossing Signalization and Reduction Delays at Level
Crossings //
Монография / Международный центр научного партнерства
«Новая Наука», 2022, – C. 110.
