TW486880B - Decoding device and decoding method - Google Patents

Decoding device and decoding method Download PDF

Info

Publication number
TW486880B
TW486880B TW090107313A TW90107313A TW486880B TW 486880 B TW486880 B TW 486880B TW 090107313 A TW090107313 A TW 090107313A TW 90107313 A TW90107313 A TW 90107313A TW 486880 B TW486880 B TW 486880B
Authority
TW
Taiwan
Prior art keywords
error
data
correction
check code
polynomial
Prior art date
Application number
TW090107313A
Other languages
English (en)
Inventor
Toshihiko Fukuoka
Hiroyuki Senda
Original Assignee
Matsushita Electric Industrial Co Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Matsushita Electric Industrial Co Ltd filed Critical Matsushita Electric Industrial Co Ltd
Application granted granted Critical
Publication of TW486880B publication Critical patent/TW486880B/zh

Links

Classifications

    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/13—Linear codes
    • H03M13/15—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes
    • H03M13/151—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes using error location or error correction polynomials
    • H03M13/1555—Pipelined decoder implementations
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/13—Linear codes
    • H03M13/15—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/13—Linear codes
    • H03M13/15—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes
    • H03M13/151—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes using error location or error correction polynomials
    • H03M13/1525—Determination and particular use of error location polynomials
    • H03M13/1535—Determination and particular use of error location polynomials using the Euclid algorithm
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/37—Decoding methods or techniques, not specific to the particular type of coding provided for in groups H03M13/03 - H03M13/35
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/13—Linear codes
    • H03M13/15—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes
    • H03M13/151—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes using error location or error correction polynomials
    • H03M13/1515—Reed-Solomon codes

Landscapes

  • Physics & Mathematics (AREA)
  • Mathematical Physics (AREA)
  • Probability & Statistics with Applications (AREA)
  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Algebra (AREA)
  • General Physics & Mathematics (AREA)
  • Pure & Applied Mathematics (AREA)
  • Error Detection And Correction (AREA)
  • Detection And Prevention Of Errors In Transmission (AREA)
  • Detection And Correction Of Errors (AREA)

Description

