(57)【特許請求の範囲】
【請求項１】
一定のメモリ領域に巡回的にアクセスするためのアドレスをモジュロ加算により生成するアドレス生成回路であって、
２ＮビットのアドレスとＮビットの更新ステップおよびＮビットのモジュロ対象領域サイズに対して、
２ＮビットのアドレスとＮビットの更新ステップを加算して２Ｎビットの加算結果を出力する２入力加算器と、
２Ｎビットのアドレスにおける下位ＮビットとＮビットの更新ステップおよびＮビットのモジュロ対象領域サイズを加減算してＮビットの加減算結果を出力する３入力加減算器と、
前記３入力加減算器によるＮビットの出力結果に対してその最上位ビット側から２Ｎビットのアドレスにおける上位Ｎビットを連接して２Ｎビットの連接結果を出力する連接手段と、
２入力加算器の出力結果あるいは連接手段の出力結果のいずれか一方を選択するための選択信号を、２Ｎビットのアドレスにおける下位ＮビットとＮビットの更新ステップおよびＮビットのモジュロ対象領域サイズに基づいて生成する選択判断回路と、
前記選択判断回路からの前記選択信号により２入力加算器による２Ｎビットの出力結果あるいは連接手段による２Ｎビットの出力結果のいずれか一方を選択するマルチプレクサと、を有し、
前記２入力加算器と、前記３入力加減算器と、前記選択判断回路とをそれぞれ独立に並列動作させることを特徴とするアドレス生成回路。
【請求項２】
前記選択判断回路は、
モジュロ対象領域のサイズを表す所定数のビットのうち、実際にサイズ表現に使用されたビットのなかで最上位のビットを検出し、前記アドレスにおいて、この検出した最上位のビットと同位のビットより上位のビットすべてをゼロクリアした値を生成するマスク回路と、
上から所定数のビットがその符号を表す前記更新ステップの該符号ビットの否定と、前記モジュロ対象領域サイズを表す各ビットとの論理積を算出する否定論理積回路と、
前記マスク回路の出力に前記更新ステップを加算し、前記否定論理積回路の出力を減算する３入力加減算器と、
前記３入力加減算器の出力と前記更新ステップの符号ビットとの排他的論理和を算出する排他的論理和回路と、
を有し、
前記モジュロ対象領域サイズＤＭは、２K-1 ≦ＤＭ＜２K （Ｋは任意の自然数）で、前記モジュロ対象領域の先頭アドレスにおける下位Ｋビットがすべて０であり、
前記更新ステップを表すデータは、前記下位Ｋビットが更新ステップ数を表し、その上位ビットが該更新ステップの符号を表し、
前記選択判断回路は、
前記３入力加減算器により前記アドレスの下位Ｋビットと前記更新ステップの下位Ｋビットの加算結果から、モジュロ対象領域サイズ、あるいは０を減算し、
前記排他的論理和回路により、前記３入力加減算器の減算結果における固定の位置にある符号ビットと前記更新ステップの符号ビットとの排他的論理和を算出することで前記選択信号を生成することを特徴とする請求項１記載のアドレス生成回路。
【請求項３】
一定のモジュロ対象領域に巡回的にアクセスするために、更新前アドレスに更新ステップを加算することで生成した更新アドレスが、前記モジュロ対象領域を逸脱しているか否かを判断する選択判断回路であって、
モジュロ対象領域のサイズを表す所定数のビットのうち、実際にサイズ表現に使用されたビットのなかで最上位のビットを検出し、更新前アドレスにおいて、この検出した最上位のビットと同位のビットより上位のビットすべてをゼロクリアした値を生成するマスク回路と、
上から所定数のビットがその符号を表す前記更新ステップの該符号ビットの否定と、前記モジュロ対象領域サイズを表す各ビットとの論理積を算出する否定論理積回路と、
前記マスク回路の出力に前記更新ステップを加算し、前記否定論理積回路の出力を減算する３入力加減算器と、
前記３入力加減算器の出力と前記更新ステップの符号ビットとの排他的論理和を算出する排他的論理和回路と、
を有し、
前記モジュロ対象領域サイズＤＭは、２K-1 ≦ＤＭ＜２K （Ｋは任意の自然数）で、前記モジュロ対象領域の先頭アドレスにおける下位Ｋビットがすべて０であり、
前記更新ステップを表すデータは、前記下位Ｋビットが更新ステップ数を表し、その上位ビットが該更新ステップの符号を表し、
前記選択判断回路は、
前記３入力加減算器により前記アドレスの下位Ｋビットと前記更新ステップの下位Ｋビットの加算結果から、モジュロ対象領域サイズ、あるいは０を減算し、
前記排他的論理和回路により、前記３入力加減算器の減算結果における固定の位置にある符号ビットと前記更新ステップの符号ビットとの排他的論理和を算出することで前記選択信号を生成することを特徴とする選択判断回路。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はアドレス生成回路、選択判断回路に関し、特にモジュロ加算によるアドレス生成を高速に実行するアドレス生成回路、及びそのアドレス生成回路に適用される選択判断回路に関する。
【０００２】
【従来の技術】
ディジタル信号を高速かつ効率的に処理する機構を備えるディジタル信号処理プロセッサ（ＤＳＰ）は、組み込み用途に用いられることが多い。組み込み用途では、装置全体の大きさに制約があったり、製造コストを低く抑える必要があるため、ＤＳＰのチップサイズ、特に同チップに占める内蔵メモリの大きさが制限される。こうした事を考慮して、ＤＳＰには、内蔵メモリのサイズを制限しても効率を落とさないアーキテクチャが採用されている。例えば、ＤＳＰにおけるメモリアクセス方法の一つであるモジュロアドレシングは、モジュロ加算により生成したアドレスを用いて一定のメモリ領域を巡回的にアクセスすることで、限られたメモリ領域を何度も使い回すことを可能とする。しかし、このようなメモリ利用における効率化の反面、上記アドレス生成におけるモジュロ加算は、通常の加算と異なり、加算結果がその上限値あるいは下限値を逸脱した場合に適切な値に補正する必要があるため、回路としての遅延時間が大きくなる。また、本演算を行なう回路は、乗算器と並んでＤＳＰの全データパスにおける遅延時間が最大のパス（＝クリティカルパス）になる可能性が高い。このため、モジュロ加算を高速に実行できるアドレス生成回路が必要となる。
【０００３】
このようなモジュロ加算を高速に実行するアドレス生成回路として、従来、例えば特開平７−１６８７５３号公報に示されているように、複数の演算器を用いてモジュロ加算における加算や補正処理を行う回路が提案されている。
【０００４】
この従来のアドレス生成回路では、モジュロアドレシングの対象となるメモリ領域（以下、モジュロ対象領域）のサイズＤＭが２K-1 ≦ＤＭ＜２K であり、領域の先頭アドレスＢＡＳＥにおける下位Ｋビットがすべて０であるとする。そして、本回路が生成するアドレスはＢＡＳＥからＢＡＳＥ＋ＤＭ−１までの任意の整数値を取るとする。
【０００５】
このような条件の下で、本回路は、更新前のアドレスＤＰに更新ステップＤＮを加算することで更新後のアドレスＤＰ' を生成する。但し、ＤＮの値が負であるとき加算後の値がＢＡＳＥより小さくなった場合にはＤＭを加算し、ＤＮの値が正であるとき同加算後の値がＢＡＳＥ＋ＤＭより大きいかあるいは等しくなった場合にはＤＭを減算することにより、同加算後の値を補正してＤＰ' とする。
【０００６】
図８は、従来のアドレス生成回路の構成を示すブロック図である。本回路は、アドレスＤＰ２０５に更新ステップＤＮ２０６を加算する２入力加算器２０１と、同加算器２０１の加算結果２０８に対して領域サイズＤＭ２０７を加算あるいは減算する２入力加減算器２０２と、加算器２０１の出力結果２０８とＢＡＳＥあるいはＢＡＳＥ＋ＤＭの減算によりこれらの大小比較を行い、本比較結果に基づいて加算器２０１，加減算器２０２の出力結果２０８，２０９のいずれか一方を選択するための選択信号２１０を生成する選択判断回路２０３と、選択信号２１０に基づいて出力結果２０８，２０９の一方を選択して回路出力ＤＰ' ２１１とするマルチプレクサ２０４とを含んで構成される。なお、選択判断回路２０３は、判断結果が真であるとき選択信号２１０として“０”を出力し、さもなければ“１”を出力する。また、マルチプレクサ２０４は、選択信号２１０が“０”であるとき加算器２０２の結果２０９を出力し、同信号が“１”であるとき加算器２０１の結果２０８を出力する。
【０００７】
次に、本回路の動作について説明する。本回路では、補正が不要な場合と補正が必要な場合の両アドレスを投機的に計算し、補正が必要かどうかの判断に基づいて一方のアドレスを選択して回路出力とする。より具体的には、まず、補正が不要な場合のアドレスを計算するため、２入力加算器２０１において、ＤＰ２０５にＤＮ２０６を加算する。次に、補正が必要な場合のアドレスを計算するため、２入力加減算器２０２において、ＤＮ２０６の値が正の場合、加算結果２０８からＤＭ２０７を減算する。一方、同ＤＮ２０６の値が負の場合には、加算結果２０８にＤＭ２０７を加算する。この加減算器２０２の動作と並行して、選択判断回路２０３において、補正が必要かどうかを次のように判断して選択信号２１０を出力する。ＤＮ２０６の値が正の場合、加算結果２０８がＢＡＳＥ＋ＤＭより大きいかあるいは等しいかどうかを判断し、大きいかあるいは等しいときには選択信号２１０として“０”を出力するが、そうでなければ同信号２１０として“１”を出力する。また、同ＤＮ２０６の値が負の場合、加算結果２０８がＢＡＳＥより小さいかどうかを判断し、小さいときには選択信号２１０として“０”を出力するが、そうでなければ同信号２１０として“１”を出力する。その後、マルチプレクサ２０４において、選択信号２１０が“０”の場合、加減算器２０２の出力結果２０９を回路出力ＤＰ' ２１１として出力する。また、選択信号２１０が“１”の場合には、加算器２０１の出力結果２０８をＤＰ' ２１１として出力する。
【０００８】
【発明が解決しようとする課題】
上記従来技術では、加算器２０１の結果が確定するのを待ってから加減算器２０２および選択判断回路２０３が有効な動作を開始するため、これら演算器の動作が逐次的になっている。これにより、本アドレス生成回路の遅延時間は大きくなり、具体的には「（加算器２０１の遅延時間）＋（加減算器２０２の遅延時間）＋（マルチプレクサ２０４の遅延時間）」、あるいは「（加算器２０１の遅延時間）＋（選択判断回路２０３の遅延時間）＋（マルチプレクサ２０４の遅延時間）」となる。
【０００９】
本発明は上記事情に鑑みてなされたものであり、演算器どうしの入出力依存関係を無くして逐次動作を解消することによりモジュロ加算を高速に実行するアドレス生成回路、及びそれに適用される選択判断回路を提供することを目的とする。
【００１１】
【課題を解決するための手段】
係る目的を達成するために請求項１記載の発明は、一定のメモリ領域に巡回的にアクセスするためのアドレスをモジュロ加算により生成するアドレス生成回路であって、２ＮビットのアドレスとＮビットの更新ステップおよびＮビットのモジュロ対象領域サイズに対して、２ＮビットのアドレスとＮビットの更新ステップを加算して２Ｎビットの加算結果を出力する２入力加算器と、２Ｎビットのアドレスにおける下位ＮビットとＮビットの更新ステップおよびＮビットのモジュロ対象領域サイズを加減算してＮビットの加減算結果を出力する３入力加減算器と、３入力加減算器によるＮビットの出力結果に対してその最上位ビット側から２Ｎビットのアドレスにおける上位Ｎビットを連接して２Ｎビットの連接結果を出力する連接手段と、２入力加算器の出力結果あるいは連接手段の出力結果のいずれか一方を選択するための選択信号を、２Ｎビットのアドレスにおける下位ＮビットとＮビットの更新ステップおよびＮビットのモジュロ対象領域サイズに基づいて生成する選択判断回路と、選択判断回路からの選択信号により２入力加算器による２Ｎビットの出力結果あるいは連接手段による２Ｎビットの出力結果のいずれか一方を選択するマルチプレクサと、を有し、２入力加算器と、３入力加減算器と、選択判断回路とをそれぞれ独立に並列動作させることを特徴とする。
【００１２】
請求項２記載の発明は、請求項１記載の発明において、選択判断回路は、モジュロ対象領域のサイズを表す所定数のビットのうち、実際にサイズ表現に使用されたビットのなかで最上位のビットを検出し、アドレスにおいて、この検出した最上位のビットと同位のビットより上位のビットすべてをゼロクリアした値を生成するマスク回路と、上から所定数のビットがその符号を表す更新ステップの該符号ビットの否定と、モジュロ対象領域サイズを表す各ビットとの論理積を算出する否定論理積回路と、マスク回路の出力に更新ステップを加算し、否定論理積回路の出力を減算する３入力加減算器と、３入力加減算器の出力と更新ステップの符号ビットとの排他的論理和を算出する排他的論理和回路と、を有し、モジュロ対象領域サイズＤＭは、２K-1 ≦ＤＭ＜２K （Ｋは任意の自然数）で、モジュロ対象領域の先頭アドレスにおける下位Ｋビットがすべて０であり、更新ステップを表すデータは、下位Ｋビットが更新ステップ数を表し、その上位ビットが該更新ステップの符号を表し、選択判断回路は、３入力加減算器によりアドレスの下位Ｋビットと更新ステップの下位Ｋビットの加算結果から、モジュロ対象領域サイズ、あるいは０を減算し、排他的論理和回路により、３入力加減算器の減算結果における固定の位置にある符号ビットと更新ステップの符号ビットとの排他的論理和を算出することで選択信号を生成することを特徴とする。
【００１４】
請求項３記載の発明は、一定のモジュロ対象領域に巡回的にアクセスするために、更新前アドレスに更新ステップを加算することで生成した更新アドレスが、モジュロ対象領域を逸脱しているか否かを判断する選択判断回路であって、モジュロ対象領域のサイズを表す所定数のビットのうち、実際にサイズ表現に使用されたビットのなかで最上位のビットを検出し、更新前アドレスにおいて、この検出した最上位のビットと同位のビットより上位のビットすべてをゼロクリアした値を生成するマスク回路と、上から所定数のビットがその符号を表す更新ステップの該符号ビットの否定と、モジュロ対象領域サイズを表す各ビットとの論理積を算出する否定論理積回路と、マスク回路の出力に更新ステップを加算し、否定論理積回路の出力を減算する３入力加減算器と、３入力加減算器の出力と更新ステップの符号ビットとの排他的論理和を算出する排他的論理和回路と、を有し、モジュロ対象領域サイズＤＭは、２K-1 ≦ＤＭ＜２K （Ｋは任意の自然数）で、モジュロ対象領域の先頭アドレスにおける下位Ｋビットがすべて０であり、更新ステップを表すデータは、下位Ｋビットが更新ステップ数を表し、その上位ビットが該更新ステップの符号を表し、選択判断回路は、３入力加減算器によりアドレスの下位Ｋビットと更新ステップの下位Ｋビットの加算結果から、モジュロ対象領域サイズ、あるいは０を減算し、排他的論理和回路により、３入力加減算器の減算結果における固定の位置にある符号ビットと更新ステップの符号ビットとの排他的論理和を算出することで選択信号を生成することを特徴とする。
【００１６】
本発明によるアドレス生成回路は、アドレスと更新ステップを加算する２入力加算器（図１の１０１）と、アドレスと更新ステップおよび領域サイズを加減算する３入力加減算器（図１の１０２）と、これら加減算結果の選択信号を小さい遅延時間で決定できる選択判断回路（図１の１０３）とを有し、これらを独立に並列動作させる。
【００１７】
このように、モジュロ加算に必要な演算器をすべて並列に動作させることで、アドレス生成を高速に実行することができる。
【００１８】
【発明の実施の形態】
［構成の説明］
以下、本発明の実施の一形態について説明する。本実施の形態によるアドレス生成回路では、１６ビットのアドレスでアクセスするメモリにおいて、１６ビットのモジュロ対象領域サイズＤＭを２K-1 ≦ＤＭ＜２K （Ｋは１５以下の整数）とし、領域の先頭アドレスＢＡＳＥの下位Ｋビットがすべて０であるとする。そして、本回路が生成するアドレスはＢＡＳＥからＢＡＳＥ＋ＤＭ−１までの任意の整数値を取るとする。このような条件の下で、本回路は、更新前のアドレスＤＰに１６ビットの更新ステップＤＮを加算することで更新後のアドレスＤＰ' を生成する。但し、ＤＮの値が負であるとき加算後の値がＢＡＳＥより小さくなった場合にはＤＭを加算し、ＤＮの値が正であるとき同加算後の値がＢＡＳＥ＋ＤＭより大きいかあるいは等しくなった場合にはＤＭを減ずることにより、同加算後の値を補正してＤＰ' とする。なお、ＤＮの上から１６−Ｋビットは、その符号を表すものとする。
【００１９】
図１は本実施の形態によるアドレス生成回路の構成を示すブロック図である。本回路は、アドレスＤＰ１０５に更新ステップＤＮ１０６を加算する２入力加算器１０１と、ＤＰ１０５にＤＮ１０６を加算し、さらにＤＭ１０７を加算あるいは減算する３入力加減算器１０２と、加算器１０１，加減算器１０２の出力結果１０８, １０９の何れか一方を選択するための選択信号１１０を生成する選択判断回路１０３と、選択信号１１０に基づいて出力結果１０８，１０９の一方を選択して回路出力ＤＰ’１１１とするマルチプレクサ１０４とを含んで構成される。
【００２０】
２入力加算器１０１には、１６ビットのアドレスＤＰ１０５と１６ビットの更新ステップＤＮ１０６とを入力し、ＤＰ＋ＤＮを１６ビットの加算結果１０８としてマルチプレクサ１０４に出力する。
【００２１】
３入力加減算器１０２には、１６ビットのＤＰ１０５と、１６ビットのＤＮ１０６と、その符号ビット１０６’と、１６ビットのＤＭ１０７とを入力する。そして、ＤＮの符号ビット（＝ＤＮの最上位ビット）が“０”のとき、ＤＰ＋ＤＮ−ＤＭを１６ビットの加減算結果としてマルチプレクサ１０４に出力する。また、同符号ビットが“１”のときには、ＤＰ＋ＤＮ＋ＤＭを１６ビット加算結果１０９としてマルチプレクサ１０４に出力する。
【００２２】
選択判断回路１０３には、１６ビットのＤＰ１０５と、１６ビットのＤＮ１０６と、その符号ビット１０６’と、１６ビットのＤＭ１０７を入力する。そして、ＤＮの符号ビットが“０”のとき、ＤＰの下位ＫビットとＤＮの下位Ｋビットの加算結果がＤＭより大きいか等しい場合に選択信号１１０として“０”を出力し、さもなければ“１”を出力する。一方、同符号ビットが“１”のとき、ＤＰの下位ＫビットとＤＮの下位Ｋビットの加算結果が０より小さい場合に選択信号１１０として“０”を出力し、さもなければ“１”を出力する。但し、「ＤＰの下位ＫビットとＤＮの下位Ｋビットの加算結果」は、図２に示すように、ＤＰ１０５の上位（１６−Ｋ）ビットをゼロクリアした１６ビットの値と、（１６−Ｋ）ビットの符号ビット部およびＫビットの有効数字部からなる１６ビットのＤＮ１０７との１６ビット加算結果を指すものとする。なお、上記において、ＤＰ，ＤＮにおける下位Ｋビットの加算結果とＤＭの比較は、ＢＡＳＥの下位Ｋビットがすべて０であることから、ＤＰ＋ＤＮとＢＡＳＥ＋ＤＭの比較と等価である。また、同様の理由により、ＤＰ，ＤＮにおける下位Ｋビットの加算結果と０の比較は、ＤＰ＋ＤＮとＢＡＳＥの比較と等価である。
【００２３】
このような入出力を持つ本判断回路１０３は、さらに、図３に示すように、ＤＰ１０５の下位Ｋビットを切り出すマスク回路１０３０と、ＤＮ１０６の符号ビットの否定とＤＭにおける各ビットとの論理積を計算する否定論理積回路１０３１と、前記マスク回路１０３０の出力結果とＤＮ１０６とを加算して、この加算結果から前記否定論理積回路１０３１の出力結果を減算する３入力加減算器１０３２と、この３入力加減算器１０３２の１６ビット加減算結果における符号ビットとＤＮ１０６の符号ビットとの排他的論理和を計算するＥＸＯＲゲート１０３３とを含んで構成される。
【００２４】
マルチプレクサ１０４では、２入力加算器１０１の１６ビット出力結果１０８と３入力加減算器１０２の１６ビット出力結果１０９が入力される。そして、同じく入力される選択信号１１０に基づいて、同信号１１０が“０”のとき、３入力加減算器１０２の結果１０９が１６ビットの回路出力ＤＰ' １１１として出力される。また、同信号１１０が“１”のときには、２入力加算器１０１の結果１０８が１６ビットの回路出力ＤＰ' １１１として出力される。
【００２５】
なお、加減算を高速に実行するため、上記２入力加算器１０１にはキャリールックアヘッドアダーを適用し、３入力加減算器１０２, ３入力加減算器１０３２には、キャリーセーブアダーおよび加算器の最終段にキャリールックアヘッドアダーを適用する。
【００２６】
［動作の説明］
本実施形態の動作について図１、３を参照しながら詳細に説明する。本回路では、補正が不要な場合と補正が必要な場合の両アドレスを投機的に計算し、補正が必要かどうかの判断に基づいて一方のアドレスを選択して回路出力とする。
【００２７】
まず、２入力加算器１０１，３入力加減算器１０２，選択判断回路１０３が、それぞれ独立に並列動作する。
【００２８】
２入力加算器１０１では、補正が不要な場合のアドレスを計算するため、ＤＰ１０５とＤＮ１０６を加算して結果１０８を出力する。
【００２９】
３入力加減算器１０２では、補正が必要な場合のアドレスを計算するため、ＤＮ１０６の符号ビットが“０”のとき、ＤＰ１０５とＤＮ１０６を加算してＤＭ１０７を減算する。また、同ＤＮ１０６の符号ビットが“１”のときには、ＤＰ１０５とＤＮ１０６およびＤＭ１０７を加算する。
【００３０】
選択判断回路１０３では、まず、マスク回路１０３０において、ＤＭ１０７における各ビットのうち値が“１”であり、かつ最も上位に位置するビットを検出する。ＤＭ１０７の上から数えて１ビット目から（１６−Ｋ）ビット目がすべて“０”であり、（１６−Ｋ）ビット目の次のビット（すなわち、同ＤＭ１０７の下からＫビット目）が“１”であることから、検出したビットは下からＫビット目に位置する。この検出したビットに基づいて、下位Ｋビットをすべて“１”、それ以外のビットを“０”としたマスクを生成する。そして、本マスクの各ビットとＤＰ１０５における各ビットとの論理積を計算することで、ＤＰ１０５の下位Ｋビットを切り出す。
【００３１】
マスク回路１０３０の動作と並行して、否定論理積回路１０３１において、ＤＮ１０６の符号ビットの否定とＤＭ１０７の各ビットとの論理積を計算する。これにより、ＤＮ１０６の符号ビットが“０”のときには値「ＤＭ」が生成され、同符号ビットが“１”のときには値「０」が生成される。
【００３２】
マスク回路１０３０と否定論理積回路１０３１の出力が確定した後、３入力加減算器１０３２において、マスク回路１０３０の出力とＤＮ１０６を加算して、否定論理積回路１０３１の出力を減算する。これにより、ＤＮ１０６の符号ビットが“０”のときには、ＤＰの下位ＫビットとＤＮの下位Ｋビットの加算結果がＤＭより大きいかあるいは等しいかを判断するための減算が行われる。また、同符号ビットが“１”のときには、ＤＰの下位ＫビットとＤＮの下位Ｋビットの加算結果が０より小さいかを判断するための減算が行われる。
【００３３】
ＤＮ１０６の符号ビットが“０”のときに、３入力加減算器１０３２による加減算結果の符号ビット（上位１６−Ｋビット）が“０”であると、ＤＰ＋ＤＮがモジュロ対象領域を逸脱していると判定できる。また、同符号ビットが“１”のときに加減算結果の符号ビットが“１”であると、ＤＰ＋ＤＮがモジュロ対象領域を逸脱していると判定できる。つまり、ＤＮ１０６の符号ビットと減算結果（＝３入力加減算器１０３２による出力結果）の符号ビットが一致するとき、ＤＰ＋ＤＮがモジュロ対象領域を逸脱していることになる。そこで、ＥＸＯＲゲート１０３３において、３入力加減算器１０３２による出力結果の符号ビットとＤＮの符号ビットとの排他的論理和を計算する。これにより、更新アドレスがモジュロ対象領域を逸脱しているとき両符号ビットが一致するので選択信号１１０として“０”が出力され、さもなければ“１”が出力される。
【００３４】
これら２入力加算器１０１，３入力加減算器１０２，選択判断回路１０３による出力が確定した後、マルチプレクサ１０４は、選択判断回路１０３からの選択信号が“０”の場合、３入力加減算器１０２の出力結果１０９を回路出力ＤＰ’として出力する。また、選択信号１１０が“１”の場合には、２入力加算器１０１の出力結果１０８をＤＰ’１１１として出力する。
【００３５】
このように、２入力加算器１０１、３入力加減算器１０２、選択判断回路１０３を独立に並列動作させたとき、選択判断回路１０３がクリティカルパスとなるため、アドレス生成回路全体の遅延時間は「（選択判断回路１０３の遅延時間）＋（マルチプレクサ１０４の遅延時間）」となる。
【００３６】
ここで、本実施形態と上述した特開平７−１６８７５３号公報（以下、従来例１という）に開示された「モジュロ加算回路」との遅延時間について比較考察する。
まず、本実施形態の選択判断回路１０３は、ＤＰ１０５の下位ＫビットとＤＮ１０６の加算結果をＤＭあるいは０と比較している。このため、図４に示すように、３入力加減算器１０３２の出力結果における符号ビットを用いて選択判断を行なうことができる。すなわち、３入力加減算器１０３２の出力結果における下からＫ＋１番目のビットがキャリーにより反転するのを検出することで選択判断を行なうことになるが、本実施形態においては、上位１６−ＫビットをゼロクリアしたＤＰにＤＮを加算するため、Ｋ＋１番目のビットのキャリーが最上位のビットまで反映される。そこで、このモジュロ対象領域のサイズ（２K-1 ≦ＤＭ＜２K ）が変更されても、この最上位のビットを見ることで選択判断を行なうことができる。一方、上述した従来例１のモジュロ加算回路においても、ＤＰ＋ＤＮの加算結果を、ＢＡＳＥ＋ＤＭ、あるいはＢＡＳＥと比較する場合、図４に示されるように３入力加減算器の出力結果における下からＫ＋１番目のビットがキャリーにより反転するのを検出することで選択判断を行なうことになる。しかしながら、従来例１では、Ｋ＋１番目のビットのキャリーが最上位ビットまで反映されることはないので、この任意の位置にあるＫ＋１番目のビットを検出しなければならない。そのため、図５に示されるように任意の位置にあるビットを抽出するためのマルチプレクサが必要となる。本実施形態は固定された位置にあるビットを用いるのでこのようなマルチプレクサが不要になる。これにより、従来例１は本実施形態よりもマルチプレクサの分だけ遅くなる。
【００３７】
また、図５に示すように、本実施形態ではマスク回路が必要であるのに対し、従来例１では検出すべきキャリービットの位置（すなわち、下からＫ＋１番目）を生成するデコーダ回路が必要となる。このデコーダ回路は、マスク回路と同様に、ＤＭ１０７における各ビットのうち値が“１”であり、かつ最も上位に位置するビットを検出するため、本実施形態は、従来例１のモジュロ加算回路よりも高々ＡＮＤゲート一段分だけ遅くなる。このように両者は互いに他より遅くなる要因を有するが、通常、マルチプレクサはＡＮＤゲート一段よりも遅いことから、本実施形態は従来例１のモジュロ加算回路よりも高速である。
【００３８】
また、選択判断回路１０３内の３入力加減算器や３入力加減算器１０２による加減算は、３データの加減算を２回に分けて実行する従来技術の加減算よりも高速である。なぜなら、図６に示すように、前者ではキャリーセーブアダー１段とキャリールックアヘッドアダー１段で済むが、後者ではキャリールックアヘッドアダー２段が必要となるからである。なお、キャリーセーブアダーは、キャリールックアヘッドアダーよりも高速である。
【００３９】
これらのことから、本アドレス生成回路の遅延時間は、従来技術の遅延時間である「（加算器２０１の遅延時間）＋（加減算器２０２の遅延時間）＋（マルチプレクサ２０４の遅延時間）」、あるいは「（加算器２０１の遅延時間）＋（選択判断回路２０３の遅延時間）＋（マルチプレクサ２０４の遅延時間）」よりも小さい。
【００４０】
［実施例］
ＤＮ１０６の値が正である場合と負である場合の計算例を以下に示す。
まず、ＤＮが正である場合の例として、「ＤＰ＝０ｘ０１２Ｆ，ＤＮ＝０ｘ０００６，ＤＭ＝０ｘ００１０」であるときの本実施の形態によるアドレス生成例を示す。本例では、ＤＭが０ｘ００１０（＝２＾４）であることから、Ｋ＝５であり、モジュロ対象領域は０ｘ０１２０から０ｘ０１２Ｆまでとなる。また、ＤＰ＋ＤＮが０ｘ０１３５であることから、モジュロ対象領域を逸脱する例となっている。このとき、２入力加算器１０１の出力（ＤＰ＋ＤＮ）１０８は、０ｘ０１３５となり、３入力加算器１０２の出力（ＤＰ＋ＤＮ−ＤＭ）１０９は０ｘ０１２５となる。一方、選択判断回路１０３における３入力加減算器１０３２の出力は、
０ｘ０００Ｆ（マスク回路１０３０の出力）＋０ｘ０００６（ＤＮ）−０ｘ００１０（ＤＭ）＝０ｘ０００５
となる。そして、本出力の符号ビット“０”とＤＮ１０６の符号ビット“０”との排他的論理和１０３３である選択信号１１０が“０”となることから、３入力加減算器１０２の出力結果１０９がマルチプレクサ１０４により選択されて回路出力ＤＰ' １１１となる。
【００４１】
次に、ＤＮが負である場合の例として、「ＤＰ＝０ｘ０１２３，ＤＮ＝０ｘＦＦＦＡ，ＤＭ＝０ｘ００１０」であるときのアドレス生成例を示す。本例においてもＫ＝５であり、モジュロ対象領域は０ｘ０１２０から０ｘ０１２Ｆまでとなる。また、ＤＰ＋ＤＮが０ｘ０１１Ｄであることから、モジュロ対象領域を逸脱する例となっている。このとき、２入力加算器１０１の出力（ＤＰ＋ＤＮ）１０８は、０ｘ０１１Ｄとなり、３入力加算器１０２の出力（ＤＰ＋ＤＮ＋ＤＭ）１０９は０ｘ０１２Ｄとなる。一方選択判断回路１０３における３入力加減算器１０３２の出力は、
０ｘ０００３（マスク回路１０３０の出力）＋０ｘＦＦＦＡ（ＤＮ）−０ｘ００００＝０ｘＦＦＦＤ
となる。そして、本出力の符号ビット“１”とＤＮ１０６の符号ビット“１”との排他的論理和１０３３である選択信号１１０が“０”となることから、３入力加減算器１０２の出力結果１０９がマルチプレクサ１０４により選択されて回路出力ＤＰ' １１１となる。
【００４２】
上記実施の形態の説明では、アドレスＤＰ１０５、更新ステップＤＮ１０６、領域サイズＤＭ１０７がすべて１６ビットである場合について説明したが、他のビット長でも本発明の実施の形態が有効であることは明らかである。例えば、ＤＰが３２ビットであり、ＤＮおよびＤＭが１６ビットである場合のように、アドレスの長さが２Ｎビットであり、更新ステップや領域サイズの長さがＮビットである場合の実施の形態について、図７を参照して簡単に説明する。同図において、２入力加算器１０１およびマルチプレクサ１０４のデータ幅が３２ビットであり、ＤＰ１０５の下位１６ビットを３入力加減算器１０２および選択判断回路１０３の入力とし、ＤＰ１０５の上位１６ビットと３入力加減算器１０２の１６ビット出力結果１０９とを連接部１１２により連接した３２ビットの値をマルチプレクサ１０４の入力とする以外は図１の構成と同じである。２入力加算器１０１は３２ビット演算となるが、選択判断回路１０３は１６ビット演算のままでよい。このため、選択判断回路１０３の遅延時間は加算器１０１の遅延時間よりも小さくなる。よって、図７におけるアドレス生成回路の遅延時間は、「（２入力加算器１０１の遅延）＋（マルチプレクサ１０４の遅延）」となり、通常の加算に対するモジュロ加算のオーバーヘッドはマルチプレクサ１０４の遅延時間だけですむ。
【００４３】
なお、上述した実施形態は本発明の好適な実施の形態である。但し、これに限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々変形実施が可能である。
【００４４】
【発明の効果】
以上の説明より明らかなように本発明は、２入力加算器、３入力加減算器、選択判断回路をすべて並列動作させることで、逐次的動作を解消し、モジュロ加算によるアドレス生成を高速に実行することができる。
【００４５】
また、選択判断回路は、下位Ｋビット以外の上位ビットをすべてゼロクリアしたアドレスと更新ステップとを加算し、この加算結果をモジュロ対象領域サイズ、あるいは０と比較している。従って、３入力加減算器による下からＫ＋１番目のビットがキャリーにより反転するのを検出することで選択判断を行なう際に、Ｋ＋１番目のビットのキャリーが最上位のビットまで反映され、モジュロ対象領域のサイズが変更されても、この最上位のビットを用いて選択判断を行なうことができる。従って、従来、任意の位置にあるビットを抽出するために必要であったマルチプレクサが不要となり、アドレスの生成をさらに高速に実現することができる。
【００４６】
また、アドレスの長さが更新ステップや領域サイズの長さよりも大きい場合、選択判断回路の遅延時間が２入力加算器の遅延時間よりも小さくなり、通常の加算とマルチプレクサ１段の遅延時間でモジュロ加算を実行することができる。
【図面の簡単な説明】
【図１】本発明の実施の形態によるアドレス生成回路の構成を示すブロック図である。
【図２】本発明の実施の形態における下位Ｋビットの加算を示す図である。
【図３】本発明の実施の形態による選択判断回路の構成を示すブロック図である。
【図４】実施形態と従来技術における３入力加減算器の違いを示す図である。
【図５】実施形態と従来技術との選択判断回路の違いを示す図である。
【図６】実施形態と従来技術との違いを示す図である。
【図７】本発明の第２の実施の形態によるアドレス生成回路の構成を示すブロック図である。
【図８】従来のアドレス生成回路の構成を示すブロック図である。
【符号の説明】
１０１  ２入力加算器
１０２  ３入力加減算器
１０３  選択判断回路
１０４  マルチプレクサ
【図１】
0004042364.tif 000002
【図２】
0004042364.tif 000003
【図３】
0004042364.tif 000004
【図４】
0004042364.tif 000005
【図５】
0004042364.tif 000006
【図６】
0004042364.tif 000007
【図７】
0004042364.tif 000008
【図８】
0004042364.tif 000009