Cyklisk kod

Cykliska koderär bland de blocksystematiska 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 hittas

klä sig på vissa ställen. Möjligheten att upptäcka och korrigera praktiskt taget alla fel med en relativt liten redundans jämfört med andra koder, såväl som enkelheten i kretsimplementeringen av kodnings- och avkodningsutrustningen, gjorde dessa koder utbredda. Teorin om cykliska koder bygger på gruppteori och polynomalgebra över Galoisfältet.

En cyklisk kod är en kod i vilken ordningen för distribution av kodkombinationer utförs på ett sådant sätt att Hamming-kodavståndet förblir konstant varje gång vid övergång från vilken kombination som helst till en angränsande.

Cykliska koder är en hel familj av felkorrigerande koder, inklusive Hamming-koder som en av varianterna, men ger generellt sett större 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 överföring av kodkombinationer över en kommunikationskanal. Den cykliska koden hänvisar till systematiska blockkoder (n, k), i vilka de första k bitarna är en kombination av den primära koden, och de efterföljande (n × k) bitarna är kontrollbitar.

Konstruktionen av cykliska koder är baserad på operationen att dividera det sända kodordet med ett genererande irreducerbart polynom med graden r. Resten av divisionen används vid bildandet av kontrollbitar. I detta fall föregås divisionsoperationen av en multiplikationsoperation som skiftar k-bitars informationskodkombination åt vänster med r bitar.

Ett polynom (polynom), som kan representeras som en produkt av polynom av lägre grader, kallas reducerbart (i ett givet fält), annars är det irreducerbart. Irreducerbara polynom spelar en roll som liknar primtal i talteorin. De irreducerbara polynomen P(X) kan skrivas som decimala eller binära tal, eller som ett algebraiskt polynom.

Cyklisk kodningsprocess

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

Som informationssymboler k för att konstruera cykliska koder tas kombinationer av en binär kod för alla kombinationer. I det allmänna fallet, om en given kodkombination Q(x) multipliceras med ett genererande polynom P(x), får vi en cyklisk kod som har vissa korrigerande egenskaper beroende på valet av P(x). I denna kod kommer emellertid kontrollsymbolerna m att vara placerade på en mängd olika platser i kodordet. En sådan kod är inte systematisk, vilket gör det svårt att implementera den i kretsar. Situationen kan avsevärt förenklas om kontrolltecken tilldelas i slutet, det vill säga efter informationstecken. För detta ändamål är det lämpligt att använda följande metod:

Multiplicera kodordet G(x) som ska kodas med monomer X m som har samma grad som polynomet P(x);

Vi dividerar produkten G(x)X m med det genererande polynomet P(x m):

där Q(x) är divisionens kvot; R(x) - återstoden.

Genom att multiplicera uttrycket (2.1) med Р(х) och överföra R(x) till den andra delen av likheten utan att vända tecken, får vi:

Således, enligt likhet (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 för alla kombinationer med ett genererande polynom P(x);

Genom att multiplicera det givna kodordet G(x) med ett enda polynom X m som har samma grad som det genererande polynomet P(x), med tillägg av resten R(x) som erhålls efter att ha dividerat produkten G(x)X m med det genererande polynomet P(X).

Meddelandekodning

Det krävs att kodordet 1100 kodas, vilket motsvarar G(x)=x3+x2 med P(x)=x3+x+1.

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

Om vi ​​dividerar produkten G(x)X m med det genererande polynomet P(x m), enligt (2.1) får vi:

eller i binär motsvarighet:

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

Q(x)=x3 +x2 +x>1110

och resten:

Som ett resultat kommer den binära kodkombinationen som kodas av den cykliska koden, enligt (2.2), att ha formen:

F(x)=1110 1011=1100010

Eftersom varje tillåten kodkombination av en cyklisk kod representerar alla möjliga summor av det genererande polynomet G(x), måste de vara delbara utan återstod med P(x). Därför reduceras kontroll av korrektheten av den mottagna kodkombinationen till att identifiera återstoden när den divideras med ett genererande polynom.

Att ta emot resten indikerar förekomsten av ett fel. Resten av divisionen i cykliska koder spelar rollen som ett syndrom.

Till exempel den sända kodkombinationen F(x)=1100010, konstruerad med användning av det genererande polynomet P(x)=1011. Under påverkan av störningar omvandlades kodkombinationen till en kombination F "(x) = 1000010

Vi dividerar den mottagna kombinationen med det genererande polynomet

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

Låt oss bestämma platsen för felet, för detta delar vi enheten med ett godtyckligt antal nollor med P(x)=1011.

Ett fel uppstod i elementnummer:

Antal rester -2>4-2=2

Det vill säga, felet finns i det andra elementet.

Cykliska koder kallas så eftersom i dem kan vissa eller alla kombinationer av koden erhållas genom cyklisk skiftning av en eller flera kombinationer av koden. Det cykliska skiftet utförs från höger till vänster, där tecknet längst till vänster överförs till slutet av kombinationen varje gång. Cykliska koder tillhör praktiskt taget alla systematiska koder, där kontroll- och informationsbitar finns på strikt definierade platser. Dessutom finns koderna bland blockkoderna. 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 med en.

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

Anta att du vill koda en av kombinationerna av en fyrsiffrig binär kod. Låt oss också anta att denna kombination G(x) = x 3 + x 2 + 1® 1011. Utan att motivera vårt val tar vi från tabellen över irreducerbara polynom som ett genererande polynom P(x) = x 3 + x + 1® 1011. Multiplicera sedan G(x) till ett monomer av samma grad som det genererande polynomet. Från att multiplicera ett polynom med en monom av grad n graden av varje term i polynomet kommer att öka med n, vilket motsvarar tilldelning n nollor från siffrorna med låg ordning 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 så att det senare i stället för dessa nollor skulle vara möjligt att skriva korrigerande bitar.

Värdet på de korrigerande siffrorna hittas från resultatet av divisionen G(x) x n på P(x):

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

x6 +0+x4 +x3

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

x4 + x3 +x2 +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)¾ kvot, och R(x)¾ återstoden av divisionen G(x)×xn på P(x).

Eftersom i binär aritmetik 1 Å 1 = 0, och därmed -1 = 1, när man adderar binära tal, är det möjligt att överföra termer från en del till en annan utan att ändra tecken (om det är lämpligt), därför är likheten i formen a Å b = 0 kan också skrivas som a = b, Och hur a - b = 0. Alla tre likheterna i detta fall betyder det heller a Och bär 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.

Polynomet 1101001 är den önskade kombinationen, där 1101- informationsdelen, och 001 är kontrolltecken. Observera att vi skulle ha erhållit 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 ett genererande polynom, och genom att multiplicera en given kombination med en monom som har samma grad som det valda genererande polynomet (i vårt fall erhölls kombinationen 1101000) på detta sätt, följt av att till den resulterande produkten adderades resten av divisionen av denna produkt med det genererande polynomet (i vårt exempel har resten blankett 001).

Och här spelar egenskaperna hos det genererande polynomet en avgörande roll P(x). Metoden för att konstruera en cyklisk kod är sådan att generatorpolynomet deltar i bildandet av varje kodkombination, så varje polynom i den cykliska koden delas av generatorn utan en rest. Men bara de polynom som hör till given kod, dvs. det genererande polynomet låter dig välja tillåtna kombinationer bland 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 detta en kombination av någon annan kod (en olaglig kombination). Av resten och närvaron av en förbjuden kombination detekteras, dvs ett fel detekteras. Återstoden från divisionen av polynom är identifierare för fel i cykliska koder.

Å andra sidan används resterna från att dividera ett med nollor med ett genererande polynom för att konstruera cykliska koder.

När man dividerar en enhet med nollor med ett genererande polynom bör man komma ihåg att längden på resten inte får vara mindre än antalet kontrollbitar, därför, i händelse av brist på bitar i resten, det erforderliga antalet nollor tillskrivs resten till höger.

01100 11111+

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

