Individuaalne ülesanne
distsipliinil "Diskreetne matemaatika"
teema: "Kodeerimise arengulugu tänapäevani"

lõpetatud:
Grupp:

Moskva, 2011

Sissejuhatus
Info kodeerimise vajadus tekkis ammu enne arvutite tulekut. Kõne, tähestik ja numbrid pole muud kui süsteem mõtete, kõnehelide ja numbriline teave. Tehnikas tekkis kodeerimise vajadus kohe pärast telegraafi loomist, kuid eriti oluliseks muutus see arvutite leiutamisega.
Kodeerimise teooria ulatus laieneb andmete edastamisele reaalsete (või mürarikaste) kanalite kaudu ning teemaks on edastatava teabe õigsuse tagamine. Teisisõnu uurib see, kuidas andmeid kõige paremini pakkida, et pärast märku andmist saaks andmetest usaldusväärselt ja hõlpsalt kasulikku teavet eraldada. Mõnikord aetakse kodeerimise teooria segi krüpteerimisega, kuid see pole tõsi: krüptograafia lahendab pöördprobleem, selle eesmärk on raskendada andmetest teabe hankimist.
Käesolevas artiklis käsitleme kodeerimise arengu peamisi etappe kuni tänapäevani.
Kodeerimise arendamise ajalugu
Andmete kodeerimise vajadusega puututi esmakordselt kokku rohkem kui sada viiskümmend aastat tagasi, vahetult pärast telegraafi leiutamist. Kanalid olid kallid ja ebausaldusväärsed, mis muutis kulude minimeerimise ja telegrammi edastamise usaldusväärsuse suurendamise kiireloomuliseks. Probleem on muutunud veelgi teravamaks seoses Atlandi-üleste kaablite paigaldamisega. Alates 1845. aastast võeti kasutusele spetsiaalsed koodiraamatud; nende abiga "tihendasid" telegrafistid sõnumeid käsitsi, asendades tavalised sõnajadad lühemate koodidega. Samal ajal hakati ülekande õigsuse kontrollimiseks kasutama pariteeti, meetodit, mida kasutati perfokaartide sisestuse õigsuse kontrollimiseks isegi esimeste põlvkondade arvutites. Selleks sisestati viimasesse sisestuspakki spetsiaalselt ettevalmistatud kontrollsummaga kaart. Kui sisendseade ei olnud väga töökindel (või tekk oli liiga suur), võib tekkida tõrge. Selle parandamiseks korrati sisestusprotseduuri seni, kuni arvutatud kontrollsumma ühtis kaardile salvestatud summaga. See skeem on ebamugav ja jätab vahele ka topeltvead. Sidekanalite arenedes oli vaja tõhusamat kontrollimehhanismi.
Esimese teoreetilise lahenduse mürarikaste kanalite kaudu edastatava andmeedastuse probleemile pakkus välja statistilise informatsiooni teooria rajaja Claude Shannon. Bell Labsis viibides kirjutas Shannon teose A Mathematical Theory of Message Transmission (1948), kus ta näitas, et kui kanali ribalaius on suurem kui sõnumiallika entroopia, saab sõnumit kodeerida nii, et see edastatakse ilma põhjendamatu viivitus. Ühes oma teoreemis tõestas Shannon, et piisava ribalaiusega kanali olemasolul saab sõnumi edastada teatud ajaliste viivitustega. Lisaks näitas ta usaldusväärse edastamise võimalust kanalis esineva müra korral.
Valem C = W log ((P+N)/N) on nikerdatud Shannoni tagasihoidlikule mälestusmärgile tema Michigani kodulinnas.
Shannoni töö andis alust palju täiendavaid uuringuid infoteooria vallas, kuid neil puudus praktiline insenerirakendus. Üleminek teoorialt praktikale sai võimalikuks tänu Shannoni kolleegi Bell Labsi jõupingutustele Richard Hamming, kes kogus kuulsust Hammingi koodiklassi koodide avastamisega. On legend, et 40. aastate keskel releearvutusmasina Bell Model V perfokaartidega töötamise ebamugavus ajendas nende Hammingi koodide leiutamist. Talle anti aega masina kallal nädalavahetustel, kui operaatoreid polnud, ja ta ise pidi sisendiga askeldama. Hamming pakkus välja koodid, mis suudavad parandada vigu sidekanalites, sealhulgas arvutite andmeedastusliinides, peamiselt protsessori ja mälu vahel. Hammingi koodid näitasid, kuidas Shannoni teoreemi võimalusi saab praktikas realiseerida.
Hamming avaldas oma artikli 1950. aastal, kuigi sisearuanded dateerivad tema kodeerimise teooriat aastasse 1947. Seetõttu väidavad mõned, et kodeerimise teooria isaks tuleks pidada pigem Hammingit kui Shannonit.
Richard Hamming (1915 - 1998) omandas bakalaureusekraadi Chicago ülikoolis 1937. aastal. 1939. aastal omandas ta magistrikraadi Nebraska ülikoolis ja doktorikraadi matemaatikas Illinoisi ülikoolis. 1945. aastal alustas Hamming tööd Manhattani projektiga. 1946. aastal liitus ta ettevõttega Bell Telephone Laboratories, kus töötas koos Shannoniga. 1976. aastal sai ta õppetooli mereväe aspirantuuris Californias Montereys. Teos, mis tegi ta kuulsaks, Hammingu fundamentaalne uurimus vigade tuvastamise ja paranduskoodide kohta, avaldati 1950. aastal. 1956. aastal osales ta IBM 650 kallal töötades. Tema töö pani aluse programmeerimiskeelele, mis hiljem arenes välja kõrgetasemeliseks tasemel programmeerimiskeeled. Tunnustades Hammingu panust arvutiteaduse valdkonda, asutas IEEE tema nimelise arvutiteaduse ja süsteemiteooria silmapaistva teenistuse medali. Hamming oli esimene, kes pakkus välja "veaparanduskoodid" (ECC).
Nende koodide kaasaegseid modifikatsioone kasutatakse kõigis andmesalvestussüsteemides ning protsessori ja RAM-i vaheliseks teabevahetuseks. Üks nende variantidest, Reed-Solomoni koodid, on kasutusel CD-del, võimaldades salvestusi taasesitada ilma kriimustuste ja tolmuosakeste tekitatud kriuksumise ja mürata. Hammingil põhinevatest koodidest on palju versioone, need erinevad kodeerimisalgoritmide ja kontrollbittide arvu poolest. Sellised koodid omandasid erilise tähenduse seoses süvakosmose side arendamisega planeetidevaheliste jaamadega.
Viimastest ECC koodidest tuleks mainida LDPC (Low-Density Parity-check Code) koode. Tegelikult on neid tuntud juba kolmkümmend aastat, kuid eriline huvi nende vastu avastati just viimastel aastatel, mil hakkas arenema kõrglahutusega televisioon. LDPC koodid ei ole 100% usaldusväärsed, kuid veamäära saab reguleerida soovitud tasemele, kasutades kanali ribalaiust maksimaalselt ära. "Turbo koodid" on neile lähedal, need on tõhusad sügavas ruumis asuvate ja piiratud kanali ribalaiusega objektidega töötamisel.
Lisaks on V. A. Kotelnikovi nimi kindlalt kodeerimise teooria ajalukku sisse kirjutatud. 1933. aastal avaldas ta "Raadioside materjalid side tehnilise rekonstrueerimise esimesele üleliidulisele kongressile" teose "Eetri" ja "Traadi läbilaskevõimest". Kotelnikovi nimi sisaldub kodeerimise teooria ühe olulisema teoreemi nimetuses, mis määrab tingimused, mille korral saab edastatud signaali taastada ilma teabe kadumiseta. Seda teoreemi on kutsutud erinevalt, sealhulgas "WKS-i teoreemiks" (lühend WKS on võetud sõnadest Whittaker, Kotelnikov, Shannon). Mõnes allikas kasutatakse nii Nyquisti-Shannoni valimiteoreemi kui ka Whittakeri-Shannoni valimiteoreemi ning kodumaistes ülikooliõpikutes leidub kõige sagedamini lihtsalt “Kotelnikovi teoreemi”. Tegelikult on teoreemil pikem ajalugu. Selle esimese osa tõestas 1897. aastal prantsuse matemaatik E. Borel. E. Whittaker andis oma panuse 1915. aastal. 1920. aastal avaldas jaapanlane K. Ogura parandused Whittakeri uurimistöösse ja 1928. aastal täpsustas ameeriklane Harry Nyquist analoogsignaali digiteerimise ja rekonstrueerimise põhimõtteid.
Hammingi töö oli 1954. aastal alanud kodeerimise ajaloo uute ideede ahelreaktsiooni katalüsaator. Ameerika teadlane I. S. Reed oli esimene, kes kasutas Reed-Mülleri koodide enamusdekodeerimist. Enamusdekodeerimisel moodustatakse iga teabesümboli jaoks paaritu arv hinnanguid vastuvõetud koodi teatud sümbolikombinatsioonide mooduli 2 lisamisega. Otsus saadud sümboli tegeliku väärtuse kohta tehakse enamuse põhimõttel - kui suurem arv hinnanguid on 1, siis tehakse selline otsus. 1963. aastal kehtestas J. L. Messi selliste koodide koostamise ja dekodeerimise üldpõhimõtted. Enamiku dekodeeritavate koodide eeliseks on dekodeerimisalgoritmide äärmine lihtsus ja kiirus. Kuid selliste koodide klass on väga väike ja need koodid on teistest nõrgemad. Olulise panuse enamusdekodeeritavate koodide konstrueerimise teooria loomisesse andsid 1965. aastal Nõukogude teadlased V. D. Kolesnikov ja E. T. Mironchikov.
Väga huvitava plokkkoodide klassi pakkus 1954. aastal välja Ameerika teadlane G. Forney. Kaskaadkoodid moodustatakse järgmiselt: puhvermällu kirjutatakse n1 veeru ja n2 reaga tabeli kujul infosümbolite jada pikkusega n = n1 * n2. Üksikute ridade ja veergude sümbolid kodeeritakse paranduskoodide abil (vastavalt sisemine ja välimine) ning täiendavad kontrollsümbolid koos teabega edastatakse sidekanali kaudu. Väga märkimisväärseid tulemusi konkateneeritud koodide uurimisel said G. Forni ning nõukogude teadlased E. L. Bloch ja V. V. Zyablov. Viimaste (1976 ja 1982) uuringud näitasid, et sisemise ja välimise koodi sobiva valiku korral võimaldavad konkateneeritud koodid lahendada ülaltoodud veaparandusliku kodeerimise probleeme.
1955. aastal pakuti USA-s ja NSV Liidus välja väga oluline konvolutsiooniliste ehk korduvate koodide klass, mis on leidnud laialdast rakendust kaasaegses sidetehnoloogias. Selliste koodide koostamise ja arvutuslikult tõhusate algoritmide väljatöötamisega nende dekodeerimiseks kulus ligi paarkümmend aastat. Selles koodide klassis on sümbolite infojada jagatud m sümbolit sisaldavateks plokkideks, mis suunatakse K-sarnaste plokkide mäluga lineaarmuundurisse. Selles muunduris teisendatakse iga m vastuvõetud sümboli plokk, võttes arvesse mälus sisalduvaid K-plokke (K on koodilimiidi pikkus), n (n> m) sümboliks, mis edastatakse sidekanali kaudu. Sel juhul on teabe edastamise suhteline kiirus R = m/p. Konvolutsioonikoodid on plokk-lineaarsete koodide erijuhtum. Kuid konvolutsioonilise struktuuri kasutuselevõtt annab neile koodidele mitmeid täiendavaid omadusi, mis hõlbustavad oluliselt selle dekodeerimist. Nendel koodidel on puu või võre struktuur. Puustruktuuri igale servale vastab teatud m infosümbolite jada. Iga serva vastuvõetud sümbolite jada järgi saab leida selle kaalu - arvu, mis iseloomustab selle kaugust vastuvõetud jadast. Selle kauguse mõõtmiseks saab kasutada Hammingi mõõdikut, kui demodulaatoris tehakse raske otsus, või eukleidilist mõõdikut, kui dekodeerimine toimub maksimaalse tõenäosuse meetodil. Konvolutsioonikoodide dekodeerimine seisneb selles, et mööda koodivõret jälgitakse teekonda, mille jaoks kaugus vastuvõetud märgijadast on minimaalse väärtusega. Koodi konvolutsiooniline struktuur võimaldab kasutada korduvaid algoritme, mis lihtsustavad oluliselt selle kauguse arvutamist.
Nende koodide dekodeerimiseks pakkus Ameerika teadlane J. Wozencraft 1957. aastal välja elegantse järjestikuse dekodeerimise algoritmi, mille järgi dekooder ei vaata kõiki võimalikke teid mööda konvolutsioonikoodi koodivõre servi, vaid kõige tõenäolisemaid. Kui dekooder on mõnes etapis valinud vale tee, siis avastab ta peagi, et järgnevate servade valikutega suureneb kaugus valitud tee ja vastuvõetud jada vahel kiiresti. See on signaal, et dekooder astuks paar sammu tagasi ja alustaks alternatiivsete, usutavamate teede uurimist. Järjestikusel dekodeerimisel on arvutuste arv serva kohta juhuslik suurus ja kõigi uuritud harude arvutatud kaugused tuleb salvestada dekoodri mällu. Esimesed järjestikuse dekodeerimisalgoritmi uuringud viisid läbi J. Wozencraft ja B. Reiffen. 1963. aastal täiustas seda R. M. Fano, 1966. aastal pakkus nõukogude teadlane K. Sh. Zigangirov välja selle algoritmi tõhusa modifikatsiooni ja mõnevõrra hiljem (1969) tegi sarnase ettepaneku ka Ameerika teadlane F. Jelinek.
Märkimisväärne saavutus kodeerimise teooria vallas oli 1967. aastal ühe suurima Ameerika teadlase A. Viterbi poolt välja töötatud arvutuslikult väga tõhus algoritm konvolutsioonikoodide dekodeerimiseks maksimaalse tõenäosusega. See algoritm uurib erinevalt järjestikuse dekodeerimise algoritmist kõike võimalikud viisidüle koodivõre koodipiirangu k pikkusel, seega on see rakendatav suhteliselt väikeste väärtustega K = 1-10 konvolutsioonikoodide dekodeerimiseks.
Viterbi ja järjestikuse dekodeerimise konvolutsioonikoodid ja algoritmid on praegu magistraalraadio- ja satelliitsidesüsteemides väga levinud.
Ameerika teadlane D. Slepyan, kes sai märkimisväärseid tulemusi kommunikatsiooniteooria erinevates valdkondades, oli esimene, kes 1956. aastal pani range aluse pariteedikontrolliga lineaarsete plokkkoodide teooriale – rühmade matemaatilisele teooriale.
1957. aastal võttis teine ​​ameeriklane E. Prange esimesena kasutusele tsüklilise koodi mõiste ja tõi välja selle seose algebra ideaalidega. Tsüklilised koodid on oluline lineaarsete koodide alamklass, millel on tõhusad kodeerimis- ja dekodeerimisalgoritmid, mis põhinevad Galois' algebralise väljateooria ideede rakendamisel. Olulise panuse nende koodide teooria väljatöötamisse andsid Ameerika teadlased Peterson, Berlekamp ja Kasami.
Bose, Roy-Chowdhury (USA, 1960) ja Hockwinghami (Prantsusmaa, 1959) väga oluline ja ulatuslik lineaarsete tsükliliste koodide klass, mida nimetatakse BCH-koodideks nende iseseisvalt avastanud teadlaste nimede esitähtede järgi, võimaldas seda teha. mitmete vigade parandamiseks aktsepteeritud koodisõnas . Nendel koodidel olid järgmised parameetrid: n = 2m - 1, k > 2m - 1 - mt, d > 2t + 1 Hammingi kaugus koodikombinatsioonide vahel). BCH-koodid dekodeeritakse teatud algebraliste võrrandite lahenduste põhjal.
jne.................

Kursus: Infoteooria ja kodeerimine

Teema: Kodeerimine

2. Koodide klassifikatsioon

Bibliograafia

1. Kodeerimine. Põhimõisted ja määratlused

Mõelge teabe kodeerimisega seotud põhikontseptsioonidele. Sidekanalisse edastamiseks teisendatakse sõnumid signaalideks. Sümbolid, millega sõnumeid luuakse, moodustavad esmase tähestiku, kusjuures iga sümbolit iseloomustab selle esinemise tõenäosus sõnumis. Iga teade vastab unikaalselt signaalile, mis esindab teatud elementaarsete diskreetsete sümbolite jada, mida nimetatakse koodikombinatsioonideks. Kodeerimine on teadete muutmine signaaliks, s.o. sõnumite teisendamine koodikombinatsioonideks. Kood - sõnumielementide ja koodikombinatsioonide vahelise vastavuse süsteem. kodeerija - seade, mis teostab kodeerimist. Dekooder - seade, mis sooritab pöördoperatsiooni, s.o. koodsõna teisendamine sõnumiks. Tähestik - võimalike koodielementide kogum, s.o. elementaarsed sümbolid (koodisümbolid) X = (xi), kus i = 1, 2,..., m. Koodielementide arv - m helistas talle alus . Binaarkoodi jaoks xi = (0, 1) ja m = 2. Nimetatakse antud tähestiku piiratud tähemärkide jada koodide kombinatsioon (koodsõna). Koodikombinatsiooni elementide arv - n helistas tähtsus (kombinatsiooni pikkus). Erinevate koodikombinatsioonide arv ( N=mn) kutsutakse maht või koodi võimsus.

