Кодирование информации в ЭВМ

 

 

 

 

Кодирование информации в ЭВМ

 

 

 

Проверил:

Выполнил:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Оренбург 2009

 

Содержание

 

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

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

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

2. Способы кодирования информации в ЭВМ …………………………………………………..6
3. Кодирование символьной информации………………………………………………………..7
4. Кодирование числовой информации …………………………………………………………..8
5. Кодирование графической информации…………………………………………………….....9
6. Кодирование звуковой информации …………………………………………………………11
7. Алгоритм Хаффмана …………………………………………………………………………..16
8. Алгоритм кодирования Лемпеля – Зива ……………………………………………………..15
9. Помехоустойчивые коды ……………………………………………………………………...17
10. Теоремы Шеннона …………………………………………………………………………..18

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

Программа на  кодирование информации ………………………………………………………...19

Приложение ………………………………………………………………………………………………...21

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

   Теория кодирования близка к древнейшему искусству тайнописи – криптографии. Над разработкой различных шифров трудились многие известные ученые: философ Ф. Бэкон, математики Д.Кардано, Д. Валлис. Одновременно с развитием методов шифровки развивались приемы расшифровки, или криптоанализа.

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

  Грандиозные достижения человечества - письменность и арифметика - есть не что иное, как система кодирования речи и числовой информации. Информация никогда не появляется в чистом виде, она всегда как-то представлена, как-то закодирована.

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

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

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

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

Майкл Фарадей в 1831 году сделал открытие, буквально перевернувшее мир: он изобрел способ получения электрического тока. И чуть ли не сразу же электрический ток был использован для передачи сообщений [10].

На основе теоретических разработок английского ученого Шиллинга, американский изобретатель Сэмюэл Морзе создал и широко внедрил в практику телеграфные аппараты и линии связи. Морзе пришлось создавать язык, отчасти похожий на язык африканского барабанного телеграфа. И электрический ток, и барабан имеют весьма небогатый собственный язык. По барабану можно либо стучать, либо нет. Электрический ток или идет, или его нет. Поэтому и кодировка, предложенная Морзе использовала всего три своеобразные буквы: длинный сигнал (тире), короткий сигнал (точка), нет сигнала (пауза) - для разделения букв. Так, знаменитый сигнал SOS - (Save Our Souls - спасите наши души) кодируется так:

<точка>, <точка>, <точка> - S 
<пауза> 
<тире>, <тире>, <тире> - O 
<пауза> 
<точка>, <точка>, <точка> - S

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

  В середине нашего века под руководством Алана Тьюринга  под Лондоном  появились компьютеры, обрабатывающие  буквы и цифры, т.е. символьную информацию. Именно там в 1943 году был создан специализированный компьютер, расшифровывающий немецкие военные коды (машина называлась “Колосс”). Тысячи перехваченных за день неприятельских сообщений вводились в память “Колосса”, после чего в поисках соответствия машина перебирала сотни тысяч вариантов, расшифровывая самые сложные коды.

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

  Объект: Информационные процессы

  Предмет: Кодирование информации

  Цель: Разработать программно – методический комплекс “Кодирование информации”

  Задачи:

1. Выделить основные понятия теории кодирования
2. Уточнить способы представления информации в ЭВМ
3. Рассмотреть алгоритмы кодирования (алгоритм Хаффмана, Лемпеля – Зива, Хемминга)
4. Рассмотреть основные виды помехоустойчивых кодов
5. Разработать программно – методический комплекс по кодированию информации

 

 

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

 

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

 

  Рассмотрим ряд определений, использующихся в теории кодирования:

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

  Кодирование – перевод информации, представленной посредством первичного алфавита, в последовательность кодов.

  Декодирование - операция, обратная кодированию, т.е. восстановление информации в первичном алфавите по полученной последовательности кодов.

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

  Примером обратимого  кодирования является представление  знаков в телеграфном коде  при передаче сообщений и восстановление  их при приеме.

  Примером необратимого  кодирования является перевод  текста с одного естественного  языка на другой (обратный перевод  побуквенно обычно не соответствует  исходному тексту).

  Основными задачами кодирования являются:

1. Обеспечение экономичности  передачи информации посредством устранения избыточности

2. Обеспечение надежности (помехоустойчивости) передачи информации

3. Согласование скорости  передачи информации с пропускной  способностью канала

  Соответствие между элементами дискретных сообщений и видом кодирования обеспечивается выбором:

1. Длительности сигналов

2. Длины кодового слова 

3. Алфавита знаков и  способа кодирования (побуквенного, блочного).  Различают побуквенное и блочное кодирование.   При побуквенном кодировании каждому знаку внешнего алфавита ставиться в соответствие кодовое слово из знаков внутреннего алфавита.  При блочном кодировании слову из знаков внешнего алфавита ставиться в соответствие кодовое слово из знаков внутреннего алфавита.

Чтобы код был обратимым, необходимо:

1) чтобы разным символам  входного алфавита А были сопоставлены разные кодовые комбинации;

2) чтобы никакая кодовая  комбинация не составляла начальной  части какой-нибудь другой кодовой  комбинации.

Кодирование информации (иногда говорят — шифровка) – это процесс формирования определенного представления информации. В более узком смысле под термином «кодирование» часто понимают переход от одной формы представления информации к другой, более удобной для хранения, передачи или обработки.

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

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

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

 

2. Способы кодирования информации в ЭВМ

 

Одна и та же информация может быть представлена (закодирована) в нескольких формах. Двоичное кодирование – один из распространенных способов представления информации. В вычислительных машинах, в роботах и станках с числовым программным управлением, как правило, вся информация, с которой имеет дело устройство, кодируется в виде слов двоичного алфавита. Двоичный алфавит состоит из двух цифр 0 и 1. Цифровые ЭВМ (персональные компьютеры относятся к классу цифровых) используют двоичное кодирование любой информации. В основном это объясняется тем, что построить техническое устройство, безошибочно различающее 2 разных состояния сигнала, технически оказалось проще, чем то, которое бы безошибочно различало 5 или 10 различных состояний.

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

Среди всего разнообразия информации, обрабатываемой на компьютере, значительную часть составляют числовая, текстовая, графическая и аудиоинформация. Познакомимся с некоторыми способами кодирования этих типов информации в ЭВМ. [ 3]

 

3. Кодирование символьной (текстовой) информации

 

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

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

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

В настоящее время, большая часть пользователей, при помощи компьютера обрабатывает текстовую информацию, которая состоит из символов: букв, цифр, знаков препинания и др. Подсчитаем, сколько всего символов и какое количество бит нам нужно: 10 цифр, 12 знаков препинания, 15 знаков арифметических действий, буквы русского и латинского алфавита, ВСЕГО: 155 символов, что соответствует 8 бит информации.

  Суть кодирования заключается в том, что каждому символу ставят в соответствие двоичный код от 00000000 до 11111111 или соответствующий ему десятичный код от 0 до 255.

  Для кодирования текстов используются различные таблицы перекодировки.

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

  Наиболее популярные таблицы перекодировки: ДКОИ-8, ASCII, CP1251, Unicode, причем тексты, закодированные при помощи одной таблицы не будут правильно отображаться в другой, поэтому важно, чтобы при кодировании и декодировании одного и того же текста использовалась одна и та же таблица. ( Базовая таблица кодировки ASCII приведена в таблице 1.1.). Не так давно был предложен новый стандарт символьного кодирования UNICODE, где каждый символ кодируется уже двумя байтами. Он позволяет свободно обмениваться сообщениями по Интернету на любом языке, не выясняя предварительно, понимает ли другой компьютер ваш родной алфавит.