【發明所屬技術領域】 本么明係有關於一種進行擴張里德所羅門 (Reed-S〇l〇mon)碼之多重錯誤訂正之解碼技術。 【習知技術】 記憶裝置之資料之記憶、在高速通 可實現多重錯誤訂正之碼上廣為使 為了在各種大容量 訊之資料之傳送等，在 用里德所羅門碼。 a 碼 號 問i ^原始多項式為W(Z)、W(Z) = 〇之根為α時，里德所薄 ’糸^ "亥根為原始元素之伽羅瓦域（Ga 1 〇 i s F i e 1 d )上之 :塔係貝料段錯誤訂正碼之一。纟此，設伽羅瓦域GF ( y ) 原始70素為α，考慮在該伽羅瓦域GF(2〇之元素、 "、Γ、aexp(2m~2)之中具有根之里德所羅門碼。在該 係，長n=2m — 1，設m位元為1個處理單位，即}個符 原資料量係n—2t符號（t係錯誤訂正數）。 里德所羅門碼之解碼按照以下之步驟進行。 (a) 計算校驗碼（Syndr〇me)。 (b) 計算錯誤評價多項式及錯誤位置多項式。 鏈上搜尋（Chain Search)計算錯誤之位置。 C d)计鼻錯誤之大小。 (e )依照錯誤之位置和錯誤 報。 Ί於特開平1 〇 -1 3 5 8 4 6號公 486880
用擴張里德所羅門碼進行錯誤訂正之規格。 門碼係碼長η大於碼之根所屬之伽羅瓦域之元廣張里德所羅 碼，在碼長n = q之情況，稱為1次擴張里德所素之個數q之 長n = q + l之情況，稱為2次擴張里德所羅門螞、、隹門碼，在碼 例如’在北美之有線電視系統，在伽 ^ ^維瓦域G ( 97、 上，採用原始多項式Ρ(χ)使用Ρ(χ)=χ7+χ3 + ι、：一夕 、 GL(x)使用 GL(x) = (x+a) (χ+α2) (χ+α3) “」母夕員式 α5)、錯誤訂正數t = 3之1次擴張里德所羅M旗 隹门碼。此外，* 該擴張里德所羅門碼，儘管係錯誤訂正翁+ Q 你 默t = 3，因母多頊 式GL (X)係5次之多項式’在計算校驗碼時兩 、 了而要和一般不同 之處理。 一般之里德所羅門碼，在設碼長η為2m之棒 “ h況，需要 在具有2™ + l個元素之伽羅瓦域GFUni)上構成碼，但是擴 張里德所羅門碼係伽羅瓦域GF(2m)上也可將碼長η延長至2ra 以上。 【發明要解決之課題】 考慮1個符號之位元數m = 7、錯誤訂正數t = 3之伽羅瓦 域GF ( 27 )上之里德所羅門碼。 一般之里德所羅門碼係在伽羅瓦域G F ( 27)之元素α 〇、 αι、···、α126之中具有根，碼長η = 127。因母多項式gl(x) 之次數係錯誤訂正數t之2倍，錯誤訂正數t = 3時，母多項 式心（乂）使用6次之多項式，可設*GL(x) = (x+a) (χ+α2) (χ+ α3) (χ+ （χ+ α5) (x+ α6) 〇
五、發明說明（3) m 27 ? #考慮擴張里德所羅Η碼， GF(2)，構成具有更長之碼1馬，在相同之伽羅瓦域 如，可考慮碼長n =丨28之擴張组馬，可進行錯誤訂正。例 誤之位置成一對—對應，萨2錯誤位置多項式之根和錯 項式求錯誤之位置。鏈上^，用鏈上搜尋解錯誤位置多 依次代入錯誤位置多項式下:糸將伽羅瓦域之全部之元素 素，作為錯誤位置多項式之，求該式子之值變成零之元 數t = 3之情況，將元素依次^之^方法。例如，在錯誤訂正 式，、求式子之值變成零時所三次式之錯誤位置多項 項式之3個根。 之元素，作為錯誤位置多 在碼字附加超過了訂正性 錯誤評價多項式和錯誤位置 h況，因未正確的導出 未正確的導出錯誤位置多項、式，或在鏈上搜尋之處理 誤。在此情況，不進行錯誤；可認為係無法訂正錯 入資料。 处理’原封不動的輸出輸 GF( 2”之。二碼，因碼長η比伽羅瓦域 一對一對應，關於鏈上搜尋需要=素^錯誤之位置不是 碼之解碼不同之處理。 赘進仃和一般之里德所羅門 碼長之ΙΥΛ7?擴張里德所羅門碼解碼。例如， 1 Η δ之擴張里德所羅 況，由資料記號122個符卢二r §、盯正數t為3之情 羅瓦域GF(27)，因利用鏈t 1己號6個符號構成。在伽 和用鏈上搜哥可訂正的只有127個符
=，以接收字128個符號之中只有冗長記號】個符號以外之 剩下之1 27個符號為對象’進行錯誤訂正。 ^ 了疋’有使用1 2 8個碼訂正碼之中之1 2 7個符號之問 ^及，對於未進行訂正處理之冗長記號1個符號也可能 …曰。吳之h況’有發生未正確的訂正之誤訂正之問題。 碥梦Ϊ Ϊ明係為解決上述之課題’其目的在於提供一種解 站、及解碼方法，在對於擴張里德所羅門碼之接收字 正】的、隹判疋疋否可訂正錯誤，在可訂正錯誤之情況得到 ^的進行訂正處理之資料，而且在無法 使得不進行錯誤訂正。 < ㈡况 【解決 為 講求之 張里德 資料； 判定有 訂正資 誤訂正 又 利範圍 產生之 料。 課題之方式】 述之課題’如申請專利範圍第1項之發明所 ;罹門二Λ解碼裝置，具備訂正處理部，對由擴 二：：構成之接收字進行錯誤訂正處理，求正 料，而在益法產Ι:;τ正資料之情況，輸出該 前之接收;;。a之訂正資料之情況，輪出錯 第iV之申:專利範圍第2項之發明’係在如申請專 乐丄項之解碼裝置，兮 ^ ^ 訂正資料有錯誤時二=產部^ 又 在如申請專利範圍 第3項之發明 係在如申請專
哪880 五、發明說明（5) ::艳圍第1項之解碼裝置，該訂正處理 二料為止重複執行該錯誤訂正處理的、產生無誤之 C之次數也無法產生無誤之訂正資料ΐ仃f誤訂 產生無誤之訂正資料。 貝枓日寸，判定無 又’如申請專利範圍第4項 一 具備： 、号x月係種解碼褒置， 校驗碼計算部，將由妒 作為輸入資料，求該輪入‘料所、准門碼構成之接收字 驗碼後，依照該輸入資料垆給杈驗碼，作為輸入資料校 否有錯誤之第—旗桿俨號又而：f出表示在該輪入資料是 ，第-訂正資料之校驗；輸=料所求得 :…身料校驗碼輸出表示在以:t=;=古依照該 弟二旗標信號； /弟叮正貝枓疋否有錯誤之 驗碼：I f多項< ·位置多項式導出部，依照該輸入資料校 馬求錯誤評價多項式及錯誤位置多項式之各次數之係 位娶而且依照自該係數求得之錯誤之評價值及對應之錯誤 置多項式之微分值求錯誤之大小； 而鍵上搜尋部’依照該係數求該錯誤位置多項式之根， 且求將該根各自代入該錯誤評價多項式後所得到之錯誤 之5平價值及將該根各自代入該評價多項式·位置多項式之 導函數所得到之錯誤位置多項式之微分值； π 以及錯誤訂正部，在該第一旗標信號表示在該輸入資 料有錯誤之情況，依照該根及對應之該錯誤之大小，將對 於該輪入資料進行錯誤訂正處理所得到之資料作為該第，
486880
五、發明說明（6) 盯正資料輸出，而在該第一旗標信號表示在該輪入次 錯誤之情況，將該輸入資料作為該第一訂正資料貝料…、 且在该第二旗標信號表示在該第一訂正資料有_誤出而 況，將對於該第一訂正資料進行復原成錯誤訂 資料之復原處理所得到之資料作為第二訂正資别之 二旗標信號表示在該第一訂正資料無錯誤二兄而 將邊弟一訂正資料作為第二訂正資料輸出。 月/ 若依據如申請專利範圍第4項之發明，因不 料杈驗碼，也求訂正資料校驗石馬， 别貝 了錯誤訂正。 』侍知疋否正確的進行 又，在如申請專 利蘇III势/1 S 4 貝 < 务明，係在如 „4項之解碼裝置，該校驗碼計 t擇器，輸入該輸入資料及 八 -訂正資料後，交互輸出該輪入；:輸出之該第 第-訂正資料，分別求該輸入；；輪：之該輸入資料及該 驗碼； 貝料才父驗碼及該訂正資料校 輪入資料校驗碼保持器，伴^ 出； 1示符该輪入資料校驗碼後輸 叮正資料校驗碼保持器 出； 保待该訂正資料校驗碼後輸 第一校驗碼零檢測器， 出之該輸入資料校驗碼 该輸入資料校驗碼保持器輸 該輸入資料無錯誤般輪^^全部為零之情況，如表示在 ’出以弟一旗標信號；而在不全為零
五、發明說明（7) 之情況，如表示在該輸入資料有錯誤般輸出該第一旗標信 號； _以及第二杈驗碼零檢測器，在該訂正資料校驗碼保持 器輸出之該訂正資料校驗碼之成分全部為零之情況，如表 不在該第一訂正資料無錯誤般輸出該第二旗標信號；而在 不全為零之情況，如表示在該第一訂正資料有錯誤般輸出 該第二旗標信號。 若依據如申請專利範圍第5項之發明，因平行的求輸 入資料校驗碼及訂正資料校驗碼後，同時輸出第一旗標信 唬及第二旗標信號’可同時得知在輸入資料及第一訂正資 料是否有錯誤。 人 利範圍 出部係 錯誤評 出的 ； 之次數 若 德互除 項式， 羅門碼 又 利範圍 德所羅 ’在如申請專利範圍第6項之發明，係在如申請專 第4項之解碼裝置，該評價多項式·位置多項式導 利用歐基里德互除運算依照該訂正資料校驗碼求該 價多項式及該錯誤位置多項式之各次數之係數後輸 在該歐基里德互除運算終了時，該錯誤位置多項式 係該錯誤評價多項式之次數以下也輸出該係數。 依^如申請專利範圍第6項之發明，因不論歐基里 ^ ^之結果，可得到錯誤評價多項式及錯誤位置多 :it誤之位置及錯誤之大小後’進行擴張里德所 石馬〇 楚在如申請專利範圍第7項之發明，係在如申請專 門4 满項> 之解碼裝置，該鏈上搜尋部將定義該擴張里 ·、、、根之伽羅瓦域之元素依次代入該錯誤位置多
486880 五、發明說明（8) __ 項式後，求該錯誤位置多項式辦 一 錯誤位置多項式之根；係該錯誤位；多項：：：里作為該 個數小於該錯誤位置多項式之次數 1 4^/、之根之 位置多項式之根。 人m兄，也輸出該錯誤 利丄在如申請專利範圍第8項之發明，係在如申&皇 利犯圍苐4項之解碼裝置’該訂正處理部具備：申h專 第一錯誤訂正器’在該第一旗桿俨 — 料有錯誤之情況，將對於該輸入資： = = ;輪入資 2之錯誤之位置表示之符號減去對應之該錯c對 誤訂正處理所得到之資料各自作為該第一訂正之錯 錯誤之情況’將該輸入資料各自作為C; 枓輸出； π 叮正資 錯誤之位置資料保持器，保持該錯誤之位 錯誤之大小資料保持器，保持該錯誤之大小2出； 以及第二錯誤訂正器’在該第二旗標传 後輪出； 丁訂正資料有錯誤之情況，將進行對於該S二該第 士和該錯誤之位置表示之符號對應之該錯誤之k貧料加 y成該錯誤訂正處理前之資料之復原處理所得至：值而 自作為該第二訂正資料輸出；而在無錯誤之、乂貝料 第一訂正資料各自作為該第二訂正資料輸出。况，將該 若依據如申請專利範圍第8項之發明， :於輸入資料之訂正處理和對於第一訂：的處理 理，可高速的處理。 ^设原處 又’在如申請專利範圍第9項之發明’係在如申請專 1 第13頁 五、發明說明C9) ϊί圍第4項之解碼裝置，更包含，料記憶部，將該輸入 屮“、呆持至該訂正處理部開始求第一訂正資料為止後輸 =L將該第一訂正資料保持至該訂正處理部開始求第了訂 貪料為止後輸出。 若依據如申請專利範圍第9項之發明，可按照適當之 二序供給訂正處理部所需之資料。又，因對於一個接收 =，只要記憶輸入資料或自該輸入資料所產生 -貪料之其中-方即可，可使資料記憶部之容量正 又，如申請專利範圍第10項之發明係一種解碼方法， 進理!由擴張里德所羅門碼構成之接收字 於訂正處理，求訂正資料；在該訂正處理步 了：i生之訂正跑照其校驗碼判定有無錯誤；在產生 以之將該訂正資料決定為應= 4:接誤之訂正資料之情況，將錯誤訂 j <接收子决疋為應求之訂正資料。 在對於接 可使得不 若依據如申請專利範圍第i或10項之 予判定最後無法產生無誤料χ 輪出未正確的訂正之資料。丁正貝抖之情況 利“第圍發明，係在如申請專 :產生之…料有錯誤時'定 若依據如申請專利範 料有錯誤時，不再進行錯誤訂正或11項之發明，在訂正資 ^疋為無法產生無誤 486880 五、發明說明（10) 之訂正資料後，輸出錯誤訂正前之接收字。 又二在如申請專利範圍第12項之發明，係在如申請專 利範圍第^項之解碼方法，在該訂正處理步驟，至產生無 誤之訂正資料為止重複執行該錯誤訂正處理；進行錯誤訂 正處=定之次數也無法產生無誤之訂正資無 法產生無誤之訂正資料。 若依據如申請專利範圍第3或12項之發明，重複進行 錯誤訂正，可提高產生無誤之訂正資料之可能性。 【發明之實施例】 以下邊參」照圖面邊說明本發明之一實施例。 圖1係表示本實施例之里德所羅門解碼裝 方塊圖。圖1之里德所羅門解碼裝 1 η、評僧客馆ι , 八1甸仅％碼計异部 1〇冲仞夕項式•位置多項式導出部20、鏈上 3〇、 錯誤訂正部4 〇以及資料記情邻5 〇 !孑郤 多項式•位置才碼計算部1(3、評價 夕貝八位置夕項式導出部2 0、鏈上拙1都Q π ^ 正部40作為訂正處理部動作。 炎寸。卩30以及錯誤訂 圖1之里德所羅門解碼裝置 構成之接收字作為輪入資料DI 由擴張里德所羅門碼 資料C2輸出。在以下舉例 知碼後作為第二訂正 伽羅瓦域GF⑻上之—次擴張二之擴『里德所羅門碼係 之位議=7、碼長n = 128。—個接:、、.=’設-個符說 成。又，以錯誤訂正數t = 3為例收予由128個符銳構 所羅門碼可訂正3個符號之錯誤:月。因此，本擴張里德 五、發明說明（11) 圖2係說明在圖1 圖。在以下，邊夂日” θ 所羅門解碼裝置之處理之流程 ㈣、2、…、圖1及圖2之步驟s卜S11邊說明。但， 置ju稱為錯誤之位1)。。將這種接收字中之錯誤符號之位 在4父驗碼計管都]Λ 資料記憶部50記二〗資料記憶部50輸入輸入資料DI。 在步驟SI f雨入資料DI後，向錯誤訂正部40輸出。 碼，作為浐驗碼計算部10計算輸入資料之校驗 巧作為輸入資料校驗碼SI。 在步驟S2，p w 成分是否全部為ΐ :十算部10檢測輪入資料校驗碼SI之 之成八入加& 、¥。枝驗碼計算部1 0在輸入資料校驗碼s 1 為莖二二二二f之情況，判定定輸人資料D1無錯誤，將作 •组士 、不仏就之第一無誤狀態暗示信號F1設為ON，向錯 卹Π!40輸出後，移至步驟S3之處理。而，校驗碼計算 :，輸入資料校驗碼SI之成分不全為零之情況，判定定 剧入貝料DI有錯誤，將第一無誤狀態暗示信號F丨設為 FF」向錯誤訂正部4〇輸出後，移至步驟^之處理。在任 一情況’校驗碼計算部丨〇都向評價多項式·位置多項式導 出部20輸出輸入資料校驗碼SI。 少在步驟S 3 ’錯誤訂正部4 〇因第一無誤狀態暗示信號F1 係ON而得知不必訂正錯誤，將資料記憶部5〇輸出之輸入資 料D I原封不動的作為第一訂正資料向校驗碼計算部丨〇及資 料記憶部5 0輸出。 、 _在步驟S4〜S7，第一無誤狀態暗示信號F1係〇1^，係在 輸入資料D I存在錯誤之情況之處理。
第16頁 486880 五、發明說明（12) 在步驟S4二評價多項式•位置多項式導出部2〇利用歐 基里德互除運算自輪入資料校驗碼s丨求錯誤位置多項式α (^)及錯誤評價多項式ω(ζ)之各次數之係數後，向鏈上搜 尋部3 0輸出這些多項式之係數。 π ΐ 2二式•位置多項式導出部2 〇具備資料保持器及 上未示）。資料保持器保持輸入資料校驗 二°人土“互除運算之中間結果，最後輸出錯誤位置 夕項式σ(ζ)及錯誤評價多項式ω(ζ)之各次數之係數。伽 ΪΪίίϋ資料:呆持器之輸出進行歐基里德互除運算而 [-^ 7 ΛΛ- i向貝料保持器輸出。關於該歐基里德互除 運异之、、，田即，記載於特開平1 0-1 35 846號公報。 美軍^石卜p/v ^ 平價多項4 ·位置多項式導出部2 0在歐 錯誤評價多項式ω (τζ V:數了下置多 係數。 、z J之火數以下，也輸出這些多項式之 在步驟S 5，鏈上插盖都q n/ 夕话—、,.上技哥°卩30進订鏈上搜尋，求錯誤位置 (；ϋ二元% #ju。即，鏈上搜尋部3〇將伽羅瓦域 代入錯誤位置多項式σ(ζ)，求錯誤位 “Ζ)之根m 二t該錯誤位置多項式 尋部，錯誤位置多 /ϋ^0輪出。此時，鍵上搜 互異之根之個數係小立之¥伽夕羅瓦域GF(27)具有之 情況，也不判斷是否可:;m項式σ⑴之次數之 只A (7 l Z J之根α〜ju各自和錯誤之位置
第17頁 486880 五、發明說明（13) j U對應。 又鏈上搜号部30將錯誤位置多項式σ(ζ)之根-ju 各自代入錯誤評價多項式ω(ζ)後，求錯誤之評價值ω( α -jU )，而且將錯誤位置多項式σ ( ζ )之根a _ju各自代入錯 誤位置多項式σ ( z )之導函數後，求錯誤位置多項式之微 分值σ ’（ α -川）。鏈上搜尋部3 〇向評價多項式•位置多項 式導出部2 0輸出錯誤之評價值ω ( α —ju)及錯誤位置多項式 之微分值σ ’（ a)。 在^，S6，在評價多項式•位置多項式導出部2〇之伽 羅瓦運异盎（圖上未示）將錯誤之評價值ω ( α _ju)除以對應 之錯誤位置多項式之微分值σ，（ α -ju)，求表示錯誤之位 置ju之各自之符號中之錯誤位元之錯誤之大小e後，向錯 誤訂正部4 0輸出。 u e 在步驟S7，錯誤訂正部4〇依照和鏈上搜尋部3〇輸出之 錯誤位置多項式σ (z)之根α -,u之各根對應之錯誤之位置 及評價多項式•位置多項式導出部2()輸出之錯誤之大小 u，對資料記憶部50輸出之輸入資料〇1進行錯誤訂正處 ^。即’自係輸入資料DI之接收字之錯誤之位置卜之符號 ，去和其對，之錯誤之大小％。因係在伽羅瓦域Μ(㈧之 擴大域之運算，不是減去而是加上錯誤之大小穴也可。 ^錯誤訂正部40將錯誤訂正處理後之資料作i第一訂正 貢料ci，向校驗碼計算部10及資料記憶部5〇輸出。資料記 憶部50記憶第一訂正資料⑴灸，再向錯誤訂正部4〇輸出第 一訂正資料C1。
第18頁 486880
在步驟S8 ’奴驗碼計算部ίο計算第一訂正資料ci之校 驗碼，作為訂正資料校驗碼SC。 一在步驟S9，評價多項式•位置多項式導出部2〇檢測訂 ，資=杈驗碼SC之成分是否全部為零。校驗碼計算部丨〇在 訂正資料校驗碼SC之成分全部為零之情況，判定第一訂正 =料C1，錯誤，將作為第二旗標信號之第二無誤狀態暗示 仏號F2汉為0N，向錯誤訂正部40輸出後，移至步驟S1 〇之 處理。而，校驗碼計算部10在訂正資料校驗碼sc之成分不 全ί零之情況，判定第一訂正資料C1有錯誤，將第二無誤 狀悲暗示化號F2設為OFF，向錯誤訂正部4〇輸出後，移至 步驟S11之處理。 在步驟S10，錯誤訂正部4〇因第二無誤狀態暗示信號 F2係0N而得知第一訂正資料C1無錯誤，將資料記憶部50 輸出之第一訂正資料C1原封不動的作為第二訂正資料C2輸 出0 在步驟S11，錯誤訂正部4〇因第二無誤狀態暗示信號 F2係OFF而得知第一訂正資料C1有錯誤，依照和鏈上搜尋 部3 0輸出之錯誤位置多項式σ (z)之根^ _ju之各根對應之 錯誤之位置ju及評價多項式•位置多項式導出部2〇輸出之 錯誤之大小eu，進行將資料記憶部5 〇輸出之第一訂正資料 C1復原成訂正處理前之輸入資料1)〗之處理。即，對於第一 訂正資料C1之錯誤之位置j u之符號，加上或減去與其對應 之錯誤之大小eu。錯誤訂正部4 〇將復原後所得到之輸入資 料D I作為第二訂正資料〇2輸出。
第19頁 486880 五、發明說明（15) 圖3係表示圖！之校驗竭計算部之構 ，校驗碼計算部10具備選擇器u、校驗碼運：二入 貧料校驗碼保持器13、訂正資料校驗 二 輸， 驗碼零檢測器15以及第二校驗碼零檢測器16 ^ 在選擇器11輸入輸入資料DI及第一訂正資料^ 向校驗碼運算器12交互的輸出輸入資料di及第一= 貧料C1。校驗碼運算器丨2和選擇器丨丨同步的動作，交互 輸=料校驗骑之計算和求訂正資料校驗碼％之言; ，碼保持器13和訂正資料校驗碼保持 輸入資料校驗碼保持器i 3只取入校驗碼運算器丨2之輸 出,中之輸入資料校驗碼81並保持後，向第一校驗碼零= 測盗15輸出、。第一校驗碼零檢測器15在輸入資料校驗碼si 之成分全部為零之情況，判定輸入資料1)丨無錯誤，將第一 無誤狀態暗示信號F 1設為0N，而在輸入資料校驗碼s丨之成 分=全為零之情況，判定輸入資料…有錯誤，將第一無誤 狀恶暗示信號F 1設為〇FF後，向錯誤訂正部4〇輸出。又， 輸入資料校驗碼保持器1 3和第一校驗碼零檢測器丨5輸出第 無誤狀恶暗示信號F 1之時刻同步的向評價多項式•位置 多項式導出部2 0輸出輸入資料校驗碼s I。 一樣的，訂正資料校驗碼保持器丨4只取入校驗碼運算 為1 2之輸出之中之訂正資料校驗碼sc並保持後，向第二校 驗碼零檢測器1 6輸出。第二校驗碼零檢測器丨6在訂正資料 校驗碼SC之成分全部為零之情況將第二無誤狀態暗示信號 486880 五、發明說明（16) F2設為0N，而在輸入資料校驗碼SI之成分不全為雯 將第二無誤狀態暗示信號F2設為〇FF後，向錯誤勺;正 輸出。 σ 4 0 圖4係表不圖1之錯誤訂正部之方塊圖。圖4 。兮 正部40具備第一錯誤訂正器41、錯誤之位置資料保θ 42、錯誤之大小資料保持器43以及第二錯誤訂正哭44 : 在第一錯誤訂正器41輸入第一無誤狀態暗示^ 資料記憶部50輸出之輸入資料!)〗、鏈上搜尋部3〇^ ^扭 誤位置多項式σ (ζ)之根α -ju以及評價多項式· / 、’曰 式導出部2 0輸出之錯誤之大小&。 、 置夕項 第一錯誤訂正器41在第一無誤狀態暗示信 情況’因不必對輸入資料D Ϊ訂正錯誤，將輪入資b料旧= 不動的作為第一訂正資料C1輸出。又，第一錯# — f封 在第一無誤狀態暗示信號為OFF之情況，輸3入^^广41 有錯誤二因需：訂正錯誤，對於在輸入資料di和貝根含 應之錯誤之位置j u之各位置表示之符號，進 子 和該錯誤之位置ju對應之錯誤之大小eu之錯誤訂正口上 後，將訂正處理後之資料作為第一訂正資料 訂正資料C1。 物出弟— 錯誤之位置資料保持器42記憶根α _ju後， 訂正器44輸出。錯誤之大小資料保持器43記憶錯竽:，誤 eu後，向第二錯誤訂正器44輸出。 …’曰、大小 在第二錯誤訂正器44輸入第二無誤狀態暗示信號F2、
486880 五、發明說明（17) 資料記憶部50輸出之第一訂正資料C1、錯誤 (Z )之根α ―川以及錯誤之大小e 。 只八σ 第二錯^為44在第：無誤狀態暗示信號F2為〇 十月況’因不必對苐一訂正資料C1訂正錯誤，將第一訂正資 料C1'=動的作為第二訂正細輸出。又，第二錯； 訂正器44在第二無誤狀態暗示信號F2為附之情況，第 = =誤1需要訂正錯誤，依照和根之 對應之錯誤之位置JU和錯誤之大小e〆進行使 原成在第-錯誤訂正器41之訂正處理前d 置忉各自表示之符號，加上正貧枓ci之錯誤之位 之錯誤之大小eu。第二錯誤：咸哭去4f該錯誤之位幻u對應 入資料Di作為第二訂正資船輸;。將復原後所得到之輸 於是，第二錯誤訂正器44在第一 確的進行訂正處理而第—訂二^。丁正為41無法正 原後之輸入細，而不是1輸；;輸出復 圖。圖叫表示向校驗碼；；置；動作之時序 資料㈣入，曝)表：二 校驗碼SI及訂正資料校驗碼％之計算士 J輸：貧料 多項式•位置多項式導出部2() 圖（）表不在評價 錯…多項式σ(ζ)==
4〇之弟及弟二訂正資料π、以之輪出。 I
48688U 五、發明說明（18) ，圖5，P〇〜p5各自表示執行關於第〇5個輸入之訊息 IS理’，P表示未動作之狀態。此夕卜，將瑪長W28 % 6 收字虽作—個訊息封處理。纟此，特別主要說明 讥恩封P2。 入於ii::路處理階段，將訊息封P2作為輸入資料di輸 .^ 4 ”、…异"卩10及貧料記憶部5 0。校驗碼計算部1 0計算 關於訊息封P2之輸入資料校驗碼SI (圖5(a)、（b))。 物在Ϊ二管路處理階段，評價多項式·位置多項式導出 :百先使用在第-管路處理階段所計算之關於訊息封？2 之^貧料校驗碼SI，計算錯誤評價多工員式〇⑴及錯誤 位，夕項式σ(ζ)之各次數之係數（圖5(c))。然後，鏈上 技尋邛3 0使用该錯誤評價多項式ω (z )及錯誤位置多項式 σ(ζ)，利用鏈上搜尋計算關於訊息封“之錯誤位置多項 式σ(ζ)之根a-iu、錯誤之評價值ω( a—ju)以及錯誤位置 多項式之微分值〇·，（ am)(圖5(d))。此外，評價多項式 •位置多項式導出部2〇使用關於訊息封p2之錯誤之評價值 ω ( α -w )及錯誤位置多項式之微分值σ，（ α —ju )計算錯誤 之大小eu (圖5 (c))。在第二管路處理階段，評價多項式· 位置多項式導出部20及鏈上搜尋部30之一方進行計算處理 之期間，另一方變成停止狀態。 因進行這種處理，在評價多項式•位置多項式導出部 2 0及鏈上搜尋部3 〇輸入頻率為基準時計信號（圖上未示）之 4倍之時計信號（圖上未示）。 在第三管路處理階段，錯誤訂正部4 〇使用在第二管路
第23頁 486880 五、發明說明（19) 處理1¾段所計算之關於訊息封P2之錯誤位置多項式σ ( z ) 乂二w及錯誤之大小〜，按照需要對資料記憶部5 〇所保 」之訊息封P2之輸入資料D丨進行錯誤訂正處理後，求第一 =正資料C1 (圖5(e))。錯誤訂正部4〇向校驗碼計算部1〇及 =料圮憶部5 0輸出第一訂正資料C1。又，在第三管路處理 ，段’校驗碼計算部1 〇依照訊息封p2之第一訂正資料c丨計 异C正貧料校驗碼sc。此時，在校驗碼計算部丨〇及資料記 憶部50輸入訊息封P4，校驗碼計算部1〇也計算關於訊息封 P4之輸入資料校驗碼si (圖5(b))。 於疋’因平行的計算輸入資料校驗碼S I及訂正資料校 驗碼SC ’在校驗碼計算部丨〇輸入頻率為基準時計信號（圖 上未示）之2倍之時計信號（圖上未示）。 在第四管路處理階段，錯誤訂正部4〇在訊息封？2之第 一纤正資料C1之叮正資料校驗碼s c之成分之成分不全為零 時，將對於資料記憶部5〇所保持之第一訂正資料以進行& 原處理所得到之訂正處理前之輸入資料D丨作為第二訂正資 料C2輸出，而訂正資料校驗碼％之成分之成分全為零時，、 將資料記憶部5 0所保持之第一訂正資料(：丨原封不動的作 第二訂正貧料C2輸出。此時，錯誤訂正部4〇也進行關於 第二管路處理階段輸入校驗碼計算部丨〇之訊息封以之錯誤 訂正處理，求第一訂正資料C1 (圖5(e))。 在以上四個管路處理階段，關於訊息封P2之一連串之 處理完了。此外，在錯誤訂正部4〇及資料記憶其 準之時計信號（圖上未示）。 U輸入基
第24頁 486880
圖6係說明在圖3之校驗碼計算部之内部之 圖。圖6(a)係表示對選擇器丨丨之輸入資料M之乍之時序 係表示對選擇器丨丨之第一訂正資wC1之輸入，（(；入’（b) 在校驗碼運算器12之校驗碼計算，（d)係表示來表示 料校驗碼保持器13之輸入資料校驗碼31之輪出輪 不來自第一校驗碼零檢測器丨5之第一無誤狀態暗 之輸出，（f )係表示來自訂正資料校驗碼保持器丨4〜 =校：碼SC:”，⑻係表示來自第二校驗碼零：測 U、6之第一無誤狀悲暗不信號F2之輸出。在圖6，Μ〜π和 圖5 —樣的各自表示執行關於第〇〜5個輸入之訊息封之處 理，又，Ρ2(η)表示執行關於在訊息封Ρ2之第^個符號=户 理。 JU 免 在第一管路處理階段，如圖6(a)、（b)所示，在圖3之 選擇器11依次輸入訊息封P2之符號P2(i)、P2(2)、…、 2 (η) ’作為苐一個訊息封Ρ 2之輸入資料D I，而且依次輸 入訊息封Ρ0之符號P〇(l)、Ρ〇(2).....Ρ0(η)，作為第0個 訊息封Ρ0之第一訂正資料Cl。 選擇器 11 如P2(l)、P0(1)、P2(2)、P〇(2)..... Ρ 〇 (η)般向校驗碼運算器1 2交互的輸出第二個訊息封ρ 2之 輪入資料D I和第0個訊息封Ρ0之第一訂正資料c 1。校驗碼 運算器1 2對於自選擇器11輸入之符號按照輸入之順序進行 &驗碼計算（圖6 ( c ))。校驗碼運算器1 2在對於關於訊息封 Ρ2之輸入資料DI之輸入資料校驗碼SI及關於訊息封Ρ0之第 一訂正資料C1之訂正資料校驗碼SC完成各自之第η個符號
第25頁 ^880
之計算時，分別向輸入資料校驗碼保持器丨3及訂正資料校 ，碼保持器1 4輸出。校驗碼運算器丨2按照輸入資料D丨之符 戒之輸入速率之2倍之速率進行對於個符號之處理。 在第二管路處理階段，輸入資料校驗碼保持器丨3向第 一校驗碼零檢測器15輸出關於訊息封P2之輸入資料校驗碼 S 11圖6 (d))。訂正資料校驗碼保持器丨4向第二校驗碼零檢 測裔16輸出，於訊息封p〇之訂正資料校驗碼％(圖6(f ))。 又，在第二管路處理階段，第一校驗碼零檢測器丨5將 關於訊息封P2之輸入資料校驗碼SI之成分是否全部為零之 檢^結果作為第一無誤狀態暗示信號F 1輸出。例如，該輸 入貝料杈驗碼S I之成分係全為零，訊息封p2無錯誤時，第 ，校驗碼零檢測器1 5將第—無誤狀態暗示信號F1設為0N後 輸出圖6 三一樣的，第二校驗碼零檢測器1 6將關於訊 息封po，汀正賁料校驗碼sc之成分是否全部為零之檢測結 果作為第=，誤狀態暗示信號F2輸出（圖6(g))。 ϋ 5 ί ί二，處理階段，和在第一管路處理階段-樣， ^於;自2計算關於訊息封1"4之輸入資料校驗碼SI及 關於汛了封P2之訂正資料校驗碼sc (圖6(c))。 冰自H:二路處理階段，帛一校驗碼零檢測器1 5將關於 别入資料校驗碼$ I之成分是否全邻為交之檢測 結果作為第一盔钽业能择-产啼P1认疋否王σ卩為零之檢別 …、块狀悲暗不乜號F 1輪出（圖6 (e))。一樣 二驗碼零檢測器16將關於訊息封p〇之訂正資料校 是否全部為零之檢測結果作為第二無誤狀態 睛輪出（圖6(g))。於是，校驗碼計算部1{)以4個
第26頁 486880 五、發明說明（22) *-- 管路處理階段完成關於一個訊息封之處理。 如以上所示，本發明之解碼裝置對於輪入資料M進行 錯誤訂正處理後’對於訂正錯誤後之資料C 1，再進行校驗 碼計算，求訂正資料校驗碼SC，因在認為誤訂正之情況輸 出錯誤訂正前之輸入資料DI，可避免輸出錯誤之訂正資 料。 、 此外，在以上之實施例， 所產生之訂正資料是否含有錯 誤多次後判定也可。即，預先 正資料未檢測到錯誤為止重複 正資料之情況，輸出該訂正資 之次數也未產生無誤之訂正資 誤之訂正資料後，使得輸出係 料D I也可。在此情況，需要錯 料，校驗碼計算部1 〇就求訂正 是否是零後通知錯誤訂正吾卩4 〇 多項式導出部2 0輸出校驗碼。 此外’藉者使用微處理器 明之解碼裝置。 只在訂正錯誤一次後，判定 誤’但是使得在進行訂正錯 記憶輸入資料DI後，至在訂 錯誤訂正，在產生無誤之訂 料；而在重複錯誤訂正既定 料之情況，判定無法產生無 盯正前之預先記憶之輸入資 誤訂正部4 0每輸出訂正資 資料之校驗碼，判定校驗碼 ’而且向評價多項式•位置 等，也可利用軟體實現本發 【發明之效果】 理後：本r月之解碼裝置，因對於錯誤訂正處 二r而㈣錯誤，可防止誤訂正，不 、、’馬’也可貫現擴張里德所羅門碼之解
第27頁 486880
第28頁 486880 圖式簡單說明 圖1係表示本實施例之里德所羅門解碼裝置之構造之 方塊圖。 圖2係說明在圖1之里德所羅門解碼裝置之處理之流程 圖。 圖3係表示圖1之校驗碼計算部之構造之方塊圖。 圖4係表示圖1之錯誤訂正部之方塊圖。 圖5係說明在圖1之里德所羅門解碼裝置之動作之時序 圖。 圖6係說明在圖3之校驗碼計算部之内部之動作之時序 圖。 【符號說明】 10 校驗碼計算部 1 1 選擇器 12校驗碼運算器 13輸入資料校驗碼保持器 1 4訂正資料校驗碼保持器 1 5第一校驗碼零檢測器 1 6第二校驗碼零檢測器 2 0評價多項式•位置多項式導出部 3 0 鏈上搜尋部 4 0 錯誤訂正部 41 第一錯誤訂正器 4 2錯誤之位置資料保持器
第29頁 486880 圖式簡單說明 4 3錯誤之大小資料保持器 4 4 第二錯誤訂正器 5 0資料記憶部 D I輸入資料 C1第一訂正資料 C2第二訂正資料 S I 輸入貢料校驗碼 S C訂正貧料权驗碼 F 1第一無誤狀態暗示信號（第一旗標信號） F 2第二無誤狀態暗示信號（第二旗標信號）
第30頁

