Линейные коды и полилинейные рекурренты

  • View
    228

  • Download
    8

Embed Size (px)

Transcript

  • .., ..

    , 1997

  • 4

    1 , 61.1 . . . . . . . . . . . . . . . . . . . . . . . 61.2 . . . . . . . . . . . . . . . . . . . . 91.3 .

    . . . . . . . . . . . 22

    2 262.1 . . . 262.2 . . . . . . 312.3 . . . . . . . . . . . . . . . . . . 332.4 - . . . . . . . . . . . . . 422.5 . . . . . . . . . . . . 45

    3 543.1 . . . . . . . . . . 543.2 . . . . . . . . 573.3 . . . . . . . . . . . . . . . . . . . 613.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 643.5 | . . . . . . . . . . . . . . . . . . . . . . . . . . . 723.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

    4 864.1 , . . . . . . . . 884.2 . . . . . . . . . . . . . . . . . . 1014.3 . 1134.4 . . . . . . . . . . . . . . . . 1214.5 - . . . . . . . . . . . . . 127

    5 1325.1 . - 1325.2 - . . . . . . . . . . . . . . . . . . 1405.3 - . . . . . . . . . . 150

    2

  • 3

    5.4 - . . . . . 1535.5 . . . . . . . . . . 1585.6 . . . . . . . . . . . . . . . . . . 1635.7 . . . . . . 170

    6 1806.1 . . . . 1816.2 . . . . . . . . . . . . . . 1886.3 1936.4 . . . . . . . . . . . . . 1996.5 -

    . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2016.6 . . . . . . . . . . . . . . . . . 205

    7 : , , 2117.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2117.2 . . . . . . . . . . . . . . . . . . . . . . . 2147.3 . . . . . . . . . . . . . 217

    226

  • , - [5, 17, 53, 10] , ( ) [2, 7, 17, 18, 26, 47, 64, 65, 66, 46, 67] , - , - . , , (., , [9]). - , , .

    - , . , , - , , , . , 7.3.

    4, 5, - . , , , -. 7.1, 7.2 . -, .

    6, , , - . -, , , :

    | - ;

    | , ;| ,

    .

    4

  • 5

    , . , - .

  • 1

    ,

    1.1

    A. . n K n. K . a =(a1; :::; an) 2 n b = (b1; :::; bn) 2 n d(a;b) i 21; n, ai 6= bi. , d: n n ! R n, ..

    1.1.1. . a;b; c 2 n

    d(a;b) = 0 , a = b;

    d(a;b) = d(b; a);

    d(a; c) d(a;b) + d(b; c):

    K

    d(K) = minfd(a;b) : a;b 2 K; a 6= bg:

    K n , C d, (n; C; d)-. k =logjj jKj ( k ). -, K [n; k; d]- [n; k; d]q-, q = jj. , - , (n; C)- [n; k]-.

    1.1.2. . = Z2 K = f(0; 0; 0); (1; 1; 1)g. K [3; 1; 3]Z2-.

    6

  • 7

    1.1.3. ( , ). | . K = f(a; :::; a) : a 2 g [n; 1; n]-.

    1.1.4. ( ). (; ) | - e. K = f(a1; :::; an) 2 n : a1:::an = eg [n; n 1; 2]-. , a;b 2 n d(a;b) = 1, - a;b K , .. d(K) 2. , K a = (a; a1; e; :::; e) b = (a; e; a1; e; :::; e), a 2 n e, d(K) d(a;b) = 2. , = Z2. K .

    1.1.5. . = Z2, K = f(0; 0; 0); (0; 1; 1); (1; 0; 1); (1; 1; 0)g Z32. K [3; 2; 2]Z2-.

    1.1.6. ( ). = R | - , F (x) 2 R[x] | m R LR(F ) | u R F (x). n m

    K = L0;n1R (F ) = fu(0; n 1) : u 2 LR(F )g; u(0; n 1) = (u(0); :::; u(n 1)) n u 2 LR(F ), [n;m]R-. K R = Z2, F (x) = x

    2 + x + 1, n = 3. - F (x) K .

    K n , , b 2 n - a 2 K, .. a 2 K, d(a;b) . a , - . - a 2 K.

    B. . k[n; k]- K , n, k=n - K K. k=n 1 k=n 1, ,, K | -.

    d(K) K K - . d(K) > r, , K r. d(K) > 2r, , K r . - .

  • 8

    r a 2 n Or(a) = fb 2 n : d(a;b) rg:

    1.1.7. . K n d(K) > r , 8a 2 K Or(a) \ K = fag; (1.1.1)

    d(K) 2r + 1 , 8a;b 2 K (a 6= b)) (Or(a) \ Or(b) = ?): (1.1.2)

    , K , a 2 K a0, a r , .. d(a; a0) = r. , r < d(K), (1.1.1), a0 =2 K, , (, K), , . r < d(K)=2, , (1.1.2), b 2 K ,

    8c 2 K n b d(a0;b) < d(a0; c); b = a. , a a0.

    , - , . - . , -, , -9 [32; 6; 16]Z2- 6=32.

    [n; k; d]- - x 1.2.

    C. K k 2 N , - 1 i1 < i2 < ::: < ik n , !1; :::; !k 2 - a 2 K, ai1 = !1, ..., aik = !k. , i1, ..., ik | K, 1; n n fi1; :::; ikg = fik+1; :::; ing | . - ai1 , ..., aik a 2 K, aik+1 , ..., ain | . -

    1.1.8. . K 2 n | k - i1, ..., ik, K [n; k]-, 'k+1; :::; 'n:

    k ! , 8a 2 n (a 2 K), (ais = 's(ai1 ; :::; aik); s 2 k + 1; n): 2 (1.1.3)

  • 9

    (1.1.3) - K.

    , (1.1.3) a - (ai1 ; :::; aik) b 2 K , . , 1.1.2{1.1.6 [n; k]- - 1; k.

    D. . = RM | R e. K R- Mn n M n M , [n; k]M -, k =logjM j jKj. .

    a 2 Mn kak = d(a; 0) a.

    1.1.9. . K < Mn -

    d(K) = minfkak : a 2 K n 0g: (1.1.4)

    . , [n; k]P - P K < P n k. , 1.1.2, 1.1.4{1.1.6 .

    1.2

    A. , -.

    1.2.1. ( ). K [n; k; d]-,

    d n k + 1: (1.2.1)

    2 K:

    ai = (ai1; :::; ain); i 2 1; C; C = jjk;

    0B@ a11 : : : a1n... ...aC1 : : : aCn

    1CA =0B@ a11 : : : a1;d1 a1d : : : a1n... ... ... ...

    aC1 : : : aC;d1 aCd : : : aCn

    1CA :

  • 10

    d(K) = d, n d + 1 . , n d+ 1 , ..

    k = jCj jjnd+1: 2 (1.2.1)

    jKj jjnd+1 (1.2.2) [18, 7] K. K - , - (1.2.1), (1.2.2) , .. K [n; k; n k + 1]-.

    - [n; n; 1]- K = n, [n; 1; n]- ( 1.1.3) [n; n1; 2]- \" 1.1.4. q = 2 - [18, . 310]. (. [47, . 192], [18, . 312, 7]), - n k q [n; 1; n]- .

    1.2.2. ( |). P | q , k 2 N P [xjk] | P k. n !1; :::; !n 2 P n( ) u1; :::; un 2 P . a(x) 2 P [xjk]

    v(a(x)) = (u1a(!1); :::; una(!n)) 2 P n: k n

    K = fv(a(x)) : a(x) 2 P [xjk]g [n; k; nk+1]P -, k .

    , , K | P n, P [xjk] e; x; :::; xk1, K

    v(e) = (u1; u2; :::; un);v(x) = (u1!1; u2!2; :::; un!n);: : : : : :

    v(xk1) = (u1!k11 ; u2!

    k12 ; :::; un!

    k1n ):

    k n , , k , , . a(x) 2 P [xjk]n0, v(a(x)) a(x) P , .. , k 1. ,

  • 11

    kv(a(x))k n (k 1) d(K) n k + 1. , , ,a(x) = (x !1):::(x !k1), kv(a(x))k = n (k 1). , d(K) =nk+1 K -. GRSP (n; k) [n; k]- | P .

    | n = q, u1 = ::: = un = e. [q; k; q k+1]P -. RSP (k).

    B. ( ). - .

    1.2.3. ( ). K [n; k]-

    q d(K) > 2r,

    qk qn=sq(n; r); (1.2.3)

    sq(n; r) = 1 + (q 1)n+ (q 1)2n

    2

    + :::+ (q 1)r

    n

    r

    : (1.2.4)

    2 , sq(n; r) Or(a) r - a 2 n. a 2 K . , jKj jOr(a)j =qksq(n; r), jjn = qn. 2

    (1.2.3) , . K , (1.2.3) (, d(K) = 2r + 1).

    , 1.1.2, , , - , -, 3.

    \ " -.

    1.2.4. ( ). l 2 N , l > 1, n = 2l 1 Hln | Z2, l Z2,

    Hln =

    0BBBB@1 0 1 0 : : : 10 1 1 0 : : : 10 0 0 1 : : : 1. . . . . . . . . . . . . . . . . .0 0 0 0 : : : 1

    1CCCCAl(2l1)

    :

  • 12

    K a# 2 Zn2 Hx# = 0: (1.2.5)

    K [n; n l; 3]Z2 . -, K . rankH = l, dimK = n l. K (1; 1; 1; 0; :::; 0) 3 2, H . , d(K) = 3. - K (1.2.5). , - (1.2.3) 2nl,

    2n

    s2(n; 1)=

    2n

    1 + (2l 1) = 2nl:

    , K | . H2(l). , H2(l) - l = 2,

    1.1.2.

    P = GF (q),. x 3.3.

    [23; 12; 7]2 [11; 6; 5]3- (. [47, 9, 12]). | , q , , [ q

    m1q1

    ; qm1q1 m; 3]q- Hq(l) [18].

    [2, x 13.2], [18, 20], [47, 9].

    C. . .

    1.2.5. ( ). [n; k]- K q

    d nqk1(q 1)qk 1 =

    q 1q

    jKjjKj 1 n: (1.2.6)

    2 K n [n; k; d]- M = qk. d K:

    d 1M(M 1)

    Xa;b2K

    d(a;b):

    mij K, i- j 2 . Pj2mij = M i 2 1; n. jl | .:

    M(M 1)d Xa;b2K

    d(a;b) =Xa;b2K

    nXi=1

    (1 ai;bi)

  • 13

    =nXi=1

    Xj;l2

    (1 jl)mijmil =nXi=1

    24 Xj2

    mij

    !2Xj2

    m2ij

    35=

    nXi=1

    "M2

    Xj2

    m2ij

    #:

    ||,

    M(M 1)d nXi=1

    24M2 1q

    Xj2

    mij

    !235 = q 1q

    M2n;

    . 2 , (1.2.6), , -

    :

    d =1

    M(M 1)Xa;b2K

    d(a;b):

    , - . . - [n; 1; n]- 1.1.3. .

    1.2.6. ( ). P = GF (q) | q -, V | k P 0 V n 0 = fv1; :::; vng,n = qk 1. V g:V ! P (- V ) g 2 V

    g = (g(v1); :::; g(vn)) 2 P n:

    SP (k) = fg 2 P n : g 2 V g [n; k; q1

    q(n+ 1)]-.

    , , SP (k) | Pn jSP (k)j =

    jV j = qk. , , , v1; :::; vk V , g 2 SP (k) g(v1); :::; g(vk),.. SP (k) | 1; k. , g 2 SP (k)n0, g:V ! P V P ( g(V ) P ). ,Ker g V dimP V dimP P = k1, V n 0 qk1 1 vi , g(vi) = 0. kgk = n (qk1 1) = q1

    q(n + 1) d(SP (k)) =

    q1q(n + 1). ,

    SP (k) , . . Sq(k).

  • 14

    - , x 2.5B. , - . , (1.2.6) . ,, K (1.2.6). K , - K d, jKj

    jKj1> jKj

    jKj1,

    K K (1.2.6) .D. |. Aq(n; d) -

    C, (n; C; d)q- jj = q. (1.2.3) :

    Aq(n; d) qn=[ d1

    2]X

    i=0

    n

    i

    (q 1)i: (1.2.7)

    1.2.7. ( ).

    Aq(n; d) qn=d1Xi=0

    n

    i

    (q 1)i: (1.2.8)

    2 , K | (n; C; d)q-, , K, K d. , , jKjsq(n; d1) qn, sq(n; d1) | d 1 n, . (1.2.4). . 2

    , -:

    C < qn=d1Xi=0

    n

    i

    (q 1)i;

    (n; C; d)q-. Bq(n; d) q

    k, [n; k; d]q-

Recommended

View more >