(57)【特許請求の範囲】
【請求項１】
データ通信方法であって、
（ａ）複数データ・パケットを含むデータ・メッセージを送信する段階と、
（ｂ）前記データ・メッセージを受信し、受信したデータ・メッセージに含まれる第１のデータ・パケットのエラーを検査する段階と、
（ｃ）該第１のデータ・パケット中で受入れ不能なエラーを検出した場合、該データ・パケットの再送信を要求する段階と、
（ｄ）再送信された1つ以上のデータ・パケットを受信する段階と、
（ｅ）前記第1のデータ・パケットと前記１つ以上のデータ・パケットとを含む一連のデータ・パケットを使用して前記第１のデータ・パケットを再構成する段階であって、
前記一連のデータ・パケット中の交番データ・パケットに対しては、前記一連のデータ・パケット中の以前に受信したデータ・パケットと現在受信したデータ・パケットとからの情報を使用して多数決投票操作を実行し、前記交番データ・パケットに対する再構成データ・パケットである多数決投票されたデータ・パケットを発生する段階と、
前記一連のデータ・パケット中の前記交番データ・パケット以外のデータ・パケットに対しては、前記多数決投票されたデータ・パケットと現在受信したデータ・パケットとを比較することにより、異なるビット値を有する１つ以上のビット位置を識別してそのビット値の1つ以上を変更し、該１つ以上の変更されたビット値を有するデータ・パケットを前記交番データ・パケット以外のデータ・パケットに対する前記再構成データ・パケットとする段階と
を含む前記再構成する段階と、
（ｆ）前記再構成データ・パケットのエラーを検査する段階と、
（ｇ）前記再構成データ・パケットが前記段階（ｆ）において受け入れ可能と判明した場合は、確認信号を送信する段階と、
を含むデータ通信方法。
【請求項２】
請求の範囲第１項記載の方法において、段階（ｅ）は前記多数決投票されたデータ・パケットと現在受信したデータ・パケットとに対して排他的ＯＲ演算を実行することを含む方法。
【請求項３】
請求の範囲第１項記載の方法において、各データ・パケットはデータ・ビットとエラー検出ビットとを含み、前記検査段階（ｂ）と（ｆ）とはデータ・パケットに対して巡回冗長コード計算を実行することを含む方法。
【請求項４】
請求の範囲第１項記載の方法において、前記多数決投票操作は、
非整合ビットの数を閾値と比較する段階を更に含む方法。
【請求項５】
請求の範囲第１項記載の方法において、前記多数決投票操作は、前記データ・パケットの各々からの対応するビット位置におけるビット値を各ビット累計器が合計するように前記データ・パケットにおける各対応するビット位置に対してビット累計器を保持する段階を含む方法。
【請求項６】
請求の範囲第１項記載の方法において、各データ・パケットはデータ・ビットとエラー検出ビットを含むが、エラー訂正ビットを含まない方法。
【請求項７】
データ処理方法であって、
第１の送信されたデータ単位と、１つ以上の再送信データ単位とを含む一連のデータ単位を受信する段階と、
前記一連のデータ単位を使用してデータ単位を再構成する段階であって、
前記一連のデータ単位中の交番データ単位に対しては、前記一連のデータ単位中の以前に受信したデータ単位と現在受信したデータ単位とからの情報を使用して多数決投票操作を実行し、前記交番データ単位に対する再構成データ単位である多数決投票されたデータ単位を発生する、多数決投票を実行する段階と、
前記一連のデータ単位中の前記交番データ単位以外のデータ単位に対しては、前記多数決投票されたデータ単位と現在受信したデータ単位とを比較する比較段階と、異なるビット値を有する１つ以上のビット位置を識別してそのビット値の１つ以上を変更し、該１つ以上の変更ビット値を有するデータ単位を前記交番データ単位以外のデータ単位の再構成データ単位とする、変更段階と、
を含む前記データ単位を再構成する段階と、
前記再構成データ単位の各々が受入れ可能であるかどうか決定する段階と、
を含むデータ処理方法。
【請求項８】
請求の範囲第７項記載の方法において、前記交番データ単位は前記一連のデータ単位中の奇数データ単位であり、前記交番データ単位以外のデータ単位は前記一連のデータ単位中の偶数データ単位である方法。
【請求項９】
請求の範囲第７項記載の方法において、前記比較段階は、排他的OR演算を実行する段階と、異なるビット値の数を閾値と比較する段階と、前記異なるビット値の数が前記閾値より小さいときに前記変更段階を実行する段階と、を含む方法。
【請求項１０】
請求の範囲第７項記載の方法において、前記多数決投票されたデータ単位は以下の段階に従って決定される：
データ単位中の各対応するビット位置に対して、前記一連のデータ単位中の各データ単位から対応するビット位置のビット値の和を累計する段階と、
前記一連のデータ単位の数を基に閾値を決定する段階と、
各累計和を前記閾値と比較する段階と、
該累計和が前記閾値より小さいか又は等しい場合、前記多数決投票されたデータ単位の対応するビット位置のビット値を０に設定する段階と、
該累計和が前記閾値より大きい場合、前記多数決投票されたデータ単位の対応するビット位置のビット値を１に設定する段階と、
を含む方法。
【請求項１１】
請求の範囲第７項記載の方法において、前記決定段階は、前記データ単位の各々のエラーを解析する段階と、各データ単位はエラー検出ビットを含み、受入れ不能なエラーを検出した場合データ単位の再送信を要求する段階と、を含む方法。
【請求項１２】
請求の範囲第９項記載の方法において、エラー検出ビットは巡回冗長コード検査ビットで、各データ単位はエラー訂正ビットを含まない方法。
【請求項１３】
請求の範囲第１０項記載の方法において、前記閾値を決定する段階は、
前記一連のデータ単位におけるデータ単位の数を２で割り算する段階と、
生成した商を切り捨てる段階と、
を含む方法。
【請求項１４】
請求の範囲第１０項記載の方法において、前記請求の範囲第１０項に記載された前記段階は前記再構成データ単位の各ビット位置に対して実行される方法。
【請求項１５】
請求の範囲第１０項記載の方法において、前記請求の範囲第１０項に記載された前記段階は前記再構成データ単位の一部のビット位置に対してのみ実行される方法。
【請求項１６】
請求の範囲第７項記載の方法において、前記再構成データ単位が受入れ可能かどうか決定する段階において、受入れ不能な場合は前記異なるビット値の１つを変更する方法。
【請求項１７】
送信器がデータ通信リンクを介してデータ単位を複数回送信することにより一連のデータ単位を発生するデータ通信システムにおいて使用される受信器であって、
前記データ通信リンクに接続され、前記一連のデータ単位を受信するためのトランシーバと、
前記トランシーバに接続されたデータプロセッサであって、該データプロセッサは、
（１）以下のようにデータ単位を再構成し、
（ａ）前記一連のデータ単位において受信した交番データ単位に対しては、前記一連のデータ単位における以前に受信したデータ単位と現在受信したデータ単位とからの情報を使用して、多数決投票操作を実行することにより、前記交番データ単位の再構成データ単位である多数決投票されたデータ単位を発生し、
（ｂ）前記一連のデータ単位において受信した前記交番データ単位以外のデータ単位に対しては、前記多数決投票されたデータ単位と現在受信したデータ単位とを比較し、異なるビット値を有するビット位置の数を識別してそのビット値の１つ以上を変更し、該１つ以上の変更されたビット値を有するデータ単位を前記交番データ単位以外のデータ単位に対する前記再構成データ単位とし、
（２）前記再構成データ単位が受入れ可能であるかどうか決定する、
ように構成されたデータ受信器。
【請求項１８】
請求の範囲第１７項記載の受信器において、前記受信器は携帯無線装置であり、データ通信リンクは無線チャネルである受信器。
【請求項１９】
請求の範囲第１７項記載の受信器において、前記データプロセッサは前記一連のデータ単位における前記データ単位の各々から対応するビット位置に対するビット値の合計を記憶するために、前記再構成データ単位における１つ以上のビット位置に対してビット累計器を保持するように構成されている受信器。
【請求項２０】
請求の範囲第１９項記載の受信器において、前記データプロセッサは前記一連のデータ単位の数を基に閾値を決定し、各累計和を前記閾値と比較し、前記累計和が前記閾値より小さいか又は等しい場合、前記多数決投票されたデータ単位の対応するビット位置のビット値を０に設定し、前記累計和が前記閾値より大きい場合、前記多数決投票されたデータ単位の対応するビット位置のビット値を１に設定するように構成されている受信器。
【請求項２１】
請求の範囲第１７項記載の受信器において、前記再構成データ単位が受入れ不能な場合、前記データプロセッサは前記異なるビット値の1つ以上を変更して新たな再構成データ単位を発生するように構成されている受信器。
【発明の詳細な説明】
発明の分野
本発明はデータ処理と通信の分野に一般に関係し、特に通信チャネルを介して送信された又はメモリから検索されたデータの回復に関係する。
発明の背景と要旨
ディジタル・データ・システムでは、メモリに記憶されたデータと共に通信チャネルを介して送信されたデータがエラーにより破壊されるのは普通のことである。エラーを検出し、及び／又は検出したエラーを訂正するために標準的に使用される多数の技術がある。エラー検出技術の１例は公知の巡回冗長コード(CRC)検査である。ブロック・コードとコンボリューション・コードを使用する他の技術はエラー検出とエラー訂正の両方を可能とする。エラー検出と訂正のため、追加のコード・ビットがデータ・ビットに追加される。データを通信チャネルを介して受信した時、又はメモリから検索した時、受信／検索データは追加のビットをある方法で使用してデコードされ、データの一部がエラーであるかどうか検出する。これらのデコード処理を考えるひとつの方法は、印刷文書を読んでいる時にスペルミスを訂正する人間の能力を類推することである。単語は互いに十分に異なっているため、読者はどの語が何を意味しているかを直感的に知っている。
これらのエラー検出及び／又は訂正コード化技術はすべてある程度まで冗長情報を追加する。データ単位に冗長性を組み込めば組み込むほどエラーが正確に検出され、ある場合には訂正される。残念なことに、コード化／冗長ビットの数が増加するにつれて、全体のデータ「情報量」が減少する。言い換えると、単位時間当り送信される実際のデータ内容が減少する。加えて、コード化／冗長ビットの数が増加するにつれて、コード／デコード・アルゴリズムの複雑性が増加し、これは限定されたデータ処理リソースを消費し、データ処理時間を遅くする。
データが破壊されそうもないある種の相対的に「きれいな」環境下では、より簡単なエラー検出及び／又は訂正処理と関連して少ないコード化／冗長ビットが使用可能である。しかしながら、相当な雑音、干渉等がある不利な環境下では、通常このような簡略化は選択肢ではない。例えば、ラジオ／無線通信環境を考える。無線周波数通信チャネルは、常に存在する雑音、ほとんど連続的に変化する通信チャネル特性、多重路フェーディング、記号間干渉(ISI)を生じる時間分散、隣接チャネル通信からの干渉、そして多くの他の要因を含む破壊要因の砲火を受けている。
これらの各種の破壊要因から保護するために使用される１つの通信プロトコル（すなわち処理方式）は、自動繰返し要求(ARQ)処理である。純粋なARQ方式はエラー検出のみを使用する−−エラー訂正は使用されない。特に、ある型式のエラー検出ビット／コード化を有するデータ・パケットが送信側から受信側へ通信チャネルを介して送信される。各受信データ・パケットはデータ・パケットに含まれるエラー検出ビットを使用して受信側によって処理され、データ・パケットが正しく受信されたかどうかを決定する。パケットが安全かつ正確に受信された場合、受信側は確認信号(ACK)を送信側に返信する。エラーを検出した場合、受信側は否定確認(NAK)を送信側に返信し、データ・パケットを破棄し、送信側からのこれと同じデータ・パケットの送信を待機する。加えて、送信側が情報を送信し、受信側が情報を受信し処理し、次いでACK又はNAK信号を送信側に送信するための十分な時間を与える所定のタイミング窓を設定する。所定の窓内に送信側がACK信号を受信しない場合、又は窓内にNAK信号を受信した場合、送信側はデータ・パケットを再送信する。
無線通信のような雑音の多い又はその他のデータ破壊環境下では、データが正しく受信される前に多数の再送信が発生しうる。大事なことは、何回データ・パケットが送信／再送信されようと、受信側は以後再送信されたデータ・パケットから正確な情報を如何にデコードするかに関して「賢く」ならないことである。言い換えると、特定のデータ・パケット再送信時にパケットを正しく受信する確率は、そのパケットの前回の再送信の確率より良くはならない。
このARQプロトコルを改良する可能な選択肢は、データ・パケットに前進型エラー訂正（forward error correction:FEC）ビットを追加してある程度のビット訂正を可能とすることである。このような「ハイブリッド」技術の例は、CRCエラー検出ビットをボーズ・シャドフリ・ホッケンヘム（Bose-Chaudhuri-Hocquenghem）（BCH）パリティ検査ビットに置き換えることである。エラーのあるビットが受信側で訂正可能ならば、これ以上の再送信の必要なしに確認が送信側に送信可能である。限定された数のエラー・パターンが訂正可能なこのようなハイブリッド技術を使用した場合でも、このようなハイブリッド技術は（純粋なARQプロトコルと同様に）前回受信したパケットに含まれる情報を利用していない。純粋ARQプロトコルのエラーのあるデータ・パケット又はハイブリッド技術を使用して訂正不能なエラーを有するデータ・パケットは単に廃棄されて連続した一連の再送信を必要とする。
必要なものは、前回に送信したパケットに含まれる情報を利用する、すなわち廃棄するのではなくエラーのあるデータ・パケットを使用して、今回受信したデータ・パケットの再送信を前回受信したデータ・パケットからの情報を使用して訂正可能とするような、例えばARQプロトコルに適用可能なデータ回復技術である。前回送信したパケットのビットの大部分は正しいものと見なされ、多くの場合１つ又は数ビットのみが破壊されている。本発明の主な目的は、パケットの前の送信から累計された正しい情報を利用して、正しいデータ・パケットを発生することである。しかしながら、この技術は大量の処理時間を消費してはならず、最小化されなければならない。この処理に必要とされるメモリ量は出来るだけ少なくして、メモリ・リソースが限定されている各種の環境、例えば携帯／移動無線でこの技術を使用可能としなければならない。それゆえ、各データ・パケットに前進型エラー訂正ビットを追加することなく、ARQプロトコルに前進型エラー訂正を与えることが望ましい。
本発明の目的は、前に受信／送信したが受入れられなかったデータ単位に含まれる情報を使用して正しいデータ単位を回復するデータ回復装置を提供することである。
本発明の目的は、データ単位に追加の前進型エラー訂正ビットを追加することなくデータが訂正可能となるような自動繰返し要求(ARQ)処理環境下でのデータ回復技術を提供することである。
本発明の別な目的は、データ・パケットへ前進型エラー訂正ビットの追加や、複雑な前進型エラーデータ訂正デコード処理、又は大量のメモリ・リソースを必要とすることなく不利な環境下でデータを回復するのに有効なエラー回復技術を提供することである。
本発明は上述の各種の問題を解決し、これら及び他の目的を満足する。データ単位を受信し、エラーを検査し、エラーを検出した場合に再送信してデータ単位の組を発生する自動繰返し要求データ送信システムでは、本発明は受入れ可能なデータ単位を再構成するため、一連の交番データ単位に第１の再構成操作を実行し、それ以外の一連のデータ単位に第２の再構成操作を実行する。再構成操作の１つは現在受信したデータ単位と一連の前に受信したデータ単位に基づいた多数決投票データ単位の決定を含む。他の再構成操作は、現在受信したデータ単位に対する多数決投票データの直接比較を実行し、相違ビット値を有するビット位置を識別する。正しいデータ単位を発生することを期待してこれらのビット位置の１つ以上のビット値を変更する。純粋の自動繰返し要求(ARQ)環境（すなわち、前進型エラー訂正なしのもの）に対する投票及びパケット比較再構成技術のこの別種の応用は非常に重要である、なぜなら通信装置は高ビットエラー率環境でその性能を非常に改良可能で、より短い期間内で送信パケットを正しく受信する確率を増加できる。
交番多数決投票及びパケット比較データ単位再構成技術を使用した望ましい例示実施例では、「引分け」投票を解決することが困難であるという意味で投票に偶数のパケットが存在する時には多数決投票は有効でなくなる。例えば、投票される４パケットがあって、あるビット位置に対してパケットの内の２つが「１」を有し、他の２パケットがその位置に「０」を有している場合にそのビット位置にどの値を割当てるべきであるのか？「１」又は「０」を任意に選択するのではなく、本発明の望ましい例示実施例は奇数の受信データ・パケットに対して多数決投票を使用し、偶数パケットに対しては多数決投票データ他と現在受信したデータ・パケットとを直接比較してこの引分けの板ばさみを回避する。多数決投票と直接比較技術の両方で、前に受信したデータ・パケットからの情報が使用され、これは正しいパケットを得る見込みを増加する。
多数決投票と直接比較操作は比較的実行が簡単であり、相対的に少量のデータ処理リソースと時間が消費される。さらに、本発明は、最小のメモリで前に受信したがエラーのあるパケットに含まれる情報を利用する新規の技術を提供する。前回受信したエラー・パケットからの情報は保存するが、パケット自体は保存しない。代わりに、本発明は、各受信データ単位からそのビット位置でビットの和を再構成データ・パケットの各対応ビット位置に累計する。次いで一連の再送信データ単位の数を基に閾値が決定され、各累計和が閾値と比較される。累計和が閾値に等しいかそれ以下の場合、再構成データ・パケットの対応するビット位置のビット値は０に設定される。それ以外は、再構成データ・パケットの対応するビット位置のビット値は１に設定される。
【図面の簡単な説明】
本発明のこれらの及び他の目的と共に本発明の特定の例示実施例が、同じ番号は同じ要素を参照している以下の図面と関連して以下に記載されている。
図１は本発明の１例示実施例によるデータ通信装置の機能ブロック線図である。
図２は本発明の１例示実施例による方法を図示した流れ図である。
図３Ａ−３Ｃはデータ・メッセージ内に含まれる例示データ・メッセージとデータ・パケットを図示する。
図４は多数決投票パケットを図示する。
図５は本発明の１例示実施例によるビット累計機能を図示する。
図６は受信データ・パケットの多数決投票パケットとの直接比較を図示する。
図７は本発明が特別の応用例を有する複数サイト、幹線無線通信装置の概略図である。
図８は本発明を使用する無線データ・ネットワークの機能ブロック線図である。
図９は本発明に従って使用される携帯／可動無線トランシーバの機能ブロック線図である。
図１０は本発明の１例示実施例によるデータ回復処理を図示する流れ図である。
図１１は本発明の１例示実施例により実行される直接比較操作を図示する流れ図である。
図１２は本発明によるデータ回復方式の１例示実施例により実施される多数決投票処理の流れ図である。
望ましい例示実施例の詳細な説明
以下の説明では、限定のためではなく説明の都合上、本発明の完全な理解を提供するために、特定の回路、インターフェース、技術等のような特定の詳細を記載する。しかしながら、当業者には、本発明は特定の詳細から逸脱するほかの実施例でも実施できることは明らかである。本発明の説明を不必要な詳細で不明瞭にしないよう、他の例では、公知の方法、装置、回路の詳細な説明は省いている。
本発明は、例示の都合上データ通信装置の文脈でのみ説明している。以下の実施例は無線通信環境に対する本発明の応用を特に記述している。しかしながら、本発明は無線通信又はこれに関する任意の型式のデータ通信に限定されるものではない。本発明の他の応用例は、例えば記憶装置へ又はそこから転送される各種のデータを含む破壊される可能性のあるデータを受信及び／又はアクセスしなければならない任意の種類のデータプロセッサである。
従って、図１は、ネットワーク・バス１６を介して他のデータプロセッサ又は他の装置、例えば周辺装置であるデータ受信器１４へのデータのパケットを送信するデータプロセッサ２０のような送信側１２を含む有線型式データ通信ネットワークを説明する。両方のデータプロセッサ２４、２６はその各々のメモリ２２、２８を有し、両データプロセッサはネットワーク・バス１６を介してパケット情報を通信する各トランシーバ２４、３０を含む。データプロセッサ２０とトランシーバ２４は、データのデータ単位、すなわちデータ・パケットへの分割と共にエラー検出ビットの包含／コード化を含む、ネットワーク・バス１６を介した伝送に使用される適当なプロトコルに従ってデータをフォーマットする。データプロセッサ２６は、各データ単位を正しく受信したかどうか検出するため、メモリ２８に記憶したアルゴリズムに従ってトランシーバ３０で受信したデータ単位を処理する。本発明の特に有利な応用例の１つでは、自動繰返し要求(ARQ)プロトコルを送信側と受信側との間に使用して、受信側１４でデータ単位を正しく受信した時に、受信側１４がネットワーク・バス１６を介して送信側１２へ確認(ACK)を送信するようにする。データ単位を不正に受信して、本発明によって正しく再構成できなかった場合、受信側１４はネットワーク１６を介して送信側１２へ否定確認(NAK)を送信し、送信側１２はこれに応答して同じデータ単位を再送信する。
そのデータ単位の一連の再送信版からデータ単位を正確に回復するため受信側データプロセッサ２６で使用されるデータ回復技術は、ここで図２に記載されている。以下では一連のデータ単位は通信チャネル（有線又は無線）上の再送信の意味で記述されているが、一連のデータ単位は同一のデータ単位のデータ記憶装置からの複数アクセスによっても発生可能である。再送信又はアクセスの回数はもちろん任意の装置の設計パラメータである。多数回の再送信又はアクセスはよりエラー発生し易い装置に設定され、一方低い制限は相対的にエラーの少ない装置／環境で設定される。
データ回復処理４０では、データ単位を受信しエラーを検査する（ブロック４１）。現在のデータ単位をエラーなしで（又は代わりにある程度にビット・エラーを許容可能なディジタル音声のような応用例に対しては受入れ可能なビット・エラー率内で）受信した場合、受信側１４から送信側１２へ確認（ACK）が返送され（ブロック４７）、次の受信データ単位のエラーが検査される（ブロック４１）。そうでない場合は、これがデータ単位の最初の伝送であるかどうかの判断が行われる（ブロック４３）。そうである場合、受信側１４はデータ単位の再送信を要求し（ブロック４４）、再送信データ単位の受信とエラーの検査に復帰する（ブロック４１）。
これがデータ単位の再送信である場合、このデータ単位が「交番」データ単位であるかどうかの判断が実行される（ブロック４８）。１例として、交番データ単位が同じデータ単位の「奇数」転送、すなわち転送１、再転送３、再転送５、等に対応する。反対に、交番データ単位が「偶数」転送、すなわち再転送２、再転送４、再転送６、等に対応しても良い。データ単位が交番データ単位である場合、第１のデータ単位再構成操作が実行される（ブロック５０）。そうでない場合、第２データ単位再構成操作が実行される（ブロック５２で）。
第１又は第２データ単位再構成操作のどちらかを実行した後、ブロック５４で再構成データ単位が有効かどうか、例えば再構成データ単位にビット・エラーがないか又は所定のビット・エラー閾値以下であるかどうかの判断が行われる。そうである場合、制御はブロック４７へ復帰し、ここで受信側１４は送信側１２へ確認を返信する。そうでない場合、制御はブロック４４へ復帰し、データ単位の再送信を要求する。
本発明はデータがある単位で送信される任意のデータ・フォーマットに適用できる。例えば、図３Ａはディジタル・データ・メッセージの１例のフォーマットを図示する。メッセージは、データ・メッセージの開始、送信側及び／又は受信側アドレス情報、メッセージ長、等を含む任意数の機能に割当てられたビットのヘッダー部分から開始する。このようなヘッダの１例は標準インターネット・プロトコル（IP）ヘッダである。ヘッダに続いて、パケット第１、パケット第２、パケット第３、....のような図３Ａに示すデータのパケットが続く。
図３Ｂに示す各パケットはデータ及びエラー検出ビットの両方を含む。言い換えると、各パケットの全てのビットが送信すべき本質的な情報に対応しているわけではない。本発明ではデータ・パケットという用語がしばしば用いられているが、本発明はデータの任意の単位に適用でき、データ・パケットに必ずしも限定されないことが認められる。
データ・パケットのある特定の例示構成が図３Ｃに図示されている。データ・パケットの第１部分の所定数のデータ・ビットに、第２部分の巡回冗長検査(CRC)ビットが続く。CRCはエラー検出のみを提供する−−これはエラーの訂正には使用されない。公知のCRCの例はCRC-CCITTとCRC-16を含む。本発明はまたBCHパリティ検査ビットのような前進型エラー検出及び訂正ビットにも適用できる。しかしながら、本発明の利点の１つは、前進型エラー訂正ビットとコード化／デコード・アルゴリズムがデータ回復に使用する必要がない点である。
第１及び第２データ単位再構成操作の１つは図４の例示と関連して以下に説明する多数決投票操作である。望ましい実施例では、多数決投票技術が交番の奇数データ・パケット伝送に適用される。それ故、図４に示す簡単な例では、多数決投票操作はデータ・パケットの３回の伝送に実行される。各データ・パケットはこの非限定例では32データ・ビットと16CRCビットを含む。ある特定のビット位置のビットの２つ又は３つが同じ値を有する場合、多数決投票データ・パケットではそのビット位置にその値が割当てられる。３データ・パケットの最初の８ビット・バイトの２つの例は、第４ビット位置で１、１、０の多数決投票が１を生じることを示している。対照的に、第7ビット位置では、ビット値０、１、０の多数決投票が０を生じ、その第７ビット位置に割当てられる。図示してはいないが、データ・パケットのビットのどの部分も使用して多数決投票操作が実行可能である。しかしながら、全ての３２データ・ビットと全ての１６CRCビットに対して多数決投票を実行することにより、より多くの情報が得られる。
多数決投票パケットは第１、第２、第３データ・パケットからの累計ビット情報を単一のデータ・パケットに組み合わせる。図４に示すように、これらのビットの多くは、正確に受信される（ある特定のビット位置では全て０又は全て１）。異なるビット値間で多数決投票決定を必要とするビット位置でさえも、多数決投票の結果が正しいビット値に対応する確率が高い。多数決投票パケットを発生した後、データ・パケットにCRC演算を実行して、これが正しいか又は受入れ可能な許容値内であるかを決定する。
本発明の特に有利ではあるが非限定的な実施は、多数決投票決定過程に使用する新規のビット累計機能の使用である。各受信データ・パケットをメモリ中に記憶して多数決投票操作用にこれらの記憶データ・パケットの各々を引き出すのではなく、データ・パケットの各ビット位置に対してビット累計を発生し保持することによりメモリが節約され、複雑度が減少する。受信データ・パケットの各ビットは対応するビット累計器に加算される。従って、各データ・パケットに48ビット有る場合、データ・パケットは48個のビット累計器を有し、各累計器の寸法は１バイトである。「１」のビット値はそのビット位置のビット累計器に加算される「１」を発生し、「０」のビット値は対応するビット累計器値に変化を生じさせない。このようにして、データ・パケットの各ビット位置での「１」の全体数の実行時和が保持される。各ビット累計器の全体和値が受信データ・パケットの数と比較される。ビット累計器の全体和値が閾値を越えている場合、多数決投票ビットは「１」に設定され、それ以外は多数決投票ビットは「０」に設定される。閾値は受信パケット数の半分に等しく設定しても良い。
このようなビット累計器は、非常に多数のパケット再送信を必要とする環境下では特に有用である。例えば、全部で255パケット再送信が許可されている場合、各ビット累計器は単一の８ビット（すなわち１バイト）フィールドとして定義可能である。この構成を使用すると、16データ・バイトと2CRCバイトを有するデータ・パケットは最大255データ・パケット再送信に対応して144個のビット累計器（すなわち144バイト）を必要とする。これは、各パケット再送信をRAM中に個別に記憶する場合と比較してRAMの大量の節約を提供する。パケットを255回送信した場合、各パケットを個別に記憶すると、255 X 18バイト＝4,590バイトのRAMを必要とする。本発明で使用したビット累計器方法では、144バイトのみが必要でメモリの相当の節約が可能である。その他の構成は全体で15データ・パケット再送信のみを許可するもので、４ビット（ニブル）ビット累計器フィールドを使用する。この構成は単一バイトのRAMに2ビット累計器を提供可能とする。
奇数データ・パケット受信の場合、受信データ・パケットの各ビット位置のビット値は対応するビット累計器に加算されて新たな多数決投票データ・パケットを作成する。この新たな多数決投票データ・パケットが次いでCRCアルゴリズムを使用して処理される。これがCRC検証をパスすると、多数決投票データ・パケットは受入れられ、確認が送信器に発生されて正しいパケットの受信を指示する。多数決投票パケットがまだエラーの場合、否定確認が送信側に送信され、パケットは再送信される。
多数決投票は偶数のパケット受信にも適用可能ではあるが、「引分け」の存在の可能性のため、例えば４パケットを受信してあるビット位置で２つの「１」と２つの「０」が有る場合、この技術はそれほど有効ではない。代わりに、本発明の望ましい実施例では、偶数データ・パケット（受入れ不能なエラーで受信）は、前の奇数データ・パケット受信で計算された多数決投票データ・パケットと直接比較される。偶数データ・パケットのデータ・パケット・ビット値は上述したようにデータ・パケット・ビット累計器に加算される。しかしながら、多数決投票自体は実行されないため、多数決投票パケット（これに対して直接比較を行う）は前の奇数データ・パケット受信時に計算されたものと同じままである。
直接比較データ単位再構成技術の例は図６に図示されている。直接比較は例えば排他OR(XOR)演算を使用して実施され、ここでは２つの比較データ・パケット間で異なるビットは２進数「１」を発生し、同じビットは２進数「０」を発生する。多数決投票と同様に、直接比較はデータ・パケットのビットの部分に、又は望ましくは、パケットの全てのデータ・ビットに実行される。例えば後者を実施するためには、図示受信データ・パケットの全てのデータ及びCRCビットが多数決投票データ・パケットの全てのデータとCRCビットと比較される。
ビット相違数が閾値を越えた場合、以下の理由により、パケットを破棄して否定確認を送信側に送信するのが賢明である。しかしながら、パケットがわずかに数ビット位置でのみ異なっている場合、これらの相違ビットを、実行しているCRCアルゴリズムにより全ての可能な組合せを体系的に設定して、各可能な組合せに対してデータの正確度を検査する。言換えると、相違ビット位置の１つが現在「１」に設定されている場合、これを「０」に変更してCRCアルゴリズムを検査する。２ビット位置が相違している場合、可能な４つの異なるビット組合せが試される。３ビット位置に対しては、３個の可能なビット組合せが試される、等々。従って、可能なビット組合せの数は２bitdifsに等しく、ここで「bitdifs」は相違ビット数に等しい。これらのビット組合せのどれかが正しいCRC検査を生じる場合、確認が受信側で発生され、訂正パケットは受入れられる。正しいパケットが回復できない場合、否定確認が送信される。
この２つのデータ単位再構成技術間、例えばパケット受信の偶数奇数間で交番する過程は、パケットが正しく確認されるか又は最大数の再試行に達するまで続行される。８ビット累計器を使用する上述の例示構成では、再試行／再送信の最大許容数は255である。
直接比較技術の閾値の設定では、許容可能なビット相違数に実際的な制限がある。最初の問題は、全ての可能な組合せに対してCRCを計算する処理時間量である。この処理時間は、所定の時間量、例えば１秒の内のわずかな時間内に受信側が送信側へある種の肯定確認／否定確認を提供することを保証するため制限されている。受信側が全ての可能なビット組合せを試行するため大量の時間を浪費する場合、このACK/NAK送信タイミング窓を容易に超える可能性がある。第２の問題は、送信側により実際には送信されていないパケットを正しいものとして受入れる、すなわち「誤送受入れ(falsing)」の問題である。２パケット間のビット相違数が大きい場合、パケットを不正な値に訂正して、それにも係らずCRC検証を通過する確率が増大する。それ故、直接比較技術でより多くのビット相違を受入れるトレードオフは、増大するデータ処理時間、増加する電力消費、「誤送受入れ」の大きな確率である。
本発明の重要な特徴は、エラーである又は受入れ不能である場合に、そのパケットを廃棄することによりエラーの有るデータ・パケットからの重要な情報が失われない点である。対比的に、本発明は、多数決投票と直接比較エラー訂正技術の両方を使用してこの重要な情報を保存し使用する。
例えば、２％のビット・エラー率(BER)環境で、データ・パケットが４バイトのデータと、２バイトのCRCコード・ビットの全体で48ビットから構成されている場合を考える。この環境下では、データ・パケットの各伝送が１つ以上のエラーを含む確率（62％）は高い。本発明を使用しない場合、エラーなしにデータ・パケットの伝送を受信する確率は以下の式により決定可能である：
0003775800.tif 000002
従って、１つ以上のビット・エラーを有するパケットを受信する確率は以下に従って決定される：
0003775800.tif 000003
この２％のビット・エラー率環境では、正しく受信できる単一ビットの確率は98％である（すなわちＰcorrect bit＝98％）。しかしながら、パケット中のデータ・ビットの全数が４から16バイト（全体で144ビット）に増大した場合、エラーを含むパケットの確率は非常に高い（94.5％）。結果として、単にエラーの有るデータ・パケットを廃棄し、次の伝送がエラーなしで到達すると期待する現在の技術は非現実的で有効ではない。本発明によるデータ回復／再構成技術の恩恵がないと、２回のデータ伝送で受入れ可能なデータ・パケットを成功裏に受信する確率は以下のとおりである：
0003775800.tif 000004
48ビット・パケットの２％ビット・エラー環境でも、２回の試行でパケットを成功裏に受信する確率は61.8%で、これはこの相対的に低いビット・エラー率環境でさえも特に期待できるものではない。
しかしながら、本発明の望ましい例示実施例による偶数伝送時の直接比較と奇数伝送時の多数決投票を追加することにより、複数回送信されたデータ・パケットを正しく受信する確率は非常に改良される。２つの訂正技術の各々の以下の確率計算がこの改良を定量化する助けとなる。
パケット間で２ビット相違のみを許容するものと仮定した直接比較では、２回だけ送信したパケットを成功裏にデコードする確率は以下の式により決定される：
0003775800.tif 000005
直接比較技術を含めた時にデータ・パケットを正しく受信する確率は約62%から67%に増大する。この話では受信パケットと多数決投票パケットは２ビットだけ相違していることのみが許されているため、この増加は控えめである。言換えると、２パケットの各々は１ビット・エラーのみを有することが出来、２パケットの単一ビット・エラーは同じ位置であってはならない。しかしながら、許容ビット相違数を拡大して３又は４ビット相違を含ませるようにした場合、成功裏受信の確率は著しく増大する。
以上のデータ回復過程に多数決投票を追加すると、３回送信したパケットを訂正する確率を改良する。１パケット伝送を正しく受信する確率に対して上記の式を使用すると、多数決投票を使用しない３伝送によりパケットを受信する確率は以下のとおりである：
0003775800.tif 000006
48ビット・データ・パケットで2%ビット・エラー率環境では、Ｐsuccess＝78.4%である。多数決投票を含めた場合、３回の伝送でパケットを正しく受信する確率は以下のとおりである：
0003775800.tif 000007
多数決投票を用いてパケットを正しく受信する確率は98.7%である。
直接比較と多数決投票技術の両方を追加した場合、２%ビット・エラー率環境で３回だけ送信した受信48ビット・パケットを正しくデコードする確率はほとんど100%である。特に、データ・パケットを正しく回復する確率のこの増加が、データ・パケットに追加する追加の前進型エラー訂正ビットなしで達成される。代わりに本発明は前に受信したデータ・パケットの貴重な情報を使用して受信側をより「賢明に」教育し、現在受信したデータ・パケットを訂正する。さらに、直接比較と多数決投票技術は最小の時間、計算、メモリ・リソースのみを必要とする。３回以上の送信を必要とする特に雑音の多い環境下でさえも、本発明は新たな各受信により送信データ・パケットを正しく回復するよう段々接近してくる。
データ処理リソースが限定され、メモリ空間を保存する必要があり、通信環境が標準的には不利である（高いビット・エラー率）、本発明の可能な１使用例は無線通信の分野である。通信装置の1例は図7に示す幹線無線リピータ装置１００である。幹線無線リピータ装置１００は「複数サイト」装置であり、サイト・コントローラS1が移動無線と担当区域A1から特定の被呼出人又は被呼出人のグループと通信するためチャネルを要求する呼を受信する。呼出人はその携帯／移動RFトランシーバの送話(PTT)ボタンを押してチャネルを要求する。これは、割当てRF制御チャネル上を送信される内行ディジタル制御メッセージを介してサイト・コントローラS1に、音声作業チャネルが必要であることを通知する。サイト・コントローラS1は呼出人に作業チャネルを割当て、呼出人の無線装置に制御チャネルから割当て作業チャネルに切替えるように指令する。割当て作業チャネルはサイトによりカバーされる区域内の通信をサポートする。
加えて、サイト・コントローラは、複数サイト・スイッチ１０４に割当てた作業チャネルを含む制御メッセージを送信する。このスイッチは、また、他のサイト・コントローラへチャネル要求を送信し、呼出人にサービスするRFサイト・リピータと被呼出人にサービスするRFサイト・リピータとの間に音声信号通路が作成されるよう音声信号を経由させる。加えて、１つ以上の分配コンソール１０６と公衆線加入者（中央電話相互接続交換機１０８を介して）が通信に関係できるよう、音声信号通路も同様に設定できる。チャネル要求メッセージを受信すると、これらの２次サイト・コントローラは各々RF作業チャネルを呼に割当てる（例えば、呼出人のチャネル要求メッセージにより指定された被呼出人が関係RF通信サイトによりサービスされるカバー区域内にたまたま物理的に位置している場合）。その間複数スイッチ２００は呼出人の音声がサイトS1の能動RF受信器から呼に関連する他のサイトの各々の能動送信器へ経由されることを保証する。更なる詳細は例えば米国特許第5,200,954号に提供されている。
データ・ネットワークを介した携帯／移動無線装置を用いてデータ通信も実行可能である。例えば、図８はイーサネット・ネットワーク１１０と無線データ・ネットワーク１１２を含む２つの異なる型式のネットワークを図示している。イーサネット・ネットワーク１１０と無線ネットワーク１１２は、データ・ゲートウェイ１１４とデータ・インターフェース・モジュール１２６を使用して「相互ネットワーク」される。データ・ゲートウェイ１１４は両ネットワーク間でメッセージを翻訳するインターフェースを提供する。データ・ゲートウェイ１１４は、TCP/IPのような標準のプロトコルを例えば使用してイーサネット・ネットワーク同軸ケーブル１１４上のホスト・コンピュータ１１６、１１８、１２０に接続する。RFデータ・ネットワーク１１２では、データ・インターフェース・モジュールは、無線周波数通信チャネルを介して１台以上の無線装置１２８、１３０と通信する複数個のサイト１２２、１２４に接続する。無線データ端末１３２、１３４（例えばノートPC）は各々無線１２８、１３０に接続されてデータ通信を実施する。
無線データ端末１３２からホストA  １１６へ通信を行うためには、無線１２８がRF制御チャネル上でサイト１２２に、メッセージが有ることを通知し、RF作業チャネルを要求する。サイト１２２は利用可能なRF作業チャネルを割当て、無線１２８に通知する。次いでサイト１２２はデータ・インターフェース・モジュール１２６へ呼割当てを送信し、このモジュールはこれをデータ・ゲートウェイ１１４へ経由させてデータ・ゲートウェイとRF作業チャネルとの間のデータ路を設定する。無線１２８はメッセージをパケットに分割し、RF作業チャネルを通してサイト１２２へパケットを送信する。サイト１２２はデータ・インターフェース・モジュール１２６を介してデータ・パケットをデータ・ゲートウェイ１１４へ受信したように転送する。データ・ゲートウェイ１１４が大量のメッセージ・パケットを受信した後、正しくこれが受信されたかどうかを検査し、RF作業チャネルを通して１つ以上の確認信号を無線へ返信する。データ・パケットが正確に受信されなかった場合、否定確認信号が無線に送信されて、無線はデータ・ゲートウェイが正しく受信しなかったパケットを含む他のバーストを再送信する。データ・ゲートウェイ１１４が全メッセージを受信するまで、又は無線がその再試行回数が尽きるまでこれが続行される。データ・ゲートウェイ１１４がデータ・メッセージを成功裏に受信した場合、データ・ゲートウェイ１１４はバス１１４を介してホスト・コンピュータ１１６へメッセージを送信する。
本発明に使用される適当な移動／携帯無線装置の全体アーキテクチャは図９に図示するようなマイクロプロセッサを基にしたものである。マイクロプロセッサ１５０には、適当なメモリ１５２と、無線表示部、キーパッド、送話(PTT)スイッチとインターフェースするための入出力(I/O)回路１５４と共に、音声出力をスピーカへ与え、マイクロフォンからのアナログ音声入力を受入れる音声回路１６８が設けられている。モデム１５６は、音声コード化へのディジタル・インターフェース、車両位置、複数サイト・スイッチ、無線データ端末１３２を含む他の型式のディジタル通信副システムとして機能する。ある場合には、ソフトウェアではなくハードウェアで実行されるCRC検査のようなエラー検出アルゴリズムを有することが望ましい。このような場合、モデム１５６は変調／復調機能に加えて、エラー検出及び／又は訂正機能を実行するハードウェア回路を含む。I/O回路１５４は又、従来の信号結合器１６４を介して、当業者には容易に認められるような共通のアンテナ１６６を通して全２重通信を可能とするRF受信器１６２と送信器１６０のマイクロプロセッサ１５０による適切なプログラム制御も可能とする。無線データ端末１３２はモデム１５６に接続したRS-232ケーブル１５８を介して無線１２８と通信する。
例えば、上述した無線通信ネットワークに実装されるような本発明を以下に詳細に説明する。特に、無線チャネルを通して送信されたデータ・パケットを受信する無線受信器により実行される例示データ回復処理を、図１０に図示した流れ図と関連して以下に説明する。最初に、パケット・カウント変数PACETCNTが０に設定される（ブロック１８０）。データ・パケットを受信し（ブロック１８２）、パケット・カウント変数を増分する（ブロック１８４）。データ・パケットが図４−６に図示したものと同様のフォーマットを有しているものと仮定して、CRC検査操作が受信パケットに対して実行されてエラーを検出する（ブロック１８６）。CRC検査で、データ・パケットが正しく受信されたことを確認した場合（ブロック１８８）、受信器は無線通信チャネルを通して確認信号（ブロック２０２）を送信し、制御はブロック１８２に復帰して次のデータ・パケットを受信する。そうでない場合は、受信データ・パケット・ビット値がこのデータ・パケットに対して保持されている対応するビット累計器に加算される（ブロック１９０）。ブロック１９２で、現在のパケット・カウントが奇数であるかどうか、すなわち、これがこのデータ・パケットの偶数又は奇数再送信であるか、の判断が行われる。これが奇数伝送である場合、図１１により詳細に図示する多数決投票データ単位回復アルゴリズムが実行される（ブロック１９４）。これが偶数伝送である場合、直接比較データ回復処理が図１２に図示するように実行される（ブロック１９６）。図１１及び図１２により詳細に図示したどちらかのデータ回復操作を実行した後、制御は判断ブロック１９８に復帰して、CRC検査を使用してパケットが成功裏にデコードされたかどうかを決定する。そうでない場合、ブロック２００で再試行が要求され、制御はブロック１８２に復帰して再送信パケットを受信する。それ以外、再構成データ・パケットは受入れ可能であり、確認信号が送信され（ブロック２０２）、次の実際のデータ・パケットがブロック２０４で処理される。
直接比較アルゴリズム（ブロック２１０）を図１１に図示した流れ図と関連して以下に説明する。図６に図示したものと同じ方法で、現在受信したデータ・パケットの偶数伝送の直前のデータ・パケットの奇数伝送に対して計算された多数決データ・パケットを、現在受信している偶数データ・パケットと排他ORする（ブロック２１２）。排他OR比較の結果として（すなわち、「１」の排他OR出力を有するビット位置）相違ビット数の和を変数BITDIFに割当てる（ブロック２１４）。変数BITDIFが所定の閾値より少ないか又は等しいかの判断を行なう（ブロック２１６）。上述したように、この閾値は、改良されたデータ回復性能と、このビット相違数から生じるビット組合せの指定数のCRCを計算するのに必要なデータ処理時間／リソースとの間のトレードオフである。相違ビット数が閾値を越えている場合、成功フラグは偽に設定される（ブロック２１８）。制御は図10に復帰し、データ・パケットが再送されるよう再試行要求が出される。そうでない場合、各種のビット組合せを使用して一連の可能な試行データ・パケットを発生する（ブロック２２０）。これらの可能な試行データ・パケットの内の1つを選択し（ブロック２２２）、CRC検査計算を実行する（ブロック２２４）。CRC検査が満足できる場合（ブロック２２６）、成功フラグが真に設定され（ブロック２３２）、制御は図10に復帰し、ここで確認信号が送信される。そうでない場合、ブロック２２８で、全ての可能な試行データ・パケットの組合せを解析したかどうかの判断が行われる。そうでない場合、制御はブロック２２２に復帰し、まだ解析していない可能な試行データ・パケットの内の他のものを選択する。それ以外は、全ての可能な試行データ・パケットが受入れ不能な結果を生じた。成功フラグは偽に設定され（ブロック２３０）、制御は図10に復帰して否定確認を送信し、これによりデータ・パケットを再送信させる。
図12に図示した流れ図と関連して多数決投票アルゴリズム（ブロック２５０）を以下に説明する。ブロック２５２で、データ・パケット中の全ビット数に対応する変数TOTALBITSを設定する。この説明で使用される非限定的な例に従うと、ビットの全数は48に設定される。ビット累計器は、データ・パケット中のビット位置の１つを「指す」変数BITNUMのように初期化される。ブロック２５４で、閾値変数Ｔが設定される。閾値を計算する１例の方法は、パケット・カウントを２で割算して残りを切り捨てる（「TRUNC」）。
ブロック２５６で、指されている現在のビット位置のビット累計器のビット和が閾値Tを超えたかどうかの判断を行なう（ブロック２５６）。そうである場合、多数決データ・パケットのこのビット数のビット値を１に設定する（ブロック２５８）。そうでない場合、多数決データ・パケットのこのビット位置のビット値を０に設定する（ブロック２６０）。次いでブロック２６２で、変数BITNUMが１つ増分されて次のビット位置／ビット累計器を指す。ブロック２６４で、新たなビット位置（BITNUM）がデータ・パケットのビット総数より小さいかどうかの判断が行われる。小さい場合、ブロック２５６−２６４の処理が繰返される。大きい場合、このデータ・パケットの多数決投票操作は完了し、ブロック２６６でCRC検査が実行される。CRC検査の結果が良好な場合（ブロック２６８）、成功フラグを真に等しく設定する（ブロック２７２）；そうでない場合、成功フラグは偽に設定される（ブロック２７０）。次いで制御は図10に復帰して確認を送信するか（ブロック２０２）又は再試行を要求する（ブロック２００）。
従って、本発明は前に受信したデータ・パケットからの情報を利用してデータを回復してデータ・パケットを再構成し、50%以下のビット・エラー率を想定した実際に送信されるデータ・パケットを再構成する確率をさらに増加させる。新たな受信の度に、累計した情報が受信器をより正確に近く導いて、実際に送信されたデータ・パケットを得る。こうしなければ捨てられるであろう情報の使用は、限定されたデータ処理及び／又はメモリ・リソースを有するトランシーバによる不利な通信環境では特に有用である、高度に効率的で有効なビット・エラー訂正を可能とする。
本発明は特定の実施例を参照して説明してきたが、本発明の範囲と共にその応用と特徴は他の実施例に拡大でき、以下の請求の範囲によってのみ制限される。
【図１】
0003775800.tif 000008
【図２】
0003775800.tif 000009
【図３Ａ】
0003775800.tif 000010
【図３Ｂ】
0003775800.tif 000011
【図３Ｃ】
0003775800.tif 000012
【図４】
0003775800.tif 000013
【図５】
0003775800.tif 000014
【図６】
0003775800.tif 000015
【図７】
0003775800.tif 000016
【図８】
0003775800.tif 000017
【図９】
0003775800.tif 000018
【図１０】
0003775800.tif 000019
【図１１】
0003775800.tif 000020
【図１２】
0003775800.tif 000021