JPH08329244A

JPH08329244A - 最小誤差記憶装置

Info

Publication number: JPH08329244A
Application number: JP7136406A
Authority: JP
Inventors: Hiroyuki Iwahashi; 弘幸岩橋
Original assignee: Sharp Corp
Current assignee: Sharp Corp
Priority date: 1995-06-02
Filing date: 1995-06-02
Publication date: 1996-12-13
Anticipated expiration: 2016-10-09
Also published as: US5953454A; JP3215598B2

Abstract

(57)【要約】【目的】多重ループ制御が不要でアドレス生成が簡単で
あるとともに、同一カテゴリの最小誤差検知も同時に実
行可能とする。【構成】結果記憶メモリ１８から読み出され、第１のレ
ジスタ１２に一時的に保持された読出誤差と、誤差計算
部１１より入力され、第２のレジスタ１３に一時的に保
持された入力誤差とを、第２のセレクタ１５において比
較する。そして、その比較の結果、読出誤差が入力誤差
より小さいときには、読出誤差を結果記憶メモリ１８内
の元の位置に書き込み、読出誤差が入力誤差より大きい
ときには、入力誤差を、読出誤差のあった元の位置に書
き込むとともに、その読出誤差をも含めてそれ以後の読
出誤差を、結果記憶メモリ１８内に順次繰り下げて書き
込む処理を行う。

Description

【発明の詳細な説明】

【産業上の利用分野】本発明は、音声認識や文字認識等
に用いられるパターン認識において、得られた誤差を小
さい順（又は得られた類似度の高い順）に並び替えて記
憶する最小誤差記憶装置に関する。

【０００１】

【従来の技術】音声認識や文字認識等に用いられるパタ
ーン認識では、未知の入力パターンと、未知の入力パタ
ーンと同等の手法で得られた複数個の既知の標準パター
ンとを記憶しておき、これら両パターンに基づく誤差計
算（又は類似度計算）を行い、この計算結果の中から、
誤差の小さい（又は類似度の高い）標準パターンを複数
個だけ採用し、これらを誤差の小さい順（又は類似度の
高い順）に並び替えて結果記憶メモリに記憶させてい
る。そして、この結果記憶メモリに記憶された複数個の
誤差（又は類似度）に基づいて、未知の入力パターンを
特定している。

【０００２】このようなパターン認識では、上述の如
く、結果記憶メモリに類似度の高い順に記憶する場合
と、誤差の小さい順に記憶する場合とがあるが、これら
は表裏一体の関係であることから、ここでは誤差の小さ
い順にＮ個を記憶する場合を例示して説明する。

【０００３】Ｎ個の誤差を小さい順に並び替える方法と
しては、既知の“ソートアルゴリズム”があり、その代
表的な方法で誤差を小さいものから順に並び替える処理
を図１２に示す。

【０００４】誤差を小さい順にＮ個記憶したい場合に
は、結果記憶メモリにはＮ個の記憶領域〔アドレス
（０）からアドレス（Ｎ−１）まで〕が必要となる（ス
テップＳ５１）。そして、このアルゴリズムの実行結果
は、図１３に示す結果記憶メモリのアドレス（０）から
アドレス（Ｎ−１）に記憶されることになる。

【０００５】すなわち、結果記憶メモリの先頭アドレス
（Ｉ＝０）の内容Ａを読み出し、次に、このアドレスに
隣接するアドレス（Ｊ＝Ｉ＋１）を算出し、アドレス
（Ｊ）で示す結果記憶メモリの内容Ｂを読み出す（ステ
ップＳ５２〜Ｓ５４）。

【０００６】そして、両者Ａ，Ｂの大小比較を行い（ス
テップＳ５５）、Ａ＜Ｂの場合には何もせずにステップ
Ｓ５７へと動作を進め、Ａ≧Ｂの場合には、ＡとＢとを
入れ替えて（ステップＳ５６）、ステップＳ５７へと動
作を進める。すなわち、ステップＳ５６では、Ａをアド
レス（Ｊ）で示すメモリの内容とし、Ｂをアドレス
（Ｉ）で示すメモリの内容とする。

【０００７】そして、ステップＳ５７でアドレス（Ｉ）
を更新して、ステップＳ５３からの処理を繰り返すとい
った動作を（Ｎ−１）回行うことにより（ステップＳ５
８）、アドレス（Ｎ−１）には、アドレス（０）からア
ドレス（Ｎ−１）までの中で最大値のものが記憶される
ことになる。

【０００８】この後、結果記憶メモリの処理アドレスを
アドレス（０）からアドレス（Ｎ−２）として、上記と
同様の処理を（Ｎ−２）回行うことにより、アドレス
（Ｎ−２）には、アドレス（０）からアドレス（Ｎ−
２）までの中で最大値のものが記憶されることになる。

【０００９】このような処理を、結果記憶メモリの処理
アドレスがアドレス（０）となるまで繰り返し行い、す
なわち（Ｎ−３）回、（Ｎ−４）回、・・・、１回と順
次行うことにより、記憶結果メモリには、先頭アドレス
（０）からアドレス（Ｎ−１）まで、値の小さい順番に
誤差が記憶されることになる。

【００１０】上記の処理をメモリアクセス回数に注目し
てみると、条件分岐によって変動するが、最短経路で
は、

【００１１】

【数１】最長経路では、

【００１２】

【数２】となる。

【００１３】

【発明が解決しようとする課題】アクセス回数は、処理
時間に影響を与える重要な要素であり、アクセス回数が
少ない程処理時間は短くなるが、上記の処理方法では、
同じアドレスを数回〔アドレス（０）では（Ｎ−１）
回、アドレス（１）では（Ｎ−２）回等〕アクセスする
必要があり、処理時間がかかるといった問題がある。

【００１４】また、上記の処理をハードウエアとして構
成する場合には、隣接するアドレス生成や、多重ループ
制御等が必要となるため、規模が大きくかつ複雑になる
といった問題もある。

【００１５】パターン認識では、標準パターンの数が膨
大であるため、上記のアルゴリズムをそのまま適用する
ことは、現実的でない。そのため、必要な個数に絞り込
む処理が必要となる。

【００１６】つまり、入力パターンと標準パターンとの
誤差計算を行う毎に、記憶されているＮ個の中の最大値
を求め、計算結果がこれより小さい場合は、これを計算
結果と置き換えるわけである。これにより、最小値をも
つＮ個がランダムに記憶されることになる。

【００１７】ところで、パターン認識における最小誤差
記憶（すなわち、値の小さい順番に誤差を記憶）におい
て、もう一つ考慮しなければならない課題がある。それ
は、同一カテゴリの処理である。

【００１８】パターン認識では、同一カテゴリについ
て、複数個の標準パターンを用意しておくのが一般的で
ある。そのため、最小誤差記憶の場合、同一カテゴリに
ついては統合し、図１４に示すように、「カテゴリ内の
最小誤差を、そのカテゴリの代表として採用する」こと
を行っている。

【００１９】つまり、上述した誤差の大小関係に加え、
カテゴリ内での大小関係も考慮する必要がある。そのた
め、カテゴリをも考慮して上記従来の処理方法を採用す
ることは、処理時間がさらに増大するとともに、ハード
ウエア構成についても、さらに規模が大きくかつ複雑な
ものとなるといった問題がある。

【００２０】本発明はこのような問題点を解決すべく創
案されたもので、その目的は、多重ループ制御が不要で
アドレス生成が簡単であるとともに、同一カテゴリの最
小誤差検知も同時に実行できる最小誤差記憶装置を提供
することにある。

【００２１】

【課題を解決するための手段】上記課題を解決するた
め、本発明の請求項１記載の最小誤差記憶装置は、計算
により求められた入力パターンと標準パターンとの誤差
を最小のものから順番に複数個記憶する第１の記憶部
と、この第１の記憶部に記憶された複数個の誤差を小さ
い順に順次読み出す第１の読み出し処理部と、この第１
の読み出し処理部により順次読み出された誤差を一時的
に保持する第１の保持部と、誤差計算部より入力された
誤差を一時的に保持する第２の保持部と、前記第１の保
持部に保持された読出誤差と前記第２の保持部に保持さ
れた入力誤差との比較を行い、読出誤差が入力誤差より
小さいときには読出誤差を前記第１の記憶部内の元の位
置に書き込み、読出誤差が入力誤差より大きいときには
入力誤差を読出誤差のあった元の位置に書き込むととも
に、その読出誤差をも含めてそれ以後の読出誤差を前記
第１の記憶部内に順次繰り下げて書き込む処理を行う第
１の書き込み処理部とを備えた構成とする。

【００２２】また、本発明の請求項２記載の最小誤差記
憶装置は、計算により求められた入力パターンと標準パ
ターンとの誤差を最小のものから順番に複数個記憶する
とともに、この複数個の誤差のそれぞれに対応したカテ
ゴリを誤差に対応付けて記憶する第２の記憶部と、この
第２の記憶部に記憶された複数個の誤差及びカテゴリ
を、誤差の小さい順に順次読み出す第２の読み出し処理
部と、この第２の読み出し処理部により順次読み出され
た誤差及びカテゴリを一時的に保持する第３の保持部
と、誤差計算部より入力された誤差及び対応するカテゴ
リを一時的に保持する第４の保持部と、前記第３の保持
部に保持された読出誤差と前記第４の保持部に保持され
た入力誤差との比較を行い、読出誤差が入力誤差より小
さいときには読出誤差及びカテゴリを前記第２の記憶部
内の元の位置に書き込み、読出誤差が入力誤差より大き
いときには入力誤差及びカテゴリを読出誤差及びカテゴ
リがあった元の位置に書き込むとともに、その読出誤差
及びカテゴリをも含めてそれ以後の読出誤差及びカテゴ
リを前記第２の記憶部内に順次繰り下げて書き込む処理
を行う第２の書き込み処理部と、この第２の書き込み処
理部での処理と並行して前記第３の保持部に保持された
カテゴリと前記第４の保持部に保持されたカテゴリとの
比較を行い、読出誤差が入力誤差より小さいときに両カ
テゴリが一致したときには、その一致したカテゴリ及び
読出誤差を前記第２の記憶部内の元の位置に書き込み処
理し、読出誤差が入力誤差より大きいときに両カテゴリ
が一致したときには、その一致したカテゴリ及び読出誤
差を前記第２の記憶部から削除する処理を、前記第２の
書き込み処理部での処理に優先して行う第３の書き込み
処理部とを備えた構成とする。

【００２３】

