JPS6127769B2

JPS6127769B2 -

Info

Publication number: JPS6127769B2
Application number: JP19892681A
Authority: JP
Inventors: Yoshitake Suzuki; Hiroki Yamauchi; Atsushi Iwata
Original assignee: Nippon Telegraph and Telephone Corp
Current assignee: NTT Inc
Priority date: 1981-12-10
Filing date: 1981-12-10
Publication date: 1986-06-27
Also published as: JPS5899836A

Description

【発明の詳細な説明】本発明はエンコーダ回路に関し、詳しくは、並
列２進データのビツトの値が、上位あるいは下位
からみて、最初に“０”から“１”または“１”
から“０”に反転する桁を高速に検出する機能を
有するエンコーダ回路に関するものである。以下
では簡単のため、データのビツト長が16ビツトと
し、そのビツトの値がMSB（最上位ビツト）か
ら数えて最初に“１”から“０”に反転する桁を
検出する機能をもつたエンコーダ回路について説
明する。

従来、２進データA₁₆〜A₁（A₁₆：MSB）の
MSBから数えて最初に値が“１”から“０”に
反転する桁を検出し、４ビツトの２進データZ₄〜
Z₁として出力する回路は第１図の構成をとつてい
る。第１図において、１はデータA₁₆〜A₁を入力
として、ビツトが最初に“１”から“０”に反転
した桁から下位の桁すべてを“０”にセツトする
AND ARRAY回路である。すなわち、このAND
ARRAY回路１は、前段のANDゲートの出力Bi
（ｉ＝16，15，…，２）を次段のANDゲートに入
力して、入力データAi_-1とのAND条件をとり、
出力Bi_-1を得るものである。たゞし、B₁₆＝A₁₆で
ある。２は出力B₁₆〜B₁を入力として、反転桁の
み“１”、他の桁はすべて“０”の信号C₁₆〜C₁
を出力するEXCLUSIVE OR ARRAY回路であ
る。たゞし、C₁＝B₁である。３は信号C₁₆〜C₁を
入力として、これを４ビツトの２進符号に変換す
る回路で、その出力Z₄〜Z₁が、入力データA₁₆〜
A₁の値がMSBから数えて最初に反転する桁は何
桁目であるかを示す。

ところで、第１図のエンコーダ回路の中で演算
時間が最もかゝるのはAND ARRAY回路１の部
分であり、こゝでは信号が15段のANDゲートを
通過する。このため、エンコーダ回路の高速性が
著しく妨げられるという欠点があつた。

本発明は、上記の欠点を解決するため、AND
ARRAYの機能を高速に実行する回路を用いたも
ので、以下、図面について詳細に説明する。

第２図は、第１図のAND ARRAY回路１と同
一の機能を高速に実行する回路を含む本発明の一
実施例である。第２図において、S₁，S₂，S₃は16
ビツトのAND ARRAYをそれぞれ10，４，２桁
の部分AND ARRAYに分割したもので、各部分
AND ARRAYは、その内部でそれぞれ前段の
ANDゲートの出力Bi（ｉ＝16，15，…，２）を
次段のANDゲートに入力して、入力データAi_-1
とのAND条件をとり、出力Bi_-1を得るとゝもに
（たゞし、B₁₆＝A₁₆）、該当部分AND ARRAY内
のすべての入力のAND条件をとり、下位部分
ARRAYの最上位桁への入力B₇′，B₃′を発生する
機能を有している。回路２，３は第１図と同様で
ある。

最初に、第２図の部分AND ARRAYS₁，S₂，
S₃が第１図の回路のAND ARRAYと同一の機能
を有することを説明する。部分AND ARRAYS₁
内において、最上位入力A₁₆はそのまゝ出力B₁₆と
なる。B₁₆はA₁₅とゝもにANDゲート１１に入力
され、B₁₅＝｛B₁₆∩A₁₅）を出力する。B₁₅はA₁₄
とゝもにANDゲート１２に入力され、B₁₄を出力
する。以下同様にして、部分AND ARRAYS₁内
において出力B₁₆〜B₇が定まる。一方、A₁₆〜A₇
は多入力AND回路２６に入力され、出力B₇′を得
る。ただし、 B₇′＝〔A₁₆∩A₁₅∩…A₈∩A₇｝である。こゝで、B₇′＝B₇となるが、その理由を
以下に説明する。

