Статья:

Исследование итеративного алгоритма декодирования MAP и разработка модели турбокодека в сиcтеме MathCAD

Конференция: XLII Студенческая международная заочная научно-практическая конференция «Молодежный научный форум: технические и математические науки»

Секция: Технические науки

Выходные данные
Зиновьев П.А., Федурин Н.Е. Исследование итеративного алгоритма декодирования MAP и разработка модели турбокодека в сиcтеме MathCAD // Молодежный научный форум: Технические и математические науки: электр. сб. ст. по мат. XLII междунар. студ. науч.-практ. конф. № 2(42). URL: https://nauchforum.ru/archive/MNF_tech/2(42).pdf (дата обращения: 17.08.2018)
Лауреаты определены. Конференция завершена
Эта статья набрала 14 голосов
Мне нравится
Дипломы
лауреатов
Сертификаты
участников
Дипломы
лауреатов
Сертификаты
участников
на печатьскачать .pdfподелиться

Исследование итеративного алгоритма декодирования MAP и разработка модели турбокодека в сиcтеме MathCAD

Зиновьев Павел Алексеевич
магистрант, Сибирский государственный университет телекоммуникаций и информатики, РФ, г. Новосибирск
Федурин Никита Евгеньевич
студент, Сибирский государственный университет телекоммуникаций и информатики, РФ, г. Новосибирск
Мелентьев Олег Геннадьевич
научный руководитель, проф., Сибирский государственный университет телекоммуникаций и информатики, РФ, г. Новосибирск

 

На сегодня турбокоды получили широкое распространение в области связи, особенно в технологиях беспроводной связи, таких как WiMAX, мобильные и спутниковые сети и др. Турбокоды особенно эффективны в каналах с низким отношением сигнал/шум, поэтому имеют огромные перспективы для использования в новых поколениях связи [4]. В этой статье представлен принцип работы турбокода и его итеративного декодирования при помощи алгоритма MAP. Также представлен численный пример кодирования и декодирования турбокода. Модель выполнена в среде MathCAD v.15, разработаны функции для вычисления всех параметров декодирования.

Структура 1/3 турбокодера показана на рисунке 1. Используем два идентичных свёрточных кодера. На первый поступает информационный бит , на второй поступает перемеженный информационный бит. В результате получаем один информационный бит и два проверочных. Для перемежения входной информационной последовательности используется псевдослучайный перемежитель (interleaver) [1; 5].

 

Рисунок 1. Структурная схема турбокодера

 

Каждый свёрточный кодер является систематическим рекурсивным RSC-кодером, но поскольку мы уже передаем информационный элемент  на выход турбокодера, то на выходе каждого из двух RSC-кодеров будут только проверочные элементы и .

 

Рисунок 2. Схема RSC-кодера

 

При детектировании значения принятого символа из канала необходимо определить его значение функции правдоподобия. Расположение этого символавдоль оси х не позволяет однозначно определить значение передаваемого бита, поскольку в любой точке на оси х соответствуют два значения правдоподобия – для  и для . Основываясь на принципах жесткого решения и максимального правдоподобия, приемник должен сравнить значения  и  и вынести решение о принятом бите. Таким образом, в жесткой схеме принятия решения, при расположении точки правее порога x = 0, сигнал переносит бит «1».

 

Рисунок 3. Функции распределения вероятностей принятого сигнала

 

Если взять логарифм отношения  к  для a и b, то:

,

Как видно, вероятнее всего a является «0», а b является «1». Логарифм отношения  к  называется логарифмическим отношением функций правдоподобия (LLR – Log-Likelyhood Ratio).

 

Рисунок 4. Структурная схема турбодекодера

 

MAP – это алгоритм декодирования по методу максимума апостериорной вероятности контролирующих ошибки кодов, определённых на решётках [5]. На рисунке 5 приведена блок-схема алгоритма MAP турбодекодера.

 

Рисунок 5. Блок-схема алгоритма MAP турбодекодера

 

Для вычисления LLR нужно рассчитать значения переходов между узлами решетки, прямую и обратную метрики. Переходы между узлами решетки рассчитываются как:

,

где:  и  – прошлое и следующее состояния, и  – информационный и проверочный символы на решетке, и  – информационный и проверочный символы на входе декодера, – качество канала, – информация с прошлой итерации работы декодера, k – номер элемента. Рассчитать прямую метрику α можно рекурсивно:

