IA4 - 編碼、解碼與糾錯: 以二進制訊號為例

位於美國新墨西哥州的甚大天線陣列 (Very Large Array, VLA)

資訊 (information) 的傳遞在人類文明演進的歷史中扮演著極重要的角色，不僅僅是知識、技能，更是讓文化以及思想的瑰寶得以傳承，縱然生命會消逝，但前人所建立起的經驗卻能夠代代相傳給往後的人們。這些知識、技能和思想都可以歸納成資訊的一種，而在資訊遞交給後代的過程就稱做傳輸 (transmission)。傳輸不見得是保真的，亦即後代的人們所讀到前人的著作可能有多種版本，例如莎士比亞 (W. Shakespear) 的著作全集就有多種版本在流通，又或是1631年的邪惡聖經 (Wicked Bible) 事件，印刷廠將十誡中的Thou shalt not commit adultery (不可姦淫) 誤植成Thou shalt commit adultery (應當姦淫)。這些都是資訊在傳遞的過程當中發生失真，大部分的失真皆無大礙，並不影響資料原來意義的解讀，但少部分的失真卻是重大的，可能導致文意生變，甚至完全與當時書寫者的核心概念大相徑庭。所以既然失誤不可避免，有沒有什麼方法能讓我們盡可能的重建出原始資料的樣貌呢？

一、訊號的傳遞

讓我們來看看資料是怎麼傳輸的，以通電話為例 (圖1)，當你朋友撥手機給你時，他的聲音會被手機錄下並編碼，接著通過基地台、電信機房，再到離你最近的基地台將訊號廣播出去，你的手機收到訊號後將之解碼重新轉成類比音訊，再透過喇叭將你朋友的聲音播放給你聽，同時地，若換你說話，則這個過程將逆向發生！

圖1. 聲音訊號如何透過手機傳到朋友的手機或話筒上，補充一下當代手機的編解碼的方式是利用類似貝氏機率的方式去重建可能的原始訊號，不是這篇專題內提到的$R_r$編碼

　但注意訊號在傳遞的過程可能失真，就像你聽到手機播放你朋友的聲音時，總會覺得不像是親耳聆聽他的聲音一樣清晰，像隔著一層簾幕一樣，或甚至音調也有一些變化，有時背景還會傳來微若的雜訊滋滋聲。這便是圖1中間紫色虛線框裡描述的，當訊號透過層層基地台、電信機房時，原始的訊號發生了失真，可能被干擾了，或位元流失、誤植⋯等等，如果你的手機收到這樣破損的訊號，它甚至可能沒辦法重新解讀成類比音訊撥放給你聽。這時候，在一開始你朋友的手機做了一件事，那就是不僅僅是將你朋友的聲音送出去而已，在發送聲音訊號時，同時也一併發送可以讓你手機重建原始訊號並揪出可能的干擾源並剔除，這個過程便稱做編碼 (encode)，其中還附帶糾錯方式 (error correction)。而當你的收機收到訊號後，它會查看糾錯方式，並和收到的訊號做匹配，糾正不正確的雜訊，接著重建你朋友的聲音再撥放，這個過程則是解碼 (decode)。

1.1 有損傳輸

在繼續看編碼與解碼前，讓我們先來了解一下傳輸，特別是對大部分的通訊傳輸而言，它們都是不保真的，表示通過傳輸通道後，原始的資料都會發生異變。我們以二進制的例子來說，如果我傳輸了一組資料如下 $$\begin{array}{ccccccccccc} 發送 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 接收 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 \end{array}$$ 在上面的例子裡，原始發送的資料是10個$1$，但通過傳輸後，在接收端則是收到在第1和第9個 (依照python慣例所有序列都從$0$開始，這也是英制的習慣😂) 位置翻號變成$0$了，這便是資料傳輸時發生的失真。
　如果接收端知道接收的資料應全部為$1$，那它就可以自行更正，而由上面的例子我們發現10個位元中有兩個發生變異，我們也可以量化該傳輸通道的失真率約是$0.2$ (這其實蠻大的😅)，往後我們在通過該傳輸通道的時候，我們對它的錯誤率有所掌握，便可用對應的算法來應付。以上便是有損傳輸的概念，沒有興趣怎麼構造一個有損傳輸的模擬的話，可以直接跳第二節了，而在第三節我們會看一個實例，通過一個雜訊通道傳輸如下圖2的加菲貓 (我未擁有加菲貓版權，本網誌亦無透過廣告利益，也無任何其他回饋給作者本人的利益，如有侵權請來信告知！) 圖片，然後再透過解碼器解碼重建圖片。

圖2. $162\times 128$的灰階加菲貓塗鴉，位元$0$表示白色，$1$表黑色

　好的，我們可以這樣做有損傳輸的模擬，我先假定失真率，或者雜訊發生的機率是$f$，即有$f$的機率會讓$0$和$1$互換 $$\begin{array}{ccc} 1 & \to & 1\\ & \overset{f}{\begin{array}{cc} \searrow & \nearrow\\ \nearrow & \searrow \end{array}}\\ 0 & \underset{1-f}{\to} & 0 \end{array}$$ 上述左方是原始資料，右方是經傳輸過的資料，所以如果沒有發生異變，則有$(1-f)$的機率會直接到對應到右方與原始資料相同的位元值，但如果發生變異，則有$f$的機率左上的$1$會變成右下的$0$而左下的$0$變成右上的$1$。由於原始資料經傳輸後是否發生變異就像白努力試驗一樣，若擲出正面則發生變異，反面則保持原樣，只是這擲的銅板是不公正的。所以變得到了有損傳輸的模擬算法：

1. 傳輸進來的資料$\mathbf{x}=(x_1,x_2,\cdots,x_k)$
2. 對每個元素進行白努力試驗，其中輸入機率$f$，用${\tt True}$和${\tt False}$來表示試驗結果
   將結果收集成一組向量$\mathbf{f}=(f_1,f_2,\cdots,f_k)$
3. 則每個元素$x_i$會得到一個試驗結果$f_i$
   ${\tt if}~(f_i{\tt ==True}):$ 翻號$1\leftrightarrow 0$
   ${\tt else}:$ $x_i$保持不變

上面的算法可以用源代碼裡的channel函數實現，由於模擬有損傳輸不是這篇專題的重點，這裡我就不列出它的腳本了，有興趣可以自己看。在channel函數裡的第一個過程是檢查輸入資料 (這邊輸入應該使用ndarray) 的維度，維度告訴我們原始資料被編碼器重複拷貝了幾次 (變數repeat)，每個資料有幾個元素 (變數data_len)，這提供了等下進行是否翻號的白努力試驗數量的資訊，另外為了方便比較，我們把輸入的二進制訊號都轉成bool的形式，直到輸出後再轉回$0,1$的狀況。

二、編碼與解碼

好了，接下來我們就來看要如何重建上面所述被有損傳輸攪亂或者變異的資料，要解碼首先要先編碼，在編碼的過程中，我們同時也需要告訴解碼器該如何重建原始資料。

2.1 編碼器

這裡要看的是一種簡單的編碼和解碼方式，稱作重複編碼 $R_r$ (repetition)，假設原始的訊號是一組含有$k$個元素的向量$\mathbf{x}=(x_1,x_2,\cdots,x_k)$，則編碼器會輸出$r$個拷貝，數學表示如 $$輸出=\overbrace{\left(\begin{array}{c} \mathbf{x}\\ \mathbf{x}\\ \vdots\\ \mathbf{x} \end{array}\right)}^{共r個\mathbf{x}}=\left(\begin{array}{cccc} x_{1} & x_{2} & \cdots & x_{k}\\ x_{1} & x_{2} & & x_{k}\\ \vdots & & \ddots & \vdots\\ x_{1} & x_{2} & \cdots & x_{k} \end{array}\right),\tag{1}$$ 當然(1)要重複幾個$r$是任意的，我會後面會解釋$r$應取奇數才是恰當的。另外為了排版方便起見，有時我們會將行向量 (column vector) 寫成 $$\mathbf{x}=\left(\begin{array}{c} \mathbf{x}_{1}\\ \mathbf{x}_{2}\\ \vdots \end{array}\right)=(\mathbf{x}_1,\mathbf{x}_2,\cdots)^T,\tag{2}$$ 以列向量 (row vector) 的轉置 (transpose, $T$) 表示。尤其在呈現算法步驟的時候，因為排版空間的關係，沒辦法塞進一個垂直的行向量，用列向量比較節省空間，還有就是這篇小專題們只考慮二進制的訊號，亦即傳送的資訊僅為$0$和$1$，所以那些元素$x_i$只有這兩種選擇而已。
　由上面的概念，$R_r$編碼僅單純重複拷貝原始資料$r$次，然後就送進傳輸通道去了，所以很簡單地得到了編碼器算法：