Kui a N0 on siis lähtesõnumite arv N³N0. Koodi olekute komplekt peab katma objekti olekute komplekti. Täielik vormiriietus n- numbriline kood koos alusega m sisaldab N=mn koodikombinatsioonid. Sellist koodi nimetatakse primitiivne.

2. Koodide klassifikatsioon

Koode saab klassifitseerida erinevate kriteeriumide alusel:

1. Aluse järgi (tähemärkide arv tähestikus): binaarne (binaarne m=2) ja mitte binaarne (m ¹ 2).

2. Koodikombinatsioonide (sõnade) pikkuse järgi:

ühtlane - kui kõik koodikombinatsioonid on sama pikkusega;

ebaühtlane - kui koodikombinatsiooni pikkus ei ole konstantne.

3. Vastavalt edastusmeetodile:

järjestikused ja paralleelne;

plokk - andmed paigutatakse esmalt puhvrisse ja seejärel kantakse kanalisse ja binaarsesse pidev .

4. Mürakindluse järgi:

lihtne (primitiivne, täielik) - teabe edastamiseks kasutatakse kõiki võimalikke koodikombinatsioone (ilma liiasuseta);

korrigeeriv (mürakindel) - mitte kõiki, vaid ainult osa (lubatud) koodikombinatsioone kasutatakse sõnumite edastamiseks.

5. Sõltuvalt eesmärgist ja rakendusest saab tinglikult eristada järgmisi kooditüüpe:

Sisemised koodid - see on seadmetes kasutatavad koodid. Need on masinkoodid, samuti koodid, mis põhinevad positsiooniliste arvusüsteemide kasutamisel (kahe-, kümnend-, kahend-, kümnend-, kaheksand-, kuueteistkümnend- jne). Levinuim kood arvutis on kahendkood, mille abil on lihtne rakendada riistvaraseadmeid kahendkoodis andmete salvestamiseks, töötlemiseks ja edastamiseks. See tagab seadme kõrge töökindluse ja kahendkoodis andmetega töötamise lihtsuse. Binaarandmed, mis on kombineeritud 4-liikmelistes rühmades, moodustavad kuueteistkümnendkoodi, mis on hästi kooskõlas arvuti arhitektuuriga, töötades andmetega baitide kordades (8 bitti).

Sidekoodid ja nende edastamine sidekanalite kaudu . ASCII-kood (American Standard Code for Information Interchange) on personaalarvutites laialt levinud. ASCII on 7-bitine kood tähtnumbriliste ja muude märkide jaoks. Kuna arvutid töötavad baitidega, kasutatakse 8. bitti sünkroonimiseks ehk paarsus ehk koodi laiendamiseks. IBMi arvutid kasutavad teabevahetuseks laiendatud kahendkoodi EBCDIC (Extended Binary Coded Decimal Interchange Code).

Sidekanalites kasutatakse laialdaselt teletaibikoodi CCITT (International Consultative Committee on Telephony and Telegraphy) ja selle modifikatsioone (MTK jne).

Teabe kodeerimisel sidekanalite kaudu edastamiseks, sealhulgas riistvarateedel, kasutatakse koode, mis tagavad maksimaalse teabeedastuskiiruse selle tihendamise ja liiasuse kõrvaldamise tõttu (näiteks: Huffmani ja Shannon-Fano koodid), ja koode, mis tagavad andmeedastuse usaldusväärsus, lisades edastatavatesse sõnumitesse liiasuse (näiteks: rühmakoodid, Hamming, tsüklilised ja nende variandid).

Spetsiaalsete rakenduste koodid on koodid, mis on loodud andmeedastuse ja -töötluse eriprobleemide lahendamiseks. Selliste koodide näide on tsükliline halli kood, mida kasutatakse laialdaselt nurk- ja lineaarsetes ADC-des. Fibonacci koode kasutatakse kiirete ja mürakindlate ADCde ehitamiseks.

Põhitähelepanu on kursusel pööratud andmevahetuse koodidele ja nende edastamisele sidekanalite kaudu.

KODISEERIMISE EESMÄRGID:

1) Andmeedastuse efektiivsuse tõstmine maksimaalse andmeedastuskiiruse saavutamise kaudu.

2) Mürakindluse parandamine andmeedastuse ajal.

Nende eesmärkide kohaselt areneb kodeerimise teooria kahes peamises suunas:

1. Säästliku (efektiivse, optimaalse) kodeerimise teooria tegeleb koodide otsimisega, mis võimaldavad tõsta häireteta infoedastuse efektiivsust kanalites, välistades allikate liiasuse ja andmeedastuskiiruse parima sobitamise sidekanali ribalaiusega.

2. Veaparandusliku kodeerimise teooria tegeleb häiretega kanalites infoedastuse usaldusväärsust suurendavate koodide otsimisega.

3. Koodide esitamise viisid

Olenevalt kasutatavatest kodeerimismeetoditest kasutatakse erinevaid koodide matemaatilisi mudeleid, kusjuures kõige sagedamini kasutatav koodide esitus on kujul: koodmaatriksid; koodipuud; polünoomid; geomeetrilised kujundid jne.

3.1 Koodide maatriksesitus

Kasutatakse vormi tähistamiseks n- numbrilised koodid. Primitiivse (täieliku ja ühtse) koodi puhul sisaldab maatriks n- veerud ja 2n- read, st. kood kasutab kõiki kombinatsioone. Müraimmuunsuse jaoks (vigade parandamine, tuvastamine ja parandamine) sisaldab maatriks n- veerud ( n = k+m, kus k- teabe arv ja m- kontrollnumbrite arv) ja 2k- read (kus 2k- lubatud koodikombinatsioonide arv). Kell suured väärtused n ja k maatriks on liiga tülikas ja kood on kirjutatud lühendatud kujul. Koodide maatriksesitus on kasutusel näiteks lineaarsetes grupikoodides, Hammingi koodides jne.

3.2 Koodide esitamine koodipuudena

koodipuu on ühendatud graafik, mis ei sisalda tsükleid. Ühendatud graafik - graafik, milles mis tahes tipupaari jaoks on neid tippe ühendav tee. Graaf koosneb sõlmedest (tippudest) ja servadest (harudest), mis ühendavad erinevatel tasanditel paiknevaid sõlmi. Ühtse kahendkoodiga puu ehitamiseks valitakse tipp, mida nimetatakse puu juureks (allikaks) ja tõmmatakse sellest servad kahele järgmisele tipule jne.

Täieliku koodi koodipuu näide on näidatud joonisel 1.

111 110 101 100 011 010 001 000

Joonis 1. Täieliku binaarkoodi puu aadressil n = 3

Veaparanduskoodipuu ehitatakse üles täiskoodipuu põhjal, kustutades keelatud koodikombinatsioonid. Ebaühtlase koodipuu jaoks kasutatakse kaalutud graafikut ja ülemineku tõenäosused on näidatud puu servadel. Koodi esitust koodipuu kujul kasutatakse näiteks Huffmani koodides.

3.3 Koodide esitamine polünoomidena

Koodide esitamine polünoomide kujul põhineb binaarruumi sarnasusel (isomorfismil) n- maksimaalselt astmepolünoomide jadad ja ruumid n - 1.

Kood mis tahes numbrisüsteemi jaoks, millel on alus X võib esitada järgmiselt:

G(x) = an-1 xn-1+ an-2 xn-2+... +a1x+a0 =,

kus ai - etteantud arvusüsteemi numbrid (kahendarvudes 0 ja 1);

X- sümboolne (fiktiivne) muutuja, mille eksponent vastab kahendarvu numbrite arvudele;

Näiteks: koodikombinatsiooni 1010110 saab esitada järgmiselt:

G(x)=1×x6+0×x5+1×x4+0×x3+1×x2+1×x1+0×x0 =x6+x4+x2+x=10101

Veelgi enam, toimingud koodidega on samaväärsed polünoomide toimingutega. Koodide esitamist polünoomide kujul kasutatakse näiteks tsüklilistes koodides.

3.4 Koodide geomeetriline esitus

Mis tahes kombinatsioon n- biti binaarkoodi saab esitada tipuna n- mõõtühiku kuup, s.o. kuubik serva pikkusega 1. Kaheelemendilise koodi jaoks ( n = 2) koodikombinatsioonid asuvad ruudu tippudes. Kolme elemendi koodi jaoks

(n = 3) - ühikkuubi tippudes (joon. 2).

Üldiselt n mõõtekuubikul on 2n tipud, mis vastab koodikombinatsioonide komplektile 2n.

n = 2 n = 3

Joonis 2. Binaarkoodi geomeetriline mudel

Koodikauguse geomeetriline tõlgendamine. Koodi kaugus – minimaalne servade arv, mis tuleb läbida, et ühest koodikombinatsioonist teise jõuda. Koodi kaugus iseloomustab koodi mürakindlust.

Bibliograafia

1. Klovsky D.D. Signaali edastamise teooria. -M.: Side, 1984.

2. Kudrjašov B.D. Infoteooria. Õpik ülikoolidele Kirjastus PETER, 2008. - 320lk.

3. Ryabko B.Ya., Fionov A.N. Tõhus meetod suure tähestikuga allikate adaptiivne aritmeetiline kodeerimine // Infoedastuse probleemid. - 1999. - T.35, väljaanne. - Lk.95 - 108.

4. Semenjuk V.V. Diskreetse teabe ökonoomne kodeerimine. - Peterburi: SPbGITMO (TU), 2001

5. Dmitriev V.I. Rakendusinfo teooria. Moskva: Kõrgkool, 1989.

6. Nefedov V.N., Osipova V.A. Diskreetse matemaatika kursus. M.: MAI, 1992.

7. Kolesnik V.D., Poltyrev G.Sh. Infoteooria kursus. M.: Nauka, 2006.

Kodeerimine ja dekodeerimine Inimene kasutab teiste inimestega teabe vahetamiseks loomulikke keeli. Koos loomulike keeltega on välja töötatud ka ametlikud keeled nende professionaalseks kasutamiseks mis tahes valdkonnas. Teabe esitamist keelt kasutades nimetatakse sageli kodeerimiseks. Kood on sümbolite kogum (tavasümbolid) teabe esitamiseks. Kood on kokkuleppeliste märkide (sümbolite) süsteem teabe (sõnumi) edastamiseks, töötlemiseks ja säilitamiseks. Kodeerimine on teabe (sõnumite) koodi kujul esitamise protsess. Kogu kodeerimiseks kasutatavat märkide komplekti nimetatakse kodeeringu tähestikuks. Näiteks arvuti mällu kodeeritakse igasugune teave kahendtähestiku abil, mis sisaldab ainult kahte märki: 0 ja 1.

Teabe kodeerimise viisid Sama teabe kodeerimiseks saab kasutada erinevaid viise; nende valik sõltub mitmest asjaolust: kodeerimise eesmärgist, tingimustest, olemasolevatest vahenditest. Kui teil on vaja teksti kõnetempoga üles kirjutada, kasutame kiirkirja; kui teil on vaja saata tekst välismaale, kasutage inglise tähestikku; kui on vaja teksti esitada kirjaoskajale vene inimesele arusaadavas vormis, siis kirjutame selle üles vastavalt vene keele grammatika reeglitele. "Tere pärastlõunal, Dima!" "Dobryi den, Dima"

Teabe kodeerimise viisid Teabe kodeerimise valik võib olla seotud selle töötlemise kavandatud viisiga. Näitame seda kvantitatiivse teabe arvude esitamise näitel. Vene tähestikku kasutades saate kirjutada numbri "nelikümmend seitse".Kasutades araabia kümnendarvusüsteemi tähestikku, kirjutame "47".Teine meetod pole mitte ainult lühem kui esimene, vaid ka mugavam arvutuste tegemiseks Milline kirje on arvutuste tegemiseks mugavam: "korruta nelikümmend seitse saja kakskümmend viis" või "47x 125"? Ilmselgelt teine.

Sõnumi krüpteerimine Mõnel juhul on vaja sõnumi või dokumendi tekst krüpteerida, et need, kes seda ei peaks tegema, ei saaks seda lugeda. Seda nimetatakse võltsimiskaitseks. Sel juhul salatekst krüpteeritakse. Iidsetel aegadel nimetati krüpteerimist krüptograafiaks. Krüpteerimine on lihtteksti krüptitud tekstiks teisendamine ja dekrüpteerimine on pöördteisendusprotsess, mille käigus algtekst taastatakse. Krüpteerimine on samuti kodeerimine, kuid ainult allikale ja adressaadile teadaoleva salameetodiga. Krüpteerimine on teadus, mida nimetatakse krüptograafiaks.

Chappe optiline telegraaf 1792. aastal lõi Prantsusmaal Claude Chappe süsteemi visuaalse teabe edastamiseks, mida nimetati optiliseks telegraafiks. Lihtsamal kujul oli see tüüpiliste hoonete kett, mille katusel paiknesid teisaldatavate risttaladega postid, mis loodi üksteisest nähtavale kohale. Liigutatavate semaforristtaladega poste juhtisid kaablite abil spetsiaalsed operaatorid hoonete seest. Schapp lõi spetsiaalse kooditabeli, kus iga tähestiku täht vastas Semafori moodustatud kindlale figuurile, olenevalt põikvardade asendist tugiposti suhtes. Chappe süsteem võimaldas sõnumeid edastada kiirusega kaks sõna minutis ja levis kiiresti üle Euroopa. Rootsis töötas optiliste telegraafijaamade kett kuni 1880. aastani.

Esimene telegraaf Esimene tehniline vahend teabe edastamiseks kaugelt oli telegraaf, mille leiutas 1837. aastal ameeriklane Samuel Morse. Telegraafiteade on elektriliste signaalide jada, mis edastatakse ühest telegraafiseadmest juhtmete kaudu teisele telegraafiseadmele. Leiutaja Samuel Morse leiutas hämmastava koodi (Morse kood, Morse kood, "Morse kood"), mis on inimkonda teeninud tänapäevani. Teave on kodeeritud kolme "tähega": pikk signaal (kriips), lühike signaal (punkt) ja signaal puudub (paus) tähtede eraldamiseks. Seega on kodeerimine taandatud rangelt määratletud järjekorras paigutatud märkide komplekti kasutamisele. Tuntuim telegraafiteade on SOS (Save Our Souls) hädasignaal. See näeb välja selline: "---"

Morsekood 4. punkt koma 5/6 ? 7!

Esimene juhtmeta telegraaf (raadiovastuvõtja) 7. mai 1895 vene keel teadlane Aleksander Stepanovitš Popov demonstreeris Venemaa füüsikalis-keemiaühingu koosolekul seadet, mida ta nimetas "välgudetektoriks", mis oli mõeldud elektromagnetlainete registreerimiseks. Seda seadet peetakse maailma esimeseks juhtmeta telegraafiseadmeks, raadiovastuvõtjaks. 1897. aastal teostas Popov traadita telegraafiseadmete abil teadete vastuvõtmist ja edastamist ranniku ja sõjaväelaeva vahel. 1899. aastal konstrueeris Popov elektromagnetlainete vastuvõtja moderniseeritud versiooni, kus signaale võeti vastu (morsekoodis) operaatori kõrvaklappides. 1900. aastal viidi tänu Popovi juhtimisel Hoglandi saarele ja Kotkasse Vene mereväebaasi ehitatud raadiojaamadele edukalt päästeoperatsioone läbi saare lähedal madalikule sõitnud sõjalaeva Kindral-Admiral Apraksin pardal. Gogland. Traadita telegraafi teel edastatud sõnumite vahetamise tulemusena sai Venemaa jäämurdja Yermak meeskond õigeaegselt ja täpselt informatsiooni Soome kalurite kohta maharebitud jääl.

Baudot telegraafimasin Ühtse telegraafi koodi mõtles välja prantslane Jean Maurice Baudot 19. sajandi lõpus. See kasutas ainult kahte erinevad tüübid signaalid. Pole tähtis, kuidas te neid nimetate: punkt ja kriips, pluss ja miinus, null ja üks. Need on kaks erinevat elektrilist signaali. Kõikide märkide koodi pikkus on sama ja võrdne viiega. Sel juhul pole tähtede üksteisest eraldamise probleemi: iga viis signaali on tekstimärk. Seetõttu pole passi vaja. Koodi nimetatakse ühtlaseks, kui koodi kõigi märkide pikkus on võrdne. Baudot kood on esimene meetod tehnoloogia ajaloos binaarne kodeering, teave. Tänu sellele ideele oli võimalik luua otsetrükkimise telegraafiaparaat, mis näeb välja nagu kirjutusmasin. Teatud tähega klahvi vajutamisel genereeritakse vastav viieimpulsiline signaal, mis edastatakse sideliini kaudu. Boodiüksus on saanud nime Bodo järgi. Kaasaegsed arvutid kasutavad teksti kodeerimiseks ka ühtset kahendkoodi.

