JPH05308294A

JPH05308294A - 誤り訂正装置および訂正方法

Info

Publication number: JPH05308294A
Application number: JP4113401A
Authority: JP
Inventors: Junko Nakase; 純子中瀬; Nobukazu Doi; 信数土居; Toshiharu Nakatomi; 俊治中富
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1992-05-06
Filing date: 1992-05-06
Publication date: 1993-11-19

Abstract

(57)【要約】【目的】動作不要な演算部を休止させることにより、
消費電力を低減させて、集積化に適した誤り訂正装置を
実現する。【構成】シンドロ−ムから誤り位置と誤り数値を求め
る回路を、ガロア体演算部とチェンサ−チ演算部とこれ
らを制御する制御部で構成する。そして、制御部によ
り、ガロア体演算部とチェンサ−チ演算部の動作をそれ
ぞれ独立に休止させる。これにより、消費電力を減少さ
せる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、誤り訂正装置および訂
正方法に関し、特に多シンボルの誤りを訂正する場合に
有効であり、消費電力が少ない誤り訂正装置および訂正
方法に関する。

【０００２】

【従来の技術】従来より、ディジタル信号を磁気テ−プ
等の記録媒体やＭＯＳ型半導体等の記憶媒体に記録する
場合、記録デ−タを誤り訂正符号（Ｅrror Ｃorrectin
g Ｃodes:ＥＣＣ）の符号語として記録し、再生時に誤
り訂正符号を復号して誤りを訂正している。誤り訂正装
置としては、例えば、村上，須田『ディジタルＶＴＲ用
信号処理ＬＳＩ』誤り訂正装置がある（テレビジョン学
会誌、Ｖol.43,Ｎo.12 (1989),pp.1333〜1339に記載さ
れている）。図２は、従来の誤り訂正装置のブロック図
である。誤り訂正装置は、図２に示すように、シンドロ
−ム演算ブロック８と、誤り位置・誤り数値導出ブロッ
ク９と、訂正ブロック１０と、遅延ブロック１１とから
構成されている。シンドロ−ム演算ブロック８では、入
力される誤り訂正符号の符号語のデ−タをもとにシンド
ロ−ムを計算する。次に、誤り位置・誤り数値導出ブロ
ック９では、シンドロ−ムをもとに誤り位置と誤り数値
を求める。ここで、誤り位置とは、符号語のどのシンボ
ルが誤っているかを示すものであり、誤り数値は、誤り
位置で生じた誤りの０／１パタ−ン（間違ったビットに
１を立てたもの）である。訂正ブロック１０では、遅延
ブロック１１から読み出された符号語のデ−タの誤り位
置に対して誤り数値との排他的論理和をとって訂正を行
う。これらのシンドロ−ム演算ブロック８、誤り位置・
誤り数値導出ブロック９、および訂正ブロック１０は、
３段のパイプライン動作を行うように構成される。

【０００３】

【発明が解決しようとする課題】前述の誤り訂正装置
は、半導体技術の進歩により１チップで実現することも
可能になった。しかしながら、回路自体の集積化が可能
であっても、大規模な回路を高速動作させる場合には、
消費電力が大きくなってしまうため、ＬＳＩ化に支障を
きたすことがある。誤り訂正シンボル数が増加すると、
誤り位置・誤り数値導出ブロックで実行すべきオペレ−
ション数も増加してしまうため、電力消費の増加も顕著
となる。本発明の目的は、このような従来の課題を解決
し、誤り訂正シンボル数が多い場合でも、消費電力を低
減することができ、集積化に適した誤り訂正装置および
訂正方法を提供することにある。

【０００４】

【課題を解決するための手段】上記目的を達成するた
め、本発明の誤り訂正装置は、（イ）入力された誤り訂
正符号を基にシンドロ−ムを算出する第１の演算手段
と、第１の演算手段の出力を基に誤り位置と誤り数値を
求める第２の演算手段と、第２の演算手段の出力を基に
誤り訂正符号の訂正を行う訂正手段とを備え、第１の演
算手段と第２の演算手段と訂正手段とでパイプライン動
作を行わせる誤り訂正装置において、第２の演算手段
は、少なくとも、シンドロ−ムを基に誤り位置多項式お
よび誤り数値多項式の係数を求め、かつ誤り数値多項式
の係数と誤り位置から誤り数値を求めるガロア体演算部
と、ガロア体演算部から受け取った誤り位置多項式の係
数を基にチェンサ−チを実行し、誤り位置を求めるチェ
ンサ−チ演算部と、ガロア体演算部およびチェンサ−チ
演算部に対してそれぞれ演算を行わない期間に動作を休
止させるように制御する制御部とで構成することを特徴
としている。また、（ロ）ガロア体演算部は、少なくと
もガロア体任意元の積和を求める積和手段と、積和手段
の出力を保持する複数のレジスタと、積和手段の入力を
選択する複数のマルチプレクサとから構成され、またチ
ェンサ−チ演算部は、少なくとも、誤り位置多項式の係
数を基にガロア体固定係数乗算を行う演算手段と、誤り
位置多項式に代入する元またはその逆元を生成するガロ
ア体カウンタと、演算手段の出力の零を検出する零検出
手段と、零検出手段の制御によりガロア体カウンタの出
力を保持するレジスタとから構成されることも特徴とし
ている。また（ハ）ガロア体演算部は、ガロア体任意元
の積和を求める積和手段と、ガロア体の逆元を求める逆
元手段と、積和手段および逆元手段の出力を保持する複
数のレジスタと、積和手段および逆元手段の入力を選択
する複数のマルチプレクサとを具備することも特徴とし
ている。また、（ニ）積和手段は、ガロア体積和機能
と、ガロア体任意元の乗算機能およびガロア体任意元の
加算機能の２つの機能のうちの少なくとも１つの機能を
有し、制御信号により複数の上記機能が切り替えられる
ように構成されることも特徴としている。また、（ホ）
チェンサ−チ演算部は、ガロア体固定係数の乗算を行う
演算手段を有し、演算手段には、少なくとも誤り位置多
項式の係数とガロア体固定係数乗算器の出力とを選択す
るマルチプレクサと、マルチプレクサの出力をラッチす
るレジスタと、レジスタの出力にガロア体の固定元を乗
ずるガロア体固定係数乗算器とからなる複数個の演算ユ
ニットと、演算ユニットの複数の出力および誤り位置多
項式の定数項のガロア体加算を行う加算手段とを設けた
ことも特徴としている。また、（ヘ）チェンサ−チ演算
部は、誤り位置多項式に代入する元またはその逆元を生
成するガロア体カウンタを有し、ガロア体カウンタに
は、少なくともガロア体カウンタの初期値とガロア体固
定係数乗算器の出力とを選択するマルチプレクサと、マ
ルチプレクサの出力をラッチするレジスタと、レジスタ
の出力にガロア体の固定元を乗ずるガロア体固定係数乗
算器とを設けたことも特徴としている。また、（ト）第
１の演算手段，第２の演算手段および訂正手段の他に、
入力されたイレ−ジャフラグを基に誤り位置を求める第
３の演算手段を具備し、上記第２の演算手段は、上記第
１の演算手段の出力を基に誤り位置と誤り数値を求める
か、あるいは第１の演算手段の出力と第３の演算手段の
出力を基に誤り数値を求め、また訂正手段は、第２の演
算手段の出力を基に誤り訂正符号の訂正を行うか、ある
いは第３の演算手段で求められた誤り位置と第２の演算
手段で求められた誤り数値を基に訂正を行い、また第２
の演算手段および訂正手段は、外部からの選択信号によ
りそれぞれの動作を切り換えることにより、符号語のみ
から訂正処理を行う第１の訂正方式と、誤り訂正符号お
よびイレ−ジャフラグから訂正処理を行う第２の訂正方
式のいずれか一方を実行して、第１の訂正方式を選択し
た場合には、第３の演算手段の動作を休止させることも
特徴としている。さらに、（チ）第２の演算手段は、少
なくとも連続したガロア体の元を生成するガロア体カウ
ンタと、イレ−ジャフラグの制御により該ガロア体カウ
ンタの出力を保持するレジスタと、選択信号を基にガロ
ア体カウンタを制御する制御信号を生成する信号生成手
段とを備え、第１の訂正方式を選択した場合には、ガロ
ア体カウンタの動作を休止させることも特徴としてい
る。また、本発明の誤り訂正方法は、（リ）シンドロ−
ムを基に誤り位置と誤り数値を求めて、求められた誤り
位置と誤り数値を基に誤り訂正符号を訂正して出力する
誤り訂正方法において、ガロア体の固定係数乗算を行う
ガロア体演算部と、ガロア体の固定係数乗算を行うチェ
ンサ−チ演算部は、パイプライン動作１，２，３の順序
で処理を実行し、先ず動作（１）では、ガロア体演算部
でシンドロ−ムを基に誤り位置多項式・誤り数値多項式
の係数を求める一方、チェンサ−チ演算部では動作を休
止し、次に動作（２）では、求められた誤り位置多項式
の係数を基にチェンサ−チを実行して、誤り位置を導出
する一方、ガロア体演算部では動作を休止し、次に動作
（３）では、求められた上記誤り位置と既に求められて
いる誤り数値多項式の係数を基に誤り数値を求める一
方、上記チェンサ−チ演算部では動作を休止することを
特徴としている。また、（ヌ）ガロア体演算部の動作を
休止させるときには、演算が不要な期間に、ガロア体演
算部を構成する複数のマルチプレクサの入力信号および
制御信号を固定にするか、あるいはガロア体演算部を構
成する複数のレジスタを入力デ−タのラッチを行わない
ホ−ルド状態にし、またチェンサ−チ演算部の動作を休
止させるときには、演算が不要な期間に、チェンサ−チ
演算部を構成するレジスタを入力デ−タのラッチを行わ
ないホ−ルド状態にするか、あるいはチェンサ−チ演算
部を構成するマルチプレクサの入力信号および制御信号
を固定にすることも特徴としている。

【０００５】

【作用】本発明においては、誤り位置・誤り数値導出ブ
ロックとして、ガロア体演算部とチェンサ−チ演算部と
を用いて、それぞれの動作が不要な期間だけ独立に休止
させることにより、消費電力を低減させる。従来におい
ても、誤り位置・誤り数値導出ブロックとして、ガロア
体演算部およびチェンサ−チ演算部を用いたものも存在
するが、いずれも休止することなく、常時動作させてい
るので、訂正シンボル数が増加したときには、オペレ−
ション数が増加して消費電力は著しく増加している。本
発明では、ガロア体の任意元乗算を必要とする誤り位置
多項式・誤り数値多項式の係数導出および誤り数値導出
と、ガロア体の固定係数乗算を必要とするチェンサ−チ
演算とをそれぞれガロア体演算部、チェンサ−チ演算部
で独立に実行することができ、さらに制御部にガロア体
演算部およびチェンサ−チ演算部の動作を各々独立に休
止させることにより、各演算部を休止させることができ
る。さらに、制御部を設けることにより、ガロア体演算
部およびチェンサ−チ演算部の各々が具備する演算器を
制御信号により多重使用することが可能であるため、演
算器の数を減少させることができる。

【０００６】

