Цифровая обработка сигналов в радиоэлектронных системах (стр. 14 )

Обычно определение ТЧП начинается с выбора модуля M, а затем исследуются возможные значения N. В качестве модуля чаще всего используют числа Мерсенна и Ферма. Соответственно различают ТЧП Мерсенна (ТЧПМ) и ТЧП ферма (ТЧПФ).

ТЧП – Мерсена

Числа Мерсенна определяются выражением, где - простое число. ТЧПМ существует, если N делит все числа вида (qi - 1), где qi- составные множители из разложения числа Мерсенна

.

Для простых чисел Мерсенна длину преобразуемой последовательности получают из условия, что число N делит число т. е.

Из теории чисел известно, что если , то делится на , и Кроме того число 2 является делителем числа . Следовательно, можно определить -точечные ТЧПМ.

Рассмотрим вопрос определения . Если простое, то корнем порядка является 2 так как . Если составное число то, 2 тоже является корнем, но необходимо чтобы имело обратное число, а это условие выполняется в том случае если

.

Таким образом, можно определить прямое и обратное точечное преобразование Мерсена.

и

, (95)

где .

Для 2p точечного преобразования корнем является так как и степени корня представляют собой разные числа отличные от нуля.

Для составного Mp необходимо выполнить проверку на взаимную простоту чисел:

для .

Для то получаем:

.

Следовательно, можно определить 2p-точечное ТЧПМ

,

, (96)

где .

Для преобразования осуществляются без операций умножения. Возможно ТЧПМ другого размера с , но в этом случае появляются операция умножения.

Пример. Пусть ,

,

Матрица ТЧП строится так же как матрица преобразований Фурье с одним отличием: место поворачивающего множителя занимает число

Определим

,

используя алгоритм Евклида:

, .

Обратное ТЧПМ имеет вид

.

Недостаток преобразования Мерсенна состоит в том, что для него отсутствуют алгоритмы быстрого вычисления, так как числа p и 2p не разлагаются на большое количество сомножителей. Этого недостатка лишены преобразования Ферма (ТЧПФ).

ТЧП Ферма

ТЧПФ в качестве корня использует двойки и степени двойки. Это позволяет получить удобную арифметику, N кратную степени двойки.

Числа Ферма имеют вид , где . Например .Первые пять чисел – это простые числа остальные числа составные., где - простое число. Если - простое число, то размер выборки определяется из условия: .

Если - составное число, то простой множитель имеет вид.

Следовательно всегда можно найти такое -точечное преобразование по модулю, для которого выполняется условие:

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

ТЧПФ имеет вид

mod

, (97)