【作用】請求項１記載の発明の作用について述べる。

【００２４】第１の読み出し処理部により第１の記憶部
から読み出され、第１の保持部に一時的に保持された読
出誤差と、誤差計算部より入力され、第２の保持部に一
時的に保持された入力誤差とを、第１の書き込み処理部
において比較する。

【００２５】第１の書き込み処理部は、その比較の結
果、読出誤差が入力誤差より小さいときには、読出誤差
を第１の記憶部内の元の位置に書き込み、読出誤差が入
力誤差より大きいときには、入力誤差を読出誤差のあっ
た元の位置に書き込むとともに、その読出誤差をも含め
てそれ以後の読出誤差を、第１の記憶部内に順次繰り下
げて書き込む処理を行う。

【００２６】すなわち、図５に示す例で言えば、入力誤
差である入力（１７）が、第１の記憶部内のアドレス
（３）に書き込まれ、アドレス（３）に書き込まれてい
た誤差（２０）は、一つ繰り下がったアドレス（４）
に、アドレス（４）に書き込まれていた誤差（２０）
は、一つ繰り下がったアドレス（５）にと、順次繰り下
がって書き込まれる。

【００２７】つまり、計算結果を割り込ませることで、
それまで実行されて記憶されている結果を活用できる利
点がある。

【００２８】請求項２記載の発明の作用について述べ
る。

【００２９】第２の読み出し処理部により第２の記憶部
から読み出され、第３の保持部に一時的に保持された読
出誤差及びカテゴリと、誤差計算部より入力され、第４
の保持部に一時的に保持された入力誤差及びカテゴリと
のうち、読出誤差と入力誤差とを第２の書き込み処理部
において比較する。そして、第２の書き込み処理部で
は、請求項１に記載した第１の書き込み処理部と同様の
処理を行う。

【００３０】一方、第３の書き込み処理部は、第２の書
き込み処理部での処理と並行し、かつ第２の書き込み処
理部での処理に優先して、次の処理を実行する。

【００３１】すなわち、第３の保持部に保持されたカテ
ゴリと、第４の保持部に保持されたカテゴリとの比較を
行い、読出誤差が入力誤差より小さいときに両カテゴリ
が一致したときには、その一致したカテゴリ及び読出誤
差を、第２の記憶部内の元の位置に書き込み処理し、読
出誤差が入力誤差より大きいときに両カテゴリが一致し
たときには、その一致したカテゴリ及び入力誤差を、第
２の記憶部から削除する処理を行う。

【００３２】つまり、図９に示す例で言えば、同図
（ｃ），（ｄ）に示すように、第３の保持部に保持され
たアドレス（８）の読出誤差及びカテゴリ（８０，９
０）と、第４の保持部に保持された入力誤差及びカテゴ
リ（２６，９０）との比較では、読出誤差（８０）が入
力誤差（２６）より大きいときに両カテゴリが一致する
ことから、このときにはその一致したカテゴリ（９０）
及び入力誤差（８０）のアドレス（８）の内容を削除す
る処理を行う、また、同図（ｅ），（ｆ）に示すよう
に、第３の保持部に保持されたアドレス（１）の読出誤
差及びカテゴリ（１０，９０）と、第４の保持部に保持
された入力誤差及びカテゴリ（１８，９０）との比較で
は、読出誤差（１０）が入力誤差（１８）より小さいと
きに両カテゴリが一致することから、このときにはその
一致したカテゴリ（９０）及び入力誤差（１０）を元の
アドレス（１）の位置に書き込み処理する。すなわち、
この場合はソートされない。

【００３３】つまり、計算結果を割り込ませることで、
それまで実行されて記憶されている結果を活用しつつ、
同一カテゴリの処理も同時に行える利点がある。

【００３４】

【実施例】以下、本発明の一実施例を図面を参照して説
明する。

【００３５】図１は、本発明の最小誤差記憶装置の電気
的構成を示すブロック図であり、請求項１に対応してい
る。

【００３６】すなわち、誤差計算部１１、第１のレジス
タ１２、第２のレジスタ１３、第１のセレクタ１４、第
２のセレクタ１５、コンパレータ１６、バッファ１７、
結果記憶メモリ１８及び制御部１９によって構成されて
いる。また、図２は、本発明の最小誤差記憶装置の他の
実施例を示しており、図１に示す結果記憶メモリ１８を
シフトレジスタ又はＦｉＦｏ（ファースト・イン・ファ
ースト・アウト）を用いて構成したものである。両者の
違いは、結果記憶にメモリを用いるか、シフトレジスタ
を用いるかであり、最小誤差記憶の原理自体は同じもの
である。

【００３７】図２に示す回路構成では、アドレス生成が
不要であるため、回路規模を更に軽減できる利点があ
る。また、図１及び図２に示す結果記憶メモリ１８は、
所望するＮ個の結果に見合う記憶容量が必要であり、初
期値として無限大、回路では最大値を与えておく。記憶
個数が少ない場合には、図２に示す回路構成の方が有利
である。

【００３８】また、各図には示されていないが、結果記
憶メモリ１８は、外部回路例えばＣＰＵ等に接続されて
おり、結果記憶メモリ１８の初期化や結果の読み出し
は、これら外部回路で行うものとする。

【００３９】第１のレジスタ１２は、結果記憶メモリ１
８から読み出した内容Ｂを保持するレジスタである。第
２のレジスタ１３は、誤差計算部１１からの入力Ａ又は
第１のレジスタ１２の内容Ｂのいずれかを保持するレジ
スタである。

【００４０】また、第１のセレクタ１４は、第２のレジ
スタ１３に、誤差計算部１１からの入力Ａを保持させる
か、第１のレジスタ１２の内容Ｂを保持させるかの選択
を行う選択回路であり、制御部１９からの切替信号Ｓ１
は、実行時はＢ側を、そうでない場合はＡ側を選択する
切替信号となっている。

【００４１】また、第２のセレクタ１５は、第１のレジ
スタ１２の内容Ｂ又は第２のレジスタ１３の内容Ａのい
ずれかを書き込むための選択回路であり、コンパレータ
１６からの切替信号Ｓ２は、コンパレータ１６の出力結
果により、Ａ＜Ｂの場合はＡ側を、Ａ≧Ｂの場合はＢ側
を選択する切替信号となっている。

【００４２】コンパレータ１６は、第１のレジスタ１２
の内容Ｂと、第２のレジスタ１３の内容Ａとを比較する
回路である。

【００４３】バッファ１７は、読み込み時には結果記憶
メモリ１８の内容Ｂが第１のレジスタ１２に入力される
ように、書き込み時には第２のセレクタ１５の出力Ｙが
結果記憶メモリ１８に入力されるように制御する回路で
ある。

【００４４】制御部１９は、結果記憶メモリ１８のアド
レス生成、メモリの読み出し／書き込み、ループ制御、
各レジスタ１２，１３への保持信号発生、バッファ制御
等を行う回路である。

【００４５】なお、誤差計算部１１自体の構成について
は、本発明の範囲外であり、また従来より行われている
ものであるので、ここでは説明を省略する。

【００４６】すなわち、本発明の最小誤差記憶装置によ
れば、ハードウエア構成は、誤差計算部１１からの誤差
と、結果記憶メモリ１８から読み出した結果（誤差）と
を保持する第１及び第２のレジスタ１２，１３、両誤差
の大小関係を判定するコンパレータ１６、第１及び第２
のレジスタ１２，１３のどちらの内容を書き込むかを選
択する第１及び第２のセレクタ１４，１５といったシン
プルな構成となっている。また、図２では、結果記憶メ
モリ１８をシフトレジスタで構成しているため、Ｂから
Ａへの入れ替えが容易に行える。

【００４７】次に、上記構成の最小誤差記憶装置の動作
について、図３に示すフローチャート、図４に示す処理
図を適宜参照して説明する。

【００４８】入力パターンと辞書（標準パターン）との
誤差を計算し、この計算した誤差を逐次並び替えて記憶
していくことにより、結果記憶メモリ１８の内容は、

【００４９】

【数３】Ｍ（０）≦Ｍ（１）≦Ｍ（２）≦・・・≦Ｍ
（Ｉ）≦・・・≦Ｍ（Ｎ−１）ただし、Ｉ＝０，１，２，・・・，Ｎ−１Ｍ（Ｉ）：アドレスＩのメモリ内容の関係が成立しているはずである。

【００５０】この関係を利用するとき、メモリ内容をア
ドレス（０）から順次読み出していき、計算された誤差
がメモリの内容より小さくなったアドレス（Ｉ）へ入力
誤差を割り込ませ、それ以降についてはアドレス（Ｉ）
の内容をアドレス（Ｉ＋１）へ移動していくことで、ソ
ート動作が可能であることがわかる。

【００５１】そこで、ここでは上記のようにして、最小
誤差Ｎ個が結果記憶メモリ１８のアドレス（１），
（２），・・・，（Ｎ−１）に小さい順に記憶されてお
り、誤差計算部１１によって計算された誤差Ａが、第２
のレジスタ１３に保持されているものとして、本実施例
の動作を説明する。

【００５２】すなわち、結果記憶メモリ１８のアドレス
（Ｉ＝０）の内容Ｂを読み出して第１のレジスタ１２に
保持し（ステップＳ１，Ｓ２）、各レジスタ１２，１３
に保持された内容Ａ，Ｂの大小比較を行う（ステップＳ
３）。

【００５３】そして、Ａ＜Ｂの場合には、Ａをアドレス
（Ｉ）の内容とし、その後ＢをＡに置き換える（ステッ
プＳ４）。また、Ａ≧Ｂの場合には、Ｂを読み込んだ元
のアドレス（Ｉ）に戻す（ステップＳ５）。

【００５４】そして、ステップＳ６でアドレス（Ｉ）を
更新して、ステップＳ２からの処理を繰り返すといった
動作をＮ回行うことにより（ステップＳ７）、結果記憶
メモリ１８には、最小値順に並び替えられた誤差がアド
レス（０）からアドレス（Ｎ−１）に記憶されることに
なる。

【００５５】本実施例によれば、メモリアクセス回数
は、条件分岐に依存せず、対象となるアドレス（Ｉ）に
ついて、読み込み／書き込みが各１回行われるだけであ
る。すなわち、Ｔ＝２・Ｎである。つまり、上記した従
来の処理方法よりもメモリアクセス回数が軽減されてい
るので、その分高速な処理が可能となる。

【００５６】また、図４及び図５からも分かるように、
隣接するアドレスの生成や多重ループ制御も不要である
ので、ハードウエアとして実現する場合の回路規模も簡
素化できることが分かる。

【００５７】ここで、結果記憶メモリ１８の記憶個数が
１０（Ｎ＝１０）の場合の実施例について、図５に示す
動作概念図及び図６に示す動作過程の一覧表を適宜参照
して説明する。ただし、図５において（ａ）が実行前の
結果記憶メモリ１８の内容、（ｂ）が実行後の結果記憶
メモリ１８の内容である。

【００５８】処理の実行前に、誤差計算部１１の計算結
果として、現時点の入力誤差（１７）が第２のレジスタ
１３に記憶されているものとする。

【００５９】この条件で上記の処理を実行した結果、図
５及び図６に示す実施例では、入力誤差である入力（１
７）が、結果記憶メモリ１８のアドレス（３）に書き込
まれ（図５及び図６において符号２１により示す）、ア
ドレス（３）に書き込まれていた誤差（２０）は、一つ
繰り下がったアドレス（４）に、アドレス（４）に書き
込まれていた誤差（２０）は、一つ繰り下がったアドレ
ス（５）にと、順次繰り下がって書き込まれ、実行前の
最後のアドレス（９）に書き込まれていた誤差（９０）
が除外されることになる。

【００６０】つまり、メモリの内容が入力値（入力誤
差）より小さい場合はメモリの内容がそのまま残り、メ
モリの内容が入力値（入力誤差）より大きくなった時点
で、その入力値がメモリに取り込まれ、その後のメモリ
の内容がシフトされ、最大値が除外されることになる。

【００６１】ここで、標準パターン数をＰ、最小誤差と
して記憶する個数をＮとして、実際の最小誤差の記憶に
要するメモリのアクセス回数を算出する。

【００６２】本発明では、アクセス回数Ｔ１は、

【００６３】

【数４】Ｔ１＝Ｐ＋２・Ｐ′・Ｎであるのに対して、既知のソートアルゴリズムを使って
最小誤差を記憶する方法では、アクセス回数Ｔ２は、

【００６４】

【数５】Ｔ２＝Ｐ・（Ｎ＋１）＋Ｎ・（Ｎ−１）となる。

【００６５】算出式の前項は、標準パターンの中でＮ位
以内に入っているかを判断するメモリアクセスであり、
後の項は、Ｎ個の並び替えに必要なメモリアクセス回数
である。Ｎ位以内に入っているかどうかを判断するに
は、本発明では常に決められたメモリアドレスに最大値
が記憶されているため、各標準パターンについて１回行
うだけでよいが、既知のソートアルゴリズムを使った場
合には、Ｎ個の最小誤差がランダムに記憶されているこ
とから、この記憶されているＮ個の中から最大値を検出
し、それと入れ替えることが必要である。

【００６６】実際に最小誤差の対象となるパターン数
Ｐ′は、

【００６７】

【数６】２・Ｐ′・Ｎ＝Ｐ・（Ｎ＋１）＋Ｎ・（Ｎ−１）−Ｐより、

【００６８】

【数７】Ｐ′≦（Ｐ＋Ｎ−１）／２である。すなわち、標準パターン数の半分以下が実際の
最小誤差記憶の対象になれば、本発明の方がメモリアク
セス回数を少なくすることができる。

【００６９】また、本実施例では、結果記憶メモリ１８
をシフトレジスタ形式として構成できる利点がある。シ
フトレジスタで構成した場合には、通常のメモリアクセ
ス速度に比べて半分以下の速度でよく、処理時間を等価
的に速くすることが可能である。

【００７０】次に、同一カテゴリを考慮した場合の処理
について説明する。

【００７１】図７は、本発明の最小誤差記憶装置の電気
的構成を示すブロック図であり、請求項２に対応してい
る。

【００７２】すなわち、誤差計算部１１、第１のレジス
タ１２、第２のレジスタ１３、第１のセレクタ１４、第
２のセレクタ１５、コンパレータ１６、バッファ１７、
制御部１９を備えており、これらの構成は図１及び図２
に示したものと同様であるので、ここでは説明を省略す
る。

【００７３】本実施例では、上記構成の他に、第３のレ
ジスタ３２、第４のレジスタ３３、第２のコンパレータ
３４、第３のコンパレータ３５、第３のセレクタ３６、
第４のセレクタ３７、第５のセレクタ３８、第６のセレ
クタ３９、制御部４０、切替制御部４１及び結果記憶メ
モリ４２を備えた構成となっている。

【００７４】第３のレジスタ３２は、結果記憶メモリ４
２から読み出したカテゴリＤを保持するレジスタであ
る。第４のレジスタ３３は、誤差計算部１１からの入力
ｃ又は第３のレジスタ３２の内容Ｄのいずれかを保持す
るレジスタである。

【００７５】第３のセレクタ３６は、第３のレジスタ３
２のカテゴリＤ又は入力カテゴリｃのいずれかを書き込
むための選択回路であり、切替信号Ｓ１は、実行時には
Ｄ側を、そうでない場合はｃ側を選択する切替信号とな
っている。

【００７６】第２のコンパレータ３４は、入力カテゴリ
ｃと第４のレジスタ３３のカテゴリＣとの一致を判定す
る。第３のコンパレータ３５は、入力カテゴリｃと第３
のレジスタ３２のカテゴリＤとの一致を判定する。

【００７７】第４のセレクタ３７は、各コンパレータ３
４，３５の判定結果を選択するものであり、切替信号Ｓ
２は、第１のコンパレータ１６の出力Ａ＜Ｂ、第４のセ
レクタ３７の出力ＴＦ及び第３のコンパレータ３５の出
力Ｄ＝ｃの組み合わせによって決定される。

【００７８】第５のセレクタ３８は、第３のレジスタ３
２の内容Ｄ又は第４のレジスタ３３の内容Ｃのいずれか
を書き込むための選択回路であり、切替信号Ｓ２は、第
４のセレクタ３７の出力ＴＦによって切り替えられる。

【００７９】第６のセレクタ３９は、第５のセレクタ３
８の出力であるカテゴリを書き込むか、第２のセレクタ
１５の出力である誤差を書き込むかを決める選択回路で
ある。

【００８０】結果記憶メモリ４２は、誤差を記憶する領
域ＭＧと、カテゴリを記憶する領域ＭＣとを独立させて
いるが、連続したメモリ空間に配置して、≪誤差≫、≪
カテゴリ≫、・・・といった記憶形式としても、時分割
処理で行えば問題はない。

【００８１】次に、上記構成の最小誤差記憶装置の動作
について、図８に示すフローチャートを適宜参照して説
明する。ただし、最小誤差順に並び替える処理は、図３
乃至図６に示した処理と同様であるので、ここでは説明
を省略し、同一カテゴリの処理についてのみ説明を行う
ものとする。

【００８２】本実施例においては、請求項１に対応した
上記実施例での処理と同様にして、最小誤差Ｎ個が対応
するカテゴリと共に、結果記憶メモリ４２のアドレス
（１），（２），・・・，（Ｎ−１）に誤差の小さい順
に記憶されており、誤差計算部１１によって計算された
誤差Ａが第２のレジスタ１３に、対応するカテゴリＣが
第４のレジスタ３３にそれぞれ保持されているものとす
る（ステップＳ１１）。また、図８に用いているＲＦ、
ＴＦ、ＷＦはカテゴリに対応するためのフラグであり、
実行前にクリアされているが（ステップＳ１２）、次の
条件で有効（＝１）となる。

【００８３】すなわち、結果記憶メモリ４２から読み出
したカテゴリ（以下、読出カテゴリという）と、誤差計
算部１１より入力されたカテゴリ（以下、入力カテゴリ
という）とが同じときＲＦ＝１、ソート実行中に入力カ
テゴリと同じカテゴリを書き込んだときＷＦ＝１、結果
記憶メモリ４２に書き込もうとするカテゴリが入力カテ
ゴリと同じときＴＦ＝１となる。

【００８４】上記条件において、次に結果記憶メモリ４
２のアドレス（Ｉ＝０）の内容を読み出し、そのうちの
読出誤差Ｂを第１のレジスタ１２に、読出カテゴリＤを
第３のレジスタ３２にそれぞれ保持させる（ステップＳ
１３，Ｓ１４）。そして、読出カテゴリＤが入力カテゴ
リＣと同じ場合には、ＲＦを有効（＝１）とし（ステッ
プＳ１６、同じでない場合にはＲＦを無効（＝０）とし
て（ステップＳ１７）、ステップＳ１８への処理へと進
む。

【００８５】ステップＳ１８では、各レジスタ１２，１
３に保持された内容Ａ，Ｂの大小比較を行う。そして、
Ａ＜Ｂであって、Ａに対するカテゴリが入力カテゴリＣ
と同じである場合には（ステップＳ１８，Ｓ２４）、Ｔ
Ｆを有効（＝１）とし（ステップＳ２５）、Ａをアドレ
ス（Ｉ）のＭＧ領域の内容とし、その後ＢをＡに置き換
える（ステップＳ２６）。また、Ｃをアドレス（Ｉ）の
ＭＣ領域の内容とし、その後ＤをＣに置き換えて（ステ
ップＳ２７）、ステップＳ３２へと動作を進める。

【００８６】また、Ａ≧Ｂであって、ＲＦ、ＷＦのいず
れかが無効（＝０）である場合には（ステップＳ１８，
Ｓ１９，Ｓ２０）、ステップＳ２８へと動作を進める。
そして、ステップＳ２８において、Ｂに対するカテゴリ
が入力カテゴリＣと同じである場合には、ＴＦを有効
（＝１）とし（ステップＳ２９）、Ｂをアドレス（Ｉ）
のＭＧ領域の内容とし（ステップＳ３０）、Ｄをアドレ
ス（Ｉ）のＭＣ領域の内容として（ステップＳ３１）、
ステップＳ３２へと動作を進める。

【００８７】また、Ａ≧Ｂであって、ＲＦ、ＷＦの両方
が有効（＝１）である場合には（ステップＳ１８，Ｓ１
９，Ｓ２０）、ステップＳ２１へと動作を進めて、ＴＦ
を有効（＝１）とする。ここで、本来はＢをアドレス
（Ｉ）に戻すところであるが、すでに同一カテゴリが存
在しているので、Ｂは書き込むことができない。

【００８８】そこで、Ａをアドレス（Ｉ）のＭＧ領域の
内容とし、その後ＢをＡに置き換える（ステップＳ２
２）。また、Ｃをアドレス（Ｉ）のＭＣ領域の内容と
し、その後ＤをＣに置き換えて（ステップＳ２３）、ス
テップＳ３２へと動作を進める。

