Scientific journal
Modern high technologies
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 1,007

DEVELOPMENT OF A MATHEMATICAL MODEL OF THE MULTICHANNEL SYSTOLIC MATRIX TO PERFORM THE NUMBER-THEORETIC TRANSFORMATIONS OF SIGNALS IN POLYNOMIAL MODULAR CODE

Kalmykov M.I. 1 Toporkova E.V. 1 Stepanova E.P. 1 Voloshin E.A. 1 Provornov I.A. 1 Tyncherov K.T. 2
1 North-Caucasian Federal University
2 Federal State Budgetary Educational Institution of Higher Edication «Ufa State Petroleum Technological University» (USPTU)
Methods and algorithms of digital signal processing (DSP) are constantly expanding their scope. This is especially evident in the standards of IEEE 802.11, on the basis of which the majority of wireless information transmission systems are built. The OFDM technology is based on the orthogonal discrete Fourier transform (DFT) and its fast calculation algorithms. However, DFT has a number of drawbacks that reduce the efficiency of the OFDM technology. These include the use of complex numbers as the turning coefficients of DFT. First, this leads to an increase in circuit costs for the implementation of orthogonal signal transformations. Second, the use of sine and cosines to perform DFT results in additive and multiplicative errors. To eliminate these shortcomings, the article proposes to use the theoretical – numerical transformations (TNT), which are implemented in the polynomial modular code (PMC). It is possible to increase the speed of TNT in PMC due to the application of systolic calculation principles. Therefore, the development of a mathematical model of a multichannel systolic matrix to perform the theoretical and numerical transformations of signals in the polynomial modular code is an urgent task. The aim of the article is to increase the speed of TNT calculation by developing a mathematical model of a multichannel systolic matrix functioning in a polynomial modular code.
orthogonal signal transformations
discrete Fourier transform
systolic algorithms
number-theoretic transformation
polynomial modular code

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