Файл: Методы кодирования данных (Процесс формирования цифровых сигналов).pdf

Введение

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

Хотя существующие на данный момент системы передачи данных отвечают всем основным стандартам и требованиям, они все же не являются совершенными. Причин тому влияние помех в канале связи. При передаче сообщений по каналам связи могут возникать помехи, способные привести к искажению принимаемых знаков. Естественный язык обладает большой избыточностью (в европейских языках — до 7%), чем объясняется большая помехоустойчивость сообщений, составленных из знаков алфавитов таких языков. Примером, иллюстрирующим устойчивость русского языка к помехам, может служить предложение «в словох всо глосноо зомононо боквой о». Здесь 26% символов «поражены», однако это не приводит к потере смысла. Таким образом, в данном случае избыточность является полезным свойством. Избыточность могла бы быть использована и при передаче кодированных сообщений в технических системах. Например, каждый фрагмент текста («предложение») передается трижды, и верным считается та пара фрагментов, которая полностью совпала. Однако, больная избыточность приводит к большим временным затратам при передаче информации и требует большого объема памяти при ее хранении. Впервые теоретическое исследование эффективного кодирования предпринял К. Шеннон.

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

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

Объект: процесс формирования цифровых сигналов

Предмет: кодирование информации

Цель исследования: разработать алгоритм на основе анализа задачи кодирования

Задачи:

1. Проанализировать теоретические основы задачи кодирования
2. Рассмотреть основные виды помехоустойчивых кодов
3. Практическая реализация помехоустойчивого кодирования.

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

1.1 Постановка задачи кодирования

Прежде чем рассмотреть задачу кодирования, необходимо рассмотреть ряд определений, использующихся в теории кодирования [1]:

Код – (1) правило, описывающее соответствие знаков или их сочетаний одного алфавита знакам или их сочетаниям другого алфавита; - (2) знаки вторичного алфавита, используемые для представления знаков или их сочетаний первичного алфавита.

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

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

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

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

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

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

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

Пусть первичный алфавит A содержит N знаков со средней информацией на знак, определенной с учетом вероятностей их появления, I₁^(A) (нижний индекс отражает то обстоятельство, что рассматривается первое приближение, а верхний индекс в скобках указывает алфавит). Вторичный алфавит B пусть содержит M знаков со средней информационной емкостью I₁^(A). Пусть также исходное сообщение, представленное в первичном алфавите, содержит n знаков, а закодированное сообщение – m знаков. Если исходное сообщение содержит I^(A) информации, а закодированное – I^(B), то условие обратимости кодирования, т.е. неисчезновения информации при кодировании, очевидно, может быть записано следующим образом:

I^(A) ≤ I^(B), смысл которого в том, что операция обратимого кодирования может увеличить количество формальной информации в сообщении, но не может его уменьшить. Однако каждая из величин в данном неравенстве может быть заменена произведением числа знаков на среднюю информационную емкость знака, т.е.:

n*I₁^(A) ≤ n*I₁ ^(B), или I₁^(A) ≤ m/n*I₁ ^(B)

Таким образом, отношение m/n четко характеризует среднее число знаков вторичного алфавита, которое будет использоваться для кодирования одного знака первичного алфавита. Такой набор называется длиной кода или длиной кодовой цепочки. Обозначим его K^(B) , при этом верхний индекс указывает алфавит кодов.

В конкретном случае, когда возникновение любых знаков вторичного алфавита оценивается равновероятно, согласно формуле Хартли I₁^(B)=log₂M, и тогда I₁^(A) /log₂M≤ K^(B) (1)

По аналогии с величиной R, характеризующей избыточность языка, можно ввести относительную избыточность кода (Q):

Q= 1 – I^(A) / I^(B) = 1- I₁^(A) / K^(B)*I₁^(B) (2)

Данная величина позволяет определить, насколько операция кодирования повысила длину исходного сообщения. Логично, чем меньше Q (т.е. чем ближе она к 0 или, что то же, I^(B) ближе к I^(A)), тем более выгодным будет считаться код и более рациональной будет считаться сама операция кодирования. Выгодность кодирования при передаче и хранении – это экономический фактор, поскольку более рациональный код дает возможность затратить на передачу сообщения меньшее количество энергии, а также времени и, таким образом, меньше времени занимать линию связи; при хранении применяется меньше площади поверхности (объема) носителя. Также важно сознавать, что выгодность кода не идентична временной выгодности всей цепочки «кодирование – передача – декодирование», так как возможна ситуация, когда за применение рационального кода при передаче данных потребуется расплачиваться тем, что операции кодирования и декодирования будут требовать больше времени и других ресурсов.

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

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

Базовыми целями кодирования являются:

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

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

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

Согласование между компонентами дискретных сообщений и типом кодирования реализуется оптимальным подбором:

1. Длительности сигналов

2. Длины кодового слова

3. Алфавита знаков и метода кодирования. Например, может быть выбран блочный или побуквенный тип шифрования.

Примем, что сообщение источника данных составляется из знаков аi, i=1,2,.. Na внешнего (такой алфавит также называют «входным» или «первичным») алфавита А размером Na. Сообщения - это слова, образованные последовательностью nr символов: Ar =a1a2…anr. В устройстве кодировки слово Ar трансформируется в кодовое слово Br=b1b2…bmr, составленное из mr знаков b_j, j=1,2,..Nb внутреннего (такой алфавит также называют «выходным» или «вторичным») алфавита В. Количество символов кодового алфавита является основанием кода. Число знаков в кодовом слове называют длиной кодового слова. Отображение G количества слов в алфавите А на количество слов в алфавите В является кодирующим отображением или кодом. Использование кодирующего отображения G к произвольному слову из входного алфавита называется процессом кодирования. То есть код представляет собой правило отображения символов одного алфавита в символы другого алфавита, а кодирование представляет собой процесс трансформации одной формы сообщения в другую с помощью указанного кода.

Следует различать побуквенное и блочное шифрование. При побуквенном (посимвольном) кодировании каждому символу вторичного алфавита ставится в соответствие кодовый символ из числа символа первичного алфавита. [2]

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

Слова из символов первичного алфавита В, сопоставленные словам из знаков вторичного алфавита А по определенному правилу G, являются так называемыми кодовыми комбинациями. Если ArE A и G(Ar)= Br, то считается, что слову Ar соответствует кодовая комбинация Br. Общность кодовых комбинаций применяемых для передач определенного объема дискретных сообщений именуют кодовым словарем.

Процесс, обратный кодированию, заключается в восстановлении из кодовой комбинации Br=b1b2…bmr слова Ar=a1a2…anr из входного алфавита и называется процессом декодирования. Если процесс кодирования выполняется с применением правила G, то процесс декодирования базируется на использовании правила G-1, где G-1 есть отображение, обратное отображению G.

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

Пусть Ar — слово в алфавите А и Br =G(Ar) — слово в алфавите В. Код называется обратимым, если для любого слова Br =G(Ar) в алфавите В существует единственное преобразование G-1(Br)= Ar . То есть, по слову Br в алфавите В, всегда однозначно восстанавливается слово Ar в алфавите А, из которого было образовано слово Br.

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

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

Для того, чтобы результирующий код был обратимым, требуется:

1) чтобы разным знакам входного алфавита А были сопоставлены различные кодовые комбинации;

2) чтобы всякая кодовая комбинация не составляла начальной части какой-либо другой кодовой комбинации.

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

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