Nederlands
Menu

Basis van informatietheorie en codering

Leer met meerkeuzevragen, voornamelijk rekenvragen, over informatie-inhoud en entropie, wederzijdse informatie, redundantie, codes met vaste en met variabele lengte, prefixcodes en de ongelijkheid van Kraft, de gemiddelde codelengte en het rendement van Huffman-codes, run-length encoding, de LZ77-methode, verliesvrije compressie en compressie met verlies, pariteit en verticale en horizontale pariteit, checksums, de berekening van een CRC, de Hamming-afstand en het vermogen om fouten te detecteren en te corrigeren, Hamming-codes en SECDED, de coderatio, interleaving, ARQ en FEC, de capaciteit van het binair symmetrisch kanaal, de kanaalcoderingsstelling en de omzetting van Gray-code.

Oefen 10 vragenWillekeurige vragen uit dit onderwerp · ongeveer 5 minuten Dit onderwerp oefenenAlle vragen over dit onderwerp in willekeurige volgorde Zwakke vragenAlleen de laatst fout beantwoorde vragen opnieuw oefenen

Basis van informatietheorie en codering: kernpunten

„Hoeveel bits is deze informatie waard?” „Hoe klein kunnen deze gegevens worden gemaakt?” „Hoe kunnen bits die door ruis zijn verminkt, worden gevonden en hersteld?” Zulke vragen worden beantwoord door de informatietheorie en de codetheorie, die door Shannon zijn gegrondvest. Ze worden overal in computers en communicatie gebruikt: bij het comprimeren van bestanden, voor ECC in geheugens, voor foutcorrectie op communicatiekanalen, voor CRC's in opslagapparaten en meer.

Dit onderwerp controleert met berekeningen de informatie-inhoud −log₂ p en de entropie, de voorwaarde waaronder de entropie maximaal is, voorwaardelijke entropie en wederzijdse informatie, redundantie en het aantal bits dat nodig is om dingen van elkaar te onderscheiden. Daarna komen codes met vaste en met variabele lengte aan bod, prefixcodes en de ongelijkheid van Kraft, het opbouwen van een Huffman-code en haar gemiddelde codelengte, het rendement vergeleken met de entropie, het effect van symbolen samen coderen, run-length encoding en de LZ77-methode, en de keuze tussen verliesvrije compressie en compressie met verlies. Het tweede deel behandelt pariteit en verticale en horizontale pariteit, de zwakte van checksums, het berekenen van de controlebits van een CRC en het detecteren van burstfouten, de Hamming-afstand en het aantal bitfouten dat kan worden gedetecteerd en gecorrigeerd, het lokaliseren van een fout met het syndroom van de Hamming-code (7, 4), het aantal controlebits van SECDED, de coderatio, interleaving, ARQ en FEC, en de capaciteit van het binair symmetrisch kanaal en de kanaalcoderingsstelling, en sluit af met de omzetting van Gray-code. Dit helpt ook bij de basistheorie (informatietheorie en communicatietheorie) van IT-certificeringsexamens. De waarden in de rekenvragen, ook die van de foute antwoorden en de Huffman-bomen, zijn gecontroleerd door ze in Python te berekenen. Binaire getallen en drijvende komma worden behandeld in „Computerarithmetiek”, het berekenen van een pariteitsbit en de eigenschappen van Gray-code in „Logische schakelingen”, het omzetten van binair naar Gray-code in „Timinganalyse en CDC”, de kans op fouten die pariteit mist in „Kansrekening, statistiek en wachtrijen”, de kanaalcapaciteit volgens de stelling van Shannon-Hartley in „Basis van draadloze communicatie”, ECC voor geheugen in „DRAM”, 8b/10b-codering en de CRC van PCI Express in „Interfaces en busstandaarden”, Base64 en gzip in „Basis van webtechnologie”, kruisentropie in „Basis van machine learning”, en hashes en cryptografie in „Basis van informatiebeveiliging”.

Alle vragen over Basis van informatietheorie en codering (40)
  1. Stel dat de informatie-inhoud die men krijgt wanneer men hoort dat een gebeurtenis met kans p heeft plaatsgevonden, −log₂ p bit is. Wat is de informatie-inhoud die men krijgt wanneer men hoort dat een gebeurtenis met kans 1/8 heeft plaatsgevonden?
  2. Welke uitspraak over de eigenschappen van de informatie-inhoud (−log₂ p wanneer men hoort dat een gebeurtenis met kans p heeft plaatsgevonden) is juist?
  3. Een bron zendt de symbolen A, B, C en D onafhankelijk van elkaar uit met kansen 1/2, 1/4, 1/8 en 1/8. Wat is de entropie (de gemiddelde informatie-inhoud per symbool) van deze bron?
  4. Welke combinatie van de maximale entropie van een bron die 8 soorten symbolen uitzendt en de voorwaarde waaronder dat maximum wordt bereikt, is juist?
  5. Een binaire bron zendt onafhankelijk 0 uit met kans 0,9 en 1 met kans 0,1. Neem log₂ 0,9 ≈ −0,152 en log₂ 0,1 ≈ −3,32. Welke waarde ligt het dichtst bij de entropie van deze bron?
  6. Een bron die 8 soorten symbolen uitzendt, heeft een entropie van 2,4 bit. Als de redundantie wordt gedefinieerd als 1 − (entropie ÷ maximale entropie), wat is dan de redundantie van deze bron?
  7. Welke beschrijving van de voorwaardelijke entropie H(X|Y) en de wederzijdse informatie I(X;Y) van twee stochastische variabelen X en Y is juist?
  8. Twee stochastische variabelen X (waarde 0 of 1) en Y (waarde a, b of c) hebben de gezamenlijke kansen P(0, a) = P(0, b) = P(1, b) = P(1, c) = 1/4, en elke andere combinatie heeft kans 0. Wat is de wederzijdse informatie I(X;Y)?
  9. De 36 tekens die bestaan uit de 26 hoofdletters en de 10 cijfers moeten worden onderscheiden met bitreeksen die allemaal even lang zijn (een code met vaste lengte). Wat is het minimale aantal bits dat per teken nodig is?
  10. Welke beschrijving van een code met variabele lengte, vergeleken met een code met vaste lengte, is juist?
  11. Welke van de volgende verzamelingen codewoorden voor vier symbolen is een prefixcode (een code waarin geen enkel codewoord het begin van een ander codewoord is)?
  12. Een prefixcode kent de codewoorden A = 0, B = 10, C = 110 en D = 111 toe aan de symbolen A, B, C en D. Wat is het resultaat als de bitreeks 110100111 vanaf het begin wordt gedecodeerd?
  13. Aan de vier symbolen A tot D moeten codewoorden met de volgende lengtes (aantallen bits) worden toegekend om een binaire prefixcode te maken. Met welke combinatie van codelengtes is dat mogelijk?
  14. Er wordt een binaire prefixcode gemaakt, en de codewoorden 00 en 01 van lengte 2 zijn al in gebruik. Hoeveel codewoorden van lengte 3 kunnen er maximaal worden toegevoegd zonder de voorwaarde van een prefixcode te schenden?
  15. Een bron zendt de symbolen A, B, C en D onafhankelijk uit met kansen 0,4; 0,3; 0,2 en 0,1, en wordt gecodeerd met een Huffman-code. Wat is de gemiddelde codelengte per symbool?
  16. Een bron zendt de symbolen A tot E onafhankelijk uit met kansen 0,3; 0,25; 0,2; 0,15 en 0,1, en wordt gecodeerd met een Huffman-code. De codewoorden kunnen veranderen afhankelijk van welke van twee gelijke kansen eerst wordt gekozen, maar de gemiddelde codelengte niet. Wat is de gemiddelde codelengte per symbool?
  17. Een bron zendt de symbolen A, B en C onafhankelijk uit met kansen 0,6; 0,3 en 0,1, en haar entropie is ongeveer 1,30 bit. Welke waarde ligt het dichtst bij het rendement (entropie ÷ gemiddelde codelengte) wanneer deze bron met een Huffman-code wordt gecodeerd?
  18. Een binaire bron zendt onafhankelijk 0 uit met kans 0,8 en 1 met kans 0,2. De symbolen worden per twee genomen, elk van de vier paren 00, 01, 10 en 11 wordt als één symbool behandeld, en ze worden gecodeerd met een Huffman-code. Wat is de gemiddelde codelengte per oorspronkelijk symbool?
  19. Welke beschrijving van het verband tussen verliesvrije compressie en de entropie van een bron is juist?
  20. De tekenreeks van 40 tekens AAAAAAAAAAAABBBBCCCCCCCCCCCCCCCCCCCCDDDD (12 keer A, 4 keer B, 20 keer C en 4 keer D) wordt gecomprimeerd met run-length encoding, die elke reeks van hetzelfde opeenvolgende teken weergeeft als een paar „teken (1 byte) en aantal (1 byte)”. De oorspronkelijke tekenreeks gebruikt 1 byte per teken. Als de compressieverhouding wordt gedefinieerd als „grootte na compressie ÷ grootte voor compressie”, wat is dan de compressieverhouding?
  21. Welke gegevens worden met run-length encoding waarschijnlijk het kleinst?
  22. Welke beschrijving van het idee achter de LZ77-methode, die in ZIP, gzip en vergelijkbare tools wordt gebruikt, is juist?
  23. Gegevens die met de LZ77-methode zijn gecomprimeerd, moeten worden hersteld. De gegevens bestaan in deze volgorde uit „teken A”, „teken B” en „(afstand 2, lengte 5)”. (afstand d, lengte L) betekent dat de bewerking „kopieer het teken dat d tekens vóór het einde van de herstelde tekenreeks staat naar het einde” L keer wordt herhaald, één teken per keer. Wat is de herstelde tekenreeks?
  24. Bij welk van de volgende gevallen moet bij het comprimeren van gegevens verliesvrije compressie worden gebruikt in plaats van compressie met verlies?
  25. Aan een bitreeks van gegevens wordt één even pariteitsbit toegevoegd zodat het aantal enen even is, en de ontvanger controleert het aantal enen. Welke beschrijving van deze controle is juist?
  26. Vier rijen van 4 databits werden verzonden met aan het rechtereinde van elke rij een even pariteitsbit voor die rij, en tot slot een rij met de even pariteitsbits van de kolommen (verticale en horizontale pariteit). De ontvangen bits waren rij 1: 1011 1, rij 2: 0100 0, rij 3: 1100 0, rij 4: 0101 0 en pariteitsrij: 0100 (de meest rechtse bit van elke rij is de pariteit van die rij). Als precies één bit fout is, op welke positie zit die bit?
  27. Gegevens worden byte voor byte opgeteld, en de laagste 8 bits van de som worden als controlewaarde (checksum) meegestuurd. Welke van de volgende fouten kan deze controle niet detecteren?
  28. Aan de gegevens 1101 moeten de 3 controlebits worden toegevoegd van een CRC met het generatorpolynoom x³ + x + 1 (bitreeks 1011). De controlebits zijn de rest van de deling van 1101000, de gegevens gevolgd door drie nullen, door 1011, waarbij in de deling de exclusieve OF in plaats van aftrekken wordt gebruikt. Wat zijn de controlebits?
  29. Welke beschrijving van een CRC waarvan het generatorpolynoom graad r (r controlebits) en een constante term 1 heeft, is juist?
  30. Wat is de Hamming-afstand tussen de twee codewoorden van 7 bits 1011010 en 0110011?
  31. De minimale Hamming-afstand van een code (de kleinste Hamming-afstand tussen twee willekeurige codewoorden) is 5. Beschouw het gebruik ervan alleen voor foutdetectie of alleen voor foutcorrectie. Welke combinatie van het aantal bitfouten dat altijd kan worden gedetecteerd en het aantal bitfouten dat altijd kan worden gecorrigeerd, is juist?
  32. Welke combinatie van de minimale Hamming-afstand van de code die bestaat uit de vier codewoorden 00000, 01011, 10101 en 11110, en het aantal bitfouten dat ze altijd kan corrigeren, is juist?
  33. Welke waarde ligt het dichtst bij de coderatio van de Hamming-code (7, 4), die 3 controlebits toevoegt aan 4 databits om een codewoord van 7 bits te vormen?
  34. In een Hamming-code (7, 4) worden de zeven bits van links af genummerd van 1 tot 7, en de bits 1, 2 en 4 zijn controlebits. Ze worden zo ingesteld dat het aantal enen even is in de bits 1, 3, 5 en 7 (controle 1), in de bits 2, 3, 6 en 7 (controle 2) en in de bits 4, 5, 6 en 7 (controle 4). Als het ontvangen woord 0110001 een fout van 1 bit bevat, welke bit is dan fout?
  35. Aan 32 databits wordt een SECDED-code toegevoegd, die fouten van 1 bit corrigeert en fouten van 2 bits detecteert. Het aantal controlebits r van een Hamming-code is de kleinste waarde die voldoet aan 2^r ≥ aantal databits + r + 1, en SECDED voegt daar 1 bit totale pariteit aan toe. Hoeveel controlebits zijn er nodig?
  36. Vijf codewoorden van de Hamming-code (7, 4) worden naast elkaar gezet en verzonden in de volgorde: bit 1 van elk van de vijf codewoorden, dan bit 2 van elk, enzovoort (interleaving met diepte 5). De ontvanger herstelt de oorspronkelijke volgorde en corrigeert daarna in elk codewoord een fout van 1 bit. Wat is de maximale lengte van een burstfout, geconcentreerd in opeenvolgende bits, die altijd kan worden gecorrigeerd?
  37. Welke beschrijving van ARQ (automatic repeat request) en FEC (forward error correction), methoden om fouten in communicatie op te vangen, is juist?
  38. In een binair symmetrisch kanaal worden 0 en 1 verzonden, en elke bit slaat onafhankelijk om met kans 0,1. Met de binaire entropie H(p) = −p log₂ p − (1 − p) log₂(1 − p) geldt H(0,1) ≈ 0,469. Welke waarde ligt het dichtst bij de kanaalcapaciteit van dit kanaal per overdracht?
  39. Welke uitspraak geeft de inhoud van de kanaalcoderingsstelling van Shannon juist weer?
  40. Om een Gray-code om te zetten in een gewoon binair getal wordt de meest significante bit ongewijzigd overgenomen, en wordt elke lagere bit gevonden als de exclusieve OF van de binaire bit die al op de positie één hoger is gevonden en de bit van de Gray-code op dezelfde positie. Wat is de 4-bits Gray-code 1101, omgezet naar een binair getal?

Andere onderwerpen in Computersystemen