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

Введенное кодовое расстояние, называемое расстоянием Хемминга,

равно числу разрядов, в которых различаются два сравниваемых вектора

V ^ v ,

Пример3.1. Пусть Vx =1010 и V2 =1110, тогда w(Vx) =2;и<Р2) = 3;

= МУ\ Ф ^ ) = w(1010©ll 10) = и<0100) = 1, т. е. два сравниваемых вектора различаются только во втором разряде.

Пример 3.2. Пусть = 1010 и ё= 0010, тогда Kj'= 101000010 =

= 1000. Следовательно, ошибка произошла в третьем разряде передаваемо­ го вектора, т. к. именно этот разряд вектора ошибки равен 1.

Из (3.5) следует, что

e = V ' O V

Назовем вес вектора ошибки кратностью ошибки. Так, в примере 3.2 w{e) = 1, т. к. имеет место однократная ошибка. Проанализируем собы­ тия, имеющие место при передаче информации по двоичному симметрич­ ному каналу л-разрядным двоичным неизбыточным кодом, для которого справедливо равенство

М0 = М = 2 \

и, следовательно,

Ri = R\] = 0.

Рассмотрим вероятностные соотношения для передачи сообщений кодовыми комбинациями.

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

где п - длина кодовой комбинации; q - вероятность правильной передачи символа; р - вероятность неправильного (ошибочного) приема одного символа (вероятность ошибки на символ).

Обобщим приведенные соображения, записав вероятность полной группы событий, возникающих при приеме кодовой комбинации. Действи­ тельно, возможно одно из следующих событий: нет ошибок - с вероятно­ стью Р{0), однократная ошибка в любом разряде - с вероятностью />(1), двукратная ошибка в любых разрядах - с вероятностью Р(2), и т. д. Сумма вероятностей, образующих полную группу независимых событий, равна 1:

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

•правильная передача сообщения - имеет место при правильном приеме всех символов;

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

Поскольку указанные варианты образуют полную группу событий, то сумма их вероятностей равна 1. Вероятность правильной передачи Рпр определяется вероятностью Р(0), а вероятность трансформации Рхр - сум­ мой всех остальных вероятностей от Р(1) до Р(п):

Для наглядности анализа указанных событий воспользуемся графом канала передачи данных (ГКПД). При этом на входе дуги находится кодо­ вая комбинация из множества рабочих комбинаций кода {Л,-}, а на выходе дуги - кодовая комбинация, наблюдаемая на выходе канала. Это могут быть либо кодовое слово из {А; } при правильной передаче или трансфор­ мации сообщения, либо кодовое слово из множества запрещенных комби­ наций кода {B i} при искаженной передаче. Ребро ГКПД нагружено соот­ ветствующим значением вектора ошибки.

Пример 33. Пусть М0= М= 2*\ ГКПД показан на рис. 3.1.

(At) fBj}

000

001

010

O il

100§=(000)

б= (0 0 1 )--------

101(010)

110

111

Рис. 3.1. ГКПД при передаче сообщений неизбыточным кодом п = 3

Из рис. 3.1 видно, что т. к. М0 - М = 0, то подмножество {В( } - пус­ тое, и, следовательно, любая ошибка вызывает трансформацию сообщения, т.е. является необнаруженной. Действительно, если передается кодовый вектор (кодовая комбинация) Л4 = V4 = 100, то искажение (ошибка) в лю­ бом разряде вызывает переход в одну из разрешенных комбинаций и полу­ чателю выдается другое сообщение.

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

Корректирующие свойства кода могут быть направлены на два вида действий:

•исправление ошибок;

•обнаружение ошибок.

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

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

Из рис. 3.3 видно, что при передаче сообщений кодом, обнаружи­ вающим ошибки, имеют место три события: правильная передача (неис­ каженная), трансформация сообщения, вызываемая необнаруженной ошибкой, и стирание сообщения, вызываемое обнаруженной ошибкой. Обнаружение ошибки происходит при появлении на выходе ДСК (на входе декодера) запрещеной комбинации. Доля обнаруживаемых ошибок равна

М о-М р

---------- -, т. е. совпадает с избыточностью кода.

М 0

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

Ш<Bj}

Рис. 3.4. ГКПД при передаче сообщений избыточным кодом п - 3, обнаруживающим ошибки нечетной кратности

Разобьем полное множество комбинаций на два непересекающихся множества: множество рабочих комбинаций Мр и множество запрещенных комбинаций Мг. Для первичного кодирования будем использовать только рабочие комбинации А,.

Размерность каждого из множеств равна 4, следовательно,

А/0 =Л/р +М г =4 + 4 = 8.

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

А3100—- —►ООО.в, е М 3,

Л3100—^-И 10В 4 еМ „

А3100— »1012?з е М 3.

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

Для исправления ошибки характеристик кода недостаточно. Дейст­ вительно, любую из комбинаций Bj можно получить в результате ошибки одинаковой кратности в разных рабочих кодовых комбинациях. Например, комбинацию В\ можно получить в результате однократной ошибки ех в Л3,

е2в Л2и л и е3вА\.

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

Избыточность построенного кода оценивается, как Rx = 0,5; /?п= 0,33. Минимальное кодовое расстояние </min = 2. Код обнаруживает любые ошибки нечетной кратности. Ошибки четной кратности не обнаруживают­ ся, т.е. вызывают трансформацию сообщений. Можно ввести параметр г как кратность обнаруживаемых ошибок, т.е. код гарантирует обнаружение ошибок кратности не более г.

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

Сообщение будет принято правильно, если ошибок в кодовой комбинации нет (вероятность этого события Рпр). Все ошибки кратности не более г будут обнаружены, и сообщение будет стерто (вероятность этого события Яст). Если кратность ошибок превысит г, то произойдет трансфор­ мация сообщения (вероятность этого события Р^).

Запишем сформулированные условия:

Для построения кода, исправляющего ошибки, необходимо полное множество М0 комбинаций кода разбить на М непересекающихся подмно­ жеств так, что

" р

М 0 = Е ( ^ + 1 ) , (3.12) /=1

где Li - мощность /-го подмножества запрещенных комбинаций; L, + 1 - мощность подмножества, включая /-ю рабочую комбинацию; данное под­ множество называют сигнальной зоной (сферой) /-й рабочей комбинации.

правляемых ошибок.

Таким образом, разбиение типа рис. 3.5 удовлетворяет следующим условиям:

Способ приема состоит в том, что если принята некоторая комбина­ ция из /-го подмножества, то декодером выносится решение о том, что пе­ редана комбинация Таким образом, исправляется та часть всевозмож­ ных ошибок, под действием которых /-я рабочая комбинация (Af) не выхо­ дит за пределы /-й сигнальной зоны. При этом знак равенства в (3.13) озна­ чает, что построен код, исправляющий ошибки, так называемый «плотноупакованный»; знак < означает, что корректирующая способность кода ис­ пользована либо для исправления ошибок, либо для исправления и обна­ ружения ошибок. Доля исправляемых ошибок, в предположении, что все

м р 1 L 1

рабочие комбинации равновероятны, составляет ]Г-------------1-----= ----- • wA/p М р

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

т.е. ошибки малой кратности более вероятны, чем ошибки большой крат­ ности. Поэтому в /-ю сигнальную зону включаются запрещенные комби­ нации Bt, удаленные от А{ на наименьшее кодовое расстояние по сравне­

3.5. Исправление и обнаружение ошибок избыточными кодами

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

Пример 3.6. Построим код длины /1 = 4, исправляющий однократные и обнаруживающий двукратные ошибки.

На рис. 3.7. приведен код с d(Al9A2) = 4, исправляющий все одно­ кратные и обнаруживающий все двукратные ошибки, и ГКПД, иллюстри­ рующий процесс передачи информации указанным кодом. Построенный код является плотноупакованным. В КПД имеют место 3 события: пра­ вильная передача сообщений, стирание и трансформация. Правильная пе­ редача имеет место как при их отсутствии ошибок, так и при любой одно­ кратной ошибке. Стирание происходит при двукратной ошибке. Из рис. 3.7 видно, что построенный код исправляет любую однократную ошибку, т. к. запрещенная комбинация не выходит из сигнальной зоны соответствую­ щей рабочей комбинации, искаженной однократной ошибкой попутно. Двукратные ошибки также будут обнаружены, поскольку переведут рабо­ чую комбинацию во множество запрещенных состояний Мг.

Мг

Г • 0110

•ООП

• 1001

•0000

• 1111

^ • 1100

Рис. 3.7 Структура избыточного кода п- 4, исправляющего однократные и обнаруживающиего двукратные ошибки и ГКПД

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

Минимальное кодовое расстояние <4™ = 4.

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

Будем сичтать, что сообщение будет принято правильно, если ошибок в кодовой комбинации нет или кратность ошибок не превышает S, и они будут исправлены (вероятность этого события Рп^). Все ошибки кратности более S и менее г будут обнаружены, и сообщение будет стерто (вероятность этого события Рсг). Если кратность ошибок превысит г, то произойдет трансформация сообщения (вероятность этого события Р1р).

Запишем сформулированные условия:

0 < w(e) < S - правильная передача сообщения,

1S < w(e) < г~ стирание сообщения,

w(e) > г - трансформация сообщения.

Вероятностные соотношения выглядят следующим образом:

р ‘ ( \ - р У

v /

Как видно из приведенных соотношений, вероятность транс­ формации уменьшается из-за исправления ошибок (увеличения вероятности правильной передачи) и появления вероятности стирания (обнаружения ошибок).

3.6. Геометрическая модель кода

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

Пример 3.7. Рассмотрим геометрическую модель 3-разрядного дво­ ичного кода (рис. 3.8).

Геометрической моделью является 3-мерный куб, каждая из 8 вер­ шин которого соответствует кодовой комбинации двоичного неизбыточно­ го кода. Кружками обведены вершины куба, соответствующие рабочим комбинациям кода, обнаруживающего ошибки из примера 4.4. Каждое ребро куба соответствует расстоянию Хемминга d = 1. На модели видно, что для кода, обнаруживающего ошибки, минимальное расстояние между рабочими комбинациями равно двум (</min~ 2).

Из рис. 3.8 видно, что кодовое расстояние между вершинами куба, соответствующими рабочим комбинациям 101 и 010 (пример 3.5), равно 3.

Рис. 3.8. Геометрическая модель 3-разрядного двоичного кода

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

3.7. Связь между кодовым расстоянием Хемминга и максимальной кратностью обнаруживаемых и исправляемых ошибок

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

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

Сформулируем и докажем ряд утверждений.

Утверждение 3.1. Для того чтобы код обнаруживал любые ошибки кратности г и меньше, минимальное кодовое расстояние должно удовле­ творять условию

(3.17)

Краткое доказательство. Как было показано в подразд. 3.3, сиг­ нальные зоны кода, обнаруживающего ошибки, состоят только из рабочих комбинаций кода. Таким образом, если между комбинациями кода рас­ стояние не меньше г + 1, то не существует никакой ошибки кратности г и меньше, которая перевела бы одну комбинацию кода в сигнальную зону другой (для этого потребуется, по крайней мере, ошибка кратности (г + 1)). Следовательно, все ошибки кратности г и меньше будут обнаружены.

Пример 3.8. Пусть г = 1, поэтому dm\n=1 + 1=2 . Рассмотрим гео­ метрическое представление кода (рис. 3.9).

Рис. 3.9. Геометрическая иллюстрация обнаружения ошибки кратности г = 1

Рабочие комбинации К, и Vj имеют dij= dmт = 2, а кодовое расстояние до любой из комбинаций множества Л/3 равно d = 1. Поэтому при любой однократной ошибке будет принята кодовая комбинация из Л/3. Это даст возможность обнаружить однократную ошибку. При двукратной ошибке вместо одной рабочей комбинации Vt будет принята другая рабочая ком­ бинация Vj. Это приведет к трансформации сообщения.

Код с */mjn = 2 был рассмотрен в примере 3.4, из которого видно, что не существует ни одной ошибки нечетной кратности, способной вызвать трансформацию (см. рис. 3.4), т.к. любая такая ошибка переведет рабочую комбинацию кода в запрещенную и будет обнаружена. Но так как двукрат­ ные ошибки при этом обнаружены не будут, то код с tfmin= 2 в соответст­ вии с утверждением 3.1 гарантирует обнаружение однократных ошибок.

Пусть г = 2, поэтому dm\n = 2 + I = 3 . Рабочие комбинации К, и Vj имеют dy = dmj„ = 3, а кодовое расстояние d до любой из комбинаций мно­ жества Мг равно 1 или 2. Поэтому при любой однократной или двукратной ошибке будет принята кодовая комбинация из М2. Это даст возможность обнаружить такие ошибки. При трехкратной ошибке вместо одной рабочей

комбинации Vi будет принята другая рабочая комбинация Vh Это приведет к трансформации сообщения.

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

Утверждение 3.2. Для того чтобы код исправлял любые ошибки кратности s и меньше, минимальное расстояние должно удовлетворять ус­ ловию

4m . ^ 2 s + 1. (3.18)

Краткое доказательство. В сигнальную зону каждой рабочей ком­ бинации кода, кроме рабочей комбинации, входят еще запрещенные ком­ бинации, удаленные от рабочей на расстояние 5 и меньше. Согласно усло­ вию (3.13) сигнальные зоны не должны пересекаться. Для обеспечения этого условия достаточно соблюдение (3.18), т. к. непересекающиеся сиг­ нальные зоны каждой рабочей комбинации разделяются по крайней мере одним кодовым переходом. Таким образом, при соблюдении (3.18) любая ошибка кратности s и меньше не способна перевести передаваемую рабо­ чую комбинацию в чужую сигнальную зону и, следовательно, в соответст­ вии с правилом принятия решения (п. 3.4) будет исправлена.

Пример 3.9. Пусть s = 1, тогда согласно (3.18) dmin = 3. В примере 3.5 рассмотрен подобный код. Из рис. 3.6 и 3.8 видно, что dmin = 3 гаранти­ рует соблюдение условий (3.18), т. е. сигнальные зоны (СЗ) двух рабочих комбинаций кода не пересекаются. Каждая сигнальная зона состоит из всех возможных запрещенных комбинаций, удаленных от рабочей на d - 1, что соответствует однократным искажениям, и, значит, любая однократная ошибка будет исправлена.

Рассмотрим геометрическое представление кода (рис. 3.10).

СЗ/ СЗ,

Рис. ЗЛО. Геометрическая иллюстрация исправления ошибки кратности s = 1

Рабочие комбинации К, и V) имеют dy = */mm = 3, а кодовое расстояние до любой из комбинаций собственной сигнальной зоны СЗ равно d = S= 1. Поэтому при любой однократной ошибке будет принята кодовая комбина­ ция из СЗ. Это даст возможность исправить ошибку, заменив комбинацию из СЗ на соответствующую ей рабочую комбинацию. При двукратной ошибке будет принята комбинация из сигнальной зоны другой рабочей комбинации. Это приведет к исправлению другой рабочей комбинации

и, соответственно, трансформации сообщения. Таким образом, код с dmm= 3 гарантирует исправление однократной ошибки.

Распространив приведенные соображения по закону математической индукции для произвольного значения s, можно считать утверждение до­ казанным.

Утверждение 3.3. Для того чтобы код исправлял ошибки кратности s и обнаруживал ошибки кратности от s + 1 до г (s < г), минимальное рас­

Краткое доказательство. Проанализированная в утверждении 3.2 конструкция сигнальных зон кода, исправляющего 5-кратные ошибки, со­ гласно условию (3.19) требует расстояния между сигнальными зонами, равного по крайней мере 25 + 1.

Пусть г = 5 + А (А > 1). Тогда (3.19) гарантирует выполнение требо­ вания (3.18), т.е. ошибки кратности s и меньше будут исправлены. При этом ошибки кратности 5 < г ' < г = 5 + Д (Д > 1) порождают запрещенные комбинации кода, не принадлежащие ни одной сигнальной зоне. Они уда­ лены от соответствующей рабочей комбинации на кодовое расстояние больше 5 , в то же время они не переведут рабочую комбинацию в чужую сигнальную зону, т. е. будут обнаружены.

Пример ЗЛО. Пусть s = 1, г = 2, тогда dmi„ = 4.

Изобразим фрагмент геометрической модели кода, состоящий из двух рабочих комбинаций: Vt и V);, таких, что d(Vt ,F; ) = 4 (рис. 3.11).

Рис 3.11. Фрагмент геометрической модели кода с dm;„= 4

Образуем сигнальные зоны, удовлетворяющие условию (3.13), т.е. непересекающиеся и состоящие из рабочей комбинации и запрещенных комбинаций, удаленных от рабочей на d = 1. Следовательно, такой код ис­ правляет любую однократную ошибку. В то же время любая двукратная ошибка переведет V{ или V в запрещенную комбинацию из множества Af3,

отличного от обеих сигнальных зон. Применив процедуру оптимального декодирования и установив, что d(V^^M 3) = 2, можно обнаружить ошибку и стереть сообщение.

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

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

В зависимости от минимального кодового расстояния корректирую­ щая способность кода может быть перераспределена на разные действия.

4ошибки (г = 2),

•обнаружение трехкратной ошибки (г = 3),

•исправление двукратной ошибки (s = 2),

5• исправление однократной (5 = 1) и обнаружение трехкратной ошибки (г = 3),

• обнаружение четырехкратной ошибки (г = 3).

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

3.8. Верхние и нижние границы избыточных кодов

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

3.8.1.Верхняя граница Хемминга

Проанализируем соотношение (3.13). Если принять, что

то указанное соотношение можно записать в виде MpL < М0- М р. Обозначим через Е полное множество исправляемых ошибок. Тогда

имеет место Е = L. Подставляя (3.1) и (3.2) в (3.20), получим

Поскольку s - максимальная кратность исправляемых ошибок, то для двоичных л-разрядных кодов, исправляющих ошибки,

Подставляя (3.22) в (3.21), получим окончательный вид границы Хемминга для двоичных кодов:

i + s i

Напомним, что т - число информационных символов кода, п - об­ щее число символов (разрядов) кода, называемое длиной кода, к = (и - т) - число избыточных символов кода. Поделив левую и правую части нера­ венства (3.23) на 2п\ получим другой вид границы Хемминга:

Неравенства(3.23) и (3.24) при заданных т ns решаются подбором. Пример 3.11. Найти параметры кода, исправляющего однократную

ошибку, для передачи М= 11 сообщений.

Найдем т = [log 11] = 4; s = 1. Тогда из (3.23) получим

24 — .

1 4- П

Пример 3.13. Пусть т = 4, dmin = 3. Тогда из (3.25) получим

п ♦16 = п ♦0,533 и л > 5,625. Выбираем ближайшее большее целое чис­ Т ч 5

ло п = 6, тогда согласно (3.25,а) тхгах < 4 и Л > 2.

Таким образом, из границы Плоткина следует, что не существует ко­ да, исправляющего однократные ошибки, с числом избыточных символов к меньше 2 и общей длиной кода меньше 6. Действительно, ближайший существующий код с максимальной скоростью передачи имеет параметры п = 7, к = 3. Но данный пример подтвердил, что граница Плоткина дает лучшие оценки, чем граница Хемминга, при малых RH. Данный пример подтверждает, что граница Плоткина не является границей существования. В работе [10] показано, границы Плоткина достигают лишь коды, в кото­ рых расстояние между любыми двумя различными кодовыми словами од­ но и то же; такие коды называются эквидистантными. Например, двоич­ ными эквидистантными кодами являются коды, состоящие из последова­ тельностей максимальной длины, и коды, получающиеся из матриц Адамара [10,11]. Наряду с рассмотренными верхними границами существует еще граница Элайеса, которая лучше обеих рассмотренных границ, по

крайней мере при средних скоростях /?и = —. Граница Элайеса нами не

п

рассматривается.

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

3.8.3. Нижняя граница Варшамова-Гильберта

Как отмечалось выше, наряду с верхними границами существуют нижние кодовые границы, в частности граница Варшамова-Гильберта [12]. Сравнительный анализ этих границ показывает следующее. Верхняя гра­ ница утверждает, что не существуют коды с числом избыточных символов меньше определенного граничного числа к\. В то же время нижняя грани­ ца, в частности Варшамова-Гильберта, «гарантирует» существование ко­ дов с числом избыточных символов к2 меньше другого граничного числа:

к2> к\.

Нижняя граница Варшамова-Гильберта имеет вид

(3.26)

При этом утверждается, что существует (л,/и)-код с кодовым рас­ стоянием, не меньшим г/, и с числом избыточных разрядов к < п ~ т .

Пример 3.14. Оценим с помощью границы Варшамова-Гильберта параметры кода из примера 3.12, т.е. кода длины п = 63 с dmin = 5. Согласно

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

выводу: из границы Хемминга следует, что не существует кодов с к < 11, т.е, по Хэммингу, к > 11 (нижняя граница по избыточным символам и, сле­ довательно, верхняя граница по информационным символам), а граница Варшамова-Гильберта «гарантирует» существование кодов с к < 16 (верх­ няя граница по избыточным символам и, следовательно, нижняя граница по информационным символам).

3.9. Оптимальное декодирование с «жестким» и «мягким» принятием решения первой решающей схемой

В главе 2 описан поэлементный прием сигналов ПРО, получивший наибольшее распространение в современных цифровых телекоммуника­ ционных системах. ПРС может принимать «жесткое» и «мягкое» решение относительно элементарных сигналов на входе. Если мощность входного канального алфавита равна к, а мощность выходного канального алфавита к ’, то условно такой канал обозначим как (к х &')-канал. Тогда при «жест­ ком» принятии решения имеет место к = к' , а при «мягком»- к <к'

Мы будем рассматривать (2 х &')-канал, т. е. двоичный симметрич­ ный канал, у которого мощность выходного канального алфавита больше трех. Промежуточное место между поэлементным приемом с «жестким» принятием решений и «приемом в целом» занимает прием с «мягким» принятием решения. Было доказано, что в (2 х /г')-канале нецелесообразно делать к' больше 8, т. е. к ' <8 [12]. Поэтому ниже будет рассмотрен (2 х 8)-канал. Выигрыш в помехоустойчивости канала передачи данных,

L) и •1и и □ L in □ □□ П □Г1ПГ1 □п п П Г !П П Г »Г !П П □ П !'1□ □П П П □ □ [3Г □

н при «мягком» декодировании, по сравнению с «жестким» декодированием, объемом дополнительной информации о величине искаженного элементарного сигнала, поступающего на вход декодера.

3.9.1. Сигнальные зоны, реализуемые в ПРС (2 ж 8)-канала

Пусть ПРС реализует когерентный прием двух противоположных сигналов ± S(t) . В канале действует «белый шум» со спектральной плот­ ностью N0/ 2Вт/Гц. Оптимальным приемником является согласованный фильтр (СФ) с импульсной характеристикой g(t) = к s (Т - /), где Т -

длительность элементарного сигналаS ( t ) , на который настроен согласо­ ванный фильтр. Отсчеты сигналов на выходе СФ берутся с частотой сле­ дования сигналов и подаются на вход решающего (регистрирующего) уст­ ройства (РУ). В ПРС с «жестким» принятием решения РУ определяет знак отсчета, т. е. сигнальные зоны противоположных сигналов отслеживают только знак входного сигнала. В ПРС с «мягким» принятием решения сиг­ нал с выхода СФ подается на вход аналого-цифрового преобразователя с N уровнями квантования (N = 8). Таким образом, РУ принимает решение о величине сигнала на его входе, и на вход декодера передается одно из восьми соответствующих значений элементарного сигнала. Значения на­ пряжения на выходе СФ в моменты отсчетов являются гауссовскими слу­

дачи 1 или 0) и дисперсией с 2 = N0/2 (£*- энергия принятого элементарно­ го сигнала). Таким образом, плотность распределения вероятностей напря­ жения р = S + £, на выходе согласованного фильтра (рис. 3.12) имеет вид