部分AND ARRAYS₁の第i_-1桁の出力Bi_-1（ｉ
＝16，…，８）は Bi_-1＝｛Bi∩Ai_-1｝（ｉ＝16，…，８）となる
が、例えばA₁₂＝０のときには B₁₂｛B₁₃∩A₁₂｝＝０となり、その結果B₁₁は B₁₁｛B₁₂∩A₁₁｝＝０となる。同様にして、B₁₀〜B₇も“０”となるこ
とは明らかである。すなわち、部分AND
ARRAYS₁の入力A₁₆〜A₇のうち、どれか１つが
“０”であれば、B₇は“０”となるから、これは
A₁₆〜A₇を入力とするAND回路の出力B₇′と等価
である。

部分AND ARRAYS₂の機能は上記S₁と同様で
ある。ただし、ANDゲート２０の入力は、AND
回路２６の出力B₇′とA₆となる。A₆〜A₃および
B₇′はAND回路２７に入力され、該AND回路２７
はB₃′を出力する。こゝで、B₃′＝B₃となるが、そ
の理由は、A₁₆〜A₇のうちどれか１つが“０”で
あればB₇′＝０であること、およびA₆〜A₃のうち
どれか１つが“０”であればB₃′＝０となること
から明らかである。

部分AND ARRAYS₃では、AND回路２７の出
力B₃′がA₂とともにANDゲート２４に入力され、
出力B₂が定まる。B₂とA₁は最下位桁のANDゲー
ト２５に入力され、B₁が出力される。

上記B₁₆〜B₁は、B₁₆とB₁₅、B₁₅とB₁₄、B₁₄と
B₁₃、…、B₂とB₁のペアでEXCLUSIVE OR
ARRAY回路２に並列的に入力され、出力として
C₁₆〜C₂が定まる。ただし、C₁＝B₁である。C₁₆
〜C₁は、A₁₆〜A₁のうち、MSBから数えて最初に
値が反転する桁に対応する桁のみ“１”で、その
他の桁は“０”であるようなデータである。C₁₆
〜C₁は、16―４ビツト２進変換回路３に入力さ
れ、その結果出力Z₄〜Z₁が得られる。

次に、第２図の回路が第１図のAND ARRAY
に比べて高速となること、および高速化のための
各部分AND ARRAYの桁数の最適な配分を求め
る手法を述べる。

入力データの桁数をＮとし、AND ARRAYを
ｎ個の部分AND ARRAYS₁，S₂，…，Ｓ_oに分割
し、その桁数をそれぞれm₁，m₂，…ｍ_oとする。
また、２入力ANDゲートの入力から出力までの
遅延時間をＴ、ｍ入力AND回路の遅延時間をｆ
(m)Ｔとし、各部分AND ARRAYS₁，S₂，…，Ｓ
_oからの最長遅延を等しくする条件を求めれば、 m₁＋m₂＋…＋ｍ_o＝Ｎｆ（m₁）Ｔ＋m₂T ＝（m₁−１）Ｔｆ（m₁）Ｔ＋ｆ（m₂＋１）Ｔ＋m₃T
＝（m₁−１）Ｔ〓ｆ（m₁）Ｔ＋ｆ（m₂＋１）Ｔ＋…
＋ｆ（ｍ_o-1＋１）Ｔ＋ｍ_oＴ＝（m₁−１）Ｔなる各式を得る。こゝで、第１の式は、桁数Ｎを
m₁，m₂，…，ｍ_o桁ずつ桁配分することを示す。
第２の式は、部分AND ARRAYS₁の多入力AND
回路の遅延時間ｆ（m₁）Ｔと、部分AND
ARRAYS₂の遅延時間m₂Tとの和が、部分AND
ARRAYS₁の遅延時間（m₁−１）Ｔと等しくなる
ための条件を示す。第３の式は、ｆ（m₁）Ｔ
と、部分AND ARRAYS₂の多入力AND回路の遅
延時間ｆ（m₂＋１）Ｔと、部分AND ARRAYS₃
の遅延時間m₃Tとの和が、（m₁−１）Ｔと等しく
なるための条件を示す。また、第４の式は、部分
AND ARRAYS₁から部分AND ARRAYS_o-1まで
の多入力AND回路の遅延時間の総和と、部分
AND ARRAYS_oの遅延時間ｍ_oＴとの和が、部分
AND ARRAYS₁の遅延時間（m₁−１）Ｔと等し
くなるための条件を示す。

一方、CMOS多入力ANDゲートの入力数依存
性ｆ(m)は、経験的に以下の式で近似される。