Binaarne kodeerimine arvutis Kogu teave, mida arvuti töötleb, peab olema esindatud binaarne kood kasutades kahte numbrit: 0 ja 1. Neid kahte märki nimetatakse kahendnumbriteks või bittideks. Kahe numbri 0 ja 1 abil saab kodeerida mis tahes teate. See oli põhjus, miks arvutit tuleb korraldada kaks oluline protsess: kodeerimine ja dekodeerimine. Kodeerimine on sisendinfo muutmine arvuti poolt tajutavale vormile, s.t. binaarne kood.

Miks binaarne kodeerimine Tehnilisest vaatenurgast osutus kahendarvusüsteemi kasutamine teabe kodeerimiseks palju lihtsamaks kui muude meetodite kasutamine. Tõepoolest, on mugav kodeerida teavet nullide ja ühtede jadana, kui need väärtused on esitatud kahe võimaliku elektroonilise elemendi stabiilse olekuna: 0 - elektrilist signaali pole; 1 - elektrilise signaali olemasolu. Teabe kodeerimise ja dekodeerimise viisid arvutis sõltuvad ennekõike teabe tüübist, nimelt sellest, mida tuleks kodeerida: numbreid, teksti, graafikat või heli.

Arvusüsteemide tüübid ARVUSSÜSTEEMID POSITIONALMITTE-POSITIONAL Mittepositsioonilistes numbrisüsteemides ei sõltu numbriga tähistatav väärtus numbri asukohast. XXI Positsioonilistes arvusüsteemides oleneb numbriga tähistatud väärtus numbrikirjes selle asukohast arvus (positsioonis). 2011. aastal

Mittepositsioonilised numbrisüsteemid Praktiliselt mittepositsioonilise numbrisüsteemi kanooniline näide on rooma keel, mis kasutab numbritena ladina tähti: I tähistab 1, V - 5, X - 10, L - 50, C - 100, D - 500 , M Täisarvud kirjutatakse neid numbreid korrates. Näiteks II = = 2, siin tähistab sümbol I 1 olenemata arvu kohast. Suurte arvude õigeks kirjutamiseks rooma numbritega peate esmalt üles kirjutama tuhandete, seejärel sadade, seejärel kümnete ja lõpuks ühed. Näide: arv Kaks tuhat MM, üheksasada CM, kaheksakümmend LXXX, kaheksa VIII. Kirjutame need koos: MCMLXXXVIII. MMCMLXXXVIII = ()+() = 2988 Arvude kuvamiseks mittepositsioonilises numbrisüsteemis ei saa piirduda piiratud arvude hulgaga. Lisaks on aritmeetiliste toimingute sooritamine neis äärmiselt ebamugav.

Vana-Egiptuse mittepositsiooniline kümnendarvusüsteem. Umbes kolmandal aastatuhandel eKr mõtlesid iidsed egiptlased välja oma numbrisüsteemi, milles määrasid võtmenumbrid 1, 10, 100 jne. kasutati hieroglüüfe. Kõik ülejäänud arvud koostati nendest võtmenumbritest, kasutades liitmistoimingut. Vana-Egiptuse arvusüsteem on kümnendsüsteem, kuid mittepositsiooniline.

Tähestikulised numbrisüsteemid. Täiustatud mittepositsioonilised numbrisüsteemid olid tähestikusüsteemid. Nende numbrisüsteemide hulka kuulusid kreeka, slaavi, foiniikia jt. Nendes tähistati numbreid 1 kuni 9, täisarvu kümneid (10 kuni 90) ja täisarve sadu (100 kuni 900) tähestiku tähtedega. Tähestikulises numbrisüsteemis Vana-Kreeka numbreid 1, 2,..., 9 tähistati kreeka tähestiku esimese üheksa tähega, näiteks a = 1, b = 2, g = 3 jne. Järgmisi 9 tähte kasutati numbrite 10, 20, ..., 90 (i = 10, k = 20, l = 30, m = 40 jne) tähistamiseks ning numbrite 100, 200, . .. , 900 viimast 9 tähte (r = 100, s = 200, t = 300 jne). Näiteks numbrit 141 tähistas rma. Slaavi rahvaste seas kehtestati tähtede arvväärtused slaavi tähestiku järjekorras, mis kasutas esmalt glagoliiti ja seejärel kirillitsa tähestikku. Rohkem infot vene kirjakeele tekke ja arengu kohta leiab kodulehelt

Positsioonilised arvusüsteemid Positsioonilistes numbrisüsteemides oleneb numbriga tähistatud väärtus numbrikirjes selle asukohast arvus (positsioonis). Kasutatud numbrite arvu nimetatakse numbrisüsteemi baasiks. Näiteks 11 on üksteist, mitte kaks: = 2 (võrdle Rooma numbrisüsteemiga). Siin on tähemärgil 1 erinev tähendus olenevalt numbri asukohast.

Esimesed positsioonilised numbrisüsteemid Kõige esimene selline süsteem, kui sõrmi täitsid loendamisseadme, oli viiekordne. Mõned Filipiinide saarte hõimud kasutavad seda tänapäevalgi ja tsiviliseeritud riikides on selle reliikvia ekspertide hinnangul säilinud vaid kooli viiepallise hindamisskaala kujul.

Kaksteistkümnendsüsteem Kaksteistkümnendsüsteem tekkis järgmisena pärast kvinaararvude süsteemi. See sai alguse iidsest Sumerist. Mõned teadlased usuvad, et selline süsteem tekkis pöidlaga käe falange loendamisest. Kaksteistkümnendsüsteemi arvusüsteem sai laialt levinud 19. sajandil. Selle laialdast kasutamist minevikus näitavad selgelt paljudes keeltes esinevad numbrinimetused, aga ka mitmes riigis säilinud aja, raha ja teatud mõõtühikute vahekordade arvestamise viisid. Aasta koosneb 12 kuust ja pool päeva 12 tunnist. Tänapäeva kaksteistkümnendsüsteemi elementi võib loendada kümnete kaupa. Arvu 12 kolmel esimesel astmel on oma nimed: 1 tosin = 12 tükki; 1 bruto = 12 tosinat = 144 tükki; 1 mass = 12 bruto = 144 kümneid = 1728 tükki. Inglise nael jaguneb 12 šillingiks.

Seksagesimaalne numbrite süsteem see kasutas kuuskümmend numbrit! Hilisematel aegadel kasutasid seda araablased, aga ka iidsed ja keskaegsed astronoomid. Seksagesimaalne arvusüsteem on teadlaste sõnul eelmainitud viie- ja kaksteistkümnendsüsteemi süntees.

Millised asukohanumbrite süsteemid on praegu kasutusel? Praegu on levinumad kümnend-, kahend-, kaheksand- ja kuueteistkümnendsüsteemid. Binaarset, kaheksandsüsteemi (nüüd asendatakse kuueteistkümnendsüsteemiga) ja kuueteistkümnendsüsteemi kasutatakse sageli digitaalseadmete, programmeerimise ja arvuti üldise dokumentatsiooniga seotud valdkondades. Kaasaegsed arvutisüsteemid töötavad digitaalsel kujul esitatud teabega.

Kümnendarvusüsteem Kümnendarvusüsteem on positsiooniline arvusüsteem, mis põhineb baasil 10. Eeldatakse, et alus 10 on seotud inimese sõrmede arvuga. Kõige levinum numbrisüsteem maailmas. Numbrite kirjutamiseks kasutatakse märke 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, mida nimetatakse araabia numbriteks.

Kahendarvusüsteem Binaarne arvusüsteem on positsiooniline arvusüsteem, mille alus on 2. Kasutatakse numbreid 0 ja 1. Digitaalseadmetes kasutatakse kahendsüsteemi, kuna see on kõige lihtsam ja vastab nõuetele: Mida vähem on süsteemis väärtusi , seda lihtsam on üksikute elementide valmistamine. Mida väiksem on elemendi olekute arv, seda suurem on mürakindlus ja seda kiiremini see töötab. Lihtne luua liit- ja korrutustabeleid arvude põhitoimingute jaoks

Kümnend-, kahend-, kaheksand- ja kuueteistkümnendarvusüsteemide tähestik NumbrisüsteemBaasnumbrite tähestik Kümnend100, 1, 2, 3, 4, 5, 6, 7, 8, 9 Kahend20, 1 oktaal80, 1, 2, 3, 6, 5, . , 7 Hex160, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F

Kümnend-, kahend-, kaheksand- ja kuueteistkümnendsüsteemi arvusüsteemide vastavus p= p= p= p= ABCDEF10 Kasutatud numbrite arvu nimetatakse arvusüsteemi baasiks. Töötades korraga mitme arvusüsteemiga, märgitakse nende eristamiseks tavaliselt süsteemi alus alamindeksina, mis kirjutatakse kümnendkohana: see on kümnendkohaga arv 123; sama arv, kuid kahendarvuna. Kahendarvu saab kirjutada järgmiselt: = 1* * * * * *2 0.

Arvude tõlkimine ühest arvusüsteemist teise Tõlkimine kümnendarvusüsteemist arvusüsteemi alusega p viiakse läbi kümnendarvu ja selle kümnendjagatiste järjestikuse jagamisel p-ga ning seejärel viimase jagatise ja jääkide vastupidises järjekorras väljakirjutamisega. . Tõlgime kümnendarvu kahendarvusüsteemideks (arvusüsteemi alus on p=2). Selle tulemusena saime =99 10

Arvud arvutis Arvuti numbrid salvestatakse ja töödeldakse kahendarvusüsteemis. Nullide ja ühtede jada nimetatakse kahendkoodiks. Spetsiifilised omadused käsitleme arvude esitusi arvutimälus teistes õppetundides teemal "numbrisüsteemid".

Tekstilise teabe kodeerimine Traditsioonilistes kodeeringutes kasutatakse ühe märgi kodeerimiseks 8 bitti. Valemist 2.3 on lihtne välja arvutada, et selline 8-bitine kood võimaldab kodeerida 256 erinevat märki. Konkreetse numbrikoodi määramine sümbolile on kokkuleppe küsimus. Koodeks on vastu võetud rahvusvahelise standardina. ASCII tabel(American Standard Code for Information Interchange), mis kodeerib märkide esimese poole numbrikoodidega 0 kuni 127 (koodid 0 kuni 32 ei ole määratud mitte tähemärkidele, vaid funktsiooniklahvidele) ja teine ​​pool sisaldab rahvuslikud tähestikud, pseudograafilised sümbolid ja mõned matemaatilised märgid. Kahjuks on praegu viis erinevat kirillitsa kodeeringut (KOI8-R, Windows.MS-DOS, Macintosh ja ISO), mis tekitab lisaraskusi venekeelsete dokumentidega töötamisel. Kronoloogiliselt oli üks esimesi standardeid vene tähtede kodeerimiseks arvutites KOI8 ("Informatsioonivahetuskood, 8-bitine"). Seda kodeeringut kasutati juba 70ndatel EC seeria arvutites ja alates 80ndate keskpaigast hakati seda kasutama UNIX operatsioonisüsteemi esimestes venestatud versioonides. Microsoft Windows, lühendatult CP1251 ("CP" tähendab "koodilehte", "koodilehte").CP1251

Tekstiinfo kodeerimine 90ndate algusest, MS DOS operatsioonisüsteemi domineerimise ajast, on jäänud CP866 kodeering. Mac OS-i operatsioonisüsteemi kasutavad Apple'i arvutid kasutavad oma Maci kodeeringut. Lisaks kiitis Rahvusvaheline Standardiorganisatsioon (International Standards Organisation, ISO) vene keele standardiks heaks veel ühe kodeeringu nimega ISO CP866MacISO. 90ndate lõpus võeti kasutusele uus kodeering. rahvusvaheline standard Unicode, mis eraldab ühele märgile mitte ühe baidi, vaid kaks ja seetõttu saab seda kasutada mitte 256, vaid erinevate märkide kodeerimiseks. Unicode'i standardi täielik spetsifikatsioon sisaldab kõiki olemasolevaid, väljasurnud ja kunstlikult loodud tähestikke maailmas, samuti palju matemaatilisi, muusikalisi, keemilisi ja muid sümboleid. Näide Väljendage sõna "arvuti" kuueteistkümnendkoodina kõigis viies kodeeringus. Kasutage CD-ROM-i CP866, Maci ja ISO koodilehtede hankimiseks ning arvutikalkulaatorit, et teisendada arvud kümnendsüsteemist kuueteistkümnendsüsteemi. Sõna "arvuti" kümnendkoodide jadad erinevates kodeeringus on koostatud kodeerimistabelite alusel: KOI8-R: CP1251: CP866: Mac: ISO: Tõlgime koodijada kümnendsüsteemist kuueteistkümnendsüsteemi kalkulaatori abil: KOI8 -R: FC F7 ED CP1251: DD C2 CC CP866: 9D 82 8C Mac: 9D 82 8C ISO: CD B2 BC tekstidokumendidühelt kodeeringult teisele kasutatakse spetsiaalseid konverteriprogramme. Üks selline programm on Hieroglyph tekstiredaktor, mis võimaldab tõlkida trükitud teksti ühest kodeeringust teise ja isegi kasutada ühes tekstis erinevaid kodeeringuid.

Info esitusviisi analoogne ja diskreetne vorm Inimene on võimeline tajuma ja salvestama informatsiooni kujutiste kujul (visuaalne, heliline, kombatav, maitsmis- ja lõhnataju). Visuaalseid pilte saab salvestada kujutiste kujul (joonised, fotod jne) ning helipilte saab salvestada plaatidele, magnetlintidele, laserplaatidele jne. Teavet, sealhulgas graafikat ja heli, saab esitada analoog- või diskreetsel kujul. Analoogesitlusega füüsiline kogus omandab lõpmatu arvu väärtusi ja selle väärtused muutuvad pidevalt. Diskreetse esituse korral omandab füüsiline suurus lõpliku väärtuste hulga ja selle väärtus muutub järsult.

Teabe esituse analoog- ja diskreetne vorm Toome näite teabe analoog- ja diskreetse esituse kohta. Keha asend kaldtasandil ja trepil määratakse X- ja Y-koordinaatide väärtustega. Kui keha liigub mööda kaldtasapinda, võivad selle koordinaadid omandada lõpmatu arvu pidevalt muutuvaid väärtusi. teatud vahemikust ja trepist üles liikudes ainult teatud väärtuste kogum ja järsult muutuv.

Diskretiseerimine Analoogesituse näide graafiline teave võib serveerida näiteks maalilõuendit, mille värvus muutub pidevalt, ja tindiprinteriga prinditud diskreetset kujutist, mis koosneb eri värvi üksikutest täppidest. Heliteabe analoogsalvestuse näiteks on vinüülplaat (heliriba muudab oma kuju pidevalt) ja diskreetne helikompaktplaat (mille heliriba sisaldab erineva peegelduvusega alasid). Graafilise ja heliteabe teisendamine analoogvormist diskreetsesse vormi toimub diskreetsuse teel, st pideva graafilise kujutise ja pideva (analoogse) helisignaali jagamisega eraldi elementideks. Diskretiseerimise käigus viiakse läbi kodeerimine, see tähendab igale elemendile konkreetse väärtuse määramine koodi kujul. Diskretiseerimine on pidevate kujutiste ja heli muutmine diskreetsete väärtuste kogumiks koodide kujul.

Bitmap piltide kodeerimine Bitmap pilt on erinevat värvi punktide (pikslite) kogum. Piksel - pildi minimaalne pindala, mille värvi saab määrata iseseisvalt. Kujutise kodeerimise käigus tehakse selle ruumiline diskreetimine. Kujutise ruumilist diskretiseerimist võib võrrelda mosaiigist pildi konstrueerimisega (suur hulk väikeseid mitmevärvilisi klaase). Pilt jagatakse eraldi väikesteks fragmentideks (punktideks) ja igale fragmendile määratakse selle värvi väärtus ehk värvikood (punane, roheline, sinine jne). Pildi kvaliteet sõltub punktide arvust (mida väiksem on punkti suurus ja vastavalt, mida suurem on nende arv, seda parem kvaliteet) ja kasutatud värvide arv (mida rohkem värve, seda paremini pilt on kodeeritud).

Värvimudelid Värvi esitamiseks numbrikoodina kasutatakse kahte värvimudelit, mis on üksteisega pöördvõrdelised: RGB või CMYK. RGB mudelit kasutatakse telerites, monitorides, projektorites, skannerites, digikaamerates... Selle mudeli põhivärvid on punane (punane), roheline (roheline), sinine (sinine). CMYK värvimudelit kasutatakse printimisel paberile printimiseks mõeldud kujutiste moodustamisel.

RGB värvimudel Värvilistel piltidel võib olla erinev värvisügavus, mille määrab punkti värvi kodeerimiseks kasutatavate bittide arv. Kui kodeerida pildil ühe punkti värvi kolme bitiga (üks bitt iga RGB värvi kohta), siis saame kõik kaheksa erinevat värvi.