1. 輸入欲傳輸的資料$\mathbf{x}$與編碼器拷貝資料的次數$r$
   eg. $\mathbf{x}={\tt [1,0,0,1,0,1,0]}$和$r=3$
2. ${\tt return}:~(\underbrace{\mathbf{x},\mathbf{x},\cdots,\mathbf{x}}_{拷貝r個})^T$
   eg. 輸出${\tt [[1,0,0,1,0,1,0],[1,0,0,1,0,1,0],[1,0,0,1,0,1,0]]}$

用簡單的python腳本來實現：

def encoder(data, repeat=3):
    """
    data: data to be transmitted
    repeat: times of repetition of data
    """
    # Examples:
    # If data = [a,b,c] and repeat=3
    # The following returns [[a,b,c],[a,b,c],[a,b,c]]
    return np.tile(data,(repeat,1))

在這個腳本裡，編碼器其實沒做任何事情，它就只是將資料 (data) 拷貝多次送出而已，我們用numpy的tile函數來實現複製多次的功能，其中複製的次數由參數repeat決定，預設是$3$。

2.2 解碼器

從1.1節我們知道訊號在傳輸的途中可能受到雜訊的干擾，使得有些$1$翻成$0$或$0$翻成$1$，所以經過傳輸後 $$\overbrace{\left(\begin{array}{c} \mathbf{x}\\ \mathbf{x}\\ \vdots\\ \mathbf{x} \end{array}\right)}^{編碼後}\to\boxed{{\rm noisy~channel}}\to\overbrace{\left(\begin{array}{c} \mathbf{x}_{1}\\ \mathbf{x}_{2}\\ \vdots\\ \mathbf{x}_{r} \end{array}\right)}^{傳輸後}.$$ 編碼器一開始輸出了$r$個相同的$\mathbf{x}$，而傳輸後由於雜訊的影響，每個$\mathbf{x}$都可能不再是原來的$\mathbf{x}$，而且這$r$個傳輸後的$\mathbf{x}$也都可能不太一樣了，所以我們將傳輸後每個原始資料的拷貝都標上編號，代表每個$\mathbf{x}_i$都可能與原始的$\mathbf{x}$有所不同。舉個例子來說，他可能長成像這樣 $$\left(\begin{array}{c} \mathbf{x}_{1}\\ \mathbf{x}_{2}\\ \vdots\\ \mathbf{x}_{r} \end{array}\right)=\left(\begin{array}{cccc} x_{11} & x_{12} & \cdots & x_{1k}\\ x_{21} & x_{22} & & x_{2k}\\ \vdots & & \ddots & \vdots\\ x_{r1} & x_{r2} & \cdots & x_{rk} \end{array}\right)=\left(\begin{array}{ccccccc} 1 & 0 & 0 & 1 & 0 & 1 & 0\\ 1 & 0 & 0 & 1 & 0 & 1 & 0\\ 1 & 0 & 0 & 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 1 & 0 & 1 & 0\\ & & & \vdots\\ 1 & 1 & 0 & 1 & 0 & 1 & 0 \end{array}\right), \tag{3}$$ 經過雜訊的通道後，每份原始資料的拷貝都有可能受到一定程度的污染，如同(3)右邊那個含有$1$和$0$的矩陣，假設原始資料如同第一列所示是${\tt [1,0,0,1,0,1,0]}$，但由於傳輸雜訊的關係，每一列所代表的原始資料的拷貝中都可能有一兩個元素從$0$翻成$1$或反之。

　對每一行的元素來說，假設是(3)的第一行，它代表$r$個拷貝中的第一個元素，假設這個元素是$1$，原則上雜訊雖然會使得元素翻號，但應不至於太頻繁的翻號，所以將這$r$第一行的元素加總平均後，如果它的值大於$0.5$代表屬於$1$的數量佔大多數，按照多數決的想法，我們可以推斷原始資料的第一個元素應該是$1$，但如果小於$0.5$，則$0$佔大多數，該處的元素應該是$0$。所以在一開始編碼器複製多個原始資料的拷貝時，等同是讓解碼器能夠糾錯，盡量重建被雜訊通道攪亂的資料。基於這樣的概念，我們可以得到二進制解碼器算法：

1. 輸入經過雜訊通道傳輸後的資料$(\mathbf{x}_1,\mathbf{x}_2,\cdots,\mathbf{x}_r)^T$
2. 將每一行上的值加總並除以$r$得到$\mathbf{x}^\prime=(x_1^\prime,x_2^\prime,\cdots,x_k^\prime)$
3. ${\tt if}~(x_i^\prime > 0.5):~{\tt return}~1$
   ${\tt else:~return}~0$

