Линеен код

По математика и теория на информацията ред код Важен тип блок код се използва в схемите за откриване и коригиране на грешки. Линейните кодове, в сравнение с други кодове, позволяват прилагането на по-ефективни алгоритми за кодиране и декодиране на информация.

Съдържание

В процеса на съхраняване на данни и предаване на информация по комуникационни мрежи неизбежно възникват грешки. Мониторингът на целостта на данните и корекцията на грешки са важни задачи на много нива на работа с информация (по-специално физически, канален, транспортен слой на OSI модела).

В комуникационните системи са възможни няколко стратегии за справяне с грешки:

  • откриване на грешки в блокове с данни и заявка за автоматично препредаване повредени блокове - този подход се използва главно на ниво връзка и транспорт;
  • откриване на грешки в блокове с данни и изхвърляне на лоши блокове - този подход понякога се използва в поточни медийни системи, където забавянето на предаването е важно и няма време за повторно предаване;
  • корекция на грешка (корекция на грешки напред) се прилага на физическо ниво.

Кодове за откриване и коригиране на грешки

Корекционни кодове - кодове, използвани за откриване или коригиране на грешки, възникващи по време на предаването на информация под въздействието на смущения, както и по време на нейното съхранение.

За да направите това, когато пишете (прехвърляте), специално структуриран прекомерен информация и при четене (получаване) се използва с цел откриване или коригиране на грешки. Естествено, броят на грешките, които могат да бъдат коригирани, е ограничен и зависи от конкретния използван код.

С кодове за корекция на грешки, тясно свързани кодове за откриване на грешки. За разлика от първата, втората може само да установи факта на грешка в предадените данни, но не и да я коригира.

Всъщност използваните кодове за откриване на грешки принадлежат към същите класове кодове като кодовете за корекция на грешки. Всъщност всеки код за коригиране на грешки може да се използва и за откриване на грешки (и ще може да открие повече грешки, отколкото е успял да поправи).

По начина на работа с данните са разделени кодовете, които коригират грешките блок, разделяне на информацията на фрагменти с постоянна дължина и обработка на всеки от тях поотделно, и конволюционен, работа с данни като непрекъснат поток.

Блокови кодове

Нека кодираната информация да бъде разделена на фрагменти с дължина \ (k \) бита, които се преобразуват в кодови думи дължина \ (n \) бита. Тогава съответният блоков код обикновено се означава \ ((n, k) \). Освен това се извиква числото \ (R = \ frac \) код скорост.

Ако оригиналните битове \ (k \) останат непроменени, кодът добавя \ (n-k \) проверка, се нарича такъв код систематичен, в противен случай несистематичен.

Блоковият код може да бъде зададен по различни начини, включително таблица, където всеки набор от информационни битове \ (k \) се преобразува в \ (n \) бита на кодовата дума. Добрият код обаче трябва да отговаря поне на следните критерии:

  • възможността за коригиране на възможно най-много грешки,
  • възможно най-малко съкращения,
  • лекота на кодиране и декодиране.

Лесно е да се види, че дадените изисквания си противоречат. Ето защо има голям брой кодове, всеки от които е подходящ за свой собствен набор от задачи.

Почти всички използвани кодове са линейни. Това се дължи на факта, че нелинейните кодове са много по-трудни за изследване и е трудно за тях да осигурят приемлива лекота на кодиране и декодиране.

Матрица на поколението

Нека векторите \ (\ overrightarrow = (x_. X_), \ overrightarrow = (x_. X_). \ Overrightarrow = (x_. X _) \) да бъдат основата на линейното пространство \ (C \). Чрез дефиницията на основа всеки вектор \ (\ overrightarrow \ в C \) може да бъде представен като линейна комбинация от базисни вектори: \ (\ overrightarrow = \ overrightarrow + \ overrightarrow +. + \ Overrightarrow \) или в матрица форма, като:

Тази връзка установява връзка между векторите на коефициенти \ (\ overrightarrow = (,.) \) И векторите \ (\ overrightarrow \ в C \). Като изброите всички вектори на коефициенти \ (\ overrightarrow = (,.) \), Можете да получите всички вектори \ (\ overrightarrow \ в C \). С други думи, матрицата \ (G \) генерира линейното пространство.

Проверете Matrix

Друг начин за определяне на линейни пространства е да се опише чрез матрицата на четността.

Нека \ (\ mathbb \) е линейно k-мерно пространство над полето \ (\ mathbb_q \) и \ (\ mathbb \) ортогоналното допълнение \ (\ mathbb \). Тогава, по една от теоремите, измерението на \ (\ mathbb \) е \ (r = n - k \). Следователно има r базисни вектори в \ (\ mathbb \). Нека \ (\ overrightarrow_1 = (_1>. _N>), \ overrightarrow_2 = (_1>. _N>). \ Overrightarrow_r = (_1>. _N>) \) основа в \ (\ mathbb \).

Тогава всеки вектор \ (\ overrightarrow \ в C \) удовлетворява следната система от линейни уравнения:

\ (\ започнете h_ x_1 + h_ x_2 +. + h_ x_n = 0 \\ h_ x_1 + h_ x_2 +. + h_ x_n = 0 \\. \\ h_ x_1 + h_ x_2 +. + h_ x_n = 0 \ end \ )

Или в матрична форма: \ (\ overrightarrow H ^ T = 0 \),

където \ (H = \ begin \ overrightarrow_1 \\ \ overrightarrow_2 \\. \\ \ overrightarrow_r \\ \ end = \ begin h_ & h_ & . & h _ \\ h_ & h_ & . & h _ \\. . & . & . & . \\ h_ & h_ & . & h _ \\ \ end \) - проверете матрицата.


Дадената система от линейни уравнения трябва да се разглежда като система от проверки за всички вектори на линейно пространство, поради което матрицата \ (\ mathbb \) се нарича контролна матрица.