where u=(01.2m-1 We now describe the MAP algorithm in detail by using the trellis diagram.For no loss of generality of the result we assume that the trellis diagram contains parallel transitions.Refer to Fig.5.9.2.Denote by S the set of encoder states and by M=the number of states.In Fig.5.9.2=4 is assumed.Let S be the encoder state at time k.A branch at the kth section in the corresponding trellis diagram can be specified by b=(SS),where ug and x are the information and modulated symbols associated with the state transition SS Denote by B.(s',s)the set of all the parallel branches connecting S=s'es and S=sES.The non-binary MAP algorithm can be derived as follows. ① ① ② ② ② ② ③ 3) +③ y y Figure5.9.2 Pa=)Pu=S=8=） A,5=功 (5.9.1) p(y) where B is the set of transitions SS that are caused by the input ui.According to the BCJR algorithm,the probabilities p(.=s'S=s.y)can be calculated as p(u=1,S1=S',S=3,y)=4-(s)y(s',s)B(g) where2 where {0,1,.,2 1} m U = − . We now describe the MAP algorithm in detail by using the trellis diagram. For no loss of generality of the result, we assume that the trellis diagram contains parallel transitions. Refer to Fig. 5.9.2. Denote by S the set of encoder states and by M = |S| the number of states. In Fig.5.9.2 |S|=4 is assumed. Let k S be the encoder state at time k. A branch at the kth section in the corresponding trellis diagram can be specified by 1 ( ,) k kkk b S uxS ≡ − , where uk and k x are the information and modulated symbols associated with the state transition k k 1 S S − → . Denote by ( ', ) Bk s s the set of all the parallel branches connecting 1 ' k S s − = ∈S and k S s = ∈S . The non-binary MAP algorithm can be derived as follows. 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 uk /xk Sk-1 S S k 0 SN yk 1 1 k − y 1 N k+ y Figure 5.9.2 ( 1 11 ) ( ) ( ', ) | , ', | i k N N k kk k ss B Pu i Pu iS s S s − ∀ ∈ = = = == y y ∑ 1 1 ( ', ) 1 ( , ', , ) i ( ) k N kk k N ss B pu iS s S s p − ∀ ∈ = == = ∑ y y (5.9.1) where i Bk is the set of transitions S S k k −1 → that are caused by the input uk=i. According to the BCJR algorithm, the probabilities 1 1 ( , ', , ) N kk k pu iS s S s = == − y can be calculated as 1 1 ( , ', , ) N kk k pu iS s S s = == − y 1( ') ( ', ) ( ) i kk k αγ β s ss s =⋅⋅ − where