Вероятностное устройство для умножения матриц

 

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

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

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

РЕСПУБЛИК (19) (11) M5D G 06 F 7 70

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ.И ОТКРЫТИЙ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 3477609/18-24 (22) 28.07.82 (46) 23.11.83. Бюл. )) 43 (72) В.В. Яковлев, О.С. Mальченкова и A.Â. Яковлев (71) Ленинградский ордена Ленина институт инженеров железнодорожного транспорта им. акад. В.Н. Образцова (53) 681.3(088.8) (56) 1. Гладкий В.С. Вероятностные вычислительные модели. М., "Наука", 1973, р. 5.1.

2. Авторское свидетельство СССР

9 774413, кл. G 06 F 15/36, 1978 (прототип). (54) (57) ВЕРОЯТНОСТНОЕ УСТРОЙСТВО

ДЛЯ УМНОЖЕНИЯ МАТРИЦ, содержащее первый и второй блоки ключей, руппы входов которых являются входами устройства, блок преобразователей число вЂ, вероятность, первая группа входов:которого соединена с первой группой выходов первого блока ключей, блок умножителей, первая и вторая группы входов которого соединены соответственно с первой группой выходов второго блока ключей и группой выходов блока преобразователей число-вероятность, блок сумматоров, группа входов которого соединена с группой выходов блока умножителей, блок интеграторов, груп- . па входов которого соединена с группой выходов блока сумматоров, третий блок ключей, группа входов которого соединена с группой выходов блока интеГраторов, а группа выходов является выходами устройства, генератор случайной последовательности, выход которого соединен с входом блока сумматоров, генератор случайных чисел, выход которого соединен с входом генератора случайной последовательности и управляющим входом блока преобразователей число-вероятность, генератор тактовых импульсов, выход которого соединен с входом генератора случайных чисел, блок управления, состоящий из последовательно соединенных триггера, Е элемента 0 и счетчика, причем выход триггера соединен с первым входом элемента 0 и управляющими входами первого, второго и третьего блоков ключей, второй вход элемента

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

105б192

10

14

И 42

9 И 14

24 22 ° 24 а <2 . а44

2t 22 74

° ° ° °

° ° ° onn „л bn2

° . ° а rl ап2 ° ° ° ann

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

n-ro порядка.

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

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

Наиболее близким техническим решением к изобретению является вероятностное устройство для умножения матриц, содержащее первый блок ключей, вторая группа выходов которого через вторую группу входов .блока преобразователей число — веI 1 где — — вероятность появления сим.п вола 1 в случайной бинарной последовательности, вырабатываемой генератордм стохастических констант, связан с преобразованием п чисел исходной матрицы (Ь; ) в случайные бинарные последовательности (2) .

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

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

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

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

Процесс вычислений элементов выходной матрицы (с; ) ii, j =1, 2 . ° .

n)

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

1056192

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

По сигналу "Пуск", который является внешним по отношению к устройству, триггер 12 устанавливается в "1". Данное состояние триггера является сигналом разрешения переда 65 умножителей и второй группой входов блока преобразователей число— вероятность.

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

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

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

\ подключена,к первой группе выходов второго блока 7 ключей. Вторая группа выходов блока 7 соединена с второй группой входов блока 2 преобразователей число-вероятность, первая группа входов которого соеди иена с первой группой выходов первого блока 1 ключей, а выходи — с второй группой входов блока 3 умнежителей, Выкоды блока 3 умножйтелей соединены с группой входов блока 4 сумматоров, группа выходов которого подключена к группе входов блока 5 интеграторов, группа выходов блока 5 соединена с группой входов третьего блока 6 ключей, выходы которого являются выходами устройства. Управляющий вход треть- 40 его блока 6 ключей соединен с управляющими входами первого 1 и второго

7 блоков ключей и выходом триггера 12 блока 11 Управления, второй вход элемента 13 которого соединен 45 с выходом генератора 9 тактовых импульсов и входом генератора 10 случайных чисел. Выход генератора

10 подключен к управляющему входу блока 2 преобразователей число- 50 вероятность и к входу генератора 8 случайной последовательности, выход которого соединен с входом блока 4 сумматоров. В блоке 11 управления первый вход элемента 13 соединен с выходом триггера 12, выход — с входом счетчика 14, а выход счетчика 14

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

Как и в известном устройстве элементы матриц (а; ), Ь; ) пред ставлены двоичными (-раэрчднымн кодами с фиксацией запятой перед стар" шим разрядом. По сигналу из блока 11 управления г старших. разрядов чисел а; и b f через блоки 1 и 7 ключей передаются на блок 3 умножителей.

Одновременно все оставшиеся 1- r младших разрядов чисел через блоки 1 и 7 ключей поступают на блок 2 пре.образователей число-вероятность, где осуществляется их преобразование в случайные последовательности бинарных символов х; и у с вероятностями соответственно р(x, 1 1)

p(у;; =1)=8;, где,. к; и 8 двойчные значения 1- г=разрядных чисел соответственно а; и Ь;.

Например, если а" =, Ь"

<1 З

3, 1 то при г=2 имеем a! =, 8" = 5г ° 41 5

Образованные случайные последовательности х; и 1; представляют младший разряд чисел aj u bij cooTветственно..В блоке 3 умножителей осуществляется перемножение указанных вероятностно округленных чисел по известным правилам матричного умножения. Например, для получения элемента с;

<,1 с = (а b" +а Ь + ...+

<1 и 1 11 (2 2 (1)

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

1 1 с весом — . Весовой коэффициенти и вырабатываемый генератором 8 случайной последовательности, представлен бинарной случайной последовательностью символов Г с вероятностью

p(f)= и

Использование несовместных случайных последовательностей f (S 1, S

2 . ° ., n) обеспечивает получение на выходах блока 4 сумматров последовательностей случайных двоичных чисел, математические ожидания кото

1056192

Фиг 7

Фиа2

ВНИИПИ Эаказ 9307/42 Тираж 706 Подписное

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

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

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

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