Файл: Кодирования информации ( Основы и основные понятия кодирования информации ).pdf

Прежде всего, среднее число двоичных элементарных сигналов, приходящихся в закодированном сообщении на одну букву исходного сообщения, не может быть меньше Н, где Н = - p1 log p1 – p2 log p2 - … - pn log pn – энтропия опыта, состоящего в распознавании одной буквы текста (или, короче, просто энтропия одной буквы). Отсюда сразу следует, что при любом методе кодирования для записи длинного сообщения из М букв требуется не меньше чем МН двоичных знаков, и никак не может превосходить одного бита.

Если вероятности р1, р2, … …, рп не все равны между собой, то Н < log n; поэтому естественно думать, что учет статистических закономерностей сообщения может позволить построить код более экономичный, чем наилучший равномерный код, требующий не менее М log n двоичных знаков для записи текста из М букв.

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

Коды можно классифицировать по различным признакам:

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

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

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

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

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

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

Коды для обмена данными и их передачи по каналам связи. Широкое распространение в ПК получил код ASCII (American Standard Code for Information Interchange). ASCII - это 7-битный код буквенно-цифровых и других символов. Поскольку ЭВМ работают с байтами, то 8-й разряд используется для синхронизации или проверки на четность, или расширения кода. В ЭВМ фирмы IBM используется расширенный двоично-десятичный код для обмена информацией EBCDIC (Extended Binary Coded Decimal Interchange Code). В каналах связи широко используется телетайпный код МККТТ (международный консультативный комитет по телефонии и телеграфии) и его модификации (МТК и др.).

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

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

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

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

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

1.3 Кодирование данных при беспроводной передачи информации

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

Существует несколько задач, объединяемых общим названием «обеспечением анонимности», среди них выделяют [1]:

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

• Сокрытие маршрута передачи — данный вид анонимности не позволяет злоумышленнику определить маршрут конкретного пакета, т.е. список узлов, через которые он проходит, допуская тем не менее увидеть наличие такого пакета где-то в сети.
• Сокрытие факта передачи данных — данный вид анонимности не позволяет злоумышленнику определить наличие факта передачи, например, не давая отличить передачу реальных данных от белого шума.

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

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

Глава 2 Анализ Обеспечения секретности передачи данных в беспроводных сетях с сетевым кодированием

2.1 Метод COPE

Метод COPE [2] использует три механизма для повышения эффективности использования среды:

• гибкое прослушивание (Opportunistic Listening) — механизм, обеспечивающий сохранение всех пакетов, которые проходили через данный узел или были «услышаны» узлом на сети, даже если они не предназначены ему, в специальный буфер в течение некоторого времени (время хранения по умолчанию — 0.5 c). Также каждый узел широковещательно рассылает отчёты о получении, содержащие информацию о том, какие пакеты были сохранены и подслушаны;
• определение состояния соседних узлов (Learning Neighbour State) — метод, осуществляющий определение списка пакетов, которые есть в буферах соседних узлов. Механизм определения состояния основан на вычислении метрики EXT [5], которая назначается каждой паре узлов и характеризует вероятность успешной передачи данных между ними. Таким образом, каждый узел хранит таблицу для каждого соседнего узла и заполняет её, занося в неё пакеты и вероятность успешного получения этих пакетов;
• гибкое кодирование (Opportunistic Coding) — метод, отвечающий за правильный выбор линейной комбинации пакетов на основании данных, полученных при помощи остальных механизмов.

Утверждение 1. Узел-источник может переслать п пакетов Р\,... ,Р_п п соседним узлам п,... ,г_п — каждый пакет своему получателю — в рамках одной передачи объединив пакеты, тогда и только тогда, когда любой rj уже имеет все пакеты, кроме Pj. [3]

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

Рис. 2.1. Иллюстрация передачи пакетов по методу COPE: начальное состояние сети

Рассмотрим сеть, структура которой изображена на рис. 2.1.

На схеме изображен источник А и три получателя — В, С и D. На источнике содержится четыре пакета Р1 ,Р2,Р3,Р4, подлежащих пересылке. Рассмотрим задачу, в которой цель А — передать все пакеты на узел В и D. Рассмотрим процедуру передачи по шагам.

На первом шаге, изображенном на рис. 2.1, узел A пытается передать пакет P1 узду В. При этом, несмотря на то, что основной получатель этого пакета — узел В, узлы С и D также находится в зоне передачи и способны подслушать передаваемые данные, используя гибкое прослушивание. Пусть в процессе передачи произошла ошибка, и узел С не смог корректно принять Р1. После окончания передачи пакета Р1, узлы В и D рассылают подтверждение получения пакета, что даёт А возможность понять, что до С пакет не дошел.

Согласно методике COPE, подверждения получения пакета рассылаются каждым узлом асинхронно либо в момент передачи им какого-то пакета, либо, если узел не передаёт информацию, регулярными отдельными пакетами. При этом для уменьшения избыточности передачи подтверждений используется следующий подход: в заголовок каждого пакета вставляются дополнительные поля, содержащие идентификатор последнего полученного пакета и битовую карту, содержащую информацию о предыдущих полученных пакетах. Так, например, заголовок {Р4, 011} содержит информацию о том, что последним был получен пакет Р4, до него были получены пакеты Р1 и Р2, а пакет Р3 получен не был. Такой подход обеспечивает возможность подтверждать пакеты несколько раз без больших накладных расходов, таким образом обеспечивая защиту от возможных потерь пакетов с подтверждениями.

Второй шаг передачи изображен на рис. 2а. Теперь узел А передаёт очередной пакет — Р2 узлу D. При этом, как и на первом шаге, узлы В и D находятся в зоне передачи и могут подслушать передаваемый пакет. На этот раз ошибка случается при приёме пакета узлом D — отправитель узнал об этом, не получив подтверждение получения за определённое время. Аналогичным образом происходит передача пакета Р3 узлу В на рис. 2б — за исключением того, что на этот раз узел В не смог принять пакет.

Далее, на четвёртом шаге (рис. 3а) отправитель А, воспользовавшись утвеждением 1, применяет гибкое кодирование, чтобы передать недостающие пакеты всем трём узлам одновременно. Действительно, для передачи 3 пакетов Р1, Р2, Р3 получателям B,C,D необходимо и достаточно, чтобы каждый из получателей имел ровно два пакета из списка передаваемых — что выполняется, поэтому, создав линейную комбинацию Р1 0 Р2 0 Р3, отправитель может за одну трансмиссию передать сразу три пакета трём получателям, каждый из которых сможем успешно декодировать нужный пакет. После получения пакета, каждый узел, как и ранее, передаёт подтверждение получения.