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

Напомним для начала, что двоичный код – это код с основанием 2.

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

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

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

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

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

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

Пример. Определить кодовое расстояние между комбинациями 100101100 и 110110101.

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

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

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

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

Допустим, по каналу связи передается кодовое слово U, в результате принята последовательность Û, возможно, содержащая ошибки. Если е – вектор ошибок, то Û = Ue,или, что то же самое, e = UÛ, U = Ûe.

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

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

При длине кодового слова n всего возможных кодовых слов – 2ⁿ, из них безошибочными могут быть 2^k. Соответственно, все множество кодовых комбинаций разбивается на две группы: разрешенные комбинации и запрещенные комбинации. Разрешенных комбинаций S_р = 2^k, запрещенных S_f = S – S_р=2ⁿ - 2^k. Если на приемной стороне установлено, что принятая комбинация относится к разрешенным, то считается, что сообщение прошло без искажений, а если принята запрещенная комбинация, то делается вывод, что произошла ошибка. Однако, если ошибка такова, что посланная комбинация, претерпев искажения, тем не менее, попала во множество разрешенных комбинаций, такая ошибка обнаружена не будет.

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

ошибочная трансформация в запрещенную комбинацию   безошибочная передача   ошибочная трансформация в разрешенную комбинацию    

Sр

Sр

S

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

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

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

Доля исправляемых ошибочных комбинаций от числа обнаруживаемых составляет:

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

Определим вероятность ошибочного приема сообщения. Пусть p – вероятность появления ошибки при передаче отдельного бита кодовой комбинации. Для оценки вероятности возникновения ошибки при передаче кодовой комбинации, состоящей их n бит необходимо принять определенные исходные предположения, которые называются математической моделью ошибок. Наиболее простая из них (рассмотрим только ее) – считать появление ошибки в каждом отдельном знаке (бите) кода случайным событием, которое не зависит от того, с ошибками или без них были переданы предыдущие биты.

Тогда:

1 – p – вероятность безошибочной передачи отдельного бита;

(1 – p)ⁿ – вероятность безошибочной передачи цепочки n бит;

P_n = 1 – (1 – p)ⁿ – вероятность появления хотя бы одной ошибки в комбинации n бит. При малых p можно воспользоваться соотношением Бернулли; тогда P_n n∙p. Так можно оценить суммарную вероятность появления всех ошибок. Если же требуется найти вероятность ошибки с заданной кратностью t, то следует воспользоваться формулой биноминального распределения:

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

Дата добавления: 2014-10-22