Устройства обработки БЧХ-кодов на основе норм синдромов

_Доклады БГУИР_

2003 январь-март Том 1, № 1

ИНФОРМАТИКА

УДК 621.391

УСТРОЙСТВА ОБРАБОТКИ БЧХ-КОДОВ НА ОСНОВЕ НОРМ СИНДРОМОВ

В. А. ЛИПНИЦКИЙ

Белорусский государственный университет информатики и радиоэлектроники П. Бровки, 6, Минск, 220013, Беларусь

Поступила в редакцию 9 января 2003

Теория норм синдромов предоставляет перестановочные алгоритмы коррекции ошибок, позволяющие на порядок снизить "проблему селектора". Их реализация возможна как с помощью ПЗУ, так и ПЛИС. Первая обладает хорошей аппаратурной экономичностью, вторая -высоким быстродействием.

Ключевые слова: помехоустойчивость, БЧХ-коды, синдром ошибок, норма синдрома, декодер, перестановочное декодирование.

Введение

Одной из прикладных задач общей теории телекоммуникаций является повышение помехоустойчивости цифровой передачи, хранения, обработки и коммутации сообщений [1, 2]. При широком многообразии помехоустойчивых кодов на практике реализован лишь небольшой спектр кодов и методов их декодирования. Это декодеры, базирующиеся на методе максимального правдоподобия, используемые, как правило, для обработки низкоскоростных кодов [3], мажоритарные декодеры, синдромные декодеры для обработки высокоскоростных кодов. Основное препятствие здесь — "проблема селектора" — быстрый рост количества селектируемых векторов с увеличением длины кода или кодового расстояния. Общепризнано считать эффективными перестановочные декодеры, базирующиеся на автоморфизмах кодов [1]. Однако до последнего времени они не нашли практической реализации ввиду отсутствия теоретической базы и, как следствие, сложности алгоритмов коррекции ошибок. Определенным шагом в развитии перестановочных методов обработки кодов является создание теории норм синдромов [4]. Суть теории состоит в следующем. Под действием группы Г векторы-ошибки разбиваются на непересекающиеся классы — Г-орбиты. Каждая Г-орбита имеет четко очерченный спектр векторов и синдромов — зная вектор (синдром вектора) одной Г-орбиты, можно однозначно восстановить все остальные векторы (синдромы ее векторов). Через компоненты синдрома вычисляется норма синдрома [4]. Норма синдрома не зависит от циклических сдвигов, является однозначной характеристикой каждой Г-орбиты; это и есть норма Г-орбиты. Г-орбиты с различными нормами имеют непересекающиеся спектры синдромов. Отсюда следует, что код может корректировать любой набор К Г-орбит векторов-ошибок с попарно различными нормами. Практически в любом коде можно построить совокупность Г-орбит К, содержащий не только произвольные случайные ошибки, допустимые кодовым расстоянием, но и ряд зависимых ошибок, вплоть до полного исчерпания синдромных возможностей кода.

Норменный метод декодирования. Изложенная теория предоставляет следующий метод декодирования ошибок: вычисляется синдром ошибок S(X) = $(~ё) принятого сообщения

х = е + у, где у — истинное кодовое слово, е — вектор ошибок; далее вычисляется норма синдрома Ы(8(х)) = N . Норма указывает Г орбиту I, которой принадлежит вектор е . Если в Г-орбите I зафиксировать один элемент в качестве образующего, то, сравнив синдромы 8(ё) и 3(в}.), можно определить величину циклического сдвига, переводящего е^ в е . Тем самым вектор ошибок е может быть однозначно определен. Основные этапы этого алгоритма для БЧХ-кода с минимальным расстоянием d=5 исправляющего ошибки кратности 1=2, состоят в следующем.

1. Вычисляется синдром Я = (сс'т ,а1т ) (БВС).

2. Находятся текущие значения степеней ¡т, ]т элементов поля Галуа (ПЗУ1 и ПЗУ2).

3. Вычисляется показатель нормы синдрома deg N=( ]т —3 ¡т )(mod п) (применяется сумматор по модулю п).

4. По показателю deg N находится показатель /0 первой компоненты синдрома образующего вектора ошибок (с применением ПЗУЗ).

5. Вычисляется Ь1 = (гт —10 )(mod п) номер первого ошибочного разряда (с помощью сумматора по модулю п).

6. Вычисляется номер Ь2 второго ошибочного разряда — с помощью блока вычисления наблюдаемого вектора ошибок (БВНВО), состоящего из ПЗУ4 и сумматора по модулю п, вычисляется диаметр ошибки и, следовательно, положение второй ошибочной позиции.

7. Путем раздельной дешифрации Ь1 и Ь2 (с помощью дешифраторов Дш1 и Дш2) находятся векторы ошибок е1 и е2 веса 1.

8. Находится суммарный вектор е = е1 + е2 в блоке элементов ИЛИ (на рис. 1 — блок 1).

9. Осуществляется коррекция принятого сигнала в блоке инвертирования (БИ).

Декодер, реализующий данный алгоритм , представлен на рис. 1.

Рис. 1. Структурная схема декодера, использующего ПЗУ и сумматоры по модулю п

В сумме аппаратурная сложность данного декодера составляет (^ N + 3n)\og2n + 3п

элементов И, ИЛИ, ячеек памяти. Например, для длины кода п=127, 1=2 аппаратурная сложность составляет 3115 элементов. Такая сложность вполне приемлема для современной микроэлектронной базы. Однако декодер отличается неоднородностью входящих блоков; это приводит к большим затратам площади кристаллов, реализующим декодер. Сложность предложенного декодера почти в три раза меньше числа селектируемых комбинаций: C121 + C227 =8128 по таблице смежных классов, на реализацию которой потребуется ПЗУ емкостью 221о&п • 221°ьп (при п=127 емкость его примерно равна 64 Кбит) при извлечении из него двух \0g2n разрядных кодов адресов ошибок. Если декодер реализовать на основе классического метода синдромов с использованием ПЗУ емкостью, равной суммарному числу синдромов, умноженному на длину кода, то для данного примера емкость ПЗУ составит 8128-127«Мбит.

Анализ показывает, что с увеличением кратности ^ корректируемых ошибок увеличивается число ПЗУ для преобразования элементов поля в их показатели, количество сумматоров по модулю п для нахождения показателей компонент норм синдромов deg М-, ПЗУ для хранения адресов ошибок образующего вектора. Также требуется блок вычисления текущего значения нормы

синдрома Мт = (М1,М2,...,Мг) (при о^>7 норма синдрома становится вектором [4]. Ясно, что данный блок может быть реализован на элементах И, максимальное число входов у которых равно а их суммарное число равно количеству норм синдромов, необходимых для декодирования ¿-кратных ошибок.

Анализ рассматриваемого метода декодирования и его реализаций показывает, что операции при вычислениях совершаются с двоичными числами с промежуточными переходами в унитарные коды (в дешифраторах и ПЗУ) и обратно в двоичные. Это приводит к большим задержкам сигналов при преобразованиях, а также к высокой сложности при реализации сумматоров по модулю п при их параллельной схеме исполнения, а при последовательной реализации — к низкому быстродействию.

Если реализовать алгоритм декодирования на ПЛИС, то в этом случае происходит преобразование синдрома (двоичного кода) в унитарный код с помощью дешифратора, а далее вычисляется норма N и вектор ошибок ё в унитарных кодах.

На рис. 2 представлена структурная схема декодера на ПЛМ, реализующая метод декодирования в унитарном коде для БЧХ-кода длиной п=7. Каждая точка на пересечении вертикальных и горизонтальных шин логических матриц ЛМ1 и ЛМ2 обозначает элемент 2И. Схема построена на основе таблицы, где представлены все векторы-ошибки веса 1-2, собранные в Г-орбиты

11-14, синдромы ошибок в названном коде и показатели норм Г-орбит.

Перечень векторов Г - орбит ошибок веса 1, 2 и их синдромов в БЧХ- коде длиной 7

Г-орбита 11 12 13 14

ё и 8

с

с2

С

с4

с3

с6

degМ( I) 0 5 3 6

Рис. 2. Структурная схема декодера, реализующего метод коррекции в унитарных кодах

Двоичные коды синдрома с выходов БВС поступают на входы дешифраторов Дш 1 и Дш2, где преобразуются в унитарные коды. Эти коды поступают на первую логическую матрицу БВНС-ЛМ1, на выходах которой устанавливаются в унитарном коде единичные сигналы в зависимости от вычисленной нормы N; на выходах второй логической матрицы (БВТВО-ЛМ2) — текущие векторы ошибок Таким образом, по сути дела логическая матрица ЛМ2 заменяет функции, БВОВО, БВЦС, БВТВО декодера (рис. 2) и производит циклический сдвиг образующего вектора ошибок e. Прообразом здесь является работа [5].

Результаты и обсуждения

Основное преимущество норменного декодера на ПЛИС — высокое быстродействие — обеспечивается как за счет исключения отдельных блоков, так и благодаря регулярной и однородной структуре ЛМ. Так, например, для декодера на рис. 2 сигнал задерживается лишь в трех последовательно соединенных высокоскоростных блоках (дешифраторе и двух ЛМ. Известно, что сумматоры по mod n являются достаточно медленными элементами. Сложность реализации рассматриваемого декодера определяется емкостью двух ЛМ, одна из которых наполовину заполнена ( 0,5  n2 ). Это приводит к более высокой сложности устройства. В частности, при длине кода n=127 сложность примерно равна 22 Кбит. Это в семь раз выше сложности декодера на рис. 1, однако примерно в 4 раза соответственно ниже сложности декодера, реализующего декодирование по таблице смежных классов.

Заключение

Теория норм синдромов предоставляет перестановочные алгоритмы коррекции ошибок, позволяющие на порядок снизить "проблему селектора". Их реализация возможна как с помощью ПЗУ, так и ПЛИС. Первая обладает хорошей аппаратурной экономичностью, вторая - высоким быстродействием.

DEVICES FOR BCH CODES DECODING USING SYNDROME NORMS

V.A. LIPNITSKY Abstract

The syndrom norm theory provides permutation algorithms for error correcting thus essentially decreasing a "selector problem". They can be implemented by using RAM and PLIS. The first one has accessible hardware economy, the second one — high speed performance.

Литература

1. Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А. Теория кодов, исправляющих ошибки. М., 1979.

2. Варламова О. Помехоустойчивые кодеки — будущее цифровой телефонии. Интернет, 2002.

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

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

5. Конопелько В.К. Устройство декодирования для коррекции двойных ошибок. А.с. № 1833968. 1993. Бюл. изобрет. № 30.