唯一可以變長碼的判斷法

1、必備知識必備知識.一一 1. 等長碼：等長碼： 若一組碼中所有碼字的碼長都相同，即若一組碼中所有碼字的碼長都相同，即li=l(i=1,2,q)，則稱為等長碼。，則稱為等長碼。 2. 變長碼：變長碼： 若一組碼組中所有碼字的碼長各不相同，則稱為若一組碼組中所有碼字的碼長各不相同，則稱為變長碼。變長碼。 3. 非奇異碼：非奇異碼： 若一組碼中所有碼字都不相同，則稱為非奇異碼。若一組碼中所有碼字都不相同，則稱為非奇異碼。 4. 奇異碼：奇異碼： 若一組碼中有相同的碼字，則稱為奇異碼。若一組碼中有相同的碼字，則稱為奇異碼。 5. 唯一可譯碼：唯一可譯碼： 若碼的任意一串有限長的碼符號序列只能唯一地若碼

2、的任意一串有限長的碼符號序列只能唯一地被譯成所對應的信源符號序列，則此碼稱為唯一被譯成所對應的信源符號序列，則此碼稱為唯一可譯碼，否則就稱為非唯一可譯碼?？勺g碼，否則就稱為非唯一可譯碼。二二.編碼的定義編碼的定義碼碼非分組非分組碼碼 分組碼分組碼奇異碼奇異碼 非奇異非奇異碼碼 非唯一可譯非唯一可譯碼碼 唯一可譯碼唯一可譯碼非即時碼非即時碼 即時碼即時碼 (非延長非延長碼碼) . 唯一可譯碼唯一可譯碼： 任意有限長的碼元序列任意有限長的碼元序列,只能被唯一地分割成一只能被唯一地分割成一個個的碼字。個個的碼字。 例：例：0,10,11是一種唯一可譯碼。是一種唯一可譯碼。 任意一串有限長碼序列任意一

3、串有限長碼序列,如如100111000,只能被分割只能被分割成成10,0,11,10,0,0。任何其他分割法都會產(chǎn)生一些。任何其他分割法都會產(chǎn)生一些非定義的碼字。非定義的碼字。 奇異碼不是唯一可譯碼奇異碼不是唯一可譯碼 非奇異碼非奇異碼 唯一可譯碼唯一可譯碼 碼碼3 100,1,1,1000 非唯一可譯碼非唯一可譯碼 碼碼2 10000100. Kraft不等式只是用來說明唯一可譯碼是不等式只是用來說明唯一可譯碼是否存在否存在,并不能作為唯一可譯碼的判據(jù)。并不能作為唯一可譯碼的判據(jù)。 如碼字如碼字0，10，010，111雖然滿足雖然滿足Kraft不等式不等式,但它不是唯一可譯碼。但它不是唯一可

4、譯碼。惟一可譯碼的判斷準則惟一可譯碼的判斷準則 算法思想：根據(jù)惟一可譯碼的定義可知，當且僅算法思想：根據(jù)惟一可譯碼的定義可知，當且僅當有限長的碼符號序列能譯成兩種不同的碼字序當有限長的碼符號序列能譯成兩種不同的碼字序列，則此碼是非惟一的可譯變長碼。即如下圖情列，則此碼是非惟一的可譯變長碼。即如下圖情況發(fā)生，其中況發(fā)生，其中Ai和和Bi都是碼字。在下圖中，都是碼字。在下圖中，B1一一定是定是A1的前綴，而的前綴，而A1的尾隨后綴一定是另一碼的尾隨后綴一定是另一碼字字B2的前綴；又的前綴；又B2的尾隨后綴又是其他碼字的前的尾隨后綴又是其他碼字的前綴。最后，碼符號序列的尾部一定是一個碼字。綴。最后，

5、碼符號序列的尾部一定是一個碼字。A1A2A3AmB1B2B3Bm有限長碼符號序列譯成兩種不同的碼字序列惟一可譯碼的判斷方法惟一可譯碼的判斷方法 將碼將碼C中所有碼字可能的尾隨后綴組成一個集中所有碼字可能的尾隨后綴組成一個集合合F，當且僅當集合，當且僅當集合F中沒有包含任一碼字，則中沒有包含任一碼字，則可判斷此碼可判斷此碼C為唯一可譯變長碼。為唯一可譯變長碼。 集合集合F的構造：的構造： 首先觀察碼首先觀察碼C中最短的碼字是否是其它碼字的中最短的碼字是否是其它碼字的前綴。若是，將其所有可能的尾隨后綴排列出。前綴。若是，將其所有可能的尾隨后綴排列出。而這些尾隨后綴又可能是某些碼字的前綴，再而這些尾

