Кодирование информации

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

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

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

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

 

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

1 0

1 0 1 0

1 0 1 0 1 0 1 0

111 110 101 100 011 010 001 000

Рис.1. Дерево для полного двоичного кода при n = 3

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

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

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

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

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

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

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

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

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

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

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

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

(n = 3) - в вершинах единичного куба (рис.2).

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

n = 2 n = 3

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

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

 

 

2.2 Кодирования и декодирования информации.

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

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

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

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

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

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

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

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

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

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

Более крупной единицей информацией является машинное слово, представляющее собой последовательность символов , занимающих одну ячейку в памяти машины. В зависимости от ЭВМ машинного слова может колебаться в пределах— от 16 до 64 двоичных разрядов. машинное слово может быть командой, числом или буквенно-цифровой последовательностью. Обычно машинное слово используется как единое целое в ЭВМ, хотя на некоторых машинах допускается обработка частей машинного слова.  Массив информации, содержащий 1024 машинных слова, называется страницей.

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

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

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

Информационная модель – целенаправленно отобранная информация об объекте или процессе.

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

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

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

Например, набор цифр 271009 может обозначать:

• массу объекта;
• длину объекта;
• расстояние между объектами;
• номер телефона;
• запись даты 27 октября 2009 года.

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

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

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

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

Для общения друг с другом мы используем код - русский язык.

При разговоре этот код передается звуками, при письме - буквами.

Водитель передает сигнал с помощью гудка или миганием фар.

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

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

Способ кодирования зависит от цели, ради которой оно осуществляется:

• сокращение записи;
• засекречивание (шифровка) информации;
• удобство обработки;
• и т. п.

Существуют три основных способа кодирования текста: