Кіріспе

Кодтардың қасиеттерін және олардың тиімділігін зерттеу

Кодтау теориясы – кодтардың қасиеттерін және олардың нақты қолданыстарға сай келуін зерттеу саласы. Кодтар деректерді сығыстыру, криптография, қателерді анықтау және түзету, деректерді беру және сақтау үшін қолданылады. Кодтар ақпараттық теория, электротехника, математика, лингвистика және компьютерлік ғылым сияқты түрлі ғылыми пәндерде тиімді және сенімді деректерді беру әдістерін жасау мақсатында зерттеледі. Бұл көбінесе артық ақпаратты жоюды және берілген деректердегі қателерді түзетуді немесе анықтауды қамтиды. Кодтаудың төрт түрі бар:

Деректерді сығыстыру (немесе бастапқы кодтау)
Қателерді бақылау (немесе арна кодтау)
Криптографиялық кодтау
Жолдық кодтау

Деректерді сығыстыру деректерді тиімдірек беру үшін деректер көзінен қажетсіз артық ақпаратты жоюға бағытталған. Мысалы, ZIP деректерді сығыстыру дерек файлдарын кішірейтеді, осылайша интернет трафигін азайтуға көмектеседі. Деректерді сығыстыру және қателерді түзету біріктіріліп зерттелуі мүмкін. Қателерді түзету деректер көзінен алынған деректерге қосымша артық ақпаратты қосады, бұл беру арнасындағы кедергілерге төзімділікті арттырады. Көптеген қолданушылар қателерді түзетуді қолданатын көптеген қолданыстар туралы білмейді. Кәдімгі музыкалық компакт-дискілер (CD) сызықтар мен шаң-тозаңдарды түзету үшін Reed-Solomon кодын пайдаланады. Бұл жағдайда беру арнасы – CD-нің өзі. Ұялы телефондар жоғары жиілікті радиосигналдардың әлсіреуін және шуын түзету үшін кодтау әдістерін қолданады. Деректер модемдері, телефондық байланыс және NASA Deep Space Network биттерді жеткізу үшін арна кодтау әдістерін қолданады, мысалы, турбо код және LDPC кодтары.

Кодтау теориясының тарихы

1948 жылы Клод Шеннон "Белл жүйесінің техникалық журналының" шілде және қазан айларында жарық көрген екі бөлімнен тұратын "Коммуникацияның математикалық теориясы" атты мақаласын жариялады. Бұл жұмыс хабар жіберушінің жібергісі келетін ақпаратты қалай тиімді кодтау мәселесіне арналған. Осы іргелі еңбегінде ол Норберт Винер әзірлеген ықтималдықтар теориясының құралдарын пайдаланды, бұл құралдар сол кезде коммуникация теориясына қолданылудың бастапқы кезеңінде болған. Шеннон ақпараттың энтропиясын хабарламадағы белгісіздікті өлшеу үшін жасады, сонымен бірге ақпарат теориясының негізін қалады. 1949 жылы бинарлы Голай коды құрастырылды. Бұл код 24 биттік әр сөзде үш қатеге дейін түзетуге және төртінші қатені анықтауға қабілетті қателерді түзету коды. Ричард Хамминг 1968 жылы Bell Labs-те сандық әдістер, автоматты кодтау жүйелері, қателерді анықтау және түзету кодтарындағы жұмысы үшін Тьюринг сыйлығына ие болды. Ол Хамминг кодтары, Хамминг терезелері, Хамминг сандары және Хамминг қашықтығы деп аталатын ұғымдарды ойлап тапты. 1972 жылы Насыр Ахмед дискретті косинус түрлендіруін (DCT) ұсынды, оны ол 1973 жылы Т. Натаражан және К. Р. Раомен бірге әзірледі. DCT – ең көп қолданылатын жоғалтулы сығылу алгоритмі, JPEG, MPEG және MP3 сияқты мультимедиа форматтарының негізі.

Көз кодтамасы

Көздік кодтаудың мақсаты – бастапқы деректерді алып, оларды қысқарту.

Қасиеттері

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

Принцип

Ақпарат көзінің энтропиясы – ақпараттың мөлшерін көрсетеді. Көбінесе, бастапқы кодтар ақпарат көзіндегі артық ақпаратты азайтуға және көбірек мәлімет беретін аз биттермен оны ұсынуға тырысады. Белгілі бір ықтималдық моделіне сәйкес хабарламалардың орташа ұзындығын ең төменге дейін азайтуға бағытталған деректерді сығымдау энтропиялық кодтау деп аталады. Ақпарат көзін кодтау схемаларының әртүрлі әдістері ақпарат көзінің энтропия шегіне жетуге ұмтылады. C(x) ≥ H(x), мұнда H(x) – ақпарат көзінің энтропиясы (битрат), ал C(x) – сығымдалғаннан кейінгі битрат. Ешқандай ақпарат көзін кодтау схемасы ақпарат көзінің энтропиясынан жақсы нәтиже бере алмайды.

Мысал

Факсимильдік хабар алмасуда қарапайым сериялық код қолданылады. Деректерді кодтау жіберушіге қажетсіз артық ақпаратты жояды, соның салдарынан хабар таратуға қажетті жолақтық ені азаяды.

Каналды кодтау

Каналдық кодтау теориясының мақсаты – жылдам таралатын, көптеген жарамды кодты сөздерді қамтитын және көптеген қателерді түзете алатын немесе кем дегенде анықтайтын кодтарды табу. Бұл салалардағы өнімділік өзара байланысты емес, бірақ олардың арасында компромисс болады. Сондықтан, әртүрлі кодтар әртүрлі қолданбалар үшін оңтайлы. Бұл кодтың қажетті қасиеттері негізінен деректерді тарату кезінде қателер пайда болу ықтималдығына байланысты. Типик CD-де бұзылулар көбінесе шаң немесе сызықтардан туындайды. CD-лер деректерді дискіге тарату үшін өзара араластырылған Reed–Solomon кодтауын пайдаланады. Бұл өте жақсы код болмаса да, қарапайым қайталау коды түсінікті мысал ретінде қызмет ете алады. Біз дыбысты білдіретін деректер блогын алып, оны үш рет жіберсек дейік. Қабылдаушыда біз үш қайталауды біт бойынша қарап, көпшілік дауыспен шешеміз. Бұл жердегі ерекшелік – біз біттерді тікелей ретпен жібермейміз, оларды араластырамыз. Деректер битінің блогы алдымен 4 кіші блокқа бөлінеді. Содан кейін біз блок бойынша кезегімен өтіп, бірінші блоктан бір біт, содан кейін екінші блоктан бір біт, және т.б. жібереміз. Бұл деректерді дискі бетіне тарату үшін үш рет қайталанады. Қарапайым қайталау кодының жағдайында бұл тиімді көрінбеуі мүмкін. Дегенмен, осы араластыру техникасын қолданғанда, сызық немесе шаңның тудырған "жарылыс" қатесін түзетуде өте тиімді болатын, күшті кодтар бар. Басқа кодтар әртүрлі қолданбалар үшін қолайлырақ. Алыс ғарыш байланыстары қабылдағыштың жылу шуымен шектеледі, ол жарылыс сипатынан гөрі үздіксіз сипатқа ие. Сол сияқты, тар жолақты модемдер телефон желісіндегі шумен шектеледі, ол үздіксіз кедергі ретінде жақсы сипатталады. Ұялы телефондар жылдам өшіп-қосылу құбылысына ұшырайды. Жоғары жиіліктердің қолданылуы сигналдың тіпті қабылдағыш бірнеше сантиметрге жылжытылған жағдайда да жылдам жоғалуына себеп болуы мүмкін. Тағы да, осы құбылысқа қарсы күресуге арналған арна кодтарының бір класы бар.

Сызықтық блок кодтары

Сызықтық блок кодтары сызықтық қасиетке ие, яғни кез келген екі код сөзінің қосындысы да код сөзі болады, және олар бастапқы биттерді блоктар түрінде өңдейді, сондықтан оларды сызықтық блок кодтары деп атайды. Сызықтық емес блок кодтары да бар, бірақ осы қасиетсіз кодтың жақсы екенін дәлелдеу қиын. Кодтың тағы бір қасиеті – бір код сөзінің қанша көршісі болуы мүмкін. Мысал ретінде тиындарды қарастырайық. Бірінші кезде монеталарды тіктөртбұрышты торға орналастырамыз. Әрбір тиынның 4 жақын көршісі болады (және 4 бұрыштағы, олар алысрақ). Алтыбұрышта әрбір тиынның 6 жақын көршісі болады. Өлшемдерді арттырғанда, жақын көршілердің саны өте жылдам өседі. Соның салдарынан, шудың қабылдағышты көрші код сөзін таңдауға итермелеуінің (демек, қатеге) мүмкіндіктері де артады. Бұл блок кодтарының, тіпті барлық кодтардың негізгі шектеуі. Жеке көршіге қате жіберу қиынға соғуы мүмкін, бірақ көршілердің саны жеткілікті болуы мүмкін, сондықтан жалпы қателік ықтималдығы артады. Бұл ең белгілі пішіндеу кодтарының бірі.

Конволюциялық кодтар

