(57)【特許請求の範囲】
【請求項１】
複数の対数数を和分する方法であって、該方法は、
（ａ）複数の対数数の各々を対応する１つの対応値へ変換するステップと、 
（ｂ）前記対応値の各々を複数のカウンタの一つと関連付けるステップと、
（ｃ）対数数の発生ごとに、その対応値と関連づけられているカウンタを増分させるステップと、 
（ｄ）カウンタのカウント値が１を越えた場合、そのカウンタのカウント値をゼロにし、そのカウンタと関連付けられた対応値の倍の値と関連付けられた上位カウンタを増分させるステップと、
（ｅ）前記複数の対数数のすべてが発生終了すると、下位カウンタから上位カウンタに向かって、カウンタを和分するステップであって、下位カウンタ同士を結合し、更に、すべてのカウント値が単一の上位カウンタ内に収まるまでそれとも単一の上位カウンタ及び非ゼロカウント値を有する一つの下位カウンタ内に収まるまで、前記（ｄ）ステップを繰り返すステップと、
（ｆ）和分の合計が単一の上位カウンタ内に収まる場合、前記単一の上位カウンタのカウント値が表す値の対数数を計算するステップと、及び
（ｇ）和分の合計が単一の上位カウンタ及び非ゼロカウント値を有する一つの下位カウンタ内に収まる場合、前記単一の上位カウンタ及び前記１つの下位カウンタ内のカウント値を和分し、和分されたカウント値が表す値の対数数を計算するステップと、を含む方法。
【請求項２】
複数の対数数を和分する装置であって、該装置は、
複数の対数数の各々を対応する１つの対応値へ変換する手段と、 
前記対応値の各々を複数のカウンタの一つと関連付ける手段と、
対数数の発生ごとに、その対応値と関連づけられているカウンタを増分させる手段と、 
カウンタのカウント値が１を越えた場合、そのカウンタのカウント値をゼロにし、そのカウンタと関連付けられた対応値の倍の値と関連付けられた上位カウンタを増分させる手段と、
前記複数の対数数のすべてが発生終了すると、下位カウンタから上位カウンタに向かって、カウンタを和分する手段であって、すべてのカウント値が単一の上位カウンタ内に収まるまでそれとも単一の上位カウンタ及び非ゼロカウント値を有する一つの下位カウンタ内に収まるまで、下位カウンタ同士を結合し続ける手段と、
和分の合計が単一の上位カウンタ内に収まる場合、前記単一の上位カウンタのカウント値が表す値の対数数を計算する手段と、及び
和分の合計が単一の上位カウンタ及び非ゼロカウント値を有する一つの下位カウンタ内に収まる場合、前記単一の上位カウンタ及び前記１つの下位カウンタ内のカウント値を和分し、和分されたカウント値が表す値の対数数を計算する手段とを含む装置。
【請求項３】
コンピュータに、
（ａ）複数の対数数の各々を対応する１つの対応値へ変換するステップと、 
（ｂ）前記対応値の各々を複数のカウンタの一つと関連付けるステップと、
（ｃ）対数数の発生ごとに、その対応値と関連づけられているカウンタを増分させるステップと、 
（ｄ）カウンタのカウント値が１を越えた場合、そのカウンタのカウント値をゼロにし、そのカウンタと関連付けられた対応値の倍の値と関連付けられた上位カウンタを増分させるステップと、
（ｅ）前記複数の対数数のすべてが発生終了すると、下位カウンタから上位カウンタに向かって、カウンタを和分するステップであって、下位カウンタ同士をを結合し、更に、すべてのカウント値が単一の上位カウンタ内に収まるまでそれとも単一の上位カウンタ及び非ゼロカウント値を有する一つの下位カウンタ内に収まるまで、前記（ｄ）ステップを繰り返すステップと、
（ｆ）和分の合計が単一の上位カウンタ内に収まる場合、前記単一の上位カウンタのカウント値が表す値の対数数を計算するステップと、及び
（ｇ）和分の合計が単一の上位カウンタ及び非ゼロカウント値を有する一つの下位カウンタ内に収まる場合、前記単一の上位カウンタ及び前記１つの下位カウンタ内のカウント値を和分し、和分されたカウント値が表す値の対数数を計算するステップとを実行させ、複数の対数数を和分させるためのプログラム。

【発明の詳細な説明】
【０００１】
（発明の分野） 本発明は対数値として表現された数の計算を実施する装置および方法に関し特に符号付き対数値として表現された数の計算を実施する装置および方法に関する。
【０００２】
（発明の背景） コンピュータやデジタル信号処理装置のような数値処理装置は一般的に量の固定小数点すなわち線形表現もしくは浮動小数点表現を使用する。浮動小数点表現では、量は３つの部分、符号、指数部および仮数部で表わすことができる。
【０００３】
符号ビットは表わされる量が正か負かを示す。仮数部はその符号を取り去った量の大きさを表わすことができ１よりは小さいが２の累乗で除算もしくは乗算することにより０．５よりも大きくスケールされる。指数部は仮数をスケールするのに使用される２の累乗を示し、正の指数は量がその２の累乗を乗じた仮数に等しいことを意味し負の指数は量が２の累乗で除算した仮数に等しいことを意味する。したがって、指数部は正もしくは負であることがありそれ自体の符号ビットを有する。事実、指数部は表現した量の大きさの２を底とする対数の整数部である。しかしながら、小数部は線形目盛上でも仮数により表わされる。したがって、浮動小数点は最上位ビットが対数目盛上にあり最下位ビットが線形目盛上にある混合線形／対数表現である。
【０００４】
また完全対数形式で数値表現を与えることも知られている。完全対数表現は量の大きさの対数の整数部および小数部の両方が符号ビットと一緒に使用されてその大きさの対数をとる前に量が正であったか負であったかを示すのに使用される。浮動小数点表現の指数部と同様に、大きさの対数はその大きさが１よりも大きいか小さいかを示すそれ自体の符号を有する。あるいは、対数は常に量がある最小表現可能値よりもどれだけ大きいかを記述する正の数であるとみなすことができる。いずれの場合も、ゼロの対数はマイナス無限大であるため対数表現には典型的にゼロを表現できないという問題がある。
【０００５】
線形すなわち固定小数点表現の利点は、乗算器は一般的により複雑で電力を消費するが、加算器は典型的に単純に構成されることである。完全対数表現の利点は、加算は一般的に実施が困難であるが、乗算器および除算器は典型的により単純に構成され、それぞれ単なる加算器および減算器であることである。
【０００６】
さらに、対数表現は量を二乗する（左シフト）もしくは量の平方根をとる（右シフト）時に一般的に有利であり、したがって、
【数１】
ＳＱＲＴ（Ｘ２＋Ｙ２）
のような演算をしばしば実施しなければならない場合には、固定小数点算術を使用する時の３つ（２つの二乗と１つの平方根）の替わりに実施すべき困難な演算（“＋”）は１つしかないため、対数算術は典型的により効率的となる。
【０００７】
浮動小数点表現では、加算および乗算は除算および平方根演算のように一般的により複雑な演算となる。したがって、浮動小数点は典型的に高い処理負荷を課す。
【０００８】
（発明の概要） 前記検討から、計算に使用する値の完全対数表現を提供することが本発明の目的である。
【０００９】
改良された対数加減算装置および方法を提供することが本発明のもう１つの目的である。
【００１０】
符号付き対数値を和分する改良された装置および方法を提供することが本発明のもう１つの目的である。
【００１１】
ゼロ値の表現を与えながら完全対数表現を使用する装置および方法を提供することが本発明のもう１つの目的である。
【００１２】
本発明は対数値として表現された数値の加算装置および方法を提供する。最初に対数値を離散数の値の１つとして表現することにより対数加算に通常関連する処理負荷なしで多数の符号なし対数値を和分する方法が提供される。例えば、対数値は８−ビット２進語で表わして最大値から最小値までの範囲を表わす合計２５６の個別の可能値を与えることができる。カウンタが和分される対数値の大きな（すなわち２５６の値よりも著しく多い）母集団内の離散値の各々の発生数のカウント値を累算する。次に対数値自体の和分ではなくカウンタ内のカウント値の反復低減により値の和が発生される。反復手順には最初に置換される１よりも大きいカウント値に比例するより高い値のカウンタ内のカウント値を増分することによりより低い値のカウンタ内の１よりも大きいカウント値を置換することが含まれている。全てのカウンタが１もしくはゼロの値に低減されていると、より低い離散値のカウンタで開始して和文される全ての対数値の和を表わす非ゼロ値を有するカウンタが１つだけとなるまで非ゼロカウント値が結合される。
【００１３】
本発明はさらに符号付き対数値の累算も提供する。後述するように新たにＺｅｃｈ対数を適用して処理負荷が低減される。本発明の方法は対数値の加減座に限定された精度を必要とする場合に効率を改善する。
【００１４】
本発明の第１の特徴にしたがって、複数の対数数の和分方法が提供される。複数の対数数の各々が所定数の値、例えば８−ビットＡ／Ｄコンバータ出力の２５６の可能値、の中の１つとして表現される。複数の対数数の各々の発生数が複数のカウンタにより累算され、その各々に所定数の値の中の１つの値が関連している。１よりも大きいカウント値を有する複数のカウンタの中の第１のカウンタのカウント値が複数のカウンタの中の第１のカウンタのカウント値を減少し複数のカウンタの中の第２のカウンタを増分することにより低減される。複数のカウンタの中の第２のカウンタは複数のカウンタの中の第１のカウンタの所定数の値の中の関連する１つの値の倍数に対応する所定数の値の中の関連する１つの値を有するカウンタとして選択される。複数のカウンタの中の第２のカウンタがする場合には複数のカウンタの中の第３のカウンタを増分してオーバフローが先送りされる。複数のカウンタが１以下のカウント値を有するようになるまで演算は繰り返される。
【００１５】
本発明のもう１つの実施例では、１以下のカウント値の“ヒストグラム”がさらに処理されて複数のカウンタの中のもう１つのカウンタを増分することにより複数のカウンタの中の２つのカウンタ内の非ゼロカウント値を置換する単一の非ゼロ値だけが与えられる。複数の対数数の和に対応する非ゼロカウント値を含むのが複数のカウンタの中の１つのカウンタだけとなるまでこの演算は反復される。本発明の複数の量を和分（ｓｕｍｍａｔｉｏｎ）する方法の別の実施例では、和分は複数の単ビットメモリ要素を利用して行われる。各々が離散値の値の１つに対応する複数の単ビットメモリ要素がゼロに初期化される。次に複数の量の中の最初の１つが得られる。複数の量の中の得られた１つの量の量子化された値に対応する単ビットメモリ要素の中の最初の１つが次にモジュロ−２の演算を使用して増分される。最初の単ビットメモリ要素である時にキャリーが発生する場合には、最初の単ビットメモリ要素の量子化された値の２倍に対応する第２の単ビットメモリ要素がモジュロ−２の演算を使用して増分される。一実施例では、第２の単ビットメモリ要素の増分に続いてその増分からの任意のキャリーがキャリーを発生する単ビットメモリ要素の量子化された値の２倍に対応する単ビットメモリ要素を反復増分して伝播される。演算は和分される複数の量の各々について繰り返されて複数の量の和を示す離散数の値の中の１つに対応する単ビットメモリ要素の中の非ゼロ要素を与える。好ましくは２分の１により関連される対応する値を有する単ビットメモリ要素は一緒に鎖でつながれて２進語を形成する。
【００１６】
本発明の方法のもう１つの特徴にしたがって、各々が符号および対数量（ｌｏｇｍａｇｎｉｔｕｄｅ）を有する第１の数と第２の数を結合する方法が提供される。第１の数の符号が第２の数の符号と比較されて第１および第２の数を結合するのに加減算が必要かどうかが確認される。第２の数の対数量と第１の数の対数量との差が求められる。求められた差に基づいて第１の数と第２の数の中のより大きい値の数が識別され出力レジスタに出力値として置数される。所望する精度閾値に達すると演算は停止される。そうでなければ、所望する精度閾値に達するまで次のステップが繰り返される。求められた差の最上位部および最下位部が識別される。最上位部に関連する第１の値が第１のテーブルから得られる。第１のテーブルから得られる値は、好ましくは、Ｚｅｃｈ対数値である。得られた第１の値は出力値と累算される。得られた第１の値は求められた差とも累算されて新しく求められた差が与えられる。
【００１７】
符号および対数量を有する２つの数を結合する本発明の方法のもう１つの実施例では、繰返し演算はさらに第２のテーブルから最下位部に関連する第２の値を得ることを含んでいる。好ましくは、第２の値も予め計算されたＺｅｃｈ対数値である。得られた第２の値も求められた差と累算されて新しく求められた差が与えられる。
【００１８】
当業者ならばお判りであろうが、本発明の方法の特徴に関して本発明を説明してきたが、本発明は方法、装置もしくはコンピュータプログラムとして実施できることをお判り願いたい。
【００１９】
（発明の詳細な説明） 次に本発明の好ましい実施例を示す添付図を参照して本発明をより詳細に説明する。しかしながら、本発明は多くの異なる形式で実施することができここに記載する実施例に限定されるものではなく、これらの実施例は本開示が綿密かつ完全であって発明の範囲を等業者に完全に伝えるためのものである。
【００２０】
次に図１に、本発明を利用できる１つの動作環境を表わすアンテナにより受信される信号のサンプルからの対数値の累算について本発明の動作環境を説明する。図１はアンテナから信号を受信する典型的な受信機ブロック図を示す。送信機が信号を送信しているか（送信機）受信しているか（受信機）に応じて送受信器スイッチ１１によりアンテナ１０が交互に受信機もしくは送信機に接続される。実施例では、受信機は帯域制限フィルタ１２、ダウンコンバータ１３、局部発振器１４、第１のＩＦフィルタ１５およびＩＦ増幅器システム１６を含んでいる。図１に示すように、ＩＦ増幅器システム１６はほぼ対数目盛り上で信号の複数の測定を行う検出器もしくは他の手段を内蔵するものとする。その後測定はＡ／Ｄコンバータ１７によりサンプルされデジタル化される。測定は所定数の値からＡ／Ｄコンバーター１７により選択される。ＩＦ増幅器システム１６はさらに瞬時信号位相情報を含む帯域制限された第１もしくは第２のＩＦ信号を位相デジタイザ１８に出力することができ、それは位相の余弦および正弦もしくは位相値自体等の位相に関連するデジタル化された値を出力する。デジタル化された測定値は２つの成分を含むことができ、１つは瞬時信号振幅の対数にほぼ比例し他方は同じサンプリングクロックで測定した位相関連値である。デジタル化された信号強度測定値のこれらの特徴の組合せにより前記米国特許第５，０４８，０５９号のログポーラ（ｌｏｇｐｏｌａｒ）技術を実施する時の受信信号の完全な複素ベクトル性質を表わす一連のログポーラ値が形成される。次にログポーラ値をデジタル信号プロセッサ（図示せず）で処理して情報を抽出することができる。受信通信信号をサンプリングして受信信号強度表示（ＲＳＳＩ）を発生するセルラー電話機は図１のシステムを応用できる使用例である。
【００２１】
本発明は特にアナログ形式ではなくデジタル形式で表わされる対数値を処理するのに向けられていている。デジタル平均化は、例えば、分離された期間（ｄｉｓｊｏｉｎｔｅｄ ｐｅｒｉｏｄｓ ｏｆ ｔｉｍｅ）にわたる平均の計算によく適していることがお判りであろう。しかしながら、特に消費電力に関して、多数の値をデジタルで累算、積分もしくは合計することはアナログ方法の使用に比べてより負担となることがある。本発明は多数のデジタル対数値の加算もしくは累算に伴う努力を低減しようとするものである。
【００２２】
本発明の第１の特徴に従って、合計される値の数がＡ／Ｄコンバータが作り出せる可能な異なる数（すなわち、出力ビットパターン）よりも遥かに大きい場合には、各可能値が総和ウィンドウにわたって何回観察されるかをカウント値するだけでよい。例えば、Ａ／Ｄコンバータが８ビットコンバータであれば、２５６の可能な異なる値をその出力に作り出すだけでよい。典型的にこれらの値は０．５ｄＢステップで１２８ｄＢの範囲を有する対数デシベル目盛り上の測定に対応する。ビットパターンの最下位ビットは０．５ｄＢステップに対応し、第２の最下位ビットは１ｄＢステップに対応し、以下同様に６４ｄＢステップに対応する最上位ビットまで続く。Ａ／Ｄコンバータは２５６の異なる出力値を作り出すため、いかに多くの測定サンプルが実際にとられても、各出力が何回作り出されたかを記憶するのに僅か２５６のカウンタしか必要としない。２５６のカウンタは各々がアドレスを有するマイクロプロセッサメモリ内の２５６のランダムアクセスメモリ位置により簡便に表わすことができる。メモリアドレスが測定できる最低値（例えば、最低ノイズレベルよりも低い）に等しい値で始まって逐次増加するものと考えられる場合には、各アドレスは対応する対数数値に等しいと考えることができる。累算される量が測定されないが、例えば、目盛内に対数値が含まれる場合には、累算される対数数の最低値に基づいて最低値カウンタを選択することができる。本発明の実施例を記述するのに使用される“カウンタ”は“メモリ位置”もしくは“ビン（ｂｉｎｓ）”ともいわれる。
【００２３】
Ａ／Ｄコンバータが測定をサンプルするたびに、その出力（デジタル化された測定値）に対応するアドレス（メモリ位置）が１だけ増分されてその特定の測定値の発生を記録する。好ましくは測定累算期間の開始時にカウント値はゼロにリセットされる。
【００２４】
図２に示すように、観察期間の終りにメモリ位置の内容は累算される対数数確率分布のヒストグラムを与える。典型的には、全てのカウンタに非ゼロカウント値が集中されるわけではない。セルラー電話機信号等の自然発生信号の測定に基づく本発明の応用において分布は一般的に全受信機ダイナミックレンジよりも狭い値の領域の周りに集中されるものと予期される。行われる測定数が大きすぎず、任意特定値の観察数が２５５を超えないと予期される場合には、カウント値は１つの８ビット内に含めることができる。しかしながら、本発明の別の特徴ではビンのカウント値のオーバフローが補償される。１つの８ビットビンの典型的な実施例におけるオーバフローは同じ数が２５６回観察されていることを示すため、これらの観察の総エネルギ（数の和）はｄＢ目盛り上で１０ＬＯＧ１０（２５６）である単一値のエネルギの単純に２５６倍である、すなわち単一値よりも２４．０８ｄＢ多い。
【００２５】
１つのビン内に２５６のカウント値を配置するのではなく、前記したようにアドレス（メモリ位置）が０．５ｄＢステップでデシベル表示の数値を表わす場合には、２４．０８ｄＢ高いビン、すなわちビン（アドレスプラス４８）、内にカウント値１が配置される。オーバフローしたビンは必要に応じて自動的にリセットされる（すなわちこのビンの８ビット実施例におけるＡ／Ｄコンバータからの対応する信号強度測定の第２５５から第２５６発生までカウント値する時にビンのカウント値が１１１１１１１１から００００００００へオーバフローする場合）。このオーバフロープロセスは前記したように２４．０８ｄＢ高いものに対応するメモリ内で４８離れたバイトアドレスを鎖でつないで１つの長い２進語とすることにより実現することができる。したがって、２５５のカウント値を増分してもう１度ゼロに等しくなる時の単バイトカウント値のオーバフローは鎖内の次のバイト、すなわちメモリ内の４８高いバイト、を増分することにより償われる（ａｌｌｏｕｎｔｅｄ ｆｏｒ）。使用する対数目盛がステップ当り０．５ｄＢでなければ、４８のアドレス増分はエネルギの２４．０８ｄＢの増分に最も近い何らかの値に変えなければならない。別のメモリ記憶構成が後に開示されておりそれは鎖でつながれたこれらのバイトを次々にメモリ内に配置してより長い語を生成し従来の２進加算器を使用するキャリー伝播を容易にする。
【００２６】
前記したように値のヒストグラムを集めた後で、図２に示すように、カウント値で表わされる数（エネルギ）が合計される。同じ値の２５６カウント値（発生）が前に２４．０８ｄＢ高い１つの値と等価であると説明されたのと同様に、任意の値の任意複数のカウント値の観察はより高い値の単一カウント値、すなわちより高いアドレスされたメモリ位置の１のカウント値、の観察と等価である。例えば、アドレスＡ内の２のカウント値はアドレスＡ＋３ｄＢｓ（０．５ｄＢステップの場合のＡ＋６）の１のカウント値と同じである。同様に、アドレスＡの３つの等しい値はアドレスＡ＋４．７７ｄＢ（近似的にＡ＋１０）の１つの値に一致し、Ａの等しい４つの値はＡ＋６ｄＢｓ（Ａ＋１２）の１つの値に一致し以下同様である。いかなるビンにも２５５よりも大きいカウント値はないため（１つの８ビットビンを仮定して）、より低い値のビン内の数の和を表すために別のカウント値を増分することができるよう２から２５６の可能な各カウント値をアドレスの最も近い整数へ離して変換するのにリードオンリーメモリ（ＲＯＭ）内の２５５エントリルックアップテーブルで十分である。
【００２７】
本発明の一実施例においてより高いアドレスのカウント値の増分により１よりも大きいカウント値を置換する前記手順は最下位ビンから開始して、図３に示すように、各ビンが最終的にせいぜい１のカウント値しか含まなくなるまで反復適用される。さらに本発明の実施例に従った数の和分はさまざまなビンからの単一（単位）カウント値を結合する手段を利用する。
【００２８】
浮動小数点表現や前記した固定小数点対数目盛等の非線形マッピングを使用して有限精度数として量が表わされる場合には、このような量を結合して丸め誤差の影響を低減しながら和を表わす数を作り出すための好ましい順序がある。好ましくはない方法の例により好ましい方法を理解するのは容易である。固定精度対数表現には精度の最下位ビットが必ずしも同じ量を表わさないという特徴がある。例えば、小数点の前と後に１つの１０進数がある底１０対数で量が表わされる場合には、量１０，０００，０００は“７．０”として表わされ“７．２”はおよそ１２，５００，０００を表わす。したがって、最下位デジットを０から１へ増分すると２，５００，０００で表わされる量が増大する。一方、量５は“０．７”で表わされ“０．８”はおよそ６．２５の値を表わし、この場合最下位デジットを１だけ増分すると１．２５の量の増加しか表わさない。
【００２９】
対数加算ユニットが（それらの各底１０対数“７．０”および“０．７”で表わされる）１０，０００，０００および５等の値内に大きな差異のある２つの量を結合して同じｘ．ｘ表現内にそれらの和１０，０００，００５の対数を得るよう要求されると、１０，０００，００５の対数は“７．０”の最下位デジット内に見られる１０，０００，０００の対数からは不十分な差異であるため、答はやはり７．０となる。したがって、１０，０００，０００への５の加算は５を何回加算しても見えない。たとえ５が１００万回加算されても、結果はやはり１０，０００，０００の対数（すなわち“７．０”）であり所望する１５，０００，０００の対数ではない。したがって、対数量は好ましくは“最小プラス最大”の順序では結合されない。替わりに、２つの最小量が好ましくは最初に一緒に結合されて２つの量の各々よりも大きい和を作り出す。この和は好ましくは値の下降順に再ソートされ残りの量は合計されさらに２つの最小量が再度結合され結合すべき２つの量、例えば最大量およびその他全ての和、しか残らなくなるまで以下同様に続けられる。したがって、より小さい全ての量の和は最大量に近い値であり最大量と結合した時にその最下位デジットに影響を及ぼすよい機会を有する。例えば、５を１００万回１０，０００，０００に加算する場合、最初に１００万の５を一緒に加算して５，０００，０００の対数を“６．７”として得る方がよい。次に“６．７”と“７．０”の対数加算として和５，０００，０００を１０，０００，０００と結合して和１５，０００，０００の対数を“７．２”として得ることができ、それはより正確な値“７．１７６”に使用される固定位置デジットの最も近い近似である。
【００３０】
したがって、図３に達した状況からの手順はより低い値メモリ位置のカウント値を最初に結合してどのより高いアドレスメモリ位置がそれらの和と等価であるかを確認することである。したがって、ビン２および４内の２つの最低非ゼロエントリが最初に結合される。ビン４内の量が“Ｘ”であれば、ビン２内の量は１ｄＢ低い、すなわちおよそ“０．８Ｘ”である。したがって、ビン２と結合されたビン４の量は“１．８Ｘ”であり、それは１０ＬＯＧ１０（１．８）であって“Ｘ”よりも２．５ｄＢ高く、ビン４よりも５ビン高いビン（例えば、ビン９）内のカウント値と等価の結合である。ビン９は１だけ増分されてビン２およびビン４が集められる。図３の例では、ビン９は既に１を含んでおり２へ増分される。ビン９内の２は３ｄＢ高いビン（すなわち、ビン１５において６ビン高い）内の１と等価である。したがって、ビン９は増分したモジュロ−２であり、２ではなくゼロとなりビン１５へキャリーが発生される。実施例では、ビン１５はゼロであるためキャリー無しで１へ増分しキャリー伝播は停止する。そうでなければ、キャリー伝播は停止するまでビン９，１５，２１等を通って続けることを許される。当業者ならば，キャリー手順は６だけ離れたビン間を鎖でつないだキャリーの２進加算、あるいは選択した特定の対数（もしくは単調）目盛に対するエネルギの３ｄＢもしくは２分の１に対応するなんらかの分離、であることがお判りであろう。
【００３１】
さらに図３について、ビン２および４内のエントリを結合した後で、結合される次の２つのエントリはビン６および１０内にあり、ビン９内のエントリは前記キャリー演算によりゼロにクリアされている。ビン６および１０は４ビンすなわち２ｄＢ離れており、それらの相対値はビン６に対しては“０．６Ｘ”でありビン１０に対しては“Ｘ”である。ビン６および１０の結合により“１．６Ｘ”の和となりそれは“Ｘ”よりも２ｄＢ高く、ビン１０よりも２ｄＢ（４位置）高いビン、すなわちビン１４、内のカウント値と等価の結合である。したがって、ビン１４内のエントリは増分されてビン６および１０の結合されたエネルギを受け、ビン９からのキャリーに対して前記したようにビン２０へのキャリーを生じビン１４はゼロのままとされる。この手順は全てのビンが結合され最後の結合によりビン位置に１が配置されるまでビン１２および１３の結合等により継続され、そのアドレスによりオリジナル数の和の対数が得られる。
【００３２】
図３において、図２の同じ値の多数の発生から単一発生へ低減した後で、ヒストグラムメモリは０もしくは１のエントリ、すなわち単ビット量、しか含んでいない。したがって、図２に関して説明したようにカウント値を減少した後で得られる情報は２５６バイトではなく２５６ビットのより小さいメモリ内に保持することができる。図４に示すように、この圧縮表現は僅か３２バイトしか占有しない。さらに、非ゼロエントリの結合はビン対の結合に限定する必要がない。例えば、予め計算したルックアップテーブルをアドレスするバイトを使用して０もしくは１エントリが単バイトを占有する８つのビンを１度に同時に結合してバイト内に含まれる全ての非ゼロエントリの和を表わす数を得ることができる。例えば、バイトが左側に最上位ビット（より高い値のビンに関連する）を有するビットパターン１００１００１０を含む場合、最上位ビットで表わされる量を“Ｘ”で表わし、次の右のビット（ビンとビンとの間隔は０．５ｄＢで、３ビン低い）は“Ｘ”よりも１．５ｄＢ小さい量すなわち近似的に“０．７Ｘ”を表わし、６ビン低い（３ｄＢ）次のビットは“０．５Ｘ”を表わす。したがって、全体バイトは“Ｘ”＋“０．７Ｘ”＋“０．５Ｘ”＝“２．２Ｘ”の量を表わしそれは“Ｘ”よりも３．５ｄＢ大きい。したがって、全体バイトは７だけ高いビン内のエントリで置換することができ、それは次のバイトの第２の最上位ビット内に１を配置して遂行される。したがって、前記ビットパターンに対するルックアップテーブルエントリは値１５を含み、現在バイト（“Ｘ”の基準値として使用された）プラス７の増分の最上位非ゼロビット（すなわち、ビット数８）の数である。
【００３３】
２進では、１０進数１５は１１１１であり、それは１．１１１と解釈すべきであり小数点の左の数字はメモリ内で何バイト高く１を加えるかを示し（すなわち、この場合は１バイト高い）小数点の右の１１１はどのビット（すなわち、この場合は１１１＝７）に１を加えるべきかを示す。バイト内の非ゼロエントリの合計結果は同じバイト内に１を与えることがあることをお判り願いたい。例えば、ビットパターン００００００１１に対する合計結果は同じバイト内の最も近い近似へのビットパターン１０００００００である。
【００３４】
しかしながら、元々１つの非ゼロエントリしか含んでいないバイトは前記した方法で１を照合しても変化しない。したがって、異なるバイトからの１を照合する手段も本発明により提供される。本発明の一実施例に従って、それはバイト内の１の照合結果によりバイト内の全ビットがゼロにリセットされたままとされない場合にフラグをセットすることにより提供される。フラグは可能な全ての８ビットパターンについて予め計算してルックアップテーブルに格納することができる。例えばルックアップテーブル出力バイトの最上位，すなわち“符号”ビット，とすることができるフラグがセットされると，ルックアップテーブル出力値の残りのビットは照合後に１のままとされるバイト内のビット位置を示すことができる。次の非ゼロバイトに照合を実施した後で，前の照合操作からフラグがセットされると，図３に関してビンの結合に対して前記した手順を使用して前の操作から残された量が最初に新しいバイトの最下位非ゼロビットと結合される。したがって、８ビットを一時に結合する試みは総和プロセスをスピードアップさせるが，単ビットを結合する必要性に完全に取って代わることはできない。
【００３５】
図３に示すように，ビン９が１から２へ増分されており、それがゼロにリセットされてビン１５にキャリーを発生する時は，プロセスは一時に６ビット飛越すキャリーとの２進加算である。６だけ離れたビットが同じ語内に現れるように、図５に示す方法で図４の圧縮メモリを再構成することにより，語の任意のビットに１を加算するのに従来の２進加算器を使用することができる。一般的に、選択した対数目盛が３ｄＢを表わすＬビン分離を有する場合には（より正確には表わされる量の２：１の増加）、各第Ｌ番１ビットビンを同じ２進語内に配置することができる。したがって、図５に示すように、第１の語はＭビン０，Ｌ，２Ｌ．．．を含み，第２の語はＭビン１，Ｌ＋１，２Ｌ＋１．．．を含みビンＬ−１，２Ｌ−１，３Ｌ−１．．．を含む第Ｌ番Ｍビット語まで同様とされる。
【００３６】
任意のビンが増分される時は，増分されるビンに対応するビットを含む語が２進加算器２０へ読み込まれ，そこで増分されるビット位置内の１は別として全てのゼロを含むもう１つのＭビット語が加えられる。正規の２進キャリー演算が本方法のキャリー必要条件を引き受ける。どのビットが増分されるかの決定は予め記述されている，すなわち対もしくはそれ以上の非ゼロビットをルックアップテーブルを使用して一緒に照合することにより照合したビンの和と等価である量を表わすためにそこへ“１”を加算しなければならないより高いビンのビン数もしくはビン位置、すなわち本例ではビット数１５、を決定する。したがって、図５のビン０，１，２．．．Ｌ−１からなる垂直カラムからの１の照合（すなわち、全ての語の最下位ビットにわたる）は、これらのＬビットを使用してルックアップテーブルをアドレッシングした後で，特定の語の特定ビットの増分と等価であることが判り、それは次に加算器２０を使用して実施される。あるいは、１を水平に、すなわち図５の同じＭビット語にわたって、照合するようにルックアップテーブルを予め計算することができる。１語内のビットウェイト（信号の大きさで表わされる）は２進級数１：２：４：８．．．等内で関連されているため、このルックアップテーブルは図２のヒストグラムを図３の単ビットエントリへ縮小するのに使用する対数へ２進数を変換するためのルックアップテーブルと同じである。特定のマイクロプロセッサ命令セットやアプリケーションのプログラミングにとってどちらが最も効率的であるかに応じていずれかの方法を使用することができる。
【００３７】
次に図５についてＲＳＳＩ値を対数累算するための特に単純な方法を説明する。受信機が測定できるＲＳＳＩ値の全範囲は１２８ｄＢであり、測定は０．５ｄＢ最下位ビット（ＬＳＢ）値を有する８ビット語で表わされるものとする。より正確には，ＬＳＢ値は１０ＬＯＧ１０（２）／６であり０．５に非常に近い。したがって、図５のビンは各々が４３ビットの６語を形成し，可能な２５６値を包含するのに十分な２５８ビンを与える。各語内の隣接ビンは２の因子だけ離れたエネルギレベルを表わし、観察したＲＳＳＩ値はその８ビット値によりアドレスされる適切なビン数０から２５５へ１を加えるだけで記録される。ビンに“１”が加えられると、リップルキャリーはそのビンを含む語の中を流れることができる。語の最上位ビット（ＭＳＢ）は非常に高いエネルギレベルを表わすため，非常に多数の強信号（高い量）値を累算しない限りオーバフローは予期されないが、語長にあるヘッドルームを許す、例えば、語長を４３から４８へ増大することによりオーバフローを防止することができる。ＭＳＢは最高ＲＳＳＩ値よりもおよそ３２倍すなわち１５ｄＢ大きいエネルギレベルを表わすようになる。
【００３８】
全てのＲＳＳＩ値をこのように累算した後で，６つの４８ビット語の各々が全エネルギの部分対数和でありさらに結合されて最終和が得られる。それは対数加算もしくはここに記載されたいずれかの方法により遂行することができる。したがって、任意多数のＲＳＳＩ値の累算は本質的に各々が０．５ｄＢだけ離された全ダイナミックレンジの異なる“スライス”からの部分対数和を表わす６つの２進語の結合へ簡約化される。
【００３９】
図６Ａ，６Ｂ，６Ｃは前記した方法を実現するマイクロプロセッサアーキテクチュアを利用する本発明に従った装置の実施例を示す。図６Ａにおいて、メモリセグメント１０１，１０２，１０３を含むメモリ１００はそこに値を読み書きする算術／論理ユニット（“ＡＬＵ”）２００によりアドレスされる。複数の対数表現数を累算する目的を実施するために，メモリ１０１は結合される対数数を保存する手段を提供しＡＬＵ２０はメモリ１０１から逐次数を読み出すことを含む本発明の方法特徴を実施するようにプログラムにより制御される。次に読み出した各数はヒストグラムメモリ１０２の特定のビンをアドレスするのに使用され、それは次に増分される。全ての値がメモリ１０１から読み出されると、メモリ１０２は各離散信号強度測定値がメモリ１０１内で何回生じたかのカウント値を含んでいる。
【００４０】
図６Ｂは前記した本発明の方法の特徴に従ってヒストグラムメモリを単ビットビンしかない圧縮形式へ縮小する手段を提供する。図６Ｂに示すように、ＡＬＵ２００はヒストグラムメモリ２００から逐次カウント値を読み出し各カウント値を使用して対数ルックアップテーブル３０１をアドレスするようにプログラムされている。ルックアップテーブル３０１は１をヒストグラムビン内の総量と等価に配置しなければならないビン数を指示するのに必要な現在ビン数への増分に関するカウント値の対数を戻す。増分すべき位置に既に１を含む圧縮メモリの結果として生じることがある任意のキャリーを引き受けるリード、増分およびライト操作によりこの１を直接圧縮メモリ１０３へ書き込むことができる。
【００４１】
図６Ｃは圧縮メモリ１０３内で１を照合して最終対数和を得る演算を示す。この演算を実施する時に，ＡＬＵ２００は一時に１バイトを読み出し、それは和を表わすためにビットを増分しなければならない現在バイトから離れたビンの増分もしくは離れたビンの間隔（デルタ数）に関してバイトの全ての非ゼロ要素の和の対数を戻す第２のルックアップテーブル３０２へ加えられる。ＡＬＵ２００はデルタ数を現在バイトアドレスへ加えて増分されるビットを含むバイトのアドレスを得る。そのバイトは次に読み出され、適切なビットが増分され、増分したビットが既に１であれば次に前記した方法に従ってキャリーが実施される。
【００４２】
当業者ならばお判りのように、図４，５，６Ａ，６Ｂ，６Ｃの本発明の前記した特徴はハードウェア、ソフトウェアもしくはその組合せにより提供することができる。本発明の装置のさまざまな構成要素は一部個別要素として図示されているが、実際上入出力ポートおよび実行ソフトウェアコードを含むマイクロコントローラ、カスタムもしくはハイブリッドチップ、個別部品もしくはそれらの組合せにより実現することができる。
【００４３】
図７Ａおよび図７Ｂは本発明の１つの特徴の一実施例の動作を示すフロー図である。ブロック１０００において、ヒストグラムメモリ要素はゼロにリセットされ数の新しいセットを累算する準備ができる。ブロック１００１において、信号強度測定等の数のアナログ表現がＡ／Ｄコンバータへ入力される、あるいは数の予め格納されたデジタル値がメモリ１０１から検索される。この値はブロック１００２において増分されるメモリ１０２内のアドレスに関連しており，したがってその特定値の発生を記録している。ブロック１００３において、さらに入力値を累算すべきかを決定するテストが行われる。累算すべきであれば、ブロック１００１へ戻って次の値を得、そうでなければブロック１００４へ進んでヒストグラムメモリ１０２内に含まれる完全なヒストグラムの縮小が開始される。
【００４４】
ブロック１００４における処理は最低番号ビン、すなわち最少数（測定信号の可能な大きさの値）が観察された回数を与えるカウント値を含むアドレスにおけるヒストグラムメモリ１０２内に含まれるカウント値、で開始される。最小値が検出された回数を示すカウント値はヒストグラムメモリ１０２から検索される。このカウント値はブロック１００５においてルックアップテーブルをアドレスして１のカウント値がブロック１００４で検索された倍数カウント値と等価である現在ビン数よりも高いビン数“デルタ”を決定するのに使用される。ブロック１００４におけるカウント値が既に１の値を含んでおれば，ブロック１００５から１００８までの動作は実施する必要がない。そうでなければ、ブロック１００６においてビン数“デルタ”内のカウント値を現在ビンよりも高く増分することにより１よりも大きいカウント値が減少される。ブロック１００７において、ビンのカウント値オーバフローがチェックされる。増分によりオーバフローとなってカウント値がゼロとなる場合には、その特定の値（数）が生じる回数が最大ビンのカウント値を１だけ越えており（ＭＡＸＣＯＵＮＴ＋１）ｘＶＡＬＵＥの合計がさらに高い番号のビン内の１のカウント値と等価となりそれは常に（ＭＡＸＣＯＵＮＴ＋１）の対数により決定されるだけ離された一定数のビンである。したがって、この一定数のビンはブロック１００８において“デルタ”の値に加算されブロック１００７においてオーバフローが検出されなくなるまでブロック１００６へのリターンが繰り返される。操作は次にブロック１００９へ進みさらに任意のビンが処理されるかが確認される。処理される場合には、ブロック１００４へ戻って次のビンが処理される。そうでなければ、操作はブロック１０１０へ進み全てのビンがゼロもしくは１しか含まず，適切な高い番号のビンにおいて倍数カウント値が単一カウント値へ変換されている。
【００４５】
ブロック１０１０において、現在ビン数が最低番号ビンへリセットされる。随意，最低番号非ゼロビンへ戻ってゼロビンの処理を回避することができるが、ブロック１０１１を替わりに使用して非ゼロビンをテストしそれらをスキップすることができる。ブロック１０１１において非ゼロカウント値が検出されると、そのビン数がブロック１０１３において保存される。ブロック１０１４において、ブロック１０１５におけるチェックにより決定される次の非ゼロビン数を見つけるためにアドレスが増分される。ブロック１０１６においてこれ以上ビン数はないことが確認されると、所望の対数和を示すブロック１０１３に保存されたビン数で操作はエグジットする。そうではなくて、ブロック１０１５において第２の非ゼロビンが検出される場合には、ブロック１０１３で保存されたビン数から間隔がとられたそのビン数がブロック１０１７で計算されビン間隔はブロック１０１８においてルックアップテーブルをアドレスして１のカウント値が最初の非ゼロビンの値（ブロック１０１３からの）と第２の非ゼロビンの値（ブロック１０１５で見つかった）との和と等価である高い番号のアドレスを決定するのに使用される。ルックアップテーブルは最後に見つかった増分されるビンからデルタアドレスを戻す。デルタアドレス位置のビンは最後に見つけた非ゼロビンをゼロにリセットした後でブロック１０１９において増分される。後者の目的はブロック１０１９で増分されたビンが最後に見つけた非ゼロビンと同じであるかもしれないことである（例えば、値の和が２つの中の大きい方よりも十分大きくなければ和に対する大きい値を超える増加を示す丸めとなる）。したがって、ブロック１０１９の後で、最後に見つけた非ゼロビンは不変カウント値を保持している。
【００４６】
もう１つの可能性はブロック１０２０の後でビンのカウント値が１よりも大きくなることがあることである。モジュロ−２増分の使用によりこの場合モジュロ−２オーバフローを表示しながらビンはゼロへ増分するようにされる。オーバフローはブロック１０２０において検出されブロック１０２１において１のカウント値が現在ビン内の２のカウント値と等価であるより高くアドレスされたビンの間隔が検出される。現在ビン内の２のカウント値の替わりに、このより高くアドレスされたビン内に１のカウント値を加えるためのリターンがなされ、ブロック１０２０においてオーバフローが検出されなくなるまでリップルスルーキャリー（ｒｉｐｐｌｅ−ｔｈｒｏｕｇｈ ｃａｒｒｙ）効果の形でプロセスが反復する。最後に見つけた非ゼロビンアドレスにまだ等しいビンアドレスでブロック１０１１へのリターンが行われる。ビンのカウント値はゼロとなりその場合ブロック１０１１および１０１２は非ゼロビンが見つかるかあるいは全てのビンがテストされるまでビンをスキップする。したがって、最後に見つけた非ゼロビンアドレスもしくは新しい非ゼロビンアドレスがブロック１０１３において保存され全てのビンが空にされたことを示すブロック１０１２もしくはブロック１０１６の処理が終了されるまでプロセスは継続する。ブロック１０１３に保存されたビンアドレスは所望の対数和を示すようになる。
【００４７】
図７Ａおよび図７Ｂに示すように、ブロック１０００から１００９までの操作は低い値の多数の観察を高い値の単一観察へ有効に縮小する。ここに記載された対数算術の新しい方法は繰返し加算の替わりに通常の線形算術で乗算を使用するのと同様である。多数のカウント値を単一カウント値へ縮小した後で、メモリはゼロもしくは１のカウント値しか含んでいない。したがって、これらの単ビット値のよりコンパクトな記憶装置を使用することができる。図８Ａおよび図８Ｂはよりコンパクトな記憶装置を使用して対数累算をさらに加速させる本発明の実施例を示す。ブロック２００１から２０１７までの操作は図７Ａおよび図７Ｂに関して前記したヒストグラムの構造および縮小を示す。しかしながら、図７Ａおよび図７Ｂに関して検討されなかったこれらの操作の詳細は図８Ａおよび図８Ｂ操作の実施例に例示されている。例えば、観察した入力測定値（数）のヒストグラムを作る時に、ブロック１００４においてビンオーバフローのテストが行われブロック２００５においてＬＯＧ（ＭＡＸＣＯＵＮＴ＋１）だけ高い高い番号のビンへの対数キャリーが行われる（図７Ａおよび図７Ｂのブロック１００７に関して前記したように）。また、ブロック２００９において、ビンのカウント値がすでにゼロもしくは１であればそれぞれブロック２０１０もしくは２０１１において値を直接圧縮メモリ内に記録することができる。数の発生の縮小はブロック２０１２から２０１５に示すように多数の発生がブロック２００９で検出される時に行うだけでよい。ブロック２０１７において全てのビンが縮小されていることが検出されると、ブロック２０１８において操作が継続されて圧縮メモリに現在含まれている単ビット値が処理される図８Ａおよび図８Ｂの操作の実施例では、図７Ａおよび図７Ｂの実施例に比べて、単ビットカウント値はバイトを処理して一時に８ビット処理される。しかしながら、本発明の利点はこのような実施例に限定はされずブロック２０２１において適切なサイズのルックアップテーブルを使用することにより一時に任意数のビットを処理しても得られることをお判り願いたい。
【００４８】
ブロック２０１９において圧縮メモリから検索したバイト（すなわち規定長の語）は、ブロック２０２０においてゼロであると検出されなければ、ブロック２０２１においてルックアップテーブルをアドレスして間隔すなわちビン数“デルタ”を適切なビット位置内の１のビット値が現在バイトの全ての非ゼロビットで表わされる全ての数（測定値）の和と等価であるより高い番号のビンに決定する。ルックアップテーブルは増分されるバイトを指示する“デルタ”アドレスおよび増分されるバイト内のビット数を含んでいる。“アドレス＋デルタ”に表示されるバイト内のビットはブロック２０２２において増分したモジュロ−２増分となりブロック２０２３においてモジュロ−２オーバフローがチェックされる。オーバフローが検出される、すなわちビットがゼロに増分されている、場合には２であったはずのカウント値が２倍の量を表わすより高い番号のビンへの１の増分により置換される。現在ビンから離れたより高い番号のビンはＬＯＧ（２）であり、したがってＬＯＧ（２）はブロック２０２４において“デルタ”に加えられる定数である。ブロック２０２２，２０２３，２０２４からなるリップルキャリーループは、図５に関して前記したように、圧縮メモリ内のＬＯＧ（２）離れたビットが一緒に鎖でつながれて２進語を形成する場合には正規の２進加算と等価である。
【００４９】
バイト内の全ての非ゼロビットの和は時々同じバイト内で単一の１となることがある、すなわちブロック２０２１においてバイトアドレス“デルタ”はゼロでブロック２０２２で増分したビットは同じバイト内のビットとなる。したがって、ブロック２０２２において増分を実施する前にブロック２０２１において現在バイトがゼロにリセットされる。ブロック２０２５において現在バイトがゼロにリセットされたままであれば、それはバイトの内容がより高い番号の（アドレスされた）バイトへ転送されていることを示す。そうではなくて、バイトがゼロでなければ、バイトの内容がバイトを残していて前へ送られることを示す。したがって、ブロック２０２６において、ここに記載されているようにより高い番号の（アドレスされた）バイトで累算しなければならない現在バイト内の残りの１のビットアドレスを示すキャリーフラグがセットされる。ブロック２０２７の操作で全てのバイトが処理されていることが検出されると、所望の対数和を示す圧縮メモリ内の最後の一のビットアドレスで処理が終了される。そうでなければ、ブロック２０２８においてバイトアドレスが増分されブロック２０１９へ戻ってバイト処理が継続される。
【００５０】
図７ａ，図７Ｂ，図８Ａ，図８Ｂにおいて、ＭＡＸＣＯＵＮＴで示す最大ビンのカウント値を超えるとより高い順のビンへのキャリーが実行される。圧縮メモリ内で１の値が増分される場合には、同様により高い番号のビンへのキャリーが行われる。ＭＡＸＣＯＵＮＴが１に等しければ後者は前者と同じである。したがって、図９Ａおよび図９Ｂの操作のフロー図に示すように、ＭＡＸＣＯＵＮＴを１に等しくセットすれば単ビットメモリ内の値のヒストグラムを直接累算することができる。
【００５１】
次に図９Ａおよび図９Ｂについて、実施例の操作はブロック３００１において全ビットをゼロにクリアすることにより開始される。次にブロック３００２において新しい測定値（数）が入力され、それは増分されるメモリ内のビットのアドレスを示す。増分はブロック３００３においてモジュロ−２実施され、例えばメモリ内のＬＯＧ（２）離れたビットを一緒に鎖でつないで２進語を形成することにより、リップルスルーキャリーがブロック３００４で検出されブロック３００５で伝播される。ブロック３００６におい全ての測定値（数）が入力されていることが検出されると、本方法は図８Ａおよび図８Ｂのブロック２０１８からと同様にブロック３００７から継続される。図９Ａおよび図９Ｂにおいて、キャリーフラグの使用についてさらに説明する。
【００５２】
ブロック３００７において第１のバイトで開始すると、ブロック３００８においてその値が検索されブロック３００９においてテストされる。それがゼロであれば、全バイトが処理されているかを検出するブロック３０１７へスキップされる。そうでなければ、処理されるバイトアドレスがブロック３０１８において増分され次のバイトを得るためにブロック３００８へ戻る。バイトが非ゼロであれば、ブロック３０１０における操作で“キャリーフラグ”がセットされているかチェックされる。キャリーフラグは前に処理したバイトが非ゼロ状態のままとされていたかを示す。そうであれば、ブロック３０１９からブロック３０２４は前に処理したバイトの値を現在バイトで累算させる。一実施例では、これらの操作は前に処理したバイトの非ゼロビットを現在バイトの最低非ゼロビットで累算して行われる。
【００５３】
前記したように、丸め効果を最小限に抑えるために対数累算は好ましくは最小値から次に小さい値の順で行われる。したがって、ブロック３０２０において、ビット間隔は非ゼロ値を残す予め処理されたビットと現在バイトの最低非ゼロビットとの間に決定される。このビット位置差はブロック３０２１においてルックアップテーブルに適用されて２つの非ゼロカウント値の和を表わすより高いビットアドレスを得る。ルックアップテーブルから戻されるこのビットアドレスは現在バイトの最低非ゼロビットと同じビットとすることができ（広い間隔のビット値を有する相対値差により丸めによる増加がない）、そのため２つの非ゼロカウント値の和を表わすより高いビットアドレスのビットを増分する前にブロック３０２２において現在バイトの最低非ゼロビットがゼロにリセットされる。ブロック３０２３においてモジュロ−２オーバフローが検出される場合には、ブロック３０２４においてアドレスが決定されるＬＯＧ（２）高いビットへのキャリーが行われる。ＬＯＧ（２）離れたビットが鎖でつながれて２進語を形成する場合にはこれも２進加算と等価である。キャリーが完全に伝播している場合には、現在バイトがゼロであればブロック３００９へ戻ってその点から処理が進められる。
【００５４】
ブロック３０１０においてキャリーフラグがセットされなければ、任意の前のキャリーフラグがブロック３０１９においてリセットされており、バイトの全ての非ゼロビットにより表わされる値がブロック３０１１において照合される。それは例示する実施例において和を表わす増分を受け取るより高い番号のビットのアドレスを与えるルックアップテーブルをアドレスするバイトを使用して行われる。次により高い番号のビットのアドレスにおけるビットはブロック３０１２において増分され、前と同様に通常の２進加算により操作することができるキャリー伝播ループブロック３０１３，３０１４，３０１２により任意のキャリーが処理される。キャリーが完全に伝播されると、ブロック３０１５は現在バイトがゼロであるかどうかをチェックする。ゼロであれば、その全体内容がより高いバイトへ照合されており忘れることができる。そうでなければ、非ゼロビットが処理されるバイト内に残っており、ブロック３０１６においてキャリーフラグがセットされ、非ゼロビットのビットアドレスが保存される。次にブロック３０１７においてさらにバイトを処理すべきか確認され、処理しない場合には、所望の対数和を示す保存されたビットアドレスで処理が終了する。前記した本発明のさまざまな実施例に対する操作は対数（もしくは他の非線形単調）目盛で表わされる多数の値を効率的に累算したい当業者であればさらに修正することができる。
【００５５】
図７Ａ，図７Ｂ，図８Ａ，図８Ｂ，図９Ａ，図９Ｂについて本発明の操作を示すフロー図により本発明を説明してきた。フロー図の各ブロックおよびそれらの組合せはコンピュータプログラム命令により実現できることをお判り願いたい。これらのプログラム命令はプロセッサへ与えて、プロセッサ上で実行する命令がフロー図ブロック内に指定された機能を実現する手段を生成するように、マシンを作り出すことができる。コンピュータプログラム命令はプロセッサが実行して一連の操作ステップを実施しプロセッサで実行する命令がフロー図ブロック内に指定された機能を実現するためのステップを提供するようにコンピュータ実現プロセスを作り出すことができる。
【００５６】
したがって、フロー図のブロックは指定した機能を実施する手段の組合せ、指定した機能を実施するステップの組合せおよび指定した機能を実施するプログラム命令手段をサポートする。また、フロー図の各ブロック、およびその組合せは指定した機能もしくはステップを実施する特殊目的ハードウェアベースシステム、もしくは特殊目的ハードウェアとコンピュータ命令の組合せにより実現できることもお判りであろう。
【００５７】
（符号付き対数数の累算）
前記した本発明の特徴は符号なし数の処理に関連していた。本発明のもう１つの特徴は符号付き対数値の累算に向けられる。本発明の符号付き対数値の累算特徴を理解する背景として、当業者ならば既知のＺｅｃｈ対数について最初に説明する。対数算術に必要な精度が制限されている場合には、Ｚｅｃｈ対数を使用して次のように加減算を実施することができる。
ａ＝ｌｏｇ（Ａ）かつｂ＝ｌｏｇ（Ｂ）で“Ａ”および“Ｂ”の和の対数の値を計算する場合、 ｃ＝ｌｏｇ（Ｃ）を求め、ここにＣ＝Ａ＋Ｂであり、 “ｅ”が関連する対数の底である場合に、
【数２】
ｃ＝ｌｏｇ（Ａ＋Ｂ）＝ｌｏｇ（ｅａ＋ｅｂ）
【００５８】
【数３】
したがって、ｃ＝ａ＋ｌｏｇ（１＋ｅ−（ａ−ｂ））
ａ＞ｂの時に最も有用 ｃ＝ｂ＋ｌｏｇ（１＋ｅ−（ｂ−ａ）） ｂ＞ａの時に最も有用 減算については次式となる
【数４】
ｃ＝ａ−（−ｌｏｇ（１−ｅ−（ａ−ｂ））
あるいは ｃ＝ｂ−（−ｌｏｇ（１−ｅ−（ｂ−ａ））
【００５９】
したがって、所望する答を得るために次の関数を計算する必要がある。
【数５】
ｙ＝Ｚ＋（ｘ）＝ｌｏｇ（１＋ｅ−ｘ）あるいは
ｙ＝Ｚ−（ｘ）＝−ｌｏｇ（１−ｅ−ｘ）ここに、ｘ＝｜ａ−ｂ｜は常に正でありｙは減算に対する負の対数に選択すると常に正とすることができる。
【００６０】
“ｘ”の所要精度が多すぎるビットまで拡張しない限り、これらの関数Ｚ＋（ｘ）およびＺ−（ｘ）はＺｅｃｈ対数であり、“ｘ”の値によりアドレスされる予め計算されたルックアップテーブルを使用して実施することができる。例えば、Ｚｅｃｈ対数を使用して対数加算を実施する（限定精度の通信信号プロセッサの状況で）ことがＤｒ．エヌ．ジー．キングスベリーのＰｈ．Ｄ．ｔｈｅｓｉｓ ａｔ Ｃａｍｂｒｉｄｇｅ Ｕｎｉｖｅｒｓｉｔｙ Ｅｎｇｌａｎｄ，ｃａ １９７０に記載されている。精度の極端なビット数により極端なサイズのルックアップテーブルとなる。現在のメモリ技術水準では、ルックアップテーブルもしくはリードオンリーメモリ（ＲＯＭ）の１６３８４語となる“ｘ”の１６ビット値は極端ではない。このようなＲＯＭはシリコン集積回路上のシリコンエリアを現在１６ｘ１６ビット乗算器よりも多く消費するが、より少ない電力を消費するように設計することができる。消費電力の低減はラップトップコンピュータやセルラー電話機等のバッテリ作動装置において特に望ましい。
【００６１】
本発明の前記した特長は複数の対数表現数（もしくは測定値）の効率的な和分に向けられている。このような和分を実施する必要性は信号強度の平均化等のさまざまな応用において生じることがある。もう１つの例は２つのｎ−次元ベクトル間の点乗積の形成と同じである第１セットの値Ａ１，Ａ２，Ａ３‥‥Ａｎと第２セットの値Ｂ１，Ｂ２，Ｂ３‥‥Ｂｎ間の相関を実施することである。最初に、ＡｉおよびＢｉ等の対応する値が１からｎの範囲の“ｉ”について乗算される。背景の節で前記したように、ＡｉおよびＢｉが対数表現であればこの演算は加算に単純化される。次に‘ｎ’の量Ｃｉ＝Ａｉ．Ｂｉが和分される。しかしながら、これらの値は符号付き量とすることができる。次に説明するように負の量の処理を行う符号付き対数数の累算に向けられた本発明の特徴により和分は有益に行うことができる。
【００６２】
本発明の符号付き累算特徴の最初のステップは発生する全ての異なるＣｉ値のヒストグラムすなわちカウント値を形成することである。負の量を処理するために、各ヒストグラムビンは同じ大きさの負の発生を超える正値の過剰発生を示す負もしくは正のカウント値を保持することを許可される。例えば、符号付き対数値＋１３７が５９回観察され符号付き対数値−１３７が２５回観察される場合には、ビン１３７内のカウント値は５９−２５＝３４となり、負の値は５９の正の値の２５をオフセットし、正の値の正味３４カウント値を残すことを示す。ゼロの正味のカウント値はその値の負の発生数が正の発生数に等しくなったことを示し、互いに完全にオフセットする。したがって、ゼロのカウント値は純粋対数表現では表現されない値である真のゼロを表わす。
【００６３】
カウンタ内の符号付き累算は前記したようにカウンタ内の同じ対数量の発生を累算して実現することができるが、カウンタ（ビン）が増分するか減分するかを決定する符号を使用する。
【００６４】
全てのＣｉ値がカウント値されると、数を使用して多数の１つの値の正味の発生をもう１つの値の単一発生に低減する符号なし数の累算について前記したのと同様にビンのカウント値の低減操作が進行する。前記したように多数の正味正の発生はもう１つのカウンタ（ビン）に適用しなければならない“１”の増分へ低減される。しかしながら、さらに値の多数の正味負の発生はもう１つの選択したカウンタ（ビン）を減分することにより結合される。増分もしくは減分によりビンアンダーフローもしくはオーバフローが生じる場合には、より高い番号のビンをそれぞれ増分もしくは減分するキャリーもしくはボロー（ｂｏｒｒｏｗ）が発生される。低減プロセスの後で、全てのビンが−１，０もしくは＋１のカウント値を含み、したがって、少なくとも２ビットビンでなければならない。−１，０もしくは＋１のカウント値に使用される数表現は多様なプロトコル、例えば、２ビット２進表現
００＝０ ０１＝＋１ １１＝−１もしくは、例えば、下記の表現で提供することができる。
００＝０ 正値も負値も発生しない ０１＝＋１ 正値の発生 １０＝−１
負値の発生 １１＝ 同じ大きさの正値および負値の両方の発生を表わすが、既に互いにオフセットして００を生じているためビットパターン１１は生じてはならない。
【００６５】
本発明の符号付累算特徴のもう１つの実施例では、１セットのビン（カウンタ）が正値発生のヒストグラムを累算するのに使用されもう１セットのビン（カウンタ）が負値発生を累算するのに使用される。各セットのビン内の１もしくは０のカウント値へ別々に低減した後で、正値の単一発生が対応する負値の単一発生のオフセット（キャンセル）を許可される。それは、随意、２セットの低減されたビンを排他的にＯＲし、それらを２進語として処理して、負値も正値も発生しない位置にゼロがありかつ負値および正値が共に発生する位置にもゼロがあるマスクを得ることにより実現することができる。次にマスクは２セットのビンにより論理的にＡＮＤされて反対符号の値をキャンセルする。
【００６６】
符号なし累算と同様に、最高の大きさの前に最低の大きさの順序で値を結合することにより最大精度が得られると予期される。より低い大きさ（すなわち、より低いビン数（アドレス））の負値がより大きい大きさ（すなわち、より高いビン数）の正値と結合されると正値のビン数以下の正値のビン数となる。しかしながら、符号なし値とは対照的に、結果的に得られるビン数はより小さい（負の）値のビン数よりも少なくなることがある。したがって、符号付数を低減する場合、値を結合しても必ずしもビンは低いアドレスから高いアドレスへと空にはされず、非ゼロカウント値を含むビンアドレスの後退拡張となることがある。それでも、このような非常に小さい量は前進的に階段を上る量と結合されると、そのビン数を著しく上下することがないため典型的にプロセスは迅速に収束するものと予期される。したがって、ほぼ等しい正値および負値が結合される時に発生される小さい量は非常に一時的に存在するものと予期される。それでもこれらの値は好ましくは結合の結果結合したいずれの値よりも小さい値となってはならない符号なし値の低減と区別してチェックされる。
【００６７】
本発明の符号付き対数値特徴に対して、前記したＺｅｃｈ対数法が利用される。特に、値の結合に使用されるルックアップテーブルは前記した予め計算されたＺｅｃｈ対数を含んでいる。
【００６８】
（精度を高めた符号付き対数数の加減算）
前記した本発明の特徴は大量の符号付き対数数の累算に向けられているが、それらは主として限定された精度が必要である応用に向けられる。しかしながら、より高い精度でより限定された量の対数値の累算を必要とする応用もある。次に説明する本発明のもう１つの特徴に従って、各々が符号および対数量を有する第１および第２の数を効率的に結合する方法、装置およびコンピュータプログラムプロダクトが提供される。本発明のこの特徴によりより高い精度で対数加減算が実施される。
【００６９】
背景として、対数加算式は次のようである。
【数６】
ｃ＝ｌｏｇ（Ｃ）＝ｌｏｇ（Ａ＋Ｂ）−ｌｏｇ（ｅａ＋ｅｂ）＝ａ＋ｌｏｇ（１ ＋ｅ−（ａ−ｂ））すなわち ＝ｂ＋ｌｏｇ（１＋ｅ−（ｂ−ａ））すなわち ＝（ａ＋ｂ）／２＋ｌｏｇｃｏｓｈ（｜ａ−ｂ｜／２）＋ ｌｏｇ（２）
【００７０】
各式は好ましくは、それぞれ、ａ＞ｂ，ｂ＞ａかつａおよびｂがほぼ等しい場合に利用される。
【００７１】
拡張精度算術では、例えばａおよびｂの値がデジタル値で表現される場合には、ａおよびｂはより長い語長ビットを有する。加算が依存する関数ｘ＝｜ａ−ｂ｜は最上位部ｘ１および最下位部ｘ２を有するものとしてさらに処理することができる。関数ｘがｘ１およびｘ２部を有するものとして処理される場合には、符号および対数量を有する２つの量の加算はｌｏｇ（１＋ｅ−（ｘ１，ｘ２））等の計算項を含むものとして表現することができ（ｘ１，ｘ２）はｘ２と連接したｘ１を意味する。
【００７２】
符号および量として表現される数の処理において多様な精度範囲が所望されることがあるが、典型的な例は１ビット符号および３１ビット対数量からなる３２ビット数としてａおよびｂを与える。例えば、共通浮動小数点表現は符号、８ビット指数部および２４ビット仮数部を含み最上位ビットが常に１となるまで左シフトすることによりそれらは２３ビットへ低減することができる（１は次にドロップされ内包される）。この浮動小数点フォーマットに対する指数範囲は２の＋１２７乗から２の−１２８乗であり、１０−３８から１０＋３８の大きさを有する数を表現することができる。
【００７３】
大きさのこの同じ範囲を“ｅ”の＋８８乗と−８８乗の間で表現することができる。したがって、数の浮動小数点表現は１０−２７から１０＋２７の幾分小さい範囲を表わす底“ｅ”の対数に対する７ビット整数部を使用して与えることができる。あるいは、典型的な浮動小数点のように８ビット整数部を使用して１０−５５から１０＋５５のより大きい範囲を表わすことができる。後者が選択される場合は、対数の２３ビット小数部を同じ３２ビット語長内に入れることができる。最下位ビットは２の−２４乗を表わすようになる。したがって、ｄ（ｌｏｇ（ｘ））＝２−２４＝ｄｘ／ｘとなる。“ｘ”の値は２−２４すなわち、およそ、１６，０００，０００分の１の一定の小数精度で表わされる。
【００７４】
したがって、表現のこのフォーマットにより、この因子（すなわち、大きい方は小さい方の値のおよそ１６，０００，０００倍）以上異なる２つの量は加減算され、より大きい量の最下位ビットはなんら変化しない。２つの量はその底“ｅ”の対数がおよそ１６よりも異なる場合には１６，０００，０００倍よりもさらに異なる。したがって、ｘ＝｜ａ−ｂ｜が１６よりも大きければ、加減算を実施する必要はなく結果は単にａもしくはｂ（関連する符号ビットと共に）の大きい方となる。
【００７５】
対数値の表示の精度からのこの制限を適用して本発明は２つの値を比較的高い精度で効率的に結合することができる。特に、本発明に従って、およそ１６よりも小さい、すなわち小数点の左に４ビットもしくはせいぜい５ビットしかない、ｘの最上位部（前記したようにａおよびｂ間の差を表わす）であるｘ１の値だけが考慮される。本発明の高精度結合特徴の実施例では、点の右側に２３ビットがある（前記した小数部）。したがって、（ｘ１，ｘ２）はせいぜい最上位２８ビット（すなわち考慮されるビット）しかない。好ましくは２８ビットはｘ１およびｘ２間に分割され、ｘ１は形式ｘｘｘｘｘ．ｘｘｘｘｘｘｘｘｘ（小数点の左に５ビットがある）の１４ビット最上位部とされｘ２は最下位１４ビット部とされる。
【００７６】
前記したＺｅｃｈ対数Ｚ＋（ｘ）およびＺ−（ｘ）はこの場合次のように表わされる。
【数７】
Ｚ＋（ｘ）＝Ｚ＋（ｘ１，ｘ２）＝Ｚ＋（ｘ１＋）＋Ｚ＋（ｘ’） ｝．．．（１）ここに ｘ’＝ｘ＋Ｚ＋（ｘ１＋）＋Ｚ−（ｘ２）式（１）および下記に示すように、ｘ１＋はｘ１が１最下位ビット（ＬＳＢ）増分したことを意味しｘ２はｘ２の１の補数、すなわち（１０００００００００００００−ｘ２）を意味する。
【００７７】
さらに
【数８】
Ｚ−（ｘ）＝Ｚ−（ｘ１，ｘ２）＝Ｚ−（ｘ１＋）＋Ｚ−（ｘ’） ｝．．．（２）ここに ｘ’＝ｘ−Ｚ−（ｘ１＋）＋Ｚ−（ｘ２）
【００７８】
最上位部および最上位部を使用してＺｅｃｈ対数式の別々の成分を定義することは同様に最上位部ｘ１’および最下位部ｘ２’を有するものとしてＸ’を表現することにより反復することができる。Ｚｅｃｈ，Ｚ±（ｘ’）は同様にｘ”等に関して拡張することができる。それは次のように式（１）および（２）へ代入して数学的に表現することができる。
【数９】
Ｚ＋（ｘ）＝Ｚ＋（ｘ１，ｘ２）＝Ｚ＋（ｘ１＋）＋Ｚ＋（ｘ１’＋） ＋Ｚ＋（ｘ１”＋） ｝．．．（３） Ｚ−（ｘ）＝Ｚ−（ｘ１，ｘ２）＝Ｚ−（ｘ１＋）＋Ｚ−（ｘ１’＋） ＋Ｚ−（ｘ１”＋） ｝．．．（４）
【００７９】
したがって、式（３）および（４）におけるｘ１，ｘ１’，ｘ１”等の値は少なくともＺ−（ｘ２），Ｚ−（ｘ２’）等の値だけ連続的に大きくなりそれらは少なくとも−ｌｏｇｅ（２−９）であり６に等しい。したがって、級数の３項の後で、残りは元のｘ値よりもおよそ１８（６の３倍）大きいｘの値のＺｅｃｈ対数となる。したがって、整数部は１６よりも大きく、それは前記したように、２つの数の結合結果の最下位ビットに影響を及ぼしてはならない。すなわち実施例の精度について、式（３）および（４）は３項の後で実施例の３２ビット語長まで正確な結果に収束する。
【００８０】
前記したように、２つの数の結合を実施する演算の実行は関数Ｚ±（ｘ１＋）およびＺ−（ｘ２）を利用する。これらの関数は好ましくは予め計算されてルックアップテーブルに格納される。ｘ１およびｘ２が１４ビット量である実施例では、１６３８４語サイズのルックアップテーブルとなる。
【００８１】
次に図１０および図１１に関して、本発明の符号付き対数数の高精度結合特徴に従った装置の実施例および装置の動作について説明する。図１０の実施例はｘ１およびｘ２が１４ビット量として表現される前記した例のフォーマットに従って示されている。したがって、図１０に示す第１のテーブル（Ｔ１）４００３、すなわち他の記憶手段、は拡張ｘ１値のＺ＋およびＺ−の両方の値を含む３２７６８語ルックアップテーブルである。第２のテーブル（Ｔ２）４００４、すなわち他の記憶手段、はＺ−（ｘ２）に対する値を含む１６３８４語テーブルである。テーブル４００３および４００４は本発明の対数数結合演算を実施するコンピュータ上のメモリの割当てブロックとして実現することができる。
【００８２】
図１０に示すように、結合すべき数は加減算される入力量（数）を受け入れる３２ビットバスである入力バス４００１を介して装置へ入力される。“ａ”と呼ばれる第１の数が入力バス４００１に加えられタイミング論理４００８へ開始信号が与えられて動作を開始する。タイミング論理４００８は入力アキュムレータ４００２へロード信号を送り次にそれは入力バス４００１からの第１の数“ａ”を入力アキュムレータ４００２へロードする。タイミング論理４００８はさらに出力アキュムレータ４００７へロード信号を与え次にそれは入力バス４００１からの第１の数“ａ”を出力アキュムレータ４００７へロードする。アキュムレータ４００２，４００７のローディング操作については図１１のブロック５００１のフロー図でさらに説明する。
【００８３】
次に“ｂ”と呼ばれる第２の加減数が入力バス４００１に加えられる。タイミング論理４００８が第２のロードパルスを入力アキュムレータ４００２へ送って既にロードされている数“ａ”から第２の数“ｂ”を減じる。当業者ならば予めロードされている数から第２の数を減じるアキュムレータはお判りであろう。当業者ならばお判りのように、本発明で使用するのに適したアキュムレータは入力バスに加わる値は減算するが帰還バスに加わる値は加算するように提供することができる。図１０の実施例に示すように、この減算は３１ビット対数部の減算である。“ａ”および“ｂ”の別々の符号ビットが排他的オアされて“ａ”および“ｂ”により表わされる量が同じ符号であるか異なる符号であるか確認される。符号が異なる場合には、入力アキュムレータ４００２は加減算バス４０１０を介して“減算”信号を出力する。加減算バス４０１０は第１のテーブル４００３に接続されていてその第１５番アドレスを与える。加減算バス４０１０はさらに加算器／減算器回路４００５に接続されていて“ａ”および“ｂ”が異なる符号である時に減算する表示を加算器／減算器回路４００５に与える。“ａ”および“ｂ”が同じ符号である時は、入力アキュムレータ４００２は加減算バス４０１０を介して“加算”信号を出力する。信号結合操作は図１１のフロー図のブロック図５００２に示されている。入力アキュムレータ４００２内に予めロードされている第１の数から第２の数を減算して結果を入力アキュムレータ４００２内に配置する入力アキュムレータ４００２の操作を図１１のフロー図のブロック図５００３に示す。
【００８４】
“ｂ”と結合される数“ａ”の対数量よりも大きい対数量を有する数“ｂ”については、前記したように、各３１ビット対数部の減算により負の値が得られる。すなわち、数“ａ”および“ｂ”の対数量部の絶対値については、“ｂ”はより大きい量を表わしていた。この状態はどの停止／より大きい検出器４００６がタイミング論理４００８に信号を与えるかに応答する停止／より大きい検出器４００６により検出される。第１および第２の数の対数量を比較する図１０の装置の動作は図１１のブロック５００４に示されている。より大きい値を表わす“ｂ”の表示に応答するタイミング論理４００８は出力アキュムレータ４００７へ第２のロードパルスを送って図１１のブロック５００５にさらに示すように“ｂ”の値を出力アキュムレータ４００７へロードする（“ａ”の元の値をオーバライトする）。したがって、出力アキュムレータ４００７はブロック５００５の操作の後でその各符号ビットを含むより大きい量を有する値“ａ”もしくは“ｂ”を含んでいる。
【００８５】
さらに、入力アキュムレータ４００２が第２の入力値“ｂ”を減算した後で負となる（すなわち、“ｂ”がより大きい量を有する）場合には、入力アキュムレータ４００２はその内容の補数、すなわち、モジュラス｜ａ−ｂ｜を出力する。モジュラス｜ａ−ｂ｜が閾値（全体精度に関連しており、前記したように３２ビットの実施例では１６−１８の範囲）よりも大きければ、停止／より大きい検出器４００６はタイミング論理４００８に停止信号を与える。入力アキュムレータ４００２の最上位ビットが停止／より大きい検出器４００６へ与えられて停止／より大きい検出器４００６は所定の閾値よりも大きいモジュラスを検出することができる。停止信号に応答して、タイミング論理８は計算を停止させ、例えば結合される数を与える外部コンピュータ（図示せず）へ、結合操作は完了である表示を与える。この点において、出力バス４００９を介して外部コンピュータにアクセスできる出力レジスタ４００７内に所望の答が含まれている。前記したように、数を表現するために選択した語サイズの精度限界が与えられると結合操作により大きい値に匹敵する結果を生じるため、量間の差異が大きすぎると（所定の閾値を越える）操作は停止される。閾値を超えたことを検出する操作は図１１のブロック５００６に示されている。
【００８６】
あるいは、｜ａ−ｂ｜がまだ精度閾値よりも大きくなければ、入力アキュムレータ４００２の最下位１４ビット（ｘ２を含む）が第２のテーブル４００４をアドレスしてその中に格納された値Ｚ−（ｘ２）を得るために与えられる。次の最上位１４ビット（ｘ１を含む）は値Ｚ＋（ｘ１＋）もしくはＺ−（ｘ１＋）を得るために第１のテーブル４００３へ加えられる。各加算もしくは減算Ｚ値に対する値は、最上位アドレスビットとして第１のテーブル４００３へ与えられる、加減算出力４０１０からの信号が加算を示すか減算を示すかに従って検索される。実施例におけるｘ１の拡張値のＺ＋の値はいかなる場合もｌｏｇｅ（２）＝０．６９よりも小さく、したがって２３ビット小数部しか与えられない。しかしながら、Ｚ−の値はｘ１がゼロであれば−ｌｏｇｅ（２−９）の最大となることがある。したがって、２６ビット出力は第１のテーブル４００３から与えられる。Ｚ値を得る操作を図１１のブロック５００７に示す。
【００８７】
第２のテーブル４００４が選択した精度閾値（すなわち、実施例では１６から１８）よりも大きい値（ｘ２）を出力する時は、出力アキュムレータ４００７に既に格納されている値を変えるためにさらに反復することは予期されない。したがって、第２のテーブル４００４は３１のすぐ下の、すなわち、５ビット部を有する出力値を小数点の左に与えるように構成することができる。加算器／減算器４００５はテーブル４００３，４００４からの出力値を結合する手段を提供する。テーブル４００３，４００４からの出力値を結合した結果が所定の精度閾値よりも大きいことを検出すると、加算器／減算器４００５は停止検出器４００６に作動的に接続されるオーバフローインジケータをセットする。加算器／減算器４００５からのオーバフロー表示に応答して、加算器／減算器４００５は検出器４００６を停止するために停止信号をタイミング論理４００８へ与えて所望の精度に達していることを表示する。オーバフロー検出操作は図１１のブロック５００８に示されている。
【００８８】
オーバフローが検出されない場合には、加算器／減算器４００５の出力（２８ビット長以下）は入力アキュムレータ４００２へ戻される。図１１のブロック５００９に示すように、加算器／減算器はテーブル４００３，４００４からの出力値を結合して精度閾値を超えていない場合には繰返し入力アキュムレータ４００２へ戻す。実施例では、出力が２８ビット長よりも短くオーバフローは検出されないかのように２８ビット長が加えられる。２８ビット長よりも長ければ、オーバフローが検出されていることがある。図１１のブロック５０１０に示すように、タイミング論理４００８は“加算”パルスを発生しそれに応答して入力アキュムレータ４００２はその中に含まれている前の値を加算器／減算器４００５からの出力に累算する（したがって、一連の値ｘ’，ｘ”，．．．の中の１つを発生する）。また図１１のブロック５０１１に示すように、タイミング論理４００８は“加算”パルスを出力アキュムレータ４００７へ送って第１のテーブル４００３からの値すなわちＺ±（ｘ１）に出力アキュムレータ４００７の前の内容を累算する。
【００８９】
図１０および図１１について前記したように、式（３）もしくは（４）に利用された一連の値の反復について操作を詳しく説明した。全ての項の計算を所望の精度レベルまで完成するために、図１１のブロック５０１１からブロック５００６へのリターンに示すように、操作は出力アキュムレータ４００７内で式（３）もしくは（４）の項を累算するために継続される。３２ビット精度の実施例に対して精度閾値は３サイクル内に得られるものと予期される。したがって、本発明を実施する時は、３２ビット高精度対数加減算をおよそ４論理クロックサイクル毎に実施することができる。
【００９０】
本発明に従って符号付き対数数に精度改善演算を実施することは同様な精度の浮動小数点加算器と同等以下の複雑さである。しかしながら、本発明では乗算、除算、二乗および平方根を対数表現する利点が得られる。さらに、これらの演算は浮動小数点の演算よりも複雑さが著しく少なく各論理クロックサイクル毎に実施することができる。
【００９１】
さらに、本発明の装置、方法およびプログラムプロダクトによりコンピュータ等の処理システムで乗算および加算を同時に処理することができる。それは新しい加減算を開始する前に、アキュムレータ４００２，４００７をリセットするのではなく第３の対数値“ｃ”にセットすることにより遂行される。したがって、第１の数“ａ”が入力されると、それは“ｃ”に加えられてＡおよびＢの積を形成する。しかしながら、前記したように操作が継続して結果は、“乗算−累算”すなわちＭＡＣ演算と呼ばれる、ＡＣ±Ｂの対数となる。当業者ならば前記した技術の他の明確なバリエーションを作り出すことができるであろう。例えば、図１０に示す装置は“バタフライ演算”として知られる和および差の同時計算に利用することができる。もう１つの応用は同時ＭＡＣ回路を使用して２つの複素数の積を計算することであり、このバリエーションはさまざまな応用に有用である。
【００９２】
対数算術を実施するためにＺｅｃｈ対数を再帰的に計算する本発明は値のＺｅｃｈ対数を最上位部のＺｅｃｈ対数により大きい値のＺｅｃｈ対数をプラスしただけの表現で表わす式（１）および（２）の再帰的形式に基づいている。より大きい値のＺｅｃｈ対数は連続的に小さくなるものと予期され、したがってより有効ではないため、対数加減算を実施するための迅速に収束する再帰型マシンを構成することができる。
【００９３】
図１０および図１０について説明した実施例はＺｅｃｈ対数の引数“ｘ”の最上位部および最下位部への分割に基づいていたが、“ｘ”をさらに分割しても本発明の利益が得られることをお判り願いたい。例えば、“ｘ”を３つ以上の部分へ分割することができ加算した成分に対して付加ルックアップテーブルを利用することができる。“ｘ’が３つ以上の部分に分割される場合には、ｘからのｘ’もしくはｘ’からのｘ”の計算も再帰的プロセスであることが判る。あるいは、再帰的計算の場合には当業者ならばご存知のようにアキュムレータ４００２，４００７の替わりにスタックを使用して図１０に示すものと同様なハードウェアによりこれらの計算を実施することができる。より大きい数を使用して“ｘ”を分割すると装置の複雑さは増すがルックアップテーブルのサイズを低減することができる。それは所望の精度を達成しようとするとメモリチップ技術により経済的に提供できるよりも大きいテーブルサイズとなってしまう場合に有利である。
【００９４】
本発明をその動作を示す図１１のフロー図について説明してきた。フロー図の各ブロックおよびその組合せはコンピュータプログラム命令により実現できることをお判り願いたい。プロセッサ上で実行する命令がフロー図ブロックに指定された機能を実現する手段を生成するように、これらのプログラム命令をプロセッサに与えてマシンを作り出すことができる。コンピュータプログラム命令はプロセッサで実行して一連の操作ステップを実施させプロセッサで実行する命令がフロー図ブロックに指定された機能を実現するステップを提供するようにコンピュータ実行プロセスを作り出すことができる。
【００９５】
また当業者ならば、図１０の本発明の前記した特徴はハードウェア、ソフトウェア、もしくはその組合せにより提供できることがお判りであろう。本発明の装置のさまざまな構成要素を図１０に一部個別要素として図示したが、実際上は入出力ポートおよび実行ソフトウェアコードを含むマイクロコントローラ（プロセッサ）、カスタムもしくはハイブリッドチップ、個別構成要素もしくはその組合せにより実現することができる。
【００９６】
図面および明細書に、本発明の典型的な好ましい実施例を開示し、特定の用語が利用されたが、包括的かつ説明的感覚でのみ使用され限定的意味合いはなく、発明の範囲は特許請求の範囲に記載される。
【図面の簡単な説明】
【図１】 本発明に使用する信号受信装置を示すブロック図である。
【図２】 本発明の実施例に従って得られる複数の信号強度測定のグラフである。
【図３】 図２に示す複数の信号強度測定の処理を示すグラフである。
【図４】 本発明に従った装置の実施例を示す略図である。
【図５】 本発明に従った装置のもう１つの実施例を示す略図である。
【図６Ａ】 本発明の実施例に従ったプロセッサアーキテクチュアの略ブロック図である。
【図６Ｂ】 本発明のもう１つの実施例に従ったプロセッサアーキテクチュアの略ブロック図である。
【図６Ｃ】 本発明のさらにもう１つの実施例に従ったプロセッサアーキテクチュアの略ブロック図である。
【図７】 図７Ａと図７Ｂ間の関係を示す略図である。
【図７Ａ】 本発明の実施例に従った操作を示すフロー図である。
【図７Ｂ】 本発明の実施例に従った操作を示すフロー図である。
【図８】図８Ａと図８Ｂ間の関係を示す略図である。
【図８Ａ】 本発明のもう１つの実施例に従った操作を示すフロー図である。
【図８Ｂ】 本発明のもう１つの実施例に従った操作を示すフロー図である。
【図９】図９Ａと図９Ｂ間の関係を示す略図である。
【図９Ａ】 本発明のさらにもう１つの実施例に従った操作を示すフロー図である。
【図９Ｂ】 本発明のさらにもう１つの実施例に従った操作を示すフロー図である。
【図１０】 本発明の符号付き対数アキュムレータの実施例に従ったプロセッサアーキテクチュアの略ブロック図。
【図１１】 本発明の符号付き対数アキュムレータの実施例に従った操作を示すフロー図。
【図１】
0004302880.tif 000002
【図２】
0004302880.tif 000003
【図３】
0004302880.tif 000004
【図４】
0004302880.tif 000005
【図５】
0004302880.tif 000006
【図６Ａ】
0004302880.tif 000007
【図６Ｂ】
0004302880.tif 000008
【図６Ｃ】
0004302880.tif 000009
【図７】
0004302880.tif 000010
【図７Ａ】
0004302880.tif 000011
【図７Ｂ】
0004302880.tif 000012
【図８】
0004302880.tif 000013
【図８Ａ】
0004302880.tif 000014
【図８Ｂ】
0004302880.tif 000015
【図９】
0004302880.tif 000016
【図９Ａ】
0004302880.tif 000017
【図９Ｂ】
0004302880.tif 000018
【図１０】
0004302880.tif 000019
【図１１】
0004302880.tif 000020