Файл: МЕТОДЫ КОДИРОВАНИЯ ИФОРМАЦИИ.pdf

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

Целью данной работы является анализ технологий кодирования информации.

Задачи работы:

- анализ и классификация технологий кодирования информации;

- анализ технологий штрихового кодирования;

- анализ криптографических алгоритмов;

- анализ математических моделей шифрования и кодирования информации.

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

Предмет исследования: технологии кодирования информации.

1. Теоретические основы кодирования информации

1.1 Основы и основные понятия кодирования информации

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

Алфавит представляет собой множество возможных кодовых элементов, т.е. элементарных символов (кодировки)X = {xi}, где i = 1, 2,..., m. Число кодовых элементов (m) представляет собой его основание. Для двоичных кодов xi = {0, 1} и m = 2. Конечные последовательности символов данного алфавита представляют собой кодовые комбинации (кодовые слова). Количество элементов в кодовых комбинациях - n представляет собой значимость кода (длину комбинации). Количество различных кодовых комбинаций (N = mn) называется объемом или мощностью кода.

Целями кодирования являются [2]:

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

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

В соответствии с данными целями развитие теории кодирования происходит в следующих направлениях:

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

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

Описание теоретических основ технологий кодирования было проведено Шенноном К. , проводившим исследование процессов передачи информации по техническим каналам связи (теория связи, теория кодирования). Указанный подход к кодированию предполагает: осуществление перехода от представления данных в одной символьной системе к представлению в другой символьной системе. Подобное преобразование производится при кодировании письменного русского текста в символы азбуки Морзе для передачи его с помощью телеграфной связи или радиосвязи. Данное кодирование связано с наличием потребности приспособление кода к используемым техническим средствам работы с данными.

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

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

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

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

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

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

Если необходимо сохранение числовой информации без искажения, то её лучше записывать в форме текста. Например, в финансовых документах числовые суммы сопровождаются суммами в текстовой форме: «пятьсот шестьдесят три руб.» вместо «563 руб.». При записи в цифровой форме искажение или добавление одной цифры изменяет все значение. В случае использования текстовой формы даже наличие грамматических ошибок могут не приведет к изменению смысла.

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

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

Классификация кодов проводится с помощью следующих признаков [12]:

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

2. Классификация по длине кодовых комбинаций (слов): равномерное, при одинаковой длине кодовых комбинаций и неравномерное кодирование в случаях, когда длина кодовых комбинаций непостоянна.

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм данного метода кодирования включает этапы[10]: