JPS63267018A - ロングデイスタンスコ−ドの誤り訂正方式および誤り訂正装置 - Google Patents
ロングデイスタンスコ−ドの誤り訂正方式および誤り訂正装置Info
- Publication number
- JPS63267018A JPS63267018A JP10016987A JP10016987A JPS63267018A JP S63267018 A JPS63267018 A JP S63267018A JP 10016987 A JP10016987 A JP 10016987A JP 10016987 A JP10016987 A JP 10016987A JP S63267018 A JPS63267018 A JP S63267018A
- Authority
- JP
- Japan
- Prior art keywords
- error
- matrix
- long distance
- equation
- row
- 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
- Error Detection And Correction (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
〔技術分野〕
ＢＣＨ符号、リードソロモン符号などの誤り訂正符号を
用い、２５５ワードなどの多数のワードをブロックとし
てこのブロックに含まれる多数ワードの誤り訂正を行う
データの符号化、復号化が光ディスクなどの記録・再生
あるいはデータ伝送などに使用されている。 本発明は、このような１つの訂正系列で多数の誤り訂正
が可能な符号（ロングディスタンスコード）を高速で復
号するとともに誤り訂正を行うための方式および誤り訂
正装置を提供するものである。 （従来技術） ＢＣＨ符号あるいはリードソロモン符号などによって多
数ワードの誤りを訂正するためには受信データからシン
ドロームを生成して誤り位置多項式の係数を求める必要
がある。 すなわち、この誤り位置多項式は、誤り位置に対応する
値を根として持つ多項式であり、誤り位置多項式の各項
の係数を求めることによって誤りの生じたデータの位置
を算出することができる。 従来このような誤り位置多項式の係数を求める方式とし
てピーターソン、バーレカンプ・マツシイ、ユークリッ
ド互除法などが知られているが、ハードウェアによって
構成しようとするとそのハードウェアの量が大きいため
に実用化に適したハードを得ることが困難であり、また
、ソフトウェアによって処理を行なうには判断が難しく
処理速度に問題が生じる。 〔目 的〕 本発明は、上記のようなロングディスタンスコードを高
速で復号するとともに、ハード化に適したロングディス
タンスコードにおける誤り訂正方式および装置を提供す
ることを目的とする。 −〔構 成〕 本発明の構成について、それぞれが８ビツトで構成され
る２５５ワードからなるブロックの、４ワード訂正可能
な、２５６元ガロア体ＧＦ （２” ）のリードソロモ
ン符号に適用した実施例に基づいて説明する。 リードソロモン符号の復号は、次の５つのステップによ
って行われる。 （１）受信データからシンドロームを求める。 （２） このシンドロームから誤り位置多項式を求め
る。 （３） この誤り位置多項式から誤り位置を求める。 （４） 誤り位置から誤りパターンを求める。 （５）誤り位置と誤りパターンとによって誤り訂正を行
う。 本発明においては、上記（２）のシンドロームからの誤
り位置多項式の算出、および（４）の誤り位置から誤り
パターンの算出の双方を同一の処理方法によって高速で
求められる復号方式を提供する。 以下の実施例における演算（＋で示す加算、×で示す乗
算および÷または／で示す除算）はいずれもモデュロ２
の演算であって、一般にテーブルを参照することによっ
て実行されものであり、そのテーブルの一例として、Ｃ
Ｆ （２’ ）上でＧ（Ｘ）＝Ｘ” ＋Ｘ’ ＋Ｘ’
＋Ｘ雪＋１を法とする上記演算のテーブルの一部を第８
図に例示する。 なお、同図（ａ）は加算テーブル、同図中）は乗算テー
ブル、同図（Ｃ）は乗算テーブルであらて、この除算テ
ーブルの最上列は被除数、最左欄は除数である。 誤りを含んだ受信データの各語の値をｒ６’ｗｒ２５４
とすると、受信データＲ（ｘ）は次の（１）式で与えら
れる。 Ｒ（ｘ）＝ ｒ（１ｘ”’ ＋ ｒ １ ｘ”３ ＋
−−−−＝−−−−−−−−−＋ｒ ａｓｓ Ｘ ’
＋ ｒ ｚｓ４−・−−−−−（１）この受信デー
タから生成されるシンドローム８１〜Ｓ７は、この（１
）式のＸにα０１αＩ 、 、−、−、、−α７をそれ
ぞれ代入した次式のものである。 Ｓ＠ ＝Ｒ（α’ ） ＝ｒ６ ＋ｒ、＋−−−−・・
＋ｒ０３ ＋ｒ １％４ ＳＩ＝Ｒ（α’ ）ｘｒｏａ”’ ＋ｒ、ｅｘ”” ＋
・−”’ ”’ ＋ ｒ ｔｓ３α’＋ｒｔｓａＳ＊
−Ｒ＜ａ” ）＝ｒｅ ｃｘ”” ＋ｒ、ｏｒ”””
”” ”” ＋ ｒ ｔｓ３α”” ＋ｒｚｓｎＳ ？
” Ｒ（ＣＸ’ ） −ｒ、 αｔ口°’ ＋ｒ、
αＨ，、。 ＋・・・”’ｒ０３α１° ”ｒｇｓ４・・・・・・（
２） 誤り位置多項式σ（ｘ）は次の（３）式のように定義さ
れる。 σ（ｘ）＝ （ｘ＋Ｖ１ ） （ｘ＋Ｖ２ ） （
ｘ＋Ｖ３ ）（ｘ＋Ｖ４） ＝ｇ’ ＋ｔＦ、ｇ’ ＋σｚ Ｘ” ＋Ｉ、Ｘ＋ｅｌ
。 ・・・・・・（３） ここでｖ１〜ｖ４は誤り位置、すなわち誤りのあるワー
ド位置を示すもので、（１）式のＸのべき乗の値に対応
しており、一般的にはテーブルを参照することにより１
０進′表現によるワード位置が求められるものであって
、このテーブルの一例として、第８図の演算テーブルと
同様に、ＣＦ （２’ ）上でＧ（，１）＝ｘ” ＋ｘ
’ ＋ｘ’ ＋ｘ” ＋ｌを法とするαのべき乗表現と
１０進表現との対応を示すテーブルの一部を第９図に示
しである。 このテーブルによって、ｖ＝ｔのときはαＯ−１で最下
位のｒ□、の項、Ｖ＝４のときはα２＝４でｒ ｔ％ｔ
の項のようになる。 なお、この実施例では、Ｓｏ〜Ｓフの８種のシンドロー
ムを用いており、４つの誤り位置と４つの誤りパターン
とを表す８つの未知数は、この８種のシンドロームを用
いて演算することによって算出できるものであるが、誤
りパターンを先に求めると同一の値、すなわち同一の誤
りパターンがあった場合に誤り位置を算出できなくなる
恐れがあるので、誤り位置を先に求めるのが一般的であ
る。 また、この誤り位置は２５５のワードの位置を示すもの
であるから０〜２５５（２進８桁）の値であり、誤りパ
ターンは１ワード８ビツト内の誤りのパターンとして“
０００００００１”から“１１１１１１１１″の２５５
通りであり、誤りの存在が検出されたワードにこのパタ
ーンを加算することによって誤りが訂正される。 誤り位置多項式である（３）式の各係数σ０〜σ３の値
とシンドロームＳｏ、〜Ｓ７との間には次の（４）式の
ような関係が成り立つ。 ・−・・−・・（４） この（４）式の右辺を左辺に移項して行列の形を変える
と次の（５）式になる。 ・・・−・・−・（５） この（５）式の両辺に、ある行列Ａを左から乗じて次の
（６）式のように変形すると、σ０〜σ３は（７）で示
すように求められる。 一一一一一・−・（６） σｏ ”ａ。 σ１−ａ １ σ２ ＝ａ３ σ３−ａ３ −・・・−・−（７）ところ
で、上記のように（５）式を（６）式に変形するために
両辺に乗じた行列Ａは右辺の値が０であるから任意のも
のでよく、結局、（５）式のｓｏ ％Ｓ？で表される行
列を（６）式の形になるように左基本変形すればよいこ
とになる。 この左基本変形をＳｏ−ｗ５７の値がそれぞれ０゜１５
．８５，１１５，１９３，１１５，１６１および２３１
の場合を例に採って具体的に説明する。 （５）式の左辺第１項は次の（８）式で表される。 この式（８）を（６）式の形に変形する第１段階として
その第１列が（６）式の左辺第１項の第１列のになるよ
うに変形を行う。 （８）式の第１列第１行の値が０であるから、第１列が
０でない行と置き換えるために、第２行と第１行とを入
れ換えると次の（９）式になる。 次に第１列第１行の値１５を１にするために、第１行の
各列の値をこの１５で割るモデエロ２の演算を行うと次
の（１０）式になる。 次に、第３および第４行目の第１列の値を０にするため
に、第３行目については第１行の値を８５倍してからこ
の第３行目の各値にモデュロ２の加算を、また第４行目
については第１行の値を１１５倍してからこの第３行目
の各値にモデエロ２の加算を行うことによって次の（１
１）式を得る。 次に、上記式（８）を（６）式の形に変形する第２段階
としてその第２列が（６）式の左辺第１項の第２列と同
じ にするために、上記同様の手法として、第２列目をその
第２行の１５でモデエロ２の除算を行い、次いでこの第
２行目の値を８７倍して第３行目とモデュロ２の加算を
、またこの第２行目の値を５８倍して第４行目とモデュ
ロ２の加算を行うことによって下記の（１２）式を得る
。。 次に、上記式（８）を（６）式の形に変形する第３段階
としてその第３列が（６）式の左辺第１項の第３列と同
じ にするために、上記第１段階と同様に第３列目が０の第
３行と第４行とを入れ換えて、 とし、第３列目をその第３行の１０１でモデュロ２の除
算を行うとともに、この得られた第３行目の値を６２倍
して第１行目とモデエロ２の加算を行い、またこの第３
行目の値を１５倍して第２行目とモデュロ２の加算を行
うことによって下記の（１４）式を得る。 次に、上記式（８）を（６）式の形に変形する最後の段
階としてその第４列が（６）式の左辺第１項の第４列と
同じ にするために、第４行をその第４列の１０１でモデュロ
２の除算を行い、得られた第４行目の値を８７倍して第
１行目にモデエロ２の加算を、また１０７倍して第２行
目にモデュロ２の加算を行うことによって前記の（６）
式と同一の形の下記（１５）式が得られる。 これによって、（６）式について説明したように、σｏ
＝６４ σ５＝１２０ σ２−５４ σｓ ＝ １５ −−−−−−・（１６
）が得られ、これらσの値を（３）式に示した誤り位置
多項式に代入することによって ｘ’ ＋１５ｘ’＋５４ｘ”＋１２０ｘ＋６４ −−−
−−−−（１７）が得られる。 この（１７）式をチェノのアルゴリズムなどによって解
いてその根を求めると誤り位置を検出することができ、
この（１７）式の場合には、ｘ−１，２，４，８・・・
・−・−・（１８）・であるから、前述のように（１）
式のｒ！Ｓ４＊’□３ 。 ｒ ｚｓｚの項およびｒ ｆｆｉ！ＩＩの項に誤りがあ
ることになる。 以上のようにして誤り位置が検出されたので、次に誤り
パターン、すなわち正しいデータのパターンを検出する
手法について説明する。 誤り位置ｖ１の誤りパターンがＹｔ、誤り位置ｖ２の誤
りパターンがＹ２のように、誤り位置■１ 、Ｖ２ 、
ｖｓ 、Ｖ４がそれぞれ誤りパターンＹ１、Ｙ２、Ｙ３
、Ｙ４に対応するものとする。 このとき、誤りパターンＹ１〜Ｙ４、誤り位置ｖ１〜ｖ
４およびシンドロームＳｏ−ｗｓｓとの間には次の関係
が成り立つ。 ・・−・−（１９） この（１９）式の右辺を、先に（４）式から（５）式に
変換したと同様に左辺に移項して行列の形を変えると次
の（２０）式になる。 ・・・・・・ （２０） この（２０）式の左辺の左側の行列に上記誤り位置とし
てｖｌ−１、ｖ２＝２、ｖ３＝４、ｖ４＝８．５ｏ＝０
．５ｔ＝１５．５２＝８５．５ｓ＝１１５をそれぞれ代
入し、（８）式ないしく１５）式で説明したと同様の左
基本変形を行うと次の（２１）式に示すように変形され
る。 この行列の第４列の値によって誤りパターンＹ１〜Ｙ４
は次の（２２）式のようになる。 Ｙ、＝１ Ｙ２＝１ Ｙｓ＝１ Ｙ４＝１ ・・・・・・（２２）
これによって、誤りパターンはいずれもｌであることが
検出されるので、誤りがある１、２．４．８番目のワー
ドについてパターン１の訂正を行えばよい。 なお、この誤りパターンＹの値は、その誤りパターンを
１０進数で表しており、上記パターン１は、“００００
０００１″を誤り位置のワードにモデュロ２で加算すれ
ばよい。 次に、上記の４ワード訂正が可能な符号によって３ワー
ドの誤りを訂正する過程について例を挙げて説明する。 誤りの例として、誤り位置を最後の３項とし、誤りパタ
ーンＹ、〜Ｙ、とすると、次の（２３）式のようになる
。 誤り位置 誤りパターン ｖ、＝ｌ Ｙｌ＝２ （すなｔ）ち”００００
００１０．”）ｖｇ＝２ Ｙ２＝３ （すな、
ｔ）ち”００００００１１”）Ｖ３＝４ Ｙ３＝
４ （すなわち０００００１００″）・・・・・・（
２３） （５）式の左辺の左側の行列にこれらの値を代入した、
前記（８）式に対応する式は次の（２４）式のようにな
る。 この式（２４）を変形する第１段階としてその第１列が
（６）式の左辺第１項の第１列の になるように変形を行うと次のく２５）式になる。 次に、第２列目か になるように変形を行うと次の（２６）式になる。 次に、第３列目か になるように変形を行うと次の（２７）式になる。 この（２７）式の第４行目はすべて０であり、σ３は存
在せず、３ワードの誤りであることが識別される。 このように３ワードの誤りである場合には、前記の（３
）式に相当する誤り位置多項式は次の（２８）式で表さ
れる。 σ（ｘ）＝ （ｘ＋Ｖ１）（ｘ＋Ｖｔ ）（ｘ＋Ｖｔ
）”！’ ＋σ２ Ｋ” 十ｄＩ Ｘ＋ｔ１６・−−−
−−−・・（２８） 先に（５）式として示した、シンドロームＳＯ＃Ｓ６と
の関係式は次の（２９）式のように変形される。 −・−・（２９） この（２９）式を左基本変形することによってσ０〜σ
２を求めることができるが、この値は既に上記（２７）
式の左上の３行４列の行列で求められており、第４列の
値に示されているように、σ・−８ σ１士１４ １．−７ ・・−−−−−−（３
０）であり、また誤り位置多項式は次の（３１）式で示
される。 ｘ” ＋７ ｘ” ＋ｌ ４ｘ＋８ ・−・−・−
・（３１）そして、誤り位置を示すこの式の根は、ｘ−
１、ｚ ｗ ２、ｘ＝４ ・−・−・−（３
２）となる。 次に誤りパターンを求めるため（１９）式にこの値を代
入すると、 ・−一一−−−−・（３３） となる。 誤りパターンを求めるには、この（３３）式を解けばよ
いが、他の方法としてこの左辺左側の行列を次の（３４
）式のように変形してから、゛上述の誤り位置を求める
際に適用したと同一の手法によって更に変形を行って（
３５）式を得、これから（３６）式に示す誤りパターン
を求めることができる。 ｖｌ −１、Ｙｌ −２ ｖ２−２、 Ｙｌ −３ Ｖ ８ ｖ−ｒ＝ ３、 Ｙｓ −４−−−−−−
−（３６）以上に説明した４ワード訂正を一般的にｔワ
ード訂正に拡張した場合の誤り位置多項式を求める演算
手順を第１図のフローチャートに示す。 このフローチャートにおいて、Ｓｏ〜Ｓｉｔ−１はシン
ドロームを、またａｌ、ｊは次の（４０）式で示す行列
の各要素を示す。 ・・・・・・（４０） 同図（ａ）は前記（５）式の左辺第１項ののシンドロー
ムＳｏ ｘｓ、の値を各要素ａｉ＋ｊに代入する処理を
示すもので、ステップ（１）でこの行列の左上の要素ａ
１９．を指定し、ステップ〔２〕でこの要素に（ｉ ＋
ｊ−２）を添字として持つシンドローム、すなわち（
ｉ＋ｊ−２）＝（１＋１−２）＝Ｏを添字とするシンド
ローム３０を代入し、ステップ〔３〕で同一行の次の列
の要素ａｌ ｅｔを指定して〔４〕のステップで行の
要素数、ここでは５、を超えないことを確認してからス
テップ〔２〕に戻ってこの要素ａｔ ｅｔにシンドロ
ームＳ１を代入し、以下〔４〕のステップでこの行の要
素への代入が終了したことを識別するまで同様にＳｘｗ
Ｓａを入力する。 この行の代入が終了したときにはステップ〔４〕での判
断の結果がｙとなるので、〔５〕のステップで行を第２
行目に移して要素ａｔ ｓｌからａ８ 。 ５まで上記と同様に代入を行い、ａ２９．の代入が済む
と第３行目の代入に移り以下同様に５行４列のすべての
要素に上記（４０）式のシンドロームの値を代入する。 この代入がすべて終了して各要素の値に（８）式の数値
が代入された■における行列は下記（４２）式に示すも
のである。 なお、ステップ〔２〕において設定されるＳの添字（ｉ
＋ｊ−２）は、（４１）式で明らかなように、斜めの線
上の要素に同一のシンドロームが代入されることに対応
するものである。 同図中）は上記（４２）式から（９）式に対応する下記
の（４３）弐への変形を行うフローチャートを示すもの
である。 この第１図（ｂ）のステップ〔７〕においては、１列目
を［１０００１にするために列番号Ｐを１にし、ステッ
プ〔８〕で行番号も列番号と等しいｌにして要素ａＩ
９．Ｉを指定し、
用い、２５５ワードなどの多数のワードをブロックとし
てこのブロックに含まれる多数ワードの誤り訂正を行う
データの符号化、復号化が光ディスクなどの記録・再生
あるいはデータ伝送などに使用されている。 本発明は、このような１つの訂正系列で多数の誤り訂正
が可能な符号（ロングディスタンスコード）を高速で復
号するとともに誤り訂正を行うための方式および誤り訂
正装置を提供するものである。 （従来技術） ＢＣＨ符号あるいはリードソロモン符号などによって多
数ワードの誤りを訂正するためには受信データからシン
ドロームを生成して誤り位置多項式の係数を求める必要
がある。 すなわち、この誤り位置多項式は、誤り位置に対応する
値を根として持つ多項式であり、誤り位置多項式の各項
の係数を求めることによって誤りの生じたデータの位置
を算出することができる。 従来このような誤り位置多項式の係数を求める方式とし
てピーターソン、バーレカンプ・マツシイ、ユークリッ
ド互除法などが知られているが、ハードウェアによって
構成しようとするとそのハードウェアの量が大きいため
に実用化に適したハードを得ることが困難であり、また
、ソフトウェアによって処理を行なうには判断が難しく
処理速度に問題が生じる。 〔目 的〕 本発明は、上記のようなロングディスタンスコードを高
速で復号するとともに、ハード化に適したロングディス
タンスコードにおける誤り訂正方式および装置を提供す
ることを目的とする。 −〔構 成〕 本発明の構成について、それぞれが８ビツトで構成され
る２５５ワードからなるブロックの、４ワード訂正可能
な、２５６元ガロア体ＧＦ （２” ）のリードソロモ
ン符号に適用した実施例に基づいて説明する。 リードソロモン符号の復号は、次の５つのステップによ
って行われる。 （１）受信データからシンドロームを求める。 （２） このシンドロームから誤り位置多項式を求め
る。 （３） この誤り位置多項式から誤り位置を求める。 （４） 誤り位置から誤りパターンを求める。 （５）誤り位置と誤りパターンとによって誤り訂正を行
う。 本発明においては、上記（２）のシンドロームからの誤
り位置多項式の算出、および（４）の誤り位置から誤り
パターンの算出の双方を同一の処理方法によって高速で
求められる復号方式を提供する。 以下の実施例における演算（＋で示す加算、×で示す乗
算および÷または／で示す除算）はいずれもモデュロ２
の演算であって、一般にテーブルを参照することによっ
て実行されものであり、そのテーブルの一例として、Ｃ
Ｆ （２’ ）上でＧ（Ｘ）＝Ｘ” ＋Ｘ’ ＋Ｘ’
＋Ｘ雪＋１を法とする上記演算のテーブルの一部を第８
図に例示する。 なお、同図（ａ）は加算テーブル、同図中）は乗算テー
ブル、同図（Ｃ）は乗算テーブルであらて、この除算テ
ーブルの最上列は被除数、最左欄は除数である。 誤りを含んだ受信データの各語の値をｒ６’ｗｒ２５４
とすると、受信データＲ（ｘ）は次の（１）式で与えら
れる。 Ｒ（ｘ）＝ ｒ（１ｘ”’ ＋ ｒ １ ｘ”３ ＋
−−−−＝−−−−−−−−−＋ｒ ａｓｓ Ｘ ’
＋ ｒ ｚｓ４−・−−−−−（１）この受信デー
タから生成されるシンドローム８１〜Ｓ７は、この（１
）式のＸにα０１αＩ 、 、−、−、、−α７をそれ
ぞれ代入した次式のものである。 Ｓ＠ ＝Ｒ（α’ ） ＝ｒ６ ＋ｒ、＋−−−−・・
＋ｒ０３ ＋ｒ １％４ ＳＩ＝Ｒ（α’ ）ｘｒｏａ”’ ＋ｒ、ｅｘ”” ＋
・−”’ ”’ ＋ ｒ ｔｓ３α’＋ｒｔｓａＳ＊
−Ｒ＜ａ” ）＝ｒｅ ｃｘ”” ＋ｒ、ｏｒ”””
”” ”” ＋ ｒ ｔｓ３α”” ＋ｒｚｓｎＳ ？
” Ｒ（ＣＸ’ ） −ｒ、 αｔ口°’ ＋ｒ、
αＨ，、。 ＋・・・”’ｒ０３α１° ”ｒｇｓ４・・・・・・（
２） 誤り位置多項式σ（ｘ）は次の（３）式のように定義さ
れる。 σ（ｘ）＝ （ｘ＋Ｖ１ ） （ｘ＋Ｖ２ ） （
ｘ＋Ｖ３ ）（ｘ＋Ｖ４） ＝ｇ’ ＋ｔＦ、ｇ’ ＋σｚ Ｘ” ＋Ｉ、Ｘ＋ｅｌ
。 ・・・・・・（３） ここでｖ１〜ｖ４は誤り位置、すなわち誤りのあるワー
ド位置を示すもので、（１）式のＸのべき乗の値に対応
しており、一般的にはテーブルを参照することにより１
０進′表現によるワード位置が求められるものであって
、このテーブルの一例として、第８図の演算テーブルと
同様に、ＣＦ （２’ ）上でＧ（，１）＝ｘ” ＋ｘ
’ ＋ｘ’ ＋ｘ” ＋ｌを法とするαのべき乗表現と
１０進表現との対応を示すテーブルの一部を第９図に示
しである。 このテーブルによって、ｖ＝ｔのときはαＯ−１で最下
位のｒ□、の項、Ｖ＝４のときはα２＝４でｒ ｔ％ｔ
の項のようになる。 なお、この実施例では、Ｓｏ〜Ｓフの８種のシンドロー
ムを用いており、４つの誤り位置と４つの誤りパターン
とを表す８つの未知数は、この８種のシンドロームを用
いて演算することによって算出できるものであるが、誤
りパターンを先に求めると同一の値、すなわち同一の誤
りパターンがあった場合に誤り位置を算出できなくなる
恐れがあるので、誤り位置を先に求めるのが一般的であ
る。 また、この誤り位置は２５５のワードの位置を示すもの
であるから０〜２５５（２進８桁）の値であり、誤りパ
ターンは１ワード８ビツト内の誤りのパターンとして“
０００００００１”から“１１１１１１１１″の２５５
通りであり、誤りの存在が検出されたワードにこのパタ
ーンを加算することによって誤りが訂正される。 誤り位置多項式である（３）式の各係数σ０〜σ３の値
とシンドロームＳｏ、〜Ｓ７との間には次の（４）式の
ような関係が成り立つ。 ・−・・−・・（４） この（４）式の右辺を左辺に移項して行列の形を変える
と次の（５）式になる。 ・・・−・・−・（５） この（５）式の両辺に、ある行列Ａを左から乗じて次の
（６）式のように変形すると、σ０〜σ３は（７）で示
すように求められる。 一一一一一・−・（６） σｏ ”ａ。 σ１−ａ １ σ２ ＝ａ３ σ３−ａ３ −・・・−・−（７）ところ
で、上記のように（５）式を（６）式に変形するために
両辺に乗じた行列Ａは右辺の値が０であるから任意のも
のでよく、結局、（５）式のｓｏ ％Ｓ？で表される行
列を（６）式の形になるように左基本変形すればよいこ
とになる。 この左基本変形をＳｏ−ｗ５７の値がそれぞれ０゜１５
．８５，１１５，１９３，１１５，１６１および２３１
の場合を例に採って具体的に説明する。 （５）式の左辺第１項は次の（８）式で表される。 この式（８）を（６）式の形に変形する第１段階として
その第１列が（６）式の左辺第１項の第１列のになるよ
うに変形を行う。 （８）式の第１列第１行の値が０であるから、第１列が
０でない行と置き換えるために、第２行と第１行とを入
れ換えると次の（９）式になる。 次に第１列第１行の値１５を１にするために、第１行の
各列の値をこの１５で割るモデエロ２の演算を行うと次
の（１０）式になる。 次に、第３および第４行目の第１列の値を０にするため
に、第３行目については第１行の値を８５倍してからこ
の第３行目の各値にモデュロ２の加算を、また第４行目
については第１行の値を１１５倍してからこの第３行目
の各値にモデエロ２の加算を行うことによって次の（１
１）式を得る。 次に、上記式（８）を（６）式の形に変形する第２段階
としてその第２列が（６）式の左辺第１項の第２列と同
じ にするために、上記同様の手法として、第２列目をその
第２行の１５でモデエロ２の除算を行い、次いでこの第
２行目の値を８７倍して第３行目とモデュロ２の加算を
、またこの第２行目の値を５８倍して第４行目とモデュ
ロ２の加算を行うことによって下記の（１２）式を得る
。。 次に、上記式（８）を（６）式の形に変形する第３段階
としてその第３列が（６）式の左辺第１項の第３列と同
じ にするために、上記第１段階と同様に第３列目が０の第
３行と第４行とを入れ換えて、 とし、第３列目をその第３行の１０１でモデュロ２の除
算を行うとともに、この得られた第３行目の値を６２倍
して第１行目とモデエロ２の加算を行い、またこの第３
行目の値を１５倍して第２行目とモデュロ２の加算を行
うことによって下記の（１４）式を得る。 次に、上記式（８）を（６）式の形に変形する最後の段
階としてその第４列が（６）式の左辺第１項の第４列と
同じ にするために、第４行をその第４列の１０１でモデュロ
２の除算を行い、得られた第４行目の値を８７倍して第
１行目にモデエロ２の加算を、また１０７倍して第２行
目にモデュロ２の加算を行うことによって前記の（６）
式と同一の形の下記（１５）式が得られる。 これによって、（６）式について説明したように、σｏ
＝６４ σ５＝１２０ σ２−５４ σｓ ＝ １５ −−−−−−・（１６
）が得られ、これらσの値を（３）式に示した誤り位置
多項式に代入することによって ｘ’ ＋１５ｘ’＋５４ｘ”＋１２０ｘ＋６４ −−−
−−−−（１７）が得られる。 この（１７）式をチェノのアルゴリズムなどによって解
いてその根を求めると誤り位置を検出することができ、
この（１７）式の場合には、ｘ−１，２，４，８・・・
・−・−・（１８）・であるから、前述のように（１）
式のｒ！Ｓ４＊’□３ 。 ｒ ｚｓｚの項およびｒ ｆｆｉ！ＩＩの項に誤りがあ
ることになる。 以上のようにして誤り位置が検出されたので、次に誤り
パターン、すなわち正しいデータのパターンを検出する
手法について説明する。 誤り位置ｖ１の誤りパターンがＹｔ、誤り位置ｖ２の誤
りパターンがＹ２のように、誤り位置■１ 、Ｖ２ 、
ｖｓ 、Ｖ４がそれぞれ誤りパターンＹ１、Ｙ２、Ｙ３
、Ｙ４に対応するものとする。 このとき、誤りパターンＹ１〜Ｙ４、誤り位置ｖ１〜ｖ
４およびシンドロームＳｏ−ｗｓｓとの間には次の関係
が成り立つ。 ・・−・−（１９） この（１９）式の右辺を、先に（４）式から（５）式に
変換したと同様に左辺に移項して行列の形を変えると次
の（２０）式になる。 ・・・・・・ （２０） この（２０）式の左辺の左側の行列に上記誤り位置とし
てｖｌ−１、ｖ２＝２、ｖ３＝４、ｖ４＝８．５ｏ＝０
．５ｔ＝１５．５２＝８５．５ｓ＝１１５をそれぞれ代
入し、（８）式ないしく１５）式で説明したと同様の左
基本変形を行うと次の（２１）式に示すように変形され
る。 この行列の第４列の値によって誤りパターンＹ１〜Ｙ４
は次の（２２）式のようになる。 Ｙ、＝１ Ｙ２＝１ Ｙｓ＝１ Ｙ４＝１ ・・・・・・（２２）
これによって、誤りパターンはいずれもｌであることが
検出されるので、誤りがある１、２．４．８番目のワー
ドについてパターン１の訂正を行えばよい。 なお、この誤りパターンＹの値は、その誤りパターンを
１０進数で表しており、上記パターン１は、“００００
０００１″を誤り位置のワードにモデュロ２で加算すれ
ばよい。 次に、上記の４ワード訂正が可能な符号によって３ワー
ドの誤りを訂正する過程について例を挙げて説明する。 誤りの例として、誤り位置を最後の３項とし、誤りパタ
ーンＹ、〜Ｙ、とすると、次の（２３）式のようになる
。 誤り位置 誤りパターン ｖ、＝ｌ Ｙｌ＝２ （すなｔ）ち”００００
００１０．”）ｖｇ＝２ Ｙ２＝３ （すな、
ｔ）ち”００００００１１”）Ｖ３＝４ Ｙ３＝
４ （すなわち０００００１００″）・・・・・・（
２３） （５）式の左辺の左側の行列にこれらの値を代入した、
前記（８）式に対応する式は次の（２４）式のようにな
る。 この式（２４）を変形する第１段階としてその第１列が
（６）式の左辺第１項の第１列の になるように変形を行うと次のく２５）式になる。 次に、第２列目か になるように変形を行うと次の（２６）式になる。 次に、第３列目か になるように変形を行うと次の（２７）式になる。 この（２７）式の第４行目はすべて０であり、σ３は存
在せず、３ワードの誤りであることが識別される。 このように３ワードの誤りである場合には、前記の（３
）式に相当する誤り位置多項式は次の（２８）式で表さ
れる。 σ（ｘ）＝ （ｘ＋Ｖ１）（ｘ＋Ｖｔ ）（ｘ＋Ｖｔ
）”！’ ＋σ２ Ｋ” 十ｄＩ Ｘ＋ｔ１６・−−−
−−−・・（２８） 先に（５）式として示した、シンドロームＳＯ＃Ｓ６と
の関係式は次の（２９）式のように変形される。 −・−・（２９） この（２９）式を左基本変形することによってσ０〜σ
２を求めることができるが、この値は既に上記（２７）
式の左上の３行４列の行列で求められており、第４列の
値に示されているように、σ・−８ σ１士１４ １．−７ ・・−−−−−−（３
０）であり、また誤り位置多項式は次の（３１）式で示
される。 ｘ” ＋７ ｘ” ＋ｌ ４ｘ＋８ ・−・−・−
・（３１）そして、誤り位置を示すこの式の根は、ｘ−
１、ｚ ｗ ２、ｘ＝４ ・−・−・−（３
２）となる。 次に誤りパターンを求めるため（１９）式にこの値を代
入すると、 ・−一一−−−−・（３３） となる。 誤りパターンを求めるには、この（３３）式を解けばよ
いが、他の方法としてこの左辺左側の行列を次の（３４
）式のように変形してから、゛上述の誤り位置を求める
際に適用したと同一の手法によって更に変形を行って（
３５）式を得、これから（３６）式に示す誤りパターン
を求めることができる。 ｖｌ −１、Ｙｌ −２ ｖ２−２、 Ｙｌ −３ Ｖ ８ ｖ−ｒ＝ ３、 Ｙｓ −４−−−−−−
−（３６）以上に説明した４ワード訂正を一般的にｔワ
ード訂正に拡張した場合の誤り位置多項式を求める演算
手順を第１図のフローチャートに示す。 このフローチャートにおいて、Ｓｏ〜Ｓｉｔ−１はシン
ドロームを、またａｌ、ｊは次の（４０）式で示す行列
の各要素を示す。 ・・・・・・（４０） 同図（ａ）は前記（５）式の左辺第１項ののシンドロー
ムＳｏ ｘｓ、の値を各要素ａｉ＋ｊに代入する処理を
示すもので、ステップ（１）でこの行列の左上の要素ａ
１９．を指定し、ステップ〔２〕でこの要素に（ｉ ＋
ｊ−２）を添字として持つシンドローム、すなわち（
ｉ＋ｊ−２）＝（１＋１−２）＝Ｏを添字とするシンド
ローム３０を代入し、ステップ〔３〕で同一行の次の列
の要素ａｌ ｅｔを指定して〔４〕のステップで行の
要素数、ここでは５、を超えないことを確認してからス
テップ〔２〕に戻ってこの要素ａｔ ｅｔにシンドロ
ームＳ１を代入し、以下〔４〕のステップでこの行の要
素への代入が終了したことを識別するまで同様にＳｘｗ
Ｓａを入力する。 この行の代入が終了したときにはステップ〔４〕での判
断の結果がｙとなるので、〔５〕のステップで行を第２
行目に移して要素ａｔ ｓｌからａ８ 。 ５まで上記と同様に代入を行い、ａ２９．の代入が済む
と第３行目の代入に移り以下同様に５行４列のすべての
要素に上記（４０）式のシンドロームの値を代入する。 この代入がすべて終了して各要素の値に（８）式の数値
が代入された■における行列は下記（４２）式に示すも
のである。 なお、ステップ〔２〕において設定されるＳの添字（ｉ
＋ｊ−２）は、（４１）式で明らかなように、斜めの線
上の要素に同一のシンドロームが代入されることに対応
するものである。 同図中）は上記（４２）式から（９）式に対応する下記
の（４３）弐への変形を行うフローチャートを示すもの
である。 この第１図（ｂ）のステップ〔７〕においては、１列目
を［１０００１にするために列番号Ｐを１にし、ステッ
プ〔８〕で行番号も列番号と等しいｌにして要素ａＩ
９．Ｉを指定し、
〔９〕のステップでこの要素の値を見
てその値が０であればステップ〔１０〕において行番号
に１を加え、ステップ〔１１〕における行番号の識別に
よって行列の最下行に至るまでの範囲内で第１列目の要
素の値が０でない行を捜す。 第１列目の要素の値が０でない行が見つかればステップ
〔１２〕に移り１行番号が初期値Ｐ−１以外であれば、
すなわち第１行第１列の値が０であれば、ステップ〔１
３〕において要素の列番号を示す添字を１にして第１行
に移す行の第１列の要素を指定してから、行の入れ換え
を行うために〔１４〕のステップにおいて一時的に１ワ
一ド分の記憶容量を有する退避用のレジスタｄにａ１９
．の要素の値を移してその後に上記ステップ
てその値が０であればステップ〔１０〕において行番号
に１を加え、ステップ〔１１〕における行番号の識別に
よって行列の最下行に至るまでの範囲内で第１列目の要
素の値が０でない行を捜す。 第１列目の要素の値が０でない行が見つかればステップ
〔１２〕に移り１行番号が初期値Ｐ−１以外であれば、
すなわち第１行第１列の値が０であれば、ステップ〔１
３〕において要素の列番号を示す添字を１にして第１行
に移す行の第１列の要素を指定してから、行の入れ換え
を行うために〔１４〕のステップにおいて一時的に１ワ
一ド分の記憶容量を有する退避用のレジスタｄにａ１９
．の要素の値を移してその後に上記ステップ
〔９〕〜〔
１１〕で検出された行番号ＬＰを有する入れ換えるべき
行の第１列の要素ａＬＦｔＪを代入し、その後退避用レ
ジスタｄに退避しておいた要素ａ３９．の値をａＬＰｓ
ｊに移す。 この処理をステップ〔１５〕において処理する列番号を
増やしながら最後の列まで行うことによって上記（４３
）式の配列を有する■の状態に至るが、第１行の第１列
の要素ａｌ ｓｌＯ値がもともと（４３）式のように
０でなければ入れ換えを行う必要がないのでステップ〔
１２〕から直接■の状態に移ることができる。 第１図（Ｃ１のステップ〔１７〕〜〔２０〕は、上記（
４３）式の第１行第１列の要素の値を１とするためにこ
の行の第２列目以降の各要素をこの第１行第１列の要素
の値で割る処理を行うもので、（４４）式としてここに
再掲する前記の（１０）式に示すようにに変形するフロ
ーである。 ステップ〔１７〕は第２列目の要素を指定するために、
列を示す添字を行番号Ｐに１を加え、ステップ〔１８〕
ではこれら要素第１行第１列の要素の値で除算を行い、
〔１９〕〜〔２０〕のステップによってこの行の各要素
についての処理が終了するまで繰り返すことによって、
上記（４４）式の状態が得られる。 次のステップ〔２１〕〜〔２７〕は第３および第４行の
第１列の値をそれぞれ０にするための処理であって、第
３行の各要素には第１行の対応する要素の値を８５倍し
て加えることによってその第１列の値を０にし、また第
４行の各要素には第１行の対応する要素の値を１１５倍
して加えることによってその第１列の値を０にするもの
である。 ステップ〔２１〕では第１行の第２列目の要素を指定し
ており、ｉ＝ＰであればこのＰの列はこの列の値を［１
０００１などの所要の値にすることを目的とするもので
あるからあえて演算を行う必要がないのでステップ〔２
２〕によって排除して、それ以外の行についてステップ
〔２３〕の処理を行う。 このステップ〔２３〕の処理は、所要の値にすべき行Ｐ
の同一列の要素の値に自己の属する行のＰ列目の値を乗
算して当該要素自身の値を加算するものであり、これを
〔２４〕、〔２５〕のステップによって行の終わりまで
処理し、これが終了するとステップ〔２６〕、〔２７〕
によって次の行の処理を行う。 その結果、■においては、先に（１１）式として示した
次の（４５）式の行列 が得られる。 次のステップ〔２８〕においては、次の列を所定の値、
例えば第２列目を［０１００］とする処理を行うために
列の番号に１を加えて未処理の行が残っている期間中前
記ステップ〔８〕に戻す。 また、■は誤りが少ない場合などで、前記ステップ〔１
１〕において既に処理が不必要になった場合のルートを
示している。 このようにしてすべての処理が終了したステップ〔３０
〕の前段において得られた行列は（１５）式として示し
た である。 この行列から誤り位置多項式の係数を求めるために、こ
の係数σの添字の初期値としてステップ〔３０〕で０を
セットする。 この添字に＋１すれば、この係数を保持している列番号
になるので、ステップ〔３１〕においては最後の列ｐ＝
ｔの当該列番号の値をステップ〔３１〕〜〔３３〕、の
処理によって順次読出すことができる。 なお、ステップ〔３４〕は誤り位置多項式の最高次の項
の係数を供給するもので、この係数は必ず１であるので
演算は必要としない。 第２図は誤りパターンを求めるための処理を示すフロー
チャートであって、第１図に示した誤り位置を求める処
理と相違する処理のみを示してあり、第１図と同一のス
テップ番号を付したステップは同一の処理を行うもので
あり、また対応する処理に、ついては１００を加えたス
テップ番号を付しである。 第２図（ａ）は第１図（ａ）に相当する処理を示してあ
り、 −−−−−・・（５０） を展開する処理を行うもので、第１図に示したステップ
〔２〕における行列の第１列ないし第４列のシンドロー
ムに代えて誤り位置■４．ム−１を、また第５列にシン
ドロームＳ（１”Ｓｉを代入する点で第１図の場合と相
違している。 ステップ（１００）は上記誤り位置を各要素に代入する
ステップであり、ステップ（１０３）は第５列目のシン
ドロームＳｏ〜Ｓ３を代入するものであり、この第２図
（ａ）の処理が終了した■′における行列は下記（５１
）式に示したとおりになる。 第２図（ｂ）は第１図（ｄ）に対応するもので、上記（
５１）式に示した行列について第１図のステップ〔７〕
ないし〔２７〕と同様な処理を行った、ステップ〔１２
８〕の前段■′における行列は次の（５２）式に示すと
おりである。 先に〔２１〕式について説明したように、この〔５２〕
式の第５列の第１行から第４行は、誤り位置Ｙｓ 、Ｙ
２ 、Ｙｓ 、Ｙａに順次対応する誤りパターンを示し
ており、この例では誤りパターンがすべて１、すなわち
“０００００００１”であるから、上記の誤り位置にあ
る復号すべきデータワードにこの’０００００００１”
を加算することによって誤り訂正を行うことができる。 第３図ないし第６図はそれぞれ本発明による誤り訂正方
式を実行するための装置の構成を示すものである。 第３図は従来の誤り訂正装置におけると同様な構成を用
いたもので、バス３０にＣＰＵ３ Ｌ ＲＡＭ３２、Ｒ
ＯＭ３３およびＩ１０ボート３４がそれぞれ接続されて
おり、ＣＰＵ３１はＲＯＭ３３が格納しているプログラ
ムおよびテーブルなどを読出してＲＡＭ３２にストアし
、このプログラムおよびテーブルに基づいてモデエロ２
の演算を含む処理を行うものであり、受信したデータワ
ードから得られたシンドロームは第１のＩ１０ボート３
４から入力され、上記ＣＰＵ３１によって処理されて誤
り位置および誤りパターンがこのＩ１０ポート３４から
それぞれ出力されて、復号したデータワードの訂正に用
いられる。 この第３図の構成においては、モデュロ２の演算をＣＰ
Ｕにおいて処理するものであるため、その演算時間が長
くなって処理速度が低いという欠点がある。 第４図は上記欠点を解決した本発明の実施例を示すもの
で、バス４０にＣＰＵ４１、ＲＡＭ４２、ＲＯＭ４３お
よびＩ１０ポート４４がそれぞれ接続され、さらに本発
明によってモデュロ２の乗算器４５１、モデュロ２の除
算器４５２を含むものとして示したモデュロ２の演算処
理部４５が設けられており、第１図のフローチャートに
おけるステップ〔１４〕、〔１８〕および〔２３〕など
のｃｐυでは処理困難なモデュロ２の演算をこの演算処
理部４５で行わせることによって処理速度を向上させる
ことができる。 第５図は第１図に示したフローチャートの演算処理を主
として転送によって行うようにした装置を示すもので、
ステップ〔１８〕の除算を行うための除算部５４、ステ
ップ〔２３〕の処理を行うための乗算および加算を行う
演算部５５およびステップ〔１４〕でのデータワードの
入れ換えを行うために必要な退避用レジスタ５６がバス
５０に接続されており、このバスにはＲＡＭ５２、Ｉ１
０ボート５３とともに、ＣＰＵを含み主としてデータの
転送制御を行うための転送制御部５１が接続されている
。 この実施例の除算部５４および演算部５５は第４図の演
算処理部４５に相□当するものであり、退避用レジスタ
５６はラッチ５６１１，５６１２および３状態バツフア
５６２１．５６２２からなる２組の記憶手段を備えてお
り、入れ換えるべき２つのデータワードをそれぞれのラ
ッチ５６１１．５６１２にストアしてから順次読出すこ
とによってデータワードの入れ換えを行うものである。 第６図は先に説明した本発明の誤り訂正方式が行列の行
を基本とする処理を行うものである点に着目して発明し
た４行５列、すなわちｔ＝４、の行列を処理する誤り訂
正装置の実施例であって、行列記憶部６０、データワー
ド入換部７０、演算処理部８０および０検出部９０から
なり、図中口内にＡ−ＨおよびＫを記入したのはそれぞ
れゲートである。 その動作を前記〔５〕式の左辺第１項の下記の行列（６
０）を処理する場合を例にとって第７図のフローチャー
トに基づいて説明する。 ４行５列に図示されたレジスタはそれぞれ上記行列の対
応する要素のデータワードを格納するためのもので、こ
れらレジスタは格納するデータワードの行列中の要素の
位置に合わせてａｔ ｅｌ レジスタ〜ａ４ ｐ％
レジスタとする。 第７図（ａ）のステップ（２０１）〜（２１３）はこれ
らレジスタに上記行列の値を代入する処理であって、ス
テップ（２０１）で入力ゲートＫを導通状態として、ス
テップ（２０２）で初期値を１にセットするとともにス
テップ（２０３）として入力線６１上にシンドロームＳ
（五−１，すなわちＳｏを出力する。 次にステップ（２０４）としてｊをｉに等しい値、ここ
では１、としてステップ（２０５）で行の範囲内にある
ことを確認してからステップ（２０？）で添字ｋを求め
てａＪ ｔｋのレジスタに上記シンドロームＳｏをス
テップ（２０Ｂ）で格納する。 このステップ（２０１）から（２０８）の処理は、上記
（６０）式の要素ａｌ ａＮおよびａＲ９１の値がと
もに同一のシンドロームＳ１であり、また要素ａＩ
＄３ 、ａｍ ＃＊および１９．の値がともに同一のシ
ンドロームＳ２であり、以下シンドロームＳｓ ｘｓ、
まで斜め、の線上の要素に同一のデータワードが代入さ
れることから、レジスタの添字ｊとｋをステップ（２０
４）〜（２０Ｂ）に示す処理によって選択して格納を行
うようにしたものであり、ステップ（２０６）の処理は
行列の最下行以下の行に属する要素を指定する添字が生
成されたときに排除するためのものである。 ステップ（２０９）においては、行数を１だけ減少させ
るとともに列数を１だけ増加させることによって次の斜
め線上の要素にステップ（２１２）で＋１された添字を
有するシンドロームＳを格納するものであり、ステップ
（２１０１、（２１１）および（２１３）は選択された
添字によって指定される要素が存在しないときにこの添
字を排除するためのものである。 第７図（ｂ）に示すズテップ（２１４）ないしく２２６
は第１図山）の処理に相当するもので、ステップ〔２１
４〕ないしく、２１９）は指定された列のデータワード
の値が０であるか否かを識別する処理であり、ステップ
（２２０）ないしく ２２６）は行の入れ換えを行う処
理である。 初期値としてはステップ（２１４）で列番号としてｌを
セットし、ステップ（２１５）で行番号もｌとしてａｌ
＄１のレジスタを指定してステップ〔２１６〕でゲ
ートＣをアクティブとし、ステップ〔２１７〕でこのレ
ジスタが格納しているデータワードを０検出器９０に送
ってその値が０であるか否かを識別する。 ・ もし、その値が０であればステップ（２１８）で行
番号を＋１してステップ（２１９）でこの行番号が行列
内に存在することを確認してステップ〔２１６〕に戻り
、（８１式から（９）式への変換について先に説明した
ように、ステップ（２１５）で指定された要素の値が０
でない行を見つける。 ステップ（２２０）は行の入れ換えが必要か否かを判断
し、入れ換えが必要でなければ直接、入れ換えが必要で
あればステップ（２２１）ないし〔２２６〕の処理を行
って（９）式に示す行列を■において生成する。 このステップ（２２１）および（２２２）においては、
Ｐ行に属するゲートＦをアクティブにして入換用レジス
タＲ１にランチパルスを出力するとともにＬＰ行目のレ
ジスタのゲートＦをアクティフ゛にして入れ換えられる
べきデータワードを格納していたレジスタの値をこの入
換用レジスタＲ１にストアさせ、続くステップ（２２３
）および〔２２４〕においては同様に入れ換えるべき要
素の値を入換用レジスタＲ２にストアさせ、次いでステ
ップ（２２５）および（２２６）においてはこれら入換
用レジスタＲ１、Ｒ２にストアされていたデータワード
を要素を格納するレジスタ入れ換えて戻し、これによっ
て行の入れ換えを行い、（９）式に示す行列が得られる
。 この処理は行を単位として同一の行に属するすべてのレ
ジスタについて同時に行われるので、１回の処理時間で
行の入れ換えが完了する。 第７図（ｅ）は第１図（Ｃ）の処理に相当する処理を行
うフローであって、ステップ（２２７１においては除算
を行うために逆数テーブル１ ／ ｘの出力が各列ごと
に設けられている乗算器Ｘ社供給されるようにセレクタ
を切換え、先に第１図（Ｃ）のステップ〔１９〕で説明
した除算を同一の行に属するすべての要素について同時
並列に実行し、ステップ〔２２８〕においてもとのレジ
スタに除算を行った結果を書込む。 ステップ（２２９）によって第１図（Ｃ）のステップ〔
２２〕の処理、すなわち既に演算が終了している行を除
き、ステップ（２３０）ないしく ２３３）において〔
２３〕ステツプに対応する処理、すなわち前記（１０）
式から（１１）式への変形を行い、ステップ〔２３４〕
において次の行を指定するとともに（２３５）のステッ
プにおいてこの行列内にあることを確認しながら上記の
処理を各行について繰り返すものである。 レジスタａム 、デのゲートＢをアクティブにしてこの
レジスタの値を演算処理部８０に送り、セレクタ８２は
この値を直接乗算器８３１〜８３５の一方の入力端子に
供給するように切換えるとともに、これら乗算器の他方
の入力端子にはｉ行に属する各レジスタからゲートＥを
経てこれらレジスタが格納している値を印加することに
よって同一行について同時に乗算を行い、さらにこれに
よって得られた結果をゲー）Ｄを介して送られてきた上
記各レジスタが格納している値と加算器８４によってそ
れぞれ加算してからもとの１行のレジスタにそれぞれ格
納し、これら処理の最終段階である■においては、最初
の処理の場合には前記の（１１）式に示した行列を行列
記憶部６０の各レジスタに生成する。 第７図（ｄ）は第１図（ｄ）に対応するもので、ステッ
プ（２２６）においては列番号に＋１して上記の〔２１
５〕のステップ以降の処理を繰返し、ステップ（２３７
）において最後の列までの処理の終了が検知されたとき
には前記の行列式（１５）が行列記憶部６０の各レジス
タに生成される。 この第７図（ｄ）のステップ（２３８）ないしく ２４
２）の処理は先に第１図（ｄ）のステップ〔３０〕ない
し〔３４〕について説明した処理と同様であって、誤り
位置多項式の係数が順次水められる。なお、この誤り位
置多項式の最高次の項の係数は常に１であるから必ずし
も算出する必要がないことは前述のとおりである。 また、この第６図および第７図についての説明は、誤り
位置多項式の係数を算出する場合についてのものである
が、第６図（ａ）に示したフローで行列記憶部６０の各
レジスタに記憶させるデータワードを（２０）式の左辺
第１項の行列のデータワードとすれば、上記誤り位置多
項式の係数を求める処理とい同一の処理を行うことによ
って誤りパターンを求めることができることは先に述べ
たとおりである。 以上の説明はＧＦ （２” ）上のリードソロモン符号
についてのものであるが、本発明はガロア体によって制
限を受けるものではなく、また、訂正符号としてｂ−隣
接符号などの他のロングディスタンスコードを用いた場
合にも適用できることは明らかであろう。 また、行列を転置した場合にも本発明による誤り訂正装
置を適用し得ることもまた明らかであろう。 〔効 果〕 本発明によれば、行列式の解を直接的な演算によって求
めるものではなく、行列式の変形とこの行列を構成する
データワードについての演算とによって解を得ることが
できるのでその処理が極めて簡単になり、演算装置に過
大な負担をかけることもなく、処理を迅速化することが
できるという格別の効果を達成できる。 特に、第６図に示した誤り訂正装置のように、各列に演
算手段を配置することによって１つの行を単位として各
列の要素を並列的に処理を行うように構成すればさらに
その処理時間を短縮することができる。
１１〕で検出された行番号ＬＰを有する入れ換えるべき
行の第１列の要素ａＬＦｔＪを代入し、その後退避用レ
ジスタｄに退避しておいた要素ａ３９．の値をａＬＰｓ
ｊに移す。 この処理をステップ〔１５〕において処理する列番号を
増やしながら最後の列まで行うことによって上記（４３
）式の配列を有する■の状態に至るが、第１行の第１列
の要素ａｌ ｓｌＯ値がもともと（４３）式のように
０でなければ入れ換えを行う必要がないのでステップ〔
１２〕から直接■の状態に移ることができる。 第１図（Ｃ１のステップ〔１７〕〜〔２０〕は、上記（
４３）式の第１行第１列の要素の値を１とするためにこ
の行の第２列目以降の各要素をこの第１行第１列の要素
の値で割る処理を行うもので、（４４）式としてここに
再掲する前記の（１０）式に示すようにに変形するフロ
ーである。 ステップ〔１７〕は第２列目の要素を指定するために、
列を示す添字を行番号Ｐに１を加え、ステップ〔１８〕
ではこれら要素第１行第１列の要素の値で除算を行い、
〔１９〕〜〔２０〕のステップによってこの行の各要素
についての処理が終了するまで繰り返すことによって、
上記（４４）式の状態が得られる。 次のステップ〔２１〕〜〔２７〕は第３および第４行の
第１列の値をそれぞれ０にするための処理であって、第
３行の各要素には第１行の対応する要素の値を８５倍し
て加えることによってその第１列の値を０にし、また第
４行の各要素には第１行の対応する要素の値を１１５倍
して加えることによってその第１列の値を０にするもの
である。 ステップ〔２１〕では第１行の第２列目の要素を指定し
ており、ｉ＝ＰであればこのＰの列はこの列の値を［１
０００１などの所要の値にすることを目的とするもので
あるからあえて演算を行う必要がないのでステップ〔２
２〕によって排除して、それ以外の行についてステップ
〔２３〕の処理を行う。 このステップ〔２３〕の処理は、所要の値にすべき行Ｐ
の同一列の要素の値に自己の属する行のＰ列目の値を乗
算して当該要素自身の値を加算するものであり、これを
〔２４〕、〔２５〕のステップによって行の終わりまで
処理し、これが終了するとステップ〔２６〕、〔２７〕
によって次の行の処理を行う。 その結果、■においては、先に（１１）式として示した
次の（４５）式の行列 が得られる。 次のステップ〔２８〕においては、次の列を所定の値、
例えば第２列目を［０１００］とする処理を行うために
列の番号に１を加えて未処理の行が残っている期間中前
記ステップ〔８〕に戻す。 また、■は誤りが少ない場合などで、前記ステップ〔１
１〕において既に処理が不必要になった場合のルートを
示している。 このようにしてすべての処理が終了したステップ〔３０
〕の前段において得られた行列は（１５）式として示し
た である。 この行列から誤り位置多項式の係数を求めるために、こ
の係数σの添字の初期値としてステップ〔３０〕で０を
セットする。 この添字に＋１すれば、この係数を保持している列番号
になるので、ステップ〔３１〕においては最後の列ｐ＝
ｔの当該列番号の値をステップ〔３１〕〜〔３３〕、の
処理によって順次読出すことができる。 なお、ステップ〔３４〕は誤り位置多項式の最高次の項
の係数を供給するもので、この係数は必ず１であるので
演算は必要としない。 第２図は誤りパターンを求めるための処理を示すフロー
チャートであって、第１図に示した誤り位置を求める処
理と相違する処理のみを示してあり、第１図と同一のス
テップ番号を付したステップは同一の処理を行うもので
あり、また対応する処理に、ついては１００を加えたス
テップ番号を付しである。 第２図（ａ）は第１図（ａ）に相当する処理を示してあ
り、 −−−−−・・（５０） を展開する処理を行うもので、第１図に示したステップ
〔２〕における行列の第１列ないし第４列のシンドロー
ムに代えて誤り位置■４．ム−１を、また第５列にシン
ドロームＳ（１”Ｓｉを代入する点で第１図の場合と相
違している。 ステップ（１００）は上記誤り位置を各要素に代入する
ステップであり、ステップ（１０３）は第５列目のシン
ドロームＳｏ〜Ｓ３を代入するものであり、この第２図
（ａ）の処理が終了した■′における行列は下記（５１
）式に示したとおりになる。 第２図（ｂ）は第１図（ｄ）に対応するもので、上記（
５１）式に示した行列について第１図のステップ〔７〕
ないし〔２７〕と同様な処理を行った、ステップ〔１２
８〕の前段■′における行列は次の（５２）式に示すと
おりである。 先に〔２１〕式について説明したように、この〔５２〕
式の第５列の第１行から第４行は、誤り位置Ｙｓ 、Ｙ
２ 、Ｙｓ 、Ｙａに順次対応する誤りパターンを示し
ており、この例では誤りパターンがすべて１、すなわち
“０００００００１”であるから、上記の誤り位置にあ
る復号すべきデータワードにこの’０００００００１”
を加算することによって誤り訂正を行うことができる。 第３図ないし第６図はそれぞれ本発明による誤り訂正方
式を実行するための装置の構成を示すものである。 第３図は従来の誤り訂正装置におけると同様な構成を用
いたもので、バス３０にＣＰＵ３ Ｌ ＲＡＭ３２、Ｒ
ＯＭ３３およびＩ１０ボート３４がそれぞれ接続されて
おり、ＣＰＵ３１はＲＯＭ３３が格納しているプログラ
ムおよびテーブルなどを読出してＲＡＭ３２にストアし
、このプログラムおよびテーブルに基づいてモデエロ２
の演算を含む処理を行うものであり、受信したデータワ
ードから得られたシンドロームは第１のＩ１０ボート３
４から入力され、上記ＣＰＵ３１によって処理されて誤
り位置および誤りパターンがこのＩ１０ポート３４から
それぞれ出力されて、復号したデータワードの訂正に用
いられる。 この第３図の構成においては、モデュロ２の演算をＣＰ
Ｕにおいて処理するものであるため、その演算時間が長
くなって処理速度が低いという欠点がある。 第４図は上記欠点を解決した本発明の実施例を示すもの
で、バス４０にＣＰＵ４１、ＲＡＭ４２、ＲＯＭ４３お
よびＩ１０ポート４４がそれぞれ接続され、さらに本発
明によってモデュロ２の乗算器４５１、モデュロ２の除
算器４５２を含むものとして示したモデュロ２の演算処
理部４５が設けられており、第１図のフローチャートに
おけるステップ〔１４〕、〔１８〕および〔２３〕など
のｃｐυでは処理困難なモデュロ２の演算をこの演算処
理部４５で行わせることによって処理速度を向上させる
ことができる。 第５図は第１図に示したフローチャートの演算処理を主
として転送によって行うようにした装置を示すもので、
ステップ〔１８〕の除算を行うための除算部５４、ステ
ップ〔２３〕の処理を行うための乗算および加算を行う
演算部５５およびステップ〔１４〕でのデータワードの
入れ換えを行うために必要な退避用レジスタ５６がバス
５０に接続されており、このバスにはＲＡＭ５２、Ｉ１
０ボート５３とともに、ＣＰＵを含み主としてデータの
転送制御を行うための転送制御部５１が接続されている
。 この実施例の除算部５４および演算部５５は第４図の演
算処理部４５に相□当するものであり、退避用レジスタ
５６はラッチ５６１１，５６１２および３状態バツフア
５６２１．５６２２からなる２組の記憶手段を備えてお
り、入れ換えるべき２つのデータワードをそれぞれのラ
ッチ５６１１．５６１２にストアしてから順次読出すこ
とによってデータワードの入れ換えを行うものである。 第６図は先に説明した本発明の誤り訂正方式が行列の行
を基本とする処理を行うものである点に着目して発明し
た４行５列、すなわちｔ＝４、の行列を処理する誤り訂
正装置の実施例であって、行列記憶部６０、データワー
ド入換部７０、演算処理部８０および０検出部９０から
なり、図中口内にＡ−ＨおよびＫを記入したのはそれぞ
れゲートである。 その動作を前記〔５〕式の左辺第１項の下記の行列（６
０）を処理する場合を例にとって第７図のフローチャー
トに基づいて説明する。 ４行５列に図示されたレジスタはそれぞれ上記行列の対
応する要素のデータワードを格納するためのもので、こ
れらレジスタは格納するデータワードの行列中の要素の
位置に合わせてａｔ ｅｌ レジスタ〜ａ４ ｐ％
レジスタとする。 第７図（ａ）のステップ（２０１）〜（２１３）はこれ
らレジスタに上記行列の値を代入する処理であって、ス
テップ（２０１）で入力ゲートＫを導通状態として、ス
テップ（２０２）で初期値を１にセットするとともにス
テップ（２０３）として入力線６１上にシンドロームＳ
（五−１，すなわちＳｏを出力する。 次にステップ（２０４）としてｊをｉに等しい値、ここ
では１、としてステップ（２０５）で行の範囲内にある
ことを確認してからステップ（２０？）で添字ｋを求め
てａＪ ｔｋのレジスタに上記シンドロームＳｏをス
テップ（２０Ｂ）で格納する。 このステップ（２０１）から（２０８）の処理は、上記
（６０）式の要素ａｌ ａＮおよびａＲ９１の値がと
もに同一のシンドロームＳ１であり、また要素ａＩ
＄３ 、ａｍ ＃＊および１９．の値がともに同一のシ
ンドロームＳ２であり、以下シンドロームＳｓ ｘｓ、
まで斜め、の線上の要素に同一のデータワードが代入さ
れることから、レジスタの添字ｊとｋをステップ（２０
４）〜（２０Ｂ）に示す処理によって選択して格納を行
うようにしたものであり、ステップ（２０６）の処理は
行列の最下行以下の行に属する要素を指定する添字が生
成されたときに排除するためのものである。 ステップ（２０９）においては、行数を１だけ減少させ
るとともに列数を１だけ増加させることによって次の斜
め線上の要素にステップ（２１２）で＋１された添字を
有するシンドロームＳを格納するものであり、ステップ
（２１０１、（２１１）および（２１３）は選択された
添字によって指定される要素が存在しないときにこの添
字を排除するためのものである。 第７図（ｂ）に示すズテップ（２１４）ないしく２２６
は第１図山）の処理に相当するもので、ステップ〔２１
４〕ないしく、２１９）は指定された列のデータワード
の値が０であるか否かを識別する処理であり、ステップ
（２２０）ないしく ２２６）は行の入れ換えを行う処
理である。 初期値としてはステップ（２１４）で列番号としてｌを
セットし、ステップ（２１５）で行番号もｌとしてａｌ
＄１のレジスタを指定してステップ〔２１６〕でゲ
ートＣをアクティブとし、ステップ〔２１７〕でこのレ
ジスタが格納しているデータワードを０検出器９０に送
ってその値が０であるか否かを識別する。 ・ もし、その値が０であればステップ（２１８）で行
番号を＋１してステップ（２１９）でこの行番号が行列
内に存在することを確認してステップ〔２１６〕に戻り
、（８１式から（９）式への変換について先に説明した
ように、ステップ（２１５）で指定された要素の値が０
でない行を見つける。 ステップ（２２０）は行の入れ換えが必要か否かを判断
し、入れ換えが必要でなければ直接、入れ換えが必要で
あればステップ（２２１）ないし〔２２６〕の処理を行
って（９）式に示す行列を■において生成する。 このステップ（２２１）および（２２２）においては、
Ｐ行に属するゲートＦをアクティブにして入換用レジス
タＲ１にランチパルスを出力するとともにＬＰ行目のレ
ジスタのゲートＦをアクティフ゛にして入れ換えられる
べきデータワードを格納していたレジスタの値をこの入
換用レジスタＲ１にストアさせ、続くステップ（２２３
）および〔２２４〕においては同様に入れ換えるべき要
素の値を入換用レジスタＲ２にストアさせ、次いでステ
ップ（２２５）および（２２６）においてはこれら入換
用レジスタＲ１、Ｒ２にストアされていたデータワード
を要素を格納するレジスタ入れ換えて戻し、これによっ
て行の入れ換えを行い、（９）式に示す行列が得られる
。 この処理は行を単位として同一の行に属するすべてのレ
ジスタについて同時に行われるので、１回の処理時間で
行の入れ換えが完了する。 第７図（ｅ）は第１図（Ｃ）の処理に相当する処理を行
うフローであって、ステップ（２２７１においては除算
を行うために逆数テーブル１ ／ ｘの出力が各列ごと
に設けられている乗算器Ｘ社供給されるようにセレクタ
を切換え、先に第１図（Ｃ）のステップ〔１９〕で説明
した除算を同一の行に属するすべての要素について同時
並列に実行し、ステップ〔２２８〕においてもとのレジ
スタに除算を行った結果を書込む。 ステップ（２２９）によって第１図（Ｃ）のステップ〔
２２〕の処理、すなわち既に演算が終了している行を除
き、ステップ（２３０）ないしく ２３３）において〔
２３〕ステツプに対応する処理、すなわち前記（１０）
式から（１１）式への変形を行い、ステップ〔２３４〕
において次の行を指定するとともに（２３５）のステッ
プにおいてこの行列内にあることを確認しながら上記の
処理を各行について繰り返すものである。 レジスタａム 、デのゲートＢをアクティブにしてこの
レジスタの値を演算処理部８０に送り、セレクタ８２は
この値を直接乗算器８３１〜８３５の一方の入力端子に
供給するように切換えるとともに、これら乗算器の他方
の入力端子にはｉ行に属する各レジスタからゲートＥを
経てこれらレジスタが格納している値を印加することに
よって同一行について同時に乗算を行い、さらにこれに
よって得られた結果をゲー）Ｄを介して送られてきた上
記各レジスタが格納している値と加算器８４によってそ
れぞれ加算してからもとの１行のレジスタにそれぞれ格
納し、これら処理の最終段階である■においては、最初
の処理の場合には前記の（１１）式に示した行列を行列
記憶部６０の各レジスタに生成する。 第７図（ｄ）は第１図（ｄ）に対応するもので、ステッ
プ（２２６）においては列番号に＋１して上記の〔２１
５〕のステップ以降の処理を繰返し、ステップ（２３７
）において最後の列までの処理の終了が検知されたとき
には前記の行列式（１５）が行列記憶部６０の各レジス
タに生成される。 この第７図（ｄ）のステップ（２３８）ないしく ２４
２）の処理は先に第１図（ｄ）のステップ〔３０〕ない
し〔３４〕について説明した処理と同様であって、誤り
位置多項式の係数が順次水められる。なお、この誤り位
置多項式の最高次の項の係数は常に１であるから必ずし
も算出する必要がないことは前述のとおりである。 また、この第６図および第７図についての説明は、誤り
位置多項式の係数を算出する場合についてのものである
が、第６図（ａ）に示したフローで行列記憶部６０の各
レジスタに記憶させるデータワードを（２０）式の左辺
第１項の行列のデータワードとすれば、上記誤り位置多
項式の係数を求める処理とい同一の処理を行うことによ
って誤りパターンを求めることができることは先に述べ
たとおりである。 以上の説明はＧＦ （２” ）上のリードソロモン符号
についてのものであるが、本発明はガロア体によって制
限を受けるものではなく、また、訂正符号としてｂ−隣
接符号などの他のロングディスタンスコードを用いた場
合にも適用できることは明らかであろう。 また、行列を転置した場合にも本発明による誤り訂正装
置を適用し得ることもまた明らかであろう。 〔効 果〕 本発明によれば、行列式の解を直接的な演算によって求
めるものではなく、行列式の変形とこの行列を構成する
データワードについての演算とによって解を得ることが
できるのでその処理が極めて簡単になり、演算装置に過
大な負担をかけることもなく、処理を迅速化することが
できるという格別の効果を達成できる。 特に、第６図に示した誤り訂正装置のように、各列に演
算手段を配置することによって１つの行を単位として各
列の要素を並列的に処理を行うように構成すればさらに
その処理時間を短縮することができる。
第１図は本発明の誤り訂正方式により誤り位置多項式の
係数を求めるフローチャート、 第２図は本発明の誤り訂正方式により誤りパターンを求
めるために変更されたフローチャート、 第３図ないし第６図は本発明による誤り訂正装置の実施
例を示す図、 第７図は第６図の誤り訂正装置によって誤り位置多項式
の係数を求めるフローチャート、第８図はモデュロ２の
演算テーブルの例、第９図はガロア体上の乗数表現と１
０進表現との対応を示すテーブルの例である。 特許出願人 株式会社 リコー第１区 （ｂ） １図 （Ｑ） 第 ：２図 省孝（９ミ］丁ｚ−１５：ｔの９２′ｉ式＝しイｙ’」
第４図
係数を求めるフローチャート、 第２図は本発明の誤り訂正方式により誤りパターンを求
めるために変更されたフローチャート、 第３図ないし第６図は本発明による誤り訂正装置の実施
例を示す図、 第７図は第６図の誤り訂正装置によって誤り位置多項式
の係数を求めるフローチャート、第８図はモデュロ２の
演算テーブルの例、第９図はガロア体上の乗数表現と１
０進表現との対応を示すテーブルの例である。 特許出願人 株式会社 リコー第１区 （ｂ） １図 （Ｑ） 第 ：２図 省孝（９ミ］丁ｚ−１５：ｔの９２′ｉ式＝しイｙ’」
第４図
Claims (7)
- （１）ロングディスタンスコードの復号に際して、シン
ドロームから誤り位置多項式の各項の係数あるいは誤り
パターンを求めるために、 ｐ行（ｐ＋１）列の行列の各要素ｑ＿ｉ、＿ｊにデータ
ワードＡ＿（＿ｉ＿＋＿ｊ＿−＿２＿）〔但し、１≦ｉ
≦ｐ）１≦ｊ≦ｐ＋１、Ａ＿０〜Ａ＿２＿ｐ＿−＿１は
シンドロームあるいは誤り位置〕を設定し、 この行列を左基本変形することにより、上記多項式の係
数を求めることを特徴とするロングディスタンスコード
における誤り訂正方式。 - （２）ロングディスタンスコードの復号に際して、ロン
グディスタンスコードにより訂正可能な最大の数ｔを超
えないｎ個の誤りの場合に、シンドロームから誤り位置
多項式の各項の係数を求めるために、 上記ｐを誤りの数ｎとしたｎ行（ｎ＋１）列の行列の各
要素ａ＿ｉ、＿ｊのデータワードとしてシンドロームＳ
＿（＿ｉ＿＋＿ｊ＿−＿２＿）をそれぞれ設定し、この
行列を左基本変形することにより、誤り位置多項式の係
数を求めることを特徴とする特許請求の範囲第１項記載
のロングディスタンスコードにおける誤り訂正方式。 - （３）ロングディスタンスコードの復号に際して、誤り
位置とシンドロームとによってそれぞれの誤り位置に対
応した誤りパターンを求めるために、 上記ｐをｎとしたｎ行（ｎ＋１）列の行列の、要素ａ＿
ｉ、＿ｊのデータワードとしてＶ＿ｉ＾ｊ＾−＾１〔但
し、１≦ｉ≦ｎ、１≦ｊ≦ｎ、Ｖ＿１〜Ｖｎは誤り位置
〕を、また、要素ａ＿ｉ、＿ｎ＿＋＿１のデータワード
としてシンドロームＳ＿ｉ＿−＿１をそれぞれ設定し、 この行列を左基本変形することにより、それぞれの誤り
パターンを求めることを特徴とする特許請求の範囲第１
項記載のロングディスタンスコードにおける誤り訂正方
式。 - （４）演算を要する要素の数が少ないときには、すべて
の要素のデータワードが０である行および列を追加する
ことによって、要素の配列を変更することなく同一の処
理を行い得るようにしたことを特徴とする特許請求の範
囲第１項記載のロングディスタンスコードにおける誤り
訂正方式。 - （５）ロングディスタンスコードの復号に際して、シン
ドロームから誤り位置多項式の各項の係数あるいは誤り
パターンを求めるために、 ｐ行（ｐ＋１）列の行列の各要素ｑ＿ｉ、＿ｊに対応す
るデータワードＡ＿（＿ｉ＿＋＿ｊ＿−＿２＿）をそれ
ぞれ格納するメモリ（Ｍ＿ｉ、＿ｊ）と、 このメモリの入出力バス（Ｂ）に接続されたモデュロ２
の演算を行う演算器（Ｃ）を備えることを特徴とするロ
ングディスタンスコードの誤り訂正装置。 - （６）入出力バス（Ｂ）にデータワードを入れ換えるた
めのバッファ（Ｄ）がさらに接続されていることを特徴
とする特許請求の範囲第５項記載のロングディスタンス
コードの誤り訂正装置。 - （７）ｐ行（ｐ＋１）列の行列の各要素ｑ＿ｉ、＿ｊに
対応するデータワードＡ＿（＿ｉ＿＋＿ｊ＿２）をそれ
ぞれ格納するメモリ（Ｍ＿ｉ、＿ｊ）の各列ごとに演算
器（Ｃ＿１、Ｃ＿２、……Ｃ＿ｐ＿＋＿１）とデータワ
ードを入れ換えるためのバッファ（Ｄ＿１、Ｄ＿２、…
…Ｄ＿ｐ＿＋＿１）とを備え、各行に属するデータワー
ドの処理を並行して行うようにしたことを特徴とする特
許請求の範囲第６項記載のロングディスタンスコードの
誤り訂正装置。
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP10016987A JPS63267018A (ja) | 1987-04-24 | 1987-04-24 | ロングデイスタンスコ−ドの誤り訂正方式および誤り訂正装置 |
| US07/185,079 US4937829A (en) | 1987-04-24 | 1988-04-22 | Error correcting system and device |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP10016987A JPS63267018A (ja) | 1987-04-24 | 1987-04-24 | ロングデイスタンスコ−ドの誤り訂正方式および誤り訂正装置 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPS63267018A true JPS63267018A (ja) | 1988-11-04 |
Family
ID=14266818
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP10016987A Pending JPS63267018A (ja) | 1987-04-24 | 1987-04-24 | ロングデイスタンスコ−ドの誤り訂正方式および誤り訂正装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS63267018A (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP0407101A3 (en) * | 1989-06-28 | 1992-04-08 | Digital Equipment Corporation | Error detection and correction system for long burst errors |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS59123945A (ja) * | 1982-12-29 | 1984-07-17 | インタ−ナシヨナル ビジネス マシ−ンズ コ−ポレ−シヨン | 多数バイトエラ−訂正システム |
| JPS59124011A (ja) * | 1982-12-29 | 1984-07-18 | インタ−ナシヨナル ビジネス マシ−ンズ コ−ポレ−シヨン | 多数バイトエラ−訂正システム |
-
1987
- 1987-04-24 JP JP10016987A patent/JPS63267018A/ja active Pending
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS59123945A (ja) * | 1982-12-29 | 1984-07-17 | インタ−ナシヨナル ビジネス マシ−ンズ コ−ポレ−シヨン | 多数バイトエラ−訂正システム |
| JPS59124011A (ja) * | 1982-12-29 | 1984-07-18 | インタ−ナシヨナル ビジネス マシ−ンズ コ−ポレ−シヨン | 多数バイトエラ−訂正システム |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP0407101A3 (en) * | 1989-06-28 | 1992-04-08 | Digital Equipment Corporation | Error detection and correction system for long burst errors |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP3959788B2 (ja) | 縦及び横のパリティコードを有するデータフレームにおけるエラーを修正するシステム | |
| KR930003997B1 (ko) | 에러 정정부호의 복호방법 및 복호장치 | |
| US4928280A (en) | Fast processor for multi-bit error correction codes | |
| JPH0444447B2 (ja) | ||
| JPS59124011A (ja) | 多数バイトエラ−訂正システム | |
| EP0836285B1 (en) | Reed-Solomon decoder with general-purpose processing unit and dedicated circuits | |
| JP3281387B2 (ja) | Ｃｒｃ／ｅｄｃチェッカシステム | |
| JPS632370B2 (ja) | ||
| JP3502583B2 (ja) | 誤り訂正方法および誤り訂正装置 | |
| JPS6114540B2 (ja) | ||
| JP2662472B2 (ja) | 誤り訂正処理用シンドローム演算回路 | |
| JP3614978B2 (ja) | ガロア体の除算方法および除算装置 | |
| JP2553565B2 (ja) | ガロア体演算装置 | |
| JPH07226687A (ja) | 誤り訂正処理装置 | |
| JPH02164133A (ja) | ロングディスタンスコードの誤り訂正装置 | |
| JP2907138B2 (ja) | 誤り訂正の演算処理方法及び処理回路 | |
| JP3252421B2 (ja) | ユークリッドの互除回路 | |
| JP3231811B2 (ja) | 行列演算回路 | |
| JP2000295116A (ja) | 誤り修正符号化方法 | |
| JPH0750595A (ja) | 復号化装置 | |
| JPH01158826A (ja) | ロングディスタンスコードの誤り訂正方式 | |
| JPH0834439B2 (ja) | ガロア体演算装置 | |
| JPH10308675A (ja) | リードソロモン復号装置 | |
| JPH0267826A (ja) | ロングディスタンスコードの誤り訂正装置 | |
| JPH08272634A (ja) | アドレス生成回路 |