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

1

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

Делью изобретения является повышение быстродейс . вия.

Для пояснения сущности изобретения сравним обычный и усеченный алгоритмы БПФ. В случае, когда числ отсчетов сигнала равно степени двух т.е. , дискретный спектр сигнала может быть вычислен за р шагов п рекуррентным формулам.

х.,,(р)-Х;(р)+Х;()

Х;,(Р-Ь2 - ) Х;(р) -Х;(р+2 - ) W

где i - номер maraj

Х;,х;+| - входные и выходные данные для i I -ro щага;

Р, - номера отсчетов в массивах входных и выходных данных; W - тригонометрический коэффициент, причем

w exp (Z MAFT/N)

в приведенных формулах . 2 и .2,

где

оГС- ;

1 0,2 -I,

m

Так как периодическая дискретная функция k с периодом N, достаточно сформировать массив тригонометрических коэффициентов и отсчетов, При этом W соответствует k-му отсчету в массиве.

На фиг. 1 приведен пример направленной граф-схемы алгоритма БПФ для случая N 2 .На этой схеме вершины графа (точки) соответствуют отсчетам данных. На каждом шаге алгоритма линии без стрелок соответствуют простой передаче данных, линии со стрелками соответствуют передаче с предварительным умножением на тригоно.метрический коэффициент. Знак + или - возле вершины графа указывает ка операцию, с помощью которой получен соответствующий отсчет. Ниже граф-схемы алгоритма БПФ указаны для каждого шага i значения, которые принимают переменные m и 1. В рассматриваемом примере для определения дискретного спектра сигнала требуется выполнить 12 операций комплексного умножения.

O

5

0

5

0

5

0

5

0

5

В усеченном алгоритме БПФ требуется найти М (М « N) отсчетов дискретного спектра сигнала с номерами b,,bj ,...,Ь, где bj - целые числа из интервала (О, N-l).Пpи этом достаточно на каждом шаге преобразования определить только те отсчеты, которые требуются на следующем шаге.

На фиг. 1 зачернены вершины граф- схемы алгоритма БПФ, соответствующие отсчетам данных, которые необходимо определить на каждом шаге для вычисления отсчетов дискретного спектра сигнала с номерами 3 и 7. Таким образом, зачерненные вершины графа образуют граф-схему усеченного алгоритма БПФ для случая, когда М 2,Ь, 3,Ьг 7.

При использовании алгоритма усеченного БПФ вычисление ведется по тем же формулам, но переменная m принимает значение m (bj)mod , где j 1, 2 . .. И.

В рассматриваемом примере для вычисления искомых отсчетов спектра требуется выполнить 8 операций комплексного умножения, т.е. на одну треть меньше, чем при использовании обычного алгоритма БПФ. Выигрыш достигается тем, что данное устройство для формирования адресов процессора усеченного БПФ формирует на каждом шаге алгоритма только те адреса, которые нужны для вычисления искомых отсчетов дискретного спектра сигнала. Благодаря этому процессор не выполняет операции с ненужными отсчетами.

На фиг. 1 представлен алгоритм усеченного БПФ; на фиг. 2 - блок-схема устройства; на фиг. 3 - блок-схема блока регистров, блока элементов И, блока счетчиков и блока фиксации нуля; на фиг. 4 - алгоритмы работы устройства; на фиг. 5 - временные диаграммы; на фиг, 6 - схема блока управления; на фиг. 7 - схема логического узла.

Устройство (фиг. 2) содержит регистры 1 и 2 сдвига, счетчики 3 и 4, сдвигатели 5 и 6, элемент И 7, сумматоры 8 и 9 блоки 10 и 11 сравнения, блок 2 регистров, блок 13 элементов И, блок 14 сч€1тчиков, блок 5 фиксации нуля и блок 16 управления, выходы 17-22 блока управления, входы 23-26 блока управления, выход 27

fO

15

20

31278883

адреса коэффициента, выходы 28 и 29 адреса соответственно первого и второго операндов.

На фиг. 3 приведены схемы блока 12 регистров, блока 13 элементов И, блока 14 счетчиков и блока I5 фиксации нуля. Блок 12 регистров содержит регистры 30, число которых не меньше числа искомых отсчетов дискретного спектра сигнала М. Блок 14 счетчиков содержит соответствующее число счетчиков 31. Блок 13 элементов И содержит М групп элементов И, причем число элементов И 32 в каждой группе равно разрядности регистров 30. Блок фиксации нуля включает блок элементов И, состоящий из элементов И 33, число которых равно числу счетчиков 31, и элемент ИЛИ 34.

