АРИФМЕТИЧЕСКОЕ КОДИРОВАНИЕ СООБЩЕНИЙ С ИСПОЛЬЗОВАНИЕМ СЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

  • Published on
    05-Apr-2017

  • View
    223

  • Download
    0

Embed Size (px)

Transcript

  • 2008 2(2)

    519.72

    1

    ..

    . .. , .

    E-mail: vpotapov@math.nsc.ru

    ,

    . , -

    , -

    .

    : , , , -

    .

    , . - A . - f A . - .

    , , . .. [1, 2] - . , [3, 4]. [5].

    - . , , - (0,1) . -, , , .. [6, 7].

    A P A* A. - P(wa)=P(w), wa, aA, wA*, P(w) = 1, . - ( ), , . .P(a1, , an) = P(a1)P(an). I(w)= log P(w) wA

    * - (A, P). (., , [8]) , I(w) .

    . wAn - L(w)= P(x), xAn, , w, R(w) = L(w) + P(w). [0,1) - i(w) = [L(w), R(w)). i(w) P(w) - q(w) , , 2log P(w), . f(w) wAn

    1 ( 08-01-00671).

  • 132 ..

    q(w) log P(w), - . f An , |f(w)| I(w) + 1, . . . , f A*, w , P(w)/2. f , Cod(n) f(w) wAn, Cod , - |Cod(n)| = log n(1 + o(1)). -, , [8, 9].

    . x1, , xn, - (0,1). wAn. m -, i(w), .. xmi(w). w gx(w)=Cod(m). , gx A

    n. 1. 1, , , (0,1)

    . E|g(w)| I(w)(1+ o(1)) |w|.. A (0, 1). P(iA) = P(A) A

    i1, , n P(1, , n1A, nA) = (1 P(A))n1P(A). m

    A (0, 1), i , , iA.

    E(m) = 1

    1

    (1 ( )) ( ) 1/ ( ).n

    n

    n P A P A P A

    =

    = log t , E(log m) log(E(m)).

    A = i(w). E|g(w)| = E|Cod(m)| = (1+o(1))E(log m) (1+o(1)) log (E(m)) = I(w)(1+o(1)) |w|. .

    f, g . , 1 , - I(w).

    - . -. B = 2A A. w = a1an W = b1bn, aibi i = 1 n. - F B* , : () Fo , A, Fo(F(W)) WB*. , , . - (B, P), P B.

    [7] ( ) -. , , ( )( )min ( ) log ( )

    b B a b

    H P b Q a

    = , -

    Q A, -, . . WB*. - bB (B, P) ( ) log ( )

    a b

    I b Q a

    = , I(W)

    W = b1bn I(bi). Q , H. wAn

    i(w) Q. WB* i(W) = i(w), wA*, - WB*. x1, , xn, (0,1). m , i(W), .. xmi(W). W - Gx(W) = Cod(m). , Gx B

    n. 2. 1,, , (0,1)

    . E|G(W)| I(W)(1+ o(1)) |W|. 2 1. [7] , -

    .

  • 133

    1. Rissanen J. Generalized Kraft inequality and arithmetic coding // IBM J. Res. Develop. 1976. V. 20. No. 3. P. 198 203. 2. Rissanen J., Langdon G. Universal modelling and coding // IEEE Trans. Inform. Theory. 1981. V. IT-27. No. 1. P. 12 23. 3. .., .. // . 1999. . 35. . 4. C. 95 108.

    4. Witten I.H., Neal R.M., Cleary J.G. Arithmetic coding for data compression // Commun. ACM. 1987. V. 30. No. 6. P. 520 540.

    5. .. // :. II. .: - -

    , 2001. . 59 70.

    6. .. // . . 2006. . 140. 1. . 321 325.

    7. .. // . . 4. .: -, 2004. . 385 399.

    8. .. . . : . , 1999.

    9. .. // -. .: , 1968. . 20. . 173 179.

Recommended

View more >