Extra

Extra#

Binair optellen#

Op de basisschool heb je vast geleerd hoe je grootte getallen bij elkaar kan optellen door ze onder elkaar te zetten.

\[\begin{split} \begin{array}{r} 1\phantom{0}\\ 529\\ +\;\phantom{0}742\\ \hline 1271 \end{array} \end{split}\]

Zodra je boven de 10 komt, zet je de eenheden onder de streep en onhoud je de tientallen door deze boven de som te zetten. 9+2 = 11, dus 1 onder de streep en 1 onthouden

We kunnen hetzelfde doe als we binaire getallen bij elkaar optellen.

\[\begin{split} \begin{array}{r} 11\phantom{000}\\ 101101\\ +\;\phantom{00}1110\\ \hline 111011 \end{array} \end{split}\]

0 + 0 = 0
1 + 0 = 1
1 + 1 = 10
1 + 1 + 1 = 11

Als we 1 + 1 bij elkaar optellen, krijgen we 10 (binair) We schrijven de eenheden onder de lijn, dus 0 en onthouden de tweetallen, in dit geval 1.

Functie 5: add_b(s, t)#

In de basis opgaven zag je een manier om twee binaire getallen op te tellen: zet ze eerst om naar grondtal 10, tel deze getallen op en zet vervolgens de uitkomst weer om naar een binaire string.

Bij deze opgave zal je echter een andere, meer directe, methode implementeren voor het optellen van twee binaire getallen, met behulp van de “basisschool” methode:

  101110
  100111
--------

Dit ziet er na optelling als volgt uit:

   111
  101110
  100111
--------
 1010101

Je ziet hier de “carry” bits op de eerste regel.

Schrijf voor dit probleem een Python functie add_b(s, t) die twee strings als argument accepteert. Deze strings stellen binaire getallen voor.

De functie add_b moet een nieuwe string teruggeven die de som van de twee argumenten voorstelt.

De som moet berekend worden met het “basisschool” binaire optelalgoritme, zoals hierboven is besproken, en niet met basisconversies (door grondtallen om te zetten). Dat wil zeggen dat de optelling puur syntactisch zal moeten zijn: je gebruikt de opteloperator + voor getallen van Python niet.

Hier zijn een paar voorbeelden:

In [1]: add_b("11100", "11110")
Out[1]: '111010'

In [2]: add_b("10101", "10101")
Out[2]: '101010'

In [3]: add_b("11", "1")
Out[3]: '100'

In [4]: add_b("11", "100")
Out[4]: '111'

En hier een aantal tests:

assert add_b("11", "100") == "111"
assert add_b("11100", "11110") == "111010"
assert add_b("110", "11") == "1001"
assert add_b("110101010", "11111111") == "1010101001"
assert add_b("1", "1") == "10"

Beeldcompressie#

Tot nu toe hebben we onderzocht hoe getallen in binaire vorm worden weergegeven, maar in dit probleem onderzoeken we de weergave van beelden met behulp van 0’s en 1’s.

Voor dit deel schrijf je twee functies, compress(s) en uncompress(c), samen met een of meer hulpfuncties.

Om te beginnen bekijken we alleen 8 bij 8 zwart-wit afbeeldingen zoals de afbeelding hieronder:

Dambord

Elke cel in de afbeelding wordt een “pixel” genoemd. Een witte pixel wordt voorgesteld door het cijfer 0 en een zwarte pixel door het cijfer 1. Het eerste cijfer staat voor de pixel in de linkerbovenhoek van de afbeelding. Het volgende cijfer staat voor de pixel in de bovenste rij en de tweede kolom. Het achtste bit (cijfer) staat voor de pixel aan de rechterzijde van de bovenste rij. Het volgende bit staat voor de meest linkse pixel in de tweede rij, enzovoort. Daarom wordt de bovenstaande afbeelding weergegeven door de volgende binaire string met lengte 64:

"1010101001010101101010100101010110101010010101011010101001010101"

Een andere manier om deze string voor te stellen in Python is

"1010101001010101" * 4

Achtergrond#