Расчет обратной метрики β так же вычисляется рекурсивно, начиная с конца решетки:

Чтобы начать вычисление метрик, нам нужно инициализировать начальные состояния:

 

Декодер #1

 

Декодер #2

 

1

1

 

1

0,25

0

0

 

0

0,25

0

0

 

0

0,25

0

0

 

0

0,25

 

Так как мы не знаем в каком состоянии остановлен свёрточный декодер #2, то его начальные значения β будут равны: , где  – количество ячеек в регистре памяти кодера. При этом результаты вычисления метрик нужно пронормировать:  и .
Расчет LLR с выхода декодера осуществляется по формуле:

где:  – это априорная информация, которая является мягким выходом декодера после одной итерации декодирования,  – это внешняя информация, взятая из результата предыдущей итерации декодирования [6; 9].

Рассмотрим пример итеративного декодирования турбокода алгоритмом MAP [6]. На вход турбокодера отправим последовательность из шести битов:. Эти биты приходят на RSC #1. Результат кодирования показан на решетке:

 

Рисунок 6. Кодирование в RSC #1

 

Искусственно остановим состояние решетки в нулевом состоянии, отправив дополнительно еще два бита:. Теперь перемежим эту информационную последовательность (с учётом добавочных битов) для отправки на второй декодер. Результат кодирования для RSC #2 и схема работы псевдослучайного перемежителя:

 

Рисунок 7. Кодирование в RSC #2 (слева) и схема работы перемежителя (справа)

 

Далее информационные и проверочные биты преобразуются в символы отправляются в канал. После этого получаем искаженную последовательность:

Таблица 1.

Передача информации по каналу с шумом

xk

p1k

p2k

 

AWGN

 

x`k

p`1k

 p`2k

+1

+1

-1

 

1,966099

2,132927

-0,701887

 

2,966099

3,132927

-1,701887

+1

-1

-1

 

-1,232363

-0,443420

-0,696641

 

-0,232363

-1,443420

-1,696641

-1

-1

+1

 

0,750745

0,823265

0,823463

 

-0,249255

-0,176735

1,823463

-1

+1

+1

+

1,832447

-0,088392

1,036052

=

0,832447

0,911608

2,036052

+1

-1

-1

-1,262811

0,551007

-2,051227

-0,262811

-0,448993

-3,051227

-1

+1

+1

 

0,205224

0,277622

0,462560

 

-0,794776

1,277622

1,462560

+1

+1

+1

 

-0,569778

0,978633

1,105726

 

0,430222

1,978633

2,105726

-1

-1

+1

 

0,257169

0,465353

-0,700940

 

-0,742831

-0,534647

0,299060

 

Первый этап первой итерации декодирования. Вычислим значение  при .

Таблица 2.

Переходы между узлами решетки

s`,s

γ1(s`,s)

γ2(s`,s)

γ3(s`,s)

γ4(s`,s)

γ5(s`,s)

γ6(s`,s)

γ7(s`,s)

γ8(s`,s)

0,0

0.00245

5.342977

1.531105

0.174810

2.037664

0.617025

0.089918

3.587580

0,1

445.423716

0.187162

0.653123

5.720493

0.490758

1.62068

11.12122

0.278739

1,2

0.846345

3.357031

0.930047

0.923891

1.204641

0.125884

0.212586

0.812058

1,3

1.181551

0.297882

1.075214

1.082379

0.830122

7.94385

4.703990

1.231440

2,0

445.423716

0.187162

0.653123

5.720493

0.490758

1.62068

11.12122

0.278739

2,1

0.00245

5.342977

1.531105

0.174810

2.037664

0.617025

0.089918

3.587580

3,2

1.181551

0.297882

1.075214

1.082379

0.830122

7.94385

4.703990

1.231440

3,3

0.846345

3.357031

0.930047

0.923891

1.204641

0.125884

0.212586

0.812058

 

Таблица 3.

Результаты  с учетом нормировки

s

α0(s)

α1(s)

α2(s)

α3(s)

α4(s)

α5(s)

α6(s)

α7(s)

α8(s)

0

1

0.000005

0.000007

0.276497

0.086266

0.125209

0.125318

0.611503

0.645632

1

0

0.999995

