Faltningskodare

Faltningskodare är en slags tillståndsmaskin som kodar datapaket så att de utgående bitarna beror på de inkommande och de tidigare bitarna. Detta sker genom modulo2-addering, det vill säga via XOR-grindar. Denna typ av kodning fungerar bra till att upptäcka och rätta till fel i efterhand, och den är enkel att implementera. En nackdel med den är att det är komplicerat att avkoda den.

Teori

En faltningskodare med två tidigare värden sparade i ett skiftregister.

En faltningskodare består av XOR-grindar och ett skiftregister som sparar de tidigare tillstånden, det vill säga de senast inkomna bitarna. De inkommande databitarna modulo2-adderas med de bitar som är sparade i skiftregistret. Därefter släpps två bitar ut för varje inbit. Ett jämnt antal ettor som adderas ger svaret 0 medan ett ojämnt antal ger svaret 1.

Exempel

Om man låter följande insekvens 1100 kodas i faltningskodaren på bilden och kodar från vänster till höger sker följande steg (där den fullständiga utsekvensen står underst):

1. Skiftregistrerna T1 och T2 är tomma vid start och står därför på 0
2. När 1 kommer till XOR-grindarna adderas 1+0+0=1 på Utdata 1 och 1+0=1 på utdata 2.
3. 1 kommer därnäst. Nu har första ettan flyttat sig till T1 och T2 är fortfarande noll. Därför adderas 1+1+0=0 och till utdata 2 blir det 1+0=1.
4. Vid nästa steg har både T1 och T2 fått tillståndet 1, och nu kommer en 0:a. Detta ger att utdata 1 blir 0+1+1=0 och utdata 2 blir 0+1=1
5. Sista 0 kommer nu, och T1 har då en nolla och T2 en etta. Då blir utdata 1 följande: 0+0+1=1 och utdata 2 blir 0+1=1
6. Den fullständiga utsekvensen: 11 01 01 11

Man kan även läsa sekvensen från höger till vänster, vilket ger ett annat resultat. Därför måste det vara fördefinierat vilken bit som är först.

Avkodning

För att avkoda ett faltningskodat ord använder man Viterbis algoritm med hjälp av ett trellisdiagram.