Toepassingen van algebra in de informatica

Ga naar: navigatie, zoeken
MarcVanBarel.jpg

Samenvattingen

Klik hier om de samenvattingen te bekijken

Algemene informatie

Academiejaar 2012-2013

Vanaf het academiejaar 2012-2013 verandert het examen: je mag vanaf nu enkel de cursus meenemen (dus geen oplossingen van oefenzittingen of oude examens). Daarenboven mag je in de cursus enkel markeren en kleine foutjes verbeteren of kleine aanduidingen maken (je mag er geen oplossingen in noteren).

Vanaf dit academiejaar worden er ook meer inzichtsvragen gesteld naast oefeningen.

Het examen voor academiejaar 2012-2013

Het examen is een volledig schriftelijk oefeningen-examen. Je mag zo veel meenemen als je wilt: cursus, rekenmachine, opgeloste oefenzittingen, opgeloste voorbeeldexamens, ...

Daar je alles mag meenemen en het examen een vast stramien volgt is het examen niet zo heel moeilijk. Wel is 4 uur heel krap om de 4 vragen volledig op te lossen. Werk dus heel snel en let op voor modulo-rekenfouten!

Structuur van het examen

  1. Zoek de inverse van een gegeven veelterm
  2. Lineaire blokcodes
  3. De grote BCH vraag
  4. Convolutionele codes

Academiejaar 2008-2009

Vanaf het academiejaar 2008-2009 wordt dit opleidingsonderdeel gedoceerd door professor Van Barel in plaats van professor Haegemans.

Vakevaluatie

Elk puntje hieronder is iemands mening. Verander aub geen puntjes. Als je een andere mening hebt, gelieve ze onderaan toe te voegen.

Kwaliteit cursus (prijs, duidelijkheid, overeenkomst met les, ...)

  • 2018: Er zijn drie cursusteksten. De eerste gaat over zuivere algebra en heb je uiteindelijk niet nodig. Je hebt vooral de tweede nodig en over het algemeen is die redelijk duidelijk.

Studiebelasting (aantal studiepunten in verhouding met bestede tijd)

  • 2018: Het valt over het algemeen wel mee. Het examen is gemakkelijker dan je verwacht na de eerste paar lessen.

Plaats binnen de opleiding (nodige voorkennis, overlap met andere vakken, relevantie van het vak,...)

  • 2018: Voorkennis van lineaire algebra is nuttig; eerder om abstract te redeneren over algebra's en groepen dan om te kunnen werken met stelsels. Voor de rest staat het op zichzelf: het gaat vooral over foutverbeterende codes.

Manier van lesgeven bij hoorcolleges (snelheid, verstaanbaarheid, structuur, nut, ...)

  • 2018: Soms gaat het nogal snel met de nieuwe begrippen, vooral in het begin. De colleges zijn niet nodig om te slagen voor dit vak.

Evaluatie oefenzittingen/labo's (nut, begeleiding, ...)

  • 2018: Geen enkele oefenzitting is afgeraakt, maar als je ze maakt, heb je een perfect beeld van de te kennen inhoud van de cursus.

Examen (mate waarin het een weerspiegeling is van de cursus, examenvorm, ...)

  • 2018: Niet moeilijker dan de oefenzittingen. Het is wel veel meer, natuurlijk.


29 januari 2019

Vraag 1

(2 punten)

  • Voldoet <M,*> aan alle eigenschappen van een groep?
  • Voldoet <G,*> aan alle eigenschappen van een groep?
  • Is <H,*> een deelgroep van <G,*>

Vraag 2

(2 punten)

Gegeven is een priemideaal, bewijs.

Vraag 3

(2 punten)

Gegeven met primitief element een nulputn van over

We weten dat alle elementen van de muliplicatieve groep geschreven kan worden als en ook als veelterm in van graad < 5. Geef het resultaat in die twee voorstellingen.

Vraag 4

(2 punten)

Is een primitieve veelterm over GF(5), met andere woorden kan de veelterm gebruikt worden om op te stellen?

Vraag 5

( 3 punten)

Gegeven een (5, 3) Hamming code over met een primitief element van en een nulpunt van de primitieve veelterm .

  • Bepaal G voor een systematische code
  • Codeer
  • Decodeer

Vraag 6

( 2 punten)

Bepaal de generator veelterm van een cyclische blokcode van een lengte 10 over GF(3) met een maximum dimensie die 1 fout kan verbeteren.

Mag gegeven worden in gefactoriseerde vorm via nulpunten. Dit wil zeggen in fucntie van een nulputn van een primitieve veelterm over GF(3). Dus factoren moeten niet samen genomen worden tot je een veelterm bekomt behorende tot GF(3)[X]. Wat is de dimensie?

Vraag 7

( 3 punten)

BCH van lengte 12 over GF(5) die 3 fouten kan verbeteren. De parameter l is 3

Gegeven de machten van primitief element van GF(25) over GF(5)

Ontvangen: 3 3 1 3 0 4 0 1 0 1 1 1

Syndroom:

i 1 2 3 4 5 6


Vervolledig de BM tabel.

S n d
0 /
1
2
3
4 2
5
6 2

Vraag 8

30 januari 2018 Voormiddag

  • M is de verzameling van 2x2 matrices over Z_2 waarvan de determinant gelijk is aan 1 (dus de niet-singuliere matrices), met de normale matrixvermenigvuldiging gedefinieerd.
    • Toon aan dat M 6 elementen heeft
    • Bewijs dat M een groep is
  • Zij U en V twee idealen in de ring R. Zij U+V { u+v | u uit U, v uit V }. Bewijs dat U+V ook een ideaal is in R.
  • Gegeven twee veeltermen (het was iets als x^7 - x^5 - 2x^2 + 2 en x^5 - 3x^4 - x + 3), geef de gemeenschappelijke rationale nulpunten
  • Gegeven de veelterm x^3 + x^2 + 1 over GF(2), is dit een primitieve veelterm? M.a.w. kan ze gebruikt worden om GF(2^3) te construeren?
  • Gegeven een hammingcode over GF(2^2) met alpha^2 + alpha + 1 = 0 als primitief element en als pariteitstestmatrix H = [1, alpha, alpha^2, 1, 0],[1, 1, 1, 0, 1].
    • Bepaal de generatormatrix G voor een systematische code.
    • Encodeer een gegeven informatiewoord.
    • Decodeer een gegeven codewoord.
  • Gegeven een BCH-code over GF(7) met t = 2, l = 6, n = 8.
    • Bepaal de generatorveelterm zo'n code. Er zijn een 1e, 2e en 3e-graads primitieve veelterm voor GF(7) gegeven, kies hier één van om GF(7^k) op te stellen. Je hoeft de generatorveelterm niet volledig uitgeschreven te geven. Ontbinding in factoren over GF(7) volstaat. Zorg dus er dus voor dat er geen machten van beta of alpha meer in voorkomen.
      • Hint: maak een tabel met machten van beta. Een tabel met machten van alpha is niet aangeraden.
    • Wat is de dimensie van de code.
    • decodeer een gegeven V met het PGZ algoritme. S_1, S_2, en S_4 krijg je cadeau. S_3 moet je zelf berekenen.
  • Gegeven een tabel voor het BM-algoritme die deels is ingevuld, vul deze aan. Er is een tabel met de elementen van GF(3^3) als machten van alpha en als veeltermen over GF(3) gegeven. Deze vraag is gelijkaardig aan het voorbeeld van juni 2008.
  • Gegeven een diagramma voor een convolutionele code met 2 inputs en 3 outputs
    • Geef de 6 generatorveeltermen (deze waren: voor i_1: G_1 = 1, G_2 = 1, G_3 = X + 1; voor i_2: G_1 = 0, G_2 = 1, G_3 = X
    • teken het toestandsdiagram
    • encodeer een informatiewoord

31 Januari 2017 Voormiddag

(Als iemand de deftige wiskundige notatie wil gebruiken, doe maar, ik krijg het niet werkend.)

  • Definieer M als de verzameling van reëele 2x2 matrices en de vermenigvuldiging als de normale matrixvermenigvuldiging. Er zijn enkele wetten uit de lineaire algebra gegeven (voor vierkante matrices): det(A*B) = det(A)*det(B) en voor det(A) != 0: det(A^-1) = det(A)^-1. Verder mag je ook steunen op algemeen bekende eigenschappen, zoals bijvoorbeeld de associativiteit van de matrixvermenigvuldiging in het algemeen (dit stond er niet bij maar heeft de prof wel gezegd). (2ptn)
    • Is <M, *> een groep?
    • Is <G, *> een groep, met G = {g|g uit M met det(g) != 0}?
    • Is <H, *> een deelgroep van G, met H = {h|h uit G met det(h) = 1}?
  • Beschouw de ring <Z_5[x], +, *>. Is <(1 + 3*x + 3*x^2 + x^3), +, *> een priemideaal over deze ring? (2ptn)
  • We werken over GF(5^3) met een primitief element alpha als nulpunt van de veelterm x^3 + 3*x + 2 = 0. We weten dat elk element van GF(5^3) kan geschreven worden als een macht van alpha of een veelterm in alpha van graad kleiner dan 3. Bereken de volgende elementen en schrijf ze uit in beide voorstellingen: (2ptn)
    • (alpha^3)*(alpha^4)
    • (alpha^2 + 2*alpha + 1) + (alpha^2 + alpha + 4)
  • Is x^2 + 2*x + 2 een primitieve veelterm over GF(3)? Met andere woorden, kan deze gebruikt worden om GF(3^2) mee te construeren? (2ptn)
  • Gegeven een (5, 3)-Hammingcode met als pariteitsmatrix H = [[1, alpha, alpha^2, 1, 0], [1, 1, 1, 0, 1]] over GF(2^2) met alpha als nulpunt van x^2 + x + 1. (3ptn)
    • Bepaal de generatormatrix G voor een systematische code.
    • Codeer [1, 1, alpha].
    • Decodeer [alpha, 1, alpha, 1, 1 + alpha].
  • Bepaal de generatorveelterm van een cyclische code met maximale dimensie die 1 fout kan verbeteren, met lengte 10, over GF(3). Je hoeft alleen de factoren te bepalen in functie van een primitief element alpha, je moet deze veelterm dus niet uitwerken tot de coëfficiënten allemaal terug in GF(3) zitten. Wat is de dimensie van deze code? (2ptn)
  • Gegeven een BCH-code over GF(5) met lengte 12, t = 3 en l = 3. Alpha is een primitief element van GF(5^2) en je krijgt een lookup-table voor additieve notatie in functie van multiplicatieve notatie en vice-versa, om snel bewerkingen mee uit te voeren. Gegeven een ontvangen woord (dat je niet nodig hebt) en de syndromen hiervan [alpha^6, alpha^3, alpha^11 (misschien alpha^12?), alpha^6, alpha^19, alpha^15]. Vul een tabel met tussenresultaten uit het BM-algoritme voor delta, n, d, lambda(x) en lambda*(x) aan. Een aantal tussenresultaten zijn al gegeven (6 iteraties, in de laatste iteratie was d 2, meer herinner ik me niet meer). (3ptn)
  • Gegeven het onderstaande encoderdiagram voor een (2, 1)-convolutionele code. (4ptn)
    • Bepaal de generatorveeltermen.
    • Teken het toestandsdiagram.
    • Bereken d_min en d_free = d_oneindig.
    • Codeer 1 1 0 1 0 1.
    • Waarom zou je deze code systematisch noemen?
    • Decodeer 10 01 11 10 01. Je weet dat de encoder geklaard is (dus al het geheugen is 0 op het einde).

Bestand:TAI2013encoder.jpg‎

26 Januari 2016 Voormiddag

  • Geef antwoord op volgende vragen: (2ptn)
    • Is een abelse groep?
    • Is een abelse groep?
    • Is de vermenigvuldiging distributief t.o.v. de optelling in ?
  • Zijn en isomorf als ringen? (2ptn)
  • Is een primitieve veelterm voor GF(5)? (2ptn)
  • Een veelterm splitsen in factoren over een veld (was zeer eenvoudig,het was een 4degraads veelterm met 4 nulpunten) (2ptn)
  • H matrix (in de vorm is gegeven (2ptn)
    • Bepaal de generator matrix uit H voor een systematische code
    • Codeer een informatiewoord
    • Decodeer een ontvangen woord
  • Bepaal de generatorveelterm van een cyclische (NIET BCH) code met lengte 63 en met maximale graad. Twee nulpunten werden gegeven, evenals de primitieve veeltermen van de velden waarover gewerkt werd. (3ptn)
  • Vraag over BM algoritme: Gegeven de volgende opeenvolging van waardes van in het algoritme op pagina 75: 0 0 2 2 2 2 4 4 4 4 7 7 7 (ben niet zeker van de laatste 2 of 3 termen)(3ptn)
    • Bepaal de waardes van en beargumenteer
    • Bepaal of de matrices regulier of singulier zijn voor
  • Encoder diagram gegeven voor convolutionele code (4ptn)
    • Geef de generator veeltermem (waren en
    • Bepaal en
    • Codeer een informatiewoord
    • Decodeer een ontvangen woord

23 januari 2013 Voormiddag

  • Geef antwoord en bewijs de vragen over de volgende structuur: dat Waarbij de optelling en vermenigvuldiging gedefinieerd zijn zoals gewoonlijk
    • is een ring?
    • is een comutatieve ring?
    • heeft een eenheid element voor de vermenigvulding?
    • is een lichaam?
    • is een veld?
    • is een integriteitsdomein?
  • Bewijs hetvolgende: Als zij een eindige commutatieve ring met multiplicatieve eenheid. Bewijs dat een maximaal ideaal is van als en slechts als een priemideaal van is.
  • Ontbind in priemfactoren over [Oplossing was als ik me niet vergis dus dat zou overeen uit moeten komen]
  • is x^2 + 1$ een primitieve veelterm van GF(3)?
  • Gegeven dat een systematische (6,4)-code is over . Deze code heeft als pariteitsmatrix H:
        [Ben niet helemaal zeker van het eerste stuk v/d matrix maar het leek er toch fel op]
    • Bereken de generatormatrix van deze code
    • codeer i = 1 1 1 1 [ofzo, maakt niet zoveel]
    • decodeer v = 1 2 3 2 1 1 [ongeveer, maakt niet zoveel] en vind het informatie woord.
  • Bepaal de generator veelterm van een cyclische code met lengte 80 over , waarbij en nulpunten zijn van de generatormatrix, zodat de dimensie maximaal is. is een primitief element van (ofzo) en een primitief element van . Wat is de dimensie van de code?
  • Vraag over BM algoritme: Gegeven de volgende opeenvolging van waardes van in het algoritme op pagina 75: 0 0 2 2 2 3 3 3 3 6 6 6 6
    • Bepaal de waardes van en beargumenteer
    • Bepaal of de matrices regulier of singulier zijn voor
  • Vraag over convolutionele codes. Gegeven het onderstaande een encoder diagram.

Bestand:TAI2013encoder.jpg‎

    • Bepaal de generator veeltermen $g^{(i)}$ voor $i = 1,2$ [er waren twee outputs]
    • Teken het toestands diagram.
    • Bepaal en
    • Codeer 10111011 [ongeveer, maakt niet zoveel]
    • Decodeer 10 11 10 11 via het viterbi algoritme [ongeveer, maakt niet zoveel]

Examen juni 2012

Exact dezelfde soort vragen als de voorbije 3 jaar:

Vraag 1

Een inverse zoeken in

Vraag 2

H is gegeven

  • Bepaal G
  • codeer een gegeven i
  • decodeer een gegeven v en wat is de bijhorende i

Vraag 3

Een BCH code gegeven

  • Wat is de dimensie? Wat is de dimensie bij l=8? Zou een keuze l=1 goed zijn?
  • Vul de tabel met de machten van verder aan.
  • Vul de minimaalveeltermen voor gegeven nevenklassen aan + bepaal de generatorveelterm
  • Vul de syndromen aan.
  • Vul de tabel voor het BM-algoritme aan
  • Voor d=0,1,2: wat is en
  • Bepaal de plaats en de waarde van fouten

Vraag 4

Een blokdiagram van convolutionele codes gegeven (1 invoerbit, 2 registers, 3 uitvoerbits)

  • Bereken de generatorveeltermen
  • Geef het toestandsdiagramma
  • Bereken en
  • Decodeer een gegeven woord.

Examen juni 2011

Vraag 1

bewijs dat inverteerbaar is in

Vraag 2

(8,6) Hamming code GF(7)

H= [10123456 , 01111111] (dus een matrix met 2 rijen en 8 kolommen)

  • G?
  • codeer i=400306
  • decodeer v=60342545 wat is i?

Vraag 3

BCH n=13 GF(3) t=3 l=1

  • wat is de dimensie van de code? en de dimensie bij l=2,l=8? is l=1 goed gekozen?
  • Vul de tabel van alfa aan
  • Vul minimaalveeltermen aan
  • Vul Si aan
  • BM
  • phi(d)(x) en mu(d) voor d=0,1,2
  • bepaal de plaats en waarde van de fouten

Vraag 4

Je krijgt het blokdiagram van een convolutionele code en je moet daaruit

  • de generatorveeltermen berekenen
  • een toestandsdiagramma van de code geven
  • de afstanden en berekenen
  • een bepaalde ontvangen woord decoderen met het Viterbi-algoritme

Examen 19 juni 2009

Vraag 1

Bewijs dat inverteerbaar is in

Vraag 2

Vraag over lineaire code. Je krijgt de pariteitstestmatrix H en je moet

  1. de generatormatrix G geven
  2. een gegeven informatiewoord coderen
  3. een gegeven ontvangen woord (dus met fout) decoderen

Vraag 3

De grote Berlekamp-Massey-en-Forney-vraag. Deze vraag staat ook op de meeste punten.

Vraag 4

Je krijgt het blokdiagram van een convolutionele code en je moet daaruit

  1. de generatorveeltermen berekenen
  2. een toestandsdiagramma van de code geven
  3. de afstanden en berekenen
  4. een bepaalde ontvangen woord decoderen met het Viterbi-algoritme

Examen 25 augustus 2008

Vraag 1

Gegeven volgende simpele code: Een infowoord van 3 tekens (modulo 3), abc wordt omgezet in een codewoord als volgt: abcde, met abc gelijk aan abc uit het informatiewoord, en de zodat d+a+c=0 en e zodat a+e=0. Wat is de lengte van de code, hoeveel fouten kan ze verbeteren en hoeveel fouten kan ze vinden? Dimensie van de code? Is het een lineaire code? Is het een cyclische code? Stel een generatormatrix op voor deze code.

Vraag 2

BCH code in GF(8) n= 15 en moet 2 fouten kunnen verbeteren (t=2) Bepaal hoeveel verschillende codes je hiervoor kan construeren, en wat is de optimale code, en hoeveel mogelijke optimale codes zijn er?
Tip: je mag l vrij kiezen, varieer deze van 0 tot 14, bepaal de cyclotomische nevenklassen en hun minimaalveeltermen. Je moet werken met een GF(8^5) code over GF(8) (want 8^5(mod 15)=1) Dit wil ook zeggen dat er maximaal 5 elementen in een cyclotomische nevenklasse zitten. Schrijf dan voor elke waarde van l de combinatie van minimaalveeltermen uit die de generatorveelterm g(x) vormen (2t opeenvolgende machten van beta). Schrap dan alle identieke g(x). Wat je overhoudt is het aantal (en welke) mogelijke generatorveeltermen en dus verschillende codes. Voor het bepalen van de efficiëntie van de code, zeg je dat de code een (n,k)-code is, met k=n-(graad(g(x))

Vraag 3

BCH code over GF(19), n=18 (dus je hebt een GF(19) over GF(19) code (k=1)) en t=2 Bepaal g(x), je mag zelf l kiezen. (omdat k=1 heeft elke cyclot. nevenklasse juist 1 element en is de graad van g(x) altijd even groot, ongeacht de keuze van je l) Bepaal de dimensie van de code. Codeer een zelfgekozen infowoord met d>=2 (doe dit ook zo simpel mogelijk, kies dus 2 tekens verschillend van 0, dat spaart veel rekenwerk uit) Zet in het bekomen codewoord 2 zelfgekozen fouten, decodeer dit woord terug met BM en Forney. (Voor het bepalen van de syndromen mag je gebruik maken van het feit dat je de foutlocaties al kent).

Vraag 4

Convolutionele codes. Gegeven een encoder diagramma (met 1 schuifregister, 1 input bit en 2 output bits), bepaal aan de hand daarvan de generatorveeltermen. Teken nu een state diagram van de encoder. Bepaal de min distance en de free distance. Encodeer een gegeven infowoord. Decodeer een zelfgekozen codewoord.

Examen 11 juni 2008

Dit is het examen van 11 juni 08. Ik heb een poging gedaan tot het uitgebreid uitwerken van het examen. Dit kan misschien handig zijn als extra voorbeeld. Ik kan niet garanderen dat alles juist is, maar ik ben er vrij zeker van dat het redelijk juist is. Bekijk ook deze alternatieve oplossing van het examen, mooi uitgewerkt in LaTeX.

Zeker aan te raden om dit examen eens proberen te maken! Als je dit kan, kan je het examen. (het examen ziet er altijd ongeveer hetzelfde uit)

Examen januari 2007

Vraag 1

Je kreeg een lineaire blokcode met enkele deelvragen:

  1. is deze lineair?
  2. wat is zijn dimensie?
  3. bereken de G en H matrix
  4. codeer een eigen gekozen informatiewoord
  5. bereken cH^T met c het codewoord uit (d)

Vraag 2

Een code verbeteren met behulp van PGZ algoritme en het informatiewoord bepalen.

Vraag 3

Grote oefening op BCH codes.

Examen september 2005

Vraag 1

Een 2-foutenverbeterende BCH-code over GF(7) van lengte 8 en l = 6. Kies een van de volgende primitieve veeltermen x + 2 X² + 3x + 5 X³ + 3x + 2

  1. bepaal de generatorveeltermen, zoals je weet zijn dat er 6 (invoer i=1,2, uitvoer j=1,2,3)
  2. wat is de dimensie ?
  3. decodeer met PGZ : 2 6 4 6 5 1 3 1 als je weet dat S_1 = 0, S_2 = 4 en S_4 = 4

Het zal niet nuttig zijn alle machten van alpha op te schrijven.

Vraag 2

Grote BCH code vraag met deelvraagjes zoals voorbeeld examen, zoals bepaal R, zoek fouten, decodeer, ...

BCH n=13, q=3, t=3, l=7

Vraag 3

opgave

  1. bepaal de generatorveeltermen
  2. teken het toestandsdiagramma
  3. codeer 10 11 01 00 11

Mijn oplossingen

1.b. | dim = 5, (8,3)-code
1.c. | 0 6 4 4 5 1 3 1
2. | /
3.c. | 111 100 010 001 101