Каскадний пристрій швидкого перетворення фур’є

Предлагаемое изобретение относится к вычислительной технике и может быть использовано в системах цифровой обработки сигналов. Известны поточные схемы быстрого преобразования Фурье (Рабинер Л. Гоулд Б. Теория и применение цифровой обработки сигналов. - М.: Мир. - С.674), содержащие n последовательно соединенных каскадов, каждый из которых содержит переключатель, первый, второй и третий элементы задержки и арифметическое устройство. Наиболее близким к предлагаемому изобретению по технической сущности и достигаемому результату является каскадное устройство для быстрого преобразования Фурье, описанное в (А.с. СССР №1265794, кл. G06F15/332), содержащее n (n = log4 N, где N число элементов преобразования Фурье) последовательно соединенных каскадов, каждый из которых содержит арифметический блок, коммутатор, два элемента задержки, синхронизатора, формирователя тригонометрических коэффициентов, коммутатора и регистра. Для удобства описания объединим арифметический блок и коммутатор каждого из n каскадов в арифметический блок. Недостатками указанных устройств является: а) работа арифметический блок только 25% времени, равного длительности входного массива. Это связано со структурой алгоритма, который обеспечивает выполнение сразу 4 х коэффициентов (Рабинер Л., Гоулд Б. Теория и применение цифровой обработки сигналов. - М.: Мир, 1978. - С.674) за 25% времени от длительности массива. Следовательно арифметический блок загружен не полностью, б) значительное энергопотребление и низкая надежность, так как на каждый этап быстрого преобразования приходится по одному арифметическому блоку. В основу изобретения поставлена задача: создать такое каскадное устройство быстрого преобразования Фурье, в котором введение рекурсивных связей между выходом и входом арифметических блоков позволит использовать поточно-рекурсивный метод в конвейерной обработке сигнала, в результате чего достигается полная загрузка арифметических блоков, что позволило бы обеспечить значительное увеличение производительности устройства. 100% - я загрузка арифметический блок достигается при выполнении одним арифметическим блоком четырех этапов быстрого преобразования Фурье. Техническим результатом предлагаемого изобретения является уменьшение на 75% по сравнению с известными устройствами физического числа сумматоров и умножителей, что дает значительное сокращение энергопотребления и увеличивает надежность устройства. В устройство, содержащее синхронизатор, формирователь атригонометрических коэффициентов и n (n = 1/4(log4N), N - число элементов преобразования Фурье) последовательно соединенных каскадов, каждый из которых содержит арифметический блок, причем первый и второй выходы синхронизатора подключены соответственно к пятому и шестому входам каждого арифметического блока, выход последнего арифметического блока является информационным выходом устройства, второй вход син хронизатора является входом установки устройства, первый вход синхронизатора является тактовым входом устройства, адресный выход синхронизатора подключен к адресному входу формирователя тригонометрических коэффициентов, выход i - го (i = i, n) коэффициента которого подключен к седьмому входу i - го арифметического блока, введены n формирователей данных первого этапа, n формирователей данных второго этапа, n формирователей данных третьего этапа, n формирователей данных четвертого этапа, вход первого формирователя данных первого этапа является информационным входом устройства, первый вход j - го (j =2, n) формирователя данных первого этапа подключен к выходу (j - 1) - го арифметического блока, выход i го формирователя данных первого этапа подключен к первому входу i - го арифметического блока, второй и третий входы j - го формирователя данных первого этапа подключены соответственно к (8j - 7) - му и (8j - 6) - му выходам синхронизатора, первый вход i - го формирователя данных второго этапа подключен к выходу i - го арифметического блока, выход i - го формирователя данных второго этапа подключен ко второму входу i - го арифметического блока, второй и третий входы i го формирователя данных второго этапа подключены соответственно к (8j - 5) - му и (8j - 4) му выходам синхронизатора, первый вход i - го формирователя данных третьего этапа подключен к выходу i - го арифметического блока, выход i - го формирователя данных третьего этапа подключен к третьему входу i - го арифметического блока, второй и третий входы i - го формирователя данных третьего этапа подключены соответственно к (8j - 3) - му и (8j - 2) - му выходам синхронизатора, лей данных четвертого этапа, первый вход i - го формирователя данных четвертого этапа подключен к выходу i - го арифметического блока, выход i - го формирователя данных четвертого этапа подключен к четвертому входу i - го арифметического блока, второй и третий входы i го формирователя данных четвертого этапа подключены соответственно к (8j - 1) - му и 8j - м у выходам синхронизатора. Введение в устройство n формирователей данных первого этапа, n формирователей данных второго этапа, n формирователей данных третьего этапа и n формирователя данных четвертого этапа, а также дополнительных связей с этими блоками обеспечивает непрерывную работу все х арифметических блоков. Поскольку одна итерация быстрого преобразования Фурье выполняется за 25% времени, равного длительности массива, то подготавливая необходимые данные для каждой последующей итерации в соответствующем формирователе данных, удается использовать оставшееся время для выполнения одним арифметическим блоком дополнительно трех итераций Фурье. Это позволяет сократить число арифметических блоков в четыре раза. На фиг.1 изображена структурная схема устройства: на фиг.2 - структурная схема первого формирователя данных первого этапа; на фиг.3 структурная схема j - го формирователя данных первого этапа; на фиг.4 - структурная схема i - го формирователя данных второго этапа; на фиг.5 структурная схема i - го формирователя данных третьего этапа; на фиг.6 - стр уктурная схема i - го формирователя данных четвертого этапа; на фиг.7 - структурная схема i - го арифметического блока; на фиг.8 структурная схема синхронизатора; на фиг.9 - структурная схема формирователя тригонометрических коэффициентов; на фиг.10 - структурная схема устройства для N = 256; на фиг.11 - временные диаграммы, поясняющие работу устройства для N = 256; на фиг.12 - временные диаграммы, поясняющие выполнение первого этапа быстрого преобразования Фурье; на фиг.13 - временные диаграммы, поясняющие выполнение второго этапа быстрого преобразования Фурье; на фиг.14 временные диаграммы, поясняющие выполнение третьего этапа быстрого преобразования Фурье; на фиг.15 - временные диаграммы, поясняющие выполнение четвертого этапа быстрого преобразования Фурье. Каскадное устройство быстрого преобразования Фурье содержит: n последовательно соединенных каскадов, каждый из которых содержит формирователь 1 данных первого этапа, формирователь 2 данных второго этапа, формирователь 3 данных третьего этапа, формирователь 4 данных четвертого этапа и арифметический блок 5, а также синхронизатор 6, формирователь 7 тригонометрических коэффициентов, причем информационный вход первого формирователя 1 данных первого этапа является информационным входом устройства, информационный вход j - го формирователя 1 данных первого этапа подключен к информационному выходу (j - 1) - го арифметического блока 5, информационный выход i - го формирователя 1 данных первого этапа подключен к информационному входу i - го арифметического блока 5. первый и второй управляющие входы j - го формирователя 1 данных первого этапа подключены соответственно к (8j - 7) - му и (8j - 6) - му управляющим выходам синхронизатора 6, информационный вход i - го формирователя 2 данных второго этапа подключен к информационному выходу i - го арифметического блока 5, информационный выход i - го формирователя 2 данных второго этапа подключенко второму информационному входу i - го арифметического блока 5, первый и второй управляющие входы i - го формирователя 2 данных второго этапа подключены соответственно к (8j - 5) - му и (8j - 4) - му управляющим выходам синхронизатора 6, информационный вход i - го формирователя 3 данных третьего этапа подключен к информационному выходу i - го арифметического блока 5, информационный выход i - го формирователя 3 данных третьего этапа подключен к третьему информационному входу i го арифметического блока 5, первый и второй управляющие входы i - го формирователя 3 данных третьего этапа подключены соответственно к (8j - 3) - му и (8j - 2) - му управляющим выходам синхронизатора 6, информационный вход i - го формирователя 4 данных четвертого этапа подключен к информационному выходу i - го арифметического блока 5, информационный выход i - го формирователя 4 данных четвертого этапа подключен к четвертому информационному входу i - го арифметического блока 5, первый и второй управляющие входы i - го формирователя 4 данных четвертого этапа подключены соответственно к (8j - 1) - му и 8j - му управляющим выходам синхронизатора 6, информационный выход последнего арифметического блока 5 является информационным выходом устройства, пятый и шестой управляющие входы i - го арифметического блока 5 подключены соответственно к первому и второму управляющим выходам синхронизатора 6, первый управляющий вход синхронизатора 6 является входом установки устройства, второй управляющий вход синхронизатора 6 является тактовым входом устройства, адресный выход синхронизатора 6 подключен к адресному входу формирователя 7 тригонометрических коэффициентов, выход i - го коэффициента которого подключен ко входу задания коэффициентов i - го арифметического блока 5. Устройство работает следующим образом. Первый формирователь 1 данных первого этапа (фиг.2) содержит первый элемент задержки 8, второй элемент задержки 9, третий элемент задержки 10 и четвертый элемент задержки 11, которые имеют размерность N/4. Вход первого элемента задержки 8 является информационным входом формирователя 1. Выход первого элемента задержки 8 соединен со входом второго элемента задержки 9, а также с информационным выходом формирователя 1. Выход второго элемента задержки 9 соединен со входом третьего элемента задержки 10, а также с информационным выходом формирователя 1. Выход третьего элемента задержки 10 соединен со входом четвертого элемента задержки 11. а также с информационным выходом формирователя 1. Выход четвертого элемента задержки 11 соединен с информационным выходом формирователя 1. j - й формирователь i (j = 2, n) данных первого этапа (фиг.3) содержит первый элемент задержки 12, второй элемент задержки 13, третий элемент задержки 14, четвертый элемент задержки 15, пятый элемент задержки 17, шестой элемент задержки 18, седьмой элемент задержки 19 и мультиплексор 16. Первый элемент задержки 12 имеет размерность (N/4 - 3N/4 (4j - 3)), второй элемент задержки 13 имеет размерность (N/4 2N/4 (4j - 3)), третий элемент задержки 14 имеет размерность (N/4 - N/4^ (4j - 3)), четвертый элемент задержки 15 имеет размерность (N/4), пятый, шестой и седьмой элементы задержки 17, 18, и 19 имеют размерность (N/4 (4j - 3)). Вход первого элемента задержки 12 соединен с информационным входом j-ro формирователя 1, а выход со входом A мультиплексора 16. Вход второго элемента задержки 13 соединен с информационным входом j - го формирователя 1, а выход со входом B мультиплексора 16. Вход третьего элемента задержки 14 соединен с информационным входом j - го формирователя 1, а выход со входом C мультиплексора 16. Вход четвертого элемента задержки 15 соединен с информационным входом j - го формирователя 1, а выход со входом D мультиплексора 16. Вход S1 мультиплексора 16 соединен со вторым входом j го формирователя 1. Вход S2 мультиплексора 16 соединен со третьим входом j - го формирователя 1. Выход Q мультиплексора 16 соединен со входом пятого элемента задержки 17 и с информационным выходом j - го формирователя 1. Выход пятого элемента задержки 17 соединен с выходом j - го формирователя 1 и со входом шестого элемента задержки 18. Выход шестого элемента задержки 18 соединен с выходом j - го формирователя 1 и со входом седьмого элемента задержки 19. Выход седьмого элемента задержки 19 соединен с выходом j - го формирователя 1. i - й формирователь 2 данных второго этапа (фиг.4) содержит первый элемент задержки 20, второй элемент задержки 21, третий элемент задержки 22, четвертый элемент задержки 23, пятый элемент задержки 25, шестой элемент задержки 26, седьмой элемент задержки 27 и мультиплексор 24. Первый элемент задержки 20 имеет размерность (N/4 - 3N/4 (4i - 2)), второй элемент задержки 21 имеет размерность (N/4 2N/4 (4i - 2)), третий элемент задержки 22 имеет размерность (N/4 - N/4 (4i - 2)), четвертый элемент задержки 23 имеет размерность (N/4), пятый, шестой и седьмой элементы задержки 25, 26 и 27 имеют размерность (N/4 (4i - 2)). Вход первого элемента задержки 20 соединен с информационным входом i - го формирователя 2, а выход со входом A мультиплексора 24. Вход второго элемента задержки 21 соединен с информационным входом i - го формирователя 2, а выход со входом B мультиплексора 24. Вход третьего элемента задержки 22 соединен с информационным входом i - го формирователя 2, а выход со входом C мультиплексора 24. Вход четвертого элемента задержки 23 соединен с информационным входом i - го формирователя 2, а выход со входом D мультиплексора 24. Вход S1 мультиплексора 24 соединен со вторым входом i го формирователя 2. Вход S2 мультиплексора 24 соединен со третьим входом i - го формирователя 2. Выход Q мультиплексора 24 соединен со входом пятого элемента задержки 25 и с информационным выходом i - го формирователя 2. Выход пятого элемента задержки 25 соединен с выходом i - го формирователя 2 и со входом шестого элемента задержки 26. Выход шестого элемента задержки 26 соединен с выходом i - го формирователя 2 и со входом седьмого элемента задержки 27. Выход седьмого элемента задержки 27 соединен с выходом i - го формирователя 2. i - й формирователь i.3 данных третьего этапа (фиг.5) содержит первый элемент задержки 28, второй элемент задержки 29, третий элемент задержки 30, четвертый элемент задержки 31, пятый элемент задержки 33, шестой элемент задержки 34, седьмой элемент задержки 35 и мультиплексор 32. Первый элемент задержки 28 имеет размерность (N/4 - 3N/4 (4i - 1)), второй элемент задержки 29 имеет размерность (N/4 2N/4 (4i - 1)), третий элемент задержки 30 имеет размерность (N/4 - N/4 (4i - 1)), четвертый элемент задержки 31 имеет размерность (N/4), пятый, шестой и седьмой элементы задержки 33, 34 и 35 имеют размерность (N/4 (4i - 1)). Вход первого элемента задержки 28 соединен с информационным входом i - го формирователя 3, а выход со входом A мультиплексора 32. Вход второго элемента задержки 29 соединен с информационным входом i - го формирователя 3, а выход со входом B мультиплексора 32. Вход третьего элемента задержки 30 соединен с информационным входом i - го формирователя 3, а выход со входом C мультиплексора 32. Вход четвертого элемента задержки 31 соединен с информационным входом i - го формирователя 3, а выход со входом D мультиплексора 32. Вход 51 мультиплексора 32 соединен со вторым входом i го формирователя 3. Вход S2 мультиплексора 32 соединен со третьим входом i - го формирователя 3. Выход Q мультиплексора 32 соединен со входом пятого элемента задержки 33 и с информационным выходом i - го формирователя 3. Выход пятого элемента задержки 33 соединен с выходом i - го формирователя 3 и со входом шестого элемента задержки 34. Выход шестого элемента задержки 34 соединен с выходом i - го формирователя 3 и со входом седьмого элемента задержки 35. Выход седьмого элемента задержки 35 соединен с выходом 1-го формирователя 3. i - й формирователь i.4 данных четвертого этапа (фиг.6) содержит первый элемент задержки 36, второй элемент задержки 37, третий элемент задержки 38, четвертый элемент задержки 39, пятый элемент задержки 41, шестой элемент задержки 42, седьмой элемент задержки 43 и мультиплексор 40. Первый элемент задержки 36 имеет размерность (N/4 - 3N/4 (4i)), второй элемент задержки 37 имеет размерность (N/4 - 2N/4 (4i)), третий элемент задержки 38 имеет размерность (N/4 - N/4^(4i)), четвертый элемент задержки 39 имеет размерность (N/4), пятый, шестой и седьмой элементы задержки 41, 42 и 43 имеют размерность (N/4 (4i)). Вход первого элемента задержки 36 соединен с информационным входом i - го формирователя 4, а выход со входом A мультиплексора 40. Вход второго элемента задержки 37 соединен с информационным входом i - го формирователя 4, а выход со входом B мультиплексора 40. Вход третьего элемента задержки 38 соединен с информационным входом i - го формирователя 4, а выход со входом C мультиплексора 40. Вход четвертого элемента задержки 39 соединен с информационным входом i - го формирователя 4, а выход со входом D мультиплексора 40. Вход S1 мультиплексора 40 соединен со вторым входом i - го формирователя 4. Вход S2 мультиплексора 40 соединен со третьим входом i - го формирователя 4. Выход Q мультиплексора 40 соединен со входом пятого элемента задержки 41 и с информационным выходом i - го формирователя 4. Выход пятого элемента задержки 41 соединен с выходом i - го формирователя 4 и со входом шестого элемента задержки 42. Выход шестого элемента задержки 42 соединен с выходом i - го формирователя 4 и со входом седьмого элемента задержки 43. Выход седьмого элемента задержки 43 соединен с выходом i - го формирователя 3. i - й арифметический блок 5 (фиг.7) содержит мультиплексор 44, первый сумматор 45, первый вычитатель 46, второй сумматор 47, второй вычитатель 48, первый умножитель 49, третий сумматор 50, третий и четвертый вычитатели 51 и 52, четвертый сумматор 53, второй, третий и четвертый умножители 54, 55 и 56. Входы A1, B1, C1 и D1 мультиплексора 44 соединены с первым информационным входом устройства. Входы A2, B2, C3 и D3 мультиплексора 44 соединены с вторым информационным входом устройства. Входы A3, B3, C3 и D3 мультиплексора 44 соединены с третьим информационным входом устройства. Входы A4, B4, C4 и D4 мультиплексора 44 соединены с четвертым информационным входом устройства. Вы ход Q1 мультиплексора 44 соединен со входом A первого сумматора 45 и входом A первого вычитателя 46. Выход Q2 мультиплексора 44 соединен со входом B первого сумматора 45. Выход Q3 мультиплексора 44 соединен со входом B первого вычитателя 46, входом A второго сумматора 47 и входом A второго вычитателя 48. Выход Q4 мультиплексора 44 соединен со входом B второго сумматора 47 и входом B второго вычитателя 48. Выход первого сумматора 45 соединен со входом A третьего сумматора 50 и входом A третьего вычитателя 51. Выход первого вычитателя 46 соединен со входом A четвертого сумматора 53 и входом A четвертого вычитателя 52. Выход второго сумматора 47 соединен со входом B третьего сумматора 50 и входом B третьего вычитателя 51. Выход второго вычитателя 48 соединен со входом первого умножителя 49, выход которого соединен со входом B четвертого вычитателя 52 и со входом B четвертого сумматора 53. Выход третьего сумматора 50 соединен с информационным выходом блока 5. Выход третьего вычитателя 51 соединен со входом A второго умножителя 54, вход B которого соединен с седьмым входом блока 5. Выход четвертого вычитателя 52 соединен со входом A третьего умножителя 55, вход B которого соединен с седьмым входом блока 5. Выход четвертого сумматора 53 соединен со входом A четвертого умножителя 56, вход B которого соединен с седьмым входом блока 5. Выходы M второго, третьего и четвертого умножителей 54, 55 и 56 соединены с информационным выходом блока 5. Синхронизатор 6 (фиг.8) включает в себя (8n) разрядный двоичный счетчик 57, тактовый вход C которого соединен с первым входом блока 6, а на вход сброса R соединен с вторым входом блока 6 1 - й, 2 - й, ..., 8n - й выходы счетчика 57 соединены соответственно с 8n - м, 8n - 1 - м, ..., 1 - м выходами блока 6. Формирователь 7 тригонометрических коэффициентов (фиг.9) содержит 3n запоминающих устройств 58.i, 59.i и 60.i, входы U8n, U(8n - 1), ..., U1 которых соединены с адресным входом блока 7, а выходы Q соединены с выходом блока 7. В целом каскадное устройство быстрого преобразования Фурье работает по алгоритму быстрого преобразования Фурье с прореживанием по частоте по основанию 4 где следующим образом. Рассмотрим случай для N = 256. Структурная схема устройства для N = 256 приведена на фиг.10. Устройство содержит формирователь 1 данных первого этапа, формирователь 2 данных второго этапа, формирователь 3 данных третьего этапа, формирователь 4 данных четвертого этапа, арифметический блок 5, синхронизатор 6 и формирователь 7 тригонометрических коэффициентов. Размерности элементов рассчитаны по приведенным выше формулам для N = 256. Импульсный сигнал "Сброс", приходящий на управляющий вход устройства, обнуляет счетчик 57 синхронизатора 7, устанавливая управляющие сигналы U(8n), ..., U1 в низкий логический уровень. После окончания действия сигнала "Сброс" по первому тактовому импульсу, приходящему на тактовый вход устройства, на его информационный вход начинает последовательно поступать массив отсчетов OM0, ..., OM255 (последовательность N1 на фиг.11,а). Используя последовательность N1, формирователь 1.1 данных первого этапа формирует на своем информационном выходе последовательности X1(n) (фиг.12,в), X2(n) (фиг.12,г), X3(n) (фи г.12,д) и X4(n) (фиг.12,е) синхронно с поступлением информационный вход устройства отсчетов OM192, ..., OM255 (фиг.12,а) последовательности N1. Поскольку мультиплексор 44 находится в положении "0" (фиг.12,б и фиг.11,г), то арифметический блок 1.5 выполняет над последовательностями X1(n) (фиг.12,в), X2(n) (фиг.12,г), X3(n) (фи г.12,д) и X4(n) (фиг.12,е) первый этап быстрого преобразования Фурье i = 1 (фиг.11,б), формируя на своем информационном выходе последовательности X1(n) (фиг.12,ж) Y2(т) (фиг.12,з) Y3(n) (фиг.12,и) и Y4(n) (фиг.12, и), которые поступают на информационный вход формирователя 1.2 данных второго этапа. Формирователь 1.2 данных второго этапа формирует на своем информационном выходе последовательности X5 (фиг.13,в) X6 (фиг.13,г) X7 (фиг.13,д) и X8 (фи г.13,е), которые поступают на информационный вход арифметического блока 1.5 синхронно с поступлением на информационный вход устройства отсчетов OM0, ..., OM63 (фиг.13,а) последовательности N2 (фиг.11,а). Положения мультиплексора 24 показаны на фиг.13,к. Поскольку мультиплексор 44 находится в положении "1" (фиг. 13,б и фиг.11, г) то арифметический блок 1.5 выполняет над последовательностями X5(n) (фиг.13,в), X6(n) (фиг.13,г), X7(n) (фиг.13,д) и X8(n) (фиг.13,е) второй этап быстрого преобразования Фурье i = 2 (фиг.11,б), формируя на своем информационном выходе последовательности Y1(n) (фиг.13,ж), Y2(n) (фиг.13,з), Y3(n) (фиг.13,и) и Y4(n) (фи г.13,и), которые поступают на информационный вход формирователя 1.3 данных третьего этапа. Формирователь 1.3 данных третьего этапа формирует на своем информационном выходе последовательности X9 (фиг.13,в), X10 (фиг.14,г) X11 (фиг.14,д) и X12 (фиг.14,е), которые поступают на информационный вход арифметического блока 1.5 синхронно с поступлением на информационный вход устройства отсчетов OM65, ..., OM127 (фиг.14,а) последовательности N2 (фиг.11,а). Положения мультиплексора 32 показаны на фиг.14,к. Поскольку мультиплексор 44 находится в положении "2" (фиг.14,б и фиг.11,г) то арифметический блок 1.5 выполняет над последовательностями X9(n) (фиг.14,в), X10(n) (фиг.14,г), X11(n) (фиг.14,д) и X12(n) (фиг.14,е) третий этап быстрого преобразования Фурье i = 3 (фиг.11,б), формируя на своем информационном выходе последовательности Y1(n) (фиг.14,ж), Y2(n) (фиг.14,з), Y3(n) (фиг.14,и) и Y4(n) (фиг.14,й), которые поступают на информационный вход формирователя i.4 данных четвертого этапа. Формирователь i.4 данных четвертого этапа формирует на своем информационном выходе последовательности X13 (фиг.15,в), X6 (фиг.13,г), X7 (фиг.13,д) и XB (фиг.13,е), которые поступают на информационный вход арифметического блока 1.5 синхронно с поступлением на информационный вход устройства отсчетов OM0, ..., OM63 (фиг.13,а) последовательности N2 (фиг.11,а). Положения мультиплексора 40 показаны на фиг.15,к. Поскольку мультиплексор 44 находится в положении "3" (фиг.15,б и фиг.11,г) то арифметический блок 1.5 выполняет над последовательностями X13 (фиг.15,в), X6 (фиг.13,г) X7 (фиг.13,д) и XB (фиг.13,е) четвертый этап i = 4 быстрого преобразования Фурье, формируя на своем информационном выходе последовательности Y1(n) (фиг.15,ж), Y2(n) (фиг.15,з), Y3(n) (фиг.15,и) и Y4(n) (фиг.15,й), которые поступают на информационный выход устройства. Примечание. Запись ((N/4^ (4j - 3)) означает возведение в степень 4j - 3 числа N/4.