4.2码的唯一可译性信源信源WW0U信信无损确定信道编码译码宿源（等效）Fff为一一对应的变换，只是无失真编码的必要条件并不充分；要保证将码元序列无失真地恢复成信源符号序列还要求编出的码自身具有独特的结构。有实用价值的码应该具有唯一可译性，即能从码字序列（也是码元序列）唯一地恢复成信源符号序列·举例：下雨天留客天留我不留
1 4.2 码的唯一可译性 •f 为一一对应的变换，只是无失真编码的必要条件， 并不充分； •要保证将码元序列无失真地恢复成信源符号序列， 还要求编出的码自身具有独特的结构。 •有实用价值的码应该具有唯一可译性，即能从码字 序列（也是码元序列）唯一地恢复成信源符号序列。 •举例：下雨天留客天留我不留 f 1 f 无损确定信道 （等效） U 信源 编码 信 源 W 信 宿 信源 译码 W U ˆ
1、唯一可译码(UDC,UniquelyDecodableCode）·唯一可译码（UDC）：该码的码字组成的任意有限长码字序列（也是码元序列）都能恢复成唯一的信源序列。否则称为非唯一可译码。·码是唯一可译码的充分必要条件是：由码中的码字组成的任意有限长的码字序列（也是码元序列），都能唯一划分成一个个的码字，且任一码字只与唯一一个信源符号对应。·奇异码：含相同码字的码。否则称为非奇异码·非续长码：码中任一码字都不是另一码字的续长（延长）。否则为续长码。·非及时码：如果接收端收到一个完整的码字后，不能立即译码，还需等下一个码字开始接收后才能判断是2否可以译码。否则为及时码或立即码
2 1、唯一可译码 （UDC，Uniquely Decodable Code） •唯一可译码（UDC）：该码的码字组成的任意有限长 码字序列（也是码元序列）都能恢复成唯一的信源序 列。否则称为非唯一可译码。 •码是唯一可译码的充分必要条件是：由码中的码字组 成的任意有限长的码字序列（也是码元序列），都能 唯一划分成一个个的码字，且任一码字只与唯一一个 信源符号对应。 •奇异码：含相同码字的码。否则称为非奇异码。 •非续长码：码中任一码字都不是另一码字的续长(延长)。 否则为续长码。 •非及时码：如果接收端收到一个完整的码字后，不能 立即译码，还需等下一个码字开始接收后才能判断是 否可以译码。否则为及时码或立即码
5种不同的码UWsW,WP(u,)W,W3W3:1/20000010ui100100101000010011/4uz1,00,10,01→u,uu1/8100110110011us10,01,001→ugu,1/8111110111111us1,00,1,00,1→uu,uu,uW：定长码。非奇异码。非续长码。定长非奇异码肯定是UDCW：定长码。奇异码。奇异码肯定不是UDCWs：变长码。非奇异码。续长码。非及时码。不是UDCW：变长码。非奇异码。非续长码。及时码。非续长码肯定是UDC是UDCW：变长码。非奇异码。续长码。非及时码。3
3 5种不同的码 U P u W W i W W W u u u u 1 2 4 3 5 1 2 3 4 ( ) 1 2 00 00 1 0 0 1 4 01 00 00 10 01 1 8 10 10 01 110 011 1 8 11 11 10 111 111 W1 : 定长码。 W3 : 变长码。 奇异码。 定长非奇异码肯定是UDC u u u u u u u u u u u u u 1 2 4 3 4 3 2 1 1 2 1 2 1 1,00,10,01 1001001 10,01,00,1 1,00,1,00,1 W2 : 定长码。 W4 : 变长码。 W5 : 变长码。 非奇异码。 非奇异码。 非奇异码。 非奇异码。 续长码。 非续长码。 续长码。 及时码。 非及时码。 奇异码肯定不是UDC 不是UDC 非续长码肯定是UDC 是UDC 非及时码。 非续长码。 W3： 1001001
唯一可译码非奇异码定长非奇异码非续长码奇异码码非唯一可译码非奇异码定长非奇异码唯一可译码变长非续长码（部分）变长续长码
4 唯一可译码 定长非奇异码 非续长码 非 奇 异 码 码 奇异码 非奇异码 非唯一可译码 唯一可译码 定长非奇异码 变长非续长码 （部分）变长续长码
2、码树W4 =111W2W3AW3WW.=011W4三阶节点W2W2 =01二阶节点W111=0一阶节点CW,=(00,01,10,11W=0,10,110,111W,={0,01,011,111)·码树从树根开始向上长出树枝，树枝代表码元，树枝与树枝的交点叫做节点。·r进制码树：码元个数为r，各节点（含树根）向上长出的树枝数不大于1阶节点：经过I根树枝才能到达的节点。·终端节点或端点：向上不长出树枝的节点。·整树：r进制码树各节点（包括树根）向上长出的树枝数均等于r。·码字：与码树上的节点对应，组成该码字的码元就是从树根开始到该节点所经过的树枝（或码元）。5·非续长码：所有码字均处于终端节点，即端点上
5 2、码树 • 码树从树根开始向上长出树枝，树枝代表码元，树枝与树枝的交点叫 做节点。 • r 进制码树：码元个数为r ，各节点(含树根)向上长出的树枝数不大于 r 。 • l 阶节点：经过l 根树枝才能到达的节点。 • 终端节点或端点：向上不长出树枝的节点。 • 整树：r进制码树各节点(包括树根)向上长出的树枝数均等于r。 • 码字：与码树上的节点对应，组成该码字的码元就是从树根开始到该 节点所经过的树枝(或码元)。 • 非续长码：所有码字均处于终端节点，即端点上。 0 1 0 1 w4 w3 w2 w1 1 0 0 0 0 1 1 1 w4 w3 w2 w1 一阶节点 0 1 1 1 4 w 111 1 w 0 1 1 3 w 0112 w 01 二阶节点 三阶节点 W1={00, 01, 10, 11} W4={0, 10, 110, 111} W5={0, 01, 011, 111}
3、Kraft不等式非续长码存在性定理：对于任一r进制非续长码各码字的码长为li,l2,，l必须满足Kraft不等式：Zr-li≤1反过来，若上式成立，就一定能构造一个r进制非续长码。·不满足Kraft不等式的码肯定不是非续长码：满足Kraft不等式的码也不一定是非续长码根据满足Kraft不等式的码长集合可构造出一个非续长码；上述定理对唯一可译码仍然成立
6 3、Kraft不等式 • 不满足Kraft 不等式的码肯定不是非续长码； • 满足Kraft 不等式的码也不一定是非续长码； • 根据满足Kraft 不等式的码长集合可构造出一个 非续长码； • 上述定理对唯一可译码仍然成立。 非续长码存在性定理：对于任一 r 进制非续长码， 各码字的码长为{l1 , l2 , . , lq }必须满足Kraft 不等式: 反过来，若上式成立，就一定能构造一个 r 进制非 续长码。 1 i 1 q l i r
唯一可译码存在性定理：对于任一r进制唯一可译码（UDC），各码字的码长为(li,l，…，l，必须满足Kraft不等式：r-li≤1反过来，若上式成立，就一定能构造一个r进制唯一可译码（UDC）。Kraft不等式是唯一可译码存在的充要条件：如果码是唯一可译码，则必定满足该不等式·如果满足Kraft不等式，则这种码长的唯一可译码一定存在；但不表示所有满足不等式的码一定是唯一可译码。7
7 •Kraft 不等式是唯一可译码存在的充要条件； •如果码是唯一可译码，则必定满足该不等式； •如果满足Kraft 不等式，则这种码长的唯一可译码 一定存在； •但不表示所有满足不等式的码一定是唯一可译码。 唯一可译码存在性定理：对于任一 r 进制唯一可译 码（UDC），各码字的码长为{l1 , l2 , . , lq }，必须 满足Kraft 不等式： 反过来，若上式成立，就一定能构造一个 r 进制唯 一可译码（UDC）。 1 i 1 q l i r