TWI362186B - - Google Patents

Description

1362186 100年6月10曰修正替換頁 九、發明說明： ---- 【發明所屬之技術領域】 本發明係關於一種應用於軟體無線電解碼器之特徵值快速計算方法， 特別是指一種應用於里德-索羅門解碼器之特徵值快速計算方法。 【先前技術】 請參閱圖1 ’為習知運用於里德·索羅門解碼器中特徵值計算方法 之流程步驟圖其中Γη為接收多項式以幻中χη項的係數，a為GF(256)之本質 元素，η和k為0到255的整數。運用習知技術在（255,255-2t)里德-索羅. 門碼（企業標準）的症狀計算如下，這㈣【是能更正符號錯誤的數目。 接收多項式 (1)

⑶ 明=%)琳） 這裡的7是傳送的代號，而7是錯誤多項式如 e = ejXJl + ehxh + · · · + e.x^

這個是錯誤的值及{λλ，/…，χΛ丨是錯誤位置。 e.sGF(2m) and XEGF(2m) 症狀的計算如 5, = r(al) = rQa10 + r{a11 +··· + γ„ αΗΐη~Χ) —1 S2 =r(a2) = r0a2.0 +/·ια21 +…+ /· α2·(2™-ΐ) ： r" (4) S2l =r(a2,) = r0a(2〇'° +r,a(201 + + ^ 關於索羅門解碼器中特徵值計算，習知技術乃利用除法技術來達成， 即圖1中的mod 255 ’該mod 255為m〇dul〇 255 (除255取餘數）的除法指 1362186 iOO年6月10日修正替換.. 令。細d運算可以在x86平台的DIV (除法）指令來得^, 中指出’ DIV指令需要23個cpu週期時間，故速度較慢，不適合軟體無、 線電的實現》 由此可見，上述習用技術仍有諸多缺失及不足，實非一良善之設計， 而亟待加以改良。 本案發明人鑑於習用技術所触的各項缺點及不足，乃盈思加以改良 創新，並經多年苦心孤諸潛心研究後，終於成功研發完成本件應用於軟體 無線電解碼器之特徵值快速計算方法。 $ 【發明内容】 本發明之目的即在於提供—種應·軟體無線電解碼器之特徵值快速 計算方法’係_加法指令（ADD)來取代除法指令（div)的使用，進 而使軟體無_解之特雖計算缺為快速。 本發月之-人目的係在於提供一種應用於軟體無線電解碼器之特徵值 快速計算方法，由於很多微處理器（cpu)都是一個16位元暫存器由兩個 8位兀暫存器組成’故本發明將不只限於X86系統之應用。 鲁 可達成上述發明目的之應用於軟體無線電解碼器之特徵值快速計算方 法，係利用加法指令（ADD)來取代目前使用的除法指令（div)，由於一 個16位元暫存器（ax)乃由一個高8位元暫存器（ah)及一個低8位元暫 存器⑻所組成，該高8位元暫存器乘以256再加上低8位元組暫存器， 即為I6位7G暫存器的值，因此10位元暫存器除以255將等於兩個8位元 暫存器相加（ax=ah+al)，又由於使用除法指令所需的時間遠大於加法指令，

S 故本發明以加法指令取代除法 速。 100年6月10日修正替換頁 指令，將可使解碼器之^徵值運算能更為快 【實施方式】 由於在Intel報告指出除法指令（DIV)需要23個cpu週期。將遠大 於加法指令0.5個CPU週期。所以可清楚得知習知技術速度較慢，不適合 軟體無線電技術的實現。 _ 本發明乃在一些條件下用加法指令（ADD)來取代除法指令， 將可以得到較好的效能。 更進一步的分析，可以將X除255運算分為以下三種狀況： 狀況 1 : if ;c<255，fl/i = 0 jc mod 255 = (0x256 + a/)mod 255 =(a/) mod 255 - =al . (5) =ah + al # 狀況 2 : if = 255，aZ = 255，M = 〇 (6) ah + al = 255 xmod 255 = 0^ah + al 狀況 UI:if 256<文<510，以=1，0“/<255 λ： mod 255 =(ah x 256 + al) mod 255 =(1 x 256 + al) mod 255 =(1 + al) mod 255 = l + al =ah + al 丄 δΟ 表1.x mod 255結果

