第九章 信道的糾錯編碼

第九章

信道的糾錯編碼第九章信道的糾錯編碼9.1差錯控制的基本形式9.2糾錯碼分類及基本概念9.3線性分組碼

香農第二定理指出,當信息傳輸速率低于信道容量時,通過某種編譯碼方法,就能使錯誤概率為任意小.目前已有許多有效的編譯碼方法,并形成了一門新的技術

—

糾錯編碼技術.

糾錯編碼即信道編碼，與信源編碼一樣都是一種編碼，但兩者的作用是完全不同的。

信源編碼的目的是壓縮冗余度，提高信息的傳輸速率.

信道編碼的目的是提高信息傳輸時的抗干擾能力以增加信息傳輸?shù)目煽啃?9.1差錯控制的基本形式9.1.1前向糾錯方式9.1.2反饋重發(fā)方式9.1.3混合糾錯方式9.1.4信息反饋方式9.1.1前向糾錯（EFC）方式FEC(ForwardErrorControl)方式:發(fā)端發(fā)送有糾錯能力的糾錯碼,接收端收到這些碼后,通過糾錯譯碼器自動地糾正傳輸中的錯誤.信源FEC編碼信道FEC譯碼信宿優(yōu)點是不需要反饋信道;能進行一個用戶對多個用戶的同時通信;譯碼實時性較好;控制電路也比較簡單.缺點是譯碼設備較復雜;編碼效率較低.9.1.2反饋重發(fā)（ARQ）方式ARQ(AutomaticRepeatreQuest)方式:發(fā)端發(fā)出能夠發(fā)現(xiàn)錯誤的檢錯碼,收端譯碼器收到后,判斷在傳輸中有無錯誤產生,并通過反饋信道把檢測結果告訴發(fā)端.發(fā)端把收端認為有錯的消息再次傳送,直到收端認為正確接收為止.信源編碼器正向信道譯碼器信宿緩存器重發(fā)控制器反向信道重發(fā)判決器9.1.2反饋重發(fā)（ARQ）方式優(yōu)點是譯碼設備簡單,在冗余度一定的情況下,碼的檢錯能力比糾錯能力要高得多,因而整個系統(tǒng)能獲得極低的誤碼率.應用ARQ方式必須有一條從收端至發(fā)端的反饋信道.其控制電路比較復雜,傳輸信息的連貫性和實時性也較差.9.1.3混合糾錯（HEC）方式反饋信道ARQFEC

編碼器正向信道FEC

譯碼器ARQ9.1.3混合糾錯（HEC）方式HEC(HybridErrorControl)方式:前兩種方式的結合.發(fā)端發(fā)送的碼既能檢錯、又有一定的糾錯能力.收端譯碼時若發(fā)現(xiàn)錯誤個數(shù)在碼的糾錯能力以內,則自動進行糾錯;若錯誤個數(shù)超過了碼的糾錯能力,但能檢測出來,則通過反饋信道告知發(fā)方重發(fā).這種方式在一定程度上避免了FEC方式譯碼設備復雜和ARQ方式信息連貫性差的缺點.9.1.4信息反饋（IRQ）方式信息信號信息信號發(fā)端收端IRQ(InformationRepeatRequest)方式:收端把收到的碼全部由反饋信道送回發(fā)端,在發(fā)端進行比較,發(fā)現(xiàn)錯誤后,把出錯的碼再次重發(fā),直到收端正確接收為止.方法和設備簡單,無需糾、檢錯編譯系統(tǒng).但需要雙向信道,傳輸效率↓、實時性差.糾錯方式小結可糾正錯誤的碼發(fā)收FEC能夠發(fā)現(xiàn)錯誤的碼發(fā)收ARQ應答信號能夠發(fā)現(xiàn)和糾正錯誤的碼發(fā)收HEC應答信號

信息信號發(fā)收IRQ信息信號9.2糾錯碼分類及基本概念9.2.1糾錯碼分類9.2.2糾錯碼的基本概念及其糾錯能力9.2.1糾錯碼分類

根據(jù)干擾和噪聲形式對信道分類隨機信道:

錯碼出現(xiàn)是隨機的,統(tǒng)計獨立的.例如,高斯白噪聲信道,衛(wèi)星信道、同軸電纜、光纜信道等.—糾隨機差錯碼.突發(fā)信道:

錯碼成串集中出現(xiàn),在很短的時間出現(xiàn)大量錯碼,而過后又存在較大的無錯碼位.例如,移動通信信道、短波信道、帶擦傷的光盤等.—糾突發(fā)差錯碼.混合信道:

既存在隨機錯碼,又存在突發(fā)錯碼,兩者均不能忽略.—糾混合差錯碼.9.2.1糾錯碼分類

按應用目的分類檢錯碼:能發(fā)現(xiàn)錯誤但不能糾正錯誤的碼.糾錯碼:不僅能發(fā)現(xiàn)錯誤而且還能糾正錯誤的碼.糾刪碼:

能夠糾正被刪除了信息的錯誤的碼.9.2.1糾錯碼分類

按碼的結構中對信息序列處理方式分類分組碼:把信息序列以每k個碼元分組(信息組),編碼器將每個信息組按一定規(guī)律產生r個多余的碼元(校驗元),形成一個長為n=k+r的碼字.記為(n,k)碼.卷積碼:把信息序列以每k個分組,通過編碼器輸出長為n的一個子碼,該子碼的n－k個校驗元不僅與本子碼的信息元有關,而且與其前L個子碼的信息元有關.記為(n,k,L)碼.9.2.1糾錯碼分類

按碼的數(shù)學結構中校驗元與信息元關系分類線性碼:校驗元與信息元之間呈線性關系的碼.非線性碼:校驗元與信息元之間呈非線性關系的碼.線性碼的理論較成熟,但非線性碼出現(xiàn)許多好碼.

按碼是否具有循環(huán)性分類循環(huán)碼:分組碼中的任一碼字的碼元循環(huán)移位后仍是這組的碼字.非循環(huán)碼:分組碼中的任一碼字的碼元循環(huán)移位后不一定是這組的碼字.9.2.1糾錯碼分類

按碼元取值分類二元碼和多元(q)碼.

按構造碼的數(shù)學理論分類代數(shù)碼:建立在近世代數(shù)基礎上.線性分組碼是代數(shù)碼中一類重要的碼.幾何碼:數(shù)學理論基礎是投影幾何學.算術碼:數(shù)學理論基礎是數(shù)論、高等算術.組合碼:數(shù)學理論基礎是排列組合和數(shù)論.9.2.1糾錯碼分類9.2.2糾錯碼的基本概念及糾錯能力

碼字信息元校驗元

信道編碼器將輸入信息序列,每k個信息符號分成一組(信息組,個),記為,其中稱為信息元.

編碼器將每個信息組按一定規(guī)律產生r個多余的符號(校驗元),形成一個長為n=k+r的碼字.碼字中每個符號稱為碼元.

不同的n長的碼符號序列總共有種,(n,k)分組碼的個稱為許用碼字,其余稱為禁用碼字.9.2.2糾錯碼的基本概念及糾錯能力

碼字的漢明重量

碼字中含非零碼元的個數(shù)稱為碼字的漢明重量.記作W(C).設二元碼字,則例如,碼字10110,碼重W=3.9.2.2糾錯碼的基本概念及糾錯能力

錯誤圖樣設發(fā)送碼接收碼接收碼組和發(fā)送碼組之差為(模2減)E稱為錯誤圖樣.無差錯發(fā)生有差錯發(fā)生碼字、接收序列和錯誤圖樣的關系:9.2.2糾錯碼的基本概念及糾錯能力

錯誤圖樣在二元無記憶信道中,發(fā)生一位隨機差錯的錯誤圖樣個數(shù)二位隨機差錯的錯誤圖樣個數(shù)發(fā)生e位隨機差錯的錯誤圖樣個數(shù)全錯的錯誤圖樣個數(shù)全對的錯誤圖樣個數(shù)9.2.2糾錯碼的基本概念及糾錯能力

