1.4.6. Использование теоретико-числовых преобразований

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

Теоретико-числовое преобразование определяется для последовательностей целых чисел как пара преобразований:

имеющих структуру, похожую на структуру ДПФ. Здесь М — целое положительное число; — целое положительное число, взаимно-простое с М и такое, что на него делится число где Р — любой из простых сомножителей а — число такое, что является наименьшим положительным целым числом, для которого справедливо ).

Преобразование (1.53) называется прямым, а -обратным ТЧП (ОТЧП). При вычислении ОТЧП встречаются операции сравнения, выполняемые над отрицательными степенями целого числа. По определению [1.12]

где — целые числа; в том и только в том случае, если

Использование ТЧП для вычисления круговой свертки двух последовательностей целых чисел аналогично ДПФ (см. 1.4.2) и заключается в выполнении следующих действий:

1) вычислении ТЧП последовательности

2) вычислении ТЧП последовательности

3) перемножении полученных ТЧП:

4) вычислении ОТЧП последовательности

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

С точки зрения эффективности вычислений к ТЧП предъявляются следующие требования:

число должно быть представимо в виде произведения большого числа сомножителей, чтобы существовал эффективный алгоритм типа БПФ;

умножение на степени а должно быть простой операцией; так, если а равно некоторой степени числа 2, то умножение сводится к сдвигам;

число М должно иметь двоичное представление с малым количеством разрядов для облегчения операции по и быть достаточно большим, чтобы исключить переполнение.

Наибольшее распространение на практике получили теоретико-числовые преобразования с числами Ферма (ТЧПФ) и Мерсенна (ТЧПМ).

Теоретико-числовое преобразование Ферма [1.6, 1.12] является наиболее перспективным, так как позволяет использовать эффективные алгоритмы типа В качестве модуля М выбирается одно из чисел Ферма:

называется числом Ферма. Первые семь чисел равны:

В табл. 1.4 приведены параметры «скольких возможных реализаций ТЧПФ.

Таблица 1.4 (см. скан)

Пример 1.14. С помощью ТЧПФ вычислить свертку последовательностей: . В качестве модуля выберем число . При Матрица ТЧПФ (1.53) принимает вид

Так как , то матрица

Согласно (1.55)-(1.58) вычисляем:

1) ТЧПФ последовательности

2) ТЧПФ последовательности

4) ОТЧПФ от дает искомую свертку: Так как результаты должны лежать в диапазоне то окончательно . (Сравните с примером 1.13).

Теоретико-числовым преобразованием Мерсенна [1.12] называется пара следующих преобразований:

где — простое положительное число; - простое число (число Мерсенна).

В качестве могут быть выбраны числа 2, 3, 5, 7, 13, 17, 19, 31, 61. С точки зрения обеспечиваемого динамического диапазона наиболее широко используются числа 31 и 61. Преобразование Мерсенна не обладает структурой БПФ и для своей реализации требует операций сдвига и — сложения.

Пример 1.15. С помощью ТЧПМ найдем свертку последовательностей: . Выберем тогда Матрица имеет вид

Так как то матрица

Теперь вычисляем: -

1) ТЧПМ последовательности

2) ТЧПМ последовательности

3) произведение коэффициентов полученных

4) ОТЧПМ последовательности Так как результат должен лежать в диаазоне то искомая свертка будет равна . (Сравните с примером 1.14.)