1、BCH碼在通信領域研究與應用本科畢業設計論文題 目 BCH碼在通信領域的研究與應用 院 系 電子與電氣學院 班 級 電子085 班 姓 名 陳帥 指導教師 郭建中 日 期 2012年5月4日 目錄第1章 概 述21.1 當前BCH碼的現狀21.2 差錯控制技術概述2第2章 線性分組碼的基本原理42.1 線性分組碼42.2 線性分組碼的糾檢錯能力42.3 線性分組碼的生成矩陣52.4 線性分組碼的監督矩陣7第3章 循環碼原理與介紹83.1 循環碼介紹83.1.1 循環碼的多項式表示83.1.2 (n,k)循環碼的生成多項式93.1.3 循環碼的生成矩陣和一致校驗矩陣93.2 循環碼編譯碼原理11

2、3.2.1 循環碼編碼原理113.2.2 循環碼的譯碼原理12第4章 BCH碼原理與介紹154.1 BCH碼的優點154.2 BCH碼的構建154.3 BCH碼的編碼164.4 BCH碼的解碼16第5章 BCH碼在通信領域的應用175.1 模擬移動通信系統中數字信令的BCH編碼17第六章 全文總結18參考文獻19摘要本文為了研究BCH碼在通信領域的應用，先從線性分組碼的基本檢錯與糾錯原理出發，得出其一般規律：其能檢出多個錯碼，但只能糾正一個錯碼。為了能使其編碼效率提高，繼而研究了漢明碼，既是線性碼中能糾正一個錯碼且效率最高的。最后研究具有循環特性的且能糾正多個錯碼的BCH碼。 關鍵字：線性分組

3、碼；漢明碼；循環碼；BCH碼ABSTRACTIn order to study BCH code application in telecommunication field, first from the linear block codes of basic error checking and correction principle, the general rule: the detection of multiple error code, but only to correct a wrong code. In order to improve the coding effici

4、ency, then study the Hamming code is a linear code, can correct an error code and the efficiency is the highest. The final study with cyclic characteristics and can be corrected for multiple fault code BCH code。Keywords：Linear block codes；Hamming code；Cyclic code；BCH code第1章 概 述1.1 當前BCH碼的現狀 計算機通信是一

5、種以數據通信形式出現，在計算機與計算機之間或計算機與終端設備之間進行信息傳遞的方式。它是現代計算機技術與通信技術相融合的產物，在軍隊指揮自動化系統、武器控制系統、信息處理系統、決策分析系統、情報檢索系統以及辦公自動化系統等領域得到了廣泛應用。隨著計算機、衛星通信及高速數據網的飛速發展，數據的交換、處理和存儲技術得到了廣泛應用，人們對數據傳輸和存儲系統的可靠性提出了越來越高的要求。因此，如何控制差錯、提高數據傳輸和存儲的可靠性，成為現代數字通信系統設計工作者所面臨的重要課題，線性分組碼是差錯控制編碼的重要一種，線性分組碼的編碼與譯碼電路比較簡單，糾錯能力也較強，是實際應用中比較流行的差錯控制編碼

6、方法之一。線性分組碼中的BCH碼，由于能糾正多個錯碼，接譯碼比較容易，應用相對比較廣泛。1.2 差錯控制技術概述數字信號在傳輸過程中，由于受到干擾的影響，碼元波形將變壞，接收端收到后可能發生錯誤判決，由乘性干擾引起的碼間串擾，一般采用均衡的辦法糾正。加性干擾的影響一般從合理選擇調制制度解調方法以及發送功率等方面考慮，使加性干擾不足以影響達到誤碼率要求。在仍不能滿足要求時，為減少錯誤、提高通信質量還采用檢錯、糾錯技術，即差錯控制措施。差錯控制的主要方法是將數據以某種形式編碼。差錯控制的核心為：抗干擾編碼，簡稱差錯控制編碼。差錯控制編碼分為檢錯碼、糾錯碼兩大類。它在碼元間建立了某種數學約束關系，并

7、且對特定的信道總存在某種糾錯編碼信號以實現最小的能量或最小的帶寬或最小的時間代價獲得最小的數據傳輸差錯。對于不同信道，采用不同類型的差錯控制技術。差錯控制技術主要有：檢錯重發：在發送碼元序列中加入差錯控制碼元，接收端利用這些碼元檢測到有錯碼時，利用反向信道通知發送端，要求發送端重發，知道正確接收為止。前向糾錯：前向糾錯是利用接收端在發送碼元序列中加入的差錯控制碼元，不但能夠發現錯碼，還能夠將錯碼恢復其正確值。反饋校驗：不需要在發送序列中加入差錯控制碼元，接收端接收到的碼元原封不動的轉發會發送端。在發送端將他和原發送碼元逐一比較，若發現有不同，就認為接收端接受的序列有錯碼，發送端立即從發。檢錯刪

8、除：在接收端發現錯碼后，立即將其刪除，不要求重發。這種方法只適合在少數特定系統中，在那里發送碼元有大量的多余度，刪除部分接收碼元不影響應用。1.3 本文主要工作本文先研究線性分組碼的基本檢錯與糾錯原理，還有其監督矩陣和生成矩陣，后研究循環碼的編碼與譯碼過程，他們都能檢出多個錯，但只能糾正一個錯。最后研究具有循環特性的且能糾正多個錯碼的BCH碼，及其編碼與譯碼過程和BCH碼在通信領域的應用。第2章 線性分組碼的基本原理2.1 線性分組碼線性分組碼是一類奇偶校驗碼，它可以由（n，k）形式表示，編碼器將一個k比特信息分組（信息矢量）轉變為一個更長的由給定元素符號集組成的n比特編碼分組，當這個符號集包

9、含兩個元素（0和1），與二進制相對，稱為二進制編碼。 分組碼是對每段k 位長的信息組，以一定規則增加r = n - k個檢驗元，組成長為n的序列：，稱這個序列為碼字。在二進制情況下，信息組總共有個( q 進制為個) ，因此通過編碼器后，相應的碼字也有個，稱這個碼字集合為( n , k) 分組碼。n長序列的可能排列總共有種。稱被選取的個 n重為許用碼組，其余個為禁用碼組，稱R = k / n為碼率。那么對于（7，3）碼即為用7位長的序列表示3位信息碼，7位長序列的可能排列總共有個。許用碼組有個，其余個禁用碼組，碼率為R=3/7=42.86%。對于長度為n的二進制分組碼，可以表示成（n，k），通常

10、用于前向糾錯。在分組碼中，監督位加到信息位之后，形成新碼，在編碼中，k個信息位，被編為n位長度，（n-k）個監督碼的作用是實現檢錯和糾錯。2.2 線性分組碼的糾檢錯能力在分組碼中，我們把碼組C中非零分量（對二進制來說，即1分量）的數目定義為碼組C的漢明重量。兩個碼組對應位上數字不同的個數稱為碼組的距離，簡稱碼距，也稱漢明距離。對（n，k）線性碼來說，個碼字中所有可能碼字之間的漢明距離中最小的距離稱為該碼的最小漢明距離，用dmin表示。而對于線性分組碼來說，線性分組碼的最小距離等于它的最小重量。一個線性分組碼碼的最小距離dmin和碼的抗干擾能力有如下關系：若要檢測m個錯碼，要求最小距離dminm

11、+1若要糾正t個錯碼，要求最小距離dmin2t+1若要糾正t個錯碼同時檢測m個（m>t）錯碼，要求碼的最小距離dminm+t+1由上可知，一個（n,k）線性分組碼有兩個重要參數。一個是它的最小距離dmin，它反映了碼的抗干擾能力，dmin越大，碼的糾錯或檢錯能力越強；另一個是碼率R=k/n，它表示信息位在碼組中所占的比重，R越大，說明信息位占的比重越高，故碼的有效性越高。顯然，我們希望構造一個R高且dmin大的碼，但實際上這兩者是矛盾的。編碼的主要任務就是如何找到一種方法，在滿足一定R的條件下，使dmin盡可能地大。2.3 線性分組碼的生成矩陣選用碼組的信息組為，碼字為。當已知信息組時，

12、按以下規則得到四個校驗元，即 (1)這組方程稱為校驗方程。 （7,3）碼有許用碼組有個，其余個禁用碼組，碼率為R=3/7=42.86%。發送方發送的是許用碼字，若接收方收到的是禁用碼字，則說明傳輸中發生了錯誤。為了深化對線性分組碼的理論分析，可將其與線性空間聯系起來。由于每個碼字都是一個二進制的n重，即二進制n維線性空間中的一個矢量，因此碼字又稱為碼矢。線性分組碼的一個重要參數是碼率R=k/n,它說明在一個碼字中信息位所占的比重，R越大，說明信息位所占比重越大，碼的傳輸信息的有效性越高。由于(n,k)線性分組，線性分組碼的個碼字組成了n維線性空間的一個k維子空間。因此這個碼字完全可由k個線性無

13、關的矢量所組成。設此k個矢量為，有生成矩陣形式為：(n,k)碼字中的任一碼字均可由這組基底的線性組合生成，即： Ci=CnCn-1Cn-2Cn-k·G (3)上式中CnCn-1Cn-2Cn-k是k個信息元組成的信息組。表3-1 按上式編出的（7，3）碼信息組碼字00000000000010010011010010011001101101011001001100101101111111011010101111111001對于表3-1給出的（7,3）線性分組碼，可將其寫成矩陣形式：（4）其中，（7,3）線性分組碼的生成矩陣為（5）2.4 線性分組碼的監督矩陣線性分組碼的四個校驗元由式（1

14、）所示的線性方程組決定的，把（1）式移相有：（6）上式的矩陣形式為：（7）這里的四行七列矩陣稱為（7,3）線性分組碼的一致監督矩陣（一致校驗矩陣），用H表示，即：（8）第3章 循環碼原理與介紹3.1 循環碼介紹循環碼是線性分組碼的一種，所以它具有線性分組碼的一般特性，此外還具有循環性。循環碼的編碼和解碼設備都不太復雜，且檢(糾)錯能力強。它不但可以檢測隨機的錯誤，還可以檢錯突發的錯誤。（n,k）循環碼可以檢測長為n-k或更短的任何突發錯誤，包括首尾相接突發錯誤。循環碼是一種無權碼，循環碼編排的特點是相鄰兩個數碼之間符合卡諾圖中的鄰接條件，即相鄰兩個數碼之間只有一位碼元不同，碼元就是組成數碼的單

15、元。符合這個特點的有多種方案，但循環碼只能是表中的那種。循環碼的優點是沒有瞬時錯誤，因為在數碼變換過程中，在速度上會有快有慢，中間經過其它一些數碼形式，稱它們為瞬時錯誤。這在某些數字系統中是不允許的，為此希望相鄰兩個數碼之間僅有一位碼元不同，即滿足鄰接條件，這樣就不會產生瞬時錯誤。循環碼就是這樣一種編碼，它可以在卡諾圖中依次循環得到。循環碼又稱格雷碼（ Grey Code ）。循環碼最大的特點就是碼字的循環特性，所謂循環特性是指：循環碼中任一許用碼組經過循環移位后，所得到的碼組仍然是許用碼組。若（   ）為一循環碼組，則（  ）、（ ）、還是許用碼組。也

16、就是說，不論是左移還是右移，也不論移多少位，仍然是許用的循環碼組。3.1.1 循環碼的多項式表示設碼長為n的循環碼表示為 （，,， ，） （1）其中為二進制數，通常把碼組中各碼元當做二進制的系數，即把上式中長為n的各個分量看做多項式： T(x) =+ （2）的各項系數，則碼字與碼多項式一一對應，這種多項式中，x僅表示碼元位置的標記,因此我們并不關心x的取值，這種多項式稱為碼多項式。3.1.2 (n,k)循環碼的生成多項式(n,k)循環碼的生成多項式寫為g(x),它是(n,k)循環碼碼集中唯一的，冪次為n-k的碼多項式，則g(x)是一個冪次為n的碼多項式。按模（+1）運算，此時： = Q(x)+

17、 （3） 即 g(x)R（x），且因 g(x)也是n階冪，故Q(x)=1.由于它是循環碼，故 g(x)按模（+1)運算后的“余式”也是循環碼的一個碼字，它必能被g(x)整除，即：=F(x) （4）由以上兩式可以得到： g(x)= Q(x)（+1）+R(x) =（+1）+f(x)g(x) （5）和+1=+f(x)g(x)=h(x)g(x) （6）從上式中可以看出，生成多項式g(x)應該是+1的一個因式，即循環碼多項式應該是+1的一個n-k次因式。3.1.3 循環碼的生成矩陣和一致校驗矩陣對所有的i=0,1,2,k-1，用生成多項式g(x)除，有：=(x)g(x)+(x) （7） 式中（x）是余式

