A matematikában , pontosabban a kódelméletben , a lineáris kód egy korrekciós kód , amelynek bizonyos linearitási tulajdonsága van.
Pontosabban, egy ilyen kód egy véges dimenziós vektortér vektortérként van felépítve egy véges mező fölött . Az alkalmazott véges vektortér gyakran F 2 n, a szokásos kifejezés ekkor a bináris lineáris kódé . Három paraméter írja le [ n , k , δ]. n leírja az azt tartalmazó tér dimenzióját. Ezt a mennyiséget nevezzük a kód hosszát . k a kód dimenzióját jelenti, amely megfelel az egyszer dekódolt szavak méretének , és δ leírja a kód egyes szavai közötti minimális távolságot Hamming- értelemben .
A lineáris kódok jelentik az iparban használt korrekciós kódok nagy részét. Ez a megközelítés különösen az egyszerű detektálást javasló kódokra terjed ki, majd új továbbítást igényelnek. Más kódok lehetővé teszik a változtatások finom redundancia-kezeléssel történő kijavítását.
Emlékeztető: F 2 az egyedi test két elemmel, F 2 n pedig az n dimenzió vektortere . Ha az alapmező Fd , akkor a d elemet tartalmazó mező , a dedikált kifejezés a d alap lineáris kód . A véges mezők elmélete biztosítja, hogy d egy prímszám hatványa, és hogy létezik egy egyedi mező, amely rendelkezik ezzel a bíborossal.
A lineáris kód a korrekciós kód speciális esete . A cél lehetővé teszi a hibák kijavítását egy üzenet továbbítása után . Ez a javítás redundáns információk hozzáadásával lehetséges. Az üzenet nagyobb készletbe van ágyazva , a méretkülönbség redundanciát tartalmaz. Egyszerű példa, hogy az ismétlési kódra az üzenetet például háromszor küldik el, a dekódolást szavazással hajtják végre. Itt a nagyobb halmaz háromszoros dimenzióban van, mint az eredeti üzenet.
Idézzük fel a formalizálás alapvető elemeit. Létezik egy sor E alkotják szekvenciák hossza k , azaz, hogy az indítást rang k , mind az értékek a szekvencia nulla, és értéket egy ábécé. Ezek az elemek azok az üzenetek terét jelentik, amelyeket kommunikálni akarunk. Annak érdekében, hogy az üzenetet a kívánt redundancia, létezik egy injektív térkép φ az E értékek a F , a tér hosszúságú szekvenciák n értékekkel egy ábécé. A φ függvényt kódolásnak hívjuk , az φ ( E ) -t kódnak hívjuk, a kód φ ( E ) szavának elemét , n a kód hosszát és k a kód dimenzióját.
A matematikai eszközök hatékonyságának lehetővé tétele érdekében célszerű lehet algebrai struktúrákat használni . az E és F ábécét ugyanazon véges mezőnek választják . Az E (ill. F ) elemei a k (ill. N ) véges szekvenciái , E és F természetesen öröklik a véges dimenziójú és kanonikus alapú vektortér struktúráját, a tér struktúráját . Egy mezőn. A kódoló alkalmazást lineárisan választjuk .
A tér F van ellátva távolságban az úgynevezett Hamming-távolság eredő pszeudo-norma , a Hamming-súly . Az F pont Hamming-súlya p megegyezik a nullától eltérő koordinátáinak számával. Az F két eleme közötti Hamming távolság a különbségük Hamming értelmében vett súlya.
A lineáris kódok a korrekciós kódok típusainak nagy többségének felelnek meg. Ezeket a változások detektálására használják, társított korrekciós módszerként egy újraküldési kérelmet, ekkor a leggyakoribb technika az ellenőrző összeg . Számos helyzetben használják őket, néhány elszigetelt hibától kezdve a nagy változásokig vagy a törlési jelenségekig.
Bár az alkalmazott keretet széles körben használják, ennek ellenére nem felel meg az összes igénynek. Két fő témát idézhetünk, amelyeket a lineáris kódok elmélete kevéssé kezel. A jó kód megfelel az optimalitási kritériumnak, azt mondják, hogy tökéletes. A lineáris kódelmélet keretei kritériumokat kínálnak ennek az optimalitásnak a érvényesítésére. Azonban nem kínál módszert az ilyen típusú kódok tervezésére.
A hibajavításra rendelkezésre áll egy általános módszer, a szindróma dekódolása . Ez a módszer abból áll, hogy létrehoz egy táblázatot, amely társítja az egyes hibákat, azok megoldását. A táblázat exponenciálisan növekszik a valószínűleg hibás betűk számával. Nagy korrekciós kapacitás esetén ez a megközelítés már nem működik.
A ciklikus kódok elmélete, a véges mezők tulajdonságainak széles körű felhasználásával, kielégíti ezt a két igényt. A ciklikus kód egy lineáris kód, amelynek további algebrai szerkezete van.
Itt F d az egyedi mezőt d elemekkel jelöli (vö. A cikk véges mezője ). Megjegyezzük, hogy az F d értékű szekvenciák vektorterét F d n azonosítja . Az F d n vektorteret felruházzák a Hamming-távolsággal .
Ami a többi korrekciós kódot illeti, a paraméterek fogalma érvényes. A vektortér szerkezetének figyelembevétele érdekében azonban egy kicsit módosul:
A lineáris kódok paramétereinek meghatározása ezért nem kompatibilis a korrekciós kódoknál használt általánosabbal. Emiatt hagyományosan egy lineáris kód paramétereit [ n , k , δ] és egy általános korrekciós kódot { n , M , δ} jelöljük .
Mint korábban, van egy kódoló alkalmazás : φ.
Monitoring ellenőrzés és esetleges korrekciók adott egy lineáris leképezés H a F d n az F d n-k , amelynek mag C . A lineáris algebra elmélete azt mutatja, hogy ilyen alkalmazás létezik, egyszerűen csak egy projektornak a C -vel párhuzamosan C- vel kiegészített altérre való tekintetével .
A paritásmátrix kifejezést használják a kontrollmátrix megjelölésére is .
Megjegyzés: Ezeket a jelöléseket a cikk többi részében használjuk.
A lineáris algebra összes tulajdonsága érvényes a lineáris kódokra. A kód így könnyebben megvalósítható és dekódolható is. Ezenkívül a vektortér-generáló eszközök, például a kettős tér vagy a tenzor szorzata lehetővé teszik új kódok tervezését, amelyek időnként jobban megfelelnek az ipari kényszereknek.
A kódoló alkalmazás lineáris, ezért generátormátrixának köszönhetően ábrázolva és kiszámítva . A kódot teljes egészében a kx n dimenziójú generátormátrixa határozza meg. Sőt, mivel kódjának tulajdonságai csak a the ( E ) geometriától függenek . Ha f egy izomorfizmus az E , a kód által meghatározott térkép φ az ugyanaz, mint a φ. Ez a következő meghatározást eredményezi:
A G mátrixnak van egy különösen egyszerű formája :
Az e bekezdéshez kapcsolódó cikk fontos tulajdonságot mutat be:
Ez az írás felgyorsítja és leegyszerűsíti a kódolást és a dekódolást. Ezután a mátrix a következő formát ölti:
A C mátrix koordinátái megfelelnek a redundanciának, céljuk az esetleges hibák felderítése és kijavítása:
Lineáris esetben a kód a k dimenzió vektoraltere . Ekkor létezik F szurjektív lineáris térképe az n - k dimenziós térben, amely a kernel számára pontosan a kódot tartalmazza:
Szisztematikus kód esetén a generátor mátrix kifejezése azonnal megadja a kontroll mátrixét.
Itt I k a k rendű azonossági négyzetmátrixot jelöli . Ez a mátrix viszonylag egyszerű módszert kínál a minimális távolság kiszámítására:
Lineáris kód esetén a Hamming-távolságot pszeudo-normából adódó távolságként fejezzük ki. A Hamming-súly , amely a nullától eltérő koordináták számát kóddal társítja, itt álnorma szerepet játszik.
Az alapstruktúra linearitása közvetlen tulajdonságot vezet be:
Ennek meggyőződéséhez elegendő észrevenni, hogy ha x és y a kód két szava, akkor a különbségük is a kód szava.
A kétségtelenül kijavítható hibák maximális száma t közvetlenül a minimális δ távolságból következik. Valójában t a legnagyobb egész szám, szigorúan kisebb, mint δ / 2. Az ideális helyzet az, amikor a bezárt golyók középpontjában a kód és a t sugár szavai alkotják az F partícióját . Ezután tökéletesről beszélünk .
Ha eléri a Singleton-kötést, akkor a kód MDS.
A kód lineáris felépítése természetesen felveti a kettős kód fogalmát. A szimmetrikus bilinear forma kanonikus, és beállítja a C kettős kódot .
Egy olyan szisztematikus kód esetében, amelyhez mindig lehetséges visszatérni, a C vezérlő mátrixa kettősének generátor mátrixává válik. Ezután elegendő az adatbázis átrendezése a szisztematikus kód megszerzéséhez. Hasonlóképpen, a C generátormátrix kettős hangvezérlő mátrix.
Ez lehet számítani a minimális távolságot ettől , de ez nem elegendő ahhoz, hogy tudja, hogy az : meg kell tudni, hogy a számlálóra polinomja súlyát . Ezután MacWilliams identitása megadja azt, amelyből egyszerűen kivonjuk az utóbbi minimális távolságát.
A lineáris algebra számos más, a kódnak megfelelő technikát kínál. A tenzortermék erre példa. Két vektortérrel egy harmadik izomorfot társít a második tér első vonalának lineáris térképeihez.
Minden olyan konfiguráció kijavítására szolgál, amely kevesebb, mint δ 0 .δ 1/4 hibával rendelkezik.
A legegyszerűbb hibakezelési technika az érvényesítésre korlátozódik. Ha az üzenet nem része a kódnak, akkor hamisnak nyilvánítja. Általában egy új továbbítási kérelem a korrekciós technika.
A leggyakrabban alkalmazott módszer abból áll, hogy az üzenethez hozzáadnak egy vagy több ellenőrző bitet, amely megfelel az üzenet együtthatóinak véges testében lévő összegnek. Ez a technika a kilenc bizonyításának analógja .
Még ha ez az ellenőrző bitek számának növelését is jelenti, ez a módszer növelheti a megbízhatóság szintjét. Ha a valószínűség elég nagy ahhoz, hogy feltételezzük, hogy egyetlen hiba csúszhat az üzenetbe, akkor egy ellenőrző bit teljesíti a feltételt.
Egyetlen vezérlőbit esetén a kódparaméterek [ n , n - 1, 2]. Egy ilyen kód önmagában nem tudja kijavítani a hibát. Valójában minden hibánál n- 1 pont van a kódtól, amelyek közel vannak. Az önkorrekcióhoz további információkra van szükség.
A megvalósítás egyszerű, az üzenet képének kiszámítása a vezérlő mátrix segítségével biztosítja az információt. Ha a kép nulla, akkor az üzenet kódnak felel meg, és hiba nélkül. Ellenkező esetben hibát jelentenek be.
A kérdéssel itt csak a szisztematikus kódok esetében foglalkozunk. Nemcsak a megoldást veszi figyelembe az ipar, hanem ezen felül bármilyen más konfiguráció is ekvivalens ezzel.
Kezdetben csak a nulla vektor problémáját lehet figyelembe venni. A kapott üzenetnek tehát k első 0 koordinátája és c vezérlőbitjei vannak, amelyek nem mind nulla. Ez a helyzet hibának felel meg, mert a generátor mátrix által a nulla vektor képe adja a nulla vektort, és ezért a vezérlő bitek nullaak egy olyan kódnál, amelynek első k nulla koordinátája van.
Az üzenetnek megfelelő korrekció m kisebb Hamming-súly és a kép a H ellenőrző mátrix alapján . c . Ha a szám a változásokat, amelyek generált a vektor (0, c ) kevesebb, mint (δ - 1) / 2, akkor létezik egy egyedi m olyan, hogy H . m = - H . c . Itt H . c visszaéléssel jelöli a H. (0, c ) vektort . A társított kód m - c , a kezdeti üzenet pedig m . Ellenőrizzük, hogy H. ( M - c ) = 0 és m - c kód. Ekkor lehetséges minden egyes H értékre . c , az m korrekció társításához .
Általános esetben, ha a fogadott üzenet nem része a kódnak, akkor annak képe az ellenőrző mátrix által egy H-nek megfelelő érték . c adott. Úgy tűnik, hogy m az a legkisebb korrekció, amelyet l- re kell alkalmazni egy kód megszerzéséhez. Valóban, H ( l + m ) egyenlő H-val . c - H . c és a minimum az előző bekezdés következménye.
Értékének meghatározása m a H . c nagyban függ a kód megválasztásától. Megfelel a lineáris optimalizálás által lefedett klasszikus problémának . A gyakorlatban ritkán alkalmaznak ilyen módszereket. Vagy a vezérlőbitek száma csökken, és a kombinatorika csökken, vagy a tér hatalmas, és a kódnak más tulajdonságai vannak, amelyek gyakran polinomok és a cikk ciklikus kódjában vannak leírva .
A megvalósítást - mivel a vezérlőbitek helye csökken - általában hash-tábla hajtja végre . Ez a táblázat megalapozza az egyes szindrómák és a minimális súlyú üzenet között a szindrómát képező képet a kontroll mátrix által.