А. Ж. Асамбаев криптография негіздері


таспа  (немесе  бір  реттік  блокнот



Pdf көрінісі
бет17/19
Дата15.03.2017
өлшемі2,01 Mb.
#9839
1   ...   11   12   13   14   15   16   17   18   19

таспа  (немесе  бір  реттік  блокнот,  немесе  Вернам  шифры)  деп  аталады.  Шифрлау 
процесіне екілік деректер тап болады деп болжайық. Беретің және қабылдайтың жақта екі 
бірдей  таспа  дайындалады,  мысалы,  магнитті.  Оларда  шифрлау  кілті  бар.  Беретің  жақта 
таспа  шифрлау  құрылғыға  қойылады,  ал  қабылдайтың  жақта  –  дешифрлау  үшін 
пайдаланатын ұқсас құрылғыға. Жіберуші хабарды беретін болса, ол бастапқы хабардың 
бір  битын  және  магнитті  таспадан  бір  битты  модулі  екі  бойынша  қосады.  Осыдан  кейін 
таспа келесі күйге ауыстырылады және кілттің екінші битын пайдаланып хабардың екінші 
битын шифрлауға болады.  Осылай барлық хабар шифрланады. Қабылдайтың жақта кілті 
бар таспа ұқсас пайдаланылады.  
Мысалы, бастапқы хабарда келесі екілік цифрлар болсын:  
m = 1100101110... 
Кілттік ретінде пайдаланатын тізбек мұндай болсын деп болжам жасайық: 
k = 1001100111... 
Шифрлауды бір реттік таспа әдісі бойынша орындайық, әрбір бағанда цифрларды 
модулі екі бойынша қосып: 
бастапқы мәтін              m = 1100101110... 
кілттік тізбектің биты      k = 1001100111... 
------------------- 
шифрланған мәтін            с = 0101001001... 
 
Бұл процесс кіру деректер ағынына гаммана салуға ұқсайды. Бір реттік таспасы бар 
шифр  шынында  гаммалау  болып  табылады,  бірақ,  оның  басқа  криптожүйелерден 
айырмашылығы – шексіз гамма.   
Бір  реттік  таспада  барлық  әріптер  бірдей  жиілікпен  кездеседі.  Сондықтан, 
гамманың қанша болса да таңбасы белгілі болса, біз келесі әріп қандай болатының алдын 
ала  болжай  алмаймыз.  Осыдан  шығады,  гамма  таңбаларының  барлық  тізбектері  тең 
ықтималды.  Демек,  Вернам  шифры  көмегімен  шифрланған  хабар,  кез  келген  сәйкес 
ұзындығы  бар  ашық  мәтінге  «дешифрлану»  мүмкін,  себебі  шамаланған  гамма 
таңбаларының тізбегінде оны басқадан айыратын ешқандай қасиеті жоқ. 
Вернам шифрында кілттік деректер тасушы ретінде дәл таспаны пайдалану  мүлде 
міндетті  емес.  Ең  керекті,  жіберуші  мен  алушыда  өлшемі  бастапқы  хабардың 
ұзындығынан кем емес құпиялы кілт болу қажет.  
Әбден құпиялы жүйелер тәжірибеде жүзеге асырылу мүмкін. Бірақ, неліктен олар 
барлық жағдайда пайдаланбайды? Мұнын бірнеше себебі бар. Біріншіден, жабық кілті бар 
шифрлау  жүйедегіндей  оларда  кілттерді  үлестіру  проблемасы  бар.  Екіншіден,  әбден 
құпиялы  жүйеде  шифрлау  кілттің  ұзындығы  аз  болғанда  ашық  мәтіннің  ұзындығымен 
бірдей  болу  керек.  Одан  басқа,  әрбір  хабарды  шифрлау  үшін  өз  жаңа  кілт  қолданылу 
керек.  Осы  факторлар  әбден  құпиялы  жүйенің  жүзеге  асыруын  тым  қымбатқа  және  аса 
қолайлы емеске әкеледі. Осындай жүйелерді тек ең маңызды байланыс (мысалы, үкімет) 
желілер үшін пайдалану жөн.  
 
13.5 Жалғыздық қашықтығы 
 
Егер  криптографиялық  жүйе  әбден  құпиялы  болмаса,  онда  шифрланған  хабар 
криптоталдаушыға  бастапқы  хабар  туралы  кейбір  ақпарат  беру  мүмкін.  Маман 
шифрмәтінді  тура  бір  мәнді  дешифрламасада,  бірақ  кілт  немесе  ашық  мәтін  жөнінде 
кейбір болжау жасай алады. Келесі дәл сол кілтпен шифрланған хабарды алғаннан кейін, 
криптоталдаушы өз білімін кеңейтіп, ақырында хабарды дешифрлай алу мүмкін.  
Шифрланған  хабарды  бірмәнді  дешифрлау  үшін,  оның  ұзындығы  қандай  болу 
керек.  Бұрын  қарастырылған  мысалда  қарапайым  ауыстыру  әдіспен  жабылған  11 
символдан тұратын хабарды біз ашып оқуға әрекет жасадық. Орыс тілдің статистикалық 

 
124 
заңдылықтарын  талдау  негізінде  ашық  мәтіннің  бірнеше  қолайлы  варианты  таңдап 
алынды, бірақ олардан бір «дұрысын» таңдау үшін ақпарат жетпеді. Сірә, ұстап алынған 
хабардың  кейбір  ұзындығы  болады,  одан  кейін  хабардың  ашып  оқу  ықтималдығы  бірге 
жақындайды.   
Шеннон  шифрдың  жалғыздық  қашықтығы  (немесе  бірегей  қашықтығы)  U 
деген ұғым енгізді, ол кілтті бір мәнді қалпына келтіру үшін шифрланған хабардың қанша 
әріптерін ұстап алу қажеттігін көрсетеді.  
Жалғыздық  қашықтығын  есептеу  үшін  кілт  энтропиясын  Н(К)  білу  керек. 
Симметриялық  шифрлар  үшін  кілт  энтропиясы  шамамен  кілттер  санының  N
K
  негізі  2 
бойынша логарифмына тең:  
Н(К) = log
2
 N
K

Мысалы, қарапайым ауыстыру шифры үшін мүмкін болатын кілттер саны барлық 
мүмкін ауыстыру кестелер санымен анықталады және тең N

= 33!   8,68 10
36
, сондықтан 
кілт энтропиясы тең болады  
Н(К) = log
2
 8,68 10
36
   122,7 
Егер  бізге  кейбір  шифры  үшін  кілт  энтропиясы  Н(К)  белгілі  болса,  онда  ол  үшін 
жалғыздық қашықтығы мына формула бойынша есептеледі 
U = H(K) / D
мұндағы – шифрланатын хабардың артықтығы. 
Орыс  тілінде  хабарларға  қолданылатын  қарапайым  ауыстыру  шифры  үшін 
жалғыздық қашықтығын есептейік: 
U = H(K) / D = 122,7/3,5   35,1 
Яғни егер ұстап алынған хабардың ұзындығы 35 символдан артық болса, онда оны 
бір  мәнді  ашып  оқу  мүмкін.  Ал  шифрланған  мәтіннің  ұзындығы  35  символдан  кем 
болғанда бір мәнді ашу мүмкін емес.  
Қарсыласқа  кілтті  анықтауды  және  дешифрлауды  қиналту  үшін,  қолданылатын 
шифрларда  жалғыздық  қашықтықты көбейту  қажет (шексіздікке дейін жақсы болар еді). 
Жалғыздық  қашықтықты  есептеу  формуласын  талдап,  анықтаймыз,  мұны  екі  тәсілмен 
істеуге болады. 
Егер кілт энтропиясы шексіздікке тең болса, онда шифрдың жалғыздық қашықтығы 
да  шексіздікке  тең  болады.  Кілт  ұзындығы  неғұрлым  ұзын  болса,  кілт  энтропиясы 
соғұрлым  үлкен  болады.  Бір  реттік  таспа  жүйесін  пайдаланғанда  кілт  теорияда  шексіз 
және  оның  бәр  символдары  тең  ықтималды  болады,  сондықтан  осындай  шифрдың  кілт 
энтропиясы  шексіз  үлкен  болады.  Демек,  Вернам  шифрдың  жалғыздық  қашықтығы 
шексіздікке тең. 
Жоғары  айтылғандай,  шексіз  үлкен  кілті  бар  шифрды  пайдалану  тәжірибелік 
орынды емес. Бірақ шифрлау кілттерді анда-санда ауыстыруға болады, мысалы, сеанстық 
кілттерді пайдаланып, яғни әрбір хабарды шифрлау үшін жаңа кілтті қолдану. 
Жалғыздық қашықтықты үлкейтудің екінші тәсілі – бастапқы мәтіннің артықтығын 
азайту.  Егер  хабар  артықтығы  нөлге  тең,  онда  кілт  ешқашан  анықталмайды,  ал 
шифрланған  хабар  ашылмайды,  себебі  жалғыздық  қашықтығы  шексіздікке  тең  болады. 
Өкінішке орай, тәжірибеде бұл мүмкін емес, өйткені кез келген мағыналы хабарда кейбір 
нөлден өзгеше артықтығы болады.  
Бірақ  хабардағы  артықтықты  деректерді  сығу  арқылы  азайтуға  болады.  Себебі  
деректерді  сығу  кезінде  «сығылған»  мәтіннің  энтропиясы  сақталындаы,  ал  ұзындығы 
азаяды. Демек, энтропия сығылған мәтінде бастапқыдан бір әріпке артық, ал артықтығы – 
кем. Ендеше, сығу кодтаудан кейін шифрдың жалғыздық қашықтығы өседі. 
 
Негізгі терминдер 
 
Тілдің  абсолют  нормасы  –  тілдегі  барлық  символдар  тізбегі  тең  ықтималды 
болғанда, кейбір тілдің бір символымен беріле алатын ақпараттың максимал бит саны. 

 
125 
Тіл артықтығы – белгілі тілдегі мәтінде болатын ақпарат артықтығын белгілейтің 
статистикалық шама.  
Тіл нормасы – хабардың бір символына келетін ақпарат саның сипаттайтын шама. 
Бір  реттік  таспа  (немесе  бір  реттік  блокнот,  немесе  Вернам  шифры)  –  әбден 
құпиялы  жүйені  жүзеге  асыруының  мүмкін  болатын  варианты.  Шексіз  гаммалау  сияқты 
жүзеге асырылу мүмкін. 
Жалғыздық  қашықтығы  (немесе  бірегей  қашықтығы)  –  кілтті  бір  мәнді 
қалпына  келтіру  үшін  шифрланған  хабардың  қанша  әріптерін  ұстап  алу  қажеттігін 
көрсететін шама. 
Әбден  құпиялы  жүйе  -  шифрланған  мәтіннің  талдауы  ашық  мәтін  туралы 
(ұзындығынан басқа) ешқандай ақпарат бермейтін криптографиялық жүйе.  
Хабар энтропиясы – Шеннон енгізген шама. Статистикалық тәуелсіз хабарларды 
тудыратын көзінің бір элементар хабарға келетін ақпарат санын анықтайды. Ақпараттың 
белгісіздік немесе болжанбайтындық өлшемі болып табылады. 
 
Сұрақтар 
 
1. Хабар көзінің энтропиясы қалай анықталады? 
2. Хабар көзінің энтропиясы нені сипаттайды? 
3. Тіл нормасы нені анықтайды? 
4. Тілдің абсолют нормасы қалай есептеледі? 
5. Тіл артықтығы нені сипаттайды? 
6. Неге табиғи тілде жазылған хабарларда әрқашан артықтық болады? 
7. Әбден құпиялы криптографиялық жүйенің анықтамасын беріңіз. 
8. Әбден құпиялы жүйелер болмайтын шифрлар мысалын келтіріңіз. 
9.  Неге  бір  реттік  таспа  шифры  (Вернам  шифры)  әбден  құпиялы  жүйе  болып 
табылады? 
10.  Неге  әбден  құпиялы  жүйелер  тәжірибеде  ақпаратты  қорғау  үшін  жаппай 
пайдаланбайды? 
11. Шифр кілтінің энтропиясы қалай анықталады? 
12. Шифр үшін жалғыздығының қашықтығы қалай есептеледі? 
 
Жаттығулар 
 
1.  Көз  32  әртүрлі  символ  генерациялайды.  Хартли  бойынша  1  символға  келетін 
ақпарат саны қандай? 
2. Деректерді берудің кейбір құрылғысы 256 әртүрлі символ генерациялау мүмкін. 
Хартли бойынша 10 символға келетін ақпарат саны қандай? 
3. Кейбір хабарлар көзі үшін Хартли бойынша 1 символға келетін ақпарат саны 6 
битқа тең болғаны белгілі. Хабарлар көзінің алфавитындағы символдар саны қаншаға тең? 
4.  Екі  көзі  екі  символдан  генерациялайды.  Бірінші  көз  символдарды  бірдей 
ықтималдықпен  генерациялайды,  екіншісі  –  түрлі  ықтималдықпен. Қандай  көзі  үшін  бір 
символға келетін Шеннон бойынша ақпарат саны артығырақ болады? 
5.  Хабарлар  көзі  n  әртүрлі  p
1
,  p
2
,...,  p
n
  ықтималдықпен  m
1
,  m
2
,...,  m
n
  хабарларды 
генерациалайды. Берілген бастапқы деректер үшін көздің энтропиясын анықтаңыз: 
 
= 4;  p
1
 = 0,25,  p

= 0,25,  p
3
 = 0,375,  p
4
 = 0,125; 
 
n = 6;  p
1
 = 0,0025,  p

= 0,0075,  p
3
 = 0,09,  p
4
 = 0,2,  p

= 0,5,  p
6
 = 0,2; 
 
n = 4;  p

= 0,25,  p

= 0,1,  p
3
 = 0,15,  p
4
 = 0,5. 
6. кілті бар Вернам шифры көмегімен m хабарды шифрлаңыз:  
 
m = 1001001110,  k = 0100111011; 
 
m = 0101101110,  k = 1010101011; 
 
m = 1111001101,  k = 0110001011. 

 
126 
7.  Орыс  тілінде  хабарларды  (32  әріп)  қолданылатын  n  позицияға  ығысуы  бар 
Цезарь шифры үшін кілт энтропиясын есептеңіз.  
8.  Орыс  тілінде  хабарларды  қолданылатын  (32  әріп)  n  позицияға  ығысуы  бар 
Цезарь  шифры  үшін  жалғыздық  қашықтығын  есептеңіз.  Орыс  тілінде  хабарлардың 
артықтығын бір символ үшін 3,5 битке тең деп алыңыз. 
9. Кілттердің барлық варианттары тең ықтималды және мүмкін деп алып, екілік  
кілттің  берілген  ұзындығы  бар  шифрлар  үшін  жалғыздық  қашықтығын  есептеңіз. 
Хабарлар артықтығы D
 
= 256 бит,  D = 3,5; 
 
= 512 бит,  D = 3; 
 
= 128 бит,  D = 4. 
 
 
 
 
14 ШИФРЛАУ, БӨГЕУІЛГЕ ТҰРАҚТЫ КОДТАУ 
 
ЖӘНЕ АҚПАРАТТЫ СЫҒУ
 
 
Көзден  тұтынушыға  ақпаратты  беру  барысында  ақпаратқа  әртүрлі  жағымсыз 
факторлар  әсер  етеді.  Криптографиялық  әдістер  ақпаратты  бұзу  әсерлердің  бір  түрінен 
ғана  қорғайды  -  ақпаратты  әдейі  бұзудан  немесе  бұрмалаудан.  Бірақ,  тәжірибеде 
ақпаратты  берген  кезде  байланыс  желіде  кездейсоқ  бөгеуілдер  болу  мүмкін, 
аппаратураның  қателіктері  мен  істен  шығуы,  деректер  тасушының  қирауы  және  т.б. 
Ақпаратты беру проблемаларды шешу үшін нақты байланыс жүйелерде түрлі әдістер мен 
тәсілдердің  комплекстік  пайдалануы  қажет.  Бұл  бөлімде  бөгеуілге  тұрақты  кодтарды 
пайдалану және деректерді сығу алгоритмдер қарастырылған.  
Бөлім  мақсаты:  беру  және  сақтау  барысында  ақпаратты  комплексті  қорғау  үшін 
шифрлаудың, бөгеуілге тұрақты кодтаудың және ақпаратты сығудың бірлескен пайдалану 
принциптерімен таңысу. 
 
14.1 Ақпаратты беру проблемалар және оларды комплекстік шешу 
 
Көзден  тұтынушыға  ақпаратты  беру  барысында  ақпаратқа  әртүрлі  жағымсыз 
факторлар  әсер  етеді.  Криптографиялық  әдістер  ақпаратты  бұзу  әсерлердің  бір  түрінен 
ғана  қорғайды  -  ақпаратты  әдейі  бұзудан  немесе  бұрмалаудан.  Бірақ,  тәжірибеде 
ақпаратты  берген  кезде  байланыс  желіде  кездейсоқ  бөгеуілдер  болу  мүмкін, 
аппаратураның  қателіктері  мен  істен  шығуы,  деректер  тасушының  қирауы  және  т.б. 
Сонымен, нақты байланыс жүйелерде кездейсоқ әсерлеуден ақпаратты қорғау проблемасы 
бар. 
Бұрың  шифрланатын  және  берілетін  хабарлардың  негізгі  типі  мәтіндік  хабар 
болатын,  ХХI  ғасырда  криптографиялық  қорғау  цифрлық  видео-  және  сөз  хабарларды, 
жер  карталарды  беруде,  видеоконференцияны  ұйымдастыруда  қолданылады.  Дәл 
сондықтан  соңғы  кезде  орасан  зор  ақпараттық  массивтерді  шифрлау  проблемасы  туады
Интерактивті  жүйелер  үшін  (телеконференция  сияқты,  аудио-  немесе  видеобайланыс) 
осындай  шифрлау  нақты  уақыт  тәртібінде  жүзеге  асырылып  пайдаланушыға 
байқалмайтын болу керек.  
Көрсетілген проблемаларды ақпарат теориясының жетістіктерін комплекстік түрде 
пайдаланып шешуге болады.    
Ақпарат 
теориясында 
ақпарат 
түрлендірудің 
үш 
түрін 
ажыратады: 
криптографиялық  шифрлау,  бөгеуілге  тұрақты  кодтау  және  сығу  (немесе  компрессия). 
Бұрыңғы  кейбір  ғылыми  жұмыстарда  түрлендірудің  үш  түрін  кодтау  деп  аталатын: 
криптографиялық кодтау, бөгеуілге тұрақты кодтау және тиімді кодтау (деректерді сығу). 

 
127 
Олардың  ортақтығы  –  ақпарат,  мағынасын  емес,  көрсету  нысаның  қандай  болса  да 
жолмен өзгертеді. Түрлі кодтаулардың айырмашылығы өткізілетін түрлендіру мақсатына 
тәуелді. 
Мысалы,  криптографиялық  түрлендірудің  мақсаты  рұқсатсыз  қатынаудан  қорғау, 
аутентификациялау  және  әдейі  өзгертуден  қорғау.  Бөгеуілге  тұрақты  кодтау  ақпаратты 
беру  және  сақтау  кезінде  кездейсоқ  бөгеуілден  қорғау  мақсатымен  орындалады.  Тиімді 
кодтау  берілетің  және  сақталынатын  деректердің  көлемін  минимизациялау  мақсатымен 
жасалынады.  
Тәжірибеде  ақпарат  түрлендірудің  осы  үш  түрі  әдетте  бірлесіп  пайдаланылады. 
Мысалы,  кейбір  программалық  пакеттер  шифрлаудың  алдында  өңделетін  деректерді 
архивтейді.  Басқа жағынан, ақпаратты берудің нақты жүйелерінің құрамында (жергілікті 
және  ғаламдық  желілер,  CD  немесе  DVD-дискілер)  ақпаратты  қорғау  жүйелер,  бақылау 
және кездейсоқ қателіктерді түзету құралдар әрқашан бар болады. 
Сонымен,  криптографиялық  шифрлау,  бөгеуілге  тұрақты  кодтау  және  сығу  бір 
бірін  толықтырады,  және  олардың  комплекстік  пайдалануы  берілетін  ақпаратты  сенімді 
қорғау  үшін  байланыс  арналарды  тиімді  пайдалануға  көмектеседі.  Ақпаратты  қорғау 
жүйелерде  пайдаланатын  бөгеуілге  тұрақты  және  тиімді  кодтау  теориясының  негізгі 
қағидаларын қарап шығайық.  
 
14.2 Бөгеуілге тұрақты кодтау 
 
Айтылғандай,  ақпаратты  криптографиялық  түрлендіру  сұрақтары  хабарларды 
бөгеуілге тұрақты кодтау сұрақтарымен тығыз байланысты. Ол бір (теориялық) жағынан 
криптографиялық  шифрлауда  және  бөгеуілге  тұрақты  кодтауда  бірдей  ақпарат 
теориясының заңдарының пайдаланатына себепті. Басқа (тәжірибелік) жағынан ақпаратты 
жинау,  сақтау  және  беру  процестері  бөгеуiл  әсер  ететін  жағдайда  өтеді,  олар 
сақталынатын  және  өңделетін  деректерді  бұрмалау  мүмкін.  Сондықтан,  осындай 
қателіктерді  табатын  және  түзететін  әдістерді  әзірлеу  мен  пайдалану  өте  актуальды. 
Математикалық  көзқарасынан  бұл  есеп  бөгеуілге  тұрақты  кодтарды  синтездеуге 
жатады. 
Бөгеуілге  тұрақты  кодтауды  және  хабарларды  сығу  сұрақтарды  талқылауда  код 
ұғымы енгізіледі. Жалпы код дегеніміз – бұл белгілердің жинағы және ақпаратты белгілер 
жиынтығы  ретінде  көрсете  алатын  ережелер  жүйесі.  Мүмкін  болатын  белгілердің  кез 
келген қатары кодты сөз деп аталады. Мысалы, екілік 1100 санды екілік 4-разрядты кодты 
сөз деп санауға болады. 
Бөгеуілге  тұрақты  кодтаудың  ортақ  идеясы  -  барлық  мүмкін  болатын  кодты 
сөздерден  рұқсат  етіледі  бәріне  емес,  тек  олардың  кейбіреуіне.  Мысалы,  жұптылық 
бойынша бақылауы бар кодта тек бірліктер жұп саны бар сөздерге рұқсат етіледі. Қателік 
мүмкін болатын сөзді мүмкін болмайтын сөзге айналдырады және сондықтан табылады.  
Бөгеуілге  тұрақты  кодтар  блокты  және  үйірткіліге  бөлінеді.  Блокты  кодтар 
ақпаратты  тұрақты  ұзындығы  бар  фрагментке  бөледі  және  олардың  әрбіреуін  жеке 
өңдейді, ал үйірткілі блоктар деректермен үздіксіз ағын сияқты жұмыс істейді. 
 Блокты кодтар минимал  кодтық  ара қашықтықпен сипатталады. Екі  кодты сөздер 
арасындағы Хэмминг бойынша қашықтық деп разрядтар санын атайды, оларда сөздер 
әртүрлі.  Мұнда  минимал  кодтық  ара  қашықтық  ретінде  кез  келген  қос  түрлі  кодты 
сөздер үшін ең кіші Хэмминг бойынша қашықтықты таңдайды.  
Мысалы,  біз  тек  үшразрядты  екілік  сөздерді  пайдаланайық.  Барлығы  осындай 
кодты  сөздер  сегіз  болу  мүмкін.  Кодты  сөздердің  бір  бірінен  айырмашылығы  тек  бір 
бірлікке  тең  болса  оларды  көршілес  деп  атайды.  Мысалы,  кодты  сөздер  101  мен  111  – 
көршілес,  өйткені  олар  орта  разрядпен  ғана  ерекшеленеді,  ал  101  мен  110  сөздер  - 
көршілес емес, себебі оларда ерекшеленеді соңғы екі разряды. Барлық үшразрядты екілік 
комбинацияларды  бейнелеп  көрсетейік  және  көршілес  кодты  сөздерді  сызықтармен 

 
128 
қосайық.  Онда  біз  14.1  суреттегідей  схеманы  аламыз.  Бөгеуілге  тұрақты  емес  әдеттегі 
кодтын минимал кодтық ара қашықтығы бірге тең.  
 
 
Сурет 14.1. Үшразрядты екілік кодты сөздер 
 
Барлық үшразрядты екілік сөздерді хабарды беру үшін пайдалану кезінде, олардың 
бәрі  мүмкін болатын деп саналады. Жұптылық шарты бойынша бақылауды қолданайық. 
Онда  тек  рамкамен  бөлінген  бірліктердің  жұп  саны  бар  сөздер  рұқсат  етілетін  болады 
(14.2 сур. қара).  
 
 
Сурет 14.2. Жұптылық бойынша бақылауда мүмкін болатын үшразрядты кодты сөздер 
 
Жұптылық бойынша бақылауы бар кодтың мүмкін болатын сөздерінің минимал ара 
қашықтығы  екіге  тең  (14.2  суреттен  көрінеді,  ешқандай  рамкадағы  екі  кодты  сөздер 
сызықтармен  қосылмаған,  яғни  көршілес  емес).  Дәл  осы  себептен  кодты  сөздегі  жеке 
қателік бұл сөзді жарамайтынға айналдырады.  
Бөгеуілге  тұрақтылыққа  жету  үшін  кәдімгі  кодпен  салыстырғанда  сөз  ұзындығын 
үлкейту қажет. Берілген мысалда тек екі разряды ғана ақпараттық болып табылады. Олар 
төрт әртүрлі сөзді құрайды. Үшінші разряд бақылаушы болады және тек мүкін сөздердің 
ара  қашықтығын  үлкейту  үшін  қызмет  етеді.  Ақпаратты  беруге  бақылаушы  разряд 
қатыспайды,  өйткені  ол  ақпаратқа  сызықты  тәуелді  болады.  Жұптылық  бойынша 
бақылауы бар коды деректер блоктарда жеке қателіктерді табуға мүмкіндік береді. Бірақ 
ол екі ретті қателіктерді табалмайды, себебі екі ретті қателік кодты сөзді мүмкін болатын 
сөздер аралығынан өткізіп және оны басқа мүмкін болатынға айналдырады.  
Сонымен,  кодтың  қателіктерді  тауып  түзету  қабілеті  болу  үшін,  оның 
артықшылықсыздығынан  бас  тарту  қажет.  Ол  үшін  екілік  символдардың  мүмкін 
комбинациялар жиының екі ішкі жиынға бөледі: мүмкін және мүмкін емес кодты сөздер. 
Бөлуді  мүмкін  сөздер  арасындағы  минимал  кодты  қашықтықты  үлкейту  оймен 
орындайды. Бұл жағдайда кез келген бір ретті қателік мүмкін кодты сөзді мүмкін емеске 
айналдырады, сол себептен оны табуға болады. 

 
129 
Әрине, қосымша бақылау разрядтың енгізілуі кодталған ақпаратты сақтауға немесе 
беруге арналған шығындарды көбейтеді. Ал пайдалы ақпараттың нақты көлемі өзгеріссіз 
қалады. Бұл жағдайда бөгеуілге тұрақты кодтың артықтығы туралы айтуға болады. Оны 
формальді  түрде  бақылау  разряд  санының  кодты  сөздің  жалпы  разрядтар  санына 
қатынасы деп анықтауға болады.  
Бақылау  разрядтар  ақпаратты  бермейді,  сондықтан  олар  пайдасыз.  Бақылау 
разрядтың салыстырмалы саның бөгеуілге тұрақты кодтың артықтығы деп атайды 
%
100
n
k
Q

мұндағы n – блоктағы екілік разрядтың жалпы саны; k – бақылау разрядтар саны. 
Мысалы,  қарастырылған  жұптылық  бойынша  бақылауы  бар  үшразрядты  кодтың 
артықтығы тең: 
%
33
%
100
3
1
%
100
n
k
Q
 
Артықтық  кодтың  өте  маңызды  сипаттамасы,  артықтықтың  тым  өсуі  жағымсыз. 
Ақпарат  теориясының  маңызды  есебі  –  минимал  артықтығы  бар  кодты  синтездеу,  олар 
қойылған табу және түзету қабілетін қамтамасыз етеді. 
Суреттейтің  мысал  ретінде  бір  ретті  қателікті  табуға  және  түзетуге  мүмкіндік 
беретің  қарапайым  кодтардын  біреуін  қарастырайық  –  Хэмминг  кодын.  Ұзындығы  n 
кодты  сөзде  ақпараттық  k  және  бақылау  m  разряды  бар.  Бұрмаланған  i-ші  разрядтын 
түзетуі  –  бұл  қабылданған  кодты  сөзді,  i-ші  разрядында  бірлігі  бар  0…010…0  түрлі 
вектормен қосу (модулі 2 бойынша).  
n-разрядты  кодты  сөз  үшін  бір  ретті  қателікке  сай  келетін  осындай  n  векторлар, 
және  қателіксіз  сөзді  қабылдау  жағдайға  сәйкес  келетін  бір  нөлдік  векторы  болады. 
Сонымен,  m  бақылау  разряды  n+1  қателік  векторды  құрастыруға  қамтамасыз  ету  керек, 
яғни n   2
m
-1 теңсіздік орындалу керек. Нәтижесінде Хэмминг коды деп аталатын кодты 
(2
m
-1, 2
m
-1-m) аламыз.  
m=3 сәйкес ең қарапайым жағдай (7,4)-кодты құрастырады, оны былай синтездеуге 
болады. Әрбір қателік векторға реттік нөмір – синдром сәйкестендіреміз (кесте 14.1). Осы 
кезде нөлдік қателік векторға нөлдік синдром сай болады.  
 
Кесте 14.1. Қателік векторы және оған сәйкес синдромдар 
a

Достарыңызбен бөлісу:
1   ...   11   12   13   14   15   16   17   18   19




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет