Устройство для вычисления коэффициентов разложения функции

 

Изобретение относится к области вычислительной техники и предназначено для вычисления спектральных коэффициентов разложения функции в дискретном базисе. Цель изобретения - упрощение устройства за счет разложения функции на основе теплицевой матрицы. Устройство содержит регистр , сумматор двух n-разрядных чисел, счетчик, элемент И-НЕ, две группы элементов И, n-разрядный информационный вход, вход синхронизации, n-разрядный выход, вход начальной установки. Принцип действия устройства основан на использовании дискретной системы базисных функций LQ.k). образующей базис в пространстве RN, J,k 0,N-1. Эта система представляет собой нижне-треугольную теплицевую матрицу, элементы которой, включая главную диагональ , равны единице. 1 ил. (Л С

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (я). G 06 F 15/332

ГОСУДАРСТВЕ НЮЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4906831/24 (22) 30.01.91 (46) 30.06.93, Бюл. М 24 (72) А.A,Àðòþøèí, Н.В.Нечаев, А.H.Ñåìàøко, В,АЯапицкий и О.Н.Липчанский (56) Авторское свидетельство СССР

М 881761, кл. G 06 F15/332,,1980.

Авторское свидетельство СССР

hL 962974, кл. 6 06 F 15/332, 1981.

Авторское свидетельство СССР

t+918952, кл. G06F 15/332, 1980(прототип), Садыхов P.Х., Чеголин П.M., Шмерко

В.П. Методы и средства обработки сигналов в дискретных базисах. Минск: Наука и техника, 1987.

Шило В.Л. Популярные цифровые микросхемй. Справочник. — М.: Радио и связь, 1987, Залманзон Л.А. Преобразования

Фурье, Уолша, Хаара и их применение в управлении, связи и других областях . — M,:

Наука, 1989.

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

Цель изобретения - упрощение конструкции устройства за счет разложения функции нв основе теплицевой матрицы.

„„5lJ „„1 824641 А1 (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КОЭФФИЦИЕНТОВ РАЗЛОЖЕНИЯ ФУНКЦИИ (57) Изобретение относится к области вычислительной техники и предназначено для вычисления спектральных коэффициентов разложения функции в дискретном базисе.

Цель изобретения — упрощение устройства за счет разложения функции на основе теплицевой матрицы. Устройство содержит регистр, сумматор двух и-разрядных чисел, счетчик, элемент И-НЕ, две группы элементов И, и-разрядный информационный вход, вход синхронизации, и-разрядный выход, вход начальной установки. Принцип действия устройства основан на использовании дискретной системы базисных функций

l4,k), образующей базис в пространстве RN, J,k =Кй — 1. Эта система представляет собой нижне-треугольную теплицевую матрицу, элементы которой, включая главную диагональ, равны единице. 1 ил.

На чертеже представлена функциональная схема устройства.

Устройство содержит информационный вход 1, вход синхронизации 2, регистр 3, сумматор двух и-разрядных чисел 4, и-разрядный выход 5, элемент И-НЕ 6, счетчик 7, первую группу элементов И 81 — 8л, вторую группу элементов И 91 — 9n, вход начальной установки 10.

Принцип действия устройства основан на использовании дискретной системы базисных функций Ц),k} îáðàçóþùåé базис в пространстве R;J,k=О,NÈ.

N, Эта система представляет собой нижне-треугольную теплицеву матрицу, эле1824641 л1е»»ты которой, включая глаоlról0 диагОналь, равны единице:

1 О О О О, 1 1 О О О.

1 1 1 О О, 1 1 1 1 О.

1 1 1 !0

1 1 1 1 11

О О

О О

О О

О О, О О

О О

1 1 1 1 11 111111

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

:»»у;0;It . я:л Уо» ш": позволяет пастроигь бо!

1001 е Il б-»ст!?Одой»ству»ощие устрой. ", Ээ за счет простоты алгоритма

r вычислений.

Если в качестве оценки спектра мощное»и цен»! иро.»энного зргадического стациoiled!? I»oI.u случайного процесса

Иоr»C. ЬЗОВЭтЬ СООТНОШЕНИЕ:

1 "= .

:;01 =И Х (ЭР-0)). р ==о то процес- вычисления коэффициентов л»-, (j) разложения последовательности

I .(») = х((!с+ р) At)

3Р где ht — шэг дискретизации, р — номер циклического сдвига, сспдится к суммированию с накоплением ординат отсчетов х», !=-1,N, Обозначим ар 0) - cl, 35

Из описания используемой системы базисных функций следует, чта процесс вычисrI0r-:.;»я 0! можно записать таким Обрэзам, со = ха

С» = СО+ Х! 40

-,.g = с, »- х

Ci == CI-1+ Xl

С».-1 = СЛ1-г + ХЛ»-1

Устройство работает следующим образом.

В статическом режиме счетчик и регистр установлены в нулевое состояние сиг- 50 налом, подаваемым на вход 10 устройства.

На вход 1 устройства информация не поступает, Устройство готово к работе с N отсчетами исследуемой функции.