Рис. 3.12. Плотность распределения вероятностей значения напряжения р = S + <Е,

Шкала квантования сигналов на выходе СФ равномерная с шагом кванто­ вания

где шj —весовой коэффициент.

3.9.2. Оптимальное декодирование в канале с «мягким» принятием решения

Для вычисления кодового расстояния в канале с «мягким» приняти­ ем решения введем метрику, отличную от (3.6):

В канале с «жестким» принятием решения по-прежнему пользуемся метрикой (3.6).

Алгоритм оптимального декодирования по критерию максимального правдоподобия, реализуемый декодером в канале 2 х 8 с «мягким» приня­ тием решения, таков:

1.В памяти декодера хранятся все (2м- 1)-векторов. При этом для двоичной записи каждого символа отводим по три ячейки памяти.

2.Для исправления ошибок при приеме вектора V 1 вычисляются по

формуле (3.31) кодовые расстояния (1(У\У{), где / = l,2m - 1 . Находится

отом, что передавался кодовый вектор Уу.

3.Для исправления и обнаружения ошибок при приеме вектора V повторяется процедура, описанная в п. 2. Если для некоторого Vv находит­

ся наименьшее кодовое расстояние среди всех вычисленных, то принима­ ется решение о том, что передавался вектор Уу. Если же хотя бы для двух хранимых кодовых векторов Уу и У^ вычисленные кодовые расстояния до

У' совпали, т. е. ^(У г,Уу)=с((У\У^), то сообщение ^'стирается.

Пример 3.16. Рассмотрим код с параметрами п = 7, т = 3, dm\n = 4. В двоичном симметричном канале с «жестким» принятием решения дан­ ный код исправляет однократные ошибки (некоторые сочетания двукрат­ ных ошибок - при оптимальном декодировании) и обнаруживает все дву­ кратные ошибки и ряд ошибок большей кратности. Проанализируем кор­ ректирующую способность этого же кода, но в канале 2 х 8 с «мягким» принятием решения (см. рис. 3.12 и 3.13). Представим два из семи векто­ ров рассматриваемого кода: У{ и У2 соответственно в каналах с «жест­ ким» и «мягким» принятием решения.

В канале 2 x2: У} = 1011100;К2 = 0101110.

При уверенном приеме (рис. 3.16) множество возможных значений информационных параметров сигнала разбивается на подмножества, коли­ чество которых совпадает с разновидностью символов (размерностью ал­ фавита на входе канала). Для двоичного канала связи таких подмножеств два: зона уверенного приема символа «О» и зона уверенного приема сим­ вола «1». Пороговое значение для принятия решения обычно определяется как UJ2.

При неуверенном приеме (рис. 3.17) добавляется зона, в которую по­ падают значения информационных параметров, которые нельзя отнести ни

кодному из символов. Она имеет границы от нижнего порога (С/Пн) до верхнего порога (£УПВ)- Попадание в зону неуверенного приема приводит

кзамене принятого символа на символ «х». Попадание в зону выше U* приводит к принятию решения о приеме символа «1». Попадание в зону ниже UnHприводит к принятию решения о приеме символа «О».

При уверенном приеме сигнала (символа) из линии связи на выходе ПРС, реализующей «жесткое» принятие решения, наблюдается один из двух символов: «О» и «1». При неуверенном приеме сигнала (символа) из линии связи на выходе ПРС, реализующей «мягкое» принятие решения, наблюдается один из трех символов: «О», «1», «х» (рис. 3.18).

Рис. 3.18. Прием и декодирование линейного сигнала S'(i) в канале со стиранием

Поскольку ошибка стирания обнаруживается уже на уровне ПРС, то для ВРС коррекция ошибок стирания сводится только к исправлению ошибок указанного вида. Количество стираний (символов <сс» в принятой кодовой комбинации) явно указывает кратность ошибок стирания.

Сформулируем несколько утверждений, связывающих избыточность (^min) и корректирующие свойства кода в канале со стиранием.

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

dm>n>eс+1. (3.36)

Краткое доказательство. Необходимо применить оптимальное де­ кодирование по критерию min кодового расстояния в уверенно принятых символах. Это означает, что нужно вычислить d({Kl},K') и принять реше­

ние в пользу того вектора Vt (/ = l,2m -1), для которого d(Vi>Vr) = 0. Это вы­

текает из условия, что в уверенно принятых символах отсутствуют ошибки перехода, следовательно, min {^(K/,F/)} = 0 (ошибки стирания исправлены).

Пример 3.17. Выберем избыточный код (7,3,4). J min = 4, поэтому со­ гласно (3.36) ес = 3. Проведем анализ для рабочих векторов V\ = 1110100 и V2 = 0111010. Пусть принят вектор V' = НдсссОО. Определяем кодовое расстояние по уверенно принятым символам: <ИУ\У) = 0, d(V2,V ) = 2. По результатам вычислений делаем вывод о том, что был передан вектор Vt.

Исправление ошибок стирания сводится к выбору правильного вари­ анта замены символов <сс». Аналогичные выводы позволяют сформулиро­ вать соотношения для кодов, исправляющих или обнаруживающих и ошибки перехода, и ошибки стирания.

Утверждение 3.5. Для того чтобы код обнаруживал любые ошибки перехода кратности г и меньше и исправлял любые ошибки стирания крат­ ности ес и меньше, минимальное кодовое расстояние должно удовлетво­

Краткое доказательство. Необходимо применить оптимальное де­ кодирование по критерию min кодового расстояния в уверенно принятых символах. Это означает, что нужно вычислить ^({^},^0 для уверенно при­ нятых символов и принять решение. Если присутствуют только ошибки

стирания, то решение принимается в пользу того вектора (/= l,2m-1), для которого d(V/iHr) = 0. Это вытекает из условия, что в уверенно приня­ тых символах отсутствуют ошибки перехода, поэтому min {d(V„V')} = 0. Если присутствуют и ошибки перехода, и ошибки стирания, то все вычис­ ленные кодовые расстояния будут больше нуля (d({F/}fF/) >0). По этому условию ошибки будут обнаружены, а сообщение стерто.

Пример 3.18. Выберем избыточный код (7,3,4). dmjn = 4, поэтому со­ гласно (3.37) г = 1 и ес = 2 (как один из вариантов). Проведем анализ для рабочих векторов V\ = 1110100 и У2 = 0111010. Пусть принят кодовый век­ тор У = 11*1*00. Определяем кодовое расстояние по уверенно принятым символам: d(V\,Vr) = 1, d(V2,Vr) = 2. По результатам вычислений делаем вы­ вод об обнаружении ошибок перехода и стирании сообщения.

Утверждение 3.6. Для того, чтобы код исправлял любые ошибки перехода кратности s и меньше и любые ошибки стирания кратности ес и меньше, минимальное кодовое расстояние должно удовлетворять условию

Краткое доказательство. Необходимо применить оптимальное де­ кодирование по критерию min кодового расстояния в уверенно принятых

символах. Это означает, что нужно вычислить d({Vi}>V) для уверенно при­ нятых символов и принять решение. Если присутствуют только ошибки

стирания, то решение принимается в пользу того вектора V/ (z = 1,2W-1), для которого = 0. Это вытекает из условия, что в уверенно приня­ тых символах отсутствуют ошибки перехода, поэтому min {d(VhV )} = 0. Если присутствуют и ошибки перехода, и ошибки стирания, то все вычис­ ленные кодовые расстояния будут больше нуля (rf({Pi},P0 >0). При этом выбирается минимальное кодовое расстояние (для исправления ошибок оно будет < s). По этому условию ошибки перехода будут исправлены, а сообщение передано получателю.

Пример 3.19, Выберем избыточный код (7,3,4). dm\n = 4, поэтому со­ гласно (3.38) s = 1 и ес= 1. Проведем анализ для рабочих кодовых векторов V) = 1110100 и У2 = 0111010. Пусть принят кодовый вектор V9= 1111*00. Определяем кодовое расстояние по уверенно принятым символам и полу­ чаем d(V!,*")= 1 = s, d(V2, y f) = 2 > s. По результатам вычислений делаем вывод об исправлении ошибок перехода и передаче правильного сообще­ ния получателю.

Утверждение 3.7. Для того чтобы код обнаруживал любые ошибки перехода кратности г и меньше, исправлял любые ошибки перехода крат­ ности s и меньше и любые ошибки стирания кратности ес и меньше, мини­

Декодирование кодов при наличии ошибок указанной кратности рас­ смотрено в примерах 3.17, 3.18, 3.19 отдельно, поэтому рассматриваться не будет.

Методы обеспечения помехоустойчивости на приеме в ПРС сводятся к оптимальному приему сигналов на фоне помех. Но для обеспечения вы­ сокой достоверности указанных методов явно недостаточно. Это объясня­ ется возможными искажениями в передаваемом по линии связи закодиро­ ванном сообщении. Обработка кодовых комбинаций происходит во второй решающей схеме. Поэтому методы обеспечения помехоустойчивости при обработке кодовых комбинаций во ВРС сводятся к применению специаль­ ных алгоритмов декодирования.

Контрольные вопросы к главе 3

1. Привести выражения и сравнить способы оценки избыточнос (/?ь /?„), привести примеры: а) М0= 16, Мр= 8; б) Л/0 =16, Л/р = 3.

2.Ввести понятия «кодовый вес», «кодовое расстояние» («расстоя­ ние Хэмминга»), «кратность ошибки», привести примеры их вычисления. Рассмотреть аддитивную модель воздействия ошибок на кодовый вектор

вдискретном канале связи, привести примеры искажения кодового вектора для ошибок кратности е = 1, 2,3.

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

ятностные характеристики.

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

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

скратностью исправляемых ошибок перехода.

8.Привести примеры использования корректирующих свойств кода

Д Л Я ^niin “ 6 И l/rnin ~ 7.

9.Проанализировать верхние и нижние границы избыточных кодов.

10.Рассмотреть оптимальное декодирование в двоичном канале со стиранием, привести вероятностные характеристики.

11. Проанализировать связь минимального кодового расстояния с кратностью корректируемых ошибок перехода и стирания.