分組碼糾錯能力與碼最小距離的關系碼距的幾何意義:以n=3的編碼為例,a2a1a0(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a1碼距是n維空間中單位正多面體頂點之間的漢明距離.發(fā)送碼字000和111,最小距離是3,可以糾正1位碼元的錯誤,檢測2位碼元的錯誤.9.2.2糾錯碼的基本概念及糾錯能力

分組碼的碼率(n,k)分組碼的許用碼組數(shù)為M=2k,R稱作信道信息傳輸率,也稱作碼率.它表示了信息位在分組碼碼字中的比重.一個好的實際糾錯編碼方案,不但希望其糾錯檢錯能力強,而且希望其碼率高.9.3線性分組碼9.3.1一致校驗矩陣和生成矩陣9.3.2伴隨式及標準陣列譯碼9.3.3漢明碼9.3.1一致校驗矩陣和生成矩陣分組碼:把信息序列以每k個碼元分組(信息組),編碼器將每個信息組按一定規(guī)律產生r個多余的碼元(校驗元),形成一個長為n=k+r的碼字.記為(n,k)碼.線性碼:校驗元與信息元之間呈線性關系的碼.各碼元應滿足齊次線性方程:

一致校驗方程9.3.1一致校驗矩陣和生成矩陣各碼元應滿足齊次線性方程:

一致校驗方程共r個方程,k個獨立變量—

k個獨立的信息元,r個校驗元可由此方程給出.例某(7,3)線性分組碼,k=3,r=4,決定校驗元的齊次線性方程組如下9.3.1一致校驗矩陣和生成矩陣

一致校驗方程共r個方程,k個獨立變量—

k個獨立的信息元,r個校驗元可由此方程給出.上式稱一致校驗方程,式中c6,c5,c4是獨立的,其余4位可由這三個量求得.例某(7,3)線性分組碼,k=3,r=4,決定校驗元的齊次線性方程組如下9.3.1一致校驗矩陣和生成矩陣

一致校驗方程令信息組中,信息組m2m1m0

碼字c6c5c4c3c2c1c000000000000010011101010010011101101110101001001110101101001111011010011111110100得(7,3)線性分組碼表19.3.1一致校驗矩陣和生成矩陣

一致校驗矩陣上式稱一致校驗方程,式中c6,c5,c4是獨立的,其余4位可由這三個量求得.矩陣形式表示方程9.3.1一致校驗矩陣和生成矩陣

一致校驗矩陣矩陣形式表示方程令矩陣

稱為(7,3)分組碼的一致校驗矩陣.9.3.1一致校驗矩陣和生成矩陣

一致校驗矩陣

矩陣的每一行是線性方程組中各方程的系數(shù).一般分組碼的一致校驗矩陣,階:信息元和校驗元之間的校驗關系完全由一致校驗矩陣確定.9.3.1一致校驗矩陣和生成矩陣

生成矩陣前例中,信息組中得(7,3)線性分組碼校驗元例9.29.3.1一致校驗矩陣和生成矩陣

生成矩陣前例中,信息組中得(7,3)線性分組碼碼字例9.29.3.1一致校驗矩陣和生成矩陣

生成矩陣矩陣形式表示方程例9.29.3.1一致校驗矩陣和生成矩陣

生成矩陣令矩陣

稱為(7,3)分組碼的生成矩陣.矩陣形式表示方程例9.29.3.1一致校驗矩陣和生成矩陣

生成矩陣信息組m2m1m0

碼字c6c5c4c3c2c1c000000000000010011101010010011101101110101001001110101101001111011010011111110100生成矩陣

的行矢量是(7,3)碼的一個碼字.所有碼字可由此行矢量線性組合獲得.令矩陣

的三個碼字是線性無關的,即獨立的.表19.3.1一致校驗矩陣和生成矩陣

生成矩陣對于一般的線性分組碼(n,k),設有一組k個線性獨立的碼字,生成矩陣為階,9.3.1一致校驗矩陣和生成矩陣

系統(tǒng)碼信息組m2m1m0

碼字c6c5c4c3c2c1c000000000000010011101010010011101101110101001001110101101001111011010011111110100若信息組以不變的形式,在碼字的任意k位中出現(xiàn)的碼;否則,稱為非系統(tǒng)碼.若生成矩陣能把信息元保留在各碼字的最左邊k位上,此系統(tǒng)碼的生成矩陣G稱為標準生成矩陣.表19.3.1一致校驗矩陣和生成矩陣對于某(n,k)線性分組碼C,在2k個碼字中k個獨立碼字組不止一種.對于同一碼,當選取不同的獨立碼字組構成的生成矩陣G也可不同.但經過若干次矩陣的初等變換后,可變成其等價的標準生成矩陣.

系統(tǒng)碼9.3.1一致校驗矩陣和生成矩陣

不同的生成矩陣例9.3二元(7,3)線性碼,生成矩陣信息組m2m1m0

碼字c6c5c4c3c2c1c000000000000011110100010101001101101001111001001110101011101011000111011111101001表2生成非系統(tǒng)碼.G2經過初等變換,得標準生成矩陣①②③②+③①+②碼字同表19.3.1一致校驗矩陣和生成矩陣

另取標準生成矩陣信息組m2m1m0

碼字c6c5c4c3c2c1c000000000000010011110010010011101101110011001001011101101010111011011001111110010表3生成系統(tǒng)碼,不同的(7,3)線性分組碼.碼字不同表19.3.1一致校驗矩陣和生成矩陣(n,k)線性分組碼的重要性質(1)(n,k)線性分組碼由其生成矩陣G或校驗矩陣

H確定.(2)封閉性.(n,k)碼中任意兩個許用碼字之和仍為許用碼字.證明(3)含有零碼字.n位長,(n,k)碼的許用碼字.9.3.1一致校驗矩陣和生成矩陣(n,k)線性分組碼的重要性質(4)所有許用碼字可由其中一組k個獨立碼字線性組合而成.(5)碼的最小距離等于非零碼的最小重量.證明9.3.1一致校驗矩陣和生成矩陣

最小距離d與一致校驗矩陣H之間的關系定理設(n,k)線性分組碼C的校驗矩陣為H,則碼的最小距離d的充要條件是H中任意d-1個列矢量線性無關,且有d個列矢量線性相關.證明必要性:必有一碼字C,具有d個非零分量.因此H中一定有d個列矢量是線性相關的.而d-1個線性無關.充分性:類似.9.3.1一致校驗矩陣和生成矩陣

最小距離d與一致校驗矩陣H之間的關系

由定理知,當所有列矢量相同時,其排列位置不同的H矩陣所對應的(n,k)碼,都有相同的最小距離,則它們在糾錯能力和碼率上是完全等價的.

對于分組碼來說,系統(tǒng)碼和非系統(tǒng)碼的糾錯能力是相同的.由于系統(tǒng)碼的編、譯碼較非系統(tǒng)碼簡單,且G和H可以方便地互求,主要討論系統(tǒng)碼.例9.4前例(7,3)線性分組碼,k=3,r=4,標準一致矩陣為(1)任何三列相加均非零,最少相關列數(shù)是4.(2)信息組m2m1m0

碼字c6c5c4c3c2c1c000000000000010011101010010011101101110101001001110101101001111011010011111110100表1(3)驗證例9.4前例(7,3)線性分組碼,k=3,r=4,G2生成非系統(tǒng)碼信息組m2m1m0

碼字c6c5c4c3c2c1c000000000000011110100010101001101101001111001001110101011101011000111011111101001表2例9.4前例(7,3)線性分組碼,k=3,r=4,G2生成非系統(tǒng)碼此時:一致校驗方程例9.4前例(7,3)線性分組碼,k=3,r=4,G2生成非系統(tǒng)碼對應G2一致校驗矩陣此時:一致校驗方程例9.4前例(7,3)線性分組碼,k=3,r=4,G2生成非系統(tǒng)碼H1與H2不同,但最小相關數(shù)也是4.

G2與G1都生成(7,3,4)分組碼,糾錯能力是1,碼率是3/7.因此說G2與G1是等價的.對應G2一致校驗矩陣例9.4前例(7,3)線性分組碼,k=3,r=4,G3生成系統(tǒng)碼H3最小相關數(shù)仍是4.G3與G1生成(7,3,4)碼不同,但糾錯能力、碼率相同.因此說G3與G1也是等價的.對應G2一致校驗矩陣9.3.2伴隨式及標準陣列譯碼

線性碼的糾錯與伴隨式令S與發(fā)送的許用碼字無關,僅與錯誤圖樣E有關.稱S為R的伴隨式.不同的錯誤圖樣對應不同的伴隨式.根據(jù)伴隨式判斷和糾正傳輸差錯.設(n,k)線性分組碼發(fā)送許用碼字,經信道傳輸后,接收序列是,錯誤圖樣為

.可以將接收碼字

用一致校驗方程進行檢驗:

線性碼的糾錯與伴隨式令S與發(fā)送的許用碼字無關,僅與錯誤圖樣E有關.稱S為R的伴隨式.不同的錯誤圖樣對應不同的伴隨式.根據(jù)伴隨式判斷和糾正傳輸差錯.例9.5前例(7,3)線性分組碼,k=3,r=4,標準一致矩陣為(1)傳送時沒發(fā)生差錯,

線性碼的糾錯與伴隨式例9.5前例(7,3)線性分組碼,k=3,r=4,標準一致矩陣為(1)傳送時沒發(fā)生差錯,(2)傳送時發(fā)生1位碼元差錯,H1中的第1列矢量H1中的第3列矢量若發(fā)送碼字和,都發(fā)生E1錯誤,接收序列為和

線性碼的糾錯與伴隨式伴隨式與發(fā)送碼字無關,僅與錯誤圖樣有關!當發(fā)生1位差錯在第i位上,伴隨式Si正好是其H中第i列矢量.(3)傳送時發(fā)生2位碼元差錯,若

線性碼的糾錯與伴隨式(3)傳送時發(fā)生2位碼元差錯,若伴隨式不為零,說明傳送的碼字發(fā)生了差錯;由于不同的錯誤圖樣對應相同的伴隨式,無法糾正發(fā)生的2位差錯;原因,只能糾正1位碼元的錯誤.

線性碼的糾錯與伴隨式(4)傳送時發(fā)生3位差錯,伴隨式不為零,說明傳送的碼字發(fā)生了差錯;若用于糾正1位碼元的錯誤,則無法檢測出發(fā)生3位碼元的錯誤;或者只用于檢測差錯,能檢測出任意小于或等于3位差錯的錯誤.伴隨式不為零,說明傳送的碼字發(fā)生了差錯;由于不同的錯誤圖樣對應相同的伴隨式,無法糾正發(fā)生的2位差錯;原因,只能糾正1位碼元的錯誤.

線性碼的糾錯與伴隨式此碼能糾正單個錯誤,同時檢測出2個錯誤;dmin

≥t+e+12)用于檢查3個錯誤.dmin

≥e+1

總結:時,

9.3.2伴隨式及標準陣列譯碼

最小距離譯碼規(guī)則滿足n次無記憶擴展信道中,隨機差錯的錯誤圖樣E出現(xiàn)的概率為發(fā)生1位隨機錯誤發(fā)生2位隨機錯誤9.3.2伴隨式及標準陣列譯碼n次無記憶擴展信道中,隨機差錯的錯誤圖樣E出現(xiàn)的概率為發(fā)生1位隨機錯誤發(fā)生2位隨機錯誤發(fā)生e位隨機錯誤發(fā)生n位全錯9.3.2伴隨式及標準陣列譯碼

一般采用最大似然譯碼規(guī)則,在BSC信道中,重量最小的E,發(fā)生的概率最大.因此選取最輕的E作為譯碼的錯誤圖樣.這也是采用了最小距離譯碼準則.發(fā)生e位隨機錯誤發(fā)生n位全錯9.3.2伴隨式及標準陣列譯碼

線性分組碼的基本譯碼步驟Step1:

由接收到的序列R,計算伴隨式S=RHT

;Step2:

若S=0,正確接收;若S不為零,尋找錯誤圖樣;Step3:

由錯誤圖樣解出碼字C=R+E.

標準陣列譯碼步驟Step1:

接收序列R;Step2:

查標準陣列譯碼表,直接得到譯碼C.9.3.2伴隨式及標準陣列譯碼

標準陣列譯碼表構造方法(1)根據(jù)許用碼字將禁用碼字進行分類,分類的依據(jù)是錯誤圖樣.9.3.2伴隨式及標準陣列譯碼錯誤圖樣E0+Cj

=Cj………………碼字禁用碼字標準陣列譯碼(陪集首)E0+C1=C1E0+C0=0E1+C0=E1E1+C1E1+Cj…E2+C0=E2E2+C1E2+Cj……S0

S1

S2

…伴隨式

標準陣列譯碼表構造方法9.3.2伴隨式及標準陣列譯碼(1)根據(jù)許用碼字將禁用碼字進行分類,分類的依據(jù)是錯誤圖樣.(2)先把全部2k個碼字,C0,C1,…，置于表的第一行；(3)在余下的2n－2k個禁用碼字中,選擇一個重量最輕的n長序列記作E1,作為第二行的首位元素,于是第二行的元素是E1和每個碼字Ci（i＝0,1,…,2k-1）相加.

標準陣列譯碼表構造方法9.3.2伴隨式及標準陣列譯碼(4)在余下的禁用碼字中,再選擇一個重量最輕的n長序列記作E2,作為第三行的首位元素,于是第三行的元素是E2和每個碼字Ci（i＝0,1,…,2k-1）相加.(5)依此類推,直到全部禁用碼字分完為止.(6)在表的最前面增加一列,為錯誤圖樣對應的伴隨式Si.

