TWI334279B - Efficient chien search method for reed-solomon decoding and machine readable recording medium comprising instructions for performing the method - Google Patents

Description

、發明說明： 【發明所屬之技術領域】 本發明是有關於一種里得-索羅門（Reed-Solomon)解碼 中之陳氏尋根（Chien Search)方法，特別是指一種里得·索羅 門解碼中減少程式流程分歧（Branch)以提昇效能之陳氏尋根 方法’及包含用以執行該方法之複數指令的機器可讀記錄 媒體。 【先前技術】 近年來’從消費性電子產品到通訊電子產品，對於訊 號傳送之可靠度的需求曰漸殷切；因此，錯誤偵測更正機 制也日益重要。在數位通訊過程中，傳送端為了確保欲傳 送之原始資料的正確性’一般而言，會對原始資料附加冗 餘資料（Redundant Data)，而接收端即可根據此冗餘資料進 行錯誤校正；其中以里得-索羅門碼最為常見。也由於里得_ 索羅門碼對於傳輸通道中所產生的錯誤有很好的更正能力 故成為非㊉受歡迎的通道編碼（Channel Coding)方式之一 且目别已為衛星通訊系統、數位電視系統、各式數位影 音記錄媒體等所廣泛使用之錯誤更正碼（Error Correction Code)。 儘管里得-索羅門碼在錯誤更正方面有相當優異的效能 表現，但其解碼所需的運算量十分龐大，所以通常會以硬 體的方式來汁算處理；若要以程式解碼的方式在處理器上 =仃，勢必會遭遇到運算量過於龐大而導致解碼速度過於 緩慢的問題；ϋ在一些由軟體定義作業(像是，軟體無線電 1334279 (Software Defined Radio, SDR))之通訊裝置的應用上，加速 里知··索羅門碼之程式解碼速度已然成為一項重要之研究課 題。

參閱圖1，現有的里得-索羅門解碼程序可分為四個階 段，分別如階段11、12、13，及14所示：徵候（syn(jrome) »十算錯誤位置多項式（Error Location Polynomial)計算、陳 氏尋根（Chien Search)，及錯誤值（Error Value)計算。在此里 侍-索羅門解碼程序中，將近4〇%的運算量是集中在階段Η 的陳氏尋根，若能有效降低陳氏尋根之處理時間，即可成 功地加速里得·索羅門碼之解碼速度。

參閱圖2, 一習知的里得_索羅門解碼中之陳氏尋根方 法包含下列步驟。在步驟21中，初始化一位置索引，j = 〇 ;以及一符號（Symbol)索引，i = 0。在步驟22中，計算一 ，誤評估值Λ(α，·）。在步驟23中，判斷該錯誤評估值八以·） 是否等於G;若是，則代表第丨個位置的符號有錯誤發生， 需進行步驟24之處理；否則，繼續進行步驟26之處理。 在步驟24〜25中’先將目前的符號索引丨儲存至—錯誤位置 陣列，L〇Cati〇n[j] = i;繼而增加該位置索引……+1。在 步驟26〜28中，判斷陳氏尋根是否已完成，即判斷是否 结束陳氏尋根；否則，增加該符號索引， 別」並回到上述步驟重複執行。其中，n代表已接收之 一里得.索羅門區塊碼（Block Code)的-符號（SymbGl)總數。 該習知方法之步驟23所執行的判斷處理，會產生程式 流程分歧(Branch);也就是當Λ⑷^時執行某日―運算⑽ 6 1334279 ’步驟24)’當咖㈣時執行另一運算（即，步驟26)。分 歧會造成處理器之亂序執行（Dis〇rder Executi〇n)，連帶使得 處理器之管線(Pipeline)内部的指令與資料重置，而導致整 體效能不彰。 其他習知的里得-索羅門解碼中之陳氏尋根方法如美 國專利公告號祕，263,470及US6,36〇,348中所揭露，主要 是以查表（Lockup Table)方式加速陳氏尋根之計算；但皆 未對解決陳氏尋根内程式流程分歧的問題有所著墨。

