Huruvida det cykliska prefixet innehåller användbar information. Cykliska koder

Cykliska koder benämns så att en del av kodkombinationerna eller alla kombinationer i dem kan erhållas genom cyklisk förskjutning av en eller flera kodkombinationer. Cyklisk förskjutning utförs från höger till vänster och karaktären längst till vänster överförs till slutet av kombinationen varje gång. Cykliska koder, praktiskt taget alla hänvisar till systematiska koder, i dem finns kontroll- och informationssiffror på strikt definierade platser. Dessutom klassificeras koder som blockkoder. Varje block (en bokstav är ett speciellt fall av ett block) kodas oberoende.

Idén att konstruera cykliska koder baseras på användningen av polynom som inte kan reduceras inom binära tal. Oreducerbarpolynom kallas som inte kan representeras som en produkt av polynom med lägre grader med koefficienter från samma fält, precis som primtal inte kan representeras som en produkt av andra tal. Med andra ord är oreducerbara polynom delbara utan återstod endast av sig själva eller av enhet.

Oreducerbara polynomer i teorin om cykliska koder spelar rollen som generatorer av polynomer. Om den givna kodkombinationen multipliceras med det valda irreducerbara polynomet får vi en cyklisk kod vars korrigeringsfunktioner bestäms av den irreducible polynom.

Antag att du vill koda en av kombinationerna av fyrsiffriga binär kod... Antag också att denna kombination G (x) \u003d x 3 + x 2 + 1 ®1011. Även om vi inte styrker vårt val tar vi från tabellen över oreducerbara polynomer som ett genererande polynom. P (x) \u003d x 3 + x + 1 ®1011. Sedan multiplicerar vi G (x) av ett monom av samma grad som det genererande polynom. Från att multiplicera ett polynom med ett monomium n graden av varje term i polynom kommer att öka med n, vilket motsvarar tilldelning n nollor på sidan av polynomets minst signifikanta bitar. Eftersom graden för det valda irreducerbara polynomet är lika med tre multipliceras den ursprungliga informationskombinationen med ett monomium på tre grader

G (x) x n \u003d(x 3 + x 2 + 1) x 3 \u003d x 6 + x 5 + x 3 \u003d1101000.

Detta görs så att det senare i stället för dessa nollor skulle vara möjligt att skriva korrigeringssiffror.

Värdet på de korrigerande siffrorna hittas från resultaten från division G (x) x n på P (x):

x 6 + x 5 + 0 + x 3 + 0 + 0 + 0 ½x 3 + x + 1

x 6 + 0 + x 4 + x 3

x 5 + x 4 + 0 + 0 x 3 + x 2 + x + 1 + x 5 + 0 + x 3 + x 2

x 4 + x 3 + x 2 +0

x 4 + 0 + x 2 + x

x 3 + 0 + x + 0

x 3 + 0 + x + 1

Således,

eller i allmänhet

var Q (x) ¾ privat, och R (x) ¾ resten av uppdelningen G (x) × x n på P (x).

Eftersom i binär aritmetik 1 Å 1 \u003d 0, och därför -1 \u003d 1, när man lägger till binära tal är det möjligt att överföra termer från en del till en annan utan att ändra tecknet (om det är lämpligt), därför är formens lika a Å b \u003d0 kan skrivas som a \u003d b, Och hur a - b \u003d 0. Alla tre likheter i detta fall betyder att antingen a och b är lika med 0, eller a och bär lika med 1, dvs. har samma paritet.

Således kan uttryck (5.1) skrivas som

F (x) \u003d Q (x) P (x) \u003d G (x) x n + R (x),

vilket i fallet med vårt exempel kommer att ge

F (x) \u003d(x 3 + x 2 + x +1) (x 3 + x +1)= (x 3 + x 2 +1) x 3 +1,

F (x) \u003d1111 1011 = 1101000 + 001 = 1101001.

Polynom 1101001 är önskad kombination, där 1101 är en informationsdel och 001 är kontrolltecken. Observera att vi skulle få önskad kombination både som ett resultat av att multiplicera en av kombinationerna av den fullständiga fyrsiffriga binära koden (i detta fall 1111) med en generatorpolynom och genom att multiplicera den givna kombinationen med en monom med samma grad som det valda generatorpolynomet (i vårt fall erhölls sålunda kombinationen 1101000) med efterföljande tillsats till den resulterande produkten av återstoden av uppdelningen av denna produkt med det genererande polynomet (i vårt exempel har resten formen 001 ).

Och här spelar den avgörande rollen egenskaperna hos det genererande polynomet P (x)... Metoden för att konstruera en cyklisk kod är sådan att generatorpolynomet deltar i bildandet av varje kodkombination, varför varje polynom av den cykliska koden delas av generatorn utan en återstod. Men bara de polynomer som tillhör den här koden, det vill säga, det genererande polynomet låter dig välja de tillåtna kombinationerna från alla möjliga. Om en återstående del erhålls när den cykliska koden delas med det genererande polynomet, har antingen ett fel inträffat i koden eller så är det en kombination av någon annan kod (förbjuden kombination). I resten detekteras närvaron av en förbjuden kombination, det vill säga ett fel detekteras. Rester från uppdelning av polynom är feligenkänning av cykliska koder.

Å andra sidan används resterna av att dela en med nollor av det genererande polynomet för att konstruera cykliska koder.

När man delar en med nollor med ett genererande polynom bör man komma ihåg att längden på återstoden inte får vara mindre än antalet kontrollsiffror, därför, i händelse av brist på siffror i resten, det nödvändiga antalet nollor tilldelas till höger om resten.

01100 11111+

från och med den åttonde kommer resten att upprepas.

Resterna från division används för att konstruera genererande matriser, som på grund av deras tydlighet och bekvämlighet vid erhållande av derivatkombinationer används allmänt för att konstruera cykliska koder. Konstruktionen av en genererande matris reduceras till sammanställningen av en enhets transponerad och ytterligare matris, vars element är återstoden av att dela en med nollor av det genererande polynomet P (x)... Kom ihåg att den transponerade identitetsmatrisen är en fyrkantig matris, varav alla element är nollor, förutom de element som ligger diagonalt från höger till vänster från topp till botten (i en otransporterad matris är diagonalen med identitetselement från vänster till höger från topp till tå). Elementen i den extra matrisen tilldelas till höger om den identitetstransponerade matrisen. Endast de resterna vars vikt är W ³ d 0 - 1, där d 0 Är det minsta kodavståndet. Längden på resterna måste vara minst antalet kontrollbitar och antalet rester måste vara lika med antalet informationsbitar.

Raderna i den genererande matrisen är de första kombinationerna källkod... Resten av kodkombinationerna erhålls genom att summera modulo 2 alla möjliga kombinationer av rader i den genererande matrisen.

Exempel.

Konstruera en komplett genereringsmatris av en cyklisk kod som upptäcker alla enkla och dubbla fel vid överföring av 10-bitars binära kombinationer.

Beslut.

Välj det närmaste värdet enligt tabell 5.12 k ³ 10.

Tabell 5.12 - Förhållandet mellan information och kontrolltecken för en kod på upp till 16 bitar

n	k	ρ	n	k	ρ

Enligt tabellen kommer detta värde att vara k \u003d11, medan r \u003d4, och

n \u003d15. Vi väljer också generatorpolynom x 4 + x 3 +1.

Den kompletta genereringsmatrisen är konstruerad från enhetstransponeringsmatrisen i kanonisk form och en ytterligare matris motsvarande kontrollsiffrorna.

Transponera matris för k \u003d11 ser ut som:

En ytterligare matris kan konstrueras från resterande delning av en kombination i form av en med nollor (den sista raden i den identitetstransponerade matrisen) av det valda genereringspolynomet.

Hela generatormatrisen kommer att vara:

Metoden som beskrivs ovan för att konstruera genererande matriser är inte den enda. Generatormatrisen kan konstrueras genom att multiplicera elementen i identitetsmatrisen direkt med generatorpolynomet. Detta är ofta bekvämare än att hitta resten av en uppdelning. De erhållna koder skiljer sig inte på något sätt från koder konstruerade från genererande matriser, i vilka den ytterligare matrisen består av återstoden av att dela en med nollor av det genererande polynomet.

