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 ?


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

  • $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Jul 27 '12 at 21:35

Graph theory and trellis graphs are related, for example, in Chapter 2 of this MSc. Thesis, M. Stylianou, Evaluating the Network Survivability issue of K-best Paths through Graph Theoretic Techniques, Univ. Cyprus, June, 2005.

Another interesting work is S.D. Nikolopoulos, Addressing network survivability issues by finding the K-best paths through a trellis graph, Proc. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies - INFOCOM '97, IEEE, Vol.1, pp. 370-377, 1997.

From the abstract,

*In this paper we aim to offer a solution in the selection of the K-best disjoint paths through a network by using graph theoretic techniques. The basic approach is to map an arbitrary network graph into a trellis graph which allows the application of computationally efficient methods to find disjoint paths. *

In the Appendix, the author presents an algorithm named Net-to-Trellis ...with a help of an example the processes of transforming a network G(V,E, c) into a A trellis graph. ...

  • $\begingroup$ Thanks for the answer ! Some problem with link on "thesis" :( $\endgroup$ – Alexander Chervov Jul 28 '12 at 9:34
  • $\begingroup$ Sorry. Corrected. $\endgroup$ – Papiro Jul 28 '12 at 10:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.