Дәріс №4, 5 Дәрістің тақырыбы: Ақпаратты кодтау тарыхы Дәрістің мақсаты

1.Кодтау теориясы

2. Хемминг коды

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

Мәліметтерді кодтаудың қажеттілігімен алғашқы рет жүз елу жыл бұрын тап болды. Каналдар өте қымбат және сенімсіз болғандықтан телеграммаларды жіберудің өте тиімді жолдары қарастырылды.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 Всесоюзному съезду по вопросам технической реконструкции связи»-да ол өзінің «О пропускной способности ‘эфира’ и ‘проволоки’» атты жұмысын жариялады. Бұл теоремада жіберілген сигнал ақпараттың жоғалтуынсыз қайтадан қалпына келетін шарттарды анықтайды.
Санау жүйесі

Символдардың шектеулі жинақтау көмегімен сандар жазу ережелер жиынтығы санау жүйесі деп аталады. Санау жуйелері позиционды және позиционды емес болып болінеді. Позиционды емес жүйеге римдіктер санды белгілеу үшін қолданған жүйе мысал бола алады.

Позиционды санау жүйесінде қолданылатын символдар саны жүйе негізіне тең. Әр символдың салмағы (маңыздылығы) жүйе негізіне бөлінеді және жазылған санда берілген символдың алынатын позициясына тәуелді. Символ позициясының нөмірін разряд деп атайды.

Жалпы жағдайда n-разрядті жағымды N саныпозиционды санау жүйесінде негізімен мына өрнекпен көрсетіледі

Өндіріс электрониканың, микропроцессорлы техниканың және автоматиканың сандық құрылғыларында жиі позиционды санау жүйелерімен 2, 10, 16 негізінде жұмыс істейді.

Ақпаратты сандық және микропроцессорлі құрылғыларда өңдеу позиционды екілік санау жүйесінде (2 негізінде) жүргізіледі.

Екілік санды басқа санау жүйесінде көрсетілген сандардан айыру үшін, оны оң жақтан В (Binaire) жұрнағымен толықтырады, немесе 2 индексімен қамтамасыз етеді.

Екілік санды шағынырақ күйде көрсету үшін жиі оналтылық позиционды санау жүйесі қолданылады.Бұл жүйеде бірінші он натурал қатардағы 0ден 9ға дейін мүшелері, және бірінші алты латын әріптер Адан Fқа дейін (A = 10, B = 11, C = 12, D = 13, E = 14, F = 15) қолданылады. Оналтылық санды басқа санау жүйесінде көрсетілген сандардан айыру үшін , оны оң жақтан Н (Hexadecima) жұрнағымен толықтырады, немесе 16 индексімен қамтамасыз етеді.

Әртүрлі санақ жүйелерінің сандар сәйкестігі 1.1 кестесінде көрсетілген

Позиционды санақ жүйелерінде толық сандарды жүйеден қандай да негізбен ондық жүйеге аудару (1.1) формула бойынша орындалады. Мысалы 101011₂ екілік санын ондық санға түрлендіру 1.1 формуласына формальді мән енгізгенде болады
101011₂ = 1·2 ⁵ + 0·2 ⁴ + 1·2 ³ + 0·2 ² + 1·2 ¹ + 1·2 ⁰ =

=1·32 + 0·16 + 1·8 +0·4 + 1·2 + 1·1 = 32 + 8 + 2 + 1 = 43₁₀

Екілік санды ондыққа аударғанда, мәні 1-ге тең разрядтарда салмақтық коэффициент қалыптасады. Мысалы, 101011₂ екілік санын ондыққа аударғанда, екілік сандардың разрядтарына сай ондық салмақтық коэффициентін қойғанда мұндай нәтиже аламыз:

32 16 8 4 2 1

1 0 1 0 1 1

Бірлік 0,1,3,5 разрядтарында болады (разрядтар санағы кішісінен, нөлден басталады),сондықтан 0,1,3,5, немсе 1 + 2 + 8 + 32 = 43 разрядтарының салмақты коэффициенттері пайда болады.

Аударманы жеңілдету үшін жатқа 2ⁿ n = 0ден n = 14ке дейінсандарының ондық мәндерін білу қажет. Бұл мәндер 1.2 кестесінде көрсетілген.

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

43 ондық санын екілікке аудару мысалы:

43 |_2__

1 _20 10 |_2__

1 _10_ 5 |_2__

0 _ 4_ 2 |_2_

1 _2_ 1

0

43 ондық санын оналтылыққа аудару мысалы:

43 |_16_

_32_ 2

11

Аударма нәтижесі:43 ₁₀ = 2В ₁₆ ,өйткені 11₁₀ = В₁₆,

Аударымда екілік санды кіші разрядтан бастап тетрадтарға (4 разрядтардан тұратын топтар) бөледі. Үлкен топты керегінше екілік сан алдына нөл жазып тетрадаға дейін толтырады. Алынған тетрадаларды он алтылық сандарының разрядтарын көрсетеді, сондықтан аударымда екілік тетрада он алтылық санымен ауыстырылады (0000 ₂ 0_16ға сай, … 1111 ₂ F_16ғасай). Екілік тетрадалармен он алтылық сандардың сәйкестігі 1.1 кестесінде көрсетілген.

Екілік санды он алтылыққа аудару мысалы:
101011 ₂ = 0010 1011 ₂ = 2В _16.

2 ₁₆ В ₁₆.

Қайта өту аналогті түрде іске асады – он алтылық санның әр бір разряды оған эквивалентті екілік тетрадамен ауыстырылады.

Позиционды санау жүйелерімен қатар өндіріс электрониканың, микропроцессорлі техниканың, және автоматиканың сандық құрылғыларында позиционды емес жүйемен кодтар қолданылады.Жиі екілі- ондық және унитарлы жүйе көп қолданылады.

Екілі-ондық санау жүйесінде сан төрт разрядты екілік комбинацияның (тетрадалардың) келесіретін көрсетеді, оның саны эквивалентті ондық санының разряд санына тең. Әрбір екілік тетрада ондық санының бір разрядыныңекілік эквиваленті болып табылады. Екілік тетрада мен ондық сандардың сәйкестігі 1.1 кестесінде көрсетілген.Тетраданың сандық мәні 9дан (ондық эквивалентте) көп бола алмайтынын айта кету керек. Егер екілі- ондық санды тетрадалар арасында қалдырады, ал толмаған үлкен тетраданы нөлдермен толтырады.

Екілі-ондық санды басқа санау жүйедегі саннан айыру үшін оны оң жағынан BD (Binary Decimals) жұрнағымен толықтырады, немесе 2-10 индексімен қамтамасыз етеді.

Екілік санды ондыққа аудару мысалые:

2 ₁₀ 9 ₁₀.

Қайта өту аналогті түрде іске асады – ондық санның әр бір разряды оған эквивалентті екілік тетрадамен ауыстырылады.

Унитарлы жүйеде 1символы үнемі тек бір позицияда болады, ал қалған позицияларда 0 болады. 1 саны бар позиция нөмері (0ден бастап унитарлы санының ондық эквиваленті болып табылады. Нөлінші нөмір оң жақтағы шеткі.

Унитарлы (сегіз разряд үшін) және ондық санау жүйелерінің сан сәйкестігі 1.3кестесінде көрсетілген.