URSS.ru Магазин научной книги
Обложка Конопелько В.К., Липницкий В.А. Теория норм синдромов и перестановочное декодирование помехоустойчивых кодов Обложка Конопелько В.К., Липницкий В.А. Теория норм синдромов и перестановочное декодирование помехоустойчивых кодов
Id: 122550
512 р.

Теория норм синдромов и перестановочное декодирование помехоустойчивых кодов Изд. 3

2012. 176 с.
Газетная пухлая бумага
  • Мягкая обложка

Аннотация

В настоящей книге изложены основы теории норм синдромов --- теории инвариантов циклической и циклотомической групп автоморфизмов классических помехоустойчивых кодов. Обнаружены глубокие конструктивные возможности по коррекции ошибок известными кодами, в принципе, исчерпывающие весь спектр потенциальных возможностей кодов. В двухуровневую схему коррекции ошибок (обнаружение --- исправление) введено промежуточное звено --- идентификация ошибок,... (Подробнее)


Содержание
top
Введение
1.Алгоритмы декодирования классических помехоустойчивых кодов
 1.1.Алгебраические методы декодирования помехоустойчивых кодов
 1.2.Перестановочное декодирование помехоустойчивых кодов
2.Классификация векторов-ошибок двоичных кодов с помощью группы циклических сдвигов
 2.1.Множество ошибок двоичных кодов, их веса и диаметры
 2.2.Классификация векторов-ошибок посредством группы циклических сдвигов
 2.3.Структура неполных Г-орбит
 2.4.Классификация ошибок веса 1 и 2
 2.5.Классификация векторов-ошибок веса 3
3.Синдромы ошибок в двоичных примитивных БЧХ-кодах с минимальным расстоянием 5
 3.1.О некоторых гомоморфизмах мультипликативной группы поля Галуа характеристики 2
 3.2.О полноте множества синдромов ошибок линейных кодов
 3.3.Специфика синдромов ошибок в двоичных примитивных БЧХ-кодах с минимальным расстоянием 5
 3.4.Синдромные признаки полных Г-орбит
 3.5.Спектры синдромов неполных Г-орбит
 3.6.Синдромы векторов-ошибок веса 1, 2
4.Нормы синдромов в БЧХ-кодах с минимальным расстоянием 5, их свойства и значение
 4.1.Основные определения и результаты
 4.2.Нормы Г-орбит
 4.3.Равномерное распределение синдромов по нормам
 4.4.Г-орбиты с вырожденными нормами
 4.5.Распределение синдромов внутри Г-орбит
 4.6.Основная теорема о нормах синдромов
5.МЕТОД НОРМ КОРРЕКЦИИ ОШИБОК И ЕГО ВОЗМОЖНОСТИ
 5.1.Суть метода норм
 5.2.Алгоритм коррекции ошибок БЧХ-кодом с помощью норм синдромов
 5.3.Потенциальные возможности метода норм
 5.4.БЧХ-код минимальной длины
 5.5.Декодирование БЧХ-кодов на основе метода норм синдромов на вентильных матрицах
 5.6.Условия совместной коррекции двойных ошибок и пакетов ошибок длины 3
 5.7.Условия совместной коррекции двойных ошибок и пакетов ошибок длины 3,4 БЧХ-кодом с кодовым расстоянием 5
6.Нормы синдромов в реверсивных кодах, их свойства и значение
 6.1.История вопроса и основные результаты
 6.2.Необходимые сведения о реверсивных кодах
 6.3.Спектры синдромов Г-орбит
 6.4.Синдромы векторов-ошибок веса 1,2
 6.5.Нормы синдромов в реверсивных кодах и спектр из значений
 6.6.Нормы Г-орбит
 6.7.Декодирование реверсивных кодов норменным методом
 6.8.Потенциальные корректирующие возможности метода норм для реверсивных кодов
 6.9.Совместная коррекция двойных и сочетаний ошибок веса 3
 6.10.Коррекция пакетов ошибок длины 4
 6.11.Коррекция модулей ошибок длины 4 совместно с двойными случайными ошибками
7.Синдромы ошибок в двоичных примитивных БЧХ-кодах с минимальным расстоянием 7
 7.1.Необходимые сведения о полях Галуа характеристики 2
 7.2.Решение систем уравнений в полях Галуа характеристики 2
 7.3.Специфика синдромов ошибок в двоичных примитивных БЧХ-кодах с минимальным расстоянием 7
 7.4.Синдромные признаки полных Г-орбит
 7.5.Спектры синдромов неполных Г-орбит
 7.6.Синдромы веторов-ошибок веса 1, 2, 3