　原則上來說，如果取$r$是奇數的話，那麼$x^\prime_i\neq 0.5$，亦即經過了雜訊的傳輸後，僅有可能是$0$或$1$佔多數的情況，這樣解碼器則很容易推論原始資料在該處應該是$0$或$1$。但如果$r$是偶數，則便有可能最後在同一行中$0$和$1$一樣多，這樣便無法判別原始資料應該是哪一個，所以在一開始編碼拷貝$r$個原始資料時，$r$應避免取成偶數。用python來實現解碼器算法得到：

def decoder(incoming):
    """
    incoming: data received
    """
    # How many repetitions from the binary encoder
    repeat = len(incoming)
    # Step 2: Summing the incoming data along each column
    corrected = np.sum(incoming, axis=0)/repeat
    
    # Step 3: Returns the reconstructed binary data 
    return (corrected>0.5).astype(int)

上述腳本的第一步使用len是為了得到encode函數到底重複拷貝了幾次資料，所以我們的解碼器decode函數完全不需要使用者額外輸入編碼器重複次數$r$它會從收到的資料自動偵測。

三、實例

在源代碼的網站上會有一個叫做data的資料夾，內含一個garfield.txt的文字檔，裡面共有20736個由$0$和$1$組成的位元組，將之讀進notebook後利用plt的imshow函數便可以得到加菲貓的黑白圖像。源代碼的範例如

# Loading binary text file
data = open("data/garfield.txt","r")
bi_gar = data.readlines()
data.close()

# Convert string to numpy array
# After this, gar_img is an array with dimension (,20736)
# Later on, gar_img will be transmitted via noisy channel  
gar_raw=bi_gar[0].split(",")
gar_array=np.asfarray(gar_raw)

# Reshape the 1-D array into (162,128) array for plotting
plt.imshow(gar_array.reshape((162,128)),cmap="binary_r",interpolation="None")

執行完上面的代碼後應該會得到如圖2的黑白加菲貓，這就是原始資料。
　若把gar_array送進encoder函數裡，它會拷貝三個gar_array，再將它們送進channel函數模擬失真的傳輸過程，將輸出的值一樣用imshow作圖後得到如圖3，三張充滿雜訊的加菲貓黑白圖。

圖3. 通過noisy channel後的三張gar_array的拷貝

　不難發現三張圖都充滿了雜訊，這是由於傳輸的過程當中有$0.1$的機率會使得$0\leftrightarrow 1$產生翻轉，最後有些該出現黑點地方的反而變成白點，應該白色的地方反而變成黑色。但這都沒關係，一樣將這三個副本輸進decoder後將輸出做圖，我們得到了圖4。

圖4. 通過decoder重建後的加菲貓，原始資料經過$R_3$編碼

　通過重建後的加菲貓比未重建前少掉非常多的雜訊，不過還是有一些躁點，這是由於我們編碼採用重複三次的$R_3$，如下的例子 $$\begin{array}{cccccc} 原始 & 1 & 0 & 0 & 1 & 0\\ 編碼 & 111 & 000 & 000 & 111 & 000\\ 傳輸 & 110 & 010 & 000 & 010 & 001\\ 重建 & 1 & 0 & 0 & 0 & 0 \end{array}$$ 由於我們是複製三份一模一樣的原始資料，但傳輸後假設三個副本當種有兩個很不幸地出現錯誤，那麼採多數決的狀況來重建，就會像倒數第二個位元組一樣，經傳輸後反而是錯誤的位元組佔大多數，這時重建的結果則仍然是錯誤的，這便稱做$R_r$編碼的固有錯誤率 (intrinsic error)。給定傳輸通道的發生錯誤的機率$f$，則$R_r$這種編碼經過重建後仍會存在一定比率的錯誤，這是無法消去的。但我們可以推斷，只要重拷貝多次，固有錯誤率應該會降低，即固有錯誤率和$r$成反比。例如在圖5，這次我們取$R_{11}$，即編碼時送出11份拷貝，最後重建的結果會發現很多躁點都消失了，連貓眼都很完美的重現，不像是圖4一樣仍然埋藏在雜訊當中。

圖5. 通過$R_{11}$編碼再重建的加菲貓，許多雜訊都消失了，重建效果良好

3.1 關於固有錯誤率的一些討論

