【正文】 i+1]=((GF[i]1)amp。i=6。 int GF[7]={1}。 在 ? ?m2GF 域中 , 兩個以自然基表示的元素直接相乘時 ,約需要 3mm? 個模 2 加法器 , 這樣實現的電路復雜度較高 , 而且缺乏規(guī)范性 , 因此一般釆用對偶基下的乘法器。在高速應用時一般考慮用比特并行乘法器。在有限域的各種算術運算中 ,乘法研究最多。 擴展域元素代替二進制元素的一個好處就是表達的緊密性，使得非二進制編碼和譯碼過程的數學表示變得簡單。由于 07aa? ，所以在該域中有 7個非零元素，或者說總共 7個元素。多項式的階數是它的最高冪指數。具體說， m次 q(x)在擴張域 GF( mq )內必有 m個根。它的最高次冪為 m，而系數在 GF(q)上，它是不可約多項式。對于次數等于或大于 m的乘積多項式，可以取它相對于一個 m次固定多項式的余項多項式。首先，我們要求在一個集合內的任何兩個多項式之積是本集合中的另一個多項式，以滿足封閉性。 0 , 1 , 2 , , 1i i ic a b i n? ? ? ? 若為 A(x)B(x)，則只要把 B(x)系數以 GF(2m )中的加法逆元代替得到 B(x)，再作 B(x)+ A(x)運算即可，在二進制情況下“ ”與“ +”運算相同，以此相加和相減的運算結果一樣?？梢钥闯?，多項式加法器的實現比較簡單，可以直接將 2 個多項式對應的系數異或即可， 而多項式乘法器的實現比較復雜 ，這里重點介紹 用 高級語言編寫出有限域上的 乘法器 原理和方法 。 有限域元素運算 了解了有限域后，看看如何用 高級語言編寫 出有限域上的加法器和乘法器。 } 程序運行結果 圖 32。i=6。7)^3。i++) {if(GF[i]=3) GF[i+1]=GF[i]1。 for(i=0。 源程序代碼如下： include void main() { int GF[7]={1}。 0X 1X 2X 3X 圖 31由本源多項式表示的基本元素映射為域元素的電路 根據本源多項式可得 GF( 32 )域元素表如 表 32 所示。置線路初始狀態(tài)非零，例如為 100，每個時鐘實現一次右移，可以證明， 圖 31 中所示的每個域元素 (除了全 0元素 )將周 期性地出現在移位寄存器的狀態(tài)上。 本文設計的是 RS(7,3)碼編碼器，由表 31可 以查出本原多項式是： ? ? 31f x x x? ? ? ， 用 本源 多項式表示的基本元素可映射為域元素 圖 (LFSR)電路的形式。 (3)[n,k]循環(huán)碼的生成多項式 g(x)是 1nx? 的因式，即 ? ? ? ?1nx h x g x?? 。 某某 大學畢業(yè)論文（設計） 9 表 3— 1常用本原多項式 M 本原多項式 2 21 XX?? 3 31 XX?? 4 41 XX?? 5 261 XX?? 6 61 XX?? 7 371 XX?? 8 2 3 4 81 X X X X? ? ? ? 本原多項式 g(x)具有以下的性質 : (1)在 [n,k]循環(huán)碼中，生成多項式 g(x)是唯一的 (nk)次多項式，且次數是最低 的。不可約多項式是指一個多項式不能因式分解為更低冪次的多項式， B整除 A 是指 A除以 B 得到非 0 商并且余數為 0。本原多項式可定義為 :一個 m 階的不可約多項式 f(x)。域元素對乘法封閉的條件可由下面的不可約多項式表示 : ? ?2110ma ? ??即 ? ?21 01maa? ?? （ ） 根據這個多項式限制條件，任何冪次等于或超 21m? 的域元素都可降階為如下表示 的冪次小于 21m? 的元素。 GF(2n )中任何非零元素都可以由 a 的冪次表示。二進制域 GF(2)是 GF(2n )的一個子域，類似于實數是復數的一個子域一樣。 GF(q)是 GF(mq )的子集。有限域的一個重要性質是每個有限域 GF(q)至少要包含一個叫做 a的本原元素，它能生成該域中的每個元素。 元素個數有限的域稱有限域，用 GF(q)表示 q 階有限域。 3）加法和乘法間有如下分配律 : ? ?? ? ? ?? ??? ? ? （ ） ? ?? ? ? ?? ??? ? ? （ ） 則稱 Q是一個域。 2） Q 中非零元素全體對乘法構成阿貝爾群。 某某 大學畢業(yè)論文（設計） 8 3 有限域的 乘法器設計 有限域（伽羅華域）的基本概念 首先介紹一下域 的概念。由于 RS的編碼比較簡單，實現起來也很容易。 式 ()具有以下直接含義，我們可以認為譯碼器花費 nk個冗余碼元，它是可糾正碼元數的 2倍。 t可以表示為 : 1m in[ ] [ ]22d n kt ???? () 其中 :[x] 表示小于或等于 x的最大正整數。對于非二進制編碼 , 兩個碼字間的距離 (類似于漢明距離 )定義為序列間的不同碼元數目。擴展的 RS碼由2mn? ,或 21mn??組成 , 但 n不能再大。 02mkn? ? ? () 其中 ,k是已編碼分組的數據碼 元數目 ,n是已編碼分組中總的碼元數 。在 q進制 BCH 碼的碼字中 , 每個碼元的取值在 GF(q)上 ,但碼的 g(x)的根卻在 GF(q)某某 大學畢業(yè)論文（設計） 7 的擴域 ? ?mGFq 中 ,若碼元取值的域與碼的 g(x)的根所在的域相同 , 則稱這類 BCH碼為 RS碼。 RS 碼 RS碼是線性分組 BCH 碼中一個重要的子類。 RS碼是多元 BCH碼的一種特例，即取 m=1，故 RS碼的生成多項式的根和碼元符號在同一域上。那么，多元 BCH碼的碼元符號取自多元域 ? ?GFq ，其中 q為某一素數或素數之冪，而糾正 t個 錯誤的多元 BCH碼的生成多項式是以 ? ?GFq 的擴域 ? ?mGF q 上 2t個元素為根的 多項式為 ? ? ? ?? ? ? ?22tg x x x x? ? ?? ? ? ? () 多元 BCH碼的校驗矩陣： ? ? ? ?? ? ? ?12122 2 2121 1 1111nnnnnnd d dH? ? ?? ? ?? ? ???????? ? ?????????? () 式中， ? 為 ? ?mGFq 本原 元：碼長 1mnq??； d為設計距離， d=2t+1。在實際中應用的最多的是二進制 BCH碼，將二進制 BCH碼的概念進行擴展可以得到多進制 BCH碼。 BCH碼的定義 ： 給定任一有限域 ? ?GFq 及其擴域 ? ?mGF q ，其中 q是素數或素數之冪， m為某一正整數。稍后，格林斯坦（ Greenstein）和齊勒爾（ Ziegler）把它推廣到多進制。BCH碼是迄今為止研究得最為詳盡，分析得最為透徹，取得成果也最多的碼類之一。 BCH碼是目前所發(fā)現的一類很好的線性糾錯碼類，它的糾錯能力很強，特別是在短和中等碼長下，其性能接近理論值，并且構造方便，編碼簡單。多項式 ??gx稱為碼的生成多項式。這表明 ? ?,nk 循環(huán)碼可以由它的一個 r(r=nk) 次碼多項式 ??gx來確定。即： ? ? ? ? ? ? ? ?m od 1i inC x x C x x?? () 根據循環(huán)碼的循環(huán)特性，可由一個碼字的循環(huán)移位特性得到其他的非零碼字。 通常用多項式來表示循環(huán)碼?；谶@些特征，循環(huán)碼特別引人注 目，對它的研究也比較深入和系統。目前已發(fā)現的大部分線性分組碼均與循環(huán)碼有密切聯系，它們之中的大部分都可歸結于循環(huán)碼的范疇。在 1967 年，由 Viterbi 提出的 Viterbi 算法成為了卷積碼的譯碼工作中至今為止最常用的譯碼算法。從對序列譯碼的研究中，人們了解到一類具有高度 結構化的有效的樹型碼 —— 卷積碼，其中卷積碼是由 Elias在 1955 年所發(fā)現的。最初的研究是在最優(yōu)碼字未知的情況下去估計分組碼中最好的碼型的誤碼率。隨著研究地不斷深入，更為有效的編譯碼算法也不斷地得到改進，如在 1972 年由 Chase 提出的 Chase 算法。 BCH 碼的發(fā)現同時帶動了在軟件和 硬件上設計有效編譯碼算法的研究。這就是 Bose,RayChaudhuri(1960)和 Hocquenghem(1959)發(fā)現了一類具有多個糾錯能力的分組碼 BCH 碼，以及 Reed 和 Solomon(1960)發(fā)現了適用于非二元信道的分組碼 ——ReedSolomon 碼。但是，這些分組碼都沒有一般的理論基礎。盡管如此，在 1960 年以前，人們仍然無法找到比 Hamming碼更好 的一類碼型。在 1950 年， Hamming 第一次描述了一類具有單個糾錯能力的分組碼 ——Hamming 碼。所以，在上世紀的整個 50 年代，主要的工作在于尋找能夠產生低誤碼率的碼型構造方法，但結果卻不如人意；到了 60 年代，糾錯碼研究開始從兩個方向進行長期的發(fā)展。但是，信道編碼定理提出之后，工程師們意識到建立一條太好的通信信道是不值得的，而有效地使用糾錯碼的能力才是合理的。而 Shannon 提出的信道編碼定理正是為糾錯碼的發(fā)展奠定了理論基礎。這樣的設計形式一般可分為五個部分： 1）計算校驗子 2）求解關鍵方程 3）求取錯誤位置4）求取錯誤值 5）糾正錯誤。正因為基于 FPGA 的 RS碼實現方式有如此顯著的優(yōu)勢。另外這種方法還可以根據實際要求，把 RS 編譯碼器的周圍的一些相關電路也某某 大學畢業(yè)論文（設計） 3 集成在同一片 FPGA 芯片里。因為 FPGA 作為一種高密度可編程邏輯器件，可以反復編程，具有很好的靈活性，便于修改 RS編譯碼的參數。 FPGA 技術，以配置 FPGA 器件的方式實現 RS 編譯碼。這種方法靈活，用戶通過修改軟件代碼的辦法對 RS 編譯碼的參數和功能做出較大的調整。 (DSP)芯片實現 RS編譯碼功能。 這種方案用戶可以不必關心 RS 編譯碼器的內部結構，只要了解如何使用這個芯片就行了。正因為有超大規(guī)模集成電路出現， RS 碼在通信領域被廣泛應用。而且它只提供編譯后的 .vho 文件，不提供源代碼。而現在，隨著芯片價格的下調和集成的提高，以及功能強大的 EDA 軟件的幫助 ，將有能力把譯碼器做在便宜的 FPGA 上。使用硬件描述語言設計高速執(zhí)行的芯片，這種設計是富有挑戰(zhàn)性和花費時間的，需要一定的硬件工程技巧，并且需要用到的芯片資源比較多 (上萬門 )。對于低速率碼流，國內外大部分都是用單片機和 DSP來實現。 對于 RS 碼的編譯碼器，現有的專用集成電路 (ASIC)大部分是數字電視廣播 (DVB)的RS(204,188)和深空衛(wèi)星通信系統中用的 RS(255,223)碼。 RS 碼也是空間應用存貯器系統中的首選碼。很多國際標準采用了 RS 碼例如空間數據系統咨詢委員會在遙測信道編碼的建議書中將 RS（ 255， 223）系統碼作為標準使用。糾錯碼技術還廣泛應用于計算機存儲和運算系統中。在通信領域中， CRC循環(huán)校驗已成為各類線路傳輸中必不可少的一部分。 隨著信息時代的到來和微電子技術的飛速發(fā)展，糾錯碼技術已成為一門標準技術而被廣泛應用。當碼元經信道傳輸產生錯誤時，譯碼器可以檢出或糾正錯誤。所有的數字通信系統如通信、雷達、遙控遙測、數 字計算機的存儲系統和內部運算以及數字計算機之間的數據傳輸等，都可歸結成如圖 11 所示模型 信 源 信 源 編 碼 器 信 道 編 碼 器 調 制 器信 道解 調 器信 道 譯 碼 器信 源 譯 碼 器信 宿噪 聲 源 圖 11通信系統模型 我們關心的是圖中的信道編、譯碼器即糾錯編、譯碼器兩個方框。提高信息傳輸的可靠性和有效性，始終是通信工作所追求的目標。數字信號經過傳輸，會產生錯誤。利用 C語言實現了 RS(7,3)碼的編碼器和伽羅華域 GF(32 )內的乘法器的設計，并通過 Matlab仿真對編碼器結果進行驗證，程序輸出結果與驗證結果一致，表明所設 計的編碼器和乘法器算法能夠滿足設計要求。既適宜糾正隨機錯誤，更適宜糾正突發(fā)錯誤，因而被廣泛地用于各種通信系統及數據存儲中，如深空通信、移動通信、光纖通信、磁盤陣列、 DRAM、光盤數字視頻廣播 (DVB)等系統。 202120212 學期 第 14 周 — 第 15 周，論文 答辯。