УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ДВУМЕРНОГО ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ Российский патент 1995 года по МПК G06F17/14 

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

Известно устройство для вычисления двумерного дискретного преобразования Фурье, содержащее Р вычислительных модулей, где Р порядок входной матрицы, и блок ввода [1]
Недостатками этого устройства являются большие аппаратурные затраты и невозможность вычисления двумерного дискретного преобразования Фурье для случая, когда размерность входной матрицы больше числа Р.

Наиболее близким по технической сущности к предлагаемому является устройство, содержащее три блока ввода, Р вычислительных модулей первого типа (Р порядок входной матрицы) и Р вычислительных модулей второго типа [2]
Недостатками данного устройства являются большие аппаратурные затраты и невозможность вычисления двумерного дискретного преобразования Фурье в случае, если размерность входной матрицы превышает число вычислительных модулей в устройстве.

Цель изобретения сокращение аппаратурных затрат.

Поставленная цель достигается тем, что устройство для вычисления двумерного дискретного преобразования Фурье содержит m вычислительных модулей 7, где m фиксированное число (m ≅ T, T размерность результирующей матрицы Y[I, T] ) n регистров 8, где n P(Q+I)-2m (P и Q размерности входной матрицы Х[P, Q] ), три группы триггеров 9 11, группу элементов ИЛИ 12, три элемента ИЛИ 13 15 и выход 16, причем первый 1 информационный вход устройства подключен к первым входам группы элементов ИЛИ 12, выход которого подключен к первому информационному входу первого вычислительного модуля 7₁, второй 2 информационный вход устройства подключен ко второму информационному входу первого вычислительного модуля 7₁, первый 3, второй 4 и третий 5 управляющие входы устройства подключены к первым входам соответственно первого 13, второго 14 и третьего 15 элементов ИЛИ, выходы которых подключены соответственно к первому, второму и третьему управляющим входам первого вычислительного модуля 7₁, первый и второй информационные выходы, первый, второй и третий управляющие выходы i-го вычислительного модуля 7 (i ) подключены соответственно к первому и второму информационным входам, первому, второму и третьему управляющим входам (i+1)-го вычислительного модуля 7, первый информационный выход 7_m-го вычислительного модуля подключен к информационному входу 8_n-го регистра, информационный вход 8_i-го регистра (i ) подключен к выходу 8_i+1-го регистра, выход первого 8₁ регистра подключен ко вторым входам группы элементов ИЛИ 12, второй информационный выход 7_m-го вычислительного модуля подключен к выходу 16 устройства, первый, второй и третий управляющие выходы 7_m-го вычислительного модуля подключены к информационным входам n-х триггеров соответственно первой 9, второй 10 и третьей 11 групп, информационный вход i-го триггера (i ) j-й группы (j ) подключен к выходу (i+1)-го триггера j-й группы, выходы первых триггеров первой 9, второй 10 и третьей 11 групп подключены соответственно к вторым входам первого 13, второго 14 и третьего 15 элементов ИЛИ, тактовый вход 6 устройства подключен к синхровходам всех вычислительных модулей, регистров и триггеров, при этом каждый вычислительный модуль 7 содержит тринадцать групп элементов И 23-35, семь элементов И 36 42, шесть групп элементов ИЛИ 43-48, семь элементов ИЛИ 49 55, пять регистров 56-60, группу регистров 61, двенадцать триггеров 62 73, умножитель 74 и сумматор 75, причем первый 17 информационный вход вычислительного модуля подключен к информационному входу первого 56 регистра, выход которого подключен к первым входам первой 24, второй 27 и третьей 28 групп элементов И и информационному входу второго 57 регистра, выход которого подключен к первому 76 информационному выходу вычислительного модуля, второй 18 информационный вход которого подключен к информационному входу третьего 58 регистра, выход которого подключен к первым входам четвертой 23 и пятой 25 групп элементов И, вторые входы пятой 25 группы элементов И подключены к выходу первого 50 элемента И, а выход к первым входам третьей 44 группы элементов ИЛИ, выход которого подключен ко второму информационному выходу вычислительного модуля, выход четвертой 23 группы элементов И подключен к первым входам первой 43 группы элементов ИЛИ, вторые входы которой подключены к выходу первой 24 группы элементов И, а выход к информационному входу четвертого 59 регистра, синхровход которого подключен к выходу первого 36 элемента И, первый вход которого подключен к выходу второго 49 элемента ИЛИ, выход четвертого 59 регистра подключен к первому входу умножителя 74, выход которого подключен к первому входу сумматора 75, второй вход которого подключен к выходу второй 46 группы элементов ИЛИ, а выход к первым входам шестой 29, седьмой 32 и восьмой 26 групп элементов И, выход которой подключен ко вторым входам третьей 44 группы элементов ИЛИ, выход третьего 55 элемента ИЛИ подключен к первым входам девятой 34 группы элементов И, выходы девятой 34 и десятой 33 групп элементов И подключены соответственно к первому и второму входам четвертой 47 группы элементов ИЛИ, выход которой подключен ко второму входу умножителя 74, выход третьей 28 группы элементов И подключен к первым входам второй 46 группы элементов ИЛИ, вторые входы которой подключены к выходу одиннадцатой 31 группы элементов И, второй вход которой подключен к выходу четвертого 54 элемента ИЛИ, выход пятого 51 элемента ИЛИ подключен ко вторым входам второй 27 группы элементов И, выход которой подключен к первым входам пятой группы 45 элементов ИЛИ, вторые входы которой подключены к выходу элементов И шестой 29 группы, а выход к информационному входу первого регистра 57₁группы, выход 57_i-го регистра группы (i ) подключен к информационному входу 57_i+1-го регистра группы, выход 57_Р-го регистра группы подключен к первым входам десятой 33, одиннадцатой 31, двенадцатой 35 и тринадцатой 30 групп элементов И, вторые входы группы И 30 подключены к выходу шестого 52 элемента ИЛИ, а выход к третьим входам пятой 45 группы элементов ИЛИ, выход седьмого 53 элемента ИЛИ подключен ко вторым входам элементов И седьмой 32 группы, выходы которых подключены к первым входам элементов ИЛИ шестой 48 группы, вторые входы которой подключены к выходам элементов И двенадцатой 35 группы, а выходы к информационному входу пятого 60 регистра, выход которого подключен ко вторым входам элементов И девятой 34 группы, первый 19 управляющий вход вычислительного модуля подключен к инверсным первым входам второго 37, третьего 38 и четвертого 39 элементов И, первым входам пятого 40, шестого 41 и седьмого 42 элементов И и информационному входу первого 68 триггера, выход которого подключен к информационному входу второго 69 триггера, выход которого подключен к первому 78 управляющему выходу вычислительного модуля, второй 20 управляющий вход которого подключен к инверсным вторым входам второго 37, четвертого 39, пятого 40 и шестого 41 элементов И, вторым входам третьего 38 и седьмого 42 элементов И и информационному входу третьего 70 триггера, выход которого подключен к информационному входу четвертого 71 триггера, выход которого подключен к второму 79 управляющему выходу вычислительного модуля, третий 21 управляющий вход которого подключен к инверсным третьим входам третьего 38, четвертого 39, шестого 41 и седьмого 42 элементов И, третьим входам второго 37 и пятого 40 элементов И и информационному входу пятого 72 триггера, выход которого подключен к информационному входу шестого 73 триггера, выход которого подключен к третьему 80 управляющему выходу вычислительного модуля, выходы элементов И со второго 37 по седьмой 42 подключены соответственно к информационным входам триггеров с седьмого 62 по двенадцатый 67, выход седьмого 62 триггера подключен к первым входам второго 49 и пятого 51 элементов ИЛИ и вторым входам элементов И четвертой 23 группы, выход восьмого 63 триггера подключен к первому входу первого 50 и второму входу пятого 51 элементов ИЛИ, выход девятого 64 триггера подключен ко вторым входам элементов И третьей 28, шестой 29 и десятой 33 групп, выход десятого 65 триггера подключен ко вторым входам элементов И первой 24 и двенадцатой 35 групп, второму входу второго 49 и первому входу шестого 52 элементов ИЛИ, выход одиннадцатого 66 триггера подключен к первым входам третьего 55, четвертого 54 и седьмого 53 элементов ИЛИ и вторым входам первого 50 и шестого 52 элементов ИЛИ, выход двенадцатого 67 триггера подключен к вторым входам восьмой 26 группы элементов И, вторым входам третьего 55, четвертого 54 и седьмого 53 элементов ИЛИ и третьему входу шестого 52 элемента ИЛИ, синхровход 22 вычислительного модуля подключен к синхровходам первого 56, второго 57, третьего 58 и пятого 50 регистров, регистров группы 61, триггеров 62-73 и второму входу первого 36 элемента И.

