4.6 Быстрое преобразование Фурье длины 17

17-точечное ДПФ с ядром задается равенством

(17)

В =.

Для уменьшения числа умножений, как и для 5-точечного ДПФ, воспользуемся переходом к циклической свертке с последующей редукцией по следствию из утверждения 4.5.1. Сначала воспользуемся алгоритмом Рейдера для перехода к циркулянту. Так как 5 является примитивным элементом поля GF(17) , то имеем:

i	1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
N=5	5 8 6 13 14 2 10 16 12 9 11 4 3 15 7 1

Таким образом, без учета в нумерации одиночного окаймления, к циклической свертке приводит, например, такая перестановка строки столбцов матрицы Фурье в (17) (соответствующих координат преобразуемого вектора а и спектра А), которая дается второй строкой этой таблицы: единичное окаймление остается на месте, а первая строка циркулянта соответственно имеет вид:

получаем,

16

, (18)

где , – вектор, полученный из спектра А указанной перестановкой координат, а - вектор столбец, определяемый вторым равенством в (18).

Согласно утверждению 4.5.2, задача вычисления (18) эквивалентна задаче вычисления циклической свертки

(19)

Вычислять свертку (19) будем следующим образом. Пусть (так что ) и пусть

Так что

,

,

Сначала будем полагать переменную х параметром и найдем циклическую свертку по модулю . Обозначая , согласно равенствам (15) имеем:

₍₂₀₎

В поле для элемента выполняется тождества:

; ;

(21)

Эти тождества позволяют упростить вычисления величин, входящих в (20). Например,

Aлгоритм вычисления R(x)=r(x) для произвольного многочлена содержит 4 умножения и 12 сложений. А именно, воспользуемся равенством (12) и учтем, что в поле согласно второму из тождеств в (20) выполняется равенство ,char=2. Имеем:

При табличной реализации умножения необходимо иметь только один массив длины 256 произведений всех элементов поля на элемент . Алгоритм:

(22)

Для остальных 5 умножений вида R(x)=r(x)b(x) число умножений не уменьшается, равно 9, и алгоритм, согласно (12), можно записать в виде:

Алгоритм: , , , , , ,

, , , , , , (23), , , , , , , , .

Так как суммы коэффициентов , естественно, вычисляются заранее и вводятся в алгоритм фиксированными константами, то всего имеем 9 умножений и 17 сложений. Для входящих в (20) коэффициентов, величины

соответственно равны:

Полное число сложений и умножений для этой реализации равно соответственно 129 и 61. Для полного БПФ по длине 255 имеем 1935 сложений и 1255 умножений.

4.7. БПФ-укороченные коды Рида-Соломона

В 4.2 было дано спектральное описание циклического кода. Согласно этому описанию, кодовое слово находится спектре кодового слова информационного вектора, содержащего подряд идущих нулей. При таком подходе код способен исправлять не более ошибок. Были построены эффективные алгоритмы вычисления ДПФ длин 3, 5, 17 над полем и быстрый алгоритм вычисления ДПФ длины 255.

На практике, однако, не всегда возможно (или целесообразно) применять кодовые слова длины 255 над . Одним из путей уменьшения требуемых вычислительных ресурсов и снижения времени обработки данных при кодировании и декодировании применение так укороченных РС-кодов.

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

Алгоритмы кодирования при прямом способе укорочения РС-кода совпадают с алгоритмами для полного кода. Поэтому временные характеристики несистематического кодера, основанного на спектральной технологии кодирования остаются такими же, как и для полного кода. Объясняется это тем, что при несистематическом кодировании, когда к информационному вектору применяется быстрое преобразование Фурье (БПФ), весь массив данных (все 255 координат) обрабатываются одновременно и вычисления проводятся сразу для нескольких групп точек. При этом обнуляемые позиции кодового слова равномерно распределяются по всему трехмерному кубу, реализующему БПФ, и автоматически включаются в вычисления на полной длине кодового слова. Поэтому целесообразно сделать укорочение кодового слова таким образом, чтобы сократить вычисления в алгоритмах БПФ.