Оглавление 

 

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

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

 

      ^П

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

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

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

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

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

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

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

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

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

      Пусть первичный алфавит 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)), тем более выгодным оказывается код и более эффективной операция кодирования. Выгодность кодирования при передаче и хранении – это экономический фактор, поскольку более эффективный код позволяет затратить на передачу сообщения меньше энергии, а также времени и, соответственно, меньше занимать линию связи; при хранении используется меньше площади поверхности (объема) носителя. При этом следует сознавать, что выгодность кода не идентична временной выгодности всей цепочки кодирование – передача – декодирование; возможна ситуация, когда за использование эффективного кода при передаче придется расплачиваться тем, что операции кодирования и декодирования будут занимать больше времени и иных ресурсов (например, места в памяти технического устройства, если эти операции производятся с его помощью).

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

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

      Основными задачами кодирования являются:

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

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

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 к любому слову из входного алфавита называется кодированием. То есть код - это правило отображения знаков одного алфавита в знаки другого алфавита, кодирование – это преобразование одной формы сообщения в другую посредством указанного кода.

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

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

      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) пока следует воспринимать как  соотношение оценочного характера, из которого неясно, в какой степени при кодировании возможно приближение к равенству его правой и левой частей. По этой причине для теории связи важнейшее значение имеют две теоремы, доказанные Шенноном. Первая – затрагивает ситуацию с кодированием при передаче сообщения по линии связи, в которой отсутствуют помехи, искажающие информацию. Вторая теорема относится к реальным линиям связи с помехами.

 

      

2. Первая теорема Шеннона

 

      ^Р

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