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

 

Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов для вычисления двумерного дискретного преобразования Фурье. Цель изобретения - сокращение аппаратурных затрат. Цель достигается тем, что устройство содержит n операционных блоков, где n - размерность входной матрицы x [ n, n] , и блок ввода, причем операционный блок содержит 2n + 3 регистров, умножитель, сумматор, девять триггеров, пятнадцать групп элементов И, шесть групп элементов ИЛИ, восемь элементов И, двенадцать элементов ИЛИ, элемент ИЛИ - НЕ и три элемента НЕ. 3 табл. , 4 ил.

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

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

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

Устройство для вычисления двумерного дискретного преобразования Фурье (фиг. 1) содержит первую 1₁ и вторую 1₂ группы информационных входов, информационный вход 2, первый 3, второй 4, третий 5, четвертый 6 и пятый 7 тактовые входы, синхровход 8, блок 9 ввода, операционные блоки 10_i (i= ) и выход 11.

Блок 9 ввода (фиг. 3) содержит первую 12 и вторую 13 группы информационных входов, первый 14 и второй 15 тактовые входы, первый 16 и второй 17 входы режима записи, синхровход 18, регистры 19_i, 20_i (i= ) группы элементов И 21_i, 22_i (i= ), группы элементов ИЛИ 23_i, 24_i (i= ), группу элементов ИЛИ 25, элементы И 26, 27 и выход 28.

Операционный блок 10 (фиг. 4) содержит первый 29 и второй 30 информационные входы, первый 31, второй 32 и третий 33 тактовые входы, синхровход 34, регистры 35₁, 35₂, 36, 37_i, 38_i (i= ), умножитель 39, сумматор 40, группы элементов И 41-56, группы элементов ИЛИ 57-62, элементы И 63-70, элементы ИЛИ 71-82, элемент ИЛИ-НЕ 83, элементы НЕ 84-86, триггеры 87-95, первый 96 и второй 97 информационные выходы, первый 98, второй 99 и третий 100 тактовые выходы.

В основу работы устройства для вычисления двумерного дискретного преобразования Фурье по формулам i= ; j= ; p= ; q= ; Y_ij= X_pqω^ipω^jq, ω = exp; b_jp= x_pqω^iq; Y_ij= b_jpω^ip положены следующие рекуррентные соотношения: j= ; p= ; q= ; b(j, p, 0)= x_{p, n-1}; b(j, p, q)= b(j, p, q-1) ω ^j+ x_{p, n-1-q}; b_jp= b(j, p, n-1); i= ; j= ; p= ;
y(i, j, -1)= 0;
y(i, j, n)= y(i, j, p-1) ωⁱ+ b_{j, n-1-p};
y_ij= y(i, j, n-1).

Рассмотрим работу операционного блока 10 (фиг. 4) и блока 9 ввода (фиг. 3).

Операционный блок 10 работает в шести режимах, которые задаются комбинацией сигналов a^j, b^j и c^j, подаваемых соответственно на входы 31, 32 и 33 на j-м такте .

Первый режим работы задается комбинацией сигналов τ₁ⁱ= (a^j, b^j, c^j)= (0, 0, 1). При этом на выходе элемента И 65 формируется управляющий сигнал μ₁, а на выходе триггера 87 - управляющий сигнал α₁^j (по сигналу μ^j обеспечивается запись в регистры на j-м такте, а по сигналу α^j - на (j+ 1)-м такте). Сигнал μ₁ подается на вход группы элементов И 51 и на входы элементов ИЛИ 71 и 72 (открываются группы элементов И 41, 49, 51 и элемент И 63). На вход 29 подается элемент ω^j и через группы элементов И 41 и ИЛИ 57 записывается в регистр 37₁ на j-м такте. Информация из регистра 37_i (i= ) переписывается в регистр 37_i+1. Управляющий сигнал α₁ подается на вход элемента ИЛИ 77 (открываются группы элементов И 44, 49). Содержимое регистра 37₁ через группу элементов И 47 выдается на выход 96 операционного блока. Входной элемент х, подаваемый на вход 30, записывается в регистр 35₁. Содержимое регистра 36 через группы элементов И 51 и ИЛИ 59 записывается в регистр 38₁. Содержимое регистра 38_i (i= ) записывается в регистр 38_i+1. Содержимое регистра 35₂ через группы элементов И 49 и ИЛИ 58 выдается на выход 97.

