close

Вход

Забыли?

вход по аккаунту

?

2001-0103-0-01

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
Санкт-Петербургский
государственный университет аэрокосмического приборостроения
?. ?. ???????
?????????? ????
??????? ???????
Санкт-Петербург
2001
??? 621.391.254.019.4 (075)
??? 32.811.4
?62
??????? ?. ?.
?62 ?????????? ????: ????. ???????/ ???????. ???., 2001. 80 ?.: ??.
? ??????? ?????????? ???????? ??????????, ???????????? ? ????????? ???????????????? ?????????? ?????, ?? ???????????, ????????,
????????????? ? ?????????????, ? ????? ??????????????? ??????????
?????????? ? ???????????? ????????? ???? ?????.
?????????? ??????? ?????????? ?????????? ????? ? ???????????????? ????????, ? ??? ????? ? ??????? ? ??????????? ???????? ?????.
?????????? ??????? ?????????? ???????????? ?????? "??????????
????".
????????????? ??? ???????????????? ?????????????? ???? ????
????????.
??????????:
??????? ??????????? ?????????????? ??????
?????-?????????????? ???????????????? ???????????? ????? ?????????;
???????? ??????????? ???? ?????? ?. ?. ???????
??????????
???????????-???????????? ??????? ????????????
? ???????? ???????? ???????
© ?????-?????????????
??????????????? ???????????
???????????????? ???????????????, 2001
©
2
?. ?.???????, 2001
???????????
??????????? ????? ??????????? ?????? ????? ???????? ??? ???????? ?????? ???????? ??????? ????????? (?? ????????? ?? ???????????)
? ???????? ????. ??-?? ??????? ????? ? ??????? ????? ???? ??? ?????? ?????? ???????? ???????? ????????? ???????? ??????, ??? ????? ????????, ???????? ? ??????????? ???????? ?????, ? ???????????????? ????????????. ? ????????? ????? ?? ??????? ????? ??????????
???????? ?????? ?? ????? ???????? ???????????? ? ?????????????
???????????? ??????????, ??? ????????????? ??? ?????????? ???????????? ?????????????????? ???????-???????? ??????? ??????????,
??????????? ?????????? ????????, ????????? ???????????? ????
????????? ??????????? ???????????? ?????????? ??? ?????? ???????????.
????????????????? ????????? ?????? ? ???????? ? ???????? ???????? ????? ???????? ?????????? ????????????????? ???????????, ??????????? ?? ???????? ????????????? ???????????? ? ????????????
?????????, ??? ???????? ? ?????????? ???????????? ?????? ?????? ?
?????????? ?????????????? ???????? ????????.
?????? ? ??????? ????????????????? ??????????? ?????? ????????? ?????? ? ????? ???????? ?? ????????????? ????????????? ?????????? ????? ? ???????????, ? ?????????? ?????, ? ????? ????????? ??
???????? ?? ???????? ????? ?????????????? ?????? ? ??????????? ?????? ??????? ? ?????? ????? ? ??????????? ?????? ? ???????? ???????? ?????.
???????????? ???????????? ????? ??????? ?? ??? ??????: ???????
???? ? ??????????? ????. ? ??????? ????? ???????????? ?????????????? ?????????????????? ??????????? ?? ????????? ????? ? ??????????? ? ??????? ????? ????????????? ????? ??????????? ????????.
??????? ?????????? ?????????? ? ???????????? ?????????? ???? ??
?????. ? ??????????? ?????, ?????????? ????? ???????, ?????????????, ??????????????? ??? ???????????, ???????????? ?????????????? ?????????????????? ?? ??????????? ?? ?????, ? ??????????? ???3
???? ??????????? ? ???????????? ??????? ????? ???????????????.
???????? ??????????? ? ????????????? ????? ?????????????? ? ??????????? ??????.
? ????? ? ?????????? ? ?????? ? ??????? ??????????? ? ??????????? ???????? ????? ???????????? ? ??? ??? ???? ??????? ???????????????? ????. ???, ? ???????? ????????????? ??????????? (???????????? ???????) ???????????? ??????? ??????????? ????, ? ??????? ???????? ????? ??????????? ??? ???????, ??? ? ?????????? ????, ? ??????????? ??????????? ??????????? ?????? ?????, ? ????????, ???????????? ??????????? ?????????? ????.
????????? ??????? ??????? ???????? ??????????? ??????????? ?????
????????????????? ??????? ???????? ??????????? [1]. ? ???????? ???????? ????? ??? ?? ???????? ????????? 4 ???????????? ??????, ????????? ? ??????? ? ????????? ???????????: ?????????? ????? [2], ???????????? ????? [3], ??????????????? ????? [4] ? ???????????? ?????
[5]. ?????? ????????? ??????? ???????? ???????, ???????? ??????
????????? 5-? ???????????? ?????? ??????????? ?????.
???????? ??????? ??????? ? ???????????? ? ??????????????? ?????????? ??? ?????????: ??????????? 654200 ? ??????????????, ????????????? 200700 ? ????????????; ??? ?????????: ??????????? 552500 ?
??????????????; ??? ???? ???? ????????: ??????????? 654100 ? ???????????? ? ?????????????????, ????????????? 200400 ? ????????????
???????????.
????? ???????? ??????????????? ? ????????????? ???????? ??????
2502 ?. ?. ???????? ?? ?????? ??? ?????????? ?????????? ???????, ??
????????? ??????? ???????? ?????????? ???????????? ???????, ?? ?????????? ????????? ?????????? ?????? ?? ???????????.
4
1. ?????? ???????????? ??? ?????
?????? ??????????? ???????????? ??? ??? ????????? ? 1955 ?. ????? ????????????????? ?. ?. ?????? [6], ??????? ?????? ???? ?????????
???????? ? ????????????? ??????? ???????? ?????, ? ????? ??????? ? ?????????????????? ????????? ????? ??. ?. ?. ????-????????.
?????? ???????? ??????????? ????? ?????? ????????????? ? ??????? ????? ????????????? ?????? ? ??????? ??????????? ? ??????? ????
?????? 4 ???? (? 1959 ?.) ?????? ????????? ???????????? ??? ??? ?????? ?? ????? ??? ????????? ?????? ? ????? ????????????? [7].
? ???? ????? ????????????? ????????? ????????????? ???????????? ? ??????????? ? ???????? ??????? ??????????? ?????????? ?. ????????? ? ?. ??????? ?????, ???????????? ??????? [8]. ?????? ??
???????? ?????????? ?? ????????????? ???????? ? ??????????? ????? ????????????? ?????? ? ??????? ?????? ? ???????? ???????????
? ???????? ?????????: ???? ????????, ???????? ????????? ????????
?????? ?????????? ???????? ?????????? ?????? ????????? ?????, ??????????? ? ????????? ?????. ???????? ?? ???? ????? ???????? ?
????? ?. ?. ????????? ? E. ?. ??????????? ?????????????? ??????????? ?????? (1968), ????????????? ????? ??????? ?????? [9]? ? ????? ? ????, ????? ????, ????? ?????????? ??? ?????? ????? ???????
?? ???????? ?????, ???????????? ??????, ? ???????? ????.?
???????, ??? ?. ?. ???????? ? E. ?. ?????????? ? ???? ????? ????????? ???? ? ? ????????? ????? (??? ??????? ??????????? ???? ?
??????????) ???????? ? ????.
????, ?????????? ???? ?????????? ????????????? ???? ????? ? ????????? ?????? ?. ?. ?????, ??????? ??????????? ? ?????????? ??????? ???????? ?????????? ?????????? [10] ? ????? ?????????.
?? ???? ???? ?????????????????? ??????? ???????? ?? ???????????
?? ????????? ??????? ??????????. ? ????? ?????????????? ???????? ?????????? ?????????????? ???????, ??? ??? ????? ???????
????? ??????????????? ????????? ?????????? ???? ???????????5
???. ????????? ?????????????? ??????? ????? ai, ? ??????????????
????? bi ???????? ????? ?????????????????? ????????:
a1b1 a2b2 a3b3 ??.a kb k a k+1b k+1 ?.
?????????????? ??????? ???????????? ???????????? ??????????, ? ?????????????? ??????????? ?? ?????????? ???????:
(1.1)
bi = ak?S + ak+S+1 (mod2),
??? s ? ???????????? ????? ?????, ?????????? ????? ???? (s = 0,1,2?).
????????, ??? ??? ????????? ?????? ?????????? ??????????????? ??????? bi ??????????? (1.1) ? ???????? ?????????????????? ?? ????? ????????? ??? i = k. ? ?????? ?? ?????????? ?????? ??????????????? ??????? a i ??????????? (1.1) ?? ????? ??????????? ??? ????
????????? k, ? ?????? ??? k1 = i ? s ?1 ? ??? k2 = i + s. ?????? ?????
??????? ??????? ??????????? ?????? ??? ?????????????. ? ????????
??????? ?????????????????? ??? ??????? bk ??????????? ???????????
(1.1). ???? ??? ????????? ?? ??????????? ??? ???? ????????? k (k = k1
? k = k2) ? ??? ????
k2 ? k1 = 2s+1,
(1.2)
?? ????????????? ??????? ak1+S+1 ?????? ???? ??????? ?? ???????????????.
????????, ??? ???????????? ?????? ???? ????? 1/2. ?? ????????? ?????????? ??? ???????? ???????? ???????, ????? ????????? ?????????
?????????. ???, ???? s = 0, ?? ???????????? ?????????? ?????????????,
????? ????? ????? ???????? ????????? ????????? ??????? ?? ????? ????
(? ? ????????? ??????? ????) ????????? ???????? ???????? ( ??? ????
??????????? ??? ??????????????, ??? ? ?????????????? ???????).?
??? ??????????? ? ????. 1.1, 1.2 ? 1.3 ?????????? ???????? ???????? ?????????????? (???????????) ????? ????? ??? ????? s = 0,1 ? 2
??????????????. ??? ?? ???????????? ???????? ????????????? ???????? ??????????????????? ? ??????????? ?? ???? ????? ??????????
?????????. ?????????? ??????? ? ?????????? ?? ????????????? ?????????? ? ???????? ?????? ???????. ??? ???? ??????????????? ???????? s = 0,1 ? 2 ??????? ???????? ????????????? ??????????????????
?? 10 ???????? 0001101011 (??? s = 2 ? ? ??????????? ?? 14).
??? ????? ?? ????????????? ???????? ???????????? ????? ?????
???????????? ?? ?????? 2, ? ???????????? ? ?????????? (1.1), ?????????????????? ??????????? ???????? ?????????? ????????? ? ???????????? ????????? ???? s.
6
???????. 1.1
S=0
?????????? ????????,
??????? ???????? i
?????????????? ???????,
???????????? ?? mod2,
??????????? ???????
a1b1
1
0
a2b2
2
0
a3b 3
3
0
a4b4
4
1
a 5b 5
5
1
a6b6
6
0
a 7b7
7
1
0
0
1
0
1
1
1
???????? ??????????????????
0 0 0 0 0 1 1 0 1 1 0 1 1 1
????????????? ??? ?????? ? ????? ?????????????? ???????
0 0 0 0 0 1 1 0 0 1 0 1 1 1
???????? ??????????????????,
???????????? ?? mod 2,
????????? ????????????
0
0
1
1
0
1
1
1
0
1
0
0
0
1
?????????????? ??????????????????
????????????? ??? ?????? ? ????? ??????????? ???????
0 0 0 0 0 1 1 0 1 0 0 1 1 1
???????? ??????????????????,
???????????? ?? mod 2,
????????? ????????????
0
0
1
0
1
1
1
0
0
0
1
1
0
1
?????????????? ??????????????????
????????????? ??? ?????? ? ???? ??????????? ????????
???????? ??????????????????,
???????????? ?? mod 2,
????????? ????????????
0
?????????????? ??????????????????
0
0
0
0
0
0
0
0
1
0
0
0
0
1
1
1
1
1
0
1
lc = 3
1
1
0
0
1
a 8b 8
8
0
0
1
1
1
0
0
0
1
1
0
1
0
0
1
1
0
1
0
1
1
1
1
0
1
0
1
0
a 10 b 10
10
1
1
0
1
1
a9b9
9
1
0
0
1
1
7
8
???????. 1.2
S=1
??????? ???????? i
?????????????? ???????,
???????????? ?? mod2,
??????????? ???????
1
0
2
0
3
0
4
1
5
1
6
0
7
1
1
1
0
0
1
1
0 1 0 1 1 0 1 0 0 1 1 1
????????????? ??? ?????? ? ????? ?????????????? ???????
???????? ??????????????????,
0
0 1 0 1 0 0 1 0 0 1 1 1
???????????? ?? mod 2,
????????? ????????????
0
1
0
1
1
1
?????????????? ??????????????????
1
1
0
1
0
0
????????????? ??? ????? ?????? 3 ????????
0
0 1 0 1 0 1 0 0 0 1 1 1
???????? ??????????????????,
???????????? ?? mod 2,
????????? ????????????
0
0
0
1
0
1
?????????????? ??????????????????
1
1
0
1
0
0
???????? ??????????????????
lc = 7
8
0
0
0
0
0
0
9
1
10
1
1
1
1
1
0
0
0
0
0
0
???????. 1.3
S=2
i
1
0
2
0
3
4
0
0
5
1
0
0
1
6
1
1
1
1
7
0
0
0
0
1
0
0
1
0
0
8
9
10
11
12
13
14
0
1
1
1
0
1
1
0
1
1
0
1
1
1
1
1
1
1
1
1
0
0
1
1
0
????????????? ??? ????? ?????? 5 ????????
0
0
0
0
1
1
0
1
1
0
1
0
1
1
1
0
1 0
1 1
1
0
0
0
1
0
1
1
1
0
1
0
0
1
1
lc
= 11
9
?????????? ??????????? ??????????? ??????? ???????????? ????? ????????? ??????????????, ??????? ??????????????? ???????
??????????????????, ?????????? ???????? ?? ?????? ?????.
?? ??????? ?????? ?????????????? ?? ?? ????? ????????? ????????? ??????????? ????????, ??? ? ?? ??????? ???????? (1.1), ? ???????????? ????????? ?? ? ????????? ???????????? ?????????. ???? ???
?????? ?????? ???, ?? ????????? ???????????? ?? ?????? 2 (?????????) ????? ???????? ?? ??????????????????, ?????????? ???? ????. ???
??????????????????, ??? ?? ??? ? ??????? ??????????? ?????, ?????????? ?????????. ???????? [5], ??? ?????? ????????? ??????????? ??
??????????? ???????? (? ?????????? ? ?????? ???????) ? ???????? ????????? ????????? ???????, ??????????? ??? ??????? ???????????.
? ?????? ??????????? ???????, ??????? ????? ???????? ????????????? ??????, ???????? ???????????? ?????????, ??????????? ??? ???????????? ??????. ??????? ????????? ???????????? ???????????
??????, ??????? ???????? ? ????????? ? ?????????? ?????????????????? 1 ?? ??????????????? ????????. ? ????.1.1?1.3 ???????????????
???????? ?????? ? 1 ?? ????????, ???????????? ???????????? ??????, ?? ???????. ?? ???????? ?????????? ???????????? ?? ?????? 2 ??
????????? (1.1) ?????????????? ???????? ai, ??????????? ? ????????, ?????? ???????, ???????????? ???????????? ??????, ????????
? ???????? ?????? ???????.
??? ????? ?? ????. 1.1, ??? s = 0 ?????? ??? ?????? ?????? 5-??
??????????????? ??????? ???????? ??? ????????????? ? ?????? ????
??????????? ???????? 4-?? ? 5-??, ??? ????????? ????????? ??????????? ????? ???? 5-? ?????????????? ??????, ? ???????????? ? ??????????? (1.1) ? (1.2).
????????????? ??? ?????? ? ????? ??????????? ??????? ??? ?????? ????????? ???? s ???????? ? ?????????? ???????????? ????????
?????? ? ????? ???????, ??? ?? ?????? ?? ?????????? ????? ????????????? ??????????????????.
????????????? ??? ?????? ? ???? ?????????????? ????????
(????. 1.1, s = 0) ??????????, ??? ??? ??????? ????????????? ????????? ??????? (4-? ? 6-?) ?????? ???? ?????????, ????? ?? ???????????
? ???????????? ?????????? ??????????? ????????. ??? ????? ??????
?????? ?????????? ??????????? ???????? ? ?????????? ????????????
?????? ??????????? ??? ?????????? ?, ?? ??????? ????, ??? ????????.
? ????. 1.1 ???????? ????????, ????? ? ?????????????????? ????????10
??? ???????? ??????? ???????????? ?????? ?? 4 ?????? ????????? ???????? ? 3-?? ?? 6-?, ??????? ???????? ?????? ???????.
??? ??????? ?????????? ??????? ??????? ???? (lc = 3) ????? ??????????? ???????? ????? ????? ??????????? ??????????????? ?????????. ??????? ???? ???????? lc ? ??????????? ????????.
? ???? ??????, ????? ??????????? (1.1) ??????????? ?? ???????????
??? ?????? ??????????? ???????? ? 3-?? ?? 6-?, ? ???????????? ? ?????????? (1.2) 4-? ? 6-? ?????????????? ???????? ?????????? ?? ???????????????, ?. ?. ?????????? ?????? ??????????? ???????? ???????? ?????????????? ???????? ? ???????? i = 4 ? i = 6. ?????? ? ???????? ????????
lc = 3 ???????? ????? ??????????? 5-? ?????????????? ??????, ???
???????? ??-?? ???????? ???????? ???????? (?????? 4-?? ? ??????? 6-??)
?????????????? ???????? ????? ????? ??????????? ??????? (1.2) ? ??,
????? ????????, ????? ? ???????? ??????? ?? ???????????????.
??? ???? ????? ????? ?? ????????? ?????????? ????????? ?????
????? ??????????? ???????? ????? ?????????? ???????????????
?? ??????? ???? ?? ???, ????? ???? ??????? ???????????? ??????????? ???????? ?? ???????????. ??? ???????? ? ????, ??? ???????????
?????????? lc = 3 ????????? ????????? ?? ??????? ???? (??? s = 0) ?? l? = 2
(??? ?????????????? ???????). ????? ???????, ??? ???????????? ????????????? ?????????????? ???????? ????????? ????? ????? ???????? ???????????? ????????? ????? ???????? ???????? l0 = lc + l? ??
????? ??????????? ???????? ? ?????? ???????????. ??? ???? ????? ?
????? s = 0 ???????? l0 = 5. ?????????? ???? (s>0) ???????????? ??????????? ??????????? ?? ?????? ????????? ???????? ? ???????????
??????????????????, ?? ? ????? ?????? ????????? ????????. ??? s = 0
??? ????? ?? ???????? ?????????? ???? ??? ?????? ????????? ????????? ???????, ? ??? ???? s = 1 ?????????? ??????????? ???????????
????? ?? ???? ???????? ????????.
???????? ?????????? ?????? ????????? ? ?????????? ???????????
? ??????? ???????? ????? ??????????? ?????????, ???????????? ??????? ?????? ???????????? ?????? ???????. ??????????? ???????? ????????? ? ? ??????? ? ???????????????? ??????????? ??????? (????????????????? ??????), ? ?????????, ? ???????? ????????? ????? [11].
??? ???? ???????? ?????? ??? ?? ??????????, ? ????????? ?????????, ????? ???????????? ??????? ????????????? ???????????? ??????.
? ???? ????? ????????? ???????? ???????????? ????????? ????????
?????????? [7] ????????? ?.?.: ???? ???????? ????? ???????? ????11
????? ????????????????? ?????????, ????????? ? ??????????? ??? ???????????????? ??????? ????????????. ???, ????? ?????? ??????????? ? ???????? ???????? ??????????? ??????? burst of error ??? ??????
?????? ?????? ???????, ???? ? ??????? ?????????? ??????????? ? ?????? ???????? (?????? ???????, ???????? ??????? ? ?. ?.)?. ? ??????????, ????????????? ? ?????? ????????? ?. ?., ????? ????????????
???????? ????? (?????) ??????.
????? ?????? ?????? b ???????????? ???????? ??????, ? ???????
??? ??????? ????????? ? ?????????????????? b ???????? ??? ???????, ??? ??????? ??????? ???? ?????????????????? ? ???????. ???,
??????? ?????? ??? ????? ?????? ?????? b = 4 ????? ????????? ????????? ??????? (??? ?????????????????? ?????? n = 10): 0001101000,
0100100000, 0000011110 ? ?. ?.
?????? ? ????? ??????????? ??????????? ????? ?????? ? ???? ?????
??????????? ???????? ?? ???? ??? s. ??? ?????????? ??????? ???????? s
???????, ???????? ? ???? ? ?? ?? ???????? ?? ???????? (1.1), ????? ????????? ?? ??????? ?? ???????, ??? ????????? ?????? ?? ??? ????? ??????
??????????. ??? ???? ????? ?????? ?????, ??? ???????, ??????????? ?????? ???????, ?? ????????? ???? ? ?????? ?????????? ?? ???????? (1.1).
? ????. 1.2 ??? ???? ????? ? ????? s = 1, ?????? ? ?????????? ??????????????? ???????? ???????????? ???? ? ????????????? ??? ?????? ?
????? ?????????????? ???????, ??????????? ????????????? ????????
?????????????????? ??? ????? ?????? ?? ???? ????????. ??? ?????, ?????????? (??????) ??????? ?? ??????? ???? ? ?????? ?????? ??????????
?? ???????? (1.1). ? ????? ? ???? ??? ??? (2 ????????????? ? ???? ??????????? ????? ????) ????? ???????????? ?????????. ??????????? ? ????
? ????? s = 0, ?? ????. 1.1 ?????, ??? ???????? ? ?????????????? ?????????? ???????? ??????????? ?????? (????? ??? ??????), ??? ???????
??? ?????????, ???????? ? ????????? ????????????? ??????????? ??????????????????. ????? ???????, ??? ???? s = 0 ? ???? ????? ????????????
????? ?????? ??????????? ? ???? ?????? b = 1.
??? ???? s = 1 ? ????? ?????? ?? 3 ???????? ??????????? ?????????? lc = 7, ? ????? ??????????? ?????????????? ????????? ??????????? ???????? ??? ???????????? ????????????? l? = 6. ??? ???????? ?
????, ??? ?????????? ????????????? ?????????? (???? ??????????) ?????????????? ??????? ??? ????????? ????? ?????? ?? ???? ????????
???????? ??? ???????? (???????????) ????????? ? ?????????????
???????? ????????? l0 = lc + l? = 7 + 6 = 13.
12
? ????. 1.3 ??????????? ???????? ???????????? ???? ????? ? ????? s
= 2, ??? ???? ??????????? ??????? ????????????? ????? ??????, ????????? ?? 5 ????????. ??? ???? ??????????? ?????????? lc = 11, ?????????????? ? l? = 10 ? ?????????????? ???????? ???????? l0 = 21 ?????
???????????? ??????? ????? ????????????? 1.4
?? ??????????? ???????? ?????????.
? ????. 1.4 ?????????? ?????? ??????s
b
lc
l?
l0
????? ??? ???????? ???????????? ??????0
1
3
2
5
?????? ????? ?????? b ? ????????? ??1
3
7
6
13
??????? l0 ?? ????? ???????? ??? ????
2
5
11
10
21
????????? ???? s = 0,1,2 ???? ?????.
2si+1 2b+1 2b 4b+1
si
?? ????????? ?????? ????. 1.4 ??????????????? ????? ????? ????? ???? ????? s, ?????? b ???????????? ????? ??????
b = 2s+1
(1.3)
? ???????? ??????????
(1.4)
l0 = 4b +1.
????????????? ????? ???????? ??????? ? ????????????? ????????? ????? ??????????? ????? ?????? ????????? ? ??????????? ???? ???????????? ?????.
??????? ???????? ?? ??, ??? ??? ??????? ????????????? ??????????? ??????? ?????????????????? ?? ??????? ?????? ?????? ???? ?????????? ??????? ????????????? ?? ???????? ?????????, ????????????
??????? ?????????? ????????????? ? ??????????? ????????. ? ????????? ??????, ??? ???? ?????????????, ?????? ????????????? ?????????? ???????????, ????????? ??????????? ?????????????? ??????? ????? ???? ?????????? ??? ??????????? ? ????????. ??? ???????????? ????????, ????????? ? ????? ????????????, ?????? ????????
?????????????? ??????? ?????????? ????????????? ??? ?? ????????,
??? ? ?? ???????? (??? ??????? ???????????) ?????????.
??? ?????????? ?????, ??? ????? ??????? ???????????? ? ????????
????. ?????? ?????????? (????????????) ????, ???????????? ?????
??????, ???? ??????? ????? ??????????????. ?????? ? ?? ? 1963 ?.
??????? ???????????? ????? ??????????????? ???????? ?????? ?????????? ????? [13] ? ????? ??????? ????, ???????????? ????????? ??????. ? ?????????? ?????? ?????????? ?????????? ????? ???? ???????? ?? ?????? ?????????? ?????.
13
2. ???????? ?????????? ??????
?????????? ???????????, ????????????? ? ????? ???? ??????????
[6?27], ??????? ????? ?????????, ???????????? ???????? ???????????????? ??????????? ??????????. ?????????? ????? ???????????? ?????
??????????, ?????????????? ?? ?????? ???? ?????? ? ????? ?????? k
??????? ?????????????? ????????, ? ???????? ?? ????? ?? ??? ??
???? n ???????? ????????, ?????????? ???????? ?? ?????? ?????.
????????? R = k/n ???????? ????????????? ????????? ????. ???????? ???????, ??????????? ??????? ?? ?????? ?????, ??????? ?? m ?????????????? ????????, ??????????? ?? ???? ? ?????????? ??????.
????? ???????, ???????? ??????? ??????????? ?????? ?????????? ???????????? ??? ??????? ???????? ? ??????????, ????????? ?? m?k ?????????? ?????????????? ????????. ??????? ???????? ?? ??, ??? ?
???? ????? ???????? ??????? ?????? ??????? ??? ?? ??????????, ???
? ?? ??????????? ?????????????? ????????, ? ???????????? ? ?????????? (1.1), ????????? ??? ???? ± s ? ??????????.
????????? ?????????? ??????????? ?????? ????????: ??????? ??????, ????????? ?? ?????? 2 ? ??????????.
??????? ?????? ???????? ???????????? ???????????? ???????????
(??? 2.1), ? ??????? ???????? ???????? ??????? 0 ??? 1. ????? ?????????? ????? m ? ???????? ?????? ? ?????????? ?????? ????. ? ??????
??????????? ?? ???? ???????? ?????? ??????????????? ??????? ??????, ?????????? ? ??????? ?????? ???????, ????????? ?? ???????? ?
????????????. ?????? ?? ?????????, ?????????? ? ???????? ????????
???????????? ?? ???? ?????? ??????, ?????????? ??? ????? ???????
????? ??????, ???? ? ????????? ????? ?????????????? ??????.
?) ????
?????
1
?) ????
1
2
3
2
3
???. 2.1. ??????? ??????
14
...
m
...
m
?????
???????????? ??? ????????? ??????????? ????????? ??????: ? ?????????????? ??????? ???????? (???.2.1, ?) ? ? ?????????????????
????????????????? ??????? ????? ???????? (???.2.1, ?), ??? ???? ??????????? ?? ?????? ?????????? ????? ???????????????? ???????? ?????????? ????????, ? ?????????, ????? ???????????? ?? ?????? 2 [5].
???????, ??? ??? ??????????? ??????????? ????????, ??? ???????,
?? ????????? ???? ??????, ?? ??????? ????????? ???????? ????????,
???????????? ?????????? ?????????? ?? ????????.
???????? ?? ?????? 2 ???????????? ???????? ??????????? ?? ???
????? ???????? 0 ? 1. ??????? ???????? ?? ?????? 2 ?????????: ????? ???????? ???????? ????? 0, ???? ????? ?????? ????? ???????????
?? ????? ???????? ?????, ? ????? 1, ???? ??? ????? ???????. ? ?????????, ??? ???????????? ????? 0 ? 0 = 0, 1 ? 0 = 1, 0 ? 1 = 1, 1 ? 1 = 0, ???
?????? ? ???????????? ???????? ?? ?????? 2.
??????????? ???? ????? ???? ?????, ??? ???????? ?? ???. 2.2.
m2
???. 2.2. ???????? ??????????? ???? ???????????? ?? ?????? 2
?????????? ???????????? ???????????????? ?????????? ???????????
?? ??? ????? (????????) ???????? ? ????????????? ?? ?????? ???????????
??????? ??????? ???????? ? ????? ?????. ??????????? 3 ???????? ??????????? ???????????? ? ?????? ?????????? ??????? (???. 2.3)
?)
?)
1
2
n
?????
1
2
?)
?????
1
2
n
?????
n
???. 2.3. ???????? ??????????? ????????????
?? ???. 2.3, ? ???????????? ????????? ????? ???????????, ?? ???. 2.3, ?
? ????????, ?? ???. 2.3, ? ? ? ???? ???????? ??????. ???????? ???????
???????????? ? ????? ????????? ??????????? ? ?????????? ???????
???????????? ????????????? ????????? ???? R = k/n, ??? k ? ????? ????????????? ????????; n ? ????? ???????????? ? ????? ????? ???????? ?? ???? ???? ??????????? ?? ????? ??????????????? ???????. ?
15
???????????? ? ???? ????? ????????? (????? ???????? ?????? ???????????) ?????? ???? ????? n, ? ??????? ???????????? ?????? ???? ? n ???
?????? ??????? ???????? ???????. ???, ??? ???????? R = 1/2 ? ??????????? ?????? ???? 2 ???????? ? ???????????? ?????? ?????????????
? ????????? ???????? ????????.
??? ??????? ?? ???. 2.4 ????????? ?????? ???? ????? ? ?????????? ?????? S = 0,1,2, ?????????? ?? ????????? R = 1/2.
S=0
?????
S=1
S=2
?????
?????
???. 2.4. ?????? ??? ???? ?????
?? ???????? ? ????????? ??????, ?????????? ???? ????? ???????????????? ?? ??????????????? ? ?????????????????. ??????????????? ?????????? ????? ???????? ????? ???, ??? ???????? ? ????????
?????????????????? ??????? ???????? ?????????? ??? ????????? ?????????? ?? ?????????????????? ?????????????? ????????. ? ?????????
?????? ?????????? ??? ???????? ?????????????????. ?? ???. 2.5, ? ? ?
????????????, ??????????????, ??????? ??????? ???????????????? ?
?????????????????? ??????????? ???? ??? R = 1/2. ? ?????? ?? ????
??????? ??????? ???????? ?????????????? ??????? ????????? ? ?????????? ???????, ????????? ?? ???? ?????, ???????????? ? ????????
??????? ?????????. ????? ??????? ?? ???? ??????????? ???????? ?????????? ??????????????? ??????? ?????????? ?????????? ??? ??????
? ?????? ?? ??????? ? ????????? ??? ????? ??? ???????? ???????
???????. ? ?????? ???????????????? ??????????? ???? (???. 2.5, ?) ?????? ?? ???????? ??????? ????????, ?????????? ?? ?????? ???? ?????? ???????????, ?????? ????? ????????? ?????????????? ??????, ??????????? ? ?????????? ???????. ?? ???. 2.5, ? ????? ??????, ???
???????? ?????????????????? ??????? ???????? ?? ???????? ???????
?????????????? ??????? ? ?????????? ????, ??????? ????? ?????
????????? ????????????????? ?????????? ???.
16
?)
?)
?????
?????
????
????
???. 2.5. ??????? ??????? ???????????????? (?) ?
?????????????????? (?) ??????????? ????
? ????? ?????? ?????????? ??????? ?????? ??????????? ???? (???. 2.6)
???????? m ?????, ? ?????????? ?????? ???? ???? ?????? ??? ??????? 1 ? k < m ????????? ?????????????? ????????, ??? m ?????? k,
????????? ?? ???? ???? n ? 2 ??????? ??????. ??? ????, ????????,
??????? ?????? ???????? ??????????????? ??????? ????? ???????????????? ?? l? = mn/k ???????? ??????? ????????. ??? ???????? ?????????? ?????? ?????? ???????? ??????????? ? ?????? ????, ???????????
???????? ????? ???? ??? ??????? ???????????. ????? ???????? ??????????? ? ?????????? ????? ?????? ? ???????? ??????????? ????????
?? ????????? ?? ?????? 2 ????? ?????????? ?????????????? ????????
??????????? ??????????? ????.
??????????????
???????
0
1
m?2
2
m?1
? ?????
???. 2.6. ????? ??? ????????? ??????????? ??????
??? ???? ????? ?????? ????????? ??????????? ??????, ??????????
???????, ????? ??????? ???????? ?????? ??????? ? ?????? ?? ?????????? ?? ?????? 2, ???? ???????? ??????? ????? ???????. ????? j-?? ????????? ?? ?????? 2 ??????????? ????? ??????? j-? ??????????? ??????????????????
(2.1)
gj = (gj0, gj1, gj2,? gjm?1 ),
??? ??????????
17
?1, ???? i-? ?????? ???????? ?????? ? j-? ??????????;
g ji = ?
?0, ? ????????? ??????.
(2.2)
???????? ????????? ?????????? ?????: k,n = 1,2, ..., 8; R = k/n =
=1/4,...,7/8; m = 2, ..., 10 [15].
???????? ????? ?? ???????? ??????????? ?????????? ???? ?? ????????? R = 1/2 (???. 2.5). ??? ???????? R = 1/n ????????? ?????? ???????? ??????????, ?? ??? ????????? ?? ?????? 2 ?????????? ?? n ??????????, ?????????? n ???????? ???????? ??? ??????? ??????????????? ???????, ???????????? ?? ???? ??????. ?? ???. 2.7, ? ?????????
????? ??????????? ?????? ??? ???????? R = 1/3.
?) A1(X)
?) ????
B1(X)
B2(X)
?????
B3(X)
A2(X)
?????
???. 2.7. ??????? ??????? ??? ????????? 1/3(?) ? 2/3(?)
??? ????????? R = k/n,??? k >1, ??? ???????, ? ????? ?????? ?????????? k ????????? ??????. ???????? ???????? ??????, ?????????? ??
???. 2.7, ? ??? ???? ? R = 2/3. ? ????? ???????????? ???????? ??? ??????? (???? ??? ??????? ?????????????????? A1(X), ?????? ? ??? A2(X)) ?
?????????, ?? ?????? 2 ????????? ??? ??????? ??? ???????? ??????????????????? B1(X), B2(X), B3(X).
?????????? ??? ?????? ???????? ??????????? ??????????? (????????????) ???????????, ???????????? ????? ??????????????????? (2.1),
??????? ????, ??? ??? ???????? ??? ???????? ???????? ???????????
????? [5]. ??????????? ?????????? ????????? ?????????? ?????????
????????? ?????? ??????????? ????. ???????? ??????? ??????? ?????
??????????? ? ???? ??????? ?????????????????? ?????????????? ???????? ? ??????????? ??????????? ????, ???????? ???????? ???????????? ??????? ???????????, ?? ?? ???? ? ????????? ???????.
18
3. ????????????? ?????????? ?????
? ??????? ???????????
? ??????? ?? ??????? ?????, ?????? ?? ??????? ??????????? ???????????? ??????????? ???????????, ?????????? ??? ??????? ??? ?????? ????????
????????? ??????????? ???????????, ????? ??????? ???????????? ???????????
n ???????? ????????, ???????????? ?? ?????? ???? ? ????? ?????.
?????????? ?????????????????? ?????????????? ????????, ??????????? ?? ???? ??????, ? ???? ?????????? (????????)
(3.1)
A(X) = a0+a1X+a2X2+?,
i
??? X ? ?????? ????????? ???????? ?? i ?????? ?????? ???????????
????????; ai = 0;1 ? ?????????????? ???????? ???????.
??????????, ??????????? n ??????????????????? ??????? ????????, ??????????? ?? ???? ??????????? ?????? ? ????? ? ????? ?????,
(3.2)
Bj(X) = b0(j)+b1(j)X+b2(j)X2+?,
(j)
bi = 0;1 ? ???????? ??????? ??????? ?? j-? ????? ??????????? ??????.
? ???? ?????????? ??????????? ????
(3.3)
Bj(X) = Gj(X)A(X),
???
Gj(X) = g0+g1X+g2X2+?+gm?1X m?1 ?
(3.4)
j-? ??????????? ????????? ??????????? ????; gi = 0;1 ? ??? ????????
???????????? (2.1), ?????? 1, ???? i-? ?????? (i = 0, ..., m?1) ??????????? ???????? ????? ????? ???????????? ??????? ? j-? ?????? ??????????? ??????, ? ?????? ???? ? ????????? ??????.
????????, ??? ?????? ???????????????? ??????????? ???? (???. 2.5, ?)
??????????? ?????????? ?????
(3.5)
G1(X) = 1; G2(X) = 1+X 2,
? ??? ?????? ?????????????????? ??????????? ???? (???. 2.5, ?)
(3.6)
G1(X) = 1+X+X2 ; G2(X) = 1+X2.
??????????? ?????????? ????? ???? ?????????? ? ??????? ??????? k Ч n, ?????????? ??????????? ???????? ?? ???????????. ??19
??????, ??????????? ??????? ??? ??????? (???. 2.4), ? ????????????
? (3.5) ? (3.6), ???????????? ? ????
G1(X) = [1 1+X 2] ?
G2(X) = [1+X+X2 1+X 2].
(3.7)
?????? ? ??????? ????????????? ?????? ?? k ???????? ??????? ?????????????????? (? ?????? ?????? k = 1), ? ????? ??????????? ? ??????
????? ????? ???? ???????????? ?? ?????? 2. ??? k > 1 ?????????
??????????? ?????????? ????? ????????? ????.
???, ??? ????? ?????? (???. 2.7, ?) ??? ???????? R = 2/3, ????????
??? ??????????? ?????? ???????????? ??????????, ??????????? ?????? ???????? ?????? ????? ????? ?????????? ? ????? ???????????.
????? ????? ???????? ????????? ? ????????? ????????????????????
????? ???? ???????????? ? ????????? ????????? ?????:
?G11 ( X )G12 ( X )G13 ( X ) ?
[ B1 ( X ) B2 ( X ) B3 ( X )] = [ A1 ( X ) A2 ( X )] ?
?.
?G21 ( X )G22 ( X )G23 ( X ) ?
(3.8)
? ?????? ?????? ??????????? ??????? ??????????? (?????????)
????? ???
?1 + X
G( X ) = ?
? 0
1+ X
X
?
.
+ X ??
(3.9)
??????????, ? ???????? ???????, ??? ????? ?????? (???. 2.5, ?), ???
?????????? ?????????????????? ?????????????? ???????? 101. ????
?????????????????? ????????????? ?????????
A(X) = 1+X2.
????? ?? ?????? ??????? ????????? ?? ?????? 2 ?????? (???. 2.5, ?) ?????????????????? ??????? ???????? ????? 11011, ?? ????????????? ?????????
B1(X) = 1+X+X3+X4.
?? ?????? ??????? ????????? ?? ?????? 2 ????? ?????? ?????????????????? ??????? ???????? ????? 10001, ? ?? ????????????? ?????????
B2(X) = 1+X4.
? ????? ?? ?????? ?????? ????? ???????????? ??????????????????
B(X) ???????? ???????? ?? 5 ?????? ?????????? ??????? ?????????????????? 101 ? ????????????? ????????:
20
B1(X) 1 1 0 1 1
B2(X)
1 0 0 0 1
B(X)
11 10 00 10 11
????? 1 2 3 4 5
???????? ??????, ??? ??????????? ?????????
B1(X) = A(X)G1(X) ;
(3.10)
B2(X) = A(X)G2(X),
??? ????? ???????????? ??????????? ???????? ????? ?????????? ??
?????? 2. [5]
????????? ????????????? ??????????? ???? ? ??????? ??????????? ???????????, ????? ?????? ?????????? ??? ??????????? ??????????????????? ????????????? ???????????? ???????????, ??????????
? ???????? ??? ???????????? ?????. ????????? ?????? ???????? ?????
?????????? ? ???????????? ??? ??????? ????? ??????????? ????????
??????. ????????, ????????? ?????? (???. 2.5, ?) ????? ???????? ? ????
? ???? ???????????????????: 111; 101, ??????? ? ???????? ????? ???????????? ???????????? ??????????????? ??????????? ???????????
(3.6), ? ? ???????????? ????? ?7;5.
???????? ?????????????????? ????????????? ??????????? ??????????? ?????? ???????? ???????????? ????? [16].
??????? ????????, ??? ??? ???????????? ???????????????? ???? ?????? ?? ??????????? ??????????? G1(X) = 1, ?. ?. ? ??????? ???????
???????? ?????? ?????????????? ?????? ??????????????? ?????????
? ?????. ??? ???? ????????? ???? ? ???????? ????? ????? ??????????????? ???????? 100?0 ? ????? ?????? ????????, ?????? ????? ???????? m ? ?????????? ????????. ? ?????????, ??? ???????????????? ?????? (???. 2.5, ?) ? ???????????? ???????????? (3.5) ???????? ?????????? ???? ????? 100 ? 101 (? ???????????? ????? ? 4;5).
????? ???????, ????? ??????????? ???? ???????????? ??????? ??????? ??????? m-?????????? ???????? ??????.
? ????? ?????? ?????????????????? ????????????? j-?? ????????????? ?????????? (j = 1, ..., n) ??? ???????? ????????????? ????? ????? ???
Gj = { g0j , g1j , ..., gmj ?1 }
? ????????? ? ??????????? ??????????????????? ???? (2.1). ????
A = {a0,a1,a2,?} ?
21
?????????????????? ?????????? ?????????????? ????????, ?
Bj = { b0j , b1j , b2j ?} ?
?????????????????? ??????? ???????? ?? j-? ????? ??????????? ??????,
?? ??? ?????? ?? ???, ????????????? ? µ-? ?????? ??????? (µ = 0,
1,2,...), ????? ????????
bµj =
m ?1
? aµ?i gij .
i =0
(3.11)
????? ???????, ?????? ??????? ?????? ???????? ?????????????????? ?????? ??????????? ???? ???????????? ???????? ?????????? ?????????????? ? ??????????? ???????????????????, ??? ? ????????????? ???????? ?????????? ?????.
?????????? ???? ???????? ??????? ??????? ??????????? ??? ???????????? ?????. ??? ???????????? ??????????? ????????? ?????????? ?????????????????? ?????????????? ???????? ?? ????? ?? ????????????, ? ??????? ??????? ???????????.
???????? ??? ???????????? ?, ? ?????????, ??? ?????????? ?????
??????? ???????? ????? ?? ????? ??????, ??? ??? ??????? ??????? ??????????? ?? ???????? ????? ????????? ?????????????? ????????
??? ??????? ????? ?????? ??????. ??????? ???????? ???? ????????
????? ??????? ??? ???????????.
?????? ??????, ?????????? ???? ????? ????????????? ??? ????????? ??????? ?????, ??? ??? ?? ?????? ???? ?????? ?????? ?? ????????
????? ????????? ?????????????? ???????? ??????????? ???????????? ???? ???????? ??????? ????????. ?????? ????? ???????? ??????? ???????? ??????????? ????, ??????????? ? ????????? ???? ?? ?????? ????? ?????? ??????, ???????? ????????????? ??????????, ?????
??? ??? ???????? ??????????? ??????????? ????? ????????? ???????
??????? ???????? (???????? ???????) ???????????. ????????? ????????? ????????????? ???????????? ???????????? ?????????? ????? ????? ?????????, ??? ??? ????????? ??????????? ?????, ??? ??? ??????? ???????????, ??????????? ?????????? ??????? ????????????? ???????? ????? ????, ???????????? ?????? ??????? ???????????. ??? ????????, ??????? ???????? ????? ???? ????????? ??? ?????????? ??????? ????????????? ???????????. ????????? ???????????? ?????????? ???????????? ????? ????????????? ????????? ??????????, ?????????????? ??? ??????????? ? ????????????? ?????????? ?????.
22
4. ??????????? ????????????? ?????????? ?????
?????????? ????? ??? ???????? ??????? ? ??????? ????????? ?????????? ?????????. ????????? ????????? ???????????? ????? ???????????? ????, ??????? ???????? ??????????????? ? ?????????? ??????????? ??????, ? ?????, ?????????? ?????????, ????????? ????????? ???????? ????? ???????????. ????????? 000...0 ?????????? ???????, ????????? ? ?????????. ??? ?????? ?? ????? ?????????? ??????? ???????, ??????????? ??????? ??? ??????????????? ???????? ??
????????? ? ?????????. ??? ????????, ????????? ????????? ??? ??????
??????????? ???? (???. 2.5, ?) ????? ????? ???, ?????????? ?? ???. 4.1,
??? ????????? ????????? ?????? ???????? ????? ??????? a, b, c, d.
?????????? ?????????? ?????? ??????? ???????, ???????????? ?
(m?1) ???????? ???????? (??????? ?? ????? ??????). ?????? ??? ???????
?????? (???. 2.5, ?) ? m = 3 ????? ?????????? ? ????? ?? ??????? ?????????
? 00, 10, 11 ? 01. ??? ????????? ????????????? ???????? ????? (???. 4.1).
????????? ????????? ????????? ???????. ????????????? ????? ????????? ? ????????? 00 ? ??????????? ?? ???? ??????? 0 ????????? ???
????? ? ????????? 00. ?? ?????? ?????? ????? ??????? 00. ?? ????????? ???? ??????? ?????????? ?????? 00 ????? ????????? 00.
????? ??? ??????????? ??????? 1 ??00
??? ????????? ? ????????? 10 ? ?? ??? ?????? ????? ??????? 11. ???? ??????? ?? ??a
00
??????? 00 ? ????????? 10 ??????????
11
11
???????? (??????). ????? ???????? ??????????? ??????? 0 ??? 1. ????? ????????? ?
b
c
????????? 01 ???? 11, ? ??????? ?? ??????
10
01
????? 10 ??? 01 ??????????????. ???????01
01
??? ????????? ????????? ?????????????,
d
11
????? ??????????? ????????? ???????? ??
??????? ????????? ?? ??? ?????????.
10
????, ????????, ? ?????????? ?????- ???. 4.1. ????????? ?????????
?????? (???. 2.5, ?)
??? ?????? ????? ????????? ??????? ???23
???????? ?????????? 011, ?? ?? ?????? ????????? ????????? ??? ???????????? ????????? ?? ????????? 11(d) ? ????????? 01(?); ??????????? ??? ???? ??????? ??????? ????? 01, ??? ???????? ??? ??????????????? ??????, ?????????? ????????. ???????????? ?????????????????? ?????????? ?????????????? ???????? ?????? ?????????? ?????????????????? ????? ????????? ? ??? ???? ??????????? ???????
???????, ?????????? ??? ???????????????? ???????, ????????????
????????? ?????? ?? ????????? ?????????.
??????????????? ????????? ????????? ????? ?????????? ?? ???????,
??? ???? ??????? ??? ?????????? ?????????? (??????????) ?????????.
???, ????????, ?????????? ????????? ??? ?????? (???. 2.5, ?) ?????????
????????? ???????? ???????????? ?? ???. 4.1, ???????? ?? ???. 4.2. ?? ???
???????, ??? ????????? ????? (?????) ????????????? ?????????, ???????????? ??? ??????? ??????????????? ??????? 1, ? ???????? ????? (?????) ? ??????????????? ??????? 0. ?? ?????????? ????????? ?????, ???
?? ????????? ????? ????????? ???????????? ????????? ? ?????? ??????????
?????????????. ???, ?? ???. 4.2 ???????? ????????????? ????????? ?????????? ????????? ????? ???????? ????? ???????? ????? ?????? ??????, ???
??? ??? ??????????? ? ????? ?????????? ??????????????? ??????? ?????? ?????? ???????? ??????? ?????? ? ????? ?? ????????? ??????? ??
???????????? ??????? ????????. ?????? ???????? ??????????? ????????????? ??????? ? ???, ??? ? ?????? ????? ??????? ???????? ????? ?????? ?
??????? ?? ??????, ? ???????? ?????? 2m?1, ??? m ? ????? ????? ? ????????
??????, ??????????? ??? ???????????.
00
?????????
?????????
00
11
11
10
01
a
00
11
10
01
10
01
d
a = 00
11
11
b
11 10
01
00
c
01
a 00
00
b
11 10
01
00
11
01
d
b=
10
d = 11
?????
???. 4.2. ?????????? ????????? ?????? (???. 2.5, ?)
24
01
c = 10
c
10
00
?????????? ????????? ?????????? ??? ??????????? ????, ?? ??????? ????? ???????????? ????? ??? ???????????. ????????, ??? ??????????? ?? ???? ?????? ?????????????????? 1011? ???? ?? ???????
(1 ? ??????????, 0 ? ???????? ?????) ???? ??????????? ???????? ???????????? ???????? ?????????????????? 11100001?
?????? ?????????????? ?????????????????? ???????? ????????????? ???????????? ???? (???????????? ??????????) ?? ?????????. ??????? ?????????????????? ?? ?????? ??????????? ????? ?????????? ?????????? ??? ??????? ??? ????????????? ?????? ??????????. ?????
???????, ?????????? ????????? ?????????? ????????? ?????????????? ??????????????????, ?????????????????? ????????? ?????? ? ?????????????????? ???????? ?? ??? ??????.
??????? ??????????? ????????? ??? ???????????? ??????????? ?
????????????? ?????????? ????? ???????? ????? ??????? ??????, ?????????? ?? ????????? ????????? ????????? ? ?????????? ????????? [8,
14?15, 24?25]. ????, ??????????? ???????? ????????????? ? ???????
???????? ??????, ?????????? ????????????. ????? ???????, ?????????? ???? ????????? ? ??????????? ?????.
25
5. ???????? ????????? ?
?????????????? ?????????? ?????
??? ?????????? ??????????? ?????????????? ?????????????? ??????????????????? ? ???????? ??????? ?????????? ??????????. ?????
????????? ??????????? ???? ???????? ?????????? ??????? ?? m ???????? ? ????????? ?? ?????? 2 ??? ??????????? ??????? ???????? ???????? ??????????????????. ????? ?????????? ????????? ? ????????????? ????????? ????????. ?????????? ?? ?????? ????????????? ??????????? ??????? ??????? ???????? ? ????? ?????. ? ???????????? ?
????? ?????????? ???????????? ?????????? ????? ????? ???????????
??? ?????????? ? ?????????????, ???????????? ????????? ?????.
1. ????? ?????????????? ????????, ??????????? ?? ???? ???? ??
???? ?????? ? k.
2. ????? ???????? ?? ?????? ?????? ? n, ??????????????? k, ??????????? ?? ???? ???????? ?? ????.
3. ???????? ???? ???????????? ????????????
R = k/n
(5.1)
? ????????????? ????????????, ???????? ??? ???????????. ???, ???
????? ????? (???. 2.4) ? ??????? (???. 2.5) ???????? R = 1/2. ??? ??????
(???. 2.7, ?) ???????? ???? R = 1/3, ? ??? ?????? (???. 2.7, ?) ? R = 2/3,
?. ?. ?? ???? ?????? ???????????? ????????? k = 2 ??????????????
???????, ? ?? ?????? ?????????? n = 3 ??????? ??????? ?? ???? ???????
????. ????????? ???????? ???????? R = 1/n ? R = n?1/n (R = 2/3 ??
???. 2.7, ?). ??????? ???????? ???? ????????? ????????? ??????????
??????????? ?????? ?????, ???? ???????? ???????? ????????? ?????????? ?????? ?? ?????? ?????????.
4. ???????????? ????
ж = 1 ? R = 1 ? k/n.
(5.2)
? ?????????, ??? R = 1/3 ????? ???????? ? ???????? ?????????????????? ????????? ?? ????? ?? ??????? ?????????????? ?????????????????? ? 3 ????. ?????? ???????? ?? ??????? ????????????, ???????26
??? ???? ??????? ??????? ??????????????? ????????? ??????? ?????????????? ?????????.
5. ?????? ????, ?????????? ????? ??????? ?????? ???????? ??????????? ??? ?????????????? ?????? ???????? ????? [18], ????????????
???????????? ???????? ???????????? ?????????? ? ??????? ??????????? ??????? G(X) (3.9):
l = k max ??deg gi, j ( x ) + 1?? ,
i, j
(5.3)
??? deg gi, j(x) ? ??????? (?? degree ? ????.) ???????????? ??????????.
? ???? ???????, ???????????? ??????? ?????? ?? ??????????? ??????????? ?????????? ????? ???????? m ? ???????? ?????? ?????? (???. 2.6). ?
?????? ???????? ????? ?????????? X0 = 1 ????????
m = max ?? deg gi, j ( x ) + 1??
(5.4)
? ?????? ??????????? ????? ???????? ? ???????? ??????.
????? ???????, ?????? ???? (??????? ????? ???????? ???????????)
???????? ??????? ??????????
l = km,
(5.5)
?????? ??? ???????????? (k = 1) ??????? ?????????????? ???????,
??????????? ? ????? ??? ???????????? ??????????? ???? ?? ???? ????,
l = m, ?. ?. ?????? ???? ???????????? ?????? ????? ? ???????? ??????,
??????????? ??? ???????????.
??????? ???????? ?? ??, ??? ? ???? ?????????? [6?8, 18] ??? ??????????? ?????????? ??????? ??????? ???? ??????????? ?????????
X0 = 1 ???????? ? ??????????????? ????? ???????????? ?? ?????? 2
??? ??????????????? ?? ??????? ??????????? ?? ? ?????? ?????? ???????? ?????? ??????, ??? ??? ???????? ?? ???. 2.6 ? ? ?????? ?????? ?????????? ???????, ? ??????????????? ?? ??????? ????. ??? ???? ?????
????????? ???????? ? ???????? ?????? ?? ???? ???????????. ????? ????????? ?????? ??????????? ???????? ?????????? ????????? ??????.
6. ?????? ????? ???????? ??????????? (???), ?????????? ????? ???
?? ?????? ?????? [23] ??? ??????? ?????? ????? [18], ??????????????
?????? ??????? ????????, ??????????? ??????? ? ?????????? ??????? ????? ???????????? ? ???? ??????? ?????????????? ??????? ?
??????? ? ????? ???????????????? ???????, ? ???????????? ????????
??????? ?????? ????????? ???????. ? ?????? ????, ??? ?????? k ????27
?????? ? ?????????? ???????? ?????? ?????????????? ??????? ?????????????? ?? ?????? n ?????????, ?????? ??? ????? ????????????
?????????? [18]
l? = n max ??deg_ gij ( x ) + 1?? ,
(5.6)
??? ? ???????????? ? (5.4) ? (5.5)
l? = nm =
ln
.
k
(5.7)
???????? l? ?????????? ?? ????? ???????????? ????? ???????? ???????? ?????? ?????? ?????????????? ?????? ? ?????? ?? ?? ????,
??? ? ????? ???????? ???? [5]. ???????? ?????? ??? ?????????????
????????????? ?????????????? ?????? ? ?????????????? ?????????????????? ??? ?????? ??????????????? ???????.
? ????. 5.1 ????????? ?????????????????? ???????? ?? ??????? ??????????????? ??????? ??? ??????????? ?? ???? ?????????????? ??????????????????, ?????????? ?????? ???? ??????? ? A(X) = 1000? ???
???? ??????????? ?????????? ???????? ????? ???????? B(X) ?? ?????? ????? ???????? ???????????, ??????? ??????????? ? ????. 5.1.
??????? 5.1
? ??? ?????
??????
R
1
2.5, ? 1/2
2
2.5, ? 1/2
3
2.7, ? 1/3
4
2.7, ? 2/3
???????????
?????????? ?
???????
1
1+X2
1+X+X2
1+X2
1+X+X2
1+X+X2
1+X2
???????? ?????????????????? B(X)
L
l?
dmin
1 1 0 0 0 1 0 0 0 ?
3 6
3
1 1 1 0 1 1 0 0 0 ?
3 6
5
1 1 1 1 1 0 1 1 1 0 0 0 ...
3 9
8
1
1
1
1
1
0
0 2
6
5
? ????. 5.1 ??????? ??????????? ?????????? ??? ???? ???? ?????????? ??????? (???. 2.5 ? 2.7, ?) ? ??????????? ??????? ??? ??????
(???. 2.7, ?), ?????????? ???????? ?????? ????? l, ?????? ??? l? ?
???????????? ?????????? ?????????? dmin (??. ????? ?. 10). ?????????
28
???????? ?????????????????? B(X) ??? ?????? ?? ???? ??????? ?????????????? ?????????????????? A(X) = 10000?, ??????? ????????? ??????????????? ?????????? l? ? dmin. ??? ?????? (???. 2.7, ?), ??????????????? ???????? R = 2/3, ?????????????????? A(X) ???????? ?? ??????? ????, ? ?? ?????? ???? ? 00000?
7. ?????????? ??????????? ???? ?????????? ?????????????, ?? ??
???? ???????????? ???? ???????????? ???????? ????????? ? k ? n, ???????????? ???????? ???? R = k/n. ???, ? [18] ??? ???????????? (n, k), ?
[21] ? (k, n), ?? ? ??????????? ?????????? ? ?????????? ???? ??????
?????? ????????, ???????????? ??????? ????? ???????? ???????????
(?????? ????) ? l [6, 11, 15, 27]. ????? ?????????????? ???? ??????? ?
??????????? ??? ????? ???????????
(n, k, l),
(5.8)
??? ????????? ?? ??????????? ???? ????? ?? ?????????? ???????? ????
R = k/n ? ????? ???????? ? ?????????? ???????? ??????, ?????? ???
???????? ????? ??????????? ????? ? R = 1/n ?????????? ???? ????? ?
(n, k, m).
8. ??? w ???????? ??????? ??????????????????? ???????????? ?????? ????????, ???????? ? ??? ?????????????????? ??? ??????? ?????.
????????, w = 4 ??? ??????? ?????????? 101011, ? w = 2 ? ??? ?????????? 1001.
9. ??????? ?????????? d ?????????? ??????? ???????? ????? i-? ? j-?
???????? ???????????? ??? ??????? ?? ?????????? ?????. ??? ????? ???? ???????? ??????? ?????????? ??????? ?????????? ????? ????? ????????????? ? ??? ????????. ? ????? ???? ??????? ??????????
????? ???? ?????????? ??? ????????? ????????? ???????? ?? ??????
2 ??????????? ???????? ??????? ?????????? ?
d ij =
L
? kik ? k jk ,
k =1
(5.9)
??? kik ? kjk ? k-? ??????? ??????? ?????????? i ? j; L ? ????? ???????
??????????.
??????? ? ?????? ??????????? ??????? ???????? ?????????? ????
?. ???????, ??????? ?????????? d ???????? ???????????.
10. ??????????? ??????? ?????????? dmin ? ??? ?????????? ?????????? ???????? ??? ?????? ??????? ?????????? ?????????? ?????. ??29
?????? ??? ????????? ???? ??????? ??????????, ?????????? ??????????? ?? ???
(5.10)
dmin = mindij.
?????? ??? ??????????? ??????????? ??? ??????? ?????, ???????
?????????? ?????. ?????????? ???? ???????? ???????????? ? ??????????????? ??????? ???????????? ????????????, ????????????? ??????? ????????? ????????? ??????? ???????????????????, ????? ???????? ??????? ??????????? ??????????. ????? ???????? ? ????????
??? ????????? ????? ???????? L ?????????? ?? ???????? ??????? ?????
????? ? ???????????? ??????????.
??? ????? ????????, ??????? ??????? ?????? ??????? ? ?????? ???
????????? ??????????? ??????? ??????????????????, ?????????? ??????? ???? ?????????????. ???? ???????? ???? ??????????? ? ??????????? ??? ????? ???????? ????? ???????????? ??????, ?? ? ?????
?????? ?????????? ?????? ???? ????????????? ?????? ???????? ? ????????? ?????????????, ?????? ? ????? ?????? ?????????? ?????????.
?????? ???? ????????????? ?????? ???? ?? ?????? ?????? ?????
???????? ??????????? l? (5.7) ? ???????? ? ????????? ??? ?? ?????????.
? ???????????? ? ????????? ?????? L ?????????????? ? ????????
?????????, ??????????? ?????????? ???????? ??? ????? ??? ???????
???? ?????????? L-? ??????????? ????????? ??????????? ??????????? ???? ? ???????????? dL. ???? L ????? l?, ?? ??? ?????????? ??????
??????????? ????????? ??????????? ? ????? ?????????? ???, ??? ? ?
??????? ?????
(5.11)
dl? = dmin.
???????????? ???????? ??????????? ???????????? ?????????? ?????????? dL* ????? ????????, ????????? ????? L ?????????????? ? ???????? ???????? ? ?????????????
d ? = max d L = d L* ,
(5.12)
d l? ? d l? +1 ? d l? +2 ? ... ? d ? .
(5.13)
L
?????? ????????, ???
???????? dL* ??????????? ???????? ??? ?????? ???????? ???????
?????????? ?????, ????????? ??? ???????? ????????? ??????, ? ?????????? ???????? ???? ?????????? ??? ?????? ????????? ???? [18, 20].
30
?????? ??????????????? ????, ????????? ???????????? ??? ?????????????? ????????, ???????? ?????? ????????? ?????????? ????, ?. ?.
???????????? ?????????? ??????? ???????????????????, ??????? ?????? ???????? ?????????? ?????????? [15, 23].
??????????? ????????? ?????????? dL ??????????? ???? ????? ?????????? ? ?????????????? ????????? ????????? ??? ?????????? ????????? ??? ???????????????? ??????.
????????? ?????????? ??? ???????? ???????? ?????, ?? ????? ????????? ????? ?? ?????????? ????????? ???? ??????????? ????? ???? ?
??????? ????? (??????? ????), ?. ?. ????, ?????????????????? ???????
???????? ???????? ??????? ????????? ?? ?????. ?????????????, ??????????? ????????? ?????????? ??????????? ???? ????? ????? ???????????? ????? ??????, ?. ?. ???????????? ???? ?????, ??????? ??????????
? ????????? ? ??????? ?????. ?????????? ????????? ???? ????? ???????????? ??? ??????????? ???????????? ?????????? ??????????, ????
??? ?????? ?? ????? ???????? ??? ??????????????? ??????? ????????
?? ?????? ??????, ? ????? ?????????? ??? ?????, ???????????? ? ??????????? ? ??????? ?????. ?? ???. 5.1 ???????? ???????? ??????????
????????? c ??????? ????? ??? ?????? ??????????? ???? (???. 2.5, ?),
??????????? ?? ???? ?????????? ????????? (???. 4.2).
a
0
0
00
0
0
0
2
2
b
01
c
10
2
1
11
0
1
1
1
1
2
2
0
1
1
1
1
1
1
0
2
2
0
1
d
2
2
1
1
3
1
4
5
???. 5.1. ?????????? ????????? ? ??????? ?????
??? ?????? (???. 2.5, ?)
?? ??? ????? ??????, ??? ?? ???? ????????? ?????, ????????????
? ??????????? ? ?????????????? ???????, ????? ????, ???????
??? 5, ????????? ?? ???????? ???? ?? 3 ????? [ab(11)?bc(10)?ca(11)],
31
??? ????, ????????? ?? ???????? ???? ?? 4 [ab(11)?bd(01)?dc(01)?ca(11)]
? 5 [ab(11)?bc(10)?cb(00)?bc(10)?ca(11)] ?????? ? ??????? ??? w = 6
? ?. ?.
????? ???????, ??????????? ??? ?????????? ???? ??? ??????? ??????????? ???? ????? 5, ?????????????, ??????????? ????????? ?????????? ????? ???? dmin = 5. ????????, ???? ??? ????? ????????? (??. ?????
?. 11) ????? ??? ??????, ???????????? ? ?????? ?????, ??? ??? ???
??? ?????? ????? ???????? ? ????, ??? ??????????? ?????????????????? ??????? ???????? ????? ????? ?????????? ?????????? ?? ?????????? ??????????????????, ?????? ????, ? ?? ???? ?????? ??????????????????? ??? ?????????? ????? ?? ??????? ???? ?? ????? ????. ?????????????, ??? ????????????? ?? ???????? ?????????? ?????????? ????? ??? ?????? ???? ????? ????? ??????????.
???????? ???????????? ?????????????? ??????????? ???????????
???? ??? ????, ??? ?????? ??? ??????????? ????????? ??????????.
??????? ????????? ?????? ??????????? ????, ?. ?. ??? ???????????
??????????, ????????? ??????? ????? ???????, ????? ??????????????? ??????????? ????????? ?????????? ????. ??? ??? ?????? ??????
???????? ???????????? ????????? ?????????????? ??????????? ??????????? ???? ??? ??? ????????????? ?? ????????? ?????????????, ?
?????????, ??? ????????????? ?? ????????? ??????? (??. ????. 8.3).
?????? ? ??????? ???????????? ?????????? ?????????? ??????????? ???? ?? ?????????? ?????????, ????? ???????? dmin ?????????? ??
?????????????????? ???????? ???????? B(X) ? ?? ?????? ????? ???????? ??????????? l? (5.7).
? ????. 5.1 ?? ????????? ?????????? B(X) ?? ????????? l? ? ????????? ??????? ????????? ???????? dmin ??????????????? ?????, ??????? ????? ???? w ??????????????????? B(X):
d min = Wl? ,
(5.14)
??? Wl? ? ??? ??????? ?????????????????? ?? ?????? ????? ????????
??????????? l?.
??????? ???????? ?? ??, ??? ??? ?????? ?? ???. 2.5, ? (?????? ??????
????. 5.1) ???????? ?????????????????? B(x) ?? ????????? ?????????
????????? ?? ?????????? ????????? ???? ??? ??????????? ?? ???? ??????
?????????????????? A(X) = 1000? ??? ?????????? ????????? (???. 4.2),
??? ??? ???? ?? ??????? [ab(11)?bc(10)?ca(11)] ?????????? ????????????? B(X) = 111011000?.
32
????? ???????, ??????????? ????????? ?????????? dmin ??? ????????? ????????? ???????? ?????????? ????? ????? ????? ?? (5.14), ????????? ????????? ???????? ?????????????????? B(X) ?? ????? l?
(????.5.1.), ??? ? ???????? ??? ?????????? ???????????? ??????.
11. ?????????????? ??????????? ???? ???????????? ?????????? (???????????) ???????????? g? ??????, ??? ??????? ???????? ????????????? ????? ?????? ? ??????? ???????????, ???????????? ????????
?????. ????????, ??? ??? ?????? ????????? g?, ??? ??????????? ???????? ???. ??????? ????????? ??????? ??????????? ????? ?????????
???????????? ???????? ?????????? ? ?????????? ??????. ????????,
?????????? ??????? ??????? ?????????????????? ??????????????? ??
???????? ??????? ? ??? ?? ??????????????, ?? ??????? ??? ??????
????? ??????, ?. ?. ? ???, ?? ??????? ??? ?????????? ??????? ??????
????????. ??????? ???????, ??? ??? ??? ??????? ????? ???????????
??? ???????
(5.15)
dmin ? 2g? + 1,
?????? ???????, ???
? d ? 1?
g ? ? ? min ? ,
? 2 ?
(5.16)
??? ?? x ?? ???????? ????? ????? ????? ?.
??? ?????????? ??????????? ????????? ???????????? ?????? ???????????? ??????????? ?????????? ? ?????? ???????????? ?????????? ?????????? dL ??? ????????? ??????? ??????????????????? ? ?????? L. ???? ? ?????????????????? ????????? ?? ????? g? ??????, ?????? g? ????????????? ???????????
(5.17)
2g? + 1 ? dL,
?? ?????? ????????????.
? ?????????, ??? ????? L ??????? ??????????????????, ?????? ?????? ????? ???????? ??????????? l?, ? ???????????? ? (5.11),
(5.18)
2g? + 1 ? dmin,
??? ????????? ? (5.15) ? (5.16) ??? ??????? ?????, ??? ???, ??????????
????? ???????? ???? ???????????? ?????? ????? ???????? ???????????
??? ?????????? ?????.
12. ???????? ???? ?????????? ??????????? ????? ?????????? ?????????????, ????????? ? ???????????? ??????, ??????????? ? ????33
?? ?????. ???????? ???? ??????? ?? ??????? ????? ???????? ??????????? l (5.5) ? ?? ???? ?????????? ?????????. ? [23] ????????, ??? ??????????? ??????????? ?????? ??? ????????????? ? ????? ???? ???????
?? ????????? ??????? ??????????? dL. ???, ??? ?????????????? ?????
?????? (???. 2.5, ?), ????????????? ??? (2, 1, 3) ? ??????????? ?????????? G1 ? G2 (????. 5.1 ), ???????? dmin = 5. ??? ???? (2, 1, 5) ? ??????????? ??????????
G1(X) = 1 + X3 + X4,
(5.19)
G2(X) = 1 + X + X3 + X4,
??????? ?????????? ??? ??????????? ???????? ??????? ? ??????? ??????? ????? GSM, dmin = 7. ? ??? ????? ?????? ???? (2, 1, 7) ? ??????????? ??????????
G1(X) = 1 + X2 + X3+ X5 + X6,
G2(X) = 1 + X + X2+ X3 + X6,
(5.20)
??????????? ? ???????? ??????????? ?????, dmin = 10.
?????????????, ???? ? ??????? ??????? ???????????? l ????????
????? ???????.
13. ?????????????? ??????? ???? ? ?????????? ??????? ?? ?????????????????? ??? ?????????? ??????????????? ???????????. ???
???????, ? ???????? ???????????? ?????????? ???????? ? ??????????????? ??????? ?????????? ??-2, ???????????? ???????????????
??????? ? ????????? ????? 0° ??? ???????? ??????? ?1? ? 180° ???
???????? ?0? (??? ????????).
??? ????????? ????????? ???????? ??????????? ?????????? ??????
?????? ??????? p1 ? ?????????????? ?????????????????? ???? ?????????? ?? ?????? ???????????? ????????? ????????? ??????????? ?????????? ?????????? ????????? ??????/???.
??? ???????? ?????????? ? ?????????????? ???????????? ???
?????? k ????????????? ???????? ?? ???????? ????? ????????? ???????? n ???????? ? ??????????? ??????????? ?? ?? ?? ????? ??? ??? ??
?????? ????????.
??? ???? ???????? ????????? ???????????? ???????? ??? ????????
(??? ???????? R = 1/3 ? ? ??? ????), ??? ????????? ?????????? ??????
?????? ? n/k ???. ???????? ???????? ???????? ??????????? p1 ????? ?????????????? ??? ??? ?????? ????????? ??????/???. ??????? ????????? ??????/??? ??? ?????????? ??????????? ? ??? ???? ??? ?? ????34
????????? ???????? ?????????? ?????????????? ??????? ????, ?????????? ? ?????????.
??????? ??????????????? ?????? ?????????????? ????????????? ???
????? ???????????? ????????? ????? ???????????? ?? ???????????????? ??????????????? ???????? ?? ??????????? (????)
(5.21)
? = 10lgRdmin (??),
??? R = k/n ? ????????????? ???????? ????; dmin ? ??????????? ???????
??????????.
???????? ???? ????????????? ??? ??? ??????????? p1 ? 0 ? ???????? ??????? ???????? ????????? ??? ??? p1 ? 0 [23].
? ????. 5.2 ????????? ???????? ?????????????? ???????? ?????????? ????? ?? ????????? R = 1/2, ? ????????? ???????? ????.
???? ?????? ???????????? ???????????? ? ???????????? ?????
?????? ? ??????? ???????? ?????? ???? (5.5) ? ???????????? ????????
?????????? (5.11).
??????? 5.2
?
1
2
3
4
5
6
??????????? ??????????
5,7
15,17
23,35
53,75
133,171
247,371
R
l
dmin
????, ??
1/2
3
4
5
6
7
8
5
6
7
8
10
10
3,98
4,77
5,44
6,02
6,99
6,99
??????? ?? ??????????? ????? ???? ??????????? ???????? ??????????? ????????, ????????, ????? ?????????? ???????? ???????????? ? ???????? ?????, ?????????? ???????? ?????? ??? ?????????? ???????? ????????.
??? ?????????? ? [15], ??? ????????? ????????????? ???????? ??
??????????? ???????? ???????? ?????????? ???? ? ????? ?????? ???????? ??????????? ? ? ?????????????? ?? ????????? ???????. ? ?????????, ?????? ????????? ??? ? R = 1/2, l = 6, ??????? ????? ??? 5??
??? p1 = 10?5, ??????????? ?? ?????? ???????? ??? ????????? ?????????
???????? ??????.
14. ????????? ??????? ?????????? ????? ?????????? ???????????
???????????? ?????????? ?????? ?? ??????? ???????? ? ???????? ?? ??????? ?????? ??????? ?????.
35
????????? ??????????? ?????? ???????????? ?????? ??? ??????????
?????????, ???????? ???????? ??????? ? ???????? ??????, ?????????
?? ?????? 2 ? ????? ?????????? ? ????????? ???????. ? ???????????
??????? ????? ???????? ?????? ????? ??????? ?????????? ???????? ??????, ? ?????? ???????? ??????????? ?????????????? ? ????????? ???????? ????????. ??????? ????? ???????, ??? ????????? ???????????
?????? ??????? ??????? ?? ????? ???????? m ??? ?? ????? ????????
??????????? l. ???????????? ?????????? ??????????, ?????????? ?? ?????????? ???????? ??? ????? ?????????? ?????????, ?? ????????????
?????.
????????? ????????? ???????????? ??????? ?????????????. ? ????????? ????? ???????????? ??? ???????? ?????? ????????????? ?????????? ?????: ?????????, ??????????? ????????????? ?????? ????????????? ??????? ?????, ???????????????? ? ????????????? ?? ????????? ???????.
???????? ???????? ? ?????????? ???????? ????????? ????????????? ????????????? ??? ???????, ??? ? ?????????? ?????. ?????????
?????????? ????????? ?????? ??????????? ??????????????? ??????
????? ???????? ??????????? l? (5.7). ???????? ?????????? ?????? ???
??????????? ?????? ????????? ????????? (g? = 1, 2). ?????? ?????????? ?????????? ????????? ???????????? ?????? ???????? ? ????????????? ?????????? ???????? ?????????? ?????????, ??????? ?? ????????????? ???????????? ???????? ???.
?????????? ????????? ????? ???????? ???????, ????? ?????????? (?????????) ??????? ?????????? ??????????????? ? ?????? ?????
???????? ???????????. ??? ????????????? ????????? ??????? ?????????? ??? ?? ??????? ????? ??? ????? ??????????? ????? ????????,
?? ???? ??????? ??? ? 0,4 ?0,5 ?? [23]. ??????? ??????????? ???????????? ???????? ??????????? ??? ????? ? ??? l ? 7?8. ?????????
?????????????? ????? ????????? ???????? ??? ????????????????? ???????? ?????????????, ? ???????? ?????? ? ?? ???? ???????? ? ????????????????? ???????.
15. ?????????? ??????????? ? ???????????? ???????????? ??????????? ????????????? ???????????? ?????????????? ??????????????????. ????????, ??? ?? ?????? ????? ?????? ? ?????????? ?????? ???????? ? ???????? ?????????? ??????. ????????, ???????? ????? ????????? ?????? ?? ?????????? ? ?????? ? ???? ?? ????????? ????????.
36
? ???????????? ??????? ?????????? ??????????? ???????????? ????????????? ??????? ?????????? ????? ????????????????????, ???????????? ???????.
????? ????????? ??????? ?????????? ???, ????? ????? ???????????? ????, ??????????? ?????????? ??? ???????, ???????? ?????
????? ??????????? ? ???????? ????????. ?????????? ????? ?????? ??
????????? ????????????? ???, ??? ??????????? ??? l ??? ????????
dmin, ??? ??????????? ??????????? ???? ???????. ????? ????? ????????????, ??? ???????, ????????? ?? ???. ? ?????????? ??????? ??????? ??????? ????? ?????????? ????? ? ?????? ?????????? ??????????? ??? ?????? ? ?????????? ???? ????????.
16. ???????????? ? ????????????? ??????? ????????????? ??????????? ???? ? ???????????? ?????? ?????????????? ????????, ??????????? ?? ????????????? ?????? ???????????????? ????? ???????????
?????????????????? ????????. ????, ??? ???? ????????? ????? ???????? ? ??????? ??????? ??? ????? ?????? ????????????? ??????? ??????????? ???? ????????? ?????????????? ???????????? ?????????????? ???????, ?? ????? ??? ?? ????? ????????????? ????????. ? ????
?????? ???????????, ? ?????????, ???????? ??????????? ???????? ????????.
?????????? ????? ??? ?????????? ? ????????????? ?????????? ?????, ???????? ? ???????? ?????? ?????????????? ???? ?????.
37
6. ????????????? ?????????? ?????
6.1. ??????????????? ? ????????????????? ????
???? ? ?????????????????? ??????????? ??????? ??????? ???????? ????? ???????? r = n ? k ?????????? ???????? ?? k ??????????????, ?? ??? ???????? ???????????????. ? ??????????????? ?????? ?? k
??????? ????? ?????????????? ??????????????????. ?? ????????? n?k
??????? ? ?????????????????? ??????????? ????????, ???????????
??? ???????? ?????????? ??????????????.
?????? k ??????? ???????????????? ?????? ????????? ??????????????? ? ??????? ????????? ?????????. ???? ????? ???????? ????????????????, ?? ???. 2.5 ????????: ?) ? ???????????????, ?) ? ????????????????? ?????? ??? ???????? ???? R = 1/2, ?. ?. ??? k = 1. ??? ???????
? k = 1 ??? ???????????? ??????????????? ????? ???? ?? ??????????? ??????????? ???? G1(X) = 1, ???? G2(X) = 1, ????? ?????????????? ?????????????????? ???? ?????? ???????? ??????????????????.
??????????????? ???? ????????? ???????? ?? ???????? ???????
?????? ?????????????? ????????, ?? ????????? ????????????? ???
?????-???? ???? ????????? ??????????? ????????. ? ??????? ????????????????? ??????????????????? ?????????? ??????????????? ??
??????????, ??? ?????? ????????? ???, ????? ??? ?????????? ??????
?? ????? ???? ????? ???????????? ? ????????.
???????????? ????????????????? ?????????? ????? ???????? ??, ???
?? ??????????? ????????? ?????????? ????, ??? ? ???????????????
??????? 6.1 ??? ?????? ?????? ????????.
??? ??????????? ???, ??? ?????????????????????? ???????????????
m
?????????? ?????????? ??? ?????? ? dmin
??? ? dmin
?? ???????? ?? ??????????????2
3
3
?? ??????????????????, ????????
3
5
4
???? ?? ?????????? ?? ?????? 2,
4
6
4
??? ? ???????? ? ??????????
5
38
7
5
???????????? ?????????? ?????????? ????.
? ???????? ??????? (????. 6.1) ????????? ???????????? ????????
???????????? ?????????? ?????????? ??? ??????????????? ? ????????????????? ?????????? ????? ?? ????????? R = 1/2 ??? ????????? ????? m ??????????? ????????.
?????? ????????????????? ?????????? ????, ? ??????? ?? ???????????????, ????? ???? ?????????????????.
6.2. ???????????????? ?????????? ????
???????????????? ?????????? ????? ?????????? ???, ??? ????????
???????? ????? ??????, ????????????? ? ?????? ?????, ????? ???????? ? ???????????? ????? ?????? ? ?????????????? ????????.
?????????? ????? ?????????????????? ??????????? ???? (???. 6.1, ?),
????????? ????????? ???????? ????????? ?? ???. 6.1, ?, ??? ?????? ????????? ????????? ?????? ?????????? ??????? a, b, c, d. ???????, ???
?? ?????? ????? ????????? ?????????????????? ?????????????? ????????, ??????????????? ????? ?????????????????? ????? ?????????
??????: abddd... dca.
?)
?)
00
????
00
a
11
01
10
10
b
?)
01
10
01
c
11
d
11
?????
00
???. 6.1. ????? ?????????????????? ????????????????? ???? (?) ?
??? ????????? ????????? (?)
??????? ?? ???????? ????? ?? ????????? ????????? ????. ????? ??
????????? ?????? (???. 6.1, ?) ???????, ??? ?????????????????? ??????? ????????, ???????????? ?? ?????? ?????, ????? ????? ??? ?????? 6,
??? ??????????? ?? ????, ??????? ??? ????? ????????? ? ????????? d.
???? ? ?????? ????? ?????? ?? ????? ?????? ???????????? ???????
39
???????? ?????????? ? ???? ??????? ??? ????, ?? ???????? ?????????????????? ???????? ????? ????? ??????? ?????????? ???????? ??
???????? ????, ??? ?? ????????? ????. ??? ???????? ? ????, ??? ???
????????????? ?? ???????? ?????????? ????????, ?. ?. ?? ?????????
?????????????, ??????? ???? ????? ?????? ? ???????? ?????????. ?
?????????? ??? ????????????? ????? ??????? ??????????? ??????? ????? ??????. ????? ???????, ?????, ?????????? ?? ???. 6.1, ?, ????????? ???????????????? ?????????? ???.
????????, ????? ????? ????????? ???????????????? ?????????? ???
?????, ????? ?? ????????? ????????? ????? ?????? ????? ????????? ????
???????? ????, ??????????????? ????????? ?????????? ?????????????? ????????. ??? ???????? ?????????? ????? ?? ????????? R = 1/n,
??? ??????? ?????? ???????? ????? ?????? ????? ??????, ?????? ?????
????? ? ??????? ?????, ??????????????? ????????? ?? ???? ??????, ?. ?.
????????? ?????????????? ????????. ?????????????, ??? ????? ?????? ????? ????????? ???????????????? ?????????? ???. ? ????? ?????? ??????????? ? ??????????? ??????? ???????????????? ???????????
???? ??????? ? ???, ????? ??? ??????????? ?????????? ????? ?????
????????.
????????, ??? ????????????????? ?????? (???. 6.1, ?) ? R = 1/2, l = 3
??????????? ??????????
G1(X) = 1 +X,
G2(X) = 1 +X2.
(6.1)
????????, ??? ??? ???? ?????? ???????? ????? ?????? ????? ?????? (?? 2) ? ??? ?????????? ???? ????? ????? ????????? 1+X. ???????, ??? ??????? ??????? ?????????????????? ???????? ? ???????? ?????????????????? 000000?, ? ?? ????? ??? ??????? ??????????????????,
????????? ??????? ?? ??????, ???????? ? ???????? ?????????????????? 11010000? ????? ???????, ??? ?????? ? ?????? ???????? ???????? ? ???????????? ????? ?????? ? ?????????????? ????????, ???
???????? ???????? ??????????? [15].
???????????? ??????????????? ?????????? ????? ???????? ??, ???
??? ?? ????? ???? ?????????????????. ?????????????, ??? ???????????????? ??????????? ???? ?????? ????????? ????, ???????????????
????????? ?????????? ?????????????? ????????, ??????? ?? ?????
????? ??????? ???, ??? ??? ?????????? ?????????????? ??????? ??????????? ???????????? ?? ?????? ? ?????????? ????.
40
????? ???????, ??? ?????? ????????? ?????? ??????????? ???? ??????????? ?????????? ???? (?. ?. ????? ?? ??????????? ???????? ??
????????? ?? ?????? 2) ????????? ??????? ????? ???????, ????? ???????? ?????????????????? ??? ? ???????????? ??????????? ????????? ???????????. ????? ???? ?????? ???? ??????????????????, ? ??????????? ?? ?????????? ?? ?????? ????? ????? ?????????. ???
?????? ???????? ????? ??????? ?????? ???????????? ???.
6.3. ?????????? ?????????? ????
? ????????? ????? ??? ???????? ???????? ?????? ? ???????????
?????? ????? ????????? ??????? ????????? ? ??????????? ?????. ???
??????????????? ??????? ????????? (??-2) ?????? ?1? ?????????? ?
????????? ????? 0, ??? ???????? ??????? ?1? ? ? ????? ?. ???????
???????, ??????????? ??? ???????????? ?????? ? ?????????????, ??????????, ??? ???????, ?? ???????????? ???????. ??? ???? ? ???????
?????????? ????? ???????????? ????????? ??????????????? ???, ???
???????? ? ??? ?????????? ????????? ???????, ????? ??? ??????? ?1?
??????????? ??? ?0?, ? ??? ??????? ?0? ? ??? ?1?, ?. ?. ????????? ?????? ????????. ???????? ?? ???????? ? ??????? ? ????????????????
??????? ?????????? ??????????? ??? ??? ?????????? ????????.
??????? ??? ?????? ????? ?. ?. ???????? ? 1954 ?., ????????? ???????????? ? ???????? ???????? ?????????? ?????????? ??????? ???
??????????? ???????????. ????? ?????? ???? ????? ? ?????????????
??????? ??????????? (???) [28]. ? ?????????? ??? ???????? ?????????????????? ? ????????????? ??????? ????????? (???) ? ? ?????????????? ????????? (???) [29].
??????????? ????????, ??????????? ????????????? ?????, ???????????? ??????????? ?????? ? ?????? ? ??????? ????????????????,
???????? ??????? ????????????? ??????????? (???. 6.2). ??? ???? ????? ????????????????? ???? ?????? ???? ?????????? ??? ???????????????, ?. ?. ?????? ???????? ????????? ?????????????? (????????????)
?? ????????? ? ???????? ?????????????? ????. ??? ????????, ??? ????
???????? ??????? ???????? ?????????? ?? ???????????????, ?? ??????????????? ???????? ?????????????????? ????? ?????????????.
? ???? ?????? ? ?????? ? ??-2 ???????? ????????? ????????, ????????????? ????????? ???? ??????? ??????? ?? ?, ?????? ????????? ?
???????? ???? ?????????????? ???????? ?? ?????? ????????.
41
?
??????????
?????
A(X)
A( X )
??????????
??????? ?
A ?( X )
?????
A'(X)
?????????
?????
???????????
???????
???. 6.2. ?????? ???????? ?? ?????? ? ????????????????
? ??????? ????????????? ????????????
??????? ???????????? ?????????? ????? ? R = 1/2, ???????????? ??
????????? ???????, ??? ???????? ????? ????? ???
?
? GS(i) = 1,
(6.2)
S =0
??? G(X) ? ??????????? ???????; ? ? ???????????? ??????? G(X); i = 1;
2 ? ????? ???????? G(X); ? ? ???? ???????????? ?? ?????? 2.
????????? (6.2) ????????, ??? ????? ??????, ? ?????? ??????????? ?????????? (????????) ????????? ??????????? ??????????? ? ???????? ????, ?????? ???? ????????.
??? ???? ?????????????????? ?? ?????? ??????, ????????? ??????
?? ???????? 1, ????????? ?????????????????? ?? ?????? ??????, ?????
??????? ????????? ?? ???????? 1. ? ???? ?????? ????????? ?????????? ???? ???????? ?? ?????? ???????? ???????? ???? ? ?????????
?????????? ???????? ?? ?????? ????????.
??? ????????????? ????? ?????? ???? ?????????? ??????? ??????????? ? ????????????? ??????? ????????? ?????????? (?????????????)
???????????????????????????, ??? ???????? ?? ???. 6.2. ??? ????????
? ?????????? ?????????? ?????????????? ??????. ?????????? ?????
?????????? ?????????????????? ?????? A(X) ? ?????????????????? A'(X),
? ??????? ?????????? ???????, ??????????????? ??????? 1 ? A(X), ???????? ?? ????????? ? ??????????, ? ?????????? ???????, ??????????????? ??????? 0 ? A(X), ???????? ??????????.
???? ? ?????? ?? ???????? ?????????? ???????????? ??????????????
?????, ?? ??????????????? ?????????????????? A ?( X ) ????????? ? A'(X)
?
(?? ??????????? ?????? ?????????????) ? A ( X ) ?????????, ???????, ?
A(X). ???? ? ?????? ???????? ?????????? ???????????? ??????, ?? ???
????????????? ??????????? ???? ?????????????, ??? ??????????????
????? A( X ) ????? ????????? ? A'(X). ?????? ????? ??????????? ??????42
?
????? ???????? ??????, ?????????????????? A( X ) ????? ????????? ?
A(X).
????? ???????, ??? ????????????? ??????????? ???? ??????????
???????? ???????????? ????????????? ? ?????????? ????????, ??????? ??? ?????? ? ???????? ?????? (???. 6.2).
???????, ??? ? ?????????? ???????? ???? ???????? ?????? ????????
? ????? ?? ???? ?????? (????????? ??????) ?? ?????? ???????????
???????? (??? ? ? ?????? ???). ??????????????? ?????? ??????????
??? ???? ????? 0,1?0,2 ?? [15].
? ????. 6.2 ???????? ????????, ??? ??? ??????????? ?? ??????????
?
??????? ?????????????????? ???????? A ?( X ) , ??? ? ??????????, ??? ? ?
?
??????????, ???????? ?????????????????? A( X ) ????? ?????????.
?
?????? ??????? ? ??????????????????? A ?( X ) ???????? ??????,
??????? ???????? ? ???????? ?????????????????? ? ????? ?? ???? ??????.
??????? 6.2
???????
?
10110110010
10110110010
1101101011
???????
?
A?( X )
?
?
01001001101
01001001101
1101101011
A( X )
? ????. 6.3 ????????? ???????? ?????????????? ?????????? ?????????? ????? ??? ??????? ? ?? ? ?????? ??? ? = 2 ? 4 ??? ????????
???? R = 1/2. ??????? ???????? ??????? ????? ???????? ??????????? l
(5.5), ???????? ???????????? ???????? ?????????? dmin (5.10) ? ???????????????? ??? ? (5.21). ??????????? ?????????? G(X) ????? ???????????? ? ???????????? ????? ??????.
??????? 6.3
?
1
2
3
4
5
6
7
M
R
2
1/2
4
1/2
G1(X), G2(X)
13,15
25,37
61,73
133,171
23,32
212,113
212,131
l
dmin
4567
66810
588
488
????, ??
4,77
4,77
6,02
6,99
3,01
6,02
6,02
43
?? ???????? ???? ?????????? ???????? ???? ?? ???????? ? ????
??????? ??????????? ?????. ???????? ?????????? ???? ????????????
? ? ??????? ? ???????????????? ?? [23].
6.4. ??????????????? ?????????? ????
???????????? ?????????? ?????????? ????? ?? ?????????? R = k/n
????????? ???????????, ???????? ? ?????? ??????? ????????? ????????
?????? (????????? ??????? ? ???????) [15]. ????????? ????????? ????????? ????? ???? ???????? ??? ?????? ???? ? R = 1/n ? ????????????? ??? ???????? ????????? ???????? ? ???????? ?????????????????? ??? ????????? ???? ? R = k/n. ? ?????????, ??????? ?????????????????? ?????????? ???? ? R = 2/3 ????? ???? ???????? ?? ??????????????????? ???? ? R = 1/2 ????? ?????????????? ???????????? (??????????)
????????. ?????????? ??? ????? ????? ??? ??????? ?? ?????? ???????? ??? ?????? ???? ?????????????? ????????, ?. ?. ??? ???????? ?????
????? R = 2/3. ????? ???? ?????????? ????????????????.
??????????
p
p4
u
q
q4
????????????
P
p4
p3
p1
p3
p2
p1
p2
q3
q1 Q
q3
q2
q1
p?4
p?4
p?3
p?1
p?3 p?2
p?1
p?2 q?3
q?1
? ????????
?????
0 q?3 0 q?1
???. 6.3. ??????????? ???????? ???????????????? ????
?? ???. 6.3 ??????? ??????? ??????????. ??? ??????????? ?? ????
?????? ??????????????? ??????? u ?? ??? ?????? ?????????? ???? ???????? p ? q. ? ???????????, ????????? ?? ??????? ??????????? ?????????, ???????????? ????? ?????????????? ??????????????????? p ? q ?
??????? ?????????????????? P ? Q, ??? ??????? ??????? q2 ? q4 ??
?????? ???????????. ??????? ?????????????? ???????? ?? ????? ?????? ????????????? ?????? ???????? ?? ??? ??????? p1p2p3p4 ? q1q2q3q4
? ????? ???????? ?? ??????? ??????????? p1p3p4 ? q1q3p2. ??? ????
???????? ???????????????? ???? 2/3. ?? ???????? ??????? ??????????
44
???????? ?????????????? ? ?????? ??????????? ???????? ? ?????? ???????? ???????????, ????????, ????.
????????????? ?????, ?????????? ??????????? ????????? ???? ??
????????? 1/2, ????? ??????????? ?????????, ????????????? ?? ??? ????????. ?????????? ???? ????????????? ?????????? ??????????? ???????? ??????????.
??????????????? ???? ????? ????? ?? ?? ??????????????, ??? ?
????????? ????????? ????, ??????? ??-?? ????? ???????? ? ???? ??????? ??? ????? ???????????????.
6.5. ?????????? ???? ? ?????????? ???????????
????????? ? ?????????????? ???????????? ??????
? ?????????? ??????? ??????????? ??????? ????? ????????? ?????????? ?????, ?????????????? ??????????? ?????? ????????? ????????????. ??????????? ????, ???????????? ????????? ??????, ???????????? ????????? ? ??????? ??????, ????? ??????, ????? ?????? ? ????????????? ???????????? ??????????? ?????? [8, 14]. ????????? ??? ?????????? ????????????? ?????????? ?????. ??? ???????,
? ????, ? ????????? ???????? ???????? ???????????? ?? ???????.
?????? ??????????? ????, ???????????? ??????????? ??????,
???? ??????? ???????? (1955 ?.) ??? ????????? ??????????????. ?????????? ????? ????? ( ??? ????????? ??????????????) ???? ??????????
????????, ??????? ? ?????? 1961 ?. ?????????? ?????? ????????????
????, ??????????????? ?????????? ??????????? ??????, ????? ?????? ????? ???????? ? ??????? ???????????????? ???? ? ???????? ?????????? ???????? ?????? ????? ????????? (???????? ??? ? l?).
?????? ????????? ????? ?????????? ?????, ???????????? ???????????? ??????, ????????? ????????????????? ???? ?????. ?? ?? ?????????? ????? ?????????? ????????????? [30]. ?????? ? ?? [13] ?????
????, ???????????? ????????? ??????, ? ??????? ???????????? ?????
??????????????? ???????? ?????? ?????????? ?????.
???????????????? ????????????? ????????? ?????????? [31]. ??????????? ???????? ??? ????????? ????. ????? ?????????????????
???????????? ??? ?????????? ???????? ????????????????? ?????????????, ?????????? ???????? ????- ????????? [24]. ???? ???????? ??
?????? ??????? ????? ????????? ????, ?? ????? ?????? ??????????? ?
???????? ?????????? ? ???????? ????????? ?????????????? ?????45
??? ????????????????? ?????????????. ???????? ?????????? ????????????????? ????????????? ? ???????????????? ? ???????? ???????.
????? ???????? ???????? ?????????? ????? ????? ?????? ? ???, ????? ???? (?????????? ??? ????????) ???????????? ?????. ????? ??
???? ?????? ??? ??? ??????? ? 1967 ?., ?? ??????? ??????? ? ??????
??????? ??????????? ?????? ??? ?????????? ????? ? ? ?? ???????
???????, ??? ?????????????? ??????????? ?????????? ?????, ??? ??????? ???????? ???????????, ????? ??????????????? ????????????? ???????? ????? ??? ?? ?????. ??? ????????? ???? ?????? ??????? ??????????? ???????? ????????????? ?????????? ?????, ???????, ??? ?????????, ????????? ??? ???????? ????????????? ?? ????????? ?????????????. ???? ???????? ???? ?????????? ?????????? ???????.
?????????? ????, ???????????? ????? ??????, ??? ?????????? ?
????. 1, ???? ?????????? ??????, ? ????? ??????????????. ? ????????????? ??????????? ?????????? ??? ???? ???????? ???????? ?????????????????? [6]. ? ?????????? ????, ???????????? ????? ??????,
????????? ????????, ? ????? ???????? ? ???? [13].
?? ?????????? ???? ???????????? ??????????? ? ????????? ??? ?????????? ??????????????? ?????????? ????? ?? ???? ?????? ??????.
????? ????????? ????????? ?? ?????????????, ? ??? ???? ????????
???????? ??????????-?????????-????? (???-????). ?????, ? 1966 ?.,
??????? ?????????? ??????????? ????, ??????? ????????? ????? ? ??????????, ??? ???-????.
??? ??????????? ????????? ?????? ? ????? ?????? ????????? ?????????? ??? ?????????? ????????? ????, ??????????? ????????? ?????????????, ????? ? ???????????? ??????? ? ?????????? ???? ????
[8, 14].
???? ?? ????????? ????? ?????????? ???? ???? ???? ???????? ????????????? ????????????, ?? ? ?????????? ??? ????? ??????????? ??????? ? ????????? ? ???????????????? ?????????????? ? ???????????
?????, ? ????? ? ????????? ? ????????? ?????????????? ? ???????????
???????? ???????? ??????, ???????? ??????? ?????????? ? ?????? ????????.
46
7. ???????????? ?????? ? ??????
????? ????????????????? ???? ??????? ?? ?????? ? ????????, ??????
????????????? ? ????????? ???????????? ? ??????? (???. 7.1).
????
?????
?????
?????????
?????
??????? ?????????????
?????????????
???????????
???????
??????? ?????????????
?????????????
???. 7.1. ??????????? ????? ?????? ? ??????
??????? ????????????? ????????? ????????????????????????, ??????????? ??? ?????? ?????? ? ??????. ?? ?????? ??????? ????????????? ??
???????? ??????? ?????????? ?? ?????????????? ???????????????????.
???????????????? ?????? ???????????? ? ???????? ????????? ?????. ?? ???. 7.2 ??????? ?????? ???????????? ?????? (???. 2.5, ?) ??
????????? 1/2 ? ???????? ???????????? ??-2 ? ??-4.
????
??????
u1
u2
1
?????
??????
?????
??-2
?????
??-4
(1)
v1
u3
0
(2 )
v1
(1)
u4
1
(2 )
(1)
u5
1
(2 )
(1)
0
(2 )
v2
v2
v3
v3
v4
v4
0
0
0
0
1
1
1
1
?
?
?
0
0
0
?
0
(1)
v5
2
v5( )
0
1
0
?
t
t
t
?
?/2
0
3?/2
3?/2
t
??
t
??
t
???. 7.2. ????????? ????????? ????????
47
??? ????????????? ??????? ????????? (00 ? 0, 10 ? ?/2, 11 ? ? ?
01 ? 3?/2) ?? ?????? ?????????? ????? ????????????? ??????, ??????
??????? ???????? ???? ????????????? ???? ???????? ?? ?????? ??????.
??? ????????????? ? ?????? ???????
???????
????? ???????????? ????S
z0
p(z/S1)
???? ?? Q ???????. ??? Q = 8 ??? ???7
111
?? ???????? ???????? ????????? ?? ??S1
6
110
???? ??? ? ? ??????? ???????-?????5
101
???? ??????????????? (???) ?????????4
100
?? ? ???????? ??????????? ???????0
3
011
???. ?? ???. 7.3 ??? ??-2 ????????
????????? ?????????? ????? S0 ? S1,
2
010
???????? ???????????? ??? ????????S0
1
001
??? ? ????? ?, ???????? ????????? ???000
0
?????????? ???????????? ??????? ? ??p(z/S0)
????? p(z/S0) ? p(z/S1), ? ????? ????????
???. 7.3. ????????? ??????????? ????????????? ????????????? ???????
???????? ???????? ????????
z0 . ????????????? ???????? ??????? z0
???? ??????? ???????.
??????? ??????????? ?? ???????? ???????????? ?????????? ???????? ????????????? (??), ? ??????? ?????? ??????????? ???? ? ?????????? ???????? ????????????? (??) (???. 7.2). ??? ?????? ???????
???????????? ?????? ? ?????? ?????????? ????????? ???????????????
????, ??????????? ??? ?????????????? ??????? ? ????????????.
????? ??????? ?????????? ????? ?????????? ??????. ???????? ???????? ????????? ???????? ?????????? ????????? ? ?????????, ?????????????? ?? ??????.
?????????? ? ??????? ????????????????? ???? ??????? ???? ?
????????????? ?????? ?????????? ????? ??? ????????? ???????? ?
???????? ???????? ???????.
48
8. ?????? ????????????? ?????????? ?????
???????? ?????? ?????????? ????? ??????????? ? ???? ???????????? ? ???????????? ? ????? ?????????? ???????? ????????????? ?????????? ?????: ?????? ?????????? ????????????? [30], ?????? ????????????????? ????????????? [24, 31] ? ?????? ????????????? ?? ????????? ????????????? (???????? ???????) [17].
????? ?????????? ????????????? ?????????? ????? ? ???????? ?????????? ?????? ????????????? ????????????? ???????? ????? [5]. ???????????? ????? ?????? ???????? ???????? ?????????, ?, ?????????????, ? ??????????? ??? ?????????. ????? ????????, ??????????? ???
????????????? ?????? ??????????????? ???????, ??? ????? ?????????
?? ??????????? ????????? ?????????? ????????.
????? ????????????????? ????????????? ???????? ??????? ?????????????? ?????????????, ??? ??????? ????? ????????, ??????????? ???
????????????? ?????? ???????, ???????? ????????? ?????????. ???
??????????? ?????????? ????????? ????????? ????? ????????????????? ????????????? ?? ????? ??????????????? ???????????? ? ??????
????????????? ?? ????????? ?????????????.
????? ????????????? ?? ????????? ????????????? ????????????
????? ??????????, ??? ????? ?????????? ?????????????, ?????? ????????? ?????????, ??????????? ??? ??? ??????????, ?????????? ??????????????? ? ?????? ????? ????.
8.1. ????? ?????????? ?????????????
??? ????????? ????????????? ?????????? ????? ??????????? ???????? (???????? ????? ????????? ????????), ????? ??? ???????? ??? ??????????????????, ?????????? ??????????? ????????? ?????????????? ?????????, ???????? ?? ????? ?????????? ????????, ??? ????? ?????????????
(???????????? ?????) ? ????????? ??? ??????????? ? ??????? ?????????
??????? ? ???????? ????????????? ???????. ???????? ??????????? ?????
?????? ????????????? ? ???????? ??????????. ?????? ?? ?? ?????????
????????? ????????????? ?????????????? ??????????? ??????????? ????.
49
????? ????, ?? ??? ?????????? ???? ????? ???? ???????????? ???? ???????. ????? ?????????? ??? ???????? ????????????? ????????? ???????,
?? ?????? ???????? ????????? ???????????????.
? ???????? ????? ?????????? ????????????? ?????????? ????? ?????????? ?????? ????????????? ????????????? ??????????? ???????
????? [5].
????? ????? ???????? ??? ??????????? ???? (R = 1/2) ????????????
?? ???. 8.1.
????
1
?????????????? ???????
????????????
???????
????
???????? ?????
????
2
?????????????
?????????? ???????
?????????? ?????
(???????????? ???????)
???????????
???. 8.1. ????? ????? ???????? ??? ??????????? ????
????????? ?????????????, ??? ???????, ??????????? ??? ??????????????? ?????. ??????? ???????? ?????? ??????, ? ??????? ?? ??????????? ?????????????? ???????? ? ?????????? ???????? ???????????
????? ??????????? ??????????????????. ? ???? ????? ?????????????
???????? ? ??????? ?????? 1 ? 2 ??????????????? ??????? ?????????????????? ???????? ?? 2 ?????? ? ?????????????? ? ???????????,
????????????? ????????? ??????? ????? ????????.
? ????????????? ???????? (????????? ?? ?????? 2) ?????????? ?????????????????? ????????? S, ??????? ????????? ?? ???? ???????????
????????. ? ?????????? ? ?????? ?????? ?????????????????? ?? ??????
????????????? ???????? ?????? ?????????, ? ?????????? ?????????????????? ??????? ?? ????? ?????. ????????? ??????? ?????? ????????????? ???????????? ???????????? ?????????? ???????????????????, ? ??????? ?? ???????????? ???????? ?????????? ????????? ???????. ????? ???????????? ??????????? ???????? ?????????? ?????
???????, ????? ?? ????????? ?????????? ?????????????????? ?????
???? ?????????? ?????????? ???????.
50
?????????? ????? ?????????? ?? ???????? ???????????? ??????????? ? ?????????????? ???????? ????? ?????????????? ????????. ????
??????? ?????????? ??????, ??????? ????? ???? ??????????, ?? ?????????? ????? ?????????? ?????? ? ???? ????? ????? ?????? ?????????
???????? ?? ???????? ????? ???????????? ?? ?????? 2 ? ???????
?????? ?? ??????????????? ???????? ?????????? ????????.
??????, ???????????? ? ????????? ?????????????? ?????, ?????
?????? ?? ??????? ?????????, ??????????????? ??????????? ??????, ????????? ?????????? ???? ??????????. ??? ???? ????? ???????
???? ????????? ??????????? ???? ?????????????? ???????????, ??????? ????????? ??????? ???? ??????. ??? ????? ???? ?????????? ??
???? ???????? ?????, ??????? ?? ????? (???. 8.1) ???????????? ?????????? ??????.
???????? ????? ??????????? ?????????? ??????? ??????? ????????
? ?????????? ??????? ?????? ? ???????? ??????. ??? ????? ???????? ?
???????, ??????????? ???????????? ??????. ???????????? ??????
? ?????? ????? ??????? ??????? ??????????? ???????? ? ????? ?????????, ??? ? ??? ?????????? ?????????? ?????? ? ?????? ??????? ?????
?????????? ?????? ???????????? ???????????. ??????? ????? ??????? ?
???, ??? ????? ??????????? ???????? ?????? ? ???????? ??????, ?????
?? ??? ???? ????????? ??????? ??????????????????, ? ????????? ????????? ? ?????????, ????? ???? ?????????????.
???????? ????????? ???????? ??????????? ??????? ???????????
??????. ???????? ?????? ????? ????????? ????????? ?? ????? ???????? ???????????: ????? ????? ?????? ????????? ??????????????
??????????? ????, ?????????? ????????? ???? ????????? ????????.
?????? ?????? ??????? ?? ????????????? ????????????????? ?????, ?
??????? ??????????????? ?????? ??????????. ? ???? ?? ????? ????????? ?????????? ?????????????, ??? ??????? ???????? ????? ?? ?????????? ??????? ?????? ?? ????????????. ????????, ??? ??? ????????
????? ?? ????? ??????????? ??????.
??? ????????? ????????????? ??????????, ? ????????, ??????????????? ????. ??? ???????? ????, ???????? ?? 1/2, ????????? ??????????
???????? ?? ?????????? ?? ????????? ????. ??? ???????????? ?????????? ???? ????? ???????? ????????????????? ????, ??????????? ?????????? ??????? ???????????? ?? ?????? ?????? ??????????? ?????????? ????????. ????????? ??????? ????????????????? ????? ????????? ? [14].
51
?????? ?????????? ????????????? ???????? ?? ??????? ?????, ?
??? ??????? ??????? ?????????? ?? ????????.
8.2. ????? ????????????????? ?????????????
???? ???????? ?????????? ?????????? ????????????? ?, ?????????????, ???????? ?? ?????????? ????????????? ???????????? ???????????? ???????? ????? ? ????????? ?? ?????????????? ????????????, ??
????????????? ??????????? ???????????? ??????? ?????????????????
????????????? ????? ????? ?? ????? ??????? ????? ???????????? ?????????? ??????? ??????? ??? ?????? ? ?????? [8].
??? ???????????????? ????????????? ????? ????????, ??????? ?????? ????????? ???????, ??? ???? ????? ???????????? ???? ??????, ?????????? ? ??????????? ?? ?????? ????? ? ??????. ????? ????????
??? ???????????????? ????????????? ???????? ???????? ???????? ???????? ? ????? ? ??????. ??? ???? ????????? ????????, ??????? ???????????? ????????, ????? ???????? ??? ????????????? ???????????
?????????. ???????????????? ??????? ???????? ?? ?????????? ?????,
??????????? ????????? ?????????? ?? ??????? ?????????, ? ????????? ??? ??????? ???????? ???????? ????????, ? ???????? ? ???? ??????
???????? ???????????? ??????????, ??????????????? ??? ????????
??????????? ?????? ??? ????????? ?????? ????? ? ??????. ? ?????? ???? ????? ????????? ? ?????? ?????? ???????? ?????????????? ??????????? ????, ??? ???????????????? ????????????? ? ??????
??????? ????????????? ????? ????????? ??????. ?????? ??? ???????????????? ????????????? ?????? ????? ????????? ????? ? ??-?? ????,
??? ??????????? ???????????? ??? ?????? ?????? ????????? ????????????? ??????????, ?. ?. ??-?? ???????????? ??????. ???? ???????????
?????? ??-?? ???????????? ?????? ??????????? ??????????? ??????,
??? ??????????? ????????????? ?????? ??-?? ????????????? ????????? ??? ?????????? ??????, ?? ?????? ??? ? ????? ?????????? ?????????????? ????????? ????????????????? ?????????????.
??? ???????????? ?????????? ????????????????? ?????????????
?????? ???????????? ?????????? ??? ? ???? ???????? ??????, ???????
??? ?????? (???. 2.5, ?) ????????? ?? ???. 8.2.
??????? ?????? ???????? ????????? ???????. ????????? ????????
????????? ??????????? ???????? ?????? ????????????? ????????? ????
??????. ???? ??????? ?????????????? ??????, ??????????? ? ???????,
52
????? 1, ?? ??? ????????????? ?????
00
a
00 a
(????? ??????), ??????, ??? ???????
11
?? ???? ???????, ????, ? ???? ?????b
00
10
????????? ?????? ????? 0, ? ??
c
b
11
01
?????. ??? ????? ???????? ??? ??d
00
11
??? ????, ??????????????? ??????a
10 c
00
???? ????? ?????? ??????, ??? ???- 0
11
b
???? ?? ??????? ?????? ???????? ??01
c
01 d
??? ??????????? ???????, ? ?.?. ???
10
d
?????? ?????? ?????? ??????????00
a
11
a
?? n ??????? ????????, ??????????
11
10
b
??? ???? ?? ?????? ??????. ???????10
c
00
b
????? ?????????? ????????????????
1
01
11
d
?????, ??????????? ?????-???? ???
11
????, ?????????? ????? ??????. ????,
01 c
a
00
??????????? ????? ??????, ??????01
b
01
???? ?????????. ??? ???????? ?????
c
10 d
10
? ????? ?????? ?? ??????? ???? ??d
???? ????? ???????? 2? ?????, ????????.8.2. ??????? ?????? ??????
?? ?? ??????? ???????????? n ?????(???. 2.5, ?)
??? ????????.
????, ??????????? ???????? ????????????? ? ??????? ????????
??????, ?????????? ????????????. ????? ???????, ?????????? ????
????????? ? ???????????.
????? ????????, ??? ????????????? ????? ?????????? ?????????
???? ????? ???????? ?? ???????? ??????, ???? ?????????? ?? ???? ??????, ????? ??????? ??? ???????????????? ??????? ??????????? ?????????? ??????? ???????. ??? ???? ???????? ?? ???. 8.2 ??????????? ??????? a, b, c, d ? ????????????? ?????????? ?????? ?? ?????????
????????? (???. 4.1).
?????? ?????????????????? ?????????? ?????????????? ????????
????????? ???????????? ???? ?? ???????? ??????. ????????, ?????????????? ?????????????????? 1001?. ????????? ???? ?? ????????
??????, ?????????? ????????? ?????? ?? ???. 8.2, ???????? ????????????? ?????????????????? ??????? ???????? 11101111? ????????, ?????? ???????? ??????????? ? ????????? ????????? (???????????) ????,
?. ?. ???? ????, ??????? ? ???????????????? ??? ???????? ???????.
53
????? ???????, ??? ?????????? ????????????????? ?????????????
??????? ?????????? ???????? ?????????????? ???? ?? ??????, ??? ????????? ????????? ?? ??????? ??????? ????? ????????? ?????, ??????? ??????? ?????????????.
???????????, ??? ????? ????????? ?????????? ???, ? ??????????
?? ???????? ?????????????????? ?????????? ?????????????? ??????????????????. ??? ????? ??????? ?????????? ????????????? ?????????? ????? ??????? ???? ???????? ??????, ????????? ???????? ?????????????????? ? ???????????????????, ??????????????? ????, ?? ???????? ?????????? ????????. ???? ??? ???? ??????? ?????????? ????????? ????, ???????? ????????????? ??????????????????, ????? ??????????? ? ???????? ???????????????????, ?? ??????????? ???????, ???
??? ?????????????????? ? ????????????. ????? ????????????????? ?????????????, ???????????? ???????????? [31], ??????????????? ??????? ????? ?? ??????? ?????? ???? ?? m-?? ????? (m ? ????? ????????
???????? ?????? ??????), ??????????????? ???????? ??????? ?????????????????? ????????? ?? ?????-?? ???????????? ?????????? ?? ?????????? ??????????????????, ? ????? ????????????? ??????? ??????????????? ???????. ?????? ?????????? ?????????????? ????????
????????? ?????? ?????????????? ?????? ??????? ????? ??????????
????. ????????? ????? ????????????? ??????? ? ??????????? ?????????????? ???????? ?????????????? ????? ??? ??, ??? ? ??????? ??????????????? ???????, ?? ???? ???????? ? ??? ?????? ??????????
????????????????? ?????????????.
????? ?? ????????? ???????? ???? ?? ??????? ?????? ? ????????
?????????????????? ???????? ?????????? ???????? ????? ????. ????
?????????? ???????? ????? ???????????????????? ? ?????? no, ?????? ????? ???????????? ???????? ????????, ?? ????????? ???????????? ????? Do, ?? ?????????????????? ????? ??????? ????????????. ? ?????? ????????? ????????????? ?????? ????? Do ??????????
????? ???????, ????? ??????????? ????, ??? ?????????? ???????? ????? ?????????????? ? ???????? ???????????????????? ???? ?????? ???
Do, ?? ????????? ???????? 2?L, ??? L ? ????????? ???????? ??????????. ??? ???? ??????????? ????, ??? ?????????? ???????? ????? ?????????? ????? ?????? ? ???????? ??????????????????? ?????? ???
Do, ??? ??????? L ??????????? ??????????? ?????.
???????????, ??? ???? ????? ????????????? ???????????? ? ???????? ???????????? ?????? ? ???????????? ???????? p. ????????, ??? ?
54
???????? ???????????? ?????? ??? ?????? ?????? ?????????? ??????? ?????? ????? ???? ?????? ???????? ? ???????????? ? ? ????????? ? ???????????? q = 1?p, ?????? ? ?????? ?????? ?????? ??????????? ??????? 0 ?? ???????? ??????? ??????????????? ?????? 1, ??? ?
????????. ??? ?????? ??? ?????? ??????????? ?????????? ?????? ??????? ?? ??????? ?? ????, ????? ??????? ???????? ?? ???? ? ??? ???
???? ???????. ?? ???. 8.3 ???????? ??????????? ???????? ??? ????????? ????????????? ??????.
????????? ? ?????? ?????? ????????? ?????????? ? ????????????
???????? ?, ?? ?????????? ???????? d, ??????????? ????? ???????????
????, ??? ???????? ?? ???. 8.4, ????? ?????? ????? ?????????? ?? ????????? p ? ?????? ????? ???????????? ???????? n0. ? ?? ?? ????? ?????????? ????????, ??????????? ????? ?????? ??????? ???? ???????? ??????, ????? ?????????? ?? ????????? 1/2, ????????? ????????? ???? ???????? ?????? ?????????? ???? ?? ????? ?????????????? ? ????????
????????. ????? ???????, ?????????? ????????, ??????????? ?????
??????????? ? ?????????? ???? ???????? ??????, ??????????? ??????????. ??? ????, ???? ???? ?? ????????? ????? ????????????? ????
???????? ?????? ??? ?????? ???????????, ?? ????? ????????? ?????
?????? ????? ??????????, ????? ??????????? ???? ????? ????????? ?
? ????? ?????? ?????????? ???? ????? ??????.
0
q = 1?p
0
d
???????????? ????
(?????? 0,5)
p
?????????? ????
(?????? p)
p
1
q = 1?p
???. 8.3. ???????????
????????? ??? ?????????
????????????? ??????
1
n0
???. 8.4. ??????????? ??????????
???????? d ?? ?????
?????????????? ???????? ? n0
???? ???????? ????????????????? ????????????? ??? ??????? ????????? [31] ?? ?????? ????????????? ??????????? ?????? ??? ??????.
????????? ???? ??????? ????? ?????? ?????????? ???????? ?? ?????? ??????? (?????????????? ?????????? [19]), ?????????? ?????????? ?????????? ????????, ??????? ???? ??????? ????? ????.
55
?????? ?????????? ????????????????? ????????????? ???????? ????????, ???????????? ???? [32], ??????? ??????????????? ?????????? ? ????????????? ??? ????????????? ?????? ? ????? ???? ?????
????????? ???????. ???? ???????? ???????? ?????????? ???? ?? ????,
??? ? ???????? ???????????, ?? ??? ???? ??????? ????? ????????, ??????????? ??? ????????????? ?????? ???????, ?? ??????? ?? ????? ???????? ???????????. ??? ???????? ?????? ????????? ????. ????? ????,
???????????? ????????? ???? ???????? ????? ??, ??? ?? ????????? ????? ??????? ??????????? ??????????. ????????? ????????? ????????
???? ?? ??????? ?? ????? ???????? ???????????, ?? ??? ????????? ???????????? ??? ??? ??????? ???, ?. ?. ??? ????? ???????????? ??????
?? ?????????????? ??????. ????????? ???????????? ??????????????
????????????? ????????? ???? ?????????? ? [8, 14?15].
??? ????? ????????? ?????????? ????????????????? ????????????? ???????? ???????? ???????????, ???????????? ? 1966 ?., ?????????? ?????????? ????????????? ?? ????????? ?????????????.
???? ???????? ?????? ???????? ????-?????????? (?? ???????????
stack ? ????, ?????), ??? ??? ??? ??? ?????????? ????????? ?????? ??????? ???????, ?????????? ??????? ????????? ??????????????? ???????????? ???????, ?. ?. ????????? ????? ???????.
? ???????? ??????? (?????????? ????????) ????? ?? ???????? ?????? ??? ???? ????????? ????? ???????????? ??????? ????????????? ????
(???? ????), ?? ? ??????????? ???????? ????????, ???????? ????????
???????????? ?????? ?? ???????? ????????????? ???? ? ?????????? ??????????? ??????, ????? ??????????? ??????????? ?????? ????????????? ? ???????? ????? ???????? ??? ????????????? ?????? ??????????????? ??????? [24].
?????????? ?????????? ?? ???? ?????????????? ??????????????
??????, ??????? ?????????? ??????? ??? ?????? ????????? ?????????????, ???????? ????????? ?????????, ??? ?????????? ??? ???? ?????????? ????????????????? ?????????????, ??? ??? ??? ??? ????????
??????????????. ?????????? ???????????? ????????? ?????????? ???
??????, ??? ???? ??????? ???? ? ??????, ?. ?. ??? ?????? ???????????
?????? ??? ?????? ??????? ???????? ? ?????? ???????? ????? ?????????. ??? ??????????? ???? ??????????????? ?????????? ??? ????
?????????? ????????????????? ????????????? ????????? ????????? ????????? ????????????? ?????????? (??) ????? ?????????? ???????????????? ????????? ? ?????? ???????? ?????? ?????????. ?????? ?
56
??? ??????, ????? ????? ???????????? ?????????? ??????????? ?????
??????? (???????? ???????????, ??????????????? ????????? ????????? ?????? ?????), ???????? ???????????? ????????? ??, ??? ???????? ? ?????? ? ?????????????. ??? ???????? ??????????? ???? ???????
????????????????? ?????????????. ?????? ????????? ???? ??????? ????
?????, ???? ?????? ?? ??????? ?? ????? ??????? ???????????, ??? ????????? ???????????? ??????? ????? ??????? ???????????, ? ?????????????, ?????????? ??????? ????????????? ??????????????? ??????????? ????.
??? ?????? ? ???????? ? ????????????? ??? ??????? ????????????????? ?????????????, ????? ????????? ???????? ?????????? ?????? ????????? ?? ? ?????????????? ????????, ????? ????? ???????????? ??????? ????? ?????????????? ????????, ??????????????? ? ????????
???????????? ??????? ??????????? ?????? ? ?????????????, ?????????? ?????????????????? ??????? ????????? ????????, ???????? ?????????????????? ?????. ??? ????? ??????? ??????????????? ?? ???????? ?????????? ???? ?? ??????. ? ?????? ??????? ????????? ?????? ????????
??????????? ?????????? ??? ??????????? ?????? ? ?????????????.
??-?? ???????? ?????????? ????? ????????????? ? ????????? ?????????? ?? ????????????? ??? ????????????? ?????????????? ??????? ?????, ??? ??? ??????? ???????????. ? ?????????, ?? ?????????
????????????? ?? ??????? ??????, ??? ??????? ?????????? ????????????? ???????? ?????, ??? ???????, ??????????. ?????? ??? ???? ??????? ????????????? ?????????? ????? ?????????? ???????? ????????????? ?? ????? ???????? ?????? (??????? ?????????????), ?. ?. ????????????? ?? ??????? ????????, ??????????????? ?????? ????? ?????? ??????????? ??????.
??????????? ????? ???????? ??????????? ????? ????????? ?????????? ????? ???????? ??????? (???. 8.9) ? ??? ????????, ??? ?? ????? ???????? ???????? ???????? ??, ???? ????????? ??????? ? ?????? ???????? ????? ?????????.
8.3. ????? ????????????? ?? ????????? ???????
????? ???????????? ????? ????????????? ?? ????????? ?????????????. ???? ????????? ??????? ??????? ? ???, ??? ? ???????? ????????????? ??? ????????? ???? ???????????????? ????????? ?????????
???????, ??????????? ?????????? ??? ???? ??????? ??????? ? ?????57
???? ????????? ?? ?????? ????? ? ?? ?????? ??????? ?????? ?????
????????? ? ?????????? ????????? ?????????? ??????????? ????
(??????????? ????????? ?? ??????????????????, ?????????? ????????
??????? ?? ???????? ?????????????????? ??????????).
????????????? ?? ?????? ???????, ?? ????????, ???????????? ?????
???????? ?????? ???????????????, ??????????? ??????????????? ????
?? ????? ? ?????????? ????????? ????.
8.3.1. ????????????? ? ?????? ?????????? ?????? ??? ??????
???????????????? ?????? ????????? ?? ??????? ?????????????????? ??????????? ???? ? ??????????? (2, 1, 3) ? ???????????? ??????????, ??????????? ?????????? (3.6), ????? ???????? ???????
?? ???. 2.5, ?. ??????? ????????? ?????????????????? ???????? 10110
? ????? ????????, ??? ??? ??????? ??????? ??? ??????.
?????????? ??????????? ???????????
q 2q 1
????????? ????????? ??????? (???. 8.5),
00
00
00
??????? ????????? ????????????? ????11
11
????? (???. 4.1). ????????? ?????? ???????? ????????? 00. ? ???????????? ?
10
10
10
00
?????????? ????????? ????????? ???????
(???. 8.5) ? ?????? ???????? ?????? ???01
01
01
????? ??? ????????: 00 ? 00 ? 00 ? 10.
??????? ???????? ????????????? ?? ??01
10
11
???? ?????? ??????? ?????????? 00, ???11
???? ? 11.
???. 8.5. ????????? ?????????
??? ??????? ?? ??
Документ
Категория
Без категории
Просмотров
0
Размер файла
569 Кб
Теги
0103, 2001
1/--страниц
Пожаловаться на содержимое документа