На фиг. 1 представлена структурная схема устройства для вычисления двумерного дискретного преобразования Фурье; на фиг. 2 структурная схема вычислительного модуля.

Устройство для вычисления двумерного дискретного преобразования Фурье (фиг. 1) содержит первый 1 и второй 2 информационные входы, первый 3, второй 4 и третий 5 управляющие входы, тактовый вход 6, вычислительные модули 7_i (i ), регистры 8_i (i ), первую 9_i, вторую 10_i и третью 11_i (i ) группы триггеров, группу элементов ИЛИ 12, элементы ИЛИ 13-15 и выход 16.

Вычислительный модуль 7 (фиг. 2) содержит первый 17 и второй 18 информационные входы, первый 19, второй 20 и третий 21 управляющие входы, синхровход 22, группы элементов И 23 35, элементы И 36-42, группы элементов ИЛИ 43-48, элементы ИЛИ 49-55, первый 56, второй 57, третий 58, четвертый 59 и пятый 60 регистры, группы регистров 61i (i ), триггеры 62-73, умножитель 74, сумматор 75, первый 76 и второй 77 информационные выходы, первый 78, второй 79 и третий 80 управляющие выходы.

В основу работы устройства положен алгоритм вычисления двумерного дискретного преобразования Фурье в виде выражений:
Y_ij=x_pq·ωiI