Claims (1)

  1. 486880 六、申請專利範圍 1 · 一種解碼 具備訂 字進行錯誤 該訂正 (Syndrome) 在產生 而在無法產 接收字。 2 ·如申請專 部在自該接 生無誤之訂 3·如申請專 該訂正 係重複 為止； 裝置，其特徵為： 正處理部，對 訂正處理， 只張里德所羅門碼構成 考搜2 求訂正資料； 战之接收 處里邻對於所產 判定有無錯誤；^ 丁正資料依照其校驗碼 了無誤之訂正資料之情 生無誤之訂 輸出忒§丁正資 貝枓之情況，輸出錯誤訂心之 利範圍第1項之解碼裝置， a 收字所產生之吖正眘杷+ 八 Μ 4正處理 正資料。了貝枓有錯誤時’判定無法產 利範圍第1項之解碼裝置，其中： 處理部 ’、 · 執行該錯誤訂正處理直至產生無誤之訂正資料 一在進行錯誤訂正處理既定之次數仍無法產生無誤之 正資料時，即判定無法產生無誤之訂正資料。 4 · 一種解碼裝置，具備： 校驗碼（Syndrome)計算部，將由擴張里德所羅門碼構 成之接收字作為輸入資料，求该輸入資料之校驗碼，作為 輸入資料校驗碼後，依照該輸入資料校驗碼輸出表示在該 輸入資料是否有錯誤之第/旗標信號’而且求依照該輸入 資料所求得之第一訂正資料之校驗碼’作為訂正資料校驗 碼，依照該訂正資料校驗碼輸出表示在該第一訂正資料是
    …申請專利範圍 否有錯誤之第二旗標信號； ，價多項式•位置多項式導出部，依照該輸入資料校 馬求錯誤評價多項式及錯誤位置多項式之各次數之係 你$而且依照自該係數求彳于之錯誨之評價值及對應之錯誤 置多項式之微分值求錯誤之大小； 鏈上搜尋部，依照該係數求該錯誤位置多項式之根， 將該根各自代入該錯誤評價多項式後所得到之錯誤 值及將該根各自代入該評價多項式·位置多項式之 ϊί得到之錯誤位置多項式之微分值；及 錯誤之情況，依照該根及對應之示在該輸入資料有 輸入資料進行錯誤訂正處理所得到之曰=之大小，將對於該 貧料輸出，而在該第一旗標信號表二，作為該第一訂正 之情況，將該輸入資料作為該第—1、在該輪入資料無錯誤 該第二旗標信號表示在該第一訂正=正資料輸出；而且在 對於該第一訂正資料進行復原成錯=料有錯誤之情況，將 復原處理所得到之資料作為第二訂、=正處理前之資料之 二旗標信號表示在該第一訂正資料盔二料輸出，而在該第 -訂正資料作為第二訂正資料輸出‘:…之情;兄’將該第 5·如申請專利範圍第4項之解碼裝置，复 ^ 算部具備： 中，該权驗碼計 一訂ί =德輸：該：入資料及該訂正處理部輸出之該第 枝驗馬運异益，依照該選擇器輸出之該輸入資料及該
    第32頁 486880
    六、申請專利範圍 第一訂正資料，分別求該輸 驗碼； 輸入資料校驗碼保持器 出； 訂正資料校驗碼保持哭 出； ^ 入貧料校驗碼及該訂正資料校 ’保持該輸入資料校驗碼後輸 ’保持該訂正資料校驗碼後輸 第 出之該 該輸入 之情況 號；及 第 出之該 該第一 為零之 二旗標 6 ·如申 該 係 錯誤評 出的； 在 次數係 7 ·如申 保持器輸 如表示在 不全為零 一旗標信 保持器輸 如表示在 而在不全 輪出該第 一校驗碼零檢測哭扁 ^ λ杳# e ^ 在该輸入資料校驗碼 輸入貝科才父驗碼之&八人 成分全部為零之情況， 資料無錯誤般輪出兮筮 物出遺弟一旗標信號；而在 如义示在4輪入資料有錯誤般輸出該第 f校=碼零檢測器，在該訂正資料校驗碼 訂正貧料校驗碼之成分全部為零之情況， 訂正資料無錯誤般輸出該第二旗標信號； 情況，如表示在該第一訂正資料有錯誤般 信號。 請專利範圍第4項之解碼裝置，其中： 驗螞求該 係數後輸 多項式之 數。 評價多項式•位置多項式導出部 利用歐基里德互除運算依照該訂正資料校 價多項式及該錯誤位置多項式之各次數之 該歐基里德互除運算終了時，該錯誤位置 該錯誤評價多項式之次數以下也輸出該係 請專利範圍第4項之解碼裝置，其中·· ----- 第33頁 486880 六、申請專利範圍 該鏈上搜尋 將定義該擴 次代入該錯誤位 成零之元素，作 即令於該錯 誤位置多項式之 之根。 8·如申請專利範 部具備： 第 料有錯 應之錯 誤訂正 而在無 料輸出 錯 錯 及 第 正資料 該錯誤 成該錯 作為該 訂正資 一錯誤訂 誤之情況 誤之位置 處理所得 錯誤之情 誤之位置 誤之大小 二錯誤訂 有錯誤之 之位置表 謨訂正處 第二訂正 料各自作 部 張f德所羅門碼之根之伽羅瓦域之元素依 f夕項式後’求該錯誤位置多項式之值變 為該錯誤位置多項式之根； ^ 1 Μ S之互異之根之個數小於該錯 人之情況下，亦輸出該錯誤位置多項式 圍第4項之解碼裝置，其中，該訂正處理 正Ϊ斟ί該ί 一旗標信號表示在該輸入資 二、於遠輸入資料進行自和該根各 J不，符號減去對應之該錯誤之大小之』 況，將該輸入資料各自作為該第_ =資 持該錯誤之位置後輸出； 貝料保持裔’保拉兮^ 咏符该錯誤之大小後輸出； 正器’在該第二旗標信號表示在該 情況’將進行對於該第一訂正 ： 示之符號對應之該錯誤之大小之值而復原 :f料輸出；而在無錯誤之情況，將該第ί 為該第二訂正資料輸出。
    第34頁 486880 六、申請專利範圍 9.如申請專利範圍第4項之解碼裝置，其中，更包含資料 記憶部，將該輸入資料保持至該訂正處理部開始求第一訂 正資料為止後輸出，將該第一訂正資料保持至該訂正處理 部開始求第了訂正資料為止後輸出。 1 0. —種解碼方法，其特徵為： 具備訂正處理步驟，對由擴張里德所羅門碼構成之接 收字進行錯誤訂正處理，求訂正資料； 在該訂正處理步驟，對於所產生之訂正資料依照其校 驗碼判定有無錯誤； 在產生了無誤之訂正資料之情況，將該訂正資料決定 為應求之訂正貧料’而在無法產生無誤之訂正貧料之情 況，將錯誤訂正前之接收字決定為應求之訂正資料。 11.如申請專利範圍第1 0項之解碼方法，其中，該訂正處 理步驟在自該接收字所產生之訂正資料有錯誤時，判定無 法產生無誤之訂正資料。 1 2.如申請專利範圍第1 0項之解碼方法，其中： 在該訂正處理步驟， 重複執行該錯誤訂正處理直至產生無誤之訂正資料為 止； 在進行錯誤訂正處理既定之次數仍無法產生無誤之訂 正資料時，即判定無法產生無誤之訂正資料。
    第35頁
