(57)【要約】ヘッダ圧縮／伸長を使用するパケット通信において、ヘッダ毎に変化しないヘッダ・ビット（Ｓ）に関連する固定チェックサム情報を再利用することによって、チェックサム生成の計算の複雑性が低減され得る。所望のチェックサム（ＣＳ）を生成するために、固定チェックサム情報は、ヘッダ毎に変化するヘッダ・ビット（Ｔ）についての情報と一緒に使用され得る。チェックサムは、ヘッダ伸長器によって圧縮されたヘッダから生成される再構成ヘッダ（１７）を確認するのに使用され得る。【特許請求の範囲】
【請求項１】
パケット受信局がパケット送信局から受信した圧縮されたヘッダから生成する、再構成されたヘッダを確認するのに使用するチェックサムの生成方法であって、前記圧縮されたヘッダは前記パケット送信局でターゲット・ヘッダを圧縮して生成され、
ターゲット・ヘッダの固定部分に関連し、パケット・フロー内の全てのヘッダの対応する固定部分内の不変の固定情報を伝える、固定チェックサム情報を提供するステップと、
前記ターゲット・ヘッダの過渡的部分を表し、前記パケット・フローの他のヘッダの対応する過渡的部分内の対応する情報と異なり得る情報を伝える、別の情報を提供するステップと、
再構成されたヘッダを確認するのに使用するチェックサムを生成すべく、前記固定チェックサム情報と前記別の情報とを組合せるステップと、を備えることを特徴とする方法。
【請求項２】
前記パケット受信局及び前記パケット送信局が無線通信デバイスであることを特徴とする請求項１に記載の方法。
【請求項３】
前記固定チェックサム情報を提供するステップが、前記パケット・フロー内のコンテキスト更新ヘッダを提供するステップと、前記コンテキスト更新ヘッダの前記過渡的部分からの情報をチェックサム・レジスタに供給せずに、前記コンテキスト更新ヘッダの前記固定部分からの情報を前記チェックサム・レジスタに供給するステップと、前記供給ステップの後に前記チェックサム・レジスタの符号化状態を格納するステップと、を含むことを特徴とする請求項１に記載の方法。
【請求項４】
前記組合せるステップが、格納された符号化状態を前記チェックサム・レジスタにロードし、その後で前記別の情報を前記チェックサム・レジスタに供給するステップを含むことを特徴とする請求項３に記載の方法。
【請求項５】
前記固定チェックサム情報を提供するステップが、前記固定部分を前記過渡的部分から分離するために前記コンテキスト更新ヘッダをソーティングするステップを含み、前記コンテキスト更新ヘッダの前記固定部分からの情報を供給するステップが、前記情報を前記チェックサム・レジスタにシフトするステップを含み、前記別の情報を前記チェックサム・レジスタに供給するステップが、前記別の情報を前記チェックサム・レジスタにシフトするステップを含むことを特徴とする請求項４に記載の方法。
【請求項６】
前記別の情報を提供するステップが、前記固定部分を前記過渡的部分から分離するために、前記ターゲット・ヘッダ及び前記再構成されたヘッダの一方をソーティングするステップを含むことを特徴とする請求項４に記載の方法。
【請求項７】
前記一方のヘッダが前記ターゲット・ヘッダであり、前記別の情報が前記ターゲット・ヘッダの前記過渡的部分内の情報であることを特徴とする請求項６に記載の方法。
【請求項８】
前記一方のヘッダが前記再構成されたヘッダであり、前記別の情報が前記ターゲット・ヘッダの前記過渡的部分内の情報を表す、前記再構成されたヘッダの前記過渡的部分内の情報であることを特徴とする請求項６に記載の方法。
【請求項９】
前記固定チェックサム情報を提供するステップが、前記パケット・フロー内のコンテキスト更新ヘッダを提供するステップと、前記固定部分を前記過渡的部分から分離するために前記コンテキスト更新ヘッダをソーティングするステップと、前記パケット・フローの間に前記情報のそれぞれの部分が変化する可能性に従って前記過渡的部分内の情報をソーティングする別のソーティングステップと、前記ソーティング及び前記別のソーティングでソートされたコンテキスト更新ヘッダをチェックサム・レジスタにシフトするステップと、前記シフト動作の間に前記チェックサム・レジスタに現れる固定情報と過渡的情報との組合せのそれぞれについて、前記チェックサム・レジスタの対応する符号化状態を格納するステップと、を含むことを特徴とする請求項１に記載の方法。
【請求項１０】
前記別の情報を提供するステップが、前記パケット・フローの間に前記情報のそれぞれの部分が変化する可能性に従って、前記ターゲット・ヘッダ及び前記再構成されたヘッダの一方の前記過渡的部分内の情報をソーティングするステップを含み、前記組合せるステップが、前記格納された符号化状態の１つを前記チェックサム・レジスタにロードし、その後で前記チェックサム・レジスタに、前記コンテキスト更新ヘッダの対応する部分と異なる前記一方のヘッダの過渡的部分の一部をシフトするステップを含むことを特徴とする請求項９に記載の方法。
【請求項１１】
前記一方のヘッダが前記再構成されたヘッダであり、最後に述べたシフトするステップにおける各シフトにそれぞれ対応した前記チェックサム・レジスタの別の符号化状態を格納するステップと、前記格納された前記別の符号化状態の１つを前記チェックサム・レジスタにロードし、その後で前記再構成されたヘッダの１つの対応する部分と異なる、後続して再構成されたヘッダの前記過渡的部分の一部を前記チェックサム・レジスタにシフトするステップとを含み、これにより前記後続して再構成されたヘッダを確認するのに使用するチェックサムを生成することを特徴とする請求項１０に記載の方法。
【請求項１２】
前記固定チェックサム情報を提供するステップが、前記パケット・フロー内の前記固定情報に関連する第１のチェックサム成分を生成するステップを含むことを特徴とする請求項１に記載の方法。
【請求項１３】
前記別の情報を提供するステップが、それぞれが前記パケット・フロー内のヘッダの前記過渡的部分の関連する部分を表している、複数の別のチェックサム成分を提供するステップを含むことを特徴とする請求項１２に記載の方法。
【請求項１４】
前記別の情報を提供するステップが、前記ターゲット・ヘッダ及び前記再構成されたヘッダの一方の前記過渡的部分内のビット値に基づいて、前記別のチェックサム成分の少なくともいくつかを選択するステップを含み、前記組合せるステップが、前記チェックサムを生成するために、前記選択された別のチェックサム成分を前記第１のチェックサム成分と組合せるステップを含むことを特徴とする請求項１３に記載の方法。
【請求項１５】
前記組合せるステップが、前記選択された別のチェックサム成分のそれぞれと前記第１のチェックサム成分とのモジュロ−２の加算を行うステップを含むことを特徴とする請求項１４に記載の方法。
【請求項１６】
前記選択するステップが、前記ターゲット・ヘッダ内のビット値に基づいて選択するステップを含むことを特徴とする請求項１４に記載の方法。
【請求項１７】
前記選択するステップが、前記再構成されたヘッダ内のビット値に基づいて選択するステップを含むことを特徴とする請求項１４に記載の方法。
【請求項１８】
前記固定チェックサム情報を提供するステップが、前記パケット・フロー内のヘッダの前記過渡的部分内の複数のビット部分を表す、第２のチェックサム成分を生成するステップを含むことを特徴とする請求項１３に記載の方法。
【請求項１９】
前記組合せるステップが、前記チェックサムを生成するために、前記第２のチェックサム成分を前記別のチェックサム成分及び前記第１のチェックサム成分と組合せるステップを含むことを特徴とする請求項１８に記載の方法。
【請求項２０】
前記チェックサムがＣＲＣチェックサムであることを特徴とする請求項１に記載の方法。
【請求項２１】
パケット受信局がパケット送信局から受信した圧縮されたヘッダから生成する、再構成されたヘッダを確認するのに使用するチェックサムを生成する装置であって、前記圧縮されたヘッダは前記パケット送信局でターゲット・ヘッダを圧縮して生成され、
ターゲット・ヘッダの固定部分に関連し、パケット・フロー内の全てのヘッダの対応する固定部分内の不変の固定情報を伝える、固定チェックサム情報を受信する第１の入力と、
前記ターゲット・ヘッダの過渡的部分を表し、前記パケット・フローの他のヘッダの対応する過渡的部分内の対応する情報と異なり得る情報を伝える、別の情報を受信する第２の入力と、
前記第１及び第２の入力に接続され、再構成されたヘッダを確認するのに使用するチェックサムを生成すべく、前記固定チェックサム情報と前記別の情報とを組合せるコンバイナと、を備えることを特徴とする装置。
【請求項２２】
無線通信デバイス内に設けられていることを特徴とする請求項２１に記載の装置。
【請求項２３】
前記コンバイナが、前記第２の入力に接続され、前記別の情報がシフトされて入力されるチェックサム・レジスタを含み、前記固定チェックサム情報が、前記固定情報に応答して前記チェックサム・レジスタによって生成される前記チェックサム・レジスタの符号化状態を含み、前記チェックサム・レジスタに接続され、前記符号化状態を格納する格納デバイスをさらに含み、前記格納デバイスが、前記第１の入力に接続され、前記別の情報が前記チェックサム・レジスタにシフトされる前に前記符号化状態を前記チェックサム・レジスタにロードすることを特徴とする請求項２１に記載の装置。
【請求項２４】
前記別の情報が、前記ターゲット・ヘッダの前記過渡的部分内の情報であることを特徴とする請求項２３に記載の装置。
【請求項２５】
前記別の情報が、前記ターゲット・ヘッダの前記過渡的部分内の情報を表す、前記再構成されたヘッダの前記過渡的部分内の情報であることを特徴とする請求項２３に記載の装置。
【請求項２６】
前記固定チェックサム情報が、前記パケット・フロー内の前記固定情報に関連する第１のチェックサム成分を含み、前記別の情報が、それぞれが前記パケット・フロー内のヘッダの前記過渡的部分の関連する部分を表している、複数の別のチェックサム成分を含み、前記コンバイナが、前記チェックサムを生成すべく、前記別のチェックサム成分を前記第１のチェックサム成分と組合せるよう動作することを特徴とする請求項２１に記載の装置。
【請求項２７】
前記コンバイナが、前記別のチェックサム成分のそれぞれと前記第１のチェックサム成分とのモジュロ−２の加算を行う計算ロジックを含むことを特徴とする請求項２６に記載の装置。
【請求項２８】
前記固定チェックサム情報が、前記パケット・フロー内のヘッダの前記過渡的部分内の複数のビット部分を表す第２のチェックサム成分を含み、前記コンバイナが、前記チェックサムを生成すべく、前記別のチェックサム成分を前記第１及び第２のチェックサム成分と組合せるよう動作することを特徴とする請求項２６に記載の装置。
【請求項２９】
前記コンバイナが、ＣＲＣチェックサムを生成すべく動作することを特徴とする請求項２１に記載の装置。
【請求項３０】
前記パケット受信局に設けられていることを特徴とする請求項２１に記載の装置。
【請求項３１】
前記パケット送信局に設けられていることを特徴とする請求項２１に記載の装置。
【請求項３２】
前記パケット受信局が前記組合せるステップを実行することを特徴とする請求項１に記載の方法。
【請求項３３】
前記パケット送信局が前記組合せるステップを実行することを特徴とする請求項１に記載の方法。
【発明の詳細な説明】
【０００１】
＜発明の技術分野＞
本発明は概してパケット・フローにおけるヘッダの圧縮／伸長に関し、より詳細には、ヘッダの圧縮又は伸長で使用するチェックサムの計算に関する。
【０００２】
＜発明の背景＞
セルラ電話などのパーソナル無線通信デバイスの広範囲な普及が、増大しているインターネットの使用と結びつき、無線通信リンクを介したインターネット・プロトコル（ＩＰ）のトラフィックの提供に対する願望を駆り立ててきた。従来の無線通信リンクにおいては通信リソースが比較的乏しいため、例えばＩＰトラフィックを運ぶパケットに使用されるＩＰヘッダなどのデータ・パケットのヘッダに含まれる情報を圧縮する様々な技術が開発されてきた。送信局では、ヘッダ圧縮器によって全ヘッダ情報が圧縮され、圧縮されたヘッダ情報は無線通信リンクを介して送信される。受信局では、ヘッダ伸長器が送信された圧縮されたヘッダ情報から全ヘッダを再構成する。これは、ヘッダ情報の送信に必要な無線通信リンクのリソースの量を減少させる。
【０００３】
図１は、ヘッダ圧縮／伸長を伴う無線パケット通信（例えば、ＩＰトラフィック）を提供する、従来の無線通信局（例えば、セルラ電話）の例を示した図である。図１の例では、パケット・プロセッサ１４は、双方向通信のために通信アプリケーション１１と無線通信インタフェース１３とに接続されている。パケット・プロセッサ１４は、通信アプリケーション１１から通信情報を受信し、この情報を適切なパケットに組み立て、そのパケットは無線通信リンク１５を介した送信のために無線通信インタフェース１３に渡される。パケット・プロセッサ１４によって生成されたパケット１０は、ヘッダ部分１８とペイロード部分１６を含んでいる。ペイロード部分１６はペイロード情報を含み、ヘッダ部分１８は圧縮されたヘッダ情報１７とチェックサム１９を含んでいる。図１及び２に示したように、パケット・プロセッサ１４は、圧縮されたヘッダ情報１７を生成するために、通信アプリケーション１１から受信した全ヘッダ情報を圧縮すべくヘッダ圧縮器１２を使用する。また、パケット・プロセッサ１４は、ヘッダ情報をカバーするチェックサム１９を生成するのにチェックサム発生器１２を使用する。
【０００４】
図１の通信局が無線通信リンク１５を介してパケット１０を受信するとき、パケット・プロセッサ１４は、圧縮されたヘッダ情報１７及びチェックサム１９から全ヘッダ情報を再構成するのに、ヘッダ伸長器及びチェックサム生成器１２を使用する。圧縮されたヘッダ情報が生成される元のヘッダが、再構成されるヘッダと一致すべきターゲット・ヘッダである。そして再構成された全ヘッダ情報が、ペイロード情報と共に通信アプリケーション１１にもたらされる。コンテキスト更新が生じると、送信端でコンテキストを更新する付加情報がヘッダに追加され、受信端でチェックサムの生成が必要となる（図３の破線を参照）。
【０００５】
既知のヘッダ圧縮／伸長方式では、伸長器は受信した圧縮されたヘッダ情報から全ヘッダ情報を推定（あるいは推測）しようとする。このような技術は、パケット・ヘッダのある部分が、通常は比較的容易に予測できる形で変更されると予期されるので、効率的となり得る。例えば、ある従来のリアルタイム音声アプリケーションは、そのヘッダに比較的容易に予測できるタイムスタンプ・フィールドを利用する。他の例は、リアルタイムのビデオアプリケーションと、例えばＦＴＰなどの通常のベストエフォート・サービス用のヘッダとを含んでいる。伸長器が全ヘッダの推定（あるいは推測）を行うとき、この推定／推測に基づいてチェックサムが生成され、圧縮されたヘッダと共に受信したチェックサムと比較される。これは図３に示されている。パケット・プロセッサ１４のヘッダ伸長器の推定値発生器３１は、無線通信インタフェース１３から圧縮されたヘッダ情報１７を受信する。推定値発生器１３によって生成された全ヘッダの推定値はそれからチェックサム１９’を生成するチェックサム発生器１２に入力される。そしてチェックサム１９’は圧縮されたヘッダ情報と共に受信したチェックサム１９と３３で比較される。チェックサムが一致すると、推定／推測はターゲット・ヘッダの再構成が正しいと見なす。しかしながら、３３でチェックサムが一致しなかったら、推定値発生器３１は再度推定するよう指示され、その上で上記のチェックサム生成及び比較処理が繰り返される。
【０００６】
不都合なことに、ヘッダの圧縮及び伸長の両方に対する上記のチェックサム生成処理は、計算が複雑であり、推定の数が増えると共に伸長器での計算についての要件が増大する。
【０００７】
このため、ヘッダ圧縮及び伸長におけるチェックサム生成に関する計算の複雑性を低減することが望まれている。
【０００８】
本発明は、ヘッダ毎に変化しないヘッダのビットに関連する固定チェックサム情報を利用して、チェックサム生成の計算の複雑性を低減する。この固定チェックサム情報は、所望のチェックサム情報を生成するために、変化したヘッダのビットについての情報と一緒に使用され得る。ある実施形態によれば、変化しないヘッダのビットに関連する固定チェックサム符号化状態が、所望のチェックサムを生成するのに、変化するヘッダのビット自体と組合せて使用され得る。他の実施形態では、変化しないヘッダのビットに関連するチェックサム成分が、チェックサムを生成するのに使用され得る。固定チェックサム情報の使用は、チェックサム生成の計算の複雑性を好適に低減する。本発明の複雑性が低減されたチェックサム生成は、ヘッダ伸長器で再構成されるヘッダに関するチェックサムの計算に使用され得、圧縮器の端部で圧縮されたヘッダ情報と共に送信されるチェックサムを計算するのにも使用され得る。
【０００９】
＜詳細な説明＞
本発明では、所与のパケット・フローの間に、あるヘッダ情報が長い期間の間（あるいは全く）変化しないであろうと認識している。そのような変化しない（本明細書では定常あるいは固定とも称する）ヘッダ情報は、ＩＰのソース及びデスティネーションのアドレスを含んでいる。この変化しないヘッダ情報は、パケット・フローのヘッダに関連して計算される変化しないチェックサム成分の元となるであろう。従って、本発明は、様々なヘッダに対するチェックサムを生成するために、このヘッダ毎に変化しないあるいは固定のチェックサム成分を再利用し、ヘッダ毎に変化するヘッダのビットについての情報に繰り返して組合せる。これは概略的に図４に示されており、ここでコンバイナ４０は、固定チェックサム情報と変化するビットについての情報とのそれぞれの入力を受信し、それらから例えば、ＣＲＣ（巡回冗長コード）あるいはその相補的なチェックサムを生成する。
【００１０】
図５は、本発明によるチェックサム発生器の代表的実施形態の関連する部分を示した図である。図５のチェックサム発生器は、５１で全ヘッダを受信し、それに応答して５２でチェックサムを出力する。図５のチェックサム発生器は、図４の１４で示したようなパケット・プロセッサ内に設けられてもよい。その上、図５のチェックサム発生器は、図２に概略的に示したようにヘッダ圧縮と一緒に、あるいは図３に概略的に示したようにヘッダ伸長と一緒に使用されてもよい。このため、５１での全ヘッダは、図１及び２の１１で示されたような通信アプリケーションから受信した全ヘッダ（すなわち、コンテキストが更新されたヘッダ又は圧縮され再構成されるターゲット・ヘッダ）、又は、例えば、図３の３１で示された全ヘッダの推定値などの、ヘッダ伸長器によって生成された再構成された全ヘッダのいずれかを表している。
【００１１】
図５のチェックサム発生器は、全ヘッダ５１を受信し、そのビットを固定（ｓｔａｔｉｏｎａｒｙ）ビット部分Ｓ（図６も参照せよ）と過渡的（ｔｒａｎｓｉｅｎｔ：あるいは変化する）ビット部分Ｔとにソートするソータ４１を含んでいてもよい。固定ビット部分Ｓはパケット・フローの間に変化しないビットを含んでおり、過渡的ビット部分Ｔはパケット・フローの間に変化するビットを含んでいる。ソータ４１の出力は、全ヘッダがヘッダのコンテキスト更新に関連しているか、あるいは通常のヘッダ圧縮／伸長動作に関連しているかを示す更新／圧縮信号４６によって制御される、スイッチ４３に入力される。コンテキスト更新の間、信号４６は、従来の（例えば、ＣＲＣ）技術を使用して５２でのチェックサムＣＳを生成するチェックサム・レジスタ４５に全ヘッダがシフトされるように、スイッチ４３の位置を４３Ａに制御する。
【００１２】
図６に示されたように、ソータ４１は、固定ビットＳが過渡的ビットよりも前にチェックサム・レジスタに入るように、ヘッダのビットをソートする。固定ビットＳの全てがチェックサム・レジスタ４５に（スイッチ・ノード４３Ａを介して）シフトされたとき、チェックサム・レジスタ４５のその時点での符号化状態が４４の符号化状態格納部に格納される。この格納された符号化状態は、変化しない固定ビットに関連する固定のチェックサム符号化状態であり、従ってヘッダ圧縮／伸長の間の後続するチェックサム生成で再利用され得る。
【００１３】
ヘッダ圧縮／伸長動作の間、ソータ４１の出力がストリッパ４７に入力されるように、信号４６はスイッチ４３の位置を４３Ｂに制御する。ストリッパ４７は、過渡的ビットＴだけがチェックサム・レジスタ４５にシフトされるように、固定ビットＳを取り除く。しかしながら、過渡的ビットＴをチェックサム・レジスタ４５にシフトする前に、既に格納された固定チェックサム符号化状態が、符号化状態格納部４４から引き出され、チェックサム・レジスタ４５にロードされる。この符号化状態がチェックサム・レジスタ４５にロードされた後、ストリッパ４７から出力される過渡的ビットＴがチェックサム・レジスタ４５にシフトされ、これにより５２で所望のチェックサムが生成される。この既に格納された固定チェックサム符号化状態の利用は、このように５２で所望のチェックサムを生成するためにシフトされなければならないビット数を好適に低減する。
【００１４】
従来のＩＰプロトコルにおける図６の過渡的ビットの例は、ＩＰ−ＩＤ及びＲＴＰシーケンス番号を含んでいる。ＩＰ−ＩＤは送信されるパケット毎にユニークであり、ある場合には送信されるパケット毎に１だけインクリメントされるが、より一般的には１より多い数だけインクリメントされる。ＲＴＰシーケンス番号は、いつパケットがユーザに提供されるべきかを伝える。例えば、パケットが音声データを含んでいるとき、ＲＴＰシーケンス番号はいつ音声データがデコードされスピーカから出力されるべきかを伝える。
【００１５】
図７は、図５のチェックサム発生器によって実行され得る代表的動作を示している。７１で全ヘッダを受信した後、ヘッダのビットは７２で固定ビットと過渡的ビットにソートされる。７３で全ヘッダ（コンテキスト）更新であれば、７４で固定ビットはチェックサム・レジスタにシフトされる。７４で固定ビットがチェックサム・レジスタにシフトされれば、７５でチェックサム・レジスタの符号化状態が格納され、その後７６で過渡的ビットがチェックサム・レジスタにシフトされる。
【００１６】
７３でヘッダの更新がないとき（すなわち、通常のヘッダ圧縮／伸長動作）、７７で格納された符号化状態がチェックサム・レジスタにロードされ、７８で全ヘッダから固定ビットが取り除かれる。その後、７６で過渡的ビットがチェックサム・レジスタにシフトされる。
【００１７】
図６Ａは、ある実施形態において図５のソータ４１によって実行され得る別の代表的ソート動作を示している。図６Ａの例では、更に図６の過渡的ビットが変化の可能性に従って格納される。例えば、図６Ａの例では、ＩＰ−ＩＤ及びＲＴＰシーケンス番号の最下位ビットはＴ１、Ｔ２のいちばん左に置かれるであろう。対照的に、変化する可能性の最も低いビット、例えばＩＰ−ＩＤ及びＲＴＰシーケンス番号の最上位ビットは、図６Ａのいちばん右、すなわちビットＴＮとそれに隣接して配置されるであろう。このソーティング動作が使用されるとき、符号化状態格納部４４にはいくつかの符号化状態が格納される。例えば、コンテキスト更新で全ヘッダが受信されたとき、全ての固定ビットＳがチェックサム・レジスタ４５にシフトされた時点で符号化状態が格納され、図６Ａの過渡的ビットのそれぞれがチェックサム・レジスタ４５にシフトされた後にも符号化状態が格納される。ソータ４１は、４４に格納される符号化状態を生成するのに使用された過渡的ビットのソートされたバージョンの記録を保持している。この記録からソータ４１は、通常の圧縮／伸長動作の間に、格納された符号化状態を生成するのに使用された全ヘッダとは異なる現在の全ヘッダの最初の過渡的ビットの位置を、４２でストリッパ４７及び符号化状態格納部４４に指示する。そしてストリッパは全ての固定ビットと全ての変化しない過渡的ビットを取り除き、変化した過渡的ビットだけがチェックサム・レジスタ４５にシフトされればよいように、変化しないビットに対応した格納された符号化状態がチェックサム・レジスタ４５にロードされる。
【００１８】
図７と一緒に図７Ａを見ると、図５のチェックサム・レジスタで図６Ａのソーティング動作を実行する場合に実行され得る代表的動作が示されている。図７Ａでは、図７の７５で固定ビットに関連するチェックサム・レジスタの符号化状態が格納された後に、７０１で最初の過渡的ビットがチェックサム・レジスタにシフトされる。そして７０２でこの過渡的ビットに関連する符号化状態が格納され、７０３で全ての過渡的ビットがチェックサム・レジスタに格納されるまで、７０１及び７０２の処理が繰り返される。その後、動作は図７の７１に戻る。また、図７には、図７の７３での動作で「ＮＯ」となった場合に実行される７０４−７０６の動作が示されている。７０４で、最初の変化した過渡的ビットが識別され、７０５で、変化しないビットに対応する符号化状態がチェックサム・レジスタにロードされる。７０６で、最初に変化した過渡的ビットまでの全てのビットが全ヘッダから取り除かれ、シフトされたビット位置に関連した符号化状態を更新するためにシフトされたビットそれぞれに関連した符号化状態を格納する間に、７０１−７０３で残りの過渡的ビットがチェックサム・レジスタにシフトされる。
【００１９】
このように、図７Ａの動作によれば、伸長の間に生成される各再構成ヘッダについて、その再構成されるヘッダに対するチェックサムを計算する間に、新たな符号化状態が格納される。従って、各再構成ヘッダに対するチェックサムの計算を、既に再構成されたヘッダに対するチェックサムの計算（例えば、格納された符号化状態）に基づいたものとすることができる。これは（上記のように）各伸長動作の間に一連のヘッダ推定値を生成する伸長動作において特に有効であるが、これは新たなチェックサムの計算が新たな推定値それぞれについて必要となるからである。同様に、圧縮側で、圧縮されている新たなヘッダそれぞれについてのチェックサムの計算を、既に圧縮されたヘッダのチェックサムの計算（例えば、格納された符号化状態）に基づくものとすることができる。
【００２０】
上述のように、本発明によって生成されるチェックサムの一つの例はＣＲＣチェックサムである。このチェックサム及び他の巡回符号に関連する他のチェックサムは、所与のコードワードｃ１及びｃ２について、チェックサム生成関数ｆが以下に示す特性
ｆ（ｃ１＋ｃ２）＝ｆ（ｃ１）＋ｆ（ｃ２）　　　式１
を有するような、リニアな特性を有している。
【００２１】
このため、２つのコードワードを組合せて得られるチェックサムは、最初にコードワードを（モジュロ−２加算で）組合せ、チェックサムを計算する（式１の左側）か、あるいは各コードワードのチェックサムを計算してモジュロ−２加算で組合せる（式１の右側）かのいずれかによって得られる。この巡回チェックサム符号のリニア特性は、チェックサム生成の複雑さを低減するために本発明で利用される。
【００２２】
特に、ヘッダの更新が生じたとき、全ヘッダの全ての過渡的ビットが０にセットされ得、初期のチェックサムＣ０がこのように変更された全ヘッダから計算され得る。更に、全ヘッダにおける各過渡的ビットの位置についての１つの初期チェックサムから、別の初期チェックサムの組が計算され得る。これら更なる初期チェックサムのそれぞれは、１にセットされて初期チェックサムが計算される過渡的ビットを除いて、全ヘッダ内の全てのビットを０にセットして計算される。このように、Ｎ個の過渡的ビット（例えば３２−４８の過渡的ビット）について、ここではＣｅ１，Ｃｅ２，…，ＣｅＮで示すＮ個の初期チェックサムがある。これらのチェックサムは、予め計算され、必要なときに後で使用できるように格納されているのが好適である。
【００２３】
上記の観点から、ヘッダ圧縮／伸長動作の間にチェックサムを計算するとき、上述のチェックサムＣ０は、初期チェックサムＣｅ１，Ｃｅ２，…，ＣｅＮと以下の式に従って（モジュロ−２で）組合せられる。すなわち、
ＣＳ＝Ｃ０＋ｂ１Ｃｅ１＋ｂ２Ｃｅ２＋…＋ｂＮＣｅＮ　　　式２
ここで、ｂ１…ｂＮはＮ個の過渡的ビットの値（０又は１）を表しており、全ての加算はモジュロ−２である。
【００２４】
図８は、上記の式２に従ってチェックサムを計算できるチェックサム発生器の代表的実施形態の関連する部分を示す図である。図８のチェックサム発生器は、図５に関して上記で概略的に説明したのと同様に、ヘッダ圧縮器側又はヘッダ伸長器側のいずれかで使用できる。図８では、コンテキスト更新と一緒に全ヘッダが受信されると、スイッチ８１は位置８１ｂとなるように制御される。これにより、全ヘッダはチェックサム・レジスタ８３及びマスカー８２に供給される。チェックサム・レジスタ８３は、最初にコンテキスト更新に関連するチェックサムを生成し、このチェックサムＣＳＵをシフトレジスタ８６に出力する。その後、チェックサム・レジスタ８３は、マスカー８２から過渡的ビット全てが０にセットされた全ヘッダのマスクされたバージョンを受信する。チェックサム・レジスタ８３は、この全ヘッダのマスクされたバージョンから初期チェックサムＣ０を生成し、チェックサムＣ０をシフトレジスタ８６に出力する。このため、コンテキスト更新の間のチェックサム・レジスタ８３の動作の後、シフトレジスタ８６は全ヘッダ更新に関連したチェックサムＣＳＵと全ヘッダ更新のマスクされたバージョンに関連する初期チェックサムＣ０との両方を含んでいる。そして全ヘッダのコンテキスト更新に関連するチェックサムＣＳＵは、従来の使用に利用可能である。
【００２５】
ヘッダ圧縮／伸長動作の間、全ヘッダから固定ビットを取り除き、過渡的ビットｂ１，ｂ２，…，ｂＮを計算ロジック１００の入力８８に送出する、ストリッパ８６に全ヘッダが供給されるように、スイッチ８１が位置８１Ａとなるように制御される。計算ロジック１００は入力８９で、格納部８５から予め計算された初期チェックサムＣｅ１，Ｃｅ２，…，ＣｅＮを受信し、更に入力８４で初期チェックサムＣ０を受信する。計算ロジック１００は上記の式２を実行して所望のチェックサムＣＳを生成する。
【００２６】
図９は、図８の実施形態で実行され得る代表的動作を示す図である。９１−９２で全ヘッダ更新が受信されると、９３でチェックサムＣＳＵが生成される。そして、９４で過渡的ビットがマスクされる。過渡的ビットをマスクした後、９５で初期チェックサムＣ０が生成される。その後、９１で次の全ヘッダが待機する。９１−９２で全ヘッダがコンテキスト更新に関連していなければ、９６で過渡的ビットｂ１−ｂＮが供給され、９７で式２に従ってチェックサムＣＳが計算され、その後で９１で次の全ヘッダが待機する。
【００２７】
図１０は、図９に示した動作を実行し得る代表的擬似コードを示している。図１０で、Ｃ’は概して図８及び９におけるＣＳに対応している。
【００２８】
式２及び図８から１０からわかるように、Ｎ個の過渡的ビットを含むチェックサムの計算は、最大でＮ個のモジュロ−２加算（すなわち、ＸＯＲ演算）を必要とする。ある推定された全ヘッダから別の推定された全ヘッダに変化する過渡的ビットが比較的少ないアプリケーションでは、変化した過渡的ビットについてのみモジュロ−２加算が必要となることにも注意されたい。また、図８−１０の実施形態は、全ヘッダ内でのソーティングあるいはビットの並び替えを含んでいないことにも注意されたい。
【００２９】
式２におけるモジュロ−２加算の数は、過渡的ビットによって定義される１つ又は複数の値の最上位ビット（ＭＳＢ）は、非常にまれにしか変化しないという事実を利用することによって、一層低減することができる。例えば、８１９２のＲＴＰシーケンス番号は、ＲＴＰシーケンス番号が１６３８４に達するまで、１３個の最下位ビット（ＬＳＢ）だけが変化するビットパターンに対応する。このため、ＲＴＰシーケンス番号のビット１４−３２は、非常に長い時間間隔について変化しないままである。この結果、ＭＳＢに関連する初期チェックサムは、上述のチェックサムＣ０が計算されるのと同時に計算され得る。ＭＳＢに対応するこのチェックサムは、式２におけるモジュロ−２加算の数をＭＳＢの数より１つ少ない数だけ低減することを可能とする。過渡的ビットの所与の部分のＭＳＢに対する初期チェックサムの値を計算するこの手法は、そのＭＳＢが非常に長い期間変化しない値を定義する過渡的ビットのあらゆる部分に適用することができる。
【００３０】
ＲＴＰシーケンス番号を例に挙げると、ＲＴＰシーケンス番号が３２ビットであると仮定すると、最上位の１６ビットは非常に長い時間間隔について変化せず、ＲＴＰシーケンス番号がインクリメントされるだけであろう。コンテキスト更新が生じた際、上述のチェックサムＣ０に加えて初期チェックサムＣＳ０が計算され得る。チェックサムＣＳ０は、ＲＴＰシーケンス番号の最上位１６ビット以外の全てのヘッダのビットを０にセットして計算される。加えて、別の初期チェックサムＣＳ＋１が計算され得る。この後者のチェックサムは、ＭＳＢ部分を１だけインクリメントし、１６のＭＳＢ以外の全ヘッダのビットを０にして計算される。チェックサムＣＳ０は、ＭＳＢが変化する（すなわち、１だけ増える）まで全ヘッダのチェックサムを計算するのに使用され、その際チェックサムの計算においてＣＳ０はＣＳ＋１に置き換えられるであろう。このように、ＭＳＢが変化するまで、全ヘッダについてのチェックサムは以下のように計算され得る。
式３
ここで、ｊはチェックサムＣＳ０で計算されていない残りの過渡的ビットのビット位置を指し、全ての加算はモジュロ−２加算である。上述のＲＴＰシーケンス番号の例において、チェックサムＣＳ０は１６の過渡的ビット（すなわち、１６のＭＳＢ）を計算したが、従って式３は式２よりもモジュロ−２加算が１５少ない。上述のように、ＲＴＰシーケンス番号のＭＳＢ部分が変化すると、式３のＣＳ０が上述のチェックサムＣＳ＋１に置き換えられる。
【００３１】
過渡的ビットで表わされる１つ以上の他の値が、ＬＳＢ部分と非常にまれにしか変化しないＭＳＢ部分とに分割できると仮定すると、これらの値それぞれのＭＳＢについて、上述のチェックサムＣＳ０及びＣＳ＋１が計算され得る。以下の式４は、過渡的ビットによって表わされる２つの異なった値について、チェックサムＣＳ０（１）及びＣＳ０（２）をそれぞれ計算する、チェックサム計算を示している。
式４
ここで、ｊはチェックサムＣＳ０（１）及びＣＳ０（２）で計算されていない残りの過渡的ビットのビット位置を指し、全ての加算はモジュロ−２加算である。チェックサムＣＳ０（１）及びＣＳ０（２）の両方が１６個のＭＳＢを計算すると仮定すると、式４が必要とするモジュロ−２加算は式２よりも３０少なくなり、式３よりも１５少ない。このため、過渡的ビットが表す数が非常にまれにしか変化しないＭＳＢを有する限り、チェックサムＣＳを生成する計算の複雑性はかなり低減され得る。
【００３２】
図１１は、上記の式３及び４を実行し得るチェックサム発生器の代表的実施形態の関連する部分を示す図である。図１１のチェックサム発生器は、ヘッダのコンテキスト更新の間はスイッチ８１が位置８１Ｂとなるように制御され、全ヘッダがレジスタ１１３及びマスカー１１２に供給されるように、図８のスイッチ８１と一緒に使用することができる。チェックサム・レジスタ１１３は、上記で図８に関して説明したヘッダ更新のチェックサムＣＳＵを計算できる。このチェックサムＣＳＵは、チェックサム・レジスタ１１３からシフトレジスタ１１４へ出力され、そこで従来の使用が可能となる。チェックサムＣＳＵが生成された後、チェックサム・レジスタ１１３は、上述のチェックサムＣ０，ＣＳ０及びＣＳ＋１の計算に使用すべき全ヘッダを適切にマスクした（そしてＣＤ＋１の場合にはインクリメントした）バージョンをマスカー１１２から受信する。これらのチェックサムはまた、チェックサム・レジスタ１１２からシフトレジスタ１１４に出力される。チェックサム値ＣＳ０及びＣＳ＋１のユニークなセットが、過渡的ビットの複数の値のそれぞれのＭＳＢについて計算され得ることに注意されたい。
【００３３】
通常の圧縮／伸長動作の間に図８のスイッチ８１が位置８１Ａにあるとき、全ヘッダ（あるいは全ヘッダの推定値）は、全ての固定ビットとシフトレジスタ１１に格納されたＣＳ０及びＣＳ＋１のチェックサムのセットで計算される全ての過渡的ビットとを取り除く、ストリッパ１１６に供給される。このストリップ動作の後に残っている過渡的ビットは、シフトレジスタ１１４に格納されたチェックサムのセットに関連したＬＳＢ（及びおそらくはどのチェックサムのセットでも計算されていない他の何らかの過渡的ビット）を含んでいる。これらの計算されていない過渡的ビット（ｂｊ’ｓ）は、１１７の対応する（予め計算されて格納された）チェックサム（Ｃｅｊ’ｓ）と共に計算ロジック１１０に１１６で入力される。計算ロジックは、入力としてチェックサムＣ０及びチェックサムのセットＣＳ０及びＣＳ＋１を受信する。計算ロジック１１０は、式３又は式４のいずれかに従って所望のチェックサムＣＳを生成する。所与のＭＳＢのセットに対してＣＳ０又はＣＳ＋１のいずれを使用するかという問題は、８１Ａから受信したＭＳＢのセットのそれぞれを、関連するＣＳ０を生成するのに使用したＭＳＢの対応するセットと比較するコンパレータ１１８によって解決される。ＣＳ０を生成するのに使用したＭＳＢは、コンパレータ１１８による使用のためにマスカー１１２に格納され得る。ＭＳＢがコンパレータ１１８で一致したら、コンパレータの出力１１９は計算ロジック１１０にＣＳ０を使用する信号を送信し、それ以外ではＣＳ＋１が使用される。
【００３４】
図１２（図９と一緒に参照する）は、図１１のチェックサム発生器によって実行され得る代表的動作を示している。図９の９５でチェックサムＣ０が生成された後、１２１で選択されたＭＳＢ部分以外の全ての過渡的ビットはマスクされ、１２２でチェックサムＣＳ０が生成される。その後１２３で、選択されたＭＳＢ部分がインクリメントされ、１２４でチェックサムＣＳ＋１が生成される。１２１−１２４のステップが、１２５でチェックサムＣＳ０及びＣＳ＋１の全ての所望のセットが計算されたと判定されるまで繰り返される。その時、動作は図９の９１に戻る。図９の９２で「ＮＯ」と判定された後にも図１２での動作が開始し得る。すなわち、受信した全ヘッダがコンテキストの更新を構成するものではなかった場合、１２７でＬＳＢと他のいずれかの過渡的ビット（ｂｊ’ｓ）が得られる。１２８で、ＣＳ０／ＣＳ＋１それぞれのセットからチェックサムＣＳ０又はＣＳ＋１が選択される。その後１２９で、チェックサムＣＳが、例えば、式３又は４に従って計算され、その後動作は図９の９１に戻る。
【００３５】
図１３は、図１２に示した動作を実行可能な代表的擬似コードを示している。図１３において、Ｃ’は概して図１１及び１２のＣＳに対応する。図１３では単一のＣＳ０／ＣＳ＋１のセットだけを考慮しているが、ＣＳ０／ＣＳ＋１のセットそれぞれについて、３−１１行を重複させることで所望する数だけのセットを考慮することが容易に可能である。
【００３６】
図１１−１３の実施形態に関して、ＭＳＢの各セットについて、対応するＣＳ０／ＣＳ＋１のセットは周期的に更新される必要があることに注意されたい。しかしながら、そのような更新は非常にまれであり、費用がかからず、かつ必要とされる更新の頻度を減らすために、ＣＳ０／ＣＳ＋１のセットにＭＳＢの＋２のインクリメントに対応するチェックサム値、すなわち、ＣＳ＋２を加えるのも非常に容易である。
【００３７】
ヘッダの圧縮及び伸長を利用する従来の無線通信デバイスのチェックサム生成部分を、ソフトウェア、ハードウェア、あるいはソフトウェアとハードウェアの組合せで好適に変更して、図４−１３に示した実施形態を実現することは当業者には容易であろう。
【００３８】
上記では本発明の代表的実施形態を詳細に説明したが、これらの説明は様々な実施形態として実現可能な本発明の範囲を限定するものではない。
【図面の簡単な説明】
【図１】、
【図２】、
【図３】
無線通信デバイスで使用される従来のヘッダ圧縮／伸長及びチェックサム生成を示す図である。
【図４】
本発明によるチェックサム生成を示す図である。
【図５】
本発明によるチェックサム生成器の代表的実施形態の関連する部分を示す図である。
【図６】
図５のソータによって実行され得る１つの代表的動作を示す図である。
【図６Ａ】
図５のソータによって実行され得る別の代表的動作を示す図である。
【図７】
図５の実施形態で図６のソータ動作を実行したときに実行され得る代表的動作を示す図である。
【図７Ａ】
図５の実施形態で図６Ａのソータ動作を実行したときに実行され得る代表的動作を示す図である。
【図８】
本発明によるチェックサム生成器の他の代表的実施形態の関連する部分を示した図である。
【図９】
図８のチェックサム生成器によって実行され得る代表的動作示す図である。
【図１０】
図９に示した動作を実行させる代表的擬似コードを示す図である。
【図１１】
本発明によるチェックサム生成器の他の代表的実施形態の関連する部分を示した図である。
【図１２】
図１１のチェックサム生成器によって実行され得る代表的動作示す図である。
【図１３】
図１２に示した動作を実行させる代表的擬似コードを示す図である。
【図１】
2004504753.tif 000002
【図２】
2004504753.tif 000003
【図３】
2004504753.tif 000004
【図４】
2004504753.tif 000005
【図５】
2004504753.tif 000006
【図６】
2004504753.tif 000007
【図６Ａ】
2004504753.tif 000008
【図７】
2004504753.tif 000009
【図７Ａ】
2004504753.tif 000010
【図８】
2004504753.tif 000011
【図９】
2004504753.tif 000012
【図１０】
2004504753.tif 000013
【図１１】
2004504753.tif 000014
【図１２】
2004504753.tif 000015
【図１３】
2004504753.tif 000016
【国際公開パンフレット】
2004504753.tif 000017
2004504753.tif 000018
2004504753.tif 000019
2004504753.tif 000020
2004504753.tif 000021
2004504753.tif 000022
2004504753.tif 000023
2004504753.tif 000024
2004504753.tif 000025
2004504753.tif 000026
2004504753.tif 000027
2004504753.tif 000028
2004504753.tif 000029
2004504753.tif 000030
2004504753.tif 000031
2004504753.tif 000032
2004504753.tif 000033
2004504753.tif 000034
2004504753.tif 000035
2004504753.tif 000036
2004504753.tif 000037
2004504753.tif 000038
2004504753.tif 000039
2004504753.tif 000040
2004504753.tif 000041
2004504753.tif 000042
2004504753.tif 000043
2004504753.tif 000044
2004504753.tif 000045
2004504753.tif 000046
2004504753.tif 000047
【国際公開パンフレット（コレクトバージョン）】
2004504753.tif 000048
【国際調査報告】
2004504753.tif 000049
2004504753.tif 000050