Доклад на тему: "кодирование"




Скачать 338.14 Kb.
НазваниеДоклад на тему: "кодирование"
страница1/3
Дата публикации04.07.2013
Размер338.14 Kb.
ТипДоклад
zadocs.ru > Информатика > Доклад
  1   2   3
Илларионова Кристина, ММ-11

Доклад на тему: "КОДИРОВАНИЕ"
Язык дан для того, чтобы скрывать свои мысли.

Народная мудрость

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

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

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

История кодирования и защиты информации.

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

~       Движение факелов использовал древнегреческий историк Полибий (II в. Дон.э.};

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

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

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

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

~       Беспроволочный телеграф (радиопередатчик) был изобретен А.С.Поповым в 1895 г. И Маркони в 1897 г. Независимо друг от друга;

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

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

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

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

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

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

Развитие современной теории кодирования стимулировалось прогрессом систем связи. Теория информации Шеннона, основанная на понятии энтропии, является математической основой эффективных кодов, широко используемых для сжатия информации. Их примерами являются коды Шеннона-Фано и код Хаффмена.

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

Таким образом, современная теория кодирования - это совокупность, по крайней мере, четырех различных направлений:

  1. Теория систем счисления;

  2. Теория криптографии;

  3. Теория эффективных кодов;

  4. Теория избыточных кодов.

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

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

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

1. Несложен, прост в работе;

2. Надежен, труден для дешифровки посторонним;

3. Скрытен, по возможности не должен вызывать подозрений.

Шифры Бэкона – сочетание шифрованного текста с дезинформа­цией в виде нулей. Двузначные коды и шифры использовались задолго до появления ЭВМ.

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

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

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

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

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

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

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

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

^ ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ ТЕОРИИ КОДИРОВАНИЯ
Оптимальным статистическим (экономным) кодированием называется кодирование, при котором обеспечивается распределение времени на передачу отдельных символов алфавита в зависимости от априорных вероятностей их появления:
; (1)
где Cп - пропускная способность канала; pi - априорная вероятность i –й кодовой комбинации; ti -длительность i-й кодовой комбинации.

Оптимальными неравномерными кодами (ОНК) - называются коды, в которых символы алфавита кодируются кодовыми словами минимальной средней длины.

Принципы построения оптимальных кодов:

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

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

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

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

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

Существует много методов оптимального, статистического кодирования. Наиболее часто используют оптимальное кодирование по методу Шеннона - Фано и Хаффмена.

^ АЛФАВИТНОЕ КОДИРОВАНИЕ

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

 и  .

 Элементы алфавита называются буквами. Упорядоченный набор в алфавите А назовем словом

 

,где , число п показывает количество букв в слове и называется длиной слова ,  обозначается п =l()=||.

Пустое слово обозначается:



Для слова

 

буква a1, называется началом, или префиксом, слова , а буква an — окончанием, или постфиксом, слова .

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

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

    Множество всех непустых слов алфавита А обозначим А*:

 

    Множество А называют алфавитом сообщений, а множество В — кодирующим алфавитом. Множество слов, составленных в алфавите В,обозначим В*.

Обозначим через F отображение слов алфавита А в алфавит В. Тогда слово    назовем кодом слова .

    Кодированием называют универсальный способ отображения информации при ее хранении, передаче и обработке в виде системы соответствий между элементами сообщений и сигналами, при помощи которых эти элементы можно зафиксировать. Таким образом, код — правило однозначного преобразования (т.е. функция) сообщения из одной символической формы представления (исходного алфавита А) в другую (объектный алфавит В), обычно без каких-либо потерь информации. Процесс преобразования F: А*→В* слов исходного алфавита А в алфавит Вназывается кодированием информации.

    Процесс обратного преобразования слова  в слово  называется декодированием. Таким образом, декодирование — функция, обратная F, т.е. F-1.

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

    Если |B|= m, то F называется m-ичным кодированием, наиболее распространенный случай В = {0, 1}- двоичное кодирование. Именно этот случай и рассматривается в дальнейшем.

    Если все кодовые слова имеют одинаковую длину, то код на­зывается равномерным, или блочным.

    Алфавитное (или побуквенное), кодирование можно задать таблицей кодов. Кодом или кодирующей функцией, будет служить некоторая подстановка . Тогда

 

, где ,  .

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

Пример:

Пусть заданы алфавиты

 А = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

 В = {0, 1}.

Тогда таблица кодирования может быть подстановкой:

 .

    Это двоично-десятичное кодирование, оно является взаимнооднозначным и потому допускает декодирование.

Однако схема

 

 не является взаимно-однозначной. Например, набор из шести единиц 111111 может соответствовать как слову 333, так и 77,  а также 111111, 137, 3311 или 7111 плюс любая перестановка.

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

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

    Алфавитное кодирование с разделимой схемой допускает де­кодирование. Можно доказать, что префиксная схема является разделимой.

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

^ Неравенство Макмиллана

Если схема алфавитного кодирования

  

разделима, то справедливо неравенство

 

Пример:

     Схема алфавитного кодирования

 А={ аb} и В={0, 1}, 



является разделимой, т. к.

,

и, значит, выполняется неравенство Макмиллана



    Данная схема префиксной не является, т.к. элементарный код буквы  а   является префиксом элементарного кода буквы b.
  1   2   3

Добавить документ в свой блог или на сайт

Похожие:

Доклад на тему: \"кодирование\" iconДоклад на тему: «Особенности исторического пути России в концепции Л. В. Милова»
Доклад прочитан 16 апреля 2008г в Московском обществе испытателей природы (моип) (секция «Философские и методологические проблемы...

Доклад на тему: \"кодирование\" iconДоклад на тему: Голод 1932-1933 г г. в Украине
Сталинское руководство накладывало табу на эту тему. Про страшную беду не разрешалось говорить открыто, а тем более упоминать в газетах...

Доклад на тему: \"кодирование\" iconДоклад по информатике на тему: «Методы и средства создания и сопровождения сайта»

Доклад на тему: \"кодирование\" iconРеферат Тема: “ Проблема обеспечения безопасности человека при использовании...
Еще несколько лет назад психологи и психиатры спорили о том, возможно ли в принципе кодирование человека. Теперь они уже не спорят,...

Доклад на тему: \"кодирование\" iconДоклад по Кубановедению на тему
Памятник воинам, принимавшим участие в освобождении города от немецко-фашистских захватчиков, 1965 г

Доклад на тему: \"кодирование\" iconДоклад на тему «Ювенальная юстиция инструмент уничтожения»
Татьяна Сергеевна Кучер, заместитель председателя Донецкой областной общественной организации «Научный совет»

Доклад на тему: \"кодирование\" iconДоклад по дисциплине: История На тему: Культурные
Достижения в области культуры в эпоху Петра очень незначительны, хотя по его приказу и было переведено с иностранных языков около...

Доклад на тему: \"кодирование\" iconДоклад. На тему : История вычислительной техники
Естественно, сама по себе, производительность и скорость счёта современных вычислительных устройств давно уже превосходят возможности...

Доклад на тему: \"кодирование\" iconДоклад на тему «Леонард Эйлер»
Леонард Эйлер (1707-1783) — математик, механик, физик и астроном. По происхождению швейцарец

Доклад на тему: \"кодирование\" iconВнимание! Страница дорабатывается!
Учебным планом изучения дисциплины предусматривается такой вид работы студента, как доклад или сообщение. Мможно сделать 1 доклад...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
zadocs.ru
Главная страница

Разработка сайта — Веб студия Адаманов