Kodning och avkodning av information
För att utföra uppgiften korrekt kommer du att få 1 poäng. Det tar ungefär 2 minuter.
För att klara uppgift 5 i datavetenskap behöver du veta:
Kodningär översättning av information från en form av representation till en annan.
Avkodning– Det här är den omvända processen med kodning.
Kodning sker enhetlig Och ojämn;
- med enhetlig kodning kodas alla tecken med lika långa koder; Till exempel: ASCII eller Unicode.
- med ojämn kodning kan olika symboler kodas med koder av olika längd, detta gör avkodningen svår på grund av uppkomsten av kodtvetydighet. Till exempel: Tecken A kodas med siffran 0, B av sekvensen 01 och B av sekvensen 1. Så till exempel kan meddelandet "011" avkodas som ABB eller BV. Om koden är tvetydig kan information avkodas på olika sätt.
För entydig avkodning måste koden uppfylla Fano skick:n och inget kodord kan vara början på ett annat kodord.
Information och dess kodning
Olika tillvägagångssätt för att definiera begreppet "information". Typer av informationsprocesser. Informationsaspekt i mänsklig aktivitet
Information(lat. information- förklaring, presentation, informationsuppsättning) är ett grundläggande begrepp inom datavetenskap, som inte kan ges en strikt definition, utan bara kan förklaras:
- information är nya fakta, ny kunskap;
- information är information om föremål och miljöfenomen som ökar graden av mänsklig medvetenhet;
- information är information om föremål och företeelser i miljön som minskar graden av osäkerhet i kunskapen om dessa föremål eller fenomen vid vissa beslut.
Begreppet "information" är allmänt vetenskapligt, det vill säga det används inom olika vetenskaper: fysik, biologi, cybernetik, datavetenskap, etc. Dessutom är detta begrepp i varje vetenskap associerat med olika begreppssystem. Inom fysiken betraktas således information som antientropi (ett mått på ordningen och komplexiteten i ett system). Inom biologi är begreppet "information" förknippat med det lämpliga beteendet hos levande organismer, såväl som med forskning om ärftlighetsmekanismer. Inom cybernetik förknippas begreppet "information" med kontrollprocesser i komplexa system.
De viktigaste socialt betydelsefulla egenskaperna hos information är:
- verktyg;
- tillgänglighet (förståbarhet);
- relevans;
- fullständighet;
- pålitlighet;
- lämplighet.
Informationsprocesser förekommer kontinuerligt i det mänskliga samhället: människor uppfattar information från omvärlden med hjälp av sina sinnen, förstår den och fattar vissa beslut, som, översatta till verkliga handlingar, påverkar världen omkring dem.
Informationsprocessär processen att samla in (ta emot), sända (utbyta), lagra, bearbeta (omvandla) information.
Insamling av informationär processen att söka och välja de nödvändiga meddelandena från olika källor (att arbeta med specialiserad litteratur, referensböcker; utföra experiment; observationer; undersökningar, frågeformulär; söka i informations- och referensnätverk och system, etc.).
Överföring av informationär processen att flytta meddelanden från en källa till en mottagare längs en överföringskanal. Information överförs i form av signaler - ljud, ljus, ultraljud, elektrisk, text, grafik etc. Sändningskanaler kan vara luftrum, elektriska och fiberoptiska kablar, individer, mänskliga nervceller m.m.
Datalagringär processen att spela in meddelanden på ett påtagligt medium. Numera används papper, trä, tyg, metall och andra ytor, film och fotografiska filmer, magnetband, magnet- och laserskivor, flash-kort etc. för att lagra information.
Databehandlingär processen att få nya meddelanden från befintliga. Att bearbeta information är ett av de viktigaste sätten att öka dess kvantitet. Som ett resultat av behandlingen kan meddelanden av andra typer erhållas från ett meddelande av en typ.
Dataskyddär processen att skapa förhållanden som förhindrar oavsiktlig förlust, skada, ändring av information eller obehörig åtkomst till den. Sätt att skydda information är att skapa säkerhetskopior, lagra den i ett säkert rum, ge användarna lämpliga åtkomsträttigheter till information, kryptera meddelanden, etc.
Språk som ett sätt att representera och överföra information
Beroende på sätt att uppfatta tecken är indelade i:
- visuella (bokstäver och siffror, matematiska tecken, musiknoter, vägmärken, etc.);
- auditiv (talat tal, klockor, sirener, pip, etc.);
- taktil (punktskrift för blinda, beröringsgester, etc.);
- lukt;
- smak.
För långtidsförvaring registreras skyltar på lagringsmedia.
För att förmedla information används tecken i formuläret signaler(trafikljussignaler, skolklockljud etc.).
Enligt metoden för koppling mellan form och mening tecken är indelade i:
- ikonisk— deras form liknar det visade objektet (till exempel mappen "Den här datorn" på datorns "Skrivbord);
- symboler— kopplingen mellan deras form och betydelse fastställs enligt allmänt accepterad konvention (till exempel bokstäver, matematiska symboler ∫, ≤, ⊆, ∞; symboler för kemiska grundämnen).
För att representera information används teckensystem som kallas språk. Grunden för alla språk är alfabet— en uppsättning symboler från vilka ett meddelande bildas, och en uppsättning regler för att utföra operationer på symboler.
Språken är indelade i:
- naturlig(talat) - ryska, engelska, tyska, etc.;
- formell- finns inom speciella områden av mänsklig aktivitet (till exempel algebraspråket, programmeringsspråk, elektriska kretsar, etc.)
Nummersystem kan också ses som formella språk. Således är decimaltalsystemet ett språk vars alfabet består av tio siffror 0..9, det binära talsystemet är ett språk vars alfabet består av två siffror - 0 och 1.
Metoder för att mäta mängden information: probabilistiska och alfabetiska
Måttenheten för informationsmängden är bit. 1 bitär mängden information som finns i ett meddelande som halverar osäkerheten i kunskap om något.
Förhållandet mellan antalet möjliga händelser N och mängden information I bestäms Hartleys formel:
Låt oss till exempel säga att bollen är i en av fyra lådor. Det finns alltså fyra lika sannolika händelser (N = 4). Sedan enligt Hartleys formel 4 = 2 I. Därav I = 2. Det vill säga, meddelandet om vilken ruta bollen är i innehåller 2 bitar av information.
Alfabetisk synsätt
Med den alfabetiska metoden för att bestämma mängden information abstraherar man från innehållet (betydelsen) av information och betraktar det som en sekvens av tecken för ett visst teckensystem. Uppsättningen av symboler för ett språk (alfabetet) kan ses som olika möjliga händelser. Sedan, om vi antar att förekomsten av symboler i ett meddelande är lika sannolikt, kan vi med Hartleys formel beräkna hur mycket information varje symbol bär:
Till exempel på det ryska språket finns det 32 bokstäver (bokstaven ё används vanligtvis inte), det vill säga antalet händelser kommer att vara lika med 32. Då kommer informationsvolymen för ett tecken att vara lika med:
I = log 2 32 = 5 bitar.
Om N inte är en heltalspotens av 2, så är log 2N inte ett heltal och I måste avrundas uppåt. När jag löser problem i detta fall kan jag hittas som log 2 N", där N′ är potensen av två närmast N - så att N′ > N.
Till exempel finns det 26 bokstäver på engelska. Informationsvolymen för ett tecken kan hittas så här:
N = 26; N" = 32; I = log 2 N" = log 2 (2 5) = 5 bitar.
Om antalet bokstäver är N, och antalet tecken i meddelandeposten är M, beräknas informationsvolymen för detta meddelande med formeln:
I = M log 2 N.
Exempel på problemlösning
Exempel 1. Ljusdisplayen består av glödlampor, som var och en kan vara i ett av två lägen ("på" eller "av"). Vilket är det minsta antalet glödlampor som måste finnas på resultattavlan för att den ska kunna sända 50 olika signaler?
Lösning. Genom att använda n glödlampor, som var och en kan vara i ett av två tillstånd, kan 2 n signaler kodas. 2 5< 50 < 2 6 , поэтому пяти лампочек недостаточно, а шести хватит.
Svar: 6.
Exempel 2. Den meteorologiska stationen övervakar luftfuktigheten. Resultatet av en mätning är ett heltal från 0 till 100, som skrivs med minsta möjliga antal bitar. Stationen gjorde 80 mätningar. Bestäm informationsvolymen för observationsresultaten.
Lösning. I det här fallet är alfabetet en uppsättning heltal från 0 till 100. Det finns 101 sådana värden totalt. Därför är informationsvolymen för resultaten av en mätning I = log 2 101. Detta värde kommer inte att vara ett. heltal. Låt oss ersätta talet 101 med den närmaste potensen av två större än 101. Detta tal är 128 = 27. Vi antar för en dimension I = log 2 128 = 7 bitar. För 80 mätningar är den totala informationsvolymen lika med:
80 · 7 = 560 bitar = 70 byte.
Svar: 70 byte.
Probabilistiskt förhållningssätt
En probabilistisk metod för att mäta mängden information används när möjliga händelser har olika sannolikheter att inträffa. I detta fall bestäms mängden information enligt Shannons formel:
$I=-∑↙(i=1)↖(N)p_ilog_2p_i$,
där $I$ är mängden information;
$N$ — antal möjliga händelser;
$p_i$ är sannolikheten för $i$-th-händelsen.
Anta till exempel att när du kastar en asymmetrisk tetraedrisk pyramid kommer sannolikheterna för enskilda händelser att vara lika:
$p_1=(1)/(2), p_2=(1)/(4), p_3=(1)/(8), p_4=(1)/(8)$.
Sedan kan mängden information som kommer att erhållas efter att ha implementerat en av dem beräknas med Shannons formel:
$I=-((1)/(2)log_2(1)/(2)+(1)/(4)log_2(1)/(4)+(1)/(8)log_2(1)/( 8)+(1)/(8)·log_2(1)/(8))=(14)/(8)$ bitar $= 1,75 $bitar.
Enheter för att mäta mängden information
Den minsta informationsenheten är bit(Engelsk) binär siffra (bit)- binär informationsenhet).
Bitär mängden information som krävs för att entydigt fastställa en av två lika sannolika händelser. Till exempel får en person en bit information när han får reda på om tåget han behöver är sent eller inte, om det var frost på natten eller inte, om student Ivanov är närvarande vid föreläsningen eller inte, etc.
Inom datavetenskap är det vanligt att överväga sekvenser med 8 bitars längd. Denna sekvens kallas byte.
Härledda enheter för att mäta mängden information:
1 byte = 8 bitar
1 kilobyte (KB) = 1024 byte = 2 10 byte
1 megabyte (MB) = 1024 kilobyte = 2 20 byte
1 gigabyte (GB) = 1024 megabyte = 2 30 byte
1 terabyte (TB) = 1024 gigabyte = 2 40 byte
Processen att överföra information. Typer och egenskaper hos källor och mottagare av information. Signal, kodning och avkodning, orsaker till informationsförvrängning vid överföring
Information överförs i form av meddelanden från vissa källa information till henne mottagare genom kommunikationskanal mellan dem.
Informationskällan kan vara en levande varelse eller en teknisk anordning. Källan skickar det överförda meddelandet, som kodas in i det överförda signal.
Signalär en material- och energiform av informationsrepresentation. Med andra ord, signalär en informationsbärare, vars en eller flera parametrar, ändras, visar ett meddelande. Signaler kan vara analog(kontinuerlig) eller diskret(impuls).
Signalen skickas över en kommunikationskanal. Som ett resultat visas en mottagen signal vid mottagaren, som avkodas och blir det mottagna meddelandet.
Överföring av information via kommunikationskanaler åtföljs ofta av störningar, vilket orsakar förvrängning och förlust av information.
Exempel på problemlösning
Exempel 1. För att koda bokstäverna A, Z, P, O används tvåsiffriga binära siffror 00, 01, 10, 11 respektive. Ordet ROSE kodades på detta sätt och resultatet skrevs i hexadecimal kod. Ange det resulterande numret.
Lösning. Låt oss skriva ner sekvensen av koder för varje tecken i ordet ROSE: 10 11 01 00. Om vi betraktar den resulterande sekvensen som ett binärt tal, kommer det i hexadecimal kod att vara lika med: 1011 0100 2 = B4 16.
Svar: B4 16.
Informationsöverföringshastighet och kommunikationskanalkapacitet
Mottagning/överföring av information kan ske med olika hastigheter. Mängden information som överförs per tidsenhet är informationsöverföringshastighet, eller informationsflödets hastighet.
Hastigheten uttrycks i bitar per sekund (bps) och deras multipler Kbps och Mbps, såväl som byte per sekund (byte/s) och deras multipler KB/s och MB/s.
Den maximala hastigheten för informationsöverföring över en kommunikationskanal kallas kanalkapacitet.
Exempel på problemlösning
Exempel 1. Dataöverföringshastigheten via en ADSL-anslutning är 256 000 bps. Att överföra filen via denna anslutning tog 3 minuter. Bestäm filstorleken i kilobyte.
Lösning. Filstorleken kan beräknas genom att multiplicera överföringshastigheten med överföringstiden. Låt oss uttrycka tiden i sekunder: 3 min = 3 ⋅ 60 = 180 s. Låt oss uttrycka hastigheten i kilobyte per sekund: 256000 bps = 256000: 8: 1024 KB/s. När vi beräknar filstorleken, för att förenkla beräkningarna, lyfter vi fram krafterna hos två:
Filstorlek = (256000:8:1024) ⋅ (3 ⋅ 60) = (2 8 ⋅ 10 3:2 3:2 10) ⋅ (3 ⋅ 15 ⋅ 2 2) = (2 8 ⋅ 125 ⋅ 3:2 ⋅ 3: 2 10) ⋅ (3 ⋅ 15 ⋅ 2 2) = 125 ⋅ 45 = 5625 KB.
Svar: 5625 KB.
Presentation av numerisk information. Addition och multiplikation i olika talsystem
Representera numerisk information med hjälp av nummersystem
För att representera information i en dator används en binär kod, vars alfabet består av två siffror - 0 och 1. Varje siffra i en maskinbinär kod bär en mängd information som är lika med en bit.
Notationär ett system för att registrera nummer med en specifik uppsättning siffror.
Nummersystemet kallas positionella, om samma siffra har en annan betydelse, vilket bestäms av dess plats i talet.
Decimaltalssystemet är positionellt. Till exempel, i talet 999 betyder siffran "9", beroende på positionen, 9, 90, 900.
Det romerska talsystemet är icke-positionell. Till exempel förblir värdet på siffran X i talet XXI oförändrat när dess position i talet varierar.
Positionen för en siffra i ett nummer kallas ansvarsfrihet. Siffran i ett nummer ökar från höger till vänster, från låga till höga siffror.
Antalet olika siffror som används i ett positionsnummersystem kallas dess grund.
Utökad form av numretär en post som representerar summan av produkterna av siffrorna i ett tal och värdet av positionerna.
Till exempel: 8527 = 8 ⋅ 10 3 + 5 ⋅ 10 2 + 2 ⋅ 10 1 + 7 ⋅ 10 0 .
Den utökade formen för att skriva tal i ett godtyckligt talsystem har formen
$∑↙(i=n-1)↖(-m)a_iq^i$,
där $X$ är ett tal;
$a$ — siffror i den numeriska posten som motsvarar siffrorna;
$i$ — index;
$m$ — antal siffror i bråkdelen;
$n$ — antal siffror i heltalets delnummer;
$q$ är basen i talsystemet.
Låt oss till exempel skriva den utökade formen av decimaltalet $327,46$:
$n=3, m=2, q=10,$
$X=∑↙(i=2)↖(-2)a_iq^i=a_2·10^2+a_1·10^1+a_0·10^0+a_(-1)·10^(-1)+ a_(-2)·10^(-2)=3·10^2+2·10^1+7·10^0+4·10^(-1)+6·10^(-2)$
Om basen för det använda talsystemet är större än tio, så introduceras en symbol med en parentes överst eller en bokstavsbeteckning för talen: B - binärt system, O - oktalt, H - hexadecimalt.
Till exempel, om i det duodecimala talsystemet 10 = A och 11 = B, kan talet 7A,5B 12 skrivas enligt följande:
7A,5B 12 = B ⋅ 12 -2 + 5 ⋅ 2 -1 + A ⋅ 12 0 + 7 ⋅ 12 1.
Det hexadecimala talsystemet har 16 siffror, betecknade 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, vilket motsvarar följande tal i decimalen talsystem: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15. Exempelnummer: 17D,ECH; F12AH.
Översättning av tal i positionsnummersystem
Konvertera tal från ett godtyckligt talsystem till decimaltal
För att konvertera ett tal från vilket positionsnummersystem som helst till decimaler måste du använda den utökade formen av siffran, och om nödvändigt ersätta bokstavsbeteckningarna med motsvarande siffror. Till exempel:
1101 2 = 1 ⋅ 2 3 + 1 ⋅ 2 2 + 0 ⋅ 2 1 + 1 ⋅ 2 0 = 13 10 ;
17D,ECH = 12 ⋅ 16 -2 + 14 ⋅ 16 -1 + 13 ⋅ 160 + 7 ⋅ 16 1 + 1 ⋅ 16 2 = 381,921875.
Konvertera tal från decimaltalsystemet till ett givet
För att konvertera ett heltal i decimaltalsystemet till ett tal i vilket annat talsystem som helst, dividera jämnt med talsystemets bas tills du får noll. Tal som uppstår som en rest från division med basen i systemet representerar en sekventiell post av siffrorna i ett tal i det valda talsystemet från det minst signifikanta till det mest signifikanta. Därför, för att skriva själva talet, skrivs divisionsresterna i omvänd ordning.
Låt oss till exempel konvertera decimaltalet 475 till det binära talsystemet. För att göra detta kommer vi att sekventiellt utföra division med basen av det nya talsystemet, det vill säga med 2:
När vi läser divisionsresterna från botten till toppen får vi 111011011.
Undersökning:
1 ⋅ 2 8 + 1 ⋅ 2 7 + 1 ⋅ 2 6 + 0 ⋅ 2 5 + 1 ⋅ 2 4 + 1 ⋅ 2 3 + 0 ⋅ 2 2 + 1 ⋅ 2 1 + 1 ⋅ 2 0 = 1 + 2 + 8 + 16 + 64 + 128 + 256 = 475 10 .
För att konvertera decimalbråk till ett tal i valfritt talsystem, multiplicera med basen av talsystemet successivt tills bråkdelen av produkten är lika med noll. De resulterande heltalsdelarna är siffrorna i numret i det nya talsystemet, och de måste representeras av siffrorna i detta nya talsystem. Hela delar kasseras därefter.
Låt oss till exempel omvandla decimalbråket 0,375 10 till det binära talsystemet:
Det erhållna resultatet är 0,011 2.
Alla tal kan inte uttryckas korrekt i det nya talsystemet, så ibland beräknas bara det nödvändiga antalet bråksiffror.
Konvertera tal från binära till oktala och hexadecimala och vice versa
För att skriva oktala tal används åtta siffror, d.v.s. i varje siffra i numret är 8 skrivalternativ möjliga. Varje siffra i ett oktalt tal innehåller 3 bitar information (8 = 2 І; І = 3).
För att konvertera ett tal från det oktala talsystemet till binär kod är det således nödvändigt att representera varje siffra i detta tal som en triad av binära tecken. Extra nollor i de mest signifikanta siffrorna kasseras.
Till exempel:
1234,777 8 = 001 010 011 100,111 111 111 2 = 1 010 011 100,111 111 111 2 ;
1234567 8 = 001 010 011 100 101 110 111 2 = 1 010 011 100 101 110 111 2 .
När du konverterar ett binärt tal till det oktala talsystemet måste du ersätta varje triad av binära siffror med en oktal siffra. I det här fallet, om nödvändigt, justeras talet genom att lägga till nollor före heltalsdelen eller efter bråkdelen.
Till exempel:
1100111 2 = 001 100 111 2 = 147 8 ;
11,1001 2 = 011,100 100 2 = 3,44 8 ;
110,0111 2 = 110,011 100 2 = 6,34 8 .
Sexton siffror används för att skriva hexadecimala tal, d.v.s. för varje siffra i ett nummer är 16 skrivalternativ möjliga. Varje siffra i ett hexadecimalt tal innehåller 4 bitar information (16 = 2 І; І = 4).
Så för att konvertera ett binärt tal till hexadecimalt måste du dela upp det i grupper om fyra siffror och konvertera varje grupp till en hexadecimal siffra.
Till exempel:
1100111 2 = 0110 0111 2 = 67 16 ;
11,1001 2 = 0011,1001 2 = 3,9 16 ;
110,0111001 2 = 0110,0111 0010 2 = 65,72 16 .
För att konvertera ett hexadecimalt tal till binär kod måste varje siffra i detta nummer representeras av fyra binära siffror.
Till exempel:
1234,AB77 16 = 0001 0010 0011 0100,1010 1011 0111 0111 2 = 1 0010 0011 0100,1010 1011 0111 0111 2;
CE4567 16 = 1100 1110 0100 0101 0110 0111 2 .
När du konverterar ett tal från ett godtyckligt talsystem till ett annat måste du utföra en mellankonvertering till ett decimaltal. Vid konvertering från oktalt till hexadecimalt och vice versa används den binära extranummerkoden.
Låt oss till exempel konvertera det ternära talet 211 3 till septumssystemet. För att göra detta, konvertera först talet 211 3 till decimal genom att skriva dess utökade form:
211 3 = 2 ⋅ 3 2 + 1 ⋅ 3 1 + 1 ⋅ 3 0 = 18 + 3 + 1 = 22 10 .
Sedan konverterar vi decimaltalet 22 10 till septaltalssystemet genom att dividera jämnt med basen av det nya talsystemet, dvs med 7:
Så, 211 3 = 31 7.
Exempel på problemlösning
Exempel 1. I ett talsystem med en viss bas skrivs talet 12 som 110. Ange denna bas.
Lösning. Låt oss beteckna den önskade basen n enligt regeln för att skriva tal i positionsnummersystem 12 10 = 110 n = 0 · n 0 + 1 · n 1 + 1 · n 2. Låt oss göra en ekvation: n 2 + n = 12. Låt oss hitta den naturliga roten av ekvationen (en negativ rot är inte lämplig, eftersom basen i talsystemet per definition är ett naturligt tal större än ett): n = 3. Låt oss kolla svaret vi fick: 110 3 = 0 3 0 + 1 3 1 + 1 3 2 = 0 + 3 + 9 = 12.
Svar: 3.
Exempel 2. Separera med kommatecken, i stigande ordning, anger alla baser av talsystem där talet 22 slutar på 4.
Lösning. Den sista siffran i ett tal är resten när talet divideras med talsystemets bas. 22 - 4 = 18. Låt oss hitta divisorerna för talet 18. Dessa är talen 2, 3, 6, 9, 18. Talen 2 och 3 är inte lämpliga, eftersom det i talsystem med bas 2 och 3 inte finns någon nummer 4. Så de nödvändiga baserna är siffrorna 6, 9 och 18. Låt oss kontrollera resultatet genom att skriva talet 22 i de angivna talsystemen: 22 10 = 34 6 = 24 9 = 14 18.
Svar: 6, 9, 18.
Exempel 3. Ange, separerade med kommatecken, i stigande ordning, alla nummer som inte överstiger 25, vars inmatning i det binära talsystemet slutar på 101. Skriv svaret i decimaltalssystemet.
Lösning. För enkelhetens skull kommer vi att använda det oktala talsystemet. 101 2 = 5 8. Då kan talet x representeras som x = 5 8 0 + a 1 8 1 + a 2 8 2 + a 3 8 3 + ..., där a 1, a 2, a 3, ... är siffror i oktalt system. De erforderliga talen får inte överstiga 25, så expansionen måste begränsas till de två första termerna (8 2 > 25), dvs sådana tal måste ha representationen x = 5 + a 1 8. Eftersom x ≤ 25 är de tillåtna värdena av en 1 kommer att vara 0 , 1, 2. Genom att ersätta dessa värden i uttrycket för x får vi de nödvändiga talen:
ai = 0; x = 5 + 08 = 5;.
ai=1; x = 5 + 18 = 13;.
ai = 2; x = 5 + 28 = 21;.
Låt oss kolla:
13 10 = 1101 2 ;
21 10 = 10101 2 .
Svar: 5, 13, 21.
Aritmetiska operationer i positionstalssystem
Reglerna för att utföra aritmetiska operationer på binära tal specificeras genom additions-, subtraktions- och multiplikationstabeller.
Regeln för att utföra additionsoperationen är densamma för alla talsystem: om summan av de tillagda siffrorna är större än eller lika med basen i talsystemet, överförs enheten till nästa siffra till vänster. Vid avdrag, om nödvändigt, gör ett lån.
Exekveringsexempel tillägg: lägg till de binära talen 111 och 101, 10101 och 1111:
Exekveringsexempel subtraktion: subtrahera de binära talen 10001 - 101 och 11011 - 1101:
Exekveringsexempel multiplikation: Låt oss multiplicera de binära talen 110 och 11, 111 och 101:
Aritmetiska operationer utförs på liknande sätt i oktala, hexadecimala och andra talsystem. Det är nödvändigt att ta hänsyn till att överföringsbeloppet till nästa siffra när man lägger till och lånar från den högsta siffran vid subtrahering bestäms av värdet på basen i talsystemet.
Låt oss till exempel lägga till de oktala talen 36 8 och 15 8, samt subtrahera de hexadecimala talen 9C 16 och 67 16:
När du utför aritmetiska operationer på tal representerade i olika talsystem måste du först konvertera dem till samma system.
Representerar siffror i en dator
Fast punktformat
I datorns minne lagras heltal i formatet c fixpunkt: varje siffra i en minnescell motsvarar samma siffra i ett nummer.
För att lagra icke-negativa heltal tilldelas 8 bitar minne. Minsta antalet motsvarar åtta nollor lagrade i åtta bitar av en minnescell och är lika med 0. Maximalt antal motsvarar åtta ettor och är lika med
1 ⋅ 2 7 + 1 ⋅ 2 6 + 1 ⋅ 2 5 + 1 ⋅ 2 4 + 1 ⋅ 2 3 + 1 ⋅ 2 2 + 1 ⋅ 2 1 + 1 ⋅ 2 0 = 255 10 .
Således är intervallet för icke-negativa heltal från 0 till 255.
För n-bitars representation kommer området att vara från 0 till 2 n - 1.
För att lagra signerade heltal tilldelas 2 byte minne (16 bitar). Den mest signifikanta siffran tilldelas talets tecken: om talet är positivt skrivs 0 i teckensiffran, om talet är negativt - 1. Denna representation av siffror i en dator kallas direktkod.
Används för att representera negativa tal ytterligare kod. Det låter dig ersätta den aritmetiska operationen av subtraktion med en additionsoperation, vilket avsevärt förenklar driften av processorn och ökar dess prestanda. Den komplementära koden för ett negativt tal A lagrat i n celler är 2 n − |A|.
Algoritm för att erhålla tilläggskoden för ett negativt tal:
1. Skriv ner direktkoden för numret i n binära siffror.
2. Skaffa omvänd kod för numret. (Den omvända koden bildas av direktkoden genom att ersätta nollor med ettor och ettor med nollor, förutom siffrorna i teckenbiten. För positiva tal sammanfaller den omvända koden med direktkoden. Den används som en mellanlänk för att få en extra kod.)
3. Lägg till en till den resulterande omvända koden.
Till exempel får vi tilläggskoden för numret -2014 10 för en representation på sexton bitar:
Vid algebraisk addition av binära tal med tvås komplementkod representeras positiva termer i tvås komplementkod, och negativa termer representeras i tvås komplementkod. Sedan summeras dessa koder, inklusive teckenbitarna, som anses vara de mest signifikanta bitarna. Vid bärning från skyltbiten kasseras bärenheten. Som ett resultat erhålls en algebraisk summa i direkt kod om denna summa är positiv, och i komplementär kod om summan är negativ.
Till exempel:
1) Hitta skillnaden 13 10 - 12 10 för en åttabitars representation. Låt oss representera de givna talen i det binära talsystemet:
13 10 = 1101 2 och 12 10 = 1100 2.
Låt oss skriva de direkta, omvända och komplementära koderna för talet -12 10 och direktkoden för talet 13 10 i åtta bitar:
Låt oss ersätta subtraktion med addition (för bekvämligheten med att kontrollera teckenbiten kommer vi villkorligt att separera den med tecknet "_"):
Eftersom det fanns en överföring från teckenbiten kasserar vi den första enheten, och som ett resultat får vi 00000001.
2) Hitta skillnaden 8 10 - 13 10 för en åttabitars representation.
Låt oss skriva de direkta, omvända och komplementära koderna för talet -13 10 och direktkoden för talet 8 10 i åtta bitar:
Låt oss ersätta subtraktion med addition:
Teckenbiten innehåller ett, vilket innebär att resultatet erhålls i tvås komplementkod. Låt oss gå från den kompletterande koden till den omvända och subtrahera en:
11111011 - 00000001 = 11111010.
Låt oss gå från den omvända koden till den direkta och invertera alla siffror, med undantag av tecknet (mest signifikanta) siffran: 10000101. Detta är decimaltalet -5 10.
Eftersom i n-bitars representation av ett negativt tal A i tvås komplementkod, den mest signifikanta biten allokeras för att lagra tecknet för talet, är det minsta negativa talet lika med: A = -2 n-1, och det maximala : |A| = 2 n-1 eller A = -2 n-1 - 1.
Låt oss definiera intervallet för nummer som kan lagras i RAM i formatet långa undertecknade heltal(32 bitar minne tilldelas för att lagra sådana nummer). Minsta negativa siffra är
A = -2 31 = -2147483648 10.
Det maximala positiva talet är
A = 2 31 - 1 = 2147483647 10.
Fördelarna med fixpunktsformatet är enkelheten och klarheten i representationen av tal, enkelheten hos algoritmerna för att implementera aritmetiska operationer. Nackdelen är det lilla intervallet av representativa tal, vilket är otillräckligt för att lösa de flesta tillämpade problem.
Flyttalsformat
Reella tal lagras och bearbetas i en dator i formatet med flytpunkt använder exponentiell notation för siffror.
Ett tal i exponentiellt format representeras enligt följande:
där $m$ är mantissan för talet (en riktig bråkdel som inte är noll);
$q$ är basen i talsystemet;
$n$ är ordningen på numret.
Till exempel skulle decimaltalet 2674.381 i vetenskaplig notation skrivas enligt följande:
2674,381 = 0,2674381 ⋅ 10 4 .
Ett flyttal kan uppta 4 byte minne ( normal noggrannhet) eller 8 byte ( Dubbel precision). När man skriver ett tal tilldelas bitar för att lagra mantiss-tecknet, exponenttecknet, exponenten och mantissan. De två sista kvantiteterna bestämmer intervallet för förändringar i siffror och deras noggrannhet.
Låt oss definiera intervallet (ordningen) och precisionen (mantissa) för formatet av vanliga precisionstal, det vill säga fyrabyte. Av de 32 bitarna är 8 tilldelade för att lagra ordern och dess tecken, och 24 tilldelas för att lagra mantissan och dess tecken.
Låt oss hitta det maximala värdet för ordningen på numret. Av de 8 bitarna används den mest signifikanta biten för att lagra ordertecknet, de återstående 7 används för att registrera ordervärdet. Det betyder att maxvärdet är 1111111 2 = 127 10. Eftersom tal är representerade i det binära talsystemet, alltså
$q^n = 2^(127)≈ 1,7 · 10^(38)$.
På samma sätt är det maximala värdet för mantissan
$m = 2^(23) - 1 ≈ 2^(23) = 2^((10 · 2,3)) ≈ 1000^(2,3) = 10^((3 · 2,3)) ≈ 10^7$.
Således är intervallet för siffror med vanlig precision $±1,7 · 10^(38)$.
Kodning av textinformation. ASCII-kodning. De huvudsakliga kyrilliska kodningarna som används
Överensstämmelsen mellan en uppsättning tecken och en uppsättning numeriska värden kallas teckenkodning. När textinformation skrivs in i en dator är den binärkodad. Symbolkoden lagras i datorns RAM. I processen att visa en symbol på skärmen utförs den omvända operationen - avkodning, dvs konvertera teckenkoden till dess bild.
Den specifika numeriska koden som tilldelats varje tecken registreras i kodtabeller. Samma tecken i olika kodtabeller kan motsvara olika sifferkoder. De nödvändiga textkonverteringarna utförs vanligtvis av speciella omvandlingsprogram inbyggda i de flesta applikationer.
Vanligtvis används en byte (åtta bitar) för att lagra en teckenkod, så teckenkoder kan variera från 0 till 255. Sådana kodningar kallas enkelbyte. De tillåter 256 tecken (N = 2 I = 2 8 = 256). Tabellen med enbyte-teckenkoder kallas ASCII (American Standard Code for Information Interchange- Amerikansk standardkod för informationsutbyte). Den första delen av ASCII-kodtabellen (från 0 till 127) är densamma för alla IBM-PC-kompatibla datorer och innehåller:
- kontrollteckenkoder;
- koder för siffror, aritmetiska operationer, skiljetecken;
- några specialtecken;
- koder av stora och små latinska bokstäver.
Den andra delen av tabellen (koder från 128 till 255) varierar från dator till dator. Den innehåller koder för bokstäver i det nationella alfabetet, koder för vissa matematiska symboler och koder för pseudografiska symboler. För ryska bokstäver används för närvarande fem olika kodtabeller: KOI-8, SR1251, SR866, Mas, ISO.
Nyligen har en ny internationell standard fått stor spridning Unicode. Den allokerar två byte (16 bitar) för att koda varje tecken, så den kan koda 65536 olika tecken (N = 2 16 = 65536). Teckenkoder kan ha värden från 0 till 65535.
Exempel på problemlösning
Exempel. Följande fras är kodad med Unicode:
Jag vill gå på universitetet!
Utvärdera informationsvolymen för denna fras.
Lösning. Den här frasen innehåller 31 tecken (inklusive mellanslag och skiljetecken). Eftersom Unicode allokerar 2 byte minne för varje tecken, kommer hela frasen att kräva 31 ⋅ 2 = 62 byte eller 31 ⋅ 2 ⋅ 8 = 496 bitar.
Svar: 32 byte eller 496 bitar.
A9 Ämne: Kodning och avkodning av information.
Vad du behöver veta:
· kodning är översättning av information från ett språk till ett annat (inspelning i ett annat symbolsystem,
i ett annat alfabet)
· vanligtvis är kodning översättning av information från "mänskligt" språk till ett formellt språk, till exempel till binär kod, och avkodning är den omvända övergången
· ett tecken i det ursprungliga meddelandet kan ersättas med ett tecken i den nya koden eller flera tecken, eller vice versa - flera tecken i det ursprungliga meddelandet ersätts med ett tecken i den nya koden (kinesiska tecken anger hela ord och begrepp)
· kodning kan vara enhetlig Och ojämn
;
med enhetlig kodning kodas alla tecken med lika långa koder;
med ojämn kodning kan olika tecken kodas med koder av olika längd, detta gör avkodningen svår
· det kodade meddelandet kan vara entydigt avkoda från början , om uppfyllt Fano skick : inget kodord är början på ett annat kodord;
· kodat meddelande kan vara otvetydigt avkoda från slutet , om uppfyllt omvänt Fano-tillstånd: inget kodord är slutet på ett annat kodord;
· Fano-villkoret är ett tillräckligt men inte nödvändigt villkor för entydig avkodning.
Exempeluppgift
Meddelanden som endast innehåller 4 bokstäver sänds över kommunikationskanalen: E, N, O, T. För att koda bokstäverna E, N, O används 5-bitars kodord: E - 00000, N - 00111, O - 11011. För denna uppsättning koder har ord följande egenskap: två valfria ord från uppsättningen skiljer sig åt i minst tre positioner. Denna egenskap är viktig för att dekryptera meddelanden i närvaro av störningar. Vilket av följande kodord kan användas för bokstaven T så att den angivna egenskapen gäller för alla
fyra kodord?
1) 1100 inget av orden ovan passar
Lösning:
1) koden som diskuteras i problembeskrivningen avser brusbeständiga koder som gör det möjligt att upptäcka och korrigera ett visst antal fel orsakade av störningar under dataöverföring;
1) antalet positioner där två kodord av samma längd skiljer sig åt kallas Hamming-avståndet
2) en kod i vilken Hamming-avståndet mellan varje par av kodord är d, låter dig upptäcka upp till d-1 fel; för rättelse r fel kräver att ett villkor är uppfyllt
d ≥ 2r + 1
så koden med d = 3 låter dig upptäcka ett eller två fel och korrigera ett fel.
3) det är lätt att kontrollera att för en given kod (E - 00000, H - 00111, O - 11011) är Hamming-avståndet 3; tabellen belyser de olika bitarna, det finns tre av dem i par E-H och H-O och fyra
i par E-O:
E – 00000 E – 00000 N – 00111
N – 00111 O – 11011 O – 11011
4) nu kontrollerar vi avståndet mellan kända koder och svarsalternativ; för det första svaret 11111 får vi ett minsta avstånd på 1 (i O-T-paret), detta alternativ är inte lämpligt:
T - 11111 T - 11111 T - 11111
5) för det andra svaret 11100 får vi ett minimiavstånd på 3 (i par E-T och O-T):
E – 00000 N – 00111 O – 11011
T - 11100 T - 11100 T - 11100
6) för det tredje svaret 00011 får vi det minsta avståndet 1 (i H-T-paret), detta alternativ är inte lämpligt:
E – 00000 N – 00111 O – 11011
T - 00011 T - 00011 T - 00011
7) sålunda behålls Hamming-avståndet på 3 endast för svar 2. Svar: 2.
Ett annat exempel på uppgift:
För att koda en viss sekvens bestående av bokstäverna A, B, C, D och D används en olikformig binär kod, som gör det möjligt att entydigt avkoda den resulterande binära sekvensen. Här är koden: A–00, B–010, B–011, G–101, D–111. Är det möjligt att förkorta längden på kodordet för en av bokstäverna så att koden fortfarande kan avkodas entydigt? Koderna för de återstående bokstäverna bör inte ändras. Välj det rätta svaret.
1) för bokstaven B är detta omöjligt
3) för bokstaven B – för bokstaven G – 01
Lösning (enkel väg, kontrollera Fanos villkor):
8) för entydig avkodning är det tillräckligt att Fano-villkoret eller det omvända Fano-villkoret är uppfyllt;
9) kontrollera alternativ 1, 3 och 4 sekventiellt; om ingen av dem är lämplig måste du välja alternativ 2 ("detta är omöjligt");
10) kontroll Alternativ 1: A–00, B–01, C–011, G–101, D–111.
«(koden för bokstaven B sammanfaller med början av koden för bokstaven B);
det "omvända" Fano-villkoret är inte uppfyllt(koden för bokstaven B sammanfaller med slutet av koden för bokstaven G); därför är detta alternativ inte lämpligt;
11) kontroll alternativ 3: A–00, B–010, C–01, G–101, D–111.
« det direkta Fano-villkoret är inte uppfyllt(koden för bokstaven B sammanfaller med början av koden för bokstaven B);
« det omvända Fano-tillståndet är inte uppfyllt(koden för bokstaven B sammanfaller med slutet av koden för bokstaven G); därför är detta alternativ inte lämpligt;
12) kontroll alternativ 4: A–00, B–010, C–011, G–01, D–111.
« det direkta Fano-villkoret är inte uppfyllt(koden för bokstaven G sammanfaller med början av koderna för bokstäverna B och C);
Men det "omvända" Fano-villkoret är uppfyllt(koden för bokstaven G sammanfaller inte med slutet av koderna för de andra bokstäverna); så detta alternativ passar; rätt svar är 4.
Exempel på uppgift: demo_12
För att koda en viss sekvens bestående av bokstäverna A, B, C, D och D, bestämde vi oss för att använda en olikformig binär kod, som gör att vi entydigt kan avkoda den binära sekvensen som visas på den mottagande sidan av kommunikationskanalen. Använd kod : A–1, B–000, B–001, G–011.
Ange vilket kodord bokstaven D ska kodas med. Längden på detta kodord ska vara den minsta möjliga. Koden måste uppfylla egenskapen entydig avkodning.
Lösning:
13) notera att för en känd del av koden är Fano-villkoret uppfyllt - inget kodord är början på ett annat kodord
14) om D = 00, en sådan kodkedja sammanfaller med början av B = 000 och B = 001 000000: det kan vara DDD eller BB; alltså det första alternativet passar inte
15) om D = 01, en sådan kodkedja sammanfaller med början av Г = 011, är det omöjligt att entydigt avkoda kedjan 011: det kan vara JA eller G; så det andra alternativet också passar inte
16)
om D = 11, Fano-villkoret överträds också: kodordet A = 1 sammanfaller med början av koden för bokstaven D, det är omöjligt att entydigt avkoda kedjan 111: det kan vara JA eller AAA; tredje alternativet
passar inte
17) för det fjärde alternativet, D = 010, Fano-villkoret bryts inte; rätt svar – 4 .
Ett annat exempel på uppgift:
För att sända ett meddelande över en kommunikationskanal som endast består av bokstäverna A, B, C, D, bestämde de sig för att använda en kod med ojämn längd: A=0, B=10, C=110. Hur man kodar
bokstaven G, så att kodens längd är minimal och en entydig uppdelning av det kodade meddelandet i bokstäver tillåts?
Lösning (alternativ 1, urvalsmetod):
1) överväg alla alternativ i ordningsföljd av ökande längd på bokstaven G-koden
2) låt oss börja med Г=1;
det visar sig att meddelandet "10" kan avkodas på två sätt:
Hur GA eller B, så det här alternativet är inte lämpligt
3) nästa längsta alternativ Г=11;
i detta fall kan meddelandet "110" avkodas
Hur GA eller B, så det här alternativet är inte heller lämpligt 4) tredje alternativet, Г=111
, ger entydig avkodning i alla kombinationer av bokstäver, därför... är svaret 3.
Ett annat exempel på uppgift:
För att koda bokstäverna A, B, C, D bestämde de sig för att använda tvåsiffriga sekventiella binära tal (från 00 till 11). Om du kodar teckensekvensen BAVG på detta sätt och skriver resultatet i hexadecimal kod får du
Lösning:
18) från villkoret är bokstavskoderna följande: A – 00, B – 01, C – 10 och D – 11, koden är enhetlig
19) BAVG-sekvensen kodas enligt följande:= 1001011
20) vi kommer att dela upp en sådan post i tetrader från höger till vänster och omvandla varje tetrad till det hexadecimala systemet (det vill säga först till decimaler, och sedan ersätta alla siffror från 10 till 15 med bokstäverna A, B, C, D, E, F); vi får 1001011 = 0 = 4B16 Rätt svar är 1.
Ett annat exempel på uppgift:
En svartvit bitmappsbild kodas rad för rad, med början i det övre vänstra hörnet och slutar i det nedre högra hörnet. Vid kodning representerar 1 svart och 0 representerar vit.
För kompakthetens skull skrevs resultatet i hexadecimalt talsystem. Välj rätt kodinmatning.
1) BD9AA5 2) BDA9B5 3) BDA9D5 4) DB9DAB
Lösning:
1) "dra ut" rasterbilden till en kedja: först den första (översta) raden, sedan den andra, etc.:
1 rad | 2 rad | 3 rad | 4 rad |
2) det finns 24 celler i denna remsa, fyll de svarta med ettor och de vita med nollor:
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
||||||||||||||
1 rad | 2 rad | 3 rad | 4 rad |
3) eftersom varje siffra i det hexadecimala systemet är uppdelad i exakt 4 binära siffror, delar vi remsan i tetrads- grupper om fyra celler (i det här fallet spelar det ingen roll var du ska börja divisionen, eftersom det finns ett heltal av anteckningsböcker i remsan - 6):
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
4)
omvandling av tetraderna till det hexadecimala systemet får vi sekventiellt talen B (11), D (13), A (10), 9, D (13) och 5, det vill säga en kedja BDA9D5 Rätt svar – 3.
Ett annat exempel på uppgift:
För att sända nummer över en brusig kanal används en paritetskod. Var och en av dess siffror skrivs i binär representation, med inledande nollor adderade till en längd av 4, och modulosumman av dess element adderas till den resulterande sekvensen 2 (till exempel om vi sänder 23 , då får vi sekvensen 0010 1 00110 ). Bestäm vilket nummer som sändes över kanalen i formuläret 0100011 ?
Lösning:
1) låt oss först ta reda på hur siffrorna i exemplet är kodade; det är uppenbart att enhetlig längdkod används; eftersom 2 tecken är kodade med 10 binära siffror (bitar) tilldelas 5 bitar för varje siffra, dvs. 2 → 00101 Och 3 → 00110
2) enligt villkoret är de första fyra bitarna i varje sekvens den binära koden för siffran, och den femte biten (paritetsbiten) används för verifiering och beräknas som "summa modulo två", det vill säga resten av att dividera summan av bitarna med 2; Sedan
2 = 00102, paritetsbit (0 + 0 + 1 + 0) mod 2 = 1
3 = 00112, paritetsbit (0 + 0 + 1 + 1) mod 2 = 0
3) men vi behöver inte paritetsbiten alls behövs inte, något annat är viktigt: den femte biten i varje femma kan kasseras!
4) dela upp den givna sekvensen i grupper om 5 bitar vardera:
01010, 10010, 01111, 00011.
5) kasta den femte (sista) biten i varje grupp: 0101, 1001, 0111, 0001.
Dessa är de binära koderna för de överförda numren: 01012 = 5, 10012 = 9, 01112 = 7, 00012 = 1.
6) sålunda sändes siffrorna 5, 9, 7, 1 eller numret 5971.
7) Svar: 2.
A9 Uppgifter för träning.
№ 69 – 71
69) Meddelanden som endast innehåller 4 bokstäver sänds över kommunikationskanalen: A, B, C, D. För att koda bokstäverna A, B, C används 5-bitars kodord: A - 10000, B - 00101, C - 01010. För detta har en uppsättning kodord följande egenskap: två valfria ord från uppsättningen skiljer sig i minst tre positioner. Denna egenskap är viktig för att dekryptera meddelanden i närvaro av störningar. Vilket av följande kodord kan användas för bokstaven G så att den angivna egenskapen gäller för alla fyra kodorden?
1) 0110 inget av ovanstående ord är lämpliga
70) (http://ege. *****) För att sända brusbeständiga meddelanden i ett alfabet som innehåller 16 olika tecken, används en enhetlig binär kod. Denna kod uppfyller följande egenskap: vilket kodord som helst innehåller ett jämnt antal ettor (möjligen inga). Vilken är den kortaste längden ett kodord kan ha?
71) Meddelanden som endast innehåller 5 bokstäver A, I, K, O, T sänds över kommunikationskanalen För att koda bokstäverna används en ojämn binär kod med följande kodord:
A-0, I-00, K-10, O-110, T-111.
Bland orden nedan, ange en vars kod bara kan avkodas på ett sätt. Om det finns flera sådana ord, ange det första i alfabetisk ordning.
1) KAA 2) HICCUP 3) CAT 4) inget av meddelandena är lämpliga
1. För att koda bokstäverna A, B, C, D bestämde de sig för att använda tvåsiffriga sekventiella binära tal (från 00 till 11). Om du kodar sekvensen av GBVA-tecken på detta sätt och skriver resultatet i hexadecimal kod får du:
1) 13DBCA16 3) D
2.
För 5 bokstäver i det latinska alfabetet ges deras binära koder (för vissa bokstäver - från två
bitar, för vissa - från tre). Dessa koder presenteras i tabellen:
Bestäm vilken uppsättning bokstäver som kodas av en binär sträng
1) baade 2) badde 3) bacde 4) bacdb
3.
För att koda ett meddelande som endast består av bokstäverna A, B, C, D och E, använd
binär kod med ojämn längd:
Vilket (endast ett!) av de fyra mottagna meddelandena sändes utan fel?
och kan avkodas:
4. För att sända ett meddelande över en kommunikationskanal som endast består av bokstäverna A, B, C, D, bestämde de sig för att använda en kod med ojämn längd: A=0, B=100, C=101. Hur ska bokstaven G kodas så att kodlängden blir minimal och det kodade meddelandet entydigt kan delas upp i bokstäver?
5. En svartvit bitmappsbild kodas rad för rad, med början i det övre vänstra hörnet och slutar i det nedre högra hörnet. Vid kodning representerar 1 svart och 0 representerar vit.
För kompakthetens skull skrevs resultatet i det oktala talsystemet. Välj rätt kodpost.1412
6. För att sända nummer över en brusig kanal används en paritetskod. Var och en av dess siffror skrivs i binär representation, med inledande nollor adderade till en längd av 4, och summan av dess element modulo 2 läggs till den resulterande sekvensen (om vi till exempel sänder 23 får vi en sekvens). Bestäm vilket nummer som sändes över kanalen i formuläret?
7.
För att koda bokstäverna O, Ch, B, A, K används binära koder med siffrorna 0, 1, 2, 3 respektive 4 (med bevarande av en obetydlig nolla i fallet med ensiffrig representation). Om du kodar en sekvens av tecken på detta sätt
Zucchini och skriv resultatet i hexadecimal kod får du:
1) 5434DA4 3) ABCD
8.
För att sända ett meddelande över en kommunikationskanal som endast består av bokstäverna A, B, C, D, bestämde de sig för att använda en kod med ojämn längd: A=01, B=1, B=001. Hur man kodar
bokstaven G, så att kodens längd är minimal och en entydig uppdelning av det kodade meddelandet i bokstäver tillåts?
9. För att sända ett meddelande över en kommunikationskanal som endast består av bokstäverna A, B, C, D, bestämde de sig för att använda en kod med ojämn längd: A=0, B=100, C=110. Hur ska bokstaven G kodas så att kodlängden blir minimal och det kodade meddelandet entydigt kan delas upp i bokstäver?
Driften av elektronisk datorteknik för databehandling har blivit ett viktigt steg i processen att förbättra lednings- och planeringssystemen. Men denna metod för att samla in och bearbeta information skiljer sig något från den vanliga, och kräver därför omvandling till ett system av symboler som är förståeligt för en dator.
Vad är informationskodning?
Datakodning är ett obligatoriskt steg i processen att samla in och bearbeta information.
Som regel betyder en kod en kombination av tecken som motsvarar den överförda informationen eller några av dess kvalitativa egenskaper. Och kodning är processen att sammanställa en krypterad kombination i form av en lista med förkortningar eller specialtecken som fullt ut förmedlar den ursprungliga innebörden av meddelandet. Kodning kallas också ibland för kryptering, men det är värt att veta att det senare förfarandet innebär att data skyddas från hackning och läsning av tredje part.
Syftet med kodning är att presentera information i ett bekvämt och kortfattat format för att förenkla dess överföring och bearbetning på datorenheter. Datorer fungerar bara med information av en viss form, så det är så viktigt att inte glömma detta för att undvika problem. Begreppet databehandling innefattar sökning, sortering och ordning, och kodning sker vid inmatning av information i form av en kod.
Vad är informationsavkodning?
Frågan om vad kodning och avkodning är kan uppstå för en PC-användare av olika anledningar, men i alla fall är det viktigt att förmedla den korrekta informationen som gör det möjligt för användaren att framgångsrikt gå vidare i informationsteknologins flöde. Som du förstår erhålls utdatakoden efter databehandlingsprocessen. Om ett sådant fragment dekrypteras bildas den ursprungliga informationen. Det vill säga avkodning är den omvända processen för kryptering.
Om data under kodningen tar formen av symboliska signaler som helt motsvarar det överförda objektet, tas den överförda informationen eller några av dess egenskaper bort från koden under avkodningen.
Det kan finnas flera mottagare av krypterade meddelanden, men det är mycket viktigt att informationen hamnar i deras händer och inte tidigare lämnas ut av tredje part. Därför är det värt att studera processerna för kodning och avkodning av information. De hjälper till att utbyta konfidentiell information mellan en grupp samtalspartners.
Kodning och avkodning av textinformation
När du trycker på en tangentbordsknapp får datorn en signal i form av ett binärt nummer, vars avkodning finns i kodtabellen - den interna representationen av tecken i datorn. ASCII-tabellen anses vara standard över hela världen.
Det räcker dock inte att veta vad kodning och avkodning är, du behöver också förstå hur data finns i en dator. Till exempel, för att lagra ett tecken i en binär kod, allokerar en elektronisk dator 1 byte, det vill säga 8 bitar. Den här cellen kan bara ta två värden: 0 och 1. Det visar sig att en byte låter dig kryptera 256 olika tecken, eftersom detta är antalet kombinationer som kan göras. Dessa kombinationer är nyckeldelen av ASCII-tabellen. Till exempel är bokstaven S kodad som 01010011. När du trycker på den på tangentbordet kodas och avkodas data och vi får det förväntade resultatet på skärmen.
Hälften av ASCII-standardtabellen innehåller koder för siffror, kontrolltecken och latinska bokstäver. Den andra delen är fylld med nationella tecken, pseudografiska tecken och symboler som inte är relaterade till matematik. Det är tydligt att denna del av tabellen kommer att skilja sig åt i olika länder. Siffror när de anges omvandlas också till binär beräkning enligt standardsammanfattningen.
Kodning av nummer
En liknande metod för att koda bildpunkter används också i tryckeribranschen. Endast här är det vanligt att använda en fjärde färg - svart. Av denna anledning förkortas utskriftskonverteringssystemet CMYK. Detta system använder så många som trettiotvå binära bitar för att representera bilder.
Metoder för att koda och avkoda information involverar användning av olika teknologier, beroende på typen av indata. Till exempel kallas grafiska bilder i sexton-bitars binära koder High Color. Denna teknik gör det möjligt att överföra så många som tvåhundrafemtiosex nyanser till skärmen. Genom att minska antalet binära bitar som används för att kryptera grafiska pixlar, minskar du automatiskt mängden tillfälligt lagringsutrymme som krävs. Denna metod för datakodning kallas vanligtvis index.
Kodning av ljudinformation
Nu när vi har tittat på vad kodning och avkodning är, och de metoder som ligger till grund för denna process, är det värt att uppehålla sig vid frågan om kodning av ljuddata.
Ljudinformation kan representeras i form av elementära enheter och pauser mellan varje par av dem. Varje signal omvandlas och lagras i datorns minne. Ljud matas ut med hjälp av krypterade kombinationer lagrade i PC-minnet.
När det gäller mänskligt tal är det mycket svårare att koda, eftersom det har en mängd olika nyanser, och datorn måste jämföra varje fras med en standard som tidigare lagrats i dess minne. Igenkänning sker endast när det talade ordet finns i ordboken.
Kodning av information i binär kod
Det finns olika metoder för att implementera en sådan procedur som kodning av numerisk, textuell och grafisk information. Dataavkodning sker vanligtvis med omvänd teknologi.
Vid kodning av siffror tar den till och med hänsyn till syftet med vilket numret matades in i systemet: för aritmetiska beräkningar eller helt enkelt för utdata. All data kodad i det binära systemet krypteras med ettor och nollor. Dessa symboler kallas även bitar. Denna kodningsmetod är den mest populära, eftersom den är den lättaste att organisera tekniskt: närvaron av en signal är 1, frånvaron är 0. Binär kryptering har bara en nackdel - längden på symbolkombinationerna. Men ur teknisk synvinkel är det lättare att använda ett gäng enkla, liknande komponenter än ett litet antal mer komplexa.
Fördelar med binär kodning
- Denna form av informationspresentation lämpar sig för olika typer av information.
- Inga fel uppstår under dataöverföring.
- Det är mycket lättare för en PC att bearbeta data kodad på detta sätt.
- Kräver enheter med dubbla tillstånd.
Nackdelar med binär kodning
- Stor längd på koder, vilket saktar ner deras bearbetning något.
- Svårigheten att uppfatta binära kombinationer för en person utan särskild utbildning eller träning.
Slutsats
Efter att ha läst den här artikeln kunde du ta reda på vad kodning och avkodning är och vad det används till. Man kan dra slutsatsen att de datatransformationstekniker som används helt och hållet beror på typen av information. Det kan inte bara vara text, utan även siffror, bilder och ljud.
Kodning av olika information gör att du kan förena formen för dess presentation, det vill säga göra den enhetlig, vilket avsevärt påskyndar processerna för bearbetning och automatisering av data för vidare användning.
Elektroniska datorer använder oftast principerna för standard binär kodning, som omvandlar den ursprungliga formen av informationsrepresentation till ett format som är mer bekvämt för lagring och vidare bearbetning. Vid avkodning sker alla processer i omvänd ordning.
Men du kan inte förmedla det till alla med din röst. Därför, sedan urminnes tider, var ögonblicket för kodning av data viktigt så att det kunde läsas av dem som det var avsett för. Efter hand blev deras kryptering också aktuell. Det var nödvändigt att lägga in information i meddelandet som var begriplig för andra och som inte avslöjade innebörden för främlingar. Vi kommer att prata om allt detta, ta reda på vad kodning och avkodning är.
Förstå terminologin
Det finns ingen väg utan detta. När vi talar om kodad text betyder det att en annan uppsättning tecken har associerats med den. Detta kan användas för att öka tillförlitligheten eller av den enkla anledningen att kanalen bara kan använda ett begränsat antal symboler. Till exempel är den binära koden som moderna datorer körs på byggd på ettor och nollor.
Information kan kodas in i vissa symboler för att spara den. Som ett exempel kan vi nämna resultaten av tester som innehåller indikatorer på människokroppen. Men den mest populära frågan är: "Vad är kodning och avkodning inom datavetenskap?" Vi kommer att leta efter svaret på det.
Om meningen
Tidigare spelade processen att koda och avkoda information en hjälproll och betraktades inte som en separat gren av matematiken. Men med tillkomsten av elektroniska datorer förändrades situationen avsevärt. Numera är kodning en central fråga när man löser en lång rad praktiska problem inom programmering och genomsyrar därför all informationsteknologi. Så, med dess hjälp:
- Informationen är skyddad från obehörig åtkomst.
- Ger brusimmunitet vid överföring av data över kommunikationskanaler.
- Information av godtycklig natur (grafik, text, siffror) presenteras i datorns minne.
- Databasinnehållet komprimeras.
Om alfabetet
När man pratar om vad kodning och avkodning är är det svårt att bortse från grunden för det hela. Nämligen alfabetet. Det finns två typer - initial och kod. Den första innehåller initial information. Med kodad menar vi modifierad data, som, om den ges nyckeln, ändå kan överföra det krypterade innehållet till oss. Inom datavetenskap görs detta med hjälp av binär kod, som bygger på ett alfabet bestående av noll och ett.
Låt oss titta på ett litet exempel. Låt oss säga att vi har två alfabet (A och B) som består av ett ändligt antal tecken. Låt oss säga att de ser ut så här: A = (A0, A1, A2...A33), B = (B0, B1, B3...B34). Beståndsdelarna i alfabetet är bokstäver. Medan deras ordnade uppsättning kallas ett ord. Den har en viss längd. Den första bokstaven i ett ord kallas början (prefix), medan den sista bokstaven kallas slutet (postfix). Det kan finnas olika regler för att bygga strukturer. Till exempel kräver vissa informationskodningssystem ett mellanrum mellan orden, medan andra klarar sig utan det. I allmänhet är alfabetet nödvändigt för att bygga ett universellt system för att visa information, lagra, bearbeta och överföra den. I detta fall tillhandahålls en viss överensstämmelse mellan olika signaler och meddelandeelementen som är krypterade i dem.
Arbeta med data
När information omvandlas till sin ursprungliga form kallas processen som sker avkodning. Det måste utföras på all data som har krypterats. I det här fallet används den så kallade inversa mappningen (bijection). Låt oss överväga situationen med ett binärt system. Alla hennes kodord är lika långa. Därför kallas koden uniform (block). I detta fall är kodningsfunktionen en viss substitution. Vi kan ta ovanstående alfabetsystem som exempel. Många elementära koder används för att beteckna vissa sekvenser.
Låt oss säga att vi har A0 = (A, B, C, D) och B0 = (1, 0). Hur kan detta representeras för en dator? Och med denna sekvens: A = 00, B = 01, C = 10, D = 11. Som du kan se har varje tecken en specifik kodning. Referensinformation om kodningsalfabetet matas in i datorutrustningen och den börjar vänta på inkommande signaler. En nolla kommer, följt av en annan - ja, det betyder bokstaven A. Om vi drar paralleller med att skriva ett ord i en textredigerare, bör det noteras att inte bara en bokstav kommer att överföras, utan också motsvarande reaktion på den kommer att lanseras. Till exempel kommer en viss sekvens av monitorns lysdioder att tändas och visar alla inmatade tecken.
Arbetsuppgifter
På tal om exempel på kodnings- och avkodningsinformation, bör det noteras att det aktuella systemet inte är en-till-en. Till exempel kan bokstaven A motsvara kombinationen inte bara 00, utan också 11, 10 eller 01. Men det bör beaktas att det bara kan finnas en av dem. Det vill säga att endast en viss symbol tilldelas kombinationen. Om ett kodningsschema innebär att ett ord delas in i elementära komponenter, kallas det separerbart. I de fall där en bokstav inte fungerar som början på en annan, är detta prefixmetoden. Detta gäller hård- och mjukvaruproblem. Arkitekturen har också ett visst inflytande på kodning, men på grund av det stora antalet implementeringsalternativ är det ganska problematiskt att överväga det.
Kodning bokstav för bokstav
Detta är det enklaste tillvägagångssättet. Om vi pratar om informationskodningsspråk, så är detta kanske det mest populära alternativet. I en begränsad version diskuterades det ovan. Låt oss ta reda på hur koden ser ut utan avgränsare. Låt oss säga att vi har ett alfabet (original) där alla ryska bokstäver är placerade. Decimalsiffror används för kodning. Här är A = 1 och Z = 33. Således kan sekvensen av bokstäver AYАА uttryckas som 133331. Om det finns en önskan att göra alfabetet enhetligt, är det nödvändigt att göra vissa ändringar. Så för de första nio bokstäverna måste du lägga till noll. Och exemplet vi ansåg AYAA förvandlas till 01333301.
Ojämn kodning
Det tidigare diskuterade alternativet anses vara bekvämt. Men i vissa fall är det smartare att satsa på ojämna koder. Detta är vettigt när olika bokstäver förekommer med olika frekvenser i källtexten. Därför är det vettigt att koda vanligare tecken med korta notationer och sällsynta tecken med långa notationer. Låt oss bygga ett binärt träd från bokstäver i det ryska alfabetet. Och som ett tillägg, låt oss ta specialtecken. Bokstäverna används oftast, så vi börjar med dem: A - 0, B - 1, C - 10, D - 11 och så vidare. Och först efter dem kommer frågetecken, procentsatser, kolon och andra att användas. Även om kanske kommatecken och punkter fortfarande bör sättas på första plats.
Om Fanos skick
Teoremet säger att vilken kod som helst (prefix och enhetlig) tillåter möjligheten till entydig kodning. Låt oss säga att vi använder det tidigare diskuterade exemplet med 01333301. Vi börjar röra oss åt höger. 0 ger oss ingenting. Men 01 tillåter oss att identifiera bokstaven A. Låt oss ändra den initiala koden något och presentera den som 01 333301. Därefter väljer vi det första Z, det andra och ett annat A. Som ett resultat har vi 01 33 33 01. Även om initialt koden slogs samman, nu kan vi enkelt avkoda den, eftersom vi vet vad som finns i den. Nämligen - A Z I A. Observera att det alltid dechiffreras entydigt, och det finns inga tolkningar inom ramen för det antagna systemet, tack vare vilket det är möjligt att säkerställa hög tillförlitlighet för den överförda informationen. Men hur fungerar datorer?
Drift av elektroniska datorer
Kodning och avkodning av datorsignaler bygger på användningen av så kallade låga och höga signaler, som i den logiska dimensionen motsvarar noll och ett. Vad betyder det? Låt oss säga att vi har en mikrokontroller. Om en lågspänning på 1,5 V tas emot vid en av dess ingångar, anses det att ett logiskt nollvärde har överförts. Men om 5 V sänds, kommer en enhet att skrivas till motsvarande minnescell. I detta fall är det nödvändigt att uppnå enighet mellan informationskällan och kommunikationskanalen. I allmänhet, när du skapar elektronik, är det nödvändigt att ta hänsyn till ett stort antal olika punkter. Dessa inkluderar energikrav, typen av information som överförs (diskret eller kontinuerlig) och mycket mer. Samtidigt måste data hela tiden omvandlas på ett sådant sätt att den kan överföras över kommunikationskanaler. Således, i fallet med binär teknologi, representeras signaler i form av spänning som appliceras på ingången av transistorer eller andra komponenter. Under avkodningen översätter data meddelandet till en form som mottagaren kan förstå.
Minimal redundans
I praktiken har det visat sig att det är oerhört viktigt att meddelandekoden har en minimilängd. Inledningsvis kan det tyckas, vilken skillnad gör det - sex, åtta eller sexton bitar används för kodning? Men skillnaderna är obetydliga om ett ord används. Tänk om miljarder? Lyckligtvis kan du anpassa den alfabetiska kodningen till alla krav som ställs. Men om ingenting är känt om uppsättningen är det i det här fallet ganska svårt att formulera ett optimeringsproblem. Men i praktiken är det som regel fortfarande möjligt att få ytterligare information. Låt oss titta på ett litet exempel. Låt oss säga att vi har ett budskap som presenteras på naturligt språk. Men den är krypterad och vi kan inte läsa den. Vad kommer att hjälpa oss i dekrypteringsuppgiften? Ett av de möjliga alternativen är ett papper på vilket sannolikheten för att bokstäver dyker upp fördelas. Tack vare detta blir konstruktionen av en optimal kod vad gäller avkodning möjlig med hjälp av en exakt matematisk formulering och en rigorös lösning.
Låt oss titta på ett exempel
Låt oss anta att vi har ett visst separerbart alfabetiskt kodningsschema. Då kommer alla derivator som representerar en ordnad mängd också att ha denna egenskap. Dessutom, om längden på de elementära koderna är lika, så påverkar deras omarrangemang inte längden på hela meddelandet. Men om storleken på den överförda informationen direkt beror på sekvensen av bokstäver, betyder det att komponenter av olika längd användes. Dessutom, om det finns ett specifikt meddelande och ett schema för att koda det, är det möjligt att välja en lösning på problemet när dess längd är minimal. Hur uppnår man detta? Låt oss titta på ett tillvägagångssätt som använder en algoritm för att tilldela elementära koder, vilket gör att vi effektivt kan närma oss lösningen av effektivitetsproblemet:
- Bokstäverna ska sorteras i fallande ordning efter kvantitativ förekomst.
- Det är nödvändigt att placera de elementära koderna i ökande ordning efter deras längd.
- Och slutligen är det nödvändigt att placera komponenterna i optimal ordning så att de vanligaste symbolerna tar minsta möjliga plats.
Sammantaget är systemet enkelt. Om du arbetar med små mängder data. Men med moderna datorer är detta ganska problematiskt att implementera på grund av den betydande mängden information.
Slutsats
Så vi tittade på vad ett system för kodning och avkodning av information är, vad det kan vara, vad som för närvarande finns inom datavetenskap, liksom många andra frågor. Men du bör ändå förstå att det här ämnet är extremt omfattande; en artikel räcker inte för detta. Som en fortsättning på ämnet kan vi överväga datakryptering, kryptografi, ändra visningen av information i olika elektronik, nivåer av dess bearbetning och många andra punkter. Men området för datavetenskap anses med rätta vara ett av de mest komplexa, så att lära sig allt detta kommer inte att vara möjligt snabbt. Dessutom är teoretiska kunskaper här inte lika med praktiska färdigheter. Det senare ger nämligen resultat av hög kvalitet.