Rester från division används för att konstruera genererande matriser, som, på grund av sin synlighet och bekvämlighet för att erhålla derivatkombinationer, används i stor utsträckning för att konstruera cykliska koder. Konstruktionen av en genererande matris reduceras till kompileringen av en enda transponerad och ytterligare matris, vars element är resterna av att dividera en enhet med nollor med ett genererande polynom P(x). Kom ihåg att den enhetstransponerade matrisen ä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 icke-transponerad matris är diagonalen med identitetselement placerad från vänster till höger, uppifrån och ned). Elementen i den extra matrisen tilldelas till höger om den identitetstransponerade matrisen. Endast de rester, vars vikt W³d0- 1, var d0- minsta kodavstånd. 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 kodkombinationerna erhålls som ett resultat av modulo 2-summering av 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 - Relationer mellan information och kontrollsymboler för en kod upp till 16 bitar lång

n	k	ρ	n	k	ρ

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

n= 15. Vi väljer också ett genererande polynom x 4 + x 3 +1.

Vi bygger hela generatormatrisen från den enhetstransponerade matrisen i kanonisk form och en extra matris som motsvarar kontrollsiffrorna.

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

En ytterligare matris kan konstrueras genom att resten av kombinationen divideras i form av en enhet med nollor (den sista raden i den identitetstransponerade matrisen) med det valda genererande polynomet.

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

Metoden för att konstruera genererande matriser som beskrivs ovan är inte den enda. Den genererande matrisen kan konstrueras som ett resultat av direkt multiplikation av elementen i identitetsmatrisen med det genererande polynomet. 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 ett genererande polynom.

Den genererande matrisen kan också konstrueras genom att cykliskt skifta kombinationen som erhålls genom att multiplicera raden i identitetsmatrisen av rang k till ett genererande polynom.

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

Idén med felkorrigering bygger på att en felaktig kombination, efter ett visst antal cykliska skift, "justeras" till resten på ett sådant sätt att den tillsammans med resten ger en korrigerad kodkombination. Resten i det här fallet är inget annat än skillnaden mellan de förvrängda och korrekta symbolerna, enheterna i resten ä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 enheter i resten är lika med antalet fel i koden. I detta fall kan naturligtvis antalet enheter antingen vara lika med antalet fel s, korrigeras med 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 mottagna kombinationen 1 fel).

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

Processen för felkorrigering diskuteras i detalj nedan med hjälp av exempel på att konstruera specifika koder.

Cykliska koder kännetecknas av det faktum att under den cykliska permutationen av alla symboler i kodkombinationen av en given kod, bildas en annan kodkombination av samma kod.

Cyklisk kodkombination;

Även en cyklisk kodkombination.

När man överväger cykliska koder binära tal representeras som ett polynom, vars grad ( P - 1), P- längden på kodkombinationen.

Till exempel, kombinationen 1001111 ( n= 7) kommer att representeras av ett polynom

Med denna representation reduceras operationer på kodkombinationer till operationer på polynom. Dessa operationer utförs i enlighet med vanlig algebra, förutom att reduktionen av liknande termer utförs modulo 2.

Feldetektering med hjälp av en cyklisk kod säkerställs genom att välja som tillåtna kombinationer de som delas utan rest med något förvalt polynom G(x). Om den mottagna kombinationen innehåller förvrängda tecken, division med ett polynom G(x) utförs med resten. Detta genererar en signal som indikerar ett fel. Polynom G(x)kallas generering.

Konstruktionen av kombinationer av en cyklisk kod är möjlig genom att multiplicera den ursprungliga kombinationen A(X) till det genererande polynomet G(x) med reduktion av liknande termer modulo 2:

• om produktens högsta effekt inte överstiger ( P - 1), då kommer det resulterande polynomet att representera kodkombinationen av den cykliska koden;
• om produktens högsta effekt är större än eller lika med P, då är produktpolynomet delbart med det förvalda gradpolynomet P och resultatet av multiplikationen är resten av divisionen.

Således kommer alla polynom som representerar kombinationer av en cyklisk kod att ha en grad under P.

Ofta, som ett polynom med vilket divisionen utförs, tas ett polynom G(x)= +1. Med sådan bildande av kodkombinationer kan positionerna för information och kontrollsymboler inte bestämmas i förväg.

En stor fördel med cykliska koder är att det är lätt att konstruera kodare och avkodare, som i sin struktur representerar skiftregister med återkoppling.

Antalet bitar i registret väljs lika med graden av det genererande polynomet.

