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

Фотографии, записанные в формате JPEG, могут быть приняты судом в качестве доказательств, несмотря на то, что изображение сжато с потерями.

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

1.5. Прямая коррекция ошибок

Прямая коррекция ошибок (FEC) - это метод, который использовался в течении нескольких лет в оптоволоконных системах на подводных лодках. Этот метод позволяет с почти идеальной точностью передать данные, даже если передача осуществляется по каналу с большим количеством шумов. В настоящее время используется несколько алгоритмов FEC, таких как код Хэмминга, код Рида-Соломона и код БЧХ.

В качестве примера, рассмотрим работу мобильного телефона в условиях слабого сигнала сотовой сети. Допустим, вы хотели сказать человеку на другом конце линии некую последовательность чисел. Есть несколько методов, которые можно использовать для повышения точности. Предположим, что список чисел, которые вы хотите передать, это 7, 3, 8, 10, 12 и 21. Одним из способов может быть повтор списка чисел два раза. Запишите каждый список и сравните их, если они совпадают, передача данных, вероятно, корректна. Основным недостатком такого метода является то, что, поскольку данные передаются дважды, пропускная способность системы делится пополам и, если списки не совпадают, у вас не будет ни малейшего представления, который из них верный. Используя этот метод, для того, чтобы убедиться в хорошем качестве передачи и исправить некоторые ошибки, вам придется отправить данные три раза и проверить, что два из трех списков полностью совпадают. Второй способ будет выглядеть примерно так: в первую очередь, вы будете отправлять количество чисел, которые необходимо принять, затем саму последовательноcnm, и в конце последует передача числа, являющегося суммой последовательности. Передаваемое сообщение при этом примет следующий вид: 6, 7, 3, 8, 10, 12, 21, и 67. Человек, принимающий сообщение, будет смотреть на первое число, чтобы затем убедится, что будет получено правильное количество чисел в сообщении, а затем проверит, что число в конце последовательности действительно является суммой переданных чисел. Этот метод требует отправки значительно меньшего количества дополнительных данных. Если любое полученное число неверно или пропущено, то число контрольной суммы в конце передачи не будет соответствовать сумме, передаваемых чисел. Показанные выше методы представляют собой примеры кода обнаружения ошибок. Они позволяют определить, была ли передача точной, но не позволяют исправлять ошибки.

Примечание: Термин "Forward" в FEC означает, что исправление ошибок осуществляется путем передачи некоторой информации вместе с передачей данных.

Код исправления ошибок считается более сложным, в сравнении с кодом обнаружения ошибок и используется почти в каждом современном коммуникационном приложении. Также, коды исправления ошибок нашли широкое применение в CD и DVD проигрывателях. Для того, чтобы привести пример кода исправления ошибок, нужно ввести и объяснить два термина: двоичность и чётность. В предыдущих примерах кода обнаружения ошибок, мы использовали такие числа, как 7, 3, 8, и т.д. Это базовые числа системы исчисления, знакомой нам в повседневной жизни. Двоичные числа в основе имеют два числа, которые могут иметь только два возможных значения – 0 или 1. Бинарная система используется почти во всех коммуникационных и компьютерных системах. Второе определение, которое необходимо разобрать, называется четность. Чётность - термин, который используется в двоичных системах связи, чтобы указать, является ли число единиц в передаче четным или же нет. Если число единиц является четным, то чётность совпадает и наоборот.

Глава 2. Сетевое кодирование

2.1. Основы сетевого кодирования

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

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

Рассмотрим пример графа «Бабочка», который состоит из узла-источника S, четырех промежуточных узлов A, B, C, D и двух узлов получателей R₁, R₂. Сами же ребра имеют пропускную способность равную 1пакету/кадру. Двумя ребрами соединены лишь узлы С и D. Работа узлов выстраивается по принципу «принимай и передавай дальше». До передачи сам пакет хранится на промежуточном узле.

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

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

2.2. Случайное сетевое кодирование

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

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

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

2.3. Защита информации от искажения

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

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

Сетевое кодирование – относительно новое понятие позволяющее достичь

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

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

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

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