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

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

2、100010=10,0,0,10/10,00,10/10,0,01,04.即時(shí)碼和非即時(shí)碼即時(shí)碼：收到一個(gè)碼后能立刻判定完整，并開始譯碼。非即時(shí)碼：收到一個(gè)碼后也不知道是否完整。碼奇異碼非分組碼分組碼非奇異碼非唯一可譯碼非即時(shí)碼 即時(shí)碼唯一可譯碼分組碼：把發(fā)碼序列分成一段段的組，進(jìn)行編碼。非分組碼：輸入與編碼不能一一對(duì)應(yīng)，也寫不成碼表奇異碼必然非唯一可譯，非唯一可譯必然非即時(shí)（非即時(shí)未必非唯一可譯）逆否就是即時(shí)必然唯一可譯，能判定是否完整當(dāng)然唯一可譯即時(shí)碼的另一種數(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碼樹從一個(gè)點(diǎn)(樹根)開始分裂成多個(gè)點(diǎn)(節(jié)點(diǎn))，末端節(jié)點(diǎn)對(duì)應(yīng)于輸入信息，輸入信息對(duì)應(yīng)編碼就是從樹根開始沿最短路徑到對(duì)應(yīng)節(jié)點(diǎn)所有經(jīng)過的(節(jié)點(diǎn)/樹枝)碼字順序排列。碼的長度就等于節(jié)數(shù)。滿樹每層都完全分裂定長碼不滿樹非定長碼由于路徑不同，任意一個(gè)碼都不是其他碼的前綴(即時(shí)碼的充要條件)，所以必然是即時(shí)碼唯一可譯碼存在的充要條件克勞夫特不等式是即時(shí)碼存在的充分必要條件：滿足不等式的一定能用碼樹來描述，不滿足的一定不能用碼樹?？偮窂綌?shù)目是1，進(jìn)制的碼長次方表示了該碼長(碼樹的層)一共有多少種編碼可能(碼樹的路徑)，每一個(gè)編碼的倒數(shù)即它占據(jù)了該層幾分之1的路徑。滿足不等式說明，路徑?jīng)]有被占滿（或者剛好占滿

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