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

 

Изобретение относится к цифровой вычислительной технике и может быть использовано в системах цифровой обработки сигналов. Цель изобретения - расширение области применения за счет обработки многоразрядных данных Цель достигается за счет того, что в состав устройства входят регистры 1, 2 сдвига, коммутаторы 3, 4, триггер 5, элемент НЕ 6, счетчик 7, элемент ИЛИ-НЕ 8, счетчики 9, 10, сумматор-вычитатель 11, элементы И 12, 13, элемент ИЛИ-НЕ 14, триггеры 15,16. 2 ил.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК (51)5 G 06 F 15 332

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К А BTOPCKOMY СВИДЕТЕЛЬСТВУ

ГОСУДАРСТ8ЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (2I) 4658105/24 (22) 03.03.89 (46) 07.03.9!. Бюл. № 9 (71) Минский радиотехнический институт (72) В. Г. Березовский и В. В. Лосев (53) 681.32 (088.8) (56) Авторское свидетельство СССР № 325510, кл. G 06 F 15/332, 1987.

Авторское свидетельство СССР № 1280388, кл. G 06 F 15/332, 1986.

ÄÄSUÄÄ 1633424 A 1

2 (54) УСТРОЙСТВО ДЛЯ БЫСТРОГО УМНОЖЕНИЯ ВЕКТОРА НА МАТРИЦУ (57) Изобретение относится к цифровой вычислительной технике и может быть использовано в системах цифровой обработки сигналов. Цель изобретения — расширение области применения за счет обработки многоразрядных данных. Цель достигается за счет того, что в состав устройства входят регистры 1, 2 сдвига, коммутаторы 3, 4, триггер 5, элемент НЕ 6, счетчик 7, элемент ИЛИ вЂ” НЕ 8, счетчики 9, 10, сумматор-вычитатель 11, элементы И 12, 13, элемент ИЛИ вЂ” НЕ 14, триггеры 15,16. 2 ил.

Изобретение относится к цифровой вычислительной технике и может использоваться в системах цифровой обработки сигналов.

Цель изобретения — расширение области применения за счет обработки многоразрядных данных.

На фиг. 1 представлена структурная схема устройства для быстрого умножения вектора на матрицу; на фиг. 2 — временные диаграммы, поясняющие принцип работы.

Устройство содержит регистры I и 2 сдвига, коммутаторы 3 и 4, триггер 5, элемент

НЕ 6, счетчик 7, элемент ИЛИ вЂ” НЕ 8, счетчики 9 и 10, сумматор-вычитатель 11, элементы И 12 и 13, элемент ИЛИ вЂ” НЕ 14, триггеры 15 и 16, информационный вход 17, тактовый выход 18, информационный вход 19, тактовый выход 20, тактовый вход 21, вход

22 начальной установки, информационный выход 23.

Устройство для умножения вектора размерностью (mi+m ) на матрицу полного кода размером 2 " + ) (m +т2) работает следующим образом.

