(57)【要約】【課題】事後にビット・ストリーム中のデータに関する分析を再現する。【解決手段】試験測定装置４０５は、ステート・マシーン４１５を記憶できる。ステート・マシーン４１５は、ビット・ストリーム４３５を分析するのに利用され、状態に由来するパンくずリスト４６５は、ステート・マシーンのメモリ４１０に保存できる。すると、パンくずリスト４６５は、ステート・マシーン４１５の動作を分析するのに利用できる。【選択図】図４
2016085745.tif 000002
【特許請求の範囲】
【請求項１】
試験測定装置と、
該試験測定装置上のメモリと、
正規表現及びビット・ストリームを受けるよう動作する上記試験測定装置上の受信部と、
上記正規表現からステート・マシーンを発生するステート・マシーン発生部と、
上記ステート・マシーンを用いて上記ビット・ストリームを分析するよう動作する分析部と、
上記ステート・マシーン中のある１つの状態に入るたびに、パンくずリストを発生して上記メモリ中に保存するパンくずリスト発生部と
を具える分析用システム。
【請求項２】
上記パンくずリスト発生部は、予期せぬ入力についてエラー状態に入ったときに、形式、ＩＤ及び時間の中の少なくとも１つを含むパンくずリストを生成し、上記メモリに保存するよう動作する請求項１による分析用システム。
【請求項３】
試験測定装置で正規表現を受ける処理と、
上記正規表現からステート・マシーンを生成する処理と、
上記ステート・マシーンをビット・ストリームに適用する処理と、
上記ステート・マシーン中の少なくとも１つの状態に関して、少なくとも１つの上記状態に入るときに、上記試験測定装置のメモリにパンくずリストを保存する処理と
を具える分析用方法。
【請求項４】
少なくとも１つの上記状態に入るときに、上記試験測定装置のメモリにパンくずリストを保存する処理が、予期せぬ入力についてエラー状態に入ったときに、エラーのパンくずリストを保存する処理を含み、上記パンくずリストが、形式、ＩＤ及び時間の中の少なくとも１つを含む請求項３による分析用方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、試験測定装置に関し、特に、試験測定装置においてビット・ストリームの分析を再現する方法に関する。
【先行技術文献】
【特許文献】
【０００２】
【特許文献１】特表２００７−５２２４５３号公報
【特許文献２】米国特許第７７９７３４６号明細書
【特許文献３】特表２００４−５２３１６６号公報
【特許文献４】特開２００７−２８６０２５号公報
【特許文献５】米国特許第９０６９０１７号明細書
【特許文献６】特許第５６０５８４２号公報
【非特許文献】
【０００３】
【非特許文献１】「Breadcrumb（navigation）」の記事、Wikipedia（英語版）、［オンライン］、［２０１５年１０月２３日検索］、インターネット、<https://en.wikipedia.org/wiki/Breadcrumb_(navigation）>
【非特許文献２】「パンくずリスト」の記事、Wikipedia（日本語版）、［オンライン］、［２０１５年１０月２３日検索］、インターネット、<https://ja.wikipedia.org/wiki/パンくずリスト>
【発明の概要】
【発明が解決しようとする課題】
【０００４】
信号のリアルタイム分析には、いいところもある。しかし、時として、事後にデータに関する試験測定装置の動作を再現し、その詳細をチェックできるようにするのは有益である。現在、ビット・ストリーム中のデータを分析するときに、この分析の再現を行う方法がない。
【０００５】
本発明の実施形態は、従来技術のこれと他の問題に取り組むものである。
【課題を解決するための手段】
【０００６】
本発明は、次のような種々の概念から表現できる。
【０００７】
本発明の概念１は、システムであって、
試験測定装置と、
該試験測定装置上のメモリと、
正規表現及びビット・ストリームを受けるよう動作する上記試験測定装置上の受信部と、
上記正規表現からステート・マシーンを発生するステート・マシーン発生部と、
上記ステート・マシーンを用いて上記ビット・ストリームを分析するよう動作する分析部と、
上記ステート・マシーン中のある１つの状態に入るたびに、パンくずリストを発生して上記メモリ中に保存するパンくずリスト発生部と
を具えている。
【０００８】
本発明の概念２は、上記概念１によるシステムであって、このとき、上記パンくずリスト発生部は、形式、ＩＤ及び時間の中の少なくとも１つを含むパンくずリストを発生するよう動作する。
【０００９】
本発明の概念３は、上記概念１によるシステムであって、このとき、上記パンくずリスト発生部は、予期せぬ入力についてエラー状態に入ったときに、形式、ＩＤ及び時間の中の少なくとも１つを含むパンくずリストを生成し、上記メモリに保存するよう動作する。
【００１０】
本発明の概念４は、上記概念１によるシステムであって、上記ステート・マシーンを最適化するよう動作するステート・マシーン最適化部を更に具えている。
【００１１】
本発明の概念５は、上記概念１によるシステムであって、保存された上記パンくずリストを利用して、上記ステート・マシーンの動作を再現する再現部を更に具えている。
【００１２】
本発明の概念６は、方法であって、
試験測定装置で正規表現を受ける処理と、
上記正規表現からステート・マシーンを生成する処理と、
上記ステート・マシーンをビット・ストリームに適用する処理と、
上記ステート・マシーン中の少なくとも１つの状態に関して、少なくとも１つの上記状態に入るときに、上記試験測定装置のメモリにパンくずリストを保存する処理と
を具える。
方法を含む。
【００１３】
本発明の概念７は、上記概念６による方法であって、このとき、少なくとも１つの上記状態に入るときに、上記試験測定装置のメモリにパンくずリストを保存する処理が、上記ステート・マシーン中の各状態に入るときに、パンくずリストを保存する処理を含んでいる。
【００１４】
本発明の概念８は、上記概念６による方法であって、このとき、少なくとも１つの上記状態に入るときに、上記試験測定装置のメモリにパンくずリストを保存する処理が、少なくとも１つの上記状態に入るときにパンくずリストを保存する処理を含み、上記パンくずリストが、形式、ＩＤ及び時間の中の少なくとも１つを含んでいる。
【００１５】
本発明の概念９は、上記概念６による方法であって、このとき、少なくとも１つの上記状態に入るときに、上記試験測定装置のメモリにパンくずリストを保存する処理が、予期せぬ入力についてエラー状態に入ったときに、エラーのパンくずリストを保存する処理を含み、上記パンくずリストが、形式、ＩＤ及び時間の中の少なくとも１つを含んでいる。
【００１６】
本発明の概念１０は、上記概念６による方法であって、このとき、上記正規表現からステート・マシーンを生成する処理が、上記ステート・マシーンを最適化する処理を含む。
【００１７】
本発明の概念１１は、上記概念６による方法であって、上記ステート・マシーンへのビット・ストリームの適用を把握（フォロー）するために、保存された上記パンくずリストを利用する処理を更に具えている。
【図面の簡単な説明】
【００１８】
【図１Ａ】図１Ａは、特定のパケットにマッチングするプロトコルの例を示す。
【図１Ｂ】図１Ｂは、図１Ａのパケットにマッチできるステート・マシーンを示す。
【図１Ｃ】図１Ｃは、図１Ａのパケットのデータを含む条件についてトリガできるステート・マシーンを示す。
【図２Ａ】図２Ａは、いくつかのパケットにマッチングするプロトコルの第２の例を示す。
【図２Ｂ】図２Ｂは、図２Ａのパケットにマッチする最適化していないステート・マシーンを示す。
【図２Ｃ】図２Ｃは、図２Ａのパケットにマッチする最適化したステート・マシーンを示す。
【図２Ｄ】図２Ｄは、図２Ａのパケットのデータを含む条件についてトリガできるステート・マシーンを示す。
【図３Ａ】図３Ａは、複合トリガ条件を反映するよう変更された図１Ｂのステート・マシーンの例を示す。
【図３Ｂ】図３Ｂは、複合トリガ条件を反映するよう変更された図１Ｂのステート・マシーンの別の例を示す。
【図４】図４は、図１Ｂ〜１Ｃ及び２Ｂ〜２Ｄのステート・マシーンを生成及び利用し、種々のトリガ条件に合致したときに試験測定装置にトリガをかけることができ、そして、図１Ｂ〜１Ｃ及び２Ｂ〜２Ｄのステート・マシーンの動作を反映しているパンくずリストをメモリに保存できる、本発明の実施形態による試験測定装置を示す。
【図５】図５は、図４のステート・マシーン変更部をより詳細に示す。
【図６】図６は、図４のパンくずリストをより詳細に示す。
【図７Ａ】図７Ａは、図４の試験測定装置を用いて、プロトコル及びユーザ設定からトリガ・ステート・マシーンを生成する本発明の実施形態による手順の一部分のフローチャートを示す。
【図７Ｂ】図７Ｂは、図４の試験測定装置を用いて、プロトコル及びユーザ設定からトリガ・ステート・マシーンを生成する本発明の実施形態による手順の残りの部分のフローチャートを示す。
【図８】図８は、図４の試験測定装置を用いて、プロトコル及び複合トリガ条件からトリガ・ステート・マシーンを生成する本発明の実施形態による手順のフローチャートを示す。
【図９】図９は、図４の試験測定装置を用いて、ステート・マシーンを最適化する本発明の実施形態による手順のフローチャートを示す。
【図１０】図１０は、図４の試験測定装置を用いて、パンくずリストを保存できるステート・マシーンを生成する処理を利用する本発明の実施形態による手順のフローチャートを示す。
【発明を実施するための形態】
【００１９】
本発明がどのように動作するか説明する前に、正規表現及びステート・マシーンの間の関係を理解するのは有益である。
【００２０】
正規表現が与えられると、その正規表現を表すステート・マシーンを構築できる。すると、そのステート・マシーンは、特定の入力がその正規表現とマッチするかどうかを判断するのに利用できる。もしそのステート・マシーンが許容し得る最終状態になれば、入力は、その正規表現とマッチする。さもなくば、入力は正規表現とはマッチしない。
【００２１】
図１Ａは、「データ・パケット」と名前の付けられ、正規表現として表現されたデータのパケットに関するプロトコルの例を示す。プロトコル１０５は、データのパケットを記述している。ビット・ストリームがこの正規表現に対して比較されると、システムは、そのビット・ストリーム内にそのパケットが見つけられるかどうか判断できる。
【００２２】
図１Ｂは、図１Ａの正規表現に対応するステート・マシーンを示す。ステート・マシーン１１０には、状態１１５、１２０、１２５、１３０、１３５、１４０及び１４５があり、これら状態間の遷移を伴う。各状態（これは、ノード又は頂点とも呼ぶことができる）は、その状態に入るのにどのようなデータがマッチする必要があるかを記述している（受容基準）。各矢印は、その状態に関する目標の受容基準が満たされていれば、横断できるパスである。スタート状態１１５及び成功状態１４５は除いて、これら状態は、パケットによって予期されるデータに順次対応している。よって、状態１２０は、ビット・ストリーム内の状態Ｓとマッチし、状態１２５は、「begin（開始）」とラベルされたフィールドに対して、３ビットのデータとマッチし、状態１３０は、「addr」とラベルされたフィールドに対して、４ビットのデータとマッチする、などである。全てのデータがステート・マシーン１１０の複数の状態によって、マッチさせることができるとすると、成功状態１４５に達したとき、システムは、そのパケット「データ・パケット」は、成功裏にマッチしたと宣言できる。
【００２３】
ステート・マシーン１１０は、実際のステート・マシーンの簡略化バージョンを表している。例えば、ステート・マシーン１１０は、種々の状態間の遷移にラベルを付けていないし、ステート・マシーン１１０は、データが予期したものとマッチしない場合に使用されるエラーの状態又は遷移を示してもいない。当業者であれば、これら詳細がなくても、ステート・マシーン１１０がどのように動作するか、理解できよう。
【００２４】
正式には、数学用語では、ステート・マシーンは、５個の成分からなるもの（Σ，Ｓ，ｓ０，δ，Ｆ）として表され、ここで、Σはアルファベット（ステート・マシーンによって認識された複数シンボルからなるセット）であり、Ｓはステート・マシーン中の複数状態からなるセット（set：組、グループ）であり、ｓ０は初期状態であり、δは遷移関数であって、Ｓ中の各状態及びΣ中の各シンボルをＳ中の状態（これは、入力の状態と同じ状態であっても良い）へとマッピングし、そして、Ｆは、Ｓ中の複数の最終状態のセットである。よって、ステート・マシーン１１０は、より正式には、（Σ，Ｓ，ｓ０，δ，Ｆ）として表すことができ、ここで：
【００２５】
Σ＝｛Ｓ，０，１，…｝（状態Ｓ及びバイナリ値０及び１だけよりも、もっと多くの認識されたシンボル（これらはステート・マシーンによって認識されたシンボルだけであるけれども）が潜在的に存在し得る）
【００２６】
Ｓ＝｛１１０，１１５，１２０，１２５，１３０，１３５，１４０，１４５｝
【００２７】
ｓ０＝１１０
【００２８】
δ（δは、その完全な遷移関数を表すのは、非常にめんどうであるし、ほとんど価値がないであろうことから、ここでは、より詳細には表さない）
【００２９】
Ｆ＝｛１４５｝
【００３０】
実際、ステート・マシーン１１０のこの表現は、必ずしも完全ではない。遷移は、典型的には、シンボルのグループでよりは、個々のシンボルで生じる。よって、状態１２０から１２５への遷移は、実際には、３つの遷移（そして、それ故に、いくつかの中間状態）を含むことができる（各ビットについて認識されたものは、そのフィールドが「begin」とラベルが付けられる）。しかし、簡略化しても、当業者であれば、ステート・マシーン１１０がどのように動作するか理解できよう。
【００３１】
ユーザは、ステート・マシーン１１０中で、ある特定の値が所与の状態に関して読み出されたら、ある処理にトリガをかけたい（処理を始動したい）かもしれない。例えば、ユーザは、もしアドレス・フィールドが値１０（バイナリ値で１０１０、１６進数でＡ）を保持していたら、ある処理にトリガをかけたいかもしれない。図１Ｃは、このトリガを実現するためにどのようにステート・マシーン１１０を変更できるかの例を示す。図１Ｃでは、任意のあり得る値をアドレス・フィールドに関してマッチング処理する代わりに、ステート・マシーン１５０が、ビット・ストリームを特定の値１０１０と（状態１５５において）比較している。もしその値が見つかれば、続いて、状態１６０において、トリガが満たされたと考えられ、そして、トリガが処理を開始させる（その処理は、どのようなものでも良い）。
【００３２】
状態１１５及び１２０は、ステート・マシーン１５０と、ステート・マシーン１１０とで同じであることに注意されたい（状態１１５は、ステート・マシーンが開始する状態であり、状態１２０は、ビット・ストリームの状態Ｓとマッチする）。しかし、状態１６５は特定フィールドが読み出されたかに留意しない点で、状態１２５とは異なる。言い換えれば、状態１６５では、重要なのは、３つのビットがビット・ストリームから読み出されることだけである。状態１５５は、そのアドレス・フィールドにマッチするか（状態１３０でのように）ではなく、その特定ビット・パターン１０１０とマッチするかだけに関係があるので、状態１５５も状態１３０とは異なる。最後に、ユーザの条件が一度マッチしたら、更なるマッチング処理を行う必要はなく、そのため、ステート・マシーン１５０は、状態１３５及び１４０に類似するものを持っていない：条件を満たした後、トリガを直ちに出すことができる。
【００３３】
図１Ａ〜１Ｃは、正規表現、この正規表現にマッチするステート・マシーン及びトリガ・ステート・マシーンのかなり単純化した例を示す。（トリガ・ステート・マシーンは、時として、シンプルに「ステート・マシーン」と呼ばれるが、状況から、当業者であれば、特定のステート・マシーンが、トリガ・ステート・マシーンであるか、又は、正規表現にマッチするステート・マシーンであるかを判断できる。）図２Ａ〜２Ｄは、もっと複雑な例を示す。図２Ａでは、３つの異なるパケットに関する正規表現が示されている。これら正規表現は、図２Ｂに示すように、ステート・マシーンに変換できる。図２Ｂのステート・マシーン２０５は、３つの可能なプロトコルをカバーするのに、単一のスタート（start）状態を利用していることに注意されたい。
【００３４】
ステート・マシーン２０５は、示したように利用できる。しかし、ステート・マシーン２０５を示したように使うには、先読み又はバックトラッキングが必要であろうし、これは、追加のメモリを必要とし、ビット・ストリームの処理を低下させることがある。例えば、複数の状態が、特定の入力を前提として、最も左に達したと仮定しよう（図２Ｂは、プロセッサがどのようにステート・マシーン２０５を使うかというよりは、人によって読まれるであろうため）。例えば、状態２１０、２１５及び２２０の全ては、Begin状態にマッチし、そして、状態２２５、２３０及び２３５の全ては、スレーブ・アドレス・フィールドとして、４ビットにマッチすることに注意されたい。最も左を優先するアプローチを用いると、Begin状態と、スレーブ・アドレス・フィールドとして４ビットとを読んだ後には、システムは、状態２２５にあるであろう。しかし、もし次に読むビットが０だと、システムは、ステート・マシーン２０５の間違った枝（ブランチ）をたどり、そして、正しい枝を見つけようとして、ステート・マシーン２０５を巻き戻さなければならないであろう。これは、バックトラッキングの例である。ステート・マシーン２０５を逆行させ、異なる枝を処理しなければならなくなると、ビット・ストリームの処理が遅くなるのは、明かであろう。ステート・マシーン２０５を用いてバックトラッキングを避けるには、先読み処理が必要となろう（システムは、ビット・ストリームにこれからやってくるビットをなんとかして調べなければならない）。先読みも、複雑で高価である。
【００３５】
バックトラッキング及び先読みの両方を避けるように、ステート・マシーン２０５を最適化できる。図２Ｃのステート・マシーン２４０は、最適化したステート・マシーンの例を示す。ステート・マシーン２４０によれば、先読みをする必要がなく、バックトラッキングの心配もない。複数パケットのいずれかの任意のプリフィックス（先頭の値）が与えられると（パケット全体を含めて、パケット全体まで）、そのプリフィックスにマッチするあり得るパスは、ステート・マシーン２４０を通して、１つしかない。従って、先読みをする必要はないし、バックトラッキングを心配する必要もない：ステート・マシーン２４０中の特定の状態と、特定の入力シンボルとが与えられると、遷移する先のあり得る状態は１つしかない（この状態は、簡単のため、図２Ｃでは示していないエラー状態かもしれない）。
【００３６】
最適化は、次の手順を用いて達成できる。スタート状態からツリーを歩くことによってスタートし、等しい複数のノードを組み合わせ（つまり、それら複数ノードを単一のノードに結合する）、同じ親（parent：ペアレント）を持たせる。この処理は、組み合わせるノードが無くなるまで繰り返すことができる。続いて、等しい成功状態を見つけ、それらを組み合わせ、次に等しいノードを組み合わせ、同じ子供（チルドレン）を持たせる（再度、組み合わせノ―ドが無くなるまで、その処理を繰り返す）。
【００３７】
図２Ｄは、ユーザによってカスタマイズされた特定トリガの例を示す。図２Ｄでは、ユーザは、正規表現中のパケットのアドレス・フィールド（スレーブ・アドレス・フィールドではない）が値０に設定された場合に、トリガするように選択している。このフィールドは、パケットのレジスタ０ライト（Register０Write）中に現れないので、そのステート・マシーンのこの枝（ブランチ）全体をトリガ・ステート・マシーン２４５から排除できる。どのような値もスレーブ・アドレス・フィールドに対してマッチでき、その後で、ビット０及び１は、マッチしなければならない。その後、任意のビットが発生でき（実際のビットは、読まれる特定のパケットに依存するであろうが、トリガ・ステート・マシーン２４５は、どの値を受けるに関係がない）、その後に、アドレス・フィールドに関するビットを受け、値０と比較できる。もし値０がアドレス・フィールドについてマッチするなら、トリガ・ステート・マシーン２４５は成功であり、トリガを開始できる。
【００３８】
上記例は、等式として表される単一のトリガ基準を利用する。しかし、そのトリガ条件を等式に限定する理由はない。等式（＝＝）を別にすると、他のトリガ条件の例としては、等しくない（！＝）、より小さい（＜）、以下（＜＝）、より大きい（＞）、又は、以上（＞＝）があり得る。加えて、トリガ条件は、正規表現中のフィールドの情報のサブセットだけに依存するかもしれない。例えば、図２Ｄでは、ユーザは、アドレス・フィールドの中間の３ビットが００１に等しいかどうかだけに感心があるかもしれない（アドレス・フィールド（これは、合計５ビットを持っている）の最初と最後のビットは、任意の値にマッチして良い）。特定の状態に達することだけに依存してトリガ条件を設定することも可能である。例えば、ユーザは、その実際の値に関係なく、いつアドレス・フィールドに達したかを知ることに感心があるかもしれない。
【００３９】
加えて、トリガ条件は、単一の基準（これは、１つの単純なトリガ条件と呼ばれる）に限定される必要はない。ユーザは、任意の所望組み合わせにＡＮＤ及びＯＲ演算子を用いて組み合わせられた複数の基準（複合トリガ条件）を指定できる。よって、ステート・マシーンは、複数の条件（これらのいずれかは、サブ条件などのセットを含むかもしれない）を試験することができる。当業者であれば、ユーザが供給した条件を、どのようにして積和標準形（Disjunctive Normal Form）又は和積標準形（conjunctive normal form）に単純化するかわかるであろうし、これは、ステート・マシーンの構造を単純化できる。（積和標準形は、連言節（conjunctive clause）の選言（disjunction）、即ち、ＡＮＤ（論理積）のＯＲ（論理和）として表現された論理式に言及する。和積標準形は、同様にＯＲ（論理和）のＡＮＤ（論理積）を表す。）
【００４０】
図３Ａ〜３Ｂは、複合トリガ条件を有するステート・マシーンの例を示す。図３Ａでは、ユーザが、（addr == 0xA && parity == 1）のトリガ条件を指定している。こうしたトリガ条件は、２つの条件の連言（conjunction：論理積、結合）である。このトリガ条件は、２つの状態の両方が特定の値を持つことを必要とするので、ステート・マシーン中の２つの状態が（ユーザによって指定されて）特定の値に設定される。他の状態の値は、通常、重要ではなく、単一の状態へと組み合わせることができる。
【００４１】
図３Ｂでは、ユーザは、（addr == 0xA || parity == 1）の特定トリガ条件（選言的トリガ条件）を指定している。このトリガ条件は、２つの状態の一方が特定の値を持つことを必要とするので、別々の条件を有する２つのステート・マシーンを確立し、上述の最適化手法を用いて統合できる。このトリガ条件は、選言（disjunction）のため、１つステート・マシーンに適用されるけれども、成功トリガへのあり得るパスは２つ存在する。
【００４２】
図３Ａ〜３Ｂは、２つの可能なトリガ値を組み合わせる単一のＡＮＤ又はＯＲを含んでいる例を与える。しかし、この処理をもっと複雑なトリガ条件に関して一般化できることは明かであろう。例えば、もしトリガ条件が、ＡＮＤ演算で結合される２つの値か、又は、もう１つの値（（Ｘ  ＡＮＤ  Ｙ）ＯＲ  Ｚ）の形の式）を含むなら、ステート・マシーンはコピーしても良い。１つのコピーは、ＡＮＤ演算の第１値を反映するよう変更でき、第２のコピーは、ＡＮＤ演算の第２値を反映するよう変更でき、第３のコピーは、ＯＲ演算の残りの値を反映するよう変更できる。最初の２つのステート・マシーンは、続いて、第３のステート・マシーンと組み合わせられて最適化され、複合トリガ条件を表すようにできる。
【００４３】
さて、トリガ・ステート・マシーンを説明してきたが、トリガ・ステート・マシーンを利用できるシステムを説明できる。図４は、種々のトリガ条件が満たされたときに、試験測定装置をトリガする図１Ｂ〜１Ｃ及び２Ｂ〜２Ｄのステート・マシーンを生成及び利用できる、本発明の実施形態による試験測定装置を示す。システムは、試験測定装置４０５を含んでいても良い。試験測定装置は、他にも可能性がある中で特にオシロスコープのような、任意の所望の試験測定装置であっても良い。
【００４４】
試験測定装置４０５は、メモリ４１０を含んでも良い。メモリ４１０は、ステート・マシーン４１５のような情報を記憶できる。ステート・マシーン４１５は、正規表現にマッチさせるのに利用されるステート・マシーン、言い換えると、図１Ｂ、２Ｂ及び２Ｃのステート・マシーン１１０、２０５及び２４０のようなステート・マシーンとしても良い。ステート・マシーン４１５は、図１Ｃ及び２Ｄのステート・マシーン１５０及び２４５のような、トリガ・ステート・マシーンであっても良い。
【００４５】
試験測定装置４０５は、試験測定装置４０５の入力を受けることができる受信部４２０も含むことができる。入力は、あらゆる方法で受けることができる。例えば、受信部４２０は、トリガ条件４２５（これ自身が、例えば、特定のビット・フィールドに関してユーザが選択した値４３０を含んでも良い）のような情報をユーザが入力するためのユーザ・インタフェースを含んでいても良い。又は、受信部４２０が、分析すべきビット・ストリーム４３５のようなビット・ストリームを含む信号を受けるのを含んでいても良い。また、受信部４２０は、（例えば、統合開発環境（ＩＤＥ）を通して）正規表現４４０を受けても良く、これは、システムがビット・ストリーム４３５で受けると予期されるデータを特定でき、ステート・マシーン４１５を構築するのに利用できる（正規表現４４０又はトリガ・ステート・マシーンを認識するステート・マシーンである）。
【００４６】
試験測定装置４０５は、種々の他のユニットも含むことができる。ステート・マシーン変更部４４５は、既存のステート・マシーン（例えば、正規表現４４０にデータをマッチさせるもの）を取ってきて、それをトリガ・ステート・マシーンとして動作するように変更する。上述のように、これは、色々な可能性のなかでも特に、トリガ条件満たした後に生じる状態を除去する処理と、トリガ条件の一部と考えられない値の状態を組み合わせる（結合する）処理とを含むことができる。
【００４７】
処理エンジン４５０は、種々のステート・マシーン（例えば、正規表現４４０又はステート・マシーン変更部４４５を用いて生成されたトリガ・ステート・マシーンを用いて生成されるステート・マシーンを含む）を用いてビット・ストリーム４３５を処理できる。この処理は、ビット・ストリーム４３５からビットが読み出されるときに、種々のステート・マシーンのそれぞれに関する現在の状態をアップデートする処理を含んでも良い。
【００４８】
トリガ・システム４５５は、トリガ条件が満たされたとき、即ち、トリガ・ステート・マシーンが満たされたときに、トリガを送信できる。トリガ・システム４５５は、当業者であれば理解するであろうように、トリガの結果として任意のアクションを実行するために、試験測定装置４０５の任意の所望コンポーネントにトリガを送信できる。
【００４９】
ステート・マシーン発生部４６０は、正規表現４４０からステート・マシーンを生成できる。上述のように、これは、正規表現で提示された順番でフィールドにマッチする状態のシーケンシャルなシリーズを生成する処理を含んでも良い。また、これは、異なる正規表現にマッチする種々のステート・マシーンを単一のステート・マシーンに結合して、先読み及びバックトラッキングの問題を避けるように、ステート・マシーンを最適化する処理を含んでも良い。
【００５０】
トリガ・ステート・マシーンを発生及び利用することとは別に、試験測定装置４０５は、パンくずリスト（「パンくず リスト」又は「パンくずナビゲーション」とも呼ばれる：非特許文献１及び２参照）を生成するのにも利用できる。「パンくずリスト」の用語は、パンくずの跡を付けるというヘンデルとグレーテルの童話に由来する。パンくずリストは、ステート・マシーンの動作を、ユーザが再現し、データがどのように処理されたか見るのを可能にする。パンくずリスト４６５のようなパンくずリストは、メモリ４１０に記憶できるデータのほんのちょっとのものである。基本的に、ステート・マシーン中の状態に入るたびに、パンくずリストは保存されて良い。パンくずリストは、状態の形式（例えば、エラー状態、パケット・スタート、パケット・エンド又はフィールド）、状態のＩＤ（これは、フィールド又はパケットを特定できる）及び状態に入ること（エントリー）を生じさせるデータのスタート及びストップ時間のような時間、などのようなデータを含むことができる。当業者であれば、他の可能性のなかでも特に、「時間」は、文字通りの時間の概念（信号のスタートから秒単位で、又は、その何分の１かで）に言及しなければならないものはでなく、むしろ信号へのインデックスに言及しても良いことが理解できよう。パンくずリストは、適宜、分析に関係する追加データも含んで良い。従って、パンくずリストに含めるべきデータのＩＤ（identification：識別）は、ユーザがカスタマイズできる。
【００５１】
パンくずリストは、通常、トリガ・ステート・マシーンを用いて生成できる。しかし、当業者であれば、任意の他のステート・マシーンをパンくずリストの生成に利用できないという理由はなく、従って、任意のステート・マシーンを用いてパンくずリストを生成できることが理解できよう、
【００５２】
パンくずリストの生成をサポートするため、試験測定装置４０５が分析部４７０を含んでも良い。分析部４７０は、ステート・マシーンを用いてビット・ストリーム４３５を分析できる。動作において、分析部４７０は、処理エンジン４５０に類似するが、それらの目的は異なる。処理エンジン４５０が、正規表現を認識しようとして、ビット・ストリーム４３５のビットをマッチングに関与する一方、分析部４７０は、パンくずリストをいつメモリ４１０に保存するか判断することに関与する。また、分析部４７０及び処理エンジン４５０は、典型的には、異なるステート・マシーン上で動作する：分析部４７０は、通常、トリガ・ステート・マシーンを利用する（利用しなければならないことはないが）一方で、プロセッサ４５０は、正規表現にマッチするフルのステート・マシーンを利用する。
【００５３】
試験測定装置４０５は、パンくずリスト発生部４７５も含んで良い。パンくずリストを発生する時間であるという（例えば、新しい状態に入ったと、分析部４７０によって判断されるような）場合に、パンくずリスト発生部４７５は、そのパンくずリストをメモリ４１０に保存できる。
【００５４】
最後に、試験測定装置４０５は、再現部４８０を含んでも良い。再現部４８０は、ユーザが、ビット・ストリーム４３５についてのステート・マシーンの動作を（分析部４７０で処理されたように）再現するのを可能する。この再現は、ユーザが、何が起きたかを追いかける（フォローする）のを可能にする。
【００５５】
上述の試験測定装置４０５は、トリガ・ステート・マシーン又はパンくずリストの生成のいずれか、又は両方を処理できる。試験測定装置の中には、複数のステート・マシーンを処理するのに必要なハードウェア及び／又はソフトウェアを含むものもある。もし試験測定装置が、複数のステート・マシーンを処理できるのなら、試験測定装置４０５は、トリガ条件及びパンくずリストに関する処理の両方を実行できる。
【００５６】
図５は、図４のステート・マシーン変更部をより詳細に示している。図５では、ステート・マシーン変更部４４５は、ステート・マシーン最適化部５０５を含んでいるとして示されている。ステート・マシーン最適化部５０５は、上述のように、ステート・マシーンを最適化できる。こうした最適化は、正規表現にマッチするよう設計されたステート・マシーンについてか、又は、トリガ・ステート・マシーンについてか、どちらでも可能である。
【００５７】
図６は、図４のパンくずリストをより詳細に示している。図６では、パンくずリスト４６５は、形式６０５、ＩＤ６１０及び時間６１５を含むとして示されている。上述のように、形式６０５は、パンくずリスト４６５を生成した状態の形式を特定できる。ＩＤ６１０は、パンくずリスト４６５を生成したステート・マシーン中の特定の状態を特定できる。そして、時間６１５は、その状態がいつパンくずリスト４６５を生成したかの、信号中の時間（又はインデックス）を特定できる。
【００５８】
図７Ａ〜７Ｂは、図４の試験測定装置を用いて、プロトコルとユーザ設定とからトリガ・ステート・マシーンを生成する手順のフローチャートを示す。図７Ａでは、ブロック７０５において、システムが正規表現を受けても良い。ブロック７１０では、システムが、正規表現に対応するステート・マシーンを生成できる。ブロック７１５では、システムがステート・マシーンを最適化できる。
【００５９】
ブロック７２０では、システムは、正規表現に対応するステート・マシーン（ブロック７０５〜７１５で生成されたステート・マシーンと同じでも良い）を特定できる。ブロック７２５では、システムは、ユーザからトリガ条件を受ける。これは、色々な可能性のなかでも特に、例えば、正規表現中の特定フィールドに関するユーザ指定値（又は値の一部）、複数のそうしたユーザ指定値、単に到達するべき（リーチすべき）フィールドを含んでいても良い。ブロック７３０では、システムは、トリガ条件を実行するように変更できるステート・マシーン中の１つの状態（又は１より多い状態）を特定できる。
【００６０】
ブロック７３５（図７Ｂ）では、システムは、特定された状態を変更し、ユーザ選択値と比較しても良い。ブロック７４０、システムは、変更されたステート・マシーンを記憶できる。ブロック７４５では、システムは、ビット・ストリームを受けることができる。ブロック７５０では、システムは、変更されたステート・マシーンを用いて、ビット・ストリームを処理できる。ブロック７１０では、システムは、トリガ条件が満たされたか判断できる。もしそうなら、次に、ブロック７５５において、システムは、トリガ・システムを利用（apply）できる。
【００６１】
上述のように、トリガ条件は、複合トリガ条件でも良い。この場合、手順のフローチャートは、トリガ条件の複合された特性を反映するように変更できる。図８は、この変更を反映している。図８は、図７Ａ〜７Ｂのブロック７３０及び７３５を変更している：図７Ａ〜７Ｂの他のブロックは変更がなく、そのため、図８では示していない。
【００６２】
図８では、ブロック８０５において、システムが、複合トリガ条件で関係する複数の状態を特定する。関係する状態の個数は、複合トリガ条件中に含まれる単純な条件の個数よりも少ないことがある。例えば、図１Ｂに示されるステート・マシーンに関する複合トリガ条件は、（addr == 0xA || addr == 0xF）であっても良い。複合トリガ条件の両側で同じ状態が使われることに注意されたい。ブロック８１０では、システムは、複合トリガ条件中の単純なトリガ条件それぞれについて１回、ステート・マシーンを複製する。上記例を続けると、複合トリガ条件は、２つの単純なトリガ条件（addr == 0xA || addr == 0xF）を含み、そのため、システムは、ステート・マシーンの２つの複製を生成するであろう。ブロック８１５では、各複製ステート・マシーン内で、特定された状態が、ユーザ指定値との比較を反映するよう変更される。最後に、ブロック８２０では、変更された複製ステート・マシーンが、複合トリガ条件を反映する単一のステート・マシーンを生成するように結合される。このポイントにおいて、処理は、図７Ｂのブロック７４０に続く。
【００６３】
図９は、図４の試験測定装置を用いてステート・マシーンを最適化する本発明の実施形態による手順のフローチャートを示す。図９では、ブロック９０５において、システムが、トリガ条件が満たされた後に生じた状態を除去できる。ブロック９１０では、システムが、任意の値を満たすことができる隣接する状態を単一の状態に統合できる。
【００６４】
図１０は、図４の試験測定装置を用いてパンくずリストが保存できるステート・マシーンを生成する処理を利用する本発明の実施形態による手順のフローチャートを示す。ブロック１００５では、システムが正規表現を受けても良い。ブロック１０１０では、システムが正規表現からステート・マシーンを生成できる。ブロック１０１５では、システムは、ステート・マシーンを最適化できる。ブロック１０２０では、システムは、ステート・マシーンをビット・ストリームに適用できる。ブロック１０２５では、システムが、ステート・マシーン中のある状態に入るたびに、パンくずリストを保存できる。ブロック１０３０では、システムは、ビット・ストリームへのステート・マシーンの適用を再現するのに、保存されたパンくずリストを利用できる。
【００６５】
上記フローチャートは、いくつかの可能な本発明の実施形態を示している。しかし、本発明の他の実施形態では、ブロックを異なるアレンジで構成でき、要望に応じて異なるブロックを含めたり、省略したり、又は、必要に応じて１つのブロック（又は複数ブロック）を繰り返したりできる。本発明の実施形態は、フローチャートについてのこのようなバリエーションの全てを含むことを意図している。
【００６６】
本発明の実施形態は、限定されることなく、次の記述（statements）に拡張できる。
【００６７】
本発明の実施形態は、試験測定装置と、試験測定装置上のメモリと、正規表現及びビット・ストリームを受けるように動作する試験測定装置上の受信部と、正規表現からステート・マシーンを生成するステート・マシーン発生部と、ステート・マシーンを用いてビット・ストリームを分析するよう動作する分析部と、ステート・マシーン中のある１つの状態に入る（エントリーする）たびにパンくずリストを生成し、メモリ中に保存するよう動作するパンくずリスト発生部とを具えるシステムを含む。
【００６８】
本発明の実施形態は、試験測定装置と、試験測定装置上のメモリと、正規表現及びビット・ストリームを受けるように動作する試験測定装置上の受信部と、正規表現からステート・マシーンを生成するステート・マシーン発生部と、ステート・マシーンを用いてビット・ストリームを分析するよう動作する分析部と、ステート・マシーン中のある１つの状態に入るたびにパンくずリストを生成し、メモリ中に保存するよう動作するパンくずリスト発生部とを具えるシステムを含み、このとき、パンくずリスト発生部は、形式、ＩＤ及び時間のいずれかを少なくとも含むパンくずリストを生成するよう動作する。
【００６９】
本発明の実施形態は、試験測定装置と、試験測定装置上のメモリと、正規表現及びビット・ストリームを受けるように動作する試験測定装置上の受信部と、正規表現からステート・マシーンを生成するステート・マシーン発生部と、ステート・マシーンを用いてビット・ストリームを分析するよう動作する分析部と、ステート・マシーン中のある１つの状態に入るたびにパンくずリストを生成し、メモリ中に保存するよう動作するパンくずリスト発生部とを具えるシステムを含み、このとき、パンくずリスト発生部は、予期しない入力について、エラー状態に入った場合に、形式、ＩＤ及び時間のいずれかを少なくとも含むパンくずリストを生成するよう動作する。
【００７０】
本発明の実施形態は、試験測定装置と、試験測定装置上のメモリと、正規表現及びビット・ストリームを受けるように動作する試験測定装置上の受信部と、正規表現からステート・マシーンを生成するステート・マシーン発生部と、ステート・マシーンを最適化するよう動作するステート・マシーン最適化部と、最適化されたステート・マシーンを用いてビット・ストリームを分析するよう動作する分析部と、最適化されたステート・マシーン中のある１つの状態に入るたびにパンくずリストを生成し、メモリ中に保存するよう動作するパンくずリスト発生部とを具えるシステムを含む。
【００７１】
本発明の実施形態は、試験測定装置と、試験測定装置上のメモリと、正規表現及びビット・ストリームを受けるように動作する試験測定装置上の受信部と、正規表現からステート・マシーンを生成するステート・マシーン発生部と、ステート・マシーンを用いてビット・ストリームを分析するよう動作する分析部と、ステート・マシーン中のある１つの状態に入る（エントリーする）ときはいつもパンくずリストを生成し、メモリ中に保存するよう動作するパンくずリスト発生部と、保存されたパンくずリストを用いて、ステート・マシーンの動作を再現する再現部とを具えるシステムを含む。
【００７２】
本発明の実施形態は、試験測定装置で正規表現を受ける処理と、正規表現からステート・マシーンを生成する処理と、ステート・マシーンをビット・ストリームに適用する処理と、ステート・マシーン中の少なくとも１つの状態に関して、この少なくとも１つの状態に入る（エントリーする）ときに、試験測定装置のメモリにパンくずリストを保存する処理とを具える方法を含む。
【００７３】
本発明の実施形態は、試験測定装置で正規表現を受ける処理と、正規表現からステート・マシーンを生成する処理と、ステート・マシーンをビット・ストリームに適用する処理と、ステート・マシーン中の少なくとも１つの状態に関して、この少なくとも１つの状態に入るときに、試験測定装置のメモリにパンくずリストを保存する処理であって、ステート・マシーン中の各状態に入るときに試験測定装置のメモリにパンくずリストを保存する処理とを具える方法を含む。
【００７４】
本発明の実施形態は、試験測定装置で正規表現を受ける処理と、正規表現からステート・マシーンを生成する処理と、ステート・マシーンをビット・ストリームに適用する処理と、ステート・マシーン中の少なくとも１つの状態に関して、この少なくとも１つの状態に入るときに、試験測定装置のメモリにパンくずリストを保存する処理であって、ステート・マシーン中の少なくとも１つの状態に入るときに試験測定装置のメモリにパンくずリストを保存する処理とを具える方法を含み、上記パンくずリストは、形式、ＩＤ及び時間の少なくとも１つを含んでいる。
【００７５】
本発明の実施形態は、試験測定装置で正規表現を受ける処理と、正規表現からステート・マシーンを生成する処理と、ステート・マシーンをビット・ストリームに適用する処理と、ステート・マシーン中の少なくとも１つの状態に関して、この少なくとも１つの状態に入るときに、試験測定装置のメモリにパンくずリストを保存する処理であって、予期しない入力についてエラー状態に入るときに試験測定装置のメモリにエラーのパンくずリストを保存する処理とを具える方法を含み、上記パンくずリストは、形式、ＩＤ及び時間の少なくとも１つを含んでいる。
【００７６】
本発明の実施形態は、試験測定装置で正規表現を受ける処理と、正規表現からステート・マシーンを生成する処理と、ステート・マシーンを最適化する処理と、最適化したステート・マシーンをビット・ストリームに適用する処理と、最適化したステート・マシーン中の少なくとも１つの状態に関して、この少なくとも１つの状態に入るときに、試験測定装置のメモリにパンくずリストを保存する処理とを具える方法を含む。
【００７７】
本発明の実施形態は、試験測定装置で正規表現を受ける処理と、正規表現からステート・マシーンを生成する処理と、ステート・マシーンをビット・ストリームに適用する処理と、ステート・マシーン中の少なくとも１つの状態に関して、この少なくとも１つの状態に入るときに、試験測定装置のメモリにパンくずリストを保存する処理と、保存されたパンくずリストを利用して、ステート・マシーンへのビット・ストリームの適用をフォロー（把握）する処理とを具える方法を含む。
【００７８】
以下の説明は、適切なマシーンの簡潔で一般的な説明の提供を意図するものであり、このマシーンにおいて、本発明のいくつかの側面を実現できる。典型的には、マシーンは、システム・バスを含み、これに、プロセッサ、メモリ、例えば、ランダム・アクセス・メモリ（ＲＡＭ）、リード・オンリー・メモリ（ＲＯＭ）、その他の状態保持メディア、ビデオ・インターフェース、そして、入力／出力インターフェース・ポートが取り付けられる。マシーンは、少なくとも一部分は、キーボード、マウスなどの従来の入力デバイスからの入力によって、制御されても良く、加えて、別のマシーンから受けた指示、バーチャル・リアリティ（ＶＲ）環境を用いるインタラクティブな処理、生体フィードバック、又は、他の入力信号によって制御されても良い。本願において、用語「マシーン（機械）」は、単一のマシーン、又は、通信可能に結合された一緒に動作する複数マシーン又は複数デバイスのシステムを広く包含するよう意図している。典型的なマシーンには、パソコン、ワークステーション、サーバ、ポータブル・コンピュータ、ハンドヘルド・デバイス、電話、タブレットなどのようコンピューティング・デバイスに加えて、例えば、自動車、電話、タクシーなどの私有又は公共の輸送機関のような輸送装置を含んでいる。
【００７９】
マシーンは、プログラマブル又はノン・プログラマブル・ロジック・デバイス又はアレー（ＦＰＧＡなど）、ＡＳＩＣ、組込み型コンピュータ、スマート・カードなどのような組込み型コントローラ（embedded controller）を含んで良い。マシーンは、ネットワーク・インターフェース、モデム、他の通信的な結合を介するなど、１つ以上の遠隔装置への１つ以上の接続を利用しても良い。複数のマシーンは、イントラネット、インターネット、ＬＡＮ、ＷＡＮなどのような物理的又は論理的なネットワークにより、相互接続されていても良い。当業者であれば、ネットワーク通信には、無線周波数（ＲＦ）、衛星、マイクロ波、ＩＥＥＥ810.11、Bluetooth（登録商標）、光通信、赤外線通信、ケーブル、レーザなどといった、有線又は無線の短距離、長距離のキャリアやプロトコルを用いて良いことが理解できよう。
【００８０】
発明は、マシーンがアクセスしたときに、マシーンがタスクを実行するか、又は、抽象データ形式又は低レベルのハードウェア状況を定義するという結果が得られる機能、手続、データ構造、アプリケーション・プログラムなどを含む関連データを参照するか又は連動して記述されても良い。関連データは、例えば、ＲＡＭ、ＲＯＭなどの揮発性及び／若しくは不揮発性メモリ、又は、ＨＤＤ、ＦＤ、オプティカル・ストレージ、テープ、フラッシュ・メモリ、メモリ・スティック、デジタル・ビデオ・ディスク、生体ストレージなどを含む他の記憶デバイス及びそれらに関連する記憶媒体に記憶しても良い。関連データは、物理的及び／又は論理ネットワークを含む伝送環境を通して、パケット、シリアル・データ、パラレル・データ、伝播信号などの形式で送ることができ、圧縮又は暗号フォーマットで利用されても良い。関連データは、分散型環境で利用され、マシーンがアクセスするローカル又は遠隔な場所に記録されても良い。
【００８１】
図示した実施形態を参照しながら、本発明の原理を説明及び図示してきたが、こうした原理から離れることなく、説明した実施形態を、構成や細部において変更しても良いことが理解できよう。先の説明では、特定の実施形態に絞って説明しているが、別の構成も考えられる。特に、「実施形態において」といった表現を本願では用いているが、こうした言い回しは、大まかに言って実施形態の可能性を意味し、特定の実施形態の構成に限定することを意図するものではない。本願で用いているように、これら用語は、別の実施形態に組み合わせ可能な同じ又は異なる実施形態に言及するものである。
【符号の説明】
【００８２】
４０５  試験測定装置
４１０  メモリ
４１５  ステート・マシーン
４２０  受信部
４３５  ビット・ストリーム
４４０  正規表現
４６５  パンくずリスト
４７０  分析部
４７５  パンくずリスト発生部
４８０  再現部
６０５  形式
６１０  ＩＤ
６１５  時間
【図１Ａ】
2016085745.tif 000003
【図１Ｂ】
2016085745.tif 000004
【図１Ｃ】
2016085745.tif 000005
【図２Ａ】
2016085745.tif 000006
【図２Ｂ】
2016085745.tif 000007
【図２Ｃ】
2016085745.tif 000008
【図２Ｄ】
2016085745.tif 000009
【図３Ａ】
2016085745.tif 000010
【図３Ｂ】
2016085745.tif 000011
【図４】
2016085745.tif 000012
【図５】
2016085745.tif 000013
【図６】
2016085745.tif 000014
【図７Ａ】
2016085745.tif 000015
【図７Ｂ】
2016085745.tif 000016
【図８】
2016085745.tif 000017
【図９】
2016085745.tif 000018
【図１０】
2016085745.tif 000019
【外国語明細書】
【発明の名称】System and method for analysis
【技術分野】
【０００１】
This invention relates to test-and-measurement instruments, and more particularly to ways to re-create the analysis of a bit stream in a test-and-measurement instrument.
【先行技術文献】
【特許文献】
【０００２】
【特許文献１】特表２００７−５２２４５３号公報
【特許文献２】米国特許第７７９７３４６号明細書
【特許文献３】特表２００４−５２３１６６号公報
【特許文献４】特開２００７−２８６０２５号公報
【特許文献５】米国特許第９０６９０１７号明細書
【特許文献６】特許第５６０５８４２号公報
【非特許文献】
【０００３】
【非特許文献１】「Breadcrumb (navigation)」の記事、Wikipedia（英語版）、［オンライン］、［２０１５年１０月２３日検索］、インターネット、<https://en.wikipedia.org/wiki/Breadcrumb_(navigation)>
【非特許文献２】「パンくずリスト」の記事、Wikipedia（日本語版）、［オンライン］、［２０１５年１０月２３日検索］、インターネット、<https://ja.wikipedia.org/wiki/パンくずリスト>
【発明の概要】
【発明が解決しようとする課題】
【０００４】
Real time analysis of signals has its place.  But sometimes, it is useful to re-create the operation of a test-and-measurement instrument on data after the fact, and more slowly, so that the details can be checked.  Currently, there is no way to do this analysis re-creation when analyzing data in a bit stream.
【０００５】
Embodiments of the invention address this and other problems with the prior art.
【課題を解決するための手段】
【０００６】
The present invention can be described from various concepts as below.
【０００７】
A concept 1 of the present invention is a system, comprising:
a test-and-measurement instrument;
a memory on the test-and-measurement instrument;
a receiver on the test-and-measurement instrument operative to receive a regular expression and a bit stream;
a state machine generator to generate a state machine from the regular expression;
an analyzer operative to analyze the bit stream using the state machine; and
a breadcrumb generator operative to generate and save in the memory a breadcrumb whenever a state in the state machine is entered.
【０００８】
A concept 2 of the present invention is a system according to the concept 1, wherein the breadcrumb generator is operative to generate a breadcrumb including at least one of a type, an ID, and a time.
【０００９】
A concept 3 of the present invention is a system according to the concept 1, wherein the breadcrumb generator is operative to generate and save in the memory a breadcrumb when an error state is entered on an unexpected input, the breadcrumb including at least one of a type, an ID, and a time.
【００１０】
A concept 4 of the present invention is a system according to the concept 1, further comprising a state machine optimizer operative to optimize the state machine.
【００１１】
A concept 5 of the present invention is a system according to the concept 1, further comprising a re-creator to re-create the operation of the state machine using the saved breadcrumbs.
【００１２】
A concept 6 of the present invention is a method, comprising:
receiving a regular expression at a test-and-measurement instrument;
generating a state machine from the regular expression;
applying the state machine to a bit stream; and
for at least one state in the state machine, saving a breadcrumb in a memory of the test-and-measurement instrument when the at least one state is entered.
【００１３】
A concept 7 of the present invention is a method according to the concept 6, wherein saving a breadcrumb in a memory of the test-and-measurement instrument when the at least one state is entered includes saving a breadcrumb in the memory of the test-and-measurement instrument as each state in the state machine is entered.
【００１４】
A concept 8 of the present invention is a method according to the concept 6, wherein saving a breadcrumb in a memory of the test-and-measurement instrument when the at least one state is entered includes saving the breadcrumb in the memory of the test-and-measurement instrument when the at least one state is entered, the breadcrumb including at least one of a type, an ID, and a time.
【００１５】
A concept 9 of the present invention is a method according to the concept 6, wherein saving a breadcrumb in a memory of the test-and-measurement instrument when the at least one state is entered includes saving an error breadcrumb in the memory of the test-and-measurement instrument when an error state is entered on an unexpected input, the breadcrumb including at least one of a type, an ID, and a time.
【００１６】
A concept 10 of the present invention is a method according to the concept 6, wherein generating a state machine from the regular expression includes optimizing the state machine.
【００１７】
A concept 11 of the present invention is a method according to the concept 6, further comprising using the saved breadcrumbs to follow the application of the bit stream to the state machine.
【図面の簡単な説明】
【００１８】
【図１Ａ】FIG. 1A shows an example of a protocol for matching a particular packet
【図１Ｂ】FIG. 1B shows a state machine that can match the packet of FIG. 1A.
【図１Ｃ】FIG. 1C shows a state machine that can trigger on a condition involving the data of the packet of FIG. 1A.
【図２Ａ】FIG. 2A shows a second example of a protocol for matching several packets.
【図２Ｂ】FIG. 2B shows an un-optimized state machine to match the packets of FIG. 2A.
【図２Ｃ】FIG. 2C shows an optimized state machine to match the packets of FIG. 2A.
【図２Ｄ】FIG. 2D shows a  state machine that can trigger on a condition involving the data of the packets of FIG. 2A.
【図３Ａ】FIG. 3A shows an example of the state machine of FIG. 1B modified to reflect compound trigger conditions.
【図３Ｂ】FIG. 3B shows another example of the state machine of FIG. 1B modified to reflect compound trigger conditions.
【図４】FIG. 4 shows a test-and-measurement instrument that can create and use the state machines of FIGs. 1B-1C and 2B-2D to trigger the test-and-measurement instrument when various trigger conditions are met, and to save breadcrumbs into memory reflecting the operation of the state machines of FIGs. 1B-1C and 2B-2D, according to an embodiment of the invention.
【図５】FIG. 5 shows more detail about the state machine modifier of FIG. 4.
【図６】FIG. 6 shows more detail about the breadcrumbs of FIG. 4.
【図７Ａ】FIG. 7A shows a portion of a flowchart of a procedure for creating a trigger state machine from a protocol and user configuration using the test-and-measurement instrument of FIG. 4, according to an embodiment of the invention.
【図７Ｂ】FIG. 7B shows a remaining portion of the flowchart of a procedure for creating a trigger state machine from a protocol and user configuration using the test-and-measurement instrument of FIG. 4, according to an embodiment of the invention.
【図８】FIG. 8 shows a flowchart of a procedure for creating a trigger state machine from a protocol and a compound trigger condition using the test-and-measurement instrument of FIG. 4, according to an embodiment of the invention.
【図９】FIG. 9 shows a flowchart of a procedure for optimizing a state machine using the test-and-measurement instrument of FIG. 4, according to an embodiment of the invention.
【図１０】FIG. 10 shows a flowchart of a procedure for using creating a state machine that can save breadcrumbs using the test-and-measurement instrument of FIG. 4, according to an embodiment of the invention.
【発明を実施するための形態】
【００１９】
Before explaining how the invention operates, it is useful to understand the relationship between regular expressions and state machines.  
【００２０】
Given a regular expression, a state machine can be constructed that represents that regular expression.  The state machine can then be used to determine whether a particular input matches the regular expression.  If the state machine processes to an acceptable end state, then the input matches the regular expression; otherwise, the input does not match the regular expression.
【００２１】
FIG. 1A shows an example of a protocol for a packet of data named “dataPacket”, expressed as a regular expression.  Protocol 105 describes a packet of data.  When a bit stream is compared against this regular expression, the system can determine if the packet is found within the bit stream.
【００２２】
FIG. 1B shows a state machine that corresponds to the regular expression of FIG. 1A.  State machine 110 includes states 115, 120, 125, 130, 135, 140, and 145, with transitions between these states.  Each state (which can also be called a node or vertex) describes what data needs to be matched to enter the state (the acceptance criterion).  Each arrow is a path that can be traversed provide the target acceptance criterion for the state is met.  Aside from start state 115 and success state 145, these states correspond sequentially to the data expected by the packet.  Thus, state 120 matches a state S within the bit stream, state 125 matches three bits of data against the field labeled “begin”, state 130 matches four bits of data against the field labeled “addr”, and so on.  Assuming that all the data can be matched by the states of state machine 110, when success state 145 is reached, the system can declare that the packet “dataPacket” has been successfully matched.
【００２３】
State machine 110 represents a simplified version of the actual state machine.  For example, state machine 110 does not label the transitions between the various states, nor does state machine 110 show error states or transitions that are used when data does not match what is expected.  A person skilled in the art would understand how state machine 110 operates, even without these details.
【００２４】
Formally, in mathematical terms, a state machine can be represented as a quintuple (Σ, S, s0, δ, F), where Σ is the alphabet (the set of symbols recognized by the state machine), S is the set of states in the state machine, s0 is the initial state, δ is the transition function, which maps from each state in S and each symbol in Σ to a state in S (which could be the same state as the input state), and F is the set of final states in S.  Thus, state machine 110 could be more formally represented as (Σ, S, s0, δ, F), where:
【００２５】
Σ = {S, 0, 1, …} (there could potentially be more symbols recognized than just the state S and binary values 0 and 1, even though these are the only symbols recognized by the state machine)
【００２６】
S = {110, 115, 120, 125, 130, 135, 140, 145}
【００２７】
s0 = 110
【００２８】
δ (δ is not expressed in more detail here because expressing the complete transition function would be very cumbersome and of little value)
【００２９】
F = {145}
【００３０】
In fact, this expression of state machine 110 is not necessarily complete.  Transitions typically occur on individual symbols, rather than groups of symbols.  Thus, transitioning from state 120 to 125 can actually involve three transitions (and therefore some intermediate states): one for each bit recognized for the field labeled “begin”.  But as a simplification, a person skilled in the art would understand how state machine 110 operates.
【００３１】
A user might want to trigger some process if a particular value is read for a given state in state machine 110.  For example, a user might want to trigger a process if the address field stores the value 10 (in binary, 1010; in hexadecimal, A).  FIG. 1C shows an example of how state machine 110 can be modified to implement this trigger.  In FIG. 1C, instead of matching against any possible value for the address field, state machine 150 compares the bit stream with the specific value 1010 (in state 155).  If that value is found, then at state 160, the trigger is considered satisfied, and the trigger causes the process to start (whatever that process might be).
【００３２】
Note that states 115 and 120 are the same in state machine 150 as in state machine 110: state 115 is a state in which the state machine starts, and state 120 matches state S from the bit stream.  But state 165 is different from state 125, in that state 165 does not care about the particular field being read.  Put another way, in state 165 all that matters is that three bits are read from the bit stream.  State 155 is also different from state 130, as state 155 is concerned only with matching the particular bit pattern 1010, rather than matching the address field (as in state 130).  Finally, once the user condition has been matched, no further matching needs to be done, so state machine 150 does not include analogs to states 135 and 140: the trigger can be issued immediately after the condition is met.
【００３３】
FIGs. 1A-1C show a fairly simple example of a regular expression, state machine to match the regular expression, and trigger state machine.  (Trigger state machines are sometimes referred to simply as “state machines”, but from context a person skilled in the art can determine if a particular state machine is a trigger state machine or a state machine to match a regular expression.)  FIGs 2A-2D show a more complicated example.  In FIG. 2A, regular expressions for three different packets are shown.  These regular expressions can be converted into a state machine, as shown in FIG. 2B.  Note that state machine 205 in FIG. 2B uses a single start state to cover all three possible protocols.
【００３４】
State machine 205 can be used as shown.  But using state machine 205 as shown would require look-ahead or backtracking, which requires additional memory and can slow down processing of a bit stream.  For example, assume that where multiple states can be reached given a particular input, the left-most (as FIG. 2B would be read by a person, rather than how a processor might use state machine 205).  For example, note that states 210, 215, and 220 all match Begin states, and states 225, 230, and 235 all match 4 bits as a slaveAddress field.  Using a left-most first approach, after reading a Begin state and 4 bits as the slaveAddress field, the system would be in state 225.  But if the next bit read would be a 0, then the system would be following the wrong branch of state machine 205, and would have to unwind the processing of state machine 205 to attempt to find the correct branch.  This is an example of backtracking.  It should be apparent that having to reverse state machine 205 and process a different branch can slow down processing of the bit stream.  Avoiding backtracking using state machine 205 would require look-ahead processing: the system would have to somehow look at bits yet to come in the bit stream.  Look-ahead is also complicated and expensive.
【００３５】
To avoid both backtracking and look-ahead, state machine 205 can be optimized.  State machine 240 in FIG. 2C shows an example of an optimized state machine.  With state machine 240, there is no need to look ahead, and no concern about backtracking.  Given any prefix (up to and including the entire packet) of any of the packets, there is only one possible path through state machine 240 that matches that prefix.  Therefore, there is no need to perform look-ahead, and no need to worry about backtracking: given a particular state in state machine 240 and a particular input symbol, there is only one possible state to transition to (this state might be an error state, not shown in FIG. 2C for simplicity).
【００３６】
Optimization can be accomplished using the following procedure.  Start by walking the tree from the start state and combining the nodes (that is, merge the nodes into a single node) that are equivalent and have the same parent.  This process can be repeated until there are no more like nodes to combine.  Then find the equivalent Success states, combine them, and then combine nodes that are equivalent and have the same children (again, repeating the process until there are no more like nodes to combine).
【００３７】
FIG. 2D shows an example of a particular trigger customized by the user.  In FIG. 2D, the user has selected to trigger when the address field (not the slaveAddress field) of a packet in the regular expression is set to the value 0.  Since this field does not appear in the packet Register0Write, this entire branch of the state machine can be eliminated from trigger state machine 245.  Any value can be matched against the slaveAddress field, after which the bits 0 and 1 must be matched.  Any bit can occur after that (although the actual bit would depend on the particular packet being read, trigger state machine 245 does not care which value is received), after which the bits for the address field are received, and can be compared with the value 0.  If the value 0 is matched for the address field, then trigger state machine 245 has succeeded, and the trigger can be initiated.
【００３８】
The above examples use a single trigger criterion, expressed as an equality.  But there is no reason to limit the trigger condition to an equality.  Aside from equality (==), examples of other trigger conditions can be inequality (!=), less than (<), less than or equal to (<=), greater than (>), or greater than or equal to (>=).  In addition, the trigger condition might depend on only a subset of information from the field in the regular expression.  For example, in FIG. 2D, the user might only be interested in whether the middle three bits of the address field are equal to 001: the first and last bit in the address field (which has a total of five bits) can match any value.  It is also possible to set a trigger condition that depends merely on reaching a particular state.  For example, the user might be interested in knowing when the address field is reached, regardless of its actual value.
【００３９】
In addition, trigger conditions do not have to be limited to a single criterion (which can be termed a simple trigger condition).  The user can specify multiple criteria (compound trigger conditions), combined using AND and OR operators, in any desired combination.  Thus, the state machine might be testing for multiple conditions, any of which might involve a set of sub-conditions, and so on.  A person skilled in the art would know how to simplify the user’s provided condition into disjunctive normal form or conjunctive normal form, as desired, which might simplify the design of the state machine.  (Disjunctive normal form refers to a logical formula expressed as a disjunction of conjunctive clauses: that is, an OR of ANDs.  Conjunctive normal form similarly describes an AND of ORs.)
【００４０】
FIGs. 3A-3B show examples of state machines with compound trigger conditions.  In FIG. 3A, the user has specified the trigger condition of (addr == 0xA && parity == 1).  Such a trigger condition is a conjunction of the two conditions.  Because the trigger condition requires that two states both have specified values, two states in the state machine are set to specific values (as specified by the user); the values for other states are generally not important, and can be combined into a single state.
【００４１】
In FIG. 3B, the user has specified a trigger condition of (addr == 0xA || parity == 1): a disjunctive trigger condition.  Because the trigger condition requires one of two states to have a specified value, two state machines, with the separate conditions, can be established and merged using the optimization techniques described earlier.  Note that even though the trigger condition applies to a single state machine, because of the disjunction, there are two possible paths to a successful trigger.
【００４２】
FIGs. 3A-3B give examples involving a single AND or OR combining two possible trigger values.  But it should be apparent that the process can be generalized for more complicated trigger conditions.  For example, if the trigger condition involves two values joined by an AND operation, or another value (an expression of the form ((X AND Y) OR Z), then the state machine can be copied.  One copy can be modified to reflect the first value of the AND operation; a second copy can be modified to reflect the second value of the AND operation; and the third copy can be modified to reflect the other value of the OR operation.  The first two state machines can then be combined and optimized as described above to represent the AND operation, and that state machine can then be combined and optimized with the third state machine to represent the compound trigger condition.
【００４３】
Now that trigger state machines have been described, a system that can use trigger state machines can be described.  FIG. 4 shows a test-and-measurement instrument that can create and use the state machines of FIGs. 1B-1C and 2B-2D to trigger the test-and-measurement instrument when various trigger conditions are met, according to an embodiment of the invention.  The system can include test-and-measurement instrument 405.  Test-and-measurement instrument can be any desired test-and-measurement instrument, such as an oscilloscope, among other possibilities.
【００４４】
Test-and-measurement instrument 405 can include memory 410.  Memory 410 can store information, such as state machine 415.  State machine 415 can be a state machine used to match a regular expression: in other words, a state machine such as state machines 110, 205, and 240 of FIGs. 1B, 2B, and 2C).  State machine 415 can also be a trigger state machine, such as state machines 150 and 245 of FIGs. 1C and 2D.
【００４５】
Test-and-measurement instrument 405 can also include receiver 420, which can receive input into test-and-measurement instrument 405.  Input can be received in any number of ways.  For example, receiver 420 can include a user interface for a user to input information, such as trigger condition 425, which itself can include, for example, user-selected value 430 for a particular bit field.  Or, receiver 420 can include receive a signal that includes a bit stream, such as bit stream 435, to be analyzed.  Receiver 420 can also receive regular expression 440 (for example, through an integrated development environment (IDE), which can identify the data the system should expect to receive in bit stream 435, and which can be used to construct state machine 415 (be it a state machine to recognize regular expression 440 or a trigger state machine).
【００４６】
Test-and-measurement instrument 405 can also include various other units.  State machine modifier 445 can take an existing state machine (for example, one that matches data to regular expression 440) and modifies it to operate as a trigger state machine.  As discussed above, this can include eliminating states that occur after the trigger condition is satisfied, and combining states whose values are not considered as part of the trigger condition, among other possibilities.
【００４７】
Processing engine 450 can process bit stream 435 using various state machines (including, for example, a state machine generated using regular expression 440 or a trigger state machine produced using state machine modifier 445).  This processing can include updating the current state for each various state machine, as bits are read from bit stream 435.
【００４８】
Trigger system 455 can send a trigger when the trigger condition is met (that is, when the trigger state machine is satisfied.  Trigger system 455 can send the trigger to any desired component of test-and-measurement instrument 405 to perform any action as a result of the trigger, as would be understood by person of ordinary skill in the art.
【００４９】
State machine generator 460 can generate a state machine from regular expression 440.  As discussed above, this can include creating a sequential series of states that match fields in the order presented in the regular expression.  This can also include combining various state machines that match different regular expressions into a single state machine, and optimizing a state machine to avoid look-ahead and backtracking problems.
【００５０】
Aside from generating and using trigger state machines, test-and-measurement instrument 405 can also be used to generate breadcrumbs (also called "breadcrumb list" or "breadcrumb navigation": see non-patent documents 1 and 2).  The term of "breadcrumbs" comes from the fairytale of Hansel and Gretel that they get on the trail of breadcrumbs.  Breadcrumbs let a user re-create the operation of a state machine, to see how data was processed.  Breadcrumbs, such as breadcrumb 465, are bits of data that can be stored in memory 410.  Essentially, whenever a state in a state machine is entered, a breadcrumb can be saved.  A breadcrumb can include data, such as the type of state (e.g., error state, packet start, packet end, or field), an ID for the state (that can identify the field or packet), and a time, such as the start and/or stop time of the data that caused the state entry.  A person skilled in the art will recognize that “time” does not have to refer to the literal concept of time (as in seconds or fractions thereof since the start of the signal), but rather can refer to an index into a signal, among other possibilities.  Breadcrumbs can also include additional data pertinent to analysis, as appropriate.  Therefore, the identification of the data to be included in the breadcrumbs can be user-customized.
【００５１】
Breadcrumbs are usually generated using a trigger state machine.  But a person skilled in the art will recognize that there is no reason why any other state machine cannot be used to generate breadcrumbs, and therefore breadcrumbs can be generated using any state machine.
【００５２】
To support breadcrumb generation, test-and-measurement instrument 405 can include analyzer 470.  Analyzer 470 can analyze bit stream 435 using a state machine.  In operation, analyzer 470 is similar to processing engine 450, but their objectives are different.  Whereas processing engine 450 is concerned with matching bits from bit stream 435 to attempt to recognize regular expressions, analyzer 470 is concerned with determining when to save a breadcrumb to memory 410.  Analyzer 470 and processing engine 450 also typically operate on different state machines: analyzer 470 usually uses (but does not have to use) a trigger state machine, whereas processor 450 uses a full state machine to match a regular expression.
【００５３】
Test-and-measurement instrument 405 can also include breadcrumb generator 475.  When it is time to generate a breadcrumb (e.g., when a new state is entered as determined by analyzer 470), breadcrumb generator 475 can save the breadcrumb to memory 410.
【００５４】
Finally, test-and-measurement instrument 405 can include re-creator 480.  Re-creator 480 permits a user to re-create the operation of the state machine (as processed by analyzer 470) on bit stream 435.  This re-creation enables the user to follow what happened.
【００５５】
Test-and-measurement instrument 405 as described can process either the trigger state machine or the breadcrumb generation, or both.  Some test-and-measurement instruments include the necessary hardware and/or software to process multiple state machines.  If a test-and-measurement instrument is capable of processing multiple state machines, then test-and-measurement instrument 405 can perform both processing for trigger conditions and breadcrumbs.
【００５６】
FIG. 5 shows more detail about the state machine modifier of FIG. 4.  In FIG. 5, state machine modifier 445 is shown as including state machine optimizer 505.  State machine optimizer 505 can optimize a state machine, as described above.  Such optimization can be either for a state machine designed to match a regular expression or for a trigger state machine.
【００５７】
FIG. 6 shows more detail about the breadcrumbs of FIG. 4.  In FIG. 6, breadcrumb 465 is shown as including type 605, ID 610, and time 615.  As discussed above, type 605 can specify the type of state which generated breadcrumb 465.  ID 610 can specify the specific state in the state machine that generated breadcrumb 465.  And time 615 can specify the time (or index) in the signal when the state generated breadcrumb 465.
【００５８】
FIGs. 7A-7B show a flowchart of a procedure for creating a trigger state machine from a protocol and user configuration using the test-and-measurement instrument of FIG. 4, according to an embodiment of the invention.  In FIG. 7A, at block 705, the system can receive a regular expression.  At block 710, the system can generate a state machine that corresponds to the regular expression.  At block 715, the system can optimize the state machine.
【００５９】
At block 720, the system can identify the state machine corresponding to a regular expression (which can be the same state machine generated in blocks 705-715).  At block 725, the system can receive a trigger condition from the user.  This can include, for example, a user-specified value (or part of a value) for a particular field in the regular expression, multiple such user-specified values, or even just a field to be reached, among other possibilities.  At block 730, the system can identify a state (or more than one state) in the state machine that can be modified to implement the trigger condition.
【００６０】
At block 735 (FIG. 7B), the system can modify the identified state(s) to compare with the user-selected value.  At block 740, the system can store the modified state machine.  At block 745, the system can receive a bit stream.  At block 750, the system can process the bit stream using the modified state machine.  At block 710, the system can determine if the trigger condition was met.  If so, then at block 755 the system can apply a triggering system.
【００６１】
As discussed above, a trigger condition can be a compound trigger condition.  In that case, the flowchart of the procedure can be modified to reflect the compound nature of the trigger condition.  FIG. 8 reflects this change.  FIG. 8 modifies blocks 730 and 735 of FIGs. 7A-7B: the other blocks in FIGs. 7A-7B are unmodified and therefore not shown in FIG. 8.
【００６２】
In FIG. 8, at block 805, the system identifies states that are implicated by the compound trigger condition.  The number of implicated states might be less than the number of simple conditions included in the compound trigger condition.  For example, a compound trigger condition for the state machine shown in FIG. 1B might be (addr == 0xA || addr == 0xF).  Note that the same state is used in both sides of the compound trigger condition.  At block 810, the system replicates the state machine once for each simple trigger condition in the compound trigger condition.  Continuing the above example, the compound trigger condition includes two simple trigger conditions (addr == 0xA and addr == 0xF), so the system would generate two replicas of the state machine.  At block 815, within each replicated state machine, an identified state is modified to reflect the comparison with the user-specified value.  Finally, at block 820, the modified replicated state machines can be combined to produce a single state machine that reflects the compound trigger condition.  At this point, processing can continue with block 740 of FIG. 7B.
【００６３】
FIG. 9 shows a flowchart of a procedure for optimizing a state machine using the test-and-measurement instrument of FIG. 4, according to an embodiment of the invention.  In FIG. 9, at block 905, the system can remove states that occur after the trigger condition is met.  At block 910, the system can merge adjacent states that can be satisfied by any value into a single state.
【００６４】
FIG. 10 shows a flowchart of a procedure for using creating a state machine that can save breadcrumbs using the test-and-measurement instrument of FIG. 4, according to an embodiment of the invention.  At block 1005, the system can receive a regular expression.  At block 1010 the system can generate a state machine from the regular expression.  At block 1015, the system can optimize the state machine.  At block 1020, the system can apply the state machine to a bit stream.  At block 1025, the system can save a breadcrumb whenever a state in the state machine is entered.  At block 1030, the system can use the saved breadcrumbs to re-create the application of the state machine to the bit stream.
【００６５】
The above flowcharts show some possible embodiments of the invention.  But other embodiments of the invention can organize the blocks in different arrangements, and can include or omit different blocks as desired, or repeat a block (or multiple blocks) as needed.  Embodiments of the invention are intended to include all such variations on the flowcharts.
【００６６】
Embodiments of the invention can extend to the following statements, without limitation:
【００６７】
An embodiment of the invention includes a system, comprising: a test-and-measurement instrument; a memory on the test-and-measurement instrument; a receiver on the test-and-measurement instrument operative to receive a regular expression and a bit stream; a state machine generator to generate a state machine from the regular expression; an analyzer operative to analyze the bit stream using the state machine; and a breadcrumb generator operative to generate and save in the memory a breadcrumb whenever a state in the state machine is entered.
【００６８】
An embodiment of the invention includes a system, comprising: a test-and-measurement instrument; a memory on the test-and-measurement instrument; a receiver on the test-and-measurement instrument operative to receive a regular expression and a bit stream; a state machine generator to generate a state machine from the regular expression; an analyzer operative to analyze the bit stream using the state machine; and a breadcrumb generator operative to generate and save in the memory a breadcrumb whenever a state in the state machine is entered, wherein the breadcrumb generator is operative to generate a breadcrumb including at least one of a type, an ID, and a time.
【００６９】
An embodiment of the invention includes a system, comprising: a test-and-measurement instrument; a memory on the test-and-measurement instrument; a receiver on the test-and-measurement instrument operative to receive a regular expression and a bit stream; a state machine generator to generate a state machine from the regular expression; an analyzer operative to analyze the bit stream using the state machine; and a breadcrumb generator operative to generate and save in the memory a breadcrumb whenever a state in the state machine is entered, wherein the breadcrumb generator is operative to generate and save in the memory a breadcrumb when an error state is entered on an unexpected input, the breadcrumb including at least one of a type, an ID, and a time.
【００７０】
An embodiment of the invention includes a system, comprising: a test-and-measurement instrument; a memory on the test-and-measurement instrument; a receiver on the test-and-measurement instrument operative to receive a regular expression and a bit stream; a state machine generator to generate a state machine from the regular expression; a state machine optimizer operative to optimize the state machine; an analyzer operative to analyze the bit stream using the optimized state machine; and a breadcrumb generator operative to generate and save in the memory a breadcrumb whenever a state in the optimized state machine is entered.
【００７１】
An embodiment of the invention includes a system, comprising: a test-and-measurement instrument; a memory on the test-and-measurement instrument; a receiver on the test-and-measurement instrument operative to receive a regular expression and a bit stream; a state machine generator to generate a state machine from the regular expression; an analyzer operative to analyze the bit stream using the state machine; a breadcrumb generator operative to generate and save in the memory a breadcrumb whenever a state in the state machine is entered; and a re-creator to re-create the operation of the state machine using the saved breadcrumbs.
【００７２】
An embodiment of the invention includes a method, comprising: receiving a regular expression at a test-and-measurement instrument; generating a state machine from the regular expression; applying the state machine to a bit stream; and for at least one state in the state machine, saving a breadcrumb in a memory of the test-and-measurement instrument when the at least one state is entered.
【００７３】
An embodiment of the invention includes a method, comprising: receiving a regular expression at a test-and-measurement instrument; generating a state machine from the regular expression; applying the state machine to a bit stream; and for at least one state in the state machine, saving a breadcrumb in a memory of the test-and-measurement instrument when the at least one state is entered, including saving a breadcrumb in the memory of the test-and-measurement instrument as each state in the state machine is entered.
【００７４】
An embodiment of the invention includes a method, comprising: receiving a regular expression at a test-and-measurement instrument; generating a state machine from the regular expression; applying the state machine to a bit stream; and for at least one state in the state machine, saving a breadcrumb in a memory of the test-and-measurement instrument when the at least one state is entered, including saving the breadcrumb in the memory of the test-and-measurement instrument when the at least one state is entered, the breadcrumb including at least one of a type, an ID, and a time.
【００７５】
An embodiment of the invention includes a method, comprising: receiving a regular expression at a test-and-measurement instrument; generating a state machine from the regular expression; applying the state machine to a bit stream; and for at least one state in the state machine, saving a breadcrumb in a memory of the test-and-measurement instrument when the at least one state is entered, including saving an error breadcrumb in the memory of the test-and-measurement instrument when an error state is entered on an unexpected input, the breadcrumb including at least one of a type, an ID, and a time.
【００７６】
An embodiment of the invention includes a method, comprising: receiving a regular expression at a test-and-measurement instrument; generating a state machine from the regular expression; optimizing the state machine; applying the optimized state machine to a bit stream; and for at least one state in the optimized state machine, saving a breadcrumb in a memory of the test-and-measurement instrument when the at least one state is entered.
【００７７】
An embodiment of the invention includes a method, comprising: receiving a regular expression at a test-and-measurement instrument; generating a state machine from the regular expression; applying the state machine to a bit stream; for at least one state in the state machine, saving a breadcrumb in a memory of the test-and-measurement instrument when the at least one state is entered; and using the saved breadcrumbs to follow the application of the bit stream to the state machine.
【００７８】
The following discussion is intended to provide a brief, general description of a suitable machine in which certain aspects of the invention may be implemented.  Typically, the machine includes a system bus to which is attached processors, memory, e.g., random access memory (RAM), read-only memory (ROM), or other state preserving medium, storage devices, a video interface, and input/output interface ports.  The machine may be controlled, at least in part, by input from conventional input devices, such as keyboards, mice, etc., as well as by directives received from another machine, interaction with a virtual reality (VR) environment, biometric feedback, or other input signal.  As used herein, the term “machine” is intended to broadly encompass a single machine, or a system of communicatively coupled machines or devices operating together.  Exemplary machines include computing devices such as personal computers, workstations, servers, portable computers, handheld devices, telephones, tablets, etc., as well as transportation devices, such as private or public transportation, e.g., automobiles, trains, cabs, etc.
【００７９】
The machine may include embedded controllers, such as programmable or non-programmable logic devices or arrays, ASICs, embedded computers, smart cards, and the like.  The machine may utilize one or more connections to one or more remote machines, such as through a network interface, modem, or other communicative coupling.  Machines may be interconnected by way of a physical and/or logical network, such as an intranet, the Internet, local area networks, wide area networks, etc.  One skilled in the art will appreciated that network communication may utilize various wired and/or wireless short range or long range carriers and protocols, including radio frequency (RF), satellite, microwave, Institute of Electrical and Electronics Engineers (IEEE) 810.11, Bluetooth (Registered Trademark), optical, infrared, cable, laser, etc.
【００８０】
The invention may be described by reference to or in conjunction with associated data including functions, procedures, data structures, application programs, etc. which when accessed by a machine results in the machine performing tasks or defining abstract data types or low-level hardware contexts.  Associated data may be stored on tangible computer-readable media as non-transitory computer-executable instructions.  Associated data may be stored in, for example, the volatile and/or non-volatile memory, e.g., RAM, ROM, etc., or in other storage devices and their associated storage media, including HDD, FD, optical storage, tapes, flash memory, memory sticks, digital video disks, biological storage, etc.  Associated data may be delivered over transmission environments, including the physical and/or logical network, in the form of packets, serial data, parallel data, propagated signals, etc., and may be used in a compressed or encrypted format.  Associated data may be used in a distributed environment, and stored locally and/or remotely for machine access.
【００８１】
Having described and illustrated the principles of the invention with reference to illustrated embodiments, it will be recognized that the illustrated embodiments may be modified in arrangement and detail without departing from such principles.  And, though the foregoing discussion has focused on particular embodiments, other configurations are contemplated.  In particular, even though expressions such as “in one embodiment” or the like are used herein, these phrases are meant to generally reference embodiment possibilities, and are not intended to limit the invention to particular embodiment configurations.  As used herein, these terms may reference the same or different embodiments that are combinable into other embodiments.
【符号の説明】
【００８２】
405  test and measurement instrument
410  memory
415  state machine
420  receiver
435  bit stream
440  regular expression
465  breadcrumb
470  analyzer
475  breadcrumb generator
480  Re-creator
605  type
610  ID
615  time
【請求項１】
A system for analysis, comprising:
a test-and-measurement instrument;
a memory on the test-and-measurement instrument;
a receiver on the test-and-measurement instrument operative to receive a regular expression and a bit stream;
a state machine generator to generate a state machine from the regular expression;
an analyzer operative to analyze the bit stream using the state machine; and
a breadcrumb generator operative to generate and save in the memory a breadcrumb whenever a state in the state machine is entered.
【請求項２】
A system for analysis according to claim 1, wherein the breadcrumb generator is operative to generate and save in the memory a breadcrumb when an error state is entered on an unexpected input, the breadcrumb including at least one of a type, an ID, and a time.
【請求項３】
A method for analysis, comprising:
receiving a regular expression at a test-and-measurement instrument;
generating a state machine from the regular expression;
applying the state machine to a bit stream; and
for at least one state in the state machine, saving a breadcrumb in a memory of the test-and-measurement instrument when the at least one state is entered.
【請求項４】
A method for analysis according to claim 3, wherein saving a breadcrumb in a memory of the test-and-measurement instrument when the at least one state is entered includes saving an error breadcrumb in the memory of the test-and-measurement instrument when an error state is entered on an unexpected input, the breadcrumb including at least one of a type, an ID, and a time.
【要約】
【課題】 Re-create analysis for data in a bit stream after the fact.
【解決手段】 A test-and-measurement instrument 405 can store a state machine 415.  As the state machine 415 is used to analyze a bit stream 435, breadcrumbs 465 can be saved from states in a memory 410 of the state machine.  The breadcrumbs 465 can then be used to analyze the operation of the state machine 415.
【選択図】図４
【図１Ａ】
2016085745.tif 000020
【図１Ｂ】
2016085745.tif 000021
【図１Ｃ】
2016085745.tif 000022
【図２Ａ】
2016085745.tif 000023
【図２Ｂ】
2016085745.tif 000024
【図２Ｃ】
2016085745.tif 000025
【図２Ｄ】
2016085745.tif 000026
【図３Ａ】
2016085745.tif 000027
【図３Ｂ】
2016085745.tif 000028
【図４】
2016085745.tif 000029
【図５】
2016085745.tif 000030
【図６】
2016085745.tif 000031
【図７Ａ】
2016085745.tif 000032
【図７Ｂ】
2016085745.tif 000033
【図８】
2016085745.tif 000034
【図９】
2016085745.tif 000035
【図１０】
2016085745.tif 000036