Felrättande kodning

Radiokanalen är full av brus, fädning och störningar, så en del av de bitar som sänds kommer fram vända. Felrättande kodning (eng. channel coding, forward error correction, FEC) löser det genom att sändaren medvetet lägger till extra bitar, redundans, enligt en regel som mottagaren känner till. Med regeln kan mottagaren upptäcka och ofta rätta fel utan att be om omsändning. Det är därför en mobil kan hålla en länk fast en märkbar andel av de mottagna bitarna är fel före avkodningen, och därför en amatör kan avkoda en FT8-signal som ligger under bruset. Artikeln går från de enklaste metoderna till de koder som används i 5G, och räknar på exempel.

Varför kodning behövs#

Shannon visade 1948 att det för varje datatakt under kanalens kapacitet $C$ (se kanalkapacitet) finns koder som ger så små fel man vill, om blocken görs tillräckligt långa. Satsen säger inte hur koderna ser ut, och jakten på praktiska koder har pågått i över sjuttio år.

Utan kodning kan felfrekvensen bara sänkas med högre effekt. Okodad BPSK behöver $E_b/N_0\approx \mathrm{9,6}$ dB för bitfelsfrekvensen ${10}^{-5}$ (se digital modulation och brus och signal–brusförhållande). Med en bra kod nås samma kvalitet vid ca 1–4 dB, vilket sparar mer än en faktor tre i effekt. Priset är att varje databit följs av extra bitar: med kodtakten $R=k/n$ går $1/R$ gånger fler bitar över kanalen, vilket kräver mer bandbredd eller en modulation med fler bitar per symbol.

Två strategier kombineras. FEC (forward error correction) rättar felen i mottagaren utan återkoppling, och är det enda som går vid envägssändning (DAB, tv, GPS) eller lång fördröjning (rymdsonder). ARQ (automatic repeat request) upptäcker fel och ber om omsändning, vilket kräver en returkanal. Mobilnäten och Wi-Fi använder båda. Figur 1 visar var kodningen sitter i kedjan.

Upptäcka fel: paritet och CRC#

Det enklaste skyddet är en paritetsbit: en extra bit som väljs så att antalet ettor i ordet blir jämnt. Ordet 1011 får paritetsbiten 1 och sänds som 10111. Om en enda bit vänds blir antalet ettor udda och mottagaren ser att något är fel, men inte vilken bit. Två fel upphäver varandra och passerar obemärkta, så en paritetsbit upptäcker bara ett udda antal fel.

En CRC (cyclic redundancy check, cyklisk redundanskontroll) är ett kraftfullare sätt att göra detsamma. Meddelandet tolkas som ett polynom över talen 0 och 1, förskjuts $r$ steg och divideras med ett generatorpolynom av grad $r$, där all aritmetik görs modulo 2 (addition är XOR). Resten, $r$ bitar, läggs till efter meddelandet. Mottagaren dividerar hela ordet och får resten noll om inget är fel.

Divisionen i exemplet, rad för rad. Varje steg XOR:ar 1011 mot de fyra bitar som står rakt under, och det upprepas tills alla bitar utom de tre sista är nollor:

11010011101100000   meddelande + 000
1011
01100011101100000
 1011
00111011101100000
  1011
00010111101100000
   1011
00000001101100000
       1011
00000000110100000
        1011
00000000011000000
         1011
00000000001110000
          1011
00000000000101000
           1011
00000000000000100   rest: 100

En CRC med $r$ bitar upptäcker alla felskurar (flera fel i följd) upp till längden $r$, och för slumpmässiga fel är sannolikheten att ett fel slinker igenom ungefär $2^{-r}$. Med $r=3$ är det 1 på 8, vilket är för dåligt i praktiken, men med $r=16$ blir det ca 1 på 65 000 och med $r=32$ ungefär 1 på fyra miljarder. Därför används CRC med 16, 24 eller 32 bitar i Ethernet, Wi-Fi, Bluetooth och mobilnät. I 5G NR ligger CRC på både transportblock och kodblock, och kontrollkanalerna har 24 bitar (nedlänk) eller 11 respektive 6 bitar (upplänk).² En CRC rättar inget, men talar om att avkodaren misslyckades och att ARQ behövs.

Blockkoder och Hamming-avstånd#

En blockkod $(n,k)$ gör $k$ databitar till ett kodord på $n$ bitar. Av de $2^n$ möjliga orden är bara $2^k$ giltiga kodord. Hamming-avståndet mellan två ord är antalet positioner där de skiljer sig, och koden har minsta avstånd $d_{\mathrm{m}\mathrm{i}\mathrm{n}}$ om alla par av kodord skiljer sig i minst så många positioner. Tänk på kodorden som punkter i ett rum. Varje bitfel flyttar det mottagna ordet ett steg bort från det sända kodordet. Så länge ordet fortfarande ligger närmare det sända kodordet än något annat kodord, och det gäller om högst $t=\lfloor (d_{\mathrm{m}\mathrm{i}\mathrm{n}}-1)/2\rfloor$ fel inträffat, blir rätt kodord det närmaste, och avkodning är att välja det. I stället för att rätta kan koden upptäcka upp till $d_{\mathrm{m}\mathrm{i}\mathrm{n}}-1$ fel.

Hamming(7,4)#

Richard Hamming konstruerade 1950 en kod som rättar ett fel: Hamming-koden. Varianten $(7,4)$ lägger tre paritetsbitar till fyra databitar. Bitarna numreras 1–7, och de tre paritetsbitarna placeras på platserna 1, 2 och 4, de som är potenser av två. Varje paritetsbit kontrollerar de platser vars nummer, skrivet binärt, har motsvarande bit satt: $p_1$ (plats 1) platserna 1, 3, 5, 7, $p_2$ (plats 2) platserna 2, 3, 6, 7 och $p_3$ (plats 4) platserna 4, 5, 6, 7. Varje kontroll väljs så att antalet ettor bland dess platser blir jämnt. Figur 2 visar samma sak som ett Venn-diagram: tre cirklar, en per kontroll, där databitarna ligger i överlappen och paritetsbitarna i de delar som bara tillhör en cirkel.

Matematiskt är kontrollerna en matris. Kolumn $j$ i $𝐇$ är talet $j$ skrivet binärt, och ett mottaget ord $𝐫$ ger syndromet $𝐬=𝐇{𝐫}^T$ (modulo 2):

Syndromet är noll för alla giltiga kodord, och för ett ord med ett fel i plats $j$ blir det kolumn $j$. Därför pekar syndromet direkt på felet. Det finns 16 kodord av 128 möjliga ord, och varje ord som inte är ett kodord ligger exakt ett steg från ett kodord. Koden kallas perfekt: $2^4(1+7)=2^7$, så inga ord är över. Lägger man till en extra paritetsbit över hela ordet får man den utökade Hamming-koden $(8,4)$ med $d_{\mathrm{m}\mathrm{i}\mathrm{n}}=4$, som rättar ett fel och upptäcker två. Varianter av den, till exempel $(72,64)$, används i datorminnen med felrättning (ECC-minne).

Hamming publicerade koden 1950, två år efter Shannons artikel. Därefter följde Reed–Solomon (1960), LDPC (1962), Viterbi (1967), turbokoder (1993) och polära koder (2009).

Reed–Solomon: koder för skurar#

En Reed–Solomon-kod (RS) räknar inte med bitar utan med symboler på $m$ bitar, till exempel byte, och bygger på polynom över en ändlig kropp $GF(2^m)$. En kod $\mathrm{R}\mathrm{S}(n,k)$ har $n\le 2^m-1$ symboler, $k$ av dem data, och $n-k=2t$ paritetssymboler. Den rättar upp till $t$ felaktiga symboler, och ett fel i en symbol räknas lika oavsett om en eller alla åtta bitar i symbolen är fel. Det gör den utmärkt mot felskurar. Dess minsta avstånd $d_{\mathrm{m}\mathrm{i}\mathrm{n}}=n-k+1$ är det största möjliga för sin längd (en så kallad MDS-kod).

Exempel: $\mathrm{R}\mathrm{S}(255,223)$ över $GF(256)$ har 32 paritetssymboler och rättar upp till $t=16$ felaktiga byte. Kodtakten är $223/255=\mathrm{0,875}$. Samma familj finns i CD-skivan (två Reed–Solomon-koder med interleaving, CIRC, som rättar repor), i QR-koder, i första generationens digital-tv DVB-T ($\mathrm{R}\mathrm{S}(204,188)$, $t=8$), i DAB+ (se DAB+ och digital-tv) och i trafiksättet JT65 för jord–måne–jord-förbindelser ($\mathrm{R}\mathrm{S}(63,12)$).³

Reed–Solomon ensam klarar inte lika låga signal–brusförhållanden som de koder som följer. Därför används den ofta som yttre kod i en sammansatt kod: en faltningskod eller LDPC-kod tar hand om det mesta, och Reed–Solomon städar upp felskurar som blir kvar. Så är DVB-T och många rymdlänkar byggda.

Faltningskoder och Viterbi-avkodning#

Blockkoder tar ett block i taget. En faltningskod (eng. convolutional code) är i stället en ström: varje ny databit skiftas in i ett litet register, och flera utbitar räknas ut från registrets innehåll. Koden i figur 3 har takt $1/2$, tre bitars register (tvångslängd $K=3$) och två utbitar $v_1$ och $v_2$. De ges av generatorerna 111 och 101, vilket oktalt skrivs $(7,5)$. Varje databit ger alltså två kodbitar, och de två senaste databitarna bestämmer kodarens tillstånd: fyra möjliga.

Kodning är att följa en väg genom tillstånden. Matar man in 1 0 1 1 följt av två avslutande nollor (en svans, som tömmer registret) får man paren 11 10 00 01 01 11. Svansen kostar några bitar, men gör att kodordet slutar i nolltillståndet, vilket mottagaren utnyttjar. Det fria avståndet $d_{\mathrm{f}\mathrm{r}\mathrm{e}\mathrm{e}}$ är det minsta antalet skillnader mellan två olika vägar som startar och slutar i samma tillstånd. För koden $(7,5)$ är $d_{\mathrm{f}\mathrm{r}\mathrm{e}\mathrm{e}}=5$, så den rättar två fel som ligger nära varandra.

Viterbi-algoritmen#

Mottagaren ska hitta den väg genom tillstånden vars kodbitar ligger närmast det mottagna. Antalet vägar fördubblas för varje ny bit. Viterbi-algoritmen (1967) undviker explosionen: leder två vägar till samma tillstånd vid samma tid kan den sämre aldrig bli en del av den bästa vägen, så den kastas direkt. I varje tillstånd behövs bara en överlevare och en metrik, summan av alla avvikelser längs vägen.

Antalet tillstånd är $2^{K-1}$ och arbetet per bit växer i samma takt. En kod med $K=7$ har 64 tillstånd, och är en av de mest använda faltningskoderna: generatorerna $(133,171)$ oktalt, takt $1/2$, finns i Wi-Fi (IEEE 802.11a/g/n), DVB och många satellitlänkar. Dess fria avstånd är 10, så den rättar upp till fyra tätt liggande fel. För mycket långa koder är Viterbi omöjlig. Trafiksättet WSPR använder en faltningskod med tvångslängd 32, vilket skulle ge över två miljarder tillstånd, och avkodas därför med en annan metod (sekventiell avkodning, Fanos algoritm) som bara följer de mest lovande vägarna.³

Högre takt än 1/2 fås genom punktering: en del av kodbitarna stryks efter ett fast mönster, och mottagaren sätter in platshållare. Då fås takter som 2/3 och 3/4 från samma 1/2-kod med samma avkodare, vilket Wi-Fi och DVB gör.

Mjuka beslut#

Hittills har demodulatorn gjort ett hårt beslut för varje bit: 0 eller 1. Men en mottagen spänning nära gränsen mellan symbolerna är mycket osäkrare än en som ligger långt in i ett beslutsområde. Ett mjukt beslut behåller den informationen, normalt som ett log-likelihood-förhållande (LLR). För BPSK med brusvarians ${\sigma }^2$ och mottagen spänning $y$ är

Tecknet säger vilken bit som är mest sannolik, och beloppet hur säker den är. Viterbi-avkodaren använder då avstånd i spänning i stället för antal skilda bitar. Det ger ungefär 2 dB bättre än hårda beslut för den här typen av kod (2,4 dB i figur 6), och mjuka värden är utgångspunkten för alla moderna iterativa avkodare. Därför behöver demodulatorn ha en mjuk utgång och inte bara en bitström.

Interleaving: sprid ut skurarna#

De flesta koder är byggda för spridda fel, men radiokanalen ger fel i skurar: ett fädningsdjup, en störpuls eller ett kort avbrott slår ut flera bitar i följd. En interleaver (omflätare) blandar bitordningen före sändning, så att kodbitar som hör ihop hamnar långt från varandra i tid, och mottagaren ordnar om dem igen. En skur i kanalen blir då spridda fel som koden klarar.

Den enklaste varianten är ett blockinterleaver: bitarna skrivs in i en matris rad för rad och läses ut kolumn för kolumn. Figur 5 visar fyra kodord av Hamming(7,4), som var och en rättar ett fel. En skur på fyra bitar i följd förstör två av orden (vart och ett får två fel) om bitarna sänds ord för ord. Med interleaving ger samma skur ett fel i varje ord, och alla fyra rättas.

Priset är fördröjning: mottagaren måste vänta in hela blocket. En interleaver som ska klara en skur på $B$ bitar med en kod som rättar $t$ fel per kodord behöver ett djup på minst $B/t$ kodord. I rundradio går det bra med lång fördröjning och djup interleaving, men i telefoni och i datalänkar med krav på låg fördröjning måste den hållas kort.

Kodningsvinst och Shannons gräns#

Kodningsvinsten är skillnaden i $E_b/N_0$ (se brus och signal–brusförhållande) som krävs för samma bitfelsfrekvens utan och med kod. Figur 6 jämför fyra system med BPSK i en brusig kanal (AWGN), alla beräknade för den här artikeln: okodad BPSK, Hamming(7,4) med hårda beslut och faltningskoden $K=7$ med hårda respektive mjuka beslut. Hamming-kurvan är exakt: felen i de avkodade databitarna är summerade över alla 128 möjliga felmönster. Kurvorna för faltningskoden är unionsgränser, övre gränser byggda på kodens avståndsspektrum, som blir mycket noggranna vid låga felfrekvenser.

Siffrorna vid BER ${10}^{-5}$ finns i tabell 1.

Tabell 1. Eb/N0 för bitfelsfrekvensen ${10}^{-5}$, BPSK på AWGN-kanal. Alla värden utom turbokoden är beräknade för den här artikeln.

Tre saker syns. Hamming(7,4) ger knappt något vid hård avkodning: redundansen betyder att varje kodbit får mindre energi, och det äter nästan upp vinsten. Under ca 6 dB är den sämre än okodat. Mjuka beslut ger 2,4 dB extra i faltningsexemplet. Och det är ett stort glapp mellan faltningskoden och gränsen, 4,2 dB mot 0,19 dB, som de bästa moderna koderna stänger till ca en halv dB.

Turbokoder och LDPC#

Faltningskoden $K=7$ ligger ca 4 dB från gränsen. År 1993 presenterade Berrou, Glavieux och Thitimajshima turbokoder som rapporterades nå $E_b/N_0=\mathrm{0,7}$ dB vid BER ${10}^{-5}$ med takt 1/2, ca 0,5 dB från gränsen.¹ En turbokod består av två enkla faltningskodare som kodar samma data, där den ena får bitarna i en blandad ordning (en lång interleaver). Mottagarens två avkodare skickar mjuk information fram och tillbaka och förfinar gissningen för varje iteration, som en turbomotor som återanvänder sin utgång. Turbokoder användes för data i 3G (UMTS/HSPA) och 4G (LTE).

LDPC-koder (low-density parity-check) uppfanns av Robert Gallager i början av 1960-talet och glömdes bort, eftersom datorerna då var för små. De återupptäcktes på 1990-talet. En LDPC-kod definieras av en paritetsmatris $𝐇$ med mycket få ettor, så varje kontroll gäller bara några få bitar. Ett ord $𝐜$ är ett kodord om $𝐇{𝐜}^T=\mathbf{0}$. Matrisen ritas som en Tannergraf med en nod per bit och en per kontroll, och en kant där matrisen har en etta (figur 7). Hamming-koden är en liten sådan graf. En LDPC-kod har i stället tusentals noder med bara några kanter vardera, och avkodas iterativt: bit- och kontrollnoderna skickar sannolikheter till varandra över kanterna (meddelandeöverföring, belief propagation, ofta i den förenklade formen min-sum) tills alla kontroller stämmer. Arbetet växer linjärt med blocklängden och kan göras parallellt, vilket passar moderna kretsar.

LDPC-koder används i DVB-S2 och DVB-T2 (tillsammans med en BCH-kod), i Wi-Fi (sedan IEEE 802.11n), i 10 Gbit/s-Ethernet över tvinnat par, i FT8 och i 5G NR. FT8 använder $(174,91)$: 77 meddelandebitar och 14 bitar CRC blir 91 bitar som kodas till 174 (se Digitala trafiksätt).

LDPC i 5G NR#

För att samma hårdvara ska klara många blockstorlekar är 5G:s LDPC-kod kvasicyklisk. Den definieras av en liten basgraf, en matris med ettor och nollor, där varje etta ersätts av en cyklisk förskjutning av enhetsmatrisen i storleken $Z\times Z$ och varje nolla av en nollmatris. Talet $Z$ kallas lyftstorlek och kan väljas bland 51 värden mellan 2 och 384.² Det finns två basgrafer:

Tabell 2. LDPC-koden i 5G NR (3GPP TS 38.212). Värden från en översiktsartikel, kontrollerade bara mot den.