標準陣列譯碼表構造方法9.3.2伴隨式及標準陣列譯碼(1)標準陣列譯碼表是一個2n－k行、2k列的陣列.(2)表中每列元素組成一個子集,許用碼字Cj（j＝0,1,…,2k-1）是它的子集首.(3)表中每一行稱為一個陪集,每一行的首位元素Ei

（i＝0,1,…,2n-k-1）稱作陪集首.

標準陣列譯碼表構成小結9.3.2伴隨式及標準陣列譯碼(1)如果把陪集首看成是錯誤圖樣,則同一陪集中的所有元素都對應相同的伴隨式,而不同的陪集具有不同的伴隨式.(2)對于同一列的各子集來說,2n-k個序列的錯誤圖樣雖然不同,但都對應同一個許用碼字.

標準陣列特性

標準陣列譯碼方法方法1:

在表中搜尋接收碼字R,把R所在列的子集首Cj作為譯碼;方法2:

求出伴隨式S,找出S所在行中的R,把R所在列的子集首Cj作為的譯碼.例9.6設(5,2)系統(tǒng)線性碼的生成矩陣G,構造該碼的標準陣列譯碼表.若接收碼,求發(fā)送碼的估值.解:(1)信息組,求出許用碼字(2)求出校驗矩陣(3)求最小距離錯誤圖樣(陪集首)碼字禁用碼字標準陣列譯碼伴隨式C1=01101C0=00000C2=10111C3=11010S0=000S1=111E1=100001110100111

01010

E2=01000001011111110010E3=00100010011001111110E4=00010011111010111000E5=00001011001011011011E6=00011011101010011001E7=00110010111000111100S2=101S3=100S4=010S5=001S6=011S7=110能糾正1位隨機錯誤！(4)構造標準陣列譯碼表(5)對接收碼譯碼選擇不唯一9.3.2伴隨式及標準陣列譯碼(1)標準陣列譯碼表需要存入2n個R,隨n呈指數(shù)增大.

簡化譯碼表(2)只保留標準陣列譯碼表中伴隨式Si和錯誤圖樣Ei(3)由R計算出伴隨式S

由表查找S對應的錯誤圖樣E

計算SiEiS0=000E0=00000S1=111S2=101S3=100S4=010S5=001E1=1000