Een $$(n,M=2^m,d)$$-code is een binaire code, waarbij de codewoorden $$n$$ symbolen lang zijn, en waarvan er $$M=2^m$$ effectief gebruikt worden. Er zijn dus $$m$$ "nuttige" bits en $$n-m \ge 0$$ "controle" (of "checksum") bits. De grootheid $$d$$ stelt de minimale Hammingafstand tussen twee verschillende codewoorden voor.

Programmeer het onderstaande in de klasse Code:

• een constructor met drie argumenten, namelijk de lengte van de codewoorden (n), het aantal nuttige bits per codewoord (m) en de BinaireVeelterm(v) die het mogelijk maakt om een sequentie van $$m$$ bits om te zetten naar een codewoord bestaande uit $$n$$ bits. De constructor controleert of de argumenten zinvolle initialisatiewaarden voor een Code bevatten, namelijk:
  • $$n>0$$ en $$m\ge0$$
  • $$n\ge m$$
  • de graad van de veelterm v is precies $$n-m$$ (anders worden codewoorden met een foutieve lengte gegenereerd)}
  Indien niet aan alle voorwaarden voldaan wordt, wordt de code ongeldig beschouwd, dan worden de attributen m en n op de waarde -1 geplaatst.
• de attributen m en n bevatten de gelijknamige waarden uit de constructoroproep (tenzij deze waarden ongeldig zouden zijn, dan krijgen ze de waarde -1).
• de methode __str__() die de Code afdrukt in de gedaante $$(n,M)$$, gevolgd door de gebruiksvriendelijke string-gedaante van de veelterm tussen '[' en ']'. Een Code met codewoorden van 15 symbolen, waarbij 11 nuttige bits per codewoord gecodeerd worden, met veelterm $$x^4+x+1$$ wordt dus afgedrukt als (15,2048)[x**4+x**1+1]. Een ongeldige code krijgt als stringgedaante (-1,0)[None].
• een geschikte methode __repr__().
• de operator ==, waarbij 2 codes gelijk zijn indien de waarden $$n$$ en $$m$$ gelijk zijn en ook de veeltermen gelijk zijn.
• de methode codeer(): deze methode heeft 1 argument, namelijk een lijst van gehele getallen, allen 1 of 0. Deze methode zet een lijst van lengte $$m$$ om naar een lijst van lengte $$n$$, een codewoord van de code. Dit codewoord wordt als resultaat van de methode teruggegeven (dit resultaat is dus opnieuw een lijst met enkel '1'-en '0'-en). Om het codewoord te bepalen ga je als volgt tewerk:
  • zet het originele bitptroon om naar een binaire veelterm (hierbij interpreteer je de bit op positie $$i$$ als coëfficiëent van $$x^i$$).
  • vermenigvuldig deze veelterm met de code-veelterm
  • zet deze veelterm opniew om naar een bitpatroon (zelfde interpretatie)
  Indien de argumentlijst niet de correcte lengte heeft, wordt een lege lijst als resultaat teruggegeven. Let erop dat de gecodeerde lijst voor geldige argumenten precies $$n$$ symbolen bevat (vul desnoods aan met 0-symbolen). Indien de code ongeldig geïnitialiseerd werd is het resultaat eveneens de lijst [].
• de methode decodeer() met als argument een lijst van gehele getallen, allen 0 of 1. Het is de bedoeling dat deze methode een lijst van $$n$$ symbolen terug omzet naar een geldig codewoorde van $$m$$ symbolen. In het geval dat de code ongeldig geïnitialiseerd werd, of indien de argumentlijst een foute lengte heeft, dan is het resultaat de lijst []. In het andere geval, wordt een geldig codewoord gegenereerd. Dit kan je doen door alle codewoorden $$0$$ t.e.m. $$2^m-1$$ in volgorde af te lopen (m.a.w. door alle binaire voorstellingen in $$m$$ bits van de getallen $$0$$ t.e.m. $$2^m-1$$ te overlopen) tot je het codewoord ontmoet dat moet gedecodeerd worden. Ook als gepoogd wordt een niet bestaand codewoord te decoderen, wordt [] als resultaat teruggegeven. Controleer dat de methoden codeer() en decodeer() elkaars inverse zijn (m.a.w. na elkaar oproepen van deze methoden moet de originele lijst terug opleveren).
• de methode corrigeer() doet hetzelfde als de methode decodeer(), alleen wordt nu het dichtstbijzijnde geldige codewoord gezocht, en wordt de bijhorende sequentie van m nuttige bits als resultaat teruggegeven. Wanneer de argumentlijst een niet-bestaand codewoord voorstelt, maar wel de correcte lengte heeft, wordt steeds een gedecodeerde sequentie van m bits als resultaat teruggegeven. Veronderstel dat de Code zo geconstrueerd werd dat dit minimum eenduidig is (m.a.w. er is slecths 1 dichtste codewoord voor elke te decoderen sequentie).
• de methode min_hamming_afstand() (zonder argumenten): deze methode bepaalt de grootheid $$d$$ van de $$(n,M,d)$$-code, en geeft deze als resultaat terug (het resultaat is dus een int). (Je kan dit doen door voor alle paren verschillende codewoorden de Hamming-afstand te bepalen, en de minimale waarde in deze zoektocht bij te houden.) Deze methode wordt niet op Dodona getest, omdat dit relatief veel rekentijd vergt.

TIP: Je zal in je code voor de methode decodeer over alle bitpatronen van lengte $m$ itereren. Bekijk de functie product() uit de module itertools om dit makkelijk mogelijk te maken !

Je hoeft je code voor de klasse BinaireVeelterm niet mee in te dienen (maar dit mag wel).

Voorbeeld

code = Code(15, 11, BinaireVeelterm(set([0, 1, 4])))
print(code)                               # (15,2048)[x**4+x**1+1]
w_n = [1,1,0,0,0,0,0,0,0,0,0]
w_m = code.codeer(w_n)
print(w_m)                         
# [1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
print(code.decodeer(w_m))         
# [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
w_m[3] = 1
print(code.decodeer(w_m))                 # []
print(code.corrigeer(w_m))                
# [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]