Med $Z=384$ har BG1 $46·384=17664$ rader och $68·384=26112$ kolumner, och $22·384=8448$ kolumner är informationsbitar. De två första kolumnerna sänds inte, så kodordet är $66·384=25344$ bitar långt och takten $8448/25344=1/3$. Basgraf väljs efter transportblockets storlek $A$ och kodtakten $R$: BG2 används om $A\le 292$, eller om $A\le 3824$ och $R\le \mathrm{0,67}$, eller om $R\le \mathrm{0,25}$. Annars används BG1. Större block delas upp i flera kodblock, och sedan anpassas kodordet till radioresursen (rate matching).

Polära koder#

De polära koderna presenterades av Erdal Arıkan 2009 och var de första explicita koder som bevisligen når kanalens kapacitet med en avkodningskomplexitet som bara växer ungefär som $N\log N$ för blocklängden $N$. Idén är kanalpolarisering. Tar man två oberoende kopior av en brusig kanal och kombinerar deras ingångar med en XOR, blir den ena av de två nya, syntetiska kanalerna sämre än originalet och den andra bättre. Upprepar man det $n$ gånger för $N=2^n$ kanaler, blir nästan alla kanaler antingen mycket bra eller mycket dåliga, medan summan av kapaciteterna är oförändrad.

Det är enklast att se i en raderingskanal, där en bit antingen kommer fram eller går förlorad med sannolikheten $\epsilon$. De två nya kanalerna har då raderingssannolikheterna

För $\epsilon =\mathrm{0,5}$ ger ett steg 0,75 och 0,25, och tre steg ($N=8$) ger de åtta värdena i figur 9. Summan av kapaciteterna $1-\epsilon$ är hela tiden 4 bitar. Längre koder polariserar tydligare (figur 8): för $N=1024$ har 37 % av delkanalerna kapacitet över 0,99, 37 % under 0,01, och bara en fjärdedel ligger däremellan.

Koden är sedan enkel att bygga: data skickas på de $K$ bästa delkanalerna och en fast, känd nolla (fryst bit) på de övriga, så takten är $K/N$. Kodaren är ett nätverk av XOR-grindar, en butterfly (figur 9): $𝐱=𝐮{𝐆}_N$ med ${𝐆}_N={𝐅}^{\otimes n}$ och $𝐅=\left(\begin{array}{cc}1& 0\\ 1& 1\end{array}\right)$.

Avkodning sker med successiv cancellering (SC): avkodaren bestämmer $u_0,u_1,\dots$ i tur och ordning och använder tidigare beslut för att avgöra nästa. Frysta bitar är kända. SC är enkel men sårbar, eftersom ett tidigt fel sprider sig, så man använder listavkodning (SCL) som behåller flera kandidater, och en CRC som talar om vilken kandidat som är rätt (CA-SCL). Därför finns CRC-bitar även i korta kontrollmeddelanden.

I 5G NR används polära koder för kontrollkanalerna: nedlänkens kontrollinformation (DCI), upplänkens (UCI, när meddelandet är tillräckligt långt) och sändningskanalen BCH.² Kodlängden är $N=2^n$ med $n$ från 5 till 9 i nedlänk ($N$ upp till 512) och upp till 10 i upplänk ($N$ upp till 1 024), och lägsta kodtakt är 1/8. Mycket små meddelanden skyddas i stället av enkla blockkoder, och vilka delkanaler som är bäst anges av en fast tabell i specifikationen. Polära koder passar korta block med höga krav på tillförlitlighet, LDPC långa block med hög datatakt. Se vidare 5G NR och Så fungerar ett mobilnät.

ARQ och HARQ#

Om CRC:n visar fel kan mottagaren be om en ny sändning, ARQ. Det ger säker leverans, men fördröjningen växer med antalet omsändningar. HARQ (hybrid ARQ) kombinerar FEC och ARQ: mottagaren kastar inte det felaktiga blocket utan sparar de mjuka värdena. Vid omsändning skickas samma kodbitar (Chase-kombination) eller andra, tidigare osända bitar av samma kodord (inkrementell redundans), och mottagaren lägger ihop allt. Det fungerar som en kod med lägre takt som byggs upp bara när det behövs. Mobilnäten använder HARQ med flera parallella processer, så att sändaren kan skicka nya block medan den väntar på svar. Tillsammans med snabb länkanpassning (val av modulation och kodtakt efter kanalens kvalitet, se kanalkapacitet) kan länken arbeta nära sin kapacitet med få omsändningar.

Kontrollfrågor#