Scientific journal
Advances in current natural sciences
ISSN 1681-7494
"Перечень" ВАК
ИФ РИНЦ = 0,775

NONPOSITIONAL CODE RESIDUE CLASSES IN PARALLEL DIGITAL SIGNAL PROCESSING TECHNOLOGY

Goncharov P.S. 1 Kalmykov M.I. 1 Stepanova E.P. 1
1 North-Сaucasian federal university
3024 KB
The main goal of the research is the development of parallel technology of digital signal processing (DSP), which allows the use , by using the mathematical model nonpositional integer DSP provide high-speed signal processing. To solve this problem we propose to use mathematical models DSP using nonpositional modular codes that by parallelizing at the transaction level and low-bit data processing speeds up computing and digital signal processing to provide real-time
polynomial system of residue classes
modular codes
parallel computing the residues
orthogonal bases

Использование цифровых методов представления, обработки и передачи приводит к многократному увеличению занимаемой полосы частот и, как следствие этого, к многократному увеличению скорости передачи информационных сообщений. Решение данной проблемы лежит в области разработки эффективных методов реализации цифровой обработки сигналов (ЦОС). Отмеченные обстоятельства обусловили повышенный интерес разработчиков систем связи к использованию методов цифровой обработки сигналов в различных областях, начиная с обработки речи, заканчивая обработкой изображения. Повысить эффективность реализации ЦОС возможно за счет применения математической модели, поддерживающую параллельную обработку исходных данных.

Основная часть. Основным содержание цифровой обработки сигнала является извлечение полезной информации относительно объекта, который является источником информации, либо относительно среды, через которую сигнал проходит. Сложность алгоритмов, используемых для обработки сигнала, определяются такими факторами, как структура сигналов, их количество, частотный диапазон, необходимая разрешающая способность, тип источников обрабатываемых сигналов, условия распространения сигнала от источников на вход системы обработки. При этом эффективность работы системы ЦОС, ее производительность, надежность, габаритные размеры и потребляемая мощность тесно связаны с требуемой точностью вычислений, которая определяется форматами используемых данных, диапазоном частот входных сигналов, объемами обрабатываемой информации и особенно алгоритмом реализации.

Существующая в последние годы тенденция в цифровой вычислительной технике тенденция к распараллеливанию вычислений связана с непрерывным ростом требований к производительности вычислительных устройств ЦОС. Среди методов обработки данных в реальном масштабе времени наиболее оптимальными для микроэлектронной реализации считаются методы, базирующиеся на нейросетевом базисе.

Однако предъявляемые жесткие временные ограничения и отсутствие высокопроизводительной нейросетевой базы ЦОС является основным сдерживающим фактором широкого внедрения методов цифрового преобразования сигналов в системах передачи речи со сжатием, статистическим уплотнением, пакетной коммутацией, IP-телефонии и других инфотелекоммуникационных системах.

Требования высокой точности и высокой скорости обработки сигнала, предъявляемые к современным системам цифровой обработки сигналов, обуславливает активизацию работ по применению математических моделей ЦОС, обладающих свойством кольца или поля. Ввиду изложенного положения дел на текущем этапе внедрения методов цифровой обработки сигналов в системы обработки и передачи информации вполне понятна актуальность исследований по разработке высокоскоростных параллельных спецпроцессоров ЦОС, поддерживающих целочисленную арифметику, реализованных на основе нейросетевого базиса.

Проведенные исследования методов ЦОС показали, что реализация ортогональных преобразований сигналов в реальном масштабе времени возможно лишь на основе специализации вычислительных средств. Под данной процедурой понимается распараллеливание вычислений на одновременно работающем множестве процессоров, что позволяет в рамках существующих ограничений на массогабаритные характеристики добиться больших функциональных возможностей. Наиболее перспективным направлением распараллеливания вычислений является использование непозиционных систем, в частности, полиномиальной системы классов вычетов (ПСКВ). Если в качестве оснований алгебраической системы выбрать минимальные многочлены gonch2.wmf поля gonch3.wmf, то полином gonch4.wmf, удовлетворяющий условию gonch5.wmf где gonch6.wmf – полный диапазон, представляется в виде

gonch7.wmf, (1)

где gonch8.wmf, gonch9.wmf.

Рассмотрим выполнение модульных арифметических операций в ПСКВ. Пусть степень минимального многочлена gonch10.wmf, равна mi. Тогда первый операнд имеет вид

gonch11.wmf.

Соответственно для второго операнда получаем

gonch12.wmf.

