ЎЗБЕКИСТОН АЛОҚА АХБОРОТЛАШТИРИШ АГЕНТЛИГИ

ТОШКЕНТ АХБОРОТ ТЕХНОЛОГИЯЛАРИ УНИВЕРСИТЕТИ

5521900 – "Информатика ва ахборот технологияси" бакалавриатура йўналиши талабалари учун

"Ҳисоблаш тизимларининг ахборот асослари" фани бўйича курс ишига

УСЛУБИЙ КЎРСАТМАЛАР

Тошкент - 2008

Тузувчилар: Салим Каримович Ғаниев

Абдухалил Абдужалилович Ғаниев

"Компьютер тизимлари ва тармоқлари" кафедраси

Тақризчилар: Расулова С.С. - ТАТУ, "Татбиқий информатика" кафедраси доценти, т.ф.н.

Абдуллаев М.М. – ТДТУ "Автоматлаштириш ва бошқарув" кафедраси доценти, т.ф.н.

I. Курс ишининг мақсади ва мазмуни

Курс ишининг асосий мақсади арифметик амаллар бажарилиши алгоритмларининг граф-схемаларини ишлаб чиқиш ва бу алгоритмларни амалга оширувчи бошқариш автоматлар структураларини қуриш бўйича амалий кўникмаларга эга бўлиш.

Қўйилган мақсадга талабалар томонидан мустақил тарзда автоматнинг берилган операцион тизимида қатор микроамаллар бажарилиши алгоритмини ишлаб чиқиш, ушбу алгоритмларни берилган базисдаги мантиқий схемаларда амалга оширувчи бошқариш автоматаларини қуриш орқали эришилади.

Курс ишининг намунавий тематикаси:

"Арифметик амалларнинг берилган алгоритмини амалга оширувчи қурилманинг бошқариш автоматини синтезлаш"

II. Топшириқлар

Курс ишига топшириқлар бошқариш автоматини синтезлаш учун дастлабки маълумотлар ва чегараланишлар наборини ўз ичига олади. Топшириқларнинг барча вариантлари 1-жадвалга киритилган.

1-жадвал.

№	Амаллар	Амаллар бажарилиши коди	Хотира элементи хили	Автомат хили
1	±	ТесК	D	Мур
2	х	ТК	RS	Мили
3	÷1	ТК	JK	Мур
4	÷2	ТК	D	Мили
5	х2	ТК	JK	Мур
6	±	ТесК	JK	Мили
7	х	ТК	D	Мур
8	х2	ТК	RS	Мили
9	÷1	ТК	D	Мили
10	÷2	ТК	RS	Мур
11	±	ҚК	T	Мили
12	х	ТК	T	Мур
13	÷1	ТК	D	Мили
14	÷2	ТК	RS	Мур
15	х2	ТК	T	Мили
16	±	ҚК	D	Мур
17	х	ТК	JK	Мили
18	х2	ТК	T	Мили
19	÷1	ТК	T	Мур
20	÷2	ТК	JK	Мур

Жадвал қатори битта вариантни ифодалайди ва вариант тартиб рақами гуруҳ бўйича рўйхатнинг тартиб рақами орқали аниқланади.

1-жадвалда қўйидаги белгилашлар ишлатилган:

± - алгебраик қўшиш/айириш;

х – оддий кўпайтириш;

х2 – тезлаштирилган кўпайтириш (кўпайтирувчининг икки хонасини тахлиллаш билан).

÷1 – қолдиқни тиклаб бўлиш;

÷2 – қолдиқни тикламасдан бўлиш;

ТК – тўғри код;

ТесК – тескари код;

ҚК – қўшимча код.

III. Ишни бажариш босқичлари

Қатъий (схемали) мантиқли бошқариш автоматини синтезлашда қуйидаги босқичларни ажратиш мумкин:

1. Автоматнинг операцион қисми структурасини ишлаб чиқиш.

2. Бажарилувчи амал алгоритмининг мазмунли граф-схемасини ишлаб чиқиш.

3. Амал алгоритмининг функционал граф-схемасини ҳосил қилиш.

4. Амал алгоритмининг белгиланган граф-схемасини ҳосил қилиш.

5. Автомат графини қуриш.

6. Автомат ҳолатларини кодлаш.

7. Ўтишларнинг структуравий жадвалини тузиш.

8. Чиқиш йўли сигналлари ва қўзғатиш сигналлари учун мантиқий функция системаларини аниқлаш ва уларни биргаликда минималлаштириш.

9. Бошқариш автоматининг функционал схемасини қуриш.

IV. Қатъий (схемали) мантиқли бошқариш автоматини синтезлаш мисоли

Қуйида қўзғалмас вергулли сонларни қўшиш (айириш) амалининг бажарилишини таъминловчи қатъий (схемали) мантиқли бошқариш автоматини синтезлашда юқорида келтирилган босқичларнинг амалга оширилиши келтирилган.

Қўшиш (айириш) амалини параллел усулда бажаришда сонларни ифодалаш учун модификацияланган кодлардан фойдаланилади. Бундай кодларда ишора учун иккита хона ажратилади (00), (11), (01) ва (10). Қўшиш қуйидаги адгоритм бўйича амалга оширилади:

- агар операнд ишораси мусбат бўлса, у амалда тўғри модификацияланган кодда иштирок этади. Агар операнд ишораси манфий бўлса, у амалда тескари модификацияланган кодда иштирок этади.

- операндларнинг иккили коди барча хоналари (рақам ва ишора хоналари) бўйича қўшилади; бунда бирга тенг бўлган катта ишора хонасидан кўчириш қиймати сигнали йиғиндининг кичик хонасига узатилади;

- йиғинди ишора хоналарининг қиймати "00"га тенг бўлса, йиғинди мусбат қийматга эга ва тўғри кодда ифодаланган бўлади;

- йиғинди ишора хоналарининг қиймати "11"га тенг бўлса, йиғинди манфий қийматга эга ва тескари кодда ифодаланган, йиғиндининг тўғри кодини олиш учун йиғиндининг рақам хоналарини инвертирлаш лозим бўлади;

- йиғинди ишора хоналарининг қиймати "01" ёки "10"га тенг бўлса, натижа машина хона тўрининг тўлиб тошишига олиб келади.

1. Автомат операцион қисмининг структурасини ишлаб чиқиш..

Юқорида келтирилган алгоритм бўйича қўшиш амалини бажарувчи автомат операцион қисмининг структураси 1-расмда келтирилган.

Ушбу схемада n+2 хонали тўпловчи жамлагич ишлатилади. Жамлагич тескари боғланиш занжири билан қамраб олинган бўлиб, бу занжир орқали жамлагичнинг катта ишора хонасидан кўчириш қиймати сигнали жамлагичнинг кичик хонасига узатилади.

Биринчи қўшилувчи жамлагичда сақланади деб фараз қилинади. Иккинчи қўшилувчи регистрда сақланади. Натижа эса чиқиш йўли шинасида параллел кодда шаклланади.

Автомат операцион қисмида қуйидаги микроамаллар бажарилади:

(айириш амали учун)

Автомат операцион қисмида қуйидаги мантиқий шартлар (огоҳлантирувчи сигналлар) ишлатилади:

2. Қўшиш амали алгоритмининг мазмунли граф-схемасини ишлаб чиқиш.

Қўшиш (айириш) амали алгоритмининг мазмунли граф-схемаси

2-расмда келтирилган.

3. Алгоритмнинг функционал граф-схемасини ҳосил қилиш.

Алгоритмнинг функционал граф-схемасини ҳосил қилиш босқичида алгоритм графи оператор учлари микрокомандалар символлари билан, шарт учлари эса мантиқий шартлар билан белигиланади ва улар мос учлар ичига ёзилади.

Бизнинг мисол учун

y₅=Y₁; y₂y₃=Y₂; y₁,y₃=Y₃; y₉=Y₄

SignSM=P₁, SignRG=P₂

Қўшиш (айириш) амали алгоритмининг функционал граф-схемаси

3-расмда келтирилган.

4. Алгоритмнинг белгиланган граф-схемасини ҳосил қилиш.

Мили автомати асосида бошқариш автоматини синтезлашда белгиланган граф-схемани ҳосил қилиш қуйидаги қоида бўйича бажарилади:

- бошланиш учидан кейинги учнинг кириш йўли ва тамом учининг кириш йўли "а₁" символи билан белгиланади;

- оператор учларидан кейинги барча учлар белгиланиши шарт;

- агар учнинг кириш йўли белгиланса, у фақат битта символ билан белгиланади;

- бошланиш ва тамом учларидан ташқари барча учлар ҳар хил символлар билан белгиланади.

Мур автомати асосида бошқариш автоматини синтезлашда белгиланган граф-схемани ҳосил қилиш қуйидаги қоида бўйича бажарилади::

