Kodningsteori¶
Kodningsteori besvarar en mycket praktisk fråga: när du skickar ett meddelande och några bitar blir flippade av brus, hur kan mottagaren märka — och till och med rätta — felen? Knepet är att inte använda alla möjliga ord. Om bara vissa "kodord" är tillåtna, så är ett förvanskat ord oftast inte tillåtet, vilket är flaggan om att något gått fel.
Kursen studerar binära linjära koder, och deras charm är en dubbel identitet: en linjär kod är på en gång ett gruppteoretiskt objekt (en delgrupp) och ett linjäralgebraiskt objekt (ett underrum). Varje tentauppgift lutar sig mot den dubbla identiteten, så håll båda hattarna nära.
Linjära koder¶
En binär kod av längd \(n\) är bara en vald mängd ord i \((\mathbb{Z}_2)^n\) — strängar av \(n\) bitar. Den är linjär när den är en delgrupp till \((\mathbb{Z}_2)^n\); ekvivalent (samma sak, linjäralgebrahatten) ett linjärt underrum. Konkret betyder det: den innehåller det idel-nollor ordet, och summan av två godtyckliga kodord är åter ett kodord.
Storleken på en linjär kod
En linjär kod av dimension \(k\) har
I synnerhet är storleken på en linjär kod alltid en tvåpotens.
Varför en tvåpotens — och varför slutenhet under addition är det enda som behöver kontrolleras. I \(\mathbb{Z}_2\) är addition XOR, och varje ord är sin egen invers (\(x + x = \mathbf{0}\)), så "sluten under inverser" kommer gratis. Kvar blir slutenhet under addition, och en mängd bitsträngar sluten under XOR spänns upp av några \(k\) oberoende ord — vilket ger exakt \(2^k\) kombinationer.
Tentamen (maj 2024, uppgift 5a): varför är denna kod inte linjär?
Räkna: \(\lvert C \rvert = 6\). Men en linjär kod måste ha \(2^k\) element, och \(6\) är inte en tvåpotens. Så \(C\) kan inte vara linjär. En rad, ingen aritmetik.
(Du skulle i stället kunna jaga två kodord vars XOR hamnar utanför \(C\) — men storlekskontrollen är snabbare och alltid tillgänglig. Grip efter den först.)
Att göra en kod linjär¶
För att växa en icke-linjär \(C\) till en linjär \(C'\) lägger du till de "saknade" summorna tills den är sluten. Den systematiska vägen, med underrumshatten: hitta en genererande mängd inuti \(C\), ta hela underrummet den genererar, och bekräfta att resultatet innehåller \(C\).
Tentamen (maj 2024, uppgift 5b): att fullborda \(C\) till en linjär kod
Beteckna orden \(v_0 = 0000000000\), \(v_1 = 0101010101\), \(v_2 = 1010101010\), \(v_3 = 1111111111\), \(v_4 = 0000011111\), \(v_5 = 1111100000\).
Summorna som läcker ut ur \(C\) är \(v_1 + v_4\) och \(v_2 + v_4\), så lägg tillbaka dem:
Att visa att \(C'\) är linjär — det är här poängen bor, och argumentet är slugt. Låt \(W\) vara underrummet genererat av \(v_1, v_2, v_5\). Vi visar \(C' = W\), vilket gör \(C'\) till ett underrum (alltså linjär) automatiskt. Beviset är en storleksmacka:
- \(C' \subseteq W\): kontrollera att varje ord i \(C'\) är en kombination av \(v_1, v_2, v_5\). Mycket riktigt \(v_0 = 0\cdot v_1\), \(v_3 = v_1 + v_2\), \(v_4 = v_3 + v_5 = v_1 + v_2 + v_5\), och \(w, w'\) är summor av dessa. Så alla \(8\) ord i \(C'\) bor i \(W\).
- \(\lvert W \rvert = 8\): \(v_1, v_2, v_5\) är linjärt oberoende (kontrollera direkt), så \(\dim W = 3\) och \(\lvert W \rvert = 2^3 = 8\).
- Slutsats: \(C' \subseteq W\), båda har \(8\) element, så \(C' = W\). Ett underrum — klart. \(\square\)
Det återanvändbara draget: i stället för att mala igenom alla \(8 \times 8\) summor för att verifiera slutenhet, fånga \(C'\) inuti ett underrum av samma storlek och dra slutsatsen om likhet genom räkning. Att packa in efter kardinalitet slår råstyrka.
Hammingavstånd¶
Hammingavståndet \(\delta(x, y)\) mellan två ord är antalet positioner där de skiljer sig — bokstavligen hur många bitflippar som förvandlar det ena till det andra. En kods minsta avstånd är det minsta avståndet mellan två distinkta kodord:
Detta enda tal styr allt om felhantering: ju längre isär kodorden är, desto mer förvanskning kan du överleva utan att förväxla ett ord med ett annat.
Genvägen som gör linjära koder lätta
För en linjär kod är minsta avståndet lika med den minsta vikten — det minsta antalet \(1\):or i något nollskilt kodord:
Varför: avståndet \(\delta(x, y)\) räknar de skiljande positionerna, vilket är exakt antalet \(1\):or i \(x + y\) — det vill säga \(\operatorname{wt}(x+y)\). Och för en linjär kod är \(x + y\) ett annat kodord. Så varje parvist avstånd är vikten av något kodord, och att minimera avstånd = att minimera vikt. Detta gör om \(\binom{\lvert C\rvert}{2}\) parvisa jämförelser till bara \(\lvert C \rvert - 1\) viktberäkningar. Bara giltigt om koden är linjär — kontrollera det först.
Detektering och rättning¶
Nu belöningen: hur många fel kan en kod fånga, och hur många kan den reparera?
De två trösklarna
En kod med minsta avstånd \(\delta\) kan:
- detektera upp till \(\delta - 1\) fel, och
- rätta upp till \(t\) fel, där \(\delta \geq 2t + 1\) — dvs. \(t = \left\lfloor \frac{\delta - 1}{2} \right\rfloor\).
Geometrin bakom båda talen. Föreställ dig kodorden som punkter, varje par minst \(\delta\) isär. Fel knuffar ett mottaget ord bort från det sanna kodordet:
- Detektering. Med färre än \(\delta\) flippar kan du inte landa exakt på ett annat kodord (de är \(\delta\) isär), så ett förvanskat ord är igenkännbart otillåtet — du detekterar upp till \(\delta - 1\) fel.
- Rättning. För att reparera, fäst det mottagna ordet vid det närmaste kodordet. Det är bara entydigt om de "klot" med radie \(t\) kring kodorden inte överlappar — vilket kräver \(\delta \geq 2t + 1\) (två klot med radie \(t\) behöver ett mellanrum på mer än \(2t\) mellan centra).
Tentamen (maj 2024, uppgift 5c–d): avstånd och avkodning
(c) Minsta avstånd och felkapacitet. För den linjära \(C'\) har det lättaste nollskilda ordet vikt \(5\), så \(\delta(C') = 5\). För den ursprungliga (icke-linjära) \(C\), använd en tvåsidig klämning:
- \(C \subset C'\), så varje avstånd i \(C\) förekommer också i \(C'\); alltså \(\delta(C) \geq \delta(C') = 5\).
- Och \(\delta(v_0, v_1) = 5\) uppnås av ett faktiskt par i \(C\); alltså \(\delta(C) \leq 5\).
Tillsammans \(\delta(C) = 5\). Så båda koderna detekterar upp till \(\delta - 1 = 4\) fel och rättar upp till \(t = \lfloor 4/2 \rfloor = 2\).
(Klämningen — undre gräns från den linjära övermängden, övre gräns från ett explicit par — låter dig låna den linjära kodens lätta minsta-vikt-beräkning för att fastställa den icke-linjära kodens avstånd. Ett prydligt knep värt att minnas.)
(d) Avkoda ett mottaget ord. Du tar emot \(x = 0101011111\) (skickat med \(C\)). Beräkna \(\delta(x, v)\) till varje kodord; det närmaste är \(v_4 = 0000011111\) på avstånd \(2\). Eftersom \(C\) rättar upp till \(2\) fel är detta inom räckhåll: ordet innehåller minst \(2\) fel och du rättar det till \(v_4 = 0000011111\).
Kontrollmatriser¶
En kontrollmatris för \(C\) är en matris \(A\) sådan att koden är exakt mängden av ord som \(A\) dödar:
Detta är ett kompakt sätt att specificera en kod, och det kommer med en gratis bonus: eftersom kärnan till en linjär avbildning alltid är ett underrum, är det i sig ett bevis för att \(C\) är linjär att presentera \(C\) som \(\ker A\). Två praktiska följder: att testa om ett ord är ett kodord är en matris–vektor-produkt (\(Ax \stackrel{?}{=} 0\)), och dimensionen faller ut ur dimensionssatsen, \(k = n - \operatorname{rang}(A)\).
Snabbreferens¶
| Fråga | Snabbaste vägen |
|---|---|
| Är \(C\) linjär? | Är \(\lvert C \rvert\) en tvåpotens? Om inte, klart. Om ja, kontrollera slutenhet under \(+\) (XOR). |
| Vad är \(\delta(C)\)? | Linjär: minsta vikten av ett nollskilt ord. Icke-linjär: alla parvisa avstånd. |
| Hur många fel detekteras? | \(\delta - 1\) |
| Hur många rättas? | \(\lfloor (\delta - 1)/2 \rfloor\) |
| Avkoda ett mottaget ord \(x\) | Fäst vid det närmaste kodordet i Hammingavstånd |
| Visa att \(C\) är linjär, givet \(A\) | \(C = \ker A\) är ett underrum, alltså linjär |