Конволюционно кодиране.
ОСНОВНИ СВЕДЕНИЯ ЗА КОНВОЛЮЦИОННОТО КОДИРАНЕ
Конволюционния код се генерира от преместващ регистър с краен брой състояния. В най-общия случай този регистър се състои от L (k – битови ) стъпала и n суматори по mod 2, както е показано на фигурата по-долу.
Входните битове, които се приемат за бинарни постъпват непрекъснато на входа на регистъра. При това броят на изходните битове, съответстващ на k –входни символи е n , като стойността на всеки един от тези символа ще зависи от входната комбинация и състоянието на (L. k – k ) = k(L – 1) клетки на регистъра. Скоростта на кодирането ще бъде равна на k/n. Параметърът L се нарича кодово ограничение на конволюционния код.
4.5.3.1. Генериране и описание на конволюционните кодове
Описанието на конволюционните кодове може да се извърши по няколко начина. Един от тези начини е като се използва пораждащата матрица, както това се прави при блочните кодове. Трябва да се има в предвид обаче, че тъй като тези кодове са непрекъснати, то пораждащата им матрица е полунепрекъсната. Названието на конволюционното кодиране произлиза от факта, че кодовата последователност на изхода на кодера представлява конволюция на импулсната характеристика на кодера с входната последователност.
Съществува специфичен, алтернативен на пораждащата матрица метод за описание на структурата на конволюционните кодери, заключаващ се в използването на множество от n вектори, по един за всеки суматор по mod 2. В общия случай всеки от тези вектори има размерност, равна на L.k и съдържа толкова единици, колкото са връзките на суматора с тригерите на регистъра.
Друг начин на задаване на конволюционните кодери е чрез пораждащите ги полиноми. При такова представяне, изходната последователност на кодера може да се разглежда като получена чрез умножението на входната последователност на пораждащия полином, където умножаването на многочлените се извършва над полето GF(2). Когато пораждащите полиноми са неравни на единица, то генерирания от тях код е не систематичен.
Друг широко използван метод за описание на конволюционните кодове е графическия. Съществуват три различни начина за графическо описание на кодовете:използване на кодово дърво, използване на решетеста диаграма и използване на диаграма на състоянията.
На следващата фигура е дадено кодовото дърво, описващо работата на кодера, изобразен на фигурата. Предполага се че началното състояние на кодера е 000. Всеки входен символ, равен на 0 води до придвижване на дървото нагоре, а всеки входен символ, равен на 1 – надолу. Комбинацията, изписана на всеки клон е изходна. Така при входна комбинация 1001, кодера ще генерира изходна комбинация 111001011111. пътят по дървото за този случай, e показан с прекъсната линия. Ясно е, че при нарастване на дължината на входната комбинация, броят на възможните пътища, а следователно и структурата на дървото ще нараства експоненциално. За щастие този ръст може да се ограничи. Това е възможно, тъй като в структурата на дървото се забелязва периодичност.
Кодер с L = 3, k =1, n = 3, g 1 (x) = 1; g 2 = 1 + x2 ; g 3 = 1 + x + x2
Кодово дърво на конволюционен код с R c = 3, L = 3
Наистина след L такта, кодовите комбинации в изхода на кодера започват да се повтарят. Това е така, защото 3 – битовата комбинация след всеки такт се определя от входния бит и състоянието на първия и втория тригер на регистъра, т.е. от следните два символа от всеки клон на дървото. Тези два символа определят четири състояния на тригерите, означени като а = 00, b = 01, c = 10, d = 11. Ако всеки възел на дървото се означи със съответното състояние на клона (последните два символа), ще има два възела а, два възела b, два възела c и два възела d. От кодовото дърво се вижда, че клоновете, излизащи от възли с еднакво означение са идентични в смисъл, че генерират еднакви три битови комбинации. Това показва, че два възела от дървото, имащи еднакви означения, могат да се слеят в един. Така кодовото дърво придобива нова, по-компактна форма, наречена решетеста диаграма.
Решетеста диаграма за код с L = 3, R c = 1/3
Вижда се също така, че след началното си състояние диаграмата съдържа четири възела във всеки тактов интервал, съответстващи на четирите състояния на регистъра a, b, c и d. След втория тактов интервал във всеки възел влизат два и излизат два пътя. От двата излизащи пътя, единият съответствува на входен бит 0, а другият - на 1. движението по решетеста диаграма, при входна последователност 1001 е показано със стрелки. Вижда се, че генерираната от кодера конволюционна последователност е същата, както при кодовото дърво.
Тъй като изходната последователност на разглеждания кодер зависи от вида на водния бит и състоянието на регистъра, то кодера може да се разглежда като автомат с краен брой състояния, работата на който може да се опише с т.н. диаграма на състоянията.
В случая диаграмата е просто граф на възможните състояния на кодера и възможните му преходи от едно състояние в друго. За кодера от фигурата по-горе тази диаграма е представена на следната фигура.
Диаграма на състоянията на кодер с R c = 1/3, L = 3
От диаграмата се вижда че възможните преходи от едно състояние в друго са: , където с e означен преходът от състояние ά в състояние β, когато входния бит е 1.
Трите бита във всеки клон на диаграмата показват изходната последователност, генерирана при постъпването на всеки входен бит. При това с пунктир са означени преходите при входен бит 1, а с непрекъсната линия преходите, при входен бит 0.
Даденото по-горе описание на конволюционните кодове е за скорост на кодиране R c = 1/n и кодовото ограничение L = 3, но то може да бъде обобщено и за скорост, равна на m/n и произволноL. В този случай, кодовото дърво ще се характеризира с 2m клона, излизащи от всеки възел. Решетестата диаграма и диаграмата на състоянията ще се характеризират със 2 m(L-1) възможни състояния, като до и от всяко състояние ще водят 2m пътя (след нулевия преход).
4.5.3.2. Декодиране на конволюционните кодове
За разлика от блоковите кодове, при които отделните кодови комбинации имат строго определена дължина n, то конволюционните кодове са непрекъснати и неразделими. Разбира се, за улесняване на декодирането, приемната полубезкрайна последователност от символи може принудително да бъде разсичана така, че обработвания блок да има някаква крайна продължителност. За да се нулира регистъра след обработка на подобен блок, е необходимо след последния информационен символ да се включат (при кодирането) L – нулеви символа, наричани крайни бита или “опашка”.тъй като последните не носят полезна информация, то скорост на кодиране, пада под Rc. За да бъде действителната скорост на кодирането колкото се може по-близо до m/n, то е необходимо дължината на отсичания обработван блок да бъде значително по-голямо от кодовото ограничение L. Така разсичания периодически конволюционен код ще бъде равнозначен на боклов код със сравнително голяма дължина на кодовите си думи. При тактов подход на обработка, за да се извърши оптимално кодиране, не е необходимо да се изчислява кодовото разстояние на всички възможни разклонения на кодовото дърво или в решетестата диаграма.
За декодирането на конволюционните кодове съществуват множество алгоритми, но в клетъчните радиокомуникации широко приложение е намерил алгоритъма на Витерби. Този алгоритъм е приложим в системите с цифрова обработка на сигналите и е еднакво ефективен при демодулатори работещи, както в режим с твърдо, така и в режим с меко решение.демодулаторът работи в режим с твърдо решение, когато изходът му се квантува и броят на нивата на квантуване е 2. Когато броят на нивата, с които се квантува изходът на демодулатора е по-голям от 2, се казва че той работи в режим с меко решение. Метриката, която се използва за определяне на кодовите разстояния в декодера на Витерби, включен към изхода на демодулатор с твърдо решение, е Хемингова, а в декодера, работещ с меко решение – Евклидова.
В най-общ вид, задачата за декодирането на конволюцоионните кодове може да се разглежда, като задача за намиране на правилния път от входа до изхода на решетестата диаграма, с помощта на някакви правила за декодирането. Очевидно, идеален би бил изборът, който минимизира броя на грешките, при сравняването на изходната последователност с входната. Опитите обаче за апаратна реализация на подобна задача се оказват за сега безуспешни. Практически, много по-целесъобразни са се оказали опитите за избор на път по диаграмата, който минимизира вероятността за възникване на грешка в последователността, т.е. път, които преди всичко се съгласува най-добре с приетата комбинация. Макар такъв подход и да не гарантира минимизирането на вероятността за грешка на символ, то може да се твърди, че за почти всички кодове (с изключение на патологично лошите, наричани още катастрофични) малката вероятност за възникване на грешки в последователността, водят до малка вероятност за възникване на грешка на символите. Поради тази причина всички опасения, възникващи в следствие не оптималността на такъв подход, се оказват несъществени.
И наистина, едно от основните предимства на представянето на конволюционните кодове чрез решетеста диаграма, е че броят на клоните остава постоянен, равен на 2L -1 , независимо от нарастването на броя на входните символи. Това се дължи на обстоятелството, че излишните части на кодовото дърво се отъждествяват, както беше изтъкнато по-горе. Вследствие на това отъждествяване, дори в даден момент де е избран неверен път, то по-късно този път може да се слее с верния, което за добрите кодове може да се разглежда като събитие, настъпващо с голяма вероятност. По този начин избрания път се превръща в максимално правдоподобен.
Алгоритъмът на Витерби използува сравнително проста интерактивна процедура, предложена от А. Витерби през 1967г. За определяне на максимално правдоподобния път в решетестата диаграма. На пръв поглед, ако се изходи от предпоставката, че броя на възможните пътища расте експоненциално с увеличаване на дължината на входната последователност, задачата за оценка на последователността по метода на максималното правдоподобие е почти нерешима. А.Витерби показва, че решаването на тази задача не само е възможно , но е и сравнително лесно. Методът за намирането на подобна оценка се заключава в непосредственото изчисляване на метриката на всеки път от диаграмата. В началото броят на пътищата наистина расте експоненциално с нарастване на дължината на входната последователност, но след това се появява възможност за изключване на толкова пътища във всеки клон, колкото отново възникват. По такъв начин се оказва съставянето на списък със сравнително голям брой пътища, в който винаги да е включен най-правдоподобния път за дадена входна последователност.
4.5.4. ДЕКОРЕЛАЦИЯ НА ГРЕШКИТЕ В КАНАЛНИТЕ КОДЕРИ (ДЕКОДЕРИ)
За да направим разпределението на грешките на входа на декодера по-равномерно, цифровата последователност от изхода на кодера се подлага на цифрово преобразуване, заключаващо се в изменение на реда на следване на символите. На приемния край, последователността от изхода на демодулатора е необходимо да се подложи на аналогично преобразуване, заключаващо се във възстановяване на реда на следване на символите, преди те да се пот дадат на входа на декодера. Нужно е да се отбележи при това, че ако демодулатора квантува всеки кодов символ на q – бита, то устройството за възстановяване на реда на следване на символите (УВРСС) се нуждае от q – пъти по-голям обем от памет, от колкото устройството за изменение реда на следване на символите (УИРСС).
4.5.4.1. Периодични устройства за де корелация
Периодични устройства за де корелация се наричат такива УИРСС (УВРСС), при който разместването (или наместването) на символите представлява периодическа функция на времето. Тези устройства в редица случаи се предпочитат пред псевдослучайните, поради своята простота. Биват блокови и конволюционни.
Блокови устройства за де корелация.
На входа на тези устройства символите постъпват във вид на блокове и УИРСС извършва едно и също разместване на всеки блок от символи. По конкретно това разместване се извършва, като символите се записват в стълбовете на матрица, съдържаща N реда и B стълба. При предаването им в канала символите се четат по редове. При такъв подход, последователните символи от водния блок се оказват разделени помежду си от N символа. Подобно устройство се нарича блоково (B, N) УИРСС. На приемния край в УИРСС се извършва обратната операция – записа на символите се извършва по редове, а четенето по стълбове.
Най-важните свойства на блоковата де корелация се заключават в следното:
Всеки пакет от грешки, имащи дължина b < B се трансформира в изхода на УВРСС в единични грешки, разделени от не по-малко от N символа;
Всеки пакет от грешки с дължина b = r.B, където r > 1, се трансформира в пакети от грешки с дължина не по-голяма от r символа, като всяка двойка от тези пакети е разделена помежду си с не по-малко от N – r символа;
Всяка периодическа последователност от единични грешки, разделени помежду си с В символа, се трансформира еди пакет от грешки с дължина, равна на N символа;
Времето на задържане на символите в блоковия декорелатор е равно на 2NB символа и следователно всяко от устройствата му се нуждае от памет с капацитет, равен на NB символа;
Параметрите на УИРСС се избират от изискването, дължината на очакваните пакети от грешки в канала b, да не превишава В. При нестационарни характеристики на пакета от грешки, УИРСС, съгласно третото свойство, може да работи неустойчиво. Що се отнася до избора на N, то той зависи от използваната схема за канално кодиране, но в повечето случай N трябва да бъде по-голямо от дължината на сегмента, за който се извършва декодирането. Така за блоковите кодове, N трябва да бъде по-голямо от дължината на блока, а при конволюционните кодове – по-голямо от дължината на кодовото ограничение. При такъв избор, всеки пакет от грешки с дължина b < B ще води до не повече от една грешка във всеки отрязък, имащ дължина, равен на дължината на кодовото ограничение.
Блоковите декорелатори предявяват същите изисквания по отношение на синхронизацията както при блоковите кодове. УВРСС не може да работи правилно, ако не му е известно началното на всеки блок от символи в изхода на УИРСС. Естествено е в този случаи да не може да се осъществи правилен процес на коригиране на грешките. УИРСС и УВРСС се синхронизират с помощта на един от известните стандартни методи за кадрова синхронизация, при които периодически в кодовите последователности в устройството за разместване се вмъкват специални синхронизиращи комбинации с добри корелационни свойства. При този метод в кодовите последователности се вмъкват обикновено 1 – 2 % допълнителни символи. Друг подход при синхронизацията на двете устройства, не изискващ вмъкване на допълнителни символи, се заключава в замяната на някой кадрови символи със синхро-комбинация, която след декодирането се изтрива.
Конволюционни устройства за де корелация
Подобно устройство е дадено на фигурата по долу и е известен като декорелатор на Форни. Устройството работи по следния начин. Цифровия поток от кодера постъпва в набор от В регистъра с нарастваща дължина. При встъпването на всеки следващ символ, комутаторът превключва изхода на сумиращото устройство към входа на следващия регистър. В същото време, най-стария кодов символ, записан в този регистър, постъпва в канала. Това е възможно, ако комутаторите от входа и изхода на предаващата страна работят синхронно. На приемната страна, устройството за възстановяване на реда на следване на символите осъществява обратната операция. За точното възстановяване на реда на следване на символите е необходимо комутаторите в предавателната и приемната страна да работят също синхронно. На практика, много често вместо преместващи регистри, се използва памет с произволен достъп със съответстващо управление на достъпа.
Най-важните свойства на конволюцоионните декорелатори са:
Минималното разстояние между кои и да са два символа в изхода на УИРСС при условие, че това разстояние на входа е било N = MB , е равно на В;
От това следва, че всеки пакет от грешки с дължина b < B в канала се преобразува в единични грешки, разделени с не по-малко от N символа;
Периодическа последователност от единични грешки, намиращи се на разстояние N + 1 символа една от друга, се преобразува в устройството за възстановяване на реда на следване на символите в пакет с дължина, равна на B;
Общото време на задържане на този тип декодери е N(B – 1) символи и това налага във всяко от устройствата на декорелатора да се използва памет с обем N(B – 1)/2 символа, което е два пъти по-малко, от колкото в устройствата на блоковия декорелатор.
Параметрите B и N на декорелатора се избират по същия начин, както при блоковите декорелатори. Що се отнася до синхронизацията, то при конволюционните декорелатори тя се осъществява много по-лесно. Това е така защото, при последните, съществуващата неопределеност при определяне на позициите на символите е равна на В, докато в блоковите декорелатори, тя е NB. Кадровата синхронизация може да се извършва, както при блоковите кодове, така и по-специални, твърде интересни методи.
4.5.4.2. Псевдослучайни устройства за де корелация
Този тип декорелатори се характеризират със сравнително по-голяма устойчивост на работата си и се предпочитат в случаите, когато характеристиките на канала (или на пакетите) от грешки притежават известна нестационарност, т.е. изменят се във времето (подобна ситуация може да възникне например, когато канала е подложен на преднамерени смущения).
Тази способност на псевдослучайните декорелатори се дължи на сравнително по-сложната им структура или алгоритъма на работа.
На фигурата е дадена типична схема на УИРСС на подобен декорелатор. Символите от изхода на конволюционния кодер се записват последователно в паметта на УИРСС, която е от типа ППД (памет с произволен достъп). След записа на целия блок, имащ дължина L, тези символи се разместват, посредством четене на паметта по закона на псевдослучайната последователност (ПСП), генерирана от генератора и записана в адресируемата памет. За правилната работа на устройството са необходими две ППД, работещи в противофаза: когато в едната става записване на символите, в другата се извършва четене. След завършване на цикъла двете ППД сменят ролята си и се избира ново псевдослучайно разместване. Трябва да се отбележи, че ако разместването във всеки блок се извършва по закона на една и съща ПСП, то е възможно съществуването на някой комбинации от адитивните и преднамерените смущения, които влошават характеристиките на декорелатора. За избягване на този недостатък на декорелатора е необходимо често да се променя генерираната ПСП.
Един от често използваните методи се заключава в записването на определен брой различни ПСП в ПЗУ и в случайния избор на една от тях за разместване на символите във всеки блок. Типичния брой ПСП варира от 10 до 100, в зависимост от критерия, определящ качеството на комуникационната система. Практически генерирането на тези последователности се извършва от преместващи регистри с логически обратни връзки, които се определят от примитивни полиноми. Тези полиноми могат да бъдат записани в ПЗУ. Например ПЗУ 64х10 ще съхранява 64 полинома от 10 степен, генериращи ПСП с максимална дължина (М – ПСП). Броят на елементите във всяка последователност ще бъде равен на L = 210 – 1 =1023. избора на даден многочлен от това ПЗУ позволява да се управлява логическата обратна връзка на регистъра, което дава възможност за генерирането на 64 различни начина на разместване на символите. Освен това е възможно получаването на 1023 различни циклични измествания на всяка от тези 64 М – ПСП като се променя началния вектор в преместващия регистър. Структурата на псевдослучайната УБРСС е аналогична.
Псевдослучайните декорелатори се използват в каналните кодери (декодери) на клетъчните системи с CDMA – радио технологии.
Няма коментари:
Публикуване на коментар