Задача кодирования
4 Введение В настоящее время по каналам связи передаются данные со столь высокими требованиями к достоверности передаваемой информации, что удовлетворить эти требования традиционным методами - совершенствованием антенно-фидерных устройств, увеличением излучаемой мощности, снижением собственного шума приемника - оказывается экономически невыгодным или просто невозможным. Хотя существующие на данный момент системы передачи данных отвечают всем основным стандартам и требованиям, они все же не являются совершенными. Причин тому влияние помех в канале связи. При передаче сообщений по каналам связи могут возникать помехи, способные привести к искажению принимаемых знаков. Естественный язык обладает большой избыточностью (в европейских языках -- до 7%), чем объясняется большая помехоустойчивость сообщений, составленных из знаков алфавитов таких языков. Примером, иллюстрирующим устойчивость русского языка к помехам, может служить предложение «в словох всо глосноо зомононо боквой о». Здесь 26% символов «поражены», однако это не приводит к потере смысла. Таким образом, в данном случае избыточность является полезным свойством. Избыточность могла бы быть использована и при передаче кодированных сообщений в технических системах. Например, каждый фрагмент текста («предложение») передается трижды, и верным считается та пара фрагментов, которая полностью совпала. Однако, больная избыточность приводит к большим временным затратам при передаче информации и требует большого объема памяти при ее хранении. Впервые теоретическое исследование эффективного кодирования предпринял К. Шеннон. Одним из средств решения подобных несоответствий в системах передачи цифровой информации, является применение помехоустойчивых кодов, лежащих в основе устройств кодирования/декодирования. Высокоэффективным средством решения данной проблемы является применение помехоустойчивого кодирования, основанного на введении искусственной избыточности в передаваемое сообщение. Помехоустойчивое кодирование передаваемой информации позволяет в приемной части системы обнаруживать и исправлять ошибки. Актуальность: Работа подавляющего числа современных систем связи основана на передаче сообщений в цифровом виде. Сбой при приеме любого элемента цифровых данных способен вызвать значительное искажение всего сообщения в целом, что, в свою очередь, может привести к полной потере информации, содержащейся в нем. В современных информационных системах важнейшей задачей является обеспечение информационной безопасности, связанной с методами криптографии и кодирования, теоретические основы которой заложил Шеннон в своих трудах. В данной работе будут рассмотрены основы задачи кодирования, а также практическое применение помехоустойчивых кодов. Объект: процесс формирования цифровых сигналов Предмет: кодирование информации Цель исследования: разработать алгоритм на основе анализа задачи кодирования. Задачи: 1) Проанализировать теоретические основы задачи кодирования. 2) Рассмотреть основные виды помехоустойчивых кодов. 3) Практическая реализация помехоустойчивого кодирования. 1 1 Теоретические основы задачи кодирования 1.1 Постановка задачи кодирования Прежде чем рассмотреть задачу кодирования, необходимо рассмотреть ряд определений, использующихся в теории кодирования [1]: Код - (1) правило, описывающее соответствие знаков или их сочетаний одного алфавита знакам или их сочетаниям другого алфавита; - (2) знаки вторичного алфавита, используемые для представления знаков или их сочетаний первичного алфавита. Кодирование - перевод информации, представленной посредством первичного алфавита, в последовательность кодов. Декодирование - операция, обратная кодированию, т.е. восстановление информации в первичном алфавите по полученной последовательности кодов. Операции кодирования и декодирования называются обратимыми, если их последовательное применение обеспечивает возврат к исходной информации без каких-либо ее потерь. Информационная энтропия - в теории связи энтропия используется как мера неопределенности ожидаемого сообщения, т.е. энтропия источника информации с независимыми сообщениями есть среднее арифметическое количеств информации сообщений Примером обратимого кодирования является представление знаков в телеграфном коде и их восстановление после передачи. Примером кодирования необратимого может служить перевод с одного естественного языка на другой - обратный перевод, вообще говоря, не восстанавливает исходного текста. Безусловно, для практических задач, связанных со знаковым представлением информации, возможность восстановления информации по ее коду является необходимым условием применения кода, поэтому в дальнейшем изложении будет рассматриваться только обратимое кодирования. Таким образом, кодирование предшествует передаче и хранению информации. При этом, как указывалось ранее, хранение связано с фиксацией некоторого состояния носителя информации, а передача - с изменением состояния с течением времени (т.е. процессом). Эти состояния или сигналы будем называть элементарными сигналами - именно их совокупность и составляет вторичный алфавит. Без технических сторон передачи и хранения сообщения (т.е. того, каким образом фактически реализованы передача-прием последовательности сигналов или фиксация состояний), математическая постановка задачи кодирования, дается следующим образом. [5] Пусть первичный алфавит A содержит N знаков со средней информацией на знак, определенной с учетом вероятностей их появления, I1(A) (нижний индекс отражает то обстоятельство, что рассматривается первое приближение, а верхний индекс в скобках указывает алфавит). Вторичный алфавит B пусть содержит M знаков со средней информационной емкостью I1(A). Пусть также исходное сообщение, представленное в первичном алфавите, содержит n знаков, а закодированное сообщение - m знаков. Если исходное сообщение содержит I(A) информации, а закодированное - I(B), то условие обратимости кодирования, т.е. неисчезновения информации при кодировании, очевидно, может быть записано следующим образом: I(A) ? I(B), смысл которого в том, что операция обратимого кодирования может увеличить количество формальной информации в сообщении, но не может его уменьшить. Однако каждая из величин в данном неравенстве может быть заменена произведением числа знаков на среднюю информационную емкость знака, т.е.: n*I1(A) ? n*I1 (B), или I1(A) ? m/n*I1 (B) Отношение m/n, очевидно, характеризует среднее число знаков вторичного алфавита, которое приходится использовать для кодирования одного знака первичного алфавита - будем называть его длиной кода или длиной кодовой цепочки и обозначим K(B) (верхний индекс указывает алфавит кодов). [ В частном случае, когда появление любых знаков вторичного алфавита равновероятно, согласно формуле Хартли I1(B)=log2M, и тогда I1(A) /log2M? K(B) (1) По аналогии с величиной R, характеризующей избыточность языка, можно ввести относительную избыточность кода (Q): Q= 1 - I(A) / I(B) = 1- I1(A) / K(B)*I1(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 знаков bj, 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. Операции кодирования и декодирования называют обратимыми, если их последовательное применение обеспечивает возврат к исходной форме сообщения без потери информации. Пусть Ar -- слово в алфавите А и Br =G(Ar) -- слово в алфавите В. Код называется обратимым, если для любого слова Br =G(Ar) в алфавите В существует единственное преобразование G-1(Br)= Ar . То есть, по слову Br в алфавите В, всегда однозначно восстанавливается слово Ar в алфавите А, из которого было образовано слово Br. Примером обратимого кодирования является представление знаков в телеграфном коде при передаче сообщений и восстановление их при приеме. Примером необратимого кодирования является перевод текста с одного естественного языка на другой. (Обратный перевод побуквенно обычно не соответствует исходному тексту.) Чтобы код был обратимым, необходимо: 1) чтобы разным символам входного алфавита А были сопоставлены разные кодовые комбинации; 2) чтобы никакая кодовая комбинация не составляла начальной части какой-нибудь другой кодовой комбинации. Наиболее простым правилом кодирования является сопоставление каждому символу входного алфавита А слова конечной длины в выходном алфавите В. Код может быть задан в форме таблицы, графа, аналитического выражения, то есть в тех же формах, что и отображение. Выражение (1) пока следует воспринимать как соотношение оценочного характера, из которого неясно, в какой степени при кодировании возможно приближение к равенству его правой и левой частей. По этой причине для теории связи важнейшее значение имеют две теоремы, доказанные Шенноном. Первая - затрагивает ситуацию с кодированием при передаче сообщения по линии связи, в которой отсутствуют помехи, искажающие информацию. Вторая теорема относится к реальным линиям связи с помехами.
Страницы: 1, 2, 3, 4, 5
|