Содержание:

Введение

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

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

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

Глава 1 Кодирование данных

Раздел 1 Понятие кода и кодирования данных

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

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

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

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

Раздел 2 Актуальность

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

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

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

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

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

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

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

Глава 2

Раздел 1 Обзор и классификации методов кодирования данных

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

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

Представление целых чисел производиться с помощью их кодирования в двоичной системе счисления: в таком виде они и записываются в ячейке. Один бит доступен при этом для представления знака числа (нулем записывается знак "плюс", единицей – "минус").

Для представления действительных чисел применяется особый формат чисел с плавающей запятой. Число при этом кодируется в виде: где M – мантисса, p – порядок числа N, q – основание системы счисления. Если при этом мантисса M подчиняется условию , то число N называют нормализованным.

Кодирование текста

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

Существующий стандарт ASCII (American Standard Code for Information Intercange – американский стандартный код для обмена информацией; 8 – разрядная система кодирования) содержит в себе две таблицы кодирования – расширенную и базовую. Одна таблица содержит 128 символов, в ней размещены коды символов английского алфавита, а во второй таблице кодирования содержатся расширенные символы в количестве 128 штук.

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

Например, кодировка символов русского языка Windows – 1251 применяется для компьютеров, работающих под ОС Windows. Альтернативная кодировка для русского языка – это КОИ – 8, которая также широко используется в российском секторе Интернет и в компьютерных сетях.

В настоящее время получает распространение универсальная система UNICODE, которая основанная на 16 – разрядном кодировании символов. Эта 16 – разрядная система позволяет присвоить универсальные коды для 65536 различных символов, т.е. в этой таблице размещаются символы языков большинства стран мира.

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

• использующие Симметричное шифрование. Заключается в том, что обе стороны-участники обмена данными имеют идентичные ключи для шифрования и расшифровки данных. Этот способ осуществляет преобразование, позволяющее предотвратить получение доступа к информации третьей стороной.
• использующие Асимметричное шифрование. Используются в паре два разных ключа — открытый и секретный. В асимметричном шифровании ключи работают в связке— если данные зашифрованы секретным ключом, то расшифровать их можно только соответствующим открытым ключом и наоборот — если данные шифруются открытым ключом, то расшифровать их можно только соответствующим секретным ключом. Использовать непарные открытый и секретный ключи — невозможно. Пары асимметричных ключей связаны математическими зависимостями.
• использующие Хеширование. Входной массив данных произвольной длины преобразуется в выходную битовую строку фиксированной длины. Такие преобразования также называются хеш-функциями или функциями свертки, хеш-кодом, контрольной суммой или дайджестом сообщения называют их результаты. Результаты хэширования всегда статистически уникальны. Последовательность, различающаяся хотя бы одним байтом, никогда не будет преобразована в то же самое значение.

Распространенные алгоритмы:

• симметричные DES, AES, ГОСТ 28147-89, Camellia, Twofish, Blowfish, IDEA, RC4 и др.;
• асимметричные RSA и Elgamal (Эль-Гамаль);
• хэш-функций MD4, MD5, MD6, SHA-1, SHA-2, ГОСТ Р 34.11-2012 («Стрибог») .

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

Все изображения за небольшим исключением можно разделить на две большие группы – растровую и векторную графику.

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

Для кодирования черно-белых изображений применяются оттенки серого цвета, то есть при кодировании учитывается только яркость. Она записывается одним числом, следовательно для записи одного пикселя требуется от 1 до 8 бит, где чёрный цвет – 0, белый цвет – N = 2^k-l, где k – количество разрядов, которые отводятся для записи цвета. Пример, при длине ячейки в 8 бит это 256-1 = 255.

Цветные изображения кодируются как сумма трёх основных цветов – зелёного,красного и синего. Поэтому достаточно записать цвет тремя числами – яркостью его красной, зелёной и синей составляющих. Этот способ кодирования имеет название RGB (Red – Green – Blue). Его применяют в устройствах, излучающих свет, например компьютерных мониторах, телевизорах и экранах других гаджетов. Для реальных красок действуют иные правила, потому как они сами по себе не излучают свет, а только поглощают цвета спектра. Исходя из этого при печати цветных изображений применяется метод CMY (Cyan – Magenta – Yellow) – голубой, сиреневый, жёлтый цвета.

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

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

Кодирование звука

Музыка представляет из себя колебания звука. Записав и преобразовав которые можно получить последовательность нулей и единиц. Этот процесс называется дискретизацией. Прибор для выполнения дискретизации называется аналогово-цифровым преобразователем (АЦП). Воспроизведение такого звука производится при помощи цифро-аналогового преобразователя (ЦАП). Полученный в итоге сигнал выравнивается и преобразуется в звук при помощи усилителей и динамиков. На качество звучания влияют частота дискретизации и разрешение (размер ячейки, выделенной под запись значения амплитуды). К примеру, при записи музыки на диски используются 16-разрядные значения и частота дискретизации 48 кГц. [4]

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

Уже достаточно давно используется весьма компактный вариант представления музыки – нотная запись. В ней с помощью специальных символов указывается высота и длительность, а также общий темп исполнения мелодии. В целом, подобную запись можно назвать алгоритмом для исполнителя, записанным на специальном формальном языке. В 1983 г. передовые производители компьютеров и музыкальных синтезаторов разработали стандарт, определивший такую систему кодов. Он получил название MIDI (Musical Instrument Digital Interface). [4] При таком кодировании запись компактна, достаточно легко меняется инструмент музыканта, тональность звука. Одна и та же запись может воспроизводиться как на компьютере, так и на синтезаторе.

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

Есть и другие форматы записи музыки. Среди них – формат MP3, дающий возможность с весьма большим качеством и степенью сжатия кодировать музыку, при этом вместо 18 – 20 музыкальных композиций на стандартном компакт-диске (CDROM) помещается около 200. Одна песня занимает примерно 3,5 Mb, что позволяет пользователям сети Интернет непринужденно обмениваться музыкальными композициями.

Раздел 2 Кодирование текста

Шифр Вижинера

В 1467 году итальянский ученый Леон Альберти впервые задокументировал описание многоалфавитного шифра. Для переключения между алфавитами использовался металлический шифровальный диск. Эта система переключает алфавиты после нескольких зашифрованных слов. Позднее, в 1518 году, Иоганн Трисемус в своем труде «Полиграфия», посвященном криптологии, изобрел tabula recta - центральный компонент шифра Виженера.[6] Представляет собой алфавитную таблицу, каждая строка которой циклически сдвигается.

В 1586 году Блез Виженер представил собственное описание простого, однако, при этом невероятно стойкого к ручному взлому шифра перед комиссией Генриха III во Франции. Немногим позже именно Вижинеру было присвоено изобретение шифра. Давид Кан в своей книге «Взломщики кодов» отозвался об этом критически, написав, что история «проигнорировала важный факт и назвала шифр именем Виженера, несмотря на то, что он ничего не сделал для его создания». [7]

Известный математик Чарльз Доджсон в 1916 году отозвался о шифре Виженера как о не взламываемом в своей статье «Алфавитный шифр», такого же мнения был и Scientific American в 1917 году. Это представление было полностью опровергнуто Фридрихом Касиски в XIX веке, после того, как он сумел полностью взломал шифр. Хотя известны случаи взлома этого шифра некоторыми опытными криптоаналитиками еще в XVI веке. [6]

Шифр Виженера очень прост в использовании, особенно в случае применения шифровальных дисков: к примеру, медный шифровальный диск для шифра Виженера использовался в ходе Гражданской войны в Америке. [8]

Гилберт Вернам улучшал взломанный шифр (он получил название шифр Вернама-Виженера в 1918 году), но, несмотря на его работу, шифр попрежнему продолжал быть уязвимым к криптоанализу. Несмотря на это работа Вернама в финале позволила получить шифр, который по-настоящему сложно взломать.

Шифр Цезаря

В I в до н. э. Гай Юлий Цезарь во время войны с галлами, в переписке со своими сторонниками в Риме, заменял в тексте первую букву латинского алфавита (А) на четвертую (D), вторую (В) - на пятую (Е), наконец, последнюю - на третью.

Сообщение об одержанной им победе выглядело так: YHQL YLGL YLFL «Veni, vidi, vici» - «Пришел, увидел, победил» (лат.).

Шифр Цезаря, также известный как шифр сдвига, код Цезаря или сдвиг Цезаря - является одним из самых простых и является самым известным из методов шифрования.

