Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Егер тек қана барлық бірлік қателіктер емес,сонымен қатар, екілік тәуелсіз қателіктерді өңдеу керек болса, онда теңсіздіктің түрі мынадай болады:
2n-k-l+
Жалпы жағдайда барлық тәуелсіз қателіктерді s дәрежесіне дейін өңдеп қоысмша теңсіздік аламыз:
2n-k-l++…+
Айта кету керек, барлық жағдайда практика жүзінде орындалмайтын жоғарыда келтірілген қатынастарда тексерілетін символдардың теориялық минималды мүмкін болатын сандар шегі кқрсетілген. Сәйкес келетін теңдеулерге қарағанда жиі тексерілетін символдарды көп қажет етеді.
Әрбір бастауыш қателікті өңдеудің анықтаушысын салыстыру процесін қарастырғанда бір себебі анықталады.
Бақылау сұрақтары:
Тақырып 15. Циклдық кодтау. Түзетуші топтық кодтар.
Лекция мақсаты: Циклдық кодтардың құрылуы
Циклдық кодтардың құрылуы
Жалпы түсініктер және анықтамасы
Кез келген группалық код (n, k) матрица түрінде жазылуы мүмкін, қосылатын k сызықты тәуелсіз жолдар n символдар және керісінше, кез келген қасиеті k сызықты тәуелсіз n-разрядты кодтың комбинациясы кейбір топтық кодты құраушы матрица түрінде қарастырылуы мүмкін. Көп түрлі осындай кодтар арасынан айналымның қосымша шартымен байланысқан туындатушы матрицалар жолдарының кодтарын ерекшелеуге болады.
Бір комбинацияны циклдық қозғалу арқылы туындатушы матрицалардың барлық жолдарын алуға болады, бұл кодты туындатушы деп аталады. Бұл шартты қанағаттандыратын кодтар циклдық кодтар деген атқа ие болған.
Қозғалыс оңнан солға қарай жүргізіледі және сол жақ шеттегі символ комбинацияның соңына орналастырылады.Жазайық, мысал, комбинациялар кодтарының қасиеті, циклдық қозғалатын комбинациялар арқылы алынған түрі 001011:
Циклдық мүмкін (n,k)-кодтардың саны әртүрлі топтық (n,k)-кодтар санынан көп есе аз болады.
Циклдық кодтарды суреттегенде n-разрядты комбинациялық кодтар көпмүшелі фиктивті х-айнымалы түрінде көрсетіледі. у және х дәрежелері разрядтар нөмірлеріне сәйкес келеді (нөлден бастап),ал жалпы жағдайда коэффиценті х деп GF(q) өрісінің элементі болып табылады. х0 = 1 фиктивті айнымалысы ең төменгі санның разрядына сәйкес келеді. GF(q) өрісінің көпмүше коэффицентін GF(q) өрісінің үстіндегі көрмүшесі деп атайды. Екілік кодтарды қарастырмауымызға байланысты, х-тің коэффиценті тек 0 және 1 сандары болады. Басқаша айтқанда, GF(2) өріс үстінде көпмүшені оперировать етеміз. Жазып алайық, мысал, 01011 кодтық комбинацияны құраушы көпмүше түрінде:
G(x) = 0·x4 + 1·x3 + 0·x2 + 1·x + 1
Нөлдік коэффицентті жазғанда көпмүшелік түседі, туындатушы көпмүшелік:
G(x) = x3 + x + 1
Нөлдік коэффицентпен қосылатын х-тің үлкен дәрежесін көпмүшеліктің дәрежесі деп атаймыз. Енді кодтық комбинацияларға жасалған әрекеттер көпмүшеліктерге әрекетке өтеді. Көпмүшеліктерді қосу коэффиценттерді екінші модуль арқылы жүзеге асырады.
Көрсетілген циклдық қозғалыс кейбір туындатушы көпмүшенің дәрежесін n – k деп бірлікті кодтық комбинацияның соңына ауыстырмай х-ке көбейту сияқты қарапайым орындайды. Көбейтеміз, мысал, матрицаның бірінші жолы (001011) , g0(х) = x3 + x + 1 сәйкес көпмүшені, х-ке, матрицаның екінші жолын (010110) , сәйкесінше көпмүшені х • g0(x) аламыз.
Мына екі комбинацияның қосындысы x3 + x + 1 және х+1арқылы табылған мәні кодтық комбинацияның шыққан мәніне тең екеніне көз жеткіземіз. Шынымен де,
Циклдық қозғалыс жолдар матрица бірлігімен үлкен (n-м) разрядында (солдан) тең болады көпмүшенің х жолына сәйкес болатын , біруақытты алыну көпмүшенің нәтижесіне тең хn + 1= хn– 1 модуль бойынша хn + 1.
Бұл жерде циклдық кодтың кез келген рұқсат етілген комбинациясы модуль xn + l бойынша құралатын көпмүшенің басқа бір көпмүшеге көбейтілуінің нәтижесінен алынады.Басқаша айтсақ,дәл келетін таңдауда құралатын көпмүше және циклдық кодтың кез келген көпмүшесі қалдықсыз бөлінетін болады.Рұқсат етілмеген кодтық комбинациясына сәйкес келетін,бірде бір көпмүше,құралатын көпмүше қалдықсыз бөлінбейді.Бұл қасиет қатені табуға мүмкіндік береді.Көпмүшенің көбеюі және бөлінуі кері байланыс бар жылжу регистрында оңай орындалады.
Циклдық кодтарға математикалық кіріспе
Осылай n-разрядты циклдық кодтың әрбір рұқсат етілген комбинациясы екі көпмүшенің туындысы болып табылады,оның біреусі құраушы,онда бұл комбинацияларды n-1 дәрежесінен жоғары емес көпмүшелердің барлық туындылары ретінде қарастыруға болады.Бұл мына ойға алып келеді,осы кодтарды құрау үшін тағы бір алгербралық жүйенің тармағынн қолдануға,дәлірек,сақина теориясына.
Келтірілген анықтамаға сүйене отырып,сақинаны құрау үшін көптеген n-разрядты кодтық комбинацияларға екі операция жүктеу керек,қосу және көбейту.
Көпмүшелерді қосу операциясы модуль екі бойынша келтірілген коэфиценттерге сәйкес таңдалған.
Енді көбейту операциясын қарастырайық.Көпмүшелерді көбейту операциясы қарапайым ережелер бойынша модуль екі сәйкес мүшелерді келтіру тұйықталу шартын бұзуға алып келеді.
Расымен,көбейту нәтижесі бойынша n-1 дәрежесінен үлкен көпмүшелерді аламыз,дәреже 2(n-1) дейін жетуі мүмкін,ал оған сәйкес кодтық комбинациялар n разрядты саннан көп болады,осыған сәйкес қарастырылып отырған көптікке қатысы болмайды.Сондықтан символдық көбейту операциясы былай беріледі:
1)көпмүшелер қарапайым ереже бойынша көбейтіледі,бірақ модуль екі бойынша келтірілген мүшелерге сәйкес;
2)егер туындының жоғары дәрежесі n-1 көп болмаса,ол символдық көбейтудің нәтижесі болады;
3)егер туындының жоғары дәрежесі n-ға тең немесе үлкен болса,онда көпмүше туындысы алдын ала анықталған nи дәрежесіндегі көпмүшеге символдық көбейту бөлудің қалдығы жатады.
Қалдықтың дәрежесі n-1 аспайды,сонымен қатар,бұл көпмүше k разрядты кодтық комбинациялардың көптігіне жатады.
Расымен n-1 дәредесіндегі көпмүшенің көбейтіндісінің нәтиесінде мынаны аламыз:
G(x) = (xn-1 + xn-2 + … + x + 1)x = xn + xn-1 + … + x
Қарастыра келе,көбейту нәтижесі кодтық комбинацияға сәйкес келу керек,шыққан кодтық комбинациясының циклдық жылжуы жолымен құралады,онда хn –ді 1-ге ауыстыру керек.Мұндай ауыстыру көпмүшенің xn+ 1-ге көбейтіндісінен алынған бөлінуге эквивалентті болады,мұны былайша қалдықты алу деп атайды немесе модуль xn+ 1 бойынша келтіру.
Выделим теперь в нашем кольце подмножество всех многочленов, кратных некоторому многочлену g(x). Такое подмножество называют идеалом, а многочлен g(x)-порождающим многочленом идеала.
Количество различных элементов в идеале определяется видом его порождающего многочлена. Если на порождающий многочлен взять 0, то весь идеал будет составлять только этот многочлен, так как умножение его на любой другой многочлен дает 0.
Если за порождающий многочлен принять 1[g(x) = 1], то в идеал войдут все многочлены кольца. В общем случае число элементов идеала, порожденного простым многочленом степени n-k, составляет 2k.
Теперь становится понятным, что циклический двоичный код в построенном нами кольце n-разрядных двоичных кодовых комбинаций является идеалом. Остается выяснить, как выбрать многочлен g(x), способный породить циклический код с заданными свойствами.
Согласно определению циклического кода все многочлены, соответствующие его кодовым комбинациям, должны делиться на g(x) без остатка. Для этого достаточно, чтобы на g(x) делились без остатка многочлены, составляющие образующую матрицу кода. Последние получаются циклическим сдвигом, что соответствует последовательному умножению g(x) на х с приведением по модулю xn + 1.
Следовательно, в общем случае многочлен gi(x) является остатком от деления произведения g(x)·хiна многочлен xn + 1и может быть записан так:
gi(x)=g(x)xi + c(xn + 1)
где с =1, если степень g(x) хiпревышает п-1; с = 0, если степень g(x) хiне превышает п-1.
Отсюда следует, что все многочлены матрицы, а поэтому и все многочлены кода будут делиться на g(x) без остатка только в том случае, если на g(x) будет делиться без остатка многочлен xn + 1.
Таким образом, чтобы g(x) мог породить идеал, а, следовательно, и циклический код, он должен быть делителем многочлена xn + 1.
Поскольку для кольца справедливы все свойства группы, а для идеала - все свойства подгруппы, кольцо можно разложить на смежные классы, называемые в этом случае классами вычетов по идеалу.
Первую строку разложения образует идеал, причем нулевой элемент располагается крайним слева. В качестве образующего первого класса вычетов можно выбрать любой многочлен, не принадлежащий идеалу. Остальные элементы данного класса вычетов образуются путем суммирования образующего многочлена с каждым многочленом идеала.
Если многочлен g(x) степени m = n-kявляется делителем xn + 1, то любой элемент кольца либо делится на g(x) без остатка (тогда он является элементом идеала), либо в результате деления появляется остаток r(х), представляющий собой многочлен степени не выше m-1.
Элементы кольца, дающие в остатке один и тот же многочлен ri(x), относятся к одному классу вычетов. Приняв многочлены r(х) за образующие элементы классов вычетов, разложение кольца по идеалу с образующим многочленом g(x) степени mможно представить табл. 4.12, где f(x)-произвольный многочлен степени не выше n-m-1.
Таблица 4.12.
|
0 |
g(x) |
x·g(x) |
(x+1)·g(x) |
… |
f(x)·g(x) |
|
r1(x) r2(x) … … rn(x) |
g(x) + r1(x) g(x) + r2(x) … … g(x) + rn(x) |
x·g(x) + r1(x) x·g(x) + r2(x) … … x·g(x) + rn(x) |
(x+1)·g(x) + r1(x) (x+1)·g(x) + r2(x) … … (x+1)·g(x) + rn(x) |
… … … … … |
f(x)·g(x) + r1(x) f(x)·g(x) + r2(x) … … f(x)·g(x) + rn(x) |
Как отмечалось, групповой код способен исправить столько разновидностей ошибок, сколько различных классов насчитывается в приведенном разложении. Следовательно, корректирующая способность циклического кода будет тем выше, чем больше остатков может быть образовано при делении многочлена, соответствующего искаженной кодовой комбинации, на образующий многочлен кода.
Наибольшее число остатков, равное 2m- 1 (исключая нулевой), может обеспечить только неприводимый (простой) многочлен, который делится сам на себя и не делится ни на какой другой многочлен (кроме 1).
Контрольные вопросы: