(57)【要約】      （修正有）【課題】アイ・ダイアグラム中の最適なサンプリング・ポイントを見つける。【解決手段】チャンネルを介したトランスミッタからレシーバへのマルチ・シンボル通信のシステム及び方法において、複数シンボルのシーケンスを表す信号波形を送信する。各シンボルのユニット・インターバルの持続時と、各シンボルは、特有の信号レベルと関連している。水平時間軸及び垂直信号レベル軸を有するアイ・ダイアグラムとして波形をグラフィカルに表す処理と、任意のニット・インターバル中の波形がどの信号を表すかを決める各アイ中の位相と識別しきい値によるサンプリング・ポイント６６Ａ〜６６Ｃを利用する。アイ・ダイアグラム中のアイを特定する処理と、各アイ内に適合する凸多角形領域を見つける処理と、各アイの凸多角形領域に適合する最大矩形を見つける処理と、各アイ中に、そのアイの矩形の中心において、サンプリング・ポイントを配置する処理とがある。【選択図】図１６
2017103754.tif 000002
【特許請求の範囲】
【請求項１】
１つのユニット・インターバルにおいて送信可能で、夫々がそれ特有の信号レベルと関連する少なくとも２つの異なるシンボルを含み、１ユニット・インターバル幅のグラフ中に置かれる信号の有り得る全てのユニット・インターバル・サイズの波形を、夫々時間軸を表す水平軸と信号レベルを表す垂直軸とを有する多角形を形成する１つ以上のアイでグラフィカルに表すと共に時間軸を表す水平軸と信号レベルを表す垂直軸とを有するアイ・ダイアグラムを定める複数の上記シンボルのシーケンスを含む信号を送信するトランスミッタと、
複数の上記シンボルの上記シーケンスのためのレシーバと、
上記トランスミッタを上記レシーバに結合するチャンネルと、
時間的にはユニット・インターバルの中央半分に境界を示し、信号レベルについては上記アイの直ぐ下及び直ぐ上の信号レベルで特定される境界を示す、上記アイ・ダイアグラム中の上記アイ夫々の領域を定める境界ボックスと、
任意のユニット・インターバルにおける波形がどの信号を表すかを定めるための、上記ユニット・インターバル中の上記アイ夫々内のサンプリング・ポイントと、
上記アイ夫々内の最大凸形サブセットを求める手段と、
上記アイ夫々の上記凸形サブセットに適合する最大直交矩形を求める手段と
を具え、
上記アイ夫々に関する上記サンプリング・ポイントが、上記矩形の中心と等しい信号レベルに配置されるマルチ・シンボル通信システム。
【請求項２】
チャンネルを介したトランスミッタからレシーバへのマルチ・シンボル通信の方法であって、複数のシンボルのシーケンスを表す波形として信号を送信する処理を含み、上記シンボルのユニット・インターバルの持続時間の夫々及び上記シンボル夫々がその特有の信号レベルと関連しており、上記方法が、
１つ以上のアイを形成するようアレンジされた水平時間軸及び垂直信号レベル軸を有するアイ・ダイアグラムとして上記波形をグラフィカルに表す処理と、
任意のユニット・インターバルにおける上記波形がどの信号を表すか求めるために、夫々位相及び識別しきい値を有するサンプリング・ポイントを使用する処理と、
上記アイ・ダイアグラム中のアイを特定する処理と、
上記アイ夫々内に適合する凸多角形領域を見つける処理と、
上記アイ夫々の上記凸多角形領域に適合する最大矩形を見つける処理と、
上記アイ夫々において、上記アイの上記矩形の中心に上記サンプリング・ポイントを配置する処理と
を具えるマルチ・シンボル通信の方法。
【請求項３】
凸多角形領域を見つける処理が、上記アイ内に適合する多角形領域を求める処理と、１つ以上の凹形を除去するために１つ以上の切断ラインに沿って上記多角形領域を切り取る処理とを有する請求項２によるマルチ・シンボル通信の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、アイ・ダイアグラム中の最適なサンプリング・ポイントを見つける機能を有するマルチ・シンボル通信のシステム及び方法に関する。
【背景技術】
【０００２】
通信システムは、図１に示すように、トランスミッタ２０と、トランスミッタをレシーバ２４に接続するチャンネル２２と、レシーバ自身とから構成される。トランスミッタは、複数シンボルのシーケンスから構成される信号を伝送するが、各シンボルは、ユニット・インターバルと呼ばれる所定の同じ時間的長さの間に伝送される。歴史的には、０及び１で示される２つのシンボルだけが存在してきた。もっと新しい通信規格では、もっと多数のシンボルの使用を提案しており、例えば、現時点での新しい提案はＰＭＡ４であり、これは、４つのシンボル（０，１，２及び３）を定義し、これらのいずれか１つが１つのユニット・インターバルで伝送できる。シンボルの個数に関係なく、各シンボルは、その特有の信号レベルに関係しており、これは、それ特有の電気的電圧又はそれ特有の光強度である。
【０００３】
アイ・ダイアグラムは、信号のユニット・インターバルの大きさで、有り得る全ての波形について、それらの全てを、ちょうど１ユニット・インターバルの幅のグラフに重ねることによって、グラフィカルに表す標準的な方法である。ユニット・インターバルにおける任意の点での各波形の値は、次の全てによって決定される。
（１）その特定の波形について、ユニット・インターバル中にトランスミッタによって送信されるのがシンボル
（２）チャンネルのばらつき（dispersion）及びその他の特性によって劣化
（３）チャンネルの特性によって定まるＮ個の先行するユニット・インターバルのＮ個のいくらかに関する複数シンボルによって影響される（これは、シンボル間干渉と呼ばれる）
（４）種々のジッタ源（ガウシャン、周期性（periodic））によって影響される
（５）種々の信号ノイズ（ガウシャン、周期性（periodic））によって影響される
（６）クロストーク（直ぐ近くの他の信号キャリアからの放射を原因とする電磁気的干渉）によって影響される
（７）他の効果（例えば、デューティ・サイクル歪）によって影響される
【０００４】
アイ・ダイアグラムの水平軸は、時間軸である。垂直軸は、信号レベルであり、電気的なシステムについてはボルト単位で、光学的システムについてはワット単位で測定される。ＰＭＡ４システムについての見本のアイ・ダイアグラム２６が、図２に示されている。これは、ＰＭＡ４の４つの信号レベル２８Ａ〜２８Ｄを分離する３つのアイがある。白色十字３０は、この方法によって定められるサンプリング・ポイントである。
【０００５】
用語「アイ・ダイアグラム」は、その図形（ダイアグラム）の中心のクリアな領域の形状と、人の目（アイ）としばしば類似することとから、その名称が取られたものである。この領域は、通常（ノイズや位相ジッタが存在しない状態において）、波形が通過しないために、クリアとなっている。アイ・ダイアグラム（そして、特にアイ）の重要なことは、そのアイ自身のほとんどどこにでもサンプリング・ポイントを配置できることである。
【０００６】
サンプリング・ポイントは、任意のユニット・インターバル中の波形がどの信号を表しているか（例えば、２シンボル・システムでは、任意に与えられたユニット・インターバル中の波形が０又は１を表しているかどうか）をレシーバが決定するに利用するユニット・インターバル中のポイントである。正しい信号を決定するため、各アイ中に１つのサンプリング・ポイントが必要である。例えば、４シンボル・システムにおける波形は、任意のユニット・インターバルにおいて、０、１、２又は３を表す可能性があり、そのため、３つのアイの夫々中に１つで、３つのサンプリング・ポイントが使用される。本願で説明する方法は、任意の個数のシンボルを有する任意のシステムにおける任意のアイに適用可能である。
【０００７】
サンプリング・ポイントは、２つの座標で定められる。
（１）水平座標は、時間であり、サンプリング・ポイントの位相と呼ばれる。これは、レシーバが、受けた波形の信号レベルを確認する場合において、ユニット・インターバル毎の開始からの時間である。
（２）垂直座標は、識別しきい値（decision threshold）であり、典型的には、ボルト又はワットで測定される。例として０及び１のシンボルを用いると、レシーバは、サンプリング時点で識別しきい値より上の波形を１として特定（identify）し、その時点で識別しきい値より下の波形を０として特定する。
【０００８】
０、１、２及び３を明確に認識するため、サンプリング・ポイントの周りに垂直ギャップ（gap：隔たり）を設けると良い。また、時間に伴う現実のレシーバの少量のドリフト（実際には、時間及び信号レベルの両方にドリフトする）のため、サンプリング・ポイントの周りに水平ギャップも設けると良い。これは、アイ・ダイアグラムが形成され、アイが識別され、そして、サンプリング・ポイントがアイの内側に配置されるためである。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特表２０１５−５１２１７３号公報
【非特許文献】
【００１０】
【非特許文献１】「多角形」の記事、特に「凸多角形」の用語説明、Wikipedia、［online］、［２０１６年９月２０日検索］、インターネット＜https://ja.wikipedia.org/wiki/多角形＞
【非特許文献２】「Convex Set」の記事、Wikipedia、［online］、［２０１６年９月２１日検索］、インターネット＜https://en.wikipedia.org/wiki/Convex_set＞
【発明の概要】
【発明が解決しようとする課題】
【００１１】
サンプリング・ポイントはドリフトすることがある（レシーバは、完璧な装置ではない）ため、サンプリング・ポイントをアイのエッジ近くに配置しないことが望ましい。公称（nominal）のサンプリング・ポイントの周辺のある領域は、波形がないようにすべきである。事実、これは、マスク試験の目的の１つである。マスクの形状を知るのではなく、代わりに、我々は、サンプリング・ポイントを矩形で囲み、後ほど、マスクをその中に適合（フィット）させる。問題は、その矩形の大きさとアスペクト比だけである。アスペクト比は、レシーバの実際的な知識と数値から求められる。アスペクト比は、水平及び垂直方向のある量のドリフトを許容するように選択されても良い。１つの実施形態では、アスペクト比は、矩形が水平及び垂直方向のドリフトの同じ部分を捕捉するように、選択されても良い。例えば、電気的なレシーバについては、ある定数（例えば、ピコ秒当たりＸミリ・ボルト）を利用しても良いし、光学的にレシーバについては、別のもの（例えば、ピコ秒当たりＹマイクロ・ワット）を用いても良い。
【００１２】
しかし、ある所与のアスペクト比について、矩形の大きさは、可能な限り大きく作るべきである。本発明は、所与のアスペクト比に関して、矩形を最大化する方法を提供する。
【００１３】
アイ・ダイアグラムには、複数の凹形状があっても良い。これについては、少なくとも２つの理由があるが、本発明とは関係はない。関係あることは、サンプリング・ポイントを選択する際に、凹形状は、アイの有用な領域を制限するので、避けなければならないということである。
【課題を解決するための手段】
【００１４】
アイ・ダイアグラムを分析する伝統的な手段は、１次元の複数ステップのシーケンスから構成される。例えば、第１ステップは、垂直のアイ開口を、その最も高さのある（tallest）ポイントで測定することであろう。続いて、第２ステップは、垂直開口の中間点を取り、そのレベレでの水平アイ開口を測定することであろう。こうした１次元のステップは、アイを全体として２次元のものとして分析することはない。本願で説明する方法の概要は、画像分析の２次元手法をこの問題に応用することによって、アイ・ダイアグラム及び（よって、そのアイ）を２次元のオブジェクトとして扱うということである。本発明の種々の概念は、次のように記述しても良い。
【００１５】
本発明の概念１は、通信システムであって、
１つのユニット・インターバルにおいて送信可能で、夫々がそれ特有の信号レベルと関連する少なくとも２つの異なるシンボルを含み、１ユニット・インターバル幅のグラフ中に置かれる信号の有り得る全てのユニット・インターバル・サイズの波形を、夫々時間軸を表す水平軸と信号レベルを表す垂直軸とを有する多角形を形成する１つ以上のアイでグラフィカルに表すと共に時間軸を表す水平軸と信号レベルを表す垂直軸とを有するアイ・ダイアグラムを定める複数の上記シンボルのシーケンスを含む信号を送信するトランスミッタと、
複数の上記シンボルの上記シーケンスのためのレシーバと、
上記トランスミッタを上記レシーバに結合するチャンネルと、
時間的にはユニット・インターバルの中央半分に境界を示し、信号レベルについては上記アイの直ぐ下及び直ぐ上の信号レベルで特定される境界を示す、上記アイ・ダイアグラム中の上記アイ夫々の領域を定める境界ボックスと、
任意のユニット・インターバルにおける波形がどの信号を表すかを定めるための、上記ユニット・インターバル中の上記アイ夫々内のサンプリング・ポイントと、
上記アイ夫々内の最大凸形サブセットを求める手段と、
上記アイ夫々の上記凸形サブセットに適合する最大直交矩形を求める手段と
を具え、
上記アイ夫々に関する上記サンプリング・ポイントは、上記矩形の中心と等しい信号レベルに配置される。
【００１６】
本発明の概念２は、上記概念１の通信システムであって、このとき、上記サンプリング・ポイントの夫々は、上記矩形の中心に配置される。
【００１７】
本発明の概念３は、上記概念１の通信システムであって、このとき、上記サンプリング・ポイントの夫々は、他のサンプリング・ポイントと位相が揃えられる。
【００１８】
本発明の概念４は、チャンネルを介したトランスミッタからレシーバへのマルチ・シンボル通信の方法であって、複数のシンボルのシーケンスを表す波形として信号を送信する処理を含み、上記シンボルのユニット・インターバルの持続時間の夫々及び上記シンボル夫々がその特有の信号レベルと関連しており、上記方法が、
１つ以上のアイを形成するようアレンジされた水平時間軸及び垂直信号レベル軸を有するアイ・ダイアグラムとして上記波形をグラフィカルに表す処理と、
任意のユニット・インターバルにおける上記波形がどの信号を表すか求めるために、夫々位相及び識別しきい値を有するサンプリング・ポイントを使用する処理と、
上記アイ・ダイアグラム中のアイを特定する処理と、
上記アイ夫々内に適合する凸多角形領域を見つける処理と、
上記アイ夫々の上記凸多角形領域に適合する最大矩形を見つける処理と、
上記アイ夫々において、上記アイの上記矩形の中心に上記サンプリング・ポイントを配置する処理と
を具えている。
【００１９】
本発明の概念５は、上記概念４によるマルチ・シンボル通信の方法であって、上記アイにおける上記サンプリング・ポイントを、上記アイの全てに共通する時間インターバルへと強制する処理を具えている。
【００２０】
本発明の概念６は、上記概念４によるマルチ・シンボル通信の方法であって、このとき、凸多角形領域を見つける処理は、上記アイ内に適合する多角形領域を求める処理と、１つ以上の凹形を除去するために１つ以上の切断ラインに沿って上記多角形領域を切り取る（トリミングする）処理とを含んでいる。
【００２１】
本発明の概念７は、上記概念６によるマルチ・シンボル通信の方法であって、このとき、上記切断ラインは、上記多角形の外周上に位置する両端を有するように配置される。
【００２２】
本発明の概念８は、上記概念６によるマルチ・シンボル通信の方法であって、このとき、凹形が残らなくなるまで、上記概念６のステップを繰り返す処理を含んでいる。
【図面の簡単な説明】
【００２３】
【図１】図１は、本発明の実施形態が実装される通信システムのブロック図である。
【図２】図２は、ＰＭＡ４、即ち、４シンボル通信規格に関するアイ・ダイアグラムの見本である。
【図３】図３は、図２のようなＰＭＡ４アイ・ダイアグラムであるが、この中の画素は正方形である。
【図４】図４は、図３のようなＰＭＡ４ダイアグラムであり、これにおいて、オリジナルのアイは輪郭が示され、各アイ内の最大凸領域には陰影がつけられている。
【図５】図５は、１つの凹形を有する多角形である。
【図６】図６は、凹形に広がる切断ラインを有する図５を示す。
【図６Ａ】図６Ａは、凸多角形を生じる有り得る切断ラインを示す。
【図６Ｂ】図６Ｂは、図６Ａの多角形から導かれた凸多角形を示す。
【図６Ｃ】図６Ｃは、凸多角形を生じるいくつかの有り得る切断ラインを示す。
【図７】図７は、複数の入り込んだポイントを有する多角形を示す。
【図８】図８は、複数の有り得る切断ラインを有する図７の多角形を示す。
【図９】図９は、複数の切断ラインを有する図５及び６の多角形を示す。
【図１０】図１０は、図３の中央のアイ・ダイアグラムのような現実の多角形である。
【図１１】図１１は、２つの凹形を有する多角形を示す。
【図１１Ａ】図１１Ａは、２つの凹形と見本の切断ラインを有する多角形を示す。
【図１１Ｂ】図１１Ｂは、２つの凹形と、ドットのある見本の切断ラインを有する多角形を示す。
【図１２Ａ】図１２Ａは、図７及び８にあるような複数の入り込んだポイントを有する多角形を示す。
【図１２Ｂ】図１２Ｂは、図７及び８にあるような複数の入り込んだポイントを有するが、限られた個数の切断ラインの多角形を示す。
【図１３Ａ】図１３Ａは、図１０の多角形を示す。
【図１３Ｂ】図１３Ｂは、外側輪郭内に陰影付凸形サブセットを有する図１０の多角形を示す。
【図１４】図１４は、図３のようなＰＭＡ４アイ・ダイアグラムであり、最大矩形を各凸領域に詰め込んでいる。
【図１５Ａ】図１５Ａは、多角形内に適合する最大矩形を得るための一連のダイアグラムの１つである。
【図１５Ｂ】図１５Ｂは、多角形内に適合する最大矩形を得るための一連のダイアグラムの１つである。
【図１５Ｃ】図１５Ｃは、多角形内に適合する最大矩形を得るための一連のダイアグラムの１つである。
【図１５Ｄ】図１５Ｄは、多角形内に適合する最大矩形を得るための一連のダイアグラムの１つである。
【図１６】図１６は、図１４のコピーであり、これにおいて、各ダイアグラムは、最大矩形と、サンプリング・ポイント「＋」を収容している。
【図１７Ａ】図１７Ａは、サンプリング・ポイントを共通時間インターバルに強制する前の図２のアイ・ダイアグラムを示す。
【図１７Ｂ】図１７Ｂは、サンプリング・ポイントを共通時間インターバルに強制した後の図２のアイ・ダイアグラムを示す。
【発明を実施するための形態】
【００２４】
ステップ１−画素カテゴリを減らす
アイ・ダイアグラム自身は、ＰＤＦ（probability distribution function：確率分布関数）である。アイ・ダイアグラムの自動分析における第１ステップは、画素の複数のカテゴリを大きな数から減らして、２つの画素カテゴリにすることである。事前に定義した確率、例えば、１０−６を選択し、アイ・ダイアグラム中の１０−６よりも小さい値の全ポイントを白に色付けし、残りの全ポイントを黒に色付けする。これは、図３で、ＰＭＡ４アイ・ダイアグラムの画像において見ることができる。これは、先のダイアグラム（図形）と同じアイ・ダイアグラムであるが、ここでは、画素は正方形である。
【００２５】
ステップ２−アイを見つける
第２ステップは、ダイアグラム中のアイ２６Ａ、２６Ｂ、２６Ｂの特定（identify：識別）である。これは、いくつかの領域が、もしそれらのポイントの夫々がしきい値より低い確率を有するなら実際にはアイではないにもかかわらず、擬似アイとして現れることがあるので、問題が多くなり得るものである。これら疑似アイは、システムを分析する上で関心のないものであるが、アイを特定する自動処理を複雑にする。アイは、（１）アイ・ダイアグラム中の有り得る領域の境界を示し、（２）その領域内の最大オブジェクトを選択することによって、特定される。各アイに関するその領域は、時間的には、ユニット・インターバルの中央の半分ＵＩ／２で境界が示される。信号レベルにおいては、アイの直ぐ下及び直ぐ上の複数の特定信号レベル、つまり、アイを特定するのに使われる２つの信号レベルによって境界が示される。図３のダイアグラムでは、アイは、境界ボックスによって囲まれ、それらの重心に十字（これらは、まだ決定ではないので、サンプリング・ポイントではない）でマークが付けられている。
【００２６】
ステップ３−各アイ内の最大凸領域を見つける
各アイ２６Ａ、２６Ｂ、２６Ｃについて、アイ内の凸領域３２Ａ、３２Ｂ、３２Ｃを見つける。アイ中の出っ張りは、サンプリング・ポイントを決める際には関心がなく、分析を難しくするので、凸形状が利用される。最適なサンプリング・ポイントを選択する上で、最大の自由度を許すために、アイ内の最大凸領域を見つけるのが望ましい
【００２７】
計算幾何学の文献の網羅的ではないサーチ（調査）では、多角形内の最大凸領域を算出するアルゴリズムは見つからなかった（アイは、画素で構成されるグリッド上にあり、そのため、その境界は、多数のエッジを有する多角形である）。こうした欠落の１つの理由は、一般的な数学的ケースの場合では、一意の解法がないためかもしれないが、アイ・ダイアグラム中のアイという実際的な場合には、こうした一意でないことは、予期されていないだけなく、もしこれが生じたとしても関係はない。
【００２８】
実証可能な形で最大凸領域を見つけるアルゴリズムは、多数の可能なものについての複雑で演算処理的に負荷の大きいサーチを必要とするだろう。代わりに、すぐれた推定（少なくとも）を提供する高速なアルゴリズムが開発されてきた。
【００２９】
このアルゴリズムの結果は、以下のダイアグラムで示されている。オリジナルのアイの夫々は、黒で輪郭が描かれ、各アイの内側の最大凸領域は、灰色に陰影がつけられている。
【００３０】
アルゴリズムの背景
多角形の最大（即ち、最大領域）凸形サブセット（部分集合）は、結果として、第２の、もっと小さな多角形を生成する（この解法は唯一ではない可能性がある一方で、この可能性については、関心がないし、ここでは無視する）。
【００３１】
図５は、指し示された複数のエッジで形成される１つの凹形がある多角形を示す。この１つの凹形３６は、その両側に１つで、２つの出っ張り３８を形成する。数学的には、ある形状が、もしその形状内の任意の２つのポイントについて、これらを接続する直線が、完全にその形状内にあるなら、凸形である（非特許文献２参照）。
【００３２】
アイについては、図５に示す多角形が凸形でないことは明らかであるが、これは、多角形内の直線で接続した２ポイントが、全体が多角形内にはないことを見出すことによって証明される。２つのポイント（夫々は、異なる出っ張り中にあるものが選択された）を接続している図６のライン４０は、全体が多角形内にはなく、凸形でないことを証明している。
【００３３】
多角形の任意の凸形サブセット（必ずしも最大サブセットではない）を見つける処理は、凹形で形成される出っ張りを切り取る処理から構成される。例えば、先の多角形の凸形サブセットは、１つ又は両方の出っ張りの部分を除去する１つの切断工程によって得られる。次の図は、１つの有り得る切断ラインを図６Ａに、得られる凸多角形を図６Ｂに示す。
【００３４】
図６Ａ及び６Ｃに示すように、多数の切断ラインが有り得る。夫々が、異なる凸多角形を生じる。
【００３５】
凹形が、複数の入り込んでいるポイントで輪郭が示される場合、状況はもっと複雑である。
【００３６】
図７の多角形を検討する。その切断ライン４４は、図８に示すように、３つの入り込んでいる頂点４６のうちのいずれかを通過できる。
【００３７】
上述のように、無限の数の可能な切断ラインがある。しかし、実際上は、図８に示すように、我々は、画素で構成されたグリッドを検討しており、多角形の全頂点は、このグリッドに制限される。この場合、有限の数の可能な切断ラインしかないが、可能なものの数は、それでも大きい。
【００３８】
最大凸領域を見つけることは、切断ライン４２が、多角形の外周の任意の画素において終わることを可能にしなければならないことを意味する。以下のダイアグラムは、全ての凹形について、可能なものが多数あるという考えを説明している。単一の凹形（図９に示すように）については、網羅的なサーチをする必要はない。しかし、複数の入り込んだ凹形があると、網羅的なサーチをしなければならず、本願が示すような組み合わせ論（combinatorics）の効果は、現実的である。
【００３９】
この組み合わせの状況は、多数の頂点を有する多角形に対して働きかける場合には、より悪化さえする。これは、多角形が、切れ目のない形態で特定される場合、即ち、任意の外周画素ｐ１で始まり、その次の外周画素ｐ２が、ｐ１に隣接する８個の画素の１つである場合である。そうした多角形の実際の、そして、典型的な例２６Ｂが、図１０に示されている。これは、３４０個の頂点を有している。複数の凹形がある場合、通常、１つの凹形当たり１つで、複数の切断ラインがある（例外は、ある１つの凹形についての切断ラインが、別の凹形を形成する出っ張りの少なくとも１つを完全に切り取る場合である。よって、この第２の凹形は、無視して良い）。
【００４０】
２つの凹形４８、５０（３つの出っ張りを形成している）を有する多角形が、図１１に示されている。１つの有り得る切断ラインの対５４及び５６が、図１１Ａに示されている。
【００４１】
これは、切断工程が必ずしもオリジナルの多角形の外周上のポイントで終わるわけではないという別の複雑な特徴を示している。図１１Ｂの例では、切断ライン５４及び５６の両方は、外周上に１つの端点（end point）と、図１１Ｂに示すドット５８でマークを付けたポイントにおけるものとを有している。
【００４２】
最大凸形サブセットを見つけるには、１つの切断ラインが他の切断ラインの効果を変化させることがあるので、通常、複数の切断ラインを一緒に検討する必要がある。再度、これは、全ての入り込み（intrusions：侵入）に関する全ての切断ラインの全ての組み合わせを検討するという網羅的又は網羅的に近いサーチをしなければならないことを意味する。これは、演算処理的にあまりに負荷が大きいということになり得る。
【００４３】
開示されるアルゴリズム
本願で開示されるアルゴリズムは、いくつかの要因を認めることに基いている。
１.  最適に近い凸領域は、実際上は、最適な凸領域と同じ程度に良い。
２.  実際問題として、複数の切断ライン間の相互作用は、通常、２次効果として無視できる。これは、重要な単純化である。なぜなら、それは、１）アルゴリズムが、複数の凹形を、それらの全てをまとめ扱う代わりに、１度に１個扱うことを可能にし、２）全ての切断ラインの両端が外周上にあって、多角形の中央にはないことを暗示しているからである。
３．  最適ではなく、最適に近い凸領域のサーチでは、有り得る切断ラインの全てを検討する必要はない。事実、その数は、切れ目のない多角形のセグメントの延長である切断ラインのみを検討することによって、著しく減少する。
【００４４】
切れ目のない外周を有する画素から構成されるグリッドにおいて、外周の直線セグメントの全ては、水平、垂直又は４５度の角度のいずれかである。単純な凹形６０は、図１２Ａ及び１２Ｂのような外観かもしれない。
【００４５】
この方法は、図１２Ｂに示される５個の切断ライン６２Ａ〜６２Ｅのみを検討するが、これらの夫々は、多角形の１つのセグメントの延長である。
【００４６】
これら切断ラインの最も良いものは、最適な切断ラインから、方向の点で最大で２２.５度（４５度の半分）だけ異なるが、それは、０度（水平）、４５度及び９０度（垂直）の切断ラインの間のどこかになければならないためである。多角形の角度は、ランダムに生じると仮定する（合理的な仮定）と、平均的な誤差は、その半分、つまり、約１１度であろう。これらは、出っ張りの切断についての許容範囲であり、これらは、それら自身、オリジナルの多角形の小さな部分に過ぎない。
【００４７】
この方法のステップは、次の通りである。
１.  既知の任意の方法（これをどのように行うかは、本願では記述しない）を利用して、多角形の凹形６０を見つける
２.  凹形における多角形セグメントを延長することによって形成できる全ての切断ライン６２を見つける。
３.  各切断ラインについて、もし切断を行った場合に得られるであろう多角形の面積を計算する。
４.  切断後、最大面積の多角形を生成する切断ラインに沿って切断を行う。
５.  凹形が残らなくなるまで、切断で生成された多角形に関して、上記ステップを繰り返す。
【００４８】
典型的な結果が、図１３Ａ及び１３Ｂに示されている。オリジナルの切れ目のない多角形２６Ｂが黒で、凸形サブセット３２Ｂが灰色で示されている。
【００４９】
ステップ４−各凸領域内に上記アスペクト比を有する最大矩形を見つける
各凸領域（１つのアイ当たり１つ）について、凸領域３２Ｂ中に適合するアスペクト比の最大矩形６４Ｂを見つけなければならない。その結果は、図１４に示され、ここでは、黒の矩形６４Ａ、６４Ｂ、６４Ｃが、所定のアスペクト比を有し、各灰色凸領域内に適合する最大直交矩形（orthogonal rectangle）を表す。
【００５０】
用語
矩形のアスペクト比は、その高さに対するその幅の比率である。この場合、これは、各アイ中の上側（upper）及び下側（lower）信号レベルで定まるアイ・ダイアグラムの高さに対するアイ・ダイアグラムのユニット・インターバル、つまり、幅を指している。
【００５１】
矩形は、もしその辺が垂直及び水平であれば、つまり、斜めでなければ、直交である。
多角形は、もしその外周が画素の切れ目のない連続（contiguous sequence）によって特定されるのであれば、切れ目がない（contiguous）。
領域は、もしその形状内の任意の２つのポイントの、それらを接続した直線も完全にその領域内にあるのなら、凸形である。
【００５２】
アルゴリズム
所与のアスペクト比に関し、矩形の任意の２つの角がわかれば、その矩形が完全に決まる。図１５Ａに示すような多角形の外周上のポイントＰを検討する（この方法は、画素で構成された多角形グリットで動作するが、ピクセル化（pixelation：画素を認識できるようにすること）は、ダイアグラム中に示されない）。
【００５３】
図１５Ｂに示すようなＰに角がある任意の矩形については、その矩形の他の３つの角の夫々には、２つの制約があるであろう：（１）その角は多角形の内側になければならず、（２）矩形全体も、多角形の内側になければならない。
【００５４】
この方法の第１ステップは、凸領域上の任意ポイントＰを選択し、Ｐから水平、垂直及び対角線上に直線を与えることである。対角線の角度は、そのラインがＰと反対側の角を通過するように、所望のアスペクト比によって定まる。ポイントＰＨ、ＰＶ及びＰＤを見つけるが、このとき、水平、垂直及び対角線は、再度、多角形と交差する。多角形は、凸形なので、これら他の交差は、一意（unique）なものである（多角形それ自身が、水平、垂直の辺、又は、適切な角度の対角線を有している特殊な場合は無視する）。
【００５５】
１つの有り得る形態が、図１５Ｂに示されている。
【００５６】
ポイントＰと連動して、ＰＨ、ＰＶ及びＰＤの夫々は、図１５Ｃに示すように、所望のアスペクト比を有する異なる矩形を定義できる
【００５７】
しかし、多角形が凸形とわかっているので、これら矩形の中の最も小さいものが、ポイントＰに関して探している矩形である。それは、Ｐに１つの角が有り、適切なアスペクト比を有し、多角形の内側に適合する最大直交矩形である。先の図においては、それは、ＰＶで定まる矩形である。
【００５８】
これの証明は、次の通り。
下側左角がＰＶより下にあると、多角形の外側に置かれることになるであろうことから、確かに、もっと大きな矩形は可能ではない。これは、ＰＶで定まる矩形が、完全に多角形内にあることを相変わらず示している。図１５Ｄに示される残りの矩形の角ＱＨ及びＱＤを検討する。
【００５９】
凸性（convexity）によって、Ｐ及びＰＨは多角形内にあるので、ＱＨもそうである。
【００６０】
凸性（convexity）によって、Ｐ及びＰＤは多角形内にあるので、ＱＤもそうである。
【００６１】
凸性（convexity）によって、矩形の４つの角の全てが多角形内にあるので、矩形の４つの辺もそうである。
【００６２】
矩形の任意の内部ポイントは、矩形の辺上の複数ポイントを接続した何らかの直線上にあるので、凸性（convexity）の最終的な利用によって、内部ポイントも多角形中にある。
【００６３】
これは、多角形が凸形なので、矩形が完全に多角形内に収容されるかどうか確認する必要がないことを明確に示している。３つの矩形の最も小さいものを選択することによって、ポイントＰを基点とする適切な矩形を確実に得られる。
【００６４】
最後に、アルゴリズムのステップは、次の通りである。
ステップ１．各凸領域上でポイントＰを選び、Ｐから、水平、垂直及び対角線上に直線を与えて、ポイントＰＨ、ＰＶ及びＰＤを見つける。
ステップ２．ＰＨ、ＰＶ及びＰＤで定まる３つの矩形の中の最も小さいものを、ポイントＰについての矩形として選択する。
ステップ３．全ての外周ポイントについて、先のステップを繰り返し（これは、多角形に切れ目がないので、全て含める）、各ポイントに関する矩形を求める。最大のそうした矩形を選択する。
【００６５】
ステップ５−各アイについて、最適なサンプリング・ポイントを見つける
各凸領域について最大矩形が見つかったなら、図１６に示すように、アイに関する最適なサンプリング・ポイント６６Ａ、６６Ｂ、６６Ｃが、矩形の中心として選択される。
【００６６】
これら十字は、図２に示され、図１７Ａで再生成されたサンプリング・ポイントを定める。図１７Ａ中のサンプリング・ポイントは、必ずしも垂直に揃っていない、つまり、同位相ではないことに注意すべきである。
【００６７】
ステップ６（オプション）−これらサンプリング・ポイントを共通時間インターバルに強制する
各アイを独立して分析してきたが、オプションで、共通のサンプリング位相７０を強制しても良い。このオプションを利用する場合、先に見つけたサンプリング・ポイントは、必要に応じてそれらのしきい値を調整して、全てのアイに共通する時間インターバル（システムによっては、狭いレンジでも良い）へと強制される。例えば、以下による：
１）  全てのアイに共通する位相レンジを定める。もしそうしたレンジが存在しないなら、解法に制約はない。
２）  これら位相の平均を計算する。もしそれが共通レンジ内なら、この位相を全てのサンプリング・ポイントに利用する。そうでないなら、共通レンジの中間ポイントを利用する。
３）  各アイについて、共通位相における垂直中間ポイントを識別しきい値として選択する。
【００６８】
図１７Ｂの画像は、先の複数のサンプリング・ポイントが共通時間インターバルに強制された場合の見本の出力を示す。図１７Ｂに見られるように、白色サンプリング・ポイントは、水平軸上で、互いに、より近くなっている。
【００６９】
本発明の原理を、その好ましい実施形態において、説明し、図示してきたが、本発明は、こうした原理から離れることなく、構成及び細部を変更できることは明らかである。
【符号の説明】
【００７０】
２０  トランスミッタ
２２  チャンネル
２４  レシーバ
２６  アイ・ダイアグラム
２６Ａ  アイ
２６Ｂ  アイ
２６Ｃ  アイ
２８Ａ  ＰＭＡ４の４つの信号レベルの１つ
２８Ｂ  ＰＭＡ４の４つの信号レベルの１つ
２８Ｃ  ＰＭＡ４の４つの信号レベルの１つ
２８Ｄ  ＰＭＡ４の４つの信号レベルの１つ
３０  ホワイト・クロス（サンプリング・ポイント）
３２Ａ  凸 領域
３２Ｂ  凸 領域
３２Ｃ  凸 領域
３６  凹形
３８  出っ張り
４０  ライン
４２  切断ライン
４４  切断ライン
４６  入り込んだ頂点
４８  凹形
５０  凹形
５４  切断ライン
５６  切断ライン
５８  ドット
６０  凹形
６２Ａ  切断ライン
６２Ｂ  切断ライン
６２Ｃ  切断ライン
６２Ｄ  切断ライン
６２Ｅ  切断ライン
６４Ａ  矩形
６４Ｂ  矩形
６４Ｃ  矩形
６６Ａ  サンプリング・ポイント
６６Ｂ  サンプリング・ポイント
６６Ｃ  サンプリング・ポイント
７０  共通サンプリング位相
【図１】
2017103754.tif 000003
【図２】
2017103754.tif 000004
【図３】
2017103754.tif 000005
【図４】
2017103754.tif 000006
【図５】
2017103754.tif 000007
【図６】
2017103754.tif 000008
【図６Ａ】
2017103754.tif 000009
【図６Ｂ】
2017103754.tif 000010
【図６Ｃ】
2017103754.tif 000011
【図７】
2017103754.tif 000012
【図８】
2017103754.tif 000013
【図９】
2017103754.tif 000014
【図１０】
2017103754.tif 000015
【図１１】
2017103754.tif 000016
【図１１Ａ】
2017103754.tif 000017
【図１１Ｂ】
2017103754.tif 000018
【図１２Ａ】
2017103754.tif 000019
【図１２Ｂ】
2017103754.tif 000020
【図１３Ａ】
2017103754.tif 000021
【図１３Ｂ】
2017103754.tif 000022
【図１４】
2017103754.tif 000023
【図１５Ａ】
2017103754.tif 000024
【図１５Ｂ】
2017103754.tif 000025
【図１５Ｃ】
2017103754.tif 000026
【図１５Ｄ】
2017103754.tif 000027
【図１６】
2017103754.tif 000028
【図１７Ａ】
2017103754.tif 000029
【図１７Ｂ】
2017103754.tif 000030
【外国語明細書】
【発明の名称】system and method of multi-symbol communications
【技術分野】
【０００１】
This invention relates to system and method of multi-symbol communications having a feature of finding an optimum sampling point in an Eye Diagram.
【背景技術】
【０００２】
A communications system consists of a transmitter 20, a channel 22 connecting the transmitter to a receiver 24, and the receiver itself, as shown in FIG. 1.  The transmitter transmits a signal consisting of a sequence of symbols, each symbol being transmitted for the same predefined length of time called a unit interval. Historically there have been only two symbols-denoted 0 and 1. Newer communication standards propose using more symbols, e.g., a new proposal at this time is PAM4 which defines four symbols (0, 1, 2 and 3), any one of which can be transmitted in one-unit interval. Regardless of the number of symbols, each symbol is associated with its own signal level which is either its own electrical voltage or its own optical intensity.
【０００３】
An eye diagram is a standard means of graphically representing all possible unit-interval sized waveforms of a signal by overlaying all of them in a graph just one-unit interval wide. The value of each waveform at any point in the unit interval is determined by all the following:
（１）the symbol as sent by the transmitter in the unit interval for that particular waveform,
（２）degraded by the dispersion and other characteristics of the channel,
（３）influenced by the symbols of the N previous unit intervals for some N determined by the characteristics of the channel (this is called inter-symbol interference),
（４）influenced by various sources of jitter (Gaussian, periodic),
（５）influenced by various sources of signal noise (Gaussian, periodic),
（６）influenced by crosstalk (electromagnetic interference due to radiation from other nearby signal carriers), and
（７）influenced by other effects (e.g., duty cycle distortion)
【０００４】
The horizontal axis of an eye diagram is a time axis. The vertical axis is the signal level and is measured in volts for electrical systems and in watts for optical systems. A sample eye diagram 26 for a PAM4 system is shown in FIG. 2. Note that it has three eyes that separate the four signal levels 28A - 28D of PAM4.  The white crosses 30 are the sampling points as determined by this method.
【０００５】
The nomenclature “eye diagram” takes its name from the shape of the center, clear area of the diagram and its frequent resemblance to a human eye. This area is clear because normally (in the absence of noise or phase jitter) no waveforms pass through it. The importance of an eye diagram (and in particular of the eye) is that the sampling point can be placed almost anywhere in the eye itself.
【０００６】
A sampling point is the point in the unit interval used by the receiver to determine which signal the waveform in any unit interval represents (e.g., in a two symbol system, whether the waveform in any given unit interval represents 0 or 1.) To determine the correct signal, one sampling point is needed in each eye. For example, the waveform in a four-symbol system may represent a 0, 1, 2 or 3 in any given unit interval, so three sampling points are used, one in each of the three eyes. The method described herein is applicable to any eye in any system with any number of symbols.
【０００７】
A sampling point is defined by its two coordinates.
（１）The horizontal coordinate is time and is referred to as the phase of the sampling point. This is the time from the start of every unit interval when the receiver checks the signal level of the received waveform.
（２）The vertical coordinate is the decision threshold, and is typically measured in volts or watts. Using the 0 and 1 symbols as an example, a receiver identifies a waveform that is above the decision threshold at the time of the sampling phase as a 1 and identifies a waveform that is below the decision threshold at that time as a 0.
【０００８】
In order to unambiguously recognize 0, 1, 2 and 3, there should be vertical gaps around the sampling point. There should also be a horizontal gap around the sampling point, because over time sampling points in real receiver’s drift by a small amount (they actually drift in both time and signal level). It is for these reasons that eye diagrams are constructed, the eye identified and the sampling point placed within the eye.
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特表２０１５−５１２１７３号公報
【非特許文献】
【００１０】
【非特許文献１】「多角形」の記事、特に「凸多角形」の用語説明、Wikipedia、［online］、［２０１６年９月２０日検索］、インターネット＜https://ja.wikipedia.org/wiki/多角形＞
【非特許文献２】「Convex Set」の記事、Wikipedia、［online］、［２０１６年９月２１日検索］、インターネット＜https://en.wikipedia.org/wiki/Convex_set＞
【発明の概要】
【発明が解決しようとする課題】
【００１１】
Because a sampling point can drift (receivers are not perfect devices), it is desirable that the sampling point not be placed close to the edge of an eye. Some region around the nominal sampling point should be clear of waveforms. In fact, this is one of the purposes of mask testing. Not knowing the shape of a mask, we instead surround the sampling point with a rectangle into which a mask can later fit. The only questions are the size and aspect ratio of the rectangle. The aspect ratio will be determined from practical knowledge of receivers and a numeric value. The aspect ratio may be selected to allow a certain amount of drift in the horizontal and vertical directions. In one embodiment, the aspect ratio may be selected so that the rectangle captures the same fraction of drift in both the horizontal and vertical directions. For example, one constant may be used for electrical receivers (e.g., X millivolts per picosecond), while another may be used for optical receivers (e.g., Y microwatts per picosecond). 
【００１２】
For a given aspect ratio, however, the rectangle size should be made as large as possible. This invention provides a method to maximize the rectangle for a given aspect ratio.
【００１３】
An eye diagram can have concavities. There are at least two reasons for this but none are relevant to this invention. What is relevant, is that the concavities must be avoided when selecting a sampling point, because they limit the useful area of the eye.
【課題を解決するための手段】
【００１４】
Traditional means of analyzing eye diagrams consist of a sequence of one-dimensional steps. For example, a first step might be to measure the vertical eye opening at its tallest point. A second step might then be to take the midpoint of that vertical opening and measure the horizontal eye opening at that level. Such one-dimensional steps never analyze the eye as an entire two-dimensional entity. A quick summary of the method described herein is that it treats the eye diagram and (hence the eye) as a two-dimensional object, by applying two-dimensional techniques of image analysis to the problem.  Various concepts of the present invention may be described as below.
【００１５】
A concept 1 of the present invention is a communications system, comprising:
a transmitter for transmitting a signal includes a sequence of symbols;
a receiver for the sequence of symbols; and
a channel coupling the transmitter to the receiver;
the sequence of symbols including at least two different symbols which can be transmitted in one-unit interval and each symbol associated with its own signal level;
the sequence of symbols defining an eye diagram for graphically representing in one or more eyes all possible unit-interval sized waveforms of a signal overlain in a graph one-unit interval wide;
the eye diagram having a horizontal axis representing a time axis and a vertical axis representing the signal level;
each eye forming a polygon having a horizontal axis representing a time axis and a vertical axis representing the signal level;
a bounding box defining a region of each eye in the eye diagram bounded in time to a middle half of the unit interval and bounded in signal level by specific signal levels just below and just above the eye;
a sampling point in the unit interval within each eye to determine which signal the waveform in any unit interval represents; 
means for determining a maximal convex subset within each eye; and
means for determining a largest orthogonal rectangle that fits in the convex subset of each eye;
the sampling point for each eye being positioned at a signal level equal to the center of the rectangle.
【００１６】
A concept 2 of the present invention is a communications system according to the concept 1 in which each sampling point is positioned at the center of the rectangle.
【００１７】
A concept 3 of the present invention is a communications system according to the concept 1 in which each sampling point is aligned in phase with the other sampling points.
【００１８】
A concept 4 of the present invention is a method of multi-symbol communications from a transmitter to a receiver via a channel, including transmitting signals as a waveform representing a sequence of symbols, each symbol of unit-interval duration and each symbol associated with its own signal level, the method comprising:
graphically representing the waveform as an eye diagram having a horizontal time axis and a vertical signal level axis arranged to form one or more eyes;
using a sampling point in each eye to determine which signal the waveform in any unit interval represents, each sampling point having a phase and a decision threshold;
identifying the eyes in the eye diagram;
finding a convex polygonal region fitting within each eye;
finding a largest rectangle fitting the convex polygonal region of each eye; and
positioning the sampling point in each eye at a center of the rectangle of that eye.
【００１９】
A concept 5 of the present invention is a method of multi-symbol communications according to the concept 4 including coercing the sampling points in the eyes into a time interval that all the eyes have in common.
【００２０】
A concept 6 of the present invention is a method of multi-symbol communications according to the concept 4 in which finding a convex polygonal region includes determining a polygonal region that fits within the eye, and trimming the polygonal region along one or more cut lines to remove one or more concavities.
【００２１】
A concept 7 of the present invention is a method of multi-symbol communications according to the concept 6 in which the cut lines are positioned to have opposite ends that lie on a perimeter of the polygon.
【００２２】
A concept 8 of the present invention is a method of multi-symbol communications according to the concept 6 in which including repeating the steps of the concept 6 until there are no concavities left.
【図面の簡単な説明】
【００２３】
【図１】FIG. 1 is a block diagram of a communications system in which an embodiment of the present invention is implemented.
【図２】FIG. 2 is a sample eye diagram for a PAM4, or four-symbol communications standard.
【図３】FIG. 3 is a PAM4 eye diagram like FIG. 2 but in which the pixels are square.
【図４】FIG. 4 is a PAM4 diagram like FIG. 3 in which the original eye is outlined and the largest convex area inside each eye is shaded.
【図５】FIG. 5 is a polygon that has one concavity.
【図６】FIG. 6 shows FIG 5 with a cut line spanning the concavity.
【図６Ａ】FIG. 6A shows a possibly cut line that yields a convex polygon.
【図６Ｂ】FIG. 6B shows a convex polygon derived from the polygon of FIG. 6A.
【図６Ｃ】FIG. 6C shows several possibly cut lines that yield a convex polygon.
【図７】FIG. 7 shows a polygon with multiple intruding points.
【図８】FIG. 8 shows the FIG. 7 polygon with multiple possibly cut lines.
【図９】FIG. 9 shows the polygon of FIGS 5 and 6 with multiple cut lines.
【図１０】FIG. 10 is a real polygon like the middle eye diagram of FIG. 3
【図１１】FIG. 11 shows a polygon with two concavities.
【図１１Ａ】FIG. 11A shows a polygon with two concavities and example cut lines.
【図１１Ｂ】FIG. 11B shows a polygon with two concavities and example cut lines with a dot.
【図１２Ａ】FIG. 12A shows a polygon with multiple intruding points as in FIGS. 7 and 8.
【図１２Ｂ】FIG. 12B shows a polygon with multiple intruding points as in FIGS. 7 and 8 but a limited number of cut lines.
【図１３Ａ】FIG. 13A shows the polygon of FIG. 10.
【図１３Ｂ】FIG. 13B shows the polygon of FIG. 10 with a convex subset shaded within the outer outline.
【図１４】FIG. 14 is a PAM4 eye diagram like FIG. 3 in which the largest rectangles are filled into each convex area.
【図１５Ａ】FIG. 15A is one of a series of diagrams for deriving the largest rectangle that fits within a polygon.
【図１５Ｂ】FIG. 15B is one of a series of diagrams for deriving the largest rectangle that fits within a polygon.
【図１５Ｃ】FIG. 15C is one of a series of diagrams for deriving the largest rectangle that fits within a polygon.
【図１５Ｄ】FIG. 15D is one of a series of diagrams for deriving the largest rectangle that fits within a polygon.
【図１６】FIG. 16 is a copy of FIG. 14 in which each diagram contains a largest rectangle and a sampling point “＋”.
【図１７Ａ】FIG. 17A shows the eye diagram of FIG. 2 before coercing the sampling points into a common time interval.
【図１７Ｂ】FIG. 17B shows the eye diagram of FIG. 2 after coercing the sampling points into a common time interval.
【発明を実施するための形態】
【００２４】
Step 1 - Reduce the pixel categories 
The eye diagram itself is a PDF (probability distribution function). The first step in automatically analyzing an eye diagram is to reduce the categories of pixels from a large number (based on the probability at each pixel) down to two categories of pixels. Picking a predefined probability, e.g., 10-6, any point in the eye diagram whose value is less than 10-6 is colored white and all other points are colored black. This can be seen in the image of a PAM4 eye diagram in FIG. 3. This is the same eye diagram as in the previous diagram but here the pixels are square.
【００２５】
Step 2 - Find the eyes
The second step is to identify the eye(s) 26A, 26B, 26B in the diagram. This can be problematic, since some regions may appear as pseudo-eyes if each of their points have probability below the threshold, even though they are not actually eyes. These pseudo-eyes are of no interest in analyzing the system but complicate the automatic process of identifying the eyes. An eye is identified by (1) bounding its possible region in the eye diagram and (2) selecting the largest object in that region. The region for each eye is bounded in time to the middle half of the unit interval UI/2. It is bounded in signal (S) level by the specific signal levels just below and just above the eye, i.e., by the two signal levels that will be used to distinguish the eye.
In the diagram in FIG. 3 the eyes are surrounded by bounding boxes and marked with a cross at their centroid (which are not the, as yet undetermined, sampling points).
【００２６】
Step 3 - Find the largest convex region within each eye
For each eye 26A, 26B, 26C, a convex region 32A, 32B, 32C within the eye is found. A convex shape is used because any protrusions in the eye are of no interest when determining a sampling point, and make the analysis difficult. It is desirable to find the largest convex region within the eye so as to permit the greatest latitude in selecting an optimum sampling point.
【００２７】
A non-exhaustive search of the literature of computational geometry found no algorithm for computing a largest convex region inside a polygon. (The eye is on a pixelated grid and so its border is a polygon with a large number of edges.) One reason for such a lack may be that in the general mathematical case there is not a unique solution, although for the practical case of eyes in eye diagrams such non-uniqueness is not only never expected but irrelevant even if it occurs.
【００２８】
An algorithm to find the provably largest convex region would require a complex and computationally exhaustive search of a large number of possibilities. Instead a fast algorithm that provides an excellent approximation (at least) has been developed.
【００２９】
The result of this algorithm is shown in the diagram below. Each original eye is outlined in black and the largest convex area inside each eye is shaded grey.
【００３０】
Algorithm Background
Finding the maximum (i.e., largest area) convex subset of a polygon produces a second, smaller polygon as a result. (While it is possible that the solution is not unique, this possibility is of no interest and is ignored here.)
【００３１】
FIG. 5 shows a polygon that has one concavity formed by the indicated edges. This one concavity 36 creates two protrusions 38, one on either side of it.  Mathematically a shape is convex if, given any two points within the shape, the straight line connecting them is entirely within the shape (see non-patent document 2).
【００３２】
While it is clear to the eye that the polygon in FIG. 5 is not convex, it is proved by finding two points within the polygon whose connecting straight line does not lie entirely within the polygon. The line 40 in FIG. 6 that connects the two points (each chosen to be in a different protrusion), does not lie entirely within the polygon, proving that it not convex.
【００３３】
Finding any convex subset of a polygon (not necessarily a maximum subset) consists of cutting off the protrusions created by the concavities. For example, a convex subset of the polygon above can be obtained by one cut operation that eliminates parts of one or both protrusions. The next figure shows one possible cut line in FIG. 6A and the resulting convex polygon in FIG. 6B.
【００３４】
Many cut lines are possible, as shown in FIG. 6A and 6C.  Each yields a different convex polygon.
【００３５】
When a concavity is defined by multiple intruding points, the situation is more complex. 
【００３６】
Consider the polygon in FIG. 7.  Its cut lines 44 can pass through any one of the three intruding vertices 46, as shown in FIG. 8.
【００３７】
As described above there are an infinite number of possible cut lines. However, in practice as shown in FIG. 8 we work on a pixelated grid and all polygon vertices are restricted to this grid. In this case, there are only a finite number of possible cut lines, yet the number of possibilities can still be large.
【００３８】
Finding the largest convex region means we must allow the cut line 42 to end at any pixel on the perimeter of the polygon. The following diagram illustrates the idea that there are a large number of possibilities for every concavity. For a single concavity (as shown in FIG. 9) one need not do an exhaustive search. But, with multiple interacting concavities an exhaustive search must be done, so the effect of combinatorics as shown here is real.
【００３９】
The combinatorial situation is even worse when working with polygons that have a large number of vertices. This is the case when the polygons are specified in a contiguous manner, i.e., starting at any perimeter pixel p1 the next perimeter pixel p2 is one of the eight pixels adjacent to p1. An actual and typical example of such a polygon 26B is shown the FIG. 10. It has 340 vertices.   When there are multiple concavities there are usually multiple cut lines, one per concavity. (The exception is when a cut line for one concavity completely cuts away at least one of the protrusions forming another concavity. This second concavity can then be ignored.)
【００４０】
A polygon with two concavities 48, 50 (forming three protrusions) is shown in FIG. 11.  Each of these two concavities will have a cut line. One possible pair of cut lines 54 and 56 is shown in FIG. 11A.
【００４１】
This illustrates another complicating feature, which is that a cut operation does not always end on a point on the perimeter of the original polygon. In the example of FIG. 11B, both cut lines 54 and 56 have one end point on the perimeter and one at the point marked with a dot 58 shown in FIG. 11B.
【００４２】
Finding the maximum convex subset generally requires that the cut lines be considered together, because one cut line can change the effect of other cut lines. Again, this means that an exhaustive or near-exhaustive search must be done that considers all combinations of all cut lines for all intrusions. This can be computationally too expensive.
【００４３】
The Disclosed Algorithm
The algorithm disclosed herein is based on recognizing several factors.
1.  A near-optimum convex region is as good in practice as the optimum convex region.
2.  As a practical matter, interactions between cut lines can generally be ignored as a second order effect. This is a key simplification, because it 1) allows an algorithm to handle concavities one at a time instead of handling all of them together and 2) implies that both ends of all cut lines lie on the perimeter and not in the middle of the polygon.
3.  In searching for a near-optimum rather than an optimum convex region, not all possible cut lines need be considered. In fact, the number is grossly reduced by considering only those cut lines that are extensions of segments of the contiguous polygon.
【００４４】
On a pixelated grid with contiguous perimeters, all perimeter straight line segments are either horizontal, vertical or at a 45° angle. A simple concavity 60 might look like FIGS 12A and 12B.
【００４５】
This method only considers the five cut lines 62A - 62E shown in FIG. 12B, each of which is an extension of one segment of the polygon:
【００４６】
The best of these cut lines differs in orientation from the optimal cut line by at most 22.5° (one half of 45°), since it must lie somewhere between the 0° (horizontal), 45°, and 90° (vertical) cut lines. Assuming that the polygon angles occur randomly (a reasonable assumption), the average error will be half of that, or about 11°. These are acceptable tolerances for cutting off protrusions which generally are themselves just a small fraction of the original polygon.
【００４７】
The steps of this method are as follows:
1.  Find a concavity 60 of the polygon, using any method known in the art (how to do this is not described in this document).
2.  Find all cut lines 62 that can be created by extending a polygon segment at the concavity.
3.  For each cut line, calculate the area of the polygon that would result if that cut was made.
4.  Make a cut along the cut line that produces the largest area polygon after the cut.
5.  Repeat the above steps with the polygon that was produced by the cut until there are no concavities left.
【００４８】
A typical result is shown in FIGS. 13A and 13B. The original contiguous polygon 26B is shown in black and the convex subset 32B in grey.
【００４９】
Step 4 - Find the largest rectangle that has the aspect ratio within each convex region
For each convex region (one per eye) the largest rectangle 64B of the aspect ratio that fits in the convex region 32B must be found. The result is shown in FIG. 14, where the black rectangles 64A, 64B, 64C represent the largest orthogonal rectangle that has the predetermined aspect ratio and fits within each grey convex area:
【００５０】
Terminology
The aspect ratio of a rectangle is the ratio of its width to its height.  In this case, it refers the unit interval of the eye diagram i.e. width, and to the height of the diagram as defined by upper and lower signal levels in each eye.
【００５１】
A rectangle is orthogonal if its sides are vertical and horizontal, i.e., it is not on an angle.
A polygon is contiguous if its perimeter is specified by a contiguous sequence of pixels.
A region is convex if, given any two points within the shape, the straight line connecting them is also entirely within the region.
【００５２】
The Algorithm
For a given aspect ratio, knowing any two corners of the rectangle completely determines the rectangle. Consider a point P on the polygon’s perimeter as shown in FIG. 15A. (This method works on a pixelated grid but the pixelation is not shown in the diagrams.)
【００５３】
For any rectangle as shown in FIG. 15B that has a corner at P, each of the rectangle’s other three corners will have two constraints: (1) that the corner must be inside the polygon and (2) that the entire rectangle must also be inside the polygon.
【００５４】
The first step of the method is to select an arbitrary point P on the convex region and project straight lines from P horizontally, vertically and diagonally. The angle of the diagonal line is determined by the desired aspect ratio, so that the line will pass through the corner opposite P. Find the points PH, PV and PD where the horizontal, vertical and diagonal lines intersect with the polygon again. Because the polygon is convex these other intersections are unique (ignoring the special case in which the polygon itself has sides that are horizontal, vertical or diagonal at the correct angle).
【００５５】
One possible configuration is shown in FIG. 15B. 
【００５６】
In conjunction with point P, each of PH, PV and PD can define a different rectangle that has the desired aspect ratio, as shown in FIG. 15C.
【００５７】
But, because we know the polygon is convex, the smallest of these rectangles is the rectangle we seek for point P. It is the largest orthogonal rectangle with one corner at P and with the correct aspect ratio that fits inside the polygon. In the figure above it is the rectangle determined by PV.
【００５８】
The proof of this is as follows.
Certainly no larger rectangle is possible, for then the lower left corner would be below PV which would place it outside the polygon. It remains to show that the rectangle determined by PV is entirely within the polygon. Consider the remaining rectangle corners QH and QD as shown in FIG. 15D.
【００５９】
By convexity, because P and PH are in the polygon so is QH.
【００６０】
By convexity, because P and PD are in the polygon so is QD.
【００６１】
By convexity, because all four corners of the rectangle are in the polygon so are all four sides of the rectangle.
【００６２】
Because any interior point of the rectangle lies on some straight line connecting points on the sides of the rectangle, then by one final use of convexity that interior point is also in the polygon.
【００６３】
This demonstrates that, because the polygon is convex, we need not check whether the rectangle is wholly contained within the polygon. By selecting the smallest of the three rectangles we are guaranteed to have the correct rectangle based at point P.
【００６４】
Finally, the steps of the algorithm are the following.
Step 1. Pick a point P on each convex region and project straight lines from P horizontally, vertically and diagonally to find points PH, PV and PD.
Step2. Select the smallest of the three rectangles determined by PH, PV and PD as the rectangle for point P.
Step 3. Repeat the previous steps for all perimeter points (this is all inclusive because the polygon is contiguous) to determine the rectangle for each point. Select the largest such rectangle.
【００６５】
Step 5 - Find the optimum sampling point for each eye 
Once the largest rectangle has been found for each convex region, the optimum sampling point 66A, 66B, 66C for an eye is selected as the center of the rectangle, as shown in FIG. 16:
【００６６】
The crosses define the sampling points shown in FIG. 2, reproduced again in FIG. 17A.  Note that the sampling points in FIG. 17A are not necessarily vertically aligned; i.e. in phase.
【００６７】
Step 6 (Optional) - Coerce the sampling points into a common time interval 
Optionally, although each eye has been analyzed independently, a common sampling phase 70 may be enforced. When this option is used, the sampling points found above are coerced into a time interval that all the eyes have in common (which may be a narrow range for some systems) with their thresholds adjusted as necessary. For example, by:
1)  Determine a phase range that is common to all eyes. If no such range exists, there is no constrained solution.
2)  Compute the average of the phases. If it is within the common range, use this phase for all sampling points. Otherwise, use the midpoint of the common range.
3)  For each eye, select as its decision threshold the vertical midpoint at the common phase.
【００６８】
The image in FIG. 17B shows an example output when the sampling points above are coerced into a common time interval.  As can be seen in figure 17B, the white sampling points are closer to each other on the horizontal axis.
【００６９】
Having described and illustrated the principles of the invention in a preferred embodiment thereof, it should be apparent that the invention can be modified in arrangement and detail without departing from such principles.
【符号の説明】
【００７０】
20  Transmitter
22  Channel
24  Receiver
26  Eye Diagram
26A  Eye
26B  Eye
26C  Eye
28A  one of four signal levels of PAM4
28B  one of four signal levels of PAM4
28C  one of four signal levels of PAM4
28D  one of four signal levels of PAM4
30  White Cross（Sampling Point）
32A  Convex Region
32B  Convex Region
32C  Convex Region
36  Concavity
38  Protrusion
40  Line
42  cut line
44  cut line
46  Intruding Vertex
48  Concavity
50  Concavity
54  cut line
56  cut line
58  Dot
60  Concavity
62A  cut line
62B  cut line
62C  cut line
62D  cut line
62E  cut line
64A  Rectangle
64B  Rectangle
64C  Rectangle
66A  Sampling point
66B  Sampling point
66C  Sampling point
70  Common sampling phase
【請求項１】
A multi-symbol communications system, comprising:
a transmitter for transmitting a signal includes a sequence of symbols;
a receiver for the sequence of symbols; and
a channel coupling the transmitter to the receiver;
the sequence of symbols including at least two different symbols which can be transmitted in one-unit interval and each symbol associated with its own signal level;
the sequence of symbols defining an eye diagram for graphically representing in one or more eyes all possible unit-interval sized waveforms of a signal overlain in a graph one-unit interval wide;
the eye diagram having a horizontal axis representing a time axis and a vertical axis representing the signal level;
each eye forming a polygon having a horizontal axis representing a time axis and a vertical axis representing the signal level;
a bounding box defining a region of each eye in the eye diagram bounded in time to a middle half of the unit interval and bounded in signal level by specific signal levels just below and just above the eye;
a sampling point in the unit interval within each eye to determine which signal the waveform in any unit interval represents; 
means for determining a maximal convex subset within each eye; and
means for determining a largest orthogonal rectangle that fits in the convex subset of each eye;
the sampling point for each eye being positioned at a signal level equal to the center of the rectangle.
【請求項２】
A method of multi-symbol communications from a transmitter to a receiver via a channel, including transmitting signals as a waveform representing a sequence of symbols, each symbol of unit-interval duration and each symbol associated with its own signal level, the method comprising:
graphically representing the waveform as an eye diagram having a horizontal time axis and a vertical signal level axis arranged to form one or more eyes;
using a sampling point in each eye to determine which signal the waveform in any unit interval represents, each sampling point having a phase and a decision threshold;
identifying the eyes in the eye diagram;
finding a convex polygonal region fitting within each eye;
finding a largest rectangle fitting the convex polygonal region of each eye; and
positioning the sampling point in each eye at a center of the rectangle of that eye.
【請求項３】
A method of multi-symbol communications according to claim 2 in which finding a convex polygonal region includes determining a polygonal region that fits within the eye, and trimming the polygonal region along one or more cut lines to remove one or more concavities.
【要約】
【課題】 Find an optimum sampling point in an Eye Diagram
【解決手段】 A system and method of multi-symbol communications from a transmitter to a receiver via a channel, including transmitting signals as a waveform representing a sequence of symbols, each symbol of unit-interval duration and each symbol associated with its own signal level.  This method includes graphically representing the waveform as an eye diagram having a horizontal time axis and a vertical signal level axis arranged to form one or more eyes, and using a sampling point 66 in each eye to determine which signal the waveform in any unit interval represents.  Each sampling point 66 has a phase and a decision threshold.  The method further includes identifying the eyes in the eye diagram, finding a convex polygonal region fitting within each eye, finding a largest rectangle fitting the convex polygonal region of each eye, and positioning the sampling point 66 in each eye at a center of the rectangle of that eye.
【選択図】図１６
【図１】
2017103754.tif 000031
【図２】
2017103754.tif 000032
【図３】
2017103754.tif 000033
【図４】
2017103754.tif 000034
【図５】
2017103754.tif 000035
【図６】
2017103754.tif 000036
【図６Ａ】
2017103754.tif 000037
【図６Ｂ】
2017103754.tif 000038
【図６Ｃ】
2017103754.tif 000039
【図７】
2017103754.tif 000040
【図８】
2017103754.tif 000041
【図９】
2017103754.tif 000042
【図１０】
2017103754.tif 000043
【図１１】
2017103754.tif 000044
【図１１Ａ】
2017103754.tif 000045
【図１１Ｂ】
2017103754.tif 000046
【図１２Ａ】
2017103754.tif 000047
【図１２Ｂ】
2017103754.tif 000048
【図１３Ａ】
2017103754.tif 000049
【図１３Ｂ】
2017103754.tif 000050
【図１４】
2017103754.tif 000051
【図１５Ａ】
2017103754.tif 000052
【図１５Ｂ】
2017103754.tif 000053
【図１５Ｃ】
2017103754.tif 000054
【図１５Ｄ】
2017103754.tif 000055
【図１６】
2017103754.tif 000056
【図１７Ａ】
2017103754.tif 000057
【図１７Ｂ】
2017103754.tif 000058