Устройство для дискретных ортогональных преобразований
Изобретение относится к вычислительной технике и может быть использовано в специализированных системах обработки сигналови изображений высокой производительности. Цель изобретения - расширение функциональных возможностей за счет обработки в различных ортогональных базисах и выполнения многомерного дискретного преобразования Фурье. Поставленная цель
,4
Ф1
СОЮЗ COBETCHHX
СООИАЛИСТИЧЕСКИХ
РЕСПУБЛИК
„„SU„„1399764
ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ В, .:.:-: " ОПИСАНИЕ ИЗОБРЕТЕНИЯ H АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4165027/24-24 (22) 22.12.86 (46) 30.05.88. Бил. Ф 20 (71) Ленинградский институт точной механики и оптики (72) Г.А.Кухарев, В.С.Скорняков и А.И.Тропченко (53) 681.32 (088.8) (56) Аллен Ц. Архитектура вычислительных устройств. ТИИЭР, т. 73, 1985, У 5. Системы параллельной обработки/Под ред. Д.Ивенса, 11.: Мир, 1986,с; 416. (54) УСТРОЙСТВО ДЛЯ ДИСКРЕТНЫХ ОРТОГОНАЛБНЫХ ПРЕОБРАЗОВАНИЙ (5?) Изобретение относится к вычислительной технике и может быть использовано в специализированных системах обработки сигналов и изображений высокой производительности. Uesrb изобретения — расширение функциональных возможностей эа счет обработки в различных ортогональных базисах и выполнения многомерного дискретного преобразования урье. Поставленная цель 1399764 достигается благодаря тому, что в устройство введены информационные входы и 2, первая матрица .3 с вычислительными модулями 4 и выходом 5, дополнительные матрицы 6 с вычислиИзобретение относится к вычислительной технике и может быть использовано в специализированных системах обработки сигналов и изображений вы сокой производительности. Цель изобретения — расширение функциональных возможностей за счет обработки в различных ортогональных i базисах и выполнения многомерного дискретного преобразования Фурье, 10 На фиг.l представлена функциональная схема предлагаемого устройства; на фиг.2 - функциональная схема вычислительного модуля первой (систолической) матрицы; на фиг.3 — функ- 15 циональная схема вычислительного модуля второй систолической матрицы; ,на фиг.4 - функциональная схема ка нала блока конвейерных регистров. Устройство (фиг.l) содержит инфор- 20 мационные входы 1 и 2, первую систолическую матрицу 3 с вычислительными модулями 4 и выходом 5, m-1 дополнительных систолических матриц 6 с вы числительными модулями 7 и вторым 8 25 и третьим 9 входами, блок 10 из ш-1 конвейерных регистров, содержащий каналы 11 и выход 12,информационный выход 13 устройства и вход 14 синхронизации. 30 Вычислительный модуль 4 (фиг.2) содержит входы !5-17, регистры 18 и 19, умножитель 20, сумматор 21 и выходы 22-24. Вычислительный модуль 7 (фиг.З) 35 содержит входы 25-27, регистр 28, умножитель 29, сумматор 30 и выходы 31-33. Канал 11 (фиг.4) содержит вход 34, регистры 35 и выходы 36 н 37. 4р Устройство работает следующим образом, На вход 1 устройства поступают весовые множители вида тельными модулями 7 и входами 8 и 9, блок 10 конвейерных регистров, содержащий каналы 11 и выход 12, информационный выход 13 устройства, вход 14 синхронизации. 4 ил. 2 и ** ехр (12 вр1/ag; 1 с О,п-r; рб О, п-l. (l) На вход 2 устройства поступают данные k-й подстроки исходной последовательности из N отсчетов. После загрузки (n-))-го элемента k-й подстроки при поступлении последнего п-го элемента подстроки систолической матрицей 3 выполняется преобразование вида tl -1 рЕ С x(k-l)n + 1 + 1 ° W» (2) Во -(lr1 где С - элемент с номером р (р6 О, и-1) обработанной k-й подстроки, являющейся результатом обработки на первой ступени вычислений. С выхода 5 первой систолической к матрицы 3 результаты С, выполнения и-точечного ДПФ поступают на вторую ступень обработки. Укаэанные результаты поступают на первый вход первой дополнительной систолической матрицы 6, где домножаются на дополнительные весовые множители W 1, поступающие на второй вход 8 указанной матрицы. Полученные результаты умножения вида (3) поступают на первый вход второго модуля 7 первой дополнительной матрицы б. На вход 9 второго модуля 7 поступают весовые множители вида W „ (л) Вычислительные модули 7 дополнительной систолической матрицы 6 реализуют вычисления: n-< ко причем элементы результата с разными номерамьр от О до (n-1)-ro формируются параллельно-последовательно в модулях 7 дополнительной систолической 1399764 ьь х вых вмх 1 вх! х ьх1 Вх вх ХВ» Wer1 вх Wåõ х Т ьх + х х 11ьх ° еь х ЬЫх матрицы б, а промежуточные результаты суммирования хранятся в регистрах соответствующих каналов 11 блока конвейерных регистров 10. Результаты вычислений по выражению (4), являющиеся результатами выполнения второй ступени вычислений, снимаются с общего выхода 12 блока конвейерных регистров 10 и поступают на вход следующей дополнительной систолической матрицы 6, которая выполняет действия, аналогичные выражению (4), формируя результаты следующей ступени вычислений. При этом на второй вход 8 i-й дополнительной систолической матрицы 6 поступают весовые множите(%) ли вида Ы„,где i e 1, ш-!. Результаты обработки снимаются с общего выхода 12 последнего блока конвейерных регистров IO,который является выходом 13 устройства. Если W „ = 1, то в данном случае реализуется выполнение и-мерного ДПФ над m-мерными данными вида п n ... «и, причем каждая систолическая матрица 3 или 6 выполняет обработку по одной из координат Ес(э3 ли дополнительные множители W> (i 6 1, ш-1) принадлежат к классу ДЭФ, то выполняется и-точечное БПФ по основанию п, причем и-точечная "бабочка" реализуется путем ДПФ подстроки длиной и отсчетов. Если допол. (э ) нительные весовые множители W,, поступающие на входы 9 дополнительных систолических матриц, квантованы на малое число уровней, то устройство выполняет преобразование в Фурье-подобном базисе, например» комплексных прямоугольных функций, комплексном базисе Уолша, базисе пилообразных функций. При этом каждый модуль 4 первой систолической матрицы 3 реализует следующие функции (фиг.2): Каждый модуль 7 дополнительной систолической матрицы 6 реализует функции (фиг.3): Устройство управляется тактовыми.импульсами по входу 14 синхронизации. 55 формулаиэобретения 1. Устройство для дискретных ортогональных преобразований, содержащее первую матрицу из и-1 (и — основание преобразования) вычислительных модулей, причем первый и второй выходы j-го (i = 1, и-2) вычислительного модуля подключены соответственно к первому и второму входам (i+I)-го вычислительного модуля, первый вход первого вычислительного модуля является первым информационным входом устройства-, информационным выходом которого I явеяется второй выход (n-1)-го вычислительного модуля, тактовые входы вычислительных модулей соединены между собой и являются тактовым входом устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения области применения за счет обработки в различных ортогональных базисах и выполнения многомерного дискретного преобразования Фурье, в него введены m-l матриц из и вычислительных модулей в каждой, m-l(m=log„N,N — - размер преобразования блоков) конвейерных регистров, каждый из которых состоит иэ и каналов по п регистров (k = 1, и-1) в каждом, третий выход i-го вычислительного модуля первой матрицы подключен к третьему входу (i+1)-го вычислительного модуля первой матрицы, второй и третий входы первого вычислительного модуля которой соединены между собой и являются вторым информационным входом устройства, второй выход (n-I )-го вычислительного модуля первой матрицы подключен.к первому входу первого вычислительного модуля второй матрицы, первый выход первого вычислительного модуля 1-й (j = 2, m) матрицы подключен к перво му входу второго вычислительного модуля j-.é матрицы, первый и второй выходы i-го вычислительного модуля j-й матрицы подключены соответственно к первому и второму входам (i+I)-ro вычислительного модуля j-й матрицы, третий выход 1-ro (1 = 1, n) вычислительного модуля j-й матрицы подключен к первому входу 1-ro канала.(j-I)-ro блока конвейерных регистров, тактовый вход которого является тактовым вхо- дом устройства, выход 1-ro канала (j-I)-ro блока конвейерных регистров подключен к третьему входу 1-го вычислительного модуля. j-й матрицы,вто5 13997 рые входы всех каналов j-ro блока конвейерных регистров соединены с первым входом первого вычислительного модуля (+1)-й матрицы и является ()+1)-м Информационным входом устройства, а выход (Bl-1)-го блока конвейерных регистров подключен к информационному Выходу устройства, тактовые входы вычислительных модулей j-й матрицы под- 1О ключены к тактовому входу устройсФва. 2. Устройство по и. 1, о т л и— ч а ю щ е е с я тем, что вычислительНый модуль первой матрицы содержит jrepsbN и второй регистры, умножитель И сумматор, причем первым входом вычислительного модуля является инфорМационный вход первого регистра, перI алый выход которого является первым Ьыходом модуля, второй выход первого регистра подключен к первому входу умножителя второй вход которого яв1 ляется вторым входом модуля, выход :умножителя подключен к первому входу сумматора, выход которого является вторым выходом модуля, третьим выходом которого является первый выход второго регистра, второй выход которого подключен к второму входу сумматора, информационный вход второго ре гистра является третьим входом моду-. ,ля, тактЬвым входом которого являют-! ся соединенные между собой тактовйе ,входы первого и второго регистров. 64 6 3. Устройство по п. 1, о т л и ч а ю щ е е с я тем, чта вычислительный модуль j-й (j = 2, М) матрицы содержит регистр, умнажитель и сумматор, причем первый вход умнажителя, является первым входом модуля, вторым входом которого является информационный вход регистра, выход умнажителя подключен к первому входу сумматора и является первым выходом модуля; вторым выходом которого является первый выход регистра, второй выход которого подключен к второму входу умножителя, выход сумматора является третьим выходом модуля, третьим входом которого является второй вход сумматора, тактовый вход регистра является тактовым входом модуля. 4. Устройство по и. 1, о т л и— ч а ю щ е е с я тем, что каждый канал j-го (j 1 m-1) блока конвейер1 k ных регистров содержит и еггистров, причем shixop i-го (i 1, п-1) регистра подключен к информационному входу (i+1)-ro регистра, информационный вход первого регистра является входом канала, а первый и второй выходы и регистра являются соответстк зенно первым и вторым выходами канала, вторые выходы каналов соединены между собой и являются выходом j-ro блока конвейерных регистров, тактовым входом которого являются соедик ненные между собой тактовые входы п регистров.! 399764 Составитель А.Баранов Редактор А.Левкина Техред А.Кравчук Корректор М.П1ароши Заказ 2668/50 Тираа 704,Подписное BRHHIIH Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж-35, Рауаская наб., д. 4/5 Производственно-полиграФическое предприятие, г. Укгород, ул. Проектная, 4