Den genererande matrisen kan konstrueras på samma sätt genom cyklisk förskjutning av kombinationen erhållen som ett resultat av att multiplicera raden i identitetsmatrisen av rang k på generatorns polynom.

Fel i cykliska koder detekteras med resten av att dela den resulterande kombinationen med det genererande polynomet. Resten av uppdelningen är felidentifierare, men anger inte felets placering i den cykliska koden.

Idén med felkorrigering baseras på det faktum att den felaktiga kombinationen efter ett visst antal cykliska förskjutningar "monteras" på resten på ett sådant sätt att det tillsammans med resten ger det korrigerade kodordet. I detta fall är resten inte mer än skillnaden mellan de förvrängda och korrekta symbolerna, enheterna i resten står exakt på platserna för de förvrängda bitarna i kombinationen justerade genom cykliska skift. Den förvrängda kombinationen justeras tills antalet i resten är lika med antalet fel i koden. I det här fallet kan antalet naturligtvis antingen vara lika med antalet fel s, korrigeras av den här koden (koden korrigerar 3 fel och 3 fel i en förvrängd kombination) eller mindre s (koden korrigerar 3 fel och i den accepterade kombinationen 1 fel).

Platsen för felet i kodkombinationen spelar ingen roll. Om en k ³ (n / 2), sedan efter ett visst antal skift kommer alla fel att vara i zonen för "engångs" -åtgärden hos det genererande polynomet, det vill säga det räcker att erhålla en återstod vars vikt är W £ s, och detta räcker redan för att korrigera den förvrängda kombinationen.

Felkorrigeringsprocessen diskuteras i detalj nedan med hjälp av exempel på byggnadsspecifika koder.

Det är en underklass av linjära koder som har den egenskapen att cyklisk permutation av symboler i ett kodat block ger ett annat möjligt kodat block av samma kod. Cykliska koder baseras på tillämpningen av idéer från den algebraiska teorin för Galois-fält1.

Många av de viktigaste anti-jamming-koderna för kommunikationssystem, -

särskilt cykliskt, baserat på strukturerna för ändlig aritmetik

galois fält. Vid fältet kallas den uppsättning element som det ändliga fältet

operationernas namn är bifogade i citattecken, eftersom de inte alltid är allmänt accepterade aritmetiska operationer. Fältet innehåller alltid ett nollelement (0) eller noll och ett element (1) eller ett. Om numret q fältelement är begränsade, då kallas fältet ändligt fält, eller ändligt Galois-fältoch betecknas GF (q) y Var q - fältorder. Det minsta Galois-fältet är tvåelementets iole GF (2), som endast består av två element 1 och 0. För att

1 Evariste Galois (1811 - 1832) - fransk matematiker, lade grunden till modern algebra.

utför operationer på element GF (2) ledde inte till att gå längre än detta fält, de utförs modulo 2 (i allmänhet bestäms detta av ordningen på fältet för enkla Galois-fält).

Fältet har ett antal specifika matematiska egenskaper. För fältelement definieras tilläggs- och multiplikationsåtgärder, och resultaten av dessa operationer måste tillhöra samma uppsättning.

För additions- och multiplikationsoperationer följs de vanliga matematiska associativitetsreglerna - och + (B + c) \u003d (a + B) + c, kommutativitet - a + b \u003d b + aoch och b \u003d b och och distribution - och (B + s) \u003d och b + och från.