- бошланиш ва тамом учлари "а₁" символи билан белгиланади;

- барча оператор учлари белгиланиши шарт;

- ҳар хил оператор учлари ҳар хил символлар билан белгиланади.

4- расмда "а" ва "б" да, мос ҳолда, Мили ва Мур автоматлари асосида автоматлар синтезлашдаги алгоритмнинг белгиланган граф-схемалари келтирилган:

5. Автомат графини қуриш.

Алгоритмнинг белгиланган граф-схемаси бўйича Мили автоматининг графи қуйидагича қурилади. Автомат ҳолатларига мос граф учлари қўйиб чиқилади. Графнинг а_i учдан чиқувчи ёйлари аниқланади. Бунда графнинг ҳар бир ёйига алгоритм граф-схемасидаги а_i нуқтадан а_j нуқтага ягона оператор учи орқали ўтувчи йўл мос келади (). Тамом ва бошланиш учларига борувчи ёйлар бундан истисно.

Алгоритмнинг белгиланган граф-схемаси бўйича Мур автоматининг графи қуйидагича қурилади. Автомат ҳолатларига мос граф учлари қўйиб чиқилади. ўтишнинг ҳар бир йўлига кириш йўли сигнали P(a_i, a_j) таъсирида автоматнинг а_i ҳолатидан ҳолатига ўтиш, a_ia_j ўтиш йўлига эса – бирлик сигнали таъсирида a_i ҳолатидан a_j холатига ўтиш мос келади.

5-расм "а" ва "б"да, мос ҳолда, Мили ва Мур автоматларининг графлари келтирилган.

6. Автомат ҳолатларини кодлаш.

Автомат ҳолатларини кодлаш автомат ҳолатларини тўплами билан хотира элементлари тўплами орасида ўзаро бир маъноли мосликни ўрнатишдан иборат. Соддаликни таъминлаш мақсадида хотира элементлари сифатида RS – триггерлардан фойдаланамиз ва уларни Т₁,…,Т_r каби белгилаймиз.

Автоматнинг бир ҳолатдан иккинчи ҳолатга ўтиши хотира элементлари ҳолатларининг ўзгариши ҳисобига амалга оширилади. Масалан автомат 0101 кодли ҳолатдан 1001 кодли ҳолатга ўтса, T₁ триггер "0" ҳолатидан "1" ҳолатига, T₂ триггер эса "1" ҳолатидан "0" ҳолатига ўтади. Т₃ ва Т₄ триггерларнинг ҳолати ўзгармайди.

Бизнинг мисолда Мили автомати учун тўртта ҳолат мавжуд, демак иккита триггер ишлатиш кифоя, яъни

Мур автомати учун эса олтита ҳолат мавжуд, демак учта триггер ишлатилса кифоя, яъни

7. Ўтишларнинг структуравий жадвалларини тузиш.

Кўп сонли ҳолатларига ва ўтишларга эга бўлган автоматларни ифодалашда графлардан фойдаланиш кўзга ташланувчанликнинг йўқолишига олиб келади. Шу сабабли, графларни структуравий жадваллар кўринишида ифодалаш афзал ҳисобланади. Структуравий жадваллар тўғри ва тескари бўлади. Тўғри структуравий жадвалда барча ўтишлар кетма-кет тарзда, аввал биринчи ҳолатдан, кейин иккинчи ҳолатдан ва ҳ. ёзилади. Тескари структуравий жадвалда аввал биринчи ҳолатга барча ўтишлар, кейин иккинч ҳолатга барча ўтишлар ва ҳ. ёзилади.

Равшанки, автомат ўтишларининг структуравий жадвалларини (тўғри ва тескари) бевосита алгоритмнинг белгиланган граф-схемаси бўйича тузиш мақсадга мувофиқ ҳисобланади, яъни автомат графини қуриш шарт эмас, чунки жадвал рўйхат кўринишидаги граф ҳисобланади.

2 ва 3-жадвалларда, мос ҳолда Мили ва Мур автоматларининг тескари структуравий жадваллари келтирилган.

2-жадвал.

Дастлабки ҳолат	Дастлабки ҳолат коди	Ўтиш ҳолати	Ўтиш ҳолати коди	Кириш йўли сигналлари	Чиқиш йўли сигналлари	Қўзғатиш сигналлари
а3 а3 а4 а4	01 01 11 11	а1	00		Y4 - Y4 -	R2 R2 R1 R2 R1 R2
a1	00	a2	10	P1	Y1	S1
а1 a1 а2 а2	00 00 10 10	a3	01		Y2 Y3 Y2 Y3	S2 S2 R1 S2 R1 S2
а3	00	a4	11	P1	Y1	S1