TW090107313A 2000-03-27 2001-03-27 Decoding device and decoding method TW486880B (en)

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP2000086831A JP3352659B2 (ja) 2000-03-27 2000-03-27 復号装置及び復号方法

Publications (1)

Publication Number Publication Date
TW486880B true TW486880B (en) 2002-05-11

Family

ID=18602933

Family Applications (1)

Application Number Title Priority Date Filing Date
TW090107313A TW486880B (en) 2000-03-27 2001-03-27 Decoding device and decoding method

Country Status (7)

Country Link
US (2) US20030145272A1 (zh)
EP (1) EP1280281A4 (zh)
JP (1) JP3352659B2 (zh)
KR (1) KR100526222B1 (zh)
CN (1) CN1252937C (zh)
TW (1) TW486880B (zh)
WO (1) WO2001073952A1 (zh)

Families Citing this family (13)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP3352659B2 (ja) 2000-03-27 2002-12-03 松下電器産業株式会社 復号装置及び復号方法
US6954892B2 (en) * 2002-06-06 2005-10-11 National Chiao Tung University Method for calculating syndrome polynomial in decoding error correction codes
US7206993B2 (en) 2003-03-12 2007-04-17 Matsushita Electric Industrial Co., Ltd. Method and device for decoding Reed-Solomon code or extended Reed-Solomon code
CN100394506C (zh) * 2003-08-20 2008-06-11 上海乐金广电电子有限公司 纠错装置及方法
CN100384116C (zh) * 2005-03-31 2008-04-23 中国科学院空间科学与应用研究中心 一种高速译码芯片
KR100714447B1 (ko) 2005-11-28 2007-05-07 한국전자통신연구원 수정 유클리드 알고리즘 연산 장치 및 그 방법과 그를이용한 리드-솔로몬 복호 장치
US20070150798A1 (en) * 2005-12-12 2007-06-28 Jia-Horng Shieh Method for decoding an ecc block and related apparatus
CN101453219B (zh) * 2007-11-30 2012-02-08 无锡华润矽科微电子有限公司 一种钱搜索电路及利用该电路的钱搜索方法
RU2390049C1 (ru) * 2008-10-07 2010-05-20 Государственное образовательное учреждение высшего профессионального образования "Саратовский государственный университет им. Н.Г. Чернышевского" Параллельный дешифратор управляемой транспозиции информации, хранимой в персональной эвм
US8370727B2 (en) * 2009-02-03 2013-02-05 Silicon Motion, Inc. Method and circuit for decoding an error correction code
KR101678917B1 (ko) * 2010-09-16 2016-11-24 삼성전자주식회사 디코더, 이의 동작방법, 및 이를 포함하는 장치들
CN102684706A (zh) * 2012-05-16 2012-09-19 山东华芯半导体有限公司 并行搜索的检错纠错方法和电路
US11651830B2 (en) * 2020-07-09 2023-05-16 Synopsys, Inc. Low latency decoder for error correcting codes

