Кодтау теориясы. Кодтау: тарихы және алғашқы қадамы

Кодтау  теориясы. Кодтау: тарихы және алғашқы  қадамы.

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

Каналдар өте  қымбат және сенімсіз болғандықтан телеграммаларды  жіберудің өте тиімді жолдары  қарастырылды.1845 жылы пайдалануға арнайы кодтау кітаптары шықты; олардың көмегімен телеграфистер қолмен мәліметтердегі ұзақ сөйлемдерді қысқа кодтармен алмастырды. Сол кездері мәліметтердің жіберілуінің дұрыстығын тексеру үшін жұптық бақылау әдісі қолданылды, бұл әдісті перфокарталардың дұрыстығын тексеру үшін компьютердің бірінші және екінші буындарында да қолданылды. Ол үшін ең соңғы мәліметтер колодасына арнайы дайындалған бақылау сомасы бар картаны салған. Егер енгізу құрылғысы сенімсіз болса (немесе колода тым ұзын болған жағдайда), онда қате тууы мүмкін. Оны жөндеу үшін картадағы сомамен сәйкес келмегенше процедураны қайталай беретін. Бұл сұлбаның ыңғайсыз болғанымен қатар, ол екі есе қателер жіберетін. Байланыс каналдарының дамуымен қатар бақылаудың өте тиімді механизмі керек болды.

Бұл мәселенің теориялық  шешімін алғашқы болып ақпараттың статистикалық теориясынының негізін  қалаушы Клод Шеннон ұсынды. Шеннон өз заманының жұлдызы болды,ол АҚШ-тың  академиялық элитасынынң мүшесі болған. Ванневар Буштың аспиранты  болып, ол 1940 жылы жасы 30 жетпеген оқымыстыларға  берілетін Нобель атындағы сыйлыққа ие болды (Нобель премиясымен шатастырмаңыздар). Bell Labs жұмыс істеп жүріп  Шеннон «Мәліметтерді жіберудің математикалық теориясы» (1948) атты жұмыс жазды, ол жұмыста Шеннон  каналдың жіберу мүмкіндігі мәліметтердің энтропия бастауынан жоғары болса, онда мәліметтерді ешқандай ақаусыз жіберілетіндей етіп кодтап қоюға болатынын дәлелдеді.Бұл түйіндеме Шеннонның көптеген дәлелдеген теоремалардың біреуінде бар. Сонымен қатар, ол каналда шудың бар болуына қарамастан мәліметтің жіберілу мүмкіндігінің теориялы түрде дәлелдеп берді.Шеннонның Мичиган штатында өзінің туып өскен қаласында орнатылған ескерткішінде ойып жазылған формуланы C = W log ((P+N)/N) Альберт Эйнштейннің E = mc² формуласының мәнімен салыстырады.Шеннонның еңбектері ақпараттар теория облысындағы ары қарай зерттеулерінде өз ықпалын тигізді, бірақта оларда инженерлік практикалық қосымшасы бар болмады. Теориядан практикаға алмасу Ричарда Хэммингтің жұмысынан байланысты болды. Ол Шеннонның Bell Labs бойынша әріптесі болды және кодтар класын ашқандығы үшін әйгілі болды, оларды «Хэмминг коды» деп атады. Өзінің жаңалығын Хемминг 40 жылдардың ортасында  Bell Model V есептеуіш  машинасының перфокарталармен жұмыс жасау қолайсыздығынан ашты деген аңыз бар. Оған операторлар жоқ болғанда, яғни демалыс күндерде машинамен жұмыс жасауға мүмкіндік берді және ол өзі енгізулермен жұмыс жасады. Хемминг байланыс каналдарындағы, сонымен қатар компьютерлердегі ақпараттарды беру магистральдарында, ең бастысы жад пен процессор арасындағы қателерді түзете алатын кодты ұсынды. Хемминг коды Шеннон теоремасында көрсетілген мүмкіндіктерді практикалық түрде қалай іске асыруға болатындығын көрсетеді.

     Хемминг  өзінің мақаласын 1950 жылы жарыққа  шығарды, бірақта ішкі жазбаларда  кодтау теориясы 1947 жылмен белгіленген. Сондықтанда кейбіреулер кодтау теориясының атасы ретінде Шеннонды емес, Хеммингті атау керек деп ойлайды. Бірақта, техника тарихында алғашқыны іздеу пайдасыз нәрсе.

   Хемминг  бірінші болып «қателерді түзейтін  кодтарды» (Error-Correcting Code, ECC) ұсынғандығы  анық екенін білеміз. Бұл кодтардың  қазіргі заманғы модификациялары  барлық ақпараттарды сақтау жүйелерінде  және жад пен процессор арасындағы  алмасулар үшін қолданатыны белгілі.  Олардың бір нұсқасы Рид-Соломонның  коды компакт-дискілерде қолдланылады.  Хэмминг тәсілі бойынша жасалынған көптеген кодтар нұсқалары бар, олар кодтау алгоритмдері бойынша және тексеретін биттер саны бойынша айырмашылықтары бар. Мұндай кодтарға планетааралық станциялармен космостық байланыс жасау үшін ерекше көңіл беріле бастады, мысалы, Рид-Мюллердің кодтарын 7 ақпараттық битке 32 тексеруші бит немесе 6 ақпараттық битқа – 26 тексеруші биттар келетін болды.ECC жаңа кодтардың бірі ретінде LDPC (Low-Density Parity-check Code) кодын айтуымызға болады. Негізінде олар отыз жыл бұрын танымал блған, бірақта қазіргі уақытта оларға ерекше көңіл бөлінуде. LDPC коды 100-пайыздық анықтылығы бомағанмен, ол қатенің мүмкіндігін керекті нәтижеге дейін жеткізуімізге мүмкіндік береді және сонымен қатар каналдың жіберу мүмкіндігі максимальді толық түрде қолданылады. Оларға  «турбокодтар» (Turbo Code) өте жақын келеді, олар алыс космостағы объектілермен жұмыс жасағанда өте қолайлы.

