Элементы теории кодирования

Государственное образовательное учреждение

высшего профессионального образования

«Арзамасский  государственный педагогический институт

им. А.П. Гайдара» 
 

Кафедра математики, теории и методики обучения математике 
 

Макарова  К.А., студентка

З курса очного отделения

физико-математического

факультета 
 
 
 

КУРСОВАЯ  РАБОТА

ЭЛЕМЕНТЫ  ТЕОРИИ КОДИРОВАНИЯ 
 
 

Научный руководитель:

к.п.н., доцент Фомина Н.И. 
 
 
 
 
 
 
 
 

Арзамас

2011 

Содержание 
 

Введение…………………………………………………………………………..3

§ 1. Базовые понятия теории кодирования……………………………………...5

§ 2. Алфавитное кодирование……………………………………………………9

§ 3. Двоичный алфавит………………………………………………………….14

§ 4. Кодирование и обработка чисел компьютером…………………………...20

§ 5. Решение практических задач……………………………………………..25

Заключение………………………………………………………………………35

Литература……………………………………………………………………….36 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Введение

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

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

        Кодирование - это преобразование сообщения в форму, удобную для передачи по каналу связи.

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

        Дискретная математика – одна из областей математики, начала которой возникли в глубокой древности. Основной отличительной чертой её классической математики, которая в основном занимается изучением свойств объектов непрерывного характера с использованием основного понятия – предел, является дискретность, противоположность непрерывности. Предметом дискретной математики является изучение свойств произвольных структур (множеств с операциями, отношения и аксиомами), которые появляются как в самой математике, так и в области её приложений.

       Дискретная математика включает в себя такие разделы как теорию чисел, алгебру, математическую логику, теорию графов и сетей, теорию кодирования, комбинаторный анализ и теорию конечных автоматов.

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

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

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

         Целью данной курсовой работы является рассмотрение кодирования как способа представления информации.

        Задачи курсовой работы состоят в изучении учебной и научной литературы по теме исследования, в рассмотрении сущности понятия кодирования информации, в характеристике процессов кодирования и декодирования.

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

§ 1. Базовые понятия теории кодирования

1. 1. Кодирование как способ представления информации

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

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

         Часто термин «кодирование» употребляется в более узком смысле. Кодирование в узком смысле слова подразумевает представление сообщения в форме, удобной для передачи по некоторому каналу связи.

Информационное  сообщение всегда связано с источником информации, приемником информации и каналом передачи.

Чтобы передать информацию, её необходимо предварительно преобразовать.

         Кодирование - это преобразование сообщения в форму, удобную для передачи по каналу связи.

        Декодирование - операция восстановления принятого сообщения.

В систему  связи необходимо ввести устройства для кодирования и декодирования информации.

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

обнаружить ошибки, если они возникают;

исправлять  найденные ошибки;

защищать  информацию, передающуюся по каналам связи;

ускорять передачу информации по каналу связи.

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

1. 2. Кодирование и декодирование

         Кодированием называется отображение произвольного множества А в множество конечных последовательностей в некотором алфавите В, а декодированием — обратное отображение.

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

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

      Рассмотрим некоторые примеры кодов.

1. Азбука Морзе в русском варианте ( алфавиту, составленному из алфавита русских заглавных букв и алфавита арабских цифр ставится в соответствие алфавит Морзе):

2. Код  Трисиме (знакам латинского алфавита  ставятся в соответствие комбинации  из трех знаков: 1,2,3):

Код Трисиме  является примером, так называемого, равномерного кода (такого, в котором все кодовые комбинации содержат одинаковое число знаков - в данном случае три). Пример неравномерного кода - азбука Морзе.

3. Кодирование  чисел знаками различных систем  счисления

1. 3. Помехоустойчивое кодирование

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

1. 4. Канал связи

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

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

   

   

   

     
 

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

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

   1. 5. Криптология

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