Cyklisk kod

Cykliska koder tillhör antalet block systematiska koder där varje kombination kodas oberoende (i form av ett block) på ett sådant sätt att information k och kontroll t symboler alltid finns

klä på vissa ställen. Möjligheten att upptäcka och korrigera nästan alla fel med en relativt låg redundans i jämförelse med andra koder, liksom enkelheten i kretsimplementeringen av kodnings- och avkodningsutrustningen har gjort dessa koder utbredda. Teorin om cykliska koder bygger på teorin om grupper och polynomalgebra över Galois -fältet.

Cyklisk kod - en kod i vilken ordningen för distribution av kodkombinationer utförs på ett sådant sätt att när Hammar -kodavståndet passerar från en kombination till det intilliggande, förblir det konstant varje gång.

Cykliska koder är en hel familj av felkorrigerande koder, som inkluderar Hamming-koder som en av sorterna, men generellt ger större flexibilitet när det gäller möjligheten att implementera koder med den nödvändiga förmågan att upptäcka och korrigera fel som uppstår vid överföring av kodkombinationer över en kommunikationskanal. Den cykliska koden hänvisar till systematiska block (n, k) -koder, i vilka de första k bitarna är en kombination av den primära koden, och de efterföljande (n? K) bitarna är kontroller.

Konstruktionen av cykliska koder är baserad på att dividera det överförda kodordet med det genererande oreducerbara polynomet av grad r. Resten av divisionen används för att bilda kontrollsiffror. I detta fall föregås divisionsoperationen av en multiplikationsoperation som förskjuter k-bitars informationskodkombination till vänster med r-bitar.

Ett polynom (polynom) som kan representeras som en produkt av polynom med lägre grader kallas reducerbart (i ett givet fält), annars - oreducerbart. Oreducerbara polynom spelar en roll som liknar primtal i talteori. De oreducerbara polynomen P (X) kan skrivas som decimaltal eller binära tal, eller som ett algebraiskt polynom.

Cyklisk kodningsprocess

Cyklisk kodning är baserad på användningen av ett irreducerbart polynom P (X), som i förhållande till cykliska koder kallas en generator, generator eller genererande polynom (polynom).

Som informationssymboler k för konstruktion av cykliska koder tas kombinationer av den binära koden för alla kombinationer. I det allmänna fallet, om den angivna kodkombinationen Q (x) multipliceras med det genererande polynomet P (x), får vi en cyklisk kod som har vissa korrigerande egenskaper beroende på valet av P (x). I den här koden kommer dock kontrolltecknen m att finnas på en mängd olika platser i kodkombinationen. Denna kod är inte systematisk, vilket gör det svårt att implementera schematiskt. Situationen kan förenklas kraftigt om kontrolltecken läggs till i slutet, det vill säga efter informationstecken. För detta ändamål är det lämpligt att använda följande metod:

Vi multiplicerar kodkombinationen G (x), som måste kodas, med det monomala X m, som har samma grad som det genererande polynomet P (x);

Vi delar produkten G (x) X m med generatorns polynom P (x m):

där Q (x) är delningskvoten; R (x) är resten.

Multiplicera uttryck (2.1) med P (x) och överföra R (x) till den andra delen av jämlikheten utan att ändra tecknet till motsatsen, får vi:

Enligt jämlikhet (2.2) kan den cykliska koden, det vill säga det kodade meddelandet F (x), bildas på två sätt:

Multiplikation av en kodkombination av en binär kod med alla kombinationer genom att generera polynom P (x);

Multiplicera ett givet kodord G (x) med ett enda polynom X m med samma grad som det genererande polynomet P (x), med tillägg av resten R (x) erhållet efter att ha dividerat produkten G (x) X m med genererar polynom P (NS).

Meddelandekodning

Det krävs för att koda kodordet 1100, vilket motsvarar G (x) = x 3 + x 2 med P (x) = x 3 + x + 1.

Vi multiplicerar G (x) med X m, som har den tredje graden, får vi:

Genom att dividera produkten G (x) X m med generatorpolynomet P (x m), enligt (2.1), får vi:

eller i binär ekvivalent:

Som ett resultat får vi kvoten Q (x) av samma grad som G (x):

Q (x) = x 3 + x 2 + x> 1110

och resten:

Som ett resultat kommer kombinationen av en binär kod kodad med en cyklisk kod enligt (2.2) att ha formen:

F (x) = 1110 1011 = 1100010

Eftersom varje tillåten kodkombination av den cykliska koden representerar alla möjliga summor av det genererande polynomet G (x) måste de vara delbara utan en rest med P (x). Därför reduceras kontrollen av att det antagna kodordet är korrekt för att identifiera resten när det divideras med det genererande polynomet.

Ta emot resten indikerar ett fel. Resten av uppdelningen i cykliska koder spelar rollen som ett syndrom.

Till exempel, det överförda kodordet F (x) = 1100010, byggt med det genererande polynomet P (x) = 1011. Under påverkan av störningar omvandlades kodkombinationen till kombinationen F "(x) = 1000010

Vi delar den accepterade kombinationen med det genererande polynomet

Närvaron av resten R (x) = 001 indikerar ett fel. Det indikerar dock inte direkt var felet ligger i kombinationen. Det finns flera metoder baserade på analysen av syndromet för att bestämma felet.

Bestäm platsen för felet, för detta delar vi enheten med ett godtyckligt antal nollor med P (x) = 1011.

Ett fel uppstod i elementet numrerat:

Antal rester -2> 4-2 = 2

Det vill säga att felet är i det andra elementet.

En cyklisk kod är en linjär kod som är en ändlig uppsättning som är stängd med avseende på funktionen av cyklisk förskjutning av kodvektorerna som bildar den. Låt det ges n-dimensionell vektor v = a 0 a 1 …ett-1 med koordinater från målfältet F... Dess cykliska skift är en vektor v "= a n-1 a 0 a 1 ... ett -2 .

Överväga n-dimensionellt aritmetiskt utrymme över Galois -fältet Gf(2). Varje vektor a 0 a 1 …ett-1 av Gf(2) man kan associera ett en-till-ett-polynom a 0 +a 1 x+…+ett -1 x n-1 med koefficienter från Gf(2). Summan av två vektorer a 0 a 1 …ett-1 och b 0 b 1 …b n-1 är associerad med summan av motsvarande polynom, produkten av fältelementen med vektorn - produkten av polynomet som motsvarar denna vektor av elementet.

Tänk på något polynom g(x) från det beskrivna linjära rummet. Uppsättningen för alla polynom från detta delrum, som är delbara utan resten med g(x), bildar ett linjärt delrum. Ett linjärt delrum definierar någon linjär kod.

Linjär kod som bildas av en klass av polynom C(g(x)), multiplar av något polynom g(x), kallas det genererande polynomet, kallas polynom.

Låt oss visa hur polynomkoder är relaterade C(g(x)) och cykliska koder. Låt vara a = a 0 … Ett-1 - något kodord och motsvarande kodpolynom a(x) = a 0 +...+ett -1 x n-1. Cyklisk skjuvning a"matchar koden polynom a"(x) = ett -1 +a 0 x+…+ett -2 x n -1, som kan uttryckas genom originalet:

Eftersom polynomkoden måste vara delbar med g(x), sedan för att det ska vara cykliskt, polynomet a"(x) måste delas med g(x). Från denna övervägande kan vi formulera följande sats. En polynomkod är cyklisk om och endast om polynomet g(x) är en delare av polynomet x n-1. I detta fall polynomet g(x) kallas för den cykliska kodens genererande polynom.

I kodningsteorin bevisas följande sats: om polynomet g(x) har examen n–k och är en delare x n–1, då C(g(x)) är en linjär cyklisk ( n, k) -kod.

Polynom x n Faktor –1 x n–1 = (x–1)(x n -1 +x n-1 + ... + 1). Därför finns cykliska koder för alla n... Cyklisk n-bitkoder är lika med antalet divisorer för polynomet x n-1. För att konstruera cykliska koder har polynomiska sönderdelningstabeller utvecklats x n–1 till oreducerbara polynom, det vill säga till dem som bara är delbara med en och av sig själv.

Tänk till exempel vilka koder som kan byggas baserat på polynomet x 7 -1 över fältet Gf(2). Faktoriseringen av ett polynom till oreducerbara faktorer har formen

Eftersom sex avdelare av polynomet kan bildas x 7 -1, genom att kombinera oreducerbara delare, finns det sex binära cykliska koder. ( n, k) -koden bestäms för det första av värdet n och för det andra värdet k = n – s, s- graden av divisorpolynomet x n-1 definierar koden. Nedan visas delarna av polynomet och deras motsvarande värden k:

x – 1, s=1, k=6;

x 3 + x 2 +1, s=3, k=4;

x 3 + x+1, s=3, k=4;

(x–1)(x 3 + x 2 +1)=x 4 + x 2 + x + 1, s=4, k=3;

(x–1)(x 3 + x+1)=x 4 + x 3 + x 2 +1, s=4, k=3;

(x 3 + x 2 +1)(x 3 + x+1)=x 6 +x 5 +x 4 +x 3 +x 2 +x, s=6, k=1.

(7, 6) -koden har bara en kontrollsymbol, och (7, 1) -koden har bara en informationskod. De är paritet respektive repetition.

Liksom en vanlig linjär kod kan en cyklisk kod definieras av en generatormatris. Därför är uppgiften att hitta en sådan matris, det vill säga hitta k linjärt oberoende kodkombinationer som bildar den. För detta kommer vi att använda egenskapen att den cykliska koden är stängd med avseende på den cykliska skiftoperationen. Observera att cyklisk förskjutning till höger med en bit motsvarar multiplicering av polynomet g(x) på x... Sedan kan genereringsmatrisen konstrueras genom att ta det genererande polynomet som rader och k dess cykliska skift:

Låt oss nu överväga hur man använder det genererande polynomet g(x) = 1+x+x 3 är kodad med en (7, 4) -kod. Ta till exempel 4-bitarsordet (0101), som motsvarar polynomet f(x) = x + x 3. Multiplicera dessa två polynom.

Matchar detta ord, från en formell variabel x... Det kan ses att denna korrespondens inte bara är en-till-en, utan också isomorf. Eftersom "ord" består av bokstäver från ett fält kan de läggas till och multipliceras (element för element), och resultatet kommer att finnas i samma fält. Polynomen som motsvarar en linjär kombination av ett par ord och är lika med en linjär kombination av polynomen i dessa ord

Detta gör att vi kan betrakta uppsättningen ord med längd n över ett ändligt fält som ett linjärt utrymme av polynom med högst n-1 över fältet

Algebraisk beskrivning

Om kodordet, erhållet genom cyklisk, flyttar en bit åt höger från ordet, då motsvarande polynom c 1 (x) erhålls från föregående genom att multiplicera med x:

Utnyttja att,

Skift åt höger respektive vänster med j siffror:

Om m(x) är ett godtyckligt polynom över fältet GF(q) och c(x) är kodordet för den cykliska ( n,k) sedan m(x)c(x)mod(x n − 1) är också kodordet för denna kod.

Genererar polynom

Definition Det genererande polynomet för det cykliska ( n,k) kod C kallas en sådan icke -noll -polynom från C vars grad är den minsta och koefficienten vid den högsta graden g r = 1 .

Sats 1

Om C- cyklisk ( n,k) kod och g(x) är dess genererande polynom, sedan graden g(x) är lika med r = n − k och varje kodord kan representeras unikt som

c(x) = m(x)g(x) ,

där graden m(x) är mindre än eller lika med k − 1 .

Sats 2

g(x) är det genererande polynomet för det cykliska ( n,k) i koden är en delare av binomen x n − 1

Konsekvenser: Således kan du som ett genererande polynom välja valfritt polynom, divisorn x n- 1. Graden av det valda polynomet bestämmer antalet kontrollsymboler r, antalet informationssymboler k = n − r .

Generativ matris

Polynomen är linjärt oberoende, annars m(x)g(x) = 0 med noll m(x), vilket är omöjligt.

Detta innebär att kodord kan skrivas, liksom för linjära koder, enligt följande:

, var Gär en alstrande matris, m(x) - information polynom.

Matrisen G kan skrivas i symbolisk form:

Kontrollera Matrix

För varje kodord i den cykliska koden är sant. Det är därför kolla matris kan skrivas som:

Kodning

Osystematiskt

Med icke-systematisk kodning erhålls kodordet i form av produkten av informationspolynomet genom att generera

c(x) = m(x)g(x) .

Det kan implementeras med hjälp av polynommultiplikatorer.

Systematisk

Med systematisk kodning bildas kodordet i form av ett informationsdelblock och en kontroll

Låt då informationsordet bilda kodordets högsta befogenheter

c(x) = x r m(x) + s(x),r = n − k

Sedan av villkoret följer det

Denna ekvation sätter regeln för systematisk kodning. Det kan implementeras med hjälp av multi-cycle linjära filter (MLF)

Exempel på

Binär (7,4,3) kod

Som delare x 7 - 1 väljer vi det genererande polynomet för den tredje graden g(x) = x 3 + x + 1 , då kommer den resulterande koden att ha längd n= 7, antalet kontrollsymboler (graden av genererande polynom) r= 3, antalet informationssymboler k= 4, minsta avstånd d = 3 .

Generativ matris koda:

där den första raden är polynomnotationen g(x) koefficienter i stigande grad. Resten av linjerna är cykliska skift på den första raden.

Kontrollera matris:

där i: e-kolumnen, från och med 0: e, är resten av divisionen x i av polynom g(x), skrivet i stigande grader, från början.

Så, till exempel, erhålls den tredje kolumnen, eller i vektornotation.

Det är lätt att se det GH T = 0 .

Binär (15.7.5) BCH -kod

Som ett genererande polynom g(x) kan du välja produkten från två delare x 15 − 1 ^

g(x) = g 1 (x)g 2 (x) = (x 4 + x + 1)(x 4 + x 3 + x 2 + x + 1) = x 8 + x 7 + x 6 + x 4 + 1 .

Sedan kan varje kodord erhållas med hjälp av produkten från informationspolynomet m(x) med examen k- 1 på detta sätt:

c(x) = m(x)g(x) .

Till exempel motsvarar informationsordet polynomet m(x) = x 6 + x 5 + x 4 + 1 , sedan kodordet c(x) = (x 6 + x 5 + x 4 + 1)(x 8 + x 7 + x 6 + x 4 + 1) = x 14 + x 12 + x 9 + x 7 + x 5 + 1 eller i vektorform

se även

Länkar

Wikimedia Foundation. 2010.

Cykliska former i musik
Cykliska gränsvillkor

Se vad "cykliska koder" finns i andra ordböcker:

förkortade cykliska koder- - [L.G. Sumenko. The English Russian Dictionary of Information Technology. M.: GP TsNIIS, 2003.] Ämnen informationsteknik i allmänhet EN förkortade cykliska koder ...

Reed-Solomon-koder- icke-binära cykliska koder som låter dig korrigera fel i datablock. Elementen i kodvektorn är inte bitar, utan grupper av bitar (block). Reed Solomon -koder som fungerar med byte (oktetter) är mycket vanliga. Reed Salomons kod är ... Wikipedia

Golay -koder- En familj av perfekta linjära blockkoder med felkorrigering. Den mest användbara är Golay binära kod. Den ternära Golay -koden är också känd. Golay -koder kan ses som cykliska koder. ... ... Teknisk översättarguide

Felkorrigeringskoder

Fel vid korrigering av koder- Upptäckt av fel i kommunikationsteknik, en åtgärd som syftar till att övervaka dataintegriteten under inspelning / uppspelning av information eller under överföring över kommunikationslinjer. Korrigering av fel (felkorrigering) för att återställa information efter ... ... Wikipedia

Felkorrigering av koder- Upptäckt av fel i kommunikationsteknik, en åtgärd som syftar till att övervaka dataintegriteten under inspelning / uppspelning av information eller under överföring över kommunikationslinjer. Korrigering av fel (felkorrigering) för att återställa information efter ... ... Wikipedia

VITRUSSKA STATENS UNIVERSITET FÖR INFORMATIK OCH RADIOELEKTRONIK

Institutionen för RES

abstrakt om ämnet:

”Cykliska koder. BChH -koder "

MINSK, 2009

Cykliska koder

En cyklisk kod är en linjär block (n, k) -kod, som kännetecknas av den cykliska egenskapen, d.v.s. ett vänster skift av tillåtet kodord med ett steg ger också ett tillåtet kodord som tillhör samma kod och där uppsättningen kodord representeras av en uppsättning polynom av grad (n-1) och mindre, delbart med något polynom g ( x) av grad r = nk som är en faktor för binomialet xn +1.

Polynomet g (x) kallas generera.

Som följer av definitionen, i en cyklisk kod, representeras kodord som polynom

där n är kodens längd; är koefficienterna från fältet GF (q).

Om koden är byggd över fältet GF (2), tar koefficienterna värdena 0 eller 1 och koden kallas binär.
Exempel. Om det cykliska kodordet

sedan motsvarande polynom

Till exempel, om koden är konstruerad över fältet GF (q) = GF (2 3), vilket är en förlängning av GF (2) modulo det irreducerbara polynomet f (z) = z 3 + z + 1, och elementen i detta fält har formen representerad i tabell 1,

sedan koefficienterna

ta värdena för elementen i detta fält och därför visas de själva som polynom i följande form
där m är graden av polynomet som används för att erhålla förlängning av fältet GF (2); a i - koefficienter som tar värdet av elementen i GF (2), dvs. 0 och 1. En sådan kod kallas qth.

Längden på en cyklisk kod kallas primitiv och själva koden kallas primitiv om dess längd är n = q m -1 på GF (q).

Om kodens längd är mindre än den primitiva kodens längd, kallas koden trunkerad eller icke-primitiv.

Såsom följer av definitionen är en gemensam egenskap hos cykliska kodord deras delbarhet utan återstod av något polynom g (x), kallat generering.

Resultatet av att dela binomialet x n +1 med polynomet g (x) är kontrollpolynomet h (x).

Vid avkodning av cykliska koder används felet polynom e (x) och syndrompolynomet S (x).

Högst felpolynomet (n-1) bestäms utifrån uttrycket

var finns polynomen som representerar mottagna (med ett fel) respektive överförda kodord.

Non -nollkoefficienter i e (x) intar positioner som motsvarar fel.

Exempel.

Det syndromiska polynom som används vid avkodning av den cykliska koden definieras som resten av att dela det mottagna kodordet med det genererande polynomet, d.v.s.

eller

Följaktligen beror det syndromiska polynomet direkt på felpolynomet e (x). Denna position används för att konstruera en tabell med syndrom som används i avkodningsprocessen. Denna tabell innehåller en lista över felpolynom och en lista över motsvarande syndrom bestämda utifrån uttrycket

(se tabell 2).

I processen för avkodning beräknas syndromet från det mottagna kodordet, sedan hittas motsvarande polynom e (x) i tabellen, vars summering med det mottagna kodordet ger det korrigerade kodordet, d.v.s.

De listade polynomen kan läggas till, multipliceras och delas med hjälp av de välkända reglerna för algebra, men med minskning av resultatet mod 2, och sedan mod xn +1, om resultatgraden överstiger graden (n-1) .

Antag att kodens längd är n = 7, då ges resultatet mod x 7 +1.

När man konstruerar och avkodar cykliska koder som ett resultat av uppdelningen av polynom, är det vanligtvis nödvändigt att inte ha kvoten utan resten av divisionen.
Därför rekommenderas en enklare uppdelningsmetod, inte med hjälp av polynom, utan endast dess koefficienter (alternativ 2 i exemplet).

Exempel.

Matris tilldelning av koder

Den cykliska koden kan specificeras av generator- och paritetsmatriserna. För att konstruera dem är det tillräckligt att känna till generatorn g (x) och kontrollpolynomet h (x). För en icke -systematisk cyklisk kod konstrueras matriser genom cykliskt skift av generator och kontrollpolynom, d.v.s. genom att multiplicera dem med x

och

När matrisen H (n, k) konstrueras, är den främsta koefficienten för polynomet h (x) placerad till höger.

Exempel. För en cyklisk (7,4) -kod med ett genererande polynom g (x) = x 3 + x + 1 har matriserna G (n, k) och H (n, k) formen:

var

För en systematisk cyklisk kod bestäms matrisen G (n, k) utifrån uttrycket

där I k är identitetsmatrisen; R k, r är en rektangulär matris. Raderna i matrisen R k, r bestäms utifrån uttrycken eller där a i (x) är värdet på i-raden i matrisen I k; i är radnumret för matrisen R k, r.

Exempel. Matrisen G (n, k) för (7,4) -koden baserad på det genererande polynomet g (x) = x 3 + x + 1 konstrueras i följande sekvens

eller

Bestäm R 4.3 med

eftersom

På ett liknande sätt bestäms det