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

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