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

НАЦИОНАЛЬНЫЙ ЦЕНтР ИНТЕЛЛЕКТУАЛЬНОИ СОБСТВЕННОСТИ(71) Заявитель Учреждение образования Полоцкий государственный университет (ВУ)(72) Авторы МальЦев Сергей Васильевич Богущ Рихард Петрович (ВУ)(73) Патентообладатель Учреждение образования Полоцкий государственный университет (ВУ)Устройство вычисления векторно-матричного произведения, содержащее входной регистр, арифметические устройства и блок управления, отличающееся тем, что содержит запоминающее устройство промежуточных результатов, матричный коммутатор, постоянное запоминающее устройство и блок формирования адреса, причем входной регистр выполнен в виде последовательно-параллельного регистра, вход которого является информационным входом устройства, его дополнительные входы подключены к выходам запоминающего устройства промежуточных результатов, а выходы подключены ко входам матричного коммутатора, управляющие входы которого соединены с выходами постоянного запоминающего устройства, выходы матричного коммутатора через арифметические устройства соединены со входами запоминающего устройства промежуточных результатов, выходы блока управления соединены с управляющими входами запоминающего устройства промежуточных результатов, блока формирования адреса и главным управляющим входом постоянного запоминающего устройства, дополнительные управляющие входы которого подключены к выходам блока формирования адреса.Устройство относится К области вычислительной техники И может быть использовано в приборах и системах, в которых осуществляется беспоисковая синхронизация бинарных сигналов или декодирование кодов методом максимального правдоподобия.Известно устройство вычисления векторно-матричного произведения по Уолщу (ортогонального преобразования по Уолшу) 1, включающее сумматоры-вычитатели и регистры сдвига, причем первый и второй входы 1-го (1 1,2,) сумматора-вычитателя подключены соответственно к выходу и ко входу 1-го регистра сдвига, вход первого регистра сдвига является информационным входом устройства, выход суммы каждого из сумматороввь 1 читателей, имеющих номера с 2 по 2 п-1 (п 1,2,,11-1,2 М - число коэффициентов преобразования), подключен к входу соответствующего регистра сдвига из группы регистров сдвига, имеющих номера с 2 по 321-1, а выход разности - к входу соответствующего регистра сдвига из группы регистров сдвига, имеющих номера с 321 по 2 п 1-1, выходы суммы и выходы разности сумматоров-вычитателей, имеющих номера с 21 по 2 Ы-1,представляют собой 2 информационных выходов устройства. Недостатком известного устройства является то, что с помощью данного устройства невозможно вычислить векторно-матричное произведение для матриц с произвольной внутренней структурой и размерами.Наиболее близким по технической сущности является устройство вычисления векторно-матричного произведения для матриц на основе функций Уолща (для вычисления коэффициентов преобразования по Уолшу) 2, содержащее 1 о 3211 ступеней единичного преобразования, где Ы - число разрядов преобразуемой последовательности, каждая из ступеней содержит регистр сдвига, вход и выход которого соединены со входом сумматора-вычитателя, первый выход которого подсоединен к первым входам элементов И группы, выходы элементов И группы каждой ступени соединены с входами регистра сдвига последующей ступени, и блок управления, выходы которого соединены с вторыми входами элементов И групп всех ступеней единичного преобразования, а второй выход сумматора-вычитателя каждой ступени единичного преобразования соединен с третьими входами элементов И группы.Недостатком данного устройства является следующее. Использование устройства вь 1 числения векторно-матричного произведения для матриц на основе функций Уолща (для вычисления коэффициентов преобразования по Уолшу) возможно лищь для бинарных матриц с определенной внутренней структурой и размерами, т.е. для матриц, размером 1 Т 11, где Ы 2, а строки матриц представляют собой функции Уолща. Однако существует ряд бинарных сигналов с хорошими корреляционными свойствами (квадратично-вычетные коды, характеристические последовательности, коды Якоби и др.), матрицы-циркулянты которых невозможно свести к матрицам, строки которых содержат все функции Уолща. Следовательно, данное устройство неприменимо для таких типов сигналов.Задачей изобретения является сокращение времени вычисления векторно-матричного произведения и уменьщение за счет этого временных затрат при синхронизации или декодировании бинарных сигналов произвольных размеров и с произвольной внутренней матричной структурой.Поставленная задача рещается тем, что в устройство вычисления векторно-матричного произведения, содержащее входной регистр, арифметические устройства и блок управления, 2в отличие от прототипа, введены запоминающее устройство промежуточных результатов,Матричный коммутатор, постоянное запоминающее устройство и блок формирования адреса,причем входной регистр выполнен в виде последовательно-параллельного регистра, вход которого является информационным входом устройства, его дополнительные входы подключены К выходам запоминающего устройства промежуточных результатов, а выходы подключены ко входам матричного коммутатора, управляющие входы матричного коммутатора соединены с выходами постоянного запоминающего устройства, а его выходы через арифметические устройства соединены со входами запоминающего устройства промежуточных результатов, выходы блока управления соединены с управляющими входами запоминающего устройства промежуточных результатов, блока формирования адреса и главным управляющим входом постоянного запоминающего устройства, кроме того, дополнительные управляющие входы постоянного запоминающего устройства подключены к выходам блока формирования адреса.Ускоренное вычисление векторно-матричного произведения для матриц с произвольной внутренней структурой и размерами достигается вследствие того, что сначала вь 1 числяется сумма, соответствующая соседним парам столбцов матрицы и элементов вектора,затем эти результаты используются для образования сумм четырех элементов в столбцах матрицы и т.д. При этом на каждой итерации число различных сумм ограничено некоторой постоянной величиной, равной количеству неповторяющихся фрагментов строк исходной матрицы. Это позволяет исключить повторные вычисления одинаковых результатов. Процесс завершается через 1 о 32 М итераций.На фиг. 1 представлена блок-схема устройства вычисления векторно-матричного произведения. Устройство вычисления векторно-матричного произведения содержит входной последовательно - параллельный регистр 1 (РГ), вход которого является информационным входом устройства, а дополнительные входы подключены к выходам запоминающего устройства промежуточных результатов 2 (ЗУ). Выходы регистра 1 подключены ко входам матричного коммутатора 3 (МК). Управляющие входы матричного коммутатора МК соединены с выходами постоянного запоминающего устройства 4 (ПЗУ). Выходы матричного коммутатора МК через арифметические устройства 515 (АУ 1 АУ) соединены со входами ЗУ 2. Выходы блока управления 6 (БУ) соединены с управляющими входами ЗУ 2, блока формирования адреса 7 (БФА) и главным управляющим входом ПЗУ 4. Дополнительные управляющие входы ПЗУ 4 подключены к выходам БФА 7.Устройство работает следующим образом. В исходном состоянии в последовательнопараллельном регистре 1 записан вектор сигнал длиной М. Элементы вектор - сигнала через матричный коммутатор 3, который подключает к соответствующим входам арифметических устройств 5 вначале все элементы, которые необходимо сложить, а затем все элементы которые необходимо вычесть, поступают на арифметические устройства 5. Матричный коммутатор 3 управляется соответствующей матрицей сомножителем, которая защита в ПЗУ 4, на первой итерации первой матрицей. Результаты вычислений записываются в ЗУ 2 промежуточных результатов. На втором этапе вычислений данные из ЗУ 2 промежуточных результатов через входной регистр 1 подаются на матричный коммутатор 3, который управляется второй матрицей сомножителем, считанной из ПЗУ 4. Блок управления 6 осуществляет подбор итераций. БФА 7 управляется БУ 6 и формирует адреса сигнальных матриц, защитых в ПЗУ 4, в соответствии с текущей информацией. Процесс вычисления заверщается через 1 о 32 М итераций.Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.