# “Trellis graph” is it standard term in graph theory ? What are its properties ?

In coding theory (convolutional codes) the graph called "trellis diagramm" is used to visualize something.

I wonder is it a standard term in graph theory? Corresponding Wikipedia article is not convincing.

If it is well-known graph - what are its properties (chromatic polynom, spectrum, etc...) ? What is known about it ? What are the references ?

PS

Let me remind definition of trellis graph - it depends on alphabet say {0,1} and on two integers "k" (state number = (alphabet size)^p for some "p") and "n".

The graph have k*n vertexes. Each of vertexes corresponds to words in the alphabet of lenth "p". Say p=2, we have 4 words

00 00 ........ 00

01 01 ........ 01

10 10 ........ 10

11 11 ........ 11

This words are copied "n" times. Now we have (alphabet size) size of edges going from each vertex. They connect the words X and Y if X stands in l-th column and Y in (l+1) copy and Y can be obtained by adding 1 symbol to word "X" from the left, and deleting the rightest symbol in X.

E.g. X = 00 will be connected with Y=00 and Y=10

• IIRC David Forney was the first to draw these graphs in order to make the correctness of the Viterbi decoding algorithm clear to all and sundry. He also coined the term "trellis". At least that's the way the history was once told to me by another big name in coding theory. – Jyrki Lahtonen Jul 27 '12 at 21:35