Патент 1061151

Устройство для вычисления коэффициентов дискретного преобразования хаара

 

УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КОЭФФИЦИЕНТОВ ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ХААРА, содержащее блок формирования режимов, первый и второй сумматоры-вычитатели , первый и второй элементы И, сдвиговый регистр, отличающееся тем, что, с целью сокращения оборудования, оно содержит первый и второй блоки памяти , первый и второй счетчики, первый и второй элементы задержки, коммута,тор и элемент ИЛИ, информационный выход первого сч;етчика подключен к адресному входу первого блока памяти и входу коммутатора, выходы которого соединены с соответствующими входами элемента ИЛИ, выход которого подключен к счетному входу второго счетчика, первым входам первого и второго элементов И и входу первого элемента задержки, выход которого подключен к первому входу первого сумматора-вычитателя, выход которого соединен со вторыми входами первого.и второго элементов И и первым входом второго суммат.ора-вычитателя , второй вход которого подключен к информационному выходу .сдвигового регистра, информационный вход которого объединен со вторым входом первого сумматора-вычитателя и подключен к информационному выходу первого блока памяти, информационный вход которого является информационным входом устройства и соединен с информационным выходом второго блока памяти, информационный вход которого подключен к выходу первого элемента И, адресный вход и вход считывания второго блока памяти подключены соответственно к информационному выходу второго счетчика и выходу второго элемента задержки, при-чем блок формирования режимов содержит счетчик, дешифратор и распределитель импульсов, информационный выход счетчика блока формирования режимов соединен со (Л входом дешифратора, выходы которого соединены со входами распределителя импульсов, первый выход которого подключен-к счетному входу первого счетчика, второй выход распределителя импульсов соединен со входами сброса первого и второго счетчиков и второго сумматора-вычитателя, третий выход распределителя импульсов подключен к управляющему входу Ot) первого сумматора-вычитателя, чет .вертый выход распределителя импульсов соединен со входом второго элемента задержки и входом записи перСП вого блока памяти, пятый выход распределителя импульсов подключен к управляющим входам сдвигового регистра и второго сумматора-вычитателя, шестой выход распределителя импульсов соединен с третьими входами первого и второго элементов И, при этом выход второго сумматора-вычитателя и выход второго элемента И являются соответственно первым и вто&ым информационными выходами устройства, а счетный вход счетчика блока формирования режимов является тактовым входом устройства.

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

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

РЕСПУБЛИК (19) .(11) 3(51) 6 06 F 15/332

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPbITHA

ОПИСАНИЕ ИЗОБРЕТЕНИ :.". .

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

-. .,.@ -„, 1

Ю, (21) 3475114/18-24 (22) 26.07.82 (46) 15.12.83. Бюл. )) 46 (72 ) Ю.В. Соболев, П.Ф. Поляков, О.С.Попов и В.Г.Иванов (71) Харьковский институт инженеров железнодорожного транспорта им. С.М.Кирова (53) 681.32(088.8) (56) 1. Авторское свидетельство СССР

)) 578623, кл. 0 06 F 15/332, 1977.

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

)) 484523, кл. 0 06 F 15/332, 1975 (прототип). (54)(57).УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ

КОЭФФИЦИЕНТОВ ДИСКРЕТНОГО ПРЕОБРАЗОВАННН XAAPA, содержащее блок формирования режимов, первый и второй сумматоры-вычитатели, первый и второй элементы И, сдвиговый регистр, о т л и ч а ю щ е е с я тем, что, с целью сокращения оборудования, оно содержит первый и второй блоки памяти, первый и второй счетчики, первый и второй элементы задержки,. коммутатор и элемент ИЛИ, информационный выход первого счетчика подключен к адресному входу первого блока памяти и входу коммутатора, выходы которого соединены с соответствующими входами элемента ИЛИ, выход которого. подключен к счетному входу второго счетчика, первым входам первого и второго элементов И и входу первого элемента задержки, выход которого подключен к первому входу первого сумматора-вычитателя, выход которого. соединен со вторыми входами первого,и второго элементов

И и первым входом второго сумматора-вычитателя, второй вход которого подключен к информационному выходу .сдвигового регистра, информационный

1 вход которого объединен со вторым входом первого сумматора-вычитателя и подключен к информационному выходу первого блока памяти, информа-,. ционный вход которого является информационным входом устройства и соединен с информационным выходом второго блока памяти, информационный вход которого подключен к выходу первого элемента И, адресный вход и вход считывания второго блока памяти подключены соответственно к информационному выходу второго счетчика и выходу второго элемента задержки, причем блок формирования режимов содержит счетчик, дешифратор и распределитель импульсов, ин-. формационный выход счетчика блока Щ формирования режимов соединен со входом дешифратора, выходы которого соединены со входами распределителя импульсов, первый выход которого подключен к счетному входу первого счетчика, второй выход распределителя импульсов соединен со входами сброса первого и второго. счетчиков и второго сумматора-вычитателя, третий выход распределителя импуль: сов подключен к управляющему входу первого сумматора-вычитателя, чет.вертый выход распределителя импульсов соединен со входом второго элемента задержки и входом записи первого блока памяти, пятый выход распределителя импульсов подключен к управляющим входам сдвигового регист ра и второго сумматора-вычитателя, шестой выход распределителя импульсов соединен с третьими входами первого и второго элементов И, при этом выход второго сумматора-вычитателя и выход второго элемента И являются соответственно первым и вторым информационными выходами устройства, а счетный вход счетчика блока формирования режимов является тактовым входом устройства.

1061151

На фиг. 1 представлена блок-схе-

40 ма устройства для вычисления коэффициентов дискретного преобразования Хаара; на фиг. 2 — функциональная схема блока формирования режимов; на фиг. 3 — временная диаграм45 ма его Работы.

Устройство содержит блок 1 форми-. рования режимов, первый счетчик 2, первый блок 3 памяти, первый сумма- тор-вычитатель 4, коммутатор 5, элемент ИЛИ 6, первый элемент Й 7, второй счетчик 8, второй блок 9 памяти, сдвиговый регистр 10, второй сумматор-вычитатель 11, второй элемент И 12, регистрирующий блок 13, первый элемент задержки 14, второй элемент задержки 15, счетчик 16 блока 1,дешифратор 17,разделитель- ные диоды 18 (распределитель импуль-.= сов), выходы 19 блока 1.

60.довательного алгоритма быстрого преобразования Хаара. Пусть задан

65,вектор размерности 4 входных данных

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

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

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

Наиболее близким к предлагаемому является устройство, содержащее преобразователь аналог-цифра, сумма тор-интегратор, сдвиговые регистры, сумматоры, работающие на суммирование, сумматоры, работающие на вычитание, элементы И, блок синхрониза ции (2) .

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

Цель изобретения - сокращение оборудования.

Поставленная цель достигается тем, что устройство для вычисления коэффициентов дискретного преобразования Хаара, содержащее блок формирования режимов, первый и второй сумматоры-вычитатели, первый и второй элементы И, сдвиговый регистр, содержит первый и второй блоки памяти первый и второй счетчики, первый и второй элементы задержки, коммутатор и элемент ИЛИ, информационный выход первого счетчика под.-ключен к адресному входу первого блока памяти и входу коммутатора, выходы которого соединены с соответствующими входами элемента ИЛИ, выход которого подключен к счетному входу второго счетчика, первым входам первого и второго элементов . И и входу первого элемента задерж» ки, выход которого подключен к первому входу первого сумматора-вычитателя, выход которого соединен со вторыми входами первого и второго элементов И и первым входом второго сумматора-вычитателя, второй вход которого подлкючен к йнформационному выходу сдвигового регистра, информационный вход которого объединен со вторым входом первого сумматоравычитателя и подключен к информационному выходу первого 6лока памяти, информационный вход которого является информационным входом устройст ;ва и соединен с информационным выходом второго блока памяти, инфор5

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

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

k:2 -(5 где и =1, 2, ...,Иофй-1;

1, 2, ..., Н/2" °

В выражении Щ значения х

101 представляют собой значения входного вектора дискретных данных, т.е. выборки исходной функции в дискретных точках времени. Учитывая (1), определяем коэффициенты быстрого преобразования Хаара в виде

ceogI(+» <е, 1((> (2)

m-( где и(= 1, 2, °... log31, «3 = 2 а для правой части выражения .(2)

1, М = 2(- 1. 2 . Коэффициент С „ (свободный член) определяем как

С = х М((> + „(eog31- ()

=х„+х„, Заметим, что коэффициенты С ; в выражении (21 получаются не нормированными. Этот факт можно учесть при синтезе, т.е. доумножать их на (и 2 }..

Используя выражения (1), (2) и (3), записываем более подробно выЧисление коэффициентов для и = 8. ,Определяем промежуточные обобщенные,суммы (1} И=1(=1р2,...,й/2 х 1 = хю1 + хсо1 х" = хж1 + <

И для Il= 2 ,х =х®+х," (5) х(" = х(> + х "3 а 3

Тогда коэффициенты C определяются как

С = х91 + Р,С (= х," — х® . Сн — х(2) - хс 3 С3 — ч(" = (3

33 % ъ м г 8

Число операций типа сложения-вычитания для определения С,„ равно

14 (4), (5) и (б) и в. общем случае составляет 2 (й- 1) .

Предлагаемое устройство работает

„следующим образом. дискретные значения исходной функции поступают на информационный вход первого блока 3 памяти и хранятся в нем, т.е. по первому адресу хранится первый отсчет, по второму— второй и т.д. С первого выхода блока 1 в первый счетчик 2 поступает сигнал, т.е. его содержимое становится равным 001 (единице) . По первому адресу из первого блоКа 3 памяти считывается значение х о ив ( поступает на вход первого сумматора-вычитателя 4, на управляющем входе которого присутствует сигнал с третьего выхода блока 1. Таким образом, первый сумматор-вычитатель

4 работает в вычитающем режиме. В первый счетчик 2 добавляется единица и его содержимое становится равным

010 (двум). Из первого блока 3 памяти считывается значение х О и г на выходе первого сумматора-вычита» теля (4} образуется разность х 1 (а1 (- z> . Коммутатор 5 срабатывает, когда в первом счетчике 2 находится

5 четное значение адреса, т.е. 2, 4, . ° . . Сигнал с выхода этого коммутатора через элемент ИЛИ б поступает на первый управляющий вход первого элемента И 7 и второго элемента И 12. На шестом выходе блока 1 при этом присутствует сигнал, который поступает на вторые управляющие входы этих элементов И.

Заметим, что первый элемент И 7 сра25 батывает тогда, когда на его втором управляющем входе отсутствует сигнал, а второй элемент И 12 срабатывает, когда этот управляющий сигнал есть.

Таким образом, значение разности (о) <о1 х, - x с выхода первого сумматора-вычитателя 4 через открытый второй элемент И 12 поступает в регистрирующий блок 13. Из (б) видно, что значение этой разности представляет собой коэффициент Хаара

С3(Сигнал с выхода элемента ИЛИ б через второй элемент 15 задержки устанавливает в "ноль" первый сум40 матор-вычитатель 4. Второй сумматорвычитатель 11 заблокирован, так как отсутствует управляющий сигнал с пятого выхода блока 1. В первый счетчик 2 опять добавляется единица и

45 его-значение становится равным 011 (трем). Из первого блока 3 памяти считывается значение х >, и процесс (а( формирования коэффициента С аналогичен описанному.- После получения

50 коэффициента С34 блок 1 со своего второго выхода устанавливает схему устройства в исходное состояние ! (счетчики и сумматоры в "ноль") .

Затем в первый счетчик 2 снова

55 заносится единица (001) . Из первого блока 3 памяти считывается значение х(и поступает на сумматор-вычита(о) тель 4 . Затем считывается значение

l x, так как в первый счетчик 2 из (o7

60 блока 1 добавлена единица (0 1 0 ) . .иа управляющем входе сумматора- вь3 читателя 4 отсутствует сигнал с третьего зыхода блока 1, т . е . сумматор- вычитатель 4 работает в режи65 ме суммирования . Сигнал с выхода

1061151 коммутатора 5 (так как в счетчике

2 четный адрес) через элемент ИЛИ б поступает на первый вход первого элемента И 7, на втором входе которого отсутствует сигнал с шестого выхода блока 1. Таким образом, первый элемент И 7 открыт и значение промежуточной суммы х поступает по первому адресу во второй блок 9 памяти, так как во втором счетчике

8 записана единица с выхода элемента ИЛИ б. Этот же сигнал через второй элемент 15 задержки устанавливает в "ноль" первый сумматор-вычитатель 4. B первом сметчике 2 находится в это время значение третьего адреса (,011), и считанное значение

z + поступает на сумматор-вычитатель. Процесс обработки повторяется до тех пор, пока в первом счетчике

2 не будет двоичное значение, равное восьми (1000), т.е. адрес последнего х . Таким образом, во вто(о! ром блоке 9 памяти по первому адресу находится значение промежуточной суммы х !!, по второму - х и т.д.(4).

Далее со второго выхода блока 1 схема устанавливается в исходное состояние, а управляющий сигнал с четвертого вь!хода блока,1 переписывает содержимое второго блока 9 памяти в первый блок 3 памяти. Причем содержимое четвертого адреса х " записывается по первому адресу первого блока 3 памяти, затем содержимое третьего адреса х записывает« (М

3 ся снова по первому адресу z первого блока 3 памяти, а значейия первого адреса этого блока 3 памяти предварительно переписываются по второму адресу и т.д. Таким образом, в первом блоке 3 памяти по первому адресу находится значение х „", по второму - х", и т.д.

Влок l снова засылает в первый счетчик значение .(001) и из первого блока поочередно считываются значения х,, х и т,д., т.е. ормиру(i) О! ются промежуточные суммы х и х, (5) . Как только значение первого счетчика 2 стает равным четырем (100) т.е. образуются две последние промежуточные суммы х< и х блок 1 устанавливает схему в исходное состояние, а управляющий сигнал с его четвертого выхода переписывает содержимое второго блока 9 памяти в первый блок 3 памяти аналогично описанному. Так как по второму адресу второго блока 9 памяти нахо- . дится значение хф, то оно поступает по первому адресу первого блока

З.памяти. Предварительно в этом блоке происходит последовательный сдвиг на один адрес в сторону увеличения его содержимого, т.е. в пер вом блоке 3 памяти, начиная с пер55

65 щие выходы блока 1 и управляют рабо

50.вого адреса, находятся значения про:межуточных сумм в следующем порядке:. хЕ х(т! х14! х(х!" 1 хн) . В пер2 I L I .1 3, 4 вый счетчик 2 заносится единица (001) и из первого блока 3 памяти считывается значение х ", которое поступает на вход первого сумматоравычитателя 4. В сдвиговый регистр

10 это значение на,заносится, так как отсутствует управляющий сигнал с пятого выхода блока 1. Затем в первом счетчике находится значение. два (010), и иэ первого блока 3 памяти считывается значение х! !, которое поступает на первый сумматорвычитатель 4. На пятом и третьем выходах блока 1 появляются управляющие сигналы, кото ые позволяют занести значение х в сдвиговый регистр 10, а в первом сумматоре-вычитателе 4 получить разность х,"

- х,. т.е. коэффициент C«(6) . управляющий сигнал с шестого выхода блока 1 открывает второй элемент

И 12, так как на его первом управляющем входе присутствует разрешаю-: щий сигнал с выхода элемента ИЛИ б, а в счетчике находится значение два (010), и коммутатор 5 срабатывает.

С выхода второго элемента И 12 значение коэффициента С!! поступает в регистрирующий блок 13. В сдвиговом регистре 10 происходит сдвиг влево информации на один разряд, т.е. умножение на два, и эта информация (2х,) поступает на первый вход вто1 рого сумматора-вычитателя 11, на второй вход которого с выхода первого сумматора-вычитателя поступает BHaveние разности (x — х ), Таким обра" зом, с выхода второго сумматора-вычитателя 11 снимается значение коэффициента Сщ (C!!, = х, — х!," + 2х" =

= х „" + х " ) . В первый счетчик 2. заносится двоичное значение три (110) и .из первого блока 3 памяти считывается значение х!1!, потом при значении в первом счетчике, равном четырем 100), считывается х!" и на выходе первого сумматора-вычитателя .4 формируется коэффициент С (6} .

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

Режим работы ус трой с тв а з адает блок 1 (фиг. 2) . Счетчик 16 работает в обычном счетном режиме. По мере изменения его содержимого на выходах дешифратора 17 последовательно появляются управляющие сигналы (сначала на первом, потом на втором и т.д.). Эти сигналы .через разделительные диоды 18 (распределитель импульсов) поступают на соответствую1061151 фиг/ иг. той всего устройства. Временная ди-. аграмма работы блока 1 приведена на фиг. 3.

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

1061151

Составитель A.Áàðàíîâ

Редактор M.Êåëåìåø ТехрЕдЛ.Иикеш Корректор В.Бутяга

Заказ 10042/52. Тираж 706 Подписное

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

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

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4