Convolutional code trellis diagram

A trellis is a graph whose nodes are ordered into vertical slices (time) with every node at almost every time connected to at least one node at an earlier and at least one node at a later time. The earliest and latest times in the trellis have only one node (hence the "almost" in the preceding sentence).

Trellises are used in encoders and decoders for communication theory and encryption. They are also the central datatype used in Baum–Welch algorithm or the Viterbi Algorithm[1] for Hidden Markov Models.

The trellis graph is named for its similar appearance to an architectural trellis.

References

edit
  1. ^ Ryan, M. S., & Nudd, G. R. (1993). The viterbi algorithm. University of Warwick, Department of Computer Science.

See also

edit


Stub icon

This graph theory-related article is a stub. You can help Wikipedia by adding missing information.

Stub icon

This article related to telecommunications is a stub. You can help Wikipedia by adding missing information.

📚 Artikel Terkait di Wikipedia

Trellis

(especially vineyards) Trellis drainage pattern, a drainage system Trellis (graph), a special kind of graph used in computer science Trellis chart, a series

List of graph theory topics

Split graph String graph Strongly regular graph Threshold graph Total graph Tree (graph theory). Trellis (graph) Turán graph Ultrahomogeneous graph Vertex-transitive

Small multiple

small multiple (sometimes called trellis chart, lattice chart, grid chart, or panel chart) is a series of similar graphs or charts using the same scale

Convolutional code

of the convolutional codes facilitates trellis decoding using a time-invariant trellis. Time invariant trellis decoding allows convolutional codes to

List of algorithms

algorithm for constructing maximum-cardinality matching on graphs. Coloring algorithm: algorithms for graph (vertex or edge) coloring (subject to constraints,

Reactive programming

a data flow graph to be constructed. Reactive programming libraries for dynamic languages (such as the Lisp "Cells" and Python "Trellis" libraries) can

Lattice

over a ring that is embedded in a vector space over a field Lattice graph, a graph that can be drawn within a repeating arrangement of points Lattice-based

Viterbi algorithm

can be visualized by means of a trellis diagram. The Viterbi path is essentially the shortest path through this trellis. A generalization of the Viterbi