Лекция 1 Ақпарат теориясы ақпараттық жүйелерді сипаттаудың сапалы және сандық әдістері негізі ретінде. Ақпаратты өлшеу


Лекция 15 Ақпарат теориясы ақпараттық жүйелердің синтезі мен декомпозицисы



бет20/20
Дата24.01.2023
өлшемі1.34 Mb.
#181866
түріЛекция
1   ...   12   13   14   15   16   17   18   19   20
Байланысты:
6-Лекция

Лекция 15
Ақпарат теориясы ақпараттық жүйелердің синтезі мен декомпозицисы
құралы ретінде
Полиномиальды кодтауда әрбір мәлімет өрнектеледі, ал кодтаудың өзі тұрақталған көп мүшелікке көбейтуден тұрады. Полиномиальды кодтар – блоктық және бұрын қарастырылғандардан тек кодтау және декодтау алгоритмімен өзгешеленеді.
a=a0…am-1 – екілік мәлімет болсын. Онда оған a(x)= а01x+…+аm-1xm-1 көп мүшелілігін сәйкестендіреміз. Барлық есептеулер екінші модуль бойынша есептеу классы өрісінде жүргізіледі, яғни кез-келген арифметикалық операциялар нәтижесінен оны екіге бөлгендегі қалдығын алады.
Мысалы, m=5-тегі 10011 кезектестігіне 1+x3+x4 мүшелігі сәйкес келеді.
Кейбіp k дәрежесіндегі қателіктерді жазайық,
q(x)= q0+q1x+…+qkxk q0 qk .
q(x) кодтау көпмүшелігімен полиномиальды коды a(x) мәлімет сөзінің b(x)= a(x)q(x)=b0+b1x+…+bn-1xn-1 көпмүшелілігімен немесе b=b0…bn-1 көпмүшелігі коэффициентінің кодтау сөзімен кодтайды.q0 qk шарты қажет, өйткені кері жағдайда b0 және bn-1 еш ақпарат тасымалдамайды, себебі олар барлық уақытта нөлге тең болады.
Мысал. Кодтайтын q(x)= 1+x2+x3 көпмүшелігін қарастырамыз. a(x)= x+x3+x4 көпмүшелігіне жауап беретін 01011 мәліметі b(x)=q(x)a(x)= x+x5+x7 көпмүшелігінің коэффициентімен кодталады, яғни b=01000101.
k дәрежесіндегі q(х) полиномиальды код, m*(m+k) көлеміндегі G кодтау матрицасымен матрицалық код болып табылады.

яғни j-ші қатардағы нөлдік элементтер - бұл j-ден (j+k)-ға дейінгі бағанада орналасқан кодтау коэффициентінің кезектестігі болып табылады.
Мысалы, кодтайтын 1+x+x3 көпмүшелігі бар(3,6)-коды мына матрицаға

немесе мына бейнелерге жауап береді: 000000000, 001001101, 010011010, 011010111, 100110100, 101111001, 110101110, 111100011.
Полиномиалды кодтар топталған болып табылады.
Бұл матрицалық кодтау арқылы алынатын кодтардың кодталған екендігінен шығады.
Кодтайтын q(x) копмүшелігі бар (m,n)-кодын қарастырамыз. e=e0…en-1 қателер қатары, егер оған сәйкес келетін e(x)= e0+e1x+…+en-1xn-1 көпмүшелігі q(x)-ке бөлінсе, онда табылмай қалады.
Шынымен a(x)q(x)+e(x) q(x)-ке бөлінеді, егер де e(x) q(x)-ке бөлінсе.Сондықтан көпмүшелігі q(x)-ке бөлінбейтін кез-келген қателер табылады және сәйкесінше, көпмүшелігі q(x)-ке бөлінетін қателер табылады.
Осылайша, кодтайтын q(x) көпмүшелігі бар полиномиалды кодты қолданғанда қателерді табу көпмүшелікті қалдықпен бөлу алгоритмі көмегімен жүзеге асырылады: егер қалдық нөл емес болса, онда жіберуде деректердің сығылуы болды.
Хэммингтің кодын полиномиалды ретінде құруға болады, мысалы, кодтайтын x3+x2+ 1 көпмүшелігі бұрын қарастырылғандардан жақсырақ жетілдірілген (4,7)-кодын анықтайды.
Егер сәйкес (m,n)-кодын тудыратын q(x) кодтау көпмүшелігі xj+1(jd – кодтау сөзінің арасынлағы минималды арақашықтығы болсын, ол нөлдік емес кодтау сөздерінің салмақтарының арасындағы минимумға тең.d=2 есептейік. Онда a(x)q(x)=b(x) және b(x)-тің дәрежесі n-нен үлкен емес болатындай a(x) бар болады. b-ның салмағы екіге тең, сондықтан b(x)=xm+xl және ll( xm-l+ l) бұл xm-l+l q(x)-ке бөлінуі керек дегенді білдіреді, ал бұл шарт бойынша мүмкін емес. Егер d=1 деп есептесек, онда бұл xm q(x)-ке бөлінуі керек деген тұжырымға әкеледі, бұл да шартқа қарсы келеді. Сөйтіп d .
Кодтайтын x11+x9+x7+x5+x+1 көпмүшелігі, 7 кодтау сөзінің минималды арақашықтығындағы жетілдірілген Голейдің (12,23)- кодын анықтайды.
Хэммингтің және Голейдің кодтарынан басқа жетілдірілген код жоқ екені 1971 жылы финдік және кеңестік математиктер көмегімен дәлелденді[20].
Полиномиалды кодтардың арасындағы ең қызықтысы циклдік кодтар болып табылады, онда b0…bn-2bn-1 түріндегі кез-келген кодтау сөзімен бірге bn-1b0…bn-2 кодтау сөзі де болады.




Достарыңызбен бөлісу:
1   ...   12   13   14   15   16   17   18   19   20




©kzref.org 2023
әкімшілігінің қараңыз

    Басты бет