(57)【特許請求の範囲】
【請求項１】
入力データ系列と類似度の高い標準データ系列を、ツリー状のデータ構造をとる複数の標準データ系列の中から探索するデータ探索装置であって、
前記複数の標準データ系列を予め記憶する記憶手段と、
該記憶手段に記憶された標準データ系列の部分系列を特定するポインタを生成するポインタ生成手段と、
外部からの入力データ系列に対し前記ポインタで特定される標準データ系列の部分系列の枝尤度を異なった定義式を用いて夫々出力する複数個の枝尤度生成手段と、
該複数個の枝尤度生成手段の夫々から出力する枝尤度を受け、前記入力データ系列に対し夫々異なった定義式を用いて前記ポインタで特定される標準データ系列の部分系列の尤度を生成して出力する複数個の尤度生成手段とを有し、
該複数個の尤度生成手段の出力である複数の尤度を夫々の尤度に対応した複数の閾値と夫々比較し、比較結果に基づいて前記夫々の尤度に対応させた複数の閾値を夫々増減或いは不変として前記ポインタをツリー状のデータ構造の枝上を前進或いは後進させ、ポインタを同一の枝上を再度前進させる場合には、再度のポインタ前進の際の閾値の組は前回のポインタ前進の際の閾値の組と異なるようにする処理動作を有し、前記複数の尤度が大きくなるようにポインタを制御することを特徴とするデータ探索装置。
【請求項２】
前記複数個の尤度生成手段のうちの一つが出力する尤度が、標準データ系列の出現確率の対数から定数を引いた値に比例することを特徴とする請求項１記載のデータ探索装置。
【請求項３】
前記ポインタ生成の制御はファノ・アルゴリズムに基づいて制御を行なう請求項１記載のデータ探索装置。
【請求項４】
入力データ系列と類似度の高い標準データ系列を、ツリー状のデータ構造をとる複数の標準データ系列の中から探索するデータ探索用のコンピュータ・プログラムであって、コンピュータに
予め決められた複数の標準データ系列を記憶するステップと、
記憶された標準データ系列の部分系列を特定するポインタを生成するステップと、
外部から入力されたデータ系列に対し前記ポインタで特定される標準データ系列の部分系列の枝尤度を異なった定義式を用いて複数個出力するステップと、
前記複数個の枝尤度に基づいて前記入力されたデータ系列に対し夫々異なった定義式を用いて前記ポインタで特定される標準データ系列の部分系列の尤度を夫々複数個生成するステップとを実行させ、
該複数個の尤度を夫々の尤度に対応した複数の閾値と夫々比較し、比較結果に基づいて前記夫々の尤度に対応させた複数の閾値を夫々増減或いは不変として前記ポインタをツリー状のデータ構造の枝上を前進或いは後進させ、ポインタを同一の枝上を再度前進させる場合には、再度のポインタ前進の際の閾値の組は前回のポインタ前進の際の閾値の組と異なるようにする処理動作を実行させ、前記複数の尤度が大きくなるようにポインタの制御を実行させることを特徴とするデータ探索用のコンピュータ・プログラム。
【請求項５】
前記複数個の尤度のうちの一つは、標準データ系列の出現確率の対数から定数を引いた値に比例する請求項４記載のデータ探索用のコンピュータ・プログラム。
【請求項６】
前記ポインタ生成の制御はファノ・アルゴリズムに基づいて行なわれる請求項４記載のデータ探索用のコンピュータ・プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、入力データ系列と類似度の高い標準データ系列を、予め与えられている複数の標準データ系列の中から探索して、探索された標準データ系列又は探索された標準データ系列に対応するコードを出力する、データ探索方法及び装置に関する。
【０００２】
【従来の技術】
従来技術について述べる前に、説明の便宜上いくつかの定義をしておく。
【０００３】
以下では混乱のない限り情報のことをデータ系列と呼ぶ。例えば２値画像情報は０あるいは１の値を取るシンボルの系列すなわちデータの系列に変換できるように、工学の分野で取り扱う情報はなんらかのデータ系列として表現できる。また、データ系列をｘ＝（ｘ１，ｘ２，．．．，ｘＮ（ｘ））で表現する。ここでＮ（ｘ）はデータ系列ｘの長さで、ｘ１，ｘ２，．．．，ｘＮ（ｘ）は夫々データ系列を構成するシンボルを表す。尚、各シンボルは、１又は複数のビットからなる。
【０００４】
また、データ系列ｘの先頭のｊシンボルを取り出して得られる長さｊの系列のことを、長さｊの部分データ系列又は単に部分系列と呼び、ｘｊ＝（ｘ１，ｘ２，．．．，ｘｊ）で表す。部分系列ｘｊのｊ番目のシンボルｘｊは、部分系列ｘｊの末端と呼ばれる。尚、長さ０の部分系列ｘ０を空系列と呼ぶ。空系列は「ＮＵＬＬ」とも表記される。データ系列ｘの長さＮ（ｘ）の部分系列ｘＮ（ｘ）は、データ系列ｘに等しい。
【０００５】
また、データ系列ｙと部分系列ｘｊに対して定義される尤度と呼ばれる量をΓ（ｘｊ）と表記する。尚、尤度Γ（ｘｊ）は、データ系列ｙと部分系列ｘｊの両方に依存して値が決まるので、本来はΓｙ（ｘｊ）とでも書くべきだが、以下では説明の便宜上、単にΓ（ｘｊ）と表記する。
【０００６】
データ探索装置は、与えられたデータ系列ｙに対して、尤度Γ（ｘ）を大きくするようなデータ系列ｘを、予め与えられている複数のデータ系列の中から探索して、探索されたデータ系列又はそれに対応するコードを出力するものである。以下では予め与えられた複数のデータ系列の夫々を標準データ系列と呼ぶ。
【０００７】
それら複数の標準データ系列は、図１に示すように、一般に、ツリー状のデータ構造として記憶される。すなわち、夫々の標準データ系列（ｘ１，ｘ２，．．．，ｘＮ（ｘ））に対して、次のような操作を行って、ツリー状のデータ構造中を探索する。
【０００８】
まず、図１のツリーの最左端の分岐点にポインタを置く。もし、ポインタの置かれている分岐点から枝分かれしている枝で、シンボルｘ１の割り振られた枝が存在すれば、ポインタをその枝の右端（次の分岐点）に進め、さもなくば、シンボルｘ１の割り振られた新しい枝をその分岐点に付け足し、ポインタをその枝の右端に進める。以下同様に、このような操作を、シンボルｘ２，．．．，ｘＮ（ｘ）についても続けて行い、ポインタをツリーの右方向に進めて行く。
【０００９】
尚、ツリーの最左端の分岐点のことを幹と呼び、ツリーの最右端の分岐点のことをツリーの末端と呼ぶ。また、標準データ系列の部分系列ｘｊのことをツリーの幹から末端にいたるまでの通り道という意味でパスとも呼ぶ。また、データ探索装置が出力する標準データ系列のことを解と呼ぶ。解は、一般に、尤度が最大であるような標準データ系列である。尚、説明の便宜上、特に断りの無い限り、データ探索装置が装置内部に解の候補として記憶している標準データ系列あるいは標準データ系列の部分系列のことも夫々解あるいは解の部分系列と呼ぶ。
【００１０】
尚、標準データ系列は、論理的にはツリー状のデータ構造として記憶されるが、物理的にはルック・アップ・テーブルとしてメモリに記憶される。このため、標準データ系列の部分系列ｘｊは、そのメモリのアドレスとしても表現できる。以下では、そのアドレスのことを、標準データ系列の部分系列ｘｊを示すポインタと呼ぶ。
【００１１】
図２（ａ）に示すように、矢印で示される部分系列の末端に、枝ｂｌを付け加えて、実線矢印で示される部分系列を得ることを、その部分系列を示すポインタを前進させると言い、図２（ｂ）に示すように、点線矢印で示される部分系列の末端の枝ｂｌをｂｒに付け替えて、実線矢印で示される部分系列を得ることを、その部分系列を示すポインタを横進させると言い、図２（ｃ）に示すように、点線矢印で示される部分系列の末端の枝ｂｌを除去して、実線矢印で示される部分系列を得ることを、その部分系列を示すポインタを後進させると言う。
【００１２】
データ探索方法は、様々な分野で夫々独立に開発されてきたために、分野によって呼び方や分類は異なるが、どの分野のデータ探索方法も、与えられたデータ系列に対して、尤度が最大である（あるいは最大である可能性の高い）標準データ系列を、予め記憶された複数の標準データ系列の中から選び出し、その標準データ系列又はそれに対応する符号を出力する。
【００１３】
例えばパターン認識では、入力されたカメラ画像や音声などに対応するデータ系列が、予め記憶された標準パターンのどのパターンに近いかを捜し出し、そのパターンに対応する符号を認識結果として出力する。以下では従来のデータ探索方法のうち、本発明と関連のある逐次復号法について詳しく説明する。
【００１４】
逐次復号法にはファノ・アルゴリズムとスタック・アルゴリズムが知られている。
【００１５】
ファノ・アルゴリズムの原理については、例えば、米国電気電子工学会の情報理論に関する論文誌の第９巻の６４項から７４項に掲載された論文（Ｒｏｂｅｒｔ  Ｍ．  Ｆａｎｏ，  “Ａ  Ｈｅｕｒｉｓｔｉｃ  Ｄｉｓｃｕｓｓｉｏｎ  ｏｆ  Ｐｒｏｂａｂｉｌｉｓｔｉｃ  Ｄｅｃｏｄｉｎｇ”，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，  Ｖｏｌ．ＩＴ−９，  ｐｐ．６４−７４，  Ａｐｒｉｌ  １９６３）やガラガー著の書籍（Ｒｏｂｅｒｔ  Ｇａｌｌａｇｅｒ，  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ  ａｎｄ  Ｒｅｌｉａｂｌｅ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ，  Ｊｏｈｎ  Ｗｉｌｅｙ  ＆  Ｓｏｎｓ，  １９６８）に詳しい記述がある。
【００１６】
スタック・アルゴリズムの原理については、例えば、アイビーエム・ジャーナル・オブ・リサーチ・アンド・ディベロップメントの第１３巻６号の６７５項から６８５項に掲載された論文（Ｆ．Ｊｅｌｉｎｅｋ， “Ｆａｓｔ ＳｅｑｕｅｎｔｉａｌＤｅｃｏｄｉｎｇ Ａｌｇｏｒｉｔｈｍ Ｕｓｉｎｇ ａ Ｓｔａｃｋ，” ＩＢＭ Ｊ． Ｒｅｓ． Ｄｅｖｅｌｏｐ．， Ｖｏｌ．１３，Ｎｏ．６， ｐｐ．６７５−６８５， Ｎｏｖｅｍｂｅｒ １９６９）に詳しい記述がある。
【００１７】
それ以外にも幾つかの逐次復号法が知られているが、それらは、ファノ・アルゴリズムやスタック・アルゴリズムを変形したものであったり、あるいは両者を組み合わせたものである。
【００１８】
尚、逐次復号法という名称は、誤り訂正の分野で使われる用語である。人工知能や計算機理論の分野では、逐次復号法に相当するデータ探索法は、最良優先探索、バックトラック法、ヒューリスティック探索などと呼ばれている。
【００１９】
探索方法の歴史については例えばジャーナル・オブ・ジ・アソシエーション・フォー・コンピューティング・マシナリー誌の第１２巻４号の５１６項から５２４項に記載された論文（ＳｏｌｏｍｏｎＷ． Ｇｏｌｏｍｂ ａｎｄ Ｌｅｏｎａｒｄ Ｄ． Ｂａｕｍｅｒｔ， “ＢａｃｋｔｒａｃｋＰｒｏｇｒａｍｍｉｎｇ，” Ｊｏｕｒｎａｌ ｏｆ ｔｈｅ Ａｓｓｏｃｉａｔｉｏｎ ｆｏｒＣｏｍｐｕｔｉｎｇ Ｍａｃｈｉｎｅｒｙ， Ｖｏｌ．１２， Ｎｏ．４，ｐｐ．５１６−５２４，Ｏｃｔｏｂｅｒ １９６５）に詳しく述べられている。以下では、従来の逐次復号法のうち、ファノ・アルゴリズムについて、詳しく説明する。
【００２０】
まず、ファノ・アルゴリズムの基本原理を、誤り訂正の簡単な例を用いて説明しよう。
【００２１】
この例題で用いる符号化装置の基本構成を図３に示す。尚、以下では符号理論における慣例に従って符号化装置のことを符号器とも呼ぶ。尚、この例においては、情報シンボルが１ビットで表現されるので、情報ビットと呼ぶべきかもしれないが、説明の便宜上、情報シンボルと呼ぶことにする。
【００２２】
図３において、入力端子３９３に０が供給されている時に入力端子３９１にクロックパルスが１個供給されると、フリップフロップ３１１，３１２，３１３は、記憶している値を０に初期化する。一方、入力端子３９３に１が供給されている時に入力端子３９１にクロックパルスが１個供給されると、フリップフロップ３１１、３１２、３１３は、夫々入力端子３９２から供給される情報シンボル、フリップフロップ３１１の出力、フリップフロップ３１２の出力を保持して、保持した値を出力する。
【００２３】
入力端子３９２から供給される情報シンボルは、出力端子３９４１にも供給される。排他的論理和回路３２２は、入力端子３９２から供給される情報シンボル、フリップフロップ３１１の出力，フリップフロップ３１２の出力、フリップフロップ３１３の出力の合計４ビットの排他的論理和を計算する。排他的論理和回路３２３は、入力端子３９２から供給される情報シンボル、フリップフロップ３１２の出力、フリップフロップ３１３の出力の合計３ビットの排他的論理和を計算する。排他的論理和回路３２２と排他的論理和回路３２３の計算結果は、夫々出力端子３９４２と出力端子３９４３に供給される。そして、出力端子３９４１、３９４２、３９４３に出力される合計３ビットが、符号シンボルとして出力される。
【００２４】
このような符号器で情報シンボル系列ｕ１，ｕ２，...を符号化するには次のようにする。
【００２５】
まず、入力端子３９３に０を供給して、入力端子３９１にクロックパルスを１個供給し、フリップフロップ３１１，３１２，３１３の保持しているビットを、オールゼロに初期化する。
【００２６】
その後、入力端子３９３に１を供給し続ける。そして、入力端子３９２に、情報シンボルｕ１を供給する。すると、情報シンボルｕ１に対応する符号シンボルｘ１＝（ｘ１（１），ｘ１（２），ｘ１（３））が、出力端子３９４１，３９４２，３９４３に得られる。
【００２７】
その後、入力端子３９１にクロックパルスを１個供給した後に、入力端子３９２に情報シンボルｕ２を供給すると、出力端子３９４１，３９４２，３９４３に、情報シンボルｕ２に対応する符号シンボルｘ２＝（ｘ２（１），ｘ２（２），ｘ２（３））が得られる。以下、以上のような操作を繰り返して、情報シンボル系列ｕ３，ｕ４，...に対する符号化が同様に行われる。
【００２８】
ところで、最初に出力される符号シンボルｘ１＝（ｘ１（１），ｘ１（２），ｘ１（３））は、情報シンボルｕ１によって決まり、次に出力される符号シンボルｘ２＝（ｘ２（１），ｘ２（２），ｘ２（３））は、情報シンボルｕ１，ｕ２によって決まり、同様に、その後の符号シンボルｘｊ＝（ｘｊ（１），ｘｊ（２），ｘｊ（３））は、情報シンボルｕ１，ｕ２，…，ｕｊによって決まる。
【００２９】
情報シンボル系列と符号シンボル系列との間には、このような依存関係があるので、符号シンボル系列の集合は、図４のようなツリー構造で記述できる。図４の左端の枝に書かれている２つの符号シンボル（夫々３ビットからなる）は、夫々、符号器に情報シンボル系列の最初の情報シンボルとして１あるいは０が入力された時の、符号器の出力である。図において、最初の情報シンボル１に対応する符号シンボル１１１の添えられた枝から、右方向に枝分かれしている２本の枝は、夫々、最初の１に続いて情報シンボル１あるいは０が入力された時の、符号器の出力に対応している。以下同様にして、情報シンボルと符号シンボルとの対応が記述されており、例えば、ｕ１＝１，ｕ２＝１，ｕ３＝０，ｕ４＝０に対応する符号シンボル系列は、図４の太線で示される。
【００３０】
尚、この例における「符号シンボル系列」と「情報シンボル系列」と「受信信号系列」は、一般的なデータ探索においては、夫々、「標準データ系列」と「標準データ系列に対応する符号」と「データ系列」に対応している。そして、符号理論の分野におけるデータ探索とは、符号シンボル系列を通信路に通して得られる受信信号系列から元の符号シンボル系列（あるいは其れに対応する情報シンボル系列）を復元することである。
【００３１】
このようなツリー構造（情報シンボル系列と符号シンボル系列との依存関係）は、次のようにして、データ探索に利用できる。尚、以下では、符号理論における慣例に従ってデータ探索のことを復号化とも呼ぶ。
【００３２】
まず、例えば、図３の符号器の出力する符号系列１１１ １０１ ００１ ０００が、２元対称通信路を通して送信され、受信信号系列１０１ １０１ ００１ ０００が得られたとしよう（注：３ビットの小ブロックは、夫々３ビットの符号シンボルに対応する受信信号であり、最初の小ブロックの２番目のビットが誤って受信されている）。
【００３３】
すると、図４から、送信された符号シンボル系列の最初の符号シンボルは、０００あるいは１１１であることがわかる。従って、ハミング距離の近い１１１が送信されたと仮定できる。また、この仮定が正しければ、次に送信された符号シンボルは、１０１であると仮定できる。同様にして、後続の符号シンボルは、００１ ０００と仮定できる。すなわち、符号シンボル系列１１１  １０１  ００１  ０００が送信されたと仮定できる。このように逐次的に仮定をしてゆけば、夫々の仮定において検証すべき符号シンボルの数を僅か２つにできる。
【００３４】
次に、上述の場合と同様に、符号系列１１１ １０１ ００１ ０００が送信されて、受信信号系列０１０ １０１ ００１ ０００が得られたとしよう（前述の例よりもエラーの個数が多い）。この場合、最初に送信された符号シンボルは、ハミング距離の小さい０００であると仮定できる。また、この仮定が正しければ、後続の符号シンボルは、１１１ １０１ ００１と仮定できる。すなわち、符号シンボル系列０００ １１１ １０１ ００１が送信されたと仮定できる。
【００３５】
しかし、この場合、送信されたと仮定された符号シンボル系列と受信信号系列は、合計で４ビットも食い違っている。このことは、一旦誤った仮定が成されると、後続の符号シンボルと受信信号とが無相関になってしまうということを示している。
【００３６】
復号器は、受信信号系列と復号した符号シンボル系列を比較した結果、復号した符号シンボル系列に誤ったビットが多いことがわかると、最初の仮定が間違っていると認識する。そして、最初の仮定が間違っていると認識すると、ツリーを後戻りして、最初の仮定と別の仮定を試して、今度は、正しく復号する必要がある。このように、逐次的な仮定は、可能な選択肢を減らすことによって、後において成される仮定を単純化するだけでなく、初期の仮定の確からしさに関する情報も与えてくれる。
【００３７】
ファノ・アルゴリズムは、ツリー構造で表現できる符号の復号化方法であり、以上の例で示したように、ツリーの枝ごとに、どちらの枝が正しい符号シンボルに対応しているのか仮定するとともに、後続の仮定の確からしさの低さが初期の仮定の誤りを示している場合には初期の仮定を変更する、ということを繰り返して、復号化を行うものである。
【００３８】
もっとも、実際のファノ・アルゴリズムは、もう少し複雑である。図５は、ファノ・アルゴリズムの動作規則を示す表の一例である（前記ガラガーの書籍に記載されているものである）。どのような条件が成立する時に新しい仮定を行うのかとか、どのような条件が成立する時に後戻りして古い仮定を変更するのか、という具体的な規則を記述すると、図５のように、やや複雑なものになる。
【００３９】
尚、図において、Ｔは、閾値と呼ばれる変数である。Γは、
Γ（ｘｊ）＝−ｌｏｇ｛ｐ（ｙ）／ｐ（ｙ｜ｘｊ）｝−Ｂ（ｘｊ−１）
で定義される尤度（ファノ尤度と呼ばれる）である。ここで、ｐ（ｙ）はデータ系列ｙが出現する確率、ｐ（ｙ｜ｘｊ）は標準データ系列の長さｊの部分系列ｘｊが出現したという条件下でデータ系列ｙが出現する確率、ｐ（ｘｊ）は標準データ系列の長さｊの部分系列ｘｊが出現する確率である。また、Ｂ（ｘｊ−１）は標準データ系列の長さｊの部分系列ｘｊに対するバイアス値であり、ｘｊが正しい解の部分系列であればΓ（ｘｊ）の期待値が正となり、ｘｊが正しい解の部分系列で無ければΓ（ｘｊ）の期待値が負となるような値が選ばれる。
【００４０】
また、図において、「Ｉ」は、閾値を増加（Ｉ）させること、すなわち、Γ（ｘｊ）−Δ＜Ｔ＋ｔΔ≦Γ（ｘｊ）を満足する最大の整数ｔに対してＴ＝Ｔ＋ｔΔとすることを意味し、「Ｎ」は閾値を変更しない（Ｎ）ことを意味し、「Ｄ」は閾値を減少（Ｄ）させること、すなわちＴ＝Ｔ−Δとすることを意味する（図５の注１参照）。
【００４１】
また、図において、「Ｆ」、「Ｌ」、「Ｂ」は、夫々、解の部分系列を示すポインタを前進（Ｆ）させること，解の部分系列を示すポインタを横進（Ｌ）させること，解の部分系列を示すポインタを後進（Ｂ）させることを意味し、「Ｌ or Ｂ」は、ポインタが横進可能ならばポインタを横進（Ｌ）させ、さもなくばポインタを後進（Ｂ）させることを意味する（図５の注２参照）。
【００４２】
尚、あるポインタが横進可能か否とは、「そのポインタの示す部分系列の末端の枝の付け根」から分岐する部分系列をすべて探索し尽くしたか否かという意味なのだが、そのことは、次のようにすると簡単に判定できる。
【００４３】
すなわち、図６に示すように、同じ分岐点から枝分かれしている枝に、順序を付ける。図では、図の上のほうから順に、１、２と順序付けしている。尚、前述の誤り訂正の例においては、暗黙のうちに、「枝に割り当てられた符号シンボル」と受信信号との間のハミング距離にもとづいて、枝に順序付けをしていた。枝の順序付けの仕方に依存して、ポインタの動作は変わる。しかし、ファノ・アルゴリズムは尤度が最大となるような標準データ系列を探索するものであるから、枝の順序付けの仕方が探索結果に影響を及ぼすことはない。このため、図６では、説明の便宜上、図の上のほうから順に、１、２と順序付けしている。
【００４４】
そして、ポインタを前進（Ｆ）させる時には、１番目の枝（＃１が書き添えられている枝）を通って前進させる。また、ポインタを横進（Ｌ）させる時には、１番目の枝から２番目の枝（＃２が書き添えられている枝）に横進（Ｌ）させる。尚、一般に、２個より多い枝分かれがある場合にポインタを横進（Ｌ）させる時には、ｊ番目の枝からｊ＋１番目の枝に横進（Ｌ）させる。
【００４５】
すると、ポインタの示す部分系列の先端の枝が、その枝の付根から分岐する枝のうち、最終番の枝かどうかで、ポインタを横進させられるか否かが、すなわち、その枝の付け根から分岐する部分系列をすべて探索し尽くしたか否かが、判定できる。
【００４６】
従って、仮に枝分かれの数をＣ本とすると、図５の注２は、「「Ｌ or Ｂ」とは、ポインタの示す部分系列の末端の枝に、１番からＣ−１番の番号が割り振られていれば、ポインタを横進（Ｌ）させ、Ｃ番が割り振られていれば、ポインタを後進（Ｂ）させることを意味する」と言いかえられる。
【００４７】
ファノ・アルゴリズムは、図５に示されるように、複数の規則の羅列として定義されるので、無限ループに陥らずに解を探索できることを理論的に示すことは難しい。そこで、以下では、簡単な例を用いて、無限ループに陥らずに解を探索できることを示す。
【００４８】
図７は、従来のファノ・アルゴリズムの動作原理を示す模式図である。図において、縦軸方向は、解の部分系列の尤度を示し、横軸方向は解の部分系列の深さを示している。また、解の部分系列は折れ線で、閾値は水平線で示されている。尚、以下の説明においては、解の部分系列を指すポインタを単にポインタと呼び、解の部分系列の尤度を単に尤度と呼ぶ。
【００４９】
ポインタが最初に枝ｂ１上を前進（Ｆ）すると、図５の規則１に従って、閾値がΔだけ増加する（図７（ａ））。
【００５０】
次に、ポインタが枝ｂ２上を前進（Ｆ）すると、やはり、図５の規則１に従って、Δだけ増加する（図７（ｂ））。尚、ここで枝ｂ２は、枝ｂ１の先端から分岐している枝である。
【００５１】
さて、その後、図５の規則に従ってポインタの前進・横進・後進を繰り返したものの、解が発見できなかったので、ポインタが枝ｂ１の付け根に戻ってきたとしよう。ポインタが枝ｂ１の付け根に戻ってくる際には、当然、後進（Ｂ）で戻ってくる（図７（ｃ））。
【００５２】
ポインタが枝ｂ１の付根にまで後進すると、図５の規則４に従って、閾値ＴがΔだけ減らされて、ポインタは再び枝ｂ１上を前進（Ｆ）する（図７（ｄ））。
【００５３】
次に、ポインタは、枝ｂ２上を前進（Ｆ）するのだが、その際には、図５の規則２に従って、閾値Ｔを増加させることなく、前進（Ｆ）する（図７（ｅ））。
【００５４】
以上の例からわかるように、ポインタがある同一の枝上を再度前進（Ｆ）する場合（図７（ｄ）の場合）には、前回（図７（ａ））その枝上を前進（Ｆ）した時の閾値（Ｔ（ａ））とは、異なる閾値（Ｔ（ａ）−Δ）で前進（Ｆ）する。このため、ファノ・アルゴリズムにおいては、無限ループに陥ること無く、解の探索が行われる。
【００５５】
尚、誤り訂正の分野におけるファノ・アルゴリズムの実施例については、例えば、米国特許第３，６６５，３９６号（Ｇｅｏｒｇｅ  Ｄａｖｉｄ  Ｆｏｒｎｅｙ，  Ｊｒ．，  Ｓｅｑｕｅｎｔｉａｌ  Ｄｅｃｏｄｉｎｇ，  Ｕｎｉｔｅｄ  Ｓｔａｔｅｓ  Ｐａｔｅｎｔ，  Ｎｏ．  ３，６６５，３９６，  Ｍａｙ  １９７２）に詳しい記述がある。
【００５６】
符号化率Ｒと呼ばれる値がコンピューテーショナル・カットオフレートＲｃｏｍｐと呼ばれる値よりも小さいと、ファノ・アルゴリズムで解を探索するのに要する計算時間の平均値は、解の長さＮ（ｘ）に比例する値になることが知られている。これに対して、総当り探索で解を探索するのに要する計算時間の平均値は、夫々の分岐点における枝分かれの数が２の場合には、２Ｎ（ｘ）に比例する値になる。従って、ファノ・アルゴリズムは、総当り探索と比べて、劇的に高速に解を探索できる。
【００５７】
尚、符号化率Ｒとは、情報シンボル系列の１シンボルを表現するのに必要なビットの数と、符号シンボル系列の１シンボルを表現するのに必要なビット数の比である。また、コンピューテーショナル・カットオフレートＲｃｏｍｐとは、前述の確率ｐ（ｙ）、ｐ（ｙ｜ｘｊ）、ｐ（ｘｊ）に依存して決まる値で、情報シンボル系列のエントロピーＨよりもやや小さい値であることが知られている。
【００５８】
ファノ・アルゴリズムには、以上で述べたように、高速に解を探索できるという特徴があるので、誤り訂正の分野で広く使われてきた。
【００５９】
【発明が解決しようとする課題】
しかしながら、ファノ・アルゴリズムには、標準データ系列が等確率で出現しない用途においては、しばしば、解を探索するのに要する計算時間の平均値が、解の長さＮ（ｘ）に比例する値にならずに、発散してしまうという問題があった。
【００６０】
なぜなら、標準データ系列が等確率で出現しないと、情報シンボル系列のエントロピーＨに相当する値が小さくなり、それに伴って、コンピューテーショナル・カットオフレートＲｃｏｍｐに相当する値も小さくなるからである。そして、符号化率に相当する値がコンピューテーショナル・カットオフレートＲｃｏｍｐに相当する値よりも大きくなると、解を探索するのに要する計算時間の平均値が、解の長さＮ（ｘ）に比例する値にならずに、発散してしまうからである。厳密には、標準データ系列の個数が有限個なので、計算量が無限大に発散することは無いのだが、多くの場合には、実用的な時間内で処理できないほど膨大な量になってしまう。
【００６１】
さて、標準データ系列が等確率で出現しない用途において、解を探索するのに要する計算時間の平均値が発散してしまうというファノ・アルゴリズムの問題を解決するためには、標準データ系列の出現確率に依存して、探索する標準データ系列の数を絞り込むことが必要である。
【００６２】
ところで、標準データ系列の出現確率に依存して探索する標準データ系列の数を絞り込む方法としては、出現確率が上位一定位以内であるような標準データ系列だけを探索したり、出現確率が一定値以上であるような標準データ系列だけを探索するビーム・サーチという方法が知られている。尚、ビーム・サーチについては、例えば特開平８−６５８８や特開平８−３２８５８３に記述がある。
【００６３】
しかしながら、ファノ・アルゴリズムにおいては、逐次的に１度に１本の部分系列しか調べないので、従来のビーム・サーチは適用できなかった。
【００６４】
このため、パターン認識や音声認識のように、標準データ系列が著しく不等確率で出現する用途において、ファノ・アルゴリズムが使われることは無かった。
【００６５】
【発明の目的】
本発明は、上記の問題点を解決し、標準データ系列が等確率で出現しない場合であっても少ない計算量で解を探索できる、データ探索方法及び装置を提供することを目的とする。
【００６６】
【課題を解決するための手段】
本発明のデータ探索装置は、
予め決められた複数の標準データ系列を記憶する記憶手段と（図１９の２）、
前記記憶手段に記憶された標準データ系列の部分系列を特定するポインタを生成するポインタ生成手段と（図１９の３）、
外部から入力されたデータ系列に対する前記標準データ系列の部分系列の枝尤度を出力する枝尤度生成手段を複数個有し（図１９の４１〜４ｍ）、
前記複数の枝尤度生成手段の夫々から出力する枝尤度に基づいて尤度を生成して出力する複数の尤度生成手段と（図１９の５１〜５ｍ）、
該複数の尤度生成手段の出力である複数の尤度の夫々が最大となるように前記ポインタ生成手段を制御するポインタ生成制御手段と
を具えたことを特徴とする。
【００６７】
尚、前記複数の尤度生成手段のうちの一つが出力する尤度は、標準データ系列の出現確率の逆数の対数から定数を引いた値に比例するものであることが望ましい。
また、前記ポインタ生成制御手段は、ファノ・アルゴリズムに基づいて制御を行なうものであることが望ましい。
【００６８】
本発明のデータ探索方法は、
予め決められた複数の標準データ系列を記憶し、
記憶された標準データ系列の部分系列を特定するポインタを生成し、
外部から入力されたデータ系列に対する前記標準データ系列の部分系列の枝尤度を複数個出力し、
前記複数の枝尤度に基づいて複数の尤度を生成し、
該複数の尤度の夫々が最大となるように前記ポインタの生成を制御する
ことを特徴とする。
【００６９】
尚、前記複数の尤度のうちの一つは、標準データ系列の出現確率の逆数の対数から定数を引いた値に比例するものであることが望ましい。
【００７０】
また、前記ポインタの生成制御は、ファノ・アルゴリズムに基づいて行なわれるものであることが望ましい。
【００７１】
【発明の実施の形態】
本発明では、ファノ尤度以外の第２の尤度を導入する。本発明は、簡単に言うと、逐次的に１度に１本のパスについてファノ尤度と第２の尤度を調べつつ、それら２つの尤度を同時に最大化するパスを探索するものである。
【００７２】
尚、以下では、ファノ尤度をΓ１と表記する。すなわち、
Γ１（ｘｊ）＝−ｌｏｇ｛ｐ（ｙ）／ｐ（ｙ｜ｘｊ）｝−Ｂ１（ｘｊ−１）
とする。ここで、Ｂ１（ｘｊ）はバイアス値であり、従来のファノ・アルゴリズムで用いられるバイアス値Ｂ（ｘｊ）と等しい。
【００７３】
また、第２の尤度を、
Γ２（ｘｊ）＝Ａ２（ｘｊ）−Ｂ２（ｘｊ−１）
とおく。ここで、Ａ２（ｘｊ）は後で定義される値である。また、Ｂ２（ｘｊ−１）はバイアス値であり、ｘｊが正しい解の部分系列であればΓ２（ｘｊ）の期待値が正となり、ｘｊが正しい解の部分系列で無ければΓ２（ｘｊ）の期待値が負となるような値が選ばれる。
【００７４】
但し、標準データ系列が等確率で出現する場合には、どの期待値も等しい値をとるので、そのようにバイアス値を選ぶことができない。その場合には、Γ２（ｘｊ）の期待値が常に正となるように、バイアス値を選ぶものとする。
【００７５】
２つの尤度Γ１，Γ２を同時に最大化することは、一般に、予め与えられた定数α１，α２に対して、α１Γ１＋α２Γ２という一つの尤度を最大化することに帰着してしまうように思える。
【００７６】
しかしながら、逐次的に１度に１本のパスについて２つの尤度Γ１，Γ２を調べつつ２つの尤度Γ１，Γ２を同時に最大化するパスの部分系列を探索すると、単に２つの尤度Γ１，Γ２が同時に最大化できるだけでなく、実は、夫々、Γ１（ｘｊ）とΓ２（ｘｊ）の定義式の第１項目である−ｌｏｇ｛ｐ（ｙ）／ｐ（ｙ｜ｘｊ）｝とＡ２（ｘｊ）の大きなパスが優先的に探索されるという効果が得られる。
【００７７】
なぜなら、ファノ・アルゴリズムにおいては、ファノ尤度Γ（ｘｊ）の定義式におけるバイアス値Ｂ（ｘｊ−１）を適切に選ぶことによって、ファノ尤度Γ（ｘｊ）の定義式の第１項目の値の大きなパスを優先して探索しているからである。
【００７８】
そこで、本発明では、第２の尤度Γ２の第１項目であるＡ２（ｘｊ）を
Ａ２（ｘｊ）＝ｌｏｇ｛ｐ（ｘｊ）｝
とする。すなわち、第２の尤度Γ２を
Γ２（ｘｊ）＝ｌｏｇ｛ｐ（ｘｊ）｝−Ｂ２（ｘｊ−１）
とする。
【００７９】
出現確率ｐ（ｘｊ）の大きな解ｘｊは、当然のことながら、ｌｏｇ｛ｐ（ｘｊ）｝の値が大きいから、そのように第２の尤度を選んで、逐次的に１度に１本のパスについて２つの尤度Γ１，Γ２を調べつつ２つの尤度Γ１，Γ２を同時に最大化するパスを探索すると、出現確率の高い標準データ系列が優先的に探索される。このため、標準データ系列が等確率で出現しない場合であっても、少ない計算量で解を探索できる。
【００８０】
但し、本発明の基本原理は、以上で述べたようなものであるが、本発明のデータ探索方法を具体的に記述する動作規則を構成することは非常に難しい。
【００８１】
というのも、尤度と閾値の組を２つに増やすこと自体は容易なのだが、とるべき動作が一つしか無いので、従来のファノ・アルゴリズムの動作規則に従って２つの尤度と閾値を独立に変更することができないからである。また、尤度と閾値の組が２つに増えると、その分だけ、可能な動作規則の数が膨大なものとなるからである。
【００８２】
従来のファノ・アルゴリズムでさえ、その動作規則が直感的な理解を妨げるほど抽象的かつ複雑なのであるから、従来のファノ・アルゴリズムの動作規則と異なる未知の膨大な動作規則の組について、その動作を確認するということを繰り返して、所望の動作規則を試行錯誤的に求めるということは、事実上不可能である。
【００８３】
もっとも、幸いなことに、本発明の動作規則を探すための手がかりが幾つかある。
【００８４】
まず、本発明のデータ探索方法は従来のファノ・アルゴリズムを拡張したものであるから、２つの尤度のうち一方が単調に増加する場合には、本発明の動作規則は従来のファノ・アルゴリズムに帰着しなければならない。
【００８５】
また、本発明においては、２つの尤度Γ１，Γ２を同時に最大化するのであるから、すなわち２つの尤度Γ１，Γ２は対等なのであるから、動作規則は尤度Γ１，Γ２に関して対称でなければならない（すなわち、動作規則においてΓ１とΓ２を入れ替えると、元の動作規則と等価な動作規則が得られなければならない）。
【００８６】
これらを手がかりにして、幾つかの動作規則を試行錯誤的に試してみたところ、図８のような動作規則が得られた。この動作規則は、動作規則の候補を絞り込むための手がかりとして示した前述の条件を満足している。尚、図８の記法は、図５と同様である。
【００８７】
次に、図８に示す動作規則に従って探索すると、無限ループに陥らずに解を探索できることを示しておこう。
【００８８】
図９は、本発明の動作原理を示す模式図である。図において、縦軸方向は、解の部分系列の尤度Γ１を示し、横軸方向は解の部分系列の深さを示している。また、解の部分系列は折れ線で、閾値Ｔ１は水平線で示されている。尚、以下の説明においては、解の部分系列を指すポインタを単にポインタと呼び、解の部分系列の尤度を単に尤度と呼ぶ。
【００８９】
図９（ａ）に示すように、枝ｂ３において、図８の規則１．１に従って、閾値Ｔ１を増加して前進し、その後、枝ｂ７において、図８の規則１．１に従って、閾値Ｔ１を増加して前進したとする。また、枝ｂ３から枝ｂ７に到る過程において、閾値Ｔ２は変更されていないものとする。
【００９０】
この場合には、従来のファノ・アルゴリズムと同様に、ポインタが枝ｂ７上を前進（Ｆ）する場合には、前回枝ｂ７上を前進（Ｆ）した時とは、異なる閾値Ｔ１で前進（Ｆ）する。このため、無限ループに陥ること無く、解の探索が進行する。
【００９１】
一方、図９（ｂ）に示すように、枝ｂ３から枝ｂ７に到る過程で、枝ｂ５において、閾値Ｔ２が変更されたとする。
【００９２】
この場合には、枝ｂ７から枝ｂ３のほうに後戻りすると、枝ｂ５において、図８の規則４.２が適用されて、枝ｂ３に後戻りする前に、枝７に戻ることがある。すると、ポインタは、前回枝ｂ７上を前進（Ｆ）した時と同じ閾値Ｔ１で、枝ｂ７上を前進（Ｆ）してしまう。
【００９３】
しかし、幸いなことに、枝ｂ５において、図８の規則４.２が適用されて閾値Ｔ２が変更されているので、再び枝ｂ７上を前進する場合には、前回枝ｂ７上を前進（Ｆ）した時とは、異なる閾値Ｔ２で枝ｂ７上を前進している。
【００９４】
以上の例からわかるように、本発明においては、ポインタがある枝上を前進（Ｆ）する場合には、前回その枝上を前進（Ｆ）した時とは、異なる閾値の組（Ｔ１，Ｔ２）で前進する。このため、本発明においては、無限ループに陥ること無く、解の探索が行われる。
【００９５】
次に、本発明のデータ探索方法の実施形態についてフローチャートを参照して詳細に説明する。
【００９６】
図１０は、本発明のデータ探索方法の実施形態を示すフローチャートである。尚、以下の説明においては、解の部分系列を指すポインタを単にポインタと呼び、解の部分系列の尤度を単に尤度と呼ぶ。
【００９７】
図において、処理が開始されるとステップＳ１１０に制御が移される。
【００９８】
ステップＳ１１０においては、閾値Ｔ１と閾値Ｔ２の両方を０にし、標準データ系列を記憶しているツリー状のデータ構造の幹のアドレスをポインタに設定し、ステップＳ１２０に制御が移される。
【００９９】
ステップＳ１２０においては、ポインタの尤度Γ１（ｘｊ），Γ２（ｘｊ）が計算され、ステップＳ１３０に制御が移される。尚、ここでｘｊは、ポインタの示す部分系列ｘｊである。図及び以下の説明においても、説明の便宜上、ｘｊは、ポインタの示す部分系列ｘｊであるとする。
【０１００】
ステップＳ１３０においては、ポインタがツリーの末端に達しており、かつ、Γ１（ｘｊ）≧Ｔ１、かつ、Γ２（ｘｊ）≧Ｔ２ならば処理を終了し、さもなくば、ステップＳ１４０に制御を移す。
【０１０１】
ステップＳ１４０においては、Γ１（ｘｊ−１）、Γ１（ｘｊ）、Γ２（ｘｊ−１）、Γ２（ｘｊ）、Ｔ１、Ｔ２、Δ１、Δ２に対して、図８の規則で用いられる比較演算を施して、ステップＳ１５０に制御を移す。
【０１０２】
ステップＳ１５０においては、図８の規則に従って、ステップＳ１４０の比較演算の結果、および、ポインタが横進可能であるか否かにもとづいて、閾値Ｔ１とＴ２に対する操作とポインタに対する操作を決定し、ステップＳ１６１１に制御を移す。
【０１０３】
尚、図及び以下の説明において、閾値に対する３種類の操作を、夫々、「Ｉ」、「Ｎ」、「Ｄ」と表記する。ここで、「Ｉ」、「Ｎ」、「Ｄ」は、夫々、閾値を増加（Ｉ）させること、閾値を変更しない（Ｎ）こと、閾値を減少（Ｄ）させることを意味する。また、ポインタに対する３種類の操作を、夫々、「Ｆ」、「Ｌ」、「Ｂ」と表記する。ここで、「Ｆ」、「Ｌ」、「Ｂ」は、夫々、ポインタを前進（Ｆ）させること、横進（Ｌ）させること、後進（Ｂ）させることを意味する。
【０１０４】
ステップＳ１６１１においては、ステップＳ１５０で決定された閾値Ｔ１に対する操作が、「Ｄ」、「Ｎ」、「Ｉ」であれば、夫々、ステップＳ１６２１、ステップＳ１６１２、ステップＳ１６３１に制御を移す。
【０１０５】
ステップＳ１６２１においては、閾値Ｔ１を減少（Ｄ）させて、ステップＳ１６１２に制御を移す。なお、閾値Ｔ１の減少のさせ方は、図８の注１に従うものとする。
【０１０６】
ステップＳ１６３１においては、閾値Ｔ１を増加（Ｉ）させて、ステップＳ１６１２に制御を移す。なお、閾値Ｔ１の増加のさせ方は、図８の注１に従うものとする。
【０１０７】
ステップＳ１６１２においては、ステップＳ１５０で決定された閾値Ｔ２に対する操作が、「Ｄ」、「Ｎ」、「Ｉ」であれば、夫々、ステップＳ１６２２、ステップＳ１７１、ステップＳ１６３２に制御を移す。
【０１０８】
ステップＳ１６２２においては、閾値Ｔ２を減少（Ｄ）させて、ステップＳ１７１に制御を移す。なお、閾値Ｔ２の減少のさせ方は、図８の注１に従うものとする。
【０１０９】
ステップＳ１６３２においては、閾値Ｔ２を増加（Ｉ）させて、ステップＳ１７１に制御を移す。なお、閾値Ｔ２の増加のさせ方は、図８の注１に従うものとする。
【０１１０】
ステップＳ１７１においては、ステップＳ１５０で決定された動作が、「Ｂ」、「Ｌ」、「Ｆ」であれば、夫々、ステップＳ１７２、ステップＳ１７３、ステップＳ１７４に制御を移す。
【０１１１】
ステップＳ１７２においては、ポインタを後進（Ｂ）させて、ステップＳ１２０に制御を移す。
【０１１２】
ステップＳ１７３においては、ポインタを横進（Ｌ）させて、ステップＳ１２０に制御を移す。
【０１１３】
ステップＳ１７４においては、ポインタを前進（Ｆ）させて、ステップＳ１２０に制御を移す。
【０１１４】
次に、本発明のデータ探索装置の実施形態について図面を参照して詳細に説明する。
【０１１５】
図１１は、本発明のデータ探索装置の実施形態を示す機能ブロック図である。尚、以下の説明においては、解の部分系列を指すポインタを単にポインタと呼び、解の部分系列の尤度を単に尤度と呼ぶ。
【０１１６】
図において、データ系列ｙが、入力端子１１から入力されて、枝尤度生成手段４１及び４２に供給される。
【０１１７】
標準データ系列記憶手段２は、複数の標準データ系列が予めツリー状のデータ構造として記憶されているリード・オンリ・メモリ（ＲＯＭ）などの記憶装置で構成されている。そして、後述のポインタ生成手段３から出力されるポインタが示す標準データ系列の部分系列ｘｊを、枝尤度生成手段４１及び４２と出力端子１２に供給する。
【０１１８】
ポインタ生成手段３は、「標準データ系列記憶手段２に記憶されているツリーの分岐点のアドレス」が予め記憶されているリード・オンリ・メモリ（ＲＯＭ）などの記憶装置と、ポインタを記憶するためのレジスタで構成されている。そして、後述の制御手段１０からの制御信号に従って、ポインタを前進（Ｆ）、横進（Ｌ）あるいは後進（Ｂ）させる。
【０１１９】
尚、標準データ系列記憶手段２とポインタ生成手段３の詳細と、これが実際にどのようにして構成されるかについては、ここでは触れない。その詳細は、情報処理に関するほとんどの書籍に記載されており、当業者にとっては明白なことである。そのような書籍の一つとして、例えば、カラーノ著の書籍（Ｆｒａｎｋ  Ｍ．  Ｃａｒｒａｎｏ，  Ｄａｔａ  Ａｂｓｔｒａｃｔｉｏｎ  ａｎｄ  Ｐｒｏｂｌｅｍ  Ｓｏｌｖｉｎｇ  Ｗｉｔｈ  Ｃ＋＋：  Ｗａｌｌｓ  ａｎｄ  Ｍｉｒｒｏｒｓ，  Ｔｈｅ  Ｂｅｎｊａｍｉｎ／Ｃｕｍｍｉｎｇｓ  Ｐｕｂｌｉｓｈｉｎｇ  Ｃｏｍｐａｎｙ，  Ｉｎｃ．，  １９９５）がある。
【０１２０】
横進可能識別信号生成手段１は、ポインタ生成手段３から出力されるポインタを入力し、そのポインタの示す標準データ系列の部分系列ｘｊが横進可能かどうか判定し、可能ならば１を出力し、さもなくば０を出力する。横進可能識別信号生成手段１の出力は、動作決定手段８に供給される。以下では、横進可能識別信号生成手段１の出力を、横進可能識別信号と呼ぶ。
【０１２１】
尚、横進可能識別信号生成手段１は、例えば、標準データ系列記憶手段２におけるデータの配置を次のように選んでおけば、簡単な論理回路で構成できる。
【０１２２】
すなわち、標準データ系列記憶手段２において、標準データ系列の部分系列ｘｊが横進可能でなければ、そのポインタの下位Ｌビットがオール１であるように、一方、標準データ系列の部分系列ｘｊが横進可能であれば、そのポインタの下位Ｌビットがオール１でないように、標準データ系列記憶手段２に記憶されているデータを予め配置しておく。尚、ここでＬは、予め決められた定数である。
【０１２３】
このようにすると、横進可能識別信号生成手段１は、ポインタの下位Ｌビットの論理積の否定を計算する論理回路として簡単に構成できる。
【０１２４】
枝尤度生成手段４ｋ（ｋ＝１，２）は、前述の尤度Γｋの定義式に従って、入力端子１１から供給されるデータ系列ｙと、標準データ系列記憶手段２から供給される部分系列ｘｊに対して、
γｋ（ｘｊ）（Γｋ（ｘｊ）−Γｋ（ｘｊ−１）に相当する）
を求め、計算結果を尤度生成手段５ｋに供給する。なお、以下では、γｋ（ｘｊ）のことを、尤度Γｋに関するｘｊの枝尤度と呼ぶ。
【０１２５】
尚、γ１（ＮＵＬＬ），γ２（ＮＵＬＬ）は、十分に大きな値として定義しておく（注：ＮＵＬＬは空の系列を意味する）。このようにすると、ポインタがツリーの幹に到達しても、次の動作は常に「前進（Ｆ）」となるので、それ以上後戻りすることが自動的に避けられる。
【０１２６】
尤度生成手段５ｋ（ｋ＝１，２）は、枝尤度生成手段４ｋから供給される枝尤度γｋ（ｘｊ）にもとづいて、部分系列ｘｊ−１の尤度Γｋ（ｘｊ−１）と、部分系列ｘｊの尤度Γｋ（ｘｊ）を計算し、計算結果を比較手段６ｋと閾値生成手段７ｋに供給する。
【０１２７】
比較手段６ｋ（ｋ＝１，２）は、閾値生成手段７ｋから供給される閾値Ｔｋと、予め決められた定数Δｋと、尤度Γｋ（ｘｊ−１），Γｋ（ｘｊ）に対して、比較演算
Γｋ（ｘｊ−１）＜Ｔｋ，
Γｋ（ｘｊ−１）＜Ｔｋ＋Δｋ，
Γｋ（ｘｊ）≧Ｔｋ
を行い、演算結果を動作決定手段８に供給する。
【０１２８】
閾値生成手段７ｋ（ｋ＝１，２）は、尤度生成手段５ｋから供給される尤度Γｋ（ｘｊ）と後述の動作決定手段８から供給される動作信号と後述の制御手段１０から供給される制御信号にもとづいて閾値Ｔｋを生成し、生成された閾値Ｔｋを比較手段６ｋに供給する。
【０１２９】
動作決定手段８は、横進可能識別信号生成手段１から供給される横進可能識別信号と、比較手段６１及び６２から供給される比較結果と、レジスタ９に保持されている過去の動作信号に依存して、次の動作信号と２個の閾値制御信号を決定し、決定された動作信号と２個の閾値制御信号を出力する。
【０１３０】
尚、動作信号は、「Ｆ」、「Ｌ」、「Ｂ」で表記される３種類の値をとる。ここで、「Ｆ」、「Ｌ」、「Ｂ」は、夫々、夫々、ポインタを前進（Ｆ）させること、横進（Ｌ）させること、後進（Ｂ）させることを意味する。
【０１３１】
また、２個の閾値制御信号は、「Ｉ」、「Ｎ」、「Ｄ」で表記される３種類の値をとる。ここで、「Ｉ」、「Ｎ」、「Ｄ」は、夫々、閾値を増加（Ｉ）させること、閾値を変更しない（Ｎ）こと、閾値を減少（Ｄ）させることを意味する。
【０１３２】
レジスタ９は、制御手段１０からＣＬＲ信号入力端子に０が供給されている時に制御手段１０からクロック信号入力端子にクロックパルスが１個供給されると、記憶している値を「前進（Ｆ）」に初期化し、制御手段１０からＣＬＲ信号入力端子に１が供給されている時に制御手段１０
１０
からクロック信号入力端子にクロックパルスが１個供給されると、動作決定手段８から供給される動作信号を保持する。また、レジスタ９に保持されている動作信号は、動作決定手段８に供給される。
【０１３３】
制御手段１０は、動作決定手段８の出力にもとづいて、ポインタ生成手段３、尤度生成手段５１及び５２、閾値生成手段７１及び７２、レジスタ９に制御信号を送出する。すると、制御手段１０が動作を終了した時点で、出力端子１２に解ｘが得られる。
【０１３４】
図１２は、尤度生成手段５ｋ（ｋ＝１，２）の基本構成を示す機能ブロック図である。図において、枝尤度γｋ（ｘｊ）が、入力端子５５１から入力されて、減算器５１０と加算器５２０に供給される。
【０１３５】
レジスタ５４０には、尤度Γｋ（ｘｊ）が保持されており、保持されている尤度Γｋ（ｘｊ）が、出力端子５７２、減算器５１０、加算器５２０に供給される。
【０１３６】
減算器５１０は、レジスタ５４０から供給される尤度Γｋ（ｘｊ）から、枝尤度γｋ（ｘｊ）を減算して、得られた減算結果Γｋ（ｘｊ）−γｋ（ｘｊ）をセレクタ５３０と出力端子５７１に供給する。枝尤度の定義により、計算結果Γｋ（ｘｊ）−γｋ（ｘｊ）は、Γｋ（ｘｊ−１）に等しい。
【０１３７】
加算器５２０は、レジスタ５４０から供給される尤度Γｋ（ｘｊ）に、枝尤度γｋ（ｘｊ）を加算して、得られた計算結果Γｋ（ｘｊ）＋γｋ（ｘｊ）をセレクタ５３０に供給する。枝尤度の定義により、計算結果Γｋ（ｘｊ）＋γｋ（ｘｊ）は、Γｋ（ｘｊ＋１）に等しい。
【０１３８】
セレクタ５３０は、入力端子５６１から供給される制御信号が「前進（Ｆ）」ならば、加算器５２０の出力を選択して出力し、入力端子５６１から供給される制御信号が「後進（Ｂ）」ならば、減算器５１０の出力を選択して出力する。
【０１３９】
レジスタ５４０は、入力端子５６３から０が供給されている時に入力端子５６２からクロックパルスが１個供給されると、記憶している値を０にし、入力端子５６３から１が供給されている時に入力端子５６２からクロックパルスが１個供給されると、セレクタ５３０から供給される値を保持する。
【０１４０】
ポインタを後進（Ｂ）させると、新しいポインタの尤度（即ち、新しいポインタで特定される部分系列ｘｊ−１の尤度（以下同様））はΓｋ（ｘｊ−１）となり、ポインタを前進（Ｆ）させると、新しいポインタの尤度はΓｋ（ｘｊ＋１）となるから、セレクタ５３０の出力する値は、新しいポインタの尤度に等しい。このため、レジスタ５４０には、常に、新しいポインタの尤度が正しく保持される。
【０１４１】
図１３は、比較手段６ｋ（ｋ＝１，２）の基本構成を示す機能ブロック図である。
【０１４２】
図において、入力端子６５１から尤度Γｋ（ｘｊ−１）が入力されて、比較器６２０，６３０に供給される。入力端子６５２から閾値Ｔｋが入力されて、比較器６２０と加算器６１０と比較器６４０に供給される。入力端子６５３から尤度Γｋ（ｘｊ）が入力されて、比較器６４０に供給される。
【０１４３】
加算器６１０は、入力端子６５２から供給されるＴｋに予め決められた定数Δｋを加算し、計算結果Ｔｋ＋Δｋを比較手段６３０に供給する。
【０１４４】
比較器６２０は、入力端子６５１から供給されるΓｋ（ｘｊ−１）と入力端子６５２から供給されるＴｋとの大小を比較し、比較結果Γｋ（ｘｊ−１）＜Ｔｋを出力端子６６１に供給する。
【０１４５】
比較器６３０は、入力端子６５１から供給されるΓｋ（ｘｊ−１）と加算器６１０から供給されるＴｋ＋Δｋとの大小を比較し、比較結果Γｋ（ｘｊ−１）＜Ｔｋ＋Δｋを出力端子６６２に供給する。
【０１４６】
比較器６４０は、入力端子６５３から供給されるΓｋ（ｘｊ）と入力端子６５２から供給されるＴｋとの大小を比較し、比較結果Γｋ（ｘｊ）≧Ｔｋを出力端子６６３に供給する。
【０１４７】
図１４は、閾値生成手段７ｋ（ｋ＝１，２）の基本構成を示す機能ブロック図である。
【０１４８】
レジスタ７４０には、閾値Ｔｋが保持されており、保持されている閾値Ｔｋが、出力端子７５５、セレクタ７３０、減算器７１０に供給される。
【０１４９】
減算手段７１０は、レジスタ７４０から供給されるＴｋから定数Δｋを減算し、計算結果Ｔｋ−Δｋをセレクタ７３０に供給する。
【０１５０】
加算器７２０は、入力端子７５１から供給されるΓｋ（ｘｊ）と予め決められた定数Δｋに対して、Γｋ（ｘｊ）−Δｋ＜Ｔｋ＋ｔΔｋ≦Γｋ（ｘｊ）を満足する最大の整数ｔを求め、Γｋ（ｘｊ）＋ｔΔｋをセレクタ７３０に供給する。
【０１５１】
セレクタ７３０は、入力端子７５２から供給される閾値制御信号の値が、「増加（Ｉ）」、「減少（Ｄ）」、「不変（Ｎ）」の時には、夫々、加算器７２０、減算器７１０、レジスタ７４０の出力を選択し、選択された値をレジスタ７４０に供給する。
【０１５２】
レジスタ７４０は、入力端子７５４から０が供給されている時に入力端子７５３からクロックパルスが１個供給されると、記憶している値を０にし、入力端子７５４から１が供給されている時に入力端子７５３からクロックパルスが１個供給されると、セレクタ７３０から供給される値を保持する。
【０１５３】
セレクタ７３０は、閾値Ｔｋの新しい値を出力しているので、レジスタ７４０には、常に、新しい閾値Ｔｋの値が正しく保持される。
【０１５４】
図１５は、動作決定手段８の論理構造を示す真理値表である。
【０１５５】
表において、入力側の「動作」と書かれた信号は、レジスタ９から供給される動作信号であり、動作信号の値は「Ｆ」、「Ｌ」、「Ｂ」で表示されている。ここで、「Ｆ」、「Ｌ」、「Ｂ」は、夫々、ポインタを前進（Ｆ）させること、ポインタを横進（Ｌ）させること、ポインタを後進（Ｂ）させることを意味する。
【０１５６】
入力側の「Γｋ（ｘｊ−１）＜Ｔｋ」「Γｋ（ｘｊ−１）＜Ｔｋ＋Δｋ」「Γｋ（ｘｊ）≧Ｔｋ」（ｋ＝１，２）と書かれた信号は、比較手段６ｋから供給される比較結果であり、信号の値が０であることは、その関係式が成立していないことを示し、信号の値が１であることは、その関係式が成立していることを示す。
【０１５７】
入力側の「横進可能」と書かれた信号は、横進可能識別信号生成手段１から供給される横進可能識別信号で、ポインタを横進させらるか否かを示す信号であり、信号値が０であることは、横進させられないことを示し、信号値が１であることは、横進させられることを示す。
【０１５８】
尚、真理値表の入力側において、「−」と書かれた欄は、そこの値が、０でも１でも構わないことを示す。
【０１５９】
出力側の「閾値Ｔｋ」（ｋ＝１，２）と書かれた信号は、入力側において成立する条件に対応して閾値生成手段７ｋ（ｋ＝１，２）へ出力する閾値制御信号であり、信号の値は「Ｉ」、「Ｄ」、「Ｎ」で表示されている。ここで、「Ｉ」、「Ｄ」、「Ｎ」は、それぞれ、閾値を増加（I）すること、閾値を減少（Ｄ）させること、閾値を変更しない（Ｎ）ことを意味する。
【０１６０】
また、出力側の「動作」と書かれた信号は、入力側の条件に対して制御手段
１０
とレジスタ９へ出力する動作信号であり、信号の値は「Ｆ」、「Ｌ」、「Ｂ」で表示されている。ここで、「Ｆ」、「Ｌ」、「Ｂ」は、夫々、ポインタを前進（Ｆ）させること、ポインタを横進（Ｌ）させること、ポインタを後進（Ｂ）させることを意味する。
【０１６１】
尚、真理値表の出力側において、「−」と書かれた欄は、そこの値が、真理値表の他の列の条件で決まることを示している。
【０１６２】
図１６は、制御手段１０の動作を示すフローチャートである。尚、説明の便宜上、図及び以下の説明において、ｘｊはポインタの示す部分系列ｘｊを意味する。また、解の部分系列を指すポインタを単にポインタと呼び、解の部分系列の尤度を単に尤度と呼ぶ。
【０１６３】
図において、制御手段１０が動作を開始すると、まず、ステップＣ１１０に制御を移す。
【０１６４】
ステップＣ１１０においては、ツリー状のデータ構造の幹を示すポインタをポインタ生成手段３に設定するとともに、尤度生成手段５１及び５２と閾値生成手段７１及び７２とレジスタ９に対して、ＣＬＲ信号入力端子に０を供給して、クロック信号入力端子にクロックパルスを１個供給し、その後、ＣＬＲ信号入力端子に１を供給し、ステップＣ１２０に制御を移す。
【０１６５】
ステップＣ１２０においては、もし、ポインタがツリーの末端に到達しており、かつ、Γ１（ｘｊ）≧Ｔ１かつΓ２（ｘｊ）≧Ｔ２であれば、処理を終了し、さもなくば、制御をステップＣ１３０に移す。
【０１６６】
ステップＣ１３０においては、動作決定手段８の出力する動作信号の値が「Ｂ」であれば、制御をＣ１４１に移し、動作決定手段８の出力する動作信号の値が「Ｌ」であれば、制御をＣ１５１に移し、動作決定手段８の出力する動作信号の値が「Ｆ」であれば、制御をステップＣ１６１に移す。
【０１６７】
ステップＣ１４１においては、尤度生成手段５１及び５２のＳＥＬ信号入力端子に「Ｂ」を供給して、尤度生成手段５１及び５２と閾値生成手段７１及び７２とレジスタ９のクロック信号入力端子にクロックパルスを１個供給し、制御をステップＣ１４２に移す。
【０１６８】
ステップＣ１４２においては、ポインタを後進（Ｂ）させ、制御をステップＣ１２０に移す。
【０１６９】
ステップＣ１５１からステップＣ１５４に到る一連のステップにおいては、一旦、ポインタを後進（Ｂ）させた後に、後進してきた枝から見て横進する位置にある枝に向けてポインタを前進（Ｆ）させることで、ポインタを横進（Ｌ）させる。
【０１７０】
まず、ステップＣ１５１においては、尤度生成手段５１及び５２のＳＥＬ信号入力端子に「Ｂ」を供給して、尤度生成手段５１及び５２と閾値生成手段７１及び７２とレジスタ９のクロック信号入力端子にクロックパルスを１個供給し、制御をステップＣ１５２に移す。
【０１７１】
ステップＣ１５２においては、ポインタを後進（Ｂ）させ、制御をステップＣ１５３に移す。
【０１７２】
ステップＣ１５３においては、後進してきた枝から見て横進する位置にある枝に向けてポインタを前進（Ｆ）させ、制御をステップＣ１５４に移す。
【０１７３】
ステップＣ１５４においては、尤度生成手段５１及び５２のＳＥＬ信号入力端子に「Ｆ」を供給して、尤度生成手段５１及び５２のクロック信号入力端子にクロックパルスを１個供給し、制御をステップＣ１２０に移す。
【０１７４】
ステップＣ１６１においては、ポインタを前進（Ｆ）させ、制御をステップＣ１６２に移す。
【０１７５】
ステップＣ１６２においては、尤度生成手段５１及び５２のＳＥＬ信号入力端子に「Ｆ」を供給して、尤度生成手段５１及び５２と閾値生成手段７１及び７２とレジスタ９のクロック信号入力端子にクロックパルスを１個供給し、制御をステップＣ１２０に移す。
【０１７６】
【発明の他の実施の形態】
データ系列ｙが出現する確率ｐ（ｙ）と、標準データ系列の長さｊの部分系列ｘｊが出現したという条件下でデータ系列ｙが出現する確率ｐ（ｙ｜ｘｊ）と、標準データ系列の長さｊの部分系列ｘｊの出現する確率ｐ（ｘｊ）の組のことを、以下では、確率モデルと呼ぶ。
【０１７７】
データ探索方法が用いられる用途においては、どのような情報をデータ系列の１シンボルとして定義するかによって、異なる確率モデルが定義される。このため、１つの用途に対して、複数の確率モデルが存在し得る。
【０１７８】
例えば、音声認識においては、音声信号をＡ／Ｄ変換されて得られる各々のサンプル値に相当するディジタル信号を１シンボルとして定義することもできる。或いは、そのディジタル信号系列から認識された音素や単語を１シンボルとして定義することもできる。
【０１７９】
本発明の第１の実施形態では、１つの確率モデルしか扱っていなかったので、２つの尤度しか用いていなかった。しかし、そのことは、本発明が、２つの尤度を用いるものに限定されることを意味していない。本発明のデータ探索方法は、一般に、ｍ個の「尤度と閾値の組」に対しても適用できる。
【０１８０】
ここで、ｍは、次のようにして決まる定数である。すなわち、確率モデルの個数をｋとし、ｇ個（１≦ｇ≦ｋ）の確率モデルに対しては夫々２つの尤度を用い、残りのｋ−ｇ個の確率モデルに対してはファノ尤度しか用いないとすると、ｍは、ｍ＝ｋ＋ｇである。本発明は、標準データ系列の出現確率に応じて探索する標準データ系列の数を絞り込むものであるから、ｇ個の確率モデルにおいて２つの尤度を用いことで、探索する標準データ系列の数を絞り込むことができるのであれば、残りのｋ−ｇ個の確率モデルについては、ファノ尤度だけを用いれば良い。
【０１８１】
図１７は、本発明のデータ探索方法の第２の実施例の動作規則を示す表である。尚、図１７の記法等は、図８と同様である。
【０１８２】
説明は省略するが、ｍ＞２の場合には、ポインタがある枝上を前進（Ｆ）する場合には、前回その枝上を前進（Ｆ）した時とは、異なる閾値の組（Ｔ１，Ｔ２，．．．，Ｔｍ）で前進する。このため、本発明においては、ｍ＞２の場合にも、無限ループに陥ること無く、解の探索が行われる。
【０１８３】
次に、本発明のデータ探索方法の第２の実施形態について図面を参照して詳細に説明する。
【０１８４】
図１８は、本発明のデータ探索方法の第２の実施形態を示すフローチャートである。
【０１８５】
図１８において、ステップＳ２１０、Ｓ２２０、Ｓ２３０、Ｓ２４０、Ｓ２５０、Ｓ２６０ｋ、Ｓ２７０の処理内容は、夫々、データ探索方法の第１の実施例（図１０）におけるＳ１１０、Ｓ１２０、Ｓ１３０、Ｓ１４０、Ｓ１５０、Ｓ１６０ｋ、Ｓ１７０の処理内容と同様である。但し、データ探索方法の第１の実施例（図１０）では、尤度Γｋと閾値Ｔｋの組が、２個しか無かったが（ｋ＝１，２）、第２の実施例では、ｍ個（ｍ＞２）に増やされている。それに伴って、夫々のステップにおいては、２個の変数についてではなく、ｍ個の変数について処理を行っている。また、第１の実施例では、ステップＳ１６０１からステップＳ１６０２までの２段のステップが直列接続されていたが、第２の実施例では、ステップＳ２６０１からステップＳ２６０ｍまでのｍ段のステップが直列接続されている。
【０１８６】
第２の実施例に関する詳しい説明は省略したが、第２の実施例は、第１の実施例の自然な拡張になっているので、以上の説明によって、第２の実施例の構成が理解できるであろう。
【０１８７】
本発明のデータ探索装置の第２の実施形態について図面を参照して詳細に説明する。
【０１８８】
図１９は、本発明のデータ探索装置の第２の実施形態を示す機能ブロック図である。
【０１８９】
図において、第１の実施例（図１１）では、枝尤度生成手段４、尤度生成手段５、比較手段６、閾値生成手段７の組が、２個しか無かったが、第２の実施例では、ｍ個（ｍ＞２）に増やされている。また、それに伴って、第２の実施例では、第１の実施例（図１１）の動作決定手段８、制御手段１０が、夫々、動作決定手段１８、制御手段２０に置き換えられている。
【０１９０】
図２０は、動作決定手段１８の論理構造を示す真理値表である。この真理値表は、動作決定手段１６０の真理値表（図１５）の自然な拡張になっている。
【０１９１】
図２１は、制御手段２０の動作を示すフローチャートである。このフローチャートは、夫々のステップにおいて、２個の尤度及び閾値についてではなく、ｍ個の尤度及び閾値について処理が行われていることを除けば、制御手段１０の動作を示すフローチャート（図１６）と同様である。
【０１９２】
第２の実施例に関する詳しい説明は省略したが、第２の実施例は、第１の実施例の自然な拡張になっているので、以上の説明によって、第２の実施例の構成が理解できるであろう。
【０１９３】
尚、本発明は斯る特定実施形態のみに限定されるべきではなく、当業者は、実施例の変形が本発明の意図を損なわずに実行しうることを理解するであろう。具体的には、例えば、次のような変形が可能である。
【０１９４】
（１）実施例では、前記ガラガーの書籍に記載されているファノ・アルゴリズムにもとづく実施例について説明されているが、他の逐次復号法や他のファノ・アルゴリズムの改良版にもとづくものであっても良い。
【０１９５】
（２）実施例では、便宜的にΓｋ（ｘ−１）＝−∞と定義することで、解の部分系列がツリーの幹部分に到達したという情報を動作決定手段８に供給する必要を無くしていた。しかし、解の部分系列がツリーの幹部分に到達したという情報を動作決定手段８に供給して、それにもとづいて動作を決定しても良い。
【０１９６】
（３）図５や図８の動作規則を変更することも可能である。例えば、図５や図８におけるΓｋ（ｘｊ）≧Ｔｋという条件を、Γｋ（ｘｊ）≧Ｔｋ＋Δｋに置き換えることも可能である。なぜなら、ファノ・アルゴリズムにおいて閾値を増加させるということは、図５の注１に書かれている操作を行うことであり、実際に閾値Ｔが増加させられるのは、Γ（ｘｊ−１）＜Ｔ＋ΔかつΓ（ｘｊ）≧Ｔ＋Δの時だからである。
【０１９７】
（４）実施例では、尤度Γｋと閾値Ｔｋにもとづいて次の動作を決めているが、初等的な式変形操作を行えば、Γｋ−Ｔｋの値だけにもとづいて動作を決めることが可能であることがわかるだろう。Γｋ−Ｔｋの値だけにもとづいて動作を決めるようにすれば、レジスタの個数が節約できるし、尤度Γｋや閾値Ｔｋを記憶するためのレジスタにおいてオーバーフローが発生することを防止できる。
【０１９８】
（５）実施例では、解として得られた標準データ系列ｘをそのまま出力しているが、標準データ系列ではなく、夫々の標準データ系列に対応して予め決められているコードを出力しても良い。
【０１９９】
【発明の効果】
本発明の第１の効果は、解の出現頻度が等確率でなくても、探索のための計算量が小さく済むため、誤り訂正のような用途だけでなく、パターン認識や音声認識などの用途でも、高速にデータ探索が行えるということである。その理由は、既に述べた通りである。
【０２００】
本発明の第２の効果は、装置規模が小さく済むということである。その理由は、パターン認識や音声認識などの用途で従来用いられていた探索方法においては、複数の探索アルゴリズムが組み合わせて用いられていたが、本発明においては、ファノ・アルゴリズム１種類だけで済むからである。しかも、ファノ・アルゴリズムは、探索アルゴリズムの中で、最も装置規模が小さく済む探索方法の一つだからである。
【０２０１】
本発明の第３の効果は、尤度が複数になっても、尤度の設計が容易であるということである。その理由は、パターン認識や音声認識などの用途で従来用いられていた探索方法においては、しばしば設計者が尤度を実験や試行錯誤などの手段によって経験的に決めていたが、本発明においては、解の出現確率さえ決まれば、尤度が自動的に決まるからである。また、従来の探索方法においては、複数の尤度Γ１，．．．，Γｍを同時に最大化する場合には、一般には、重み係数α１，．．．，αｍを決めて、α１Γ１＋．．．＋αｍΓｍを最大化することが行われるので、ｍが大きい場合には、最適な重み係数α１，．．．，αｍを決めることが非常に難しかったが、本発明においては、そのような係数を決める必要が無いからである。
【図面の簡単な説明】
【図１】標準データ系列のデータ構造を示す模式図
【図２】パスに対する操作の定義を示す模式図
【図３】誤り訂正用の符号化装置（符号器）の基本構成を示す機能ブロック図
【図４】誤り訂正用の符号化装置（符号器）の動作を示す模式図
【図５】従来のファノ・アルゴリズムの動作規則を示す表
【図６】横進可能か否かを判定するための方法を示す模式図
【図７】従来のファノ・アルゴリズムの動作原理を示す模式図
【図８】本発明のデータ探索方法の動作規則を示す表
【図９】本発明のデータ探索装置の動作原理を示す模式図
【図１０】本発明のデータ探索方法の実施形態を示すフローチャート
【図１１】本発明のデータ探索装置の実施形態を示す機能ブロック図
【図１２】尤度生成手段５の基本構成を示す機能ブロック図
【図１３】比較手段６の基本構成を示す機能ブロック図
【図１４】閾値生成手段７の基本構成を示す機能ブロック図
【図１５】動作決定手段８の論理構造を示す真理値表
【図１６】制御手段１０の動作を示すフローチャート
【図１７】本発明のデータ探索方法の動作規則を示す表
【図１８】本発明のデータ探索方法を示すフローチャート
【図１９】本発明のデータ探索装置の第２の実施形態を示す機能ブロック図
【図２０】動作決定手段１８の論理構造を示す真理値表
【図２１】制御手段２０の動作を示すフローチャート
【符号の説明】
１  横進可能識別信号生成手段
２  標準データ系列記憶手段２
３  ポインタ生成手段
４  枝尤度生成手段
５  尤度生成手段
６  比較手段
７  閾値生成手段
８，１８  動作決定手段
９  レジスタ
１０，２０  制御手段
３１１，３１２，３１３  フリップフロップ
３２２，３２３  排他的論理和回路
５１０，７１０  減算器
５２０，６１０  加算器
６２０，６３０，６４０  比較器
５３０，７３０  セレクタ
７２０  加算器
５４０、７４０  レジスタ
【図１】
0003993392.tif 000002
【図２】
0003993392.tif 000003
【図３】
0003993392.tif 000004
【図４】
0003993392.tif 000005
【図５】
0003993392.tif 000006
【図６】
0003993392.tif 000007
【図７】
0003993392.tif 000008
【図８】
0003993392.tif 000009
【図９】
0003993392.tif 000010
【図１０】
0003993392.tif 000011
【図１１】
0003993392.tif 000012
【図１２】
0003993392.tif 000013
【図１３】
0003993392.tif 000014
【図１４】
0003993392.tif 000015
【図１５】
0003993392.tif 000016
【図１６】
0003993392.tif 000017
【図１７】
0003993392.tif 000018
【図１８】
0003993392.tif 000019
【図１９】
0003993392.tif 000020
【図２０】
0003993392.tif 000021
【図２１】
0003993392.tif 000022