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

1. Общие принципы построения помехоустойчивых кодов

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

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

Любые коды могут быть представлены как конечные множества N_р слов, каждое из которых состоит из n символов. Интерпретировать кодовые слова можно по-разному:

1) как наборы из n предметов, располагаемых в некотором порядке в n позициях – комбинаторная интерпретация;

2) как наборы n-значных элементов множества, замкнутого относительно операций над наборами – алгебраическая интерпретация;

3) как множество точек некоторой геометрической фигуры – геометрическая интерпретация.

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

Таким образом, все множество N=2ⁿ двоичных кодовых комбинаций, где n - число разрядов в комбинации, разбивается на два подмножества - разрешенных N_р и запрещенных N-N_р кодовых комбинаций. Если в результате воздействия помех передаваемая кодовая комбинация перейдет из подмножества разрешенных в подмножество запрещенных, ошибка будет обнаружена при приеме (рис. 3.5)

Рис. 3.5. Кодовые пространства при обнаружении ошибок

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

Пусть, например, требуется передавать два сообщения - А₁ и А₂. Для этого достаточно одного двоичного разряда - А₁ = 0, А₂ = 1. Под воздействием помехи одно сообщение неминуемо преобразуется в другое.. Добавим к каждой кодовой комбинации еще по одному разряду, выбрав его значение таким, чтобы в каждой разрешенной кодовой комбинации было нечетное число единиц, т.е. А₁ = 01, А₂ = 10. Эти комбинации образуют подмножество разрешенных кодовых комбинаций. В подмножество запрещенных, следовательно, войдут комбинации, содержащие четное число единиц - 00 и 11. Одиночная ошибка может перевести сообщение А₁ в 00 или в 11, аналогично и по отношению к сообщению А₂, т.е. при наличии одиночной ошибки обе комбинации переходят в подмножество запрещенных, т.о. любая одиночная ошибка будет обнаружена.

При необходимости построения кода с исправлением ошибок все множество кодовых комбинаций N разбивается на N_p непересекающихся подмножеств. Каждое из подмножеств приписывается одной из N_p разрешенных кодовых комбинаций. Если передавалась кодовая комбинация A_j , принадлежащая подмножеству N_j , а принятой оказалась комбинация A_i , которая также принадлежит подмножеству N_j , то принимается решение о том, что принята комбинация A_j , т.е. ошибка исправляется. Если комбинация в результате воздействия помех перейдет в другое подмножество, то она будет принята с ошибкой (рис. 3.6).

Рис. 3.6. Кодовые пространства при исправлении ошибок

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

Для иллюстрации сказанного продолжим рассмотренный ранее пример, введя в использованные в нем кодовые комбинации еще один дополнительны разряд. В результате образуется множество из N=2³ = 8 кодовых комбинаций. Его следует разделить на два (по числу передаваемых сообщений А₁ и А₂) непересекающихся подмножества. Пусть, например, для передачи А₁¹ используется комбинация 001. Одиночная ошибка в любом из разрядов этой комбинации приведет к комбинациям А₁² = 000, А₁³ = 011 и А₁⁴ = 101. Эти четыре комбинации и образуют первое подмножество. При приеме любой из них будет принято решение о том, что передавалось А₁, т.е. любая одиночная ошибка будет исправлена. Аналогично относительно А₂, если положить, что А₂¹ = 110, то А₂² = 111, А₂³ = 100, А₂⁴ = 010. При приеме любой из этих комбинаций будет принято решение, что передавалось А₂.

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

В общем случае для двоичных кодов расстояние между i-ой и j-ой комбинациями кода определяется по формуле

, (3.14)

где x_il -символ на l-ой позиции i-ой комбинации, x_jl - символ на l-ой позиции j-ой комбинации, - символ суммирования по модулю два.

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

Величина min d_ij = d_min , где минимум берется по всем комбинациям, входящим в данный код, называется кодовым расстоянием кода.

Множество n-разрядных кодовых комбинаций можно рассматривать как n-мерное векторное пространство, называемое кодовым пространством, а его элементы - кодовые комбинации, можно назвать кодовыми векторами.

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

Пусть, например, v₁ = 11111 - переданный кодовый вектор, а v₂ = 10111 - принятый кодовый вектор, тогда вектор ошибки е=01000.

С этих позиций модель дискретного двоичного канала можно представить в виде сумматора по модулю 2 (рис. 3.7). При теоретических исследованиях процесса возникновения ошибок в дискретном канале используют математические модели ошибок.
	Рис. 3.7. Модель дискретного двоичного канала

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

Назовем величину, равную числу единиц в векторе ошибки, кратностью ошибки и обозначим ее символом q.

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

(3.15)

Здесь p_n,q -вероятность того, что при передаче по дискретному каналу в кодовой комбинации двоичного кода с разрядностью n возникнет ошибка кратности q .

Используя (3.15) можно получить следующие выражения для вероятности ошибочного декодирования р_од при исправлении ошибок и для вероятности необнаруженной ошибки р_но при обнаружении ошибок .

Здесь [d/2] означает целую часть d/2. Знак неравенства в этих выражениях ставится потому, что код, вообще говоря, может исправлять некоторые ошибки кратности d/2 и выше и обнаруживать ошибки кратности d и выше.

Неравенства, приведенные выше, иллюстрируют важную роль кодового расстояния d как основного показателя исправляющих и обнаруживающих свойств кода в симметричном канале без памяти - чем больше d, тем меньше р_од и р_но. С учетом этого задачу поиска наилучшего кода в смысле максимального d следует формулировать так: «При заданном числе кодовых комбинаций М разрядности n найти код длины n, содержащий М комбинаций и имеющий наибольшее возможное d». В общем виде эта задача в теории кодирования не решена, хотя для некоторых М и n ее решения получены.

Пример 3.6. Определить вероятность возникновения ошибок кратности q=0,1,2,3,4,5 в кодовой комбинации длины n=5 двоичного кода, если вероятность ошибочного приема разряда p=0,1. Определить вероятность ошибочного приема кодовой комбинации.

Решение. В качестве ответа на первый вопрос вероятности, вычисленные по формуле (3.15) сведем в таблицу

q	0	1	2	3	4	5
p5,q	0,56	0,33	0,07	0,008	0,0004	0,00001

Из таблицы видно, что вероятность появления ошибок большой кратности мала. Наиболее часто появляются однократные ошибки.

Для ответа на второй вопрос воспользуемся формулой , где p_5,0 -вероятность безошибочного приема. Тогда .

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

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

Результатом действия ошибки кратностью q_max на разрешенную кодовую комбинацию будет новая кодовая комбинация, удаленная от первой на расстояние q_max.

Отсюда ясно, что для обнаружения всех ошибок, кратностью не превышающей q_max, кодовое расстояние должно быть d> q_max, по крайней мере

d = q_max + 1 . (3.16)

В теории кодирования доказывается, что для обеспечения возможности исправления ошибок кратности не более q_max кодовое расстояние должно быть больше 2q_max. Обычно оно выбирается по формуле

d = 2q_max + 1 . (3.17)