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

  • Published on
    27-Dec-2016

  • 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- GF (q). , q | , Aq(n; d) Bq(n; d). Bq(n; d) , (1.2.8):

    Bq(n; d) qn=d1Xi=0

    n

    i

    (q 1)i: (1.2.9)

    , :

    qk < qn=d1Xi=0

    n

    i

    (q 1)i;

    [n; k+ 1; d]q-. - Kl, l 2 0; k + 1, [n; l; d]q-. K0 = f0g.

  • 15

    , l 2 0; k [n; l; d]q- Kl . ql qk

    Pd2i=0

    s1i

    (q 1)i, , -

    , nk, d 2 Hs1. Hs1, Hs. Hn (n k) n d 1 . Hn [n; k]q- , d(. 2.1.2), . 2

    1.2.9. ( |). :

    Bq(n; d) qn1=d2Xi=0

    n 1i

    (q 1)i;

    Bq(n; d) qn=d2Xi=0

    n

    i

    (q 1)i:

    2 1.2.8 ,

    qk < qn1=d2Xi=0

    n 1i

    (q 1)i;

  • 16

    [n; k + 1; d]q-. . r = n k. , 1.2.8,

    qr >d2Xi=0

    n 1i

    (q 1)i; (1.2.10)

    [n; nr; d]q-. r - n, (1.2.10). , [n; n r; d]q-,

    qr d2Xi=0

    n

    i

    (q 1)i; . . qk qn=

    d2Xi=0

    n

    i

    (q 1)i:

    . 2 , q | ,

    Aq(n; d) , 1.2.7. 1.2.9

    n, q, d. d , q2 + n2 ! 1,

    Bq(n; d) >

    qn1n1d2

    (q 1)d2 ; Bq(n; d) >

    qnn

    d2

    (q 1)d2 :

    , q(1 d2

    n) < 1. , (1.2.9),

    |.

    E. . [n; k; d]q- K - jj = q R = k=n = d=n, , - . , d=n k=n, [0; 1], , - n.

    Vq = f(; R) 2 [0; 1]2 : [n; k; d]q- d=n = k=n = Rg

    Uq | Vq.

    q() = supfR : (; R) 2 Uqg; 2 [0; 1]:

    q | , , - , V linq , U

    linq

    linq (). , linq () q(). q() linq ()

  • 17

    . , . [64, 1.3.1], [32, 2], q()

    linq ()

    [0; (q 1)=q], q() = linq () = 0 2 [(q 1)=q; 1]. [64]: q()

    linq () -

    (0; (q 1)=q); ; , q() =

    linq ()? q()

    linq ()

    , . [64].

    , Uq q() - , - . , [n; k; d]q- , (d=n; k=n) 2 Uq. (; R) Uq , [ni; ki; di]q- , ni !1,di=ni ! ki=ni ! R i ! 1. , q() - , .. , . .

    1.2.10. . [n; 1; n]q- 1.1.3 = 1, R = 1=n. q(1) = 0, (; R) =2 Uq. , q(). , x 2.5B. , :

    =qm1(q 1)qm 1 >

    q 1q

    ; R =m(q 1)qm 1 > 0;

    , (; R) q().

    , .

    1.2.11. ( ).

    q() 1 :2 [ni; ki; di]q- , ni ! 1

    di=ni ! i ! 1. (1.2.1) Ri 1 i + 1ni . i!1 lim

    i!1 1 . , q() 1 . 2

    q- Hq [0;q1q]

    Hq(0) = 0;

    Hq(x) = x logq(q 1) x logq x (1 x) logq(1 x); 0 < x q1q :

  • 18

    1.2.12. . n t | , t < q1qn, n; t!

    1 , t=n! .

    limn!1

    1

    nlogq sq(n; t) = Hq();

    sq(n; t) (1.2.4).

    2 z 2 (0; 1) :

    sq(n; t) =tX

    i=0

    n

    i

    (q 1)i

    tXi=0

    n

    i

    (q 1)izit =

    zttX

    i=0

    n

    i

    (q 1)izi zt[1 + (q 1)z]n: (1.2.11)

    z, , , tzt1[1 + (q 1)z] + zt(q 1)n = 0, z = t=((q 1)(n t)). t < q1

    qn, z 2 (0; 1). z (1.2.11),

    sq(n; t) (q 1)t(n t)ttt

    n

    n tn

    =(q 1)t

    (t=n)t(1 t=n)nt :

    1

    nlogq sq(n; t)

    t

    nlogq(q 1)

    t

    nlogq

    t

    n1 t

    n

    logq

    1 t

    n

    :

    n; t!1 , t=n! , :

    limn!1

    1

    nlogq sq(n; t) Hq():

    . n

    t

    =

    rn

    2t(n t) nn

    tt(n t)nt e(n)(t)(nt);

    j(k)j < 112k

    , k 2 N . 1

    nlogq sq(n; t)

    1

    nlogq

    n

    t

    (q 1)t = t

    nlogq(q 1)

    t

    nlogq

    t

    n

    1 tn

    logq

    1 t

    n

    +1

    nlogq

    n

    2t(n t) +1

    n((n) (t) (n t)):

    n; t!1, t=n! , :

    limn!1

    1

    nlogq sq(n; t) Hq(): 2

  • 19

    1.2.13. ( ).

    q() 1Hq(=2); 2 [0; 1]:

    2 (1.2.3)

    k n logq sq(n; [d12 ]): n n ! 1, , 1.2.12, . 2

    1.2.14. ( ). -:

    q() 1 q 1q

    ; 0 < q 1q

    ;

    q() = 0;q 1q 1:

    2 [n; k; d]q- K, = dn q1q . 1.2.5, q

    q1 qk

    qk1,

    qk 1 q 1

    q

    1: (1.2.12)

    , n ! 1 k . ,k=n! 0, .. q() = 0.

    < q1q. n0 = [ (d1)q

    q1] < n. n n0

    K. K0 K, nn0 ,

    jK0j qnn0 jKj = qk: (1.2.13) d0 K0

    0 =d0

    n0 dn0 d(d 1)q

    q 1 >q 1q

    : (1.2.14)

    K0 (1.2.12):

    jK0j 1 q 1

    0q

    1:

    , (1.2.13) (1.2.14),

    qnn0k jK0j1 1 q 1

    0q 1 d 1

    d=

    1

    d:

  • 20

    ,

    k n n0 + logq d = n(d 1)qq 1

    + logq d n

    (d 1)qq 1 + 1 + logq d:

    n n!1,

    q() 1 q 1q

    : 2

    , q = 2 - R, | (. . 1.1). , , . ( , , [2, x 13.6], [18, . 98{101],[64], [32, I.2]).

    1.2.15. ( |).

    q() 1Hq q 1q q 1

    q

    s1 q

    q 1

    !:

    .

    1.2.16. ( ).

    q() 1Hq(); 20;q 1q

    :

    2 1.2.7 k n logq sq(n; d 1). n n!1, 1.2.12, . 2

    1.2.17. ( |).

    linq () 1Hq(); 20;q 1q

    :

    (q = 2) . 1.1.

    | 1952{1957. ( q) . 1982 . - , - GF (q), | q.

  • 21

    -

    6

    R

    @@@@@@@@@@@@@@@@@@@@@@@@

    AAAAAAAAAAAAAAAAAAAAAAAA

    0

    1:0

    0:312 0:5 1:0

    1

    2

    3

    4

    5

    . 1.1: (q = 2).1 | ,2 | ,3 | ,4 | |,5 | |.

  • 22

    -

    6

    R

    eeeeeeeeeeeee

    @@@@@@@

    0

    1:0

    q1q

    1:0

    2

    5

    () q < 49

    -

    6

    R

    eeeeeeeeeeeee

    @@@@@@@@@

    0

    1:0

    q1q

    1:01 2

    2

    5

    () q 49

    . 1.2: - GF (q) (q | ).

    1.2.18. ( - ). q| .

    linq () 1 (pq 1)1:

    [66]. [64], [32]. [66, x 6], [64, . 352], q < 49 - | (, , ), q 49 - | 1 2, Hq() = + (

    pq 1)1 (. . 1.2).

    1.3 .

    . -

    A. . : n ! n - ( ) ,

    8a;b 2 n d((a); (b)) = d(a;b): (1.3.1)1.3.1. ( ..). : n ! n

    , 1, ..., n 2 S(), ' 2 Sn,

    8a = (a(1); :::; a(n)) 2 n (a) = (1(a('(1))); :::; n(a('(n)))): (1.3.2)

  • 23

    2 S(n) (1.3.2). , S(n)| S(n) , . , S(n). , 12 2 S(n) 1; 2 2 S(n). \ , ...", , 12 1; 2 2 S(n).

    , = Zq = f0; 1; :::; q 1g (0) = 0: (1.3.3)

    a 2 Znq , , kak a. , (1.3.3),

    8a 2 Znq k(a)k = d((a); 0) = d(a; 0) = kak: (1.3.4)

    , es = (0; :::; 0; 1; 0; :::; 0), s 2 1; n, (1.3.4) k(es)k = 1, ..

    (es) = use'(s); us 2 Zq n 0; s 2 1; n; ': 1; n! 1; n: (1.3.5), ' | 1; n. , s; t 2 1; n s 6= t, d(es; et) = 2. , d((es); (et)) = 2 , (1.3.5), '(s) 6= '(t). , ,

    (es) = e'(s); s 2 1; n; ' 2 Sn: (1.3.6) s 2 1; n u 2 Zq n f0; 1g k(ues)k =kuesk = 1, d((ues); e'(s)) = d(ues; es) = 1. , u 2 Zq

    (ues) = s(u)e'(s); s: ! ; (0) = 0; (1) = 1: s 2 S(), s(u) = s(v) u; v 2

    ,

    d(ues; ves) = 1; d((ues); (ves)) = 0;

    .. | , . , , ,

    8n 2 Zq 8s 2 1; n (ues) = ues; (1.3.7) , = " | - n.

    6= ". (a) = b 6= a a 2 Znq n 0. , (1.3.4), kbk = kak. a(i) 6= b(i) i 2 1; n. .

    (a) a(i) = 0, b(i) 6= 0 d(a; b(i)ei) = kak+ 1 = kbk+ 1;

  • 24

    d((a); (b(i)ei)) = d(b; b(i)ei) = kbk 1: , | .

    (b) a(i) 6= 0, d(a; a(i)ei) = kak 1 = kbk 1;

    d((a); (a(i)ei)) = d(b; a(i)ei) kbk; , | . 2

    1.3.1 \ , - ", . - : n ! n, \" a 2 n \" (a) 2 n. , (a) r . - (a) (a)0 , d((a); (a)0) = r. (a)0 a - a0 = 1((a)0). | , , , a0 a r, n , a . -: d(a; a0) = d((a); (a)0)? 1.3.1. S(n) < S(n) - n.

    B. . . K n K0 n K K0, - 2 S(n) , K0 = (K). , (1.3.2) 1, ..., n , , K K0 . S(n)

    Aut(K) = f 2 S(n) : (K) = Kg K. K , Aut(K) ,

    8a = (a(1); :::; a(n)) 2 n (a) = (a(2); :::; a(n); a(1)): (1.3.8)1.3.2. ( ). -

    1.1.6 F (x) 2 R[x] F (0) 2 R( R | R). , [22], t 2 N , F (x) j x...

Recommended

View more >