0

0.648177

0.490561

0.20369

0.080761

0.164843

0.227173

2

0

0

0.918491

0.04039

0.196582

0.358283

0.478213

0.172365

0.05674

3

0

0

0.081501

0.034937

0.226591

0.312817

0.315708

0.051289

0.070455

Таблица 4.

Результаты  с учетом нормировки

s

β8(s)

β7(s)

β6(s)

β5(s)

β4(s)

β3(s)

β2(s)

β1(s)

β0(s)

0

1

0.927906

0.007756

0.00085

0.011918

0.620645

0.497532

0.561278

0.289971

1

0

0

0.001425

0.046305

0.384623

0.182016

0.096161

0.229608

0.00058

2

0

0.072094

0.959294

0.001678

0.046058

0.038162

0.318321

0.127281

0.708827

3

0

0

0.031526

0.951132

0.557401

0.159177

0.087986

0.081832

0.000623

 

Результаты расчета LLR первого этапа первой итерации декодирования и расчет внешней информации для следующего декодера. Как видим, здесь три ошибки при декодировании:

Таблица 5.

Результаты первого этапа первой итерации

Жесткое решение

 

11.304209

1

0

5.932198

5.372011

 

-2.335599

3.707484

1

0

-0.464726

4.17221

 

-2.786418

0.393572

1

0

-0.49851

0.892082

 

4.17221

0.505559

1

0

1.664894

-1.159335

Перемежение

0.892082

-0.436345

0

0

-0.525622

0.089277

 

0.089277

-4.37597

0

0

-1.589552

-2.786418

 

-1.159335

3.737709

1

0

0.860444

2.877265

 

2.877265

-3.821261

0

0

-1.485662

-2.335599

 

5.372011

 

Второй этап первой итерации декодирования.

Таблица 6.

Переходы между узлами решетки

s`,s

γ1(s`,s)

γ2(s`,s)

γ3(s`,s)

γ4(s`,s)

γ5(s`,s)

γ6(s`,s)

γ7(s`,s)

