Контрольные

вопросы к

Лекции 12

12-1. Что называется кодом?

12-2. Что называется основанием кода?

12-3. Какой код называется равномерным?

12-4. Что называется мощностью кода?

12-5. Как определяется коэффициент избыточности кода?

12-6. Какой код называется безизбыточным?

12-7. Являются ли безизбыточными двоично-десятичные коды?

12-8. Что является целью эффективного кодирования?

12-9. Опишите методику Шеннона-Фано для построения эффективного кода.

12-10. В чем состоит недостаток методики Шеннона-Фано для построения эффективного кода?

12-11. Опишите методику Хаффмена для построения эффективного кода.

12-12. Опишите методику построения кодового дерева для кода Хаффмена.

12-13. Какие эффективные коды называются префиксными?

12-14. Что устанавливает неравенство Крафта?

Лекция 13

Общие

Принципы

Построения

Помехоустойчивых

Кодов

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

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) сведем в таблицу

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

Для ответа на второй вопрос воспользуемся формулой , где 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)

3.3.2. Классификация избыточных двоичных кодов

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

Рассмотрим одну из возможных классификаций избыточных корректирующих кодов (рис. 3.8).

Рис. 3.8

1. Так же как и неизбыточные, избыточные коды могут быть подразделены на равномерные и неравномерные. Признаком равномерности является то, что в каждой кодовой комбинации содержится n = const разрядов. Неравномерные коды получили существенно меньшее распространение.

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

3. Если в каждой кодовой комбинации длины n блокового кода можно выделить k разрядов, предназначенных собственно для передачи информации и называемых информационными, и n-k разрядов, избыточно введенных для увеличения кодового расстояния кода с целью придания ему корректирующих свойств, то такой код называется разделимым. Эти n-k разрядов называются контрольными или проверочными. Если такого разделения разрядов кодовой комбинации по их функциональному назначению произвести нельзя, то такой код называется неразделимым.

4. Если в разделимом коде при кодировании информационные символы не изменяются, то такой код называется систематическим. В противном случае, т.е. когда при кодировании изменяются не только проверочные, но и информационные разряды, код называется несистематическим. Характерной особенностью большинства систематических кодов является то, что проверочные n-k разрядов кодовой комбинации представляют собой результаты определенных линейных операций над k информационными разрядами. Такие коды называются линейными. Линейные коды образуют векторное пространство и обладают следующим важным свойством: две кодовые комбинации можно сложить (для двоичных кодов - по модулю два), в результате чего получится третья кодовая комбинация этого же кода. Это свойство приводит к двум важным следствиям. Первое - каждая кодовая комбинация выражается в виде линейной комбинации небольшого числа выделенных кодовых комбинаций, называемых базисными векторами. Это существенно упрощает как описание кода (см.далее - матричное описание), так и процедуры кодирования и декодирования. Второе - линейность существенно упрощает вычисление параметров кода, в частности, кодового расстояния. Расстояние Хэмминга между данной кодовой комбинацией и нулевой кодовой комбинацией равно числу ненулевых элементов в данной кодовой комбинации. Это число часто называют весом Хэмминга данной кодовой комбинации. Список, содержащий число кодовых комбинаций каждого веса, называют спектром кода.

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

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

3.3.3 Простейшие блоковые коды с обнаружением ошибок

1. Код на одно сочетание (или код с постоянным весом)

Как следует из названия кода, в каждой его кодовой комбинации, состоящей из n разрядов, содержится t единиц, причем t=const для всех комбинаций.

Мощность кода, т.е. число разрешенных комбинаций, равна числу сочетаний из n по t,т.е.

.

Следовательно, коэффициент избыточности такого кода

.

В качестве примера кода на одно сочетание можно привести код «из 5 по 2», для которого

и и d=2.

Разрешенные комбинации этого кода: 00011, 00101, 00110, 01001, 01010, 01100, 10001, 10010, 10100, 11000.

Из рассмотренного примера можно сделать вывод о том, что этот код является неразделимым.

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

2. Разделимые коды с обнаружением ошибок

Из названного класса рассмотрим принципы образования и характеристики следующих кодов:

* код с проверкой паритета (на четность или нечетность),

* код с простым повторением,

* инверсный код,

* корреляционный код.

Правила образования этих кодов ясны из приводимой ниже таблицы.

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

Этот код обнаруживает все ошибки нечетной кратности. Мощность кода N_p = 2^n-1. Коэффициент избыточности , т.е. уменьшается с увеличением числа разрядов кодовой комбинации.

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

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

. (3.18)

Пусть, например, используется код с проверкой на нечетность и справедлива модель ошибок из примера 3.8., в котором р_ош = 0,44. Как было сказано, код с проверкой на нечетность обнаруживает все ошибки нечетной кратности, следовательно, вероятность появления необнаруженной ошибки (см.табл.в примере 3.8.) равна р_{н ош} = р_5,2 + р_5,4 = 0,07 + 0,0004 = 0,0704. Тогда .

При приеме кода с простым повторением осуществляется сравнение k информационных разрядов комбинации с остальными n-k контрольными разрядами. Если значения сравниваемых одноименных разрядов совпадают, то комбинация полагается принятой верно. В противном случае реализуется защитный отказ. Этот код обнаруживает все ошибки нечетной кратности и часть ошибок четной кратности. Мощность кода N_p = 2^n/2. Коэффициент избыточности .

Прием инверсного кода осуществляется в два этапа. На первом этапе анализируется четность информационной части комбинации. Если она четна, то проверочная часть остается без изменения. Если она нечетна, то проверочная часть инвертируется. На втором этапе информационная часть поразрядно сравнивается с проверочной. Если они совпадают, то полагается, что комбинация принята верно. Этот код обнаруживает все ошибки кратностью 1,2,5,6 и большую часть 3- и 4-кратных ошибок. Мощность кода и коэффициент избыточности имеют те же значения, что и для кода с простым повторением.

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