Дәріс 9 Сызықтық блоктық кодтар. Хеммингтің салмағы мен қашықтығы. Қателерді анықтау және түзету мүмкіндігі.
Алдыңғы дәрістерде (7,4)-Хэмминг коды мысалында сызықтық блок кодтарының негізгі қасиеттері көрсетілген және синдромды декодтау әдісі келтірілген. Енді келесі сұрақ туындайды: "жақсы "кодтар" жаман " кодтардан қалай ерекшеленеді және оларды қалай іздеу керек? Сызықтық кодтардың құрылымын толығырақ ашып, біз осы сұрақтың жауабын қысқаша тұжырымдауға тырысамыз.
Декодтау процесін жақсы түсіну үшін біз векторлық кеңістіктің геометриялық көрінісін қолданамыз. 10-суретте n өлшемді екілік векторлық кеңістік секторы көрсетілген. Онда n-өлшемді код векторы 0 ерекше орын алады, ол әрқашан кез-келген сызықтық кодқа жатады (бұл сызықтық кодтардың қасиеттерінен туындайды). Мұнда "о "таңбаларымен белгіленген n өлшемді код векторлары көрсетілген. Мүмкін болатын қабылданған R векторлары " х " таңбаларымен белгіленеді. Кодтық сөздерді декодтау аймақтары жазықтықтағы осы кодтық сөздердің суреттеріне сәйкес келетін нүктелерде орталықтары бар шеңбер ретінде көрсетілген. Бұл дегеніміз, егер қабылданған r векторы, мысалы, Қараңғы аймақтың ішінде болса (10-сурет орташа шеңбер), онда декодер тұтынушыға v1 код сөзін береді.
v1 сөзі арнаға жіберілсін. Бұрмалау нәтижесінде арнада қабылдау мен декодтаудың үш нұсқасы болуы мүмкін (10-сурет).
1. Бірінші жағдайда, e1 қате векторы берілген векторды v1 декодтау аймағына жататын нүктеге көрсетеді. Декодер арнада пайда болған қателерді түзете отырып, тұтынушыға берілген vi сөзін береді.
2. Екінші жағдайда, e2 векторы берілген v1 векторын v2 декодтау аймағына аударады, осылайша тұтынушыға v1 орнына қате v2 сөзі беріледі. Алайда қате танылады, өйткені қабылданған r2 векторы код сөзі емес.
3. Үшінші жағдайда, e3 қате векторы берілген сөзді v3 қате код сөзіне көрсетеді. Анықталмаған қате бар.
10-сурет - "о" кодтық сөздері бар векторлық кеңістік және "х" деген сөздермен ауыстырылсын.
Суреттен кодтың түзету қабілеті код сөздері арасындағы қашықтыққа байланысты екені анық. Біз екілік векторлармен айналысатындықтан және олардың арасындағы қашықтық сәйкес келмейтін компоненттердің санымен анықталатындықтан, келесідей жаза аласыз
. (9.1)
Осылайша өлшенген қашықтық қашықтық, Хамминг деп аталады. Оны vi және vj векторларының скаляр қосындысының нөлден басқа компоненттерінің (Хэмминг салмағы) саны ретінде де анықтауға болады
. (9.2)
1-кесте. (7,4)- Хэмминг кодының кодтық кестесі
Мысал: (7,4)- Хэмминг кодын синдродық декодтау.
1-кестені қолданып, v1 = (1101000) және v2 = (0110100) векторлары арансындағы Хэмминг ара қашықтығын анықтайық. (9.1) өрнекке сәйкес
. (5.3)
(9.2) өрнегін қолданып анықтайық
. (5.4)
Кодтың түзету қабілетін анықтайтын маңызды параметр – dmin минималды кодтық қашықтық. Оны анықтау үшін барлық жұп сөздер арасындағы Хэмминг қашықтығын есептеп, ең кішісін табу керек. Сызықтық кодтар жағдайында есептеулерді айтарлықтай азайтуға болады. Осы мақсатта біз сызықтық кодтардың негізгі қасиетін - векторлық код кеңістігінің "оқшаулану" қасиетін қолданамыз. Бұл қасиет тікелей сызықтық кодтардың анықтамасынан туындайды және келесідей тұжырымдалады: код сөздерінің кез-келген сызықтық тіркесімі код сөзі болып табылады. С кодын құрайтын екілік кодтық сөздердің жиынтығын қарастырайық, осы жиынның әр сөзін екі модульге қосыңыз, кейбір жазылған еркін кодтық сөздер vi. Содан кейін көптеген код сөздері өздігінен пайда болады, ал vi векторы; нөлдік код сөзіне ауысады. Бұл суретте кодтық сөздердің жұп қашықтығы өзгермейтіндіктен және vi векторы ерікті түрде таңдалғандықтан, dmin келесідей анықталады
, (9.5)
яғни, сызықтық кодтың минималды dmin кодтық қашықтығы нөлдік емес кодтық сөздің минималды салмағына тең. Код сызығынан кез-келген кодқа қатысты код қашықтықтарының симметриялылығы да шығады.
1-кестеден (7,4) - Хэмминг кодының dmin 3-ке тең.
Жоғарыда келтірілген барлық ойлар мен мысалдарды қорытындылай келе, сызықтық кодтың түзету қабілетін келесідей анықтай аламыз.
Сызықтық екілік (n, k) – код минималды хэмминг қашықтығы бар код dmin – 1 қателерін анықтап, t қателерін түзете алады.
Егер код и < t еселікт барлық қателеріді түзетсе, онда декодтау аймақтары n өлшемді кеңістіктегі t радиусының сфералары болып табылады.
c (n, k) rодтық сөздің салмағы – нөлдік емес элементтер саны - w(c) деп белгіленеді. 0 барлық сызықтық блоктық кодтардың кодтық сөзі екенін ескере отырып, әр сызықтық блоктық кодта нөлдік салмақты код сөзі бар.
с1, c2 екі кодтық сөздер арасындағы Хемминг қашықтығы (Hamming distance) d(c1, c2) деп белгіленеді және c1 және c2 ерекшеленетін элементтер санына тең. Код сөзінің салмағы оның нөлдік код сөзіне дейінгі қашықтығына тең екені анық.
Әрі қарай, сызықтық кодтың с1 және c2 екі кодтық сөздері үшін с1 – c2 сөзі де кодтық сөз екенін ескерсек, d(c1, c2) = w(c1 – c2), яғни сызықтық блоктық код үшін салмақ пен қашықтық арасында сәйкестік бар екені анық.
Ағымдағы c код сөзінен бастап қалған код сөздеріне дейінгі барлық қашықтықтардың жиынтығы берілген кодтың барлық салмақтарының жиынтығына сәйкес келеді, сондықтан с код сөзін таңдауға байланысты емес.
Кодтың ең аз қашықтығы (минималды қашықтық) - бұл барлық мүмкін код сөздерінің жұптары арасындағы ең аз қашықтық:
Кодтың минималды салмағы (минималды салмақ) - нөлден басқа барлық Код сөздерінің ішіндегі код сөздерінің минималды салмағы:
Сызықтық блок кодтары үшін минималды салмақ минималды қашықтыққа сәйкес келеді.
Сызықтық блок кодтары үшін минималды салмақ пен тексеру матрицасының бағандары арасында байланыс бар:
Rem: cHt = 0 –бұл c үшін бұл қажетті және жеткілікті шарт
Минималды wmin салмағы бар сөзді таңдарда (немесе dmin-дің ең аз қашықтығы), біз H матрицасының бағандары мен dmin сызықтық тәуелді екенін аламыз. Басқа сөздер үшін қашықтық бұдан кем болмайтынын ескере отырып, H матрицасының сызықтық тәуелді бағандарының ең аз саны dmin, яғни баған кеңістігінің өлшемі- (dmin – 1).
Қорытынды.
Қателіктерден қорғау үшін артықтықты қолданудың екі негізгі әдісін қарастырайық. Бірінші әдіспен қателерді анықтау және қайта жіберу, қатенің бар-жоғын тексеру үшін жұптық бақылау биті қолданылады (деректерге қосымша бит). Сонымен қатар, қабылдағыш терминал қатені түзетуге тырыспайды, ол таратқышқа деректерді қайта жіберу туралы сұрау жібереді. Таратқыш пен қабылдағыш арасындағы мұндай диалог үшін екі жақты байланыс қажет екенін атап өткен жөн. Екінші әдіс, тікелей түзету, тек бір жақты байланыс желісін қажет етеді, өйткені бұл жағдайда жұптық бақылау биті қателерді анықтауға да, түзетуге де қызмет етеді. Әрі қарай, барлық қате комбинацияларын түзету мүмкін емес екенін көреміз, сондықтан түзету кодтары қателерді түзету мүмкіндіктеріне сәйкес жіктеледі.
Қателерді кодтармен анықтау және түзету принципі геометриялық модельдер арқылы жақсы суреттеледі. Кез – келген n-элементтік екілік кодты n-өлшемді текшемен көрсетуге болады, онда әр шың код комбинациясын көрсетеді, ал текшенің жиегінің ұзындығы бір бірлікке сәйкес келеді. Мұндай текшеде шыңдар арасындағы қашықтық олардың арасындағы жиектердің ең аз санымен өлшенеді, d белгіленеді және кодтық қашықтық деп аталады.
Достарыңызбен бөлісу: |
