【正文】 循環(huán)碼的定義及性質 ................................................................................................... 2 、循環(huán)碼的性質 ................................................................................................... 2 、循環(huán)碼的定義 ........................................ 2 、循環(huán) 編碼原理 ................................................................................................... 2 、循環(huán)碼的編碼方法 ..................................... 2 、舉例：（ 7,4）循環(huán)碼 ................................... 3 循環(huán)碼的編碼 ................................................................................................................. 4 、循環(huán)碼的生成矩陣 ..................................... 4 、循環(huán)碼的生成多項式 ................................... 4 、生成多項式和碼多項式的關系 ........................... 4 、循環(huán)碼的監(jiān)督多項式和監(jiān)督矩陣 ......................... 5 循環(huán)碼的譯碼 ................................................................................................................. 7 本章小結 ........................................................................................................................... 7 2 循 環(huán)碼的編譯碼器的 FPGA實現(xiàn) ..................................................................................... 7 FPGA 及其設計原理簡介 .............................................................................................. 8 、 FPGA 介紹 ............................................ 8 、 FPGA 設計流 程 ........................................ 8 循環(huán)碼編碼器 ............................................................................................................... 9 XXX 3 循環(huán)碼譯碼器 ............................................................................................................... 12 循環(huán)編 /譯碼器的設計 ................................................................................................ 16 參考文獻 ........................................................................................................................................ 23 附 錄 ............................................................................................................................................. 25 英文原文 ： ............................................ 25 英文翻譯 ： ............................................ 28 附錄 A系統(tǒng)源程序 ............................................................................................................. 31 附錄 B：系統(tǒng)框圖 .............................................................................................................. 36 XXX 1 前 言 信息在傳遞過程中，可能因某種原因使傳輸?shù)臄?shù)據(jù)發(fā)生錯誤 . 為減 少和避免這類錯誤的發(fā)生，除提高硬件的可靠性外，在數(shù)據(jù)的編碼上也應提供檢錯和糾錯的支持 . 具體做法是：在要傳送的數(shù)據(jù)代碼中加入若干個校驗位，使之在傳送過程中若發(fā)生錯誤則會生成非法代碼而被發(fā)現(xiàn)，甚至能根據(jù)非法代碼確定錯誤的位置而給予糾正，這種具有檢錯或糾錯能力的編碼即校驗碼，其中只能發(fā)現(xiàn)錯誤而不能糾正錯誤的編碼為檢錯碼，既能發(fā)現(xiàn)錯誤又能糾正錯誤的編碼為糾錯碼 . 常見的校驗碼有奇偶校驗碼、海明校驗碼和循環(huán)冗余校驗 CRC碼，它們都是將被校驗的數(shù)據(jù)代碼按 k 位一組分組，每組添加 r 個校驗位，形成 n 位一組的代碼，故又 稱為（ n,k）分組校驗碼 . 傳送時校驗位和數(shù)據(jù)位被一起發(fā)出，若傳送過程沒發(fā)生錯誤，則接收方剔除校驗位保留數(shù)據(jù)位，否則經校驗給予糾正（對糾錯碼）或要求重發(fā)（對檢錯碼） . 其中 CRC 碼既可檢錯又可糾錯（與生成多項式的選取有關），是以數(shù)據(jù)塊為對象進行校驗的一種高效、可靠的檢錯和糾錯方法，由于它的編解碼簡單、糾錯能力強且誤判概率很低 , 因而在工業(yè)測控及通信系統(tǒng)中得到了廣泛的應用。對通信的可靠性檢查就需要“校驗”，校驗是從數(shù)據(jù)本身進行檢查，它依靠某種數(shù)學上約定的形式進行檢查，校驗的結果是可靠或不可靠，如果可靠就對數(shù)據(jù)進行處理，如果不可靠，就丟棄重發(fā) 或者進行修復。 、循環(huán) 編碼原理 在編碼時，首先需要根據(jù)循環(huán)碼的參數(shù)確定生成多項式 g(x)，也就是從 xn+1的因子中選出一個（ nk）次多項式作為 g(x)；然后，利用循環(huán)碼的編碼特性，即所有循環(huán)碼多項式 A(x)都可以被 g(x)整除，來定義生成多項式 g(x)。 c．找出與碼多項式相對應的循環(huán)碼字。 b．用 g(x)除 xnk+i(i=0,1,…,k 1),得： Xnk+i=qi(x)g(x)+,ri(x) 于是 xnk+i+ri(x)是 g(x)的倍式，且次數(shù)小于等于 n 一 1，所以為碼多項式。 b．用 gG)除 xn－ km(x)得到余式 r(x)。移位過程和相應的多項式運算如表 。 、生成多項式和碼多項式的關系 定理 1：在（ n ， k）循環(huán)碼中，生成多項式 g（ x）是唯一的（ nk）次碼多項式，且次數(shù)是 最低的。所以稱這種循環(huán)碼為推廣循環(huán)碼。 定理 4: （ n ， k）循環(huán)碼的生成多項式 g（ x）是（ 1nx? ）的因子，即 1 ( ) ( )nx h x g x? ? ? 定理 5：若 g（ x）是一個（ nk）次多項式，且為（ 1nx? ）的因式，則 g（ x）生成一個（ n， k）循環(huán)碼。 其中（ n， k）循環(huán)碼也可由其監(jiān)督多項式完全確定 。 在接收端達到檢錯目的的譯碼原理十分簡單。和一般的線性分組碼一樣，當 21nk n? ??時，具有糾正一位錯碼的能力。本章只對循環(huán)碼的理論編碼進行了研究，接下來一章將介紹如何利用 FPGA的 verilog語言編 碼實現(xiàn)循環(huán)碼的編譯。目前， FPGA廣泛應用于通信、移動設備、航空航天、自動控制等領域，并有向計算密集型應用發(fā)展的趨勢。 （ 2） 綜合 綜合就是將電路的高級語言（如行為描述）轉換為低級的，可 生成與 FPGA 的基本結構相映射的網(wǎng)表文件或程序。 循環(huán)碼編碼器 循環(huán)碼通常采用碼多項式描述，例如一個（ 7,4）循環(huán)碼的碼字為（ 1001000），就可以用 T(x)=1+3x 表示。 仍然 以（ 7,4）循環(huán)碼為例，若輸入信息碼元為 3( ) 1u x x?? ，則： 7 4 3 3 6 2 3( ) ( 1 ) m o d ( 1 )nkx u x x x x x x x x x??? ? ? ? ? ? ? ? ? 因此，碼多項式為 ： 2 7 4 3 2 3 6( ) ( ) ( ) ( 1 )nkc x r x x u x x x x x x x x x??? ? ? ? ? ? ? ? ? ? 其中 2()r x x x?? 為信息碼元置為高位后整除生成多項式后的余式，它正好對應于校驗序列。 經過 4 次移位后，信息組全部輸出。 根據(jù)以上思路，設計編碼器源代碼如下。//c為編碼輸出碼字， c[0]~c[3]為信息碼元， c[4]~c[6]為監(jiān)督碼元 input [3:0] u。 reg[6:0] c。 //初始化 for(i=0。 d2=d1。i7。 d0=0。 // Outputs wire [6:0] c。 end always 10 clk=!clk。若碼元無錯，則 y(x)可被 g(x)整除，余項為零。 表 g(x)生成（ 7， 4）循環(huán) 碼糾錯過程 錯誤圖樣 e(x) 伴隨子 s(x) 伴隨矢量 012sss 移位次數(shù) I 移位后伴隨子矢量012sss 6e 21x? 101 0 101 5e 21 xx?? 111 1 101 4e 2xx? 011 2 101 3e 21x? 110 3 101 2e 2x 001 4 101 1e x 010 5 101 0e 1 100 6 101 由表 ，若錯誤圖樣 6()ex x? ，即 6x 位置上有錯，則接收矢量 y(x)全部進入伴隨式寄存器后，伴隨式為（ 101）。 根據(jù)上述分析，利用接收碼字中單個錯誤出現(xiàn)在首位的錯誤圖樣及相應的伴隨式，設計譯碼器的原理框圖如圖 。若無錯，則錯誤檢測電路無輸出；若有錯，則錯誤檢測電路輸出為 “ 1”。 output[6:0] c。 reg temp。 //錯誤檢測輸出信號 always (posedge clk) begin s0=0。 buffer=y。(~ s1)amp。 s1=s0^temp。i=i1) //輸出糾錯譯碼后的碼字 begin e=s0amp。 s2=s1。 if(e==1) //若出錯，對緩存進行清零 begin s0=0。 end endmodule module test。 // Instantiate the Unit Under Test (UUT) decoder uut ( .c(c), .y(y), .clk(clk) )。b0110100。b0011010。b0001101。b0100011。b0010111。 endmodule /譯碼器的設計 一 系統(tǒng)構成 系統(tǒng)構成框圖如圖 ： 圖 故該系統(tǒng)的信號流程為： （ 1）由信號發(fā)生器產生輸入串行測試數(shù)據(jù)； （ 2）再將該數(shù)據(jù)經串 /并變換為并行的數(shù)據(jù)字； （ 3）然后將此數(shù)據(jù)字編碼產生對應的并行碼字； XXX 17 （ 4）將并行碼字經并 /串變換產生發(fā)送碼流； （ 5）將接收碼流經串 /并變換產生接收碼字； （ 6）將接收碼字譯碼產生對應的并行數(shù)據(jù)字； （ 7）將并行數(shù)據(jù)字經并 /串變換產生接收數(shù)據(jù)流。 （ 2）信號發(fā)生器模塊 該模塊產生一串行的偽隨機碼流 c， 作為測試輸入數(shù)據(jù)，其時鐘 clk7為輸入數(shù)據(jù)時鐘。 另一個為接收碼流的串 /并變換： 如下圖 /并變換器 2的時序仿真，圖 /并變換器 2的模塊圖