Toepassingen van algebra in de informatica: verschil tussen versies

Ga naar: navigatie, zoeken
Regel 1: Regel 1:
 
[[Afbeelding:AnnHaegemans.jpg|right|200px|]]
 
[[Afbeelding:AnnHaegemans.jpg|right|200px|]]
  
== Het Examen ==
+
== Algemene informatie ==
 
 
 
Het examen is open boek en gaat enkel over de oefeningen.
 
Het examen is open boek en gaat enkel over de oefeningen.
  
''Structuur''
+
=== Structuur van het examen ===
 +
# Kort vraagje over code theorie
 +
# Stel generatorveelterm op + PGZ
 +
# De grote BCH vraag (>= 10 punten)
 +
# Convolutional codes
  
1. kort vraagje over code theorie<br>
+
Zorg dat je zekér voorbereid bent om zo'n grote oefening 3 te maken als op het voorbeeldexamen dat je vindt op Toledo. Als je de oefeningen uit de oefenzittingen kunt, ben je klaar voor dit examen!
2. stel generatorveelterm op + PGZ<br>
 
3. de grote BCH vraag ( >= 10 ptn. )<br>
 
4. convolutional codes
 
  
Zorg dat je zekér voorbereid bent om zo'n GROTE oefening 3 te maken als op het voorbeeld examen, dat je vind op TOLEDO. Oplossingen van oefenzittingen vind je op [http://www.cs.kuleuven.ac.be/~bartv/tai/ deze site]. Als je die kunt, ben je klaar voor dit examen!
+
=== Academiejaar 2008-2009 ===
 +
Tijdens het academiejaar 2008-2009 wordt dit opleidingsonderdeel gedoceerd door professor Van Barel die de wegens ziekte afwezige professor Haegemans vervangt.
  
 
+
== Examen 25 augustus 2008 ==
== Voorbeeldexamen (11-06-08) ==
+
=== Vraag 1 ===
 
+
Gegeven volgende simpele code:
Dit is het [[Media:Tai_INFO_juni_08.pdf|examen van 11 juni 08]].<br>
+
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.
Heb een poging gedaan tot het [[Media:Opl_tai_examen_juni_08.pdf|uitgebreid uitwerken van het examen]].  Kan misschien handig zijn als extra voorbeeld.  Ik kan niet garanderen dat alles juist is enzo, maar ik ben er vrij zeker van dat het redelijk juist is.
 
 
 
== Herexamen 25-08-08 ==
 
 
 
1) Gegeven volgende simpele code:<br>
 
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.<br>
 
 
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.
 
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.
  
2) BCH code in GF(8)<br>
+
=== Vraag 2 ===
n= 15  en moet 2 fouten kunnen verbeteren (t=2)<br>
+
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?<br>
 
Bepaal hoeveel verschillende codes je hiervoor kan construeren, en wat is de optimale code, en hoeveel mogelijke optimale codes zijn er?<br>
 
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))
 
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))
  
3) BCH code over GF(19), n=18 (dus je hebt een GF(19) over GF(19) code (k=1)) en t=2<br>
+
=== Vraag 3 ===
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)<br>
+
BCH code over GF(19), n=18 (dus je hebt een GF(19) over GF(19) code (k=1)) en t=2
Bepaal de dimensie van de code.<br>
+
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)
Codeer een zelfgekozen infowoord met d>=2<br> (hoe dit ook zo simpel mogelijk, kies dus 2 tekens verschillend van 0, dat spaart veel rekenwerk uit)
+
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).
 
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).
  
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.
+
=== 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 [[Media:Tai_INFO_juni_08.pdf|examen van 11 juni 08]]. Ik heb een poging gedaan tot het [[Media:Opl_tai_examen_juni_08.pdf|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.
  
== Examenvragen (januari'06-'07) ==
+
== Examen januari 2007 ==
  
 
=== Vraag 1 ===
 
=== Vraag 1 ===
 
+
Je kreeg een lineaire blokcode met enkele deelvragen:
Je kreeg een lineaire blokcode met enkele deelvragen: <br>
+
# is deze lineair?
a) is deze lineair?<br>
+
# wat is zijn dimensie?
b) wat is zijn dimensie?<br>
+
# bereken de G en H matrix
c) bereken de G en H matrix<br>
+
# codeer een eigen gekozen informatiewoord
d) codeer een eigen gekozen informatiewoord<br>
+
# bereken cH^T met c het codewoord uit (d)
e) bereken cH^T met c het codewoord uit (d)<br>
 
 
   
 
   
 
=== Vraag 2 ===
 
=== Vraag 2 ===
 
+
Een code verbeteren met behulp van PGZ algoritme en het informatiewoord bepalen.
Een code verbeteren met behulp van PGZ algoritme en het informatiewoord bepalen.<br>
 
  
 
=== Vraag 3 ===
 
=== Vraag 3 ===
 +
Grote oefening op BCH codes.
  
Grote oefening op BCH codes <br>
+
== Examen september 2005 ==
 
 
== Examenvragen (september '05) ==
 
 
 
slechts 3 vragen :
 
 
 
 
=== Vraag 1 ===
 
=== Vraag 1 ===
Een 2-foutenverbeterende BCH-code over GF(7) van lengte 8 en l = 6.<br>
+
Een 2-foutenverbeterende BCH-code over GF(7) van lengte 8 en l = 6.
Kies een van de volgende primitieve veeltermen <br>
+
Kies een van de volgende primitieve veeltermen
x + 2<br>
+
x + 2
X² + 3x + 5<br>
+
X² + 3x + 5
X³ + 3x + 2<br>
+
X³ + 3x + 2
  
en a) bepaal de generatorveeltermen, zoals je weet zijn dat er 6 (invoer i=1,2, uitvoer j=1,2,3)<br>
+
# bepaal de generatorveeltermen, zoals je weet zijn dat er 6 (invoer i=1,2, uitvoer j=1,2,3)
b) wat is de dimensie ?<br>
+
# wat is de dimensie ?
c) 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
+
# 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.
Het zal niet nuttig zijn alle machten van alpha op te schrijven
 
  
 
=== Vraag 2 ===
 
=== Vraag 2 ===
grote BCH code vraag met deelvraagjes zoals voorbeeld examen, zoals bepaal R, zoek fouten, decodeer, ...
+
Grote BCH code vraag met deelvraagjes zoals voorbeeld examen, zoals bepaal R, zoek fouten, decodeer, ...
  
 
BCH n=13, q=3, t=3, l=7
 
BCH n=13, q=3, t=3, l=7
 
  
 
=== Vraag 3 ===
 
=== Vraag 3 ===
 
 
[http://www.student.kuleuven.be/~m0316348/opgave3.jpg opgave]
 
[http://www.student.kuleuven.be/~m0316348/opgave3.jpg opgave]
  
a) bepaal de generatorveeltermen <br>
+
# bepaal de generatorveeltermen
b) teken het toestandsdiagramma<br>
+
# teken het toestandsdiagramma
c) codeer 10 11 01 00 11
+
# codeer 10 11 01 00 11
 
 
== Mijn oplossingen ==
 
  
 +
=== Mijn oplossingen ===
  
 
1.b. | dim = 5, (8,3)-code<br>
 
1.b. | dim = 5, (8,3)-code<br>

Versie van 9 feb 2009 om 15:26

AnnHaegemans.jpg

Algemene informatie

Het examen is open boek en gaat enkel over de oefeningen.

Structuur van het examen

  1. Kort vraagje over code theorie
  2. Stel generatorveelterm op + PGZ
  3. De grote BCH vraag (>= 10 punten)
  4. Convolutional codes

Zorg dat je zekér voorbereid bent om zo'n grote oefening 3 te maken als op het voorbeeldexamen dat je vindt op Toledo. Als je de oefeningen uit de oefenzittingen kunt, ben je klaar voor dit examen!

Academiejaar 2008-2009

Tijdens het academiejaar 2008-2009 wordt dit opleidingsonderdeel gedoceerd door professor Van Barel die de wegens ziekte afwezige professor Haegemans vervangt.

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.

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