因此，有必要尋求一解決之道，以減少該習知方法中 之程式流程分歧，使得陳氏尋根之處理時間更進-步地降 低，而加速里得-索羅門碼之解碼速度。 【發明内容】 Φ古& t "你捉供一裡里得-索羅門解碼 集（Par 陳氏尋根方法，適用於在-具有平行處理指令 、s Pr°GeSSlng Instrueti()n Set)之處理器上執行。

於疋’本發明里得-索羅門解碼 法是包含下列步驟：（心笪心 K陳氏寸根方 估值進行映射處理，^評估值;(b)將該錯誤評 引健存至-錯誤位置記整值;⑷將—㈣ 該索引調整值更新該位 ’ h據 將步驟⑷〜⑷重複一特定次數。（)—索引;及⑺ 解碼根:在提供一種供執行里得-索羅門 於0 + 氏尋根方法之機器可讀記錄媒體。 疋發明機器可讀記錄媒體是包含複數指令’該 7 4令用以在-具有平行處理指令集之處理器上 ⑷計算-錯誤評估值；⑻㈣錯料估 ^ ::置Γ求得一索引調整值; 更新:广憶Γ對應一位置索引處；⑷根據該索引調整‘ 重複-特定次數。 及⑴將步驟⑷〜⑷ 陳氏藉由減少陳氏尋根巾之程式流程分歧，使得 吸氏哥根之處理時間 更進步地降低，而加速里得-索羅門 馬之解碼速度’的確可制本發明之目的。 【實施方式】 、有關本發明之前述及其他技術内纟、特點與功效，在 乂下配合參考®式之—個較佳實施例的詳細說明中，將可 清楚的呈現。 回顧圖1里得-索羅門解碼程序包含四個階段I〗、I〗 、13，及14。在階段u中，徵候計算之目的是為了判斷接 收到的訊號是否已受到雜訊（N〇ise)的污染；若徵候的計算 結果為0，代表訊號未受雜訊污染（即，接收到之訊號正確） ’否則’就必需繼續進行階段12〜14之處理。在階段12中 利用柏力月-梅西演算法（Beriekainp-Massey Algorithm)， 以計算出一錯誤位置多項式。在階段13中，根據該錯誤位 置多項式進行陳氏尋根，以求出至少一錯誤評估值，該錯 誤評估值可用以確認錯誤位置。在階段14中，求出至少一 錯誤值’最後在適當的錯誤位置減去錯誤值，以還原出正 確訊號。 一般而言’一里得-索羅門區塊碼的設計都是以Reed_ Solomo咖，A：)來表示，”代表經過編碼後每個區塊⑻〇叫的 符號總數，代表每個區塊被編碼的原始訊息符號（Message Symbol)數目，且>(„一幻/2，,代表至多可校正之錯誤數目 以歐規 DVB(Digital Video Broadcasting)系統為例，其採 用的為Reed-S〇l〇m〇n(204，188)，即，該里得-索羅門區塊碼 内總共有204個符號、被編碼的原始訊息符號數目為】88 , 且至多可校正8個錯誤。 假設接收到的該里得-索羅門區塊碼如表示式（1)所示。 r = r〇+r1+r2+... + ri+... + rn_l....................................... 其中’ ί為一符號索引，Γι•代表該里得_索羅門區塊碼中 第/個符號。 經過柏力肯·梅西演算法可求出有錯誤產生之符號的數 量以及錯誤位置多項式，假設有錯誤產生之符號共有d個 ’則s十鼻出之錯誤位置多項式如表示式（2)所示。 八(α )-々 + + 々a21 + 々a31 -----1- Adad,........ (之） 其中，of幺之。 ^對於每一個符號~計算對應之錯誤評估值Λ(α,·)，其計 算公式如表示式（3)所示。 A(a〇)=々+ Aja0 +々a0 +知0 +…+又〆 八(a ) = 4 +々a1 + \a2 +々a3 +…+又〆 ： .............(3) 八(a )= 4 丨 + 々a2"2 + Αα3"-3 η-----μ ^ ccd^n~1^ 若計算出之Λ(«ό為0，則表示符號。有錯誤產生；否 1334279 則’表示符號r(•正確無誤。 由於里付-索羅門碼之編碼/解碼原理及其有限 建構於迦羅瓦場(Gal()is Field陶Ί，2„代麵羅瓦場^ 應的兀素總數。在本說明書中’表示式(3)内錯誤評估值 Λ(α )之有限場運算為迦羅瓦場運算。 本發明里得索解碼中有效率之陳氏尋 “施例’可藉由軟體程式而完成。故本發明是以程^ s撰寫複數指令後’儲存於一機器可讀記錄媒體；當 指令載入至一具有平行處理指令集Λ 行本發明之方法。 返執 在本較佳實施例中，該方法是在具有SSE2指令集之 州處理器上執行，但該方法亦可在其他具有類似的平行處 理指令集之數位訊號處理器_)、通用處理器⑽咖 Purpose Proce謝）、或中央處理單元（cp⑺上執行所以， 本發明之實施麟受限於本較佳實施例之例示。 根方法包含下列步驟 參閱圖3,本發明里得-索羅門解碼中有效率之陳氏尋 在步驟31中’初始化一位f旁 . ^ ^ 伹置裳引，尸〇;以及初始化該 苻號索引，ζ·=〇。 在步羯32 t，根據表示式（3)所示之計算公式求出該 f誤評估值咐）。在本較㈣施射，是藉由該平行處理 指令集進行向量式有限場運算，—次平行計算“筆錯誤 *平估值ΛΟ1)〜Λ(α,+0>_1))。jl中，a曰丄 /、中，向1式有限場運算技術並非 本發明之重點部分，其4τ & 、、-即不在此贅述。又，p筆錯誤評估