Кодтау теориясының  тарихына Владимир Александрович Котельниковтың аты нық жазылған. 1933 году  «Материалах по радиосвязи к I Всесоюзному съезду по вопросам технической реконструкции связи»-да ол өзінің «О пропускной способности ‘эфира’ и ‘проволоки’» атты жұмысын жариялады. Бұл теоремада жіберілген сигнал ақпараттың жоғалтуынсыз қайтадан қалпына келетін шарттарды анықтайды.

Бұл теореманы әркім  әрқалай атайды, соның ішінде «WKS теоремасы» (аббревиатура WKS взята от Whittaker, Kotelnikov, Shannon). Кейбір бастауларда   Nyquist-Shannon sampling theorem және Whittaker-Shannon sampling theorem деп те аталады, ал өзіміздің жоғарғы оқу орындарының оқулықтарында жай ғана «Котельников теоремасы» деп кездестіреміз. Шын мәнінде теореманың өзіндік тарихы бар. Оның бірінші бөлігін 1897 жылы француз математигі Эмиль Борель дәлелдеген. Ал 1915 жылы өзінің еңбегін Эдмунд Уиттекер қосты.  1920 жылы жапондық  Кинносуки Огура  Уиттекер зерттеулеріне өзінің жөндеулерін жариялады, ал  1928 жылы американдық Гарри Найквист цифрлардың принциптерін және анал

Фоно  коды. Префикстің қасиеті. Кодтау және декодтау.

Фоно коды. Префикстің қасиеті қарастырылады. Кодтау және декодтау амалдары қарастырылады.

Префикстің қасиеті, ол каналда шудың бар болуына  қарамастан мәліметтің жіберілу мүмкіндігінің  теориялы түрде дәлелдеп берді.Шеннонның  Мичиган штатында өзінің туып өскен  қаласында орнатылған ескерткішінде  ойып жазылған формуланы C = W log ((P+N)/N) Альберт  Эйнштейннің E = mc² формуласының мәнімен салыстырады.

Шеннонның еңбектері  ақпараттар теория облысындағы ары  қарай зерттеулерінде өз ықпалын  тигізді, бірақта оларда инженерлік практикалық қосымшасы бар болмады. Теориядан практикаға алмасу Ричарда  Хэммингтің жұмысынан байланысты болды. Ол Шеннонның Bell Labs бойынша әріптесі болды және кодтар класын ашқандығы  үшін әйгілі болды, оларды «Хэмминг коды»  деп атады. Өзінің жаңалығын Хемминг 40 жылдардың ортасында  Bell Model V есептеуіш  машинасының перфокарталармен жұмыс жасау қолайсыздығынан ашты деген аңыз бар. Оған операторлар жоқ болғанда, яғни демалыс күндерде машинамен жұмыс жасауға мүмкіндік берді және ол өзі енгізулермен жұмыс жасады. Хемминг байланыс каналдарындағы, сонымен қатар компьютерлердегі ақпараттарды беру магистральдарында, ең бастысы жад пен процессор арасындағы қателерді түзете алатын кодты ұсынды. Хемминг коды Шеннон теоремасында көрсетілген мүмкіндіктерді практикалық түрде қалай іске асыруға болатындығын көрсетеді.

Фоно коды. Берілген ондық санау жүйесінің түбірінен  басқа түбір жүйесін құру мүмкін болады. Р- санау жүйесінің түбірі болсын. Онда кез- келген сан Z (әзірше бүтін  санды қолданайық) көрсетілген шартпен Z<P^k(K≥0, бүтін сан) Егер Р көптік түрде болса, максималдық көрсеткіш жүйесі К-1-ге тең екенін көрсетеді.

Z_p=a_u-1*P^u-1+a_u-2*P^-2+…+a₁*P¹+a₀*P⁰=Σ^u-1_j-0aj*P¹

Aj коэфициенттің жүйелік түбір құрғандағы қысқартылған жазу саны:

Z_p=(a_k-1a_k-1…a₁a₀)

Индекс P Z санын көрсетеді, оның минималды көрсеткіші Р? Р aj 1 емес, өйткені барлық aj= 0 форма (1) түсінігін жоғалтады. Бірінші нәтижесі Р=2 бұл минималдық позициялық жүйе болып келеді. Санау жүйесінде екілік деп аталады. Екілік санау деп 0 және 1- ді айтады. Ал >(1) формасы 2 жүйесен құралады. Қызығушылық тура осы санау жүйесіне байланысты. Барлық компьютерлердегі санау жүйесі 0 және 1 көмегімен тек техника арқылы жасалады. Бұның көмегімен компьютерде сегіздік және он алтылық санау жүйесі қолданады.

 Шеннон теоремасы туралы түсінік..

Шеннон теоремасы көмегімен қателіктерді түзету.

Шеннон теориясында мәліметтерді кодтау. Блоктық екілік кодтау

Оптималдық коттау мәселесіне кірісейік. әзірше ең жақсы көрсеткіш (ең аз екілік) Хаффман әдісі- орыс алфавитінде 1% көрсетеді. Хаффман кодын жақсарту мүмкін емесін көрсетті. Бірақ Шеннонның бірінші теоремасы оған кері көсеткіш болып келеді. Шеннонның айтуы бойынша кодтау еселік пайдалы көрсеткішке жеткізуге болады. Бұл келіспеушіліктің туған себебі: біз кодтауды алфавитпен ғана шектелдік. Алфавиттік кодтаумен жіберіген жолдама тек бөлек белгілерді алфавиттік жолмен құрайды. Бірақ кодтау нұсқаулары болады және кодтық белгілер бірнеше әріптен тұрады. Бұны блоктық комбинация деп атайды. Блоктық код кемуді азайтады. Бұны мысалдан көруге болады. Сөздік бар әртүрлі тілде, n әрпі бар, n = 16000 тең. әр сөзге бір қалыпты екілік код қояйық. Кодтың ұзындығын табу үшін : кцкц           . Әр сөзге 14 ноль және 1 қоямыз. Бұған сәйкес екілік иероглиф шығады. Мысалы: Информатика сөзіне сәйкес коды 10101011100110, Наука сөзіне 00000000000001, ал интересная сөзіне- 00100000000010 бұдан шыққаны:

000000000000110101011100110000000000000001.

Бұл «ИНФОРМАТИКА ИНТЕРЕСНАЯ НАУКА» деген сөйлемді құрайды. Бұны бағалау өте оңай, ортаңғы ұзын орыс сөзі К^(r)= 6.3 әріптер (5,3әріп+ сөз арасындағы пробел) алфавит белгісінің ақпараты мынаған тең I⁽²⁾=K⁽²⁾/ K^(r)=14/6.3=2.222 бит, 2,545 биттен екі есе аз. Алфавиттікке қарағанда сөзді кодтау тиімдірек екенін көрсетеді.Егерде кодтаудығ тазалығын орнатып Хаффманның кодын қолдансақ, кодтаудың тиімділігі ұлғаяды. Бұндай тәжірибелерді Хаффман өз кезінде жасаған.

Сөздің орнына әріпті кодтауға болады. Мағынасы жоқ блоктарды  сөз ұзындығы бойынша бірдей деуге  болады. Блоктарды ұзартып Хаффман  кодын қолданып ортаңғы ақпарат  бір белгіге I теңестіруге болатынына қол жеткізді. 

Бірақ, оңай деп  қарамағанда блоктық және сөздік кодтау әдісінде өз кемшіліктері бар. Біріншіден: үлкен кодтық таблицаны  сақтау керек және әр қашанда код  орнатқанда немесе кодты шешкен кезде  көмегі керек. Бұл жадта үлкен  орын алады және жұмысты ақырын жүргізуі мүмкін. Екіншіден: сөйлесу тілінде  тудырмалы сөздер кездеседі. Мысалы: зат есім септігі орыс тілінде  немесе етістік формасы ағылшын  тілінде қазіргі кодтау әдістің  әр қайсысына өз кодын белгілеу керек. Бұдан кодтық таблицаны тағы бірнеше  рет үлкеюге алып келеді. Үшіншіден: стандартты таблицаның мәселесі туды. Сонымен төртінші алфавиттің кодтауының жақсылығы әрбір әріптен кез- келген сөзді кодтау мүмкін Сөзді  кодтаған кезде қолда бар сөздікті қолдануға болады. Көрсетілген себеп  блокты және сөзді кодтау тек теориялық  қызығушылық көрсетеді. Ал практикада кодтау алфавиті ғана қолданады. 

Кодтар, антикодтар. Хемминг коды. 

Кодтар, антикодтар. Хемминг кодымен таныстыру.

Информатиканың  бастапқы түсініктерін қарастырғанда  біз дискретті ақпаратты анықтау  үшін кейбір алфавиттерді қолданатынын білдік. Бірақта ақпарат пен алфавит  арасында біртектілік сәйкестік  жоқ. Басқа сөзбен айтқанда, бір ақпарат  әр түрлі әр түрлі алфавит арқылы көрсетілуі мүмкін. Мұндай мүмкіндіктің арқасында бір алфавиттен екіншісіне өту мәселесі туындайды, бірақта  мұндай алмастыру ақпаратты жоғалтуға  алып келмеуі тиіс. Алмастыруға дейінгі  ақпаратты– алғашқы; ал соңында көрсетілетін, яғни кодталған алфавитті- екінші деп атауға келісейік.

Анытамалар тізбегін еңгізейік:

Код – (1) сәйкес белгілерді бейнелейтін немесе олардың бір алфавиттің белгілермен сәйкес келуін зерттейтін ереже болып табылады; - (2) белгілерді көрсету үшін немесе олардың алғашқы алфавитпен сәйкес келуі үшін қолданатын екінші алфавиттің белгілері.

Кодтау – алғашқы алфавиттен кодтар тізбегімен көрсетілген ақпараттың алмасуы.

Декодтау – қайтымды кодтау операциясы, яғни алынған кодтар тізбегінен ақпаратты алғашқы алфавитке келтіру.

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

Қайтымды кодтаудың  мысалы болып телеграфтық кодтауындағы белгілер табылады. Қайтымды емес кодтаудың  мысалы ретінде бір тілден екінші тілге аудару және керісінше аударманы  алуымызға болады.

Осылайша, кодтау ақпарат  беруді және сатауды қамтамасыз етеді. Ертеректе айтылып кеткендей, ақпаратты  сақтау оның таратушыларына байланысты, ал ақпарат беру – уақыт ағымындағы күйінің аласуына байланысты. Бұл  күйлерді немесе дыбыстарды  элементарлы дыбыстар деп атаймыз.

Келесі қадамда кодтау есебінің математикалық қойылымын қарастырамыз.

Циклдық кодтар. Синдроп бойынша декодтау.

.Циклдық кодтар. Синдроп бойынша декодтау.

Циклдық кодтар. Синдроп бойынша декодтау.

Теориялық информатика. Шеннон теориясында ақпаратты кодтау. Компьютерде санды қамтамасыздандыру. Компьютермен әр түрлі есептеу және есептік информация арқылы есеп шығарғанда немесе компьютерлік графикада қолданады. Осыдан таңдау жүргіземіз, компьбтердегі  оптимплдық санды нақты 8- битті (байттық) бүтін санға қолданылатын кодтау. Бірақ, бұндай кодтау оптималды болмайды. Оны мына мысалдан көруге болады: берілген екі мәнді 13- саны 8- битті кодтау бөлек цифрларды ASCII кодында оның әдісі былай болып көрінеді: 00110001001100011 код 16- бит ұзындық болды. Егер ол екілік каскада бойынша берілсе,(мысалы, таңдаулы каскад алсақ «Угадай-ка- 16»  бұдан бері жазылды) онда төрт битті  тізімді аламыз 1101. Маңызды әр түрлі  түрмен көрсетпей-ақ берілгенді (әрәп немесе сан) көрсету. Онымен операцияларды  жасау. Әріптердің орнын бірдей қалдыру, санды өзгерту. Мысалы, басқа санның көмегімен түбір табу. Компьютердегі  формалармен салыстырғанда мектеп кезінен келе жатқан екі маңызды  түбір бар «Біріншіден сан  екілік санау жүйесі бойынша жазылады(бірінші  ондықтан қарағанда). Екіншіден санның жазылғанда аяқты разрядтардан басталады(арифметикада бұндай тәсіл мүмкін емес)»

 Рида – Маллер кодтары.

 Рида – Маллер кодтарымен таныстыру.

Рида – Маллер кодтары

Әрбір белгіге ақпараттың орта мәніне тең келетін N белгі A алғашқы алфавитінде бар болсын және олардың бар болу мүмкіндігі анықталған болсын I₁^(A) (төменгі индекс бірінші қозғалысты қарастыратынжағдайларды көрсетеді, ал жоғарғы индекс жақшаның ішінде алфавитті көрсетеді).  I₁^(A) ақпараттық орта сиымдылығына сәйкес келетін М белгі В екенін алфавитінде бар болсын, алфавитте көрсетілетін бастапқы мәліметтерде  n белгілер, ал кодтталған мәліметтерде – m белгілер бар болсын. Егер бастапқы мәліметте  I^(A) ақпарат бар болса, онда кодтталғанда – I^(B) болсын. Сонда кодттаудың қайтымы шарты төмендегідей жазылады: