Cyclische code

Cyclische codes behoren tot de bloksystematische codes waarin elke combinatie onafhankelijk wordt gecodeerd (in de vorm van een blok) op een zodanige manier dat de informatie k en besturingssymbolen altijd hetzelfde zijn

kleed je op bepaalde plekken aan. Het vermogen om vrijwel alle fouten te detecteren en te corrigeren met een relatief lage redundantie in vergelijking met andere codes, evenals de eenvoud van de circuitimplementatie van coderings- en decoderingsapparatuur, maakten deze codes wijdverspreid. De theorie van cyclische codes is gebaseerd op groepentheorie en de algebra van polynomen over het Galoisveld.

Een cyclische code is een code waarin de volgorde van distributie van codecombinaties zodanig wordt uitgevoerd dat bij het verplaatsen van een willekeurige combinatie naar de aangrenzende, elke keer dat de Hamming-codeafstand constant blijft.

Cyclische codes zijn een hele familie van foutbestendige codes, waaronder Hamming-codes als een van hun varianten, maar bieden over het algemeen een grotere flexibiliteit in termen van de mogelijkheid om codes te implementeren met het noodzakelijke vermogen om fouten te detecteren en te corrigeren die optreden bij het verzenden van codecombinaties via een communicatiekanaal. Een cyclische code verwijst naar systematische blokcodes (n, k), waarbij de eerste k cijfers een combinatie van de primaire code vertegenwoordigen, en de daaropvolgende (n ? k) cijfers controlecijfers zijn.

De constructie van cyclische codes is gebaseerd op de bewerking waarbij de verzonden codecombinatie wordt gedeeld door een genererende onherleidbare polynoom van graad r. De rest van de deling wordt gebruikt om controlecijfers te vormen. In dit geval wordt de delingsoperatie voorafgegaan door een vermenigvuldigingsoperatie, die de k-bit informatiecodecombinatie met r bits naar links verschuift.

Een polynoom (polynoom) dat kan worden weergegeven als een product van polynomen van lagere graden, wordt reduceerbaar genoemd (in een bepaald veld), anders onherleidbaar. Onherleidbare polynomen spelen een rol die vergelijkbaar is met priemgetallen in de getaltheorie. Onherleidbare polynomen P(X) kunnen worden geschreven als decimale of binaire getallen of als een algebraïsche polynoom.

Cyclisch codeerproces

Cyclische codering is gebaseerd op het gebruik van een irreducibele polynoom P(X), die in relatie tot cyclische codes een generator, generator of genererende polynoom (polynoom) wordt genoemd.

Combinaties van binaire codes voor alle combinaties worden beschouwd als informatiesymbolen k voor het construeren van cyclische codes. In het algemene geval, als een gegeven codecombinatie Q(x) wordt vermenigvuldigd met een genererende polynoom P(x), is het resultaat een cyclische code die bepaalde corrigerende eigenschappen heeft, afhankelijk van de keuze van P(x). In deze code zullen de besturingssymbolen m zich echter op een grote verscheidenheid aan plaatsen in de codecombinatie bevinden. Dergelijke code is niet systematisch, wat de circuitimplementatie ervan moeilijk maakt. De situatie kan aanzienlijk worden vereenvoudigd als controlesymbolen aan het einde worden toegevoegd, dat wil zeggen na informatiesymbolen. Voor dit doel is het raadzaam om de volgende methode te gebruiken:

We vermenigvuldigen de codecombinatie G(x) die gecodeerd moet worden met een monomial Xm die dezelfde graad heeft als de genererende polynoom P(x);

We delen het product G(x)Х m door de genererende polynoom Р(х m):

waarbij Q(x) het delingsquotiënt is; R(x) - rest.

Door uitdrukking (2.1) te vermenigvuldigen met P(x) en R(x) over te dragen naar het andere deel van de gelijkheid zonder het teken om te draaien, verkrijgen we:

Volgens gelijkheid (2.2) kan een cyclische code, dat wil zeggen een gecodeerd bericht F(x), dus op twee manieren worden gevormd:

Vermenigvuldiging van één codecombinatie van een binaire code met alle combinaties door een genererende polynoom P(x);

Door een gegeven codecombinatie G(x) te vermenigvuldigen met een enkele polynoom X m die dezelfde graad heeft als de genererende polynoom P(x), en de rest R(x) op te tellen die wordt verkregen na het delen van het product G(x)X m door de genererende polynoom polynoom P( X).

Codering van berichten

Het is vereist om de codecombinatie 1100, die overeenkomt met G(x)=x 3 +x 2, te coderen met behulp van P(x)=x 3 +x+1.

We vermenigvuldigen G(x) met X m, wat de derde macht heeft, we krijgen:

Door het product G(x)Х m te delen door de genererende polynoom Р(х m), verkrijgen we volgens (2.1):

of in binair equivalent:

Als resultaat verkrijgen we dus het quotiënt Q(x) van dezelfde graad als G(x):

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

en de rest:

Als gevolg hiervan zal de binaire codecombinatie gecodeerd met een cyclische code, volgens (2.2), de vorm aannemen:

F(x)=1110 1011=1100010

Omdat elke toegestane cyclische codecombinatie alle mogelijke sommen van de genererende polynoom G(x) vertegenwoordigt, moeten ze zonder rest deelbaar zijn door P(x). Daarom komt het controleren van de juistheid van de geaccepteerde codecombinatie neer op het identificeren van de rest bij het delen ervan door de genererende polynoom.

Het ontvangen van een saldo duidt op de aanwezigheid van een fout. De rest van de indeling in cyclische codes speelt de rol van een syndroom.

De verzonden codecombinatie F(x)=1100010 is bijvoorbeeld geconstrueerd met behulp van de genererende polynoom P(x)=1011. Onder invloed van interferentie werd de codecombinatie omgezet in de combinatie F"(x)=1000010

We delen de geaccepteerde combinatie door een genererende polynoom

De aanwezigheid van de rest R(x)=001 duidt op een fout. Het geeft echter niet direct de locatie van de fout in de combinatie aan. Om de fout te bepalen, zijn er verschillende methoden gebaseerd op syndroomanalyse.

Laten we de locatie van de fout bepalen; deel één met een willekeurig aantal nullen door P(x) = 1011.

Er is een fout opgetreden in elementnummer:

Aantal residuen -2>4-2=2

Dat wil zeggen, de fout zit in het tweede element.

WIT-RUSLANDSE STAATSUNIVERSITEIT VOOR INFORMATICA EN RADIO-ELEKTRONICA

Afdeling RES

samenvatting over het onderwerp:

"Cyclische codes. BCH-codes"

MINSK, 2009

Cyclische codes

Een cyclische code is een lineaire blokcode (n,k), die wordt gekenmerkt door de eigenschap van cycliciteit, d.w.z. een verschuiving naar links met één stap van elk toegestaan ​​codewoord geeft ook een toegestaan ​​codewoord dat tot dezelfde code behoort en waarvoor de set codewoorden wordt weergegeven door een set polynomen van graad (n-1) of minder, deelbaar door een polynoom g(x) van graad r = n-k , wat een factor is van de binomiale x n +1.

Het polynoom g(x) wordt genereren genoemd.

Zoals uit de definitie volgt, worden codewoorden in een cyclische code weergegeven als polynomen

waarbij n de codelengte is; - coëfficiënten uit het veld GF(q).

Als de code over het GF(2)-veld is opgebouwd, nemen de coëfficiënten de waarden 0 of 1 aan en wordt de code binair genoemd.
Voorbeeld. Als het codewoord van de cyclische code

dan de overeenkomstige polynoom

Als de code bijvoorbeeld is opgebouwd over het veld GF(q)=GF(2 3), wat een uitbreiding is van GF(2) modulo, is de irreducibele polynoom f(z)=z 3 +z+1, en de elementen van dit veld hebben de vorm weergegeven in tabel 1,

dan de coëfficiënten

neem de waarden van de elementen van dit veld en daarom worden ze zelf weergegeven in de vorm van polynomen van de volgende vorm
waarbij m de graad is van de polynoom waarmee de velduitbreiding GF(2) werd verkregen; a i - coëfficiënten die de waarde aannemen van de elementen van GF(2), d.w.z. 0 en 1. Deze code wordt q-th genoemd.

De lengte van een cyclische code wordt primitief genoemd en de code zelf wordt primitief genoemd als de lengte ervan n=q m -1 op GF(q) is.

Als de lengte van de code kleiner is dan de lengte van de primitieve code, wordt de code verkort of niet-primitief genoemd.

Zoals uit de definitie volgt, is de algemene eigenschap van codewoorden van een cyclische code hun deelbaarheid zonder rest door een polynoom g(x), de generator genoemd.

Het resultaat van het delen van de binomiale x n +1 door de polynoom g(x) is de testpolynoom h(x).

Bij het decoderen van cyclische codes worden de foutpolynoom e(x) en de syndroompolynoom S(x) gebruikt.

De foutpolynoom van graad niet meer dan (n-1) wordt bepaald op basis van de uitdrukking

waar zijn polynomen die respectievelijk de ontvangen (met fout) en verzonden codewoorden vertegenwoordigen.

Coëfficiënten die niet nul zijn in e(x) bezetten posities die overeenkomen met fouten.

Voorbeeld.

Het syndromale polynoom dat wordt gebruikt bij het decoderen van een cyclische code wordt gedefinieerd als de rest van het delen van het ontvangen codewoord door het genererende polynoom, d.w.z.

of

Bijgevolg hangt het syndroompolynoom rechtstreeks af van het foutpolynoom e(x). Deze voorziening wordt gebruikt bij het construeren van de syndroomtabel die wordt gebruikt in het decoderingsproces. Deze tabel bevat een lijst met foutpolynomen en een lijst met overeenkomstige syndromen, bepaald op basis van de uitdrukking

(zie tabel 2).

Tijdens het decoderingsproces wordt het syndroom berekend op basis van het ontvangen codewoord, waarna de overeenkomstige polynoom e(x) in de tabel wordt gevonden, waarvan de sommatie met het ontvangen codewoord het gecorrigeerde codewoord oplevert, d.w.z.

De vermelde polynomen kunnen worden opgeteld, vermenigvuldigd en gedeeld met behulp van de bekende algebraregels, maar met het resultaat mod 2, en vervolgens mod x n +1 als de graad van het resultaat de graad (n-1) overschrijdt.

Laten we aannemen dat de codelengte n=7 is, dan presenteren we het resultaat mod x 7 +1.

Bij het construeren en decoderen van cyclische codes als resultaat van het delen van polynomen, is het meestal nodig om niet het quotiënt te hebben, maar de rest van de deling.
Daarom wordt een eenvoudiger delingsmethode aanbevolen, waarbij geen polynomen worden gebruikt, maar alleen de coëfficiënten ervan (optie 2 in het voorbeeld).

Voorbeeld.

Toewijzing van matrixcodes

Een cyclische code kan worden gespecificeerd door een generator en een controlematrix. Om ze te construeren is het voldoende om de genererende g(x) en de testende polynomen h(x) te kennen. Voor een niet-systematische cyclische code worden matrices geconstrueerd door de genererende en controlerende polynomen cyclisch te verschuiven, d.w.z. door ze met x te vermenigvuldigen

En

Bij het construeren van de matrix H (n,k) bevindt de leidende coëfficiënt van de polynoom h(x) zich aan de rechterkant.

Voorbeeld. Voor een cyclische (7.4) code met een genererende polynoom g(x)=x 3 +x+1 hebben de matrices G (n,k) en H (n,k) de vorm:

Waar

Voor een systematische cyclische code wordt de matrix G (n,k) bepaald uit de uitdrukking

waarbij ik de identiteitsmatrix is; Rk,r is een rechthoekige matrix. De rijen van de matrix Rk,r worden bepaald uit de uitdrukkingen waarin a i (x) de waarde is van de i-de rij van de matrix Ik; i is het rijnummer van de matrix Rk,r.

Voorbeeld. De matrix G (n,k) voor de (7.4) code gebaseerd op het genererende polynoom g(x)=x 3 +x+1 wordt in de volgende volgorde opgebouwd

