錯誤修正碼的編碼及解碼方法以及編碼解碼器的製作方法

2023-09-18 12:28:00

專利名稱：錯誤修正碼的編碼及解碼方法以及編碼解碼器的製作方法
技術領域：
本發明涉及數據通信技術領域，更具體地說，涉及一種錯誤修正碼的編碼及解碼 方法以及編碼解碼器。
背景技術：
錯誤修正碼(error correction code)用於修正數據的錯誤。通信系統所傳輸 的數據於傳輸端傳送前經常事先被編碼為錯誤修正碼(包含數據訊息及檢查碼)。當接 收端收到錯誤修正碼數據時，即使數據於傳輸過程中遭受損毀而產生隨機錯誤，亦可藉解 碼錯誤修正碼而回復正確的數據。同樣的，數據儲存系統亦經常在儲存數據前將所儲存的 數據編碼為錯誤修正碼。當數據於儲存過程中遭受損毀而產生隨機錯誤時，亦可藉解碼 錯誤修正碼而回復正確的數據。常見的錯誤修正碼如BCH碼(Bose，Ray-Chaudhuri, and Hocquenghem code)及 RS 碼(Reed-Solomon code)。BCH 碼常用於快閃記憶體數據的儲存，而 RS 碼常用於光碟數據的儲存。當數據儲存系統欲取出其所儲存的數據時，所取出的為編碼後的錯誤修正碼，因 此在數據使用前必須先解碼錯誤修正碼，以還原為原始數據。圖1為錯誤修正碼的習知解 碼方法100的流程圖。首先，解碼器接收一錯誤修正碼(步驟102)。接著，解碼器依據該 錯誤修正碼的檢查碼(parity)計算多個症狀碼(syndrome)(步驟104)。接著，解碼器檢 查是否該等症狀碼皆為零(步驟106)。若該等症狀碼為零，表示錯誤修正碼沒有發生錯 誤，因此不需進一步的修正。反之，若該等症狀碼有其中之一不為零，表示錯誤修正碼有錯 誤發生，因此必須對錯誤修正碼進行修正。首先，解碼器依據該等症狀碼計算一錯誤多項 式(error-location polynomial)的多個係數(步驟108)。接著，解碼器執行一秦氏搜尋 (Chien search)以找出該錯誤多項式的根(步驟110)。由於該錯誤多項式的根指示錯誤 修正碼中發生錯誤的位的位置，因此解碼器便可依據該錯誤多項式的根修正該錯誤修正碼 (步驟112)，而得到無錯誤的錯誤修正碼，亦即得到正確的數據。然而，當解碼器於步驟108計算錯誤多項式的係數時，會耗費許多時間。同樣的， 當解碼器於步驟110進行秦氏搜尋以找出錯誤多項式的根時，亦會耗費許多時間。於習知 的解碼方法100中，只要錯誤修正碼的多個症狀碼其中之一不為零便表示有錯誤發生，因 此必須執行步驟108與步驟110以便修正錯誤，也因而造成系統的解碼時間的延遲。於錯 誤修正碼的多個症狀碼不為零時，若能在部分情況中以其它方式修正錯誤修正碼，進而避 免於步驟108中計算錯誤多項式的係數以及於步驟110中進行秦氏搜尋以找出錯誤多項式 的根，則可大大的減少所需的解碼時間，而增進解碼器的效能。因此，需要一種可減少錯誤 修正碼的解碼時間的編碼及解碼方法。