18、，表示為：（x）=+ （8）因此，+（x）是g(x)的倍式，即+（x）是碼多項式，由此得到系統形式的生成矩陣為：G= （9）它是一個kn階的矩陣。同樣，由G=0可以得到系統形式的一致校驗矩陣為： H= （10）如已知（7，4）循環碼的生成多項式和校驗多項式分別為：g(x) = x3 + x +1，h(x) = x4 + x2 + x +1。寫得其生成矩陣和校驗矩陣分別為：G= （11） H= （12） 3.2 循環碼編譯碼原理3.2.1 循環碼編碼原理有信息碼構成信息多項式m(x)= +其中高冪次為k-1;用乘以信息多項式m(x)，得到的 m(x)最高冪次為n-1,該過程相當于把信息嗎（，）移

19、位到了碼字德前k個信息位，其后是r個全為零的監督位;用g(x)除 m(x)得到余式r(x),其次數必小于g(x)的次數，即小于（n-k）,將此r(x)加于信息位后做監督位，即將r(x)于 m(x)相加，得到的多項式必為一碼多項式。初始化根據上面的討論，可得到在（7，4）循環碼編碼的程序框圖如圖1 所下圖示：確定余式r(x): 確定c(x): 儲存c(x)圖2 編碼程序框圖3.2.2 循環碼的譯碼原理 糾錯碼的譯碼是該編碼能否得到實際應用的關鍵所在。譯碼器往往比編碼較難實現，對于糾錯能力強的糾錯碼更復雜。根據不同的糾錯或檢錯目的，循環碼譯碼器可分為用于糾錯目的和用于檢錯目的的循環碼譯碼器。 通常

20、，將接收到的循環碼組進行除法運算，如果除盡，則說明正確傳輸；如果未除盡，則在寄存器中的內容就是錯誤圖樣，根據錯誤圖樣可以確定一種邏輯，來確定差錯的位置，從而達到糾錯的目的。用于糾錯目的的循環碼的譯碼算法比較復雜，感興趣的話可以參考一些參考書。而用于檢錯目的循環碼，一般使用ARQ通信方式。檢測過程也是將接受到的碼組進行除法運算，如果除盡，則說明傳輸無誤；如果未除盡，則表明傳輸出現差錯，要求發送端重發。用于這種目的的循環碼經常被成為循環冗余校驗碼，即CRC校驗碼。CRC校驗碼由于編碼電路、檢錯電路簡單且易于實現，因此得到廣泛的應用。在通過MODEM傳輸文件的協議如ZMODEM、XMODEM協議中均

21、用到了CRC校驗技術。在磁盤、光盤介質存儲技術中也使用該方法。 在SystemView中沒有提供專用的CRC循環冗余校驗碼編碼器，讀者可根據有關參考書設計一個相應的仿真電路。如果不想親自動手設計，可以在CDMA庫（IS95）中找到一個現成的專用的CRC編碼器和譯碼器。該圖符（FrameQ）是的接入信道的數據幀品質指示編碼器，其中使用了多種不同比特率的數據模型，通過CRC校驗來判斷接入信道的質量好壞。其中規定每一幀的長度為20ms的數據。一個典型IS-95-A標準規定的9600信道的CRC測試碼的長度為192比特，其中信息位172位、校驗位12比特、尾部全零8比特。感興趣的讀者可以加入一個速率為

22、860bps（192bit/0.2ms860）的PN數據，然后觀察經過CRC編碼后的波形。并可用對應的譯碼器譯碼觀察輸出波形是否與輸入的PN碼一致。當碼字c通過噪聲信道傳送時，會受到干擾而產生錯誤。如果信道產生的錯誤圖樣是e，譯碼器收到的n重接受矢量是y,則表示為： y=c+e （13）上式也可以寫成多項式形式：y(x)=c(x)+e(x) （14）譯碼器的任務就是從y(x)中得到，然后求的估值碼字= y(x)+ （15） 并從中得到信息組。 循環碼譯碼可按以下三個步驟進行： （1）有接收到的y(x)計算伴隨式s(x);（2）根據伴隨式s(x)找出對應的估值錯誤圖樣；（3）計算= y(x)+

