Hypertrellis: A Generalization of Trellis and Factor Graph

摘要: Factor graphs have recently been introduced as an efficient graphical model for codes to study iterative decoding algorithms. However, it is well-known that a factor graph generalizes only the time axis of trellis, but omits state transition representation. In this paper, new model, called hypertrellis, proposed overcome insufficiency graphs. A hypertrellis in essence weighted hypergraph generalization traditional trellis. Its topology, which extends can take form any graph. key extension interpretation hypergraph. This facilitated by introducing “starfish” drawing representation hypergraphs, enhances applicability models enabling simpler and easier visualization, relative The maximum likelihood (MLD) problem then formulated shortest hyperpath search on hypertrellis. For hypertrellises with acyclic hyperpath-oriented MLD algorithm, one-way introduced. celebrated Viterbi provides insights into management surviving history various practical simplifications. It shown algorithm has lower minimal delay. computational complexity amount storage needed are also bett er than min-sum algorithm. Some connections between another bipartite trellis formation, discussed.