Pages
▼
Monday, May 20, 2013
Sunday, May 19, 2013
Գետաշեն-Геташен-Getashen
Արծիւների բոյնն ես, չքնաղ Գետաշէն
Բարբարոս ցեղերի անդադար սանձով
Դու քաջերի օրրան, իմ քաջ Գետաշէն:
Բարբարոս ցեղերի անդադար սանձով
Դու քաջերի օրրան, իմ քաջ Գետաշեն:
Կրկ.
Չորս կողմս անդունդ է
Ճամփեքդ փակւած
Երկնքում սեւմութ, ամպ է կուտակւած:
Հոգիդ հայկական, շէներն էլ լքւած
Դու կաս ու կմնաս, յաւերժ Գետաշէն:
Ջահել տղերք դու քիչ ունես Գետաշէն,
Բայց ծերերն էլ մի բանով պակաս չեն:
Ամէն մի կին մի ֆիդաի տնաշէն,
Քեզ յաղթել չի լինի, իմ քաջ Գետաշէն:
Ամէն մի կին մի ֆիդաի տնաշէն,
Քեզ յաղթել չի լինի, իմ քաջ Գետաշէն:
Կրկ.
Դու պիտի դիմանաս ու կանգուն մնաս,
Հակառակ թշնամուն պիտի շէնանաս,
Մայր Հայաստանին պիտի դու միանաս,
Արցախի դարպասն ես իմ քաջ Գետաշէն:
Մայր Հայաստանին պիտի դու միանաս,
Արցախի դարպասն ես իմ քաջ Գետաշէն:
Կրկ.
Thursday, May 16, 2013
Wednesday, May 15, 2013
Thursday, May 9, 2013
Մայիսի 9 ----------------9 МАЯ!
Մայիսի 9-ին հայ ժողովուրդը տոնում է Հայրենական մեծ պատերազում տարած հաղթանակի և Շուշիի ազատագրման օրերը.
Спасибо дедам за ВЕЛИКУЮ ПОБЕДУ, внукам за ШУШИ! 9 МАЯ - ДЕНЬ ПОБЕДЫ! ПОЗДРАВЛЯЮ ВСЕХ С ПРАЗДНИКОМ ВЕЛИКОЙ ПОБЕДЫ - 9 МАЯ! ЖЕЛАЮ ВСЕМ МИРНОГО НЕБА НАД ГОЛОВОЙ!
Monday, May 6, 2013
Wednesday, May 1, 2013
ԲՈՒԼՅԱՆ ՖՈՒՆԿՑԻԱՆԵՐԻ ՀԱՍԿԱՑՈՒԹՅՈՒՆԸ
Բուլյան ֆունկցիաների հասկացությունը
Բուլյան ֆունկցիաների հասկացությունը
Բուլյան են կոչվում այն ֆունկցիաները (f(x1, x2,…xn)), որոնք, ինչպես և նրանց արգումենտները, կարող են ընդունել երկու արժեք` «0» և «1»:
Բոլոր n արգումենտներից f(x1, x2,…xn)ֆունկցիան որոշված է 2n հավաքածուներում կամ կետերում:
Երբեմն այդ հավաքածուների բազմությունը կոչվում է բուլյան տարածություն, իսկ այդ տարածության յուրաքանչյուր տարր` բուլյան վեկտոր:
Օրինակ
գB = { 0,1}
գB2 = {0,1} Բ {0,1} = {00, 01, 10, 11}
Բուլյան ֆունկցիաներն են f(x) : Bn ® B;
B = {0,1};
X= {x1, x2, … xn} Կ Bn; xj Կ B;
x1, … xn –փոփոխականներն են, x1, x1, x2 , x2 . . . – տառերը ( литералы.)
Տառերը `դրանք փոփոխականներն են կամ նրանց ժխտումները:
Օրինակ եթե x1 տառը ներկայացնում է f = {x|x1=1}, ապա x1 –ը ներկայացնում է g = {x|x1=0} տրամաբանական ֆունկցիան:
Եթե g(x) = f(x) բոլոր Bn ֆունկցիայի հավաքածուներն են, ապա g(x) և f(x) տրամաբանական ֆունկցիաները համարժեք են:
Ֆունկցիան կոչվում է ամբողջովին որոշված, եթե ցան¬կա-ցած հավաքածուի համար հայտնի է նրա արժեքը:
Իսկ եթե որոշ հավաքածուներում ֆունկցիայի արժեք¬ները որոշված չեն, ապա ֆունկցիան կոչվում է ոչ լրիվ կամ մասնակի որոշված:
Կան ընդամենը n փոփոխականների 2n աստիճանի 2 տարբեր ֆունկցիաներ, այդ թվում «0»-ի և «1»-ի հաստատունները և տրիվիալ ֆունկցիաները:
Բուլյան ֆունկցիաների ներկայացման ձևերը
1. Աղյուսակի միջոցով
2. Անալիտիկ ներկայացում (բանաձևերի միջոցով)
3. BDD-ների միջոցով
4. Բուլյան ցանցերի միջոցով
5. Սխեմաների միջոցով:
Աղյուսակի միջոցով տրված է ֆունկցիա
“1” {2,3,5,7,10,11,13,14,15}
x1 x2 x3 x4 f(x1x2 x3 x4)
0 0 0 0 0
0 0 0 1 0
0 0 1 0 1
0 0 1 1 1
0 1 0 0 0
0 1 0 1 1
0 1 1 0 0
0 1 1 1 1
1 0 0 0 0
1 0 0 1 0
1 0 1 0 1
1 0 1 1 1
1 1 0 0 0
1 1 0 1 1
1 1 1 0 1
1 1 1 1 1
Ֆունկցիայի ներկայացումը BDD-ի
միջոցով
BDD-ն երկուական լուծումների դիագրամների (Binary Decision Diagrams, BDD)` գրաֆ է, որը հանդիսանում է սեմանտիկ ծառերի մոդիֆիկացում: BDD-ներում ֆունկցիայի միևնույն արժեքով հանգույցները միացված են: BDD-ները օգտագործում են որպես բուլյան ֆունկցիաների ներկայացման կոմպակտ ձև: Այս ներկայացման ձևը արդարացված է այն դեպքում, երբ պետք է բազմակի անգամ հաշվարկել բուլյան ֆունկցիայի արժեքը փոփոխականների տարբեր հավաքածուների համար:
ՍԵմանտիկ ծառ
Ծառի գագաթը նշանակենք x1 : Մյուս շարքի գագաթները կնշանակենք x2 փոփոխականով, հաջորդ շարքի գագաթները` x3 փոփոխականով, իսկ ներքևի շարքի գագաթները կնշանակենք ֆունկցիայի արժեքներով:
Սեմանտիկ ծառից BDD-ի կառուցման ալգորիթմը կայանում է հետևյալում`
1. Ֆունկցիայի կրկնող արժեքների հեռացում,
2. Կրկնող տեստային հանգույցների հեռացում: Եթե BDD- ում երկու տարբեր միջանկյալ հանգույցներ համարվում են ենթադիագրամի կառուցվածքային համարժեք արմատներ, ապա նրանց փոխարինում են մեկ արմատով:
3. Ավելորդ տեստային հանգույցների հեռացում: Եթե որոշ t դուրս եկած երկու կողերը ցույց են տալիս միևնույն հաջորդ հանգույցին, օրինակ u-ին, ապա t հանգույցը կարելի է հեռացնել միացնելով t հանգույց մտնող կողերը u հանգույցի հետ: Ֆունկցիայի ներկայացնելը BDD-ների միջոցով օգտակար է այն դեպքում, երբ օրինակ անհրաժեշտ է բազմակի անգամ հաշվարկել ֆունկցիայի արժեքները փոփոխականների տարբեր հավաքածուների համար:
Մեր օրինակի համար BDD հետևյալն է`
1.
2.
3.
Տվյալ ֆունկցիան կոչվում է ITE-օպերատոր (IF – THEN – ELSE).
Այս օպերատորի միջոցով կարելի է ներկայացնել ցանկացած 2 փոփոխականից կախված ֆունկցիա:
Կառուցենք սխեման մուլտիպլեքսորի հիման վրա
4.
Մինիմացման աղյուսակային մեթոդը (Աուֆենկամպի և
Հոնի մեթոդը)
Ավտոմատի վիճակները հաջորդաբար բաժանվում են ըստ 1-, 2-, K-, (K+1)- համարժեք վիճակների դասերի:
Այդ բաժանումները նշանակենք π1, π 2, …, π k, π k+1:
Դիտարկենք մինիմացումը օրինակի վրա: Տրված է Միլիի ավտոմատի գրաֆը`
BABCB/1 CAB/2
Անցնենք ավտոմատի առաջադրման աղյուսակային ձևին:
π1բաժանում` Աղյուսակ 1.1
X
S A B C
S0 S0/0 S1/0 S5/0 A1
S1 S2/0 S1/0 S5/0 A1
S2 S0/0 S3/0 S5/0 A1
S3 S2/0 S1/0 S4/0 A1
S4 S6/0 S1/1 S5/0 B
S5 S6/0 S1/0 S5/0 A1
S6 S0/0 S1/2 S5/0 C1
A1 { S0,S1, S2, S3 ,S5 }
B1 { S4}
C1 { S6}
π2 բաժանում` Աղյուսակ 1.2
X
S A B C
A1 S0 A1 A1 A1 A2
S1 A1 A1 A1 A2
S2 A1 A1 A1 A2
S3 A1 A1 B1 B2
S5 C1 A1 A1 C2
B1 S4 C1 A1 A1 D2
C1
S6
A1
A1
A1
E2
A2 { S0,S1, S2 }
B2 { S3}
C2 { S5}
D2 { S4}
E2{S6}
π3 բաժանում ` Աղյուսակ 1.3
1
X
S A B C 2
A2
S0 A2 A2 C2 A3
S1 A2 A2 C2 A3
S2 A2 B2 C2 B3
B2 S3 B3 A3 E3 D4
C2 S4 F3 A3 D3 E4
D2 S5 F3 A3 D3 F4
E2 S6 A3 A3 D3 K4
A3{ S0,S1} D3 { S5}
B3 { S2} E3 { S4}
C3{S4} F3 { S6}
π4 բաժանում` Աղյուսակ 1.4
X
S A B C
A3 S0 A3 A3 D3 A4
S1 B3 A3 D3 B4
B3 S2 A3 C3 D3 C4
C3 S3 B3 A3 E3 D4
E3 S4 F3 A3 D3 E4
D3 S5 F3 A3 D3 F4
F3 S6 A3 A3 D3 K4
A4 { S0 } E4 { S4}
B4 { S1} F4 { S5}
C4{ S2} K4{ S6}
D4 { S3}
π5 բաժանում` Աղյուսակ 1.5
X
S A B C 5
A4 S0 A4 B4 F4 A5
B4 S1 C4 B4 F4 B5
C4 S2 A4 D4 F4 C5
D4 S3 C4 B4 E4 D5
E4 S4 K4 B4 F4 E5
F4 S5 K4 B4 F4 F5
K4 S6 A4 B4 F4 K5
A5 { S0} E5 { S4}
B5 { S1} F5 { S5}
C5 { S2} K5 { S6 }
D5 { S3}
Մինիմացման արդյունքում համարժեք վիճակներ չստացանք, այսինքն գրաֆը մինիմացված է:
Վերացական ավտոմատի հասկացություն
Կոմբինացիոն սխեմաներից բացի գոյություն ունեն ինֆորմացիայի ավելի բարդ ձևափոխիչներ, որոնց ռեակցիան կախված է տվյալ պահին ոչ միայն մուտքի վիճակից, այլև նրանից, թե ինչ կար մուտքին մինչ այդ: Այդպիսի ձևափոխիչները կոչվում են ավտոմատներ:
Ավտոմատ է կոչվում ինֆորմացիայի դիսկրետ ձևափոխիչը, որը մուտքային ազդանշանների ազդեցության տակ ընդունակ է անցնել մեկ վիճակից մյուսը և ձևավորել ելքային ազդանշաններ:
Վերացական ավտոմատն առաջադրվում է հետևյալ հինգ բազմությունների օգնությամբª A= { X, Y, S,d, }l,
որտեղ
X={X1, X2, …, XM} - ավտոմատի մուտքային այբուբենն է,
Y={Y1, Y2, …, YN} - ավտոմատի ելքային այբուբենն է,
S={S0,S1, …, Sk-1} - ավտոմատի ներքին վիճակների բազմությունն է կամ այբուբենը,
- անցումների ֆունկցիան է,
l - ավտոմատի ելքերի ֆունկցիան է:
Ավտոմատը կոչվում է վերջավոր, եթե X, Y, S բազմություն-ները վերջավոր են:
Ավտոմատը գործառում է ժամանակի դիսկրետ պահերին t=0,1, 2,…,n: Ժամանակի յուրաքանչյուր պահին ավտոմատը գտնվում է S բազմության որևէ մի վիճակում:
S0 - ավտոմատի սկզբնական վիճակն է (t=0 ժամանակի պահին):
d անցումների ֆունկցիան ժամանակի յուրաքանչյուր t պահին որո¬շում է ավտոմատի հաջորդ վիճակը կախված ավտոմատի ընթացիկ վիճա¬կից և մուտքային ազդանշանից: Այլ կերպ ասած, d ֆունկցիան «վիճակ -մուտքային ազդանշան» յուրաքանչյուր զույգին համապատասխանեցնում է հաջորդ վիճակը:
d : SxX®S d-ն հանդիսանում է S xX դեկարտյան արտադրյալի արտապատկերումը S բազմության մեջ: Անցումների ֆունկցիան կարելի է գրել հետևյալ կերպª St+1=d(St, xt):
l ելքային ֆունկցիան ժամանակի յուրաքանչյուր t պահին որոշում է ավտոմատի ելքային ազդանշանը:
Գոյություն ունի ավտոմատների 2 մոդելներª Միլիի և Մուրի ավտոմատներ: Նրանք տարբերվում են ելքերի ֆունկցիաներով, որոնք որոշվում են հետևյալ կերպª
Yt =l (St, Xt) – Միլիի ավտոմատի համար կամ l : SxX®Y
Yt = l(St) – Մուրի ավտոմատի համար:
Միլիի ավտոմատում ելքային ազդանշանը ժամանակի t պահին կախված է ինչպես մուտքային ազդանշանից ժամանակի t պահին, այնպես էլ ընթացիկ վիճակից:
Մուրի ավտոմատում ելքային ազդանշանը բացահայտ կախված չէ մուտքային ազդանշանից, այլ որոշվում է միայն ընթացիկ վիճակով:
Վիճակը դա ավտոմատի հիշողությունն է անցյալ մուտքային ազդեցությունների մասին:
Ավտոմատները կոչում են նաև հաջորդական մեքենաներ (Sequential Machine), քանի որ մուտքային հաջորդականությունը ձևափոխվում է վիճակների հաջորդականությանը և ելքային հաջորդականությանը:
Կարելի է ասել, որ վերացական ավտոմատն ունի մեկ մուտք և մեկ ելք: Ավտոմատի մուտքին հաղորդվում է մուտքային այբուբենի տառերի հաջորդականությունը, ելքում ձևավորվում են ելքային հաջորդականությունները:
Վերացական ավտոմատի պայմանական գրաֆիկական նշանակումն է`
Սահմանում:
Ավտոմատը կոչվում է լրիվ որոշված, եթե յուրաքանչյուր «վիճակ-մուտք» զույգի համար որոշված են ավտոմատի հաջորդ վիճակը և ելքը: Հակառակ դեպքում ավտոմատը հանդիսանում է ոչ լրիվ որոշված:
Սինթեզման փուլերը կոդավորում ենք`
a) Մուտքային ազդանշանների կոդավորում` log23≤ 2
x1 x2
A 0 0
B 0 1
C 1 0
1 1
b) Ելքային ազդանշանների կոդավորում` log23 ≤ 2
y1 y2
0 0 0
1 0 1
2 1 0
Ավտոմատի վիճակների կոդավորման համար օգտագործում ենք բինար կոդավորում:
S0 000
S1 001
S2 010
S3 011
S4 100
S5 101
S6 110
S7 111
Համակցված (կոմբինացիոն) սխեմաներ
Համակցված կամ տրամբանական սխեմաների միջոցով իրագործում են բուլյան ֆունկցիաները: Սխեմաները կոչվում են համակցված, քանի որ սխեմայի ելքային ազդանշանները որոշվում են մուտքային ազդանշանների համակցումով:
Սխեմայի հիմնական բաղադրիչներն են տրամաբանական տարրերը: Նկարագրենք տրամաբանական տարրերը.
Տրամաբանական բազմապատկում,կոնյունկցիա, «ԵՎ», «AND»
Տրամաբանական գումարում, դիզյունկցիա, «ԿԱՄ», «OR»
Տրամաբանական ժխտում, ինվերսում, «ՈՉ», «NOT»
«ԵՎ-ՈՉ» տարր, (Շեֆերի շտրիխ), «NAND»
«ԿԱՄ-ՈՉ» տարր, (Պիրսի սլաք), «NOR»
«ԿԱՄ բացառող» տարր, (ըստ mod 2 գումարում), «XOR»
«Համարժեքություն» տարր,, «NXOR»
JK Տրիգեր
J K- տրիգերը ունիվերսալ տրիգեր է, քանի որ դրա հիման վրա կարելի է կառուցել բոլոր դիտարկված տրիգերները: Երկտակտանի սինխրոն J K- տրիգերի պայմանական գրաֆիկական պատկերը և իսկության աղյուսակը ներկայացված են`
Jt
Kt Qt Qt+1
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 0
J K Qt+1
0 0 Qt
1 0 1
0 1 0
1 1 Qt
J մուտքը “1”-ի տեղակայման մուտքն է, K մուտքը` “0”-ինը: Ի տարբերություն R S տրիգերի 1 1 կոմբինացիան թույլատրելի է: Սահմանենք J K -տրիգերի բնութագրիչ հավասարումը:
J K անցումների մատրիցը և գրաֆը`
QtQt+1 J K
00 0 *
01 1 *
10 * 1
11 * 0
KQ
J 00 01 11 10
0 1
1 1 1
1
Qt+1 ֆունկցիայի արտահայտությունը մինիմացումից
հետո`
Qt+1=KtQt v JtQt
Ընդհանուր սինխրոն JK-տրիգերը կառուցվում է RS տիպի տրիգերի հիման վրա:
J K Qt Qt+1 Rt St
0 0 0 0 -- 0
0 0 1 1 0 --
0 1 0 0 -- 0
0 1 1 0 1 0
1 0 0 1 0 1
1 0 1 1 0 --
1 1 0 1 0 1
1 1 1 0 1 0
KQ
J 00 01 11 10
0 - 1 -
1 1
R=KQ
JQ
S 00 01 11 10
0 -
1 1
- 1
S=JQ
J K-ն ունիվերսալ տրիգեր է, այսինքն նրա հիման վրա կարելի է
ստանալ բոլոր տրիգերները (T,D,RS):
Նախնական
վիճակ Մուտքա յին
ազդա նշան
x1 x2 Հաջորդ
վիճակ
Տ.Գ.Վ Ելքա յին ազդանշան
y1y2
q1 q2 q3 q1q2q3 J1 K1 J2 K2 J3 K3
S0 000 A 00 S0 000 0 - 0 - 0 - 00
B 01 S1 001 0 - 0 - 1 - 00
C 10 S5 101 1 - 0 - 1 - 00
11 - - - - - - - -
S1 001 A 00 S2 010 0 - 1 - - 1 00
B 01 S1 001 0 - 0 - - 0 00
C 10 S5 101 1 - 0 - - 0 00
11 - - - - - - - -
S2 010 A 00 S0 000 0 - - 1 0 - 00
B 01 S3 011 0 - - 0 1 - 00
C 10 S5 101 1 - - 1 1 - 00
11 - - - - - - - -
S3 011 A 00 S2 010 0 - - 0 - 1 00
B 01 S1 001 0 - - 1 - 0 00
C 10 S4 100 1 - - 1 - 1 00
11 - - - - - - - -
S4 100 A 00 S6 110 - 0 1 - 0 - 00
B 01 S1 001 - 1 0 - 1 - 01
C 10 S5 101 - 0 0 - 1 - 00
11 - - - - - - - -
S5 101 A 00 S6 110 - 0 1 - - 1 00
B 01 S1 001 - 1 0 - - 0 00
C 10 S5 101 - 0 0 - - 0 00
11 - - - - - - - -
S6 110 A 00 S0 000 - 1 - 1 0 - 00
B 01 S1 001 - 1 - 1 1 - 10
C 10 S5 101 - 0 - 1 1 - 00
11 - - - - - - - -
S7 111
A 00 - - - - - - - -
B 01 - - - - - - - -
C 10 - - - - - - - -
11 - - - - - - - -
Հինգ փոփոխականներից կախված ֆունկ¬¬ցիաների ներկայացման համար օգտագործում ենք երկու հատ Կառնոյի քարտ հինգ փոփոխականի համար:
Մինիմացումը կատարում ենք Կառնոյի քարտերի միջոցով:
q1 q1
x1x2
q2q3 00 01 11 10
00
_ 1
01 _ 1
11 _ 1
10 _ 1
x1x2
q2q3 00 01 11 10
00 _ _
_ _
01 _ _ _ _
11 _ _ _ _
10 _ _ _ _
J1=x1
q1 q1
x1x2
q2q3 00 01 11 10
00 _
_ _ _
01 _ _ _ _
11
_ _ _ _
10 _ _ _ _
x1x2
q2q3 00 01 11 10
00
1 _
01 1 _
11
_
_ _ _
10 1 1 _
K1 = x2 V q2x1
q1
q1
x1x2
q2q3 00 01 11 10
00 _
01
1 _
11 _ _ _ _
10 _ _ _ _
x1x2
q2q3 00 01 11 10
00
1
_
01
1
_
11 _ _ _ _
10
_ _
_
_
J2=q3x1 x2vx1x2q1
q1 q1
x1x2
q2q3 00 01 11 10
00 _
_
_ _
01 _
_ _ _
11
1 _
1
10
1
_
1
x1x2
q2q3
00
01 11 10
00 _
_
_ _
01 _ _
_ _
11 _ _ _ _
10
1
1 _
1
k2 = q3 x2 V x1 V q1 V q3x2
q1 q1
x1x2
q2q3 00 01 11 10
00
1 _
1
01
_ _ _ _
11 _ _ _ _
10
1 _ 1
x1x2
q2q3 00 01 11 10
00
1
_ 1
01 _ _ _ _
11 _ _ _ _
10
1 _
1
J3=x2 V x1
q1 q1
x1x2
q2q3 00 01 11 10
00
_ _ _ _
01 1 _
11 1 _
1
10 _ _ _ _
x1x2
q2q3 00 01 11 10
00
_
_ _ _
01
1
_
11 _ _
_ _
10 _
_
_ _
k3 = x1 x2 V q2 x1
q1 q1
x1x2
q2q3 00 01 11 10
00
_
01
_
11 _
10
_
x1x2
q2q3 00 01 11 10
00 _
01 _
11 _
_ _ _
10 1 _
Y1=q2x2q1
q1 q1
x1x2
q2q3 00 01 11 10
00 _
01
_
11 _
10
_
x1x2
q2q3 00 01 11 10
00
1 _
01
_
11 _ _ _ _
10
_
Y2= q2 q3x2q1
Եվ-ԿԱՄ-ՈՉ ԲԱԶԻՍ
Դե-Մորգանի օրենքները
X1 & X2 = X1 V X2
X1 V X2 =X1& X2
և-ՈՉ ԲԱԶԻՍ
J1=x1
K1=x2 v q2 x1=x2 & q2 x1
J2=q3x1x2 v q1x1x2= q3x1x2 & q1x1x2
K2=q3x2vx1vq1vq3x2= q3x2 & x1 & q1 & q3x2
J3=x2 v x1=x2 & x1
K3=x1x2 v x1q2=x1x2 & x1q2
Y1=q2q1x2
Y2=q1q2q3x2
և-ոչ
ԿԱՄ-ՈՉ ԲԱԶԻՍ
J1=x1
K1=x2 V q2 x1=x2 Vq2 V x1
J2=q3x1x2 v q1x1x2=q3 v x1 v x2 v q1 v x1 v x2
K2=q3x2 v x1 v q1 v q3x2= q3 v x2 v x1 v q1 v q3 v x2
J3=x2 v x1
K3=x1x2 v x1q2= x1 v x2 v x1 v q2
Y1=q2q1x2= q2 v q1 v x2
Y2=q1q2q3x2=q1 v q2 v q3 v x2
термы q1 q2 q3 X1 x2 J1 K1 J2 K2 J3 K3 Y1 Y2
k1 ● ● ● 1 ● 1 ● ● ● ● ● ● ●
k2 ● ● ● ● 1 ● 1 ● ● ● ● ● ●
k3 ● 1 ● 0 ● ● 1 ● ● ● ● ● ●
k4 ● ● 1 0 0 ● ● 1 ● ● ● ● ●
k5 1 ● ● 0 0 ● ● 1 ● ● ● ● ●
k6 ● ● 0 ● 0 ● ● ● 1 ● ● ● ●
k7 ● ● ● 1 ● ● ● ● 1 ● ● ● ●
k8 ● ● 1 ● 1 ● ● ● 1 ● ● ● ●
k9 1 ● ● ● ● ● ● ● 1 ● ● ● ●
k10 ● ● ● ● 1 ● ● ● ● 1 ● ● ●
k11 ● ● ● 1 ● ● ● ● ● 1 ● ● ●
k12 ● ● ● 0 0 ● ● ● ● ● 1 ● ●
k13 ● 1 ● 1 ● ● ● ● ● ● 1 ● ●
k14 1 1 ● ● 1 ● ● ● ● ● ● 1 ●
k15 1 0 0 ● 1 ● ● ● ● ● ● ● 1
PLA
Ռեֆերատներ, կուրսայիններ, դիպլոմայիններ
referatner.do.am
Բուլյան ֆունկցիաների հասկացությունը
Բուլյան են կոչվում այն ֆունկցիաները (f(x1, x2,…xn)), որոնք, ինչպես և նրանց արգումենտները, կարող են ընդունել երկու արժեք` «0» և «1»:
Բոլոր n արգումենտներից f(x1, x2,…xn)ֆունկցիան որոշված է 2n հավաքածուներում կամ կետերում:
Երբեմն այդ հավաքածուների բազմությունը կոչվում է բուլյան տարածություն, իսկ այդ տարածության յուրաքանչյուր տարր` բուլյան վեկտոր:
Օրինակ
գB = { 0,1}
գB2 = {0,1} Բ {0,1} = {00, 01, 10, 11}
Բուլյան ֆունկցիաներն են f(x) : Bn ® B;
B = {0,1};
X= {x1, x2, … xn} Կ Bn; xj Կ B;
x1, … xn –փոփոխականներն են, x1, x1, x2 , x2 . . . – տառերը ( литералы.)
Տառերը `դրանք փոփոխականներն են կամ նրանց ժխտումները:
Օրինակ եթե x1 տառը ներկայացնում է f = {x|x1=1}, ապա x1 –ը ներկայացնում է g = {x|x1=0} տրամաբանական ֆունկցիան:
Եթե g(x) = f(x) բոլոր Bn ֆունկցիայի հավաքածուներն են, ապա g(x) և f(x) տրամաբանական ֆունկցիաները համարժեք են:
Ֆունկցիան կոչվում է ամբողջովին որոշված, եթե ցան¬կա-ցած հավաքածուի համար հայտնի է նրա արժեքը:
Իսկ եթե որոշ հավաքածուներում ֆունկցիայի արժեք¬ները որոշված չեն, ապա ֆունկցիան կոչվում է ոչ լրիվ կամ մասնակի որոշված:
Կան ընդամենը n փոփոխականների 2n աստիճանի 2 տարբեր ֆունկցիաներ, այդ թվում «0»-ի և «1»-ի հաստատունները և տրիվիալ ֆունկցիաները:
Բուլյան ֆունկցիաների ներկայացման ձևերը
1. Աղյուսակի միջոցով
2. Անալիտիկ ներկայացում (բանաձևերի միջոցով)
3. BDD-ների միջոցով
4. Բուլյան ցանցերի միջոցով
5. Սխեմաների միջոցով:
Աղյուսակի միջոցով տրված է ֆունկցիա
“1” {2,3,5,7,10,11,13,14,15}
x1 x2 x3 x4 f(x1x2 x3 x4)
0 0 0 0 0
0 0 0 1 0
0 0 1 0 1
0 0 1 1 1
0 1 0 0 0
0 1 0 1 1
0 1 1 0 0
0 1 1 1 1
1 0 0 0 0
1 0 0 1 0
1 0 1 0 1
1 0 1 1 1
1 1 0 0 0
1 1 0 1 1
1 1 1 0 1
1 1 1 1 1
Ֆունկցիայի ներկայացումը BDD-ի
միջոցով
BDD-ն երկուական լուծումների դիագրամների (Binary Decision Diagrams, BDD)` գրաֆ է, որը հանդիսանում է սեմանտիկ ծառերի մոդիֆիկացում: BDD-ներում ֆունկցիայի միևնույն արժեքով հանգույցները միացված են: BDD-ները օգտագործում են որպես բուլյան ֆունկցիաների ներկայացման կոմպակտ ձև: Այս ներկայացման ձևը արդարացված է այն դեպքում, երբ պետք է բազմակի անգամ հաշվարկել բուլյան ֆունկցիայի արժեքը փոփոխականների տարբեր հավաքածուների համար:
ՍԵմանտիկ ծառ
Ծառի գագաթը նշանակենք x1 : Մյուս շարքի գագաթները կնշանակենք x2 փոփոխականով, հաջորդ շարքի գագաթները` x3 փոփոխականով, իսկ ներքևի շարքի գագաթները կնշանակենք ֆունկցիայի արժեքներով:
Սեմանտիկ ծառից BDD-ի կառուցման ալգորիթմը կայանում է հետևյալում`
1. Ֆունկցիայի կրկնող արժեքների հեռացում,
2. Կրկնող տեստային հանգույցների հեռացում: Եթե BDD- ում երկու տարբեր միջանկյալ հանգույցներ համարվում են ենթադիագրամի կառուցվածքային համարժեք արմատներ, ապա նրանց փոխարինում են մեկ արմատով:
3. Ավելորդ տեստային հանգույցների հեռացում: Եթե որոշ t դուրս եկած երկու կողերը ցույց են տալիս միևնույն հաջորդ հանգույցին, օրինակ u-ին, ապա t հանգույցը կարելի է հեռացնել միացնելով t հանգույց մտնող կողերը u հանգույցի հետ: Ֆունկցիայի ներկայացնելը BDD-ների միջոցով օգտակար է այն դեպքում, երբ օրինակ անհրաժեշտ է բազմակի անգամ հաշվարկել ֆունկցիայի արժեքները փոփոխականների տարբեր հավաքածուների համար:
Մեր օրինակի համար BDD հետևյալն է`
1.
2.
3.
Տվյալ ֆունկցիան կոչվում է ITE-օպերատոր (IF – THEN – ELSE).
Այս օպերատորի միջոցով կարելի է ներկայացնել ցանկացած 2 փոփոխականից կախված ֆունկցիա:
Կառուցենք սխեման մուլտիպլեքսորի հիման վրա
4.
Մինիմացման աղյուսակային մեթոդը (Աուֆենկամպի և
Հոնի մեթոդը)
Ավտոմատի վիճակները հաջորդաբար բաժանվում են ըստ 1-, 2-, K-, (K+1)- համարժեք վիճակների դասերի:
Այդ բաժանումները նշանակենք π1, π 2, …, π k, π k+1:
Դիտարկենք մինիմացումը օրինակի վրա: Տրված է Միլիի ավտոմատի գրաֆը`
BABCB/1 CAB/2
Անցնենք ավտոմատի առաջադրման աղյուսակային ձևին:
π1բաժանում` Աղյուսակ 1.1
X
S A B C
S0 S0/0 S1/0 S5/0 A1
S1 S2/0 S1/0 S5/0 A1
S2 S0/0 S3/0 S5/0 A1
S3 S2/0 S1/0 S4/0 A1
S4 S6/0 S1/1 S5/0 B
S5 S6/0 S1/0 S5/0 A1
S6 S0/0 S1/2 S5/0 C1
A1 { S0,S1, S2, S3 ,S5 }
B1 { S4}
C1 { S6}
π2 բաժանում` Աղյուսակ 1.2
X
S A B C
A1 S0 A1 A1 A1 A2
S1 A1 A1 A1 A2
S2 A1 A1 A1 A2
S3 A1 A1 B1 B2
S5 C1 A1 A1 C2
B1 S4 C1 A1 A1 D2
C1
S6
A1
A1
A1
E2
A2 { S0,S1, S2 }
B2 { S3}
C2 { S5}
D2 { S4}
E2{S6}
π3 բաժանում ` Աղյուսակ 1.3
1
X
S A B C 2
A2
S0 A2 A2 C2 A3
S1 A2 A2 C2 A3
S2 A2 B2 C2 B3
B2 S3 B3 A3 E3 D4
C2 S4 F3 A3 D3 E4
D2 S5 F3 A3 D3 F4
E2 S6 A3 A3 D3 K4
A3{ S0,S1} D3 { S5}
B3 { S2} E3 { S4}
C3{S4} F3 { S6}
π4 բաժանում` Աղյուսակ 1.4
X
S A B C
A3 S0 A3 A3 D3 A4
S1 B3 A3 D3 B4
B3 S2 A3 C3 D3 C4
C3 S3 B3 A3 E3 D4
E3 S4 F3 A3 D3 E4
D3 S5 F3 A3 D3 F4
F3 S6 A3 A3 D3 K4
A4 { S0 } E4 { S4}
B4 { S1} F4 { S5}
C4{ S2} K4{ S6}
D4 { S3}
π5 բաժանում` Աղյուսակ 1.5
X
S A B C 5
A4 S0 A4 B4 F4 A5
B4 S1 C4 B4 F4 B5
C4 S2 A4 D4 F4 C5
D4 S3 C4 B4 E4 D5
E4 S4 K4 B4 F4 E5
F4 S5 K4 B4 F4 F5
K4 S6 A4 B4 F4 K5
A5 { S0} E5 { S4}
B5 { S1} F5 { S5}
C5 { S2} K5 { S6 }
D5 { S3}
Մինիմացման արդյունքում համարժեք վիճակներ չստացանք, այսինքն գրաֆը մինիմացված է:
Վերացական ավտոմատի հասկացություն
Կոմբինացիոն սխեմաներից բացի գոյություն ունեն ինֆորմացիայի ավելի բարդ ձևափոխիչներ, որոնց ռեակցիան կախված է տվյալ պահին ոչ միայն մուտքի վիճակից, այլև նրանից, թե ինչ կար մուտքին մինչ այդ: Այդպիսի ձևափոխիչները կոչվում են ավտոմատներ:
Ավտոմատ է կոչվում ինֆորմացիայի դիսկրետ ձևափոխիչը, որը մուտքային ազդանշանների ազդեցության տակ ընդունակ է անցնել մեկ վիճակից մյուսը և ձևավորել ելքային ազդանշաններ:
Վերացական ավտոմատն առաջադրվում է հետևյալ հինգ բազմությունների օգնությամբª A= { X, Y, S,d, }l,
որտեղ
X={X1, X2, …, XM} - ավտոմատի մուտքային այբուբենն է,
Y={Y1, Y2, …, YN} - ավտոմատի ելքային այբուբենն է,
S={S0,S1, …, Sk-1} - ավտոմատի ներքին վիճակների բազմությունն է կամ այբուբենը,
- անցումների ֆունկցիան է,
l - ավտոմատի ելքերի ֆունկցիան է:
Ավտոմատը կոչվում է վերջավոր, եթե X, Y, S բազմություն-ները վերջավոր են:
Ավտոմատը գործառում է ժամանակի դիսկրետ պահերին t=0,1, 2,…,n: Ժամանակի յուրաքանչյուր պահին ավտոմատը գտնվում է S բազմության որևէ մի վիճակում:
S0 - ավտոմատի սկզբնական վիճակն է (t=0 ժամանակի պահին):
d անցումների ֆունկցիան ժամանակի յուրաքանչյուր t պահին որո¬շում է ավտոմատի հաջորդ վիճակը կախված ավտոմատի ընթացիկ վիճա¬կից և մուտքային ազդանշանից: Այլ կերպ ասած, d ֆունկցիան «վիճակ -մուտքային ազդանշան» յուրաքանչյուր զույգին համապատասխանեցնում է հաջորդ վիճակը:
d : SxX®S d-ն հանդիսանում է S xX դեկարտյան արտադրյալի արտապատկերումը S բազմության մեջ: Անցումների ֆունկցիան կարելի է գրել հետևյալ կերպª St+1=d(St, xt):
l ելքային ֆունկցիան ժամանակի յուրաքանչյուր t պահին որոշում է ավտոմատի ելքային ազդանշանը:
Գոյություն ունի ավտոմատների 2 մոդելներª Միլիի և Մուրի ավտոմատներ: Նրանք տարբերվում են ելքերի ֆունկցիաներով, որոնք որոշվում են հետևյալ կերպª
Yt =l (St, Xt) – Միլիի ավտոմատի համար կամ l : SxX®Y
Yt = l(St) – Մուրի ավտոմատի համար:
Միլիի ավտոմատում ելքային ազդանշանը ժամանակի t պահին կախված է ինչպես մուտքային ազդանշանից ժամանակի t պահին, այնպես էլ ընթացիկ վիճակից:
Մուրի ավտոմատում ելքային ազդանշանը բացահայտ կախված չէ մուտքային ազդանշանից, այլ որոշվում է միայն ընթացիկ վիճակով:
Վիճակը դա ավտոմատի հիշողությունն է անցյալ մուտքային ազդեցությունների մասին:
Ավտոմատները կոչում են նաև հաջորդական մեքենաներ (Sequential Machine), քանի որ մուտքային հաջորդականությունը ձևափոխվում է վիճակների հաջորդականությանը և ելքային հաջորդականությանը:
Կարելի է ասել, որ վերացական ավտոմատն ունի մեկ մուտք և մեկ ելք: Ավտոմատի մուտքին հաղորդվում է մուտքային այբուբենի տառերի հաջորդականությունը, ելքում ձևավորվում են ելքային հաջորդականությունները:
Վերացական ավտոմատի պայմանական գրաֆիկական նշանակումն է`
Սահմանում:
Ավտոմատը կոչվում է լրիվ որոշված, եթե յուրաքանչյուր «վիճակ-մուտք» զույգի համար որոշված են ավտոմատի հաջորդ վիճակը և ելքը: Հակառակ դեպքում ավտոմատը հանդիսանում է ոչ լրիվ որոշված:
Սինթեզման փուլերը կոդավորում ենք`
a) Մուտքային ազդանշանների կոդավորում` log23≤ 2
x1 x2
A 0 0
B 0 1
C 1 0
1 1
b) Ելքային ազդանշանների կոդավորում` log23 ≤ 2
y1 y2
0 0 0
1 0 1
2 1 0
Ավտոմատի վիճակների կոդավորման համար օգտագործում ենք բինար կոդավորում:
S0 000
S1 001
S2 010
S3 011
S4 100
S5 101
S6 110
S7 111
Համակցված (կոմբինացիոն) սխեմաներ
Համակցված կամ տրամբանական սխեմաների միջոցով իրագործում են բուլյան ֆունկցիաները: Սխեմաները կոչվում են համակցված, քանի որ սխեմայի ելքային ազդանշանները որոշվում են մուտքային ազդանշանների համակցումով:
Սխեմայի հիմնական բաղադրիչներն են տրամաբանական տարրերը: Նկարագրենք տրամաբանական տարրերը.
Տրամաբանական բազմապատկում,կոնյունկցիա, «ԵՎ», «AND»
Տրամաբանական գումարում, դիզյունկցիա, «ԿԱՄ», «OR»
Տրամաբանական ժխտում, ինվերսում, «ՈՉ», «NOT»
«ԵՎ-ՈՉ» տարր, (Շեֆերի շտրիխ), «NAND»
«ԿԱՄ-ՈՉ» տարր, (Պիրսի սլաք), «NOR»
«ԿԱՄ բացառող» տարր, (ըստ mod 2 գումարում), «XOR»
«Համարժեքություն» տարր,, «NXOR»
JK Տրիգեր
J K- տրիգերը ունիվերսալ տրիգեր է, քանի որ դրա հիման վրա կարելի է կառուցել բոլոր դիտարկված տրիգերները: Երկտակտանի սինխրոն J K- տրիգերի պայմանական գրաֆիկական պատկերը և իսկության աղյուսակը ներկայացված են`
Jt
Kt Qt Qt+1
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 0
J K Qt+1
0 0 Qt
1 0 1
0 1 0
1 1 Qt
J մուտքը “1”-ի տեղակայման մուտքն է, K մուտքը` “0”-ինը: Ի տարբերություն R S տրիգերի 1 1 կոմբինացիան թույլատրելի է: Սահմանենք J K -տրիգերի բնութագրիչ հավասարումը:
J K անցումների մատրիցը և գրաֆը`
QtQt+1 J K
00 0 *
01 1 *
10 * 1
11 * 0
KQ
J 00 01 11 10
0 1
1 1 1
1
Qt+1 ֆունկցիայի արտահայտությունը մինիմացումից
հետո`
Qt+1=KtQt v JtQt
Ընդհանուր սինխրոն JK-տրիգերը կառուցվում է RS տիպի տրիգերի հիման վրա:
J K Qt Qt+1 Rt St
0 0 0 0 -- 0
0 0 1 1 0 --
0 1 0 0 -- 0
0 1 1 0 1 0
1 0 0 1 0 1
1 0 1 1 0 --
1 1 0 1 0 1
1 1 1 0 1 0
KQ
J 00 01 11 10
0 - 1 -
1 1
R=KQ
JQ
S 00 01 11 10
0 -
1 1
- 1
S=JQ
J K-ն ունիվերսալ տրիգեր է, այսինքն նրա հիման վրա կարելի է
ստանալ բոլոր տրիգերները (T,D,RS):
Նախնական
վիճակ Մուտքա յին
ազդա նշան
x1 x2 Հաջորդ
վիճակ
Տ.Գ.Վ Ելքա յին ազդանշան
y1y2
q1 q2 q3 q1q2q3 J1 K1 J2 K2 J3 K3
S0 000 A 00 S0 000 0 - 0 - 0 - 00
B 01 S1 001 0 - 0 - 1 - 00
C 10 S5 101 1 - 0 - 1 - 00
11 - - - - - - - -
S1 001 A 00 S2 010 0 - 1 - - 1 00
B 01 S1 001 0 - 0 - - 0 00
C 10 S5 101 1 - 0 - - 0 00
11 - - - - - - - -
S2 010 A 00 S0 000 0 - - 1 0 - 00
B 01 S3 011 0 - - 0 1 - 00
C 10 S5 101 1 - - 1 1 - 00
11 - - - - - - - -
S3 011 A 00 S2 010 0 - - 0 - 1 00
B 01 S1 001 0 - - 1 - 0 00
C 10 S4 100 1 - - 1 - 1 00
11 - - - - - - - -
S4 100 A 00 S6 110 - 0 1 - 0 - 00
B 01 S1 001 - 1 0 - 1 - 01
C 10 S5 101 - 0 0 - 1 - 00
11 - - - - - - - -
S5 101 A 00 S6 110 - 0 1 - - 1 00
B 01 S1 001 - 1 0 - - 0 00
C 10 S5 101 - 0 0 - - 0 00
11 - - - - - - - -
S6 110 A 00 S0 000 - 1 - 1 0 - 00
B 01 S1 001 - 1 - 1 1 - 10
C 10 S5 101 - 0 - 1 1 - 00
11 - - - - - - - -
S7 111
A 00 - - - - - - - -
B 01 - - - - - - - -
C 10 - - - - - - - -
11 - - - - - - - -
Հինգ փոփոխականներից կախված ֆունկ¬¬ցիաների ներկայացման համար օգտագործում ենք երկու հատ Կառնոյի քարտ հինգ փոփոխականի համար:
Մինիմացումը կատարում ենք Կառնոյի քարտերի միջոցով:
q1 q1
x1x2
q2q3 00 01 11 10
00
_ 1
01 _ 1
11 _ 1
10 _ 1
x1x2
q2q3 00 01 11 10
00 _ _
_ _
01 _ _ _ _
11 _ _ _ _
10 _ _ _ _
J1=x1
q1 q1
x1x2
q2q3 00 01 11 10
00 _
_ _ _
01 _ _ _ _
11
_ _ _ _
10 _ _ _ _
x1x2
q2q3 00 01 11 10
00
1 _
01 1 _
11
_
_ _ _
10 1 1 _
K1 = x2 V q2x1
q1
q1
x1x2
q2q3 00 01 11 10
00 _
01
1 _
11 _ _ _ _
10 _ _ _ _
x1x2
q2q3 00 01 11 10
00
1
_
01
1
_
11 _ _ _ _
10
_ _
_
_
J2=q3x1 x2vx1x2q1
q1 q1
x1x2
q2q3 00 01 11 10
00 _
_
_ _
01 _
_ _ _
11
1 _
1
10
1
_
1
x1x2
q2q3
00
01 11 10
00 _
_
_ _
01 _ _
_ _
11 _ _ _ _
10
1
1 _
1
k2 = q3 x2 V x1 V q1 V q3x2
q1 q1
x1x2
q2q3 00 01 11 10
00
1 _
1
01
_ _ _ _
11 _ _ _ _
10
1 _ 1
x1x2
q2q3 00 01 11 10
00
1
_ 1
01 _ _ _ _
11 _ _ _ _
10
1 _
1
J3=x2 V x1
q1 q1
x1x2
q2q3 00 01 11 10
00
_ _ _ _
01 1 _
11 1 _
1
10 _ _ _ _
x1x2
q2q3 00 01 11 10
00
_
_ _ _
01
1
_
11 _ _
_ _
10 _
_
_ _
k3 = x1 x2 V q2 x1
q1 q1
x1x2
q2q3 00 01 11 10
00
_
01
_
11 _
10
_
x1x2
q2q3 00 01 11 10
00 _
01 _
11 _
_ _ _
10 1 _
Y1=q2x2q1
q1 q1
x1x2
q2q3 00 01 11 10
00 _
01
_
11 _
10
_
x1x2
q2q3 00 01 11 10
00
1 _
01
_
11 _ _ _ _
10
_
Y2= q2 q3x2q1
Եվ-ԿԱՄ-ՈՉ ԲԱԶԻՍ
Դե-Մորգանի օրենքները
X1 & X2 = X1 V X2
X1 V X2 =X1& X2
և-ՈՉ ԲԱԶԻՍ
J1=x1
K1=x2 v q2 x1=x2 & q2 x1
J2=q3x1x2 v q1x1x2= q3x1x2 & q1x1x2
K2=q3x2vx1vq1vq3x2= q3x2 & x1 & q1 & q3x2
J3=x2 v x1=x2 & x1
K3=x1x2 v x1q2=x1x2 & x1q2
Y1=q2q1x2
Y2=q1q2q3x2
և-ոչ
ԿԱՄ-ՈՉ ԲԱԶԻՍ
J1=x1
K1=x2 V q2 x1=x2 Vq2 V x1
J2=q3x1x2 v q1x1x2=q3 v x1 v x2 v q1 v x1 v x2
K2=q3x2 v x1 v q1 v q3x2= q3 v x2 v x1 v q1 v q3 v x2
J3=x2 v x1
K3=x1x2 v x1q2= x1 v x2 v x1 v q2
Y1=q2q1x2= q2 v q1 v x2
Y2=q1q2q3x2=q1 v q2 v q3 v x2
термы q1 q2 q3 X1 x2 J1 K1 J2 K2 J3 K3 Y1 Y2
k1 ● ● ● 1 ● 1 ● ● ● ● ● ● ●
k2 ● ● ● ● 1 ● 1 ● ● ● ● ● ●
k3 ● 1 ● 0 ● ● 1 ● ● ● ● ● ●
k4 ● ● 1 0 0 ● ● 1 ● ● ● ● ●
k5 1 ● ● 0 0 ● ● 1 ● ● ● ● ●
k6 ● ● 0 ● 0 ● ● ● 1 ● ● ● ●
k7 ● ● ● 1 ● ● ● ● 1 ● ● ● ●
k8 ● ● 1 ● 1 ● ● ● 1 ● ● ● ●
k9 1 ● ● ● ● ● ● ● 1 ● ● ● ●
k10 ● ● ● ● 1 ● ● ● ● 1 ● ● ●
k11 ● ● ● 1 ● ● ● ● ● 1 ● ● ●
k12 ● ● ● 0 0 ● ● ● ● ● 1 ● ●
k13 ● 1 ● 1 ● ● ● ● ● ● 1 ● ●
k14 1 1 ● ● 1 ● ● ● ● ● ● 1 ●
k15 1 0 0 ● 1 ● ● ● ● ● ● ● 1
PLA
Ռեֆերատներ, կուրսայիններ, դիպլոմայիններ
referatner.do.am