Тақырып 13. Кедергіге төзімді кодалау. Кодалы арақашықтықпен түзетуші қабілеті бар кодалардың байланысы

Дәрістің мақсаты: Кодалық ара-қашықтық түсінігін меңгеру

Сұрақтар:

1. Максималды шынайылық тәсілі

2. Минималды кодалық ара қашықтық дегеніміз не?

3. Ара қашықтық матрицасы қалай құрылады?

4. Жұптық бақылауы неге негізделген?

Берілгеннен ең аз санға ерекшелейтін, тәуелсіз қателіктер кезінде қодалық комбинацияға ауысу мүмкіндігі туады.

Екі кез-келген кодалық комбинацияның айырмашылық дәрежесі Хэмминг мағынсында қашықтықпен сипатталады және кодалық ара-қашықтық деп аталады.

Кодалық ара-қашықтық комбинациялары бір-бірінен ерекшеленетін символ санымен сипатталады.

Екілік кодта екі комбинация арасындағы кодалық ара-қашықтықты алу үшін осы комбинациялардың суммасының 2 модулі бойынша бірліктердің санын табу жеткілікті.

(2 модулі бойынша қосу: y=x1+x2 қосынды 1 ге тең болады егер x1мен x2 бір бірімен сәйкес келмесе)

Барлық кодалық рұқсат етілген комбинация жұптары бойынша алынған минималды қашықтық минималды кодалық қашықтық деп аталады.

Котдың қасиетінің толық бейнесін D матрица қашықтығы береді.

23мысал: Симметриялық матрицамен код арақашықтығын құру х₁ = 000; х₂ = 001; х₃ = 010; х₄ = 111.

Шешімі. 1. Код үшін минимальды кодтыұ арақашықтық d=1

2. Код үшін төртінші ретті симметриялық матрица

4.1 таблица

	x1	x2	x3	x4
x1
x2
x3
x4

Қабылдаудан кейін қайта кодолау былайша жүргізіледі, қабылданған код рұқсат етілген бойынша теңдестіріледі, яғни одан ең аз кодтық арақашықтық бойынша.

Мұндай қайта кодолау максимальды ұқсастық кодалауы деп аталады.

D=1 кодтық арақашықтығында барлық кодтық құрылымға рұқсат етілген.

Мысалы, n=3 рұқсат етілген құрылымында келесідей болады: 000, 001, 010, 011, 100, 101, 110, 111.

Кез келген бірлік қателік берілген құрылымнан басқа рұқсат етілген құрылымға транспорленеді. Бұл қателік түзеуге қабілетсіз жағдайы.

Егер d = 2 онда бірлік қателіктегі рұқсат етілген құрылымнан басқа рұқсат етілген құрылымға өтпейді.Мысалы, көп жағдайда рұқсат етілген кодтық құрылым бірлік санның жұптығы бойынша жасалуы мүмкін.Мысалы n=3 үшін:

000, 011, 101, 110 – рұқсат етілген құрылым;

001, 010, 100, 111 – рұқсат етілмеген құрылым;

Код бірлік қателікті көрсетеді,сондай-ақ тақ еселік қателіктерді көрсетеді(n=3 үшін).

Жалпы жағдайда еселік қателікті көрсетуде r дейін минимальды хэмминг арақашықтығы рұқсат етілген код құрылымында 1-ден артық болуы тиіс d_{0 min}³r+1.

Шынында бұл жағдайда еселік өспейді,яғни бір рұқсат етілген құрылымнан басқасына ауысатын жағдайда емес.

Бірлік қателікті жөндеу үшін кодтық құрылымды көптеген рұқсат етілмеген кодтық құрылыммен салыстыру керек.үшін

Көптеген жағдайда қиып өтпес үшін хэмминг қашықтығы рұқсат етілген кодтық құрылым үшін 3-тен кем болмауы тиіс. n=3 үшін рұқсат етілген кодтық комбинацияда 000 және 111 қабылдауға болады. Сонда рұқсат етілген құрылым 000 –ді көптеген рұқсат етілмеген құрылымдардан яғни 000 құрылымында екілік қателікті қорытады 001,010,100 бұрын жазу керек.

Подобным же образом разрешенной комбинации 111 необходимо приписать подмножество запрещенных кодовых комбинаций: 110, 011, 101, образующихся в результате возникновения единичной ошибки в комбинации 111:

Сол сияқты 111 рұқсат етілген құрылымында мына рұқсат етілмеген код құрылымдарын бұрын жазу керек 110, 011, 101,яғни 111 құрылымында қорытындысында бірлік қателікті шығарады.

Жалпы жағдайда бар мүмкіндігінше барлық қателікті табу үшін s –ке дейін қайта кодалауды қоса алғанда максимальды ұқсастық, әрбір қателік рұқсат етілмеген құрылымға өтуі тиіс.

Кез келген n – разрядты екілік құрылым m-ші бірлік куб,яғни қыры ұзындығымен түсіндірілуі мүмкін.

n=2 кодтық құрылымында квадрат төбесінде орналасады.

Рис. 4.2.

Жалпы жағдайда n –өлшемді кубта 2ⁿ төбелері болады,кодтық құрылымның мүмкін болар жоғары мәніне тең.

Мұндай модель қарапайым геометриялық интерпретация және бөлек кодтық құрылымдағы кодтық қашықтықты береді.Ол кубтың бірлік кбтың кіші қабырғаларының санына тең. Егер бұзылған құрылым алғашқысына ұқсас түрде қалса басқа рұқсат етілген құрылымдарға қарағанда,онда қателік тек табылып қана қоймас жөнделеді, яғни мынадай болу керек: немесе

Жалпы, барлық қателік ұстау үшін және s еселікке дейін қателікті жөндеу үшін олдардық код арақашықтығы мынаған тең болу керек: d ³ r+s+1 (r³s).

Бірлік тәуелсіз қателікті жөндеудегі қайта кодолау әдісі келесідей түсіндіріледі.

Көп жағдайда әрбір рұқсат етілген құрылым үшін барлық төбелері қатысады,яғни (d-1)/2 радиусты және центрі төбеде.Егер қорытындысында бөгет құрылымы сфера ішіндегі (d-1)/2 нүктесіне өтсе, онда ондай қателік жөнделеді.

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

1. Максималды шынайылық тәсілі

2. Минималды кодалық ара қашықтық дегеніміз не?

3. Ара қашықтық матрицасы қалай құрылады?

4. Жұптық бақылауы неге негізделген?

Дата добавления: 2015-10-23