(57)【要約】【課題】演算の高速化を図り、また、小型化を図ることで並列度を高めることが可能な半導体装置を提供する。【解決手段】半導体装置２０１は、乗数を示す３ビットの第１の乗数データを受けて、ブースのアルゴリズムに従い、シフトフラグ、反転フラグおよび演算フラグを出力するデコーダＤＥＣ１，ＤＥＣ２と、被乗数を示す２ビットの第１の被乗数データと、シフトフラグ、反転フラグおよび演算フラグとを受けて、シフトフラグに基づいて第１の被乗数データの上位ビットおよび下位ビットのいずれかを選択し、選択したビットを反転フラグに基づいて反転または非反転し、反転または非反転されたデータおよび所定の論理レベルのデータのいずれかを演算フラグに基づいて選択し、第１の乗数データおよび第１の被乗数データの部分積を示す部分積データとして出力する第１の部分積算出部３１〜３８とを備える。【選択図】図１
2010165179.tif 000002
【特許請求の範囲】
【請求項１】
乗数を示す３ビットの第１の乗数データを受けて、ブースのアルゴリズムに従い、シフトフラグ、反転フラグおよび演算フラグを出力する第１のデコーダと、
被乗数を示す２ビットの第１の被乗数データと、前記シフトフラグ、前記反転フラグおよび前記演算フラグとを受けて、前記シフトフラグに基づいて前記第１の被乗数データの上位ビットおよび下位ビットのいずれかを選択し、前記選択したビットを前記反転フラグに基づいて反転または非反転し、前記反転または非反転されたデータおよび所定の論理レベルのデータのいずれかを前記演算フラグに基づいて選択し、前記第１の乗数データおよび前記第１の被乗数データの部分積を示す部分積データとして出力する第１の部分積算出部とを備える半導体装置。
【請求項２】
前記第１の被乗数データは、下位ビットである第１の被乗数ビットと、上位ビットである第２の被乗数ビットとを有し、
前記第１のデコーダは、前記第１の乗数データを受けて、ブースのアルゴリズムに従い、補数フラグをさらに出力し、
前記半導体装置は、さらに、
前記第２の被乗数ビットが下位ビットであり、第３の被乗数ビットが上位ビットである第２の被乗数データと、前記シフトフラグ、前記反転フラグおよび前記演算フラグとを受けて、前記シフトフラグに基づいて前記第２の被乗数データの上位ビットおよび下位ビットのいずれかを選択し、前記選択したビットを前記反転フラグに基づいて反転または非反転し、前記反転または非反転されたデータおよび所定の論理レベルのデータのいずれかを前記演算フラグに基づいて選択し、前記第１の乗数データおよび前記第２の被乗数データの部分積を示す部分積データとして出力する第２の部分積算出部と、
前記第１の部分積算出部から受けた前記部分積データおよび前記第２の部分積算出部から受けた前記部分積データに対して前記補数フラグに基づいて補数処理を実行し、各前記部分積データを加算する部分積加算部を備える請求項１に記載の半導体装置。
【請求項３】
前記第１の乗数データは、最下位ビットである第１の乗数ビットと、２ビット目である第２の乗数ビットと、最上位ビットである第３の乗数ビットとを有し、
前記半導体装置は、さらに、
前記第３の乗数ビットが最下位ビットである３ビットの第２の乗数データを受けて、ブースのアルゴリズムに従い、シフトフラグ、反転フラグ、演算フラグおよび補数フラグを出力する第２のデコーダと、
前記第１の被乗数データと、前記第２のデコーダからの前記シフトフラグ、前記反転フラグおよび前記演算フラグとを受けて、前記シフトフラグに基づいて前記第１の被乗数データの上位ビットおよび下位ビットのいずれかを選択し、前記選択したビットを前記反転フラグに基づいて反転または非反転し、前記反転または非反転されたデータおよび所定の論理レベルのデータのいずれかを前記演算フラグに基づいて選択し、前記第２の乗数データおよび前記第１の被乗数データの部分積を示す部分積データとして出力する第３の部分積算出部と、
前記第２の被乗数データと、前記第２のデコーダからの前記シフトフラグ、前記反転フラグおよび前記演算フラグとを受けて、前記シフトフラグに基づいて前記第２の被乗数データの上位ビットおよび下位ビットのいずれかを選択し、前記選択したビットを前記反転フラグに基づいて反転または非反転し、前記反転または非反転されたデータおよび所定の論理レベルのデータのいずれかを前記演算フラグに基づいて選択し、前記第２の乗数データおよび前記第２の被乗数データの部分積を示す部分積データとして出力する第４の部分積算出部とを備え、
前記部分積加算部は、前記第１の部分積算出部から受けた前記部分積データおよび前記第２の部分積算出部から受けた前記部分積データに対して前記第１のデコーダから受けた前記補数フラグに基づいて補数処理を実行し、前記第３の部分積算出部から受けた前記部分積データおよび前記第４の部分積算出部から受けた前記部分積データに対して前記第２のデコーダから受けた前記補数フラグに基づいて補数処理を実行し、各前記部分積データを加算する請求項２に記載の半導体装置。
【請求項４】
第１のデータおよび第２のデータの積を算出する半導体装置であって、
前記第１のデータおよび前記第２のデータを加算し、前記加算した和データを出力する加算部と、
前記第１のデータおよび前記第２のデータを減算し、前記減算した差データを出力する減算部と、
前記加算部から受けた前記和データを、前記和データを２乗した２乗データに変換して出力する第１のテーブル部と、
前記減算部から受けた前記差データを、前記差データを２乗した２乗データに変換して出力する第２のテーブル部と、
前記第１のテーブル部から受けた前記２乗データと前記第２のテーブル部から受けた前記２乗データとを減算し、前記第１のデータおよび前記第２のデータの積として出力する出力演算部とを備える半導体装置。
【請求項５】
前記第１のテーブル部は、前記加算部から受けた前記和データを、前記和データを２で除算した結果を２乗した２乗データに変換して出力し、
前記第２のテーブル部は、前記減算部から受けた前記差データを、前記差データを２で除算した結果を２乗した２乗データに変換して出力する請求項４に記載の半導体装置。
【請求項６】
前記加算部は、前記第１のデータおよび前記第２のデータを加算し、前記加算結果から１を減算した和データを出力し、
前記減算部は、前記第２のデータから前記第１のデータを減算し、前記減算結果から１を減算した差データを出力し、
前記第１のテーブル部は、前記加算部から受けた前記和データを、前記和データを２で除算した結果を２乗した２乗データに変換して出力し、
前記第２のテーブル部は、前記減算部から受けた前記差データを、前記差データを２で除算した結果を２乗した２乗データに変換して出力し、
前記出力演算部は、前記第１のテーブル部から受けた前記２乗データと前記第２のテーブル部から受けた前記２乗データとを減算し、前記減算結果および前記第１のデータを加算したデータを前記第１のデータおよび前記第２のデータの積として出力する請求項４に記載の半導体装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、半導体装置に関し、特に、演算処理を行なう半導体装置に関する。
【背景技術】
【０００２】
近年、デジタルカメラ、デジタルビデオ、ビデオ会議及び携帯電話等の普及に伴い、音声、静止画像及び動画等のマルチメディアアプリケーションのデータ量が増大している。そして、この増大したデータをリアルタイムに処理する必要が生じている。さらに、モバイル機器においては、高速処理のみならず、その携帯性から長時間駆動が可能であり、かつ小型であることが求められるようになってきた。
【０００３】
さらに、ＷＣＤＭＡ、ＪＰＥＧ（Joint  Photographic  Expert  Group）２０００およびＭＰＥＧなど新たな規格が次々と出現している。このような背景から、マルチメディアアプリケーションを処理するＬＳＩは、高速処理、低消費電力及び小面積であることが必須条件とされるため、従来はデジタルシグナルプロセッサ（ＤＳＰ）をはじめとして、固有の処理のみに特化したＡＳＩＣ（Application Specific Integrated Circuit）が利用されてきた。
【０００４】
一般にマルチメディアアプリケーションは、被処理データ間の相互依存が少ないという特徴を持つことから、並列処理によって処理効率を上げることが可能である。例として、画像圧縮形式の１つであるＪＰＥＧにおいては、圧縮対象画像の全ピクセルを８×８のブロックに区切り、これらのブロックをすべて並列に処理することが可能となっている。この並列化可能処理には、離散コサイン変換（ＤＣＴ）、量子化、ジグザグスキャンおよびランレングス処理等の並列可能アルゴリズムが含まれる。
【０００５】
ＤＳＰおよびＡＳＩＣ等の従来のＬＳＩは、これらのブロックを並列に処理するために、ＳＩＭＤ（Single  Instruction  Multiple  Data）というアーキテクチャを採用することが多い。ＳＩＭＤとは、複数の演算器（Processing  Element：ＰＥ）を内部に持ち、各ＰＥに対し同一の命令を送り、複数の異なるデータを同タイミングで並列に処理するアーキテクチャであり、マルチメディアデータ処理に適しているといえる。
【０００６】
ＳＩＭＤアーキテクチャのように並列処理を行なうアーキテクチャでは、演算器（ＰＥ）のビット長を小さくし、小面積で実装し、その並列度を高めることで、処理能力の向上を図ることができる。しかしながら、ＰＥのビット幅を小さく設計すると並列度を高めやすい一方で、乗算等の処理に多くのクロックサイクルがかかってしまうという問題がある。乗算処理はマルチメディア処理で多く用いられる処理の一つであり、乗算器を少ないビット数かつ小面積で実現しながら、高速演算を実現することで、静止画像、動画像および音声などの処理の効率化を図ることができ、ユーザのニーズを満たすことができる。
【０００７】
図２０は、ビットパラレル方式を示す図である。図２１は、ビットシリアル方式を示す図である。
【０００８】
一般にＤＳＰおよび各種ＳＩＭＤアーキテクチャを利用したデータの処理方法は、図２０に示すように各ワードをいくつかのブロックに分けて並列に処理する方法（以下、ビットパラレル方式と呼ぶ）、および図２１に示すように、すべてのワードを逐次処理する方式（以下、ビットシリアル方式と呼ぶ）の２通りが挙げられる。以下に各々の特徴を述べる。
【０００９】
［ビットパラレル方式］
１）１ワードのビット長にあわせた複数のＰＥを設けるため、１ワードを１クロックサイクル程度で処理することが可能。
２）ブロック個数ｂ分、１度に複数のワードを処理可能。
３）処理ビット幅は一定であるため、アプリケーションによっては演算に使用しないＰＥが生ずる。
４）１ワードのビット長ｄが大きいほど、１ブロックを処理するために必要なＰＥの個数が増加し、並列度を上げるためにはより多くのハードウェアリソースを必要とする。
５）１ワードを１クロックサイクルで処理する場合には、すべてのワードを処理するためにａクロックサイクルが必要となる。
６）必要なＰＥの個数は、（ｄ×ｂ）個となる。
【００１０】
［ビットシリアル方式］
１）１ワードに対し、１〜２ビット長のＰＥを用意するため、１ワードをほぼビット長ｄと同程度のクロックサイクルで処理することが可能。
２）１回の処理でワード個数（ａ×ｂ）分、並列に処理が可能。
３）処理ビット幅が可変であるため、アプリケーションにあわせてＰＥを有効に利用可能。
４）１ワードに必要なＰＥの個数が少ないため、並列度を上げた場合にもハードウェアリソースをそれほど消費しない。
５）データの処理方向を変える必要がある。
６）すべてのワードを処理するためにはｄクロックサイクルが必要となる。
７）必要なＰＥの個数は、（ａ×ｂ）個となる。
【００１１】
マルチメディアアプリケーション処理は、主に処理ビット幅が可変であり、処理ワード数が非常に多いという特徴があり、高速にマルチメディアアプリケーション処理を行なうためには、極力ｂを大きくし、ａを小さくすることが理想である。すなわち、ｄ≪ｂの関係が成り立てばよく、これまでビットシリアル方式はマルチメディアアプリケーションを効率よく処理するアーキテクチャとして考えられてきた。
【００１２】
ビットシリアル演算を行なう構成として、たとえば、特許文献１には、以下のような半導体装置が開示されている。すなわち、行列状に配列されかつ複数のエントリに分割される複数のメモリセルを有するメモリセルアレイ、各上記エントリに対応して配置され、各々が指定された演算を対応のエントリのデータに対して行なう複数の第１の演算回路、各上記エントリと対応の第１の演算回路との間でデータを転送する複数のデータ転送線、および上記複数のデータ転送線それぞれに対応して配置され、対応のデータ転送線と対応の第１の演算回路との間でビット単位でかつエントリパラレル態様でデータを転送する複数のデータ転送回路を備え、各上記エントリには多ビットデータが格納され、各上記第１の演算回路は対応のエントリの多ビットデータに対してビットシリアルな態様で演算を実行する。
【先行技術文献】
【特許文献】
【００１３】
【特許文献１】特開２００６−１２７４６０号公報
【発明の概要】
【発明が解決しようとする課題】
【００１４】
しかしながら、１ビットシリアル演算では加算および減算等の処理はビット長と同程度のクロックサイクルで処理可能である一方で、乗算処理および除算処理はビット長の２乗以上のクロックサイクルがかかってしまう。ここで、クロックサイクルを短くするために、演算器のビット長を多くすることが考えられる。しかしながら、ビット長を多くすると、クロックサイクル数は減少するものの、回路面積が大きくなり並列度が高められないという問題が発生する。
【００１５】
それゆえに、本発明の目的は、演算の高速化を図り、また、小型化を図ることで並列度を高めることが可能な半導体装置を提供することである。
【課題を解決するための手段】
【００１６】
本発明の一実施例の形態の半導体装置は、要約すれば、デコーダが、ブースのアルゴリズムに従い、シフトフラグ、反転フラグおよび演算フラグを出力する。そして、部分積算出部が、デコーダから受けた各フラグに基づいて、乗数データおよび被乗数データの部分積を示す部分積データを出力する。
【発明の効果】
【００１７】
本発明の一実施例の形態によれば、演算の高速化を図り、また、小型化を図ることで並列度を高めることができる。
【図面の簡単な説明】
【００１８】
【図１】本発明の第１の実施の形態に係る半導体装置の構成を示す図である。
【図２】本発明の第１の実施の形態に係る半導体装置におけるブースデコーダの構成を示す回路図である。
【図３】ブースデコーダの真理値表を示す図である。
【図４】本発明の第１の実施の形態に係る半導体装置におけるセレクタセルの構成を示す回路図である。
【図５】セレクタセルの真理値表を示す図である。
【図６】本発明の第１の実施の形態に係る半導体装置におけるシフト加算回路の構成を示す回路図である。
【図７】本発明の第１の実施の形態に係る半導体装置の変形例の構成を示す図である。
【図８】本発明の第１の実施の形態に係る半導体装置が行なう乗算処理のフローを示す図である。
【図９】本発明の第１の実施の形態に係る半導体装置が行なう乗算処理以外の演算の基本概念を示す図である。
【図１０】本発明の第１の実施の形態に係る半導体装置が行なう加算処理のフローを示す図である。
【図１１】本発明の第１の実施の形態に係る半導体装置が行なう減算処理のフローを示す図である。
【図１２】本発明の第１の実施の形態に係る半導体装置が行なう補数処理のフローを示す図である。
【図１３】本発明の第１の実施の形態に係る半導体装置が行なう反転処理のフローを示す図である。
【図１４】本発明の第１の実施の形態に係る半導体装置が行なう１ビットシフト処理のフローを示す図である。
【図１５】本発明の第１の実施の形態に係る半導体装置が行なう２ビットシフト処理のフローを示す図である。
【図１６】本発明の第１の実施の形態に係る半導体装置が行なう３ビットシフト処理のフローを示す図である。
【図１７】本発明の第２の実施の形態に係る半導体装置の構成を示す図である。
【図１８】本発明の第２の実施の形態に係る半導体装置における加減算部の構成を示す図である。
【図１９】本発明の第２の実施の形態に係る半導体装置における出力演算部９５の構成を示す図である。
【図２０】ビットパラレル方式を示す図である。
【図２１】ビットシリアル方式を示す図である。
【発明を実施するための形態】
【００１９】
以下、本発明の実施の形態について図面を用いて説明する。なお、図中同一または相当部分には同一符号を付してその説明は繰り返さない。
【００２０】
＜第１の実施の形態＞
図１は、本発明の第１の実施の形態に係る半導体装置の構成を示す図である。
【００２１】
図１を参照して、半導体装置２０１は、ブースデコーダＤＥＣ１，ＤＥＣ２と、レジスタ１１〜２１と、セレクタセル（部分積算出回路）３１〜３８と、シフト加算回路（部分積加算回路）４０とを備える。図１において、乗数を示すデータＹ０〜Ｙ３および被乗数を示すデータＸ０〜Ｘ３は、いずれも番号の小さい方が下位ビットを示し、ＬＳＢはデータＹ０およびデータＸ０であり、ＭＳＢはデータＹ３およびデータＸ３である。
【００２２】
以下、ブースデコーダＤＥＣ１，ＤＥＣ２の各々をブースデコーダＤＥＣと称する場合がある。セレクタセル３１〜３８の各々をセレクタセルＳＥＬと称する場合がある。
【００２３】
半導体装置２０１は、たとえば４ビットシリアル乗算器であり、４ビット×４ビットごとにシーケンシャルに乗算を行なう。
【００２４】
ブースデコーダＤＥＣ１は、乗数を示すデータＹ０，Ｙ１、およびレジスタ２１からのデータを受けて、ブースのアルゴリズムに従い、シフトフラグＤ、演算フラグＮ、反転フラグＦおよび補数フラグＣ１をレジスタ１６〜１８およびシフト加算回路４０へそれぞれ出力する。
【００２５】
レジスタ１６は、ブースデコーダＤＥＣ１から受けたシフトフラグＤを保持するとともにセレクタセル３１〜３４へ出力し、かつ保持したシフトフラグＤの論理レベルを反転したデータをセレクタセル３１〜３４へ出力する。
【００２６】
レジスタ１７は、ブースデコーダＤＥＣ１から受けた演算フラグＮを保持するとともにセレクタセル３１〜３４へ出力し、かつ保持した演算フラグＮの論理レベルを反転したデータをセレクタセル３１〜３４へ出力する。
【００２７】
レジスタ１８は、ブースデコーダＤＥＣ１から受けた反転フラグＦを保持するとともにセレクタセル３１〜３４へ出力する。
【００２８】
ブースデコーダＤＥＣ２は、乗数を示すデータＹ１，Ｙ２，Ｙ３を受けて、ブースのアルゴリズムに従い、シフトフラグＤ、演算フラグＮ、反転フラグＦおよび補数フラグＣ２をレジスタ１９〜２１およびシフト加算回路４０へそれぞれ出力する。
【００２９】
レジスタ１９は、ブースデコーダＤＥＣ２から受けたシフトフラグＤを保持するとともにセレクタセル３５〜３８へ出力し、かつ保持したシフトフラグＤの論理レベルを反転したデータをセレクタセル３５〜３８へ出力する。
【００３０】
レジスタ２０は、ブースデコーダＤＥＣ２から受けた演算フラグＮを保持するとともにセレクタセル３５〜３８へ出力し、かつ保持した演算フラグＮの論理レベルを反転したデータをセレクタセル３５〜３８へ出力する。
【００３１】
レジスタ２１は、ブースデコーダＤＥＣ２から受けた反転フラグＦを保持するとともにデータＦ２としてセレクタセル３５〜３８へ出力し、かつブースデコーダＤＥＣ１へ出力する。
【００３２】
レジスタ１２は、ＳＲＡＭから受けた被乗数を示すデータＸ０を保持するとともにセレクタセル３１、３２、３５および３６へ出力する。
【００３３】
レジスタ１３は、ＳＲＡＭから受けた被乗数を示すデータＸ１を保持するとともにセレクタセル３２、３３、３６および３７へ出力する。
【００３４】
レジスタ１４は、ＳＲＡＭから受けた被乗数を示すデータＸ２を保持するとともにセレクタセル３３、３４、３７および３８へ出力する。
【００３５】
レジスタ１５は、ＳＲＡＭから受けた被乗数を示すデータＸ３を保持するとともにセレクタセル３４および３８ならびにレジスタ１１へ出力する。
【００３６】
レジスタ１１は、レジスタ１５から受けたデータＸ３を保持するとともにセレクタセル３１および３５へ出力する。また、レジスタ１１は、外部から受けたリセット信号ＲＳＴによってリセットされる。
【００３７】
セレクタセル３１は、レジスタ１１から受けたデータ、レジスタ１２から受けたデータＸ０、レジスタ１６から受けたシフトフラグＤおよびその反転データ、レジスタ１７から受けた演算フラグＮおよびその反転データ、ならびにレジスタ１８から受けた反転フラグＦに基づいて、レジスタ１１から受けたデータが下位ビットであり、データＸ０が上位ビットである２ビットの被乗数データと、データＦ２が最下位ビットであり、データＹ０が２ビット目であり、データＹ１が最上位ビットである３ビットの乗数データとの部分積を算出し、部分積Ｓ１０としてシフト加算回路４０へ出力する。
【００３８】
セレクタセル３２は、レジスタ１２から受けたデータＸ０、レジスタ１３から受けたデータＸ１、レジスタ１６から受けたシフトフラグＤおよびその反転データ、レジスタ１７から受けた演算フラグＮおよびその反転データ、ならびにレジスタ１８から受けた反転フラグＦに基づいて、データＸ０が下位ビットであり、データＸ１が上位ビットである２ビットの被乗数データと、データＦ２が最下位ビットであり、データＹ０が２ビット目であり、データＹ１が最上位ビットである３ビットの乗数データとの部分積を算出し、部分積Ｓ１１としてシフト加算回路４０へ出力する。
【００３９】
セレクタセル３３は、レジスタ１３から受けたデータＸ１、レジスタ１４から受けたデータＸ２、レジスタ１６から受けたシフトフラグＤおよびその反転データ、レジスタ１７から受けた演算フラグＮおよびその反転データ、ならびにレジスタ１８から受けた反転フラグＦに基づいて、データＸ１が下位ビットであり、データＸ２が上位ビットである２ビットの被乗数データと、データＦ２が最下位ビットであり、データＹ０が２ビット目であり、データＹ１が最上位ビットである３ビットの乗数データとの部分積を算出し、部分積Ｓ１２としてシフト加算回路４０へ出力する。
【００４０】
セレクタセル３４は、レジスタ１４から受けたデータＸ２、レジスタ１５から受けたデータＸ３、レジスタ１６から受けたシフトフラグＤおよびその反転データ、レジスタ１７から受けた演算フラグＮおよびその反転データ、ならびにレジスタ１８から受けた反転フラグＦに基づいて、データＸ２が下位ビットであり、データＸ３が上位ビットである２ビットの被乗数データと、データＦ２が下位ビットであり、データＹ０が２ビット目であり、データＹ１が最上位ビットである３ビットの乗数データとの部分積を算出し、部分積Ｓ１３としてシフト加算回路４０へ出力する。
【００４１】
セレクタセル３５は、レジスタ１１から受けたデータ、レジスタ１２から受けたデータＸ０、レジスタ１９から受けたシフトフラグＤおよびその反転データ、レジスタ２０から受けた演算フラグＮおよびその反転データ、ならびにレジスタ２１から受けた反転フラグＦに基づいて、レジスタ１１から受けたデータが下位ビットであり、データＸ０が上位ビットである２ビットの被乗数データと、データＹ１が最下位ビットであり、データＹ２が２ビット目であり、データＹ３が最上位ビットである３ビットの乗数データとの部分積を算出し、部分積Ｓ２０としてシフト加算回路４０へ出力する。
【００４２】
セレクタセル３６は、レジスタ１２から受けたデータＸ０、レジスタ１３から受けたデータＸ１、レジスタ１９から受けたシフトフラグＤおよびその反転データ、レジスタ２０から受けた演算フラグＮおよびその反転データ、ならびにレジスタ２１から受けた反転フラグＦに基づいて、データＸ０が下位ビットであり、データＸ１が上位ビットである２ビットの被乗数データと、データＹ１が最下位ビットであり、データＹ２が２ビット目であり、データＹ３が最上位ビットである３ビットの乗数データとの部分積を算出し、部分積Ｓ２１としてシフト加算回路４０へ出力する。
【００４３】
セレクタセル３７は、レジスタ１３から受けたデータＸ１、レジスタ１４から受けたデータＸ２、レジスタ１９から受けたシフトフラグＤおよびその反転データ、レジスタ２０から受けた演算フラグＮおよびその反転データ、ならびにレジスタ２１から受けた反転フラグＦに基づいて、データＸ１が下位ビットであり、データＸ２が上位ビットである２ビットの被乗数データと、データＹ１が最下位ビットであり、データＹ２が２ビット目であり、データＹ３が最上位ビットである３ビットの乗数データとの部分積を算出し、部分積Ｓ２２としてシフト加算回路４０へ出力する。
【００４４】
セレクタセル３８は、レジスタ１４から受けたデータＸ２、レジスタ１５から受けたデータＸ３、レジスタ１９から受けたシフトフラグＤおよびその反転データ、レジスタ２０から受けた演算フラグＮおよびその反転データ、ならびにレジスタ２１から受けた反転フラグＦに基づいて、データＸ２が下位ビットであり、データＸ３が上位ビットである２ビットの被乗数データと、データＹ１が最下位ビットであり、データＹ２が２ビット目であり、データＹ３が最上位ビットである３ビットの乗数データとの部分積を算出し、部分積Ｓ２３としてシフト加算回路４０へ出力する。
【００４５】
シフト加算回路４０は、セレクタセル３１〜３８からそれぞれ受けた部分積Ｓ１０，Ｓ１１，Ｓ１２，Ｓ１３，Ｓ２０，Ｓ２１，Ｓ２２，Ｓ２３と、ブースデコーダＤＥＣ１およびＤＥＣ２から受けた補数フラグＣ１，Ｃ２とに基づいて、部分積Ｓ１０，Ｓ１１，Ｓ１２，Ｓ１３，Ｓ２０，Ｓ２１，Ｓ２２，Ｓ２３を加算することにより、データＸ０〜Ｘ３とデータＹ０〜Ｙ３との乗算結果を算出する。
【００４６】
データＩ０〜Ｉ３は、シリアル乗算における前段の乗算結果までの累積値を示している。シフト加算回路４０は、算出した乗算結果と、ＳＲＡＭから受けたデータＩ０〜Ｉ３とを加算し、加算結果を示す４ビットのデータＲ０〜Ｒ３をデータＳＯＵＴとしてＳＲＡＭへ出力する。なお、半導体装置２０１は、ＳＲＡＭを備える構成であってもよい。
【００４７】
また、レジスタ１１は、ブースのアルゴリズムに従う乗数のデコード（以下、ブースデコードとも称する。）結果に基づいて被乗数データのシフトが行なわれる場合、シフト結果すなわちレジスタ１５の出力データを補完する。シフト動作が行なわれる場合には、レジスタ１１〜１４の出力データが演算の対象となる。
【００４８】
以下、データＸ０〜Ｘ３の各々をデータＸと称する場合がある。データＹ０〜Ｙ３の各々をデータＹと称する場合がある。部分積Ｓ１０，Ｓ１１，Ｓ１２，Ｓ１３，Ｓ２０，Ｓ２１，Ｓ２２，Ｓ２３の各々を部分積Ｓと称する場合がある。
【００４９】
図２は、本発明の第１の実施の形態に係る半導体装置におけるブースデコーダの構成を示す回路図である。図２において、データＹＬ，ＹＭ，ＹＨは、ブースデコーダＤＥＣ１においてはそれぞれデータＦ２，Ｙ０，Ｙ１を示し、ブースデコーダＤＥＣ２においてはそれぞれデータＹ１，Ｙ２，Ｙ３を示す。また、データ／ＹＬ，／ＹＭ，／ＹＨは、ＹＬ，ＹＭ，ＹＨの論理レベルを反転したデータを示す。また、Ｄ，Ｎ，Ｆ，Ｃは、それぞれシフトフラグ、演算フラグ、反転フラグおよび補数フラグを示す。
【００５０】
図２を参照して、ブースデコーダＤＥＣは、ＮチャネルＭＯＳトランジスタＭ１〜Ｍ６と、ＰチャネルＭＯＳトランジスタＭｐ１〜Ｍｐ５と、ＮＡＮＤゲートＧ１，Ｇ２と、ＮＯＴゲートＧ３とを含む。
【００５１】
ＰチャネルＭＯＳトランジスタＭｐ１は、データＹＭを受けるゲートと、データ／ＹＨを受けるソースと、ドレインとを有する。ＮチャネルＭＯＳトランジスタＭ１は、データ／ＹＭを受けるゲートと、データ／ＹＨを受けるドレインと、ソースとを有する。ＰチャネルＭＯＳトランジスタＭｐ２は、データ／ＹＭを受けるゲートと、データＹＨを受けるソースと、ドレインとを有する。ＮチャネルＭＯＳトランジスタＭ２は、データ／ＹＨを受けるゲートと、データＹＨを受けるドレインと、ソースとを有する。
【００５２】
ＰチャネルＭＯＳトランジスタＭｐ３は、データ／ＹＨを受けるゲートと、データ／ＹＬを受けるソースと、ドレインとを有する。ＮチャネルＭＯＳトランジスタＭ３は、データ／ＹＭを受けるゲートと、データ／ＹＬを受けるドレインと、ソースとを有する。ＰチャネルＭＯＳトランジスタＭｐ４は、データ／ＹＭを受けるゲートと、データＹＬを受けるソースと、ドレインとを有する。ＮチャネルＭＯＳトランジスタＭ４は、データ／ＹＨを受けるゲートと、データＹＬを受けるドレインと、ソースとを有する。
【００５３】
ＮＡＮＤゲートＧ１は、ＰチャネルＭＯＳトランジスタＭｐ１およびＭｐ２のドレインと、ＮチャネルＭＯＳトランジスタＭ１およびＭ２のソースとに接続された第１入力端子と、ＰチャネルＭＯＳトランジスタＭｐ３およびＭｐ４のドレインと、ＮチャネルＭＯＳトランジスタＭ３およびＭ４のソースとに接続された第２入力端子とを有する。
【００５４】
ＮＡＮＤゲートＧ２は、ＮＡＮＤゲートＧ１の出力端子に接続された第１入力端子と、ＰチャネルＭＯＳトランジスタＭｐ３およびＭｐ４のドレインと、ＮチャネルＭＯＳトランジスタＭ３およびＭ４のソースとに接続された第２入力端子とを有する。
【００５５】
ＰチャネルＭＯＳトランジスタＭｐ５は、データ／ＹＨを受けるゲートと、ＮＡＮＤゲートＧ１の出力端子に接続されたソースと、ドレインとを有する。ＮチャネルＭＯＳトランジスタＭ５は、データＹＨを受けるゲートと、ＮＡＮＤゲートＧ１の出力端子に接続されたドレインと、ソースとを有する。ＮチャネルＭＯＳトランジスタＭ６は、データ／ＹＨを受けるゲートと、論理ローレベルの信号すなわち”０”を示す信号を受けるドレインと、ソースとを有する。ＰチャネルＭＯＳトランジスタＭｐ５のドレイン、およびＮチャネルＭＯＳトランジスタＭ５，Ｍ６のソースが互いに接続され、この接続ノードの電圧が補数フラグＣとして出力される。
【００５６】
ＮＡＮＤゲートＧ１は、第１入力端子において受けたデータおよび第２入力端子において受けたデータの論理積を反転したデータを演算フラグＮとして出力する。また、データＹＨが反転フラグＦとして出力される。ＮＡＮＤゲートＧ２は、第１入力端子において受けたデータおよび第２入力端子において受けたデータの論理積を反転したデータをＮＯＴゲートＧ３へ出力する。ＮＯＴゲートＧ３は、ＮＡＮＤゲートＧ２から受けたデータの論理レベルを反転し、反転したデータをシフトフラグＤとして出力する。
【００５７】
図３は、ブースデコーダの真理値表を示す図である。
図３を参照して、入力データＹＨ，ＹＭ，ＹＬがすべて”０”である場合には、ブースデコーダＤＥＣは、シフトフラグＤ、演算フラグＮ、反転フラグＦおよび補数フラグＣとしてそれぞれ”０”，”０”，”０”，”０”を出力する。この場合、セレクタセルＳＥＬおよびシフト加算回路４０では、データＸ０〜Ｘ３とデータＹ０〜Ｙ３との乗算において、部分積として０が加算される。
【００５８】
また、入力データＹＨ，ＹＭ，ＹＬがそれぞれ”０”，”０”，”１”である場合には、ブースデコーダＤＥＣは、シフトフラグＤ、演算フラグＮ、反転フラグＦおよび補数フラグＣとしてそれぞれ”０”，”１”，”０”，”０”を出力する。この場合、セレクタセルＳＥＬおよびシフト加算回路４０では、データＸ０〜Ｘ３とデータＹ０〜Ｙ３との乗算において、部分積として対応のデータＸがそのまま加算される。
【００５９】
また、入力データＹＨ，ＹＭ，ＹＬがそれぞれ”０”，”１”，”０”である場合には、ブースデコーダＤＥＣは、シフトフラグＤ、演算フラグＮ、反転フラグＦおよび補数フラグＣとしてそれぞれ”０”，”１”，”０”，”０”を出力する。この場合、セレクタセルＳＥＬおよびシフト加算回路４０では、データＸ０〜Ｘ３とデータＹ０〜Ｙ３との乗算において、部分積として対応のデータＸがそのまま加算される。
【００６０】
また、入力データＹＨ，ＹＭ，ＹＬがそれぞれ”０”，”１”，”１”である場合には、ブースデコーダＤＥＣは、シフトフラグＤ、演算フラグＮ、反転フラグＦおよび補数フラグＣとしてそれぞれ”１”，”１”，”０”，”０”を出力する。この場合、セレクタセルＳＥＬおよびシフト加算回路４０では、データＸ０〜Ｘ３とデータＹ０〜Ｙ３との乗算において、部分積として対応のデータＸが１ビットシフトアップされたデータが加算される。
【００６１】
また、入力データＹＨ，ＹＭ，ＹＬがそれぞれ”１”，”０”，”０”である場合には、ブースデコーダＤＥＣは、シフトフラグＤ、演算フラグＮ、反転フラグＦおよび補数フラグＣとしてそれぞれ”１”，”１”，”１”，”１”を出力する。この場合、セレクタセルＳＥＬおよびシフト加算回路４０では、データＸ０〜Ｘ３とデータＹ０〜Ｙ３との乗算において、部分積として対応のデータＸが１ビットシフトアップされたデータの補数データが加算される。
【００６２】
また、入力データＹＨ，ＹＭ，ＹＬがそれぞれ”１”，”０”，”１”である場合には、ブースデコーダＤＥＣは、シフトフラグＤ、演算フラグＮ、反転フラグＦおよび補数フラグＣとしてそれぞれ”０”，”１”，”１”，”１”を出力する。この場合、セレクタセルＳＥＬおよびシフト加算回路４０では、データＸ０〜Ｘ３とデータＹ０〜Ｙ３との乗算において、部分積として対応のデータＸの補数データが加算される。
【００６３】
また、入力データＹＨ，ＹＭ，ＹＬがそれぞれ”１”，”１”，”０”である場合には、ブースデコーダＤＥＣは、シフトフラグＤ、演算フラグＮ、反転フラグＦおよび補数フラグＣとしてそれぞれ”０”，”１”，”１”，”１”を出力する。この場合、セレクタセルＳＥＬおよびシフト加算回路４０では、データＸ０〜Ｘ３とデータＹ０〜Ｙ３との乗算において、部分積として対応のデータＸの補数データが加算される。
【００６４】
また、入力データＹＨ，ＹＭ，ＹＬがそれぞれ”１”，”１”，”１”である場合には、ブースデコーダＤＥＣは、シフトフラグＤ、演算フラグＮ、反転フラグＦおよび補数フラグＣとしてそれぞれ”０”，”０”，”１”，”０”を出力する。この場合、セレクタセルＳＥＬおよびシフト加算回路４０では、データＸ０〜Ｘ３とデータＹ０〜Ｙ３との乗算において、部分積として０が加算される。
【００６５】
ブースデコーダＤＥＣは、いわゆるブースのアルゴリズムに従い乗数をデコードする回路である。
【００６６】
しかしながら、ブースのアルゴリズムに従う通常のブースデコーダでは、乗数を３桁の符号付２進数へデコードするのに対し、本発明の第１の実施の形態に係る半導体装置におけるブースデコーダＤＥＣは、乗数をシフトフラグＤ、反転フラグＦ、演算フラグＮおよび補数フラグＣへデコードする。
【００６７】
そして、シフトフラグＤ、反転フラグＦ、演算フラグＮを後述するセレクタセルＳＥＬへ入力することで、部分積を生成し、また、補数フラグＣをシフト加算回路４０へ入力して補数処理を実行する。
【００６８】
ブースデコーダＤＥＣは、乗数ビットを２ビット増加する毎に、１つ追加するだけで、汎用的にｍビット×ｎビットの回路構成に対応することができる。
【００６９】
図４は、本発明の第１の実施の形態に係る半導体装置におけるセレクタセルの構成を示す回路図である。図４において、／Ｄ，／Ｎ，／Ｆは、それぞれシフトフラグ、演算フラグおよび反転フラグの論理レベルを反転したデータを示す。また、ＸＬは被乗数の下位ビットを示し、ＸＨは被乗数の上位ビットを示す。
【００７０】
図４を参照して、セレクタセルＳＥＬは、ＮチャネルＭＯＳトランジスタＭ１１〜Ｍ１６と、ＰチャネルＭＯＳトランジスタＭｐ１１〜Ｍｐ１５とを含む。
【００７１】
ＮチャネルＭＯＳトランジスタＭ１１は、シフトフラグ／Ｄを受けるゲートと、データＸＬを受けるドレインと、ソースとを有する。ＰチャネルＭＯＳトランジスタＭｐ１１は、シフトフラグＤを受けるゲートと、データＸＬを受けるソースと、ドレインとを有する。ＮチャネルＭＯＳトランジスタＭ１２は、シフトフラグＤを受けるゲートと、データＸＨを受けるドレインと、ソースとを有する。ＰチャネルＭＯＳトランジスタＭｐ１２は、シフトフラグ／Ｄを受けるゲートと、データＸＨを受けるソースと、ドレインとを有する。ＰチャネルＭＯＳトランジスタＭｐ１３は、反転フラグＦを受けるゲートと、ソースと、ドレインとを有する。ＮチャネルＭＯＳトランジスタＭ１３は、反転フラグ／Ｆを受けるゲートと、ドレインと、ソースとを有する。ＮチャネルＭＯＳトランジスタＭ１４は、ゲートと、反転フラグＦを受けるドレインと、ソースとを有する。ＰチャネルＭＯＳトランジスタＭｐ１４は、ＮチャネルＭＯＳトランジスタＭ１１およびＭ１２のソース、ＰチャネルＭＯＳトランジスタＭｐ１１およびＭｐ１２のドレイン、ＰチャネルＭＯＳトランジスタＭｐ１３のソース、ＮチャネルＭＯＳトランジスタＭ１３のドレインならびにＮチャネルＭＯＳトランジスタＭ１４のゲートに接続されたゲートと、反転フラグ／Ｆを受けるドレインと、ソースとを有する。ＮチャネルＭＯＳトランジスタＭ１５は、演算フラグＮを受けるゲートと、ドレインと、ソースとを有する。ＰチャネルＭＯＳトランジスタＭｐ１５は、演算フラグ／Ｎを受けるゲートと、ＰチャネルＭＯＳトランジスタＭｐ１３のドレイン、ＰチャネルＭＯＳトランジスタＭｐ１４のソース、ＮチャネルＭＯＳトランジスタＭ１３，Ｍ１４のソース、およびＮチャネルＭＯＳトランジスタＭ１５のドレインに接続されたソースと、ドレインとを有する。ＮチャネルＭＯＳトランジスタＭ１６は、演算フラグ／Ｎを受けるゲートと、論理ローレベルの信号を受けるドレインと、ソースとを有する。ＰチャネルＭＯＳトランジスタＭｐ１５のドレインと、ＮチャネルＭＯＳトランジスタＭ１５，Ｍ１６のソースとが互いに接続され、この接続ノードの電圧が部分積Ｓとして出力される。
【００７２】
図５は、セレクタセルの真理値表を示す図である。
図５を参照して、演算フラグＮ、反転フラグＦおよびシフトフラグＤがそれぞれ”０”，”０”，”０”である場合には、セレクタセルＳＥＬは、部分積Ｓとして”０”を出力する。
【００７３】
また、演算フラグＮ、反転フラグＦおよびシフトフラグＤがそれぞれ”０”，”０”，”１”である場合、”０”，”１”，”０”である場合、および”０”，”１”，”１”である場合には、セレクタセルＳＥＬは、部分積Ｓとして”０”を出力する。
【００７４】
また、演算フラグＮ、反転フラグＦおよびシフトフラグＤがそれぞれ”１”，”０”，”０”である場合には、セレクタセルＳＥＬは、部分積ＳとしてデータＸＨを出力する。
【００７５】
また、演算フラグＮ、反転フラグＦおよびシフトフラグＤがそれぞれ”１”，”０”，”１”である場合には、セレクタセルＳＥＬは、部分積ＳとしてデータＸＬを出力する。
【００７６】
また、演算フラグＮ、反転フラグＦおよびシフトフラグＤがそれぞれ”１”，”１”，”０”である場合には、セレクタセルＳＥＬは、部分積ＳとしてデータＸＨの論理レベルを反転したデータ／ＸＨを出力する。
【００７７】
また、演算フラグＮ、反転フラグＦおよびシフトフラグＤがそれぞれ”１”，”１”，”１”である場合には、セレクタセルＳＥＬは、部分積ＳとしてデータＸＬの論理レベルを反転したデータ／ＸＬを出力する。
【００７８】
このように、セレクタセルＳＥＬは、ブースのアルゴリズムに従ってデコードされた演算フラグＮ、反転フラグＦおよびシフトフラグＤに基づいて部分積を算出する。
【００７９】
より詳細には、再び図４を参照して、ＰチャネルＭＯＳトランジスタＭｐ１１，Ｍｐ１２およびＮチャネルＭＯＳトランジスタＭ１１，Ｍ１２で構成される選択回路は、シフトフラグＤに基づいて、セレクタセルＳＥＬへ入力された被乗数データをシフトするか否かを選択する。すなわち、この選択回路は、シフトフラグＤが”０”の場合にはデータＸＨをそのまま出力し、シフトフラグＤが”１”の場合にはデータＸＨの１ビット下位のデータＸＬを出力する。
【００８０】
ＰチャネルＭＯＳトランジスタＭｐ１３，Ｍｐ１４およびＮチャネルＭＯＳトランジスタＭ１３，Ｍ１４によって構成される排他的論理和回路は、反転フラグＦが”１”の場合には、上記選択回路によって選択されたデータＸＬまたはデータＸＨを反転させて出力する。また、この排他的論理和回路は、反転フラグＦが”０”の場合には、上記選択回路によって選択されたデータＸＬまたはデータＸＨをそのままＮチャネルＭＯＳトランジスタＭ１５およびＰチャネルＭＯＳトランジスタＭｐ１５へ出力する。
【００８１】
ＰチャネルＭＯＳトランジスタＭｐ１５およびＮチャネルＭＯＳトランジスタＭ１５，Ｍ１６によって構成される回路は、演算フラグＮが”１”の場合には、上記排他的論理和回路から受けたデータを部分積Ｓとして出力し、演算フラグＮが”０”の場合には、”０”を示すデータを部分積Ｓとして出力する。
【００８２】
図４に示すセレクタセルＳＥＬの回路構成を１単位とすることで、乗数ビットおよび被乗数ビットを増加させた乗算回路を簡単に構成することが可能となる。
【００８３】
図６は、本発明の第１の実施の形態に係る半導体装置におけるシフト加算回路の構成を示す回路図である。
【００８４】
図６を参照して、シフト加算回路４０は、たとえば４ビット×４ビット用の回路であり、ハーフアダー（ＨＡ）５１〜５４と、フルアダー（ＦＡ）６１〜６８と、マルチプレクサ（ＭＵＸ）７１〜７３と、レジスタ８１〜８３とを含む。
【００８５】
ハーフアダー５１は、部分積Ｓ１３およびＳ２１を加算し、加算結果の下位ビットをデータＳｕｍとしてフルアダー６１へ出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてハーフアダー５３へ出力する。
【００８６】
ハーフアダー５２は、部分積Ｓ１２およびＳ２０を加算し、加算結果の下位ビットをデータＳｕｍとしてフルアダー６２へ出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてフルアダー６１へ出力する。
【００８７】
ハーフアダー５３は、部分積Ｓ２２およびハーフアダー５１から受けたキャリー出力Ｃｏｕｔを加算し、加算結果の下位ビットをデータＳｕｍとしてフルアダー６４へ出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてフルアダー６３へ出力する。
【００８８】
フルアダー６１は、ハーフアダー５２から受けたキャリー出力Ｃｏｕｔをキャリー入力Ｃｉｎすなわち桁上げ値として受けて、ハーフアダー５１から受けたデータＳｕｍおよびＳＲＡＭから受けたデータＩ３を加算し、加算結果の下位ビットをデータＳｕｍとしてフルアダー６５へ出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてフルアダー６４へ出力する。
【００８９】
フルアダー６２は、レジスタ８１から受けたデータをキャリー入力Ｃｉｎすなわち桁上げ値として受けて、ハーフアダー５２から受けたデータＳｕｍおよびＳＲＡＭから受けたデータＩ２を加算し、加算結果の下位ビットをデータＳｕｍとしてフルアダー６６へ出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてフルアダー６５へ出力する。
【００９０】
ハーフアダー５４は、部分積Ｓ１１およびレジスタ８２から受けたデータを加算し、加算結果の下位ビットをデータＳｕｍとしてフルアダー６７へ出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてフルアダー６６へ出力する。
【００９１】
フルアダー６３は、フルアダー６４から受けたキャリー出力Ｃｏｕｔをキャリー入力Ｃｉｎすなわち桁上げ値として受けて、部分積Ｓ２３およびハーフアダー５３から受けたキャリー出力Ｃｏｕｔを加算し、加算結果の下位ビットをデータＳｕｍとしてマルチプレクサ７２へ出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてマルチプレクサ７１へ出力する。
【００９２】
フルアダー６４は、フルアダー６５から受けたキャリー出力Ｃｏｕｔをキャリー入力Ｃｉｎすなわち桁上げ値として受けて、ハーフアダー５３から受けたデータＳｕｍおよびフルアダー６１から受けたキャリー出力Ｃｏｕｔを加算し、加算結果の下位ビットをデータＳｕｍとしてマルチプレクサ７３へ出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてフルアダー６３へ出力する。
【００９３】
フルアダー６５は、フルアダー６６から受けたキャリー出力Ｃｏｕｔをキャリー入力Ｃｉｎすなわち桁上げ値として受けて、フルアダー６１から受けたデータＳｕｍおよびフルアダー６２から受けたキャリー出力Ｃｏｕｔを加算し、加算結果の下位ビットをデータＲ３として出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてフルアダー６４へ出力する。
【００９４】
フルアダー６６は、フルアダー６７から受けたキャリー出力Ｃｏｕｔをキャリー入力Ｃｉｎすなわち桁上げ値として受けて、フルアダー６２から受けたデータＳｕｍおよびハーフアダー５４から受けたキャリー出力Ｃｏｕｔを加算し、加算結果の下位ビットをデータＲ２として出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてフルアダー６５へ出力する。
【００９５】
フルアダー６７は、フルアダー６８から受けたキャリー出力Ｃｏｕｔをキャリー入力Ｃｉｎすなわち桁上げ値として受けて、ハーフアダー５４から受けたデータＳｕｍおよびＳＲＡＭから受けたデータＩ１を加算し、加算結果の下位ビットをデータＲ１として出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてフルアダー６６へ出力する。
【００９６】
フルアダー６８は、レジスタ８３から受けたデータをキャリー入力Ｃｉｎすなわち桁上げ値として受けて、部分積Ｓ１０およびＳＲＡＭから受けたデータＩ０を加算し、加算結果の下位ビットをデータＲ０として出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてフルアダー６７へ出力する。
【００９７】
マルチプレクサ７１は、制御信号ＢＤＣに基づいて、ブースデコーダＤＥＣ２から受けた補数フラグＣ２およびフルアダー６３から受けたキャリー出力Ｃｏｕｔのいずれかを選択してレジスタ８１へ出力する。マルチプレクサ７２は、制御信号ＢＤＣに基づいて、フルアダー６３から受けたデータＳｕｍおよび”０”を示すデータのいずれかを選択してレジスタ８２へ出力する。マルチプレクサ７３は、制御信号ＢＤＣに基づいて、ブースデコーダＤＥＣ１から受けた補数フラグＣ１およびフルアダー６４から受けたデータＳｕｍのいずれかを選択してレジスタ８３へ出力する。
【００９８】
レジスタ８１は、マルチプレクサ７１から受けたデータを保持するとともにフルアダー６２へ出力する。レジスタ８２は、マルチプレクサ７２から受けたデータを保持するとともにハーフアダー５４へ出力する。レジスタ８３は、マルチプレクサ７３から受けたデータを保持するとともにフルアダー６８へ出力する。
【００９９】
このように、シフト加算回路４０は、セレクタセルＳＥＬから出力される部分積、及び補数フラグＣの値等を加算する。より詳細には、シフト加算回路４０は、セレクタセルＳＥＬから出力される部分積Ｓ１０〜Ｓ１３およびＳ２０〜Ｓ２３と、シリアル乗算における前段の乗算結果までの累積値Ｉ０〜Ｉ３と、このシフト加算回路４０における加算結果の１クロック前の上位ビットまたは補数フラグＣとを加算する。
【０１００】
シフト加算回路４０において加算結果の下位ビットであるデータＲ０〜Ｒ３が出力され、上位ビットは次のクロックタイミングで加算するためにフィードバック用のレジスタ８１〜８３に格納される。
【０１０１】
シフト加算回路４０は、最も効率よく加算器を構成できるＷａｌｌａｃｅの木を用いた回路構成を有している。シフト加算回路４０は、ビットシリアル演算において、被乗数であるデータＸのうち最下位ビットのデータを扱う場合には、上位ビットのフィードバックが存在しないという特徴がある。また、被乗数であるデータＸのうち最下位ビット以外のデータを扱う場合には、補数フラグＣは必要がないという特徴がある。このため、シフト加算回路４０では、マルチプレクサ７１〜７３によって上位ビットのデータおよび補数フラグＣのいずれかを選択する。より詳細には、制御信号ＢＤＣは、被乗数であるデータＸのうち最下位ビットのデータを扱う場合に活性化され、これにより、マルチプレクサ７１〜７３は、それぞれ補数フラグＣ２，”０”を示すデータ，補数フラグＣ１を選択する。このような構成により、回路規模を削減することができる。
【０１０２】
図７は、本発明の第１の実施の形態に係る半導体装置の変形例の構成を示す図である。
図７を参照して、半導体装置２０２は、被乗数が４ビット、乗数が４ビットの４ビット×４ビットシリアル乗算器である半導体装置２０１を、被乗数がｍビット、乗数がｎビットのｍビット×ｎビットシリアル乗算器に拡張した構成を有している。
【０１０３】
半導体装置２０２は、ｎ／２個のブースデコーダＤＥＣと、（ｍ×ｎ／２）個のセレクタセルＳＥＬと、ｍビット×ｎビット用のシフト加算回路とを備える。
【０１０４】
以上のように、本発明の第１の実施の形態に係る半導体装置では、回路面積を小さくして高並列化を図ることが可能であるとともに、符号付乗算を高速に行なうことが可能である。また、シリアル処理を順次行なっていくことによって、可変長の演算が可能であり、また、マルチメディア処理において頻出する加算処理および減算処理が実行可能である。したがって、マルチメディアデータを効果的に処理することができる。
【０１０５】
図８は、本発明の第１の実施の形態に係る半導体装置が行なう乗算処理のフローを示す図である。図８は、８ビット×８ビットの乗算処理フローを示している。
【０１０６】
図８を参照して、Ｘは被乗数であり、Ｙはブースデコードに使用する乗数であり、Ｚは演算結果である。また、ＢａｂはＸａおよびＹｂの部分積であり、ＭａｂはＸａおよびＹｂの部分積の下４桁と前段の部分積の上３桁との和である。
【０１０７】
演算結果Ｚは、以下の式のように各部分積Ｍａｂを足し合わせることにより得られる。
Ｚ０＝Ｍ００
Ｚ１＝Ｍ１０＋Ｍ０１
Ｚ２＝Ｍ２０＋Ｍ１１
Ｚ３＝Ｍ３０＋Ｍ２１
次に、演算処理の流れを説明する。
１）Ｙ０を入力し、ブースのアルゴリズムに従いデコードし、Ｄ／Ｎ／Ｆ／Ｃフラグをセットする。
２）Ｘ０を入力し、Ｘ０×Ｙ０の部分積Ｂ００を算出する。Ｂ００の下位４ｂｉｔをＭ００とする。Ｍ００がそのままＺ０となる。
３）Ｘ１を入力し、Ｘ１×Ｙ０の部分積Ｂ１０を算出する。Ｂ１０の下位４ｂｉｔおよびＢ００の上位３ｂｉｔの和をＭ１０として出力する。
４）Ｘ２を入力し、Ｘ２×Ｙ０の部分積Ｂ２０を算出する。Ｂ２０の下位４ｂｉｔおよびＢ１０の上位３ｂｉｔの和をＭ２０として出力する。
５）Ｘ３を入力し、Ｘ３×Ｙ０の部分積Ｂ３０を算出する。Ｂ３０の下位４ｂｉｔおよびＢ２０の上位３ｂｉｔの和をＭ３０として出力する。
６）Ｙ１を入力し、ブースのアルゴリズムに従いデコードし、Ｄ／Ｎ／Ｆ／Ｃフラグをセットする。
７）Ｘ０を入力し、Ｘ０×Ｙ１の部分積Ｂ０１を算出する。Ｂ０１の下位４ｂｉｔをＭ０１とする。Ｍ０１およびＭ１０の和をとりＺ１とする。
８）Ｘ１を入力し、Ｘ１×Ｙ１の部分積Ｂ１１を算出する。Ｂ１１の下位４ｂｉｔおよびＢ０１の上位３ｂｉｔの和をＭ１１とし、Ｍ２０との和をとりＺ２とする。
９）Ｘ２を入力し、Ｘ２×Ｙ１の部分積Ｂ２１を算出する。Ｂ２１の下位４ｂｉｔおよびＢ１１の上位３ｂｉｔの和をＭ２１とし、Ｍ３０との和をとりＺ３とする。
【０１０８】
ここで、半導体装置２０１は、前述のようにブースデコードおよび部分積加算を行ない、上記Ｚ＊（＊は０〜３）をそれぞれ算出する。たとえば、Ｚ０を求める演算では、レジスタ１２〜１５に４ビットの上記Ｘ０が格納され、４ビットの上記Ｙ０がブースデコードされる。
【０１０９】
シフト加算回路４０は、ブースデコード結果に基づいてシフトおよび反転されたデータを加算して上記部分積Ｂ＊＊（＊＊は００，１０，２０，３０，０１，１１，２１）を算出する。そして、シフト加算回路４０は、各部分積を加算し、加算結果をＺ＊としてＳＲＡＭに保存する。
【０１１０】
図９は、本発明の第１の実施の形態に係る半導体装置が行なう乗算処理以外の演算の基本概念を示す図である。図９は、８ビット×８ビットの演算処理フローを示している。
【０１１１】
ブースのアルゴリズムを用いたビットシリアル乗算器では、乗算以外にも演算が可能である。ビットシリアル乗算器において、２つのブースデコード結果に基づく値、ＳＲＡＭからの入力、および上位ビットのフィードバックを利用することで、加算、減算、補数、反転およびシフト処理を行なうことが可能である。
【０１１２】
図９を参照して、Ｘは演算対象数であり、Ｙはシフトおよび補数処理に利用する数であり、ＹａはＹの下位２ビット＋Ｆ２レジスタの値すなわちレジスタ２１の保持値であり、ＹｂはＹの上位３ビットの値であり、Ｚは演算結果であり、ＺＲＥＧはキャリー用レジスタの値すなわちレジスタ８１〜８３の保持値であり、ＳＲＡＭＩＮはＳＲＡＭからの入力値である。
【０１１３】
ブースデコーダＤＥＣによってＸ×Ｙａ（１段目）およびＸ×Ｙｂ（２段目）を計算し、それらとＺＲＥＧおよびＳＲＡＭＩＮの値とを加算する。この加算結果の下位４ビットをＺとして出力し、上位３ビットをＺＲＥＧとして次のクロックタイミングにおいてフィードバックする。すなわち、Ｘ×Ｙ＋ＳＲＡＭＩＮ＋ＺＲＥＧの演算を行なうことにより、加算、減算、補数、反転およびシフトといった処理を行なうことが可能となる。
【０１１４】
図１０は、本発明の第１の実施の形態に係る半導体装置が行なう加算処理のフローを示す図である。図１０は、８ビット×８ビットの加算処理フローを示している。
【０１１５】
加算処理では、Ｘ＝Ａ、Ｙ＝０００１、Ｆ２＝０、ＳＲＡＭＩＮ＝Ｂを入力することにより、演算を行なう。
【０１１６】
図１０を参照して、Ａは被加数であり、Ａ０はＡの下位４ビットであり、Ａ１はＡの上位４ビットであり、Ｂは加数であり、Ｂ０はＢの下位４ビットであり、Ｂ１はＢの上位４ビットであり、ＹａはＹの下位２ビット＋Ｆ２レジスタの値であり、ＹｂはＹの上位３ビットの値であり、Ｚは演算結果である。
【０１１７】
次に、演算処理の流れを説明する。
１）Ｙａ＝０１０、Ｙｂ＝０００を入力し、ブースのアルゴリズムに従いデコードし、フラグをセットする。
２）Ｘ＝Ａ０、ＳＲＡＭＩＮ＝Ｂ０を入力する。Ａ０×Ｙａの演算結果としてそのままＡ０が出力され、Ａ０×Ｙｂの演算結果として”００００”が出力される。
３）ＺＲＥＧにはキャリー”０”が入力される。Ｚ０としてＡ０＋Ｂ０が出力される。
４）Ｘ＝Ａ１を入力し、ＳＲＡＭＩＮ＝Ｂ１を入力する。Ａ１×Ｙａの演算結果としてそのままＡ１が出力され、Ａ１×Ｙｂの演算結果として”００００”が出力される。また、ＺＲＥＧとして１クロック前のクロックタイミングにおいて生成されたキャリーが出力される。
５）ＺＲＥＧにはキャリーが入力され、Ｚ１としてＡ１＋Ｂ１＋キャリーが出力される。
【０１１８】
以上（１）〜（５）の処理を繰り返し行なうことで、８ビット以上の加算を行なうことが可能である。
【０１１９】
図１１は、本発明の第１の実施の形態に係る半導体装置が行なう減算処理のフローを示す図である。図１１は、８ビット×８ビットの減算処理フローを示している。
【０１２０】
減算処理では、Ｘ＝Ｂ、Ｙ＝１１１１、Ｆ２＝０、ＳＲＡＭＩＮ＝Ａを入力することにより、演算を行なう。
【０１２１】
図１１を参照して、Ａは被減数であり、Ａ０はＡの下位４ビットであり、Ａ１はＡの上位４ビットであり、Ｂは減数であり、Ｂ０はＢの下位４ビットであり、Ｂ１はＢの上位４ビットであり、ＹａはＹの下位２ビット＋Ｆ２レジスタの値であり、ＹｂはＹの上位３ビットの値であり、Ｚは演算結果である。
【０１２２】
次に、演算処理の流れを説明する。
１）Ｙａ＝１１０、Ｙｂ＝１１１を入力し、ブースのアルゴリズムに従いデコードし、フラグをセットする。
２）Ｘ＝Ｂ０、ＳＲＡＭＩＮ＝Ａ０を入力する。Ｂ０×Ｙａの演算結果としてＢ０の補数が出力され、Ｂ０×Ｙｂの演算結果として”００００”が出力される。
３）ＺＲＥＧにはキャリー”００１”が入力され、Ｚ０としてＡ０＋（−Ｂ０）が出力される。
４）Ｘ＝Ｂ１、ＳＲＡＭＩＮ＝Ａ１を入力する。Ｂ１×Ｙａの演算結果としてＢ１の補数が出力され、Ｂ１×Ｙｂの演算結果として”００００”が出力される。また、ＺＲＥＧとして１クロック前のクロックタイミングにおいて生成されたキャリーが出力される。
５）ＺＲＥＧにはキャリーが入力され、Ｚ１としてＡ１＋（−Ｂ１）＋キャリーが出力される。
【０１２３】
以上（１）〜（５）の処理を繰り返し行なうことで、８ビット以上の減算を行なうことが可能である。
【０１２４】
図１２は、本発明の第１の実施の形態に係る半導体装置が行なう補数処理のフローを示す図である。図１２は、８ビット×８ビットの補数処理フローを示している。
【０１２５】
補数処理では、Ｘ＝Ａ、Ｙ＝１１１１、Ｆ２＝０、ＳＲＡＭＩＮ＝０を入力することにより、演算を行なう。
【０１２６】
図１２を参照して、Ａは被減数であり、Ａ０はＡの下位４ビットであり、Ａ１はＡの上位４ビットであり、ＹａはＹの下位２ビット＋Ｆ２レジスタの値であり、ＹｂはＹの上位３ビットの値であり、Ｚは演算結果である。
【０１２７】
次に、演算処理の流れを説明する。
１）Ｙａ＝１１０、Ｙｂ＝１１１を入力し、ブースのアルゴリズムに従いデコードし、フラグをセットする。
２）Ｘ＝Ａ０、ＳＲＡＭＩＮ＝０を入力する。Ａ０×Ｙａの演算結果としてＡ０の補数が出力される。
３）ＺＲＥＧにはキャリー”００１”が入力され、Ｚ０として−Ａ０が出力される。
４）Ｘ＝Ａ１、ＳＲＡＭＩＮ＝０を入力する。Ａ１×Ｙａの演算結果としてＡ１の補数が出力される。また、ＺＲＥＧとして１クロック前のクロックタイミングにおいて生成されたキャリーが出力される。
５）ＺＲＥＧにはキャリーが入力され、Ｚ１として−Ａ１＋キャリーが出力される。
【０１２８】
以上（１）〜（５）の処理を繰り返し行なうことで、８ビット以上の補数処理を行なうことが可能である。
【０１２９】
図１３は、本発明の第１の実施の形態に係る半導体装置が行なう反転処理のフローを示す図である。図１３は、８ビット×８ビットの反転処理フローを示している。
【０１３０】
反転処理では、Ｘ＝Ａ、Ｙ＝１１１１、Ｆ２＝０、ＳＲＡＭＩＮ＝０を入力することにより、演算を行なう。
【０１３１】
図１３を参照して、Ａは反転処理前の値であり、Ａ０はＡの下位４ビットであり、Ａ１はＡの上位４ビットであり、ＹａはＹの下位２ビット＋Ｆ２レジスタの値であり、ＹｂはＹの上位３ビットの値であり、Ｚは反転処理結果である。
【０１３２】
次に、演算処理の流れを説明する。
１）Ｙａ＝１１０、Ｙｂ＝１１１を入力し、ブースのアルゴリズムに従いデコードし、フラグをセットする。
２）Ｘ＝０、ＳＲＡＭＩＮ＝０を入力し、演算結果の上位ビット”０００”をキャリーレジスタに保存する。
３）Ｙａ＝１１０、Ｙｂ＝１１１を入力し、ブースのアルゴリズムに従いデコードし、フラグをセットする。ただし、キャリーフラグは保存せず前のクロックまでのデータを保持する。
４）Ｘ＝Ａ０、ＳＲＡＭＩＮ＝０を入力する。Ａ０×Ｙａの演算結果としてＡ０の反転データが出力される。
５）Ｚ０として−Ａ０が出力される。
６）Ｘ＝Ａ１、ＳＲＡＭＩＮ＝０を入力する。Ａ１×Ｙａの演算結果としてＡ１の反転データが出力される。
７）Ｚ１としてＡ１の反転データが出力される。
【０１３３】
以上（１）〜（７）の処理を繰り返し行なうことで、８ビット以上の反転処理を行なうことが可能である。
【０１３４】
次に、本発明の第１の実施の形態に係る半導体装置が行なう算術シフト処理を説明する。４ビット回路においては、１ビットシフト〜４ビットシフトの組み合わせによって、ｍビットシフトを実現可能である。たとえば７ビットシフトは、３ビットシフトおよび４ビットシフトの組み合わせによって実現可能である。また、４ビットシフトはデータのコピーによって実現可能であるため、以下では、１ビットシフト、２ビットシフトおよび３ビットシフトについて述べる。
【０１３５】
図１４は、本発明の第１の実施の形態に係る半導体装置が行なう１ビットシフト処理のフローを示す図である。図１４は、８ビットであるＡの１ビットシフト処理フローを示している。
【０１３６】
１ビットシフト処理では、Ｘ＝Ａ、Ｙ＝０００１、Ｆ２＝１、ＳＲＡＭＩＮ＝０を入力することにより、演算を行なう。
【０１３７】
図１４を参照して、Ａはシフト処理前の値であり、Ａ０はＡの下位４ビットであり、Ａ１はＡの上位４ビットであり、ＹａはＹの下位２ビット＋Ｆ２レジスタの値であり、ＹｂはＹの上位３ビットの値であり、Ｚはシフト処理結果である。
【０１３８】
次に、演算処理の流れを説明する。
１）Ｙａ＝０１１、Ｙｂ＝０００を入力し、ブースのアルゴリズムに従いデコードし、Ｆ２フラグを１にセットする。
２）Ｙａ＝０１１、Ｙｂ＝０００を入力し、ブースのアルゴリズムに従いデコードし、フラグをセットする。
３）Ｘ＝Ａ０、ＳＲＡＭＩＮ＝０を入力する。Ａ０×Ｙａの演算結果としてＡ０を１ビットシフトしたデータが出力される。
４）キャリーレジスタにはＡ０の最上位ビットが保存され、Ｚ０としてＡ０の下位３ビットおよび”０”が出力される。
５）Ｘ＝Ａ１、ＳＲＡＭＩＮ＝０を入力する。Ａ１×Ｙａの演算結果としてＡ１を１ビットシフトしたデータが出力される。
６）Ｚ１としてＡ１の下位３ビットおよびＡ０の最上位ビットが出力される。
【０１３９】
以上（１）〜（６）の処理を繰り返し行なうことで、１ビットシフト処理を逐次的に行なうことが可能である。
【０１４０】
図１５は、本発明の第１の実施の形態に係る半導体装置が行なう２ビットシフト処理のフローを示す図である。図１５は、８ビットであるＡの２ビットシフト処理フローを示している。
【０１４１】
２ビットシフト処理では、Ｘ＝Ａ、Ｙ＝０１００、Ｆ２＝０、ＳＲＡＭＩＮ＝０を入力することにより、演算を行なう。
【０１４２】
図１５を参照して、Ａはシフト処理前の値であり、Ａ０はＡの下位４ビットであり、Ａ１はＡの上位４ビットであり、ＹａはＹの下位２ビット＋Ｆ２レジスタの値であり、ＹｂはＹの上位３ビットの値であり、Ｚはシフト処理結果である。
【０１４３】
次に、演算処理の流れを説明する。
１）Ｙａ＝０００、Ｙｂ＝０１０を入力し、ブースのアルゴリズムに従いデコードし、Ｆ２フラグを０にセットする。
２）Ｙａ＝０００、Ｙｂ＝０１０を入力し、ブースのアルゴリズムに従いデコードし、フラグをセットする。
３）Ｘ＝Ａ０、ＳＲＡＭＩＮ＝０を入力する。Ａ０×Ｙａの演算結果としてＡ０を２ビットシフトしたデータが出力される。
４）キャリーレジスタにはＡ０の上位２ビットが保存され、Ｚ０としてＡ０の下位２ビットおよび”０”が出力される。
５）Ｘ＝Ａ１、ＳＲＡＭＩＮ＝０を入力する。Ａ１×Ｙａの演算結果としてＡ１を２ビットシフトしたデータが出力される。
６）Ｚ１としてＡ１の下位２ビットおよびＡ０の上位２ビットが出力される。
【０１４４】
以上（１）〜（６）の処理を繰り返し行なうことで、２ビットシフト処理を逐次的に行なうことが可能である。
【０１４５】
図１６は、本発明の第１の実施の形態に係る半導体装置が行なう３ビットシフト処理のフローを示す図である。図１６は、８ビットであるＡの３ビットシフト処理フローを示している。
【０１４６】
３ビットシフト処理では、Ｘ＝Ａ、Ｙ＝０１１１、Ｆ２＝１、ＳＲＡＭＩＮ＝０を入力することにより、演算を行なう。
【０１４７】
図１６を参照して、Ａはシフト処理前の値であり、Ａ０はＡの下位４ビットであり、Ａ１はＡの上位４ビットであり、ＹａはＹの下位２ビット＋Ｆ２レジスタの値であり、ＹｂはＹの上位３ビットの値であり、Ｚはシフト処理結果である。
【０１４８】
次に、演算処理の流れを説明する。
１）Ｙａ＝１１１、Ｙｂ＝０１１を入力し、ブースのアルゴリズムに従いデコードし、Ｆ２フラグを１にセットする。
２）Ｙａ＝１１１、Ｙｂ＝０１１を入力し、ブースのアルゴリズムに従いデコードし、フラグをセットする。
３）Ｘ＝Ａ０、ＳＲＡＭＩＮ＝０を入力する。Ａ０×Ｙａの演算結果として”００００”、Ａ０×Ｙｂの演算結果としてＡ０を３ビットシフトしたデータが出力される。
４）キャリーレジスタにはＡ０の上位３ビットが保存され、Ｚ０としてＡ０の下位１ビットおよび”０００”が出力される。
５）Ｘ＝Ａ１、ＳＲＡＭＩＮ＝０を入力する。Ａ１×Ｙａの演算結果として”００００”が出力され、Ａ１×Ｙｂの演算結果としてＡ１を３ビットシフトしたデータが出力される。
６）Ｚ１としてＡ１の下位１ビットおよびＡ０の上位３ビットが出力される。
【０１４９】
以上（１）〜（６）の処理を繰り返し行なうことで、３ビットシフト処理を逐次的に行なうことが可能である。
【０１５０】
以上のように、本発明の第１の実施の形態に係る半導体装置は、乗算以外にも加算、減算、補数、反転およびシフト処理を行なうことが可能であり、かつこれらの演算を高速に行なうことが可能である。
【０１５１】
次に、本発明の他の実施の形態について図面を用いて説明する。なお、図中同一または相当部分には同一符号を付してその説明は繰り返さない。
【０１５２】
＜第２の実施の形態＞
本実施の形態は、第１の実施の形態に係る半導体装置と比べて演算方法を変更した半導体装置に関する。以下で説明する内容以外は第１の実施の形態に係る半導体装置と同様である。
【０１５３】
図１７は、本発明の第２の実施の形態に係る半導体装置の構成を示す図である。
図１７を参照して、半導体装置２０３は、加減算部９６と、テーブル部９３，９４と、出力演算部９５とを備える。加減算部９６は、加算部９１と、減算部９２とを含む。
【０１５４】
半導体装置２０３は、データＸおよびデータＹの積を算出する。半導体装置２０３では、ビットシリアル乗算器を構成する方法として、乗算の式変形と、テーブルルックアップとを用いる。
【０１５５】
まず、半導体装置２０３のテーブル参照を用いた乗算アルゴリズムについて説明する。
ｎビット×ｎビットの乗算を行なう際に、乗算結果をすべて事前に計算し、テーブルに格納しておけば、乗算は１回のテーブル参照によって行なうことができる。
【０１５６】
しかしながら、このような方法では、テーブルの大きさが２2n×２×ｎビットと大きくなってしまう。
【０１５７】
そこで、半導体装置２０３では、以下の式（１）あるいは式（２）が成り立つことを利用する。
【０１５８】
Ｘ×Ｙ＝（（Ｘ＋Ｙ）2−Ｘ2−Ｙ2）／２  ・・・（１）
Ｘ×Ｙ＝（（Ｘ＋Ｙ）2−（Ｘ−Ｙ）2）／４  ・・・（２）
（ｎ＋１）ビットのデータの平方を事前に計算しておき、計算結果をテーブルに格納しておくことにより、ＸおよびＹの乗算を、式（１）では２回のテーブル参照と３回の加減算とにより実現することができる。また、式（２）では３回のテーブル参照と３回の加減算とにより実現することができる。また、テーブルの大きさを２n+1×（２×ｎ＋２）ビット程度と小さくすることができる。
【０１５９】
さらに、半導体装置２０３では、Ｘ≧Ｙの条件下で、以下の式（３）および（４）に従ってＸおよびＹの乗算を行なう。
【０１６０】
Ｘ＋Ｙが偶数のとき、Ｘ×Ｙ＝（（Ｘ＋Ｙ）／２）2−（（Ｘ−Ｙ）／２）2  ・・・（３）
Ｘ＋Ｙが奇数のとき、Ｘ×Ｙ＝（（Ｘ＋Ｙ−１）／２）2−（（Ｘ−Ｙ−１）／２）2＋Ｙ  ・・・（４）
Ｘ＋Ｙが偶数のときは、Ｘ−Ｙも必ず偶数になる。また、（Ｘ＋Ｙ）および（Ｘ−Ｙ）は、２進数で表記した場合には、必ず最下位ビットが”０”となる。すなわち、（（Ｘ＋Ｙ）／２）の演算、および（（Ｘ−Ｙ）／２）の演算では、余りが発生せず、演算結果は必ずｎビット以下になる。したがって、式（３）を実行する際に、ｎ2すなわちｎビット×ｎビットの演算を行なうためのテーブルを設ければよく、テーブルの大きさを、２n+1×（２×ｎ＋２）ビットからさらに２n×２×ｎビットと小さくすることができる。
【０１６１】
Ｘ＋Ｙが奇数のときは、Ｘ−Ｙも必ず奇数になる。また、（Ｘ＋Ｙ）および（Ｘ−Ｙ）は、２進数で表記した場合には、必ず最下位ビットが”１”となる。すなわち、Ｘ＋Ｙが奇数のとき、（Ｘ＋Ｙ）および（Ｘ−Ｙ）にそれぞれ１を減ずれば必ず最下位ビットが”０”となる。そうすると、（（Ｘ＋Ｙ−１）／２）の演算、および（（Ｘ−Ｙ−１）／２）の演算では、余りが発生せず、演算結果は必ずｎビット以下になる。したがって、式（４）を実行する際に、ｎ2すなわちｎビット×ｎビットの演算を行なうためのテーブルを設ければよく、テーブルの大きさを、２n+1×（２×ｎ＋２）ビットからさらに２n×２×ｎビットと小さくすることができる。
【０１６２】
次に、上記アルゴリズムを実現する半導体装置２０３における各機能ブロックの動作を説明する。まず、Ｘ＋Ｙが偶数の場合における半導体装置２０３の動作について説明する。
【０１６３】
加算部９１は、データＸおよびデータＹを加算し、加算した和データをテーブル部９３へ出力する。
【０１６４】
減算部９２は、データＸおよびデータＹを減算し、減算した差データをテーブル部９４へ出力する。
【０１６５】
テーブル部９３は、加算部９１から受けた和データを、この和データを２で除算し、除算結果を２乗したデータに変換して出力する。
【０１６６】
テーブル部９４は、減算部９２から受けた差データを、この差データを２で除算し、除算結果を２乗したデータに変換して出力する。
【０１６７】
出力演算部９５における減算部は、テーブル部９３から受けたデータとテーブル部９４から受けたデータとを減算し、減算結果をデータＸおよびデータＹの乗算結果として出力する。
【０１６８】
そして、出力演算部９５は、減算部において算出した乗算結果と、ＳＲＡＭから受けたシリアル乗算における前段の乗算結果までの累積値とを加算し、加算結果を示すデータをＳＲＡＭに保存する。なお、半導体装置２０３は、ＳＲＡＭを備える構成であってもよい。
【０１６９】
次に、Ｘ＋Ｙが奇数の場合における半導体装置２０３の動作について説明する。
加算部９１は、データＸおよびデータＹを加算し、加算結果から１を減算した和データをテーブル部９３へ出力する。
【０１７０】
減算部９２は、データＸおよびデータＹを減算し、減算結果から１を減算した差データをテーブル部９４へ出力する。
【０１７１】
テーブル部９３は、加算部９１から受けた和データを、この和データを２で除算し、除算結果を２乗したデータに変換して出力する。
【０１７２】
テーブル部９４は、減算部９２から受けた差データを、この差データを２で除算し、除算結果を２乗したデータに変換して出力する。
【０１７３】
出力演算部９５における減算部は、テーブル部９３から受けたデータとテーブル部９４から受けたデータとを減算し、減算結果をデータＸおよびデータＹの乗算結果として出力する。
【０１７４】
そして、出力演算部９５は、減算部において算出した乗算結果と、ＳＲＡＭから受けたシリアル乗算における前段の乗算結果までの累積値とを加算し、加算結果を示すデータをＳＲＡＭに保存する。
【０１７５】
以下では、データＸおよびデータＹがそれぞれ４ビットのデータであると仮定して説明する。すなわち、データＹ０〜Ｙ３およびデータＸ０〜Ｘ３は、いずれも番号の小さい方が下位ビットを示し、ＬＳＢはデータＹ０およびデータＸ０であり、ＭＳＢはデータＹ３およびデータＸ３である。また、データＸ０〜Ｘ３の各々をデータＸと称する場合がある。データＹ０〜Ｙ３の各々をデータＹと称する場合がある。
【０１７６】
図１８は、本発明の第２の実施の形態に係る半導体装置における加減算部の構成を示す図である。図１８は、Ｘ＋Ｙが偶数の場合における構成を示している。
【０１７７】
図１８を参照して、加算部９１は、レジスタ１０１〜１０４と、フルアダー１１０〜１１２と、ハーフアダー１１３とを含む。減算部９２は、レジスタ１０５〜１０８と、フルアダー１１４〜１１７と、ＮＯＴゲートＧ１５と、ＥＸＯＲゲートＧ１６〜Ｇ１９とを含む。
【０１７８】
レジスタ１０１は、ＳＲＡＭから受けたデータＸ３を保持するとともにフルアダー１１０および１１４へ出力する。レジスタ１０２は、ＳＲＡＭから受けたデータＸ２を保持するとともにフルアダー１１１および１１５へ出力する。レジスタ１０３は、ＳＲＡＭから受けたデータＸ１を保持するとともにフルアダー１１２および１１６へ出力する。レジスタ１０４は、ＳＲＡＭから受けたデータＸ０を保持するとともにハーフアダー１１３およびフルアダー１１７へ出力する。
【０１７９】
レジスタ１０５は、ＳＲＡＭから受けたデータＹ３を保持するとともにフルアダー１１０およびＮＯＴ回路Ｇ１１へ出力する。レジスタ１０６は、ＳＲＡＭから受けたデータＹ２を保持するとともにフルアダー１１１およびＮＯＴ回路Ｇ１２へ出力する。レジスタ１０７は、ＳＲＡＭから受けたデータＹ１を保持するとともにフルアダー１１２およびＮＯＴ回路Ｇ１３へ出力する。レジスタ１０８は、ＳＲＡＭから受けたデータＹ０を保持するとともにハーフアダー１１３およびＮＯＴ回路Ｇ１４へ出力する。ＮＯＴゲートＧ１１〜Ｇ１４は、それぞれレジスタ１０５〜１０８から受けたデータの論理レベルを反転してフルアダー１１４〜１１７へ出力する。
【０１８０】
フルアダー１１０は、フルアダー１１１から受けたキャリー出力Ｃｏｕｔをキャリー入力Ｃｉｎすなわち桁上げ値として受けて、レジスタ１０１から受けたデータＸ３およびレジスタ１０５から受けたデータＹ３を加算し、加算結果の下位ビットをデータＳｕｍとしてテーブル部９３へ出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてテーブル部９３へ出力する。
【０１８１】
フルアダー１１１は、フルアダー１１２から受けたキャリー出力Ｃｏｕｔをキャリー入力Ｃｉｎすなわち桁上げ値として受けて、レジスタ１０２から受けたデータＸ２およびレジスタ１０６から受けたデータＹ２を加算し、加算結果の下位ビットをデータＳｕｍとしてテーブル部９３へ出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてフルアダー１１０へ出力する。
【０１８２】
フルアダー１１２は、ハーフアダー１１３から受けたキャリー出力Ｃｏｕｔをキャリー入力Ｃｉｎすなわち桁上げ値として受けて、レジスタ１０３から受けたデータＸ１およびレジスタ１０７から受けたデータＹ１を加算し、加算結果の下位ビットをデータＳｕｍとしてテーブル部９３へ出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてフルアダー１１１へ出力する。
【０１８３】
ハーフアダー１１３は、レジスタ１０４から受けたデータＸ０およびレジスタ１０８から受けたデータＹ０を加算し、加算結果の下位ビットをデータＳｕｍとしてテーブル部９３へ出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてフルアダー１１２へ出力する。
【０１８４】
フルアダー１１４は、フルアダー１１５から受けたキャリー出力Ｃｏｕｔをキャリー入力Ｃｉｎすなわち桁上げ値として受けて、レジスタ１０１から受けたデータＸ３およびＮＯＴゲートＧ１１から受けたデータＹ３の反転データを加算し、加算結果の下位ビットをデータＳｕｍとしてＥＸＯＲゲートＧ１６へ出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力ＣｏｕｔとしてＮＯＴゲートＧ１５へ出力する。ＮＯＴゲートＧ１５は、フルアダー１１４から受けたキャリー出力Ｃｏｕｔの論理レベルを反転してＥＸＯＲゲートＧ１６〜Ｇ１９へ出力する。
【０１８５】
フルアダー１１５は、フルアダー１１６から受けたキャリー出力Ｃｏｕｔをキャリー入力Ｃｉｎすなわち桁上げ値として受けて、レジスタ１０２から受けたデータＸ２およびＮＯＴゲートＧ１２から受けたデータＹ２の反転データを加算し、加算結果の下位ビットをデータＳｕｍとしてＥＸＯＲゲートＧ１７へ出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてフルアダー１１４へ出力する。
【０１８６】
フルアダー１１６は、フルアダー１１７から受けたキャリー出力Ｃｏｕｔをキャリー入力Ｃｉｎすなわち桁上げ値として受けて、レジスタ１０３から受けたデータＸ１およびＮＯＴゲートＧ１３から受けたデータＹ１の反転データを加算し、加算結果の下位ビットをデータＳｕｍとしてＥＸＯＲゲートＧ１８へ出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてフルアダー１１５へ出力する。
【０１８７】
フルアダー１１７は、”１”を示すデータをキャリー入力Ｃｉｎすなわち桁上げ値として受けて、レジスタ１０４から受けたデータＸ０およびＮＯＴゲートＧ１４から受けたデータＹ０の反転データを加算し、加算結果の下位ビットをデータＳｕｍとしてＥＸＯＲゲートＧ１９へ出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてフルアダー１１６へ出力する。
【０１８８】
ＥＸＯＲゲートＧ１６〜Ｇ１９は、それぞれフルアダー１１４〜１１７から受けたデータＳｕｍおよびＮＯＴゲートＧ１５から受けたデータの排他的論理和をテーブル部９４へ出力する。
【０１８９】
加算部９１は、４つの加算器によって構成されている。また、減算部９２では、ＸにＹの補数を加算する、すなわちＹの反転と、”１”及びＸとを加算することにより、Ｘ−Ｙの演算を行なっている。
【０１９０】
ここで、加算部９１は、Ｘ≧Ｙの場合には正の値を出力し、また、加算部９１においてオーバーフローが発生する。また、加算部９１は、Ｘ＜Ｙの場合には、補数の値を出力する。
【０１９１】
Ｘ−Ｙの演算結果をそのまま２乗する場合には符号は問題にならないが、半導体装置２０３では、テーブル部９４がテーブル参照を行なうため、Ｘ＜Ｙである場合には、出力結果の補数をとる。すなわち、オーバーフローが発生しなければ、Ｘ＜Ｙであると判断できるので、フルアダー１１４のキャリー出力Ｃｏｕｔが”０”の場合には、ＮＯＴ回路Ｇ１５から論理ハイレベルのデータがＥＸＯＲゲートＧ１６〜Ｇ１９へ出力される。これにより、ＥＸＯＲゲートＧ１６〜Ｇ１９は、フルアダー１１４〜１１７から受けたデータＳｕｍを反転して出力する。
【０１９２】
次に、テーブル部の動作について説明する。半導体装置２０３では、ｎビットのデータＸとｎビットのデータＹとを加算した値を２乗したデータに変換し、かつｎビットのデータＸとｎビットのデータＹとを減算した値を２乗したデータに変換するテーブルを利用する。この場合、Ｘ＋Ｙの２乗データは最大ｎ＋１ビットとなり、Ｘ−Ｙの２乗データは最大ｎビットになるが、これらの２乗データは後に１／４倍されるので、テーブル参照が必要なデータは、Ｘ＋Ｙに対してｎビット、Ｘ−Ｙに対してｎ−１ビットとなる。
【０１９３】
テーブル部９３では、（（Ｘ＋Ｙ）／２）2の計算結果が保存されており、テーブル部９４では、（（Ｘ−Ｙ）／２）2の計算結果が保存されている。
【０１９４】
テーブル部は、加算結果用・減算結果用を共通にしたものを用意する方法と、加算および減算を同時に実行したい場合にはテーブルを別々に用意する方法が考えられる。
【０１９５】
図１９は、本発明の第２の実施の形態に係る半導体装置における出力演算部９５の構成を示す図である。図１９は、テーブルを加算結果用、減算結果用と別々に用意する場合における構成を示している。図１９において、テーブル部９３の出力データを示すデータＡ０〜Ａ７、テーブル部９４の出力データを示すデータＢ０〜Ｂ７および累積部分積Ｋ０〜Ｋ３は、いずれも番号の小さい方が下位ビットを示し、ＬＳＢはデータＡ０、データＢ０および累積部分積Ｋ０であり、ＭＳＢはデータＡ７、データＢ７および累積部分積Ｋ３である。また、データＡ０〜Ａ７の各々をデータＡと称する場合がある。データＢ０〜Ｂ７の各々をデータＢと称する場合がある。累積部分積Ｋ０〜Ｋ３の各々を累積部分積Ｋと称する場合がある。ここで、累積部分積Ｋ０〜Ｋ３は、ＳＲＡＭに保存されているシリアル乗算における前段の乗算結果までの累積値である。
【０１９６】
テーブルを加算結果用、減算結果用と別々に用意する場合には、減算結果用のテーブルの大きさは２n-1×（２×ｎ−２）ビットとなる。また、この場合、減算結果用のテーブルの値をあらかじめ（Ｘ−Ｙ）2の補数をとった値にしておくことにより、出力演算部９５における演算を加算のみにすることができる。
【０１９７】
図１９を参照して、出力演算部９５は、ハーフアダー１２１〜１２５と、フルアダー１２６〜１４３と、マルチプレクサ１５１〜１５８と、レジスタ１６１〜１６６とを含む。
【０１９８】
テーブル部９３，９４の変換処理では、（Ｘ＋Ｙ）／２という数字を扱っている。Ｘ＋Ｙが奇数の場合には、（Ｘ＋Ｙ）／２は整数ではなくなることから、データＡおよびデータＢの減算結果にさらにＸまたはＹのいずれかを加算する必要がある。このため、出力演算部９５では、マルチプレクサ１５１〜１５８を用いて、Ｘ＋Ｙの最下位ビットＱ２すなわち図１８に示す加算部９１のハーフアダー１１３から出力されるデータＳｕｍに基づいてＸまたはＹを加算するか否かを決定し、ＸおよびＹの大小関係に基づいてＸおよびＹのいずれを加算するかを決定する。
【０１９９】
より詳細には、データＱ１は、Ｘ＞Ｙの場合には”１”となり、Ｘ≦Ｙの場合には”０”となる。データＱ１は、たとえば図１８に示す減算部９２のフルアダー１１４から出力されるキャリー出力Ｃｏｕｔである。
【０２００】
マルチプレクサ１５１は、データＱ１が”１”の場合にはデータＹ３を選択し、データＱ１が”０”の場合にはデータＸ３を選択してマルチプレクサ１５５へ出力する。マルチプレクサ１５２は、データＱ１が”１”の場合にはデータＹ２を選択し、データＱ１が”０”の場合にはデータＸ２を選択してマルチプレクサ１５６へ出力する。マルチプレクサ１５１は、データＱ１が”１”の場合にはデータＹ１を選択し、データＱ１が”０”の場合にはデータＸ１を選択してマルチプレクサ１５７へ出力する。マルチプレクサ１５１は、データＱ１が”１”の場合にはデータＹ０を選択し、データＱ１が”０”の場合にはデータＸ０を選択してマルチプレクサ１５８へ出力する。
【０２０１】
マルチプレクサ１５５は、（Ｘ＋Ｙ）の演算結果を示すデータの最下位ビットＱ２が”１”の場合にはマルチプレクサ１５１から受けたデータを選択し、最下位ビットＱ２が”０”の場合には”０”を選択してフルアダー１２６へ出力する。
【０２０２】
マルチプレクサ１５６は、（Ｘ＋Ｙ）の演算結果を示すデータの最下位ビットＱ２が”１”の場合にはマルチプレクサ１５２から受けたデータを選択し、最下位ビットＱ２が”０”の場合には”０”を選択してフルアダー１２７へ出力する。
【０２０３】
マルチプレクサ１５７は、（Ｘ＋Ｙ）の演算結果を示すデータの最下位ビットＱ２が”１”の場合にはマルチプレクサ１５３から受けたデータを選択し、最下位ビットＱ２が”０”の場合には”０”を選択してフルアダー１２８へ出力する。
【０２０４】
マルチプレクサ１５８は、（Ｘ＋Ｙ）の演算結果を示すデータの最下位ビットＱ２が”１”の場合にはマルチプレクサ１５４から受けたデータを選択し、最下位ビットＱ２が”０”の場合には”０”を選択してフルアダー１３５へ出力する。
【０２０５】
ハーフアダー１２１は、データＡ７およびデータＢ７を加算し、加算結果の下位ビットをデータＳｕｍとしてフルアダー１２９へ出力する。
【０２０６】
ハーフアダー１２２は、データＡ６およびデータＢ６を加算し、加算結果の下位ビットをデータＳｕｍとしてフルアダー１３０へ出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてフルアダー１２９へ出力する。
【０２０７】
ハーフアダー１２３は、データＡ５およびデータＢ５を加算し、加算結果の下位ビットをデータＳｕｍとしてフルアダー１３１へ出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてフルアダー１３０へ出力する。
【０２０８】
ハーフアダー１２４は、データＡ４およびデータＢ４を加算し、加算結果の下位ビットをデータＳｕｍとしてフルアダー１３２へ出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてフルアダー１３１へ出力する。
【０２０９】
フルアダー１２６は、データＢ３をキャリー入力Ｃｉｎすなわち桁上げ値として受けて、マルチプレクサ１５５から受けたデータおよびデータＡ３を加算し、加算結果の下位ビットをデータＳｕｍとしてフルアダー１３３へ出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてフルアダー１３２へ出力する。
【０２１０】
フルアダー１２７は、データＢ２をキャリー入力Ｃｉｎすなわち桁上げ値として受けて、マルチプレクサ１５６から受けたデータおよびデータＡ２を加算し、加算結果の下位ビットをデータＳｕｍとしてフルアダー１３４へ出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてフルアダー１３３へ出力する。
【０２１１】
フルアダー１２８は、データＢ１をキャリー入力Ｃｉｎすなわち桁上げ値として受けて、マルチプレクサ１５７から受けたデータおよびデータＡ１を加算し、加算結果の下位ビットをデータＳｕｍとしてハーフアダー１２５へ出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてフルアダー１３４へ出力する。
【０２１２】
フルアダー１２９は、フルアダー１３０から受けたキャリー出力Ｃｏｕｔをキャリー入力Ｃｉｎすなわち桁上げ値として受けて、ハーフアダー１２１から受けたデータＳｕｍおよびハーフアダー１２２から受けたキャリー出力Ｃｏｕｔを加算し、加算結果の下位ビットをデータＳｕｍとしてレジスタ１６１へ出力する。
【０２１３】
フルアダー１３０は、フルアダー１３１から受けたキャリー出力Ｃｏｕｔをキャリー入力Ｃｉｎすなわち桁上げ値として受けて、ハーフアダー１２２から受けたデータＳｕｍおよびハーフアダー１２３から受けたキャリー出力Ｃｏｕｔを加算し、加算結果の下位ビットをデータＳｕｍとしてレジスタ１６２へ出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてフルアダー１２９へ出力する。
【０２１４】
フルアダー１３１は、フルアダー１３２から受けたキャリー出力Ｃｏｕｔをキャリー入力Ｃｉｎすなわち桁上げ値として受けて、ハーフアダー１２３から受けたデータＳｕｍおよびハーフアダー１２４から受けたキャリー出力Ｃｏｕｔを加算し、加算結果の下位ビットをデータＳｕｍとしてレジスタ１６３へ出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてフルアダー１３０へ出力する。
【０２１５】
フルアダー１３２は、フルアダー１３３から受けたキャリー出力Ｃｏｕｔをキャリー入力Ｃｉｎすなわち桁上げ値として受けて、ハーフアダー１２４から受けたデータＳｕｍおよびフルアダー１２６から受けたキャリー出力Ｃｏｕｔを加算し、加算結果の下位ビットをデータＳｕｍとしてレジスタ１６４へ出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてフルアダー１３１へ出力する。
【０２１６】
フルアダー１３３は、フルアダー１３４から受けたキャリー出力Ｃｏｕｔをキャリー入力Ｃｉｎすなわち桁上げ値として受けて、フルアダー１２６から受けたデータＳｕｍおよびフルアダー１２７から受けたキャリー出力Ｃｏｕｔを加算し、加算結果の下位ビットをデータＳｕｍとしてフルアダー１３６へ出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてフルアダー１３２へ出力する。
【０２１７】
フルアダー１３４は、ハーフアダー１２５から受けたキャリー出力Ｃｏｕｔをキャリー入力Ｃｉｎすなわち桁上げ値として受けて、フルアダー１２７から受けたデータＳｕｍおよびフルアダー１２８から受けたキャリー出力Ｃｏｕｔを加算し、加算結果の下位ビットをデータＳｕｍとしてフルアダー１３７へ出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてフルアダー１３３へ出力する。
【０２１８】
ハーフアダー１２５は、フルアダー１２８から受けたデータＳｕｍおよびフルアダー１３５から受けたキャリー出力Ｃｏｕｔを加算し、加算結果の下位ビットをデータＳｕｍとしてフルアダー１３８へ出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてフルアダー１３４へ出力する。
【０２１９】
フルアダー１３５は、データＢ０をキャリー入力Ｃｉｎすなわち桁上げ値として受けて、マルチプレクサ１５８から受けたデータおよびデータＡ０を加算し、加算結果の下位ビットをデータＳｕｍとしてフルアダー１３９へ出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてハーフアダー１２５へ出力する。
【０２２０】
レジスタ１６１〜１６４は、それぞれフルアダー１２９〜１３２から受けたデータＳｕｍを保持するとともにフルアダー１３６〜１３９へ出力する。ここで、出力演算部９５の演算ビット幅は４ビットしかないのに対し、データＡおよびデータＢのデータ長はそれぞれ８ビットである。レジスタ１６１〜１６４を設けることにより、上位側のデータを一時保存して演算を２回に分けて実行することができる。
【０２２１】
フルアダー１３６は、ＳＲＡＭから受けた累積部分積Ｋ３をキャリー入力Ｃｉｎすなわち桁上げ値として受けて、フルアダー１３３から受けたデータＳｕｍおよびレジスタ１６１から受けたデータを加算し、加算結果の下位ビットをデータＳｕｍとしてフルアダー１４０へ出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてレジスタ１６５へ出力する。
【０２２２】
フルアダー１３７は、ＳＲＡＭから受けた累積部分積Ｋ２をキャリー入力Ｃｉｎすなわち桁上げ値として受けて、フルアダー１３４から受けたデータＳｕｍおよびレジスタ１６２から受けたデータを加算し、加算結果の下位ビットをデータＳｕｍとしてフルアダー１４１へ出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてフルアダー１４０へ出力する。
【０２２３】
フルアダー１３８は、ＳＲＡＭから受けた累積部分積Ｋ１をキャリー入力Ｃｉｎすなわち桁上げ値として受けて、ハーフアダー１２５から受けたデータＳｕｍおよびレジスタ１６３から受けたデータを加算し、加算結果の下位ビットをデータＳｕｍとしてフルアダー１４２へ出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてフルアダー１４１へ出力する。
【０２２４】
フルアダー１３９は、ＳＲＡＭから受けた累積部分積Ｋ０をキャリー入力Ｃｉｎすなわち桁上げ値として受けて、フルアダー１３５から受けたデータＳｕｍおよびレジスタ１６４から受けたデータを加算し、加算結果の下位ビットをデータＳｕｍとしてフルアダー１４３へ出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてフルアダー１４２へ出力する。
【０２２５】
フルアダー１４０は、フルアダー１４１から受けたデータＳｕｍをキャリー入力Ｃｉｎすなわち桁上げ値として受けて、フルアダー１３６から受けたデータＳｕｍおよびフルアダー１３７から受けたキャリー出力Ｃｏｕｔを加算し、加算結果の下位ビットをデータＲ３として出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてレジスタ１６６へ出力する。
【０２２６】
フルアダー１４１は、フルアダー１４２から受けたキャリー出力Ｃｏｕｔをキャリー入力Ｃｉｎすなわち桁上げ値として受けて、フルアダー１３７から受けたデータＳｕｍおよびフルアダー１３８から受けたキャリー出力Ｃｏｕｔを加算し、加算結果の下位ビットをデータＲ２として出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてフルアダー１４０へ出力する。
【０２２７】
フルアダー１４２は、フルアダー１４３から受けたキャリー出力Ｃｏｕｔをキャリー入力Ｃｉｎすなわち桁上げ値として受けて、フルアダー１３８から受けたデータＳｕｍおよびフルアダー１３９から受けたキャリー出力Ｃｏｕｔを加算し、加算結果の下位ビットをデータＲ１として出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてフルアダー１４１へ出力する。
【０２２８】
レジスタ１６５は、フルアダー１３６から受けたキャリー出力Ｃｏｕｔを保持するとともにデータＬ１としてフルアダー１４３へ出力する。レジスタ１６６は、フルアダー１４０から受けたキャリー出力Ｃｏｕｔを保持するとともにデータＬ０としてフルアダー１４３へ出力する。
【０２２９】
フルアダー１４３は、レジスタ１６６から受けたデータＬ０をキャリー入力Ｃｉｎすなわち桁上げ値として受けて、フルアダー１３９から受けたデータＳｕｍおよびレジスタ１６５から受けたデータＬ１を加算し、加算結果の下位ビットをデータＲ０として出力し、加算結果の上位ビットすなわち桁上げ値をキャリー出力Ｃｏｕｔとしてフルアダー１４２へ出力する。
【０２３０】
以上のように、本発明の第２の実施の形態に係る半導体装置では、本発明の第１の実施の形態に係る半導体装置と同様に、回路面積を小さくして高並列化を図ることが可能であるとともに、符号付乗算を高速に行なうことが可能である。また、シリアル処理を順次行なっていくことによって、可変長の演算が可能であり、また、マルチメディア処理において頻出する加算処理および減算処理が実行可能である。したがって、マルチメディアデータを効果的に処理することができる。
【０２３１】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【符号の説明】
【０２３２】
１１〜２１  レジスタ、３１〜３８，ＳＥＬ  セレクタセル（部分積算出回路）、４０  シフト加算回路（部分積加算回路）、５１〜５４，１１３，１２１〜１２５  ハーフアダー、６１〜６８，１１０〜１１２，１１４〜１１７，１２６〜１４３  フルアダー、７１〜７３，１５１〜１５８  マルチプレクサ、８１〜８３，１０１〜１０８，１６１〜１６６  レジスタ、９１  加算部、９２  減算部、９３，９４  テーブル部、９５  出力演算部、９６  加減算部、２０１〜２０３  半導体装置、ＤＥＣ１，ＤＥＣ２  ブースデコーダ、Ｍ１〜Ｍ６，Ｍ１１〜Ｍ１６  ＮチャネルＭＯＳトランジスタ、Ｍｐ１〜Ｍｐ５，Ｍｐ１１〜Ｍｐ１５  ＰチャネルＭＯＳトランジスタ、Ｇ１，Ｇ２  ＮＡＮＤゲート、Ｇ３  ＮＯＴゲート、Ｇ１５  ＮＯＴゲート、Ｇ１６〜Ｇ１９  ＥＸＯＲゲート。
【図１】
2010165179.tif 000003
【図２】
2010165179.tif 000004
【図３】
2010165179.tif 000005
【図４】
2010165179.tif 000006
【図５】
2010165179.tif 000007
【図６】
2010165179.tif 000008
【図７】
2010165179.tif 000009
【図８】
2010165179.tif 000010
【図９】
2010165179.tif 000011
【図１０】
2010165179.tif 000012
【図１１】
2010165179.tif 000013
【図１２】
2010165179.tif 000014
【図１３】
2010165179.tif 000015
【図１４】
2010165179.tif 000016
【図１５】
2010165179.tif 000017
【図１６】
2010165179.tif 000018
【図１７】
2010165179.tif 000019
【図１８】
2010165179.tif 000020
【図１９】
2010165179.tif 000021
【図２０】
2010165179.tif 000022
【図２１】
2010165179.tif 000023