ch3离散无记忆信源的无损编码

第3章离散无记忆信源的无损编码离散无记忆信源的等长编码输出字符表A={a1,…,aK},概率{p1,…,pK}。长度为L的信源源输出序列uL={u1,…,uL}，共有KL种序列。编码字符表B={b1,…,bD}。长度为N的编码字符序列—码字，共DN个码字。要求：LNKDDKLNloglog离散无记忆信源的等长编码Shannon等长信源编码定理熵为H(U)的离散无记忆信源，对信源输出长度为L的输出序列进行编码，假设编码字符表有D个符号，则当时，信源可以实现无损编码。反之若则不存在无损信源编码。DUHLNLlog/])([DUHLNLlog/])([离散无记忆信源的等长编码等长编码的编码速率和编码效率DLNRlogRUH)(存在唯一可译的D元不等长码不存在唯一可译的D元不等长码)(UHR)(UHR离散无记忆信源的不等长编码非奇异码唯一可译码即时码异字头码信源消息码A1码A2码A3码A4a10000a2010110a3100011110a4101101111110离散无记忆信源的不等长编码Kraft不等式存在长度为为n1，n2，…，nK的D元异字头码的充要条件为定理：唯一可译码满足Kraft不等式11KknkD离散无记忆信源的不等长编码Shannon不等长信源编码定理DUHnlog)(1log)(DUHn任一唯一可译的D元不等长码总满足存在唯一可译的D元不等长码满足离散无记忆信源的不等长编码扩展信源(UL)的信源编码定理任一唯一可译的D元不等长码总满足存在唯一可译的D元不等长码满足DULHDUHUnLLlog)(log)()(1log)(1log)()(DULHDUHUnLL离散无记忆信源的不等长编码平均码长任一唯一可译的D元不等长码总满足存在唯一可译的D元不等长码满足LUnnL)(DUHnlog)(LDUHn1log)(离散无记忆信源的不等长编码不等长编码的编码速率和编码效率DnRlogRUH)(存在唯一可译的D元不等长码不存在唯一可译的D元不等长码)(UHR)(UHRHuffman编码二元Huffman编码步骤：将信源的K个符号按概率递减次序排列。将两个概率最小的信源符号合并成一个新符号，新符号的概率值为两个信源符号概率值的和。依次类推，直至信源最后只剩下一个符号。将每次合并的两个信源符号分别用0和1表示。由后向前返回，就得到各信源符号对应的码字。D元Huffman编码步骤：增补D-M个概率为0的虚拟符号，其中M由下式给出：K=(D-1)i+M将信源的K+(D-M)个符号按概率递减次序排列。将D个概率最小的信源符号合并成一个新符号，新符号的概率值为D个信源符号概率值的和。依次类推，直至信源最后只剩下一个符号。将每次合并的D个信源符号分别用0,1,…，D-1表示。从后向前返回，就得到各信源符号对应的码字。Shannon编码将信源发出的符号按概率递减次序排列。计算第k个信源符号的累加概率：将累加概率Pk变换成二进制数，取小数点后lk位数作为第k个信源符号的码字,码长lk可由下式确定：式中：—取大于或等于x的最小整数。11kiikpP)(logkkuplx信源符号iu概率)(iup累加概率ip)(logiup码字长度il二元码字1u0.200.002.3430002u0.190.202.4130013u0.180.392.4830114u0.170.572.5631005u0.150.742.7431016u0.100.893.34411107u0.010.996.6671111110Fano编码将信源符号按其出现的概率由大到小依次排列。将依次排列的信源符号分为两大组，使两个组的概率之和尽量相同。一组指定0，另一组指定1。将每一大组的信源符号进一步再分成两组，使划分后两个组的概率之和尽量相同。一组指定0，另一组指定1。如此重复，直至每个组只剩下一个信源符号为止。信源符号所对应的码字即为费诺码。125.0125.025.05.0)(4321uuuuUPU08.016.018.022.004.032.0)(654321uuuuuuUPUShannon-Fano-Elias编码设信源定义将转换成二进制小数的形式，取小数点后位作为的码字。其中)()()()()(321321nnupupupupuuuuUPU)(21)()(11kkiikupupuF)(kuF)(kulku1)(1log)(kkupul125.0125.05.025.0)(4321uuuuUPU符号概率F(uk)F(uk))(kuF二进制码长)(kul码字u10.250.250.1250.0013001u20.50.750.5000.100210u30.1250.8750.81250.110141101u40.1251.00.93750.1111411111)(1log)(kkupul)(21)()(11kkiikupupuF算术编码（AC）初始时设S=Φ，F(Φ)＝0，p(Φ)＝1。计算序列的积累概率和序列的概率。计算码长将F(S)写成二进制数的形式,取其前L位作为序列S的码字；如果小数点后有多于L位数据，就进位到第L位作为序列S的码字。11)()(kiikupuF)()()()()()()(rrrrupSpSupuFSpSFSuF)(1logSpL设二元无记忆信源序列F（S）P（S）L序列的码字Φ01010.010.1111110.01110.1001111110.1001010.01101121111100.1001010.0001101141010111010.10011010110.0001010001410101110100.10011010110.000001010001610011111101010.100111000000010.0000001111001171001111111010110.10011100111101110.00000010110110017100111175.025.010)(UPU求信源序列11101011的算术编码。