Конволюциялық кодтың идеясы – әр кодтық сөз символын түрлі кіріс хабарлама символдарының салмақталған қосындысы етіп жасау. Бұл LTI жүйелерінде жүйе шығысын табу үшін қолданылатын конволюцияға ұқсас, егер сіз кіріс және импульстік жауапты білсеңіз. Сондықтан, біз жүйелік конволюциялық кодолағыштың шығысын табамыз, ол кіріс битінің конволюциялық кодолағыш күйлерімен, тіркегіштерімен конволюциясы болып табылады. Негізінен, конволюциялық кодтар шуға қарсы эквивалентті блок-кодға қарағанда артық қорғаныс ұсынбайды. Көп жағдайда олар бірдей қуатты блок-кодқа қарағанда іске асырудың қарапайымдығын ұсынады. Кодолағыш әдетте жай схема болып табылады, оның күй жады және кері байланыс логикасы бар, көбінесе XOR қақпалары. Декодер бағдарламалық қамтамасыз ету немесе микропрограммалық қамтамасыз ету арқылы іске асырылуы мүмкін. Витерби алгоритмі – конволюциялық кодтарды декодтау үшін қолданылатын оптималды алгоритм. Есептеу жүктемесін азайту үшін оңайлатулар бар. Олар тек ең мүмкін болатын жолдарды іздеуге сүйенеді. Олар оптималды болмаса да, көбінесе шу деңгейі төмен ортада жақсы нәтижелер береді. Конволюциялық кодтар дауыс жолақты модемдерде (V.32, V.17, V.34) және GSM ұялы телефондарында, сондай-ақ спутниктік және әскери байланыс құрылғыларында қолданылады.

Криптографиялық кодтау

Криптография немесе криптографиялық кодтау – үшінші тараптардың (қарсыластар деп аталатын) болуындағы қауіпсіз байланыс техникаларын зерттеу және қолдану практикасы. Көбінесе, бұл қарсыластарды тоқтатуға арналған протоколдарды құру және талдау туралы; деректердің құпиялылығы, деректердің толықтығы, аутентификация және жауапкершіліктен босату сияқты ақпараттық қауіпсіздіктің әртүрлі аспектілері қазіргі заманғы криптографияның негізгі бөлігін құрайды. Қазіргі заманғы криптография математика, компьютерлік ғылым және электротехника ғылымдарының тоғысқан жерінде пайда болды. Криптографияның қолданылуына банкомат карточкалары, компьютерлік парольдер және электрондық коммерция жатады. Криптография, қазіргі заманға дейін, шифрлаумен, яғни ақпаратты оқылатын күйден түсініксіз нәрсеге айналдырумен шамалас болды. Шифрланған хабардың авторы бастапқы ақпаратты қалпына келтіруге қажетті декодтау әдісін тек көздеген алушылармен ғана бөлісіп, басқа біреулердің солай істеуіне мүмкіндік бермейтін. Бірінші дүниежүзілік соғыстан бастап және компьютерлердің пайда болуымен криптологияны жүзеге асыруға қолданылатын әдістер күрделене түсті және оның қолданылу аймағы кеңейді. Қазіргі заманғы криптография математикалық теория мен компьютерлік ғылымның тәжірибесіне негізделген; криптографиялық алгоритмдер есептеу қиындығына байланысты болжамдарға сүйене отырып жасалады, бұл алгоритмдерді кез келген қарсыластың тәжірибеде бұзуын қиындатады. Мұндай жүйені теориялық тұрғыдан бұзу мүмкін, бірақ белгілі бір практикалық құралдармен оны іске асыру мүмкін емес. Сондықтан мұндай схемалар есептеу тұрғысынан қауіпсіз деп есептеледі; теориялық жетістіктер, мысалы, бүтін сандарды жіктеу алгоритмдерінің жақсаруы және жылдам есептеу технологиялары осы шешімдерді үнемі жаңартуды талап етеді. Ақпараттық қауіпсіздіктің теориялық тұрғыдан қамтамасыз етілген схемалары бар, оларды шексіз есептеу қуатымен де бұзу мүмкін емес – мысалы, бір реттік блокнот, бірақ мұндай схемаларды іске асыру теориялық тұрғыдан бұзуға болатын, бірақ есептеу тұрғысынан қауіпсіз механизмдерге қарағанда қиын.

Жолды кодтау

