(57)【要約】方法及び装置は、Ｎ個のバイナリビットのブロック内に分布する第１の極性値のビットのパターンに長さがＮビット未満のコードを割り当てるように構成される。基本的に方法は、（１）Ｎ個のバイナリビットのブロック中の第１の値のビット数を判定するステップと、（２）第１の値の判定したビット数に基づいて基数値を選択するステップと、（３）Ｎ個のバイナリビットのブロック中の第１の値の判定したビット数の特定の分布を表す変位値を決定するステップと、（４）基数値及び変位値を加算して合計を取得し、その合計を使用して割当てコードを形成するステップとを含む。基数値は、式Ｉ0＝NＣ1＋NＣ2＋NＣ3．．．NＣK-1を評価することにより選択されるのが好ましい。式中、ＫはＮ個のバイナリビットのブロック中の第１の値のビットの判定された数である。変位値を決定するステップは、（ビットＮがバイナリの第１の値ビットである場合）変位値Ｉ（Ｎ，Ｋ）をN-1ＣK＋Ｉ（Ｎ−１，Ｋ−１）として再帰的に決定するステップを含むのが好ましい。式中、Ｉ（Ｎ−１，Ｋ−１）はＮ−１ビット中の残りのＫ−１個の第１の値ビットから成るパターンの符号化である。一方、ビットＮが第１の値ビットでない場合、変位値を判定することは、変位値Ｉ（Ｎ，Ｋ）をＩ（Ｎ−１，Ｋ）として再帰的に決定するステップを含むの好ましい。式中、Ｋは残りのＮ−１ビット中のＫ個の第１の値ビットから成るパターンの符号化である。
2010517467.tif 000002
【特許請求の範囲】
【請求項１】
Ｎ個のバイナリビットのブロック内に分布する第１の値のビットのパターンに長さがＮビット未満のコードを割り当てるように構成される符号器（２０）であって、
前記Ｎ個のバイナリビットのブロック中の前記第１の値のビットの数に依存して基数値を選択する手段（２２）と、
前記Ｎ個のバイナリビットのブロック中の前記第１の値の前記ビットの数の特定の分布を表す変位値を決定する手段（２４）と、
前記基数値及び前記変位値を加算して合計を取得するように構成される加算器（２６）とを備えることを特徴とする符号器（２０）。
【請求項２】
前記基数値を選択する手段（２２）は、Ｋが前記Ｎ個のバイナリビットのブロック中の前記第１の値のビットの判定された数である場合に、式Ｉ0＝NＣ1＋NＣ2＋NＣ3．．．＋NＣK-1を評価するように構成されることを特徴とする請求項１記載の符号器（２０）。
【請求項３】
前記変位値を決定する手段（２４）は、ビットＮがバイナリの第１の値ビットである場合、Ｉ（Ｎ−１，Ｋ−１）がＮ−１ビット中の残りのＫ−１個の第１の値ビットから成るパターンの符号化であるときに、前記変位値Ｉ（Ｎ，Ｋ）をN-1ＣK＋Ｉ（Ｎ−１，Ｋ−１）として再帰的に決定し、ビットＮが第１の値ビットでない場合、Ｋが前記残りのＮ−１個のビット中のＫ個の第１の値ビットから成るパターンの符号化であるときに、前記変位値Ｉ（Ｎ，Ｋ）をＩ（Ｎ−１，Ｋ）として再帰的に決定するように構成されることを特徴とする請求項１記載の符号器（２０）。
【請求項４】
複数の可能な符号化技術の呼び出しの順番を選択するように構成される符号器技術選択器（７０）を更に具備し、
前記符号化技術のうち少なくとも１つは前記基数選択手段及び前記変位値決定手段を使用して実現されることを特徴とする請求項１記載の符号器（２０（８））。
【請求項５】
前記複数の実行可能な符号化技術のうちワードに対して実際に利用された符号化技術に関する表示を前記割り当てられたコードに含めるように構成される符号化技術選択指標（７２）を更に具備することを特徴とする請求項４記載の符号器（２０（８））。
【請求項６】
Ｎ個のバイナリビットのブロック内に分布する第１の値のビットのパターンに長さがＮビット未満のコードを割り当てる方法であって、
（１）前記Ｎ個のバイナリビットのブロック中の前記第１の値のビットの数を判定するステップと、
（２）前記第１の値のビットの前記判定された数に基づいて基数値を選択するステップと、
（３）前記Ｎ個のバイナリビットのブロック中の前記第１の値のビットの前記判定された数の特定の分布を表す変位値を決定するステップと、
（４）前記基数値及び前記変位値を加算して合計を取得し、前記合計を使用して割当てコードを形成するステップと
を有することを特徴とする方法。
【請求項７】
前記第１の値はバイナリ「１」であることを特徴とする請求項６の方法。
【請求項８】
前記Ｎ個のバイナリビットのブロックの各ビットに対応する前記ブロックのパケットにおいて誤りが検出されたかを示すために前記ビットを使用するステップを更に含むことを特徴とする請求項６記載の方法。
【請求項９】
前記割当てコードとして前記合計を使用することを更に含むことを特徴とする請求項６記載の方法。
【請求項１０】
前記基数値を選択する前記ステップ（２）は、Ｋが前記Ｎ個のバイナリビットのブロック中の前記第１の値のビットの前記判定された数である場合に、式Ｉ0＝NＣ1＋NＣ2＋NＣ3．．．＋NＣK-1を評価するステップを含むことを特徴とする請求項６記載の方法。
【請求項１１】
前記変位値を判定する前記ステップ（３）は、
前記変位値をゼロに初期化するステップと、
前記ビットブロックに残る前記第１の値のビット数がゼロである場合にゼロの変位値を返すステップと、
前記ビットブロック中の前記第１の値のビット数が非ゼロであり且つ前記ビットのブロックの第１のビットが前記第１の値のビットである場合、
Ｋが前記Ｎビットブロック中の前記第１の値のビットの前記判定された数であるときに前記変位値にNＣKを加算するステップと、
残りのＮ−１ビット中の残りのＫ−１個の第１の値ビットから成るパターンを表すように決定される前記変位値を加算する動作とを実行するステップと、
前記ビットのブロックの前記第１のビットが前記第１の値でない場合に、前記残りのＮ−１ビット中で位置を特定されるＫ個の第１の値ビットから成るパターンと同様に決定される前記変位値を前記変位値に加算するステップとを含むことを特徴とする請求項６記載の方法。
【請求項１２】
前記変位値を判定する前記ステップ（３）は、
ビットＮがバイナリの第１の値ビットである場合、Ｉ（Ｎ−１，Ｋ−１）がＮ−１ビット中の残りのＫ−１個の第１の値ビットから成るパターンの符号化であるときに、前記変位値Ｉ（Ｎ，Ｋ）をN-1ＣK＋Ｉ（Ｎ−１，Ｋ−１）として再帰的に決定するステップと、
ビットＮが第１の値ビットでない場合、Ｋが前記残りのＮ−１ビット中のＫ個の第１の値ビットから成るパターンの符号化であるときに、前記変位値Ｉ（Ｎ，Ｋ）をＩ（Ｎ−１，Ｋ）として再帰的に決定するステップとを含むことを特徴とする請求項６記載の方法。
【請求項１３】
前記割当てコードが最大許容値より大きいかを判定し、前記割当てコードが前記最大許容値より大きい場合に前記割当てコードを前記最大許容値に設定するステップを更に含むことを特徴とする請求項６記載の方法。
【請求項１４】
ステップ（１）の前に、前記Ｎビットのブロックを符号化するためにランレングス符号化を使用するステップと、前記ランレングス符号化を使用することにより所望の長さより短いビットの符号化ブロックが生成されない場合、
ステップ（２）乃至（４）を実行して前記割当てコードを取得するステップとを更に含むことを特徴とする請求項６記載の方法。
【請求項１５】
ランレングス符号化が前記Ｎビットのブロックを符号化するために使用されたかを示すために前記符号化ブロックに指標を追記するステップを更に含むことを特徴とする請求項１４記載の方法。
【請求項１６】
ステップ（１）乃至（４）から取得される前記割当てコードが最大許容値以上である場合、ランレングス符号化を使用して前記Ｎビットブロックを符号化し、符号化ブロックを生成し、
オプションとして、前記符号化ブロックが最大許容ビット長より大きい場合、前記割当てコードを前記最大許容値に設定し、
オプションとして、前記符号化ブロックが最大許容ビット長より大きくない場合、前記ランレングス符号化ブロックを前記割当てコードとして使用することを特徴とする請求項６記載の方法。
【請求項１７】
ランレングス符号化が前記割当てコードを生成するために使用されたかを示す前記指標を追記することを更に含むことを特徴とする請求項１６記載の方法。
【請求項１８】
ステップ（１）の前に、前記Ｎビットブロック中の第１の極性のビットの全ての位置が前記Ｎビットの複数の特定のサブセットのうちの１つにおいて特定されるかを判定し、特定されない場合にステップ（１）乃至（４）を実行するステップを更に含むことを特徴とする請求項６記載の方法。
【請求項１９】
前記Ｎビットブロック中の前記第１の極性の前記ビットの全ての位置が前記Ｎビットの特定のサブセットにおいて特定される場合、使用されたサブセットを示し且つサブセットが使用されたことを示す指標に追記される前記ビットのサブセットを前記割当てコードとして使用することを特徴とする請求項１８記載の方法。
【請求項２０】
Ｎ個のバイナリビットのブロック内に分布する第１の値のＫビットのパターンを取得するために長さがＮビット未満の割当てコードを復号化するように構成される復号器（５０）であって、
（１）受信コードＭ＝Ｉ0＋Ｉを比較値NＣ1，NＣ2．．．NＣKmaxと連続して比較する動作と、
（２）再構成される前記Ｎビットワード中のＫ個の前記第１の値ビットを判定するために動作（１）の比較結果を使用する動作と、
（３）厳密にＫ個の前記第１の値ビットから成る特定のパターンに割り当てられた変位値（Ｉ）を決定するために、動作（１）の前記比較結果からＭの残差値を使用する動作とを実行するように構成されることを特徴とする復号器（５０）。
【請求項２１】
前記復号器（５０）は、変位値（Ｉ）がN-1ＣK以下である場合、
ビット（Ｎ）が前記第１の値を有するときに前記比較値を減算し且つ残りをN-2ＣK-1と比較してビット（Ｎ−１）を判定する再帰動作と、
ビット（Ｎ）が前記第１の値ビットでないときにN-1ＣK-1と比較する再帰動作とを実行するように更に構成されることを特徴とする請求項２０記載の復号器。
【請求項２２】
Ｎ個のバイナリビットのブロック内に分布する第１の値のＫビットのパターンを取得するために長さがＮビット未満の割当てコードを復号化する方法であって、
（１）受信コードＭ＝Ｉ0＋Ｉを比較値NＣ1，NＣ2．．．NＣKmaxと連続して比較するステップと、
（２）再構成される前記Ｎビットワード中のＫ個の前記第１の値ビットを判定するために動作（１）の比較結果を使用するステップと、
（３）厳密にＫ個の前記第１の値ビットから成る特定のパターンに割り当てられた変位値（Ｉ）を決定するためにステップ（１）の前記比較結果からＭの残差値を使用するステップと
を有することを特徴とする方法。
【請求項２３】
変位値（Ｉ）がN-1ＣK以下である場合、
ビット（Ｎ）が前記第１の値を有するときに前記比較値を減算し且つ残りをN-2ＣK-1と比較してビット（Ｎ−１）を判定する再帰動作と、
ビット（Ｎ）が前記第１の値ビットでない時にN-1ＣK-1と比較する再帰動作とを更に含むことを特徴とする請求項２２記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタルデータのブロックの圧縮又は符号化に関し、特に、バイナリ値の特定の分布を含むブロックの圧縮又は符号化に関する。
【背景技術】
【０００２】
パケットを生成した送信機が正常に受信されなかった任意のパケットを再送できるように、パケットを正常に受信したことの確認応答を送信機に送出することは、パケットデータ送信において一般的である。場合によっては、（例えば）特に軌道上の衛星を介する送信遅延のため、パケット毎の確認応答を行なうのは効率的でない。その代わり、パケットデータ受信機等の受信機は、Ｎ個のデータパケット（「コンテナ」と呼ばれる）のグループを発信側送信機から受信する。受信機は、誤り検出を使用して各復号化データパケットを正確なもの又は不正確なものとして分類する。パケットが正確なものである場合、Ｎビット確認応答ワードの対応するビットが第１の値（例えば、０）に設定され、パケットが不正確なものである場合、ビットは第２の値（例えば、１）に設定される。その受信機は、確認応答ワードの再構成を含むか又は許可し、そうしてどのパケットが再送される必要があるかを発信側送信機に通知するように、関連する送信機に発信側送信機と関連する受信機に対して符号化メッセージを送信させる。
【０００３】
従来技術において、そのような確認応答ワードを送信する２つの一般的な方法が周知である。第１の方法は、確認応答ワード全体を送信し、巡回冗長検査（ＣＲＣ）コードを追加して誤りから保護する。第２の周知の方法は、確認応答ワードを圧縮するためにランレングス符号化を採用する。ランレングス符号化は、誤りパターンが集中するという予想を利用するため、連続するいくつかの０の中には連続するいくつかの１が点在すると予想される。実際にはこれは、地上移動通信において発生する可能性があるように、遅いレイリーフェージング信号のために予想される誤りパターンである。しかし、ライスフェージング環境で限界の信号レベルで動作する衛星通信において、誤りのパターンは異なる。誤りは連続して発生するとは限らず、無作為に分布する。
【０００４】
しかし、誤り数がある閾値より少ない場合、可能な誤りパターンの数はＮビットより少ないビットを使用して記述可能であり、より大きなサイズのコンテナが同一メッセージ長を使用して確認可能になる。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
従って、望まれること及び本発明の目的は、Ｎビット中のＫ個の極性値から成る特定のパターンにＮビットより少ない数を割り当て、そのＮビットより少ない数が簡単に復号できてＮビットワードを生成するような１つ以上の方法、装置、システム及び技術である。
【課題を解決するための手段】
【０００６】
方法及び装置は、長さがＮビット未満のコードを、Ｎ個のバイナリビットのブロック内に分布する第１の極性値のビットパターンに割り当てるように構成される。基本的にこの方法は、（１）Ｎ個のバイナリビットのブロック中における第１の値のビット数を判定することと、（２）判定した第１の値のビット数に基づいて基数値を選択することと、（３）Ｎ個のバイナリビットのブロック中において判定された第１の値のビット数の特定の分布を表す変位値を判定することと、（４）基数値及び変位値を加算して合計を取得し、その合計を使用して割当てコードを形成することとを含む。
【０００７】
基数値は、式Ｉ0＝NＣ1＋NＣ2＋NＣ3．．．＋NＣK-1を評価することにより選択されるのが好ましい。式中、ＫはＮ個のバイナリビットのブロック中において判定された第１の値のビット数である。
【０００８】
変位値を決定することは、（ビットＮが第１の値のバイナリビットである場合）変位値Ｉ（Ｎ，Ｋ）をN-1ＣK＋Ｉ（Ｎ−１，Ｋ−１）として再帰的に決定することを含むのが好ましい。式中、Ｉ（Ｎ−１，Ｋ−１）は、Ｎ−１ビット中の残りのＫ−１個の第１の値ビットから成るパターンの符号化である。一方、ビットＮが第１の値ビットでない場合、変位値を決定することは、変位値Ｉ（Ｎ，Ｋ）をＩ（Ｎ−１，Ｋ）として繰り返し判定することを含むのが好ましい。式中、Ｋは残りのＮ−１ビット中のＫ個の第１の値ビットから成るパターンの符号化である。
【０００９】
いくつかの実施例及び態様において、割当てコードが最大許容値より大きいと判定される場合、割当てコードは、符号化の失敗を示すものとして最大許容値に設定される。
【００１０】
いくつかの実施例及び態様は、例えば、本明細書により説明されるか又は含まれる符号化／圧縮技術又は別の符号化／圧縮技術（例えば、ランレングス符号化等）等の符号化／圧縮技術、あるいはデータのブロックの内容を考慮して通信する別の方法を選択する論理又は装置により構成される。例えば、符号器技術選択器は、事前定義済みの順番で複数の実行可能な符号化又は圧縮技術を採用するために採用及び構成される。所定の順番及び達成された成功に基づいて、符号化技術選択指標は、メッセージ又は確認応答ワードにオプションとして含まれ、複数の実行可能な符号化技術のうち実際に利用された技術に関して受信機又は復号器に通知する。
【００１１】
符号器技術選択器／選択は、別の符号化／圧縮技術ではなく、ひとつの種類の符号化／圧縮技術の使用のために特に準備されたか又は適切な条件又は状況を判定又は評価する論理又は機能性を更に含んでもよい。例えば、符号器技術選択器の一実施例はブロックを解析し、誤りビット（例えば第１の極性のビット）の全ての位置が、前記Ｎビットの複数の特定のサブセットのうちの１つにおいて特定されるかを判定する。Ｎビットブロック中の誤りビット（例えば、第１の極性ビット）の全ての位置が前記Ｎビットの特定のサブセットにおいて特定される場合、符号器は、指標に付加された、ビットの誤りが検出されたサブセットを、割当てコードとして使用する。その指標は、使用されたサブセットを示し且つ別の符号化技術とは対照的にサブセットが実際に使用されたことを示す役割を果たす。
【００１２】
本明細書により説明されるか又は含まれる実施形態の例示及び説明は、確認応答メッセージ又はワードの符号化／圧縮に関するが、これに限定されない。メッセージ／ワードのビットはブロックのパケットに対応し、ビットはイベント（例えば、誤り）がパケットにおいて／パケットに対して発生したかを示す。
【００１３】
いくつかの面において、技術が符号器及び符号器の動作のモードの種々の実施形態を含む一方で、他の面において、技術は復号器及び復号器を動作させる方法、並びに（他の実施形態及びモードにおいて）符号器及び復号器の双方を採用する通信システムを含む。
【図面の簡単な説明】
【００１４】
本発明の上記目的、特徴及び利点、並びに他の目的、特徴及び利点は、添付の図面において示されるような好適な実施形態の以下の更に特定の説明から明らかとなるだろう。図中、図中符号は同一の部分を示す。図面は、必ずしも縮尺どおりではなく、本発明の原理を示すことに重点が置かれている。
【図１】符号器の第１の実施形態を示す概略図である。
【図２】符号器の第２の実施形態を示す概略図である。
【図３】符号化処理のモードの一例と関連して実行される代表的な動作の限定的でない例を示すフローチャートである。
【図４】符号器の第３の実施形態を示す概略図である。
【図５】復号器の第１の実施形態を示す概略図である。
【図６】復号化処理のモードの一例と関連して実行される代表的な動作の限定的でない例を示すフローチャートである。
【図７】第１のタイプのメッセージの形式を示す図である。
【図８】符号器の別の実施形態を示す概略図である。
【図９】符号化技術の動的な選択を有する符号化処理のモードの一例と関連して実行される代表的な動作の限定的でない例を示すフローチャートである。
【図１０】符号化技術の動的な選択を有する符号化処理のモードの別の例と関連して実行される代表的な動作の限定的でない例を示すフローチャートである。
【図１１】割当てコードが最大許容値より大きいと判定された時に実行される代表的な動作の限定的でない例を示すフローチャートである。
【図１２】符号化技術の動的な選択を有する符号化処理のモードの別の例と関連して実行される代表的な動作の限定的でない例を示すフローチャートである。
【図１３】ブロックサブセットに本質的に限定される第１の極性ビットを有するブロックの一実施形態を示す図である。
【図１４】図１２のモードと共に使用するのに適切なメッセージ又はワードの一例を示す図である。
【図１５】第１の通信ユニット及び第２の通信ユニットを含む通信システムの一実施形態を示す概略図である。
【発明を実施するための形態】
【００１５】
以下の説明において、限定しない説明の目的で、本発明を完全に理解するために特定のアーキテクチャ、インタフェース、技術等の特定の詳細を示す。しかし、本発明がそれらの特定の詳細とは異なる他の実施形態において実現されてもよいことは、当業者には明らかであろう。すなわち、当業者は、本明細書に明確に説明又は図示しないが、本発明の原理を組み込み且つ趣旨の範囲内に含まれる種々の構成を考案できるだろう。いくつかの例において、周知のデバイス、回路及び方法の詳細な説明は、不必要な詳細により本発明の説明を曖昧にしないために省略される。本発明の原理、面及び実施形態、並びにそれらの特定の例を説明する本明細書における全ての表現は、構造的及び機能的な等価物を含むことを意図する。更に、そのような等価物が現時点で周知の等価物及び今後開発される等価物、すなわち構造に関係なく同一の機能を実行する開発される任意の要素を含むことを意図する。
【００１６】
従って、例えば、本明細書のブロック図が技術の原理を組み込む回路網の概念図を表せることは、当業者には理解されるだろう。同様に、任意のフローチャート、状態遷移図及び擬似コード等は、コンピュータ可読媒体において本質的に表されてもよく且つコンピュータ又はプロセッサが明示的に示されているか否かに関わらずコンピュータ又はプロセッサにより実行されてもよい種々の処理を表すことが理解されるだろう。
【００１７】
「プロセッサ」又は「制御器」とラベル付けされるか又は説明される機能ブロックを含む種々の要素の機能は、専用ハードウェア及び適切なソフトウェアと関連してソフトウェアを実行できるハードウェアを使用することにより提供されてもよい。プロセッサにより提供される場合、それらの機能は単一の専用プロセッサ、単一の共有プロセッサ又は複数の個別のプロセッサにより提供されてもよい。複数の個別のプロセッサの一部は共有されるか又は分散されてもよい。更に、用語「プロセッサ」又は「制御器」の明示的な使用は、ソフトウェアを実行できるハードウェアのみを示すものとして解釈されるべきではなく、デジタル信号プロセッサ（ＤＳＰ）ハードウェア、ソフトウェアを格納する読み出し専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）及び不揮発性記憶装置を含んでもよいが、それらに限定されない。
【００１８】
図１は、Ｎビットワードを受信する（矢印２１で表されるように）符号器２０の一実施形態を示す。符号器２０は、特定の種類のビット極性（例えば、バイナリ「１」等の第１の値ビット又は第１の極性値）の発生の頻度がＮの分数（たとえばＥ／Ｎ）に限定される場合、ＮビットワードをＮビットより少ないビット数に符号化するように構成される。図１の符号器２０の例は、基数選択ユニット２２、変位値決定ユニット２４及び加算器２６を含む。以下に更に詳細に説明するように、基数選択ユニット２２は、Ｎ個のバイナリビットのブロック中の第１の値（例えば、第１の極性）のビット数に依存して基数値を選択するように構成される。変位値決定ユニット２４は、Ｎ個のバイナリビットのブロック中の第１の値のビット数の特定の分布を表す変位値を決定するように構成される。加算器２６は、基数値及び変位値を加算して合計を取得するように構成される。その合計は、矢印２８により示されるように「割当てコード」として符号器２０により割り当てられるコード等の符号器２０により出力されるコード（例えば、Ｎビット符号化値より小さい）を取得するために使用されるが、その合計は符号器２０により出力されるコードであるのが好ましい。
【００１９】
図２は、符号器２０（２）が分数チェッカユニット３０をオプションとして更に含む一変形例を示す。特に、分数チェッカユニット３０は、第１の値ビット（例えば、バイナリ「１」）の数が許容可能な分数Ｅ／Ｎより大きいかを判定するように構成される。第１の値ビット数が許容可能な分数Ｅ／Ｎより大きいと分数チェッカユニット３０が判定した場合、矢印３２により示されるように、分数チェッカユニット３０は、第１の値ビットの数が符号化可能なビット数より多かったことを示すメッセージ又はコードを生成又は送出又はその両方を行うことができる。
【００２０】
図３は、符号器（符号器２０又は本明細書で説明する他の符号器）により実行される代表的な動作の限定的でない例を示す。動作３−１は、符号器２０に入力されたＮビットワードの第１の値ビット数Ｋ（例えば、バイナリ「１」のビット等の第１の極性ビット）をカウントすることを示す。動作３−２は、Ｎ個のバイナリビットのブロック中の第１の値のビット数Ｋに依存して基数値Ｉ0を決定又は選択することを示す。動作３−３は、変位値Ｉを決定することを示す。
【００２１】
次に、動作３−２を更に詳細に説明する。最初に一般的な表現を展開する前にいくつかの例を参照して説明する。Ｋが１である場合、Ｎビット中の第１の値ビット（例えばバイナリ「１」）の生じ得るパターンの数はＮである。従って、符号化は１からＮの間の数である。ちなみに、数０は、Ｎビットの入力ワード中に第１の値ビットが存在すること（例えば、デジタル「１」がない）を示すために使用される。
【００２２】
Ｋが２の場合、生じ得るビットパターンの数はNＣ2であるため、厳密に２つの第１の値ビットから成る特定のパターンは１からNＣ2の間の数で記述されてもよい。２つの第１の値ビットから成るパターンを記述するのに使用されるコードが１つの第１の値ビットから成るパターンを記述するのに使用されるコードと重複しないことを保証するために、その数に対して使用されるコードはＮを加算することにより１に対して使用される最大コードを超えて変位される。従って、２つの誤りのパターンに対するコードはＮ＋１とＮ＋NＣ2との間である。同様に、Ｎビットのワード中の厳密に３つの第１の値ビットから成るパターンを記述するのに使用されるコードは、Ｎ＋NＣ2＋１とＮ＋NＣ2＋NＣ3との間である。
【００２３】
従って、一般に、厳密にＫ個の第１の値ビットから成るパターンを記述するのに使用されるコードは、NＣ1＋NＣ2＋NＣ3．．．＋NＣK-1＋１とNＣ1＋NＣ2＋NＣ3．．．＋NＣKとの間になる。NＣKは、合計Ｎ個の中からＫ個を選択するためのあり得る方法の数に対する標準的な数学的表記法であり、順列及び組合せの理論から得られる。第１の値ビット（例えば、「１」）に等しいＫビットを有するＮビットのバイナリワードの数は、単純に合計ＮビットからそのＫビットを選択する、あり得る方法の数である。NＣKの値は、式１［Ｎの階乗はＫの階乗及び（Ｎ−Ｋ）の階乗で除算される］又は式２（式１及び式２の双方において、またここで使用されるように、Ｎ及びＫはともに負でない整数である）で書かれる。例えば、5Ｃ2は（５×４×３）／（２×１）＝３０である。
【００２４】
式１：NＣK＝Ｎ！／［（Ｎ−Ｋ）！Ｋ！］
式２：NＣK＝Ｎ（Ｎ−１）（Ｎ−２）．．．（Ｎ−Ｋ＋１）／Ｋ（Ｋ−１）（Ｋ−２）．．．１
符号化の結果又は出力コードは基数＋変位、すなわちＩ0＋Ｉで書かれてもよい。式中、基数Ｉ0＝NＣ1＋NＣ2＋NＣ3．．．＋NＣK-1であり、変位（Ｉ）として周知の値は１〜NＣKの範囲にある。従って、動作３−２では、基数値Ｉ0はＩ0＝NＣ1＋NＣ2＋NＣ3．．．＋NＣK-1として選択される。
【００２５】
図３の符号化モードの動作３−３は、上述のように、変位値Ｉを決定することを含む。特に、変位値（Ｉ）は、２つの例に従って計算又は決定される。第１の例として、Ｎビット入力ワードのビットＮが第１の値ビット以外の値を有する場合（例えば、第１の値ビットがバイナリ「１」である場合にビットＮがバイナリ「０」である場合）、Ｋ個の第１の値ビット（例えば、バイナリ「１」）はビット１〜Ｎ−１に含まれる必要がある。従って、Ｎビット入力ワードの残りのＮ−１ビット中のＫ個の第１の値ビット（１）から成る生じ得るパターンはN-1ＣK個存在する。一方、第２の例として、入力ワードのビットＮが第１の値（例えば、バイナリ「１」）である場合、Ｋ−１個の第１の値ビットは残りのＮ−１ビットに含まれる。従って、この第２の例において、Ｎ−１ビット中のＫ−１個の第１の値ビットから成るあり得るパターンはN-1ＣK-1個存在する。
【００２６】
式３は、恒等式を提供する。
【００２７】
式３：NＣK＝N-1ＣK＋N-1ＣK-1
式３の恒等式は、昇順の数Ｉが、Ｎビット中の厳密にＫ個の第１の値ビットから成る特定のパターンに割り当てられる順番を規定するために使用される。
【００２８】
Ｉ（Ｎ，Ｋ）により示すように、Ｎビット中のＫ個の第１の値ビットから成るパターンの索引が符号化され、Ｉは以下に説明するように再帰的に計算されてもよい。
【００２９】
図３のサブ動作３−３−１に示すように、ビットＮがバイナリの第１の値ビット（例えば、バイナリ「１」）である場合、Ｉ（Ｎ，Ｋ）はＩ（Ｎ，Ｋ）＝N-1ＣK＋Ｉ（Ｎ−１，Ｋ−１）により与えられる。式中、Ｉ（Ｎ−１，Ｋ−１）はＮ−１ビット中の残りのＫ−１個の第１の値ビットから成るパターンの符号化である。
【００３０】
一方、図３のサブ動作３−２に示すように、ビットＮが第１の値ビットでない場合（例えば、ビットＮがバイナリ「０」である場合）、Ｉ（Ｎ，Ｋ）＝Ｉ（Ｎ−１，Ｋ）である。式中、Ｋは残りのＮ−１ビット中、Ｋ個の第１の値ビットから成るパターンの符号化である。
【００３１】
一実現例によると、上述の方法の動作において必要なNＣKの値は、実時間計算を回避するために、事前に計算され、Ｎ及びＫの全ての値に対するルックアップテーブルＴ（Ｎ，Ｋ）に格納されてもよい。図４は、符号器２０（４）がＴ（Ｎ，Ｋ）ルックアップテーブル４０を含む一実施形態を示す。
【００３２】
例として図５に示されるように、この技術の別の面は、符号器２０又は上述により説明されるか又は含まれる別の符号器等の符号器から受信されるコードを復号化するように構成される復号器５０に関する。復号器５０は、Ｎ及びＫの値が事前設定されるか又は伝達されている。復号器５０は、基数値復号化ユニット５２及び変位値復号化ユニット５４を含む。復号器５０は、コードを受信し（矢印５６により示される）、復号化ワードを出力する（矢印５８により示される）。
【００３３】
復号器５０等の復号器により実行される代表的ではあるが限定的でない動作の例を図６に示す。図６の一例の態様において、動作６−１は、受信コードＭ＝Ｉ0＋Ｉを比較値NＣ1，NＣ2，．．．NＣKmaxと連続して比較することを含む。動作６−２は、選択された比較値がＭより小さい場合に適切な選択された比較値をＭから減算することを含む。Ｍが比較値NＣKより小さい場合、動作６−３において、添え字Ｋは再構成されるＮビットワード中の第１の値ビット数を与え、動作６−４において、Ｍの残差値は変位値（Ｉ）に等しく、コードは厳密にＫ個の第１の値ビット（例えば、バイナリ「１」）から成る特定のパターンに割り当てられる。動作６−５において、変位値（Ｉ）は復号化され、ＩをN-1ＣKと比較することにより対応するパターンを判定する。変位値（Ｉ）がN-1ＣK以下である場合、ビット（Ｎ）は第１の値ビットではない。変位値（Ｉ）がN-1ＣK以下でない場合、ビット（Ｎ）は第１の値ビットである。ビット（Ｎ）が第１の値を有する場合、比較値が減算され、手順はその残りをN-2ＣK-1と比較してビット（Ｎ−１）を判定する。しかし、ビット（Ｎ）が第１の値ビットでない場合、次の比較はN-1ＣK-1に対して行なわれる。手順は、Ｎビットパターンの全てのビットが再作成されるまで繰り返される。
【００３４】
表１は、Ｎビットの入力ワード毎に符号化関数（ＥＮＣＯＤＩＮＧ  ＦＵＮＣＴＩＯＮ）の一例及び復号化関数（ＤＥＣＯＤＩＮＧ  ＦＵＮＣＴＩＯＮ）の一例を呼び出す論理又はルーチンの一実現例を示すテストプログラムの一例である。ここでＮは最大２４ビットである。２４ビットは、標準的な整数ワードの３２ビット最大長さ以内である。より長いワードに対して動作する命令又はより長いワード長さ演算を実現するソフトウェアプログラムによりマシンを使用して、任意の長さのワードを、本明細書で開示される情報を使用して平均的な技術を有するユーザにより行なわれるそれらのルーチンの適切な変更により符号化することができる。
【００３５】
表２は、本発明の圧縮アルゴリズムを実行する再帰的整数関数（ＲＥＣＵＲＳＩＶＥ  ＩＮＴＥＧＥＲ  ＦＵＮＣＴＩＯＮ）に対する論理又はルーチンの一実現例を示す。表３は、復号化関数（ＤＥＣＯＤＩＮＧ  ＦＵＮＣＴＩＯＮ）の一例に対する論理又はルーチンの一実現例を示す。実現例として、表１乃至表３の論理及びルーチンは、ＦＯＲＴＲＡＮでコーディングされる。他の種類のコーディング、並びに論理又はルーチン又はその両方が代わりに提供されてもよいことは理解されるだろう。
【００３６】
更に他の実施形態及び態様は、（１）上述により含まれる符号化／圧縮技術等の符号化／圧縮技術又は、（２）Ｎビット中のＫ個の第１の値ビットから成るパターンを圧縮するための他の符号化／圧縮技術（例えば、一般的なランレングス符号化アルゴリズム）を選択すること（例えば、動的に選択すること）を含む。最適な圧縮を達成する技術が選択されるか、あるいはいずれの技術も有効ではない場合にはいずれも採用されない。全ての第１の値ビットの位置がワードの特定の部分において特定される場合、符号化／圧縮技術を動的に選択することは特に有益である。動的な選択を含む実施形態の例示及び説明の限定的でない例は確認応答ワードであり、そのワードのビットはブロックのパケットに対応し、ビットはパケットが誤りを含むか否かを示す。
【００３７】
例えば、６４ビットより少ないビットを使用して６４個のデータパケットのうち誤って受信されたデータパケットに関する情報を搬送することが必要であると仮定する。ビット数を減少することは、誤り訂正又は誤り検出コード、あるいはその双方の使用に対応するために有用である場合が多い。誤り訂正及び誤り検出コードの双方ともビット数を拡大する。
【００３８】
次に、動的な選択の実施形態及び態様のいくつかの実現例を代表的な例として説明する。各実現例は、一般に、それに対応した異なるメッセージタイプを結果として与えるか又は利用する。例えば、符号化選択実施形態／態様の第１の実現例は、誤りが、３２個のパケットのブロック全体より小さい範囲に留まるとしたなら、第１のメッセージタイプを採用して３２個のパケットから成るブロックにおいて生じ得る全ての誤りを記述できる。一般に図７に示される第１のメッセージタイプの形式の一例は、誤りを含む各ブロックのために３２ビットワード６０（例えば、ワード６０の各ビットはブロックのパケットに対応する）、誤りを含むブロックを識別するためのブロック識別子６２及び、メッセージが実際にこの第１のタイプのメッセージであることを示すために添付されるメッセージ指標６４（フラグ、ビット又は値）を含む。３２ビットワード６０＋ブロック指標＋メッセージ指標は、誤り保護されて（例えば、誤り保護コード６６又は巡回冗長検査文字により）送信されるのが好ましい。
【００３９】
図８は、符号器２０（８）が符号器技術選択器７０及び（オプションとして）符号化技術選択指標７２を含む一実施形態及び態様を示す。符号器技術選択器７０は、本明細書により説明されるか又は含まれる符号化／圧縮技術又は別の符号化／圧縮技術（例えば、ランレングス符号化等）等の符号化／圧縮技術、あるいはデータのブロックのコンテンツを考慮して通信する別の方法を選択する論理により構成される。
【００４０】
符号器技術選択器７０は、事前定義済みの順番で複数の可能な符号化又は圧縮技術を採用するように構成されてもよく、それにより符号器２０（８）は、例えば図９に示すような論理又は代表的な動作を実現する。図９に示す特定の例において、動作９−１において、符号器技術選択器７０は、Ｎビットワードを符号化するためにランレングス符号化等のデフォルトの符号化技術又は方式を実質的に最初に自動的に選択及び採用する。動作９−２において、動作９−１の符号化がＮビットワードの十分な圧縮を行なったか又は与えたかのチェックを実行する。動作９−１の符号化（例えば、ランレングス符号化）が十分な圧縮を提供した場合、「他の」符号化技術（例えば、ランレングス符号化）が採用されたことの表示が結果として得られる割当てコードに添付される。一方、動作９−１の符号化がＮビットワードの十分な圧縮を行なえなかった場合（デフォルトの符号化（ランレングス符号化等）を使用することにより、所望の長さより短いビットの符号化ブロックが生成されない場合）、本明細書において説明されるような符号化（例えば、図３の動作による）が次に採用される。従って、符号器は、所定の順番及び達成された成功に基づいて適切な符号化技術を動的に選択でき、（必要に応じて）符号化技術選択指標７２は、複数の可能な符号化技術のうちワードに対して実際に使用された符号化技術に関して受信機又は復号器に通知する指示又は他の情報を含むことができる（ステップ９−３）。
【００４１】
図１０は、符号化技術の呼び出しの順番が図９とは逆である別の変形例を示す。図１０において、動作１０−１により表されるように、符号器技術選択器７０は、まず図３の符号化技術等の（第１の）符号化技術を試す。動作１０−２において、第１の符号化技術が十分な圧縮を行えないと判定される場合、別の符号化技術が採用される（動作１０−３）。動作１０−２において、第１の符号化技術が十分な圧縮を行うと判定される場合、第１の符号化技術により生成された符号化は割当てコードとして使用される（動作１０−４）。動作１０−５において、実際に採用された符号化技術を区別するために受信機又は復号器により使用される指標が追記される。
【００４２】
上述の例の変形例として、符号器技術選択器７０は、別の符号化／圧縮技術ではなくひとつの種類の符号化／圧縮技術を使用するのに特に準備されるか又は適切な条件又は状況を判定又は評価する論理又は機能性を含んでもよい。例えば、符号器技術選択器７０は、符号化選択実施形態／態様の第２の実現例において採用され、３２個のパケットから成るブロック全てが誤りを含むといった状況において第２のメッセージタイプを採用できる。３２ビットのブロックは６４ビット等の更に大きいブロックにまとめられ、ランレングス符号化される（動作９−１）。ランレングス符号化が十分な圧縮を行なう（動作９−２により判定されるように）場合、圧縮ワードは、この第２のメッセージタイプに対する指標に追記され（動作９−３）、（オプションとして）誤り保護されて送信される。
【００４３】
一方、ランレングス符号化が十分な圧縮を行なわない場合、本明細書により説明され且つ含まれる技術（図３のような動作を含む）が適用されてもよい。その結果、Ｎ＝６４及びＫｍａｘ＝１６の場合に５０ビット以下の符号が得られるが、誤りが６４ビットワードの特定の部分に制限される場合には、より多くの誤りがあっても５０ビット未満にできる。結果が５０ビットで記述される場合より長い場合、実際には２50−２より長い場合、符号は誤りパターンが符号化されないことを示す２50−１（５０個の「１」）に設定される。これは、全ての６４個のパケットが再送される必要があることを示すために送信機により使用される。メッセージタイプ３の指標と共に５０ビットコードは、誤り保護されて送信される。
【００４４】
図１１と共に上述の例は、仮の割当てコードが展開され（動作１１−１）、割当てコードが最大許容値より大きいと判定される（動作１１−２）場合、動作１１−３において、割当てコードは符号化の失敗を示すために最大許容値に設定されることを更に示す。割当てコードは、最大値より大きくない場合に使用される（動作１１−４）。
【００４５】
符号器技術選択器７０は、ブロックを解析し、ブロックのコンテンツを考慮して提供される通信の種類を判定する論理を有してもよい。例えば、符号器が受信ブロックを表す確認応答ワードを符号化する動作を実行する一実現例において、符号器技術選択器７０は図１２に示されるような動作を実行する論理を含む。動作１２−１によると、符号器技術選択器７０はブロックを解析し、前記Ｎビットブロック中の第１の極性のビット等の誤りビットの全ての位置が、前記Ｎビットの複数の特定のサブセットのうちの１つにおいて特定されるかを判定する（動作１２−２）。
【００４６】
例えば図１３は、誤りがブロック８０の１つの一般的な領域又はサブセットで発生するブロック８０を示す。符号器技術選択器７０は、ブロック８０をサブセット８２1，８２2，．．．８２Nに分割し、全ての誤り（例えば、全ての第１の極性ビット）が１つの特定のサブセット、すなわちサブセット８２2において発生することを観察する。「サブセット」（例えば、サブセットの長さ又は場所又はそれら両方）の定義又は表現は、事前に定義／判定されるか又は例えば符号器技術選択器７０により実行中に判定される。
【００４７】
動作１２−２において、全ての誤り位置がブロック８０の特定のサブセットにおいて特定されるわけではないと判定される場合、動作１２−３により示されるように、符号器技術選択器７０は図３の符号化／圧縮技術等のデフォルトの符号化／圧縮技術を選択する。一方、動作１２−４により示されるように、Ｎビットブロックにおける誤りビット（例えば、第１の極性ビット）の全ての位置が前記Ｎビットの特定のサブセットにおいて特定される場合、符号器は指標に追記されたビットのサブセットを割当てコードとして使用する。この指標は、使用されたサブセットを示し且つサブセットが実際に使用されたことを示す役割を果たす。例えば図１４は、符号器タイプフラグ又は指標９２1、サブセット識別子９２2及びペイロード９２4を含むメッセージ９０又は符号化ワードの形式の一例を示す。符号化タイプフラグ又は指標９２1は、動作１２−４のような符号化技術が実行された（例えば、デフォルトの符号化技術の代わりに）ことを明示する。サブセット識別子９２2は、図示する例におけるサブセット８２2等のブロックの誤りが発生したサブセットを識別する。ペイロード９２4は、誤りが発生したサブセットの内容を含む。
【００４８】
一般に、本明細書により説明され且つ含まれる実施形態の例示及び説明の限定的でない例は、確認応答メッセージ又はワードである。メッセージ／ワードのビットはブロックのパケットに対応し、ビットはイベント（例えば、誤り）がパケットにおいて或いはパケットに対して発生するかを示す。この目的のために、図１５は第１の通信ユニット１０２及び第２の通信ユニット１０４を含む通信システム１００の一実施形態を示す。第１の通信ユニット１０２は、例えば第１の通信ユニット１０２から第２の通信ユニット１０４に送信される情報を受信及び格納するように構成されるデータバッファ１０６を含む。データバッファ１０６のデータの受信、格納及び読み出しは、バッファマネージャ１０８により管理及び制御される。データバッファ１０６又は個別ブロック生成器１１０は、データバッファ１０６に格納されるデータをブロック形式にフォーマットする。ブロック形式のパラメータ及び必要条件は、実現例により異なる。ブロックは、最終的に、出力チャネル１１４を介する適用／送信のために送信機１１２（例えば、第１の通信ユニット１０２に対するトランシーバの送信機部分）に供給される。
【００４９】
次に説明するように、第１の通信ユニット１０２は、受信機１１６（例えば、第１の通信ユニット１０２に対するトランシーバの受信機部分）及び確認応答復号器１１８等の復号器を更に含む。
【００５０】
図１５の第２の通信ユニット１０４は、受信機１２０（例えば、第２の通信ユニット１０４に対するトランシーバの受信機部分）を含む。受信機１２０は、ブロックデフォーマッタ１２２に接続され、ブロックデフォーマッタ１２２は、第１の通信ユニット１０２からチャネル１１４を介して受信したデータをブロックに分割するか又はブロックで表現する。ブロックデフォーマッタ１２２によりデフォーマットされるブロックは、データバッファ１２４に格納される。データバッファ１０６と同様に、バッファ１２４に格納されるブロックの受信、格納及び読み出しは、バッファマネージャ１２６により管理又は制御される。更に、第２の通信ユニット１０４は、出力チャネル１１４を介して受信され且つバッファ１２４に格納されるブロックにおいて誤りの位置を特定するように構成されるブロックチェッカ１２８を含む。誤りの位置の特定は、周知の多くの技術のうち任意の技術に従ってブロックチェッカ１２８により実行される。更にオプションとして、ブロックチェッカ１２８は、従来の誤り訂正技術を使用して誤り訂正を試行できる。
【００５１】
ブロックのチェックに関連して、ブロックチェッカ１２８（又はそれに相当するユニット）は、第１の通信ユニット１０２から出力チャネル１１４を介して受信されるブロックの正確度を反映する確認応答メッセージ又は確認応答ワードを準備する。例えば、ブロックの各パケットは、確認応答ワードのビットにより表されてもよい。そのビットは、パケットが誤りを含んでいた場合には第１の極性値（例えば、バイナリ「１」）に設定され、パケットが誤りを含んでいなかった場合には第２の極性値（例えば、バイナリ「０」）に設定される。
【００５２】
第２の通信ユニット１０４は、確認応答メッセージ符号器１３０及び送信機１３２（例えば、第２の通信ユニット１０４に対するトランシーバの送信機部分）を更に含む。確認応答メッセージ符号器１３０は、ブロックチェッカ１２８等により展開される確認応答メッセージ又は確認応答ワードを符号化又は圧縮する。確認応答メッセージ符号器１３０により実行されるような確認応答メッセージ又は確認応答ワードの符号化又は圧縮は、本明細書により説明されるか又は含まれる任意の符号化／圧縮技術に従ってもよい。この目的のために、図１５は、限定的でない例として、確認応答メッセージ符号器１３０が基数選択ユニット２２（１５）、変位値判定ユニット２４（１５）及び加算器２６（１５）を含むものとして示す。それらの動作は、例えば図３等の先の実施形態の説明を参照することにより理解される。確認応答メッセージ符号器１３０の構造及び動作は、上述の１つ以上の実施形態の特徴及び技術を組み合わせてもよいことが理解されるだろう。
【００５３】
ここで説明する目的のために、確認応答メッセージ符号器１３０は、確認応答メッセージ送信機としての役割を果たす。特に、送信機１３２は、符号化／圧縮確認応答メッセージ又は確認応答ワードをチャネル１３４を介して第１の通信ユニット１０２に送信する。
【００５４】
第２の通信ユニット１０４から第１の通信ユニット１０２にチャネル１３４を介して送出された符号化／圧縮確認応答メッセージ又は確認応答ワードは、第１の通信ユニット１０２の受信機１１６により受信される。チャネル１３４を介して送出された確認応答メッセージ又は確認応答ワードが符号化／圧縮されていることを考慮して、確認応答メッセージ又は確認応答ワードは確認応答復号器１１８に適用される。確認応答復号器１１８により実行されるような確認応答メッセージ又は確認応答ワードの復号化又は伸張は、本明細書により説明されるか又は含まれる任意の技術に従ってもよい。例として、図１５は、図５により理解されるように、確認応答復号器１１８が基数値復号化ユニット５２（１５）及び変位値復号化ユニット５４（１５）を含むものとして示す。例えば、確認応答復号器１１８により実行されるような復号化動作は、図６により一般に表される動作であってもよい。
【００５５】
ブロックのパケットが誤りを含んでいたことが確認応答復号器１１８により判定される場合、確認応答復号器１１８は信号又はメッセージをバッファマネージャ１０８に送出する（矢印１４０により示される）。バッファマネージャ１０８への信号１４０は誤りのあるパケットを示し、バッファマネージャ１０８が第１の通信ユニット１０２から第２の通信ユニット１０４への出力チャネル１１４での送信のために別のブロックを準備する際に使用する誤りのあるパケットをデータバッファ１０６から再び取り出すことを可能にする。このようなパケットの再送により、再送されたパケットの内容を受信し且つ望ましくは正常に取り出すという別の機会を第２の通信ユニット１０４に提供する。
【００５６】
従って、この技術は、単独で使用される場合、あるいは他の方法又は技術が失敗した場合、Ｎ個のバイナリビットのワードをＮビットより少ないビット数に圧縮する手段を提供する。その手段は、Ｎビットワード内のビットの多くの異なる統計分布が、全体的に符号化され得るように他の方法と組み合わされる。それら統計分布は、所定の応用例において最も顕著であると予想される適当な分布である。種々の符号化方法により符号化できないビット分布は、符号化不可能としてフラグを立てられ、「符号化不可能」を示す適切なコードが送信される。
【００５７】
本明細書により説明されるか又は含まれる符号器又は復号器又はその両方の１つ以上の実施形態は、プロセッサ又は制御器を使用して実現される。プロセッサ又は制御器という用語自体は、先に包括的に明確に説明された。
【００５８】
本明細書において説明される限定的でない代表的な１つ以上の実施形態の１つ以上の特徴が組み合わせ可能なことは理解されるべきである。例えば一変形例において、符号器は、図２の実施形態の分数チェッカユニット３０及び図４の実施形態のＴ（Ｎ，Ｋ）ルックアップテーブル４０の双方を含むことができる。別の例として、任意の実施形態は、図８の実施形態のような符号器技術選択器７０を含むことができる。
【００５９】
この技術は、パケット毎に１ビット未満でパケットの成功又は失敗を示さなければならないようにパケットデータ通信システムにおいて確認応答ワードを符号化するのに特に有用であり、ランレングス符号化が適切でない場合に使用できる。一般にこの技術は、一方のビット極性を他方のビット極性より多く含むことが周知である場合にＮビットバイナリパターンをＮビットより少ないビット数に符号化する方法を含む。第１の極性ビット（バイナリ「１」等）がより少ない頻度で発生すると仮定すると、基数インデックスＩ0は、実際の数がＫ個の第１の極性ビットに基づいて計算され、そのインデックスはNＣ1＋NＣ2＋NＣ3．．．＋NＣK-1である。インデックスＩは、Ｎビット中の厳密にＫ個の１から成る特定のパターンを表すために計算され、基数インデックスに加算されて符号化表現Ｍ＝Ｉ0＋Ｉを取得する。
【００６０】
Ｍを復号化して元のＮビットワードを取得するために、ＭはNＣ1，NＣ2，NＣ3．．．，NＣK-1と連続して比較され、比較値がＭより小さい場合は比較値をＭから減算する。Ｍの残差値はＩと等しく、誤り数Ｋは、直前の減算される順列数の添え字に１を加算することにより与えられる。Ｋを与えると、Ｉの値は復号化され、元のＮビットを再生成できる。
【００６１】
上述の説明は多くの特性を含むが、それらは本発明の範囲を限定するものではなく、本発明の現在の好適な実施形態のいくつかを単に例示するものとして解釈されるべきである。本発明の範囲は、添付の請求の範囲及びその合法な等価物により判定されるべきである。従って、本発明の範囲は、当業者に明らかとなる他の実施形態を完全に含み、添付の請求の範囲以外のものにより限定されないことが理解されるだろう。添付の請求の範囲において、単数形の要素を示す場合、明示的に示されない限り「１つのみ」を意味する意図はなく、「１つ以上」を意味する。当業者に周知の上述の好適な実施形態の要素に対する全ての構造的等価物、化学的等価物及び機能的等価物は、参考として本明細書に明確に取り込まれ、本発明の請求の範囲に含まれることが意図される。更に、デバイス又は方法は、本発明により解決しようとする全ての問題に対処する必要はなく、また本発明の請求の範囲に含まれる必要もない。また、本開示における要素、構成要素又は方法ステップは、その要素、構成要素又は方法ステップが請求の範囲に明示的に説明されているが一般に公開される意図はない。
【００６２】
【表１】
2010517467.tif 000003
【００６３】
【表２】
2010517467.tif 000004
【００６４】
【表３】
2010517467.tif 000005
【図１】
2010517467.tif 000006
【図２】
2010517467.tif 000007
【図３】
2010517467.tif 000008
【図４】
2010517467.tif 000009
【図５】
2010517467.tif 000010
【図６】
2010517467.tif 000011
【図７】
2010517467.tif 000012
【図８】
2010517467.tif 000013
【図９】
2010517467.tif 000014
【図１０】
2010517467.tif 000015
【図１１】
2010517467.tif 000016
【図１２】
2010517467.tif 000017
【図１３】
2010517467.tif 000018
【図１４】
2010517467.tif 000019
【図１５】
2010517467.tif 000020
【手続補正書】
【提出日】平成21年4月22日(2009.4.22)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
第１の値のビットの数ＫがＮの一部に限定されている場合に、Ｎ個のバイナリビットのブロック内に分布する前記第１の値のビットのパターンに長さがＮビット未満のコードを割り当てるように構成される符号器（２０）であって、
式Ｉ0＝NＣ1＋NＣ2＋NＣ3．．．＋NＣK-1を評価するように構成され、前記Ｎ個のバイナリビットのブロック中の前記第１の値のビットの数Ｋに依存して基数値Ｉ0を選択する手段（２２）と、
前記Ｎ個のバイナリビットのブロック中の前記第１の値の前記ビットの数の特定の分布を表す変位値を決定する手段（２４）であって、
ビットＮがバイナリの第１の値ビットである場合、Ｉ（Ｎ−１，Ｋ−１）がＮ−１ビット中の残りのＫ−１個の第１の値ビットから成るパターンの符号化であるときに、前記変位値Ｉ（Ｎ，Ｋ）をN-1ＣK＋Ｉ（Ｎ−１，Ｋ−１）として再帰的に決定し、
ビットＮが第１の値ビットでない場合、Ｋが前記残りのＮ−１ビット中のＫ個の第１の値ビットから成るパターンの符号化であるときに、前記変位値Ｉ（Ｎ，Ｋ）をＩ（Ｎ−１，Ｋ）として再帰的に決定する手段と、
前記基数値及び前記変位値を加算して合計を取得するように構成される加算器（２６）とを備えることを特徴とする符号器（２０）。
【請求項２】
複数の可能な符号化技術の呼び出しの順番を選択するように構成される符号器技術選択器（７０）を更に具備し、
前記符号化技術のうち少なくとも１つは前記基数選択手段及び前記変位値決定手段を使用して実現されることを特徴とする請求項１記載の符号器（２０（８））。
【請求項３】
前記複数の実行可能な符号化技術のうちワードに対して実際に利用された符号化技術に関する表示を前記割り当てられたコードに含めるように構成される符号化技術選択指標（７２）を更に具備することを特徴とする請求項２記載の符号器（２０（８））。
【請求項４】
Ｎ個のバイナリビットのブロック内に分布する第１の値のビットのパターンに長さがＮビット未満のコードを割り当てる方法であって、
（１）前記Ｎ個のバイナリビットのブロック中の前記第１の値のビットの数を判定するステップと、
（２）前記第１の値のビットの前記判定された数に基づいて基数値を選択するステップと、
（３）前記Ｎ個のバイナリビットのブロック中の前記第１の値のビットの前記判定された数の特定の分布を表す変位値を決定するステップと、
（４）前記基数値及び前記変位値を加算して合計を取得し、前記合計を使用して割当てコードを形成するステップと
を有することを特徴とする方法。
【請求項５】
前記第１の値はバイナリ「１」であることを特徴とする請求項４の方法。
【請求項６】
前記Ｎ個のバイナリビットのブロックの各ビットに対応する前記ブロックのパケットにおいて誤りが検出されたかを示すために前記ビットを使用するステップを更に含むことを特徴とする請求項４記載の方法。
【請求項７】
前記割当てコードとして前記合計を使用することを更に含むことを特徴とする請求項４記載の方法。
【請求項８】
前記基数値を選択する前記ステップ（２）は、Ｋが前記Ｎ個のバイナリビットのブロック中の前記第１の値のビットの前記判定された数である場合に、式Ｉ0＝NＣ1＋NＣ2＋NＣ3．．．＋NＣK-1を評価するステップを含むことを特徴とする請求項４記載の方法。
【請求項９】
前記変位値を判定する前記ステップ（３）は、
前記変位値をゼロに初期化するステップと、
前記ビットブロックに残る前記第１の値のビット数がゼロである場合にゼロの変位値を返すステップと、
前記ビットブロック中の前記第１の値のビット数が非ゼロであり且つ前記ビットのブロックの第１のビットが前記第１の値のビットである場合、
Ｋが前記Ｎビットブロック中の前記第１の値のビットの前記判定された数であるときに前記変位値にNＣKを加算するステップと、
残りのＮ−１ビット中の残りのＫ−１個の第１の値ビットから成るパターンを表すように決定される前記変位値を加算するステップとを実行するステップと、
前記ビットのブロックの前記第１のビットが前記第１の値でない場合に、前記残りのＮ−１ビット中で位置を特定されるＫ個の第１の値ビットから成るパターンと同様に決定される前記変位値を前記変位値に加算するステップとを含むことを特徴とする請求項４記載の方法。
【請求項１０】
前記変位値を判定する前記ステップ（３）は、
ビットＮがバイナリの第１の値ビットである場合、Ｉ（Ｎ−１，Ｋ−１）がＮ−１ビット中の残りのＫ−１個の第１の値ビットから成るパターンの符号化であるときに、前記変位値Ｉ（Ｎ，Ｋ）をN-1ＣK＋Ｉ（Ｎ−１，Ｋ−１）として再帰的に決定するステップと、
ビットＮが第１の値ビットでない場合、Ｋが前記残りのＮ−１ビット中のＫ個の第１の値ビットから成るパターンの符号化であるときに、前記変位値Ｉ（Ｎ，Ｋ）をＩ（Ｎ−１，Ｋ）として再帰的に決定するステップとを含むことを特徴とする請求項４記載の方法。
【請求項１１】
前記割当てコードが最大許容値より大きいかを判定し、前記割当てコードが前記最大許容値より大きい場合に前記割当てコードを前記最大許容値に設定するステップを更に含むことを特徴とする請求項４記載の方法。
【請求項１２】
ステップ（１）の前に、前記Ｎビットのブロックを符号化するためにランレングス符号化を使用するステップと、
前記ランレングス符号化を使用することにより所望の長さより短いビットの符号化ブロックが生成されない場合、ステップ（２）乃至（４）を実行して前記割当てコードを取得するステップとを更に含むことを特徴とする請求項４記載の方法。
【請求項１３】
ランレングス符号化が前記Ｎビットのブロックを符号化するために使用されたかを示すために前記符号化ブロックに指標を追記するステップを更に含むことを特徴とする請求項１２記載の方法。
【請求項１４】
ステップ（１）乃至（４）から取得される前記割当てコードが最大許容値以上である場合、ランレングス符号化を使用して前記Ｎビットブロックを符号化し、符号化ブロックを生成し、
オプションとして、前記符号化ブロックが最大許容ビット長より大きい場合、前記割当てコードを前記最大許容値に設定し、
オプションとして、前記符号化ブロックが最大許容ビット長より大きくない場合、前記ランレングス符号化ブロックを前記割当てコードとして使用することを特徴とする請求項４記載の方法。
【請求項１５】
ランレングス符号化が前記割当てコードを生成するために使用されたかを示す前記指標を追記することを更に含むことを特徴とする請求項１４記載の方法。
【請求項１６】
ステップ（１）の前に、前記Ｎビットブロック中の第１の極性のビットの全ての位置が前記Ｎビットの複数の特定のサブセットのうちの１つにおいて特定されるかを判定し、特定されない場合にステップ（１）乃至（４）を実行するステップを更に含むことを特徴とする請求項４記載の方法。
【請求項１７】
前記Ｎビットブロック中の前記第１の極性の前記ビットの全ての位置が前記Ｎビットの特定のサブセットにおいて特定される場合、使用されたサブセットを示し且つサブセットが使用されたことを示す指標に追記される前記ビットのサブセットを前記割当てコードとして使用することを特徴とする請求項１６記載の方法。
【請求項１８】
Ｎ個のバイナリビットのブロック内に分布する第１の値のＫビットのパターンを取得するために長さがＮビット未満の割当てコードを復号化するように構成される復号器（５０）であって、
（１）基数値＋変位値として記述される受信コードＭ＝Ｉ0＋Ｉを比較値NＣ1，NＣ2．．．NＣKmaxと連続して比較する動作と、
（２）再構成される前記Ｎビットワード中のＫ個の前記第１の値ビットを判定するために動作（１）の比較結果を使用する動作と、
（３）厳密にＫ個の前記第１の値ビットから成る特定のパターンに割り当てられた変位値（Ｉ）を決定するために、動作（１）の前記比較結果からＭの残差値を使用する動作とを実行するように構成されることを特徴とする復号器（５０）。
【請求項１９】
前記復号器（５０）は、変位値（Ｉ）がN-1ＣK以下である場合、
ビット（Ｎ）が前記第１の値を有するときに前記比較値を減算し且つ残りをN-2ＣK-1と比較してビット（Ｎ−１）を判定する再帰動作と、
ビット（Ｎ）が前記第１の値ビットでないときにN-1ＣK-1と比較する再帰動作とを実行するように更に構成されることを特徴とする請求項１８記載の復号器。
【請求項２０】
Ｎ個のバイナリビットのブロック内に分布する第１の値のＫビットのパターンを取得するために長さがＮビット未満の割当てコードを復号化する方法であって、
（１）基数値＋変位値として記述される受信コードＭ＝Ｉ0＋Ｉを比較値NＣ1，NＣ2．．．NＣKmaxと連続して比較するステップと、
（２）再構成される前記Ｎビットワード中のＫ個の前記第１の値ビットを判定するために動作（１）の比較結果を使用する動作と、
（３）厳密にＫ個の前記第１の値ビットから成る特定のパターンに割り当てられた変位値（Ｉ）を決定するために動作（１）の前記比較結果からＭの残差値を使用するステップと
を有することを特徴とする方法。
【請求項２１】
変位値（Ｉ）がN-1ＣK以下である場合、
ビット（Ｎ）が前記第１の値を有するときに前記比較値を減算し且つ残りをN-2ＣK-1と比較してビット（Ｎ−１）を判定する再帰ステップと、
ビット（Ｎ）が前記第１の値ビットでない時にN-1ＣK-1と比較する再帰ステップとを更に含むことを特徴とする請求項２０記載の方法。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００４
【補正方法】変更
【補正の内容】
【０００４】
しかし、誤り数がある閾値より少ない場合、可能な誤りパターンの数はＮビットより少ないビットを使用して記述可能であり、より大きなサイズのコンテナが同一メッセージ長を使用して確認可能になる。他の従来技術によるアプローチは、「コンテキストの選択に基づく２レベル画像の可逆圧縮および階層的数え上げ符号化(Lossless compression of bi-level images based on context selection and hierarchical enumerative coding)」(Image processing, Proceedings 2001, vol.3, no., pp. 438-441, Jaehyuk Im, Jechang Jeong著、２００１年発行)に記載されている。この文書には、局所的に固定されたバイナリ列の圧縮に階層的数え上げ符号化を利用した数え上げ符号化器および数え上げ復号化器が示されている。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００１５
【補正方法】変更
【補正の内容】
【００１５】
以下の説明において、限定しない説明の目的で、本発明を完全に理解するために特定のアーキテクチャ、インタフェース、技術等の特定の詳細を示す。しかし、本発明がそれらの特定の詳細とは異なる他の実施形態において実現されてもよいことは、当業者には明らかであろう。本発明の原理、面及び実施形態、並びにそれらの特定の例を説明する本明細書における全ての表現は、構造的及び機能的な等価物を含むことを意図する。
【国際調査報告】
2010517467.tif 000021
2010517467.tif 000022
2010517467.tif 000023
2010517467.tif 000024