信息論惟可譯碼判別方法專題培訓(xùn)課件

信息論惟可譯碼判別方法3.唯一可譯碼與非唯一可譯碼

定義5.3

任意有限長的碼元序列，如果只能唯一地分割成一個個碼字，便稱為唯一可譯碼。唯一可譯碼的物理含義是指不僅要求不同的碼字表示不同的信源符號，而且還要求對由信源符號構(gòu)成的符號序列進(jìn)行編碼時，在接收端仍能正確譯碼而不發(fā)生混淆。唯一可譯碼首先是非奇異碼，且任意有限長的碼字序列不會雷同。4.即時碼與非即時碼

定義5.4

無需考慮后續(xù)的碼符號就可以從碼符號序列中譯出碼字，這樣的唯一可譯碼稱為即時碼。下面討論唯一可譯碼成為即時碼的條件。

定義5.5

設(shè)為一碼字，對于任意的，稱碼符號序列的前j個元素為碼字的前綴。按照上述的前綴的定義，有下述結(jié)論：

定理5.1

一個唯一可譯碼成為即時碼的充要條件是其中任何一個碼字都不是其他碼字的前綴。即時碼可以用樹圖來構(gòu)造．圖5.2是一個二元即時碼的樹圖．圖5.2二元即時碼的樹圖樹是沒有回路的圖，所以它也是由節(jié)點(diǎn)和弧構(gòu)成的．樹中最頂部的節(jié)點(diǎn)稱為根節(jié)點(diǎn)，沒有子節(jié)點(diǎn)的節(jié)點(diǎn)稱為葉子節(jié)點(diǎn)。所有根節(jié)點(diǎn)的子節(jié)點(diǎn)稱為一階節(jié)點(diǎn)，所有一階節(jié)點(diǎn)的子節(jié)點(diǎn)稱為二階節(jié)點(diǎn)，依此類推。階節(jié)點(diǎn)最多有個。節(jié)點(diǎn)的階次又稱為節(jié)點(diǎn)的深度。綜上所述，可將信源編碼作如下分類：碼非分組碼（樹碼）分組碼（塊碼）奇異碼非奇異碼非唯一可譯碼唯一可譯碼即時碼非即時碼唯一可譯碼的判別準(zhǔn)則A.A.Sardinas和G.W.Patterson于1957年提出下述算法用于判斷碼C的唯一可譯性．此算法的原理如下所示：

其中都是碼字。可知，當(dāng)且僅當(dāng)某個有限長的碼符號序列能譯成兩種不同的碼字序列時，此碼不是唯一可譯碼，此時一定是的前綴，而的尾隨后綴一定是另一碼字的前綴；而的尾隨后綴又是其他碼字的前綴．最后，碼符號序列的尾部一定是一個碼字。設(shè)C為碼字集合，按以下步驟構(gòu)造此碼的尾隨后綴集合F：(1)考查C中所有的碼字，若是的前綴，則將相應(yīng)的后綴作為一個尾隨后綴碼放入集合中；(2)考查C和兩個集合，若是的前綴或是的前綴，則將相應(yīng)的后綴作為尾隨后綴碼放入集合中；(3)即為碼C的尾隨后綴集合；(4)若F中出現(xiàn)了C中的元素，則算法終止，返回假(C不是唯一可譯碼)

否則若F中沒有出現(xiàn)新的元素，則返回真。定理5.5

一個碼是唯一可譯碼的充要條件是的并集中沒有C中的碼字。2023/5/247惟一可譯碼判別準(zhǔn)則——例題命題5.4.1一種碼是唯一可譯碼的充要條件是S1,S2,…中沒有一個含有S0中的碼字。S0S1S2S3S4S50000010111011100011000111101111001111101110111101惟一可譯碼判別準(zhǔn)則——例題S0S1S2S3S4S5S6S7abbcdedebaddebcbcdeabbbaddebbbcde方法一:根據(jù)異前綴碼是唯一可譯碼來進(jìn)行判斷。其步驟如下:首先,觀察是否為非奇異碼。若是奇異碼,肯定不是唯一可譯碼;其次,計算是否滿足Kraft不等式。若不滿足一定不是唯一可譯碼;最后,將碼畫成一棵碼樹圖,觀察是否滿足異前綴碼的碼樹圖的構(gòu)造,若滿足則是唯一可譯碼。這種方法的理論基礎(chǔ)是異前綴碼一定是唯一可譯碼,通過經(jīng)典的Kraft不等式及碼樹圖進(jìn)行判別。但它的缺點(diǎn)也是顯而易見的,若不是異前綴碼時,則此方法無法判斷是否是唯一可譯碼惟一可譯碼判別方法方法二:使用A.A.Sardinas和G.W.Patterson設(shè)計的判斷