问答题
证明一个码C是唯一可译码当且仅当其k次扩展
Ck(x1,x2,…,xk)=C(x1)C(x2)…C(xk)
对任意的k≥1都是从Xk到D*的一一映射。
【正确答案】我们利用反证法。假设对于某些k来说,Ck不是从Xk到D*的一一映射,则需证明C不是唯一可译码。
根据假设,必然存在两个不同的序列(x1,…,xk)和(y1,…,yk)满足:
Ck(x1,…,xk)=C(x1)…C(xk)=C(y1)…C(yk)=Ck(y1,…,yk) (5.10)
反过来,如果C不是唯一可译码,那么根据唯一可译码的定义,必然存在两个不同的序列(x1,…,xi)和(y1,…,yj)满足:
C(x1)C(x2)…C(xi)=C(y1)C(y2)…C(yj) (5.11)
将这两个序列按照不同的顺序串接起来,得到:
C(x1)…C(xi)C(y1)…C(yj)=C(y1)…C(yj)C(x1)…C(xi) (5.12)
这表明对于k=i+j来说Ck不是Xk到D*的一一映射。
【答案解析】