ｆ(m)＝１（ｍ−２）α こゝで、Ｎ＝16、α＝0.5を代入すれば、m₁〜
ｍ_oを元とするｎ元連立１次方程式が得られる。
ここでｎ＝３としてこれを解き、ｍを整数化する
と、m₁＝10、m₂＝４、m₃＝２となる。

第２図はこのようにして桁配分を決めたもので
あるが、このときのA₁₆〜A₁入力からB₁₆〜B₁出
力までの最大遅延時間Ｔ_ARは、前記の式によれ
ば、Ｔ_AR＝（m₁−１）＝9Tとなる。

次に、第２図において、A₁₆〜A₁入力からB₁₆
〜B₁出力までの遅延時間Ａ_ARを求めてみる。ｔ
＝０で入力A₁₆〜A₁が定まるものとすれば、ｔ＝
０でB₁₆、ｔ＝ＴでB₁₅、ｔ＝2TでB₁₄…が定ま
り、ｔ＝9TでB₇が定まる。一方、多入力AND回
路２６の出力B₇′は、前記のｆ（m₁）にm₁＝10を
代入してｆ(10)＝５を得るから、ｔ＝5Tで定まる
ことがわかる。B₇′が定まることによつて、部分
AND ARRAYS₂のANDゲート２０が駆動され、
その結果ｔ＝6TでB₆，…，ｔ＝9TでB₃が定ま
る。また、部分AND ARRAYS₂の多入力AND回
路２７は、ｔ＝5TでB₇′の入力により駆動される
が、ｆ（４＋１）＝2.5だから、出力B₃′はｔ＝5T
＋2.5T＝7.5Tで定まる。従つて、部分AND
ARRAYS₃のANDゲート２４はｔ＝7.5TでB₃′が
定まることにより駆動され、ｔ＝8.5TでB₂が定
まる。B₂とA₁を入力とするANDゲート２５の出
力はｔ＝9.5Tで定まる。

このように、部分AND ARRAYの桁配分を最
適化することにより、各部分AND ARRAY内の
最下位桁の出力B₇，B₃およびB₁が、ほぼ同時に
求まる。

ところで、第２図の多入力AND回路２６，２
７は、例えば３〜４入力程度のANDゲート二段
から構成することも可能である。その場合、入力
数依存性を与える関数ｇ(m)が得られゝば、前記
のｆ(m)の代わりにｇ(m)を用いることにより、
入力データに対する桁分割の最適化を図ることが
できる。第３図は、３入力ANDゲートを用いて
多入力AND回路を構成したもので、部分AND
ARRAYS₁，S₂，S₃はそれぞれ９，５，２桁に分
割されている。こゝで、２入力ANDゲート、３
入力ANDゲートの遅延時間を、先のｆ(m)に２お
よび３を代入して求めると、それぞれＴ、1.5T
となるので、ANDゲート２８の出力B₈′はＴ＝3T
で定まる。また、ANDゲート２９の出力B₃′はＴ
＝5.5Tで定まる。部分AND ARRAYS₁の最下位
桁の出力B₈は、ANDゲート８段分の遅延により
ｔ＝8Tで定まり、また、部分AND ARRAYS₂の
ANDゲート３０の入力がｔ＝3Tで定まるから、
S₂の最下位桁の出力B₃は、その後のANDゲート
５段分の遅延によりｔ＝8Tで定まる。さらに、
部分AND ARRAYS₃のANDゲート３１の入力
B₃′がｔ＝5.5Tで定まるから、B₂がｔ＝6.5T、B₁
がｔ＝7.5Tで定まる。

このように、A₁₆〜A₁入力よりB₁₆〜B₁出力ま
での最長遅延時間は、第２図の回路では9.5T、
第３図の回路では8Tとなるが、これは第２図の
多入力AND回路２６，２７と同等の機能を実行
する回路の遅延特性の差によるものである。例え
ば、バイポーラ素子においては入力数依存性が
CMOSに比べて弱く、従つて、多入力ANDゲー
トの入力数依存性も異なつた関数で表わされる
が、それに判つて、AND ARRAYの最適な桁配
分の状態も異なつてくることが予想される。さら
に、バイポーラ素子においては、第３図のように
多入力AND回路をANDゲートの複数段構成によ
り実現するよりも、第２図のように、多入力
ANDゲート１段により構成する方が、遅延時間
が低減する。

従来のエンコーダ回路において、データA₁₆〜
A₁を入力後、Z₄〜Z₁を出力するまでの遅延時間Ｔ
_Eは、次式で与えられる。

Ｔ_E＝Ｔ_AR＋Ｔ_EX＋Ｔ_Z ただし、Ｔ_ARはAND ARRAY回路１、Ｔ_EXは
EXCLUSIVE ORゲート、Ｔ_Zは16―４ビツト２
進変換回路３の遅延時間である。こゝで、Ｔ_EX
Ｔ、Ｔ_Z5Tとすれば、従来のAND ARRAY回
路ではＴ_AR＝15Tであるから、結局Ｔ_E21Tと
なる。一方、第３図の回路を用いればＴ_AR＝8T
となり、この結果Ｔ_E14Tとなり、エンコーダ
回路全体の遅延時間は従来の約67％となるから、
その高速化は明らかである。

以上、簡単のために、入力データA₁₆〜A₄の値
がMSBから数えて最初に“１”から“０”に反
転するビツトの位置を検出する回路について記し
たが、本回路を用いて、入力データの値がMSB
から数えて最初に“０”から“１”に反転するビ
ツトの位置を検出する機能を実現するには、あら
かじめA₁₆〜A₁ビツト反転回路に入力し、その出
力₁₆〜_１を本回路の入力とすればよい。さら
に、２の補数表示のような入力データに対して
は、MSBビツトをみて、それが“０”ならば反
転し、“１”ならば非反転となる機能を有する変
換回路を用いればよい。

また、本エンコーダ回路と同等の機能を、
ANDゲートの代わりにORゲートを用いることに
より実現することができる。第１図の１におい
て、AND ARRAYをOR ARRAYに置き換えれ
ば、前段のORゲートの出力Biと入力Ai_-1が、次
段のORゲートに入力され、その出力Bi_-1は Bi_-1＝｛Bi∪Ai_-1｝（ｉ＝16，…，２）として得られるから、OR ARRAYはデータA₁₆
〜A₁の値がMSBから数えて最初に“０”から
“１”に反転する桁から下位の桁すべてを“１”
にセツトする。

本発明のエンコーダ回路は、例えば高速な演算
回路における正規化回路に適用することができ
る。正規化回路は演算結果の桁落ちを判定し、そ
の落ちた桁数だけデータをシフトする機能を有す
るが、本エンコーダ回路の入力A₁₆〜A₁にデータ
を入力すれば、２のEXCLUSIVE OR回路の出力
C₁₆〜C₁から、MSBから数えて桁落ちの数に対応
する桁のみに“１”が立つデータが高速に得られ
るので、その出力をシフターに導入すればよい。
その他、並列比較形A/D変換器において、各識別
レベルに対応するコンパレータ出力が、高レベル
側からみて“０”から“１”に反転する桁を、反
転桁より低レベル側に符号誤りが生じていても正
しく高速に検出する回路に適用できる。

【図面の簡単な説明】

第１図は従来の16ビツトエンコーダ回路を示す
図、第２図は本発明のエンコーダ回路の一実施例
を示す図、第３図は第２図のAND ARRAY回路
の別の構成例を示す図である。１…AND ARRAY回路、２…EXCLUSIVE
OR ARRAY回路、３…16―４ビツト２進変換
器、１１〜２５…２入力ANDゲート、２６〜２
７…多入力AND回路、２８〜２９…３入力AND
ゲート、３０〜３１…２入力ANDゲート。

Claims

【特許請求の範囲】

１Ｎ桁（Ｎ＞１）の２進データを複数に分割し
てｎ個の部分データとし、各部分データは、もと
の２進データの下位ビツトあるいは上位ビツトに
対応する部分データに向い順次少ない桁数を有
し、各部分データの中に“０”あるいは“１”が
１つ以上含まれるか否かを検出し、その検出信号
を順次下位あるいは上位の部分データの最上位あ
るいは最下位ビツトへの入力データとする第１の
回路と、各部分データ内で、その最上位あるいは
最下位ビツトから部分データの値を順次みてい
き、ビツトの値が“１”あるいは“０”が連続す
る間は“１”あるいは“０”を出力し、その値が
最初に“０”あるいは“１”に反転したビツトよ
り下位あるいは上位のビツトに対してはすべて
“０”あるいは“１”を出力する第２の回路と、
該第２の回路より出力されたデータの互いに隣り
合う桁同士の排他的論理和（EXCLUSIVEOR）
をとつて、その結果を出力する第３の回路と、該
第３の回路の出力を入力し、それをＭ桁（Ｍ＞
１）の２進データに変換して出力する第４の回路
を有することを特徴とするエンコーダ回路。