Устройство для вычисления векторно-матричного произведения

НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ВЕКТОРНО-МАТРИЧНОГО ПРОИЗВЕДЕНИЯ(71) Заявитель Полоцкий государственный университет(72) Авторы Мальцев Сергей Васильевич Богуш Рихард Петрович(73) Патентообладатель Полоцкий государственный университет(57) Устройство для вычисления векторно-матричного произведения, содержащее входной последовательно - параллельный регистр, вход которого является информационным входом устройства, запоминающее устройство промежуточных результатов, матричный коммутатор, блок управления, постоянное запоминающее устройство, блок формирования адреса и арифметические устройства, отличающееся тем, что оно дополнительно содержит -входовые суммирующие устройства, причем выходы регистра через -входовые суммирующие устройства подключены ко входам запоминающего устройства промежуточных результатов, выходы которого подключены ко входам матричного коммутатора,управляющие входы которого соединены с выходами постоянного запоминающего устройства, а выходы через арифметические устройства соединены с дополнительным входом запоминающего устройства промежуточных результатов, выходы блока управления соединены с управляющими входами блока формирования адреса, запоминающего устройства промежуточных результатов и главным управляющим входом постоянного запоминающего устройства, кроме этого дополнительные управляющие входы постоянного запоминающего устройства подключены к выходам блока формирования адреса.(56) 1. А.с. СССР 744555, МПК 067/38, 1980, БИ 24. 2. Пат. РБ 207 (полезная модель), МПК 06 5/00, 2000, ОБ 4 (прототип). Устройство относится к области вычислительной техники и может быть использовано в приборах и системах, в которых осуществляется беспоисковая синхронизация бинарных сигналов или декодирование кодов методом максимального правдоподобия. Известно устройство для вычисления векторно-матричного произведения для матриц на основе функций Уолша (для вычисления коэффициентов преобразования по Уолшу) 1,содержащее 2 ступеней единичного преобразования, где -число разрядов преобразуемой последовательности, каждая из ступеней содержит регистр сдвига, вход и выход которого соединены со входом сумматора - вычитателя, первый выход которого подсоединен к первым входам элементов И-группы, выходы элементов И-группы каждой ступени соединены с входами регистра сдвига последующей ступени, и блок управления,выходы которого соединены с вторыми входами элементов И-групп всех ступеней единичного преобразования, а второй выход сумматора-вычитателя каждой ступени единичного преобразования соединен с третьими входами элементов И-группы. Недостатком данного устройства является следующее. Использование устройства ускоренного вычисления векторно-матричного произведения для матриц на основе функций Уолша (для вычисления коэффициентов преобразования по Уолшу) возможно лишь для бинарных матриц с определенной внутренней структурой и размерами, т.е. для матриц, размером, где 2, а строки матриц представляют собой функции Уолша. Однако существует ряд бинарных сигналов с хорошими корреляционными свойствами (квадратично-вычетные коды, характеристические последовательности, коды Якоби и др.), матрицы-циркулянты которых невозможно свести к матрицам, строки которых содержат все функции Уолша. Следовательно, данное устройство неприменимо для таких типов сигналов. Наиболее близким по технической сущности является устройство для вычисления векторно-матричного произведения 2 содержащее входной регистр, арифметическое устройство, блок управления, запоминающее устройство промежуточных результатов,матричный коммутатор, постоянное запоминающее устройство, блок формирования адреса, а в качестве входного регистра используется последовательно-параллельный регистр,дополнительные входы которого подключены к выходам запоминающего устройства промежуточных результатов, а выходы подключены ко входам матричного коммутатора,управляющие входы матричного коммутатора соединены с выходами постоянного запоминающего устройства, а его выходы через арифметические устройства соединены со входами запоминающего устройства промежуточных результатов, выходы блока управления соединены с управляющими входами запоминающего устройства промежуточных результатов, блока формирования адреса и главным управляющим входом постоянного запоминающего устройства, кроме того дополнительные управляющие входы постоянного запоминающего устройства подключены к выходам блока формирования адреса. Недостатком данного устройства является следующее. Использование устройства для вычисления векторно-матричного произведения для матриц с произвольной внутренней структурой и размерами позволяет вычислять с помощью 2-х входовых арифметических устройств суммы наитерации для 2 соседних столбцов. При этом на каждой итерации число различных сумм ограничено некоторой величиной, равной количеству неповторяющихся фрагментов строк размером 2 на каждой итерации. Однако для матриц нелинейных бинарных сигналов возможно сокращение вычислительных затрат, если использовать внутреннюю и внешнюю процедуры векторно-матричного умножения. Для данного устройства, содержащего только 2-х входовые арифметические устройства, сокращение вычислительных затрат не приведет к уменьшению времени вычисления век 2 799 торно-матричного произведения, т.к. потребуется 21 итераций векторноматричного умножения где- число разрядов входного вектора,21 обозначает наибольшее ближайшее целое от дробного числа - 21. Задачей полезной модели является сокращение времени вычисления векторноматричного произведения и уменьшение за счет этого временных затрат при синхронизации или декодировании бинарных сигналов произвольных размеров и произвольной внутренней матричной структуры. Поставленная задача решается тем, что в устройство вычисления векторно-матричного произведения, содержащее входной последовательно - параллельный регистр, вход которого является информационным входом устройства, запоминающее устройство промежуточных результатов, матричный коммутатор, блок управления, постоянное запоминающее устройство, блок формирования адреса и арифметические устройства, в отличие от прототипа введены -входовые суммирующие устройства (2-1), входы которых подключены к выходам входного последовательно - параллельного регистра, а выходы подсоединены к основным входам запоминающего устройства промежуточных результатов,а выходы запоминающего устройства подключены ко входам матричного коммутатора,управляющие входы которого соединены с выходами постоянного запоминающего устройства ПЗУ, а выходы - через арифметические устройства соединены с дополнительным входом запоминающего устройства промежуточных результатов, выходы блока управления соединены с управляющими входами запоминающего устройства промежуточных результатов, блока формирования адреса и главным управляющим входом постоянного запоминающего устройства, кроме этого дополнительные управляющие входы постоянного запоминающего устройства подключены к выходам блока формирования адреса. Ускорение вычисления векторно-матричного произведения для матриц, размером, нелинейных бинарных сигналов достигается вследствие того, что используется оптимизация блочного разбиения матриц. Поэтому вначале вычисляются суммы для матрицблоков размером , где 2-1, т.е. осуществляется выполнение внутренней процедуры. Данная операция выполняется с помощью -входовых суммирующих устройств,которые могут быть построены на основе систолических, за одну итерацию. Необходимое число -входовых суммирующих устройств для вектора размеромопределяется, как. Затем осуществляется суммирование полученных результатов - осущест 21 вляется выполнение внешней процедуры за 2 / шагов с помощью арифметическихустройств, необходимое число которых определяется как. Таким образом, для 2 выполнения векторно-матричного умножения требуется (2 /) итераций. На фигуре представлена блок-схема устройства ускоренного вычисления векторноматричного произведения. Устройство ускоренного вычисления векторно-матричного произведения содержит входной последовательно - параллельный регистр (ППР) 1, вход которого является информационным входом устройства. Выходы регистра ППР через входовые суммирующие устройства (СУ) 2 подключены ко входам запоминающего устройства промежуточных результатов (ЗУ) 3. Выходы ЗУ подключены ко входам матричного коммутатора (МК) 4. Управляющие входы матричного коммутатора МК соединены с выходами постоянного запоминающего устройства (ПЗУ) 5. Выходы матричного коммутатора МК через арифметические устройства (АУ 1 АУр) 6 соединены с дополнительным входом ЗУ. Выходы блока управления (БУ) 7 соединены с управляющими входами ЗУ,блока формирования адреса (БФА) 8 и главным управляющим входом ПЗУ. Дополнительные управляющие входы ПЗУ подключены к выходам БФА. 3 799 Устройство работает следующим образом. В последовательно - параллельный регистр ППР поступает вектор-сигнал длиной , из которого составляющие вектор - сигнала длиной поэлементов поступают в суммирующие устройства СУ, где осуществляется вычисление векторно-матричного умножения для отрезков входного вектора длиной поэлементов, результаты вычислений в запоминающее устройство промежуточных результатов ЗУ, из которого, через матричный коммутатор МК, который подключает к соответствующим входам арифметических устройств АУ все элементы, которые необходимо сложить и вычесть на данной итерации, поступают на арифметические устройства АУ. Матричный коммутатор МК управляется соответствующей матрицей сомножителем, которая зашита в ПЗУ. На первой итерации МК управляется первой матрицей внешней процедуры. Результаты вычислений записываются в ЗУ промежуточных результатов. На втором этапе вычислений данные из ЗУ промежуточных результатов подаются на матричный коммутатор МК, который управляется второй матрицей сомножителем внешней процедуры, считанной из ПЗУ. Блок управления БУ осуществляет подбор итераций. БФА управляется БУ и формирует адреса сигнальных матриц, зашитых в ПЗУ, в соответствии с текущей информацией. Процесс вычисления завершается через (2 /) итераций, а результат вычисления снимается с выходов арифметических устройств. Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.