Кодтау теориясы. Кодтау: тарихы және алғашқы қадамы.
Кодтау теориясы — компьютингтің дамуына өз үлесін қосқан математиканың бір облысы болып табылады. Оның таралу облысы мәліметтерді нақты каналдар бойынша беру, ал оның пәні берілген ақпараттың нақтылығын қамтамасыз ету болып табылады. Кейбірде кодтау теориясын шифрлеумен шатастырады, бірақ ол дұрыс емес: криптография кері есепті шешеді, оның мақсаты- мәліметтерден ақпаратты алуды қиындату.
Кодтау теориясы мәліметтерді жоғалтпай алуды қамтамасыз етеді.
Мәліметтерді кодтаудың қажеттілігімен алғашқы рет жүз елу жыл бұрын тап болды. Каналдар өте қымбат және сенімсіз болғандықтан телеграммаларды жіберудің өте тиімді жолдары қарастырылды.1845 жылы пайдалануға арнайы кодтау кітаптары шықты; олардың көмегімен телеграфистер қолмен мәліметтердегі ұзақ сөйлемдерді қысқа кодтармен алмастырды. Сол кездері мәліметтердің жіберілуінің дұрыстығын тексеру үшін жұптық бақылау әдісі қолданылды, бұл әдісті перфокарталардың дұрыстығын тексеру үшін компьютердің бірінші және екінші буындарында да қолданылды. Ол үшін ең соңғы мәліметтер колодасына арнайы дайындалған бақылау сомасы бар картаны салған. Егер енгізу құрылғысы сенімсіз болса (немесе колода тым ұзын болған жағдайда), онда қате тууы мүмкін. Оны жөндеу үшін картадағы сомамен сәйкес келмегенше процедураны қайталай беретін. Бұл сұлбаның ыңғайсыз болғанымен қатар, ол екі есе қателер жіберетін. Байланыс каналдарының дамуымен қатар бақылаудың өте тиімді механизмі керек болды.
Бұл мәселенің теориялық шешімін алғашқы болып ақпараттың статистикалық теориясынының негізін қалаушы Клод Шеннон ұсынды. Шеннон өз заманының жұлдызы болды,ол АҚШ-тың академиялық элитасынынң мүшесі болған. Ванневар Буштың аспиранты болып, ол 1940 жылы жасы 30 жетпеген оқымыстыларға берілетін Нобель атындағы сыйлыққа ие болды (Нобель премиясымен шатастырмаңыздар). Bell Labs жұмыс істеп жүріп Шеннон «Мәліметтерді жіберудің математикалық теориясы» (1948) атты жұмыс жазды, ол жұмыста Шеннон каналдың жіберу мүмкіндігі мәліметтердің энтропия бастауынан жоғары болса, онда мәліметтерді ешқандай ақаусыз жіберілетіндей етіп кодтап қоюға болатынын дәлелдеді.Бұл түйіндеме Шеннонның көптеген дәлелдеген теоремалардың біреуінде бар. Сонымен қатар, ол каналда шудың бар болуына қарамастан мәліметтің жіберілу мүмкіндігінің теориялы түрде дәлелдеп берді.Шеннонның Мичиган штатында өзінің туып өскен қаласында орнатылған ескерткішінде ойып жазылған формуланы C = W log ((P+N)/N) Альберт Эйнштейннің E = mc2 формуласының мәнімен салыстырады.
Шеннонның еңбектері ақпараттар теория облысындағы ары қарай зерттеулерінде өз ықпалын тигізді, бірақта оларда инженерлік практикалық қосымшасы бар болмады. Теориядан практикаға алмасу Ричарда Хэммингтің жұмысынан байланысты болды. Ол Шеннонның 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 жылы американдық Гарри Найквист цифрлардың принциптерін және анал
Ақпарат [мына сайттан][1] алынды.
[1]: http://zhgu.16mb.com/index.php/ru/2012-03-14-05-11-49/12-2011-11-24-15-34-13/60-2012-06-17-14-34-52.html
