Характеристики блочных линейных кодов

Напомним для начала, что двоичный код — это код, составленный из двоичных цифр — нуля и единицы.

Количество разрядов в каждой кодовой комбинации (блоке) называют длиной, или значностью, кода и обозначают п.

Символы каждого разряда могут принимать значения О или 1.

Количество единиц в кодовой комбинации называют весом и обозначают со.

Например, кодовая комбинация 100 101 100 имеет значность п = 9 и вес со = 4.

Степень отличия двух любых кодовых комбинаций характеризуется кодовым расстоянием d (расстоянием Хемминга), которое определяется как число разрядов, в которых комбинации отличаются одна от другой.

Кодовое расстояние Хемминга является мерой различия кодовых слов одинаковой значности. Если длины кодовых комбинаций различаются, то применяется редакторское расстояние (расстояние В. И. Левенштейна)^[1].

Для определения кодового расстояния надо просуммировать (по модулю 2) две кодовые комбинации и определить вес суммы.

Пример

Определить кодовое расстояние между комбинациями 100 101 100 и 110 110 101.

Просуммируем:

Вес полученной суммы (количество единиц) со = 4, следовательно, кодовое расстояние d = 4.

8 Определить все кодовые расстояния между безошибочными комбинациями сообщений разведчиков.

Ответ: расстояние между первой и второй строками порождающей матрицы — 6, между первой и третьей — 5, между второй и третьей — 5.

При передаче в кодовых комбинациях возникают ошибки типа «инверсия». Если ошибка произошла в одном разряде блока, она называется однократной, при ошибках в двух, трех и т. д. разрядах они называются двукратными, трехкратными и т. д. Для описания возникающих в канале ошибок используют вектор ошибки, обычно обозначаемый как е и представляющий собой двоичную последовательность длиной п с единицами в тех позициях, в которых произошли ошибки. Вес вектора ошибки равен кратности ошибки.

Так, вектор ошибки е = (0 100 0) означает однократную ошибку в четвертом разряде, вектор ошибки е=(1 100 000) —двукратную ошибку в первом и втором разрядах.

Допустим, по каналу связи передается кодовое слово и, на приемном конце канала декодером принята последовательность й, возможно, содержащая ошибки. Если е — вектор ошибок, то верны соотношения й = и ®е, а также е = и®й и и = й@е.

Помехоустойчивость кодирования обеспечивается за счет введения избыточности. Это значит, что из п символов кодовой комбинации для передачи информации используется к < п символов.

Коэффициент избыточности кода — это отношение количества проверочных битов к длине кода:

При длине кодового слова п всего существует 2'¹ кодовых слов, из них допустимыми могут быть 2^к. Соответственно, все множество кодовых комбинаций разбивается на две группы: разрешенные комбинации и запрещенные комбинации. Разрешенных комбинаций S_p = 2^к, запрещенных Sf = S — S_p = = 2'¹ -2^к. Все разрешенные комбинации известны как кодеру, так и декодеру, поскольку полностью определяются первичным алфавитом, а точнее, системой первичного кодирования алфавита источника. Если на приемной стороне канала передачи информации установлено, что принятая комбинация относится к разрешенным, то считается, что сообщение прошло без искажений, а если принята запрещенная комбинация, то делается вывод, что произошла ошибка. Однако если ошибка такова, что посланная комбинация, претерпев искажения, тем не менее попала во множество разрешенных комбинаций, такая ошибка обнаружена не будет: у декодера нет оснований считать ее ошибочной.

Пусть всего S_p разрешенных комбинаций. Каждая из них при передаче может трансформироваться в любую из S возможных комбинаций, т. е. всего имеется S? S_p возможных вариантов передачи. Из них S_p вариантов безошибочной передачи, S_p ? (S_p — 1) вариантов ошибочной трансформации в другие разрешенные комбинации и Sp • (S — S_p) вариантов трансформации в запрещенные комбинации (см. рис. 4.3).

Только передача в запрещенные варианты может быть обнаружена. Доля обнаруживаемых ошибок составляет.

Обнаруженную ошибку можно исправить, если для каждой запрещенной комбинации можно указать единственную исходную, т. е. посланную комбинацию. Таким образом, ошибка исправляется в S-S_p случаях, равных количеству запрещенных комбинаций. Доля исправляемых ошибочных комбинаций от числа обнаруживаемых составляет:

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

Рис. 4.3. Схема возникновения ошибок при передаче кодовых слов:

• 1 — ошибочная трансформация в запрещенную комбинацию;
• 2 — безошибочная передача; 3 — ошибочная трансформация в разрешенную комбинацию; 4 — разрешенные комбинации;
• 5 — запрещенные комбинации

Определим вероятность ошибочного приема сообщения. Пусть р — вероятность появления ошибки при передаче отдельного разряда кодовой комбинации. На практике эта вероятность определяется конструктивной защищенностью канала связи от внешних помех. Например, для локальных сетей, где средой передачи данных является витая пара, р = 10^_4-ь10^_6. А для оптоволоконных каналов р = 10~⁹. Для оценки вероятности возникновения ошибки при передаче кодовой комбинации, состоящей из п бит, необходимо принять определенные исходные предположения, которые называются математической моделью ошибок. Наиболее простая из них (рассмотрим только ее) — считать появление ошибки в каждом отдельном разряде (бите) кода случайным событием, которое не зависит от того, с ошибками или без них были переданы предыдущие биты. Тогда:

• • 1 — р — вероятность безошибочной передачи отдельного разряда;
• • (1 — p)ⁿ — вероятность безошибочной передачи цепочки п разрядов;
• • Р_п = 1 — (1 — р)^п — вероятность появления хотя бы одной ошибки в комбинации п разрядов. При малых р можно воспользоваться соотношением Бернулли, тогда Р_п ~ пр. Так можно оценить суммарную вероятность появления всех ошибок. Если же требуется найти вероятность ошибки с заданной кратностью t, то следует воспользоваться формулой биноминального распределения:

Вероятность ошибочной передачи сообщения с учетом всех ошибок кратности от 1 до t находится так:

Если помехоустойчивый код рассчитан на парирование ошибок кратностью до t включительно, то вероятность исправления ошибки определяется величиной P+_t.

• [1] Levensteirt V. I. Binary codes capable of correcting deletions, insertions, andreversals. URL: https://nymity.ch/sybilhunting/pdf/Levenshteinl966a.pdf