1. Наука
  2. Видання
  3. Системи обробки інформації
  4. 2(76)'2009
  5. Алгоритм швидкого перетворення Фур'є Гуда-Томаса в кінцевих полях для усіченого вектора

Алгоритм швидкого перетворення Фур'є Гуда-Томаса в кінцевих полях для усіченого вектора

С.В. Дуденко, С.В. Алексєєв, В.В. Добровольський
Анотації на мовах:

Для класичного перетворення Фурье в кінцевих полях існують швидкі алгоритми, серед яких виділяють алгоритми Кулі-Тьюки і Гуда-Томаса, які дозволяють значно зменшити обчислювальну складність за рахунок перєіндексації точок векторів. Показано, що для усіченого перетворення Фурье в залишкових класах можна застосувати тільки алгоритм Кулі-Тьюки, оскільки властивість парності довжин векторів для усіченого перетворення Фурье і вимога взаємної простоти множників Гуда-Томаса не дозволяють використовувати його алгоритмічне рішення.
Ключові слова: перетворення Фурье, швидке перетворення Фурье, алгоритм