23、，得到估計碼字。若=c(x),則譯碼正確，否則，若c(x)，則譯碼錯誤。由于g(x) 的次數為n - k 次，g(x) 除E(x) 后得余式（即伴隨式）的最高次數為n-k-1次，故S(x) 共有2n-k 個可能的表達式，每一個表達式對應一個錯誤格式。可以知道(7,4）循環碼的S(x) 共有2(7-4) = 8個可能的表達式，可根據錯誤圖樣表來糾正(7,4）循環碼中的一位錯誤，其伴隨式如表1所示。BCH（7，4）循環碼錯誤圖樣表：錯誤圖樣錯誤圖樣碼字伴隨式S(x)伴隨式E6(x)=x61000000x2100E5(x)=x50100000x2+x110E4(x)=x40010000x2+x+11

24、11E3(x)=x30001000x+1011E2(x)=x20000100x2+1101E1(x)=x10000010x010E0(x)=x000000011001E(x)=000000000000表1 BCH（7，4）循環碼錯誤圖樣表上式指出了系統循環碼的譯碼方法：將收到的碼字R(x) 用g(x) 去除，如果除盡則無錯；否則有錯。如果有錯，可由余式S(x) 一一找出對應圖樣，然后將錯誤圖樣E(x) 與R(x) 模2 和，即為所求碼字C(x) ，從而實現糾錯目的。第4章 BCH碼原理與介紹4.1 BCH碼的優點提高信息傳輸的可靠性和有效性，始終是通信工作所追求的目標。糾錯碼是提高信息傳輸可靠

25、性的一種重要手段。1948年香農（Shannon）在他的開創性論文“通信的數學理論”中，首次闡明了在有擾信道中實現可靠通信的方法，提出了著名的有擾信道編碼定理，奠定了糾錯碼的基石。根據香農的思想，研究者先后給出了一系列設計好碼和有效譯碼的方法。以后，糾錯碼受到了越來越多的通信和數學工作者，特別是代數學家的重視，使糾錯碼無論在理論上還是在實際中都得到了飛速發展。BCH、卷積碼，Turbo碼、LDPC碼等現代數據傳輸通信中,常常因傳輸差錯造成誤碼錯碼,尤其在無線通信中,空中的突發或隨機干擾噪聲會造成編碼差錯。為了提高傳輸的正確率,往往采用一些校驗方法,以檢驗糾正傳輸差錯。通信中校驗的方法很多, 如

26、BCH、卷積碼，Turbo碼、LDPC碼等，其中的BCH編碼有其獨特的優點:它的糾錯能力很強，特別在短和中等碼長下，其性能很接近于理論值，構造方便，編碼簡單，不僅可以檢糾突發性錯誤,還能檢糾隨機差錯。因此, 在通信系統中得到廣泛應用，如在我國地面數字電視廣播標準中就選用了BCH（762 .752）碼。4.2 BCH碼的構建BCH 碼使用有限域上的域論與多項式。為了檢測錯誤可以構建一個檢測多項式，這樣接收端就可以檢測是否有錯誤發生。要構建一個能夠檢測、校正兩個錯誤的 BCH 碼，我們要使用有限域 GF(16) 或者 Z2x<x4 + x + 1>。如果是m1(x) = x4 + x

27、+ 1的一個根，那么m1就是的極小多項式，這是因為m1(x) = (x -)(x -2)(x -4)(x -8)=x4 + x + 1。 如果要構建一個能夠糾正一個錯誤的BCH碼，那么就使用 m1(x)，這個代碼就是所有滿足：C(x)0（mod m1(x)）且根為,2,4,8 的多項式 C(x)。4.3 BCH碼的編碼構建碼字為(c14, c13, ., c8)，這樣多項式為c14+c13+.+c8，我們將它稱為CI。然后就要找出CR滿足CR=CI (mod m1,3(x)=c7+c6+.+c0這樣就得到待發的碼字C(x) = CI+CR (mod m1,3(x) = 0例如，如果我們要對 (

28、1,1,0,0,1,1,0) 進行編碼CI=x14+x13+x10+x9 然后用m1,3(x) 除以（這里的除法是多項式除法）CI ，得到結果為 CR(x)，在Z2域中，我們可以算出 CR為x3+1 這樣，待發的碼字為(1,1,0,0,1,1,0, 0,0,0,0,1,0,0,1) 4.4 BCH碼的解碼BCH 的解碼過程可以分為以下四步：1、計算接收到的向量R的 2t 伴隨矩陣； 2、計算錯誤定位多項式； 3、解多項式，得到錯誤位置； 4、如果不是二進制 BCH 碼，就計算錯誤位置的誤差值。 假設我們收到一個碼字向量r，即多項式 R(x)。如果沒有錯誤，那么 R()=R(3)=0如果有一個錯誤，例如 r=c+ei，其中 ei 表示 R14 的第i個基向量，于是：S1=R () =C () +