JPH0315209B2 - - Google Patents
Info
- Publication number
- JPH0315209B2 JPH0315209B2 JP58202291A JP20229183A JPH0315209B2 JP H0315209 B2 JPH0315209 B2 JP H0315209B2 JP 58202291 A JP58202291 A JP 58202291A JP 20229183 A JP20229183 A JP 20229183A JP H0315209 B2 JPH0315209 B2 JP H0315209B2
- Authority
- JP
- Japan
- Prior art keywords
- data
- circuit
- binary data
- output
- input
- 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.)
- Expired - Lifetime
Links
Landscapes
- Complex Calculations (AREA)
- Character Discrimination (AREA)
Description
(1) 発明の技術分野
本発明は、特に２つのデータ群の相違度を、両
データ群における各データの差の絶対値の累積和
として計算する装置に関する。 (2) 技術の背景 一般に音声認識或いは画像認識では、入力する
音声パターンや画像パターンを予め定めた複数の
標準パターンと比較し、これら標準パターンのう
ち該入力パターンとの相違が一番小さいものを認
識パターンとするようにしている。そして、この
入力パターンと標準パターンとの相違の尺度とし
て、例ば、多数次元での特徴抽出によつ複数のデ
ータからなる（多次元）入力パターンと同次元の
データからなる予め定めた標準パターンとにおけ
る対応する次元の各データ値の差の絶対値を順次
加算した累積和を用いることができる。すなわ
ち、当該累積和が大きければ、入力パターン、標
準パターンの相違は大きく、当該累積和が小さけ
ればその相違が小さいものとなる。 そこで、音声認識或いは画像認識では、その入
力パターンと標準パターンの両データ群の相違を
上記のような累積和として計算する相違度計算装
置が必要となり、更に当該累積和をできるだけ高
速に計算できる装置が要望されている。 (3) 従来技術と問題点 従来、この種の相違度計算装置として例えば第
１図に示すようなものが考えられる。ここで、対
象となる２つのデータ群Ａ＝｛Ai｝、 Ｂ＝｛Bi｝を構成する２進データは、正又は負
の値であり、その表現は、演算処理に便利なよう
に、例えばｎ＋１ビツト表現のものであれば、 Ai＝−ao・2n＋A′ A′＝＋ao-1・2n-1＋ao-2・2n-2＋ ……＋a121＋a020 ao〜a0：０又は１ で示される数値となる、いわゆる２の補数表現さ
れたものとなつている（Biについても同様）。 第１図において、１は上記のように２の補数表
現されたデータ群Ａ、及びＢの対応する次元のデ
ータAiとBiとの大小を判定する比較回路、２は上
記データAi，Biを入力し、比較回路１での判定結
果に基づいて、データAi，Biのうち大きい方を選
択出力するマルチプレクサ、３は上記データAi，
Biを反転回路７ａ，７ｂによつて反転させた当該
反転データ（１の補数）を入力し、比較回路１で
の判定結果に基づいて、データAi，Biのうち小さ
い方の反転データを選択出力するマルチプレク
サ、４はマルチプレクサ２、及び３からの各出力
データとビツトデータ“１”とを加算する加算回
路であり、この比較回路１、マルチプレクサ２，
３、及び加算回路４によつて、入力するデータ
Ai，Biの大きい方から小さい方を減算する減算回
路が構成され、すなわち、最終段の加算回路４か
らの出力がデータAiとBiの差の絶対値｜Ai−Bi｜
となる。そして、データ群Ａ、及びＢからのデー
タが入力する毎に加算回路４から出力される上記
絶対値｜Ai−Bi｜を、加算回路５によつて、レジ
スタ６に格納されている前回までの加算結果と加
算して、この加算結果を再度レジスタ６に格納す
るようにし、レジスタ６の最終格納データが、上
記データ群Ａ，Ｂにおける対応する次元の各デー
タの差の絶対値の累積和Σ｜Ai−Bi｜、すなわち
データ群Ａ，Ｂの相違度となるようにしている。 このように、データ群Ａ、及びＢから順次入力
するデータAi，Biの大小を判定し、その大きい方
から小さい方を減算した結果を順次累積加算する
ようにした上記相違度計算装置は、ハードウエア
で構成することにより、比較的高速な処理が実現
できるようになる。 しかしながら、この第１図に示すような相違度
計算装置では、データAi，Biの大小を判定する比
較回路１と、この比較回路１の判定結果に基づい
てデータ選択を行なうマルチプレクサ２、及び３
が必要なため、回路構成が比較的複雑になるとい
う不具合がある。 (4) 発明の目的 本発明は上記の点に鑑みてなされたもので、特
に２の補数表現された２進データからなる２つの
データ群における互いに対応した各データの差の
絶対値の累積和を計算する相違度計算装置をでき
るだけ簡単な回路構成で実現することを目的とし
ている。 (5) 発明の構成 上記目的を達成するため本発明は、負の数のみ
が２の補数表現された２つの２進データの差の絶
対値を計算する装置であつて、 前記２進データのうちの一方の２進データと、
他方の２進データの反転データとを加算する加算
回路と、前記２つの２進データの符号ビツトと前
記加算回路から出力される最上位桁上がりビツト
とが入力され、当該ビツトデータの排他的論理和
により前記２つの２進データの大、小を判定する
判定回路と、前記加算回路からの最上位桁上がり
ビツト以外の出力２進データを、前記一方の２進
データが前記他方の２進データより大なるとき
は、そのまま出力し、前記一方の２進データが前
記他方の２進データ以下であるときは、反転した
後、“１”を加算して出力する回路とを備えるよ
うにししたものである。 (5) 発明の実施例 まず、本発明において行なわれる負の数のみが
２の補数表現された２つの２進データの差の絶対
値を求める計算について、基本的な論理を説明す
る。 例えば、ｎ＋１ビツトで負の数のみが２の補数
表現された２つの２進データＸ及びＹの符号ビツ
ト（最上位ビツト）をそれぞれXo，yoとし、残
りのｎビツトで表現される部分をそれX′，Y′と
すると、各データＸ，Ｙは Ｘ＝−xo・2n＋X′ Ｙ＝−yo・2n＋Y′ で示される数値となるが、２進演算の過程におい
ては符号ビツトと他のビツトは同様の取扱いとな
るので、 Ｘ＝xo・2n＋X′ Ｙ＝yo・2n＋Y′ となる。 ここで、データＸとデータＹの反転データ（１
の補数）とを加算した加算データＳを考ると、 Ｓ＝Ｘ＋ ＝（xo・2n＋X′） ＋（o・2n＋′） ＝（Xo＋o）・2n ＋（X′＋′） ……(1) となる。 この演算においてｎ＋１（符号）ビツト目から
の桁上がりをCo+1、ｎビツト目からの桁上がりを
をCoとすると、 １ xo＝０、yo＝１のとき、 すなわち、Ｘ０＞Ｙのとき、 xo＋o＝０であるから Co+1＝０ となる。 ２ xo＝１、yo＝０のとき、 すなわち、Ｘ＜０Ｙのとき、 xo＋o＝10（２進値）であるから、 Co+1＝１ となる。 ３ Xo＝０、yo＝０又はxo＝１、 yo＝１のとき、上記加算データＳは、 xo＋o＝１であるから、 Ｓ＝2n＋（X′＋′） となり、Y′がｎビツト表現であるから ′＝2n−１−Y′ となつて Ｓ＝2n+1−１＋（X′−Y′） となる。 ３−１ ここで、Ｘ＞Ｙのとき Ｘ，Ｙは同符号でX′＞Y′となるから Ｓ≧2n+1 となつて、(1)式の演算におけるｎ＋１ビツト
目からの桁上がりがあり、 Co+1＝１ ３−２ 一方、ＸＹのとき Ｘ，Ｙは同符号でX′Y′となることから Ｓ2n+1−１ となつて上記演算におけるｎ＋１ビツト目か
らの桁上がりがなく、 Co+1＝０ となる。 以上の関係を整理すると次表のようになる。
データ群における各データの差の絶対値の累積和
として計算する装置に関する。 (2) 技術の背景 一般に音声認識或いは画像認識では、入力する
音声パターンや画像パターンを予め定めた複数の
標準パターンと比較し、これら標準パターンのう
ち該入力パターンとの相違が一番小さいものを認
識パターンとするようにしている。そして、この
入力パターンと標準パターンとの相違の尺度とし
て、例ば、多数次元での特徴抽出によつ複数のデ
ータからなる（多次元）入力パターンと同次元の
データからなる予め定めた標準パターンとにおけ
る対応する次元の各データ値の差の絶対値を順次
加算した累積和を用いることができる。すなわ
ち、当該累積和が大きければ、入力パターン、標
準パターンの相違は大きく、当該累積和が小さけ
ればその相違が小さいものとなる。 そこで、音声認識或いは画像認識では、その入
力パターンと標準パターンの両データ群の相違を
上記のような累積和として計算する相違度計算装
置が必要となり、更に当該累積和をできるだけ高
速に計算できる装置が要望されている。 (3) 従来技術と問題点 従来、この種の相違度計算装置として例えば第
１図に示すようなものが考えられる。ここで、対
象となる２つのデータ群Ａ＝｛Ai｝、 Ｂ＝｛Bi｝を構成する２進データは、正又は負
の値であり、その表現は、演算処理に便利なよう
に、例えばｎ＋１ビツト表現のものであれば、 Ai＝−ao・2n＋A′ A′＝＋ao-1・2n-1＋ao-2・2n-2＋ ……＋a121＋a020 ao〜a0：０又は１ で示される数値となる、いわゆる２の補数表現さ
れたものとなつている（Biについても同様）。 第１図において、１は上記のように２の補数表
現されたデータ群Ａ、及びＢの対応する次元のデ
ータAiとBiとの大小を判定する比較回路、２は上
記データAi，Biを入力し、比較回路１での判定結
果に基づいて、データAi，Biのうち大きい方を選
択出力するマルチプレクサ、３は上記データAi，
Biを反転回路７ａ，７ｂによつて反転させた当該
反転データ（１の補数）を入力し、比較回路１で
の判定結果に基づいて、データAi，Biのうち小さ
い方の反転データを選択出力するマルチプレク
サ、４はマルチプレクサ２、及び３からの各出力
データとビツトデータ“１”とを加算する加算回
路であり、この比較回路１、マルチプレクサ２，
３、及び加算回路４によつて、入力するデータ
Ai，Biの大きい方から小さい方を減算する減算回
路が構成され、すなわち、最終段の加算回路４か
らの出力がデータAiとBiの差の絶対値｜Ai−Bi｜
となる。そして、データ群Ａ、及びＢからのデー
タが入力する毎に加算回路４から出力される上記
絶対値｜Ai−Bi｜を、加算回路５によつて、レジ
スタ６に格納されている前回までの加算結果と加
算して、この加算結果を再度レジスタ６に格納す
るようにし、レジスタ６の最終格納データが、上
記データ群Ａ，Ｂにおける対応する次元の各デー
タの差の絶対値の累積和Σ｜Ai−Bi｜、すなわち
データ群Ａ，Ｂの相違度となるようにしている。 このように、データ群Ａ、及びＢから順次入力
するデータAi，Biの大小を判定し、その大きい方
から小さい方を減算した結果を順次累積加算する
ようにした上記相違度計算装置は、ハードウエア
で構成することにより、比較的高速な処理が実現
できるようになる。 しかしながら、この第１図に示すような相違度
計算装置では、データAi，Biの大小を判定する比
較回路１と、この比較回路１の判定結果に基づい
てデータ選択を行なうマルチプレクサ２、及び３
が必要なため、回路構成が比較的複雑になるとい
う不具合がある。 (4) 発明の目的 本発明は上記の点に鑑みてなされたもので、特
に２の補数表現された２進データからなる２つの
データ群における互いに対応した各データの差の
絶対値の累積和を計算する相違度計算装置をでき
るだけ簡単な回路構成で実現することを目的とし
ている。 (5) 発明の構成 上記目的を達成するため本発明は、負の数のみ
が２の補数表現された２つの２進データの差の絶
対値を計算する装置であつて、 前記２進データのうちの一方の２進データと、
他方の２進データの反転データとを加算する加算
回路と、前記２つの２進データの符号ビツトと前
記加算回路から出力される最上位桁上がりビツト
とが入力され、当該ビツトデータの排他的論理和
により前記２つの２進データの大、小を判定する
判定回路と、前記加算回路からの最上位桁上がり
ビツト以外の出力２進データを、前記一方の２進
データが前記他方の２進データより大なるとき
は、そのまま出力し、前記一方の２進データが前
記他方の２進データ以下であるときは、反転した
後、“１”を加算して出力する回路とを備えるよ
うにししたものである。 (5) 発明の実施例 まず、本発明において行なわれる負の数のみが
２の補数表現された２つの２進データの差の絶対
値を求める計算について、基本的な論理を説明す
る。 例えば、ｎ＋１ビツトで負の数のみが２の補数
表現された２つの２進データＸ及びＹの符号ビツ
ト（最上位ビツト）をそれぞれXo，yoとし、残
りのｎビツトで表現される部分をそれX′，Y′と
すると、各データＸ，Ｙは Ｘ＝−xo・2n＋X′ Ｙ＝−yo・2n＋Y′ で示される数値となるが、２進演算の過程におい
ては符号ビツトと他のビツトは同様の取扱いとな
るので、 Ｘ＝xo・2n＋X′ Ｙ＝yo・2n＋Y′ となる。 ここで、データＸとデータＹの反転データ（１
の補数）とを加算した加算データＳを考ると、 Ｓ＝Ｘ＋ ＝（xo・2n＋X′） ＋（o・2n＋′） ＝（Xo＋o）・2n ＋（X′＋′） ……(1) となる。 この演算においてｎ＋１（符号）ビツト目から
の桁上がりをCo+1、ｎビツト目からの桁上がりを
をCoとすると、 １ xo＝０、yo＝１のとき、 すなわち、Ｘ０＞Ｙのとき、 xo＋o＝０であるから Co+1＝０ となる。 ２ xo＝１、yo＝０のとき、 すなわち、Ｘ＜０Ｙのとき、 xo＋o＝10（２進値）であるから、 Co+1＝１ となる。 ３ Xo＝０、yo＝０又はxo＝１、 yo＝１のとき、上記加算データＳは、 xo＋o＝１であるから、 Ｓ＝2n＋（X′＋′） となり、Y′がｎビツト表現であるから ′＝2n−１−Y′ となつて Ｓ＝2n+1−１＋（X′−Y′） となる。 ３−１ ここで、Ｘ＞Ｙのとき Ｘ，Ｙは同符号でX′＞Y′となるから Ｓ≧2n+1 となつて、(1)式の演算におけるｎ＋１ビツト
目からの桁上がりがあり、 Co+1＝１ ３−２ 一方、ＸＹのとき Ｘ，Ｙは同符号でX′Y′となることから Ｓ2n+1−１ となつて上記演算におけるｎ＋１ビツト目か
らの桁上がりがなく、 Co+1＝０ となる。 以上の関係を整理すると次表のようになる。
【表】
すなわち、ＸがＹより大きい時は、Ｘ，Ｙの最
上位ビツトとＳ＝Ｘ＋の最上位桁上がりビツト
との排他的論理和の論理出力が“１”、 Ｘ＞Ｙのとき、 XoyoCo+1＝１ ……(2) となる一方、ＸがＹ以下の時は、Ｘ，Ｙの最上位
ビツトとＳ＝Ｘ＋の最上位桁上がりビツトとの
排他的論理和の論理出力が“０”、 ＸＹのとき、 XoyoCo+1＝０ ……(3) となる。 一方(1)式で示される加算データＳは Ｓ＝Ｘ＋ ＝Ｘ＋2n+1−１−Ｙ となることから、データＸ，Ｙの差の絶対値 Ｄ＝｜Ｘ−Ｙ｜は、Ｘ＞Ｙのとき Ｄ＝Ｘ−Ｙ ＝Ｓ＋１−2n+1 となる。そして、更に Ｓ＝Co+1・2n+1＋S′ ……(4) （S′＝So・2n＋So-1・2n-1 ……＋S1・21＋S0・20） となることから、 xo＝yo、Co+1のとき、 Ｄ＝Co+1・2n+1＋S′＋１−2n+1 ＝S′＋１ ……(5) Xo＝０、yo＝１、Co+1＝０のとき Ｄ＝S′＋１−2n+1 ……(6) (6)式をｎ＋１ビツト表現すると、 Ｄ＝S′＋１ となる。すなわち、ＸがＹより大きいとき、Ｘ，
Ｙの差の絶対値Ｄ＝｜Ｘ−Ｙ｜は、(1)式で示され
る加算データＳのうち最上位桁上がりビツト以外
の２進データS′に“１”を加算したものとなる。 Ｘ＞Ｙのとき Ｄ＝S′＋１ ……(7) また、当該絶対値Ｄ＝｜Ｘ−Ｙ｜は、ＸＹの
とき Ｄ＝Ｙ−Ｘ ＝2n+1−１−Ｓ ＝2n+1−１−S′−Co+1・2n+1 となることから、 Xo＝yo、Co+1＝０のとき Ｄ＝2n+1−１−S′＝′ ……(6) Xo＝１、yo＝０、Co+1＝１のとき Ｄ＝−2n+1 ……(9) (9)式をｎ＋１ビツト表現すると、 Ｄ＝ となる。すなわち、ＸがＹ以下のとき、Ｘ，Ｙの
差の絶対値Ｄ＝｜Ｘ−Ｙ｜は、(1)式で示される加
算データＳのうち最上位桁上がりビツト以外の２
進データS′を反転したものとなる。 ＸＹのとき Ｄ＝′ ……(10) 上記(2)式、(3)式、及び(7)式、(10)式から xoyoCo+1＝１のとき Ｄ＝｜Ｘ−Ｙ｜ ＝S′＋１ ……(11) xoyoCo+1＝０のとき Ｄ＝｜Ｘ−Ｙ｜＝′ ……(12) となる。 すなわち、２の補数表現された２つの２進デー
タの差の絶対値を求めるには、まず、当該２進デ
ータの一方と、他方の反転データとを加算し、該
加算結果の最上位桁上がりビツトと上記２の補数
表現された両２進データの最上位ビツトとの排他
的論理和出力が“１”のときに、上記加算結果の
最上位桁上がりビツト以外の２進データに“１”
を加算し、また上記排他的論理和出力が“０”の
ときに、上記加算結果の最上位桁上がりビツト以
外の２進データを反転するようにする。 以下、上記基本理論に従つて作動する本発明の
実施例を図面に基づいて説明する。 第２図は本発明の一実施例を示すブロツク図で
ある。 同図において、１０は２の補数表現されたデー
タ群ＡのデータAiと、同様に２の補数表現された
データ群ＢのデータBiを反転回路１６によつて反
転させた当該反転データiとを加算する加算回
路、１１は上記データAi及びBiの最上位ビツトす
なわち符号ビツトと加算回路１０から出力される
最上位桁上がりビツトを入力し、データAi，Biの
大小を判定する排他的論理和回路（以下EOR回
路という）、１２は加算回路１０から出力される
最上位桁上がりビツト以外の２進データを入力
し、EOR回路１１からの論理出力に基づいて当
該入力データを変換出力するデータ変換回路であ
り、このデータ変換回路１２は、加算回路１０か
ら出力されるビツト毎に当該ビツトデータが入力
される排他的論理和ゲート１２−１〜１２−ｎ
（以下EORゲートという）を設け、該EORゲート
１２−１〜１２−ｎの他方入力端に、EOR回路
１１からの論理和出力をインバータ１７によつて
反転した反転ビツトデータが入力するようにし、
この各EORゲート１２−１〜１２−ｎの出力を
データ変換回路１２の出力としている。 また、１３は加算回路、１４は加算回路１３か
らの出力データを格納するレジスタであり、この
加算回路１３、及びレジスタ１４は、データ変換
回路１２からの出力データとEOR回路１１から
の論理出力が加算回路１３に入力する毎に、加算
回路１３が当該入力データとレジスタ１４に格納
されたデータとを加算して再度この加算データを
レジスタ１４に格納する、いわゆる累積和回路を
構成している。 ここで、加算回路１０は上記式(1)（Ｓ＝Ｘ＋
Ｙ）を実現する回路、排他的論理和回路１１は上
記式(2)、及び(3) （Ｘ＞Ｙのとき、xoyoCn+1＝１、 ＸＹのときxoyoCn+1＝０） の判定を行なう回路、データ変換回路１２は(11)
式、(12)式におけるS′又は′を求める回路、加算
回路１３は(11)式、(12)式 （Ｄ＝S′＋１、Ｄ＝′） を実現する回路である。 次に下記に示す３次元のデータ群Ａ，Ｂにおけ
る相違度の計算を例にとつて作動を説明する。 Ａ＝｛２，−３，４｝ Ｂ＝｛−２，１，２｝ 上記データ群Ａ，Ｂの各データを例えば４ビツ
で２の補数表現すると、 Ａ＝｛0010，1101，0100｝ Ｂ＝｛1110，0001，0010｝ となる。 まず、Ai＝0010，Bi＝1110が入力されると加算
回路１０は Ai＋Ｂi＝0010＋0001＝0011 を出力し、この２進データ（0011）はデータ変換
回路１２に入力される。AiとBi、及び加算回路１
０からの最上位桁上がりビツトは（010）となる
ことからEOR回路１１の論理出力は ０１０＝１ となり、データ変換回路１２への入力データ
（0011）はEORゲート１２−１〜１２〜ｎを介し
てそのまま（0011）として出力される。そして、
加算回路１３で、データ変換回路１２からの出力
とEOR回路１１の論理出力と既にクリアされて
いるレジスタ１４の格納データが加算され、 0011＋１＋０＝0100 該加算データ（0100）がレジスタ１４に格納さ
れる。 次に、Ai＝1101、Bi＝0001が入力されると、加
算回路１０の出力は Ai＋i＝1101＋1110＝11011 EOR回路１１の論理出力は １０１＝０ となり、データ変換回路１２への入力データ
（1011）は、EORゲート１２−１〜１２−ｎを介
して反転されて（0100）として出力される。そし
て、加算回路１３で、データ変換回路１２からの
当該出力データ（0100）とEOR回路１１の論理
出力“０”とレジスタ１４の格納データ（0100）
とが加算され 0100＋０＋0100＝1000 該加算データ（1000）がレジスタ１４に格納さ
れる。 更に、Ai＝0100、Bi＝0010が入力すると、加算
回路１０の出力は Ai＋i＝0100＋1101＋10001 EOR回路１１の論理出力は ００１＝１ となり、データ変換回路への入力データ（0001）
は、EORゲートを介してそのまま（0001）とし
て出力され、そして、加算回路１３の出力が 0001＋１＋1000＝1010 となつて、該加算データ（1010）がレジスタ１４
に格納される。 このようにデータ群Ａ，Ｂのすべての構成デー
タについての演算が終了したときのレジスタ１４
に格納されたデータ（1010）が、上記データ群
Ａ，Ｂにおける互いに対応した各データの差の絶
対値の累積和、すなわち相違度となり、この場
合、相違度は「10」（10進数）である。 上記のように本実施例は、加算回路１０の最上
位桁上がりビツトと入力するデータAi，Biの最上
位ビツトとの排他的論理和出力によつてデータ
Ai，Biの大小の判定を行い、該判定結果に基づく
加算回路１０の最上位桁上がりビツト以外の２進
データの変換データ、及び当該排他的論理和出力
の加算によつてデータAi，Biの差の絶対値が求め
られるため、第１図に示す装置のようにデータ
Ai，Biを選択するマルチプレクサ２，３が不要に
なると共に、データAi，Biの大小を判定する回路
構成が簡単となる。 第３図は本発明の他の実施例を示すブロツク図
である。この実施例は、加算回路１０からの最上
位桁上がりビツト以外の２進データと、EOR回
路１１の論理出力ビツトとをレジスタ１５に格納
するような構成となり、このレジスタ１５は、レ
ジスタ１４と同一のクロツクに同期して、出力及
び格納動作を行なうものである。このような構成
にすれば、データAi，Biを入力してから、レジス
タ１５にデータを格納するまでの動作と、レジス
タ１５からデータを出力してから、レジスタ１４
にデータを格納するまでの動作とが同一クロツク
同期内に並列して行なわれるため、そのクロツク
周期を第２図に示す場合より小さくすることがで
き、その結果、装置全体の処理を更に高速化でき
る。 (7) 発明の効果 以上詳細に説明したように、本発明によれば、
２の補数表現された２進データからなる２つのデ
ータ群における互いに対応した各データの差の絶
対値の和を計算する相違度計算装置が、従来考え
られていたものよりも簡単な回路構成で実現で
き、その結果、その演算処理も更に高速化するこ
とができる。
上位ビツトとＳ＝Ｘ＋の最上位桁上がりビツト
との排他的論理和の論理出力が“１”、 Ｘ＞Ｙのとき、 XoyoCo+1＝１ ……(2) となる一方、ＸがＹ以下の時は、Ｘ，Ｙの最上位
ビツトとＳ＝Ｘ＋の最上位桁上がりビツトとの
排他的論理和の論理出力が“０”、 ＸＹのとき、 XoyoCo+1＝０ ……(3) となる。 一方(1)式で示される加算データＳは Ｓ＝Ｘ＋ ＝Ｘ＋2n+1−１−Ｙ となることから、データＸ，Ｙの差の絶対値 Ｄ＝｜Ｘ−Ｙ｜は、Ｘ＞Ｙのとき Ｄ＝Ｘ−Ｙ ＝Ｓ＋１−2n+1 となる。そして、更に Ｓ＝Co+1・2n+1＋S′ ……(4) （S′＝So・2n＋So-1・2n-1 ……＋S1・21＋S0・20） となることから、 xo＝yo、Co+1のとき、 Ｄ＝Co+1・2n+1＋S′＋１−2n+1 ＝S′＋１ ……(5) Xo＝０、yo＝１、Co+1＝０のとき Ｄ＝S′＋１−2n+1 ……(6) (6)式をｎ＋１ビツト表現すると、 Ｄ＝S′＋１ となる。すなわち、ＸがＹより大きいとき、Ｘ，
Ｙの差の絶対値Ｄ＝｜Ｘ−Ｙ｜は、(1)式で示され
る加算データＳのうち最上位桁上がりビツト以外
の２進データS′に“１”を加算したものとなる。 Ｘ＞Ｙのとき Ｄ＝S′＋１ ……(7) また、当該絶対値Ｄ＝｜Ｘ−Ｙ｜は、ＸＹの
とき Ｄ＝Ｙ−Ｘ ＝2n+1−１−Ｓ ＝2n+1−１−S′−Co+1・2n+1 となることから、 Xo＝yo、Co+1＝０のとき Ｄ＝2n+1−１−S′＝′ ……(6) Xo＝１、yo＝０、Co+1＝１のとき Ｄ＝−2n+1 ……(9) (9)式をｎ＋１ビツト表現すると、 Ｄ＝ となる。すなわち、ＸがＹ以下のとき、Ｘ，Ｙの
差の絶対値Ｄ＝｜Ｘ−Ｙ｜は、(1)式で示される加
算データＳのうち最上位桁上がりビツト以外の２
進データS′を反転したものとなる。 ＸＹのとき Ｄ＝′ ……(10) 上記(2)式、(3)式、及び(7)式、(10)式から xoyoCo+1＝１のとき Ｄ＝｜Ｘ−Ｙ｜ ＝S′＋１ ……(11) xoyoCo+1＝０のとき Ｄ＝｜Ｘ−Ｙ｜＝′ ……(12) となる。 すなわち、２の補数表現された２つの２進デー
タの差の絶対値を求めるには、まず、当該２進デ
ータの一方と、他方の反転データとを加算し、該
加算結果の最上位桁上がりビツトと上記２の補数
表現された両２進データの最上位ビツトとの排他
的論理和出力が“１”のときに、上記加算結果の
最上位桁上がりビツト以外の２進データに“１”
を加算し、また上記排他的論理和出力が“０”の
ときに、上記加算結果の最上位桁上がりビツト以
外の２進データを反転するようにする。 以下、上記基本理論に従つて作動する本発明の
実施例を図面に基づいて説明する。 第２図は本発明の一実施例を示すブロツク図で
ある。 同図において、１０は２の補数表現されたデー
タ群ＡのデータAiと、同様に２の補数表現された
データ群ＢのデータBiを反転回路１６によつて反
転させた当該反転データiとを加算する加算回
路、１１は上記データAi及びBiの最上位ビツトす
なわち符号ビツトと加算回路１０から出力される
最上位桁上がりビツトを入力し、データAi，Biの
大小を判定する排他的論理和回路（以下EOR回
路という）、１２は加算回路１０から出力される
最上位桁上がりビツト以外の２進データを入力
し、EOR回路１１からの論理出力に基づいて当
該入力データを変換出力するデータ変換回路であ
り、このデータ変換回路１２は、加算回路１０か
ら出力されるビツト毎に当該ビツトデータが入力
される排他的論理和ゲート１２−１〜１２−ｎ
（以下EORゲートという）を設け、該EORゲート
１２−１〜１２−ｎの他方入力端に、EOR回路
１１からの論理和出力をインバータ１７によつて
反転した反転ビツトデータが入力するようにし、
この各EORゲート１２−１〜１２−ｎの出力を
データ変換回路１２の出力としている。 また、１３は加算回路、１４は加算回路１３か
らの出力データを格納するレジスタであり、この
加算回路１３、及びレジスタ１４は、データ変換
回路１２からの出力データとEOR回路１１から
の論理出力が加算回路１３に入力する毎に、加算
回路１３が当該入力データとレジスタ１４に格納
されたデータとを加算して再度この加算データを
レジスタ１４に格納する、いわゆる累積和回路を
構成している。 ここで、加算回路１０は上記式(1)（Ｓ＝Ｘ＋
Ｙ）を実現する回路、排他的論理和回路１１は上
記式(2)、及び(3) （Ｘ＞Ｙのとき、xoyoCn+1＝１、 ＸＹのときxoyoCn+1＝０） の判定を行なう回路、データ変換回路１２は(11)
式、(12)式におけるS′又は′を求める回路、加算
回路１３は(11)式、(12)式 （Ｄ＝S′＋１、Ｄ＝′） を実現する回路である。 次に下記に示す３次元のデータ群Ａ，Ｂにおけ
る相違度の計算を例にとつて作動を説明する。 Ａ＝｛２，−３，４｝ Ｂ＝｛−２，１，２｝ 上記データ群Ａ，Ｂの各データを例えば４ビツ
で２の補数表現すると、 Ａ＝｛0010，1101，0100｝ Ｂ＝｛1110，0001，0010｝ となる。 まず、Ai＝0010，Bi＝1110が入力されると加算
回路１０は Ai＋Ｂi＝0010＋0001＝0011 を出力し、この２進データ（0011）はデータ変換
回路１２に入力される。AiとBi、及び加算回路１
０からの最上位桁上がりビツトは（010）となる
ことからEOR回路１１の論理出力は ０１０＝１ となり、データ変換回路１２への入力データ
（0011）はEORゲート１２−１〜１２〜ｎを介し
てそのまま（0011）として出力される。そして、
加算回路１３で、データ変換回路１２からの出力
とEOR回路１１の論理出力と既にクリアされて
いるレジスタ１４の格納データが加算され、 0011＋１＋０＝0100 該加算データ（0100）がレジスタ１４に格納さ
れる。 次に、Ai＝1101、Bi＝0001が入力されると、加
算回路１０の出力は Ai＋i＝1101＋1110＝11011 EOR回路１１の論理出力は １０１＝０ となり、データ変換回路１２への入力データ
（1011）は、EORゲート１２−１〜１２−ｎを介
して反転されて（0100）として出力される。そし
て、加算回路１３で、データ変換回路１２からの
当該出力データ（0100）とEOR回路１１の論理
出力“０”とレジスタ１４の格納データ（0100）
とが加算され 0100＋０＋0100＝1000 該加算データ（1000）がレジスタ１４に格納さ
れる。 更に、Ai＝0100、Bi＝0010が入力すると、加算
回路１０の出力は Ai＋i＝0100＋1101＋10001 EOR回路１１の論理出力は ００１＝１ となり、データ変換回路への入力データ（0001）
は、EORゲートを介してそのまま（0001）とし
て出力され、そして、加算回路１３の出力が 0001＋１＋1000＝1010 となつて、該加算データ（1010）がレジスタ１４
に格納される。 このようにデータ群Ａ，Ｂのすべての構成デー
タについての演算が終了したときのレジスタ１４
に格納されたデータ（1010）が、上記データ群
Ａ，Ｂにおける互いに対応した各データの差の絶
対値の累積和、すなわち相違度となり、この場
合、相違度は「10」（10進数）である。 上記のように本実施例は、加算回路１０の最上
位桁上がりビツトと入力するデータAi，Biの最上
位ビツトとの排他的論理和出力によつてデータ
Ai，Biの大小の判定を行い、該判定結果に基づく
加算回路１０の最上位桁上がりビツト以外の２進
データの変換データ、及び当該排他的論理和出力
の加算によつてデータAi，Biの差の絶対値が求め
られるため、第１図に示す装置のようにデータ
Ai，Biを選択するマルチプレクサ２，３が不要に
なると共に、データAi，Biの大小を判定する回路
構成が簡単となる。 第３図は本発明の他の実施例を示すブロツク図
である。この実施例は、加算回路１０からの最上
位桁上がりビツト以外の２進データと、EOR回
路１１の論理出力ビツトとをレジスタ１５に格納
するような構成となり、このレジスタ１５は、レ
ジスタ１４と同一のクロツクに同期して、出力及
び格納動作を行なうものである。このような構成
にすれば、データAi，Biを入力してから、レジス
タ１５にデータを格納するまでの動作と、レジス
タ１５からデータを出力してから、レジスタ１４
にデータを格納するまでの動作とが同一クロツク
同期内に並列して行なわれるため、そのクロツク
周期を第２図に示す場合より小さくすることがで
き、その結果、装置全体の処理を更に高速化でき
る。 (7) 発明の効果 以上詳細に説明したように、本発明によれば、
２の補数表現された２進データからなる２つのデ
ータ群における互いに対応した各データの差の絶
対値の和を計算する相違度計算装置が、従来考え
られていたものよりも簡単な回路構成で実現で
き、その結果、その演算処理も更に高速化するこ
とができる。
第１図は従来考えられていた相違度計算装置を
示すブロツク図、第２図、及び第３図は本発明の
実施例を示すブロツク図である。 １０，１３……加算回路、１１……排他的論理
和回路（EOR回路）、１２……データ変換回路、
１４……レジスタ。
示すブロツク図、第２図、及び第３図は本発明の
実施例を示すブロツク図である。 １０，１３……加算回路、１１……排他的論理
和回路（EOR回路）、１２……データ変換回路、
１４……レジスタ。
Claims (1)
- 【特許請求の範囲】 １ 負の数のみが２の補数表現された２つの２進
データの差の絶対値を計算する装置であつて、 前記２進データのうちの一方の２進データと、
他方の２進データの反転データとを加算する加算
回路と、前記２つの２進データの符号ビツトと前
記加算回路から出力される最上位桁上がりビツト
とが入力され、当該ビツトデータの排他的論理和
により前記２つの２進データの大、小を判定する
判定回路と、前記加算回路からの最上位桁上がり
ビツト以外の出力２進データを、前記一方の２進
データが前記他方の２進データより大なるとき
は、そのまま出力し、前記一方の２進データが前
記他方の２進データ以下であるときは反転した
後、“１”を加算して出力する回路とを備えてな
る相違度計算装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP58202291A JPS60186979A (ja) | 1983-10-28 | 1983-10-28 | 相違度計算装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP58202291A JPS60186979A (ja) | 1983-10-28 | 1983-10-28 | 相違度計算装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS60186979A JPS60186979A (ja) | 1985-09-24 |
| JPH0315209B2 true JPH0315209B2 (ja) | 1991-02-28 |
Family
ID=16455105
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP58202291A Granted JPS60186979A (ja) | 1983-10-28 | 1983-10-28 | 相違度計算装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS60186979A (ja) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH0199190A (ja) * | 1987-10-13 | 1989-04-18 | Fujitsu Ltd | 距離演算回路 |
Family Cites Families (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4218751A (en) * | 1979-03-07 | 1980-08-19 | International Business Machines Corporation | Absolute difference generator for use in display systems |
| JPS58132861A (ja) * | 1982-02-03 | 1983-08-08 | Toshiba Corp | 演算回路 |
-
1983
- 1983-10-28 JP JP58202291A patent/JPS60186979A/ja active Granted
Also Published As
| Publication number | Publication date |
|---|---|
| JPS60186979A (ja) | 1985-09-24 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US4953115A (en) | Absolute value calculating circuit having a single adder | |
| US4722069A (en) | Nonrestoring divider | |
| CA1332196C (en) | Radix-16 divider using overlapped quotient bit selection and concurrent quotient rounding and correction | |
| JPH01125626A (ja) | 逆数計算方法 | |
| JPH02190928A (ja) | 除算器 | |
| US5132925A (en) | Radix-16 divider using overlapped quotient bit selection and concurrent quotient rounding and correction | |
| US5309383A (en) | Floating-point division circuit | |
| CN100524201C (zh) | 用于实现2的幂的浮点估计的装置与方法 | |
| JP2585649B2 (ja) | 除算回路 | |
| US6847986B2 (en) | Divider | |
| US6728745B1 (en) | Semiconductor circuit for arithmetic operation and method of arithmetic operation | |
| JPH04205026A (ja) | 除算回路 | |
| JP2006172035A (ja) | 除算・開平演算器 | |
| JPS63123125A (ja) | 浮動小数点数の加算装置 | |
| US3591784A (en) | Real time digital fourier analyzer | |
| JPH0315209B2 (ja) | ||
| TWI802095B (zh) | 模數乘法電路與對應之計算模數乘法之方法 | |
| EP0442220B1 (en) | Decoder | |
| KR0182169B1 (ko) | 로그값 계산회로 | |
| JPS6227864A (ja) | 累算回路 | |
| KR20060078258A (ko) | 가변 진법 나눗셈 연산기 | |
| JP3482102B2 (ja) | 絶対値距離演算回路 | |
| JPH05165605A (ja) | 浮動小数点乗算器及び乗算方法 | |
| JP3213982B2 (ja) | 除算回路 | |
| SU809149A2 (ru) | Преобразователь двоичного кода сме-шАННыХ чиСЕл B дВОичНО-дЕС ТичНый КОд |