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\).
Sfärpackningsgränsen¶
Rättning fungerar genom att lägga en klotmed radie \(t\) kring varje kodord och snäppa ett mottaget ord till det klot det landar i. För att det ska vara entydigt måste kloten vara disjunkta — och disjunkta klot kan inte överbelamra rummet. Att räkna hur många ord ett klot innehåller förvandlar detta till en hård gräns för hur många kodord som kan samexistera.
Sfärpackningsgränsen (Hamming-gränsen)
En binär kod av längd \(n\) som rättar \(t\) fel — så att dess klot med radie \(t\) är disjunkta — har som mest
Nämnaren är antalet ord inom avstånd \(t\) från ett fixerat ord: \(\binom{n}{i}\) sätt att vända exakt \(i\) av de \(n\) bitarna, summerat över \(i = 0, \dots, t\).
Varför. Det finns \(2^n\) ord totalt. Vart och ett av de \(\lvert C\rvert\) disjunkta kloten förbrukar \(\sum_{i=0}^{t}\binom{n}{i}\) av dem, och disjunkta mängder kan inte summera till mer än hela rummet — så \(\lvert C\rvert \cdot \sum_{i=0}^{t}\binom{n}{i} \leq 2^n\). En kod som når gränsen med likhet slösar inget: varje ord ligger i exakt ett klot. En sådan kod kallas perfekt — kloten täcker hela rummet utan luckor.
Löst: Hamming-koden \([7,4]\) är perfekt
Hamming-koden har \(n = 7\), \(\lvert C\rvert = 2^4 = 16\) och rättar \(t = 1\) fel. Kontrollera gränsen: ett klot med radie \(1\) rymmer \(\binom{7}{0} + \binom{7}{1} = 1 + 7 = 8\) ord, så
Likhet — de \(16\) kloten täcker alla \(128\) ord i \((\mathbb{Z}_2)^7\) exakt. Varje mottaget ord ligger inom avstånd \(1\) från precis ett kodord, så enkelfelsrättning träffar aldrig ett tvetydigt fall. Det är vad "perfekt" betyder, gjort konkret.
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)\).
Generatormatriser och kodning¶
En kontrollmatris testar medlemskap; en generatormatris producerar kodord. Det är en \(k \times n\)-matris \(G\) vars rader är en bas för \(C\), så varje kodord är en kombination av dem — att koda ett \(k\)-bitars meddelande \(\mathbf{m}\) är en enda matrisprodukt:
När \(\mathbf{m}\) löper över alla \(2^k\) meddelanden löper \(\mathbf{c}\) över alla \(2^k\) kodord. De två matriserna är två vyer av samma kod och är länkade genom
— varje genererat kodord klarar kontrollen, vilket är precis påståendet att raderna i \(G\) ligger i \(\ker A\). En systematisk generator \(G = [\,I_k \mid P\,]\) är den bekväma formen: de första \(k\) bitarna i varje kodord är meddelandet självt (kopierat av \(I_k\)) och de sista \(n-k\) är paritetskontroller (beräknade av \(P\)). Avkodning läser sedan bara av meddelandet från början.
Syndromavkodning¶
För en kod given av en kontrollmatris finns en avkodningsmetod långt smartare än att jämföra det mottagna ordet mot alla \(2^k\) kodord. Given ett mottaget ord \(\mathbf{r}\), beräkna dess syndrom:
- Om \(\mathbf{s} = \mathbf{0}\) är \(\mathbf{r}\) ett giltigt kodord — acceptera det.
- Om \(\mathbf{s} \neq \mathbf{0}\) inträffade ett fel. Avgörande nog beror syndromet enbart på felmönstret, inte på vilket kodord som skickades: om \(\mathbf{r} = \mathbf{c} + \mathbf{e}\) så är \(A\mathbf{r}^{\top} = A\mathbf{c}^{\top} + A\mathbf{e}^{\top} = A\mathbf{e}^{\top}\), eftersom kodord har noll-syndrom. Så syndromet fingeravtrycker felet, och du rättar genom att hitta det lättaste \(\mathbf{e}\) med det syndromet.
Varför detta är Hamming-kodernas eleganta fall
Arrangera kontrollmatrisen så att dess kolumner är de binära talen \(1\) till \(n\) i ordning. Då är syndromet för ett enbits-fel i position \(p\) exakt kolumn \(p\) — dvs. den binära siffran för \(p\). Syndromet stavar bokstavligen ut felets position. Ingen sökning: läs syndromet som ett tal, vänd den biten.
Löst: enkelfelsrättning med Hamming-koden \([7,4]\)
Ta kontrollmatrisen vars kolumner är \(1,2,\dots,7\) i binär form (översta raden = \(4\)-biten):
Anta att du tar emot \(\mathbf{r} = 1001101\) (bitarna \(r_1 \dots r_7\)). Beräkna syndromet — varje rad i \(A\) plockar ut positionerna med en \(1\) och summerar dem mod \(2\):
Så \(\mathbf{s} = (s_1,s_2,s_3) = (1,1,1)\), vilket läst som en binär siffra (översta raden \(4\)-biten) är \(111 = 7\). Felet är i position \(7\). Vänd \(r_7\) från \(1\) till \(0\):
Kontrollera rättningen: det nya syndromet är \((0,0,0)\), så \(\mathbf{c}\) är ett äkta kodord. En matrisprodukt lokaliserade och rättade felet — ingen jämförelse mot de \(16\) kodorden behövdes. Att "syndromet namnger den trasiga biten" är hela tjusningen med konstruktionen.
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 |