Вероятностное устройство для реше-Ния СиСТЕМ лиНЕйНыХ АлгЕбРАичЕСКиХуРАВНЕНий Советский патент 1981 года по МПК G06F7/70 G06F7/38 G06F17/18 

(54) ВЕРОЯТНОСТНОЕ УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ минающем устройстве (ЗУ) хранятся все коэффициенты -jj и свободные члены (i , ,2,3 -.n) Процесс считывания из динамического ЗУ организован так, что на первый блок ключей передаются в первом такте синхронизации п чисел (Ь;,- (i 1 ,2. . .Д1) , во втором такте п коэффициентов ( ,2 . . ./i) в третьем такте п коэффициентов (,2...,n) и т.д. В блоке преобразователей число-вероятность осуществляется в каждом такте параллельное преобразование п этих чисел в бинарHbte символы, вероятности появления которых численно равны величинам преобразуемых чисел. После этого символы записываются в блок регистров сдвига состоящий из п регистров сдвига. Пос ле заполнения регистров вероятностны ми отображениями, что фиксируется во времени процессом переполнения счетчика, происходит выполнение очередно итерации il, Недостатком этого устройства является низкое быстродействие при вычислении корней системы линейных алгебраических уравнений, что связано с тем,что длительность каждой итерации определяется временем заполнения всех разрядов блока регистров сдвига п вероятностными отображениями 4viсел ; ot,j4 Другими словами каждая К-я итерация выполняется за п тактов частоты генератора тактовых импульсов. Цель изображения - увеличение быстродействия устройства. Поставленная цель достигается тем что вероятностное устройство для решения систем линейных алгебраических уравнений, содержащее последовательно соединенные блок динамического запоминания, первый блок ключей, бло преобразователей число-вероятность, блок регистров сдвига,второй блок ключей, блок умножения, блок сложения, блок интегрирования, третий блок ключей, выход которого является выходом устройства, счетчик, выход которого соединен с управляющими вхо дами второго и третьего блоков ключе генератор случайных чисел, выход которого соединен с управляющим входом преобразователей число-вероятность, генератор тактовых импульсов, выход которого соединен с управляющим входом первого блока ключей, входом синхронизации блока регистров сдви0га и входом генератора случайных чи сел, блок задержки, входы которого соединены с соответствующим выходами блока сложения, а выходы с соответствующи.ми входами блока умножения, дополнительно содержит первый и второй блоки инверторов элемент И, первый и второй элементы ЗАПРЕТ разрещающие входы которых соединены с выходом генератора тактовых импульсов, входы первого блока инверторов соединены с соответствующими выходами блока задержки, а выходы - с соответствующими входами первой группы входов элемента И, входы входного блока инверторов соединены ссоответ-г ствующими выходами блока преобразователей число-вероятность, а выходы с соответствующими входами второй группы входов элемента И, вь1ход которого соединен с запрещающими входами первого и второго элементов ЗАПРЕТ, выход первого элемента ЗАПРЕТ соединен с управляющим входом блока динамического запоминания устройства, а выход второго элемента ЗАПРЕТ - со входом счетчика, t На чертеже представлена блок-схема устройства. Устройство содержит блок 1 динамического запоминания, вход 2 управления блока динамического запоминания, первый элемент ЗАПРЕТ 3, генератор 4 тактовых импульсов, генератор 5 случайных чисел, счетчик 6,запрещающий вход 7, первого и рторого логических элементов , первый блок 8 ключей,блок 9 преобразователей число-вер|оятность, блок 10 регистров сдвига, второй элемент 11 ЗАПРЕТj второй блок 12 ключей, блок 13 умножения, блок 14 сложения, блок 15 интегрирования, третий блок 16 ключей, блок 17 задержки, первый 18 инверторов, элемент И 19, второй блок 20 инверторов, Выходы блока 1 динамического запоминания соединены с выходами первого блока 8 ключей, выходы которого соединены с входами блока 9 преобразователей число-вероятность, выходы которого подключены к входам второго блока 20 инверторов и к входам блока 10 регистров сдвига, выходы которого соединены с входами второго блока 12 ключей, выходы которого соединены с входами блока 13 умножения, выходы которого подключены к входам блока 14 сложения, выходы которого соединены с входами блока 17 задерж ки и с входами блока 15 интегрирова ния, выходы которого соединены с вх дами третьего блока 16 ключей, управляющий вход которого соединен с равляющим входом второго блока 12 ключей с выходом счетчика 6. Выход генератора 4 тактовых импульсов сое динен с управляющим входом первого блока 8 ключей, входом синхронизаци блока 10 регистров сдвига, с разрешающими входами первого и второго логических элементов ЗАПРЕТ 3 и 11 и с входом генератора 5.случайных чисел, выход которого подключен к уп равляющему входу блока 9 преобразователей число-вероятность. Выход пер вого логического элемента ЗАПРЕТ 3 соединен с входом 2 управления блока 1, а запрещающий вход - с запрещающим входом второго логического элемента ЗАПРЕТ 11 и выходом логического элемента И 19, первая группа входов которого подключена к выходам первого блока 18 инверторов, входы которого соединены с выходами блока 17 задержки и с входами блока 13 умножения . Вторая группа входов логического элемента И 19 соединена с вы ходами второго блока 20 инверторов, входы которого подключены к выходам блока 9 преобразователей число-вероя ность. Выход второго логического эле мента ЗАПРЕТ 11 соединен с входом счетчика 6. Устройство работает следующим образом. По первому импульсу (такту) из генератора 4 тактовых импульсов, пер вые п чисел (1 1,2. л.п) через первый блок ключей 8 передаются на блок 9, состоящий из п преобразователей число-вероятность, где осуществляется их преобразование в бинарные случайные символы (О или 1) с вероятное тями появления, численно равными вел чинам соответствующих преобразуемых чисел р)-. Эти символы далее записыва ются в первые разряды каждого из празрядных регистров сдвига блока 10. Одновременно в счетчик 6 емкостью п добавляется единица. По следующему такту генератора тактовых импульсов на выходы блока 1 поступают п чисел ti: (j l,2,.,n) которые после преобразования в блоке 9 преобразователей число-вероятность записываются в О6 виде вероятностных отображений в пер вые разряды каждого из регистров сдвига блока 10, причем ранее написанная в них информация передается во вторые разрядь регистров. Содержимое счетчика 6 увеличивается на единицу. Этот процесс длится до тех пор, пока п не будут заполнены все п разрядов регистров блока 10 регистров сдвига, причем ранее записанная в них информация передается во вторые разряды регистров. Содержимое счетчика 6 увег личивается на единицу. При этом происходит переполнение счетчика 6. По сигналу переполнения осуществляется передача содержимого регистров блока 10 на блок 13 умножения. При этом как и в схеме известного устройства происходит реализация зависимости .«, W (О номер итерации; значение корня системы линейных алгебраических уравнений п-го порядка; t-j приведенные коэффициенты этой системы. Результат каждой итерации записывается в блок 15 интегрирования, где происходит статистическое усреднение, поступающих бинарных символов в каждои итерации и, таким образом, за К итераций вырабатывается несмещенная оценка корней Х- системы алгебраических уравнений. Очевидно, что время вычисления этих оценок равно Т Kni(2) де t - длительность тактового интервала генератора тактовых импульсов. Появление сомножителяfn)в ( 2)свяано с необходимостью заполнения реистров сдвига в блоке 10. В предлагаемом устройстве время ычислений существенно снижается за счет того, что не в каждой итерации требуется полного заполнения регистров сдвига в блоке 10. Действительно как видно из (l ) в случае, если все отображения и 0, то X 1) 0, и таким образом ясно, что дальнейшее заполнение регистров лишено смысла и можно перейти к следующей итерации, т.е. снова преобразовать /i в бинарные случайные символы. Если в этом случае вероятностные отображения оказываются нуле.выми, то вновть итерация завершается .после одного такта генератора тактовых импульсов и т.д. до появления хотя бы одного ненулевого вероятностного отображения из вектора fe . При i;3TOM если все отображения . 0 и отображения fJ- 0, то на выходе л гического элемента И 19 присутствует сигнал - логическая 1, который по за прещающему входу 7 первогои второго логических элементов ЗАПРЕТ 3 и 11 п пятствует перемещению информации в блоке 1 динамического запоминания и добавлению приращений в счетчик 6. Формула изобретения Вероятностное устройство для решения систем линейных алгебраических уравнений, содержащее последовательно соединенные блок динамического за поминания, первьш блок ключей, блок преобразователей число-вероятность, блок регистров сдвига, второй блок ключей, блок умножения, блок сложения, блок интегрирования, третий бло ключей, выход которого является выходом устройства, счетчик, выход которого, соединен с управляющими входами второпо и третьего блоков ключей, генератор случайных чисел, выхо которого соединен с управляющим входом блока преобразователей число-вероятность, генератор тактовых импуль сов,, выход которого соедине;н с управ ляющим входом первого блока ключей, входом синхронизации блока регистров сдвига и входом генератора случайных чисел, блок задержки, входы которого соединены с соответствующими выходами блока сложения, а выхо,чы с соответствующими входами блока y iнoжения, отличаю.щееся тем, что, с целью увеличения быстродействия, оно содержит первый и второй блоки инверторов, элемент И, первый и второй элементы ЗАПРЕТ,разрешающие входы которых соединены с выходом генератора тактовых импульсов, нходы первого блока инверторов соединены с соответствующими выходами блока задержки, а выходы - с соответствующими входами первой группы элементов И, входы второго блока инверторов соединены с соответствующими вькодами блока преобразователей число-вероятность, а выходы - с соответствзпощими входами второй группы элемента И, выход которого соединен с запрещающими входами первого и второго элементов ЗАПРЕТ, выход первого элемента ЗАПРЕТ соединен с управляющим входом блока динамического запоминания устройства, а выход второго элемента ЗАПРЕТ - со входом счетчика. Исто 1ники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР № 481042, кл. G 06 G 7/34, 1975. 2.Авторское свидетельство СССР , кл. G 06 F 15/36, 1978. 3.Авторское свидетельство СССР № 629541, кл. G 06 G 7/34, 4. Федоров Р.Ф., Яковлев Добрис Г.В. Стокастическйе преобразователи информации. Л., Машинострохвние, 1978, рис. 123 (прототип).