Varför fungerar CD-skivor fortfarande även med repor? Hur kan Voyager 1 skicka data från 24 miljarder kilometer bort genom rymdstörningar? Kodningsteori löser problemet att sända information korrekt över opålitliga kanaler. Genom att lägga till redundant information smart kan vi detektera och korrigera fel automatiskt - från QR-koder till wifi-överföring.

Fördjupning

Kodningsteori utvecklar metoder för att detektera och korrigera fel i dataöverföring och lagring. Hamming-avstånd mäter skillnader mellan kodord. Linear codes använder algebraiska strukturer för effektiv kodning/avkodning. Reed-Solomon koder skyddar allt från CD-skivor till satellitdata. Moderna koder som LDPC närmar sig Shannon-gränsen för kanalkapacitet.

Grundläggande feldetektering

Simplaste feldetektering lägger till paritetsbit: jämnt antal 1:or i kodord. Single parity kan detektera udda antal fel men inte korrigera. Checksum och CRC (Cyclic Redundancy Check) ger starkare feldetektering. Kodningsteorins mål: maximera felavgörande med minimal redundans.

Paritetsbit exempel

7-bit ASCII med jämn paritet:

'A' = 1000001 → paritetsbit = 1⊕0⊕0⊕0⊕0⊕0⊕1 = 0

Kodord: 10000010 (8 bitar)

'B' = 1000010 → paritetsbit = 1⊕0⊕0⊕0⊕0⊕1⊕0 = 0

Kodord: 10000100

Feldetektering:

Mottaget: 10000110 (fel i position 2)

Paritet: 1⊕0⊕0⊕0⊕0⊕1⊕1⊕0 = 1 ≠ 0

→ Fel detekterat!

Begränsning: Kan inte detektera jämnt antal fel

Exempel: 10000110 → 10001110 (2 fel) har korrekt paritet

Hamming-koder och avstånd

Hamming-avstånd d(x,y) räknar antal positioner där x och y skiljer sig. Minimum Hamming-avstånd d för kod avgör feldetekterings/korrigeringsförmåga: kan detektera d-1 fel och korrigera ⌊(d-1)/2⌋ fel. Hamming-koder är första konstruktionen som kan korrigera 1-bit fel.

Hamming(7,4) kod konstruktion

Hamming(7,4): 4 databitar → 7 totalbitar med 1-fel-korrigering

Paritetsmatrix H (3×7):

H = [0 0 0 1 1 1 1]

[0 1 1 0 0 1 1]

[1 0 1 0 1 0 1]

Kodning av data d = [d₁ d₂ d₃ d₄]:

1. Placera databitar: [d₁ d₂ d₃ _ d₄ _ _]

2. Beräkna paritetsbitriar p₁,p₂,p₃:

p₁ = d₁ ⊕ d₃ ⊕ d₄ (position 4)

p₂ = d₂ ⊕ d₃ ⊕ d₄ (position 6)

p₃ = d₁ ⊕ d₂ ⊕ d₄ (position 7)

Exempel d = [1 0 1 1]:

p₁ = 1⊕1⊕1 = 1, p₂ = 0⊕1⊕1 = 0, p₃ = 1⊕0⊕1 = 0

Kodord: [1 0 1 1 1 0 0]

Linjära koder och generatormatriser

Linjär kod är undertum av vektorrum F₂ⁿ. Generatormatris G kodar meddelanden: c = mG. Paritetsmatrix H kontrollerar: Hc^T = 0 för giltiga kodord. Systematisk form [I|P] gör kodning/avkodning enkel. Dual kod har paritetsmatris som generatormatris för ursprungskoden.

Systematisk Hamming(7,4) kod

Generatormatris i systematisk form G = [I₄|P]:

G = [1 0 0 0 | 0 1 1]

[0 1 0 0 | 1 0 1]

[0 0 1 0 | 1 1 0]

[0 0 0 1 | 1 1 1]

Paritetsmatris H = [P^T|I₃]:

H = [0 1 1 1 | 1 0 0]

[1 0 1 1 | 0 1 0]

[1 1 0 1 | 0 0 1]

Kodning: m = [1 0 1 1] → c = mG = [1 0 1 1 0 0 1]

Feldetektering: s = Hc^T kallas syndrom

Om s = 0: inget fel

Om s ≠ 0: s pekar på felposition (kolumn i H)

Reed-Solomon koder

Reed-Solomon (RS) koder arbetar över ändliga kroppar GF(q) och kan korrigera burst-fel. Baserad på polynominterpolation: k datapunkter definierar unikt polynom av grad k-1. Evaluera i n > k punkter för redundans. Kan korrigera t fel om n - k ≥ 2t. Används i CD, DVD, QR-koder.

Reed-Solomon exempel över GF(7)

RS(6,3) över GF(7) med α = 3 (primitiv rot):

Kodning av meddelande m = [2, 1, 4]:

1. Skapa polynom: f(x) = 2 + 1x + 4x² (mod 7)

2. Evaluera i α⁰, α¹, ..., α⁵:

f(1) = 2 + 1 + 4 = 0 (mod 7)

f(3) = 2 + 3 + 4·9 = 2 + 3 + 1 = 6 (mod 7)

f(2) = 2 + 2 + 4·4 = 2 + 2 + 2 = 6 (mod 7)

osv...

Kodord: [0, 6, 6, 1, 3, 5]

Felkorrigering: Kan korrigera ⌊(6-3)/2⌋ = 1 fel

Använd Berlekamp-Massey algoritm för att hitta felpolynom

Lagrange interpolation för att rekonstruera ursprungspolynom

Cykliska koder och CRC

Cyklisk kod: om (c₀,c₁,...,cₙ₋₁) är kodord, då är också (cₙ₋₁,c₀,c₁,...,cₙ₋₂). Definieras av generatorpolynom g(x) som delar xⁿ-1. CRC använder cykliska koder för feldetektering i nätverk och lagring. Effektiv hårdvaruimplementering med skiftregister.

CRC-8 beräkning

CRC-8 med generatorpolynom g(x) = x⁸ + x² + x + 1

Binärt: 100000111

Meddelande: 11010011 (8 bitar)

CRC beräkning:

1. Skifta meddelande 8 steg vänster: 1101001100000000

2. Dividera med g(x) = 100000111:

11010011 | 100000111

100000111

---------

001001000 → fortsätt division...

Rest (CRC): 01001110

Skicka: meddelande + CRC = 11010011 01001110

Mottagaren dividerar hela meddelandet med g(x)

Om rest = 0: inget fel detekterat

Om rest ≠ 0: fel detekterat

Moderna koder och Shannon-gränsen

Shannon's channel coding theorem visar fundamental gräns för felfri kommunikation. Kanalkapacitet C definierar max informationshastighet. Turbo codes och LDPC (Low-Density Parity-Check) codes närmar sig Shannon-gränsen. Används i modern telekommunikation som 4G/5G och WiFi.

LDPC kod princip

LDPC: paritetsmatrix H har få 1:or per rad/kolumn

Exempel H (3×6) för LDPC(6,3):

H = [1 1 0 1 0 0]

[0 1 1 0 1 0]

[1 0 1 0 0 1]

Fördelar:

· Iterativ avkodning (belief propagation)

· Nära Shannon-gränsen för långa koder

· Paralleliserbar hårdvaruimplementering

Tanner graf representation:

· Variabelnoder (kodordspositioner)

· Kontrollnoder (paritetsekvationer)

· Kanter från H-matrisens 1:or

Avkodning:

· Iterativ meddelandepassning

· Soft-decision information

· Konvergens till ML-avkodning

Vanliga misstag

❌ Förväxla detektering med korrigering

Feldetektering kräver mindre redundans än felkorrigering

Exempel: Enkel paritet detekterar 1 fel men kan inte korrigera det

❌ Underskatta burst-fel

Många fysiska kanaler ger korrelerade fel, inte oberoende

Exempel: Hamming-koder dåliga för burst-fel, Reed-Solomon bättre

❌ Ignorera complexity av avkodning

Optimal avkodning kan vara NP-svår för allmänna koder

Exempel: Maximum likelihood decoding är exponentiell utan struktur

Tillämpningar

Digital lagring

CDs, DVDs, SSD-minnen använder Reed-Solomon och BCH-koder

Exempel: CD använder Reed-Solomon för att korrigera repor och damm

Trådlös kommunikation

WiFi, 4G, 5G använder LDPC och turbo codes

Exempel: 802.11n WiFi använder LDPC för högre datahastigheter

Satelliter och rymdsonder

Långdistans kommunikation kräver kraftfull felkorrigering

Exempel: Mars Rover använder Reed-Solomon + konvolutional coding

Övningar

1 Lätt

Beräkna Hamming-avstånd mellan kodorden 1011001 och 1110100. Hur många fel kan detekteras/korrigeras?

Tips

Räkna positioner där bitarna skiljer sig

Visa facit

Svar: d = 4. Kan detektera 3 fel, korrigera 1 fel

Förklaring: Positioner 2,3,6,7 skiljer sig. Med d=4 kan detektera d-1=3 fel och korrigera ⌊(d-1)/2⌋=1 fel

2 Medel

Koda meddelandet [1,0,1,1] med Hamming(7,4) generatormatrisen från exemplet.

Tips

Multiplicera meddelandet med generatormatrisen G

Visa facit

Svar: Kodord: [1,0,1,1,0,0,1]

Förklaring: c = mG = [1,0,1,1] · G ger kodordet genom matrixmultiplikation

3 Medel

Förklara varför Reed-Solomon koder är bättre för burst-fel än Hamming-koder.

Tips

Tänk på hur fel är fördelade och korrigeringsförmågan

Visa facit

Svar: RS arbetar över större alfabet, så 1 symbolfel = många bitfel. Hamming korrigerar bara 1 bitfel

Förklaring: Reed-Solomon kan korrigera t symbolfel oavsett burst-längd inom symbol, medan Hamming bara korrigerar enstaka bitar

Sammanfattning

Kodningsteori utvecklar metoder för pålitlig informationsöverföring över störda kanaler. Hamming-avstånd bestämmer fel-detekterings/korrigeringsförmåga. Linjära koder använder generator- och paritetsmatriser för systematisk kodning. Reed-Solomon koder korrigerar burst-fel genom polynom över ändliga kroppar. Cykliska koder och CRC ger effektiv feldetektering. Moderna LDPC och turbo codes närmar sig Shannon-gränsen. Kodningsteori är kritisk för digital lagring, trådlös kommunikation och rymdforskning.