Family Cites Families (17)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2751415B2 (ja) * 1989-06-07 1998-05-18 キヤノン株式会社 誤り検出訂正回路
JP3137119B2 (ja) * 1989-06-07 2001-02-19 キヤノン株式会社 誤り訂正装置
US5280488A (en) * 1990-11-08 1994-01-18 Neal Glover Reed-Solomon code system employing k-bit serial techniques for encoding and burst error trapping
JPH09507117A (ja) * 1993-11-04 1997-07-15 シーラス ロジック，インコーポレイテッド リードソロモン復号化器
JPH088760A (ja) * 1994-06-16 1996-01-12 Toshiba Corp 誤り訂正装置
WO1997011530A1 (fr) 1995-09-20 1997-03-27 Hitachi, Ltd. Procede de decodage d'une grappe d'erreurs du code de reed-solomon et dispositif correspondant
JP2773701B2 (ja) * 1995-09-25 1998-07-09 日本電気株式会社 誤り訂正復号装置
JP3439309B2 (ja) * 1996-11-29 2003-08-25 日本電気株式会社 二重伸長リードソロモン復号装置
JPH10262034A (ja) * 1997-03-19 1998-09-29 Sharp Corp 符号化及び復号化装置
US5905740A (en) * 1997-04-08 1999-05-18 Seagate Technology, Inc. Apparatus and method for error correction
JPH113573A (ja) * 1997-04-15 1999-01-06 Mitsubishi Electric Corp 拡大リードソロモン符号の誤り訂正復号方法と誤り訂正復号装置、１次伸長拡大リードソロモン符号の誤り訂正方法と誤り訂正装置、および２次伸長拡大リードソロモン符号の誤り訂正方法と誤り訂正装置
US5966369A (en) * 1997-04-23 1999-10-12 Eastman Kodak Company Reducing corrugations in optical recording discs
JP3265273B2 (ja) 1998-12-02 2002-03-11 日本電気株式会社 誤り訂正回路
JP2000349652A (ja) 1999-06-07 2000-12-15 Hitachi Ltd 誤り訂正手段を備えた記憶装置
JP3352659B2 (ja) 2000-03-27 2002-12-03 松下電器産業株式会社 復号装置及び復号方法
KR20020065788A (ko) * 2001-02-07 2002-08-14 삼성전자 주식회사 엠 또는 이엠 비트 데이터 처리 겸용 리드 솔로몬 복호기및 그 복호 방법
US7206993B2 (en) * 2003-03-12 2007-04-17 Matsushita Electric Industrial Co., Ltd. Method and device for decoding Reed-Solomon code or extended Reed-Solomon code

