Файл: Технологии программирования. Методы кодирования данных.pdf

ВВЕДЕНИЕ

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

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

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

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

Объект исследования: кодирование и методы кодирования данных.

Предмет исследования: представление методов кодирования данных на примере метода кодирования Хаффмана.

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

---

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

1. изучить представление о процессе кодирования информации;
2. провести классификацию назначения и способов предоставления кодов;
3. определить основные типы кодирования;
4. выявить разновидности методов кодирования;
5. рассмотреть метод кодирования Хаффмана;
6. представить анализ задач кодирования.

Так, вопросы изучения методов кодирования данных рассматривались в работах таких ученых, как А.В. Еремеев, К.С. Варламов, И.Н. Перевалова, К.А. Михайловская, И.С. Иркутов, М.П. Красильников, У.Л. Малиновская, З.А. Сейташвили, Р.В. Харитонов, Я.П. Зайцев, А.Р. Калинин, К.Г. Кравец, А.А. Шульга, А.Н. Морозова, О.В. Полываная, С.В. Сергеев, Г.П. Варапаев, И.А. Кузьменский, О.Л. Макарова, А.И. Ужиков, У.В. Малахова, К.В. Артемова, З.Г. Сердюкова, и других авторов.

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

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

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

ГЛАВА 1. ИЗУЧЕНИЕ ПРЕДСТАВЛЕНИЯ И КОДИРОВАНИЯ ИНФОРМАЦИИ

Общие понятия теории кодирования

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

1. Философский подход (основоположниками являются Бауэр, Гоод): Кодирование – это преобразование сигнала в смысл. ^[1]

---

2. Практический подход (основоположниками являются Глушков, Лебедев): Кодирование - преобразование одного сигнала в другой сигнал без изменения смысла. Код - это правило замены одного символа на другой. Коды подразделяются на виды:

По структуре:

• Табличный;

• Линейный.

По типам сигнала:

• Графический;

• Текстовый;

• Числовой;

• Звуковой. [5, с. 44]

В 1946 году Джон фон Нейман доказал, что в виде нулей и единиц, возможно, представить любой вид кода, т.е. в виде системы счисления двоичного кодирования. Вся информация, с которой взаимодействует современная вычислительная техника, преобразуется в числа в двоичной системе счисления. Физические устройства (ячейки памяти, регистры) могут находиться только в двух состояниях, а именно 0 или 1 [20, с. 11].

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

Перевод информации, представленной сообщением в первичном алфавите, в последовательность кодов можно определить, как кодирование информации. Информация может быть представлена в различных формах, например, в виде чисел, текста, рисунка и др. А кодирование – это процесс перевода из одной формы в другую. Существуют различные методы декодирования и кодирования информации в компьютере. Эти методы зависят от вида информации: графическое изображение, текст, звук или число [11, с. 35].

Также для числа важно, как оно будет использовано: в вычислениях или тексте, или в процессе ввода. Вся эта информация с помощью цифр 0 и 1 кодируется в бинарной системе счисления. Эти два символа называют двоичными цифрами или битами. Такого рода способ кодирования технически просто организовать: 1 – когда есть электрический сигнал, 0 – когда нет сигнала. Недостатком двоичного кодирования является его длинные коды. Однако в технике иметь дело с большим числом простых однотипных элементов легче, чем с незначительным числом сложных [19, с. 82].

---

Теоретические основы кодирования различных видов информации Современный компьютер способен обрабатывать числовую, текстовую, графическую, звуковую и видео-информацию (Таблица 1). В компьютере эти виды информации представлены в виде двоичного кода, т. е. используется алфавит мощностью два (всего два символа 0 и 1) [15, с. 56].

Кодирование числовой информации.

Любое число машинного двоичного кода несет количество информации равное 1 биту. Данное заключение можно сделать, рассматривая цифры машинного алфавита, как равновероятные события. При записи бинарной цифры можно осуществить выбор только одного из двух возможных состояний, а, значит, она несет количество информации равное 1 бит. Следовательно, две цифры несут информацию 2 бита, четыре цифры -4 бита и т. д. Для определения количества информации в битах, достаточно посчитать количество цифр в двоичном машинном коде. ^[2]

Кодирование текстовой информации.

Для представления текстовой информации необходимо использовать алфавит мощностью 256 символов. Обычно для кодирования одного символа используют количество информации равное 1 байту, т. е. I = 1 байт = 8 бит. Принцип кодирования заключается в том, что любому символу в соответствие с ним ставят двоичный код от 00000000 до 11111111 или подходящий ему десятичный код от 0 до 255.

Для кодировки русских букв применяют пять различных кодовых таблиц (ISO, СР866, КОИ - 8, СР1251, Мас), при этом тексты, закодированные с помощью одной таблицы, не смогут правильно отображаться в любой другой кодировке (Таблица 2).

Однако для перекодировки текстовых документов используют специальные программы – конверторы. Кодировка Unicode, отводит по 2 байта на каждый символ, соответственно, с ее помощью можно закодировать не 256 символов, а 65536 различных символов. Для определения числового кода символа необходимо воспользоваться кодовой таблицей [1, с. 9].

Кодирование графической информации.

На сегодняшний день технологии обработки графической информации обширно применяются на персональных компьютерах. Большое применение получила специальная область информатики, изучением которой являются методы и средства создания и обработки изображений при помощи программно-аппаратных вычислительных комплексов, и эта область получила название компьютерная графика. В связи с тем, что во многих сферах человеческой деятельности используется визуализация данных, без компьютерной графики трудно представить не только компьютерный, но и материальный мир. Графическую информацию можно представлять в двух формах, как аналоговую или дискретную [15, с. 23].

---

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

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

Чем меньше размер точки, тем выше качество, так как изображение составляется из большего количества точек. Создавать и хранить графические объекты возможно в нескольких видах - в виде растрового, векторного или фрактального изображения. Отдельным предметом считается 3D (трехмерная) графика, в которой сочетаются векторный и растровый способы формирования изображений.^[4] Он изучает методы и приемы построения объемных моделей объектов в виртуальном пространстве. Для каждого вида необходим собственный метод кодирования. Растровое изображение. В качестве примера можно взять газету, посмотреть на нее через увеличительное стекло и увидеть черно-белое графическое изображение, состоящее из мельчайших точек, которые составляют определенный узор – растр. В 19 веке во Франции возникло одно из новых направлений в живописи - пуантилизм. Особенностью данного направления было нанесение рисунка на полотно в виде разноцветных точек.

Помимо этого в полиграфии данный метод уже давно применяется для кодирования графической информации. Точность передачи рисунка зависит от размера точек и их количества. Уже после разбивания рисунка на точки, начиная с левого угла, передвигаясь по строкам слева направо, можно кодировать цвет каждой точки. После, такая точка будет называться пикселем. Размер растрового изображения определяется умножением количества пикселей на информационный объем одной точки, который зависит от количества возможных цветов [12, с. 45].

---