Устройство для выполнения быстрого преобразования Уолша на скользящем интервале Советский патент 1993 года по МПК G06F15/332 

W

е

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

vj 00

ю ю

8

ние его функциональных возможностей за счет вычисления коэффициентов преобразования УоЛша С упорядочением по частотам следования. Поставленная цель достигается тем, что устройство содержит вычислительные модули l-ln. регистры

. ,

;мЗТГ И«:: -.-;Изобретение относится к области автоматики и вычислительной техники и может быть использовано для обработки цифровых сигналов , четных и нечетных последовательностей, в системах обработки изображений, для цифровой фильтраций, сжатия информации, для спектрального и корреляционного анализа случайных про- , в системах связи и т.д;

Цель изобретения - расширение функ- цйо нальйыЦ возможностей за счет вычисле- ния;крэффициеитов преобразования Урлша с упорядочением по частотам следования.

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

Матрица Л/2П для имеет вид:

1111111 1 1----1 1 1--1 1--1 w (cs) 1-1--1-1 81111---- 1 1--1 1-- 1--1-1 1- 1 -1 -1 -1 Поставленная цель достигается тем, что устройство содержит переключатель и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого подключён к первому информационному входу переключателя, выход которого подключен к второму тактовому входу п-го вычислительного модуля, второй информационный вход переключателя соединен с первым входом элемента ИСКЛЮ2j ( п), сумматоры-вычитатели 3j, коммутаторы, 5, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 6 и переключатель 7. Устройство реализует новый алгоритм быстрого четно-нечетного преобразования Уолша. 7 ил.

5

0

5 0

5

0

5

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

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

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

Переключатель (фиг. б) содержит два элемента И 12,13 и элемент НЕ 14.

Регистр 2i в первом вычислительном модуле выполняет задержку на один такт, а регистр в каждом последующем вычислительном модуле выполняет задержку в четыре раза больше, чем в предыдущем модуле. В 1-м вычислительном модуле регистр 2i является 4и-разрядным.

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

реальном масштабе времени и на скользящем интервале.

Последовательности длиной N, определенные на скользящем интервале, состоят из текущих значений отсчетов входного сигнала с 0-го по (Ы-1}-й, с 1-го по N-й, с 2-го по (М+1)-и отсчеты и т.д.

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

Устройство работает следующим образом. .. . ... .. .

Входная последовательность { x(1)-x(N)}, представляющая собой текущие значения отсчетов дискретного сигнала, с частотой fT (фиг. 7) тактовых импульсов поступает на второй вход сумматора-вычитателя Зь который срабатывает в каждом такте, и на информационный вход регистра 2i в первом вычислительном модуле, где задерживается на один такт (в регистре хранится один отсчет сигнала). На выход коммутатора 4ч в течение каждого такта выводится сумма, а затем разность, сформированные на выходах сумматора-вычитателя 3i,.начиная с второго такта (в первом такте формируются и выводятся сумма и разность первых двух отсчетов из предыдущей входной последо- эательностй). Регистр 2i и коммутатор 4i управляются тактовым сигналом 1 (фиг. 7} с первого тактового входа первого вычислительного модуля.

Данные с выхода коммутатора 4i поступают с тактовой частотой 2 fT на второй вход сумматора-вычитателя За и на информационный вход регистра 22, который управляется тактовым сигналом 2 (фиг. 7) с первого тактового входа второго вычислительного модуля. В регистре 1г данные задерживаются на четыре такта. В течение каждого такта работы регистра 2 в нечетных тактах на выход коммутатора 4а, который управляется тактовым сигналом 3 (фиг. 7) с,второго тактового входа второго вычислительного модуля, выводятся результаты: сумма, затем - разность, а в четных тактах - разность, затем сумма, сформированные на выходах сумматора-вычитателя 32 во втором вычислительном модуле:

{x(j)+xU+4), x(j}-x(M), , 3, 5,... xGMJ+4)(xGMi+4),,4,6...,

начиная с пятого такта. В течение первых четырех тактов формируются и выводятся результаты: сумма и разность (разность и сумма) двух пар отсчетов, состоящих из пер5 вых четырех отсчетов из предыдущей входной последовательности.

В k-м (, n-i) вычислительном модуле данные с выхода (k-1)-ro вычислительного модуля поступают на второй вход суммато0 ра-вычитателя 3k и на информационный вход регистра 2k с тактовой частотой tV. В регистре 2k, который управляется тактовым сигналом с первого тактового входа k-ro вычислительного модуля, данные задержи5 ваются тактов. На выход коммутатора 4k, управляемого сигналом с второго тактового входа k-ro вычислительного модуля, в течение каждого такта работы регистра 2k в нечетных тактах выводятся результаты: сум0 ма, затем - разность, а в четных тактах - . разность затем сумма, сформированные в соответствии с графами преобразования (фиг. 1 и 2) на выходах сумматора-вычитателя 3k в k-м модуле:

fxffl+xG+f-1). xG)-xG+4k- . 3. 5,... lxG)-xG+4k 1), xG)+xG+4k-1), . 4, 6,...

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

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

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

0 управляемого тактовым сигналом 6й (фиг. 7) с первого тактового входа вычислительного модуля, формируются результаты: сумма и разность, которые в зависимости от режима работы устройства выводятся на выходы

