Научный журнал
Фундаментальные исследования
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,222

РАЗРАБОТКА БЫСТРОГО АЛГОРИТМА ВЫЧИСЛЕНИЯ ТЕОРЕТИКО-ЧИСЛОВЫХ ПРЕОБРАЗОВАНИЙ СИГНАЛОВ

Юрданов Д.В. 1 Калмыков М.И. 1 Гостев Д.В. 1 Калмыков И.А. 1
1 ФГАОУ ВО «Северо-Кавказский федеральный университет»
Целью исследований является повышение скорости выполнения ортогональных преобразований сигналов при использовании теоретико-числовых преобразований в конечных полях. Использование быстрых алгоритмов дискретного преобразования Фурье позволяет повысить скорость цифровой обработки сигналов (ЦОС) за счет параллельных вычислений. Однако быстрое преобразование Фурье (БПФ) обладает рядом недостатков. Во-первых, это наличие двух вычислительных трактов для обработки действительной и мнимой части сигнала. Во-вторых, использование тригонометрических функций в качестве поворачивающих коэффициентов, что приводит к ошибкам округления. Решить данную проблему можно за счет использования теоретико-числового преобразования сигнала. Однако при выполнении ортогональных преобразований сигналов в конечных полях Галуа не используются быстрые алгоритмы, подобные быстрым алгоритмам преобразованиям Фурье. Поэтому разработка быстрого алгоритма вычисления теоретико-числового преобразования является актуальной задачей.
цифровая обработка сигналов
ортогональные преобразования сигналов
быстрое преобразование Фурье
быстрые алгоритмы
теоретико-числовые преобразования
1. Арслан Х., Чен Ши Нинг. Сверхширокополосная беспроводная связь. – М.: Техносфера, 2012. – 550 с.
2. Власов Е.Г. Конечные поля в телекоммуникационных приложениях. Теория и применение FEC, CRC и M-последовательностей. Практическое пособие. – М.: Инфа-М, 2016. – 285 с.
3. Макклеллан Дж.Г., Рейдер Ч.М. Применение теории чисел в цифровой обработке сигналов; Пер. с англ. / Под ред. Ю.И. Манина. – М.: Радио и связь, 1993. – 356 с.
4. Чернов В.М. Квазипараллельный алгоритм безошибочного вычисления свертки в редуцированных кодах Мерсена-Люка // Компьютерная оптика. – 2015. – № 2. – С. 241–248.
5. Шапошников А.В. Быстрый алгоритм вычисления теоретико-числового преобразования // Актуальные проблемы современной науки – 2013. – № 2. – С. 204-207.
6. Юрданов Д.В., Калмыков М.И., Журавлев К.М., Калмыков И.А. Использование теоретико-числовых преобразований для систем связи с OFDM // Международный журнал прикладных и фундаментальных исследований. – 2017. – № 3–2. – С. 178–182.
7. Anne O’Donnell, Chris J. Bleakley, Efficient Concurrent Error Detection and Correction of Soft Errors in NTT-based Convolutions. Published in: Signals and Systems Conference (ISSC 2009), IET Irish. Date Added to IEEE Xplore: 12 August 2010. Electronic ISBN: 978-1-84919-213-2. INSPEC Accession Number: 11260190. DOI: 10.1049/cp.2009.1724.
8. Jörg Arndt Matters Computational. Ideas, Algorithms, Source Code. – Springer Berlin Heidelberg, 2011. – 731 р.
9. Steven G. Johnson and Matteo Frigo, A modied split-radix FFT with fewer arithmetic operations, IEEE Transactions on Signal Processing 55. – 2007. – № 1. – Р. 111–119.
10. Yurdanov D., Kalmykov M., Gostev D. The implementation of information and communication technologies with the use of modular codes. CEUR Workshop Proceedings 1837, 2017. – Р. 206–212.

Цифровая обработка сигналов (ЦОС) относится к числу наиболее динамически развивающихся областей инженерной деятельности [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, предпочтительнее использовать прямую формулу ТЧП.

 


Библиографическая ссылка

Юрданов Д.В., Калмыков М.И., Гостев Д.В., Калмыков И.А. РАЗРАБОТКА БЫСТРОГО АЛГОРИТМА ВЫЧИСЛЕНИЯ ТЕОРЕТИКО-ЧИСЛОВЫХ ПРЕОБРАЗОВАНИЙ СИГНАЛОВ // Фундаментальные исследования. – 2017. – № 10-1. – С. 67-71;
URL: http://www.fundamental-research.ru/ru/article/view?id=41791 (дата обращения: 21.07.2019).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.252