Блок управления (фиг. 6) содержит дешифратор 35, триггеры 36-38, элементы И 39-46, элементы ИЛИ 47-52, элементы НЕ 53-55, резистор 56, конденсатор 57, логический узел 58, генератор 59 тактовых импульсов.

Логический узел (фиг.. 7) содержит элементы НЕ 60-62, элементы И 63-65 с выходом 66, элементы И 67-71, элементы ИЛИ 72-75.

Для пояснения работы устройства на фиг. 4 приведена блок-схема алго- ритма его работы. На блок-схеме алгоритма использованы следующие обозначения:

Рг1 - первый регистр 1 сдвига;

Рг2 - второй регистр 2 сдвига;

Сч1 - первый счетчик 3;

Сч2 - второй счетчик 4;

БлСч - блок 14 счетчиков;

См1 - первый сумматор 8;

См2 - второй сумматор 9; СхСд - второй сдвигатель 6; : - обозначает запись информации;

означает запись разряд Сч;

I1(Рг - означает сдвиг содержимого Рг влево на один разряд;

Р1, Р2, РЗ, Р4 - сигналы на входах 23-26 блока 16 управления.50

У1, У2, УЗ, У4, У5, У6 - сигналы на выходах.17-22 блока 16 управления.

Для пояснения работы устройства для формирования адресов процессора усеченного БПФ воспользуемая также временными диаграммами, приведенными на фиг. 4. Временные диаграммы построены для случая, когда N 8 , М

2 ве ри .на и ег лы Рг ра тр ра

со та

си и ин пи по на и Сч ре 5 Си в по ло но на ра 31

чи 00 в де ся эт хо 45 со по на пр на да ро ад ци

сл Та ве кр

30

35

40

55

гд

O

5

0

2, Ь 3, Ъ 7. На диаграмме приведены сигналы СС, формируемые внутри блока 1 6 управления (БУ-), сиг- .налы Р1, Р2, РЗ и Р4 на его входах и сигналы У1, У2, УЗ, У4. У5, У6 на его выходах. Приведены также сигналы на прямых выходах разрядов Рг1, Рг2, Сч, Сч2. Б соответствии с рассматриваемым примером Рг1 и Рг2 - трехразрядные, а Сч1 и Сч2 - двухразрядные.

Устройство для формирования аДре- сов процессора усеченного БПФ работает следующим образом.

После запуска БУ он формирует сигнал У1, который устанавливает Рг1 и Рг2 в режим параллельной записи информации, и сигнал У5, который за- письгоает в Рг1 и Рг2 код 001. При поступлении следующего импульса сигнала СС БУ формирует сигналы У2, УЗ и У5. Первый из них устанавливает Сч2 и Сч1, а также счетчики 31 в режим параллельной записи информации. 5 Сигнал УЗ обнуляет Сч1 и записьгоает в каждый счетчик 31 код, который получается в результате поразрядного логического умножения кода, записанного в одном из регистров блока 30 на код, записанный в старших г-1 разрядах Рг2. При этом в счетчиках 31 записываются коды

(bj),

коды, записанные в регистрах 30.

Б рассматриваемом примере в счетчики 31 при этом записывается код 00. Сигнал У4 обнуляет Сч2. Так как в счетчиках 31 записан О, на выходе блока 15 фиксации нуля появляется логическая единица (Р4 1). При этом в алгоритме выполняется переход от вершины 4 к вершине 7, что 5 соответствует формированию У6 при поступлении следующего импульса сигнала СС. Этот сигнал информирует процессор о том, что на выходе См2 находится адрес Л1 (первого операн- да, на выходах См1 - адрес А2 второго операнда и на выходах СхСд - адрес A3 тригонометрического коэффи-. циента).

В рассматриваемом примере в этом случае AI 000, А2 001 и A3 000. Так как в Сч2 и записан О, а на инверсных выходах всех разрядов Сч2, кроме младшего, находится код 11,

0

5

0

где Ъ; на выходе блока 11 срзвнения находит ся логический нуль (РЗ О). Поэтому в алгоритме выполняется переход от вершины 8 к вершине 9. Так как сигнал У2 при этом не вырабатывается сигнал У4 добавляет к содержимому Сч2 единицу. После этого по сигналу У6 на выходах См1, См2 и СхСд считываются адреса А1 010, и А3 000. В следующем цикле считываются коды 100, 101, 000 и наконец, коды 110, 111 и 000. При этом на выходе блока II сравнения появляется логическая единица, так как с Сч2 записан код 11. Поскольку на выходе блока 10 сравнения также установлена ло гическая елиница (Р2 1) вьтолняет ся переход к вершине 10 блок-схемы алгоритма. Формируемый при этом сигнал У5 сдвигает содержимое Рг1 и Рг2 влево на один разряд. В младший разряд Рг1 записывается логический нуль а Рг2 - логическая единица. Так как в Рг1 записан не нуль, сигнал . Поэтому вьтолняется переход к вершине 3 алгоритма. Производится новая запись кодов в счетчики 31. В рассматриваемом примере записывается код О. При этом на выходе блока I5 фиксации нуля появляется логический нуль (Р4 о). Так как на выходе блока 10 сравнения тоже нуль (), формируется сигнал УЗ, которьп добав ляет 1 к содержимому Сч1 и вычитает 1 из содержимого счетчиков ЗГ. В результате счетчики 31 обнуляются и появляется сигнал Р4 - 1. Поэтому выполняется переход к вершине 7 алгоритма и считывается адрес А1 001, А2 011 и A3 010. В следую щем цикле содержимое Сч2 увеличивается на единицу и считьгааются адреса.А1 « 101, А2 1 П и A3 010. Затем проходит очередной сдвиг кодов в Рг1 и Рг2 и новая запись в счетчик 31. На этот раз в них записывается код I1. Так как происходит обращение к вершине 6 алгоритма. После трех обращений счетчик 31 обнуляется, а в Сч1 появляется код 11. При появлении следующего импульса сигнала СС БУ формирует У6, и с выходов СМ1, См2,-СхСд считьюа- ются коды 101, 111, 011. Затем происходит очередной сдвиг кодов в Рг1 и Рг2. Так как Рг1 при этом обнуляется, БУ по сигналу Р4 с выхода элемента И 7 прекращает работу устрой278883 6

ства для формирования адресов процессора усеченного БПФ.

Формула изобретения

10

fS

20

25

: Устройство для формирования адресов процессора усеченного быстрого преобразования Фурье, содержащее первый регистр сдвига, первый и второй счетчики, блок управления, первый выход которого подключен к установочным входам первого и второго счетчиков, счетные входы которых подключены соответственно к второму и третьему выходам блока управления, четвертый и пятый выходы которого подключены соответственно к тактовому входу и входу управления направлением сдвига первого регистра сдвига, отличающееся тем, что, с целью повьппения быстродействия, в него введены первый и второй сумматоры, второй регистр сдвига, первьй и второй сдвигатели, элемент И, первый и второй блоки сравнения, блок счетчиков, первый и второй блоки элементов И, элемент ИЛИ и блок регистров, i-й выход(,г, г- разрядность которого подключен к i-му входу первого блока элементов И, i-й выход которого подключен к i-му, информационному входу блока счетчиков, i-й информационный выход которого подключен к i-му входу второго блока элементов И, i-й выход которого подключен к i-му входу элемента ИЛИ, выход которого подключен к первому входу блока управления , первый, второй, четвертый и пятый выходы которого подключены соответственно к установочному и счетному входам блока счетчиков и тактовому и установочному входам второго регистра сдвига, j-й {j 2,г) разряд прямого выхода которого подключен к (j+r-l)-My входу первого блока элементов И и (J-1)-му входу первого блока сравнения, выход которого подключен к второму входу блока управления, третий вход которого подключен к выходу второго блока сравнения (J-1)-й вход которого подключен к разряду инверсного выхода второго регистра сдвига, i-й разряд прямого выхода первого регистра сдвига подключен к i-му входу первого сум матора, i-му входу управления сдвигом первого сдвигателя, i-й выход

ХЗ

35

40

45

50

55

которого подключен к i-му входу второго сумматора, i-й выход которого является i-M адресным выходом первого операнда устройства и подключен к (1+г)-му входу первого сумматора, i-й выход которого является i-M адресным выходом второго операнда устройства, выходом адреса коэффициента которого является 1-й выход второго сдвигателя (j-l)ft вход управления сдвигом которого подключен к (j-l)-My разряду прямого выхода первого регистра сдвига, i-й разряд инверсного выхода которого подключен к i-му входу элемента И, выход которого подключен к четвертому входу блока управления, (J-l)-й разряд выхода первого счетчика подключен к (j+r-2)-My входу первого блока сравнения, (j-l)-My информационному входу второго сдвигателя и (j+r-l)-My входу второго сумматора, (j-l)-й разряд выхода второго счетчика подключен к (j+r-2)-My входу второго блока сравнения и (j-l)- му информационному входу первого сдвигателя шестой выход блока управления является выходом синхронизации устройства, блок управления со- держит десять элементов ИЛИ, шесть элементов НЕ, шестнадцать элементов И, три RS-триггера, дешифратор и генератор тактовых импульсов, выход которого подключен к первым входам элементов И с первого по шестой, к входу первого элемента НЕ, выход которого подключен к входам синхронизации первого, второго и третьего RS-триггеров, выходы которых подключены Соответственно к первому, второму и третьему входам дешифратора, первый и второй выходы которого подключены соответственно к первому и второму входам первого элемента ИЛИ, выход которого подключен к первым входам второго и третьего элементов ИЛИ, выходы которых подключены соответственно к R-входу первого RS-триггера и первому входу седьмого элемента И, выход которого подключен к S- входу второго RS-триггера, третий вь1ход дешифратора подключен к второму входу первого элемента И,первому входу четвертого элемента ИЛИ и первому входу пятого элемента ИЛИ, выход которого подключен к В-входу первого RS-т.риггера, четвертый выход дешифратора подключен к второму входу элеO

5

0

5

0

5

0

5

0

5

мента И, первым входам шестого и седьмого элементов ИЛИ, первым входом восьмого и десятого элементов И, выходы которых подключены -сооткет- ственно к В-входу третьего RS-трнг- гера, второму входу второго элемента ИЛИ и первому входу восьмого элемента ИЛИ, выход которого подключен

к первому входу девятого элемента ИЛИ, выход которого подключен к R- входу второго RB-триггера, пятый выход дешифратора подключен к второму входу третьего элемента И и пер- вым входам одиннадцатого, двенадцатого и тринадцатого элементов И, выходы которых подключены соответственно к второму и третьему входам восьмого элемента ИЛИ и второму входу пятого элемента ИЛИ, шестой выход дешифратора подключен к второму вхо-, ду седьмого элемента ИЛИ и первым входам четырнадцатого и пятнадцатого элементов И, выхода которых подключены соответственно к. третьему входу второго элемента ИЛИ и четвертому входу восьмого элемента ИЛИ, седьмой выход дешифратора подключен к второму входу четвертого элемента ИЛИ, первому входу десятого элемента ИЛИ и первому входу шестнадцатого элемента И, выход которого подключен к второму входу третьего элемента ИЛИ, третий вход которого объединен с вторым входом шестого элемента ИЛИ и подключен к восьмому выходу дешифратора, вторые входы седьмого и восьмого элементов И объединены и подключены к выходу второго элемента НЕ, вход которого объединен с вторыми входами девятого и десятого элементов ИЛИ и подключен к выходу третьего элемента НЕ, вход которого является входом задания логической едини15з1 устройства, выходы первого, второго и третьего элементов И являются соответственно пятым, первым и шестым выходами блока, четвертым, третьим и вторым выходами которого являются выходы соответственно четвертого, пятого и шестого элементов И, вторые входы которых подключены к выходам соответственно четвертого., шестого и седьмого элементов ИЛИ, второй вход шестнадцатого элемента И подключен к выходу четвертого элемента НЕ, вход которого является четвертым входом блока, второй вход которого подключен к вторым входам

одиннадцатого и пятнадцатого элементов И, второй вход двенадцатого элемента И подключен к выходу пятого элемента НЕ, вход которого объединен с вторым входом тринадцатого элемента И и является третьим входом блока, первый вход которого подключен к вторым входам девятого и четырнадцатого элементов И и входу шестого элемента НЕ, выход которого подключен к второму входу десятого и третьему входу пятнадцатого элементов И.

Изобретение относится к радиотехнике и вычислительной технике и может быть использовано в устройствах цифровой обработки сигналов. Цель изобретения - повышение быстродействия. Поставленная цель достигается за счет того, что устройство содержит два регистра сдвига, два счетчика, блок управления, два сумматора, два блока сдвига, элемент И, два блока сравнения, блок счетчиков, два блока элементов И, элемент ИЛИ, блок регистров. Причем блок управления содержит шесть элементов НЕ, шестнадцать элементов И, три RS-триггера, десять элементов ИЛИ, дешифратор и генератор тактовых импульсов. Устройство формирует на каждом шаге алгоритма тблько те адреса., которые нужны для вычисления искомых отсчетов дискретного спектра сигнала. Благодаря этому процессор не выполняет операции с ненужньми отсчетами. 7 ип. КЛ с

Редактор В. Иванова

Составитель А. Баранов Техред А.Кравчук

Заказ 6841/49Тираж 671Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

7 1 б

Фмг. 7

Корректор А. Обручар