Научный журнал
Современные наукоемкие технологии
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 1,021

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

Калмыков М.И. 1 Топоркова Е.В. 1 Степанова Е.П. 1 Волошин Е.А. 1 Проворнов И.А. 1 Тынчеров К.Т. 2
1 ФГАОУ ВО «Северо-Кавказский федеральный университет»
2 ФГБОУ ВО «Уфимский государственный нефтяной технический университет»
Методы и алгоритмы цифровой обработки сигналов (ЦОС) постоянно расширяют сферу своего применения. Особенно наглядно это проявляется в стандартах IEEE 802.11, на основе которых построено большинство беспроводных систем передачи информации. В основе технологии OFDM лежит ортогональное дискретное преобразование Фурье (ДПФ) и также его быстрые алгоритмы вычисления. Однако ДПФ имеет ряд недостатков, которые снижают эффективность технологии OFDM. К ним можно отнести использование комплексных чисел в качестве поворачивающих коэффициентов ДПФ. Во-первых, это приводит к увеличению схемных затрат на реализацию ортогональных преобразований сигналов. Во-вторых, использование синусов и косинусов для выполнения ДПФ приводит к аддитивным и мультипликативным погрешностям. Для устранения отмеченных недостатков в статье предлагается использовать теоретико-числовые преобразования (ТЧП), которые реализуются в полиномиальном модулярном коде (ПМК). Повысить скорость выполнения ТЧП в ПМК возможно за счет применения систолических принципов вычислений. Поэтому разработка математической модели многоканальной систолической матрицы для выполнения теоретико-числовых преобразований сигналов в полиномиальном модулярном коде является актуальной задачей. Целью статьи является повышение скорости вычисления ТЧП за счет разработки математической модели многоканальной систолической матрицы, функционирующей в полиномиальном модулярном коде.
ортогональные преобразования сигналов
дискретное преобразование Фурье
систолические алгоритмы
теоретико-числовое преобразование
полиномиальный модулярный код
1. Катков К.А., Пашинцев В.П., Катков Е.К. Влияние параметров возмущенной ионосферы на ошибку слежения за фазой навигационного радиосигнала // Современная наука и инновации. 2016. № 2 (14). С. 52–64.
2. Катков К.А., Пашинцев В.П., Катков Е.К. Информационная система мониторинга ионосферы // Известия Самарского научного центра Российской академии наук. 2016. Т. 18. № 2–3. С. 907–912.
3. Джиган В.И. Адаптивная фильтрация сигналов: теория и алгоритмы. М.: Техносфера, 2013. 528 с.
4. Meyer-Baese U.H., Meyer-Baese A., Gonzalez D., Botella G. Code obfuscation using very long identifiers for FFT motion estimation models in embedded processors. Journal of Real-Time Image Processing, 2016. Р. 817–827.
5. Пролетарский А.В., Баскаков И.В., Федотов Р.А. Беспроводные сети Wi-Fi (2-е изд.). М.: НОУ «ИНТУИТ», 2016. 284 с.
6. Бакулин М.Г., Крейнделин В.Б., Шлюма А.М., Шумов А.П. Технология OFDM: учебное пособие для вузов. М.: Горячая линия-Телеком, 2017. 352 с.
7. Калмыков И.А., Емарлукова Я.В., Гиш Т.А., Дунин А.В., Макарова А.В. Математические модели и схемные решения отказоустойчивых непозиционных вычислительных систем: коллективная монография. Ставрополь: Изд-во СКФУ, 2016. 216 с.
8. Юрданов Д.В., Калмыков М.И., Журавлев К.М., Калмыков И.А. Использование теоретико-числовых преобразований для систем связи с OFDM // Международный журнал прикладных и фундаментальных исследований. 2017. № 3–2. С. 178–182.

