離散信源

1. 信源的數(shù)學(xué)模型機(jī)器分類

信息的來(lái)源稱為信源
信息是抽象的，需要通過(guò)消息（文字沮焕、圖片等）來(lái)研究信源
對(duì)信源進(jìn)行建模

信源可以輸出多個(gè)符號(hào)烦粒，每個(gè)符號(hào)以一定的概率隨機(jī)出現(xiàn)蜡秽，故可以用概率來(lái)描述信源

$X$ 表示信源的隨機(jī)變量瘸羡； $x_i$ 表示信源符號(hào)漩仙； $P(x_i)$ 表示信源符號(hào) $x_i$ 出現(xiàn)的概率
$\left[ \begin{matrix} X \\ P \end{matrix} \right] = \left[ \begin{matrix} x_1 & x_2 & \cdots & x_q \\ P(x_1) & P(x_2) & \cdots & P(x_q) \end{matrix} \right] \\ \, \\ \sum_{i=1}^q P(x_i) = 1, P(x_i) \ge 0$

信源的分類：根據(jù)信源輸出在時(shí)/空、幅度取值是否連續(xù)

連續(xù)信源：時(shí)/空連續(xù)犹赖、幅度連續(xù)（比如自然圖像）
$\left[ \begin{matrix} X \\ P \end{matrix} \right] = \left[ \begin{matrix} (a,b) \\ P(x) \end{matrix} \right]$

離散信源（數(shù)字信源）：時(shí)/空離散队他、幅度離散（如數(shù)字圖像）
$\left[ \begin{matrix} X \\ P \end{matrix} \right] = \left[ \begin{matrix} x_1 & x_2 & \cdots & x_q \\ P(x_1) & P(x_2) & \cdots & P(x_q) \end{matrix} \right]$

信號(hào)的分類：

連續(xù)信號(hào)（模擬信號(hào)）：時(shí)間和幅度都是連續(xù)的

量化信號(hào)：時(shí)間連續(xù)、幅度離散

離散信號(hào)：時(shí)間離散冷尉、幅度連續(xù)

數(shù)字信號(hào)：時(shí)間和幅度都是離散的

信源的分類：根據(jù)信源輸出是否獨(dú)
立

有記憶信源：信源發(fā)出的各個(gè)符號(hào)之間不是相互獨(dú)立的漱挎，是有依賴關(guān)系的

有限記憶信源：信源發(fā)出的消息符號(hào)只與前若干個(gè)符號(hào)的關(guān)系比較密切系枪，與更前面符號(hào)的關(guān)系逐漸減弱雀哨，直至無(wú)關(guān)。如果只與前 $m$ 個(gè)符號(hào)有關(guān)系私爷，則稱 $m$ 為記憶長(zhǎng)度
$P(x_i | x_{i-1} x_{i-2} \cdots x_{i-m})$

無(wú)限記憶信源：信源發(fā)出的消息符號(hào)與前面出現(xiàn)的所有符號(hào)都有關(guān)系
$P(x_i | x_{i-1} x_{i-2} x_{i-3} \cdots )$

無(wú)記憶信源：信源發(fā)出的各個(gè)消息符號(hào)是相互獨(dú)立的雾棺，是沒(méi)有依賴關(guān)系的

2. 離散無(wú)記憶信源

2.1 定義

信源 $X$ 的符號(hào)集為 $(x_1,x_2,\cdots,x_q)$ ， $q$ 為信源發(fā)出的消息符號(hào)的個(gè)數(shù)衬浑，每個(gè)符號(hào)發(fā)生地概率為 $P(x_i),\, i = 1,2,\cdots,q$ 捌浩，這些消息符號(hào)彼此互不相關(guān)，且有 $\displaystyle \sum_{i=1}^q P(x_i) = 1, \, P(x_i) \ge 0$ 工秩，則稱 $X$ 為離散無(wú)記憶信源尸饺。

2.2 信源的自信息量和平均自信息量

定義一：信源中某個(gè)事件（消息符號(hào)）的自信息量，表示該符號(hào)帶有信息量的多少
$I(x_i) = -log_{_2}P(x_i)$
定義二：信源的平均自信息量（信源熵）助币，表示平均每個(gè)符號(hào)帶有的信息量多少
$H(X) = E(I(x_i)) = \sum_{i=1}^q P(x_i)log_{_2}P(x_i)$

3. 離散無(wú)記憶信源的擴(kuò)展信源

3.1 $N$ 次擴(kuò)展信源

定義：集合中的每一個(gè)元素是一個(gè) $N$ 維隨機(jī)矢量
舉例：

二進(jìn)制信源： $X = \{00,01,10,11\}, N = 2$

二次擴(kuò)展信源（ $N = 2$ ）
$\left[ \begin{matrix} X^2 \\ P \end{matrix} \right] = \left[ \begin{matrix} \alpha_1 & \alpha_2 & \alpha_3 & \alpha_4 \\ P(\alpha_1) & P(\alpha_2) & P(\alpha_3) & P(\alpha_4) \end{matrix} \right]$

三次擴(kuò)展信源（ $N = 3$ ）
$\left[ \begin{matrix} X^3 \\ P \end{matrix} \right] = \left[ \begin{matrix} \alpha_1 & \alpha_2 & \cdots & \alpha_8 \\ P(\alpha_1) & P(\alpha_2) & \cdots & P(\alpha_8) \end{matrix} \right]$

3.2 離散無(wú)記憶信源的 $N$ 次擴(kuò)展

定義： $X$ 是一個(gè)離散無(wú)記憶信源
$\left[ \begin{matrix} X \\ P \end{matrix} \right] = \left[ \begin{matrix} x_1 & x_2 & \cdots & x_q \\ P(x_1) & P(x_2) & \cdots & P(x_q) \end{matrix} \right]$
則 $X$ 的 $N$ 次擴(kuò)展信源為：
$\left[ \begin{matrix} X^N \\ P \end{matrix} \right] = \left[ \begin{matrix} \alpha_1 & \alpha_2 & \cdots & \alpha_{q^N} \\ P(\alpha_1) & P(\alpha_2) & \cdots & P(\alpha_{q^N}) \end{matrix} \right]$
其中
$X^N = (X_1,X_2,\cdots,X_N) \\ \alpha_i = x_{i_1} x_{i_2} \cdots x_{i_N} \\ P(\alpha_i) = \prod_{k=1}^N P(x_{i_k}) = \prod_{k=1}^N p_{i_k}$

3.3 離散無(wú)記憶信源的 $N$ 次擴(kuò)展信源的熵

定義：離散無(wú)記憶信源 $X$ 的 $N$ 次擴(kuò)展信源 $X^N$ 的熵等于信源 $X$ 的熵的 $N$ 倍浪听，即
$H(X^N) = NH(X)$

證明：
$\displaystyle H(X^N) = -\sum_{i=1}^{q^N} P(\alpha_i) log_{_2}P(\alpha_i) = -\sum_{i=1}^{q^N} P(\alpha_i) log_{_2} \prod_{k=1}^N P(x_{i_k}) \\ = -\sum_{i=1}^{q^N}P(\alpha_i) \sum_{k=1}^N log_{_2}P(x_{i_k}) = -\sum_{i=1}^{q^N} \sum_{k=1}^N P(\alpha_i) log_{_2}P(x_{i_k}) \\ = -\sum_{k=1}^N ( \sum_{i_1 = 1}^q \sum_{i_2 = 1}^q \cdots \sum_{i_N = 1}^q P(x_{i_1}) P(x_{i_2}) \cdots P(x_{i_N}) log_{_2}P(x_{i_k}) \\ = -\sum_{k=1}^N ( \sum_{i_1 = 1}^q \sum_{i_2 = 1}^q \cdots \sum_{i_N = 1}^q P(x_{i_1}) \cdots P(x_{i_k}) log_{_2}P(x_{i_k}) \cdots P(x_{i_N})) \\ = -\sum_{k=1}^N \sum_{i_k = 1}^q P(x_{i_k}) log_{_2}P(x_{i_k}) = \sum_{k=1}^N H(X) = NH(X)$

3.4 信源分類

根據(jù)信源輸出符號(hào)所對(duì)應(yīng)的不同的隨機(jī)過(guò)程可以導(dǎo)出不同的信源模型
隨機(jī)變量前后獨(dú)立與否

獨(dú)立隨機(jī)信源-無(wú)記憶

不獨(dú)立隨機(jī)信源-有記憶

獨(dú)立、平穩(wěn)相結(jié)合

離散無(wú)記憶

時(shí)離高斯信源等

隨機(jī)過(guò)程平穩(wěn)與否

平穩(wěn)信源

非平穩(wěn)信源

4. 離散平穩(wěn)信源

4.1 定義

若信源產(chǎn)生的隨機(jī)序列 $X_1, X_2, \cdots$ 滿足：

所有 $X_1, X_2, \cdots$ 都取值于符號(hào)集 $A=(a_1,a_2,\cdots,a_q)$
序列是平穩(wěn)(Stationary)的眉菱，即對(duì)所有的非負(fù)整數(shù) $i_1,i_2,\cdots,i_N$ 迹栓， $h$ 以及 $x_1,x_2,\cdots,x_N \in A$ ，有
$P\{X_{i_1}=x_1,X_{i_2}=x_2,\cdots,X_{i_N}=x_N\} = P\{X_{i_1 + h}=x_1,X_{i_2 + h}=x_2,\cdots,X_{i_N + h}=x_N\}$

則稱此信源為離散平穩(wěn)信源俭缓。

4.2 含義

離散平穩(wěn)信源所發(fā)出的符號(hào)序列的概率分布與時(shí)間起點(diǎn)無(wú)關(guān)克伊，概率是平穩(wěn)的酥郭。

一維平穩(wěn)信源
$P(X_i = x) = P(X_j = x) = P(x)$
二維平穩(wěn)信源
$P(X_i = x_1,X_{i+1} = x_2) = P(X_j = x_1,X_{j+1} = x_2) = P(x_1 x_2)$
完全平穩(wěn)信源 (簡(jiǎn)稱為平穩(wěn)信源) ( $N$ 為任意正整數(shù))
$P(X_{i+1}=x_1,X_{i+2}=x_2,\cdots,X_{i+N}=x_N) = P(X_{j+1} = x_1, X_{j+2} = x_2, \cdots, X_{j+N} = x_N) = P(x_1 x_2 \cdots x_N)$

4.3 性質(zhì)

離散平穩(wěn)信源的條件概率也與時(shí)間起點(diǎn)無(wú)關(guān)

證明：
$已知 P(x_i) = P(x_j), P(x_i x_{i+1}) = P(x_j x_{j+1}), \cdots, P(x_i x_{i+1} \cdots x_{i+N}) = P(x_j x_{j+1} \cdots x_{j+N}) \\ \because P(x_i x_{i+1}) = P(x_i)P(x_{i+1}|x_i) = P(x_j x_{j+1}) = P(x_j)P(x_{j+1}|x_j) \\ \therefore P(x_{i+1}|x_i) = P(x_{j+1}|x_j) \\ \because P(x_i x_{i+1} x_{i+2}) = P(x_i) P(x_{i+1} | x_i) P(x_{i+2} | x_i x_{i+1}) \\ = P(x_j x_{j+1} x_{j+2}) = P(x_j) P(x_{j+1} | x_j) P(x_{j+2} | x_{j} x_{j+1}) \\ \therefore P(x_{i+2}|x_i x_{i+1}) = P(x_{j+2} | x_j x_{j+1}) \\ \,\,\,\,\,\,\,\vdots \\ \therefore P(x_{i+N}|x_i x_{i+1} \cdots x_{i+N-1}) = P(x_{j+N} | x_j x_{j+1} \cdots x_{j+N-1})$

離散平穩(wěn)信源不一定是離散無(wú)記憶信源

4.4 二維平穩(wěn)信源的熵

二維平穩(wěn)信源 $X$ 的概率空間為：
$\left[ \begin{matrix} X \\ P \end{matrix} \right] = \left[ \begin{matrix} a_1 & a_2 & \cdots & a_q \\ P(a_1) & P(a_2) & \cdots & P(a_q) \end{matrix} \right]$
且有
$\sum_{i=1}^q P(a_i) = 1$
同時(shí)已知連續(xù)兩個(gè)信源符號(hào)出現(xiàn)的聯(lián)合概率分為 $P(a_i a_j), i,j = 1, 2, \cdots, q$ ，且有
$\sum_{i=1}^q \sum_{j=1}^q P(a_i a_j) = 1 \\ P(a_j | a_i) = {P(a_i a_j) \over P(a_i)} \\ \sum_{j=1}^q P(a_j | a_i) = 1$
$\left[ \begin{matrix} X_1 X_2 \\ P \end{matrix} \right] = \left[ \begin{matrix} a_1 a_1 & a_1 a_2 & \cdots & a_q a_q \\ P(a_1 a_1) & P(a_1 a_2) & \cdots & P(a_q a_q) \end{matrix} \right]$

聯(lián)合熵： $\displaystyle H(X) = H(X_1 X_2) = -\sum_{i=1}^q \sum_{j=1}^q P(a_i a_j)log_{_2}P(a_i a_j)$
條件熵： $\displaystyle H(X_2 | X_1) = -\sum_{i=1}^q \sum_{j=1}^q P(a_i a_j)log_{_2}P(a_j | a_i)$

4.5 極限熵

定義一：源輸出為 $N$ 長(zhǎng)符號(hào)序列愿吹，平均每個(gè)符號(hào)的熵為
$H_N(X) = {1 \over N}H(X^N) = {1 \over N}H(X_1,X_2,\cdots,X_N)$
定義二：信源輸出為 $N$ 長(zhǎng)符號(hào)序列不从，當(dāng) $N \rightarrow \infty$ ，則極限熵為
$H_{\infty}(X) = \lim_{N \rightarrow \infty}H_N(X)$
含義：信源輸出的符號(hào)序列中洗搂，平均每個(gè)符號(hào)帶有的信息量消返，即實(shí)際的熵
定理：對(duì)任意離散平穩(wěn)信源，若 $H_1(X) < \infty$ 耘拇，則 $\displaystyle \lim_{N \rightarrow \infty} H_N(X) = \lim_{N \rightarrow \infty} H(X_N | X_1 X_2 \cdots X_{N-1})$ 撵颊，即 $\displaystyle \lim_{N \rightarrow \infty} {1 \over N} H(X_1 X_2 \cdots X_N) = \lim_{N \rightarrow \infty} H(X_N | X_1 X_2 \cdots X_{N-1})$

證明：

根據(jù)可加性：
$\displaystyle NH_N(X) = H(X^N) = H(X^{N-1}X) = H(X^{N-1}) + H(X_N|X^{N-1}) \\ = (N-1)H_{N-1}(X) + H(X_N|X^{N-1})$

根據(jù)熵之間的關(guān)系：
$\displaystyle NH_N(X) = H(X^N) = \sum_{n=1}^N H(X_n | X^{n-1}) \ge NH(X_N | X^{N-1})$

根據(jù)平穩(wěn)性和熵之間的關(guān)系：
$\forall n \in [1,N], H(X_n | X^{n-1}) \ge H(X_N | X_1 X_2 \cdots X_{N-1}) \\ H(X_N | X^{N-1}) \le H_N(X)$

5. 馬爾可夫信源

6. 信源的相關(guān)性和剩余度

最后編輯于：2020.06.07 02:04:08

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市惫叛，隨后出現(xiàn)的幾起案子倡勇，更是在濱河造成了極大的恐慌，老刑警劉巖嘉涌，帶你破解...
沈念sama閱讀 222,590評(píng)論 6贊 517
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件妻熊，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡仑最，警方通過(guò)查閱死者的電腦和手機(jī)扔役，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 95,157評(píng)論 3贊 399
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門(mén)，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)警医，“玉大人亿胸，你說(shuō)我怎么就攤上這事≡せ剩” “怎么了侈玄？”我有些...
開(kāi)封第一講書(shū)人閱讀 169,301評(píng)論 0贊 362
道士緝兇錄：失蹤的賣(mài)姜人
文/不壞的土叔我叫張陵，是天一觀的道長(zhǎng)吟温。經(jīng)常有香客問(wèn)我序仙，道長(zhǎng)，這世上最難降的妖魔是什么鲁豪？我笑而不...
開(kāi)封第一講書(shū)人閱讀 60,078評(píng)論 1贊 300
?港島之戀（遺憾婚禮）
正文為了忘掉前任潘悼，我火速辦了婚禮，結(jié)果婚禮上爬橡，老公的妹妹穿的比我還像新娘治唤。我一直安慰自己，他們只是感情好堤尾，可當(dāng)我...
茶點(diǎn)故事閱讀 69,082評(píng)論 6贊 398
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布肝劲。她就那樣靜靜地躺著，像睡著了一般。火紅的嫁衣襯著肌膚如雪辞槐。梳的紋絲不亂的頭發(fā)上掷漱，一...
開(kāi)封第一講書(shū)人閱讀 52,682評(píng)論 1贊 312
城市分裂傳說(shuō)
那天，我揣著相機(jī)與錄音榄檬，去河邊找鬼卜范。笑死，一個(gè)胖子當(dāng)著我的面吹牛鹿榜，可吹牛的內(nèi)容都是我干的海雪。我是一名探鬼主播，決...
沈念sama閱讀 41,155評(píng)論 3贊 422
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼舱殿，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼奥裸！你這毒婦竟也來(lái)了？” 一聲冷哼從身側(cè)響起沪袭，我...
開(kāi)封第一講書(shū)人閱讀 40,098評(píng)論 0贊 277
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤湾宙，失蹤者是張志新（化名）和其女友劉穎，沒(méi)想到半個(gè)月后冈绊，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體侠鳄，經(jīng)...
沈念sama閱讀 46,638評(píng)論 1贊 319
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 38,701評(píng)論 3贊 342
?白月光啟示錄
正文我和宋清朗相戀三年死宣，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了伟恶。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 40,852評(píng)論 1贊 353
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡毅该，死狀恐怖博秫，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情鹃骂，我是刑警寧澤台盯，帶...
沈念sama閱讀 36,520評(píng)論 5贊 351
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布罢绽，位于F島的核電站畏线，受9級(jí)特大地震影響，放射性物質(zhì)發(fā)生泄漏良价。R本人自食惡果不足惜寝殴，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 42,181評(píng)論 3贊 335
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望明垢。院中可真熱鬧蚣常，春花似錦、人聲如沸痊银。這莊子的主人今日做“春日...
開(kāi)封第一講書(shū)人閱讀 32,674評(píng)論 0贊 25
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)。三九已至贞绳，卻和暖如春谷醉，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背冈闭。一陣腳步聲響...
開(kāi)封第一講書(shū)人閱讀 33,788評(píng)論 1贊 274
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工俱尼，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人萎攒。一個(gè)月前我還...
沈念sama閱讀 49,279評(píng)論 3贊 379
代替公主和親
正文我出身青樓遇八，卻偏偏與公主長(zhǎng)得像，于是被迫代替她去往敵國(guó)和親耍休。傳聞我的和親對(duì)象是個(gè)殘疾皇子刃永，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 45,851評(píng)論 2贊 361