Soft decision decoding of error-correcting codes is a standard procedure in telecommunication systems. The most used and studied way of performing soft-decision decoding is via trellis. The advantage of the trellis representation is a possibility of performing maximum likelihood or maximum a posteriori probability decoding using trellis oriented algorithms. It is crucial to select the proper trellis in order to minimize a decoding complexity. Nevertheless, it is important to differentiate between the problem of minimizing the combinatorial complexity of the trellis representation of the code, and the problem of minimizing the decoding complexity. Minimizing the combinatorial complexity, i.e. finding the edge-minimal trellis representation of the code, is a well-defined problem, which should be thought of as the necessary first step in minimizing the decoding complexity, which is much less defined.

In this talk we show that theory of trellis representation of convolutional codes, which is based on canonical D-description, is not complete. Particularly, we will show that rate R=k/n convolutional codes based on the realization as a linear sequential circuit with k-inputs and one-output have trellises that can provide smaller decoding complexity than conventional encoders created in the framework of the classical D-description. Also we give new formulations of algorithms for maximum likelihood and maximum a posteriori probability decoding. Decoding trellises based on the proposed algorithms are introduced with the corresponding modification of the Viterbi and MAP algorithms. The proposed algorithms provide the smallest complexity of the maximum-likelihood and maximum a posteriori probability trellis decoding among known. Finally, the challenges and unsolved problem are discussed.

Alexander Geyer received his engineering degree and Ph.D. from the Odessa National Academy of Telecommunication (ONAT) in 1980 and 1989, respectively. He was with Telecommunication Laboratory of Volgograd Regional Communication Department (Russia) (1980-83). He was researcher of the Communication Laboratory (1983-89), assistant/ associate professor and Head of the Department at the ONAT (1993-02) and senior researcher of the Satellite Communication department at the Ukrainian Radio and TV Re-search Institute (1994-01). He was research professor at the Telecommunication Research Centre of Catalonia (Barcelona) in 2003-04.

He is a corresponding Member of the Communication Academy of Ukraine. He was awarded by research grants of the German Academic Exchange Service (DAAD), Deutsche Forschungsgemeinschaft (DFG) and Spanish Ministry of Education and Science in 2000, 2001 and 2003, respectively. He has published more than 50 journal and conference papers and coauthored a textbook.