True Color Praktikas eraldatakse RGB-mudelis värvipildi iga punkti värvi kohta teabe salvestamiseks tavaliselt 3 baiti (st 24 bitti) – 1 bait (st 8 bitti) iga komponendi värviväärtuse jaoks. Seega võib iga RGB komponendi väärtus olla vahemikus 0 kuni 255 (kokku 2 8 = 256 väärtust) ja pildi iga punkti saab sellise kodeerimissüsteemiga värvida ühes värvitoonis. Sellist värvikomplekti nimetatakse tavaliselt True Coloriks (tõelised värvid), kuna inimsilm ei suuda ikkagi suuremat mitmekesisust eristada.

Vektorkujutiste kodeerimine Vektorkujutis on graafiliste primitiivide (punkt, segment, ellips...) kogum. Iga primitiivi kirjeldatakse matemaatiliste valemitega. Kadesta kodeerimist rakenduskeskkonnast. Vektorgraafika eeliseks on see, et vektorgraafikat salvestavad failid on suhteliselt väikesed. Samuti on oluline, et vektorgraafikat saaks suurendada või vähendada ilma kvaliteeti kaotamata.

Graafilised failivormingud Bit MaP image (BMP) on universaalne bitmap graafilise failivorming, mida kasutatakse Windowsi operatsioonisüsteemis. Seda vormingut toetavad paljud graafikaredaktorid, sealhulgas redaktor Paint. Soovitatav andmete salvestamiseks ja jagamiseks teiste rakendustega. Tagged Image File Format (TIFF) on rasterkujutise failivorming, mida toetavad kõik suuremad graafikaredaktorid ja arvutiplatvormid. Sisaldab kadudeta pakkimisalgoritmi. Kasutatakse dokumentide vahetamiseks erinevate programmide vahel. Soovitatav kasutada avaldamissüsteemidega töötamisel. Graphics Interchange Format (GIF) on rastergraafika failivorming, mida toetavad erinevate operatsioonisüsteemide rakendused. Sisaldab kadudeta pakkimisalgoritmi, mis võimaldab teil faili suurust mitu korda vähendada. Soovitatav piiratud arvu värvidega (kuni 256) programmiliselt loodud piltide (diagrammid, graafikud ja nii edasi) ja jooniste (nt aplikatsioonid) salvestamiseks. Kasutatakse graafika paigutamiseks Interneti veebilehtedele. Kaasaskantava võrgugraafika (PNG) bitmap-graafikafailivorming, mis sarnaneb GIF-ile. Soovitatav graafika paigutamiseks Interneti veebilehtedele. Joint Photographic Expert Group (JPEG) on rastergraafika failivorming, mis rakendab skannitud fotode ja illustratsioonide jaoks tõhusat tihendusalgoritmi (JPEG meetod). Tihendusalgoritm võimaldab teil faili suurust kümneid kordi vähendada, kuid see viib mõne teabe pöördumatu kadumiseni. Toetavad erinevate operatsioonisüsteemide rakendused. Kasutatakse graafika paigutamiseks Interneti veebilehtedele.

Heli kodeerimine Arvuti kasutamine heli töötlemiseks algas hiljem kui numbrite, tekstide ja graafika jaoks. Heli on pidevalt muutuva amplituudi ja sagedusega laine. Mida suurem on amplituud, seda valjem see inimese jaoks on, seda suurem on sagedus, seda kõrgem on toon. Helisignaalid meid ümbritsevas maailmas on äärmiselt mitmekesised. Keerulisi pidevaid signaale saab esitada piisava täpsusega teatud arvu lihtsate siinusvõnkumiste summana. Veelgi enam, iga terminit, see tähendab iga sinusoidi, saab täpselt määratleda teatud arvparameetrite kogumiga - amplituud, faas ja sagedus, mida võib mingil ajahetkel pidada helikoodiks.

Ajaline heli diskreetimine Helisignaali kodeerimise käigus teostatakse selle ajaline diskreetimine - pidev laine jagatakse eraldi väikesteks ajalõikudeks ja igale sellisele lõigule määratakse kindel amplituudi väärtus. Seega asendatakse signaali amplituudi pidev sõltuvus ajast diskreetse helitugevuse tasemete jadaga.

Binaarse helikodeeringu kvaliteedi määrab kodeeringu sügavus ja diskreetimissagedus. Diskreetimissagedus – signaali taseme mõõtmiste arv ajaühikus. Helitugevuse tasemete arv määrab kodeeringu sügavuse. Kaasaegsed helikaardid pakuvad 16-bitise heli kodeerimise sügavust. Sel juhul on helitugevuse tasemete arv N = 2 I = 2 16 =

Videoteabe esitus Viimasel ajal kasutatakse arvutit üha enam videoteabega töötamiseks. Lihtsaim selline töö on filmide ja videoklippide vaatamine. Tuleb selgelt mõista, et videoteabe töötlemine nõuab arvutisüsteemi väga suurt kiirust. Mis on film arvutiteaduse mõistes? Esiteks on see heli ja graafilise teabe kombinatsioon. Lisaks kasutatakse ekraanil liikumise efekti tekitamiseks diskreetset tehnoloogiat staatiliste piltide kiireks muutmiseks. Uuringud on näidanud, et kui ühe sekundi jooksul vahetada välja rohkem kui üks kaader, siis inimsilm tajub nendes toimuvaid muutusi pidevana.

Videoteabe esitamine Näib, et kui staatilise graafika ja heli kodeerimise probleemid on lahendatud, pole videopildi salvestamine keeruline. Kuid see on ainult esmapilgul, sest traditsioonilisi teabe salvestamise meetodeid kasutades osutub filmi elektrooniline versioon liiga mahukaks. Üsna ilmselge täiustus on jätta meelde esimene kaader tervikuna (kirjanduses on tavaks nimetada seda võtmekaadriks) ja järgmistes salvestada ainult erinevused algkaadrist (erinevuskaadrid).

Mõned videofailivormingud Videoandmete esitamiseks on palju erinevaid vorminguid. Windowsi keskkonnas on näiteks juba üle 10 aasta kasutatud Video for Windowsi vormingut, mis põhineb universaalsetel AVI laiendiga failidel (Audio Video Interleave - interleaving audio and video). Mitmekülgsem on Quick Time multimeediumivorming, mis algselt sai alguse Apple'i arvutitest. Viimasel ajal on laiemalt levinud videopiltide tihendussüsteemid, mis võimaldavad pildil mõningaid silmale hoomamatuid moonutusi, et tihendusastet suurendada. Selle klassi kuulsaim standard on MPEG (Motion Picture Expert Group). MPEG-s kasutatavaid meetodeid pole lihtne mõista ja need tuginevad üsna keerulisele matemaatikale. Tehnoloogia nimega DivX (Digital Video Express) on laiemalt levinud. Tänu DivX-ile oli võimalik saavutada tihendusaste, mis võimaldas ühele CD-le mahutada täispika filmi kvaliteetse salvestuse – tihendada 4,7 GB DVD-film 650 MB-le.

Multimeedium Multimeedia (multimeedia, inglise keelest. multi - palju ja meedia - meedia, keskkond) - arvutitehnoloogiate kogum, mis kasutab samaaegselt mitut teabekandjat: tekst, graafika, video, fotograafia, animatsioon, heliefektid, kvaliteetne heli . Sõna "multimeedia" tähendab mõju kasutajale korraga mitme infokanali kaudu. Võib öelda ka nii: multimeedia on arvutiekraanil oleva pildi (sh graafilise animatsiooni ja videokaadrid) kombinatsioon teksti ja heliga. Multimeediasüsteeme kasutatakse enim hariduses, reklaamis ja meelelahutuses.

Küsimused: Mis on kood? Tooge näiteid kooliainetes kasutatava teabe kodeerimise kohta? Mõelge välja oma viise vene tähtede kodeerimiseks. Kodeerige sõnum "arvutiteadus", kasutades morsekoodi. Mis on numbrisüsteem? Mis on kahte tüüpi numbrisüsteeme? Mis on numbrisüsteemi alus? Mis on numbrisüsteemi tähestik? Näited. Millist numbrisüsteemi kasutatakse arvude salvestamiseks ja töötlemiseks arvuti mällu? Milliseid arvutipilte te teate? Milline maksimaalne summa värve saab pildil kasutada, kui igale punktile on eraldatud 3 bitti? Mida teate RGB värvimudeli kohta?

Ülesanded: Kirjutage rooma numbrite süsteemis üles arv 1945. Kirjutage üles arvud laiendatud kujul: , 957 8, Millega võrdub arvud 74 8, 3E 16, 1010 kümnendsüsteemis? Kuidas kirjutatakse arv kahendsüsteemis? kaheksandas? Arvutage graafikarežiimi jaoks vajalik videomälu maht: ekraani eraldusvõime 800x600, värvikvaliteet 16 bitti.

Hariduslik: õpilaste infokultuuri kujundamine, distsipliin, sihikindlus, töökultuur, positiivne motivatsioon kasvatustööks

