Urganch davlat universiteti fizika-matematika fakulteti matematika yo’nalishi 182-guruh talabasi holbayeva malikaning

2.2. TESKARI BOG’LANISHI BO’LMAGAN AVTOMATLAR

Elementning yuqori va quyi indeksi. To’g’ri sxema. Teskari bog’lanishi bo’lmagan avtomat. Xarakteristik funksiya. -indeksi. Kuchsiz avtomatli to’liq sistema.

O’tgan paragrafda mantiq algebrasining funksiyalarini faqat to’g’ri sxemalargina realizatsiya etishini ko’rdik. Birtaktli funksional elementlardan yasalgan sxemaning umumiy holda ishlash jarayonini ko’raylik. Sxema kirishlariga har momentda signallar majmuasi berilib turiladi. Aniqki, sxemaning chiqishidagi signal uning kirishlariga oldingi momentlarda berilgan signallar majmuasiga bog’liq bo’ladi.

Funksional elementning quyi va yuqori indekslari degan tushunchani kiritaylik.

1-ta’rif. Sxemaning kirishlariga berilgan signallar  funksional elementning chiqishida hosil bo’lishiga qadar bosib o’tilgan ichki funksional elementlarning maksimal soniga ( elementning o’zi ham kiradi) elementning yuqori indeksi va minimal soniga quyi indeksi deb aytiladi. funksional element sxemaning chiqish elementi (ya’ni ozod chiqishga ega bo’lgan elementi) bo’lsin. U vaqtda elementning yuqori va quyi indekslarini mos ravishda va bilan belgilaymiz.

Demak, sxema to’g’ri bo’lishi uchun biror elementning kirishlariga chiqishlari ulangan hamma funksional elementlarning yuqori indekslari teng bo’lishi kerak (etarli shart).

Sxema ta’rifiga asosan, vaqt momentida sxemaning chiqishidagi signal uning kirishlariga dan momentgacha berilgan signallar naboriga bog’liq bo’ladi. Demak, momentdagi chiqish signali uning kirishlariga ketma-ket berilgan signallar majmuasining funksiyasi bo’ladi:

.

Bu yerda -mantiq algebrasining argumentli funksiyasi va - kirishlarga momentda berilgan signallar majmuasi bo’ladi. Agar sxema to’g’ri bo’lsa, u holda funksiya qat’iyan momentda (ya’ni , albatta ) berilgan faqatgina bitta signallar majmuasiga bog’liq bo’ladi va sxema funksiyani ushlab turish vaqti ( takt) bilan realizatsiya etadi.

2-ta’rif. kirishlarga va bitta chiqishga ega bo’lgan qurilma berilgan bo’lsin (3.1-shakl) Har bir momentda uning kirishlariga 0 yoki 1 signal berilganda, chiqishida har bir momentda 0 yoki 1 signal hosil bo’ladi. CHiqishdagi signal kirishlarga dan momentgacha ketma-ket berilgan signallar majmuasining funksiyasi bo’ladi:

.

Bu yerda momentda berilgan signallar majmuiga teng bo’ladi. U vaqtda bunday qurilmaga teskari bog’lanishi bo’lmagan avtomat deb aytiladi. Mantiq algebrasining funksiyasi uning xarakteristik funksiyasi, -indeksi, -ushlab turish vaqti deb aytiladi.

Agar teskari bog’lanishi bo’lmagan ikkita avtomatlarning ₁ va ₂ xarakteristik funksiyalari faqatgina soxta argumentlari bilan farq qilsa, u holda bunday avtomatlarga ekvivalent avtomatlar deb aytiladi.

Har qanday funksional element birorta teskari bog’lanishi bo’lmagan avtomatni ifodalaydi. Bu element uchun xarakteristik funksiya u realizatsiya qiladigan funksiya bilan mos tushadi, indeks va ushlab turish vaqti bo’lsa birga teng bo’ladi.

SHunday qilib, bir taktli funksional elementlardan tuzilgan har qanday sxema teskari bog’lanishi bo’lmagan avtomatni ifodalaydi. Aslida funksional elementlar birtaktli bo’lishi shart emas. Faqatgina sxemaning quyi va yuqori indekslarini boshqacha hisoblash kerak:

elementning quyi va yuqori indekslari deb, sxemaning kirishlariga berilgan signallar elementning chiqishida hosil bo’lguncha bosib o’tilgan funksional elementlar ushlab turish vaqtlari yig’indisining mos ravishda minimumi va maksimumiga aytiladi.

Har qanday teskari bog’lanishi bo’lmagan avtomat o’z navbatida bitta funksional elementlardan tuzilgan sxemani ifodalaydi (ushbu fikrning to’g’riligini isbotlashni o’quvchiga havola etamiz).

3-ta’rif. Funksional elementlardan tuzilgan sxema bilan ifodalanadigan avtomat teskari bog’lanishi bo’lmagan avtomatidan faqatgina ushlab turish vaqti bilan farq qilsa, bu avtomat avtomatni realizatsiya etadi deyiladi.

4-ta’rif. Agar har qanday teskari bog’lanishi bo’lmagan avtomatni funksional elementlardan tuzilgan sxema orqali realizatsiya etish mumkin bo’lsa, u holda funksional elementlar sistemasi kuchsiz avtomatli to’liq sistema deb aytiladi. Birtaktli funksional elementlar sistemasi to’liqligining yetarli va zarur sharti elementlar sistemasining kuchsiz avtomatli to’liqlik shartiga mos keladi.

2.3. TESKARI BOG’LANISHI BO’LGAN FUNKSIONAL ELEMENTLARDAN SXEMALAR YASASH.

Chekli avtomat haqida umumiy tushunchalar

Teskari bog’lanishli funksional elementlar. Xotirada saqlovchi qurilma. Sxemaning (t+1) momentdagi holati.  avtomat. Avtomat holatlari. Avtomat ishining natijalari.

Hozirgacha bizlar funksional elementlardan yasalgan teskari bog’lanishi bo’lmagan sxemalarni ko’rib o’tdik. Bunday cheklashni biz nulьtaktli funksional elementlardan sxemalar yasash masalasini yechish uchun qo’ygan edik, chunki, aks holda, bunday sxemalarning ish jarayonini yoritish mumkin emasdi.

1-shakl

1-shaklda ko’rsatilgan funksiyani realizatsiya qiladigan sxemaning ish jarayonini ko’rib o’taylik. funksionalni birtaktli element deb hisoblaymiz. Agar biror momentda  ning chiqishida 1 signal paydo bo’lsa, u vaqtda shu momentning o’zida o’sha signal uning kirishida paydo bo’ladi va momentda uning chiqishida 0 signal paydo bo’ladi va hokazo. Natijada, funksional elementning chiqishida ketma-ket 1,0,1,0,1,0,...... signallar paydo bo’ladi va nulьtaktli funksional element bo’lgan vaqtdagi qarama-qarshiliklar o’z-o’zidan yo’qoladi. Bu sxemani “qo’ng’iroq” sxemasi deb atash mumkin, chunki qo’ng’iroqda bir taktda qarama-qarshi qiymatlarga o’zgaradigan ketma-ket beriladigan signallar foydalaniladi.

Bu paragrafda biz quyidagi shartlarni qanoatlantiruvchi teskari bog’lanishli sxemalarni ko’rib chiqamiz:

1) Qurilmaning elementlari orasida faqat va faqat bittaginasi ozod chiqishga ega;

2) elementning har bir kirishi elementlarning faqatgina bittasining chiqishi bilan ulanadi.

Yuqoridagi shartlarni qanoatlantiruvchi bir taktli funksional elementlardan yasalgan teskari bog’lanishli sxemalarning ishlash jarayonini ko’rib o’taylik. Sxema teskari bog’lanishli bo’lganligi uchun uning chiqishidagi signal na faqat sxema kirishlariga berilgan signallar majmuidan, balki uning ichki elementlarining chiqishidagi signallarga ham bog’liq bo’ladi. Bu keyingi signallar sxema kirishlariga berilgan signallarga bog’liq bo’lmasligi ham mumkin yoki ancha oldin berilgan kirish signallariga bog’liq bo’lishi mumkin. Masalan, tsikl elementlarining kirishi sxema kirishi bo’lmasligi mumkin. 16 - shakldagi birtaktli element funksiyani, birtaktli elementi bo’lsa funksiyani realizatsiya qiladilar. -bir-taktli ushlab turish elementi.

f f

 

x y x y z

a) b)

2-shakl.

Agar 2,a - shakldagi sxemaning kirishiga istalgancha ancha oldin 1 signali berilgan bo’lsa, u holda shu signalning o’zi doimo uning chiqishida paydo bo’lib turadi (ya’ni signal xotirada saqlanadi).

2,b-shakldagi sxemada signal faqat bo’lgandagina xotirada saqlanadi. signalni berib, xotirani tozalashimiz mumkin. SHundan keyingina ning yangi qiymatini xotirada saqlay olamiz ( qiymatda). Real sxemalarda “xotirada saqlovchi qurilma” tsikl yordamida realizatsiya etiladi.

Teskari bog’lanishli sxema ish jarayonining xarakteristikasini ifodalashda uning ichki elementlarining holatini hisobga olish kerak.

- teskari bog’lanishli sxema va - uning elementlari bo’lsin. Bu yerda - chiqish elementi bo’lsin, ya’ni ozod chiqishga ega bo’lgan elementdir. elementning chiqishidagi vaqt momentidagi signalini bilan belgilaymiz ( 0 yoki 1 ga teng). Sxema chiqishida momentdagi signal ga teng bo’ladi.

ga sxemaning vaqt momentidagi holati deb aytiladi. momentda sxema kirishlariga berilgan signallarni bilan va orqali ularning majmuini belgilaymiz. U vaqtda sxemaning momentdagi holati , sxemaning momentdagi va lari orqali bir qiymatli aniqlanadi, ya’ni

=.

Demak, momentdagi elementlarning chiqishidagi signallar ularning kirishlariga momentda berilgan signallarga bog’liq bo’lar ekan, ya’ni momentda sxemaning kirishlariga berilgan signallar va elementlarning shu momentdagi chiqish signallariga bog’liqdir.

Aniqrog’i, argumentli ta mantiq algebrasi funksiyalarining majmuidan (to’plamidan) iborat bo’ladi. Bu argumentlarning ayrimlari soxta bo’lishi mumkin.

Masalan, uchun faqat quyidagi argumentlar soxta emas: elementning kirishlariga chiqishlar ulangan funksional elementlarga va sxemaning kirishlari bevosita elementning ham kirishlari deb hisoblanadigan signallarga mos keladigan argumentlar. Agar faqat shunday soxta emas argumentlarni hisobga olsak, u vaqtda funksiya element realizatsiya etadigan funksiyaga mos keladi va yuqoridagi formula vaqt momentida elementlarning chiqishlarida momentda ularning kirishlariga berilgan signallar majmuiga bog’liq bo’lgan qanday signal paydo bo’lishini ko’rsatadi.

Ta’rif. - uzunlikdagi ikkilik majmualarning biror to’plami bo’lsin. Agar argumentli ta qisman aniqlangan mantiq algeb-rasining funksiyalaridan iborat majmui ko’rsatilgan bo’lsa, u holda ruxsat etilgan holatlar to’plamida kirishga ega bo’lgan avtomat berilgan deb aytamiz.

Bu yerda funksiyalar shunday uzunlikdagi ikkilik majmualarda aniqlanganki, ulardan ta elementi kiruvchi majmua bo’ladi va shu majmuadagi funksiyalarning qiymati ga kiradi. to’plamdagi elementlar soniga avtomatning xotirasi deb aytiladi. Agar avtomatning boshlang’ich holati , biror natural son (ushlab turish vaqti deb aytiladi) va har bir vaqt momentida uzunlikdagi kirish signallar majmui berilgan bo’lsalar, u holda avtomatning ish jarayoni aniqlangan deb aytiladi.

Agarda avtomatning ish jarayoni aniqlangan bo’lsa, u vaqtda lar uchun uning ketma-ket holatlari

=,

formula orqali aniqlanadi. Bu formulaga avtomatning holatlar tenglamasi deb aytiladi. Ravshanki, avtomatning har qanday vaqt momentidagi holati bo’ladi. ketma-ketligiga avtomatning chiqishi (ishning natijasi) deb aytiladi. Agar va faqatgina ga bog’liq bo’lsa, u holda avtomat mantiq algebrasining funksiyasiga aylanadi.

Qabul qilingan belgilashlarda birtaktli funksional elementlardan yasalgan teskari bog’lanishli sxema quyidagi xarakteristikaga ega bo’lgan avtomatni ifodalaydi: ; momentdagi sxema elementlar chiqishla-ridagi signallari; -hamma mumkin bo’lgan elementlar chiqishidagi signallar majmui.

SHunday qilib ushlab turish vaqtiga ega bo’lgan chekli avtomatni birtaktli funksional elementlardan yasalgan teskari bog’lanishli sxema orqali ifodalash mumkin.