МНОГОПАРАМЕТРИЧЕСКАЯ КЛАССИФИКАЦИЯ АВТОМАТНЫХ МАРКОВСКИХ МОДЕЛЕЙ НА ОСНОВЕ ГЕНЕРИРУЕМЫХ ИМИ ПОСЛЕДОВАТЕЛЬНОСТЕЙ СОСТОЯНИЙ

  • Published on
    04-Apr-2017

  • View
    218

  • Download
    3

Embed Size (px)

Transcript

  • 2010

    4(10)

    519.217

    .. , ..

    . .. ,. ,

    E-mail: sshalagin@mail.ru, Alsu124@mail.ru

    - () - . , -. (), - , . - , , .

    : , , -, , -, , , , .

    () -

    , , , . . , [1 3]. , - (), , [4, 5].

    , m-, m = 2, 3, . . . [6, 7].

    , -, Statistica 6.0 [8], [9, 10]. , .

    [9, 10] - () , . , [11] , - , [11 13]. , - [11]. - .

  • 42 . . , . .

    , , .

    , [14 16], - , , - . () -, , . , , - N , , . - ().

    1. 1. [1]

    (S, P, 0) , (1)

    S = {s0, s1, . . . , sn1} ; P [1] - P = (pij), i, j = 0, n 1; 0 n- - .

    2. - [4] (

    U , S, P, (u, s)), (2)

    U [4], u0, u1, . . . , ul1 p = (p0, p1, . . . , pl1); l -

    [4];l1i=0

    pi = 1, 0 6 pi 6 1; (u, s) ,

    (u, s) s S. P =l1i=0

    piAi, Ai

    ( [5]). Ai, akj(i), k, j = 0, n 1, :

    akj(i) =

    {1, (ui, sk) = sj,0, (ui, sk) 6= sj.

    3. (1) , , . . - [1].

    4. C P , -, .

    , (1) (2), . : D, - . , P , (P ).

    , . , : ()

  • 43

    - (). () - (). () (). :

    1) pij, i = 0, n 1, j = 0, i, p0(n1);2) pij, i = 0, n 1, j = i, n 1, p(n1)0;3) pij, i, j = 0, k 1, k = [n/2], pij, i, j =

    = k, n 1, p(k1)k pk(k1);4) pij, i = 0, k 1, j = k, n 1, k = [n/2], pij,

    i = k, n 1, j = 0, k 1. -

    . -

    , , ?

    2. (P ) ,

    P , . fk, k = 1 n, n 1,

    si sj (si, sj S, i, j == 0, n 1) , i j = k. fk , [7].

    N Y (N1),, yz = k i j = k (yz Y , z = 1, N 1), z- si sj.

    si sj , i j = k,

    fk =1

    N 1N1z=1

    yz, yz =

    {1, yz = k,0, yz 6= k,

    k = 1 n, n 1. (3)

    fk (k = 1 n, n 1) si sj , i j = k, fk, - (P ), (P ),

    fk =1

    n

    n|k|i=1

    m(i, k), (4)

    m(i, k) = pi(ik) k = 1 n, 0 m(i, k) = p(i+k)i k = 1, n 1. (3) (4) . - N . k = |fk fk|(k = 1 n, n 1) , fk - si sj i j = k, i, j = 0, n 1. , fk, k = 1 n, n 1, . - , k [17]. - N > 5 [17]. , fk Y (N 1), -

  • 44 . . , . .

    [17]

    k =fk fk = t

    fk (1 fk)N 1

    , k = 1 n, n 1, (5)

    t , - , , . fk - [17]

    fk [

    5

    N 1,N 6N 1

    ]. (6)

    1. (6) , (3), N1z=1

    yz

    [5, N 6], yz Y , z = 1, N 1. (6) fk -

    , . k

    k = max(|fk p1k|, |p2k fk|), (7)

    p1k p2k , :

    N1m=l

    CmN1pm1k (1 p1k)

    Nm1 =

    2;

    lm=0

    CmN1pm2k (1 p2k)

    Nm1 =

    2,

    l si sj , i j = k, k = 1 n, n 1 [16]. (5)

    N =fk

    (1 fk

    )f fk2 t2 + 1 6 maxfk

    fk(

    1 fk)

    2t2

    = 142

    t2, k = 1 n, n 1. (8)

    1. N , -

    f , (P1) (P2), P1 P2 - , (8).

    1, , - ,

    = maxk=1n,n1

    (min fk(P1)min fk(P2)) , (9)

    fk(P1), fk(P2) k- , P1 P2 -, N , - , , - , (8).

    1 (P ) -, P .

  • 45

    3. ()

    pij > 0 P D pij [D, 1 D],i, j = 0, n 1. (4) fk, k = 1 n, n 1.

    (P ), P {,,,}, - , P , (P ), .

    1. (4). 2. , fk

    P , (P ) ( ). 3. fk -

    (3) . N, , k, (5).

    4. , (P ), , , , , , - .

    1 4 (3).

    1 . 2. fk, k = 1 n, n 1,

    Vk P (4), , min fk, , h = D h Vk, , max fk, , h = 1D h Vk.

    (min fk,max fk) - .

    f1n = (D, 1D) , fk = (0, 0), k = 2 n,1,f0 =

    (D, 1 (2 + n(n 1))0,5Dn1

    ), (10)

    fk =((1 kn1)D, 1 (n+ k 1)(n k)0,5Dn1

    ), k = 1, n 1.

    :

    fk =((1 kn1)D, 1 (n+ k 1)(n k)0,5Dn1

    ), k = 1 n,1,

    f0 =(D, 1 (2 + n(n 1))0,5Dn1

    ), (11)

    fk = (0, 0), k = 1, n 2, fn1 = (D, 1D).

    , w = 0,5n v = [w] + 1, n > 4:

    fk = (0, 0) k = 1 n,v k = v, n 1,f0 =

    (D, 1 2Dn1((v 1)2 1)

    ). (12)

  • 46 . . , . .

    n:

    f1 =

    ((n 1)Dn1, 1 2Dn1

    ((v 1,25)2 + 23

    16

    )),

    f1 =((n 1)Dn1, 1 2Dn1(v 1,5)2 + 0,25

    ),

    fk =((1 + 2k)Dn1, 1 (v 1) (v + k) +D (v 2) (n+ k v)

    ), k = 1 v,2.

    n:

    f1 = f1 =((n 1)Dn1, 1 2Dn1((w 1,5)2 0,75)

    ),

    fk =((1 2|k|)Dn1, 1Dn1(2w2 n(1 + |k|) + 2|k|+ 1)

    ), k = w,2, k = 2, w.

    : f0 = (0, 0); - n:

    fk =(kDn1, 1 k[w]D

    ), k = 1, [w],

    fk =(kDn1, 1 k[w]D

    ), k = [w],1, (13)

    fk =([w]Dn1, 1 2[w]D

    ), k = [w] + 1,

    fk =((1 k)Dn1, 1 (n k)[w]D

    ), k = 1 n,[w] 2, k = [w] + 2, n 1;

    n:

    fk =(|k|Dn1, 1 + |k| (1 w)D

    ), k = w + 1,1, k = 1, w 1,

    fk =((1 |k|n1)D, 1 (n |k|) (w 1)D

    ), k = 1 n,w, k = w, n 1.

    , (10)(13), . 1 2 . Q-

    , , - , , ; JQ fk, fk(Q) = 0.

    3. fk (4), RQ, - (P Q) , : fk(Q) = 0, min fk (Q) > 0, k JQ.

    4. RQ(1) RQ(2) fk (4), - (P1 Q(1)) (P2 Q(2)), Q(1) Q(2) = , .

    (10)(13), fk 0 :

    fk(T) = 0, k JT = {2 n, 3 n, . . . ,1},fk(T) = 0, k JT = {1, 2, . . . , n 2} ,

    fk() = 0, k J = J1 J2 = {1 n, 2 n, . . . ,v} {v, v + 1, . . . , n 1},f0() = 0.

  • 47

    1 fk, k = 1 n, n 1

    P min fk max fkD, k = 1 n 1D, k = 1 n

    D, k = 0 1 (2 + n(n 1))0,5Dn1,k = 0

    (1 kn1)D, 1 (n+ k 1)(n k)0,5Dn1,k = 1, n 1 k = 1, n 1

    0, k = 2 n,1 0, k = 2 n,1(1 kn1)D, 1 (n+ k 1)(n k)0,5Dn1,k = 1 n,1 k = 1 n,1

    D, k = 0 1 (n+ k 1)(n k)0,5Dn1,k = 0

    D, k = n 1 1D, k = n 10, k = 1, n 2 0, k = 1, n 2

    n mod 2 = 1

    min fk max fk

    kn1D, k = 1, [w] 1 k[w]D,k = 1, [w], k = [w],1

    [w]Dn1, 1 2[w]D,k = [w] 1, k = [w] + 1 k = [w] 1, k = [w] + 1

    (1 k)n1D, 1 (n k)[w]D,k = 1 n,[w] 2, k = 1 n,[w] 2,k = [w] + 2, n 1 k = [w] + 2, n 1

    kn1D, k = [w],1n mod 2 = 0

    min |fk| max |fk| |k|n1D, 1 |k| (w 1)D,

    k = w + 1,1, k = w + 1,1,k = 1, w 1 k = 1, w 1

    (1 |k|n1), 1 (n |k|) (w 1),k = 1 n,w, k = 1 n,w,k = w, n 1 k = w, n 1

    3 4 - () (P ), P {,,,}, ( ).

  • 48 . . , . .

    1. , , - (P), , (M), M{,,}.

    2. , -, (P), , (M).

    3. , , - (P), , (P).

    1 , {, , , }. , . :

    A1 = maxkJ

    |min fk()min fk()| = maxkJ

    (min fk()) = (n 1)Dn1 k = 1,

    B1 = maxkJ

    |min fk()min fk()| = maxkJ

    (min fk()) = (n 1)Dn1 k = 1. , ,

    C1 = max

    k(J\J1 )J2|min fk()min fk()| =

    = max

    (max

    k(J\J1 )(min fk()), max

    kJ2(min fk())

    ).

    (14)

    J\J1 = {[w],[w]+1, . . . ,1}. maxk (min fk()) == (n 1)Dn1 k = 1, k J2 maxk (min fk()) = (n 1)Dn

    1

    k = 1. C1 = (n 1)Dn1. , , , (14),

    E1 = maxkJ{0}

    |min fk()min fk()|. J{0} = {2n, 3n, . . . , 0},

    maxkJ

    (min fk()) = [w]Dn1, min f0 () = D. E1 = D.

    1 : {,,,}, , min (A1, B1, C1, E1) = (n1)Dn1. fk, fk - : |min fk()min fk(Q)| > (n1)Dn1, Q {,,,}. R .

    2 , = {,}.

    , , - (13), A2 = max

    kJ\J2|min fk()min fk()| = (n 1)Dn1, k = 1.

    , , , - (14), B2 = max

    k{0}J|min fk()min fk()| = D. {0} J = {0, 1, . . . ,

    n 2}, min f0 () = D, maxkJ

    (min fk()) = [w]Dn1.

    , 2, , - , min(A2, B2) = (n 1)Dn1. , - R , fk, fk |min fk()min fk()| > (n 1)Dn1.

    , . - , (14), A3 = max

    k{0}J|min fk()min fk()|.

  • 49

    {0} J = {1 n, 2 n, . . . ,v, 0, v, v + 1, . . . , n 1}, min fk () = D k = 0, max

    kJ(min fk()) = [w]Dn1.

    , R , fk, fk - : |min fk()min fk()| > D.

    , , 1 3, 2. (P ), P {,,,},

    R = R R R . , (9), (n 1)Dn1.

    3. (3), R, , (P ), - , P . , , (P ), (5) ( (6) )

    N = maxfkR

    (fk

    (1 fk

    )t22k + 1

    )6

    n2t24(n 1)2D2

    + 1, (15)

    k fk R fk, - (n 1)Dn1. k, - , (15). = 0,95, -, t = 1,96 [17], D = 5 102. , (15) -: N = max

    fkR

    (1536,64 n2 (n 1)2 fk

    (1 fk

    )+ 1). , (15),

    fk = 0,5 N 6 384,16 n2 (n 1)2 + 1. 3. , (6) R

    J , fk, k J , (7) Nk:{

    (n 1)Dn1 > fk p1k,(n 1)Dn1 > p2k fk,

    {p1k > fk (n 1)Dn1,p2k 6 (n 1)Dn1 + fk,

    (16)

    p1k p2k , (7), = 0,95:

    Nk1m=l

    CmNk1pm1k (1 p1k)

    Nkm1 = 0,475,l

    m=0

    CmNk1pm2k (1 p2k)

    Nkm1 = 0,475.

    l si sj , i j = k, k = 1 n, n 1.

    5. , - , (P ), N = max(Nk, Nz), Nk, k J , (16), Nz -, (15), z = 1 n, n 1.

    2 3 , P{,,,}, n = 5. - fk . 2; .

  • 50 . . , . .

    2 n = 5

    f4 (D, 1D)/5 (D, 1 4D)/5 (0, 0) (D, 1D)/5f3 (0, 0) (2D, 1 7D)/5 (0, 0) (2D, 1 2D)/5f2 (0, 0) (3D, 1 9D)/5 (D, 1 2D)/5 (2D, 1 2D)/5f1 (0, 0) (4D, 1 10D)/5 (4D, 1 9D)/5 (D, 1D)/5f0 (5D, 1 11D)/5 (5D, 1 11D)/5 (5D, 1 10D)/5 (0, 0)f1 (4D, 1 10D)/5 (0, 0) (4D, 1 8D)/5 (D, 1 2D)/5f2 (3D, 1 9D)/5 (0, 0) (D, 1 3D)/5 (2D, 1 4D)/5f3 (2D, 1 7D)/5 (0, 0) (0, 0) (2D, 1 4D)/5f4 (D, 1 4D)/5 (D, 1D)/5 (0, 0) (D, 1 3D)/5

    1 . 3, , - . {,,,} fk, k = 1, 1, k 6 D.

    3 , {,,,}

    f4 f3 f2 f1 f0 f1 f2 f3 f4 Ma. .

    0,4D 0,6D 0,8D 0,8D 0,6D 0,4D 0,8D

    0,2D 0,2D 0,8D 0,4D 0,4D 0,2D 0,8D

    0,4D 0,4D 0,2D D D

    , 2, . 4 {,,} fk, k = 0, 1, D.

    4 , {,,}

    f4 f3 f2 f1 f0 f1 f2 f3 f4 Ma. .

    0,2D 0,4D 0,4D 0,8D 0,2D 0,2D 0,8D

    D 0,2D 0,4D 0,4D D

    . 5 3, f0 D.

  • 51

    5 ,

    f4 f3 f2 f1 f0 f1 f2 f3 f4 Ma. .

    0,2D 0,4D D 0,4D 0,2D D

    . 24 , (P ), P {,,,}. k = D, k = 1, 1.

    (3), fk, k = 1, 1, , (P ), - , P . -, , (P ), (5) (14):

    N = maxfkR

    (2401 fk

    (1 fk

    )+ 1)6 602,

    k fk fk, k = 1, 1, - 2 n = 5. , , (15); = 0,95, t = 1,96;D = 5 102.

    4. 4 , -

    (P ), P {,,,}. (15) (5) , (16) .

    , (P ). P , , , n = 5. ,, , MS Excel. D = 5 102.

    5 (P ), 20 , , , 400 . (15) 602, , - , (5). - N , , (P ), 94% NM = 602.

    N , , . 6.

    , - ( = 0,95), (), - 509 , 85% NM . , , 473 . - 79% NM . . , (),

  • 52 . . , . .

    , , ().

    6 N ,

    N % % NM 380 564 87 63 94

    86 233 13 14 39

    380 564 99 63 94

    417 564 97 69 94

    343 564 90 57 94

    , , - . - . 7. (F -) 221,8 p < 5 105. - 1,622 102. -.

    7

    - F - (3,291) .

    f1 0,073929 409,5078 0,718518

    f0 0,074529 413,8994 0,619251

    f1 0,094515 560,1085 0,668676

    . 7 - : - , F - - . , [11, 12], - 409 [4, 7], - 0,1. .

    , - , 100%, .

    5.

    , si sj i j = k (si, sj S, i, j = 0, n 1), , - (P ). P , , ,

  • 53

    , (P ). -, (P ) .

    , . .

    , 3 n = 5 , , 602 0,5. - , n . , (2n 2), - . , n . .

    N , (11), (

    maxkJ

    k

    )1.

    k, , D , 22 0,5D. , , 621% .

    (P ) -

    , P . , - .

    , - (P ). 0,5 - . - , .

    , - , - .

    1. ., . . .: , 1970. 272 .2. .. . .; .: , 1949. 436 .3. . . -

    . .: . , 1976. 344 .4. . . . .: , 1985. 287 .

  • 54 . . , . .

    5. .. . .: , 1970. 88 .6. .., .., .., .. .

    .: , 2002. 480 .7. Friedman W.F., Callimahos D. Military crypto analyze. Part I. V. Z. Aegean Park Press,

    Laguna Hills CA, 1985. 356 p.8. .. Statistica: . 2- . .: -

    , 2003. 700 .9. .., .., .. .

    // . .. . 2001. . 1. 3.. 3739.

    10. .., .., .., .. - // - . : , 2000. . 91106.

    11. ., ., .M. - . .: , 1977. 221 .

    12. . . .: , 1982. 272 .13. .. // . . 1953.

    3(55). . 320.14. .., .. -

    // . . : . . . : - , 2007. . 9092.

    15. .., .. - // XV : . . .: - . .. , 2007. C. 7879.

    16. .., .. - // . .. . 2010. 1. . 9499.

    17. .. . IV ., . .: , 1969. 576 .

Recommended

View more >