JPH02215231A

JPH02215231A - 誤り訂正装置

Info

Publication number: JPH02215231A
Application number: JP1036924A
Authority: JP
Inventors: Motoichi Kashida; 樫田　素一; Nobuitsu Yamashita; 伸逸山下
Original assignee: Canon Inc
Current assignee: Canon Inc
Priority date: 1989-02-16
Filing date: 1989-02-16
Publication date: 1990-08-28
Anticipated expiration: 2013-10-15
Also published as: JP2810397B2; US5155734A

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】〔産業上の利用分野〕本発明は誤り訂正装置に関し、特にその処理速度の高速
化に関するものである。

〔従来の技術〕

従来、プログラム制御形式の誤り訂正装置において、プ
ログラムのジャンプ（処理の移行）の判断及びこれに伴
うプログラムカウンタの変更はある判定結果がでる毎に
、その度実行されている。

従−来の処理の過程をリードソロモン符号のシンドロー
ム判定を例として説明する。リードソロモン符号は巡回
型の多元ブローク符号であり、近年様々な分野に応用さ
れ広く知られる様になった。

今、符号長（ｎ）、情報シンボル（ｋ）個、検査シンボ
ル（ｎ−ｋ）個からなるリードソロモン符号について、
その復号法を説明する。但し、上記各シンボルは（ｍ）
個の２進ビツトつまり２−個の元を有する有限体である
ガロア体ＧＦ　（２”）の元である。

そして、この場合（１）重エラー訂正リードソロモン符
号の生成多項式ｇ　（ｘ）は、（α）をガロア体ＧＦ　
（２“）の原始光として次の（１）式または（２）式の
ように表わされる。

ｇ（ｘ）＝（ｘ＋α）（Ｘ＋α２）・・・（Ｘ＋αジ　　　　・・・・・・・・・・・・・
・・・・・　（１）ｇ（ｘ）＝（ｘ＋α。）（Ｘ十α）・・・（Ｘ＋α２１−１　）　　　　・・・・・・・・
・・・・・・・・・・　（２）また、送信符号語をＣ（
ｘ）、受信符号語をＲ（ｘ）で表わし、且つエラー多項
式をＥ（ｘ）とすると、これらの間には次のような関係
が成立する。

Ｒ（ｘ）　＝　Ｃ（ｘ）　＋　Ｅ（ｘ）　　　　　　・
・・・・・・・・・・・・・・・・・・　（３）この場
合、多項式の係数はガロア体ＧＦ（２’）に含まれてお
り、エラー多項式Ｅ　（ｘ）はエラーロケーションおよ
び値（大きさ）に対応する項だけを含んでいる。

従って、位置Ｘｉにおけるエラー値をＹｌとするとＥ（
ｘ）　　＝ΣＹＪｘ’　　　　　　　　　　・・・・・
・・・・・・・・・・・　（４）となり、該（４）式で
Σはエラーのすべての位置にわたる総和を意味している
。

ここで、シンドロームＳ１をＳ＋＝Ｒ（α１）〔但しｉ＝ｏ、　　１・・・２ｔ　−
１）・・・（５）の如く定義したとすると、上記（３）
式より５ｉ＝Ｃ（α’）　＋Ｅ　（α′）となる。

この場合、Ｃ（ｘ）はｇ　（ｘ）で常に割り切れるので
Ｃ（α１）−〇であるから５ｉ＝Ｅ　（α′）となる。そこで、上記（４）式よりＳ　＋　＝　Ｅ　（ａ’　）　　＝　ΣＹｌ（（Ｚ’）
’−ΣＹ　ｊＸ＋’−・・（６）と表わすことができる
。但し、αＩ　：＝　Ｘ　、とおいたもので、ｘＩはα
Ｉにおけるエラーロケーションを表わしている。

ここで、エラーロケーション多項式σ（Ｘ＞はエラー数
をｅとして／ σ（ｘ）　＝　ＴＩ　（ｘ−Ｘ＋）＝ｘ１＋σＨｘ’−’＋・・・十σ。・・・・・・・・
・・・・・・　（７）と定義される。

また、（７）式のび、〜σ。はシンドロームＳｌとの間
で次のように関係付けられる。

Ｓ＋＋ｅ　　＋　σ　Ｉ　Ｓ＋＋ｅ−１＋　・・・　σ
　ｅ−Ｉ　Ｓ　＋＋＋　　＋　σ　ｅＳｉ　　　・・・
　（８）つまり、以上のようなリードソロモン符号の復
号手順は（Ｉ）　（５）式によりシンドロームＳ１を計算する。

（ｎ）　（８）式によりエラーロケーション多項式の係
数σ１〜σ。を計算する。

（ｍ）（７）式によりエラーロケーション多項式の根Ｘ
ｊを求める。

（ＴＶ）（６）式によりエラー値Ｙｌを求め、（４）式
によりエラー多項式を求める。

（Ｖ）（３）式によりエラー訂正を行う。

なる（Ｉ）〜（Ｖ）の手順に帰着せしめられる。

次に、以上のような復号手順によるエラー訂正の具体例
として、ｌブロックデータに４個の検査シンボルを用い
た場合について説明する。

すなわち、この場合の生成多項式ｇ　（Ｘ）はｇ（翼＞
　＝（ｘＩ１）（ｘ＋α）（Ｘ＋α２）（ｘＩα３）となり、２重エラーまでの訂正が可能となるものである
。

今、実際に誤り訂正を行う場合を考えると、想定される
エラーの数ｅはｅ　”　Ｏ＋　ｅ　＝１　＋　ｅ　”　
２ｒ　ｅ≧３の場合が考えられる。ｅ＝ｏの場合には受
信符号語が正しいのであるから、誤り訂正処理は行わな
い。またｅ≧３の場合も訂正能力を越えているわけであ
るから、エラーフラグを立てること以外の誤り訂正処理
は行わない。即ち、実際にはｅ＝１の場合とｅ＝２の場
合に誤り訂正処理を行うことになる。

誤り訂正処理としては、上述の復号手順（■）。

（ｎ）に対応して概路次の様な手順をふむ。

（ａ）シンドローム８０〜Ｓ３を計算する。

（ｂ）シンドロームＳ。〜Ｓ３を検査し、５ｏ＝Ｓ。

＝８２＝８３＝０の４合は、ｅ＝ｏと判断して誤り訂正
処理を終了する。更に、シンドロームＳ。

〜Ｓ３のうち、いずれか１つの値のみがＯの場合はｅｆ
−１であり、いずれか２つ以上の値がＯの場合にはｅ≧
３であることが（６）式から明らかである。

（Ｃ）　（＆）式をｅ＝１．ｅ＝２について書き直すと
、ｅ＝１の場合にはとなる。また、ｅ＝２の場合にはとなる。

ここで、実際の復号器がｅ＝１の場合から動作を始める
ものとすると、先ず連立方程式（９）を満足する解σ１
を求めなければならない。そして、この解が存在しなけ
れば、復号器は次にｅ＝２の場合について連立方程式（
１０）を満足する解σ１．σ２を求めなければならない
。なお、ここでも解が得られない場合はｅ≧３とみなす
ことになる。

（９）式の解σ１はとして求め、（１０）式の解σ１．σ２はとして求める
。

これらの手順において各ステップで様々な式の値の判定
を行い、判定結果に従って処理過程を表すプログラムの
流れを変える必要がある。

例えば、前記（ｂ）のステップに於いてシンドロームＳ
。−３３の値によってエラーの数ｅは第１表の様に判定
できる。

第　　１表また、これらの判定に従う処理の流れを第３図のフロー
チャートに示す。第３図中「ｅ≧３」で示すステップは
、エラー数が３以上であると判断し、訂正能力オーバー
の処理ルーチンへ移行することを示す。「ｅ≧２」で示
すステップは、エラー数が２以上であると判断し、２訂
正の処理ルーチンへ移行することを示す。更に「ｅ≧１
」で示すステップは、エラー数が１以上であると判断し
、１訂正の処理ルーチンへ移行することを示す。

また、上述の如くプログラムの流れを変える、即ち、プ
ログラムのジャンプを行う例として、上述（Ｃ）のステ
ップに於いてエラーロケーション多項式の係数σ１．σ
２を計算する際、その分母（Ｓｌ＋５Ｏ８２）及び分子
（ＳＯ３３＋Ｓ、Ｓ２）。

（ＳＩＳ　ａ　＋　Ｓ　２”）がＯであるか否か判定し
、これらの判定結果に従いプログラムジャンプを行うこ
とが考えられる。即ち、上記分母（Ｓｌ”＋５Ｏ８２）
が０の場合には、訂正能力オーバーの処理ルーチンへ移
行させ、分子（ＳＯ３３＋５ＩＳ２）ｌ　　（ＳｔＳ３
＋８２２）のいずれかがＯの場合には１訂正の処環ルー
チンへ移行させるものである。

〔発明が解決しようとする問題点〕

しかしながら、上記従来例では例えば第３図のフローチ
ャート中“Ｙ＃の場合にプログラムをジャンプさせると
すると「ｅ≧２」で示すステップを介して２訂正ルーチ
ンへ行（までには１又は２回のジャンプを必要とし、ｒ
ｅ＝ＯＪで示すステップを介してノーエラールーチンへ
行くまでに４回程度のプログラムジャンプを必要とする
。しかも、これらのプログラムの記述にはかなりのプロ
グラムステップ領域を費やすことが第３図より明らかで
ある。

また、前述したエラーロケーション多項式の係数σ０．
σ２を演算する過程に於いても同様に、（Ｓｌ”　＋Ｓ
ＯＳ２　）ｌ　　（ＳＯＳ３＋ＳＩ　Ｓ２　）ｌ　　Ｃ
８＋　Ｓ３＋ｓ２’）が夫々０であるか否かを判定する
ステップを順次行った場合に於いても同様にプログラム
のステップ領域が大きくなる。

この様にプログラムステップ領域が大きくなり、プログ
ラムジャンプの機会が増えると、このプログラムの実行
に時間がかかり、高速の処理が行えない。そのため、高
ビットレートの受信符号を処理することが困難であった
。

〔問題点を解決するための手段〕

かかる背景下に於いて、本発明にあっては誤り訂正符号
を含む受信符号の誤りを訂正する装置において、複数種
の誤り訂正処理を有する処理プログラム中、該複数種の
処理のいずれかへの処理の移行を判断する基準となる複
数の判定符号を前記受信符号に基き順次形成する第１の
手段と、該複数の判定符号を同時に出力する第２の手段
と、該同時出力された複数の判定符号に従い前記プログ
ラム中の処理の移行を実行する第３の手段とを備える構
成とした。

〔作　用〕

上述の如く構成することにより、処理プログラム中の処
理の移行回数を少な（することができ、プログラムステ
ップ領域を小さくでき、高速処理が実現できる。

〔実施例〕

以下、本発明の実施例について説明する。

第１図は本発明の一実施例としての誤り訂正装置の要部
をなすプログラム処理回路の構成を示す図である。

図中、１は受信符号語の入力端であり、伝送路で発生し
た誤りを含んだ符号語列が入力される。シンドローム計
算回路２ａ、　２ｂ、　２ｃ、　２ｄは夫々シンドロー
ムＳＯ＋　Ｓｌ＋　Ｓ２＋　ｓ３を（６）式に従って演
算する回路である。処理はあらかじめ記述されたプログ
ラムに従って行われるが、その−部を記すと、まず、Ｓ
ｏのゲートを開いてデータバスＤＢにシンドロームＳ。

を出力し、これを−時記憶回路（ＲＥＧ）３が一時記憶
する。次に、５ｏ＝Ｏのチエツクのためプログラムメモ
リより値Ｏをデータバス（ＤＢ）に出力し、これをＲＥ
Ｇ４が一時記憶する。

この時、第１の手段を構成する算術演算ユニット（ＡＬ
Ｕ）８ではＲＥＧ３の出力と、ＲＥＧ４の出力を比較し
、その比較結果を１ビツトデータとして出力する。即ち
、シンドロームＳ０がＯの時にＡＬＵ８は「０」、シン
ドロームＳ０がＯ以外の時にＡＬＵ８は「１」を出力す
る。このＡＬＵ８の出力はシフトレジスタ５に１ビツト
データとして入力されることになる。

上述の如き処理をシンドロームＳ、、Ｓ２．Ｓ３につい
て繰り返すことにより、第２の手段を構成するシフトレ
ジスタ５に各シンドローム８０〜ｓ３が０であるか否か
を示すデータ（判定符号）は４つ記憶されており、４ビ
ツトデータとされている。

ここで、第１表の判定結果を上記ＡＬＵ８の出力である
１ビツトデータとして表現し、移行しようとするルーチ
ンをエラー数に対応づけてｒＯＪ、　　ｒｌＪ。

ｒ２Ｊ、　　ｒ３Ｊで表現した場合の対応を第２表に示
す。

第　　２表比較器６に第２表のルーチン「０」に対応する４ビツト
パターンｒｏｏｏＯＪをデータバスＤＢより入力する。

この時、プログラムカウンタ７には、ルーチンｒＯＪを
実行するためのプログラムのジャンプ先のアドレス（ｋ
ビット）がデータバスＤＢから入力される。ここで、比
較器６ではシフトレジスタ５の出力とｒｏｏｏｏＪとを
比較し、一致する時、プログラムカウンタを上記ジャン
プ先アドレスデータでプリセットする。これに伴い不図
示の処理部によりルーチン「０」の処理が実行される。

次に、比較器６にルーチン「１」に対応する４ビツトパ
ターンｒｌｌｌｌＪをデータバスＤＢより入力し、同様
にシフトレジスタ５の出力がｒｌｌｌｌＪである場合に
はプログラムカウンタ７はルーチンｒｌＪに対応するジ
ャンプ先アドレスのデータにてプリセットされる。

更に、比較器６にルーチン「２」に対応する４ビットパ
ターンＪＯ１１］、Ｊ及びｒｌｏｌｌＪを順次入力し、
シフトレジスタ５の出力と一致した場合には、ルーチン
「２」に対応するジャンプ先アドレスのデータでプリセ
ットする。