Во втором режиме работы τ₃^j= (0, 1, 0). При этом на выходе элемента И 66 формируется управляющий сигнал μ₂, а на выходе триггера 88 - управляющий сигнал α₂. Сигнал μ₂ подается на вход группы элементов И 46, на входы элементов ИЛИ 71, 72 и 73, а сигнал α₂ - на вход элемента ИЛИ 77. Открываются группы элементов И 41, 44, 49 и элементы И 63, 64. Как и в первом режиме, аналогично элемент ω записывается в регистр 37₁, содержимое регистра 37₁ выдается на выход 96 и информация записывается в регистры 37_i. Входной элемент х записывается в регистр 38₁, через группы элементов И 46 и ИЛИ 59, а также записывается в регистр 35₁. Содержимое регистра 35₂ выдается на выход 97. Информация из регистра 38_i (i= ) записывается в регистр 38_i+1.

В третьем режиме τ₂^j= (1, 0, 0). При этом управляющий сигнал μ₃формируется на выходе элемента И 67, а управляющий сигнал α₃ - на выходе триггера 89. Сигнал μ₃ подается на входы элементов ИЛИ 72, 73, 74 и 75, а сигнал α₃ - на входы группы элементов И 47 и элементов ИЛИ 78, 79. Открываются группы элементов И 42, 45, 47, 49, 53, 56 и элементы И 63, 64. Содержимое регистра 37_n через группы элементов И 42 и ИЛИ 57 записывается в регистр 37₁. Содержимое регистра 37_i (i= ) записывается в регистр 37_i+1. Входной элемент х записывается в регистры 35₁ и 36 (по сигналу μ₃ открыт элемент И 64 и разрешается запись в регистр 36). На выход 97 подается содержимое регистра 35₂. Содержимое сумматора 40 через группы элементов И 53 и ИЛИ 59 записывается в регистр 38₁ по сигналу μ₃ . Содержимое регистра 38_n <b> через группы элементов И 56 и ИЛИ 61 подается на первый вход умножителя 39, на второй вход которого содержимое регистра 37_n <ω> подается через группы элементов И 45 и ИЛИ 62. На выходе умножителя 39 формируется значение b ˙ω . На первый вход сумматора 40 подается содержимое регистра 35₁ < x> через группы элементов И 47 и ИЛИ 60, а на второй вход - значение b ˙ ω . На выходе сумматора 40 формируется значение b ˙ω + x по сигналу α₃.

В четвертом режиме работы τ₄ = (1, 0, 1). На выходе элемента И 68 формируется сигнал μ₄, на выходе триггера 90 - сигнал α₄. Сигнал μ₄подается на выходы элементов ИЛИ 72,74 и 75, а сигнал α₄ - на входы элементов ИЛИ 78, 79 и группы элементов И 52. Открываются группы элементов И 42, 45, 49, 52, 53, 56 и элемент И 63. Аналогично, как и в третьем режиме, информация в регистрах 37_i (i= ) циклически переписывается. На выход 97 подается содержимое регистра 35₂ через группы элементов И 49 и ИЛИ 58. В регистр 35₁ записывается входной элемент х. В регистр 38₁ записывается иформация с выхода сумматора 40 через группы элементов И 53 и ИЛИ 59 по сигналу μ₄ . Содержимое регистра 38_i (i= ) записывается в регистр 38_i+1. По сигналу α₄ на выходе умножителя 39 формируется значеие b˙ω (элемент b подается с регистра 37_n, а элемент ω- с регистра 38_n), на выходе сумматора 40 - значение b˙ω + x (элемент х подается с регистра 36 через группы элементов И 52 и ИЛИ 60).

В пятом режиме работы τ₅= (1, 1, 0). На выходе элемента И 69 формируется сигнал μ₅, на выходе триггера 91 - сигнал α₅. Сигнал 5 подается на входы элементов ИЛИ 71, 72 и 76, а сигнал μ₅ - на входы группы элементов И 48, элементов ИЛИ 71, 76, 77, 80, 81, 82 и элемента ИЛИ-НЕ 83. Открываются группы элементов И 41, 43, 44, 48, 50, 54, 55 и элемент И 63. Входной элемент ωзаписывается в регистр 37₁, который выдается через группу элементов И 44 на выход 96. Содержимое регистра 38_n записывается в регистр 38₁ через группы элементов И 54 и ИЛИ 59. Содержимое регистра 38_i (i= ) записывается в регистр 38_i+1. На первый вход умножителя 39 входной элементy подается с выхода регистра 35₁ через группы элеметов И 48 и ИЛИ 61, а на второй вход - содержимое регистра 37₁ <ω>через группы элементов И 43 и ИЛИ 62. На выходе умножителя 39 формируется значение y˙ω , которое подается на вход сумматора 40, на второй вход которого подается содержимое регистра 38_n<b> через группы элементов И 55 и ИЛИ 60. На выходе сумматора 40 формируется значение y ˙ω + b, которое через группы элементов И 50 и ИЛИ 58 подается на выход 97.