5 первого и второго коммутаторов 4П и 5.

В режиме преобразования Уолша с упорядочением по частотам следования на выход 10 первого коммутатора 4П, который управляется сигналом 6 с первого тактово0 го входа вычислительного модуля, с частотой 2nfr в течение каждого нечётного такта выводятся результаты сумма и разность, а в течение каждого четного такта - разность и сумма, сформированные в соответствии с

5 графами преобразования (фиг, 3 и 4) на вы-. ходах сумматора-вычитателя Зп:

,п-1

N

хОМ-И 1) .3,5....,7|H

x,wG) П-1ч

xG)-xG+4n-1)/

дП-1

N

X1WG){

xG)-xG+4n-1). J-2,4,6,...-,y

«n-1

xG)+xG+4n-1).

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

Таким образом; текущие значения N ко- эффициентов преобразования Уолша с упорядочением по ч а сТйта м следований от первой последовательности (х(1)-х(М)} получаются йа в ыхо дах суйматора-вычйтатёля Зп в ri-M вычислительном модуле по приходу N-го dtc4eTa i ouHoV6 сигнала и выводятся на выход коммутатора 4П с частотой в N раз больше тактовой частоты отсчетов входного сигнала. По приходу следующего (N+1)-ro текущего отсчета входного сигнала на выход коммутатора 4П выводятся новые текущие значения следующих N коэффициентов преобразования от второй последовательности {х(2)-х(М+1)}ит.д; ;

В режиме четно-нечетного преобразо- вания Уолша коммутаторы 4П и 5управляются сигналом 7 (фиг. 7) с второго тактового входа вычислительногохм6дуля. При этом в нечетные такты на выход. 10 первого коммутатора 4П с частотой fr выводятся суммы, представляющие собой коэффициенты xi°(j) преобразования по четным Cal функциям Уолша с нечетными номерами от первой последовательности {х(1)-х(М)}, а в четные такты выводятся разности, которые представляют собой коэффициенты xis(j) преобразования по нечетным Sal функциям

Формула изобретения Устройство для выполнения быстрого преобразования УолшаГна скользящем интервале, содержащее п (2П - размер преобразования) вычислительных модулей, причем выход 1-го(, п-1) вычислительного модуля подключен к информационному входу 1+1 -гр вычислительного модуля, информационныйвхбд ггервбго вычислительного модуля является инфор йЩйойным вхбдЪм устройства, первым и вторым информационными BHxcflaWii являются соответственно первый и второй выходы п-го вычислительного модуля, первый тактовый вход J-ro . п) вычислительнЬгб модуля является J-M тактовым входом первой группы устройства, второй тактовый вход m-ro (, г - вычислительного модуля является rn-1-м тактовым входом второй группы уст

с четными номерами, сформированные на выходах сумматора-вычитателя 3Q:

5 1015 20

N

xic(lH GMJ+4n-1), 1, 3, 5,..., -у-1

in h i

2

N

xicG)xG)-xG+4n-1), J 2, 4, 6,..., у

Одновременно с этим на выход 11 второго коммутатора 5 в нечетные такты выводятся разности, представляющие собой коэффициенты xis(j) преобразования по нечетным функциям с нечетными номерами, а в четные такты - суммы, которые представляют собой коэффициенты xisQ) преобразования по нечетным функциям с четными номерами, сформированные на выходах сумматорагвычитателя Зп:

xisG)xG)-xG+4n;1),,3,5,..., у-1

S/i

n-h

N

xrG)xG)+x ), , 4, 6,.,., у

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

коэффициентов xi°G) преобразования по четным функциям Уолша выводятся на выход первого коммутатора 4П, а текущие значения

у коэффициентов xisG) преобразования по нечетным функциям выводятся на выход второго коммутатора 5 с частотой у fr до прихода (N+1)-ro текущего отсчета входного сигнала.

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

ройства, причем J-й вычислительный модуль содержит регистр, еумматор-вычитатель vt коммутатор, а n-й вычислительный модуль содержит два коммутатора/причем в j-м вычислительном модуле выход регистра подключен к первому входу сумматора-вычитателя. выходы суммы и разности которого подключены соответственно к первому и второму информационным входам коммутатора, а в п-м вычислительном модуле - первого и второго коммутаторов, второй вход сумматора-вычитателя соединен с информационным входом регистра и является информационным входом вычислительного модуля, первым тактовым входом которого является тактовый вход регистра, а m-м вычислительном модуле управляющий вход коммутатора подключен к второму тактовому входу вычислительного модуля, а в первом вычислительном модуле управляющий вход коммутатора подключен к первому тактовому входу вычислительного модуля, в 1-м вычислительном модуле выход коммутатора является выходом вычислительного модуля, отличающееся тем, что, с целью упрощения устройства и расширения функциональных возможностей за счет вычисления коэффициентов преобразования Уолшэ с упорядочением по частотам следования, оно содержит переключатель и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого подключен к первому информационному входу переключателя, выход которого подключен к второму тактовому входу n-го вычисли - - - 8ь/чит0нце Фиг. I

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

/2 EL .

fl РЧI

я

Фие.6