Samoopravné kódy – Hammingovy kódy, cyklické kódy

Samoopravné kódy – Hammingovy kódy, cyklické kódy

Hammingův kód

Hammingovy kódy tvoří významnou skupinu kódů, které opravují jednoduché chyby. Kódy se snadno dekódují a jsou perfektní, tj. mají nejmenší myslitelnou redundanci. Hammingův kód s n-kontrolními znaky má délku 2^n-1 takže dostáváme 3-2 kód, 10-15 kód apod. Hammingovy kódy jsou perfektní kódy pro jednoduché opravy, tato vlastnost je charakterizuje.

Binární kód se nazývá Hammingův jestliže má kontrolní matici jejíž slova jsou nenulové délky a žádné z nich se neopakuje.

Např. pro pět informačních prvků ( k = 5) a n = 9 je počet prvků zabezpečení:

(= počet řádků H) a sloupců kontrolní matice H.

Cyklické kódy

Patří k systematickým lineárním kódům. Jejich specifická vlastnost, podle které se nazývají, spočívá v tom, že cyklickou záměnou prvků použité kódové složky vzniká opět použitá kódová složka. Je-li použitá složka cyklického kódu, pak i kódové složky a patří k použitým složkám kódu.

Kódová složka délky n je pak vyjádřena polynomem n-1 stupně:

Cyklický (n,k) kód je takový kód, jehož kódové složky lze vyjádřit mnohočleny stupně n-1 a menšího, jež jsou dělitelné beze zbytku generačním mnohočlenem G(X) stupně .

Označme I(X) mnohočlenem, jež reprezentuje přenášenou informaci a k prvky. Postup zabezpečení je následující. Každý mnohočlen I(X) se nejprve násobí členem : čímž se stupeň každého členu polynomu I(X) zvýší o r, tj na Potom se I(X) dělí generačním mnohočlenem G(X):

Např. pro n = 7 lze realizovat tolik cyklických kódů délky n = 7, kolik existuje dělitelů dvojčlenu . Protože dvojčlen lze rozložit na: existuje celkem 6 různých polynomů G(X), kterým odpovídají kódy v tabulce.

Z hlediska rozložení chybných míst v přenesené zprávě dělíme kanály na: s nezávislým výskytem chyb a se shluky chyb. Shlukem chyb délky b rozumíme skupinu b po sobě jdoucích prvků posloupnosti zprávy, z nichž alespoň první a poslední jsou chybné a vzdálenost dalšímu shluku je větší než b. Podle doporučení mezinárodní normy se používají cyklické kódy (n,k) s generačním mnohočlenem (CCITT-16) Dále se používá cyklický kód CRC-16 s generačním mnohočlenem Oba kódy detekují následující chyby :

všechny jednoduché, dvojnásobné a trojnásobné chyby

jakýkoliv počet chyb

libovolný shluk o délce b-16 nebo kratší