唯一可以变长码的判断法

1、必备知识必备知识.一一 1. 等长码：等长码： 若一组码中所有码字的码长都相同，即若一组码中所有码字的码长都相同，即li=l(i=1,2,q)，则称为等长码。，则称为等长码。 2. 变长码：变长码： 若一组码组中所有码字的码长各不相同，则称为若一组码组中所有码字的码长各不相同，则称为变长码。变长码。 3. 非奇异码：非奇异码： 若一组码中所有码字都不相同，则称为非奇异码。若一组码中所有码字都不相同，则称为非奇异码。 4. 奇异码：奇异码： 若一组码中有相同的码字，则称为奇异码。若一组码中有相同的码字，则称为奇异码。 5. 唯一可译码：唯一可译码： 若码的任意一串有限长的码符号序列只能唯一地若码

2、的任意一串有限长的码符号序列只能唯一地被译成所对应的信源符号序列，则此码称为唯一被译成所对应的信源符号序列，则此码称为唯一可译码，否则就称为非唯一可译码。可译码，否则就称为非唯一可译码。二二.编码的定义编码的定义码码非分组非分组码码 分组码分组码奇异码奇异码 非奇异非奇异码码 非唯一可译非唯一可译码码 唯一可译码唯一可译码非即时码非即时码 即时码即时码 (非延长非延长码码) . 唯一可译码唯一可译码： 任意有限长的码元序列任意有限长的码元序列,只能被唯一地分割成一只能被唯一地分割成一个个的码字。个个的码字。 例：例：0,10,11是一种唯一可译码。是一种唯一可译码。 任意一串有限长码序列任意一

3、串有限长码序列,如如100111000,只能被分割只能被分割成成10,0,11,10,0,0。任何其他分割法都会产生一些。任何其他分割法都会产生一些非定义的码字。非定义的码字。 奇异码不是唯一可译码奇异码不是唯一可译码 非奇异码非奇异码 唯一可译码唯一可译码 码码3 100,1,1,1000 非唯一可译码非唯一可译码 码码2 10000100. Kraft不等式只是用来说明唯一可译码是不等式只是用来说明唯一可译码是否存在否存在,并不能作为唯一可译码的判据。并不能作为唯一可译码的判据。 如码字如码字0，10，010，111虽然满足虽然满足Kraft不等式不等式,但它不是唯一可译码。但它不是唯一可

4、译码。惟一可译码的判断准则惟一可译码的判断准则 算法思想：根据惟一可译码的定义可知，当且仅算法思想：根据惟一可译码的定义可知，当且仅当有限长的码符号序列能译成两种不同的码字序当有限长的码符号序列能译成两种不同的码字序列，则此码是非惟一的可译变长码。即如下图情列，则此码是非惟一的可译变长码。即如下图情况发生，其中况发生，其中Ai和和Bi都是码字。在下图中，都是码字。在下图中，B1一一定是定是A1的前缀，而的前缀，而A1的尾随后缀一定是另一码的尾随后缀一定是另一码字字B2的前缀；又的前缀；又B2的尾随后缀又是其他码字的前的尾随后缀又是其他码字的前缀。最后，码符号序列的尾部一定是一个码字。缀。最后，

5、码符号序列的尾部一定是一个码字。A1A2A3AmB1B2B3Bm有限长码符号序列译成两种不同的码字序列惟一可译码的判断方法惟一可译码的判断方法 将码将码C中所有码字可能的尾随后缀组成一个集中所有码字可能的尾随后缀组成一个集合合F，当且仅当集合，当且仅当集合F中没有包含任一码字，则中没有包含任一码字，则可判断此码可判断此码C为唯一可译变长码。为唯一可译变长码。 集合集合F的构造：的构造： 首先观察码首先观察码C中最短的码字是否是其它码字的中最短的码字是否是其它码字的前缀。若是，将其所有可能的尾随后缀排列出。前缀。若是，将其所有可能的尾随后缀排列出。而这些尾随后缀又可能是某些码字的前缀，再而这些尾

