修正歐幾裡德算法的部分並行實現方法及裝置的製作方法
2023-10-08 16:51:59 2
專利名稱：修正歐幾裡德算法的部分並行實現方法及裝置的製作方法
技術領域：
本發明涉及數字信息傳輸領域，特別是涉及一種用於CMMB(China MobileMultimedia Broadcasting,中國移動數字多媒體廣播電視)系統的修正歐幾裡德算法的部分並行實現方法。本發明還涉及一種修正歐幾裡德算法的部分並行實現裝置。
背景技術：
CMMB是中國國家廣電總局於2006年10月頒布的中國移動多媒體廣播行業標準，該標準於2006年11月I日起正式實施。它是一種基於多載波OFDM (正交頻分復用)技術的無線廣播系統，採用先進的信道糾錯編碼和多載波OFDM調製技術，提高了抗幹擾能力和對移動性的支持；採用時隙發射方式來降低終端的功耗。依據CMMB網絡覆蓋的設想，CMMB信號由S波段衛星覆蓋網絡和U波段地面覆蓋網絡實現信號覆蓋。S波段衛星覆蓋網絡廣播信道用於直接接收，Ku波段上行，S波段下行；分發信道用於地面增補轉發接收，Ku波段上行，Ku波段下行，由地面增補網絡轉發器轉為S波段發送到CMMB終端。為實現城市人口密集區域移動多媒體廣播電視信號的有效覆蓋，採用U波段地面無線發射構建城市U波段地面覆蓋網絡。信號的地面無線傳送階段，由於地面無線傳輸環境比較惡劣，會對傳輸信號產生複雜的信號畸變，在接收端必須採用一定的信號處理方法進行數據恢復。基於OFDM技術，CMMB系統本身可以減少信號無線傳輸過程中的頻率選擇性幹擾，但是由於CMMB系統中包含傳輸速率較高的多電平調製方式，為了得到性能較好的傳輸質量，CMMB接收端需要採用相干解調方式恢復信號。相干解調方式將帶來3dB的信號增益，雖然實現複雜度較之非相干解調高，但是將明顯提高信號接收質量。因此，在CMMB系統中，前向糾錯部分是影響系統接收性能的一個關鍵部分。在CMMB系統中，針對RS (裡德-索羅蒙)碼的三種模式，可以採用純串行實現方法，但是這種實現方法運行時間上很長，並不能滿足某些系統的時序要求；採用全並行的實現方法，雖然運行時間比較快，但是其佔用了大量的組合邏輯運算單元。因此如何在減少組合邏輯運算單元數量的同時，又能很好的滿足系統時序的要求，成為了一個需要解決的問題。
發明內容
本發明要解決的技術問題是提供一種修正歐幾裡德算法的部分並行實現方法，既能有效減少組合邏輯運算單元的數量，又能保證高效進行數據處理；為此，本發明還要提供一種修正歐幾裡德算法的部分並行實現裝置。為解決上述技術問題，本發明的修正歐幾裡德算法的部分並行實現方法包括如下步驟
步驟一、根據伴隨式的計算結果，初始化錯誤位置多項式和錯誤值多項式，使Q(X)=s(x),R(X) = 0, n (X) = 0, ii (X) = I ;其中，1^)為錯誤值多項式，n (X)為錯誤位置多項式，S(x)為伴隨多項式，Q(X)和U (x)分別為計算錯誤值多項式和計算錯誤位置多項式的輔助多項式；步驟二、將M項所述錯誤位置多項式和M項錯誤值多項式分為4組，每組內包含N項錯誤位置多項式和N項錯誤值多項式，每個周期內同時完成N項錯誤位置多項式和N項錯誤值多項式的並行運算，四個周期完成第一次迭代運算，得到錯誤位置多項式和錯誤值多項式的最高次數項係數和控制信號，繼而進行下一次的第二次迭代運算；其中，M和N均為大於I的正整數；步驟三、在設定的2t X4個周期結束時，停止迭代運算，此時得到錯誤位置多項式和錯誤值多項式。本發明的修正歐幾裡德算法的部分並行實現裝置，包括初始化模塊，用於對錯誤值多項式和錯誤位置多項式進行初始化，使Q(X)= S(X)，R(X) =0，n(x) =0, u (x) = I;其中，R(X)為錯誤值多項式，n(x)為錯誤位置多項式，S(X)為伴隨多項式，Q(X)和U (x)分別為計算錯誤值多項式和計算錯誤位置多項式的輔助多項式；並行運算單元，與初始化模塊相連接，每個並行運算單元包括16個組合邏輯運算單元，每個並行運算單元在一個周期內完成四分之一錯誤值多項式和錯誤位置多項式的迭代運算，在4個周期內完成所有錯誤值多項式和錯誤位置多項式的一次迭代運算；在每次錯誤值多項式迭代運算完成後得到錯誤值多項式的最高次數項係數，同時一次迭代運算完成後進行移項操作，將空出的組合邏輯運算單元在下一次迭代運算時用於錯誤位置多項式的計算。常規MEA (修正歐幾裡德算法)實現的方法存在的不足之處是(I)全並行實現方法，使錯誤值多項式和錯誤位置多項式分開運算，佔用了大量的組合邏輯運算單元；(2)純串行實現方法運算時間太長，效率不高。本發明通過研究MEA算法流程，提出了一種基於錯誤值多項式和錯誤位置多項式，利用同一個組合邏輯運算單元計算錯誤多項式和錯誤位置多項式的部分並行實現方法。由於計算錯誤值多項式和錯誤位置多項式的組合邏輯運算單元結構相同，利用錯誤值多項式左移之後空出來的組合邏輯運算單元來計算錯誤位置多項式，這樣就不用再產生新的組合邏輯運算單元對錯誤位置多項式進行計算，使得組合邏輯運算單元的數量大大減少，且運算時間仍可滿足系統需求；另外，採用部分並行的實現方法，又進一步減少了一部分組合邏輯運算單元。本發明既能有效減少組合邏輯運算單元的數量，又能保證高效進行數據處理。
下面結合附圖與具體實施方式
對本發明作進一步詳細的說明圖I是基於修正歐幾裡德算法的CMMB系統結構圖；圖2是基於修正歐幾裡德算法的FEC(前向糾錯)模塊結構圖；圖3是基於修正歐幾裡德算法的RS模塊結構圖；圖4是基於修正歐幾裡德算法的部分並行實現結構圖；圖5是基於修正歐幾裡德算法的部分並行實現方法的流程圖6是圖4所示的部分並行結構中的組合邏輯運算單元結構圖。
具體實施例方式為了保證接收信號的可靠性，避免在傳輸及解碼過程當中出現錯誤，CMMB系統在編碼時採用了 RS (240，224)，RS (240，192)，RS (240，176)三種編碼方式來增強系統本身的糾錯能力。這種編碼方式要增加一些冗餘數據，在解碼時通過這些冗餘數據可以判斷數據的正確性。本發明提出了一種基於修正歐幾裡德算法的，保證採用較少組合邏輯運算單元且高效的進行數據處理實現方式。CMMB系統的前向糾錯模塊位於解碼模塊之後，如圖I所示。對於接收到的信號經過解調、FFT (快速傅立葉變換)、解擾和解碼之後，已經得到了最後的數據，為了保證這些數據的準確性，加入了最後的前向糾錯模塊。 如圖2所示，所述前向糾錯模塊主要包括四個依次串接的模塊，分別是解位交織(BIDN)模塊、低密度奇偶校驗碼(LDPC)模塊、解字節交織(BYDIN)模塊和裡德-索羅蒙(RS)解碼模塊。其中，低密度奇偶校驗碼模塊和裡德-索羅蒙解碼模塊為主要的數據糾錯模塊。另外兩個模塊，解位交織模塊和解字節交織模塊分別為LDPC模塊和RS解碼模塊做好準備，數據經解位交織後送入LDPC模塊進行解碼，再經解字節交織後送入RS解碼模塊。參見圖3所示，一個完整的RS解碼模塊主要包括三部分，分別是伴隨式計算模塊、MEA(修正歐幾裡德算法)模塊(即所述的修正歐幾裡德算法的部分並行實現裝置)和錢氏搜索福尼計算模塊。其中，伴隨式計算模塊用於計算伴隨多項式各項係數且確定傳送來的數據有無錯誤；數據一進入RS解碼模塊就要進入到緩存寄存器中進行數據緩存，緩存數據是為了保存原始數據；MEA模塊用於計算得到錯誤值多項式和錯誤位置多項式；錢氏搜索可以確定出錯誤位置及錯誤個數，福尼計算則可以確定錯誤值；加法器，將緩存寄存器中的保存原始數據與錢氏搜索模塊確定出的錯誤值多項式和錯誤位置多項式相加，得到的和輸入給寫回模塊，將錯誤修正。因此，MEA模塊是RS解碼模塊中的一個核心模塊，從算法角度也是最為複雜的部分。結合圖5所示，在MEA模塊中，首先是由初始化模塊對錯誤值多項式和錯誤位置多項式進行初始化，Q(X) = S(X), R(X) = 0, n (X) = 0, u (x) = I ;其中，R(X)為錯誤值多項式，n (X)為錯誤位置多項式，S(X)為伴隨多項式，Q(X)和U (x)分別為計算錯誤值多項式和計算錯誤位置多項式的輔助多項式。以RS(240，176)為例，錯誤值多項式和錯誤位置多項式均為64項，將16項錯誤值多項式和錯誤位置多項式作為一組，共分4組由並行運算單元進行並行迭代運算，如圖4所示。圖4中的每個並行運算單元又包括16個如圖6所示的組合邏輯運算單元，使這64項錯誤值多項式和計算錯誤位置多項式的一次迭代運算在4個周期內完成，經過2t次這樣的迭代運算以後(圖中每個運算單元表示一次迭代運算)，即可得到錯誤值多項式和錯誤位置多項式的各項係數。數據進入組合邏輯運算單元後，如果錯誤值多項式的最高次數項係數a古0，且A=deg(R)-deg(Q)彡0，使R(X)和Q (X)相互交換，a和b相互交換(a，b分別為R和Q的最高次數項係數)，然後再進行迭代運算，計算錯誤值多項式和錯誤位置多項式；否則直接計算錯誤值多項式和錯誤位置多項式。當迭代運算到固定周期(2tX4)時即可停止迭代運算。迭代運算完成後，對於RS(240，224)模式，得到的錯誤位置多項式和錯誤值多項式分別是8項多項式；對於RS(240,192)模式，得到的錯誤位置多項式和錯誤值多項式分別是24項多項式；對1 (240，176)模式，得到的錯誤位置多項式和錯誤值多項式分別是32項多項式。圖6為一個組合邏輯運算單元的結構圖，本發明將錯誤位置多項式和錯誤值多項式的運算放在了同一個周期。在圖6中，每一個組合邏輯運算單元運算完成以後，錯誤值多項式要左移一項，右邊空出來的組合邏輯運算單元對計算錯誤值多項式是浪費的，利用這些空出來的組合邏輯運算單元來計算錯誤位置多項式，這樣相當於省掉了本來應該用於計算錯誤位置多項式的組合邏輯運算單元，為MEA模塊的設計省去大量的組合邏輯運算單圖6中描述了兩種運算過程，分別是當A = deg(R)-deg(Q)≥0，則給出交換(swap)信號,此時使R(x)和Q(X)相互交換，deg(R)和deg(Q)相互交換,進行尺=尺+
a
的運算，此時deg(Q)進行加I操作；當A = deg(R)-deg(Q) < 0,則直接進行i = +
a
運算，此時deg(R)進行加I操作。得到的計算結果用於下一次迭代計算。以上通過具體實施方式
對本發明進行了詳細的說明，但這些並非構成對本發明的限制。在不脫離本發明原理的情況下，本領域的技術人員還可做出許多變形和改進，這些也應視為本發明的保護範圍。
權利要求
1.一種修正歐幾裡德算法的部分並行實現方法，其特徵在於，包括如下步驟 步驟一、根據伴隨式的計算結果，初始化錯誤位置多項式和錯誤值多項式，使Q(X)=S(X)，R(X) = O，n (X) = 0, u (x) = I ;其中，R(X)為錯誤值多項式，n (X)為錯誤位置多項式，S(X)為伴隨多項式，Q(X)和U (x)分別為計算錯誤值多項式和計算錯誤位置多項式的輔助多項式； 步驟二、將M項所述錯誤位置多項式和M項錯誤值多項式分為4組，每組內包含N項錯誤位置多項式和N項錯誤值多項式，每個周期內同時完成N項錯誤位置多項式和N項錯誤值多項式的並行迭代運算，四個周期完成第一次迭代運算，得到錯誤位置多項式和錯誤值多項式的最高次數項係數和控制信號，繼而進行下一次的第二次迭代運算；其中，M和N均為大於I的正整數； 步驟三、在設定的2tX4個周期結束時，停止迭代運算，此時得到錯誤位置多項式和錯 誤值多項式。
2.如權利要求I所述的方法，其特徵在於在執行步驟一完成初始化後，如果錯誤值多項式的最高次數項係數a古0,且A = deg(R)-deg(Q)彡0,則使R(X)和Q(X)相互交換,a和b相互交換，然後再進行迭代運算，計算錯誤值多項式和錯誤位置多項式；否則直接計算錯誤值多項式和錯誤位置多項式；其中，a, b分別為RU)和Q(X)的最高次數項係數。
3.—種修正歐幾裡德算法的部分並行實現裝置，其特徵在於，包括 初始化模塊，用於對錯誤值多項式和錯誤位置多項式進行初始化，使Q(X) = S(X)，R(x) = 0，n (x) = 0, u (x) = I ;其中，R(X)為錯誤值多項式，n (x)為錯誤位置多項式，S(X)為伴隨多項式，Q(X)和U (x)分別為計算錯誤值多項式和計算錯誤位置多項式的輔助多項式； 並行運算單元，與初始化模塊相連接，每個並行運算單元包括16個組合邏輯運算單元，每個並行運算單元在一個周期內完成四分之一錯誤值多項式和錯誤位置多項式的迭代運算，在4個周期內完成所有錯誤值多項式和錯誤位置多項式的一次迭代運算；在每次錯誤值多項式迭代運算完成後得到錯誤值多項式的最高次數項係數，同時一次迭代運算完成後進行移項操作，將空出的組合邏輯運算單元在下一次迭代運算時用於錯誤位置多項式的計算。
全文摘要
本發明公開了一種修正歐幾裡德算法的部分並行實現方法，步驟一、根據伴隨式的計算結果，初始化錯誤位置多項式和錯誤值多項式，使Q(x)＝S(x)，R(x)＝0，η(x)＝0，μ(x)＝1；其中，R(x)為錯誤值多項式，η(x)為錯誤位置多項式；步驟二、在同一周期內同時對錯誤值多項式和錯誤位置多項式並行進行迭代運算；步驟三、在設定的周期結束時，停止迭代運算，得到錯誤位置多項式和錯誤值多項式。本發明還公開了一種修正歐幾裡德算法的部分並行實現裝置。本發明既能有效減少組合邏輯運算單元的數量，又能保證高效進行數據處理。
文檔編號H04L1/00GK102655443SQ201110052369
公開日2012年9月5日 申請日期2011年3月4日 優先權日2011年3月4日
發明者張玉安 申請人:上海華虹集成電路有限責任公司