[發(fā)明專利]錯誤修正碼的編碼及解碼方法以及編碼解碼器

有效

• 申請?zhí)枺?/td>: 200910168023.2
• 申請日: 2009-08-10
• 公開（公告）號: CN101938280A
• 公開（公告）日: 2011-01-05
• 發(fā)明（設(shè)計）人: 楊宗杰
• 申請（專利權(quán)）人: 慧帝科技(深圳)有限公司;慧榮科技股份有限公司
• 主分類號: H03M13/00
• 分類號: H03M13/00
• 代理公司: 深圳市順天達專利商標(biāo)代理有限公司 44217
• 代理人: 易釗

技術(shù)領(lǐng)域

本發(fā)明涉及數(shù)據(jù)通信技術(shù)領(lǐng)域，更具體地說，涉及一種錯誤修正碼的編碼及解碼方法以及編碼解碼器。

背景技術(shù)

錯誤修正碼(error?correction?code)用于修正數(shù)據(jù)的錯誤。通信系統(tǒng)所傳輸?shù)臄?shù)據(jù)于傳輸端傳送前經(jīng)常事先被編碼為錯誤修正碼(包含數(shù)據(jù)訊息及檢查碼)。當(dāng)接收端收到錯誤修正碼數(shù)據(jù)時，即使數(shù)據(jù)于傳輸過程中遭受損毀而產(chǎn)生隨機錯誤，亦可藉解碼錯誤修正碼而回復(fù)正確的數(shù)據(jù)。同樣的，數(shù)據(jù)儲存系統(tǒng)亦經(jīng)常在儲存數(shù)據(jù)前將所儲存的數(shù)據(jù)編碼為錯誤修正碼。當(dāng)數(shù)據(jù)于儲存過程中遭受損毀而產(chǎn)生隨機錯誤時，亦可藉解碼錯誤修正碼而回復(fù)正確的數(shù)據(jù)。常見的錯誤修正碼如BCH碼(Bose，Ray-Chaudhuri，and?Hocquenghem?code)及RS碼(Reed-Solomon?code)。BCH碼常用于閃存數(shù)據(jù)的儲存，而RS碼常用于光盤數(shù)據(jù)的儲存。

當(dāng)數(shù)據(jù)儲存系統(tǒng)欲取出其所儲存的數(shù)據(jù)時，所取出的為編碼后的錯誤修正碼，因此在數(shù)據(jù)使用前必須先解碼錯誤修正碼，以還原為原始數(shù)據(jù)。圖1為錯誤修正碼的習(xí)知解碼方法100的流程圖。首先，解碼器接收一錯誤修正碼(步驟102)。接著，解碼器依據(jù)該錯誤修正碼的檢查碼(parity)計算多個癥狀碼(syndrome)(步驟104)。接著，解碼器檢查是否該等癥狀碼皆為零(步驟106)。若該等癥狀碼為零，表示錯誤修正碼沒有發(fā)生錯誤，因此不需進一步的修正。反之，若該等癥狀碼有其中之一不為零，表示錯誤修正碼有錯誤發(fā)生，因此必須對錯誤修正碼進行修正。首先，解碼器依據(jù)該等癥狀碼計算一錯誤多項式(error-location?polynomial)的多個系數(shù)(步驟108)。接著，解碼器執(zhí)行一秦氏搜尋(Chien?search)以找出該錯誤多項式的根(步驟110)。由于該錯誤多項式的根指示錯誤修正碼中發(fā)生錯誤的位的位置，因此解碼器便可依據(jù)該錯誤多項式的根修正該錯誤修正碼(步驟112)，而得到無錯誤的錯誤修正碼，亦即得到正確的數(shù)據(jù)。

然而，當(dāng)解碼器于步驟108計算錯誤多項式的系數(shù)時，會耗費許多時間。同樣的，當(dāng)解碼器于步驟110進行秦氏搜尋以找出錯誤多項式的根時，亦會耗費許多時間。于習(xí)知的解碼方法100中，只要錯誤修正碼的多個癥狀碼其中之一不為零便表示有錯誤發(fā)生，因此必須執(zhí)行步驟108與步驟110以便修正錯誤，也因而造成系統(tǒng)的解碼時間的延遲。于錯誤修正碼的多個癥狀碼不為零時，若能在部分情況中以其它方式修正錯誤修正碼，進而避免于步驟108中計算錯誤多項式的系數(shù)以及于步驟110中進行秦氏搜尋以找出錯誤多項式的根，則可大大的減少所需的解碼時間，而增進解碼器的效能。因此，需要一種可減少錯誤修正碼的解碼時間的編碼及解碼方法。

發(fā)明內(nèi)容

本發(fā)明所要解決的技術(shù)問題在于針對現(xiàn)有技術(shù)的上述缺陷，提供一種錯誤修正碼的編碼及解碼方法以及編碼解碼器。

本發(fā)明解決其技術(shù)問題所采用的技術(shù)方案之一是：構(gòu)造一種錯誤修正碼的編碼及解碼方法，其包括下列步驟：接收一原始數(shù)據(jù)；將該原始數(shù)據(jù)分割為多個區(qū)段數(shù)據(jù)；依據(jù)一第一產(chǎn)生多項式(generator?polynomial)分別產(chǎn)生該等區(qū)段數(shù)據(jù)之短檢查碼(short?parity)；附加該等短檢查碼于該等區(qū)段數(shù)據(jù)之后，以分別產(chǎn)生多個短碼字(short?codeword)；結(jié)合該等短碼字以得到一編碼數(shù)據(jù)；依據(jù)一第二產(chǎn)生多項式(generator?polynomial)以產(chǎn)生該編碼數(shù)據(jù)之長檢查碼(long?parity)，其中該第一產(chǎn)生多項式為該第二產(chǎn)生多項式之至少一個最小多項式(minimumpolynomial)的函式；附加該長檢查碼于該編碼數(shù)據(jù)之后，以產(chǎn)生該錯誤修正碼之一長碼字(long?codeword)。

本發(fā)明所述的錯誤修正碼的編碼及解碼方法，其中該第一產(chǎn)生多項式為該第二產(chǎn)生多項式的至少一個最小多項式的最小公倍式。

本發(fā)明所述的錯誤修正碼的編碼及解碼方法，更包括儲存該長碼字于一儲存媒體中。

本發(fā)明所述的錯誤修正碼的編碼及解碼方法，更包括：

自一儲存媒體讀出該長碼字；自該長碼字取出其所包含的該等短碼字；依據(jù)該等短碼字的該等短檢查碼計算該等短碼字的多個短癥狀碼；檢查是否該等短癥狀碼皆為零；以及當(dāng)該等短癥狀碼其中的一至數(shù)個非零短癥狀碼不為零時，利用該等非零短癥狀碼更正對應(yīng)的該等短碼字。

本發(fā)明所述的錯誤修正碼的編碼及解碼方法，更包括：