Устройство для приведения матрицы к треугольной идемпотентной форме Советский патент 1987 года по МПК G06F17/16 

i l.iu6j)l l4 iMl. l/IHlAiliOl К Hl)14IU-,ifH4-.:ibllOH

rcMiHKf It 11|Н Л,н;1зи;.1че1И1 для |чм1км1ия систем .линеииых у|)авиений, оиред(.|еиия ко фipilUHCI: гон , liilk iiliOr O О.ЧНОрОДИО i Н.ИЮСГИОН) уравнения, (определения кода ДДдюсле- д)ате, 1ьн()гти.

lU .ib изобретения - повышение быстродействия.

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

ячейки намяти; на ())иг. 3 пример выпо.- блока у||рав.1ення; на (f)Hi. 4 временные isiai раммы раоогы упройсгва; на . Г) fipiiM( .. Mi (Лции блока )а .i6ua, iiefiec ав.тяемосо с не) сто.тбЦ|)М.

N cTpoiiciBo для н)ив1мения матрицы г- т|н 1ЧЛ1Д10И мдемпогсн гной (fiopMe содержи б.ток I ввода HFHJiopMainiM, ДРи)ич- нун) матрину 2, блпк Л памяти, ячейки 4 памяти, причем чпс,-|() ячеек 4 памяти в составе мат|)ииы 2 равно пг. а в составе блока памяти Лт. блок Г) Bi i6opa сголбна.

пер1ч га1), 1яемо| о с первым сто,тбпом, комму- Farop ti входов ячеек 4 памя1И первою cTo;i6- пл ;,1емен1 ИЛ 11 7, in ofioii б,чок 8 (лемонгов И, третий б.юк ( :)Лементов И, 10 ун- р; в,1епия, б,1()к II инверторов, iiepiii.m б.ток } 2 ).-|сментов И, :),-|еменг H. IH-Iifi 13, блок 14 i .i,;B:i,i; репкмшя.

И ;(Н-та ячейки 4 памяти входят комму- raTijp I), .н. мент If) 1ЫМЯ1П, :)леме11Т И 17, (лмматор 1 S по модулю два, первый 19, вто- poi i 20 и гретий 21 ин(()ормапиоп П)1е входы, nepiii,ui 22, 23 и 1р(чпй 24 уп|)ав, 1ИК)- пии и.),|ы, вхо,т 2Г) аписи, б,токирои()чный вхот 2(. и .ыход 27.

Г),1ок 1(.1 т1рав, содержит третий 28, пятьи 29, nepBi.iiF .30, BTopoii 3 и четве ь гый ,32 В1.1ХОДЫ, вход 3.3, ieiie|)aTO) ,34 тактовых им11у. 1,сов, первый 35 и порой 3(i трип-еры, третий И ..7, счетчик 38, трегий грипч р ,3.1, -л1емет 40, 11е)вый 41 и второй 42 э,пименты IIfxioK ) выбора сТ1),|бца, пе|кч 1 ав,|яе.мого с первым CT(j,i6HoM, oдepжиг itn-li эле- мепгов HI: 43, (/ - 1) :,1емептов М 44, (/п-1) . К ментов ИН 4Г, ) :1.|с-меитон II 46, 1П-2 э,теметов 111: 47, (гп-2) элементов И 48, (ГЦ -1) j,ieMeiiro i И 49, (/«-1) элементов ИЛИ Г)0. :.и-мепт ИЛИ 51 и элемент И.:1И-111-: 52.

cтpoйcтвo работает с.тедующнм образом.

.v (, гройс тво д,1Я приведения матрины ; |)е 1ч. ;ы1(,ч | H.it Mno:ентной ()орме поз- .1о.1Яет определить .чмпепие Z системв //; и1неГиН)1х ypaiuKMHin с in неи; вестными вида /ч ;; , I де а задаппая niXf i матрина; : .адан1П)1Й //(-мерный вектор-строка.

1 на к; момент производится уста- . i. i i , . iiiop. 1 памяти двоичной матри- iU i 2 и б.юка 3 намяти в нулевое состояние, 1 ()П1 I ера 3) б, 1ока И) управ,тения в единичное

С(к-гояние, ipHiiepoB 3() и 39 и счетчика 38 б, и)ка 10 управления в нулевое состояние (цепи установки не показаны). Во время дейс1 вия единичного потенциала на первом управляющем входе 22 с вт)1ходов блока 1 ввода информации в ячейки памяти 4 двоичной матрицы 2 но входу 19 записываются 0.1, п заданные для всех /, п , 2, ..., т, а в ячейки намяти 4 б.тока 3 памяти гп-мерQ ный вектор-строка L .

Задним фронтом импу,тьса триггер 36 устанавливается в едипичное состояние, эле.мситы И 41 и 42 открываются но первым входам, и начинаегся процесс приведения матриць к треугольной идемнотентной фор5 ме, во Ефемя кото()О1 о при наличии единичного потенциа.та на гретьем выходе 28 б.юка К) управления на выходе 32 и.меет место ну,1евой нотенпиа,., при :)1Ч)м сигнал на выходах 27 ячеек памяти 4 соотве тствует сиг на,чу па выходах ч.тементов 16 намяти дан ных ячеек 4 намяти, и па входы блока 5 выбора сто.тбца, перес1авляем(лч) с первым столбцом, нодаются сигна-ты с выходов 27 ячеек памяти 4 iiejiHosi строки двоичпой матрицы 2 и с выходов диагопальных ячеек 4

5 памяти двоичной матрицы 2.

Б,.1ок 5, имеющий гп выходов,онреде.шет сто,;|бец, который необходимо переставить с первым сто.тбцом, но с, 1ед Ю1цему п 1инци- пу: если на выходе 27 ячейки 4 памяти первой строки первого столбца двоичной матрн0 нь1 2 имеет место единт1чный потенциа., то единичный п(ггенциа;| фо(1мируетсй на нер- во.м выходе б,:1ока 5 и на выходе, номер которого соответствует номеру самого левого столбца двоичной матрицы 2, в котором на выходах верхней и диаго1|а,11)НОЙ ячеек 4

5 намяти имеют место соответственно единичный и нулевой поте1П1.иа. 1ы, а н)и отсутствии такого столбца едииичный ситна,: форми- )уется иа первом выходе б, 1ока 5 и на выходе, номер KoTopoi o соответствует номе()у самого левого сто,чбца двоичной матрицы 2, в котором на выходе верхней ячейки 4 намяти имеет место едипичн1,1Й нотенцнал. Данный алгоритм рса.1изован с помонт1,ю схемы блока 5 (фиг. 5). Ири на.тичии едипично1о потенциала па вь1ходе яче11ки 4 иамяти пе)вой

5 строки iiepBoi O столбца дтюичной .)1 2 единичный сигнал форми)уется тсх и.ко на нервом выходе б,.1ока 5, так как на выходах элементов И 46, И, 1И-И : 52 формируются нулевые сигналы за счет блокировки входов эле.ментов И 46 ннверсным си1на,.-1ом с выхо0 да ячейки 4 памяти первой строки первого столбца двоичной матрицы 2. Ири нулевом выходе верхней ячейки 4 памяти иервого столбца двоичной матрицы 2 при наличии столбцов с единичным выходом вс-рхней ячейки 4 намя 1 и и нулевым выходом диаго5 иа.чьной ячейки 4 памяти двоичной матрицы 2 единичные нотенциа.чы формируются на выходах тех г,. 1ементов И 44, входы кото рых подключены к выходам данных стс лбцов.

0

а с помощью элементов . 45 и элементов 11 4в слииичный 11()14 ппиа.1 формируется только на выходе roio улемеи и) И 4(i, вход ко1())И)го чер1М ълемеш И 44 соединен с ну- .|евым и единичным выходами верхней и диагональной ячеек 4 намяти крайне1Ч) лева1() столбца, ири на выходе злеменга ИЛИ- HF. 52 формируетея ну.певсп потенниал. б. ю- кирующий элементы И 49, а единичн1)1Й ио- генциал формируется только на выходе кио элемента ИЛИ 50, номер которого соответствует номеру крайнего .leisoi o столона, кото- необходимо иересгавигь с первым столбцом.

При отсутсгвии столо и1 с едииичным выходом верхией ячейки 4 намяти на Eiijixo.ie :;.1еменпа ИЛИ-ПН 52 формируется едииич- ный нотенциал, и с помощью члеменгов 111. 47 и И 4)S осуик ствлястся ({)орми1)оиаиие единичн()|ч) iu)TeHiuia.ia на выходе того 4.:к - менга И 4)Н. который неиосредственно соединен с единичным выходом верхнего . le мента 4 памяти крайнего .leBoi o сго.и )ца двоичной матрицы 2. Данный единичн1 1И нотенииа. иередается чере: соогвегс вую- шие .чементы И 49, ИЛИ 5() и 51 на иерв1)1Й выход б.чока о и на тог выход, номе) которо- 1() еоог1 етствует крайнему :1евому сто.пбиу, KOTOpbiii необходимо иереставить с первым сто.чбцом.

Ири отсугсгвии K)aiinei4) левого с голбца cor. iacno приведенному а.1горитму па Bct-x Biiixo;iax б.юка 5 формируюгся иу.аевые по- тепциа.:1Ы.

Иусть в пача.тьный момент обработки .(аписаипо1( ииформации крайним левым сто. 1бцом двоичной матрицы 2 яв.чяегся .:)К)- бой не первый сто.тбец двоичной матрицы 2. В JTOM случае иа первом В1 1ходе б.чока 5 и на одпом H;i 2 т выходов блсжа 5 сформируются единичные нотенниалы. На.шчие единпчного потенциала на 2ч- П в1)1Х()дах б.юка 5 приводит к (((ормированию единичного погепциа.ча па выходе -лчемепта И„ЧИ 7. Лаппый сигиа.ч подается на б.локировочный вход iii б. кжа 10 упра15.:1ения, нри том на выходе j.ieMenTa И 41, а с.чедовате.1ьно, и на выходе 2 б.чока 10 уп)ав.чения формируется единичиый гютенциа.ч, на выходе .че- мента И 42 (на выходе V2 б,чока управления)иу.чевой потенциал, а на счетшлй вход счетчика 38 блокируегся постуг1.че1ше I актового имиу.чьса. С приходом имиу.чьса на вход 25 :и1циси в ячейки 4 намяти nepBoi o сто.чбпа двоичпой матрицы 2 и б.чока 3 памяти строки ио входу 20 осуществ.чяется по- сгрочпая перепись информации и: ячеек 4 памячи то1() сто.чбца, который соответствует выбранному крайнему левому, а в данный крайни) .чевый столбец нроизводитея но- сгрочпая И11фо(1мации и;( первого сто.чбца двоичпой матрпцы 2 и б.Ц)ка 3 памяти. В ячейках 4 намяги осга.чьн1)1х сго.и )- 1U)B двоичной матриць 2 и б.юка 3 памячп пнформапия в данном такте осчается бе ч

0

0

0

5

0

5

и:и1еиения. 1ос.че перениски И1ц|и)(1мации на выходах б.чока 5. а с.чедовате.чыю. па В1,1ходе э.чемента ИЛИ 7 имеет место Hy.icBoii потепциа.ч, при единичиы) по- ченнна.ч имеет место на выходе .чемеига И 42 (на выходе 32 б.чока Ю .цм1ия), а па выходе элемепта И 41 (на выходе 28 б.юка И) управ.чения) ну.чевой нотенциа.ч, на вторых управляющих входах 23 ячеек 4 памяти в момепт имеет место ну.чево11 1И)тепциа.ч, а па третьих уирав.чяю- ших входах 24 ячеек иамяти 4 едипичпьи noreinina.i. 1Ь.чок 9 :1.чементов И формирует единичный потеициа.ч па гех выходах, номера которых соотвечсгвуют номерам сто.чбцов двоичпой мачрицы 2 (KJIOMC первого сто.чбца). в когорых в данный момепт па выходах 27 верхних ячеек 4 памяти имеет меето i uiini4Hbiii иотеьциа.ч, нри том в ячейках 4 памяги ка/кдо11 строки 2-rin сто.чбцов про- И-1ВОДИГСЯ суммировапие по моду.чю два содержимого :1.чемепта l(i памяги данпо) яче11ки 4 намяги с выходным сигна.чом ячейки 4 памяти даино1( строкн нервого сто.чбца. .чо1ически перемпо/кепп1)1м с сигпа.чом иа б.ижировочпом входе 2() данпо11 ячейки 4.

С. приходом гактового имиу.чьса па вход 25 запи.си в яче11ки 4 памячи по третьим П1и|1ормапиопн1)1м входам 21 записывается 1П|формация с выходов 27 других ячеек 4 памяти (вход 21 ячейки 4 намяти /-ой ст11оки /ч о сго.чбца двоичной матрицы 2 соедииен с В1 1ходом 27 яче11ки памяти /+1-Й строки f I I ло сто.чбца двоичной мачрииы 2). Одновременно данньи raKroBbiii импу.Ч1)С посту- паег на C4erHi,iii вход счетчика и иод- счигывается. Таким образом, при па.чичпи крайп(Ч() .чевого счо.чбца в 2--ni сто.чбцах двоичной матрицы 2 одпократпое выпо.чпе- inie базиси1 1х onepanni t а.чгоритма приведе- пия магршИ) к трсу1Ч1.чьпой идемгютептиой 1|)орме осушесч вляетсм за два времеип1 1Х пи к.) а.

В с.имующи) момепт краЙ1Ц|м .чевым его.|бцом яв.чяегся первый сто.чбец двоично) ма1 1ИЦЬ1 2 .чибо крайниГ) .чевый его.чбец вооби1е отсугствует. В уч ом с.чучае на выходах б.чока 5. а с.чедовате.чьпо. на вь1ходе .чемента ИЛИ 7 и па б.цжировочном входе б.чока 10 управ.чения имеет месю ну.чево) потенциал- Иа вь1ходе .чемеита И 41 (выход 28 блока уцравленпя) формируется иу.чевой иотенциа,, а иа В1 1ходе .чемента И 42 (выход 32 б.чока унрав.чения)едипичн1 и) потенциа.ч.

Иа вторых управ.чякмцих входах 23 ячеек 4 памяти в дапиый момепт имеет месчо иу.чевой потеппиа.ч. а на Tpennix управ.чяю- 1ЦИХ входах 24едшшчпьи) поте)|циа.ч.

Б.чок 9 э.чементов И формирует едииичш.п) нотециа.ч па тех выходах, номера которых соог етсгвуют 1П)ме(1ам сто.чбцов двоичпой мач рпц| 1 2 (кроме первого сто.чбца), в ко- в данньп) моменч на выходах 27 liepx- iHtx ячеек 4 памяги имсеч место едипичн1 1Й

потенциа., при УТОМ в ячейках 4 памяти K;i/K,UHt строки столбцов производиюя )()ваиие ио модулю два содержимого :), 1С меита И) памяти дайной ячейки 4 памяти с выходным сигналом ячейки 4 иамяти дан- иой сгроки первого столбца, логически пере- множенн1)1М с сигна.чом на блокировочном входе 26 ячейки 4 иамяти.

С приходом очередного тактово1ч) им- iiy. на вход 25 записи в ячейки 4 памяти по третьим информационным входам 21 (аиисывается информация с В1 1ходов 27 л.руг их ячеек 4 памяти.

()диов)еменпо данный тактовый импу. цл поступает на сч1 тный вход счегчика 38 и нод- СЧ1Г1 ыиается.

Таким o6|)a:u)M, если крайним левым сюлоним .авончной матрицы 2 Я1 лнегся iie)- itbni ск. лбец и, Hi крайни левьп сголбец li данный MCJMein отсутствует, (.)днок)атное выполнение базисных операций алгоритма приведения ди(Л1чп()й матрицы 2 к греуголь- Hoii идемнотен гной форме осуп1еств. 1яется (а один ире.мепной цпк.л.

Дпалогичпо в с.тедукицие мо.менП) врс - меии между такгопыми имну.ия ами при наличии крайнего .ченои) сю.чбца н нервом сюлбце двоичио матрицы 2 либо при от- схтсгвии крайнего .тевого столбца од11ок1)ат- пое выпо. шение базиспых (не)аций црине- двоичной матрицы 2 к треугольной ггчемноген rHoii ((юрмс осушесгв-тяется за o.uiii iipi MeHHoii цикл, а при па.тпчпи крайнего .;ено|(1 сго.лбца ио сто.тбцах двоич- ггой магрицы 2 за два в|)еменгп 1х цикла, Г1|)и в процессе однократного вьгнолпе- ния базисных операций счетчиком 38 под- считьк аегся одип такговый импу.тьс.

Приведение мат1)ицы к треугольной идем- готентной фо)ме осугцеств.ляегся в резу. га ге /«-кратною выпо.тнения базисп1 1х опе- рацнй в процессе подсчета счегчиком ,38 т 1актовьгч имиу.чьсов. Ьсли в 1Г)оцессе при- ведегп1я матрицы крайпим ,евым сто,тбцом (кчм да ив,чяегся 1гер1и гй cio, i6eri .чибо к|)ай- ГП1Й , столбец, ,чибо к|)айгп|й левый сто.лбец огсу гсл вуег, TCJ п)иведепие мат|)и- пы 2 к I реуголг,11ой идс миоген rriori (()орме псугщ с Г1.ляегся за гп вр1 менных цик.чов, ес.ли краГгни.м леиГ)1м счо.лбцом всегда яв,чя- ск я , 1Н)бой из 2- . Гп столбцов, то ириведеппе ov v щесгвляелся за 2//; временных ruiK, ia.

В общем п 1иведение матриги 1 к 11)С у1о.1Ы1ОЙ идемпотентпся ( оеу- 1Гач1 г ляется ,:а 2. И -р )емепных цик.ла (11(} - 1П соотие: С1 Byei чис,лу с.лучаев, когда 1 роцес1 е ВЫГК1, iiicHUM базисньгх операций кра1гпим .левым сго.лбцом яв,1яегсн первый мГм) к|)а{гнпй .левг,1Й столбец в данньг1| момент отсутствует), 1грактнческп за (I, ,3-i- :-1, 7}in времен1п,гх цикла.

