6-тақырып Автоматтардың құрылымдық синтезі
6.1 Автоматтардың құрылымдық синтезі
Автомат кестесін құру үрдісі әдетте екі қатысты бағыныңқы деңгейге: абстрактілі және құрылымдық синтез деп екіге бөлінеді.
Абстрактілі синтез деңгейінде берілген жұмыс шарттарына сүйеніп, ауысым және автомат шығыстарының кестесін құру орындалады.
Құрылымдық синтездің мәні автоматтық функционалды кесте құру. Құрылымдық синтез деңгейінің шығыс мәліметтері болып ауысым мен автомат шығыстарының таблицалары, логикалық элементтер жүйесі, жады элементінің типі, сондай-ақ кесте жұмысы мен сапасына қойылатын қосымша талаптар, мысалы: жұмыс уақыты, тәуекелдің жіберілуі, қоршаған ортамен байланыс шарты, құны және т.б. табылады.
Шығыс мәліметтер мен құрылымдық синтез деңгейінде шешілетін сұрақтар шеңбері айтарлықтай өзгеруі мүмкін екенін атап өткен жөн. Мысалы құрылымдық синтезде кейбір жағдайларда ізделіп отырған кест енің таңдау міндетін шешеді.
Қарастырылып жатқан кесте екі бөліктен: комбинациялық кесте мен жады элементтерінен тұрады. Жады элементтерінің шығыс сигналдарына сәйкес келетін ауыспалылары автоматтың ішкі ауыспалылары деп аталады. ауыспалылар кестеде жады элементтерінің жай-күйін өзгертетін кіріс сигналдарын ерекшелеу үшін қолданып, қоздыру функциясы деп аталады. Жады элементі ретінде тәжірибеде элементарлы автоматтар жиі қолданылады.
Келтірілген кестеде кіріс ауыспалыларының мағына жиынтығы абстрактілі автоматының кіріс алфавитінің әріптеріне, шығыс ауыспалылар жиынтығы шығыс алфавитінің әріптеріне, - абстрактілі автоматтың күіне сәйкес келеді.
Жалпы жағдайда келтірілген құрылымдық автомат кестесіндегі комбинациялық кесте түрлі міндеттерді шешуі мүмкін. Егер бұл кестені әрбіреуі жеке ішінаралық кестемен шешілетіндей екі ішінаралық кестеге бөліп тастасақ, онда автоматтық құрылымдық кестесі 2-суретте келтірілгендей түрде көрсетілуі мүмкін. Бұл кестеде комбинациялық кесте шығыс функциясын өндіреді, қоздырғыш функциясын, кодтарды түрлендіруші –шығыс сигналдарын қайта кодтауға қолданылады, ал кодтарды түрлендіру –шығыс сигналдарын түрлендіруге.
және кодтарын түрлендірушілерін құрылымдық автомат кестесінде міндетті түрде болуы шарт емес, бірақ кейбір жағдайларда оларды кесте құрылымына енгізу қиындықты азайтуға жеткізіп, тұрғызу немесе автомат кестесінің жұмысын бақылау үрдісін жеңілдетеді.
Құрылымдық синтездің негізгі кезеңдері.
Құрылымдық синтез процедурасын бір-бірімен байланысты бірнеше кезеңдерге бөліп қарастыру ыңғайлы.
Автоматтың құрылымдық кестесін таңдау. Синтездің бұл кезеңі көбінесе кестенің тұрғызылу ретін анықтайды. Бұл кезеңнің негізгі қиыншылығы құрылымдық кесте таңдауда формалды критерилердің жоқтығында. Құрылымдық кестені таңдауды анықтайтын факторлардың негізгілерінің бірі жасаушының тәжірибесінде.
Кіріс және шығыссигналдарын кодтау. Кіріс сигналдарын кодтау мәні абстрактілі автоматтың pi кіріс алфавитінің әрбір әрпінде бір мәнді тәсілмен сәйкестіріледі. Бұдан кіріс алфавитінің әріптер саны түріндегі екілік ауыспалылар жиынтығының санынан аспайтыны, яғни кодтау біртекті екені анық. Осыдан шыға келе кіріс алфавитінің әріптерін кодтау үшін қажет екілік ауыспалылар санын шартынан анықтауға болады.
Шығыс сигналдарын кодтау дегеніміз абстрактілі автоматтың шығыс wi алфавитінің әріптеріне ұқсас тәсілмен шығыс ауыспалылар мәндерінің жиынтығы сәйкестіріледі. Кодтау нәтижелері әдетте кіріс және шығыс сигналдарын кодтау кестесіне енгізіледі.
Кіріс және шығыс сигналдарын кодтаудың кейбір тапсырмаларында абстрактілі синтез кезеңінде кесте жұмысының шарты негізінде беріледі. Бұндай жағдайларда автоматтың құрылымдық кестесіне кодтарды түрлендірушілер енгізілуі мүмкін.
Бұл кодтау кезінде ауыспалылар әрбір мәндерінің жиынтығына сәйкес түрде ауспалылар жиынтығы қойылады, ал әрбір ауыспалы жиынтығына ауыспалылар жиынтығы. Сондай-ақ, кіріс және шығыс сигналдарын кодтау кестесінің комбинациялық бөлігінің күрделілігіне автомат күйін кодтауға әсер еткендей әсер етеді.
Жады элементтерінің санын таңдау және автомат жай-күйін кодтау. Жай-күйді кодтау дегеніміз әрбір жай-күйіне ішкі ауыспалы жиынтығы сәйкестіріледі. Жай- күймен оларға сәйкес кодтар түрінде беріліп, автомат жай-күйін кодтау таблицасы депаталады.
Қоздырғыш функциясын тұрғызу. Қоздырғыштың функциясы автомат көшу қажет жай-күй кодын алу үшін жады элементінің кірісіне қандай сигнал беретінін анықтайды.
Құрылымдық синтездегі қоздырғыш функциясы абстрактілі автомат ауысымдарының функцияларына сәйкес келеді. Бұл сәйкестік автомат жай-күйін анықтайтын ішкі ауыспалылар және бір уақытқа қатысты кіріс ауыспалыларына қоздырғыш функциялары бағыныңқы болу керегін көрсетеді.
Шығару функциясын тұрғызу. Мили автоматында әрбір шығару функциясы шығыс сигналдар жиынтығының сәйкес компонентін анықтайды. Құрылымдық синтездегі шығыс функциясы абстрактілі автоматтың шығару функциясына сәйкес келеді. Олар y1, y2, ..., yh ішкі ауыспалылар мен кіріс ауыспалыларға бағынышты. Бұдан анықтайтын ауыспалылар мәні үнемі бір уақыт сәтіне қатысты болғандықтан, шығыс функциясы ауыстырып-қосқыш функция болып табылады:
Мур автоматының шығыс функциялары әр сәтте шығыс символдарының жиынтығын анықтайды:
6.2 Асинхронды автоматтар
Асинхронды автоматтардың немесе дәлірек айтқанда автоматтың асинхрондық моделінің ерекшелігі кіріс сигналдарының қасиеттерімен анықталады. Бұндай автоматтың кіріс сигналдары импульстік түрдегі (6.1а суреті) сигналдарға ұқсас. Бұл кезде келесі шектеуліктер алынған болатын:
Сурет 6.1 - Импульсивті және потенциалды түріндегі сигналдар
- сигналдар автомат кірісіне үнемі периодты СИ реттілігі беретін нақты бір уақытта ғана түсе алады;
- кіріс сигналдарының ұзақтығы аз ;
- автомат кірісіндегі тактілейтін сигналдардың аралығындағы уақытта сигнал болмайды. Бұндай сигналдарға тұрғызылған автомат модельдері элементтерінде гальвандық байланысы жоқ импульстік типтегі сигналдармен жұмыс істейтін кестелерге сәйкес келеді.
Асинхронды автоматтың кіріс сигналдары потенциалды түрдегі сигналдарға (6.1б суреті) ұқсас. Бұндай сигналдарға келесі қасиеттер тән болу керек: - сигнал автомат кірісінде кез келген уақытта болады;
- кіріс сигналының ұзақтығына шектеулік қойылмайды және ол кейбір минималды мөлшерінен асады; кіріс сигналдары кез келген уақытта өзгеруі мүмкін.
Аталып өткен қасиеттер асинхрондық автомат үзіліссіз жұмыс істейді деп айтуға мүмкіндік береді.
Синхрондық автоматқа сияқты екілік кіріс сигналдарын қарастырумен шектелеміз. Және бұл жағдайда асинхрондық автомат моделі потенциал түріндегі элементтерден құрылған кестелерді мазмұндау үшін қолданылуы мүмкін. Айтарлық кіріс сигналының іс-әрекетінен синхронды автомат күйіне ауысады. Потенциалды түрдегі сигналдардың келтірілген қасиеттеріне сәйкес автомат кірісінде болады және аяқталуы алдын ала белгілі болмайтын ауысым орындалған соң ғана. Осыған сәйкес бұндай ауысым орындалған соң автомат келесі кірісте сигнал өзгерісі болғанға дейін күйінде қалу керек. Мазмұндалған жайды келесі анықтама түрінде қорытуға болады. Егер автомат күйінен іс-әрекет астында күйіне ауысым жасаса, яғни , және іс-әрекеті астында күйінде қалса, онда бұндай күй тұрақты деп аталады.
Асинхрондық автомат жұмысы да синхронды түрдегі автомат сияқты ауысым кестесі мен шығыс немесе граф көмегімен мазмұндалынады. Бірақ нөлдік емес ұзақтығы бар сигналдарға ауысу бұндай мазмұндауды қиындата түседі. Алдымен асинхрондық автоматты графты құру тәсілін берілген синхрондық автоматты графы бойынша құруға тоқталайық.
(6.2а) суретінде графы келтірілген синхронды автомат берілген делік. Бұл графты құру кезінде кіріс сигналдарының ұзақтығы есептелген жоқ. Егер де шығысқа берілетін импульстік сигналдар соңғы ұзақтыққа ие болады деп санасақ, онда әр сигналдың іс-әрекеті кезінде автомат қандай күйде болу керектігін анықтай қажет.
Бұны (6.2б) суретінде көрсетілгендей әр ауысымға берілген граф асинхронды автоматты анықтайды, себебі автоматың барлық жай-күйі ұрақты болып келеді.
Сурет 6.2 - Синхронды және оған сәйкес келетін асинхронды автоматының диаграммасы
Асинхронды автоматта барлық ауысымдар таблицаларын құру кзінде қосымша қиындықтар туғызатын тұрақты жай-күйлер арасында іске асырылады. Егер күйі тұрақты болып келсе, онда жолмен анықталатын, күйімен, бағанамен, кіріс сигналымен күйінің символы ауысым таблицасының торында жазылуы керек, себебі .
Осыдан асинхронды автомат ауысым таблицасының тұрақты күйі үшін кіріс сигналы өзгергенде автомат қандай күйге өзгеру керектігін көрсететін қосымша құралдар қажет. Бұл қиындық келесі тәсілмен шешіледі. Автомат күйінің өзгеру үрдісі екі кезеңге бөлінеді.
Алдымен кіріс сигналдары өзгереді де, автомат күйі өзгермейді, ал содан кейін кіріс сигналдарының жаңа мәндеріне сәйкес жай-күй де өзгереді. Бұл үрдістің бірінші кезеңіне ескі күймен белгіленген ауысым таблицасының жолында ауысу сәйкес келеді.
Сонымен, бірінші кезең сөзсіз автоматтың ауыспалы күйіне сәйкес келетін таблицаның жаңа торын анықтайды. Бұндай күйлерді транзитивті деп атайды. Бұл торда автомат көшетін күйдің символын жазып қоямыз.
Екінші кезеңдегі күйдің өзгеруіне жаңа кіріс сигналдарымен анықталған бағана бойынша ауысудың автомат көшу қажет күйімен белгіленген жолға көшу сәйкес келеді. Екінші кезеңде қолданылатын ауысым көрсеткіштері бар тұрақты күйге сәйкес келетін символдарды дөңгелек жақшаларға алатынымызды уәделесіп алайық.
Асинхронды автоматтың ауысым мен шығыс таблицасына мысал ретінде 6.1-кестені келтіруге болады. Бұл кесте (6.2б) суретінде келтірілген граф бойынша құрылған.
Кесте 6.1 - Граф бойынша құрылған
6.1-кестеде ауысым қалай орындалатынын мысал негізінде қарастырайық. Айтарлық автомат 00 кіріс сигналдарының іс-әрекетінің астында 3 күйінде делік. Ауысым таблицасына сәйкес бұл күй тұрақты болып келеді. Егер енді кіріс сигналдарының 10-ға өзгерсе, онда автомат қандай күйге өзгеретінін табу үшін 10 сигналдарымен белгіленген үшінші жол бойынша бағанаға көшуді орындау қажет.
Бұл тәсілмен анықталған таблица торында автомат көшетін күйдің нөмірі бұл күйі-орналасқан. Тігінен 10 бағанасында жолына дейін жүре отырып бұл күйдің тұрақты екеніне көз жеткіземіз. Яғни бұл ауысым аяқталды деген сөз.
Қарастырылған мысалда бір тұрақты күйден екіншіге ауысқанда автомат бір транзиттік күйден құтқарылады. Жалпы жағдайда автомат күйінің өзгеруі бірнеше транзиттік күйлерден өтіп ауысуы мүмкін, бірақ олар ауысым таблицасының бір бағанасында орналасуы керек.
Достарыңызбен бөлісу: |