發明內容
本發明所要解決的技術問題在於針對現有技術的上述缺陷，提供一種錯誤修正碼 的編碼及解碼方法以及編碼解碼器。
5
本發明解決其技術問題所採用的技術方案之一是構造一種錯誤修正碼的編 碼及解碼方法，其包括下列步驟接收一原始數據；將該原始數據分割為多個區段數據； 依據一第一產生多項式(generator polynomial)分別產生該等區段數據之短檢查碼 (short parity)；附加該等短檢查碼於該等區段數據之後，以分別產生多個短碼字(short codeword)；結合該等短碼字以得到一編碼數據；依據一第二產生多項式(generator polynomial)以產生該編碼數據之長檢查碼(long parity)，其中該第一產生多項式為該第 二產生多項式之至少一個最小多項式(minimumpolynomial)的函式；附加該長檢查碼於該 編碼數據之後，以產生該錯誤修正碼之一長碼字(long codeword) 0本發明所述的錯誤修正碼的編碼及解碼方法，其中該第一產生多項式為該第二產 生多項式的至少一個最小多項式的最小公倍式。本發明所述的錯誤修正碼的編碼及解碼方法，更包括儲存該長碼字於一儲存媒體 中。本發明所述的錯誤修正碼的編碼及解碼方法，更包括自一儲存媒體讀出該長碼字；自該長碼字取出其所包含的該等短碼字；依據該等 短碼字的該等短檢查碼計算該等短碼字的多個短症狀碼；檢查是否該等短症狀碼皆為零； 以及當該等短症狀碼其中的一至數個非零短症狀碼不為零時，利用該等非零短症狀碼更正 對應的該等短碼字。本發明所述的錯誤修正碼的編碼及解碼方法，更包括當該等短症狀碼計算完畢後，依據該長碼字的該長檢查碼計算該長碼字的一長症 狀碼；檢查是否該長症狀碼為零；當該長症狀碼不為零時，檢查是否該等非零短症狀碼均 可正確更正對應的該等短碼字；以及當該等非零短症狀碼均可正確更正對應的該等短碼字 時，利用該等非零短症狀碼更正該長症狀碼，以得一更正後長症狀碼。本發明所述的錯誤修正碼的編碼及解碼方法，更包括當該長症狀碼不為零，且該等非零短症狀碼的部分無法正確更正對應的該等短碼 字時，利用該長症狀碼對無法正確更正的該等短碼字進行修正。本發明所述的錯誤修正碼的編碼及解碼方法，其中該長碼字及該等短碼字為BCH 碼或RS碼。本發明解決其技術問題所採用的技術方案之二是構造一種錯誤修正碼的編 碼解碼器，其包括一錯誤修正碼編碼器以及一錯誤修正碼解碼器；該錯誤修正碼編碼 器接收一原始數據，將該原始數據分割為多個區段數據，產生該等區段數據之短檢查碼 (short parity)，附加該等短檢查碼於該等區段數據之後以分別產生多個短碼字(short codeword)，結合該等短碼字以得到一編碼數據，產生該編碼數據之長檢查碼(long parity)，以及附加該長檢查碼於該編碼數據之後以產生一長碼字(long codeword)，以供 儲存於一儲存媒體；該錯誤修正碼解碼器自該儲存媒體讀出該長碼字，自該長碼字取出其 所包含的該等短碼字，依據該等短碼字的該等短檢查碼計算該等短碼字的多個短症狀碼 (short syndrome)，檢查是否該等短症狀碼皆為零，以及當該等短症狀碼其中之一至數個 非零短症狀碼不為零時，利用該等非零短症狀碼更正對應之該等短碼字。本發明所述的錯誤修正碼的編碼解碼器，其中該錯誤修正碼編碼器依據一第一產 生多項式以產生該等區段數據的該等短檢查碼，並依據一第二產生多項式以產生該編碼數據的該長檢查碼，其中該第一產生多項式為該第二產生多項式的至少一個最小多項式的函 式。本發明所述的錯誤修正碼的編碼解碼器，其中該第一產生多項式為該第二產生多 項式的至少一個最小多項式的最小公倍式。本發明所述的錯誤修正碼的編碼解碼器，其中該錯誤修正碼編碼器包括一短碼字編碼器，依據該第一產生多項式以產生該等區段數據的該等短檢查碼； 一第一添附器，附加該等短檢查碼於該等區段數據之後以分別產生該等短碼字；一長碼字 編碼器，結合該等短碼字以得到該編碼數據，並依據該第二產生多項式以產生該編碼數據 的該長檢查碼；以及一第二添附器，附加該長檢查碼於該編碼數據之後以產生該長碼字。本發明所述的錯誤修正碼的編碼解碼器，其中當該等短症狀碼計算完畢後，該錯 誤修正碼解碼器依據該長碼字的該長檢查碼計算該長碼字的一長症狀碼，檢查是否該長症 狀碼為零，當該長症狀碼不為零時檢查是否該等非零短症狀碼均可正確更正對應的該等短 碼字，當該等非零短症狀碼均可正確更正對應的該等短碼字時，利用該等非零短症狀碼更 正該長症狀碼以得一更正後長症狀碼。本發明所述的錯誤修正碼的編碼解碼器，其中當該長症狀碼不為零，且該等非零 短症狀碼的部分無法正確更正對應的該等短碼字時，該錯誤修正碼解碼器利用該長症狀碼 對無法正確更正的該等短碼字進行修正。本發明所述的錯誤修正碼的編碼解碼器，其中該錯誤修正碼解碼器包括一症狀碼計算模塊，依據該等短碼字的該等短檢查碼計算該等短碼字的該等短症 狀碼，並依據該長碼字的該長檢查碼計算該長碼字的該等長症狀碼；一控制電路，檢查是否該等短症狀碼皆為零，當該等短症狀碼其中的該等非零短 症狀碼不為零時利用該等非零短症狀碼更正對應的該等短碼字，檢查是否該長症狀碼為 零，當該長症狀碼不為零時檢查是否該等非零短症狀碼均可正確更正對應的該等短碼字， 以及當該等非零短症狀碼均可正確更正對應的該等短碼字時利用該等非零短症狀碼更正 該長症狀碼。本發明所述的錯誤修正碼的編碼解碼器，其中該長碼字及該等短碼字為BCH碼或 RS碼。本發明解決其技術問題所採用的技術方案之三是構造一種錯誤修正碼的解碼方 法，其包括下列步驟接收該錯誤修正碼之一長碼字(long codeword)，其中該長碼字包括 多個短碼字(short codeword)及一長檢查碼(long parity)，每一該等短碼字均包括一短 檢查碼(short parity)；自該長碼字取出其所包含的該等短碼字；依據該等短碼字的該等 短檢查碼計算該等短碼字的多個短症狀碼(short syndrome)；檢查是否該等短症狀碼皆為 零；當該等短症狀碼其中之一至數個非零短症狀碼不為零時，利用該等非零短症狀碼更正 對應之該等短碼字；當該等短症狀碼計算完畢後，依據該長碼字的該長檢查碼計算該長碼 字的一長症狀碼(long syndrome)；檢查是否該長症狀碼為零；當該長症狀碼不為零時，檢 查是否該等非零短症狀碼均可正確更正對應之該等短碼字；當該等非零短症狀碼均可正確 更正對應之該等短碼字時，利用該等非零短症狀碼更正該長症狀碼，以得一更正後長症狀 碼。本發明所述的錯誤修正碼的解碼方法，更包括
當該長症狀碼不為零，且該等非零短症狀碼的部分無法正確更正對應的該等短碼 字時，利用該長症狀碼對無法正確更正的該等短碼字進行修正。本發明所述的錯誤修正碼的解碼方法，其中該等短碼字的該等短檢查碼依據一第 一產生多項式所產生，該長碼字的該長檢查碼依據一第二產生多項式所產生，其中該第一 產生多項式為該第二產生多項式的至少一個最小多項式的函式。本發明所述的錯誤修正碼的解碼方法，其中該第一產生多項式為該第二產生多項 式的至少一個最小多項式的最小公倍式。本發明所述的錯誤修正碼的解碼方法，其中該長碼字及該等短碼字為BCH碼或RS碼。實施本發明的技術方案，具有以下有益效果減少了錯誤修正碼的解碼時間，降低 了誤判的機率，增進了解碼器的效能。


