Тақырып 12. Кедергіге төзімді кодалау

⇐ ПредыдущаяСтр 30 из 40Следующая ⇒

Дә рістің мақ саты: Хемминг кодын ү йрену. Кедергіге тө зімді кодалау тү сінігі

Сұ рақ тар:

1. Кедергіге қ алыпты қ арсы тұ ратын кодтар дегеніміз не?

2. Хэмминг коды?

3. Хэмминг коды не ү шін қ олданылады?

4. Қ ателерді ө ң деу несімен кө мектеседі?

Кедергіге тө зімді кодалау

Кодалы аймақ

Шулы дискретті арнаның басты теоремасы бойынша, ақ парат жасаудың жылдамдығ ы арнаның ө ткізу қ абілетіне тең немесе одан кем болса, онда ақ параттың арна бойынша аз қ ателікпен жіберуге мү мкіндік беретін коды болады. Бірақ ол хабарлауды максималды жылдамдық пен жә не минималды қ ателікпен кодалау мә селесін шешпейді, яғ ни кедергіге тө зімді кодалау мә селесін шешпейді. Бұ л мә селені шешудің арнайы ә дістері бар. Кең қ олданысқ а ие: алгебралық ә діс, оның кө мегімен группалық кодтар класы зерттелді, жә не геометриялық кодтар.

Кодтық аяның қ ұ рылысын біркелкі кодағ а қ олданып қ араймыз, дербес жағ дайда блоктық, кодалық комбинациялар бір біріне тә уелсіз кодталады жә не декодталады. Шығ у алфавиті В біркелкі n-ретті коды, Г m символдан қ ұ ралады; mсаны коданын негізі деп аталады. Осындай кодтың кодалық комбинациясының тү рі мынадай мұ нда мағ ынасы ші разрядты коды,

алфавит символын реттейміз жә не m модулі бойынша есептеудің ә ртү рлі символды классы екенін тү сінеміз. Индекс классын m санын қ алдық ө кіліне бө лгенде қ оямыз.

Кө птік В-ге екі алгебралық операцияны енгізейк: кө бейту мен қ осуды- , Cr классы мұ нда, r-бө лген кездегі қ алдық m –ді жә не классты сумма класс егер жә не егер .

2. 5-те кө рсетілгендейкө п класстар m модулі бойынша енгізілген қ осу жә не кө бейту амалдары кө рсетілген аймақ болады. Бұ л кодалық комбинацияғ а мұ рша береді В шығ у алфавитіндегі n-ретті

бірретті коданы аймақ ү стіндегі сызық ты n векторы ретінде қ арастырады. Бұ л аймақ ты ары қ арай кодалық аймақ деп, ал оның элементтерін кодалық вектор деп қ арастырамыз. m модулді операцияларды жең ілдету ү шін оларды ары қ арай белгілейміз.

Қ одалық аймақ та кодалық векторлар қ ателігін дұ рыстау анализі нә тижесінде метрика енгізеді. Қ олданысқ а ие Ли мен Хэмминг метрикасы.

Метрика Ли анық тамасын анық тау ү шін вектор весі ұ ғ ымын қ олданамыз

Мұ нда

Ли арақ ашық тығ ы вектор арасында , бұ л вектор салмағ ының артү рлігі деп аталады.

Кең қ олданысқ а ие блотық кодаларды қ ұ ру кезінде Хэмминг метрикасын қ олданады.

Қ ателерді ө ң деу

кедергіге қ алыпты қ арсы тұ ратын кодтар тек қ ана қ ателерды анық тауды ғ ана жү зеге асырмай сонымен қ атар оларды ө ң дейді. Qm нан аспайтын еселіктердың қ ателеіктерін ө ң деудің жалпы идеясы келесіде. М кедергіге қ алыпты қ арсы тұ ратын қ одтардың мү мкін болатын кодалық комбинациялары N класына бө лінеді. Бұ л бө ліну ә р классқ а бір рұ қ сат етілген жә не оғ ан жақ ын рұ қ сат етілмеген кодалық комбинация кіру керек. Қ айта кодалау кезінде қ абылданғ ан кодалық комбинация кай классқ а жататынын анық талады. Егер де кодалық комбинаия қ атеиен қ абылданса, яғ ни рұ қ сат етілмеген, онда ол ол классқ а жататын рұ қ сат етілгенге ө ң деледі. Кодалау теориясында Qm нан аспайтын еселіктердың қ ателеіктерін қ ң деу мү мкіндіктерін жү зеге асыру ү шін кодалық ара-қ ашық тық 2qm нан кө п болу керек екені дә лелденген. Кө біне ол формуласымен анық талады. n разрядты екілік кодты N кодалық комбинациясының ең ү лкен санын d қ ашық тық пен табу ерекше болып саналады.

Кодалау теориясында келесі ө рнектер бар:

Хэмминг коды

(n, k)-кодының мысалы ретінде ара – қ ащық тығ ы 3ке тең жә не дара қ ателіктерді ө ң дейтін Хэмминг кодын алайық. Кодалық ара-қ ашық тығ ы d=3 ке тең коды ү шін рұ қ сат етілген сан 7, 5 – тақ ырыпта кө рсетілгендей ге тең. Хэмминг коды ү шін бұ л тең сіздік тең дікке айналады. Кодтың кодалық комбинациясының алғ ашқ ы к разряды ақ параттық ретінде қ олданылады, жә не ол келсіге тең

Бұ л тең деу Хэмминг кодын анық тайтын бү тін санды мә нді к=0, 1 4, 11 26,..., береді: (3, 1)-код, (7, 4)-код, (15, 11) – код жә не т. б.

Бақ ылау сұ рақ тары:

5. Кедергіге қ алыпты қ арсы тұ ратын кодтар дегеніміз не?

6. Хэмминг коды?

7. Хэмминг коды не ү шін қ олданылады?

8. Қ ателерді ө ң деу несімен кө мектеседі?

⇐ Предыдущая 25 26 27 28 293031 32 33 34 Следующая ⇒