Lecture Notes on Channel Coding - Convolutional Codes PDF

Технически Университет – София Факултет по Телекомуникации Катедра „Комуникационни Мрежи“ Основи на предаването на информация Канално кодиране. Конволюционни кодове Доц. д-р Павлина Колева  Основи на Предаването на Информация :: доц. д-р Павлина...

Технически Университет – София Факултет по Телекомуникации Катедра „Комуникационни Мрежи“ Основи на предаването на информация Канално кодиране. Конволюционни кодове Доц. д-р Павлина Колева  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 2 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Конволюционни кодове Конволюционният код се описва с трите цели числа n, k и K. Отношението k/n има същото значение на скорост на кодиране (количество информация в един кодиран бит), както и при блоковите кодове. В случая n не определя дължината на блока или кодовата дума, както при блоковите кодове. Цялото число K се явява параметър, наречен дължина на кодовото ограничение (constraint length), който показва броя на k-разрядните стъпала на кодиращия преместващ регистър.  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 3 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Конволюционни кодове Важна особеност на конволюционните кодове (за разлика от блоковите) е, че кодерът има памет. Това означава, че n-разрядната кодова последователност, получена вследствие на конволюционно кодиране, се явява функция не само на една k-разрядна входна кодова дума, а и на предишните (K – 1) входни k-разрядни последователности. На практика n и k са малки цели числа, а K се изменя с цел контрол на силата и сложността на кода.  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 4 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Конволюционни кодове Един конволюционен кодер може да се представи по начина, показан на фиг. 1. Той се реализира с помощта на kK-разряден преместващ регистър (K е дължината на кодовото ограничение) и n на брой суматори по модул 2. Дължината на кодовото ограничение – това е броят на k-битовите премествания, след които един информационен бит може да повлияе върху изходния сигнал на кодера. 1 2 3 4................ kK m = m1, m2, …, mi kK – стъпков преместващ регистър Входна последователност (преместване на k стъпки за един такт) 1 + 2 +.......... n + Суматори по модул 2 Разпределител Фиг. 1. Конволюционен кодер с дължина Последователност на кодовата дума на кодовото ограничение K и скорост k/n U = U1, U2, …, Ui, …  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 5 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Конволюционни кодове Във всеки един момент от време (тактов интервал) в първите k стъпки на преместващия регистър се записват k бита. Всичките битове в регистъра се преместват k стъпки надясно. Състоянията на изходите на n-те суматора чрез разпределителя последователно се отнемат и образуват изходната кодова последователност. 1 2 3 4................ kK m = m1, m2, …, mi kK – стъпков преместващ регистър Входна последователност (преместване на k стъпки за един такт) 1 + 2 +.......... n + Суматори по модул 2 Разпределител Фиг. 1. Конволюционен кодер с дължина Последователност на кодовата дума на кодовото ограничение K и скорост k/n U = U1, U2, …, Ui, …  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 6 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Конволюционни кодове Кодерът от фигурата преобразува всяка една последователност m в уникална последователност от кодови думи U, с помощта на кодираща функция G[]: U = G(m) = U1, U2, U3, …, Ui, … Всяка кодова дума Ui се състои от двоични кодови символи, т.нар. канални битове. 1 2 3 4................ kK m = m1, m2, …, mi kK – стъпков преместващ регистър Входна последователност (преместване на k стъпки за един такт) 1 + 2 +.......... n + Суматори по модул 2 Разпределител Фиг. 1. Конволюционен кодер с дължина Последователност на кодовата дума на кодовото ограничение K и скорост k/n U = U1, U2, …, Ui, …  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 7 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Конволюционни кодове Думата Ui, често наричана “клон” на кодовата последователност U се дефинира чрез Ui = U1i, … Uji, … , Uni където Uji е j-тия двоичен кодов символ на клона Ui от кодовата последователност U. 1 2 3 4................ kK m = m1, m2, …, mi kK – стъпков преместващ регистър Входна последователност (преместване на k стъпки за един такт) 1 + 2 +.......... n + Суматори по модул 2 Разпределител Фиг. 1. Конволюционен кодер с дължина Последователност на кодовата дума на кодовото ограничение K и скорост k/n U = U1, U2, …, Ui, … Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 8 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ"  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 9 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Описание на конволюционните кодове  За представяне на един конволюционен кодер се използват различни методи, най-известните от които са: ▫ Графичен; ▫ Полиномен; ▫ Диаграма на състоянията; ▫ Дървовиден граф на преходите; ▫ Решетъчна диаграма.  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 10 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Описание на конволюционните кодове Графично и векторно описание  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 11 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Графично и векторно описание На фиг. 2 е показан модел на конволюционен кодер (2, 1) с дължина на кодовото ограничение K = 3. Той има n = 2 суматора по модул 2 и е със стъпка на преместване k = 1. Скоростта на кодиране на кода k/n е равна на 1/2. Във всеки тактов интервал един бит постъпва в най-лявата клетка на регистъра. Останалите битове, записани в регистъра, се преместват с една клетка надясно. g1 = 111 Първи символ Чрез разпределителя на изхода се + на кода формира двойката символи на кода. u1 Входен бит m Изходна Тези символи образуват кодовата кодова u2 дума дума, свързана с постъпилия в Фиг. 2. Модел на регистъра входен бит. + Втори символ конволюционен на кода кодер g2 = 101 Това се извършва за всеки един входен бит.  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 12 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Графично и векторно описание Изборът на връзките между суматорите и разрядите в регистъра влияят върху характеристиките на кода. Всяко едно изменение в избора на тези връзки води до различен код. Задачата за избор на тези връзки се свежда до това да се получат оптимални дистанционни свойства на кода. Тя е много сложна и като цяло нерешима, но чрез компютърни симулации са намерени добри кодове за k < 20. g1 = 111 Първи символ + на кода u1 Входен бит m Изходна кодова u2 дума Фиг. 2. Модел на + Втори символ конволюционен g2 = 101 на кода кодер  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 13 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Графично и векторно описание За разлика от блоковите кодове, които имат фиксирана дължина на кодовата комбинация n, при конволюционните кодове няма определен размер. Чрез периодично прекъсване на входните кодови последователности може принудително да им се придаде блокова структура. Необходимо е към входната информационна последователност да се добавят нулеви разряди, които служат за изчистване на преместващия регистър. Добавените битове не носят допълнителна информация. g1 = 111 Първи символ + на кода Ефективната скорост на кодиране u1 Входен бит m Изходна ще бъде по-малка от k/n. кодова u2 дума Фиг. 2. Модел на + Втори символ конволюционен g2 = 101 на кода кодер  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 14 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Графично и векторно описание Един от основните начини за описание на кодера е чрез група от n на брой вектори на връзките – по един за всеки от n-те суматора по модул 2. Всеки вектор има размерност K и описва връзките на разрядите (клетките) на преместващия регистър със съответния суматор по модул 2. Единица в дадената позиция на вектора е свързан със показва, че съответният разряд в суматора по Нула регистъра не е свързан модул 2 За кодера от фиг. 2 могат да се g1 = 111 Първи символ + на кода запишат следните вектори за u1 връзките Входен бит m Изходна кодова дума 𝑔1 = 111 u2 Фиг. 2. Модел на 𝑔2 = 101 + Втори символ конволюционен g2 = 101 на кода кодер  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 15 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Графично и векторно описание Фиг. 3. Конволюционно кодиране g1 = 111 на входна последователност g1 = 111 + m = 101 + u1 u1 m=101 10 u1 u2 t0 0 0 0 t1 1 0 0 1 1 u2 u2 + + g2 = 101 В моментите от време g2 = 101 t1, t2 и t3 постъпват последователно трите бита от вектора на g1 = 111 съобщението. g1 = 111 + + u1 u1 1 u1 u2 u1 u2 t2 0 1 0 t3 1 0 1 1 0 0 0 u2 u2 + + g2 = 101 g2 = 101  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 16 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Графично и векторно описание Фиг. 3. Конволюционно кодиране g1 = 111 на входна последователност g1 = 111 + m = 101 + u1 u1 u1 u2 u1 u2 t4 0 1 0 t5 0 0 1 1 0 1 1 u2 u2 + + g2 = 101 За изчистване на g2 = 101 регистъра в моментите от време t4 и t5 се въвеждат Краят на съобщението g1 = 111 (K – 1) = 2 нули. преминава през целия регистър. + В момента от време t6 u1 В момента от изходът на регистъра е u1 u2 време t6 вече t6 0 0 0 нулев. 0 0 може да се u2 предава ново В момента от време t5 + съобщение. регистърът се установява g2 = 101 в изходно състояние.  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 17 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Графично и векторно описание Вектор на съобщението m=101 Крайният ляв символ представлява първия Последователност на изхода U = 11 10 00 10 11 предаден на изхода. За декодиране на съобщението е необходима пълната последователност на изхода (включваща кодовите символи). За извеждане на съобщението от кодера е необходима една нула по-малко, отколкото са разрядите на регистъра или K – 1 изчистващи битове.  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 18 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Импулсна реакция Конволюционният кодер може да се опише чрез своята импулсна характеристика. Реакцията на кодера при преминаване на единичен бит през него. Импулсна реакция на конволюционен кодер Изходна последователност при вход m = 101 Съдържание Изходна дума Вход m Изход на регистъра u1 u2 1 11 10 11 100 1 1 0 00 00 00 010 1 0 1 11 10 11 001 1 1 Сума по модул 2 11 10 00 10 11 Входна поредица: 1 0 0 Линейно събиране на отместените във Изходна поредица: 11 10 11 времето импулсни характеристики на съответните входни импулсни. Получената последователност на изхода, при единица на входа, се нарича реакция на кодера на импулсно въздействие или негова импулсна характеристика.  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 19 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Описание на конволюционните кодове Полиномно описание  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 20 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Полиномно описание Конволюционният кодер може да се представи като набор от n генераторни полинома, по един за всеки от n-те суматора по модул 2. Всеки полином е от степен (K – 1) (или по-малка) и описва връзките на кодиращия преместващ регистър със съответните суматори по модул 2. Коефициентите на отделните събирателни на полинома от степен (K – 1) са равни или на 1, или на 0, в зависимост от това дали има връзка между преместващия регистър и суматора по модул 2. За кодера от фиг. 2 могат да се запишат g1 = 111 + следните генераторни полинома: Входен бит m u1 𝑔1 𝑥 = 1 + 𝑥 + 𝑥 2 𝑔2 𝑥 = 1 + 𝑥 2 u2 Изходната последователност се получава Фиг. 2. Модел на по следния начин: конволюционен + кодер g2 = 101 𝑈 𝑥 = 𝑚 𝑥 𝑔1 𝑥 редуващо се с 𝑚 𝑥 𝑔2 𝑥 m(x) е векторът на съобщението, представен в полиномен вид  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 21 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Полиномно описание 𝑚 = 101 ⇒ 𝑚 𝑥 = 1 + 𝑥 2 𝑔1 𝑥 = 1 + 𝑥 + 𝑥 2 𝑔2 𝑥 = 1 + 𝑥 2 𝑚 𝑥 𝑔1 𝑥 = 1 + 𝑥 2 1 + 𝑥 + 𝑥 2 = 1 + 𝑥 + 𝑥 3 + 𝑥 4 𝑚 𝑥 𝑔2 𝑥 = 1 + 𝑥 2 1 + 𝑥 2 = 1 + 𝑥 4 𝑚 𝑥 𝑔1 𝑥 = 1𝑥 0 + 1𝑥 1 + 0𝑥 2 + 1𝑥 3 + 1𝑥 4 𝑚 𝑥 𝑔2 𝑥 = 1𝑥 0 + 0𝑥 1 + 0𝑥 2 + 0𝑥 3 + 1𝑥 4 𝑈 𝑥 = 1,1 𝑥 0 + 1,0 𝑥 1 + 0,0 𝑥 2 + 1,0 𝑥 3 + 1,1 𝑥 4 𝑈 = 11 10 00 10 11  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 22 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Описание на конволюционните кодове Диаграма на състоянията  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 23 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Диаграма на състоянията Един от начините за представяне на прости 00 кодиращи устройства е чрез кодовата последователност, която се диаграма на състоянията a получава на изхода на кодера при (state diagram). определен входен бит 11 00 11 00 Състоянията представляват съдържание на последните K – 1 най-десни клетки на възможното съдържание на b c преместващия регистър последните K – 1 най-десни 10 01 клетки на преместващия регистър. 10 Входен бит 0 Пътищата между 01 d 01 Входен бит 1 състоянията отразяват 11 кодовата последователност, която се получава на изхода 10 на кодера при определен Фиг. 4. Диаграма на състоянията на конволюционен кодер със скорост на кодиране 1/2 входен бит.  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 24 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Диаграма на състоянията Състоянията на регистъра са следните: a = 00 00 b = 10 кодовата последователност, която се c = 01 a получава на изхода на кодера при d = 11 определен входен бит 11 00 11 Диаграмата показва всички 00 съдържание на последните K – възможни преходи от едно 1 най-десни клетки на преместващия регистър състояние в друго за кодера. b c 10 01 От всяко едно състояние съществуват два възможни 10 прехода, съответстващи на Входен бит 0 01 d 01 възможните два входни бита. 11 Входен бит 1 Всеки един път между състоянията е означен със 10 съответна кодова дума, която Фиг. 4. Диаграма на състоянията на конволюционен кодер със скорост на кодиране 1/2 се получава на изхода.  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 25 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Диаграма на състоянията Преместването в регистъра за единица време е един бит. 00 Съществуват само два кодовата последователност, която се възможни прехода между a получава на изхода на кодера при отделните състояния. определен входен бит 11 00 11 Например, ако състоянието 00 съдържание на последните K – на кодера е 00, единствените 1 най-десни клетки на възможности са следващите преместващия регистър b c състояния са: 00 или 10. 10 01 Диаграмата на състоянията на 10 един конволюционен кодер Входен бит 0 01 d 01 ясно показва, че 11 Входен бит 1 всяка една изходна кодова 10 последователност се явява Фиг. 4. Диаграма на състоянията на конволюционен кодер функция, както на входния бит, със скорост на кодиране 1/2 така и на предишните (K – 1) бита.  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 26 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Диаграма на състоянията Входен бит Състояние на кодера Състояние stage0 stage1 stage2 (state) g1 = 111 0 0 0 Входен + a бит 1 0 0 u1 stage0 stage1 stage2 0 1 0 u2 b Състояние 1 1 0 на кодера + 0 0 1 g2 = 101 c 1 0 1 0 1 1 d 1 1 1  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 27 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Диаграма на състоянията g1 = 111 stage1 stage2 State Входен + 0 0 a бит u1 1 0 b stage0 stage1 stage2 0 1 c u2 Състояние 1 1 d 00 на кодера + Входен бит 0 g2 = 101 a Входен бит 1 00 ti ti+1 stage0 stage1 stage2 State u1 u2 stage1 stage2 State b c 0 0 0 a 0 0 0 0 a 10 01 d 11  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 28 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Диаграма на състоянията g1 = 111 stage1 stage2 State Входен + 0 0 a бит u1 1 0 b stage0 stage1 stage2 0 1 c u2 Състояние 1 1 d 00 на кодера + Входен бит 0 g2 = 101 a Входен бит 1 11 00 ti ti+1 stage0 stage1 stage2 State u1 u2 stage1 stage2 State b c 0 0 0 a 0 0 0 0 a 10 01 1 0 0 a 1 1 1 0 b d 11  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 29 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Диаграма на състоянията g1 = 111 stage1 stage2 State Входен + 0 0 a бит u1 1 0 b stage0 stage1 stage2 0 1 c u2 Състояние 1 1 d 00 на кодера + Входен бит 0 g2 = 101 a Входен бит 1 11 00 ti ti+1 stage0 stage1 stage2 State u1 u2 stage1 stage2 State b c 0 1 0 b 1 0 0 1 c 10 01 10 d 11  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 30 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Диаграма на състоянията g1 = 111 stage1 stage2 State Входен + 0 0 a бит u1 1 0 b stage0 stage1 stage2 0 1 c u2 Състояние 1 1 d 00 на кодера + Входен бит 0 g2 = 101 a Входен бит 1 11 00 ti ti+1 stage0 stage1 stage2 State u1 u2 stage1 stage2 State b c 0 1 0 b 1 0 0 1 c 10 01 1 1 0 b 0 1 1 1 d 10 01 d 11  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 31 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Диаграма на състоянията g1 = 111 stage1 stage2 State Входен + 0 0 a бит u1 1 0 b stage0 stage1 stage2 0 1 c u2 Състояние 1 1 d 00 на кодера + Входен бит 0 g2 = 101 a Входен бит 1 11 00 11 ti ti+1 stage0 stage1 stage2 State u1 u2 stage1 stage2 State b c 0 0 1 c 1 1 0 0 a 10 01 10 01 d 11  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 32 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Диаграма на състоянията g1 = 111 stage1 stage2 State Входен + 0 0 a бит u1 1 0 b stage0 stage1 stage2 0 1 c u2 Състояние 1 1 d 00 на кодера + Входен бит 0 g2 = 101 a Входен бит 1 11 00 11 ti ti+1 00 stage0 stage1 stage2 State u1 u2 stage1 stage2 State b c 0 0 1 c 1 1 0 0 a 10 01 1 0 1 c 0 0 1 0 b 10 01 d 11  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 33 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Диаграма на състоянията g1 = 111 stage1 stage2 State Входен + 0 0 a бит u1 1 0 b stage0 stage1 stage2 0 1 c u2 Състояние 1 1 d 00 на кодера + Входен бит 0 g2 = 101 a Входен бит 1 11 00 11 ti ti+1 00 stage0 stage1 stage2 State u1 u2 stage1 stage2 State b c 0 1 1 d 0 1 0 1 c 10 01 10 01 d 01 11  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 34 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Диаграма на състоянията g1 = 111 stage1 stage2 State Входен + 0 0 a бит u1 1 0 b stage0 stage1 stage2 0 1 c u2 Състояние 1 1 d 00 на кодера + Входен бит 0 g2 = 101 a Входен бит 1 11 00 11 ti ti+1 00 stage0 stage1 stage2 State u1 u2 stage1 stage2 State b c 0 1 1 d 0 1 0 1 c 10 01 1 1 1 d 1 0 1 1 d 10 01 d 01 11 10  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 35 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Описание на конволюционните кодове Дървовидна диаграма  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 36 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Дървовидна диаграма Дървовидната диаграма (tree diagram) добавя към диаграмата на състоянията още една размерност – време. 1 0 a t1 11 00 b a t2 01 10 11 00 d c b a t3 10 01 00 11 01 10 11 00 d c b a d c b a t4 10 01 00 11 01 10 11 00 10 01 00 11 01 10 11 00 d c b a d c b a d c b a d c b a t5 10 01 00 11 01 10 11 00 10 01 00 11 01 10 11 00 10 01 00 11 01 10 11 00 10 01 00 11 01 10 11 00 Фиг. 5. Дървовидна диаграма на конволюционен кодер със скорост на кодиране 1/2  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 37 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Дървовидна диаграма Във всеки следващ момент на постъпване на входен бит процедурата на кодиране може да бъде описана чрез преместване по клоновете на диаграмата отгоре надолу. 1 0 На всеки един клон a съответства една t1 изходна кодова 11 00 последователност. b a t2 01 10 11 00 d c b a t3 10 01 00 11 01 10 11 00 d c b a d c b a t4 10 01 00 11 01 10 11 00 10 01 00 11 01 10 11 00 d c b a d c b a d c b a d c b a t5 10 01 00 11 01 10 11 00 10 01 00 11 01 10 11 00 10 01 00 11 01 10 11 00 10 01 00 11 01 10 11 00 Фиг. 5. Дървовидна диаграма на конволюционен кодер със скорост на кодиране 1/2  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 38 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Дървовидна диаграма Входен бит 0 изходната последователност се намира на клона, надясно и надолу Входен бит 1 който е в посока наляво и надолу 1 0 a t1 11 00 b a t2 01 10 11 00 d c b a t3 10 01 00 11 01 10 11 00 d c b a d c b a t4 10 01 00 11 01 10 11 00 10 01 00 11 01 10 11 00 d c b a d c b a d c b a d c b a t5 10 01 00 11 01 10 11 00 10 01 00 11 01 10 11 00 10 01 00 11 01 10 11 00 10 01 00 11 01 10 11 00 Фиг. 5. Дървовидна диаграма на конволюционен кодер със скорост на кодиране 1/2  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 39 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Дървовидна диаграма Предполага се, че преместващият регистър на кодера първоначално е нулиран. За входна последователност Изходната последователност е 1 0 11011 11 01 01 00 01 a t1 11 00 b a t2 01 10 11 00 d c b a t3 10 01 00 11 01 10 11 00 d c b a d c b a t4 10 01 00 11 01 10 11 00 10 01 00 11 01 10 11 00 d c b a d c b a d c b a d c b a t5 10 01 00 11 01 10 11 00 10 01 00 11 01 10 11 00 10 01 00 11 01 10 11 00 10 01 00 11 01 10 11 00 Фиг. 5. Дървовидна диаграма на конволюционен кодер със скорост на кодиране 1/2  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 40 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Описание на конволюционните кодове Решетъчна диаграма  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 41 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Входен бит 0 Решетъчна диаграма Входен бит 1 t1 t2 t3 t4 t5 t6 Фиг. 6. Решетъчна диаграма на конволюционен кодер 00 00 00 00 00 a = 00 11 11 11 11 11 11 11 11 със скорост на кодиране 1/2 b = 10 00 00 00 10 10 10 10 c = 01 Кодова последователност 01 01 01 на клона 01 01 01 01 d = 11 10 10 10 Използвани са същите условни изображения, Възлите на решетката представляват както и при диаграмата на състоянията. състоянието на кодера.  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 42 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Входен бит 0 Решетъчна диаграма Входен бит 1 t1 t2 t3 t4 t5 t6 Фиг. 6. Решетъчна диаграма на конволюционен кодер 00 00 00 00 00 a = 00 11 11 11 11 11 11 11 11 със скорост на кодиране 1/2 b = 10 00 00 00 10 10 10 10 c = 01 Кодова последователност 01 01 01 на клона 01 01 01 01 d = 11 10 10 10 Във всеки момент от време за представяне на 2k – 1 възможни състояния на кодера решетката трябва да има 2k – 1 възли.  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 43 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Входен бит 0 Решетъчна диаграма Входен бит 1 t1 t2 t3 t4 t5 t6 Фиг. 6. Решетъчна диаграма на конволюционен кодер 00 00 00 00 00 a = 00 11 11 11 11 11 11 11 11 със скорост на кодиране 1/2 b = 10 00 00 00 10 10 10 10 c = 01 Кодова последователност 01 01 01 на клона 01 01 01 01 d = 11 10 10 10 След достигане дълбочина на решетката (равна на три) в момент от време t4 може да се забележи, че тя има фиксирана периодична структура.  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 44 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Входен бит 0 Решетъчна диаграма Входен бит 1 t1 t2 t3 t4 t5 t6 Фиг. 6. Решетъчна диаграма на конволюционен кодер 00 00 00 00 00 a = 00 11 11 11 11 11 11 11 11 със скорост на кодиране 1/2 b = 10 00 00 00 10 10 10 10 c = 01 Кодова последователност 01 01 01 на клона 01 01 01 01 d = 11 10 10 10 В общия случай фиксираната структура се реализира след достигане на дълбочина K. От този момент във всяко едно състояние може да се влезе от което и да е от двете предишни състояния.  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 45 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Входен бит 0 Решетъчна диаграма Входен бит 1 t1 t2 t3 t4 t5 t6 Фиг. 6. Решетъчна диаграма на конволюционен кодер 00 00 00 00 00 a = 00 11 11 11 11 11 11 11 11 със скорост на кодиране 1/2 b = 10 00 00 00 10 10 10 10 c = 01 Кодова последователност 01 01 01 на клона 01 01 01 01 d = 11 10 10 10 Кодовите думи на изхода съответстват на преходите между състоянията, изобразени като етикети на клоновете на решетъчната диаграма.  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 46 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Входен бит 0 Решетъчна диаграма Входен бит 1 t1 t2 t3 t4 t5 t6 Фиг. 6. Решетъчна диаграма на конволюционен кодер 00 00 00 00 00 a = 00 11 11 11 11 11 11 11 11 със скорост на кодиране 1/2 b = 10 00 00 00 10 10 10 10 c = 01 Кодова последователност 01 01 01 на клона 01 01 01 01 d = 11 10 10 10 За входна последователност Изходната последователност е Двойните линии показват 11011 11 01 01 00 01 пътя през решетката. Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 47 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ"  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 48 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Декодиране на конволюционни кодове Декодиране по максимално правдоподобие  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 49 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Декодиране по максимално правдоподобие Ако всички входни последователности от съобщения са равновероятни, то минималната вероятност за грешка се получава чрез използване на декодер, който сравнява условните вероятности и избира максималната. Условните вероятности се наричат още функции на правдоподобие: 𝑚 𝑃 𝑍/𝑈 Z приета поредица U(m) една от възможните предадени последователности Декодерът избира U(m'), ако 𝑃 𝑍/𝑈 𝑚′ = max 𝑃 𝑍/𝑈 𝑚 за всички 𝑈 𝑚  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 50 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Декодиране по максимално правдоподобие Взимане на двоично решение на основата на принципа на максимално правдоподобие по отношение на един приет сигнал: Ако 𝑝 𝑧 𝑠1 > 𝑝 𝑧 𝑠2 се взима решение, че е бил предаден сигналът s1(t). В противен случай се взима решение, че е бил предаден сигналът s2(t). Параметърът z представлява z(Т), т.е. значението на приетия сигнал за време t = Т. Използване на принципа на максимално правдоподобие за декодиране на конволюционни кодове: Осъществява се в контекста на избора на най-вероятна последователност.  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 51 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Декодиране по максимално правдоподобие Обикновено има едно множество от кодови думи, които е вероятно да са били предадени. При двоичен код последователността от L бита е член на множество от 2L възможни последователности. Следователно, в контекста на максимално правдоподобие, декодерът решава, че е предадена последователността U(m'), ако условната вероятност P(Z|U(m')) е > от вероятностите на всички останали последователности, които е възможно да са били предадени. Такъв оптимален декодер, който минимизира вероятността за грешка (за случая, когато всички предадени символи са равновероятни), се нарича декодер, работещ на принципа на максимално правдоподобие (MLD – Maximum Likelihood Detector).  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 52 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Декодиране на конволюционни кодове Алгоритъм на Витерби  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 53 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Алгоритъм на Витерби Алгоритъмът на Витерби реализира декодиране, основано на принципа на максимално правдоподобие. Алгоритъмът използва особеностите на структурата в решетката на кода. Алгоритъмът включва изчисление на една мярка на подобие (или разстояние) между приетия сигнал в момент от време ti и всички пътища на решетката, входящи за всяко едно състояние в момента ti. В алгоритъма на Витерби не се разглеждат пътища на решетката, които, съгласно принципа на максимално правдоподобие, не могат да се считат за оптимални. Ако в едно и също състояние влизат два пътя, се избира този, който има по-добра метрика; този път се нарича път на оцеляване. Изборът на пътища за оцеляване се извършва за всяко едно състояние.  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 54 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Алгоритъм на Витерби Декодерът напредва по дълбочина в решетката, като взима решение по пътя на малко вероятните пътища. Предварителното отхвърляне на малко вероятните пътища опростява процеса на декодиране. Задачата за избор на оптимален път може да се разглежда като избор на кодова дума с максимална метрика на правдоподобие или избор на кодовата дума с минимална метрика на разстоянието. За илюстрация на този метод на декодиране ще се използва кодерът от фиг. 2 с решетка от фиг. 6. Предполага се, че каналът за предаване е двоичен симетричен канал. В този случай подходяща метрика е Хеминговото разстояние.  Основи на Предаването на Информация :: доц. д-р Павлина Колева, проф. дтн Владимир Пулков 55 Канално кодиране. Конволюционни кодове ФТК, Катедра "КМ" Входен бит 0 Алгоритъм на Витерби Входен бит 1 Последователност на съобщението m: 1 1 0 1 1 Началото на решетката е Предадена кодова дума U: 11 01 01 00 01 в момент от време t1 Приета кодова дума Z: 11 01 01 10 01 в състояние 00. Пълната решетъчна структура се образува след момент t3. Фиг. 6. Решетка на кодера Всеки един клон във време ti се означава с Хеминговото разстояние между получените кодови символи и кодовата дума, съответстваща на същия клон от решетката на кодера. Кодерът (фиг. 6) се характеризира с кодови думи, които се виждат на клоновете на решетката