Таырыбы. Кодтау: тарихы жне алашы адамы.

Жоспары. Кодтау теориясыны даму тарихымен таныстыру. Жалпы кодтау дістерімен таныстыру.

Кілттік сздер: Кодтау,

Иллюстрациялы материал:слайд

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

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

Кодтау теориясы мліметтерді жоалтпай алуды амтамасыз етеді.

Мліметтерді кодтауды ажеттілігімен алашы рет жз елу жыл брын тап болды. Каналдар те ымбат жне сенімсіз боландытан телеграммаларды жіберуді те тиімді жолдары арастырылды.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 жылы американды Гарри Найквист цифрларды принциптерін жне анал

Дріс

Таырып.Шифрлар. Абстрактілі алфавит.

Жоспар:Абстрактілі алфавит трлерімен арастырылады. Шифрлармен таныстыру.

Кілттік сздер:алфавит, унарлы

Иллюстрациялы материал:слайд

Абстрактілі алфавит трлерімен

Осы адамда санау жйесіні трін арастырайы. Кейбір кері атысты санды тсіндірейік. рбір сан з тсінігін жне формасын береді. Санны тсінігі баса сандардан (лкен, кіші немесе те) болады. Немесе осьтік тізімі бойынша. Форма крсеткіші мен оны аты жазылуы тиіс. Сонда тізім белгі кмегімен крсетіледі. Сан екі рет айталануы ммкін. Біра р трлі крсеткішпен жазылады.

Санны санау жйесі арылы оны крсеткіш дісін табуа болады.

Санау жйесі- бл санны ережесі бойынша жасалады жне берілген сандар арылы жинатау. Адамдар санны жазылуы бойынша р трлі тсілді олданады. Оларды топа блуге болады:

· Унарлы

· Позиционды емес

· Позиционды

Унарлы- бл санау жйесінде санны жазылу бойынша бір белгіні ана олданады. Ол I (сызыша) трады жне I осады. Оны клемі з санына те. Осы жйе балалара бастапы сандарды йретеді. (санау таяшасын еске тсіруге болады) унарлы жйе педагогтара те маызды. йткені бл оай діс жне операция болып келеді. Унарлы жйе санны белгісін жне рамындаы бірлігін крсетеді. Унарлы жйеде санды жазу шін біз Z₁- ді олданамыз.

Позиционды емес- е таралагн Римдік санау жйесі. Кейбір сандар лкен латын рпімен жазылады. 1-I, 5-V, 10- X, 50- L, 100- C, 500- D, 1000- M олданан сандар базадаы келесі ереже ереже арылы тізіледі:

Мысалы: XIX- 19 саны, MOXLIX- 1549 саны. Бл тсілде жазу лкен жне олайсыз. Одан да олайсыз егер біз арифметика операциясын жасаса. Ноль жне сан белгісі М- нан лкен сондытан римды ріптерге кез-келген санды жазуа ммкіндік бермейді. (натуралды сандарда). Сол себептен Римдік сандар тек ана нмірлеу шін ана олданылады.

 

азіргі кезде сандарды позициялы жйесі олданылады.

Позициялы деп санау жйесін айтады. Бл баса сан арасындаы санны орналасу орнын немесе позициясын крсетеді. азір таралан жйесі бар жазылуы бойынша 10 цифр олданылады. Олар: 0,1,2,3,4,5,6,7,8,9. Бл сандар крсеткішті ысаруын крсетеді.

Мысалы:

272,12=2*10²+7*10⁸+2*10⁰+1*10^-1+2*10^-2

Берілген сандарда 2 ш рет айталанады. Біра бл санны позициясын крсетеді. Бдан санны максималды тбірінен бірге кеміген. Онды санау жйесі осыдан шыан тсінікті, унарлы жйе бойынша жасалан. Бдан брын тарихи бестік, алтылы, он екілік, жиырмалы жне де алпысты жйе болан деп длелденді.

 

Унарлы менРимдік санау жйесіні айырмашылыы болып табылатын осу жне азайту базистік саны болып табылады. Ол санды ранымен, позициялы сана жатпайды. Осы жйені аддитивтік деп атайды. Позициядан айырмашылыы аддитивтікті мультипликатты деп санауа болады. Санны лшемі кбейту мен осу арылы табылады. Е басты айырмашылыы позицияны кейінгі белгісіне ойылады.(санды онды разряда блуі оны сан белгісімен белгілейді). Сандарды шексіз жазуа болады, оны аддитивтіге араанда, позициялы жйеде жазанымыз оай болады. Осылай кбейту жне блу операциясы жасалады. Осы тсіл компьютерге жне адама шыару оай.

 

Бкіл санны маынасы бірлік крсеткішіне кіреді. Бны нтижесі санау жйесінде брі бір бірдей болып алады. Айырмашылыы тек крсету клем формасынан болады. Мысалы:

IIIII₁=5₁₀=101₂=10₅=5₆=5₁₆

Баса сзбен бны крсеткіші лкен болмайды. Бл онды жйені орнына мысалы екілік санау жйесін олдануа болады.

 

Дріс