Наиболее простым подходом к реализации адаптивной системы кодирования является предварительная подготовка набора кодеков с динамическим переключением между ними. Такой метод не всегда является оптимальным, так как при переходе с одного кода на другой изменять зачастую необходимо лишь некоторые параметры кода. Гораздо более эффективным методом является динамическая перестройка только тех параметров кода, которые отвечают за его избыточность. Способы поиска и оптимизации данных алгоритмов различны для разных видов кодов.
Код Рида-Соломона как внешняя ступень кодирования
Коды Рида-Соломона были открыты в 1960 году американскими учеными Ридом и Соломоном как частный случай кодов Боуза-Чоудхури-Хоквингема. Прошло более полувека, а данные коды до сих пор остаются одним из наиболее востребованных видов помехоустойчивого кодирования. Их популярность связана с тем, что кодовые слова в данном виде кодирования разнесены максимально далеко друг от друга, что положительно сказывается на их помехозащищенности. Коды Рида-Соломона( далее РС) хорошо справляются с исправлением пакетов ошибок, возникающих при воздействии на канал связи импульсной помехи, поэтому эти коды как нельзя лучше подходят в качестве внешней ступени кодирования каскадного кода. Однако аппаратная реализация адаптивных алгоритмов декодирования кодов РС – сложная и ресурсоемкая процедура, и оптимизация этих алгоритмов является актуальной задачей.
Способы декодирования РС-кодов достаточно хорошо разработаны в теоретическом и реализационном плане, тем не менее представляет собой довольно сложную задачу. Типовая схема декодирования, получившая название авторегрессионного спектрального метода декодирования, состоит из следующих шагов:
• вычисления синдрома ошибки( синдромный декодер);
• построения полинома локаторов ошибок( стираний), осуществляемого либо посредством высокоэффективного, но сложно реализуемого алгоритма Берлекэмпа-Месси, либо посредством простого, но медленного Евклидового алгоритма;
• нахождения корней данного полинома, обычно решающегося полным перебором всех возможных значений( алгоритм Ченя);
• определения характера ошибки, сводящегося к построению битовой маски, вычисляемой на основе обращения алгоритма Форни или любого другого алгоритма обращения матрицы;
• исправления ошибочных символов путем наложения битовой маски на информационное слово и последовательного инвертирования всех искаженных бит с помощью операции XOR.
Схема быстрого декодирования кодов РС приведена на рисунке 1.
Реализация данного алгоритма на ПЛИС сводится, как правило, к разработке трех основных АЛУ:
1. SC-block( Syndrome Computation block). Блок расчета синдромного многочлена. Выполняет вычисления согласно формуле( 1).
где R( z) – полином принятых кодовых слов, α – примитивный элемент поля Галуа.
2. KES-block( Key-Equation block). Блок, решающий ключевое уравнение:
где Ʌ( z) – полином локаторов ошибки, t – корректирующая способность кода.
3. CSEE-block( Chien Search and Error Evaluator block). Блок, выполняющий процедуру Ченя по поиску корней полинома локаторов ошибок путем последовательного перебора всех возможных значений и рассчитывающий значение ошибки согласно алгоритму Форни:
где Y – значение ошибки, Ʌ’( z) – производная от полинома локаторов ошибки, j – номер позиции в принятом векторе R, на которой произошла ошибка.
Наиболее сложным в реализации алгоритмом из представленных на рисунке 1 является алгоритм поиска полинома локаторов ошибок. Он также является наиболее ресурсоемким, поэтому создание оптимального декодера кода РС будет осуществляться за счет оптимизации этого алгоритма.
Наиболее эффективным с точки зрения скорости обработки данных алгоритмом поиска полинома локаторов ошибок считается алгоритм Берлекэмпа-Месси( далее БМА).
Нахождение решения ключевого уравнения, имеющего минимальную степень, эквивалентно построению регистра сдвига минимальной длины с обратными связями, отображающими Ʌ( x), порождающим первые 2t членов S( x). Основное содержание данного алгоритма формулируется следующим образом. Вначале находят самый короткий регистр сдвига, генерирующий S 1. Далее проверяют, порождает ли этот регистр также S 2. Если порождает, то данный регистр по-прежнему остается наилучшим решением, и нужно проверить, порождает ли он следующие символы
ПЛИС – программируемая логическая интегральная схема. АЛУ – арифметико-логическое устройство.
( 1)
( 2)
( 3)
55