Hem / Problem/ Slingkodning. Utbildningsmetodiskt centrum för språkträning avtf kc

Loopkodning. Utbildningsmetodiskt centrum för språkträning avtf kc

Den enklaste cykliska koden med tillåter detektering av enstaka fel och fel med udda multiplicitet. Det genererande polynomet av denna kod har formen Bland de irreducerbara polynomen som ingår i expansionen är detta polynom det polynom av minsta graden.För valfritt antal informationsbitar behövs alltså endast en kontrollbit. Teckenvärdet för denna bit säkerställer pariteten för antalet ettor i varje tillåten kodkombination. Den resulterande cykliska paritetskontrollkoden är kapabel att detektera inte bara enstaka fel i individuella bitar, utan även fel i vilket udda antal bitar som helst.

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

För att konstruera en extra matris hittar vi resten av att dividera den sista raden av den enhetstransponerade matrisen, utfylld med nollor, med det valda polynomet:

Den ytterligare matrisen C, k har således formen

Nu bygger vi genereringsmatrisen

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

Tabell 39 (se skanning)

Det är av känt intresse att betrakta följande enklaste kod från det andra gradens irreducerbara polynomet

Den allmänna vyn av genereringsmatrisen för den cykliska koden som bildas av polynomet skiljer sig i strukturen av den ytterligare matrisen med två kolumner.

Det är lätt att verifiera att, när de divideras med en given generator, polynomen som uttrycker raderna

identitetsmatrisen (för att hitta en ytterligare matris bildas tre typer av residualer: 11, 01 och 10. Följaktligen kommer vikten av varje kombination av den erhållna -koden att vara minst två. Det minsta kodavståndet mellan två kombinationer är också två. Men den enklaste. Korrigeringsförmågan hos båda koderna är dock inte densamma. Den aktuella koden har stor redundans och gör det möjligt att upptäcka inte bara eventuella fel med udda mångfald, utan också alla parade intilliggande fel, såväl som alla fel separerade av ett oförvrängt element.

Klassen av linjära koder, som kallas cshaiska koder... Namnet kommer från huvudegenskapen för dessa koder: om någon kodkombination tillhör en cyklisk kod, så tillhör den kombination som erhålls genom cyklisk permutation av den ursprungliga kombinationen (cykliskt skift) också till denna kod:

Den andra egenskapen för alla tillåtna kombinationer av cykliska koder är deras delbarhet utan rest med något valt polynom, kallat det genererande.

Dessa egenskaper används vid konstruktionen av koder för kodnings- och avkodningsanordningar, såväl som vid upptäckt och korrigering av fel.

Cykliska koderär en hel familj av felkorrigerande koder (varav en av varianterna är Hamming-koder), vilket ger stor flexibilitet vad gäller möjligheten att implementera koder med nödvändig förmåga att upptäcka och korrigera fel som uppstår vid sändning av kodkombinationer över en kommunikationskanal. Cyklisk kod hänvisar till systematiskt block (l, &) - koder där Till de första siffrorna är en kombination av den primära koden och den efterföljande (l - Till) siffrorna kontrolleras.

Konstruktionen av cykliska koder är baserad på operationen att dividera det överförda kodordet med det genererande irreducerbara gradpolynomet G. Resten av divisionen används för att bilda kontrollsiffror. I detta fall föregås divisionsoperationen av multiplikationsoperationen, som utför en vänsterförskjutning av ^ -bit informationskodkombinationen med G utsläpp.

Vid avkodning av det mottagna n-bitarskodordet utförs åter division med det genererande (genererande, genererande) polynomet.

Felsyndromet i dessa koder är närvaron av återstoden av divisionen av det mottagna kodordet av det genererande polynomet. Om syndromet är noll, anses det inte finnas några fel. Annars, med hjälp av det resulterande syndromet, kan du bestämma bitnumret för det mottagna kodordet, i vilket felet inträffade, och korrigera det.

Möjligheten för flera fel i kodkombinationerna är dock inte utesluten, vilket kan leda till falska korrigeringar och (eller) icke-detektering av fel när en tillåten kombination transformeras till en annan.

Låt det totala antalet bitar i blocket vara lika med i, varav användbar information bära T bitar, då är det i händelse av ett fel möjligt att korrigera j bitar. Beroende 5 på NS och T för koder kan bestämmas från tabell. 2.6.

Tabell 2.6

Beroende av det totala antalet siffror av kombinationer av antalet informationssiffror och korrigerade siffror

Ökar skillnaden (n - t), du kan inte bara öka antalet korrigerbara bitar s, men också upptäcka flera fel. Procentandelen av upptäckta flera fel visas i tabellen. 2.7.

Tabell 2.7

Procentandel av flera upptäckta fel

Det är bekvämt att beskriva cykliska koder och deras konstruktion med hjälp av polynom (eller polynom). Kombinationen skrivs i form av ett polynom för att på ett formaliserat sätt visa funktionen för det cykliska skiftet för det ursprungliga kodordet. Så, "-elementkodkombinationen kan beskrivas av polynomet (NS- 1) grader:

varett „_j =(0, 1) ochett „_, =0 motsvarar noll element i kombinationen, q „_, = 1 - icke-noll;i- numret på biten i kodkombinationen.

Låt oss representera polynomen för specifika 4-elementkombinationer:

Additions- och subtraktionsoperationer är ekvivalenta och associativa och utförs modulo 2:

Exempel på att utföra operationer:

Divisionsoperationen är den vanliga divisionen av polynom, men istället för subtraktion används additionsmodulo 2:

Cyklisk förskjutning av en kodkombination - flytta dess element från höger till vänster utan att störa deras ordning, så att elementet längst till vänster tar platsen för det längst till höger.

Huvudegenskaperna och namnet på cykliska koder är relaterade till det faktum att alla tillåtna kombinationer av bitar i det överförda meddelandet (kodorden) kan erhållas genom operation av cyklisk skiftning av något källkodord.

Låt oss säga att den ursprungliga kodkombinationen och motsvarande polynom ges:

Multiplicera Åh) på NS:

Sedan den maximala graden NS i ett kodord av längd NS inte överstiger (n - 1), sedan från höger sida av det resulterande uttrycket för att erhålla det ursprungliga polynomet är det nödvändigt att subtrahera Åh"- 1). Subtraktion Åh"- 1) kallas att ta resten modulo (x n - 1).

Förskjutningen av den ursprungliga kombinationen med / mått kan representeras enligt följande: yxa)? Y - Åh"- 1), dvs. multiplikation Åh) nah "och tar resten modulo (x" - 1). Att ta resten är nödvändigt när man erhåller ett polynom med grad som är större än eller lika med NS.

Idén att konstruera cykliska koder är baserad på användningen av irreducerbara polynom. Ett irreducerbart polynom är ett polynom som inte kan representeras som en produkt av polynom av lägre grader, d.v.s. delbar endast med sig själv eller med en och inte delbar med något annat polynom. Binomialen (x "+ 1) är delbara med ett sådant polynom utan rest. Irreducerbara polynom i teorin om cykliska koder spelar rollen som att generera polynom.

För att återgå till definitionen av den cykliska koden och med hänsyn till registreringen av de cykliska skiftoperationerna för kodkombinationerna, kan vi skriva genereringsmatrisen för den cykliska koden i följande form:

varP (x)- den ursprungliga kodkombinationen, på grundval av vilken alla andra(T- 1) grundläggande kombinationer;

С, = 0 ellerCj =1 ("O" om den resulterande graden av polynometP (x) -x 'inte överstiger (l - 1), eller "1" - om det gör det).

Kombination P (x) kallas en genererande (generator) kombination. För att konstruera en cyklisk kod räcker det att välja rätt P (x). Då är alla andra kodkombinationer desamma som i gruppkoden.

Generatorpolynomet måste uppfylla följande krav:

P (x) måste vara icke-noll;
vikten P (x) får inte vara mindre än det minsta kodavståndet: V (P (x))> d mm;
P (x) måste ha högsta examen k (k - antalet redundanta element i koden);
P (x) måste vara en divisor av polynomet (x "- 1).

Uppfyllelsen av det sista villkoret leder till det faktum att alla arbetskodkombinationer av den cykliska koden får egenskapen delbarhet med P (x) utan rest. Med hänsyn till detta kan vi ge en annan definition av en cyklisk kod: en cyklisk kod är en kod, vars alla arbetskombinationer är delbara med generatorpolynomet utan rest.

För att bestämma graden av det genererande polynomet kan man använda uttrycket r> log 2 (och + 1), var NS- storleken på det överförda paketet åt gången, dvs. längden på den konstruerade cykliska koden.

Exempel på att generera polynom ges i tabellen. 2.8.

Tabell 2.8

Exempel på generatorpolynom

Algoritmen för att erhålla en tillåten kodkombination av en cyklisk kod från en kombination av en enkel kod är som följer.

Låt ett polynom ges P (x) = a z _ (x z + a z _ 2 x r ~ 1 + ... + 1, som bestämmer kodens korrigeringsförmåga och antalet kontrollbitar Till, samt den ursprungliga kombinationen av en enkel från-elementkod och informationsbitar i form av ett polynom A m (x).

Det är nödvändigt att bestämma den tillåtna kodkombinationen av den cykliska koden (och, Till).

1. Vi representerar den ursprungliga kodkombinationen i form av ett polynom A m (x). Vi multiplicerar polynomet för det ursprungliga kodordet med x g: A t (x) x d. Grad av att generera polynom G lika med värdet av den mest signifikanta biten i det ursprungliga kodordet.
2. Bestäm kontrollsiffrorna som kompletterar den ursprungliga informationskombinationen till den tillåtna, som resten av att dividera produkten som erhållits i föregående stycke med generatorn

polynom:

Resten av divisionen betecknas som R(x).

3. Det slutligen lösta cykliska mönstret

kod definieras som = Och t (x)? xr + R (x).

För att bestämma felen i det mottagna kodordet räcker det att dividera det med det genererande polynomet. Om den accepterade kombinationen är laglig kommer resten av divisionen att vara noll. En rest som inte är noll indikerar att den accepterade kombinationen innehåller fel. Beroende på typen av återstoden (syndromet) är det i vissa fall också möjligt att dra en slutsats om felets natur och dess placering och rätta till felet.

Algoritmen för att fastställa felet är som följer.

Låt "-elementkombinationerna ( n = k + t).

1. Vi identifierar det faktum att det finns ett fel. Vi får resten av divisionen av den accepterade kombinationen A n - (x) till det genererande polynomet P (x): A(NS)
--- = Rq (x). Restens närvaro R 0 (x) för (A 0 (x) f 0) indikerar P (x)

om felet.

2. Dela det resulterande polynomet # (x) = Л „_,(NS) 0 Rq (x) per generator Rg (x): W-1 = R (x), var R (x)- aktuellt saldo.

3. Jämför LDx) och R(x). Om de är lika, inträffade felet i den mest signifikanta biten. Om inte, ökar vi graden av det adopterade polynomet med x och dividerar igen:

4. Jämför det resulterande saldot med Rq (x). Om de är lika, så inträffade felet i den andra biten. Om de inte är lika, då multiplicerar vi Shx) x 2 och upprepa dessa operationer tills vi får

R(x) = Helvete.

Felet kommer att vara i siffran som motsvarar siffran med vilken graden ökas Shx), plus 1. Till exempel när det gäller jämställdhet R (x) och LDx)

Matchar detta ord, från 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 adderas och multipliceras (element för element), och resultatet blir i samma fält. Polynomet som motsvarar en linjär kombination av ett par ord och är lika med en linjär kombination av dessa ords polynom

Detta tillåter oss att betrakta uppsättningen ord med längden n över ett ändligt fält som ett linjärt utrymme av polynom med grad som högst n-1 över fältet

Algebraisk beskrivning

Om kodord erhålls genom att cykliskt skifta en bit åt höger från ordet, sedan motsvarande polynom c 1 (x) erhålls från den föregående genom att multiplicera med x:

Utnyttja det faktum att,

Skift till 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) kod, sedan m(x)c(x)mod(x n − 1) är också kodordet för denna kod.

Genererar polynom

Definition Det genererande polynomet för den cykliska ( n,k) kod C kallas ett sådant polynom som inte är noll från C, vars grad är den minsta och koefficienten i 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 generatorpolynomet för den cykliska ( n,k) av koden är en divisor av binomialet x n − 1

Konsekvenser: alltså, som ett genererande polynom, kan du välja vilket polynom som helst, 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 vid icke-noll m(x), vilket är omöjligt.

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

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

Matrisen G kan skrivas i symbolisk form:

Kontrollera matrisen

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

Kodning

Osystematisk

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 polynommultiplikatorer.

Systematisk

Med systematisk kodning bildas kodordet i form av ett informationsunderblock och en check

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

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

Sedan av tillståndet följer det

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

Exempel på

Binär (7,4,3) kod

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

Generativ matris koda:

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

Kontrollera matris:

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

Så, till exempel, den 3:e kolumnen erhålls, 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 av två divisorer 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 produkten av 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 randvillkor

Se vad "cykliska koder" är i andra ordböcker:

förkortade cykliska koder- - [L.G. Sumenko. Den engelska ryska ordboken för informationsteknologi. M .: GP TsNIIS, 2003.] Ämnen informationsteknologi i allmänhet EN förkortade cykliska koder ...

Reed-Solomon-koder- Icke-binära cykliska koder för att korrigera fel i datablock. Elementen i kodvektorn är inte bitar, utan grupper av bitar (block). Reed Solomon-koder som fungerar med bytes (oktetter) är mycket vanliga. Reed Solomons kod är ... Wikipedia

Golay-koder- En familj av perfekta linjära blockkoder med felkorrigering. Den mest användbara är den binära Golay-koden. 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- Detektering av fel i kommunikationsteknik, en åtgärd som syftar till att övervaka dataintegriteten under inspelning/uppspelning av information eller under dess överföring över kommunikationslinjer. Korrigering av fel (korrigering av fel) proceduren för att återställa information efter ... ... Wikipedia

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

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

i synnerhet cyklisk, baserad på strukturer av finit aritmetik

Galois fält. Vid fältet kallas mängden element som har ett ändligt fält

operationernas namn står inom citattecken eftersom de inte alltid är allmänt accepterade aritmetiska operationer. Fältet innehåller alltid ett nollelement (0), eller noll, och ett ettelement (1), eller ett. Om antalet q elementen i fältet är begränsade, då anropas fältet ändligt fält, eller ändligt Galois-fält, och betecknas GF (q) y var q - fältorder. Det minsta Galois-fältet är iolen med två element GF ( 2), bestående av endast två element 1 och 0. För att

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

utföra operationer på element GF ( 2) inte ledde till att gå utöver detta fält, de utförs modulo 2 (i allmänhet bestäms detta av fältets ordning för enkla Galois-fält).

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

För additions- och multiplikationsoperationer följs de vanliga matematiska associativitetsreglerna - a + (B + c) = (a + B)+ c, kommutativitet - a + b = b + a och a b = b a och distribution - a (B+ s) = a b + a med.