100年6月10曰修正替換頁 結果列在表丨。從這個表中可以注意到大部分（議㈣）的例子能 用㈣來取代。因為邊有炉255，因為_d255 = 〇“y的 關係不能保持。物免糊外，_科細“(傘。⑽”。 —近似的結果如表2所示張表，可注意那行“㈣的_⑴，， 是與x<510的“xm〇d255”相同。 表 2. (x+l) m〇d 255 結果 例 X X mod 255 ah+alf〇r(x+1) ah+al-1 for (x+l) 0 幺；c < 254 X x+l X 例子n 254 254 . 255 254 例子m ---一 255 0 1 — -. 0 例子IV ----- 256 1 2 丨— 1 例子V 256 < λ < 510 x-255 --- x-254 x-255 由於這種關係，本發明設計-個新_程步驟，如圖2所示， 說明里德-索羅門碼，假設“ GF⑽)之本f元素，錢存在一組可 去除t個錯誤符號的(255, 255-2t)里德-索羅門崎，其各項參數定義 如下： 碼字長度 255

S 8 1J62186 訊息位元數目 255-2t 可更正符號錯誤的個數 t 高8位元暫存器 (ah) 低8位元暫存器 (al) 100年6月l〇日修正替換頁 Γη為接收多項式χη項的係數 η和k為〇到255的整數 其流程步驟為： 步驟 1 : = l〇g(rn)+1 + d 步驟 2 : = ί·η. +、· 一 1

步驟 3 :〜=aM-logUJ 其中log為對數運算’ anti_log為log的反運算 -上述流程步驟中並不包含除法運算，乃由加法運算所組成，故於特徵 值運算時可具有較佳之效能，適合軟體無線電技術的實現。 習用的演算法和本發明的演算法的症狀計算流量以有Intd pemium Μ 1顧z CPU χ86㈣赚4測。·工具是Mi_請㈣歸Q聰團 隊版的軟_«。魏量測工具是Mi嶋^ s_聽_效能 探測器。本發_演算法在戦平“錄計算流量是每秒85,47〇個封 包，相較於習用的演算法快了 3.06倍的時間（每秒27,917侧包）。 本發明所提供之應用於敕體無線電解石馬器之特徵值快速計算方法，盘 其他習用技術相互比較時，更具備下列優點·· 、 1.本發明在特徵值計算上省略 的指令替代。 ^改用加法雜魏度快很多倍 1362186 100年6月10日修正替終頁 2. 本發明應用於以χ86個人電腦為基礎的軟體無電DVB-T平台 上’將可使特徵值計算速度增加數倍。 3. 本發明可延伸至以χ86個人電腦為基礎的其他軟體無線電平台 上，只要有使用里德-索羅門解碼器，例如：WiMAX上。 上列詳細說明係針對本發明之一可行實施例之具體說明，惟該實施例 並非用以限制本發明之專利範圍，凡未脫離本發明技藝精神所為之等效實 施或變更，均應包含於本案之專利範圍中。 綜上所述’本案不但在技術思想上確屬創新，並能較習用物品增進上鲁 述多項功效，應以充分符合新雜及進步性之法定發明專利要件，妥依法 提出申請’騎貴局核准本件發明專獅請案，以勵發明，至感德便。 【圖式簡單說明】 圓1為習知運用於里德-索羅門解中特徵值計算〆 方法之流程步 驟圖；以及 &圖2為本發明應用於軟體無線電解竭器之特徵值快速計算^ &方法之 流程步驟圖。 φ 【主要元件符號說明】 無元件符號

S 10

Claims (1)

1. •1362186 100年11月29日修正替換頁 十、申請專利範圍 1. 一種應用於軟體無線電解 竭裔之特徵值快速計算方法，可應用於以 x86個人_為基礎的 一杲弘DVB-丁 +台上，將可使特徵值計算 速度增加數倍，係以加法於八 曰7 (ADD)來進行特徵值之計算；其運算 流程步驟為： 步驟 1 : ζ·” =丨og(r„)+l +虓； 步驟 2 .人4 = ζ·η ·α/ + . a/； -1 ; 步驟 3 :〜=_‘_i〇gD ; 其中〜為接收多項式中χη項的係數，《為〇到255的整數，（為〇到 255的整數，w為低8位元暫存器值，以為高8位元暫存器值。 2·如申請專利範圍第1項所述之應用於軟體無線電解碼器之特徵值快速 計算方法，係可延伸至以x86個人電腦為基礎的其他軟體無線電平^ 上’只要有使用里德-索羅門解碼器。