編碼原理

這里主要介紹線性編碼有關(guān)內(nèi)容

線性編碼

術(shù)語(yǔ)代數(shù)編碼理論表示編碼原理的子領(lǐng)域，其編碼性質(zhì)以代數(shù)術(shù)語(yǔ)表示，然后進(jìn)一步研究 。

代數(shù)編碼理論基本上分為兩大類代碼：

線性分組碼

卷積碼

它分析一個(gè)編碼的以下三個(gè)特性-主要是：

碼字長(zhǎng)度

有效代碼字總數(shù)

兩個(gè)有效代碼字之間的最小距離，主要使用漢明距離，有時(shí)也使用其他距離像Lee距離。

線性分組碼

線性分組碼具有的特性的線性度，即，任何兩個(gè)碼字的總和也是一個(gè)編碼字，并且它們被應(yīng)用到組的源比特中，因此稱為線性分組碼。有分組碼不是線性的，但是很難證明編碼是沒(méi)有這個(gè)屬性的編碼。

線性分組碼由其符號(hào)字母（例如，二進(jìn)制或三元）和參數(shù)（n，m，

n是碼字的長(zhǎng)度，以符號(hào)表示，

m是將一次用于編碼的源符號(hào)的數(shù)量，

有許多類型的線性分組碼，如循環(huán)碼（如漢明碼）、重復(fù)代碼、奇偶校驗(yàn)碼、多項(xiàng)式編碼（例如BCH碼）、里德 - 所羅門編碼、代數(shù)幾何編碼、里德 - 穆勒編碼、完美編碼。

編碼原理使用N維球體模型。例如，可以在桌面上或三維中將多少便士包裝成圓圈，可以將多少個(gè)彈珠包裝在一個(gè)球面上。其他注意事項(xiàng)輸入編碼的選擇。例如，六邊形包裝成矩形框的約束將在角落留下空的空間。隨著尺寸越來(lái)越大，空白空間的百分比越來(lái)越小。但是在某些維度上，包裝使用所有空間，這些代碼是所謂的“完美”代碼。唯一非常重要和有用的完美編碼是距離為3漢明碼，其參數(shù)滿足（2 r - 1，2 r - 1 - r，3）和[23,12,7]二進(jìn)制和[11,6,5 ]三重Golay碼。

另一個(gè)編碼屬性是單個(gè)碼字可能具有的鄰居的數(shù)量。再次，以便士為例。首先我們把便士打包成矩形網(wǎng)格。每一分錢將有4個(gè)鄰近的鄰居（在距離更遠(yuǎn)的角落有4個(gè)）。在六邊形，每一分錢將有6個(gè)近鄰。當(dāng)我們?cè)黾映叽鐣r(shí)，近鄰的數(shù)量增加非?？?。結(jié)果是使接收端選擇鄰居（因此錯(cuò)誤）的噪聲的方式也增加。這是分組碼以及所有編碼的基本限制。可能更難對(duì)單個(gè)鄰居造成錯(cuò)誤，但鄰居數(shù)量可能足夠大，因此總錯(cuò)誤概率實(shí)際上會(huì)受到影響。

線性分組碼的屬性可以應(yīng)用于很多應(yīng)用。例如，線性分組碼的校正子集合唯一性被用網(wǎng)格成形，是最有名的形狀碼之一。傳感器網(wǎng)絡(luò)中使用相同的屬性進(jìn)行分布式源代碼編碼。

卷積碼

如果特定的一致監(jiān)督關(guān)系不是在一個(gè)碼字中實(shí)現(xiàn)，而是在個(gè)碼字中實(shí)現(xiàn)，這種碼稱為卷積碼。卷積碼可用移位寄存器來(lái)實(shí)現(xiàn)，這種卷積編碼器的輸出可看作是輸入信息碼元序列與編碼器響應(yīng)函數(shù)的卷積。能糾正突發(fā)錯(cuò)誤的哈格伯爾格碼也是一種卷積碼。在平穩(wěn)高斯噪聲干擾的信道上采用序貫譯碼方法的卷積碼有很好的性能，能用于衛(wèi)星通信和深空通信。

