[發明專利]糾錯碼的解碼方法及電路

有效

• 申請號: 200910132840.2
• 申請日: 2009-04-16
• 公開（公告）號: CN101795140A
• 公開（公告）日: 2010-08-04
• 發明（設計）人: 楊宗杰
• 申請（專利權）人: 慧國(上海)軟件科技有限公司;慧榮科技股份有限公司
• 主分類號: H03M13/00
• 分類號: H03M13/00
• 代理公司: 上海專利商標事務所有限公司 31100
• 代理人: 駱希聰

技術領域

本發明是有關于糾錯碼，特別是有關于糾錯碼的解碼方法及電路。

背景技術

糾錯碼(error?correction?code)是用于修正資料的錯誤。通信系統所傳輸的資 料于傳輸端傳送前經常事先被編碼為糾錯碼。當接收端收到糾錯碼資料時，即 使資料于傳輸過程中遭受損毀而產生隨機錯誤，也可借解碼糾錯碼而回復正確 的資料。同樣的，資料儲存系統亦經常在儲存資料前將所儲存的資料編碼為糾 錯碼。當資料于儲存過程中遭受損毀而產生隨機錯誤時，亦可借解碼糾錯碼而 回復正確的資料。常見的糾錯碼如BCH碼(Bose，Ray-Chaudhuri，and Hocquenghem?code)及RS碼(Reed-Solomon?code)。BCH碼常用于閃存資料的儲 存，而RS碼常用于光碟資料的儲存。

當資料儲存系統欲取出其所儲存的資料時，所取出的為編碼后的糾錯碼， 因此在資料使用前必須先將糾錯碼解碼，以還原為原始資料。圖1為解碼糾錯 碼的現有方法100的流程圖。此處以BCH碼為糾錯碼的示例以進行說明。首 先，解碼電路接收一BCH碼(步驟102)。接著，解碼電路依據該BCH碼計算 一癥狀碼(syndrome)(步驟104)。接著，解碼電路檢查是否該癥狀碼為零(步驟 106)。若癥狀碼為零，表示該BCH碼沒有發生錯誤，因此不需進一步的修正。 反之，若癥狀碼不為零，表示BCH碼有錯誤發生，因此必須對BCH碼進行修 正。

首先，解碼電路依據該癥狀碼依次計算一錯誤多項式(error-location polynomial)的多個系數(步驟108)。該錯誤多項式的系數的計算是以回圈的方 式，逐次產生由低次系數直到高次系數。因此，必須持續回圈執行步驟108到 產生該錯誤多項式的最高次系數為止，才將系數計算完畢，而得到完整的錯誤 多項式(步驟110)。接著，解碼電路執行一秦氏搜尋(Chien?search)以找出該錯誤 多項式的根(步驟112)。該錯誤多項式的根便指示BCH碼中發生錯誤的位元的 位置，因此解碼電路便可依據該錯誤多項式的根修正該BCH碼(步驟114)，而 得到無錯誤的BCH碼。

圖2顯示現有解碼糾錯碼的時序圖。自時點t_a開始，解碼電路首先于時段 T₁中計算糾錯碼的癥狀碼(步驟202)。自時點t_b開始，解碼電路接著于時段T₂中依據癥狀碼計算糾錯碼的錯誤多項式的系數(步驟204)。自時點t_c開始，解碼 電路接著于時段T₃中進行秦氏搜尋以找出錯誤多項式的根，而得到糾錯碼的錯 誤位元的位置(步驟206)。因此，解碼糾錯碼的整個時程需要(T₁+T₂+T₃)的時間。

由于解碼糾錯碼是通訊系統的接收端、及光盤機或閃存讀取資料的必要步 驟，因此若加速糾錯碼的解碼會大大提升通訊系統及如光盤機或閃存的資料儲 存系統的效能。然而，由于資料錯誤是隨機發生，圖2的步驟202、204、206 的需要時間T₁、T₂、T₃很難大幅縮短。因此，需要一種加速糾錯碼的解碼的方 法，以提升對糾錯碼進行解碼的通訊系統及資料儲存系統的效能。

發明內容

有鑒于此，本發明的目的在于提供一種糾錯碼(error?correction?code)的解碼 方法，以解決現有技術存在的問題。首先，依據該糾錯碼計算一癥狀碼 (syndrome)。接著，依據該癥狀碼依序計算一錯誤多項式(error-location polynomial)的多個系數。每當計算得到這些系數中的一新產生系數時，檢查該 新產生系數是否為零。當該新產生系數為零時，依據已計算得到且次數低于該 新產生系數的多個低次項系數建立一假定錯誤多項式。接著，執行一秦氏搜尋 (Chien?search)以找出該假定錯誤多項式的根。最后，依據該假定錯誤多項式的 根修正該糾錯碼。