TW522657B - PGZ algorithm based multi-mode Reed-Solomon decoder and its method - Google Patents
PGZ algorithm based multi-mode Reed-Solomon decoder and its method Download PDFInfo
- Publication number
- TW522657B TW522657B TW091100683A TW91100683A TW522657B TW 522657 B TW522657 B TW 522657B TW 091100683 A TW091100683 A TW 091100683A TW 91100683 A TW91100683 A TW 91100683A TW 522657 B TW522657 B TW 522657B
- Authority
- TW
- Taiwan
- Prior art keywords
- polynomial
- error
- mode
- characterization
- decoder
- Prior art date
Links
- 238000004422 calculation algorithm Methods 0.000 title claims abstract description 41
- 238000000034 method Methods 0.000 title claims description 24
- 238000012937 correction Methods 0.000 claims description 30
- 238000011156 evaluation Methods 0.000 claims description 21
- 238000012512 characterization method Methods 0.000 claims description 19
- 238000004364 calculation method Methods 0.000 claims description 16
- 239000011159 matrix material Substances 0.000 claims description 12
- 230000002079 cooperative effect Effects 0.000 claims description 6
- 230000001419 dependent effect Effects 0.000 claims description 3
- 230000014509 gene expression Effects 0.000 claims description 2
- 239000000463 material Substances 0.000 claims description 2
- 230000008030 elimination Effects 0.000 claims 1
- 238000003379 elimination reaction Methods 0.000 claims 1
- 238000004891 communication Methods 0.000 abstract description 2
- 239000007787 solid Substances 0.000 abstract 1
- 238000010586 diagram Methods 0.000 description 8
- 238000009795 derivation Methods 0.000 description 4
- 238000004519 manufacturing process Methods 0.000 description 4
- 238000005516 engineering process Methods 0.000 description 3
- 230000005540 biological transmission Effects 0.000 description 2
- 230000000694 effects Effects 0.000 description 2
- NAWXUBYGYWOOIX-SFHVURJKSA-N (2s)-2-[[4-[2-(2,4-diaminoquinazolin-6-yl)ethyl]benzoyl]amino]-4-methylidenepentanedioic acid Chemical compound C1=CC2=NC(N)=NC(N)=C2C=C1CCC1=CC=C(C(=O)N[C@@H](CC(=C)C(O)=O)C(O)=O)C=C1 NAWXUBYGYWOOIX-SFHVURJKSA-N 0.000 description 1
- PEDCQBHIVMGVHV-UHFFFAOYSA-N Glycerine Chemical compound OCC(O)CO PEDCQBHIVMGVHV-UHFFFAOYSA-N 0.000 description 1
- 238000013461 design Methods 0.000 description 1
- 238000009434 installation Methods 0.000 description 1
- 238000012545 processing Methods 0.000 description 1
- 230000003252 repetitive effect Effects 0.000 description 1
- 230000004044 response Effects 0.000 description 1
- 208000011580 syndromic disease Diseases 0.000 description 1
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
- H03M13/65—Purpose and implementation aspects
- H03M13/6502—Reduction of hardware complexity or efficient processing
-
- 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
-
- 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/158—Finite field arithmetic processing
-
- 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/1585—Determination of error values
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 Correction Of Errors (AREA)
Description
522657 經濟部智慧財產局員工消費合作社印製 A7 B7_______ 五、發明說明（1 ) [發明之技術領域] 本發明係有關於一種李得-所羅門解碼器；進一步地 說明，本發明是一種基於 PGZ 演算法 (Peterson-Gorenstein-Zierler Algorithm)的多模式李得 _戶斤 羅門解碼器。 [發明背景與習知技術] 李得-所羅門碼（Reed-Solomon Code，RS碼）由於對 連續傳輸錯誤（Burst Transmission Errors)有很好的錯誤 更正能力，因此在諸如xDSL、電纜數據機、處理器與 記憶體之間、CD以及DVD等數位通訊與儲存系統之中 普遍地使用作前向錯誤更正。 在各種RS解碼演算法之中，pgz演算法對於實現 K3的RS解碼器提供了最簡單的方法。這在如處理器與 記憶體間的錯誤控制碼（Error Control Code，ECC)之類 需要較小錯誤更正能力的系統是一種低成本的做法。不 像疊代的RS解碼演算法，如Bedekamp_Massey演算法， 傳統PGZ演算法的主要缺點是僅能運作於單一更正能 力。換言之，解卜3的PGZ解碼電路不能正確執行 2的更正，所以匕3的PGZ解碼電路將需要置放三份不 同的硬體電路來分別計算戶1，t=2以及卜3的更:^就 如圖二所示的電路方塊圖。 顯然地，在電路中放置三份重複的硬體電路對於晶 片面積與成本是一種製造上的負擔。由於以傳統pgz = 算法的技術來製作李得-所羅門解碼器，需要針對每個不 同的錯誤更正能力（錯誤更正能力的數目丨=〇，丨2 3等） 來個別設計硬體架構，-旦錯誤碼的數目增加時，，所需 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公$ —-—-- -----I!--------裝--- (請先閱讀背面之注意事項UI寫本頁) 線· 522657 A7 ---------- -B7 ___ 五、發明說明（2 ) 要的晶片面積也相對的成級數增加，因此這無形中增加 了製作時的成本，同時也使其硬體的使用效率降低。此 外，在李得-所羅門解碼器的架構當中，很清楚地有限場 反相器（Fimte Field Inversion，FFI)在整個電路當中佔據 了很大的面積且需要花費很長的運算時間，且隨著錯誤 更正能力的增加，整體電路的設計會變得非常複雜，且 所需要有限場加法器（Flnite Field Adder FFA)以及有限 %乘法裔（Finite Field Multiplier，FFM)更是隨著級數成 因此，本發明提供一種可配置的VLSI架構來執行以 PGZ /貝异法為基礎解決各種更正能力的多模式李得_所 羅門解碼器，將是具有產業的利用性與進步性。 本發明的主目的在於提供一種基於PGZ演算法而因 應錯决狀況以解決各種更正能力的多模式李得·所羅門 解碼器。 " 本發明的次一目的在於提供一種在VLSI架構中為 低成本且使用較少面積資源的多模式pGZ解碼電路以 實施李得-所羅門解碼器而解決各種錯誤更正的問題。 、本發明的再一目的在於提供一種改良基於pGz演算 $實施李得·所羅門解碼器，將錯誤更正能力卜3的硬體 电路加以修改，以達到利用同一份硬體電路可以解決各 種錯誤的更正能力t=05l，2,3。 [發明概述] 有鐘於習知技術以PGZ演算法為基礎實施李得-所 羅門解碼器，在VLSI架構令係利用重複的硬體電路來 達到各種錯誤的更正能力㈣，而造程上較大面積 本紙張尺度it用中國國家標準㈣似4規格⑽χ 297公羞了 - — — — — — — — ·1111. (請先閱讀背面之注咅？事項寫本頁) 訂· 522657 經濟部智慧財產局員工消費合作社印製 A7 五、發明說明（3 ) 的佔用及硬體資源使用效率的降低，且演算法的實施 (Implement)包含有限場反相器的運算使整體電路計算複 雜度增加且影響運算的速度，因此本發明遂利用演算法 的推導’使得實施李得_所羅門解碼器，在解關鍵方程式 (Key Equation)運算時無須有限場反相器的運算，以達到 降低使用面積的資源及提昇運算效能，此外，本發明改 良基於PGZ演算法實施李得-所羅門解碼器具有錯誤更 正能力t=3的硬體電路，使其具有多模式PGZ解碼電路 可以處理卜0，丨，2,3個錯誤更正，為本發明諸多重要的特 徵之一 ° 在本叙明的一種實施例中，李得_所羅門解碼程序包 3 ·计异接收資料的表徵（syndr〇me)·，解算關鍵方程式； 二及評估錯誤位置與錯誤評價，其中解算關鍵方程式的 程序係以簡化的PGZ演算法為基礎，並進一步推導出解 异過程無須FFI的運算，以大幅減少計算的複雜度並降 低硬體架構所佔㈣面積資源’而且經由—多模解碼方 =獲得錯誤數目而提出可以處理陶,2,3個錯誤更正 的夕模式PGZ解碼架構。 人·=發日月的另一實施例中，李得-所羅門解瑪器包 ί Μ、徵計算器，以計算接收資料的表徵(巧油_); ^鍵方程切算器，接收表徵計算器輸㈣表徵方程 誤位置與錯誤評價評估器，接收關鍵方程式 仔錯秩位置與錯誤評價；其中_方 : ::Ζ解碼器為基礎，且卿馬架構係由二^ ，、、成而無須FFI，PGZ解碼器包含—多模解碼控制器， “氏張涵用^各⑽x 297¥1 ---1-----------裝--- (請先閱讀背面之注意事項寫本頁) · -線· 522657 A7
經濟部智慧財產局員工消費合作社印製 以獲得錯誤數目使pGz解錯誤更正，遂以一多模式:冓可以處理Μ，！二3偏 算器。 解碼器實施關鍵方程式萌 本發明基於PGZ演曾、去 器及其方法以及其諸多二與羅門解碼 及所附圖式中得到進—步的瞭鲈亏倣將攸下述砰細說明 [圖式標號說明] μ + 100多模式PGZ解碼器ιοί表徵計算器102關鍵方程式解算器 103評估器 104有限場加法器，FFa 105有限場乘法器，ffm 106有限場反相器，ffi 107控制器108錯誤更正器 109先進先出（fIF〇） [發明之較佳實施例說明] 雖然本發明將參閱較佳實施例之所附圖式予以充份 描述’但在此描述之前應瞭解熟悉本行之人士可修改在 本文中所描述之發明，同時獲致本發明之功效。因此， 須瞭解以下之描述對熟悉本行技藝之人士而言為一廣 泛之揭示，且其内容不在於限制本發明。 首先請參考圖一，係顯示李得-所羅門解碼程序之流 程圖。一李得-所羅門解碼程序主要包含以下程序：計算 接收多項式r(x)的表徵（Syndr〇me)，以獲得表徵多項式 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公着
• I I I 14-----------裝 (請先閱讀背面之注意事項寫本頁) n · 訂· 線 522657 C7 D7 五、創作説明（5) (Syndrome polynomial) S(x);根據表徵多項式 S(x)，解 算出關鍵方程式（Key equation)的錯誤位置多項式（Error location polynomial) σ(χ)及錯誤評價值多項式（Error value polynomial) ω(χ);根據錯誤位置多項式σ(χ)與錯誤 評價值多項式ω(χ)，評估錯誤位置與錯誤評價值；以及 根據評估的錯誤位置與錯誤評價值，更正接收資料的錯 誤得到傳送碼字元的多項式c(x)。 上述程序中，傳送碼字元的多項式c(x)與接收多項 式r(x)可由以下的式（1)來表示 r(x)=c(x)+e(x) ⑴ 其中，e(x)表示錯誤樣型（Error pattern)。從接收多項 式r(x)的α1所獲得的表徵值&可表示為式（2) /7-1 5,=厂(a’）= Z [(a’)·7 所以 1 < / < 2/ 表徵多項式S(X)定義為 (2) (請先閱讀背面之注意事項寫本頁) 裝· 訂. 5(χ) = Χ^.. (3) 解算出關鍵方程式的PGZ演算法包含解算了 TVewi⑽ 的步驟： 線 經濟部中央標準局員工消費合作社印製 〜 · …义+1 σ f-1 -A 〜 · A = ^ 2 人1 心+2 · .._ σ 0 — St _ 表徵值&係用來解出式(4)中的σ值 項式σ(χ)定義為 σ(χ) = 〇〇 + cr^ + ... + ctAxrl + ^ 而所解的關鍵方程式為式（6)所示 本紙張尺度適用中國國家標準(CNS)A4規格(210X297公釐） (4) 而錯誤位置多 (5) 522657 A7 B7 五、發明說明（6 〇·(χ)^(χ) = ~ω{χ) + // · χ2/, 其中’錯誤評價多項式ω (χ)定義為 (〇{χ) =ω0 + +^y?1x/_1. =1時 ⑹ ⑺ 根據PGZ演算法從式（4)中獲得K]k]-[-^] ^ σ〇'^ 所以，計算的錯誤位置為 σ(χ) = σ0 +χ 因此’可以解算t=l的關鍵方程式 σ(χ. χ:⑺⑻〜(σ。+ x)(V χ2 其中，錯誤評價多項式為 Φ) = ^〇 〇 必。二 σηχ(9) 對於t=〗時，上述PGZ演算法解算出式（8)與（9)的 RTL(Register Transistor Leve丨）之硬體架構如圖四所 示，將包含： FFAx1; FFM x2; FFI x1 當t=2時 根據PGZ演算法從式(4)中獲得 (8) --------1-------裝--- (請先閱讀背面之注咅？事項寫本頁) _ 線- 經濟部智慧財產局員工消費合作社印製 —S2 σι" ~s\ Λ _σ〇_ _~S2_ σι => 〇2〇4^V°3； ， ^4 + (¾)2 解算t=2的關鍵方程式，其錯誤評價多項式為 (η) 對於t=2時，上述PGZ演算法解算出式（10)與（11 的RTL硬體架構如圖五所示，將包含： (10) 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐） 522657 發明說明（ FFI x1 FFA x4; FFM x11; 當t=3時 根據PGZ演算法從式(4)中獲得 "S2 5? S4" V2- ~^1 \ S5 = ~S2 SA S3 s;_ _σ〇_ ~S^_ +52从4 +4¾ +4¾ +4¾ + 从4& +&从 + W4 +4¾ + ¾¾ 項 WA + 似5 + + A W + 挪6 + S2S4S6+ S3S4S5 +S3S4S5 +54^4+^3^ +S2S5S5 S]S4S6 + + S3S3S5 + SlS5S5 + S2S2S6 + S3S4S4 S2S4S6 + S3S4S5 + S3S4S5 + + S3S3S6 +S0S5S5 ^]2) 解算t=3的關鍵方程式，其錯誤評價多項式為 丁 必(X)=必。+必〆+ β2χ2 且 〇;〇 = σ0^ ^ ωλ = σ0^2 + σ} Sx ^ ω2 = a0S3 + σ]S2 + σ2^ (j 3 ) 對於t=3時，上述PGZ演算法解算出式（12)與（13) 的RTL硬體架構，將包含： FFA x19; FFM x49; FFI x1 因此，以傳統PGZ演算法為基礎實施李得_所羅門解 碼1§ ’在VLSI架構中造成製程上較大面積的佔用及硬 體資源使用效率的降低，且演算法的實施(㈣丨⑽如)包 各FF7的運异使整體電路計算複雜度增加且影響運算的 速度，本發明進一步簡化演算法的推導，使得‘施；得 -所羅門解碼ϋ得減少計算複雜度，並在解關鍵方 (Key EqUatlon)運算時無須FFI的運算，以達到 :: 面積的資源及提昇運算效能。 -
本發明李得-所羅門解碼程序，進-步簡化t==3 PGZ 本紙張尺度it用中關家標準（CNS)A4 g(21G χ 297公^· 522657 五、發明說明（8) 演算法的式（12)，在σ。，σΐ5 σ2的分母中，兩項可 從FFA中取消；同樣地，在σ〇的分子有兩項μ而亦可 從FFA中取消。此外，式（12) σ〇, & ^的相乘項^办， S2S3S5, S2S4S5, S2S5S5中，共同項祕皆出現在前述各 項中，所以本發明的解算程序中先算出項的值可有 效降低計算的複雜度；同樣地，其他共同項心^， SsS^SiS5, &SlSG，皆可先被算出來。如此，相對於上 述t=3時，PGZ演算法解算出式（12)與（13)的RTL硬體 架構，本發明簡化t=3PGZ演算法的RTL硬體架構如圖 六所示，可減少到包含： FFA x12; FFM x27; FFI x1 再者，PGZ演算法的解算過程中包含FFI的運算， 不但會使硬體架構的計算速度降低，而且也佔用了許多 的硬體面積資源，因此，本發明再一步簡化了 pGz演算 法使其解算過程中無須包含FFI 106的運算。 再次參考式（4)，並定義了表徵矩陣夕⑻、錯誤位置 向量與表徵向量'如下
St、t 二 ^3 ^4…心2 ； ：*. ： σ/>：1 - σί-2 二 V -夕2 _A+1 4+2 …^ ， _σ〇 _ 所认Newton Identity可表示為 μ (Η) 另外，表徵矩陣5加的行列式表示為 為二 detd，） （15) 將矩陣‘的行列式為乘上式⑺及式（7)，獲得新的錯誤 本紙張尺度適用中國國家標準（CNS)A4規格（210 « — — Jilt — — — — — — — * I I (請先閱讀背面之注意事項寫本頁) Ί.Φ、I · ;線· 經濟部智慧財產局員工消費合作社印製 297公釐） 經濟部智慧財產局員工消費合作社印製 522657 A7 —B7 五、發明說明（9 ) 位置多項式φ(χ)及新的錯誤評價多項式Ω(Χ)之表示式 如下： φ(χ)二 Φ。+ Φ〆 + .·. + Φ,-〆—1 + Φ〆 (16) Ω(χ) = Α}ω(χ) = 4ω0 + Α^ωλχ + ... + Α,ω^χ^ Ω(χ)二 Ω0 +Ω〆 + …+ Ω㈠ χ 卜1 (17) 因此， 當t=l時 4 二夕2 (18) Φ0 二{σ0，=冷 (19) Ω。=為〇Ά =為叫 （20) 當t=2時 A2 = S2S4 + (S3)2 (21) Φ〇 = Λ2σ0 5 Φι = Α2σ] Φ2 = Α2 (22) 4⑺。^{ = Α2σ0S2 + A2alSl = Α2ω] ^23) 當t=3時 4 二 w6+w5 +4¾ + W4+W6+w5 (24) Φ0 = Α?σ0 Φ} = Α3σ 1 ^ Φ2 = Α3σ2 Φ 3 = Α? (25) 二 二 乂3⑺Q ^3^"〇^2 ~ ^3^1 .， 5 Ω2 = +^3σΐ^2 +^3σ2^1 = ^3^2 (26) 相較於t=3時傳統PGZ演算法計算σ值，本發明再 一步簡化了 PGZ演算法，對於t二3計算φ值已消除FFI 的運算。因此，本發明再一步簡化t二3 PGZ演算法無須 FFI運算的RTL硬體架構如圖七所示，可再一步減少到 包含： 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐） ----r-----------裝--- (請先閱讀背面之注意事項寫本頁) 訂.· -線· 522657 A7 發明說明（10)FFA x12; FFM x24; FF, χ〇 然而，對於傳、统PGZ架構係利用重複的硬體電路 達到各種錯誤的更正能力㈣），如圖二所示的電路_ 圖’本發明的目的之一係提出利用同一份硬體電路可以 解決各種錯誤的更正能力㈣山2,3，如圖三所示的 明電路方塊圖。 X 對於傳統PGZ演算法，解卜3的PGZ解碼電路不能 正確執行t=l，2的更正，係因錯誤數目少於3時，會^ 生”除零”(dmded-by-zero)的問題。因為對於t=3所要解 算的方程式為 ---------------M i (請先閱讀背面之注意事項fjmlf寫本頁) 飞5； V σ2_ ~^1 S3 S4 S5 σι = SA S5 s6 σ〇_ 一-及 倘若錯誤數目少於3時，則矩陣中的行列將會 是線性相依（Linearly dependent)，即 —V =a 二 β 人 訂 經濟部智慧財產局員工消費合作社印製 其中α與^為常數。 因此，式（12)的分母項與3個分子項會為〇 w6 + w4 + w6 + m 〇 & w + w4 + w5 + 丨3从二 〇 + + 夕3 丨3S4 + W 夕4 + 夕1 夕3夕6 + 夕2 W = 〇 S}S4S6 + S2S4S5 + S3S3S5 + *^^5^5 + S3S3S6 + S3S4S4 = 0 (28) 同樣地，倘若錯誤數目少於2時，式（10)的分母項與 2個分子項會為0，即 W 十 = 〇 S}S3 + S2S2 = ο (29) W + w = ο 一旦計算σ值發生，，除零”(divided-by-zero)的問題 即 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐） 522657 A7 五、發明說明（11) 時’傳統PGZ演算法便無法正確執行錯誤的更正。所以 為了一克服此狀況，傳、统PGZ架構需要重複硬體電路，如 圖一所不’亚配合一檢查錯誤狀態的狀態機⑼价 machme)來達到各種錯誤的更正能力。 本發明為了整合同-份硬體電路以解決各種錯誤的 更正，而從式(28)與式(29)中進—步解析出重要資訊，這 些重要資訊將可被_決以錯誤數目，即各種錯誤數 目發生時 當t=0時， 5尸0 當 t=0，l 時， 田 t 〇，ι，2 時 而根據式（15)，得知 ’ 訂
Ai= S2 ^2~ S2S4 +S3S3 A3- S2S4S6+S4S4S4^S3S3S6^S2S5S5 所以，利用A〗、A2、A3即可判斷出錯誤數目，其 PGZ演算法的多模解碼程序如圖八所示。 /艮據本發明圖七所示簡化卜3 PGZ演算法無須F打 運算的RTL硬體架構，配合一控制g 1〇7來實施圖八所 示的多模解碼程相獲得錯誤數目m多模式脱 解碼電路lGG Lx同―份硬體電路的低成本架構解 決各種錯誤的更正(匕3)。圖九所示為本發明多模式PGZ 解碼電路100的R丁L硬體架構，其令包含·· FFAx15; FFM x27; FFI χ〇 根據本發明上述簡化PGZ演算法的推導基礎，在本 發明的一種實施例令，李得_所羅門解碼程序主要包含以 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐） 發明說明（l2) 下程序：計算接收資料的表徵值；解算關鍵方程式·，以 及評估=誤位置與錯紐價，其中解算_方程式的程 序係以簡化的pGZ演算法為基礎，對於Η的PGZ演曾 法先計算錯誤位置多項式（12)σ(χ)中的共同項，以減= 用FFA及FFM的數量，並進一步推導出解算過程备須 FFI的運算，以大幅減少計算的複雜度並降低硬體架盖 所佔用的面積資源，*且經由—多模解碼方法利用行列 式4以判斷獲得錯誤數目而實施多模式李得_所羅門解 碼矛羊序。 在本發_另—實施财H切得_所羅門解碼 "。匕3 .表彳玫計异器101，以計算接收資料的表徵 (Synd_e);關鍵方程式解算器1〇2，接收表徵計算哭輪 出的表徵方程式；以及錯誤位置與錯誤評價評估。二 接收關鍵方程式解算H輸出的錯誤位置方程式^ 錯方程式’以獲得錯誤位置與錯誤評價，·呈 鍵方程式解算器以簡化的PGZ解碼器為基礎，且阶 解碼架構包含FFA 1〇4與FFM丨G5，而無須m⑽，吻 解碼器包含-多模解碼控制器ϊ〇7，藉由行列式為 斷獲得錯誤數目，冑咖解碼架構可以處理㈣,U3 個錯决更正’遂以一多模式pGz解碼器⑽實施關 程式解算器1〇2。 乃 〜在詳細說明本發明的較佳實施例之後，熟悉該項技 術人士可清楚的瞭解’並在不脫離下述申請專利範圍與 f神下可進行各《化與改變，μ本發明亦不受限ς 說明書之實施例的實施方式。 [發明功效] 522657 A7 五 發明說明（η) 根據本發明所實施的多模 a 其方法係基於簡化的PGZ渾曾;^所羅門解碼器及 關鍵方程式解算器為-多模7=异自關鍵。方程式，其中 與FFM，甚至可以無須FFI，且該多丄，包, 含-多模解碼控制器，係藉由行 角午碼器包 項 數目，使其PGZ解碼架構可以處理以⑴個；：= ^，俾使本發明多模式李得_所羅⑽碼ϋ在VLSI ；:構 中為低成本且使用較少面積資源，而簡化的似淨曾、法 亦大幅降低計算複雜度，使_方程式 ^ 度提昇。 |迷 訂 、、不上所述丨發明具有諸多優良特性，並解決習知 技術在實務上與制上之缺失與不便，提出有效之解決 方法凡成貝用可罪之系統，進而達成新穎且附經濟效 益之價值，實已符合發明專利之申請要件，懇請釣局 能予詳審並賜准專利權益保障，以優惠民生實感德便。 線 本紙張尺度適用中國國家標準（CNS)A4規^x 297公爱） 五 發明說明（14) [圖式之簡單說明] 圖一為—李得·所羅π解碼料之流程圖。 圖二為傳統PGZ解碼架構利用重複的 到各種錯誤更正的電路錢圖。 來達 體 圖為本毛θ月夕拉《PGZ解碼架構利用同—十 電路解決各種錯誤更正的電路方塊圖。 V更 圖四為t=1PGZ解碼架構的RTL硬體架構圖。 圖五為t=2PGZ解碼架構的RTL硬體架構圖。 圖六為本發明簡化t=3PGZ演算法的Rn硬體架構 圖。 圖七為本發明簡化t=3 pGZ演算法無須m運算的 RTL硬體架構圖。 圖八為本發明多模解碼流程圖。 圖九為本發明多模式PGZ解碼器的RTL硬體架構 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐）
Claims (1)
- ^22657 六、申請專利範圍 L ^李得_所羅門解碼方法，細簡化的PGZ演算法為 二二=接收!!!的一表徵多項式s(x)後，由前 =價值多項杨），再得到—錯誤樣^^ ::接::料的不超過,個錯誤之更正，其中t為正： 數，该李得-所羅門解碼方法包含： 從該表徵？項式S⑻定義—表 徵向量〜，以解算1%= %;以及 ⑴”表 _ =表徵矩陣I的行列式值At，用料義一新 ^錯錢置多項式φ(χ)及—新的錯誤評價值多項式 (X)"刀別為Φ(ΧΗν⑻，Ω(χ)=Αίω(χ)，俾使可直接 ^法運算以及乘法運算來解算出錯誤位置與錯誤評 1貝值，而無須除法運算。 =請專利範圍第i項所述之李得，解碼方法， f中前述解算的步驟，更包含：藉由解算表 欲矩陣^是否線性相依，以判斷錯誤數目卜 3.如申請專利範圍第2項所述之李得_所羅⑽碼方法， 其中前述解算表徵矩陣‘是否線性相依的程序，更包 含：解算表徵矩陣‘的行列式值At，若㈣則t=1 ; 若A:邦則t=2 ;若八3邦則卜3。 4 訂 一種多模式李得-所羅Η解碼器，用以進行接收資料的 不超過，錯誤之更正’其中t為正整數，該多模式李 得-所羅門解碼器包含： ' -表徵計，以計算接收資料的_表 S(x); 、 —關鍵方程式解算器，具有-多模解碼控制器， 本紙張尺度適用中國國家標準（CNS)A4規格（21G X 297公釐— 522657 六 、申請專利範圍 ，接於该表徵計算器，用以由前述表徵多項式s(x)解 异出一錯誤位置多項式σ(χ)及一錯誤評價值多項式 ω(χ);以及 一评估器，耦接於該關鍵方程式解算器，由該錯 决位置多項式σ(χ)及該錯誤評價值多項式仍^)得到一 錯誤樣型； 其中岫述關鍵方程式解算器係以pGz解碼器為基 楚且5亥PGZ解碼器的RTL架構係包含FFA與FFM 而無須FFI “亥多模解碼控制器由表徵多項式s(x)定義 、，表欲矩陣心，，並藉該表徵心車&,的行列式值八 判斷獲得該錯誤數目t，以相應致能一相關解碼電路之 運作，俾使該多模式李得_所羅門解碼器可以處理多模 式之錯誤更正。 、 ..申=專利乾圍第4項所述之多模式李得-所羅Η解碼 為’，、中該多模式李得_所羅門解碼器係可處理多 t—1、2或3個錯誤更正。 圍第4項所述之多模式李得-所羅門解碼 岫述夕杈解碼控制器接收前述表徵矩陣夕 Π列式值A1、A2 ★用以判斷錯誤數目…二 ^ ，以相應致能該相關解碼電路之運作。 7. 圍第6項所述之多模式李得·所羅門解碼 消 :;器輪出==;gz解碼器根购 〜:::::=算_式…、2 8.::錯 =羅:：^ •縣，該多模式李 522657 A8 B8 C8 D8 六、申請專利範圍 得-所羅門解碼器包含： 一表徵計算器，以計算接收資料的一表徵多項式 S⑻； 一關鍵方程式解算器，具有一多模解碼控制器， 耦接於該表徵計算器，用以由前述表徵多項式S(x)解 算出一錯誤位置多項式σ(χ)及一錯誤評價值多項式 ω(χ);以及 一評估器，耦接於該關鍵方程式解算器，由該錯 誤位置多項式σ(χ)及該錯誤評價值多項式ω(χ)得到一 錯誤樣型； 其中前述關鍵方程式解算器係以P G Ζ解碼器為基 礎，且該PGZ解碼器的解算無須除法運算而提昇其運 算效率；該多模解碼控制器由表徵多項式S(x)定義一 表徵矩陣，並藉該表徵矩陣的行列式值At判斷 獲得該錯誤數目t，以相應致能一相關解碼電路之運 作，俾使該多模式李得-所羅門解碼器可以處理多模式 之錯誤更正。 — — — — — — · I I (請先閱讀背面之注意事項本頁) 訂· •線- 經濟部智慧財產局員工消費合作社印彻衣 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐）
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| TW091100683A TW522657B (en) | 2002-01-17 | 2002-01-17 | PGZ algorithm based multi-mode Reed-Solomon decoder and its method |
| US10/302,825 US7039853B2 (en) | 2002-01-17 | 2002-11-25 | Multi-mode Reed-Solomon decoder based upon the PGZ algorithm and associated method |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| TW091100683A TW522657B (en) | 2002-01-17 | 2002-01-17 | PGZ algorithm based multi-mode Reed-Solomon decoder and its method |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| TW522657B true TW522657B (en) | 2003-03-01 |
Family
ID=21688231
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| TW091100683A TW522657B (en) | 2002-01-17 | 2002-01-17 | PGZ algorithm based multi-mode Reed-Solomon decoder and its method |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US7039853B2 (zh) |
| TW (1) | TW522657B (zh) |
Families Citing this family (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| FR2863794B1 (fr) * | 2003-12-16 | 2006-03-03 | Canon Kk | Procedes et dispositifs de localisation d'erreurs pour les codes de geometrie algebrique |
| FR2865083B1 (fr) * | 2004-01-13 | 2006-04-07 | Canon Kk | Decodage pour code de geometrie algebrique associe a un produit fibre. |
| CN1773863B (zh) * | 2004-11-12 | 2010-06-02 | 中国科学院空间科学与应用研究中心 | 一种可用于大容量存储器的rs（256，252）码纠错译码芯片 |
| CN1773864B (zh) * | 2004-11-12 | 2010-05-05 | 中国科学院空间科学与应用研究中心 | 一种纠错能力为2的扩展里德—所罗门码的译码方法 |
| JP5422974B2 (ja) * | 2008-11-18 | 2014-02-19 | 富士通株式会社 | 誤り判定回路及び共有メモリシステム |
| CN101697490B (zh) * | 2009-10-16 | 2013-09-25 | 苏州国芯科技有限公司 | 一种应用在基于理德-所罗门码的ecc模块上的解码方法 |
| JP2016126813A (ja) * | 2015-01-08 | 2016-07-11 | マイクロン テクノロジー， インク． | 半導体装置 |
| CN111884680A (zh) * | 2020-06-20 | 2020-11-03 | 青岛鼎信通讯股份有限公司 | 一种应用于电力线载波通信系统的rs编码方法 |
-
2002
- 2002-01-17 TW TW091100683A patent/TW522657B/zh not_active IP Right Cessation
- 2002-11-25 US US10/302,825 patent/US7039853B2/en not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| US20030135810A1 (en) | 2003-07-17 |
| US7039853B2 (en) | 2006-05-02 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN111160548B (zh) | 计算装置以及计算方法 | |
| TW522657B (en) | PGZ algorithm based multi-mode Reed-Solomon decoder and its method | |
| JPH02500319A (ja) | データ修正方法および装置 | |
| CN102684709B (zh) | 一种译码方法及其译码装置 | |
| TW200522531A (en) | High performance CRC calculation method and system with a matrix transformation strategy | |
| KR19980027920A (ko) | 에러 정정 방법 및 장치 | |
| TW566008B (en) | Apparatus for solving key equation polynomials in decoding error correction codes | |
| JP2800723B2 (ja) | リードソロモン復号器の誤り位置検出回路 | |
| JPS63186338A (ja) | 誤り訂正回路 | |
| RU2417409C2 (ru) | Отказоустойчивый процессор | |
| CN114359080A (zh) | 图像恢复方法、存储介质、电子设备和计算机程序产品 | |
| TW427077B (en) | Error correcting method and error correcting apparatus | |
| WO1994015406A1 (fr) | Procede et circuit de correction d'erreurs | |
| Tang et al. | A new single-error correction scheme based on self-diagnosis residue number arithmetic | |
| CN112953570B (zh) | 一种纠错解码方法、装置、设备及计算机可读存储介质 | |
| JPH10322226A (ja) | リードソロモン復号方法 | |
| JP2907138B2 (ja) | 誤り訂正の演算処理方法及び処理回路 | |
| EP0295949B1 (en) | Method and apparatus for decoding Reed-Solomon code | |
| Yan et al. | Fast and low-complexity decoding algorithm and architecture for quadruple-error-correcting RS codes | |
| JP2705162B2 (ja) | 演算処理装置 | |
| RU2758065C1 (ru) | Отказоустойчивый процессор с коррекцией ошибок в байте информации | |
| CN114448634B (zh) | 用于椭圆曲线加密的密钥 | |
| Liu et al. | A view of Gaussian elimination applied to early-stopped Berlekamp–Massey algorithm | |
| JPH10308675A (ja) | リードソロモン復号装置 | |
| JPH10285052A (ja) | ユークリッド復号法およびユークリッド復号回路 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| GD4A | Issue of patent certificate for granted invention patent | ||
| MK4A | Expiration of patent term of an invention patent |