Систолический процессор обобщенного дискретного преобразования

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 1)5 6 06 Р 15/3 ЕНИ ОБ ПИСА ИДЕТЕЛЬСТВУ АВТОРСКО киберн С.А тои ельство 32, 1986 льство 32, 1987 СССР ССОР РЕОБПРОЦ НОГО ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР(54) СИСТОЛИЧ ЕСКИОБОБЩЕННОГО ДИСКРАЗОВАНИЯ 1651295 А 1(57) Изобретение относится к автоматике и вычислительной технике и может быть использовано в высокопроизводительных системах цифровой обработки и сжатия иэображений, а также в системах спектрального анализа, Цель изобретения - расширение функциональных возможностей за счет обеспечения сжатия информации. Процессор содержит блок 1 из й (й - размер преобразования) регистров 2 сдвига, й арифметических блоков 3, обьединенных в матрицу 4, генератор 5 двумерных базисных функций, элемент б задержки, счетчик 7, дешифратор 8, сумматор 9, элемент 10 задержки и регистр 11. 4 ил., 1 табл.5 10 15 Изобретение относится к автоматике ивычислительной технике и может быть исПользовано в высокопроизводительных системах цифровой обработки и сжатияиэобракений, а также в системах спектрального анализа.Целью изобретения является расширение функциональных возможностей путемВыполнения сжатия информации.Дискретное двумерное обобщенноепреобразование можно выполнять используя двумернь 1 е функции Виленкина-Крестенсона (ВКФ), При этом коэффициент Ь,матрицы преобразования Е вычисляетсяследующим образом:И - а - 1п 1 П =, 81 а)=о=огде аЧ = (А 1 Ч, ХЧ = Рщ 1)Ч;Ьпп = Ч(в,п,х,у) С(Ч(а,х)М(п,у; а,п = О,И;А - матрица отсчетов сигнала;Яп - матрица значений двумерной функции;Ч(а,х), Ч(п,у) - ВКФ по соответствующим координатам.Двумерные ВКФ можно представить вудобном для их формирования виде:Ч(в,п,х,у) =- Ч(в,х)8 Ч(п,у), (2)гдеРд, - символ Кронекеровского произведения,Система ВКФ Ч(сп,х), определяемаяобычно на конечном интервале М = Р, приР = 2 включает фукнции Уолша, приР = К(а =1) - дискретныеэкспоненциальные функции. Аналитически ВКФ могутбыть получены как произведение соответствующих обобщенных функций Радемахера:аЧ(а,х) = П (Х(Кх)1 ф (3)В свою очередь обобщенные функцииРадемахера определяются следующим соотношением:Р ) еРР епс (х/Р"ца рНа фиг.1 представлена структурная схема процессора; на фиг.2 и 3 - структурныесхемы соответственно арифметическогоблока и генератора двумерных базисных 20 25 30 35 40 50 функций; на фиг,4 - первые шестнадцать двумерных функций Фурье,Систолический процессор дискретного обобщенного преобразования содержит (фиг.1) блок 1 сдвиговых регистров 2, арифметические блоки (АБ) 3 линейной матрицы 4, (цифровой) генератор 5 двумерных базисных функций, первый элемент б задержки, счетчик 7 (импульсов), дешифратор 8 (с импульсным выходом), сумматор 9, второй элемент 10 задержки, регистр 11, группу информационных входов 12, входы 13 и 14 номера функции, вход 15 запуска, тактовый вход 16, вход 17 кодов функции, информационный выход 18 и выход 19 синхронизации,АБ 3 (фиг,2) содержиг умножитель 20, сумматор 21 и регистр 22,Цифровой генератор 5 двумерных базисных функций (фиг,3) содержит элемент 23 задержки, блоки 24 и 25 постоянной памяти (ПЗУ), регистр 26, умножитель 27 и сдвиговые регистры 28 и 29.На фиг.4 символами ЧЧ показаны соответствующие приведенные значения двумерных тригонометрических функций, где Я = ехр( - ) /М). При этом сама функцияг.7 где(в,п,х,у) находится на пересечении столбца, определяемого функцией беев,х), и строки, определяемой функцией бе 1(п,у),Б таблице представлена диаграмма работ каждого АБ в различные временные такты при вычислении одного коэффициента преобразования для размерности равной 4.Процессор работает следующим образом,Вначале производится настройка генератора 5 на требуемый базис ВКФ, Зто осуществляется путем последовательной подачи на входы 13 и 14 двоичных кодов номеров в,п функций выбранного базиса ВКФ (например, Фурье, где гп,п = 0,М), на вход 17 - значений функций, а на вход 15 - соответствующих управляющих сигналов для записи информации. При этом двоичные коды являются адресами, Так как обработка двумерных сигналов (иэображений) обычно осуществляется "окном" небольшой размерности, то этот процесс не требует значительных временных затрат,Затем на группу входов 2 последовательно подаются соответствующие значения исходных данных аф,) =- 1 У), на входы 13 и 14 - коды номеров требуемой двумерной функции бей,п,х,у), а на вход 15 - сигналы запуска генератора (сигналы считывания информации). На вход 16 процессора подаеся (2 М) тактовых импульсов. Рас 16512955 10 столбец э 1 э,агэ,азз,а 4 з данных, нэ выходы ли 50 55 смотрим работу устройства для случая Мх 1 ч=- 4 х 4 при п 1 = 3 и п = 1.По первому тактовому импульсу значения первого столбца данных а 11,а 21,аз 1,а 41 заносятся в соответствующие 1-разрядные регистры 2 сдвига блока 1. которые осуществляют задержку на (1-1) такт, где 1 - номер выхода блока 1 (а следовательно, и номер регистра 2), В результате только на первом выходе блока 1 появляется а 11, а на остальных выходах будет сигнал "0". Одновременно только на первом выходе генератора 5. появляется Яп = ЧЧо (фиг,4), а на остальных выходах - "О". АБ 3 линейной матрицы 4 работают в соответствии со следующим рекурсивным алгоритмом:С 1". = С 1". "+ ац . Я), (5) где Е - номер шага вычислений, Ц = 1,4. При этом С = О. Следовательно, в АБ 31 (см.таблицу) будет найдено произведение1а 11 ЧЧО = С 1, которое поступает в АБ 32,Одновременно тактовый импульс проходит элемент 6 задержки и записывается в счетчик 7, осуществляющий подсчет поступающих импульсов, а также приходит на вход записи регистра 11, Так как в исходный момент содержимое регистра 11 оавно нулю, на вход сумматора 9 поступает "О". На другой вход суммматора 9 одновременно поступает сигнал "0 с выхода АБ 34, и поэтому на выходе сумматора 9 значение "0", которое перезаписывается в регистр 11 тактовым импульсом,По второму тактовому импульсу в блок 1 записываются значения второго столбца данных а 12,агг.азг,а 42. Одновременно нэ выходах блока 1 появляются а 12 и а 21, а на выходах генератора 5 - значения функции 312 = ЧЧз и 521 = ЧЧ 1 (фиг.4).АБ 32 вцчисляет С 1= С 1+ а 21 ЧЧ 1, а АБ 31 - С 3= д 12ччз (см,таблицу).По третьему тактовому импульсу в блок 1 сдвиговь 1 х регистров записывается третий нейной матрицы 4 поступают очередные значения а 1 з,а 22,аэ 1 и соответственно 51 з = =ЧЧ 2, 522 = ЧЧО, ЯЗ 1 = ЧЧ 2, АБ 3 матрицы раба- тают в соответствии с (5) и вычисляют Сз = = Зз 1 ВЬ;Сг г= С 21+ агг И/о: С 1 = С 11+ аз 1 ЧЧ 2(см.таблицу),По четвертому импульсу в блок 1 заносятся данные а 14,а 24,аз 4,44 четвертого столбца, а на его выходах появляются д 14,82 з,дзз,э 41, Одновременно на выходах генератора 5 формируются з 14 = ЧЧ 1; з 2 з = = Из зз 2 = ЧЧ 1 и 3 41 =. Юз, ( см, фиг. 4). АВ 31" ЗзвычисляютсоответственноС 4=а 14 ЧЧ 1; 15 20 25 30 35 40 45 Сз = Сз+ агз ЧЧз; Сг = Сг+ азг ЧЧ 1, а АБ 34 находит значениеС 1 = С 1+ а 41 ЧЧз (см.таблицу). Вычисленное значение С 1 проходит сумматор 9 без изменения(так как на второй вход сумматора 9 поступает "0" с выхода регистра 11) и записывается в регистр 11 тактовым импульсом с выхода элемента 6 задержки. Задержка на элементе 6 необходима для того, чтобы вычислительный процесс в сумматоре 9 оканчивался раньше, чем осуществится запись результата в регистр 11, Таким образом, за первые М тактов (М = 4) происходит вычисление суммы произведений С 1 соответствующих элементов первого столбца исходных данных ап и первого столбца значений двумерной функции Ь 1. Вычисление тяп в соответствии с (1) осуществляется теперь следующим образом;: : С 1.(6)1 - 1где,1 - номер столбца.С каждым последующим тактовым импульсом происходит вычисление последующих сумм произведений остальных столбцов исходных данных и двумерной функции Сг,Сз,С 4 (см.таблицу), При этом осуществляется накопление результатов в регистре 11, т.е, вычисление 1 пп.Как только счетчик 7 подсчитает (2 М - 1) тактовых импульсов, то на выходе подключенного к нему дешифратора 8 появляется импульс, который поступает на выход 19 и сигналуэирует о получении в регистре 11, э следовательно, и на выходе 18 процессора необходимого коэффициента преобразования, определяемого двумерной функцией с 1 е 1(гп,п,х,у). Одновременно импульс с выхода дешифратора 8 поступает на вход элемента 10 задержки и, появившись на его выходе, производит установку в исходное состояние ("0") счетчик 7 и регистр 11. Задержка нэ элементе 10 необходима для считывания результата с выхода регистра 11 до его установки в исходное состояние, Процессор готов к вычислению новых коэффициентов.Аналогичным образом вычисляются другие коэффициенты двумерного преобразования Фурье, а также коэффициенты преобразования в других базисах ВКФ.Блок 1 сдвиговых регистров работает следующим образом.Тактовыми импульсами информация а,1 с входа 12 заносится и сдвигается в регист" рах 2, число разрядов в которых соответствует номеру регистра 2. При этом исходные5 10 15 20 25 30 35 40 45 50 55 данные а поступают на вход последовательного ввода информации в регистр 11 (т.е. занесение осуществляется путем сдвига на один разряд), а процесс сдвига производится по переднему фронту тактового Импульса, Так как регистр 21 имеет один разряд, регистр 22 - два разряда и т,д., то регистр 21 не производит задержки инфорчации, регистр 22 осуществляет задержку а один такт, регистр 2 з - на два такта и т.д. , оэтому по первому тактовому импульсу информация появляется только на выходе регистра 21, а следовательно, только на первом выходе блока 1. По второму импульсу появляется информация и на втором выходе блока 1 и т.д.АБ 3 работает следующим образом.На входы умножителя 20 поступают а) ,и Я, последний производит их перемножение, а результат произведения поступает на ,один из входов сумматора 21, на второй вход которого подается результат вычисления (5) из АБ Зь 1. Полученная сумма с выхода ,сумматора 21 записывается в регистр 22 по заднему фронту тактового импульса (того ,тактового импульса, под действием которого в АБ 3 поступили соответствующие а,зи ). Генератор 5 работает следующим образом.В режиме настройки на вход 17 поступают значения заданных базисных функций, а на входы 13 и 14 - двоичные коды номеров функции, служащие одновременно адресами для записи информации в электрически программируемые ПЗУ 24 и 25, Так как базисные функции фп,х) и Ч (п,у) имеют одинаковые значения (для функции с одинаковыми в,п), то занесение информации осуществляется одновременно по одинаковым адресам в оба ПЗУ (по одной шине 17) управляющими сигналами по входу 15. При этом адреса последовательно увеличиваются, а функции Ч(в,х) и Ч(п,у) записываются соответственно в ПЗУ 25 и 24,В режиме генерации требуемой двумерной функции Н(в,п,х,у) по двоичным кодам щ и и на выходах 13 и 14 например. бе(3,1,х,у сигналами считывания информации (запуска генератора) на входе 15 осуществляется выборка значений соответствующих функций например, бет(3,х) и бет(1,у). Значения функций по установочным входам заносятся в соответствующие регистры 29 и 26. При этом для функции де 1(3,х) в регистр 29 будут записаны значения ЧЧО,ЧЧз,ЧЧ 2,ЧЧ 1, а для функции бет(1,у) в регистре 26 будут ЧЧо,ЧЧ 1,Ю 2 МЧэ. С выходов регистра 26 значения функции бет(1,у) поступают на входы умножителей 27, на другие входы которых поступает первое значение (ЧЧо) функции бе 1(3,х) с выхода регистра 29. На выходах умножителей 27 в соответствии с (2) формируется первый столбец двумерной функции бе 1(3,1,х,у); ЧЧоЧЧ Ю 2 ЧЧз) (см. фи г.4),По переднему фронту первого тактового импульса полученные значения первого столбца функции бе 1(3,1,х,у) записываются в регистры 28.Регистры 28 имеют такую же 1-разрядную структуру, как и регистры 2 блока 1, и работают аналогичным образом. Поэтому по первому импульсу на выходах генератора 5 появляется только первое значение первого столбца (ЧЧо), Одновременно первый тактовый импульс поступает на вход элемента 23 задержки, появившись на его выходе, производит сдвиг содержимого регистра 29 в сторону младшего разряда (в сторону выхода), В результате на выходе регистра 29 появляется второе значение (ЧЧз) функции бе(3,1,х.у), Задержка на элементе 23 необходима для того, чтобы осуществить запись результатов в регистры 28 прежде, чем появится новое значение функции бе 1(3,1,х.у) на входе регистра 29, На выходе умножителей 27 появляется второй столбец функции бе 1(3,1,х,у): ЧЧзЧЧоЧЧЧЧ 2) (фиг,4), который заносится в регистры 28 вторым тактовым импульсом, На выходах регистра 28 появляются значения ЧЧЗ,ЧЧ 1 функции бей(3,1,х,у), требуемой двумерной функции (фиг,4), значения которых последовательно появляются на выходах регистров 28.Аналогичным образом формируются другие функции де 1(е,п,х,у), а также функции в других базисах ВКФ.Формула изобретения Систолический процессор обобщенного дискретного преобразования, содержащий блок сдвиговых регистров,й (И - размер преобразования) арифметических блоков, сумматор и регистр, причем 1-й ( = 1 Я) выход блока регистров подключен к первому информационному входу 1-го арифметического блока, выход )-го= 1,М - 1)-го арифметического блока подключен к второму информационному входу+ 1) = го арифметического блока, выход й-го арифметического блока подключен к первому входу сумматора, 1-й информационный вход блока сдвиговых регистров является 1-м информационным входом группы процессора, тактовым входом которого являются соединенные между собой тактовые входы арифметических блоков и блока регистров, о т л и ч а ю щ и й с я тем, что. с целью расширения функциональных возможностей путем обеспечения сжатия информаиг. 3 ции, в него введены два элемента задержки, счетчик, дешифратор и генератор двумерных базисных функций, выход 1-й функции которого подключен к входу задания коэффициентов 1-го арифметического блока, вы ход первого элемента задержки подключен к входу разрешения записи регистра и счет ному входу счетчика, информационный выход которого подключен к входу дешифратора, выход которого является вы ходом синхронизации процессора и подключен к входу второго элемента задержки, выход которого подключен к установочным входам счетчика и регистра, выход которого является информационным выходом процессора и подключен к второму входу сумматора, выход которого подключен к информационному входу регистра, вход первого элемента задержки соединен с тактовым входом генератора двумерных базисных функций и подключен к тактовому входу процессора, первым и вторым входами номера функции и входом кодов функции которого являются соответственно первый и второй входы номера функции и вход кодов функции генератора двумерных базисных функций, вход запуска которого является входом запуска процессора.