Respons utförs från utmatningen av registret till några siffror genom adderare, vars antal väljs av en mindre än antalet medlemmar som inte är noll i det genererande polynomet. Adderare installeras vid ingångarna till de bitar i registret, som motsvarar medlemmar som inte är noll i det genererande polynomet.

Figur 17 visar kodningsregisterschemat för omvandling av en fyrabitarskombination till en sjubitarskombination.

Figur 17 - Schema för kodningsregistret

I tabell. 4 visar hur genom att skifta den ursprungliga kombinationen 0101, erhålls den cykliska kodkombinationen 1010011. n= 7, k=4. Kombination 0101, knapp i position 1. Under de första fyra cyklerna kommer registret att fyllas, därefter flyttas nyckeln till position 2. Återkopplingen är stängd. Under inverkan av sju skiftcykler sker bildandet av en sjubitars cyklisk kod.

Tabell 4

Cyklisk kodegenskaper:

1) den cykliska koden detekterar alla enstaka fel om det genererande polynomet innehåller mer än en medlem. Om G(x)=x+ 1, då detekterar koden enstaka fel och alla udda;

2) cyklisk kod med G(x)= (x+ 1)G(x) upptäcker alla enkla, dubbla och trippelfel;

3) en cyklisk kod med ett genererande polynom G(x) grader r = n - k upptäcker allt gruppfel varaktighet i r tecken.

Kontrollfrågor

Vitrysslands statliga universitet för informationsvetenskap och radioelektronik

Institutionen för RES

abstrakt om ämnet:

Cykliska koder. BCH-koder"

MINSK, 2009

Cykliska koder

En cyklisk kod är en linjär block (n,k)-kod, som kännetecknas av egenskapen cyklicitet, dvs. skiftning åt vänster ett steg av ett tillåtet kodord ger också det tillåtna ett kodord, som tillhör samma kod och för vilken 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 = n-k, vilket är en faktor av binomialen xn+1.

Polynomet g(x) kallas generering.

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

där n är längden på koden; - koefficienter från fältet GF(q).

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

sedan motsvarande polynom

Till exempel, om koden byggs över fältet GF(q)=GF(2 3), vilket är en förlängning av GF(2) modulo ett irreducerbart polynom f(z)=z 3 +z+1, och elementen i detta fält har den form som visas 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 följande slag
där m är graden av polynomet med vilken förlängningen av fältet GF(2) erhålls; a i - koefficienter som tar värdet av elementen i GF(2), dvs. 0 och 1. En sådan kod kallas q-th.

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 längden på koden är mindre än längden på den primitiva koden kallas koden förkortad eller icke-primitiv.

Som följer av definitionen är en gemensam egenskap för kodorden i en cyklisk kod deras delbarhet utan rest med något polynom g(x), kallat generatorn.

Resultatet av att dividera binomet x n +1 med polynomet g(x) är testpolynomet h(x).

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

Felpolynomet med högst (n-1) grad bestäms från uttrycket

där är polynom som representerar de mottagna (i fel) respektive sända kodorden.

Koefficienter som inte är noll i e(x) upptar positioner som motsvarar fel.

Exempel.

Det syndromiska polynomet som används vid avkodning av den cykliska koden definieras som resten av att dividera det mottagna kodordet med generatorpolynomet, dvs.

eller

Därför beror syndrompolynomet direkt på felpolynomet e(x) Denna bestämmelse används vid konstruktionen av syndromtabellen som används i avkodningsprocessen. Denna tabell innehåller en lista över felpolynom och en lista över motsvarande syndrom som bestäms frå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, dvs.

De listade polynomen kan adderas, multipliceras och divideras med de kända algebrareglerna, men med resultatet reducerat mod 2, och sedan mod x n +1 om graden av resultatet överstiger graden (n-1).

Låt oss anta att längden på koden är n=7, då ger vi resultatet mod x 7 +1.

När man konstruerar och avkodar cykliska koder, som ett resultat av division av polynom, är det vanligtvis nödvändigt att inte ha en kvot, utan en rest från division.
Därför rekommenderas en enklare divisionsmetod som inte använder polynom, utan endast dess koefficienter (alternativ 2 i exemplet).

Exempel.

Matristilldelning av koder

Den cykliska koden kan ges genom att generera och kontrollera matriser. För att konstruera dem räcker det att känna till generatorn g(x) och testa h(x) polynom. För en icke-systematisk cyklisk kod konstrueras matriser genom en cyklisk förskjutning av de genererande och kontrollerande polynomen, dvs. genom att multiplicera dem med x

Och

När man konstruerar matrisen H (n,k) finns den ledande koefficienten för polynomet h(x) 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) från uttrycket

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

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

eller

R 4,3 bestäms med användning av

därför att

På liknande sätt är det bestämt

En cyklisk kod är en linjär kod, som är en ändlig uppsättning stängd med avseende på driften av en cyklisk förskjutning av kodvektorerna som bildar den. Låt det ges n-dimensionell vektor v = a 0 a 1 …en-1 med koordinater från destinationsfält F. Dess cykliska förskjutning kallas vektorn v"= a n-1 a 0 a 1... en -2 .

Överväga n-dimensionellt aritmetiskt utrymme över ett Galois-fält GF(2). Varje vektor a 0 a 1 …en-1 av GF(2) man kan associera ett en-till-ett polynom a 0 +a 1 x+…+en -1 x n-1 med koefficienter från GF(2). Summan av två vektorer a 0 a 1 …en-1 och b 0 b 1 …b n-1 motsvarar summan av polynomen som motsvarar dem, 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 utrymmet. Mängden av alla polynom från detta delrum som är delbara utan rest med g(x) bildar ett linjärt delrum. Ett linjärt delrum definierar någon linjär kod.

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

Låt oss visa hur polynomkoderna är relaterade C(g(x)) och cykliska koder. Låta a = a 0 …en-1 är något kodord, och motsvarande kodpolynom a(x) = a 0 +...+en -1 x n-1 . cykliskt skifte a" motsvarar kodpolynomet a"(x) = en -1 +a 0 x+…+en -2 x n -1 , som kan uttryckas i termer av originalet:

Eftersom polynomkoden måste vara delbar med g(x), för att det ska vara cykliskt, polynomet a"(x) måste vara delbart med g(x). Utifrån denna övervägande kan vi formulera följande teorem. En polynomkod är cyklisk om och endast om polynomet g(x) är en divisor av polynomet x n-1. I det här fallet polynomet g(x) kallas ett genererande polynom av en cyklisk kod.

I kodningsteorin bevisas följande sats: om ett polynom g(x) har en examen n–k och är en divisor x n-1 alltså C(g(x)) är linjär cyklisk ( n, k)-koda.

Polynom x n-1 faktorisera x n–1 = (x–1)(x n -1 +x n-1 +...+1). Därför finns cykliska koder för alla n. Antal cykliska n-bitkoder är lika med antalet divisorer för polynomet x n-1. För att konstruera cykliska koder har tabeller för uppdelning av polynom utvecklats x n-1 för irreducerbara polynom, det vill säga för de som bara är delbara med 1 och sig själv.

Fundera till exempel på vilka koder som kan byggas utifrån polynomet x 7–1 över planen GF(2). Nedbrytningen av ett polynom till irreducerbara faktorer har formen

Eftersom det är möjligt att bilda sex divisorer av polynomet x 7–1, genom att kombinera irreducerbara divisorer, 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är graden av divisorpolynomet x n-1 definierar koden. Följande är divisorerna för 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+x3+x2+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 endast en kontrollsymbol och (7, 1)-koden har endast en informationssymbol. De är en paritetskontrollkod respektive en upprepningskod.

Liksom en vanlig linjär kod kan en cyklisk kod ges av en genererande matris. Därför är uppgiften att hitta en sådan matris, det vill säga att hitta k linjärt oberoende kodkombinationer som bildar den. För detta använder vi egenskapen för stängning av en cyklisk kod med avseende på driften av ett cykliskt skift. Observera att en cyklisk förskjutning åt höger med en siffra är ekvivalent med att multiplicera polynomet g(x) på x. Sedan kan den genererande matrisen konstrueras genom att ta det genererande polynomet och som rader k dess cykliska skiftningar:

Låt oss nu överväga hur, med hjälp av det genererande polynomet g(x) = 1+x+x 3 är kodad med (7, 4)-kod. Ta till exempel ett 4-bitars ord (0101), som motsvarar polynomet f(x) = x + x 3 . Multiplicera dessa två polynom