В результате ириведения двоичной мат- )иг;ы 2 к т)еу1о,льной идемиотентиой форме в блоке ,3 памяти формируется некоторая строка, являющаяся одпи.м из решений Z системы т линейных уравнений с т меиз- 1 естными вида Zot //. Пос.ле подсчета счетчиком ,38 т тактовых импульсов иа выходе счетчика формируел ся перепад, устанав.ли- ваюи1ий триггер 36 в пу.левое состояние, а тригтер 39 в едипичное, при этом выполнение базисных операций нрекрап1ается, первьгм тактовым импу.чьсом с выхода гене- )ат()ра 34 триггер ,39 усланавливается в ну- .левое состояние и па выходе 29 б,лока I O формируется сигиа.л вг,1вода реик ния, при JTOM |)еп1епия в б,локе осу|цеств.ляется при ус.ловии отсутслвия единичного сигна.ла на вьгходе .лемента П, 1И-ИР-; 13.

20

Формула илопрегения

. Устройство для приведеиия матрицы к треуг ольно идемг1оте1гтпой форме по авт. св. № 1288714. отличающееся тем. что, с це,льк) повыгпепия быстродействия, в irerx)

вгн ден tf/ioMenT И, 1П, выходы Koropor j соединены с второг с.) 1ГО т-н В1)1ходами б.лока выбора сто.лбна (т ко.шчество базисньгх онераций), выход :)лемеита П.-Ш соедииеи с б.локировочным входом б.лока управ,ленпя. 2. стройство но н. I, отличающееся тем, что блок у(1ра(,ления соде)жит генератор тактовых нмну.льсов, нерЕИ.гй, )й и л )е- ЛГ1Й тригт ерьг, нервьгй, второй и третий :,ле- меит1)1 И, ,лемент 11Н, счетчик. н)ичем вход установки в «О третьего триггера соединен с 1гервым входом третьего элемента И, с входом установки в «О нервого тригге)а, с выходом геиератора тактовых импульсов и яв- .ляется нервым выходо.м б,лока управления, вьгход т)И1Л ера соединен с входом устано1)ки в «I второго лрнггера и является

вторым выходом блока управления, выход второго триггера соединен с вторым входом третьего э,леме11та И и с первыми входами первого и втор(и (.) (.чементов И, вг,1Х()ДЬ| которых являются соответственно третьим и четвертым выходами б.лока уирав.лепия,

второй вход первою члемеита И соединен че)ез :).лемент ; с вторым входом второго .лемента И и с т|)етьим входом третьего элемента И и является блокировочным входом блока уг1рав,ления. выход т)етье|() :(ле- мента И подключен к счетному входу счетчика, выход переполнения которого подк.лю- чеп к входу устаповки в «О второго триг1е)а и к входу устаповки в «1 третьег о триггера. В1)1ход которог о является пятым вьгходом б.лока унравлепия.

28 32

29

Фиг.

Фиг. 5

1 LionctcTiMiHO отпосигоя к об,:к1сти числительной техники и нре.ша.чна нмю .тля решения систем лине1(иы ура(нени11, онре- .Ц ления ко:(({к})иние11тои .iHiieiinoiо одиоро.г ного ра: иосгиого уравнения, опре.телення ко.та М-иос. 1ед(жате,1ьн()сп и. Це,1Ь изобретения иов1 1И1е11ие )действия. VcTpoii- ство содержит блок 1 ввода информации, inXni дпоичнук мат|1ииу 2, блок памяти ii, яче(|ки памяпи . причем чис,и1 ячеек иамя- 1н 4 в сси таве митриць 2 раши) «г. а в составе б,тока памяти Л равно tn. блок 5 выбора cTO,:i6na, перестраиваемогч) с HepuL iM стсхпб- иом, коммутатор 6 вхо.тов ячеек памяти 4 iiepBoi o сюлбца, члеменг И, 1И 7, б,чоки э,1е- ментов 11 8, 9, 12, б,ток И) унрав.чения, б,ток II HHiiepiopoB, ll. llMIl- 13, блок 14 вывода рен1ения. В yerpoiicine иск.тючаются операции Пересi ановок его.чбцов, когда Kpaii- ним .к-вым столбцом яв. 1яется iieiMtbui стол- беи И.П1 кра1и1И11 .leHbiii столбец вообще от- cyii TByei , что но:ии)ляет достигнуть цели и (обрс теиия. I ;t. и. ф-,1Ы, 5 и.1. (Л Ыы;; га No . I