Файл: Методы кодирования данных (Определение и история появления методов кодирования данных).pdf

Введение

Важным и главным элементом информатики как наука является публикация статьей «Теория информации» и «Теория кодирования» Клод Шеннона в 1948. Я не зря упомянул К. Шеннона, ведь, он начал развивать кодирование информации на ЭВМ, также он считается «отцом информационного века».

Тема «Методы кодирования данных» является актуальный по сей день, ведь, люди начиная изучать информатику без исключения в первую очередь столкнуться, с кодировкой информации, так как это способ «общения» с цифровыми устройствами, язык на котором «работают» цифровые устройство, «общаются между собой», сложный, но одновременно и легкий, ведь алфавит данного языка состоит из двух букв 1 и 0. Данная тема дает широкие возможности в проведение:

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

Целью данной курсовой работы является изучение методов кодирования данных. Некоторым может показаться что кодирование информации, оно присуще только для цифровых устройств, но это не так далее в курсовой работе это будет рассмотрено, ведь, кодированием еще пользовались в 5 век до н.э. только не путать шифрование и кодирование. Шифрование — это способ изменения сообщения или другого документа, обеспечивающее искажение (сокрытие) его содержимого. (Кодирование – это преобразование обычного, понятного, текста в код. При этом подразумевается, что существует взаимно однозначное соответствие между символами текста (данных, чисел, слов) и символьного кода – в этом принципиальное отличие кодирования от шифрования.

ГЛАВА 1.Определение и история появления методов кодирования данных.

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

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

---

Теория кодирования и теория информации возникли в начале XX века. Начало развитию этих теорий как научных дисциплин положило появление в 1948 г. статей К. Шеннона, которые заложили фундамент для дальнейших исследований в этой области. Но до возникновения теории кодирования и до появления ЭВМ, телеграфов люди искали наиболее эффективные способы передачи информации.

• Оптический телеграф– семафор рисунок 1 – впервые использовали братья Шапп в 1792 г. На протяжении 225 км были устроены 22 станции, то есть башни с шестами и подвижными планками. Для передачи одного знака требовалось при этом 2 мин. Вскоре построены были и другие линии, и система братьев Шапп получила широкое распространение. От Парижа до Бреста депеша передавалась в 7 мин., от Берлина до Кёльна — в 10 мин. Три подвижные планки такой системы могли принимать 196 различных относительных положений и изображать таким образом столько же отдельных знаков, букв и слов, наблюдаемых при помощи зрительных труб. Несмотря на недостатки оптической телеграфии, заключающиеся главным образом в зависимости от погоды, её активно использовали почти до середины XIX века, в России — до начала 1860-х годов. Своими блестящими победами Наполеон I немало обязан оптическому телеграфу, с помощью которого он имел возможность быстро передавать свои распоряжения на большие расстояния.

Рисунок 1. Оптический семафор братьев Шаппа и их телеграфный алфавит

• Движение электромагнитной стрелки в электромагнитных телеграфных аппаратах впервые применили русский физик П.Л. Шиллинг (1832) и профессора Гёттингенского университета Вебер и Гаусс (1833). 1 – источник тока, 2 – клавиатура, 3 – магнитные стрелки, 4 – провод обратной связи, 5 – вызывное устройство. Посредством 16 клавиш передаточного прибора можно было послать ток того или другого направления и таким образом стрелки мультипликаторов поворачивать вперёд то белым, то чёрным кружком, составляя этим путём условленные знаки. Впоследствии Шиллинг упростил свой приёмный прибор, оставив в нём только один мультипликатор вместо шести, причём условный алфавит был составлен из 36 различных отклонений магнитной стрелки.

Рисунок 2. Схема электромагнитного телеграфа П.Л.Шилинга

• Азбука и телеграфный аппарат Самюэла Морзе (1837). Принцип кодирования азбуки Морзе исходит из того, что буквы, которые чаще употребляются в английском языке, кодируются более простыми сочетаниями точек и тире. Это делает освоение азбуки Морзе проще, а передачи — компактнее. Передача кодов Морзе производится при помощи телеграфного ключа различных конструкций: классического ключа Морзе, электронного ключа, механических полуавтоматов типа «виброплекс», а также при помощи клавиатурных датчиков кода Морзе (например, Р-010, Р-020) и электронных устройств, автоматически формирующих телеграфное сообщение.

---

Рисунок 3. Дерево кода Морзе - направо точки, налево тире.

В эпоху развития телеграфов, для передачи информации использовали азбуку Морзе, в которой буквы были закодированы точкой и тире, ведь, в телеграф передавал гальванический ток на приемник, на котором была установлена магнитная стрелка, которая дергалась при поступлении тока. Также создатели передатчиков обеспокоились тем что передаваемую информацию могут прочитать и понять третьи лица. Для предотвращения таких ситуаций информацию начали шифровать. Методов шифрования было куча, ведь, шифрование развивалось еще с 5 в.н.э., а может и еще раньше. Один из шифровщиков, который внес большой вклад в развитие и формирования модели шифровок — это Сэр Френсис Бэкон(1561-1626) автор двухлитерного кода, доказал в 1580 г., что для передачи информации достаточно двух знаков. Также Ф. Бэкон сформулировал требования к шифру:

1. Шифр должен быть несложен, прост в работе;

2. Шифр должен быть надежен, труден для дешифровки 10 посторонним;

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

Шифры Бэкона – сочетание шифрованного текста с дезинформацией в виде нулей. Таким образом, двузначные коды и шифры использовались задолго до появления ЭВМ. Новый толчок развитию теории кодирования дало создание в 1948 году Клодом Эльвудом Шенноном (1916 — 2001) теории информации. Идеи, изложенные Шенноном в статье «Математическая теория связи», легли в основу современных теорий и техник обработки, передачи и хранения информации. В основе теории информации лежит гипотеза о статистическом характере источника сообщений. Случайная последовательность знаков не несет информации, так же как и ключ кода. А расшифровать код можно, используя знания о статистических закономерностях сообщения и кода. Теория количества информации Шеннона основана на известной со времен Аристотеля альтернативе выбора одного из двух знаков между 0 и 1. В книге вводится логарифмическая функция как мера информации, и показывается её удобство: «Она удобна практически. Параметры, важные в инженерных приложениях — такие, как время, пропускная способность, число переключателей и так далее — обычно меняются линейно при логарифмическом изменении числа возможных вариантов. К примеру, добавление одного переключателя удваивает число возможных состояний их группы, увеличивая на единицу его логарифм по основанию 2. Увеличение в два раза времени приводит к квадратичному росту числа сообщений, или удвоению их логарифма, и так далее. Она близка к нашему интуитивному представлению о такой мере. Это тесно связано с предыдущим пунктом, так как мы интуитивно измеряем величины, линейно сравнивая их со стандартами. Так, нам кажется, что на двух перфокартах можно разместить в два раза больше информации, а по двум одинаковым каналам — передать её в два раза больше. Она удобна математически. Многие предельные переходы просты в логарифмах, в то время как в терминах числа вариантов они достаточно нетривиальны» - К. Шеннон. Также вводится понятие обобщённой системы связи, состоящей из источника информации, передатчика, канала, приемника и пункта назначения. Шеннон разделяет все системы на дискретные, непрерывные и смешанные. Результаты его научных исследований способствовали развитию помехоустойчивого кодирования и простых методов декодирования сообщений. Далее речь будет идти только о методах кодирования данных на цифровых устройствах как персональный компьютер.

---

2. Методы кодирования данных

2.1 Кодирование чисел

Для работы с числовой информацией мы пользуемся системой счисления, содержащей десять цифр: от 0 до 9. Эта система называется десятичной. Кроме цифр, в десятичной системе большое значение имеют разряды. Подсчитывая количество чего-нибудь и дойдя до самой большой из доступных нам цифр (до 9), мы вводим второй разряд и дальше каждое последующее число формируем из двух цифр. Дойдя до 99, мы вынуждены вводить третий разряд. В пределах трех разрядов мы можем досчитать уже до 999 и т.д. Таким образом, используя всего десять цифр и вводя дополнительные разряды, мы можем записывать и проводить математические операции с любыми, даже самыми большими числами. Компьютер ведет подсчет аналогичным образом, но имеет в своем распоряжении всего две цифры - логический ноль (отсутствие у бита какого-то свойства) и логическую единицу (наличие у бита этого свойства). Система счисления, использующая только две цифры, называется двоичной. При подсчете в двоичной системе добавлять каждый следующий разряд приходится гораздо чаще, чем в десятичной.

Рисунок 4. Первые десять чисел в каждой системе счисления

Как видите, в десятичной системе счисления для отображения любой из первых десяти цифр достаточно 1 разряда. В двоичной системе для тех же целей потребуется уже 4 разряда. Соответственно, для кодирования этой же информации в виде двоичного кода нужен носитель емкостью как минимум 4 бита (0,5 байта). Человеческий мозг, привыкший к десятичной системе счисления, плохо воспринимает систему двоичную. Хотя обе они построены на одинаковых принципах и отличаются лишь количеством используемых цифр. В двоичной системе точно так же можно осуществлять любые арифметические операции с любыми числами. Главный ее минус - необходимость иметь дело с большим количеством разрядов. Так, самое большое десятичное число, которое можно отобразить в 8 разрядах двоичной системы - 255, в 16 разрядах – 65535, в 24 разрядах – 16777215.

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

• Небольшие целые числа без знака. Для сохранения каждого такого числа на запоминающем устройстве, как правило, выделяется 1 байт (8 битов). Запись осуществляется в полной аналогии с двоичной системой счисления. Целые десятичные числа без знака, сохраненные на носителе в двоичном коде, будут выглядеть примерно так:

---

Рисунок 5. Число на носителе в двоичном коде

• Большие целые числа и числа со знаком. Для записи каждого такого числа на запоминающем устройстве, как правило, отводится 2-байтний блок (16 битов). Старший бит блока (тот, что крайний слева) отводится под запись знака числа и в кодировании самого числа не участвует. Если число со знаком "плюс", этот бит остается пустым, если со знаком "минус" – в него записывается логическая единица. Число же кодируется в оставшихся 15 битах. Например, алгоритм кодирования числа +2676 будет следующим:

1. Перевести число 2676 из десятичной системы счисления в двоичную. В итоге получится 101001110100;
2. Записать полученное двоичное число в первые 15 бит 16-битного блока (начиная с правого края). Последний, 16-й бит, должен остаться пустым, поскольку кодируемое число имеет знак +.

В итоге +2676 в двоичном коде на запоминающем устройстве будет выглядеть так:

Рисунок 6. Закодированное число на носителе

Запись отрицательных чисел в инвертированной форме позволяет заменить все операции вычитания, в которых они участвуют, операциями сложения. Это необходимо для нормальной работы компьютерного процессора. Максимальным десятичным числом, которое можно закодировать в 15 битах запоминающего устройства, является 32767. Иногда для записи чисел по этому алгоритму выделяются 4-байтные блоки. В таком случае для кодирования каждого числа будет использоваться 31 бит плюс 1 бит для кодирования знака числа. Тогда максимальным десятичным числом, сохраняемым в каждую ячейку, будет 2147483647 (со знаком плюс или минус).

• Дробные числа со знаком. Дробные числа на запоминающем устройстве в двоичном коде кодируются в виде так называемых чисел с плавающей запятой (точкой). Алгоритм их кодирования сложнее, чем рассмотренные выше. Тем не менее, попытаемся разобраться. Для записи каждого числа с плавающей запятой компьютер чаще всего выделяет 4-байтную ячейку (32 бита):

1. в старшем бите этой ячейки (тот, что крайний слева) записывается знак числа. Если число отрицательное, в этот бит записывается логическая единица, если оно со знаком "плюс" – бит остается пустым.
2. во втором слева бите аналогичным образом записывается знак порядка (что такое порядок поймете позже);
3. в следующих за ним 7 битах записывается значение порядка.
4. в оставшихся 23 битах записывается так называемая мантисса числа.

---