Характерной чертой современных достижений в сфере инфотелекоммуникаций является широкое применение алгоритмов и методов цифровой обработки сигналов (ЦОС). Так, в работах [1, 2] показана реализация методов ЦОС в системах космической связи. Применение данных методов позволяет повысить помехоустойчивость в условиях мелких неоднородностей. В работах [3, 4] рассматривается использование методов ЦОС при выполнении цифровой фильтрации. В работах [5, 6] показана перспективность использования ортогональных преобразований сигналов в системах OFDM. Применение дискретного преобразования Фурье (ДПФ) и его быстрых алгоритмов в системах передачи информации, использующих стандарты IEEE 802.11, позволяет повысить скорость передачи данных при наиболее эффективном использовании радиочастотного ресурса. Однако быстрое преобразование Фурье (БПФ) характеризуется рядом недостатков, которые приводят к повышению схемных затрат и снижению точности выполнения ортогональных преобразований сигналов. Устранить такие недостатки возможно за счет использования теоретико-числовых преобразований (ТЧП), которые реализуются в полиномиальном модулярном коде (ПМК). Использование целочисленных вычислений в ПМК позволяет устранить ошибки округления и обеспечить преобразование сигнала при меньших схемных затратах. Повысить скорость выполнения ТЧП в ПМК возможно за счет применения систолических принципов вычислений. Поэтому разработка математической модели многоканальной систолической матрицы для выполнения теоретико-числовых преобразований сигналов в полиномиальном модулярном коде является актуальной задачей.

Известно, что использование целочисленных ортогональных преобразований сигналов, в частности теоретико-числовых преобразований, позволяет устранить ошибки округления, которые вызваны тригонометрическими поворачивающими коэффициентами ДПФ и БПФ. Кроме того, использование полиномиального модулярного кода приводит к повышению скорости выполнения ТЧП за счет распараллеливания вычислений на уровне арифметических модульных операций и использования табличной реализации [7]. Дальнейшее повышение скорости выполнения ТЧП возможно за счет применения параллельно-конвейерных вычислений, использующих систолические принципы построения. Поэтому целью статьи является повышение скорости вычисления ТЧП за счет разработки математической модели многоканальной систолической матрицы, функционирующей в ПМК.

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

В настоящее время при выполнении ортогональных преобразований сигналов широко используются быстрые преобразования Фурье, которые задаются выражением

kalm01.wmf (1)

где kalm02.wmf и kalm03.wmf – отсчеты входного вектора, имеющие четные и нечетные номера соответственно; kalm04.wmf – поворачивающие коэффициенты БПФ.

Анализ выражения (1) показывает, что использование косинусов и синусов в качестве поворачивающих коэффициентов WN приводит к значительным погрешностям округления. Устранить данный недостаток позволяет целочисленное ортогональное преобразование ТЧП. В этом случае снимаемый на выходе АЦП входной вектор x(n) представляет собой множество элементов поля GF(М). Тогда спектральные коэффициенты ТЧП определяются как

kalm05.wmf, (2)

где kalm06.wmf; kalm07.wmf – порождающий элемент поля Галуа с характеристикой М.

Ортогональные преобразования сигналов также можно выполнить в полях GF(pv)

kalm08.wmf, (3)

где kalm09.wmf – s-я спектральная составляющая сигнала; kalm10.wmf – n-й входной отсчет; kalm11.wmf. kalm12.wmf

Повысить скорость выполнения ТЧП возможно за счет применения ПМК. В данном коде в качестве оснований используются неприводимые полиномы pi(z), где kalm13.wmf. В коде ПМК число Х сначала представляется в полиномиальной форме X(z), а затем в виде остатков kalm14.wmf, где kalm15.wmf [7]. Тогда справедливо выражение

kalm16.wmf, (4)

где kalm17.wmf; * – операция сложения, вычисления и умножения по модулю рi(z).

Применяя полиномиальный модулярный код, получаем следующее ТЧП сигнала

kalm18.wmf (5)

где kalm19.wmf; kalm20.wmf; kalm21.wmf; kalm22.wmf

Однако выполнение ТЧП сигнала в ПМК требует временных затрат, соизмеримых с O(d2) операций модульных умножений. Дальнейшее снижение временных затрат на выполнение ТЧП возможно за счет применения систолических принципов вычислений [8]. При использовании систолических матриц преобразования (4) можно выполнить на основе рекуррентной схемы Горнера

kalm23.wmf, (6)

где kalm24.wmf.

Тогда математическая модель систолического массива ТЧП в модулярном коде имеет вид

kalm25.wmf (7)

Проведя обобщение равенства (7), получаем математическую модель ТЧП сигналов в модулярном коде с использованием многоканальной систолической матрицы (МСМ)

kalm26.wmf (8)

Так как МСМ состоит из однотипных процессорных элементов (ПЭ), то каждый из ПЭ (s = 1, 2, …, d), выполняет следующую базовую операцию