För varje fältelement och invers tillägg måste finnas (-och) och om och icke-noll, det omvända av multiplikationen (th ').

Fältet måste innehålla tillsatsenhet - element 0 så att och + 0 = ochför alla fältelement och.

Fältet måste innehålla multiplikativ enhet - element 1 så att aL \u003d a för alla fältelement och.

Det finns till exempel fält riktiga nummer, rationella tal, komplexa nummer. Dessa fält innehåller ett oändligt antal objekt.

I själva verket är alla uppsättningar som bildas genom cyklisk permutation av ett kodord också kodord. Så till exempel kommer cykliska permutationer av kombination 1000101 också att vara kodkombinationer 0001011, 0010110, 0101100, etc. Den här egenskapen gör det möjligt att kraftigt förenkla kodaren och avkodaren, särskilt när man upptäcker fel och korrigerar ett enda fel. Uppmärksamhet på cykliska koder beror på det faktum att deras inneboende högkorrigerande egenskaper realiseras på grundval av relativt enkla algebraiska metoder. Samtidigt, för avkodning av en godtycklig linjär blockkod, används ofta tabellmetoder som kräver en stor mängd avkodarminne.

En cyklisk kod kallas ett linjärt block (n, k) -kod som är cyklisk, dvs. en stegvis vänsterförskjutning av ett tillåtet kodord ger det tillåtna ett kodordtillhör samma kod och vars uppsättning kodord representeras av en uppsättning polynomer av grad (S - 1) eller mindre delbart med det genererande polynomet g (x) grad r \u003d n-k y binom x n +

I en cyklisk kod representeras kodord av polynom (polynom)

var p - kodlängd; A i - Galois-fältkoefficienter (kodkombinationsvärden).

Till exempel, för kodkombination 101101 har polynomnotationen formen

Exempel på cykliska koder är jämna kontrollkoder, repetitionskoder, Hamming-koder, PC-koder och turbokoder.

Hamming-kod... Felkorrigeringsfunktionerna för Hamming-koden är relaterade till minimikodavståndet d 0. Alla multipelfel är fixade q \u003d cnt (d 0 - l) / 2 (här betyder cnt "heltal") och flerfel upptäcks d 0 - 1. Så när du letar efter udda d Q \u003d 2 och enstaka fel detekteras. I Hammings kod d 0 \u003d 3. Förutom informationsbitarna, L \u003d log 2 Q av redundanta kontrollbitar, var Q - antalet informationsbitar. Parameter Lavrundas till närmaste högre heltal. L-bitkontrollkoden är det inverterade resultatet av bitvis tillsats (additionsmodul 2) av numren på de informationsbitar vars värden är lika med en.

Exempel 7.7

Låt oss ha huvudkoden 100110, dvs. Q \u003d 6. Låt oss definiera en extra kod.

Beslut

Vi finner det L \u003d 3 och kompletterande kod är

där P är symbolen för den bitvisa tilläggsoperationen, och efter inverteringen har vi 000. Nu kommer tilläggskoden att sändas med huvudkoden. Vid mottagaren beräknas tilläggskoden igen och jämförs med den sända. Jämförelsekoden är fixerad, och om den skiljer sig från noll, är dess värde numret på den felaktigt mottagna biten i huvudkoden. Så om koden 100010 tas emot är den beräknade tilläggskoden lika med inversionen från 010SH10 \u003d 100, d.v.s. 011, vilket betyder ett fel i den tredje siffran.

Generaliseringen av Hamming-koder är cykliska BCH-koder, som tillåter korrigering av flera fel i det mottagna kodordet.

Reed - Salomonkoder är baserade på Galois-fält eller efterföljande nollor. Aritmetiska operationer är addition, subtraktion, multiplikation, division etc. över element av en efterföljande noll ger ett resultat som också är ett element av den nollan. En Reed-Solomon-kodare eller avkodare måste utföra dessa åtgärder. Alla åtgärder för att implementera koden kräver specialutrustning eller specialiserad programvara.

Turbokoder. Redundanta koder kan användas både oberoende och i form av någon kombination av flera koder, när uppsättningarna av symboler för en redundant kod betraktas som elementära informationssymboler för en annan redundant kod. En sådan union började kallas kaskad koda. En stor fördel med sammanfogade koder är att deras användning gör det möjligt att förenkla kodaren och speciellt avkodaren jämfört med liknande anordningar för icke-sammanfogade koder med samma längd och redundans. Sammankopplad kodning ledde till skapandet av turbokoder. Turbocode kallas en parallell signalstruktur bestående av två eller mer systematiska koder. Grundprincipen för deras konstruktion är användningen av flera parallella komponentkodare. Som komponentkoder kan du använda både block- och faltningskoder, Hamming-koder, PC-kod, BCH, etc. Användning av perforering (punktering) gör att du kan öka den relativa hastigheten för turbokoden och anpassa dess korrigeringsförmåga till den statistiska kommunikationskanalens egenskaper. Principen för turbokodsbildning är följande: insignal x, bestående av TILL bit, matas parallellt med N interleavers. Var och en av de senare är en anordning som tillåter element i ett block av TILL bitar i pseudoslumpmässig ordning. Utgångssignalen från interfolierna - de ordnade symbolerna - matas till motsvarande elementära kodare. Binära sekvenser x p i \u003d 1,2, ..., JV, vid kodarens utgång finns kontrollsymboler, som tillsammans med informationsbitarna utgör ett enda kodord. Användningen av interleaver gör det möjligt att förhindra uppkomsten av sekvenser av korrelerade fel vid avkodning av turbokoder, vilket är viktigt när man använder den återkommande avkodningsmetoden, som är traditionell vid bearbetning. Beroende på valet av komponentkoden är turbokoderna uppdelade i fällbara turbokoder och blockerar produktkoder.

Cykliska koder är ett slags linjära gruppkoder och klassificeras som systematiska koder. De skapades ursprungligen för att förenkla avkodningsprocedurer. Den höga effektiviteten vid upptäckt av fel i sådana koder säkerställde emellertid deras breda tillämpning i praktiken. Det är bekvämt att betrakta en binär vektor av en cyklisk kod inte som en kombination av nollor och enor, utan som en polynom i viss grad

där x är basen för nummersystemet, koefficienterna som hör till uppsättningen i fallet binärt system beräkning.

Exempel. En binär vektor kan representeras som ett polynom enligt följande:

Genom att representera binära vektorer i form av polynomier kan du minska verkan på vektorer till åtgärder på polynom. Vart i:

tillsättningen av polynom reduceras till summan modulo 2 av koefficienterna för variabelns lika kraft

multiplikation utförs enligt den vanliga regeln för multiplicering av effektfunktioner, men de erhållna koefficienterna för en given grad adderas modulo 2;

delning utförs enligt reglerna för att dela effektfunktioner, medan subtraktionsoperationen ersätts av summeringsmodul 2.

Exempel. Hitta summan av polynom

Hitta produkten av polynom

Dela upp polynom

Huvudegenskapen för cykliska koder är följande: om en vektor tillhör en cyklisk kod, tillhör också vilken vektor som helst som erhålls från den som övervägs med hjälp av cykliska förskjutningar också den cykliska koden.

Idén att konstruera cykliska koder bygger på konceptet med ett irreducerbart polynom. Ett polynom sägs vara oreducerbart om det endast är delbart av sig själv och av ett och inte kan delas av något annat polynom. Med andra ord kan ett irreducerbart polynom inte representeras som en produkt av polynom med lägre grader. Ett polynom är delbart med ett oreducerbart polynom utan en återstod. I teorin om cykliska koder spelar oreducerbara polynomer rollen som generatorer av polynomer. Typerna av irreducerbara polynomer i olika grader anges i

Exempel på irreducerbara polynomer:

Cykliska kodvektorer är konstruerade enligt följande regler. Låt vara vilken binär vektor som helst av någon naturlig kod; är en monomial av grad, en irreducibel gradpolynom. Därefter bildas vilken vektor av en cyklisk kod som helst med hjälp av relationen

var är resten av uppdelningen

Således kan vilken vektor som helst av en cyklisk kod bildas genom att multiplicera någon vektor av en naturlig binär kod med en monom av en grad med tillsats av resten av uppdelningen till den resulterande produkten. När man konstruerar cykliska koder på detta sätt, placeras informationsbitar i varje kodvektor är strikt ordnade - de upptar de viktigaste bitarna i kodvektorn, och resten av siffrorna kontrollerar.

Exempel. Vektorn för en naturlig binär kod har formen Generera en cyklisk kodvektor från neger, förutsatt att det genererande polynomet har formen

Vi representerar vektorn som ett polynom

Som ett resultat av att polynomet delas med polynomet får vi resten. därför

En cyklisk kod, som vilken systematisk kod som helst, kan lämpligen ges i matrisform med användning av en genererande matris av formen

var är den transponerade identitetsmatrisen för formatet - matrisen för kontrollbitar bildas av resten av divisionen

Låt oss ställa in den genererande matrisen för den cykliska koden med längden på informationsbitar och det genererande polynomet.

Uppenbarligen har blanketten för den genererande matrisen formen

För att hitta raderna i matrisens kontrollbitar beräknar vi och skriver i form av ett polynom varje vektor i identitetsmatrisen

Längden på den cykliska kodvektorn är därför

(se skanning)

Som ett resultat får vi genereringsmatrisen C:

Vilken vektor som helst av en cyklisk kod erhålls som modsumman för vektorerna i dess genererande matris. Eftersom den cykliska koden är en gruppkod, tilldelas nollvektorn alltid den cykliska koden som enhetselementet i gruppen "

Tabell 13.5

Exempel. Konstruera alla vektorer av den cykliska koden som ges av den genererande matrisen

Koden presenteras i tabellen. 13.5.

Det bör noteras att varje cyklisk kod som specificeras av en viss genereringsmatris kan representeras i flera versioner, som skiljer sig från varandra i längden och antalet informationsbitar (med samma detekteringsförmåga). Dessa varianter av så kallade förkortade cykliska koder erhålls genom att radera de sista raderna och samma antal kolumner till vänster i den genererande matrisen för den cykliska koden. I detta fall förblir antalet kontrollbitar oförändrat och längden på koden respektive antalet informationsbitar minskar med en mängd som är lika med antalet överkorsade rader och kolumner i den genererande matrisen.

Exempel: Cyklisk kod ges av dess generatormatris

Korsa de sista sex raderna och de första sex kolumnerna från vänster. Vi får den genererande matrisen

Egenskaperna (i termer av feldetektering) för den mottagna koden är desamma som för den cykliska koden som representeras av den genererande matrisen

Konstruktionen av cykliska koder med givna parametrar är associerad med valet av ett genererande irreducerbart polynom. Det genererande polynomet väljs utifrån följande villkor: graden av polynom måste vara lika med antalet kontrollbitar i den cykliska koden.

I praktiken uppstår ofta problemet med att konstruera en cyklisk kod för en given effekt och en viss detekterings- och korrigeringsfunktion.

1. Eftersom kraften i den cykliska koden ges bestäms antalet informationsbitar i enlighet med formeln

2. Det optimala antalet kontrollbitar för den cykliska koden bestäms enligt specialtabeller.

3. Referensböcker hittar alla irreducerbara polynomer av grad

4. För en av de icke-ledande polynomema (man bör välja ett polynom med maximalt antal termer) av graden konstrueras en genererande matris för den cykliska koden. Varje kodvektor beräknas med formeln

var är polynomet för informationsvektorn för den genererande matrisen; - monomial grad - resten av uppdelningen

5. Den konstruerade genereringsmatrisen kontrolleras för följande förhållanden:

a) vikten i Hamming-betydelsen av vilken vektor som helst i den genererande matrisen måste tillfredsställa förhållandet var är det minsta avståndet i Hamming-betydelsen för den cykliska kod som övervägs;