【実施例】以下、本発明の実施例を、図面により詳細に
説明する。図１は、本発明の一実施例を示す誤り訂正装
置のブロック構成図である。本発明の誤り訂正装置は、
図２の従来構成と同じように、シンドロ−ム演算ブロッ
ク１と、誤り位置・誤り数値導出ブロック２と、訂正ブ
ロック３と、遅延ブロック４とから構成されている。こ
のうち、誤り位置・誤り数値導出ブロック２を、ガロア
体演算部５と、チェンサ−チ演算部６と、それら２つの
演算部の動作を訂正アルゴリズムに基づいて制御する制
御部７とで構成している。なお、ガロア体演算部５に
は、ガロア体の任意元どうしの乗算を行う機能が、また
チェンサ−チ演算部６には、ガロア体の固定係数乗算を
行う機能が、それぞれ設けられている。ガロア体演算部
５では誤り位置多項式の係数を求めて、これをチェンサ
−チ演算部６に渡す。チェンサ−チ演算部６ではこれに
基づいて誤り位置を求め、これをガロア体演算部５に渡
す。このようにして、誤り位置・誤り数値導出ブロック
２では、シンドロ−ム演算ブロック１により求められた
シンドロ−ムを基に誤り位置・誤り数値を求める。求め
られた誤り位置と誤り数値は、次段の訂正ブロック３に
引き渡される。訂正ブロック３では、遅延ブロック４を
介して出される符号語の誤りを訂正し、これを出力す
る。これらのシンドロ−ム演算ブロック１、誤り位置・
誤り数値導出ブロック２、および訂正ブロック３は、３
段のパイプライン構成になっている。

【０００７】図３は、本発明の誤り訂正装置における処
理の伝搬を示す図であり、図４は、図１における誤り位
置・誤り数値導出ブロックの演算内容を示す図である。
図３に示すように、本発明の誤り訂正装置では、符号語
１，２，３，・・・の順序で誤り訂正処理を実行する場
合、各ブロック１，２，３はパイプライン処理を行うこ
とにより、高速に処理を行う。誤り位置・誤り数値導出
ブロック２における演算は、図４に示すように、
（１）、（２）、（３）の３ステップからなる。これら
の各ステップの内容は、先ずステップ（１）として、ガ
ロア体演算部５において、シンドロ−ムを基に誤り位置
多項式・誤り数値多項式の係数を求める。次に、ステッ
プ（２）として、チェンサ−チ演算部６で誤り位置多項
式の係数を基にチェンサ−チを実行し、誤り位置を求め
る。この誤り位置は、ガロア体演算部５に送られる。最
後に、ステップ（３）として、ガロア体演算部５では、
誤り位置と既に求められている誤り数値多項式の係数を
基に誤り数値を求める。制御部７は、各ステップ（１）
〜（３）において、ガロア体演算部５とチェンサ−チ演
算部６の演算の手順を訂正アルゴリズムに基づいて制御
する。さらに、制御部７は、ガロア体演算部５とチェン
サ−チ演算部６の２つの演算部間のデ−タの入出力を制
御するとともに、両演算部において演算が必要でない期
間には、各演算部をそれぞれ休止させるように制御す
る。このような制御部７は、例えば、訂正アルゴリズム
に基づいたプログラムを記憶させたＲＯＭにより実現で
きる。

【０００８】本実施例では、誤り位置・誤り数値導出ブ
ロック２において、動作不要な回路を休止させて、必要
最低限の回路だけ動作させるため、消費電力を低減させ
ることが可能である。また、ガロア体の任意元乗算器
は、ガロア体の固定係数乗算器に比べて回路規模が大き
い。ここで、任意元乗算器とは、ｘ×ｙ等で表わされる
ような未知の値の乗算であるため、ゲ−ト数が多数必要
となり、回路が複雑化する。一方、固定係数乗算器は、
２×ｘ等で表わされるような係数を含む乗算であるた
め、ゲ−ト数は少なくて済み、回路も簡単化できる。例
えば、ガロアフィ−ルドＧＦ（２⁸）上の乗算器で比較
すると、前者は後者の約１０倍の回路規模となる。その
ために、一般的にガロア体の任意元乗算器を具備したガ
ロア体演算部５は、ガロア体の固定係数乗算器を具備し
たチェンサ−チ演算部６に比べると、回路規模が著しく
大である。従って、チェンサ−チの期間にガロア体演算
部５の動作を休止させて、チェンサ−チ演算部６のみを
動作させると、消費電力を低減させることができ、極め
て有効である。また、パリティシンボル数が一定のとき
には、符号語の長さ（シンボル数）が長いほど誤り位置
・数値導出ブロック２における全演算時間に対するチェ
ンサ−チ演算時間の割合は大きい。すなわち、チェンサ
−チ演算部６において、誤り位置を求める場合には、誤
り位置多項式に符号語のシンボル数だけガロア体の元を
代入して演算する必要がある。従って、シンボル数が多
ければ多いほど演算時間がかかることになり、消費電力
は大きくなる。その結果、休止制御により、チェンサ−
チの期間に消費する電力を低減することによる効果は大
である。

【０００９】図５は、図１に示すガロア体演算部の構成
図である。図５に示すように、ガロア体演算部５は、複
数のレジスタ群１４、複数のマルチプレクサ群１５、ガ
ロア体任意元積和器１６、およびガロア体逆元器１７か
ら構成される。ガロア体演算部１３における演算は、
（ａ）シンドロ−ムを基にした誤り位置多項式・誤り数
値多項式の係数を導出することと、（ｂ）上記（ａ）で
求められた誤り数値多項式の係数と、チェンサ−チ演算
部から入力された誤り位置とを基に、誤り数値を導出す
ること、である。すなわち、ガロア体演算部１３は、レ
ジスタ群１４にシンドロ−ムとガロア体任意元積和器１
６の出力とガロア体逆元器１７の出力とを入力して、マ
ルチプレクサ群１５から制御信号ｃ３により選択して、
その中の１つをガロア体任意元積和器１６とガロア体逆
元器１７に出力させ、訂正のアルゴリズムに基づいて演
算を順次実行していく。この動作を、さらに詳細に説明
する。

