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

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