北郵電信院楊鴻文老師通信課件上下冊下冊ln08

1、第 7 周Lecture Notes 8 2006/03/28線性分組碼 問題Fig. 1是一個函數(shù)，它把 k 個信息比特組成的向量 u編為一個 n 比特向量 c。C 是所有可能編碼結(jié)果的集合，它是線性向量空間0,1n 的一個子集。C 也就是函數(shù)f (u) 的值域。BSC 信道在中被模型化為發(fā)送的碼字和錯誤圖樣 e 相加。向量 e 的元素也取于 GF(2)，e 中任何一個位置若為 1，表示這個位置發(fā)生了比特錯誤。譯根據(jù)收到的向量 y 判斷發(fā)送的碼字是什么，譯碼結(jié)果是向量c ，譯碼結(jié)果可能正確（ c = c ），也可能不正確（ c ¹ c ）。譯的輸出究竟應(yīng)該是碼字，還是它所代表的信息

2、無關(guān)緊要，因為知道了碼字就等于知道了信息，特別對于系統(tǒng)碼，這個關(guān)系更為簡明。ML 譯碼的譯碼函數(shù)可以寫為c = argmin dH (y, c)(1)cÎC表示把收到的 y 譯為 C 中離 y 最近的那個。Shannon 的理論說：對于給定的信道，有一個最大的傳輸能力（信道容量）。一定存在這樣一種編碼，使得 ML 譯碼后仍然有錯的概率隨著編碼長度的增加而無限減小。的目標是：1尋求好的編碼設(shè)計。它的傳輸能力盡量高（表現(xiàn)為編碼率 k/n），抗差錯能力盡量強(表現(xiàn)為能夠糾正多少比特的錯誤)。2復(fù)雜度可以接受。復(fù)雜度表現(xiàn)為對量或者計算量的要求。按照Shannon的理論，如果編碼足夠長的話，隨

3、機選擇一種編碼幾乎就是一種好碼。隨機編碼的意思是這樣的：以(7,4)碼為例，用擲硬幣的方法決定出Table 1中*的內(nèi)容。把這 16×7 個*號的內(nèi)容都確定出來后，等于設(shè)計出了一種編碼。注意這樣的表格可以有216´7 種不同，Hamming碼是其中之一（Table 2）。對于隨機確定的這種編碼，可以用查表法實現(xiàn)。具體電路如Fig. 2所示。ROM中存量為24 ´ 7bit 。對于任意(n, k ) 碼，需要的量是2k ´ n 。隨器加起來都不夠儲的就是Table 1，所需著k的增加，用。量將按指數(shù)速度增加。如果k達到數(shù)百，全世界所有的對于ML譯碼，如果直

4、接按照式(1)來做的話，需要計算2k 個Hamming距離，然后進行比較運算。其計算量是指數(shù)級的。ML譯碼也可以按函數(shù)查表來做。Table 3是譯碼函數(shù)表。按這樣的方法實現(xiàn)譯碼需要的量是指數(shù)級的。因此，問題的焦點成為：尋找復(fù)雜度（計算量或量）可接受的編譯碼方法。要達到這一目的，就需要編碼結(jié)構(gòu)具備某種可操作的數(shù)學(xué)特性。1/5第 7 周Lecture Notes 8 2006/03/28Fig. 2 查表法實現(xiàn)編碼Table 1 (7,4)隨機選擇編碼Table 2 (7,4)碼的編碼函數(shù)Table 3 (7,4)Hamming 碼的譯碼函數(shù)表2/5譯碼輸入譯碼輸出譯碼輸入譯碼輸出00000000

5、000001000001000001000001000001000001000001000000000000010000111000010100000110001111001011101001111000110000011100001100011110001110000110100010110000111001111101011111001111000111110011001001101100111010010001000100101110011011000001100100110000101010010100001011000100010011101000010101101011010101

6、0010101101011010101111010100101001010111101000110111011000101101010110001101000110110011000001111000100100001010011101010110100011010101100110110001011011101110110100011001001111100100110011011001編輸入u3u2u1u0編輸出(c6c5c4c3c2c1c0 )編輸入u3u2u1u0編輸出(c6c5c4c3c2c1c0 )000000000001000100001100010001111100110011

7、00001000101011010101011000110011010101110110000100010011011001100101010101010011101110101001100110011111011100000111011110011111111111編輸入u3u2u1u0編輸出(c6c5c4c3c2c1c0 )編輸入u3u2u1u0編輸出(c6c5c4c3c2c1c0 )0000*1000*0001*1001*0010*1010*0011*1011*0100*1100*0101*1101*0110*1110*0111*1111*第 7 周Lecture Notes 8 200

8、6/03/28二 線性分組碼如果編碼函數(shù) f 是線性函數(shù)，則稱這樣的分組碼為線性分組碼。此時 f 是一種線性變換，因此可以寫成c = uG(2)其中矩陣G叫生成矩陣。G必然是一個k×n的矩陣。若記g1 , g2 ,", gk 為G的第 1、2、k行，記u = (uk-1, uk-2 ,", u1, u0 ) ，則(2)可以寫成æ g1 öç g ÷,", u , u2 ÷ = ug + u)çc = (ug +"+ u g, uk -1k -2ç÷k -1 1k -

9、2 2100 k#ç g ÷è k ø對于合理的編碼，每一種信息輸入應(yīng)該對應(yīng)有一個不同的編碼結(jié)果，即編碼結(jié)果必須有2k 種中包含全零碼字(0, 0, 0,", 0) ；C不同，因此 G 的各行必須線性無關(guān)。另外容易看到：C中的元素對加法封閉；G 的每一行都在 C 中。實際上，Cg1, g2 ,", gk 是其一組基。了一個線性向量空間，任意給定 k 個線性不相關(guān)的向量，由其的線性空間就是一種線性分組碼。對于給定的 C，其生成矩陣 G 不唯一，C 中的任意一組基都可以作為 G。 Hamming 碼的生成矩陣為æ 1ç

10、 0010000100001011111011 ö0 ÷G = ç÷1 ÷(3)ç 0ç 01 ÷èø3/50100110010011101001000100010010111001101100000110110011001001101100101110010011001111100001110110111101011000101010010111001010101001010100001010110101101010000101110010001001110100101010011101010

11、110101111010001101110110001011110101001010010101011010100110011011001001100010110111011101101000110010011111001101100111110000111000111100101110100111100011000001010000011000011100000111100011110101111100111000011010001011000011100111110001111001111111111111011111011111011111011111011111011111011111

12、11111111第 7 周Lecture Notes 8 2006/03/28線性分組碼的編運算是式(2)這樣的矩陣運算。對于二進制編碼，因為乘法只是和 0、1相乘，所以(2)中只有加法運算（邏輯異或），加法次數(shù)和G中 1 的個數(shù)有關(guān)，顯然小于nk個。k 2若給定編碼率為R，則運算次數(shù)小于，它是平方增長的，比指數(shù)級有大大的改善。R三 校驗矩陣對于上述 Hamming碼，編碼結(jié)果是c = (c6c5c4c3c2c1c0 ) = (u3u2u1u0 p2 p1 p0 ) ，可以注意到編碼結(jié)果滿足線性方程組：ìc5 + c4 + c3 + c2 = 0ïc+ c + c + c

13、= 0í6531ïc+ c + c + c = 0î 6430寫成矩陣形式為æ c6 öç c ÷ç5 ÷0 öç c4 ÷æ 0 öæ 0110101111100010 ÷ç c÷ = ç 0 ÷ç 1÷ç 3 ÷çç ÷ç 101 ÷ç cç 0 ÷÷è&

14、#248;çè ø2 ÷ç c1 ÷ç c ÷è 0 ø即HcT = 0(4)其中æ 00 ö110101111100010H = ç 10 ÷(5)ç÷ç 11 ÷èø字都滿足線性方程組(4)的約束關(guān)叫監(jiān)督矩陣或校驗矩陣。這就是說，Hamming碼的所系。由于H的秩為 3（任意 3 行或者 3 列線性無關(guān)），所以線性方程組(4)有 4 個變量是的，因而其解有 16 個。這 16 個解了碼字空間C

15、。(4)這樣的關(guān)系對任意的線性分組碼都是存在的。以至于還可以把線性分組碼定義為：如果集合C是形如(4)的某個線性方程組的解的集合，則稱C為線性分組碼。四 系統(tǒng)碼一般來說，如果編輸出的比特流中原樣包含了信息比特，叫系統(tǒng)碼。編碼輸出中的這些原始信息位也叫系統(tǒng)位。(n, k ) 碼的前k個或者后k個是信息位。性分組碼中，說一個碼是系統(tǒng)碼的意思一般是說：例如以(3)為生成矩陣的(7,4)碼是系統(tǒng)碼。但以下面這個生成矩陣產(chǎn)生的碼是非系統(tǒng)的。æ 1ç 01 ö110000100001111101010 ÷G¢ = ç÷1 ÷(

16、6)ç 0ç 01 ÷èø比如：輸入(1100)，編碼結(jié)果是(1000011)，不是(1100*)的樣子。系統(tǒng)碼的生成矩陣一定包含幺陣 Ik 的所有列。(6)所給出的G¢ 中沒有包含(0,1, 0, 0) 這個列。T4/5第 7 周Lecture Notes 8 2006/03/28五 碼的等價性設(shè)有兩個(n, k ) 編，一個輸出的碼集合是C1 ，另一個是C2 。稱這兩個編是等價的，如果下列之一滿足：(1) C1 和C2 集合相同(2) C 2 只是C1 變換了比特順序。每一個編碼結(jié)果的許用碼字都和一個信息碼組對應(yīng)，給定碼的集合并不表示給定了信息碼字和編碼結(jié)果的關(guān)系。因此談?wù)摯a的等價性時不涉及信息比特的規(guī)則。上述條件(1)表示碼字集合不變，條件(2)是說碼字集合或許有變換，但這種變化只是改變了發(fā)送次序。比如原本的發(fā)送次序是 (c6c5c4c3c2c1c0 ) 自左至右順序發(fā)送，改成了(c6c5c0c4c3c2c1 ) 這樣的順序。給定一個生成矩陣 G，如果對其進行初等行變換，則上述條件(1)始終滿足。如果對 G的列調(diào)換次序，則條件(2)滿足。因此，對 G 任意做初等行變換或者列交換后碼還是等價的。同樣的，給定一個監(jiān)督矩陣 H，對 H 任意做初等行變換或者列交換后也是等價的?？偰馨岩粋€非系統(tǒng)碼的生成矩陣等價地