Методи та засоби випадкового тестування дискретних пристроiв тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

1 АВГ US'*

Национальна ахадсхьч наук УкраТки 1нстйтут kí б ер нетики ímchí В. М. Глушкова

На правах рукопису

БАРАШКО Анатолш Сергшович

МЕТОД И ТА ЗАСОБИ ВИПАДКОВОГО ТЕСТУВАННЯ ДИСКРЕТНИХ ПРИСТРОТВ

01.01.09 — математична к1бернетика

Автореферат дисертацп на здобуття наукового ступеня доктора ф13ико-математичних наук

Khïb 1994

Дисертац{ею е рукопкс.

Робота виконана в 1нститут1 прикладно! математики i меха-шки HAH Украши.

Оф1ц!йн1 опоненти: доктор фвико-математичних наук, член-кореспондент HAH Украши ЛЕТИЧЕВСЬКИЙ О. А.,

доктор ф1зико-математичних наук, професор ЛШЬКОВ Ю. М„.

доктор техшчних наук, професор РОМАНКЕВИЧ О. М.

Провщна оргашзащя: 1нститут математики HAH Украши.

Захист в1дбудеться 199^ р. о -И--

годиш на зааданш спещал!зовано1 вчено'1 ради Д 016.45.01 при 1нститут1 ибернетики iMeHi В. М. Глушкова HAH УкраТ-ни за адресою:

252650 К,и\'в МСД 22, проспект Академша Глушкова, 40.

3 дисертащею можна ознайомитися в науково-техшчному apxißi шетитуту.

Автореферат розклано >ZiMAVtS.— 1994р.

Учений секретар спещал!зованоТ вчеио! ради

синявськии В. Ф.

ЭАГА;.ЬНА ХАР-. .ЭРИСТИКА FOBOTH

Актуальн!сть теми. ЗсЛльшення складност! дискретних пркстроТв СДП) .викликане прогресом кИсроелектроююТ тех:-:1ки,призоеяо до ус-кяаднеаня процэсу ix контролю. Традиц1йкг детермшозгн! кетоди генерацп тест1в для сб'ект1в контроля з пам'яттр виязияис<г за-надто трудом юткими 1 великий обсяг обчислень vacro не дсзвояяе одераати задов¡яьн1 результата за прийнятний терыШ. У зв'яэку з цкм £Св б1льшу популяршсть знаходять недетеркшосан! метода контролю, як! використовувть для вх I дких стимул 15 на випробувану схему випадкову ado псевдовипадкову посл!дови!сть велико! довхини. Для ОЦ1НКИ в! "доз !дей об'гкта контролю на вх;дн! сткмуяи вшссрк-стовують р!зн 1 методи. Найб1яьш простим,але таким.що потребуй великого обсягу додаткового обладнання,с метод пор!вняльного тестування, коли в процес) тестування вх!дн1 набора подагться одно-' часно на об'ект контролю I на так званий золотой пристрШ.яккй язляе собой справку копщ Еипробуваног схеми. На основ i пор [зияния в1дпов!дей об'екта контролю 1 золотого пристрою робиться вп-сновок про справШсть першогр. Методи компактного тестування,що доз^оляитъ уникнути використання золотого пркстроп,базуються ка стисненн! з1дпов!дей об'ект!в контролю в деяку компактно форму, з якоТ можна эдобути необх!дну. !нфорыади> про справзисть пристрою. При компактному тесту?анн! як стискувч! функц1 г найбгльш широко використовуються статистичнI методи та сигаатурнкй анал!з. Теор1я цих двох п!дход!В 1мов1рн1сного компактного тестування CIKT) недостатньо розроблена в науков1й л!тератур!. Дисертащйна робота,в основному, присвячена доел |дзсенна ыатематичних пхтачь, пов'язаних э розробкою та ouihkod нових статистичних метод1в контролю ДП,а також з проектуванням оптимальних виносно выявления помилок сигкатурних акал1эатор!в С САЗ.

Мета робота. Створити новиЯ надрямок теср:! дотермтогаыгх автомат:в,який дозволив би з единих позишй гид ¡Яти до anz.ni и у ¡скувчих.розробки та ошнки нових статистичних метсд!в рояшзна-занят яБТОмг'Пз.що прийнят! за математлчь-i модел! ЛП.

Ка 6aal л!н1йних посл!довн1сних машин СЛПМЗ розробити оснозй теорП оагатоканальних сигнатурних анал1затор!в I зэпропонузати едину Mlpy ix якост1,що дозволила б вид 1лито клас оптимальних СА, як; добре виявляють почилки у зипадку.цо ка:!б;льш часто эустр;ч?.--

еться на практищ,коли про розпод!л !мов!рностей появи помилок к!Ч0Г0 Кб в ¡доме.

Дсол1дита клас несправностей.що виявляеться при трШковому коделсванк!, I встановити трудом 1стк!сть 1х виявлення,яка вим Спеться функц'ею !мов1рност! виявлення в1д довжини випадково! по-сшдоькост! нзбор1в. Запропонувати простий алгоритм випадково! вебудоаи тесту для виявлення поодиноких когстантних несправно-стей в схем 1,що моделюеться.

Методика доел |дуння. В дисертац1йн1й робот! використовува-лись методи теорп ск!нченних детермшованих та 1мов!рн1сн»л ав-томат!а, ЛПМ, теорп кодування,теорп шов ¡рностей, теорП матриць, скшчекких лакцепв Маркова,функцЮнального анал!зу,статистично1 теорп розп!знавання образ1в, л1н1йно1 алгебри та техшчно! д!аг-востики.

Наукова новизна дисертацп полягае в наступному: створення нозого напрямку теорп скшченних детерм1нованих автомат ¡в,ио дозволяв з единих позицШ п1д!йти до анал!зу юнуючих та розробхи I ©тики нових статистичних метод 1в розшзвавання автомат 1в,прийнятих за математичну модель ДП; росробка основ теорП СА.що базуеться на теорп ЛПМ I вклвчае -осл1дяеиня специф'чних питань.як! не знайшли воображения в за-гальк!й теорп ЛПМ ! стосувться виявлення помилок в посл1довно-стях,що анал1зуються;

ро-робка единоI Мфи якост! багатоканальних СА.на основ! яко! виз качено клас оптимальних сигнатурних анал1затор!в,здатних добре виявляти помилки у випадку.коли про розпод1л 1мов1рностей 1х появи Н14ого ке в1домо;

розроика методу проектування оптимальних багатоканальних СА з урахузаннга 1х швидкодп.

ДоотовIшIсть результатIв. Результата роботи оформлен! у виг-ляд! ыатематичних творджень ! теорем, доведения яких повн1 I Ыд-довиаить сучаеноыу р1внп строгост1 щодо математичних доведенъ.

Теоратичнб та практична значения. Робота мае теоретично-прак-тичний характер. В Н1Й створено новий напрямок теорП ск!нченних автомат!в,де до г,': жуються 1х статистичн! властивост!. Розроблено оснопа» т-аориг С., : одержано результата, як I дозволяють глибше зро-?у»1тя' прсщесич АЛ; в'1дйувапться. при стисненн1 посл1довностей,цо

«эувтъея, в сигнатуру,-,

Б1лып1сть результат!в дисер.-аця <Зуло отримано при розв'язая-н1 задач,що мають штерпретацт з техн1ч;Пй дфгаостищ. Заоначи-мо основнI результата,як] мають безпосередне практична викорис-тання:

1) розроблен! статистичн! методи IKT можуть бут:: використан! а автоматизованих системах тестувакня ДП;

2) програыно реал1зозаний метод проектування шп"; содиочого оптимального CA зпроваджено в НД1 Науковий центр и. ?оленограда;

ЗУ лрограмна реал!зац!я методу нашвавтоматичнот побудови контролю тих тес г ¡в з використаняям випадковях скгкал!в у склад! аьто-матизоваког систем моделювання I д!агностування (АСУ.1Д) впрова-джена на ряд1 шдприемств м.Саратова.

Апробащя роботи та публжацп. Результата робота допев )да-лися 1 обговорювалися ка р!зних наукових конференции,симпозиумах, школах-семшарах,зокрема на 7-й ВсеоовзнШ конферекц/г "Проблема теоретичноI к1бернэтики" С 1ркутськ, 19S53 , Республ 1канськItt науково-техн1чн1й конференцп "Функцюнально ор1ентован1 обчис-лювальш системи" СХарк !в, 19253,11-у Всесоюзному семшгр! з дискретно I математики СМосква.МДУ, 19873 .семшар! при МДУ за тестами П1д кер1вництвом чл. -кор. АН СРСР С. В.Яблонськсго (Москва,МДУ, 15873,наукозо-техн1чному сем1нар1 "1мов!рн1сн1 м&тоди тестувакня цифрозо! апаратури" СМ1нськ, 1987) ,б-й М1жнародя1Я конференцп. "Сснови теорп обчислень" СКазань,1987),сем1нар| при Казанському держун!зерсктет] з 1мов!рн1сних автомат 1в п!д кер!вництвом проф. Р. Г, Бухараева СКазань, 1988), 1-й зимовШ школ!-семшар! з метод 1в 1 систем керування обчислювальними I контрольно-вимфювальними комплексами С Саратов, 19883,6-у Юянародному симпозиум! з tcxhi-4HOI д ¡агностики IMEC0 ТС 10 С Прага, 1989), 12-й М1жнародн!й конференцп з в!дказост!йких систем i д!агностики FTSD - 12 (Прага,1989),11-й Всесоюзна конференцп з проблем теоретично! к.'бер-нетики (Волгоград,1990), 11-й м!хвуз!вськ1й школ!-сем1нэр1 з метод 1в та sacodlB техн!чноГ д1агностики (Гвано-Франк1вськ,1992).

У повному обсяз! матер 1али дисертаЩйно1 роботи допов!далпся ^одержали позитивну ощнку в 1нститут1 к!бернетики 1м.В.М.Глу-шкова HAH Украгни,1нститут1 математики HAH УкраТни.в Китвському Д8рдун!верситет1 im.T. Г.Шевченка та в Кигвському пои1техн1чкоиу ¡нстатут!.

Основний зм1ст дисчртацп детально викладений у роботах И-

24]. У монограф! I С19] автором написана глава 7. Ро<5оти [1-7, 2,11-13,15-18,20-243 записан! автором самостШно.В роботах [8,10, 34 автору належать постановка задач 1 методика « розв'язання.

Структура I об'еу. робота. Дисертац!я складаеться 1з вступу, п'ятк глав.вЕСНозку,списку цитовано! я ¡тератури,списку опуйя1ко-вашк роб1т автора за томов дисертац 11, дода^ку I м ютить 268 сто-р!нок машинописного тексту.

ЗМ1СТ РОБОТИ

У зстул! до дисертац!! даеться загальна характеристика росЗо-ти та перелгчея! основа 1 науков! результата.

Глава 1. Випадкове компактне тестування методом л!драхунку

У иэрш!й глав! розроблено математичн! основи статистичного методу ПСТ.щс с1азусться на п!драхунку частоти появи у вих!днШ 1ЮСЛ1ДОВНССТ! ДП $!КС0ВЭК01 п 1дпослIдовностI (фрагменту) вшпд-Ш1Х сигнал 1ь.

За математичну модель ДП прийнято ск!нченний сильно зв'яза-ний Д5теры1нова:шй автомат. Припустимо.що на його вход! д1е ста-Пояаркий генератор кеэалежних виладкових сигнал ¡в. Ней генератор швк!ст» визначаеться стохастичккм вектором з числом компэ-нент.що дор/ваюе к1лькосг; вхщких сигнал1в автомата. Такий век-то^ назвемо вектором вх'дного розпод!лу. Задача виявлення неспра-*шост1 ДП зеодиться до задач! роэп!зназання автомат 1в !мов!рн!с-ким експерименток.

3 мето» з'ясування закону розподшу випадково! величины,що дор!эние частотI появи фрагмента у вих!дн!й поел¡довност1 автомата ,Суча розглянута ск!нченниЗ ланапг Маркова,станами якого квля-стъся так! пари: стан автомата 1 поелiдоен!сть вих1дш;х сигнал!в, доьжииа яко! зб!гаеться з довгиною фрагмента. За допомогоп цього лакцвга <Зуло доведено,цо розпод1л частоти появи ф!ксовакого фрагмента у БКХ1ДК1Я поел1довност1 задано! довжичи апроксимуетьея кормальким законоч. Осктьки число стан!в згаданого ланцега знач-но перевицус чи г,о стан!в автомата,то отчисления параметра нормального закону • ,атематичного с;под1Еанкя > дисперсп - по цьо-иу ланцагу занадчо трудом!стке. Методом укрупнения стан!в вих1д-ного л&яцвгг булс сдергано ланцег Маркова з числом стгн!в,що до-

p ¡BHDs числу стан1в авт> ,мата, 1 показана можлив 1сть обчиолення параметра нормального закону по ланцюгу Маркова з укрупненный станами.

Встановлена анал!тична залехнюгь довжкни вмпадковог посл!-довност!, що розп!знае автомата, в 1дапр1орно г ¡мсв'фносп помллки розп1знавання,граничних дисперс!й та математичних спод!закь,як|

ОбЧКСЛЮЮТЬСЯ ПО !М0В1рН0СТЯХ ПОЯВИ ВХ1ДНИХ СИГКД ч' .в ¡.функтях переход ¡a 1 виход Iв автомат 1в,що розШзнаються. Розглянемо докладные постановку задач!. Нехай

кд) - сильно зв'язаний автомат,у якого 5д=(st .....sr > - мнохи-

на стан!в, X=<xt.....х^) - вх!дний алфав!т, У - вихщний алфав1т,

бд 1 Х^ -функцИ перехода I виход1в. Кожному х^еХ ставиться у в!дпов1дн1сть 1мов1рн1сть р^ появи вх1дного сигналу х^ .причому т.

Pfo > О I Z ^ = 1. Генератор випадкових сигнал 1в характеризуемся

вектором вх1дного розпод1лу p-Cpt. Припустило,до Л£<"<4(, Аг>,де At 1 Аг - сильно зв'язан1 автомата. Для фжсованого фрагмента иеУ* (У* - множина вс!х посл!довностей в алфавгп У ск!н-чак:ю1 довжини,цо включае пусту посл!довн1сть е. нульово! довжияи) I досить великого натурального числа п розглянемо випадкову ват-

чягу v^Cv) (i=l,2),no дор!внюе частот! появи у вих1дя!й посждов-кост! довжини п фрагмента и,подо А=А^ . За допомогою центрально! гранично г теореми для ланцюпв Маркова доведено, ¡цо розпод!л ви-

падково!- величини v^Cv) апроксимуеться нормальним законом з ма-

/4,- А,- А'

тематичним спод!ванням q- чи) та дисперсию Dn'(v). Якко q Си)*

А ■

аСи),то А можна розпшати 1мов1рн1сним экспериментом I роз-Шзнаваяня вводиться до задач1 статистично1 перевфки ппстез при

заданому розподШу випадкових величин i/Yu) 1 Ли). Надал! бу-

демо вважати розпод|л випадково! величини v^Cv) нормальним.

Н^хаЯ Ли) - частота появи фрагмента и,яка одергана внас-л'|док 1мов1рнюного експерименту. Тод! у випадку.псказано«у на рис. 1,правило прийняття ршення буде виглядати таким чином:

Г г < Ли) <2 ф А = А , J » 21

1 z > Ли) ado Ли) >2 * А =А. t 2 а

Рис. 1. Розпод!л випадхових величин vjVuJ i Л1.О Якцо anplopKl iMOBipHOCTl автомат Ib сднаков!,тобтс =1/2 ,то iMOBipnють помклхи роап 1анаьанн.ч е вазначаеться р!вн1-ств е-1/25 ,де S ~ плода.цо заитрихована на рис. 1. При п. * со А А

Dnl(v^,DnZ/!v) -» О I е •* 0. Тому для дано1 величини с > 0 мохиа знайти таке л.лкэ забезпечуе цю 1ков!рн1сть пошшки розшзнаван-ня.

Эупянимось на ойчиолокн ¡ натекать лого спод геання qrCiú i ди-

cnepcii D^Cu} . Автомату А 1 вектору вхтного рогпод1лу р поставило у в1дпоз!дн!сть Шов 1рк¡CHüñ автомат CIA') dea вход1в ACp)~

=CSA,y,{XAC\fXO,yey. Кех&й X/^.y ¡ = fx^eX |

& X^fbj.Тод! для матриц! tfVyJsfm^CyJJ ir елементи 0'",Ч!!с..сг?ться за формулою

мÓ .ОО = У Рк •

Покладзмо т.^- i ffWiayj]. Якцо /4 - сильно нв'язаннй