【００８９】そして、ステップＳ３２において、ＲＦが
有効（＝１）であった場合には、そのカテゴリを除外す
るため、Ａを最大値とする（ステップＳ３３）。そし
て、同一カテゴリを書き込んだ場合には、ＷＦを有効
（＝１）とする（ステップＳ３４）。

【００９０】そして、ステップＳ３５でアドレス（Ｉ）
を更新して、ステップＳ１４からの処理を繰り返すとい
った動作をＮ回行うことにより（ステップＳ３６）、結
果記憶メモリ４２には、最小値順に並び替えられた誤差
が、そのときのカテゴリの対応付けもなされた状態で、
アドレス（０）からアドレス（Ｎ−１）に記憶されるこ
とになる。

【００９１】次に、結果記憶メモリ４２の記憶個数が、
誤差及びカテゴリのそれぞれについて１０（Ｎ＝１０）
の場合の実施例について、図９に示す動作概念図及び図
１０及び図１１にそれぞれ示す動作過程の一覧表を適宜
参照して説明する。

【００９２】ただし、図９において、入力（誤差：０
０、カテゴリ００）に対する実行前の結果記憶メモリ４
２の内容を同図（ａ）、実行後の結果記憶メモリ４２の
内容を同図（ｂ）に示しており、入力（誤差：２６、カ
テゴリ９０）に対する実行前の結果記憶メモリ４２の内
容を同図（ｃ）、実行後の結果記憶メモリ４２の内容を
同図（ｄ）に示しており、入力（誤差：１８、カテゴリ
９０）に対する実行前の結果記憶メモリ４２の内容を同
図（ｅ）、実行後の結果記憶メモリ４２の内容を同図
（ｆ）に示している。

【００９３】すなわち、（ａ）、（ｂ）は１番目の例で
ある初期状態での動作を示しており、（ｃ），（ｄ）は
２番目の例を示しており、（ｅ）、（ｆ）は３番目の例
を示している。また、図１０は、図９（ｃ）、（ｄ）に
対応した一覧表であり、図１１は図９（ｅ）、（ｆ）に
対応した一覧表である。

【００９４】１番目の例では、アドレス（１）に入力誤
差（００）と、そのときの入力カテゴリ（００）とが書
き込まれている。

【００９５】２番目の例では、入力カテゴリ（９０）と
同じカテゴリ（９０）が結果記憶メモリ４２のアドレス
（８）にも書き込まれており、そのときの誤差（８０）
が入力誤差２６よりも大きい場合である。

【００９６】この場合には、誤差（８０）が入力誤差
（２６）より大きいときに両カテゴリが一致することか
ら、このときにはその一致したカテゴリ（９０）及び誤
差（８０）をアドレス（８）の内容から削除する処理を
行う。

【００９７】これにより、結果記憶メモリ４２に記憶さ
れていたアドレス（８）の同一カテゴリ（９０）の内容
が削除され、かつ結果記憶メモリ４２には、小さい順に
誤差が記憶されていることになる。

【００９８】３番目の例では、入力カテゴリ（９０）と
同じカテゴリ（９０）が結果記憶メモリ４２のアドレス
（１）にも書き込まれており、そのときの誤差（１０）
が入力誤差１８よりも小さい場合である。

【００９９】この場合には、誤差（１０）が入力誤差
（１８）より小さいときに両カテゴリが一致することか
ら、このときにはその一致したカテゴリ（９０）及び誤
差（１０）を元のアドレス（１）の位置に書き込み処理
する。すなわち、この場合はソートされないようになっ
ている。

【０１００】以上述べてきた各実施例は、誤差に着目し
て、誤差を小さい順に並べ替える場合について説明して
いるが、類似度に着目して、類似度の高い順に並べ替え
る場合も同様に行うことが可能である。この場合、図３
では大小関係の判定条件を入れ替え、図８でも大小関係
の判定条件を入れ替え、Ａ＝０とすることで対応でき
る。この場合の初期値は０とする。

【０１０１】

【発明の効果】本発明の請求項１記載の最小誤差記憶装
置によれば、第１の読み出し処理部により第１の記憶部
から読み出され、第１の保持部に一時的に保持された読
出誤差と、誤差計算部より入力され、第２の保持部に一
時的に保持された入力誤差とを、第１の書き込み処理部
において比較する。第１の書き込み処理部は、その比較
の結果、読出誤差が入力誤差より小さいときには、読出
誤差を第１の記憶部内の元の位置に書き込み、読出誤差
が入力誤差より大きいときには、入力誤差を読出誤差の
あった元の位置に書き込むとともに、その読出誤差をも
含めてそれ以後の読出誤差を、第１の記憶部内に順次繰
り下げて書き込む処理を行うように構成したので、多重
ループ制御が不要でアドレス生成が簡単であるため、小
規模の回路構成で制御の容易な最小誤差記憶装置が実現
できる。

【０１０２】また、本発明の請求項１記載の最小誤差記
憶装置は、第２の書き込み処理部での処理と並行し、か
つ第２の書き込み処理部での処理に優先して、第３の保
持部に保持されたカテゴリと、第４の保持部に保持され
たカテゴリとの比較を行い、読出誤差が入力誤差より小
さいときに両カテゴリが一致したときには、その一致し
たカテゴリ及び読出誤差を、第２の記憶部内の元の位置
に書き込み処理し、読出誤差が入力誤差より大きいとき
に両カテゴリが一致したときには、その一致したカテゴ
リ及び入力誤差を、第２の記憶部から削除する処理を行
うように構成したので、多重ループ制御が不要でアドレ
ス生成が簡単であり、かつ同一カテゴリの最小誤差検知
も同時に実行できる、小規模の回路構成で制御の容易な
最小誤差記憶装置が実現できる。

【図面の簡単な説明】

【図１】本発明の最小誤差記憶装置の電気的構成を示す
ブロック図であり、請求項１に対応している。

【図２】本発明の最小誤差記憶装置の他の実施例を示す
ブロック図であり、請求項１に対応している。

【図３】請求項１に対応した最小誤差記憶装置の動作を
説明するフローチャートである。

【図４】請求項１に対応した最小誤差記憶装置の動作処
理図である。

【図５】請求項１に対応した最小誤差記憶装置の動作概
念図である。

【図６】図５に示した動作概念図に対応した動作過程の
一覧表である。

【図７】本発明の最小誤差記憶装置の電気的構成を示す
ブロック図であり、請求項２に対応している。

【図８】請求項２に対応した最小誤差記憶装置の動作を
説明するフローチャートである。

【図９】請求項２に対応した最小誤差記憶装置の動作概
念図である。

【図１０】図９（ｃ）、（ｄ）に示した動作概念図に対
応した動作過程の一覧表である。

【図１１】図９（ｅ）、（ｆ）に示した動作概念図に対
応した動作過程の一覧表である。

【図１２】従来の方法で誤差を小さいものから順に並び
替える処理動作を説明するフローチャートである。

【図１３】従来のメモリアクセス回数を説明するための
図である。

【図１４】同一カテゴリを考慮した誤差の並び替えを説
明するための図である。

【符号の説明】

１１誤差計算部１２第１のレジスタ１３第２のレジスタ１４第１のセレクタ１５第２のセレクタ１６コンパレータ１７バッファ１８，４２結果記憶メモリ１９，４０制御部３２第３のレジスタ３３第４のレジスタ３４第２のコンパレータ３５第３のコンパレータ３６第３のセレクタ３７第４のセレクタ３８第５のセレクタ３９第６のセレクタ４１切替制御部４１

Claims

【特許請求の範囲】

【請求項１】計算により求められた入力パターンと標
準パターンとの誤差を最小のものから順番に複数個記憶
する第１の記憶部と、この第１の記憶部に記憶された複数個の誤差を小さい順
に順次読み出す第１の読み出し処理部と、この第１の読み出し処理部により順次読み出された誤差
を一時的に保持する第１の保持部と、誤差計算部より入力された誤差を一時的に保持する第２
の保持部と、前記第１の保持部に保持された読出誤差と前記第２の保
持部に保持された入力誤差との比較を行い、読出誤差が
入力誤差より小さいときには読出誤差を前記第１の記憶
部内の元の位置に書き込み、読出誤差が入力誤差より大
きいときには入力誤差を読出誤差のあった元の位置に書
き込むとともに、その読出誤差をも含めてそれ以後の読
出誤差を前記第１の記憶部内に順次繰り下げて書き込む
処理を行う第１の書き込み処理部とを備えたことを特徴
とする最小誤差記憶装置。
【請求項２】計算により求められた入力パターンと標
準パターンとの誤差を最小のものから順番に複数個記憶
するとともに、この複数個の誤差のそれぞれに対応した
カテゴリを誤差に対応付けて記憶する第２の記憶部と、この第２の記憶部に記憶された複数個の誤差及びカテゴ
リを、誤差の小さい順に順次読み出す第２の読み出し処
理部と、この第２の読み出し処理部により順次読み出された誤差
及びカテゴリを一時的に保持する第３の保持部と、誤差計算部より入力された誤差及び対応するカテゴリを
一時的に保持する第４の保持部と、前記第３の保持部に保持された読出誤差と前記第４の保
持部に保持された入力誤差との比較を行い、読出誤差が
入力誤差より小さいときには読出誤差及びカテゴリを前
記第２の記憶部内の元の位置に書き込み、読出誤差が入
力誤差より大きいときには入力誤差及びカテゴリを読出
誤差及びカテゴリがあった元の位置に書き込むととも
に、その読出誤差及びカテゴリをも含めてそれ以後の読
出誤差及びカテゴリを前記第２の記憶部内に順次繰り下
げて書き込む処理を行う第２の書き込み処理部と、この第２の書き込み処理部での処理と並行して前記第３
の保持部に保持されたカテゴリと前記第４の保持部に保
持されたカテゴリとの比較を行い、読出誤差が入力誤差
より小さいときに両カテゴリが一致したときには、その
一致したカテゴリ及び読出誤差を前記第２の記憶部内の
元の位置に書き込み処理し、読出誤差が入力誤差より大
きいときに両カテゴリが一致したときには、その一致し
たカテゴリ及び読出誤差を前記第２の記憶部から削除す
る処理を、前記第２の書き込み処理部での処理に優先し
て行う第３の書き込み処理部とを備えたことを特徴とす
る最小誤差記憶装置。