(57)【要約】  多段パイプラインの対数演算を実行する方法およびＡＬＵについて記載される。一実施形態によれば、主関数が２個以上の副関数に分解される。パイプラインに関連付けられたメモリがパイプラインの各段階用に参照表を格納し、各々の表は、対応する副関数に基づいて生成された関数値を表し、ある段階に関連付けられた参照表は、少なくとも１個の他の段階に関連付けられた参照表（群）と異なる。各段階は、段階入力および対応する参照表に基づいて段階出力を計算する。各段階出力を組み合わせることにより、多段パイプラインは対数演算出力を出力する。
2008502036.tif 000002
【特許請求の範囲】
【請求項１】
多段パイプラインにおける第１および第２のオペランドに基づいて対数計算を実行する方法であって、
主参照表に関連付けられた主参照関数を２個以上の副関数に分解するステップと、
各々の副関数に対して副関数参照表をメモリに格納するステップであって、各々の副関数参照表が前記主参照表の一部を含んでいる、ステップと、
前記多段パイプラインの各段階において少なくとも１個の副関数参照表を使用して段階入力に基づいて段階出力を得るステップと、
各段階出力を組み合わせて対数出力を生成するステップとを含む方法。
【請求項２】
各段階入力が、対応する前記副関数参照表をアドレス指定する、請求項１に記載の方法。
【請求項３】
前記段階入力が、ＭＳ部およびＬＳ部を含んでいて、前記段階入力のＭＳ部が前記副関数参照表をアドレス指定する、請求項１に記載の方法。
【請求項４】
前記第２オペランドから前記第１オペランドを減算して前記多段パイプラインの第１段階用に段階入力を生成するステップを更に含む、請求項３に記載の方法。
【請求項５】
先行段階からの段階入力および段階出力に補正値を累算することにより、後続段階への段階入力を生成するステップを更に含む、請求項４に記載の方法。
【請求項６】
前記メモリに格納された補正表を前記段階入力のＬＳ部によりアドレス指定して前記補正値を生成するステップを更に含む、請求項５に記載の方法。
【請求項７】
前記対数計算の実行が、第１および第２の値の和または差の対数を決定するステップを含んでいて、前記第１オペランドが前記第１値の対数を表わし、前記第２オペランドが前記第２値の対数を表わす、請求項１に記載の方法。
【請求項８】
前記段階出力を組み合わせて対数出力を生成するステップが、前記段階出力を前記第１および第２オペランドのうち一方と組み合わせて対数出力を生成するステップを含む、請求項７に記載の方法。
【請求項９】
前記第１オペランドをＭＳおよびＬＳ部に分割するステップと、
前記第２オペランドをＭＳおよびＬＳ部に分割するステップと、
前記第１および第２オペランドのＬＳ部を減算して前記パイプラインの第１段階用の段階入力のＬＳ部を生成するステップと、
前記第１および第２オペランドのＭＳ部を減算して前記パイプラインの第１段階用の段階入力のＭＳ部を生成するステップとを更に含む、請求項１に記載の方法。
【請求項１０】
前記第１および第２オペランドのＬＳ部を減算するステップが更に桁下げ部を生成し、前記第１および第２オペランドのＭＳ部を減算するステップが前記桁下げ部を考慮している、請求項９に記載の方法。
【請求項１１】
先行段階からの段階出力のＬＳ部にＬＳ補正値を累算することにより、後続段階への段階入力のＬＳ部を生成するステップと、
先行段階からの段階出力のＭＳ部にＭＳ補正値を累算することにより、後続段階への段階入力のＭＳ部を生成するステップとを更に含む、請求項９に記載の方法。
【請求項１２】
先行段階から段階出力のＬＳ部にＬＳ補正値を累算するステップが更に桁上げ部を生成し、後続段階への段階入力のＭＳ部を生成するステップが、前記桁上げ部に先行段階からの段階出力のＭＳ部および前記ＭＳ補正値を累算するステップを含む、請求項１１に記載の方法。
【請求項１３】
変更された補正表を前記段階入力のＬＳ部でアドレス指定して前記ＭＳ補正値およびＬＳ補正値を生成するステップを更に含む、請求項１１に記載の方法。
【請求項１４】
各々の副関数を実行するステップが、対応する副関数参照表または変更された副関数参照表を前記段階入力のＭＳ部でアドレス指定して前記段階出力のＭＳ部および前記段階出力のＬＳ部を生成するステップを含む、請求項１１に記載の方法。
【請求項１５】
前記段階出力を組み合わせて対数出力を生成するステップが、
段階出力のＬＳ部を前記第２オペランドのＬＳ部と組み合わせて前記出力のＬＳ部を生成するステップと、
段階出力のＭＳ部を前記第１オペランドのＭＳ部と組み合わせて前記出力のＭＳ部を生成するステップと、
前記出力のＭＳおよびＬＳ部を結合して対数出力を生成するステップとを含む、請求項１４に記載の方法。
【請求項１６】
前記段階出力を組み合わせるステップが、前記第１オペランドのＭＳ部を前記桁下げ部を考慮している少なくとも１個の段階出力のＭＳ部と組み合わせるステップを含む、請求項１５に記載の方法。
【請求項１７】
前記段階出力のＬＳ部を前記第２オペランドのＬＳ部と組み合わせるステップが更に桁上げ部を生成し、前記段階出力のＭＳ部を前記第１オペランドのＭＳ部と組み合わせるステップが、前記段階出力のＭＳ部を前記桁上げ部と組み合わせるステップを含む、請求項１５に記載の方法。
【請求項１８】
前記段階入力が所定の値を超えた場合に段階を迂回するステップを更に含む、請求項１に記載の方法。
【請求項１９】
段階を迂回するステップが、迂回された段階についてゼロに等しい段階出力を生成し、前記迂回された段階への段階入力を後続段階の段階入力として用いるステップを含む、請求項１８に記載の方法。
【請求項２０】
各段への段階入力をＭＳおよびＬＳ部に分割するステップを更に含む、請求項１に記載の方法。
【請求項２１】
前記段階入力のＭＳおよびＬＳ部が、異なる段階において異なるサイズを有している、請求項２０に記載の方法。
【請求項２２】
少なくとも１個の副関数参照表のサイズが、段階入力値の予想範囲に基づいている、請求項１に記載の方法。
【請求項２３】
前記格納された参照表は、語長が少なくとも２個の連続する段階で減少する、請求項１に記載の方法。
【請求項２４】
１個以上の副関数参照表が異なるサイズを有している、請求項１に記載の方法。
【請求項２５】
各段階からの前記副関数参照表をまとめると前記主参照表に等しい、請求項１に記載の方法。
【請求項２６】
第１および第２のオペランドに基づいて対数計算を実行する対数ＡＬＵであって、
パイプラインの各々の段階が、主関数を分解した各副関数を実行して段階出力を生成する多段パイプラインと、
各々の副関数に対する副関数参照表を格納するメモリであって、各々の副関数参照表が前記主関数に関連する前記主参照表の一部を含んでいる、メモリと、
前記パイプラインの各段階により生成された段階出力に基づいて対数出力を生成する少なくとも１個のコンバイナとを含むＡＬＵ。
【請求項２７】
各段階入力が、対応する副関数参照表をアドレス指定する、請求項２６に記載の対数ＡＬＵ。
【請求項２８】
各段階入力が、ＭＳ部およびＬＳ部を含んでいて、各段階入力のＭＳ部が前記対応副関数参照表をアドレス指定する、請求項２７に記載の対数ＡＬＵ。
【請求項２９】
前記第２オペランドから第１オペランドを減算して前記第１段階への段階入力を生成する減算器を更に含む、請求項２８に記載の対数ＡＬＵ。
【請求項３０】
前記多段パイプラインの少なくとも１個の段階が、先行段階からの段階入力および段階出力を先行段階からの補正値と組み合わせて後続段階への段階入力を生成する段階コンバイナを含む、請求項２９に記載の対数ＡＬＵ。
【請求項３１】
前記メモリが更に補正表を格納し、前記段階入力のＬＳ部が前記補正表をアドレス指定して対応する段階の補正値を生成する、請求項３０記載の対数ＡＬＵ。
【請求項３２】
前記ＡＬＵが、第１および第２の値の和または差の対数を決定することにより対数計算を実行し、前記第１オペランドが前記第１値の対数を表わし、前記第２オペランドが前記第２値の対数を表わす、請求項２６に記載の対数ＡＬＵ。
【請求項３３】
前記出力コンバイナが、前記第２オペランドに前記段階出力を累算して対数出力を生成する２個以上のアキュムレータを含む、請求項３２に記載の対数ＡＬＵ。
【請求項３４】
前記第１および第２オペランドのＬＳ部を減算して前記第１段階への段階入力のＬＳ部を生成し、前記第１および第２オペランドのＭＳ部を減算して前記第１段階への段階入力のＭＳ部を生成する減算器を更に含む、請求項２６に記載の対数ＡＬＵ。
【請求項３５】
前記減算器が更に、前記第１および第２オペランドのＬＳ部の減算に基づいて桁下げ部を生成し、前記減算器が更に、前記第１および第２オペランドのＭＳ部を減算して前記第１段階への段階入力のＭＳ部を生成する際に前記桁下げ部を考慮に入れる、請求項３４に記載の対数ＡＬＵ。
【請求項３６】
前記多段パイプラインの少なくとも１段階が、
先行段階からの段階出力のＬＳ部にＬＳ補正値を累算して後続段階への段階入力のＬＳ部を生成するＬＳ段階コンバイナと、
先行段階からの段階出力のＭＳ部にＭＳ補正値を累算して後続段階への段階入力のＭＳ部を生成するＭＳ段階コンバイナとを含む、請求項３５に記載の対数ＡＬＵ。
【請求項３７】
前記ＬＳ段階コンバイナが更に、先行段階からの段階出力のＬＳ部へのＬＳ補正値の累算に基づいて桁上げ部を生成し、前記ＭＳ段階コンバイナが前記桁上げ部に先行段階からの段階出力のＭＳ部および前記ＭＳ補正値を累算して後続段階入力のＭＳ部を生成する、請求項３６に記載の対数ＡＬＵ。
【請求項３８】
前記メモリが更に、前記パイプラインの少なくとも１段階用に、変更された補正表を格納し、前記段階入力のＬＳ部が前記補正表をアドレス指定して前記補正値を生成する、請求項３７に記載の対数ＡＬＵ。
【請求項３９】
前記メモリに格納された少なくとも１個の副関数参照表が、変更された副関数参照表を含む、請求項３７に記載の対数ＡＬＵ。
【請求項４０】
前記段階入力のＭＳ部が、前記副関数参照表または変更された副関数参照表をアドレス指定して、前記段階出力のＭＳ部および前記段階出力のＬＳ部を生成する、請求項３９に記載の対数ＡＬＵ。
【請求項４１】
少なくとも１個の出力コンバイナが、
前記段階出力のＬＳ部を前記第２オペランドのＬＳ部と組み合わせて前記対数出力のＬＳ部を生成するＬＳコンバイナと、
前記段階出力のＭＳ部を前記第１オペランドのＭＳ部と組み合わせて前記対数出力のＭＳ部を生成するＭＳコンバイナとを含む、請求項４０に記載の対数ＡＬＵ。
【請求項４２】
前記ＭＳコンバイナが、前記桁下げ部を考慮に入れながら、前記第１オペランドのＭＳ部を段階出力のＭＳ部と組み合わせる、請求項４１に記載の対数ＡＬＵ。
【請求項４３】
前記ＬＳコンバイナが更に、前記段階出力のＬＳ部と前記対数出力のＬＳ部の組合せに基づいて桁上げ部を生成し、ＭＳコンバイナが更に、前記段階出力のＭＳ部を前記第１オペランドのＭＳ部および前記桁上げ部と組み合わせて前記対数出力のＭＳ部を生成すべく構成されている、請求項４１に記載の対数ＡＬＵ。
【請求項４４】
各々の副関数参照表の語長が、少なくとも２個の連続する段階で減少する、請求項２６に記載の対数ＡＬＵ。
【請求項４５】
前記段階入力がＭＳ部およびＬＳ部を含んでいて、前記ＭＳおよびＬＳ部が異なる段階において異なるサイズを有し得る、請求項２６に記載の対数ＡＬＵ。
【請求項４６】
少なくとも１個の副関数参照表のサイズが、予想される段階入力値の範囲に基づいている、請求項２６に記載の対数ＡＬＵ。
【請求項４７】
１個以上の副関数参照表が異なるサイズを有している、請求項２６に記載の対数ＡＬＵ。
【請求項４８】
各段階からの前記副関数参照表をまとめると前記主参照表に等しい、請求項２６に記載の対数ＡＬＵ。
【請求項４９】
多段パイプラインにおいて対数計算を実行する方法であって、
前記多段パイプラインの各段階に対する副関数参照表を格納するステップであって、前記副関数参照表が主関数表の一部を含んでいる、ステップと、
対応する副関数参照表および段階入力を用いて、少なくとも１段階に対する段階出力を計算するステップと、
各段階出力を組み合わせて対数出力を生成するステップとを含む方法。
【請求項５０】
各段階への段階入力をＭＳおよびＬＳ部に分割するステップを更に含む、請求項４９に記載の方法。
【請求項５１】
前記段階入力の前記ＭＳおよびＬＳ部が異なる段階において異なるサイズを有し得る、請求項５０に記載の方法。
【請求項５２】
前記段階入力が所定の値を超えた場合、段階を迂回するステップを更に含む、請求項４９に記載の方法。
【請求項５３】
少なくとも１個の副関数参照表のサイズが、予想される前記段階入力値の範囲に基づいている、請求項４９に記載の方法。
【請求項５４】
１個以上の副関数参照表が異なるサイズを有している、請求項４９に記載の方法。
【請求項５５】
対数形式の数に対して演算を実行するＡＬＵであって、対数関数に関連付けられた参照表を格納するメモリを含み、前記参照表が、アドレス範囲により少なくとも２個の同時にアドレス指定可能な副表に分割されていて、前記ＡＬＵが、前記副表のうち少なくとも１個をアドレス指定する入力に基づいて、前記参照表を使用して対数加算および対数減算処理のうち少なくとも一つを行なうＡＬＵ。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願
本出願は２００４年６月４日出願の米国特許仮出願第６０／５７７，３８６号および２００５年１月１２日出願の第６０／６４３，２５９号を優先権主張するものであり、その内容は参照により本明細書に引用される。
【０００２】
発明の背景
本発明は、一般にコンピュータ処理およびデジタル信号処理に関し、より具体的には算術論理ユニット（ＡＬＵ）のパイプライン化された対数演算に関する。
【背景技術】
【０００３】
ＡＬＵは従来より、加算、減算、乗算、除算等、実数および／または複素数に対する各種の計算機能を実行するために用いられてきた。従来のシステムは、固定小数点または浮動小数点で表わされたＡＬＵのいずれかを用いる。精度が制限された実数対数を用いるＡＬＵもまた知られている。例えば、「対数演算を用いるデジタルフィルタリング」（Ｎ．Ｇ．キングズベリー（Ｋｉｎｇｓｂｕｒｙ）およびＰ．Ｊ．Ｗ．レイナー（Ｒａｙｎｅｒ）、電子通信学会論文集（１９７１年１月２８日）Ｖｏｌ．７、Ｎｏ．２、ｐｐ．５６〜５８）を参照されたい。「欧州対数マイクロプロセッサによる演算」（Ｊ．Ｎ．コールマン（Ｃｏｌｅｍａｎ）、Ｅ．Ｉ．チェスター（Ｃｈｅｓｔｅｒ）、Ｃ．Ｉ．ソフトリー（Ｓｏｆｔｌｅｙ）およびＪ．カドレック（Ｋａｄｌｅｃ）（２０００年７月）ＩＥＥＥ  Ｔｒａｎｓ  Ｃｏｍｐｕｔ．、Ｖｏｌ．４９、Ｎｏ．７、ｐｐ．７０２〜７１５）に実数用の高精度（３２ビット）対数演算ユニットの別の例が示されている。
【０００４】
固定小数点プログラミングは、特に乗算または除算演算の後で、小数点の位置を暗算で追い続ける負担をプログラマに課す。例えば、ＦＩＲフィルタが、１０００分１の精度で指定せねばならない重み係数−０．６０７、１．０３５、−０．６０７を用いた信号サンプルの重み付き加算を含むと仮定する。固定小数点演算において、例えば１．０３５を１０３５で表わす必要がある。その結果、信号サンプルに当該数を掛ける乗算は、結果のワード長を１０ビット拡大する。結果を同じメモリワード長に格納するために、１０ビットを捨てる必要がある。しかし、捨てられるのがＭＳＢ（最上位ビット）または、ＬＳＢ（最下位ビット）、あるいは各々の一部である否かは信号データ・スペクトルに依存し、従って現実的なデータを用いたシミュレーションにより判定しなければならない。このことは、正確なプログラミングの検証を煩雑にする。
【０００５】
浮動小数点プロセッサは、各々の格納された数の「仮数」部分に関連付けられた「指数」部分を用いて、自動的に小数点位置を追い続けることにより、小数点位置を暗算で監視する不便を回避すべく導入された。ＩＥＥＥ標準浮動小数点形式は、
ＳＥＥＥＥＥＥＥＥ．ＭＭＭＭＭＭＭＭＭＭＭＭＭＭＭＭＭＭＭＭＭＭＭ
である。ここにＳは、値の符号（０＝＋；１＝−）、ＥＥＥＥＥＥＥＥは８ビットの指数であり、ＭＭＭ．．．ＭＭは２３ビットの仮数である。ＩＥＥＥ標準浮動小数点形式により、仮数の第２４番目の上位ビットは常に１（真のゼロを除く）であり、従って省略される。ＩＥＥＥ形式では、仮数の実際の値は以下となる。
１．ＭＭＭＭＭＭＭＭＭＭＭＭＭＭＭＭＭＭＭＭＭＭＭ
例えば、底が２の対数−１．４０６２５×１０−２＝−１．８×２−７は、ＩＥＥＥ標準形式により以下のように表わすことができる。
１  ０１１１１０００．１１００１１００１１００１１００１１００１１０
更に、ゼロ指数は０１１１１１１１であり、従って数＋１．０は以下のように書くことができる。
０  ０１１１１１１１．０００００００００００００００００００００００
真のゼロを表わすには負に無限の指数を必要とするが、現実的でないため、２−１２７の代わりに真のゼロとして全桁が０のビット・パターンを解釈することにより擬似的なゼロが作られた。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
浮動小数点で表わされた２個の数の乗算には、固定小数点２４×２４ビット乗算器を用いて、サプレス（suppressed）されたＭＳＢの１が置換された仮数を掛け合わせるが、これは、指数部の加算および１２７のオフセットの１個の減算を行ない、複雑度が高い割には遅いロジックである。４８ビットを占める乗算の結果は次いで、２４ビットに切り捨てて、左寄せの後で最上位１ビットを削除しなければならない。乗算はこのように、固定小数点よりも浮動小数点で表わされた数の方がより複雑である。
【０００７】
浮動小数点で表わされた２個の数を加算するには、最初にそれらの指数を減算して、その小数点位置が揃っているか否かを確かめる必要がある。小数点位置が揃っていない場合、仮数を加算する前に、小さい方の数を選んで、暗黙の１を置換しながら、指数の差に等しい２進位置分だけ右へシフトして小数点位置を揃える。シフトを速く実行するために、固定小数点乗算器と構造および複雑度が似ているバレルシフタを用いる場合がある。加算、およびより詳しくは減算の後で、指数を増分させながら先行のゼロを仮数から左へシフトアウトしなければならない。このように、加算および減算もまた、浮動小数点演算における複雑な操作である。
【０００８】
純粋な線型形式では、固定小数点で表わされた数の加算と減算は簡単である一方、乗算、除算、平方、および平方根計算はより複雑である。乗算器は、本質的に多数の論理遅延を有する一連の「シフトおよび条件付加算」回路として構成されている。この遅延を克服すべく、高速プロセッサはパイプライン化を用いる場合があるが、これは通常、プログラミングを複雑にする。従って、高速プロセッサのパイプライン化遅延を最小限に抑えることが関心事である。
【０００９】
浮動小数点で表わされた数表現が対数表現と線型表現が混合したものである点に留意されたい。指数は、当該数の底が２の対数の整数部であり、一方、仮数は線型の小数部である。線型表現では乗算が複雑で、対数表現では加算が複雑であるため、上記は混合浮動小数点表現の場合に両方が複雑である理由を説明するものである。これを克服すべく、上述のような、いくつかの公知のシステムでは純粋の対数表現を用いている。これにより小数点位置の情報を追い続ける課題が解決されて乗算は簡単になり、加算だけが複雑なまま残る。対数加算は、従来技術において参照表を用いて実行された。しかし、表のサイズに対する制約により、この解決策は限られた語長、例えば０〜２４ビットの範囲に限定される。上述のコールマンの参照文献において、３２ビットの精度が、合理的なサイズの参照表により、乗算器を必要とする補間技術を用いて実現された。このように、コールマンの処理には、依然として乗算に付随する複雑さが伴なう。
【００１０】
加算器を必要とすることなく合理的なサイズの参照表を維持しつつ、精度を向上させるための異なる技術が本願出願人による米国特許第５，９４４，７７４号で実数について記述されており、その内容は参照によりここに引用される。しかし、実数および複素数の両方とも無線通信装置等の一般的な用途で求まれるため、両方の処理能力を備えた方法と同様に、特に無線信号処理で有用な複素数演算用の方法および装置が求められている。本出願と並行して出願された米国特許出願第＿＿＿号（代理人整理番号４０１５−５１８１）は、この問題に対処しており、その全文をここに参照におり引用する。更に、多段パイプラインを実装する方法および装置は、複素数および／または実数演算処理を実行しながらスループット速度を向上せせるのに役立つ。
【課題を解決するための手段】
【００１１】
発明の概要
本発明は、対数形式で表現された数を用いて算術演算を実行する算術論理ユニットに関する。対数表現を用いることにより、乗算と除算操作は簡素化されるが、加算と減算はより難しくなる。しかし、以下に簡単に述べる公知のアルゴリズムを用いて２個の数値の和や差の対数計算を簡素化することができる。以下の説明において、ａ＞ｂ且つｃ＝ａ＋ｂと仮定する。次式が示される。
Ｃ＝ｌｏｇｑ（ｃ）＝ｌｏｇｑ（ａ＋ｂ）＝Ａ＋ｌｏｇｑ（１＋ｑ−ｒ）  （１）
ここにｑは対数の底、ｒ＝Ａ−Ｂ、Ａ＝ｌｏｇｑ（ａ）、Ｂ＝ｌｏｇｑ（ｂ）である。式（１）で表わされた演算（以下、対数加算と称す）は、ａとｂの和の対数を加算と減算操作だけを用いて計算できるようにし、ｌｏｇｑ（１＋ｑ−ｒ）の値は参照表を用いて決定される。しかし、プロセッサは参照表を格納するために十分なメモリを必要とする。３２ビットの高精度数値の場合、多くの回路において参照表が実用には大き過ぎるため、直接的に参照する方法（direct look-up method）は一般に１６ビットの数値にしか適用できない。
【００１２】
参照表のサイズを減らすべく、引数ｒ＝Ａ−Ｂを最上位部分（ｒＭ）および最下位部分（ｒＬ）に分割することにより、関数ｌｏｇｑ（１＋ｑ−ｒ）を２個以上の参照関数に分解することができる。対数加算処理の場合、Ｃ＝Ａ＋ｌｏｇｑ（１＋ｑ−ｒ）であると示すことができ、ここにｌｏｇｑ（１＋ｑ−ｒ）は３個の部分値として表わすことができる。
【数１】
2008502036.tif 000003
ここに、ｒＭ＋はｒＭの拡大されたバージョンを表わし、ｒは次式で表わすことができる。
【数２】
2008502036.tif 000004
また、以下の詳述するように
【数３】
2008502036.tif 000005
であり、ここに、ｒＬ−は、元の最下位部分ｒＬより、ｒＭ＋を取得するためにｒＭを拡大した量だけ少ない量に等しい。所望の値Ｃはこのように、Ａと、参照関数により決定される３個の部分値の和として、計算することができる。式（２）に示すように、参照関数は、３個の部分値の全てについて同一であり、引数だけが変化する。参照関数に対する引数はｒ＝Ａ−Ｂに基づいており、反復的に計算することができる。第１の参照関数の引数ｒはＡ−Ｂであり、ｒＭおよびｒＬで表わすことができる。第２の参照関数の引数ｒ’＝｛ｒ’Ｍ；ｒ’Ｌ｝はｒ＋Ｆ（ｒＭ）＋Ｇ（ｒＬ）により決定され、第３の参照関数の引数ｒ”＝｛ｒ”Ｍ；ｒ”Ｌ｝はｒ’＋Ｆ（ｒ’Ｍ）＋Ｇ（ｒ’Ｌ）により決定される。
【００１３】
このように、Ｃは、非反復的な方法に比較べて比較的小さい２個の参照表を用いる反復的アルゴリズムに基づいて計算することができる。しかし、反復的方法で必要とされる複数回の反復はより多くの処理時間を必要とする。しかし、補間技術で用いる加算器を超えることは恐らくないであろう。
【００１４】
パイプライン化は、プロセッサのスループットを上げる技術であり、従って計算時間を短縮するものである。パイプライン化の背景にある概念は、複数段階の各段階で計算の一部を実行することである。１回の計算が第１段階を越えて進行したならば、直ちに新たな計算を開始することができる。各段階に１サイクル要する場合、３段パイプラインにおける全ての計算には３サイクルを要する。しかし、前の計算が終了する前に新規の計算を開始することができるため、各サイクル毎に計算が１回完了する。
【００１５】
パイプライン化を用いて上述のように対数計算を実行することができ、その際に各パイプラインの段階は参照関数の計算での１回の反復を実行する。しかし、パイプラインの各段階で参照表を必要とするため、３段パイプラインでは３個の参照表が存在する。対数加算関数において、参照関数は３段階の全てについて同一である。より高いスループットを得るために、パイプラインの複数段階において参照表全体を複製する必要により、参照表のサイズを減らすことであった反復的方法の利点が薄まる。
【００１６】
しかし、対数加算処理の連続的反復における参照関数に対する引数｛ｒ，ｒ’，ｒ”．．．｝が単調増加することがわかる。すなわち、数列｛ｒ，ｒ’，ｒ”．．．｝は単調増加数列であって、ｒ’はｒより少なくとも特定の量だけ大きいことが保証されている。従って、対数加算処理の第２およびそれ以降の反復は完全な参照表を必要としない。第２の反復において、最小値またはｒ’より小さい引数によりアドレス指定される参照表の値を省略することができる。第３段階において、ｒ”の最小値より小さい引数によりアドレス指定される参照表の値を省略することができる。また、第１段階において、ｒ’の最小値より大きい引数によりアドレス指定される参照表の値を省略することができる。その結果、対数加算の第１、第２、および／または後続段階においてサイズが小さくなった参照表を用いることにより、サイズが小さくなった参照表の利点を享受しながらパイプライン・アーキテクチャを利用することが可能になる。
【００１７】
本発明は、多段パイプラインにおいて対数演算を実行する方法および演算論理ユニット（ＡＬＵ）を含んでいる。本発明の一実施形態によれば、パイプラインの各段階で２個以上の副関数を使用し、各々の副関数は分解された主関数から導かれる（derived from a decomposed master function）。メモリは、各々の副関数用の副関数参照表を格納する。従って、各々の参照表は、主関数参照表の一部または全部を表わすことができる。
【００１８】
パイプラインの各段階は、段階入力に基づいて各副関数を実行して各段階の出力を得る。出力コンバイナ（output combiner）は、段階出力を組み合わせて対数出力を生成する。一実施形態において、各段階の副関数参照表のサイズは、関連する段階に対する値の予想範囲に基づいている。更に、副関数参照表のサイズは、要素数（number of entries）、語長、またはその両方において、段階毎に異なっていてよい。
【００１９】
本発明の一実施形態によれば、補正表は、段階入力に基づいて少なくとも１個の段階に対する補正値を計算する。本実施形態において、後続段階入力は、補正値および先行段階が生成した段階入力および段階出力に基づいて導かれる。
【００２０】
また、特定の段階に対する引数が、当該段階の予想される引数範囲に含まれない場合、本発明のパイプラインは１個以上の段階をスキップして、引数が当該段階の引数範囲内にある段階に直接引数を適用することができる。例えば、第１段階へ入力された引数がｒ’の最小値より大きい場合、本発明のパイプラインは第１段階を迂回して、引数を第２段階に直接適用することができる。
【００２１】
本発明は、多段パイプラインにおいて対数を実行する方法および演算論理ユニット（ＡＬＵ）を含んでいる。本発明の一実施形態によれば、主関数は、パイプラインの各段階が使用する２個以上の副関数に分解される。メモリは、各々の副関数用に副関数参照表を格納する。従って、各々の参照表は、主関数表の一部または全てを表わすことができる。
【００２２】
パイプラインの各段階は、段階入力に基づいて各副関数を実行して、各段階の段階出力を得る。出力コンバイナは、段階出力を組み合わせて最終出力を生成する。一実施形態において、各段階の副関数参照表のサイズは、関連する段階の予想される値の範囲に基づいている。更に、副関数参照表のサイズは、段階毎に異なっていてよい。
【００２３】
本発明の一実施形態によれば、補正表Ｇは、段階入力に基づいて少なくとも１個の段階に対する補正値を計算する。本実施形態において、後続段階の入力は、補正値および先行段階で生成された段階入力および段階出力に基づいて導かれる。
【発明を実施するための最良の形態】
【００２４】
発明の詳細な説明
本発明は、対数計算を実行すべく簡素化された多段パイプラインを有するＡＬＵを提供する。概して、多段パイプラインの各段階は、段階入力によりアドレス指定される関数表Ｆに基づいて部分対数出力を生成する。パイプラインを簡素化すべく、少なくとも１段階の関数表は、要素数または語長または両方のいずれかにおいて、他の段階の関数表とは異なるサイズであってよい。好適な実施形態において、主関数参照表を複数の副関数参照表に分解することができ、各々の副関数参照表はパイプラインの対応する段階で使用される。ここで用いるように、「主関数参照表」とは主参照関数に関連付けられた主参照表を指す。本実施形態では、全ての段階からの全ての副関数参照表を組み合わせたサイズは、主関数参照表のサイズにほぼ等しい。本発明の詳細および利点をよりよく理解されるよう、以下において数値表現、従来方式の補間、反復的対数演算、高精度の反復的対数加算、高精度の反復的対数減算、および指数近似に関する詳細を述べる。
【００２５】
数値の表現
ＡＬＵ内で実施される対数演算は一般に、固有の数形式を必要とする。上記のように、従来のプロセッサは、実数または複素数を、固定小数点バイナリ形式または浮動小数点形式にフォーマットすることができる。上記のように、固定小数点形式は純粋に線形形式である。従って、固定小数点で表わされた数を用いる加算と減算は単純であり、一方、乗算はより複雑である。浮動小数点で表わされた数は、対数と線型表現の混合型である。従って、加算、減算、乗算、および除算は、浮動小数点形式では全て複雑である。これらの形式に付随するいくつかの問題を克服すべく、純粋な対数形式を適切なアルゴリズムと共に用いて、対数形式に付随する加算と減算の問題を解決することができる。以下に、本発明に当てはまる範囲で、純粋対数形式に付随する更なる詳細事項について述べる。
【００２６】
純粋対数形式の実数は、（Ｓ８．２３）と略記され、以下のように表わすことができる。
Ｓ  ｘｘｘｘｘｘｘｘ．ｘｘｘｘｘｘｘｘｘｘｘｘｘｘｘｘｘｘｘｘｘｘｘ
２個のこのような実数を、複素数を表わす一つの方法として用いることができる。しかし、関連する米国特許出願第＿＿＿号（代理人整理番号４０１５−５２８１）に述べられているように、複素数を表わすのに対数極形式の方が有利である。
【００２７】
対数に用いる底は自由に選択できる。しかし、ある底を他のものに優先して選択する利点がある。例えば、底を２として選択することに多くの利点がある。第１に、式（５）に示すように、３２ビットの純粋対数形式は、（Ｓ８．２３）ＩＥＥＥ浮動小数点表現と実質的に同一に見える。
純粋対数：Ｓ  ｘｘ．．．ｘｘ．ｘｘ  ．．．ｘｘ⇔（−１）Ｓ×２−ｘｘ．．．ｘｘ．ｘｘ．．．ｘｘ
ＩＥＥＥ：Ｓ  ＥＥ．．．ＥＥ．ＭＭ．．．ＭＭ⇔（−１）Ｓ×（１＋０．ＭＭ．．．ＭＭ．．．ＭＭ）×２−ＥＥ．．．ＥＥ  （５）
底２に対する対数の整数部は、ＩＥＥＥ形式に従い１２７によりオフセットされて、数１．０はいずれの形式でも次のように表現できる。
０  ０１１１１１１１．０００００００００００００００００００００００
あるいは、１２８のオフセットを用いてもよく、この場合、１．０は次のように表現される。
０  １０００００００．０００００００００００００００００００００００
１２７または１２８のどちらを好適なオフセットとして用いるかは、実装上の問題である。
【００２８】
全ゼロパターンとは、ＩＥＥＥ浮動小数点形式に従い、擬似的な真ゼロとして定義できる。実際、同じ指数オフセット（１２７）を用いた場合、そのような純粋対数形式は、例えば４、２、１、０．５等、２のベキ乗である全ての数のＩＥＥＥ形式と一致し、各々の仮数部は図１に示すように、２のベキ乗の間で僅かに異なるだけである。
【００２９】
純粋対数形式では、表現可能な最大数は以下の通りである。
０  １１１１１１１１．１１１１１１１１１１１１１１１１１１１１１１１
これは底が２の場合、ほぼ２５６から１２７のオフセットを差し引いた対数、すなわち約２１２９または６．８１×１０３８を表わす。
【００３０】
表現可能な最小数は以下の通りである。
０  ００００００００．０００００００００００００００００００００００
これは底が２の場合、−１２７に等しい対数、すなわち５．８８×１０−３９を表わす。必要ならば、全ゼロ形式は、ＩＥＥＥの場合と同様に、擬似的な真ゼロを表わすために予約することができる。このシナリオにおいて、表現可能な最小な数は以下の通りである。
０  ００００００００．００００００００００００００００００００００１
これは底が２の場合、ほぼ−１２７に等しい対数、すなわち約５．８８×１０−３９に対応する。
【００３１】
１と２の間に値を有するＩＥＥＥ仮数の量子化精度は、２−２３のＬＳＢ値であり、精度は２−２３と２−２４（０．６〜１．２×１０−７）の間にある。数ｘを底が２の対数形式で表現する際の精度は、対数における定数２−２３であり、ｄｘ／ｘ＝ｌｏｇｅ（２）×２−２３または０．８３×１０−７を与え、これはＩＥＥＥ量子化精度の平均より僅かに良い。
【００３２】
別の実装方式では、底ｅ等、他の底での対数を用いる場合がある。底がｅの場合、実数を以下で表わされる３２ビット符号付き対数絶対値形式で格納することができる。
Ｓ  ｘｘｘｘｘｘｘ．ｘｘｘｘｘｘｘｘｘｘｘｘｘｘｘｘｘｘｘｘｘｘｘｘ
または簡便に（Ｓ７．２４）で表わす。底が大きい（ｅ＝２．７１８）ため、小数点の左側のビットの個数が少なくてもダイナミックレンジを与えるのに十分である。一方、以下に詳述するように、同じまたはより良い精度を得るには小数点の右側に追加的なビットを必要とする。
【００３３】
対数絶対値部分は、符号付きの固定小数点値であって、最左端のビットが符号であり、表現された数の符号Ｓと混同しないこと。あるいは、対数絶対値部分は＋６４（または＋６３）分オフセットされ、それによりビット・パターン
０  １００００００．００００００００００００００００００００００００
はゼロ対数（数値＝１．０）を表わす。後者の場合、表現可能な最大数は、以下の底ｅの対数を有する。
０  １１１１１１１．１１１１１１１１１１１１１１１１１１１１１１１１
これは、ほぼ１２８であり、６４のオフセットを引いて（less the offset of 64）、すなわちｅ６４または６．２４×１０２７であり、その逆数は表現可能な最小数を表わす。式（６）は、底ｅの対数表現の量子化精度を表わす。
【数４】
2008502036.tif 000006
図２は、ＩＥＥＥ浮動小数点形式（オフセットが＋１２７）を、底がｅの形式（オフセットが＋６４）および底が２の形式（オフセットが＋１２７）と比較する。
【００３４】
底を選択することは、実際には固定語長内のダイナミックレンジと精度の間のトレードオフを決定することに等しく、１整数ビットに満たないステップで小数点を移動させること（moving the point in steps of less than one whole bit）に等しい。
【数５】
2008502036.tif 000007
の底を選択すること（一般的には
【数６】
2008502036.tif 000008
、但しＮは正または負の整数）は、同一性能をもたらしつつ小数点をプラスまたはマイナスＮビット分移動させることに等しい。しかし、８の底を選択することは、対数を３で除算するため、小数点を整数個分移動させることには等しくない。換言すれば、対数の底の選択は、数学的に２進小数点の右側と左側の間のビットの分割を変更することに等しく、精度とダイナミックレンジの間の妥協点が変わる。しかし、小数点はステップ単位でしか移動されず、一方、底は連続的に変更され得る。符号付き対数絶対値の場合（符号無し、１２７オフセットの対数絶対値とは対照的に）、符号ビットは、これを対数絶対値の符号として参照することにより、数値（Ｓビット）の符号とは区別される。これを更に明らかにするために、底が１０の対数ｌｏｇ１０（３）＝０．４７７１、あるいはｌｏｇ１０（１／３）＝−０．４７７１を考慮する。このように、＋３の値を対数で示すには、数値とその対数の符号は共に＋であり、＋＋０．４７７１と書くことができる。下表にこの表記法を示す。
【００３５】
【表１】
2008502036.tif 000009
【００３６】
全ての対数表現が必ず正であるようにすべく、オフセット表現を用いる場合がある。例えば、数値を、ある選択された数、例えば０．０００１の何倍大きいかを示す対数で表現する場合、３の表現はｌｏｇ１０（３／０．０００１）＝４．４７７１に、また１／３の表現はｌｏｇ１０（０．３３３３／０．０００１）＝３．５２２９となる。オフセットにより、両方とも正になっている。０．０００１の表現は、ｌｏｇ（０．０００１／０．０００１）＝０となる。従って、全ゼロ・ビット・パターンは、可能な最小数０．０００１を表わす。
【００３７】
従来の対数表では、真数を参照するために、０．００００と０．９９９９の間の対数用に１０，０００個の数を格納する必要があり、同じ精度まで対数を得るために同様の個数が必要である。参照表のサイズを減らすために、対数的同一性（logarithmic identities）を用いる場合がある。例えば、ｌｏｇ１０（３）＝０．４７７１、およびｌｏｇ１０（２）＝０．３０１０である。これから、演繹すれば直ちに次式が得られる。
ｌｏｇ１０（６）＝ｌｏｇ１０（２×３）＝ｌｏｇ１０（３）＋ｌｏｇ１０（２）＝０．４７７１＋０．３０１０＝０．７７８１
これを演繹すれば直ちに以下も得られる。
ｌｏｇ１０（１．５）＝ｌｏｇ１０（３／２）＝ｌｏｇ１０（３）−ｌｏｇ１０（２）＝０．４７７１−０．３０１０＝０．１７６１
しかし、与えられた数値０．４７７１および０．３０１０をどのように単純に演算しても直ちに以下を演繹することはできない。
ｌｏｇ１０（５）＝ｌｏｇ１０（２＋３）＝０．６９９０
更に、３と２の対数からどのように以下を推論できるかも明らかではない。
ｌｏｇ１０（１）＝ｌｏｇ１０（３−２）＝０
【００３８】
この問題に対処すべく、対数加算関数Ｆａに基づく参照表を用いる場合がある。例えば、（２＋３）の対数は、底が１０の場合、ｌｏｇ１０（３）とｌｏｇ１０（２）のうち大きい方、すなわち０．４７７１を、それらの差の関数Ｆａ[ｌｏｇ１０（３）−ｌｏｇ１０（２）]＝Ｆａ（０．１７６１）に加算することで得られる。
Ｆａ（ｘ）＝ｌｏｇ１０（１＋１０−ｘ）  （７）
同様に、３−２の対数は、ｌｏｇ１０（３）とｌｏｇ１０（２）のうち大きい方から関数Ｆｓ（０．１７６１）を減算して得られる。ここに、底が１０の場合のＦｓ（ｘ）は以下の通りである。
Ｆｓ（ｘ）＝ｌｏｇ１０（１−１０−ｘ）  （８）
しかし、Ｆａ（ｘ）およびＦｓ（ｘ）用の参照表は依然として、各々の関数用に少なくとも１０，０００個の数値を格納する必要がある。
【００３９】
補間法
補間を用いて、参照表に格納する値の数を減らすことができる。後の考察を容易にすべく、以下で補間を更に詳しく調べる。説明を簡便にすべく、底ｅを用いる。しかし、他の底も同様に適用できる点を理解されたい。
【００４０】
例えばｘｏの有限個の表の値を用いて、すなわち表の点ｘｏの回りの関数Ｆ（ｘ）のテイラー／マクローリン展開を用いて、関数Ｆａ（ｘ）＝ｌｏｇｅ（１＋ｅ−ｘ）を計算すれば、次式が得られる。
Ｆ（ｘ）＝Ｆ（ｘｏ）＋（ｘ−ｘｏ）Ｆ’（ｘｏ）＋０．５（ｘ−ｘｏ）２Ｆ”（ｘｏ）．．．，  （９）
ここに、’は１次導関数を表わし、”は２次導関数を表わす。この展開に基づいて、ｌｏｇｅ（ｃ）＝ｌｏｇｅ（ａ＋ｂ）をテイラー／マクローリン展開の利点を用いてｌｏｇｅ（ａ）＋Ｆａ（ｘ）として計算することができる。ここに、ｘ＝ｌｏｇｅ（ａ）−ｌｏｇｅ（ｂ）であり、ｘｏの値は表で提供される。
【００４１】
３２ビットの底がｅの場合に簡単な線型補間を用いるには、２次導関数Ｆ”を含む２次項が、２４番目の２進位置、例えば２−２５未満まで無視できなければならない。Ｆａ（ｘ）＝ｌｏｇｅ（１＋ｅ−ｘ）を微分して次式が得られる。
【数７】
2008502036.tif 000010
Ｆａ”（ｘ）は、ｘ＝０のとき最大値０．２５をとる。従って、２次項は、（ｘ−ｘｏ）＜２−１１のとき２−２５未満である。この必要条件を満たすには、最上位ビットは、形式（５．１１）で表の点ｘｏをアドレス指定する。すなわち、
ｘｘｘｘｘ．ｘｘｘｘｘｘｘｘｘｘｘ
である。これは、剰余ｄｘ＝ｘ−ｘｏが以下の形式であって、
０．０００００００００００ｘｘｘｘｘｘｘｘｘｘｘｘｘ、
従って２−１１未満であるようにするためである。このように、ｄｘは１３ビットの数値であり、ｘｏは１６ビットの数値である。
【００４２】
線型補間項Ｆａ’（ｘｏ）の精度もまた、２−２５のオーダーでなければならない。Ｆａ’（ｘｏ）には２−１１未満であるｄｘが乗算されるため、Ｆａ’（ｘｏ）の精度は２−１４でなければならない。Ｆａ（ｘｏ）が丸め誤差の減少に寄与すべく表に１対の追加的なＬＳＢを提供してもよいが、この場合、各々のｘｏ値についてＦとＦ’を格納するために幅が５バイト（４０ビット）の参照表が必要となる。
【００４３】
従って、タブラー値は、２６ビットのＦａの２１６＝６５，５３６個の値、および同じ個数の対応する１４ビットＦａ’値を含んでいる。また、ｄｘ・Ｆａ’の形成に１４×１３ビット乗算器が必要である。このような乗算器は、本質的に、１３個のシフトおよび加算演算を実行し、従って約１３個の論理遅延を含んでいる。乗算器の複雑さと遅延はブースのアルゴリズムを用いて若干減らすことができるが、ベンチマークとして従来の乗算器を用いてもよい。
【００４４】
図３に、上述の線型補間を実装する従来型ＡＬＵの例証的なブロック図を示す。図３のＡＬＵは、減算器１０、加算器２０、Ｆａ／Ｆａ’参照表３０、乗算器４０、および減算器５０を用いて、値Ｃ＝ｌｏｇｅ（Ａ＋Ｂ）を推定する。本例で用いるように、Ａ＝ｌｏｇｅ（ａ）且つＢ＝ｌｏｇｅ（ｂ）である。後述するように、特異点を避けるべく減算用に後方補間を行なう必要があるため、図３にＸＭ、すなわちｘの最上位１６ビット部分より１ビット大きいｘｏの値、からの補間を示す。従って、Ｆａ用の参照表３０はＸＭ＋１におけるＦａの値を含み、含まれるＦａ’用の値は当該区間の中央値、すなわちＸＭ＋０．５で計算されたＦａ’の値である。乗算器４０は、１４ビットのＦａ’（ＸＭ）の値に、ｘの最下位１３ビットの、１３ビットで表わされる２の補数である（by the 13 bit two's complement of the least significant 13 bits of x）
【数８】
2008502036.tif 000011
を乗ずる。更に、乗算器４０は、結果がＦａ’（ＸＭ）と
【数９】
2008502036.tif 000012
の２７ビットで表わされる積であるように構成されている。
【００４５】
２７ビットで表わされる積のＬＳＢは、減算器５０への桁下げとして入力されて、残り２６ビットが２６ビットＦａ’（ＸＭ）値から減算されて２６ビットへの補間値を生成し、その値は次いで出力加算器２０内でＡとＢのうち大きい方に加算され、「１」の桁上げビットによりその結果Ｃを対数絶対値の３１ビットに切上げることができる。
【００４６】
従って、線型補間に基づく実用的な３１ビット対数加算器は、約６５，５３６×４０＝２．６２Ｍビットの参照表３０、および１３×１４ビットの乗算器４０を含んでいる。これらの構成要素は、かなり大きいシリコン領域（silicon area）を占有して、論理遅延に関して速度面での効果が無い。しかし、補間方法を用いて減算または複素数算術演算に対処すべく、語長および乗算器構成を大幅に調整する必要がある。
【００４７】
例えば、補間を用いて減算を実行するために、以下に与えられる減算関数方程式により関数値が決定される。
ＦＳ（ｘ）＝ｌｏｇｅ（１−ｅ−ｘ）    （１１）
Ｆｓ（ｘ）のテイラー／マクローリン補間は、以下の１次導関数を含んでいる。
【数１０】
2008502036.tif 000013
これはｘが０に近づくにつれ無限大に発散する。この特異点からの演算を遠ざけるべく、次式を用いて、ｘ＝ｌｏｇｅ（Ａ）−ｌｏｇｅ（Ｂ）（Ａ＞Ｂの場合）の実際の値より大きいＬＳＢ１個分タブラー値から後方に関数を補間する場合がある。
Ｆｓ（ｘ）＝Ｆｓ（ｘｏ）−（ｘｏ−ｘ）Ｆｓ’（ｘｏ）  （１３）
これは、図３の対数加算について示した実装方式である。次いで、少なくともｘの最上位ビットがゼロである場合、特異点を回避するためにのみ、ｘｏは値においてＬＳＢ１個分大きい。
【００４８】
加算の場合と同じ１６／１３ビット分割により、ｘｏの最小値は２−１１であって、Ｆｓ’のサイズは約２，０４８個の値である。しかし、Ｆｓ’の値は自身の対数加算の相手より１２ビット長いため、ｄｘ・Ｆｓ’を形成する乗算器のサイズを１３×２６ビットの装置へ増大させる。上記に鑑みて、実数の加算と実数の減算とのシナジーは、複素数演算の場合と同様に、補間を実装するＡＬＵに制限される。同時係属出願（４０１５−５２８１）に提案されている、後者の問題に対する一つ解決策は、参照表がチップ領域を占有することから、加算と減算用に別々の回路を形成しても殆どコストが掛からないとの認識に基づいており、従ってバタフライの実行（ＦＦＴで有用な加算と減算の同時実行）を可能にするものである。引数が類似していることから、実数および複素数演算用に別々の回路を形成して並列処理を可能にすることが示唆される。いずれにせよ、補間を実行するために参照表および乗算の両方が必要なことから、従来の補間法をハードウェアロジックで実装するのはより複雑になる。
【００４９】
反復的対数演算
上述の補間処理に代わるものとして、また記憶要件を減らすために、反復的解法を用いる場合がある。反復的解法は２個の比較的小さい参照表を用いて、表にされた関数に基づき反復的な処理を用いて対数出力を計算する。反復的解法を示すために、１０進数の例として、ｌｏｇ１０（３）＝０．４７７１およびｌｏｇ１０（２）＝０．３０１０からｌｏｇ１０（５）＝ｌｏｇ１０（３＋２）およびｌｏｇ１０（１）＝ｌｏｇ１０（３−２）を推論する仕方について説明する。
【００５０】
対数加算関数表（以下でＦａ表とも呼ぶ）は、底が１０の場合に、０．０と４．９の間におけるｘの値を０．１刻みで、式（７）に基づいて５０個の値を格納している。他の表（以下で補正表またはＧ表と呼ぶ）は、次式に基づいて、０．００１と０．０９９の間におけるｙの値を０．００１刻みで９９個の値を格納する。
Ｇ（ｙ）＝−ｌｏｇ１０（１−１０−ｙ）    （１４）
以下に、これら２個の参照表を用いて上述のｌｏｇ（５）＝ｌｏｇ（３＋２）の例に対する２表反復処理を示す。以下は底が１０の場合について記述しているが、当業者であれば任意の底を用いてもよいことが理解されよう。底１０とは異なる底を用いる実施形態のために、式（７）および（１４）が各々底１０での計算用の関数および補正表を定義する一方、式（１５）は一般に、任意の底ｑについて関数および補正表を定義することが理解されよう。
Ｆａ（ｘ）＝ｌｏｇｑ（１＋ｑ−ｘ）  
Ｇ（ｙ）＝−ｌｏｇｑ（１−ｑ−ｙ）  （１５）
【００５１】
対数加算処理の場合、引数ｘ＝Ａ−Ｂ＝ｌｏｇ１０（３）−ｌｏｇ１０（２）＝０．１７６１は最初に、最も近い小数点以下１桁（the nearest tenth）すなわち０．２に丸められる。５０個の値を含むＦａ表から、Ｆａ（０．２）＝０．２１２４であることがわかる。０．２１２４を０．４７７１に加算した結果、ｌｏｇ１０（２＋３）の第１近似として０．６８９５が得られる。ｘを０．１７６１から０．２に丸めることで生じる誤差分値は、０．０２３９である。この誤差は決して０．０９９を超えないため、値９９の補正参照表Ｇ（ｙ）を用いる。補正値ｙ＝０．０２３９が０．０２４へ切上げられてＧ表は補正値１．２６９５を与える。Ｇ（ｙ）＝１．２６９５、第１参照表からの値Ｆａ（０．２）＝（０．２１２４）、およびｘ（０．１７６１）の当初の値を組み合わせてＦａのための新たな引数、ｘ’＝１．６５８が生成される。当業者であれば、この場合ｘを修飾するプライム記号（’）は微分を表わしていない点を理解されよう。
【００５２】
最も近い小数点以下１桁に切上げられた場合、ｘ’＝１．７である。Ｆａ（１．７）＝０．００８６であり、これをｌｏｇ１０（２＋３）の第１近似値０．６８９５に加算すれば０．６９８１の第２近似が得られる。１．６５８を１．７に切上げたことによる誤差は、０．０４２である。ｙ＝０．０４２をＧ表で調べると、値１．０３５が得られ、これを０．００８６の前のＦａ値に加算し、且つｘ’＝１．６５８であることから、新しいｘ値すなわちｘ”＝２．７０１６が得られる。ｘ”を２．８に切上げた後でＦａ表を用いれば、Ｆａ（２．８）＝０．０００７が得られる。第２近似値（０．６９８１）に０．０００７を加算することにより、第３且つ最終の近似値０．６９８８が得られ、これは５０個の値しか含まないＦａ参照表、および１００個の値しか含まないＧ参照表を使用した場合に期待できる精度で、実際の値０．６９９０に十分近いと見なされる。必要ならば、更なる反復を行なって、若干精度な上げることができる。しかし、加算の場合、一般に４回以上の反復は必要ない。あるいは、最大反復回数が予め３に設定されている場合、最後の反復のＦａの引数を常に２．７の最も近い小数点以下１桁へ切上げるのではなく、切捨ててもよい。Ｆａ（２．７）＝０．０００９であり、これをｌｏｇ１０（３＋２）の第２近似値０．６９８１に加算すれば、予想結果ｌｏｇ１０（５）＝ｌｏｇ１０（３＋２）＝０．６９９０が得られる。
【００５３】
２表反復的処理は、乗算が回避され且つ参照表のサイズが百分の一に減少するのと引き換えに３段階の処理を受け入れることを含んでいる。ハードウェア実装において、３回の反復に必要な論理遅延の総数は実際には、乗算器の反復的な加算／シフト構造を通過する論理遅延の数より少なくて済む。いずれにせよ、上述の参照表サイズの縮小は、シリコン領域および／または精度が主な重要事項である場合に有用である。
【００５４】
ｌｏｇ１０（３−２）の値も同様に計算することができる。開始時の近似値は、より大きい数、すなわち０．４７７１の対数である。減算用のＦｓ表は以下の値を０．１刻みで格納し、Ｇ表は不変のままである。
Ｆｓ（ｘ）＝ｌｏｇ１０（１−１０−ｘ）（底が１０の場合）
Ｆｓ（ｘ）＝ｌｏｇｑ（１−ｑ−ｘ）（一般的な底ｑの場合）  （１６）
ｌｏｇ１０（３）とｌｏｇ１０（２）の差０．１７６１は最も近い小数点以下１桁０．２へ切上げられる。減算関数表で０．２を参照すればＦｓ（０．２）＝−０．４３２９が得られる。開始時近似値０．４７７１に−０．４３２９を加算すればｌｏｇ１０（１）に対する第１近似値０．０４４２が得られる。
【００５５】
０．１７６１を０．２に切上げたことによる誤差は、加算の場合、０．０２３９である。先に定義されたようにＧ表を０．０２４でアドレス指定すれば値１．２６９５が返される。先のＦｓ引数ｘ＝０．１７６１および先のＦｓ表参照値−０．４３２９に１．２６９５を加算することにより、新たなＦｓ表引数ｘ’＝１．０１２７が得られる。ｘ’を最も近い小数点以下１桁１．１に切上げ、且つＦｓ表を用いることで再びＦｓ（１．１）＝−０．０３５９が得られる。第１近似値（０．０４４２）に−０．０３５９を加算することにより、ｌｏｇ１０（１）の第２近似値０．００８３が得られる。１．０１２７を１．１に切上げたことによる誤差は０．０８７３である。値０．０８７を用いてＧ表をアドレス指定すればＧ（０．０８７）＝０．７４１０が得られる。これを先の丸めていないＦｓ表引数１．０１２７およびＦｓ表参照値−０．０３５９に加算したならば、新たなＦｓ表引数ｘ”＝１．７１７８が得られる。ｘ”を１．８に切上げた結果Ｆｓ（１．８）＝−０．００６９が得られ、これを第２近似値０．００８３に加算して結果的にｌｏｇ１０（１）の第３近似値０．００１４が得られる。１．７１７８を１．８に切上げたことによる誤差は０．０８２２である。０．０８２でＧ表をアドレス指定すれば値０．７６４３が返される。これを先のＦｓ表引数１．７１７８および先のＦｓ表参照値−０．００６９に加算することにより新たなＦｓ表引数ｘ’’’＝２．４７５２が得られる。２．４７５２を２．５に切上げることにより関数値Ｆｓ（２．５）＝−０．００１４が得られる。第３近似値（０．００１４）に−０．００１４を加算することにより、予想通りｌｏｇ１０（１）＝ｌｏｇ１０（３−２）＝０が得られる。各々の反復についてＦｓの引数が増大する結果、次第に補正が小さくなるため、本アルゴリズムは収束する。
【００５６】
減算の場合の上述の方法は、Ｆ表の減算バージョンを用いる点が異なるが、加算に関して同様である。しかし、加算と減算は同一のＧ表を用いる。更に、減算で良い精度を得るには加算より１回多くの反復が必要である。この理由は、減算の場合、Ｆｓ値を加算した際の増分が負であるため、各反復におけるＦｓの引数の立ち上がり僅かに遅く、特に最初の反復でこれが顕著だからである。
【００５７】
高精度対数加算
一般に、より一般的な底がｑの対数について解決すべき対数加算問題は、以下のステップで与えることができる。
・Ａ＝ｌｏｇｑ（ａ）およびＢ＝ｌｏｇｑ（ｂ）と仮定する。ここに、ａおよびｂは正数、且つｑは底である。
・目的：Ｃ＝ｌｏｇｑ（ｃ）を見つけること。ここで、ｃ＝ａ＋ｂである。
・従って、Ｃ＝ｌｏｇｑ（ａ＋ｂ）＝ｌｏｇｑ（ｑＡ＋ｑＢ）である。
・ＡをＡとＢのうち大きい方とする。
・この場合Ｃ＝ｌｏｇｑ（ｑＡ（１＋ｑ−（Ａ−Ｂ））
＝Ａ＋ｌｏｇｑ（１＋ｑ−（Ａ−Ｂ））
＝Ａ＋ｌｏｇｑ（１＋ｑ−ｒ）、ここにｒ＝Ａ−Ｂ、且つ正である。
従って、当該問題は１変数ｒの関数ｌｏｇｑ（１＋ｑ−ｒ）の計算に帰着された。
【００５８】
ｒの語長に制限がある場合、関数値を関数参照表により取得してもよい。例えば、１６ビットのｒ値の場合、関数参照表は６５，５３６個のワードを格納しなければならない。更に、底がｑ＝ｅ＝２．７１８の場合にｒ＞９であるならば、関数の値は２−１３未満の差でゼロと異なり、このことは、１２ビットの小数部と共に、１５までの範囲のｒの４ビットの整数部だけを考慮すればよいことを示唆している。従って、ｒ＞９の場合、関数値は小数点以下２進１２桁までゼロであり、従って参照表は、９×４，０９６＝３６，８６４ワードのメモリを占める、最大９までのｒの値だけが必要とされる。
【００５９】
ｒ＝０の場合、関数の最大値がｌｏｇｅ（２）＝０．６９であるため、１２ビットの小数部だけを格納すればよく、従って必要なメモリは６５，５３６個の１６ビットワードではなく、３６，８６４個の１２ビットのワードだけで済む。底が２の場合、関数はｒ＞１３の場合に２進１２桁までゼロであるため、ここでもｒの４ビットの整数部だけを考慮すれば済む。符号に１ビットを用いる場合、対数絶対値部分の長さは、例えば４．１１形式または５．１０形式では、１５ビットに過ぎず、且つ上述の数値は適宜調整できる。
【００６０】
しかし、例えば３２ビットの語長を用いて、１６ビットよりもはるかに高い精度を得るには、関数のための直接参照表（a direct look-up table for the function）が極端に大きくなる。例えば、ＩＥＥＥの３２ビット浮動小数点標準と同等の精度およびダイナミックレンジを与えるには、底がｅの場合にＡおよびＢは各々７ビットの整数部、２４ビットの小数部、および符号ビット１個を有していなければならない。関数が２４ビットの精度でゼロである前に、ｒの値が２５ｌｏｇｅ（２）＝１７．３２より大きくなければならず、これはｒの５ビットの正整数部により表現可能である。このように、５．２４形式で可能な２９ビットのｒ値を関数Ｆａの引数とみなさなればならない。０と１８の間のｒ値を直接参照するために、１８×２２４すなわち３億２００万個の２４ビットワードの参照表サイズが必要となる。実質的に、あらゆる対数演算の研究はこれらの表のサイズを減らすことを意図しており、６４ビット語長を実用的にすることが究極の目的である。本明細書に述べるいくつかの技術は、この目的へ向けて技術を進歩させるものである。
【００６１】
ｒの全てのビットをアドレスとして用いる対数加算関数Ｆａを直接参照する必要により、参照表のサイズを単一の大きな表から減らすべく、本発明の一実施形態は、ｒを最上位（ＭＳ）および最下位（ＬＳ）部分、すなわちｒＭとｒＬに分割するステップを含んでいる。以下に述べるように、これらのＭＳおよびＬＳ部は、はるかに小さい２個の表Ｆ、Ｇを参照する。ＭＳ部は、入力値の「切上げられた」バージョンを表わし、一方ＬＳ部は切上げられたバージョンと元の完全な引数値との差を表わす。
【００６２】
式（１７）に示すように、ｒＭをｒ＜３２の最上位１４ビット、ｒＬをｒの最下位１５ビットとする。
ｒＭ＝ｘｘｘｘｘ．ｘｘｘｘｘｘｘｘｘ
ｒＬ＝０００００．０００００００００ｘｘｘｘｘｘｘｘｘｘｘｘｘｘｘ  （１７）
簡便のため、ｒＭおよびｒＬの長さを略して（５．９）および（１５）と表記する場合がある。本方法に明らかな変更を加えることにより、ｒを最上位および最下位ビット部分に分割する他の仕方も等しく使用可能であり、以下に詳述する特定の分割を好適な対象とした考察では、異なる語長（例：１６ビット）または複素数演算に対して同じＦおよびＧ表を再利用可能なことが関心事項である。
【００６３】
ｒＭ＋を、ｒＬの可能な最大値、すなわち０００００．０００００００００１１１１１１１１１１１１１１１により増分されたｒＭの値とする。これは、最下位１５ビットが１に設定された元のｒ値そのものである点を理解されたい。いくつかの実施形態において、代替的にｒＭを０．００００００００１だけ増分することができる。すなわち次式が得られる。
ｒＭ＋＝ｘｘｘｘｘ．ｘｘｘｘｘｘｘｘｘ＋０００００．００００００００１  （１８）
ｒＬの補数値を次式で表わすことができる。
ｒＬ−＝ｒＭ＋−ｒ    （１９）
これは、ｒＭに対する上述の２個の代替的な増分のどちらが使われるかに応じて、ｒＬの補数または２の補数のいずれかである。すなわち、ｒＬ−＝
０００００．０００００００００１１１１１１１１１１１１１１１−０００００．０００００００００ｘｘｘｘｘｘｘｘｘｘｘｘｘｘｘ（ｒＬの補数）またはｒＬ−＝０００００．００００００００１０００００００００００００００−０００００．０００００００００ｘｘｘｘｘｘｘｘｘｘｘｘｘｘｘ（ｒＬの２の補数）である。ここから、底ｅの場合に以下の結果が得られる。
【数１１】
2008502036.tif 000014
ここに、
【数１２】
2008502036.tif 000015
である。ｌｏｇ（１＋ｅ−ｒ）を同様に拡張すれば次式が得られる。
【数１３】
2008502036.tif 000016
ここに、
【数１４】
2008502036.tif 000017
である。結論に至るまで反復することにより、所望の解は以下の関数の和を含んでいることがわかる。
【数１５】
2008502036.tif 000018
これらは各々のｒ引数の最上位１４ビットだけに依存し、それらの引数は１６，３８４ワードしか含まない参照表から取得することができる。
【００６４】
式（２０）〜（２２）の文脈において、表記ｒ値の修飾に用いるプライム記号（群）は、導関数を表わすものではない。その代わりに、一連のｒ値、すなわちｒ、ｒ’、ｒ”等は、対数加算関数参照表（Ｆａ）から直近に得た値を先行する値に累算して（accumulating）、ｒの最下位１５ビットすなわち、ｒＬ−が１５ビット値であるため３２，７６８ワードを有する補正参照表すなわちＧ表により与えられる値
【数１６】
2008502036.tif 000019
に依存する値を加算することにより、導かれる。
【００６５】
格納された値がｒＭ＋およびｒＬ−から計算されているが、関数および補正参照表を各々ｒＭおよびｒＬにより直接参照することができる。これらの参照表関数を各々関数ＦａおよびＧと呼び、補正値が常に極めて大きな負値である点に注目して、正の補正値をＧ表に格納してもよい。負の値を格納してこれを減算するのではなく、この正の補正値を先のｒ引数に加算する。更に、格納されている値からＧ表の最小補正値または少なくともその整数部を減算して、格納されているビット数を減らし、表から値が抽出される都度足し戻してもよい。底が２の場合、最小補正値として値８が適しており、いくつか実施形態では足し戻す必要さえない。その場合反復処理は以下のとおりである。
１．出力アキュムレータ値ＣをＡとＢのうち大きい方に初期化する。
２．Ａの方が大きい場合はｒをＡ−Ｂに、またはＢの方が大きい場合はＢ−Ａに初期化する。
３．ｒをｒＭとｒＬに分割する。
４．各々ｒＭおよびｒＬによる指定に従いＦａ（ｒＭ＋）およびＧ（ｒＬ−）を参照する。
５．ＦａにＣを、およびＦａ＋Ｇにｒを累算する。
６．ｒ＜ＳＴＯＰ_ＴＨＲＥＳＨＯＬＤ（以下に詳述）の場合はステップ３から繰返す。
【００６６】
当業者であれば、論理ｂ６．ＯＲ．（ｂ５．ＡＮＤ．（ｂ４．ＯＲ．ｂ３．ＯＲ．ｂ２））（第８、４または２ビットのうち１個が設定される、第３２ビットの設定または第１６ビットの設定）を用いて１８より大きいｒ値を検出するために数個の論理ゲートを用いてよいこと（ここで、ビット・インデックスは小数点の左側にビット位置を示す）が理解されよう。関数
【数１７】
2008502036.tif 000020
の値は常に約６．２４より大きく、従って反復は常に３サイクル以下で終了する。底が２の場合、補正値は比例的に大きく、そのため底が２の場合にｒは常に高々３サイクルで２５を超える。一般に、任意の底に対して３サイクルで十分である。
【００６７】
高精度２表対数減算
ＡおよびＢに関連付けられた符号Ｓが、ａとｂは同じ符号を有することを示す場合、上述の対数加算アルゴリズム（「対数加算」と略す）を用いることができる。そうでない場合、対数減算アルゴリズム（「対数減算」と略す）が必要である。下表に各々のアルゴリズムが用いられる場合分けを示す。
【００６８】
【表２】
2008502036.tif 000021
対数加算アルゴリズムを用いた場合、結果の符号は常に大きい方の対数絶対値に関連付けられた符号である。
【００６９】
第２の引数に関連付けられた符号が最初に反転された場合、同じことが対数減算アルゴリズムでも成り立つ。減算を行うことが求められた場合、対数演算ユニットへの入力に第２の引数が適用されたならば、第２の引数の符号の反転が行なわれる。「対数減算」アルゴリズムは、以下のように導かれる。Ａ＝ｌｏｇ（｜ａ｜）且つＢ＝ｌｏｇ（｜ｂ｜）が与えられていると仮定する。Ｃ＝ｌｏｇ（ｃ）を見出すことが求められ、ここにｃ＝｜ａ｜−｜ｂ｜である。Ａは、ＡとＢのうち大きい方とする。わかりやすく絶対値文字（｜｜）を外し、ここでａとｂの両方が正と仮定すれば、次式が得られる。
Ｃ＝ｌｏｇｅ（ａ−ｂ）＝ｌｏｇｅ（ｅＡ−ｅＢ）    （２３）
対数加算と同様に、本例でも説明目的だけのために底としてｅを用いているが、これに限定されない。
【００７０】
ＡがＢより大きいと仮定しているため、次式が得られる。
Ｃ＝ｌｏｇｅ（ｅＡ（１−ｅ−（Ａ−Ｂ）））
＝Ａ＋ｌｏｇｅ（１−ｅ−（Ａ−Ｂ））
＝Ａ＋ｌｏｇｅ（１−ｅ−ｒ）                  （２４）
ここにｒ＝Ａ−Ｂであり、その値は正である。従って、問題は１変数ｒの関数ｌｏｇ（１−ｅ−ｒ）の計算に帰着する。ｒＭ、ｒＬ、ｒＭ＋およびｒＬ−を以前定義された通りとする。すると、底ｅの場合、次式が得られる。
【数１８】
2008502036.tif 000022
ここに、
【数１９】
2008502036.tif 000023
である。ｌｏｇｅ（１−ｅ−ｒ’）を拡張すれば次式が得られる。
【数２０】
2008502036.tif 000024
ここに、
【数２１】
2008502036.tif 000025
であり、以下同様である。結論に至るまで反復することにより、所望の解は以下の関数の和を含んでいることがわかる。
【数２２】
2008502036.tif 000026
これらは各々の全語長ｒ値の最上位１４ビットだけに依存し、１６，３８４のワードだけを含む参照表により与えられる。
【００７１】
対数加算と同様に、対数減算用の参照表は、格納された値がｒＭ＋とｒＬ−から計算されているものの、ｒＭとｒＬにより直接参照できるように構成することができる。更に、対数加算と同様に、表記されたｒ値を修飾するために用いるプライム記号（群）は導関数を表わすものではない。
【００７２】
これらの参照表ＦｓおよびＧ（Ｇは対数加算アルゴリズムの場合と同じ参照表である）を各々呼び出して、上述のようにＧの正値を格納することにより、対数減算処理用に必要なＦｓおよびＧ表が生成される。１−ｅ−ｒが常に１より小さいため、Ｆｓは常に負であり、従って正の大きさ（positive magnitude）を格納して加算ではなく減算することができる。別の方法は、負の符号ビットを外した負値を格納して、減算が実行中の場合は最上位「１」を付加することにより負のビット符号を参照表の外側で置換しておく。好適な選択は、以下で詳述するように、どちらの論理が単純で、加算と減算の間の参照表の値に最大のシナジーが得られるかによる。いずれにせよ、以下のステップが「対数減算」処理の概要を示す。
１．出力アキュムレータ値ＣをＡとＢのうち大きい方に初期化する。
２．Ａの方が大きい場合はｒをＡ−Ｂに、またはＢの方が大きい場合はＢ−Ａに初期化する。
３．ｒをｒＭとｒＬに分割する。
４．各々ｒＭおよびｒＬによる指定に従いＦｓ（ｒＭ＋）およびＧ（ｒＬ−）を参照する。
５．ＦｓにＣを、およびＦｓ＋Ｇにｒを累算する。
６．ｒ＜ＳＴＯＰ_ＴＨＲＥＳＨＯＬＤ（以下に詳述）の場合はステップ３から繰返す。
【００７３】
対数加算および対数減算アルゴリズムの両方において、ＳＴＯＰ_ＴＨＲＥＳＨＯＬＤは、その後の反復からの寄与がＬＳＢの半分に満たないよう、選択される。これは、小数点以下２進２４桁を有する底ｅの場合は１７．３２（１８を用いてよい）で生じ、あるいは小数点以下２進２３桁を有する底２の場合は２４で生じる。原理的には、ＳＴＯＰ_ＴＨＲＥＳＨＯＬＤ３１を与える、底２より小さい底を見出す可能性があり、その場合、ｒの選択されたＭＳＢによりアドレス指定可能な全アドレス空間にわたり定義されるＦ関数を用いる。あるいは、ＳＴＯＰ_ＴＨＲＥＳＨＯＬＤ１５を与え、同じ特性を有する、底ｅより大きい底を見出す場合がある。しかし、Ｆ表のために全アドレス空間を用いることで得られる利点よりも、底が２であることの実際的な利点の方が大きいと思われる。一般に、底が２の場合、ＳＴＯＰ_ＴＨＲＥＳＨＯＬＤは、小数点以下の対数表現の２進位置の個数より単に１、２個大きいだけである。
【００７４】
上に挙げた１０進数の例で示唆されるように、Ｆ表を参照するために用いた最後の引数、例えば
【数２３】
2008502036.tif 000027
を、
【数２４】
2008502036.tif 000028
から切上げるのではなく切捨てれば、有限回数の反復の後で精度が向上する。２表反復処理が常に一定回数の反復を実行するか、あるいは処理が最後の反復を識別するならば、Ｆの引数を最後の反復で切り捨てることができる。最後の反復は、ｒが例えばＳＴＯＰ_ＴＨＲＥＳＨＯＬＤのある範囲（底ｅの場合〜６、底が２の場合〜８）内にあって、次の反復がＳＴＯＰ_ＴＨＲＥＳＨＯＬＤを超える筈であることが示されることにより識別できる。この方法を用いる場合、ｒＬの左端ビットが最後の反復でゼロになったならば、Ｆ表へのアドレスを１だけ減らすことができる。後述するパイプライン実装において、最終的なＦ表の内容は、切り捨てられた引数のために単純に計算される。
【００７５】
対数減算と対数加算アルゴリズムの唯一の違いは、参照表としてＦａではなくＦｓを用いる点である。両方ともサイズが１６，３８４ワードであるため、＋または−のバージョンを選択するための追加的アドレス・ビットを有する単一関数のＦ表に組み合わせすることができ、これをＦ（ｒＭ，ｏｐｃｏｄｅ）と表記する。ここで、追加的な引数「演算コード（ｏｐｃｏｄｅ）」が、対数加算または対数減算アルゴリズムのどちらを適用するべきかを示す０または１の値を取る追加的なアドレス・ビットである。あるいは、周辺ロジック（すなわち入出力アキュムレータおよび加算器／減算器）は各々の参照表に比べて小さいため、周辺ロジックを複製して独立の加算器および減算器を形成するためにほとんどコストを要しない。以下に考察する更に別の可能性として、関数Ｆａと−Ｆｓの類似性を利用することができる。
【００７６】
指数近似
上述のように、ｒＭ＋は、ｒＬの取り得る最大の値（０．０００００００００１１１１１１１１１１１１１１）だけ増やしたｒＭを含んでいても、あるいは０．００００００００１だけ増やしたｒＭを含んでいてよい。ｒＭの増分として０．００００００００１ではなく０．０００００００００１１１１１１１．．．．１を選択する利点は、ｒＭ＝０の場合に直接Ｆの値を得るために、反復的アルゴリズムを実行する間にｒＬの補数でＧ表をアドレス指定しても、あるいはｒＬ（補数を取られていない）により参照してもよい点であり、従って他の方法では困難な、２個のほぼ等しい値の減算を行なうのに単一の反復で十分な点である。補数を取った値及び補数を取らなかった値の両方を利用可能にする方が、桁上げを伝播する必要がなくなるため、２の補数を求めるよりも簡単且つ高速に行なえる。
【００７７】
対数加算の場合、Ｆａ表の値は次式で定義することができる。
【数２５】
2008502036.tif 000029
ここにｄは、好適にはＸＬが取り得る最大値、すなわち全桁１である増分を表わす。当該関数は、ＸＭによりアドレス指定される参照表として構成することができる。減算の場合、Ｆｓ表の値は次式で定義することができる。
【数２６】
2008502036.tif 000030
ＸＭの大きい値に対してＦａ（ＸＭ）＝Ｆｓ（ＸＭ）であり、且つ３２ビット演算および１６〜２４の範囲の引数に対して両方とも次式により正確に近似することができる。
【数２７】
2008502036.tif 000031
ここに、ＸＭ１はＸＭの整数部（小数点の左側のビット）、ＸＭ２は小数部、すなわち小数点の右側のビットである。カッコ内の関数は、小さい指数参照表に格納することができる。右シフタが整数部を実装することにより、小数ビットだけが指数関数を参照すればよくなるため、表のサイズが小さくなる。
【００７８】
図４に、指数近似（Ｅ）と真の関数値（Ｆａ，Ｆｓ）の類似を示す。引数が１６〜２４の範囲で変動する場合、Ｅは実質的にＦａおよびＦｓに等しい。更に、図４はまた、次式の更なる近似値がどのように指数近似と真の関数値の差、すなわちｄＦａ＝Ｅ−ＦａおよびｄＦｓ＝Ｆｓ−Ｅを十分に近似するかを示す。
【数２８】
2008502036.tif 000032
従って、図４から分かるように、８〜１６の範囲のＸＭに対して、長さが８ビット以下の小さい補正値Ｅ２により補正された場合に指数近似Ｅを用いてもよい。その結果は、２進小数点以下２４桁が必要な場合、長さが１７ビットである。
【００７９】
Ｅ曲線の下側の領域は、指数近似の実装に必要なシリコン領域に概ね近いため、図４はまた対数加算および対数減算演算用の関数表を実装するために必要な近似的シリコン領域をも示す。垂直スケールとして底が２の対数スケールを用いることは、高さが２進値で語長を表わすことを意味する。水平スケールはそのような値の個数を表わす。従って、曲線の下側の領域は、曲線値を格納するために必要なＲＯＭのビット数を表わす。しかし、指数関数Ｅは周期的であり、その値は１増分される都度右シフトされる点を除いて繰り返される。従って、小数部ＸＭ２によりアドレス指定される１サイクルだけを格納して、その結果をＸＭ１が与える位置の個数分シフトすればよい。指数関数Ｅは従って、極めて小さい表で済む。更に、補正値ｄＦまたはＥ２は明らかに元のＦａおよびＦｓ関数よりも曲線の下側の領域が小さいため、指数近似Ｅを用いて補正値ｄＦおよびＥ２を格納する方がＦａとＦｓを格納するよりも表サイズが小さくて済み、従って、より小さいシリコン領域で済む。
【００８０】
式（３２）は最下位ビットのＧ関数を次式で与える。
【数２９】
2008502036.tif 000033
ここに、（ｄ−ＸＬ）はｄが全１である場合のＸＬの補数に等しい。Ｇ（ＸＬ）の最小値は、ＸＭとＸＬの間で３１ビットの対数絶対値の分割に依存する。ＸＭが５．８形式である場合、ＸＬは０．００００００００ｘｘｘｘｘｘｘｘｘｘｘｘｘｘｘ形式であって２−８より小さい。従って、ＸＬ＝０の場合、Ｇの最小値は８．５である。形式（５．７）のＸＭの場合、Ｇの最小値は７．５であり、形式（５．９）のＸＭの場合、Ｇの最小値は９．５である。各サイクルでＸの値は少なくともＧの値分増加するため、３個のＧ値が平均して８を超える限り、Ｘは３サイクル以内に２４を超える。以下、説明の都合上引き続き３２ビット演算であると仮定する。Ｇの最小値が８．５である場合、格納されている値から底の値８を減算する場合がある。
【００８１】
図５に、指数近似に加えて補正表を用いて、引数の全範囲０〜２４にわたり関数ＦａおよびＦｓを実装する方法を示す。しかし、８〜１６の範囲にわたりＦａだけを近似する場合は、図６に示すように構成が簡単になる。
【００８２】
パイプライン
上で述べた各種の２表反復的方法を用いて、対数演算の実行に必要なメモリの量を減らすことができるが、所望の結果を得るために必要な複数回の反復の実行が、長時間を要することを理解されたい。対数演算処理の時間を短縮するため、従って速度を上げるために、本発明は、ある段階から後続段階へのフィードフォワードを有するハードウェアの新規な多段パイプラインを実装するＡＬＵを開示する。Ｆ（ｒ）関数用の参照表が各段階において連続的に大きくなるｒ値によりアドレス指定されるため、各段階における参照表は、先行段階で扱われた最大ｒ値と後続段階で扱われる最小ｒ値の間にあるアドレスの範囲だけを扱えばよい。実際に、単一の参照表Ｆ（ｒ）は、各々にパイプラインの各段階が関連付けられている、同時にアドレス指定可能な複数の副関数参照表に分解することができる。更に、ｒが増加するにつれてＦ（ｒ）の値が減少するため、各連続する表の語長を短縮することができる。チップに占める読み出し専用メモリ（ＲＯＭ）のシリコン領域はビット数、より具体的には格納されている２進の１、先行するゼロ（leading zeros）、および特定の構造を必要としない他のゼロの個数に比例するため、Ｆ（ｒ）表の分割により全体のシリコン領域を減らすことができる。
【００８３】
上述のように、対数ＡＬＵに関するあらゆる研究は実質的に、表のサイズを減らすことを関心対象としている。本明細書に開示する最適化は、この目的を達成するために重要な寄与をもたらす。本出願において、多段パイプラインは通常、実数の加算よび実数の減算の場合に各々収束させる必要に応じて３または４段階の反復を実装して、あるいは複素数演算での必要に応じてより多くの段階を実装しており、各段階について最適化されたハードウェアが直列接続されている。このようにした場合、後続のハードウェア段階が先行する計算の第２且つ後続する段階を扱うとき、新規の計算の第１段階を開始することができる。これにより、３〜４段階またはサイクル遅延毎に１回の算術演算から、単一段階遅延毎に１回の算術演算へ、スループットが向上する。
【００８４】
上は、対数加算の実行に３サイクルを用い、対数減算の実行に４サイクルを用いる２表反復的方法について述べたものである。本発明の新規なパイプラインによれば、各段階は１サイクルを実行する。各段階はＦおよびＧ表の完全な組を含んでいるが、以下に、Ｆ参照表から抽出するために用いた関数を、副関数参照表を定義する副関数に分解することにより、表のサイズを減らす（各段階は、対応する副関数参照表を有する）方法を記述する。
【００８５】
上述の３サイクル加算アルゴリズムにおいて、第１段階で用いるＦａ参照表用の引数ＸＭは、０〜２４の範囲にわたっていてよい。しかし、ＸＭ≧８ならば、２４を超える所望の終端値までＸを増やすには２段階で十分であるため、第１段階をスキップまたは迂回することができる。その場合、８より大きいＦａの引数と第２段階で最初に遭遇することにより、第１段階は、ＸＭ＜８である値を扱うことに限定され、従って最初の段階の参照表のサイズが減少する。
【００８６】
同様に、第２段階でＸＭ≧１６ならば、Ｘが第３段階の後だけでも２４を超える筈であるため、第２段階をスキップまたは迂回することができる。従って、初めて１６以上のＦａの引数に遭遇するのは第３段階においてであり、Ｆａに対する第２段階の引数は８≦ＸＭ＜１６の範囲に限られる。
【００８７】
第３段階におけるＦａに対する引数は従って、１６〜２４（１６≦ＸＭ＜２４）の範囲にある。ＸＭ＞２４の場合、Ｆａ＝０、すなわち、関数値を生成する必要は無い。ＸＭの引数の範囲が０〜９、９〜１８および＞１８に等しく分割することができる点を理解されたい。しかし、８、１６、および２４の境界を設定することは、分割を特に容易とする。ＸＭの２個の最上位ビットだけがこれらの境界を決定し、Ｆ表を２進小数点の左側３ビットによりアドレス指定するだけで済むためである。これにより、格納されたＧ−表値から底の値８が減算されても、これらの３ビットに影響を及ぼさないため、足し戻す必要がない理由が明らかになる。
【００８８】
図７に、本発明に基づく多段パイプラインを実行する、一つの例証的なＡＬＵ１００を示す。ＡＬＵ１００は、減算器１０２、複数のパイプライン段階、および１個以上の出力コンバイナ１１８、１２８、１３２を含んでいる。各段階は、分解された主参照表から導かれた副関数参照表１１２、１２２、１３０を含んでいる。このように、副関数参照表の組合せのサイズは主参照表のサイズに近い。減算器１０２は、２個の対数数値ＡおよびＢの減算を行なってＸを得る。ここにＡ＝ｌｏｇｑ（ａ）およびＢ＝ｌｏｇｑ（ｂ）である。更に、減算器１０２は、大きい方をコンバイナ１１８に出力し、また差の法を参照表１１０、１１２およびコンバイナ１１４に出力する。形式（５．８）でありながら２４未満の値である差（ＸＭ）の最上位ビットは、Ｆａ表１１２をアドレス指定する一方、最下位ビット（ＸＬ）はＧ表１１０をアドレス指定する。コンバイナ１１８は、本明細書で部分出力と称する形式（０．２４）のＦａ表の出力を、ＡとＢの大きい方と組み合わせる。Ｇ表の出力は、最大でも２４より僅かに小さい値（それ以上大きい値は計算を終了させてしまうため不要）であり、形式（５．２４）をなしている。コンバイナ１１４は、Ｇ表の出力をＸの先行値およびＦａ表１１２からの部分出力と組み合わせて、Ｘの次の値であるＸ’を得る。ＬＳＢ群ＸＬはＭＳＢ群より先に減算器１０２の外で安定しているため（Because the LSBs XL are stable out of subtracter 102 before the MSBs）、Ｇ表１１０の出力はＦａ表１１２の出力よりも先に有効になる。このように、Ｇ表１１０の出力は、図７に示すように、先にＸに加算することができる。この結果も、語長が５．２４より長い必要はなく、Ｆａ表１１２が提供する部分出力に加算される。Ｘ＞２４でアルゴリズムが収束することを、繰り返し示す必要がないよう、パイプラインの任意の段階でＸ値が２４を超えそうなことが検出されたならば、処理を終了して早い時点での結果を抽出できるようにすればよい。更に、ある段階に入力されたＸの値がＦａ表への最大アドレス値を超えた場合、ＦａおよびＧ表の出力値を強制的にゼロとすることにより、Ｘにも、ＡとＢの大きい方にも何も加算されることがないようにできる。変更されなかった値は、次のクロックサイクルで後続段階へ単に渡される。
【００８９】
コンバイナ１１６の出力は形式（５．２４）で２９ビットある。最上位１３ビット（５．８）が副関数表１２２をアドレス指定する。Ｆａ表１２２が部分Ｆａ表である理由は、この時点におけるＸＭの値が、上記のように常に８より大きいためである。要するに、第１段階の後では、ＸＭは常に８より大きい。その理由は、以下通りである。
・ＸＭの最小開始値は０より僅かに大きい。
・従ってＦａ表１２２からの値はほぼ１である。
・Ｇ表１２０からの最小値は−ｌｏｇ２（１−２−８）＝  ８．５３である。
従って、副関数表１２２に対する最小の引数は９．５である。従って、９．５と２４の間でＸＭの値を提供すれば済むため、大幅に少ないビット数で済む。しかし、８まで下げたＸＭを提供することにより、２個のＭＳビットだけに基づいて第１段階を迂回することをより簡単に決定することができる。コンバイナ１２８は、副関数表１２２からの部分出力を、これまでの結果と組み合わせる。
【００９０】
第２のＧ表１２０は、コンバイナ１１６の出力の第２４ＬＳＢを無視すれば、第１のＧ表１１０と同一であってよく、従って依然として１５ビットだけでアドレス指定される。一方、望むのであれば、第２段階のビット分割は、第１段階のものと同じである必要はない。例えば、Ｆ値の語長が短いために副関数表１２２がかなり小さい前提で、Ｘ’Ｍは１ビットだけ長く、Ｘ’Ｌは１ビット短くてもよい（あるいは、第２４ＬＳＢを用いてもよい）。第３段階のビット分割はまた、以下に詳述するように、別々に最適化することができる。
【００９１】
コンバイナ１２４は、形式５．２４をなすＧ表１２０の出力を２９ビットのＸ’値と組み合わせ、コンバイナ１２６は２９ビットの結果を副関数表１２２からの部分出力と組み合わせて、Ｘの次の値であるＸ”を得る。Ｘ”の最上位１３ビット（５．８）は、別の副関数表１３０をアドレス指定する。当該表１３０は、上述のようにこの時点におけるＸ”の値が常に１８（または１６）より大きいため、副関数表１２２よりも小さい。従って、Ｆａ値としては、第３段階では１バイト値しか無い。コンバイナ１３２は、最終のＦａ表１３０からの部分出力をコンバイナ１２８からの結果と組み合わせて、最終結果Ｃを生成し、次いでＳ８．２４からＳ８．２３へ切り捨てる。
【００９２】
いくつかの状況において、上で簡単に述べたように、パイプラインの１段階以上を迂回することができる。例えば、第１段階でＸ＞８ならば、第２段階へ値をフィードフォワードして、これらの値を処理に挿入することにより、第１段階を迂回することができる。これは、単にＸおよび部分出力にゼロを加えながら、次のクロックサイクルを待機することで実行でき、その結果、１段階先の計算を前方へ伝播することができる（the calculation that is ahead one stage can propagate forward）。同様に、第２段階でＸ’＞１６ならば、変更されていない値を第３段階へフィードフォワードすることにより、第２段階を迂回することができる。換言すれば、特定の段階の入力値が当該段階の参照表の範囲を超えた場合、図７の破線で示すように、変更されていない値をフィードフォワードすることにより、当該段階を迂回することができる。待機期間を省略することは、パイプラインが満杯でない場合のみ、あるいは１段階先の値が伝播するのを待機する等、衝突を避けるべく他の手段が取られた場合のみ、可能である。従って、パイプラインが満杯である場合、この迂回方法には必ずしも速度の利点がない。８を超える値がＦａ表１２２の先へ押しやられるため、初期Ｆａ表１１２は従って、Ｘ＝０〜８の範囲に限られる。実際、Ｆａ表１１２は、Ｆａ表１２２とＦａ表１３０のサイズ分だけ減らされて、パイプライン化された対数加算用のＦａ表のサイズの和は、非パイプライン化反復用に使用する主Ｆａ表のサイズと実質的に同一である。時分割するのに十分速くないとの仮定に基づき（assuming it is not fast enough to time-share）、Ｇ表だけが全体的に複製される。
【００９３】
「迂回」または「前進」アルゴリズムを実行するのに異なる方法がある。電力消費を増やす恐れのある過度の調整リップル（settling ripple）を避けるべく、ある段階からの後続段階へのビット遷移の再同期（リタイミング）を行なうことが高速ロジック上、望ましい。パイプライン・アルゴリズムには、第１および第２段階の間、および／または第２および第３段階の間でのフリップフロップの再同期を含んでいてよい。ＬＳＢの再同期がＭＳＢの再同期より早く生じ得る点に、また、一般に、ワードのビットは、リップル−桁上げ遅延（ripple-carry delay）に合致すべく、意図的にスタガー遅延されたクロックにより（with a deliberately stagger-delayed）再同期できる点に、注意されたい。パイプラインの順序を乱すことを避けるために、常に値が、３つの再同期された段階を介して伝播するように構成することができる。ただし、いずれかの段階でのＸ値がこれに関連付けられた副関数表が扱う値より大きい場合には、「無操作」を実行して、適当な再同期の後で、実質的に変更されていないＸ値および部分出力が後続段階へ渡される。８の底がＧ表の項目から減算されている場合に、ある段階が迂回されたならば、Ｘから値８を減算することができる。これはまた、Ｆ表の引数が特定の段階のＦ表の範囲外にある場合に、ＦおよびＧ表がゼロ値を出力するように構成することにより、実現することができる。このように、異なる副関数Ｆ表により扱われるＸ範囲に重なりが全くあるいはほとんど必要とされないため、Ｆ表に必要とされるビットの総数は、非パイプライン化アルゴリズムで使用する主Ｆ表に必要とされるビットの総数を超えない。いくつかの実施形態において、最終段階のＦ表は、補正なしで指数近似値だけを用いることができる。
【００９４】
対数減算は、異なる関数Ｆｓを用いる以外は上述の対数加算と実質的に同一であり、通常は収束のために加算よりもう１回の反復を行なう。図８に、対数減算アルゴリズムに関連付けられたパイプラインを実行する、一つの例証的なＡＬＵ２００を示す。減算器２０２は２個の対数値ＡおよびＢの減算を行なう。入力値は共に同符号を有するものと仮定され、そうでない場合はそれらの減算は代わりに対数加算アルゴリズムの使用が必要となるであろう。入力減算器２０２は、大きい方の対数絶対値により入力値を決定して、結果の符号を決定する。該符号は、Ｂの対数絶対値が大きい場合は入力符号と逆であり、Ａの対数絶対値が大きい場合は、入力符号と同一である。結果の符号は３２ビット出力のＭＳＢであり、出力までのコンバイナの連鎖２１８、２３８、２４８、２５２による影響を受けないままである。
【００９５】
差分ＭＳＢ群ＸＭがゼロならば、ＦＳ（Ｘ）の値は直接Ｇ（ＸＬ）により与えられて、パイプラインを早く終了することができる。従って、第１段階のＦｓ表２１２が扱わなければならないＸＭの最小値は０００００．０００００００１である。ただし、そのアドレスに対して格納される値は、−ｌｏｇ２（１−２−０．０００００００１１．．．．１）である。これをコンバイナ２１６のＧ表値（にコンバイナ２１４からのＸの前の値を加えたもの）から減算して、常に正の結果Ｘ’を得る。これはＸの先の値よりも、少なくとも以下の値だけ大きい。
【数３０】
2008502036.tif 000034
この結果を得るには、Ｘは０．００００００００１１１１１１１１１１１１１１１でなければならず、Ｘ’は少なくとも１．００１９７７となる。従って、ＦＳ表２３２は、原理的に全範囲を扱わねばならないＦＳ表２１２に比べて、１〜２４の範囲の引数だけを扱えばよい。しかし、パイプライン化された対数加算について上で述べた迂回原理を実装することにより、Ｘの初期値が１以上ならば、パイプラインの第１段階を迂回してＸを最初にＦＳ表２３２へ渡すことができる。従って、ＦＳ表２１２は０≦Ｘ＜１の範囲だけを扱えばよい。
【００９６】
パイプラインにおけるＸ値が１を超えたならば、各々の連続するＸ値は対数加算アルゴリズムとほぼ同程度（８．５）増加し、連続するＦｓ表は、語長が短くなって、各段階で処理されるＸの範囲に対応する値の個数のみ格納する。従って、いずれにせよ、迂回方法を利用することにより、Ｇ表を対数減算用に３倍に、対数加算用に２倍にする必要があるものの、パイプライン化されたアルゴリズム用の全ての副関数Ｆｓ表のサイズの和が、非パイプライン化システムで使用される主関数Ｆ表のサイズと同一となり得ることがわかる。対数加算および対数減算の両パイプライン化アルゴリズムにおいて、最終段階用の副関数参照表は、反復回数が打ち切られる前提のもとで結果の精度を向上させるべく、非増加ＸＭ値用の関数の値を保持することができる。
【００９７】
対数減算アルゴリズムにおいて、上述のように１段階以上が迂回されない限り、本明細書で部分出力と呼ぶ連続するＦＳ表出力は、減算器の連鎖２１８、２２８、２３８、２５２においてＡとＢの大きい方から減算される。ＦＳ表の出力は、所望の精度よりも少なくとも１個追加されるＬＳＢを含んでいてよく、そのため、全てが同じ方向に１／２ＬＳＢ分丸められている４個のＦＳ値が組み合わされた場合、全体の丸めは所望の精度よりＬＳＢ１個分を下回る。中間コンバイナ２１８、２２８および２３８はこの語長拡張により動作する一方、コンバイナ２５２は、所望の３１ビット正符号へ適切に丸めることにより、結果を切り捨てる場合がある。
【００９８】
上述のように、対数加算および対数減算パイプライン用のＦ表のサイズは、Ｆ関数の引数の予想される範囲に基づいて、パイプラインの異なる段階毎に変動する場合がある。しかし、関数および／または補正表のサイズは、段階入力に適用されるビット分割に基づいて更に最適化できる点も理解されたい。換言すれば、ビット分割を１段階以上について最適化して、格納された表のサイズを最適化することができる。例えば、ＸＭとＸＬ間の例証的なビット分割（５．８；１５）の場合、第２段階のＦａ関数は約２．３キロバイトの参照表しか必要としないが、Ｇ関数は約１３０．１ｋバイトを必要とし、合計で第２段階では１３２．４ｋに及ぶメモリ容量となる。しかし、下表に示すように、ＸＭにより多く、ＸＬにより少なくビットを割り当てるような、異なるビット分割により、第２段階に必要とされるメモリの総量を最小化することができる。
【００９９】
【表３】
2008502036.tif 000035
【０１００】
上の表は、第２段階における関数と補正表の最小の組み合わせサイズがビット分割（５．１１；１２）で生じることを示している。実際のメモリチップ領域は、関数表の最も長い語（１７ビット）より短い値および補正表の８ビットより短い値について先行するゼロを省略することにより、更に小さくできる。表のサイズを減らす他の手段を用いて、更なる削減を行なってもよい。
【０１０１】
０〜８の間のＸＭの場合、指数近似を用いるよりも、Ｆａ用の直接参照表を使用する方がより効率的であろう。加算用に格納される値は、１．０より小さく、０．２４形式で、小数点以下２４ビットの精度に格納することができる。従って、Ｆａの引数範囲０≦ＸＭ＜８の関数の第１段階の事例は、第２段階と同様に最適化することができる。この場合、直接参照表がＦａ関数を実装し、全ての語長が３バイトであると仮定される。従って、第１段階の場合、最適分割は下表に示すように（５．１０；１３）である。
【０１０２】
【表４】
2008502036.tif 000036
【０１０３】
加算アルゴリズムの最終段階（第３段階）の場合、次のＸＭ値が必要ないため、Ｇ関数を計算する必要がない。更に、引数の範囲１６≦ＸＭ＜２４の場合、指数近似だけで十分であり、Ｘの最上位ビットだけが必要である。例えば、形式５．８を用いることができ、２５６バイトの指数表で十分である。
【０１０４】
各段階について最小合計を選択すれば、３段パイプライン用に必要とされる表参照の総量は、第１段階の分割（５．１０；１３）、第２段階の分割（５．１１；１２）、および第３段階の分割（５．８）について、５７，３４４＋３４，８１６＋２５６＝９２，４１６バイトである。これはチップ領域だけを近似的に示すものである。ＲＯＭ構造の仕様により、トランジスタが存在すれば「１」、トランジスタが存在しなければ「０」を表わすならば、多くの値が必ずしもチップ域を占有しない数個の先行するゼロを有することが指摘されるためである。
【０１０５】
また、最終段階ではＸの先頭８個のバイナリの箇所（the first 8 binary places）のみが必要であるため、第２段階における前のＧ関数用の小数点以下の２４個の箇所が不要である点も理解されたい。第２段階のＧ表のサイズは従って半分になり、第２段階に対して以下のようにサイズにトレードオフが生じた表が得られる。
【０１０６】
【表５】
2008502036.tif 000037
【０１０７】
パイプライン化された対数減算アルゴリズムのためのＸＭおよびＸＬへのビット分割もまた、各段階におけるＦＳおよびＧ表の合計サイズを最小化すべく、パイプラインの１段階以上で異なっていてよい。減算器パイプライン２００の第１段階ＦＳ表２１２は、０〜１のＸＭの値だけを扱えばよく、従って２進小数点の左側がゼロである。ＦＳ関数の値は当該引数範囲の場合、最大長さ２９ビット（５．２４）とすることができ、これが４バイトまで切り上げられる。この結果、以下のトレードオフ表が得られる。
【０１０８】
【表６】
2008502036.tif 000038
【０１０９】
ＸＭとＸＬの間のビット分割（１２:１１）を選択することにより、合計メモリが最小化され、平均して、パイプラインの第２段階に１１：１２の分割に比べより大きいＸ’の値が入ることが保証される。
【０１１０】
減算器パイプライン２００の第２段階ＦＳ表２３２は、１より大きく８より小さい形式３．２３のＸ’を取扱う。第２段階が最大９までの値を扱えるようにして、２アドレス空間が全面的に使用できるようになれば便利であろう。第１段階から渡されるＸ’の値を１減算して、ＦＳ表２３２に対して０〜８の間、すなわち２進小数点の３ビット左のアドレスを提示することができる。ＦＳ関数の値は１より小さいため、小数点の右側に２４ビットすなわち３バイトしか有していない。この結果、以下のトレードオフ表が得られる。
【０１１１】
【表７】
2008502036.tif 000039
【０１１２】
従って、（３．１１：１２）分割が、第２のパイプライン段階にとり好適な選択である。
【０１１３】
第２のパイプライン段階からのＸ”の値は１１より大きくなるが、第３のパイプライン段階もまた、第２段階を迂回する９より大きい値を扱わなければならない。このように、第３段階の副関数表は、９より大きく１７より小さいＸ”の値を扱わなければならない。ＦＳ関数の値はこの場合、２バイトよりも短い。更に、最終段階においてＸ”の最上位部分だけがＦＳ表をアドレス指定するために必要となるので、Ｇ関数は２バイトの精度で格納できれば十分である。第３段階のＦＳ表へのアドレスは９を減算することにより再び９減らされて０〜８の範囲となる。すなわち、アドレスは小数点の左側に３ビットを有し、その結果、以下のトレードオフ表が得られる。
【０１１４】
【表８】
2008502036.tif 000040
【０１１５】
上の表から、第３段階の最適分割は（３．１０：１３）であることが明らかである。
【０１１６】
最終段階におけるＦＳ表は、１７より大きく最大２５までの、Ｘの可能な残りの値を扱う。関数の値は、当該引数範囲で自身の表現用に８個のＬＳＢだけが必要であるため、最終段階のＦＳ表は２〜４キロバイトのオーダーであればよい。４段パイプライン対数減算アルゴリズムに対する合計参照表の要件を合算すれば、１１８，６８８バイト、すなわち約１２ＯｋＢを得るが、これは典型的な最新のデジタル集積回路チップのシリコン領域の１０％未満である。
【０１１７】
ビット分割の最適化によりＦおよびＧ表のサイズが最適化されるが、ビット分割の最適化はまた、完全な実数バタフライ演算を実行すべく、対数加算および対数減算がパイプライン化方法において別々に実装されている場合に有用である。これにより、僅かに異なる語長を含んでいてパイプライン化にもう１段階必要な対数減算を、別個に最適化することができる。
【０１１８】
同じ値の組の加算と減算を必要としない場合であっても、別々の対数加算および対数減算装置を有していることにより、加算される値の組と減算される値の組との別々の待ち行列を同時に処理することが可能になる。これはランダムなデータで、各々全体の時間の５０％生起し、従って処理速度が２倍になるものと期待される。パイプライン化された方法を実装している場合、処理速度を最大化したいとの要望があるはずなので、対数加算および対数減算の並列実行は歓迎されるものと思われる。
【０１１９】
パイプライン化の目的はスループット速度を上げることである。この目的で、パイプラインを介した伝播遅延を減らす方法を見つけることは有用である。伝播遅延は、最下位ビットから最上位ビットまで潜在的に全経路を通る桁上げ伝播に十分な時間を与えることが必要なため、主にコンバイナにおいて起こる。このような遅延を減らすべく、先読み桁上げ生成（look-ahead carry generation）の各種の方式が知られている。
【０１２０】
図７に、コンバイナ１１４が、減算器１０２からの差分値をＧ表１１０の出力と組み合わせ、コンバイナ１１６が、コンバイナ１１４の出力をＦＳ表１１２の出力と組み合わせる様子を示す。しかし、単に値ＸＬ＋Ｇ（ＸＬ）をＧ表１１０に格納することにより、Ｘの最下位部分ＸＬをＧ（ＸＬ）の最下位部分に加算する必要をなくすことができる。同様に、コンバイナ１１４内でＸの最上位部分ＸＭをＧ表出力に加算するのではなく、ＸＭを同じくコンバイナ１１６で組み合わせてもよい。しかし、これは、単にＸＭ＋Ｆａ（ＸＭ）の値を副関数表１１２に格納することにより回避することができる。この状況において、副関数表１１２の出力はまたコンバイナ１１８でも用いられるため、減算器１０２から出力された「ＬＡＲＧＥＲ（Ａ，Ｂ）」の値を補正することにより、ＸＭの加算を補償する必要がある。この目的で、小さい方の値の最上位部分がコンバイナ１１８へ入力される。また、減算器１０２の最下位部分からの桁下げが、コンバイナ１１８へ桁上げ入力としてフィードフォワードされる。
【０１２１】
上の数学的表現は以下の通りである。（ＡＭ，ＡＬ）は各々Ａの最上位および最下位部分を表わすものとする。同様に（ＢＭ，ＢＬ）は各々Ｂの最上位および最下位部分を表わすものとする。更に、Ａ＞Ｂと仮定する。すると、その語長を法としてＸＬ＝ＡＬ−ＢＬであり、ＸＭ＝ＡＭ−ＢＭ−ｂである。ここに、ｂは演算ＡＬ−ＢＬからの桁下げビットを表わす。次に、第１段階からの出力および第２段階への入力は次式で表わされる。
Ｘ’＝Ｘ＋Ｆ（ＸＭ）＋Ｇ（ＸＬ）
＝（ＸＭ，ＸＬ）＋Ｆ（ＸＭ）＋Ｇ（ＸＬ）
＝[ＸＭ＋Ｆ（ＸＭ）]＋[ＸＬ＋Ｇ（ＸＬ）]          （３３）
＝Ｆ＃（ＸＭ）＋Ｇ＃（ＸＬ）
ここに、関数Ｆ＃およびＧ＃は、各々既に組み込まれたＸＭおよびＸＬの加算を有する（the addition of XM and XL, respectively, already built in）。Ｘ”も同様にＸ’から計算することができ、以下同様である。このように、パイプライン段階毎に１個の組み合せが除去された。対数加算処理の所望の結果は次式で得られる。
Ａ＋Ｆａ（Ｘ）＋Ｆａ（Ｘ’）＋Ｆａ（Ｘ”）＝（ＡＭ，ＡＬ）＋Ｆ＃（ＸＭ）＋Ｆ＃（Ｘ’Ｍ）＋Ｆ＃（Ｘ”Ｍ）−（ＸＭ＋Ｘ’Ｍ＋Ｘ” Ｍ）
（３４）
ＢＭ＋ｂをＡＭ−ＸＭで置換すれば、上式はまた次式のように書くことができる。
Ａ＋Ｆａ（Ｘ）＋Ｆａ（Ｘ’）＋Ｆａ（Ｘ”）＝（ＢＭ＋ｂ，ＡＬ）＋Ｆ＃（ＸＭ）＋Ｆ＃（Ｘ’Ｍ）＋Ｆ＃（Ｘ”Ｍ）−（Ｘ’Ｍ＋Ｘ” Ｍ）
（３５）
Ｘ’’’が必要でないため、パイプラインの最終段階にＦ＃関数を用いる必要がない。従って、最終段階は、余分のＸＭ”を組み込むことなく、上述の正規のＦａ関数を使用し、その結果、次式を得る。
Ａ＋Ｆａ（Ｘ）＋Ｆａ（Ｘ’）＋Ｆａ（Ｘ”）＝（ＢＭ＋ｂ，ＡＬ）＋Ｆ＃（ＸＭ）＋Ｆ＃（Ｘ’Ｍ）＋Ｆａ（Ｘ” Ｍ）−Ｘ’Ｍ
（３６）
ここに、（Ｘ’Ｍ，Ｘ’Ｌ）＝Ｘ’＝Ｆ＃（ＸＭ）＋Ｇ＃（ＸＬ）且つ（Ｘ”Ｍ，Ｘ”Ｌ）＝Ｘ”＝Ｆ＃（Ｘ’Ｍ）＋Ｇ＃（Ｘ’Ｌ）である。更に、上で指摘したように、Ｘ”Ｌを計算する必要がないため、第２のＧ表は、Ｇ値で最上位部分だけを含んでいればよい。しかし、第２段階の副関数参照表は、対数加算処理の結果に寄与するため、Ｆａ値の最下位（ＬＳ）部分を含んでいなければならない。
【０１２２】
図９に、上の構成を実行する、一つの例証的なＡＬＵ３００を示す。ここで減算器１０２は、最上位部分パート減算器３０２および最下位部分減算器３０４に分割されている。差分出力ＸＭ、ＸＬは、図７の減算器１０２からの出力と同じである。すなわち、Ａが大きい方の対数絶対値ならばＡ−Ｂ、さもなければＢ−Ａである。また、大きい方であると判定されたＡまたはＢの最下位部分がＬＬとして出力され、これも図７の減算器１０２の場合と同じである。しかし、減算器３０２の最上位部分から出力された値Ｓｍ（the value Sm output from the most significant part of subtracter 302）は、ここではＡとＢの小さい方の最上位部分であり、これはコンバイナ３２８への部分出力Ｆ＃（ＸＭ）にＸＭを余分に加算したことに起因して、大きい方の最上位部分に有効に補正される。また、Ａが大きい方であるときにＡＬ−ＢＬが桁下げを生じるか、Ｂが大きい方であるときにＢＬ−ＡＬが桁下げを生じる場合に、Ｓｍは１だけ増やされる。１だけ増やすことは、必要なときに、コンバイナ３２８の桁上げ入力に１を加えることにより実現することができる。
【０１２３】
Ｆ＃表３２０は、自身の最上位ビットに予め加算されたＦ＃関数の値を、表の引数／アドレスＸＭと共に格納し、Ｇ＃表３２２も同様に、自身の最下位ビットに予め加算されたＧ＃関数の値を、自身の引数／アドレスＸＬと共に格納する。このようにＸ’の値は、Ｆ＃およびＧ＃表がその値をＧおよびＦと既に組み合わせているため、単に１個のコンバイナＦ＃（ＸＭ）＋Ｇ＃（ＸＬ）により計算可能である。コンバイナ３２４、３２６は必須の加算を実行してＸ’を生成する。このようにして、１個のコンバイナの伝播遅延、シリコン領域、および電力消費が除去される。
【０１２４】
この処理は、第２段階まで続く。ここに、Ｘ’は第２段階への入力を表わす。Ｆ＃３３０およびＧ＃表３３２は各々、Ｘ’ＭおよびＸ’Ｌに基づく新たな関数および補正値を提供する。コンバイナ３３４は、関数および補正出力値の最上位ビットを組み合わせて、Ｘ”を生成する。コンバイナ３３８は、部分出力Ｆ＃（Ｘ’Ｌ）の最下位ビットをコンバイナ３２９の出力と組み合わせて、最下位出力ビットの新たな推定値を生成し、一方、コンバイナ３３６は、部分出力Ｆ＃（Ｘ’Ｍ）の最上位ビットをコンバイナ３２８の出力と組み合わせて、最上位出力ビットの新たな推定値を生成する。
【０１２５】
最後に、第３段階において、Ｘ”がＦ表３４０へ入力されて、Ｘ”に基づいて関数値の最上位および最下位ビットを生成する。コンバイナ３４２は、部分出力Ｆ（Ｘ”Ｍ）の最上位ビットをコンバイナ３３６の出力と組み合わせて、最上位出力ビットの最終的な推定値を生成する。同様に、コンバイナ３４４は、部分出力Ｆ＃（Ｘ”Ｌ）の最下位ビットをコンバイナ３３８の出力と組み合わせて、最下位出力ビットの最終的な推定値を生成する。
【０１２６】
パイプライン化された複素数アルゴリズムは、ビット分割に応じて収束により多くの段階を必要とする場合があるものの、実数の対数加算／減算アルゴリズムと同じ仕方で構築することができる。ただし、実数のアルゴリズムと同様に、任意の段階におけるＦの引数のｌｏｇｑ（Ｒ）部分が自身のアドレス範囲を超えた場合、当該段階を迂回する場合がある。従って、部分的な複素数Ｆ表のサイズの和は、非パイプライン化アルゴリズムでの同表の総サイズに保たれる（keeping the sum of the sizes of the partial complex F-tables to the same total size as in the unpipilined algorithm）。
【０１２７】
本発明が本明細書に明示していないメモリ圧縮技術と共に利用できることを理解されたい。例えば、米国仮特許出願第６０／５７７，３８６号に記載のメモリ圧縮技術および／または米国特許出願第＿＿＿＿＿号（代理人整理番号４０１５−５２８８）に記載のメモリ圧縮技術を本出願の発明と合わせて用いてもよい。
【０１２８】
本発明は無論、本発明の基本的特徴から逸脱することなく、本明細書に具体的に開示した方法とは別の仕方で実施することができる。本実施形態はあらゆる点で説明目的であって限定的ではなく、添付の特許請求の範囲の意味および均等の範囲内で生じる変更がすべて本発明に包含されることを理解されたい。
【図面の簡単な説明】
【０１２９】
図面の簡単な説明
【図１】ＩＥＥＥ浮動小数点形式と、実数用の真の対数形式を比較したプロット図を示す。
【図２】ＩＥＥＥ浮動小数点形式と、実数用の真の対数形式を比較したチャートを示す。
【図３】線形補間器のブロック図を示す。
【図４】真のＦ関数と、指数近似を比較したプロット図を示す。
【図５】Ｆ表構築システムのブロック図を示す。
【図６】簡素化されたＦ表構築システムのブロック図を示す。
【図７】本発明による対数加算多段パイプラインの一つの例証的なブロック図を示す。
【図８】本発明による対数減算多段パイプラインの一つの例証的なブロック図を示す。
【図９】本発明による変形された対数加算多段パイプラインの一つの例証的なブロック図を示す。
【図１】
2008502036.tif 000041
【図２】
2008502036.tif 000042
【図３】
2008502036.tif 000043
【図４】
2008502036.tif 000044
【図５】
2008502036.tif 000045
【図６】
2008502036.tif 000046
【図７】
2008502036.tif 000047
【図８】
2008502036.tif 000048
【図９】
2008502036.tif 000049
【手続補正書】
【提出日】平成18年7月18日(2006.7.18)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
多段パイプラインにおける第１および第２のオペランドに基づいて対数計算を実行する方法であって、
主参照表に関連付けられた主参照関数を２個以上の副関数に分解するステップと、
各々の副関数に対して副関数参照表をメモリに格納するステップであって、各々の副関数参照表が前記主参照表の異なる部分を含んでいる、ステップと、
前記多段パイプラインの各段階において少なくとも１個の副関数参照表を使用して段階入力に基づいて段階出力を得るステップと、
各段階出力を組み合わせて対数出力を生成するステップとを含む方法。
【請求項２】
各段階入力が、対応する前記副関数参照表をアドレス指定する、請求項１に記載の方法。
【請求項３】
前記段階入力が、ＭＳ部およびＬＳ部を含んでいて、前記段階入力のＭＳ部が前記副関数参照表をアドレス指定する、請求項１に記載の方法。
【請求項４】
前記第２オペランドから前記第１オペランドを減算して前記多段パイプラインの第１段階用に段階入力を生成するステップを更に含む、請求項３に記載の方法。
【請求項５】
先行段階からの段階入力および段階出力に補正値を累算することにより、後続段階への段階入力を生成するステップを更に含む、請求項４に記載の方法。
【請求項６】
前記メモリに格納された補正表を前記段階入力のＬＳ部によりアドレス指定して前記補正値を生成するステップを更に含む、請求項５に記載の方法。
【請求項７】
前記対数計算の実行が、第１および第２の値の和または差の対数を決定するステップを含んでいて、前記第１オペランドが前記第１値の対数を表わし、前記第２オペランドが前記第２値の対数を表わす、請求項１に記載の方法。
【請求項８】
前記段階出力を組み合わせて対数出力を生成するステップが、前記段階出力を前記第１および第２オペランドのうち一方と組み合わせて対数出力を生成するステップを含む、請求項７に記載の方法。
【請求項９】
前記第１オペランドをＭＳおよびＬＳ部に分割するステップと、
前記第２オペランドをＭＳおよびＬＳ部に分割するステップと、
前記第１および第２オペランドのＬＳ部を減算して前記パイプラインの第１段階用の段階入力のＬＳ部を生成するステップと、
前記第１および第２オペランドのＭＳ部を減算して前記パイプラインの第１段階用の段階入力のＭＳ部を生成するステップとを更に含む、請求項１に記載の方法。
【請求項１０】
前記第１および第２オペランドのＬＳ部を減算するステップが更に桁下げ部を生成し、前記第１および第２オペランドのＭＳ部を減算するステップが前記桁下げ部を考慮している、請求項９に記載の方法。
【請求項１１】
先行段階からの段階出力のＬＳ部にＬＳ補正値を累算することにより、後続段階への段階入力のＬＳ部を生成するステップと、
先行段階からの段階出力のＭＳ部にＭＳ補正値を累算することにより、後続段階への段階入力のＭＳ部を生成するステップとを更に含む、請求項９に記載の方法。
【請求項１２】
先行段階から段階出力のＬＳ部にＬＳ補正値を累算するステップが更に桁上げ部を生成し、後続段階への段階入力のＭＳ部を生成するステップが、前記桁上げ部に先行段階からの段階出力のＭＳ部および前記ＭＳ補正値を累算するステップを含む、請求項１１に記載の方法。
【請求項１３】
変更された補正表を前記段階入力のＬＳ部でアドレス指定して前記ＭＳ補正値およびＬＳ補正値を生成するステップを更に含む、請求項１１に記載の方法。
【請求項１４】
各々の副関数を実行するステップが、対応する副関数参照表または変更された副関数参照表を前記段階入力のＭＳ部でアドレス指定して前記段階出力のＭＳ部および前記段階出力のＬＳ部を生成するステップを含む、請求項１１に記載の方法。
【請求項１５】
前記段階出力を組み合わせて対数出力を生成するステップが、
段階出力のＬＳ部を前記第２オペランドのＬＳ部と組み合わせて前記出力のＬＳ部を生成するステップと、
段階出力のＭＳ部を前記第１オペランドのＭＳ部と組み合わせて前記出力のＭＳ部を生成するステップと、
前記出力のＭＳおよびＬＳ部を結合して対数出力を生成するステップとを含む、請求項１４に記載の方法。
【請求項１６】
前記段階出力を組み合わせるステップが、前記第１オペランドのＭＳ部を前記桁下げ部を考慮している少なくとも１個の段階出力のＭＳ部と組み合わせるステップを含む、請求項１５に記載の方法。
【請求項１７】
前記段階出力のＬＳ部を前記第２オペランドのＬＳ部と組み合わせるステップが更に桁上げ部を生成し、前記段階出力のＭＳ部を前記第１オペランドのＭＳ部と組み合わせるステップが、前記段階出力のＭＳ部を前記桁上げ部と組み合わせるステップを含む、請求項１５に記載の方法。
【請求項１８】
前記段階入力が所定の値を超えた場合に段階を迂回するステップを更に含む、請求項１に記載の方法。
【請求項１９】
段階を迂回するステップが、迂回された段階についてゼロに等しい段階出力を生成し、前記迂回された段階への段階入力を後続段階の段階入力として用いるステップを含む、請求項１８に記載の方法。
【請求項２０】
各段への段階入力をＭＳおよびＬＳ部に分割するステップを更に含む、請求項１に記載の方法。
【請求項２１】
前記段階入力のＭＳおよびＬＳ部が、異なる段階において異なるサイズを有している、請求項２０に記載の方法。
【請求項２２】
少なくとも１個の副関数参照表のサイズが、段階入力値の予想範囲に基づいている、請求項１に記載の方法。
【請求項２３】
前記格納された参照表は、語長が少なくとも２個の連続する段階で減少する、請求項１に記載の方法。
【請求項２４】
１個以上の副関数参照表が異なるサイズを有している、請求項１に記載の方法。
【請求項２５】
各段階からの前記副関数参照表をまとめると前記主参照表に等しい、請求項１に記載の方法。
【請求項２６】
第１および第２のオペランドに基づいて対数計算を実行する対数ＡＬＵであって、
パイプラインの各々の段階が、主関数を分解した各副関数を実行して段階出力を生成する多段パイプラインと、
各々の副関数に対する副関数参照表を格納するメモリであって、各々の副関数参照表が前記主関数に関連する前記主参照表の異なる部分を含んでいる、メモリと、
前記パイプラインの各段階により生成された段階出力に基づいて対数出力を生成する少なくとも１個のコンバイナとを含むＡＬＵ。
【請求項２７】
各段階入力が、対応する副関数参照表をアドレス指定する、請求項２６に記載の対数ＡＬＵ。
【請求項２８】
各段階入力が、ＭＳ部およびＬＳ部を含んでいて、各段階入力のＭＳ部が前記対応副関数参照表をアドレス指定する、請求項２７に記載の対数ＡＬＵ。
【請求項２９】
前記第２オペランドから第１オペランドを減算して前記第１段階への段階入力を生成する減算器を更に含む、請求項２８に記載の対数ＡＬＵ。
【請求項３０】
前記多段パイプラインの少なくとも１個の段階が、先行段階からの段階入力および段階出力を先行段階からの補正値と組み合わせて後続段階への段階入力を生成する段階コンバイナを含む、請求項２９に記載の対数ＡＬＵ。
【請求項３１】
前記メモリが更に補正表を格納し、前記段階入力のＬＳ部が前記補正表をアドレス指定して対応する段階の補正値を生成する、請求項３０記載の対数ＡＬＵ。
【請求項３２】
前記ＡＬＵが、第１および第２の値の和または差の対数を決定することにより対数計算を実行し、前記第１オペランドが前記第１値の対数を表わし、前記第２オペランドが前記第２値の対数を表わす、請求項２６に記載の対数ＡＬＵ。
【請求項３３】
前記出力コンバイナが、前記第２オペランドに前記段階出力を累算して対数出力を生成する２個以上のアキュムレータを含む、請求項３２に記載の対数ＡＬＵ。
【請求項３４】
前記第１および第２オペランドのＬＳ部を減算して前記第１段階への段階入力のＬＳ部を生成し、前記第１および第２オペランドのＭＳ部を減算して前記第１段階への段階入力のＭＳ部を生成する減算器を更に含む、請求項２６に記載の対数ＡＬＵ。
【請求項３５】
前記減算器が更に、前記第１および第２オペランドのＬＳ部の減算に基づいて桁下げ部を生成し、前記減算器が更に、前記第１および第２オペランドのＭＳ部を減算して前記第１段階への段階入力のＭＳ部を生成する際に前記桁下げ部を考慮に入れる、請求項３４に記載の対数ＡＬＵ。
【請求項３６】
前記多段パイプラインの少なくとも１段階が、
先行段階からの段階出力のＬＳ部にＬＳ補正値を累算して後続段階への段階入力のＬＳ部を生成するＬＳ段階コンバイナと、
先行段階からの段階出力のＭＳ部にＭＳ補正値を累算して後続段階への段階入力のＭＳ部を生成するＭＳ段階コンバイナとを含む、請求項３５に記載の対数ＡＬＵ。
【請求項３７】
前記ＬＳ段階コンバイナが更に、先行段階からの段階出力のＬＳ部へのＬＳ補正値の累算に基づいて桁上げ部を生成し、前記ＭＳ段階コンバイナが前記桁上げ部に先行段階からの段階出力のＭＳ部および前記ＭＳ補正値を累算して後続段階入力のＭＳ部を生成する、請求項３６に記載の対数ＡＬＵ。
【請求項３８】
前記メモリが更に、前記パイプラインの少なくとも１段階用に、変更された補正表を格納し、前記段階入力のＬＳ部が前記補正表をアドレス指定して前記補正値を生成する、請求項３７に記載の対数ＡＬＵ。
【請求項３９】
前記メモリに格納された少なくとも１個の副関数参照表が、変更された副関数参照表を含む、請求項３７に記載の対数ＡＬＵ。
【請求項４０】
前記段階入力のＭＳ部が、前記副関数参照表または変更された副関数参照表をアドレス指定して、前記段階出力のＭＳ部および前記段階出力のＬＳ部を生成する、請求項３９に記載の対数ＡＬＵ。
【請求項４１】
少なくとも１個の出力コンバイナが、
前記段階出力のＬＳ部を前記第２オペランドのＬＳ部と組み合わせて前記対数出力のＬＳ部を生成するＬＳコンバイナと、
前記段階出力のＭＳ部を前記第１オペランドのＭＳ部と組み合わせて前記対数出力のＭＳ部を生成するＭＳコンバイナとを含む、請求項４０に記載の対数ＡＬＵ。
【請求項４２】
前記ＭＳコンバイナが、前記桁下げ部を考慮に入れながら、前記第１オペランドのＭＳ部を段階出力のＭＳ部と組み合わせる、請求項４１に記載の対数ＡＬＵ。
【請求項４３】
前記ＬＳコンバイナが更に、前記段階出力のＬＳ部と前記対数出力のＬＳ部の組合せに基づいて桁上げ部を生成し、ＭＳコンバイナが更に、前記段階出力のＭＳ部を前記第１オペランドのＭＳ部および前記桁上げ部と組み合わせて前記対数出力のＭＳ部を生成すべく構成されている、請求項４１に記載の対数ＡＬＵ。
【請求項４４】
各々の副関数参照表の語長が、少なくとも２個の連続する段階で減少する、請求項２６に記載の対数ＡＬＵ。
【請求項４５】
前記段階入力がＭＳ部およびＬＳ部を含んでいて、前記ＭＳおよびＬＳ部が異なる段階において異なるサイズを有し得る、請求項２６に記載の対数ＡＬＵ。
【請求項４６】
少なくとも１個の副関数参照表のサイズが、予想される段階入力値の範囲に基づいている、請求項２６に記載の対数ＡＬＵ。
【請求項４７】
１個以上の副関数参照表が異なるサイズを有している、請求項２６に記載の対数ＡＬＵ。
【請求項４８】
各段階からの前記副関数参照表をまとめると前記主参照表に等しい、請求項２６に記載の対数ＡＬＵ。
【請求項４９】
多段パイプラインにおいて対数計算を実行する方法であって、
前記多段パイプラインの各段階に対する副関数参照表を格納するステップであって、前記副関数参照表が主関数表の異なる部分を含んでいる、ステップと、
対応する副関数参照表および段階入力を用いて、少なくとも１段階に対する段階出力を計算するステップと、
各段階出力を組み合わせて対数出力を生成するステップとを含む方法。
【請求項５０】
各段階への段階入力をＭＳおよびＬＳ部に分割するステップを更に含む、請求項４９に記載の方法。
【請求項５１】
前記段階入力の前記ＭＳおよびＬＳ部が異なる段階において異なるサイズを有し得る、請求項５０に記載の方法。
【請求項５２】
前記段階入力が所定の値を超えた場合、段階を迂回するステップを更に含む、請求項４９に記載の方法。
【請求項５３】
少なくとも１個の副関数参照表のサイズが、予想される前記段階入力値の範囲に基づいている、請求項４９に記載の方法。
【請求項５４】
１個以上の副関数参照表が異なるサイズを有している、請求項４９に記載の方法。
【請求項５５】
対数形式の数に対して演算を実行するＡＬＵであって、対数関数に関連付けられた参照表を格納するメモリを含み、前記参照表が、アドレス範囲により少なくとも２個の同時にアドレス指定可能な副表に分割されていて、前記ＡＬＵが、前記副表のうち少なくとも１個をアドレス指定する入力に基づいて、前記参照表を使用して対数加算および対数減算処理のうち少なくとも一つを行なうＡＬＵ。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１０
【補正方法】変更
【補正の内容】
【００１０】
加算器を必要とすることなく合理的なサイズの参照表を維持しつつ、精度を向上させるための異なる技術が本願出願人による米国特許第５，９４４，７７４号で実数について記述されており、その内容は参照によりここに引用される。しかし、実数および複素数の両方とも無線通信装置等の一般的な用途で求まれるため、両方の処理能力を備えた方法と同様に、特に無線信号処理で有用な複素数演算用の方法および装置が求められている。本出願と並行して出願された米国特許出願第１１／１４２７６０号は、この問題に対処しており、その全文をここに参照におり引用する。更に、多段パイプラインを実装する方法および装置は、複素数および／または実数演算処理を実行しながらスループット速度を向上せせるのに役立つ。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００２６
【補正方法】変更
【補正の内容】
【００２６】
純粋対数形式の実数は、（Ｓ８．２３）と略記され、以下のように表わすことができる。
Ｓ  ｘｘｘｘｘｘｘｘ．ｘｘｘｘｘｘｘｘｘｘｘｘｘｘｘｘｘｘｘｘｘｘｘ
２個のこのような実数を、複素数を表わす一つの方法として用いることができる。しかし、関連する米国特許出願第１１／１４２７６０号に述べられているように、複素数を表わすのに対数極形式の方が有利である。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０１２７
【補正方法】変更
【補正の内容】
【０１２７】
本発明が本明細書に明示していないメモリ圧縮技術と共に利用できることを理解されたい。例えば、米国仮特許出願第６０／５７７，３８６号に記載のメモリ圧縮技術および／または米国特許出願第１１／１４３１５７号（代理人整理番号４０１５−５２８８）に記載のメモリ圧縮技術を本出願の発明と合わせて用いてもよい。
【国際調査報告】
2008502036.tif 000050
2008502036.tif 000051
2008502036.tif 000052
2008502036.tif 000053
2008502036.tif 000054