: , , - . , . , , .
, . , , .
, , . - , , .. .
t
d0 = t + 1.
, t s ,
d0 = t + s + 1 .,
, s ,
d0 = 2s + 1.
, 2 .
k r :
,
,
,
n = k + ρ
d0 = 3
ρ1(2) = [ log2 (n + 1) ],
n,
ρ 1(2) = [log2 { (k + 1) + [ log2 (k + 1) ] } ],
k.
, (d0 = 4),
ρ 1(3) ³ 1 + log2 (n + 1),
ρ 1(3) ³ 1 + log2 [ (k + 1) + log2 (k + 1) ].
n , (d0 = 5),
ρ 2 ³ log2 (Cn2 + Cn1 + 1).
:
.
, 3 (d0 = 7),
.
, .
2.
, , .
:
|
|
() , .
2. .
:
.
( ) .
, 2. ,
Wmin =d0.
, k r. k,
n = k + r:
, , (n,k)-, (, ).
P Uk Hr ( ). Hr r, Uk k
, Uk
d0 = 2 P
, .
d0 ³ 3 , d0 . . , .
.
d0 = 3 n k : (3; 1), (7; 4),
(15; 11), (31; 26), (63; 57) .
P k . : , , 2 Hr, , , . . , , .
.
,
, - . : b1 , Hr; b2 , . . r.
|
|
S1, S2,..., Sr, . , . , . , .
͒, Hr, Ir,
͒ = úç HrIr úç.
, ͒.
.
. Ai. a1, 1.
, 2 a1 i, . a2, 1, , a1 , a2 - . i a2.
, i aj 1, n . 2 aj, 2, . aj . aj 2r-1 ( ). - aj. aj , .
, 2 i aj, . . 3.2.1.
3.2.1-
a | A1 | A2 | ... | A(2k-1) |
a1 | a1ÅA1 | a2ÅA2 | ... | a1ÅA(2k-1) |
a2 | a2ÅA1 | a2ÅA2 | ... | a2ÅA(2k-1) |
... | ... | ... | ... | ... |
a(2r-1) | a(2 r- 1)ÅA1 | a(2r-1)ÅA2 | ... | a(2r-1)ÅA(2k-1) |
Axn , , . . .
a1, a2,...,a(2r-1) 1, 2,..., (2r-1), .
.
, r + 1, (11,7),
.
3.2.1, 3.2.2 , P, , .
Hr
. .
|
|
A3 .
3.2.1 3
e | A1 | A2 | A3 | A4 | A5 | A6 | A7 | |
A8 | A9 | A10 | A11 | A12 | A13 | A14 | A15 | |
1) 0 1 0 0 1 0 0
2) 1 0 0 0 1 0 0
3) 1 1 1 0 1 0 0
4) 1 1 0 1 1 0 0
5) 0 0 0 0 1 0 0
6) 0 1 0 1 1 0 0
7) 0 1 1 0 1 0 0
a1 1 1 1
__________ ____________ a2 ________ _________ 0 1 1
__________ ____________ a3 ________ _________ 1 1 0
__________ ____________ a4 ________ _________ 1 0 1
__________ ____________ a5 ________ _________ 1 0 0
__________ ____________ a6 ________ _________ 0 1 0
__________ ____________ a7 ________ _________ 0 0 1
, 1011001, 1000101, 0001100, 0000001 1010001.
- 101, 4 = 0001000, . - 5, , 101.
- 010, (010 6) . 8 = 0001101, .. .
- 001 7, 13.
- 001 7, , , - 5.
- 000. .
, . , .. . , .
. . , N = 2k.
,
k r. n, k r
3.3.1 n, k, r
n | k | r | n | k | r |
, : , . , 2i, i = 0, 1, 2 .. - . : 1, 2, 4, 8, 16, 32 ..
(0 1), : . , - 0, - 1.
|
|
: .
n = k + r.
a1 - a2 .., .
3.3.2
n | - | n | - | ||
0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 | 1 a2 a3 a4 a5 a6 | 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 | a7 a8 a9 a10 a11 |
, :
, 1, .. a1, a3,, a5 , a7 , a9 ,a11 ..;
- , 1 , .. .. a2, a3,, a6, a7, a10,a11 ..;
- , 1 , ..
, .
3.3.3
- | ||
1, 3, 5, 7, 9, 11... 2, 3, 6, 7, 10, 11, 14, 15, 18,19, 22, 23, 26, 27, 30, 31... 4, 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23, 28, 29, 30, 31... 8, 9, 10, 11, 12, 13, 14, 15, 24, 25, 26, 27, 28, 29, 30, 31, 40, 41, 42, 43, 44, 45, 46... |
, . .
, , . , .
, , . , , . , . , , .
.
0101. .
.
k = 4. : r = 3 n = 7. n = 7, : 1, 2 4.
:
b1 b2 0 b3 1 0 1.
, .
: 1 Å 3 Å 5 Å 7 , b1 Å 0 Å 1Å 1 b1 = 0.
: 2 Å 3 Å 6 Å 7 , b2 Å 0 Å 0 Å 1 b2 = 1.
: 4 Å 5 Å 6 Å 7 , b3 Å 1Å 0 Å 1 b3 = 0.
:
0 1 0 0 1 0 1.
, 0100101 0100111. , .
: 1 Å 3 Å 5 Å 7 = 0 Å 0 Å 1Å 1 . 0.
: 2 Å 3 Å 6 Å 7 = 1 Å 0 Å 1Å 1 . 1.
: 4 Å 5 Å 6 Å 7 = 0 Å 1 Å 1Å 1 . 1.
1102 = 610. , .
, . , . , , , . , . ( ) .
|
|
. , , , . .
. , , .
, . , G(x) = x3 + x2 + 1 1011. , P(x) = x3 + x + 1 1011. G(x) , . n n, n . ,
G(x) xn = (x3 + x2 + 1) x3=x6 + x5 + x3 = 1101000.
, .
G(x) xn P(x):
1 1 0 1 0 0 0 ½ 1 0 1 1 1 0 1 1 1 1 0 0 1 1 1 1 + 1 0 1 1 1 1 1 0 1 0 1 1 1 0 1 0 1 0 1 1 0 0 1 |
x6+x5+0+x3+0+0+0 ½x3+x+1
x6+0+x4+x3
x5+x4+0+0 x3+x2+x+1+ x5+0+x3+x2
x4+ x3+x2+0
x4+ 0 +x2+x
x3+0+x+0
x3+0+x+1
,
(1)
Q(x) ¾ , R(x) ¾ G(x)×xn P(x).
1 Å 1 = 0, , -1 = 1, ( ), a Å b = 0 a = b, a - b = 0. , a b 0, a b 1, .. .
, (1)
F(x)=Q(x) P(x)= G(x) xn+R(x),
F(x)= (x3 + x2 + x + 1) (x3 + x + 1) = (x3 + x2 + 1) x3 + 1,
F(x)= 1111 1011 = 1101000 + 001 = 1101001.
1101001 , 1101‑ , 001 ‑ . , ( 1111) , , , ( 1101000) ( 001).
P(x). , , . , , . . . , , - ( ). , . . . .
, .
, , .
|
10000000000 ½ 1011
1011
01100 11111+
1011
1110
1011
1010
1011
1000
1011
, .
, , , . , P(x). , , ‑ , ( ). . , W ³ d0 - 1, d0 ‑ . , .
. 2 .
.
, 10- .
.
3.4.1 k ³ 10.
3.4.1 16
n | k | ρ | n | k | ρ |
k = 11, r = 4,
n = 15. x4 + x3 +1.
, .
k = 11 :
( ) :
100000000 11001
11001
10010
11001
10110
11001
11110
11001
011100
11001
010100
11001
11010
11001
0011000
11001
0001
:
. . , . , , .
, k .
. , .
, , . , , . , . , , s, ( 3 3 ), s ( 3 , 1 ).
. k ³ (n / 2), , . . , W £ s, .
.