^p·ωjT^q, i , j ,
b_jp=x_pq·ωjT^q, j , p ,
Y_ij=b_jp·ωiI^p, которые задаются следующими рекуррентными соотношениями:
j , p , q :
b(j,P,0) x_PQ-1,
b(j,P,q) b(j,P,q-1) ˙ω_T^j + x_pQ-1-q,
b_jP b(j,p,Q-1);
i , j , p :
Y(i,j,0) b_jP-1;
Y(i,j,P) Y(i,j,P-1) ˙ω_Iⁱ + b_jP-1-P,
Y_ij Y(i,j,P-1).

Для случая, когда m фиксированное число (2 ≅m≅ T), значение T_m T/m целое число. Если T_m не целое число, то в качестве T берется m=T/m ( ближайшее сверху целое). При этом матрицуb_jP} необходимо дополнить строками, а матрицу Y_ij} столбцами. Вектор (ω_T⁰, ω_T¹,ω_T^T-1) дополняется до m=T/m элементов нулями. Дополнительные столбцы матрицыYij} при выводе не принимаются во внимание.

Вычислительный модуль 7 обладает возможностью реализации следующих функций:
A^j+2 α^j
B^j+2 β^j
Γ^j+2= γ^j где A^j+2, B^j+2 и Γ^j+2 значения управляющих сигналов соответственно на первой 78, втором 79 и третьем 80 управляющих выходах вычислительного модуля на (j+2)-м такте,
α^j, β^j и γ^j значения управляющих сигналов соответственно на первом 19, втором 20 и третьем 21 управляющих входах вычислительного модуля на j-м такте,
F^j+2 x^j, где F^j+2 значение на первом 76 информационном выходе вычислительного модуля на (j+2)-м такте,
х^j значение на первом 17 информационном входе вычислительного модуля на j-м такте,
Z^j+1= где
a^j=
b^j=
fj2

=
fj3= ,и 1,
fj4=
f₅^j xj^-1, где Z^j+1 значение на втором 77 информационном входе вычислительного модуля на (j+1)-м такте,
ω^j значение на втором 18 информационном входе вычислительного модуля
μ₁^j=(α^j-1, β^j-1, γ^j-1) (0, 0, 1),
μ₂^j=(α^j-1, β^j-1, γ^j-1) (0, 1, 0),
μ₃^j=(α^j-1, β^j-1, γ^j-1) (0, 0, 0),
μ₄^j=(α^j-1, β^j-1, γ^j-1) (1, 0, 1),
μ₅^j=(α^j-1, β^j-1, γ^j-1) (1, 0, 0),
μ₆^j=(α^j-1, β^j-1, γ^j-1) (1, 1, 0).

Рассмотрим работу устройства для случая I 2, T 6, P 3 и Q 3:
j , p :
b(j,P,0) x_P2,
q 1:
b(j,P,1) b(j,P,0)˙ω_T^j + x_P1,
q 2:
b(j,P,2) b(j,P,1) ˙ω_T^j x_P0,
b_jP b(j,P,2);
i , j :
Y(i,j,0) b_j2,
P 1:
Y(i,j,1) Y(i,j,0) ˙ω_Iⁱ + b_j1,
P 2:
Y(i,j,2) Y(i,j,1) ˙ω_Iⁱ + b_j0,
Y_ij Y(i,j,2).

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

На вход подаются элементы х и ω_Iⁱ в моменты времени:
t P -1 p + P(Q 1 q),
p , q ,
t ω_Iⁱ= P(I + Q i 1).

На вход 2 подаются элементы ω_T^δ+(γ-1)m в моменты времени
t_ωT ( γ- 1)P(Q + I) + δ,
0 ≅δ≅ m-1, 1≅γ≅ T_m.

На входы 3, 4 и 5 подается комбинация управляющих сигналов τ_ip=(α,β,γ) i p представляемая матрицей вида:
τ_ip= в моменты времени
t P_i + p
На выходе 16 формируются элементы Y_i,δ+(γ-1)m в моменты времени
t=γP(Q + I) + m + δ P_i 1, 0 ≅δ≅ m-1, 1≅γ≅ T_m.

Для I 2, T 6, P 3 и Q 3 организация входного и выходного потоков данных, состояния регистров и результаты вычислений на выходе умножителя в вычислительных модулях 7₀, 7₁ и 7₂ приведены в табл, 1, 2 и 3.

Изобретение относится к вычислительной технике и может быть использовано в вычислительных системах обработки сигналов высокой производительности для вычисления двумерного дискретного преобразования Фурье. Цель изобретения сокращение аппаратных затрат. Цель изобретения достигается тем, что устройство содержит m вычислительных модулей, m фиксированное число, m ≅ J (J - разномерность результирующей матрицы Y [I, J]), n регистров, где n P(Q + I) 2m (P и Q разномерность входной матрицы X [P, Q]), три группы триггеров 9₁-9_n, 10₁-10_n, 11₁-11_n группу элементов ИЛИ 12 и три элемента ИЛИ 13, 14, 15, причем вычислительный модуль содержит тринадцать групп элементов И, семь элементов И, шесть групп элементов ИЛИ, семь элементов ИЛИ, пять регистров, группу регистров, двенадцать триггеров, умножитель и сумматор. 1 з. п. ф-лы, 2 ил. 3 табл.

1. УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ДВУМЕРНОГО ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее m вычислительных модулей, m фиксированное число, m ≅ τ где t размерность результирующей матрицы Y[1,τ] причем тактовый вход устройства подключен к тактовым входам вычислительных модулей с первого по m-й, первый и второй информационные выходы, первый, второй и третий управляющие выходы i-го вычислительного модуля ( ) подключены соответственно к первому и второму информационным входам, первому, второму и третьему управляющим входам (i + 1)-го вычислительного модуля, отличающееся тем, что в него введены n регистров, где n P(Q + 1) 2m, P и Q - размерность входной матрицы X[P, Q] три группы по n триггеров, группа элементов ИЛИ и три элемента ИЛИ, причем первый информационный вход устройства подключен к первым входам элементов ИЛИ группы, выходы которых подключены к первому информационному входу первого вычислительного модуля, второй информационный вход устройства подключен к второму информационному входу первого вычислительного модуля, первый, второй и третий управляющие входы устройства подключены к первым входам соответственно первого, второго и третьего элементов ИЛИ, выходы которых подключены соответственно к первому, второму и третьему управляющим входам первого вычислительного модуля, первый информационный выход m-го вычислительного модуля подключен к информационному входу n-го регистра, информационный вход i-го регистра подключен к выходу (i + 1)-го регистра, выход первого регистра подключен к вторым входам элементов ИЛИ группы, второй информационный выход m-го вычислительного модуля подключен к выходу устройства, первый, второй и третий управляющие выходы m-го вычислительного модуля подключены к информационным входам n триггеров соответственно первой, второй и третьей групп, информационный вход k-го триггера подключен к выходу (k + 1)-го триггера j-й группы, выходы первых триггеров первой, второй и третьей групп подключены к вторым входам первого, второго и третьего элементов ИЛИ соответственно, тактовый вход устройства подключен к тактовым входам триггеров первой, второй и третьей групп и n регистров. 2. Устройство по п. 1, отличающееся тем, что вычислительный модуль содержит тринадцать групп элементов И, семь элементов И, шесть групп элементов ИЛИ, семь элементов ИЛИ, пять регистров, группу регистров, двенадцать триггеров, умножитель и сумматор, причем первый информационный вход вычислительного модуля подключен к информационному входу первого регистра, выход которого подключен к первым входам элементов И первого, второй и третьей групп и информационному входу второго регистра, выход которого подключен к первому информационному выходу вычислительного модуля, второй информационный вход которого подключен к информационному входу третьего регистра, выход которого подключен к первым входам элементов И четвертой и пятой групп, вторые входы элементов И пятой группы подключены к выходу первого элемента ИЛИ, выходы элементов И пятой группы подключены к первым входам элементов ИЛИ третьей группы, выходы которых подключены к второму информационному выходу вычислительного модуля, выходы элементов И четвертой группы подключены к первым входам элементов ИЛИ первой группы, вторые входы которых подключены к выходу элементов И первой группы, а выход элементов ИЛИ первой группы подключен к информационному входу четвертого регистра, синхровход которого подключен к выходу первого элемента И, первый вход которого подключен к выходу второго элемента ИЛИ, выход четвертого регистра подключен к первому входу умножителя, выход которого подключен к первому входу сумматора, второй вход которого подключен к выходам элементов ИЛИ второй группы, а выход сумматора подключен к первым входам элементов И шестой, седьмой и восьмой групп, выходы которых подключены к вторым входам элементов ИЛИ третьей группы, выход третьего элемента ИЛИ подключен к первым входам девятой группы элементов И, выходы элементов И девятой и десятой групп подключены соответственно к первому и второму входам элементов ИЛИ четвертой группы, выходы которых подключены к вторым входам умножителя, выходы элементов И третьей группы подключены к первым входам элементов ИЛИ второй группы, вторые входы которых подключены к выходу элементов И одиннадцатой группы, вторые входы которых подключены к выходу четвертого элемента ИЛИ, выход пятого элемента ИЛИ подключен к вторым входам элементов И второй группы, выходы которых подключены к первым входам элементов ИЛИ пятой группы, вторые входы которых подключены к выходу элементов И шестой группы, а выход к информационному входу первого регистра группы, выход i-го регистра группы подключен к информационному входу (i + 1)-го регистра группы, выход P-го регистра группы подключен к первым входам элементов И десятой, одиннадцатой, двенадцатой и тринадцатой групп, вторые входы которых подключены к выходу шестого элемента ИЛИ, а выход к третьим входам элементов ИЛИ пятой группы, выход седьмого элемента ИЛИ подключен к вторым входам элементов И седьмой группы, выходы которых подключены к первым входам элементов ИЛИ шестой группы, вторые входы которых подключены к выходу элементов И двенадцатой группы, а выход к информационному входу пятого регистра, выход которого подключен к вторым входам элементов И девятой группы, первый управляющий вход вычислительного модуля подключен к инверсным первым входам второго, третьего и четвертого элементов И, первым входам пятого, шестого и седьмого элементов И и информационному входу первого триггера, выход которого подключен к информационному входу второго триггера, выход которого подключен к первому управляющему выходу вычислительного модуля, второй управляющий вход которого подключен к инверсным вторым входам второго, четвертого, пятого и шестого элементов И, вторым входам третьего и седьмого элементов И и информационному входу третьего триггера, выход которого подключен к информационному входу четвертого триггера, выход которого подключен к второму управляющему выходу вычислительного модуля, третий управляющий вход которого подключен к инверсным третьим входам третьего, четвертого, шестого и седьмого элементов И, третьим входам второго и пятого элементов И и информационному входу пятого триггера, выход которого подключен к информационному входу шестого триггера, выход которого подключен к третьему управляющему выходу вычислительного модуля, выходы с второго по седьмой элементов И подключены соответственно к информационным входам триггеров с седьмого по двенадцатый, выход седьмого триггера подключен к первым входам второго и пятого элементов ИЛИ и вторым входам элементов И четвертой группы, выход восьмого триггера подключен к первому входу первого и второму входу пятого элементов ИЛИ, выход девятого триггера подключен к вторым входам элементов И третьей, шестой и десятой групп, выход десятого триггера подключен к вторым входам элементов И первой и двенадцатой групп, второму входу второго и первому входу шестого элементов ИЛИ, выход одиннадцатого триггера подключен к первым входам третьего, четвертого и седьмого элементов ИЛИ и вторым входам первого и шестого элементов ИЛИ, выход двенадцатого триггера подключен к вторым входам элементов И восьмой группы, вторым входам третьего, четвертого и седьмого элементов ИЛИ и третьему входу шестого элемента ИЛИ, синхровход вычислительного модуля подключен к синхровходам первого, второго, третьего и пятого регистров, регистров группы, с первого по двенадцатый триггеров и второму входу первого элемента И.