сигнала. Такое упорядочение называется перестановкой адресов. Поля Галуа, в которых преобразование Фурье вычисляется наиболее просто, имеют вид GF (2" + 1), где число 2*" + 1 является простым. Известно, что если т не является степенью двойки, то 2" + 1 не является простым числом. Обратное утверждение Истинный вхойной файл

15 точек

21 точка

ПереинВексация Кули-Тьюки

15-точечный вхой гЬточечный вхой

ПереинВексация Гдйа-Томаса

15-точечный вхой г1-точечный вхой

15-точечный выхой

Рис. 11.4. Примеры переиндексации.

V„-r+r = S 2-- a" I 2"Ч-+п-/"

•- - {"=0

неверно, так как известно, что число Ч? + 1 является составным. Но для /п = 2, 4, 8 и 16 числа 2" + 1 = 5, 17, 257 и 65 537 являются простыми и известны под названием простых чисел Ферма. В поле Галуа GF (<?), где q - простое число Ферма, все делители числа q - I, включая и само это число, являются степенью двойки. Преобразование Фурье

Vj = о}Щ

существует для всех п, делящих 2", и всех элементов а, порядок которых равен п. Таким образом, в поле GF(2"-f 1) существуют преобразования Фурье длин, равных 2", 2 2; 2, 2. Построенный в таком поле систематический код Рида-Соломона может быть превращен в двоичный код, исправляющий пакеты ошибок. Этот код можно использовать для систематического кодирования г-битовых байтов; одно из 2 значений запрещается использовать в качестве информационных символов. Проверочные символы принимают 2 1 значений, так что для их двоичного представления требуется г + 1 битов.

Так как в поле GF (2" + 1) порядок элемента 2 равен 32, то преобразование Фурье длины не более 32 является чрезвычайно простым. Чтобы показать это, заметим, что в поле GF(2"+ 1) справедливо равенство 2"+ 1 =0, так что 2" = -1 и 22 = 1. Преобразование Фурье имеет вид

Vj = % 2%i,

так что умножение происходит только на степени двойки и операция умножения по существу представляет собой циклический сдвиг в двоичной арифметической системе. Такое преобразование Фурье очень легко вычисляется с помощью двоичного БПФ-алгоритма Кули-Тьюки, но длина преобразования, равная 32, слишком мала, чтобы иметь много приложений. Более длинные преобразования Фурье должны включать нетривиальные1умно-жения. Однако использование 32-ичного БПФ-алгоритма Кули- Тьюки позволяет уменьшить число таких умножений. Например, рассмотрим 1024-точечное преобразование в поле GF (2" + I):

1023 t=0

где а - элемент порядка 1024. БПФ-алгоритм Кули-Тьюки приводит эту формулу к виду

Внутренняя сумма при каждом i является 32-точечным преобразованием Фурье, а внешняя сумма является 32-точечным преобразованием Фурье при каждом i". Только со степенью элемента а связаны нетривиальные умножения, но их число равно 1024. В обш,ем случае для вычисления преобразования Фурье в поле GF (2" -f 1) требуется около п (floggg nl - 1) умножений в этом поле, (1/2) п logg я сложений и (1/2) п logon сдвигов.

Другим алгоритмом БПФ является алгоритм Гуда-Томаса для взаимно простых делителей. По сравнению с алгоритмом Кули-Тьюки он немного сложнее в принципе, но и немного проще в вычислительном отношении. В алгоритме Гуда-Томаса форма переиндексации линейного массива в двумерную (п X п")-таб-лицу, позволяющая вычислять одномерное преобразование Фурье с помощью двумерного преобразования Фурье, отличается от формы переиндексации в алгоритме Кули-Тьюки. Алгоритм Гуда-Томаса по идее существенно отличается от алгоритма Кули-Тьюки. В нем п и п" предполагаются взаимно простыми, и в основе отображения лежит китайская теорема об остатках. Способ упорядочения данных иллюстрируется рис. 11.4. Упорядочение начинается с левого верхнего угла таблицы, и компоненты записываются вдоль продолжения диагонали. Так как число строк и число столбцов взаимно просты, то продолженная диагональ пройдет через все элементы таблицы. После выполнения двумерного преобразования Фурье компоненты спектра выписываются в двумерной таблице в другом порядке.

БПФ-алгоритм Гуда-Томаса основан на китайской теореме об остатках для целых чисел. Входные индексы определяются своими вычетами по правилу

i = i (mod п), i" = i (mod n"),

задающему отображение входного индекса i в пару индексов (Г, i"), лежащих на продолженной диагонали двумерной таблицы. Согласно китайской теореме об остатках, существуют целые числа N и N", такие, что

Nn + /V"n" = 1.

Это позволяет следующим образом однозначно вычислить исходный индекс i по паре (i, i"):

i = iN"n" + i"Nn (mod n).

Выходные индексы упорядочиваются несколько иным способом. Определим

/ = N"j (mod /г), /" = Nj (mod /г").