Тогда для многочленов

gonch13.wmf

и gonch14.wmf, справедливо:

gonch15.wmf, (2)

gonch16.wmf, (3)

В силу дистрибутивности операции умножения операндов над кольцом на элементы этого кольца относительно операции сложения справедливо

gonch17.wmf (4)

где gonch18.wmf – линейная свертка; gonch19.wmf, gonch20.wmf.

Рассмотрим пример. Пусть задана ПСКВ с модулями p1=z+1; p2=z3+z2+1; p3=z3+z+1 и диапазоном

gonch21.wmf,

а также два полинома

A(z)=z4+z3+z=(1, 0, z2+z+1)

и B(z)= z2+z+1=(1, z2+z+1, z2+z+1).

Тогда справедливо

Сумма двух полиномов

Произведение двух полиномов

C(z)=A(z)+B(z)=z4+z3+z2+1=(0, z2+z+1, 0)

C(z)=A(z)B(z)=z6+z2+z=(1, 0, z+1)

A(z)= (1, 0 , z2+z+1)

B(z)= (1, z2+z+1, z2+z+1)

C(z)= (0, z2+z+1, 0 )

A(z)= (1, 0 , z2+z+1)

B(z)= (1, z2+z+1, z2+z+1)

C(z)= (1, 0 , z+1 )

Наряду с модульными операциями непозиционный СП, функционирующий в ПСКВ, выполняет и немодульные процедуры. К ним можно отнести прямое и обратное преобразование кодов [3], вычисление позиционных характеристик [3] , определение интервала [3], расширение системы оснований [3], вычисление коэффициентов обобщенной полиадической системы [3], определение «спектральных составляющих» кода ПСКВ [3].

Первой обязательной немодульной операцией является прямое преобразование из позиционного кода в код ПСКВ [4]. Образование остатка αi(z) полинома A(z) осуществляется

gonch22.wmf (5)

где gonch23.wmf – наименьшее целое от деления A(z) на pi(z); i=1,2,…n.

В полиномиальной системе классов вычетов выражение (5) можно представить в виде

gonch24.wmf. (6)

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

gonch25.wmf, (7)

где Ci – остатки от деления на pi степеней основания, которые дадут набор

gonch26.wmf. (8)

Основным достоинством данного метода является то, что выполнения используется позиционный сумматор. Однако метод понижения разрядности носит последовательный характер, в результате чего характеризуется значительными временными затратами [4].

Чтобы исправить данный недостаток был разработан итеративный алгоритм прямого преобразования ПСС-ПСКВ, который определяется выражением

gonch27.wmf, (9)

где l=0,1,2… – число итераций.

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

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

gonch28.wmf, (10)

где gonch29.wmf, gonch30.wmf.

Как показано в работе [4], этот алгоритм требует минимальных схемных затрат и может быть реализован в виде двухслойной нейронной сети. Рассмотрим пример. Необходимо определить остаток полинома gonch31.wmf по модулю gonch32.wmf, на основе равенства (10). В таблице приведены значения остатков каждого разряда

Значения остатков gonch33.wmf

zj

gonch34.wmf

zj

gonch35.wmf

zj

gonch36.wmf

z0

1

z5

z3+z+1

z10

z3+z

z1

z

z6

z3+z2+z+1

z11

z3+z2+1

z2

z2

z7

z2+z+1

z12

z+1

z3

z3

z8

z3+z2+z

z13

z2+z

z4

z3+1

z9

z2+1

z14

z3+z2

Тогда, согласно (10), получаем остаток полинома gonch37.wmf

gonch38.wmf.

Таким образом, gonch39.wmf.

Второй обязательной немодульной операцией является обратное преобразование из кода ПСКВ в позиционный код [4]. Как правило, обратное преобразование из ПСКВ в ПСС выполняется на основе Китайской теоремы об остатках (КТО). Согласно этой теореме обратное преобразование определяется

gonch40.wmf, (11)

где gonch41.wmf – ортогональный базис системы; gonch42.wmf, K(z) – ранг, P(z) – полный диапазон.

При этом ортогональный базис должен удовлетворять требованию

gonch43.wmf. (12)

В работах [4-9] приведен алгоритм вычисления ортогональных базисов ПСКВ:

1. Вычисляется значение

gonch44.wmf. (13)

2. Определяется значение остатка

gonch45.wmf. (14)

3. Выбирается вес ортогонального базиса

gonch46.wmf. (15)

4. Вычисляется значение ортогонального базиса

gonch47.wmf. (16)

