# What are trellis?

I hear the term trellis used in many contexts (trellis codes, trellis graphs, etc). From what I gathered from reading online resources, it seems that it's just a constraint graph that connects nodes from different points in time. However, I still do not have a strong grasp of "trellis." Can someone elaborate? My background is computer science and not digital signal processing. Hence, I'm having a little trouble wrapping my mind around this.

• I've seen some really awesome answers here which could easily have become a chapter in a good textbook – however, I don't think as askers, we should be expecting such broadths from answers (that's really a matter of even finding someone with enough time to write such an answer). I'd strongly recommend Proakis – Digital Communications (3rd ed, it's what I have at my private bookshelf next to my bed, can be had for <10$used online), which is a standard textbook and really clarified for me how to go from full state diagram to trellis in short. Apr 3 '17 at 8:27 • I think this gives a good overview: site.iugaza.edu.ps/ahdrouss/files/2011/03/… perhaps you could look at that or Marcus' reference above and then ask us pointed questions as to where you are having trouble. Apr 3 '17 at 10:41 • An additional comment to help get you started: a trellis is a specification for a state machine (just like the state diagram), but that emphasizes the temporal dimension. So, using a trellis you can easily describe or visualize how the state machine evolves over time. – MBaz Apr 3 '17 at 13:20 • Thanks for all the good resources. I will look into them! Apr 3 '17 at 19:33 ## 2 Answers For computer scientists, I recommend Chapter 24 (Trellis Structure of Codes by Alexander Vardy) in The Handbook of Coding Theory, V. Pless and W. C. Huffman (eds) published by Elsevier. It is unfortunately not available on line and is expensive, but your library might well have a copy. For example, with$V$denoting the set of vertices of a graph,$A$a set of edge labels, and$E = \{(v,v^\prime,a)\colon V, v\prime \in V, a \in A\}$the set of directed edges that begin at$v$, end at$v^\prime$,and have label$a$, Vardy defines a trellis as follows: A trellis$T=(V,E,A)$of depth$n$is an edge-labeled directed graph with the following property: the vertex set$V$can be decomposed as a union of disjoint subsets $$V = V_0 \cup V_1 \cup \cdots \cup V_n$$ such that every edge in$T$that begins at a vertex in$V_i$ends at a vertex in$V_{i+1}$and every vertex in$T$lies on at least one path from a vertex in$V_0$to a vertex in$V_n\$.

The definition (as well as most of the article) is in language that should be familiar to computer scientists though it may strike terror in the hearts of dsp.SE readers who are unused to such formalism.

• Nice :) I think that's the book "our" (EE) coding guys recommend to mathematicians on the topic. Uni library has it on the math racks, along with all the more basic but still applied algebra on the same shelves Apr 4 '17 at 8:53
• @MarcusMüller Thanks. Unfortunately, there is another reader who has found this answer to be so useless than s/he felt compelled to down vote it without leaving a comment. Apr 4 '17 at 14:09
• I'm afraid such is life... I'm not telling you something new, considering you've been around for much longer that I have, you can't make everyone happy. Don't let it get to you! Apr 4 '17 at 14:17
• @MarcusMüller Oh,I am used to it. I find that there is an interesting difference between dsp,SE and stats.SE which also has a lot of "drive-by" shootings except that stats.SE readers are generous with up votes while dsp.SE readers are generous with down votes. Go figure.... Apr 4 '17 at 14:46
• I downvoted your original answer before editing to add a description because the first version was: "For computer scientists, I recommend Chapter 24 (Trellis Structure of Codes by Alexander Vardy) in The Handbook of Coding Theory, V. Pless and W. C. Huffman (eds) published by Elsevier. It is unfortunately not available on line and is expensive, but your library might well have a copy." which is not a helpful answer! Apr 4 '17 at 15:06

Might help to know that this is a trellis:

• There is an old joke that you can tell a person's profession by asking them to sketch a tree. A botanist has the root at the bottom with branches and leaves growing upwards; a computer scientist has the root at the top and branches and leaves go downwards; and a coding theorist has the root on the left and the branches and leaves growing rightwards. To that we should add the distinction between how a horticulturalist sketches a trellis and how a coding theorist sketches one! Apr 4 '17 at 14:07
• I swear it was horizontal in the upload preview, but I'm glad it's upright now. Apr 4 '17 at 21:08
• Heh, heh! You gardener you! Apr 4 '17 at 21:24