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

Содержание:

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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].

Качество изображения определяется разрешающей возможностью монитора. Чем она выше, то есть больше количество строк растра и точек в строке, тем выше качество изображения. Если говорить о черно-белых изображениях и не использовать полутона, то пиксель будет принимать одно из двух состояний: светится (белый) и не светится (черный).

Так как информация о цвете пикселя называется кодом пикселя, то для его кодирования достаточно одного бита памяти: 0 - черный, 1 – белый [3, с. 41]. Если же рассматриваются изображение в виде комбинации точек с 256 градациями серого цвета, то достаточно восьмиразрядного двоичного числа для того чтобы закодировать цвет любой точки. ^[5]

Цветовые модели.

Говоря о кодировке разноцветных графических изображений, следует рассмотреть принцип декомпозиции произвольного цвета на основные составляющие. Существует несколько систем кодирования, такие как HSB, 13 RGB и CMYK. HSB - эта цветовая модель удобна для человека, так как проста и интуитивно понятна. RGB- эта модель удобна для компьютера. А модель CMYK – хорошо подходит для типографий. Данные световые модели применяют связано с тем, что световой поток может формироваться излучениями, представляющими собой комбинацию «чистых» спектральных цветов: зеленого, красного, синего или их производных [7, с. 28].

Различают аддитивное цветовоспроизведение (характерно для излучающих объектов) и субтрактивное цветовоспроизведение (характерно для отражающих объектов). В качестве примера аддитивного цветовоспроизведения можно привести электроннолучевую трубку монитора, в качестве примера субтрактивного цветовоспроизведения можно привести полиграфический отпечаток. Система кодирования RGB заключается в то что, любой цвет можно представить в виде комбинации трех цветов: красного (Red, R), зеленого (Green, G), синего (Blue, B). Другие цвета и их оттенки получаются за счет наличия или отсутствия этих составляющих. Название – RGB система получила по первым буквам основных цветов. Эта цветовая модель считается аддитивной, так как любой цвет можно получить сочетанием основных цветов в их различных пропорциях. Например, в мониторах и телевизорах используются три электронных пушки (светодиода, светофильтра) для зелёного, красного и синего каналов [4, с. 30].

При 256 градациях тона (где каждая точка кодируется тремя байтами) минимальные значения RGB (0,0,0) соответствуют черному цвету, а белому - максимальные с координатами (255, 255, 255). Чем больше значение байта цветовой составляющей, тем цвет будет ярче. Например, темно-синий кодируется тремя байтами (0, 0, 128), а ярко-синий (0, 0, 255). Система кодирования CMYK – представляет собой цветовую модель, в которой все цвета представляются как смесь четырех обрабатываемых цветов, сокращённое название от Cyan – Magenta – Yellow – Black - голубой пурпурный-желтый-черный. Система кодирования CMYK применяется при подготовке публикаций к печати. Каждому из основных цветов ставится в соответствие дополнительный цвет (дополняющий основной до белого). Получают дополнительный цвет за счет суммирования пары остальных основных цветов. Система CMYK применяется для триадной печати в полиграфии [5, с. 88].

Система кодирования HSB включает в себя три компонента: оттенок цвета (Hue), насыщенность цвета (Saturation) и яркость цвета (Brightness). Регулируя эти компоненты можно получить большое количество различных цветов. Эту систему лучше использовать в тех графических редакторах, в которых изображение создается с самого начала, а не обрабатывается уже готовое. ^[6]

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

Различают несколько режимов представления цветной графики (Таблица3):

• Полноцветный (TrueColor);

• HighColor;

• Индексный [8, с. 132].

Для кодирования яркости при полноцветном режиме каждой из составляющих применяют по 256 значений (восемь двоичных разрядов), то есть на кодирование цвета одного пикселя (в системе RGB) необходимо затратить 8*3=24 разряда. Это позволяет конкретно устанавливать 16,5 миллионов цветов. Что наиболее близко к чувствительности человеческого глаза. При кодировании с помощью системы CMYK для представления цветной графики надо иметь 8*4=32 двоичных разряда. Режим HighColor - это кодирование при помощи 16-разрядных бинарных чисел, то есть уменьшается количество двоичных разрядов при кодировании каждой точки. Однако диапазон кодируемых цветов значительно уменьшается. При индексном кодировании цвета достаточно передать всего лишь 256 цветовых оттенков. Каждый цвет здесь кодируется при помощи восьми бит данных. В данном случае код точки растра означает не цвет, а только его номер (индекс) в палитре. Отсюда и взялось название режима – индексный [6, с. 25].

Соответствие между количеством отображаемых цветов (К) и количеством бит для их кодировки (а) находиться по формуле: K = 2 a.

Векторное и фрактальное изображения.

Векторное изображение - это графический объект, состоящий из элементарных отрезков и дуг. Основным элементом изображения считается линия. Она обладает следующими свойствами: толщиной, цветом, формой (прямая, кривая), начертанием (пунктирная, сплошная). Замкнутые линии имеют свойство заполнения (выбранным цветом, или другими объектами). Все другие объекты векторной графики составляются из линий.^[7] Так как линия описывается математически как единый объект, то и объем данных для отображения объекта средствами векторной графики значительно меньше, чем в растровой графике. Информация о векторном изображении кодируется как обычная буквенно-цифровая и обрабатывается специальными программами [9, с. 87].

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

Кодирование звуковой информации [10, с. 56].

Человек на слух воспринимает упругие волны, частота которых находится в пределах от 16 Гц до 20 кГц (1 Гц - 1 колебание в секунду). В соответствии с этим упругие волны в любой среде, частоты которых лежат в указанных пределах, называют звуковыми волнами или просто звуком. В учении о звуке важны такие понятия как тон и тембр звука. Всякий реальный звук, будь то игра музыкальных инструментов или голос человека, - это своеобразная смесь многих гармонических колебаний с определенным набором частот. В настоящее время, компьютер широко применяется в различных сферах. Исключением не стала и обработка звуковой информации. Для записи звука в настоящее время используется два основных способа, это аналоговый и цифровой. Но для записи звука, на какой либо носитель его необходимо преобразовать в электрический сигнал [11, с. 16].

При помощи микрофона звуковые волны превращаются в аналоговый переменный электрический сигнал. Он проходит через звуковой тракт и попадает в аналого-цифровой преобразователь (АЦП) - устройство, которое переводит сигнал в цифровую форму. Принцип работы аналого-цифровой преобразователь заключается в том что: через определенные промежутки времени он измеряет амплитуду сигнала и передает дальше, уже по цифровому тракту, последовательность чисел, несущих информацию об изменениях амплитуды. Во время аналого-цифрового преобразования не происходит никакого физического преобразования [12, с. 74]. С электрического сигнала как бы снимается отпечаток или образец, являющийся цифровой моделью колебаний напряжения в аудио тракте. Если это изобразить в виде схемы, то эта модель представлена в виде последовательности столбиков, каждый из которых соответствует определенному числовому значению. Цифровой сигнал по своей природе дискретен - то есть прерывист, поэтому цифровая модель не совсем точно соответствует форме аналогового сигнала. Для кодирования значения амплитуды используют принцип двоичного кодирования [14, с. 193].

Звуковой сигнал должен быть представленным в виде последовательности электрических импульсов (двоичных нулей и единиц). Обычно используют 8, 16-битное или 20-битное представление значений амплитуды. При двоичном кодировании непрерывного звукового сигнала его заменяют последовательностью дискретных уровней сигнала. От частоты дискретизации (количества измерений уровня сигнала в единицу времени) зависит качество кодирования [16, с. 95].

На современные цифровые звуковые устройства устанавливаются 20- битные преобразователи. Звук так и остается 16-битным, преобразователи повышенной разрядности устанавливают для улучшения качества записи на низких уровнях. Их принцип работы заключается в следующем: исходный 18 аналоговый сигнал оцифровывается с разрядностью 20 бит. Затем цифровой сигнальный процессор DSP понижает его разрядность до 16 бит. При этом используется специальный алгоритм вычислений, при помощи которого можно снизить искажения низкоуровневых сигналов.

Кодирование видеоинформации.

Видеоинформация – наиболее сложный вид для обработки, воспроизведения и хранения. Движущиеся изображения в виде большого количества отдельных кадров, заснятых через небольшие промежутки времени (24 кадра в секунду) впервые были сохранены на кинопленке. Позднее на ту же пленку была записана и звуковая дорожка (в последующем несколько дорожек для многоканального звука) [3, с. 49]. После появилось телевидение с аналоговой записью движущегося изображения на магнитные ленты (системы телевидения PAL и SECAM используют 25 кадров в секунду, система NTSC – 29,97 кадров в секунду). Широкое распространение получили цифровые методы записи и кодирования видеоинформации с появлением компьютеров, которые постоянно совершенствуются [13, с. 71].

Среди алгоритмов с потерями одним из наиболее известных является MotionJPEG или MJPEG. Приставка Motion говорит, что алгоритм JPEG используется для сжатия нескольких кадров. При кодировании видео принято, что качеству VHS соответствует кодирование MJPEG с потоком около 2 Мбит/с, S-VHS – 4 Мбит/с. Свое развитие алгоритм MJPEG получил в алгоритме DV, который обеспечивает лучшее качество при таком же потоке данных. Это объясняется тем, что алгоритм DV применяет более гибкую схему компрессии, основанную на адаптивном подборе коэффициента сжатия для различных кадров видео и различных частей одного кадра [10, с. 12].

Для малоинформативных частей кадра, например, краев изображения, сжатие увеличивается, а для блоков с большим количеством мелких деталей уменьшается. Еще одним методом сжатия видеосигнала является MPEG. Так как видеосигнал транслируется в реальном времени, то нет возможности для обработки всех кадров одновременно.^[8] В алгоритме MPEG запоминается несколько кадров. Основной принцип заключается в предположении того, что соседние кадры мало отличаются друг от друга. Поэтому можно сохранить один кадр, который называют исходным, а затем сохраняются только изменения от исходного кадра, называемые предсказуемыми кадрами. Считается, что за десять – пятнадцать кадров картинка изменится настолько, что необходим новый исходный кадр. В результате при использовании MPEG можно достичь уменьшения объема информации более чем в 200 раз, хотя это приводит к некоторой потере качества. В настоящее время используются алгоритм сжатия MPEG-1, разработанный для хранения видео на компакт дисках с качеством VHS, MPEG-2, используемый в цифровом, спутниковом телевидении и DVD, а также алгоритм MPEG-4, разработанный для передачи информации по компьютерным сетям и широко используемый в цифровых видеокамерах и для домашнего хранения видеофильмов. Все форматы сжатия семейства MPEG (MPEG-1, MPEG-2, MPEG-4, MPEG-7) используют высокую избыточность информации в изображениях, разделенных малым интервалом времени. Алгоритмы MPEG сжимают только опорные кадры – I-кадры (Intra frame – внутренний кадр). В промежутки между ними включаются кадры, содержащие только изменения между двумя соседними I-кадрами – P-кадры (Predicted frame – прогнозируемый кадр). MPEG-4 использует технологию фрактального сжатия изображений. Фрактальное (контурно-основанное) сжатие подразумевает выделение из изображения контуров и текстур объектов. Контуры представляются в виде сплайнов (полиномиальных функций) и кодируются опорными точками [7, с. 13].

Текстуры могут быть представлены в виде коэффициентов пространственного частотного преобразования (например, дискретного косинусного или вейвлет-преобразования). Форматы файлов Microsoft AVI и MKV – контейнеры, предназначенные для хранения видеоинформации, синхронизованной с аудиоинформацией. AVI 20 может содержать в себе потоки 4 типов – Video, Audio, MIDI, Text. Причем видеопоток может быть только один, тогда как аудио – несколько [2, с.305 ].

Вывод: на сегодняшний день важно понимать и осознавать теоретические основы кодирования различных видов информации, создавать представление о том, как можно кодировать информацию, и для чего это нужно; знакомить с различными способами кодирования; показать разнообразие кодов окружающих человека; обучать и развивать навыки работы с компьютерными программами, средами; развивать умение анализировать; объединять знания, выделять основное [16, с. 99].

1.2 Классификация назначения и способы представления кодов

Коды можно классифицировать по различным признакам:

1. По основанию (количеству символов в алфавите): бинарные (двоичные m=2) и не бинарные (m № 2).

2. По длине кодовых комбинаций (слов): равномерные, если все кодовые комбинации имеют одинаковую длину и неравномерные, если длина кодовой комбинации не постоянна [20, с. 55].

3. По способам передачи: последовательные и параллельные; блочные - данные сначала помещаются в буфер, а потом передаются в канал и бинарные непрерывные.

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

5. В зависимости от назначения и применения условно можно выделить следующие типы кодов:

Внутренние коды - это коды, используемые внутри устройств. Это машинные коды, а также коды, базирующиеся на использовании позиционных систем счисления (двоичный, десятичный, двоично-десятичный, восьмеричный, шестнадцатеричный и др.). Наиболее распространенным кодом в ЭВМ является двоичный код, который позволяет просто реализовать аппаратное устройства для хранения, обработки и передачи данных в двоичном коде. Он обеспечивает высокую надежность устройств и простоту выполнения операций над данными в двоичном коде. Двоичные данные, объединенные в группы по 4, образуют шестнадцатеричный код, который хорошо согласуется с архитектурой ЭВМ, работающей с данными кратными байту (8 бит) [6, с. 23].

Коды для обмена данными и их передачи по каналам связи. Широкое распространение в ПК получил код ASCII (American Standard Code for Information Interchange). ASCII - это 7-битный код буквенно-цифровых и других символов. Поскольку ЭВМ работают с байтами, то 8-й разряд используется для синхронизации или проверки на четность, или расширения кода. В ЭВМ фирмы IBM используется расширенный двоично-десятичный код для обмена информацией EBCDIC (Extended Binary Coded Decimal Interchange Code). В каналах связи широко используется телетайпный код МККТТ (международный консультативный комитет по телефонии и телеграфии) и его модификации (МТК и др.).^[9]

При кодировании информации для передачи по каналам связи, в том числе внутри аппаратным трактам, используются коды, обеспечивающие максимальную скорость передачи информации, за счет ее сжатия и устранения избыточности (например: коды Хаффмана и Шеннона-Фано), и коды обеспечивающие достоверность передачи данных, за счет введения избыточности в передаваемые сообщения (например: групповые коды, Хэмминга, циклические и их разновидности) [13, с. 10].

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

В зависимости от применяемых методов кодирования, используют различные математические модели кодов, при этом наиболее часто применяется представление кодов в виде: кодовых матриц; кодовых деревьев; многочленов; геометрических фигур и т.д. Рассмотрим основные способы представления кодов [4, с. 47].

Матричное представление кодов. Используется для представления равномерных n - значных кодов. Для примитивного (полного и равномерного) кода матрица содержит n - столбцов и 2n - строк, т.е. код использует все сочетания. Для помехоустойчивых (корректирующих, обнаруживающих и исправляющих ошибки) матрица содержит n - столбцов (n = k+m, где k-число информационных, а m - число проверочных разрядов) и 2k - строк (где 2k - число разрешенных кодовых комбинаций). При больших значениях n и k матрица будет слишком громоздкой, при этом код записывается в сокращенном виде.^[10] Матричное представление кодов используется, например, в линейных групповых кодах, кодах Хэмминга и т.д.

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

Вывод по первой главе: в первой части курсовой рассмотрено понятия теории кодирования и классификация назначения и способы представления кодов. Кодирование - это преобразование сообщений в сигнал, т.е. преобразование сообщений в кодовые комбинации. Цели кодирования:

1) Повышение эффективности передачи данных, за счет достижения максимальной скорости передачи данных.

2) Повышение помехоустойчивости при передаче данных.

ГЛАВА 2. МЕТОДЫ КОДИРОВАНИЯ ДАННЫХ

2.1 Метод кодирования Хаффмана

Метод кодирования или сжатия информации на основе двоичных кодирующих деревьев был предложен Д.А. Хаффманом в 1952 году задолго до появления современного цифрового компьютера. Обладая высокой эффективностью, он и его многочисленные адаптивные версии лежат в основе многих методов, используемых в современных алгоритмах кодирования. Код Хаффмана редко используется отдельно, чаще работая в связке с другими алгоритмами кодирования. Метод Хаффмана является примером построения кодов переменной длины, имеющих минимальную среднюю длину. Этот метод производит идеальное сжатие, то есть сжимает данные до их энтропии, если вероятности символов точно равны отрицательным степеням числа 2 [3, с. 26].

