Процес на циклично кодиране. Циклични кодове Проценти на открити множество грешки

Това е подклас от линейни кодове, които имат свойството gem, че цикличната пермутация на символи в кодиран блок произвежда друг възможен кодиран блок от същия код. Цикличните кодове се основават на прилагането на идеи от алгебричната теория на полето на Галоа1.

Много от най-важните шумоустойчиви кодове на комуникационните системи са

по-специално циклични, базирани на структурите на крайната аритметика

Галоа полета. Полее набор от елементи, които имат крайно поле

Заглавията на операциите са в кавички, защото не винаги са общоприети аритметични операции. Полето винаги съдържа нулев елемент (0) или нула и единичен елемент (1) или единица. Ако броят релементи на полето са ограничени, тогава полето се извиква крайно поле, или крайно поле на Галоа, и се обозначава GF(q)yКъде q-полеви ред. Най-малкото поле на Галоа е поле от два елемента GF( 2), състоящ се само от два елемента 1 и 0. За да

1 Еварист Галоа (1811 – 1832) – френски математик, поставил основите на съвременната алгебра.

извършване на операции върху елементи GF( 2) не са довели до излизане извън границите на това поле, те се извършват по модул 2 (като цяло това се определя от реда на полето за прости полета на Галоа).

Полето има редица специфични математически свойства. За елементите на полето се дефинират операции събиране и умножение и резултатите от тези операции трябва да принадлежат към едно и също множество.

За операциите събиране и умножение се следват обичайните математически правила за асоциативност - А + (б + в) = (а + б)+ c, комутативност - a + b = b + aи А b = b Аи дистрибутивност - А (б+ в) = А b + А с.

За всеки полеви елемент Атрябва да има обратен елемент на събирането (-A)и ако Ане е равно на нула, обратен елемент на умножението (th').

Полето трябва да съдържа адитивна единица -елемент 0 такъв, че А + 0 = Аза всеки полеви елемент А.

Полето трябва да съдържа мултипликативна единица -елемент 1, така че aL = aза всеки полеви елемент А.

Например, има полета с реални числа, рационални числа и комплексни числа. Тези полета съдържат безкраен брой елементи.

Всъщност всички множества, образувани чрез циклична пермутация на кодова дума, също са кодови думи. Така например, цикличните пермутации на комбинацията 1000101 също ще бъдат кодови комбинации 0001011, 0010110, 0101100 и т.н. Това свойство прави възможно значително опростяване на устройствата за кодиране и декодиране, особено при откриване на грешки и коригиране на една грешка. Вниманието към цикличните кодове се дължи на факта, че присъщите им високи коригиращи свойства се реализират на базата на сравнително прости алгебрични методи. В същото време, за декодиране на произволен линеен блоков код, по-често се използват таблични методи, които изискват голямо количество памет на декодера.

Цикличният код е линеен блоков код. (n, k)-код, който се характеризира със свойството цикличност, т.е. преместване наляво с една стъпка, всяка разрешена кодова дума също дава разрешена кодова дума, принадлежаща към същия код и за която наборът от кодови думи е представен от набор от полиноми от степен (стр- 1) или по-малко, делимо на генериращия полином g(x)степени r=n-k yкоето е фактор на бинома X n+

В цикличен код кодовите думи са представени от полиноми (полиноми)

Къде п -дължина на кода; А аз -коефициенти на полето на Галоа (стойности на кодовата комбинация).

Например за кодовата комбинация 101101 полиномната нотация има формата

Примери за циклични кодове са кодове за равномерна проверка, кодове за повторение, кодове на Хеминг, PC кодове и турбо кодове.

Код на Хеминг. Възможността за коригиране на грешки в кода на Хеминг е свързана с минималното разстояние на кода d0.Всички грешки в множествеността са коригирани р= cnt (d 0- l)/2 (тук cnt означава „цяло число“) и се откриват грешки в множествеността d 0 - 1. И така, когато проверявате за нечетен паритет d Q = 2 и се откриват единични грешки. В кода на Хеминг d 0 = 3. Освен информационните категории се въвежда L= log 2 Q на излишните контролни битове, където Q-брой информационни битове. Параметър Лзакръглено до най-близкото по-високо цяло число. L-битовият контролен код е обърнат резултат от побитово добавяне (добавяне по модул 2) на числата на тези информационни битове, чиито стойности са равни на единица.

Пример 7.7

Нека имаме основния код 100110, т.е. Q = 6. Да дефинираме допълнителен код.

Решение

Ние намираме това Л= 3 и допълващият код е

където P е символът на операцията за побитово добавяне и след инверсия имаме 000. Сега допълнителният код ще бъде предаден заедно с основния код. При приемника допълнителният код отново се изчислява и сравнява с предадения. Кодът за сравнение се записва и ако е различен от нула, тогава неговата стойност е номерът на погрешно получения бит от основния код. Така че, ако се приеме кодът 100010, изчисленият допълнителен код е равен на инверсията на 010Ш10 = 100, т.е. 011, което означава грешка в 3-тата цифра.

Обобщение на кодовете на Хеминг са цикличните BCH кодове, които правят възможно коригирането на множество грешки в приетата кодова комбинация.

Кодове на Рийд-Соломонсе основават на полета на Галоа или крайни нули. Аритметични операции събиране, изваждане, умножение, деление и др. над елементите на крайна нула дават резултат, който също е елемент от тази нула. Рийд-Соломон енкодер или декодер задължително трябва да изпълнява тези операции. Всички операции за внедряване на кода изискват специален хардуер или специализиран софтуер.

Турбо кодове.Излишните кодове могат да се използват независимо или под формата на комбинация от няколко кода, когато набори от символи на един излишен код се считат за елементарни информационни символи на друг излишен код. Това сдружение започна да се нарича каскаднокод. Огромно предимство на конкатенираните кодове е, че тяхното използване прави възможно опростяването на енкодера и особено на декодера в сравнение с подобни устройства на несвързани кодове със същата дължина и излишък. Каскадното кодиране доведе до създаването на турбо кодове. Турбо коднаричаме паралелна сигнална структура, състояща се от два или повече систематични кода. Основният принцип на тяхната конструкция е използването на няколко паралелно работещи компонентни енкодера. Като компонентни кодове можете да използвате както блокови, така и конволюционни кодове, кодове на Хеминг, PC код, BCH и др. Използването на перфорация (пробиване) ви позволява да увеличите относителната скорост на турбо кода, като адаптирате неговата коригираща способност към статистическите характеристики на комуникационния канал. Принципът на генериране на турбо код е следният: входен сигнал X,състоящ се от ДОбит, захранван паралелно с Нпреплитачи. Всеки от последните е устройство, което пренарежда елементи в блок от ДОбитове в псевдослучаен ред. Изходният сигнал от интерливърите - символи с променен ред - се изпраща към съответните елементарни енкодери. Двоични последователности x p i= 1,2,..., JV, на изхода на енкодера има контролни символи, които заедно с информационните битове съставляват една кодова дума. Използването на интерливър прави възможно предотвратяването на появата на последователности от корелирани грешки при декодиране на турбо кодове, което е важно при използване на традиционния метод на повтарящо се декодиране при обработката. В зависимост от избора на компонентен код, турбо кодовете се разделят на конволюционни турбо кодове и блокови продуктови кодове.

6. Коригиране на грешки с помощта на циклични кодове

В раздел 3 беше показано, че за декодиране на правилно получена кодова дума, т.е. за намиране на съответната информационна дума, е достатъчно да се раздели полиномът, съответстващ на получената кодова дума, на генериращия полином на кода. Въпреки това, ако възникнат грешки по време на предаване, тогава тези грешки трябва да бъдат коригирани по време на процеса на декодиране.

Тъй като цикличните кодове са линейни, процесът на откриване и коригиране на грешки е свързан с намирането на получения векторен синдром. Спомнете си, че векторният синдром uсе изчислява като произведение на вектора и транспонираната контролна матрица на кода, т.е. s u= ъХ Т. В случай на цикличен код, синдромът е равен на остатъка от разделянето на съответния полином на генериращия полином на кода, ако матрицата за проверка е конструирана по определен начин. С други думи, ако ж(х) е генериращ полином на кода, тогава векторният синдром uравен на остатъка от делението u(х) включено ж(х). Ако няма грешки, тогава остатъкът и следователно синдромът на получения вектор е равен на 0.

За да коригираме грешките, трябва да изградим таблица, в която в една колона ще има всички възможни вектори на грешки, които този кодможе да коригира, а във втората колона - съответните синдроми. Корекцията на грешки, обща за всички редови кодове, би била следната:

1. За приета дума намерете синдрома на полинома, съответстващ на приетата дума.

2. Ако синдромът не е равен на 0, тогава с помощта на резултантния синдром (остата от разделението) намираме вектора на грешката, съответстващ на него в таблицата.

3. Коригирайте получената дума, като добавите модул 2 към изчисления вектор на грешката.

Първата стъпка, която се извършва чрез умножаване на получената дума по транспонираната матрица за проверка на четността, е много проста за циклични кодове, ако матрицата зе матрицата за проверка на систематичния код. в този случай й-ти ред на транспонираната матрица зТсъответства на остатъка от полином x n -1- йчрез генериращия полином на кода, а синдромът е равен на остатъка от деленето на полинома, съответстващ на получената дума, на генериращия полином на кода.

Пример:Разгледайте цикличния (7,1) код, генериран от полинома ж(х) = х 6 + х 5 + х 4 + х 3 + х 2 + х+1. Кодът се състои от две думи 0000000 и 1111111 и коригира всички комбинации от 3 или по-малко грешки. Всички генератори са булеви вектори с дължина 7, тегла 0, 1, 2 и 3. Матрицата за проверка се конструира с помощта на коефициента ( х+1) от деление х 7 +1 на х 6 + х 5 + х 4 + х 3 + х 2 + х+1 и изглежда

Нека се приеме думата 11101101, която съответства на полинома х 6 + х 5 + х 4 + х 2 + 1. Остатъкът при разделянето на този полином на генериращия полином на кода е равен на х 3 + х. Чрез директна проверка можете да проверите това, когато умножавате вектор u= 1110101 на транспонирана матрица зТ, същото като при умножаване на вектора 0001010 по зТрезултантният вектор е 0001010, което съответства на полинома х 3 + х. Вектор, съответстващ на полином х 3 + х, има тегло 2, т.е. е генератор на косет. Събирайки получения вектор 11101101 с генератора 0001010, получаваме кодовата дума 1111111, т.е. грешката ще бъде коригирана.

За линейните кодове броят на различните синдроми е 2 п - к, Къде п-к- брой знаци за проверка. Следователно, за кодове с голяма дължина на кодовата дума, т.е. с достатъчно голям брой символи за проверка, таблицата на синдромите се оказва много голяма и ще отнеме много време, за да се намери векторът на грешката. За да намалите броя на редовете в тази таблица за циклични кодове, можете да използвате строгата математическа структура на такива кодове. Основната теорема е теоремата на Мегит, която установява връзка между цикличните смени на вектор и техните остатъци от делене с генериращия полином на кода.

Теорема 6.1. (Мегит). Нека s- векторен синдром uдължина п. Синдром на циклично изместване на вектора uсъвпада със синдрома на вектор, съответстващ на полином xs(х).

Пример:Разгледайте (7.4) кода на Хеминг, който е цикличен код, генериран от полинома ж(х) = х 3 + х+ 1. Двоичният вектор 1011000 е кодова дума, тъй като съответният полином х 6 + х 4 + х 3 се дели на ж(х). Да предположим, че по време на предаването на тази кодова дума е имало една грешка в бита, съответстващ на х 4, и думата се приема u= 1001000. Синдром sна приетия вектор е 110, което съответства на полинома х 2 + х.

Помислете за цикличното изместване 0010001 на вектора u. Съответства на полинома х 4 + 1. Чрез директна проверка можете да проверите, че остатъкът от делението на полинома х 4 + 1 на полином х 3 + х+ 1 е равно х 2 + х+ 1, т.е. синдромът на вектора 0010001 е равен на 111. Остатъкът от делението на полинома xs(х) = х 3 + х 2 на х 3 + х+ 1 също е равно х 2 + х + 1.

Използвайки теоремата на Мегит, само синдроми на вектори на грешки, съответстващи на грешки в най-значимия бит, могат да се съхраняват в таблицата на синдромите. Процедурата за коригиране на грешки включва следните стъпки:

1. Намерете получения векторен синдром, като разделите съответния полином на генериращия полином на кода. Ако остатъкът от делението, съдържащо се в регистъра, е 0, тогава няма грешки и частното от делението е желаната информационна дума. В противен случай сравняваме остатъка от разделението с всички синдроми, съдържащи се в таблицата.

2. Ако остатъкът съвпада с един от синдромите в таблицата, тогава добавяме съответния вектор на грешка към получената дума, разделяме получената дума на генериращия полином на кода; частното на делението е необходимата информационна дума. Ако остатъкът xs(х) не отговаря на нито един от синдромите в таблицата, умножете s(х) включено хи разделете полинома xs(х) към генериращия полином на кода.

3. Изпълнете стъпка 2 до след това стростаналата част от стъпките не съвпада с един от синдромите в таблицата. След това циклично изместваме съответния вектор на грешката стрведнъж добавете получения вектор към получената дума, разделете получената дума на генериращия полином на кода; частното на делението е необходимата информационна дума.

Пример:Разгледайте цикличния (7,4) код на Хеминг, генериран от полинома ж(х) = х 3 + х+ 1. Съответната декодираща таблица със синдроми има следната форма.

и да предположим, че е възникнала една грешка в предадената кодова дума 0001011, т.е. например е получена думата 0101011, на която съответства полиномът х 5 + х 3 + х+ 1. Остатък при деление на многочлен х 5 + х 3 + х+ 1 върху генериращия полином на кода ж(х) = х 3 + х+ 1 е равно х 2 + х+ 1, т.е. синдромът на получения вектор е различен от 0 и е равен на 111. В таблицата няма такъв синдром и следователно няма грешки в най-значимата цифра. Умножение на полином х 2 + х+ 1, съответстващ на синдром 111, на хи разделете получения полином х 3 + х 2 + хна ж(х). Остатък от полином х 3 + х 2 + хна х 3 + х+ 1 е равно х 2 + 1, т.е. синдром 101, съответстващ на остатъка, съвпада със синдрома в намалената таблица за декодиране. Съответно генераторът 100000 на класа coset се измества с един бит наляво и полученият вектор 0100000 се добавя към получения вектор 0101011. Резултатът е думата 0001011, която е предадената кодова дума, т.е. грешката ще бъде коригирана .

Този декодер може да бъде опростен. По-специално, когато завъртате получена дума, много от коригираните модели на грешки могат да се появят многократно. Ако премахнете един от тези синдроми, тогава със съответното циклично изместване грешката все още ще бъде открита. Следователно за всяка такава двойка е достатъчно да запомните само един синдром.

Най-простият цикличен код ви позволява да откривате единични грешки и грешки с нечетна множественост. Генериращият полином на този код има формата Сред нередуцируемите полиноми, включени в разширението, този полином е полиномът с най-малка степен, следователно, за произволен брой информационни битове е необходим само един контролен бит. Стойността на символа на този бит осигурява четността на броя единици във всяка разрешена кодова комбинация. Полученият цикличен паритетен код е способен да открива не само единични грешки в отделни битове, но и грешки във всеки нечетен брой битове.

Пример. Конструирайте цикличен код за Тъй като генериращият полином е полином от 1-ва степен, броят на контролните цифри Следователно, за да конструираме цикличен код, ние конструираме генерираща матрица

За да конструираме допълнителна матрица, намираме остатъците от разделянето на последния ред на единично транспонираната матрица, допълнена с нули, на избрания полином:

Така допълнителната матрица C,k има формата

Сега изграждаме генериращата матрица

Редовете на тази матрица са първите три кодови комбинации. Останалите допустими комбинации могат да бъдат получени чрез сумиране по модул две на всички възможни комбинации от редове на матрицата. Получените унищожени кодови комбинации са дадени в табл. 39.

Таблица 39 (вижте сканирането)

От добре известен интерес е разглеждането на следния най-прост код, образуван с помощта на нередуцируем полином от втора степен

Общата форма на генериращата матрица на цикличен код, образуван от полином, се различава в структурата на допълнителна матрица с две колони.

Лесно е да се провери, че при разделяне на даден генериращ полином мономите, изразяващи низовете

идентификационна матрица (за намиране на допълнителна матрица се формират три вида остатъци: 11, 01 и 10. Следователно теглото на всяка комбинация от резултантния -код ще бъде поне две. Минималното кодово разстояние между всеки две комбинации също е 2. Но най-простият също се характеризира със същите стойности код с една проверка на четност, образувана от бином от първа степен възможно е да се открият не само всякакви грешки с нечетна множественост, но и всякакви сдвоени съседни грешки, както и всички грешки, разделени от един неповреден елемент.

Клас от линейни кодове, т.нар шаически кодове. Името идва от основното свойство на тези кодове: ако определена кодова комбинация принадлежи към цикличен код, тогава комбинацията, получена чрез циклична пермутация на оригиналната комбинация (циклично изместване), също принадлежи към този код:

Второто свойство на всички разрешени комбинации от циклични кодове е делимостта им без остатък на избран полином, наречен генериращ.

Тези свойства се използват при конструиране на кодове за кодиращи и декодиращи устройства, както и при откриване и коригиране на грешки.

Цикличните кодове са цяло семейство устойчиви на грешки кодове (една от разновидностите на които са кодовете на Хеминг), осигуряващи по-голяма гъвкавост по отношение на възможността за внедряване на кодове с необходимата способност за откриване и коригиране на грешки, които възникват при предаване на кодови комбинации през комуникационен канал. Цикличният код се отнася до систематични блокови (l, &) кодове, в които допървите цифри представляват комбинация от първичния код, а следващите (l - до)цифрите са проверка.

Конструкцията на циклични кодове се основава на операцията за разделяне на предаваната кодова комбинация на генериращия нередуцируем полином от степен Ж.Остатъкът от делението се използва за формиране на контролни цифри. В този случай операцията за деление се предшества от операция за умножение, която измества комбинацията от ^-битов информационен код наляво с Жизхвърляния.

При декодиране на получената n-битова кодова комбинация отново се извършва разделяне от генериращия (генериращ, формиращ) полином.

Синдромът на грешка в тези кодове е наличието на остатък, когато получената кодова комбинация се раздели на генериращия полином. Ако синдромът равно на нула, тогава се счита, че няма грешки. В противен случай, използвайки получения синдром, можете да определите цифрата на получената кодова комбинация, в която е възникнала грешката, и да я коригирате.

Въпреки това не може да се изключи възможността за възникване на множество грешки в кодови комбинации, което може да доведе до фалшиви корекции и (или) неоткриване на грешки при трансформиране на една разрешена комбинация в друга.

Нека общият брой битове в блока е равен на i, от които полезна информацияносят в себе си Тбита, тогава в случай на грешка е възможно да се коригират j бита. Зависимост 5 от пи Тза кодове може да се определи от таблицата. 2.6.

Таблица 2.6

Зависимост на общия брой битове на комбинации от броя на информационните и коригираните битове

Увеличаване на разликата (p - t),можете не само да увеличите броя на коригираните битове s,но и за откриване на множество грешки. Процентите на откритите множество грешки са дадени в табл. 2.7.

Таблица 2.7

Проценти на открити множество грешки

Удобно е да се описват циклични кодове и да се конструират с помощта на полиноми (или полиноми). Записването на комбинация под формата на полином се използва за показване по формализиран начин на операцията на циклично изместване на оригиналната кодова комбинация. По този начин кодовата комбинация от „-елементи“ може да бъде описана чрез полинома (стр- 1) степени:

Къдеa„_j =(0, 1) иa„_, =0 съответства на нулеви елементи от комбинацията, d„_, = 1 - ненула;аз- цифрен номер на кодовата комбинация.

Нека си представим полиноми за конкретни комбинации от 4 елемента:

Операциите събиране и изваждане са еквивалентни и асоциативни и се изпълняват по модул 2:

Примери за извършване на операции:

Операцията за деление е обичайното деление на полиноми, но вместо изваждане се използва събиране по модул 2:

Циклично изместване на кодова комбинация - преместване на нейните елементи отдясно наляво, без да се нарушава редът им, така че най-левият елемент да заеме мястото на най-десния.

Основните свойства и наименованието на цикличните кодове са свързани с факта, че всички разрешени комбинации от битове в предаденото съобщение (кодови думи) могат да бъдат получени чрез циклично изместване на някаква първоначална кодова дума.

Да приемем, че са дадени оригиналната кодова комбинация и съответният полином:

Да се ​​размножаваме О)на X:

Тъй като максималната степен Xв кодова комбинация от дължина пне надвишава (l - 1), тогава от дясната страна на получения израз, за ​​да се получи оригиналният полином, е необходимо да се извади О"- 1). Изваждане О"- 1) се нарича вземане на остатъка по модул (x n - 1).

Преместването на оригиналната комбинация от / мерки може да бъде представено както следва: a(x)? U - О"- 1), т.е. умножение О) x" и вземане на остатъка по модул (x" - 1). Вземането на остатъка е необходимо, когато се получава полином със степен, по-голяма или равна на стр.

Идеята за конструиране на циклични кодове се основава на използването нередуцируеми полиноми.Нередуцируем полином е полином, който не може да бъде представен като произведение на полиноми от по-ниски степени, т.е. се дели само на себе си или на един, а не на друг полином. Биномът (x" + 1) се дели на такъв полином без остатък. Нередуцируемите полиноми в теорията на цикличните кодове играят ролята на генериращи полиноми.

Връщайки се към дефиницията на цикличен код и като вземем предвид записа на операциите на циклично изместване на кодови комбинации, можем да напишем генериращата матрица на цикличния код в следната форма:

КъдеP(x)- оригиналната кодова комбинация, на базата на която са получени всички останали(Т- 1) основни комбинации;

C, = 0 илиCj =1 („O“, ако получената степен на полиномаR(x)-x'не надвишава (l - 1), или „1” - ако надвишава).

Комбинация P(x)се нарича генерираща (генерираща) комбинация. За да конструирате цикличен код, достатъчно е да изберете правилно P(x).Тогава всички останали кодови комбинации са същите като в груповия код.

Генериращият полином трябва да отговаря на следните изисквания:

• P(x)трябва да е различно от нула;
• тегло P(x) не трябва да бъде по-малко от минималното кодово разстояние: V(P(x)) > d mm;
• P(x)трябва да има максимална степен k (k -брой излишни елементи в кода);
• P(x)трябва да бъде делител на полинома (x" - 1).

Изпълнението на последното условие води до факта, че всички работни кодови комбинации на цикличния код придобиват свойството да бъдат делими на P(x)без следа. Като вземем това предвид, можем да дадем друга дефиниция на цикличен код: цикличен код е код, чиито всички работни комбинации се делят на генериращия полином без остатък.

За да определите степента на генериращия полином, можете да използвате израза r > log 2 (и + 1), където п- размер на предавания пакет в даден момент, т.е. дължина на изграждания цикличен код.

Примери за генериране на полиноми са дадени в табл. 2.8.

Таблица 2.8

Примери за генериране на полиноми

Алгоритъмът за получаване на разрешена циклична кодова комбинация от проста кодова комбинация е както следва.

Нека ни е даден полином P(x) = a g _ ( x g + a g _ 2 x g ~ 1 + ... + 1, което определя коригиращата способност на кода и броя на контролните битове до,както и оригиналната комбинация от прост елементарен код и информационни битове под формата на полином A t(x).

Изисква се да се определи разрешената комбинация от циклични кодове (и, до).

• 1. Представяме оригиналната кодова комбинация като полином A t(x).Умножете полинома на оригиналната кодова комбинация по x g: A t (x) x g.Степен на генериращия полином Жравен на стойността на най-значимия бит от оригиналната кодова комбинация.
• 2. Дефинираме контролните битове, които допълват оригиналната информационна комбинация до позволената, като остатък от разделянето на продукта, получен в предходния параграф, на генериращия

полином:

Означаваме остатъка от делението като R(x).

3. Окончателно разрешена циклична кодова комбинация

кодът ще бъде дефиниран като = И t(x)? x r + R(x).

За да се определят грешките в получената кодова комбинация, достатъчно е да се раздели на генериращия полином. Ако приетата комбинация е законна, тогава остатъкът от делението ще бъде нула. Остатък, различен от нула, показва, че приетата комбинация съдържа грешки. Въз основа на вида на остатъка (синдрома) в някои случаи също е възможно да се направи заключение за естеството на грешката и нейното местоположение и да се коригира грешката.

Алгоритъмът за откриване на грешки е както следва.

Нека "-елементни комбинации ( n = k + t).

• 1. Ние идентифицираме факта, че има грешка. Получаваме остатъка от делението на приетата комбинация A n -(x)към генериращия полином P(x): А(X)
• --- = Rq(x). Наличие на баланс R0(x)при (L 0 (x) f 0) показва P(x)

относно грешката.

2. Разделете получения полином #(x) = L„_,(X) 0 Rq (x) към генератора R g (x): W-1 = R(x),Къде R(x)- текущо салдо.

3. Сравнете LDx) и R(x).Ако те са равни, тогава грешката е възникнала в най-значимия бит. Ако не, увеличете степента на приетия полином с x и разделете отново:

4. Сравнете получения остатък с Rq(x). Ако са равни, значи грешката е във втората цифра. Ако не са равни, умножете Шшшт) x 2 и повтаряме тези операции, докато получим

R(x) =по дяволите

Грешката ще бъде в цифрата, съответстваща на числото, с което степента е увеличена щчх),плюс 1. Например при равенство R(x)и LDx)

Цикличните кодове са вид линейни групови кодове и спадат към систематичните кодове. Първоначално те са създадени, за да опростят процедурата за декодиране. Въпреки това, високата ефективност на такива кодове при откриване на грешки е осигурила широкото им използване в практиката. Удобно е да се разглежда двоичен вектор на цикличен код не като комбинация от нули и единици, а като полином от известна степен

където x е основата на бройната система, коефициентите, принадлежащи на множеството в случая двоична системаОтчитане.

Пример. Двоичният вектор може да бъде представен като полином, както следва:

Представянето на двоични вектори под формата на полиноми ни позволява да намалим операциите върху вектори до действия върху полиноми. В този случай:

добавянето на полиноми се свежда до сбора по модул от 2 коефициента с равни степени на променливата

умножението се извършва съгласно обичайното правило за умножение мощностни функции, обаче, получените коефициенти за дадена степен се добавят по модул 2;

делението се извършва съгласно правилата за разделяне на степенни функции, а операцията за изваждане се заменя със сумиране по модул 2.

Пример. Намерете сбора на полиномите

Намерете произведението на полиномите

Извършете деление на полиноми

Основното свойство на цикличните кодове е следното: ако един вектор принадлежи на цикличен код, тогава всеки вектор, получен от този, който се разглежда с помощта на циклични смени, също принадлежи на цикличен код.

Идеята за конструиране на циклични кодове се основава на концепцията за нередуцируем полином. Полиномът се нарича нередуцируем, ако се дели само на себе си и на единица и не се дели на друг полином. С други думи, нередуцируем полином не може да бъде представен като произведение на полиноми от по-ниски степени. Полиномът се дели на нередуцируем многочлен без остатък. Нередуцируемите полиноми играят ролята на генериращи полиноми в теорията на цикличните кодове. Дадени са видовете нередуцируеми полиноми от различни степени

Примери за нередуцируеми полиноми:

Цикличните кодови вектори се конструират в съответствие със следните правила. Нека е всеки двоичен вектор на някакъв естествен код; - моном от степен несводим полином от степен Тогава всеки вектор от цикличен код се формира с помощта на връзката

където е остатъкът от делението

По този начин всеки вектор от цикличен код може да бъде образуван чрез умножаване на някакъв вектор от естествен двоичен кодпо моном от степен с добавяне на остатъка от делението към получения продукт. При конструиране на циклични кодове по посочения метод подредбата на информационните битове във всеки кодов вектор е строго подредена - те заемат най-високите битове на кода. вектор, а останалите битове са контролни битове.

Пример. Векторът на естествения двоичен код има формата Формирайте вектор на цикличен код от негър, при условие че генериращият полином има формата

Нека представим вектора като полином

В резултат на разделянето на полином на полином получаваме остатъка. Ето защо

Цикличният код, както всеки систематичен код, е удобно указан в матрична форма, като се използва генерираща матрица на формата

където е транспонираната единична матрица на формата - матрицата от контролни цифри, образувани от остатъка от делението

Нека дефинираме генериращата матрица на цикличния код с дължината на информационните битове и генериращия полином.

Очевидно шаблонът за генериращата матрица има формата

За да намерим редовете от контролни цифри на матрицата, ние изчисляваме и записваме всеки вектор на матрицата за идентичност като полином

Следователно дължината на вектора на цикличния код е

(виж сканиране)

В резултат на това получаваме генериращата матрица C:

Всеки вектор на цикличен код се получава като сума върху режима на векторите на неговата генерираща матрица. Тъй като цикличният код е група, нулевият вектор винаги се присвоява на цикличния код като единичен елемент на групата."

Таблица 13.5

Пример. Конструирайте всички вектори на цикличния код, даден от генериращата матрица

Кодът е представен в табл. 13.5.

Трябва да се отбележи, че всеки цикличен код, определен от определена генерираща матрица, може да бъде представен в няколко версии, различаващи се една от друга по дължината и броя на информационните битове (с еднакви способности за откриване). Тези варианти на така наречените съкратени циклични кодове се получават чрез изтриване на последните редове и същия брой колони отляво в генериращата матрица на цикличния код. В този случай броят на контролните битове остава непроменен, а дължината на кода и броят на неговите информационни битове се намаляват съответно с количество, равно на броя на зачеркнатите редове и колони на генериращата матрица.

Пример, цикличен код е даден от неговата генерираща матрица

Нека задраскаме последните шест реда и първите шест колони отляво. Получаваме генериращата матрица

Характеристиките (от гледна точка на откриване на грешки) на получения код са същите като тези на цикличния код, представен от генериращата матрица

Конструирането на циклични кодове със зададени параметри е свързано с избора на генериращ несводим полином. Генериращият полином се избира въз основа на следното условие: степента на полинома трябва да бъде равна на броя на контролните битове на цикличния код.

На практика често възниква проблемът с конструирането на цикличен код с дадена мощност и дадени възможности за откриване и коригиране.

1. Тъй като мощността на цикличния код е дадена, броят на неговите информационни битове се определя в съответствие с формулата

2. Оптималният брой контролни цифри на цикличния код се определя с помощта на специални таблици.

3. С помощта на справочници се намират всички нередуцируеми полиноми от степен

4. За един от непроводимите полиноми (трябва да се избере полиномът с максимален брой членове) от степен се построява генерираща матрица на цикличния код. Всеки кодов вектор се изчислява с помощта на формулата

където е полиномът на информационния вектор на генериращата матрица; - моном от степен - остатък от деление

5. Конструираната генерираща матрица се проверява за следните условия:

а) теглото в смисъла на Хеминг на всеки вектор от генериращата матрица трябва да удовлетворява отношението където е минималното разстояние, в смисъла на Хеминг, на разглеждания цикличен код;

