Hej!

Jag skickar instruktionerna om felrättande koder med vanlig epost tills vidare eftersom jag har begränsade möjligheter hemifrån.

Artikeln av Juliusz Brzezinski ger en hel del av kursinnehållet men kan nog vara ganska kompakt läsning och innehåller inga övningar, men kan gärna läsas som en översikt inför studiet av Barnett. Juliusz behandlar också tipsproblemet, men det går utanför det tilltänkta kursinnehållet - är dock en intressant tillämpning av ternära koder, som också tas upp av Barnett, men vi koncentrerar oss på binära koder där kalkylerna är enklast och man ändå får de bärande idéerna. Vi tar heller inte upp decimala koder, men Barnett har en del material om vanliga sådana och kanske kan locka till kursivläsning.

Att ägna sig åt i Barnett:

Vi använder aritmetik modulo 2, som endast använder siffrorna 0 och 1 och där addition och multiplikation är som vanligt utom att 1 + 1 = 0. Den som vill läsa mer om detta kan se avsnitten 2.4.1 och 2.4.4 som dock handlar om mycket mer än modulo 2 och kroppen (eng. field) Z/2.

Börja gärna på s. 197, där något om användningen av koder i CD-skivor beskrivs.

Annars gäller följande avsnitt:

4.1.1 Repetitionskod, avkodning till närmsta granne. Övningar: 3 4 6

4.1.2 Paritetskontroll. Ex. 4.4 kan hoppas över. Övning: 13

4.2 Hammingavstånd. Minimiavstånd för kod, sats om felupptäckande och -rättande. Övningar: 37 39 40 41

4.3 Linjära koder, även kallade gruppkoder.

4.3.1 Vikt, sats minimivikt = minimiavstånd. Övningar: 47 48 49 50 51 53

4.3.2 Matrisrepresentation, kontrollekvationer, kontrollmatris, informationsbitar, kontrollbitar, längd, dimension, ettfelsupptäckande kod, ettfelsrättande (s.e.c.) kod, perfekt kod. Övningar: 56 57 58 59 60 62

4.3.3 Syndrom, en smartare metod för avkodning än att jämföra med listan över korrekta ord. Övningar: 66 67 68

4.3.4 Hammingkod, ett ännu smartare sätt att använda syndrom. Venndiagram för [7,4]-kod (kan f.ö. användas för kod med högst 3 kontrollbitar); nämns även i Wallins "Den osynliga matematiken". Övningar: 70 71 72 73 74 75

(4.3.5 om bl.a. ternära koder kan i tillämpliga delar läsas av den som vill förstå den kod som används i samband med tipsproblemet; just den finns i Ex. 4.22(d).)

4.5 BCH-koder är ett sätt att konstruera koder som rättar mer än ett fel. Ett avkodningsschema ges i det skuggade s. 255-256; vill man verkligen förstå det får man ge sig på övningarna 114 och 115 (en alternativ avkodningsmetod är förstås att generera samtliga kodord och avkoda via jämförelse med den listan, men vi ville ju vara smartare). Algebran här är förmodligen ny för de flesta och kräver säkert en del arbete, men ger en introduktion till s.k. Galoiskroppar: det finns en väsentligen unik kropp (dvs. algebraisk struktur som tillåter de fyra räknesätten) med p^k element för varje primtal p och positivt heltal k. Algebran modulo 2 uppfyller i alla fall nybörjarens önskedröm: (a+b)^2 är verkligen lika med a^2+b^2. Övningar: 105 108 109 111 112 (114 115)

Problem 4.27 (ni har väl sett att det kommer problem i slutet av kapitlet och är numrerade separat från övningarna; de har också facit på skilda ställen) utnyttjar litet linjär algebra för att beskriva några av begreppen i kapitlet; speciellt karakteriseras kodens minimiavstånd i termer av linjärt (o)beroende mellan kontrollmatrisens kolonner, vilket ger en annan approach än BCH till att finna en tvåfelsrättande kod.

Jag har litet svårt att bedöma huruvida ovanstående är väldigt många övningar. Många av dem är ganska direkta kontroller på att man förstått innehållet i avsnittet (jag hoppade förresten över övning 5 som jag mer eller mindre stal till introduktionen till detta tema, ni har väl gjort den redan?). Jag hoppas att ni ser att ovanstående ger svar på de frågor som ställdes i introduktionen samtidigt som många andra ju kvarstår. Vi har inte alls diskuterat hur man överför meddelanden på binär form eller hur stora koder som då behövs. Med en Hammingkod med 4 kontrollbitar kan man dock ha upp till 11 informationsbitar och alltså 2048 kodord, mer än nog om man nöjer sig med att överföra vanliga skrivtecken ett i taget och med att kunna rätta ett fel. (Ju fler bitar, desto större risk för ett fel, förstås.)

Det är nog lämpligt att försöka klara av 4.1 och 4.2 under första veckan; 4.3 kan ta 1½ vecka och 4.5 en vecka och så behövs väl litet marginal. Jag återkommer om redovisningen men välkomnar givetvis frågor om övningar eller texten genast.