Завадський Ігор Олександрович Подільні коди та їх застосування

Короткий опис

Завадський Ігор Олександрович, доцент кафедри математичної інформатики факультету комп’ютерних наук та кібернетики, Київський національний університет імені Тараса Шевченка. Назва дисертації: «Подільні коди та їх застосування». Шифр та назва спеціальності 01.05.01 теоретичні основи інформатики та кібернетики. Спецрада Д26.001.09 Київського національного університету імені Тараса Шевченка

Київський національний університет імені Тараса Шевченка
Міністерство освіти і науки України
Київський національний університет імені Тараса Шевченка
Міністерство освіти і науки України
Кваліфікаційна наукова праця
на правах рукопису
ЗАВАДСЬКИЙ ІГОР ОЛЕКСАНДРОВИЧ
УДК 519.72 : 519.688
ДИСЕРТАЦІЯ
Подільні коди та їх застосування
01.05.01 – теоретичні основи інформатики та кібернетики
Подається на здобуття наукового ступеня доктора фізико-математичних наук
Дисертація містить результати власних досліджень. Використання ідей,
результатів і текстів інших авторів мають посилання на відповідне джерело.
_____________________________________ І.О. Завадський
Науковий консультант Анісімов Анатолій Васильович, доктор фізико -
математичних наук, професор, член-кореспондент НАН України
Київ – 2020

Зміст
ВСТУП .................................................................................................................... 6
1. Аналіз методів завадостійкого та стискального кодування, а також пошуку
рядка в тексті....................................................................................................... 15
1.1. Завадостійке кодування............................................................................. 16
1.1.1. Моделі та граничні співвідношення завадостійкого кодування ....... 16
1.1.2. Блокові завадостійкі коди ...................................................................... 22
1.1.3. Згорткові завадостійкі коди та їх удосконалення ................................. 26
1.1.4. Коди, що наближуються до границі Шеннона ...................................... 30
1.2. Стискальне кодування ............................................................................... 32
1.2.1. Класифікація та загальні властивості методів стискального кодування . 32
1.2.2. Основні поняття та співвідношення теорії стискального кодування ... 36
1.2.3. Огляд стискальних кодів ........................................................................ 43
1.2.4. Патерн-коди та їх узагальнення ............................................................. 47
1.2.5. Байтові коди ........................................................................................... 57
1.3. (2,3)-коди ...................................................................................................... 60
1.4. Пошук у стиснутих текстах ............................................................................ 65
Висновки за розділом 1 ...................................................................................... 78
Розділ 2. Коди на основі двобазисних систем числення та їх застосування ..... 79
2.1.Нижній (2,3)-код ............................................................................................ 80
2.1.1. Нижнє (2,3)-розкладання цілих чисел ................................................... 80
2.1.2. Означення, кодування та декодування нижнього (2,3)-коду ............... 87
2.1.3. Властивості базового нижнього (2,3)-коду ............................................ 96
2.1.4. Завадостійкість базового нижнього (2,3)-коду ................................... 102
3
2.2. Модифікації нижнього (2,3)-коду ............................................................ 112
2.2.1. Компактний нижній (2,3)-код ............................................................ 112
2.2.2. Модифікований компактний нижній (2,3)-код ................................... 118
2.2.3. Збалансований нижній (2,3)-код ....................................................... 119
2.3. Код (2,3,z) .................................................................................................. 123
2.3.1. Структура коду ...................................................................................... 123
2.3.2. Перетворення довільної бітової послідовності на число з ℕ

Список літератури

Висновки
У дисертаційній роботі досліджено нові методи завадостійкого та
стискального кодування, а також пошуку даних у закодованих файлах, що
покращують характеристики відомих методів, призначених для розв’язання
названих задач, у широкому діапазоні значень вхідних параметрів. Означено та
досліджено поняття подільності коду, яке застосовано для визначення
асимптотичних характеристик та доведення теоретичних властивостей широкого
класу стискальних і завадостійких кодів.
Одержано такі основні результати:
1. Означено нижній (2,3)-код — подільний код на основі двобазисної
системи числення, досліджено його теоретичні властивості та
можливість застосування в завадостійкому та стискальному
кодуванні.
2. На основі нижнього (2,3)-коду побудовано схему завадостійкого
передавання даних, яка з імовірністю майже 100% виправляє 2 помилки в
інформаційних повідомленнях довжиною від кількох десятків бітів, збільшуючи
цю довжину в 1,15 разів у середньому.
3. Означено завадостійкий код (2,3,z) та розроблено двошарову схему
завадостійкого кодування з використанням цього коду та нижнього (2,3)-коду,
що дає змогу близькою до 1 ймовірністю виправляти до 15 помилок у
повідомленні довжиною 150 бітів, якщо в кожній тріаді бітів із номерами k, k+1,
k+2 є не більше 1 помилки.
4. Створено двошарову схему завадостійкого кодування з
використанням нижнього (2,3)-коду та згорткового коду спеціального вигляду,
показники завадостійкості якої є вищими за показники аналогів у разі пакетного
передавання даних у каналах із високим рівнем шуму.
5. Означено мультироздільникові та реверсні мультироздільникові
стискальні коди, досліджено їхні теоретичні властивості та визначено показники
ефективності. Вони є першими стискальними кодами, що, маючи всі якісні
312
характеристики кодів Фібоначчі, є більш гнучкими та перевершують їх як за
стискальною ефективністю, так і за швидкістю кодування й декодування.
6. Побудовано декодувальні автомати для мультироздільникових та
реверсних мультироздільникових кодів, а також прискорені побайтові алгоритми
декодування на основі квантифікації роботи цих автоматів.
7. Побудовано родину алгоритмів пошуку рядка в тексті, у яких
використовується кілька суміжних вікон пошуку. Вони мають кращу швидкодію
серед усіх відомих алгоритмів для широкого діапазону довжин патернів на
алфавітах, що містять 4 або 8 символів.
8. Створено родину спеціалізованих алгоритмів пошуку рядка в тексті
на 256-символьному алфавіті, що використовують новітній підхід зсуву вікна
пошуку на основі інформації про його суфікс, що складається з нецілої кількості
байтів. Представники цієї родини перевершують відомі аналоги в широкому
діапазоні довжин патернів.
9. Створено родину алгоритмів пошуку рядка в бінарному тексті, що
мають кращу швидкодію за всі інші відомі алгоритми для широкого діапазону
довжин патернів.
Результати дисертації можуть бути використані у створенні
високоефективних систем зберігання великих обсягів даних та їхнього пошуку,
а також для захисту даних у разі їх передавання середовищем із високим рівнем
шуму.