设信源⎭⎬⎫⎩⎨⎧=⎥⎦⎤⎢⎣⎡01.01.015.017.018.019.02.0)(7654321x x x x x x x X P X (1) 求信源熵H(X)； (2) 编二进制香农码； (3) 计算平均码长和编码效率。

解： (1)symbolbit x p x p X H i i i /609.2)01.0log 01.01.0log 1.015.0log 15.017.0log 17.018.0log 18.019.0log 19.02.0log 2.0()(log )()(2222222712=⨯+⨯+⨯+⨯+⨯+⨯+⨯-=-=∑= (2)(3)%1.8314.3609.2)()(14.301.071.0415.0317.0318.0319.032.03)(=====⨯+⨯+⨯+⨯+⨯+⨯+⨯==∑KX H R X H x p k K ii i η对信源⎭⎬⎫⎩⎨⎧=⎥⎦⎤⎢⎣⎡01.01.015.017.018.019.02.0)(7654321x x x x x x x X P X 编二进制费诺码，计算编码效率。

解：%2.9574.2609.2)()(74.201.041.0415.0317.0218.0319.032.02)(=====⨯+⨯+⨯+⨯+⨯+⨯+⨯==∑KX H R X H x p k K ii i η对信源⎭⎬⎫⎩⎨⎧=⎥⎦⎤⎢⎣⎡01.01.015.017.018.019.02.0)(7654321x x x x x x x X P X 编二进制和三进制哈夫曼码，计算各自的平均码长和编码效率。

解：二进制哈夫曼码：%9.9572.2609.2)()(72.201.041.0415.0317.0318.0319.022.02)(=====⨯+⨯+⨯+⨯+⨯+⨯+⨯==∑KX H R X H x p k K ii i η三进制哈夫曼码：%4.913log 8.1609.2log )()(8.1)01.01.015.017.018.019.0(22.01)(22=⨯====+++++⨯+⨯==∑m LK X H R X H x p k K ii i η设信源⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧=⎥⎦⎤⎢⎣⎡12811281641321161814121)(87654321x x x x x x x x X P X (1) 求信源熵H(X)；(2) 编二进制香农码和二进制费诺码；(3) 计算二进制香农码和二进制费诺码的平均码长和编码效率； (4) 编三进制费诺码；(5) 计算三进制费诺码的平均码长和编码效率；解： (1)symbolbit x p x p X H i i i /984.1128log 1281128log 128164log 64132log 32116log 1618log 814log 412log 21)(log )()(22222222812=⨯+⨯+⨯+⨯+⨯+⨯+⨯+⨯=-=∑==127/64 bit/symbol (2)二进制香农码：二进制费诺码：(3)香农编码效率：%100984.1984.1)()(64/127984.17128171281664153214161381241121)(======⨯+⨯+⨯+⨯+⨯+⨯+⨯+⨯==∑KX H R X H x p k K ii i η费诺编码效率：%100984.1984.1)()(984.17128171281664153214161381241121)(=====⨯+⨯+⨯+⨯+⨯+⨯+⨯+⨯==∑KX H R X H x p k K ii i η (4)(5)%3.943log 328.1984.1log )()(328.14128141281364133212161281141121)(22=⨯=⋅===⨯+⨯+⨯+⨯+⨯+⨯+⨯+⨯==∑m K X H R X H x p k K ii i η设无记忆二进制信源⎭⎬⎫⎩⎨⎧=⎥⎦⎤⎢⎣⎡1.09.010)(X P X先把信源序列编成数字0，1，2，……，8，再替换成二进制变长码字，如下表所示。

(1) 验证码字的可分离性；(2) 求对应于一个数字的信源序列的平均长度1K ； (3) 求对应于一个码字的信源序列的平均长度2K ； (4) 计算12K K ，并计算编码效率； (5) 若用4位信源符号合起来编成二进制哈夫曼码，求它的平均码长K ，并计算编码效率。

解：（1）满足Kcraft 不等式：122821491=+⨯=--=-∑i K i；由码树图可见，没有一个码字是其它码字的前缀，码字均在树的终结点。

所以码字可分离。

（2）序列长度、序列概率及二元码长如下表所示：8123456711111111000000数字符号信源符号/.6935911==∑=i i i L p K（3） 数字符号/.bit L p K i ii70862912='=∑=（4）信源符号/.bit K K 4756012=, 此值表示无记忆二元信源采用游程长度编码后每个二元信源需要的平均码长。

信源符号/.)(log )()(bit x p x p X H i i 469021i 2==∑=，%./)(69812==K K X H η（5）4位信源符号的联合概率、Huffman 编码及码长如下表：（码字可以不同，但码长一样）%.)(/./,/.)(29549260449702141614======∑=KX H Symbit K K Sym bit L s p K i i i η有二元平稳马氏链，已知p (0/0) = ，p (1/1) = ，求它的符号熵。

用三个符号合成一个来编写二进制哈夫曼码，求新符号的平均码字长度和编码效率。

解：平稳时马尔科夫状态的概率：⎩⎨⎧=+-+=17018010100)()()().()(.)(S P S P S P S P S p 解得：⎩⎨⎧==525310/)(/)(S P S p 一阶马氏信源的熵：sym bit S S P S Sp S p H j i j i jii /.log log log )|(log )|()(7860725732535251422212111=--+-=-=∑∑==+701130102001800052153023121321.)|(,.)|(,.)|(,.)|(,/)(,/)()|()|()()(=================S S p S S p S S p S S p S p S p S S p S S p S p S S S p%.//.)()()()(14903361621253271253250952502125021125124250491251231254811191====+⨯+++⨯++⨯+⨯==+=∑K Hsym bit L s p K i i i η11010101100111000011110006/2509/25021/25021/25024/25024/25049/25096/25015/25036/25045/25060/25094/250154/250000000111111对题的信源进行游程编码。

若“0”游程长度的截止值为16，“1”游程长度的截止值为8，求编码效率。

解：一阶马氏信源的熵同上题，sym bit H /.786011=+ 二元平稳一阶记忆序列“0”游程的长度概率：∑∞=-=>=⎪⎩⎪⎨⎧=10001500110000011515321i i l i ii l i l p l l p p p l p )(,...,,)(///二元平稳一阶记忆序列“1”游程的长度概率：∑∞=-=>=⎪⎩⎪⎨⎧=111171110111111177321i i l ii i l i l p l l p p p l p )(,...,,)(///“1”游程长度的熵：信源符号/.2),()(log )(log )(log log )(log log )(log )(log log )(log log )(log log )(log log ][log ][][log ][][/////////////////////////////////////////////bit p p H p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p pl p p pp p p pp pp p l p l p l p l p l H i i i i i i i i i i i l l l l l il l l l l i i il ii696111111171111110117111121171111102711711271111211711111127111027117112711711111111210111027117171127111127110111110210111717112711101112101117171127111211121111111111111=--=-----=----+--=-∂∂⋅⋅---=----=--=--=-=∑∑∑∑∑∑=-==--=--=∞=同理，“0”游程长度的熵：信源符号/.),()(][////bit p p H p p l H i 48331101000015000=--= 分别对“0”和“1”游程序列进行Huffman 编码，并分别计算出它们的编码效率。

“0”游程序列的长度、对应得概率、Huffman 编码的二元码长及码字数字符号信源符号/.)())(()())(()()()()()(5113517654312517654312171651514132150013019060302000111500130110017014010120010130120010011502007012004012000111612=+++++++++=+++++++++=+++++++++++++++==∑=p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p L p L i i i %.././][199951134833200===L l H i η“1”游程序列的长度、对应得概率、Huffman 编码的二元码长及码字：数字符号二元码字/.)())((////////'73241432171121111411102111110812=++++++==∑=p p p p p p p p K p K i i i%.../][75987326962211===K l H i η %....][][/][/][][][111019973251136962483322000=++=++=++=∴K L l H l H l H l H l H l H i i i i i i ηηη可见满足10ηηη>>，这里的“0”游程编码效率高，因为游程长度长，而“1”游程编码效率受游程的长度限制显得比“0”游程编码效率略低一些，因此整体的编码效率介于两者之间。