(57)【特許請求の範囲】
【請求項１】
Ｎビットを有する符号化された信号ブロックの伝送の間に生じる誤りを検出しかつ訂正するための、ワイアレス通信システムにより使用される複数の従属接続された変換段を有する高速アダマール変換装置において、
前記変換段への入力としてＮ／２個の信号対を受信するように構成された、出力端子を有する加算器および出力端子を有する減算器と、
前記加算器からの前記中間係数の第１の区別可能なシーケンスおよび前記減算器からの中間係数の第２の区別可能なシーケンスのうちの１つを選択的に受信する第１のメモリユニットと、
前記減算器から前記中間係数の第３の区別可能なシーケンスを受信する第２のメモリユニットと、
前記第１のメモリユニットの出力および前記中間係数の第２の区別可能なシーケンスのうちの１つを前記変換段の第１の出力として供給するとともに、前記第１のメモリユニットの出力および前記中間係数の第１の区別可能なシーケンスのうちの1つを前記変換段の第２の出力として供給する出力段と、
を備えることを特徴とする高速アダマール変換装置。
【請求項２】
前記加算器および減算器の前記出力端子に結合されかつ前記第１のメモリユニットに結合された第１のマルチプレクサをさらに含み、前記第１のマルチプレクサは、前記第１のメモリユニットにより受信されるべき前記第１および第２の区別可能なシーケンスのうちの１つを選択するように構成されることを特徴とする請求項１記載の装置。
【請求項３】
前記出力段が、さらに前記加算器および第１のメモリユニットの出力端子に結合された第２のマルチプレクサと、であって、前記第１のメモリユニットの出力および前記中間係数の第１の区別可能なシーケンスのうちの１つを、前記変換段の第２の出力として選択するよう構成された第２のマルチプレクサと、前記第１および第２のメモリユニットの出力端子に結合された第３のマルチプレクサであって、前記第１のメモリユニットの出力および前記中間係数の第２の区別可能なシーケンスのうちの１つを、第１の出力として選択するよう構成された第３のマルチプレクサとを備えることを特徴とする請求項１記載の装置。
【請求項４】
入力信号の連続的な対が前記ＦＨＴ装置により受信されるようにするためのクロック手段をさらに含むことを特徴とする請求項１記載の装置。
【請求項５】
前記クロック手段が、複数のビットを有するクロックカウンタ信号を生成し、前記複数のビットの各々が、前記高速アダマール変換装置の変換段により受信さ
れる信号に対応するものであることを特徴とする請求項４記載の装置。
【請求項６】
前記変換段の各々により受信される前記クロックカウンタ信号が、前記第２のメモリユニットを交番的にイネーブルしかつディスエーブルし、中間係数の前記第１または第２の区別可能なシーケンスのどちらが前記第１のメモリユニットにより受信されるかを決定することを特徴とする請求項５記載の装置。
【請求項７】
最終の変換段に結合されたコンパレータをさらに含み、前記コンパレータは、前記最終の変換段から受信される第１および第２の出力の各々の大きい方の信号を受信して格納するように構成されることを特徴とする請求項１記載の装置。
【請求項８】
最終の変換段において、前記第１および第２の出力がＮ個の正当な符号化信号ブロックのうちの１つに対応することを特徴とする請求項１記載の装置。
【請求項９】
最大の値を有する前記クロックカウンタ信号が、前記ワイアレスシステムにより送信された符号化された信号ブロックに対応することを特徴とする請求項５記載の装置。
【請求項１０】
前記Ｎ／２個の信号対が符号化された信号ブロック内にあり、前記符号化された信号ブロックが、ウォルシュコードワードであることを特徴とする請求項１記載の装置。
【請求項１１】
複数の従属接続された変換段を有する高速アダマール変換装置を使用する通信受信機により受信されるＮビット信号ブロックを復調するための方法において、
各変換段に対して、該変換段に入力されるＮ／２個の信号対を加算しおよび減算するステップと、
前記加算するステップから中間係数の第１の区別可能なシーケンスおよび前記減算するステップからの中間係数の第２の区別可能なシーケンスを、選択的に受信して、第１のメモリユニットに格納するステップと、
前記減算器からの前記中間係数の第３の区別可能なシーケンスを受信して、第２のメモリユニットに格納するステップと、
前記第１のメモリユニットの出力および前記中間係数の第２の区別可能なシーケンスのうちの１つを、前記変換段の第１の出力として供給するとともに、前記第１のメモリユニットの出力および前記中間係数の第１の区別可能なシーケンスのうちの１つを前記変換段の第２の出力として供給するステップと、
を含むことを特徴とする方法。
【請求項１２】
複数のクロックカウンタ信号を生成するステップをさらに含み、前記クロックカウンタ信号の各々が、後続の変換段に対応するものであることを特徴とする請求項１１記載の方法。
【請求項１３】
前記生成されたクロックカウンタ信号で、前記第１および第２のメモリユニットを交番的にイネーブルしおよびディスエーブルするステップと、前記中間信号対の第１または第２の区別可能なシーケンスのどちらが前記第１のメモリユニットにより受信されるかを決定するステップとをさらに含む
ことを特徴とする請求項１２記載の方法。
【請求項１４】
前記第１のメモリユニットおよび前記加算するステップからの複数の中間係数信号対を後続の変換段に提供するステップと、前記第１および第２のメモリユニットからの複数の中間係数信号対を前記後続の変換段に提供するステップとの間の交番させるステップをさらに含むことを特徴とする請求項１３記載の方法。
【請求項１５】
最終の変換段の後で、前記最終の変換段から受信された前記第１および第２の出力を比較し、前記出力の大きい方を格納するステップをさらに含むことを特徴とする請求項１１記載の方法。
【請求項１６】
Ｎビットを有する符号化された信号ブロックの伝送の間に生じる誤りを検出しかつ訂正するための、にワイアレス通信システムにより使用される複数の従属接続された変換段を有する高速アダマール変換装置において、
前記装置中の１つの変換段は、
前記変換段への入力としてのＮ／２個の信号対を受信するように構成された、出力端子を有する加算器および出力端子を有する減算器と、
前記加算器からの中間係数の第１の区別可能なシーケンスおよび前記減算器からの中間係数の第２の区別可能なシーケンスのうちの１つを選択的に受信する第１のメモリユニットと、
前記減算器からの中間係数の第３の区別可能なシーケンスを受信する第２のメモリユニットと、
前記第１のメモリユニットの出力および前記中間係数の第２の区別可能なシーケンスのうちの１つを前記変換段の第１の出力として供給するとともに、前記第１のメモリユニットの出力および前記中間係数の第１の区別可能なシーケンスのうちの１つを前記変換段の第２の出力として供給する出力段と、
を備えることを特徴とする高速アダマール変換段。
【請求項１７】
前記加算器および減算器の出力端子および前記第１のメモリユニットに結合されており、前記第１のメモリユニットのより受信されるべき前記第１および第２の区別可能なシーケンスのうちの１つを選択するように構成された第１のマルチプレクサ（１１４）をさらに含むことを特徴とする請求項１６記載の高速アダマール変換段。
【請求項１８】
前記出力段がさらに、前記加算器の出力端子および第１のメモリユニットに結合され、該第１のメモリユニットの出力および前期中間係数の第１の区別可能なシーケンスのうちの１つを、前記変換段の第２の出力として選択するよう構成された第２のマルチプレクサ（１２２）と、前記第１および第２のメモリユニットの出力端子に結合され、前記第１のメモリユニットの出力および前記中間係数の第２の区別可能なシーケンスのうちの１つを、第１の出力として選択するよう構成された第３のマルチプレクサ（１２０）とを含むことを特徴とする請求項１６記載の高速アダマール変換段。
【請求項１９】
入力信号の連続する対が前記ＦＨＴ装置により受信されるようにさせるためのクロック手段を含むことを特徴とする請求項１６記載の高速アダマール変換段。
【請求項２０】
前記クロック手段が、複数のビットを有するクロックカウンタ信号を生成し、前記複数のビットの各々が、前記高速アダマール変換装置の変換段により受信される信号に対応することを特徴とする請求項１８記載の高速アダマール変換段。
【請求項２１】
前記変換段の各々により受信される前記クロックカウンタ信号が、前記第２のメモリユニットを交番的にイネーブルしおよびディスエーブルし、前記中間係数の第１または第２の区別可能なシーケンスのうちのどちらが前記第１のメモリユニットにより受信されるかを決定することを特徴とする請求項２０記載の高速アダマール変換段。
【請求項２２】
最終の変換段において、前記第１および第２の出力が、Ｎ個の正当な符号化信号ブロックのうちの１つに対応することを特徴とする請求項１６記載の高速アダマール変換段。
【請求項２３】
最大の値を有する前記クロックカウンタ信号が、前記ワイアレスシステムにより送信された符号化信号ブロックに対応することを特徴とする請求項２０記載の高速アダマール変換段。
【請求項２４】
Ｎ／２個の信号対が、符号化信号ブロック内にあり、前記符号化信号ブロックがウォルシュコードワードであることを特徴とする請求項１６記載の高速アダマール変換段。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ワイアレス通信に係り、特に、ウォルシュ（Walsh）コードワードの送信の間に生じる誤りを検出しかつ訂正するために使用される高速アダマール変換構成に関する。
【０００２】
【従来の技術】
図１は、典型的なワイアレス通信システムを示す。交換機センタ２０１は、複数の基地局２０３−１ないし２０３−５に接続されている。また、交換機センタ２０１は、図示しないローカルまたは長距離電話局にも接続されている。ワイアレス端末２０１−１ないし２０１−３は、同じ所定の地理的領域、即ちセル中に配置された基地局と通信する。例えば、ワイアレス端末２０１−１および２０１−２は、セルＡ中に配置されており、セルＡ中に配置されこれをサービスする基地局２０３−１と通信する。
【０００３】
ワイアレス端末２０１−１が通信するために、これは、無線波により信号を基地局２０３−１に送り、基地局２０３−１は、受信した信号を交換機センタ２０１に中継し、信号の一部として供給される指示に従って、交換機センタ２０１は、その信号をどこかに中継する。その信号の所望の宛先が別のワイアレス端末である場合、交換機センタ２０１は、その信号を受信することを意図されたワイアレス端末と同じセル中に配置された基地局にその信号を中継し、基地局は、そのワイアレス端末に無線波により信号を送信する。同様に、その信号の所望の宛先が、ワイアライン端末２０７のようなワイアライン端末である場合、交換機センタ２０１は、その所望の宛先への信号をワイアラインを介してローカルまたは長距離ネットワークに中継する。
【０００４】
情報がデジタルワイアレス通信チャネルを介して送信される場合、雑音、妨害および歪みにより誤りが生じうる。伝送中に生じる誤りを検出しかつ訂正するために様々な方法が使用される。図２は、伝送誤りを検出および訂正するためにデジタルワイアレス通信チャネルにより典型的に使用されるいくつかの構成要素を示す。情報ソース（源）１２は、デジタルメッセージをエンコーダ１４に送信する。デジタルメッセージは、デジタル化された音声信号、データなどから成りうる。
【０００５】
エンコーダ１４は、デジタルメッセージを符号化し、これを送信機１６に供給する。送信機１６は、符号化されたメッセージを搬送波に変調し、これを無線波により受信機１８に送信する。受信機１８は、メッセージを受信する。このメッセージは伝送の間に転化しているかあるいは転化していないことがある。受信機１８は、受信されたメッセージを復調し、これをデコーダ２０に与える。デコーダ２０は、受信されたメッセージを複合化し、これを情報宛先２２に供給する。好ましくは、情報宛先２２に供給されるデジタルメッセージは、情報ソース１２により送信された元のデジタルメッセージと同一である。
【０００６】
情報宛先２２が情報ソース１２により送信された同じメッセージを受信するために、エンコーダ１４およびデコーダ２０は、伝送中の転化による誤りを検出および訂正するように動作する。一般に、エンコーダ１４は、デジタルメッセージ信号を固定長のブロックに分割し、各ブロックをそれに固有に関連づけられたコードワードで置き換える。コードワードは、固定長ブロックの代わりに送信され、受信されたメッセージは、伝送中に転化したかどうかを決定するために、既知のセットの正当なコードワードと比較される。そのような誤り検出／訂正スキームの１つは、ウォルシュ符号の生成および送信に関わる。
【０００７】
ウォルシュ符号システムに従って、エンコーダ１４は、情報ソース１２からのメッセージを各々ｎビットを有するブロックに分割する。送信されるべき元のｎビットの情報のブロックの各々は、２nのウォルシュチップを有する情報のブロックに対して固有のコードワードに変換される。したがって、３ビットのデータブロックは、２3即ち８個のウォルシュチップを伴うウォルシュコードワードを有することになる。元の３ビットのデータのブロックを変調および送信する代わりに、送信機１６は、ウォルシュコードワードを変調しかつ受信機１８に送信する。
【０００８】
ウォルシュコードワードが受信機１８により受信されるとき、これは復調されてかつデコーダ２０に供給される。デコーダ２０は伝送中に転化した可能性がある受信されたウォルシュコードワードを正当なウォルシュコードワードのセットと比較する。受信されたウォルシュコードワードが正当なウォルシュコードワードのセット中のコードワードのうちの１つに一致する場合、受信されたコードワードは伝送中に転化しなかったと推定されて、もともと送信を意図された３ビットの情報のブロックに復号化して戻されうる。
【０００９】
しかし、受信されたウォルシュコードワードが正当なウォルシュコードワードのセット中のコードワードのうちの１つに一致しない場合、受信されたコードワードは、伝送中に転化しており、受信機はどの正当なウォルシュコードワードがもともと送信されたかを決定しなければならない。従来技術において、高速アダマール変換（以下“ＦＨＴ”という）アルゴリズムが、受信されたコードワードの各々に対して、受信されたコードワードが特定の正当なウォルシュコードワードである可能性を計算するために使用される。ＦＨＴアルゴリズムは、この可能性を相関係数として表現する。
【００１０】
したがって、受信されたコードワードは、それに関連づけられた２n個の相関係数を有し、その１つが２n個の正当なウォルシュコードワードの各々に対応する。最大の相関係数を有する正当なウォルシュコードワードが、送信された最も可能性の高い正当なコードワードである。したがって、ＦＨＴアルゴリズムは、受信されたコードワードに最大の相関係数を有する正当なウォルシュコードワードを割当てる。「勝った(winning)」ウォルシュコードワードは、３ビットの情報のブロックに復号化されて戻され、そして情報宛先２２へ供給される。
【００１１】
【発明が解決しようとする課題】
高速アダマール変換を具現化するための多くの技法が従来技術において知られているが、これらの技法は非常に遅くかつ非常に多くのハードウェアを必要とする。したがって、高速、コンパクトかつ有効なＦＨＴエンジンに対するニーズが存在する。
【００１２】
【課題を解決するための手段】
本発明は、一実施形態において、高速アダマール変換装置である。ＦＨＴ装置は、ワイアレス通信システムにより、ＦＨＴアルゴリズムにより信号ブロックの伝送中に生じる誤りを検出しかつ訂正するために使用される。本発明のＦＨＴ装置は、ＦＨＴアルゴリズムにより必要とされる加算および減算動作を実行する一方で、信号を記憶するために、従来技術によるシステムと比べてより少量のハードウェアおよびメモリを必要とする。
【００１３】
一実施形態によれば、ワイヤレス通信システムは、例えばウォルシュコードワードに従って符号化された信号ブロックを受信するために、ＦＨＴ装置を使用する。好ましくは、相関係数が、送信された可能性ある正当なコードワードに対応するＦＨＴ装置により生成される。例えば、ワイアレス通信チャネルを介して送信されることを望まれたｎビットのデータのブロックは、送信に先立って、２nチップウォルシュコードワードに変換される。２nチップウォルシュコードワードは、ｎビットのデータのブロックの代わりに送信されて、ＦＨＴ装置の第１の変換段によりチップペアとして受信される。望ましくは、ＦＨＴ装置は、複数の変換段を含む。
【００１４】
装置の各変換段は、それが受信する入力信号への一連の動作を実行する。後続の変換段の各々は、先行する段がその入力信号を受信したクロックサイクルの数の半分である数のクロックサイクルにおいて、それに先行する段から入力信号を受信する。好ましくは、これは、各段において使用される第１および第２のメモリユニット（以下にさらに説明する）のメモリ記憶容量を、２の累乗で連続的に減少させることにより達成される。
【００１５】
装置の各段は、加算器および減算器を含む。加算器および減算器は、中間係数を生成するように、受信された信号ブロックの各々の中で入力信号対を受信する。
【００１６】
各変換段において、第１のメモリユニットは、加算器の出力端子へおよび減算器の出力端子へ結合されており、中間係数の第１の区別可能なシーケンスを加算器から受信し、中間係数の第２の区別可能なシーケンスを減算器から受信する。第２のメモリユニットは、中間係数の第３の区別可能なシーケンスを減算器から受信するように、減算器の出力端子に結合されている。第１のメモリユニットおよび加算器は、複数の中間係数信号対を後続の変換段に同時に提供し、第１および第２のメモリユニットは、複数の他の中間係数信号対を後続の変換段に同時に提供する。
【００１７】
本発明の別の実施形態において、ＦＨＴ装置は、入力信号の連続する対がＦＨＴ装置により受信されるようにするための、ｎビットカウンタのようなクロック手段を含む。クロック手段は、入力信号の各連続する対がＦＨＴ装置により受信される時間間隔を決定する。変換段の各々により受信されるカウンタ信号は、第２のメモリユニットを交番的にイネーブルしかつディスエーブルし、中間係数の第１の区別可能なシーケンスおよび第２の区別可能なシーケンスのうちのどちらが第１のメモリユニットにより受信されるかを決定する。
【００１８】
本発明のさらに別の実施形態において、最後の変換段により生成される各信号は、Ｎ個の正当な符号化された信号ブロックのうちの１つに対応する相関係数であり、最大の値を有する信号は、ワイアレスシステムにより送信された最も可能性の高い符号化された信号ブロックに対応する。したがって、送信された可能性が最も高い符号化された信号ブロックは、通信システムにより復号化され、かつ意図された受け手に送られる。
【００１９】
【発明の実施の形態】
本発明は、一実施形態によれば、本発明はこの範囲に限定されるものではないが、メッセージの伝送の間に、雑音、妨害および歪みにより生じる誤りを検出しかつ訂正するために、デジタルワイアレス通信システムにより使用される。図２は、伝送誤りを検出しかつ訂正するために、本発明の一実施形態により使用されるワイアレス通信チャネルおよび構成要素のいくつかを示す。
【００２０】
情報ソース１２は、デジタルメッセージをエンコーダ１４に送り、エンコーダ１４は、それをウォルシュコードワードに変換することによりデジタルメッセージを符号化する。そして、エンコーダ１４は、ウォルシュコードワードを送信機１６に供給し、送信機１６は、コードワードを搬送波に変調しかつそれを無線波により受信機１８に送信する。受信機１８は、受信されたウォルシュコードワードを受信しかつ復調して、それをデコーダ２０に供給する。伝送誤りのために、受信されたウォルシュコードワードは転化している可能性がある。
【００２１】
デコーダ２０は、どの正当なウォルシュコードワードが送信された可能性が最も高いかを決定するために、相関係数を生成するために、本発明のＦＨＴエンジンを使用する。デコーダ２０は、得られた正当なウォルシュコードワードを、元のデジタルメッセージに変換して戻し、これを情報宛先２２に供給する。好ましくは、情報宛先２２に供給されるデジタルメッセージは、情報ソース１２により送信された元のデジタルメッセージと同一である。
【００２２】
図３は、本発明の一実施形態により、ＦＨＴエンジンにより使用される典型的な段の構成要素を示す。段１１は、上側入力端子１０２および下側入力端子１０４を有する。上側入力端子１０２は、段がＦＨＴエンジンの第１段である場合ウォルシュチップ、または段がＦＨＴエンジンの第１段でない場合中間相関係数の何れかである複数の入力信号を受信するように構成されている。
【００２３】
Ｎ個のウォルシュチップのブロックが処理されるべき場合、上側入力端子１０２は、Ｎ／２個の入力信号ビットまたはシンボルを受信する。上側入力端子１０２は、加算器１０６の第１の入力端子に結合されており、さらに減算器１０８の第１の入力端子に結合されている。同様に、下側入力端子１０４は、段がＦＨＴエンジンの第１段である場合ウォルシュチップ、または段がＦＨＴエンジンの第１段でない場合、中間相関係数のいずれかである複数の入力信号を受信するように構成されている。
【００２４】
端子１０２と同様に、Ｎ個のウォルシュチップのブロックが処理されるべき場合、下側入力端子１０４は、Ｎ／２個の入力信号ビットまたはシンボルを受信する。下側入力端子１０４は、加算器１０６の第２の入力端子に結合されており、さらに加算器１０８の第２の入力端子に結合されている。さらに後述するように、ウォルシュチップの対または中間相関係数は、様々な異なる順序で、上側および下側入力端子１０２および１０４に到達しうる。
【００２５】
加算器１０６は、上側入力端子１０２および下側入力端子１０４により受信された入力信号の対を加算することにより出力信号１１０を生成するように構成されている。加算器１０６により生成された出力信号１１０は、マルチプレクサ１１４の入力端子“０”として示された第１の入力端子およびマルチプレクサ１２２の入力端子“０”として示された第２の入力端子に送られる。
【００２６】
減算器１０８は、上側入力端子１０２および下側入力端子１０４により受信された入力信号の同じ対を減算することにより出力信号１１２を生成するように構成されている。減算器１０８により生成された出力信号１１２は、マルチプレクサ１１４の入力端子“１”として示された第２の入力端子およびシフトレジスタ１１８の入力に送られる。マルチプレクサ１１４は、シフトレジスタ１１６の入力端子に送られる出力信号１１５を生成するように構成されている。
【００２７】
シフトレジスタ１１６および１１８はメモリ空間である。シフトレジスタ１１６および１１８に記憶されうる信号の数は、以下に説明するように、ＦＨＴエンジンにいくつの段があるかおよびそれらが配置されたものがＦＨＴのどの段であるかに依存する。シフトレジスタ１１６は、マルチプレクサ１２０の入力端子“０”として示された第２の入力端子におよびマルチプレクサ１２２の入力端子“１”として示された第１の入力端子に送られる出力信号１１７を生成するように構成される。シフトレジスタ１１８は、マルチプレクサ１２０の入力端子“１”として示された第１の入力端子に送られる出力信号１１９を生成するように構成される。
【００２８】
マルチプレクサ１２０は、現在の段がＦＨＴエンジンの最終段でない場合、エンジンの次の段の上側入力端子１０２により受信される入力信号に対応する出力信号１２４を生成するように構成される。現在の段が、ＦＨＴエンジンの最終段でない場合、出力信号１２４および次の段の対応する入力信号は、中間相関器係数と呼ばれる。現在の段がＦＨＴエンジンの最終段である場合、出力信号１２４は、最終の相関係数に対応し、その値は、送信された可能性の最も高い正当なウォルシュコードワードを決定するためにＦＨＴエンジンにより使用される。
【００２９】
マルチプレクサ１２２は、現在の段がＦＨＴエンジンの最終段でない場合、ＦＨＴエンジンの次の段の下側入力端子１０４により受信されるべき入力信号に対応する出力信号１２６を生成するように構成される。上記のように、現在の段がＦＨＴエンジンの最終段でない場合、出力信号１２６および次の段の対応する入力信号は、中間相関係数と呼ばれる。現在の段がＦＨＴエンジンの最終段である場合、出力信号１２６は最終の相関係数に対応し、その値は、送信された可能性が最も高い正当なウォルシュコードワードを決定するためにＦＨＴエンジンにより使用される。
【００３０】
ＦＨＴイネーブル信号１２７は、シフトレジスタ１１６を全ての時点でイネーブルするように、シフトレジスタ１１６に結合されている。ＦＨＴイネーブル信号１２７は、クロック手段１２８にも結合されている。この実施形態において、クロック手段１２８は、５ビットカウンタである。カウンタの各ビットは、図３において、出力端子Ｑ0ないしＱ4により示されており、各クロックサイクルは、１の値高くカウンティングする５ビットカウンタに対応する。
【００３１】
出力端子Ｑ0は、カウンタの第１ビットであり、各クロックサイクルにおいて交番的に“オン”されおよび“オフ”される（即ち、０００００，００００１等）。Ｑ1は、カウンタの第２ビットであり、５ビットカウンタが連続的に高くカウントするとき、交番的に、２つのサイクルに対して“オン”であり、２つのサイクルに対して“オフ”である（即ち、０００００，００００１，０００１０，０００１１等である）。
【００３２】
Ｑ2はカウンタの第３ビットであり、交番的に、４つのサイクルに対して“オン”であり、４つのサイクルに対して“オフ”である。Ｑ3は、カウンタの第４ビットであり、交番的に、８個のサイクルに対して“オン”であり、８個のサイクルに対して“オフ”である。図５は、以下により詳細に説明するが、出力端子Ｑ0ないしＱ3が、それぞれ連続する段１ないし段４のシフトレジスタのうちの１つおよびマルチプレクサに結合されている。
【００３３】
図３に示された実施形態において、出力端子Ｑ4は、カウンタの第４ビットであり、交番的に、１６個のサイクルに対して“オン”であり、１６個のサイクルに対して“オフ”である（即ち、０００００…０１１１１，１００００…１１１１１等である）。出力端子Ｑ4は、シフトレジスタ１１８に供給されており、シフトレジスタ１１８が、交番的に、１６個のサイクルに対してイネーブルされ、そして１６個のサイクルに対してディスエーブルされるようにする。一般に、各クロックサイクルにおいて、シフトレジスタ１１６および１１８に格納された信号は、シフトレジスタの内部メモリ空間中で１つの位置シフトされる。
【００３４】
全ての内部メモリ空間が一杯になった後、別の入力信号の到着は、シフトレジスタに、受信した第１の信号に対応する出力信号を生成させる。入力信号の各連続する到着は、受信された第２の入力信号、受信された第３の入力信号等に対応するさらなる出力信号を生成させる。出力端子Ｑ4は、マルチプレクサ１１４，１２０および１２２にも結合されており、マルチプレクサに、代替的に、１６個のサイクルに対して、それらの上側入力端子上の入力信号を選択させ、そして１６個のサイクルに対してそれらの下側入力端子上の入力信号を選択させる。
【００３５】
クロック手段１２８により使用されるカウンタのビット数が、高速アダマール変換エンジンにより処理されるウォルシュチップの数に依存することに注意すべきである。Ｎ個のウォルシュチップがエンジンにより処理されるべき場合、クロック手段１２８は、ｌｏｇ2（Ｎ／２）ビットを有するカウンタを使用する。したがって、３２個のウォルシュチップを有するブロックまたはコードワードを処理する３２−ａｒｙ直交変調器は、４ビットカウンタを使用し、１２８個のウォルシュチップを有するブロックまたはコードワードを処理する１２８−ａｒｙ直交変調器は、６ビットカウンタを使用する。カウンタのサイズに無関係に、カウンタの各ビットは、エンジンの連続する段に結合される。
【００３６】
エンジンための段の数は、ＦＨＴエンジンにより処理されるウォルシュチップの数にも依存する。ＦＨＴエンジンのための段の数は、ｌｏｇ2Ｎに等しく、ここでＮは、送信されるブロックまたはウォルシュコードワード中のウォルシュチップの数である。例えば、６４個のウォルシュチップを有するブロックまたはコードワードを処理する６４−ａｒｙ直交変調器は、ｌｏｇ2（６４）、即ち６個の段を有し、３２−ａｒｙ直交変調器は、ｌｏｇ2（３２）、即ち５個の段を有する。
【００３７】
ＦＨＴエンジンの段は、１つの段からの出力信号が後続の段のための入力信号に対応するように、カスケード接続される。図４は、本発明の一実施形態にしたがって、どのように多様な段が接続されるかを示す。図４において、Ｉ1（ｉ）およびＩ2（ｉ）は、高速アダマール変換エンジン１０に入力されるウォルシュチップである。図示されているようにウォルシュチップは、段０に入り、段０は、中間相関係数に対応する出力信号１２４−０および１２６−０を生成する。段０からの出力信号１２４−０および１２６−０は、次の段のための入力信号であり、次の段の出力信号、例えば出力信号１２４−ｌｏｇ2Ｎ−２および１２６−ｌｏｇ2Ｎ−２は次の後続段のための入力信号である。
【００３８】
これは、最終的に信号の対が段（ｌｏｇ2Ｎ）−１に入力されるまで繰り返される。図示された実施形態において、段（ｌｏｇ2Ｎ）−１は、ＦＨＴエンジンの最終段であり、これは、出力信号１２４−ｌｏｇ2Ｎ−１および１２６ｌｏｇ2Ｎ−１を生成する。これらの出力信号は、どのウォルシュコードワードが送信された可能性が最も高いかを決定するために使用される最終の相関係数に対応する。図５は、以下により詳細に説明するが、段”０”ないし”５”が６４−ａｒｙビットシステムのためにどのように接続されているかを示す。
【００３９】
前述したように、シフトレジスタ１１６および１１８に格納されうる信号即ち中間ウォルシュ係数の数は、ＦＨＴエンジンの段の数およびどの段によりシフトレジスタが配置されるかにより決定される。Ｎ個のウォルシュチップを有するウォルシュコードワードを処理するＦＨＴエンジンにおいて、シフトレジスタのｓ段中に格納されうる信号またはチップの数は、（Ｎ／４）／２sに対応する。
【００４０】
したがって、６４個のウォルシュチップを有するウォルシュコードワードを処理するシステムに対して、第１段（段“０”）のシフトレジスタ中に格納されうるチップの数は、（６４／４）／２s＝１６／２0＝１６に等しい。同じシステムに対して、第２段（段“１”）のシフトレジスタ中に格納されうるチップの数は、（６４／４）／２1＝８に等しい。このシステムの段２，３および４のシフトレジスタ中に格納されうるチップの数は、それぞれ４個、２個および１個のチップである。３２個のウォルシュチップを有するウォルシュコードワードを処理するシステムに対して、段０のシフトレジスタ中に格納されうるチップの数は、８であり、段１については４である。
【００４１】
ウォルシュチップがＦＨＴエンジンの第１段に入力されうる様々な方法がある。図６Ａ−Ｂは、本発明の一実施形態にしたがって、６４個のウォルシュチップを有するウォルシュコードワード（図５Ａ−Ｂに示されているように構成された）を入力する１つの可能な順序およびＦＨＴエンジンが入力された信号について動作を実行する方法を示すタイムチャートである。また、このタイムチャートは、６４個の最終の相関係数を生成するために必要とされるクロックサイクルの数を示す。
【００４２】
この実施形態にしたがって、クロックサイクル０として示された第１のクロックサイクルにおいて、ウォルシュチップインデックス“０”として示された第１のウォルシュチップが、段０中の上側入力端子１０２に入力され、ウォルシュチップインデックス“３２”により示されたウォルシュチップが、段０の下側入力端子１０４に入力される。次のクロックサイクルにおいて、ウォルシュチップ“１”および“３３”は、上側および下側入力端子１０２および１０４に到着し、次に“２”および“３４”，“３”および“３５”，等となる。
【００４３】
図５Ａ−Ｂは、本発明の一実施形態にしたがって、図６Ａ−Ｂのタイムチャートに対応するＦＨＴエンジンを示す。図５Ａ−Ｂは、ＦＨＴエンジンのカスケード接続された段により処理されるウォルシュチップ“０”ないし“６３”に対応する入力信号および出力信号を示す。例えば、エンジンの段“０”において、ウォルシュチップ“０”ないし“３１”に対応する入力信号は、上側入力端子１０２に到着し、ウォルシュチップ“３２”ないし“６３”に対応する入力信号は、下側入力端子１０４に到着する。図６のタイムチャートの関係で上述したように、ウォルシュチップ“０”および“３２”に対応する入力信号は、まず加算器１０６により加算されて、減算器１０８により減算される。
【００４４】
図５および６の両方に示されているように、クロックサイクル０ないし１５において、マルチプレクサ１１４の入力端子“０”が、係数“０”ないし“１５”として同定された第１の１６個のウォルシュチップ対の和に対応する出力信号１１５を生成するように、クロック手段１２８の出力端子Ｑ4により制御されて選択される。これらの同じクロックサイクルにおいて、シフトレジスタ１１６は、係数“０”ないし“１５”として同定されたマルチプレクサ１１４により生成される出力信号１１５を受け入れるようにイネーブルされる。
【００４５】
シフトレジスタ１１８は、係数“３２”ないし“４７”として同定された第１の１６個のウォルシュチップ対の差に対応する出力信号１１２を受け入れるように、イネーブルされる。したがって、１６個のサイクルの最後において、レジスタ１１６は、第１の和の結果を格納し、レジスタ１１８は、第１の１６個のウォルシュチップ対の減算の結果を格納する。
【００４６】
この時点において、シフトレジスタ１１８がディスエーブルされるようにクロック信号Ｑ4がロウになり、マルチプレクサ１２０および１２２の入力端子“０”が選択されて、マルチプレクサ１１４の入力端子“１”が選択される。結果として、クロックサイクル１６ないし３１において、マルチプレクサ１１４は、減算器１０８において受信された次の１６個のウォルシュチップ対の差に対応する係数“４８”ないし“６３”として同定される出力信号１１５を生成する。
【００４７】
シフトレジスタ１１６は、マルチプレクサ１１４により生成された係数“４８”ないし“６３”に対応する出力信号を受け入れるように、ＦＨＴイネーブル信号１２７によりイネーブルされたままとなる。その間、シフトレジスタ１１６は、クロックサイクル０ないし１５の間に受信した係数“０”ないし“１５”に対応する信号を逐次的(sequential)に出力する。これらの出力信号は、入力端子“０”において受信する信号に対応する出力信号１２４を生成するようにイネーブルされるマルチプレクサ１２０に送られる。したがって、クロックサイクル１６ないし３１において、係数“０”ないし“１５”に対応する入力信号は、段１の上側入力端子１０２に到着する。
【００４８】
クロックサイクル０ないし１５の間に、シフトレジスタ１１８は、何ら信号を受け入れないようにディスエーブルされ、その変わりに、クロックサイクル０ないし１５の間に以前に受信した係数”３２”ないし”４７”に対応する信号を格納する。また、クロックサイクル１６ないし３１の間に、マルチプレクサ１２０の入力端子”０”は、入力端子”０”で受信する信号に対応する出力信号１２６を生成するように選択される。このようにして、係数”１６”ないし”３１”に対応する入力信号が、段１の下側入力端子１０４に到着する。
【００４９】
クロックサイクル３２ないし４７の間に、シフトレジスタ１１６は、ＦＨＴイネーブル信号１２７により制御されるように、イネーブルのままにされて、クロックサイクル１６ないし３１の間において受信された係数”４８”ないし”６３”に対応する出力信号を格納するようにする。これらの出力信号は、入力端子”１”に提供された信号を選択するように構成されたマルチプレクサ１２２に送られる。このようにして、係数”４８”ないし”６３”に対応する入力信号が、段１の下側入力端子１０４に到着する。
【００５０】
シフトレジスタ１１８は、依然に格納した係数“３２”ないし“４７”に対応する出力信号を生成するように、クロック手段１２８の出力端子Ｑ4により制御されるように、再びイネーブルされる。さらに、クロックサイクル３２ないし４７において、マルチプレクサ１２２は、入力端子“１”で受信する信号に対応する出力信号を生成するようにイネーブルされる。したがって、係数“３２”ないし“４７”に対応する入力信号が、段１の上側入力端子１０２に到着する。
【００５１】
図示されているように、後続の段の各々は、先行する段がその入力信号を受信したクロックサイクルの数の半分である数のクロックサイクルにおいて、それに先行する段から入力信号を受信する。これは、前述したように、各後続の段において、シフトレジスタのメモリ格納容量を、２の累乗で、暫時的に減少させることにより達成される。
【００５２】
前述したように、本発明の一実施形態によれば、クロック手段１２８は、先行する段における場合の２倍の頻度で各後続する段において、マルチプレクサの入力信号をスイッチしかつシフトレジスタ１１８をイネーブルおよびディスエーブルするように動作する。例えば、上記の例において、クロック手段１２８が、段０において１６個のクロックサイクル毎に、マルチプレクサおよびシフトレジスタ１１８の動作を反転させた場合、段１において８クロックサイクル毎に動作を反転させ、段２において４クロックサイクル毎に動作を反転させることになる。
【００５３】
従来技術との比較において、本発明のＦＨＴエンジンは、ＦＨＴアルゴリズムにより必要とされる和および差の動作を実行する一方で、信号を格納するためのより小さな量のメモリ空間を必要とする。例えば、クロックサイクル１６において、段０および段１の両方は、係数“１６”に対応する入力信号を受信し、これについてＦＨＴアルゴリズムの和および差の動作を実行し、入力信号を格納する必要性を取り除き、または得られる出力信号を２度格納する必要性を除去する。クロックサイクル１７において、段０の上側入力信号および段１の下側入力信号に関して同じ利益が得られる。この場合において、両方の段は、係数“１７”に対応する入力信号を受信し、入力信号を格納する必要がなく、または得られる出力信号を２度格納する必要がない。
【００５４】
いずれかの２つの隣接する段の間で、連続するクロックサイクルの各々において、この利益が繰り返される。例えば、クロックサイクル２９において、ウォルシュチップ“２９”に対応する入力信号は、段０の上側入力端末１０２に到着し、係数“２９”に対応する入力信号は、段１の下側入力端子１０４に到着し、係数“１３”に対応する入力信号は、段１の上側入力端子１０２および段２の下側入力端子１０４に到着し、係数“５”に対応する入力信号は、段２の上側端子１０２および段３の下側入力端子１０４に到着する。
【００５５】
図６から分かるように、本発明のこの実施形態は、全ての６４個の相関係数を生成するために、６３個のクロックサイクルを必要とする。前述したように、段５の上側入力１０２および下側入力１０４により受信された入力信号としても示されている段４のマルチプレクサ１２０および１２２により生成された出力信号は、それぞれが正当なウォルシュコードワードに対応する最終の相関係数である。望ましくは、この実施形態において、ＦＨＴエンジンの最終段において生成される出力信号は、逐次的な順序にある。
【００５６】
一実施形態において、全ての６４個の相関係数が生成された後、最大の係数が選択されて、選択された係数に対応する正当なウォルシュコードワードが、もともと送られたウォルシュコードワードであると決定される。別の実施形態において、各２つの最終的な相関係数が段５において生成されるので、図５に示されたコンパレータ１５０は、２つのうちどちらが大きいかを決定し、次のクロックサイクルにおいて生成されることになる２つの最終的な相関係数との比較のために大きい方の係数を格納する。
【００５７】
このプロセスは、全ての最終的な相関係数が生成されかつ比較されて、最大のものが選択されるまで繰り返される。どちらの実施形態においても、受信機１８により受信された６４チップブロックまたはウォルシュコードワードは、コードワードが伝送中に雑音、妨害または歪みにより転化した場合に、訂正される。
【００５８】
ＦＨＴエンジンの第１段においてウォルシュチップが入力されうる別の方法が、図７Ａ−Ｂに別のタイムチャートとして示されている。この実施形態において、段０の上側入力１０２および下側入力１０４に到着する入力信号は、第１のクロックサイクルにおいて、ウォルシュチップ“0”および“１”がそれぞれ上側入力１０２および下側入力１０４に到着するように、逐次的な順序にある。
【００５９】
次のクロックサイクルにおいて、ウォルシュチップ“２”および“３”は、上側入力１０２および下側入力１０４に到着し、ウォルシュチップ“４”および“５”，“６”および“７”も同様に到着する。この実施形態の１つの利点は、上側入力１０２および下側入力１０４へのそれらの到着に先立ってウォルシュチップのセットをメモリ空間中で維持する必要がなく、到来するチップは、ＦＨＴエンジンに即座に供給されうることである。しかし、図７の上側段５および下側段５において分かるように、出力１２４および１２６から表れる最終の出力信号は、逐次的な順序でない。
【００６０】
以上、本発明の特定の実施例が示され説明が加えられたが、この実施例の構成を、本発明の技術的なアイデアから逸脱することなく適当に変更および修正をすることが可能であることは、当業者には明らかである。したがって、特許請求の範囲の記載は、本発明の技術的範囲に含まれるそのような変更および修正をカバーしているものと理解すべきである。
【００６１】
【発明の効果】
以上説明したように本発明によれば、従来技術による高速アダマール変換が非常に遅くかつ非常に多くのハードウェアを必要とする欠点を除去し、高速、コンパクトかつ有効なＦＨＴエンジンを提供することができる。
【図面の簡単な説明】
【図１】本発明の一実施形態による典型的なワイアレス通信システムを示す図。
【図２】本発明の一実施形態において、伝送誤りを検出しかつ訂正するために、デジタルワイアレス通信システムにより典型的に使用される構成要素のいくつかを示す図。
【図３】本発明の一実施形態によるＦＨＴエンジンの各段の構成要素を示す図。
【図４】本発明の一実施形態によりどのようにＦＨＴエンジンの複数の段が接続されるかを示す図。
【図５】本発明の一実施形態による複数の段を有するＦＨＴエンジンを示す図。
【図６】本発明の一実施形態によるＦＨＴエンジンの各段に入力信号がどのようにいつ到着するかを示すタイミング図。
【図７】本発明の別の実施形態によるＦＨＴエンジンの各段に、入力信号がどのようにいつ到着するかを示すタイミング図。
【符号の説明】
１２  情報ソース
１４  エンコーダ
１６  送信機
１８  受信機
２０  デコーダ
２２  情報宛先
１０６  加算器
１０８  減算器
１１４，１２０，１２２  マルチプレクサ
１１６，１１８  １６エレメントシフトレジスタ
１５０  コンパレータ
２０１  交換機センタ
２０３  基地局
２０７  ワイヤライン端末
【図１】
0003676174.tif 000002
【図２】
0003676174.tif 000003
【図３】
0003676174.tif 000004
【図４】
0003676174.tif 000005
【図５】
0003676174.tif 000006
【図６】
0003676174.tif 000007
【図７】
0003676174.tif 000008