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

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

Кілттік сздер:антикод, айтымды кодтар

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

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

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

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

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

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

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

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

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

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

 

Дріс

Таырып. Сызыты (топты кодтар). Циклды кодтар. Синдроп бойынша декодтау.

Жоспар: Сызыты кодтар. Циклды кодтар. Синдроп бойынша декодтау.

Кілттік сздер:цикл, синдроп

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

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

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

 

Дріс

Таырып.Симметриялы емес ателіктерді тзететін квадрат.

Жоспар: квадрат кмегімен симметриялы емес ателіктерді тзетіп йрету.

Кілттік сздер:симметрия

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

Симметриялы емес ателіктерді тзететін квадрат

Хемминг бірінші болып «ателерді тзейтін кодтарды» (Error-Correcting Code, ECC) сынандыы аны екенін білеміз. Бл кодтарды азіргі заманы модификациялары барлы апараттарды сатау жйелерінде жне жад пен процессор арасындаы алмасулар шін олданатыны белгілі. Оларды бір нсасы Рид-Соломонны коды компакт-дискілерде олдланылады. Хэмминг тсілі бойынша жасалынан кптеген кодтар нсалары бар, олар кодтау алгоритмдері бойынша жне тексеретін биттер саны бойынша айырмашылытары бар. Мндай кодтара планетааралы станциялармен космосты байланыс жасау шін ерекше кіл беріле бастады, мысалы, Рид-Мюллерді кодтарын 7 апаратты битке 32 тексеруші бит немесе 6 апаратты бита – 26 тексеруші биттар келетін болды. Хемминг зіні мааласын 1950 жылы жарыа шыарды, бірата ішкі жазбаларда кодтау теориясы 1947 жылмен белгіленген. Сондытанда кейбіреулер кодтау теориясыны атасы ретінде Шеннонды емес, Хеммингті атау керек деп ойлайды. Бірата, техника тарихында алашыны іздеу пайдасыз нрсе.

ECC жаа кодтарды бірі ретінде LDPC (Low-Density Parity-check Code) кодын айтуымыза болады. Негізінде олар отыз жыл брын танымал блан, бірата азіргі уаытта олара ерекше кіл блінуде. LDPC коды 100-пайызды анытылыы бомаанмен, ол атені ммкіндігін керекті нтижеге дейін жеткізуімізге ммкіндік береді жне сонымен атар каналды жіберу ммкіндігі максимальді толы трде олданылады. Олара «турбокодтар» (Turbo Code) те жаын келеді, олар алыс космостаы объектілермен жмыс жасаанда те олайлы.

 

Дріс

Таырып.Байтты кодтарды халыаралы жйелері. Рида – Маллер кодтары.

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

Кілттік сздер:алфавит, халыаралы жйе

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

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

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

I(A) I(B),

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

m/n, атынынасы кодттау шін лданылатын екінші алфавитті белгілеріні орта мнін сипаттайды жне оны код зындыы немесе код тізбегіні зындыы деп атайды жне K(B) деп белгілейміз(жоары индекс алфавитті кодттарын крсетеді).

Жеке жадайда,I1(B)=log2M, Хартли формуласына сйкес екінші алфавитті керек белгілеріні пайда болуы ммкін боланда, сонда

(1)

Шыады.

Тілді артышылыын сипаттайтын Rбиіктігіні аналогиясы бойынша кодтты артышылы атынасын (Q) енгізуімізге болады:

(2)

Крсетілген шарт бойынша кодттау операциясы бастапы мліметті анша есеге дейін зартандыын кре аламыз Qкіші болан жадайда кодтты тиімді екенін крдік.

Дріс

Таырып. Мебиус функциясы жне синхромизацияланатын кодтар.

Жоспар: Синхромизацияланатын кодтармен таныстыру.

Кілттік сздер:мебиус функциясы

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

Мебиус функциясы жне синхромизацияланатын кодтар

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

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

Дріс

Таырып. Латынды квадраттар жне кодтар.Адамар матрицалары жне кодтау.

Жоспар:Латынды квадраттар жне кодтар трін арастыру

Кілттік сздер:квадрат

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

Латынды квадраттар

Апаратты жіберуде кедергілер болмаан жадайда мліметтерді кодтауды мынандай нсасын кодтайтын алфавитті бір белгісіне сйкес келетіні бар болуы ммкін, код белгілеріні орташа мні алашы жне екінші алфавитті апаратты орта мніні атынасына жаын болады.

Кодты артышылы тсінігін пайдалана отырып бл теорияны ысаша былай жазуымыза болады:

Апарат жіберуде кедергілер болмаан жадайда мліметтерді кодтауды мынандай нсасы бар болады: код артышылыы р уаытта 0-ге жаын болады.

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

Ары арай M = 2 жадайымен шектейміз, яни жолдарында кодтты крсететін екі тип сигналдары олданылады- бірінші іске асырылатын нса ал екінші оны жо болуы(пауза); бар болуы жне жо болуы; мндай кодттауды екілік кодттау деп атайды.

Екілік алфавитті белгілерін "0" жне "1" деп белгілейміз,біра оларды сан ретінде емес ріп ретінде арастыруымыз керек. Бл кодтты олайлылыы санда рбір элементарлы сигнал зінде1 бит апараты бар (log2M = 1); сонда Шеннонны 1-ші теоремасын аламыз:

I1(A) K(2)

жне Шеннонны бл теоремасы келесідей сипатталады:

Апарат жіберуде кедергілер болиаан жадайда екілік кодтты орташа зындыы алашы алфавитті белгісіне келетін апаратты орта мніне сйкес келеді.

Екілік кодттау шін формула келесідей болады:

Екілік кодттауда жіберілген апаратты саныны анытамасы импульстар(бірлік) жне паузаларды (ноль) санын есептеумен аламыз. Осы кезде мынандай проблема туады: жеке кодттарды амалдар аымынан ажыратып алуы.

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

кесте 1. иылысу нсалары