Шифр Цезаря - это разновидность шифра подстановки, в нем каждый символ в изначальном тексте заменяется символом находящимся на некоторой постоянной позиций праве или левее него в алфавите. К примеру, в шифре со сдвигом 3, А будет заменена на Г, Б превратится в Д, и так далее.

Этот шифр назван в честь римского императора Гая Юлия Цезаря, применившего его для секретной передачи информации своим генералам. Древнеримский историк Светоний не называет примеров вскрытия переписки Цезаря. Сам Цезарь всегда применял один и тот же ключ (сдвиг - 3). Этот способ он применял, в частности, для частной переписки с Цицероном.[Пример данного шифра приведен в приложении 1]

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

В 19-ом столетии, раздел рекламных объявлений в газетах иногда применялась, для того чтобы обмениваться сообщениями, шифрованными с использованием легких шифров. Кан (1967) описывает события когда любители принимали участие в секретном общении, шифруя свои сообщения с применением шифра Цезаря в "Таймс". Даже позднее, в 1915, шифр Цезаря применялся: в российской армии использовался как замена для более сложных шифров, которые были сложными в использовании для войск; у немецких и австрийских криптоаналитиков были незначительные сложности при декодировании таких сообщений.

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

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

Шифр RSA

RSA - криптографическая система открытого ключа, обеспечивающая такие механизмы защиты как шифрование и цифровая подпись (аутентификация - установление подлинности). Криптосистема RSA разработана в 1977 году и названа в честь ее разработчиков Ronald Rivest, Adi Shamir и Leonard Adleman.

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

Алгоритм RSA строится по схеме:

1. Взять два достаточно больших простых числа p и q

2. Вычислить n = p * q

3. Вычислить m = (p - 1) * (q - 1)

4. Взять число d взаимно простое с m

5. Взять число e так, чтобы e * d = 1 (mod m)

Числа e и d являются ключами RSA. Шифруемые данные необходимо разбить на блоки - числа от 0 до n - 1. Шифрование и дешифровка данных производятся следующим образом:

· Шифрование: b = ae (mod n)

· Дешифровка: a = bd (mod n)

Интересно также то , что ключи e и d равнозначны, т.е. сообщение можно зашифровать как ключом e, так и ключом d, при этом расшифровка производиться при помощью второго ключа.

Алгоритм RSA намного медленнее чем DES и прочие алгоритмы блокового шифрования. Программная реализация DES работает быстрее по меньшей мере в 100 раз и от 1,000 до 10,000 - в аппаратной реализации (в зависимости от конечного устройства). Благодаря разработкам, работа алгоритма RSA, вероятно, ускорится, но аналогично ускорится и работа алгоритмов блокового шифрования.

Раздел 3 Кодирование изображений

JPEG

Самое большое отличие формата JPEG от других форматов состоит в том, что в JPEG используется алгоритм кодирования с потерями (а не алгоритм без потерь) информации.

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

Декодированное изображение JPEG далеко не всегда соответствует исходному на 100%, но достаточно часто эти различия столь малозаметны, что их едва можно обнаружить.

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

Первым шагом изображение делится на квадраты со стороной размером 8 пикселов. Далее производится кодирование каждого квадрата отдельно за три этапа.

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

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

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

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

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

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

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

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

С другой стороны, применяя методы сжатия без потерь, можно сжимать некоторые изображения на 90%. Такие изображения плохо подходят для сжатия методом JPEG.

При использовании сжатия методом JPEG потери информации обычно происходят на втором этапе процесса.

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

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

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

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

Коэффициент архивации в JPEG может изменяться в пределах от 2 до 200 раз. Как и у любого другого алгоритма сжатия с потерями, у JPEG свои особенности.

Наиболее известны "эффект Гиббса" и дробление изображения на квадраты 8х8.

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

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

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

Этот “узор” возникает при наложении наклонного растра печати на полосы изображения.

Из-за таких “сюрпризов” JPEG не рекомендуется активно использовать в полиграфии, задавая высокие показатели коэффициента сжатия.

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

Широкое применение JPEG сдерживается, пожалуй, лишь тем, что он оперирует 24-битными изображениями.

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

В приложениях, ориентированных на взыскательного пользователя, таких, например, как современные игры класса ААА, подобные задержки неприемлемы.

