Ақпараттар және кодтау теориясы
Дәріс 11. Сызықтық блоктық кодтар. Хемминг Кодтары. Кеңейтілген кодтар
жүктеу/скачать 1,27 Mb.
|
лек1 (2)
| Дәріс 11. Сызықтық блоктық кодтар. Хемминг Кодтары. Кеңейтілген кодтар.
Хемминг кодтары. Хэмминг кодтары қарапайым сызықтық блоктық кодтардың маңызды тобын құрайды. Әрбір үшін келесі параметрлері бар екілік Хэмминг коды бар: Хэмминг кодтары. кодтық сөздердің ұзындығы ақпараттық разрядтар саны тексеру разрядтарының саны т = n – k түзету қабілеті t = l, dmin = 3 мінсіз кодтар Хэмминг кодтарының дизайны келесі түрдегі тексеруші матрицасымен анықталады. . (11.1) Хэмминг кодының минималды қашықтығы dmin = 3 болғандықтан, сынақ матрицасының барлық бағандары жұппен әр түрлі болуы керек (сынақ матрицасында бірдей бағандар болмауы керек). dmin = 3 болғандықтан генератор матрицасының әр жолында кем дегенде үш бірлік болуы керек, өйткені генератор матрицасының жолдары өз кезегінде кодтық сөздер болып табылады. Егер генератор матрицасы , (11.2) бұл Р матрицасының жолдарында кем дегенде екі бірлік болуы керек дегенді білдіреді. (Демек, бұл транспонирленген матрицаның бағандарына да қатысты). Тексеруші матрицасын қарастырайық. Ол . матрицада k бағандары және т = n – k жолдары бар. "0" және " 1 " екілік таңбаларын қолдана отырып, 2т әртүрлі бағандарды құра аласыз. Бірақ, бұрын әр бағанда кемінде екі бірлік болуы керек деп айтылғандықтан, бір нөлдік бағанды және бір бірлігі бар m бағандарды тастау керек. Осылайша, мүмкіндіктер қалады. және матрицада дәл k бағандары болғандықтан, барлық осы мүмкіндіктер қолданылады. Демек, транспонирленген матрицаның бағандары кемінде екі бірліктен тұратын т = n – k ұзындығындағы барлық мүмкін екілік сөздер болып табылады. Ескерту. Матрицасының n бағандарында нөлді қоспағанда, m ұзындығының барлық мүмкін екілік сөздері бар екенін ескеріңіз, яғни және барлық бағандар әртүрлі. Бұл көрініс бір қатені түзету әдісін бірден ашуға мүмкіндік береді. Шын мәнінде, синдромдық қайта кодтау теңдеуі түрінде көрсетуге болады. Егер е-бір қатенің векторы болса, онда ол код сөзінің і-ші қате разрядында бір ғана бірлікті қамтиды. Бұл жағдайда синдром (s векторы) Н матрицасының i-ші бағанын білдіреді. Н матрицасының барлық бағандары әртүрлі болғандықтан, код сөзіндегі бір қатенің мүмкін болатын позициялары n әр түрлі синдромдардың дәлдігіне сәйкес келеді, сондықтан s синдромының мәні бойынша бір қате пайда болған код сөзінің разряд нөмірін нақты анықтауға болады, яғни.оны түзетуге болады. Мысал: (15.11)-Хэмминг коды. (15,11) Хамминг кодының мысалында жоғарыда аталған дизайнның барлық ерекшеліктерін нақты түсіндіруге болады: Тексеру матрицасы бойынша (11.2) және (11.1) көмегімен туындатушы (генеративті) матрица құрылады Мысал: деректерді (15.11)-Хэмминг кодын қолдана отырып беру. Бұл мысалда біз деректерді беру үшін (15,11)-Хэмминг кодын (7,4)-Хэмминг коды үшін бұрын алынған нәтижелермен салыстырамыз. Жылдамдық (15,11)-код (7,4) - кодтан айтарлықтай жоғары өйткені , ал . Басқа кодтау параметрлері қалай өзгеретінін көрейік. Ол үшін алдыңғы мысалдан 1,2,3 тапсырмаларын орындаймыз. Шешімі.
1. Егер оның барлық разрядтары қатесіз қабылданса, код сөзі дұрыс қабылданады екілік таңба үшін Қате ықтималдығы Ре = 0.023, алдыңғы мысалдан . (7.4) 2. Анықталмайтын қатенің ықтималдығын келесі бағалаудан аламыз . (7.5) 3. Екілік таңбаларды беру жылдамдығы 16 кбит/сек болғанда, деректерді берудің тиімді жылдамдығы . (7.6) Жоғарыда келтірілген есептеулерде біз (15,11) және (7,4) кодтар үшін Ре = 0.023 екілік таңбасындағы қатенің бірдей ықтималдығына сүйендік. Біз бірдей таратқыш қуатымен ұқсас есептеулер жүргізейік. Бұл жағдайда кодтаусыз берумен салыстырғанда бір символға энергия шығыны (15,11)-Код үшін тек дБ ((7,4)-Код үшін бұл мән 2.4 дБ құрайды - алдыңғы мысалды қараңыз). Сонымен, 7 дБ-ге тең сигнал/шу қатынасы 0.013-ке тең екілік таңбаның қате ықтималдығына сәйкес келеді, сондықтан , (7.7) Және қатенің анықталмау ықтималдығы жоғарыдан келесідей бағаланады . (7.8) Тиімді беріліс жылдамдығы да артады . (7.9) Таратқыштың өзгермейтін қуатының шарты екілік таңбалар қатесінің ықтималдығы теңдігіне қарағанда тәжірибеге жақын. (7,4)-кодпен салыстырғанда, (15,11)-Код үшін біз Rb,eff = 9.62 кбит/сек тиімді жылдамдығынан, Анықталмайтын қате ықтималдығының артуына байланысты, пайда аламыз. Қарастырылған мысалдар әр нақты жүйе үшін кодты таңдау өте мұқият жүргізілуі керек екенін көрсетеді. жүктеу/скачать 1,27 Mb. Достарыңызбен бөлісу:
|