信息與編碼理論 第2版 課件 5.3 線性分組碼

§5.3線性分組碼概述線性分組碼：具有線性性質(zhì)的分組碼。最為重要的一類信道編碼技術，它是討論其它各類碼的基礎。線性分組碼可以用的形式來描述。如果符號只取自于由兩個元素（0和1）構成集合，則稱為二進制碼。

k元組（k-tuples）

n元組（n-tuples）線性映射5.3.1向量空間定義所有二進制元組構成的集合稱為二進制域（包括0和1兩個元素）上的一個向量空間，記作。二進制域中的運算在不混淆的情況下也常常用“+”來表示模2加法。5.3.2線性分組碼的結構子空間向量空間的一個子集如果滿足下列兩個條件，則稱為的一個子空間：1)中包含全零向量；2)中任意兩個向量的和仍然在內(nèi)（封閉性質(zhì)）。線性分組碼構成一個子空間假設和是某二進制分組碼中的兩個碼字向量，則該碼是線性碼的充要條件是也為該碼的許用碼字向量。例如，向量空間中共包括下列個4元組：顯然，下列元素構成的子集是的一個子空間：容易驗證子集中任意兩個向量的和任然是中的一個向量。00000001001000100100100010011010110001010110001111011110011111110000010110101111總結：對于二進制編碼，個元組構成的集合是一個線性分組碼的充要條件是該集合為向量空間（包括所有的元組）的一個子空間。線性分組碼是由個長度為的二進制向量組成的碼字集合；對于任意兩個碼字向量均有；零向量將會是任意線性分組碼中的一個合法碼字向量。對于線性分組碼，碼字重量和碼字之間的距離存在一一對應的關系：由式(5-6)可知，而也是一個合法碼字。最小重量某線性分組碼中所有非零碼字重量的最小值，即線性分組碼的最小重量與最小碼距相等，即線性分組碼的幾何解釋：個元組（圖中所有圓點與方點）構成了向量空間，而該向量空間內(nèi)的個元組（圖中所有方點）構成了一個碼字向量子空間，這些方點代表了合法碼字（或稱許用碼字）。由圖可知選擇編碼方案的基本目標：1）為了提高編碼效率，應該在向量空間中安排盡可能多的碼字向量，這樣才能減少碼字向量中的冗余度；2）許用碼字之間的距離要盡可能的遠，這樣，即使發(fā)送碼字在傳輸過程中受到擾亂，仍然能夠以較高的概率實現(xiàn)正確譯碼。例：線性分組碼該碼共有個消息向量，因此共有8個碼字，但是在向量空間中共有個6元組，所以需要在64個6元組中選擇8個來構成碼的所有許用碼字。下表中的8個碼字構成了向量空間的一個子空間，因此這些碼字就構成了一個線性分組碼。5.3.3生成矩陣對于線性分組碼，利用前述的方法可以建立消息向量與碼字之間的對應關系，并可以用類似于表格的結構存儲下來，這樣編碼器便可以通過查表的方法來實現(xiàn)對不同消息向量的編碼操作。如果的取值較大，則利用查表法實現(xiàn)編碼器的復雜度會非常巨大。以碼為例，該碼共有個（約為）碼字，此時如果仍使用簡單的查表法來進行編碼的話，會對計算機的內(nèi)存空間提出巨大需求。因此需要尋找更為實用的編碼實現(xiàn)方法：可以通過按需生成而非存儲所有碼字的方法來減小編碼過程的復雜度。子空間的基一個線性分組碼的碼字集合是二進制維向量空間的一個維子空間（），所以通?？梢哉业缴儆趥€的元組構成的集合，該集合中的向量可以生成所有的個碼字，此時稱這些向量張成了一個子空間，張成該子空間的最小線性獨立集合稱為子空間的基，而其中包含的向量個數(shù)稱為子空間的維數(shù)。設由個線性獨立的元組向量組成的集合構成一個基，這樣可以使用這些向量來生成所需的線性分組碼，即個碼字中的每一個碼字均可以表示為（取值為0或1）為消息比特。生成矩陣（GeneratorMatrix）如果由個比特組成的消息序列可以表示為如下的行向量則碼字向量可以如下得到：維矩陣。【例5-3】確定表5-3中線性分組碼的生成矩陣?！窘狻窟x取下列3個線性獨立的碼字向量來構成生成矩陣：這樣，使用該生成矩陣便可以生成表5-3中的所有碼字，例如：討論：顯然，碼字向量是生成矩陣中行向量的線性組合。因為一個線性分組碼可以由其生成矩陣來完全確定，因此編碼器僅僅需要存儲的個行向量，而不用存儲所有的個碼字向量。對于本例而言，相比于表5-3中顯示的維碼字向量矩陣，編碼器僅需要存儲維的生成矩陣，這可以極大的降低編碼器的復雜度。5.3.4系統(tǒng)線性分組碼系統(tǒng)碼碼字向量中有連續(xù)位的內(nèi)容與消息向量完全一樣，而剩下的位表示校驗比特。系統(tǒng)線性分組碼的生成矩陣具有如下形式：使用系統(tǒng)碼可以進一步減小編碼器的復雜度。系統(tǒng)形式碼字的生成公式為于是【例5-4】給出表5-3中線性分組碼的碼字生成公式?！窘狻恳驗樵诶?-3中已經(jīng)給出了該碼的生成矩陣，因此該碼的碼字可以如下生成：顯然，利用上式得到的碼字為系統(tǒng)碼。5.3.5監(jiān)督矩陣對于某個碼維的生成矩陣，一定存在一個維的監(jiān)督矩陣（Parity-CheckMatrix），該矩陣的行向量與生成矩陣的行向量正交，即對于該碼的任意一個碼字，均有判斷碼字是由矩陣生成的充要條件為。對于系統(tǒng)碼而言，其生成矩陣形式為，為了保證與生成矩陣之間的正交性要求，其監(jiān)督矩陣顯然應具有如下結構【例5-5】給出表5-3中碼的監(jiān)督矩陣，并驗證?！窘狻坑衫?-3可知該碼的生成矩陣，于是可知監(jiān)督矩陣為因此，可得由例5-4可知，代入上式可得線性分組碼的最小碼距和監(jiān)督矩陣之間關系假如選擇是具有最小重量（或）的碼字，那么由關系式可知監(jiān)督矩陣中有列是線性相關的；另一方面，由于沒有重量小于的碼字，所以中不可能會有少于列是線性相關的。例：觀察例5-5中碼的監(jiān)督矩陣，可以發(fā)現(xiàn)其線性相關的列向量的最小數(shù)目為3，所以可以確定該碼的最小碼距為。

等于中線性相關的列向量的最小數(shù)目，也就是說的列空間是維的。對偶碼一個線性分組碼是向量空間的一個維子空間，因此會有一個正交補集（OrthogonalComplement），即由所有正交于的向量組成的集合。顯然，正交補集是向量空間的一個維子空間，所以也表示了一個線性分組碼，稱為碼的對偶碼（DualCode）?？梢宰C明，碼的生成矩陣是對偶碼的一個監(jiān)督矩陣。5.3.6伴隨式校驗錯誤圖樣（ErrorPattern）對于編碼器輸出的一個碼字，傳輸過程中某些位可能會出錯，這樣經(jīng)過信道傳輸后的接收向量可以表示為式中表示信道傳輸引起的錯誤向量，稱為錯誤圖樣。顯然，對于長度為的二進制碼字，一共有個可能的非零錯誤圖樣。伴隨式（Syndrome）對于接收向量，定義下面的維向量為對應于的伴隨式：譯碼器為了進行校驗會計算其伴隨式：如果是一個合法碼字，則其對應的伴隨式；如果中包含可檢測到的錯誤，則其對應的伴隨式中會有非零元素值；如果中包含可糾正的錯誤，則其伴隨式中會有特殊的非零值來標記特定的錯誤圖樣。顯然即由受擾碼字向量或是對應的錯誤圖樣得到的伴隨式是一樣的。線性分組碼有一個重要的性質(zhì)（譯碼的基礎）：可糾正的錯誤圖樣和伴隨式是一一對應的。由上式可知，監(jiān)督矩陣應具有下列兩個重要性質(zhì)：監(jiān)督矩陣的列向量不能有全零向量。否則，在對應的碼字位置發(fā)生的錯誤不會改變伴隨式，故該種錯誤不能檢測到。監(jiān)督矩陣的所有列向量必須彼此不同。否則，如果中的兩列是相同的，則發(fā)生在這兩個對應位置的錯誤將是不可區(qū)分的?！纠?-6】仍考慮前例中的線性分組碼，假設當發(fā)送碼字為時，接收向量是。求伴隨式，并驗證其等于?！窘狻坑山邮障蛄靠傻闷浒殡S式為