Hariduslik: vaimsete põhifunktsioonide arendamine, üldised õppimisoskused, algoritmiline mõtlemine sarnaste liidestega töötamise näidete abil.

hariv: kujundada: tunni teema põhimõistete tundmine $ oskus kasutada saadud teadmisi praktilises tegevuses; käsitletava teema olemuse ja asjakohasuse mõistmine

Varustus : tahvel, arvuti, multimeedia, elektrooniline õpik “Informaatika maailm 3,4 õppeaastat”, infokaardid, kaardid - algoritmid.

Visuaalne materjal: Samuel Finley Breeze Morse’i, Jean Maurice Emile Baudot’ portreed.

Tunni tüüp: Uute teadmiste tund.

Tunni vorm: Õppetund mängu elementidega.

Tunni tehnoloogiline kaart

№	Õpetaja tegevus	Õpilaste tegevused	aega
1.	Aja organiseerimine, eesmärkide seadmine.		5 minutit
	Tervitused, õpilaste psühholoogiline ettevalmistamine tunniks.	Tervitused, psühholoogiline ettevalmistus tunniks.
2.	Uue materjali väljatöötamine.		5 minutit
2.1.	Probleemi avaldus (heuristiline vestlus, mäng).
		Õpilased lahendavad mõistatust, osalevad vestluses, vastavad küsimustele, kuulavad kaaslaste vastuseid.
2.2.	Sissejuhatus teooriasse		10
	Teabe kodeerimine arvutis	Õpilased kuulavad, jälgivad demonstratsioone läbi projektori ekraanil, kordavad õpetaja tegevust ja hoiavad lõputöö märkmeid informandikaartide abil.
2.5	Harjutused		15
		Õpilased sooritavad rühmatöid, enesekontrolli; individuaalne töö arvutis
3.	Materjali kinnistamine (oskuste kujundamine)		3 min.
		Kodeerimisreeglite sõnastamine
4.	Õppetunni kokkuvõte.		2 minutit.

Tundide ajal

1. Organisatsioonimoment

Tervitamine, kohalviibijate kontrollimine. Õppetunni seletus.

2. Teoreetiline osa

Slaidil on näha rebus. Õpilased peavad selle välja mõtlema.

Õpetaja küsimus: Kuidas seda sõna teile esitletakse? (Krüptitud või kodeeritud.)

Vastake õpetajatele: Enne sõna "kodeerimine" määratlust soovitan teil kuulata veidi ajaloolist tausta tehniliste kodeerimismeetodite ajaloost.

Õpetaja küsimus: Kes räägib meile teabe kodeerimise tehniliste viiside ajaloost?

1. õpilane räägib S.F.B. Morsest.
Ekraanil on S.F.B. Morse portree ( riis. üks)

Teabe salvestamise ja edastamise tehniliste vahendite tulekuga on tekkinud uued ideed ja kodeerimistehnikad. Esimene tehniline vahend teabe kaugedastamiseks oli telegraaf, mille leiutas 1837. aastal ameeriklane Samuel Morse.

Telegraafiteade on elektriliste signaalide jada, mis edastatakse ühest telegraafiseadmest juhtmete kaudu teisele telegraafiseadmele. Need tehnilised asjaolud viisid S. Morse'i ideele kasutada telegraafiliinide kaudu edastatava sõnumi kodeerimiseks ainult kahte tüüpi signaale - lühikesi ja pikki.

Seda kodeerimismeetodit nimetatakse morsekoodiks. Selles on iga tähestiku täht kodeeritud lühikeste signaalide (punktide) ja pikkade signaalide (kriipsude) jadaga. Tähed on üksteisest eraldatud pausidega - signaalide puudumine.

Kõige kuulsam telegraafiteade on hädasignaal. S O S" (Päästke meie hinged- päästa meie hinged) ( fraas ekraanil). Nii näeb see välja morsekoodi järgi Inglise tähestik:

* * * – – – * * *

(tegelased ekraanil)

Kolm punkti (täht S), kolm kriipsu (täht O), kolm punkti (täht S). Kaks pausi eraldavad tähed üksteisest.

Joonisel on kujutatud morse kood vene tähestiku suhtes. (Näitab slaidi morsekoodiga.) Erilisi kirjavahemärke polnud. Need olid kirjutatud sõnadega: "punkt" - punkt, "spt" - koma jne. Morsekoodi iseloomulik tunnus on erinevate tähtede muutuva pikkusega kood, seega kutsutakse morsekoodi ebaühtlane kood.

2. õpilane räägib J.M.Baudit.
Ekraanil on portree Zh.M. Bodo ( riis. 2)

Ühtse telegraafikoodi mõtles välja prantslane Jean Maurice Baudot 19. sajandi lõpus. See kasutas ainult kahte erinevat tüüpi signaali. Pole tähtis, kuidas te neid nimetate: punkt ja kriips, pluss ja miinus, null ja üks. Need on kaks erinevat elektrilist signaali. Pikkus kõik märgikoodid on samad ja on võrdne viiega. Sel juhul pole tähtede üksteisest eraldamise probleemi: iga viis signaali on tekstimärk. Seetõttu pole passi vaja.

Baudot kood - See on esimene meetod teabe binaarseks kodeerimiseks tehnoloogia ajaloos. Tänu sellele ideele oli võimalik luua otsetrükkimise telegraafiaparaat, mis näeb välja nagu kirjutusmasin. Teatud tähega klahvi vajutamisel genereeritakse vastav viieimpulsiline signaal, mis edastatakse sideliini kaudu. Vastuvõttev masin prindib selle signaali mõjul sama kirja paberilindile.

Nüüd on teil kodeerimisest veidi arusaamist. Kodeerimise selge määratluse andmiseks soovitan teil tutvuda teabekaardiga ( 3. lisa) ja kirjuta definitsioon vihikusse.

Kodeerimine - teabe (sõnumite) koodi kujul esitamise protsess .

Ja kes oskab öelda, millised kodeerimisviisid on olemas?
On kolm peamist kodeerimismeetodit:

Leia teabekaardilt ( 3. lisa) kodeerimismeetodite skeemi ja kirjutage see oma märkmikusse.

Ja mis te arvate, mis on kogu kodeerimiseks kasutatud märkide komplekti nimi? kodeerimise tähestik. Kirjutage oma määratlus teabekaardi abil üles.

Näiteks arvuti mällu kodeeritakse igasugune teave kahendtähestiku abil, mis sisaldab ainult kahte märki: 0 ja 1.

Kas te palun öelge mulle, mis on pöördkodeerimise protsessi nimi? D ökokodeerimine. Vaata infokaarti ( 3. lisa) ja kirjuta definitsioon vihikusse.

3. Praktiline osa

Ja nüüd proovime teiega omandatud teadmisi praktikas rakendada, mis koosneb 2 osast. Praktilise töö esimene osa on kodeerimisülesanded, mida täidate paaristööna. Pärast töö lõpetamist peate üksteist vastastikku kontrollima. ( 2. lisa).

1 osa

Kodeerige fraas:

1. Õpin kodeerimist
2. Igasugune edu on ennekõike raske igapäevane töö.
3. Ma ei taha õppida, aga tahan töötada

Questi võti

osa 2

(3. lisa)

Praktilise töö teine ​​osa koosneb dekodeerimisülesandest. See viiakse läbi algoritmkaartide abil ( vaata joon. üks*).

Ülesandes number 1 ( pilt 1) õige vastus: Elementary, Watson!

* Selliseid ikoone kirjeldas Conon Doyle'i loos "Tantsivad mehed"

Ülesandes number 2 on õige vastus: Kolmkümmend kolm triikrauda aknalaual – märk sellest, et valimistulu on ebaõnnestunud!

4. Kokkuvõtete tegemine

Milliseid kontseptsioone me täna arutanud oleme? ( Kodeerimine ja dekodeerimine.)
Nimetage kodeerimismeetodid. ( Graafiline, sümboolne, numbriline.)
Kas teie arvates saab sama teabe jaoks kasutada erinevaid kodeerimismeetodeid? ( Jah.)
Ja kes selgitab, miks? ( Kuna meetod sõltub kodeerimise eesmärgist, tingimustest jne..)
Ja valik, kuidas teavet kodeerida, võib olla seotud selle töötlemise kavandatud viisiga? ( Jah.)

Niisiis oleme sõnastanud kaks olulist reeglit, et informatsiooni kodeerimiseks saab kasutada erinevaid kodeerimismeetodeid ning meetodi valik sõltub kodeerimise eesmärgist ja tingimustest. Leidke need reeglid teabekaardilt ja kirjutage need oma märkmikusse. Kodus vaadake definitsioonid, kodeerimismeetodid ja reeglid uuesti üle.