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

(19) .(11) 3(51) 0 06 Г 15/332 ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ОПИСАНИЕ ИЗОБРЕТЕНИ: . .К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(71) Харьковский институт инженеровжелезнодорожного транспортаим, С,М,Кирова(56) 1. Авторское свидетельство СССРФ 578623, кл. 0 06 Р 15/332, 1977.2. Авторское свидетельство СССР ;484523 кл. 6 06 Г 15/332, 1975(прототип),(54)(57).УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯКОЭФФИЦИЕНТОВ ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ХААРА, содержащее блок формиро"вания режимов, первый и второй сумматоры-вычитатели, первый и второйэлементы И, сдвиговый регистр, о тл и ч а ю щ е е с я тем, что, сцелью сокращения оборудования, оносодержит первый и второй блоки памяти, первый и второй счетчики, первый й второй элементы задержки,коммутатор и элемент ИЛИ, информационный выход первого счетчика подключен к адресному входу первогоблока памяти и входу коммутатора,выходы которого соединены с соответствующими входами элемента ИЛИ, выход которого. подключен к счетномувходу второго счетчика, первым входам первого и второго элементов Ии входу первого элемента задержки,выход которого подключен к первомувходу первого сумматора-вычитателя,выход которого соединен со вторымивходами первого,и второго элементовИ и первым входом второго сумматора-вычитателя, второй вход которогоподключен к информационному выходусдвигового регистра, информационный1вход которого объединен со вторым входом первого сумматора-вычитателя и подключен к информационному выходу первого блока памяти, информа-,. ционный вход которого является информационным входом устройства и соединен с информационным выходом второго блока памяти, информационный вход которого. подключен к выходу первого элемента И, адресный вход и вход считывания второго блока памяти подключены соответственно к информационному выходу второго счетчика и выходу второго элемента задержки, причем блок формирования режимов содержит счетчик, дешифра" тор и распределитель импульсов, ин-. формационный выход счетчика блока Е формирования режимов соединен со входом дешифратора, выходы которого соединены со входами распределителя импульсов, первый выход которого подключен к счетному входу первого счетчика, второй выход распределителя импульсов соединен со входами сброса первого и второго. счетчиков и второго сумматора-вычитателя, третий выход распределителя импуль сов подключен к управляющему входу первого сумматора-вычитателя, чет,вертый выход распределителя импульсов соединен со входом второго элемента задержки и входом записи первого блока памяти, пятый выход распределителя импульсов подключен к управляющим входам сдвигового регист ра и второго сумматора-вычитателя, шестой выход распределителя импульсов соединен с третьими входами первого и второго элементов И, при этом выход второго сумматора-вычитателя и выход второго элемента И являются соответственно первым и вторым информационными выходами устройства, а счетный вход счетчика блока формирования режимов является тактовым входом устройства.На фиг. 1 представлена блок-схе-40 ма устройства для вычисления коэффициентов дискретного преобразования Хаара; на фиг. 2 - Функциональная схема блока формирования режимов; на фиг. 3 - временная диаграм ма его работы.Устройство содержит блок 1 Форми-.рования режимов, первый счетчик 2,первый блок 3 памяти, первый сумма-тор-вычитатель 4, коммутатор 5,элемент ИЛИ 6, первый элемент Й 7,второй счетчик 8, второй блок 9 памяти, сдвиговый регистр 10, второйсумматор-вычитатель 11, второй элемент И 12, регистрирующий блок 13,первый элемент задержки 14, второйэлемент задержки 15, счетчик 16блока 1,дешифратор 17, разделитель-ные диоды 18 (распределитель импуль-.=сов), выходы 19 блока 1. элементов И и первым входом второго сумматора-вычитателя, второй входкото"рого подлкючен к йнформационномувыходу сдвигового регистра, информационный вход которого объединенсо вторым входом первого сумматоравычитателя и подключен к информационному выходу первого блока памяти,информационный вход которого является информационным входом устройст,ва и соединен с информационным выходом второго блока памяти, инфор 60,довательного алгоритма быстрого преобразования Хаара. Пусть задан65,вектор размерности М входных данных Изобретение относится к вычислительной технике и обработке случайных процессов и может быть использовано в специализированных вычислителях быстрых преобразований.Известно, устройство для вычисления коэффициентов Хаара, содержащее генератор тактовых импульсов, комму татор, блок селекции и распределения, инверторы, резисторы, интеграторы, регистрирующий блок, блокуправления 1 Д,Недостатками известного устройства являются наличие таких сложныхблоков как интеграторы, а такжебольшое число используемого обору, дования,Наиболее близким к предлагаемому является устройство, содержащеепреобразователь аналог-цифра, сумматор-интегратор, сдвиговые регистры,сумматоры, работающие на суммирование, сумматоры, работающие на вычитание, элементы И, блок синхронизации 2,Недостатком данного устройстваявляется сложность в изготовлении,т.е. большое число используемогооборудования.Цель изобретения - сокращениеоборудования. Поставленная цель достигается тем, что устройство для вычисления коэффициентов дискретного преобразования Хаара, содержащее блок формирования режимов, первый и второй сумматоры-вычитатели, первый и второй элементы И, сдвиговый регистр, содержит первый и второй блоки памяти первый и второй счетчики, первый и второй элементы задержки, коммутатор и элемент ИЛИ, информационный выход первого счетчика подключен к адресному входу первого блока памяти и входу коммутатора,выходы которого соединены с соответствующими входами элемента ИЛИ,выход которого подключен к счетному входу второго счетчика, первымвходам первого и второго элементов. И и входу первого элемента задержки, выход которого подключен кпервому входу первого сумматора-вычитателя, выход которого соединенсо вторыми входами первого и второго 5 10 15 20 25 30 35 мационный вход которого подключенк выходу первого элемента И, адресный вход и вход считывания второгоблока памяти подключены соответственно к информационному выходу второго счетчика и выходу второго элемента задержки, причем блок формирования режимов содержит счетчик, дешифратор и распределитель импульсов,информационный выход счетчика бпокаформирования режимов соединен совходом дешифратора, выходы которогосоединены со входами распределителяимпульсов, первый выход которогоподключен к счетному входу первогосчетчика, второй выход распределителя импульсов соединен со входамисброса первого и второго счетчикови второго сумматора-вычитателя, третий выход распределителя импульсовподключен к управляющему входу первого сумматора-вычитателя, четвертый выход распределителя импульсовсоединен со входом второго элемента задержки и входом записи первого блока памяти, пятый выход распределителя импульсов подключен куправляющим входам сдвигового регистра и второго сумматора-вычитателя,шестой выход распределителя импульсов соединен с третьими входамипервого и.второго элементов И, приэтом выход второго сумматора-вычитателя и выход второго элемента Иявляются соответственно первым ивторым информационными выходами уст-ройства, а счетный вход счетчикаблока Формирования режимов являетсятактовым входом устройства. Приведем рекуррентные соотношения, позволяющие вычислять коэффициенты Хаара с использованием послех;. Запишем выражение для обобщенных промежуточных сумм преобразования Хаара в видеЯ1 5 где п =1, 20 оМ;1, 2, Н/2"В выражении (,Ц значения х(О) представляют собой значения входного вектора дискретных данных, т.е. выборки исходной функции в дискретных точках времени. Учитывая (1), определяем коэффициенты быстрого преобразования Хаара в виде(2)е- где и) = 1, 2, 1 оГН,= 2 а для правой части выражения (2) 1 И=111- 1, М = 21" 1. 2=х+хЗаметим, что коэффициенты С ввыражении (2) получаются не нормированными. Этот факт можно учесть присинтезе, т.е. доумножать их на(3), записываем более подробно выЧисление коэффициентов для й = 8.(21, (г 1 С (о) (о 1С - х(21 - х(1 С 1 - ,с(1 - (юъ4 м г8Число операций типа сложения-вычитания дЛя определения С, равно14 (4), (,5) и (б) и в. общем случаесоставляет 2 й) .Предлагаемое устройство работает следующим образом.дискретные значения исходной функции поступают на информационный . вход первого блока 3 памяти и хранятся в нем, т.е. по первому адресу хранится первый отсчет, по второму - второй и т.д. С первого выхода блока 1 в первый счетчик 2 поступает сигнал, т.е. его содержимое становится равным 001 )единице), По первому адресу из первого блоКа 3 памяти считывается значение х(о ипоступает на вход первого сумматора-вычитателя 4, на управляющем входе которого присутствует сигнал стретьего выхода блока 1. Таким образом, первый сумматор-вычитатель4 работает в вычитающем режиме. Впервый счетчик 2 добавляется единицаи его содержимое становится равным010 (двум), Из первого блока 3 паО мяти считывается значение х(о) игна выходе первого сумматора-вычитателя (4) образуется разность х(о)(а)- хг , Коммутатор 5 срабатывает,когда в первом счетчике 2 находится5 четное значение адреса, т.е. 2,4, , . Сигнал с выхода этогокоммутатора через элемент ИЛИ бпоступает на первый управляющийвход первого элемента И 7 и второгоэлемента И 12. На шестом выходеблока 1 при этом присутствует сигнал, который поступает на вторыеуправляющие входы этих элементов И.Заметим, что первый элемент И 7 сра 25 батывает тогда, когда на его второмуправляющем входе отсутствует сигнал, а второй элемент И 12 срабатывает, когда этот управляющий сигналесть.Таким образом, значение разности(о) (о)х , - х г с выхода первого сумматора-вычитателя 4 через открытыйвторой элемент И 1 2 поступает врегистрирующий блок 1 3 . Из (б) видно, что значение этой разности представляет собой коэффициент ХаараСигнал с выхода элемента ИЛИ бчерез второй элемент 1 5 задержкиустанавливает в " ноль " первый сум 40 матор-вычитатель 4, Второй сумматорвычитатель 1 1 заблокирован, так какотсутствует управляющий сигнал с пятого выхода блока 1 . В первый счетчик 2 опять добавляется единица и45 его . значение становится равным 0 1 1(трем). Из первого блока 3 памятисчитывается значение х 1, и процесс(а)формирования коэффициента С аналогичен описанному,. После получения50 коэффициента Сц 4 блок 1 со своеговторого выхода устанавливает схемуустройства в исходное состояние.На управляющем входе сумматора- вьг читателя 4 отсутствует сигнал стретьего зыхода блока 1 , т . е . сумматор- вычитатель 4 работает в режи ме суммирования , Сигнал с выходакоммутатора 5 (так как в счетчике 2 четный адрес) через элемент ИЛИ б поступает на первый вход первого элемента И 7, на втором входе которого отсутствует сигнал с шестого выхода блока 1. Таким образом, первый элемент И 7 открыт и значение промежуточной суммы х поступает по первому адресу во второй блок 9 памяти, так как во втором счетчике 8 записана единица с выхода элемента ИЛИ б. Этот же сигнал через второй элемент 15 задержки устанавливает в "ноль" первый сумматор-вычитатель 4. В первом сметчике 2 находится в это время значение третьего адреса (011), и считанное значение х поступает на сумматор-вычита" тель. Процесс обработки повторяется до тех пор, пока в первом счетчике 2 не будет двоичное значение, равное восьми (1000), т.е. адрес последнего х . Таким образом, во вто(ором блоке 9 памяти по первому адресу находится значение промежуточной суммы х, , по второму - х, и т.д. (4).Далее со второго выхода блока 1 схема устанавливается в исходное состояние, а управляющий сигнал с четвертого вьхода блока,1 переписывает содержимое второго блока 9 памяти в первый блок 3 памяти, Пичем содержимое четвертого адреса х" записывается по первому адресу первого блока 3 памяти, затем содержимое третьего адреса х записываетИэся снова по первому адресу х; первого блока 3 памяти, а значейия первого адреса этого блока 3 памяти предварительно переписываются по второму адресу и т.д. Таким образом, в первом блоке 3 памяти по первому адресу находится значение х, , по второму - хп и т.д. Влок 1 снова засылает в первый счетчик значение,(001 и из первого блока поочередно считываются значения х, , х и т,д., т.е. ормиру) (1ются промежуточные суммы х и х (5) . Как только значение первого счетчика 2 стает равным четырем (100), т.е. образуютсядве последние промежуточные суммы х й х блок 1 устанавливает схему в исходное состояние, а управляющий сигнал с его четвертого выхода переписывает содержимое второго блока 9 памяти в первый блок 3 памяти аналогично опиСанному. Так как по второму адресу второго блока 9 памяти нахо- . дится значение хф, то оно поступает по первому адресу первого блока З.памяти. Предварительно в этом блоке происходит последовательный сдвиг на один адрес в сторону увеличения его содержимого, т,е. в пер вом блоке 3 памяти, начиная с пер 55 ходах дешифратора 17 последователь 60 но появляются управляющие сигналы(сначала на первом, потом на втором и т.д,. Эти сигналы .через разделительные диоды 18 (распределитель импульсов) поступают на соответствую 65 щие выходы блока 1 и управляют рабо 5 10 15 20 25 30 35 40 45 50.вого адреса, находятся значения про:межуточных сумм в следующем порядке: хе х(2 хИ хи х" у хн), В пер 2 Гф .1 ф 3 ф, 4 ф вый счетчик 2 заносится единица (001) и из первого блока 3 памяти считывается значение х", которое поступает на вход первого сумматоравычитателя 4. В сдвиговый регистр 10 это значение на,заносится, так как отсутствует управляющий сигнал с пятого выхода блока 1, Затем в первом счетчике находится значение. два (010), и иэ первого блока 3 памяти считывается значение х, которое поступает на первый сумматорвычитатель 4. На пятом и третьем выходах блока 1 появляются управляющие сигналы, котоые позволяют занести значение х в сдвиговый регистр 10, а в первом сумматоре-вычитателе 4 получить разность х," " х,.т.е. коэффициент С(6), управляющий сигнал с шестого выхода блока 1 открывает второй элемент И 12,так как на его первом управляющем входе присутствует разрешаю-: щий сигнал с выхода элемента ИЛИ б, а в счетчике находится значение два 010), и коммутатор 5 срабатывает. С выхода второго элемента И 12 значение коэффициента Си поступает в регистрирующий блок 13, В сдвиговом регистре 10 происходит сдвиг влевоинформации на один разряд, т,е, умножение на два, и эта информация (2 х,) поступает на первый вход второго сумматора-вычитателя 11, на второй вход которого с выхода первого сумматора-вычитателя поступает значение разности (х, - х ) , Таким обра" зом, с выхода второго сумматора-вычитателя 11 снимается значение коэффициента Сщ (Со, = х - хо + 2 х 2 = = х + х) . В первый счетчик 2. заносится двоичное значение три(110) и,из первого блока 3 памяти считывается значение х 1, потом при значении в первом счетчике, равном четырем (100), считывается х" и на выходе первого сумматора-вычитателя ,4 формируется коэффициент С (6),По аналогичной схеме Формйруются остальные коэффициенты. После считывания последнего адреса, т.е. значения х, , блок 1 устанавливает схемму в исходное состояние,Режим работы устройства задает блок 1 (фиг. 2), Счетчик 16 работает в обычном счетном режиме. По мере изменения его содержимого на вы1061151 иг,Г той всего устройства. Временная диаграмма работы блока 1 приведенана фиг. 3. Таким образом, предлагаемое уст ройство требует рая своей реализации меньше оборудования,чемпрототип.1061151 Составитель А.БарановКелемеш ТехрадЛ,ИикешКорректор В.Бутяг4 едак филиал ППП "Патент", г. Ужгород, ул. Проектная, 4 аказ 10042/52ВНИИПИпо д113035 Тираж 706сударственногам иэобретениосква, Ж,Подписноекоыитета СССРи открытийушская наб., д. 4