Кодирование информации: Методические указания

  • Published on
    08-Dec-2016

  • View
    228

  • Download
    8

Embed Size (px)

Transcript

  • 2006

  • 2006

  • 681.3 (076) 32.811.4 7 57

    - . . , . .

    : / .: . . , . . . : , 2006. 56 .

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

    . .

    , 23020165 200103165 - . .

    681.3 (076) 32.811.4 7

    . . , . . , , 2006 . , 2006

    57

  • :

    . .

    30.03.2006. 6084/16. . . . . . 3,03. .-. . 3,00. 100 .

    .

    432027, . , . . , . 32.

    , 432027, . , . . , . 32.

  • 55

    1. 3 1.1. 3 1.2. 3 1.3. 5 1.4. 6 1.5. 8 1.6. 9

    2. 10 2.1. 10 2.2.

    11

    2.3. 13 2.4. : 15 2.5. .

    19

    2.6. . 27 2.7. 39

    3. 42 3.1. 42 3.2. 43

    4. ,

    46

    4.1. 46 4.2. - 47 4.3. 49

    52 54

  • 3

    1.

    1.1. ,

    , , .

    .

    , , , , , .

    1.2.

    . , .

    : . , . 1, 0. . . , .

    . , ( ) .

    , . . ,

    64631

    8

    1i)logp(z)p(zH(z) ii =

    == (1.1)

    64631

    8

    1i)n(z)p(zl ii =

    = , (1.2)

  • 4

    n(zi) 1, zi. .1.1.

    . 1.1

    z1 1/2 1 z2 1/4 01 I z3 1/8 001 II z4 1/16 0001 III z5 1/32 00001 IV z6 1/64 000001 V z7 1/128 0000001 VI z8 1/128 0000000 VII

    , H(z). , . 1.2, 2,76,

    2,84.

    . 1.2

    z1 0,22 11 II z2 0,20 101 III z3 0,16 100 I z4 0,16 01 IV z5 0,10 001 V z6 0,10 0001 VI z7 0,04 00001 V I z8 0,02 00000 VII

    ,

    . , , .

    1 , .

  • 5

    1.3.

    , ,

    z1 z2 p(z1)=0,9 p(z2)=0,1.

    , . .

    , 1, 0, 0,47.

    , , , . 1.3.

    . 1.3

    z1 z1 0,81 1 z1 z2 0,09 01 I z2 z1 0,09 001 II z2 z2 0,01 000 III

    ,

    . 1,29,

    0,645. , ,

    . . 1.4.

    . 1.4

    z1z1z1 0,729 1 z2z1z1 0,081 011 I z1z2z1 0,081 010 III

    z1z1z2 0,081 001 II

    z2z2z1 0,009 00011 IV

    z2z1z2 0,009 00010 VI

    z1z2z2 0,009 00001 V z2z2z2 0,001 00000 VII

  • 6

    1,59, 0,53, 12% . (z)=0,47 , :

    ( )zHllim n = . (1.3)

    , , . , , , .

    1.4.

    . , . , . 1.2, , , , . 1.5.

    . 1.5

    z1 0,22 11 z2 0,20 10 II z3 0,16 011 I z4 0,16 010 IV z5 0,10 001 III z6 0,10 0001 V z7 0,04 00001 VI z8 0,02 00000 VII

    2,80. , . m>2 .

    . .

    . .

  • 7

    , . , , , . , , .

    , . 1.6. , . 1.2.

    . 1.6

    -

    1 2 3 4 5 6 7

    z1 z2 z3

    0,22 0,20 0,16

    0,22 0,20 0,16

    0,22 0,20 0,16

    ->0,26 0,22 0,20

    ->0,32 0,26 0,22

    ->0,42 ->0,58 ->1 0,321 0,42 0,26

    z4 0,16 0,16 0,16 0,16 0,20

    z5 z6 z7

    0,10 0,10 0,04

    0,10 0,10 0,03

    0,16 0,10

    0,16

    z8 0,02

    ,

    , .

    . , 1, , 1, 0. , . , . 1.6, . 1.1.

    . 1.1. , . 1.6,

  • 8

    , , :

    zl z2 z3 z4 z5 z6 z7 z8 01 00 111 110 100 1011 10101 10100

    1.5.

    ,

    , . , . . , , , .

    . , . , , . , ,

    z1 z2 z3 z4 00 01 101 100

    :

    100 00 01 101 101 101 00 z4 z1 z2 z3 z3 z3 z1

    ,

    z1 z2 z3 z4 00 01 101 010

    ( 01 010), -:

    00 01 01 01 010 101 z1 z2 z2 z2 z4 z3,

    00 010 101 010 101 z1 z4 z3 z4 z3

    00 01 010 101 01 01 z1 z2 z4 z3 z2 z2.

    , , , .

  • 9

    1.6.

    1.1 1. . 2. .

    : 1=0,22, 2=0,58, 3=0,01, 4=0,03, 5=0,16. 1.2 .

    : 1=1/8, 2=1/8, 3=1/8, 4=1/8, 5=1/4, 6=1/4.

    1.3 ,

    .

    1.4 ,

    nip= 2 , =1ip .

    (z1)=0,32 (z2)=0,26 (z3)=0,2 (z4)=0,12 1 (z5)=0,06 (z6)=0,02 (z7)=0,015 (z8)=0,005 (z1)=0,38 (z2)=0,32 (z3)=0,15 (z4)=0,1 2 (z5)=0,03 (z6)=0,02 (z1)=0,37 (z2)=0,25 (z3)=0,18 (z4)=0,1 3 (z5)=0,06 (z6)=0,04 (z1)=0,26 (z2)=0,21 (z3)=0,18 (z4)=0,11 4 (z5)=0,1 (z6)=0,08 (z7)=0,06 (z1)=0,24 (z2)=0,22 (z3)=0,16 (z4)=0,16 5 (z5)=0,12 (z6)=0,08 (z7)=0,02

  • 10

    2.

    2.1.

    , : , , , ; , .

    , , . , , , , .

    , , , , , , ( , ).

    , , , .

    , , . ( ), .

    . .

    : .

    ( k , ) n , k .

    , n .

  • 11

    . , . , , , () , .

    .

    , , . .

    2.2.

    , .

    ( ), . , , d.

    , 2. . . 2 , . () , d.

    1 0 0 1 1 1 1 1 0 1 ()=7

    1 1 0 0 0 0 1 0 1 0 ()=4

    0 1 0 1 1 1 0 1 1 1 ()=7, d=7.

    , , .

    , , .

    .

    , d=l . , n=3 :

    000, 001, 010, 011, 100, 101, 110, 111.

  • 12

    . , .

    d=2, . , , n=3:

    000, 011, 101, 110

    001, 010, 100, 111

    . r r, . ,

    .1min0 + rd (2.1) , r-

    .

    . , . n=3 , , 000 111. 000

    001, 010, 100, 000.

    111

    110, 011, 101, 111:

  • 13

    s

    1.s2dmin + (2.2)

    , s r (rs)

    1.srd min.. ++ (2.3)

    . , .

    , . , .

    2.3.

    . ,

    . , . . .

    , n . n- , n nn ,

  • 14

    , , . , . , . . , , .

    , .

    2. .

    2:

    0 0 = 0; 0 1 = 1; 1 0 = 1; 1 1 = 0.

    , , .

    : () , .

    1 2. 2.

    : .

    ( ) .

    , 2.

    , : 1100011 1001111

    1 1 0 0 0 1 1 1 0 0 1 1 1 1 0 1 0 1 1 0 0

    d = 3. , W = d.

    2 G G, a, b c ( ), a b. (ab)c = a(bc)

  • 15

    2.4. :

    , .

    , . n , , n () .

    nnn += (2.4) .

    , , . . n , , , n2 , n+1 .

    n .1n2 n + (2.5)

    , (2.4) .2222 nnnnn == + (2.6)

    (2.5), ( ) nn 21n2 + , (2.7)

    2n . ,

    ,

    ( )122

    nn

    +

    n . (2.8)

    , n2N = . n n. n, n n . 2.1.

    , , , . , 2i, i = 0, 1, 2, 3, ... . 1, 2, 4, 16, 32... (0 1), : . , .

  • 16

    . 2.1

    n n n n n n

    1 0 1 9 5 4

    2 0 2 10 6 4

    3 1 2 11 7 4

    4 1 3 12 8 4

    5 2 3 13 9 4

    6 3 3 14 10 4

    7 4 3 15 11 4

    8 4 4 16 11 5

    .

    . n =n+n a1, 2 . .:

    0001a1 00102 00113 01004 01015 01106 01117 1000a8 1001a9 101010 1011a11

    , : , (1, 3, 5, 7, 9, 11 . .); (2, 3, 6, 7, a10, a11 . .); . . , (. 2.2).

  • 17

    . 2.2

    -

    () -

    1 1, 3, 5, 7, 9, 11, ... 1

    2 2, 3, 6, 7, 10, 11, 14, 15, 18, 19, 22, 24, ... 2

    3 4, 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23, ... 4

    4 8, 9, 10, 11, 12, 13, 14, 15, 24, 25, 26, 27, 28, 29, 30, 31, 40, 41, 42, ... 8

    2.1.

    (n=4) 0101. . 2.3

    -

    1 1 02 2 1 3 0 0 4 3 0 5 1 1 6 0 0 7 1 1

    : . 2.1

    n = 3, n = 7. 1, 2, 4. . 2.3. . 2.2, 1, 2 3.

    : 1+3+5+7 , 1+0+1+1 1 = 0.

    : 2+3+6+7 , 2+0+0+1 2 = 1.

    : 4+5+6+7 , 3+1+0+1 3 = 0.

    . 2.3.

  • 18

    2.2. ,

    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. 110 = 6. , , .

    . 2.4

    ,

    - 3,

    5, 6 7

    1 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 1 0 2 0 1 0 1 0 1 0 1 3 1 0 0 0 0 1 1 1 4 1 0 0 1 1 0 0 1 5 0 1 0 0 1 0 1 1 6 1 1 0 0 1 1 0 0 7 0 0 0 1 1 1 1 0 8 1 1 I 0 0 0 0 1 9 0 0 1 1 0 0 1 1 10 1 0 1 1 0 1 0 0 11 0 1 1 0 0 1 1 0 12 0 1 1 1 1 0 0 0 13 1 0 1 0 1 0 1 0 14 0 0 1 0 1 1 0 1 15 1 1 1 1 1 1 1 1

    , 16 , . 2.4.

  • 19

    . , , . , , (. 2.4 8). , . , , .

    2.5. .

    , n n. n, n = n + n:

    nn1nnn2n1n

    n22221n22221

    n11211n11211

    PPPaaa

    PPPaaaPPPaaa

    C

    KK

    KKKKKKKK

    KK

    KK

    = (2.7)

    , , (n, k) ,

    k = n, , , .

    ( ). n, n.

    : a1 a2 a3 an P1 P2 Pn

    )nK(nKK

    )n3(n3231

    )n2(n2221

    )n1(n1211

    21

    PPP1000

    PPP0100PPP0010PPP0001

    =

    KK

    KK

    KK

    KK

    KK

    ,

    , .

    d0 = 2

  • 20

    1

    111

    1000

    010000100001

    11000

    101001001010001

    K

    KKKKK

    K

    K

    K

    K

    KKKKKK

    K

    K

    K

    ==

    , , .

    , n, n n. , n, n :

    ( ) ( )[ ]{ }[ ].1nlog1nlogn 22 +++= (2.8) .

    , . . n, :

    ( )[ ].1nlogn 2 += (2.9) 2.3. ,

    16 .

    : 1. n = 4 (16 = 24 = 2n),

    4. 2. n; n ,

    n + n, d0 = 3, [ ]{ } 38log5log5logn 222 ==+= .

    , , , 3, n + n = 4+3 = 7.

    3. 0 WdW ,

    , (d0 = 3, a W=1, ): 111; 110; 101; 011.

    4. :

    1101000101010001100101110001

    1 =

    1011000011010011000101110001

    2 =

  • 21

    1111000011010010100101100001

    3 =

    ,

    . , n, n d0, : .

    2.4. ,

    , , 2000 .

    : 1. ,11n,20002 n = (2.8), n=11 d0=3,

    ( ) ( )[ ]{ }[ ] .4111log111logn 22 =+++= 2. .

    15.151;12n;12 1115nn ===

    3. .2W,1dW 0 >

    4. n,

    .2W 5. :

    111110000000000011101000000000101100100000000001100010000000110100001000000010100000100000100000000010000111000000001000011000000000100101000000000010110000000000001

    =

  • 22

    , , 11, 11 ,

    1.dW 0n

    2.5. 120

    11- . () . , .

    :

    1. n=11 d0=3. (2.9),

    ( )[ ] .4111logn =+= 2.

    2 , . , , Wn=2, 3, 4 , , . .(0011,0100, 0110, 1010, 1100, 0111).

    3.

    11101000000001101000000101001000010010001000011000001001010000001011000000001

    =

    . n

    . : , , 2 , ,

  • 23

    , . . , .

    :

    k2k1kk

    nnnn2n1n

    n2n2221122

    n1n2211111

    PPPP..................................................

    ;PPPP

    ;PPPP

    =

    =

    =

    L

    L

    L

    (2.10)

    =

    == n

    1iiijnnij2j21j1ijPPPPP L

    2.6.

    :

    110101011111

    1000010000100001

    1101000101010001100101110001

    ==C

    : 1. n=4. ,

    N = 2n = 24 = 16.

    1) 0 0 0 0 5) 0 0 1 0 9) 0 0 0 1 13) 0 0 1 1 2) 1 0 0 0 6) 1 0 1 0 10) 1 1 0 0 14) 1 0 1 1 3) 0 1 0 0 7) 0 1 1 0 11) 0 1 0 1 15) 0 1 1 1 4) 1 1 0 0 8) 1 1 1 0 12) 1 1 0 1 16) 1 1 1 1

    2.

    2 , , .

  • 24

    1) 0 0 0 2) 1 1 1 3) 1 1 0

    5) 1 0 1

    9) 1 0 1

    3. :

    1) 0 0 0 0 0 0 0 5) 0 0 1 0 1 0 1 9) 0 0 0 1 0 1 1 13) 0 0 1 1 1 1 0 2) 1 0 0 0 1 1 1 6) 1 0 1 0 0 1 0 10) 1 0 0 1 1 0 0 14) 1 0 1 1 0 0 1 3) 0 1 0 0 1 1 0 7) 0 1 1 0 0 1 1 11) 0 0 0 1 1 1 0 15) 0 1 1 1 0 0 0 4) 1 1 0 0 0 0 1 8) 1 1 1 0 1 0 0 12) 1 0 0 1 1 0 0 16) 1 1 1 1 1 1 1

    ,

    :

    .n...,2,1,jS,in

    1iia*ijPiP ==

    = (2.11)

    , - . : 1 , , 2 , , . . n.

    S1, S2,..., Sn . , .

    , .

  • 25

    , . , - .

    , , I, . , . .

    n IH = (2.12)

    , H.

    2.7.

    1111000011010010100101100001

    =

    , .

    : 1.

    :

    111011101110

    100001000010

    001

    1111000011010010100101100001

    ==

    ,

    , ,

    34213

    14312

    14321

    SaaaPSaaaPSaaaP

    ===

    2. , S1, S2, S3 , , c , In, , . . 3. ,

  • 26

    a1 a2 a3 a4 P1 P2 P3

    101111011110

    =H100010001

    In , . .

    Sj=0, S2=1, S3=1, , 101, , , 001 . .

    3. n , 3, 4 5 3: 1100, 0010 1010. , :

    1.01011110P0;11P

    0;11101110P

    ===

    ==

    : 1 1 0 0 1 1 0; 0 0 1 0 1 1 0; 1 0 1 0 1 0 1.

    4. ,

    , . . :

    0 1 0 0 1 1 0; 0 0 1 1 1 1 0; 1 0 1 0 1 0 0. . ' =110, . . 1=1; 2=1; 3=0:

    1.0100aaaP1;0001aaaP0;0011aaaP

    4213

    4312

    4321

    ======

    0 1 1 , .

    3 , .

  • 27

    1.10001;11011;1101

    ===

    1 1 1 .

    1.00100;01100;0101

    ===

    001 .

    2.6. .

    ,

    . , . . , . .

    4 . , . , , . , .

    , , . ( ) , , , (, , ), . . . , , . . , 4 , , : ( + b) = + bc , b .

  • 28

    , (X+1), . . .

    (, ) , , , , .

    . ,

    ( ) 1101.1XXX 23 ++= , ,

    ( ) 1011.1XXX 3 ++=

    (X) , . n n, n . ,

    ( ) ( ) 1101000.XXXX1XXXX 356323n =++=++= ,

    . (X)Xn (X):

  • 29

    ( )( ) 1XX11XXX

    XKX

    323

    3

    ++++++=

    ( )( ) ( )

    ( )( )XKXRXQ

    XKXX n

    += , (2.13)

    Q(X) , R(X) (X) K(X). 1 1=0, 1=1,

    ( ), b=0 =b, b=0. , b 0, b 1, . . .

    (2.13)

    ( ) ( ) ( ) ( ) ( )XRXKXQXXXF n +== (2.14)

    R(X) (2.14)

    ( ) ( ) ( ) ( ) ( )XRXXXKXQXF n +== , (2.15)

    ( ) ( )( ) ( ) 1,X1XX1XX1XXXXF 323323 +++=+++++=

    ( ) 1101001.001110100010111111XF =+== 1101001 , 1101

    , 001 . , ( 1111) , , , ( 1101000)

  • 30

    ( 001).

    , , , 2, , , X+1.

    , , X , X , , . ,

    .XXX0X0X0X1X0X1101000;XXX0X0X0X0X1X0010100

    X;XX0X1X0X1X0X00010101;XX1X0X1X0X0X0000101

    35012345

    24012345

    3012345

    2012345

    +=++++++=++++++=++++++=+++++

    X:

    ( )( )( ) .101000XXXXX

    ;010100XXXXX;001010XXX1X

    3524

    243

    32

    +=+

    +=+

    +=+

    , X, . .

    2 , , X+1, 2:

    , .

  • 31

    .

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

    (2.15).

    , , , .

    2.8. 1011.

    :

  • 32

    : 1) 011 4) 101 7) 100 2) 110 5) 001 8) 011 3) 111 6) 010 9) 110 , .

    , , , . , (X). .

    , , 1dW 0 , d0 . , .

    . 2 .

    2.9. ,

    , ( ).

    : 1. , ,

    d0=3, , n=3, .

    2....

Recommended

View more >