' . - , . ϳ 䳺 . .
, - . , . (). , . 䳿 , . , ( ). :
Q ;
- ;
S - ( Q);
R - ( Q);
D - ( , );
- ;
- .
RS- , D- -. .
RS-. RS- . 4. : 2-Ͳ - ( 4, ), 2-Ͳ - ( 4, ). ' , . 1.1 .
4 - RS-
aftvin
1 - RS-
S | R | |||||||||||
* * | * * | * * | * * |
. , 䳺 ( , ). -Ͳ , -Ͳ - . г, , . г Qt+1 Q't+1 . Qt+1=1 S=1 R=0; Qt+1=0 S=0 R=1; Qt+1=Qt S=0 R=0. R=S=1 (*), 䳿 Qt+1=Q't+1, 䳿 - . .
|
|
S=1, R=0 1 ( Qt+1=1); S=0 R=1 - 0. S=0, R=0 , . 1 S=0, R=1, 0 - S=1, R=0. S=R=1 . S=R=0 .
D-. ³ . D- 5.
5 - D-
=0, . RS- ( 3 4) (S=R=1). =1 , D. , =0 Qt+1=Qt, =1 Qt+1=D( 2).
2 - D-
D | ||
Qt , a Qt+1 - .
, , . , .
D- . , =1. . . , , - . .
˳ - ( 6). . ³ Q Q'. ( ) . , , -, , . D-, ' . , - , .
6 - ˳
, , JK-. ' JK- - .
7.
|
|
7 -
ò
ò
ʳ ' - . ().
D- ( 8) , , . . '. , .
, , 9. (0 1), D, , . , , , D Q , ( ). . N- N . , 1011 (1 - Q4, 0 - Q3, 1 - Q2, 1 - Q1) . Q4-Q1. , , Q4 (5-9). .
8 - D-
, , . . , 5551 ( 10) - . , 1, V2 . V1 . V2 , D1-D4 , 2. : '
9 -
10 -
˲
˳ , , . , , . , , , , .
, ' D . N 11. (Q0) 1, 0. , , 1 , , , , 1. (N-1) , N- , . , (- ), .
11 - ʳ
- , . , , -. ϳ D , . dz n (' ), . 1 0 .
|
|
̳ 5555 ( 12) ( 1) ( 2), ' . ( 1 0). ' , 24=16. , N=24-1=15=(1111)2. (), 2, =2n . ˳ 0.
12 - ˳ 16
, 2n. , 6 ( ), 10 ( ), 7 ( ), 24 (). ≠ 2n n , 2n>K. , (2n-). ', , .
=10 ( 23<10<24). ˳ N=0, 1,..., 8, 9. , (N=10), . 5555 ( 13), ' , 10 ( 2 8), 0 ( R). 11- ( 10) ' ( 2), .
13 - -
, 5552 5556 =10, 5554 =2×=12.
( 11-13), , , f , , f, . , , . , 5551 - 10, 5558 - =64/n, n=1....63.
, , 5556, 5557, ( ), ( ) .
̳ 5551 ( 14) - 10. 0 1 2 ( ). ˳ 8 9 ( ), ( ).
|
|
14 -
5552 ( 15) ( 1) 5 ( 2). 瑺 2 - ( 13). ϳ . ˳ 0 (R0 ) 9 (R9 ).
15 - -
5554 ( 16) 6.
16 - ˳ 5554
̳ 5556 5557 - ; - -, - . 0 R. , D1-D4 ( 5556 0 9, 5557 0 15). S ( 1 2 - , R - ). , 1 ( ) 2 ( ). . S , R - , D . () 1 1 ' , , . 2, 9 (15), 2 ' . . 18. (S=0) 6 ( D2 D3).
17 -
, - 㳺 ( 164, 176, 564, 561), ( 3 ) R. . , RC- ( 19).
18 - 5556, 5557
19 - 0
̳ 176 1764 ( 1.20) 6 10 , . , 2 6 ( 3 2) 176 1764 4 10. ˳ . ( =0), ( =1) , 䒺 . ˳ . f>50 . 瑺 6 (176) 10 (1764).
20 - ˳ 6 (10)
ײ IJ
. ¯ ' . ' . . () n- . ( ) . , 0 9. - (0-9). ' (Yl, Y2,...) . ( 3), .
3 -
Y8 | Y4 | Y2 | Y1 | Y8 | Y4 | Y2 | Y1 | ||
Y1 ' - X1, , 5, 7, 9, Y1=X1 X3 X5 X7 X9. , : , ( 21). Y2=X2 X3 X6 X7; Y4=X4 X5 X6 X7; Y8=X8 X9. , : , ( 21).
|
|
21 -
() , , . , , .
5551 - 8421 22. - , .
22 - 5551: ) ; )
. , 5554 ( , 23, ) 1 4, 5551 1761 1 10, 555 ( 23, ) - 1 16.
, () N .
27. Q Di, i l, 2. ,
.
, .
( ), ( ), ( 28). V ( ). ̳ 5612 , . .
: , . ( select - ).
27 -
28 -
. , i- ( Ai, Bi , Pi) Pi+1.
( 4)
( 29). 30. , 瑺 ( 31).
4 -
г | S | Pi+1 | ||
29 -
30 -
31 -
-, - , ' - . 555, , : 5551, 5552 5553 (. 32).
32 -
57. , - . , .
1
Di Q, Ai. . .
A0 | A1 | E | Q |
* | * | ||
D0 | |||
D1 | |||
D2 | |||
D3 |
, , , 4, 8, 16- ( 4-1, 8-1, 16-1). .