信息論基礎(chǔ)課件：信源編碼

1、信源編碼編碼：改變信息的表示方式。物理編碼：把物理輸入信息變成符合信道傳輸要求的物理內(nèi)容。數(shù)學(xué)編碼：通過把信息集合內(nèi)所有信息擴展，排列，組合，省 略等方式，改變信息集合的數(shù)學(xué)表示。數(shù)學(xué)編碼的目的：數(shù)學(xué)上匹配信道，以更高的效率，正確，安 全的傳輸信息。 數(shù)學(xué)上匹配信道是基本的。更高的效率：信源編碼。正確：信道編碼。安全：加密編碼。碼的分類：1.定長碼與變長碼定長碼固定碼的長度變長碼不固定定長碼不如變長碼實用2.奇異碼與非奇異碼非奇異碼輸入信息與編碼一一對應(yīng)奇異碼不一一對應(yīng)。3.唯一可譯碼把多個碼字連在一起（碼序列），譯碼的過程就是“斷句”。唯一可譯碼：任意碼序列只有一種不出現(xiàn)未定義碼的分割方法。

2、100010=10,0,0,10/10,00,10/10,0,01,04.即時碼和非即時碼即時碼：收到一個碼后能立刻判定完整，并開始譯碼。非即時碼：收到一個碼后也不知道是否完整。碼奇異碼非分組碼分組碼非奇異碼非唯一可譯碼非即時碼 即時碼唯一可譯碼分組碼：把發(fā)碼序列分成一段段的組，進行編碼。非分組碼：輸入與編碼不能一一對應(yīng)，也寫不成碼表奇異碼必然非唯一可譯，非唯一可譯必然非即時（非即時未必非唯一可譯）逆否就是即時必然唯一可譯，能判定是否完整當(dāng)然唯一可譯即時碼的另一種數(shù)學(xué)描述：碼樹 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0

3、1碼樹從一個點(樹根)開始分裂成多個點(節(jié)點)，末端節(jié)點對應(yīng)于輸入信息，輸入信息對應(yīng)編碼就是從樹根開始沿最短路徑到對應(yīng)節(jié)點所有經(jīng)過的(節(jié)點/樹枝)碼字順序排列。碼的長度就等于節(jié)數(shù)。滿樹每層都完全分裂定長碼不滿樹非定長碼由于路徑不同，任意一個碼都不是其他碼的前綴(即時碼的充要條件)，所以必然是即時碼唯一可譯碼存在的充要條件克勞夫特不等式是即時碼存在的充分必要條件：滿足不等式的一定能用碼樹來描述，不滿足的一定不能用碼樹?？偮窂綌?shù)目是1，進制的碼長次方表示了該碼長(碼樹的層)一共有多少種編碼可能(碼樹的路徑)，每一個編碼的倒數(shù)即它占據(jù)了該層幾分之1的路徑。滿足不等式說明，路徑?jīng)]有被占滿（或者剛好占滿

4、）。因此總能畫出碼樹。即必能畫出至少一組即時碼，唯一可譯碼存在。McMillan證明了克勞夫特不等式也是唯一可譯碼存在的充要條件。同時，即時碼任意碼字不能是其他碼的前綴，所以一定能畫出碼樹，同時說明路徑?jīng)]占滿，不等式一定成立。唯一可譯碼只要存在一定有對應(yīng)的碼長分配相同的即時碼形式。逆命題也成立無失真信源編碼失真限制：平均失真為0。如果譯碼會產(chǎn)生錯誤，則可能失真，因此要無失真就需要唯一可譯碼。(非極限情況)信源編碼的目的就在于提高傳輸效率。提高效率有兩種等價的描述：1)單位碼長攜帶的平均信息量最大。2)傳輸一個信源信息所需要的平均最大信息率最小。其實就是用平均碼長最短的碼信源熵信源最大熵編碼最大熵0不存在無差錯編碼 唯一可譯碼不存在無差錯編碼存在但是只存在于極限唯一可譯碼存在存在唯一可譯碼不知道是否存在無差錯碼在這個范圍內(nèi)，給定差錯率限制的有失真定長編碼總可以通過擴展信源來實現(xiàn)定長編碼定理：在這個范圍內(nèi)，給定差錯率限制的有失真定長編碼