Устройство для умножения вектора размерностью выполняет операции ((Х, +

4- Y,) j= I — 2 " ),=1 — 2"" где первыми выполняются операции во внутренних скобках.

В начальный момент на вход 22 подается короткий импульс отрицательной полярности, который обнуляет все счетчики и триггеры устройства. Триггеры 15 и 16 подключают входы коммутаторов 3 и 4 к своим выходам. На информационный вход 17 подаются отсчеты Х„а на вход 19 — Y,. На тактовый вход 21 подается импульсный сигнал с частотой 1,, который используется для TBKтирования всей работы устройства. На триггере 5 он преобразуется в меандр с частотой т(2 и далее он тактирует работу регистра 2 сдвига и сумматора-вычитателя 11.

По переднему фронту тактового импульса регистр 2 сдвигает данные на одну позицию вправо. В случае, когда вход коммутатора

3 подключен к выходу, происходит циклический сдвиг данных. Сумматор-вычитатель

11 выполняет вычитание из операнда, поступившего на вход операнда, поступившего на другой вход, если на управляющем входе присутствует низкий уровень, и суммирование операндов, если на управляющем входе высокий уровень. Таким образом, за один период меандра, тактирующего работу сумматора-вычитателя 11, производится операция суммирования и вычитания, т.е. (Х,+w+- Y),= l — 2 « . С прямого выхода триггера

5 сигнал подается также на счетчик 7, где происходит деление частоты f p на 2, и далее полученный сигнал тактирует регистр 1 сдвига. По переднему фронту данные Х„ поступающие на его вход, будут сдвигаться вправо, таким образом будет происходить вычисление

I 633424

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

5 будет изменяться от 1 до 2 «, на вход реI гистра 1 сдвига будут подаваться данные Х, от другой группы. Выход 18 используется для тактирования вычислений (выдачи) данных XXf. Как только Х < появится в последней ячейке регистра 1 сдвига, т.е. на входе сумматора-вычитателя 11, на выходе элемента И 13 сформируется импульс положительной полярности, который установит на прямом выходе триггера 15 уровень логической единицы, что приведет к подключению входа коммутатора 4 к его выходу. В результате на выходе 20 появится сигнал для тактирования вычислений (выдачи) данных Y . Далее на прямом выходе триггера 16 установится уровень логической «1» и вход коммутатора 3 подключится к выходу.

20 По мере вычисления (Х"< Y,),=-l — 2

3 и выдвижения Y,: из регистра 2 сдвига в него будут заноситься данные У,. Как только процесс вычисления для Х будет окончен, в регистре 1 сдвига будет находиться послеГ довательность данных Х„в регистре 2 сдвиУ га последовательность данных У,, причем на одном входе сумматора-вычитателя бу/ I дет находиться Xi на другом Yi.

Триггеры 15 и 16 вернутся в исходное состояние, что приведет к подключению вхо3g дов коммутаторов 3 и 4 к их выходам. Далее процесс повторится для Х, и У „, т. е. ((Х, - YI),=1 — 2 "« ),=1 — 2 и

Если в качестве входных отсчетов исполь35 зуются координаты вектора, полученного от умножения вектора размерностью т на матрицу полного кода А,, т.е. X=A, 2„, и

Z,=!Zi, Zq, ..., Z,) ), а в качестве отсчетов

У, используются координаты вектора, полученного от умножения вектора размерно4О стью т на матрицу полного кода А, т.е.

У=А Z u Z = (Z,+ ь Z,„,+ >, ...,Z>+ ), то выходйые отсчеты являются координатами вектора, полученного от умножения вектора размерностью M на матрицу полного кода

45 А, т.е. И=Ам Z, причем M=mi+m и для четных М mi=m;, а для нечетных М т — — т2+-1. Так как в матрицах полного кода половина строк является инверсией другой половины строк, то устройство вычисляет и использует в качестве входных данных только

5р координаты, являющиеся результатом умножения вектора на «прямые» строки матрицы полного кода. Считается, что для инверсных строк координаты могут быть легко получены простым изменением знаков уже вычисленных коэффициентов. Вычисление коорди55 нат Х; и У, может производиться аналогичным устройством, тактированием работы, которая будет происходить соответственно с выходов 18 и 20. Устройство умножает вектор

1633424 на матрицу полного кода по алгоритмам с коэффициентом слож ности, стремящихс я к 0,5, где коэффициент сложности оценивается как число операций, приходящихся на одну строку матрицы.

Формула изобретения

Устройство для быстрого умножения вектора на матрицу, содержащее два коммутатора, первый элемент И и первый регистр сдвига, информационный вход которого является первым информационным входом устройства, отличающееся тем, что, с целью расширения области применения эа счет обработки многоканальных кодов, в него введены второй регистр сдвига, сумматор-вычитатель, три счетчика, два элемента ИЛИ—

НЕ; второй элемент И, три триггера и элемент НЕ, выход которого подключен к первым входам первого и второго элементов

ИЛИ вЂ” НЕ, выходы которых подключены к установочным входам первых соответственно счетчика и триггера, выход которого подключен к управляющему входу первого коммутатора, выход которого является первым тактовым выходом устройства и подключен к счетному входу первого счетчика, выход переноса которого подключен к первому входу второго элемента И, выход которого подключен к вторым входам первого и второго элементов ИЛИ вЂ” НЕ, прямой выход второго триггера подключен к первому информационному входу первого коммутатора, тактовому входу второго регистра сдвига, управляющему входу сумматора-вычитателя и счетному входу второго счетчика, выход переноса которого является вторым тактовым выходом устройства и подключен к тактовому входу первого регистра сдвига и счетному входу третьего счетчика, выходы разрядов которого подключены к соответствующим входам аервого элемента И, выход которого подключен к тактовому входу первого триггера и информационному входу третьего триггера, выход которого подключен к управляющему входу второго коммутатора, выход которого подключен к информационному входу второго регистра сдвига, выход которого подключен к первым информационным входам второго коммутатора и сумматора-вычитателя, второй информационный вход которого подключен к выходу первого регистра сдвига, инверсный выход второго триггера подключен к второму входу второго эле2О мента И, тактовому входу третьего триггера и информационному входу второго триггера, тактовый вход которого является тактовым входом устройства, входом начальной установки которого являются соединен ные 5 между собой установочные входы второго и третьего счетчиков, второго и третьего триггеров и вход элемента НЕ, выход сумматора-вычитателя является информационным выходом устройства, вторым информационным входом и входом логического нуля дО которого являются информационные входы соответственно второго и первого коммутаторов.

1633424

/ — -г г. 2

С оставител ь А. Ба р а нов

Редактор Е. П а п п Техред А. Кравчук Корректор С. Шевкун

Заказ 618 Тираж 407 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, )К вЂ” 35, Раушская наб., д. 4/5

Производственно-издательский комбинат «Патент», г. Ужгород, ул. Гагарина, 101