стр. 1
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

М И Р
программирования
М. ВЕРНЕР



Основы
кодирования.
Учебник для ВУЗов.



Перевод с немецкого
Д . К. Зигангирова



Рекомендовано ИППИ РАН
в качестве учебника
для студентов, обучающихся
по направлению
"Прикладные математика и физика"




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




Information
und Codierung



vn <l M ne r
o r Mbr
t tf w
o



Ш

© 2002, Friedr. Vieweg & Sohn
\ferlagsgesellschaft mbH,
Braunschweig/Wiesbaden
© 2004, ЗАО «РИЦ «Техносфера»
перевод на русский язык,
оригинал-макет, оформление.


ISBN 5-94836-019-9
ISBN 3-528-03951-5 (нем.)
Предисловие

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

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

Мартин Вернер
ЧАСТЬ I




ИНФОРМАЦИЯ
и
КОДИРОВАНИЕ
ГЛАВА I
ВВЕДЕНИЕ

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

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. Рассмотрим
вначале одиночные события. Повседневный опыт подсказывает, что
часто происходящие события, так же как и их вероятности, дают нам

стр. 1
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>