6、随后缀又可能是某些码字的前缀，再将由这些尾随后缀产生的新的尾随后缀列出。将由这些尾随后缀产生的新的尾随后缀列出。 然后再观察这些新的尾随后缀是否是某些码字然后再观察这些新的尾随后缀是否是某些码字的前缀，再将产生的尾随后缀列出。这样，首的前缀，再将产生的尾随后缀列出。这样，首先获得由最短的码字能引起的所有尾随后缀。先获得由最短的码字能引起的所有尾随后缀。 接着，按照上述将次短的码字接着，按照上述将次短的码字等等，所有码等等，所有码字可能产生的尾随后缀全部列出。由此得到码字可能产生的尾随后缀全部列出。由此得到码C的所有可能的尾随后缀组成的集合的所有可能的尾随后缀组成的集合F。唯一可译变长码的判断法

7、唯一可译变长码的判断法将码符号中的所有可能的尾随后缀组成一个集合将码符号中的所有可能的尾随后缀组成一个集合F, 当且仅当集合当且仅当集合F中没有包含任一码字，则可判断此码中没有包含任一码字，则可判断此码为唯一可译码。为唯一可译码。例题判断 是否是唯一可译码。1101,1011,1110,1100,10, 0CiAiB1A2A3A4A1B2B3B4B5B101011001011以为例. 因为最短码字为因为最短码字为“0”，不是其他码字的前缀，所，不是其他码字的前缀，所以它没有尾随后缀。观察次短码字以它没有尾随后缀。观察次短码字“10”，它是，它是码字码字“1011”的前缀，所以有尾随后缀，将码字

8、的前缀，所以有尾随后缀，将码字“1011”截去其前缀截去其前缀“10”，得尾随后缀为，得尾随后缀为“11”，这尾随后缀这尾随后缀11又是其他又是其他3个码字的前缀部分，由个码字的前缀部分，由此再列出所产生的新的尾随后缀为此再列出所产生的新的尾随后缀为00,10,01.它们它们又是一些码字的前缀部分或者某些码字是它们的又是一些码字的前缀部分或者某些码字是它们的前缀部分。如码字前缀部分。如码字“0”是是00和和01的前缀部分，而的前缀部分，而10是码字的是码字的“1011”前缀。又是新的尾随后缀为前缀。又是新的尾随后缀为0,11,1.然后再列出它们的尾随后缀。因为然后再列出它们的尾随后缀。因为11

9、的尾的尾随后缀已列出，所以只需列出随后缀已列出，所以只需列出“1”的尾随后缀，的尾随后缀，直到最后全部列完为止。其中出现重复时可略去。直到最后全部列完为止。其中出现重复时可略去。 所以得，所以得，F=11,00，10,0,1,100，110,011,101。可见，可见，F集中集中“10”和和“0”都是码字，故码都是码字，故码C不是不是唯一可译码唯一可译码.101100100101110100110011101011码字尾随后缀 例题码C=110,11,100,00,10。计算其尾随后缀： 码字 11 10尾随后缀0000 故得F=0.F集中没有元素师码C的码字，所以码C是唯一可译码 当然，根据

10、这种测试方法，即时码的尾随后缀集F是空集，所以即时码一定是唯一可译码。 唯一可译码的判断方法和步骤 （1）首先观察其是否非奇异码。若是奇异码则一定不是唯一可译码。 （2）其次计算其是否满足Kraft不等式。肉不满足一定不是唯一可译码。 （3）将码画成一颗码数图，观察其是否满足即时码的树图构造，若满足则是唯一可译码。 （4）用Sardinas和Patterson设计的判断方法：计算出码中所有可能的尾随后缀集合F，观察F中没有包含任一码字。若无则为唯一可译码；若有则一定不是可译码。 上述判断步骤中，Sardinas和Patterson设计的判断方法是能确切的判断出是否是唯一的可译码的方法，所有可以跳过（2）、（3）步骤，直接采用（4）判断法. 例题：设码C=