3-жадвал.

Дастлабки ҳолат	Дастлабки ҳолат коди	Ўтиш ҳолати	Ўтиш ҳолати коди	Кириш йўли сигналлари	Қўзғатиш сигналлари
a3 а4 а5 а6	010 110 001 101	а1(-)	000 000 000 000	1	R2 R1R2 R3 R1 R3
a1	000	a2(Y1)	100	P1	S1
a1 а2	000 100	a3(Y2)	010		S2 R1 S2
a1 a2	000 100	a4(Y3)	110		S1 S2 S2
a3 a4	010 110	a5(Y1)	001	P1	R2 S3 R1R2 S3
a3 a4 a5	010 110 001	a6(Y4)	101		S1R2 S3 R2 S3 S1

Мур автоматининг тескари структуравий жадвалда битта устун кам, чунки чиқиш йўли сигнали ўтиш ҳолати ёнига ёзилади.

8. Чиқиш йўли сигналлари ва қўзғатиш сигналлари учун мантиқий функция системаларини аниқлаш ва уларни биргаликда минималлаштириш.

2-жадвалга мувофиқ чиқиш йўли сигналлари ва қўзғатиш сигналлари учун мантиқий функция системалари қуйидаги кўринишга эга:

(1)

Ушбу мантиқий функцялар системаларини биргаликда минималлаштириш натижасида қуйидагини оламиз:

(2)

3-жадвалга мувофиқ чиқиш йўллари сигналлари ва қўзғатиш сигналлари учун мантиқий функция системалари қуйидаги кўринишга эга:

(3)

Ушбу мантиқий функция системаларини биргаликда минималлаштириш натижасида қуйидагини оламиз:

(4)

2 ва 4- ифодалар мос ҳолда, синтезланаётган Мили ва Мур автоматлари комбинацион қисмларининг математик моделларидир.

6 ва 7-расмларда, мос ҳолда, қўзғалмас вергулли сонлар устида қўшиш (айириш) амалининг бажарилишини таъминловчи Мили ва Мур автоматларининг функционал схемалари келтирилган.

Ҳисоблаш қурилмаси ишга туширилганда автомат триггерлари ихтиёрий ҳолатга ўрнатилади. Автоматни дастлабки ҳолатга ўтказиш учун "ПУСК" сигнали ишлатилади.

V. Тушунтириш матнининг мазмуни

Курс ишига тушунтириш матни қуйидаги ахборотни ўз ичига олиши зарур.

1. Титул варағи.

2. Бошқариш автоматини синтезлашга топшириқ.

3. Бажариладиган амал алгоритми.

4. Бошқариш автомати операцион қисмининг структуравий схемаси.

5. Бошқарувчи ва огоҳлантирувчи сигналларнинг вазифалари.

6. Бажариладиган амал алгоритмининг мазмунли граф-схемаси.

7. Бошқариладиган амал алгоритмининг функционал граф-схемаси.

8. Бажариладиган амал алгоритмининг белгиланган граф-схемаси.

9. Бошқариш автомати графи.

10. Бошқариш автомати ҳолатларини кодлаш.

11. Ўтишларнинг тескари структуравий жадвали.

12. Чиқиш йўли сигналлари ва қўзғатиш сигналлари учун мантикий функция системалари ва уларни биргаликда минималлаштириш.

13. Бошқариш автоматининг функционал схемаси.

14. Хотима.

15. Фойдаланилган адабиётлар рўйхати.

Адабиётлар

1. А.П.Жмакин. Архитектура ЭВМ. Уч.пособие. Санкт Петербург, БХВ-Петербург, 2006.

2. Б.Я. Цилькер, С.А., Орлов. Организация ЭВМ и систем: Учебник для вузов. – СПб: Питер,2004.

3. С.К. Ғаниев, М.М.Каримов, Н.М.Мамбетов. "Ҳисоблаш системаларининг информацион асослари: Олий ўқув юрт.талаб. учун дарслик. – Тошкент Давлат техника университети, 2002.

4. А.Я. Савельев. Основы информатики. Учеб. для ВУЗов- М.: Изд-во МГТУ им А.Э. Баумана, 2001.