Устройство для быстрого преобразования фурье Советский патент 1980 года по МПК G06F17/14 

Наличие большого числа коммутйрУкщих элементов и шин в коммутирующей матрице является существенн препятствием для ее микроминиатюри зации. Кроме того, пересылка oneрандов после каждой итерации требует определенных затрат времени и наличия специальных сигналов для управления коммутирукхцей матрицей. Цель изобретения - сокращение общего объема используемого оборудования и повышение быстродействия Поставленная цель достигается т что в устройство, содержащее первый л второй регистры, регистр маски, памяти коэффициентов, матрицу ассоциативной памяти, состоящую из Ы/2 /строк (где N - количество точек в исходной последовательности отсчето каждая из которых состоит из десяти ячеек, соединенных своими установЬч ными входами через регистр маски с выходами первого регистра, а выхода ми -со входами второго регистра,, входы пятой и шестой ячеек соединен с соответствующим номеру строки выходом памяти коэффициентов, первый и второй коммутаторы, дополнительно введены третий и четвертый коммутаторы, при этом вход первого коммутатора соединен с выходами первой, третьей, пятой, шестой, седьмой и десятой ячеек каждой строки, а выход - со входами , девятой ячеек каждой строки и с первым выходом разрешения записи строки матрицы ассоциативной памяти, вход второго коммутатора соединен- с выходами второй, четвертой, йятой, шестой, восьмой и девятой ячеек каждой строки, а выход - со входами восьмой и десятой ячеек и вторым выходом разрешения записи строки матрицы ассоциативной памяти, вход третьего коммутатор.а соединен с выходами восьмой и девятой ячеек каждой строки,а выход - с третьим выходом разрешения записи строки матрицы ассоциативной памяти, вход четвертого коммутатора соединен с выходами седьмой и десятой ячеек каждой строки, а выход - с чет чертым выходом разрешения записи строки ассоциативной памяти, входы первой, второй, третьей, четвертой ячеек каждой строки соединены с соответствующими входами строки матрицы ассоциативной памяти. Математические действия, выполняемые по каждому двухточечному преобразованию. Обо1значим:; ,,a,cos, 8, в, -. i. пары входных выборок, причем Значения выходных выборок Z( и 2 вычисляются ;ледующим образом Zg-Z-,Zp(.()(« 4-jbJ, ..(.,(VJVpy«dbKV Объединяя мнимые и действительные части, получаем .Уp(ЛaкVЬк pV- e iVe, 2 m° ;t°K p- Vj( Значения-Zg и z пересылаются на входы для выполнения над ниМи очередных итерацией. На чертеже представлена схема устройства. Устройство содержит матрицу ассоиативной памяти, состоящую из одинаковых строк 1, коммутаторы 2 () память 3 коэффициентов, регистр 4 маски, первый регистр 5, второй регистр 6. Устройство работает следуюцйм образом. Каждая строка 1 (ячейка памяти АПП) азделена на 10 ячеек: в первой ячейе хранится значение xj, во второй у , в третьей Хр, в четвертой - Ур, пятой - а, в шecтoй-в, седьмая, осьмая, девятая и десятая ячейки езервируются для промежуточных результатов вычислений, В каждой итерации информация всех трок обновляется. Значения z-, и Zp аменяются результатами вычислений предьвдущих итераций, вводятся новые оэффициенты а 1 и Ь , В каждой итерации вычисления выоляются в следующем порядке. 1-й этап.Одновременные умножения: (а) (хр) - 7 ячейка (э(). (Ур) -V 8 ячейка 2-й этап.Одновременные сложения: (р ) + (х;) - 9 ячейка (Рг) + (У1 )- 10 ячейка 3-й этап.Одновременные умножения (Ь ) (хр) - 7 ячейка (Ьк)- (Уу) - 8 ячейка После выполнения первых трех этапов получаются промежуточные результаты, которые размещены в ячейках 7 - 10 тех же строк, где хранятся исходные величины. Соответствующие пересылки промежуточных результатов вычислений осуществляются с помощью первого и второго коммутаторов. После завершения размещения промежуточных, результатов вычислений в ячейках 7-10, выполняются еще два этапа: 4-й этап.Одновременные сложения 7ячейка + 10 ячейка- Уе (UC) 8ячейка + 9 ячейка- х(ис) 5-й этап.Одновременные вычитания: 9ячейка-8 ячёйка- Хв(иС j) 10ячейка-7 ячейка- у(ис) Результаты операций, произведенны в процессе выполнения 4-го и 5-го этапов, размещаются в зонах у , х, Xg и у соответствующих строк ассоциативной памяти. Такое размещение результатов вычислений обеспечивается путем подключения разрешающих запись входЬй этих ячеекi соответственно к выходам первого, второго, третьего и четвертого коммутаторов (UC - UC). Одновременно с выполнением 5-го этапа любой из итераций в зоне а и Ь всех строк 1 вводятся новые значения коэффициентов w, хранимые в постоянной памяти 3. После окончания 5-го этапа устройство готово к выполнению очередной итера ции. Коэффициенты Фурье образуются в зонах X и у всех строк после завершения всех tog. итераций, аналогич ных описанной. Формула изрЪретения Устройство для быстрого преобразования Фурье, .содержа1дее первый и второй регистры, регистр маски, память коэффициентов,матрицу ассоциа тивной памяти, состоящую из стро (где N - количество точек в исходно последовательности отсчетов), кажда из которых состоит из десяти ячеек, соединенных своими установочными входами через регистр маски с выход ми первого регистра, а выходами - с входами второго регистра, входы пятой и шестой ячеек соединены с соот ветствующим номеру строки выходом памяти коэффициентов, первый и второй коммутаторы, отличающее с я тем, что, с целью повышения быстродействия и сокращения оборут дойанйя, в- него дополнительно введены третий и четвертый коммутаторы, при этом вход первого коммутатора соединен с Выходами первой,третьей,пятой,шестой,седьмой и десятой ячееккйгтаой строки, а выход - со входами седьмой, девятой ячеек кгикдой строки и с первым выходом разрешения записи строки матрицы ассоциативной памяти, вход второго коммутатора соединен с выходами второй, четвёрТоЙ, пятой, шестой, восьмой и девятой ячеек каждой строки, а выход - со входами Ьосьмой и десятой ячеек и вторым выходом разреше ния записи строки матрицы ассоциативной памяти, вход третьего Коммутатора соединен с выходами восьмой и:девятой ячеек каждой строки, а выхац с третьим выходом разрешения записи строки матрицы ассоциативной памяти, ,вход четвертого коммутатора соединен выходами седьмой и десятой ячеек каждой строки, а выход - с четвертый выходом разрешения записи строки ассоциативной памяти, входы первой, второй, третьей, четвертой ячеек каждой строки соединены с соответствующигли входами строки матрицы ассоциативной памяти. Источники информации, принятые во внимание при экспертизе 1 .Tonkin А., Savage J,- An Арр cation of Correlation to Rader Systemsl, The Radio and &. gag . W 12, W 7, 1972. 2. Прангишвили И.В. Однородные микроэлёкт Ё Ьн 1ыё ВёсШиё йвнШ пр соры. М., Советское радио , 1973 (прототип).