Also Published As

Publication number Publication date
EP1280281A1 (en) 2003-01-29
CN1439197A (zh) 2003-08-27
WO2001073952A1 (en) 2001-10-04
JP2001274694A (ja) 2001-10-05
US20060031742A1 (en) 2006-02-09
JP3352659B2 (ja) 2002-12-03
KR100526222B1 (ko) 2005-11-02
EP1280281A4 (en) 2005-06-15
CN1252937C (zh) 2006-04-19
KR20030036148A (ko) 2003-05-09
US20030145272A1 (en) 2003-07-31

Similar Documents

Publication Publication Date Title
TW486880B (en) Decoding device and decoding method
US9647690B2 (en) Systems and methods for error correction coding
US8694872B2 (en) Extended bidirectional hamming code for double-error correction and triple-error detection
JP6930090B2 (ja) 復号化装置、プログラム、及び情報伝送システム
TW201328198A (zh) 錯誤訂正解碼裝置
RU2448359C1 (ru) Устройство хранения и передачи данных с исправлением ошибок в байте информации и обнаружением ошибок в байтах информации
JP2012050008A (ja) 誤り検出訂正方法および半導体メモリ装置
US20190068319A1 (en) Groebner-bases approach to fast chase decoding of generalized reed-solomon codes
JP3245290B2 (ja) 復号方法とその装置
RU2450331C1 (ru) Устройство хранения и передачи данных с исправлением одиночных ошибок в байте информации и обнаружением произвольных ошибок в байтах информации
KR100330642B1 (ko) 오류정정방법및오류정정장치
JPS61252719A (ja) バ−スト誤りの訂正方法および符号・復号装置
Tang et al. A new single-error correction scheme based on self-diagnosis residue number arithmetic
CN101273573B (zh) 数据解扰装置及数据解扰方法
RU2542665C1 (ru) Устройство хранения и передачи данных с обнаружением и исправлением ошибок в байтах информации
RU106771U1 (ru) Устройство хранения и передачи данных с исправлением ошибок в байте информации и обнаружением ошибок в байтах информации
JP2606647B2 (ja) 誤り訂正方法
RU107606U1 (ru) Устройство хранения и передачи данных с исправлением одиночных ошибок в байте информации и обнаружением произвольных ошибок в байтах информации
JPS58161547A (ja) デ−タの復号化方式
JPS62128623A (ja) 誤り検出訂正装置
CN105095012A (zh) 控制器、存储装置及控制方法
JP4681415B2 (ja) エラーイベント検出方法およびエラーイベント検出装置
RU2816550C1 (ru) Устройство хранения и считывания информации с коррекцией одиночных ошибок
JP2694794B2 (ja) 誤り訂正処理方法
JP3239866B2 (ja) Ｃｒｃに基づくデータ検査方法及び装置並びに記録媒体

Legal Events

Date Code Title Description
GD4A Issue of patent certificate for granted invention patent
MM4A Annulment or lapse of patent due to non-payment of fees