В динамическом режиме на вход 1 уст- 55 ройства поступают в двоичном коде отсчеты исследуемой функции с нулевого по (Й-1)-й, Одновременно с поступлением када каждоI.o отсчета на вход 2 устройства поступает синхроимпульс.

3, .ем разряды кодл 0?счета подаются на первые входы элем п»гов И первой группы 81-8, э синхроимпульс — I!a г»орвый вход элемента И-НЕ 6. С вг иода элемента И-НЕ

6 синхроимпульс»»осгупает»»а вход с»етчика 7, э также нэ вторые входы элемен»ов И первой группы ÎI — 8„и второй группы 91 — 9„. Эким образом, при приходе r!a вход устройства када отсчетл и синхроимпульса код отсчета через открытые синхроимпульсом элемен?ы И первой группы поступает на соо?ветствующио входы сумматора 4. С лыода сумматора результ;»» посгупае» на !1xalt регистра 3, а с выхг?дг регистра 3!I<". первые вхоДы элементов И в»ОРой гРУппы 91 9в и с выходов этих зле»ментов И и 1 воат в . òñi!I» ? l0щие входы сумматора. !,Роме того, выход сумматора соединен с вь»ход<»м ус?ройсгвэ

5, Гакил» образом, результаг суммирования записывается в регистр 3 и подается I»ý и разрядный выход 5 устройства. Записанный в регистр 3 результат суммирования складывается с кодом следующего отсчета поступэгощего на вход устройства од»»овременно со следующим синхраимпульсом. Счетчик после подачи на него И синхромпульсов вырабатывает с постуг?лениел» следующего имг»ульса сигнал перепал»»ения, кого!;ый подается на второй вход элемента И-НЕ 6, чr0 помяадит к закрытию соединен»»ь»х с выходом элемента И вЂ” НЕ 6 элементов И первой и второй групп и прекграще»»»»»0 поступления кодов слагаемых нэ вход r.yv; Iг»орэ 4. После обработки N отсчетов необходимо обнули?ь счетчик и регистр сигнллом, поступающим на rixolt 10 устройства, Сравним сложность заявляемого устройства и про»отипа. Сложность пр длагэемого устройства можно выразить чере-» необходимое для P о реал:.злции число лоГИЧЕСКИХ ВЕН ИЛЕй, .10r+0 СЛохгrl00r!, У:тРО;—

I? tвэ запишется следующим образок»:

Q == Qcr 1 2пОи + Огг+ О » Ои I«, где Ос„, — сл ж»»ость сумматора;

Ои — сложность элементэ И;

Qpr — сложность регистра;

Qc — сложность счетчика;

Ои-I-! E — сложность элемента И-Н Е, При этом и-разрядный комбинационный сумматор может содержать около 20п вентилей, такое же количество вентилей будет содержать регистр, Элементы И и И-НЕ содержат по 2 вентиля, m-разрядный счетчик (m = !Ощ!4) содержит 20fll вентилей. Тогда

q =-44п+20!092!4+ 2.

Сложность протогипа выразим аналогична:

Q - !4 Ос.4» N Ог;м лч Окол»и - О »лу

+ Ок+ Орг, (>à4()4 ) где 0c — сложность сум>(э гч а;

Q>(c)>.IhI СЛО)КНОСТЬ Kr)f«t>«tytaTQpa С N Ka нэпов на один; (((фу с)10)K>100òü Ге>!.. paropa фу)>кций

УОЛВ>а -РадЕМахвра;

Q, сло>кног (ь комму>аторэ >ах-;овых

И >1Г>УГ> ЬСО В:

Qp> — o!io;>(н;.,:;;! Ре>ис) Ра СД()III à;

Ос>1-. — Слож>>ость сумматора- вьi Ihtt а

f e>I(I.

Дл«1 >)асчетов при>1е>л, 1ТО (.1(. л1 — G(>a чч 2 ()(> ),.

Ор) " 20! ОЯ;) И

"()0 (:>(,(:, — () - 1Г" ()«1(>, 1,)гда () -= 40(Ч и i N.102 ((л> 10з, 0+ 201 о(1-, >",>.

Из -,рэсч>ениг> зь>ра,.ений длч g и г,"

BI1/1>to, что ((10:кг>ос>ь g<, (()Ойствэ и прототипа f)!)apaclat;)T с yf)(1(IHчением и и > (, причем с ростом и и N 0 увел>л>ивается знэчитель>!O t)Oj) I()(Чг>ë (t

Лпя It "): N -- 10."4 ук ены))ение сложIIoo((I AQ при г римен .I,v)II заявляемого ycTpoéсTaэ !1о срэвttåttию с прототипDì

I «(fал!1!.

/г1 (5- . 10. (:f);I(1>IvI бы(:т(к>дг:.гвие заявляемого устройств(и про(о>ипэ. Время Вычисления коэффициентов разложения для заявляемоГО устройства составит:

Т == ()>()(< м > Тр(1 tc)) 2t((t (И-НЕ), rÄÅ Tr» — ВРЕМЯ СложЕНИЯ ДВУХ Il-ÐaÇPßÄÍÛÕ операндов; (pr -- ВРЕМЯ ЗВПИСИ РЕЗУЛЬТЭГОВ СЛОжЕния в регистр: тсч - вРемЯ Работы с>етчикэ; ти — время срабатывания элементов И; ти-нг -- Время срабатывания элемента

И-НЕ, л)РЕ>1Я ВЫЧИ(ПЕНИЯ КозффИЦ!1ЕН (O() РЭЗ ложения для прототипа Определяется следующим образом:

Т = N(tpr > tc>q + tr4)y 1 Ткол>м + (сл(-эч), где tpr — время работы регистра сдвига;

Т л> — ВРЕМЯ СУММИРОВаНИЯ ДВУХ П-Раэрядных операндов: т(ф)(— время формирования функции

Уолшэ-Рэдемахера;

t, .1 — время переключения коммутатора с N каналов на один;

tcht-еч — ВРемЯ Работы СУмма,oPa — вычига Tenÿ.

Полагаем, что сумматоры в заявляемом устройстве и в (трототипе одинаковой конст5

РМКЦИ>Л, 1. ). I(." ))„!л "1О I!1)б)лл) )!,". " >1 (;;;)

f 1 P! C Н >) 1 11 ) >) 1 f (; * 1;.) (i i (j Г (! !: 1 I ) 1 I 1 ) < " 1 Л

>Н Ьl >И l 1 В (,;, -. t "." 1 (i М :, .

И с х О Jl я и 3 и 3 Г е г 1 и ы " >). О > I с .T ("(к ц l " ) 1 (t . .) > е ;- >т«,) > ) «, У>>кЦии ) Оп>1>» (ВД".лл;) (1,1 1, >1«+;"

>io,. Ве(:-;;дать, ч(О (,-.-,:. -„" 1р(. (. л О д О В а (с л 1) и О ., TI > s v r i) t I t t I В б >ч с Г (О,((г) >1ствии заявляемого устроистгэ rin сравне ! i И 10 С )! p O T(j T >(I П Г) М AT г. О,.- Э В V: Т: (X(=- (— T .=.(((т„, <-т,4,у („„.;)ь

Таким образом. предла(аемое угтройстВО ПрОИЭ>".ОдИТ тах .КЕ, Как И ПрототИП, IttiЧ И С Л Е Н И Е К О З ф ФИ Ц >л Е 1-1 т О В Р Э З Л О ж Е и И Я функ»ии, Обладая при з(ом бо>1> (>)>л>л быстродействием и более прпс;ой конгтрукцией.

Предлагаемое уст()ойствп цепесообрэзно использорать при построении ctteqv роцегсopor) обработки сигналов и изображений В реальном >1ас>>1(лбе. Времени для ое(пе»ия задач спекl()лл>.>!I)fn анализа. Реализация данного устройства на основе инте>рально(л технологи(1 п()зяолит увеличить быстроцеиствле си(:т(1>л цифроВой обработки, э тэкл".о поныси>ь rex>!ОпоГИЧНОСT . (..()V1(.: За СЧЕТ (tpnCTn T>j г, Ip;(KTVptd усгроис-)>э, что ft свело О: .р. ль, О(.егпе)>(1т ув(-лИЧЕ> ИЕ ПГ>оцосс(1 ВЬ>;С)да Г(>Л>>ЫХ (4((>(П()И ИХ IlPO«\38(t)r(ot ЗС, Э Ta(.жЕ Сtiiiaitт Ь CTO имость устр )йгта» гР о р м 1(>1 а 1 з О б р е г е и и я

Устрой тво для Вычигления коэффициентов разложения фу>(кции, содер кащее ре(истр, сумматор двух и-разрядных чисел, птличак)щ(еся тем, to,сцел>по упрощения устройства за счет разложения функции на основе тепли>;,евой матрицы, оно содержит элемент И-НЕ, счетчик, ïoрвую и вторую группы элементов И, причем разряды Входа ус ()ой)ствэ подключены к первым Вх(;дл>л с()():. Сетстлу>о>дих злементОВ И пе()вой гр)(it Г1>», В1 op>.IB Входы котОрых подключены K Выходу .. (>емента И -HF, входу счетчика и Вторым Входам соответствующих элементов И второй группы, первь>е входы которь>х подключены h соответствующим выходам регистра, выходь> элементов И первой и второй гр, пп подключены K соответствующим Вхгдэм -.:,, h;atopa, Выход которого подключен к ьыходу устройства и входу регистра, )ход синхронизации устройства подключен к первому входу эле>лента И вЂ” НЕ, второй вход которого подключен к выходу переполнения счетчика, Входы обнуления счетчика и регистра >н)дилючены к входу начальной установки yot ройства.

1824641

Составитель А. Артюшин

Редактор С, Кулакова Техред М.Моргентал КоРРектоР М. Самборская

Заказ 2226 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская нэб., 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 1О1