(57)【要約】【課題】基本となる桁数のモジュール内では桁借り、桁上げが伝搬しないＮ桁加減算器ユニット及びＮ桁加減算器モジュールを提供する。【解決手段】本発明は、加減算器のうち特に加減算の規則性に基づき、被加減数と加減数の関係から加減算結果の出力パターンを予見し、基本となる桁数のモジュール内では桁借り、桁上げが伝搬しないＮ桁加減算器ユニット及びそれを用いたＮ桁加減算器モジュールを特徴とする。【選択図】図８
2009301210.tif 000002
【特許請求の範囲】
【請求項１】
１桁目の被減数Ｘ０の入力、減数Ｙ０の入力の組み合わせ（０，０）、（０，１）、（１，０）、（１，１）に対して、上位２桁目に順に０、１、０、０にて上位桁借り出力Ｂｏｕｔ（０）を出力する論理回路と、前記１桁目の被減数Ｘ０の入力、減数Ｙ０の入力の組み合わせ（０，０）、（０，１）、（１，０）、（１，１）に対して排他的ＯＲ論理にて順に０、１、１、０を１桁目出力Ｏｕｔ０として出力する排他的ＯＲ回路とを１桁目減算回路とし、
２桁目以上のｉ桁の被減数Ｘｉ−１の入力、減数Ｙｉ−１の入力及び下位ｉ−１桁からの桁借り出力Ｂｏｕｔ（ｉ−２）の有りで１、無しで０を入力する桁借りビットの入力の組み合わせ（０，０，０）、（０，０，１）、（０，１，０）、…、（１，１，０）、（１，１，１）に対して、上位ｉ＋１桁への桁借り有りで１、無しで０を順に０、１、１、１、０、０、０、１にて上位桁借り出力Ｂｏｕｔ（ｉ−１）を出力する桁借り回路と、前記ｉ桁の被減数Ｘｉ−１の入力、減数Ｙｉ−１の入力及び下位（ｉ−１）桁の桁借り回路からの桁借り出力Ｂｏｕｔ（ｉ−２）を入力し、排他的ＯＲ論理にてｉ桁出力Ｏｕｔｉ−１を出力する３入力排他的ＯＲ回路とを上位桁減算回路とし、
２桁目から任意のＮ桁目までの（Ｎ−１）桁について（Ｎ−１）個の前記上位桁減算回路をカスケードに接続し、前記１桁目減算回路をそのＢｏｕｔ（０）が前記２桁目の上位桁減算回路における桁借り回路の桁借りビットの入力となるように接続し、Ｎ桁目の上位桁減算回路における上位桁借り出力Ｂｏｕｔ（Ｎ−１）をＮ桁減算器の桁借り出力Ｂｏｕｔとすることを特徴とするＮ桁減算器ユニット。
【請求項２】
前記上位桁減算回路を３個と１桁目減算回路をカスケードに接続することで４桁減算を行うことを特徴とする請求項１に記載のＮ桁減算器ユニット。
【請求項３】
前記上位桁減算回路を７個と１桁目減算回路をカスケードに接続することで８桁減算を行うことを特徴とする請求項１に記載のＮ桁減算器ユニット。
【請求項４】
１桁目の被減数Ｘ０の入力、減数Ｙ０の入力の組み合わせ（０，０）、（０，１）、（１，０）、（１，１）に対して、上位２桁目に順に０、１、０、０にて上位桁借り出力Ｂｏｕｔ（０）を出力する論理回路と、前記１桁目の被減数Ｘ０の入力、減数Ｙ０の入力の組み合わせ（０，０）、（０，１）、（１，０）、（１，１）に対して排他的ＯＲ論理にて順に０、１、１、０を１桁目出力Ｏｕｔ０として出力する排他的ＯＲ回路とを１桁目減算回路とし、２桁目以上のｉ桁の被減数Ｘｉ−１の入力、減数Ｙｉ−１の入力及び下位ｉ−１桁からの桁借り出力Ｂｏｕｔ（ｉ−２）の有りで１、無しで０を入力する桁借りビットの入力の組み合わせ（０，０，０）、（０，０，１）、（０，１，０）、…、（１，１，０）、（１，１，１）に対して、上位ｉ＋１桁への桁借り有りで１、無しで０を順に０、１、１、１、０、０、０、１にて上位桁借り出力Ｂｏｕｔ（ｉ−１）を出力する桁借り回路と、前記ｉ桁の被減数Ｘｉ−１の入力、減数Ｙｉ−１の入力及び下位（ｉ−１）桁の桁借り回路からの桁借り出力Ｂｏｕｔ（ｉ−２）を入力し、排他的ＯＲ論理にてｉ桁出力Ｏｕｔｉ−１を出力する３入力排他的ＯＲ回路とを上位桁減算回路とし、２桁目から任意のＮ桁目までの（Ｎ−１）桁について（Ｎ−１）個の前記上位桁減算回路をカスケードに接続し、前記１桁目減算回路をそのＢｏｕｔ（０）が前記２桁目の上位桁減算回路における桁借り回路の桁借りビットの入力となるように接続し、Ｎ桁目の上位桁減算回路における上位桁借り出力Ｂｏｕｔ（Ｎ−１）をＮ桁減算器の桁借り出力ＢｏｕｔとするＮ桁減算器ユニットと、
１〜Ｎ桁の各桁ｉの被減数Ｘｉ−１、減数Ｙｉ−１それぞれを一方の入力とし、外部から桁借りビット端子に与えられる桁借りビット入力Ｂｉｎをそれぞれの他方の入力とし、排他的ＯＲの出力を改めて前記Ｎ桁減算器ユニットの被減数Ｘｉ−１、減数Ｙｉ−１の入力とする２Ｎ個の入力側排他的ＯＲ回路と、
前記Ｎ桁減算器ユニットの各桁ｉの出力Ｏｕｔｉ−１及び上位桁借りビット出力Ｂｏｕｔ（ｉ−１）それぞれを一方の入力とし、前記外部から桁借りビット端子に与えられる桁借りビット入力Ｂｉｎをそれぞれの他方の入力とし、排他的ＯＲの出力それぞれを改めてｉ桁目と上位桁への桁借りビットの出力Ｏｕｔｉ−１、Ｂｏｕｔとする出力側排他的ＯＲ回路とを備えたことを特徴とするＮ桁減算器モジュール。
【請求項５】
１桁目の被加数Ｘ０の入力、加数Ｙ０の入力の組み合わせ（０，０）、（０，１）、（１，０）、（１，１）に対してＡＮＤ論理にて上位２桁目に順に０、０、０、１の上位桁上げ出力Ｂｏｕｔ（０）を出力するＡＮＤ回路と、前記１桁目の被加数Ｘ０の入力、加数Ｙ０の入力の組み合わせ（０，０）、（０，１）、（１，０）、（１，１）に対して排他的ＯＲ論理にて順に０、１、１、０を１桁目出力Ｏｕｔ０として出力する排他的ＯＲ回路とを１桁目加算回路とし、
２桁目以上のｉ桁の被加数Ｘｉ−１の入力、加数Ｙｉ−１の入力及び下位ｉ−１桁からの桁上げ出力Ｂｏｕｔ（ｉ−２）の有りで１、無しで０を入力する桁上げビットの入力の組み合わせ（０，０，０）、（０，０，１）、（０，１，０）、…、（１，１，０）、（１，１，１）に対して、上位ｉ＋１桁への桁上げ有りで１、無しで０を０、０、０、１、０、１、１、１の順で上位桁上げ出力Ｂｏｕｔ（ｉ−１）として出力する桁上げ回路と、前記ｉ桁の被加数Ｘｉ−１の入力、加数Ｙｉ−１の入力及び下位（ｉ−１）桁の桁上げ回路からの桁上げ出力Ｂｏｕｔ（ｉ−２）を入力し、排他的ＯＲ論理にてｉ桁出力Ｏｕｔｉ−１を出力する３入力排他的ＯＲ回路とを上位桁加算回路とし、
２桁目から任意のＮ桁目までの（Ｎ−１）桁について（Ｎ−１）個の前記上位桁加算回路をカスケードに接続し、前記１桁目加算回路をそのＢｏｕｔ（０）が前記２桁目の上位桁加算回路における桁上げ回路の桁上げビットの入力となるように接続し、Ｎ桁目の上位桁加算回路における上位桁上げ出力Ｂｏｕｔ（Ｎ−１）をＮ桁加算器の桁上げ出力Ｂｏｕｔとすることを特徴とするＮ桁加算器ユニット。
【請求項６】
前記上位桁加算回路を３個と１桁目加算回路をカスケードに接続することで４桁加算を行うことを特徴とする請求項５に記載のＮ桁加算器ユニット。
【請求項７】
前記上位桁加算回路を７個と１桁目加算回路をカスケードに接続することで８桁加算を行うことを特徴とする請求項５に記載のＮ桁加算器ユニット。
【請求項８】
１桁目の被加数Ｘ０の入力、加数Ｙ０の入力の組み合わせ（０，０）、（０，１）、（１，０）、（１，１）に対してＡＮＤ論理にて上位２桁目に順に０、０、０、１の上位桁上げ出力Ｂｏｕｔ（０）を出力するＡＮＤ回路と、前記１桁目の被加数Ｘ０の入力、加数Ｙ０の入力の組み合わせ（０，０）、（０，１）、（１，０）、（１，１）に対して排他的ＯＲ論理にて順に０、１、１、０を１桁目出力Ｏｕｔ０として出力する排他的ＯＲ回路とを１桁目加算回路とし、２桁目以上のｉ桁の被加数Ｘｉ−１の入力、加数Ｙｉ−１の入力及び下位ｉ−１桁からの桁上げ出力Ｂｏｕｔ（ｉ−２）の有りで１、無しで０を入力する桁上げビットの入力の組み合わせ（０，０，０）、（０，０，１）、（０，１，０）、…、（１，１，０）、（１，１，１）に対して、上位ｉ＋１桁への桁上げ有りで１、無しで０を０、０、０、１、０、１、１、１の順で上位桁上げ出力Ｂｏｕｔ（ｉ−１）として出力する桁上げ回路と、前記ｉ桁の被加数Ｘｉ−１の入力、加数Ｙｉ−１の入力及び下位（ｉ−１）桁の桁上げ回路からの桁上げ出力Ｂｏｕｔ（ｉ−２）を入力し、排他的ＯＲ論理にてｉ桁出力Ｏｕｔｉ−１を出力する３入力排他的ＯＲ回路とを上位桁加算回路とし、２桁目から任意のＮ桁目までの（Ｎ−１）桁について（Ｎ−１）個の前記上位桁加算回路をカスケードに接続し、前記１桁目加算回路をそのＢｏｕｔ（０）が前記２桁目の上位桁加算回路における桁上げ回路の桁上げビットの入力となるように接続し、Ｎ桁目の上位桁加算回路における上位桁上げ出力Ｂｏｕｔ（Ｎ−１）をＮ桁加算器の桁上げ出力ＢｏｕｔとするＮ桁加算器ユニットと、
１〜Ｎ桁の各桁ｉの被加数Ｘｉ−１、加数Ｙｉ−１それぞれを一方の入力とし、外部から桁上げビット端子に与えられる桁上げビット入力Ｂｉｎをそれぞれの他方の入力とし、排他的ＯＲの出力を改めて前記Ｎ桁加算器ユニットの被加数Ｘｉ−１、加数Ｙｉ−１の入力とする２Ｎ個の入力側排他的ＯＲ回路と、
前記Ｎ桁加算器ユニットの各桁ｉの出力Ｏｕｔｉ−１及び上位桁上げビット出力Ｂｏｕｔ（ｉ−１）それぞれを一方の入力とし、前記外部から桁上げビット端子に与えられる桁上げビット入力Ｂｉｎをそれぞれの他方の入力とし、排他的ＯＲの出力それぞれを改めてｉ桁目と上位桁への桁上げビットの出力Ｏｕｔｉ−１、Ｂｏｕｔとする出力側排他的ＯＲ回路とを備えたことを特徴とするＮ桁加算器モジュール。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、Ｎ桁減算器ユニット、Ｎ桁減算器モジュール、Ｎ桁加算器ユニット及びＮ桁加算器モジュールに関する。
【背景技術】
【０００２】
算術演算の基本となる加減算器のような演算器はこれまで用途に応じていろいろな方式が考案されてきた（非特許文献１）。最も一般的な方式には桁上げ伝搬方式があるが、桁上げが各桁間を伝搬するため、伝搬遅延とゲート数（面積）が桁数に比例する（非特許文献２）。
【０００３】
演算速度に関しては最も高速な方式の冗長２進表現を用いた手法では１桁を２ビットで表現するため多くのゲート数を要する(非特許文献３，４)。先見桁上げ方式では加算と並行して桁上げ／桁借り分を処理するため比較的高速処理が可能であるが、桁数が多くなった場合の面積増及び分散処理化には不向きである。
【非特許文献１】Kai Hwang : "Computer Arithmetic-PRINCIPLES, ARCHI-TECTUR AND DESIGN”, John Wiley & Sons, Inc (1979)
【非特許文献２】中村次男、「ディジタル回路の基礎」、日本理工出版会、１９９２年
【非特許文献３】Tsugio Nakamura, Kazuhiro Abe, Narito Fuyutsume, Hiroshi Kasahara, and Teruo Tanaka: ”Super-high Speed, Accuracy, and Modularized Residue Number System based on Redundant Binary Representation”, IEEJ Trans.EIS, Vol.125, No.6, pp.876-886 (2005)
【非特許文献４】Yoshitaka Tsunekawa, Mitsuki Hinosugi, Masato Saito, Katsumi Abukawa, and Mamoru Miura : ”High-Performance Redundant Binary Adder Representing Each Digit by Hybrid 2 Bits /3 Bits and Its Application to Multiplier”, T.IEE Japan, Vol.119-C, No.5, pp.644-653 (1999)
【非特許文献５】恒川佳隆・日野杉充希・斉藤正人・虻川勝巳・三浦守、「１桁２ビット／３ビット混合型高性能冗長２進加算器とその乗算器への応用」、電学論Ｃ、Vol.119-C,No.5, pp.644-653 (1999)
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明は、加減算の規則性に基づき、被減数と減数との関係から減算結果の出力パターンを予見し、また、被加数と加数との関係から加算結果の出力パターンを予見し、基本となる桁数のモジュール内では桁借りが伝搬しないＮ桁減算器ユニット、Ｎ桁減算器モジュール、Ｎ桁加算器ユニット及びＮ桁加算器モジュールを提供することを目的とする。
【課題を解決するための手段】
【０００５】
本発明の１つの特徴は、１桁目の被減数Ｘ０の入力、減数Ｙ０の入力の組み合わせ（０，０）、（０，１）、（１，０）、（１，１）に対して、上位２桁目に順に０、１、０、０にて上位桁借り出力Ｂｏｕｔ（０）を出力する論理回路と、前記１桁目の被減数Ｘ０の入力、減数Ｙ０の入力の組み合わせ（０，０）、（０，１）、（１，０）、（１，１）に対して排他的ＯＲ論理にて順に０、１、１、０を１桁目出力Ｏｕｔ０として出力する排他的ＯＲ回路とを１桁目減算回路とし、２桁目以上のｉ桁の被減数Ｘｉ−１の入力、減数Ｙｉ−１の入力及び下位ｉ−１桁からの桁借り出力Ｂｏｕｔ（ｉ−２）の有りで１、無しで０を入力する桁借りビットの入力の組み合わせ（０，０，０）、（０，０，１）、（０，１，０）、…、（１，１，０）、（１，１，１）に対して、上位ｉ＋１桁への桁借り有りで１、無しで０を順に０、１、１、１、０、０、０、１にて上位桁借り出力Ｂｏｕｔ（ｉ−１）を出力する桁借り回路と、前記ｉ桁の被減数Ｘｉ−１の入力、減数Ｙｉ−１の入力及び下位（ｉ−１）桁の桁借り回路からの桁借り出力Ｂｏｕｔ（ｉ−２）を入力し、排他的ＯＲ論理にてｉ桁出力Ｏｕｔｉ−１を出力する３入力排他的ＯＲ回路とを上位桁減算回路とし、２桁目から任意のＮ桁目までの（Ｎ−１）桁について（Ｎ−１）個の前記上位桁減算回路をカスケードに接続し、前記１桁目減算回路をそのＢｏｕｔ（０）が前記２桁目の上位桁減算回路における桁借り回路の桁借りビットの入力となるように接続し、Ｎ桁目の上位桁減算回路における上位桁借り出力Ｂｏｕｔ（Ｎ−１）をＮ桁減算器の桁借り出力ＢｏｕｔとするＮ桁減算器ユニットである。
【０００６】
上記発明のＮ桁減算器ユニットにおいて、前記上位桁減算回路を３個と１桁目減算回路をカスケードに接続することで４桁減算器ユニットを構成できる。
【０００７】
また、上記発明のＮ桁減算ユニットにおいて、前記上位桁減算回路を７個と１桁目減算回路をカスケードに接続することで８桁減算器ユニットを構成できる。
【０００８】
本発明の別の特徴は、１桁目の被減数Ｘ０の入力、減数Ｙ０の入力の組み合わせ（０，０）、（０，１）、（１，０）、（１，１）に対して、上位２桁目に順に０、１、０、０にて上位桁借り出力Ｂｏｕｔ（０）を出力する論理回路と、前記１桁目の被減数Ｘ０の入力、減数Ｙ０の入力の組み合わせ（０，０）、（０，１）、（１，０）、（１，１）に対して排他的ＯＲ論理にて順に０、１、１、０を１桁目出力Ｏｕｔ０として出力する排他的ＯＲ回路とを１桁目減算回路とし、２桁目以上のｉ桁の被減数Ｘｉ−１の入力、減数Ｙｉ−１の入力及び下位ｉ−１桁からの桁借り出力Ｂｏｕｔ（ｉ−２）の有りで１、無しで０を入力する桁借りビットの入力の組み合わせ（０，０，０）、（０，０，１）、（０，１，０）、…、（１，１，０）、（１，１，１）に対して、上位ｉ＋１桁への桁借り有りで１、無しで０を順に０、１、１、１、０、０、０、１にて上位桁借り出力Ｂｏｕｔ（ｉ−１）を出力する桁借り回路と、前記ｉ桁の被減数Ｘｉ−１の入力、減数Ｙｉ−１の入力及び下位（ｉ−１）桁の桁借り回路からの桁借り出力Ｂｏｕｔ（ｉ−２）を入力し、排他的ＯＲ論理にてｉ桁出力Ｏｕｔｉ−１を出力する３入力排他的ＯＲ回路とを上位桁減算回路とし、２桁目から任意のＮ桁目までの（Ｎ−１）桁について（Ｎ−１）個の前記上位桁減算回路をカスケードに接続し、前記１桁目減算回路をそのＢｏｕｔ（０）が前記２桁目の上位桁減算回路における桁借り回路の桁借りビットの入力となるように接続し、Ｎ桁目の上位桁減算回路における上位桁借り出力Ｂｏｕｔ（Ｎ−１）をＮ桁減算器の桁借り出力ＢｏｕｔとするＮ桁減算器ユニットと、１〜Ｎ桁の各桁ｉの被減数Ｘｉ−１、減数Ｙｉ−１それぞれを一方の入力とし、外部から桁借りビット端子に与えられる桁借りビット入力Ｂｉｎをそれぞれの他方の入力とし、排他的ＯＲの出力を改めて前記Ｎ桁減算器ユニットの被減数Ｘｉ−１、減数Ｙｉ−１の入力とする２Ｎ個の入力側排他的ＯＲ回路と、前記Ｎ桁減算器ユニットの各桁ｉの出力Ｏｕｔｉ−１及び上位桁借りビット出力Ｂｏｕｔ（ｉ−１）それぞれを一方の入力とし、前記外部から桁借りビット端子に与えられる桁借りビット入力Ｂｉｎをそれぞれの他方の入力とし、排他的ＯＲの出力それぞれを改めてｉ桁目と上位桁への桁借りビットの出力Ｏｕｔｉ−１、Ｂｏｕｔとする出力側排他的ＯＲ回路とを備えたＮ桁減算器モジュールである。
【０００９】
本発明のまた別の特徴は、１桁目の被加数Ｘ０の入力、加数Ｙ０の入力の組み合わせ（０，０）、（０，１）、（１，０）、（１，１）に対してＡＮＤ論理にて上位２桁目に順に０、０、０、１の上位桁上げ出力Ｂｏｕｔ（０）を出力するＡＮＤ回路と、前記１桁目の被加数Ｘ０の入力、加数Ｙ０の入力の組み合わせ（０，０）、（０，１）、（１，０）、（１，１）に対して排他的ＯＲ論理にて順に０、１、１、０を１桁目出力Ｏｕｔ０として出力する排他的ＯＲ回路とを１桁目加算回路とし、２桁目以上のｉ桁の被加数Ｘｉ−１の入力、加数Ｙｉ−１の入力及び下位ｉ−１桁からの桁上げ出力Ｂｏｕｔ（ｉ−２）の有りで１、無しで０を入力する桁上げビットの入力の組み合わせ（０，０，０）、（０，０，１）、（０，１，０）、…、（１，１，０）、（１，１，１）に対して、上位ｉ＋１桁への桁上げ有りで１、無しで０を０、０、０、１、０、１、１、１の順で上位桁上げ出力Ｂｏｕｔ（ｉ−１）として出力する桁上げ回路と、前記ｉ桁の被加数Ｘｉ−１の入力、加数Ｙｉ−１の入力及び下位（ｉ−１）桁の桁上げ回路からの桁上げ出力Ｂｏｕｔ（ｉ−２）を入力し、排他的ＯＲ論理にてｉ桁出力Ｏｕｔｉ−１を出力する３入力排他的ＯＲ回路とを上位桁加算回路とし、２桁目から任意のＮ桁目までの（Ｎ−１）桁について（Ｎ−１）個の前記上位桁加算回路をカスケードに接続し、前記１桁目加算回路をそのＢｏｕｔ（０）が前記２桁目の上位桁加算回路における桁上げ回路の桁上げビットの入力となるように接続し、Ｎ桁目の上位桁加算回路における上位桁上げ出力Ｂｏｕｔ（Ｎ−１）をＮ桁加算器の桁上げ出力ＢｏｕｔとするＮ桁加算器ユニットである。
【００１０】
上記発明のＮ桁加算モジュールにおいて、前記上位桁加算回路を３個と１桁目加算回路をカスケードに接続することで４桁加算器ユニットを構成できる。
【００１１】
また、上記発明のＮ桁加算モジュールにおいて、前記上位桁加算回路を７個と１桁目加算回路をカスケードに接続することで８桁加算器ユニットを構成できる。
【００１２】
さらに、本発明の別の特徴は、１桁目の被加数Ｘ０の入力、加数Ｙ０の入力の組み合わせ（０，０）、（０，１）、（１，０）、（１，１）に対してＡＮＤ論理にて上位２桁目に順に０、０、０、１の上位桁上げ出力Ｂｏｕｔ（０）を出力するＡＮＤ回路と、前記１桁目の被加数Ｘ０の入力、加数Ｙ０の入力の組み合わせ（０，０）、（０，１）、（１，０）、（１，１）に対して排他的ＯＲ論理にて順に０、１、１、０を１桁目出力Ｏｕｔ０として出力する排他的ＯＲ回路とを１桁目加算回路とし、２桁目以上のｉ桁の被加数Ｘｉ−１の入力、加数Ｙｉ−１の入力及び下位ｉ−１桁からの桁上げ出力Ｂｏｕｔ（ｉ−２）の有りで１、無しで０を入力する桁上げビットの入力の組み合わせ（０，０，０）、（０，０，１）、（０，１，０）、…、（１，１，０）、（１，１，１）に対して、上位ｉ＋１桁への桁上げ有りで１、無しで０を０、０、０、１、０、１、１、１の順で上位桁上げ出力Ｂｏｕｔ（ｉ−１）として出力する桁上げ回路と、前記ｉ桁の被加数Ｘｉ−１の入力、加数Ｙｉ−１の入力及び下位（ｉ−１）桁の桁上げ回路からの桁上げ出力Ｂｏｕｔ（ｉ−２）を入力し、排他的ＯＲ論理にてｉ桁出力Ｏｕｔｉ−１を出力する３入力排他的ＯＲ回路とを上位桁加算回路とし、２桁目から任意のＮ桁目までの（Ｎ−１）桁について（Ｎ−１）個の前記上位桁加算回路をカスケードに接続し、前記１桁目加算回路をそのＢｏｕｔ（０）が前記２桁目の上位桁加算回路における桁上げ回路の桁上げビットの入力となるように接続し、Ｎ桁目の上位桁加算回路における上位桁上げ出力Ｂｏｕｔ（Ｎ−１）をＮ桁加算器の桁上げ出力ＢｏｕｔとするＮ桁加算器ユニットと、１〜Ｎ桁の各桁ｉの被加数Ｘｉ−１、加数Ｙｉ−１それぞれを一方の入力とし、外部から桁上げビット端子に与えられる桁上げビット入力Ｂｉｎをそれぞれの他方の入力とし、排他的ＯＲの出力を改めて前記Ｎ桁加算器ユニットの被加数Ｘｉ−１、加数Ｙｉ−１の入力とする２Ｎ個の入力側排他的ＯＲ回路と、前記Ｎ桁加算器ユニットの各桁ｉの出力Ｏｕｔｉ−１及び上位桁上げビット出力Ｂｏｕｔ（ｉ−１）それぞれを一方の入力とし、前記外部から桁上げビット端子に与えられる桁上げビット入力Ｂｉｎをそれぞれの他方の入力とし、排他的ＯＲの出力それぞれを改めてｉ桁目と上位桁への桁上げビットの出力Ｏｕｔｉ−１、Ｂｏｕｔとする出力側排他的ＯＲ回路とを備えたＮ桁加算器モジュールである。
【発明の効果】
【００１３】
本発明によれば、先見桁上げ方式よりは演算速度は劣るが、桁上げ伝搬方式より高速であり、しかも、これらの方式に比してゲート数の抑制と演算桁数増に対して柔軟に対応可能な加減算器のユニット及びそれを周辺回路と接続した加減算器のモジュールが提供できる。
【発明を実施するための最良の形態】
【００１４】
以下、本発明の実施の形態を図に基づいて詳説する。
【００１５】
先ず、本発明の原理について述べる。最も一般的な減算器としては、図１（ａ）に示す桁借り伝搬形がある。各桁はそれぞれ並列に減算処理を行うが、同図の場合には左側の桁から右側の桁に桁借りが各桁間を伝搬していくので、最上位桁の回路が結果を出力するには最下位桁からの桁借り伝搬を待たなければならない。そのために、大きな遅延が生じてしまう。そこで、図１（ａ）と同じ４桁の減算回路でも、図１（ｂ）に示すように２桁ずつ減算回路をモジュール化すれば桁借り伝搬が１つにできる。また図１（ｃ）に示すように４桁すべてをモジュール化すれば内部の桁借り伝搬をなくすことができる。このように、モジュール化された減算回路、すなわち減算器モジュールを多段接続し、１桁ずつ計算するのではなく複数桁を同時に処理するようにすれば、桁借り伝搬の遅延時間を少なくできて高速処理が期待できる。
【００１６】
本発明の減算器モジュールは、１桁ずつ計算し、桁借りが生じた場合に上位桁に伝搬するというものではなく、被減数と減数から出力結果を予知する。例えば、４桁の減算器では被減数１００１と減数００１１という入力には、１００１−００１１なので００１１０を出力する。このようにして、被減数と減数の４組、８個のバイナリ入力値００００００００〜１１１１１１１１の全ての組み合わせそれぞれに対する出力を予知し、それを出力することで桁借りを生じず、高速な演算を可能にしている。
【００１７】
しかし、単純にこの方法で回路構成しただけでは回路の桁数が増えた場合、回路規模が増大してしまい、回路設計が困難になる。ところが、１桁〜４桁における減算器の全入出力の関係を観察すれば、桁が増えた時の入出力増に対する規則性が見られる。そこで、この規則性を利用すれば、回路の複雑化による設計の困難度を軽減できる。減算の真理値表の規則性は次の通りである。
【００１８】
［第１の実施の形態］
本発明の第１の実施の形態の２桁減算器モジュールＭＤ（２）及びその構成に用いる２桁減算器ユニットＵＮ（２）について説明する。
【００１９】
＜２桁減算における入出力の関係＞
１桁と２桁減算器の真理値表を観察していくと次のような規則性を見つけることができる。
【００２０】
（１）減算器の入出力は桁借りが０か１で全て反転している。
【００２１】
１桁減算器の真理値表である図２の表１と２桁減算器の真理値表である図３の表２において共通なパターンの規則性を説明する。表２の入出力の桁借りＢｉｎが０の部分にＡ〜Ｐの記号を割り振る。次にそれとは対称に桁借りＢｉｎが１の部分にはＰ’〜Ａ’を割り振る。この時、中心から上下対称に２つずつ入出力を見ていくと、お互いに各ビット反転の関係になっていることが分かる。例として、次のものを示す。
【数１】
2009301210.tif 000003
【００２２】
したがって、表２の下半分は上半分の反転で求めることができ、下位桁からの桁借りＢｉｎが０か１かで分かれているので、図４に示すように、このＢｉｎを判定基準とし、反転を行うかどうかの制御用として入出力に排他的ＯＲ論理の排他的ＯＲ回路ＸＯＲｉｎ，ＸＯＲｏｕｔ，ＸＯＲＢｏｕｔを介することにより、２桁減算器ユニットＵＮ（２）に組み込む真理値表の規模を半分に縮小することができる。図４において、ＵＮ（２）は図３の表２の上半分（Ａ〜Ｐ）の２桁減算の真理値表を組み込んだ２桁減算器ユニットである。
【００２３】
また、図４の入力、出力の例では、Ｂｉｎには下位桁からの桁借りがないのでＢｉｎ＝０であり、すべての排他的ＯＲ回路ＸＯＲｉｎ，ＸＯＲｏｕｔ，ＸＯＲＢｏｕｔは入力を反転させずに通過させる状態にセットされる。そして、１桁目の被減数Ｘ０＝０、減数Ｙ０＝１、２桁目の被減数Ｘ１＝０、減数Ｙ１＝１の入力、つまり、バイナリの（００−１１）の減算式の差値は「−０１」であり、上位桁からの桁借りが必要である。この減算の場合には、表２の真理値表に照らせば「Ｆ」のケースに該当し、上位桁からの桁借りＢｏｕｔ＝１、上位桁Ｏｕｔ１＝０、下位桁Ｏｕｔ０＝１が見いだせ、２桁減算器ユニットＵＮ（２）はこれを出力している。
【００２４】
（２）最下位桁は桁借りを生じないので、１桁目の被減数Ｘ０とＹ０との組み合わせのみで決まる一定の出力「０１１０」を繰り返している。
【００２５】
図５に示す表３は、前述の方法で真理値表を半分にして、入力Ｂｉｎを省略したものである。出力について考察する。それぞれ出力を４分割しブロックごとに区切ると、最下位桁（一番右の出力）Ｏｕｔ０が同じパターン「０１１０」で出力されている。これは、Ｏｕｔ０の出力に桁借りの処理が含まれないために、単純に同じ出力が繰り返されている。
【００２６】
（３）最下位桁より上位の出力もある一定の規則で増えている。
【００２７】
次に、図５の表３の出力の２桁目Ｏｕｔ１を考察すると、一番上のブロック「０１００」を基準として、その下はそのブロックの反転「１０１１」となっている。その下も同じく「１０１１」、最後に基準の「０１００」といったように、「基準」、「反転」、「反転」、「基準」といったパターンになっている。
【００２８】
最後に最上位桁のＢｏｕｔについて、この出力の最初と最後のブロックにおいては隣のＯｕｔ１と同じである。２番目、３番目ブロックにおいてはそれぞれ全部１、全部０で埋まっており、Ｏｕｔ１との出力の違いは２、３番目のブロックだけなので、回路は同じものを用い、一番左の入力Ｘ１とＹ１から、入力が「０１」なら強制的に１、「１０」なら強制的に０にする回路を通すことでＢｏｕｔの出力を簡単に得ることができる。これらの規則性は全て桁数が増えていっても適用できるので、この方法で４つのブロックに区切ることで間単に入出力を予知することができる。
【００２９】
（４）３桁以上の減算の規則性
次に１、２、３桁と出力の桁数が増加する場合の真理値表を比較する。図６は出力だけに注目した真理値表を示したものである。まずＯｕｔ０は桁数を問わず「０１１０」の繰り返しで出力されている。桁数を１つ増やした場合、横に出力が１つ増える。全出力は縦に４倍に増えるので、前の２桁の減算の真理値表で４ブロック分だったものが次の３桁の減算の真理値表の１ブロック目になっている。そして引き継がれたその１ブロック目以降の出力は前述の規則にしたがって決定される。つまり、２桁目の出力Ｏｕｔ１は、２桁減算器の出力Ｏｕｔ１を４回繰り返す。３桁目の出力Ｏｕｔ２は、２桁減算器の出力Ｏｕｔ２に対して、上から下へ順、反転、反転、順のパターンとなる。そして、４桁目最上位桁のＢｏｕｔについて、この出力の最初と最後のブロックにおいては隣りのＯｕｔ２と同じである。２番目、３番目ブロックにおいてはそれぞれ全部１、全部０で埋まっている。
【００３０】
［第２の実施の形態］
（５）８桁減算器のモジュール化
図７にこの規則を利用して構成した８桁減算器ユニットＵＮ（８）を示している。図７における符号１０で示すブロックは、表３で示す桁借りＢｏｕｔを出力する桁借り回路であり、２桁目から８桁目までの７ブロックすべて同じものである。ただし、この８桁減算器ユニットＵＮ（８）には、図４で述べた排他的ＯＲ回路による反転機構と桁借り入力Ｂｉｎは含まれていない。
【００３１】
この８桁減算器ユニットＵＮ（８）は、１桁目の被減数Ｘ０の入力、減数Ｙ０の入力の組み合わせ（０，０）、（０，１）、（１，０）、（１，１）に対して、上位２桁目に順に０、１、０、０にて上位桁借り出力Ｂｏｕｔ（０）を出力する論理回路１１０１と、１桁目の被減数Ｘ０の入力、減数Ｙ０の入力の組み合わせ（０，０）、（０，１）、（１，０）、（１，１）に対して排他的ＯＲ論理にて順に０、１、１、０を１桁目出力Ｏｕｔ０として出力する排他的ＯＲ回路１１０２とを１桁目減算回路１１として備えている。
【００３２】
また、２桁目減算回路１２として、２桁の被減数Ｘ１の入力、減数Ｙ１の入力及び下位１桁からの桁借り出力Ｂｏｕｔ０の有りで１、無しで０を入力する桁借りビットの入力の組み合わせ（０，０，０）、（０，０，１）、（０，１，０）、…、（１，１，０）、（１，１，１）に対して、３桁目への桁借り有りで１、無しで０を０、１、１、１、０、０、０、１の順で上位桁借り出力Ｂｏｕｔ（１）として出力する桁借り回路１０と、２桁の被減数Ｘ１の入力、減数Ｙ１の入力及び下位１桁目の桁借り回路である論理回路１１１からの桁借り出力Ｂｏｕｔ（０）を入力し、排他的ＯＲ論理にて２桁出力Ｏｕｔ１を出力する３入力排他的ＯＲ回路１２０１とを備えている。
【００３３】
さらに、３桁目〜８桁目減算回路１３〜１８についても、２桁目減算回路１２と同様の構成で、ｉ＝３〜８として、ｉ桁の被減数Ｘｉ−１の入力、減数Ｙｉ−１の入力及び下位桁（ｉ−１）桁の桁借り回路１０からの桁借り出力Ｂｏｕｔ（ｉ−２）の有りで１、無しで０を入力する桁借りビットの入力の組み合わせ（０，０，０）、（０，０，１）、（０，１，０）、…、（１，１，０）、（１，１，１）に対して、上位（ｉ＋１）桁への桁借り有りで１、無しで０を０、１、１、１、０、０、０、１の順で上位桁借り出力Ｂｏｕｔ（ｉ−１）として出力する桁借り回路１０と、ｉ桁の被減数Ｘｉ−１の入力、減数Ｙｉ−１の入力及び下位ｉ−１桁の桁借り回路１０からの桁借り出力Ｂｏｕｔ（ｉ−２）を入力し、排他的ＯＲ論理にてｉ桁出力Ｏｕｔｉ−１を出力する３入力排他的ＯＲ回路１３０１〜１８０１とを備えている。
【００３４】
そして、２桁目から８桁目までの７桁について７個の上位桁減算回路１２〜１８をカスケードに接続し、１桁目減算回路１１をその論理回路１１０１の出力Ｂｏｕｔ（０）が２桁目減算回路１２における桁借り回路１０の桁借りビットの入力となるように接続し、８桁目の上位桁減算回路１８における桁借り回路の桁借り出力Ｂｏｕｔ（７）をこの８桁減算器ユニットＵＮ（８）の桁借り出力Ｂｏｕｔとしている。
【００３５】
この８桁減算器ユニットＵＮ（８）を用いて構成した８桁減算回路モジュールＭＤ（８）を図８に示す。上で述べたように、中心のブロックは図７に示した８桁減算器ユニットＵＮ（８）である。この８桁減算器ユニットＵＮ（８）内の回路は真理値表の上半分に相当するため、下位桁からの桁借り入力Ｂｉｎと各ｉ桁（ｉ＝１〜８）の被減数Ｘｉ−１、減数Ｙｉ−１との排他的ＯＲをとる排他的ＯＲ回路ＸＯＲｉｎ、下位桁からの桁借り入力Ｂｉｎと各桁の差値出力Ｏｕｔｉ−１との排他的ＯＲをとる排他的ＯＲ回路ＸＯＲｏｕｔ、また下位桁からの桁借り入力Ｂｉｎと上位桁借りビット出力Ｂｏｕｔとの排他的ＯＲをとる排他的ＯＲ回路ＸＯＲＢｏｕｔよる反転機構を付加した構成である。そして、８桁減算器ユニットＵＮ（８）の各ｉ桁の被減数Ｘｉ−１、減数Ｙｉ−１は上記の排他的ＯＲ回路ＸＯＲｉｎを経た値が入力される。同様に、８桁減算器ユニットＵＮ（８）の各ｉ桁の差値出力Ｏｕｔｉ−１に対して排他的ＯＲ回路ＸＯＲｏｕｔを経た値を改めてこの８桁減算器モジュールＭＤ（８）の差値出力Ｏｕｔｉ−１としている。
【００３６】
図７に示した本実施の形態の８桁減算器ユニットＵＮ（８）、それを用いた図８の８桁減算器モジュールＭＤ（８）によれば、モジュール化により桁上げ伝搬方式のようなビット数に比例した各桁をカスケードに接続して減算器を構成することができる。
【００３７】
［第３の実施の形態］
２桁減算器ユニット、２桁減算器モジュールを一般化することで、本発明の第３の実施の形態のＮ桁減算回路ユニット、Ｎ桁減算回路モジュールが構成できる。図９には、Ｎ＝１６の１６桁減算器ユニットＵＮ（１６）を示し、図１０にはそれを用いた１６桁減算器モジュールＭＤ（１６）を示している。
【００３８】
図９に示す１６桁減算器ユニットＵＮ（１６）において、符号１１は、図７に示した第２の実施の形態の８桁減算器ユニットＵＮ（８）における１桁目の減算回路１１と同一の構成であり、論理回路１１０１と排他的ＯＲ回路１１０２にて構成されている。また、符号１２，１３，…，１ｉ，…，１１６は８桁減算器ユニットＵＮ（８）における２桁目〜８桁目の減算回路１２，１３，…，１８と同一の構成のものである。桁借り回路１０と３入力排他的ＯＲ回路１２０１，１３０１，…，１ｉ０１，…，１１６０１とで構成されている。尚、Ｎが１６以上の場合にもそのＮ−１の数だけ減算回路１ｉをカスケードに接続する。
【００３９】
そして、図１０に示す１６桁減算器モジュールＭＤ（１６）において、中心のブロックは図９に示した１６桁減算器ユニットＵＮ（１６）である。この１６桁減算器ユニットＵＮ（１６）内の回路は真理値表の上半分に相当するため、下位桁からの桁借り入力Ｂｉｎと各ｉ桁（ｉ＝１〜１６）の被減数Ｘｉ−１、減数Ｙｉ−１との排他的ＯＲをとる排他的ＯＲ回路ＸＯＲｉｎ、下位桁からの桁借り入力Ｂｉｎと各桁の差値出力Ｏｕｔｉ−１との排他的ＯＲをとる排他的ＯＲ回路ＸＯＲｏｕｔ、また下位桁からの桁借り入力Ｂｉｎと上位桁借りビット出力Ｂｏｕｔとの排他的ＯＲをとる排他的ＯＲ回路ＸＯＲＢｏｕｔよる反転機構を付加した構成である。そして、１６桁減算器ユニットＵＮ（１６）の各ｉ桁の被減数Ｘｉ−１、減数Ｙｉ−１は上記の排他的ＯＲ回路ＸＯＲｉｎを経た値が入力される。同様に、１６桁減算器ユニットＵＮ（１６）の各ｉ桁の差値出力Ｏｕｔｉ−１に対して排他的ＯＲ回路ＸＯＲｏｕｔを経た値を改めてこの１６桁減算器モジュールＭＤ（１６）の差値出力Ｏｕｔｉ−１としている。
【００４０】
図９に示した本実施の形態の１６桁減算器ユニットＵＮ（１６）、それを用いた図１０の１６桁減算器モジュールＭＤ（１６）によれば、モジュール化により桁上げ伝搬方式のようなビット数に比例した各桁をカスケードに接続して減算器を構成することができる。
【００４１】
尚、Ｎが任意の整数である場合、そのＮ桁減算器ユニットＵＮ（Ｎ）、Ｎ桁減算器モジュール（Ｎ）については、上記８桁減算器ユニットＵＮ（８）と１６桁減算器ユニットＵＮ（１６）との関係、また８桁減算器モジュールＭＤ（８）と１６桁減算器モジュールＭＤ（１６）との関係から類推できるように、次のように構成する。
【００４２】
［第４の実施の形態］
＜Ｎ桁減算器ユニットＵＮ（Ｎ）＞
１桁目の被減数Ｘ０の入力、減数Ｙ０の入力の組み合わせ（０，０）、（０，１）、（１，０）、（１，１）に対して、上位２桁目に順に０、１、０、０にて上位桁借り出力Ｂｏｕｔ（０）を出力する論理回路１１０１と、１桁目の被減数Ｘ０の入力、減数Ｙ０の入力の組み合わせ（０，０）、（０，１）、（１，０）、（１，１）に対して排他的ＯＲ論理にて順に０、１、１、０を１桁目出力Ｏｕｔ０として出力する排他的ＯＲ回路１１０２とを１桁目減算回路１１とする。２桁目以上のｉ桁の被減数Ｘｉ−１の入力、減数Ｙｉ−１の入力及び下位ｉ−１桁からの桁借り出力Ｂｏｕｔ（ｉ−２）の有りで１、無しで０を入力する桁借りビットの入力の組み合わせ（０，０，０）、（０，０，１）、（０，１，０）、…、（１，１，０）、（１，１，１）に対して、上位ｉ＋１桁への桁借り有りで１、無しで０を順に０、１、１、１、０、０、０、１にて上位桁借り出力Ｂｏｕｔ（ｉ−１）を出力する桁借り回路１０と、ｉ桁の被減数Ｘｉ−１の入力、減数Ｙｉ−１の入力及び下位（ｉ−１）桁の桁借り回路１０からの桁借り出力Ｂｏｕｔ（ｉ−２）を入力し、排他的ＯＲ論理にてｉ桁出力Ｏｕｔｉ−１を出力する３入力排他的ＯＲ回路１ｉ０１とをｉ桁目減算回路１ｉとする。そして、２桁目からＮ桁目までの（Ｎ−１）桁について（Ｎ−１）個のｉ桁目減算回路１２，１３，…，１ｉ，…，１Ｎをカスケードに接続し、１桁目減算回路１１をそのＢｏｕｔ（０）が２桁目減算回路１２における桁借り回路１０の桁借りビットの入力となるように接続し、Ｎ桁目減算回路１Ｎにおける上位桁借り出力Ｂｏｕｔ（Ｎ−１）をＮ桁減算器ユニットＵＮ（Ｎ）の桁借り出力Ｂｏｕｔとする。
【００４３】
＜Ｎ桁減算器モジュールＭＤ（Ｎ）＞
上記Ｎ桁減算器ユニットＵＮ（Ｎ）を用い、これに対して、１〜Ｎ桁の各桁ｉの被減数Ｘｉ−１、減数Ｙｉ−１それぞれを一方の入力とし、外部から桁借りビット端子に与えられる桁借りビット入力Ｂｉｎをそれぞれの他方の入力とし、排他的ＯＲの出力を改めてＮ桁減算器ユニットＵＮ（Ｎ）の被減数Ｘｉ−１、減数Ｙｉ−１の入力とする２Ｎ個の入力側排他的ＯＲ回路ＸＯＲｉｎと、Ｎ桁減算器ユニットＵＮ（Ｎ）の各桁ｉの出力Ｏｕｔｉ−１及び上位桁借りビット出力Ｂｏｕｔ（ｉ−１）それぞれを一方の入力とし、外部から桁借りビット端子に与えられる桁借りビット入力Ｂｉｎをそれぞれの他方の入力とし、排他的ＯＲの出力それぞれを改めてｉ桁目と上位桁への桁借りビットの出力Ｏｕｔｉ−１、Ｂｏｕｔ（ｉ−１）とする出力側排他的ＯＲ回路ＸＯＲｏｕｔ，ＸＯＲＢｏｕｔとを設けることで構成する。
【００４４】
このような構成のＮ桁減算器ユニットＵＮ（Ｎ）、それを用いたＮ桁減算器モジュールＭＤ（Ｎ）によれば、モジュール化により桁上げ伝搬方式のようなビット数に比例した各桁をカスケードに接続して減算器を構成することができる。
【００４５】
［第５の実施の形態］
本発明の第５の実施の形態のＮ桁加算器ユニットＡＤＵ（Ｎ）及びそれを用いたＮ桁加算器モジュールＡＤＭ（Ｎ）について、図１１〜図１４を用いて説明する。
【００４６】
＜２桁加算における入出力の関係＞
図１１の表４に示すように、２桁加算の真理値表を観察していくと次のような規則性を見つけることができる。
【００４７】
（１）加算器の入出力は桁上げが０か１で全て反転している。
【００４８】
表４の入出力の下位桁からの桁上げＣｉｎが０の部分にＡ〜Ｐの記号を割り振る。次にそれとは対称に桁上げＣｉｎが１の部分にはＰ’〜Ａ’を割り振る。この時、中心から上下対称に２つずつ入出力を見ていくと、お互いに各ビット反転の関係になっていることが分かる。例として、次のものを示す。
【数２】
2009301210.tif 000004
【００４９】
したがって、表４の下半分は上半分の反転で求めることができ、下位からの桁上げＣｉｎが０か１かで分かれているのでＣｉｎを判定基準とし、反転を行うかどうかの制御用として入出力に排他的ＯＲ回路を介することにより、真理値表の規模を半分に縮小することができる。
【００５０】
（２）最下位桁は桁上げを生じないので、ある一定の出力を繰り返している。
【００５１】
図１２の表５は前述の方法で真理値表を半分にして、入力Ｃｉｎを省略したものである。それぞれ出力を４分割しブロックごとに区切ると、最下位桁Ｏｕｔ０が同じパターンで出力されている。これは、Ｏｕｔ０の出力に桁上げの処理が含まれないために、単純に同じ出力が繰り返されている。
【００５２】
（３）最下位桁より上位の出力もある一定の規則で増えている。
【００５３】
次に、図１２の表５の出力の２桁目Ｏｕｔ１を考察すると、一番上のブロック「０００１」を基準として、その下は一番上のブロックの反転「１１１０」となっている。その下も同じく「１１１０」、最後に基準の「０００１」といったように、「基準」、「反転」、「反転」、「基準」といったパターンになっている。
【００５４】
最後に上位桁への桁上げＣｏｕｔについて、この出力の最初と最後のブロックにおいてはそれぞれ全部０、全部１で埋まっており、２番目、３番目ブロックにおいてはＯｕｔ１の出力を反転したものとなっている。そこで、２、３番目のブロックについては、Ｏｕｔ１の回路と同じものを用い、さらに強制的に出力を反転する回路を通すことでＣｏｕｔの出力を簡単に得ることができる。
【００５５】
これらの規則性は全て桁数が増えていっても適用できるので、この方法で４つのブロックに区切ることで簡単に入出力を予知することができる。
【００５６】
図１３にはＮ桁加算器ユニットＡＤＵ（Ｎ）を示し、図１４にはそれを用いたＮ桁加算器モジュールＡＤＭ（Ｎ）を示している。
【００５７】
Ｎ桁加算器ユニットＡＤＵ（Ｎ）は、１桁目の被加数Ｘ０の入力、加数Ｙ０の入力の組み合わせ（０，０）、（０，１）、（１，０）、（１，１）に対してＡＮＤ論理にて上位２桁目に順に０、０、０、１の上位桁上げ出力Ｂｏｕｔ（０）を出力するＡＮＤ回路１０１１と、１桁目の被加数Ｘ０の入力、加数Ｙ０の入力の組み合わせ（０，０）、（０，１）、（１，０）、（１，１）に対して排他的ＯＲ論理にて順に０、１、１、０を１桁目出力Ｏｕｔ０として出力する排他的ＯＲ回路１０１２とを１桁目加算回路１０１として備えている。
【００５８】
また、Ｎ桁加算器ユニットＡＤＵ（Ｎ）は、２桁目以上のｉ桁（ｉ＝２〜Ｎ）の被加数Ｘｉ−１の入力、加数Ｙｉ−１の入力及び下位ｉ−１桁からの桁上げ出力Ｂｏｕｔ（ｉ−２）の有りで１、無しで０を入力する桁上げビットの入力の組み合わせ（０，０，０）、（０，０，１）、（０，１，０）、…、（１，１，０）、（１，１，１）に対して、上位ｉ＋１桁への桁上げ有りで１、無しで０を０、０、０、１、０、１、１、１の順で上位桁上げ出力Ｂｏｕｔ（ｉ−１）として出力する桁上げ回路１００と、ｉ桁の被加数Ｘｉ−１の入力、加数Ｙｉ−１の入力及び下位（ｉ−１）桁の桁上げ回路１００からの桁上げ出力Ｂｏｕｔ（ｉ−２）を入力し、排他的ＯＲ論理にてｉ桁出力Ｏｕｔｉ−１を出力する３入力排他的ＯＲ回路１０ｉ１とをｉ桁目加算回路１０ｉとして備えている。そして、これら２桁目からＮ桁目までの（Ｎ−１）桁について（Ｎ−１）個のｉ桁加算回路１０２，１０３，…，１０ｉ，…，１０（Ｎ−１），１０Ｎをカスケードに接続し、１桁目加算回路１０１をそのＢｏｕｔ（０）が２桁目加算回路１０２における桁上げ回路１００の桁上げビットの入力となるように接続し、Ｎ桁目加算回路における上位桁上げ出力Ｂｏｕｔ（Ｎ−１）をＮ桁加算器ユニットＡＤＵ（Ｎ）の桁上げ出力Ｂｏｕｔとなるように接続している。
【００５９】
尚、図１３に拡大して示すように、各桁の桁上げ回路１００は、ＡＮＤ回路１０１，１０２，１０３と３入力ＯＲ回路１０４にて構成されている。
【００６０】
そして、このような構成のＮ桁加算器ユニットＡＤＵ（Ｎ）を用いたＮ桁加算器モジュールＡＤＭ（Ｎ）は、図１４に示すように、Ｎ桁加算器ユニットＡＤＵ（Ｎ）と、１〜Ｎ桁の各桁ｉの被加数Ｘｉ−１、加数Ｙｉ−１それぞれを一方の入力とし、外部から桁上げビット端子に与えられる桁上げビット入力Ｂｉｎをそれぞれの他方の入力とし、排他的ＯＲの出力を改めてＮ桁加算器ユニットＡＤＵ（Ｎ）の被加数Ｘｉ−１、加数Ｙｉ−１の入力とする２Ｎ個の入力側排他的ＯＲ回路ＸＯＲｉｎと、Ｎ桁加算器ユニットＡＤＵ（Ｎ）の各桁ｉの出力Ｏｕｔｉ−１及び上位桁上げビット出力Ｂｏｕｔそれぞれを一方の入力とし、外部から桁上げビット端子に与えられる桁上げビット入力Ｂｉｎをそれぞれの他方の入力とし、排他的ＯＲの出力それぞれを改めてｉ桁目と上位桁への桁上げビットの出力Ｏｕｔｉ−１、Ｂｏｕｔとする出力側排他的ＯＲ回路ＸＯＲｏｕｔ，ＸＯＲＢｏｕｔとを備えた構成である。
【００６１】
このＮ桁加算器ユニットＡＤＵ（Ｎ）、Ｎ桁加算器モジュールＡＤＭ（Ｎ）によれば、上記減算器ユニット、減算器モジュールと同様に、モジュール化により桁上げ伝搬方式のようなビット数に比例した各桁をカスケードに接続して加算器を構成することができる。
【実施例１】
【００６２】
８ビット単位の減算回路のモジュール化を行い、それをカスケード接続して演算桁数を増加できることをシミュレーションとＦＰＧＡによる試作によって確認した。Ｘｉｌｉｎｘ社のＦＰＧＡ  Ｖｉｒｔｅｘ４、ｘｃ４ｖｌｘ６０をターゲットデバイスとして動作確認を行った。設計ツールにＸｉｌｉｎｘ社ＩＳＥ  Ｆｏｕｎｄａｔｉｏｎ  ９．１ｉを、シミュレータにはＭｅｎｔｏｒ  Ｇｒａｈｐｉｃｓ社ＭｏｄｅｌＳｉｍ  ＸＥ  III  ６．２ｇを使用した。
【００６３】
ＦＰＧＡでのシミュレーションによる、既存の桁借り伝搬方式と先見桁借り方式との性能を比較した。図１５の表６、図１６の表７より、実行速度では先見桁借り方式に及ばないものの、桁借り伝搬方式よりは速く、ゲート数においては他の２方式よりも少ないゲート数で構成できることを示している。しかし、ＦＰＧＡでの実測結果であり、ＮＡＮＤゲートのセミカスタムやフルカスタムでの実装においては、桁借り伝搬方式のゲート数が最も少なく実現できる。
【００６４】
それぞれの結果をグラフ化したものを図１７、図１８に示す。両図のグラフより、ビット数の増加に伴いゲート数の差が広がっていくので、本発明の方式は多数ビットの演算や加減算器の多段構成となる乗除算器等のゲート数抑制に有効で、かつ高速演算が期待できる。図１７と図１８は４ビットのブロック先見桁借りを演算ビットに合わせて複数個接続、たとえば６４ビット演算では１６ブロックで構成した結果の特性を示したものである。その他の方式も同様なブロック（モジュール化）を行っている。
【００６５】
図１９の表８、図２０の表９、図２１のグラフ、図２２のグラフにて、全ての方式がブロック方式ではなく、４ビット、８ビット及び１６ビットで構成した場合の比較を示す。両図表より、桁借り伝搬方式はモジュール化と相違はないが、先見桁借り方式と本発明の規則性予見方式ではより高速化が進む。ゲート数に関しては、モジュール化を行わない場合と比較しても８ビットの時点で規則性予見方式が先見桁借り方式よりも少ないゲート数で構成でき、どの桁数でモジュール化を行っても本発明の規則性予見方式での構成の方がゲート数を大幅に低減できることを示している。
【００６６】
このように、本発明の実施例によれば、減算に関して、減算データの入力パターンから出力の規則性を予見し、桁借り伝搬を抑制する設計ができ、その結果、比較的高速で、かつ、ゲート数を抑え、モジュール化に向いた構成法であることが確認できた。
【産業上の利用可能性】
【００６７】
本発明は、ゲート数の低減は消費電力の低減にも影響し、モジュール化に向いた構成法であることやゲート数を抑えた設計ができることから、高集積、多段構成に向いており多くの演算や多数ビットの演算を行なう乗除算器への応用や暗号処理などへの応用が期待できる。
【図面の簡単な説明】
【００６８】
【図１】本発明の原理を説明するための減算器のブロック図。
【図２】１桁減算器の真理値表１。
【図３】２桁減算器の真理値表２。
【図４】本発明の第１の実施の形態の２桁減算器モジュールのブロック図。
【図５】２桁減算器における入出力の規則性の表３。
【図６】１桁、２桁、３桁の減算器間の出力値の規則性の説明図。
【図７】本発明の第２の実施の形態の８桁減算器ユニットのブロック図。
【図８】本発明の第２の実施の形態の８桁減算器モジュールのブロック図。
【図９】本発明の第３の実施の形態のＮ（＝１６）桁減算器ユニットのブロック図。
【図１０】本発明の第３の実施の形態のＮ（＝１６）桁減算器モジュールのブロック図。
【図１１】２桁加算器に適用される真理値表４。
【図１２】２桁加算器における入出力の規則性の表５。
【図１３】本発明の第５の実施の形態のＮ桁加算器ユニットのブロック図。
【図１４】本発明の第５の実施の形態のＮ桁加算器モジュールのブロック図。
【図１５】本発明の実施例の減算器の他の方式の減算器との遅延の比較表６。
【図１６】本発明の実施例の減算器の他の方式の減算器とのゲート数の比較表７。
【図１７】本発明の実施例の減算器の他の方式の減算器との遅延を比較して示すグラフ。
【図１８】本発明の実施例の減算器の他の方式の減算器とのゲート数を比較して示すグラフ。
【図１９】本発明の実施例の減算器と他の方式の減算器とのモジュール化しない場合の遅延の比較表８。
【図２０】本発明の実施例の減算器と他の方式の減算器とのモジュール化しない場合のゲート数の比較表９。
【図２１】本発明の実施例の減算器と他の方式の減算器とのモジュール化しない場合の遅延を比較して示すグラフ。
【図２２】本発明の実施例の減算器と他の方式の減算器とのモジュール化しない場合のゲート数を比較して示すグラフ。
【符号の説明】
【００６９】
ＵＮ（２）  ２桁減算器ユニット
ＵＮ（８）  ８桁減算器ユニット
ＵＮ（１６）  １６桁減算器ユニット
ＭＤ（２）  ２桁減算器モジュール
ＭＤ（８）  ８桁減算器モジュール
ＭＤ（１６）  １６桁減算器モジュール
ＡＤＵ（２）  ２桁加算器ユニット
ＡＤＵ（８）  ８桁加算器ユニット
ＡＤＵ（１６）  １６桁加算器ユニット
ＡＤＭ（２）  ２桁加算器モジュール
ＡＤＭ（８）  ８桁加算器モジュール
ＡＤＭ（１６）  １６桁加算器モジュール
１０  桁借り回路
１００  桁上げ回路
１１  １桁目減算回路
１２  ２桁目減算回路
１３  ３桁目減算回路
１８  ８桁目減算回路
１１０  １０桁目減算回路
１１６  １６桁目減算回路
１ｉ  ｉ桁目減算回路
１Ｎ  Ｎ桁目減算回路
１０１  １桁目加算回路
１０２  ２桁目加算回路
１０３  ３桁目加算回路
１０８  ８桁目加算回路
１０１０  １０桁目加算回路
１０１６  １６桁目加算回路
１０ｉ  ｉ桁目加算回路
１０Ｎ  Ｎ桁目加算回路
Ｘｉ−１  ｉ桁被減数、ｉ桁被加数
Ｙｉ−１  ｉ桁減数、ｉ桁加数
Ｏｕｔｉ−１  ｉ桁出力
Ｂｉｎ  桁借り入力、桁上げ入力
Ｂｏｕｔ  桁借り出力、桁上げ出力
【図１】
2009301210.tif 000005
【図２】
2009301210.tif 000006
【図３】
2009301210.tif 000007
【図４】
2009301210.tif 000008
【図５】
2009301210.tif 000009
【図６】
2009301210.tif 000010
【図７】
2009301210.tif 000011
【図８】
2009301210.tif 000012
【図９】
2009301210.tif 000013
【図１０】
2009301210.tif 000014
【図１１】
2009301210.tif 000015
【図１２】
2009301210.tif 000016
【図１３】
2009301210.tif 000017
【図１４】
2009301210.tif 000018
【図１５】
2009301210.tif 000019
【図１６】
2009301210.tif 000020
【図１７】
2009301210.tif 000021
【図１８】
2009301210.tif 000022
【図１９】
2009301210.tif 000023
【図２０】
2009301210.tif 000024
【図２１】
2009301210.tif 000025
【図２２】
2009301210.tif 000026