kalm27.wmf, (9)

где kalm28.wmf; L – текущий такт вычислений в j-й ячейке; kalm29.wmf, kalm30.wmf – записанное в регистр РгS на L-м такте значение суммы; kalm31.wmf; kalm32.wmf – записанное в регистр РгS на (L – 1)-м такте вычисленное значение суммы; kalm33.wmf; kalm34.wmf – поворачивающий коэффициент на входе j-й ячейки МСМ в L-й такт работы.

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

Пусть задан ПМК, имеющий основания kalm35.wmf и kalm36.wmf. Данные полиномы имеют мультипликативные группы порядка d = 7. Значит, такой ПМК способен выполнить 7-точечную реализацию ТЧП сигнала. Тогда получаем

kalm37.wmf

Для разработки структуры МСМ, реализующей ТЧП в ПМК, составим таблицу, в которой показан процесс получения спектральных отсчетов для kalm38.wmf и kalm39.wmf.

Получение спектральных составляющих ТЧП в МПК

Спектр Х(j)

Входной отсчет kalm40.wmf

Входной отсчет kalm41.wmf

kalm42.wmf

kalm43.wmf

kalm44.wmf

kalm45.wmf

kalm46.wmf

kalm47.wmf

kalm48.wmf

kalm49.wmf

kalm50.wmf

kalm51.wmf

kalm52.wmf

kalm53.wmf

kalm54.wmf

kalm55.wmf

kalm56.wmf

kalm57.wmf

kalm58.wmf

kalm59.wmf

kalm60.wmf

kalm61.wmf

kalm62.wmf

kalm63.wmf

kalm64.wmf

kalm65.wmf

kalm66.wmf

kalm67.wmf

kalm68.wmf

kalm69.wmf

kalm70.wmf

kalm71.wmf

Обобщая результаты, представленные в таблице, получаем следующее выражение

kalm72.wmf

Схемная реализация разработанной математической модели МСМ, реализующей ТЧП сигналов в ПМК с основаниями kalm73.wmf и kalm74.wmf, показана на рис. 1. Каждый из ПЭ состоит из двух регистров (Рг), которые предназначены для записи отсчетов входного вектора kalm75.wmf и поворачивающего вектора kalm76.wmf. Для реализации выражения (7) используются умножитель (Ум) по модулю pi(z), где i = 1, 2, и сумматор (Cум) по модулю два. Для хранения промежуточного результата используется регистр (РгS). На рис. 2 приведена временная диаграмма вычисления ТЧП сигнала в МСМ.

kalmik1.wmf

Рис. 1. Схемная реализация математической модели МСМ ТЧП, функционирующей в ПМК

kalmik2.wmf

Рис. 2. Временная диаграмма вычисления ТЧП в МСМ

Анализ разработанной математической модели ТЧП сигнала в МСМ показал, что начальная загрузка матрицы составляет d = 7 тактов. При этом количество тактов, составляющих один цикл вычислений, равно kalm77.wmf. Из рис. 2 наглядно видно, что коэффициент эффективности применения оборудования в разработанной математической модели МСМ вычислений ТЧП составляет Q = 1. Очевидно, что время реализации базовой операции ПЭ определяется

kalm78.wmf, (10)

где t1 – время реализации процедуры приема-передачи данных в ПЭ; t2 – время модульного умножения; t3 – время выполнения операции суммирования по модулю два; t4 – время необходимое на выполнение процедуры записи и считывания результата вычислений.

Время реализации ТЧП сигнала в ПМК на основе разработанной модели МСМ составит

kalm79.wmf. (11)

