Введение
Глава 1. Полярные коды и коды Рида-Соломона 15
1.1. Полярные коды 15
1.1.1. Ядро Арикана 18
1.1.2. ЯдроБЧХ 18
1.1.3. Полярные коды как обобщенные каскадные коды 20
1.1.4. Коды произвольной длины 21
1.2. Систематическое кодирование полярных кодов с ядром Арикана 22
1.3. Декодирование полярных кодов 24
1.3.1. Алгоритм последовательного исключения 24
1.3.1.1. Описание алгоритма 24
1.3.1.2. Гауссовская аппроксимация 26
1.3.2. Списочный алгоритм последовательного исключения 27
1.3.3. Стековый алгоритм последовательного исключения 29
1.3.4. Эффективная реализация 30
1.3.4.1. Алгоритм последовательного исключения 31
1.3.4.2. Списочный алгоритм последовательного исключения 34
1.4. Коды Рида-Соломона 36
1.5. Декодирование кодов Рида-Соломона 38
1.5.1. Алгоритм Кёттера-Варди 38
1.5.2. Двумерная интерполяция 41
1.5.2.1. Итеративный интерполяционный алгоритм 42
1.5.2.2. Двоичный интерполяционный алгоритм 43
1.5.2.3. Алгоритм Ли-О Салливана 48
1.5.3. Метод перекодирования 49
1.5.3.1. Замена переменных 49
1.5.3.2. Интерполяция 51
1.5.4. Метод Чейза 51
1.6. Выводы по разделу 52
Глава 2. Построение полярных кодов 54
2.1. Полярные подкоды 54
2.1.1. Представление линейных кодов для декодирования методом последовательного исключения 54
2.1.2. Полярные подкоды БЧХ 57
2.1.2.1. Расширенные коды БЧХ 57
2.1.2.2. Предлагаемая конструкция кодов 61
2.1.3. Выводы 64
2.2. Укорочение полярных кодов с ядром Арикана 65
2.2.1. Идея предлагаемого алгоритма 66
2.2.2. Эквивалентные шаблоны для укорочения 68
2.2.3. Алгоритм оптимизации 71
2.2.4. Оценка снизу для вероятности ошибки декодирования 75
2.2.5. Снижение сложности оптимизации 80
2.2.6. Сложность декодирования укороченных кодов 82
2.2.7. Численные результаты 83
2.2.8. Выводы 86
2.3. Построение полярных кодов с произвольным двоичным ядром 86
2.3.1. Вероятность отказа от декодирования информационного символа 87
2.3.2. Точный метод 88
2.3.3. Приближенный метод 91
2.3.4. Численные результаты 92
2.3.5. Выводы 95
2.4. Выводы по разделу 95
Глава 3. Декодирование полярных кодов 97
3.1. Декодирование методом направленного поиска 97
3.1.1. Описание алгоритма 97
3.1.2. Численные результаты 100
3.1.3. Выводы 100
3.2. Последовательное декодирование полярных кодов с ядром Ари кана 102
3.2.1. Метрика пути 102
3.2.2. Эффективная реализация 104
3.2.3. Численные результаты ПО
3.2.4. Выводы 113
3.3. Алгоритм последовательного исключения для полярных кодов с произвольным двоичным ядром 113
3.3.1. Точный метод 114
3.3.2. Декодирование с помощью порядковых статистик 116
3.3.3. Численные результаты 117
3.3.4. Выводы 117
3.4. Последовательное декодирование полярных кодов с произвольным двоичным ядром 118
3.4.1. Описание алгоритма декодирования 118
3.4.2. Вычисление метрики пути 119
3.4.2.1. Функция ЛК, "1) 119
3.4.2.2. Функция й(г) 119
3.4.3. Улучшенный алгоритм декодирования 120
3.4.4. Реализация 122
3.4.4.1. Промежуточные слои 123
3.4.4.2. Последний слой 124
3.4.5. Численные результаты 125
3.4.6. Выводы 128
3.5. Последовательное декодирование кодов Рида-Соломона 128
3.5.1. Алгоритм последовательного исключения 129
3.5.2. Предлагаемый алгоритм 129
3.5.3. Вычисление функции Q(i) 131
3.5.3.1. Гауссовская аппроксимация 131
3.5.3.2. Упрощенный метод 133
3.5.4. Декодирование двоичного образа кода 136
3.5.5. Численные результаты 137
3.5.6. Выводы 140
3.6. Выводы по разделу 141
Глава 4. Декодирование длинных кодов Рида-Соломона 142
4.1. Послойный алгоритм 142
4.1.1. Построение базиса Грёбнера идеала группы 144
4.1.2. Переход от идеалов групп к идеалу слоя 145
4.1.3. Интерполяция в случае корней переменной кратности 147
4.2. Сходимость рандомизированного алгоритма умножения идеалов 147
4.3. Построение базиса для М 149
4.4. Увеличение кратностей корней 150
4.5. Гибридный алгоритм 153
4.5.1. Описание алгоритма 153
4.5.2. Численные результаты 154
4.6. Комбинаторно-алгебраическое декодирование 154
4.6.1. Описание алгоритма 154
4.6.2. Численные результаты 159
4.7. Выводы по разделу 161
Глава 5. Кодирование для систем хранения данных 162
5.1. Систематическое кодирование 162
5.1.1. Поляризующее преобразование с m = 2 165
5.1.2. Поляризующее преобразование с произвольным m 166
5.2. Быстрое умножение для ядра БЧХ 168
5.3. Анализ сложности 173
5.3.1. Поляризующее преобразование с m = 2 173
5.3.2. Поляризующее преобразование с произвольным m 174
5.3.3. Ядра Арикана и БЧХ 175
5.4. Применение полярных кодов в системах хранения данных 176
5.4.1. Предлагаемый метод кодирования 176
5.4.2. Балансировка нагрузки для группы дисков 178
5.4.3. Балансировка нагрузки между группами дисков 182
5.5. Численные результаты 185
5.6. Выводы по разделу 189
Заключение 191
Список используемых обозначений 194
Литература
