Пристрій потокового обчислювання швидкого перетворення фур’є послідовності 2 lambda цифрових відліків

Предлагаемое изобретение относится к области цифровой обработки сигналов и может быть использовано в радиолокации, гидроакустике, при обработке сейсмических и речевых сигналов, изображений. Известно устройство поточного вычисления быстрого преобразования Фурье (БПФ) последовательности 2l цифровых отсчетов (А.с. СССР №928362, кл. G06F15/332, опубл. 1982), содержащее l каскадов, где каждый из которых содержит входной и выходной коммутаторы, линию задержки, блок памяти поворачивающих множителей, блоки сумматора и умножителя выходных отсчетов на поворачивающий множитель. Недостатком такого устройства является различная длина линий задержки в различных каскадах. Наиболее близким по структуре и техническим характеристикам к предлагаемому является устройство поточного вычисления БПФ последовательности 2l цифровых отсчетов (Патент США №3746848, кл. G06F15/332, опубл. 1973), содержащее l каскадов, каждый из которых содержит арифметический блок, выполняющий базовую операцию БПФ "бабочка" над парами входных отсчетов, блок памяти поворачивающих множителей, две линии задержки одинаковой длины и коммутатор. Недостатком этого устройства является различная длина соответствующих линий задержки в различных каскадах устройства. В основу изобретения поставлена задача создания такого устройства поточного вычисления быстрого преобразования Фурье 2l отсчетов, в котором новое выполнение блока управления, коммутатора и линий задержки позволило бы обеспечить одинаковые длины линий задержки в различных каскадах устройства и за счет этого унифицировать все каскады устройства. Решение поставленной задачи достигается тем, что в устройстве поточного вычисления БПФ последовательности 2l отсчетов, содержащем l последовательно включенных каскадов, каждый из которых содержит первую и вторую линии задержки, арифметический блок, блок памяти поворачивающих множителей и коммутатор, причем третий вход арифметического блока соединен с выходом блока памяти поворачивающих множителей, входы коммутатора соединены с соответствующими выходами арифметического блока, входом устройства является вход первого каскада, а выходом устройства является выход l - го каскада, и блок управления, содержащий генератор тактовых импульсов, линии задержки выполнены в виде двух ОЗУ объемом N/2 слов каждое, где N = 2l, информационные входы которых соединены со входом каскада, а управляющие входы которых соединены с формирователем адресов записи/считывания и формирователем управляющих сигналов, в блок управления введены формирователь адресов записи/считывания и формирователь управляющих сигналов, входы которых соединены с выходом генератора тактовых импульсов, коммутатор выполнен по схеме 2 × 1, причем его входы соединены с выходами арифметического блока, а выход его является выходом каскада. Технический результат состоит в том, что при реализации поточного процессора с идентичной покаскадной структурой на СБИС возрастает технологичность производства и уменьшается стоимость готового изделия, при этом целесообразно в виде одной СБИС выполнить один каскад поточного процессора. На фиг.1 приведена структурная схема устройства поточного вычисления БПФ; на фиг.2 временные диаграммы работы устройства для случая N = 8; на фиг.3 - временные диаграммы сигналов блока управления; на фиг.4 - пример реализации блока управления. На фиг.1 приведена структурная схема устройства поточного вычисления БПФ, содержащая l каскадов 1i, где и блок управления 7. Каждый каскад содержит первое ОЗУ 2 емкостью N/2 слов, второе ОЗУ 3 емкостью N/2 слов, арифметический блок 4, блок памяти поворачивающих множителей 5, коммутатор 6. Блок управления 7 содержит генератор тактовых импульсов (ГТИ) 8, формирователь адресов записи/считывания 9 и формирователь управляющих сигналов 10. Входы ОЗУ 2 и 3 соединены и являются входом каскада. Управляющие входы ОЗУ 2 и 3 соединены с выходами формирователя адресов записи/считывания 9 и формирователя управляющих сигналов 10. Выходы ОЗУ 2 и 3 соединены с двумя входами арифметического блока 4, третий вход которого соединен с выходом блока памяти поворачивающих множителей 5, управляющие входы которого соединены с выходами формирователя адресов записи/считывания 9 и формирователя управляющих сигналов 10. Выходы арифметического блока 4 соединены с соответствующими входами коммутатора 6, управляющий вход которого соединен с выходом формирователя управляющих сигналов 10. Выход коммутатора 6 является выходом каскада. Работой всех каскадов устройства управляет блок управления 7. Каскады устройства соединены последовательно. Вход первого каскада является входом устройства, выход l - го каскада является выходом устройства. Устройство работает следующим образом. Работа всех каскадов одинакова. Поэтому можно ограничиться рассмотрением работы одного из них, например, первого. Входные отсчеты записываются в ОЗУ 2 и ОЗУ 3, причем в ОЗУ 2 записывается первая половина отсчетов, а в ОЗУ 3 записывается вторая половина отсчетов. Запись происходит в первой половине такта T, где T - интервал поступления входных отсчетов. Адрес записи в ОЗУ 2 соответствует номеру записываемого отсчета, принимающему значения от 1 до N/2, а адрес записи в банк ОЗУ 3 соответствует уменьшенному на величину N/2 номеру записываемого отсчета, принимающему значения от N/2 + 1 до N. Считывание происходит во второй половине такта T с уменьшенной вдвое тактовой частотой. При этом первый такт считывания проходит в такт времени T, в первой половине которого заполняется первая ячейка ОЗУ 3. Считывание происходит одновременно из обоих ОЗУ 2 и 3 из ячеек с одинаковыми адресами. Адрес считывания последовательно принимает значения от 1 до N/2. Считанные из ОЗУ 2 и 3 пары отсчетов с интервалом 2T поступают на входы арифметического блока 4, на третий вход которого поступает поворачивающий множитель W NK = exp(-j2 p k/N) из блока памяти поворачивающих множителей 5, при этом величина k определяется выражением где отсчетов; - номер поступившей пары - номер каскада устройства; - целая часть выражения. Арифметический блок 4 выполняет базовую операцию БПФ-2 типа "бабочка", описываемую выражениями: где a1 и a2 - входные отсчеты; b1 и b2 - выходные отсчеты. При этом выходной отсчет b1 задержан относительно входных отсчетов на время T, а выходной отсчет b2 задержан относительно входных отсчетов на время 2T. Выходные отсчеты арифметического блока 4 b1 и b2 поступают на входы коммутатора 6, интервал переключения которого равен T. Выход коммутатора 6 является выходом каскада. Временные диаграммы работы устройства для случая N = 8 приведены на фиг.2. При этом устройство содержит всего 3 каскада 11, 12 и 13 и блок управления 7. На фиг.2 по горизонтальной оси отложены номера тактов времени, а по вертикальной - номера контрольных точек устройства PL, где номер контрольной точки в каскаде устройства, - номер каскада устройства. Рассмотрим, какие сигналы должен вырабатывать блок управления 7. ОЗУ 2 и 3 могут быть выполнены на элементах ОЗУ любого типа. Пусть банки ОЗУ выполнены на ОЗУ статического типа. Для указанного случая временные диаграммы сигналов блока управления представлены на фиг.3, пример реализации блока управления 7 приведен на фиг.4. Формирователь адресов записи/считывания 9 состоит из двоичного счетчика DD2 и мультиплексора DD3. Формирователь управляющих сигналов 10 состоит из логических элементов DD1.1, DD1.2, DD1.3, DD4.1, DD4.2. Сигнал синхронизации U26, вырабатываемый ГТИ 8, поступает на входы формирователя адресов записи/считывания 9 и формирователя управляющих сигналов 10. Формирователь адресов записи/считывания 9 формирует необходимую последовательность адресов записи/считывания, а формирователь управляющих сигналов 10 формирует сигналы управления записью в ОЗУ 2 и в ОЗУ 3 сигнал управления работой коммутатора 6, сигналы управления считыванием из ОЗУ 2 и 3 и блока памяти поворачивающих множителей 5. Сигнал переключения MODE получают, задержав сигнал синхронизации U26 на время T/4. Сигнал переключения MODE используется для коммутации адресов записи/считывания. Сигналы записи формируются из сигнала синхронизации U26, сигнала переключения MODE, сигнала на выходе Q3 счетчика DD2. Передний фронт сигнала стробирования STROB сигнализирует об истинности данных на входах арифметического блока, а также используется для управления коммутатором 6.