М Вернер Основы кодирования Основы кодирования. Учебник для ВУЗов. Техносфера, 2004. - 288с. ISBN 5-94836-019-9 Первое на русском языке массовое пособие для будущих инженеров-связистов и проектировщиков радиоэлектронной аппаратуры, включая системы на кристалле. Даны основы теории информации и сжатия данных, доходчиво изложены современные алгоритмы помехоустойчивого кодирования, реализации циклических и сверточных кодов.

Braunschweig/Wiesbaden © 2004, ЗАО «РИЦ «Техносфера» перевод на русский язык, оригинал-макет, оформление. ISBN 5-94836-019-9 ISBN 3-528-03951-5 (нем.) Предисловие Реформация и кодирование - два основных понятия современной информационной техники. Информация в техническом смысле это­го слова и методы защиты информации от ошибок, возникающих в результате передачи сообщений, являются сегодня основой при под­готовке специалистов, работающих в области информационных тех­нологий.

В данной книге предпринята попытка изложить эти осно­вы в компактной форме. «Информация и кодирования» базируется на курсе лекций, прочитанных в четвертом семестре на факультете «Электротехника и информационная техника» университета г. Фулда. В первой части вводятся понятия информации, энтропии и избы­точности.

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

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

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

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

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

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

В свя­зи с этим, особую ценность для понимания представляет подробный разбор примеров и решений заданий с привлечением всего учебного материла. Я желаю учащимся успешного овладения книгой «Инфор­мация и кодирование». Мартин Вернер Часть I. Информация и кодирование Глава I. Введение Теория информации описывается с помощью вероятностных диа­грамм кодирования и передачи информации в конкретных, естествен­но - научных приложениях.

При этом появляется возможность для анализа и оптимизации потоков информации в технических систе­мах. Отделить техническое представление информации от бытово­го могут помочь лингвистические понятия: синтаксис, семантика и прагматика. В этих понятиях синтаксис и семантика являются ана­логом технических данных. Синтаксис определяет все допустимые символы и последовательности символов. Семантика объясняет их значения.

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

• Синтаксис + семантика → Данные. • Данные + прагматика → Сообщение. Основой дальнейших рассуждений является понимание информа­ции, как некоторой, экспериментально устанавливаемой величины. Толчком к этому послужила работа Клода Шеннона «Математиче­ская теория связи» [1], опубликованная в 1948 г. В ней К. Шеннон дал определение понятий современной теории информации и набро­сал основы сегодняшней техники связи.

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

Здесь для описания меры ин­формации напрашивается логарифмическая функция, которая даст ожидаемое удвоение: Общая модель связи по К. Шеннону приведена на рис. 1.1. Рис. 1.1. Модель передали информации по каналу связи но К. Шеннону. Исходным пунктом является источник информации. Его сообще­ния поступают на передатчик. При этом, сообщения могут представ­лять собой отдельные буквы связанного текста, значения функций времени, функции изменения напряжения на выходе микрофона, те­левизионные сигналы и т.д.

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

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

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

Кодирование каналов, наоборот, увеличивает избыточность сообщений. Внесение дополни­тельных проверочных символов позволяет обнаруживать и даже ис­правлять ошибки, возникающие при передаче информации по кана­лу. Кодирование капала в дальнейшем мы будем называть помехо­устойчивым кодированием. Без помехоустойчивого кодирования бы­ло бы невозможным создание накопителей огромной емкости, таких, как CD-ROM, DVD или жестких дисков. Дополнительные затраты на помехоустойчивое кодирование, которое обеспечивает приемле­мые вероятности ошибок записи/чтения, становятся пренебрежимо малыми по сравнению с выигрышем от достигаемой при этом плот­ности записи.

Рассмотренные примеры показывают, что информа­ция и кодирование являются центральными понятиями, без которых современная -информационная техника просто не существовала Бы. Следующие главы углубят эти понятия и их приложения. Глава 2. Информация, энтропия и избыточность 2.1. Информация одного события Обмен информацией, несмотря на свою нематериальную природу, является неотъемлемой частью нашей жизни. Норберт Виннер, один из основателей современной теории информации, охарактеризовал информацию следующим образом [9|: «Информация есть информация, а не материя или энергия».

Согласно Н. Виннеру, информация является новым элементом в дополнении к материи и энергии. Информация для людей настолько же важна, насколько трудно представить себе это понятие в есте­ственнонаучной форме. Мы говорим, например: «Эта информация для меня важна», имея в виду некоторую конкретную ситуацию. Та­кое субъективное восприятие не подходит для технического пред­ставления информации.

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

Проводя такие эксперименты, мы наблюдаем случайные события и это снижает неопределенность системы. Переходим к самой сущности теории информации. Прежде всего дадим определение простейшего источника, а затем введем понятие количества информации, как измеряемой величины для того, чтобы с ее помощью охарактеризовать источник.- Дискретный источник без памяти Простейший дискретный источник без памяти, X в каждый фик­сированный момент времени выдает некоторый символ X i из конеч­ного алфавита, X = 1 ,х 2 .

x k > с вероятностью Р(х i ) = р i . Выборки символов производятся независимо друг от друга. В качестве простейшего примера можно привести двоичный ис­точник без памяти с алфавитом X = 1 = 0, x 2 = 1> и вероят­ностями и Р 2 = 1 — р 1 . Выбор очередной цифры про­изводится независимо от прежних и последующих выборок. Изоб­ражение простейшего источника приведено на рис. 2.1. Рассмотрим вначале одиночные события. Повседневный опыт подсказывает, что часто происходящие события, так же как и их вероятности, дают нам мало информации.

Возьмем, например, сообщение «собака укусила человека». Это привычное известие не привлекло бы к себе никако­го внимания, в то время, как сообщение «человек укусил собаку» все газеты напечатали бы крупным шрифтом. Из этого можно сде­лать вывод: частые, ожидаемые события несут мало информации и, наоборот, редкие, т.е.

неожиданные события, обладают высоким ин­формационным содержанием. Следовательно, информация и вероят­ность находятся в обратно пропорциональной зависимости. Исходя из этого, введем понятие количества информации, как измеряемой величины на основании следующих трех аксиом [1]. Рис. 2.1. Простейший источник информации ал­фавита X . Аксиомы для определения количества информации [1] 1.

Информация одиночного события Xi £ X , происходящего с ве­роятностью pj, имеет положительное значение 2. Совместная информация двух независимых событий ( x ,, Xj ) с совместной вероятностью , равна сумме их информации 3.

Информация является непрерывной функцией от вероятности события. Аксиомы 1 и 2 утверждают, что информация нескольких событий не может взаимно уничтожаться. Аксиома 2 вводит понятие совмест­ной информации событий.

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

Возможны сле­дующие обозначения двоичного логарифма: где под ld подразумевается термин дуальный логарифм, а под lb -бинарный.* Иногда используют натуральный логарифм с единицей измерения нот, но можно использовать любую единицу измерения информации. Можно также переходить от одной единице к другой, применяя формулу пересчета: * В отечественной математической литературе для обозначения двоичного и на­турального логарифма принято использовать log. и ln. - Прим, перев. Размерность бит используется в информационной технике при двоичной системы исчисления.

Как будет показано в следующих раз­делах, двоичная система очень удобна при описании процесса приня­тия решения, когда на любой вопрос существует только два ответа: «да» или «нет». В [10] приведена наглядная интерпретация понятия «бит». Рис. 2.2. Информация символа I (р) с вероятностью появ­ления р. На рис. 2.2 показано поведение информации как функции вероят­ности. Информация постоянно происходящего события равна нулю. С ростом неопределенности информация также растет и для невоз­можного события стремится к бесконечности.

Таким образом, ин­формация соответствует всем приведенным ранее рассуждениям и удовлетворяет аксиомам 1 3. С точки зрения теории вероятности, определение информации можно рассматривать как некоторое отоб­ражение событий.

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

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

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

2.1. Информация источника представля­ет собой результат эксперимента со случайными событиями a . b . c . d . Пусть в результате повторения этого эксперимента мы получаем по­следовательность Подставив на место каждого события его информацию, получим типичную функцию стохастического процесса Предположим эргодичность (постоянство поведения) такого про­цесса во времени.

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

В рассмотренном примере математическое ожидание Е( I ) равно 1,75 бит. Из первых 12 испытаний мы также получаем оценку для I ( n ) 1,75 бит. Проводя аналогичные рассуждения, Шеннон [1] заложил в опре­деление энтропии три следующие аксиомы. Аксиоматическое определение энтропии 1. Энтропия Н(Х) = f ( p 1 , p 2 . p n ) является непрерывной функ­цией вероятностей 2. Для источников с одинаковой вероятностью событий энтропия увеличивается с ростом числа событий N.

3. Разложение процедуры выбора событий на несколько этапов не изменяет энтропию (процедуру выбора можно свести к последо­вательным двоичным решениям). Пример . Разложение процедуры выбора. Данный пример поясняет аксиому 3. Рассмотрим три события а, b и с, которые происходят с соответственными вероятностями 1/2,1/3 и 1/6. Для того, чтобы выбрать одно из этих трех, мы можем поста­вить два независимых вопроса (рис.

2.3). Рис. 2.3. Разложение процесса выбора символов. На эти вопросы могут быть даны только два ответа: или «да» или «нет».

Согласно аксиоме (3), к энтропии предъявляется следующее требование: причем, второй вопрос задается с вероятностью 1/2. Мы покажем в общем виде (рис. 2.4), что определение энтропии (2.8) удовлетворяет требованию аксиомы (Н3). Рис. 2.4 . Разложение процедуры принятия решения. Для разложенной энтропии получаем где вероятности определяются следующим образом Замечание.

Последнее, равенство подтверждается, постановкой экс­перимента со случайными событиями. Пусть событие и произошло 300 раз, событие, b - 200, а событие с - 100 раз. Частота каждого события в данном примере, равна ego вероятности. Если мы отбро­сим событие а, то останется 300 выборок событий b и с, частоты выборок этих событий удвоятся, но их отношение не изменится. Из (2.11)- (2.13) следует, что вероятности на втором шаге можно выразить как Подставляя полученные выражения в формулу для энтропии, имеем что после упрощений соответствует энтропии без разложения про­цесса выбора событий В рассмотренном примере было использовано свойство логариф­мической функции, переводящее произведение и сумму.

Определение (2.4) является единственным, при котором аксиома 3 имеет силу. Заметим также, что рассмотренное разложение процесса выбора со­бытий может быть сведено к последовательности бинарных решений «да» и «нет». Максимальной неопределенности соответствует макси­мальная энтропия источника. Сформулируем следующую теорему: Теорема 2.2.1 . Энтропия простейшего дискретного источника без памяти максимальна, если все события, в нем содержащиеся, име­ют одинаковую вероятность.

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

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

Рис. 2.5. Верхняя оценка логарифмической функции. Доказательство. Для доказательства рассмотрим два дискретных источника без памяти Р и Q , каждый из которых содержит N со­бытий с вероятностями p i и q i соответственно.

Далее воспользуемся известной верхней оценкой логарифмической функции ( рис. 2.5) Используя эту оценку, получаем Умножив обе части неравенства на р i и просуммировав по всем со­бытиям , имеем После упрощения получаем и, следовательно Предположим, что источник Q содержит только равновероятные со­бытия. Тогда Так как в процессе доказательства на источник Р не было наложено никаких ограничений, то данное неравенство имеет место для любого дискретного источника без памяти, содержащего N событий Максимум достигается, когда все события имеют одинаковые веро­ятности.

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

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

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

Пусть задан двоичный источник без памяти с алфавитом X = и с вероятностями для символов «0» и «1» - р 0 = p и р 1 = 1— p 0 соответственно. Выбор символов производится независимо. Его энтропия, называемая также функцией Шеннона, зависит только от вероятности р. Энтропия двоичного источника (функция Шеннона) На рис. 2.6 показано поведение функции Шеннона. Энтропия дво­ичного источника всюду положительна и симметрична относительно р = 1/2 и имеет максимум при одинаковой вероятности символов «0» и «1».

Максимальная энтропия равная 1 бит соответствует двоично­му решению, т.е. на вопрос о значении символа это ответ: либо «да» либо «нет».

Рис. 2.6. Энтропия двоичного источника.