Diszkrét matematika algoritmusok
Közös információt az építési ciklikus kódok
A széles körben elterjedt gyakorlat volt az osztály a lineáris kódok, amelyek az úgynevezett ciklikus. Ez a név származik alapvető tulajdonságait ezeket a kódokat, nevezetesen, ha egy bizonyos kódszó tartozik egy ciklikus kód, a kombináció kapott ciklikus permutáció az eredeti kombináció (ciklikus eltolás), szintén tartozik ezt a kódot:
A második tulajdonság minden megengedett ciklikus kód kombinációk az oszthatóság nyom nélkül a kiválasztott polinom, az úgynevezett generálnak.
Ezeket a tulajdonságokat kialakításához használt kód kódolási és dekódolási berendezések, valamint az érzékelés és a hibák kijavítását.
Ciklikus kódok - ez egy egész család hibajavító kódok, amely magában foglalja az egyik fajta Hamming kódok, de általában nagyobb rugalmasságot biztosít szempontjából a megvalósíthatóságát a kódot a szükséges kapacitás felismerni és kijavítani a hibákat, hogy az adatátvitel során történt kódszó egy kommunikációs csatornán keresztül. Ciklikus kódnak szisztematikus blokk (n k.) -codes, ahol k első biteket kombinációja az elsődleges kódot, és az azt követő (n - k) bit egy paritás.
Az alapja az építési ciklikus kódok egy osztás az átküldött kódszó generáló irreducibilis polinom foka r. A maradék a szétválás használják a formáció a paritás bit. Ebben osztási művelet előzi szorzás művelet végez egy bal Shift + K bit tájékoztató kódszót r bit.
Amikor dekódoljuk a kapott n-bites kódszó ismét elosztjuk a generátor polinom.
hiba szindróma jelenlétében ezek a kódok a fennmaradó elosztjuk a vett kódszó generál polinom. Ha a szindróma nulla, úgy tekintjük, hogy nincsenek hibák. Ellenkező esetben, a kapott szindróma számának meghatározására kisülési vett kódszó, amelyben a hiba történt, és korrigálja.
Ugyanakkor nem kizárt, hogy többféle kódszavak hiba, ami okozhat hamis korrekciókat és / vagy érzékelési hibák átalakítja egy engedélyezett kombinációi a másikra.
Legyen a teljes bitek száma a blokkban egyenlő n. beleértve hasznos információkat hordozzák m bitre, akkor meghibásodás esetén lehetőség van arra, hogy rögzítse a s bit. Dependencia s megtalálható [6] n és m a kódok a táblázatban:
n. A bitek száma
m. A számos hasznos bit
s. száma helyesbített bitek
Bevezetés kódszó polinom formájában
Leírás ciklikus kódok és megépítésük hajtjuk végre egy polinom (vagy polinomok). Rögzítése kombinációja egy többtagú megjelenítéséhez szükséges egy formális módon ciklikus eltolási művelet az eredeti kódszó. Így, n -element kódszó leírható a polinom (n - 1) milyen mértékben alkotnak:
A n -1 (x) = n -1 x n -1 + n -2 x n -2 + ... + a 1 x + 0.
ahol az a i =, és i = 0 megfelelnek a nulla elemei a kombináció, a i = 1 - nulla.
Írunk polinomok speciális 4-elem-kombinációk:
1101 ↔ A 1 (x) = x 3 + x 2 + 1
1010 ↔ A 2 (X) = x 3 + x
összeadás és kivonás műveletek végrehajtása modulo 2 Ezek egyenértékű és asszociatív:
A működés a hagyományos Division részlege polinomok, hanem használja a kivonás modulo 2 összeadással:
A ciklikus eltolás kódszó
Ciklikus eltolás kód minta - a mozgó jobbról balra elemében zavarása nélkül azok sorrendjét, hogy a bal oldali elem helyét veszi át a szélsőjobb.
Az alapvető tulajdonságok és a neve ciklikus kódok kapcsolódó tény, hogy minden megengedett kombinációi bitek a továbbított üzenetet (kódszót) lehet előállítani egy ciklikus eltolás művelet megkezdése kódszót.
Tegyük fel, hogy adott kezdeti kódszó és a megfelelő polinom:
a (X) = a n x n -1 + n -1 x n -2 + ... + a 2 x + 1
Megszorozzák a (x) x:
a (X) = a · x n x n + n -1 x n -1 + ... + a 2 x 2 + 1 x
Mivel a legnagyobb mértékben az x kódszó hossza n nem nagyobb, mint (n - 1), meg kell kivonni a n (x n - 1), a jobb oldalon a kapott expressziós az eredeti polinom. Kivonás egy n (x n - 1) a maradék modulo (x n - 1).
A váltás az eredeti kombináció, hogy i ciklusok lehet az alábbi képlettel ábrázolható: a (x) · x i - n (x n - 1), azaz megszorozzuk a (x) az x i, és a maradék modulo (x n - 1). Figyelembe egyensúly szükséges megszerzése a polinom foka nagyobb vagy egyenlő n-nel.
generáló polinom
Az ötlet az építési ciklikus kódok használatán alapuló redukálható polinomok. Ez az úgynevezett irreducibilis polinom, hogy nem lehet képviseli, mint a termék polinomok az alacsonyabb fokú, m. E. polinom osztható csak önmagában, vagy egy egységet nem osztható más polinom. Egy polinom osztható binomiális x n + 1 A irreducibilis polinomok az elmélet a ciklikus kódok hatnak generátorok polinomok.
Visszatérve a meghatározásnak ciklikus kód, és a felvételi műveletet a ciklikus eltolási kódot kombinációk, lehetőség van, hogy rögzítse egy ciklikus kód generátor mátrix, az alábbiak szerint:
p (x)
p (x) · x - C 2 (x n - 1)
p (x) · x 2 - C 3 (x n - 1)
...
p (x) · x m -1 - C m (x n - 1)
ahol p (x) - a kezdeti kódszót, amely alapján a kapott összes fennmaradó (m - 1) alap kombinációja, C i = 0 vagy C i = 1 ( "0", ha a kapott polinom foka p (x) · xi nem haladhatja meg a (n - 1), "1", ha nagyobb, mint).
A kombináció a p (x) nevezzük generáló (generátor, generátor) kombinációja. Igaz elég az építkezés egy ciklikus kód kiválasztásához p (x). Ezután az összes többi kódszavak kapott az ugyanaz, mint a kódját.
Generálása polinom kell felelniük az alábbi követelményeknek:
- p (x) kell lennie nem nulla;
- súlya p (x) nem lehet kevesebb, mint a minimális távolság: v (p (x)) ≥ d perc;
- p (x) kell egy maximális mértékű K (k - száma redundáns elemet a kód);
- p (x) kell lennie egy osztója a polinom (x n - 1).
Üzemi körülmények 4 vezet az a tény, hogy az összes működő kód ciklikus kód kombinációk tulajdonszerzési oszthatóság p (x) maradék nélkül. Ezt szem előtt tartva, tudunk adni egy másik meghatározása egy ciklikus kód. Ciklikus kód - kód minden dolgozó kombinációk, amelyek megoszlanak a generátor által nyom nélkül.
Mértékének meghatározására a generáló polinom használhatja a kifejezést R ≥ log2 (n + 1), ahol n - a méret a átvitt csomag egy időben, azaz egy ciklikus kód hossza alatt ...
Példák a generáló polinomok megtalálható [5] a táblázatban:
r. A polinom fokának
P (x), a generátor polinom
111100111, 100011101, 101100011
Algoritmus a megengedett kódszó ciklikus kód kombinációja egy egyszerű kódot
Legyen egy polinom P (x) = egy R X R -1 + r -2 x r -1 + ... + 1, meghatározza a hibajavító képességét a kódot, és r a számát ellenőrző bitek. és kezdeti kombinációs egyszerű k -element kódot formájában polinom A k -1 (x).
Ez szükséges, hogy meghatározzuk a megengedett kódot kombinációja egy ciklikus kód, (n. K).
- Szorozzuk az eredeti kódszó polinom x r.
A k -1 (x) · x r
A k -1 (x) · X R / P r (x) → R (x)
A n -1 (x) = A k -1 (x) · x R + R (x)
Felmerülő hibák a vett kódszó elég osszuk generáló polinom. Ha elfogadott kombinációja - engedélyezett, a fennmaradó részlege nulla lesz. Egy nem-zéró fennmaradó azt jelzi, hogy a kapott kombináció hibákat tartalmaz. Az egyensúly az elme (szindróma), bizonyos esetekben még a következtetést a hiba természetét, annak helyét és megoldja a problémát.
Példa. Legyen ez lehet kódolásához szükséges szekvenciájának típusú 1101, amely megfelel a (x) = x 3 + x 2 + 1.
Határozza meg a számos kísérleti szimbólumok r = 3. A táblázatból veszi a polinom P (x) = x 3 + x + 1, t. E. 1011.
Megszorozzák a (x) X R.
A (x) · x r = (x 3 + x 2 + 1) · x 3 = x 6 + x 5 + x 3 → 11.010.000
Felosztása a kapott terméket a generátor polinom g (x):
A (x) · XR / P (x) = (x 6 + x 5 + x 3) / (x 3 + x + 1) = x 3 + x 2 + x + 1 + 1 / (x 3 + x + 1) → 1111 + 001/1011
Ha elosztjuk, vegye figyelembe, hogy a kivonás készül modulo 2 összege legfeljebb a mérleg h (x) · x r. Az eredmény egy kódolt üzenetet:
F (x) = (x 3 + x 2 + 1) · (x 3 + x + 1) = (x 3 + x 2 + 1) · x 3 + 1 → 1.101.001
A kapott kódszó ciklikus kód információ szimbólumok A (x) = 1101 és ellenőrzési R (x) = 001. A kódolt üzenetet elosztjuk a generátor polinom maradék nélkül.
Hiba algoritmus
Tegyük fel, hogy n -element kombinációja (n = k + r), akkor:
- Egy maradék elosztjuk E (x), amely megfelel a magas bithiba [1000000000], a generátor polinom P r (x):
- Ha ezek egyenlőek, akkor egy hiba történt a legjelentősebb számjegyet.
- Ha nem, akkor ez fokozza a elfogadásának polinom x, majd hajtsa végre osztály:
H (x) · x / P r (x) = R (x)
- Ha ezek egyenlőek, akkor a hiba a második kategóriába tartozik.
- Ha nem, akkor szorozzuk h (x) · x 2 és megismételni ezeket a műveleteket addig, amíg az R (x) nem egyenlő R 0 (X).
A hiba lesz egy olyan kisülési megfelelő számát, amelyre a nagyobb fokú h (x), plusz egy.
Például: H (x) · x 3 / P r (x) = R 0 (X)
Francia tudós A. Hokvingem (1959) és az amerikaiak R. K. Bouz és a DK Roy-Chowdhury (1960) talált egy nagy kategóriába tartozó kód, amely egy tetszőleges minimális távolság d min ≥ 5. Ezek az úgynevezett BCH ( Bose-Chaudhuri-Hocquenghem). Generátor polinomok az ilyen kódokat, attól függően, hogy a követelmények, megtalálható [7] az alábbi táblázatban:
Ahol n - az összes elemet, m - a több információs elemek, k - száma redundáns elemek (n = m + K).
Eljárás építési a BCH kódot az adott M és D min.
- talált d perc érték, amelynél amennyiben az szükséges számú információs elemek m minimális redundancia k perc;
- táblázatban találhatók megfelel egy generátor polinommal;
- Ha D min még, többszörösen polinom található (x + 1);
- ha m >> táblázat m van megadva. lehetőség van arra, hogy mozog, hogy egy rövidített ciklikus kódot, feltűnő a generáló forráskód mátrix m táblázat paraméterei. k min (m táblázat - m set) oszlopok a bal oldalon, és az azonos számú fenti sorokban.
vizualizációja
Részletek megjelenítő egyik módszer megépítésének ciklikus kódot.
Forrás megtekintése
Az [1], [2] és a [3] és [4] bemutatja az elméleti részleteit, konstrukciós módszerek, valamint példák a ciklikus kódok.
A Web oldalak, [5], [6], [7], elsősorban a gyakorlati vizsgálatok, néhány közülük, attól függően, hogy érdeklődést és ciklikus kódok táblázata.
irodalom
Van egy pár jegyzetek a hibákat.
>>> táblázat BCH venni a honlapon fent.
25 31 11 5 11 5423325 101100010011011010101
valószínű, hogy az hibát tartalmaz egy első számú - 25 helyett kell 20 (definíció szerint, k = kolichestvo_bit_v_polinome - 1, és továbbá meg kell felelniük a feltételt k + m = n).