trellis diagram (トレリス・ダイアグラム)

デジタル変調解析測定に関する翻訳で、trellis diagram (トレリス・ダイアグラム)という言葉が出てくる(例えば、VXAベクトル信号解析Xシリーズ測定アプリケーション N9064A/W9064Aのp6)。trellis diagramは、トレリス線図とも訳される。

トレリス・ダイアグラムとは、状態遷移図の状態の遷移の様子を時間を追って見やすくしたものである。

状態遷移図とは、ある状態にある入力値を与えると、どのような状態に遷移するかを表したものである。状態は、平面内に状態を区別する記号を丸(あるいは長方形)で囲ったもので表わす。これらの状態間の遷移は、入力値の付いた矢印で表す(例えば、入力が1のときに状態Aから状態Bに遷移し、入力が0のときに状態Aから状態Aに遷移する(すなわち、入力が0のときは何もしない)場合は、状態Aから状態Bに入力値1の付いた矢印で結び、状態Aから状態Aに(すなわち、自分自身を)入力値0の付いた矢印で結ぶ)。ソフトウェアのアルゴリズムをこのように表現することにより、全体の挙動が視覚的にわかりやすくなり、バグや不具合の発見を迅速に行える。

しかし、状態遷移図では、状態を平面内の任意の場所に配置して表すので、状態の時系列変化を調べる場合は分かり難い。そこで、行列の列(縦)方向に取り得る状態を並べ、行(横)方向で時間の経過を表わして、状態間の遷移を単位時間毎に右から左に入力値の付いた矢印で結んでいくことにより、状態の遷移の様子を時間を追って見やすくしたものがトレリス・ダイアグラム(格子状の図になることからtrellisと呼ばれる)である。

状態遷移図の簡単な説明については、以下を参照。

ソフトウェア開発技術者試験対策(1) -オートマトンを考える-

トレリス・ダイアグラムについては、以下を参照。

Encoding/Decoding – Presentation of Convolutional Code(英語ページ)の「Trellis Diagram」の項

コメントは受け付けていません。