Microsoft Word - xdmm fm.doc

Transcription

1 科学出版社职教技术出版中心

2 普通高等教育 十一五 国家级规划教材高等院校信息科学系列教材 信息论与编码理论 ( 第二版 ) 沈世镒陈鲁生编著 北京

3 内容简介 本书主要介绍信息论和编码理论的基本内容, 其特点是简明扼要, 可读性强, 既具有较严谨的数学描述与推导, 又注意到信息论的实用背景, 其中许多典型问题已在通信工程中得到实际应用. 全书共分 2 章. 主要内容包括 : 信息的度量 信源编码 信道编码定理 编码理论中用到的基本抽象代数知识 编码理论的基本概念和基本问题 线性码 Hamming 码 循环码 BCH 码 Reed-Solomon 码 Golay 码 Reed-Muller 码 平方剩余码 Goppa 码以及信息论和编码理论的应用. 本书每章末均附有习题, 其中部分习题是对正文内容的补充. 本书可作为高等院校信息科学专业 计算机科学专业 通信专业以及相关专业的本科生教材, 也可供相关领域的研究生 教学与科研人员, 以及工程技术人员参考. 图书在版编目 (CIP) 数据信息论与编码理论 / 沈世镒, 陈鲁生编著. 2 版. 北京 : 科学出版社, 200 ( 普通高等教育 十一五 国家级规划教材 高等院校信息科学系列教材 ) ISBN Ⅰ. 信 Ⅱ. 沈 2 陈 Ⅲ. 信息论 - 高等学校 - 教材 2 信源编码 - 编码理论 - 高等学校 - 教材 3 信道编码 - 编码理论 - 高等学校 - 教材 Ⅳ. TN9.2 中国版本图书馆 CIP 数据核字 (200) 第 号 责任编辑 : 鞠丽娜 / 责任校对 : 柏连海责任印制 : 吕春珉 / 封面设计 : 三函设计 北京东黄城根北街 6 号邮政编码 : 出版 印刷 科学出版社发行 各地新华书店经销 * 2002 年 7 月第 一 版 开本 : B5( ) 200 年 0 月第 二 版印张 : 年 0 月第八次印刷字数 : 印数 : 定价 : 元 ( 如有印装质量问题, 我社负责调换 科印 ) 销售部电话 编辑部电话 (HI08) 版权所有, 侵权必究 举报电话 : ; ; 科学出版社职教技术出版中心

4 998,,, 280,,, ,, 200,,,,,,,,,,,,,,,, ( ),

5 8, 7, ,,.,,..,.,,.,.,,,.,,,.,..,.. 科学出版社职教技术出版中心 200 6

6 ,,,.,.,.,???.,.,..,..,., Shannon,,., Shannon Shannon.,,...,,.,...,,.,.,,...., Shannon, Shannon,.,.

7 vi ( ), ( ). ( ),.. ( ).,. 5. 5, 6, 7 9 Hamming, 0 BCH Reed-Solomon.,., Shannon, Shannon, (, )., Shannon,. 2.,,. 2,,,., 3. 3.,.,. 2,.,,.,.,...,,. 科学出版社职教技术出版中心

8 Shannon

9 viii ( ) Fano Jenson Shannon Shannon 科学出版社职教技术出版中心 Kraft Huffman Huffman Huffman Huffman

10 ix 3.5. Huffman Huffman (Gaussian)

11 x ( ) Hamming Hamming Hamming Hamming Hamming Hamming Hamming 科学出版社职教技术出版中心 BCH Reed-Solomon BCH Reed-Solomon BCH Reed-Solomon Reed-Solomon

12 xi Golay Reed-Muller Reed-Muller Goppa

13 ,,,.,...,,,.,...,..,....,.,.,. 20,.,.,, ( ),,.,,., ,.. 科学出版社职教技术出版中心,. Morse Bodo..,

14 2 ( )., Morse Bodo.,,. 2.,.,.,.,,.,.,. ( ),,, , H. Nyquist L. Hartley,,. Shannon. 3. Shannon 20 40, N. Wiener E. Fisher C. E. Shannon,.,.,. 4.,.,,....2 Shannon 948 C. E. Shannon, ,,,.,. ( )., Shannon,.,

15 3.. Shannon , Shannon,. Shannon ; ; ; ;..,., Shannon. (20 70 ) B. McMillan, A. Feinstein(958), Robert G. Gallager(968), J. Wolfowitz(978). Shannon,.,, A. N. Kolomogolov, A. Y. Xinqing, M. S. Pinsker, R. L. Dobrushin, A. N. Kolomogolov M. S. Pinsker, A. Y. Xinqing, R. L. Dobrushin,.,,.,., Shannon. Shannon,.,.,.,. W. W. Peterson(96) Robert M. Fano(96)., Wozencraft-Reiffen(96).,. 2. Shannon 科学出版社职教技术出版中心 ,. Shannon

16 4 ( ), Shannon, ,.,.....3,.... Shannon,,. 2. Shannon Kolomogolov, Hausdorff,. Shannon Kolomogolov Hausdorff,.,.,. 3.,,,.,. ( ),... ().,

17 5, Fisher Kullback-Laiber.., EM ACI Ying-Yang. S. Amari,. (2). T. Cover,,. (3).,.,.,...4 Shannon,, ,.,.., BCH Reed-Solomon,.,, Viterbi, G. Ungerbock 982 Gaussian.,, 200bit/s 30000bit/s. 30,. 3. 科学出版社职教技术出版中心..,

18 6 ( ), T. Berge, ,,,.,, 50: 60:.,. 90, IT,, JPEG(joint photographic experts group) MPEG.,,.,. 2,.,,.. 4.,,.., ; ;.,.,., ,.,,...,

19 7.,..2,..2..,..,., ;.,.,,. Shannon,,,. Shannon 948,.,,,.,...,,. Shannon Shannon.,.. Shannon.., Shannon,, Shannon., Shannon.,. 科学出版社职教技术出版中心

20 8 ( ) ,,.. 2..,,..,.,.,.,,. 3.,, ,. 6...

21 9.2.3,,., (, ).,, ( ).,,.,.,.,.,,,.,,.,.,,.,..,,,.,.,,..,.,,,,..2.4,.,.. 科学出版社职教技术出版中心,.,. 26,.,,,.,,

22 0 ( ), A H 0.06 O V 0.00 B 0.05 I P 0.09 W C J Q 0.00 X 0.00 D K R Y E 0.27 L S Z 0.00 F M T 0.09 G N U , S = [X, p(x)], X,, x X, p(x) x., x X, p(x) 0, x X.2. p(x) =., S = [X, p(x)], X ( ) ( ) , S = [X, p(x)], X ( ASCII )

23 ;. U V, u U v V, p(v u), u, v., p(v u) 0, p(v u) =, u U v V..2.2 v V C = (U, p(v u), V), U V, p(v u) ,. Y, X U V Y, f g, f(x) : X U, g(v) : V Y., U V, , E = {S, C} = {X, p(x), U, p(v u), V}. (.2.) E, f g,, E(f, g) = {S, C, (f, g), Y} = {X, p(x), U, p(v u), V, (f, g), Y}. (.2.2) 5.,. ξ S = (X, p(x)) ; ξ ; η ; η. 科学出版社职教技术出版中心 (.2.3)

