JPH01315834A - 誤り訂正符号の復号化回路 - Google Patents
誤り訂正符号の復号化回路Info
- Publication number
- JPH01315834A JPH01315834A JP63148731A JP14873188A JPH01315834A JP H01315834 A JPH01315834 A JP H01315834A JP 63148731 A JP63148731 A JP 63148731A JP 14873188 A JP14873188 A JP 14873188A JP H01315834 A JPH01315834 A JP H01315834A
- Authority
- JP
- Japan
- Prior art keywords
- circuit
- finite field
- error
- memory
- chien search
- Prior art date
- Legal status (The legal status 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 status listed.)
- Pending
Links
Landscapes
- Detection And Correction Of Errors (AREA)
- Error Detection And Correction (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
［産業上の利用分野］
この発明は、誤り訂正符号の復号化回路に関するもので
ある。
ある。
［従来の技術］
さて、一般には、計算機による種々の処理を実行するに
当り、符号語中の多数のバイトの誤りを訂正するシステ
ムが必要であり、種々のものが提案されている。
当り、符号語中の多数のバイトの誤りを訂正するシステ
ムが必要であり、種々のものが提案されている。
そして、かかる誤り訂正システムにおいて複数のバイト
エラーの復号化方法は一般に次のようにして行なわれる
。まず、エラーシンドロームを計算し、ついでこのエラ
ーシンドロームより誤り位置多項式の係数を決定してか
ら、チェンサーチ（Ｃｈｉｅｎ ５ｅａｒｃｈ）により
誤り位置多項式から誤り位置を特定し、各誤り位置に対
してバイトエラー値を決定するのである。
エラーの復号化方法は一般に次のようにして行なわれる
。まず、エラーシンドロームを計算し、ついでこのエラ
ーシンドロームより誤り位置多項式の係数を決定してか
ら、チェンサーチ（Ｃｈｉｅｎ ５ｅａｒｃｈ）により
誤り位置多項式から誤り位置を特定し、各誤り位置に対
してバイトエラー値を決定するのである。
ところで、第３図は「符号理論」（昭晃堂発行）２６３
頁図７・２に記載された従来のものと類似のチェンサー
チ回路を示すブロック図で、この回路はＢＣＨ符号（Ｂ
ｏｓｓ Ｃｈａｕｄｈｕｒｉ Ｈｏｃｑｕｅｎｇｈｅ＋
１Ｃｏｄｅｓ）などで用いられる回路である。この第３
図において、１はｎビットのレジスタ、２は加算回路、
３〜７はそれぞれガロア体ＧＦ（２”） （ｎは自然数
）上の符号語についての定数乗算回路、８は誤り位置多
項式の和がゼロであることを知らせる出力端子である。
頁図７・２に記載された従来のものと類似のチェンサー
チ回路を示すブロック図で、この回路はＢＣＨ符号（Ｂ
ｏｓｓ Ｃｈａｕｄｈｕｒｉ Ｈｏｃｑｕｅｎｇｈｅ＋
１Ｃｏｄｅｓ）などで用いられる回路である。この第３
図において、１はｎビットのレジスタ、２は加算回路、
３〜７はそれぞれガロア体ＧＦ（２”） （ｎは自然数
）上の符号語についての定数乗算回路、８は誤り位置多
項式の和がゼロであることを知らせる出力端子である。
また、第２図は従来のＢ ＣＨ符号の復号化回路の一例
を示す回路図である。この第２図において。
を示す回路図である。この第２図において。
９は受信符号語を遅延するための多段シフトレジスタ、
１０は加算回路、１１はシンドローム計算回路、１２は
誤り位置多項式導出回路、１３はチェンサーチ回路、１
４は同期回路、１５はシーケンス制御回路、１６は受信
符号語の入力端子、１７は訂正した情報の出力端子であ
る。
１０は加算回路、１１はシンドローム計算回路、１２は
誤り位置多項式導出回路、１３はチェンサーチ回路、１
４は同期回路、１５はシーケンス制御回路、１６は受信
符号語の入力端子、１７は訂正した情報の出力端子であ
る。
第３図に示すチェンサーチ回路を用いた第２図の２元Ｂ
ＣＨ符号の復号化回路の動作を説明する。
ＣＨ符号の復号化回路の動作を説明する。
まず、入力端子１６より受信符号語が入力されて、同期
回路１４へ入力されると、この同期回路１４が受信符号
語の先頭を検出する。そして、この検出結果に基づきシ
ーケンス制御回路１５が動作する。
回路１４へ入力されると、この同期回路１４が受信符号
語の先頭を検出する。そして、この検出結果に基づきシ
ーケンス制御回路１５が動作する。
一方、受信符号語は、同期回路１４と同時にシンドロー
ム計算回路１１．多段シフトレジスタ９にも入力される
。その後、このシンドローム計算回路１１で計算された
シンドロームは、誤り位置多項式導出回路１２に入力さ
れ、誤り位置多項式が導出される。この誤り位置多項式
導出回路１２からの誤り位置多項式はチェンサーチ回路
１３に入力され、チェンサーチを実行する。
ム計算回路１１．多段シフトレジスタ９にも入力される
。その後、このシンドローム計算回路１１で計算された
シンドロームは、誤り位置多項式導出回路１２に入力さ
れ、誤り位置多項式が導出される。この誤り位置多項式
導出回路１２からの誤り位置多項式はチェンサーチ回路
１３に入力され、チェンサーチを実行する。
ここで、第３図に示すチェンサーチ回路１３では、誤り
多項式をσ（Ｘ）＝σ。＋σｘｘ＋σ２ｘ２＋・・・・
＋σｔ−４ｘ”とすれば、はじめにこの誤り位置多項式
の各項の計数をｎビットのレジスタ１にそれぞれセット
してから、各レジスタ１にクロックを入力してゆくこと
が行なわれる。その後、クロックがいくつか入力される
と、出力端子８の出力がゼロになるが、この時のクロッ
ク入力数をｉとすると、α′がσ（ｊ）の根となるよう
になっている。
多項式をσ（Ｘ）＝σ。＋σｘｘ＋σ２ｘ２＋・・・・
＋σｔ−４ｘ”とすれば、はじめにこの誤り位置多項式
の各項の計数をｎビットのレジスタ１にそれぞれセット
してから、各レジスタ１にクロックを入力してゆくこと
が行なわれる。その後、クロックがいくつか入力される
と、出力端子８の出力がゼロになるが、この時のクロッ
ク入力数をｉとすると、α′がσ（ｊ）の根となるよう
になっている。
かかる処理をチェンサーチという。
これと同時に、多段シフトレジスタ９の出力側に受信符
号語が先頭から順次出力される。この出力はチェンサー
チ回路１３でのチェンサーチの実行と同期しており、こ
のチェンサーチにより誤り位置多項式σ（Ｘ）の根であ
る二とが検出された時。
号語が先頭から順次出力される。この出力はチェンサー
チ回路１３でのチェンサーチの実行と同期しており、こ
のチェンサーチにより誤り位置多項式σ（Ｘ）の根であ
る二とが検出された時。
多段シフトレジスタ９の出力を加算回路１０により訂正
するのである。
するのである。
［発明が解決しようとする課題］
従来の誤り訂正符号の復号化回路は以上のように構成さ
れているので、距離の長い符号語では誤り位置多項式導
出回路の構成が複雑となり復号に要する時間も長くなる
ため、多段シフトレジスタの段数が大きなものになると
いう問題点があった。
れているので、距離の長い符号語では誤り位置多項式導
出回路の構成が複雑となり復号に要する時間も長くなる
ため、多段シフトレジスタの段数が大きなものになると
いう問題点があった。
この発明は上記のような問題点を解消するためになされ
たもので、従来必要としていた多段シフトレジスタを用
いなくても復号化を可能にした誤り訂正符号の復号化回
路を得ることを目的とする。
たもので、従来必要としていた多段シフトレジスタを用
いなくても復号化を可能にした誤り訂正符号の復号化回
路を得ることを目的とする。
［課題を解決するための手段］
この発明に係る誤り訂正符号の復号化回路は、多段シフ
トレジスタの代わりに、受信符号語を、記憶する遅延用
メモリを設けて誤り位置を計算できるようにするととも
に、チェンサーチ回路部と同期して動作する有限体の元
発生回路を設けて遅延用メモリ内の誤り位置アドレスに
対応する有限体の元を算出することができるようにした
ものである。
トレジスタの代わりに、受信符号語を、記憶する遅延用
メモリを設けて誤り位置を計算できるようにするととも
に、チェンサーチ回路部と同期して動作する有限体の元
発生回路を設けて遅延用メモリ内の誤り位置アドレスに
対応する有限体の元を算出することができるようにした
ものである。
［作 用］
この発明における誤り訂正符号の復号化回路では、遅延
用メモリによって受信符号語が記憶されるとともに、有
限体の元発生回路がチェンサーチ回路部と同期して動作
することにより、遅延用メモリ内の誤り位置に対応した
有限体の元が得られ、多段シフトレジスタを用いずに復
号が可能になる５［発明の実施例］ 以下、この発明の一実施例を図について説明する。さて
、ガロア体０Ｆ（２”）における符号語のエラーを訂正
するリードソロモン符号には、生成多項式の根に対応す
る複数のチエツクポイントがあるが、本実施例の場合も
、第２，３図に示したものと同様、このリードソロモン
符号において誤り位置多項式の根を求めるチェンサーチ
回路をもった誤り訂正符号の復号化回路についてのもの
である。
用メモリによって受信符号語が記憶されるとともに、有
限体の元発生回路がチェンサーチ回路部と同期して動作
することにより、遅延用メモリ内の誤り位置に対応した
有限体の元が得られ、多段シフトレジスタを用いずに復
号が可能になる５［発明の実施例］ 以下、この発明の一実施例を図について説明する。さて
、ガロア体０Ｆ（２”）における符号語のエラーを訂正
するリードソロモン符号には、生成多項式の根に対応す
る複数のチエツクポイントがあるが、本実施例の場合も
、第２，３図に示したものと同様、このリードソロモン
符号において誤り位置多項式の根を求めるチェンサーチ
回路をもった誤り訂正符号の復号化回路についてのもの
である。
第１図（ａ）、（ｂ）において、２３は誤り位置多項式
や誤り数値多項式を導出するといったような有限体の演
算が可能な有限体演算回路、２４は符号語の復号化を行
なうために受信符号語を艙憶する遅延用メモリ、２５は
シンドローム計算回路であり、２６はチェンサーチ回路
である。
や誤り数値多項式を導出するといったような有限体の演
算が可能な有限体演算回路、２４は符号語の復号化を行
なうために受信符号語を艙憶する遅延用メモリ、２５は
シンドローム計算回路であり、２６はチェンサーチ回路
である。
このチェンサーチ回路２６は、第１図（ｂ）に示すごと
〈従来のチェンサーチ回路１３と同じ機能を発揮するチ
ェンサーチ回路部１８のほか、このチェンサーチ回路部
１８と同期して動作する有限体の元発生回路１９をそな
えている。
〈従来のチェンサーチ回路１３と同じ機能を発揮するチ
ェンサーチ回路部１８のほか、このチェンサーチ回路部
１８と同期して動作する有限体の元発生回路１９をそな
えている。
なお、第１図（ｂ）において、２０はクロック入力端子
、２１は有限体の元発生回路１９の出力端子、２２は出
力端子２１の出力が誤り位置多項式の根を検出したこと
を示す出力端子である。
、２１は有限体の元発生回路１９の出力端子、２２は出
力端子２１の出力が誤り位置多項式の根を検出したこと
を示す出力端子である。
また、有限体演算回路２３．遅延用メモリ２４およびチ
ェンサーチ回路２６は、第１図（ａ）に示すごとくそれ
ぞれデータバス２７とコンＩ・ロールバス２８とで接続
され、特に、チェンサーチ回路２６のクロック入力端子
２０はデータバス２７に接続され、チェンサーチ回路２
６の出力端子２１゜２２はコントロールバス２８に接続
されている。
ェンサーチ回路２６は、第１図（ａ）に示すごとくそれ
ぞれデータバス２７とコンＩ・ロールバス２８とで接続
され、特に、チェンサーチ回路２６のクロック入力端子
２０はデータバス２７に接続され、チェンサーチ回路２
６の出力端子２１゜２２はコントロールバス２８に接続
されている。
さらに、メモリ２４の片側のポートは１１部データバス
２９と接続されており、受信符号語の入力とその訂正後
の出力を行なうようになっている。
２９と接続されており、受信符号語の入力とその訂正後
の出力を行なうようになっている。
次にこの回路の動作について説明する。受信符号語は外
部データバス２９より遅延用メモリ２４に入力される。
部データバス２９より遅延用メモリ２４に入力される。
その後、このメモリ２４に入力された受信符号語はシン
ドローム計算回路２５でシンドロームを計算される。ま
た、有限体演算回路２３ではそのシンドロームから誤り
位置多項式と誤り数値多項式とが導出される。
ドローム計算回路２５でシンドロームを計算される。ま
た、有限体演算回路２３ではそのシンドロームから誤り
位置多項式と誤り数値多項式とが導出される。
そして、チェンサーチ回路２６は１．誤り位置多項式を
有限体演算回路２３から入力し、そのチ２ンサーチ回路
部１８でチェンザーチを始め、誤り位置多項式の根に対
応する有限体の元を有限体演算回路２３に戻す。この出
力は、チェンサーチ回路２６においてチェノサーチ回路
部１日と同期し動作する有限体の元発生回路１９から出
力されるが、このとき、有限体の元発生回路１９は、１
７に始多項式の根をαとすると、１→α“−→α′“−
２→・・・のように動作する。
有限体演算回路２３から入力し、そのチ２ンサーチ回路
部１８でチェンザーチを始め、誤り位置多項式の根に対
応する有限体の元を有限体演算回路２３に戻す。この出
力は、チェンサーチ回路２６においてチェノサーチ回路
部１日と同期し動作する有限体の元発生回路１９から出
力されるが、このとき、有限体の元発生回路１９は、１
７に始多項式の根をαとすると、１→α“−→α′“−
２→・・・のように動作する。
ごれにより、有限体演算回路２３は、チェンサーチの結
果から誤り数値を算出１１、 先＆、Ｔチェンチー・−
子回路２６から受けとった有限体の元で示される遅延用
メモリ２４内の内容を訂正する５、この際のデータやコ
ントロール信号の授受はデータバス２７およびコントロ
ールバス２８を通じ行なわれている。その後はメモリ２
４を通じ外部データバス２９へ訂正後の出力を出す。
果から誤り数値を算出１１、 先＆、Ｔチェンチー・−
子回路２６から受けとった有限体の元で示される遅延用
メモリ２４内の内容を訂正する５、この際のデータやコ
ントロール信号の授受はデータバス２７およびコントロ
ールバス２８を通じ行なわれている。その後はメモリ２
４を通じ外部データバス２９へ訂正後の出力を出す。
このように、チェンサーチ回路部１８と同期して動作す
る有限体の元１９によってメモリ２４内の誤り位置アド
レスに対応する有限体の元が算出され、有限体演算回路
２３や受信符号語を記憶している遅延用メモリ２４を介
し、誤り訂正符号を復号化して出力することができるの
で、従来のような多段シフトレジスタが不要となる。
る有限体の元１９によってメモリ２４内の誤り位置アド
レスに対応する有限体の元が算出され、有限体演算回路
２３や受信符号語を記憶している遅延用メモリ２４を介
し、誤り訂正符号を復号化して出力することができるの
で、従来のような多段シフトレジスタが不要となる。
なお、上記実施例は、誤り数値の計算を必要とする非２
元符号語の復号化の場合であるが、誤り数値の計算を必
要としない２元符号語の復号化にも適用可能で、上記実
施例と同様の効果を奏する。
元符号語の復号化の場合であるが、誤り数値の計算を必
要としない２元符号語の復号化にも適用可能で、上記実
施例と同様の効果を奏する。
［発明の効果］
以上のようにこの発明によれば、チェンサーチ回路部と
有限体の元発生回路とを同期して動作させることにより
、多段シフトレジスタの代わりに。
有限体の元発生回路とを同期して動作させることにより
、多段シフトレジスタの代わりに。
汎用メモリを用いて復号化回路を構成できるので５従来
困難とされていた距離の長い符号語の復号化回路が符号
長分のメモリを用意するだけで、比較的簡単に構成でき
る効果がある。
困難とされていた距離の長い符号語の復号化回路が符号
長分のメモリを用意するだけで、比較的簡単に構成でき
る効果がある。
第１図（ａ）、（ｂ）はこの本発明の一実施例による誤
り訂正符号の復号化回路を示すもので、第１図（ａ）は
その全体構成を示すブロック図、第１図（ｂ）はそのチ
ェンサーチ回路を示すブロック図であり、第２，３図は
従来の誤り訂正符号の復号化回路を示すもので、第２図
はその全体構成を示すブロック図、第３図はそのチェン
サーチ回路を示すブロック図である。 図において、１８−チェンサーチ回路部、１９・−有限
体の元発生回路、２０−クロック入力端子、２１−有限
体の元発生回路出力端子、２２〜・チェノサーチ回路部
出力端子、２３・−有限体演算回路、２４−遅延用メモ
リ、２５−シンドローム計算回路、２６−・−チェンサ
ーチ回路、２７・−データバス、２８−コントロールバ
ス、２９・・−外部データバス。 なお１図中、同一符号は同一、又は相当部分を示す。
り訂正符号の復号化回路を示すもので、第１図（ａ）は
その全体構成を示すブロック図、第１図（ｂ）はそのチ
ェンサーチ回路を示すブロック図であり、第２，３図は
従来の誤り訂正符号の復号化回路を示すもので、第２図
はその全体構成を示すブロック図、第３図はそのチェン
サーチ回路を示すブロック図である。 図において、１８−チェンサーチ回路部、１９・−有限
体の元発生回路、２０−クロック入力端子、２１−有限
体の元発生回路出力端子、２２〜・チェノサーチ回路部
出力端子、２３・−有限体演算回路、２４−遅延用メモ
リ、２５−シンドローム計算回路、２６−・−チェンサ
ーチ回路、２７・−データバス、２８−コントロールバ
ス、２９・・−外部データバス。 なお１図中、同一符号は同一、又は相当部分を示す。
Claims (1)
- ガロア体ＧＦ（２＾ｎ）上の符号語についての誤り位置
多項式の根を求めるチェンサーチ回路部をそなえた誤り
訂正符号の復号化回路において、同チェンサーチ回路部
と同期して動作する有限体の元発生回路が設けられると
ともに、受信符号語を記憶する遅延用メモリが設けられ
たことを特徴とする誤り訂正符号の復号化回路。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP63148731A JPH01315834A (ja) | 1988-06-16 | 1988-06-16 | 誤り訂正符号の復号化回路 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP63148731A JPH01315834A (ja) | 1988-06-16 | 1988-06-16 | 誤り訂正符号の復号化回路 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH01315834A true JPH01315834A (ja) | 1989-12-20 |
Family
ID=15459346
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP63148731A Pending JPH01315834A (ja) | 1988-06-16 | 1988-06-16 | 誤り訂正符号の復号化回路 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH01315834A (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2009100369A (ja) * | 2007-10-18 | 2009-05-07 | Toshiba Corp | 誤り検出訂正回路、半導体メモリコントローラ、および誤り検出訂正方法 |
Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS6394720A (ja) * | 1986-10-08 | 1988-04-25 | Mitsubishi Electric Corp | 誤り訂正符号の復号化回路 |
-
1988
- 1988-06-16 JP JP63148731A patent/JPH01315834A/ja active Pending
Patent Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS6394720A (ja) * | 1986-10-08 | 1988-04-25 | Mitsubishi Electric Corp | 誤り訂正符号の復号化回路 |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2009100369A (ja) * | 2007-10-18 | 2009-05-07 | Toshiba Corp | 誤り検出訂正回路、半導体メモリコントローラ、および誤り検出訂正方法 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH0831803B2 (ja) | 誤り訂正のための方法と装置 | |
| WO2000057561A1 (en) | Pipelined high speed reed-solomon error/erasure decoder | |
| US5805617A (en) | Apparatus for computing error correction syndromes | |
| US4751704A (en) | Method and apparatus for decoding BCH code | |
| KR970004515B1 (ko) | 리드-솔로몬 복호기의 오류위치다항식 연산방법 및 장치 | |
| KR19990016134A (ko) | 고속 시리얼 에러 위치 다항식 계산회로 | |
| CN1653699B (zh) | 软判定解码里德-索洛蒙码的方法 | |
| JP2001274694A (ja) | 復号装置及び復号方法 | |
| JP3245290B2 (ja) | 復号方法とその装置 | |
| KR100281946B1 (ko) | 신드롬 계산 장치 | |
| JPH01315834A (ja) | 誤り訂正符号の復号化回路 | |
| JPS6394720A (ja) | 誤り訂正符号の復号化回路 | |
| JP3233502B2 (ja) | 復号化装置 | |
| JP3398560B2 (ja) | 短縮化誤り訂正復号装置 | |
| JPS5975732A (ja) | 復号器 | |
| KR100335482B1 (ko) | 에러정정시스템 | |
| JP2752510B2 (ja) | 誤り訂正復号器 | |
| JP2600683B2 (ja) | リード・ソロモン符号の復号方法 | |
| KR940010434B1 (ko) | 리드-솔로몬 에러정정코드 시스템 | |
| JP2600681B2 (ja) | リード・ソロモン符号の復号方法 | |
| JP2599001B2 (ja) | 誤り訂正処理回路 | |
| JP2858538B2 (ja) | 再シンドロームチェック方式 | |
| KR100246342B1 (ko) | 리드솔로몬오류수정장치 | |
| KR100247075B1 (ko) | 리드솔로몬 디코더에 있어서 고속시리얼 에러타위치 다항식 계산회로 | |
| JPH09162753A (ja) | 符号語の復号方式 |