γ8(s`,s)

0,0

37.027066

48.648744

0.025294

0.107224

26.295547

0.179903

0.018787

0.002603

0,1

0.027007

0.020556

39.535741

9.326298

0.038029

5.558561

53.227787

384.200557

1,2

0.810899

0.611804

1.030742

0.158934

16.997298

0.298263

0.789093

211.250514

1,3

1.181551

0.297882

1.075214

1.082379

0.830122

7.94385

4.70399

1.23144

2,0

0.027007

0.020556

39.535741

9.326298

0.038029

5.558561

53.227787

384.200557

2,1

37.027066

48.648744

0.025294

0.107224

26.295547

0.179903

0.018787

0.002603

3,2

1.233199

1.634511

0.970175

6.291918

0.058833

3.352749

1.267278

0.004734

3,3

0.810899

0.611804

1.030742

0.158934

16.997298

0.298263

0.789093

211.250514

 

Таблица 7.

Результаты  с учетом нормировки

s

α0(s)

α1(s)

α2(s)

α3(s)

α4(s)

α5(s)

α6(s)

α7(s)

α8(s)

0

1

0.999271

0.999544

0.000649

0.000028

0.000096

0.006442

0.987545

0.003026

1

0

0.000729

0.000422

0.999329

0.000937

0.037461

0.000354

0.007571

0.991757

2

0

0

0.000009

0.000012

0.024624

0.004239

0.880803

0.003006

0.004181

3

0

0

0.000024

0.000011

0.974411

0.958204

0.112401

0.001878

0.001037

Таблица 8.

Результаты  с учетом нормировки

s

β8(s)

β7(s)

β6(s)

β5(s)

β4(s)

β3(s)

β2(s)

β1(s)

β0(s)

0

0.25

0.322611

0.341684

0.035868

0.052754

0.490632

0.422587

0.93188

0.979355

1

0.25

0.177389

0.017336

0.057222

0.411621

0.364305

0.004247

0.016093

0.001704

2

0.25

0.322611

0.621132

0.432318

0.084045

0.06842

0.568904

0.009759

0.017627

3

0.25

0.177389

0.019848

0.474592

0.451581

0.076643

0.004262

0.042268

0.001314

 

Результаты расчета LLR второго этапа первой итерации декодирования и расчет внешней информации для следующей итерации:

Таблица 9.

Результаты второго этапа первой итерации

 

 

-11.28214

-2.335599

-1.485662

-7.460879

 

0.586152

-11.006386

-2.786418

-1.589552

-6.630416

 

3.346571

7.054056

4.17221

-0.464726

3.346571

Обратное

перемежение

-5.582095

-5.188523

0.892082

-0.49851

-5.582095

-5.076676

4.845143

0.089277

-0.525622

5.281488

 

5.281488

-4.571117

-1.159335

1.664894

-5.076676

 

-6.630416

5.737179

2.877265

0.860444

1.99947

 

1.99947

11.890361

5.372011

5.932198

0.586152

 

-7.460879

 

Произведем обратное перемежение выхода второго этапа первой итерации декодирования  и примем жесткое решение:

Таблица 10.

Вывод результатов после декодеров

 Жёсткое решение

11.89036

1

7.05406

1

-5.18852

0

-4.57112

0

4.84514

1

-11.00639

0

5.73718

1

-11.28214

0

 

 

Декодер исправил ошибки. Мы можем произвести еще несколько итераций декодирования для увеличения доверия к полученным результатам. Результаты восьми этапов декодирования для четырех итераций:

Таблица 11.

Результаты 8 этапов декодирования

0

1

2

3

4

5

6

7

11.304

11.890

20.874

20.886

23.923

23.923

23.924

23.924

3.707

7.054

13.568

28.371

36.309

36.790

36.838

36.838

0.394

-5.189

-15.299

-23.380

-34.140

-34.175

-34.224

-34.224

0.506

-4.571

-14.706

-17.363

-20.921

-20.922

-20.923

-20.923

-0.436

4.845

13.458

21.366

34.036

34.084

34.157

34.157

-4.376

-11.006

-19.115

-30.682

-39.510

-39.561

-39.597

-39.597

3.738

5.737

15.494

18.303

20.972

20.972

20.973

20.973

-3.821

-11.282

-20.976

-33.533

-42.587

-42.637

-42.684

-42.684

 

Количество итераций может быть разным для разных алгоритмов турбодекодирования. Это также зависит от параметров канала. Обычно если дальнейшее итеративное вычисление не приводит к смене знака выходной надежности бит, то утверждают, что декодер сошелся, т.е. пришел к некоторому стационарному состоянию [2; 3]. В данной работе принято вычислять 8 итераций. Существует три критерия остановки декодера. Подробно можно узнать в [7; 8].

В результате работы получена модель турбокодека в среде MathCAD, которую можно использовать для изучения процессов итеративного декодирования, изменения и создания модели для других алгоритмов работы турбокодов. Турбокоды имеют высокий потенциал и энергетическую эффективность, что позволяет их использовать в системах связи для увеличения дальности приема, скрытности системы, поэтому актуальность исследования итеративных кодов только возрастает.

 

Список литературы:
1. Зайцев С.В., Ливенцев С., Алексеев Д. Применение турбокодов в специальных телекоммуникационных системах // Правове, нормативне та метрологічне забезпечення систем захисту інформації в Україні. – 2005. – Вип. – 2005. – Т. 11. – С. 162–167.
2. Крук Е.А. Разработка и исследование эффективных алгоритмов декодирования турбокодов в системах мобильной связи.
3. Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования // методы, алгоритмы, применение: учеб. пособие для вузов / Р. Морелос-Сарагоса. – М.: Техносфера. – 2006. – Т. 320.
4. Ситников А. В. и др. Турбокодирование как основа в системах передачи данных //Вестник Воронежского государственного технического университета. – 2013. – Т. 9. – № 6–3.
5. Скляр Б. Цифровая связь: Теоретические основы и практическое применение. – Издательский дом Вильямс, 2004.
6. Abrantes S.A. From BCJR to turbo decoding: MAP algorithms made easier. – 2004.
7. Hanzo L., Liew T. H., Yeap B. L. Turbo coding, turbo equalisation and space-time coding. – John Wiley & Sons, 2002.
8. Hanzo L. L. et al. Turbo coding, turbo equalisation and space-time coding: EXIT-chart-aided near-capacity designs for wireless channels. – John Wiley & Sons, 2011.
9. Jiang Y. A practical guide to error-control coding using Matlab. – Artech House, 2010.