Kodowanie i kryptografia
Turbokody-przeplot i rozplot
Turbokody-przeplot i rozplot
dr Robert Borowiec
Politechnika Wrocławska
Instytut Telekomunikacji i Akustyki
pokój 909, C-5
tel. 3203083
e-mail: Robert.Borowiec@pwr.wroc.pl
WWW: https://lst.ita.pwr.wroc.pl/kursy/
Slajd 2
Plan wykładu
• Historia turbokodów;
• Podstawy turbokodów
• Splot i rozplot;
©
R
o
b
e
rt
B
o
ro
w
ie
c
• Splot i rozplot;
• Typy koderów splotowych;
Slajd 3
Historia
• Turbokody zostały wynalezione przez
zespół francuskich naukowców w 1993.
Jest to pierwszy kod FEC, który umoŜliwił
zbliŜenie się w rozwiązaniach
©
R
o
b
e
rt
B
o
ro
w
ie
c
zbliŜenie się w rozwiązaniach
praktycznych do granicy wyznaczającej
teoretyczną pojemność kanału.
Slajd 4
Zasada działania kodera
W turbo kodach, ta sama informacja
wysyłana jest kilkukrotnie, lecz po
przepuszczeniu jej przez układ dokonujący
permutacji informacji w ramach bloku.
©
R
o
b
e
rt
B
o
ro
w
ie
c
permutacji informacji w ramach bloku.
Nie w tym tkwi jednak zasadnicza istota
turbokodów. To co odróŜnia turbo kody od
kodów powtórzeniowych jest wielokrotne
iteracyjne ich dekodowanie.
Slajd 5
Co decyduje o zdolności korekcyjnej
kodu?
Jedynym czynnikiem mającym bezpośredni
wpływ na zdolność korekcyjną kodu jest
odległość minimalna w zbiorze słów
kodowych.
©
R
o
b
e
rt
B
o
ro
w
ie
c
kodowych.
W przypadku kodów binarnych jest to
minimalna odległość Hamminga MHD-(ang.
Minimum Hamming Distance)
Slajd 6
Co chcemy, a co mamy
Chcemy !!!
Mamy !!!
©
R
o
b
e
rt
B
o
ro
w
ie
c
Kody o dużym MHD
Kody o małym MHD
Slajd 7
Rozwiązanie problemu, które zapewni
duŜą odległość Hamminga
Kody o małym MHD
©
R
o
b
e
rt
B
o
ro
w
ie
c
Kody o dużym MHD
Kody o małym MHD
Kody o małym MHD
Rozwiązaniem problemu jest wykorzystanie wielu kodów o
małej odległości Hamminga
Slajd 8
Turbo koder PCC
©
R
o
b
e
rt
B
o
ro
w
ie
c
Równolegle Powiązany Kod Splotowy
(ang. Parallel Concatenated Convolutional Code)
Slajd 9
Turbo koder SCCC
©
R
o
b
e
rt
B
o
ro
w
ie
c
Szeregowo powiązane kod splotowy
(ang. Serially Concatenated Constituent Coding)
Slajd 10
Turbo koder hybrydowy (HTC)
©
R
o
b
e
rt
B
o
ro
w
ie
c
Slajd 11
Turbo Product Code (TPC)-koder
zbudowany na koderach blokowych
©
R
o
b
e
rt
B
o
ro
w
ie
c
Turbo koder zbudowany na dwóch koderach blokowych (8,4) i (7,4). Nie ma w
nim układu przeplotu, gdyż sam sposób kodowania zapewnia odpowiednie
przemieszanie bitów
Slajd 12
Kodery w turbo koderach
• Przy wyborze koderów do turbo koderów,
naleŜy wykazać pewną ostroŜność i tak w
koderach PCC naleŜy stosować:
©
R
o
b
e
rt
B
o
ro
w
ie
c
• tylko i wyłącznie kodery splotowe systematyczne;
• o małym stosunku R=k/n (k-dł symbolu wej., n-dł
symbolu wyj.), gdyŜ zwiększanie n nie prowadzi
do poprawy parametrów kodera, a wymaga
większych nakładów obliczeniowych;
• najlepiej kodery rekursywne RSC
Slajd 13
Porównanie turbo koderów
PCC
SCCC
R R
R
R R
=
©
R
o
b
e
rt
B
o
ro
w
ie
c
Sprawność
Zalety
Mniejsze MHD
Większe MHD
Wady
Konieczność stosowania
kodów systematycznych
(maja gorsze właściwości
od niesystematycznych)
Rs<Rp, transmitujemy
mniej informacji, a
więcej bitów parzystości
1
2
1
2
1 (1
)(1
)
p
R R
R
R
R
=
−
−
−
1
2
s
R
R R
=
Slajd 14
Dekodowanie turbo kodów
(
)
(
)
{
{
A
zdarzenia
prawdopod.
B
zdarzenia
prawdopod.
B
zdarzenia
prawdopod.
A
zdarzenia
prawdopod.
.
Pr
)
(
)
|
(
)
(
|
,
priori
a
posteriori
a
priori
a
posteriori
a
łączne
awdopod
B
P
A
B
P
B
P
B
A
P
B
A
P
−
−
−
−
⋅
=
⋅
=
4
3
42
1
4
3
42
1
3
2
1
©
R
o
b
e
rt
B
o
ro
w
ie
c
A
zdarzenia
B
zdarzenia
prawdopod.
B
zdarzenia
A
zdarzenia
prawdopod.
łączne
(
)
)
(
)
(
)
|
(
|
PP
B
P
A
P
A
B
P
B
A
P
A
⋅
=
4
3
42
1
Slajd 15
Turbo dekoder
©
R
o
b
e
rt
B
o
ro
w
ie
c
Slajd 16
SISO-Soft input, Soft Output
0
1
0
1
1
0
1
1
1
0
©
R
o
b
e
rt
B
o
ro
w
ie
c
16
16
Dekoder 1
Dekoder 2
O tym
wiem
tylko ja
o tym
Wiem
tylko ja
Wiemy o
tym obaj
Slajd 17
Dekoder miękkodecyzyjny
To są moje hipotezy na
temat danych
prawdopodobieństwo a
priori
©
R
o
b
e
rt
B
o
ro
w
ie
c
SISO
To jest mój osąd na podstawie
danych (zebranego
doświadczenia)
prawdopodobieństwo a
posteriori
Slajd 18
Zysk z wielokrotnego przetwarzania
informacji w turbo dekoderze
©
R
o
b
e
rt
B
o
ro
w
ie
c
Slajd 19
[1] www.complextoreal.com
[2] C. Berrou, A. Glavieux, i P. Thitimajshima, „Near Shannon limit error-correcting
coding and decoding:Turbo-codes. 1”, in Technical Program, Conference Record, IEEE
International Conference on Communications, 1993. ICC 93. Geneva, 1993, t. 2, s.
1064-1070 vol.2.
©
R
o
b
e
rt
B
o
ro
w
ie
c
1064-1070 vol.2.