б) теглото в смисъла на Хеминг на контролния вектор, което е сумата по модул 2 на всеки два контролни вектора на генериращата матрица, трябва да отговаря на отношението

6. Ако генериращата матрица на цикличния код отговаря на всички горни условия, тогава всички вектори на цикличния код се изписват и определят в съответствие с известните правила за линейни групови кодове. Ако кодът не отговаря на изискванията, тогава се избира друг генериращ полином от същата степен и процедурата за генериране на цикличен код се повтаря за новия полином.

Нека конструираме цикличен код със степен 16 и коригираща способност

Защото определяме стойността чрез

3" Използвайки справочници, намираме всички нередуцируеми полиноми от степен. Има два такива полинома:

4. Избираме полином като шаблон на генериращата матрица на цикличния код

Ние представяме всеки информационен вектор от матрицата като полином

Ние напълно определяме всички вектори на генериращата матрица, използвайки формулата

Тъй като дължината на вектора на цикличния код (вижте тогава формата на генериращата матрица

По същия начин намираме всички други вектори на генериращата матрица

Таблица 13.6

В резултат на това се получава генериращата матрица C? цикличен код

5. Получената генерираща матрица удовлетворява всички необходими условия. Затова изграждаме пълен цикличен код (Таблица 13.6). Както следва от таблицата, кодът има, т.е. удовлетворява изискванията на задачата.

Бележки. Когато използваме нередуцируем полином като генератор, получаваме код, който също удовлетворява изискванията на задачата. Неговата генерираща матрица има формата

Откриването на грешки с помощта на циклични кодове се извършва по следния начин. Всеки вектор на цикличен код се разделя на генериращ полином без остатък. Следователно критерият за наличие на грешка в цикличен кодов вектор е появата на ненулев остатък от разделянето на цикличния кодов вектор на генериращ полином. Ненулев остатък е идентификатор на грешка в цикличен кодов вектор, но появата му не показва местоположението на грешката в кодовия вектор. Коригирането на грешки се основава на следния алгоритъм:

1. Разделете получения кодов вектор на генериращ полином.

Ако броят на единиците не надвишава коригиращата способност на кода, тогава добавете получения вектор по модул 2 с получения остатък. Резултатът от сумирането ще даде коригирания кодов вектор. Ако броят на остатъчните единици е по-голям от коригиращата способност на кода, тогава циклично изместете изкривения вектор наляво с един бит и след това разделете на генериращия полином. Ако полученият остатък съдържа единици не повече от коригиращата способност на цикличния код, тогава сумирайте циклично изместения вектор с остатъка. Резултатът от сумирането се измества циклично с една цифра надясно. Полученият вектор вече не съдържа грешки и е вектор от цикличен код.

3. Ако след първото циклично изместване и последващото деление остатъкът съдържа повече единици от коригиращата способност на кода, тогава процедурата на алгоритъма се повтаря, докато се получи остатък с брой единици, който не надвишава коригиращата способност на кода. В този случай резултатът от последното циклично изместване се сумира с остатъка и полученият вектор се измества циклично с толкова бита надясно, колкото оригиналният получен вектор с грешка е изместен наляво. Резултатът е коригиран кодов вектор.

Нека цикличният код е даден от неговата генерираща матрица C и генериращ полином , където

Кодът има стойност 3, т.е. коригира грешките на множеството. Нека векторът 0011101 бъде приет вместо вектора 0001101. За да коригираме грешката, извършваме следните действия. Записваме получения вектор като полином: след това разделяме на

Остатъкът, получен в резултат на разделянето, съдържа три единици, което е повече от коригиращата способност на кода. Следователно, ние правим циклично изместване наляво с един бит от получения кодов вектор. В резултат на това имаме

Делим на

Полученият остатък съдържа две единици, което е по-голямо от коригиращата способност на кода. Следователно, ние правим още едно циклично изместване наляво с един бит от получения кодов вектор. В резултат на това имаме

Делим на

Полученият остатък отново съдържа две единици, така че правим още едно циклично изместване наляво с едно място и получаваме Разделяне на