Теория кодирования: основные понятия, задачи

Содержание:

Введение

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

Теория информации как наука существует с середины ХХ века, с момента появления основополагающей работы – Клод Шеннон: «Математическая теория связи» (1948) – прошло чуть более 60 лет. У Шеннона (1916 – 2001) были предшественники, например, Р. Хартли, впервые предложивший в 1928 году количественную меру информации, или В. А. Котельников, сформулировавший в 1933 году важнейшую теорему о возможности представления непрерывной функции совокупностью ее значений в отдельных точках отсчета. Были и современники, и последователи, например, А. Н. Колмогоров, внесший большой вклад в статистическую теорию колебаний, являющуюся математической основой теории информации. Работы по развитию теории информации продолжаются и в настоящее время.

Теория информации быстро разделилась на фундаментальную и прикладную.

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

Фундаментальная теория информации – это:

– анализ сигналов как средства передачи сообщений и оценка переносимого «количества информации»;

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

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

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

Существует ли информация независимо от того, воспринимается ли она, зависит ли ее восприятие от индивидуальных способностей воспринимающего?

Противоречие частично снимается, если рассматривать информацию как некое потенциальное свойство объекта (системы).

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

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

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

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

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

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

1 Теория кодирования: основные понятия, задачи. Классификация способов кодирования

С глубокой древности люди искали эффективные способы передачи информации.

Толчок развитию теории кодирования дало создание в 1948 году Клодом Эльвудом Шенноном (1916 — 2001) теории информации. Идеи, изложенные Шенноном в статье «Математическая теория связи», легли в основу современных теорий и техник обработки, передачи и хранения информации.

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

На сегодняшний день основными целями теории кодирования являются:

· Разработка принципов наиболее экономного представления информации;

· Согласование параметров передаваемой информации с особенностями канала связи;

· Разработка приемов повышения надежности передачи информации.

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

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

При определении понятия «код» используют два подхода. С одной стороны, код — это правило, описывающее соответствие знаков или их сочетаний первичного (исходного) алфавита знакам или их сочетаниям вторичного алфавита. Также кодом называют набор знаков вторичного алфавита, используемый для представления знаков или их сочетаний первичного алфавита.

Кодирование – это перевод информации, представленной символами первичного алфавита в последовательность кодов.

Декодирование – операция обратная кодированию — перевод последовательности кодов в соответствующий набор символов первичного алфавита.

Кодер – устройство, обеспечивающее выполнение операции кодирования.

Декодер – устройство, производящее декодирование.

Рассмотрим несколько примеров кодирования:

· перевод письменного текста с одного естественного языка на другой (в этом случае первичный алфавит — алфавит языка, на котором написан текст, вторичный алфавит — алфавит языка перевода);

· ввод и сохранение текста на компьютере (первичный алфавит — алфавит используемого естественного языка, вторичный алфавит — набор двоичных цифр {0; 1});

· флажковый семафор (первичный алфавит — алфавит используемого естественного языка, вторичный алфавит — совокупность различных положений рук (флажков) по отношению к туловищу сигнальщика).

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

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

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

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

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

Существует множество способов классификации способов кодирования.

По условию построения кодовых комбинаций коды делят на равномерные и неравномерные. В равномерных кодах все сообщения передаются кодовыми группами с одинаковым числом элементов (длина кода n = const). Примером такого кода может служить телеграфный код Бодо, который является равномерным пятибитным кодом (n=5). Первоначально код, разработанный Эмилем Бодо (1845 -1903) в 1870 году для своего телеграфа, вводился прямо клавиатурой, состоящей из пяти клавиш, нажатие или ненажатие клавиши соответствовало передаче или непередаче одного бита в пятибитном коде. В 1901 году Дональд Мюррей (1866 - 1945) переработал код, изменил порядок знаков и добавил некоторые дополнительные знаки, адаптировав код Бодо к раскладке современной клавиатуры

QWERTY. Однако общие принципы — пятибитная кодировка и использование буквенного и цифрового регистров — остались неизменными.

При использовании неравномерных кодов разные сообщения могут передаваться кодовыми группами, содержащими неодинаковое число элементов (n = var).

Типичным представителем неравномерного кода является код Морзе, созданный в 1838 году Самюэлем Морзе и подвергавшийся впоследствии неоднократным изменениям. В настоящее время кодом Морзе называют способ знакового кодирования, в котором для представления букв алфавита, цифр, знаков препинания и других символов используется последовательность троичных сигналов, например, длинных и коротких: «тире» и «точек». За единицу времени принимается длительность одной точки. Длительность тире равна трём точкам. Пауза между элементами одного знака — одна точка, между знаками в слове — три точки, между словами — семь точек.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 Кодирование при сжатии данных изображений: вейвлет-кодирование

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

Прототип технологии MrSID был разработан в Национальной Лаборатории Лос-Аламоса в 1992 году. Последовавшая коммерческая версия технологии от компании LizardTech была названа MrSID Generation 2 (MG2) форматом и внедрена в 1998 г. Следующая версия, формат MrSID Generation 3 (MG3), внедрённый в 2002 г., предоставлял улучшенное качество изображения и ключевые функции, такие как кодирование без потерь. В 2010 году LizardTech представил новый формат – MrSID Generation 4 (MG4). В нём поддерживаются мультиспектральные изображения, альфа диапазоны, а также есть многие другие улучшения.

Формат JPEG2000 развивался не столь динамично. Когда в середине 90-х стало ясно, что возможностей JPEG недостаточно для некоторых применений, М. Болиек в 1996 году предложил создать новый стандарт. В 2000-м году была выпущена первая часть. Стандарт до конца еще не разработан, сейчас, по данным ISO, находится в разработке 14-я часть, «Структурное XML-представление и справочная информация». В настоящее время формат в основном используется для хранения кадров в видеопотоках и для хранения фотографий в базах данных.

Формат ECW, как и MrSID, специализирован для воздушных и космических фотографий. Он разработан организацией Earth Resource Mapping, которая ныне является частью подразделения ERDAS компании Intergraph.

В 1998 году основатель компании Стюарт Никсон и два программиста исследовали скоростную транспортировку терабайтовых изображений через интернет, результатом этих изысканий стало два продукта – Image Web Server и ECW (Enhanced Compression Wavelet). В отличие от разработчиков MrSID, которые делали упор на эффективность сжатия, разработчики ECW делали упор на производительность преобразований.

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

Массив чисел, представляющих пикселы изображения, можно представить несколькими способами:

1. Используя метод усреднения. При этом вычисляется среднее значение пары каждых соседних чисел.

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

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

Благодаря этим упрощённым примерам можно сделать некоторые наблюдения. Во-первых, кодирование и декодирование может занять некоторое время. Во-вторых, есть возможность потерять данные: в примере с «усреднением» мы потеряли данные в операции округления и мы можем никогда не получить их обратно.

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

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

Вейвлет-преобразование одномерного сигнала – это его представление в виде обобщенного ряда или интеграла Фурье по системе базисных функций

, (1)

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

Рисунок 1 – Вейвлет-преобразование

Иными словами, представим список из 4 чисел: {2, 6, 14, 6}. Путем попарного усреднения мы можем снизить его до списка «второго уровня» из двух чисел {4, 10}, и списка «различий» второго уровня, {+2, -4}. Выполняя ту же операцию снова на списке {4, 10}, мы получаем список третьего уровня {7} и список различий третьего уровня {+3}. Это показано на Рисунке 1.

Эти три списка, а также два связанных списка различий, используются для представления оригинального списка из 4-х чисел на трех уровнях разрешения. Заметьте что только последний одно-элементный список {7}и два списка различий {+3} и {+2, -4} требуются, чтобы выполнить обратную операцию и восстановить оригинальный входной список. Только с помощью этих трех списков, мы можем восстановить второй уровень: список третьего уровня {7} и список различий {+3} вернет {4, 10} (поскольку 7 – 3 = 4 и 7 + 3 = 10). Список второго уровня {4, 10} и список различий второго уровня {+2, -4} вернет, в свою очередь, оригинальный список (4-2, 4+2, 10-(-4), 10+(-4)).

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

Но даже при отношении 20:1, сжатие данных размером 20 Гб даст очень большой (1Гб) файл. Пользователи часто переживают по поводу работы с файлами такого размера, поскольку многие приложения GIS будут пытаться заглотить файл целиком, приводя к избыточным и подчас фатальным запросам к ЦП и ОЗУ. Два аспекта всех трёх форматов решают эту проблему.

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

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

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

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

