Учебное пособие по дисциплине СиСПИ

Пусть, например, избыточность источника велика, т. е.

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

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

40

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

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

чивым, или корректирующим..

При помехоустойчивом кодировании чаще всего считают, что избыточность источника на входе кодера R=0. Для этого имеются следующие основания: во-первых, очень многие дискретные источники (например, информация на выходе ЭВМ) обладают малой избыточностью; во-вторых, если избыточность первичных источников существенна, она обычно порождается сложными связями, которые в месте приема трудно использовать для повышения верности. Разумно поэтому в таких случаях по возможности уменьшить избыточность первичного источника путем эффективного кодирования, а затем методами помехоустойчивого кодирования внести такую избыточность в сигнал, которая позволит достаточно простыми средствами поднять верность. Из сказанного видно, что экономное кодирование вполне может сочетаться с помехоустойчивым.

Коды можно классифицировать по различным признакам. Одним из них является основание кода q, или число различных используемых в нем символов. Наиболее простыми являются двоичные (бинарные) коды, у которых q = 2.

Далее коды можно разделить на блочные и непрерывные. Блочными называют коды, в которых последовательность элементарных сообщений источника разбивается на отрезки и каждый из них преобразуется в определенную последовательность (блок) кодовых символов {bi}, называемую кодовой комбинаци-

41

ей или кодовым словом bi (i=1, 2, 3, ..., n-1). Непрерывные коды образуют последовательность символов {bi}, не разделяемую на последовательные кодовые комбинации: здесь в процессе кодирования символы определяются всей последовательностью элементов сообщения.

В настоящее время на практике чаще используют блочные коды, равномерные и неравномерные. В равномерных кодах, в отличие от неравномерных, все кодовые комбинации содержат одинаковое число символов (разрядов), передаваемых по каналу элементами сигнала неизменной длительности. Это обстоятельство существенно упрощает технику передачи и приема сообщений и повышает помехоустойчивость системы синхронизации. Число различных блоков М n-разрядного равномерного кода с основанием q удовлетворяет очевидному неравенству

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

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

42

ственную информацию (энтропию), приходящуюся на каждый блок.

В дальнейшем будем рассматривать главным образом двоичные коды (q = 2).

1.4.2 Неравномерные эффективные коды

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

При построении неравномерного кода необходимо обеспечить однозначность декодирования. Поясним это простым примером. Пусть алфавит источника содержит шесть сообщений, которые обозначим А, Б, В, Г, Д, Е, передаваемых независимо друг от друга с вероятностями P(А) =0,4; Р(Б)=0,3;

Р(В)=0,1; Р(Г) =0,08; Р(Д)=0,07; Р(Е)=0,05. Сумма этих вероят-

ностей, конечно, равна 1. Заметим, что энтропия этого источника

где i=l, ..., 6- -номер сообщения в алфавите источника. Чтобы закодировать эти сообщения равномерным двоич-

ным кодом, нужно затратить на каждое сообщение три символа. В соответствии с теоремой кодирования для источника эти сообщения можно закодировать двоичными символами так, чтобы в среднем на каждое сообщение затрачивать ncp = 2,16+ двоичных символов, где е — сколь угодно малое положительное число. Попробуем сделать это, не задумываясь над однозначностью декодирования, попросту присваивая наиболее вероятным символам наиболее короткие блоки, например:

43

Таким образом, для передачи сообщений А и В, имеющих суммарную вероятность 0,7, используют один символ, а для передачи остальных сообщений, имеющих суммарную вероятность 0,3- два символа, так что среднее число символов на сообщение

Получилось, что сообщения закодированы еще более экономно, чем позволяет теорема кодирования. Но это объясняется тем, что выбранный код не пригоден для передачи сообщения, так как он не обеспечивает однозначного декодирования. Действительно, пусть принята такая последовательность символов:

00110100011110... (1.39)

Ее можно в соответствии с (1.37) декодировать так:

А А Б Б А Б А А А Б ... и т. д., или ВЕГВАЕБД ..., или АГДБВГББД ...,

и еще множеством различных способов.

Конечно, можно при коде (1.37) обеспечить однозначность декодирования, если после каждого сообщения передавать некоторый символ («запятую»), разделяющую сообщения. Но тогда это уже будет не двоичный код, а троичный. Так поступил

44

Морзе, создавая свой код, где кроме точки и тире использовал третий символ • «пробел».

Однако можно построить и однозначно декодируемые двоичные коды «без запятой». Для этого достаточно (хотя и не необходимо) строить код так, чтобы он удовлетворял так называемому «префиксному свойству». Оно заключается в том, что ни одно используемое кодовое слово не должно совпадать с началом («префиксом») другого кодового слова. Это свойство не выполнено у кода (1.37), так как, например, слово, соответствующее сообщению А, является началом слова, соответствующего сообщению В и т. д.

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

