Теория кодирования

Содержание

Введение

Теоретическая часть

1. История теории кодирования

2. Основные понятия теории  кодирования

3. Системы счисления как  способ кодирования информации

3.1 Позиционные системы  счисления

3.2 Смешанные системы счисления

3.3 Двоичная система счисления

4. Современные способы  кодирования

4.1 Алфавитное кодирование

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

6.Эффективное кодирование

6.1 Основная теорема Шеннона  о кодировании для канала без  помех

Практическая часть

Заключение

Приложение1

Приложение2

Список летиратуры

 

 

 

 

 

 

 

 

 

 

 

Введение

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

Объектом кодирования  служит как дискретная, так и непрерывная  информация, которая поступает к  потребителю через источник информации. Понятие кодирование означает преобразование информации в форму, удобную для  передачи по определенному каналу связи.

Обратная операция – декодирование  – заключается в восстановлении принятого сообщения из закодированного  вида в общепринятый, доступный для  потребителя.

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

Для достижения поставленной цели были определены следующие задачи:

- углубленное изучение  теоретического материала по  теории кодирования;

- разработка заданий для  проведения лабораторного практикума  по теории кодирования;

- реализация решения задач  по теории кодирования на языке  программирования Pascal. 

 

 

 

 

 

Теоретическая часть

1.История теории  кодирования

С глубокой древности люди искали эффективные способы передачи информации:

- Движение факелов использовал  древнегреческий историк Полибий 

(II в. До н.э);

- оптический телеграф – семафор – впервые использовал Клод Шапп в 1791г.;

- Движение электромагнитной  стрелки в электромагнитных телеграфных  аппаратах впервые применили  русский физик П.Л.Шиллинг (1832) и профессора  Гёттенгенского  университета Вебер и Гаусс (1833);

- Азбука и телеграфный  аппарат Самюэла Морзе (1837);

- Международный флажковый  код для передачи информации  оптическими сигналами впервые  ввел капитан Фредерик Марьят  в 1861 г. На основе свода корабельных  сигналов;

- Беспроволочный телефон,  телевидение (1935), затем и ЭВМ  – новые средства связи, появившиеся  в XX в.,с которыми связана новая эпоха в информатизации общества.

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

К тайнописи – криптографии прибегал Гай Юлий Цезарь, заменяя  в своих тайных записях одни буквы  другими. Использовали шифрование не только древнегреческие жрецы, но и ученые Средневковья: математики итальянец  Джероламо Кардано и француз  Франсуа Виет, нидерландский гуманист, историк, юрист Гроций, выдающийся английский философ Фрэнсис Бэкон. Однако отцом  криптографии считается архитектор Леон Баттиста Альберти (1404-1472), который ввел шифрующие коды и много алфавитные подстановки.

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

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

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

Сэр Фрэнсис Бэкон (1561-1626), английский писатель и философ, лорд-канцлер  елизаветинской эпохи, автор двух литерного  кода, доказал в 1580 г., что для передачи информации достаточно двух знаков. Ф.Бэкон  сформулировал требованию к шифру.

1. Несложен, прост в работе;
2. Надежен, труден для дешифровки посторонним;
3. Скрытен, по возможности не должен вызывать подозрений.

Шифры Бэкона – сочетание  шифрованного текста с дезинформацией в

виде нулей .Двузначные коды и шифры использовались задолго  до появления ЭВМ.

Кодирование имеет значение не только в конспиративных целях  для шифровки информации. Так, в математике с помощью кодирования изучение одних объектов заменяют изучением  других, более доступных или уже  известных. Ярким примером кодирования  в математике является метод  координат, введены Декартом, который дает возможность  изучать геометрические объекты  через их аналитическое выражение  в виде чисел, букв и их комбинаций – формул [4,с.60-64].

Теория кодирования –  довольно молодая наука. Исследование надежности кодов получило новый  импульс после создания в 1948 г, Клодом Эльвудом Шенноном теории информации.

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

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

Доступность проникновения  через Интернет в экономические, политические, военные системы любой  страны выявила новую мировую  проблему – борьбу с компьютерными  взломщиками, хакерами, и компьютерными  террористами.

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

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

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

2. Основные понятия  теории кодирования.

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

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

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

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

Кодирование предшествует передаче и хранению информации. При этом, как указывалось ранее, хранение связано с фиксацией некоторого состояния носителя информации, а  передача – с изменением состояния  с течением времени (т.е процессом). Эти состояния или сигналы  называют элементарными сигналами  – их совокупность и составляет вторичный алфавит [1,с.110-135].

Существует несколько  определений понятия код, в зависимости  от области применения.

Код – правило однозначного преобразования (т.е. функция) сообщения из одной символической формы представления (исходного алфавита А) в другую (объектный алфавит В), обычно без каких –либо потерь информации.

Код – правило, описывающее  соответствие знаков или их сочетаний  первичного алфавита знакам или их сочетаниям вторично алфавита.

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

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

Процесс обратного преобразования слова называется декодированием. Декодирование  можно рассматривать как функцию  F1 – обратную функции F – кодированию.

Кодер – устройство, обеспечивающее выполнение операции кодирования.

Декодер – устройство, производящее декодирование.

Операции кодирования  и декодирования называются обратными, если  их последовательное применение обеспечивает возврат к исходной информации без каких – либо ее потерь [2, с. 63-66].

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

Правила обработки могут  быть различными:

• Поэлементное кодирование;
• Кодирование с помощью алгоритма;
• Кодирование с помощью различных видов графики и др.

Так как для любо кодирования  должна выполняться операция декодирования, то отображение должно быть обратимым (биекция).

3. Системы счисления  как способ кодирования информации.

Система счисления – совокупность различных знаков и правил, для  записи количественного значения.

Цифра – знак, предназначенный  для записи чисел.

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

В современном мире наиболее распространенным является представление  чисел посредством арабских цифр 0,1,2,3,4,5,6,7,8,9 – специальных знаков, используемых для записи чисел.

Системы счисления различаются  выбором базисных чисел, которые  обозначаются знаками – цифрами  и правилами образования из них  остальных чисел.

Системы счисления подразделяются:

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

Непозиционные системы – каждый числовой знак в записи любого числа имеет одно и то же значение, т.е значение его не зависит от его расположения в записи числа. Примером такой системы служит «римская нумерация» [3,с.234-251].