Устройство для вычисления коэффициентов Уолша Советский патент 1988 года по МПК G06F17/14 

л4а4: 4

СХ)

Изобретение относится к автоматике и вычислительной технике и может быть использовано в аппаратуре обработки и сжатия информации, при передаче данных, в аппроксимируюпа1х устройствах кусочно-квадратичного типа. Цель изобретения - повышение точности аппроксимации за счет применения преобразования в базисе кусочно-квадратичных функций Уолша. Поставленная цель достигается за счет того, что в состав устройства входят арифметический блок 1, мультиплексоры 2, регистры сдвига 3, сумматоры 4, распределитель импульсов 5 и вьмита- тели 6. 4 ил. с S СО

fft-l

Изобретение относится к автоматике и вычислительной технике и может быть использовано в аппаратуре обра- бот}си и сжатия информации, при пере- даче данных, в аппроксимирующих устройствах кусочно-квадратического типа.

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

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

R a R, Б к7 W

, W F,W,

(1)

где FI J RI первые разности; (2) F F| Rj. - вторые разности; (3) F F, . R7 третьи разности. (4) С учетом (1) - (4) алгоритм вычисления С можно записать как I шаг вычисление F, :

fo f, f f iCR; Cfo,f.-fo,f2.-f,,

f.- г f.fi.fi, f;i. -

IImar - вычисление

f:f:fU; R; rfo.f;:f;, f;,

f;-4+f;-f tfo.f,fi,ft.

IIIшаг - вычисление Fj

