MAP algorithm
MAP algorithm
T re llis c od e mod u lation
Trellis Code Modulation (TCM)
• Spectral efficiency: number of bits per second per 1 Hz of
bandw idth (b its/s/Hz).
• T h e data rate can be increased w ith outh increasing th e
bandw idth by transmiting more information per ev ery symbol.
( M ore bits per ev ery ch annel use).
• T h e information content of th e symbol is increased by
increasing amount of possible symbol v alues. F or ex ample for
transmitting tw o bits per symbol w e h av e to h av e four
possible symbol lev els.
Trellis code modulation
• In general the coding maps information bit to higher number
of code bits.
• If the coded bits are transmitted bit by bit in order to maintain
the data rate we have to increase the channel usage rate.
• More code bits means that spectral efficiency is decreased
since more bandwidth is req uired.
• The trellis coded modulation introduces additional parity bits
and does not increase the bandwidth.
• The eff ective throughput in the channel is maintained by
enlarging the number of constellation points.
• B y increasing the amount of constellation points we increase
• If th e energ y per information bit is k ept constant th e h ig h er
the signal set and more information can be transmitted by
each singnal.
number of symbol v alues decrease th e av erag e pow er per
symbol - increase of error probability for symbol.
• E rror probability can be decreased by adding more code bits -
th e code rate is increased.
MAP algorithm
MAP algorithm
Trellis code modulation
• The signalling rate is not increased since each symbol contains
more information.
• Since power ber bit is kept constant after increasing the
constellation siz e the distance between the possible
constellation points, symbols, is should be decreased
• The positive coding gain is achieved if the increase of the
error probability due to smaller distance between constellation
points is outweighted by the coding gain of the error
correction code.
Trellis code modulation
• For example: we have 4 information bits that are
tramnsmitted in 4 subsequent time intervals.
• The information bits are coded with 1/2 rate code. The
codeword contains 8 coded bits.
• In order to maintain the same information rate we have to
send for each infoamtion bit two coded bits. The coded bits
can be transmitted either by
− U sing two times shorter pulses. (two times more bandwidth)
− U sing more constellation points per channel use. For example
4 Q P SK instead of BP SK .
In order to keep power bit constant this new constellaion
should be scaled with the coding rate.
MAP algorithm
MAP algorithm
Trellis code modulation
Trellis code modulation
Coding versus noncoding
4 PSK transmitter
- 4 PSK each of the four bits may be transmitted.
- The sequence that can be transmitted is not restricted.
2(010)
2
2(010)
3(011)
1
4(011)
0(000)
- The optimum detector makes nearest phasor based decision
for each individual received symbol.
- Each phasor is represented by two bit symbol.
3
0
5(101)
7(111)
6(110)
00
01
10
11
8 PSK TCM endoder
- The 8PSK trellis has four states selected accordingly to the
state of the shift register.
- A t arrival of a new symbol the content of the shift register is
changed.
- The encoding allows only certain trajectories trough the trellis.
- Illegitimate sequences can be rejected.
Figure: C oded and non coded transmission
MAP algorithm
MAP algorithm
Trellis code modulation
Trellis code modulation
Example of TCM principle
2(010)
• The extended signal set has smaller distance between the
neighbouring constellation points than the initial signal set.
3(011)
4(011)
2(01
0)
0(000)
• Subset of the signal set has better distance compared to initial
set.
• If we know at the decoder which subset is in the use we have
5(101)
7(111)
6(110)
better BER for the bit decision than in the initial code.
• In TCM the selection of the signal set is made accordingly to
the state in the trellis of the convolutionally encoded bits.
Figure: Example of the set partitioning
MAP algorithm
MAP algorithm
Trellis code modulation
Trellis code modulation
• The binary phasor identifiers are not Gray encoded.
D
• The bit assignment is made for achieving high Eucledian
distance between the trajectories in the trellis.
Signal mapping
Bit 2
+
• The Eucledian distance amongst constellation points is
Bit 1
increased at every partition step.
• Parallel trellis transitions are assigned to phasors with
D
maximum possible distance.
+
Bit 0
D
00001111
00110011
01010101
01234567
• All the signals are used with equal probability.
• The state transitions have distance of d1 =
√
2 at least.
Figure: Example of a TCM encoder
• L ast two bits are used for identifying the used set.
• The unprotected bit 2 is used for selecting the point in each
partitioned set.
MAP algorithm
MAP algorithm
Trellis code modulation
Trellis code modulation
0
0
4
00
2
2
6
6
01
0
10
3
11
0
7
1
7
4
1 5
2
1
3
5
Figure: Example of a TCM
encoder, symbol based
trellis
• The error is divergence from
the correct trellis path.
• The minimum distance is the
minimum from :
- the distance between the
phasors labelling the
parallel branches
- distance between the
trellis paths.
• Free distance in 4PSK
√
dfree = 2
• Free distance in TCM 8PSK
q
2
2
2
dfree = min d2 ; d1 + d0 + d1 = 2
Probability calculation for the symbols
We have to evaluate the aposteriori probability for each possible
constellation point given the observed value from the channel.
p(Y |X )
X is defined by the possible constellation point (symbol).
Y is the observed noisy value
MAP algorithm
MAP algorithm
Trellis code modulation
Trellis code modulation
Example: 8 PSK
2(010)
1(001)
3(011)
4(011)
0(000)
X-Axi
s
7(111)
5(101)
6(110)
p(y |x1 ) = √
• possible 8 positions in the
complex plain.
• Can be evaluated as multiplication of two independent
gaussian probabilities or as a
complex gaussian probability.
• For a symbol x1 = 1
x1,real = 1 x1,im ag = 0
If the received point is y = 0.7 + 0.6 ∗ j
Const. Point xi
P(y |xi ) ln(P(y |xi ))
1.0000
0.7 07 1 + 0.7 07 1j
0 + 1.0000j
-0.7 07 1 + 0.7 07 1j
-1.0000
-0.7 07 1 - 0.7 07 1j
0 - 1.0000j
0.7 07 1 - 0.7 07 1j
0.13
1.19
0.048
0.00005 7
0.000...
0.000...
0.000...
0.00023 7
-2.026
0.17 68
-3 .03 07
-9 .7 69 7
-16.09 25
-18.29 5 3
-15 .087 8
-8.3 488
ln
P(P(y |xi ))
j (P(y |xj ))
-2.3 4
-0.1408
-3 .3 4
-10.09
-16.41
-18.61
-15 .41
-8.67
(yreal −x1,real )2
(yim ag −x1,im ag )2
1
1
2σ
2σ
e−
·√
e−
2πσ 2
2πσ 2
2
1|
1 − |y−x
2σ
c
=
e
2πσc2
MAP algorithm
MAP algorithm
Turb o trellis coded modulation
Turbo Pinciple on Trellis codes
• The probability is calculated for the whole symbol s1 .
• The aposteriori probabilities can not be calculated for the bits
separately.
• In general the bits probabilities are not independent.
p(y |s1 ) = p(y |b1 , b2 , b3 ) 6= p(y1 |b1 )p(y2 |b2 )p(y3 |b3 )
Possible Solutions
• Symbol based coding → Symbol Based MAP.
• Marginalisation → BICM.
• Use multiple interleavers and clever puncturing.
Turbo trellis coded modulation
Symbol based turbo codes
• We employ multiple trellis encoders in parallel.
• The puncturing is made at the output of the encoders.
− Puncturing is made on the symbols.
− In case of two encoders every other symbol is selected from
different encoder output.
• The symbol stream to different encoders is interleaved.
In order not to puncuture systematic bits:
− The symbol stream is split into two sets.
− Interleaving is made inside of the sets.
− D uring the puncturing: from one encoder is punctured away
symbols in one set, from the other encoder symbols from the
ohter set.
MAP algorithm
MAP algorithm
Turbo trellis coded modulation
Turbo trellis coded modulation
Turbo Trellis Code Modulator
Trellis
Encoder 1
Symbol based Turbo Decoding
Signal
Mapper
Symbol
Interl.
Channel
interl.
Modulator
Symbol
Deinterl.
Trellis
Encoder 1
Signal
Mapper
Figure: Example of a TTCM encoder
MAP algorithm
The symbol based MAP algorithm differ from its bit based
counterpart:
• The probabilities are calculated for the symbols.
• In general the logarithms are evaluated for the probabilities
not for the likelihood ratios.
• The extrinsic infomation is calculated for the symbols.
In TTCM encoder the full symbol is punctured away.
• In the trellis all the probabilities for all the possible values the
punctured symbol can take are set to be equal.
• The MAP decoder evaluates the aposteriori probability also
for the symbols that are punctured away and use these as the
extrinsic information for the other decoder.
• Between the decoders is transmitted the extrisic information
for the symbols.
MAP algorithm
Turbo trellis coded modulation
Turbo trellis coded modulation
0
metric
[P&S]
symbol by
symbol
MAP
A+[E&S]
4
[E&S]
interleaver
a-priori
+
2
2
interleaver
symbols
a=[E&S]
0
5
A=[e&s]
metric
6
6
symbol by
symbol
MAP
a+[e&s]
+
4
1
[e&s]
deinterleaver
a-priori
[p&s]
3
deinterleaver
a-posteriori
Hard decision
7
7
P - parity, S - systematic, E - extrinsic, A - a-priori
Figure: Example of a TCM decoder
3
1
5
P(r1|s#,2)=P(r1|b#,11,b#,21,b#,31)
P(r2|s#,2)=P(r2|b#,12,b#,22,b#,32)
P(r3|s#,3)=P(r2|b#,13,b#,23,b#,33)
Punctured
MAP algorithm
MAP algorithm
Turbo trellis coded modulation
Turbo trellis coded modulation
A
The algorithm for calculating pk,m
= P sk = m|y
Nonbinary or symbol based MAP algorithm
A
• Calculation of the pk,m
is sim ilar to calculation of a b it
• Calculation of the probability value for the symbol.
• Each information symbol uk can have M different values and
contain m log2 (M) bits of information.
• The decoder computes aposteriori Probability (APP)
each of the possible
•
2m
A
pk,m
ap osteriori p rob ab lity in the trellis of a b inary cod e.
• W e sum ov er all the p aths troug h the trellis w here g iv en
sy m b ol at tim e k w as sk = m.
for
symbols.
A
pk,m
=
A
pk,m
is the probability that the received symbol at time k was
sk = X .
• The received symbol is decided to be the one with the highest
A
probability.
pk,m
MAP algorithm
X
1
Ak−1 (st ) · Mk st 0 , st · Bk s 0 = Ck ·p A
k,m
P y 0
(s ,s)⇒
sk =m
• In d ecision p rocess w e d o not need the ab solute v alues b ut
ratios and therefore can d rop from m ultip lication w ith the
com m on constants.
MAP algorithm
T u rb o tre llis c od e d mod u lation
• The computation of Mk (st 0 , st) is diff erent in the symbol
based map compared to the binary M A P .
Mk s 0 , s = P {y ∧ Sk = st} | Sk−1 = st 0
= P yk | st 0 , st · P st| st 0
= P yk | st 0 , st · P (m)
- sk = m is the input symbol necessary to cause the transition from
state st 0 to state st.
- P (m) is the a-priori probability of m. (Typically all the symbols are
eq uiprobable).
- The fi rst term is probability that the symbol received is yk and the
symbol transmitted is xk (xk is phasor corresponding to sk ).
- yk = xk + nk . nk is complex A WG N .
Turbo trellis coded modulation
2
1 − |yk −x2k |
2σ
e
= Ck2 ηk st 0 , st
2
2π σ
X
Ak−1 (st) Mk st 0 , st
Ak (st) =
P yk | st 0 , st =
a ll st 0
X
Bk st 0 =
Bk+ 1 (st) Mk st 0 , st
a ll st
• In the result of the algorithm we get a po sterio ri estimation for
each symbol.
• S ince in TTCM the codes have the common symbols this
a po sterio ri information can be used in decoding of the other
code as the extrinsic information of the symbols.
MAP algorithm
MAP algorithm
Turbo trellis coded modulation
Turbo trellis coded modulation
Complexity of the MAP symbol decoder
Performance of TTCM
• N information symbols.
0
10
• E ach information symbol contains M possible values
BER
FER
• Number of encoder states is S.
−1
10
• The trellis code double the original signal constellation. There
are M = 2M possible transmitted symbols.
• The forward and back ward computation requires
−2
BER/FER
10
- 2 · N · M · S multiplications
- N · M · S additions
−3
10
A
• The terms in pk,m
require three multipliations
• there are total N · M terms with S terms to be summed.
−4
10
−5
10
7·N ·M ·S
3·N ·M ·S
3·N ·M
multiplications
summations
exponentials
3
3.1
3.2
3.3
3.4
3.5
SNR
3.6
3.7
3.8
3.9
4
Figure: B ER and FER for 8 PSK encoded TTCM, datarate 2 bits per
symbol
MAP algorithm
MAP algorithm
Turbo trellis coded modulation
B IC M
Bit Interleaved Coded Modulation (BICM)
−1
10
• Purpose of the BICM is to increase the diversity order of TCM
schemes.
• D iversity order of TCM is the minimum number of different
−2
BER
10
symbols along the shortest error event path between the
correct and error event path.
• If there is no parallel branch the degree of diversity is
increased when constraint length of the code is increased.
−3
10
iteration 1
iteration 2
−4
10
8-PSK modulator
Convolutional encoder
iteration 3
iteration 4
Bit 2
D
−5
10
3
3.1
3.2
3.3
3.4
3.5
SNR
3.6
3.7
3.8
3.9
4
Bit 1
D
D
+
Bit 2
+
Bit 1
+
Bit 0
011
interleaver
interleaver
interleaver
010
001
000
110
111
Figure: TTCM performance dependency on interations
Figure: Example of a BICM encoder
100
101
MAP algorithm
MAP algorithm
BICM
BICM
• The symbols are generated by a non-systematic convolutional
encoder.
Turbo BICM
Tranmsmitter
• BICM uses bit interleavers for all the bits of a symbol.
• The number of bitinterleavers equals to the number of bits
encoder
interleaver
modulator
assigned to one non-binary codeword.
Receiver
• Purpose of the bit interleaver:
- Disperse the burst errors and maximiz e the diversity order of
the system.
- U ncorrelate the bits associated with the given transmitted
symbol.
interleaver
deinterleaver
Demodulator
• The interleaved bits are collected into non-binary symbols.
SISO
decoder
Figure: BICM combined with forward error correction
• The symbols are Gray labeled.
The iterative turbo BICM improves BICM performance in gaussian
channel by increasing free eucledial distance of the code. Two new
ideas:
calcualtion of the marginal probability for each bit
set partitioning
MAP algorithm
MAP algorithm
BICM
BICM
• The deocder treats each bit stream as independent.
Bit 2
• Form the symbols are calcualted the marginal probability for
each bit.
• The decoder treats marginal probablities as they would be
Bit 1
011
010
001
110
000
independent.
100
111
010
011
100
000
011
111
101
010
011
001
000 100
000
101
111
110
100
111
101
100
001
110
111
001
110
010
000
010
101
011
001
110
101
011
Bit 0
010
001
100
000
101
111
110
(Bit 2, Bit 1, Bit 0)
Figure: Example of a set partitioning compared to Gray labelling
MAP algorithm
BICM
BICM-ID converts a 2m ary signalling scheme into m independent
parallel binary schemes.
• First iteration - the Gray labelling optimal.
- Gray labelling has a lower number of nearest neighbours
compared to SP - based labelling.
- The higher the number of nearest neighbour the higher the
chances for a bit to be decoded into wrong region.
• Second iteration
- The soft information allows to confine the decision region into
a pair of constellation points.
- We want to maximise the minimum Eucledian distance
between any two points in the possible phasor pairs for all the
bits.