クロックの時間同期方法
【課題】高速かつ効率的に実行可能なエラー許容性のクロックの時間同期を提供する
【解決手段】通信システム(1)においてクロックの時間同期を特に高速かつ効率的な方法で行うために、本発明による方法は次のステップを有する：タイムベース(10)に依存する状態値を取得するステップ；取得した各状態値が、(ｋ＋１)個の位置から成る第１リストＬの(ｋ＋１)番目に小さい要素以下であり、ここにｋは事前に定義可能なエラー許容度である場合に、この状態値を第１リストＬ中の位置に入れるステップ；この状態値が、(ｋ＋１)個の位置から成る第２リストＨの(ｋ＋１)番目に大きい要素以上である場合に、この状態値を第２リストＨ中の位置に入れるステップ；取得した状態値の数が(２ｋ＋２)以上である場合に、リストＬの(ｋ＋１)番目に小さい要素及びリストＨの(ｋ＋１)番目に大きい要素から平均値を求めるステップ；修正値をこの平均値の関数として決定するステップ；同期させるべきクロックの現在の状態値を修正するステップ。
【解決手段】通信システム(1)においてクロックの時間同期を特に高速かつ効率的な方法で行うために、本発明による方法は次のステップを有する：タイムベース(10)に依存する状態値を取得するステップ；取得した各状態値が、(ｋ＋１)個の位置から成る第１リストＬの(ｋ＋１)番目に小さい要素以下であり、ここにｋは事前に定義可能なエラー許容度である場合に、この状態値を第１リストＬ中の位置に入れるステップ；この状態値が、(ｋ＋１)個の位置から成る第２リストＨの(ｋ＋１)番目に大きい要素以上である場合に、この状態値を第２リストＨ中の位置に入れるステップ；取得した状態値の数が(２ｋ＋２)以上である場合に、リストＬの(ｋ＋１)番目に小さい要素及びリストＨの(ｋ＋１)番目に大きい要素から平均値を求めるステップ；修正値をこの平均値の関数として決定するステップ；同期させるべきクロックの現在の状態値を修正するステップ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信媒体経由で通信するノードに割り当てられたクロックの時間同期の方法に関するものである。
【０００２】
本発明はさらに、通信媒体によって他のノードと通信するノード、及び通信媒体経由で通信する複数のノードを有する通信システムに関するものである。
【０００３】
本発明は、コンピュータ、特にマイクロコンピュータ上で実行可能なコンピュータプログラムにも関するものである。
【背景技術】
【０００４】
通信媒体経由で通信するノードは例えば、バスシステムまたはネットワークによって互いにメッセージを交換する制御装置、センサ及びアクチュエータである。こうしたノード及び関連する通信媒体から成る通信システムは、例えば航空機または自動車を制御するために用いることができる。この場合の「ノード」とは、特にいわゆるインタフェースも含み、インタフェースは、通信媒体への物理的接続、及び送受信されたメッセージを処理する責任を共に負う。
【０００５】
現代の通信システムは通常、エラー（誤り）を許容すべく設計されており、このため少なくとも特定の基本機能は、通信システム内にエラーが発生してもなお、適正に実行される。このことは、例えば通信システムが安全に厳格な環境で、たとえば航空機を制御するため、あるいは自動車を制御するために使用される場合に特に重要である。従ってこうした基本機能は例えば、通信システム内にエラーが発生しても航空機がまだ制御可能であることを保証する。
【０００６】
例として、エラー許容性の通信システムは、ノード内またはメッセージの送信中に発生したエラーを取り扱う際には、このエラーが結果的なエラー、例えば、誤って送信、転送、または受信されたメッセージによって他のノードが誤ったメッセージを生成すること、あるいは他のノードがその機能を適正に実行し続けることが阻害されることが生じないことが保証されるように設計されている。こうしたメカニズムなしでは、例えば、ノード（いわゆる「バブリング・イディオット（bubbling idiot、不法大量発信者）」）が非常に大量のメッセージを通信媒体経由で送信して、他のノードからの送信データの破壊活動が生じ得るか、及び／または通信媒体が過負荷になり、このため他のノードがもはや利用不能、あるいは少なくとも十分に利用できなくなる、ということが生じ得る。
【０００７】
現在使用されている通信システムでは、特に安全に厳格な環境における通信媒体において、例えば結果的なエラーの発生を低減するために、いわゆる時間制御送信法がますます使用されている。この場合には一般に、ノードが特定時刻にメッセージを送信することのみ可能である。この方法は、通信媒体が常に、特に重要なメッセージ、例えば安全関係の用途向けのメッセージを送信可能であるのに十分な容量を有することも保証する。
【０００８】
多くの通信システムが、その適正な動作のために、いわゆるグローバルタイム（大域的時間）を必要とする。このことは例えば、複数の特定イベントの同時性、例えば種々のセンサの取得値の同時変化を規定するために重要である。グローバルタイムは特に、時間制御のメッセージ送信にとっても、例えばノードが送信可能である時点を確定するために必要である。さらに、多くの時間制御の通信媒体の場合に、このメッセージを受信した時刻にもとづいてメッセージの送信者を推察することができる。
【０００９】
グローバルタイムを決定する種々の方法が知られている。例として、通信システムには中心クロックが存在し、その現在値は通信媒体によって対応するノードに送信される。しかし、この方法は、例えばグローバルクロックの不具合が、中心クロックが絶えず同じ値を現在値として出力するということを生じさせて、このことは通常、通信システムの不具合となる、という欠点を有する。さらに、元々正しく送信されたグローバル時間の転送または受信時のエラーが、２つのノードに異なる現在時刻を捉えさせ、従って不具合のきっかけ、あるいは正しい通信の妨げとなり得る。
【００１０】
従って、通常、複数のクロックが使用される。例として、各ノードが自前のクロックを有することができる。しかし、これらのクロックの不正確さ、及び欠陥のあるクロックによって生じ得るエラーにより、これらのクロックによって決まる現在時刻は通常、時間と共に互いに一層異なってくる。従って、一様なグローバルタイムを決定するためにクロックの同期を行う。この場合には、特に、クロックを同期させるためのエラー許容性の方法を利用し、この方法では、特定数のクロックによって誤って設定、転送、または受信された現在時刻がクロックの同期に対して悪影響を与えることがあり得ない。特に、こうした方法は、誤った値を供給しているクロック、あるいは新たに始動させたクロックが他のクロックと同期することを可能にする。
【００１１】
通信システム上でメッセージを送信する時間ベースの方法では、個々のメッセージをフレームとして知られている時間ウィンドウ（窓）内で送信する。フレームは通信媒体経由で、グローバルタイムの関数として送信され、グローバルタイムを一意的に各フレームに割り当てることができる。このことは、各ノードがグローバルタイムにもとづいて各フレームを明確に識別することを可能にする。従って特に、各ノードは、どのフレームがメッセージの送信用に自ノードに割り当てられているかを認識することができる。グローバルタイムが自ノードのクロックの関数として決まるならば、種々のノードによって決まる２つの同期サイクル間のグローバルタイムが異なり得る。しかし、フレームをグローバルタイムに一意的に割り当てることを保証できるためには、２つの同期サイクル間に２つのクロック間に最大あり得る偏差に応じた時間間隔が、個々のフレーム間に存在しなければならない。しかし、フレーム間ギャップとして知られているこの時間間隔中にはメッセージを送信することができないので、フレーム間ギャップの長さは通信媒体の帯域幅（単位時間当りに伝送可能なデータ量）に悪影響する。このことは、帯域幅がクロックの精度に依存することを意味する。
【００１２】
クロックの平均精度は、連続する２つの同期間の時間間隔の大きさに依存し、言わば、新たな同期が行われるまでに複数クロックの現在時刻が互いに異なる「長さ」従って「幅」に依存する。クロックの平均精度は同期を行う速さにも依存する、というのは、送信時刻と、同期方法の期間中に決まる修正値による実際のクロックの修正との間でも、クロックが既に互いにずれていることがあるからである。
【００１３】
クロックを同期させるために、平均の算出にもとづく方法（いわゆる平均ベースの方法）が存在する。例えばバスシステムＴＴＡ及びFlexRayにおいて用いられる平均ベースの方法では、同期させるべき各ノードが、他の種々のクロックによって当該ノードに送信され、現在取得した時刻または状態値の平均を決定する。この方法において、あるノードに送信される特定数の誤ったクロック時刻からの独立を達成するために、いわゆるエラー許容度ｋを保証する。この場合には、例えば、他のクロックの状態値とは非常に異なる１つ以上の状態値（例えばｋ番目に大きい状態値及びｋ番目に小さい状態値）は、前記平均の決定中に考慮に入れない。
【００１４】
特に、平均ベースの方法は、エラー許容性のクロックの同期のために、特定した現在の状態値の特定の最小数ｎ、例えばｎ≧(２ｋ＋２)なるｎを必要とする。このことが達成されていなければ、同期を行うことができないか、あるいは同期を保証するために時間を要する方法が必要であるかのいずれかである。
【発明の開示】
【発明が解決しようとする課題】
【００１５】
本発明の目的は、特に高速かつ効率的な方法で実行され、できる限りエラー許容性のクロックの時間同期を可能にする能力を提供することにある。
【課題を解決するための手段】
【００１６】
この目的は、上述した方法が次のステップを有することによって達成される：
−少なくとも同期させるべきノードについて、当該ノードのタイムベースに依存する状態値を取得するステップと；
−取得した状態値のすべてについて、取得した状態値が(ｋ＋１)個の位置から成る第１リストＬの(ｋ＋１)番目に小さい要素未満であるか、あるいは(ｋ＋１)番目に小さい要素以下であり、ここにｋは事前に定義可能なエラー許容度である場合に、取得した状態値を第１リストＬ中の対応する位置に入れるステップと；
−取得した状態値のすべてについて、取得した状態値が(ｋ＋１)個の位置から成る第２リストＨの(ｋ＋１)番目に大きい要素より大きいか、あるいは(ｋ＋１)番目に大きい要素以上である場合に、取得した状態値Ｚを第２リストＨ中の対応する位置に入れるステップと；
−ｎ≧(２ｋ＋２)であり、ここにｎは取得した状態値の数である場合に、第１リストＬの(ｋ＋１)番目に小さい要素及び第２リストＨの(ｋ＋１)番目に大きい要素から平均値を求めるステップと；
−修正値をこの平均値の関数として決定するステップと；
−同期させるべきクロックの現在の状態値がこの修正値を計算に入れるように、このクロックを修正する。
【００１７】
（本発明の利点）
本発明による方法では、他のノードのクロックの状態値、及び当該ノード自体のクロックの状態値も、これらの状態値が第１リストＬ中に格納されている最大の状態値未満であるかあるいは以下である場合に、第１リストＬ中に入れられる。さらに、これらの状態値が第２リストＨ中に既に格納されている最小の状態値より大きいかあるいは最小の状態値以上である場合に、第２リストＨ中に入れられる。この場合に、リストＬ及びリストＨは共に(ｋ＋１)個の位置から成り、従って各場合に(ｋ＋１)個の状態値をリストＬ及びリストＨ中に格納することができる。
【００１８】
この方法は、この方法を実行した後に、最小から(ｋ＋１)個の状態値をこれらの状態値の関数としてリストＬ中に入れて、最大から(ｋ＋１)個の取得した状態値をリストＨ中に入れることを可能にする。この場合には、リストＬ及びＨの個々の位置は、例えば、最小から(ｋ＋１)番目の状態値がリストＬ中の位置Ｌ0に位置し、取得した最小の状態値が位置Ｌkに格納されるように番号付けすることができる。これに対応して、(ｋ＋１)番目に大きい状態値はリストＨ中の位置Ｈ0に格納することができ、取得した最大の状態値は位置Ｈkに格納することができる。
【００１９】
(ｋ＋１)番目に小さい状態値及び(ｋ＋１)番目に大きい状態値から平均値を決定するために、例えば、リストＬ及びリストＨのそれぞれ位置Ｌ0及びＨ0に格納されている状態値から算術平均を求める。この平均値の関数として、次に、ノードに割り当てられたクロックが同期するような修正値を決定する。この目的のために、この修正値は例えば、クロックに割り当てられる絶対値とすることができる。前記修正値を、他のクロックと同期した現在値を得るためにノードに割り当てられたクロックの現在値に加算しなければならない相対値とすることも考えられる。
【００２０】
本発明による方法の１つの特定の利点は、すべての状態値に対してリスト中の位置を用意しない、ということである。むしろ、各リスト中に(ｋ＋１)個の位置のみが存在すれば十分であり、従って、言わば(２ｋ＋２)個の状態値を入れて記憶しなければならない。(ｋ＋１)番目に小さい状態値より大きい状態値、及び(ｋ＋１)番目に大きい状態値より小さい状態値のすべてを、結果的に除外することができる。これにより、メモリー空間を節約すること、及び前記平均値を計算するのに必要な状態値の管理を達成することができる。
【００２１】
本発明による方法によれば、メモリーアクセス動作の回数も結果的に低減することができる。従って、取得した状態値の数が(２ｋ＋２)よりはるかに大きければ、特に、クロックを同期させる特に効率的かつ高速な方法を達成することができる。
【００２２】
近年のバスシステム、例えばFlexRayでは、エラー許容度は例えばｋ＝２である。この場合には、本発明による方法によれば、リストＬ及びリストＨの各々が、３つの位置、即ちそれぞれＬ＝{Ｌ0, Ｌ1, Ｌ2}及びＨ＝{Ｈ0, Ｈ1, Ｈ2}のみを具えていればよい。従って、同期させるべきノードによって取得され、前記修正値の決定において考慮に入れるべきすべての状態値の数が６よりはるかに大きい場合でも、６つの状態値がソート（特定順序に並べ替え）された状態で格納され、状態値の数が６よりはるかに大きいことは、例えば自動車を制御するためのFlexRayバスシステム実現においてしばしば存在する。
【００２３】
本発明の方法の１つの有利な展開では、測定した状態値を第１リストＬ及び／または第２リストＨ中に入れることを逐次的に行う。状態値は通常、ノードによって逐次的に取得されるので、この展開はさらに、取得した状態値を直接処理して、この取得した状態値をリストＬ及び／またはＨの一方に入れるべきか、あるいはこの状態値を除外すべきかに関するチェックを行うことを可能にする。結果的に、多数の状態値の中間記憶が必要なくなり、その結果、ここでもメモリー空間の節約がなされる。これに伴うメモリーアクセス動作の低減により、本発明の方法をより一層高速にすることができる。
【００２４】
この展開のさらなる利点は、その後の状態値を取得していても、最初の状態値の取得と同期の終了との間の時間間隔を低減することができる、ということにある。その結果、最終の状態値の取得に続いて、本発明の方法は、この最終の状態値をリストＬ及び／またはリストＨ中に入れて、位置Ｌ0及びＨ0に格納されている状態値から前記平均値を求めて、前記修正値を決定してクロックを修正する、ということに簡略化される。特に、この展開では、最終の状態値を検出した際に、通常は、取得した状態値の多数が既に除外されている。
【００２５】
好適例では、リストＬを対応するレジスタＬ0, Ｌ1,...,Ｌkによって形成し、かつ／あるいはリストＨを対応するレジスタＨ0, Ｈ1,...,Ｈkによって形成する。こうして、特に高速なクロックの同期を達成することができる、というのは、レジスタは一般にハードウェアで形成され、従って特に高速な書込み及び読出しアクセスを可能にするからである。
【００２６】
第１リストＬを、想定される最大の状態値より大きい値で初期化して、第２リストＨを、想定される最小の状態値より小さい値で初期化することが有利である。リストＬ及びＨのこうした初期化は、すべての状態値について、リストＬ及び／またはリストＨ中に値を入れることが同じ条件に依存する、ということを意味する。これらの条件は既に上述した次の条件によってサポート（支援）される：
−状態値が第１リストＬ中の最大値未満あるいは以下である場合には、リストＬ中に状態値を入れる。
−状態値が第２リストＨ中の最大値より大きいかあるいは最大値以上である場合に、リストＨ中に状態値を入れる。
この好適例では、状態値が既にリストＬ及びＨ中に入れられているか否かとは無関係に、これらの条件を公式化することができる。
【００２７】
取得した状態値をリストＬ中に入れる期間中に、格納されている状態値の大きさの順の並べ替え（ソート）を継続して、値(Ｌ0)≧値(Ｌ1)≧...≧値(Ｌk)が常に真であるようにすることが好ましく、ここにＬ0, Ｌ1,...,ＬkはリストＬの(ｋ＋１)個の位置を表わし、値(Ｌi)は位置Ｌiにおける値を表わす。さらに、取得した状態値をリストＨ中に入れる期間中に、格納されている状態値の大きさの順の並べ替えを継続して、値(Ｈ0)≦値(Ｈ1)≦...≦値(Ｈk)が常に真であるようにすることが好ましく、ここにＨ0, Ｈ1,...,ＨkはリストＨの(ｋ＋１)個の位置を表わし、値(Ｈi)は位置Ｈiにおける値を表わす。
【００２８】
このことは、例えば、一旦、考慮に入れるべき最終の状態値をノードが取得すると、リストＬ及びＨ中への格納が常に保証され、時間を要する格納を実行する必要がない、という状況を特に簡単な方法で達成する。特に、上述した取得した状態値の逐次的な処理に関連して、このことは、取得した状態値のうち(ｋ＋１)番目に小さいものが常に位置Ｌ0に格納され、取得した状態値のうち(ｋ＋１)番目に大きいものが常に位置Ｈ0に格納される、ということも保証する。
【００２９】
さらなる利点は、請求項６及び７に記載の好適例に見ることができる。これらの請求項には、第１リストＬ及び／または第２リストＨ中に状態値Ｚを入れる方法が特に明瞭かつ簡単に記載されている。この目的で、最初に、状態値Ｚの大きさに対応するリストＬ及びＨ内の位置を、例えばそれまでで最大または最小の入れられた要素から始めたリスト中の要素どうしの比較によって決定する。そして状態値Ｚを、これより大きいすべてのリストＬの要素を位置１つ分ずつ下方に移動してリスト中に入れ、位置Ｌ0にあった値が位置Ｌ1にあった値に置き換えられたことの結果として、位置Ｌ0に存在していたリストＬの最大値はリストＬから脱落する。状態値ＺをリストＨ中に入れることについても同じことが当てはまる。
【００３０】
好適例では、次のステップを実行する：
−エラー許容度ｋの関数として、事前に定義可能な終端値Ｂiの集合Ｂ＝{Ｂ0, Ｂ1,...,Ｂk}を次のように定義する。
ｉ∈{０, １,...,(ｋ−１)}なるすべてのｉについて、Ｂ0＝０；Ｂi≦Ｂ(i+1)；
ｊ∈{０, １,...,ｋ}なるすべてのｊについて、２ｊ＜Ｂ(j)；
−Ｂk＞ｎである場合には、ｉ∈{０, １,...,(ｋ−１)}なる値ｉを、取得した状態値の数ｎの関数として、条件Ｂi≦ｎ＜Ｂ(i+1)が真となるように選択する；
−Ｂk≦ｎである場合には、ｉ＝ｋを選択する；
−位置Ｌ(k-1)及びＨ(k-1)に格納されている値から前記平均値を求める。
【００３１】
この好適例は、ノードにおいて取得した状態値の数ｎが(２ｋ＋２)未満であり所定値に達していない場合でも、クロックの同期を保証するのに適している。特に、この場合には、事前に定義されていないが、取得した状態値の数ｎの関数として、事前に定義可能なエラー許容度ｋの関数として、そして事前に定義可能な終端値Ｂ0, Ｂ1,...,Ｂkの関数として決まる実際のエラー許容度ｌが達成され、ここではｌ≦ｋが常に真である。従ってこの好適例は、ノードにおいて取得された状態値の数が元々想定された数より少ない際にも、このノードにおけるクロックの同期が保証されるという利点を有する。特に、この好適例では、ｎ＜(２ｋ＋２)である場合に、エラー許容度ｌ≦ｋでのエラー許容性の同期が可能である。
【００３２】
次の値を事前に定義することが有利である：
−エラー許容度ｋ＝２；
−終端値Ｂ1＝３；
−終端値Ｂ2＝８
【００３３】
これらの値を用いて、取得した状態値のあらゆる数について、通信システム、例えばFlexRayにおけるクロックのエラー許容性の同期を、特に効率的かつ高速に保証することができる。
【００３４】
この目的は、次の構成要素を有するノードによっても達成される：
−クロック；
−当該ノードのタイムベース及び／または他のノードのタイムベースに依存する状態値を取得する手段；
−(ｋ＋１)個の位置から成る第１リスト(Ｌ)及び(ｋ＋１)個の位置から成る第２リスト(Ｈ)；
−取得した状態値を第１リスト(Ｌ)中の対応する位置に入れる手段；
−取得した状態値を第２リスト(Ｈ)中の対応する位置に入れる手段；
−第１リスト(Ｌ)の一要素及び第２リスト(Ｈ)の一要素から平均値を求める手段；
−修正値を求める手段；
−クロックを修正する手段。
【００３５】
請求項１〜９のいずれかに記載の方法は、ノードにおいて実行することが好ましい。
【００３６】
上記目的はさらに、上述した種類の通信システムによって達成され、この通信システムの少なくとも１つのノードは次の構成要素を有する：
−クロック(１５)；
−状態値を取得する手段；
−(ｋ＋１)個の位置から成る第１リスト(Ｌ)及び(ｋ＋１)個の位置から成る第２リスト(Ｈ)；
−取得した状態値を第１リスト(Ｌ)中の対応する位置に入れる手段(１２０)；
−取得した状態値を第２リスト(Ｈ)中の対応する位置に入れる手段(１３０)；
−第１リスト(Ｌ)の一要素及び第２リスト(Ｈ)の一要素から平均値(Ｍ)を求める手段(１６０)；
−修正値(Ｋ)を求める手段；
−クロックを修正する手段(１５)。
【００３７】
請求項１〜９に記載の方法は、前記通信システム内の少なくとも１つのノードにおいて実行することが好ましい。
【００３８】
コンピュータプログラムの形の本発明の実現は特に重要である。この場合には、このコンピュータプログラムはコンピュータ、特にマイクロコンピュータ上で実行することができ、そして本発明の方法を実行するのに適している。従ってこの場合には、本発明をコンピュータプロスラムによって実現して、このコンピュータプログラムは、コンピュータプログラムが実行する方法と同様に本発明を表現する。このコンピュータプログラムは、メモリー素子に記憶することが好ましい。使用するメモリー素子は特に、ランダムアクセスメモリー（ＲＡＭ）、リードオンリーメモリー（ＲＯＭ）、またはフラッシュメモリーである。
【００３９】
本発明をハードウェアで実現することも重要であり、このハードウェアは本発明による方法を実行するのに適している。ハードウェアでの実現は、本発明による方法がより一層高速に実行されるという利点を有する。
【００４０】
以下、本発明の実施例を図面を参照しながらより詳細に説明するが、本発明はこれらの実施例に限定されない。
【発明を実施するための最良の形態】
【００４１】
図１に、通信媒体５経由で互いに接続された複数のノード１０から成る通信システム１を示す。通信媒体５は、例えばFlexRay仕様あるいはＴＴＰ（Time Triggered Protocol）に準拠した時間制御のバスシステム（ＴＴＡ−Time Triggered Architecture）として設計されている。通信媒体５を他のネットワーク・トポロジーに準拠して、例えばリングとして形成することも考えられる。
【００４２】
図１に示す各ノード１０はいわゆるホスト１１及びインタフェース１２を有する。ホスト１１は、例えば単一のマイクロチップ上に形成されたマイクロコンピュータとして構成することができる。ホスト１１を、ネットワーク経由で互いに通信する複数のコンピュータから成るコンピュータシステム全体とすることも同様に考えられる。
【００４３】
インタフェース１２は、ホスト１１と通信媒体５との間に位置する。インタフェース１２は、例えば、情報をメッセージ形式に変換することによってホスト１１から、あるいはホスト１１への情報の伝送を制御し、このメッセージ形式は通信媒体５によって事前に規定されたデータフレームに対応する。フレームは一般に、メッセージフォーマットによって事前に規定された規則に従って解釈される一組のビットである。FlexRayのメッセージフォーマットは、例えば、関係するメッセージを同期に用いるべきか否かを示す特別なＳＹＮＣビット、及び実際のメッセージ（有効なデータ）を含むデータバイト数を示すＬＥＮビットを表示する。
【００４４】
もちろん、ホスト１１及びインタフェース１２を単に同一チップ上の異なる機能ユニットとして設計することも可能である。
【００４５】
時間制御の通信システム５では、通信の帯域幅を１つ（以上）の大域的（グローバル）時系列（グローバル・スケジュールとして知られている）の形で固定的に事前規定することができる。こうしたスケジュールは、ノード１０が通信媒体５によってメッセージを送信可能な時間及びノード１０がメッセージを期待している時間についての情報を具えている。メッセージが例えばフレームで送信される場合には、スケジュールは特に、ノード１０がどのフレームをメッセージの送信に利用可能であるかについての情報を提供する。
【００４６】
通信媒体５上の通信全体がグローバル・スケジュールによって制御されているので、メッセージは受信者または送信者の情報を何ら含む必要はない。各ノード１０は、メッセージの送信者または受信者を、このメッセージが送信された時点に基づいて識別する。従って、フレーム内にアドレスフィールドは必要なく、これにより帯域幅が増加する。
【００４７】
図２ａにインタフェース１２を示し、インタフェース１２はクロック１５、マイクロプロセッサ２０、及びメモリー素子３０を有する。メモリー素子３０は、例えばランダムアクセスメモリー（ＲＡＭ）として設計することができ、アドレス指定可能なメモリー領域Ｌ0, Ｌ1,...,Ｌk及びＨ0, Ｈ1,...,Ｈkを有する。インタフェース１２は、例えばリードオンリーメモリー（ＲＯＭ）として構成された他のメモリー素子３１も有する。メモリー素子３１には、例えば本発明による方法を実行すべくプログラムされたコンピュータプログラムを記憶することができる。もちろん、メモリー素子３０及び３１を単一のメモリー素子として形成することも考えられる。
【００４８】
図２ｂに示すインタフェース１２も同様に、クロック１５、マイクロプロセッサ２０、及びメモリー素子３１を有する。しかし、この場合には、マイクロプロセッサ２０はレジスタＬ0, Ｌ1,...,Ｌk及びＨ0, Ｈ1,...,Ｈkを有する。図２ｂに示すインタフェース１２の具体例は、図２ａに示す具体例と比較して、レジスタＬ0, Ｌ1,...,Ｌk及びＨ0, Ｈ1,...,Ｈkにアクセスするのに要する時間が他のメモリー素子の場合よりも短いという利点を有する。その結果、レジスタＬ0, Ｌ1,...,Ｌk及びＨ0, Ｈ1,...,Ｈkを、これらに対応する図２ａに示すメモリー領域の代わりに用いると、データをより高速に位置Ｌ0, Ｌ1,...,Ｌk, Ｈ0, Ｈ1,...,Ｈkに書き込み、そしてこれらの位置から読み出すことができる。
【００４９】
図３に通信サイクル５１を示し、その始点を破線５２で示し、その終点を破線５３で示す。通信サイクルの始点では、例えば、いわゆるＳＹＮＣシンボル５５を送信し、ＳＹＮＣシンボル５５は通信に関係するすべてのノード１０が通信サイクル５１の始点を認識することを可能にする。しかし、ＳＹＮＣシンボル５５なしで通信サイクルを開始することも可能である。通信サイクル５１内では、一般に複数のフレーム７１、７２、７３、７４...を送信し、図には例としてこのうちの４フレームを示す。時間制御の伝送法では、フレーム７１、７２、７３、７４を規定可能ないわゆる時間スロット（タイムスロット）内で送信し、図ではこれらの時間スロットの始点をそれぞれ６１、６２、６３、６４で表わす。フレーム７１、７２、７３、７４どうしの間には、メッセージを伝送しない時間間隔、いわゆるフレーム間ギャップ８１、８２、８３、８４が存在する。フレーム間ギャップ８１、８２、８３、８４は、通信システム１内の複数のノード１０のクロック１５どうしが少し異なる場合にも、フレーム７１、７２、７３、７４をこれらのフレーム送信中のノードのうちの１つに対応させて一意的に識別することを可能にするために必要である。
【００５０】
通信媒体５経由で通信中のすべてのノード１０が、フレーム７１、７２、７３、７４のノード１０への割り当てに関してフレーム７１、７２、７３、７４を同等に評価するために、これらのノード１０のクロックが同期していることが特に重要である。この場合には、クロック１５をホスト１１内またはインタフェース１２内に配置することができる。クロック１５の同期の処理も原則的には、ホスト１１内またはインタフェース１２内で同様に行われる。
【００５１】
しかし、通信の帯域は通信システム１内でのクロック１５の同期の精度に依存する、というのは、すべてのノード１０によるフレーム７１、７２、７３、７４の一意的な識別を保証するためには、フレーム７１、７２、７３、７４が互いに直接連続せず、フレーム７１、７２、７３、７４どうしの間にフレーム間ギャップ８１、８２、８３、８４が存在するからである。フレーム間ギャップ８１、８２、８３、８４は、１番目のフレーム７１、７２、７３、７４の終点と、これに続く２番目のフレーム７１、７２、７３、７４の始点との間に経過する時間間隔を表わす。従って十分正確に同期したクロックが与えられれば、これにより、２つのノード１０が同じフレーム７１、７２、７３、７４を、スケジュールに対するこれらのノードの現在時刻（が異なること）に起因して異なるように解釈して、例えばグローバル（大域的）クロックに比べて遅いクロック１５を有するノード１０が２番目のフレーム７１、７２、７３、７４を１番目のフレームとして誤って解釈する、という状況を防止することができる。
【００５２】
ノード１０のクロック１５どうしが互いに正確に同期するほど、個々のフレーム７１、７２、７３、７４間のフレーム間ギャップ８１、８２、８３、８４を小さくすることができる。個々のフレーム７１、７２、７３、７４間のフレーム間ギャップ８１、８２、８３、８４が小さいほど通信の帯域幅が大きくなる。
【００５３】
一般に、同期は特化したハードウェアによって行うことができ、このハードウェアはインタフェース１２内に集積され、同様にインタフェース１２内に集積されたクロック１５の高速かつ正確な同期を達成することを可能にする。
【００５４】
図４に、本発明による方法の非常に簡略化したフローチャートを示す。この方法はステップ１００において、例えばノード１０において、このノード１０に割り当てられたクロック１５の同期を行うべき時点から始まる。この方法の開始時に、特定変数の初期化を行う。例として、取得した状態値の数ｎを０に設定する（ｎ＝０）。
【００５５】
ステップ１１０では、例えば、通信媒体５によって送信されたフレーム７１、７２、７３、７４をノード１０が同期メッセージとして解釈して、状態値Ｚをフレーム７１、７２、７３、７４の対応するビットから読み出すことによって状態値Ｚを取得し、前記対応するビットはメッセージフォーマットにおいて規定されている。状態値Ｚの取得に続いて、取得した状態値の数ｎを１だけ増加させる（ｎ＋＋）。
【００５６】
ステップ１２０では、取得した状態値Ｚが例えばレジスタＬ0及びＬkによって形成される第１リストＬ中に格納されている最大値より小さい場合に、状態値Ｚを第１リストＬ中に入れる。いずれの場合にも、何個の状態値が既にリストＬ中に格納されているかについてのチェックを行うことなしに、最初のｋ個の取得した状態値がリストＬ中に格納されることを保証するために、初期化ステップ１００では、レジスタＬ0〜Ｌkを、想定されるあらゆる状態値Ｚより大きい＋∞の値に初期化して、すべてのＺについてＺ＜＋∞が常に真であるようにする。
【００５７】
状態値ＺをリストＬ中に入れることに関する、擬似コードの表記法を用いた好適な方法を以下に示す。この場合には、レジスタＬ0,...,Ｌkに格納されている値をＬ[0],...,Ｌ[k]で表わす：
(l1) for (i=k; i≧0; i--) {
(l2) if (Z<L[i]) {
(l3) for (j=0; j<i; j++) {
(l4) L[j]=L[j+1];
(l5) }
(l6) L[i]=Z;
(l7) break i;
(l8) }
(l9) }
【００５８】
行(l1)では、カウンタｉを初期化して最初のループを規定する。ループを通過する毎に、ｉ＝ｋから始まる値ｉを値１だけ低減する（i--）。そしてｉの値に応じて、行(l2)〜(l7)の命令を実行する。行(l2)の質問を伴う最初のループによって、リストＬの全体の位置またはレジスタＬiのうち、状態値Ｚが当該位置またはレジスタＬiに格納されている値より小さいような位置またはレジスタＬiを探索する。こうした位置が見つからなければ、状態値ＺをリストＬ中に入れずに除外する。しかし、行(l2)においてこうした位置が認識された場合には、行(l3)〜(l5)によって規定される２番目のループを行(l3)において初期化して開始する。この２番目のループでは、ｊ＜ｉであれば、リスト中の位置Ｌjにおける各値を、次に上位の位置に格納されている値Ｌ(j+1)で置き換える。従って、行(l2)で見つけた、位置Ｌiより下位の位置にあるすべての値を位置１つ分ずつ下方に移動して、位置Ｌ0にある値は脱落させる。次に行(l6)では、状態値Ｚを上記位置またはレジスタＬiに格納して、状態値Ｚを入れる動作を終了する（break i）。
【００５９】
図４に示す本発明による方法のステップ１３０では、ステップ１２０と同様に、取得した状態値Ｚが、例えばレジスタＨ0〜Ｈkによって形成されるリストＨに格納されている最小値より大きい場合に、状態値ＺをリストＨ中に入れる。いずれの場合にも、何個の状態値が既にリストＨ中に格納されているかについてのチェックを行うことなしに、最初のｋ個の取得した状態値がリストＨ中に格納されることを保証するために、初期化ステップ１００では、レジスタＨ0〜Ｈkを、想定されるあらゆる状態値Ｚより小さい−∞の値に初期化して、すべてのＺについてＺ＞−∞が常に真であるようにする。
【００６０】
状態値ＺをリストＨ中に入れることも同様に、例として擬似コードで示す。この場合には、レジスタＨ0,...,Ｈkに格納されている値をＨ[0],...,Ｈ[k]で表わす：
(h1) for (i=k; i≧0; i--) {
(h2) if (Z<H[i]) {
(h3) for (j=0; j<i; j++) {
(h4) H[j]=H[j+1];
(h5) }
(h6) H[i]=Z;
(h7) break i;
(h8) }
(h9) }
【００６１】
行(h1)でも、カウンタｉを初期化して最初のループを規定する。そしてｉの値に応じて、行(h2)〜(h7)の命令を実行する。行(h2)の質問を伴う最初のループによって、リストＨの全体の位置またはレジスタＨiのうち、状態値Ｚが当該位置またはレジスタＨiに格納されている値より大きいような位置またはレジスタＨiを探索する。こうした位置Ｈiが見つからなければ、状態値ＺをリストＨ中に入れずに除外する。しかし、行(h2)においてこうした位置が認識された場合には、行(h3)〜(h5)によって規定される２番目のループを行(h3)において初期化して開始する。この２番目のループでは、ｊ＜ｉであれば、リスト中の位置Ｈjにおける各値を、次に上位の位置に格納されている値Ｈ(j+1)で置き換える。従って、行(h2)で見つけた、位置Ｈiより下位の位置にあるすべての値を位置１つ分ずつ下方に移動して、位置Ｈ0にある値は脱落させる。次に行(h6)では、状態値Ｚを上記位置またはレジスタＨiに格納して、状態値Ｚを入れる動作を終了する（break i）。
【００６２】
ステップ１４０では、例えばさらなるＳＹＮＣフレームが認識されているので、新たな状態値Ｚを取得すべきか否かについてのチェックを行う。新たな状態値を取得すべき場合には、本発明の方法をステップ１１０から継続する。そうでない場合には、ステップ１５０では、値ｊを、取得した状態値Ｚの数ｎの関数及び終端値Ｂiの関数として定める。値ｊは、取得した状態値の数ｎが(２ｋ＋２)より小さい場合でも、本発明による方法のさらなるステップによるエラー許容性の同期を可能にするために定める。
【００６３】
値ｊは次式が常に真であるように定める：
ｊ∈{０, １,...,(ｋ−１)}なるすべてのｊについて、Ｂj≦ｎ＜Ｂ(j+1)
【００６４】
終端値Ｂi（またはＢj）は、ステップ１００の初期化段階で初期化することが好都合である。この場合には、終端値Ｂiは次の条件を満足するように初期化する：
Ｂ0＝０；
ｉ∈{０, １,...,(ｋ−１)}なるすべてのｉについて、Ｂi≦Ｂ(i+1)；
ｊ∈{０, １,...,ｋ}なるすべてのｊについて、２ｊ＜Ｂj；
【００６５】
事前に規定されたエラー許容度ｋ＝２に対して、ｉ∈{０, １, ２}なるｉについての終端値Ｂiを次のように定める：
Ｂ0＝０；
Ｂ1＝３；
Ｂ2＝８；
【００６６】
終端値Ｂjは上記のように選択し、例えば状態値を５つだけ取得している場合には、結果的にｎ＝５であり、従って値ｊについてはｊ＝１である。ステップ１６０では、各場合において、値ｊの関数として、リストＬからの１つの値及びリストＨからの１つの値より、同期のために使用可能な平均値Ｍを、例えば次式（いわゆる算術平均）に従って決定する：
【数１】
【００６７】
取得した状態値の数ｎがｎ≧(２ｋ＋２)である場合に、値ｊはｊ＝ｋである。従って、この場合には、平均値Ｍは位置Ｌ0及びＨ0に格納されている値から求める。上述したように、ステップ１２０及び１３０では、取得した状態値のうち最小のものが位置Ｌkに位置し、取得した状態値のうち最大のものが位置Ｈkに位置するように、状態値ＺをリストＬ及びＨに入れる。さらに、ｎ≧(２ｋ＋２)については、(ｋ＋１)番目に小さい値を位置Ｌ0に格納し、(ｋ＋１)番目に大きい値を位置Ｈ0に格納する。従って、ｎ≧(２ｋ＋２)であれば、平均値Ｍは、取得した状態値の(ｋ＋１)番目に小さい値及び(ｋ＋１)番目に大きい値から求める。このことは特に、取得した状態値のｋ番目に大きい値及びｋ番目に小さい値は、平均値を決定する際に考慮に入れず、そしてこのことはエラー許容度ｋによることを意味する。
【００６８】
ｋ＝２に対する終端値Ｂiをここでも上記のように定め、取得した状態値の数がここでもｎ＝５である場合には、値ｊはここでもｊ＝１であり、従ってこの場合には、前記平均値は位置Ｌ(k-1)＝Ｌ(1)及びＨ(k-1)＝Ｈ(1)に格納されている値から求める。この例より、ｎ＜(２ｋ＋２)であっても、本発明の方法によりエラー許容性のクロックの同期が可能であることがわかる。この例では、この可変のエラー許容度ｌは例えばｌ＝１である。
【００６９】
ステップ１７０では、修正値Ｋを平均値Ｍの関数として決定し、ステップ１８０では、ノード１０に割り当てられたクロック１５を修正値Ｋの関数として同期させ、そしてステップ１９０で本発明の方法を終了する。修正値Ｋは、例えば、ノード１０に割り当てられたクロック１５の現在の状態値を考慮に入れた相対値とすることができ、これにより、クロック１５を同期させるためには、修正値Ｋを現在の状態値に加算するだけでよい。
【００７０】
もちろん、図４に示す方法にさらなるステップを加えるか、あるいはいくつかのステップを省略することも考えられる。特に、個々のステップを組み合わせること、及び／または複数のステップの実行あるいは個々のステップの動作を異なる順序にすることも考えられる。もちろん、本発明による方法の実現を実施例から離れて、特に擬似コードで示す具体例から離れて行うことも可能である。
【００７１】
図４に示す本発明の方法の実施例は、例えばコンピュータプログラムの形で実現することができる。しかし、特に、本発明による方法のより高速な実現を達成するために、この方法をハードウェア、例えばいわゆるＡＳＩＣ（Application-Specific Integrated Circuit：特定用途向け集積回路）によって実現することもできる。既存のハードウェア、例えばインタフェース１２内の特定の機能ユニットを、本発明の方法を実行可能なように拡張することも考えられる。
【００７２】
さらに、すべての参照符号及び指標、例えばリストＬ及びＨの位置の番号付けは固定のものではなく、論理的な称号と考えるべきものである。従って、リストＬ及びＨ、及びこれらのリスト中の位置は異なる表わし方をすることも考えられる。番号付けの変更、特に格納順序の反転も考えられる。格納順序を反転する場合には、例えば、(ｋ＋１)番目に小さい値を位置Ｌ(k)に格納して(ｋ＋１)番目に大きい値を位置Ｈ(k+1)に格納する。本発明による方法のステップ、特にステップ１２０、１３０及び１６０は、これに応じて改変しなければならない。
【００７３】
図５に、取得した状態値ＺをリストＬ及びＨ中に入れる手順の例を示す。この場合には、リスト中に入れる動作は図４に示す本発明による方法のステップ１２０及び１３０の説明と同様に行う。図にはリストＨ及びＬを示し、これらのリストは位置Ｈ0, Ｈ1, Ｈ2及びＬ0, Ｌ1, Ｌ2を有する。Ｚは、リストＬ及びＨ中に入れるべき取得した状態値を表わす。最初（ｎ＝１）に取得した状態値Ｚ＝５を入れる前に、位置Ｌ0, Ｌ1, Ｌ2を＋∞に初期化し、位置Ｈ0, Ｈ1, Ｈ2を−∞に初期化する。この場合には、値＋∞及び−∞は、−∞が取得すべきあらゆる状態値Ｚより小さく、＋∞が取得すべきあらゆる状態値Ｚより大きいように選択し、言わばすべてのＺについて−∞＜Ｚ＜＋∞が常に真であるようにする。
【００７４】
最初は、擬似コードを用いて上述し図４に示す実施例と同様に、取得した状態値Ｚを格納すべき位置Ｌi及びＨiを探索する。こうした位置Ｌi及びＨiは、これらのリストを最上位から最下位まで探索すれば、それぞれＬ[i]＞ＺまたはＨ[i]＜Ｚであれば認識され、この探索は本実施例では言わばＬ2→Ｌ1→Ｌ0及びＨ2→Ｈ1→Ｈ0の順である。最初の状態値Ｚ＝５に対して、位置Ｌ2及びＨ2が決まる。従って位置Ｌ0及びＨ0にある値はそれぞれ位置Ｌ1及びＨ1にある値に置き換えられ、そして位置Ｌ1及びＨ1にある値はそれぞれ位置Ｌ2及びＨ2にある値に置き換えられる。従って、各場合に、リストＬ及びＨ中の値は位置１つ分ずつ下方に移動され、位置Ｌ0及びＨ0にある最下位の値は脱落する。従って状態値Ｚ＝５は位置Ｌ2及びＨ2に格納される。
【００７５】
次に、上述した方法に従い、２番目の（ｎ＝２）状態値Ｚ＝７を取得して位置Ｈ2及びＬ2に格納する。ここでも、これらの位置にある値は、位置Ｌ0及びＨ0にある値が脱落するまで位置１つ分ずつ下方に移動する。
【００７６】
次に、上述した方法に従い、３番目の（ｎ＝３）状態値Ｚ＝−３を取得して位置Ｈ2及びＬ2に格納する。ここでも、これらの位置にある値を位置１つ分ずつ下方に移動する。位置Ｌ0及びＨ0にある値は脱落する。
【００７７】
図５に示す実施例では、さらなる状態値Ｚは検出されないものと仮定する。次に値ｊを図４のステップ１５０及び１６０、及び例としてこの図に示す終端値Ｂiに対する値と同様に決定する。結果的に、位置Ｌ(２−１)及びＨ(２−１)にある値を用いて平均値Ｍを求め、従ってＭ＝５となる。
【００７８】
図６に、取得した状態値ＺをリストＬ及びＨ中に入れる手順のさらなる例を示す。この場合にも、リスト中に入れる動作は、図４に示す本発明による方法のステップ１２０及び１３０の説明と同様に行う。
【００７９】
しかしこの例では、(２ｋ＋２)より多数の状態値Ｚを取得してリストＬ及びＨ中に入れる。最初に、図５において既に説明したように、最初２つの状態値Ｚ＝５及びＺ＝７をリストＬ及びＨ中に入れる。次に、ｍ＞２に対するさらなる(２ｋ＋ｍ−１)個の状態値Ｚを入れるが、このことは図６に示しておらず、(ｎ＝２)から(ｎ＝２ｋ＋ｍ)への遷移を（縦に連続した）点々のみによって示す。
【００８０】
そして、(２ｋ＋ｍ)番目に取得した状態値Ｚ＝７を図４のステップ１２０及び１３０と同様に扱い、リストＨ及びＬ中に適宜入れる。この場合には、リストＬ中に格納されているすべての値がＺ＝７より小さい。従って状態値７はリストＬ中には格納されない。しかし、リストＨ中に格納されている値をチェックすれば、位置Ｈ0にある値が位置Ｈ1にある値に置き換えられた後に、値Ｚ＝７が位置Ｈ1に格納されることがわかる。従って位置Ｈ0にある値はリストから脱落する。
【００８１】
同様に、最終のさらなる状態値Ｚ＝−３を取得して位置Ｌ0に格納する。ここでは(２ｋ＋２)より多数の状態値を取得しているので、位置Ｌ0及びＨ0にある値を用いて平均値Ｍを求める。結果的に、クロック１５のエラー許容性の同期が、エラー許容度ｋ＝２で可能になる。
【００８２】
図４及び図５に示す例、及び図４に示す実施例でも、入れる動作を、取得した状態値Ｚに対して、まずこの状態値が位置Ｌ0及びＨ0に格納されている値より小さいか大きいかについてのチェックを行って、このことが成り立つ場合のみに、この状態値を格納する適切な位置を見つけるプロセスを開始する。このようにして、特に、取得した状態値の数ｎが(２ｋ＋２)よりはるかに多いことがしばしばある場合に、本発明による方法を実行するために要する時間を低減することができる。
【図面の簡単な説明】
【００８３】
【図１】通信媒体経由で通信する複数のノードから成る通信システムを示す図である。
【図２ａ】ノードの選択した構成要素を図式的に示す図である。
【図２ｂ】図２ａに示すノードの構成要素の他の構成を図式的に示す図である。
【図３】複数のフレームを有する通信サイクルを図式的に示す図である。
【図４】本発明による方法を示すフローチャートである。
【図５】本発明による方法の実行中にリストＬ及びＨに格納されている状態値Ｚを図式的に示す図であり、ここにｎ＜(２ｋ＋２)である。
【図６】図５と同様の図であり、ここにｎ≧(２ｋ＋２)である。
【技術分野】
【０００１】
本発明は、通信媒体経由で通信するノードに割り当てられたクロックの時間同期の方法に関するものである。
【０００２】
本発明はさらに、通信媒体によって他のノードと通信するノード、及び通信媒体経由で通信する複数のノードを有する通信システムに関するものである。
【０００３】
本発明は、コンピュータ、特にマイクロコンピュータ上で実行可能なコンピュータプログラムにも関するものである。
【背景技術】
【０００４】
通信媒体経由で通信するノードは例えば、バスシステムまたはネットワークによって互いにメッセージを交換する制御装置、センサ及びアクチュエータである。こうしたノード及び関連する通信媒体から成る通信システムは、例えば航空機または自動車を制御するために用いることができる。この場合の「ノード」とは、特にいわゆるインタフェースも含み、インタフェースは、通信媒体への物理的接続、及び送受信されたメッセージを処理する責任を共に負う。
【０００５】
現代の通信システムは通常、エラー（誤り）を許容すべく設計されており、このため少なくとも特定の基本機能は、通信システム内にエラーが発生してもなお、適正に実行される。このことは、例えば通信システムが安全に厳格な環境で、たとえば航空機を制御するため、あるいは自動車を制御するために使用される場合に特に重要である。従ってこうした基本機能は例えば、通信システム内にエラーが発生しても航空機がまだ制御可能であることを保証する。
【０００６】
例として、エラー許容性の通信システムは、ノード内またはメッセージの送信中に発生したエラーを取り扱う際には、このエラーが結果的なエラー、例えば、誤って送信、転送、または受信されたメッセージによって他のノードが誤ったメッセージを生成すること、あるいは他のノードがその機能を適正に実行し続けることが阻害されることが生じないことが保証されるように設計されている。こうしたメカニズムなしでは、例えば、ノード（いわゆる「バブリング・イディオット（bubbling idiot、不法大量発信者）」）が非常に大量のメッセージを通信媒体経由で送信して、他のノードからの送信データの破壊活動が生じ得るか、及び／または通信媒体が過負荷になり、このため他のノードがもはや利用不能、あるいは少なくとも十分に利用できなくなる、ということが生じ得る。
【０００７】
現在使用されている通信システムでは、特に安全に厳格な環境における通信媒体において、例えば結果的なエラーの発生を低減するために、いわゆる時間制御送信法がますます使用されている。この場合には一般に、ノードが特定時刻にメッセージを送信することのみ可能である。この方法は、通信媒体が常に、特に重要なメッセージ、例えば安全関係の用途向けのメッセージを送信可能であるのに十分な容量を有することも保証する。
【０００８】
多くの通信システムが、その適正な動作のために、いわゆるグローバルタイム（大域的時間）を必要とする。このことは例えば、複数の特定イベントの同時性、例えば種々のセンサの取得値の同時変化を規定するために重要である。グローバルタイムは特に、時間制御のメッセージ送信にとっても、例えばノードが送信可能である時点を確定するために必要である。さらに、多くの時間制御の通信媒体の場合に、このメッセージを受信した時刻にもとづいてメッセージの送信者を推察することができる。
【０００９】
グローバルタイムを決定する種々の方法が知られている。例として、通信システムには中心クロックが存在し、その現在値は通信媒体によって対応するノードに送信される。しかし、この方法は、例えばグローバルクロックの不具合が、中心クロックが絶えず同じ値を現在値として出力するということを生じさせて、このことは通常、通信システムの不具合となる、という欠点を有する。さらに、元々正しく送信されたグローバル時間の転送または受信時のエラーが、２つのノードに異なる現在時刻を捉えさせ、従って不具合のきっかけ、あるいは正しい通信の妨げとなり得る。
【００１０】
従って、通常、複数のクロックが使用される。例として、各ノードが自前のクロックを有することができる。しかし、これらのクロックの不正確さ、及び欠陥のあるクロックによって生じ得るエラーにより、これらのクロックによって決まる現在時刻は通常、時間と共に互いに一層異なってくる。従って、一様なグローバルタイムを決定するためにクロックの同期を行う。この場合には、特に、クロックを同期させるためのエラー許容性の方法を利用し、この方法では、特定数のクロックによって誤って設定、転送、または受信された現在時刻がクロックの同期に対して悪影響を与えることがあり得ない。特に、こうした方法は、誤った値を供給しているクロック、あるいは新たに始動させたクロックが他のクロックと同期することを可能にする。
【００１１】
通信システム上でメッセージを送信する時間ベースの方法では、個々のメッセージをフレームとして知られている時間ウィンドウ（窓）内で送信する。フレームは通信媒体経由で、グローバルタイムの関数として送信され、グローバルタイムを一意的に各フレームに割り当てることができる。このことは、各ノードがグローバルタイムにもとづいて各フレームを明確に識別することを可能にする。従って特に、各ノードは、どのフレームがメッセージの送信用に自ノードに割り当てられているかを認識することができる。グローバルタイムが自ノードのクロックの関数として決まるならば、種々のノードによって決まる２つの同期サイクル間のグローバルタイムが異なり得る。しかし、フレームをグローバルタイムに一意的に割り当てることを保証できるためには、２つの同期サイクル間に２つのクロック間に最大あり得る偏差に応じた時間間隔が、個々のフレーム間に存在しなければならない。しかし、フレーム間ギャップとして知られているこの時間間隔中にはメッセージを送信することができないので、フレーム間ギャップの長さは通信媒体の帯域幅（単位時間当りに伝送可能なデータ量）に悪影響する。このことは、帯域幅がクロックの精度に依存することを意味する。
【００１２】
クロックの平均精度は、連続する２つの同期間の時間間隔の大きさに依存し、言わば、新たな同期が行われるまでに複数クロックの現在時刻が互いに異なる「長さ」従って「幅」に依存する。クロックの平均精度は同期を行う速さにも依存する、というのは、送信時刻と、同期方法の期間中に決まる修正値による実際のクロックの修正との間でも、クロックが既に互いにずれていることがあるからである。
【００１３】
クロックを同期させるために、平均の算出にもとづく方法（いわゆる平均ベースの方法）が存在する。例えばバスシステムＴＴＡ及びFlexRayにおいて用いられる平均ベースの方法では、同期させるべき各ノードが、他の種々のクロックによって当該ノードに送信され、現在取得した時刻または状態値の平均を決定する。この方法において、あるノードに送信される特定数の誤ったクロック時刻からの独立を達成するために、いわゆるエラー許容度ｋを保証する。この場合には、例えば、他のクロックの状態値とは非常に異なる１つ以上の状態値（例えばｋ番目に大きい状態値及びｋ番目に小さい状態値）は、前記平均の決定中に考慮に入れない。
【００１４】
特に、平均ベースの方法は、エラー許容性のクロックの同期のために、特定した現在の状態値の特定の最小数ｎ、例えばｎ≧(２ｋ＋２)なるｎを必要とする。このことが達成されていなければ、同期を行うことができないか、あるいは同期を保証するために時間を要する方法が必要であるかのいずれかである。
【発明の開示】
【発明が解決しようとする課題】
【００１５】
本発明の目的は、特に高速かつ効率的な方法で実行され、できる限りエラー許容性のクロックの時間同期を可能にする能力を提供することにある。
【課題を解決するための手段】
【００１６】
この目的は、上述した方法が次のステップを有することによって達成される：
−少なくとも同期させるべきノードについて、当該ノードのタイムベースに依存する状態値を取得するステップと；
−取得した状態値のすべてについて、取得した状態値が(ｋ＋１)個の位置から成る第１リストＬの(ｋ＋１)番目に小さい要素未満であるか、あるいは(ｋ＋１)番目に小さい要素以下であり、ここにｋは事前に定義可能なエラー許容度である場合に、取得した状態値を第１リストＬ中の対応する位置に入れるステップと；
−取得した状態値のすべてについて、取得した状態値が(ｋ＋１)個の位置から成る第２リストＨの(ｋ＋１)番目に大きい要素より大きいか、あるいは(ｋ＋１)番目に大きい要素以上である場合に、取得した状態値Ｚを第２リストＨ中の対応する位置に入れるステップと；
−ｎ≧(２ｋ＋２)であり、ここにｎは取得した状態値の数である場合に、第１リストＬの(ｋ＋１)番目に小さい要素及び第２リストＨの(ｋ＋１)番目に大きい要素から平均値を求めるステップと；
−修正値をこの平均値の関数として決定するステップと；
−同期させるべきクロックの現在の状態値がこの修正値を計算に入れるように、このクロックを修正する。
【００１７】
（本発明の利点）
本発明による方法では、他のノードのクロックの状態値、及び当該ノード自体のクロックの状態値も、これらの状態値が第１リストＬ中に格納されている最大の状態値未満であるかあるいは以下である場合に、第１リストＬ中に入れられる。さらに、これらの状態値が第２リストＨ中に既に格納されている最小の状態値より大きいかあるいは最小の状態値以上である場合に、第２リストＨ中に入れられる。この場合に、リストＬ及びリストＨは共に(ｋ＋１)個の位置から成り、従って各場合に(ｋ＋１)個の状態値をリストＬ及びリストＨ中に格納することができる。
【００１８】
この方法は、この方法を実行した後に、最小から(ｋ＋１)個の状態値をこれらの状態値の関数としてリストＬ中に入れて、最大から(ｋ＋１)個の取得した状態値をリストＨ中に入れることを可能にする。この場合には、リストＬ及びＨの個々の位置は、例えば、最小から(ｋ＋１)番目の状態値がリストＬ中の位置Ｌ0に位置し、取得した最小の状態値が位置Ｌkに格納されるように番号付けすることができる。これに対応して、(ｋ＋１)番目に大きい状態値はリストＨ中の位置Ｈ0に格納することができ、取得した最大の状態値は位置Ｈkに格納することができる。
【００１９】
(ｋ＋１)番目に小さい状態値及び(ｋ＋１)番目に大きい状態値から平均値を決定するために、例えば、リストＬ及びリストＨのそれぞれ位置Ｌ0及びＨ0に格納されている状態値から算術平均を求める。この平均値の関数として、次に、ノードに割り当てられたクロックが同期するような修正値を決定する。この目的のために、この修正値は例えば、クロックに割り当てられる絶対値とすることができる。前記修正値を、他のクロックと同期した現在値を得るためにノードに割り当てられたクロックの現在値に加算しなければならない相対値とすることも考えられる。
【００２０】
本発明による方法の１つの特定の利点は、すべての状態値に対してリスト中の位置を用意しない、ということである。むしろ、各リスト中に(ｋ＋１)個の位置のみが存在すれば十分であり、従って、言わば(２ｋ＋２)個の状態値を入れて記憶しなければならない。(ｋ＋１)番目に小さい状態値より大きい状態値、及び(ｋ＋１)番目に大きい状態値より小さい状態値のすべてを、結果的に除外することができる。これにより、メモリー空間を節約すること、及び前記平均値を計算するのに必要な状態値の管理を達成することができる。
【００２１】
本発明による方法によれば、メモリーアクセス動作の回数も結果的に低減することができる。従って、取得した状態値の数が(２ｋ＋２)よりはるかに大きければ、特に、クロックを同期させる特に効率的かつ高速な方法を達成することができる。
【００２２】
近年のバスシステム、例えばFlexRayでは、エラー許容度は例えばｋ＝２である。この場合には、本発明による方法によれば、リストＬ及びリストＨの各々が、３つの位置、即ちそれぞれＬ＝{Ｌ0, Ｌ1, Ｌ2}及びＨ＝{Ｈ0, Ｈ1, Ｈ2}のみを具えていればよい。従って、同期させるべきノードによって取得され、前記修正値の決定において考慮に入れるべきすべての状態値の数が６よりはるかに大きい場合でも、６つの状態値がソート（特定順序に並べ替え）された状態で格納され、状態値の数が６よりはるかに大きいことは、例えば自動車を制御するためのFlexRayバスシステム実現においてしばしば存在する。
【００２３】
本発明の方法の１つの有利な展開では、測定した状態値を第１リストＬ及び／または第２リストＨ中に入れることを逐次的に行う。状態値は通常、ノードによって逐次的に取得されるので、この展開はさらに、取得した状態値を直接処理して、この取得した状態値をリストＬ及び／またはＨの一方に入れるべきか、あるいはこの状態値を除外すべきかに関するチェックを行うことを可能にする。結果的に、多数の状態値の中間記憶が必要なくなり、その結果、ここでもメモリー空間の節約がなされる。これに伴うメモリーアクセス動作の低減により、本発明の方法をより一層高速にすることができる。
【００２４】
この展開のさらなる利点は、その後の状態値を取得していても、最初の状態値の取得と同期の終了との間の時間間隔を低減することができる、ということにある。その結果、最終の状態値の取得に続いて、本発明の方法は、この最終の状態値をリストＬ及び／またはリストＨ中に入れて、位置Ｌ0及びＨ0に格納されている状態値から前記平均値を求めて、前記修正値を決定してクロックを修正する、ということに簡略化される。特に、この展開では、最終の状態値を検出した際に、通常は、取得した状態値の多数が既に除外されている。
【００２５】
好適例では、リストＬを対応するレジスタＬ0, Ｌ1,...,Ｌkによって形成し、かつ／あるいはリストＨを対応するレジスタＨ0, Ｈ1,...,Ｈkによって形成する。こうして、特に高速なクロックの同期を達成することができる、というのは、レジスタは一般にハードウェアで形成され、従って特に高速な書込み及び読出しアクセスを可能にするからである。
【００２６】
第１リストＬを、想定される最大の状態値より大きい値で初期化して、第２リストＨを、想定される最小の状態値より小さい値で初期化することが有利である。リストＬ及びＨのこうした初期化は、すべての状態値について、リストＬ及び／またはリストＨ中に値を入れることが同じ条件に依存する、ということを意味する。これらの条件は既に上述した次の条件によってサポート（支援）される：
−状態値が第１リストＬ中の最大値未満あるいは以下である場合には、リストＬ中に状態値を入れる。
−状態値が第２リストＨ中の最大値より大きいかあるいは最大値以上である場合に、リストＨ中に状態値を入れる。
この好適例では、状態値が既にリストＬ及びＨ中に入れられているか否かとは無関係に、これらの条件を公式化することができる。
【００２７】
取得した状態値をリストＬ中に入れる期間中に、格納されている状態値の大きさの順の並べ替え（ソート）を継続して、値(Ｌ0)≧値(Ｌ1)≧...≧値(Ｌk)が常に真であるようにすることが好ましく、ここにＬ0, Ｌ1,...,ＬkはリストＬの(ｋ＋１)個の位置を表わし、値(Ｌi)は位置Ｌiにおける値を表わす。さらに、取得した状態値をリストＨ中に入れる期間中に、格納されている状態値の大きさの順の並べ替えを継続して、値(Ｈ0)≦値(Ｈ1)≦...≦値(Ｈk)が常に真であるようにすることが好ましく、ここにＨ0, Ｈ1,...,ＨkはリストＨの(ｋ＋１)個の位置を表わし、値(Ｈi)は位置Ｈiにおける値を表わす。
【００２８】
このことは、例えば、一旦、考慮に入れるべき最終の状態値をノードが取得すると、リストＬ及びＨ中への格納が常に保証され、時間を要する格納を実行する必要がない、という状況を特に簡単な方法で達成する。特に、上述した取得した状態値の逐次的な処理に関連して、このことは、取得した状態値のうち(ｋ＋１)番目に小さいものが常に位置Ｌ0に格納され、取得した状態値のうち(ｋ＋１)番目に大きいものが常に位置Ｈ0に格納される、ということも保証する。
【００２９】
さらなる利点は、請求項６及び７に記載の好適例に見ることができる。これらの請求項には、第１リストＬ及び／または第２リストＨ中に状態値Ｚを入れる方法が特に明瞭かつ簡単に記載されている。この目的で、最初に、状態値Ｚの大きさに対応するリストＬ及びＨ内の位置を、例えばそれまでで最大または最小の入れられた要素から始めたリスト中の要素どうしの比較によって決定する。そして状態値Ｚを、これより大きいすべてのリストＬの要素を位置１つ分ずつ下方に移動してリスト中に入れ、位置Ｌ0にあった値が位置Ｌ1にあった値に置き換えられたことの結果として、位置Ｌ0に存在していたリストＬの最大値はリストＬから脱落する。状態値ＺをリストＨ中に入れることについても同じことが当てはまる。
【００３０】
好適例では、次のステップを実行する：
−エラー許容度ｋの関数として、事前に定義可能な終端値Ｂiの集合Ｂ＝{Ｂ0, Ｂ1,...,Ｂk}を次のように定義する。
ｉ∈{０, １,...,(ｋ−１)}なるすべてのｉについて、Ｂ0＝０；Ｂi≦Ｂ(i+1)；
ｊ∈{０, １,...,ｋ}なるすべてのｊについて、２ｊ＜Ｂ(j)；
−Ｂk＞ｎである場合には、ｉ∈{０, １,...,(ｋ−１)}なる値ｉを、取得した状態値の数ｎの関数として、条件Ｂi≦ｎ＜Ｂ(i+1)が真となるように選択する；
−Ｂk≦ｎである場合には、ｉ＝ｋを選択する；
−位置Ｌ(k-1)及びＨ(k-1)に格納されている値から前記平均値を求める。
【００３１】
この好適例は、ノードにおいて取得した状態値の数ｎが(２ｋ＋２)未満であり所定値に達していない場合でも、クロックの同期を保証するのに適している。特に、この場合には、事前に定義されていないが、取得した状態値の数ｎの関数として、事前に定義可能なエラー許容度ｋの関数として、そして事前に定義可能な終端値Ｂ0, Ｂ1,...,Ｂkの関数として決まる実際のエラー許容度ｌが達成され、ここではｌ≦ｋが常に真である。従ってこの好適例は、ノードにおいて取得された状態値の数が元々想定された数より少ない際にも、このノードにおけるクロックの同期が保証されるという利点を有する。特に、この好適例では、ｎ＜(２ｋ＋２)である場合に、エラー許容度ｌ≦ｋでのエラー許容性の同期が可能である。
【００３２】
次の値を事前に定義することが有利である：
−エラー許容度ｋ＝２；
−終端値Ｂ1＝３；
−終端値Ｂ2＝８
【００３３】
これらの値を用いて、取得した状態値のあらゆる数について、通信システム、例えばFlexRayにおけるクロックのエラー許容性の同期を、特に効率的かつ高速に保証することができる。
【００３４】
この目的は、次の構成要素を有するノードによっても達成される：
−クロック；
−当該ノードのタイムベース及び／または他のノードのタイムベースに依存する状態値を取得する手段；
−(ｋ＋１)個の位置から成る第１リスト(Ｌ)及び(ｋ＋１)個の位置から成る第２リスト(Ｈ)；
−取得した状態値を第１リスト(Ｌ)中の対応する位置に入れる手段；
−取得した状態値を第２リスト(Ｈ)中の対応する位置に入れる手段；
−第１リスト(Ｌ)の一要素及び第２リスト(Ｈ)の一要素から平均値を求める手段；
−修正値を求める手段；
−クロックを修正する手段。
【００３５】
請求項１〜９のいずれかに記載の方法は、ノードにおいて実行することが好ましい。
【００３６】
上記目的はさらに、上述した種類の通信システムによって達成され、この通信システムの少なくとも１つのノードは次の構成要素を有する：
−クロック(１５)；
−状態値を取得する手段；
−(ｋ＋１)個の位置から成る第１リスト(Ｌ)及び(ｋ＋１)個の位置から成る第２リスト(Ｈ)；
−取得した状態値を第１リスト(Ｌ)中の対応する位置に入れる手段(１２０)；
−取得した状態値を第２リスト(Ｈ)中の対応する位置に入れる手段(１３０)；
−第１リスト(Ｌ)の一要素及び第２リスト(Ｈ)の一要素から平均値(Ｍ)を求める手段(１６０)；
−修正値(Ｋ)を求める手段；
−クロックを修正する手段(１５)。
【００３７】
請求項１〜９に記載の方法は、前記通信システム内の少なくとも１つのノードにおいて実行することが好ましい。
【００３８】
コンピュータプログラムの形の本発明の実現は特に重要である。この場合には、このコンピュータプログラムはコンピュータ、特にマイクロコンピュータ上で実行することができ、そして本発明の方法を実行するのに適している。従ってこの場合には、本発明をコンピュータプロスラムによって実現して、このコンピュータプログラムは、コンピュータプログラムが実行する方法と同様に本発明を表現する。このコンピュータプログラムは、メモリー素子に記憶することが好ましい。使用するメモリー素子は特に、ランダムアクセスメモリー（ＲＡＭ）、リードオンリーメモリー（ＲＯＭ）、またはフラッシュメモリーである。
【００３９】
本発明をハードウェアで実現することも重要であり、このハードウェアは本発明による方法を実行するのに適している。ハードウェアでの実現は、本発明による方法がより一層高速に実行されるという利点を有する。
【００４０】
以下、本発明の実施例を図面を参照しながらより詳細に説明するが、本発明はこれらの実施例に限定されない。
【発明を実施するための最良の形態】
【００４１】
図１に、通信媒体５経由で互いに接続された複数のノード１０から成る通信システム１を示す。通信媒体５は、例えばFlexRay仕様あるいはＴＴＰ（Time Triggered Protocol）に準拠した時間制御のバスシステム（ＴＴＡ−Time Triggered Architecture）として設計されている。通信媒体５を他のネットワーク・トポロジーに準拠して、例えばリングとして形成することも考えられる。
【００４２】
図１に示す各ノード１０はいわゆるホスト１１及びインタフェース１２を有する。ホスト１１は、例えば単一のマイクロチップ上に形成されたマイクロコンピュータとして構成することができる。ホスト１１を、ネットワーク経由で互いに通信する複数のコンピュータから成るコンピュータシステム全体とすることも同様に考えられる。
【００４３】
インタフェース１２は、ホスト１１と通信媒体５との間に位置する。インタフェース１２は、例えば、情報をメッセージ形式に変換することによってホスト１１から、あるいはホスト１１への情報の伝送を制御し、このメッセージ形式は通信媒体５によって事前に規定されたデータフレームに対応する。フレームは一般に、メッセージフォーマットによって事前に規定された規則に従って解釈される一組のビットである。FlexRayのメッセージフォーマットは、例えば、関係するメッセージを同期に用いるべきか否かを示す特別なＳＹＮＣビット、及び実際のメッセージ（有効なデータ）を含むデータバイト数を示すＬＥＮビットを表示する。
【００４４】
もちろん、ホスト１１及びインタフェース１２を単に同一チップ上の異なる機能ユニットとして設計することも可能である。
【００４５】
時間制御の通信システム５では、通信の帯域幅を１つ（以上）の大域的（グローバル）時系列（グローバル・スケジュールとして知られている）の形で固定的に事前規定することができる。こうしたスケジュールは、ノード１０が通信媒体５によってメッセージを送信可能な時間及びノード１０がメッセージを期待している時間についての情報を具えている。メッセージが例えばフレームで送信される場合には、スケジュールは特に、ノード１０がどのフレームをメッセージの送信に利用可能であるかについての情報を提供する。
【００４６】
通信媒体５上の通信全体がグローバル・スケジュールによって制御されているので、メッセージは受信者または送信者の情報を何ら含む必要はない。各ノード１０は、メッセージの送信者または受信者を、このメッセージが送信された時点に基づいて識別する。従って、フレーム内にアドレスフィールドは必要なく、これにより帯域幅が増加する。
【００４７】
図２ａにインタフェース１２を示し、インタフェース１２はクロック１５、マイクロプロセッサ２０、及びメモリー素子３０を有する。メモリー素子３０は、例えばランダムアクセスメモリー（ＲＡＭ）として設計することができ、アドレス指定可能なメモリー領域Ｌ0, Ｌ1,...,Ｌk及びＨ0, Ｈ1,...,Ｈkを有する。インタフェース１２は、例えばリードオンリーメモリー（ＲＯＭ）として構成された他のメモリー素子３１も有する。メモリー素子３１には、例えば本発明による方法を実行すべくプログラムされたコンピュータプログラムを記憶することができる。もちろん、メモリー素子３０及び３１を単一のメモリー素子として形成することも考えられる。
【００４８】
図２ｂに示すインタフェース１２も同様に、クロック１５、マイクロプロセッサ２０、及びメモリー素子３１を有する。しかし、この場合には、マイクロプロセッサ２０はレジスタＬ0, Ｌ1,...,Ｌk及びＨ0, Ｈ1,...,Ｈkを有する。図２ｂに示すインタフェース１２の具体例は、図２ａに示す具体例と比較して、レジスタＬ0, Ｌ1,...,Ｌk及びＨ0, Ｈ1,...,Ｈkにアクセスするのに要する時間が他のメモリー素子の場合よりも短いという利点を有する。その結果、レジスタＬ0, Ｌ1,...,Ｌk及びＨ0, Ｈ1,...,Ｈkを、これらに対応する図２ａに示すメモリー領域の代わりに用いると、データをより高速に位置Ｌ0, Ｌ1,...,Ｌk, Ｈ0, Ｈ1,...,Ｈkに書き込み、そしてこれらの位置から読み出すことができる。
【００４９】
図３に通信サイクル５１を示し、その始点を破線５２で示し、その終点を破線５３で示す。通信サイクルの始点では、例えば、いわゆるＳＹＮＣシンボル５５を送信し、ＳＹＮＣシンボル５５は通信に関係するすべてのノード１０が通信サイクル５１の始点を認識することを可能にする。しかし、ＳＹＮＣシンボル５５なしで通信サイクルを開始することも可能である。通信サイクル５１内では、一般に複数のフレーム７１、７２、７３、７４...を送信し、図には例としてこのうちの４フレームを示す。時間制御の伝送法では、フレーム７１、７２、７３、７４を規定可能ないわゆる時間スロット（タイムスロット）内で送信し、図ではこれらの時間スロットの始点をそれぞれ６１、６２、６３、６４で表わす。フレーム７１、７２、７３、７４どうしの間には、メッセージを伝送しない時間間隔、いわゆるフレーム間ギャップ８１、８２、８３、８４が存在する。フレーム間ギャップ８１、８２、８３、８４は、通信システム１内の複数のノード１０のクロック１５どうしが少し異なる場合にも、フレーム７１、７２、７３、７４をこれらのフレーム送信中のノードのうちの１つに対応させて一意的に識別することを可能にするために必要である。
【００５０】
通信媒体５経由で通信中のすべてのノード１０が、フレーム７１、７２、７３、７４のノード１０への割り当てに関してフレーム７１、７２、７３、７４を同等に評価するために、これらのノード１０のクロックが同期していることが特に重要である。この場合には、クロック１５をホスト１１内またはインタフェース１２内に配置することができる。クロック１５の同期の処理も原則的には、ホスト１１内またはインタフェース１２内で同様に行われる。
【００５１】
しかし、通信の帯域は通信システム１内でのクロック１５の同期の精度に依存する、というのは、すべてのノード１０によるフレーム７１、７２、７３、７４の一意的な識別を保証するためには、フレーム７１、７２、７３、７４が互いに直接連続せず、フレーム７１、７２、７３、７４どうしの間にフレーム間ギャップ８１、８２、８３、８４が存在するからである。フレーム間ギャップ８１、８２、８３、８４は、１番目のフレーム７１、７２、７３、７４の終点と、これに続く２番目のフレーム７１、７２、７３、７４の始点との間に経過する時間間隔を表わす。従って十分正確に同期したクロックが与えられれば、これにより、２つのノード１０が同じフレーム７１、７２、７３、７４を、スケジュールに対するこれらのノードの現在時刻（が異なること）に起因して異なるように解釈して、例えばグローバル（大域的）クロックに比べて遅いクロック１５を有するノード１０が２番目のフレーム７１、７２、７３、７４を１番目のフレームとして誤って解釈する、という状況を防止することができる。
【００５２】
ノード１０のクロック１５どうしが互いに正確に同期するほど、個々のフレーム７１、７２、７３、７４間のフレーム間ギャップ８１、８２、８３、８４を小さくすることができる。個々のフレーム７１、７２、７３、７４間のフレーム間ギャップ８１、８２、８３、８４が小さいほど通信の帯域幅が大きくなる。
【００５３】
一般に、同期は特化したハードウェアによって行うことができ、このハードウェアはインタフェース１２内に集積され、同様にインタフェース１２内に集積されたクロック１５の高速かつ正確な同期を達成することを可能にする。
【００５４】
図４に、本発明による方法の非常に簡略化したフローチャートを示す。この方法はステップ１００において、例えばノード１０において、このノード１０に割り当てられたクロック１５の同期を行うべき時点から始まる。この方法の開始時に、特定変数の初期化を行う。例として、取得した状態値の数ｎを０に設定する（ｎ＝０）。
【００５５】
ステップ１１０では、例えば、通信媒体５によって送信されたフレーム７１、７２、７３、７４をノード１０が同期メッセージとして解釈して、状態値Ｚをフレーム７１、７２、７３、７４の対応するビットから読み出すことによって状態値Ｚを取得し、前記対応するビットはメッセージフォーマットにおいて規定されている。状態値Ｚの取得に続いて、取得した状態値の数ｎを１だけ増加させる（ｎ＋＋）。
【００５６】
ステップ１２０では、取得した状態値Ｚが例えばレジスタＬ0及びＬkによって形成される第１リストＬ中に格納されている最大値より小さい場合に、状態値Ｚを第１リストＬ中に入れる。いずれの場合にも、何個の状態値が既にリストＬ中に格納されているかについてのチェックを行うことなしに、最初のｋ個の取得した状態値がリストＬ中に格納されることを保証するために、初期化ステップ１００では、レジスタＬ0〜Ｌkを、想定されるあらゆる状態値Ｚより大きい＋∞の値に初期化して、すべてのＺについてＺ＜＋∞が常に真であるようにする。
【００５７】
状態値ＺをリストＬ中に入れることに関する、擬似コードの表記法を用いた好適な方法を以下に示す。この場合には、レジスタＬ0,...,Ｌkに格納されている値をＬ[0],...,Ｌ[k]で表わす：
(l1) for (i=k; i≧0; i--) {
(l2) if (Z<L[i]) {
(l3) for (j=0; j<i; j++) {
(l4) L[j]=L[j+1];
(l5) }
(l6) L[i]=Z;
(l7) break i;
(l8) }
(l9) }
【００５８】
行(l1)では、カウンタｉを初期化して最初のループを規定する。ループを通過する毎に、ｉ＝ｋから始まる値ｉを値１だけ低減する（i--）。そしてｉの値に応じて、行(l2)〜(l7)の命令を実行する。行(l2)の質問を伴う最初のループによって、リストＬの全体の位置またはレジスタＬiのうち、状態値Ｚが当該位置またはレジスタＬiに格納されている値より小さいような位置またはレジスタＬiを探索する。こうした位置が見つからなければ、状態値ＺをリストＬ中に入れずに除外する。しかし、行(l2)においてこうした位置が認識された場合には、行(l3)〜(l5)によって規定される２番目のループを行(l3)において初期化して開始する。この２番目のループでは、ｊ＜ｉであれば、リスト中の位置Ｌjにおける各値を、次に上位の位置に格納されている値Ｌ(j+1)で置き換える。従って、行(l2)で見つけた、位置Ｌiより下位の位置にあるすべての値を位置１つ分ずつ下方に移動して、位置Ｌ0にある値は脱落させる。次に行(l6)では、状態値Ｚを上記位置またはレジスタＬiに格納して、状態値Ｚを入れる動作を終了する（break i）。
【００５９】
図４に示す本発明による方法のステップ１３０では、ステップ１２０と同様に、取得した状態値Ｚが、例えばレジスタＨ0〜Ｈkによって形成されるリストＨに格納されている最小値より大きい場合に、状態値ＺをリストＨ中に入れる。いずれの場合にも、何個の状態値が既にリストＨ中に格納されているかについてのチェックを行うことなしに、最初のｋ個の取得した状態値がリストＨ中に格納されることを保証するために、初期化ステップ１００では、レジスタＨ0〜Ｈkを、想定されるあらゆる状態値Ｚより小さい−∞の値に初期化して、すべてのＺについてＺ＞−∞が常に真であるようにする。
【００６０】
状態値ＺをリストＨ中に入れることも同様に、例として擬似コードで示す。この場合には、レジスタＨ0,...,Ｈkに格納されている値をＨ[0],...,Ｈ[k]で表わす：
(h1) for (i=k; i≧0; i--) {
(h2) if (Z<H[i]) {
(h3) for (j=0; j<i; j++) {
(h4) H[j]=H[j+1];
(h5) }
(h6) H[i]=Z;
(h7) break i;
(h8) }
(h9) }
【００６１】
行(h1)でも、カウンタｉを初期化して最初のループを規定する。そしてｉの値に応じて、行(h2)〜(h7)の命令を実行する。行(h2)の質問を伴う最初のループによって、リストＨの全体の位置またはレジスタＨiのうち、状態値Ｚが当該位置またはレジスタＨiに格納されている値より大きいような位置またはレジスタＨiを探索する。こうした位置Ｈiが見つからなければ、状態値ＺをリストＨ中に入れずに除外する。しかし、行(h2)においてこうした位置が認識された場合には、行(h3)〜(h5)によって規定される２番目のループを行(h3)において初期化して開始する。この２番目のループでは、ｊ＜ｉであれば、リスト中の位置Ｈjにおける各値を、次に上位の位置に格納されている値Ｈ(j+1)で置き換える。従って、行(h2)で見つけた、位置Ｈiより下位の位置にあるすべての値を位置１つ分ずつ下方に移動して、位置Ｈ0にある値は脱落させる。次に行(h6)では、状態値Ｚを上記位置またはレジスタＨiに格納して、状態値Ｚを入れる動作を終了する（break i）。
【００６２】
ステップ１４０では、例えばさらなるＳＹＮＣフレームが認識されているので、新たな状態値Ｚを取得すべきか否かについてのチェックを行う。新たな状態値を取得すべき場合には、本発明の方法をステップ１１０から継続する。そうでない場合には、ステップ１５０では、値ｊを、取得した状態値Ｚの数ｎの関数及び終端値Ｂiの関数として定める。値ｊは、取得した状態値の数ｎが(２ｋ＋２)より小さい場合でも、本発明による方法のさらなるステップによるエラー許容性の同期を可能にするために定める。
【００６３】
値ｊは次式が常に真であるように定める：
ｊ∈{０, １,...,(ｋ−１)}なるすべてのｊについて、Ｂj≦ｎ＜Ｂ(j+1)
【００６４】
終端値Ｂi（またはＢj）は、ステップ１００の初期化段階で初期化することが好都合である。この場合には、終端値Ｂiは次の条件を満足するように初期化する：
Ｂ0＝０；
ｉ∈{０, １,...,(ｋ−１)}なるすべてのｉについて、Ｂi≦Ｂ(i+1)；
ｊ∈{０, １,...,ｋ}なるすべてのｊについて、２ｊ＜Ｂj；
【００６５】
事前に規定されたエラー許容度ｋ＝２に対して、ｉ∈{０, １, ２}なるｉについての終端値Ｂiを次のように定める：
Ｂ0＝０；
Ｂ1＝３；
Ｂ2＝８；
【００６６】
終端値Ｂjは上記のように選択し、例えば状態値を５つだけ取得している場合には、結果的にｎ＝５であり、従って値ｊについてはｊ＝１である。ステップ１６０では、各場合において、値ｊの関数として、リストＬからの１つの値及びリストＨからの１つの値より、同期のために使用可能な平均値Ｍを、例えば次式（いわゆる算術平均）に従って決定する：
【数１】
【００６７】
取得した状態値の数ｎがｎ≧(２ｋ＋２)である場合に、値ｊはｊ＝ｋである。従って、この場合には、平均値Ｍは位置Ｌ0及びＨ0に格納されている値から求める。上述したように、ステップ１２０及び１３０では、取得した状態値のうち最小のものが位置Ｌkに位置し、取得した状態値のうち最大のものが位置Ｈkに位置するように、状態値ＺをリストＬ及びＨに入れる。さらに、ｎ≧(２ｋ＋２)については、(ｋ＋１)番目に小さい値を位置Ｌ0に格納し、(ｋ＋１)番目に大きい値を位置Ｈ0に格納する。従って、ｎ≧(２ｋ＋２)であれば、平均値Ｍは、取得した状態値の(ｋ＋１)番目に小さい値及び(ｋ＋１)番目に大きい値から求める。このことは特に、取得した状態値のｋ番目に大きい値及びｋ番目に小さい値は、平均値を決定する際に考慮に入れず、そしてこのことはエラー許容度ｋによることを意味する。
【００６８】
ｋ＝２に対する終端値Ｂiをここでも上記のように定め、取得した状態値の数がここでもｎ＝５である場合には、値ｊはここでもｊ＝１であり、従ってこの場合には、前記平均値は位置Ｌ(k-1)＝Ｌ(1)及びＨ(k-1)＝Ｈ(1)に格納されている値から求める。この例より、ｎ＜(２ｋ＋２)であっても、本発明の方法によりエラー許容性のクロックの同期が可能であることがわかる。この例では、この可変のエラー許容度ｌは例えばｌ＝１である。
【００６９】
ステップ１７０では、修正値Ｋを平均値Ｍの関数として決定し、ステップ１８０では、ノード１０に割り当てられたクロック１５を修正値Ｋの関数として同期させ、そしてステップ１９０で本発明の方法を終了する。修正値Ｋは、例えば、ノード１０に割り当てられたクロック１５の現在の状態値を考慮に入れた相対値とすることができ、これにより、クロック１５を同期させるためには、修正値Ｋを現在の状態値に加算するだけでよい。
【００７０】
もちろん、図４に示す方法にさらなるステップを加えるか、あるいはいくつかのステップを省略することも考えられる。特に、個々のステップを組み合わせること、及び／または複数のステップの実行あるいは個々のステップの動作を異なる順序にすることも考えられる。もちろん、本発明による方法の実現を実施例から離れて、特に擬似コードで示す具体例から離れて行うことも可能である。
【００７１】
図４に示す本発明の方法の実施例は、例えばコンピュータプログラムの形で実現することができる。しかし、特に、本発明による方法のより高速な実現を達成するために、この方法をハードウェア、例えばいわゆるＡＳＩＣ（Application-Specific Integrated Circuit：特定用途向け集積回路）によって実現することもできる。既存のハードウェア、例えばインタフェース１２内の特定の機能ユニットを、本発明の方法を実行可能なように拡張することも考えられる。
【００７２】
さらに、すべての参照符号及び指標、例えばリストＬ及びＨの位置の番号付けは固定のものではなく、論理的な称号と考えるべきものである。従って、リストＬ及びＨ、及びこれらのリスト中の位置は異なる表わし方をすることも考えられる。番号付けの変更、特に格納順序の反転も考えられる。格納順序を反転する場合には、例えば、(ｋ＋１)番目に小さい値を位置Ｌ(k)に格納して(ｋ＋１)番目に大きい値を位置Ｈ(k+1)に格納する。本発明による方法のステップ、特にステップ１２０、１３０及び１６０は、これに応じて改変しなければならない。
【００７３】
図５に、取得した状態値ＺをリストＬ及びＨ中に入れる手順の例を示す。この場合には、リスト中に入れる動作は図４に示す本発明による方法のステップ１２０及び１３０の説明と同様に行う。図にはリストＨ及びＬを示し、これらのリストは位置Ｈ0, Ｈ1, Ｈ2及びＬ0, Ｌ1, Ｌ2を有する。Ｚは、リストＬ及びＨ中に入れるべき取得した状態値を表わす。最初（ｎ＝１）に取得した状態値Ｚ＝５を入れる前に、位置Ｌ0, Ｌ1, Ｌ2を＋∞に初期化し、位置Ｈ0, Ｈ1, Ｈ2を−∞に初期化する。この場合には、値＋∞及び−∞は、−∞が取得すべきあらゆる状態値Ｚより小さく、＋∞が取得すべきあらゆる状態値Ｚより大きいように選択し、言わばすべてのＺについて−∞＜Ｚ＜＋∞が常に真であるようにする。
【００７４】
最初は、擬似コードを用いて上述し図４に示す実施例と同様に、取得した状態値Ｚを格納すべき位置Ｌi及びＨiを探索する。こうした位置Ｌi及びＨiは、これらのリストを最上位から最下位まで探索すれば、それぞれＬ[i]＞ＺまたはＨ[i]＜Ｚであれば認識され、この探索は本実施例では言わばＬ2→Ｌ1→Ｌ0及びＨ2→Ｈ1→Ｈ0の順である。最初の状態値Ｚ＝５に対して、位置Ｌ2及びＨ2が決まる。従って位置Ｌ0及びＨ0にある値はそれぞれ位置Ｌ1及びＨ1にある値に置き換えられ、そして位置Ｌ1及びＨ1にある値はそれぞれ位置Ｌ2及びＨ2にある値に置き換えられる。従って、各場合に、リストＬ及びＨ中の値は位置１つ分ずつ下方に移動され、位置Ｌ0及びＨ0にある最下位の値は脱落する。従って状態値Ｚ＝５は位置Ｌ2及びＨ2に格納される。
【００７５】
次に、上述した方法に従い、２番目の（ｎ＝２）状態値Ｚ＝７を取得して位置Ｈ2及びＬ2に格納する。ここでも、これらの位置にある値は、位置Ｌ0及びＨ0にある値が脱落するまで位置１つ分ずつ下方に移動する。
【００７６】
次に、上述した方法に従い、３番目の（ｎ＝３）状態値Ｚ＝−３を取得して位置Ｈ2及びＬ2に格納する。ここでも、これらの位置にある値を位置１つ分ずつ下方に移動する。位置Ｌ0及びＨ0にある値は脱落する。
【００７７】
図５に示す実施例では、さらなる状態値Ｚは検出されないものと仮定する。次に値ｊを図４のステップ１５０及び１６０、及び例としてこの図に示す終端値Ｂiに対する値と同様に決定する。結果的に、位置Ｌ(２−１)及びＨ(２−１)にある値を用いて平均値Ｍを求め、従ってＭ＝５となる。
【００７８】
図６に、取得した状態値ＺをリストＬ及びＨ中に入れる手順のさらなる例を示す。この場合にも、リスト中に入れる動作は、図４に示す本発明による方法のステップ１２０及び１３０の説明と同様に行う。
【００７９】
しかしこの例では、(２ｋ＋２)より多数の状態値Ｚを取得してリストＬ及びＨ中に入れる。最初に、図５において既に説明したように、最初２つの状態値Ｚ＝５及びＺ＝７をリストＬ及びＨ中に入れる。次に、ｍ＞２に対するさらなる(２ｋ＋ｍ−１)個の状態値Ｚを入れるが、このことは図６に示しておらず、(ｎ＝２)から(ｎ＝２ｋ＋ｍ)への遷移を（縦に連続した）点々のみによって示す。
【００８０】
そして、(２ｋ＋ｍ)番目に取得した状態値Ｚ＝７を図４のステップ１２０及び１３０と同様に扱い、リストＨ及びＬ中に適宜入れる。この場合には、リストＬ中に格納されているすべての値がＺ＝７より小さい。従って状態値７はリストＬ中には格納されない。しかし、リストＨ中に格納されている値をチェックすれば、位置Ｈ0にある値が位置Ｈ1にある値に置き換えられた後に、値Ｚ＝７が位置Ｈ1に格納されることがわかる。従って位置Ｈ0にある値はリストから脱落する。
【００８１】
同様に、最終のさらなる状態値Ｚ＝−３を取得して位置Ｌ0に格納する。ここでは(２ｋ＋２)より多数の状態値を取得しているので、位置Ｌ0及びＨ0にある値を用いて平均値Ｍを求める。結果的に、クロック１５のエラー許容性の同期が、エラー許容度ｋ＝２で可能になる。
【００８２】
図４及び図５に示す例、及び図４に示す実施例でも、入れる動作を、取得した状態値Ｚに対して、まずこの状態値が位置Ｌ0及びＨ0に格納されている値より小さいか大きいかについてのチェックを行って、このことが成り立つ場合のみに、この状態値を格納する適切な位置を見つけるプロセスを開始する。このようにして、特に、取得した状態値の数ｎが(２ｋ＋２)よりはるかに多いことがしばしばある場合に、本発明による方法を実行するために要する時間を低減することができる。
【図面の簡単な説明】
【００８３】
【図１】通信媒体経由で通信する複数のノードから成る通信システムを示す図である。
【図２ａ】ノードの選択した構成要素を図式的に示す図である。
【図２ｂ】図２ａに示すノードの構成要素の他の構成を図式的に示す図である。
【図３】複数のフレームを有する通信サイクルを図式的に示す図である。
【図４】本発明による方法を示すフローチャートである。
【図５】本発明による方法の実行中にリストＬ及びＨに格納されている状態値Ｚを図式的に示す図であり、ここにｎ＜(２ｋ＋２)である。
【図６】図５と同様の図であり、ここにｎ≧(２ｋ＋２)である。
【特許請求の範囲】
【請求項１】
通信媒体経由で通信するノードに割り当てられたクロックを時間的に同期させる方法において、
少なくとも同期させるべき前記ノードについて、前記ノードのタイムベースに依存する状態値を取得するステップと；
取得したすべての前記状態値について、当該状態値が、(ｋ＋１)個の位置から成る第１リストの(ｋ＋１)番目に小さい要素未満であるか、あるいは(ｋ＋１)番目に小さい要素以下であり、ここにｋは事前に定義可能な許容度である場合に、当該状態値を前記第１リスト中の対応する位置に入れるステップと；
取得したすべての前記状態値について、当該状態値が、(ｋ＋１)個の位置から成る第２リストの(ｋ＋１)番目に大きい要素より大きいか、あるいは(ｋ＋１)番目に大きい要素以上である場合に、当該状態値を前記第２リスト中の対応する位置に入れるステップと；
ｎ≧(２ｋ＋２)であり、ここにｎは取得した状態値の数である場合に、前記第１リストの(ｋ＋１)番目に小さい要素及び前記第２リストの(ｋ＋１)番目に大きい要素から平均値を求めるステップと；
修正値を前記平均値の関数として決定するステップと；
同期させるべき前記クロックの現在の状態値が前記修正値を計算に入れるように、このクロックを修正するステップと
を具えていることを特徴とするクロックの時間同期方法。
【請求項２】
取得した前記状態値を前記第１リスト中及び／または前記第２リスト中に入れるステップを逐次的に実行することを特徴とする請求項１に記載の方法。
【請求項３】
前記第１リストが、対応する複数のレジスタによって形成され、前記第２リストが、対応する複数のレジスタによって形成されることを特徴とする請求項１または２に記載の方法。
【請求項４】
前記第１リストを、想定される最大の前記状態値より大きい値で初期化するステップと；
前記第２リストを、想定される最小の前記状態値より小さい値で初期化するステップとを具えていることを特徴とする請求項１〜３のいずれかに記載の方法。
【請求項５】
取得した前記状態値を前記第１リストに入れる期間中に、値(Ｌ0)≧値(Ｌ1)≧...≧値(Ｌk)が常に真であるように、格納されている値の大きさの順の並べ替えを継続し、ここにＬ0, Ｌ1,...,Ｌkは前記第１リストの(ｋ＋１)個の各位置を表わし、値(Ｌi)は位置(Ｌi)にある値を表わすステップと；
取得した前記状態値を前記第２リストに入れる期間中に、値(Ｈ0)≦値(Ｈ1)≦...≦値(Ｈk)が常に真であるように、格納されている値の大きさの順の並べ替えを継続し、ここにＨ0, Ｈ1,...,Ｈkは前記第２リストの(ｋ＋１)個の各位置を表わし、値(Ｈi)は位置(Ｈi)にある値を表わすステップと
を具えていることを特徴とする請求項１〜４のいずれかに記載の方法。
【請求項６】
前記状態値(Ｚ)を前記第１リスト中の位置(Ｌi)に格納するに当たり：
前記第１リスト中の位置(Ｌ0, Ｌ1,...,Ｌk)から、次式：
値(Ｌ0)≧値(Ｌ1)≧...≧値(Ｌi)≧Ｚ≧値(Ｌ(i+1))≧...≧値(Ｌk)
を満足する位置(Ｌi)を探索するステップと；
上式を満足する位置(Ｌi)が発見されない場合に、前記状態値(Ｚ)を除外するステップと；
上式を満足する位置(Ｌi)を発見した場合に、すべての位置(Ｌj)、ここに０≦ｊ＜ｉについて、位置(Ｌj)に格納されている値(Ｌj)を位置(Ｌ(j+1))に格納されている値(Ｌ(j+1))に置き換えて、状態値(Ｚ)を前記第１リストの位置(Ｌi)に格納するステップと
を有する関数として格納することを特徴とする請求項１〜５のいずれかに記載の方法。
【請求項７】
前記状態値(Ｚ)を前記第２リスト中の位置(Ｈi)に格納するに当たり：
前記第２リスト中の位置(Ｈ0, Ｈ1,...,Ｈk)から、次式：
値(Ｈ0)≦値(Ｈ1)≦...≦値(Ｈi)≦Ｚ≦値(Ｈ(i+1))≦...≦値(Ｈk)
を満足する位置(Ｈi)を探索するステップと；
上式を満足する位置(Ｈi)が発見されない場合に、前記状態値(Ｚ)を除外するステップと；
上式を満足する位置(Ｈi)を発見した場合に、すべての位置(Ｈj)、ここに０≦ｊ＜ｉについて、位置(Ｈj)に格納されている値(Ｈj)を位置(Ｈ(j+1))に格納されている値(Ｈ(j+1))に置き換えて、状態値(Ｚ)を前記第２リストの位置(Ｈi)に格納するステップと
を有する関数として格納することを特徴とする請求項１〜６のいずれかに記載の方法。
【請求項８】
エラー許容度(ｋ)の関数として、事前に定義可能な終端値の集合{Ｂ0, Ｂ1,...,Ｂ(k-1)}を、次の条件：
ｉ∈{０, １,...,(ｋ−１)}なるすべてのｉについて、Ｂ0＝０；Ｂi≦Ｂ(i+1)；
ｊ∈{０, １,...,ｋ}なるすべてのｊについて、２ｊ＜Ｂ(j)；
を満足するように事前に定義するステップと；
Ｂk＞ｎである場合には、ｉ∈{０, １,...,(ｋ−１)}なる値ｉを、取得した前記状態値の数ｎの関数として、条件Ｂi≦ｎ＜Ｂ(i+1)を満足するように選択するステップと；
Ｂk≦ｎである場合には、ｉ＝ｋを選択するステップと；
それぞれ位置Ｌ(k-i)及び位置Ｈ(k-i)に格納されている値(Ｌ(k-j))及び値(Ｈ(k-j))から前記平均値を求めるステップと
を実行することを特徴とする請求項１〜７のいずれかに記載の方法。
【請求項９】
次の値：
エラー許容度ｋ＝２；
終端値Ｂ1＝３；
終端値Ｂ2＝８；
を事前に定義することを特徴とする請求項１〜８のいずれかに記載の方法。
【請求項１０】
通信媒体によって他のノードと通信するノードにおいて、
クロックと；
前記ノードのタイムベース及び／または他のノードのタイムベースに依存する状態値を取得する手段と；
(ｋ＋１)個の位置から成る第１リスト及び(ｋ＋１)個の位置から成る第２リストと；
取得した前記状態値を前記第１リスト中の対応する位置に入れる手段と；
取得した前記状態値を前記第２リスト中の対応する位置に入れる手段と；
前記第１リストの一要素及び前記第２リストの一要素から平均値を求める手段と；
修正値を求める手段と；
前記クロックを修正する手段と
を具えていることを特徴とするノード。
【請求項１１】
請求項１〜９のいずれかに記載の方法を実行することを特徴とする請求項１０に記載のノード。
【請求項１２】
通信媒体経由で通信する複数のノードを有する通信システムにおいて、
少なくとも１つの前記ノードが、
クロックと；
状態値を取得する手段と；
(ｋ＋１)個の位置から成る第１リスト及び(ｋ＋１)個の位置から成る第２リストと；
取得した前記状態値を前記第１リスト中の対応する位置に入れる手段と；
取得した前記状態値を前記第２リスト中の対応する位置に入れる手段と；
前記第１リストの一要素及び前記第２リストの一要素から平均値を求める手段と；
修正値を求める手段と；
前記クロックを修正する手段と
を具えていることを特徴とする通信システム。
【請求項１３】
少なくとも１つの前記ノードにおいて、請求項１〜９のいずれかに記載の方法を実行することを特徴とする請求項１２に記載の通信システム。
【請求項１４】
コンピュータ、特にマイクロコンピュータ上で実行可能なコンピュータプログラムにおいて、該コンピュータプログラムが、コンピュータ上で実行される際に請求項１〜９のいずれかに記載の方法を実行すべくプログラムされていることを特徴とするコンピュータプログラム。
【請求項１５】
前記コンピュータプログラムがメモリー素子、特にランダムアクセスメモリー（ＲＡＭ）、リードオンリーメモリー（ＲＯＭ）、またはフラッシュメモリーに記憶されることを特徴とする請求項１４に記載のコンピュータプログラム。
【請求項１】
通信媒体経由で通信するノードに割り当てられたクロックを時間的に同期させる方法において、
少なくとも同期させるべき前記ノードについて、前記ノードのタイムベースに依存する状態値を取得するステップと；
取得したすべての前記状態値について、当該状態値が、(ｋ＋１)個の位置から成る第１リストの(ｋ＋１)番目に小さい要素未満であるか、あるいは(ｋ＋１)番目に小さい要素以下であり、ここにｋは事前に定義可能な許容度である場合に、当該状態値を前記第１リスト中の対応する位置に入れるステップと；
取得したすべての前記状態値について、当該状態値が、(ｋ＋１)個の位置から成る第２リストの(ｋ＋１)番目に大きい要素より大きいか、あるいは(ｋ＋１)番目に大きい要素以上である場合に、当該状態値を前記第２リスト中の対応する位置に入れるステップと；
ｎ≧(２ｋ＋２)であり、ここにｎは取得した状態値の数である場合に、前記第１リストの(ｋ＋１)番目に小さい要素及び前記第２リストの(ｋ＋１)番目に大きい要素から平均値を求めるステップと；
修正値を前記平均値の関数として決定するステップと；
同期させるべき前記クロックの現在の状態値が前記修正値を計算に入れるように、このクロックを修正するステップと
を具えていることを特徴とするクロックの時間同期方法。
【請求項２】
取得した前記状態値を前記第１リスト中及び／または前記第２リスト中に入れるステップを逐次的に実行することを特徴とする請求項１に記載の方法。
【請求項３】
前記第１リストが、対応する複数のレジスタによって形成され、前記第２リストが、対応する複数のレジスタによって形成されることを特徴とする請求項１または２に記載の方法。
【請求項４】
前記第１リストを、想定される最大の前記状態値より大きい値で初期化するステップと；
前記第２リストを、想定される最小の前記状態値より小さい値で初期化するステップとを具えていることを特徴とする請求項１〜３のいずれかに記載の方法。
【請求項５】
取得した前記状態値を前記第１リストに入れる期間中に、値(Ｌ0)≧値(Ｌ1)≧...≧値(Ｌk)が常に真であるように、格納されている値の大きさの順の並べ替えを継続し、ここにＬ0, Ｌ1,...,Ｌkは前記第１リストの(ｋ＋１)個の各位置を表わし、値(Ｌi)は位置(Ｌi)にある値を表わすステップと；
取得した前記状態値を前記第２リストに入れる期間中に、値(Ｈ0)≦値(Ｈ1)≦...≦値(Ｈk)が常に真であるように、格納されている値の大きさの順の並べ替えを継続し、ここにＨ0, Ｈ1,...,Ｈkは前記第２リストの(ｋ＋１)個の各位置を表わし、値(Ｈi)は位置(Ｈi)にある値を表わすステップと
を具えていることを特徴とする請求項１〜４のいずれかに記載の方法。
【請求項６】
前記状態値(Ｚ)を前記第１リスト中の位置(Ｌi)に格納するに当たり：
前記第１リスト中の位置(Ｌ0, Ｌ1,...,Ｌk)から、次式：
値(Ｌ0)≧値(Ｌ1)≧...≧値(Ｌi)≧Ｚ≧値(Ｌ(i+1))≧...≧値(Ｌk)
を満足する位置(Ｌi)を探索するステップと；
上式を満足する位置(Ｌi)が発見されない場合に、前記状態値(Ｚ)を除外するステップと；
上式を満足する位置(Ｌi)を発見した場合に、すべての位置(Ｌj)、ここに０≦ｊ＜ｉについて、位置(Ｌj)に格納されている値(Ｌj)を位置(Ｌ(j+1))に格納されている値(Ｌ(j+1))に置き換えて、状態値(Ｚ)を前記第１リストの位置(Ｌi)に格納するステップと
を有する関数として格納することを特徴とする請求項１〜５のいずれかに記載の方法。
【請求項７】
前記状態値(Ｚ)を前記第２リスト中の位置(Ｈi)に格納するに当たり：
前記第２リスト中の位置(Ｈ0, Ｈ1,...,Ｈk)から、次式：
値(Ｈ0)≦値(Ｈ1)≦...≦値(Ｈi)≦Ｚ≦値(Ｈ(i+1))≦...≦値(Ｈk)
を満足する位置(Ｈi)を探索するステップと；
上式を満足する位置(Ｈi)が発見されない場合に、前記状態値(Ｚ)を除外するステップと；
上式を満足する位置(Ｈi)を発見した場合に、すべての位置(Ｈj)、ここに０≦ｊ＜ｉについて、位置(Ｈj)に格納されている値(Ｈj)を位置(Ｈ(j+1))に格納されている値(Ｈ(j+1))に置き換えて、状態値(Ｚ)を前記第２リストの位置(Ｈi)に格納するステップと
を有する関数として格納することを特徴とする請求項１〜６のいずれかに記載の方法。
【請求項８】
エラー許容度(ｋ)の関数として、事前に定義可能な終端値の集合{Ｂ0, Ｂ1,...,Ｂ(k-1)}を、次の条件：
ｉ∈{０, １,...,(ｋ−１)}なるすべてのｉについて、Ｂ0＝０；Ｂi≦Ｂ(i+1)；
ｊ∈{０, １,...,ｋ}なるすべてのｊについて、２ｊ＜Ｂ(j)；
を満足するように事前に定義するステップと；
Ｂk＞ｎである場合には、ｉ∈{０, １,...,(ｋ−１)}なる値ｉを、取得した前記状態値の数ｎの関数として、条件Ｂi≦ｎ＜Ｂ(i+1)を満足するように選択するステップと；
Ｂk≦ｎである場合には、ｉ＝ｋを選択するステップと；
それぞれ位置Ｌ(k-i)及び位置Ｈ(k-i)に格納されている値(Ｌ(k-j))及び値(Ｈ(k-j))から前記平均値を求めるステップと
を実行することを特徴とする請求項１〜７のいずれかに記載の方法。
【請求項９】
次の値：
エラー許容度ｋ＝２；
終端値Ｂ1＝３；
終端値Ｂ2＝８；
を事前に定義することを特徴とする請求項１〜８のいずれかに記載の方法。
【請求項１０】
通信媒体によって他のノードと通信するノードにおいて、
クロックと；
前記ノードのタイムベース及び／または他のノードのタイムベースに依存する状態値を取得する手段と；
(ｋ＋１)個の位置から成る第１リスト及び(ｋ＋１)個の位置から成る第２リストと；
取得した前記状態値を前記第１リスト中の対応する位置に入れる手段と；
取得した前記状態値を前記第２リスト中の対応する位置に入れる手段と；
前記第１リストの一要素及び前記第２リストの一要素から平均値を求める手段と；
修正値を求める手段と；
前記クロックを修正する手段と
を具えていることを特徴とするノード。
【請求項１１】
請求項１〜９のいずれかに記載の方法を実行することを特徴とする請求項１０に記載のノード。
【請求項１２】
通信媒体経由で通信する複数のノードを有する通信システムにおいて、
少なくとも１つの前記ノードが、
クロックと；
状態値を取得する手段と；
(ｋ＋１)個の位置から成る第１リスト及び(ｋ＋１)個の位置から成る第２リストと；
取得した前記状態値を前記第１リスト中の対応する位置に入れる手段と；
取得した前記状態値を前記第２リスト中の対応する位置に入れる手段と；
前記第１リストの一要素及び前記第２リストの一要素から平均値を求める手段と；
修正値を求める手段と；
前記クロックを修正する手段と
を具えていることを特徴とする通信システム。
【請求項１３】
少なくとも１つの前記ノードにおいて、請求項１〜９のいずれかに記載の方法を実行することを特徴とする請求項１２に記載の通信システム。
【請求項１４】
コンピュータ、特にマイクロコンピュータ上で実行可能なコンピュータプログラムにおいて、該コンピュータプログラムが、コンピュータ上で実行される際に請求項１〜９のいずれかに記載の方法を実行すべくプログラムされていることを特徴とするコンピュータプログラム。
【請求項１５】
前記コンピュータプログラムがメモリー素子、特にランダムアクセスメモリー（ＲＡＭ）、リードオンリーメモリー（ＲＯＭ）、またはフラッシュメモリーに記憶されることを特徴とする請求項１４に記載のコンピュータプログラム。
【図１】
【図３】
【図４】
【図５】
【図６】
【図３】
【図４】
【図５】
【図６】
【公表番号】特表２００６−５２５７２４（Ｐ２００６−５２５７２４Ａ）
【公表日】平成１８年１１月９日（２００６．１１．９）
【国際特許分類】
【出願番号】特願２００６−５０６８９６（Ｐ２００６−５０６８９６）
【出願日】平成１６年４月２６日（２００４．４．２６）
【国際出願番号】ＰＣＴ／ＩＢ２００４／０５０５１１
【国際公開番号】ＷＯ２００４／１００４１１
【国際公開日】平成１６年１１月１８日（２００４．１１．１８）
【出願人】（５９００００２４８）コーニンクレッカ フィリップス エレクトロニクス エヌ ヴィ (12,071)
【氏名又は名称原語表記】Ｋｏｎｉｎｋｌｉｊｋｅ Ｐｈｉｌｉｐｓ Ｅｌｅｃｔｒｏｎｉｃｓ Ｎ．Ｖ．
【住所又は居所原語表記】Ｇｒｏｅｎｅｗｏｕｄｓｅｗｅｇ １，５６２１ ＢＡ Ｅｉｎｄｈｏｖｅｎ， Ｔｈｅ Ｎｅｔｈｅｒｌａｎｄｓ
【Ｆターム（参考）】
【公表日】平成１８年１１月９日（２００６．１１．９）
【国際特許分類】
【出願日】平成１６年４月２６日（２００４．４．２６）
【国際出願番号】ＰＣＴ／ＩＢ２００４／０５０５１１
【国際公開番号】ＷＯ２００４／１００４１１
【国際公開日】平成１６年１１月１８日（２００４．１１．１８）
【出願人】（５９００００２４８）コーニンクレッカ フィリップス エレクトロニクス エヌ ヴィ (12,071)
【氏名又は名称原語表記】Ｋｏｎｉｎｋｌｉｊｋｅ Ｐｈｉｌｉｐｓ Ｅｌｅｃｔｒｏｎｉｃｓ Ｎ．Ｖ．
【住所又は居所原語表記】Ｇｒｏｅｎｅｗｏｕｄｓｅｗｅｇ １，５６２１ ＢＡ Ｅｉｎｄｈｏｖｅｎ， Ｔｈｅ Ｎｅｔｈｅｒｌａｎｄｓ
【Ｆターム（参考）】
[ Back to top ]