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

к третьему входу узла блокировки, выход переполнения счетчика подключен к входу управления сдвигом регистра итераций, параллельный выход регистра итераций подключен к второ му информационному входу узла элементов И, выход первого разряда регистра итераций подключен к управля щему входу узла элементов И, к второму входу элемента Пик четвертому входу узла блокировки,выход (п+1)разряда регистра итераций подключен к пятому входу узла блокировки, выход узла формирования инверсного ко да подключен к суммирующим входам первого и второго вычитателей, выходы которых поразрядно подключены информационным входам разрядов с вт рого по (п+1)-ый первого и второго кольцевых регистров сдвига соответственно, входы управления сдвигом первого и второго кольцевых регистров сдвига подключены соответственно к первому и второму выходам узла блокировки, выходы второго кольцевого регистра сдвига, узла элементов Н, прямой выход второго триггера, второй выход узла синхронизации выход первого кольцевого регистра сдвига, инверсный выход второго три гера, третий и четвертый выходы узп блокировки являются выходами блока управления с первого по восьмой соответственно. Т. Устройство по п. отличающееся тем, что узел блокировки содержит элементы ИЛИ-НЕ, ИЛИ, НЕ, три сумматора по модулю дв два элемента И-НЕ, шесть элементов И и триггер, причем вход элемента НЕ является четвертым входом узла блокировки и соединен с первыми вхо дами первого сумматора по модулю дв 06 и элементна ШШ, второй вход первого сумматора по модулю два явля- ется пятым входом узла блокировки, входы эл мента ИЛИ-НЕ с первого по являются соответс вукяцими разрядами третьего входа узла блокиров-. ки, причем п-ый вход элемента ИЛИ-НЕ соединен с инверсным входом триггера, выход элемента НЕ подключен к первым входам первого и второго элементов И-НЕ, а также первого и второго элементов И, выход элемента ИЛИ-НЕ подключен к второму входу элемента ШВ, выход которого подключен к первым входам третьего и четвертого элементов И,вторые входы третьего и четвертого элементов И являются соответц ственно первым и вторым входами узла блокировки, выход третьего элемента И подключен к второму входу первого элемента И и к прямому выходу пято- го элемента И, выход четвертого элемента И подключен к второму входу второго элемента И и к прямому входу шестого элемента И, инверсные входы пятого и шестого элементов И подключены к выходу первого сумматора по модулю два, выходы пятого и шестого элементов И являются соответственно третьим и четвертым выходами узла блокировки, прямой и инверсный выходы триггера подключёшы к вторым входам первого и второго элементов И-НЕ соответственно, выходы первого и второго элементов И-НЕ подключены к первым входам второго и третьего сумматоров по модулю два, вторые входы которьк подключены к выходам второго и первого элементов И соответственно, выходы второго и третьего сумматоров по модулю два являются соответственно вторым и первым выходами узла блокировки.