För varje element i fältet a omvänd addition måste finnas (-a) och om a icke-noll, inverst element av multiplikation (th ').

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

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

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

Faktum är att alla uppsättningar som bildas av cyklisk permutation av ett kodord också är kodord. Så, till exempel, cykliska permutationer av kombination 1000101 kommer också att vara kodkombinationer 0001011, 0010110, 0101100, etc. Denna egenskap gör det möjligt att avsevärt förenkla kodaren och avkodaren, speciellt när man upptäcker fel och korrigerar ett enskilt fel. Uppmärksamhet på cykliska koder beror på det faktum att deras inneboende höga korrigeringsegenskaper realiseras på basis av relativt enkla algebraiska metoder. Samtidigt, för avkodning av en godtycklig linjär blockkod, används ofta tabellformade metoder, som kräver en stor mängd avkodarminne.

En cyklisk kod kallas ett linjärt block (n, k) - kod som är cyklisk, dvs. en vänsterförskjutning av ett tillåtet kodord 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 gradpolynom (NS- 1) eller mindre delbart med det genererande polynomet g (x) grad r = n-k y binom NS n +

I en cyklisk kod representeras kodord av polynom (polynom)

var NS - kodlängd; Ett jag - Galois-fältkoefficienter (kodkombinationsvärden).

Till exempel, för kodkombinationen 101101, har polynomnotationen formen

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

Hamming kod... Hammingkodens felkorrigeringsmöjligheter är relaterade till det minsta kodningsavståndet d 0. Alla multiplicitetsfel är fixade q= cnt (d 0- l) / 2 (här står cnt för "heltalsdel") och multiplicitetsfel upptäcks d 0 - 1. Så, när du kontrollerar konstigheter d Q = 2 och enstaka fel upptäcks. I Hamming-koden d 0 = 3. Förutom informationsbitarna, en L = log 2 Q av redundanta kontrollbitar, där Q - antalet informationsbitar. Parameter L avrundat till närmaste högre heltalsvärde. L-bitars kontrollkod är det inverterade resultatet av bitvis addition (addition modulo 2) av antalet av dessa informationsbitar, vars värden är lika med en.

Exempel 7.7

Anta att vi har huvudkoden 100110, dvs. Q = 6. Låt oss definiera en extra kod.

Lösning

Det finner vi L= 3 och kompletterande kod är

där P är symbolen för den bitvisa additionsoperationen, och efter invertering 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 överförda. Jämförelsekoden är fast, 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 av 010SH10 = 100, dvs. 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 - Solomon-koder baseras på Galois-fält, eller efterföljande nollor. Aritmetiska operationer är addition, subtraktion, multiplikation, division etc. över element av en avslutande nolla ger ett resultat som också är ett element av den nollan. En Reed-Solomon-kodare eller avkodare måste utföra dessa operationer. Alla operationer 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 symboluppsättningarna för en redundant kod betraktas som elementära informationssymboler för en annan redundant kod. Ett sådant förbund började kallas kaskad koda. En stor fördel med sammanlänkade koder är att deras användning gör det möjligt att förenkla kodaren och speciellt avkodaren i jämförelse med liknande enheter av icke sammanlänkade koder av samma längd och redundans. Sammankopplad kodning ledde till skapandet av turbokoder. Turbokod kallas en parallell signalstruktur bestående av två eller Mer systematiska koder. Grundprincipen för deras konstruktion är användningen av flera komponentkodare som arbetar parallellt. Som komponentkoder kan du använda både block- och faltningskoder, Hamming-koder, PC-kod, BCH, etc. Användningen av perforering (punktering) gör det möjligt att öka den relativa hastigheten för turbokoden, anpassa dess korrigeringsförmåga till de statistiska egenskaperna hos kommunikationskanalen. Principen för turbokodbildning är följande: insignal NS, bestående av TILL bit, matas parallellt med N interfolierare. Var och en av de senare är en enhet som permuterar element i ett block av TILL bitar i pseudo-slumpmässig ordning. Utsignalen från interfolierarna - de omordnade symbolerna - matas till motsvarande elementära kodare. Binära sekvenser x p i= 1,2, ..., JV, vid kodarens utgång finns kontrollsymboler, som tillsammans med informationsbitarna utgör ett enda kodord. Användningen av interfolieraren 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 rekursiva avkodningsmetoden, som är traditionell vid bearbetning. Beroende på valet av komponentkod är turbokoderna uppdelade i faltningsturbokoder och blockproduktkoder.

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

Idén att konstruera cykliska koder är baserad på användningen av polynom som är irreducerbara inom binära tal. Oreducerbar polynom kallas som inte kan representeras som en produkt av polynom av 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, irreducerbara polynom är delbara utan rester endast av sig själva eller genom enhet.

Irreducerbara polynom i teorin om cykliska koder spelar rollen som generatorer av polynom. Om den givna kodkombinationen multipliceras med det valda irreducerbara polynomet, får vi en cyklisk kod, vars korrigeringsmöjligheter bestäms av det irreducerbara polynomet.

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

G (x) x n =(x 3 + x 2 + 1) x 3 = x 6 + x 5 + x 3 = 1101000.

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

Värdet på korrigeringssiffrorna framgår av resultaten från divisionen 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 in allmän syn

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

Eftersom i binär aritmetik 1 Å 1 = 0, vilket betyder -1 = 1, är det möjligt, när man adderar binära tal, att överföra termer från en del till en annan utan att ändra tecknet (om det är lämpligt), därför är en likhet på formen a Å b = 0 kan skrivas som a = b, Och hur a - b = 0. Alla tre likheterna i det här fallet betyder det heller 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) = Q (x) P (x) = G (x) x n + R (x),

vilket i fallet med vårt exempel kommer att ge

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

F (x) = 1111 1011 = 1101000 + 001 = 1101001.

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

Och här spelas den avgörande rollen av egenskaperna hos det genererande polynomet P (x)... Metoden för att konstruera en cyklisk kod är sådan att generatorpolynomet deltar i bildningen av varje kodkombination, därför delas varje polynom i den cykliska koden av generatorn utan en rest. Men bara de polynom som hör till den givna koden är delbara utan rester, det vill säga det genererande polynomet låter dig välja de tillåtna kombinationerna från alla möjliga. Om, när man dividerar den cykliska koden med det genererande polynomet, en rest erhålls, så har antingen ett fel inträffat i koden, eller så är det en kombination av någon annan kod (förbjuden kombination). Av resten detekteras närvaron av en förbjuden kombination, det vill säga ett fel detekteras. Återstoden av divisionen av polynomen är feligenkännarna för cykliska koder.

Å andra sidan används resten av att dividera ett med nollor med det genererande polynomet för att konstruera cykliska koder.

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

01100 11111+

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

Återstoden från division används för att konstruera genererande matriser, som, på grund av sin klarhet och bekvämlighet för att erhålla derivatkombinationer, används allmänt för att konstruera cykliska koder. Konstruktionen av en genererande matris reduceras till kompileringen av en enhetstransponerad och ytterligare matris, vars element är återstoden av att dividera en med nollor med det genererande polynomet P (x)... Kom ihåg att den transponerade identitetsmatrisen är en kvadratisk matris, vars alla element är nollor, förutom de element som är placerade diagonalt från höger till vänster från topp till botten (i en otransponerad 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 rester vars vikt är W ³ d 0- 1, var 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... De återstående kombinationerna av koden 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 sändning av 10-bitars binära kombinationer.

Lösning.

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

Tabell 5.12 - Samband mellan information och kontrolltecken för en kod med en längd på upp till 16 bitar

n	k	ρ	n	k	ρ

Enligt tabellen kommer detta värde att vara k = 11, medan r = 4, a

n = 15. Vi väljer också generatorpolynomet x 4 + x 3 +1.

Den kompletta genereringsmatrisen är konstruerad från enhetens transponeringsmatris i kanonisk form och en extra matris som motsvarar kontrollsiffrorna.

Transponera matris för k = 11 ser ut så här:

En ytterligare matris kan konstrueras från resten av divisionen av en kombination i form av ett följt av nollor (den sista raden i den identitetstransponerade matrisen) av det valda genererande polynomet.

Den fullständiga generatormatrisen kommer att se ut så här:

Ovanstående metod för att konstruera genererande matriser är inte den enda. Generatormatrisen kan konstrueras som ett resultat av direkt multiplikation av elementen i identitetsmatrisen med generatorpolynomet. Detta är ofta bekvämare än att hitta resten av en division. De resulterande koderna skiljer sig inte på något sätt från koder konstruerade från genererande matriser, där den extra matrisen består av resten av att dividera en med nollor med det genererande polynomet.

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

Fel i cykliska koder detekteras genom att använda resten av att dividera den resulterande kombinationen med det genererande polynomet. Resten av divisionen är felidentifierare, men indikerar inte direkt platsen för felet i den cykliska koden.

Idén med felkorrigering bygger på det faktum att den felaktiga kombinationen efter ett visst antal cykliska skift "passas" till resten på ett sådant sätt att den tillsammans med resten ger det korrigerade kodordet. I det här fallet är resten inget annat ä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 justerad med cykliska skift. Den förvrängda kombinationen justeras tills antalet ettor i resten är lika med antalet fel i koden. I detta fall kan naturligtvis antalet ettor vara lika med antalet fel s, korrigeras av denna kod (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 k ³ (n / 2), sedan efter ett visst antal skift kommer alla fel att vara i zonen för "engångs"-åtgärden för det genererande polynomet, det vill säga det räcker för att få en rest, vars vikt är W £ s, och detta kommer redan att vara tillräckligt för att korrigera den förvrängda kombinationen.

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