従って、それ以外のデータがシフトレジスタ５に記憶さ
れている場合はルーチン「３」に移る様にプリセットを
行わなければプログラムは自動的にルーチン「３」に移
る様に設計されている。

上述の如く構成することにより、プログラムの流れを変
えるジャンプの回数を減少することができ、全体として
誤り訂正処理速度の高速化、プログラム領域の減少が実
現できる。

第２図は本発明の他の実施例としての誤り訂正装置の要
部をなすプログラム処理回路の構成を示す図であり、図
中第１図と同様の構成要素については同一番号を付し説
明は省略する。

第２図に示した実施例の構成に於いてはシフトレジスタ
５の出力する４ビツトデータはジャンプアドレステーブ
ル９に与えられる。ジャンプアドレステーブル９はデー
タバスＤＢからの制御信号（ＣＯＮＴ）に応答して、上
記４ビツトデータに対応する各ルーチン（第２表参照）
のジャンプ先アドレスを示すデータを出力する。上記、
制御信号Ｃ０ＮＴはプログラムカウンタ７にも入力され
ており、該制御信号Ｃ０ＮＴに応答してテーブル９から
のアドレスデータでプログラムカウンタ７がプリセット
される。

本実施例に於いても、第１図の実施例と同様の効果が得
られるの１１明らかであろう。更に、本実施例に於いて
は上述の第１図の実施例に於いて比較器６の４回の比較
動作を唯一つのステップで実行でき、更に処理の高速化
が図れる。

上述の実施例はシンドロームＳ。＋　Ｓｌ＋Ｓ２＋Ｓ３
がＯであるか否かの判定結果を判定符号とし、同時に出
力することにより処理の高速化を実現したが、前述した
エラーロケーション多項式の係数σ２．σ２の分子９分
母が０であるか否かの判定結果を判定符号として本発明
を適用しても同様の効果が得られる。

例えば、第２図に示す構成をそのまま利用して、ＲＥＧ
３ｊ：　（Ｓ　１”＋Ｓ　Ｏ３２）、（Ｓｏ　Ｓ３　＋
５１３２　）。

（Ｓ、Ｓ３＋３２”）を順次記憶させ、ＲＥＧ４には０
を記憶させることで、シフトレジスタ５にはこれらのデ
ータが０であるか否かを示す１ビツトの判別符号が順次
入力される。そして、これらのデータをジャンプアドレ
ステーブルに制御信号Ｃ０ＮＴと共に供給することによ
り所望のルーチンへプログラムが移行する。

尚、上述の実施例は２訂正リ一ドソロモン符号を例にと
って説明したが、本発明は他の誤り訂正符号による誤り
訂正装置に適用して同様の効果が得られる。

〔発明の効果〕

以上説明した様に、本発明によれば処理の高速化、更に
はプログラム領域を小さくできる誤り訂正装置が得られ
るものである。

【図面の簡単な説明】

第１図は本発明の一実施例としての誤り訂正装置の要部
をなすプログラム処理回路の構成を示す図、第２図は本
発明の他の実施例としての誤り訂正装置の要部をなすプ
ログラム処理回路の構成を示す図、第３図は従来の誤り訂正処理に於ける処理の移行動作を
説明するためのフローチャートである。図中、ｌは受信符号の入力端、２ａ、　　２ｂ、　２ｃ
。２ｄはシンドローム演算回路、３，４は一時記憶回路、
５はシフトレジスタ、６は比較器、７はプログラムカウ
ンタ、８は算術演算ユニット、９はジャンプアドレステ
ーブル、ＤＢはデータバスである。

Claims

【特許請求の範囲】

（１）誤り訂正符号を含む受信符号の誤りを訂正する装
置であって、複数種の誤り訂正処理を有する処理プログ
ラム中、該複数種の処理のいずれかへの処理の移行を判
断する基準となる複数の判定符号を前記受信符号に基き
順次形成する第１の手段と、該複数の判定符号を同時に
出力する第２の手段と、該同時出力された複数の判定符
号に従い前記プログラム中の処理の移行を実行する第３
の手段とを備える誤り訂正装置。
（２）前記複数種の処理は１訂正処理及び２訂正処理を
含み、前記第１の手段は複数のシンドロームを演算する
手段を含むことを特徴とする特許請求の範囲第（１）項
記載の誤り訂正装置。
（３）前記複数の判定符号は前記複数のシンドロームが
夫々０であるか否かを示す符号であることを特徴とする
特許請求の範囲第（２）項記載の誤り訂正装置。
（４）前記第１の手段は前記複数のシンドロームを用い
てエラーロケーション多項式の複数の係数を演算する手
段を含み、前記複数の判定符号は前記複数の係数の分子
、分母が０であるか否かを示す符号であることを特徴と
する特許請求の範囲第（２）項記載の誤り訂正装置。