I. УСТРОЙСТВО ДЛЯ РКАЛИЗАЦШ БЕЗЫЗБЫТОЧ110ГО АЛГОРЯгаЛ БЫСТРОГО ИРЕОБРАЗОБЛНИЯ ЛУРЬК, содержащее арифметический блок, блок постоянной памяти, первый блок оперативной памяти и блок управления, причем выход первого блока оперативно - памя- ти и выход блока постоянной памяти подключены соответственно к входу операндов и входу коз(})4)ициентов арифметического блока, выход которого подключен к информационному входу первого блока оперативной памяти, первый и второй выходы блока управления подключены к адресным входам первого блока оперативной памяти и блока постоянной памяти соответственно, третий выход блока управления подключен к входу управления записьюсчитыванием первого блока оперативной памяти, четвертый выход блока управления подключен к синхронизирующему входу арифметического блока, отличающее ся тем, что, с целью повьш1ения быстродействия и расширения фулкп.иональных возможностей устройства, состоящего в вычислении пресбразования одновременно до четырех последовательностей входньсх отсчетов, оно содержит второй блок оперативной памяти, причем пятый и шестой выходы блока управления подключены соответственно к адресному входу и входу управления записью-считыванием второго блока оперативной памяти, седьмой и восьмой выходы блока управления подключены к входам обращения первого и второго блоков оперативной памяти соответственно, выход второго блока оперативной памяти подключен к входу операндов арифметического блока, причем блок управления содержит узел синс хронизации, два триггера, п-разрядный счетчик (n log2N; N - объем вы(Л борки), (п+1)-разрядный регистр итераций, узел элементов И, узел формирования инверсно1о кода, элемент И два вычитателя, два (п+1)-разрядных кольцевых регистра сдвига и узел блокировки, причем первый выход узла синхронизации подключен к счетному входу первого триггера, выход которого подключен к счетному входу второго триггера, первому входу элемента И и к информационным входам первых разрядов первого и второго кольцевых регистров сдвига, прямой выход второго триггера подключен к входу счетчика, вычитающему входу первого нычитателя и к первому входу узла блокировки, инверсны выход второго триггера подключен к вычитаюи(ему входу второго вычитателя и к второму входу узла блокировки, параллельный выход счетчика подключен к первому информацпопному входу узла элементов И, к информационно ty входу узла формиров;шия инверсного кода и

Изобретение относится к автоматике и вычислительной технике и может быть использовано для решения задач спектрально-корреляционной обработкь последовательностей действительных сигналов.

Известно устройство для реализации быстрого преобразования Фурье,

содержащее узел реконфигурации счетчика, счетчик, регистр, группу элементов ИЛИ и блок ,выдачи адресов 1 .

Недостатком известного устройства является сложность построения, малое быстродействие и отсутствие возможности формирования адресов значений экспоненциальных множителей, храня- 3. щихся в постоянной памяти и предназначенных для выполнения элементарных операций БПФ. Кроме того, без дополнительных аппаратурных затрат это устройство не может реализовать алго ритм БПФ с замещением. Известно устройство для реализации алгоритма быстрого преобразования Фурье, содержащее блоки постоянной и оперативной памяти,ариф метический блок и блок управления. Выходы блока постоянной памяти и блока оперативной памяти подключены к входам арифметического блока, выходы блока управления - к управляющим входам блока постоянной памяти, блока оперативной памяти и арифметического блока 2. К недостаткам известного устройства следует отнести малую эффективность работы арифметического блока, поскольку основное время, требуемое для выполнения элементарной операции БПФ, затрачивается на запись и считы вание операндов при обращении к блоку оперативной памяти.Кроме того,в ряде задач спектрально-корреляционной обработки сигналов возникает необходимость одновременного вычисления преобразования Фурье трех и даже четырех последовательностей действительных чисел, что не может обеспечить известное устройство. Цель изобретения - повышение быст родействия и расширение функциональных возможностей устройства, состоящее в вычислении преобразования одновременно до четырех последовательностей входных отсчетов. Поставленная цель достигается тем что устройство для реализации безызбыточного алгоритма быстрого преобразования Фурье, содержащее арифметический блок, блок постоянной памяти, первый блок оперативной памяти и блок управления, причем выход первого бло- ка оперативной памяти и выход блока постоянной памяти подключены соответ ственно к входу операндов и входу ко эффициентов арифметического блока, выход которого подключен к информационному входу первого блока оперативной памяти, первый и второй выходы блока управления подключены к адресным входам первого блока оперативной памяти и блока постоянной памяти соответственно, третий выход блока управления подключен к входу управления записью-считыванием пер06вого блока оперативной памяти, четвертый выход блока управления подключен к синхронизирующему входу арифметического блока, содержит второй блок оперативной памяти, причем пятый и шестой выходы блока управления подключены соответственно к адресному входу и входу управления записью-считьшанием второго блока оперативной памяти, седьмой и восьмой выходы блока управления подклмчены к входам обращения первого и второго блоков оперативной памяти соответственно, выход второго блока оперативной памяти подключен к входу операндов арифметического блока, причем блок управления содержит узел синхронизации, два триггера, п-разрядный счетчик (n logjN; N - объем выборки),(п+1) разрядный регистр итераций, узел элементов И, узел формирования инверсного кода, элемент И, два вычитателя, два (п+О-разрядных кольцевых регистра сдвига и узел блокировки, причем первый выход узла синхронизации подключен к счетному входу первого триггера, выход которого подключен к счетному входу второго триггера, первому входу элемента И и к информационным входам первых разрядов первого и второго кольцевых регистров сдвига, прямой выход второго триггера подключен к входу счетчика, вычитающему входу первЬго вычитателя и к первому входу узла блокировки, инверсный выход второго триггера подключен к вычитающему входу второго вычитателя и к втоpofiy входу узла блокировки, параллельный выход счетчика подключен к первому информационному входу узла элементов И, к информационному входу узла формирования инверсного кода и к третьему входу узла блокировки, выход переполнения счетчика подключен к входу управления сдвигом регистра итераций, параллельный выход регистра итераций подключен к второму информационному входу узла элементов И, выход первого разряда регистра итераций подключен к управляюще- му входу узла элементов И, к второму входу элемента Инк четвертому входу узла блокировки, выход (п+1)-го разряда регистра итераций подключен к пятому входу узла блокировки, выход узла формирования инверсного кода подключен к суммирующим входам первого и второго вычитателей, выходы которых поразрядно подключены к информационньм входам разрядов с второго по (п+1)-ый первого и второго кольцевых регистров сдвига соответственно, входы управления сдвигом перяо о и второго кольцевых регистров сдвига подключены соответственно к первому и второму выходам узла блокировки, выходы второго кольцевого регистра сдвига, узла элементов И, прямой выход второго триггера, второй выход узла синхронизации, выход первого кольцевого регистра сдвига, инверсный выход второго триггера, третий и четвертый выходы узла блокировки ;являются выходами блока управления с первого по восьмой соответственно. Кроме того, узел блокировки содержит элементы , ШШ, НЕ, три сумматора по модулю два, два эле мента Н-НЕ, шесть элементов И и триг гер, причем вход элемента НЕ является четвергым входом узла блокировки и соединен с первыми входами первого сумматора по модулю два и элемента iijttl, второй вход первого сумматора по модулю два является пятым входом узла блокировки, входы элемента ИШ1НЕ с первого по п-ый являются соответствующими разрядами третьего вхОг да узла блокировки, причем п-ьш вход элемента 1ШИ-НЕ соединен с инверсным входом триггера, выход элемента НЕ подключен к первым входам первого и второго элемента Н-НЕ, а также первого и второго элементов И, выход элемента ИШ1-НЕ подключен к вт рому входу элемента ИЛИ, выход которого подключен к первым входам третьего и четвертого элементов П, вторые входы третьего и четвертого элементов Н являются соответственно пер вым и вторым входами узла блокировки выход третьего элемента И подключен к второму входу первого элемента Н и к прямому выходу пятого элемента И, выход четвертого элемента И подключен к второму входу второго элемента Н и к прямому входу шестого элемента Н, инверсные входы пятого и шестого элементов Н подключены к вы ходу первого сумматора по модулю два выходы пятого и шестого элементов И являются соответственно третьим и че вертым выходами узла блокировки, прямой и инверсный выходы триггера подключены к вторым входам первого и второго элементов И-НЕ соответственно, выходы первого и второго элементов Н-НЕ подключены к первым входам второго и третьего сумматоров по модулю два, вторые входы которых подключены к выходам второго и первого элементов И соответственно, выходы второго и третьего сумматоров по модулю два являются соответственно вто: рым и первым выходами узла блокировки. На фиг. 1 представлена функциональная схема устройства для реализации безызбыточного алгоритма быстрого преобразования Фурье; на фиг.2функциональная схема блока управления; на фиг. 3 - функциональная схема узла блокировки. Устройство содержит арифметический блок 1, блок 2 постоянной памяти, блоки 3 и 4 оперативной памяти, блок 5 управления, включающий узел элементов И 6, регистр 7 итераций, счетчик 8, триггеры 9 и 10, узел 11 синхронизации узел 12 формирования инверсного кода, элемент И 13, узел , 14 блокировки, вычитатели15 и 16 и кольцевые 17 и 18 регистры сдвига. Узел блокировки содержит элементы И-НЕ 19, элементы И 20-22, сумматоры 23 по модулю два, элемент ;.. НЕ 24, сумматор 25 по модулю два, элемент ЮШ 26, триггер 27 и элемент ИЛН-НЕ 28. Устройство для реализации безызбыточного алгоритма БПФ работает следующим образом. Четыре действительные последовательности входных отсчетов представляются как две комплексные, причем одна комплексная последовательность расположена в первом блоке 3 оперативной памяти (ОП) в двоичноинверсном порядке, а другая - во втором блоке 4 ОП в прямом порядке. Блок 5 управления -{БУ} вырабатывает коды адресов операндов, выбираег мых из первого 3 или второго 4 блоков ОП и поступающих в арифметический блок 1, предназначенный для вычисления элементарных операций БПФ вида А i BW, где А и В - значения двух точек, участвующих в преобразовании согласно направленному графу БПФ с постоянной структурой, а W - значения экспоненциальных множителей, хранящихся в блоке 2 постоянной памяти (Ш1) и считьшаемык по кодам адресов также вырабатываемых.БУ 5, При этом первый 3 и второй 4 блоки ОП работают в режимах считывание-мпиись и запись-считывание соответственно. Дв операнда А и ,В выбираются из первого блока 3 ОП и подвергаются элементарному преобразованию БПФ в арифметическом блоке 1. Операнды С и D выбираются из второго 4 блока ОП и однов ременно в первый блок 3 ОП переписываются операнды, ранее выбранные из второго 4 блока ОП и преобразованные в арифметическом блоке t. Далее преобразованные операнды А и В переписываются из арифметического блока I во второй блок 4 ОП операнды С и О подвергаются преобразованию, а из первого блока 3 ОП считывается следующая пара операндов. Преобразованные операнды С и D заносятся в первый блок 3 ОП, считываются операнды из второго блока 4 ОП, а преобразованию подвергается следующая после А и В пара операндов и т.д. Данный порядок обработки сохраняется для всех последующих выбираемых операндов. Таким образом, первый 3 и второй 4 блоки ОП обмениваются информацией, причем во время обмена осуществляется вычисление элементарного преобразования БПФ. По ле окончания очередной итерации ру перестраивается и обеспечивает выбор операндов из блоков ОП согласно изменяющемуся направлению графа БПФ После завершения итераций БПФ осуществляется дополнительная итерация, необходимая при реализации безызбыточного алгоритма. Вычисленные величины - спектры действительных последовательностей на положительных частотах последовательно считываются с выхода арифметического блока 1 причем вначале считываются спектры последовательностей, представленных как действительная часть, а затем - спектры последова7ельностей, представленных как мнимая часть комп лексных входных данных. Блок управления 5 устройства работает следующим образом. Перед началом вычислений регистр 7 итераций, счетчик 8 и триггеры 9 и 10 устанавливаются в нулевое состо яние. Выходы триггера 9 являются выходами блока управления и определяют режим работы первого 3 и второго 4 блоков ОП (О - считывание, 1 запись. На управляющем входе узла 12 формирования инверсного кода ус,танавливается потенциал О и сигна 68 лы с выходов разрядов счетчика 8 поступают на суммирующие входы вычитателей 15 и 16 без инвертирования, на вычитающих входах которых сигналы с выходов триггера 9 определяют соответственно режимы Перезапись кода в регистр и Перезапись кода в регистр с вычитанием единицы. Низкий или высокий потенциалы на первом и втором выходах узла 14 блокирования определяют режимы работы регистров 17 и 18 Перезапись кода прямо или Перезапись кода с кольцевым сдвигом вправо на один разряд соответственно. На третьем и четвертом выходах узла блокирования формируются сигналы запрещения обращения к блокам ОП (высокий потенциал) и разрешения обращения (низкий потенциал). Запрещение обращения осуществляется при появлении на первом и шестом выходах БУ 5 кодов адресов, по которым в блоки ОП записываются первые два операнда на первой итерации БПФ. Для всех остальных итераций БПФ сигнал запрещения обращения не вырабатывается. Кроме того, при осуществлении дополнительной итерации перепаковки запрещается запись информации в ячейки блоков ОП. При поступлении тактовых импульсов на вход триггера 10 его состояние, а также состояние триггера 9-, счетчика 8 и регистра итераций 7 изменяется. Сигналы с выходов разрядов счетчика 8 через узел 12 в прямом или инверсном коде поступают на входы вычитателей 15и 16, где происходит вычитание единицы из младщего разряда кода адреса записи второго, блока 4 ОП, а затем первого блока 3 ОП соответственно. Коды адресов с выходов разрядов вычитателей 15 и 16 поступают и информационные входы первого 17 и второго 18 регистров сдвига. Кроме того, на входы первых разрядов регистров 17 и 18 поступают сигналы с выхода триггера 10, состояние которого в зави- симости от потенциалов на первом и втором выходах узла 4 блокирования записьшается либо в первый разряд регистра (на управляющем входе О), либо в последний разряд регистра при сдвиге всей информации в сторону младших разрядов на один разряд (на управляющем входе 1). При выполнении первой итерации БПФ на третьем и четвертом выходах узла 14 блокирования появляются сигналы запрещающие.обращение к блокам ОП во время генерирования кодов записи первых пар операндов4 На последующих операциях БПФ сигнал запрещения обращения не вырабатывается. Коды адресов записи и считьшания операндов для первого 3 и второго 4 блоков ОП приведены в табл.1. После окончания итераций БПФ на выходе первого разряда регистра ите раций 7 появляется .сигнал I. При этом на управляющих входах регистров 17 и 18 формируется высокий потенциал, а на третьем и четвертом выходах узла 14 -.сигналы запрещения записи в блоки ОП. В этом режиме осуществляется перепаковка информации, хранящейся в блоках ОП. Коды адресов считываемых операн. дов приведены в табл.2 /здесь, как и в табл.I, коды адресов соответствуют восьйиточечному направленному графу БПФ. Формирование кодов адресов обращения к блоку 2 постоянной памяти(п осуществляется группой узлов: узел элементов И 6, счетчик 8 и регистр 06110 11тераций 7, который работает в режиме занесения 1 в старший разряд при сдвиге всей информации в сторону младших разрядов. Сдвиг и занесение информации.осуществляется по сигналу перехода состояния старшего разряда счетчика 8 из 1 в О. Для восьмиточечного БПФ коды адресов обращения к блоку 2 ПП приведены в табл.3. Предложенное устройство для pea- лизации безызбыточного алгоритма БПФ обладает широкими функциональными возможностями при увеличении быстрадействия и высокой эффективности использования арифметического блока устройства. В сравнении с известными устройствами для случая совместной обработки группы действительных последовательностей данных предложенное устройство имеет повьшенное в два раза быстродействие, что достигается полной синхронностью .работы блоков оперативной памяти и арифметического блока управления. При этом эффективность использования арифметического блока является максимальной.

I

e