Алгоритм Фено заключается в следующем. Сообщения алфавита источника, записанные в порядке невозрастающих вероятностей, разделяются на две части так, чтобы суммарные вероятности сообщений в каждой из этих частей были по возможности почти одинаковыми. Сообщениям первой части приписывается в качестве первого символа 0, а сообщениям второй части

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

Для примера (1.37) на первом этапе разделения в первой части окажется одно сообщение А с вероятностью 0,4, а во второй части - остальные сообщения с суммарной вероятностью 0,6. Если бы включить в первую часть два сообщения (А и Б), то отклонение от равновероятности было бы еще больше. Припи-

45

шем сообщению А символ 0, а остальным сообщениям, в качестве первого символа -1.

На втором этапе разделим сообщения Б, В, Г, Д, Е на две равновероятные части, включив в первую часть сообщение Б, а во вторую часть — В, Г, Д, Е. Здесь суммарные вероятности для обеих частей одинаковы — по 0,3. Припишем сообщению Б в качестве второго символа 0, а остальным сообщениям — 1. На третьем этапе сообщения В и Г образуют одну часть, а сообщения Д и Е — вторую и т. д. В результате приходим к такому коду:

Этот код, как можно убедиться, по своему построению обладает префиксным свойством. Поэтому, например, последовательность символов (1.39) декодируется однозначно, а именно:

ААГАААЕА.

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

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

46

1.4.3 Принципы помехоустойчивого кодирования

Покажем, каким образом избыточное кодирование позволяет повысить верность передачи сообщения. Как отмечалось, для помехоустойчивых блочных равномерных кодов тп>М. Это значит, что для передачи знаков сообщения используют лишь часть возможных последовательностей, составленных из m- ичных символов (часть пространства n-последовательностей). Последовательности, используемые при кодировании, называются разрешенными кодовыми комбинациями, а все другие n- последовательности — запрещенными. На вход канала поступают только разрешенные комбинации. Если при передаче кодовой комбинации bi помехи не вызовут ошибок, то на выходе канала возникает та же разрешенная комбинация. Если же один или несколько символов принимается ошибочно, то на выходе канала может возникнуть одна из запрещенных комбинаций.

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

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

47

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

Из сказанного видно, что при избыточном кодировании возможны два основных метода декодирования — с обнаружением ошибок и с их исправлением. Сущность метода декодирования с исправлением ошибок заключается в том, что все множество B принимаемых последовательностей длины n разбивается на M не перекрывающихся подмножеств: В1,B2, ..., Вм. Если принята последовательность, принадлежащая подмножеству Вi, то считается, что передавалась кодовая комбинация bi. Естественно, что в подмножестве Вi следует включить те запрещенные комбинации bj,при приеме которых наиболее вероятной переданной комбинацией является bi.

При декодировании с обнаружением ошибок множество B разбивается на М+1 подмножеств, из которых В1,В2, ..., ВM содержат каждое по одной (разрешенной) кодовой комбинации, а подмножество Вм+1 — все остальные (запрещенные) комбинации. В некоторых системах связи принятая запрещенная комбинация просто отбрасывается и не поступает к получателю. Это обосновано в тех случаях, когда потеря переданного сообщения значительно менее вредна, чем получение ложного сообщения. Чаще при декодировании с обнаружением ошибки ошибочно принятая кодовая комбинация не теряется, а восстанавливается специальными методами. Среди них наиболее распространен метод переспроса.

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

48

висимости от свойств канала то или иное правило является предпочтительным.

Существуют и смешанные методы декодирования, когда некоторые ошибки исправляют, а другие только обнаруживают. Здесь множество В также разбито на М+1 подмножеств, но в подмножество В1 ..., Вм помимо разрешенных комбинаций входят и некоторые близкие к ним запрещенные (исправляемые), а в BM+1 — только те запрещенные комбинации, которые не могут быть достаточно надежно исправлены.

Говорят, что в канале произошла ошибка кратности q, если в кодовой комбинации q символов приняты ошибочно. Легко видеть, что кратность ошибки есть не что иное, как расстояние Хэмминга между переданной и принятой кодовыми комбинациями, или, иначе, вес вектора ошибки.

Рассматривая все разрешенные кодовые комбинации и определяя кодовые расстояния между каждой парой, можно найти наименьшее из них d = min d(i;j), где минимум берется по всем парам разрешенных комбинаций. Это минимальное кодовое расстояние является важным параметром кода. Очевидно, что для простого кода d=1.

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

Если код имеет d>l и используется декодирование по методу обнаружения ошибок, то все ошибки кратностью q<.d обнаруживаются. Что же касается ошибок кратностью q≥d, то одни из них обнаруживаются, а другие нет.

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

49