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

368 ёходшми третьего, четвертого, пятого и шестого элементов И-ИЛИ и с первым входом из второй группы входов схемы сравнения, выход сумматора-вычитателя через 5inoK умножения соединен со вторыми входами третьего и четвертого элементов И-ИЛИ, первыми входами седьмого и восьмого элементов И-ИЛИ, вторым входом из второй группы, входов схемы сравнения, вход четвертого элемента И-ИЛИ соединен с вторыми входами пятого, шестого, седьмого и восьмого . элементов И-ИЛИ, выходы которых через соответствующие блоки памяти соединены соответ ствекно ; вторыми, третьими, четвертыми и пяшлш входалш первого и второго коммутаторов, выход третьего элемента И-ИЛИ является инфор мационным выходом устройства, выход схемы сравнения является контрольным выходом устройства. На чертеже приведена структурная схема предлагаемого устройства. Оно имеет блоки памяти 1, 2, 3, 4, 5, 6, сумматор 7, сумматор-вычитатель 8, блок умножения 9, блок 10 хранения весовых коэффициентов, вход 11, элементы И-ИЛИ 12. 13, 14, 15, 16, 17, 18, 19, коммутаторы 20, 21, схему сравнения 22.. Устройство реализует два алгоритма БПФ: X, . (2к) х(к) -t-i (к ) (2к - I) х (к) - X,- (к )3w (i+l)(K) .Х4 (2к) + х (2к + 1) (i+l)(K + -r ) (2к) - i,-(2KH-l)-w5 где i - номер итерации ( i 1 4- 1092 N); к - номер выборки ( к О т- N(2-1); ( -jl., wn , -. весовой коэффициент, зависящий от номера выборки и номера итерации . При реализации алгоритма (i) входная последовательность поступает в естественном порядке; запись входной информации, состоящей из 2 N комплексных выборок, в блоки 1 и памяти осуществляется следующим образом: пер вые N/2 выборок через элемент И-ИЛИ 13 в блок памяти 1, последующие IM/2 выборок (от N/2 + 1 до N) через элемент И-ИЛИ 12 в блок 2 памяти. После записи входной информации начинается обработка ее по алгоритму (i). Первая пара входных выборок хо(0) и 3le(N/2 + О) по одной считаются соответственно из блоков } и 2 памяти я через коммутаторы 20 ш 21 поступает на входы сумматора 7 и сум матора-вычитателя 8, причем значение Хо (N/2+0 на вход сумматора-вьгаитателя 8 поступает обра ным кодом. С выхода сумматора 7 полученное .здачение .Xi (0) Хо (0) + Jto(N/2 + 0) через лементы И-ИЛИ 14 и 15 записьгеается в блок 3 амяти. Значение с сумматора-вычитателя 8 хо (0) - Хо (N/2 -t-0) поступает на первый ход блока 9 умножения, одновременно на второй его вход из блока 10 хранения весовых коэ(Ьфициентов поступает соответствующее значение (w°), результат с выхода блока 9 умножения i(l) хо(0) - xo(N/2 + 0)1 w через элементы И-ИЛИ 14-15 записывается вслед за Xi (0) в блок 3 памяти. Затем вторая пара чисел аналогично описанному считывается из блоков 1 и 2 памяти и через коммутаторы 20 к 21 поступает на входы сумматора 7 и сумматора-вьшитателя 8, конечщ ш результат с выхода cyNfwaTOpa 7 и блока 9 умножения через элементы И-ИЛИ 14 и 15 записьгаается в блок 3 памяти. Так повторяется N/4 тактов. Через N/4 тактов блок 3 памяти, о оказывается заполненным и следующая пара полученных результатов через элементы И-ИЛИ 14 и 16 записью ается в блок 4 памяти. Так продолжается N/4 раз. После заполнения блока 4 заканчивается первая итерация. Во второй итерации считывание информации производится из блоков 3 и 4 памяти через соответствующие коммутаторы 20 и 21. Весь процесс идет аналогично описанному, только запись полученных результатов первые N/4 тактов через элементы И-ИЛИ 14 и 17 последовательно один за другим идет в блок 5 памяти, а вторые N/4 тактов через элементы И-ИЛИ 14 и 18 в блок 6 памяти. В третьей итерации (и в последующих нечетных итерациях) информация считывается одновременно из блоков 5 и 6 памяти, а записывается последовательно в блоки 3 и 4 памяти, а в четных итерациях они меняются местами (т.е. считывание идет из блоков 3 л 4 памяти, а запись в блоки 5 и 6 памяти. По окончании последней итерации счигыва- . ние информации через элемент И-ИЛИ 19 с выходов сумматора 7 и блока 9 умножения поCTjTiaeT на выход устройства в дво1гано-инверсном по отнощению к естественному порядку. При работе по алгоритму (2) входная инфор,мация поступает в двоично-инверсном-порядке, запись входной информации идет поочередно по одному слову в блоки 1 и 2 памяти. Первая парц чисел, считьгеаемых из блоков 1 и 2 памяти, через коммутаторы 20 к 21 обрабатывается в соответствии с формулами (2) аналогично алгоритму 1. Полученные результаты с выхода сумматора 7 в первой итерации (ив остальных нечетных итерациях) через элемент ИИЛИ 15 записываются в блок 3 памяти, а в четных итерациях в блок 5 памяти через элемент И-ИЛИ 17. Запись результатов с выхода блока 9 умножения в нечетных итерациях через элемент И-ИЛИ 1 б идет в блок 4 памяти, а в четных итерациях через элемент И-ИЛИ 18 - в блок 6 памяти. Считывание информации во всех итерациях из блоков 3 и 4 памяй идет последовательно по два числа из каждого блока памяти в течение N/4 тактов через коммутаторы 20 и .21. Аналогично в других итерациях идет считывание из блоков 5 и 6 памяти. Окончательный результат, как и в алгоритме (1), поступает на выход устройства с выходов сумматора 7 н бло ка 9 умножения через-элемент И-ИЛИ 19. Входная информация в режиме контроля через элементы И-ИЛИ 12 и 13 с выходов блок 1 и 2 памяти записывается на входы этих же бл ,ков. После реализации прямого преобразования Фурье по алгоритму (1) или (2) осуществляется ъ.- - я .«гЧ. .:..1 |- обратное преобразование Фурье N ) но по другому алгоритму, т.е. если прямое Преобразование осуществляется по алгоритму (1), обратное преобразование будет осуществляться по алгоритму (2), так как результат прямого преобразования оказывается записанным в блоки памяти в двоично-инверсном по отнощению к входному порядке. Результат прямого преобразования оказывается записанным либо в блоки 3 и 4 памяти, либо в блоки 5 и 6 памяти (в зависимости от числа итераций). Поэтому дпя обратного преобразования Фурье в первой итерации информация считывается из этих блоков в соответствии с необхошшым алгоритмом через коммутаторы 20 и 21. В последней итерации информация с выхо дов сумматора 7, блока 9 умножения и с выходов блоков 1 и 2 памяти поступает .на схему сравнения. Результат сравнения поступает на кон . рольный выход устройства.. Фо рмула изобретения Устройство для реализации быстрого преобразования Фурье, содержащее сумматор-вычитатель, блок умножения, сумматор, блоки памяти, блок хранения весовых коэффициентов, элемен ты И-ИЛИ, причем входы блока умножения соединены соответственно с выходом блока хранения весовых коэффициентов и выходом сумматора-вычитателя, отличающееся тем, что, с целью повышения надежности работы устройства вработе, оно содержит схему сравнения и два коммутатора, причем вход устройства соединен с первыми входами первого и второго элементов И-ИЛИ, вторые входы которых подключены к первой группе входов схемы сравнения, соответственно к первым входам первого и второго коммутаторов и соответственно к выходам первого и второго блоков памяти, входы которых соединены соответственно с выходами rifepBoro и второго элементов И-ИЛИ, выходы первого и второго коммутаторов соединены соответственно с первыми и вторыми входами сумматора и сумматора-зучитателя, выход cjTsiMaiO . pa соединен с первыми входами третьего, четвертого, пятого и шестого элементов И-ИЛИ ц с первым уходом из второй грушы входов схемы сравнения, выход С)адматора-вычшгателя через блок умножения соединен со вторыми входами третьего и четвертого элементов И-ИЛИ, первыми входами седьмого в восьмого элементов И-ИЛИ, вторьпч входом из второй группы входов схемы сравнения, выход четвертого элемента И-ИЛИ отедиаен с вторыми входами пятего, щестого, седьмого и восьмого элементов И-ИЛИ, выходы которых через соответствующие блоки памяти соединены соответстве}шо с вторыми, третьими, четвертыми и пятыми входами первого и второго коммутаторов, выход третьего элемента И-ИЛИ является информациогшым выхо- . дом ус-фойства, выход схемы сравнения является контрольным выходом устройства. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР ЬР 421994, кл. G 06 F 15/34, 1974. 2.Патент Франции № 2082030, G 06 F 15/00, 1971.