Устройство для быстрого умножения вектора на матрицу
Изобретение относится к вычислительной технике, средствам обработки информации и может быть использовано для быстрой цифровой обработки сигналов, представленных в функции времени. Цель изобретения - упрощение устройства. Поставленная цель достигается за счет того, что устройство состоит из двигового регистра , двух групп коммутаторов по 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