Этот метод кодирования состоит из двух основных этапов:

· Построение оптимального кодового дерева.

· Построение отображения код-символ на основе построенного дерева.

Алгоритм основан на том, что некоторые символы из стандартного 256-символьного набора в произвольном тексте могут встречаться чаще среднего периода повтора, а другие - реже. Следовательно, если для записи распространенных символов использовать короткие последовательности бит, длиной меньше 8, а для записи редких символов - длинные, то суммарный объем файла уменьшится. В результате получается систематизация данных в виде дерева («двоичное дерево»).^[11]

Пусть A={a1,a2,...,an} - алфавит из n различных символов, W={w1,w2,...,wn} - соответствующий ему набор положительных целых весов. Тогда набор бинарных кодов C={c1,c2,...,cn}, такой что: [11, с. 50]

- ci не является префиксом для cj, при i!=j; минимальна (|ci| длина кода ci) называется минимально-избыточным префиксным кодом или иначе кодом Хаффмана.

Бинарным деревом называется ориентированное дерево, полустепень исхода любой из вершин которого не превышает двух [11, с. 51].

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

Пусть Т- бинарное дерево, А=(0,1)- двоичный алфавит и каждому ребру Т-дерева приписана одна из букв алфавита таким образом, что все ребра, исходящие из одной вершины, помечены различными буквами. Тогда любому листу Т-дерева можно приписать уникальное кодовое слово, образованное из букв, которыми помечены ребра, встречающиеся при движении от корня к соответствующему листу. Особенность описанного способа кодирования в том, что полученные коды являются префиксными [3, с. 19].

Очевидно, что стоимость хранения информации, закодированной при помощи Т-дерева, равна сумме длин путей из корня к каждому листу дерева, взвешенных частотой соответствующего кодового слова или длиной взвешенных путей: где - частота кодового слова длины во входном потоке. Рассмотрим в качестве примера кодировку символов в стандарте ASCII. Здесь каждый символ представляет собой кодовое слово фиксированной(8 бит) длины, поэтому стоимость хранения определится выражением , где W- количество кодовых слов во входном потоке.^[12]

Поэтому стоимость хранения 39 кодовых слов в кодировке ASCII равна 312, независимо от относительной частоты отдельных символов в этом потоке. Алгоритм Хаффмана позволяет уменьшить стоимость хранения потока кодовых слов путем такого подбора длин кодовых слов, который минимизирует длину взвешенных путей. Будем называть дерево с минимальной длиной путей деревом Хаффмана [18, с. 64].

Классический алгоритм Хаффмана на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево).

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

2. Выбираются два свободных узла дерева с наименьшими весами;

Создается их родитель с весом, равным их суммарному весу;

Родитель добавляется в список свободных узлов, а два его потомка удаляются из этого списка;

Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой - бит 0;

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

На первом шаге из листьев дерева выбираются два с наименьшими весами - Г и Д. Они присоединяются к новому узлу- родителю, вес которого устанавливается 5+6= 11. Затем узлы Г и Д удаляются из списка свободных. Узел Г соответствует ветви 0 родителя, узел Д - ветви 1. [7, с. 51]

На следующем шаге то же происходит с узлами Б и В, так как теперь эта пара имеет самый меньший вес в дереве. Создается новый узел с весом 13, а узлы Б и В удаляются из списка свободных.

На следующем шаге «наилегчайшей» парой оказываются узлы Б/В и Г/Д.

Для них еще раз создается родитель, теперь уже с весом 24. Узел Б/В соответствует ветви 0 родителя, Г/Д - ветви 1. [4, с. 33]

На последнем шаге в списке свободных осталось только 2 узла - это узел А и узел Б (Б/В)/(Г/Д). В очередной раз создается родитель с весом 39, и бывшие свободные узлы присоединяются к разным его ветвям.^[13]

Поскольку свободным остался только один узел, то алгоритм построения дерева кодирования Хаффмана завершается.

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

Алгоритм декодирования предполагает просмотр потоков битов и синхронное перемещение от корня вниз по дереву Хаффмана в соответствии со считанным значением до тех пор, пока не будет достигнут лист, то есть декодировано очередное кодовое слово, после чего распознавание следующего слова вновь начинается с вершины дерева. [2, с. 20]

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

2.2 Постановка задачи кодирования

Реализация основных характеристик канала связи помимо разработки технических устройств, требует решения информационных задач – выбор оптимального метода кодирования [19, с. 40].

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

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

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

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

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

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

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

3. Алфавита знаков и способа кодирования (побуквенного, блочного).

Полагается, что сообщение источника информации формируется из знаков аi, i=1,2,.. Na внешнего (входного, первичного) алфавита А объемом Na. Сообщения представляют собой слова, образованные последовательностью nr знаков: Ar =a1a2…anr. В кодирующем устройстве слово Ar преобразуется в кодовое слово Br=b1b2…bmr, составленное из mr знаков bj , j=1,2,..Nb внутреннего (выходного, вторичного) алфавита В. Число знаков кодового алфавита называют основанием кода. Число знаков в кодовом слове называют длиной кодового слова.^[14] Отображение G множества слов в алфавите А на множество слов в алфавите В называют кодирующим отображением или кодом. Применение кодирующего отображения G к любому слову из входного алфавита называется кодированием. То есть код - это правило отображения знаков одного алфавита в знаки другого алфавита, кодирование – это преобразование одной формы сообщения в другую посредством указанного кода [4, с. 58].

Различают побуквенное и блочное кодирование. При побуквенном кодировании каждому знаку внешнего алфавита ставиться в соответствие кодовое слово из знаков внутреннего алфавита [4, с. 62].

При блочном кодировании слову из знаков внешнего алфавита ставиться в соответствие кодовое слово из знаков внутреннего алфавита.

Cлова из знаков внутреннего алфавита В, сопоставленные словам из знаков внешнего алфавита А по правилу G, называются кодовыми комбинациями. Если ArE A и G(Ar)= Br, то говорят, что слову Ar соответствует кодовая комбинация Br. Совокупность кодовых комбинаций используемых для передач заданного количества дискретных сообщений называют кодовым словарем [14, с. 105].

Процесс, обратный кодированию, заключается в восстановлении из кодовой комбинации Br=b1b2…bmr слова Ar=a1a2…anr из входного алфавита и называется декодированием. Если процесс кодирования осуществляется с использованием правила G, то процесс декодирования основан на применении правила G-1, где G-1 есть отображение, обратное отображению G. Операции кодирования и декодирования называют обратимыми, если их последовательное применение обеспечивает возврат к исходной форме сообщения без потери информации.

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

Примером необратимого кодирования является перевод текста с одного естественного языка на другой. ^[15]

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

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

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

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

ЗАКЛЮЧЕНИЯ

Таким образом, в ходе проведенного исследования пришли к следующим выводам:

1. Одним из разделов информатики является раздел, связанный с изучением вопросов представления и кодирования информации. Кодирование информации – это процесс формирования определенного представления информации. В более узком смысле под термином «кодирование» часто понимают переход от одной формы представления информации к другой, более удобной для хранения, передачи или обработки. Получение и преобразование, т.е. кодирование информации, является условием жизнедеятельности любого организма.
2. Существуют различные методы декодирования и кодирования информации в компьютере. Эти методы зависят от вида информации: графическое изображение, текст, звук или число. Также для числа важно, как оно будет использовано: в вычислениях или тексте, или в процессе ввода-вывода. Вся эта информация с помощью цифр 0 и 1 кодируется в бинарной системе счисления.
3. Важно понимать и осознавать теоретические основы кодирования различных видов информации, создавать представление о том, как можно кодировать информацию, и для чего это нужно; знакомить с различными способами кодирования; показать разнообразие кодов окружающих человека; обучать и развивать навыки работы с компьютерными программами, средами; развивать умение анализировать; объединять знания, выделять основное.
4. Проблема кодирования информации, имеет достаточно давнюю историю, гораздо более давнюю, нежели история развития вычислительной техники, которая обычно шла параллельно с историей развития проблемы сжатие и шифровки информации.
5. До появления работ Шеннона, Фано а позже и Хаффмана, кодирование символов алфавита при передаче сообщения по каналам связи осуществлялось одинаковым количеством бит, получаемым по формуле Хартли. С появлением этих работ начали появляться способы, кодирующие символы разным числом бит в зависимости от вероятности появления их в тексте, то есть более вероятные символы кодируются короткими кодами, а редко встречающиеся символы - длинными (длиннее среднего).

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

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Алехина Г. В. Информатика. Базовый курс [Текст]: учебное пособие / Под ред. Г. В. Алехиной. - 2-е изд., доп. и перераб. - М.: Маркет ДС Корпорейшн, 2015. - 731 с.

2. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. – М.: Мир, 2018. – 590 с.

3. Блейхут Р. Теория и практика кодов, исправляющих ошибки. – М.: Мир, 2017. – 576 с.

4. Вернер М. Основы кодирования. Учебник для ВУЗов. – М.: Техносфера, 2014. – 288 с.

5. Скляр Б. Цифровая связь. Теоретические основы и практическое применение. – М.: Издательский дом «Вильямс», 2017. – 1104 с.

6. Поляков А.К. Языки VHDL и Verilog в проектировании цифровой аппаратуры. – М.: СОЛОН-Пресс, 2016. – 320 с.

7. Стешенко В.Б. ПЛИС фирмы ALTERA: проектирование устройств обработки сигналов. – М.: ДОДЭКА, 2014.-128 с.

8. Максфилд К. Проектирование на ПЛИС. Курс молодого бойца. – М.: Издательский дом «ДОДЭКА - XXI», 2017. – 408 с.

9. Поляков А.. Тайлеб М., Тайлеб Н. Библиотека Verilog – описаний арифметических операций в поле Галуа. // Проектирование и моделирование. 2017, №5. 46-48 с.

10. Владимиров С.С. Математические основы теории помехоустойчивого кодирования: учебное пособие. СПбГУТ. – СПб, 2016. – 96 с. 54

11. Гавриков, М.М. Теоретические основы разработки и реализации языков программирования / М.М. Гавриков, А.Н. Иванченко. - М.: КноРус, 2018. - 207 c.

12. Гавриков, М.М. Теоретические основы разработки и реализации языков программирования: Учебное пособие / М.М. Гавриков, А.Н. Иванченко, Д.В. Гринченков. - М.: КноРус, 2015. - 184 c.

13. Голицына, О.Л. Основы алгоритмизации и программирования: Учебное пособи / О.Л. Голицына, И.И. Попов. - М.: Форум, 2014. - 205 c.

14. Емельянов, В.И. Основы программирования на Delphi. / В.И. Емельянов. - М.: Высшая школа, 2015. - 231 c.

15. Гулиа, Н.В. Основы вычислений и программирования в пакете MathCAD PRIME: Учебное пособие / Н.В. Гулиа, В.Г. Клоков, С.А. Юрков. - СПб.: Лань, 2016. - 224 c.

16. Гуриков, С.Р. Основы алгоритмизации и программирования на Python: Учебное пособие / С.Р. Гуриков. - М.: Форум, 2018. - 384 c.

17. Зыков, С.В. Основы современного программирования: Учебное пособие для вузов / С.В. Зыков. - М.: ГЛТ , 2015. - 444 c.

18. Колдаев, В.Д. Основы алгоритмизации и программирования: Учебное пособие / В.Д. Колдаев; Под ред. Л.Г. Гагарина. - М.: ИД Форум, Инфра-М, 2016. - 416 c.

19. Культин, Н.Б. Основы программирования в Turbo Delphi / Н.Б. Культин. - СПб.: BHV, 2014. - 384 c.

20. Парфилова, Н.И. Программирование: Основы алгоритмизации и программирования: Учебник / Н.И. Парфилова; Под ред. Трусова Б.Г. - М.: Academia, 2018. - 32 c.

ПРИЛОЖЕНИЯ

Таблица 1. Виды информации

Вид информации	Форма представления
Числовая	Количественная мера объектов и их свойств в окружающем мире; в особенности значимую роль обрела с развитием торговли, экономики и денежного обмена; подобно текстовой информации для её отображения применяется метод кодирования специальными символами — цифрами, при этом системы кодирования (счисления) могут быть разными.
Текстовая	Наибольшее значение этот способ приобрел после появления бумаги и книгопечатания. Сюда относятся способы кодирования речи человека особыми символами — буквами, при этом не нужно забывать, что разные народы имеют разные языки и используют различные наборы букв для отображения речи.
Графическая	Вид, с целью которого был реализован способ хранения информации об окружающем мире в виде наскальных рисунков, а также в виде картин, фотографий, схем, чертежей на бумаге, холсте, мраморе и других материалах, изображающих картины реального мира.
Звуковая	Количество бит, которое отводится на один звуковой сигнал, называют глубиной кодирования звука. Современные звуковые карты обеспечивают 16-, 32- или 64-битную глубину кодирования звука. При кодировании звуковой информации непрерывный сигнал заменяется дискретным, то есть превращается в последовательность электрических импульсов (двоичных нулей и единиц).
Видео	Один из способов сохранения «живых» картин окружающего мира, возникший с появлением кинематографа.

Таблица 2. Соответствие символов

Двоичный код	Десятичный код	КОИ8	СР1251	СР866	Мас	ISO
11000010	194	б	В	-	-	Т

А	К	Достаточно для…
8	28 = 256	Нарисованных изображений как те, что мы можем увидеть в мультфильмах, но этого недостаточно для изображений живой природы.
16 (HighColor)	216 = 65536	Изображений, которые находятся на картинках в журналах и на фотографиях
24 (TrueColor)	224= 16 777 216	Обработки и передачи изображений, не уступающих по качеству, которые мы можем наблюдать в живой природе

Таблица 3. Соответствие между количеством отображаемых цветов (К) и количеством бит для их кодировки

1. Алехина Г. В. Информатика. Базовый курс [Текст]: учебное пособие / Под ред. Г. В. Алехиной. - 2-е изд., доп. и перераб. - М.: Маркет ДС Корпорейшн, 2015. – С. 264. ↑

2. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. – М.: Мир, 2018. – С.53 ↑

3. Скляр Б. Цифровая связь. Теоретические основы и практическое применение. – М.: Издательский дом «Вильямс», 2017. – С.241. ↑

4. Вернер М. Основы кодирования. Учебник для ВУЗов. – М.: Техносфера, 2004. – 288 с. ↑

5. Поляков А.К. Языки VHDL и Verilog в проектировании цифровой аппаратуры. – М.: СОЛОН-Пресс, 2016. – С.145. ↑

6. Владимиров С.С. Математические основы теории помехоустойчивого кодирования: учебное пособие. СПбГУТ. – СПб, 2016. – 96 С. 54 ↑

7. Гавриков, М.М. Теоретические основы разработки и реализации языков программирования: Учебное пособие / М.М. Гавриков, А.Н. Иванченко, Д.В. Гринченков. - М.: КноРус, 2015. – С. 146. ↑

8. Емельянов, В.И. Основы программирования на Delphi. / В.И. Емельянов. - М.: Высшая школа, 2015. – С. 218. ↑

9. Зыков, С.В. Основы современного программирования: Учебное пособие для вузов / С.В. Зыков. - М.: ГЛТ , 2015. – С.145. ↑

10. Культин, Н.Б. Основы программирования в Turbo Delphi / Н.Б. Культин. - СПб.: BHV, 2014. – С.246. ↑

11. Парфилова, Н.И. Программирование: Основы алгоритмизации и программирования: Учебник / Н.И. Парфилова; Под ред. Трусова Б.Г. - М.: Academia, 2018. – С.15. ↑

12. Гулиа, Н.В. Основы вычислений и программирования в пакете MathCAD PRIME: Учебное пособие / Н.В. Гулиа, В.Г. Клоков, С.А. Юрков. - СПб.: Лань, 2016. – С. 59. ↑

13. Колдаев, В.Д. Основы алгоритмизации и программирования: Учебное пособие / В.Д. Колдаев; Под ред. Л.Г. Гагарина. - М.: ИД Форум, Инфра-М, 2016. – С. 315. ↑

14. Культин, Н.Б. Основы программирования в Turbo Delphi / Н.Б. Культин. - СПб.: BHV, 2014. – С.254. ↑

15. Гавриков, М.М. Теоретические основы разработки и реализации языков программирования: Учебное пособие / М.М. Гавриков, А.Н. Иванченко, Д.В. Гринченков. - М.: КноРус, 2015. – С. 156. ↑