b) vikten i betydelsen Hamming av kontrollvektorn, som är summan modulo 2 för två kontrollvektorer i den genererande matrisen, måste uppfylla förhållandet

6. Om den genererande matrisen för den cykliska koden uppfyller alla ovanstående villkor, skrivs alla vektorerna i den cykliska koden ut och bestäms i enlighet med de välkända reglerna för linjära gruppkoder. Om koden inte uppfyller kraven väljs en annan generatorpolynom av samma grad och proceduren för att generera en cyklisk kod upprepas för en ny polynom.

Låt oss konstruera en cyklisk kod med kraften 16 och en korrigeringskod

För bestämmer vi värdet med

3 »Från referensböckerna finner vi alla irreducerbara polynomer av grad Det finns två sådana polynomer:

4. Vi väljer polynom som generator. Blankan i den genererande matrisen för den cykliska koden har formen

Varje informationsvektor från matrisen representeras av ett polynom

Bestäm alla vektorer i den genererande matrisen helt med hjälp av formeln

Sedan längden på den cykliska kodvektorn (se formatet för den genererande matrisen då

På samma sätt hittar vi alla andra vektorer i den genererande matrisen

Tabell 13.6

Resultatet är en genererande matris C? cyklisk kod

5. Den resulterande genereringsmatrisen uppfyller alla nödvändiga villkor. Därför konstruerar vi den cykliska koden helt (tabell 13.6). Som följer av tabellen har koden, dvs. den uppfyller kraven i problemet.

Anmärkningar. När vi använder ett irreducerbart polynom som en generator får vi en kod som också uppfyller kraven för problemet. Dess genererande matris har formen

Feldetektering med cykliska koder utförs enligt följande. Varje vektor av den cykliska koden är delbar med det genererande polynomet utan en återstod. Därför är kriteriet för närvaron av ett fel i den cykliska kodvektorn framträdandet av en icke-noll återstod efter att ha delat den cykliska kodvektorn med det genererande polynomet. Icke-nollresten identifierar ett fel i den cykliska kodvektorn, men dess utseende indikerar inte placeringen av felet i kodvektorn. Felkorrigering baseras på följande algoritm:

1. Dela den mottagna kodvektorn med det genererande polynomet.

Om antalet inte överstiger kodens korrigeringsförmåga, lägg sedan till den mottagna vektorn modulo 2 med den resulterande återstoden. Summationen ger den korrigerade kodvektorn. Om antalet enheter i resten är större än kodens korrigeringsförmåga, utför sedan en cyklisk förskjutning av den förvrängda vektorn till vänster med en bit och del sedan med det genererande polynomet. Om den resulterande återstoden innehåller enheter som inte är mer än den cykliska kodens korrigeringsförmåga, lägg till den cykliskt förskjutna vektorn med resten. Flytta summeringsresultatet cykliskt en bit åt höger. Den resulterande vektorn innehåller inte redan fel och är en cyklisk kodvektor.

3. Om återstoden efter det första cykliska skiftet och efterföljande delning innehåller fler än kodens korrigeringsförmåga, upprepa sedan algoritmproceduren tills en återstående erhålls med antalet som inte överstiger kodens korrigeringsförmåga. I detta fall läggs resultatet av den sista cykliska förskjutningen till återstoden, och den resulterande vektorn förskjuts cykliskt med lika många bitar åt höger som den ursprungliga mottagna vektorn med ett fel skiftades åt vänster. Resultatet är en korrigerad kodvektor.

Låt den cykliska koden ges av dess genereringsmatris C och genererande polynom där

Koden har ett värde på 3, det vill säga den korrigerar multipelfel. Låt vektorn 0011101 tas istället för vektorn 0001101. Utför följande åtgärder för att korrigera felet. Den mottagna vektorn skrivs som ett polynom: sedan delar vi med

Resten som erhålls som ett resultat av delning innehåller tre, vilket är mer än kodens korrigeringsförmåga. Därför gör vi en cyklisk vänsterförskjutning med en bit av den mottagna kodvektorn. Som ett resultat har vi

Vi genomför uppdelning i

Den resulterande återstoden innehåller två enheter, vilket är mer än kodens korrigeringsförmåga. Därför gör vi ytterligare en cyklisk vänsterförskjutning med en bit av den mottagna kodvektorn. Som ett resultat har vi

Vi genomför uppdelning i

Den resulterande återstoden innehåller igen två, så vi gör en annan cyklisk vänsterförskjutning med en siffra och får Divider by

VITRYSSKLANDS UNIVERSITET MED INFORMATIK OCH RADIOELEKTON

institutionen för RES

abstrakt om ämnet:

”Cykliska koder. BChH-koder "

MINSK, 2009

Cykliska koder

En cyklisk kod är ett linjärt block (n, k) -kod, som kännetecknas av den cykliska egenskapen, dvs. en vänsterförskjutning av vilket tillåtet kodord som helst i ett steg ger också ett tillåtet kodord som tillhör samma kod och där uppsättningen kodord representeras av en uppsättning polynomier av grad (n-1) och mindre, delbara med något polynom g ( x) av grad r \u003d 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 längden på koden; är koefficienterna från fältet GF (q).

Om koden byggs ö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) \u003d GF (2 3), vilket är en förlängning av GF (2) modulo, det irreducerbara polynomet f (z) \u003d z 3 + z + 1, och elementen i detta fält har den form som representeras 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 av följande form
där m är graden av polynom som används för att erhålla förlängningen 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 \u003d q m -1 på GF (q).

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

Som följer av definitionen gemensam egendom av kodord för en cyklisk kod är deras delbarhet utan en återstod av något polynom g (x), kallat generatorn.

Genom att dela binomialet x n +1 med polynomet g (x) blir kontrollpolynomet h (x).

Vid avkodning av cykliska koder används felpolynomet e (x) och det syndromiska polynomet S (x).

Felpolynomets högsta grad (n-1) bestäms utifrån uttrycket

var är polynomerna som representerar de mottagna (med ett fel) respektive sända kodord.

Icke-nollkoefficienter i e (x) upptar positioner som motsvarar fel.

Exempel.

Det syndromiska polynom som används vid avkodning av den cykliska koden definieras som återstoden av att dela det mottagna kodordet med det genererande polynomet, dvs.

eller

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

(se tabell 2).

I avkodningsprocessen beräknas syndromet från det mottagna kodordet, sedan återfinns motsvarande polynom e (x) i tabellen, vars summa med det mottagna kodordet ger det korrigerade kodordet, dvs.

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

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

När man konstruerar och avkodar cykliska koder som ett resultat av uppdelningen av polynomer är det vanligtvis nödvändigt att inte ha kvoten utan resten av uppdelningen.
Därför rekommenderas ett enklare sätt att dela, utan att använda polynom, utan bara dess koefficienter (alternativ 2 i exemplet).

Exempel.

Matris tilldelning av koder

Den cykliska koden kan ges av generator- och paritetsmatriser. För att konstruera dem räcker det att känna till generatorn g (x) och kontrollpolynomet h (x). För en icke-systematisk cyklisk kod konstrueras matriser genom cyklisk förskjutning av generatorn och kontrollpolynomer, d.v.s. genom att multiplicera dem med x

och

Vid konstruktion av matrisen H (n, k) ligger den främsta koefficienten för polynomet h (x) till höger.

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

Var

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

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

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

eller

Bestäm R 4,3 med

eftersom

På ett liknande sätt,

Den enklaste cykliska koden med gör det möjligt att upptäcka enstaka fel och fel med udda mångfald. Den genererande polynom för denna kod har formen Bland de irreducerbara polynom som ingår i expansionen är detta polynom polynom av minst grad, så för ett antal informationsbitar behövs bara en kontrollbit. Teckenvärdet för denna bit säkerställer pariteten för antalet sådana i vilken tillåten kodkombination som helst. Den resulterande cykliska paritetskontrollskoden kan detektera inte bara enstaka fel i enskilda bitar, utan också fel i alla udda antal bitar.

Exempel. Konstruera en cyklisk kod för Eftersom det genererande polynomet är ett polynom av 1: a graden, antalet kontrollbitar Därför konstruerar vi en genereringsmatris för att konstruera en cyklisk kod

