Файл: Анализ методов кодирования данных.pdf

Стандарт ECMA-6 (ISO 646) позволяет размещать национальные символы на месте @. Кроме того на месте # возможно размещение £, и ¤ – на месте $. Данная система прекрасно адаптирована к европейским языкам, нуждаясь дополнительно лишь в нескольких символах. Стандарт ASCII без использования национальных «ярлыков» именуется как US-ASCII.

Для ряда языков нелатинской письменности (греческого, русского, иврита, арабского) существовали особые варианты ASCII. Так, одна из модификаций предполагала отказ от латинских строчных букв, уступив место национальным символам. Другая – переключение «на ходу» посредством символов Shift Out (SO) и Shift In (SI) между национальной версией и US-ASCII. В данном случае можно было совсем устранять латинские символы, занимая их пространство своими.

Но наиболее оптимальным вариантом стало использование 8-битных кодовых страниц (кодировок). Где нижняя часть в кодовой таблице (0–127) занята символами US-ASCII, а верхняя (128 – 255) – дополнительными символами, включая набор национальных. То есть верхняя часть таблицы до массового распространения Юникода применялась для отражения местных символов. При отсутствии универсального шаблона возникало немало проблем с разными кодировками (Windows-1251, КОИ-8 и т.д.)^[13].

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

Международный консультационный комитет по телефонии и телеграфии, МККТТ (фр. Comité Consultatif International Téléphonique et Télégraphique, CCITT) —- это подразделение Международного союза электросвязи (ITU). С 1995 года комитет официально носит название ITU-T — (англ. International Telecommunication Union - Telecommunication sector) сектор стандартизации электросвязи Международного союза электросвязи.

CCITT (ITU-T) занимается вопросами разработки технических стандартов, которые известные как «Recommendations» (рекомендации) по всем международным аспектам цифровых и аналоговых коммуникаций, а так же занимается проблемами связанными с решением технических и текущих вопросов, а также вопросов связанных с тарификацией. Раз в четыре года собирается Международная ассамблея стандартизации телекоммуникаций, WTSA — (англ. World Telecommunication Standartization Assembly) и определяет темы для изучения рабочими группами ITU-T, которые, в свою очередь, готовят рекомендации по этим темам. В некоторых сферах стандарты разрабатываются совместно с другими организациями, такими, как ISO и IEC^[14].

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

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

ГЛАВА 2 СПОСОБЫ ПРЕДСТАВЛЕНИЯ КОДОВ

2.1 Матричное представление кодов

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

• В виде кодовых матриц;
• В виде кодовых деревьев;
• В виде многочленов;
• В виде геометрических фигур и т.д.

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

2.2 Представление кодов в виде кодовых деревьев

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

Пример кодового дерева для полного кода показан на рисунке 1.

Рисунок 1. Пример кодового дерева

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

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

2.3 Представление кодов в виде многочленов

Представление кодов в виде многочленов (в литературе можно встретить представление кодов в виде полинома) базируется на подобии (изоморфизме) пространства двоичных n - последовательностей и пространства полиномов степени не выше n - 1 .

Код для любой системы счисления с основанием Х может быть представлен в следующем виде:

G (x) = an-1 xn-1 + an-2 xn-2 +... + a1 x+ a0 =,

где аi - цифры данной системы счисления (в двоичной 0 и 1);

х - символическая (фиктивная) переменная, показатель степени которой соответствует номерам разрядов двоичного числа-

Например: Кодовая комбинация 1010110 может быть представлена в виде:

G(x) =1 ×x6 +0 ×x5 +1 ×x4 +0 ×x3 +1 ×x2 +1 ×x1 +0 ×x0 =x6 +x4 +x2 +x=10101

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

2.4 Геометрическое представление кодов

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

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

На рисунке 2 представлена геометрическая модель двоичного кода.

В общем случае n мерный куб имеет 2n вершин, а это в свою соответствует набору кодовых комбинаций 2n .

n = 2 n = 3

Рисунок 2. Геометрическая модель двоичного кода

Ниже показана геометрические модели троичного двухразрядного и трехразрядного кодов соответственно.

Рисунок 3. Геометрическая модель троичного двухразрядного кода

Рисунок 4. Геометрическая модель троичного трёхразрядного кода

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

ГЛАВА 3 АНАЛИЗ МЕТОДОВ КОДИРОВАНИЯ

3.1 Аналоговое кодирование

Выделяют три основные схемы, в которые укладывается большинство методов кодирования информации, а именно:

• аналоговое кодирование,
• табличное кодирование;
• числовое кодирование.

В свою очередь табличного кодирования есть свои схемы, например символьное кодирование и цифровое кодирование^[19].

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

Аналоговое кодирование — это метод регистрации непрерывной последовательности сигналов известной физической природы в виде подобной ей последовательности данных другой физической природы.

Для аналогового кодирования характерны:

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

Если учитывать сущность определения термина «аналоговое кодирование», тогда принцип аналогового кодирования имеет две характерные черты:

• как исходная последовательность сигналов, так и результирующие данные имеют непрерывный характер;

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

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

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

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

3.2 Цифровое (числовое) кодирование

Цифровое (числовое) кодирование – представляет собой  кодирование с помощью чисел. Если быть точным, можно сказать, что числовое кодирования появилось вместе с первым алфавитом.  Например, так как каждая буква алфавита знает свое место, то у нее есть номер, а значит букву можно заменить цифрами (а точнее ее порядковым номером в алфавите): а - I, к - 12, о - 16 и т.д. Для того, чтобы пользоваться цифровым кодом нужно выучить алфавит, но это как раз очень пригодится, особенно будущему переводчику, ученому и в любой профессии, связанной с информацией^[20].

Следует отметить, что базовым является двоичное кодирование.

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