Вычислим ортогональные базисы ПСКВ, имеющей модули p1(z)=z+1, p2(z)=z2+z+1, p3(z)=z4+z3+z2+z+1, p4(z)=z4+z3+1, p5(z)=z4+z+1. Согласно выражений (13) и (14) имеем

P*1(z)= z14+z13+z12+z11+z10+z9+z8+z7+z6+z5+z4+ z3+z2+z+1;

δ1(z)=1

P*2(z)= z13+z12+z10+z9+z7+z6+z4+z3+z+1;

δ2(z)=z+1

P*3(z)= z11+z10+z6+z5+z+1;

δ3(z)=z+1

P*4(z)= z11+z10+z9+z8+z6+z4+z3+1

δ4(z)=z+1

P*5(z)=z11+z8+z7+z5+z3+z2+z+1;

δ5(z)=z3+1

Определим веса ортогональных базисов и их величины согласно (15) и (16):

m1(z)=1

B1(z)= z14+z13+z12+z11+z10+z9+z8+z7+z6+z5+z4+ z3+z2+z+1;

m2(z)=z

B2(z)= z14+z13+z11+z10+z8+z7+z5+z4+z2+z;

m3(z)=z3+z

B3(z)= z14+z13+z12+z11+z9+z8+z7+z6+z4+z3+z2+z;

m4(z)=z3

B4(z)= z14+z13+z12+z11+z9+z7+z6+z3;

m5(z)=z

B5(z)=z12+z9+z8+z6+z4+z3+z2+z;

Пусть задан полином

gonch48.wmf,

который в ПСКВ имеет вид gonch49.wmf. Тогда обратное преобразование на основе КТО определяется (11)

gonch50.wmf

Приведенные в статье материалы и примеры позволяют сделать вывод о том, что полиномиальная система классов вычетов может быть использована при выполнении цифровой обработки сигналов на основе выражения

gonch51.wmf, (17)

где gonch52.wmf – первообразный элемент порядка d для локального кольца Pi(z), который задается модулем pi(z) ПСКВ; N – порядок мультипликативной группы, порожденной этим модулем; <<gonch53.wmf>>; l=1,2,…,m; k=0,1,…Т–1.

В этом случае структура непозиционного СП ЦОС, реализующего (17), имеет вид

gonc1.wmf

Рис. 1. Структура параллельного спецпроцессора ПСКВ

Как наглядно видно из рис. 1, реализации ортогональных преобразований с использованием математической модели ЦОС в кольце полиномов будет задаваться выражением

gonch54.wmf (18)

Характерной чертой непозиционного СП ЦОС является наличие n параллельных вычислительных трактов, которые функционируют независимо от друг от друга. В каждом из них реализуется ортогональные преобразования сигналов по соответствующему модулю. Распараллеливание на уровне операции позволяет отнести данный спецпроцессор к виду SIMD. Используя один поток команд, который одновременно поступает во все вычислительные тракты, вычислительное устройство реализует ортогональные преобразования согласно (17). Малоразрядность остатков, отсутствие обмена данных между вычислительными трактами, позволяет повысить производительность спецпроцессора по сравнению с классической архитектурой сигнальных процессоров. При этом для повышения точности вычислений достаточно увеличить число вычислительных трактов, т.е. увеличить число оснований ПСКВ.

Сравнительный анализ времени выполнения ортогональных преобразовании сигналов в позиционной системе (Т1) и с использованием параллельных вычислений (Т2) показан на рис. 2. Для оценки был выбран относительный коэффициент К=ТПСС/ТПСКВ.

gonc2.wmf

Рис. 2. Сравнительный анализ времени выполненияБПФ в ПСС (Т1) и в ПСКВ (Т2)

Анализ таблицы показывает, что применение ПСКВ позволяет повысить скорость цифровой обработки сигналов с использованием алгоритма БПФ более чем в 1,5 раза. Причем при увеличении разрядности обрабатываемых данных выигрыш возрастает. Так при обработке 64 разрядных данных скорость непозиционного процессора более чем в 2 раза превосходит скорость работы позиционного СП ЦОС, даже с учетом необходимости выполнения операций прямого и обратного преобразований кодов.

Заключение. В работе показана целесообразность использования параллельных вычислений для реализации ЦОС. Применение ПСКВ позволяет за счет независимой параллельной обработки малоразрядных остатков, позволяет сократить временные затраты на выполнение ортогональных преобразований сигналов по сравнению с позиционным спецпроцессором цифровой обработки сигналов.