of

R 4,3 wordt bepaald met behulp van

omdat

Op soortgelijke wijze bepaald

Dit is een subklasse van lineaire codes die de gem-eigenschap hebben dat cyclische permutatie van symbolen in een gecodeerd blok een ander mogelijk gecodeerd blok van dezelfde code oplevert. Cyclische codes zijn gebaseerd op de toepassing van ideeën uit de algebraïsche Galoisveldentheorie1.

Veel van de belangrijkste geluidsbestendige codes van communicatiesystemen zijn dat wel

in het bijzonder cyclisch, gebaseerd op de structuren van de eindige rekenkunde

Galois-velden. Veld is de verzameling elementen met een eindig veld

De namen van de bewerkingen staan ​​tussen aanhalingstekens omdat het niet altijd gewone rekenkundige bewerkingen zijn. Het veld bevat altijd een nulelement (0), of nul, en een eenheidselement (1), of één. Als het nummer Q Als de elementen van het veld beperkt zijn, wordt het veld aangeroepen eindig veld, of eindig Galoisveld, en wordt aangegeven GF(q)y Waar Q- veldvolgorde. Het kleinste Galoisveld is een veld met twee elementen GF( 2), bestaande uit slechts twee elementen 1 en 0. Om dat te doen

1 Evariste Galois (1811 - 1832) - Franse wiskundige, legde de basis voor de moderne algebra.

het uitvoeren van bewerkingen op elementen GF( 2) hebben er niet toe geleid dat de grenzen van dit veld werden overschreden, ze worden modulo 2 uitgevoerd (in het algemeen wordt dit bepaald door de volgorde van het veld voor eenvoudige Galoisvelden).

Het veld heeft een aantal specifieke wiskundige eigenschappen. Voor veldelementen zijn optel- en vermenigvuldigingsbewerkingen gedefinieerd, en de resultaten van deze bewerkingen moeten tot dezelfde set behoren.

Voor optel- en vermenigvuldigingsbewerkingen worden de gebruikelijke wiskundige regels van associativiteit gevolgd: A + (B + c) = (een + B)+ c, commutativiteit - een + b = b + een En A b = b A en distributiviteit - A (B+ c) = A B + A Met.

Voor elk veldelement A er moet een omgekeerd element zijn voor de optelling (-A) en als A niet gelijk aan nul, invers element van vermenigvuldiging (th').

Het veld moet bevatten additieve eenheid - element 0 zodanig dat A + 0 = A voor elk veldelement A.

Het veld moet bevatten vermenigvuldigende eenheid - element 1, zodanig dat al = een voor elk veldelement A.

Er zijn bijvoorbeeld velden met reële getallen, rationale getallen en complexe getallen. Deze velden bevatten een oneindig aantal elementen.

In feite zijn alle sets die worden gevormd door cyclische permutatie van een codewoord ook codewoorden. Cyclische permutaties van de combinatie 1000101 zullen dus bijvoorbeeld ook codecombinaties 0001011, 0010110, 0101100, enz. Zijn. Deze eigenschap maakt het mogelijk om coderings- en decoderingsapparaten aanzienlijk te vereenvoudigen, vooral bij het detecteren van fouten en het corrigeren van een enkele fout. De aandacht voor cyclische codes is te danken aan het feit dat hun inherente hoge corrigerende eigenschappen worden geïmplementeerd op basis van relatief eenvoudige algebraïsche methoden. Tegelijkertijd worden voor het decoderen van een willekeurige lineaire blokcode vaker tabelmethoden gebruikt, die een grote hoeveelheid decodergeheugen vereisen.

Een cyclische code is een lineaire blokcode. (n, k)- code die wordt gekenmerkt door de eigenschap van cycliciteit, d.w.z. Door één stap naar links te verschuiven, geeft elk toegestaan ​​codewoord ook een toegestaan ​​codewoord dat tot dezelfde code behoort en waarvoor de set codewoorden wordt weergegeven door een set polynomen van graad (P- 1) of minder, deelbaar door de genererende polynoom g(x) graden r=n-k y wat een factor is van de binominale waarde X n+

In een cyclische code worden codewoorden weergegeven door polynomen (polynomen)

Waar P - codelengte; een ik - coëfficiënten van het Galoisveld (codecombinatiewaarden).

Voor de codecombinatie 101101 heeft de polynoominvoer bijvoorbeeld de vorm

Voorbeelden van cyclische codes zijn even-check-codes, herhaalcodes, Hamming-codes, pc-codes en turbocodes.

Hamming-code. De mogelijkheid om fouten in Hamming-code te corrigeren houdt verband met de minimale codeafstand d0. Alle multipliciteitsfouten worden gecorrigeerd Q= cnt (d0- l)/2 (hier betekent cnt “geheel deel”) en er worden multipliciteitsfouten gedetecteerd d 0 - 1. Dus bij het controleren op oneven pariteit dQ = 2 en enkele fouten worden gedetecteerd. In Hamming-code d0 = 3. Naast de informatiecategorieën wordt het geïntroduceerd L= log 2 Q overtollige controlebits, waarbij Q- aantal informatiebits. Parameter L afgerond naar de dichtstbijzijnde hogere gehele waarde. De L-bit-besturingscode is het omgekeerde resultaat van bitsgewijze optelling (optelling modulo 2) van de getallen van die informatiebits waarvan de waarden gelijk zijn aan één.

Voorbeeld 7.7

Laten we de hoofdcode 100110 hebben, d.w.z. Q = 6. Laten we aanvullende code definiëren.

Oplossing

Dat vinden wij L= 3 en de complementcode is

waarbij P het symbool is van de bitsgewijze optelling, en na omkering hebben we 000. Nu wordt de aanvullende code samen met de hoofdcode verzonden. Bij de ontvanger wordt de aanvullende code opnieuw berekend en vergeleken met de verzonden code. De vergelijkingscode wordt geregistreerd en als deze verschilt van nul, dan is de waarde ervan het nummer van het foutief ontvangen bit van de hoofdcode. Dus als de code 100010 wordt geaccepteerd, is de berekende aanvullende code gelijk aan de inversie van 010Ш10 = 100, d.w.z. 011, wat een fout in het derde cijfer betekent.

Een generalisatie van Hamming-codes zijn cyclische BCH-codes, die het mogelijk maken om meerdere fouten in de aangenomen codecombinatie te corrigeren.

Reed-Solomon-codes zijn gebaseerd op Galoisvelden, of eindige nullen. Rekenkundige bewerkingen optellen, aftrekken, vermenigvuldigen, delen, enz. over de elementen van een uiteindelijke nul geven een resultaat dat ook een element van die nul is. Een Reed-Solomon-encoder of -decoder moet deze bewerkingen noodzakelijkerwijs uitvoeren. Alle bewerkingen om de code te implementeren vereisen speciale hardware of gespecialiseerde software.

Turbocodes. Redundante codes kunnen afzonderlijk worden gebruikt of in de vorm van een combinatie van verschillende codes, wanneer sets symbolen van één redundante code worden beschouwd als elementaire informatiesymbolen van een andere redundante code. Deze vereniging werd genoemd trapsgewijs code. Een groot voordeel van aaneengeschakelde codes is dat het gebruik ervan het mogelijk maakt om de encoder en vooral de decoder te vereenvoudigen in vergelijking met vergelijkbare apparaten met niet-aaneengeschakelde codes van dezelfde lengte en redundantie. Cascadecodering leidde tot het ontstaan ​​van turbocodes. Turbocode noem een ​​parallelle signaalstructuur bestaande uit twee of meer systematische codes. Het basisprincipe van hun constructie is het gebruik van verschillende parallel werkende component-encoders. Als componentcodes kunt u zowel blok- als convolutionele codes, Hamming-codes, PC-code, BCH, enz. gebruiken. Door het gebruik van perforatie (punctie) kunt u de relatieve snelheid van de turbocode verhogen door het corrigerende vermogen ervan aan te passen aan de statistische kenmerken van het communicatiekanaal. Het principe van het genereren van turbocodes is als volgt: ingangssignaal X, bestaande uit NAAR bit, parallel gevoed aan N tussenbladen. Elk van deze laatste is een apparaat dat elementen in een blok herschikt NAAR bits in pseudo-willekeurige volgorde. Het uitgangssignaal van de interleavers – symbolen met een gewijzigde volgorde – wordt naar de overeenkomstige elementaire encoders gestuurd. Binaire reeksen x p ik= 1,2,..., JV, aan de uitgang van de encoder bevinden zich controlesymbolen, die samen met informatiebits één enkel codewoord vormen. Het gebruik van een interleaver maakt het mogelijk om het optreden van reeksen van gecorreleerde fouten te voorkomen bij het decoderen van turbocodes, wat belangrijk is bij het gebruik van de traditionele terugkerende decoderingsmethode bij de verwerking. Afhankelijk van de keuze van de componentcode worden turbocodes onderverdeeld in convolutionele turbocodes en blokproductcodes.

Een cyclische code is een lineaire code, een eindige verzameling die wordt gesloten onder de werking van de cyclische verschuiving van de codevectoren waaruit deze code bestaat. Laat het gegeven worden N-dimensionale vector v = A 0 A 1 …een-1 met coördinaten van het laatste veld F. De cyclische verschuiving ervan wordt een vector genoemd v"= een N-1 een 0 een 1 … een -2 .

Laten we eens overwegen N-dimensionale rekenkundige ruimte over een Galoisveld GF(2). Elke vector A 0 A 1 …een-1 van GF(2) men kan de polynoom één-op-één vergelijken A 0 +A 1 X+…+een -1 x n-1 met noteringen van GF(2). De som van twee vectoren A 0 A 1 …een-1 en B 0 B 1 …b n-1 wordt in overeenstemming gebracht met de som van de polynomen die ermee corresponderen, het product van de veldelementen door de vector - het product van de polynoom die met deze vector correspondeert door het element.

Laten we een polynoom bekijken G(X) uit de beschreven lineaire ruimte. De verzameling van alle polynomen uit deze deelruimte die zonder rest deelbaar zijn door G(X), vormt een lineaire deelruimte. Een lineaire deelruimte definieert een lineaire code.

Lineaire code gevormd door een klasse polynomen C(G(X)), veelvouden van een polynoom G(X), een genererende polynoom genoemd, wordt een polynoom genoemd.

Laten we laten zien hoe polynomiale codes gerelateerd zijn C(G(X)) en cyclische codes. Laten A = A 0 …een-1 is een codewoord en het bijbehorende codepolynoom A(X) = A 0 +...+een -1 x n-1. Cyclische verschuiving A" komt overeen met de codepolynoom A"(X) = een -1 +A 0 X+…+een -2 X n -1 , wat kan worden uitgedrukt in termen van het origineel:

Omdat een polynoomcode deelbaar moet zijn door G(X), en vervolgens, om het cyclisch te maken, de polynoom A"(X) moet deelbaar zijn door G(X). Vanuit deze overweging kunnen we de volgende stelling formuleren. Een polynoomcode is cyclisch als en slechts als de polynoom G(X) is een deler van de polynoom x n–1. In dit geval de polynoom G(X) wordt de genererende polynoom van de cyclische code genoemd.

In de codeertheorie wordt de volgende stelling bewezen: als een polynoom G(X) heeft een diploma N–k en is een deler x n–1 dan C(G(X)) is lineair cyclisch ( N, k)-code.

Polynoom x n–1 ontbinden in factoren x n–1 = (X–1)(x n -1 +x n-1 +…+1). Daarom bestaan ​​er voor iedereen cyclische codes N. Aantal cyclisch N-bitcodes gelijk aan het aantal delers van de polynoom x n–1. Er zijn polynoomuitbreidingstabellen ontwikkeld om cyclische codes te construeren x n–1 in onherleidbare polynomen, dat wil zeggen in polynomen die alleen deelbaar zijn door eenheid en door zichzelf.

Laten we bijvoorbeeld eens kijken welke codes kunnen worden gebouwd op basis van de polynoom X 7 –1 over het veld GF(2). De uitbreiding van het polynoom naar onherleidbare factoren heeft de vorm

Omdat het mogelijk is om zes delers van een polynoom te vormen X 7–1, waarbij onherleidbare delers worden gecombineerd, zijn er zes binaire cyclische codes. ( N, k)-code wordt in de eerste plaats bepaald door de waarde N en ten tweede de waarde k = N – S, S– graad van delerpolynoom x n–1, die de code definieert. Hieronder staan ​​de polynomiale delers en de bijbehorende waarden k:

X – 1, S=1, k=6;

X 3 +x 2 +1, S=3, k=4;

X 3 +x+1, S=3, k=4;

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

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

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

De (7, 6)-code heeft slechts één controlesymbool en de (7, 1)-code heeft slechts één informatiesymbool. Het zijn respectievelijk een pariteitscontrolecode en een herhalingscode.

Net als een reguliere lineaire code kan een cyclische code worden gespecificeerd door een generatormatrix. Daarom is het de taak om zo'n matrix te vinden, dat wil zeggen om te vinden k lineair onafhankelijke codecombinaties die het vormen. Voor dit doel gebruiken we de eigenschap dat de cyclische code gesloten is met betrekking tot de cyclische verschuivingsoperatie. Merk op dat een cyclische verschuiving naar rechts met één plaats gelijk staat aan het vermenigvuldigen van de polynoom G(X) op X. Vervolgens kan de genererende matrix worden geconstrueerd door de genererende polynoom en te nemen k zijn cyclische verschuivingen:

Laten we nu eens kijken hoe, met behulp van de genererende polynoom G(X) = 1+X+X 3-codering wordt uitgevoerd met een (7, 4)-code. Neem bijvoorbeeld een woord van 4 bits (0101), dat overeenkomt met een polynoom F(X) = X + X 3. Vermenigvuldig deze twee polynomen.

Overeenkomend met dit woord, van een formele variabele X. Het is duidelijk dat deze correspondentie niet alleen één-op-één is, maar ook isomorf. Omdat “woorden” bestaan ​​uit letters uit het veld, kunnen ze worden opgeteld en vermenigvuldigd (element voor element), en het resultaat zal in hetzelfde veld liggen. Een polynoom dat overeenkomt met een lineaire combinatie van een paar woorden en gelijk is aan een lineaire combinatie van polynomen van deze woorden

Hierdoor kunnen we de reeks woorden met lengte n over een eindig veld beschouwen als een lineaire ruimte van polynomen met een graad van maximaal n-1 over het veld

Algebraïsche beschrijving

Als een codewoord wordt verkregen door het cyclisch één bit naar rechts te verschuiven ten opzichte van het woord, dan is de overeenkomstige polynoom C 1 (X) wordt verkregen uit de vorige door te vermenigvuldigen met x:

Profiteren van het feit dat

Verschuif respectievelijk naar rechts en links J gelederen:

Als M(X) - een willekeurige polynoom over een veld GF(Q) En C(X) - codewoord van cyclisch ( N,k) code dan M(X)C(X)MOD(X N − 1) ook het codewoord voor deze code.

Polynoom genereren

Definitie De genererende polynoom van de cyclische ( N,k) code C zo'n niet-nul polynoom wordt genoemd van C, waarvan de graad de kleinste is en de coëfficiënt van de hoogste graad G R = 1 .

Stelling 1

Als C- cyclisch ( N,k) coderen en G(X) is de genererende polynoom, en vervolgens de graad G(X) gelijk is aan R = N − k en elk codewoord kan op unieke wijze in de vorm worden weergegeven

C(X) = M(X)G(X) ,

waar is de graad M(X) kleiner dan of gelijk aan k − 1 .

Stelling 2

G(X) - genereren van polynoom van cyclisch ( N,k)-code is een deler van de binominale waarde X N − 1

Gevolgen: dus elke polynoom, deler, kan worden gekozen als een genererende polynoom X N− 1 . De graad van de gekozen polynoom bepaalt het aantal testsymbolen R, aantal informatiesymbolen k = N − R .

Generatormatrix

Anders zijn de polynomen lineair onafhankelijk M(X)G(X) = 0 voor niet-nul M(X) wat onmogelijk is.

Dit betekent dat codewoorden, net als bij lineaire codes, als volgt kunnen worden geschreven:

, Waar G is matrix genereren, M(X) - informatief polynoom.

Matrix G kan in symbolische vorm worden geschreven:

Controleer matrix

Voor elk codewoord van een cyclische code geldt . Dat is waarom controlematrix kan worden geschreven als:

Codering

Niet-systematisch

Bij niet-systematische codering wordt het codewoord verkregen in de vorm van het product van een informatiepolynoom door een genererende polynoom

C(X) = M(X)G(X) .

Het kan worden geïmplementeerd met behulp van polynomiale vermenigvuldigers.

Systematisch

Bij systematische codering wordt het codewoord gevormd in de vorm van een informatiedeelblok en een verificatie

Laat het informatiewoord dan hogere machten van het codewoord vormen

C(X) = X R M(X) + S(X),R = N − k

Dan volgt uit de voorwaarde

Deze vergelijking bepaalt de regel voor systematische codering. Het kan worden geïmplementeerd met behulp van lineaire filters met meerdere cycli (MLF's)

Voorbeelden

Binaire (7,4,3) code

Als verdeler X 7 − 1 kiezen we een genererende polynoom van de derde graad G(X) = X 3 + X + 1 , dan heeft de resulterende code de lengte N= 7, aantal testsymbolen (mate van genererende polynoom) R= 3, aantal informatiesymbolen k= 4, minimale afstand D = 3 .

Generatormatrix code:

,

waarbij de eerste regel de polynoomnotatie is G(X) coëfficiënten in oplopende volgorde. De overige lijnen zijn cyclische verschuivingen van de eerste lijn.

Controlematrix:

,

waarbij de i-de kolom, beginnend bij 0, de rest van de deling vertegenwoordigt X i tot een polynoom G(X) geschreven in oplopende volgorde, beginnend vanaf de bovenkant.

Zo wordt bijvoorbeeld de derde kolom verkregen, of in vectornotatie.

Het is gemakkelijk om dat te verifiëren GH T = 0 .

Binaire (15,7,5) BCH-code

Als een genererende polynoom G(X) kun je het product van twee delers kiezen 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 .

Vervolgens kan elk codewoord worden verkregen met behulp van het product van de informatiepolynoom M(X) met diploma k− 1 dus:

C(X) = M(X)G(X) .

Het informatiewoord komt bijvoorbeeld overeen met de polynoom M(X) = X 6 + X 5 + X 4 + 1 en vervolgens het codewoord 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 , of in vectorvorm

Zie ook

Koppelingen

Wikimedia Stichting.

• 2010.
• Cyclische vormen in muziek

Cyclische randvoorwaarden

Kijk wat "cyclische codes" zijn in andere woordenboeken: verkorte cyclische codes

- - [L.G. Sumenko. Engels-Russisch woordenboek over informatietechnologie. M.: Staatsbedrijf TsNIIS, 2003.] Onderwerpen informatietechnologie in het algemeen EN verkorte cyclische codes ... Reed-Solomon-codes

- niet-binaire cyclische codes waarmee u fouten in datablokken kunt corrigeren. De elementen van de codevector zijn geen bits, maar groepen bits (blokken). Reed Solomon-codes die werken met bytes (octetten) zijn heel gebruikelijk. De code van Reed Solomon is... Wikipedia Golay-codes - Een familie van perfecte lineaire blokcodes met foutcorrectie. Het nuttigst is de binaire code Golay. De ternaire Golay-code is ook bekend. Golay-codes kunnen worden beschouwd als cyclische codes. … …

Handleiding voor technische vertalers

Fout bij het corrigeren van codes Foutcorrectiecodes

- Detectie van fouten in de communicatietechnologie, een actie gericht op het bewaken van de integriteit van gegevens bij het opnemen/reproduceren van informatie of bij het verzenden ervan via communicatielijnen. Foutcorrectie (foutcorrectie) procedure voor het herstellen van informatie na... ... Wikipedia Foutcorrectiecodes