【００１０】先ず、シンドロ−ム演算ブロックから入力
されたシンドロ−ムは、ガロア体演算部１３のレジスタ
群１４により保持される。マルチプレクサ群１５を構成
する複数のマルチプレクサは、それぞれレジスタ群１４
の複数の出力からガロア体任意元積和器１６およびガロ
ア体逆元器１７の入力を選択する。ガロア体任意元積和
器１６とガロア体逆元器１７は、入力に対してそれぞれ
ガロア体の積和とガロア体の逆元を求める。ガロア体任
意元積和器１６は（Ｘ・Ｙ＋Ｚ）で表わせるような演算
を行う。ここで、Ｘ，Ｙ，Ｚはそれぞれガロア体の元α
の任意のべき乗、例えばＸはαのｉ乗、Ｙはαのｊ乗、
Ｚはαのｋ乗であり、‘・’，‘＋’はガロア体の乗算
および加算を示す。ガロア体逆元器１７はガロア体の元
αのｉ乗の逆元を求める。ガロア体任意元積和器１６お
よびガロア体逆元器１７の各出力は、それぞれその値が
演算に必要とされる期間だけレジスタ群１４に保持され
る。制御信号ｃ１，ｃ２は、レジスタ群１４とマルチプ
レクサ群１５の動作を訂正のアルゴリズムに基づいて前
述のように制御する機能とともに、ガロア体演算部１３
の動作を休止させる機能をも有している。この休止機能
としては、例えばレジスタ群１４を構成する複数のレジ
スタをホ−ルド状態にするとともに、マルチプレクサ群
１５を構成する複数のマルチプレクサに入力される入力
信号、制御信号を固定する。

【００１１】図６は、図５におけるレジスタ群の構成を
示す図であり、図７は、図６のＤＦＦの動作タイムチャ
−トである。レジスタをホ−ルド状態にする方法として
は、例えば図６に示すように、レジスタ１８に入力され
るクロックを止める方法がある。レジスタとしては、ク
ロックの立上りのエッジでデ−タをラッチするデ−タフ
リップフロップ（ＤＦＦ）１８を用いることができる。
ＤＦＦ１８は、クロック端子に立上りのエッジが入力さ
れない限り、出力が変化せず、ホ−ルド状態となる。そ
こで、ＤＦＦ１８をホ−ルド状態にするために、制御信
号ｃを用いてクロック端子に入力される信号ｓ１を制御
することにより、ｓ１の立上りエッジが生成されないよ
うにする。具体的には、クロックと制御信号ｃをＯＲゲ
−ト１９に入力し、ＯＲゲ−ト１９の出力をｓ１とす
る。クロックと制御信号とｓ１の関係は、図７により明
らかとなる。制御信号ｃが‘Ｈ’の期間にはｓ１は常に
‘Ｈ’であって状態は変化しない。制御信号ｃが‘Ｌ’
の期間には、クロックの立上りエッジがｓ１に現われ
る。従って、制御信号ｃを‘Ｈ’にすることにより、Ｄ
ＦＦ１８をホ−ルド状態にすることができる。

【００１２】なお、図５では、ガロア体任意元積和器１
６およびガロア体逆元器１７がそれぞれ１個ずつの場合
を示しているが、ガロア体任意元積和器１６とガロア体
逆元器１７の個数を複数にすることも勿論可能である。
この場合には、ガロア体演算部１３で実行すべき演算
を、複数のガロア体任意元積和器１６と複数のガロア体
逆元器１７を並列に実行させる。そのために、ガロア体
任意元積和器１６とガロア体逆元器１７をそれぞれ１個
だけ設置する場合に比べて、少ない演算ステップ数で必
要な演算を実行することができる。また、ガロア体任意
元積和器１６のみで構成して、ガロア体逆元器１７を取
り除くことも可能である。例えば、ガロアフィ−ルドＧ
Ｆ（２⁸）上において、ガロア体の元αのｉ乗の逆元を
αのｊ乗としたとき、ｊ＝２５５−ｉの関係がある。こ
の関係を用いれば、逆元をガロア体任意元積和器１６を
用いて求めることができる。例えば、α¹⁰⁰の逆元はα
¹⁵⁵であるから、ガロア体任意元積和器１６によりα¹⁵⁵
を生成すればよい。

【００１３】図８は、図５におけるガロア体演算部にお
けるガロア体任意元積和器１６とその入力を選択するマ
ルチプレクサ群の構成を示す図である。このガロア体任
意元積和器２５は、ガロア体の元Ｘ，Ｙ，Ｚを入力とし
てガロア体の積和演算を実行し、Ｓ＝（Ｘ・Ｙ＋Ｚ）を
出力するものである。ここで、‘・’，‘＋’はそれぞ
れガロア体の乗算と加算を表わすものである。各入力を
選択するマルチプレクサ２２，２３，２４は、それぞれ
制御部から出力される制御信号ｃ３，ｃ４，ｃ５により
制御される。これらのマルチプレクサ２２，２３，２４
の入力は、レジスタ群２０の複数の出力と予め設定され
ている定数である。ここでは、Ｙ入力を選択するマルチ
プレクサ２３の選択可能な入力の１つとして、ガロア体
の単位元α⁰（つまり、１）を備え、またＺ入力を選択
するマルチプレクサ２４の選択可能な入力の１つとし
て、‘０’を備える。これにより、ガロア体任意元積和
器２５をガロア体任意元乗算器として用いる場合、つま
り加算の項がない場合には、マルチプレクサ２４におい
て‘０’（固定）を選択することにより、Ｚ入力を
‘０’にすることができ、Ｓ＝（Ｘ・Ｙ＋０）＝Ｘ・Ｙ
を得ることができる。

【００１４】また、ガロア体任意元積和器２５をガロア
体任意元加算器として用いる場合、つまり乗算の項がな
い場合には、マルチプレクサ２３においてα⁰を選択す
ることにより、Ｓ＝（Ｘ・α⁰＋Ｚ）＝（Ｘ＋Ｚ）を得
ることができる。マルチプレクサ２３の代りに、Ｘ入力
のマルチプレクサ２２の入力の１つとしてα⁰を備える
ことも可能である。通常、ガロア体の乗算器と加算器を
別個に設ける場合には、ガロア体の積和演算に２オペレ
−ションを要する。本実施例のように、ガロア体任意元
乗算とガロア体任意元加算とを連続して行うガロア体任
意元積和器を設けると、これらの積和の演算を１オペレ
−ションで行うことができる。さらに、制御信号により
ガロア体任意元積和器をガロア体任意元乗算器として、
またはガロア体任意元加算器として用いることも勿論可
能であり、動作的に極めて有効である。

【００１５】図９は、図１におけるチェンサ−チ演算部
の詳細構成図である。本実施例のチェンサ−チ演算部２
６は、ガロア体固定係数演算器２７と、零検出部２９
と、ガロア体カウンタ２８と、このガロア体カウンタ２
８の出力を保持するレジスタ３０とから構成される。ガ
ロア体固定係数演算器２７は、ガロア体演算部が生成し
た誤り位置多項式の係数を基にしてチェンサ−チと呼ば
れる演算を実行する。誤ったシンボル数がｔのときに
は、誤り位置多項式の次数はｔに等しく、例えばｔ＝４
のとき、誤り位置多項式σ（ｘ）は次式（１）で表わさ
れる。 σ（Ｘ）＝σ₄ｘ⁴＋σ₃ｘ³＋σ₂ｘ²＋σ₁ｘ＋σ₀ ・・・・・・・・・（１）ここで、σ₀，σ₁，σ₂，σ₃，σ₄は誤り位置多項式の
係数である。チェンサ−チ演算では、上式（１）のｘに
ガロア体の元を代入した値を求めて、式の値が零になる
ようなガロア体の元の逆元を誤り位置とする。ガロア体
の単位元からべき数が小さくなる順序で代入するものと
した場合には、上記係数をそれぞれσ₄＝Ａ₀，σ₃＝
Ｂ₀，σ₂＝Ｃ₀，σ₁＝Ｄ₀，σ₀＝Ｅ₀と置き換えると、
次式（２）に変換される。 σ（α⁰）＝Ａ₀＋Ｂ₀＋Ｃ₀＋Ｄ₀＋Ｅ₀ ・・・・・・・・・・・・・・（２）また、ｘにαの−１乗を代入した場合には、次式（３）
のように変換される。 σ（α^-1）＝Ａ₀α^-4＋Ｂ₀α^-3＋Ｃ₀α^-2＋Ｄ₀α^-1＋Ｅ₀ ・・・・・（３）ここで、Ａ₁＝Ａ₀×（αの−４乗）、Ｂ₁＝Ｂ₀×（αの
−３乗）、Ｃ₁＝Ｃ₀×（αの−２乗）、Ｄ₁＝Ｄ₀×（α
の−１乗）と、それぞれ置き換えると、次式（４）のよ
うに書き換えることができる。 σ（α^-2）＝Ａ₁α^-4＋Ｂ₁α^-3＋Ｃ₁α^-2＋Ｄ₁α^-1＋Ｅ₀ ・・・・・（４）すなわち、上式（３）の第１項は、Ａ₀（αの−２乗）⁴
＝Ａ₀（αの−４乗）²＝Ａ₁（αの−４乗）となるた
め、その他の項も同じような計算により上式（４）に書
き換えられることになる。

【００１６】前述のように、図９に示すチェンサ−チ演
算部２６のガロア体固定係数演算部２７は、定数項以外
の４項について、項毎に固定係数乗算（αの−４乗、α
の−３乗、αの−２乗、αの−１乗をｘ⁴，ｘ³，ｘ²，
ｘにそれぞれ乗算する）を順次行い、それら４項と定数
項の計５項に対してガロア体の加算を実行することによ
り、誤り位置多項式にガロア体の元を代入した値を求め
ることができる。このとき、ガロア体固定係数演算部２
７は、演算器として４個の固定係数乗算器と、固定係数
乗算器の出力と定数項を加算するガロア体の加算回路を
備える。ｔ次の誤り位置多項式について、チェンサ−チ
をｍ並列で行う場合には、ｔ個の固定係数乗算器と加算
回路の組み合わせをｍ並列分備えることにより構成され
る。零検出部２９は、上記ガロア体固定係数演算部２７
の出力が零であるか否かを判定し、零である場合には、
ガロア体カウンタ２８の値を保持するようにレジスタ３
０を制御する。ガロア体カウンタ２８は、ガロア体固定
係数演算部２７の演算に対応したガロア体の元を出力す
る。すなわち、ガロア体固定係数演算部２７が乗算する
元の位置を順次指示する。通常ガロア体カウンタ２８の
出力は、誤り位置多項式に代入される元あるいはその逆
元である。レジスタ３０は、零検出部２９の制御により
ガロア体カウンタ２８の値を誤り位置を示す値として保
持する。

【００１７】図１０は、図９におけるガロア体固定係数
演算部の詳細ブロック図である。図１０では、パリティ
シンボル数２ｔの場合のガロア体固定係数演算部３１が
示されており、ｔ個の演算ユニット３２と１個のガロア
体加算器３７とから構成されている。各演算ユニット３
２は、誤り位置多項式の係数とガロア体固定係数乗算器
３５の出力のいずれか一方を選択するマルチプレクサ３
３と、マルチプレクサ３３の出力をラッチするレジスタ
３４と、レジスタ３４の出力にガロア体の固定元を乗ず
るガロア体固定係数乗算器３５から構成されている。ガ
ロア体加算器３７は、ｔ個の演算ユニット３２の出力と
誤り位置多項式の定数項についてガロア体の加算を行
う。チェンサ−チをｍ並列で実行する場合には、ｔ個の
演算ユニット３２とガロア体加算器３７の組み合わせを
ｍ個具備する。各演算ユニット３２内のマルチプレクサ
３３およびレジスタ３４は、制御部より出力される制御
信号ｃ６，ｃ７により制御される。制御信号ｃ６、ｃ７
は、ガロア体固定係数演算部３１の動作を休止させる役
割も果す。動作を休止させるためには、レジスタ３４を
ホ−ルド状態にすること、あるいはマルチプレクサ３３
に入力される信号を固定にすることにより、実現可能で
ある。さらに、マルチプレクサ３３がクリア機能を備え
ている場合には、それによりマルチプレクサ３３の出力
が休止期間において零であるように制御する。

【００１８】図１１は、図９におけるガロア体カウンタ
の詳細ブロック図である。ガロア体カウンタ３８は、ガ
ロア体カウンタ３８の初期値とガロア体固定係数乗算器
４１の出力のいずれか一方を選択するマルチプレクサ３
９と、マルチプレクサ３９の出力をラッチするレジスタ
４０と、レジスタ４０の出力にガロア体の固定元を乗ず
るガロア体固定係数乗算器４１とから構成される。通
常、マルチプレクサ３９に入力される初期値は、誤り訂
正装置に入力される符号語の長さをＮシンボルとした場
合に、ガロア体の元であるαの（Ｎ−１）乗の値で外部
から与えられる。チェンサ−チをｍ並列で行う場合に
は、ガロア体カウンタ３８はｍ個の出力を設けて、それ
ぞれｍ並列のチェンサ−チで代入する元またはその逆元
を出力するように構成する。マルチプレクサ３９および
レジスタ４０は、制御部から出力される制御信号ｃ８，
ｃ９によりチェンサ−チ期間においてのみ動作するよう
に制御される。例えば、チェンサ−チ期間以外の期間に
おいて、レジスタ４０をホ−ルド状態にすること、また
はマルチプレクサ３９に入力される信号を固定にするこ
とにより実現できる。さらに、マルチプレクサ３９にク
リア機能がある場合には、それによりマルチプレクサ３
９の出力が休止期間で零であるように制御する。また、
チェンサ−チ期間において、マルチプレクサ３９はチェ
ンサ−チ開始１ステップ目では初期値を選択し、それ以
外ではガロア体固定係数乗算器４１の出力を選択するよ
うに制御される。

【００１９】図１２は、本発明の他の実施例を示す誤り
訂正装置の構成図である。図１２の実施例では、図１に
比べると、イレ−ジャフラグを入力する誤り位置導出ブ
ロック４６のみが余分に設置されており、それ以外は図
１と同じ構成である。本実施例の誤り訂正装置では、入
力される符号語の情報のみをもとに訂正処理を行う訂正
方式（１）と、入力される符号語および符号語に付加さ
れたイレ−ジャフラグの情報をもとに訂正処理を行う訂
正方式（２）の両訂正方式のいずれか一方を選択して実
行することが可能である。訂正方式（１），（２）のう
ちの一方を選択する処理は、選択信号ｃ１０により行わ
れる。選択信号ｃ１０は、誤り位置導出ブロック４６、
誤り位置・数値導出ブロック４３、および訂正ブロック
４４の動作を制御するために用いられる。訂正方式
（１）が選択された場合には、誤り位置・数値導出ブロ
ック４３は、シンドロ−ム演算ブロック４２で求められ
たシンドロ−ムを基に誤り位置・誤り数値を求める演算
を行う。また、訂正ブロック４４は、誤り位置・数値導
出ブロック４３で求められた誤り位置・誤り数値を基に
訂正を行う。また、このとき誤り位置導出ブロック４６
は演算の必要がないために、演算を休止するように制御
される。

【００２０】図１２の誤り訂正装置で、訂正方式（２）
が選択された場合には、シンドロ−ム演算ブロック４２
で求められたシンドロ−ムと誤り位置導出ブロック４６
で求められた誤り位置を基に、誤り位置・数値導出ブロ
ック４３において、誤り数値を求める演算を行う。ま
た、訂正ブロック４４は、誤り位置導出ブロック４６で
求められた誤り位置と誤り位置・数値導出ブロック４３
で求められた誤り数値を基に訂正を行う。また、訂正ブ
ロック４４は、誤り位置導出ブロック４６で求められた
誤り位置と誤り位置・数値導出ブロック４３で求められ
た誤り数値を基に訂正を行う。ただし、本実施例では、
誤り位置導出ブロック４６で求められた誤り位置を、誤
り位置・誤り数値導出ブロック４３を通して訂正ブロッ
ク４４に入力しているが、誤り位置を誤り位置導出ブロ
ック４６から直接訂正ブロック４４に入力するように構
成することも可能である。

【００２１】図１３は、図１２における誤り位置導出ブ
ロックの構成図である。本実施例における誤り位置導出
ブロック４７は、入力されるイレ−ジャフラグに対応し
たガロア体の元を生成するガロア体カウンタ４８と、ガ
ロア体カウンタ４８の出力をイレ−ジャフラグの制御に
よりラッチするレジスタ５２と、選択信号ｃ１０から制
御信号ｃ１１，ｃ１２を生成する制御信号生成部５３と
から構成されている。さらに、ガロア体カウンタ４８
は、初期値とガロア体固定係数乗算器５１の出力のいず
れか一方を選択するマルチプレクサ４９と、マルチプレ
クサ４９の出力をラッチするレジスタ５０と、レジスタ
５０の出力にガロア体の固定元を乗ずるガロア体固定係
数乗算器５１とから構成される。なお、通常、マルチプ
レクサ４９の入力である初期値としては、符号語長をＮ
シンボルとしたときに、αの（Ｎ−１）乗の値で与えら
れる。また、ガロア体固定係数乗算器５１としては、通
常αの（−１）乗器、つまりαの２５４乗器が用いられ
る。また、選択信号ｃ１０によりイレ−ジャフラグを用
いない訂正方式（１）が選択された場合には、次のよう
にガロア体カウンタ４８を休止させる。すなわち、制御
信号ｃ１１によりマルチプレクサ４９の選択信号を固定
にして、クリア機能を具備している場合には、出力を零
にするように制御する。また、制御信号ｃ１２により、
レジスタ５０をホ−ルド状態にするように制御する。

【００２２】

【発明の効果】以上説明したように、本発明によれば、
誤り訂正装置の誤り位置・誤り数値導出手段として、ガ
ロア体演算部およびチェンサ−チ演算部とこれらを制御
する制御部で構成し、制御部にガロア体演算部およびチ
ェンサ−チ演算部の動作をそれぞれ独立に休止させる機
能を持たせたので、動作不要な演算部を休止させること
ができ、その結果、消費電力を低減させることができ
る。特に、チェンサ−チ期間は回路規模の大きなガロア
体演算部を休止させるため、消費電力を低減させる効果
は大である。また、パリティシンボル数が一定のときに
は、符号語の長さ（シンボル数）が長いほど、誤り位置
・誤り数値導出処理の全演算時間に対するチェンサ−チ
演算時間の割合は大きいため、消費電力の低減の効果は
大きい。さらに、トランジスタのＯＮ／ＯＦＦの変化に
より電力を消費するＣＭＯＳトランジスタで誤り訂正装
置を集積した場合には、特に効果が大きい。

【００２３】

【図面の簡単な説明】

【図１】本発明の一実施例を示す誤り訂正装置のブロッ
ク構成図である。

【図２】従来の誤り訂正装置のブロック構成図である。

【図３】図１における誤り訂正装置の処理の伝搬を示す
図である。

【図４】図１における誤り位置・数値導出ブロックの各
部の演算時間を示す図である。

【図５】図１におけるガロア体演算部の詳細構成を示す
ブロック図である。

【図６】図５におけるレジスタ群の構成図である。

【図７】図６におけるレジスタの動作タイムチャ−トで
ある。

【図８】図５におけるガロア体任意元積和器およびマル
チプレクサ群の構成を示すブロック図である。

【図９】図１のチェンサ−チ演算部の構成を示すブロッ
ク図である。

【図１０】図９におけるガロア体固定係数演算部の詳細
構成図である。

【図１１】図９におけるガロア体カウンタの詳細構成図
である。

【図１２】本発明の他の実施例を示す誤り訂正装置のブ
ロック構成図である。

【図１３】図１２における誤り位置演算ブロックの詳細
構成図である。

【符号の説明】

１，８，４２シンドロ−ム演算ブロック２，９，４３誤り位置・誤り数値導出ブロック３，１０，４４訂正ブロック４，１１，４５遅延ブロック５，１３ガロア体演算部６，２６チェンサ−チ演算部７制御部１４，２０レジスタ群１５，２１マルチプレクサ群１６，２５ガロア体任意元積和器１７ガロア体逆元器１８デ−タフリップフロップ（ＤＦＦ）１９ＯＲゲ−ト２２，２３，２４，３３，３９，４９マルチプレクサ２７，３１ガロア体固定係数演算部２８，３８，４８ガロア体カウンタ２９零検出部３０，３４，４０，５０，５２レジスタ３２演算ユニット３５，４１，５１ガロア体固定係数乗算器４６，４７誤り位置導出ブロック５３制御信号生成部ｓ１ＯＲゲ−ト出力ｃ２〜ｃ９，ｃ１１，ｃ１２制御信号ｃ１２０選択信号

Claims

【特許請求の範囲】

【請求項１】入力された誤り訂正符号を基にシンドロ
−ムを算出する第１の演算手段と、該第１の演算手段の
出力を基に誤り位置と誤り数値を求める第２の演算手段
と、該第２の演算手段の出力を基に上記誤り訂正符号の
訂正を行う訂正手段とを備え、上記第１の演算手段と第
２の演算手段と訂正手段とでパイプライン動作を行わせ
る誤り訂正装置において、上記第２の演算手段は、少な
くとも、シンドロ−ムを基に誤り位置多項式および誤り
数値多項式の係数を求め、かつ誤り数値多項式の係数と
誤り位置から誤り数値を求めるガロア体演算部と、該ガ
ロア体演算部から受け取った誤り位置多項式の係数を基
にチェンサ−チを実行し、誤り位置を求めるチェンサ−
チ演算部と、上記ガロア体演算部およびチェンサ−チ演
算部に対してそれぞれ演算を行わない期間に動作を休止
させるように制御する制御部とで構成することを特徴と
する誤り訂正装置。
【請求項２】請求項１に記載の誤り訂正装置におい
て、上記ガロア体演算部は、少なくともガロア体任意元
の積和を求める積和手段と、該積和手段の出力を保持す
る複数のレジスタと、該積和手段の入力を選択する複数
のマルチプレクサとから構成され、また上記チェンサ−
チ演算部は、少なくとも、誤り位置多項式の係数を基に
ガロア体固定係数乗算を行う演算手段と、誤り位置多項
式に代入する元またはその逆元を生成するガロア体カウ
ンタと、該演算手段の出力の零を検出する零検出手段
と、該零検出手段の制御により上記ガロア体カウンタの
出力を保持するレジスタとから構成されることを特徴と
する誤り訂正装置。
【請求項３】請求項１に記載の誤り訂正装置におい
て、上記ガロア体演算部は、ガロア体任意元の積和を求
める積和手段と、ガロア体の逆元を求める逆元手段と、
該積和手段および逆元手段の出力を保持する複数のレジ
スタと、該積和手段および逆元手段の入力を選択する複
数のマルチプレクサとを具備し、また上記チェンサ−チ
演算部は、少なくとも、誤り位置多項式の係数を基にガ
ロア体固定係数乗算を行う演算手段と、誤り位置多項式
に代入する元またはその逆元を生成するガロア体カウン
タと、該演算手段の出力の零を検出する零検出手段と、
該零検出手段の制御により上記ガロア体カウンタの出力
を保持するレジスタとから構成されることを特徴とする
誤り訂正装置。
【請求項４】請求項２または３に記載の誤り訂正装置
において、上記積和手段は、ガロア体積和機能と、ガロ
ア体任意元の乗算機能およびガロア体任意元の加算機能
の２つの機能のうちの少なくとも１つの機能を有し、制
御信号により複数の上記機能が切り替えられるように構
成されることを特徴とする誤り訂正装置。
【請求項５】請求項１，２または３に記載の誤り訂正
装置において、上記チェンサ−チ演算部は、ガロア体固
定係数の乗算を行う演算手段を有し、該演算手段には、
少なくとも誤り位置多項式の係数とガロア体固定係数乗
算器の出力とを選択するマルチプレクサと、該マルチプ
レクサの出力をラッチするレジスタと、該レジスタの出
力にガロア体の固定元を乗ずるガロア体固定係数乗算器
とからなる複数個の演算ユニットと、該演算ユニットの
複数の出力および誤り位置多項式の定数項のガロア体加
算を行う加算手段とを設けたことを特徴とする誤り訂正
装置。
【請求項６】請求項１，２または３に記載の誤り訂正
装置において、上記チェンサ−チ演算部は、誤り位置多
項式に代入する元またはその逆元を生成するガロア体カ
ウンタを有し、該ガロア体カウンタには、少なくとも該
ガロア体カウンタの初期値とガロア体固定係数乗算器の
出力とを選択するマルチプレクサと、該マルチプレクサ
の出力をラッチするレジスタと、該レジスタの出力にガ
ロア体の固定元を乗ずるガロア体固定係数乗算器とを設
けたことを特徴とする誤り訂正装置。
【請求項７】請求項１に記載の誤り訂正装置におい
て、上記第１の演算手段，第２の演算手段および訂正手
段の他に、入力されたイレ−ジャフラグを基に誤り位置
を求める第３の演算手段を具備し、上記第２の演算手段
は、上記第１の演算手段の出力を基に誤り位置と誤り数
値を求めるか、あるいは上記第１の演算手段の出力と上
記第３の演算手段の出力を基に誤り数値を求め、また上
記訂正手段は、上記第２の演算手段の出力を基に誤り訂
正符号の訂正を行うか、あるいは上記第３の演算手段で
求められた誤り位置と上記第２の演算手段で求められた
誤り数値を基に訂正を行い、また上記第２の演算手段お
よび訂正手段は、外部からの選択信号によりそれぞれの
動作を切り換えることにより、符号語のみから訂正処理
を行う第１の訂正方式と、符号語およびイレ−ジャフラ
グから訂正処理を行う第２の訂正方式のいずれか一方を
実行して、上記第１の訂正方式を選択した場合には、上
記第３の演算手段の動作を休止させることを特徴とする
誤り訂正装置。
【請求項８】請求項７に記載の誤り訂正装置におい
て、上記第２の演算手段は、少なくとも連続したガロア
体の元を生成するガロア体カウンタと、イレ−ジャフラ
グの制御により該ガロア体カウンタの出力を保持するレ
ジスタと、選択信号を基に該ガロア体カウンタを制御す
る制御信号を生成する信号生成手段とを備え、上記第１
の訂正方式を選択した場合には、該ガロア体カウンタの
動作を休止させることを特徴とする誤り訂正装置。
【請求項９】シンドロ−ムを基に誤り位置と誤り数値
を求めて、求められた誤り位置と誤り数値を基に誤り訂
正符号を訂正して出力する誤り訂正方法において、ガロ
ア体の固定係数乗算を行うガロア体演算部と、ガロア体
の固定係数乗算を行うチェンサ−チ演算部は、パイプラ
イン動作１，２，３の順序で処理を実行し、先ず動作
（１）では、上記ガロア体演算部でシンドロ−ムを基に
誤り位置多項式・誤り数値多項式の係数を求める一方、
上記チェンサ−チ演算部では動作を休止し、次に動作
（２）では、求められた上記誤り位置多項式の係数を基
にチェンサ−チを実行して、誤り位置を導出する一方、
上記ガロア体演算部では動作を休止し、次に動作（３）
では、求められた上記誤り位置と既に求められている誤
り数値多項式の係数を基に誤り数値を求める一方、上記
チェンサ−チ演算部では動作を休止することを特徴とす
る誤り訂正方法。
【請求項１０】請求項９に記載の誤り訂正方法におい
て、上記ガロア体演算部の動作を休止させるときには、
演算が不要な期間に、該ガロア体演算部を構成する複数
のマルチプレクサの入力信号および制御信号を固定にす
るか、あるいは該ガロア体演算部を構成する複数のレジ
スタを入力デ−タのラッチを行わないホ−ルド状態に
し、また上記チェンサ−チ演算部の動作を休止させると
きには、演算が不要な期間に、該チェンサ−チ演算部を
構成するレジスタを入力デ−タのラッチを行わないホ−
ルド状態にするか、あるいは該チェンサ−チ演算部を構
成するマルチプレクサの入力信号および制御信号を固定
にすることを特徴とする誤り訂正方法。