V-fi fi f2 fj-irR-n-ffZ

)( J L- -O - - o г 1 J p I-i tj.J- t, ,

IVmar - вьшолнение быстрого преобразования Уолша над вектором F.J .

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

Устройство для вычисления коэффициентов Уолша содержит арифметичес- кий блок Ij мультиплексоры 2, регистры сдвига 3, сумматоры 4, распределитель импульсов 5, вычитатели 6,

Арифметический блок 1 (фиг.2) содержит первую и вторую группы вычи- тателей 7, 8 соответственно.

Распределитель импульсов 5 (фиг.З) содержит счетчики 9, 10, одновибра- тор 11, триггер 12j элемент ИЛИ 13,

Распределитель импульсов 5 работает следующим образом.

По перепаду сигнала на втором входе одновибратор 11 формирует импульс, устанавливающий все вычита

°

„

5

тели и сумматоры-вычитатели устройства, а также триггер 12 в О. Коэффициент пересчета oi счетчика 10 опр еделяется максимальной разрядностью операндов с учетом возможных переносов и задержек в арифметическом блоке 1. Коэффициент пересчета счетчика 9 равен ,N (где N - размерность массива, определяет число шагов вычислительного алгоритма), По тактовым импульсам содержимое счетчика увеличивается на единицу до тех пор, пока не станет равно oi. , при этом на выходе будет сформирован сигнал, устанавливающий триггер 12 в 1. Одновременно содержимое счетчика 9 увеличится на 1. При появлении последующих импульсов на выходе счетчика 10 состояние триггера 12 не изменяется, а содержимое счетчика 9 увеличивается на 1, При накоплении в счетчике 9 п импульсов на его выходе формируется логический перепад, запускающий одновибратор 11, который устанавливает все счетчики и триггер 12 в исходное состояние.

Арифметический блок 1 представляет собой набор одноразрядных вычита- телей и работает следующим образом.

На первый выход k-ro вычитателя 8 поступает k-й отсчет входного массива f(t|) в последовательном коде, начиная с младшего разряда. Этот же отсчет поступает на второй вход разности (k-f O-ro вычитателя. При этом на выходах вычитателей 8 формируются первые разности согласно (2), которые поступают на входы вычитателей 7. Выход каждого k-ro вычитателя 7 подключен к второму входу разности (k+l)-ro вычитателя 7. Такое соединение позволяет сформировать на выходах вычитателей 7 вторые разности согласно (3), которые поступают на входы вычитателей 8.

Вычитатели 8 соединены аналогично вычитателям б и формируют на своих выходах третьи разности согласно (4).

Устройство для вычисления коэсЬфи- цнентов Уолша работает следующим образом.

Все блоки устройства тактируются синхронно, В исходный момент все блоки устройства обнулены. При этом на первом выходе распределителя импульсов 5 присутствует О, что обеспечивает подключение выходов арифметического блока 1 через вычитатели 6

и мультиплексоры 2 к входам регистров 3 сдвига. Далее синхронно тактовым импульсам в арифметический блок 1 поступают ординаты функции f(t), где выполняется преобразование R , а результат записывается в регистры

3в течение oi тактов. Через oi тактов на выходе распределителя импульсов 5 устанавливается высокий потенциал, который подключает выходы сумматоров

4через мультиплексоры 2 к соответствующим регистрам 3 сдвига. Каждый четный сумматор 4 работает в режиме суммирования,, а каждый нечетный - в. режиме вычитания. Тем самым в соседних парах сумматоров 4 формируются суммы и разности операндов, которые пересылаются в соответствующие регистры 3 сдвига согласно алгоритму на фиг.4. Таким образом, через not/ тактов в регистрах 3 сдвига будут содержаться коэффициенты разложения в ряд в базисе кусочно-квадратичных функций Уолша. Далее О на зшрав- ляющих входах мультиплексоров 2 подключает выход арифметического блока

1 к входам регистров 3 и параллельно с вводом новой реализации f(t) г осуществляется вывод коэффициентов С предыдущей реализации.

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

Устройство для вычисления коэффициентов Уолша, содержащее N-1 вычи- тателей (N - размер преобразования), N сумматоров, N регистров сдвига, N мультиплексоров и распределитель импульсов, первый и второй выходы которого подключены соответственно к управляющим входам всех мультиплексо ров и тактовым входам всех регистров сдвига, выход i-ro (,N-l) вычита теля подключен к первому информационному входу (1+1)-го мультиплексора, выход которого подключен к информационному входу (i+l)-ro регистра сдвига, выход которого является вы- ходом i-ro коэффициента Уолша уст4448174

ройства, выходом нулевого коэффициента Уолша которого является выход первого регистра сдвига, выход кото- 5 рого подключен к выходу первого мультиплексора, отличающееся тем, что, с целью повышения точности аппроксимации за счет использования преобразования в базисе кусочно-квад10 ратичных функций Уолша, в него введен арифметический блок, 1-й (,N) вход которого является входом (l-l)-ro входного отсчета устройства, т-й (,N-l) выход арифметического бло15 ка подключен к первому входу т-го и второму входу (т+1)-го вычитате- лей, первый выход арифметического блока подключен к первому шгформа- ционному входу первого мультмплексо20 ра, а N-й выход арифметического блока подключен к первому входу (N-l)-ro вычитателя, выход (2j+l)-ro сумматора (,N/2-l) подкл очен к второму информационному входу (j+l)-ro муль25 типлексора, а выход (2JH-2)-ro сумматора подключен к второму информационному входу (j+N/2+i)-ro мультиплексора, выход (2j+l)-ro регистра сдвига подключен к первым входам (2J+1)30 го и (2j+2)-ro сумматоров, вторые выходы которых подключены к выходу (2j+2)-ro регистра сдвига, йричем арифметический блок содержит первую и вторую группы из (N-1) вычитате35 лей каждая, при этом выход k-ro (k 1,N-1) вычитателя первой группы подключен к первому входу k-ro вычитателя второй группы, первые входы первых вычитателей подключены к первому

40 входу арифметического блока, ()-м входом которого являются соедшшнные между собой второй вход i-ro и первый вход (i+l)-ro вычитателей первой группы, первый выход арифметического 45 блока подключен к первому входу арифметического блока, выход i-ro вычитателя второй группы подключен к второму входу (i+)-ro вычитателя второй группы и является (i-tl)-M выхо50 дом арифметического блока.

Фи.2

Фые.З

о

Cf

.,.

ь-Фиг. /