Главная страница  |  Описание сайта  |  Контакты
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ДВУМЕРНОГО ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ДВУМЕРНОГО ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ

УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ДВУМЕРНОГО ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ

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

1. С помощью поисковых систем

   С помощью Google:    

2. Экспресс-поиск по номеру патента


введите номер патента (7 цифр)

3. По номеру патента и году публикации

2000000 ... 2099999   (1994-1997 гг.)

2100000 ... 2199999   (1997-2003 гг.)
Номер патента: 2012048
Класс(ы) патента: G06F15/332
Номер заявки: 4941013/24
Дата подачи заявки: 03.06.1991
Дата публикации: 30.04.1994
Заявитель(и): Войсковая часть 03425
Автор(ы): Якуш В.П.; Лиходед Н.А.; Косьянчук В.В.; Соболевский П.И.
Патентообладатель(и): Якуш Виктор Павлович
Описание изобретения: Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов для вычисления двумерного дискретного преобразования Фурье.
Цель изобретения - сокращение аппаратурных затрат устройства.
На фиг. 1 приведена структурная схема устройства для вычисления двумерного дискретного преобразования Фурье; на фиг. 2 - структурная схема устройства для случая n= 3; на фиг. 3 - схема блока ввода; на фиг. 4 - схема операционного блока.
Устройство для вычисления двумерного дискретного преобразования Фурье (фиг. 1) содержит первую 11 и вторую 12 группы информационных входов, информационный вход 2, первый 3, второй 4, третий 5, четвертый 6 и пятый 7 тактовые входы, синхровход 8, блок 9 ввода, операционные блоки 10i (i= ) и выход 11.
Блок 9 ввода (фиг. 3) содержит первую 12 и вторую 13 группы информационных входов, первый 14 и второй 15 тактовые входы, первый 16 и второй 17 входы режима записи, синхровход 18, регистры 19i, 20i (i= ) группы элементов И 21i, 22i (i= ), группы элементов ИЛИ 23i, 24i (i= ), группу элементов ИЛИ 25, элементы И 26, 27 и выход 28.
Операционный блок 10 (фиг. 4) содержит первый 29 и второй 30 информационные входы, первый 31, второй 32 и третий 33 тактовые входы, синхровход 34, регистры 351, 352, 36, 37i, 38i (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= ;
Yij= Xpqωipωjq, ω = exp;
bjp= xpqωiq;
Yij= bjpωip положены следующие рекуррентные соотношения:
j= ; p= ; q= ;
b(j, p, 0)= xp, n-1;
b(j, p, q)= b(j, p, q-1) ω j+ xp, n-1-q;
bjp= b(j, p, n-1);
i= ; j= ; p= ;
y(i, j, -1)= 0;
y(i, j, n)= y(i, j, p-1) ωi+ bj, n-1-p;
yij= y(i, j, n-1).
Рассмотрим работу операционного блока 10 (фиг. 4) и блока 9 ввода (фиг. 3).
Операционный блок 10 работает в шести режимах, которые задаются комбинацией сигналов aj, bj и cj, подаваемых соответственно на входы 31, 32 и 33 на j-м такте .
Первый режим работы задается комбинацией сигналов τ1i= (aj, bj, cj)= (0, 0, 1). При этом на выходе элемента И 65 формируется управляющий сигнал μ1, а на выходе триггера 87 - управляющий сигнал α1j (по сигналу μj обеспечивается запись в регистры на j-м такте, а по сигналу αj - на (j+ 1)-м такте). Сигнал μ1 подается на вход группы элементов И 51 и на входы элементов ИЛИ 71 и 72 (открываются группы элементов И 41, 49, 51 и элемент И 63). На вход 29 подается элемент ωj и через группы элементов И 41 и ИЛИ 57 записывается в регистр 371 на j-м такте. Информация из регистра 37i (i= ) переписывается в регистр 37i+1. Управляющий сигнал α1 подается на вход элемента ИЛИ 77 (открываются группы элементов И 44, 49). Содержимое регистра 371 через группу элементов И 47 выдается на выход 96 операционного блока. Входной элемент х, подаваемый на вход 30, записывается в регистр 351. Содержимое регистра 36 через группы элементов И 51 и ИЛИ 59 записывается в регистр 381. Содержимое регистра 38i (i= ) записывается в регистр 38i+1. Содержимое регистра 352 через группы элементов И 49 и ИЛИ 58 выдается на выход 97.
Во втором режиме работы τ3j= (0, 1, 0). При этом на выходе элемента И 66 формируется управляющий сигнал μ2, а на выходе триггера 88 - управляющий сигнал α2. Сигнал μ2 подается на вход группы элементов И 46, на входы элементов ИЛИ 71, 72 и 73, а сигнал α2 - на вход элемента ИЛИ 77. Открываются группы элементов И 41, 44, 49 и элементы И 63, 64. Как и в первом режиме, аналогично элемент ω записывается в регистр 371, содержимое регистра 371 выдается на выход 96 и информация записывается в регистры 37i. Входной элемент х записывается в регистр 381, через группы элементов И 46 и ИЛИ 59, а также записывается в регистр 351. Содержимое регистра 352 выдается на выход 97. Информация из регистра 38i (i= ) записывается в регистр 38i+1.
В третьем режиме τ2j= (1, 0, 0). При этом управляющий сигнал μ3формируется на выходе элемента И 67, а управляющий сигнал α3 - на выходе триггера 89. Сигнал μ3 подается на входы элементов ИЛИ 72, 73, 74 и 75, а сигнал α3 - на входы группы элементов И 47 и элементов ИЛИ 78, 79. Открываются группы элементов И 42, 45, 47, 49, 53, 56 и элементы И 63, 64. Содержимое регистра 37n через группы элементов И 42 и ИЛИ 57 записывается в регистр 371. Содержимое регистра 37i (i= ) записывается в регистр 37i+1. Входной элемент х записывается в регистры 351 и 36 (по сигналу μ3 открыт элемент И 64 и разрешается запись в регистр 36). На выход 97 подается содержимое регистра 352. Содержимое сумматора 40 через группы элементов И 53 и ИЛИ 59 записывается в регистр 381 по сигналу μ3 . Содержимое регистра 38n <b> через группы элементов И 56 и ИЛИ 61 подается на первый вход умножителя 39, на второй вход которого содержимое регистра 37n <ω>> подается через группы элементов И 45 и ИЛИ 62. На выходе умножителя 39 формируется значение b ˙ω . На первый вход сумматора 40 подается содержимое регистра 351 < x> через группы элементов И 47 и ИЛИ 60, а на второй вход - значение b ˙ ω . На выходе сумматора 40 формируется значение b ˙ω + x по сигналу α3.
В четвертом режиме работы τ4 = (1, 0, 1). На выходе элемента И 68 формируется сигнал μ4, на выходе триггера 90 - сигнал α4. Сигнал μ4подается на выходы элементов ИЛИ 72,74 и 75, а сигнал α4 - на входы элементов ИЛИ 78, 79 и группы элементов И 52. Открываются группы элементов И 42, 45, 49, 52, 53, 56 и элемент И 63. Аналогично, как и в третьем режиме, информация в регистрах 37i (i= ) циклически переписывается. На выход 97 подается содержимое регистра 352 через группы элементов И 49 и ИЛИ 58. В регистр 351 записывается входной элемент х. В регистр 381 записывается иформация с выхода сумматора 40 через группы элементов И 53 и ИЛИ 59 по сигналу μ4 . Содержимое регистра 38i (i= ) записывается в регистр 38i+1. По сигналу α4 на выходе умножителя 39 формируется значеие b˙ω (элемент b подается с регистра 37n, а элемент ω- с регистра 38n), на выходе сумматора 40 - значение b˙ω + x (элемент х подается с регистра 36 через группы элементов И 52 и ИЛИ 60).
В пятом режиме работы τ5= (1, 1, 0). На выходе элемента И 69 формируется сигнал μ5, на выходе триггера 91 - сигнал α5. Сигнал 5 подается на входы элементов ИЛИ 71, 72 и 76, а сигнал μ5 - на входы группы элементов И 48, элементов ИЛИ 71, 76, 77, 80, 81, 82 и элемента ИЛИ-НЕ 83. Открываются группы элементов И 41, 43, 44, 48, 50, 54, 55 и элемент И 63. Входной элемент ωзаписывается в регистр 371, который выдается через группу элементов И 44 на выход 96. Содержимое регистра 38n записывается в регистр 381 через группы элементов И 54 и ИЛИ 59. Содержимое регистра 38i (i= ) записывается в регистр 38i+1. На первый вход умножителя 39 входной элементy подается с выхода регистра 351 через группы элеметов И 48 и ИЛИ 61, а на второй вход - содержимое регистра 371 <ω>>через группы элементов И 43 и ИЛИ 62. На выходе умножителя 39 формируется значение y˙ω , которое подается на вход сумматора 40, на второй вход которого подается содержимое регистра 38n<b> через группы элементов И 55 и ИЛИ 60. На выходе сумматора 40 формируется значение y ˙ω + b, которое через группы элементов И 50 и ИЛИ 58 подается на выход 97.
В шестом режиме работы τ6= (1, 1, 1). На выходе элемента И 70 формируется сигнал μ6, на выходе триггера 92 - сигнал α6. Сигнал μ6подается на входы элементов ИЛИ 76, а сигнал α6 - на входы элементов ИЛИ 81, 82, элемента ИЛИ-НЕ 83 и группы элементов И 48. Открываются группы элементов И 43, 48, 50, 54 и 55. Регистр 371 сохраняет состояние предыдущего такта, информация в регистрах 38i (i= ) циклически переписывается. На первый вход умножителя 39 подается входной элемент y с выхoда регистра 351 через группы элементов И 48 и ИЛИ 61, а на второй вход - содержимое регистра 371 <ω>> через группы элементов И 43 и ИЛИ 62. На выходе умножителя 39 формируется значение y˙ω , которое подается на вход сумматора 40, на второй вход которого подается содержимое регистра 38n <b> через группы элементов И 55 и ИЛИ 60. На выходе сумматора 40 формируется значение y ˙ω + b, которое подается через группы элементов И 50 и ИЛИ 58 на выход 97.
Блок 9 ввода работает следующим образом.
При подаче на вход 16 нулевого сигнала γгруппы элементов И 21j(j= ) закрываются, на вторые входы групп элементов ИЛИ 23j (j= ) подаются нулевые значения, на первые входы которых подаются соответствующие коэффициенты ωj, которые записываются в соответствующие регистры 19j (j= ) при наличии на входе 14 единичного сигнала (элемент И 26 открывается и тактовый импульс подается на синхровходы всех регистров 19j). При подаче на вход 16 единичного сигнала γгруппы элементов И 21j (j= ) открываются, на входы 12j подаются нулевые значения, на вход 14 подается соответствующая последовательность единичных сигналов α, на выход 28 подаются соответствующие коэффициенты ωj. Аналогично записываются и выдаются на выход 28 коэффициенты ωi.
При описании работы устройства в обозначении τij индекс i указывает номер режима работы операционного блока (i= ), а индекс j - номер такта работы устройства.
Коэффициенты ωiи ωj записываются в блок 9 ввода при подаче их соответственно на группы информационных входов 11 и 12. Коэффициенты ωjвыдаются с блока 9 ввода на первый информационный вход операционного блока 101 при наличии сигнала α = 1 в момент времени
tωi= i+n-1, а коэффициенты ωi выдаются при наличии сигнала β = 1 в моменты времени
tωi= (i+n+1)n-1.
На входы 3, 4 и 5 подаются соответственно сигналы a, b и с, которые задают шесть режимов работы τi= (a, b, c):
τ1= (0, 0, 1); τ2 = (0, 1, 0) τ3= (1, 0, 0); τ4= (1, 0, 1); τ5= (1, 1, 0); τ6= (1, 1, 1).
Управляющие сигналы подаются в следующей последовательности:

, . . . ,
,
,
,
,
.
Элементы выходной матрицы y[n, n] выдаются на выход 11 в момент времени
tyij= in+j+(n+2)n-2.
Организация входного и выходного потоков данных устройства для n= 3 приведены на фиг. 2, а состояния регистров, значения на входах и выходах операционных блоков 101, 102 и 103 приведены в табл. 1-3. В них приводятся формируемые значения b(j, p, q) и y(i, j, n-1) в соответствии с рекуррентными соотношениями вычисления двумерного дискретного преобразования Фурье.
Первый элемент yoo выдается на выход на (n2+2n-2)-м такте, а последний элемент yn-1, n-1 - на (2n2+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-й регистры первого узла регистров, всех регистров второго узла регистров и всех триггеров.