För att konstruera en ytterligare matris hittar vi resterna av att dela den sista raden i den enhetstransponerade matrisen, vadderad med nollor, med det valda polynomet:

Således har den ytterligare matrisen C, k formen

Nu bygger vi den genererande matrisen

Linjerna i denna matris är de tre första kodkombinationerna. Resten av de tillåtna kombinationerna kan erhållas genom att summera modulo två av alla möjliga kombinationer av matrisrader. De resulterande förstörda kodkombinationerna ges i tabell. 39.

Tabell 39 (se skanning)

Det är av känt intresse att överväga följande enklaste kod från andra gradens irreducibla polynom

Allmän form Den genererande matrisen för den cykliska koden som bildas av polynomet skiljer sig åt i strukturen för den ytterligare matrisen som har två kolumner.

Det är lätt att verifiera att när det delas av en given generatorpolynom av monomier som uttrycker raderna

identitetsmatrisen (för att hitta en ytterligare matris bildas tre typer av rester: 11, 01 och 10. Därför kommer vikten av varje kombination av den erhållna koden att vara minst två. Minsta kodavståndet mellan två kombinationer är också två. Men den enklaste koden med en paritetskontroll, bildad av en binomial av första graden. Korrigeringsförmågan för båda koder är dock inte densamma. Den betraktade koden har en stor redundans och gör det möjligt att upptäcka inte bara några fel med udda mångfald , men också alla ihopkopplade intilliggande fel, liksom alla fel åtskilda av ett icke-snedvridet element.