Рассмотрим работу разработанной МСМ по основанию р1(z). Перед началом работы регистры РгS МСМ обнуляются. На первом такте работы значения kalm80.wmf, kalm81.wmf поступают в ПЭ1. Спустя время t1 + t2 выполняется суммирование по модулю два kalm82.wmf с содержимым РгS. Промежуточный результат суммирования на микротакте t4 заносится в регистр РгS. Во время второго такта работы значения kalm83.wmf и kalm84.wmf с выхода ПЭ1 подаются в ПЭ2. Одновременно в ПЭ1 поступают kalm85.wmf и kalm86.wmf. На микротакте t2 второго такта kalm87.wmf задерживается в элементе задержки и одновременно в ПЭ2 вычисляется kalm88.wmf. Затем в ПЭ1 и ПЭ2 на микротакте tз происходит суммирование по модулю два, а на микротакте t4 полученные суммы записываются в регистры РгS1 и РгS2. В дальнейшем все ПЭ работают синхронно. На третьем такте выполняются переводы: kalm89.wmf и kalm90.wmf – в ПЭ3; kalm91.wmf и kalm92.wmf – в ПЭ2; kalm93.wmf и kalm94.wmf – в ПЭ1. Теперь три ПЭ (L = 1, 2, 3) работают синхронно. На четвертом такте работу начинает ПЭ4, куда поступают kalm95.wmf и kalm96.wmf. На пятом такте в работу включается ПЭ5, на шестом такте – ПЭ6, на седьмом такте – ПЭ7. При этом все ПЭ работают синхронно.

Как видно из рис. 2, на d = 7 такте МСМ закончила процедуру загрузки и разгонки. В конце данного такта результат kalm97.wmf, полученный в ПЭ1, поступает на выход МСМ. На следующем такте значение спектральной составляющей kalm98.wmf будет получено в ПЭ2. На (d + 2) = 9 такте результат kalm99.wmf будет получен в ПЭ3 и т.д. Значит, время выдачи результатов будет составлять период равный kalm100.wmf. Чтобы не тормозить работу конвейера на (d + 1) = 8 такте, на вход ПЭ1 МСМ поступают данные kalm101.wmf и kalm102.wmf.

Переход к МПК позволяет повысить скорость базовой операции ТЧП (9). В этом случае kalm103.wmf, где kalm104.wmf и kalm105.wmf – временные затраты на реализацию операции умножения и сложения. Пусть разрядность модуля d = deg Р(z) = 30. Если в МСМ использовать умножитель матричного типа, то kalm106.wmf, где ТS – время суммирования в одноразрядном сумматоре. Пусть значение ТS = 15 нс. При обработке 30-разрядных данных на базовую операцию ТЧП потребуется kalm107.wmf нс.

Вычислим временные затраты на базовую операцию ТЧП в МПК. Для d = deg Р(z) = 30 возможно использовать шесть модулей разрядности kalm108.wmf, где i = 1, 2,.., 6. Для выполнения операций сложения и умножения по модулю pi(z) можно использовать LUT-таблицы (ПЗУ 1636РР1У), время выборки которых составляет Твыб = 65 нс. Тогда время выполнения базовой операции ТЧП равно kalm109.wmf нс. Значит, применение ПМК повышает скорость выполнения базовой операции ТЧП в 3,8 раза. Кроме того, использование разработанной математической модели МСМ позволило повысить скорость выполнения ТЧП на 10 % по сравнению с чисто-систолической моделью вычислений ТЧП и 14,9 раза по сравнению c классическим выполнением ТЧП в GF(25).

Заключение

Применение ТЧП в задачах ЦОС минимизирует ошибки округления, которые получаются при использовании БПФ. Использование разработанной математической модели МСМ, функционирующей в ПМК позволяет повысить скорость вычисления базовой операции ТЧП в 3,8 раза при обработке 30-разрядных данных. А применение алгоритма МСМ позволило повысить скорость выполнения ТЧП на 10 % по сравнению с чисто-систолической моделью вычислений ТЧП и 14,9 раза по сравнению c классическим выполнением ТЧП в GF(25).

Исследование выполнено при финансовой поддержке РФФИ в рамках научного проекта № 18-37-00009.


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

Калмыков М.И., Топоркова Е.В., Степанова Е.П., Волошин Е.А., Проворнов И.А., Тынчеров К.Т. РАЗРАБОТКА МАТЕМАТИЧЕСКОЙ МОДЕЛИ МНОГОКАНАЛЬНОЙ СИСТОЛИЧЕСКОЙ МАТРИЦЫ ДЛЯ ВЫПОЛНЕНИЯ ТЕОРЕТИКО-ЧИСЛОВЫХ ПРЕОБРАЗОВАНИЙ СИГНАЛОВ В ПОЛИНОМИАЛЬНОМ МОДУЛЯРНОМ КОДЕ // Современные наукоемкие технологии. – 2019. – № 2. – С. 63-68;
URL: http://top-technologies.ru/ru/article/view?id=37410 (дата обращения: 30.11.2020).

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

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