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

 

Изобретение относится к области вычислительной техники и может быть использовано в специализированных системах обработки сигналов высокой производительности для вычисления трехмерного дискретного преобразования Фурье. Устройство содержит N₁ вычислительных модулей, где N₁ - размерность входных данных x(i₂, i₃, i₄), 0≅i₂≅N₁-1, 0≅i₃≅N₂-1, 0≅i₄≅N₃-1, причем вычислительный модуль содержит блок управления, умножитель, сумматор, два регистра, две группы регистров, шестнадцать групп элементов И, семь групп элементов ИЛИ, пять элементов ИЛИ, элемент И и элемент ИЛИ-НЕ. 1 з. п. ф-лы, 3 табл., 3 ил.

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

Известно устройство, реализующее систолический способ вычисления одномерного ДПФ и содержащее два коммутатора, операционный блок, два блока постоянной памяти, группу из К-1 (К размер преобразования) операционных блоков, группу и К блоков хранения и блок управления /1/.

Недостатком этого устройства является невозможность вычисления трехмерного ДПФ.

Наиболее близким по технической сущности является устройство, реализующее систолический способ вычисления трехмерного ДПФ для данных размером N₁·N₂·N₃ и содержащее три многоканальные систолические матрицы, причем первая многоканальная систолическая матрица содержит N₁ вычислительных ячеек N₁ запоминающих ячеек (каждая запоминающая ячейка содержит регистр и сумматор), вторая многоканальная систолическая матрица содержит N₂ вычислительных ячеек (емкость каждой запоминающей ячейки составляет 2N₁-1 регистров) и третья систолическая матрица содержит N₃ вычислительных ячеек и N₃ запоминающих ячеек (емкость каждой запоминающей ячейки составляет 2N₁N₂ 1 регистров) /2/.

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

Устройство для вычисления трехмерного дискретного преобразования Фурье (фиг. 1, 2) содержит N₁ вычислительных модулей 7, где N₁ - размерность входных данных x(i₂, i₃, i₄), 0≅i₂≅N₁-1, 0≅i₃≅N₂-1, 0≅i₄≅N₃-1, причем информационный вход 1 устройства подключен к первому информационному входу первого вычислительного модуля 7о, 2i-й вход группы информационных входов подключен ко второму информационному входу 7i-го вычислительного модуля, первый 3, второй 4 и третий 5 управляющие входы устройства подключены соответственно к первому, второму и третьему управляющим входам первого вычислительного модуля 7о, информационный выход, первый, второй и третий управляющие выходы 7i-го вычислительного модуля подключены соответственно к информационному входу, первому, второму и третьему управляющим входам 7 (i+1)-го вычислительного модуля, второй информационный выход 7i-го вычислительного модуля подключен к 8i-му выходу устройства, тактовый вход 6 которого подключен к синхровходам всех вычислительных модулей 7, при этом в вычислительном модуле 7 первый 9 информационный вход подключен к первым входам элементов И 22 первой группы и информационному входу первого 18 регистра, выход которого подключен к первому входу умножителя 16 и первому 52 информационному выходу вычислительного модуля, выходы элементов И 22 первой группы подключены к соответствующим первым входам элементов ИЛИ 38 первой группы, выход которых подключен к информационному входу первого регистра 20₁ первой группы, выход которого подключен к первым входам элементов И второй 23, третьей 34 и четвертой 33 групп, вторые входы элементов И 23 второй группы подключены к выходу элемента ИЛИ-НЕ 51, а выходы к соответствующим первым входам элементов ИЛИ 39 второй группы, выходы которых подключены к информационному входу второго регистра 20₂ первой группы, выход 20i-го регистра первой группы подключен к информационному входу 20(i+1)-го регистра, выход 20N₃-го регистра первой группы подключен к первым входам элементов И пятой 24 и шестой 26 групп, вторые входы элементов И 24 пятой группы подключены к выходу первого элемента ИЛИ 45, а выход ко вторым входам элементов ИЛИ 38 первой группы, выход второго элемента ИЛИ 46 подключен к первым входам элементов И 25 седьмой группы, выходы которых подключены к соответствующим вторым входам элементов ИЛИ 39 второй группы, выходы элементов И 26 шестой группы подключены к соответствующим первым входам элементов ИЛИ 40 третьей группы, вторые входы которых подключены к соответствующим выходам элементов И 28 девятой группы, а выходы к информационному входу первого регистра 21₁ второй группы, выход которого подключен к первым входам элементов И десятой 27, одиннадцатой 36 и двенадцатой 35 групп, выходы элементов И 27 десятой группы подключены к соответствующим входам элементов ИЛИ 41 четвертой группы, выходы которых подключены к информационному входу второго регистра 21₂ второй группы, выход 21i-го регистра подключен к информационному входу 21 (i+1)-го регистра, выход 21 N₃(N₁+N₂)-го регистра подключен к первым входам элементов И девятой 28 и тринадцатой 31 групп, второй 10 информационный вход вычислительного модуля подключен к первым входам элементов И 30 четырнадцатой группы, выходы которых подключены к соответствующим первым входам элементов ИЛИ 42 пятой группы, вторые входы которых подключены к соответствующим выходам элементов И 31 тринадцатой группы, а выходы к информационному входу второго 19 регистра, выход которого подключен к первым входам элементов И пятнадцатой 32 и шестнадцатой 37 групп, а синхровход к выходу элемента И 50, первый вход которого подключен к выходу третьего элемента ИЛИ 47, выход четвертого элемента ИЛИ 48 подключен ко вторым входам элементов И 32 пятнадцатой группы, выходы которых подключены к соответствующим первым входам элементов ИЛИ 43 шестой группы, вторые входы которых подключены к соответствующим выходам элементов И 34 третьей группы, а третьи входы к соответствующим выходам элементов И 36 одиннадцатой группы, второй вход умножителя 16 подключен к выходам элементов ИЛИ 43 шестой группы, а выход к первому входу сумматора 17, второй вход которого подключен к выходу элементов ИЛИ 44 седьмой группы, первые входы которых подключены к соответствующим выходам элементов И 35 двенадцатой группы, а вторые входы к соответствующим выходам элементов И 37 шестнадцатой группы, выход сумматора 7 подключен ко вторым входам элементов И 25 седьмой группы и первым входам элементов И 29 восьмой группы, тактовый вход 14 вычислительного модуля подключен к синхровходам первого 18 регистра, регистрам первой 20 и второй 21 групп, второму входу элемента И 50 и блока управления 15, первый, второй и третий входы которого подключены соответственно к первому 11, второму 12 и третьему 13 управляющим входам вычислительного модуля, первый, второй и третий информационные выходы которого подключены соответственно к первому 54, второму 55 и третьему 56 выходам блока управления, четвертый выход которого подключен ко вторым входам элементов И 22 первой группы, пятый выход блока управления подключен ко вторым входам элементов И 30 четырнадцатой группы, первого 45 и третьего 47 элемента ИЛИ, шестой выход блока управления подключен к первому входу первого элемента ИЛИ 45, седьмой выход блока управления подключен ко вторым входам элементов И 26 шестой группы, вторым инверсным входам элементов И 28 девятой группы и третьему входу первого элемента ИЛИ 45, восьмой выход блока управления подключен к четвертому входу первого элемента ИЛИ 45, девятый выход блока управления подключен ко вторым входам элементов И 31 тринадцатой группы и третьего элемента ИЛИ 47, десятый выход блока управления подключен к первым входам элементов ИЛИ-НЕ 51, второго 46, четвертого 48 и пятого 49 элементов ИЛИ, одиннадцатый выход управления подключен ко вторым входам элемента ИЛИ-НЕ 51, второго 46, четвертого 48 и пятого 49 элементов ИЛИ, двенадцатый выход блока управления подключен ко вторым входам элементов И 34 третьей и двенадцатой 35 групп и вторым инверсным входам элементов И 27 десятой группы, тринадцатый выход блока управления подключен ко вторым входам элементов И 36 одиннадцатой и шестнадцатой 37 групп, при этом первый вход 57 блока управления подключен к входу первого элемента НЕ 75, первым входам четвертого 71, пятого 72, шестого 73 и седьмого 74 элементов И и информационному входу первого 61 триггера, выход которого подключен к первому 78 выходу блока управления, второй 58 вход которого подключен к входу второго элемента НЕ 76, вторым входам второго 69, третьего 70, шестого 73 и седьмого 74 элементов И и информационному входу второго 62 триггера, выход которого подключен ко второму 79 выходу блока управления, третий вход 59 которого подключен к входу третьего элемента НЕ 77, третьим входам первого 68, третьего 70, пятого 72 и седьмого 74 элементов И и информационному входу третьего 63 триггера, выход которого подключен к третьему 80 выходу блока управления, выход первого элемента НЕ 75 подключен к первым входам первого 68, второго 69 и третьего 70 элементов И, выход второго элемента НЕ 76 подключен ко вторым входам первого 68, четвертого 71 и пятого 72 элементов И, выход третьего элемента НЕ 77 подключен к третьим входам второго 69, четвертого 71 и шестого 73 элементов И, выход с первого по шестой элементов И 68 73 подключены соответственно к выходам с четвертого по девятый 81 86 блока управления, выходы второго 69, третьего 70, пятого 72 и седьмого 74 элементов И подключены к информационным входам соответственно четвертого 64, пятого 65, шестого 66 и седьмого 67 триггеров, выходы которых подключены соответственно к выходам с десятого по тринадцатый 90 93 блока управления, синхровход 60 которого подключен к синхровходам всех триггеров.

Устройство для вычисления трехмерного ДПФ (фиг. 1) содержит информационный вход 1, группу информационных входов , первый 3, второй 4 и третий 5 управляющие входы, тактовый вход 6, вычислительные модули и группу информационных входов .

Вычислительный модуль 7 (фиг. 2) содержит первый 9 и второй 10 информационные входы, первый 11, второй 12 и третий 13 управляющие входы, тактовый вход 14, блок управления 15, умножитель 16, сумматор 17, регистры 18 и 19, первую группу регистров , вторую группу регистров , группы элементов И 22 37, группы элементов ИЛИ 38 44, элементы ИЛИ 45 49, элемент И 50, элемент ИЛИ-НЕ 51, первый 52 и второй 53 информационные выходы, первый 52 и второй 53 информационные выходы, первый 54, второй 55 и третий 56 управляющие выходы.

Блок управления 15 (фиг. 3) содержит первый 57, второй 58 и третий 59 управляющие входы, тактовый вход 60, триггеры 61 67, элементы И 68 74, элементы НЕ 75 77, выходы 78 90.

В основу работы устройства положено вычисление трехмерного дискретного преобразования Фурье, определяемое выражением где x(q₁, q₂, q₃) входная последовательность, 0≅q₁≅N₁-1, 0≅q₂≅N₂-1, 0≅q₃≅N₃-1, N₁, N₂, N₃ целые положительные числа, Алгоритм вычисления трехмерного дискретного преобразования Фурье задается следующими рекуррентными выражениями: x⁰(i₁, i₂, i₃, i₄) x⁰(i₁-1, i₂, i₃, i₄), 0≅i₁≅N₁-1, 0≅i₂≅N₁-1, 0≅i₃≅N₂-1, 0≅i₄≅N₃-1} 0≅i₁≅N₁-1, 0≅i₂≅N₁+N₂-1, 0≅i₃≅N₂-1, 0≅i₄≅N₃-1} 0≅i₁≅N₁-1, N₁≅i₂≅N₁+N₂-1, N₂≅i₃≅N₂+N₃-1, 1≅i₄≅N₃-1} Начальные значения x(i₂, i₃, i₄), переменной x⁰(i₂, i₃, i₄) присваиваются при i₁=0, 0≅i₂≅N₁-1, 0≅i₃≅N₂-1, 0≅i₄≅N₃-1.

Начальные значения переменной x⁰(i₁, i₂, i₃, i₄), присваиваются при i₁=0, N₁≅i₂≅N₁+N₂-1, 1≅i₃≅N₂-1, 0≅i₄≅N₃-1.

Начальные значения переменной x₀(i₁, i₂, i₃, i₄), присваиваются при i₁=0, N₁≅i₂≅N₁+N₂-1, N₂≅i₃≅N₂+N₃-1, 1≅i₄≅N₃-1.

Начальные значения переменной x³(i₁, i₂, i₃, i₄), присваиваются при 0≅i₁≅N₁-1, 1≅i₂≅N₁-1, 0≅i₃≅N₂-1, i₄=0.

Искомый результат вычисления трехмерного дискретного преобразования Фурье определяется равенством x³(i₁, i₂, i₃, N₃-1) Y³(i₁, i₂-N₁, i₃-N₂),
0≅i₁≅N₁-1, N₁≅i₂≅N₁+N₂-1, N₂≅i₃≅N₂+N₃-1.

Вычислительный модуль 7 (фиг. 2) обладает возможностью реализации следующих функций:

где А^j+1, В^j+1 и Г^j+1 значения соответственно на первом, втором и третьем управляющих выходах вычислительного модуля на (j+1)-м такте,
α^j, β^j и γ^j значения соответственно на первом, втором и третьем управляющих входах вычислительного модуля на j-м такте,
Р^j+1=p^j,
где Р^j+1 значение на первом информационном выходе вычислительного модуля на (j+1)-м такте,
р_j значение на первом информационном входе вычислительного модуля на j-м такте,

где ω^j значение на втором информационном входе вычислительного модуля на j-м такте,



Входной поток данных задается следующими выражениями.

На входы 2i₁ подается последовательность коэффициентов (0≅i₁≅N₁-1, 1≅i₂≅N₁-1,
в моменты времени

На вход 1 подается последовательность коэффициентов (N₁≅i₂≅N₁+N₂-1, 1≅i₃≅N₂-1)
в моменты времени

На вход 1 подается последовательность коэффициентов
(N₂≅i₃≅N₂+N₃-1, 1≅i₄≅N₃-1)
в моменты времени

На вход 1 подается входная последовательность x(i₂, i₃, i₄) в моменты времени

0≅i₂≅N₁-1, 0≅i₃≅N₂-1, 0≅i₄≅N₃-1.

На входы 4, 5 и 6 подаются соответственно управляющие сигналы α, β и γ, принимающие значения 0 или 1.

Управление работой вычислительных модулей 7 задается комбинацией управляющих сигналов , которые определяются переменными i₁, i₂, i₃, i₄:

Комбинация управляющих сигналов τ=(α, β, γ) подается на входы 3, 4 и 5 в моменты времени
t_τ=i₁+N₃·i₂+N₃(N₁+N₂)i₃+i₄.
Элементы выходного потока данных Y³(i₁, i₂, i₃)=x³(i₁, i₂+N₁, i₃+N₂, N₃-1) при 0≅i₁≅N₁-1, 0≅i₂≅N₂-1, 0≅i₃≅N₃-1 формируются в вычислительном модуле 7i₁-м в моменты времени

которые выдаются с соответствующих выходов 8i.

Последний элемент Y³(N₁-1, N₂-1, N₃-1) формируется на (N₃(N₂+N₃)+(N₁+N₂)+N₁-1)-м такте.

Рассмотрим работу устройства для случая N₁=3, N₂=N₃=2 (фиг. 1). Устройство содержит три вычислительных модуля 7₀, 7₁ и 7₂. Весовые коэффициенты подаются соответственно на выходы 2₀, 2₁ и 2₂. Весовые коэффициенты и входные данные x(i₂, i₃, i₄) подаются в соответствующие моменты времени на вход 1, а управляющие сигналы α, β и γ соответственно на входы 3, 4 и 5. Выходные данные Y(i₁, i₂, i₃) формируются на соответствующих выходах 8₀, 8₁ и 8₂. В таблицах 1, 2 и 3 приведены организация подачи входных данных, состояние регистров, формируемые значения на выходе сумматора и выходные данные соответственно в вычислительных модулях 7₀, 7₁, 7₂. ТТТ1 ТТТ2 ТТТ3 ТТТ4 ТТТ5 ТТТ6 ТТТ7 ТТТ8 ТТТ9 ТТТ10

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

1. Устройство для вычисления трехмерного дискретного преобразования Фурье, содержащее N₁ вычислительных модулей, где N₁ размерность входных данных x(i₂, i₃, i₄), 0≅i₂≅N₁-1, 0≅i₃≅N₂-1, 0≅i₄≅N₃-1, при этом каждый вычислительный модуль содержит умножитель, сумматор и два регистра, причем выход первого регистра является первым информационным выходом модуля и соединен с первым информационным входом умножителя, выход которого соединен с первым информационным входом сумматора, выход которого является вторым информационным выходом модуля, первый информационный вход которого соединен с информационным входом первого регистра, информационный вход устройства подключен к первому информационному входу первого вычислительного модуля, отличающееся тем, что каждый вычислительный модуль содержит блок управления, две группы регистров, шестнадцать групп элементов И, семь групп элементов ИЛИ, пять элементов ИЛИ, элемент И, элемент ИЛИ-НЕ, причем i-й вход группы информационных входов устройства подключен к второму информационному входу i-го вычислительного модуля, первый, второй и третий управляющие входы устройства подключены соответственно к первому, второму и третьему управляющим входам первого вычислительного модуля, информационный выход, первый, второй и третий управляющие выходы j-го вычислительного модуля подключены соответственно к первому информационному входу, первому, второму и третьему управляющим входам (j + 1)-го вычислительного модуля, второй информационный выход i-го вычислительного модуля подключен к i-му выходу устройства, тактовый вход которого подключен к синхровходам всех вычислительных модулей, первый информационный вход i-го вычислительного модуля подключен к первым входам элементов И первой группы, выходы которых подключены к первым входам элементов ИЛИ первой группы, выходы которых подключены к группе информационных входов первого регистра первой группы, выход которого подключен к первым входам элементов И второй, третьей и четвертой групп, вторые входы элементов И второй группы подключены к выходу элемента ИЛИ-НЕ, а выходы к первым входам элементов ИЛИ второй группы, выходы которых подключены к информационному входу второго регистра первой группы, выход l-го регистра первой группы подключен к информационному входу (l + 1)-го регистра первой группы, выход N-го регистра первой группы подключен к первым входам элементов И пятой и шестой групп, вторые входы элементов И пятой группы подключены к выходу первого элемента ИДИ, а выходы элементов И пятой группы к вторым входам элементов ИЛИ первой группы, выход второго элемента ИЛИ подключен к первым входам элементов И седьмой группы, выходы которых подключены к вторым входам элементов ИЛИ второй группы, выходы элементов И шестой группы подключены к первым входам элементов ИЛИ третьей группы, первые входы элементов И восьмой группы соединены с вторыми входами элементов И седьмой группы и выходом сумматора, выходы элементов И девятой группы к вторым входам элементов ИЛИ третьей группы, выходы которых подключены к информационному входу первого регистра второй группы, выход которого подключен к первым входам элементов И десятой, одиннадцатой и двенадцатой групп, выходы элементов И десятой группы подключены к первым входам элементов ИЛИ четвертой группы, выходы которых подключены к информационному входу второго регистра второй группы, выход r-го регистра подключен к информационному входу (r + 1)-го регистра, выход N₃(N₁ + N₂)-го регистра подключен к первым входам элементов И девятой и тринадцатой групп, второй информационный вход вычислительного модуля подключен к первым входам элементов И четырнадцатой группы, выходы которых подключены к первым входам элементов ИЛИ пятой группы, вторые входы которых подключены к выходам элементов И тринадцатой группы, а выходы к информационному входу второго регистра, выход которого подключен к первым входам элементов И пятнадцатой и шестнадцатой групп, синхровход второго регистра подключен к выходу элемента И, первый вход которого подключен к выходу третьего элемента ИЛИ, выход четвертого элемента ИЛИ к вторым входам элементов И пятнадцатой группы, выходы которых подключены к первым входам элементов ИЛИ шестой группы, вторые входы которых подключены к соответствующим выходам элементов И третьей группы, третьи входы элементов ИЛИ шестой группы подключены к выходам элементов И одиннадцатой группы, второй вход умножителя подключен к выходам элементов ИЛИ шестой группы, второй вход сумматора к выходу элементов ИЛИ седьмой группы, первые входы которых подключены к выходам элементов И двенадцатой группы, вторые входы элементов ИЛИ седьмой группы к выходам элементов И шестнадцатой группы, выходы элементов И восьмой группы к вторым входам элементов ИЛИ четвертой группы, выход пятого элемента ИЛИ к вторым входам элементов И четвертой группы, выходы которых подключены к третьим входам элементов ИЛИ седьмой группы, тактовый вход вычислительного модуля подключен к синхровходам первого регистра, регистров первой и второй групп, второму входу элемента И и синхровходу блока управления, первый, второй и третий входы которого подключены соответственно к первому, второму и третьему управляющим входам вычислительного модуля, первый, второй и третий информационные выходы которого подключены соответственно к первому, второму и третьему выходам блока управления, четвертый выход которого подключен к вторым входам элементов И первой группы, пятый выход блока управления подключен к вторым входам элементов И четырнадцатой группы, первого и третьего элементов ИЛИ, шестой выход блока управления к второму входу первого элемента ИЛИ, седьмой выход к вторым входам элементов И шестой группы, вторым инверсным входам элементов И девятой группы и третьему входу первого элемента ИЛИ, восьмой выход блока управления к четвертому входу первого элемента ИЛИ, девятый выход к вторым входам элементов И тринадцатой группы и третьего элемента ИЛИ, десятый выход к первым входам элемента ИЛИ-НЕ, второго, четвертого и пятого элементов ИЛИ, одиннадцатый выход к вторым входам элемента ИЛИ-НЕ, второго, четвертого и пятого элементов ИЛИ, двенадцатый выход к вторым входам элементов И третьей и двенадцатой групп и вторым инверсным входам элементов И десятой группы, тринадцатый выход к вторым входам элементов И одиннадцатой и шестнадцатой групп.

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

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5, Рисунок 6, Рисунок 7, Рисунок 8, Рисунок 9, Рисунок 10, Рисунок 11, Рисунок 12, Рисунок 13