00 01 10 11 0.81 0.09 0.0ቤተ መጻሕፍቲ ባይዱ 0.01
如取00，01，10编码，概率和为：0.99
扩展N＝3 000 001 010 100 101 110 111
0.729 0.081 0.081 0.081 0.009 0.009 0.001
取≥两位0的编码，概率为0.972；取前7个编码，概率为：0.999
这就要求码字总数不小于MG就行，即
rl MG
M G2N[H(s)] rl
llor gN [H (s)] l H (s)
N lorg
⑾
pEp(G )(N,]D [N I(s2i)] ⑿
满足式⑾的条件下，N时，译码错误概率 pE 0
但当
l H (s)2 rl 2N [H (s)2]
N lorg
⒀
由MG的下界式⑽可知，这种情况下选取的码字总数小
1002 取≥3个0的编码 (05个)，概率为0.9477； 1003 取≥2个0的编码 (11个)，概率为0.9963； 1004 取≥1个0的编码 (15个)，概率为0.9999
§4.3 变 长 码
变长码可以在N不很大时就可编出效率很高而且
无失真的码；变长码也必须是唯一可译码才能实
现无失真编码。
如取不等号，则为非用尽的即时码，∵即时码是唯一可译
码的一类子码，所以定理的充分性也就得到了证明。
必要性证明：已知唯一可译码的码长为 l1,l2,,lq ，设n是一个 任意的正整数，考虑等式：
qr li n r l1 r l2 r lqnq
qq
r (li1 li2 lin )
其中正确的译码概率： pE 1pE p[G 中 rl个 a i] 1 p E 2 N
pE 12N
⒃
N pE 1
等长信源编码定理
一个熵为H（S）的离散无记忆信源，若对信源
长为N的符号序列进行等长编码，设码字是从r个
字母的码符号集中选取 l 个字母组成，对于任
意 ，0 只要满足
l N
H，l(osg)当r
式⒆为各
r
j
项之和，
li1,都 ,可lin 取
而l1,l2,,lq, 又都l1可,取,lq值,
为序话码列说qA n中，j 码就l三m ，符是in个所号把1,2码以,总总 w字:,相长长{l1m,所0a同相度x1,0组数等为0}合1值的j的成j码的序的字出列长序现的度列不数不止目止的一记一序次为个列，，，共也例令有就如为7是种由j在＝个：唯6A，j个一码可换字译句
除一些无效字符组合，扩展信源中的符号总数 所需q编N
码的码字个数可大大下降。
设离散无记忆信源： sN: a1, p(a):p(a1),
aqN p(aqQ)
ai (si1,si2,siN)， i1,,qN i1,i2,,iN1,q
N
p(ai ) pik i 1,2,,qN k1
N
N
I(a i) lop (g a i) lop ig k I(sik )
于集G中可能有的信源序列数，将有相应码字对应的信源
序列的概率和记作 p[G中rl个ai]，它必然满足：
p[G 中 rl个 ai]rl•m ai Gp a(aix )
⒁
p [ G 中 r l 个 a i] 2 N [ H ( s ) 2 ]• 2 N [ H ( s ) ] 2 N
⒂
rl MG 造成有些序列没有码字对应，译码时必出错，
1 01 001，1 001 01，01 1 001，01 001 1，001 1 01，001 01 1，01 01 01
a1 a2 a3 ，a1 a3 a2， a2 a1 a3， a2 a3 a1 ， a3 a1 a2， a3 a2 a1，a2 a2 a2
因将此：代式入（上1式9）：可以合并： Aj r j
码长。
共n个码字
1
2
n 1 n
l i1
li2
令： li1li2linj
lin 1
l in
i1in1,2,,q
j的值是个码字组成的码字序列的总长，也就是n个信源符 号组成的序列所对应的码符号序列的总长度。因为讨论的
是变长码，所以设 l i 的取值范围为：
lmi nli lmax
nm l injnm l 则ax j的lm取in值1范围n为jnlmax
s 1 s 1s 1 s 2 s 1 s 3 s 1 s 4 s 2 s 1 s 2 s 2 s 2 s 3 s 2 s 4 s 3 s 1 s 3 s 2 s 3 s 3 s 3 s 4s4s1 s4s2 s4s3 s4s4 001 00 0 00 0 10 10 0 11 0 1 0 0 0 0 0 0 0 0 1 0 0 01 0 0 0 0 0 010 00 011 1001000101
• 充分性证明：假定满足不等式的码长为 l1,l2,，,lq 在q个码字
中可能有长度相同的码字。设码长为1的有n1个，长度为2
的有n2个，长度为j的有nj个，…，最大长度为l 的有nl个，
此处n为节点的阶数，（即n次扩展），此节点中的码字长
度为ni；ni为长度为i的码字个数。有：
l
ni q
一共q个码字，全为1时， l ，q 满足不等式 ： i1
i 1
i1 1 i2 1 in 1
q
q
r li1 r li n r l 1 r l2 r lq r l 1 r lq
i 1 1
in 1
⒆
右边共有 q n 项，代表了n个码字组成的码字序列的总数。
每项均对应于n个码字组成的一个码字序列，如下图，图
中1、2、…、n表明码字的序号，li1,li2,lln 分别为对应的
若通过一个二进制信道进行传输，为使信源适合信道的传输，
将用0,1符号序列表示，码符号集为
s x，[0序,1]列与 i的对应
形式可有多种，得不同的码。
码1 00 01 10 11 码2 0 01 001111
码的基本分类： 固定长度码（等长码） 变长码：各码字的码长不等 非奇异码：码中所有码字都不相同 奇异码：有同码
n 1 r l 1 n 2 r l 2 n l 1 r n l r l n l r l n 1 r l 1 n 2 r l 2 n l 1 r
移项后为：
由于都为正整数，将⒅左边去掉一项（等号去掉），有：
l 1
ni r i 1
同理得：
i 1
nl 1 r l 1 n1r l 2 n 2 r l 3 nl 2 r nl2 r l2 n1r l3 n2 r l4 nl3r
扩展N＝4
0000 0001 0010 0011 0100 0101 0110 0111
0.6561 0.0729 0.0729 0.0081 0.0729 0.0081 0.0081 0.0009
1000 1001 1010 1011 1100 1101 1110 1111
1001 0.0729 0.0081 0.0081 0.0009 0.0081 0.0009 0.0009 0.0001
单义（唯一）可译定理：设信源符号集为：s[s1s2，sq码] 符号
集为：
x ，[x又1x2 设x码r] 字为
，其w分1w2别 对wq 应的码长
为； ， 则l1l2存 l在q 唯q 一可译码的充分必要条件是：
r li ⒄1
码长
li
i 1
，码符号集中符号个数r，信源符号个数q，称作kraft
不等式。
说明：唯一可译码一定满足不等式，反之，满足不等 式的码不一定是唯一可译码。
由切贝雪夫不等式： pI(ai)N(H s)ND ([N I(a)i2)]
p I(N a i)H (s) D [I(si)/]N 2(N ,)
⑴
方差为定值
表明 N l i m (N,)N l i m D [N I(s2i)]0
I (ai ) / N 依概率收敛于H (s)
Gai
:
I(ai)H(s) N
q
rli rl1r－ l2rlj rlq 1
i 1
考虑有码长相等的情况，合并同类项后得：
l
⒅ n 1 r 1 n 2 r 2 n lr l 1 n ir i 1 i 1
l
两边同乘以 r ：l nirli rl i1
n l r l n 1 r l 1 n 2 r l 2 n l 1 r
码的N次扩展： s 2 [ a 1 s 1 s 1 ; a 2 s 1 s 2 , a 3 s 1 s 3 ; , a 1 6 s 4 s 4 ] 码2的二次扩展码为：
a 1 a 2 a 3 a 4 a 5 a 6 a 7 a 8 a 9 a 10a 16 000 01 0 00 1 0 1 1 1 0 1 0 1 00 11 0 01 0 0 1 1 0 1 01 1 00 1 1 0 1 1 11
有重码，非唯一可译码 等长非奇异码一定单义可译
等长编码条件： q r l ，满足此条件，才有可能无
重码（非奇异）；扩展后：qN rl Nloqgllorg
l log q N log r
N 1 lloqg/lorg
l ：平均每个信源符号所需要的码符号（元）个数 N 考虑到符号出现的概率以及符号之间的依赖性 。再去
m i Gp i(nai)2N[H(s)]
MG2N[H(s)]
上界 ⑻
1 ( N ,) p ( G ) M G • m a x p ( a i) ⑼
mp a(ax i)2N [H (s) ]
下界 M G [1 (N ,)2 ] N [H (⑽s) ]
我们可以只对集G中MG个信源序列进行一一对应的等长编码，
时，N几乎 可实现无