第5章無(wú)失真信源編碼定理

《第5章無(wú)失真信源編碼定理》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、幻燈片1第5章無(wú)失真信源編碼定理幻燈片2l通信的實(shí)質(zhì)是信息的傳輸。高效率、高質(zhì)量地傳送信息又是信息傳輸?shù)幕締栴}。l信源信息通過(guò)信道傳送給信宿，需要解決兩個(gè)問題：l第一，在不失真或允許一定失真條件下，如何用盡可能少的符號(hào)來(lái)傳送信源信息，以提高信息傳輸率。l第二，在信道受干擾的情況下，如何增強(qiáng)信號(hào)的抗干擾能力，提高信息傳輸?shù)目煽啃酝瑫r(shí)又使得信息傳輸率最大。l為了解決以上兩個(gè)問題，引入了信源編碼和信道編碼?；脽羝?l提高抗干擾能力（降低失真或錯(cuò)誤概率）往往是增加剩余度以降低信息傳輸率為代價(jià)的；反之，要提高信息傳輸率往往通過(guò)壓縮信源的剩余度來(lái)實(shí)現(xiàn)，

2、常常又會(huì)使抗干擾能力減弱。l上面兩者是有矛盾的，然而在信息論的編碼定理中，已從理論上證明，至少存在某種最佳的編碼或信息處理方法，能夠解決上述矛盾，做到既可靠又有效地傳輸信息。l第5章著重討論對(duì)離散信源進(jìn)行無(wú)失真信源編碼的要求、方法及理論極限，得出極為重要的極限定理——香農(nóng)第一定理?；脽羝?5.1編碼器l編碼實(shí)質(zhì)上是對(duì)信源的原始符號(hào)按一定的數(shù)學(xué)規(guī)則進(jìn)行的一種變換。l圖5.1就是一個(gè)編碼器，它的輸入是信源符號(hào)集S={s1,s2,…,sq}。同時(shí)存在另一符號(hào)集X={x1,x2,…,xr}，一般元素xj是適合信道傳輸?shù)模Q為碼符號(hào)（或稱為碼元）。編碼

3、器是將信源符號(hào)集中的符號(hào)si（或者長(zhǎng)為N的信源符號(hào)序列ai）變換成由xj（j=1,2,…,r）組成的長(zhǎng)度為li的一一對(duì)應(yīng)序列。幻燈片5lS：{s1,s2,…sq}lC：{w1,w2,…wq}編碼器l（wi是由li個(gè)xj（xj屬于X））組成的序列，并于si一一對(duì)應(yīng)lX：{x1,x2,…xr}l這種碼符號(hào)序列Wi稱為碼字。長(zhǎng)度li稱為碼字長(zhǎng)度或簡(jiǎn)稱碼長(zhǎng)。所有這些碼字的集合C稱為碼。l編碼就是從信源符號(hào)到碼符號(hào)的一種映射，若要實(shí)現(xiàn)無(wú)失真編碼，必須這種映射是一一對(duì)應(yīng)的、可逆的?；脽羝?一些碼的定義l二元碼：若碼符號(hào)集為X={0,1}，所得碼字都是一些

4、二元序列，則稱為二元碼。l若將信源通過(guò)一個(gè)二元信道進(jìn)行傳輸，為使信源適合信道傳輸，就必須把信源符號(hào)變換成0,1符號(hào)組成的碼符號(hào)序列（二元序列），這種編碼所得的碼為二元碼。二元碼是數(shù)字通信和計(jì)算機(jī)系統(tǒng)中最常用的一種碼。l等長(zhǎng)碼（或稱固定長(zhǎng)度碼）l若一組碼中所有碼字的碼長(zhǎng)都相同，即li=l（i=1,2,…,q），則稱為等長(zhǎng)碼?；脽羝?l變長(zhǎng)碼l若一組碼中所有碼字的碼長(zhǎng)各不相同，即任意碼字由不同長(zhǎng)度li的碼符號(hào)序列組成，則稱為變長(zhǎng)碼。l非奇異碼l若一組碼中所有碼字都不相同，即所有信源符號(hào)映射到不同的碼符號(hào)序列si≠sjlwi≠wj，si,sj∈S，

5、wi,wj∈C，則稱碼C為非奇異碼。l奇異碼l若一組碼中有相同的碼字，即si≠sjlwi=wj，si,sj∈S，wi,wj∈C，，則稱碼C為奇異碼。幻燈片8l同價(jià)碼l若碼符號(hào)集：{x1x2…xr}中每個(gè)碼符號(hào)xi所占的傳輸時(shí)間都相同，則所得的碼C為同價(jià)碼。一般二元碼都是同價(jià)碼。對(duì)同價(jià)碼來(lái)說(shuō)，等長(zhǎng)碼中每個(gè)碼字的傳輸時(shí)間都相同；而變長(zhǎng)碼中每個(gè)碼字的傳輸時(shí)間就不一定相同。電報(bào)中常用的莫爾斯碼是非同價(jià)碼。l碼的N次擴(kuò)展碼l假定某碼C，它把信源S中的符號(hào)si一一變換成碼C中的碼字wi，則碼C的N次擴(kuò)展碼是所有N個(gè)碼字組成的碼字序列的集合?；脽羝?l唯一

6、可譯碼l若碼的任意一串有限長(zhǎng)的碼符號(hào)序列只能被惟一的譯成所對(duì)應(yīng)的信源符號(hào)序列，則此碼稱為唯一可譯碼，或單義可譯碼。l若要所編的碼是唯一可譯碼，不但要求編碼時(shí)不同的信源符號(hào)變換成不同的碼字，而且還必須要求任意有限長(zhǎng)的信源序列所對(duì)應(yīng)的碼符號(hào)序列各不相同，即要求碼的任意有限長(zhǎng)N次擴(kuò)展碼都是非奇異碼。因?yàn)橹挥腥我庥邢揲L(zhǎng)的信源序列所對(duì)應(yīng)的碼符號(hào)序列各不相同，才能把該碼符號(hào)序列唯一地分割成一個(gè)個(gè)對(duì)應(yīng)的信源符號(hào)，從而實(shí)現(xiàn)惟一地譯碼?；脽羝?05.2等長(zhǎng)碼l一般說(shuō)來(lái)，若要實(shí)現(xiàn)無(wú)失真的編碼，這不但要求信源符號(hào)si與碼字wi是一一對(duì)應(yīng)的，而且要求碼符號(hào)序列的反變

7、換也是惟一的，所編的碼必須是唯一可譯碼。否則，所編的碼不具有惟一可譯碼性，就會(huì)引起譯碼帶來(lái)的錯(cuò)誤和失真。l若等長(zhǎng)碼是非奇異碼，則它的任意有限長(zhǎng)N次擴(kuò)展碼一定也是非奇異碼。等長(zhǎng)非奇異碼一定是惟一可譯碼。l若對(duì)信源S進(jìn)行等長(zhǎng)編碼，就必須滿足q≤rl，其中l(wèi)是等長(zhǎng)碼的碼長(zhǎng)，r是碼符號(hào)集中的碼元數(shù)?；脽羝?1l如果對(duì)信源的N次擴(kuò)展信源進(jìn)行等長(zhǎng)編碼，若要求編得的等長(zhǎng)碼是惟一可譯碼則必須滿足qN≤rl，表明只有當(dāng)l長(zhǎng)的碼符號(hào)序列數(shù)(rl)大于等于N次擴(kuò)展信源的符號(hào)數(shù)(qN)時(shí)，才可能存在等長(zhǎng)非奇異碼。l從以上不等式可得L/N≥logq/logr，式中L/

8、N是平均每個(gè)信源符號(hào)所需要的碼符號(hào)個(gè)數(shù)。等長(zhǎng)惟一可譯碼，每個(gè)信源符號(hào)至少需要用logq/logr個(gè)碼符號(hào)來(lái)變換，就是每個(gè)信源符號(hào)所需最短碼長(zhǎng)為logq/logr個(gè)。