科学出版社职教技术出版中心
普通高等教育 十一五 国家级规划教材高等院校信息科学系列教材 信息论与编码理论 ( 第二版 ) 沈世镒陈鲁生编著 北京
内容简介 本书主要介绍信息论和编码理论的基本内容, 其特点是简明扼要, 可读性强, 既具有较严谨的数学描述与推导, 又注意到信息论的实用背景, 其中许多典型问题已在通信工程中得到实际应用. 全书共分 2 章. 主要内容包括 : 信息的度量 信源编码 信道编码定理 编码理论中用到的基本抽象代数知识 编码理论的基本概念和基本问题 线性码 Hamming 码 循环码 BCH 码 Reed-Solomon 码 Golay 码 Reed-Muller 码 平方剩余码 Goppa 码以及信息论和编码理论的应用. 本书每章末均附有习题, 其中部分习题是对正文内容的补充. 本书可作为高等院校信息科学专业 计算机科学专业 通信专业以及相关专业的本科生教材, 也可供相关领域的研究生 教学与科研人员, 以及工程技术人员参考. 图书在版编目 (CIP) 数据信息论与编码理论 / 沈世镒, 陈鲁生编著. 2 版. 北京 : 科学出版社, 200 ( 普通高等教育 十一五 国家级规划教材 高等院校信息科学系列教材 ) ISBN 978-7-03-02958-5 Ⅰ. 信 Ⅱ. 沈 2 陈 Ⅲ. 信息论 - 高等学校 - 教材 2 信源编码 - 编码理论 - 高等学校 - 教材 3 信道编码 - 编码理论 - 高等学校 - 教材 Ⅳ. TN9.2 中国版本图书馆 CIP 数据核字 (200) 第 93478 号 责任编辑 : 鞠丽娜 / 责任校对 : 柏连海责任印制 : 吕春珉 / 封面设计 : 三函设计 北京东黄城根北街 6 号邮政编码 : 0077 http://www.sciencep.com 出版 印刷 科学出版社发行 各地新华书店经销 * 2002 年 7 月第 一 版 开本 : B5(720 000) 200 年 0 月第 二 版印张 : 6 200 年 0 月第八次印刷字数 : 35 000 印数 : 2 00 24 000 定价 : 27.00 元 ( 如有印装质量问题, 我社负责调换 科印 ) 销售部电话 00-6234988 编辑部电话 00-6238978-8002(HI08) 版权所有, 侵权必究 举报电话 :00-64030229;00-6403435;3505303 科学出版社职教技术出版中心
998,,, 280,,, 999 2000,, 200,,,,,,,,,,,,,,,, ( ), 2002 3
8, 7,. 2006.,,.,,..,.,,.,.,,,.,,,.,..,.. 科学出版社职教技术出版中心 200 6
,,,.,.,.,???.,.,..,..,., Shannon,,., Shannon Shannon.,,...,,.,...,,.,.,,....,. 2. 2 4 Shannon, 2. 3 4. Shannon,.,.
vi ( ), ( ). ( ),.. ( ).,. 5. 5, 6, 7 9 Hamming, 0 BCH Reed-Solomon.,., Shannon, Shannon, (, )., Shannon,. 2.,,. 2,,,., 3. 3.,.,. 2,.,,.,.,...,,. 科学出版社职教技术出版中心 2002 5
...............................................................................................................................................................................2 Shannon....................................... 2..3.................................................. 4..4..................................... 5.2......................................... 7.2..................................................... 7.2.2................................................ 8.2.3..........................................9.2.4............................................9.2.5...............................................2.3............................................. 3.3.......................................................... 4.3.2...............................................4.3.3................................................. 6...................................................................... 7 2................................................................8 2...................................................................... 8 2.............................................8 2..2.............................................9 2..3...............................................23 2.2.......................................................24 2.2...................................................... 24 2.2.2...............................................25 2.3......................................................... 28 2.3............................. 28 2.3.2................................................... 30
viii ( ) 2.3.3 Fano...................................................... 32 2.4......................................................... 32 2.4.............................................................. 33 2.4.2........................................................... 33 2.4.3....................................................... 34 2.5.......................................................35 2.5............................................35 2.5.2 Jenson.......................................... 36 2.6............................................. 38 2.6. Shannon..................................... 38 2.6.2 Shannon................................. 39 2.6.3...................................... 42 2.7........................................................... 43 2.7..............................................43 2.7.2.............................................44 2.7.3...............................................45 2.7.4...................................... 46 2...................................................................... 47 3............................................................. 5 3.......................................................... 5 3........................................................... 5 3..2...............................................5 3..3.............................................53 3..4...........................................54 科学出版社职教技术出版中心 3.2.......................................................56 3.2..............................................56 3.2.2 Kraft......................................................57 3.3............................................... 60 3.3..................................... 6 3.3.2.................................... 62 3.3.3.............................. 63 3.4 Huffman................................................63 3.4. Huffman.......................................... 64 3.4.2 Huffman.......................................... 65 3.5 Huffman........................................... 67
ix 3.5. Huffman............................................ 67 3.5.2 Huffman............................................ 68 3.6............................................... 74 3...................................................................... 78 4.........................................................80 4.......................................................... 80 4.................................................80 4..2...............................................82 4.2.......................................................83 4.2......................................... 83 4.2.2........................................ 84 4.3............................................... 87 4.3................................................87 4.3.2........................................ 90 4.4.......................................................93 4.4................................................93 4.4.2................................................... 97 4.5.............................................. 02 4.6..................................... 06 4.7 (Gaussian)............................................3 4.....................................................................5 5................................................ 7 5..................................................................... 7 5.2............................................................... 2 5.3.......................................................... 23 5.4........................................................ 24 5.5............................................................... 30 5.6......................................................34 5.....................................................................38 6................................................ 40 6......................................................... 40
x ( ) 6.......................................................... 40 6..2 Hamming Hamming.................................. 4 6..3........................................................ 42 6..4.......................................................... 42 6.2.................................................43 6.3.................................................45 6.3..................................................... 46 6.3.2................................................49 6.....................................................................54 7...............................................................56 7......................................................... 56 7.2.....................................................57 7.3................................................... 6 7.4................................................... 64 7.....................................................................68 8 Hamming....................................................... 7 8. Hamming.................................................. 7 8.2 Hamming.................................................. 72 8.3 Hamming............................................. 72 8.4 Hamming.......................................... 75 8.....................................................................77 9...............................................................79 9......................................................... 79 科学出版社职教技术出版中心 9.2........................................................ 8 9.3....................................... 84 9.4................................................... 88 9.5................................................... 89 9.....................................................................90 0 BCH Reed-Solomon.................................... 93 0. BCH...............................................93 0.2 Reed-Solomon..................................... 97 0.3 BCH Reed-Solomon.............................98 0.4 Reed-Solomon..................... 202 0....................................................................203
xi................................................. 205. Golay............................................................ 205.2 Reed-Muller......................................................206.2........................................................ 207.2.2 Reed-Muller................................................. 209.3......................................................... 20.4 Goppa........................................................... 2....................................................................22 2...................................................... 24 2................................................... 24 2...............................................24 2..2........................................ 25 2..3...................................... 26 2..4...............................................27 2..5.............................................29 2..6...............................................29 2..7........................................ 29 2..8.................................... 222 2.2................................................223 2.2.................................................... 224 2.2.2.................................................226 2.2.3...............................................228 2.2.4................................................... 23 2.3................................................232 2.3........................................................ 232 2.3.2..................................................... 234 2.3.3......................................................... 235 2....................................................................236.................................................................. 238
,,,.,...,,,.,...,..,....,.,.,. 20,.,.,, ( ),,.,,.,. 9 20 40,.. 科学出版社职教技术出版中心,. Morse Bodo..,
2 ( )., Morse Bodo.,,. 2.,.,.,.,,.,.,. ( ),,,. 20 20, H. Nyquist L. Hartley,,. Shannon. 3. Shannon 20 40, N. Wiener E. Fisher C. E. Shannon,.,.,. 4.,.,,....2 Shannon 948 C. E. Shannon, 60. 60,,,.,. ( ).,.. 948 Shannon,.,
3.. Shannon 948 20 60, 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 科学出版社职教技术出版中心 20 70 80,. Shannon
4 ( ),... 20 80 90. Shannon, 20 70 80,.,.....3,.... Shannon,,. 2. Shannon Kolomogolov, Hausdorff,. Shannon Kolomogolov Hausdorff,.,.,. 3.,,,.,. ( ),... ().,
5, Fisher Kullback-Laiber.., EM ACI Ying-Yang. S. Amari,. (2). T. Cover,,. (3).,.,.,...4 Shannon,,.. 20 70 80.,.,.., BCH Reed-Solomon,.,, Viterbi,. 2. 20 80 90. G. Ungerbock 982 Gaussian.,, 200bit/s 30000bit/s. 30,. 3. 科学出版社职教技术出版中心..,
6 ( ),. 20 70. T. Berge, 20 90.,,,.,, 50: 60:.,. 90, IT,, JPEG(joint photographic experts group) MPEG.,,.,. 2,.,,.. 4.,,.., ; ;.,.,.,. 00......,.,,...,
7.,..2,..2..,..,., ;.,.,,. Shannon,,,. Shannon 948,.,,,.,...,,. Shannon Shannon.,.. Shannon.., Shannon,, Shannon., Shannon.,. 科学出版社职教技术出版中心
8 ( ).2.2.2...2...,,.. 2..,,..,.,.,.,,. 3.,,.. 4... 5....,. 6...
9.2.3,,., (, ).,, ( ).,,.,.,.,.,,,.,,.,.,,.,..,,,.,.,,..,.,,,,..2.4,.,.. 科学出版社职教技术出版中心,.,. 26,.,,,.,,
0 ( ),.2..2.2..2. 0.2.2 A 0.082 H 0.06 O 0.075 V 0.00 B 0.05 I 0.070 P 0.09 W 0.023 C 0.028 J 0.002 Q 0.00 X 0.00 D 0.043 K 0.008 R 0.060 Y 0.020 E 0.27 L 0.040 S 0.063 Z 0.00 F 0.022 M 0.024 T 0.09 G 0.020 N 0.067 U 0.028.2., 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 ( ) ( ).. 0.2...2.2, S = [X, p(x)], X ( ASCII )..2.2. 2..
;. 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). 3..2.3,. Y, X U V Y, f g, f(x) : X U, g(v) : V Y., U V,. 4..2.4, 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)
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)
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.
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... 20 80.
5, A. N. Kolomogolov R. L Dobrushin. A. N. Kolomogolov, R. L Dobrushin. 2., 20 70. 20 80 90. 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).. 科学出版社职教技术出版中心
6 ( ) 4.,.,...3.3..., 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 ).
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), ξ ξ η η. 科学出版社职教技术出版中心
2 Shannon,.???. 2. 2.. ξ, 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,,.,.,,,.
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 ).,. 2..2. { 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)
20 ( ) k,., ( 3 ), = +. ( 3 ). ( 3 ),. 2. 2.. 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
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. 科学出版社职教技术出版中心
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(ξ)
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. 2..3 Shannon. 2... 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 3 + 3 log 3 + log 3 = log 3.585. 3 p = p 2 = 4 p 3 = 2 X = {x, x 2, x 3 }, ( H 4, 4, ) = 2 4 log 4 + 4 log 4 + log 2 =.5. 2
24 ( ) 2..2 ξ, p(ξ = ) = p, p(ξ = 0) = p, H(ξ) = p log p ( p) log( p) def = H(p). H(p), 2... 2.. 2.2,.,. 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(ξ, η)),
2 25 E ξ,η (g(ξ, η)) g(x, y) ξ, η, E ξ,η (g(ξ, η)) = p ξ,η (x, y)g(x, y). x X y Y 2.2.2 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).. 2.2. (ξ, η) 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(η ξ)). 科学出版社职教技术出版中心
26 ( ) H(ξ η) = q(y)h(ξ η = y) y Y = p(x, y) log p(x y) x X y Y = E ξ,η (log p(ξ η)). 2.2. H(ξ η) 0, ξ η, p(x y) y Y, q(y) > 0, p(x y). 2..,. 2.2.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),. 2.2.2,.,. 2.2. (ξ, η) H(ξ, η) H(ξ), η ξ ( η ξ ). 2.2. 2.2.2. (ξ, η, ζ),,. H(ξ, η ζ) = p(x, y, z) log p(x, y z) x X y Y z Z
2 27 = H(ξ ζ) + H(η ξ, ζ) = H(η ζ) + H(ξ η, ζ). 2.2.3 ξ, ξ 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,, ξ ). (ξ, η). 2 3 4 Σ 2 3 4 Σ 8 6 6 4 2 6 8 6 32 32 6 32 32 6 0 0 0 4 8 8 4 4 4 4 科学出版社职教技术出版中心
28 ( ) ξ η, ( 2, 4, 8, ) (, 8 4, 4, 4, ). 4 H(ξ) = 2 + 2 4 + 6 8 = 7 4, H(η) = 4 2 4 = 2,, H(ξ, η) = 4 + 23 8 + 6 4 6 + 4 5 32 = 25 8. H(ξ η) = H(ξ, η) H(η) = 25 8 2 = 9 8, H(η ξ) = H(ξ, η) H(ξ) = 25 8 7 4 = 8. H(η ξ) H(ξ η), H(ξ) H(ξ η) = H(η) H(η ξ). 2.3,.. 2.3.,.,,. 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.
2 29 2.3.2 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. 2.3. 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 2.3.3 u i > 0, v i > 0, i =, 2,, a, a i =, 2,, a. 2.3.2, 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 科学出版社职教技术出版中心
30 ( ). q i = v i, a v k k=,. 2.3. ξ, X = {x,, x a }, H(ξ) log a, i p(x i ) = a. 2.3.3, (u,, u a ) = (p,, p a ) ξ, v i =, i =, 2,, a, 2.3.3 a H(ξ) = p i log p i ( a ) u i log ( a ) p i log = log a. 2.3.3, i p i = a. 2.3.2. 2.3.2 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
2 3, 2.3.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 ). 2.3.2 H(ξ) H(f(ξ)), b ( qi p i H, q i2,, q ) ik i = 0, p i p i p i 科学出版社职教技术出版中心
32 ( ) p i = 0 q ij p i k i = 0, j= q ij = p i, j q ij p i =, f -. 2.3.3 Fano Fano. 2.3.4 (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 2.3.3. 2.4,,.,.
2 33 2.4.. 2.4. 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.,.. 2.3.2. H(p q) 0, p(x) 0 x p(x) = q(x).,. 2.4.2. 2.4.2 ξ η, 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, ξ η. 科学出版社职教技术出版中心
34 ( ) (4) f Y Z, I(ξ; η) I(ξ; f(η)), f -. (5) I(ξ, ξ) = H(ξ)., (4) 2.3.3,. 2.4.3,. 2.4.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.4.2 (ξ, ξ 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 ). 2.4. 2.4.2. () a = 2, 2.4.2 I(ξ; (η, ζ)) = I(ξ; η) + I(ξ; ζ η).. (2) (ξ, η, ζ), I(ξ; (η, ζ)) I(ξ; ζ). ξ η ζ.
2 35 (3) I(ξ; η ζ) = H(ξ ζ) + H(η ζ) H(ξ, η ζ), = H(ξ ζ) H(ξ η, ζ), = H(η ζ) H(η ξ, ζ). () 2.4.. (2) (), I(η; ζ ξ) 0, ξ ζ η,, ξ η ζ. (3). H(ξ), H(η), H(ξ, η), H(ξ η), H(η ξ) I(ξ; η) 2.4.. I(ξ; η) ξ η. 2.4. 2.4. 2.2., I(ξ; η) = H(ξ) H(ξ η) = H(η) H(η ξ) = 0.375. 2.5.,. 2.5. 2.5. (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 ( ).
36 ( ),.,. x 2, x, e x, x log x. x, log x. ax + b.,.,. 2.5. ( ). 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),,.. 2.5., 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,. 2.5.2 Jenson, E( )., E(ξ) = p(x)x. x X, E(ξ) = xf(x)dx. 2.5.2 (Jenson ) g, ξ, E(g(ξ)) g(e(ξ)). g, ξ.
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. 2.5.3 ( ) () 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,. 科学出版社职教技术出版中心
38 ( ) 2.6,.,. 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). 2.6.2 f(x) ξ H(ξ) H(ξ) = f(x) log f(x)dx. (2.6.2) 0 log 0 = 0.. 2.6. ( ) X, 0 a., 0 a /a, 0. H(ξ) = a 0 a log dx = log a. a, a <, log a < 0,.,. 2.6.2 ( ) ξ p λ (x) = λe λx, x, λ 0, H(ξ) = = λ 0 0 = log λ. p λ (x) log p λ (x)dx e λx (log λ λx)dx
2 39 2.6.3 ( ) ξ 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 ). 2.6.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. 2.6.4 ( ) 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 ),
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), σ). 2.6.3 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), Σ). 2.6.5 ( ) N(µ (n), σ). ξ ξ n, H(ξ (n) ) = p(x (n) ) log p(x (n) ) dx(n)
( = E = E log ) p(ξ (n) ) ( 2 log(2π)n Σ + 2 2 4 (ξ (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 ). () 2.6. 2.6.5, Shannon. ξ 0 a, H(ξ) = log a, 0 < a <, H(ξ) < 0., Shannon. Shannon Shannon. Shannon.. (2) 2.6.5, Shannon.,, H(ξ (n) ) ξ (n). 科学出版社职教技术出版中心
42 ( ) 2.6.3. (ξ, η), 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.6.6, µ (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.6.4 Σ = ( σ σ 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.
2 43, 0 σ 2 2 σ σ 22., 0 ρ = σ2 2 σ σ 22. ξ η, σ 2 = 0., ρ =, I(ξ, η) = 0.. 2.7,,,,., 2.3.. 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). 2.7. ξ 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 科学出版社职教技术出版中心
44 ( ) 2.7.2 ξ 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 µ µ
2 45 2.7.3 ξ 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 3. 3 λ 2 (2.7.5) 科学出版社职教技术出版中心 λ 3 = 2σ 2 < 0, λ 2 = 0, e λ =. 2πσ 2 f 0 (x) = ( ) exp (x µ)2 2πσ 2 2σ 2
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) = 2.7.4 2.7.2 ( ) 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) ). 2.3. 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) )
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 2. 2 2.3 500 600, 0;.,. 2.4 20. 0, 5 5 8, 8 4.,. 科学出版社职教技术出版中心
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 ).
2 49 2. ξ ξ 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) > 0. 2.7 X = (ξ, x 2,, x a ) Y = (y, y 2,, y m ), f g n m. : I(f(ξ); g(η)) I(ξ; η). 科学出版社职教技术出版中心
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.
3,.. 3. 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 -,, -. 3..2 科学出版社职教技术出版中心,,. 3..2 f X n U m, m, n, f X n U n.,,. f X U, f ( ), U (3..).
52 ( ),,. 3..3. () 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 ( ). 3.. -. (), -. (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,
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. 3..3 3..4 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 2 2 9 4 7 7 7 7 p(x)l f (x) (3..3). p(a) = p(b) = 2 7, p(c) = 9 7, p(d) = 4 7. 科学出版社职教技术出版中心
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 ) = 2 7 2 + 2 7 + 9 7 3 + 4 7 2 = 4 7, L(S, f 2 ) = 2 7 5 + 2 7 2 + 9 7 2 + 4 7 2 = 40 7. 3.., f 2 f, f 2 f.,. 3..5 ( ) S = (X, p(x)), f, L(S, f). f 0, f,. f 0 S. 3..4 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. 3..6 ( ) () 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
3 55 3..7 ( ) 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,. 3..8 ( ) 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.. 3..2 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,. 科学出版社职教技术出版中心
56 ( ) 3.2,,.. 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., 0 0 2 3, a, b, c, d., 0000000,, 0 c, 0 b, 0 a, 0 d, 0 a, 0 b, 0 a, cbadaba,.,, 0 C,, 0 0, 0, 0 c,, 0 d.. 3.2.,,,,.. 3.2.,. 3.2.2 X = {a, b, c, d}. f(a) =, f(b) = 0, f(c) = 00, f(d) = 000, 3.2.,,, 0, 0 2 3 0, a, b, c, d.., 0000000,, acbadab,.
3 57, C = {, 0, 00, 000},,,,,. 3.2.2,,.. 3.2.2 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. 3.2.2, C = {, 0, 00, 000},.,,,,,,. 3.2.,.,. 3.2.2 Kraft,. L. G. Kraft 949. 3.2.2 (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.. 科学出版社职教技术出版中心
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 2 + + α n r n..
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. 3.2.3 U = 2, C = {0,, 00, 0},, 2, 3, 3. 2 + 2 2 + 2 3 + 2 3 =, 科学出版社职教技术出版中心 j=
60 ( ), Kraft.. 0.. Kraft 3.2.4 U = {0,, 2}, l = l 2 =, l 3 = 2, l 4 = l 5 = 4, l 6 = 5. 3 + 3 + 3 2 + 3 4 + 3 4 + 3 5 = 34 + 3 4 + 3 3 + 3 + 3 + 3 5 = 96 243 <, 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,..
3 6 3.3., 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.. 3.3. 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.
62 ( ) l i = log r p i, l i = log r p i.,. 3.3.2 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 ) +. 3.3.,. p i
3 63 3.3.2 S = (X, p(x)), r f 0 H r (p,, p a ) L(S, f) < H r (p,, p a ) +. 3.3.3 3.3., 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,. 3.3.3 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. 3.3.2,, H r ( p). 3.4 Huffman,,., D. A. Huffman 952, Huffman. 科学出版社职教技术出版中心
64 ( ) 3.4. Huffman Huffman,.,,, p = (p, p 2,, p a ). 3.4. 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... 3.4. Huffman () p, Huffman, a = 9. (2) 3,,, Huffman. 7, 0.09,. (3) 4,,, Huffman. 4, 0.38,. Huffman, 3.4.. 3.4. Huffman 0.24 0.24 0.38 0.20 0.20 0.24 0.8 0.8 0.20 0.3 0.3 0.8 0.0 0.0 0.06 0.09 0.05 0.06 0.03 0.0 2. Huffman Huffman () Huffman 4, 0,, 2, 3. 4 Huffman.,
3 65. (2), 0.38, 0, 0.38 0.3, 0.0, 0.09, 0.06 4. 0.3, 0.0, 0.09, 0.06 4 0.38 0, 00, 0, 02, 03. 0.24, 0.20, 0.8 3,, 2, 3. 0.24, 0.20, 0.8, 0.3, 0.0, 0.09, 0.06 7, 2, 3, 00, 0, 02, 03 Huffman. (3), 0.09, 02, 0.09 0.05, 0.03, 0.0 3. 6. 0.05, 0.03, 0.0 3 3 0.09 02, 020, 02, 022. 9 Huffman. Huffman. 3.4.2. 3.4.2 Huffman 0.24 0.24 0.38 0 0.20 2 0.20 2 0.24 0.8 3 0.8 3 0.20 2 0.3 00 0.3 00 0.8 3 0.0 0 0.0 0 0.06 03 0.09 02 0.05 020 0.06 03 0.03 02 0.0 022 3.4.2 Huffman. U = { 0,,, r }. p = (p, p 2,, p a ). Huffman.. Huffman a r,., f(i) = i, i =, 2,, a. a > r. 科学出版社职教技术出版中心
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.
3 67 4. 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. 3.4. (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. 3.5. Huffman 科学出版社职教技术出版中心 Huffman.. 3.5. (Huffman ) Huffman H Huffman. Huffman H. 2k, 2k 2 2k, 2k 2,.
68 ( ), 2j, 2j 2 2j, 2j 2,.,.. 3.5.2 Huffman 3.5.2 (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. 3.5. C = {c, c 2,, c a } S, l(c ) l(c 2 ) l(c a ).. 3.5. 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)
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 +. 3.5.2 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
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) + ]
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)
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 )
3 73, L(S, C) > L(S, D ), D, C. h a {d, d 2,, d a }. (3), C Huffman C S.. 3.5. 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) 3.5.2 Huffman 2j, 2j, C j S j. C = C S = S..,, Huffman. 3.5..2.2.2. Huffman, r = 2., Huffman,,. 3.5. 3.5.2,, Huffman Huffman., 7, 6, 2.49,. 3.5. Huffman 0.32 00 0.32 00 0.32 00 0.38 0.62 0 0.9 0 0.9 0 0.30 0 0.32 00 0.38 0.9 0.9 0.9 0 0.30 0 0. 0 0.9 00 0.9 0.0 000 0. 0 0.09 00 科学出版社职教技术出版中心