Кроме того, если имеющиеся у вас изображения, допустим, в 8-битном формате GIF перевести в 24-битный JPEG, а потом обратно в GIF для просмотра, то потеря качества произойдет дважды при обоих преобразованиях.

Тем не менее выигрыш в размерах архивов зачастую настолько велик (в 3-20 раз!), а потери качества настолько малы, что хранение изображений в JPEG оказывается очень эффективным. JPEG-сжатие реализовано в форматах JPG и TIFF.

Стоит также уделить внимание модификациям этого алгоритма. Хотя JPEG и является стандартом ISO, формат файла не был строго зафиксирован.

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

Так, внутренние таблицы алгоритма, рекомендованные ISO, заменяются ими на свои собственные.

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

К примеру, при проведении тестов выясняется, что "отличное" качество, "100%" и "0 баллов", на выходе дают кардинально различающиеся картинки.

При этом, кстати, "100%" качества означает сжатия с потерей информации.

BMP

По решению разработчиков формат Bmp-файла не привязан к конкретной аппаратной платформе. Этот файл состоит из четырех частей: заголовка, информационного заголовка, таблицы цветов (палитры) и данных изображения. Если в файле хранится изображение с глубиной цвета 24 бита (16 млн. цветов), то таблица цветов может отсутствовать, однако в нашем, 256-цветном случае она есть.

Заголовок файла начинается с сигнатуры «BM», а затем идет длина файла, выраженная в байтах. Следующие 4 байта зарезервированы для дальнейших расширений формата, а заканчивается этот заголовок смещением от начала файла до записанных в нем данных изображения. При 256 цветах это смещение составляет 1078.

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

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

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

Глубина цвета является важнейшей характеристикой способа представления цвета в файле и измеряется в битах на точку.

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

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

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

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

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

За информационным заголовком следует таблица цветов, представляющая собой массив из 256 (по числу цветов) 4-байтовых полей. Каждое из полей соответствует своему цвету в палитре, а три байта из четырех -- компонентам синей, зеленой и красной составляющих для этого цвета. Последний, самый старший байт каждого поля зарезервирован и равен 0.

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

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

Раздел 4 Кодирование звука

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

Кодирование в формате Mp3

Формат MP3 разработан группой института Фраунгофера под руководством Карлхайнца Бранденбурга и университета Эрланген-Нюрнберг в сотрудничестве с AT&T Bell Labs и Thomson Основой разработки этого формата послужил экспериментальный кодек ASPEC (Adaptive Spectral Perceptual Entropy Coding). Первым кодировщиком в формат MP3 стала программа L3Enc, выпущенная в 1994 году. Год спустя появился первый программный MP3-плеер — Winplay3.

В процессе разработки алгоритма тесты проводились на вполне конкретных популярных композициях. Основной стала песня Сюзанны Веги «Tom’s Diner». Из чего появилась шутливое выражение, что «MP3 был создан только ради комфортного прослушивания одной из любимых песен Бранденбурга», а Сюзанну стали называть «мамой MP3».

Почти полный стандарт появился в открытом доступе 6 декабря 1991 года.

23 апреля 2017 года истекли последние патенты на формат и были прекращены сборы лицензионных отчислений с производителей программного обеспечения и встраиваемых решений. О прекращении лицензирования формата сообщил Институт Фраунгофера на своём официальном сайте. И, хотя формат mp3 всё ещё весьма популярен среди пользователей, большинство радиостанций и телеканалов перешли на использование более современных кодеков, обеспечивающих лучшее сжатие при меньшей потере качества звукозаписи.

Структура Mp3 файла

MP3-файл состоит из нескольких фрагментов (называемых фреймами) MP3, которые, в свою очередь, состоят из заголовка и блока данных. Эта последовательность фрагментов называется элементарным потоком. Фрагменты же не являются независимыми элементами («резервуар байт»), и поэтому не могут быть извлечены произвольно. Блок данных MP3-файла содержит сжатую аудиоинформацию в виде частот и амплитуд. Сам заголовок MP3 состоит из маркера, который служит для нахождения верного MP3-фрагмента. За ним следует бит, показывающий, что используется стандарт MPEG, и два бита, показывающие использование layer 3; другими словами, это определяет MPEG-1 Audio Layer 3 или MP3. Последующие значения могут варьироваться в зависимости от типа MP3-файла. Стандарт ISO/IEC 11172-3 определяет диапазон значений для каждой секции заголовка, вместе с общей его спецификацией. Большинство MP3-файлов в настоящий момент содержат ID3-метаданные, которые предшествуют или следуют за MP3-фрагментом.

