唯一可以变长码的判断法

发布者:admin 发布时间:2019-10-24 18:11 浏览次数:

  唯一可以变长码的判断法_数学_自然科学_专业资料。必备知识 . ? 1. 等长码: ? 若一组码中所有码字的码长都相同,即 li=l(i=1,2,…q),则称为等长码。 ? 2. 变长码: ? 若一组码组中所有码字的码长各不相同,则称为 变长码。

  必备知识 . ? 1. 等长码: ? 若一组码中所有码字的码长都相同,即 li=l(i=1,2,…q),则称为等长码。 ? 2. 变长码: ? 若一组码组中所有码字的码长各不相同,则称为 变长码。 ? 3. 非奇异码: ? 若一组码中所有码字都不相同,则称为非奇异码。 ? 4. 奇异码: ? 若一组码中有相同的码字,则称为奇异码。 ? 5. 唯一可译码: ? 若码的任意一串有限长的码符号序列只能唯一地 被译成所对应的信源符号序列,则此码称为唯一 可译码,否则就称为非唯一可译码。 一 二.编码的定义 非分组 码 码 分组码 奇异码 非奇异 非唯一可译 码 非即时码 即时码 (非延长 码 唯一可译码 码) ? ? ? ? 唯一可译码: – 任意有限长的码元序列,只能被唯一地分割成一 个个的码字。 例:{0,10,11}是一种唯一可译码。 任意一串有限长码序列,如100111000,只能被分割 成10,0,11,10,0,0。任何其他分割法都会产生一些 非定义的码字。 奇异码不是唯一可译码 非奇异码 – 唯一可译码 — 码3 100,1,1,1000 – 非唯一可译码 — 码2 10000100 . . ? 必须注意: – Kraft不等式只是用来说明唯一可译码是 否存在,并不能作为唯一可译码的判据。 – 如码字{0,10,010,111}虽然满足Kraft 不等式,但它不是唯一可译码。 惟一可译码的判断准则 – 算法思想:根据惟一可译码的定义可知,当且仅 当有限长的码符号序列能译成两种不同的码字序 列,则此码是非惟一的可译变长码。即如下图情 况发生,其中Ai和Bi都是码字。在下图中,B1一 定是A1的前缀,而A1的尾随后缀一定是另一码 字B2的前缀;又B2的尾随后缀又是其他码字的前 缀。最后,码符号序列的尾部一定是一个码字。 A1 B1 B2 A2 B3 A3 Am Bm 有限长码符号序列译成两种不同的码字序列 惟一可译码的判断方法 – 将码C中所有码字可能的尾随后缀组成一个集 合F,当且仅当集合F中没有包含任一码字,则 可判断此码C为唯一可译变长码。 – 集合F的构造: ? 首先观察码C中最短的码字是否是其它码字的 前缀。若是,将其所有可能的尾随后缀排列出。 而这些尾随后缀又可能是某些码字的前缀,再 将由这些尾随后缀产生的新的尾随后缀列出。 ? 然后再观察这些新的尾随后缀是否是某些码字 的前缀,再将产生的尾随后缀列出。这样,首 先获得由最短的码字能引起的所有尾随后缀。 ? 接着,按照上述将次短的码字…等等,所有码 字可能产生的尾随后缀全部列出。由此得到码 C的所有可能的尾随后缀组成的集合F。 唯一可译变长码的判断法 例题 以 1011001011 10 为例 ,1110 ,1011 ,1101 } 是否是唯一可译码。 判断 C ? {0,10,1100 Ai Bi A1 A2 A3 B3 B4 A4 B1 B2 B5 将码符号中的所有可能的尾随后缀组成一个集合F, 当且仅当集合F中没有包含任一码字,则可判断此码 为唯一可译码。 . ? 因为最短码字为“0”,不是其他码字的前缀,所 以它没有尾随后缀。观察次短码字“10”,它是 码字“1011”的前缀,所以有尾随后缀,将码字 “1011”截去其前缀“10”,得尾随后缀为“11”, 这尾随后缀11又是其他3个码字的前缀部分,由 此再列出所产生的新的尾随后缀为00,10,01.它们 又是一些码字的前缀部分或者某些码字是它们的 前缀部分。如码字“0”是00和01的前缀部分,而 10是码字的“1011”前缀。又是新的尾随后缀为 0,11,1.然后再列出它们的尾随后缀。因为11的尾 随后缀已列出,所以只需列出“1”的尾随后缀, 直到最后全部列完为止。其中出现重复时可略去。 所以得,F={11,00,10,0,1,100,110,011,101}。 可见,F集中“10”和“0”都是码字,故码C不是 唯一可译码 . 码字 00 尾随后缀 0 0 100 110 011 101 0 1 1 10 11 10 01 11 1 ? 例题 码C={110,11,100,00,10}。 计算其尾随后缀: 码字 尾随后缀 11→ 0→0 10→ 0→0 ? 故得F={0}.F集中没有元素师码C的码字, 所以码C是唯一可译码 当然,根据这种测试方法,即时码的尾随 后缀集F是空集,所以即时码一定是唯一可 译码。 唯一可译码的判断方法和步骤 (1)首先观察其是否非奇异码。若是奇异码则一定不是唯 一可译码。 (2)其次计算其是否满足Kraft不等式。肉不满足一定不 是唯一可译码。 (3)将码画成一颗码数图,观察其是否满足即时码的树图 构造,若满足则是唯一可译码。 (4)用Sardinas和Patterson设计的判断方法:计算出码 中所有可能的尾随后缀集合F,观察F中没有包含任一码字。 若无则为唯一可译码;若有则一定不是可译码。 上述判断步骤中,Sardinas和Patterson设计的判断方法 是能确切的判断出是否是唯一的可译码的方法,所有可以 跳过(2)、(3)步骤,直接采用(4)判断法 . ? 例题:设码C={0,10,1100,1110,1011,1101}, 根据上述测试方法,判断是否是唯一可译 码。 ? 解:1. 先看最短的码字:“0”,它不是其 他码字前缀,所以没有尾随后缀。 ? 2. 再观察码字“10”,它是码字“1011” 的前缀,因此有尾随后缀。 ? 所以,集合F={11,00,10,01},其中 “10”为码字,故码C不是唯一可译码。


上一篇:邀请函变“腮红刷”码商集市还有哪些亮瞎眼的    下一篇:联邦高登服务升级加“码”强势打击假货横行