讓我們在結束前花一些時間看看固有錯誤率。以$R_3$為例的話，代表三個副本內只要出現兩個以上的錯誤即會使得重建的結果仍然是錯誤的，由於每個位元組經過傳輸後出現錯誤的機率是$f$，兩個都錯就是$f^2$，再來這兩個錯誤是處在哪個位置並不重要，所以是個排列的問題，必須乘上二項式係數$\left(\begin{array}{c} 3\\ 2 \end{array}\right)=3$，對$f=0.1$來說，理論預測的固有錯誤率是$\left(\begin{array}{c} 3\\ 2 \end{array}\right) f^2=0.03$，即每百個像素平均會錯$2-3$個，對黑白加菲貓共有20736個像素點的情況，固有錯誤率是620個點上下。當然傳輸後很不幸三個副本都翻號也是會導致錯誤，只是這樣的情況的機率等於$f^3=0.001$，所以固有錯誤率的精確值是$0.031$。
　從圖6來看，在加菲貓的$R_3$編碼每個位置的位元都送出三份拷貝，但如果在傳輸的過程中，該位置的位元有兩個以上發生錯誤，像圖6左邊的狀況，則該處的位元不能正確重建。另外右邊$R_5$的狀況，在同個位置的五份拷貝中，只要錯三個以上也不能重建。將這些出現可能出現多個錯誤的機率加總起來，便稱作$R_r$編碼的固有錯誤率$p_{{\rm instri}}(R_{r})$。總括來說，$r$個副本，只要錯超過一半一上，則解碼器不能正確重建原始資料。

圖6. $R_r$編碼中只要拷貝的副本在傳輸後有同個位置的位元超過一半以上出現錯誤則該處的位元重建結果仍然是錯的

　對五個拷貝的副本，五個中錯三個以上的機率用二項式分佈描述是 $$\underbrace{\left(\begin{array}{c} 5\\ 3 \end{array}\right)f^{3}(1-f)^{2}}_{錯3個}+\underbrace{\left(\begin{array}{c} 5\\ 4 \end{array}\right)f^{4}(1-f)}_{錯4個}+\underbrace{f^{5}}_{全錯}\equiv p_{\rm intri}(R_5),$$ 其中$p_{\rm instri}(R_5)$表示$R_5$編碼的固有錯率，而$f$是傳輸時發生錯誤的機率。按照上述的邏輯，對於$R_r$編碼法，只要錯超過一半以上，就會使得解碼的糾錯失效。所以對於$r$個拷貝來說，從錯了$(r+1)/2$個開始，一路錯到滿$r$個的機率是 $$\begin{alignat*}{1} p_{{\rm instri}}(R_{r}) & \equiv\underbrace{\left(\begin{array}{c} r\\ \frac{r+1}{2} \end{array}\right)f^{(r+1)/2}(1-f)^{(r-1)/2}}_{錯\frac{r+1}{2}個}+\underbrace{\left(\begin{array}{c} r\\ \frac{r+3}{2} \end{array}\right)f^{(r+3)/2}(1-f)^{(r-3)/2}}_{錯\frac{r+1}{2}+1個}+\cdots+\underbrace{f^{r}}_{全錯} \\ & =\sum_{n=(r+1)/2}^{r}\left(\begin{array}{c} r\\ n \end{array}\right)f^{n}(1-f)^{r-n},\tag{4} \end{alignat*}$$ 對任何奇數$r$皆成立。通常來說，固有錯誤率最大的貢獻項是首項，即$f$的最低次方項，這是由於$f$通常小於$1$，以$f=0.1$的情況，他的次方每多一次，則其值小一個order，除非二項式係數$\left(\begin{array}{c} r\\ n\end{array}\right)$可以補足因為多乘上一個$f$變小的的損失，所以對於固有錯誤率的計算，通常可以考慮首項或者是next-to-leading-order term便夠精準了。

四、小結

在這個小專題裡我們討論了資訊傳輸時會發生錯誤，但如果能夠適當的引入糾錯，例如在資料傳輸前先將其編碼並放入糾錯資訊，那麼在受方重建資訊時，便能夠盡量得到跟原始資料相仿的結果。
　我們在這裡取的重複編碼法$R_r$其實已經不常被使用了，想像每打一通電話，編碼會送出三份以上的拷貝，就等同我們要付三通電話的費用，再加上這樣頗浪費頻寬，所以後來有許多編碼與糾錯的方式不斷被提出，例如漢明碼 (Hamming's code) 便是一個例子，當然這也是有機會再討論的專題了！


Source on github: I&A4_encode_decode.ipynb