Ways of implementing digital signal encoders using residues in the residue number system

Galanina Nataliya Andreevna Doctor of Technical Science Professor, Department of Mathematics and Hardware of Information Systems, Ulyanov Chuvash State University 428015, Russia, g. Cheboksary, Moskovskii pr-t, d. 15 galaninacheb@mail.ru Other publications by this author     Ivanova Nadezhda Nikolaevna 428015, g. Cheboksary, Moskovskii pr-t, d. 15 galaninacheb@mail.ru

Pesoshin Valerii Andreevich Doctor of Technical Science 420111, Kazan', ul. K.Marksa, d.10, galaninacheb@mail.ru

Существенную часть общих аппаратурных затрат цифровых устройств фильтрации и спектрального анализа в системе остаточных классов (СОК) составляют шифра­торы. Они преобразуют целые R-разрядные числа x(kT) в R_S-разрядные вычеты x_S(kT) по предварительно выбранным взаимно простым модулям N_S (S=`bar(1,nu)`). При этом критерием выбора способа реализации устройств кодированияявляется минимум функции F_ш = D_шt_ш, где D_ш – число двухвходовых логиче­ских элементов в шифраторе, t_ш – время кодирования ^{[2, 3]}. При реализации проекта на логических блоках в виде последовательно включенных матриц эле­ментов И и ИЛИ, либо их эквивалента в другом базисе исторически пер­вым было стремление минимизировать число логических элементов в схеме ^[5]. С переходом на интегральные схемы (ИС) и ростом уровня их инте­грации критерием аппаратурной сложности цифровых устройств (ЦУ) стала пло­щадь, требуемая для их размещения. Для ИС, реализуемых на кристалле, площадь измеряется в квадратных миллиметрах, а для устройств на печат­ной плате – числом корпусов в составе цифрового уст­ройства. Так как корпуса ИС отличаются размерами, то их следует приводить к некото­рым эквивалентным корпусам. Операции приведения соответствует оценка суммарной площади корпусов ЦУ по общему числу всех выводов корпусов ИС. Отсюда следует, что, во-первых, характеристикой сложности ИС является уровень интеграции, оцениваемый либо числом ба­зовых логических элементов, либо числом транзисторов, которые разме­щены на кристалле; а, во-вторых, между всеми перечисленными выше кри­териями сохраняется известная связь.

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

В связи с изложенным, в приведенных результатах исследований аппаратурные затраты для логических шифраторов выражаются количеством двухвходовых логических элементов, а для ППЗУ приводятся в виде ее ин­фор­мационной емкости в битах. «Битам» можно поставить в соответствие количество триггеров, а затем и транзисторов, пользуясь известными соотно­шениями, используемыми в микросхемотехнике:
1 ячейка памяти = 1 бит = 1 разряд = 1 триггер; 1 логический элемент = 4 – 6 транзисто­ров ^[4].

Возможно несколько способов кодирования в СОК. Пер­вый – моделирование алгоритма ^[1] :

`x_s(kT)=x(kT)-~|(x(kT))/N_s|~ N_slt=x(kT)>modN_s`

где `~|x|~` означает целую часть числа x, т.е. наибольшее целое число, не превос­ходящее x. Второй способ предусматривает со­вмещение функций АЦП и шифратора и применяется в автономных спец­процессорах. Мы остановимся на третьем методе: он используется при ра­боте устройств в СОК со стандартными магистралями традиционных устройств в позиционной системе счисления (ПСС). В таких системах шифраторы ШS переводят позиционный код в СОК. При этом ШS могут быть реализованы на ППЗУ и на логических схе­мах (для указания этого различия при реализации устройств кодирования бу­дет в дальнейшем использоваться термин «логический шифратор»).

При реализации шифраторов СОК на ППЗУ задача решается следующим образом: исходный код числа x(kT) является адресом заранее вычисленного и запрограммированного вычета x_S(kT); время кодирования составляет t_ш1 = t_ППЗУ. При реализации шифраторов на ППЗУ в качестве аппаратурных затрат можно рассматривать информационную емкость ППЗУ в битах. Так как разрядность чисел на входе ППЗУ равна R, а на выходе разрядность вычетов чисел в S-м канале СОК – R_S, то аппаратурные затраты для одного канала СОК вычисляются по формуле D_ш1 = R_S2^R (бит) ^[5]. В табл. 1 представлены значения D_ш1 для одного канала СОК.

Таблица 1

Аппаратурные затраты (D_ш1) для одного канала СОК, бит

Сократить аппаратурные затраты можно с помощью разбиения входного числа x(kT) на n частей. Очевидно, что:

`x_(s)(kT)<=sum_(i=1)^nx_s_i>modN_s, (2)`

где `x_S_i<=x_i2^((sum_(j=1)^(i-1)r_j))>modN_s ;`

r_i – разрядность i-й части числа x(kT), i =1, 2, …, n; r₀ = 0.

ППЗУ i-й части вычета x_S (x_Si) перепрограммируется в соответствии с (2). Его схема будет выглядеть следующим образом:

Рис. 2. Схема шифратора при разбиении x(kT) на две части

Аппаратурные затраты D_ш2 будут включать затраты на организацию памяти (D_ППЗУ = 2^(R/2+1)R_S бит), к которым добавятся затраты на логические схемы И (D_И = 2R_S + 1) и модульные сумматоры (`D_sum=14R_s+1`).

Кроме того, если `R/2<R_S` , то затраты на организацию памяти уменьшаются вдвое (D_ППЗУ = 2^R/2R_S), так как в этом случае «младшее» ППЗУ будет отсутствовать, а все «младшие» разряды x_мл = x_S1.

Временные затраты составят:

t_ш2=t_ппзу+2t_ср(R_s+4); t_ср=(t_зд0,1+t_зд1,0)/2, где

где t_ср – время срабатывания логической схемы (ЛС); t_зд0,1 и t_зд1,0 -

время задержки включения и выключения ИС.

Для случая разбиения x(kT) общие затраты D_ш2 приведены в табл. 2.

Таблица 2

Аппаратурные затраты (D_ш2) для схемы на рис. 2, бит

Примечание. * – этот случай связан с отсутствием «младшего» ППЗУ.

Следовательно, при использовании схемы (рис. 2) удается существенно сократить аппаратурные затраты на реализацию шифраторов: для R = 8, 10, 12, 16 – соответственно в 7,1; 15,5; 28,4; 124 (раза).

Проведенные исследования показали, что для значения вычета R_S ≤ 6 минимальное значение целевой функции F_ш = min гарантируют логические шифраторы, в которых преобразование R-разрядного входного числа x(kT) в его R_S-разрядный вычет происходит при использовании логических методов синтеза схем на основе матриц дизъюнкций и конъюнкций.

Исследования выявили периодичность вариантов и возможность логического вычисления остатков. Но такое решение допустимо для небольших значений модулей N_S = 5 (или N_S = 7) при R_S = 3, а как показывает практика, число разрядов R входной последователь­ности x(kT) бывает достаточно большим. В этом случае предлагается разбие­ние R на несколько частей с дополнительным введением сумматора (по аналогии со случаем с ППЗУ (рис. 2)). На рис. 3 представлена схема шифратора с логическими схемами LS (LS₁ соответственно для «младших» разрядов, а LS₂ – для «старших»).

Сумматор SM выполняется на логических двухвходовых элементах, число которых равняется 14R_S + 1. При его реализации обязательно учитываются знаки чисел, так как в СОК ` N=prod_(S=1)^nuN_s , `

а за "0" считается число N/2. Поэтому положительными будут числа `(N/2+R_i)N_s,`

а отрицательными, соответственно, числа `(N/2-R_i)N_s` .

Рис. 3. Схема логического шифратора
при разбиении входной последовательности на две части

Аппаратурные затраты F_ш шифраторов на логических схемах зависят от того, на сколько частей n по R_i разрядов делятся числа входной после­довательности x(kT). Например, 10-раз­рядное число L на входе логического шифратора (рис. 3) можно разбить на 3 числа:

L=l_ст+l_ср+l_мл ,

где l_ст = 3 (разряда); l_ср= 3 (разряда); l_мл = 4 (разряда).

При этом R_ст+R_ср+R_мл = R = R_общ; R_мл= R_s ^[3].

Проведенные исследования показали, что, во-первых, оптимальным является разбиение двоичного кода числа x(kT) на две части (n = 2); во-вторых, разбиение входной последовательности x(kT) на части нецеле­сооб­разно при разрядности чисел R < 8; в-третьих, R-разрядные входные числа делятся на старшую и младшую части (R_ст и R_мл), каждая из которых имеет разрядность, равную R/2.

Количество двухвходовых конъюнкторов, входящих в состав логиче­ских схем LS₁ (LS₂), определяется по формуле: D_и=R+2^R/2+13-`~|` 2^R/2/N_s`|~`,

а количество дизъюнкторов D_или устанавливается по таблицам истин­ности.

Для практически интересного случая R = 10 аппаратурные затраты пред­ставлены в табл. 3

Таблица 3

Аппаратурные затраты шифраторов на логических схемах

Модулярные сумматоры содержат 14R_S + 1 двухвходовых логических эле­ментов. Максимальное время сложения в них t_с = 2t_ср(R_S + 2), т.е. в два раза больше, чем у обычного накапливающего сумматора. Окончательно получим следующие формулы для подсчета аппара­турных и временных затрат: D_ш3 = 2D_LS + D_C; t₁ = 3t_ср + t_c = t_ср(7 + 2R_S).

Значения D_ш3 и t₁ для такого случая шифраторов приведены в табл. 4.

Таблица 4

Аппара­турные (D_ш3) и временные (t₁) затраты шифраторов

Следует отметить, что возможно дальнейшее упрощение таких логических шифра­торов и, как следствие, – сокращение аппаратурных затрат.

` `