Лекция Құпиялау теориясы Кодталу теориясының негізгі ұғымдары және анықтамалары Алфавиттік кодтталу. Оптимал кодталу. Қателерді табу және өңдеу кодттары
Қателерді табу және өңдеу кодтары
жүктеу/скачать 198,4 Kb.
|
15-лекция
| Қателерді табу және өңдеу кодтары
B = {0,1} алфавитінде n ұзындықтағы Bn сөздер жиынын қарастырамыз. Әр бір x1,x2,…,xn сөзді В алфавитінде n - өлшемді (x1,x2,…,xn) векторымен теңдестіреміз. Bn нен алынған (x1,x2,…,xn) және (y1,y2,…,yn) векторлардың қосындысы ретінде (x1 Å y1, x2 Å y2 ,…, xn Å yn) векторды айтамыз. Мұнда Å белгі модуль 2 бойынша қосу амалы екендігін ескертіп өтеміз. Егер кез келген Х = (x1,x2,…,xn) векторын bÎ В элементке көбейту амалын bХ = (bx1,bx2,…,bxn) тәрізді еңгізсек, онда Вn жиынды n-өлшемді векторлық кеңістік ретінде қарастыру мүмкін. Вn векторлық кеңістікте Х және У векторлардың сәйкес емес компоненталар саны ретінде Х және У векторлар арасында d(X,Y) – Хемминг қашықтығын және Х вектордың Х пен n-өлшемді нөльдік (0,0,...,0) вектор арасындағы қашықтық ретінде ||X|| норманы анықтау мүмкін. Бұл жерде, Bn нен алынған кез келген X = x1x2…xn сөз үшін ||X|| = j=1Σn xj және Bn нен алынған кез келген Х,У үшін d(X,Y) = ||X Å Y|| болатыны айқын. Bn метрикалық кеңістікті өте қарапайым геометрикалық интерпретация ретінде қарастыруға болады: Bn кеңістікке n-өлшемді бірлік кубтың төбелер жиыны сәйкес келеді, ал Bn нен алынған екі элемент арасындағы қашықтық куб төбелерін сәйкес ретінде қосатын тізбектегі қабырғалардың минимал санына тең. Еркін алынған Х = x1x2…xn Î Bn сөз үшін оның N(X) сандық мәнін анықтаймыз: N(X) = j=1Σn xj 2n-j . Мысалы , х = 0110011 және У = 0001101 болса, онда ||X|| = 4, ||Y|| = 3, X ÅY = 0111110, d(X,Y) = ||XÅY|| = 5, N(X) = 1+2+16+32=51, N(Y) = 1+4+8=13 болады. Мұнда, 19 сан үшін e(19) = 10011, e7(19) = 0010011 болуын ескеріп өткен жөн. Бұдан былай бұл бөлімде текқана белгілі ұзындықтағы m >2 екілік сөздерден құралатын кодтарды қарастырамыз. Айталық кез келген V = (u0,u1,…,um-1} Î Bn код үшін d(V) = mind (ui,uj), i¹ i шама берілген болсын. Осы шекті шама кодтық қашықтық деп айтылады. Мысалы, V = {a1:0100,a2:1101,a31110,a4:0010} код үшін d(ai,aj), I \ i≠j қашықтықтарды және d(V) кодтық қашықтықтарды табыңдар. Енді «қателер» деп айтылатын екілік сөздерді ауыстырудың кейбір көріністерін қарастырамыз. -Х – сөзіндегі 0→1(1→0) көрінісіндегі жеке қате деп 0 белгісінен біреуін (сәйкес ретінде 1) 1 белгісімен (сәйкес ретінде 0) ауыстыру нәтижесін айтамыз. Осы көріністегі жеке қателерді тағыда «белгілерді ауыстыру» немесе «аддитив қателер» депте айтамыз. - Х сөзіндегі 0→λ(1→λ) көрінісіндегі жеке қате деп 0 сиволдардан (сәйкесінше 1) біреуін қашықтату нәтижесін айтамыз. Сонымен бірге бұл жерде сөз ұзындығы бір бірлікке азаяды. Бұл типтегі жеке қателер ²белгілердің түсіп қалуы² деп айтылады. - Х сөзіндегі λ→ 0 (λ→1) көрінісіндегі жеке қате деп сөздің кейбір символдарының алдына немесе оның соңғы белгісінен соң белгілердің қойылу нәтижесі айтылады, мұнда сөз ұзындығы бір бірлікке көбейеді. - Х Î Bn сөзіндегі +2і(-2і), мұнда 0£ i ≤ n, көрінісіндегі жеке қате деп Х сөздің сандық мәнінен сандық мәні 2і ге үлкен (сәйкес ретінде кіші) болған YÎ Bn сөзіне ауыстыруды айтамыз. Мұндай жеке қателерді «арифметикалық қателер» деп айтамыз. Көрнекілік үшін 6- кестеде қарастырылған типтегі қателер нәтижесі бойынша 0001101 (13 санның екілік жазуы) сөзден алынған қателер орны келтірілген. 6 кесте
Қателіктердің типтері деп жеке қателер көрінісіндегі кейбір жиынды айтамыз. Мысалы, {0→λ,1→λ, λ→0,λ→1} типтегі қателер кез келген белгінің жойылуы немесе қойылуы болып есептеледі. Жеке қателердің қайталанып келу санын осы қатенің жиілігі деп айтамыз. Сонымен, 0001101 сөзі 3-реттік қате нәтижесінде (бірінші белгі алдына 1 қою, бесіншінің алдынан 0 ді түсіріп қалдыру және соңғы белгіні ауыстыру) 1001100 сөзіне өтеді. Бұдан былай {(0→1),(1→0)} типтегі қателерге, яғни белгілерді ауыстыруларға көптеу көңіл бөлеміз. Берілген типтегі әр түрлі қателерді табу және өңдеу мәселелерінің қойылуында қателердің пайда болуына жіберілген заңдылықтардың келіп шығуына мән береміз. Бұл заңдылықтар не ықтималдық, не комбинаторлық характерге ие болуы мүмкін. Ал заңдылықтар екілік сөздерді желі арқалы жеткізу немесе сақтау кезінде беріледі екен. Көбінесе кезектегі екі типтегі желілер қарастырылады: а) кез келген белгіде р(0 б) әр бір n ұзындықтағы сөзде берілген типтегі жиілігі s тен көп болмаған кез келген қате пайда болуы мүмкін. Кедергіге төзімді кодталудың негізгі бағыты кезектегілерден тұрады. Байланыс желісі арқылы Х,У,Ғ,... ақпараттардың орнына қателерді табуды қамтамасыз ететін немесе тура декодталуды жеткізетін белгілі бір жолмен X¢,Y¢,Ғ¢,… кодталудың жаңа сипаты жіберіледі. V = {u0,u1,…,um-1} Í Bn кодты қолдану кезіндегі қателерді өңдеу мүмкіншілігін кезектегідей тәрізде түсіндіру мүмкін. Т(х) арқылы қарастырылып жатқан желіде мүмкіндік қателер нәтижесінде Х сөзден алу мүмкін болған сөздер жиынын белгілейміз, дербес жағдайда Т(ui) – ui кодталған сөздің қате болу нәтижесінде алынуы мүмкін болған сөздер жиыны. i=0Um-1T(ui) жиынның V ға еркін бір мәнді D кескіні «декодталу» деп айтылады. D декодталу мәселесі i=0Um-1T(ui) жиынды қиылыспайтын D-1(ui), i = 0,1,…, m-1 ішкі жиындарға (аймақтарға) бөлумен пара – пар, мұнда әр бір D-1(ui) аймақ D кескіндеудегі ui сөздердің кернусхасынан құралған. D декодталу кезінде кез келген uі Î V сөзде ui сөзді T(vi)Ç D-1(ui) жиындағы қандайда бір сөзге ауыстырғанда тек қана сол қателіктерге ғана сүйеніп есептеуіміз табиғи. Дербес ретінде, барлық қателіктер өңделетін D декодталу бар болуы үшін T(ui ), i=0,1,…,m-1 жиындар жұбымен қиылыспайтын болуы қажет және жеткілікті. Онда, байланыс желісі бойынша әлдеқандай Y хабарды ала отырып, біз оның қандайда бір Х кодталу сөзінің аймағына тиісті екендігін анықтаймыз және дәл осы Х сөзі ретінде жеткізілетіндігіне қорытынды жасаймыз. Осындай қасиетті игерген код берілген типтегі қателерді өңдейтін код деп айтылады. V Í Bn код үшін T(Х) жиынның орнын басу типтегі s қателікті өңдеуі Х- сөздің s радиусты метрикалық аймағымен, яғни Х сөзден s тен көп болатын қашықтықта жатқан нүктелер жиынтығына сәйкес келеді. Сондықтан T(ui) жиынның қиылыспайтындылық шарты кодталу қашықтығының d(V)>2s болуына пара-пар. Сонымен, V код s қателікті өңдеу коды болады екен, сонда тек сондағана, қашан d(V)>2s+1 болса, мұнда d(V) – бүтін сан. Осы қателерді өңдеу мәселелерімен қатар қателерді өңдеудің бұданда күшсіз мәселелерін құрастыру мүмкін. V кодты қолдану кезінде бір кодтық сөзді басқа кодталу сөзіне ауыстыру кезінде ғана қателіктерді таба алмай қалуымыз мүмкін. Осы жерден дербес ретінде кезектегі тұжырым келіп шығады, яғни d кодталу қашықтығына ие болған V код барлық уақыт (d-1) ге дейінгі орнын басу типтегі жеке қателерді табуға мүмкіндік береді. Жоғарыда айтылғандардан кезектегідей қорытынды жасауымыз мүмкін. Кодталудың кедергілерге тұрақтылығын қамтамасыз ету үшін сол хабар тұралы ақпараттардан басқа хабарларды жеткізу (немесе сақтау) процесінде қателердің пайда болу кезінде жіберілген хабарларды табу және тіктеуге мүмкіндік беретін қосымша ақпараттар болатын оданда ұзындау кодтарды қолдануға тұра келеді. Бұл деректі мынадай қалыптастыру мүмкін: сенімділік үшін кодталудың көпмүмкіншілігімен ғана мақсатқа жетсе болады. Сонымен, 10 ға дейінгі араб сандарын кодтау үшін алдынғы параграфтағы мысалда сипатталғандай 9 екілік белгі қолдану емес, ал 4(24 = 16 >10) және жазылу әдісіне сәйкес минимизациялау жеткілікті ( 3 – сызба). Бірақта, кодталудың осындай әдісінде C102 = 45 жұп кодталу арасында дәл бір разрядқа айырмашылығы бар немесе тіпті жеке орын басуда бір кодты басқа код ретінде қабылдау мүмкін болған 14 жұп кодтар болады. Шын қолданып жатқан ондық 9 белгілі екілік сандар мен кодталуда бір жұптықта (0 және 8 сандары) айырмашылық тек бір разрядта болады (шамасы кейбір кездерде түсініксіз толтырылғандықтан немесе оқығандағы үзілістерге байланысты қателіктерге алып келуі мүмкін), ал басқа жұптарда үш разрядтан кем болмайды. Сонымен бірге қабылданған кодталу әдісі басқа себептермен қолайлылау. Оның қолайлылығы әдеттегі араб цифрларының жазылуына ұқсастығында. 3- сызба Кодтардың кедергілерге тұрақтылығын құрудың қарапайым әдісі – қайталану. Сонымен, егер жіберілетін сөздің әр бір әрпін (s+1) рет қайталасақ, онда мұндай код орнын ауыстыру типтегі s қателікке дейін табуға қабилетті қателік болмаса хабарлар (s+1) бір түрлі белгілерден құралған біртекті серияларға бөлшектенеді, ал егер қате табылса және тіпті егер барлық s қателік бір серияның ішінде болса, біртектілік бұзылған қателермен жіберілген бір немесе бірнеше белгілерді табу мүмкін болады. Бұдан былай біз тек қана орнын басу типіндегі жалғыз қателіктер болған жағдайды қарастырамыз. Жалғыз қателерді табу мүмкін болуы үшін алдын қарастырылған қарапайым тәсілдерді қолданғанда жіберілетін сөздер ұзындығы екі есеге, ал оны өңдеу үшін үш есеге көбейеді. Бірақта бұданда көбірек үнемді кедергіге мекем кодталулар болуы мүмкін. Мұндай әдістер идеясы кезектегілерде тұжырымдалады. Екілік сөздер жиынында кез келген функция қарастырылады. Ізденілген код осы функция кез келген бір белгіленген мәнді қабылдайтын Bn нен алынған сөздер жиыны ретінде анықталады. Бұл функция кезектегідей таңдалады, яғни нәтижеде кез келген жеке қателерде осы өзгерістер бойынша функция мәні аусады және сол сөз қателерінің бірмәнді көрінісін және қате орнын анықтау мүмкін болады. Осындай кодталу ретінде – Хемминг кодына бір мысал қарастырамыз. Мұнда, n санды белгілеп қоямыз және 2ℓ-1£ n <2ℓ шарт орындалатын сондай бір сан табамыз. Бұл жағдайда ℓ = [logn]+1 болады, Мысалы: ℓ(5) = ℓ(7) = 3, ℓ(8) = ℓ(10) = ℓ(13) = 4. Айталық, кез келген еркін Х = x1x2…xn Î Bn сөз үшін H(x)=x1el (1) Å x2el(2) Å… Åxn l (n) болсын. Бұл жерде H(X) X сөзінің екілік жазудағы (ℓ сан көмегімен) бірлік белгілер нөмірлері болған векторлардың қосындысы нәтижесінде алынған ℓ ұзындықтағы векторларды сипаттайды. Мысал: Айталық n = 6, x = 010101 және y = 110100. Онда ℓ = ℓ(6) = 3, H(x) = (0,1,0)+(1,0,0)+(1,1,0) = (0,0,0), H(y) = (0,0,1) + (0,1,0) + (1,0,0,) = (1,1,1) болады. жүктеу/скачать 198,4 Kb. Достарыңызбен бөлісу:
|