3.10 Hamming код
Най-често срещаният систематично линеен блок кодът е код на Хеминг. Това включва кодове с минимално разстояние Dmin = 3. способни да коригират еднократно грешка.
При предаването на кодовата дума чрез комуникационен канал могат да предизвикат една единствена грешка в някоя от нейните елементи. Броят на такива ситуации. По този начин, с цел да се определи къде е възникнала грешката, броят на комбинациите от тестови елементи 2г трябва да бъде не по-малко от броя на възможните ситуации за грешки в кода, плюс ситуацията, когато не се случва грешката, т.е.. Д. Неравенството
От това неравенство трябва да бъде минимално съотношение на изпитване и данни битове, необходими за коригиране на единични грешки
За изчисляване на основните параметри на кода на Хеминг да зададете броя на скрининг елементи R. тогава дължината на кодови думи п ≤ 2 R-1. и броя на информационните елементи к = N-R. Съотношенията между R. п и к са показани в следващата таблица (таблица. 3.3).
Характерна особеност на проверка код матрица с Dmin = 3 е, че колони - R различни комбинации ненулеви дължина.
Хеминг, предложени за позициониране колони от матрицата за проверка, така че -тата колона на матрицата и номера на кодовата дума ранг отговарят на бинарното представяне аз. Тогава синдрома на единния корекция на грешки е двоично представяне на номера на категория, където е възникнала грешката. За това ниво скрининг не трябва да бъде в дясната част на кодовата дума, и позициите на числа, които са с мощност на две, т. Е. 20. 21. 22. ..., 2R-1.
Например, за г = 3 Hamming код паритет проверка матрица е от формата
Матрицата за проверка (К, N) -code Hamming състои от п = 2R-1 редове и колони R и представлява двоична комбинация от т. където I - номер на колона на матрицата проверка (кодовата дума бита).
Синдром. определяне проверка система код уравнения открити от уравнението ф = 0.
Например, R = 3 за скрининг система от уравнения е както следва:
От това ниво скрининг (контролни) са едновременно
^ Да кодира съобщение m. както на потребителския интерфейс, където аз не се равнява на мощността на 2. подходящи бита съобщения са взети, както и проверка на бита с индекси на степен 2 са паритетни уравнения система код. Във всеки уравнение съдържа само една контролна сума.
ПРИМЕР 1 кодират m съобщение = (0 1 1 1) (4, 7) код Hamming.
От системата уравнения намираме контролни суми за валидиране:
Така, последователността, кодирана дума е (0001111).
Хеминг код за декодиране се случва по следния начин. Определена синдром получи последователност S = Y , където - транспозицията на кода за паритет проверка матрица; Y - полученото вектора. Ако този синдром е нула вектор, се счита, че думата се предава без грешки, в противен случай стойността на синдрома съответства на двоичното представяне на номера на категория, където е възникнала грешката. В този случай, трябва да промените стойността на погрешното освобождаване, като се брои бита от ляво на дясно, като се започне с един.
Пример 2 е кодирана информация (4, 7) код Hamming. Приет от у последователност = (0011111). Разшифровай получи вектор.
Определя се получи синдром вектор:
т. е. че грешката е възникнала в третата категория.
Коригиране на грешката чрез промяна на стойността в третия бит
В изпратеното съобщение се декодира като
Генериране на матрица (К, N) -code се Hamming матрица (к х п), в която колоните номерирани не градуса 2 форма подматрица единица, а останалите колони съответстват на код уравнения проверка. Такава матрица в кодирането на битовете съобщение да бъдат копирани в състояние не мощност от 2, и запълване на друга система за изчисление код позиция съгласно контролни битове.
Пример 3. Системата за скрининг на уравнения (4, 7) код Hamming следното:
Съответно, генератор матрица на кода има формата
Какво кодове са здрави. Какви са общите свойства се характеризират?
Какво да шумоустойчиви кодове въведе съкращения?
Какви са различните класове за корекция на грешката кодове?
Какви са кодовете се отнасят до блок за корекция на грешката кодове. В някои случаи, те трябва да се използва?
Как да се определят дейността на събиране и умножение в двоична символи GF (2) (събиране и умножение по модул 2)?
Какво кодове се наричат линейни блокови кодове. Кои кодове са собственост на систематичност.
Какво е кодировката на проверка паритет. Какво е излишъка на кода? Какви са предимствата и недостатъците на този код?
Каква информация модел предаване канал, описан от двоичен симетричен канал.
Каква е процедурата за откриване и коригиране на грешки, повтарящ се код. Какви са предимствата и недостатъците на този код?
Какви са различните начини за определяне на линейни блокови кодове. Какви са основните части на строителство кодовата дума на линейния системен код блок?
Каква е системата за проверка на уравнения линеен блок код?
Каква е генератор матрица на линеен блок код? Какви са неговите качества? Каква е структурата на матрицата на генератор?
Подобно използване на генератор матрица, за да се изгради система за проверка на уравнения на линеен блок код?
Каква е проверка матрица на линеен блок код? Какви са неговите качества?
Каква е структурата на проверка матрица на линеен блок код? Каква част от проверка матрица, съответстваща на информационните символи и какво - проверката?
Както използвайки матрицата за проверка, за да се изгради система за проверка на уравнения на линеен блок код?
Както е описано вектор грешка в двоичен комуникационен канал? Каква е задачата на декодиране на излъчваната кодовата дума?
Какво е код синдром линеен блок код? Както е определено?
Как имота се характеризира с синдром на полученото вектор? В някои случаи, кодът за синдром не може да открие грешки в предава последователност?
Как да използвате синдрома на код откриване и коригиране на грешки линеен блок код?
Както е определено от теглото и Хеминг разстоянието на двоични последователности?
Каква е минималната кода на Хеминг разстояние е линеен блок код? Как се определя това?
Какво е необходимо и достатъчно условие за откриване на линеен блок код, определен множество грешки?
Какво е необходимо и достатъчно условие за коригиране на линеен блок код, определен множество грешки?
Какви са необходими и достатъчни условия за съществуване за корекция на грешката код?
Как е минималният брой на символите за проверка за линеен блок код с определени характеристики?
Как да се изгради една генерираща матрица на линеен блок код с определени характеристики?
Всички линейни блокови кодове, наречени Хеминг кодове?
Как е броят на информация и паритет на кода за Хеминг.
Както кодовите думи са изградени кода на Хеминг.
Как е проверка за четност матрица на двоичен Хеминг код на.
Което отговаря на стойност синдром с помощта на кода на Хеминг?
Как декодиране кода на Хеминг?
Как е генератор матрица на кода на Хеминг?
1 С Shannon, Работи на теорията на информацията и кибернетика. - М. Издател чуждестранна литература 1963.
2 A. Yaglom Yaglom I. Вероятности и статистика - М. Science, 1973.