Устройство для вычисления преобразования фурье-галуа и свертки

(51) 4 С 06 Р 15/33 САНИЕ ИЗОБРЕТЕНИ ЛЬСТ иту СССР 1980. ИЯ П РТКИ иг,УДАРСТВЕННЫЙ КОМИТЕТ СССР ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИ А ВТОРСКОМУ СВИДЕ г(54) УСТРОЙСТВО ДПЯ ВЫЧИСЛЕНОБРАЗОВАНИЯ ФУРЬЕ-ГАЛУА И СВЕ(57) Изобретение относится к вычислительной технике и технической кибернетике и может быть использованов цифровых вычислительных системах,предназначенных для обработки сигналов Цель изобретения - повьппениебыстродействия, Поставленная цельдостигается за счет того, что устройство для вычисления преобразования фурье-Галуа и свертки содержитвычислительный блок 1, блок 2 умножения, вычислительный блок 3, блокнакапливающих сумматоров 4, блок 5памяти и блок.6 управления, 18 ил.17 129541руют выходные данные входных регистров 27 следующим образом: при поступлении на вход 32 и-го входногорегистра 27 (1 (иР), в котором записано значение первого сомножителяХ,Ь), значения первого (младшего)разряда Ь Ь) второго сомножителяоН Ь), соответствующего логическоиединице, выходные данные и-го регистра 27 остаются неизменными, а при 10поступлении на вход 32 значения,соответствующего логическому нулю,выходные данные п-го регистра 27становятся равными нулю, т,е. про-"исходит умножение значения 1 с-гопервого сомножителя Х, Ь) на значение первого разряда Е-го второгосомножителя Ь,1 с). 5 18Р-м цикле работы блока 2 умножения,с поступлением Р-го импульса такто,вой частоты на вход 33 во входныерегистры 27 записываются значенияпервых сомножителей Х Ь). В то жевремя на входы 32 - 32 р поступаютзначения,Р-х разрядов вторых сомножителей Ь ,1 Ь), которые корректируют выходные данные входных регистров 27, Скорректированные выходныеданные Х, Ь)Ь (р,1 Ь) входныхрегистров 27 поступают на первые входы сумматоров 20 блока 28, где онисуммируются с данными, которые поступили на вторые входы сумматоров 20 свыходов регистра 19 промежуточной памяти и на выходе сумматоров 20 Формируется суммаСкорректированные выходные данные ХЬ) ЬЬ) входных регистров 27 поступают на вторые входы (входы В) сумматоров 20 блока 28 (фиг.3), где они суммируются с данными, поступившими на первые вхо ды (входы А) этих же сумматоров с выходов регистров 19 промежуточной памяти (нулевые значения) и на выходе сумматоров 20 формируется сумма (Х,Ь)Ь (1 с) + О). Выходные 30 данные сумматоров 20 поступают на входы умножителей 21 на степени двойки, причем во всех умножителях 21 блока 28 накапливающих сумматоров по модулю М, используемого в блоке 2 умножения, производится умножение на 2 " . Выходные данные с блоков 21,поступают на входы регистров 19 промежуточной памяти, На вход 34, объединяющий входы такто вой частоты регистров 19 промежуточной памяти блока 28 поступают импульсы тактовой частоты, сдвинутые во времени на половину периода тактового импульса. Первый импульс, 45 поступивший на вход 34, разрешает запись в регистры 19 промежуточной памяти сумм полученных на выходахУРсумматоров 20 и умноженных на 2 с помощью умножителей 21, т.е. 502 Р.тХ (1,),.1 Ь).С поступлеййем третьего импульса тактовой частоты на вход 33 цикл работы блока 2 умножения повторяется и в регистры 19 промежуточ ной памяти записываются накопленные за три цикла в сумматорах 20 частичные значения произведения Х Ь) Н (К) Такой процесс повторяется Р раз, На+ 2 хЬ) Ь,Ь)Выходные данные сумматоров 20 поступают на умножители 21, где умножаются на 2 и подаются затем нар 1входы регистров 19 промежуточной памяти, Р-й импульс тактовой частоты,который поступает на вход 34, разрешает запись в регистры 19 промежуточной памяти данных, которые поступилина его входы,2 (Х (1 с) Ь(р,1(14) Выражение (14) полностью совпадает с выражением (9) для произведения двух Р-разрядных чисел Х и Н. Р значений произведений спектральных коэффициентов Х Ь) Н Ь), 0 басРс выходов223 регистров 19 промежуточной памяти поступают одновременно на Р Р-разрядных входов 38 блока 29 соединений (Фиг.5). Блок 29 соединений и группа из Р Р-разрядных выходных сдвиговых регистров 30 служат для реализации последовательного вывода Р значений произведений Х(Ы)Н Ь) из блока 2 умножения в блок 3 на . том этапе вы 9числений, когда работает блок 3.1". помощью блока 29 соединений на входпервого сдвигового регистра 30 поступают Р первых (младших) разрядов первого ВторогоР Го произведе 5ния спектральных коэффициентов, навход второго сдвигового регистра 30поступают Р вторых разрядов первого,второго, , Р-го произведенияспектральных коэффициентов,на вход Р-го сдвигового регистра30 поступают Р Р-х разрядов первого,второго Р-го произведения спектральных коэффициентов. Запись данных, поступивших на входы сдвиговыхрегистров 30, производится подачейна вход 36 разрешающего импульса,совпадающего по времени с (Р+1)-мимпульсом тактовой частоты. Выходымладших разрядов каждого из Р выходных сдвиговых регистров 30 объединеныв одну Р-разрядную шину 31.При этомпосле записи в сдвиговые регистры30 данных на первом выходе Р-разряд 25ной шины 31 появляется значение первого разряда первого произведенияХ (О) Н (0), на втором выходе -значение второго разряда произведения Х,(0) Н (0) на Р-м выходе - значение Р-го разряда произведе 30ния Х,(0) Н (0). Для получения навыходе шины 31 значения второго произведения Х, (1) Н (1) необходимопроизвести сдвиг влево содержимогоР сдвиговых регистров 30 путем подачи управляющих импульсов на входы36 и 37. При этом на выходах младших разрядов появляются значениявторого произведения Х(1) Н(1):на первом выводе Р-разрядной шины31 - значение первого разрядаХ,(1) Н (1), на втором, выводезначение второго разряда произведения Н (1) Х,(1) на Р-м выводе - значение Р-го разряда произведения Х(1) Н (1).1Для получения Р значений произведения Х,(1) Н (1) необходимо произвести (Р) сдвигов влево содержимого сдвиговых регистров 30. Импуль-.сы сдвига поступают на входы 36 и37 при работе блока 3 (обеспечиваютпоследовательный ввод значений про -изведений Х Ь) Н Ос) в блок 3). 55Блок памяти работает следующим образом,Входные данные, представляющиесобой отсчеты числовой последова 15 20тельности (Р отсчетов по 2 Р разрядов каждый, 01Р), подаются по шине 8 последовательного ввода на входы каждого сдвигового регистра 40(фиг.б, 14 и 15). В момент поступления первого отсчета входной последовательности Н(О) на вход 41 тактовой частоты первого сдвигового регистра 40 с выхода блока 6 управления поступает первый импульс тактовой частоты. С поступлением этого импульса первый отсчет записывается в первый сдвиговый регистр 40. В момент поступления второго отсчета входной последовательности Н(1) на вход 41 тактовой частоты второго сдвигового регистра 40 поступает второй импульс тактовой частоты и второй отсчет записывается во второй сдвиговый регистр 40, Таким же образом записываются остальные отсчеты входной последовательности НЙ) в соответствующие сдвиговые регистры 40. После записи последнего Р-го отсчета входной последовательности Н(Р) в Р-й сдвиговый регистр 40 процесс записи входной последовательности НВ) заканчивает - ся (это соответствует работе блока 5 памяти на первом этапе вычисления, фиг.15). Данные, записанные в сдвиговых регистра 40, поступают на выход блока 5 памяти с выходов младших разрядов регистров 40, начиная с младших разрядов. При записанных данных в регистрах 40 на выходах 32, - 32 младших разрядов регистров 40 находятся значения первых (младших) разрядов Р отсчетов входной последовательности НЬ). Для получения на выходах 32 - 32 р значений вторых разрядов отсчетов НЬ) производится сдвиг влево содержимого регистров 40 путем подачи управляющих импульсов на входы 41 и вход 42. При этом з начения первых раз рядов с выходов 32 подаются на входы последовательного ввода при сдвиге влево П, соответствующих регистров 40 и за:исываются на место старших разрядов, сдвинутых на один разряд влево. Таким образом, производится циклический сдвиг данных, записанных в регистрах 40. Повторяя сдвиг данньц; в регистрах 40 (Р) раз, получают на выходах 32 значений младших разрядов отсчетов 2 Р - разрядной числовой последовательности НЬ). Младшие Р разрядов отсчетов последовательностиНЬ) соответствуют второй части числовой последовательности Н (к).Дляполучения на выходах 32 Р старшихотсчетов 2 Р-разрядной последовательности НЬ) соответствующих первойчасти числовой последовательностиНЬ) необходимо произвести Р циклических сдвигов содержимого регисФров 40. При следующих Р сдвигах содержимого регистров 40 на выходах И32 последовательно появляются значения Р разрядов отсчетов второй частичисловой последовательности Н Ь)Таким же образом получают значенияследующих Р разрядов отсчетов первойчасти числовой последовательностиН,Ь) при осуществлении Р сдвиговсодержимого регистров 40. Работаблока 5 памяти в режиме циклического сдвига соответствует работе этого блока на втором - пятом этапахвычисления (Фиг.14 - 17). В блоке 4 накапливающих сумматоров (фиг.7, 14 - 17) производится вы числение выходной свертки путем умножения частичных значений сверток, поступающих на его входы 43 на множители 2 , 2 и 2 , и суммироЯР Р аванне полученных произведений в со ответствии с выражением (12). Перед началом работы блока 4 производится обнуление регистров 45 промежуточной памяти импульсом, который поступает синхронно с запускающим импульсом от управляющей ЭВМ на вход 52. Входные Р-разрядные отсчеты вычисленных частичных значений свертки поступают на входы 43 ЗР-разрядных входных сдвиговых регистров 44, причем пер вые (младшие) разряды Р входных отсчетов поступают на входы (Р+1)-х разрядов соответствующих входных регистров 44, вторые разряды входных отсчетов поступают на входы (Р+2)-х 45 разрядов соответствующих входных регистров 44, , Р-е разряды Р входных отсчетов поступают на вхоцы 2 Р-х разрядов соответствующих входных регистров 44. При поступлении импульса тактовой частоты на вход 48, который объединяет входы тактовой частоты группы входных сдвиговых регистров 44, производится запись данных, поступивших на Р вхо дов регистров 44, начиная с входов (Р+1)-го разряда и кончая входами 2 Р-го разряда ЗР-разрядных входных регистров 44, т.е. входные данные сразу сдвинуты на Р разряд вправо,что соответствует умножению на 2Поэтому нет необходимости умножатьна 2 частичные значения свертких(п) % Ь (п) и х (и) + Ь(п), поступающие на входы 43 блока 4 накапливающих сумматоров на третьем и шестом этапах вычислений,Частичные значения свертких,(п)Ь(п) в конце третьего этапа вычислений поступают на входырегистров 44. Вход 48 объединяетвходы тактовой частоты группы входных регистров 44,С поступлением на вход 48 на третьем этапе вычислений (Р+1)-го импульса тактовой частоты, задержанного во времени на половину периода тактового импульса (фиг.16), частичные значения свертки х,(п) - Ь (п) записываются во входные регистры 44, С выходов последнихчастичные значения свертки, умноженные на 2 , т.е. (х (п)Ь (и) 2 , поступают на вторые входы (входы В) сумматоров 46. На первые входы (входы А) сумматоров 46 поступают данные с выходов регистров 45 промежуточной памяти (нулевые значения), Полученная сумма поступает на входы регистров 45 промежуточной памяти и с поступлением перного импульса тактовой частоты на четвертом этапе вычислений (фиг.16) записываются в регистры 45. Частичные значения свертки х (и)Ь(п) в конце четвертого этапа вычислений поступают на входы регистров 44 и с поступлением на вход 48 на четвертом этапе вычислений (Р+1)-го импульса тактовой частоты, задержанного во времени на половину периода тактового импульса, записываются во входные регистры 44. Частичные значения свертки, записанные в регистрах 44 (х,(п)11(п , необходимо умножить на 2 " в соответствии с выражением (12), Для этого на пятом этапе вычислений производится сдвиг вправо содержимого регистров 44 путем подачи Р управляющих импульсов на входы 48 и 49 (Фиг. 17). Полученные на входах регистров 44 значения частичной свертки (х(п). Ь,(пф 2 подаются на вторые входы сумматоров 46, где они суммируются с данными, хранящимися в регистрах промежуточной памяти 45, Полученная сумма х,(п)(Ь (п).) 2 + + (х, (и) Ь(п) )2 ) с приходом(Р+1)-го импульса тактовой частотына пятом этапе вычислений на вход 51записывается в регистры промежуточной памяти. Частичные значения свертких (и)Ь(и) в конце пятого этапавычислений поступают на входы регистров 44 и с поступлением на вход48 (Р+1)-го импульса тактовой частоты, задержанного во времени на половину периода тактового импульса, записываются во входные регистры 44.Частичные значения свертки, записанные в регистрах 44 х (и)Ь (и 2р йнеобходимо умножить на 2 в соответствии с выражением (12), т,е, значение, определяемое выражениемх (и)Ь (и 2 Р, сдвигается на Рразрядов влево, что соответствует умножению х (и)Ь (и) на 2 . Для этого на шестом этапе вычислений(фиг,17) производится сдвиг влевосодержимого регистров 44 путем подачи Р управляющих импульсов на входы 48 и 50. Полученные на выходахрегистров 44 значения частичной свертки х (и) - Ь(и 2 подаются навторые входы сумматоров 46, где они 30суммируются с данными, хранящимисяв регистрах 45 промежуточной памятиПолученная сумма х (и)Ь (и 2 ++ (х,(и) - Ь,(и) 2 + (х (и) . 1 з (и 2,с приходом (Р+1)-го импульса тактовЬй частоты на шестом этапе вычислений на вход 51 записывается в регистрах 45 промежуточной памяти. Частичные значения свертки х (и) - Ь,(и)в конце шестого этапа вычислений поступают на входы регистров 44 и споступлением на вход 48 (Р+1)-гоимпульса тактовой частоты, задержанного во времени на половину периодатактового импульса, записываются во 45входные регистры 44. С выходов реги-стров 44 значения частичной свертких (и) - Ь,(и 2 подаются на первые входы сумматоров 46, где они суммируются с данными, хранящимися в ре гистрах 45 промежуточной памяти. Полученная на выходах сумматоров46 сумма (х,(и)Ь (и 2 ++ (х д(и)А Ь, (и 2 соответствует, выражению (12) для результирующей свертки. Данные с выводов сумматоров 46подаются на выходы 47 блока 4 накапливающих сумматоров,Блок 6 управления служит для выдачи управляющих импульсов на все блоки устройства и работает следующим образом (Лиг.8, иг.9 - 17),На вход 9 блока 6 управления поступает импульс начальной установки от управляющей ЭВМ, На вход 9 поступает запускающий импульс от управляющей ЭВМ. На вход 9поступают импульсы тактовой частоты. Вся работа устройства делится на шесть этапов длительностью (Р+1) периодов тактовых импульсов каждый. На каждом этапе работы с блока 6 управления подаются управляющие импульсы в различные блоки устройства. Перед началом работы блока управления произво- дится начальная установка узла 53 выбора режима импульсом, поступающим на вход 9, узла 53. С приходом запускающего импульса начинает работать узел 53 и на его выходе 54 появляется импульс, который запускает синхронизатор 66 и узел 67 памяти адреса, которые управляют работой блока 1 и блока 5 памяти на первом этапе вычислений (Лиг. 14). Кроме того, синхронно с запускающим импульсом от управляющей ЭВМ на выход 52 управления накапливающими сумматорами подается импульс для обнуления регистров 45 промежуточной памяти блока накапливающих сумматоров (Фиг.7). По окончании первого этапа работы блока 6 управления на выходе 55 узла 53 появляется импульс, который изменяет режим работы узла 67 памяти адреса и запускает синхронизатор 68 умножителей. Эти узлы управляют работой блока 5 памяти на протяжении второго - пятого этапов вычислений и блока 2 умножителя .на втором этапе вычислений. По окончании второго этапа работы блока 6 управления на выходе 56 узла 53 появляется импульс, который запу.скает синхронизатор 66, синхронизатор 68 умножителей, синхронизатор 69 и синхронизатор 70 накапливающих сумматоров. Эти синхронизаторы управляют работой блоков 1 - 4 на третьем этапе вычислений, По окончании третьего этапа работы блока 6 управления на выходе 57 узла 53 появляется импульс, который запускает синхронизатор 68 умножителей, синхронизатор 69, синхронизатор 70 накапливающих сумматоров. Эти синхронизаторы управ25ляют работой блоков 2, 1 и 4 на четвертом этапе вычислений. По окончании четвертого этапа работы блока 6 у 1 равления на выходе 58 узла 53 появляется импульс, который запускает синхронизатор 68 умножителей, синхронизатор 69, синхронизатор 70 накапливающих сумматоров, Эти синхронизаторы управляют работой блоков 2 - 4 на пятом этапе вычислений. По окончании 10 пятого этапа работы блока 6 управления на выходе 59 узла 53 появляется импульс, который останавливает работу формирователя 67 адреса и запускает синхронизатор 68 умножителей, син хронизатор 70 накапливающих сумматоров. Синхронизаторы 69 и 70 управляют работой блока 3 и блока 4 накапливающих сумматоров на шестом этапе вычислений. гсУзел 53 выбора режима блока 6 управления работает следующим образом (фиг.9, 14 - 17). 12954 На первый вход 9 узла 53 поступает импульс начальной установки от управляющей ЭВМ, на второй вход 9, запускающий импульс от управляющей ЭВМ, на третий вход 9поступают им р пульсы тактовой частоты. Импульсом начальной установки производится обнуление шестираэрядного 79 и (Р+1)- разрядного 80 сдвиговых регистров и первого КЯ-триггера 75. С приходом запускающего импульса на выходе второго КЯ-триггера 75 устанавливается уровень "Лог. 1", Этот же запускающий . импульс через элемент НЕ 76 устанавливает уровень "Лог.О" на входах АО управления шестиразрядного 79 и (Р+1)-разрядного 80 сдвиговых реги.стров, на первые входы которых постоянно подается уровень "Лог.1". При поступлении на входы тактовой частоты регистров 79 и 80 уровня "Лог.1" с выхода второго КЯ-триггера 75 через элементы ИЛИ 77 в первых (младших) разрядах регистров 79 и 80 записывается значение "Лог.1". Уровень "Лог.1" с первого выхода регистра 80 поступает на К-вход второго КЯ-триггера 75 и на Я-вход первого КЯ-триггера 75. При этом на выходе второго КЯ-триггера 75 устанавливается уровень "Лог.О", а на выходе первого КЯ"триггера уровень ,"Лог.1", который разрешает прохождение через элемент И 78 импульсов 26тактовой частоты, которые поступают на второй вход этой схемы.Импульсы тактовой частоты с выхода элемента И 78 через второй эле-. мент ИПИ 77 поступают на вход тактовоч частоты регистра 80. Уровень "Лог.1" с первого выхода регистра 80 поступает также на вход элемента И 81 группы из шести элементов И, на другой вход которой поступает уровень "Лог.1" с выхода регистра 79. При этом на выходе первого элемента И 81 группы находится уровень "Лог.1" до тех пор, пока значение "Лог. 1", записанное в первом разряде регистра 80, не сдвинется во второй разряд при поступлении импульса тактовой частоты на тактовый вход регистра 80. Следующим импульсом тактовой частоты производится сдвиг содержимого регистра 80 еще на один разряд вправо и так далее до тех пор, пока на (Р+1)-м выходе регистра 80 не появляется уровень "Лог,1". При этом уровень "Лог.1" поступает через элемент ИЛИ 77 на вход тактовой частоты регистра 79 и содержимое этого регистра сдвигается на один разряд вправо, т.е, на втором выходе регистра 79 появляется уровень "Лог.1", который подается на первый вход второго элемента И 81 группы. На этом заканчивается первый этап работы узла 53, который равен длительности запускающего импульса от управляющей ЭВИ плюс дительность Рпериодов тактовой частоты.Запускающий импульс по длительности равен тактовым импульсам и син хронизирован с тактовой частотой, Поэтому первый этап работы блока уп,равления режимами длится (Р+1)-периодов тактовой частоты. (Р+1)-й выход регистра 80 соединей также с входом последовательного ввода при сдвиге вправо этого же регистра и при поступлении следующего импульса тактовой частоты значение "Лог.1" записывается в первом разряде регистра 80. Таким образом с поступлением (Р+1)-го импульса тактовой частоты или первого импульса тактовой частоты второго этапа работы узла 53 на первом выходе регистра 80 появляется уровень "Лог.1", который разрешает прохождение через второй элемент И 81 уровня "Лог.1" с второго выхода регистра 79,на выходе 55 узла 53 находится уро 27 129541 вень "Лог,1" в течение одного периода .тактовой частоты. Через каждые следуюшие (Р+1) такта работы узла 53 на его выходах 56 - 59 поочередно появляются уровни "Лог.1" в течение первого периода тактовой частоты каждо,го этапа работы узла 53. В конце ше - стого этапа работы на (Р+1)-м выходе регистра 80 появляется уровень"Лог.1", который через элемент ИЛИ 77 10 поступает на вход тактовой частоты,ре. гистра 79 и содержимое этого регистра сдвигается на один разряд вправо, т.е. на всех выходах регистра 79 находятся уровни "Лог.О"и узел 53 заканчивает свою работу до поступления следующих управляющих импульсов на его входы. В результате в процессе работы узла 53 на его выходах 54-59 формируются импульсы, которые управля 20 ют работой синхронизаторов 66 - 70 рлока 6 управления (фиг.8 и 14).Синхронизатор 66 (блок 69 аналогичен блоку 66) работает следующим образом (йиг.10 14 - 17).На вход 63 синхронизатора 66 поступают запускающие импульсы с узла 53. На тактовый вход 9 поступают импульсы тактовой частоты. На вход управления (Р+1)-разрядного сдвиго вого регистра 82 постоянно подается уровень "Лог.1". С приходом запускающего импульса на входе последовательного ввода при сдвиге вправо (Р+1)-разрядного сдвигового регист ра 82, Б-входе первого КБ-триггера 83 и выходе 17 устанавливается значение "Лог. 1". При этом на выход первого КЯ-триггера 83 появляется уровень "Лог.1", который разрешает 40 прохождение тактовых импульсов через элемент И 85 на выход 15. Тактовые импульсы поступают также на вход тактовой частоты регистра 82 и вход элемента НЕ 84. С приходом45 первого тактового импульса в первом (младшем) разряде регистра 82 записывается значение "Лог,1" и на его первом выходе появляется уровень"Лог.1", который поступает на 8 вход второго КЯ-триггера 83. При этом на выходе этого КЯ-,триггера появляется уровень "Лог. 1", который разрешает прохождение инвертированных тактовых импульсов через второй элемент 60 на выход 16.С приходом второго тактового импульса содержимое регистра 82 сдвигается на один разряд вправо и на втором выходе этого регистра появляется уровень "Лог.1". Каждым следующим тактовым импульсом производится сдвиг содержимого регистра 82 на один разряд вправо. При этом импульсы тактовой частоты проходят на выход 15, а инвертированные импульсы тактовой частоты прцходят на выход 16 синхронизатора 66. С поступлением Р-го импульса тактовой частоты на Р-м выходе регистра 82 появляется уровень "Лог.1", который поступает на Б-вход третьего КЯ-триггера 83 и на его выходе устанавливается уровень "Лог.1".При этом разрешается прохождение через элемент И 85 инвертированного Р-го импульса тактовой частоты, который поступает на К-вход первого КЯ-триггера 83 и устанавливает на его выходе значение 1 Лог.О", чем запрещает дальнейшее прохождение тактовых импульсов через элемент И 85 на выход 15С поступлением (Р+1)-го импульса тактовой частоты на (Р+1)-м выходе регистра 82 появляется уровень "Лог.1", который поступает на К-входы второго и третьего КЯ-триггеров 83 и на их выходах устанавливаются уровни "Лог,О". Пр. этом запрещается прохождение инвертированных импульсов тактовой частоты с выхода элемента НЕ 84 через элементы 60. Уровень "Лог,1" с (Р+1)-го выхода регистра 82 поступает на выход 18. С .приходом следующего импульса тактовой частоты содержимое регистра 82 сдвигается на один разряд вправо и на всех выходах регистра 82 устанавливаются уровни "Лог.О". В результате в процессе работы синхронизатора 66 на его выходах 15 - 18 Формируются импульсы, которые управляют работой блока 1.Синхронизатор умножителей 68 работает следующим образом (фиг.11,14-17)На вход 64 поступают запускающие импульсы с узла 53. На тактовый вход 9 поступают импульсы тактовой частоты. На вход 72 синхронизатора 68 умножителей поступают управляющие импульсы выхода 72 синхронизатора 69 (фиг.8). Эти импульсы поступают на выход 37 и через элемент ИЛИ 90 также на выход 36 синхронизатора 68.В остальном работа синхронизатора 68 умножателей полностью соответствует работе синхронизатора 66.29 12954Узел 67 памяти адресовработает следующим образом (Ьиг. 12, 14-17).На входы 54, 55 и 59 узла 67 поступают запускающие импульсы с узла 53. На тактовый вход 9 поступают импульсы тактовой частоты. На вход управления режимом Р-разряднога сдвигового регистра 93 и первый вход (Р+1)-разрядного сдвиговога регистра 95 постоянно подается уровень "Лог, 1" Ю С приходом запускающего импульса на вход 54 на входе последовательного ввода при сдвиге вправо Р-разрядного сдвигового регистра. 93 появляется уровень "Лог.1" и с приходом перво го импульса тактовой частоты, который поступает на вход тактовой частоты регистра 93, в первом (младшем) разряде регистра 93 записывается значение "Лог.1" и на ега первом выходе 2 О появляется уровень "Лог.1", который через первый элемент ИЛИ 96 группы поступает на выход 41, узла 67. С приходом второго импульса тактовой частоты на втором выходе регистра 93 появляется уровень "Лаг,1, который через второй элемент ИЛИ 96 группы поступает на выход 41 узла 67 с приходом Р-го импульса тактовой частоты на Р-м выхода регистра 93 по О является уровень "Лог,1", который че" рез Р-й элемент ИЛИ 96 группы поступает на выход 41 р, На этом узел 67 памяти заканчивает работу, соответствующую первому этапу работы уст ройства. С приходом запускающего импульса на вход 55, который соединен с входам схемы 92 и Б-входом первого КБ-триггера 91, на входе управления режимом (Р+1)-разрядного сдвигового регистра 95 устанавливается уровень "Лог.0", а на выходе первого КБ-триггера уровень "Лог,1", который разрешает прохождение тактовых импульсов через элемент И 94 на вход тактовой частоты регистра 95. Первым импульсом тактовой частоты, поступиввжм на вход тактовой частоты регистра 95, производится запись уровня "Лаг.1" в первом (младшем) разряде регистра 95 и на первом выхоце этого регистра появляется уровень "Лаг.1", который подается на Б-вход второго КБ-триггера 91. При этом на выходе второго КБ- триггера появляется уровень "Лог,1" который разрешает прохождение инвертированных импульсов тактовой часто 30ты на выход элемента И 94, С выхода последнего инвертированные импульсы тактовой частоты поступают на выход 42 и через Р элементов ИЛИ 96 группы на выходы 41 - 41, узла 67.По экончании запускающего импульса, поступившего на вход 55, на входе управления режимом регистра 95 появляется уровень "Лог.1" и при поступлении следующего импульса тактовой частоты происходит сдвиг содержимого регистра 95 на один разряд вправо.При этом на втором выходе регистра 95 появляется уровень "Лог,1", С поступлением каждого следующего импульса тактовой частоты происходит сдвиг содержимого регистра 95 на один разряд вправо и при поступлении (Р+1)-го импульса тактовой частоты второго этапа работы устройства на (Р+1)-м выходе регистра 95 появляется уровень "Лог.1",который поступает на К-вход второго КБ-триггера и на его выходе устанавливается уровень "Лог.О", который запрещает прохождение (Р+1)-го инвертированного импульса . тактовой частоты на выходы 42 и 4 1, - 41 .узла 67. Уровень "Лог.1" с (Р+1)-га выхода регистра 95 поступает также на вход последовательного ввода при сдвиге вправо этого же регистра и при поступлении первого импульса тактовой частоты на третьем этапе работы в первом разряде регистра 95 записывается значение "Лог.1". В остальном работа узла 67 на этапе работы блока 6 управления полностью совпадает с работой этого блока на втором этапе работы. На следующих четвертом и пятом этапах работы узла 67 цикл повторяется. С приходом в начале шестого этапа работы узла 67 запускающего импульса на вход 59 на выходе первого КБ-триггера появляется уровень "Лог.О", который запрещает прохождение импульсов тактовой частоты через элемент И 94, Этим же запускающим импульсом производится обнуление содержимого регистра 95.:В результате в процессе работы узла 67 на его выходах 42 и 41 - 41 формируются импульсы, которые управляют работой блока 5 памяти устройства,Синхронизатор 70 накапливаощих сумматоров работает следующим образам (Фиг.13 - 17).31 12954На входи 57 - 59 постлают запускающие импульсы с узла 53. На первый и второй входы блока 70 поступают управляющие импульсы соответственно с четвертого 74 и второго 72 выходов синхронизатора 69. Управляющие ,импульсы, поступающие на вход 74 через элемент 99 задержки и элемент ИЛИ 100, поступают на выход 48 с задержкой на половину периода так товой частоты. С выхода схемы задержки эти же импульсы поступают на К- входы первого и второго КБ-триггеров 97 и на выходах этих КБ-триггеров устанавливается уровень "Лог.0", За - пускающий импульс с входа 57 через элемент ИЛИ 100 проходит на выход 51, Запускающий импульс, который поступает на вход 58 синхронно с первым импульсом тактовой частоты, на пятом этапе вычислений подается на Б-вход первого КБ-триггера 97 и на его выходе появляется уровень "Лог.1", который разрешает прохождение импульсов с входа 72 через элемент И 9825 на выход 49 и далее через элемент ИЛИ 100 на выход 48, а также импуль - са с входа 74 через элемент И 98 и элемент ИЛИ 100 на выход 51 на пятом этапе вычислений. Запускающий импульс, поступающий на вход 59 синхронно с первым импульсом тактовой частоты, на шестом этапе вычислений подается на Б-вход второго КБ-триг гера 97 и на его выходе появляется 35 уровень "Лог. 1", который разрешает прохождение импульсов с входа 72 через элемент И 98 на выход 50 и далее через элемент ИЛИ 100 на выход 48, а также импульса с входа 74 че рез элемент И 98, элемент ИЛИ 100 на выход 51 на шестом этапе вычислений. Импульсом, задержанным на половину периода тактовой частоты, с входа 74 производится установка в нулевое состояние первого и второго КБ-триггеров 97. В результате, в процессе работы синхронизатора 70 накапливающих сумматоров на его выходах 48 - 51 формируются импульсы, которые управляют работой блока 4 накапливающих сумматоров. формула из обретения55Устройство для вычисления преобразования Фурье-Галуа и свертки, содержащее блок умножения и блок памяти, выход которого подключен к пер 32ному входу блока умножения, о т л ич а ю щ е е с я тем, что, с целью повышения бьстродействия, в него введены первый и второй вычислительные блоки, блок накапливающих сумматоров и блок управления, информационный вход первого вычислительного блока является первым информационным входом устройства, выход первого вычислительного блока подключен к второму входу блока умножения, выход которого подключен к информационному входу второго вычислительного блока, выход которого подключен к информационному входу блока накапливающих сумматоров, выход которого является информационным выходом устройства, причем первый, второй третий, четвертый и пятый выходы блока управления подключены соответственно к управляющему входу первого вычислительного блока, адресному входу блока памяти, к синхровходу блока умножения, управляющему входу второго вычислительного блока и к синхровходу блока накапливающих сумматоров, причем информационный вход блока памяти является вторым информационным входом устройства, при этом блок управления содержит узел выбора режима, два синхронизатора вычислительных блоков, узел памяти адресов, синхронизатор умножителей, синхронизатор накапливающих суммато-. ров и три элемента ИЛИ, причем первый, второй и третий входы узла выбора режима являются соответственно входом начальной установки, входом запуска и тактовым входом устройства, первый и третий выходы узла выбора режима подключены соответственно к первому и второму входам первого элемента ИЛИ, выход которого подключен к входу первого синхронизатора вычислительного блока, первый, второй и шестой выходы узла выбора режима подключены соответственно к первому, второму и третьему адресным входам узла памяти адресов, второй, третий, четвертый и пятый выходы узла выбора режима подключены соответственно к первому, второму,третьему и четвертому входам второго элемента ИЛИ, выход которого подключен к входу запуска синхронизатора умножителей, третий, четвертый и пятый выходы узла выбора режима подключены соответственно к первому, второму, третьему и четвертому вхо12954 33дам третьего элемента ИЛИ, выход которого подключен к входу запуска второго синхронизатора вычислительного блока, четвертый, пятый и шестой выходы узла выбора режима подключены соответственно к установочному входу, входу запуска и входу останова синхронизатора накапливающих сумматоров, второй выход второго синхронизатора вычислительного блока под ключен к входу останова синхронизатора умножителей и входу запуска синхронизатора накапливающих сумматоров, четвертый выход второго синхронизатора вычислительного блока подключен к установочному входу синхронизатора накапливающих сумматоров, тактовый вход узла выбора режима объединен с установочными входами первого и второго синхронизаторов 2 О вычислительных блоков, управляющим входом узла памяти адресов и установочным входом синхронизатора умножителей, первый, второй, третий и четвертый выходы первого синхрониза 25 тора вычислительного блока объединены и являются первым выходом блока управления, первый и второй выходы узла памяти адресов объединены и являются вторым выходом блока. управле 30 ния, первый, второй, третий, четвертый и пятый выходы синхронизатора умножителей объединены и являютсятретьим выходом блока управления,первый, второй, третий и четвертый вы ходы второго синхронизатора вычислительного блока объединены и являются четвертым выходом блока управления, первый, второй, третий и четвертый выходы синхронизатора накапливающих сумматоров и второй вход узла выбора режимов объединены и являются пятым выходом блока управленкя, при этом узел выбора режима содержит два КБ- триггера, элемент НЕ, два элемента ИЛИ, элемент И, два сдвиговых регистра и группу элементов И, причем входы установки нуля первого и второго сдвиговых регистров и К-вход первого КБ-триггеров объединены и являют ся первым входом узла выбора режима. третьим входом которого является первый вход элемента И, вход элемента НЕ и Б-вход второго КБ-триггера 15 34объединены и являются вторым входомузла выбора режима, выход первогоКБ-триггера подключен к второму входу элемента И, выход которого подключен к первому входу второго элемента ИЛИ, выход элемента НЕ подключен к входам управления сдвигом первого и второго сдвиговых регистров,выход второго КБ-триггера подключенк вторым входам первого и второгоэлементов ИЛИ, выход второго элемента ИЛИ подключен к тактовому входувторого сдвигового регистра, выходмладшего разряда которого подключенк Б-входу первого КБ-триггера,К-входу второго КБ-триггера и первымвходам элементов И группы, выходстаршего разряда второго сдвиговогорегистра подключен к входу последовательного занесения информациивторого сдвигового регистра и первымвходам первого элемента ИЛИ, выходкоторого подключен к тактовому входупервого сдвигового регистра, входымладших разряцов первого и второгосдвиговых регистров соединены и являются входом логической единицы узлавыбора режимов, выходы разрядов пер,вого сдвигового регистра подключенык вторым входам соответствующих элементов И группы, выходы которых являются выходами с первого по шестойузла выбора режима, при этом вычислительный блок содержит группу изР входных регистров, узел накапливающих сумматоров по модулю М (М =2 - 1) и группу из Р выходныхрегистров, причем информационныевходы входных регистров объединены и являются информационным входом вычислительного блока, выход.-го (х= 1 Р) входного регистраподключен к -му информационномувходу узла накапливающих сумматоровпо модулю М, -й выход которогоподключен к информационному входух-го выходного регистра, выходы выходных регистров объединены и являются выходом:вычислительного блока,тактовые входы входных регистров,узла накапливающих сумматоров помодулю М и вьиодных регистров объединены и являются управляющим входом вычислительного блока, 1295415Изобретение относится к вычислительной технике и технической кибернетике и может быть использовано в,цифровых вычислительных системах,предназначенных для обработки сигналов (в частности, для обработки изоб раже ний),Цель изобретения - повышение бы-стродействия.На Фиг. 1 представлена функциональная схема устройства для вычисленияпреобразования Фурье-Галуа (ПФГ) исвертки; на Фиг.2 - схема вычислительного блока; на Фиг.З - схема узла накапливающих сумматоров по модулю М;на Фиг.4 - схема блока умножения," нафиг.5 - схема блока соединений; наФиг. 6 - схема блока памяти; на фиг. 7 -схема блока накапливающих сумматоров;на Фиг.8 - функциональная схема блока управления; на Фиг.9 - схема узлавыбора режима; на фиг,10 - схемасинхронизатора вычислительного блока; на фиг.11 - схема синхронизатора25умножителей; на фиг.12 - схема узлапамяти адресов; на фиг.13 - схемасинхронизатора накапливающих сумматоров; на Фиг.14 - общая временная диаграмма работы устройства для вычисления ПФГ и свертки; на Фиг.15 - 17 -временные диаграммы работы блоков устройства для вычисления ПФГ и свертки соответственно на первом и втором, третьем и четвертом, пятом ишестом этапах работы устройства; на 35Фиг.18 - схемы умножителей на степе-,ни двойки по модулю М = 2 - 1 в случае Р = 7. Функциональная схема устройства 40 для вычисления ПФГ и свертки (Фиг. 1) содержат вычислительный блок 1 ПФГ, блок 2 умножения, вычислительный блок 3, блок 4 накапливающих сумматоров, блок 5 памяти, блок б управле ния, информационные входы 7 и 8, вход 9 управления, информационный выход 10 устройства.Вычислительный блок (фиг.2) содержит группу из Р Р-разрядных входйых регистров 11, узел 12 накапливающих сумматоров по модулю М, группу из Р Р-разрядных выходных регистров 13, информационные выходы 14, входы управления 15 - 18. 55Узел накапливающих сумматоров по модулю М (фиг.З) содержит группу из Р Р-разрядных регистров 19 промежуточной памяти, группу из Р Р-разряд-,ных сумматоров 20, группу из Р ум- ножителей 21 на степени двойки, инФормационные входы 22, выходы 23, входы 24 и 25 управления.Схема блока умножения (фиг.4) содэржит информационные входы 26 блока, группу из Р Р в разрядн входных регистров 27, узел 28 накапливающих сумматоров по модулю М (выполненный по схеме блока накапливающих сумматоров по модулю М, содержацимися в блоке 1 ПФГ), узел 29 соединений, группу из Р Р-разрядных выходных регистров 30, выход 31 блока умножения, Р управляющих входов 32,управляющие входы 33 - 37,Блок соединений (фиг.5) содержитР Р-разрядных информационных входов38 и Р Р-разрядных выходов 39, причем младшие разряды первого, второго Р-го входов 38 соединены соответственно с первым, вторым Р-м разрядом первого выхода 39, вторые разряды первого, второго Р-го входов 38 и соединены соответственно с первым, вторым Р - м разрядом второго выхода ЗЭ, аналогично старшие (Р-е) разряды первого, второго,.., Р-го входов 38 соединены соответственно с первым, вторым Р-м разрядом Р-го входа 39.Блок памяти (Фиг,б) содержит группу из Р Р-разрядных регистров 40, выходы 32, Р управляющих входов 41,управляющий:вход 42,Блок накапливающих сумматоров(фиг,) содержит информационные входы 43,группу изР 3 Р-разрядных входных сдвиговых регистров 44, группу из Р 3 Р-разрядных регистров 45 промежуточной памяти, группу из Р 3 Р- разрядных сумматоров 46, выходы 47, управляющие входы 48 - 52.Блок управления (Фиг,8) содержит входы 9 управления, узел 53 выбора режима выходы 54 - 59, элементы ИЛИ 60 - 62, входы 63 - 65, синхронизатор 66 вычислительного блока, узел 67 памяти адресов, синхронизатор 68 умножителей, синхронизатор 69 вычислительного блока, синхронизатор 70 накапливающих сумматоров, выходы 71-74.Узел выбора режима (Фиг.9) содержит Ю-триггеры 75, элемент НЕ 76, элементы ИЛИ 7, элемент И 78, шести- разрядный сдвиговый регистр 79(Р + + 1)-разрядный сдвиговый регистр 80, группу (из шести двухвходовых) элементов И 81.г 2 гУ гс рдг 2 г гю о г г г 2гс гю гс г 5 гб г 2 гз г 6 гд го г 2 2 г 2.Решетник Редакто Подписноого коиитета СССРний и открытийРаушская наб., д аказ 61 НАКИПИ по 1303ское енно-полиграфи оизвод го г/ г 2 гю го гк гг гк гг гз гф г Тираж 673осударственлам изобретМосква, Жго 2 г 2 гз г 4 гУ дприятие, г. Ужгород, ул. Проектная,4(6) 3 12954Синхронизатор вычислительного блока (фиг,10) содержит (Р + 1)-разрядный сдвиговый регистр 82, КБ-триггеры 83, элемент НЕ 84, элементы И 85.Синхронизатор умножителей (фиг.11) содержит (Р + 1)-разрядный сдвиговый регистр 86, КБ-триггеры 87, элемент НЕ 88, элементы И 89, элемент ИЛИ 90,Узел 67 памяти адресов (фиг,12) содержит КБ-триггеры 91, элементы 1 О НЕ 92., Р-разрядный сдвиговый регистр 93, элементы И 94,(Р + 1)-разрядный сдвиговый регистр 95, Р элементов ИЛИ 96.Синхронизатор накапливающих сум маторов (фиг,13) содержит КБ-триггеры 97, элементы И 98, элемент 99 задержки и элементы ИПИ 100.Конечная цифровая свертка представляет собой числовую процедуру, 20 определяемую следующим образом:Й у(п) = Ь(п-в) х(ш), и = 0,1,2,(1)ЙФО и символически обозначается как где х(п),Ь(п) и у(п) - последовательности30 чисел.Вычисление свертки можно проводить с помощью прямого и обратного преобразований Фурье-Галуа (ППФГ и ОПФГ):35У(п) = ППФГ)ПФГ)и) ПФГ 1 х 12) где ПНФГ н ОПФГ. вычисляются по .формуламй 1 40 ППФГх= ХЬ) =х (и) Х (и),ЬФО1 (3)1 фу ОПФГхД =х(п) = М ) ХЬ)Х (и),к:ои = (ФИ= 1, (4) 15 4где х(п) - цифровой сигнал заданныйна интервале И, т,е. в точках 0,1И - 1 и принимающий значения в множестве 0,1 И - 1ХЬ) - спектр Фурье-Галуа сигнала;)1.(п) - элемент матрицы ПФГ, который находится на пересечении К-й строки и п-гостолбца этой матрицы.Операции в выражениях (3) 12 (4) выполняются по модулю М, где М - порядок поля Галуса СР(М), на которым определяются ПФГ. Если в качестве первообразного корня из единицы Б-й степени "1)1 е СР(М), принадлежащего полю Галуа, выбрать 2, то выражение (3) записывается в матричном виде (М = 2 - 1, где М - число простое) В случае М = Р, Обратное преобразование вычисляется по выражению, аналогичному выражению (5), с той лишь разницей, что матрица Х(п) заменяется матрицей Х (и), учитывается нормирующий множитель и вектор- столбцы Х (и) и ХЬ) меняются местами, т.е. вычисление ОПФГ проводится по тому же алгоритму, чуо и вычисление прямого преобразования:5 1295415 6При вычислении ППФГ после пере столбец х(п) выражение (5) записымножения матрицы Х(и) на вектор- вается 2 х(0) + 2 х(1) + 2 х(2 У +,. + 2 х(Р) 2 х(0) +2 х(1) + 2 х(2)++ 2 х(Р) 2 х(0) +2 . х(1) + 2 х(2)++ 2 х(Р) Х(0) Х(1)В матрице-столбце (8), полученной из матрицы (7), слагаемые каждогоспектрального коэффициента ХВ) перегруппированы так, что структура выражений для каждого Х(Ес) получена одинаковой, причем умножение в выражениях (8) для каждого фхтр) производится на один и тот же мно О житель, равный двойке в степени, соответствующей номеру К спектрального коэффициента ХЬ).Вычисление ХЬ) состоит в умножении первого отсчета входной последовательности х(0) на 2 , суммировании полученного результата со следующим (вторым) отсчетом входной последова" тельности х(1) и умножении полученной суммы на 2; суммировании резуль" 50 тата последнего умножения со следующим (третьим) отсчетом входной последовательности х(2) и умножениик,полученной суммы на 2 суммировании результата последнего умно жения с последним Р-м отсчетом вход" ной последовательности х(Р) и умнок жении полученной суммы на 2 (выражение (8), 0 %1 сР). Поэтому в алгоритме вычисления Х можно выделить цикл, состоящий в суммировании результата предыдущего цикла со значением слецующего отсчета входной последовательности и умножении полуКчейной суммы на 2, Цикл для первого отсчета входной последовательности х(0) может быть представлен суммированием нуля с первым отсчетом вход. ной последовательности х(0) и умножением полученной суммы, т.е, первого отсчета,на 2". Таким образом алгоритм вычисления ХЬ) состоит в последовательном выполнении Р циклов.При вычислении свертки двух последовательностей выполняется операция поточечного перемножения значений спектральных коэффициентов этих последовательностей. Операция умножения двух Р-разрядных чисел Х и Н может быть записана как+2 (Х Ь+2 (Х Ьо + ОР- Р р Н= Ь;21-.о+ 5 25 х(п) =х .,(и)2 +х. (и);х (п) 1 ( 235Ь(п)=Ь,(п) 2 +Ь (п)1 1 Ь (п)1 2 ; (10)Свертка в этом случае определяетсяследующим образом;у(п) = х(п) 4 Ь(п) = (х(п)Ь(пхарф 2 + (з(п) Ь (п) + (11)+х (п)Ь (и)45Устройство производит свертку двух числовых последовательностей (по Р отсчетов, каждый отсчет представляет собой целое число, не превышающее М = 2 - 1, т.е. представ 2 Рляемое в двоичной системе счисления 2 Р-разрядным двоичным числом). С целью сокращения длины разрядной сетки в устройстве применяется разбиение входных 2 Р-разрядных слов на части, состоящие из двух Р-разрядных слов (в соответствии с выражением (10. При этом выходная свертка опПолученное выражение (9) соответствует структуре выражения (8) длявычисления Р-го спектрального коэф-,фициента Х(Р), в котором входныеотсчеты представляют последовательность из одинаковых чисел Х (первыйсомножитель), каждое из которых умножается на значение соответственнопервого Ь , второго Ь;,Р-гоЬр., разряда второго сомножителя Н(при умножении входного отсчета (первого сомножителя Х) на значение логической единицы входной отсчет остается неизменным, при умножении назначение логического нуля - входнойотсчет становится нулевым). Поэтомувычисление значений спектральныхкоэффициентов и умножеиие двух чисел можно производить по одним и темже алгоритмам,С целью сокращения длины разряд-ной сетки при сохранении динамического диапазона входных данных применяется разбиение входных слов начасти ределяется как сумма четырех частичных сверток согласно равенству (11). ,В результатеможно избежать применения псевдопреобразования Мерсенна и, следовательно, упростить устройство, а с другой стороны добиться сокращения разрядной сетки в 2 раза как и при использовании этого преобразования.Исходя из соображений удобства аппаратной реализации частичные свертки, составляющие слагаемые результатирующей свертки у(п) = х(п)Ь(п) вычисляются в следующей последовательности (слева направо):у(п) = (х,(п) - Ь (и 2 ++ (х (и) Ь (и 2Кроме того, ПФГ выполняется только для первой входной последовательности х(п),а значение спектральныхкоэффициентов второй входной последовательности НЬ), умноженные нанормирующий множитель М , сразу заносится с управляющей ЭВМ в блокпамяти устройства. Это обусловленотем, что при выполнении большинствазадач цифровой обработки сигналовизменяется только первая входная последовательность, а вторая входнаяпоследовательность при выполненииконкретной задачи цифровой обработкисигналов остается неизменной и представляет собой импульсную реакцию.При изменении задачи обработки вблок памяти устройства вводятся новые значения спектральных коэффициЭентов,Устройство работает следующим образом (Фиг. 1) .Входные данные, представляющиесобой отсчеты первой входной последовательности х(п), где 0 с иР,подаются по входной шине 7 на входблока 1. Причем числовая последовательность подается двумя частямих (и) и х (и) (х,(п), х (и) - числовые последовательности йз Р Р-разрядных отсчетов соответственно Рстарших и Р-младших разрядов Р входных 2 Р-разрядных отсчетов х(п. От9 129счеты числовых последовательностейх(п) и х (и) поступают на вход блока 1 последовательно во времени,причем подача последовательностейх,(п) или х (и) начинается по управляющему сигналу с блока 6 управления. Отсчеты второй входной последовательности НЬ) подаются по входной шине 8 на вход блока 5 памяти,также последовательно во времени,Управляющая ЭВМ связана с блоком буправления с помощью шины 9, Управляющая ЭВМ обеспечивает подачу первой и второй входной последовательности соответственно по шине 7 и шине 8, а также управление устройством в целом. Для синхронизации работы всех блоков устройства и выработки управляющих сигналов на вход блока 6 управления по шине 9 подаютсясигналы начальной установки, пускаи тактовой частоты. Процесс вычисления свертки делится на шесть этапов(фиг.14 - 17), в пределах каждогоиз которых работают те или иные блоки устройства в соответствии с управляющими сигналами, поступающими сблока 6 управления,5 10 последовательности х (и). С выходаблока 5 памяти на первый вход блока2 умножения поступают отсчеты первой 20 части второй входной последовательности Н,(1 с). На второй вход блока2 умножения подаются вычисленные вблоке 1 на первом этапе отсчетыспектральных коэффициентов Х Ь) 25 первой части первой входной последовательности х (и). На вход блока3 подаются отсчеты последовательности перемноженных спектральныхкоэффициентов ХЬ) Н Ь) с выхода 30 блока 2 умножения, Блок 1 производит ППФГ входной последовательностих (и) . Блок 2 умножения производитпоточечное умножение значений спектральных коэффициентов двух послеЗ 5 довательностей Х, Ь) и НЬ) . Блок3 производит ОПФГ последовательности ХЬ) Н Ос), поступающей на еговход, В конце третьего этапа работы на выходе блока 1 ПФГ появляются 40 вычисленные значения спектральныхкоэффициентов Х,(М, в блоке 2 умножения записываются значения отсчетов последовательности перемноженных спектральных коэффициентов 45 Х,Ь)1 Н,М , на выходе блока 3 появляются вычисленные значения свертки х,(п)и (п),которые записываются в блок 4 накапливающих сумматоров, С помощью последнего производит ся умножение частичных значений9 Р Р осверток на множители 2 , 2 и 2и суммирование результатов умноженияв соответствии с выражением (12).На четвертом этапе работают блок 55 5 памяти, блок 2 умножения, блок 3и блок 4 накапливающих сумматоров.С выхода блока 5 памяти на первыйвход блока 2 умножения поступают отсчеты второй части второй входной Устройство начинает работать после поступления на входы 9, и 9 блока 6 управления (Фиг.8) импульса начальной установки и запускающего импульса от управляющей ЭВМ, которые устанавливают все блоки устройства в начальное состояние и запускают блок 6 управления. При этом на первом этапе работают блок 1 и блок 5 памяти, а на, их входы по шинам 7 и 8 соответствено поступают отсчеты первой части первой входной последо." вательности х,(п) и отсчеты второй входной последовательности НЬ)Блок 1 производит ППФГ входной последовательности х,(п). После завершения первого этапа работы на выходе блока 1 ПФГ появляются значения спектральных коэФФициентов ХЬ) входной последовательности х (п). В блок 5 памяти на первом этапе работы устройства записываются 2 Р-разрядные значения отсчетов второй входной последовательности НЬ).На втором этапе работают блок 5 памяти и блок 2 умножения. Входные данные в блок 2 умножения поступают с блока 1 (ХЬ и с блока 5 памяти, Причем с последнего поступают отсчеты второй части Н Ь) второй 5415 10 входной последовательности НЬ),которые являются последовательностью из Р Р-разрядных отсчетов (Рразрядов младшей группы 2 Р-разрядных значений спектральных коэффициентов НЬ Блок 2 умноженияпроизводит по гочечное умножениезначений спектральных коэффициентовдвух последовательностей Х,(И иНЬ).На третьем этапе работают блок 1, блок 5 памяти, блок 2 умножения, блок 3 и блок 4 накапливающих сумматоров. На вход блока 1 поступают отсчеты второй: части первой входной11 12954 последовательности НЬ), На другой вход блока 2 умножения подаются вычисленные с помощью блока 1 на третьем этапе отсчеты спектральных коэффициентов Х Ь) второй части первой входной последовательности х (и), На вход блока 3 подаются отсчеты последовательности перемноженных спектральных коэффициентов Х,(К) Н ), вычисленные на третьем этапе с помо щью блока 2 умножения. Последний производит поточечное умножение значений спектральных коэффициентов двух последовательностей Х,Ь) и НЬ). Блок 3 производит ОПфГ после довательности Х Ь) НЬ), поступающей на его вход, Блок 4 накапливающих сумматоров производит умножение вычисленных на третьем этапе значений свертки х (и)Ь (и) на 201 Ямножитель 2 . В конце четвертого этапа работы в блоке 2 умножения за 1 писываются значения отсчетов последовательности перемноженных спектральных коэффициентов Х Ь)" Н Ь), на выходе блока 3 появляются вычисленные значения свертки х,(п) Ь(п), которые записываются в блок 4 накапливающих сумматоров. На пятом этапе работают блок 5 памяти, блок 2 умножения, блок 3 и блок 4 накапливающих сумматоров. С выхода блока 5 памяти на первый вход блока умножения 2 поступают отсчеты первой 35 части второй входной последовательности Н,Ь), На другой вход блока 2 умножения подаются вычисленные с помощью блока 1 на третьем этапе отсчеты спектральных коэффициентов Х Ь), 40 второй части первой входной последовательности х (п). На вход блока 3 подаются отсчеты последовательности перемноженных спектральных коэффициентов Х Ь)Н Ь),вычисленные на 45 четвертом этапе в блоке 2 умножения.Последний производит поточечное умножение значении спектральных коэффициентов двух последовательностей ХЬ)Н Ь). Блок 3 производит ОПФГ последовательности Х Ь) НЬ)Блок 4 накапливающих сумматоров производит умножение вычисленных на четвертом этапе значений свертким х (п),Ь, (и) на множитель 2 и сум мирование с предыдущим значением свертки, т.е, (х,(п)Ь (и 2 + + (х(п) + Ь,(п 2 ). В конце пято"в этапа работы в блоке 2 умножения 15 12записываются значения отсчетов перемноженных спектральных коэффициентовН,Ь)Х(Е),на выходе блока 3 появляются вычисленные значения свертких(п) + Ь (и), которые записываютсяв блок 4 накапливающих сумматоров,На шестом этапе работают блок 3и блок 4 накапливающих сумматоров.На вход блока 3 подаются отсчетыпоследовательности перемноженных спектральных коэффициентов Х Ь) Н, Ь)Блок 4 накапливающих сумматоров производит умножение вычисленных на пятом этапе значений свертки х (и)1(п,на множитель 2и суммированйе с предыдущими значениями свертки, т.е.+ (х (и) м Ь (и 2. В конце шестогоэтапа работы на выходе блока 3 появляются вычисленные значения свертких (и)- Ь,(п), которые записываютсяв блок 4 накапливающих сумматоров,умножаются с помощью этого блока намножитель 2 и суммируются с предыдущими значениями свертки, т.е. навыходе блока 4 накапливающих суммато 1 ров появляются значения отсчетов вы,ходной свертки, соответствующей вы;ражению (12). После завершения шестого этапа работы устройство готово кобработке следующей последовательности входных данных,Блок 1 работает следующим образом.Входные данные, представляющие собой отсчеты числовой последователь. ности х,(п) или х (и) (Р отсчетов по Р разрядов каждый), подаются по шине 7 последовательного ввода на входы регистров 11, - 11 р группы входных регистров 11 (фиг.2, 15). Вход 15 объединяет входы тактовой частоты входных РегистРов 11, - 11,р (Р регистров представляют собой группу Р-разрядных регистров хранения данных с записью по переднему фронту импульса). В момент йоступления первого отсчета входной последовательности (например, х(0 х,(п) на вход 15 с блока б управления поступает первый импульс тактовой частоты. С постунлением этого импульса первый отсчет записываеч- ся во все входные регистры 11 и с их выходов поступает на вторые входы (входы В) сумматоров 20 блока 12 накапливающих сумматоров по модулю М (фиг.3). Импульсом, поступающим13 12на вход 17 (вход 25 на фиг.З) синхронно с первым импульсом тактовойчастоты, производится обнуление ре-.гистров 19 промежуточной памяти бло -ка 12 накапливающих сумматоров помодулю М. На вход 16 (вход 24,фиг.З)объединяющий входы тактовой частоты регистров 19 промежуточной памяти,поступают импульсы тактовой частоты, сдвинутые во времени на половину периода тактовых импульсов. До момента поступления первого импульса тактовой частоты на вход 16 значение первого отсчета х(0) входной последовательности, поданное навторые входы сумматоров 20, суммируется с данными, поступившими на первые входы (входы А) сумматоров 20 с выходов регистров 19 промежуточной памяти (нулевые значения), и полученная сумма поступает на входы умножителей 21 на степени двойки. Первый умножитель 21 на степени двойо ки производит умножение на 2 , второй умножитель 21 - на 2 Р-й умножитель 21 - на 2 Р .Полученные в результате умножения произведения х;,(0) 2 (где Е - номер вычисляемого спектрального коэффициента Х Ь), 01Р) поступают на входы регистров 19 промежуточной памяти и с приходом первого импульса тактовой частоты, поступающего на вход 16, записываются в эти регистры промежуточной памяти. Операция суммирования выполняется по модулю М = 2 - 1, что реализуется путем суммирования возможного переноса в (Р + 1)-й разряд с младшим разрядом в каждом сумматоре 20. Для этого выход переноса сумматора 20 соединен. с его же входом переноса. Операция умножения на степени двойки. реализуемая умножителями 21; - 21 р на степени двойки, производится по модулю целоГо числа М = 2 - 1, где. Р - простое число, Поэтому умножения на степени двойки представляют собой ыупслические сдвиги кодового слова. Реализовать умножение на степени двойки по модулю М = 2 - 1 можно простой коммутацией проводов. Симво" лически операция умножения на степен цвойки изображена в виде Р блоков 21 (для случая Р7 реализация этихблоков показана на Фиг.18).В момент поступления второго отсчета входных данных на вход 15 по" 95415 14ступает второй импульс тактовой частоты и второй отсчет входной последовательности х (1) записывается вовсе входные регистры 11 и с их выходов поступает на вторые входы сумматоров 20. На выходах последних формируются суммы поступивших на вторыевходы (входы В) данных с входных регистров 11 (х)(1 и данных, посту пивших с выходов регистров 12 промежуточной памяти записанных в них на1Кпредыдущем цикле (х (0) 2 ), т.е.формируется сумма х,(1) + х(0) 2Значения суммы с выходов сумматоров20 поступают на блоки 21 умножителейна степени двойки и с их выходов подаются на входы регистров 19 про- -межуточной памяти. Второй импульс,поступающий на вход 16, разрешает запись в регистры 19 данных, поданных на их входы, т.е.2 (х,(1) + 2 х,(О. В момент поступления третьего от -счета входных данных х,(2) цикл работы блока 1 повторяется и в регистры 19записываются накопленные за три цикла в каждом сумматоре 20 значения 30 частичных сумм соответствующих спектральных коэффициентов, Такой процесс повторяется Р раэ. На Р-и циклев момент поступления Р-го отсчетавходных данных ыа вход 15 поступает 35 Р-й имцульс тактовой частоты и Р-йотсчет входной последовательностих (Р) записывается во все входныерегистры 11 и с. их выходов поступаютна вгорые входы сумматоров 20. На вы ходах последних Формируются суммы,поступивших на вторые входы (входы В)анных с выходов входных регистров 111+ 2"(х,(Р-З) 2"(х(1) + 0 + 2 х,(0), 0 1 с Рс выходов сумматоров 20 поступают наблоки 21 умножителей на степенидвойки и с выходов этих блоков подаются на входы регистров 19 проме жуточной памяти. Р-й импульс, поступающий на вход 16, разрешает запись в регистры 19 данных, поступивших на, их входы в соответствиис выражением+ 2" (х (1) + 2 х,(0).Это выражение полностью совпадает с выражением (8) для спектральных коэффициентов, в котором каждому спектральному коэффициенту Х, Ь)10 соответствует выражение (13) (О1 сР). Значения Р спектральных коэффициентов Х,Ь) с выходов регистров 19 поступают на входы выходных регистров 13 блока 1 ПФГ и при поступлении на вход 18 разрешающего импульса, совпадающего по времени с (Р+1)-м импульсом тактовой частоты (Фиг. 15), записываются в регистры 13. Таким образом в конце действия (Р+1)-го импульса тактовой частоты блок 1 заканчивает вычисление ПФГ, а на Р Р-разрядных выходах блока 1 появляются значения спек тральных коэффициентов Х Ь) и блок 1 готов к обработке следующей последовательности входных данных.Блок 3 устройства производит ОПФГ последовательности значений спектральных коэффициентов, например, Х,Ь) н,Ь).Номирующий множитель М , который вводится при вычислении ОПФГ по равенству (4), учитывается в последовательности НЬ), отсчеты кото 35 рой поступают с управляющей ЭВМ уже умноженные на И ". Замена (5) матрицы степеней двоек ,Х ф (и) на маткРицу (6)Х (и), которая отличается только расположением строк, учитывается в блоке 3 путем перестановки умножителей 21 - 21 на степени двойки в соответствии с перестановкой строк матрицы Хк (и). При этом сохраняется порядок йомеров выходов блока 3 и, фактически, "он ничем не отличается от блока 1.Схема блока 3 совпадает со схемой блока 1 (Фиг.2 и 3) с той лишь разницей, что умножители 21, - 21 на степени двойки построены следующим образом: умножитель 21 осуществляет умножение на 2, умножитель 21 - на 2 , умножитель 21 - на 2 умножитель 21 - на 2 Р з умножитель 21 р - на 2 . Временная диаграмма работы блока 3 приведена на Фиг.16 и 17 (в блоке 3 с целью удобства описания устройства номера управляющих выводов даются в скобках).Блок 2 умножения производит поточечное умножение значений спектральных коэффициентов и работает следующим образом (Фиг.4, 3 и 15).Входные данные, представляющие собой отсчеты двух числовых последовательностей Х (М или Х Ь) первыхсомножителей и Н, Ь) или Н Ь) вторых сомножителей, например ХЬ) иНЬ), подаются соответственно навходы 26 входных регистров 27 и входы32 установки логического нуля этихже входных регистров. Причем значения первого, второго Р-го спектральных коэффициентов первых сомно-жителей Х,Ь) или Х (1 с) поступаютв параллельном коде соответственнона Р-разрядные входы 26 первого,второго, , Р-го входных Р-разрядных регистров 27, а значения,первого, второго, , Р-го спектральных коэффициентов вторых сомножителей Н, (к) или Н Ь) поступают в последовательном коде (поразрядно,начиная с младших разрядов) на одноразрядные входы 32 установки логического нуля соответственно первого32 второго - 32 Р-го - 32 рвходных регистров 27. Импульсы тактовой частоты с блока 6 управленияпоступают на вход 33 блока 2 умножения. Вход 33 объединяет входы тактовой частоты группы входных регистров 27. С поступлением первогоимпульса тактовой частоты значенияпервых сомножителей (например,х Ь) )записываютсяво входные регистры 27и с их выходов поступают на вторыевходы сумматоров 20 блока 28 накапливающих сумматоров по модулю М(фиг. 3),Первым импульсом тактовой частоты, поступающим на вхоД 35, производится также обнуление регистров 19 промежуточной памяти блока 28 накапливающих сумматоров по модулю М (номера управляющих входов 34 и 35 блока 28, используемого в блоке 2 умножения, указаны в скобках,фиг.3). Такая нумерация введена для удобст;ва описания блока 6 управления.,В это же время на входы 32 установки логического нуля входных регистров 27 поступают значения первых (младших) разрядов вторых сомножителей (например, Н Ь, которые корректи