0122229现代数字通信与编码理论 December 10,2011 XDU,Winter 2011 Lecture Notes Capacity-Approaching Coded-Modulation Schemes 5.9级联TCM TCM码可以按Tubo方式并行级联，也可以与其它码构成串行级联系统（例如，在 RS+TCM中做内码，在TCM+STBC中做外码)。 5.9.1TCM码的Symbol-Based Nonbinary)MAP译码算法 Consider a general trellis code.Let u=()be an information symbol sequence of length N.Each information symbol is assumed to be a binary m-tuple,i.e. =)"for =1.2.N.For convenience,we will denote u by its decimal representation,ie.,assume=,."-1.The m-bit symbols are fed into a TCM encoder,producing a sequence of N modulated symbols,x=(x),where xwithstanding for the signal constellation of size2".We assume that the symbols xx are transmitted over an AWGN channel.Let y=y=(y.y.)be the received sequence,where y(k=1,2.N)is the noisy observation of x if x is not punctured;otherwise,sety=*(implying no observation obtained). TCM yk Channel Symbol-based encoder MAP decoder Figure 5.9.1Atrellis coding system The received sequence is fed to the TCM decoder to produce the estimate of transmitted 2-ary information symbols.To minimize the probability of symbol errors,the symbol-based MAP decoder may be used.This decoder computes the APP for every 2"-ary information symbol;i.e.,P(=iy),for i=0,1,."-1,k=1,2.N Then it makes decisions according to the MAP criterion: ig =argmax P(u =ily
1 0122229 现代数字通信与编码理论 December 10, 2011 XDU, Winter 2011 Lecture Notes Capacity-Approaching Coded-Modulation Schemes 5.9 级联 TCM TCM 码可以按 Turbo 方式并行级联，也可以与其它码构成串行级联系统（例如，在 RS+TCM 中做内码，在 TCM+STBC 中做外码）。 5.9.1 TCM 码的(Symbol-Based Nonbinary) MAP 译码算法 Consider a general trellis code. Let u uu u = ( 1 2 , ,., N ) be an information symbol sequence of length N. Each information symbol is assumed to be a binary m-tuple, i.e., ( ) ,0 ,1 , 1 2 , ,., m k k k km uu u u = ∈ − F , for k=1,2,.N. For convenience, we will denote uk by its decimal representation; i.e., assume {0,1,.,2 1} m k u ∈ U = − . The m-bit symbols are fed into a TCM encoder, producing a sequence of N modulated symbols, ( ) 1 2 , ,., N x = x x x , where k x ∈X with X standing for the signal constellation of size | | 2n X = . We assume that the symbols xk are transmitted over an AWGN channel. Let 1 12 ( , ,., ) N N y y = = yy y be the received sequence, where k y (k=1,2,.N) is the noisy observation of k x if k x is not punctured; otherwise, set yk = ∗ (implying no observation obtained). ˆk u Figure 5.9.1 A trellis coding system The received sequence is fed to the TCM decoder to produce the estimate of transmitted 2m-ary information symbols. To minimize the probability of symbol errors, the symbol-based MAP decoder may be used. This decoder computes the APP for every 2m-ary information symbol; i.e., ( ) 1 | , for 0,1,.,2 1, 1,2,., N m Pu i i k N k = = −= y . Then it makes decisions according to the MAP criterion: ˆ arg max | ( 1 ) N k k i u Pu i ∈ = = y U
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) where
2 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
a(s)=p(S=s.y)is the forward state metric. B(s)=p(y=s)is the backward state metric;and (s',s)=p(ug=i.S.=s.yS=s')is the metric of the trellis branch b connecting S=s'to S=s with us=i. Note that we do not necessarily need the exact values of P(=ily,but only their ratios. Since for a fixedk,the vector P(y),being a probability vector,must sum to unity, thus by normalizing the sum to unity,we can omit the constant factor p(y in (5.9.1)and use the following simplified expression P(u =ily)>a(s)-n(s'.s)B(s) ( Now we consider the calculation of the branch metric(s's),which is the key point of the symbol-based MAP algorithm,and is also the primary difference between the MAP algorithm for binary turbo codes and the algorithm under consideration. Using Bayes'rule,the term(s'.s)can be written as (s',s)=pyS=3,S-1=S',4=)PS=sS=',4=)P(u=iS-=s) =p(yx)P(u=i)-P(S.=sIS=s'.u=i) (5.9.2) where p()is the probability of receivingy given the transmitted symbol x P() is the a priori probability of ug=i,and P(S=sS=s',=i)is 1 or 0,indicating whether or not a state transition SS with input=i exists.Thus,for a trellis branch b,we have 2s,=P4), ify=* x)P(u). (5.9.3) otherwise Define r(s,s)=p(S=s,yIS-=s) 3
3 α k k k () ( , ) s pS s ≡ = y1 is the forward state metric; βk k N k () ( | ) sp Ss ≡ = y +1 is the backward state metric; and ( ) 1 ( ', ) , , | ' i k k k kk γ s s pu iS s S s ≡ == = − y is the metric of the trellis branch b connecting Sk-1 = s’ to Sk = s with uk = i. Note that we do not necessarily need the exact values of ( | 1 ) N Pu i k = y , but only their ratios. Since for a fixed k, the vector ( ) 1 | N Pu i k = y , being a probability vector, must sum to unity, thus by normalizing the sum to unity, we can omit the constant factor 1 1 ( ) N p y in (5.9.1) and use the following simplified expression: ( ) 1 | N Pu i k = y 1 ( ', ) ( ') ( ', ) ( ) i k i kk k ss B αγ β s ss s − ∀ ∈ ∝ ⋅⋅ ∑ Now we consider the calculation of the branch metric ( ', ) i k γ s s , which is the key point of the symbol-based MAP algorithm, and is also the primary difference between the MAP algorithm for binary turbo codes and the algorithm under consideration. Using Bayes’ rule, the term ( ', ) i k γ s s can be written as ( ', ) i k γ s s 1 11 ( | , ', ) ( | ', ) ( | ') kk k k k k k k k p S sS s u i PS s S s u i Pu i S s = = = =⋅ = = =⋅ = = − −− y 1 ( | ) ( ) ( | ', ) kk k k k k p y x Pu i PS s S s u i = ⋅ =⋅ = = = − (5.9.2) where ( | ) k k p y x is the probability of receiving yk given the transmitted symbol xk, P uk ( ) is the a priori probability of uk = i, and 1 ( | ', ) PS s S s u i kk k = − = = is 1 or 0, indicating whether or not a state transition k k 1 S S − → with input uk = i exists. Thus, for a trellis branch b, we have ( ', ) i k γ s s ( ) , if ( | ) ( ), otherwise k k kk k Pu y p y x Pu ⎧ = ∗ = ⎨ ⋅ ⎩ (5.9.3) Define ( ) 1 ( ', ) , | ' k k kk γ ss pS s S s ≡= = − y
which represent the combined branch metrics.Then the non-binary BCJR algorithm can be summarized as follows. Forward recursion: a(s)-Ea-(')n.(s.s) (5.94) Backward recursion: B(s)=∑B(s)M(s',s) (5.9.5) Output: (s)ri(s',5)B(5) (5.9.6) The boundary conditionsa are theame s for the binary b coe For merical is necessary to control the dynamic range of the likelihood terms computed in (5.9.4)to (5.9.6).This can be performed by normalizing the sum of the(s)and the B(s)values to unity at every particular k symbol.Of course,the algorithm can also be implemented in the ov-do Log-MAP or Max-Log-MAP version. reduced computational complexity,resulting in the 5.9.2 Turbo Trellis-Coded Modulation (TTCM) TTCM是由两个（或多个）TCM码按照Turbo码的方式级联起来构成的并行级联编 码调制系统，它是标准二元turbo码的直接推广。This technique was originally proposed by Robertson and Worz in 1996[?] 5.9.2.1 TTCM Encoder A TTCM encoder consists of the parallel concatenation of two (or multiple)trellis-coded modulation(TCM)schemes in the same fashion as binary turbo codes.Each component TCM encoder onsists of a。 nvolutional encoder of rate mm)and a signal mapper.The mapping of bitsto signal points follows the Ungerboeck'sr of mapping by set partitioning.The first TCM encoder operates on the original input bit sequence,while the second TCM encoder manipulates the interleaved version of the input bit sequence.Here,the interleaving works on groups of bits instead of individual bits.See Fig.5.9.3,where a symbol-based odd-even interleaver is assumed.To avoid excessive r te loss,a spe puncturing technique is used:Symbols from a ary signal constellation are ansmitted alternately from the first and second encoders;i.e.,the puncturing matrix is given by P=0 01
4 ( ', ) ( ', ) k k i k b B ss γ s s ∀ ∈ = ∑ which represent the combined branch metrics. Then the non-binary BCJR algorithm can be summarized as follows. Forward recursion: 1 ' ( ) ( ') ( ', ) k kk s α αγ s s ss − ∈ = ∑ S (5.9.4) Backward recursion: 1( ') ( ) ( ', ) k kk s β βγ s s ss − ∈ = ∑ S (5.9.5) Output: ( ) 1 | N Pu i k = y 1 ( ', ) ( ') ( ', ) ( ) i k i kk k ss B αγ β s ss s − ∀ ∈ ∝ ⋅⋅ ∑ (5.9.6) The boundary conditions are the same as for the binary turbo codes. For numerical stability, it is necessary to control the dynamic range of the likelihood terms computed in (5.9.4) to (5.9.6). This can be performed by normalizing the sum of the ( ) k α s and the ( ) k β s values to unity at every particular k symbol. Of course, the algorithm can also be implemented in the log-domain with reduced computational complexity, resulting in the Log-MAP or Max-Log-MAP version. 5.9.2 Turbo Trellis-Coded Modulation (TTCM) TTCM 是由两个（或多个）TCM 码按照 Turbo 码的方式级联起来构成的并行级联编 码调制系统，它是标准二元 turbo 码的直接推广。This technique was originally proposed by Robertson and Worz in 1996 [?]. 5.9.2.1 TTCM Encoder A TTCM encoder consists of the parallel concatenation of two (or multiple) trellis-coded modulation (TCM) schemes in the same fashion as binary turbo codes. Each component TCM encoder consists of a convolutional encoder of rate m/(m+1) and a signal mapper. The mapping of coded bits to signal points follows the Ungerboeck’s rule of mapping by set partitioning. The first TCM encoder operates on the original input bit sequence, while the second TCM encoder manipulates the interleaved version of the input bit sequence. Here, the interleaving works on groups of bits instead of individual bits. See Fig. 5.9.3, where a symbol-based odd-even interleaver is assumed. To avoid excessive rate loss, a special puncturing technique is used: Symbols from a 2m+1-ary signal constellation are transmitted alternately from the first and second encoders; i.e., the puncturing matrix is given by 1 0 0 1 P ⎡ ⎤ = ⎢ ⎥ ⎣ ⎦ Thus each information bit pair is transmitted in exactly one transmitted symbol with the parity bit alternately chosen from the first and second encoders
TCM encoder Trellis Signal encoder 1 mappe ymbol Puncturing ave Trellis encoder 2 Signal mappe Figure 5.9.3 TTCM encoder.The puncturer is used to avoid rate loss by enabling the transmission of signals carrying the same information bits only once. Assume that a D-dim constellation is used.At each step,m information bits are input to the TTCM ncode nodulated syn a D-dim s constellation of size2 1 We now consider the above odd-even interleaving-puncturing rule more更深入、更一般 LetL denote the number of component codes used in a parallel concatenated system.Then introducing the following definitions the above odd-even interleav rule may be expressed mathematically via Definition:A (pseudo-random)interleaver satisfying the following constraint is called a modulo-L interleaver: π(k)modL=k mod L, wherek stands for the symbol position before interleaving. Definition:A modulo-L puncturer is one that punctures all the modulated symbols in the /th component code,except those at positionk modL=1. For a TTCM scheme,the modulo-L interleaving together with the modulo-L puncturing rule ensure that one and only one modulated symbol carrying the same uk is transmitted,and that the punctured symbols are uniformly distributed in each component code.It is clear that when L=2,the above modulo-L interleaving-puncturing rule is equivalent to that used in [3]. As an example,Fig5.9.4 shows an 8-state TTCM encoder for 8-PSK
5 Trellis encoder 1 Trellis encoder 2 Signal mapper Signal mapper Symbol interleaver TCM encoder Puncturing and Multiplexing Figure 5.9.3 TTCM encoder. The puncturer is used to avoid rate loss by enabling the transmission of signals carrying the same information bits only once. Assume that a D-dim constellation is used. At each step, m information bits are input to the TTCM encoder and then a modulated symbol selected from a D-dim signal constellation of size 2m+1 is transmitted. This yields a throughput of 2 / m D bits per 2-dim symbol. We now consider the above odd-even interleaving-puncturing rule more 更深入、更一般 地. Let L denote the number of component codes used in a parallel concatenated system. Then the above odd-even interleaving-puncturing rule may be expressed mathematically via introducing the following definitions. Definition: A (pseudo-random) interleaver satisfying the following constraint is called a modulo-L interleaver: π ( ) mod mod k Lk L = , where k stands for the symbol position before interleaving. Definition: A modulo-L puncturer is one that punctures all the modulated symbols in the lth component code, except those at position { | mod } kk L l = . For a TTCM scheme, the modulo-L interleaving together with the modulo-L puncturing rule ensure that one and only one modulated symbol carrying the same uk is transmitted, and that the punctured symbols are uniformly distributed in each component code. It is clear that when L=2, the above modulo-L interleaving-puncturing rule is equivalent to that used in [3]. As an example, Fig.5.9.4 shows an 8-state TTCM encoder for 8-PSK