Теория кодирования

     Введение 

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

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

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

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

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

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

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

     Задачи:

     1) Проанализировать теоретические основы задачи кодирования.

     2) Рассмотреть основные виды помехоустойчивых кодов.

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

 

     

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

 
     

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]

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

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

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

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