Tail-BitingTrellis Realizations for Block Codes

This award will support research aimed at deepening our understanding of graphical representations of block codes. Such representations play a fundamental role in modern coding theory, where codes on graphs are used in order to employ iterative decoding algorithms. The powerful performance of these algorithms has led to a vivid interest in optimal graphical representations of codes. Tail-biting trellises form a particular type of such graphical models. This project focuses on studying the relation between various tail-biting trellis realizations of a given code, such as minimal realizations and irreducible ones, as well as on analyzing the performance of iterative decoding algorithms on these graphs. Coding theory is at the interface of applied mathematics and engineering of communi- cation systems. It deals with ensuring the integrity of data transmission via satellite, internet, cell phones etc. The basic idea is to preprocess the to-be-sent messages in such a way that, after sending, the receiver has a good chance to recover the original mes- sage from the received, and generally erroneous, message. The preprocessing is called the encoding, and the recovering process is the decoding. This award will support research geared toward optimal graphical representations of codes, which in turn is closely related to designing ecient decoding algorithms. The award will also support the graduate pro- gram at the University of Kentucky because two Ph.D. students will be involved in the project.