Scientific journal
Fundamental research
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,674

DEVELOPMENT OF FAST ALGORITHM FOR COMPUTING NUMBER-THEORETIC TRANSFORMS OF SIGNALS

Yurdanov D.V. 1 Kalmykov M.I. 1 Gostev D.V. 1 Kalmykov I.A. 1
1 Federal State Autonomous Educational Institution Higher Professional Education «North-Caucasian Federal University»
The aim of the research is to increase the speed of execution of orthogonal transformation of signals when using number-theoretic transforms in finite fields. The use of fast algorithms of discrete Fourier transform allows to increase the speed of digital signal processing (DSP) due to parallel computing. However, the fast Fourier transform (FFT) has a number of drawbacks. First, is the presence of two computational paths for processing the real and imaginary parts of the signal. Secondly, the use of trigonometric functions as twiddle factors, which leads to rounding errors. To solve this problem through the use of number-theoretic transform of the signal. However, when carrying out orthogonal transformation of signals in finite fields, Galois does not use fast algorithms, fast algorithms similar to Fourier transforms. Therefore, the development of fast algorithm for computing number-theoretic transform is an urgent task.
digital signal processing
orthogonal transformation of signals
fast Fourier transform
fast algorithms
number-theoretic transform

Цифровая обработка сигналов (ЦОС) относится к числу наиболее динамически развивающихся областей инженерной деятельности [2, 8, 10]. Медицина, системы сотовой связи, телекоммуникации, Internet-технологии, обработка звука и изображений, навигация – вот далеко не полный перечень приложений, в которых активно используются методы ЦОС. В настоящее время широкое применение нашли специализированные процессоры (СП) цифровой обработки сигналов, которые базируются на реализации ортогональных преобразований сигналов. Такие ортогональные преобразования сигналов, как правило, определены над полем комплексных чисел. Среди таких преобразований сигналов можно выделить быстрые преобразования Фурье (БПФ) [1, 4, 9]. Однако они имеют ряд недостатков, которые связаны с наличием двух вычислительных трактов для обработки действительной и мнимой части сигнала, а также с ошибками округления, вызванных использованием в качестве поворачивающих коэффициентов функций синусов и косинусов. Поэтому разработка новых алгоритмов ортогональных преобразований сигналов с использованием целочисленной арифметики, позволяющих устранить отмеченные недостатки, является актуальной задачей.

Цель исследования

Основным недостатком ортогональных преобразований сигналов на основе БПФ является использование в качестве ортогональных базисов тригонометрических функций. Решить данную проблему можно за счет перехода к целочисленному вычислению. В работах [1, 3, 5, 7] предлагается выполнять цифровую обработку сигнала с использованием теоретико-числовых преобразований (ТЧП). Однако такие целочисленные преобразования сигналов имеют малую производительность, так как они подобны дискретному преобразованию Фурье (ДПФ). Поэтому целью работы является повышение скорости выполнения ортогональных преобразований сигналов за счет разработки быстрого алгоритма ТЧП.

Материалы и методы исследования

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

Для многих практических приложений ЦОС используется быстрое преобразование Фурье. При реализации БПФ возможны несколько вариантов организации вычислений в зависимости от способа деления последовательности yrd01.wmf длины N на части. В случае четного N возможно использование варианта «прореживания по времени», который определяется как сумма двух yrd02.wmf точечных дискретных преобразований Фурье

yrd03.wmf, (1)

где yrd04.wmf, yrd05.wmf, yrd06.wmf yrd07.wmf – подпоследовательности длины yrd08.wmf с четными и нечетными номерами соответственно. Из равенства (1) видно, что реализация БПФ характеризуется наличием двух вычислительных трактов, влияющих на схемные затраты и надежность спецпроцессора ЦОС. Кроме того, БПФ в качестве поворачивающих коэффициентов использует иррациональные числа, что снижает точность вычислений. Устранить данные недостатки возможно за счет использования ТЧП, определенного в алгебраической системе, обладающей свойствами кольца или поля [2, 6, 10].

Пусть GF(M) – конечное поле Галуа, GN – циклическая группа порядка N, yrd09.wmf – примитивный корень порядка N (εN элемент поля GF(M), удовлетворяющий условию yrd10.wmf и yrd11.wmf для любого натурального L < N). Тогда ТЧП последовательности yrd12.wmf, где yrd13.wmf yrd14.wmf имеет вид

yrd15.wmf, (2)

Обратное теоретико-числовое преобразование имеет вид

yrd16.wmf. (3)

Очевидно, что ТЧП по своей структуре наилучшим образом реализуются с использованием цифровой элементной базы. Например, если взять εN в виде степени двойки, то умножение в (2) и (3) на степени εN при вычислении ТЧП заменяется сдвигами кодовых слов и приведением сдвинутых кодовых слов по модулю числа М [2].

В работе [10] показана возможность повышения скорости выполнения ТЧП за счет использования разработанного алгоритма применения модулярных кодов. Если в качестве числа M использовать составные числа Мерсена, то выражения (2) и (3) можно свести к многомерной параллельной обработке.

Свойства ТЧП изоморфны свойствам дискретного преобразования Фурье. Следовательно, должна существовать возможность вычисления ТЧП с использованием быстрых алгоритмов, аналогичных БПФ. Перенесем подходы, используемые при построении БПФ с прореживанием по времени из поля комплексных чисел (1) в конечное поле Галуа GF(M). Принимая во внимание (1), перепишем (2) в виде:

yrd18.wmf

yrd19.wmf. (4)

Из выражения (4) вытекает условие разложения N точечного ТЧП в сумму двух ТЧП длины N/2. Рассмотрим следующую теорему.

Теорема. Пусть GF(M) – конечное поле Галуа, N – четное число, GN – циклическая группа порядка N, yrd21.wmf – примитивный корень порядка N, удовлетворяющий

yrd22.wmf. (5)

Тогда ТЧП последовательности yrd23.wmf, где yrd24.wmf представимо в виде суммы ТЧП подпоследовательностей с четными yrd25.wmf и нечетными yrd26.wmf номерами.

Доказательство. Из условия (5) следует существование примитивного корня yrd27.wmf порядка N/2. Преобразуем выражение (4) с учетом равенства (5):

yrd28.wmf

yrd30.wmf

yrd31.wmf, (6)

где S11(k) и S12(k) – ТЧП последовательностей с четными yrd32.wmf и нечетными yrd33.wmf номерами.

Так как S11(k) и S12(k) имеют размерность N/2, формулу (6) можно использовать только для вычисления S(k) при yrd34.wmf. Для случая следует воспользоваться периодичностью ТЧП:

yrd35.wmf и yrd36.wmf. (7)

С учетом (7) при условии yrd37.wmf формулу (6) можно переписать в виде

yrd38.wmf. (8)

Теорема доказана.

В отличие от БПФ в поле комплексных чисел, в котором существуют корни из единицы любой степени (yrd39.wmf, yrd40.wmf), условие представления размерности ТЧП в виде степени двойки не является достаточным для существования быстрого ТЧП с «прореживанием по времени» ввиду отсутствия в конечных полях корней из единицы любой степени. Рассмотрим примеры использования доказанной теоремы.

Результаты исследования и их обсуждение

Воспользуемся для вычисления ТЧП сигнала конечные поля GF(17), GF(29). При этом в поле GF(17) длина входной последовательности равна 16 отсчетам, а в конечном поле GF(29) – длина входного вектора будет составлять 28 отсчетов.

Пример 1. Выполним теоретико-числовое преобразование вектора (x0, x1, x2, ..., x15) = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15) в поле GF(17), для чего подготовим цепочку примитивных корней: ε16 = 3, ε8 = 9, ε4 = 13, ε2 = 16. Заметим, что подобранные числа удовлетворяют условию

yrd43.wmf, yrd44.wmf, yrd45.wmf.

На первом этапе разработанного быстрого алгоритма ТЧП по модулю 17 получаем

yrd46.wmf; yrd47.wmf;

yrd48.wmf; yrd49.wmf;

yrd50.wmf yrd51.wmf

yrd52.wmf

yrd53.wmf.

Аналогичным образом получаются остальные спектральные составляющие ТЧП. Структура и конкретные значения 16-точечного ТЧП представлена на рис. 1.

Пример 2. Вычислим ТЧП входного вектора отсчетов (x0, x1, x2, ..., x15, x27) = (0, 1, 2, ..., 26, 27) в конечном поле Галуа GF(29). Для этого необходимо вычислить следующую цепочку примитивных корней: ε28 = 2, ε14 = 4, ε7 = 16. Структура и конкретные значения 28-точечного ТЧП представлены на рис. 2.

Сформулированные в работе условия разложимости N-точечного ТЧП на преобразования меньшей размерности и доказательство теоремы позволяют разрабатывать быстрые алгоритмы ТЧП вычисления ортогональных преобразований сигналов в конечных полях. Это было продемонстрировано на примерах 1 и 2. Наиболее эффективны быстрые алгоритмы ТЧП в случае, когда длина вектора исходных данных является степенью двойки и выполнены условия (5). В этом случае деление последовательностей на две части можно продолжать до тех пор, пока не получатся двухэлементные последовательности, что было показано в примере 1.

Оценим эффективность быстрого алгоритма ТЧП с прореживанием по времени, обусловленную разложением N-точечного преобразования на несколько малых. Для вычисления N-точечного ТЧП по формуле (2) требуется N2 операций. Наибольшая степень ускорения вычислений может быть достигнута при N = 2k и существовании примитивного корня порядка N. Число требуемых при этом операций можно оценить как yrd56.wmf. Таким образом, вычислительные затраты по сравнению с непосредственным использованием формулы (2) уменьшаются в yrd57.wmf раз.

Заключение

Основное преимущество ТЧП по сравнению с ДПФ состоит в том, что корни из единицы имеют простое представление, что позволяет в вычислениях заменить комплексную арифметику на целочисленную. Использование быстрых ТЧП с прореживанием по времени имеет смысл, если число элементов в анализируемой последовательности является степенью 2 и только при существовании в конечном поле GF(M) примитивного корня порядка длины анализируемой последовательности. В этом случае разработанный алгоритм быстрого ТЧП сигнала не является приближенным алгоритмом, причем ускорение достигается исключительно за счет оптимальной организации вычислений.

yrd1.tif

Рис. 1. Структура быстрого ТЧП по модулю 17 при N = 16

yrd2.tif

Рис. 2. Структура быстрого ТЧП по модулю 29 при N = 28

Разработанный алгоритм быстрого выполнения ТЧП сигнала с прореживанием по времени предназначен для одновременного расчета всех спектральных коэффициентов S(k). Если необходимо получить значения коэффициентов для некоторых k, предпочтительнее использовать прямую формулу ТЧП.