JPS6126088B2

JPS6126088B2 -

Info

Publication number: JPS6126088B2
Application number: JP18516181A
Authority: JP
Inventors: Yoshitake Suzuki; Hiroki Yamauchi; Atsushi Iwata
Original assignee: Nippon Telegraph and Telephone Corp
Current assignee: NTT Inc
Priority date: 1981-11-20
Filing date: 1981-11-20
Publication date: 1986-06-19
Also published as: JPS5887628A

Description

【発明の詳細な説明】本発明は、パラレル２進データのビツトの値
が、上位あるいは下位からみて最初に“０”から
“１”、または“１”から“０”に反転する桁を高
速に検出する機能を有する回路に関するものであ
る。

以下では簡単のため、データのビツト長を16ビ
ツトとし、そのビツトの値が最上位桁（MSB）
から数えて最初に“１”から“０”に反転する桁
を検出する機能をもつたエンコーダ回路について
説明する。

従来、２進データA₁₆〜A₁（A₁₆：MSB）の
MSBから数えて最初に値が“１”から“０”に
反転する桁を検出し、４ビツトの２進データZ₄〜
Z₁として出力する回路は第１図の構成をとつてい
る。１はデータA₁₆〜A₁を入力として、ビツトが
最初に“１”から“０”に反転した桁から下位の
桁すべてを“０”にセツトするANDアレイ
（ARRAY）回路であり、この回路の出力をB₁₆〜
B₁とする。回路１の機能を具体的に説明する
と、前段のANDゲートの出力Ｂ_iとＡ_i-1が次段の
ANDゲートに入力され、その結果出力Ｂ_i-1がＢ_i-1＝｛Ｂ_i〓Ａ_i-1｝（ｉ＝16，……，２）として得られるものである。ただしB₁₆＝A₁₆であ
る。２は出力B₁₆〜B₁を入力として、反転桁のみ
“１”を、他の桁にはすべて“０”を出力する
EXCLUSIVE−ORアレイ回路である。この回路
の出力をC₁₆〜C₁とする。ただしC₁＝B₁である。
３は出力C₁₆〜C₁を入力として、これを２進符号
に変換する回路で、出力Z₄〜Z₁は、データA₁₆〜
A₁の値がMSBから数えて最初に反転する桁は何
桁目であるかを示す。

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

本発明は、上記の欠点を解決するために、
ANDアレイの機能を高速に実行する回路を用い
ることによつて、エンコーダ回路の高速化を図る
ことを特徴としたもので、以下これを具体的に説
明する。

第２図は、ANDアレイ回路１と同一の機能を
高速に実行する回路を含む本発明の一実施例であ
る。これは16ビツトのANDアレイを２，３，
３，４，４ビツトの部分ANDアレイS₁，S₂，
S₃，S₄，S₅に分割し、上位ビツトに対応する部分
アレイの出力が“１”である場合と“０”である
場合の両方について、あらかじめ部分アレイ内の
各桁の入力Ａ_iに対する出力を求め、上位部分ア
レイの最下位桁の出力を受けて、その値に応じ
て、あらかじめ求めておいた出力候補を選択出力
するという機能を用いることにより、ANDアレ
イ機能の高速化を達成するものである。

第１図のANDアレイ回路１の機能は、入力A₁₆
〜A₁に対し、出力B₁₆〜B₁をＢ_i-1＝｛Ｂ_i〓Ａ_i-1｝（ｉ＝16，……，２）として出力するものであるが、ここで、入力Ａ_i-
_１が“０”である場合にはＢ_i-1＝“０”となり、次
段以降のANDゲートのＢ入力はすべて“０”と
なるから、結局、出力Ｂ_i-1が“０”である桁よ
り下位の桁において、Ｂ入力とＡ入力とのAND
をとる操作は冗長となる。

本発明においては、第ｊ桁のＢ_jが“０”であ
れば、それよりも下位部分アレイのＢ出力とし
て、ANDゲートを介することなく直ちに“０”
を選択出力するよう構成する。

