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

При табличной реализации умножения необходимо иметь только один массив длины 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 над . Одним из путей уменьшения требуемых вычислительных ресурсов и снижения времени обработки данных при кодировании и декодировании применение так укороченных РС-кодов.

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