UTF-8 編碼原理

為了統(tǒng)一全世界各國(guó)語(yǔ)言文字和專業(yè)領(lǐng)域符號(hào)（例如數(shù)學(xué)符號(hào)、樂(lè)譜符號(hào)）的編碼，ISO制定了ISO 10646標(biāo)準(zhǔn)，也稱為UCS（Universal Character Set）。UCS編碼的長(zhǎng)度是31位，可以表示231個(gè)字符。如果兩個(gè)字符編碼的高位相同，只有低16位不同，則它們屬于一個(gè)平面（Plane），所以一個(gè)平面由216個(gè)字符組成。目前常用的大部分字符都位于第一個(gè)平面（編碼范圍是U-00000000~U-0000FFFD），稱為BMP（Basic Multilingual Plane）或Plane 0，為了向后兼容，其中編號(hào)為0~256的字符和Latin-1相同。UCS編碼通常用U-xxxxxxxx這種形式表示，而BMP的編碼通常用 U xxxx這種形式表示，其中x是十六進(jìn)制數(shù)字。在ISO制定UCS的同時(shí)，另一個(gè)由廠商聯(lián)合組織也在著手制定這樣的編碼，稱為Unicode，后來(lái)兩家聯(lián)手制定統(tǒng)一的編碼，但各自發(fā)布各自的標(biāo)準(zhǔn)文檔，所以UCS編碼和Unicode碼是相同的。

有了字符編碼，另一個(gè)問(wèn)題就是這樣的編碼在計(jì)算機(jī)中怎么表示?，F(xiàn)在已經(jīng)不可能用一個(gè)字節(jié)表示一個(gè)字符了，最直接的想法就是用四個(gè)字節(jié)表示一個(gè)字符，這種表示方法稱為UCS-4或UTF- 32，UTF是Unicode Transformation Format的縮寫。一方面這樣比較浪費(fèi)存儲(chǔ)空間，由于常用字符都集中在BMP，高位的兩個(gè)字節(jié)通常是0，如果只用ASCII碼或Latin-1，高位的三個(gè)字節(jié)都是0。另一種比較節(jié)省存儲(chǔ)空間的辦法是用兩個(gè)字節(jié)表示一個(gè)字符，稱為UCS-2或UTF-16，這樣只能表示BMP中的字符，但BMP中有一些擴(kuò)展字符，可以用兩個(gè)這樣的擴(kuò)展字符表示其它平面的字符，稱為Surrogate Pair。無(wú)論是UTF-32還是UTF-16都有一個(gè)更嚴(yán)重的問(wèn)題是和C語(yǔ)言不兼容，在C語(yǔ)言中0字節(jié)表示字符串結(jié)尾，庫(kù)函數(shù)strlen、 strcpy等等都依賴于這一點(diǎn)，如果字符串用UTF-32存儲(chǔ)，其中有很多0字節(jié)并不表示字符串結(jié)尾，這就亂套了。

UNIX之父Ken Thompson提出的UTF-8編碼很好地解決了這些問(wèn)題，現(xiàn)在得到廣泛應(yīng)用。UTF-8具有以下性質(zhì)：

* 編碼為U 0000~U 007F的字符只占一個(gè)字節(jié)，就是0x00~0x7F，和ASCII碼兼容。

* 編碼大于U 007F的字符用2~6個(gè)字節(jié)表示，每個(gè)字節(jié)的最高位都是1，而ASCII碼的最高位都是0，因此非ASCII碼字符的表示中不會(huì)出現(xiàn)ASCII碼字節(jié)（也就不會(huì)出現(xiàn)0字節(jié)）。

* 用于表示非ASCII碼字符的多字節(jié)序列中，第一個(gè)字節(jié)的取值范圍是0xC0~0xFD，根據(jù)它可以判斷后面有多少個(gè)字節(jié)也屬于當(dāng)前字符的編碼。后面每個(gè)字節(jié)的取值范圍都是0x80~0xBF，見(jiàn)下面的詳細(xì)說(shuō)明。

* UCS定義的所有231個(gè)字符都可以用UTF-8編碼表示出來(lái)。

* UTF-8編碼最長(zhǎng)6個(gè)字節(jié)，BMP字符的UTF-8編碼最長(zhǎng)三個(gè)字節(jié)。

* 0xFE和0xFF這兩個(gè)字節(jié)在UTF-8編碼中不會(huì)出現(xiàn)。

具體來(lái)說(shuō)，UTF-8編碼有以下幾種格式：

U-00000000 – U-0000007F: 0xxxxxxx

U-00000080 – U-000007FF: 110xxxxx 10xxxxxx

U-00000800 – U-0000FFFF: 1110xxxx 10xxxxxx10xxxxxx

U-00010000 – U-001FFFFF: 11110xxx 10xxxxxx10xxxxxx 10xxxxxx

U-00200000 – U-03FFFFFF: 111110xx 10xxxxxx10xxxxxx 10xxxxxx 10xxxxxx

U-04000000 – U-7FFFFFFF: 1111110x 10xxxxxx10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx

第一個(gè)字節(jié)要么最高位是0（ASCII字節(jié)），要么最高兩位都是1，最高位之后1的個(gè)數(shù)決定后面有多少個(gè)字節(jié)也屬于當(dāng)前字符編碼，例如111110xx，最高位之后還有四個(gè)1，表示后面有四個(gè)字節(jié)也屬于當(dāng)前字符的編碼。后面每個(gè)字節(jié)的最高兩位都是10，可以和第一個(gè)字節(jié)區(qū)分開(kāi)。這樣的設(shè)計(jì)有利于誤碼同步，例如在網(wǎng)絡(luò)傳輸過(guò)程中丟失了幾個(gè)字節(jié)，很容易判斷當(dāng)前字符是不完整的，也很容易找到下一個(gè)字符從哪里開(kāi)始，結(jié)果頂多丟掉一兩個(gè)字符，而不會(huì)導(dǎo)致后面的編碼解釋全部混亂了。上面的格式中標(biāo)為x的位就是UCS編碼，最后一種6字節(jié)的格式中x位有31個(gè)，可以表示31位的UCS編碼，UTF-8就像一列火車，第一個(gè)字節(jié)是車頭，后面每個(gè)字節(jié)是車廂，其中承載的貨物是UCS編碼。UTF-8規(guī)定承載的UCS編碼以大端表示，也就是說(shuō)第一個(gè)字節(jié)中的x是UCS編碼的高位，后面字節(jié)中的x是UCS編碼的低位。

例如U 00A9（?字符）的二進(jìn)制是10101001，編碼成UTF-8是11000010 10101001（0xC2 0xA9），但不能編碼成11100000 10000010 10101001，UTF-8規(guī)定每個(gè)字符只能用盡可能少的字節(jié)來(lái)編碼。

編碼原理是對(duì)編碼的屬性及其各自適用于具體應(yīng)用的方法研究。編碼用于數(shù)據(jù)壓縮，加密，糾錯(cuò)和網(wǎng)絡(luò)。編碼在各種科學(xué)學(xué)科（如信息理論，電氣工程，數(shù)學(xué)，語(yǔ)言學(xué)和計(jì)算機(jī)科學(xué)）都有研究 -旨在設(shè)計(jì)高效可靠的數(shù)據(jù)傳輸方法。這通常涉及去除冗余以及發(fā)送數(shù)據(jù)中的錯(cuò)誤的校正或檢測(cè)。實(shí)現(xiàn)編碼的具體方法和電路很多，方法有低速編碼和高速編碼、線性編碼和非線性編碼；電路有逐次比較型、級(jí)聯(lián)型和混合型編碼。 編碼原理按照應(yīng)用來(lái)分可以分為算術(shù)編碼原理，音頻編碼原理、圖像編碼原理、字符編碼原理等。

卷積碼擁有良好的糾錯(cuò)性能，是一種被廣泛應(yīng)用于移動(dòng)通信的信道編碼系統(tǒng)。一個(gè)（n，k，m）卷積碼編碼器由k個(gè)輸入，具有m階存儲(chǔ)的n個(gè)輸出的線形時(shí)序電路實(shí)現(xiàn)。通常， n和k是較小的整數(shù)，且

反向CDMA信道使用（3，1，8）卷積碼，碼率

該電路由一個(gè)八位寄存器、三個(gè)碼生成邏輯、一個(gè)時(shí)隙發(fā)生器和一個(gè)四選一復(fù)用器構(gòu)成。mux的輸入為

卷積編碼器的初始狀態(tài)用rst異步清零信號(hào)置為0，

假設(shè)我們只有一個(gè)沒(méi)有帶類別標(biāo)簽的訓(xùn)練樣本集合

自編碼神經(jīng)網(wǎng)絡(luò)嘗試學(xué)習(xí)一個(gè)

我們剛才的論述是基于隱藏神經(jīng)元數(shù)量較小的假設(shè)。但是即使隱藏神經(jīng)元的數(shù)量較大（可能比輸入像素的個(gè)數(shù)還要多），我們?nèi)匀煌ㄟ^(guò)給自編碼神經(jīng)網(wǎng)絡(luò)施加一些其他的限制條件來(lái)發(fā)現(xiàn)輸入數(shù)據(jù)中的結(jié)構(gòu)。具體來(lái)說(shuō)，如果我們給隱藏神經(jīng)元加入稀疏性限制，那么自編碼神經(jīng)網(wǎng)絡(luò)即使在隱藏神經(jīng)元數(shù)量較多的情況下仍然可以發(fā)現(xiàn)輸入數(shù)據(jù)中一些有趣的結(jié)構(gòu)。

稀疏性可以被簡(jiǎn)單地解釋如下。如果當(dāng)神經(jīng)元的輸出接近于1的時(shí)候我們認(rèn)為它被激活，而輸出接近于0的時(shí)候認(rèn)為它被抑制，那么使得神經(jīng)元大部分的時(shí)間都是被抑制的限制則被稱作稀疏性限制。這里我們假設(shè)的神經(jīng)元的激活函數(shù)是sigmoid函數(shù)。如果你使用tanh作為激活函數(shù)的話，當(dāng)神經(jīng)元輸出為-1的時(shí)候，我們認(rèn)為神經(jīng)元是被抑制的。

注意到

進(jìn)一步，讓

表示隱藏神經(jīng)元

其中，

為了實(shí)現(xiàn)這一限制，我們將會(huì)在我們的優(yōu)化目標(biāo)函數(shù)中加入一個(gè)額外的懲罰因子，而這一懲罰因子將懲罰那些

這里，

其中

這一懲罰因子有如下性質(zhì)，當(dāng)

我們可以看出，相對(duì)熵在

我們的總體代價(jià)函數(shù)可以表示為

其中

為了對(duì)相對(duì)熵進(jìn)行導(dǎo)數(shù)計(jì)算，我們可以使用一個(gè)易于實(shí)現(xiàn)的技巧，這只需要在你的程序中稍作改動(dòng)即可。具體來(lái)說(shuō)，前面在后向傳播算法中計(jì)算第二層（

我們將其換成

就可以了。

有一個(gè)需要注意的地方就是我們需要知道

證明上面算法能達(dá)到梯度下降效果的完整推導(dǎo)過(guò)程不再本教程的范圍之內(nèi)。不過(guò)如果你想要使用經(jīng)過(guò)以上修改的后向傳播來(lái)實(shí)現(xiàn)自編碼神經(jīng)網(wǎng)絡(luò)，那么你就會(huì)對(duì)目標(biāo)函數(shù)