この機能を実現するための各部分アレイを構成
するセル１１〜２６の具体的な構成を第３図に示
す。第３図ａは、各部分アレイの最上位桁に対応
するセルで、上位部分アレイの出力を入力Ｂ_INと
し、その桁の入力をＡ_INとしたときに、Ｂ_INの値
に応じて、その桁の出力Ｂ_OUTを選択する回路で
ある。こののセルは、アースに接続された一定出
力（第１の候補出力）と、入力Ａ_INに対応した出
力（第２の候補出力）を出力する部分３１を有
し、さらにこれらの出力を選択する選択回路３２
を有している。入力Ｂ_INが“０”のときはスイツ
チとして図に示されている選択回路３２は点ａと
ｂを接続して第１の候補出力を選択し、入力Ｂ_IN
が“１”のときは点ａとｃを接続して第２の候補
出力を選択する。この選択回路３２はCMOS回路
で構成することができ、その場合、トランスフア
ーゲートが使用できる。

第３図ｂは、同一アレイ内の隣接する上位セル
からの出力Ｓ_Oを入力Ｓ_Iとし、その桁の入力をＡ
_INとしたとき、二者のANDをとつた出力Ｓ_Oと、
隣接上位セルからの出力が“０”である場合のそ
の桁の出力（すなわち“０”）とを、上位部分ア
レイの出力Ｂ_INの値に応じて選択する機能を持つ
たセルである。具体的にはこのセルは、アースに
接続された一定出力（第１の候補出力）と、入力
Ｓ_IとＡ_INとのANDをとるAND回路３５の出力
（第２の候補出力）を出力し得る回路３３を有
し、さらに、これらの２つの出力を上位部分アレ
イの出力Ｂ_INの値に応じて選択する選択回路３４
を有している。この選択回路３４は前記の選択回
路３２と同じ構成のものである。このような構成
に基づく本実施例の回路の演算時間を見積もると
以下のようになる。ただし、第３図ｂのANDゲ
ートの遅延時間をＴ、セル中の選択回路の遅延時
間を0.5Tとする。以下、本回路の最大遅延を与
える経路について時間を追つて説明する。

まず、ｔ＝０で入力A₁₆〜A₁が定まるものとす
る。ｔ＝Ｔではセル１２内のANDゲートの出力
が定まり、ｔ＝1.5TでB₁₅が定まる。また、ｔ＝
2Tでセル１５のANDゲートの出力が定まるか
ら、ｔ＝2.5TでB₁₂が定まる。

一方、部分アレイS₃においてはｔ＝2Tでセル
１８のANDゲート出力が定まつているから、B₁₂
が定まると直ちにセル１８の選択回路を駆動し、
その結果ｔ＝3TでB₉が定まる。また、ｔ＝3Tで
セル２２のAND出力が定まるから、セル２２の
選択回路をB₉が駆動することによりｔ＝3.5Tで
B₅が定まる。B₅はただちにセル２６の選択回路
を駆動し、その結果ｔ＝4TでB₁が定まる。

以上、最大遅延経路についてのみ触れたが、
B₁₅，B₁₂，B₉およびB₅は次段の部分アレイの各桁
に同時に入力されるため、そのアレイ内の各桁の
選択回路は同時に動作することになる。従つて、
同一の部分アレイ内に属するＢ出力は同時に出力
される。すなわち、ｔ＝０でA₁₆〜A₁が入力され
たとき、ｔ＝1.5TでB₁₆，B₁₅ ｔ＝2.5TでB₁₄，B₁₃，B₁₂ ｔ＝3TでB₁₁，B₁₀，B₉ ｔ＝3.5TでB₈，B₇，B₆，B₅ ｔ＝4TでB₄，B₃，B₂，B₁ がそれぞれ定まる。

また、一般に、選択回路の遅延時間をαＴ（α
＞０）としたときのデータの桁配分については、
部分アレイ数をｎ、最下位部分アレイの桁数をｍ
としたときに、ｍ（ｎ−１）α となることを目安に、データの桁配分および部分
アレイ数の最適化を行えば、最下位部分アレイの
最下位桁ANDゲートと、上位部分アレイのＢ出
力が同時に定まることになり、従つて、A₁₆〜A₁
入力後ｎαＴの遅延でB₁₆〜B₁が定まる。

B₁₆〜B₁は、B₁₆とB₁₅，B₁₅とB₁₄，B₁₄とB₁₃，…
…，B₂とB₁のペアでEXCLUSIVE−ORアレイ回
路２に並列的に入力され、出力としてC₁₆〜C₂が
定まる。ただしC₁＝B₁となる。C₁₆〜C₁は、A₁₆
〜A₁のうち、MSBから数えて最初に値が反転す
る桁に対応する桁のみ“１”で、その他の桁は
“０”であるようなデータである。

C₁₆〜C₁は16−４ビツト２進変換回路３に入力
され、その結果出力Z₄〜Z₁が得られる。

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

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

以上説明した回路の効果を具体的に示す。

従来のエンコーダ回路において、データA₁₆〜
A₁を入力後、Z₄〜Z₁を出力するまでに要する時間
Ｔ_Eは、Ｔ_E＝Ｔ_AR＋Ｔ_EX＋Ｔ_Z ただし、Ｔ_ARはANDアレイ回路１、Ｔ_EXは
EXCLUSIVE−ORゲート、Ｔ_Zは16−４ビツト２
進変換回路３のそれぞれ遅延時間である。ここ
で、Ｔ_EXＴ，Ｔ_Z5Tとすれば、従来のANDア
レイ回路においはＴ_AR＝15Tであるから、結局Ｔ
_E21Tとなる。ここで第２図の高速ANDアレイ
回路を用いれば、Ｔ_AR＝4Tとなり、その結果Ｔ_E
10Tとなり、エンコーダ回路全体の遅延時間は
従来の約50％となるから、その高速化は明らかで
ある。

本発明のエンコーダ回路は、例えば高速な演算
回路における正規化回路に適用することができ
る。正規化回路は演算結果の桁落ちを判定し、そ
の落ちた桁数だけデータをシフトする機能を有す
るが、本エンコーダ回路の入力A₁₆〜A₁にデータ
を入力すれば、EXCLUSIVE−OR回路２の出力
C₁₆〜C₁から、MSBから数えて桁落ちの数に対応
する桁のみに“１”が立つデータが高速に得られ
るので、その出力をシフターに導入すればよい。

あるいは、並列比較形Ａ／Ｄ変換器において、
各識別レベルに対応するコンパレータ出力が、高
レベル側からみて“０”から“１”に反転する桁
を、反転桁より低レベル側に符号誤りが生じてい
ても正しく高速に検出する回路に適用できる。

【図面の簡単な説明】

第１図は従来の16ビツトエンコーダ回路、第２
図は本発明のエンコーダ回路、第３図はアレイ中
のセルである。１……ANDアレイ回路、２……EXCLUSIVE
−ORアレイ回路、３……16−４ビツト２進変換
回路、１１〜２６……セル。

Claims

【特許請求の範囲】１Ｎ桁（Ｎ＞１）の入力２進データの桁数に応
じた数のセルからなるアレイを有し、該アレイは複数個の部分アレイに分割され、下
位の桁に対応する部分アレイは上位の桁に対応す
る部分アレイの桁数と同じまたはそれ以上の桁数
に対応するセルを有し、前記各セルは、当該桁の入力２進データにかか
わらず一定である第１の候補出力および当該桁の
入力２進データに対応した第２の候補出力をそれ
ぞれ出力し得る第１の回路と、上位に位置する部
分アレイの最下位桁の出力により、第１の回路の
前記２つの候補出力から１つの出力を選択して出
力する第２の回路とを有し、さらに、このようにして出力された信号の互い
に隣り合う桁同士のEXCLUSIVE−ORをとつて
その結果を出力する第３の回路と、第３の回路の
出力を入力とし、それをＭ桁（Ｍ＞１）の２進デ
ータに変換して出力する第４の回路を有すること
を特徴とするエンコーダ回路。