閱讀筆記：通訊領域中的數學理論 A Mathematical Theory of Communication

contributed by <jouae>

拜讀 Shannon 1948 的論文，筆記一下內容。部分證明摘錄自《熵 (Entropy)》李天岩教授著，刊於數學傳播十三卷三期。

引子 Introduction

The significant aspect is that the actual message is one selected from a set of possible messages. The system must be designed to operate for each possible selection, not just the one which will actually be chosen since this is unknown at the time of design.

• 原文中一個通訊系統表示

使用

${\log }_2(\cdot )$ 的好處：

1. 當輸入值
   $x$ 呈倍數成長時，由對數特性可以寫成線性關係：
   
   $${\log }_2(cx)={\log }_2(c)+{\log }_2(x),\text{ for some }c$$

通訊系統簡易的分成三類

1. 離散型 discrete
   離散型通訊系統，指的是傳遞的訊息與傳遞的訊號皆為一序列的離散符號。例如，博多式電報(Baudo telegraphy)。
2. 連續型 continous
   離續型通訊系統，指的是傳遞的訊息與傳遞的訊號皆被視為一連續的函數。例如，收音機和電視。
3. 混和型 mixed
   混和型通訊系統，指的是上述兩者的組成。

第一部分：無雜訊的離散型通訊系統

1. 無雜訊的離散型通訊系統

離散型通訊系統有兩個例子，其一為電傳打字機(TTY)，其二為博多式電報機。

一般而言，離散型通訊系統為一從有限符號集

$\{S_1,S_2,\dots ,S_n\}$ 選取排列的序列，該序列從一點傳遞至另一點。每個符號

$S_i$ 對應至一持續時間

$t_i$。

在電報(telegraphy)中假設有以下符號：

1. ▄　 點(dot)需要
   $2$ 個時間單位。
2. ▄▄▄　 劃(dash)需要
   $4$ 個時間單位。
3. 　　　 字母間隔(letter space)需要
   $3$ 個時間單位。
4. 　　　　　　 字間隔 (word space)需要
   $6$ 個時間單位。
   同時，限制不會有連續的間隔出現。兩個字母間隔視作為字間隔。

以博多式電報為例，藉由五個按鍵，總共有

$2^5=32$ 種組合的按法，可以輸出

$32$ 個符號。依照國際電報二號字母表(International Telegraph Alphabet No 2, ITA2)定義，博多式電報使用兩個字符集，每個字符集含有

$32$ 個符號(symbols)，其中一個字符集含有

$26$ 個字母，其餘

$6$ 個符號為控制字符(control characters) 包括 Carriage-return、Line-feed、Letter-shift、Figure-shift、Space，及最後一個符號可以為 All-space 或 null。

由於博多式電報發出的每個符號都是由

$5$ 個按鍵組合出來的，所以每個符號有

$5$ 位元的資訊。假設該離散型通訊系統每秒發出

$n$ 個符號，則代表該通訊系統的最大上限通道容量(capacity)為

$5n\text{ bits/sec}$。

• 定義：離散通道容量
  $C$ 定義成：
  
  $$C=\underset{T\to \mathrm{\infty }}{lim}{\displaystyle \frac{\log N(T)}{T}}$$
  其中
  $N(T)$ 為一在時間
  $T$ 內，可允許訊號數量。

假設所有由符號

$S_1,S_2,\dots ,S_n$ 組成的序列都被允許傳送，且時長

$t_1,t_2,\dots ,t_n$ 各別對應同一下標符號的符號。例如，傳送一個符號

$S_1$ 需要對應

$t_1$ 長的單位時間。更具一體一點的例子，電報發送符號 ▄　 點(dot)需要

$2$ 個時間單位，發送 ▄▄▄　 劃(dash)需要

$4$ 個時間單位，發送由點和劃符號組成的序列 ▄　▄　▄　▄▄▄　▄▄▄　▄▄▄　▄　▄　▄　 總共需要

$2\times 3+4\times 3+2\times 3=24$ 個時間單位，該序列在摩斯密碼中代表的是 SOS。

如果

$N(t)$ 表示持續時間為

$t$ 的序列數量

$$N(t)=N(t-t_1)+N(t-t_2)+\cdots +N(t-t_n).$$

該時間

$t$ 內可允許訊號數量的總數等於以

$S_1,S_2,\dots ,S_n$ 符號結尾序列的序列數量之和，其中這些序列數量分別為

$N(t-t_1),N(t-t_2),\dots ,N(t-t_n)$ 。

解釋一下為何要設計成遞迴式的形式計算總數。假設傳送符號的總時長為

$T$ 單位時間，對於任意的兩個以上符號構成的序列且序列不超過總時長

$T$ 單位時間，我們都可以拆成兩個子序列，其一為最後一個符號

$S_i$ 的第一子序列，該第一子序列花費

$t_i$ 單位時間；其二為原序列扣除最後一個符號的第二子序列，此第二子序列花費時長在

$T-t_i$ 單位時間內，而這樣的第二子序列數量會有

$N(T-t_i)$ 個。再對該第二子序列，以第一序列中的符號為

$S_i$ ，其中

$i=1,\dots ,n$ ，進行一樣的拆解動作，值至第一子序列與第二子序列皆只剩餘一個符號。整個計算序列數量的方式就是拆解成子序列在計算，過程就跟遞迴式一致。

回到遞迴式

$N(t)$，我們要分析該遞迴式如何計算通道容量。假設

$N(t)$ 有解

$N(t)=X^t$ 則帶入該式子得到：

$$X^t=X^{t-t_1}+X^{t-t_2}+\cdots +X^{t-t_n}$$
等式兩側同除

$X^t$ 則得到一特徵方程式：

$$1=X^{-t_1}+X^{-t_2}+\cdots +X^{-t_n}$$

特徵方程的解有可能會有複數(complex number)但在此我們關心的實數特徵根行為，假設其實數特徵根可以表示為

$X_1,\dots ,X_k$ 對

$k\le n$ 且依照遞增排序

$X_1\le X_2\le \cdots \le X_k$ 則其通解表示為：

$$N(t)=X_1^t+X_2^t+\cdots +X_n^t$$

當由於

$X_1^t$ 為最大的實數特徵根，當

$t$ 不斷增長時，

$X_1^t$ 會以相對較快的速度大於其他特徵根。故當

$t$ 大時，可以將

$N(t)$ 以近似的方式表示為：

$$N(t)\approx X_1^t$$

舉個例子，假設有一線性遞迴關係：

$$a_n=a_{n-1}+a_{n-2}$$

其特徵方程可藉由假設其特徵解形式為

$a_n=x^n$ 後得到

$$1=x^{-1}+x^{-2}$$
等式兩側同乘

$x^2$ 則等價於

$$x^2-x^1-1=0$$
藉由公式解可以得到兩根

$$x={\displaystyle \frac{1+\sqrt{5}}{2}},x={\displaystyle \frac{1-\sqrt{5}}{2}}$$

則原線性遞迴式可以表示為

$$a_n={\left({\displaystyle \frac{1+\sqrt{5}}{2}}\right)}^n+{\left({\displaystyle \frac{1-\sqrt{5}}{2}}\right)}^n$$

以

$\widetilde{a_n}$ 表示最大實數特徵根近似

$a_n$

$$\widetilde{a_n}={\left({\displaystyle \frac{1+\sqrt{5}}{2}}\right)}^n$$

以下表格為近似值與實際解在不同

$n$ 時的數值，

$|a_n-\widetilde{a_n}|$ 為兩者差的絕對值

$n$	$a_n$	$\widetilde{a_n}$	$|a_n-\widetilde{a_n}|$
1	1	1.62	0.62
2	3	2.62	0.38
3	4	4.24	0.24
4	7	6.85	0.15
5	11	11.09	0.09

可以觀察到在該例子中，隨著

$n$ 越大近似值逐漸近似實際解，也就是說最大的實數特徵根在

$n$ 大時，可以代表整個線性遞迴式的行為。

隨後將線性遞迴式

$N(t)$ 帶入通道容量的差分形式後，可得

$${\displaystyle \frac{\log N(t)}{t}}$$
假設

$N(t)$ 可以最大實數特徵根表示整個系統的行為，則此處我們將

$N(t)$ 以最大實數特徵根

$X_1^t$ 替換，則

$${\displaystyle \frac{\log X_1^t}{t}}=\log X_1$$

所以通道容量為

$C=\log X_1$，換言之通道的容量只要知道可允許訊號數量的最大實數特徵根即可。

• 定理1：令第
  $s$ 個符號允許從狀態
  $i$ 到狀態
  $j$ 的持續時間表示為
  $b_{ij}^{(s)}$。則通道容量
  $C$ 等於
  $\log W$ ，其中
  $W$ 為以下行列式方程的最大實數根：
  
  $$|\sum _s{W}^{-b_{ij}^{(s)}}-{\delta }_{ij}|=0$$
  其中
  ${\delta }_{ij}$ 在
  $i=j$ 時為
  $0$。
  • 證明：
    令
    $N_i(L)$ 為以狀態
    $i$ 結束，持續時間為
    $L$ 的符號塊的數量，則：
    
    $$N_j(L)=\sum _{i,s}{N}_i(L-b_{ij}^{(s)})$$

2. The Discrete Source of Information

參考

• A Mathematical Theory of Communication by C. E. Shannon, 1948
• 數學傳播十三卷三期：熵 (Entropy) 李天岩
• [The Evolution of Character Codes, 1874-1968 by Eric Fischer]
• International Telegraph Alphabet No 2, ITA2