Простейшие корректирующие коды

Код с четным числом единиц

Код с четный числом единиц является двоичным блочным кодом и образуется путем добавления к кодовому слову k -символьного кода одного избыточного символа так, чтобы количество единиц в новом -символьном слове было четным. В таблице 14 приведён пример кодирования пятизначного кода: k =5, n =6.

 

Таблица 14 - Таблица кодирования

 

1	2	3	4	5	6
1 0 1 0	0 1 1 0	1 0 0 0	1 0 1 0	0 1 1 1	1 0 0 1

Код обнаруживает все ошибки нечетной кратности. Обнаружение ошибок производится проверкой принятого кодового слова на четность, так как все разрешенные слова имеют четное число единиц, а неразрешенные - нечетное. Проверка на четность осуществляется суммированием всех символов слова по модулю два. Если словоимеет четное число единиц, то сумма его символов по модулю 2 равна 0.

Если в канале связи ошибки независимы и вероятность искажения кодового символа равна , то согласно биномиальному закону распределения вероятность обнаружения ошибки равна

(1.21)

вероятность искажения кодового слова

                                                                      

вероятность необнаруженной ошибки

(1.22)

Коэффициент избыточности этого кода

 

Код с постоянным весом

Примером кода с постоянным весом является семизначный код с отношением единиц и нулей в каждом кодовом слове, равным . Код имеет

                                     (1.23)

разрешенных кодовых слов. Такого числа слов достаточно для помехоустойчивого кодирования всех кодовых слов 5-значного телеграфного кода.

Семизначный код 3/4 относится к неразделимым кодам с постоянным весом. В кодовом слове этого кода невозможно разделить символы на информационные и проверочные (избыточные). Обнаружение ошибок производится простым подсчетом единиц или нулей в принятой кодовом слове. Код обнаруживает все ошибки нечетной кратности и около 50% ошибок четной кратности. Ошибки не обнаруживаются, если в одном кодовом слове искажается одинаковое число единиц и нулей. Например, если в разрешенном слове 1011000 искажены первый и второй (или второй и третий и т.д.) кодовые символы, то кодовое слово превращается в другое разрешенное - 0111000 и т.д.

Вероятность необнаруженной ошибки для кода 3/4 в канале связи с независимыми ошибками равна

Избыточность кода g = r / n = 2/7» 0,3.                                                             (1.24)

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

 

Инверсный код

Кодовые слова инверсного корректирующего кода образуются повторением исходного кодового слова (таблица15).Если число единиц в исходном слове четное, оно повторяется в неизменном виде; если число единиц нечетное, то при повторении все символы исходного кодового слова инвертируются (нули заменяются единицами, а единицы - нулями).

	k					r
	1	2	3	4	5	6	7	8	9	10
a) a) б) б)	1 0 0 1	0 1 1 0	1 1 1 0	1 0 0 0	1 0 1 0	1 0 1 0	0 1 0 1	1 1 0 1	1 0 1 1	1 0 0 1

Таблица 15 - Таблица кодирования

а) - в исходном кодовом слове четное число единиц,

б)- в исходном кодовом слове нечетное число единиц.

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

Суммируются единицы, содержащиеся в первых k символах кодового слова.

2. Если число единиц четное,  последующих символов сравниваются попарно с первыми k символами; если число единиц в первых символах нечетное, последующие символы перед сравниванием инвертируются.

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

Ошибка в кодовом слове не обнаруживается, если одновременно искажается четное число символов в исходном слове и соответствующиеим кодовые символы в последовательности повторяемых  символов. Например, если в. кодовом слове 1011001001 искажены 1-ый, 2-ой, 6-ой, 7-ой символы, то ошибка не может быть обнаружена, так как образуется другое разрешенное слово - 01110'10001.

В канале связи с независимыми ошибками вероятность необнаруженной ошибки при использовании инверсного кода (таблица 1.2) равна

                                                      (1.25)

то есть существенно меньше, чем в аналогичных условиях для 6-значного кода с проверкой на четность и 7-значного кода с постоянным весом.

Однако избыточность инверсного кода еще больше,чем 7-значного кода, и равна 0,5 (50%).

Групповые коды