下面將結合附圖及實施例對本發明作進一步說明，附圖中圖1是錯誤修正碼的習知解碼方法的流程圖；圖2是本發明的數據儲存系統的區塊圖；圖3A是本發明的錯誤修正碼編碼器的區塊圖；圖3B是本發明的錯誤修正碼的編碼方法的流程圖；圖4是本發明所產生的一長碼字的示意圖；圖5是本發明的編碼器的電路圖，該編碼器可為圖3A的短碼字編碼器或長碼字編 碼器；圖6是本發明的錯誤修正碼解碼器的區塊圖；圖7是本發明的症狀碼計算模塊的電路圖；圖8是本發明的錯誤修正碼的解碼方法的流程圖。圖中，202是主機；204是數據儲存裝置；212是控制器；214是儲存媒體；222是錯 誤修正碼編碼器；224是錯誤修正碼解碼器；300是錯誤修正碼編碼器；302是短碼字編碼
器；304是第一添附器；306是長碼字編碼器；308是第二添附器從是長碼字；CS1、CS2.....
Csn是短碼字辦、D2.....Dn是區段數據；PS^ PS2.....PSn是短檢查碼孔是長檢查碼；500
是短碼字編碼器或長碼字編碼器；530，511-51N是緩衝器；501-50N是加法器；521-52N是 乘法器；600是錯誤修正碼解碼器；602是症狀碼計算模塊；604是錯誤多項式計算模塊；
606是秦氏搜尋模塊；608是控制電路；700是症狀碼計算模塊；701、702.....70K是症狀碼
產生器；731-73K是加法器；721-72K是乘法器；711-71K是緩衝器。
具體實施例方式圖2是本發明的數據儲存系統200的區塊圖。於一實施例中，數據儲存系統200 包括一主機202以及一數據儲存裝置204。該數據儲存裝置204包括一控制器212及一儲 存媒體214。於一實施例中，控制器212包括一錯誤修正碼編碼器222以及一錯誤修正碼 解碼器224。當主機202欲儲存數據D1入數據儲存裝置204時，控制器212的錯誤修正碼 編碼器222先將數據D1編碼為錯誤修正碼C1,控制器212再將錯誤修正碼C1儲存於儲存媒
8體214。當主機202自數據儲存裝置204讀取數據D2時，控制器212先自儲存媒體214讀 取包含數據D2的錯誤修正碼C2，再由控制器212的錯誤修正碼解碼器224將錯誤修正碼C2 解碼為數據D2,最後控制器212再將數據D2傳送至主機202。於一實施例中，數據儲存裝 置204為一記憶卡，儲存媒體214為一快閃記憶體，而錯誤修正碼C1與C2為BCH碼。於另一實施 例中，數據儲存裝置204為一光碟機，儲存媒體214為一光碟片，而錯誤修正碼C1與C2為RS 碼。請注意到，儲存裝置與錯誤修正碼的類型並非本發明的限制，熟悉此項技藝者在本發明 的實施例的教導下當可將其應用至任何類型的儲存裝置與錯誤修正碼。圖3A是本發明的錯誤修正碼編碼器300的區塊圖。於一實施例中，錯誤修正碼編 碼器300包括短碼字編碼器302、第一添附器304、長碼字編碼器306、以及第二添附器308。 圖3B是本發明的錯誤修正碼的編碼方法350的流程圖。圖3A的錯誤修正碼編碼器300依 據圖3B的編碼方法350將原始數據D編碼為錯誤修正碼的一長碼字Q。首先，錯誤修正碼 編碼器300接收一原始數據D (步驟352)。接著，錯誤修正碼編碼器300將該原始數據D分 割為多個區段數據(步驟354)。當短碼字編碼器302收到該等區段數據後，短碼字編碼器 302接著依據一第一產生多項式(generator polynomial)依序產生該等區段數據的短檢 查碼(short parity) Ps (步驟 356)。接著，第一添附器304附加該等短檢查碼Ps於該等區段數據之後，以分別產生多 個短碼字(short codeword) Cs (步驟358)。長碼字編碼器306接著結合該等短碼字Ps以 得到一編碼數據(步驟360)，並依據一第二產生多項式(generator polynomial)以產生 該編碼數據的長檢查碼(long parity)Pl(步驟362)。最後，第二添附器308附加該長檢查 碼於該編碼數據之後，以產生該錯誤修正碼的一長碼字(long codeword) CJ步驟364)。 其中，短碼字編碼器302的第一產生多項式為長碼字編碼器306的第二產生多項式的至少 一個最小多項式(minimum polynomial)的函式。於一實施例中，該第一產生多項式為該 第二產生多項式的至少一個最小多項式的最小公倍式(least common multiple，LCM)。舉 例來說，假設長碼字編碼器306對應的第二產生多項式g(x)為多個最小多項式Ψ^χ)、
Ψ2(χ).....Ψ「χ)的最小公倍式(W1(X)XW2U)X... XWk(x)}。於一實施例中，短碼
字編碼器302對應的第一產生多項式g』 (χ)為最小多項式Ψ^χ)。於另一實施例中，短碼 字編碼器302對應的第一產生多項式g』 (χ)為最小多項式W1(X)與Ψ2(χ)的最小公倍式 [W1(X) X Ψ2(χ)]。圖4是本發明所產生的一長碼字Q的示意圖。長碼字Q由N個短碼字CS1、CS2.....
Csn及一個長檢查碼&所組成。每一個短碼字CS1、Cs2.....Csn包括一區段數據及一短檢查
碼。舉例來說，短碼字Csi由檢查碼Psi接續於相對應的區段數據D1之後而形成，短碼字Cs2 由檢查碼Ps2接續於相對應的區段數據D2之後而形成，而短碼字Csn由檢查碼Psn接續於相
對應的區段數據Dn之後而形成。原始數據被切割為多個區段數據Dp D2.....Dn,而原始數
據在經由圖3A的錯誤修正碼編碼器300編碼後形成圖4的長碼字Q。圖5是本發明的編碼器500的電路圖，該編碼器500可為圖3A中的短碼字編碼器 302或長碼字編碼器306。假設編碼器500依據一產生多項式g(x)將數據Da轉換為檢查碼
P，而產生多項式g(x)的一次項係數為^、二次項係數為&.....N次項係數為&。編碼器
500包括加法器540、乘法器521 52N、加法器501 50N、以及緩衝器511 51N及530。 首先，數據Da的位依次被送至加法器540。加法器540依次將數據Da的位與緩衝器51N儲
9存的數據位Ddn相加而得到數據Db。乘法器521、522.....52N接著分別將數據Db與產生多
項式g(x)的係數gl、&.....gN相乘而分別得到數據Dci、Dc2.....Dcn。數據Db在經過緩衝
器530的儲存後，依次由加法器501、502.....50N分別與數據Dei、De2.....Dcm相加，而得到
數據Ddn。最後，緩衝器51N儲存數據Ddn後，將數據Ddn輸出為檢查碼P。圖6是本發明的錯誤修正碼解碼器600的區塊圖。於一實施例中，錯誤修正碼解 碼器600包括症狀碼計算模塊602、錯誤多項式計算模塊604、秦氏搜尋模塊606、以及控制 電路608。當錯誤修正碼解碼器600收到錯誤修正碼的一長碼字時，錯誤修正碼解碼器600 自該長碼字取出其所包含的多個短碼字。首先，症狀碼計算模塊602依據該等短碼字的短 檢查碼計算該等短碼字的多個短症狀碼(short syndrome) Sla, Slb，...，Sin，並依據該長碼 字的該長檢查碼計算該長碼字的多個長症狀碼(long Syn(Irome)SljS2,.. .，SK。錯誤多項式 計算模塊604用以依據長碼字的長症狀碼S1, S2，. . .，Sk計算該長碼字的錯誤多項式(error location polynomial)的係數。秦氏搜尋模塊606用以找出該錯誤多項式的多個根，以供 修正錯誤修正碼的長碼字。此外，當短碼字的短症狀碼Sla，Slb，. . .，Sin不為0時，錯誤多項 式計算模塊604亦會依據不為零的短症狀碼計算短碼字的錯誤多項式，並由秦氏搜尋模塊 606進行秦氏搜尋找出短碼字的錯誤多項式的根，以立即更正短碼字發生的錯誤。與圖1的 習知方法100類似，控制電路608檢查長症狀碼S1, S2,...，Sk是否為零，並於該等長症狀碼 S1, S2, ...，Sk皆為零時停止錯誤多項式計算模塊604對錯誤多項式的係數的計算，並停止 該秦氏搜尋模塊606對錯誤多項式的根的搜尋。然而，控制電路608尚有其它功能，可減少 解碼長碼字所需的時間，而提升錯誤修正碼解碼器600的效能。此部分功能將以圖8說明。於一實施例中，由於用以編碼短碼字的第一產生多項式是用以編碼長碼字的第二 產生多項式的最小多項式的函式，因此可利用同一組症狀碼計算模塊602計算長碼字的症 狀碼與短碼字的症狀碼。圖7是本發明的症狀碼計算模塊700的電路圖。症狀碼計算模塊
700包括多個症狀碼產生器701,702.....70K,該等症狀碼產生器701,702.....70K分別
產生長症狀碼的長症狀碼SpS2.....SK。症狀碼產生器701亦產生多個短碼字的短症狀碼
Sla，Slb，...，Sino於一實施例中，長碼字的數據位D被依次遞送至症狀碼產生器702.....
70K,當長碼字的數據位D被處理完畢，症狀碼產生器702.....70K便產生長碼字的長症狀
碼&.....SK。同時，短碼字的數據位D亦依序被遞送至症狀碼產生器701。每當一短碼字
的數據位D被處理完畢，症狀碼產生器701便產生該短碼字相應的一短症狀碼。例如，當區 段數據D1與短檢查碼Psi被輸入至症狀碼產生器701時，症狀碼產生器701便產生短碼字 Csi的短症狀碼；當區段數據D2與短檢查碼Ps2被輸入至症狀碼產生器701時，症狀碼產生器 701便產生短碼字Cs2的短症狀碼。由於長碼字由多個短碼字所組成，當症狀碼產生器701 將長碼字所包括的多個短碼字的數據位D均處理完畢，症狀碼產生器701便產生長碼字的 長症狀碼Sp圖7中的每一症狀碼產生器701、702.....70K包括一加法器、一乘法器、以及一緩
衝器。舉例來說，於第一症狀碼產生器701中，緩衝器711儲存數據D1並將其輸出。加法 器731將長碼字的數據位D與緩衝器711輸出的數據D1相加後得到一第一症狀碼Sp乘法 器721將係數α與症狀碼S1相乘後得到數據D1，而新得到的數據D1再被送至緩衝器711 中儲存。症狀碼產生器701的係數α為長碼字編碼器的產生多項式與短碼字編碼器的產 生多項式的共同根，而其它症狀碼產生器702.....70Κ的係數分別為α2.....α κ。而α、α2.....α κ為長碼字編碼器的產生多項式的根。圖8是本發明的錯誤修正碼的解碼方法800的流程圖。圖6的錯誤修正碼解碼 器600依據方法800進行錯誤修正碼的解碼。首先，錯誤修正碼解碼器600接收一長碼字 (步驟802)。接著，症狀碼計算模塊602循序計算該長碼字中一短碼字的短症狀碼(步驟 804)，例如，錯誤修正碼解碼器600首先對長碼字Q中第一個短碼字Csi進行計算。此時控 制電路608檢查是否計算得到的短症狀碼為零(步驟806)。當短症狀碼為零時，表示短碼 字正確無誤，因此症狀碼計算模塊602繼續計算該長碼字中其它的短碼字的短症狀碼(步
驟804)，例如，接著計算第二個短碼字Cs2、第三個短碼字Cs3......直到該長碼字中所有短
碼字均處理完畢為止(步驟812)。當短症狀碼不為零時，表示短碼字有錯誤，因此控制電 路608利用非零短症狀碼更正該短碼字並紀錄更正結果(步驟808)，再由症狀碼計算模塊 602繼續計算該長碼字中的短碼字的短症狀碼(步驟804)，直到該長碼字中所有短碼字均 處理完畢為止(步驟810)。接著，症狀碼計算模塊602計算長碼字的長症狀碼(步驟814)。若長症狀碼為零 (步驟816)，表示長碼字正確無誤，則該長碼字的解碼結束。若長症狀碼不為零(步驟816)， 表示長碼字有錯誤。此時控制電路608繼續檢查是否所有非零短症狀碼均可正確更正短碼 字(步驟818)。若所有非零短症狀碼均可正確更正短碼字(步驟818)，則控制電路608利 用非零短症狀碼更正長症狀碼(步驟820)，例如，若第四短碼字的Cs4的短症狀碼並非全為 零，則利用該非零短症狀碼去更正非零長症狀碼中相對應的位置。若更正後長症狀碼為零 (步驟822)，表示該些錯誤已藉由短症狀碼更正成功，則可將該些利用短碼字更正的更正 結果回復予主機，無需再利用長症狀碼進行更正整個長碼字，可大幅節省時間。若更正後長 症狀碼不為零(步驟822)，或部分非零短症狀碼無法正確更正短碼字(步驟818)，則控制 電路608利用原本的長症狀碼針對無法正確更正的短碼字進行修正(步驟824)，以得到正 確的長碼字，而該長碼字的解碼結束。若當所有短症狀碼為零時即認為該長碼字正確無誤，可能會發生誤判。因為短症 狀碼的更正能力較低，可能僅有一個或兩個位的更正能力，而當該短碼字發生的錯誤超過 該短症狀碼的更正能力時，例如出現8個位的錯誤，該短症狀碼亦可能被計算為零。因此需 要利用更正能力較強的長症狀碼再度進行檢驗。長症狀碼的更正能力較高，可能有24個位 的更正能力。故若某短碼字中出現8個位的錯誤，仍可通過長症狀碼發現，並進行後續更 正。發生誤判的機率就可降低。雖然本發明已以較佳實施例揭露如上，然其並非用以限定本發明，任何熟習此項 技術者，在不脫離本發明的精神和範圍內，當可作些許的更動與潤飾，因此本發明的保護範 圍當視後附的申請專利範圍所界定者為準。
權利要求
一種錯誤修正碼的編碼及解碼方法，其特徵在於，包括下列步驟接收一原始數據；將該原始數據分割為多個區段數據；依據一第一產生多項式分別產生該等區段數據的短檢查碼；附加該等短檢查碼於該等區段數據之後，以分別產生多個短碼字；結合該等短碼字以得到一編碼數據；依據一第二產生多項式以產生該編碼數據的長檢查碼，其中該第一產生多項式為該第二產生多項式的至少一個最小多項式的函式；附加該長檢查碼於該編碼數據之後，以產生該錯誤修正碼的一長碼字。
2.根據權利要求1所述的錯誤修正碼的編碼及解碼方法，其特徵在於，其中該第一產 生多項式為該第二產生多項式的至少一個最小多項式的最小公倍式。
3.根據權利要求1所述的錯誤修正碼的編碼及解碼方法，其特徵在於，更包括儲存該 長碼字於一儲存媒體中。
4.根據權利要求1所述的錯誤修正碼的編碼及解碼方法，其特徵在於，更包括 自一儲存媒體讀出該長碼字；自該長碼字取出其所包含的該等短碼字；依據該等短碼字的該等短檢查碼計算該等短碼字的多個短症狀碼； 檢查是否該等短症狀碼皆為零；以及當該等短症狀碼其中的一至數個非零短症狀碼不為零時，利用該等非零短症狀碼更正 對應的該等短碼字。
5.根據權利要求4所述的錯誤修正碼的編碼及解碼方法，其特徵在於，更包括 當該等短症狀碼計算完畢後，依據該長碼字的該長檢查碼計算該長碼字的一長症狀碼；檢查是否該長症狀碼為零；當該長症狀碼不為零時，檢查是否該等非零短症狀碼均可正確更正對應的該等短碼 字；以及當該等非零短症狀碼均可正確更正對應的該等短碼字時，利用該等非零短症狀碼更正 該長症狀碼，以得一更正後長症狀碼。
6.根據權利要求5所述的錯誤修正碼的編碼及解碼方法，其特徵在於，更包括 當該長症狀碼不為零，且該等非零短症狀碼的部分無法正確更正對應的該等短碼字時，利用該長症狀碼對無法正確更正的該等短碼字進行修正。
7.根據權利要求1所述的錯誤修正碼的編碼及解碼方法，其特徵在於，其中該長碼字 及該等短碼字為BCH碼或RS碼。
8.一種錯誤修正碼的編碼解碼器，其特徵在於，包括一錯誤修正碼編碼器，接收一原始數據，將該原始數據分割為多個區段數據，產生該等 區段數據的短檢查碼，附加該等短檢查碼於該等區段數據之後以分別產生多個短碼字，結 合該等短碼字以得到一編碼數據，產生該編碼數據的長檢查碼，以及附加該長檢查碼於該 編碼數據之後以產生一長碼字以供儲存於一儲存媒體；以及一錯誤修正碼解碼器，自該儲存媒體讀出該長碼字，自該長碼字取出其所包含的該等短碼字，依據該等短碼字的該等短檢查碼計算該等短碼字的多個短症狀碼，檢查是否該等 短症狀碼皆為零，以及當該等短症狀碼其中的一至數個非零短症狀碼不為零時，利用該等 非零短症狀碼更正對應的該等短碼字。
9.根據權利要求8所述的錯誤修正碼的編碼解碼器，其特徵在於，其中該錯誤修正碼 編碼器依據一第一產生多項式以產生該等區段數據的該等短檢查碼，並依據一第二產生多 項式以產生該編碼數據的該長檢查碼，其中該第一產生多項式為該第二產生多項式的至少 一個最小多項式的函式。
10.根據權利要求9所述的錯誤修正碼的編碼解碼器，其特徵在於，其中該第一產生多 項式為該第二產生多項式的至少一個最小多項式的最小公倍式。
11.根據權利要求9所述的錯誤修正碼的編碼解碼器，其特徵在於，其中該錯誤修正碼 編碼器包括一短碼字編碼器，依據該第一產生多項式以產生該等區段數據的該等短檢查碼；一第一添附器，附加該等短檢查碼於該等區段數據之後以分別產生該等短碼字；一長碼字編碼器，結合該等短碼字以得到該編碼數據，並依據該第二產生多項式以產 生該編碼數據的該長檢查碼；以及一第二添附器，附加該長檢查碼於該編碼數據之後以產生該長碼字。
12.根據權利要求8所述的錯誤修正碼的編碼解碼器，其特徵在於，其中當該等短症狀 碼計算完畢後，該錯誤修正碼解碼器依據該長碼字的該長檢查碼計算該長碼字的一長症狀 碼，檢查是否該長症狀碼為零，當該長症狀碼不為零時檢查是否該等非零短症狀碼均可正 確更正對應的該等短碼字，當該等非零短症狀碼均可正確更正對應的該等短碼字時，利用 該等非零短症狀碼更正該長症狀碼以得一更正後長症狀碼。
13.根據權利要求8所述的錯誤修正碼的編碼解碼器，其特徵在於，其中當該長症狀碼 不為零，且該等非零短症狀碼的部分無法正確更正對應的該等短碼字時，該錯誤修正碼解 碼器利用該長症狀碼對無法正確更正的該等短碼字進行修正。
14.根據權利要求12所述的錯誤修正碼的編碼解碼器，其特徵在於，其中該錯誤修正 碼解碼器包括一症狀碼計算模塊，依據該等短碼字的該等短檢查碼計算該等短碼字的該等短症狀 碼，並依據該長碼字的該長檢查碼計算該長碼字的該等長症狀碼；一控制電路，檢查是否該等短症狀碼皆為零，當該等短症狀碼其中的該等非零短症狀 碼不為零時利用該等非零短症狀碼更正對應的該等短碼字，檢查是否該長症狀碼為零，當 該長症狀碼不為零時檢查是否該等非零短症狀碼均可正確更正對應的該等短碼字，以及當 該等非零短症狀碼均可正確更正對應的該等短碼字時利用該等非零短症狀碼更正該長症 狀碼。
15.根據權利要求8所述的錯誤修正碼的編碼解碼器，其特徵在於，其中該長碼字及該 等短碼字為BCH碼或RS碼。
16.一種錯誤修正碼的解碼方法，其特徵在於，包括下列步驟接收該錯誤修正碼的一長碼字，其中該長碼字包括多個短碼字及一長檢查碼，每一該 等短碼字均包括一短檢查碼；自該長碼字取出其所包含的該等短碼字；依據該等短碼字的該等短檢查碼計算該等短碼字的多個短症狀碼； 檢查是否該等短症狀碼皆為零；當該等短症狀碼其中的一至數個非零短症狀碼不為零時，利用該等非零短症狀碼更正 對應的該等短碼字；當該等短症狀碼計算完畢後，依據該長碼字的該長檢查碼計算該長碼字的一長症狀碼；檢查是否該長症狀碼為零；當該長症狀碼不為零時，檢查是否該等非零短症狀碼均可正確更正對應的該等短碼 字；以及當該等非零短症狀碼均可正確更正對應的該等短碼字時，利用該等非零短症狀碼更正 該長症狀碼，以得一更正後長症狀碼。
17.根據權利要求16所述的錯誤修正碼的解碼方法，其特徵在於，更包括當該長症狀碼不為零，且該等非零短症狀碼的部分無法正確更正對應的該等短碼字 時，利用該長症狀碼對無法正確更正的該等短碼字進行修正。
18.根據權利要求16所述的錯誤修正碼的解碼方法，其特徵在於，其中該等短碼字的 該等短檢查碼依據一第一產生多項式所產生，該長碼字的該長檢查碼依據一第二產生多項 式所產生，其中該第一產生多項式為該第二產生多項式的至少一個最小多項式的函式。
19.根據權利要求16所述的錯誤修正碼的解碼方法，其特徵在於，其中該第一產生多 項式為該第二產生多項式的至少一個最小多項式的最小公倍式。
20.根據權利要求16所述的錯誤修正碼的解碼方法，其特徵在於，其中該長碼字及該 等短碼字為BCH碼或RS碼。
全文摘要
本發明涉及一種錯誤修正碼的編碼及解碼方法，其包括接收一原始數據；將該原始數據分割為多個區段數據；依據一第一產生多項式分別產生該等區段數據之短檢查碼；附加該等短檢查碼於該等區段數據之後，以分別產生多個短碼字；結合該等短碼字以得到一編碼數據；依據一第二產生多項式以產生該編碼數據之長檢查碼，其中該第一產生多項式為該第二產生多項式之至少一個最小多項式的函式；附加該長檢查碼於該編碼數據之後，以產生該錯誤修正碼之一長碼字。本發明還涉及一種錯誤修正碼的編碼解碼器，其包括一錯誤修正碼編碼器和一錯誤修正碼解碼器。本發明還涉及一種錯誤修正碼的解碼方法。本發明減少了錯誤修正碼的解碼時間，增進了解碼器的效能。
文檔編號H03M13/00GK101938280SQ20091016802
公開日2011年1月5日 申請日期2009年8月10日 優先權日2009年7月1日
發明者楊宗傑 申請人:慧帝科技(深圳)有限公司;慧榮科技股份有限公司