Конопелько В.К., Липницкий В.А. Теория норм синдромов и перестановочное декодирование помехоустойчивых кодов Изд. 3

Содержание

Введение

Теория и практика помехоустойчивых кодов имеет полувековую историю. Ее общепризнанным родоначальником является К.Шеннон. В 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].

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