2.5
x1 | x2 | x3 | y |
:
.
2.4 - , 2.2.
2.5 , 2.4
2.6
, , , , , , .
2.7
1. , , .
2. , , ()?
3. .
4. ?
5. .
6. ?
7. ?
3 3
3.1
3.1
, .
3.2
- .
, .
, RS, D, DV, JK, T, RSR, RSS, RSE . , (t s) (t s+1).
RS ( 4.1) , t s+1 (Q s+1 = Q s), t s R s = 0 S s = 0.
R s = 0, S s = 1 (Q s+1 = 1), R s = 1, S s = 0
(Q s+1 = 0).
R s = 1, S s = 1 (Q s+1 = *). RS - .
RSR - RS - , R s = S s = 1 (Q s+1 = 0). RSS - (Q s+1 = 1), RS - (Q s+1 = Q s).
|
|
D - ( 4.2). , (D - ). Q s+1 = D s.
DV - D - , V ( 4.3). V = 1 DV - D - , V = 0 - .
4.1 RS, RSR, RSS, RSE
t s | t S+1 | ||||
R s | S s | Q s+1 | |||
RS | RSR | RSS | RSE | ||
Q s | Q s | Q s | Q s | ||
* | Q s |
4.2 D - a
t s | t S+1 |
D s | Q s+1 |
4.3 DV - a
t s | t S+1 | |
D s | V s | Q s+1 |
Q s | ||
Q s | ||
4.4 T - a
t s | t S+1 |
T s | Q s+1 |
Q s | |
- . , , , 4.4.
JK ( 4.5) , J = K = 1 , , RS - .
4.5 JK - a
t s | t S+1 | |
J s | K s | Q s+1 |
Q s | ||
.
. .
. () .
:
- ,
-
, . , .
, , 0 1 .
MS ( ) , .. - 0 1, - 1 0.
( ) , .. - 1 0, - 0 1.
() ( 4.1) (), f1 f2 .
|
|
4.1
Q s+1 , Q f1 f2 , . , f1 f2 Q , .
:
- S ,
- MS ,
- .
MS , 4.2.
4.2 MS
-
4.3 ,
MS .
4.3 MS
-
.
4.6 S -
f 1 | f 2 | ||
─ | |||
─ | |||
: ─ f 1 f 2.
. . 4.7.
4.7 S -
f 1 | f 2 | ||
─ | |||
─ | |||
, , .
4.4
4.8.
4.8 -
f 1 | f 2 | ||
─ | |||
─ | |||
.
4.9 -
f 1 | f 2 | ||
─ | |||
─ | |||
() , f 1 f 2 . , Q s t s , . f 1 f 2. .
|
|
3.3 DV- MS -
4.10 - DV-
D | V | QS | QS+1 |
MS - .
4.11 -
D | V | QS | f1 | f2 |
.
4.12 - DV-
D\VQs | ||||
D\VQs | ||||
4.5 - DV- MS- -
4.6 DV- MS- -
3.4
1. , - - ( 4.1).
2. , - - MS ( 4.2, 4.3, 4.4, 4.5). , .
3. MS - - ( 4.7). .
4.7
t s | t S+1 | |||||||||||||||
x1 | x2 | Q S+1 | ||||||||||||||
QS | QS | QS | QS | QS | ||||||||||||
QS | QS | QS | QS | |||||||||||||
QS | QS | QS | QS | |||||||||||||
QS | QS | |||||||||||||||
QS | QS | QS | QS | QS | ||||||||||||
QS | QS | QS | QS | |||||||||||||
QS | QS | QS | QS | |||||||||||||
QS | QS |
|
|
3.5
1. .
2. .
3.6
, , , , , .
3.7
1. RS, RSR, RSS, RSE, D, T, DV JK .
2. ?
3. , , ?
4. , MS .
5. .
6. D JK ?
4 4
4.1
4.1
.
4.2
4.2
S = {A, X, Y, d, l, a0}, ..
= {0... k}, 0 - ,
= {1... n},
Y = {y1... ym},
d l.
. .
,
.
. , , .
m s (m º s), (m, e) = (s, e) e. m s , .
k . m s k - , l (m, ek) = l (s, ek) k, k - , k - . k - ( ). k- p pk. p .
.
1. p1, p2... pk, pk+1 - , - k+1 pk+1 = pk.B pk = p, .. k- .
2. p , - .
3. . .
, ( 5.1) ( 5.2).
( 5.2) p1 , p1 = {B1, B2}, B1 = {a1, a2, a5, a6},
B2 = {a3, a4}.
5.1 5.2
1 | 2 | 1 | 2 | |||
1 | 3 | 5 | 1 | y 1 | y 1 | |
2 | 4 | 6 | 2 | y 1 | y 1 | |
3 | 3 | 5 | 3 | y 1 | y 2 | |
4 | 4 | 6 | 4 | y 1 | y 2 | |
5 | 5 | 1 | 5 | y 1 | y 1 | |
6 | 6 | 2 | 6 | y 1 | y 1 |
p1 ( 5.3), 1 .
p2 2 - ( 5.4), p2 = {1, C2, C3}, C1 = {a1, a2},
|
|
C2 = {a5, a6}, C3 = {a3, a4}.
5.3 1 5.4 2-
p1 | 1 | 2 | p2 | 1 | 2 | ||||
1 | 1 | B 2 | B 1 | C 1 | 1 | C 3 | C 2 | ||
2 | B 2 | B 1 | 2 | C 3 | C 2 | ||||
5 | B 1 | B 1 | C 2 | 5 | C 2 | C 1 | |||
6 | B 1 | B 1 | 6 | C 2 | C 1 | ||||
2 | 3 | B 2 | B 1 | C 3 | 3 | C 3 | C 2 | ||
4 | B 2 | B 1 | 4 | C 3 | C 2 |
p3, p2. - 1, C2 3 ( 5.5) ( 5.6) .
5.5 5.6
1 | 2 | 1 | 2 | |||
1 | 4 | 5 | 1 | y 1 | y 1 | |
4 | 4 | 5 | 4 | y 1 | y 2 | |
5 | 5 | 1 | 5 | y 1 | y 2 |
.
- .
:
,
,
,
.
, x i X, y i Y, i .
, , , , :
kc ³ ] log 2 │A│ [,
] [ - , ,
││- , ,
= {1, 2, 3}, ││ = 3.
3 , k ³ 2. , i c , , , = {00, 01, 10}.
( 5.7) ( 5.8).
, k = 1, │X│= 2, k = ]log2 2[ = 1. , x1, x2 , , ..
X = {0, 1}.
5.7 5.8
1 | 2 | 1 | 2 | |||
1 | 2 | 1 | 1 | y 1 | y 3 | |
2 | 1 | 2 | 2 | y 2 | y 4 | |
3 | 3 | 2 | 3 | y 1 | y 2 |
y i , k = 2, .. . Y = {00,01,10,11}. , , .
( 5.9) ( 5.10) .
5.9 5.10
Q 1 Q 2 | = 0 | = 1 | Q 1 Q 2 | = 0 | = 1 | |
0 0 | 0 1 | 0 0 | 0 0 | 0 0 | 1 0 | |
0 1 | 0 0 | 0 1 | 0 1 | 0 1 | 1 1 | |
1 0 | 1 0 | 0 1 | 1 0 | 0 0 | 0 1 |
, .
, .
C , 5 ( 5.1).
5.1
:
1. , , , .
, i- - .
= | ||
5.2
2. :
1 = 000; 2 = 001. .
Q 1 \ Q 2 Q 3 | ||||
5.3
3. , - 1 2. '.
' = | ||
5.4 '
4. ' . - ' v. .. v = 4.
5. 4, ' 4. 4 - ', . .
4 = | ||
5.5 4
6. , : C'2 = {101, 011}. , 4: D'4 = C'2 = {101, 011}.
7. , , , :
W101 = │101-001│ =1;
W011 = │011-001│ =1.
4 = 101 .
Q 1 \ Q 2 Q 3 | ||||
5.6
8. ' 1- ,
' = | ||
5.7 '
9. v = 5.
10. 5, ' , 5.
5 = | ||
5.7 5
, 5 = {2, 4, 1}.
11. B5 , : C'2 = {011}, C'4 = {100, 111}, C'1 = {100, 010}. , 5:
D'5 ={011,100,111,010}.
12.
W011 =│011-001│+│011-101│+│011-101│+│011-000│= 1+2+2+2=7,
W100 =│100-001│+│100-101│+│100-101│+│100-000│= 2+1+1+1=5,
W111 =│111-001│+│111-101│+│111-101│+│111-000│= 2+1+1+3=7,
W010 =│010-001│+│010-101│+│010-101│+│010-000│= 2+3+3+1=9.
W100 = min {W011, W100, W111, W010}.
Q 1 \ Q 2 Q 3 | ||||
5.8
, 5 ( ). 4 - , .
13. ' - . , - .
' = | ||
5.9 '
14. v = 3.
15. 3, ' , 3.
3 = | ||
5.10 3
16. , 3 = {2,4}.
17. :
'2 = { 011 }, C'4 = { 111 }.
, - 3: D'3 = {011, 111 }.
18. :
W011 =│011-001│+│011-101│=1+2=3,
W111 =│111-001│+│111-101│=2+1=3.
3 = 011 .
Q 1 \ Q 2 Q 3 | ||||
5.8
.
, D1j = 0, D2j - , 2.
D2j = 0, D3j Dnj = 0, n = 1, 2, 3...
. D -, T -, RS -, JK - .
, ( ) .
, , - , Qs Qs+1. 5.11.
5.11
Qs Qs+1 | D | T | R | S | J | K |
0 0 | ¾ | ¾ | ||||
0 1 | ¾ | |||||
1 0 | ¾ | |||||
1 1 | ¾ | ¾ |
. , - , , , .
-. ( 5.12), 5.9, .
5.12
Q 1 Q 2 | = 0 | = 1 |
0 0 | 0 1 | 0 0 |
0 1 | 0 0 | 0 1 |
1 0 | 1 0 | 0 1 |
1 2 | 1 2 |
. , , 1 2.
5.13 1
\ Q 1Q 2 | ||||
- | ||||
- |
T 1 = Q 1
5.14 2
\ Q 1Q 2 | ||||
- | ||||
- |
T 2 = Q 2 x Ú Q 1 x Ú 1 2
. , .
5.15
Q 1 Q 2 | = 0 | = 1 |
0 0 | 0 0 | 1 0 |
0 1 | 0 1 | 1 1 |
1 0 | 0 0 | 0 1 |
5.16 1
\ Q 1Q 2 | ||||
- | ||||
- |
1 = 1
5.17 2
\ Q 1Q 2 | ||||
- | ||||
- |
2 = Q 2 Ú Q 1
, - .
4.3 .
- 1 2 3 4.
1. , - , . - , 1 2 3 4.
2.
3. , 2. () - . 3 4 - 1 2 3 4 00 RS - , 01 JK - , 10 D - , 11 T - .
4.4
1. , ( 2). , . .
2. , - ( 2).
3. , .
4.5
, - , , , . , , .
4.6
1. .
2. .
3. ?
4. ,
.
5. -
.
1. .. . . : , 1987.
2. ... . .: , 1974.
3. .. . .: , 1984.
4. .. . .: , 1985.
5. ... . .: , 1974.