8.Нормы синдромов в двоичных примитивных БЧХ-кодах с минимальным расстоянием 7
 8.1.Основные определения
 8.2.Нормы Г-орбит
 8.3.Равномерное распределение синдромов по нормам
 8.4.Норменные признаки полных Г-орбит
 8.5.Основная теорема о нормах синдромов
9.Применение метода норм коррекции ошибок для примитивных БЧХ-кодов с минимальным расстоянием?
 9.1.Алгоритм декодирования на основе метода норм и его потенциальные возможности
 9.2.Примитивные БЧХ-коды длины 15;31, корректирующие пакеты и тройные ошибки
10.Циклотомические подстановки
 10.1.Основные свойства циклотомических подстановок
 10.2.Влияние циклотомических подстановок на синдромы векторов-ошибок
 10.3.Нормы синдромов циклотомически связанных векторов-ошибок
 10.4.Коррекция ошибок с применением G-орбит
 10.5.Метод коррекции трехкратных ошибок на основе сжатия множества норм синдромов
11.Теория норм синдромов для произвольных примитивных БЧХ-кодов
 11.1.Свойства степенных отображений в полях Галуа характеристики 2
 11.2.Специфика синдромов в двоичных примитивных БЧХ-кодах
 11.3.Синдромные признаки полных Г-орбит
 11.4.Спектры синдромов неполных Г-орбит
 11.5.Нормы синдромов в произвольных БЧХ-кодах
 11.6.Основная теорема о нормах синдромов
12.Декодирование кодов, контролирующих зависимые ошибки
 12.1.Коррекция пакетов ошибок удлиненными реверсивными кодами
 12.1.1.Декодирование лексикографически упорядоченных реверсивных кодов
 12.1.2.Контроль сплошных пакетов ошибок реверсивными кодами
 12.2.Декодирование кодов Рида-Соломона норменным методом
 12.2.1.Взаимосвязь БЧХ-кодов с кодами Рида-Соломона
 12.2.2.Коррекция модулей ошибок кодами Рида-Соломона с помощью норм синдромов
 12.3.Перестановочное декодирование данных в формате ASCII
Заключение
Литература

Введение
top

Теория и практика помехоустойчивых кодов имеет полувековую историю. Ее общепризнанным родоначальником является К.Шеннон. В 1948 году была опубликована его статья [120], где обосновывалась возможность передачи информации по каналу с шумами с помощью кодов, контролирующих ошибки, так, что вероятность ошибки на выходе будет сколь угодно малой. Однако в работе не указаны пути нахождения подходящих кодов, эффективных алгоритмов их обработки, а лишь доказано их существование. Дальнейшие исследования шли в двух направлениях: поиска кодов с хорошими характеристиками и практического использования кодов в различных каналах передачи, обработки и хранения информации.

Первое направление развивалось весьма успешно. К настоящему моменту разработано достаточно большое множество различных помехоустойчивых кодов с хорошими параметрами по контролю как случайных, так и зависимых (пакетных, модульных) ошибок. В последние годы большое внимание уделяется синтезу кодов, предназначенных для совместной коррекции данных ошибок. Наибольшую популярность получили коды Боуза–Чоудхури–Хоквингема (БЧХ-коды), коды Рида–Соломона (PC-коды), их всевозможные модификации, другие коды специального назначения, нашедшие широчайшее применение во всех областях информатики и радиоэлектроники. Эти коды позволяют реализовать системы и устройства с недостижимыми ранее потребительскими параметрами, существенно улучшить характеристики существующих систем. Вместе с тем на практике не используются множество хороших кодов, предназначенных для коррекции многократных ошибок из-за отсутствия алгоритмов их обработки с низкими вычислительными затратами.

Основной причиной данного положения является сложность задач обработки данных кодов, поскольку увеличение числа исправляемых ошибок ведет к экспоненциальному росту анализируемых декодером всевозможных состояний ошибок, отсутствию хорошо реализуемых математических методов по решению уравнений в полях Галуа. Кроме того, существующие алгоритмы декодирования данных кодов, как правило, не конструктивны, не позволяют реализовать весь спектр их потенциальных возможностей по контролю ошибок, не ориентированы на последние достижения микроэлектроники в области СБИС процессоров для обработки кодов и сигналов.

Борьба с ошибками обычно ведется на двух уровнях – обнаружение и коррекция ошибок. Введение третьего уровня – идентификации – позволяет, как показывают исследования, после обнаружения ошибок определить их отдельные параметры (например, вес, расстояние между ошибочными разрядами) и затем выбрать оптимальный алгоритм дальнейшей обработки информации. Кроме того, идентификация ошибок позволяет упростить реализацию устройств декодирования кодов.