顯然錯誤圖樣為，于是5.3.7錯誤糾正標準陣列（StandardArray）對于一個碼，標準陣列是由所有個可能的比特長的接收向量組成的列行的陣列。結構如下：第一行由所有的合法碼字構成，其中第一個元素為全零碼字；第一列包含所有可糾正的錯誤圖樣；每一行稱為一個陪集（Coset），每行的第一個元素表示一個錯誤圖樣，稱為陪集首（CosetLeader），每行后面的元素都是合法碼字被該行陪集首擾亂后的接收向量。標準陣列的結構：結構特點：標準陣列第一行第一列的元素為全零碼字，該元素有雙重作用：既是合法碼字之一，又可看作是一個錯誤圖樣，表示傳輸過程中沒有錯誤發(fā)生，即。標準陣列包含了向量空間中所有的個元組，每個元組在標準陣列中僅出現(xiàn)一次，這樣，每個陪集包含個元組，標準陣列中共有個陪集。利用標準陣列的譯碼思想：將受擾的接收向量（標準陣列中第一行之外的其它元組）糾正為該向量所在列頂部的合法碼字。假設一個合法碼字（）通過一個噪聲干擾的信道傳輸，得到的受擾接收向量為，式中。如果信道引起的錯誤圖樣是一個陪集首，接收向量會被正確的糾正為傳輸碼字；如果錯誤圖樣不是一個陪集首，則會導致譯碼錯誤發(fā)生。陪集的伴隨式如果是第個陪集的陪集首（即錯誤圖樣），則將會是該陪集中的一個元組，該元組的伴隨式為因為是一個合法碼字，所以，于是上式變?yōu)閺纳鲜娇芍号慵藴赎嚵械拿啃校┲械拿恳粋€元素均有相同的伴隨式，而不同陪集對應的伴隨式則彼此均不相同，這樣便可以通過伴隨式來估計對應的錯誤圖樣。糾錯譯碼的步驟：(1)計算接收向量的伴隨式；(2)從標準陣列中找到某個陪集首（錯誤圖樣），使得其伴隨式也等于；(3)利用式將接收向量糾正為合法碼字。該式可以理解為從接收向量中減去了找到的錯誤圖樣，由于是二進制運算，所以減法和加法是相同的。例：對前面討論的碼使用標準陣列來進行譯碼。給出該碼的一個標準陣列，如下表：8個合法碼字構成了標準陣列的第一行。第一列中的7個非零陪集首表示可糾正的錯誤圖樣。在剩下的8個6元組構成的陪集中，可以靈活的選擇一個作為陪集首。所有重量為1的錯誤圖樣（共有6個）均是可以糾正的。注意：當且僅當信道引起的真實錯誤圖樣是該標準陣列中的一個陪集首時，譯碼結果才是正確的。對于一個糾錯能力為的碼，如果標準陣列的陪集首正好包含所有的不大于個錯誤的錯誤圖樣，且不包含任何其它錯誤圖樣（即沒有多余的糾錯能力），則稱該碼為完美碼（PerfectCode）。陪集首的選擇：應按照錯誤圖樣重量從小到大的順序來排列。重量小的錯誤圖樣出現(xiàn)的概率更高，這樣才能使得正確譯碼的概率最高。例如，對于錯誤轉移概率為的二進制對稱信道，上述碼的碼字經(jīng)過該信道傳輸之后，不發(fā)生錯誤的概率為：發(fā)生1比特錯誤的概率為：發(fā)生2比特錯誤的概率為：發(fā)生3比特錯誤的概率為：以此類推。接下來，通過計算的值可以獲得每個陪集首對應的伴隨式，而這些伴隨式均對應可以糾正的錯誤圖樣。即故各個陪集首對應的伴隨式計算結果如右表：糾錯對于接收向量，在計算得到其伴隨式之后，可以通過形如上頁的伴隨式查詢表來找到對應的錯誤圖樣。這樣得到的錯誤圖樣是實際錯誤圖樣的一個估計值，可以記作，然后譯碼器將其與接收向量相加，便可得到發(fā)送碼字的估計值：由上式可知：假如估計的錯誤圖樣與實際的錯誤圖樣相同，即，那么得到的碼字估計值與發(fā)送的實際碼字相等；假如錯誤圖樣的估計值不正確，則譯碼器得到的碼字估計值不是實際的發(fā)送碼字，這會導致無法檢測的譯碼錯誤發(fā)生。【例5-7】繼續(xù)考慮上述碼，假設當發(fā)送碼字為時的接收向量為，利用表5-6所示的伴隨式查詢表對進行譯碼?！窘狻坑山邮障蛄靠梢郧蟮冒殡S式為通過伴隨式