Fermat_Transform.HTM
Компьютеры и сигналы     ▲ Выше     Операции ЦОС в целых числах

Преобразование Ферма


 
     Полезность инженерного метода становится бесспорной только тогда, когда этот метод признаётся широким кругом тех, на кого он рассчитан и кто рассматривает его с позиций своих нужд. Сложный или не знакомый для возможных его пользователей метод может не получить должной оценки — принесёт ли он большую пользу или останется подстрочным примечанием в истории техники?
     Сейчас предложено несколько алгоритмов, предназначенных для использования в области Цифровой Обработки Сигналов, в которых можно разобраться и написать по ним программы, только располагая некоторым знанием элементарной Теории Чисел. Пока инженеры и программисты в массе не знакомы с Теорией Чисел, вопрос о полезности этих алгоритмов в конечном счёте остаётся открытым.
Дж.Х.Макклеллан,
Ч.М.Рэйдер
из Предисловия в книге , 1983.

Арифметики в конечных числовых полях
  Делимость целых чисел
  Сравнения и ВЫЧЕТы
  Группы, кольца, поля чисел
  Изоморфизм
  Числа Ферма
  Примитивные КОРНИ
  (A-1)-арифметика
Фурье-подобные преобразования в конечных полях
  Таблица Фурье-подобных преобразований
  Классификация Фурье-подобных преобразований
  Фурье-подобные преобразования над полем C
  Фурье-подобные преобразования над полем GF(M)
  Свёртка и Фурье-подобные преобразования
    Свертка двух сигналов
    История быстрых алгоритмов ЦОС
    Связь между ТЧП, ПП и ДПФ
      ПП и вычисление свёрток
      ТЧП и вычисление свёрток
      Вычисление комплексных свёрток с помощью ЧП Ферма
      Резюме сравнения ТЧП, ПП и ДПФ
Числовое преобразование Ферма
  Деление 1/T mod Fn и условия существования ЧП Ферма
    Определение ЧП Ферма
    Условия существования ЧП Ферма
    Деление 1/T mod Fn
  Переборной алгоритм вычисления 1/T mod Fn
  Формулы для вычисления КОРНЕЙ и их порядков
  Вычисление ЧП Ферма без умножений
  Примеры КОРНЕЙ для простых модулей Fn
  Примеры КОРНЕЙ для составных модулей Fn
  Одномерное ЧП Ферма
    Матричная форма ЧП Ферма по основанию 2
      Введение в матричные модели БА ЧП Ферма
      Матричные модели БА ЧП Ферма по основанию 2
      Примеры матричных моделей БА ЧП Ферма по основанию 2
    Матричная форма ЧП Ферма по смешанному основанию
      Матричная модель БА ЧП Ферма для двух сомножителей
      Матричные модели БА ЧП Ферма по основанию T
      Матричные модели БА ЧП Ферма по основанию 4
      Матричные модели БА ЧП Ферма по смешанному основанию
      Разложение N — длины ЧП Ферма на два сомножителя
  Двумерное ЧП Ферма (ЧПФ-2)
    Определение двумерного ЧП Ферма
    Модели вычисления ЧПФ-2
      Построчно-столбцовый алгоритм ЧПФ-m
      Вычисление ЧПФ-m по векторному основанию
      Вычисление 2D-спектра по ТА Григоряна
        Тензорное представление 2D-спектра при N — простом
        Способ вычисления 2D-спектра по ТА при N — простом
        Тензорное представление 2D-спектра при N=2v
        Способ вычисления 2D-спектра по ТА при N=2v
        Оценка вычислительной сложности ТА при N=2v
      Вычисление ЧПФ-2 по ПП Нуссбаумера
    Изоморфизм ДП Виленкина (ДП-В) и ДПФ-m
    Проблема оптимального БА для ДП Фурье
    Критика ЧПФ и ограничения его применения в ЦОС
    Ферма снова побеждает
      Модель вычисления одномерного ЧПФ через многомерное
      Модель вычисления ЧПФ-2 через одномерное ЧПФ и свёртки
      Модель вычисления одномерной ЦС через многомерную
    Резюме: сложность — плата за оптимальность
Теоретико-числовое преобразование Гаусса
  Кольцо ЦКЧ Гаусса
  ρ-изоморфизм Гаусса
  Пример ПСНВ+ и ПСАНВ± по модулю ЦКЧ Гаусса μ=(5+j2)
  Пример ПСНВ+ и ПСАНВ± по модулю ЦКЧ Гаусса μ=(2+j5)
  Сравнение ПСНВ+ и ПСАНВ± по модулю μ=(5+j2) и μ=(2+j5)
  Примитивные КОРНИ и модулярное ТЧП Гаусса
  Выбор параметров кольца Гаусса
  Примеры ТЧП Гаусса
  Критика ТЧП Гаусса и ограничения его применения в ЦОС
  Это не конец
    Волшебник Ферма
    Ферма опять побеждает
  ДП Фурье квантованных сигналов в кольце ЦКЧ Гаусса


Компьютеры и сигналы    ▲ В начало    Операции ЦОС в целых числах






Последнее обновление 16.09.2013

© 2005 г., Александр Тимофеев, г.Харьков, Украина, eMail: atimopheyev@yahoo.com