5.5. Вопросы реализации

На практике обычно используются декодеры кодов БЧХ, работающие во временной области. Общая структура декодера обычно аналогична показанной на рис. 5.4. Однако в зависимости от используемого кода и от требований, предъявляемых к скорости данных, детали реализации отдельных блоков декодера могут оказаться существенно различными. Задача определения схемы декодирования кодов БЧХ в конкретной ситуации оказывается далеко не сголь очевидной, как в других случаях (при поиске в таблице, использовании пороговых декодеров или декодеров Витерби для сверточных кодов).

Декодирование принятого кодового слова кода БЧХ требует выполнения трех последовательных вычислительных процедур, причем все вычисления проводятся в поле Этими процедурами являются вычисление синдрома, решение ключевого уравнения и процедура Ченя (с вычислением значения ошибки для недвоичных кодов). При низких скоростях данных наиболее эффективным является декодер; организованный в виде специализированного процессора, состоящего из следующих блоков:

1) центральный процессор выполняющий операции в поле

2) запоминающие устройства с произвольной выборкой для буферного хранения (на два кодовых слова) и для временного хранения промежуточных результатов;

3) постоянное запоминающее устройство для хранения вычислительных подпрограмм и управления процессом декодирования;

4) интерфейсы с другими частями системы (демодулятором и получателем данных).

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

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

для всех Это значение задает положение одиночной ошибки, а ее значение легко находится по формуле

Таким образом, в практических случаях, когда часто появляются безошибочные слова или слова с одиночной ошибкой, для их декодирования требуется очень мало вычислений. Это позволяет существенно уменьшить среднее число операций. Для использования этого свойства нужен буфер для кодовых слов, поступающих в то время, пока выполняется полное декодирование, включающее алгоритм Берлекэмпа и процедуру Ченя. Требуемый объем буфера зависит от кода, архитектуры декодера, скорости данных и вероятности появления ошибки в канале.

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

Заметим, что специализированные устройства для вычисления синдрома и осуществления процедуры Ченя, показанные на рис. 5.2 и 5.3, представляют собой, по существу, регистры сдвига, дополненные сумматорами и умножителями в поле Аналогичные структуры могут быть использованы и для реализации алгоритма Берлекэмпа при очень больших скоростях данных (около десятков мегабит в секунду). Этот подход будет обсуждаться позднее в данном разделе.

Реализация умножителей в поле весьма существенна при оптимизации процесса декодирования. Умножение можно выполнить несколькими различными способами. Рассмотрим, например, обычное и логарифмическое представления элементов показанные в табл. 5.2. Это поле будет использоваться во всех следующих примерах данной главы. Для умножения можно складывать логарифмы (первый столбец) по модулю 15. Однако представление во втором столбце оказывается более удобным при сложении. Таким образом, для умножения с помощью логарифмов нужно иметь устройство сложения по модулю 15 и две таблицы перехода от обычного представления к логарифмическому и обратно; таблицы легко записать в ПЗУ. Для исключения одного из обращений к таблице можно также использовать логарифмы Зеча (см. гл. 2). Такой подход особенно привлекателен для полей большой характеристики.

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

Производя умножение получаем с в виде многочлена шестой степени с коэффициентами

Можно взять вычет с по модулю получив многочлен степени 3 с коэффициентами

Таким образом, произведение может быть вычислено с помощью двухвходовых логических элементов И и сумматоров по модулю 2.

Для полей с небольшим числом элементов [скажем, для и для меньших полей] более эффективной является реализация умножителя в ПЗУ. Двухвходовый умножитель в поле требует входных и выходных линий. Его можно реализовать с помощью

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

Таким образом, в этом случае можно обойтись без элементов И и использовать только два сумматора по модулю 2.

Умножение можно также осуществлять с помощью метода «сдвига и сложения». В качестве накопителя используется регистр сдвига, аналогичный показанному на рис. 2.6, в котором обратные связи задаются многочленом Два сомножителя содержатся в двух отдельных регистрах. Последовательная проверка символов первого сомножителя производится начиная со старшего разряда, и для каждого символа, равного 1, второй сомножитель складывается с содержимым регистра накопителя, который после этого сдвигается на одну позицию. При каждом сдвиге с помощью обратной связи накопителя осуществляется редукция промежуточного результата по модулю После сдвигов накопитель содержит нужный результат. Ясно, что скорость этого метода меньше, чем непосредственного вычисления произведения, однако при больших (скажем, при он может привести к существенной экономии аппаратных средств.

Умножитель является первым кандидатом для интегрального исполнения. В действительности, цепь, показанная на рис. 5.2, как естественная составная часть входит в декодер кода БЧХ. Если указанное на этом рисунке умножение осуществляется общим -умножителем (для некоторых то интегральная микросхема, реализующая эту функцию, может быть использована в различных местах декодера. Несколько таких микросхем могут использоваться при вычислении синдрома, при выполнении процедуры Ченя и в Такая микросхема может существенно уменьшить сложность реализации высокоскоростных декодеров.

В некоторых случаях вычисление синдрома можно упростить. Предположим, что код БЧХ определен над полем где простое число. Пусть а и лежат в Заметим, что при имеем Аналогично при любом простом Теперь можно записать в виде

Учитывая, что для простого формулу (5.53) можно переписать в виде

Таким образом, не все нужно вычислять непосредственно. Некоторые из них можно получить как степени других В наиболее частом случае равенство (5.54) приобретает вид

Следовательно, в этом случае нужно вычислять лишь для четных

При умеренных скоростях данных алгоритм Берлекэмпа можно реализовать в специализированном процессоре с соответствующими арифметическим устройством в поле и Для управления процессором можно использовать структурную блок-схему, показанную на рис. 5.8, а также ее варианты, предложенные в работах [2, 46].

Предложенная Месси [46] высокопараллельная схема реализации использовалась для достижения очень высоких скоростей данных (40 Мбит/с) [47]. Структура процессора, реализующего алгоритм Берлекэмпа, показана на рис. 5.9. Многочлены хранятся в. быстрых регистрах сдвига Используемая для управления схема показана на рис. 5.10. Наиболее важное отличие этой схемы от предыдущей состоит в методе определения того, при каких условиях длина регистра

Рис. 5.9. Структурная схема параллельного процессора алгоритма Берлекэмпа

Рис. 5.10. Блок-схема реализации алгоритма Берлекэмпа процессором, схема которого приведена на рис. 5.9

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