Опыт эксплуатации средств передачи и хранения информации показывает, что после случайных ошибок малого веса наиболее вероятны группирующиеся ошибки – однократные модули или пакеты. Поэтому актуальна проблема разработки кодов и устройств совместной коррекции случайных и зависимых группирующихся ошибок.

Среди многообразия методов декодирования помехоустойчивых кодов специалисты выделяют как наиболее перспективное, но практически не разработанное – перестановочное декодирование [62].

Данная монография подводит итоги разработки нового подхода к перестановочному декодированию, обосновывает и показывает его эффективность на различных кодах. В теорию кодирования введен новый параметр – норма синдрома. Он является инвариантом при циклических сдвигах координат векторов. Это позволяет классифицировать возможные ошибки, найти идентификаторы этих классов (нормы синдромов) и на их основе предложить перестановочный метод коррекции ошибок. Данный метод хорошо реализуется на основе высоко интегрированных схем ПЛМ, ПЛИС, ПЗУ, допускает высокую степень распараллеливания алгоритмов коррекции.

Материал книги состоит из 12 глав.

В главе 1 приводится краткий анализ алгоритмов коррекции ошибок классическими кодами.

В главе 2 изложена систематическая классификация всевозможных векторов-ошибок в линейных кодах. В основу классификации положена группа Г – циклических сдвигов, принадлежащая группе автоморфизмов любого циклического кода. Таким образом, векторы-ошибки переходящие друг в друга посредством циклических сдвигов образуют один класс эквивалентности – Г-орбиту. Каждая Г-орбита содержит не более n векторов, где n – длина кода. Показано, что большинство Г-орбит – полные (содержат по n векторов). Дано описание неполных Г-орбит, а также всех орбит ошибок веса 1–3 [139].

Главы 3–5 посвящены теории норм синдромов для классических БЧХ-кодов с кодовым расстоянием d = 5, нашедших широчайшее применение в современных системах передачи, обработки и хранения информации [129–132, 136, 139, 140]. В главе 3 описана специфика синдромов ошибок принадлежащих той или иной Г-орбите: зависимость между ошибками Г-орбиты имеет столь же четкое отражение на их синдромы. Описаны спектры синдромов неполных Г-орбит, ошибок малого веса (1–3), даны синдромные признаки полных Г-орбит.

В главе 4 дано определение нормы синдрома в примитивных БЧХ-кодах с d = 5, описан спектр значений нормы синдрома, доказана инвариантность нормы относительно циклических сдвигов, что позволяет ввести понятие нормы Г-орбиты. Доказано, что нормы синдромов имеют равномерное распределение (в точности n синдромов принимают одно фиксированное значение нормы). Отсюда следует, что Г-орбиты с различными нормами содержат ошибки с различными спектрами синдромов, а следовательно, БЧХ-код может декодировать любой набор Г-орбит ошибок с попарно различными нормами. В принципе, можно подобрать набор Г-орбит, исчерпывающий весь спектр синдромов, и следовательно, декодировать любую ошибку из этого набора.

В главе 5 изложен метод коррекции ошибок на основе норм синдромов, его реализация на ПЗУ, а также на вентильных матрицах. Найдены условия совместной коррекции БЧХ-кодом с d = 5 случайных ошибок веса 1–2 и пакетов ошибок длиной 3–4. Приведены примеры кодов, где эти условия реализуются.

Глава 6 посвящена теории норм синдромов для реверсивных кодов с d = 5 [134, 135].

В главах 7–9 излагается теория норм синдромов для БЧХ-кодов с d = 1, представляющая собой развитие вышеизложенной теории для БЧХ-кодов, со своей спецификой и сложностью [136, 142–145].

Рост количества декодируемых ошибок при увеличении кодового расстояния требует поиска методов сжатия обрабатываемых синдромов при разработке эффективных кодеков для метода норм. С этой целью в главе 10 разрабатывается применение циклотомических подстановок к теории норм синдромов [141–143].

В главе 11 дано определение нормы синдрома, инвариантной относительно циклических сдвигов, для БЧХ-кодов с любым расстоянием, изложены основы общей теории норм синдромов. Доказано, что метод норм справедлив для произвольных примитивных БЧХ-кодов [146–148]. Результаты этой главы допускают и требуют дальнейших исследований.

В главе 12 изложены различные перестановочные подходы к удлиненным и модифицированным реверсивным кодам с d = 6, раскрывающие их более глубокие корректирующие возможности по сравнению с традиционными представлениями. Найден перестановочный способ коррекции модулей ошибок при передаче информации в ASC–II формате. Изложены возможности применения норменного метода для коррекции модулей ошибок модифицированными кодами Рида–Соломона [130–137].

Авторы выражают глубокую признательность В.Ф.Томилину за поддержку в работе над монографией.