6、隨后綴又可能是某些碼字的前綴，再將由這些尾隨后綴產(chǎn)生的新的尾隨后綴列出。將由這些尾隨后綴產(chǎn)生的新的尾隨后綴列出。 然后再觀察這些新的尾隨后綴是否是某些碼字然后再觀察這些新的尾隨后綴是否是某些碼字的前綴，再將產(chǎn)生的尾隨后綴列出。這樣，首的前綴，再將產(chǎn)生的尾隨后綴列出。這樣，首先獲得由最短的碼字能引起的所有尾隨后綴。先獲得由最短的碼字能引起的所有尾隨后綴。 接著，按照上述將次短的碼字接著，按照上述將次短的碼字等等，所有碼等等，所有碼字可能產(chǎn)生的尾隨后綴全部列出。由此得到碼字可能產(chǎn)生的尾隨后綴全部列出。由此得到碼C的所有可能的尾隨后綴組成的集合的所有可能的尾隨后綴組成的集合F。唯一可譯變長碼的判斷法

7、唯一可譯變長碼的判斷法將碼符號中的所有可能的尾隨后綴組成一個集合將碼符號中的所有可能的尾隨后綴組成一個集合F, 當且僅當集合當且僅當集合F中沒有包含任一碼字，則可判斷此碼中沒有包含任一碼字，則可判斷此碼為唯一可譯碼。為唯一可譯碼。例題判斷 是否是唯一可譯碼。1101,1011,1110,1100,10, 0CiAiB1A2A3A4A1B2B3B4B5B101011001011以為例. 因為最短碼字為因為最短碼字為“0”，不是其他碼字的前綴，所，不是其他碼字的前綴，所以它沒有尾隨后綴。觀察次短碼字以它沒有尾隨后綴。觀察次短碼字“10”，它是，它是碼字碼字“1011”的前綴，所以有尾隨后綴，將碼字

8、的前綴，所以有尾隨后綴，將碼字“1011”截去其前綴截去其前綴“10”，得尾隨后綴為，得尾隨后綴為“11”，這尾隨后綴這尾隨后綴11又是其他又是其他3個碼字的前綴部分，由個碼字的前綴部分，由此再列出所產(chǎn)生的新的尾隨后綴為此再列出所產(chǎn)生的新的尾隨后綴為00,10,01.它們它們又是一些碼字的前綴部分或者某些碼字是它們的又是一些碼字的前綴部分或者某些碼字是它們的前綴部分。如碼字前綴部分。如碼字“0”是是00和和01的前綴部分，而的前綴部分，而10是碼字的是碼字的“1011”前綴。又是新的尾隨后綴為前綴。又是新的尾隨后綴為0,11,1.然后再列出它們的尾隨后綴。因為然后再列出它們的尾隨后綴。因為11

9、的尾的尾隨后綴已列出，所以只需列出隨后綴已列出，所以只需列出“1”的尾隨后綴，的尾隨后綴，直到最后全部列完為止。其中出現(xiàn)重復時可略去。直到最后全部列完為止。其中出現(xiàn)重復時可略去。 所以得，所以得，F(xiàn)=11,00，10,0,1,100，110,011,101。可見，可見，F(xiàn)集中集中“10”和和“0”都是碼字，故碼都是碼字，故碼C不是不是唯一可譯碼唯一可譯碼.101100100101110100110011101011碼字尾隨后綴 例題碼C=110,11,100,00,10。計算其尾隨后綴： 碼字 11 10尾隨后綴0000 故得F=0.F集中沒有元素師碼C的碼字，所以碼C是唯一可譯碼 當然，根據(jù)

10、這種測試方法，即時碼的尾隨后綴集F是空集，所以即時碼一定是唯一可譯碼。 唯一可譯碼的判斷方法和步驟 （1）首先觀察其是否非奇異碼。若是奇異碼則一定不是唯一可譯碼。 （2）其次計算其是否滿足Kraft不等式。肉不滿足一定不是唯一可譯碼。 （3）將碼畫成一顆碼數(shù)圖，觀察其是否滿足即時碼的樹圖構造，若滿足則是唯一可譯碼。 （4）用Sardinas和Patterson設計的判斷方法：計算出碼中所有可能的尾隨后綴集合F，觀察F中沒有包含任一碼字。若無則為唯一可譯碼；若有則一定不是可譯碼。 上述判斷步驟中，Sardinas和Patterson設計的判斷方法是能確切的判斷出是否是唯一的可譯碼的方法，所有可以跳過（2）、（3）步驟，直接采用（4）判斷法. 例題：設碼C=