Линейные коды общего вида

Линейный блоковый код — такой код, что множество его кодовых слов образует -мерное линейное подпространство (назовём его ) в -мерном линейном пространстве, изоморфноепространству -битных векторов.

Это значит, что операция кодирования соответствует умножению исходного -битного вектора на невырожденную матрицу , называемую порождающей матрицей.

Пусть — ортогональное подпространство по отношению к , а — матрица, задающая базис этого подпространства. Тогда для любого вектора справедливо:

Минимальное расстояние и корректирующая способность

Основная статья: Расстояние Хемминга

Расстоянием Хемминга (метрикой Хемминга) между двумя кодовыми словами и называется количество отличных бит на соответствующих позициях:

.

Минимальное расстояние Хемминга является важной характеристикой линейного блокового кода. Она показывает, насколько «далеко» расположены коды друг от друга. Она определяет другую, не менее важную характеристику — корректирующую способность:

.

Корректирующая способность определяет, сколько ошибок передачи кода (типа ) можно гарантированно исправить. То есть вокруг каждого кодового слова имеем -окрестность , которая состоит из всех возможных вариантов передачи кодового слова с числом ошибок ( ) не более . Никакие две окрестности двух любых кодовых слов не пересекаются друг с другом, так как расстояние между кодовыми словами (то есть центрами этих окрестностей) всегда больше двух их радиусов .

Таким образом, получив искажённую кодовую комбинацию из , декодер принимает решение, что исходной была кодовая комбинация , исправляя тем самым не более ошибок.

Поясним на примере. Предположим, что есть два кодовых слова и , расстояние Хемминга между ними равно 3. Если было передано слово , и канал внёс ошибку в одном бите, она может быть исправлена, так как даже в этом случае принятое слово ближе к кодовому слову , чем к любому другому, и, в частности, к . Но если каналом были внесены ошибки в двух битах (в которых отличалось от ), то результат ошибочной передачи окажется ближе к , чем , и декодер примет решение, что передавалось слово .

Коды Хемминга

Коды Хемминга — простейшие линейные коды с минимальным расстоянием 3, то есть способные исправить одну ошибку. Код Хемминга может быть представлен в таком виде, чтосиндром

, где — принятый вектор, будет равен номеру позиции, в которой произошла ошибка. Это свойство позволяет сделать декодирование очень простым.

В вычислительной технике и сетях передачи данных би́том чётности (англ. Parity bit) называют контрольный бит, служащий для проверки общей чётности двоичного числа (чётности количества единичных битов в числе).

Применение

В последовательной передаче данных часто используется формат 7 бит данных, бит чётности, один или два стоповых бита. Такой формат аккуратно размещает все 7-битные ASCIIсимволы в удобный 8-битный байт. Также допустимы другие форматы: 8 бит данных и бит чётности.

В последовательных коммуникациях чётность обычно контролируется оборудованием интерфейса (например UART). Признак ошибки становится доступен процессору (и ОС) через статусный регистр оборудования. Восстановление ошибок обычно производится повторной передачей данных, подробности которого обрабатываются программным обеспечением (например, функциями ввода/вывода операционной системы)

Контроль некой двоичной последовательности (например, машинного слова) с помощью бита чётности также называют контролем по паритету. Контроль по паритету представляет собой наиболее простой и наименее мощный метод контроля данных. С его помощью можно обнаружить только одиночные ошибки в проверяемых данных. Двойная ошибка, будет неверно принята за корректные данные. Поэтому контроль по паритету применяется к небольшим порциям данных, как правило, к каждому байту, что дает коэффициент избыточности для этого метода 1/8. Метод редко применяется в компьютерных сетях из-за невысоких диагностических способностей. Существует модификация этого метода — вертикальный и горизонтальный контроль по паритету. Отличие состоит в том, что исходные данные рассматриваются в виде матрицы, строки которой составляют байты данных. Контрольный разряд подсчитывается отдельно для каждой строки и для каждого столбца матрицы. Этот метод обнаруживает значительную часть двойных ошибок, однако обладает большей избыточностью. Он сейчас также почти не применяется при передаче информации по сети.

Поиск по сайту: