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

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

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

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

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

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

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

Мәліметтерді кодтаудың қажеттілігімен алғашқы рет жүз елу жыл бұрын тап болды. Каналдар өте қымбат және сенімсіз болғандықтан телеграммаларды жіберудің өте тиімді жолдары қарастырылды.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₁₆

Басқа сөзбен бұның көрсеткіші үлкен болмайды. Бұл ондық жүйенің орнына мысалы екілік санау жүйесін қолдануға болады.

 

Дәріс