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

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано для обработки цифровых сигналов , четных и не ётн ь1хН6 ёдЬватёльн6стёй, в системах обработки изображений, для цифровой фильтрации, сжатия информации, для спектрального и корреляционного анализа случайных процессов, в системах связи и т.д. Целью изобретения является рас шире

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (я)5 G 06 F 15/332

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

1 (21) 4806594/24 (22) 20.02.90 (46) 23.01.93. Бюл. N. 3 (71) Институт кибернетики им, ВМ. Глушкова (72) Л.А. Гнатив, В,Е. Коссов, M.À, Гнатив и

Г.Я. Ширмовский (56) Авторское свидетельство СССР

N 620974, кл. G 06 F 5/00, 1978, Авторское свидетельство СССР

М 744555, кл. G 06 F 7/38, 1980.

„,5U„„1789990 А1 (54) УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ УОЛША HA

СКОЛЬЗЯЩЕМ ИНТЕРВАЛЕ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано для обработки цифровых сигналов, четных и йечетйых йоследовательностей, в системах обработки иэображений, для цифровой фильтрации, сжатия информации, для спектрального и корреляционного анализэ случайных процессов, в системах связи и т.д. Целью изобретения является расшире1

OO

1 4 )

О

i K С) 1789990

Изобретение относится к области автоматики и вычислительной техники и может быть использовано для обработки цифровых сигналов, четных и нечетных последовательностей, в сйстемах обработки изображений, для цифровой фильтрации, сжатия информации, для спектрального и корреляционного анализа случайных про-- цессов, в системах связи и т.д.Цель изобретения — расширение функ" циойальных возможностей за счет вычисления i<îçôôèöèåèòîa преобразовайия Уолша с-упорядочением"по частотам следовайия;: .

Для обработки четных и нечетных последовательностей и выделения четных и нечетййх сигналов предлагается использовать новОе четно-нечетное прообразовайие

Уолша. по коэффициентам которого определяют четные и нечетные последовательности, Матрица четно-нечетного преобразования Уолша Wz" в верхней половине йредставляет четные Cal(k,j) функции Уолша, а в нижней половине — нечетные Sal(k, функции, расположенные в порядке увеличения частот следования.

Матрица Щ"() для п=3 имеет вид:

11111111 Cal (О, j)

1 1---- 1 1 Cal (1, j)

1--11--1 Cal (2, j)

< tcs) = 1-1--1-1 . Cal: (3, j) в

1 1 1 1---- Sal (1, j)

11--11-- Sal (2, J)

1--1-11- Sal (3, j)

1-1-1-1- Sal. (4, j) 10

20

30

40 тельном модуле выполняет задержку в четы45 ние его функциональных возможностей за счет вычисления коэффициентов преобразования Уолша с упорядочением по частотам следования. Поставленная цель достигается тем, что устройство содержит вычислительные модули 1-I<. регистры

Р," :,г, г =. =

Постэвлеййая цель достигается тем, что устройство содержит переключатель и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого подключен к первому информационному входу переключателя, выход которого подключен к второму тактовому входу n -го вычислительного модуля, второй информационный вход переключателя соединен с первым входом элемента ИСКЛЮ2 (J=1, n), сумматоры-вычитатели 3, коммутаторы 4, 5, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ

6 и переключатель 7, Устройство реализует новый алгоритм быстрого четно-нечетного преобразования Уолша, 7 ил.

ЧАЮЩЕЕ ИЛИ и подключен к и-му тактовому входу первой группы устройства, к (n-1)му тактовому входу первой группы которого подключен второй вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, управляющий вход переключателя является входом задания режима устройства, а в и-м вычислительном модуле управляющие входы первого и второго коммутаторов подключены к второму тактовому входу вычислительного модуля, первым и вторым выходами которого являются выходы соответственно первого и второго коммутаторов.

На фиг. 1 представлен граф быстрого четно-нечетного преобразования Уолша для

N (N=2")= 3; на фиг, 2 — граф быстрого четнонечетного преобразования Уолша на скользящем интервале для N=4; на фиг. 3 — граф быстрого преобразования Уолша с упорядочением по частотам следования для N=8; на фиг, 4 — граф быстрого преобразования Уолша с упорядочением по частотам следования на скользящем интервале для N=4; на фиг. 5 — функциональная схема устройства; на фиг. 6 — схема переключателя и на фиг. 7 — временная диаграмма работы устройства для N--16.

Устройство (фиг. 5) содержит и вычислительных модулей 1> — 1л, регистры 2 (J=1, n), сумматоры-вычитатели 3, коммутаторы 4, 5, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 6 и переключатель 7, информационный вход 8, вход режима 9, информационные выходы 10, 11, Переключатель (фиг, 6) содержит два элемента И 12, 13 и элемент НЕ 14

Регистр 21 в первом вычислительном мОдуле выполняет задержку на один такт, а регистр в каждом последующем вычислире раза больше, чем в предыдущем модуле.

В 1-м вычислительном модуле регистр 2 является 4 -разрядным.

Тактовая частота регистра 21 равна частоте fT следования отсчетов входного сигнала и для каждого последующего регистра увеличивается в два раза. Это позволяет получать коэффициенты преобразования в

1789990 реальном масштабе времени и на скользящем интервале, Последовательности длиной N, определенные на скользящем интервале, состоят из текущих значений отсчетов входного сиг- 5 нала с 0-го по (N-1)-й, с 1-ro no N-й, с 2-го по (N+1)-й отсчеты и т.д.

Выбор режима работы устройства осуществляется сигналом. который подается на вход 9 управления режимом работы. При 10 подаче сигнала на вход 9 переключателя 7, равного логической "1", устройство работает в режиме преобразования Уолша с упорядочением по частотам следования, а при подаче сигнала"логического "0" — в режиме 15 четно-нечетного преобразования Уолша, Все вычислительные модули, кроме п-го модуля, работают независимо от режима работы устройства, Устройство работает следующим обра- 20 зом.

Входная последовательность (х(1) — x(N)), представляющая собой текущие значения отсчетов дискретного сигнала, с частотой f, (фиг. 7) тактовых импульсов поступает на 25 второй вход сумматора-вычитателя 31, который срабатйвает в каждом такте, и нэ информационный вход регистра 21 в первом вычислительном модуле, где задерживается на один такт (в регистре хранится один от- 30 счет сигнала). На выход коммутатора 41 в течение каждого такта выводится сумма, а затем разность, сформированные на выходах сумматора-вычитателя 31, начиная с вто. рого такта {в первом такте формируются и 35 выводятся сумма и разность первых двух отсчетов из предйдущей входной последовательноСти). Регистр 21 и коммутатор 41 управляются тактовым сигналом "1" (фиг. 7) с первого тактового входа первого вычисли- 40 тельного модуля.

Данные с выхода коммутатора 41 поступают с тактовой частотой 2 fT на второй вход сумматора-вычитателя 3z и на информационный вход регистра 2z, который управляет- 45 ся тактовым сигналом "2" (фиг. 7) с первого тактового входа второго вычислительного модуля. В регистре 22 данные задерживаются на четыре такта. В течение каждого такта работы регистра 2 в нечетных тактах на вы- 50 ход коммутатора 4z, который управляется тактовым сигналом "3" (фиг, 7) с второго тактового входа второго вычислительного модуля, выводятся результаты: сумма, затем — Разность, а в четных тактах —. разность, 55 затем сумма, сформированные на выходах сумматора-вычитателя 32 во втором вычислительном модуле: хЩ+хЦ+4), xi-x(j-4), j=1, 3, 5,...

x(j)-хО+4), x(j)+x(J44), )=2, 4, 6.. „ начиная с пятого такта. В течение первых четырех тактов формируются и выводятся результаты: сумма и разность (разность и сумма) двух пар отсчетов, состоящих из первых четырех отсчетов из предыдущей входной последовательности.

В k-м (1=3, и-1) вычислительном модуле данные с выхода (k-1)-го вычислительного модуля поступают на второй вход сумматора-вычитателя 3i и на информационный вход регистра 2к с тактовой частотой 2" f .

В регистре 2k, который управляется тактовым сигналом с первого тактового входа k-ro вычислительного модуля. данные задерживаются на 4 тактов. На выход коммутатора

k-1

4, управляемого сигналом с второго тактового входа k-го вычислительного модуля, в течение каждого такта работы регистра 2 в нечетных тактах выводятся результаты: сумма, затем — разность, а в четных тактах— разность, затем сумма, сформированнйе в соответствии с графами преобразования (фиг. 1 и 2) на выходах сумматора-вычитателя 3 в k-м модуле:

x (j)+x(j+4 ), x(j)-x(j+4 ), J=1, 3, 5,... хЩ-х(+4" 1), x(j)+ (j+4 1), J=2. 4, 6,...

k-1 начиная с (4 +1)-ro такта. В течение первых

k-1

4 тактов на выход коммутатора 41, выводятся результаты; полученйые из предыдущей входной последовательности.

В и-м вычислительном модуле данные с выхода (и-1)-го вычислительного модуля поступают на второй вход сумматора-аычитателя 3 и на информационный вход регистра 2п с тактовой частотой 2" fT, где задерживаются и-1 на 4 тактов, На выходах сумматора-вычитателя 3 в каждом такте работы регистра 2л, управляемого тактовым сигналом "6" (фиг. 7) с первого тактового входа вычислительного модуля, формируются результатысумма и разность, которые в зависимости от режима работы устройства выводятся на выходы первого и второго коммутаторов 4> и 5.

В режиме преобразования Уолшэ с упорядочением по частотам следовайия на выход 10 первого коммутатора 4>, который управляется сигналом "6" с первого тактового входа вычислительного модуля, с частотой 2"fT в течение каждого нечетного такта выводятся результаты сумма и рэзМость, а в течение каждого четного такта — разность и сумма, сформированные в соответствии с графами преобразования (фиг. 3 и 4} на вы-; ходах сумматора-вычитателя 3 .

x(J)+x(j+4" ) J-1, 3, 5,...,— 1 х1"О) = мО -x0+4" ).

1789990

20 х®-x(j+4" ), J=2, 4, 6,..., —, x1"o) =1 (J)+>«(J++44" "). начиная с(4" +1)-го такта. В течение первых 5

4" тактов формируются и выводятся на выход коммутатора 4п коэффициенты преобразования от предыдущей последовательности, Таким образом, текущие значения N ко- 10 эффициентов преобразования Уолша с упорядочением по "частотам следований от первой последовательности (х(1) — x(N)) получаются на выходах сумматора-вйчитателя

3, в и-м вычислительном модуле по приходу 15

N-го отсчетавходного сигйала и выводятся на выход коммутатора 4> с частотой в N раз больше тактовой частоты отсчетов входного сигнала. По приходу следующего (N+1)-ro текущего отсчета входного сигнала на выход коммутатора 4> выводятся новые текущие значения следующих N коэффициентов преобразования от второй последовательности (х(2) — x(N+1)) и т,д.

В режиме четно-нечетного преобразо- 25 вания Уолша коммутаторы 4л и 5управляются сигналом "7" (фиг, 7) с второго тактового входа вычислительного модуля. При этом в нечетные такты на выход,10 первого коммутатора 4> с частотой 2" fT выводятся суммы, 30 представляющйе собой коэффициенты x< (J) преобразования по четным Cal функциям

Уолша с нечетными номерами от первой последовательности {х(1)-x(N)), а в четные такты выводятся разности, которые 35 представляют собой коэффициенты х1 (О преобразования по нечетным Saj функциям

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

Устройство gnÿ выполнения быстрого преобразования.Уолша на скользящем интервале, содержащее и (2" — размер преобразования) вйчислительных модулей, причем выход 1-го(1=1, и-1) вычиСлйтельного модуля подключен к информационному входу i+1-ro вычислительного модуля, информациойййй вход йервого вычислительного модуля является информациойным входом устройства, первым и вторым информационными выходами-которого являются соответственно первый и второй выходы n-ro вычислительного модуля, первый тактовый вход 1-ro (J-1, и) вычислительного модуля является J-м тактовым входом первой группы устройСтва, второй тактовый вход m-го (m=2, и-1) вычислительного модуля является

m-1-м тактовым входом второй группы устс четными номерами, сформированные на выходах сумматора-вычитателя 3n, х1 (})=хО)+хО+4" ), )= 1, 3, 5„.„— -1

x) (J)=x®-x(J+4" ), J= 2, 4, 6,...,—

Одновременно с этим на выход 11 второго коммутатора 5 в нечетные такты выводятся разности, представляющие собой коэффициенты х О) преобразования по нечетным функциям с нечетными номерами, а в четные такты — суммы, которые представляют собой коэффициенты x> (J) преобразования по нечетным функциям с четными номерами, сформированные на выходах сумматора-,вычитателя Зп. х1 (J)=x(J)-õ (J+4" ), J=1, 3, 5„.„— -1 х1 (J)=x(J)+x (J+4" ), )=2, 4, 6,.„,—

Таким образом, текущие значения

2 коэффициентов х1 О) преобразования по четным функциям Уолша выводятся на выход первого коммутатора 4>, а текущие значения

N — коэффициентов x> O) преобразования по

2 нечетным функциям выводятся на выход втоМ рого коммутатора 5 с частотой — f до при2 хода (N+1)-ro текущего отсчета входного сигнала, По приходу следующего (N+1)-ro отсчета входного сигнала на выходы коммутаторов

4П и 5 выводятся новые текущие значения коэффициентов преобразования от следующей последовательности (х(2) — x(N+1)) и т,д. ройства, причем J-й вычислительный модуль содержит регистр, сумматор-вычитатель и коммутатор, а и-й вычислительный модуль содержит два коммутатора, причем в)-м вычислительном модуле выход регистра подключен к первому входу сумматора-вычитателя, выходы суммы и разности которого подключены соответственно к первому и второму информационным входам коммутатора, а в и-м вычиСлительном модуле -- первого и второго коммутаторов, второй вход сумматора-вычитателя соединен с информационным входом регистра и является информационным входом вычислительного модуля, первым тактовым входом которого является тактовый вход регистра, а m-м вычислительном модуле управляющий вход коммутатора подключен к второму тактовому входу вычислительного модуля, а в первом вычисли1789990

xf

Х(3

Саожеииг

Юычилюжю тельном модуле управляющий вход коммутатора подключен к первому тактовому входу вычислительного модуля, в i-м вычислительном модуле выход коммутатора является выходом вычислительного модуля, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства и расширения функциональных возможностей за счет вычисления коэффициентов преобразования Уолша с упорядочением по частотам следования, оно содержит переключатель и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого подключен к первому информационному входу переключателя, выход которого подключен к второму тактОвому входу и-го вычислиx(5 ху Ъ уф

Л(б)

Ь х( х(® тельного модуля, второй информационный вход переключателя соединен с первым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и подключен к и-му тактовому входч первой группы устройства, к и-1-му тактовому входу первой группы которого подключен второй вход элемента ИСКЛЮЧАЮ!ЦЕЕ ИЛИ управляющий вход переключателя является входом задания режима устройства, а в и-м вычислительном модуле управляющие входы первого и второго коммутаторов подключены к второму тактовому входу вычислительного модуля, первым и вторым входами которого являются выходы соответственно первого и второго коммутаторов.

X)(I)

С >(z) >

x,(s) <

0э, Х (Ф)

0 ъЮ

Х (1)4 х, (г) 1.

5 хф) >< х, (() 1789990

Х(5

Е ь ъ х(6) 1789990 % Ъ r (1) Ь

Х (2) ь

1 @44 х (м 4

Хт 4) (z), <

Х, (5) ы(„

1789990

Составитель А.Баранов

Техред М,Моргентал Корректор С,Юско

Редактор Л,Пигина

Производственно-издательский комбинат "Патент", r. ужгород, ул,Гагарина, 101. Заказ 350 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5