Вероятностное устройство для умножения матриц Советский патент 1983 года по МПК G06F7/70 

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

Известно вероятностное устройство для умножения матриц, содержащее преобразователи число-вероятность, блоки умножения и сложения, генератор случайных чисел, интеграторы элементов выходной матрицы l .

Недостатком этого устройства является низкая точность, Связанная с применением однорозрядного вероятностного кодирования 2 п чисел элементов двух исходных матриц.

Наиболее близким техническим решением к изобретению является вероятностное устройство для умножения матриц, содержащее,первый блок ключей, вторая группа выходов которого через вторую группу входов .блока преобразователей число - вероятность соединена с второй группой входов блока умножения, первая группа входов которого подключена к первой группе выходов третьего блока ключей, а выходы через последовательно соединенные блок сложения, блок интегрирования соединены соответственно с входами второго блока ключей, выходы которого являются выходами устройству, управляющий

вход второго блока ключей соединен с управляющими входами первого и третьего блоков ключей и выходом блока управления, вход которого соединен с выходом генератора тактовых импульсов и входом генератора случайных чисел, выход которого подключен к управляющему входу блока преобразователей число-вероятность и к входу генератора стохастических констант, выход которого соединен с входом блока сложения.

Процесс вычислений злементов выходной матрицы (i, j 1, 2 ... п)