FLAC

FLAC (англ. Free Lossless Audio Codec) — популярный свободный кодек, предназначенный для сжатия аудиоданных без потерь.

В отличие от аудиокодеков, обеспечивающих сжатие с потерями (MP3, AAC, WMA, Ogg Vorbis, Opus), FLAC, как и любой другой lossless-кодек, не удаляет никакой информации из аудиопотока и подходит как для прослушивания музыки на высококачественной звуковоспроизводящей аппаратуре, так и для архивирования аудио.

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

Аудиопоток

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

• Строка из четырёх байтов «fLaC»
• Блок метаданных STREAMINFO
• Другие необязательные блоки метаданных
• Аудиофреймы

Первые четыре байта идентифицируют поток FLAC. Следующие за ними метаданные содержат информацию о потоке, затем идут сжатые аудиоданные.

Метаданные

По состоянию на 10.03.2010 в libflac-1.2.1 определены следующие типы блоков: StreamInfo, Padding, Application, SeekTable, VorbisComment, CueSheet, Picture, Unknown. Блоки метаданных могут быть любого размера, не представляет большого труда добавление новых блоков. Неизвестные блоки метаданных декодер пропускает.

Блок STREAMINFO — является строго обязательным. В нём содержатся данные, позволяющие декодеру настроить буфера, частоту дискретизации, количество каналов, количество бит на семпл и количество семплов. Также в блок записывается подпись MD5 несжатых аудиоданных. Это полезно для проверки всего потока после его передачи.

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

Аудиоданные

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

Разбиение на блоки

Размер блока — крайне важный параметр для кодирования. Если он слишком мал, то в потоке будет чересчур много заголовков фреймов, что уменьшит уровень сжатия. Если же размер большой, то кодер не сможет подобрать эффективную модель сжатия. Понимание процесса моделирования поможет вам увеличить уровень сжатия для некоторых типов входных данных. Обычно при использовании линейного прогнозирования на аудиоданных с частотой дискретизации 44,1 кГц оптимальный размер блока лежит в диапазоне 2-6 тыс. семплов.

Межканальная декорреляция

Если на вход поступают стереоаудиоданные, они могут пройти через стадию межканальной декорреляции. Правый и левый канал преобразуются к среднему и разностному по формулам: средний = (левый + правый)/2, разностный = левый — правый. В отличие от joint stereo, используемом в lossy-кодерах, в lossless-кодировании этот процесс не приводит к потерям. Для данных с аудиодисков это обычно приводит к значительному увеличению уровня сжатия.

Моделирование

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

Остаточное кодирование

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

Кодирование Райса состоит из нахождения одного параметра, отвечающего распределению сигнала, а затем использования его для составления кодов. При изменении распределения меняется и оптимальный параметр, поэтому имеется метод, позволяющий пересчитывать его по необходимости. Остаток может быть разбит на контексты или разделы, у каждого из которых будет свой параметр Райса. FLAC позволяет указать, как нужно производить разбиение. Остаток может быть разбит на 2n разделов.

Составление фреймов

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

Заключение

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

Список Литературы

1. Елена Викторовна Курапова,Елена Павловна Мачикина. ОСНОВНЫЕ МЕТОДЫ КОДИРОВАНИЯ ДАННЫХ. СибГУТИ, 2010
2. Алешин Л.И., Максимов Н.В. Учебное пособие Информационные технологии Москва, 2004
3. Аршинов М.Н., Садовский Л.Е. 'Коды и математика (рассказы о кодировании)' \\Библиотечка 'Квант'. Выпуск 30 - Москва: Наука, 1983 - с.144
4. А.В. Яковлев, А.А. Безбогов, В.В. Родин, В.Н. Шамкин. Криптографическая защита информации. -- Тамбов: Издательство ТГТУ, 2006
5. M. Nilsson The audio/mpeg Media Type — Internet Engineering Task Force, 2000.
6. Математические и компьютерные основы криптологии: учебное пособие / Ю.С.Харин, В.И.Берник, Г.В.Матвеев, С.В.Агиевич. - Мн.: Новое знание, 2003. - 382 с.;
7. David, Kahn. The Codebreakers: The Story of Secret Writing. — Simon & Schuster, 1999. — ISBN 0-684-83130-9.
8. Жельников В. Кpиптогpафия от папиpуса до компьютеpа. -- М.: 1996.
9. Ященко В.В. Введение в криптографию. СПб.: Питер, 2001.
10. Д.С. Ватолин "Алгоритмы сжатия изображений". Методические материалы к спецкурсу ВМиК МГУ "Машинная графика-2" под руководством Ю.М. Баяковского.
11. Бабаш А. В., Шанкин Г. П. История криптографии. Часть I.
12. Бабаш А. В., Шанкин Г. П. История криптографии. Часть II.

Приложение 1

Зашифруем фразу “Пример текста зашифрованного шифром Цезаря” с помощью шифра Цезаря. Для русского текста получим 32 варианта записи шифровки. Варианты приведены в таблице ниже:

ROT0	Пример текста зашифрованного шифром Цезаря
ROT1	Рсйнёс уёлтуб ибщйхспгбоопдп щйхспн Чёибса
ROT2	Сткожт фжмуфв йвъкцтрдвппрер ъкцтро Шжйвтб
ROT3	Тулпзу хзнфхг кгылчусегррсёс ылчусп Щзкгув
ROT4	Уфмриф циохцд лдьмшфтёдсстжт ьмшфтр Ъилдфг
ROT5	Фхнсйх чйпцче меэнщхужеттузу энщхус Ыймехд
ROT6	Хцоткц шкрчшё нёюоъцфзёууфиф юоъцфт Ькнёце
ROT7	Цчпулч щлсшщж ожяпычхижффхйх япычху Эложчё
ROT8	Чшрфмш ъмтщъз пзарьшцйзххцкц арьшцф Юмпзшж
ROT9	Шщсхнщ ынуъыи рибсэщчкиццчлч бсэщчх Янрищз
ROT10	Щътцоъ ьофыьй сйвтюъшлйччшмш втюъшц Аосйъи
ROT11	Ъыучпы эпхьэк ткгуяыщмкшшщнщ гуяыщч Бпткый
ROT12	Ыьфшрь юрцэюл улдфаьънлщщъоъ дфаьъш Врульк
ROT13	Ьэхщсэ ясчюям фмехбэыомъъыпы ехбэыщ Гсфмэл
ROT14	Эюцътю атшяан хнёцвюьпныыьрь ёцвюьъ Дтхнюм
ROT15	Юячыуя бущабо цожчгяэроььэсэ жчгяэы Еуцоян
ROT16	Яашьфа вфъбвп чпзшдаюспээютю зшдаюь Ёфчпао
ROT17	Абщэхб гхывгр шрищебятрююяуя ищебяэ Жхшрбп
ROT18	Бвъюцв дцьгдс щсйъёваусяяафа йъёваю Зцщсвр
ROT19	Вгыячг ечэдет ъткыжгбфтаабхб кыжгбя Ичътгс
ROT20	Гдьашд ёшюеёу ыульздвхуббвцв льздва Йшыудт
ROT21	Деэбще жщяёжф ьфмэиегцфввгчг мэиегб Кщьфеу
ROT22	Еёювъё зъажзх эхнюйёдчхггдшд нюйёдв Лъэхёф
ROT23	Ёжягыж иыбзиц юцоякжешцддеще оякжег Мыюцжх
ROT24	Жзадьз йьвийч ячпалзёщчееёъё палзёд Ньячзц
ROT25	Зибеэи кэгйкш ашрбмижъшёёжыж рбмиже Оэашич
ROT26	Ийвёюй людклщ бщсвнйзыщжжзьз свнйзё Пюбщйш
ROT27	Йкгжяк мяелмъ вътгокиьъззиэи тгокиж Рявъкщ
ROT28	Клдзал наёмны гыудплйэыиийюй удплйз Сагылъ
ROT29	Лмеибм обжноь дьфермкюьййкяк фермки Тбдьмы
ROT30	Мнёйвн пвзопэ еэхёснляэкклал хёснлй Увеэнь
ROT31	Ножкго ргипрю ёюцжтомаюллмбм цжтомк Фгёюоэ
ROT32	Опзлдп сдйрся жячзупнбяммнвн чзупнл Хджяпю