Lineáris kódok
Diákok, végzős hallgatók, fiatal tudósok, akik a tudásbázisot tanulmányaik és munkájuk során használják, nagyon hálásak lesznek Önöknek.
Definíció 1. Rendszeres kódok azok, amelyekben az információs és vezérlő szimbólumok szigorúan meghatározott helyeket foglalnak el a kódkombinációkban.
Definíció 2. Lineáris kódok azok, amelyekben az ellenőrző szimbólumok az információs szimbólumok lineáris kombinációi:
A lineáris bináris kódok egy algebrai csoportot alkotnak a modulo 2 addíciós művelethez képest, mivel a lineáris kód kódszavainak összege megadja az adott kódhoz tartozó kódszót. Ez a tulajdonság lehetővé teszi a lineáris kód összes megengedett kombinációjának megalkotását, amelyek csak korlátozott számban vannak.
Definíció 3. A kódszó súlya nem nulla elemek száma.
Vegye figyelembe a csoportkódok fontos tulajdonságait: a csoportkód kódszavainak minimális kódszáma megegyezik a nem nulla kódszavak minimális súlyával.
Egy lineáris kód létrehozása az úgynevezett generátor (generáló, generáló) mátrix segítségével történik.
Generátor mátrix létrehozásakor a következő szabályokat kell követni:
1) a kezdeti kódszavak száma megegyezik az információs szimbólumok számával;
2) minden kezdeti kódszónak különböznie kell;
3) a kezdeti kódszavak között nem lehet nulla;
4) minden kezdeti kódszónak lineárisan függetlennek kell lennie;
5) az egyes kezdeti kódkombinációkban lévő egységek száma nem lehet kevesebb;
6) a kezdeti kódszavak bármely párjának kódszáma nem lehet kevesebb.
A szabályoknak megfelelően kiválasztott kezdeti kódszavak generátor mátrix formájában vannak írva. sorokat és oszlopokat tartalmaz:
Az adott mátrix által generált kódot a -code hívja.
Bármely generáló mátrix az úgynevezett bal kanonikus vagy csökkentett lépésformára redukálható
hol van a megrendelési egység almatrixa. - Sorok és oszlopokat tartalmazó ellenőrző almatrix.
A generáló mátrix kanonikus formáját úgy kaphatjuk meg, hogy kiindulási kódszósznak vesszük azokat a szavakat, amelyek az információrészben egy egységet tartalmaznak. Ebben az esetben az ellenőrző almatrix sorainak a -bit kombinációknak kell lenniük a nem kevesebb mint. Hammam kód lineáris dekódolás
A kódoló eljárás a generáló mátrix segítségével a következő: az első kombináció nulla, a generáló mátrix sorai a kívánt kód kombinációi, a fennmaradó kombinációk a generáló mátrix összes sorának összesítésével összegezhetők.
1. példa Egy generátor mátrix használatával hozzon létre egy szisztematikus lineáris kódot, amely képes egyetlen hibát kijavítani a 16 üzenet továbbítása során.
A megoldás. Ez ismeretes. Ezért és.
Táblázat szerint. határozza meg az ellenőrző karakterek számát.
A vizsgálati almatrix felépítésének szabálya szerint a sorban lévő egységek száma nem lehet kevesebb. A háromelemes kombinációk közül csak azokat válasszák, amelyekben az egységek száma nagyobb vagy egyenlő: 110, 101, 011, 111.
Megalkotjuk a generáló mátrixot
Az ellenőrző mátrixban lévő sorok egymás között váltakozhatnak. Ebben az esetben több változatot kapunk a mátrixok generálására, következésképpen a lineáris kódok több változatára a vizsgált példában.
Az ismert információrészből származó vezérlő karakterek előállítására szolgáló algoritmus a következőképpen írható le:
A vezérlő szimbólum az információs szimbólumok összege, amely megfelel a vizsgálati almatrix első oszlopának egységeinek. a második vezérlő szimbólum a vizsgálati almatrix második oszlopának megfelelő egységek szimbólumainak összege, és így tovább.
Példa 2. Kódjon egy lineáris kódban egy négyjegyű bináris kód 1100 (.
A megoldás. Az információs szimbólumok száma. A táblázatból. 3.1.
A 3. példa szerinti mátrix (3) generáló mátrixként szolgálhat, majd (4)
Tehát a kód teljes kombinációja: 1100110.
Megjegyzés. Legyen - információs szimbólumok, akkor a lineáris kód kódszava megtalálható a képletben
Az 1100 kombinációt az (5) képlet szerint kódoljuk:
A hibajavítást az ellenőrzéssel végezzük
Az ellenőrzések száma megegyezik a korrekciós kód ellenőrzési szimbólumainak számával.
Az ellenőrzések eredményeképpen szimbólumok kombinációja alakul ki. szindrómának nevezik. Ha a szindróma súlya nulla, akkor az elfogadott kombináció hibamentesnek tekinthető, különben az elfogadott kombináció hibát tartalmaz.
A hibák javítását a szindróma típusának megfelelően, kontrollmátrix segítségével végezzük. amely két almatrixból áll: és az n-edik sorrend egyik alegységén:
Az ilyen mátrix oszlopai a mátrix oszlopszámának megfelelő mentesítéshez tartozó szindróma értékét reprezentálják.
3. példa Mutassa be a 3.3 példában felépített korrekciós kód kódkombinációjának tetszőleges bitjében lévő hiba rögzítésének folyamatát.
A megoldás. Az ellenőrzési rendszer (6) megépítésének elve szerint a létrehozott kód ellenőrzési rendszere lesz
Az ellenőrző mátrixot építjük:
Ha a szindróma bitjei megfelelnek a mátrix első oszlopának. azaz akkor a hiba a kapott kombináció első számjegye, ha a szindróma formája van. amely megfelel a mátrix második oszlopának. akkor a hiba a második számjegy, és a 001-es szindróma a kódkombináció harmadik vezérlõjegyzõjében hibát jelez stb.
A kód javító tulajdonságainak ellenőrzéséhez használja a kombinációt a 7-es számon: 1010101.
Legyen egy hiba a negyedik számjegyen, azaz. a kombinációt a következő formában fogadják el: 1011101.
A 111 szindróma megegyezik a kontroll mátrix negyedik oszlopával, ezért a negyedik számjegyben a szimbólumot a fordítottra kell cserélni.
Megjegyzés. Legyen - a lineáris kód kódszava, akkor a szindróma a képletben található meg
Megtaláljuk az elfogadott kombináció szindrómáját a (3.8) képlet szerint:
Megjegyzés. A kódolás lehetséges a vezérlõmátrix segítségével: a vezérlõ szimbólum () egyenlõ az információs szimbólumok összegével, amely megfelel a mátrix második sorának egységeinek.
Hamming kód
A Hamming kód egyike a lineáris kódok fontos osztályainak. Gyakorlatilag széles körben alkalmazható, egyszerű és kényelmes egy technikai megvalósítási algoritmushoz egyetlen hiba észleléséhez és kijavításához ().
Hamming azt javasolta, hogy az ellenőrző mátrix oszlopait rendezzük úgy, hogy a mátrix th oszlopának száma és a kódkombin bitjének száma megegyezzen a szám bináris ábrázolásával. Ezután a kísérleti egyenletek segítségével talált szindróma a kódkombináció azon számjegyének bináris ábrázolása lesz, amelyben a hiba történt. Ehhez az ellenőrző szimbólumoknak nem a kódkombináció végén, hanem a törvény szerint választott pozíciók számán kell lenniük. azaz az 1., 2., 4., 8., ... számra. Így a Hamming kód ellenőrző mátrixának jellemző jellemzője, hogy oszlopai a hosszúság bináris kódjában lévő kódszavak.
4. példa. Hozzon létre egy Hamming kódot egy négybit bináris kód egyikének kombinációjához.
A megoldás. Mert. jelent.
A négy információs szimbólum eredeti kombinációja formát ölt. hol vannak ellenőrzési szimbólumok; - információs szimbólumok.
Megalakítjuk az ellenőrző mátrixot. oszlopai a kódjegy szimbólumainak száma a háromjegyű bináris kódban.
Megjegyzés. A decimális számot a formában lehet megjeleníteni
ahol két értéket vehet fel: 0 vagy 1.
Ezután egy számjegyes bináris ábrázolás.
Például. ezért 001 egy három számjegyű bináris ábrázolás, 1; 6 110, mivel. majd
Az egy egységgel ellátott oszlopok átrendezése után az ellenőrző mátrix formában lesz
A vezérlő szimbólumokat a képletek határozzák meg
Az ellenőrzési rendszer formája
Megjegyzés. Amikor egy kommunikációs csatornán keresztül továbbítódik, két vagy több hiba léphet fel a kódszóban. Ebben az esetben a szindróma bármilyen értéket vehet fel, beleértve a nullát is. Ez javítja a véletlen karaktert. Az ilyen automatikus korrekció kizárásához további karaktert ad meg, hogy ellenőrizze a teljes kombinációt a paritáshoz. A kód távolsága nő.
5. példa Kód az 1101 Hamming kódkombinációban.
A megoldás. A feltétellel. ezért. A vezérlő karakterek lesznek. Információs szimbólumok.
A vezérlő szimbólumok megkereséséhez az előző példából származó kontrollmátrixot (3.9.) Használjuk.
A rendszerből (10)
A kódszó 1010101-nek fog kinézni.
Tegyük fel, hogy hiba történt az átvitel során, és hibás kombinációt vettünk: 101011 1 (hiba történt a hatodik számjegyen).
Az ellenőrzési rendszer (3.11) segítségével megtaláljuk a szindróma kategóriáinak értékeit:
A szindróma azt jelzi, hogy a kapott kombináció hatodik számjegye hibás volt ().
Ha kettős hibát kell ellenőrizni, akkor egy további nulla bitet kell bevezetnünk:
Szerezze be a 01010101 kódot.
Hagyja, hogy a kód 0101011 1 legyen, amikor a hiba átkerül és a hiba bekövetkezik.
Az ellenőrzés ebben az esetben azt mutatja, hogy a szindróma 110, és a teljes kombináció ellenőrzése egyenlőség = 0 + 1 + 0 + 1 + 0 + 1 + 1 + 1 = 1. Ez egyetlen hibát jelez. Automatikus hibajavítás engedélyezett.
A Hamming kód kódolásával történő dekódolásához a következő algoritmus található (3.2. Táblázat).
3.2. Táblázat.
A fuzzy kereséshez jól ismert algoritmusok és Hamming kódok használhatók. A Hamming kódok hosszú és sikeresen használták a kódoláshoz és dekódoláshoz, lehetővé téve az elveszett információk helyreállítását.
Hemming hálózatokat is aktívan használnak az optikai karakterfelismerés (OCR) számára.
Azonban a Hamming algoritmusok nem csak az információs kódolás elméletében, hanem az információ visszakeresésében is alkalmazhatók. Különösen a Hamming kódok működnek együtt a fuzzy logikai eszközzel.
A Hamming kódok a legegyszerűbb lineáris kódok, amelyek minimális távolsága 3, vagyis egy hiba kijavítására alkalmas [2].
A Hamming hálózatok egyike a neurális hálózatoknak. A Hamming hálózatok működésének elve azon alapul, hogy meghatározzák Hamming távolságát a tárgyak között, és megtalálják a legközelebb.
A Hamming algoritmusok a munkájukban lineáris kódot használnak, ami a többi kóddal összehasonlítva hatékonyabb algoritmust valósít meg az adatok kódolásához és dekódolásához.
Az információkeresés és -kibocsátás folyamatában elkerülhetetlenül hibák jelentkeznek, ezért az adatintegritás-ellenőrzés és a hibajavítás fontos feladatok az információkezelés számos szintjén.
A tényleges feladat egy olyan fuzzy keresőrendszer kifejlesztése, amely egy szót talál a listán, még akkor is, ha torz, vagy hibás és hiányzó karaktereket tartalmaz.
A Hamming hálózatokban fellépő hibák észleléséhez hibaérzékelési kódokat használnak, és korrekciós kódokat használnak ki azok kijavítására.
Ehhez az adatoknak a hasznos adatokhoz való írásakor és átvitelénél strukturált redundáns információ kerül hozzáadásra speciális módon, és az olvasás (fogadás) során a hibák észlelésére vagy javítására szolgál. Természetesen a rögzíthető hibák száma korlátozott, és az adott kódtól függ.
Így a Hamming algoritmusok olyan szavak keresésére használhatók, amelyeket az eredeti lekérdezés hibákat tartalmaz.
Tegyük fel, hogy van egy szótárunk a bemeneten, és meg kell találnunk a keresési szót ebben a szótárban, még akkor is, ha hiba történt. Ehhez először át kell gondolkodnunk, és ki kell alakítanunk egy rendszert a szimbolikus információk vektorokkódolásához. Minden egyes karakterhez beállítjuk a bitmaszkot:
A szimbóluminformációk kódolásakor meg kell fontolni a forrás beszerzését. Ha például a billentyűzet segítségével írunk be karaktereket, célszerű a karakterkódokat oly módon beállítani, hogy a billentyűzet melletti szimbólumok kódjai közel legyenek a Hamminghez. Ha a forrás egy képfelismerő program (OCR), akkor hasonló kódoknak hasonlónak kell lenniük a helyesírási karakterekben. A kódolás után tehát a kapott vektorokat a neurális hálózat bemenetére szállítjuk.
Mindazonáltal figyelembe kell venni a Hamming hálózatok egyik jellemzőjét. Ha írási hiba vagy akár kettő is van, akkor az algoritmus jól működik, de ha a szimbólum elmarad, vagy az extra hozzá van adva, akkor a Heming távolság túl nagy lehet. Annak érdekében, hogy megszüntessük ezt a hiányosságot, beadjuk a bemenetet, mind a keresett szót, mind az azonos szót, kivéve minden egyes pozícióban egyenként, és minden pozícióhoz egy levelet adunk. Az ilyen megközelítés gyakorlatilag minden hibahelyet megtalál: egy hibás, egy hiányzó karaktert, egy extra szimbólumot.
Meg kell jegyezni, hogy a Hamming kódok nagy hatékonysága ellenére nincsenek bizonyos hátrányai. A lineáris kódok általában szabályosak lehetnek ritka és nagy hibákkal és hibás nyomatokkal [4]. Viszont a viszonylag gyakori, de kisebb hibák hatékonysága kevésbé magas.
A kódszavak elmentésének vagy számozásának linearitása következtében elegendő a kódoló vagy a dekóder memóriájában tárolni lényegében kisebb részt, nevezetesen csak azokat a szavakat, amelyek a megfelelő lineáris tér alapját képezik. Ez nagymértékben leegyszerűsíti a kódolási és dekódoló eszközök végrehajtását, és a gyakorlati információ-visszakeresési feladatok szemszögéből vonalkódokat vonz.
Hosted on Allbest.ru