В шестом режиме работы τ₆= (1, 1, 1). На выходе элемента И 70 формируется сигнал μ₆, на выходе триггера 92 - сигнал α₆. Сигнал μ₆подается на входы элементов ИЛИ 76, а сигнал α₆ - на входы элементов ИЛИ 81, 82, элемента ИЛИ-НЕ 83 и группы элементов И 48. Открываются группы элементов И 43, 48, 50, 54 и 55. Регистр 37₁ сохраняет состояние предыдущего такта, информация в регистрах 38_i (i= ) циклически переписывается. На первый вход умножителя 39 подается входной элемент y с выхoда регистра 35₁ через группы элементов И 48 и ИЛИ 61, а на второй вход - содержимое регистра 37₁ <ω> через группы элементов И 43 и ИЛИ 62. На выходе умножителя 39 формируется значение y˙ω , которое подается на вход сумматора 40, на второй вход которого подается содержимое регистра 38_n <b> через группы элементов И 55 и ИЛИ 60. На выходе сумматора 40 формируется значение y ˙ω + b, которое подается через группы элементов И 50 и ИЛИ 58 на выход 97.

Блок 9 ввода работает следующим образом.

При подаче на вход 16 нулевого сигнала γгруппы элементов И 21_j(j= ) закрываются, на вторые входы групп элементов ИЛИ 23_j (j= ) подаются нулевые значения, на первые входы которых подаются соответствующие коэффициенты ω^j, которые записываются в соответствующие регистры 19_j (j= ) при наличии на входе 14 единичного сигнала (элемент И 26 открывается и тактовый импульс подается на синхровходы всех регистров 19_j). При подаче на вход 16 единичного сигнала γгруппы элементов И 21_j (j= ) открываются, на входы 12_j подаются нулевые значения, на вход 14 подается соответствующая последовательность единичных сигналов α, на выход 28 подаются соответствующие коэффициенты ω^j. Аналогично записываются и выдаются на выход 28 коэффициенты ωⁱ.

При описании работы устройства в обозначении τ_i^j индекс i указывает номер режима работы операционного блока (i= ), а индекс j - номер такта работы устройства.

Коэффициенты ωⁱи ω^j записываются в блок 9 ввода при подаче их соответственно на группы информационных входов 1₁ и 1₂. Коэффициенты ω^jвыдаются с блока 9 ввода на первый информационный вход операционного блока 10₁ при наличии сигнала α = 1 в момент времени
t_ωi= i+n-1, а коэффициенты ωⁱ выдаются при наличии сигнала β = 1 в моменты времени
t_ωi= (i+n+1)n-1.

На входы 3, 4 и 5 подаются соответственно сигналы a, b и с, которые задают шесть режимов работы τ_i= (a, b, c):
τ₁= (0, 0, 1); τ₂ = (0, 1, 0) τ₃= (1, 0, 0); τ₄= (1, 0, 1); τ₅= (1, 1, 0); τ₆= (1, 1, 1).

Управляющие сигналы подаются в следующей последовательности:

, . . . ,
,
,
,
,
.

Элементы выходной матрицы y[n, n] выдаются на выход 11 в момент времени
t_yij= in+j+(n+2)n-2.

Организация входного и выходного потоков данных устройства для n= 3 приведены на фиг. 2, а состояния регистров, значения на входах и выходах операционных блоков 10₁, 10₂ и 10₃ приведены в табл. 1-3. В них приводятся формируемые значения b(j, p, q) и y(i, j, n-1) в соответствии с рекуррентными соотношениями вычисления двумерного дискретного преобразования Фурье.

Первый элемент y_oo выдается на выход на (n²+2n-2)-м такте, а последний элемент y_{n-1, n-1} - на (2n²+3n-2)-м такте.

Таким образом, предлагаемое устройство по сравнению с прототипом содержит меньший объем оборудования (прототип содержит 2n операционных блоков и n групп вхoдов для ввода элементов матрицы x [n, n] , а предлагаемое устройство - n операционных блоков и одну группу входов для ввода элементов матрицы x[n, n] , что существенно при реализации на основе сверхбольших интегральных схемах).

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

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

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4