Формат JPEG2000 универсальный, ног в нѐм есть возможность хранения произвольных XML-тегов. Для стандартизации структуры этих тегов под геоинформационные нужды Open Geospatial Consortium разработал специальный Географический Язык Разметки – (Geography Markup Language, GML). Это средство позволяет сохранять в файле большое количество метаинформации. Помимо того, что можно сохранять в MrSID и ECW, также можно на самом рисунке делать метки, подписанные текстом или дополнительным изображением, например, фотографией места. Нужно только учесть, что XML-формат избыточен по своей сути, что чревато увеличением занимаемого места.

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

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

2. также важно принять решение, что важнее – степени сжатия или же производительность, так как еще в начале статьи было сказано, что никакими способами не получить одновременно и высокую степень сжатия и высокую производительность;

3. следует принимать во внимание программы для работы с этими форматами. В плане чтения всё просто – все современные ГИС-системы позволяют читать все три формата. С кодированием несколько сложнее – есть программы специализированные, например – GeoExpress фирмы LizardTech, который предназначен для кодирования в формате MrSID. Есть и программы универсальные, например Erdas Imagine корпорации Intergraph.

3 Методы специального кодирования данных с ограничением длины поля записи

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

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

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

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

Для повышения точности отслеживания частоты синхросерии за скоростью носителя данных подстройка синхрогенератора посредством «единичных» импульсов должна выполняться достаточно часто, чтобы минимизировать накопленный «уход» частоты относительно текущей средней частоты данных воспроизведения. Обычный двоичный код имеет равную вероятность появления символов «1» или «0» в текущем такте и допускает бесконечно большие «нулевые» последовательности символов, в пределах которых нет подстройки частоты генератора. Такой код не обладает свойствами самосинхронизации. В связи с этим для представления данных на подвижном носителе в ВЗУ создают специальные канальные коды, которые гарантируют появление символа «1» через определенное количество символов «0» и поэтому обладают свойствами самосинхронизации.

Существует две причины, по которым необходимо это техническое оснащение: во-первых, синхронизируемая (синхронизирующая) схема использует поток импульсов, благодаря переходам чередующихся магнитных полярностей на диске, чтобы поддержать правильное время связывания-удержания (track-andhold), ADC и детектора. В то же время, если импульсы долгое время отсутствуют, т.е. длинная последовательность нулей (запись без возврата к нулю с инверсией – NRZI-recording), канал двусторонней связи не получит достаточно информации, чтобы обеспечить надлежащую синхронизацию (выравнивание). Вследствие этого, временной промежуток между двумя единицами (1) должен быть ограничен. Во-вторых, когда два бита записываются слишком близко друг к другу, взаимные помехи между двумя противоположными импульсами будут снижать соотношение “сигнал-шум” (SNR) при считывании только что записанной информации (эхосчитывании). Следовательно, следует использовать постоянное кодирование, чтобы гарантировать расстояние (интервал) между двумя переходами расстояние (интервал), достаточно большой, чтобы избежать межсимвольных помех (ISI); поскольку это расстояние (интервал), которое обычно определяется от средней величины, техническое оснащение в состоянии затем увеличить плотность записи. Выравнивание по частичному отклику применяется сейчас для борьбы с проблемой межсимвольных помех (ISI), но кодирование с ограничением длины поля записи (RLL) широко используется по вышеприведённым причинам.

Кодирование с ограничением длины поля записи (RLL) обычно классифицируют по (d, k): показатель d отражает минимальное количество нулей между двумя единицами (1). Показатель k ограничивает максимальное количество нулей между двумя единицами (1). С другой точки зрения, d контролирует высокочастотные составляющие в связанных сигналах токов записи, чтобы сократить межсимвольные помехи (ISI). K, напротив, оказывает доминирующее влияние на низкочастотные составляющие, чтобы обеспечить информацию о частоте для канала тактовой синхронизации. Рисунок 2 показывает диаграмму переходов для типовых (d,k) кодов:

d≤m≤k

Рисунок 2 - Диаграмма переходов (d,k) кодов