Сызықтық код (сонымен қатар цифрлық негізді жолақты модуляциялау немесе цифрлық негізді жолақты тарату әдісі деп аталады) – негізді жолақты тарату мақсатында коммуникациялық жүйеде қолдануға арналған таңдалған код. Сызықтық кодтау көбінесе цифрлық деректерді тасымалдау үшін пайдаланылады. Сызықтық кодтау физикалық каналдың (және қабылдау жабдығының) ерекшеліктеріне оңтайлы бейімделген амплитудалық және уақыт бойынша дискретті сигнал арқылы тасымалданатын цифрлық сигналды көрсетуден тұрады. Тасымалдау желісіндегі цифрлық деректердің 1-лері мен 0-дарын көрсету үшін қолданылатын кернеу немесе ток толқынының пішіні сызықтық кодтау деп аталады. Сызықтық кодтаудың жалпы түрлері – бірполярлы, полярлы, биполярлы және Манчестер кодтаулары.

Кодтау теориясының басқа да қолданыстары

Кодтау теориясының тағы бір мәселесі – синхрондауға көмектесетін кодтарды жобалау. Кодты фазалық ығысуды оңай анықтап, түзетуге және бір арнада бірнеше сигнал жіберуге мүмкіндік беру үшін жасауға болады. Кодтардың тағы бір қолданылуы, кейбір ұялы телефон жүйелерінде қолданылатын кодты бөліп көптеген қол жеткізу (CDMA) технологиясы болып табылады. Әрбір телефонға басқа телефондардың кодтарымен шамамен байланысты емес код тізбегі тағайындалады. Хабар жіберу кезінде, код сөзі дауыстық хабарды білдіретін дерек биттерін модуляциялау үшін қолданылады. Қабылдағышта деректерді қалпына келтіру үшін демодуляция процесі жүргізіледі. Бұл класс кодтардың қасиеттері көптеген пайдаланушыларға (әр түрлі кодтармен) бір уақытта бір радиоарнаны пайдалануға мүмкіндік береді. Қабылдағышқа басқа пайдаланушылардың сигналдары демодуляторға тек төмен деңгейдегі қана шу ретінде көрінеді. Кодтардың тағы бір жалпы класы – автоматты қайта сұрау (ARQ) кодтары. Бұл кодтарда жіберуші әрбір хабарламаға қателерді тексеру үшін, әдетте, тексеру биттерін қосу арқылы қосымша ақпарат қосады. Егер тексеру биттері хабарламаның қалған бөлігімен сәйкес келмесе, қабылдаушы жіберушіден хабарламаны қайта жіберуді сұрайды. Көптеген кең аумақтық желі протоколдары, ең қарапайымдарынан басқа, ARQ қолданады. Көп қолданылатын протоколдарға SDLC (IBM), TCP (Интернет), X.25 (Халықаралық) және тағы да басқалары жатады. Бұл тақырып бойынша зерттеулердің кең саласы бар, себебі қабылданбаған пакет пен жаңа пакетті салыстыру мәселесі туындайды. Бұл жаңа пакет пе, әлде қайта жіберілгені ме? Әдетте, TCP-дегідей, нөмірлеу схемалары қолданылады.

Топтық сынақ

Топтық тестілеу кодтарды өзгеше пайдаланады. Ішінде өте аз бөлігі белгілі бір ерекшеліктерімен көзге түсетін үлкен топты қарастырайық (мысалы, кемшілікті өнімдер немесе жұқтырған сынау қатысушылары). Топтық тестілеудің мақсаты – мүмкіндігінше аз тесттер арқылы қай заттардың "ерекше" екенін анықтау. Бұл мәселенің тамыры Екінші дүниежүзілік соғыс кезінде АҚШ Әскери-әуе күштерінің сарбаздарын сифилис жұқтырғанына тексеру қажеттілігінен туындады.

Аналогты кодтау

Ақпарат мидың нейрондық желілерінде, аналогты сигналдарды өңдеуде және аналогты электроникада аналогты түрде кодталады. Аналогты кодтаудың ерекшеліктеріне аналогты қателерді түзеу, аналогты деректерді сығу және аналогты шифрлеу кіреді.

Нейрокодтау

Нейрокодтау – нейробиология саласының бір бөлігі, ол мидағы нейрондық желілер арқылы сезімдік және басқа да ақпараттың қалай ұсынылғанын зерттейді. Нейрокодтауды зерттеудің негізгі мақсаты – стимул мен жеке немесе нейрондық жауаптар тобы арасындағы қатынасты, сондай-ақ топтағы нейрондардың электрлік белсенділігі арасындағы қатынасты анықтау. Нейрондар сандық және аналогтық ақпаратты кодтай алады деп саналады, сонымен қатар олар ақпараттық теорияның қағидаларын сақтайды, ақпаратты қысқартады, миға және жалпы жүйке жүйесіне жіберілетін сигналдардағы қателерді анықтап, түзетуге қабілетті.