24 2 ( ) ξ S = [X, p(x)], X, p(x)..2. E(f, g), ( ξ, ξ, η, η), p(x, u, v, y) = p(x)f(u x)p(v u)g(y v), (.2.4) p(x) p(v u) S C, f(u x) = {, u = f(x), 0, u f(x), g(y v) = {, y = g(v), 0, y g(v). (.2.5), ( ξ, ξ, η, η) (Markov), ξ, ξ ( η), η, ( ξ, ξ) η..2.5 ( ξ, ξ, η, η) (.2.4), ( ξ, ξ, η, η) E(f, g). ( ξ, ξ, η, η), ξ ξ η η..2., p(x, u, v, y) = Pr{( ξ, ξ, η, η) = (x, u, v, y)}, p(x) = Pr{ ξ = x}, p(v u) = Pr{η = v ξ = u}, (.2.6) P r (A) A, P r (A B) A B. p(a) = P r (A), p(a B) = P r (A B)..2.5,.,.. E n = {S n, C n } = {X n, p (n) (x (n) ), U n, p (n) (v (n) u (n) ), V n }, (.2.7)

25 3 X n, U n, V n, X n = {x (n) = (x, x 2,, x n ) xj X, j =, 2,, n} (.2.8) X n. U n V n., p (n) (x (n) ) p (n) (v (n) u (n) ) X n U (n) V n. { f (n) = f (n) (x (n) ) : X n U n, g (n) = g (n) (v (n) ) : V n Y n. (.2.9) E n (f (n), g (n) ) = {E n, f (n), g (n) )} = {S n, C n, f (n), g (n) )}. (.2.0) 2. E (n) (f (n), g (n) ), ( ξ (n), ξ (n), η (n), η (n) ), p (n) (x (n), u (n), v (n), y (n) ) = p (n) (x (n) )f (n) (u (n) x (n) )p (n) (v (n) u (n) )g (n) (y (n) v (n) ), p (n) (x (n) ) p (n) (v (n) u (n) ) S (n) C (n),.. f (n) (u (n) x (n) ) = g (n) (y (n) v (n) ) = {, u (n) = f (n) (x (n) ), 0, u (n) f (n) (x (n) ), {, y (n) = g (n) (v (n) ), 0, y (n) g (n) (v (n) ). ξ (n) ξ (n) η (n) η (n) (.2.) (.2.2) 科学出版社职教技术出版中心..3.

26 4 ( ).3..,,.,.,,, Hamming BCH Reed-Solomon.,., ; ;.,,.,..,.,,,.,,..3.2,,, ( ) ( ),.. C. H. Shannon 948.., T. M. Cover J. A. Thomas 99.,.,.. A. Feinstein R. G. Gallager. A. Feinstein, Shannon,. R. G. Gallager

27 5, A. N. Kolomogolov R. L Dobrushin. A. N. Kolomogolov, R. L Dobrushin. 2., Richard E. Blahut., J. H. van Lint Shu Lin. J. H. van Lint Shu Lin,,. 3. () M. S. Pinsker,.,. Kullback Laiber, Kullback-Laiber,,., J. Aczel Z. Daroczy.,. (2) J. Wolfowitz,.. I. Ceiszar J. Koruer.. (3) T. Berger,,. (4) G. Ungerboeck.. T. Cover R. E. Blahut. (5) S. Amari. S. Amari,.,. (6).. 科学出版社职教技术出版中心

28 6 ( ) 4.,., , X R., x X. 2.,, X n, x (n), a n. X n X n, x (n) n, a n a n., x i. x (n) = (x, x 2,, x n ), x i X X n. X n n x (n). n x (n), x (n) = x x 2 x n., x (n) = (x, x 2,, x n ) x (n) = x x 2 x n., (p, p 2,, p n ). p = (p, p 2,, p n ). 3.,, S n, n =, 2, 3,,, S n.. 4.,,..,,, H(ξ), H( p), H(p, p 2,, p n ), ξ p = (p, p 2,, p n ).

29 7, P r (A) p(a) A, p(x i ) p i ξ x i..??.2??.3..4,,,,,..5 E(f, g). () S, X = {0, }, p(0) = p() = 2. (2) C, U = V = {0, }, (3) f g p(0 ) = p( 0) = p, p(0 0) = p( ) = p. f() = g() =, f(0) = g(0) = 0. ( ξ, ξ, η, η)..6??.7??..8 : E(f, g), ξ ξ η η. 科学出版社职教技术出版中心

30 2 Shannon,.??? ξ, X = { } x, x 2,, x a, a. x i X, ξ x i p i = p(ξ i ) = Pr{ξ = x i }, i =, 2,, a. (2..), ξ ( x x 2 x a ξ p = p p 2 p a ), (2..2) ξ, p = (p, p 2,, p a ) ξ, a p i 0, i =, 2,, p i =., i {, 2,, a} p i =, p j = 0(j i), ξ x i,,.,.,,,.

31 2 9,, ξ x x 2 x a a a a,, a.,, H(ξ) = H( p) = H(p,, p a ). (2..3) (2..3), ξ, p (p, p 2,, p a )., { P = p = (p, p 2,, p a ) pi 0, i =, 2,, a, } a p i =, (2..4) X., H( p) P, a =, 2, 3,.,. () H(p,, p a ) (p, p 2,, p a ). (2) a, ( H a, a,, ) a ( < H a +, (3) b i, i =, 2,, k, ) a +,,. a + k b i = a, ( H a,, ) ( b = H a a,, b ) k + a (3) k 科学出版社职教技术出版中心 ( b i a H,, ). b i b i (3).,,. (3), a, k, b i i. (3)

32 20 ( ) k,., ( 3 ), = +. ( 3 ). ( 3 ), H () (3) H(p,, p a ) = a p i log c p i, (2..5) c > 0, log c c., 0 log c 0 = 0. (2..5) () (3),. b a, b a. a b = k, b i = b, i =, 2,, k,, b i = bk = a. (3) ( H a,, ) ( b = H a a,, b a ( b = H a,, b a ) + ) + H a = b s, s, ( H b s,, ) ( b s = H b s,, ( g(a) = H a,, ), a b s b s g(b s ) = g(b s ) + g(b), g(b s ) = sg(b)., (2) g(a), g(b s ) < g(b s+ ). k ( b a H b,, ) b ( b,, ). b ) ( + H b,, ). b

33 2 2, sg(b) < (s + )g(b). g(a). r t, s b s r t < b s+. (2..6) g, (2..6), g(a s ) g(r t ) < g(b t+ ), sg(b) tg(r) < (t + )g(b), s t g(r) g(b) < s +. t (2..6) s log b t log r < (s + ) log b, t t, s t log r log b < s +. (2..7) t g(r) g(b) log r log b < t. g(r) g(b) = log r log b, g(r) log r = g(b) log b., r, g(r)/ log r,, g(r) = c log r. g(r) > 0, c > 0., c =, r, g(r) = log a r. 科学出版社职教技术出版中心

34 22 ( ) (3), ( b H a,, b ) k k = g(a) a = log a a = p,, p k k b a,, b k a, k b i a g(b i) b i a log b i a a. b i a log a b i a, p,, p k, H(p,, p k ) = k p i log c p i. (2..8), H, p,, p k. lim p log p = 0, p 0 + (2..8) p,, p k. 3.,. 2.. H(ξ) H( p) ξ p = (p,, p a ), H(ξ) = H(p,, p a ) a = p i log c p i = a p i log c p i., ξ,., H(ξ) log c. E (g(ξ)) p(ξ) g(ξ)., ( ) H(ξ) = E log c, p(ξ)

35 2 23 p(ξ) ξ x p(x)., log c p(ξ). Clausius 864, C. E. Shannon 948, Shannon.. Shannon. a. c = 2, e, 3, 0, ( bit, nat, tet, det)., log c x = log b x log b c., c = 2, log 2 x = log x. c = e, log e x = ln x Shannon H(p,, p a ) 2.. Shannon, (). H(p,, p a ) (p, p 2,, p a ), (p,, p a ),. σ {, 2,, n}. H(p,, p a ) = H(p σ(),, p σ(n) ), (2). p = (p,, p a ), H(p,, p a ) 0, p. Shannon, p, H( p) = 0., H( p) = 0, p i = 0, n p i =, i p i =, p j, p. 科学出版社职教技术出版中心 2.. p i = 3 X = {x, x 2, x 3 }, ( H 3, 3, ) = 3 3 log log 3 + log 3 = log p = p 2 = 4 p 3 = 2 X = {x, x 2, x 3 }, ( H 4, 4, ) = 2 4 log log 4 + log 2 =.5. 2

36 24 ( ) 2..2 ξ, p(ξ = ) = p, p(ξ = 0) = p, H(ξ) = p log p ( p) log( p) def = H(p). H(p), ,.,. 2.2., ξ,, (ξ, η). p ξ,η (x, y) (ξ, η), p ξ,η (x, y) = Pr{(ξ, η) = (x, y)} = Pr{ξ = x, η = y}, (2.2.) η Y, Y y, H(ξ, η) = x X p ξ,η (x, y) log p ξ,η (x, y), (2.2.2) η Y H(ξ, η) = E ξ,η (log p(ξ, η)),

37 2 25 E ξ,η (g(ξ, η)) g(x, y) ξ, η, E ξ,η (g(ξ, η)) = p ξ,η (x, y)g(x, y). x X y Y p ξ,η (x, y) (ξ, η), p ξ (x) = p ξ,η (x, y), y Y p η (y) = x X p ξ,η (x, y), ξ, η, p η ξ (y x) = p ξ,η(x, y), p ξ (x) p ξ (x) 0, p ξ η (x y) = p ξ,η(x, y), p η (y) p η (y) 0, η ξ ξ η., p ξ,η (x, y), p ξ (x), p η (y), p η ξ (y x), p ξ η (x y) p(x, y), p(x), q(y), q(y x), p(x y), p(x, y) = p(x)q(y x) = q(y)p(x y) (ξ, η) p(x, y), η ξ H(η ξ) = x X ξ η p(x)h(η ξ = x) = p(x) p(y x) log q(y x) x X y Y = p(x, y) log q(y x) x X y Y = E ξ,η (log q(η ξ)). 科学出版社职教技术出版中心

38 26 ( ) H(ξ η) = q(y)h(ξ η = y) y Y = p(x, y) log p(x y) x X y Y = E ξ,η (log p(ξ η)) H(ξ η) 0, ξ η, p(x y) y Y, q(y) > 0, p(x y). 2.., H(ξ, η) = H(ξ) + H(η ξ) = H(η) + H(ξ η). H(ξ, η) = p(x, y) log p(x, y) x X y Y = p(x, y) log p(x)p(y x) x X y Y = p(x, y) log p(x) p(x, y) log p(y x) x X y Y x X y Y = p(x) log p(x) p(x, y) log p(x, y) x X x X y Y = H(ξ) + H(η ξ).. log p(x, y) = log(q(y)p(x y)) = log q(y) + log p(x y), ,., (ξ, η) H(ξ, η) H(ξ), η ξ ( η ξ ) (ξ, η, ζ),,. H(ξ, η ζ) = p(x, y, z) log p(x, y z) x X y Y z Z

39 2 27 = H(ξ ζ) + H(η ξ, ζ) = H(η ζ) + H(ξ η, ζ) ξ, ξ 2,, ξ n n p(x, x 2,, x n ), n H(ξ, ξ 2,, ξ n ) = H(ξ i ξ i,, ξ ). H(ξ, ξ 2,, ξ n ) = 2.2. p(x,, x n ) = n p(x i x i,, x ), x,x 2,,x n p(x, x 2,, x a ) log p(x, x 2,, x n ) = x,x 2,,x n p(x, x 2,, x n ) log = x,x 2,,x n n p(x i x i,, x ) n p(x, x 2,, x n ) log p(x i x i,, x ) n = p(x, x 2,, x n ) log p(x i x i,, x ) x,x 2,,x n n = p(x, x 2,, x i ) log p(x i x i,, x ) x,x 2,,x i n = H(ξ i ξ i,, ξ ). (ξ, η) Σ Σ 科学出版社职教技术出版中心

40 28 ( ) ξ η, ( 2, 4, 8, ) (, 8 4, 4, 4, ). 4 H(ξ) = = 7 4, H(η) = = 2,, H(ξ, η) = = H(ξ η) = H(ξ, η) H(η) = = 9 8, H(η ξ) = H(ξ, η) H(ξ) = = 8. H(η ξ) H(ξ η), H(ξ) H(ξ η) = H(η) H(η ξ). 2.3, ,.,, x > 0, ln x x. x f(x) = x ln x, x > 0. f (x) = x, f (ξ) = > 0, x2 f(x), x =,, x > 0, f(x) f() = 0, x ln x, x =., x = y, y > 0, y ln y.

41 p i 0, q i 0, i =, 2,, a, a q i, a p i log p i a a p i log q i, p i log p i q i 0, p i = q i, i =, 2,, a log q i p i = (log e) ( ln q ) ( ) i qi (log e), p i p i a p i = = a p i log q i p i (log e) ( a ( ) ) qi p i = 0, p i q i =, i =, 2,, n. p i u i > 0, v i > 0, i =, 2,, a, a i =, 2,, a , u i log u i v i u i v i = p i = ( a ) u i log a u i, a v i u i, a u k k= a u i, a v i 科学出版社职教技术出版中心

42 30 ( ). q i = v i, a v k k=, ξ, X = {x,, x a }, H(ξ) log a, i p(x i ) = a , (u,, u a ) = (p,, p a ) ξ, v i =, i =, 2,, a, a H(ξ) = p i log p i ( a ) u i log ( a ) p i log = log a , i p i = a q ij, j =, 2,, k i, i =, 2,, a,, k i a q ij 0, p i = q ij, p i =. j= j =, 2,, k i, i =, 2,, a, H(q, q 2,, q k, q 2, q 22,, q 2k2,, q a, q a2,, q aka ) a ( qi = H(p, p 2,, p a ) + p i H,, q ) ik i. p p i a a a a u i v i p i

43 2 3, H(q, q 2,, q k, q 2,, q 2k2,, q a,, q aka ) a k i = q ij log q ij = = j= a k i j= a p i log p i q ij log( q ij p i p i ) a = H(p, p 2,, p a ) + p i k i q ij log q ij p i a j= p i ( qi p i H,, q ) ik i. p p i f X Z, H(ξ) H(f(ξ)). f -, x, x X, p(x) 0, p(x ) 0, f(x) f(x ). Z 0 = { f(x) x X } f. Z 0 = {z, z 2,, z b }, A i = { x f(x) = zi }, z i f. A i i =, 2,, b A i = {x i, x i2,, x iki }, q ij = p(x ij ), j =, 2,, k i, i =, 2,, b, k i p i = q ij, i =, 2,, b, j= q ij, p i 2.3.2, H(ξ) = H(q,, q k,, q b,, q bkb ), H(f(ξ)) = H(p, p 2,, p b ) H(ξ) H(f(ξ)), b ( qi p i H, q i2,, q ) ik i = 0, p i p i p i 科学出版社职教技术出版中心

44 32 ( ) p i = 0 q ij p i k i = 0, j= q ij = p i, j q ij p i =, f Fano Fano (Fano ) X, p(x, y). p e = Pr{ξ η}, ξ η, H(ξ η) H(p e ) + p e log( X ), X X, H(p). p e = Pr(ξ η) = x y p(x, y),, H(ξ η) = x y p(x, y) log p(x y) x=y p(x, y) log p(x y) p(x, y) p(y) p(x, y) p(y) = p(x, y) log p(x, y) log x y x=y ( ) p(x, y) ( X ) log x y p(x, y) + p(x, y) log p(x, y) = p e log ( X ) p e x y = p e log p e + ( p e ) log = H(p e ) + p e log( X ), x=y + ( p e ) log ( p e ) ( p e ) + p e log( X ) x=y ,,.,.

45 p(x), q(x) X, a H(p q) = p(x) log p(x) q(x). 0 log 0 = 0,, x X, p(x) = 0, q(x) > 0, 0 H(p q) =. Kullback-Leibler (Divergence), Kullback- Leibler., Shannon., H(p q) 0, p(x) 0 x p(x) = q(x)., ξ η, p(x, y), p(x) q(y), ξ η I(ξ; η) 2.4. I(ξ; η) = H(p(x, y) p(x)q(y)) = p(x, y) p(x, y) log p(x)q(y) x X y Y { } p(ξ, η) = E ξ,η log. p(ξ)q(η) I(ξ; η). (). I(ξ; η) = I(η; ξ). (2). I(ξ; η) = H(ξ) + H(η) H(ξ, η), I(ξ; η) = H(ξ) H(ξ η), I(ξ; η) = H(η) H(η ξ). (3). ξ, η, I(ξ; η) 0, ξ η. 科学出版社职教技术出版中心

46 34 ( ) (4) f Y Z, I(ξ; η) I(ξ; f(η)), f -. (5) I(ξ, ξ) = H(ξ)., (4) 2.3.3, , ξ η ζ I(ξ; η ζ) = H(p(x, y z) p(x z) p(y z)) ) p(ξ, η ζ) = E ξ,η,ζ (log p(ξ ζ)p(η ζ) p(x, y z) = p(x, y, z) log p(x z)p(y z). (x,y,z) X Y Z (ξ, ξ 2,, ξ a ) η, I((ξ, ξ 2,, ξ a ); η) = a I(ξ i ; η ξ i, ξ i 2,, ξ ). I((ξ, ξ 2,, ξ a ); η) = H(ξ, ξ 2,, ξ a ) H(ξ, ξ 2,, ξ a η) a a = H(ξ i ξ i,, ξ ) H(ξ i ξ i,, ξ, η) = a I(ξ i ; η ξ, ξ 2,, ξ i ) () a = 2, I(ξ; (η, ζ)) = I(ξ; η) + I(ξ; ζ η).. (2) (ξ, η, ζ), I(ξ; (η, ζ)) I(ξ; ζ). ξ η ζ.

47 2 35 (3) I(ξ; η ζ) = H(ξ ζ) + H(η ζ) H(ξ, η ζ), = H(ξ ζ) H(ξ η, ζ), = H(η ζ) H(η ξ, ζ). () (2) (), I(η; ζ ξ) 0, ξ ζ η,, ξ η ζ. (3). H(ξ), H(η), H(ξ, η), H(ξ η), H(η ξ) I(ξ; η) I(ξ; η) ξ η , I(ξ; η) = H(ξ) H(ξ η) = H(η) H(η ξ) = , (a, b) 0 λ, 科学出版社职教技术出版中心 g(x) (a, b), x, x 2 g(λx + ( λ)x 2 ) λg(x ) + ( λ)g(x 2 ). (2.5.) λ = 0 λ =, x = x 2, g. 2.5.,, ( ). g ( ), g ( ).

48 36 ( ),.,. x 2, x, e x, x log x. x, log x. ax + b.,., ( ). g ( ), g g x 0, g(x) = g(x 0 ) + g (x 0 )(x x 0 ) + g (x ) (x x 0 ) 2, 2 x x 0 x. g (x ) 0, x. x 0 = λx + ( λ)x 2, x = x,, x = x 2, g(x ) g(x 0 ) + g (x 0 )( λ)(x x 2 ). (2.5.2) g(x 2 ) g(x 0 ) + g (x 0 )λ(x 2 x ). (2.5.3) λ (2.5.2) λ (2.5.3),, , x 0, x 2, x, e x, x log x, x, log x. g(x) = x log x, g (x) = + log x, g (x) = x > 0, Jenson, E( )., E(ξ) = p(x)x. x X, E(ξ) = xf(x)dx (Jenson ) g, ξ, E(g(ξ)) g(e(ξ)). g, ξ.

49 2 37., p g(x ) + p 2 g(x 2 ) g(p x + p 2 x 2 ). k. i =, 2,, k, p i = p i/( p k ), p i, i =, 2,, k, k k p i g(x i ) = p k g(x k ) + ( p k ) p ig(x i ) p k g(x k ) + ( p k )g ( k ) p ix i ( ) k g p k x k + ( p k ) p ix i ( k ) = g p i x i,,. ξ,,,.,,.. X, P = { p = p(x) x X, p(x) 0, p(x) = } x X X, H( p) H(p q) P ( ) () H( p) P., 0 λ, p, p 2 P, H(λ p + ( λ) p 2 ) λh( p ) + ( λ)h( p 2 ). λ = 0, p = p 2. (2) q, H(p q) p. p, H(p q) q. p log p, p log p, log q 0 p, q Jenson,. 科学出版社职教技术出版中心

50 38 ( ) 2.6,., Shannon 2.6. ξ, R = (, ) ( R X ), ξ. F (x) = Pr{ξ x}, x R. F (x), ξ. F (x), f(x) = F df (x) (x) = ξ. dx, f(x) 0, x X, f(x)dx =. (2.6.), f(x) (2.6.), ξ, f(x) f(x) ξ H(ξ) H(ξ) = f(x) log f(x)dx. (2.6.2) 0 log 0 = ( ) X, 0 a., 0 a /a, 0. H(ξ) = a 0 a log dx = log a. a, a <, log a < 0,., ( ) ξ p λ (x) = λe λx, x, λ 0, H(ξ) = = λ 0 0 = log λ. p λ (x) log p λ (x)dx e λx (log λ λx)dx

51 ( ) ξ N(µ, σ 2 ), N(µ, σ 2 ) µ, σ 2, ( ) φ µ,σ 2(x) = exp (x µ)2 2πσ 2 2σ 2. ξ R, x R, φ µ,σ 2(x) 0, E{ξ} = xφ µ,σ 2(x)dx = µ, V {ξ} = E{(ξ µ) 2 } = H(φ µ,σ 2) = = = E{ξ2 } 2σ 2 (x µ) 2 φ µ,σ 2(x)dx = σ 2. φ µ,σ 2(x) log φ µ,σ 2(x)dx φ µ,σ 2(x) ( x2 2σ 2 log ) 2πσ 2 dx + log 2πσ2 2 = 2 + log 2πσ2 2 = 2 log(2πeσ2 ) Shannon ξ (n) = (ξ, ξ 2,, ξ n ), R n X, f(x (n) ). ξ (n) Shannon H(ξ (n) ) = f(x (n) ) log f(x (n) )dx (n), (2.6.3) dx (n) = dx dx n ( ) p(x (n) ) = X 科学出版社职教技术出版中心 ξ (n) = (ξ, ξ 2,, ξ n ) n, ( (2π)n Σ exp ( x (n) µ (n)) ( Σ x (n) µ (n)) ), (2.6.4) 2 Σ (σ ij ), A A A, Σ Σ, x (n) = (x, x 2,, x n ), µ (n) = (µ, µ 2,, µ n ),

52 40 ( ) µ i = x i p(x (n) )dx (n) R n ξ i, σ ij = (ξ i µ i )(ξ j µ j )p(x (n) )dx (n) R n ξ i ξ j. (2.6.3) n N(µ (n), σ) A = (a ij ), z (n) = (z, z 2,, z n ), z (n),. n a ij z i z j 0. i,j= n a ij z i z j > 0, i,j= Σ,, z (n), n n ( ) σ ij z i z j = (x i µ i )(x j µ j )p(x (n) )z i z j dx (n) i,j= i,j= R n n = (x i µ i )(x j µ j )p(x (n) )z i z j dx (n) R n = R n = R n 0. i,j= n (x i µ i )(x j µ j )z i z j p(x (n) )dx (n) i,j= ( n ) 2 (x i µ i )z i p(x (n) )dx (n), Σ, µ (n) = (µ, µ 2,, µ n ), ξ (n) = (ξ, ξ 2,, ξ n ), N(µ (n), Σ) ( ) N(µ (n), σ). ξ ξ n, H(ξ (n) ) = p(x (n) ) log p(x (n) ) dx(n)

53 ( = E = E log ) p(ξ (n) ) ( 2 log(2π)n Σ (ξ (n) m (n)) Σ ( ξ (n) m (n)) ) = 2 log(2π)n Σ + 2 E ( ( ξ (n) m (n)) Σ ( ξ (n) m (n)) ), ( ( = E ξ (n) µ (n)) ( Σ ξ (n) µ (n)) ) n = E (ξ i µ i )Σ ij (ξ j µ j ) = = = n, n i,j= n i,j= i,j= Σ ij E ((ξ i µ i )(ξ j µ j )) Σ ij Σ ij Σ = (σ ij ) Σ = (σ ij )., n j= σ ij σ i j = δ ii = {, i = i, 0, i i. H(ξ (n) ) = 2 log ((2π)n Σ ) + n 2 = n 2 log(2πe Σ /n ). () , Shannon. ξ 0 a, H(ξ) = log a, 0 < a <, H(ξ) < 0., Shannon. Shannon Shannon. Shannon.. (2) 2.6.5, Shannon.,, H(ξ (n) ) ξ (n). 科学出版社职教技术出版中心

54 42 ( ) (ξ, η), p(x, y), p(x) p(η). p(x, y) H(ξ η) = p(x, y) log H(η ξ) = p(x, y) log I(ξ; η) = p(x, y) log p(y) dxdy; p(x, y) p(x) dxdy; p(x, y) p(x)p(y) dxdy.,., 2.3., I(ξ; η) =, , µ (2) = (µ, µ 2 ), = = 0. ( p(x, y) log p(x)p(y) p(x, y) ( p(x, y) p(x)p(y) p(x, y) (p(x, y) p(x)p(y)) dxdy ) dxdy ) dxdy (ξ, η) N(µ (2), Σ), Σ = ( σ σ 2 σ 2 σ 22, ξ N(µ, σ ), η N(µ 2, σ 22 ). I(ξ; η) = H(ξ) + H(η) H(ξ, η) = ( log(2eπσ ) + log(2eπσ 22 ) log ( (2eπ) 2 (σ σ 22 σ 2 σ 2 ) )) 2 = ( ) 2 log σ σ 22 σ σ 22 σ 2 σ 2 = log ρ, 2 ). ρ = σ σ 22 σ 2 σ 2 σ σ 22 = σ 2σ 2 σ σ 22.

55 2 43, 0 σ 2 2 σ σ 22., 0 ρ = σ2 2 σ σ 22. ξ η, σ 2 = 0., ρ =, I(ξ, η) = ,,,,., X = {x, x 2,, x a }, X ξ, log a, ξ X p(x i ) = /a,.. ξ, f(x), H(f) = b a f(x) log f(x)dx.,, H(f) ξ X = (a, b), A- : b a f(x)dx =. A-, H(f). Lagrange b b L(f) = f(x) log f(x)dx + λ f(x)dx. a a δl(f) δf = ( + log f) + λ = 0. f 0 (x) = e λ = b a,, λ = + log (b a). b H(f 0 ) = log (b a)dx = log(b a). b a a 科学出版社职教技术出版中心

56 44 ( ) ξ X = (0, ), A-2 : 0 f(x)dx =, 0 xf(x)dx = µ > 0. A-2, H(f). Lagrange L(f) = a δl(f) δf (f(x) log f(x)dx + λ f(x) + λ 2 xf(x)) dx. = ( + log f) + λ + λ 2 x = 0. + log f = λ + λ 2 x, 0 0 f(x)dx =, xf(x)dx = µ. (2.7.) 0 0 e λ+λ2x dx =, xe λ+λ2x dx = µ. λ 2 = µ, eλ = µ. (2.7.2) f 0 (x) = µ e x/µ, µ, x > 0,. ( H(f 0 ) = log µ + x ) e x/µ dx = + log µ. 0 µ µ

57 ξ X = (, ), A-3 : f(x)dx =, µ σ 2 > 0. A-3, H(f). Lagrange L(f) = (f(x) log f(x)dx + λ f(x) + λ 2 xf(x) + λ 3 (x µ)f(x)) dx. (2.7.3) δl(f) δf = ( + log f) + λ + λ 2 x + λ 3 (x µ) 2 = 0. (2.7.4) + log f = λ + λ 2 x + λ 3 (x µ) 2, f(x)dx =, xf(x)dx = µ, (x µ) 2 f(x)dx = σ 2. f(x) = exp{λ + λ 2 x + λ 3 (x µ) 2 } = exp{λ + λ 2 (x µ) + λ 3 (x µ) 2 + λ 2 µ } ( ( )) λ2 = exp (λ + λ 2 µ ) exp λ 3 (x µ) + (x µ) 2 λ 3 ( ) ( = exp λ + λ 2 µ λ2 2 4λ 2 exp (λ 3 x µ + 2λ ) ) λ 2 (2.7.5) 科学出版社职教技术出版中心 λ 3 = 2σ 2 < 0, λ 2 = 0, e λ =. 2πσ 2 f 0 (x) = ( ) exp (x µ)2 2πσ 2 2σ 2

58 46 ( ), H(f 0 ) = ( 2πσ 2 2 log (2πσ2 ) + = 2 log (2πσ2 ) + = 2 ( log (2πσ 2 ) + ) = 2 log (2eπσ2 ). 2πσ 2 (x µ)2 2σ 2 ( (x µ) 2 2σ 2 ) exp ( exp ( (x µ)2 2σ 2 (x µ)2 2σ 2 ) dx )) dx 2.7. A- A-2 A-3, A- : H(f 0 ) = b a, f 0(x) = b a ; A-2 : H(f 0 ) = + log µ, f 0 (x) = µ e x/µ ; A-3 : H(f 0 ) = 2 log (2eπσ2 ), f 0 (x) = ( ) f 0 (x (n) ) = ( ) exp (x µ)2 2πσ 2 2σ 2. Σ, ( (2π)n Σ exp ) 2 x(n) Σ (x (n) ), (2.7.6) x (n) = (x, x 2,, x n ), (x (n) ) x (n), max H(ξ (n) ) = 2 log ((2πe)n Σ )., ξ (n), Σ, p(x (n) ), H(ξ (n) ) H(ξ (n) ) = p(x (n) ) log p(x (n) )dx (n) R n ( = p(x (n) ) log p 0 (x (n) ) R n p(x (n) ) ) dx (n) p 0 (x (n) )

59 2 47 = p(x (n) ) log p 0 (x (n) )dx (n) + p(x (n) ) log p(x(n) ) R n R p n 0 (x (n) ) dx(n) ( p(x (n) ) R 2 log ( (2π) 2 Σ ) + ) 2 x(n) Σ x dx (n) n ( p0 (x (n) ) ) + p(x (n) ) dx (n) R n p(x (n) = 2 log ((2πe)n Σ ) + p(x (n) ) R n ( ) + p 0 (x (n) ) p(x (n) ) R n dx (n) ( ) 2 x(n) Σ x dx (n) = 2 log ((2π)n Σ ) + n 2 = 2 log ((2πe)n Σ ), 2.3., p 0 (x (n) ), ( ) p(x (n) ) R 2 x(n) Σ (x (n) ) dx (n) = p(x (n) ) 2 n R n = 2 = 2 n i,j= n σ ij σ ij i,j=,. 2. H(/a,, /a, 2/a, 2/a). 2.2 H (p), H(p). n i,j= ij x ix j dx (n) σ R (2) p(x (2) )σ ij x ix j dx i dx j = n , 0;., , 5 5 8, 8 4.,. 科学出版社职教技术出版中心

60 48 ( ) 2.5 ξ η p(x, y) p(0, 0) = 3, p(0, ) =, p(, 0) = 0, p(, ) = 3 3. () H(ξ), H(η). (2) H(ξ η), H(η ξ). (3) H(ξ, η). (4) H(η) H(η ξ). (5) I(ξ; η). (6). 2.6 ξ, η ζ.. () H(ξ, η ζ) H(ξ ζ). (2) I(ξ, η; ζ) I(ξ; ζ). (3) H(ξ, η, ζ) H(ξ, η) H(ξ, ζ) H(ξ). (4) I(ξ; ζ η) I(ξ; ζ ξ) I(ζ; η) + I(ξ; ζ). 2.7 {p, p 2,, p a }, q m = p m+ + + p a. :. H(p,, p a ) H(p,, p m, q m ) + q m log(a m), 2.8 ξ η = (η,, η a ), I(ξ; η) a I(ξ; η i ). 2.9 ξ m x, x 2,, x m, P (ξ = x m ) = a. : H(ξ) = a log a + ( a) log + ( a)h(η), a η m x, x 2,, x m,, : P (η = x j ) def = P (ξ = x j )/( a), j m. H(ξ) a log a + ( a) log + ( a) log(m ), a. 2.0 p = {p,, p a }, p p 2 p a. ɛ > 0 p ɛ p 2 + ɛ. : H(p,, p a ) H(p ɛ, p 2 + ɛ, p 3,, p a ).

61 ξ ξ 2 ξ a, p(ξ, x 2,, x a ) = p(x )p(x 2 x ) p(x a x n ). I(ξ ; ξ 2,, ξ a ). 2.2 p(x). : d 0, ( P p(ξ) d log ) H(ξ). d 2.3 ξ ξ 2,. () ρ = I(ξ ; ξ 2 )/H(ξ ). (2) 0 ρ. (3) ρ = 0? (4) ρ =? ρ = H(ξ 2 ξ ) H(ξ ). 2.4 ξ, η ζ, () I(ξ; η ζ) < I(ξ; η). (2) I(ξ; η ζ) > I(ξ; η). 2.5 ρ(ξ, η), x, y, () ρ(ξ, η) 0, (2) ρ(ξ, η) = ρ(y, x), (3) ρ(ξ, η) = 0 x = y, (4) ρ(ξ, η) + ρ(y, z) ρ(x, z). () ρ(ξ, η) = H(ξ η) + H(η ξ),. (2) ρ(ξ, η) ρ(ξ, η) = H(ξ) + H(η) 2I(ξ; η) = H(ξ, η) I(ξ; η) = 2H(ξ, η) H(ξ) H(η). 2.6 H(ξ η) = 0, η ξ, p(x) > 0 x, y p(x, y) > X = (ξ, x 2,, x a ) Y = (y, y 2,, y m ), f g n m. : I(f(ξ); g(η)) I(ξ; η). 科学出版社职教技术出版中心

62 50 ( ) 2.8 ξ 0 ξ ξ a. : H(ξ 0 ξ a ) n. 2.9 H(f) = f(x) ln f(x)dx. () ( ) f(x) = λe λx, x 0. (2) (Laplace ) f(x) = 2 λe λ x. (3) ξ ξ 2, ξ ξ 2, µ i, σ i,i =, 2.

63 3, S = (X, p(x)), X, p(x), x X. S n = ( X n, p (n) (x (n) ) ), ( ). U U n. ( ) ( ).,,. -. U = U n (3..) n=, U n U n, f X X n U. 3.. f -, x x X, f(x) f(x ). f -, f -., f -,, 科学出版社职教技术出版中心,, f X n U m, m, n, f X n U n.,,. f X U, f ( ), U (3..).

64 52 ( ),, () f X n U n. x (kn) = (x (n), x(n) 2,, x(n) ), k =, 2, 3,, x (n) j = (x j, x j2,, x jn ), j =, 2,, k. f (x (kn) ) = (f(x (n) ), f(x(n) 2 f f. f (X n ) U. k ),, f(x(n) k )). (3..2) (2) f X U, x (k) = (x, x 2,, x k ). k =, 2, 3,, f (x (k) ) = (f(x ), f(x 2 ),, f(x k )). f f. f X U. (3), f (X n ) ( X ) U. f -, f ( ) (), -. (2) f -, f. (3) f -,. () (2), f -, f -., x (kn) y (kn), j {, 2,, k}, x (n) j y (n) j, f -, f(x (n) j ) f(y (n) j ), (f(x (n) ), f(x(n) 2,, f(x(n) k )) (f(y(n) ), f(y (n) 2 ),, f(y (n) k )), f (x (kn) ) f (y (kn) )., f -, f. -. X = {a, b, c}, U = {0, }, f(a) = 0, f(b) = 0, f(c) = 00,

65 3 53 f -, f. f (c) = (0, 0, ), f (a, b) = (f(a), f(b)) = (0, 0, ), (a, b) c, f (a, b) = f (c). f X U -, f., U = {0, }, ( ). U f = { f(x) x X }. f, U f. f, U f., C = U f = {c, c 2,, c a }, c i = f(x i ). l f (x) f(x), l i = l f (x i ) x i, U f = {u (li) i, i =, 2,, a}, u (li) i = (u i, u i2,, u ili ), u ij U., C U f, c i = u (li) i S = (X, p(x)), f, x X, f(x) U, l f (x) f(x). f. 3.. L(S, f) = x X X = {a, b, c, d}, S = a b c d p(x)l f (x) (3..3). p(a) = p(b) = 2 7, p(c) = 9 7, p(d) = 4 7. 科学出版社职教技术出版中心

66 54 ( ) U = {0, }. f, f 2, f (a) =, f (b) = 0, f (c) = 00, f (d) = 0, f 2 (a) = 000, f 2 (b) = 00, f 2 (c) = 0, f 2 (d) =. L(S, f ) = = 4 7, L(S, f 2 ) = = , f 2 f, f 2 f., ( ) S = (X, p(x)), f, L(S, f). f 0, f,. f 0 S L(S, f 0 ) L(S, f). ( ) S n = X n, p (n) (x (n) ), n =, 2, 3,,, U. U (m) U m, (f, g) ξ (n) S n. U (m) f f : X n U m, g : U m X n ( ) () S n, (f, g), { ( )} e n (f, g) = Pr ξ (n) g f(ξ (n) ). (2) C = U (m) f = { f(x (n) ) x (n) X (n)}, v n =, f. R n = n log(v n) = n log U (m) f

67 ( ) R S n, n =, 2, 3,, ɛ n 0, n, (f (n), g (n) ),. U (m) f. () n =, 2, 3,, e(f (n), g (n) ) ɛ n 0. (2) n =, 2, 3,, R n R( + ɛ n ) R, R n = n log M n, M n =, R 2 nr, ( ) S n, ( ).. (), f g -, e n (f, g) 0. (2) U (m) f U (m),,, M n. C n = U (m) f = {, 2,, M n }, (3), f, C = U (m) f S, X = {x,, x 5 }, p = ɛ, p 2 = p 3 = p 4 = p 5 = ɛ/4., 3. 5, 3., f(x ) = 0, (f(x 2 ), f(x 3 ), f(x 4 ), f(x 5 )) = (00, 0, 0, ). f, L(S, f) = ( ɛ) + 3ɛ = + 2ɛ. ɛ <, L(S, f) = + 2ɛ < 3, ɛ < /2, L(S, f) = + 2ɛ < 2,. 科学出版社职教技术出版中心

68 56 ( ) 3.2,, , 3.2. X = {a, b, c, d}, f(a) = 0, f(b) = 0, f(c) = 0, f(b) = 0. C = {0, 0, 0, 0}.. 0,, 0., , a, b, c, d., ,, 0 c, 0 b, 0 a, 0 d, 0 a, 0 b, 0 a, cbadaba,.,, 0 C,, 0 0, 0, 0 c,, 0 d ,,,, , X = {a, b, c, d}. f(a) =, f(b) = 0, f(c) = 00, f(d) = 000, 3.2.,,, 0, , a, b, c, d.., ,, acbadab,.

69 3 57, C = {, 0, 00, 000},,,,, ,, a (k) = (a, a 2,, a k ) b (k ) = (b, b 2,, b k ), a (k) b (k ), k k, (a, a 2,, a k ) = (b, b 2,, b k ).,, C, c i c j, j i , C = {, 0, 00, 000},.,,,,,,. 3.2.,., Kraft,. L. G. Kraft (Kraft ) f, C, {l, l 2,, l a }, r = U. f, Kraft a r l k k=, {l,, l a } Kraft, {l,, l a }. U f = {u (l), u (l2),, u (la) a }, u (li) i = (u i, u i2,, u ili ), i =, 2,, a, l i.. 科学出版社职教技术出版中心

70 58 ( ) l = max{l i, i =, 2,, a}. i =, 2,, n, U i = { (u (li) i, z (l li) ) z (l li) U (l li)} U (l), (3.2.) u (li) i U f, U (k) U k, U i = r l li. i, n n n U i = r l li = r l r li. f, i j U i U j, n U i U (l) = r l,. Kraft. r l n n r li rl, li r l, l 2,, l a r Kraft. f, l,, l a. α j l i = j i. Kraft α j. (3.2.2) rj j= k =, 2, 3,, k α j r j. j= j= α j r j k α j r k j r k j= α r α r + α 2 r 2 α r 2 + α 2 r + α 3 r 3 α r n + α 2 r n α n r n..

71 3 59, l, l 2,, l a, j α j.. () α, α r, U α, C α, u,, u,2,, u,α. (3.2.3) (2), α 2 2., (3.2.3). r 2 α r. α 2 r 2 α r, α 2 2, (3.2.3). (u 2,i,, u 2,i,2 ), i =, 2,, α 2. (3.2.4), (3.2.3) (3.2.4), u k,i,j k, i, j., j. (3) α 3, 3, (3.2.3) (3.2.4). (u 3,i,, u 3,i,2, u 3,i,3 ), i =, 2,, α 3. (3.2.5) (3.2.3) (3.2.4) α r 2 + α 2 r, (3.2.3) (3.2.4) r 3 α r 2 α 2 r, (3.2.5). α 3 r 3 α r 2 α 2 r, (4), k =, 2, 3,, k. C = a, k, α j = a.,,.. Kraft l, l 2,, l a l, l 2,, l a. Kraft U = 2, C = {0,, 00, 0},, 2, 3, =, 科学出版社职教技术出版中心 j=

72 60 ( ), Kraft Kraft U = {0,, 2}, l = l 2 =, l 3 = 2, l 4 = l 5 = 4, l 6 = = = <, Kraft, U.. l = l 2 =, α = 2, u, = 0, u,2 =. l 3 = 2, α 2 =, 2 0, 2, (u 2,,, u 2,,2 = (2, 0). 4. 0, 2, (u 2,,, u 2,,2 ) = (2, 0), (u 4,,, u 4,,2, u 4,,3, u 4,,4 = (2,, 0, 0), (u 4,2,, u 4,2,2, u 4,2,3, u 4,2,4 = (2,, 0, )., 5 (u 5,,, u 5,,2, u 5,,3, u 5,,4, u 5,,5 ) = (2,,, 0, 0)., U f = {0,, 20, 200, 20, 200}. 3.3,..

73 , S = (X, p(x)), X = {x, x 2,, x a }, P = (p, p 2,, p a ). (C, f), C, C = {c, c 2,, c a }, {l, l 2,, l a }. L(S, f) = n p i l(f(x i )) = n p i l i S = (X, p(x)), f, H r (p,, p a ) L(S, f), H r ( ) r, l i = log r p i. C, Kraft, q i = /(q 0 r li ), 2.3.2, q 0 = n q i 0, i =, 2,, n, H r (p,, p a ) = = =. li r n n q i =. p i log r p i n p i log r q i n p i log r (q 0 r li ) n p i l i + log q 0 n p i l i = L(S, f), 科学出版社职教技术出版中心 q 0, log(q 0 ) 0, p i = q i, q 0 =, p i = /r li l i = log r p i.

74 62 ( ) l i = log r p i, l i = log r p i., l i,, log r p i l i < log r p i +. Int(z) z, { z, z, Int + (z) = Int(z) +, z, p = (p, p 2,, p a ), l i = Int + ( log p i ) = log r p i. log r l i < log p r +, log i p r l i r li, i p i p i r p li i, n r n p i =. li Kraft, {l, l 2,, l a }. L(S, f) = < = n p i l i n n ( ) p i log r + p i p i log r p i + n = H r (p,, p a ) +. H r (p,, p a ) ,. p i

75 S = (X, p(x)), r f 0 H r (p,, p a ) L(S, f) < H r (p,, p a ) , n =, 2, 3, X n, S n = (X n, p (n) (x (n) )) S = (X, p(x)) X n = { x (n) = (x, x 2,, x m ) xi X } p(x (n) ) = p(x, x 2,, x n ) = n p(x k )., S n. f (n) S n, f (n) X n U, l ( f (n) (x (n) ) ) f (n) (x (n) ), f (n) L(S (n), f (n) ) = ( ) p(x (n) )l f (n) (x (n) ). x (n) X n, S n S, r = U, f (n) 0 H r (p, p 2,, p a ) L(Sn, f (n) ) n p = (p, p 2,, p a ) S.. k= < H r (p, p 2,, p a ) + n ,, H r ( p). 3.4 Huffman,,., D. A. Huffman 952, Huffman. 科学出版社职教技术出版中心

76 64 ( ) 3.4. Huffman Huffman,.,,, p = (p, p 2,, p a ) p = {0.24, 0.20, 0.8, 0.3, 0.0, 0.06, 0.05, 0.03, 0.0}, U = {0,, 2, 3}, Huffman. Huffman Huffman Huffman Huffman () p, Huffman, a = 9. (2) 3,,, Huffman. 7, 0.09,. (3) 4,,, Huffman. 4, 0.38,. Huffman, Huffman Huffman Huffman () Huffman 4, 0,, 2, 3. 4 Huffman.,

77 3 65. (2), 0.38, 0, , 0.0, 0.09, , 0.0, 0.09, , 00, 0, 02, , 0.20, 0.8 3,, 2, , 0.20, 0.8, 0.3, 0.0, 0.09, , 2, 3, 00, 0, 02, 03 Huffman. (3), 0.09, 02, , 0.03, , 0.03, , 020, 02, Huffman. Huffman Huffman Huffman. U = { 0,,, r }. p = (p, p 2,, p a ). Huffman.. Huffman a r,., f(i) = i, i =, 2,, a. a > r. 科学出版社职教技术出版中心

78 66 ( ) 2. Huffman Huffman. () a > r Huffman. 2k ( ) a, k kr k a, k = Int, Int(z) r z,, 3, 5,, 2k ( ) kr k +, (k )r k + 2,, 3r 2, 2r, r., r, 2j t j = { a, j =, (k j + )r k + j, j = 2, 3,, k. (3.4.). (2) Huffman (p, p 2,, p a ),. (3) Huffman, a (k )r + k 2,,. (4) Huffman, r,,. (5) Huffman, r,,. (6), Huffman, r,. Huffman. 3. Huffman Huffman,. p j = (p j,, p j,2,, p j,tj ), j =, 2,, k, (3.4.2) Huffman 2j, t j (3.4.2), r p j,sj = p j,tj i+ (3.4.3) 2j 3 r, 2j s j.

79 Huffman Huffman (3.4.2) (3.4.3), Huffman, Huffman,, Huffman, Huffman.. () Huffman r, {0,,, r },, 2k., Huffman 2k, 2k. (2) 2j, 2j, 2j, 2j, 2j c j,, c j,2,, c j,tj, c j,i U. (3) 2j, p j,sj (3.4.3), c j,sj, 2j 2 t j r p j,i 2j, r p j,i (c j,sj, 0), (c j,sj, ),, (c j,sj, r ). (c j,sj, u) c j,sj u. 2j 3, 2j 2. (4), Huffman,, b c 2,s2, b = a (k )r + k (c 2,s2, 0), (c 2,s2, ),, (c 2,s2, b ),, 2, 3, 4 Huffman, H. C = {c, c 2,, c a } Huffman. 3.5 Huffman Huffman Huffman Huffman 科学出版社职教技术出版中心 Huffman (Huffman ) Huffman H Huffman. Huffman H. 2k, 2k 2 2k, 2k 2,.

80 68 ( ), 2j, 2j 2 2j, 2j 2,., Huffman (Huffman ) Huffman H Huffman. S, f 0 f Huffman, L(S, f 0 ) L(S, f). (3.5.). S, S, S = (X, p), S = (X, p ), X = {x, x 2,, x a }, p = (p, p 2,, p a ), X = {x, x 2,, x a}, p = (p, p 2,, p a ), p p 2 p a, p p 2 p a C = {c, c 2,, c a } S, l(c ) l(c 2 ) l(c a ) S S,.. () S S r Huffman,. a < a a + r. p p, s a, p j = p j, j < s, p j = p j, s < j < a, p j = a a+ p a+i, j = s, (3.5.2)

81 3 69 (2) C = {c, c 2,, c a }, C = {c, c 2,, c a } S S, C C r Huffman,. S S r Huffman. C C. c j = c j, j < s, c j = c j+, s < j < a, (3.5.3) c a+i = (c s, i ), i =, 2,, a a C C S S, S a = kr k +, C C r Huffman, C S, C S.,. r = 2, a = a +., C S, S D = {d, d 2,, d a },. L(S, D) = p jl(d j ) < L(S, C ) = p jl(c j) a j= s a L(S, C ) = p jl(c j) + p jl(c j) + j= p j l(c j ) + s = = j= j=s a j=s+ a p j l(c j ) + p s. j= a a j= p jl(c j) j=a 科学出版社职教技术出版中心 p j l(c j ) + p s [l(c s ) + ], L(S, D) s a L(S, D) = p jl(d j ) + p jl(d j ) + j= p j l(d j ) + s = j= j=s a j=s+ p jl(d j ) a j=a p j l(d j ) + p jl(d j ). a j=a

82 70 ( ) l a l a d a = u u 2 u la, d a+ = v v 2 v la,, h a = u u 2 u la, h a = v v 2 v la d a l a d a l a,. () h a {d, d 2,, d a },. l(d a ) = l(d a ). l(d a ) < l(d a ), D : D = {d, d 2,, d a, d a}, d a = (h a, u ) = u u 2 u la u, u u la {0, }. u u la, d a d a. D, L(S, D ) = < a p j l(d j ) + p a l(d a) j= a p j l(d j ) + p a l(d a ) j= = L(S, D). D S, l(d a ) = l(d a ) = l(h a ) +. S D D. d j = d j, j < s, d j = d j+, s < j < a, d j = h a, j = s, D = {d, d 2,, d a}, a L(S, D) = p jl(d j ) + p al(d a ) + p a l(d a) j= s = j= a p jl(d j ) + j=s p jl(d j ) + p a[l(h a ) + ] + p a [l(h a) + ]

83 3 7 p j l(d j ) + s = j= s = j= p j l(d j ) + = L(S, D ) + p s. a j=s+ a j=s+ p j l(d j ) + p s l(h a ) + p s p j l(d j ) + p s l(d s ) + p s L(S, D) = L(S, D ) + p s < L(S, C ) = L(S, C) + p s, L(S, D ) < L(S, C) C S. (2) h a {d, d 2,, d a }, d t, d t = (h a, u lt ) = (h a, u ), d a = (h a, u la )(h a, u), t < a, u u {0, }, d a d t, h a d a, d t d a d a. h a d, d 2,, d t, d t+,, d a, d t, d t d a d t.,. d a d a h a = v v 2 v la, d a = v v 2 v la = (h a, v la v a+,, v la ). (a) h a h a, h a = h a ( ), h a. (2)-,. (b) h a {d, d 2,, d a }, (),. (c) h a {d, d 2,, d a }, d t, t < a, v v = v la,. d t = (h a, v ), d a = (h a, v), 科学出版社职教技术出版中心 l(d a ) = l(d a ) = l(h a ) + = l(h a ) (3.5.4)

84 72 ( ), h a {d, d 2,, d a }, h a {d, d 2,, d a }, (3.5.4), d j = d j, j s, t, t, j {, 2,, s }, d j = h a, j = s, d j = d j, j s, t, t, j {s +, s + 2,, a}, d j = (h a, 0) j = t, d j = (h a, ) j = t, D = {d, d 2,, d a} S, a L(S, D) = p jl(d j ) + p a l(d a ) = j= j: j s;j t,t p jl(d j ) + j:s j a ;j t,t p jl(d j ) +p tl(d t ) + p al(d a ) + p t l(d t ) + p a l(d a ) = p j l(d j ) + p j l(d j: j s;j t,t j:s+ j a;j t,t +p tl(h a ) + p al(h a ) + p t l(h a ) + p a l(h a ) + p t + p a + p t + p a = p j l(d j ) + p j l(d j ) j: j s;j t,t j:s+ j a;j t,t +(p t + p a)l(h a ) + (p t + p a )(l(h a ) + ) + p t + p a p j l(d j ) + p j l(d j ) j: j s;j t,t j:s+ j a;j t,t +p s l(d s ) + p t l(d t ) + p t )l(d t ) + p s a = p j l(d j ) + p s, j= t, t < a < a, p t, p t p a p a,. p t + p a, p t + p a p a + p a = p s L(S, C ) = L(S, C) + p s > L(S, D) L(S, D ) + p s j )

85 3 73, L(S, C) > L(S, D ), D, C. h a {d, d 2,, d a }. (3), C Huffman C S Huffman 3.5.2,. () Huffman, 2j p j = (p j, p j2,, p jtj ) S j, 2j C j = (c j, c j2,, c jtj ) S j, S j S j+ Huffman, C j C j+ Huffman ( 3.5.3). (2) Huffman 2k, 2k, l(c ki ) =,. (3) Huffman 2j, 2j, C j S j. C = C S = S..,, Huffman Huffman, r = 2., Huffman,, ,, Huffman Huffman., 7, 6, 2.49, Huffman 科学出版社职教技术出版中心