Maar wat nu? Stel je voor, je bent ingehuurd door HASA (“Hanze Air and Space Administration”). HASA heeft een satelliet die 8 bij 8 zwart-wit beelden neemt en deze terugstuurt naar de aarde als binaire strings van 64 bits zoals hierboven beschreven. Om kostbare energie te besparen die nodig is voor het verzenden van gegevens, wil HASA de verzonden beelden “comprimeren” in een formaat dat zo weinig mogelijk bits gebruikt. Een manier om dit te doen is door gebruik te maken van het “run-length” coderingsalgoritme.

Stel je voor dat we een beeld hebben dat er als volgt uitziet:

Strepen

Met behulp van onze standaard opeenvolging van 64 bits wordt dit beeld weergegeven door een binaire reeks die begint met 16 opeenvolgende 0’en (voor twee rijen witte pixels) gevolgd door 16 opeenvolgende 1’en (voor twee rijen zwarte pixels) gevolgd door 16 opeenvolgende 0’en gevolgd door 16 opeenvolgende 1’en.

Run-length codering (die overigens ook wordt gebruikt als onderdeel van het JPEG beeldcompressie-algoritme) stelt voor om dit beeld weer te geven met de code “16 wit, 16 zwart, 16 wit, 16 zwart”. Dat is een veel kortere beschrijving dan het opsommen van de reeks van 64 pixels “wit, wit, wit, wit, …”.

Run-length encoding#

In het algemeen stelt onze run-length codering een beeld voor met een sequentie (een rij, of “run-length sequence” genoemd) van 8-bits bytes:

  • Het eerste bit van elke byte vertegenwoordigt het bit dat als volgende in het beeld zal verschijnen, ofwel 0 ofwel 1.

  • De laatste zeven bits bevatten het nummer in binaire vorm van de bits die achtereenvolgens op de huidige plaats in het beeld verschijnen.

Merk op dat deze run-length codering een relatief klein aantal bits zal gebruiken om het voorbeeld met 4 strepen hierboven weer te geven.

Het zal het echter zeer slecht doen (in termen van het aantal bits dat het gebruikt) in het representeren van de dambord afbeelding die we eerst bekeken hebben. In het algemeen doet de run-length codering het goed om afbeeldingen die grote blokken met effen kleuren hebben te “comprimeren”. Gelukkig geldt dit voor veel echte afbeeldingen, zoals de afbeeldingen die HASA ontvangt, die meestal wit zijn met een paar zwarte vlekken die hemellichamen voorstellen.

Functie 6: compress(s)#

Dat was een hoop informatie! Hier is nu jouw taak.

Schrijf een functie compress(s), waarvan het argument een binaire string s is met een lengte van minder dan of gelijk aan 64 en dat als resultaat een andere binaire string teruggeeft. De resulterende binaire string zou een run-length codering van het origineel moeten zijn, zoals hierboven beschreven.

Je hebt misschien Ă©Ă©n of meerdere hulpfunctie nodig en je mag ze elke naam geven die je wilt. Ook kan het zijn dat je Ă©Ă©n of meerdere functies uit het werkcollege of deze opgave wilt gebruiken!

Functie 7: uncompress(c)#

Schrijf vervolgens een functie uncompress(c) die het comprimeren van de functie compress “omkeert” of “ongedaan maakt”.

Dat wil zeggen, uncompress(compress(s)) zou s moeten teruggeven. Hier is een leuke test die dat punt illustreert:

assert uncompress(compress(64 * "0")) == 64 * "0"

Nogmaals, hulpfuncties zijn toegestaan, net als het gebruik van functies die je bij de basis opdrachten hebt geschreven.

Hier zijn een paar voorbeelden van compress en decompress in actie:

In [1]: compress(64 * "0")
Out[1]: '01000000'

In [2]: uncompress("10000101")   # 5 1'en
Out[2]: '11111'

In [3]: compress("11111")
Out[3]: '10000101'

In [4]: stripes = "0" * 16 + "1" * 16 + "0" * 16 + "1" * 16

In [5]: compress(stripes)
Out[5]: '00010000100100000001000010010000'

In [6]: uncompress("00010000100100000001000010010000")
Out[6]: '0000000000000000111111111111111100000000000000001111111111111111'
Inhoud