ВЕРОЯТНОСТНОЕ УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ Г4АТРИЦ, содержащее первый и второй блоки ключей, -руппы входов которых являются входами устройства, блок преобразователей число - вероятность, первая группа входов которого соединена с первой группой выходов первого блока ключей, блок умножителей, первая и вторая групщл входов которого соединены соответственно с первой группой выходов второго блока ключей и группой выходов блока преобразователей число-вероятность, блок сумматоров, группа входов которого соединена с группой выходов блока умножителей, блок интеграторов, группа входов которого соединена с группой выходов блока сумматоров, третий блок ключей, группа входов которого соединена с группой выходов блока интеграторов, а группа выходов является выходами устройства, генератор случайной последовательности , выход которого соединен с входом блока сумматоров, генератор случайных чисел, выход которого соединен с входом генератора случайной последовательности и управляющим входом блока преобразователей число-вероятность, генератор тактовых импульсов, выход которого соединен с входом генератора случайных чисел, блок управления, состоящий,из посi ледовательно соединенных триггера, элемента U и счетчика, причем вы(Л ход триггера соединен с первым входом элемента и и управляющими входами первого, второго и третьего блоков ключей, второй вход элемента и подключен к выходу генератора так товых импульсов, а выход.счетчика соединен с входом сброса триггера, .установочный вход которого являето л ся пусковым входом устройства, о т л и ч а ю щ е е с я тем, что с целью повышения точности, вторые 3 группы выходов первого и второго блоков ключей соединены соответственно с третьей группой входов бло;о ка умножителей и второй группой N5 входов блока преобразователей число - BepoHTHocTis.

где - вероятность появления символа 1 в случайной бинарной последовательности, вырабатываемой генераTopdM стохастических констант, связан с преобразованием п чисел исходной матрицы Ь в случайные бинарные последовательности 2 .

Недостатком известного устройства является низкая статистическая точность вычислений элементов матрицы с;Л .

Цель изобретения - повышение точности.

Поставленная цель достигается тем, что в вероятностном устрой-стве для умножения матриц, содержащем первый и второй блоки ключей, группы входов которых являются входами устройства, блок преобразователей число - вероятность, первая группа входов которого соединена с первой группой выходов первого блока ключей, блок умножителей, первая и вторая группы входов которого соединены соответственно с первой груп. пой выходов второго блока ключей и группой выходов блока преобразователей число-вероятность, блок сумматоров, группа входов которого соединена с группой выходов блока умно жителей, блок интеграторов, группа

входов которого соединена с группой выходов блока сумматоров, третий блок ключей, группа входов которого соединена с группой выходов блока интеграторов, а группа выходов является выходами устройства, генератор случайной последовательности,, выход которого соединен с входом блока сумматоров, генератор случайных чисел, выход которого соединен

5 с входом генератора случайной последовательности и управляющим входом блока преобразователей число - вероятность, генератор тактовых импульсов , выход которого соединен с вхо- ,

0 дом генератора случайных чисел, блок управления, состоящий из последовательно соединенных триггера, .элемента и и счетчика, причем выход триггера соединен с перв1.1м входом элемента U и управляющими входами первого, второго и третьего блоков ключей, второй вход элемента U подключен к выходу генератора тактовых импульсов, а выход счетчика соединен с входом сброса триггера, установочный вход которого является пусковым входом устройства, вторые группы первого и второго блоков ключей соединены соответственно

5 с третьей группой входов блока

умножителей и второй группой входов блока преобразователей число вероятность.

На фиг. 1 приведена блок-схема предлагаемого устройства; па фиг. 2 - блок-схема блока управления.

Устройство (фиг. 1) содержит первый блок 1 ключей, блок 2 преобразователей число - вероятность, блок 3 умножителей, блок 4 суг 1маторов, блок 5 интеграторов, третий блок б ключей, второй блок 7 ключей, генератор 8 случайной последовательности, генератор 9 тактовых импульсов, генератор 10 случайных чисел, блок 11 управления (фиг, 2), который в свою очередь содержит триггер 12, элемент U 13 и счетчик 14.

Вторая группа выходов первого блока 1 ключей соединена с третьей группой входов блока 3 умножителей, первая группа входов которого подключена,к первой группе выходов второго блока 7 ключей. Вторая группа выходов блока 7 соединена с второй группой входов блока 2 преобразователей число-вероятность, первая группа входов которого соединена с первой группой выходов первого блока 1 ключей, а выходы - с второй группой входов блока 3 умножителей, Выходы блока 3 умножителей соединены с группой входов блока 4 сумматоров, группа выходов которого подключена к группе входов блока 5 интеграторов, группа выходов блока 5 соединена с группой входов третьего блока б ключей, выходы которого являются выходами устройства. Управляющий вход третьего блока б -ключей соединен с управляющими входаш первого 1 и второго 7 блоков ключей и выходом триггера 12 блока 11 управления, второй вход элемента 13 которого соединен с выходом генератора 9 тактовых импульсов и входом генератора 10 случайных чисел. Выход генератора 10 подключен к управляющему входу блока 2 преобразователей число вероятность и к входу генератора 8 случайной последовательности, выход которого соединен с входом блока 4 сумматоров. В блрке 11 управления первый вход элемента 13 соединен с выходом триггера 12, выход - с входом счетчика 14, а выход счетчика 1 с входом триггера 12.

Устройство работает следующим образом.

По сигналу Пуск, который является внешним по отношению к устройству, триггер 12 устанавливается в 1. Данное состояние триггера является сигналом разрешения передачи информации через блоки 1 и 7 ключей. Одновременно открывается элемент и 13 и на вход счетчика 14 начинают поступать импульсы от генератора 9 тактовых импульсов. Разрядность счетчика определяется временем решения и зависит от заданного уровня погрешности вычислений. Импульс . переполнения счетчика 14 устанавливает триггер в нулевое состояние,

0 которое является сигналом разрешения передачи результатов вычислений через третий блок 6 ключей. Как и в известном устройстве элементы матриц Сз,-Л . i пред-

S ставлены двоичниг«1 I-разрядным кодами с фиксацией запятой перед старшим разрядом. По сигналу из блока 11 управления г старших разрядов чисел а,-, и b,j через блоки 1 и 7 ключей

Q передаются на блок 3 умножителей Одновременно все оставшиеся 1-г младших разрядов чисел через блоки 1 и 7 ключей поступают на блок 2 преобразователей число-вероятность.

где осуществляется их преобразование в случайные последовательности бинарных символов х;: и с вероятноетями соответственно p(x,i 1)

/ , Р( УМ )5м -И 5

SM двоичные значения 1- г-разрядных чисел соответственно а;; и Ь;; .

19 17 Например, если а-; -jj , b- уу ,

1 ТТ

то при имеем OL- -w , S,

Образованные случайные последовательности x;j и ). представляют младший разряд чисел и b,j соответственно. В блоке 3 умножителей осуществляется перемножение указанных вероятностно округленных чисел по известным правилам матричного умножения. Например, для получения элемента с-45

) В блоке 4 сумматоров осуществляется в соответствии с выражением (1), суммирование полученных произведений

с весом - . Весовой коэффициент у- ,

вырабатываемый генератором 8 случайной последовательности, представлен бинарной случайной последовательностью символов f с вероятностью P(f)f.

Использование несовместных случайных последовательностей fg (5 1 2 ..., п) обеспечивает получение на выходах блока 4 сумматров последовательностей случайных Двоичных

чисел, математические ожидания кото рых для каждого машинного такта соответствуют выражению {1). В блоке 5 интеграторов осуществляется декодирование соответствующих стохастических величин, т.е. получение оценок элементов матрицы сц . По сигналу из блока 11 управления содержимое сумматоров блока 5 с помощ третьего блока 6 ключей передается на выход устройства. I Таким образом, вычисления в из;в естном и предложенном устройствах ;производятся в соответствии с

tJS,7 ражением (1J, т.е. арифметические возможности устройств одинаковы, однако точностные характеристики су111,ественно различаются. В предложенном устройстве увеличение точности в работе достигается путем снижения дисперсии потоков чисел на выходах блока умножителей.. Таким образом, технико-экономический эффект предлагаемого устройства по сравнению с известным заключается в существенном уменьшении статической погрешности при выполнении умножения матриц.