автомат,то >г - лерех.'дна ыатркц» ергодичиого ланцюга Маркова I

L , A ¿ ,

Ючуе едкний нерухомий сто^асткчний вектор а -Са".....а^лщо

задовольняе матрл'чну р!зн1сть а^М^-а^; ? А позначимо вектор-стов-пець Бкм!рност" г^ ,а;о складасться з одиикчнкх компонент,1 для

и=у,... уп покладеио K*Cv)*H*Cyt3... f^Cy^). Матека-

тичне спод!вакяя вкиадково: .величина уа(Чъ> обчислпеться за форму лоз '

qÁCv) = aAKÁCv^rA = «V^,

де т/слО = Ч

Нехай г/'Су^. - незалетна шд и гранична днсперс!я вияадкозих

величин ^п ¡А'гО. яка обчаслсвться ..а матрицей граничних ковар1а-стая!в ланцвга та векторам сЛ сЛги.?, де фо-

наре 1я вшадкево! величина и>пСиЗ визначагться прибяизною р!вн!стю

тт~ п - |иТ+ • де I - довжииа фрагмента V.

Якада дсваииа п 1маз1рк юного еюсперимент/ за^вольняе нер!а-н!сть

Г /С—1И

,, + I '(у? т *СуЭ

'« 1" А

[ 9 'Су) -,£? 2Сг.О

1п

Зле2

то !моз!рн!еть покилки при роэп1знаванн1 автомата А& А^ ,Ая> не будя перевищувати с.

Глава 3. Статистичва екзшалеитнють автомат!в У гзйпрпонсваяому а яопереднШ глав! статясткчному метод! 1КТ як1ств тестування пристрою можна керуьати зШшопчи як фрагмент, так I вектор вх1днсго розпод!яу. Така могли» 1сть явлге собою косить пстугякй зас!б в руках експерикэнтатора. У зв'яэку з цкм внпшеае питания про ещаку запропснсга..ого методу 1КТ,скау.:мо, а ляхом пор "зияния йог о з катодом дет&рШноваяого тестувакня. Ви-вчавчи це питания стоссвно сильно зз'язаних автомат¡в природнт моггаа прийти до поняття статис.ичног екв!валенткост1 автомат!» та поршяння и !з авичайнок ехвшахентк.стю автомат!в.

Введено формальна визкачення статпстично: екв!гп"сктнсо'г; ; встановимо И критэр!й. Ка в!дм1ну в:д розглянутого ран мне чхе-пвого вектора р'щм *в символом лезяачимо вектор «вдексованшг Л1тер р-Ср1,... Ход! А(р) буде яз.чати собою 1А з цефжсова-нии1 1мсв1ркостями Ср1 вкступаать яте параметра). Якао зргхуватн,

!Д0 рт = 1 - | , т^ , , у дуть пся'томага.а а*}

¿=1

та - рацюнальними функШями в!д зм:кких р( ,... ,Р,„-1- Назначивши Л многчну рацюылъних фуькщй в!д р(.....рт_< ,заузажи-

мо, то qA с в ¡дофаження У* ♦ Л 1 qA назвемо статистичшш воображениям автомата А. Для $1ксованих алфав1Т1в X 1 У позначимо

■ CX.XJ) клас сильно зв'язаних автомат! в, ш,о мають вх!дний алфав!т X i вйх!днкй - У,а = позначимо в1дношення статистично! екв1валент-hocti на а(Х,У). Тод! для А,Веч(Х,У) за визначенням

ASSB0qAeq.B

Заф!ксуемо на У* деякий лексикограф ¡чны-; порядок ve,v для якого ио=е I |ut; < 1. Для будь-якого натурального п»

=1,2,... визначимо матриц» QA(vJ=[qACvivp] .епеиети яко! rzxi.m |и£ i, \-Jj\ i n. При цьому мае мюце така нер1вн1сть для в!дпов1д-

них раяпв:

rank Q*CrO < rank ffVr^-lJ).

Рангом г^ автомата А назвемо ранг матриц! iHcr^-D,тобто г^»

=rank (Ar^-D. Для будь-яких v,v 'бУ* зазначимо справедлив 1сть

piBHOcTi qA(w 'У - c/cv^cv О.

Ранговое парою систем посл1довностей для А назвемо об'ект

(ТоА,Ъ/) = CCv ,....w „ '.....w зйдовольняе так!

ГА ГА

укови: •

1) wt, ' €У*, причому wt >=u ' =е;

23 rA - rank (ИсЗ^ = rank НАСыА'Э = rank Hfw^.S^O, де

сЛи;>.

cAx ;

HACwa) = Гт/Ц 'J,...,Ли \

ry|

Нсйд.и/) ■ 6A(WA) }{ACVA'),

Для будь-якого иеУ* покладемо FACwA,v,wA'J =GACH>aJNACvJHaCi>a'J i сформулоемэ критер!й статистично! екв!валентност! автомат IB.

Теорема 2.1, Чехай А.В&чСХ.У) I Cu^.S^'J.- рангова пара систем послIдовн( jтt'Я для А. Тод!

» г^гд & г'^й/^С^.й/) & уу€у(ГАСъ>А.у,ЪА'Э =

3 теореми 2.1 випливае алгоритм!чна розв'яэн!сть проблема статисткчн*. I екв I валентноот I.

Теорема 2,1 та супутнI 1й поняття 1лвструють техн!ку,яка була вихорястана при досл!дженн! структури клас1в статистично1 екв!-валентност! та статистичних воображень. За допошгою та гех-Н1ки було одержано так! результата: -

1. Установлено Юнування ьеск!нченного числа кл-"с1в статистично! екв 1валект!;ост 1, кохний э яких м)стить неекв 1валентнI (у звичай-ному роэуыШкО автомата. Цей результат св1дчитъ про те,то за-пропокозаний нетод 1КТ все такк слаб !ший за детермшозаккй метод. 3 другого боку.Естэковлено 1снування нескшченчого числа кяас!в сГаГйстичяо! екв1вадзвтност1,кожний з яких зб!га2ться з в!дпов1-дяим класоы звпчайно! енв!залонтност1, Цей результат св1дчить про салу запропоиоЕаного методу 1КТ для деяких тип1в пристротв.

2. Дослокэпо питания 1снування автомата статистично екв1валонт-кого дакому I такого,цо мае чмсло стан1в,яке дор1внпе рангу ви-2Пдеого автомата. Автомат, для якого /снуе статисткчно еквшалент-:п:3 йсщ автомат п числом станIв,со доронсе рангу вихоного темата. названо статпстячно зводишш. Знайлено критер!й статистично! зводимост! I показано юнування статистично незводшшх автомата. ■

3. Вавчш!! властизост! ст&тастнчнпх вОображеиь автомат 1в,зокре-ыэ овяПл«!П1 уисви.эа яких ыиохана л!восторонн!х похояих статас-тэтпого воображения буде нзскшчэншо.

А 4 *

Яшссторошш поз!Дна воображения ? по иеУ визначаеться

ешззидаэзйняы

д® v 'еУ*. ВОочо.сю воображения,яке в!дпсвиае 1нЩ1альному !коа1рн1снсиу автокату.можэ яати як ск!нчечне,так I несхшченне часло п1вострройН1х пох!дннх. АиалоПчна ситуащя мае мювд I для скчьно зв'язаних детерШкованих автомата. Для формулшання критер!л ск 1 нчеаностI числа похОних статасткчяого воображения

/

введемо таке поняття. Будемо говоркти.цо воображения автомата А&СХ.УЗ обчислпваие ск1нчекним автоматом, якао ¡сяус гаккй сюнченний 1н!ц!альний автомат Мая! С=С5с>Х'с,Ус;.<5(-Дс,Р£0,ао >'с"

0 в протилежному випэчку,

,якз.о * О,

=У, У^сЯ I \'vey* ('/■.c(sc,v)-rtACv)). При обчисленШ Xçfsç.v') опера-ц1в кеикатеаац 11 сл!д зашнити добутком рацюнальних функщй. Теорема 2.2. АеоСХ,У) в автоматом з! ск1нченним числом л1во-

А

сто o:ih1x пох1дних статистичного Ыдобрахення q тод) ; т!льки

тод.,холи о'5 обчис.таане .ск!нченним автоматом.

Розгпянемс не одну властивютъ статистичних в1дображень,для доведения яког була викориетана теорема Бера з теорп метрячнях 1 тополог 1ЧНКХ простор 1в. При ¡Х|=!д визнач1!мо зв'язану область

.°т'<сР,.....Рш-Р I ! Ч < 1 & VîSiSft-ifPi >

t=l

Для автомата А&(Х,У) 1 воображения q^ : У * •» Я при ф!ксо-

1 и

вакому рсперетворветься у воображения |0 :У ■» ГО, 1J.

Розглянемо два розбиття 8д i мжшши У*,визначивши IX р!вно-сяльяостями

Vt sv, сер

la визначення цих розбитпв випливае.ьо при будь-якоыу paDm розбиття 8д е б1льш др1бне,н!я розбиття ,то<5то £ fljj . Внникае питания, чи 1снуе таке peDn ,що S^ a ôjj , I якцо це так,то що являв

собоо ннозшна таких р. Покладемо DCA) = {'peDp | в) I вазвеио цп множину опорно» для автомата А. На основ! теореш Бара про те, цо п^вний м^тркчний прост1р не мохе <5ути представлений^ вигляд! об'еднання зчисленного числа н1де не щ1льних ывожзш.ыохна довести таку теорему.

Теорема 2.3. Олорна многая^ DCA) автомата АеьСХ.У) е шльжш в Dn Ст=1Х'Р,тобто Pm S ИХАЛ.&е СОСАЛ] - замихаяня DCA), i. Аксюматично визначемо клас статистичних вЩобраяеиь I знай-дено умови.за яких скшченн! детерм1нован1 автомата мояуть реал1-зувати в тс <у чи 1ншому р ззу«1нн1 щ ыдображепня. 6. 0ск1льки запропонования статистичк/й метод IKT в зчгальному викадку виявився слабииим в!д дегерм!кованого методу.було проведено його удоскокаленкя з метою полишення моасливостей роза!зна-ватк аьтсчати. При рогп!зкаванн! автомата,на вход! якого д!в ге- ■ яератор випадкових сигнал)в,дулоэапропоноьано анал!зувати вх!д-

ну I визе 1 дну поел 1довност I I як статистичну характеристику вико-ристати частоту появи у вх1д-вих!дн1й посл1довност1 $1ксоваког пари фрагмента. Ста:лстично екв1валентними щодо. входу I виходу названо так1 сильн" зв'язан! автомата,якI не моета розшзнати при будь-якому влбер! пари фрагмента I вектора вх1дного розпо-д!лу. Доведено,до в1диошення статистичног енз!валентное?! аодо входу I виходу зсНгаеться з вГдношенням звичайно! окв!валентност1 автомата. Таким чином,удоскопал^ний статистичний метсд 1КТ за-безпечус принципову можливють'рояп!знавання автомата,. я«1 мо-жуть бута розшзнаш детерм1нованим методом. 6. Для пари автомат!в,конний з яких мае г стан!в,1 ф1ксовано! пари фрагмента одержана анал!тична залежнЮть довжини п 1мов1рн1-сного експерименту.що розшзнае автомата,в)д числа сташв г,вх.-дпого розпод1лу р СвхШшй алфав!т (0,1>, 1мов1рн1сть появи 0 е рЗ та 1мов!рност1 'помилки розп!знаваяня е-.

п * г + с £ + сгт - и т-й— ; 1п —Ц-.

Р 1 Р 8лег

Наведен! результата,як! вклвчають аиал!з статисти^чих вяь-

стмвосеЯ ся!нченних автомат 1з та критерп Гх моюшвэстей реал1-зувати статистачн! воображения, давть змогу зробити висновок про з!Д1фиття нового иапрямжу теори детермшованих автомат!в,в рамках якого розроблёно та проведено оц!нку нових статистичних методов разпгзнавання автокапв.

Глава 3. Паташя теор 11 сигнатурних анал!затор1в

В трэтШ глав! резробяеяо основи теорп сигнатурних анал!за-тор1в,ьлзначено базисн! поняття (екзшалентнють,гомоморфам та 1ншэ) I одержано результата,як! дозволяють глибше зрозум1ти пронеси, яо вШйузашъся при стискеня) лосл1довностей,що анал1зують-ся,в сигнатуру,а такоа форш>.л1зуватм деяк1 перэтворення СА при 8бэраа©ян1 IX властивостеЗ щодо виячлення поиллок.

За математнчну модель п-канального СА з г бшарниш елемен-таыи паи'ят! прийнято ЖЗМ без влход1в С=СА,В1,де А - квадратна СгхгЗ 1 В - прлмокутна Сг*ги бшарн! матриц!. Для р г. г через £р незначимо векторний прост¡р бтарних вектор 1в--стовпц/з 81:м!рносг) р, в якому як додавэиня використовуеться операщя шдсумування ® по молу~п 2. Сч С можна розглядати лк скшченний !н!Ц1альниГ; автомат без виход1в С = СЕ ,Е ,5.0).ле ЕГ - мнохина стан!в,Ет -вх!дний алфав!т,(5 - фугкшя переход1в.то визначаетьея через А I

12 . ' Л- . Г-'.

В,0 - початковий стан С0сЕг 1 вс| компонента вектора 0 е нулО. Для будь-яких 5€Ег I хйЕт функц1я перехода визначаетъся р!вн1- ■ стю 6Св,х) ~ Аг ® Вх. Як звичайно будемо використовуватн розши-

ре.чг* функцIг <5 на посл»до::юст! иеЕ^ ,де £* - ыножина вс!х вх1-дян . поол 1довносте1 ск!яченно1 довжини,включаючи пусту поел 1дов-

К1СТ1. е довжини 0. Будь-як1Я поел (довност I иеЕ^ СА С ставить у 3!дп0в!дн1сть сигнатуру 0, и). Помилки в посл1довност1

иеЕ* можна задавати посл1давнютю ,що мае одиниц! в тих по-эишях.в яхих зазнали зм!н компонента вектор|в э и . Посл1дов-иють и ',яка одержана з и внасшдок помилок и.обчислветься по- , розрядним додаванням по модулю 2 послиовностей и 1 у.причому оаздалепдь вир!внюються IX довжини шляхом дописувавня необх!д-ного числа нульових вектор 1в зл1ва в б1льш корстк 18 поел Iдовност] Си '=и 8 и).Помилки и не виявпяються СА С,якщо 'Л що екв 1валентно р1вно.т1 ¿СО.иХ). Таким чином,множина невиявлв-

вамх СА С помилок эадаеться вираэом К^ = ("««Е^ | 6С0,-\О*О). Ех-в1в£лентн)сть СА С I Сг з однаховим числом канал 1в т виэначаеться Р1ЬН0СИЛЬН1СТЮ

с. * С.

1 а

В 1н:ц1альноиу автомат! С=СЕГ,ЕП1,6,0!) можна розглядати Плькя Т! станл,як! досяжн! э початхового стану 0. Покладвиэ ■ |

| 3,,,г* СбС0,и;=5^ 1 СА С наэвемо ненадм1рним,яхао |5С| « г^.де

ш

|5С| - потугчеть множини , 1 - неособ лианы, яюю матрица Л тш-

особ~ива.

Перел1чимо питания, як 1 роз глянут! в глав! 3,1 сфорыулюемо де-

як! теореми:

екв1валентн!сть I ненады1рн1саь; гомомор$1зк, пряма сума 1 дойутох;

кратер 1й кевиявлсваност! будь-яко! множини помилок деяким СА; багатоканальк1 аналоги одноканальнях СА; рвгШзашг СА на одному рег!стр| зеуву; поргвкяння л!н!йяих I нелишних СА.

Сигнатурний анал!эатор виконуе стиснення поел! довностеЯ,що

аная!зувдься,тобто реа/пзуг. в!доораження Г^ Е Показано,цо це • воображения можна представити у вигляд! Оулерпозицп двох в)до-

"...13

драхень.одне э яких залегать тчльки в!д матриц! переходib А 1 стискув посл1довноот1,ао анал!зуьться,в поел¡довнсстi,довжина яхих дор!внюе степей 1 м!к!мального пол!нома згаданот матриц!,а друге в!добраяае стиснул посл!довкост! в стани СА. На основ! такого представления воображения энайдено критерт кенадмфност!

СА. Щоб його сформу: эвати.позглянемо матрицю Н^СтО .....АВ,

Теорема 3.1. НехаЯ С - СА,ВЭ - СЕг,£т,б,О), in/xl - м!н!маль-ний полшом матриц I A I deg лАСх)*Тд . Тод!

С - ненадм1рний СА » rank И^т^-г .

Гошморф1эи СА визначаеться звичайним способом. Будемо писа-ти С% i Сл ,якщо Са - гомоморфне зображення С . Мае м!сце р1вно-сальн1с1^ С( з С4 в С% £ Ся & Са i Ct . wie z. деяких випадхах гомоморф!зк СА вшсликав !х екв!валентн1сть. Для формулгвачня в'д-П01 »ДН01 теореми розглянемо деюлька попять. НехаЯ w(iD - загаль-

на ^1яьк1вть одкьнць у векторах послШовност! uef* . СА С назве-ио вяявлявчим поодмнок 1 поуилки , якщо -¡¿¡О -1 ф » $ Vq для BC1X

Теорема 3.8. Пехай £Г -CAt ;В У I Са=С/г,Яа) - виявляюч! по-одивокI пошшкк неиадшрнl СА I характеристичней полшом <рА (уО

матриц праштявяоа. Тод! С < Са * С1 г Сл .

Виникяв питания,як! властявост! повинна мати дов)льна мно.та-

ва У £ лоб Юнував деякнй СА С, для якого / була б множинсю . :\вм зявваяих помалок, тобто

Мяожи„у V S ^ назвеьо правильно!) швгрупос в 1дносно опера-ц 11 Ф, яга» вона задоволъняе так! умози: IV в « V; \

Z\ и ,аа е V ♦ tttO ил с V-, 3) YO S V -.

, .4} и « V 0 oNi в У для вс 1х натуральних Ч .

На ыножин! для г.ов!льно! Шггрупи У в!дноснс операцi i а

виэначимо а 1 ".ношения екч1валентност1 = ,задав|_л його ргвноснлън IV

сто ut s иа й«в ua« V . 1ндексом vy niBipynn V наавеыс число клас!в в!дношення екв1валентност! z (v., можэ бутя ■ носкшчен. I-

стхО.

Теорема 3.3, Множила V £ Е* е ыножккос невкявяввааих ясмнлок деяксго СА тод! I т1лх:си тод1,коли V - правильна Швгрупа в1днос-нс илерацн © !э ся!нченним шдексом.

У зв'язку а появий публ1кац1й по нея'нШких СА винмкла потреба тх пор ¡вняння з л1н1йними сигнатурками анализаторами. Буи'роз-глянут! властивост! СА,як1 корисн! при тестуванк/ та анал1э! г.ро-цео1в тестування,I оказано,що деяк! з цих властивостей характер-н! .'Плькк для л!н 1йних СА. При анал1з! здатност! виявляти поиилки кориснос властивютс лшШних СА е 1нвар1антн1етъ пошитая аодо поел 1 довнеотей ,яох вони змШюють. Це дозволяв дослщжуватч по-милки незалекно в1д посл1довкост*й,в яких вони виникають. Виявв-лося.що нел1н1йн! СА Ц1ег властивост! не маять. Цей факт встаноа-люе така теорема.

Теорема 3.4. СА С ьиявляе 1нвар1антну множину помадок тод! I т!льки то д1, ко ли 1снуе така ЛПМ.якг 1зсморфна С.

Нехай С - <.5,Ет,6,5 Л - ск!нченшй 1н1Щалький азтокат без

/II О

виход !в. Розглянеми таку властав 1сть СА С;

\ .в <4 * 5а * Ъеь™5, * «>

Властивють Ш хсорисна для СА там,во якщо «очатко»!. частини ета-лоннот 1 помилхово! поел1ДОБНОСТ' переводять СА в р!зы: станн.а остчнн! частини цих посяШовностей 5б1гавтьсл,то сигна^рша ака-л!затор эабезпеч.уе виявяення тако! пошшково! поел1ловкость

Ваклквоп властив1ств лШШних СА е 1н здатають риявяятн пг-милки н^залежно в!д м1сця Гх пшгзи в пося1довшст1,що аяал!зу8ть-ся. Виявгпеться,цо нел!н;йк1 СА не моауть одночасао мата' остаяао йт стиЫсть ! вла-тиають С13. Про це № 1дчнть така теореыа.

Теорема З.Р. СА С эадозольняе умову (1) 1 заявляв аоиалки незалежно в!д мюця 1х появи тод! ! т!шш тод 1,коли 1сяув така кеособлива ЛПМ.яка 1зоморфна С.

Таким чином,в третШ глав! розроблеко оскопи теор!: СА.ао базувться на теерп ЛПМ I включаэть Д0СЛ1Дкення сп©циф1чних па-тань.як! ке значащи воображения в загальнМ георп ЛЛМ I стооу-стьоя виявлэння помклок в поел1довкостях,цо анал1зу£ться.

Г лам 4.. Олтггмальн! екгнатуглп аяал1затори \

Еажливов проблемою теорIт I практики СА с проблема розробки сдиноI м(рк (X якост1,в1дносно йко! в клзс I вс!х СА можна дуяо б

вид1шти найхр;- U (оптимально щодо эдатност! виявляти помилкч. У зв'язку э велико» р1зноман1тн!стю можливих г.омклск в посл1доз-ностях.цо анал1зувться,ця проблема Бияви;.ася духа складкою. Нэ дивлячись на велику к!льк!сть podit,присвячених ефэктивност 1 ли-користання СА,единоï м!ри 'ч якост! розробити не вдалося. I все s за загальноприйнятою думкоп у Еипадку.коли про розподш ¡мозф-ностбй потей помилок н1чого не вIдома (а цо на пракыц! - ткпобий випадок),серед одноканальних СА олтимальнньм вважаються сигкатур-н! аиал 1затори,згенован! ка зеувних репстрах з лih!йнка зЕорот-шш зв'язком.що с ¿нсуеться пркм!тыним пол1номом Сприштивн! CAD. Ochobhi задач!,як1 розв'язан! в четверг1й главi,полягають в зна-ходхеш»! критврю асимптотично! оптимальност1 CA,i>. досл!дхонн1 характеристик прим itiibhiîx одноканальних СА та визначенн! класу оптш/.ая!.л1х (Загатоканальни.. СА, ио мають влаотивост! виявляти по-кагт.:, аналог 1чн1 властивостям прттивких одноканальних сигнатур-hiî апгл1затор!в.

2а основу виначення асимптотично оптимальних СА прийнята

асимптотична imob1рн1сть невиявлення помилок,вд дор!внпе 2~г для сигнатурних анал!затор1в з г елементамк пам'яп. При цьому.гви-чайно.всо зайежить в^д хласу розпод!л1в 1мов!рностей пояеи помилок, до роэглядаеться. В дисертаци доел¡дкено два класи розпод!-Л1в,як1 не духе В1др1зняютъся один Bifl одного: в первому вппадку розпод1яи беруться а симплексу t границею,а в другому - без границ!. Класи СА,во в|дпов!дають цнм випадкам.значно ?|др!зняються. Першна кдао достатньо вузысиа l в якШсь Mipi моке служите ви-значечши оптииальти СА. Другий клас охоплюе майже bcî СА i то-ыу ко вид'ляе оптималып. Сфорыу! емо б1лъ"| детально результата, «Kl одераан! а цьему напрлмку. ДосШджено асимптотичку оптималь-а1сть лппйю: : СА при двох припущеннях: коли деяк) з ¡моьфностей появи пошшок шгуть перетворвват/ся в нуль (просто асимптотична оптимальн ¡сть) I коли Bel )мов1рност) в1др1знясться вщ нуля (сяабка асимптотична оптимальн!сть). В odox випадках припускаеть-ся стацюиарнють роэподиу ЫоирностеЯ появк помилок.

Нехай En-<et ,et,.. причоку et -0. Ксхксму вх1дному сим-

волу ПОСТаВИИО У В1»,ЛОВ1ДН1СТЬ 1мов1рн1сть иого появи Pj I розглянамо клас Р рсзпод!л1в 1ков1рностей ..олви сиизг.лт з £л-

pilt

p -- <cpt,...,p^3 ! |_p£ = i & p, > o & cPí > o».

Для GA С*СЕг,Еш,бг0) i peP покладемо Xp"(uieEm | p¿ > 0> , Sp» «iseE | 3 ev* C6C0.t |SD|=WD. Тод1 критерИ» асимитотично!

p " г

оптшальност 1 дае така теореча.

Теорема 4.1. Неоообливий СА С - асимптотично оптинальний тод1

1 т!льки тод1,коли Нр=2т для BClx реР.

В наступи 1й теорем! сформульовако критер1й слайко! асиыпто-тично! оптимальност..

Теорема 4.2. Неоообливий СА С слабо асаыптотично оптикальакй тод! i тшьки тодi,коли С - неналпрний.

OcKiHbf i серед неособливих ненадшрвих СА с сигнатура! ана л!затори,ш,о як добре,так ! погано виявлявть пошлкн.то cx.adxa ас>»мптотична оптимальн 1сть не с аадовшыо» Mlpcn яксст!. ., •

Л- л окремогс типу СА критзрШ аскмптотично! оптаиальноат! можна сформулювати в термшах ьластивостей характеристичного по-л!нома матриц! переход 1в. Для б!нарно1/»а - матриц! В И J-R стовтець поэнг-иыо 1 розглякемо мноишу вектор1в-стовпц1в, що аизначаеться таким сп1вв1дноиенням:

Нп В « <at8Mt<¡>.. .еа^а1 VlStáa fatef 0,1>'й Сс^».

Теорема А'.З. Нехай С=СА,Ю такий СА.цо А - иаосойтжа г*г -матрица, Oclin В i rank В = г. Тод! для асшшто'гнчаз! о-ТЕыапь-koctí СА С нэобх1дно i достатньо.щой характерноа^чшШ кшшом pjfx) матриц! А був незводимаы.

Як зазначалося вище, на практиЩ серэд одкохаваЯяпг* espesara В1ддаеться СА.що опи.ухггься прим!1 ивннич пошчоиакн . Валква-лися в 1дкритиш. питания: як сор{вШ9гапг uis codos оряы!тгвн1 СА I чи с примиивиий СА $1рми Х'алет-Пахкард найкраодм. розгляд! цих питань за$!ксуемо увагу на однокакальшх и'А.ао олксуеться по-л!номами в пол! 6ГС2J. В1доыо,г.э будь-яку б1карну посл1яоап!оть з T04HÍCTT до нул!в зл(ва «южна аадааатя у вйгяйд! пояшома. Вв-хай pjjfxJ - пол i кем, який описуе однокакальшШ vA С, a ir¿u> - пр-niK0M,üi0 визначяе бшарку посл!довн1сгь tí . Сигнатуру s¿Ctú Во-сл!довност! и,одергану за допомогов СА С. мокла ваэначити р|вш-ctd s¿Ciü=Rp^x:>tmi:iú] ,й& R^^lwCiúl - ос»ача в!д дшепяя ®TuJ

на ».ч'х? в пол! bFCcj.Мнокина невиявлзваних СА С помияок задасть-

С/

ся виразом Vq~(veE* | p,<yJ\rfvJ} ,де p^Cx) ¡rrufu) о^лачае д!лення пол (нома mCv5 н*>. пол ihom y^yj без остач1. Для т£1 покладемо V^jCrO-iveVQ j | и |=1г?. СА С моги а визначити за допомогою матрица

Ж -

Бважавчя'непусту посл!довн!сть ueEj б!нарним вехтором-атр1ЧХ0П,одержуемо

V^CrO = Cueff | |v|=n a v[HcCrO]'-0),

де операц1я транспозиц1Г,а .....AB.BL Э одного

боку, мкожияа У^СтО е пол!ношальний код довжини п,а з другого -нульовий простф матриц! И^СгС Нехай г - сташнь пол¡нона

При ISnSr мкожияа К^ГгО схладаеться з единоI посл!довност1 О71 1

точно хажучн.че е кодом. Якдо п > г,то V^CrO м Ютить 1 ненульо-

л поелIдовностI. Тому можна говорит» лро м1н!мальну з1дстань

коду У^СтО,щ> дор|виве мш!мальн!й ваз1 кенульових поси-

довностей у '/^а).

Таким чином,введена функц!я dff.rO (рис.2) м1н!мальних вЩста-

кей.яка тля будь-якого п > г дозволяв визначити число d^C.D - i

поыилок.виявлюваних СА С в будь-як !й поел Iдовност 1 довжини гг. При

достатньо ьеликих п. d^CtO приймае значения 2 (для деяких СА -

значения 1). Оск1льки СА приэначен! для анал!зу дуже довгнх пос -

л!довпостей,то ва перший погляд здаеться.що функщя суСп) с елгб

коп характеристикою СА виявляти поыклки. Однак d^rO добре харьк

твризуе здатн1сть СА виявляти пакета поыилок.шо я об'ектами.шва-

р:антними по в1дйотеннв до довжини посл!дозност!,що анал)зуеться.

Починаючи з 1**г+1,функц1я dfrO е монотонно спадною i d^r+l.^

дор|рнпе числу wCp^Cx)} ненульових коеф!Щент!в пол!нома р^хУ

С ваз! пошкома). 3 kohotohhoctI 1 обыеженост! фунхц 1 т d^rO ви-

плизае Юнув^лпя границ! dr~ Нш dpfrO що flopisvoe 1,якщо

п-иа

,I 2 в протияежноиу вигхадку. drCrO

и

viCpQСх» 2

.-!--- ....-!- п

2Г - длг ггри-

м 1'гивних СА

Рис.2. Граф!к функцИ d^C J при <рЛх) * \г

Э точки зору здатност! виявляти паке Л! помияок той СА кращнй, чия функц1я'м!н!мальких В1дстаней бшьша. Однак Юнують СА,як1 маьть кчпор 1вняк 1 ■ функц 11 мшшальних в! деталей. Тому для визна-чання.яхий СА кращий,мае сенс пор1внюзати суми мШмальних в!д-

стакей,зм!нюючи пыд г+1 до 2Г- 1,бо для п>2г ус! СА,в репст-р! яких Юнуить зворотШ зе'язки,масть ¿£Ср_)=2. Таким чином,за мфу якостI СА С.заснсваного на репстр! зс,гву з! зворотн!ми зв'язками.можна вибрати величину

МС = 2 ¿¿то. п=г+1

М(ра якост! дозволяе пор!внювати м!ж собой нав!ть прям 1тивн 1 СА. Було знайдено 16-роэрядний прим!тивний СА,який у в!дпов!дно-ст! з вь-еденою м1рою якост! е кращш,н1ж сигкатурний акал1затор ф!ргд! Х'юлет-Паккард.

Хоча була введена М1ра якост1 одноканальних СА.яка дозволяе пор1внювати ы 1 к собов нав1ть прим1тивн1 сигнатурн! анашзатори, обчислення ц!ет «1рк виявилося досить трудомютким. На практиц1 ■ пркйнято вважати будь-як! прим!тивн! СА оптимальшгш в клас1 одноканальних. 3 точки зору здатност! виявляти помилкк ирим1тивн1 СА характеризуются тим.що вони виявляють подвШн! помияки в най-б!льа доьгих поел¡довностях. Тому за м1ру якост! СА приймемо ма-ксимальну довжину посл1довностей,в яких В1н ьиявляе будь-як I ло-ДВ1ЙН1 помилкк.

Эдатиють СА виявляти подвШн! помилки завжди пов'язана з довхикою поел ¡довност 1, що анал!зуеться. Нехай е^ - найбшьша довжина посл!довностей,в яких СА С виявляе будь-як! ПОДВШН! помилкк. Можна показати.що для будь-якого г-розрядного ш-каналь-

ного СА С 2 [ т~ .Дб ['2 V-1;] " иайб!льше число, що не перевищус 2г-1/п . 3 точки зору здатност! виявляти подв1йн! помилки перевагу ся!д в!ддавати тим СА С,у яких - -]•

При. виэкаченн! оптималъних багатсканальних СА сл!д взяти до уваги ту обета (ПН.'.ио вони можуть використовуватися в однока-аальному режим к .ли анал!эуеться б!нарна посл]дов:з!сть сигна-тпв-д-.о. подаетьсь т!дьки на один (будь-який) вх!дний канал. При

цьому вважаеться.що на решту канал ¡в подаються нульов! посл.'доз-КОСТ1. В цьому режим 1 також daza.no забеэпечити - моглив 1сть вияв-ляти подв 1йш псмилки в б1нарних посл1довностях максимально! дов-

жнни. Нехай Cq СШ<пй - найб1льша доветна бшарних посл1довно-стей.ао подаються на i-R канал,в яких СА С виявляе будь-як! по-ДВ1ЙН1 помилки.

СА С=(А,В)=(Ег,£т,6,0)ло виявляе поодикок! тошлки,назвемо

оптимальним.якщо ес -] i = 2Г - 1 для bcix l<i<ia .

Наступна теорема встановлве достатн1 умови опткмалькост! СА, як! в деяких випадках являються I необх1дними.

Теорема 4.4. СА С=(А,В1*СЕг,Еп,б,0) - оптимальний.якщо задо-вольняються таю умови:

1) характеристичний полшом рд(х) матриц! А приштавиий;

2). .¡товпцями матриц! В е вектори р.А^р,... ,/"тг1'>7'|?,де ¡3 - деяния в1дм1нниЯ в]д 0 вектор-стовпець вим!рност/ г I Т~ • Умови 1) 1 2D е необхШними для оптимальност! СА у випадку.коли

2Г - 1 д ¡литься на т..

Якщо при проектуванн! оптимальних СА безпосередньо користу-ватися умовами.що сформульованI в теорем! 4.4,то виникае необх!д-

н!сть виконувати обчислення вектор!в виду число яких близько

до 2Г. Тому такий cnocld конструввання оптимальних СА при чико-ристанк! для обчислень ЕОМ середньо! потужност! обмежекий значениями г,що не перевищують 20. В тому випадку.коли числа 2г-1 i п е взаемно прост i, мохна запропонувати значно менш трудомюткий метод хонструювання оптимальних СА.

Теорема 4.5. Нехай А - б!нарна гхг-матриця з прим¡тнвням ха-

рактеристичним пол (номом, nil - таке число,що 2r-l l m взаемно прост I i В = ('/?, Aft,... ./Г^/З^де /3 - в!дм!нний в1д 0 вектор-стовпець вим!рност! г. Тод! С=САт,ВЭ - оптимальний m-канальний СА. Якщо матрице А задавати у вигляд! супроводхугчо! матриц! дв-

яхого прим!тивного пол!ному,то обчислення матриць А"1 I В мохна виконати за. прийнятний час для досить великих г I т.. Обчислення цих матриць для г=32 I т=256 на ПЕОМ IBM PC/AT-28S займге час

б1ля 7 с.

Будь-який оптимальний т-канальнЕй СА С могна виг.ористовува^и як 1л -канальний СА С^.де пг <гя . При цьоыу С( одержуеться а С шля-з.ом ф1хсацп в ньому т, канал!в I подач! на решту т. - т какал!в лсст.йних нульових эначень. Внасл!док такого перетворення.вэагал! кажучи, одержуеться не оатимальний СА С /якцо т!льки т.(* 1. Нехай С={А,Ю,&в матриця В мЮтить т. стовпщв. Заф1ксуемо в В тХ т стовпшв.а га - т стовпц.1в,щ,о эалишилися.викреслммо. Одер-жану таким чином з В ыагрицю позначиио В. ТодI С^(А,В1Розгля-кемо випадок,коли внасл1док описаиого перетворёння оптимального СА С одержуеться також оптимальний СА.

Теорема 4.6. Нехай А - сИнарна гхг-катриця з арим!тивюш ха-

■ к К

рактеристи^-'им полШомом, п=2 I а =2 ' ,де <г , /3 - в!д-

?к-к

м!нний в!д 0 вектор-стовпоць виы1рност! г ! В=Г/3,/г ¡3, к

Р рк-к I 1рк-к _

/Г с 1 (],... ,А ~(31. Тод1 СЧ. А ,ВУ оптимальний |а -ка-

нальний СА.

Як приклад використання теороми 4.В при проектуванн! СА

розглякемо оптимальний 64-канальний СА ,до у! - бшарна

гхг-матриця з прим1тивниы харак:еристичшш пол томом Сг216) 1 В-[(3,Ар.Агр,... ,Ае*р] Стут (3 - в1дм!нний в!д 0 вэктор-стовпэць вимфност! г). У в!дпов!дкост1 з теоремою 4.6 на основ 1 С можна одержат« оптимальн! 32-, 16-,8- ! 4-каналы.1 СА С,а.1 якцо в С оаф!ксувати тах! канали:

для Сза - 1,3,5.....63; дия С|в - 1,6,9... .,61;

для св - 1,3,17.....57; для С4 - 1,17,33,49.

При кояструювакн1 оптимальшх багатоканальких СА використо-ьуються багатовходов1 схеми додавання по модулю 2 Ссхема контроле парностО. Оск!льки 1х робоча частота заложить в1д шлькост! входов.то при проектуванн! швидкодтчих СА доводиться проводит М1-Н1м!зац1» к1ль..ост! вход!в м!кросхем контролю парносп. За заказом ЭеленсградськоГ орган.'зацН !1Д1 Науковий центр було спроекто-вако ШВИДКОД1ЕЧИЙ оптимальний 25-розрядний 64-канальний СА з ро-бочою частотою 50 МГц.

Глава 5. Випадкове пошвняяьие тестувэння

У зв'язку з широким рсзповссдкенням на практик! методу ви-

2.Ï

падкового поршняльного тостуваяня ДП.остання главг. дисертацп присвячека цьо»"' методу. Тут вивчеио клао несправнсстей.ауэ вняв-лякться при тр1йховому моделвзанш, I истгкоьлепа трудом юта ¡сть IX виявлеиня.яка зимчрветься функц.ев имглриост! виявлення в!д човхиии вяпадково'! посл1довтюст1 набор ¡в, що гекеруються отащо-нарним дгерелсм неэалежих випадкозих сигнал!в з задании розпяд!-ком. iuob 1ркос"ей цих сигнал is. 2ипадко»ай процзс виязления нес-правностей описано псглиналыпш ланцвгом Маркова; за iloro допоно-гоа знайден! точне значения шов]рнс-т1 виявлзчня.а також И ни-жн! та асимптотична ou Шкн.

Нехэй ц Crû - iMOBipHlcTb гиявленн.т аеелравност! н випадкозим тестогг доехлни п. Позначно tp ьипадкову величину, ¡до дор)энюо чпслу крок!в марк 1всь:сого гроцесу з п^чатксвого стану до погпи-! i'-яя. Матэматичне спод1ванкя fi t^] та диспаше!я Df t.^1 випадховсн велачини г моана ойчкслити за допомогоо фундаментально! матриц! поглинального ланцэга. Еикористовуючи кер1внють Чебкшева.мсжка вивести ниша ощкку дчя q^CrJ'

Dî'J

q..Crû > 1----ё--.

н Cri - Wyj2

На основ! анал!зу ергодичного ланцюга Маркова,оцержаного з поглинального ланцвга.можна знайти асимптотичну ощнку

! г ежи + 1 - njvmjri ■]

%(7° * h ~51-—13—=---— ! •

L /nbftHJ J

дв § - символ функцп Лапласа.

Эаяропонозано I програмно реал!-зова..о в автомати5ован1й систем: моделв^ання I д[агкостузання CACMID досить поостяй алгоритм вииадковог побудови тесту для виявлення посда^оких коксталт-..их неспразностей ДП. Система ACMI3 впрозаджека п!дприеистпнх м. Саратова !з значниы економ!ч;гам ефектом.

OcFQBHl результата роботи 1. Створено новий напрямок т pop 11 с*, 1нченних детарм!неваних автомат !в, ¡до MuG багати сШльких рис з теор!ег i.mobIphIckkx автомата Одним з основних о;''ект1в досл!дження цього напрем:'./ е ста-тистичне воображения, яке в!дпов!дае бьгатотактиому кака/у э то-ор 11 IA. В рамхах створеного нгпрямк/ резв'пан! та..:

- Рсзроблено два статистичних методи 1ыов!р \jHoro компактного тостуьання.як! аазуються ка шдрахунку частоти появ:: п1дпосл1-довност; (фрагмента) у вих1дн;й пссл1доьноот1 та пари фрагмента у ВХ1Д-ВКХ1ДНШ поелIдовностI. Доведено,цо розподш 1мов1ркостей частот <$1 кованого фрагмента у здаидн'й поелIдовност 1 заданоI доьеини апрокскмуеться нормальниы законом,I виведен! формули для отчисления параметр нормального розлодшу - штематичного сло-д1вання та диспереП. Встансвлена акалггична залежн!сть довхини в'.1пад:с01501 посяIдовностI в!д апрюрно; 1мов1рност| помолки роз-л!зка£акня,граякчних диеперс'й та матемаигакх епод1ьань,ио об-числюьться по шогфкоетях появк ВХ1ДККХ сигнал 1 в ! функщях. перехода I виход ¡з автомат 1в.цо розп 1знаютьея.

- Розроблэн! метод!'. Т.КТ пор1вняно з дотеры'.яованим матодок тес-тування Перший метод,за винятком деяхих випадкзиявився сла-бшим аа детерм!нований,а другий'- р 1вкосильний йому.

- Введено поняття статистичко! екв ¡валег.тнест 1 автоматов, у яких зб1гаиться етьтистичн! воображения. дослЦхена структура клас1в статисгачког &кв1ваяентаост1 в термШах хлас!в звичайног екв!ва-лектяоет; автомат1в.

- Досл1дхено питания юнуванкя автомата, етапктично екв1валент-кого дака?.^ I такого,то число йога стан!в зб1гаегься з рангом етатиетичного з1дсбрахення вих1дного автомата.

- Вивчено гластивост! статастичних в!добраасэнь автог.йт 1 в, зохрема в станов леко умсви.за яких множина л!востоооня;х пох.'дних етатиетичного воображения буде неск1яченно».

- Аксюматично визначеко клае етатиетичкш: в!дображвиь та энай-деко уяову.,за яких екшчекк! детерм1нован!; автомата моауть реал1-зуЕатя в тому чи 1ншому роэумшн) ¡и в:дображекня.

2.кззроблено основи теорп сигнатурних анал1затор:в,визиачено базисн! покяття Секв1валентя1сть,го.\[омор$1зк та 1ншэЭ I одержано результата,я;с1 дозвеляэзть глибше зроэум1ти процееи.що вЩбу-ваэться при стиснекн! поел Iдовнсстей, ш.о гяал(зуютьея,в сигнатуру, а такох форкая;зувати деяк1 перетворення СА при зберехекн1 !х властивостей йодо виявлеиня аомллок.

3. Досл(д4.еаа аеккптотичаа олтямаяьякть л1я!Яних СА при двох прилунениях: коли дэяк! шов1ркост1 появи помйлок можуть перетворюва-7ися в куль (просто аскипготичнг оптимальысть) I коли вс! ¡мо-Г'рносп в1дм!н..I в!д нуля Сслабка асиметотична олтимальяютьЭ.

Одержано критерП Tlsl та 1ншоТ аоимптотичнот -оптулк-лъносп CA. 4.Введена настпьки тонка м'ра якост! одкоканаяьких CA,цо зона дозволяе пор!внввати м!г. собою яав1ть прямтшн сягнатурн! аяа-л1затори,як! за заг&яьнопризяано» .цумкоб,гзахапться оптш/алькиыи ч клас1 одноканаяьнкх CA. Показано 1снузання приштавних CA.hhi у в!дпов!дкост! з даков Ml роя якостI е кра«! сигнатурная ана-лшатор ф!рш' Х'»лзт--Паккард,що ваазазться стандартом одкока"аль-них CA.

5.0ск1лыси прим!тивн1 CA ВЕгжаються оптимальними в клас! одно-канальних,то щякоы природно «чзначитя оятимальн 1сть багатокана-льних CA таким чином,цоб вони мали так! г ыожлнвост! виязляти помилки,як I прик;ткв<:1 CA. Введена Mips якост! багатокакальних С* I на II баа! визначено клас оптимаг*>кия багатсканальннх си1'-гатурних анал1затор1в,що задоЕ ,льнякть вшцезгаданШ умов I. 6.Роароблеко метод проектування оптимальных багатяканалънмх CA з великим числом вх1дких канал!в. Цей мэтод дозволяе враховувати питания швидкодп CA.

OchobhI результата дисертацп викладен1 у таких роботах: 1. Барашко A.C. Оценка длины вероятностного эксперимента,осуществляющего статистическое распознавание автоматов / АН УССР.Кн-г арихл.математики и механики.-Донецк,1QS5.-18с.-Деп.в ВИНИТИ 28.01.85, N1032.

?.. Барашко A.C. 0 зависимости качества статистического распознавания автоматов от длины анализируемого фрагмента выходной последовательности // Автоматика и телемеханика.--1335.-NO. ~ • С. 136-142.

3. Барашко A.C. 0 длине вероятностного эксперимента и статистической экзав^ лонтности автоматов /•' Проблемы теоретической кибернетики: Тез. докл. Всесосз. кокф. -Иркутск, 1585. -С 1 В.

4. Барашко A.C. 0 некоторых свойствах статистической эквивалентности автоматов и их состояний // Теорлч управляющих систем.-

К. : Наук, думка, 1S87. -С. 3-17.

w. Барашко A.C. 0 ранге и статистическом отображении сильно связного автомата // Кибернетика. -1937. -N4. -С. 56-50.

6. Барашко A.C. 0 отатистическоЧ эквивалентности автоютов по входу и зыходу // Abtomî ;ика а телемеханика. -1527. -N'3. -С. Ш-з50.

7. B&rashko A.S. The new way of probabilistic compact Lsr-.tin.-j // Int. Conf. FCT-87 -Kazan,June.i°87.-P.*5-47.

а. Аидрихин А. И. .Барашко А. С. ,Чвревко Н.В. П ^автоматическое построение тестов с исяся&зосаякои генератора случай.: jx сигналов // Автоматика и вкчисл. техника. -1938. -N1. -С. 93-94.

9. Барашко A.G. Od одной море качества сигнатурных анализаторов /. Там its. -ИЗ. -С. 87-31.

10. Барашхо А. С. .Скобелев Б. Г. О статистически приводимых автокатах // Изв. вузов. Математика. -1939. -N2. -С. 6-10.

И. Баг ashko A, S. Fault detection in digital circuits by fragment counting // 6-th Int.Sywp. IMECG TC Technical. Diagnostics 89.-Praha,Juns,1989. -P. 443-44?

12. Барашко A.C. Об одной сравнительной характеристике сигнатурных анализаторов // 12-th Int. Genf. Fat'it-Tolerant Syst. and Diagnostics: Proc. thesis. -Praha,Sept. ,1989. -P.345.

13. Бараако «.С. С простых классах статистической ¡эквивалентности детермишфованних автоматов // Теория и моделирование управляющих систем. -1С.: Наук, думка, 1989. -С. 3-9.

14. Барашко A.C.,Чоревко Н. В. Некоторые способы оценки длины случайного теста х/ Там хе.-С. 10-15.

15. Бараако A.C. Оптимальные многоканальные сигнатурные анализаторы // Автоматика и внчисп. техника.-1990.-Ml. -С. 81-85.

16. Барашко A.C. К теории сигкатурных анализаторов //• Кибернетика. -1690. -N2. -С. 10-22.

17. Барашко A.C. Некоторые вопросы конструирования быстродействующие многоканальикх оптимальных сигнатурных анализаторов // Автоматика и вычисл. техника.-1990.-Кб.-С. 75-79.

18. Барашко А.С. Статистические отображения и их реализация конечными автомата*« // Моделирование и диагностика упр&впятмх систем. -К.: Наук, думка ДЭ51. -С. 15-23.

19. иараигко A.C. ,Скобиов Ю. А. .Сперанский Д.В. Моделирование и тестирование дискрггных устройств.-К.: Наук.думка,1992.-286 с.

20. Барашке A.C. Проектирование быстродействующие многоканальных оптимальных сигнатурных анализаторов // Методы и средства технической диагностики: Материалы XI Мегзузсвской шк. -Ч$емина-ра.-Ивано-Франкспск.окт. 1992. -С.102-105.

21. Барашко A.C. О некоторых ьелезнкх свойствах сигнатурных анализаторов '/ Кибернетика и сист. анализ. -193-3. -NO. -С 15-20.

32, BapaiSKO А С. Кэтршгаяьнал неаэбкточность к гсиуптотическая оптимальность си.латурных анализаторов // Дет АН Украины. -1S93. -

Лво. — С. 75-77.

23. Барашко А. С. Асимптотическая оптимальность сигнатурных анализаторов относительно стационарных ошибок // Кибернетика и сист. анализ. — 1993. — №5. — С. 178—181.

24. Барашко А. С. Математические основы контроля дискретных устройств методом счета фрагментов // Кибернетика и сист. анализ. — 1994, №2. — С. 44—51.

ППдп. до друку 07.07.94. Формат 60x84/16. Пагнр друк. Офс. друк. Ум,-друк. арк. 1,39. Ум. фарбо-в1дб. 1,51. Обл.-вид. арк. 1,75. Тираж 100 прим. Зам. 763.

Редакцшно-видавничии В1'дд1л з полп'рафншою дьтышцею 1нституту юбернетики ¡мет В. М. Глушкова HAH УкраГни 252650 КиТв МСД 22, проспект Академика Глушкова, 40,