Параметр d может принимать значения из натурального ряда целых чисел, включая 0, то есть 0,1,2,3,... При этом параметр к принимает соответственно значения из ряда чисел 1, 2, 3, 4, ..., так что всегда справедливо неравенство:

d<k

В связи с этим неравенством невозможно, например, значение k = 1, если d = l. В реально существующих ВЗУ известны (d,k) – коды, характеризуемые (d,k) – параметрами (0,1); (0,2); (1,3); (1,7); (2,7) и т.д.

Для анализа канальных кодов, применяемых в современных ВЗУ, созданных на основе технологий магнитной записи и оптической записи, в качестве «точки отсчета» обычно берут обычный двоичный код, который относится к позиционным однородным кодам. Следуя терминологии (d,k)-кодов обычный двоичный код можно охарактеризовать как (d,k) – код, для которого параметр d = 0, а параметр k = ∞.

Указанное значение параметра и определяет отсутствие самосинхронизации в этом коде, поскольку длина «нулевой» последовательности символов для него не ограничена сверху.

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

Недостатком (d, k) кодов является их потеря в скорости обмена данных. Из-за избыточных разрядов желаемая передача информационных битов меньше, чем в настоящем информационном потоке. Следовательно, если d выше, потери будут более существенны.

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

Более эффективная схема кодирования (0,k), используемая для каналов чтения PRML (технология Partial Response – Maximum Likelihood, что можно перевести как «неполный отклик – максимальное подобие», была разработана для обмена информацией в дальних космических экспедициях), используемая во многих накопителях на жестких дисках Seagate, обеспечивает более компактную пропорцию 16/17 и позволяет передавать данные с высокой скоростью.

Заключение

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

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

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

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

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

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

Каждая комбинация записывается в виде последовательности, составленной из некоторых условных символов — элементов кодовой комбинации. В качестве элементов кодовой комбинации могут использоваться буквы (А, В, С...) и цифры (0, 1,2...).

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

Преобразование сообщений в кодовые комбинации (кодовые слова) позволяет обеспечить:

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

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

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

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

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

1. Гвоздева В. А. Информатика, автоматизированные информационные технологии и системы. Учебник. М.: Форум, 2015. 544с.
2. Дьяконов В. Вейвлеты. От теории к практике. Изд.2-е, перераб. и доп. – М.: СОЛОН-Пресс, 2010. 400с.
3. Евсютин О., Шелупанов А., Россошек С., Мещеряков Р. Сжатие цифровых изображений. М.: Горячая Линия – Телеком, 2013. 124с.
4. Лидовский В. Основы теории информации и криптографии [Электронный ресурс]: URL: http://www.intuit.ru/studies/courses/2256/140/info (дата обращения: 10.02.2016 - 20.03.2016)
5. Литвинская О.С., Чернышев Н.И. Основы теории передачи информации. Учебное пособие. Гриф УМО МО РФ. М.: КноРус, 2015. 168с.
6. Марков А. Введение в теорию кодирования. М.: Главная редакция физико-математической литературы издательства "Наука", 1982. 192с.
7. Маскаева А.М. Основы теории информации. Учебное пособие. М.: Инфра-М, 2014. 96с.
8. Основы работы в Photoshop. Лекция 16: Хранение изображений [Электронный ресурс]: URL: http://www.intuit.ru/studies/courses/1099/138/lecture/3873?page=4 (дата обращения: 10.02.2016 - 20.03.2016)
9. Панин В.В. Основы теории информации. Учебное пособие для вузов. М.: Бином. Лаборатория знаний, 2014. 438с.
10. Сайт Центра Информационных Технологий ("ЦИТ", "ЦИТ Форум") [Электронный ресурс]: URL: http://citforum.ru/
11. Сергеенко В., Баринов В. Сжатие данных, речи, звука и изображений в телекоммуникационных системах. Учебное пособие. М.: ИП РадиоСофт, 2014. 360с.
12. Сэломон Д. Сжатие данных, изображений и звука. М.: Техносфера, 2006г. 368с.
13. Чечета С. Введение в дискретную теорию информации и кодирования. Учебное пособие. М.: МЦНМО, 2011. 224с.
14. Яковлев А. Основы вейвлет-преобразования сигналов. М.: Science Press, 2003г. 80с.