【正文】 的算法有深入了解。這種方法靈活，用戶通過(guò)修改軟件代碼的辦法對(duì) RS 編譯碼的參數(shù)和功能做出較大的調(diào)整。這種方法的缺點(diǎn)是 DSP芯片 的價(jià)格比較昂貴、編譯碼的速度受限制。 FPGA 技術(shù)，以配置 FPGA 器件的方式實(shí)現(xiàn) RS 編譯碼。 采用這種方案，即通過(guò)配置 FPGA 來(lái)完成 RS編譯碼的方法，是目前看來(lái)最好的一種方法。因?yàn)?FPGA 作為一種高密度可編程邏輯器件，可以反復(fù)編程，具有很好的靈活性，便于修改 RS編譯碼的參數(shù)。用 FPGA 實(shí)現(xiàn)的 RS 編譯碼器速度很快，運(yùn)算速度遠(yuǎn)高于 DSP 編程的方法。另外這種方法還可以根據(jù)實(shí)際要求，把 RS 編譯碼器的周圍的一些相關(guān)電路也某某 大學(xué)畢業(yè)論文（設(shè)計(jì)） 3 集成在同一片 FPGA 芯片里。這樣一來(lái)既充分利用了器件資源，又提高了產(chǎn)品集成度和可靠性，減少 了功耗，降低了成本，而且使電路性能得到明顯提高。正因?yàn)榛?FPGA 的 RS碼實(shí)現(xiàn)方式有如此顯著的優(yōu)勢(shì)。 隨著研究與應(yīng)用的不斷發(fā)展， RS 碼硬件譯碼器的實(shí)現(xiàn)已呈現(xiàn)出模塊化的設(shè)計(jì)形式。這樣的設(shè)計(jì)形式一般可分為五個(gè)部分： 1）計(jì)算校驗(yàn)子 2）求解關(guān)鍵方程 3）求取錯(cuò)誤位置4）求取錯(cuò)誤值 5）糾正錯(cuò)誤。上述五個(gè)部分的具體關(guān)系如圖 12： 計(jì) 算 校 驗(yàn) 子求 解 關(guān) 鍵 方程求 取 錯(cuò) 誤 位置求 取 錯(cuò) 誤 值 糾 正 錯(cuò) 誤圖 12 RS譯碼原理 某某 大學(xué)畢業(yè)論文（設(shè)計(jì)） 4 2 糾錯(cuò)碼的基本理論 糾錯(cuò)碼 簡(jiǎn)介 糾錯(cuò)碼的產(chǎn)生源于 1948 年 Claude Shannon 的著名論文“ A mathematical theory of munication”的發(fā)表。而 Shannon 提出的信道編碼定理正是為糾錯(cuò)碼的發(fā)展奠定了理論基礎(chǔ)。這是因?yàn)樵?Shannon 提出信道編碼定理之前，工程師們僅僅知道只有無(wú)限能量或無(wú)限帶寬才能保證噪聲信道中的消息能夠可靠傳輸 。但是，信道編碼定理提出之后，工程師們意識(shí)到建立一條太好的通信信道是不值得的，而有效地使用糾錯(cuò)碼的能力才是合理的?？上У氖?， Shannon 只是證明了合適碼字的存在，而并沒有闡述如何去獲得合 適的碼字。所以，在上世紀(jì)的整個(gè) 50 年代，主要的工作在于尋找能夠產(chǎn)生低誤碼率的碼型構(gòu)造方法，但結(jié)果卻不如人意；到了 60 年代，糾錯(cuò)碼研究開始從兩個(gè)方向進(jìn)行長(zhǎng)期的發(fā)展。 糾錯(cuò)碼研究的第一個(gè)方向是在碼字的構(gòu)造中引入代數(shù)結(jié)構(gòu)，其中的研究成果集中在分組碼的研究。在 1950 年， Hamming 第一次描述了一類具有單個(gè)糾錯(cuò)能力的分組碼 ——Hamming 碼。由于 Hamming 碼存在一定的局限性，所以人們?cè)谕蟮?10 年里堅(jiān)持不斷地向著 Shannon 指出的方向努力。盡管如此，在 1960 年以前，人們?nèi)匀粺o(wú)法找到比 Hamming碼更好 的一類碼型。同時(shí)，在這段歲月里，許多長(zhǎng)度較短的分組碼仍然不斷地被人們發(fā)現(xiàn)了。但是，這些分組碼都沒有一般的理論基礎(chǔ)。而到了 1960 年，重 大的突破終于發(fā)生了。這就是 Bose,RayChaudhuri(1960)和 Hocquenghem(1959)發(fā)現(xiàn)了一類具有多個(gè)糾錯(cuò)能力的分組碼 BCH 碼，以及 Reed 和 Solomon(1960)發(fā)現(xiàn)了適用于非二元信道的分組碼 ——ReedSolomon 碼。至此以后，由于這個(gè)領(lǐng)域的理論得到了很大的發(fā)展，所以在往后的歲月中，新的碼型也不斷地被發(fā)現(xiàn)。 BCH 碼的發(fā)現(xiàn)同時(shí)帶動(dòng)了在軟件和 硬件上設(shè)計(jì)有效編譯碼算法的研究。第一個(gè)好的譯碼算法是由 Peterson 提出的，接著，就是由 Berlekamp 和Messay 提出的更加有效的迭代算法。隨著研究地不斷深入，更為有效的編譯碼算法也不斷地得到改進(jìn)，如在 1972 年由 Chase 提出的 Chase 算法。 糾錯(cuò)碼研究的第二個(gè)方向是與概率統(tǒng)計(jì)相結(jié)合的研究方向。最初的研究是在最優(yōu)碼字未知的情況下去估計(jì)分組碼中最好的碼型的誤碼率。以這類研究為基礎(chǔ)，人們開始嘗試從概率的角度出發(fā)來(lái)了解編譯碼的原理，從而提出了序列譯碼的概念。從對(duì)序列譯碼的研究中，人們了解到一類具有高度 結(jié)構(gòu)化的有效的樹型碼 —— 卷積碼，其中卷積碼是由 Elias在 1955 年所發(fā)現(xiàn)的。在上世紀(jì)的五十年代末，卷積碼已可以通過(guò)序列譯碼算法得到成功的譯碼。在 1967 年，由 Viterbi 提出的 Viterbi 算法成為了卷積碼的譯碼工作中至今為止最常用的譯碼算法。 某某 大學(xué)畢業(yè)論文（設(shè)計(jì)） 5 循環(huán)碼 循環(huán)碼是一類最重要的線性碼，它具有嚴(yán)格的代數(shù)結(jié)構(gòu)，其性能易于分析。目前已發(fā)現(xiàn)的大部分線性分組碼均與循環(huán)碼有密切聯(lián)系，它們之中的大部分都可歸結(jié)于循環(huán)碼的范疇。并且循環(huán)碼具有循環(huán)特性，其編譯碼電路，特別是編碼電路易于實(shí)現(xiàn)?；谶@些特征，循環(huán)碼特別引人注 目，對(duì)它的研究也比較深入和系統(tǒng)。 循環(huán)碼的定義 ： 設(shè)有一個(gè) n 重的 k 維子空間 ,VVnk n? ,若對(duì)其中任意一個(gè)? ?, , ,1 2 0 ,V a a a Vn n n k???? ，恒有 ? ?, , , ,1 2 3 0 1 ,V a a a a Vn n n n k??? ? ?，則稱 ,Vnk 為循環(huán)子空間或循環(huán)碼。 通常用多項(xiàng)式來(lái)表示循環(huán)碼。將碼矢表示成多項(xiàng)式的形式，即碼元多項(xiàng)式 ??Cx為： ? ? 121 2 0nnnnC x C x C x C????? ? ? ? （ ） 其 i次循環(huán)移位所得的碼矢也用多項(xiàng)式表示為： ? ? ? ? 121 2 0i n n in i n i n iC x C x C x C x C??? ? ? ? ?? ? ? ? ? （ ） 由式（ ）乘以 ix 再除以 1nx? 得： ? ?? ? ? ?112 1012111212 1i nix C x C x C x Cii n i n iC x C x Cn n n innxxiCxiiC x C x Cn n n i nx? ? ? ??? ? ? ?? ? ? ? ?? ? ?????? ? ? ? ?? ? ? ? () 由此 可知： ??Cx的 i次循環(huán)移位是 ??Cx乘以 ix 后再除以 1nx? 的余式。即： ? ? ? ? ? ? ? ?m od 1i inC x x C x x?? () 根據(jù)循環(huán)碼的循環(huán)特性，可由一個(gè)碼字的循環(huán)移位特性得到其他的非零碼字。在 [, ]nk循環(huán)碼的 2k 個(gè)碼字，取其前 k1位皆為 0的碼字 g(x)(其次數(shù)為 r=nk)，在經(jīng)過(guò) k1次循環(huán)移位后，總共得到 k個(gè)相互獨(dú)立的碼字： ? ? ? ? ? ?1, kg x xg x x g x?可作為碼生成矩陣的 k行，于是得到 ? ?,nk 循環(huán)碼的生成矩陣 ??Gx： ? ?? ?? ?? ?? ?12kkx g xx g xGxxg xgx????????????? () 碼的生成矩陣一旦確定，碼就可以確定。這表明 ? ?,nk 循環(huán)碼可以由它的一個(gè) r(r=nk) 次碼多項(xiàng)式 ??gx來(lái)確定。每一個(gè)碼多項(xiàng)式都是 ??gx的倍式，每一個(gè)是 ??gx倍式且次 數(shù)≤ n1的多項(xiàng)式都是碼多項(xiàng)式。多項(xiàng)式 ??gx稱為碼的生成多項(xiàng)式。 某某 大學(xué)畢業(yè)論文（設(shè)計(jì)） 6 BCH 碼 自 1950年漢明發(fā)表了糾正單個(gè)錯(cuò)誤的碼以來(lái)，幾乎過(guò)了 10年的時(shí)間，才于 1959年由霍昆格姆（ Hocquenghem）， 1960年由博斯 (Bose)和雷一查得胡里（ RayChaudhuri）分別提出了糾正多個(gè)隨機(jī)錯(cuò)誤的循環(huán)碼 — BCH碼的構(gòu)造方法。 BCH碼是目前所發(fā)現(xiàn)的一類很好的線性糾錯(cuò)碼類，它的糾錯(cuò)能力很強(qiáng)，特別是在短和中等碼長(zhǎng)下，其性能接近理論值，并且構(gòu)造方便，編碼簡(jiǎn)單。特別是它具有嚴(yán)格的代數(shù)結(jié)構(gòu)，因此它在編碼理論中起著重要的作用。BCH碼是迄今為止研究得最為詳盡，分析得最為透徹，取得成果也最多的碼類之一。 1960年彼得遜伊（ Peterson）從理論上解決了二進(jìn)制 BCH碼的譯碼算法，奠定了 BCH碼譯碼的理論基礎(chǔ)。稍后，格林斯坦（ Greenstein）和齊勒爾（ Ziegler）把它推廣到多進(jìn)制。 1966年伯利坎譜（ Berlekamp）利用迭代法譯碼 BCH碼，從而大大地提高了譯碼速度，從實(shí)際上解決了 BCH碼的譯碼問(wèn)題。 BCH碼的定義 ： 給定任一有限域 ? ?GFq 及其擴(kuò)域 ? ?mGF q ，其中 q是素?cái)?shù)或素?cái)?shù)之冪， m為某一正整數(shù)。若碼元取自 ? ?GFq 上的一個(gè)循環(huán)碼，它的生成多項(xiàng)式 ??gx的根集合 R中含有以 1?? 個(gè)連續(xù)根，則由 ??gx生成的循環(huán)碼稱為 q進(jìn)制 BCH碼。在實(shí)際中應(yīng)用的最多的是二進(jìn)制 BCH碼，將二進(jìn)制 BCH碼的概念進(jìn)行擴(kuò)展可以得到多進(jìn)制 BCH碼。因?yàn)榇a元符號(hào)取自二元域 ? ?2GF 、糾 t個(gè)錯(cuò)誤的二元 BCH碼的生成多項(xiàng)式是以 ? ?2GF 的擴(kuò)域 ? ?2mGF 上 2t個(gè)相鄰元素為根的多項(xiàng)式。那么，多元 BCH碼的碼元符號(hào)取自多元域 ? ?GFq ，其中 q為某一素?cái)?shù)或素?cái)?shù)之冪，而糾正 t個(gè) 錯(cuò)誤的多元 BCH碼的生成多項(xiàng)式是以 ? ?GFq 的擴(kuò)域 ? ?mGF q 上 2t個(gè)元素為根的 多項(xiàng)式為 ? ? ? ?? ? ? ?22tg x x x x? ? ?? ? ? ? () 多元 BCH碼的校驗(yàn)矩陣： ? ? ? ?? ? ? ?12122 2 2121 1 1111nnnnnnd d dH? ? ?? ? ?? ? ???????? ? ?????????? () 式中， ? 為 ? ?mGFq 本原 元：碼長(zhǎng) 1mnq??； d為設(shè)計(jì)距離， d=2t+1。由 ? ?gx確定的 BCH碼是 q元本原 BCH碼。 RS碼是多元 BCH碼的一種特例，即取 m=1，故 RS碼的生成多項(xiàng)式的根和碼元符號(hào)在同一域上。下面將討論 RS碼。 RS 碼 RS碼是線性分組 BCH 碼中一個(gè)重要的子類。在同樣編碼冗余度下 ,RS 碼具有最強(qiáng)的糾錯(cuò)能力。在 q進(jìn)制 BCH 碼的碼字中 , 每個(gè)碼元的取值在 GF(q)上 ,但碼的 g(x)的根卻在 GF(q)某某 大學(xué)畢業(yè)論文（設(shè)計(jì)） 7 的擴(kuò)域 ? ?mGFq 中 ,若碼元取值的域與碼的 g(x)的根所在的域相同 , 則稱這類 BCH碼為 RS碼。RS碼是非二進(jìn)制循環(huán)碼 ,每一個(gè)碼元由 m個(gè)比特構(gòu)成 ,m是大于 2的任意正整數(shù) .只有所有的 n和 k都滿足 以下條件時(shí)， m比特碼元的 ? ?,RS nk 碼才存在。 02mkn? ? ? () 其中 ,k是已編碼分組的數(shù)據(jù)碼 元數(shù)目 ,n是已編碼分組中總的碼元數(shù) 。 對(duì)于大多數(shù)? ?,RS nk 碼 ? ? ? ?, 2 1,2 1 2mmn k t? ? ? ? () 其中 ,t是 RS碼能夠糾正的錯(cuò)誤碼元個(gè)數(shù) , 2n k t?? 是監(jiān)督碼元個(gè)數(shù)。擴(kuò)展的 RS碼由2mn? ,或 21mn??組成 , 但 n不能再大。對(duì)任何相同輸入輸出分組長(zhǎng)度的線性編碼 , 里德索羅蒙碼可以達(dá)到最大可能的碼元最小距離。對(duì)于非二進(jìn)制編碼 , 兩個(gè)碼字間的距離 (類似于漢明距離 )定義為序列間的不同碼元數(shù)目。里德 索羅蒙碼最小碼本距離為 min 1d n k? ? ? () 這種編碼可以糾正少于 t的任意多個(gè)錯(cuò)誤組合。 t可以表示為 : 1m in[ ] [ ]22d n kt ???? () 其中 :[x] 表示小于或等于 x的最大正整數(shù)。上式表明 ,對(duì)于 RS碼 ,糾正 t個(gè)錯(cuò)誤需要不超過(guò) 2t個(gè)的監(jiān)督碼元。 式 ()具有以下直接含義，我們可以認(rèn)為譯碼器花費(fèi) nk個(gè)冗余碼元，它是可糾正碼元數(shù)的 2倍。對(duì)于每個(gè)錯(cuò)誤，一個(gè)冗余碼元用于定位此錯(cuò)誤，另一個(gè)用于找到其正確的取值。由于 RS的編碼比較簡(jiǎn)單，實(shí)現(xiàn)起來(lái)也很容易。 RS碼的編碼原理分為時(shí)域編碼和頻域編碼 2種，本文中僅討論時(shí)域編碼。 某某 大學(xué)畢業(yè)論文（設(shè)計(jì)） 8 3 有限域的 乘法器設(shè)計(jì) 有限域（伽羅華域）的基本概念 首先介紹一下域 的概念。域 :非空元素集合 Q，若在 Q 中定義了加和乘兩種運(yùn)算且滿足下述公理： 1） Q 關(guān)