10 值Λ (y)亦可以其他的習知技術（如前述之美國專利 公=號US6,263,470 & US6,36〇 348中所揭露的查表方式） 求仔所以’本發明之實施並非受限於本較佳實施例之例 >|> 〇 在步驟33中，將該錯誤評估值输,_)進行映射㈣㈣ 處理’以求得一索引調整值G _，若錯誤評估值雄,)為〇 ’則該索引調整值心為i S則，該索引調整值6為0，如 表示式（4)所示。 = =1 ▽Λ(〇0 矣 ................................................................. 在本較佳實施例中，是藉由該平行處理指令集一次平 行映射p筆錯誤評估值雄，卜咖+㈣）。以χ86處理器之 SE2平盯處理&令集為例，先以”Mb ^令同時將 /KP=16)筆錯誤評估值Λ(α，)〜Λ(〆㈤中每一筆與〇比較其 中，若某一錯誤評估值Λ(α1為〇，則，（十二 進位）’否則’ Λ’(α^)=0;繼而以ρ_指令同時將户筆 八’的〜AV例）中每一筆與〇x〇lh進行交集（a剛運算。如 圖4所示，經過pcmpeqb與pand指令後，即可得到p筆索 引調整值。 “ 參閱圖3，在步驟34中，將該符號索引儲存至一錯 誤位置記憶體中對應該位置索引y•處。其中，該錯誤位置記 憶體實際上為一陣列（Array)，假設為L〇cati〇n[i^h而步 驟34之處理可表示為：L〇cation[/]=纟。 丨 在步驟35中’將該位置索幻·加上該索引調整值匕， 1334279 以更新該位置索引y，即，y h。 在步驟36中，更新該符號索引卜即，卜 值得/主〜的疋，在本較佳實施例中，是將ρ筆索引調 整值H+㈣依序進行步驟34〜36之處理；也就是說，在 進行完步驟33之處理後ϋ依序進行ρ次步驟34~36之 處理。其中’當㈣時’表示該符號索弓"會填入相同的 記憶體位置，此即為記憶體同位(Memory InPlace)技術。 在步驟37〜38中，判斷陳氏尋根是否已完成；若是， 則結束；否則，重複執行步驟32〜36。其中，步驟㈣之 重複人數取决於„亥里;j[索羅門區塊石馬内的符號總數”，當 處理π該里传-索羅門區塊碼内所有符號之後(此時，卜“) ’則代表陳氏尋根已完成。 回顧圖2’本發明藉由該錯誤評估值♦)之映射處理 以及記憶體同位技術，避免了該習知方法之步驟D所造成 的程式流程分歧。 歸納上述，由於本發明方法解決了陳氏尋根内程式流 知分歧的問題’減少處理器之亂序執行並提昇其管線之使 .用效能。因此’進-步降低了陳氏尋根的處理時間成功 地加速里得·索羅門碼之解碼速度，的確可以達成本發明之 目的0 惟以上所述者，僅為本發明之較佳實施例而已，當不 能以此限定本發明實施之範圍，即大凡依本發明申請專利 範圍及發明說明内容所作之簡單的等效變化與修飾，皆仍 屬本發明專利涵蓋之範圍内。 12 !； C· 1334279 【圖式簡單說明】 圖1是一架構圖，說明-里得·索羅門碼之解碼 圖2是一流程圖，說明習知 解：程序’· 氏尋根方法； 系羅門解碼中之陳 圖 2 β 上 率之 疋一 ^程圖，說明本發明里得-索羅門解碼中有效 東氏尋根方法的較佳實施例；及 圖4 β 也 疋一示思圖，說明本發明之較佳實施例的映射處 理。

13 1334279 【主要元件符號說明】 11〜14·…階段 31〜38.…步驟 21〜28-···步驟

14 ' S >

Claims (1)

1. 十、申請專利範圍： 1. :種里得-索羅Η解碼中有致率之陳氏尋根方法，適用於 有平行處理指令集之處理器 下列步驟： 3 (a)計算一錯誤評估值； 整值⑻將該錯誤評估值進行映射處理，以求得—索引調 (0將一符號索引儲存至_ 位置索引處； 肖誤位置記憶體中對應― ⑷根據該索引調整值更新該位置索引： (e)更新該符號索引；及 μ ’ ⑴將步驟⑷〜⑷重複—特定次數。 2. 依據申請專利範圍第】項所述之里 率之陳氏尋奸古、±_ 于·索羅門解碼中有效 半之陳氏德方法，其中， 一里得_索羅 ^疋人數取決於已接收之 于京羅門區塊碼的一符號總數。 3. 依據申請專利範圍第2項所述之里 率之陳氏尋根方法，其中，該步=)_中索羅⑽碼中有效 值為〇,則該“調整值為，，否則，二該錯誤評估 。 〜該索弓丨調整值為0 4. 依據申請專利範圍第3項所述之里得 率之陳氏尋根方、去 '、，-門解碼中有效 兮很万去’其中，該步驟⑷中 加上該索引調整值，以更新該位置索^ 该位置索引 5. 依據申請專利範圍第！項所述之里 率之陳氏尋根方法，其中，該步令羅=解碼甲有效 )Ύ 藉由該平行處 < S' 15 1334279 理才a令集將该錯誤評估值進行映射處理，以β 調整值。 ，得該索引 6. —種機器可讀記錄媒體，包含複數指令，該等护八 在-具有平行處理指令集之處理器上執行以下步日令用以 (a) 計算一錯誤評估值； . (b) 將該錯誤評估值進行映射處理， 整值； 索弓丨調 ⑷將一符號索引儲存至-錯誤位置記憶 位置索引處； r對應一 (d) 根據該索引調整值更新該位置索引； (e) 更新該符號索引；及 (f) 將步驟（a)〜(e)重複一特定次數。 7. 依據申請專利範圍第6項所述之機器可讀記錄媒 中，該特定次數取決於已接收之一里得-索 的 一符號總數。 甩碼的 8. 依據申請專利範圍第7 項所述之機器可讀記錄媒 中，該步驟（b)中，若兮扭& 具 右該錯誤坪估值為〇,則該索引調整 值為1，否則，該索引調整值為〇。 9·依據申請專利範圍第8 哨所it之機益可瀆記錄媒體，1 中’該步驟（d)中，將該位f舍 置宗引加上該索引調整值， 更新該位置索引。 M 10.依據申請專利範圍第6項 哨尸坏攻之機可璜記錄媒體，並 中，該步驟（b)中，藉由該平 八 ^ . 十仃處理指令集將該錯誤評估 值進盯映射處理，以求得該索引調整值。 16