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

вид 84. БЫСТРОГО УМНИЦУ. 54) УС ЕНИЯ В РОИ КТО О ДЛНА ОСУДАРСТВЕННЫЙ НОНИТЕТ СССР ДЕЛАН ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ОПИСАНИЕ ИЗ АВТОРСКОМУ С ВИВТВЪС(57) Изобретение относится к вычислительной технике, средствам обработки информации и может быть использовано для быстрой цифровой обработки сигналов, представленных в функции времени, Цель изобретения- уп"рощение устройства. Поставленнаяцель достигается за счет того, чтоустройство состоит из двигового регистра, двух групп коммутаторов по Б(где 11 - размерность вектора) коммутаторов в каждой, Б реверсивныхсчетчиков и элемента И с соответствующими связями между узлами устройства. 1 ил 1 табл.1 1280388 2Изобретение относится к вычисли- нение несущественно, если р велико, тельной технике, к средствам цифровой Например, допустив 17. погрешности, обработки информации и может быть можно вместо матрицы Адамара с использовано для быстрой цифровой п=128 использовать циркулянт с п=127. обработки сигналов, представленных в 5 Рассмотрим пример умножения сколь функции времени, зящего фрагмента последовательностиЦель изобретения - упрощение устХщ 00000001011011110101000000 на матна чертеже препстанпена схема уст- рину н размерности 7.7 ел 1 ройства, ЮУстройство, представленное на чертеже, содержит сдвигающий регистраргумента и вычислительный блок 2, который состоит иэ реверсивных счет" чиков 3 и шин связи 4, группу коммутаторов 5, шины 6 управления, выхо 1110101 0111010 0011101 1001110 0100111 1010011 1101001 Для удобства чтения отсчеты 7- элементных векторов Я(1) проводятся справа налево (рамкой отмечен Я(5).Результаты преобразования представлены в таблице,ды 7 счетчиков, группу коммутаторов 8, управляющий вход 9, элемент И 10 и информационный вход-выход 11,Устройство работает следующим образом.Соединение реверсивных счетчиков 3 с входной цепью соответствует занесению первого столбца матрицыциркулянта в регистр 2. Поэтому пос тупление каждой единицы последовательности Х в регистр 1 сопровождается занесением в регистр 2 следующего столбца матрицы М, В последующие временные интервалы смещению этой единицы в регистре 1 соответствует смещение столбца М в регистре 2, т.е.1 последовательноперечисляются все другие столбцы М, Другие единичные символы, входящие в регистр 1, 1вызывают суммирование первого столбца с результатом, который накапливается в регистре 2, что соответствует матричному умножению (суперпозиция столбцов матрицы в соответствии с видом вектора-сомножителя), Таким образом, осуществляется умножение на бесконечную периодическую матрицу, составленную иэ циркулянтов. Чтобы получить в регистре 2 результат умножения на конечную матрицу, необходимо изъять из суперпоэиции вклад, внесенный символами, выходящими из регистра аргумента.Наиболее важные ортогональные преобразования полностью или частично описываются через циркулянты, Например, матрицы Адамара размерностью р+1=4 К (где р - простое число) всегда могут быть построены как циркулянт из квадратичных вычетов и невычетов по модулю р, дополненный строкой и столбцом из единиц. Указанное дополУмножение вектора Я(1), на матрицу М осуществляется за один отсчет вре 25 меня, причем Я(1) и результат У=МЯ(1) в соответствующих регистрах 1 и 2 появляется одновременно, Формула и э обретения30 Устройство для быстрого умножениявектора на матрицу, содержащее Сдвиговый регистр, информационный вход которого является информационным входом устройства, о т л и ч а ю щ е ес я тем, что, с целью упрощения устройства, оно содержит первую и вторую группы из И коммутаторов (где И - размерность вектора), Б реверсивных счет-чиков и элемент И, выход которого подключен к управляющим входам коммутаторов первой группы, информационный вход сдвигового регистра объединен с первым информационным входом .-го (х=1701) коммУтатоРа втоРой гРУппы и является информационным входом устройства, первый и второй выходы которого подключены соответственно к суммирующему и вычитающему входам -го реверсивного счетчика, информационный выход которого подключен к информационному входу -го коммутаторапервой группы, выход которого подключен к управляющему входу 1-го коммутатора второй группы, второй информационнйй вход которого подключен к информационному выходу сдвигового регистра, а информационный вход- выход х-го коммутатора первой группыТакт, Содержание РА Содерхание РР%Я %л 3 с 1 Ят У, Уа Уз УМУ 5 У У 1 0 0000000 0000000 1 1000000 1001011 2 01 00000 1 1001 01и3 1010000 211 3 021 4 0101000 1211102 5 1010100 31223 21 6 1101010 2313223 7 1110101 4232333 8 1111010 3423233 9 0111101 3342323 10 1011110 3334232 11 1101 1 11 3334434 3332332 2333243 12 0110111 13 1011011 14 0101101 2232313 2222220 150010110 16 000 3 011 0222222 17 0000101 1021211 18 0000010 01011 3 0 0010111 19 000000 20 0000000 0000000 4 3 1280388 4является 1-м информационным входом- (+)-го реверсивного счетчика, вывыходом устройства, выход переноса ход переноса Б-го реверсивного -го =1,-1 ) реверсивного счетчи- счетчика подключен к установочному ка подключен к установочному входу входу первогореверснвного счетчика.1280388 Составитель А. Барановинская Техред М.Ходанич Корректор С. Черни Редактор Л. П Т иснР 5 Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектна каз 7052/43 ВНИИПИ Госуд по делам 113035, Москраж 671 По ственного комитета С обретений и открытий , Ж"35, Раушская наб