Помехоустойчивое кодирование

Помехоустойчивые или корректирующие коды позволяют обнаружить и исправить ошибки в принятой кодовой комбинации, искаженной помехами. Для этого к передаваемой информации добавляются проверочные символы, которые формируются по определенным правилам.

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

Отличие одной кодовой комбинации от другой характеризуется кодовым расстоянием d. Кодовое расстояние d - это количество позиций, в которых одна кодовая комбинация отличается от другой.

Для кодовых комбинаций 010 и 011 d =1, 1100 и 0110 d = 2, 0111011 и 1010001 d = 4.

Для обнаружения одиночных ошибок минимальное кодовое расстояние между комбинациями должно равняться d_min = 2. Например, для двоичного кода (основание кода m = 2) длиной n = 3 возможный набор разрешенных комбинаций с d_min = 2 имеет вид:

000; 110, 101, 011. Разрешенные комбинации содержат четное количество 1. Запрещенные комбинации содержат нечетное количество 1 - 001, 010, 100, 111.

Предположим, что была передана комбинация 000. В линии связи помеха исказила второй символ и мы приняли 010. Это запрещенная комбинация и декодер обнаружит ошибку. Выигрыш в помехоустойчивости получен за счет проигрыша в скорости передачи, т.к. четыре сообщения мы могли бы передавать с помощью четырех комбинаций безызбыточного кода с m = 2 и n = 2 00, 01, 10, 11.

Для исправления одиночных ошибок следует использовать код с d_min = 3. Например, для кода с m = 2; n = 3 можно использовать разрешенные комбинации 000 и 111 с d_min =3. Остальные 6 комбинаций 001, 010, 011, 100, 101 и 110 будут запрещенными.

Пусть передается комбинация 000. Допустим, что помеха исказила второй символ и мы приняли 010. Эта комбинация запрещенная, декодер фиксирует ошибку и определяет кодовые расстояния между принятой комбинацией 010 и возможными разрешенными 000 и 111. Комбинация 010 ближе к переданной комбинации 000 (d = l), чем к другой возможной 111 (d = 2). Таким образом, мы декодируем комбинацию 010 как 000, т.е. исправляем ошибку. Выигрыш в помехоустойчивости достигается за счет еще большего проигрыша в скорости передачи, т.к. два сообщения мы могли бы передавать с помощью двух комбинаций безызбыточного кода с m = 2, n = 1: т.е. 0 и 1. Проигрыш по скорости передачи данного кода, исправляющего одиночные ошибки, по сравнению с безызбыточным кодом равен 3.

Количество ошибок в кодовых комбинациях называется кратностью ошибок. Для обнаружения ошибок кратности k следует использовать код с d_min ³ k+1. Для исправления ошибок с кратностью k следует использовать коды с минимальным кодовым расстоянием d_min ³ 2k + l.

Модель дискретного канала предполагает независимость появления ошибок. Если кодовые комбинации содержат n двоичных символов, то количество (кратность) ошибок в кодовых комбинациях может изменяться от 0 до n.

Вероятность ошибки кратности к равна p_k = C_n^k´p^k´(1 – p)^n-k, ()

где р - вероятность ошибки в канале связи,

C_n^k - число сочетаний из n по к.

Например, при р = 10^-3 и n = 7 вероятность правильного приема всей комбинации равна р₀ = (1 – р)⁷= 0.99302, вероятность одиночной ошибки равна р₁ = С₇¹´р´(1 – р)⁶ = 6.95810´10^-3, вероятность ошибок с к = 2 - р₂ = С₇²´р²´(1 – р)⁵ = 2.08952´10^-5,

к = 3 - р₃ = С₇³´р³´(1 – р)⁴ = 3.486´10^-8.

р₃ >> р₄ >> р₅ >> р₆ >> р₇ = p⁷ = 10^-21.

Как следует из приведенных расчетов, наиболее вероятны одиночные ошибки. Вероятность двойных ошибок в 300 раз меньше.

Для обнаружения одиночных ошибок одним из наиболее совершенных способов кодирования является «проверка на четность»: к кодовой комбинации из k информационных символов добавляется один проверочный такой, чтобы количество единиц в кодовой комбинации было четным. Например, к комбинации 0100110 добавляем проверочный символ 1, и передаем комбинацию 01001101. Одиночная ошибка делает число единиц в принятой кодовой комбинации нечетным, что и обнаруживается декодером. Структурные схемы кодера и декодера с проверкой на четность представлены на рис..

Линейный двоичный блочный код

Широко используются в технике связи линейные блочные коды. Блочный код состоит из кодовых комбинаций, называемых также кодовыми словами. Кодовые комбинации линейного кода образуют линейное пространство относительно поразрядного сложения по модулю 2: сумма двух комбинаций дает тоже комбинацию этого кода.

Длина каждого кодового слова равна n, т.е. общее количество кодовых комбинаций равно N = mⁿ. Если код двоичный m = 2, то N = 2ⁿ.

Из n символов кодового слова k информационные, а n – k проверочные. Такой блочный код обозначается, как код (n,k). Разрешёнными являются только 2^k комбинаций, остальные - 2n – 2k - запрещённые. Величина R = k/n называется скоростью кода.