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

Содержание:

ВВЕДЕНИЕ

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

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

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

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

Фрэнсис Бэкон сформулировал основные требования, которые должны применяться к используемому шифру:

• простота использования;
• трудность расшифровки;
• шифр должен быть скрытен, но не должен вызывать подозрений.

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

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

Цель работы – раскрыть базовые тематические понятия, а также привести описание наиболее распространенных методов кодирования данных. Для достижения данной цели необходимо выполнить ряд задач:

• проанализировать литературу по заданной теме;
• описать основные понятия;
• изучить методы кодирования данных;
• привести примеры.

При написании работы в качестве опорных источников были использованы труды таких авторов, как А.С. Гуменюк, В.Н. Думачев, А.А. Понятов, Е.Г. Чепкунова и некоторых других, а также материал из сети Интернет, указанный в списке литературы в конце данной работы.

1. Основные понятия теории кодирования

Для рассмотрения методов кодирования важно определить основные понятия, которыми будем оперировать в дальнейшем.

Цели теории кодирования:

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

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

Однозначного определения понятию «код» нет. С одной стороны, код – это определенное правило, которое описывает соответствие знаков или их сочетаний первичного алфавита знакам или их сочетаниям вторичного алфавита. С другой, под кодом понимается набор знаков вторичного алфавита, который используется для представления знаков или их сочетаний первичного алфавита [9].

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

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

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

Необратимое кодирование бывает нескольких видов:

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

Сформулируем условие обратимости кодирования в математическом виде. Введем обозначения:

• I₁ – количество информации в исходном сообщении;
• I₂ – количество информации в кодированном сообщении.

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

I₁ ≤ I₂ (1)

2. Способы кодирования: классификация

2.1. В соответствии с условием построения кодовых комбинаций

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

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

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

2.2. В соответствии с количеством уникальных символов

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

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

Многопозиционные коды, алфавит которых состоит из большого числа символов, пока еще не нашли широкого применения в информационных системах [7].

2.3. В соответствии с формой представления

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

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

2.4. В соответствии с возможностями обнаружения/исправления ошибок

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

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

2.5. В соответствии с количеством одновременно кодируемых символов

По данному признаку коды делятся на алфавитные и блочные. Алфавитное кодирование представляет сообщение в виде последовательности кодов отдельных знаков первичного алфавита. Однако возможны варианты кодирования, когда кодовый знак относится сразу к нескольким буквам первичного алфавита или сразу к слову. Кодирование блоков понижает избыточность. Применение блочного метода имеет свои недостатки. Во‑ первых, требуется хранить огромную кодовую таблицу и постоянно к ней обращаться в процессах кодирования и декодирования, что существенно замедляет работу и требует значительных ресурсов памяти. Во-вторых, кроме основных слов любой разговорный язык содержит много производных, например, падежи существительных в русском языке или глагольные формы в английском; в данном способе кодирования им всем необходимо присвоить свои коды, что ведет к увеличению кодовой таблицы еще в несколько раз. В‑ третьих, возникает проблема согласования (стандартизации) этих громадных таблиц, что весьма непросто. Наконец, в-четвертых, алфавитное кодирование имеет то преимущество, что буквами можно закодировать любое слово, а при кодировании слов – можно использовать только имеющийся словарный запас [6].