Вернер М. Основы кодирования (2004)

МИРпрограммированияМ. ВЕРНЕРОсновыкодирования.Учебник для ВУЗов.Перевод с немецкогоД . К. ЗигангироваРекомендовано ИППИ РАНв качестве учебникадля студентов, обучающихсяпо направлению"Прикладные математика и физика"ТЕХНОСФЕРАМоскваМ. ВернерОсновы кодирования. Учебник для ВУЗов.Москва:Техносфера, 2004. - 288с. ISBN 5-94836-019-9Первое на русском языке массовое пособие для будущих инженеровсвязистов и проектировщиков радиоэлектронной аппаратуры, включаясистемы на кристалле. Даны основы теории информации и сжатия данных,доходчиво изложены современные алгоритмы помехоустойчивого кодирования, реализации циклических и сверточных кодов.Informationund Codierungvon <rtol MMtnfberwrШ© 2002, Friedr. Vieweg & Sohn\ferlagsgesellschaft mbH,Braunschweig/Wiesbaden© 2004, ЗАО «РИЦ «Техносфера»перевод на русский язык,оригинал-макет, оформление.ISBN 5-94836-019-9ISBN 3-528-03951-5 (нем.)ПредисловиеИнформация и кодирование - два основных понятия современнойинформационной техники.

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

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

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

В связи с этим, особую ценность для понимания представляет подробныйразбор примеров и решений заданий с привлечением всего учебногоматерила. Я желаю учащимся успешного овладения книгой «Информация и кодирование».Мартин ВернерЧАСТЬ IИНФОРМАЦИЯиКОДИРОВАНИЕГЛАВА IВВЕДЕНИЕТеория информации описывается с помощью вероятностных диаграмм кодирования и передачи информации в конкретных, естественно - научных приложениях. При этом появляется возможность дляанализа и оптимизации потоков информации в технических системах. Отделить техническое представление информации от бытового могут помочь лингвистические понятия: синтаксис, семантика ипрагматика. В этих понятиях синтаксис и семантика являются аналогом технических данных. Синтаксис определяет все допустимыесимволы и последовательности символов. Семантика объясняет ихзначения.

Истинный смысл и область применения поясняются прагматикой. Прагматика связывает воедино такие понятия, как данные,техническая информация, информация в бытовом понимании этогослова. Окончательно, термин «информация», понимаемый обычнокак известие или руководство к действию, превращается в сообщение, которое должно быть передано.• Синтаксис I семантика —> Данные.• Данные f прагматика —» Сообщение.Основой дальнейших рассуждений является понимание информации, как некоторой, экспериментально устанавливаемой величины.Толчком к этому послужила работа Клода Шеннона «Математическая теория связи» [lj, опубликованная в 1948 г.

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

С другой стороны, можно было бы ожидать, что две перфокарты могут хранитьвдвое больше информации, чем одна. Здесь для описания меры информации напрашивается логарифмическая функция, которая даетожидаемое удвоение:log2 N = JVlog21og22N = 27V log 2.10Глава 1. ВведениеОбщая модель связи по К. Шеннону приведена на рис. 1.1.Источник1НЫХПередатчикПриемникСигналДанныеПолучатель1анных•ПLjJ Принятый*тсигналДанныеПомехиР и с . 1.1. Модель передачи информации по каналу связи поК. Шеннону.Исходным пунктом является источник информации. Его сообщения аоступают на передатчик. При этом, сообщения могут представлять собой отдельные буквы связанного текста, значения функцийвремени, функции изменения напряжения на выходе микрофона, телевизионные сигналы и т.д.

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

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

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

Без помехоустойчивого кодирования было бы невозможным создание накопителей огромной емкости, таких,как CD-ROM, DVD или жестких дисков. Дополнительные затратына помехоустойчивое кодирование, которое обеспечивает приемлемые вероятности ошибок записи/чтения, становятся пренебрежимомалыми по сравнению с выигрышем от достигаемой при этом плотности записи. Рассмотренные примеры показывают, что информация и кодирование являются центральными понятиями, без которыхсовременная информационная техника просто не существовала бы.Следующие главы углубят эти понятия и их приложения.ГЛАВА 2ИНФОРМАЦИЯ,ЭНТРОПИЯ ИИЗБЫТОЧНОСТЬ2.1. Информация одного событияОбмен информацией, несмотря на свою нематериальную природу,является неотъемлемой частью нашей жизни.

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

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

Проводя такие эксперименты, мы наблюдаем случайныесобытия и это снижает неопределенность системы.Переходим к самой сущности теории информации. Прежде всегодадим определение простейшего источника, а затем введем понятиеколичества информации, как измеряемой величины для того, чтобыс ее помощью охарактеризовать источник.Дискретный источник без памятиПростейший дискретный источник без памяти X в каждый фиксированный момент времени выдает некоторый символ Xi из конечного алфавитаX = {х\,Х2, • • • ,Х/\[} с вероятностью P(xi)Выборки символов производятся независимо друг от друга.= р;.2.1. Информация одного событияВ качестве простейшего примера можно привести двоичный источник без памяти с алфавитом X = {х\ = 0, £2 = 1} и вероятностями 0 < р\ < 1 и Р2 = 1 ~ Р\ • Выбор очередной цифры производится независимо от прежних и последующих выборок. Изображение простейшего источника приведено на рис.

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