Устройство для быстрого умножения вектора на матрицу

 

Изобретение относится к вычислительной технике, средствам обработки информации и может быть использовано для быстрой цифровой обработки сигналов, представленных в функции времени. Цель изобретения - упрощение устройства. Поставленная цель достигается за счет того, что устройство состоит из двигового регистра , двух групп коммутаторов по N (где N - размерность вектора) коммутаторов в каждой, N реверсивных счетчиков и элемента И с соответствующими связями между узлами устройства . 1 ил., 1 табл.о 149 00 о со 00 оо

@р 4 G 06 F 15/332

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАН ИЗОБРЕТЕНИЙ И OTKPblTI44

1Й, т т1

ОПИСАНИЕ ИЗОБРЕТЕНИЯ /

Н COTOPCMOMY СННДНТННУНТНУ (21) 3922036/24-24 (22) 01,07.85 (46) 30.12.86. Бюл. I11 48 (72) А.Н. Радченко,;. И.К. Паберэ и В.И. Осадченко (53) 681.32(088.8) (56) Рабинер Л.,Гкулд Б, Теория и применение цифровой обработки сигналов. — М.: Мир, 1978.

Авторское свидетельство СССР

Ф 1078434, кл. G 06 F 15/332, 1984. (54) УСТРОЙСТВО ДЛЯ БЫСТРОГО УМНО1КЕНИЯ ВЕКТОРА НА МАТРИЦУ.,SU„„ 0388 А1 (57) Изобретение относится к вычислительной технике, средствам обработки информации и может быть использовано для быстрой цифровой обработки сигналов, представленных в функции времени. Цель изобретения - yn"" рощение устройства. Поставленная цель достигается эа счет того, что устройство состоит из двигOBDFO регистра, двух групп коммутаторов по И (где N — - размерность вектора) коммутаторов в каждой, N реверсивных счетчиков и элемента И с соответствующими связями между узлами устройства. 1 ил., 1 табл.

1 1280388 2

Изобретение относится к вычисли- нение несущественно, если р велико. тельной технике, к средствам цифровой Например, допустив 1Х погрешности, обработки информации и может быть можно вместо матрицы Адамара использовано для быстрой цифровой n= 1 28 использовать циркулянт с п=127. обработки сигналов, предстанленных в 5 Рассмотрим пример умножения сколь

Функции времени, зящего фрагмента последовательности

Цель изобретения - упрощение устX=00000001011011110101000000 на мат0а чертеже предстанпена схема уст- риду 11 раемернссти 7 ° 7 и Ч " " ройства. 10

Устройство, представленное на чертеже, содержит сдвигающий регистр

1 аргумента и вычислительный блок 2, который состоит иэ реверсивных счет" чиков 3 и шин связи ч, группу коммутаторов 5, шины 6 управления, выхо1110101

0011101

0100111

1010011

1101001

Для удобства чтения отсчеты 7элементных векторов Q(t) проводятся справа налево (рамкой отмечен Я(5).

Результаты преобразования представлены в таблице, Умножение вектора a(), на матрицу

М осуществляется за один отсчет времени, причем Q(t ) и результат Y=MQ(t) в соответстнующих регистрах 1 и 2 появляется одновременно.. ды 7 счетчиков, группу коммутаторов

8, управляющий вход 9, элемент И 10 и информационный вход-выход 11.

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

Соединение ренерсинных счетчиков

3 с входной цепью соответствует занесению перного столбца матрнцыциркулянта в регистр 2. Поэтому пос« тупление каждой единицы последовательности Х н регистр 1 сопровождается занесением в регистр 2 следующего столбца матрицы М, В последующие временные интервалы смещению этой единицы в регистре 1 соответствует смещение столбца М в регистре

2, т.е.1последонательно перечисляются нсе другие столбцы М. Другие еди ничные символы, входящие н регистр 1, I вызывают суммирование первого столбца с результатом, который накапливается в регистре 2, что соответствует матричному умножению (суперпозиция столбцов матрицы в соответствии с видом вектора-сомножителя), Таким образом, осуществляется умножение на бесконечную периодическую матрицу, составленную иэ циркулянтон. Чтобы получить в регистре 2 результат умножения на конечную матрицу, необходимо изъять из суперпоэиции вклад, внесенный символами, выходящими из регистра аргумента.

Наиболее важные ортогональные преобразования полностью или частично описываются через циркулянты, Например, матрицы Адамара размерностью р+1=4К (где р - простое число) всегда могут быть построены как циркулянт из квадратичных вычетов и невычетон по модулю р, дополненный строкой и . столбцом из единиц. Указанное дополФ о р м у л а и э обретения

Устройство для быстрого умножения вектора на матрицу, содержащее Сдвигоный регистр, информационный вход которого является информационным вхо35 дом устройства, о т л и ч а ю щ е ес я тем, что, с целью упрощения устройства, оно содержит перную и вторую группы из N коммутаторов (где N — размерность вектора), Б реверсивных счет- чиков и элемент И, выход которого подключен к управляющим входам коммутаторов первой группы, информационный вход сднигового регистра объединен с первым информационным входом i-го (i--17111) коммутатора второй группы и является информационным входом устройства, первый и второй выходы которого подключены соответственно к суммирующему и вычитающему входам i-ro реверсивного счетчика, информационный выход которого подключен к информационному входу 5.-го коммутатора первой группы, выход которого подключен к управляющему входу i-ro коммутатора второй группы, второй информационнйй вход которого подключен к информационному выходу сднигового регистра, а информационный входвыход i-ro коммутатора первой группы

Такт, Содержание PA Содерхание PP! 4 У 3 4 Б 1

0 0000000 0000000

1 1000000 100101 1

2 0100000 1 100101

3 1010000 21 1 1021

4010)0001211)02

5 ) 010100 3122121

6 1 101010 2313223

7 1110101 4232333

811110103423233

901111013342323

1010111103334232

11 11011 11 3334434

3332332

2333243

120110111

131011011

1401011012232313

2222220

150010110

16 000 ) 01 1 0222222!

700001011021211

1S 0000010 - 01 01 1 1 0

0010111

19 000000!

20 0000000 0000000

3 1280388 4 является -м информационным входом- (j+))-ãî реверсивного счетчика, вывыходом устройства, выход переноса ход переноса Б-го реверсивного

$-ro (1=1,1 -1 ) реверсивного счетчи- счетчика подключен к установочному ка подключен к установочному входу - входу первогореверснвного счетчика.

1280388

Я

С

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

Редактор Л. Пчелинская Техред М.Ходанич Корректор С. Черни

Заказ 7052/43 Тираж 671 Подписное

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

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

Производственно-полиграфическое предприятие, r. Ужгород, ул. Проектная, 4