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 $$\verb!Code!$$:

• een constructor met drie argumenten, namelijk de lengte van de codewoorden ($$\verb!n!$$), het aantal nuttige bits per codewoord ($$\verb!m!$$) en de irriciducibele $$\verb!BinaireVeelterm! (\verb!v!)$$ die het mogelijk maakt om een sequentie van $$m$$ symbolen om te zetten naar een codewoord. Je mag hierbij veronderstellen dat de veelterm irriducibel is. De constructor controleert of de argumenten zinvolle initialisatiewaarden voor een $$\verb!Code!$$ bevatten, namelijk:
  • $$n>0$$ en $$m\ge0$$
  • $$n\ge m$$
  • de graad van de veelterm $$\verb!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, en genereren de get-methoden $$\verb!get_n()!$$ en $$\verb!get_m()!$$ (zie verder) de waarden -1. In het andere geval, wordt de $$\verb!Code!$$ met de opgegeven waarden geïnitialiseerd.
• get-methoden $$\verb!get_n()!$$ en $$\verb!get_m()!$$ voor de parameters $$n$$ en $$m$$ van de $$\verb!Code!$$.
• de methode $$\verb!__str__()!$$ die de $$\verb!Code!$$ afdrukt in de gedaante $$(n,M)$$, gevolgd door de gebruiksvriendelijke string-gedaante van de veelterm tussen '[' en ']'. Een $$\verb!Code!$$ met codewoorden van 15 symbolen, waarbij 11 nuttige bits per codewoord gecodeerd worden, met veelterm $$x^4+x+1$$ wordt dus afgedrukt als $$\verb!(15,2048)[x**4+x**1+1]!$$. Een ongeldige code krijgt als stringgedaante $$\verb!(-1,0)[None]!$$.
• een geschikte methode $$\verb!__repr__()!$$.
• de operator "==", waarbij 2 codes gelijk zijn indien de waarden $$n$$ en $$m$$ gelijk zijn en ook de irreducibele veeltermen gelijk zijn.
• de methode $$\verb!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. 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 $$\verb![]!$$.
• de methode $$\verb!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 $$\verb![]!$$. 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 $$\verb![]!$$ als resultaat teruggegeven. Controleer dat de methoden $$\verb!codeer()!$$ en $$\verb!decodeer()!$$ elkaars inverse zijn (m.a.w. na elkaar oproepen van deze methoden moet de originele lijst terug opleveren).
• de methode $$\verb!corrigeer()!$$ doet hetzelfde als de methode $$\verb!decodeer()!$$, alleen wordt nu het dichtstbijzijnde geldige codewoord gezocht, en wordt de bijhorende sequentie van $$\verb!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 $$\verb!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 $$\verb!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.

Opdrachten

• Bepaal voor de $$(15,2048,?)$$-code met veelterm $$x^4+x+1$$ de minimale Hamming-afstand tussen twee verschillende codewoorden.
• Hoeveel fouten per codewoord kan je hiermee detecteren/corrigeren?
• Controleer dit door dit aantal te corrigeren fouten op een te coderen lijst toe te passen. Neem ook een grotere waarde voor dit aantal fouten, en kijk na dat de correctie niet langer lukt.
• Herhaal dit voor de $$(15,128,?)$$-code met veelterm $$x^8+x^7+x^6+x^4+1$$.

Dien zowel je oplossing voor beide klassen $$\verb!BinaireVeelterm!$$ en $$\verb!Code!$$ in.

Voorbeeld

code = Code(15, 11, BinaireVeelterm([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]