40152

ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ. КЛАССИФИКАЦИЯ КОДОВ

Лекция

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

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

Русский

2014-09-21

146 KB

53 чел.

PAGE   \* MERGEFORMAT 1

ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ

Классификация кодов

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

По длине кодов и взаимному расположению в них символов различают равномерные и неравномерные коды.

Равномерные коды имеют одинаковую длину комбинаций. Для равномерного кода число возможных комбинаций составляет . Примером такого кода является пятизначный код Бодо, применяемый в телеграфии. Код Бодо содержит пять двоичных элементов (m = 2, n = 5). Число возможных кодовых комбинаций в этом коде равно , что позволяет кодировать все буквы русского алфавита (твердый знак не передают). Однако этого мало для передачи сообщения на русском языке, содержащего буквы, цифры, знаки препинания и условные знаки (точка, запятая, двоеточие, сложение, вычитание, умножение и т. д.). Поэтому применяют «Международный код №2» (МТК-2). В коде МТК-2 используется регистровый принцип, согласно которому одна и та же пятиэлементная кодовая комбинация может использоваться до трех раз в зависимости от положения регистра: русский, латинский, цифровой. Общее число различных знаков при этом равно 84, что достаточно для кодирования телеграммы.

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

Общая идея построения неравномерных кодов подсказывается теоремой кодирования 1 Шеннона для каналов без помех. Очевидно, что средняя длина неравномерного кода будет минимизироваться тогда, когда с более вероятными сообщениями источника будут сопоставляться более короткие комбинации канальных символов. Однако проблема заключается в том, что у неравномерного кода на приемной стороне оказываются неизвестными границы этих комбинаций. Если же попытаться их выделить, используя известный способ кодирования, то декодирование может оказаться неоднозначным (действительно, если, например, букве А присвоена комбинация 1, букве Б - 0, а букве В - 10, то невозможно определить по принятой комбинации 10, передавались ли буква В или пара букв А и Б). Для того, чтобы используемый код был однозначно декодируемым, он должен удовлетворять некоторым условиям. Однозначное декодирование будет обеспечено, если ни одно кодовое слово не является началом другого кодового слова. Коды, удовлетворяющие этим условиям, называются префиксными или неприводимыми. Кстати, равномерный код также является префиксным.

Наиболее известным неравномерным кодом является код Морзе, в котором символы 1 и 0 используется в двух сочетаниях - как одиночные (1 и 0) или как тройные (111 и 000). Сигнал, отражающий одну единицу, соответствует точке («.»), трем единицам – тире («-»). Символ 0 используется как знак, отделяющий точку от тире, точку от точки и тире от тире. Совокупность 000 используется как разделительный знак между кодовыми комбинациями.

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

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

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

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

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

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

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

Блоки, содержащие k символов каждый, по определенному закону преобразуются кодером в n-символьные блоки, причем  n  k. Например, схема блочного кодера

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

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

Блочные коды подразделяются на разделимые и неразделимые. К разделимым относятся коды, кодовые комбинации которых состоят из двух частей: информационной и проверочной. Обычно проверочные символы получаются посредством некоторых операций над информационными символами. Разделимые коды условно обозначают в виде (n, k), где n – число символов в кодовой комбинации, k – число информационных символов. Число проверочных символов в разделимых блочных кодах равно r = n-k.

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

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

Например, рассмотрим схему наиболее простого систематического кодера (5,4). Здесь всего лишь один проверочный символ формируется из информационных символов путем их суммирования по модулю 2. Этот код называют кодом с проверкой на четность. Так как новую разрешенную комбинацию систематического кода можно получить линейными преобразованиями двух разрешенных, то такие коды часто называют линейными или групповыми.

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

5.2 Основные характеристики помехоустойчивых кодов

Основными характеристиками помехоустойчивых кодов являются:

1. Длина кода nэто число символов в кодовой комбинации. Например, комбинация 11010 состоит из пяти символов, следовательно, n=5. Если все кодовые комбинации содержат одинаковое число символов, то код называется равномерным. В неравномерных кодах длина кодовых комбинаций может быть разной.

2. Основание кода m – это число различных символов в коде. Для двоичных кодов символами являются 1 и 0, поэтому m=2.

3. Число кодовых комбинаций для равномерного кода равно N=mn. Например, для равномерного двоичного кода, имеющего длину n=6, число различных кодовых комбинаций равно N=26=64.

4. Число разрешенных кодовых комбинаций Nр – это количество кодовых комбинаций кода, используемых для передачи сообщений. Для помехоустойчивых кодов Nр<N. Оставшиеся кодовые комбинации N-Nр называют запрещенными. Если Nр=N, то код является безызбыточным. Для разделимых кодов Nр=2 k.

5. Избыточность кода Ки в общем случае определяется выражением

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

,

где величина k/n называется относительной скоростью кода.

6. Кодовое расстояние d(А,В) – это число позиций, в которых две кодовые комбинации А и В отличаются друг от друга. Например, если А=01101, В=10111, то d(А,В)=3. Кодовое расстояние между комбинациями А и В может быть найдено в результате сложения по модулю 2 одноименных разрядов комбинаций, а именно

,

где ai и bii-е разряды кодовых комбинаций A и B; символ обозначает сложение по модулю 2.

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

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

Для обнаружения всех ошибок кратностью s и менее, минимальное кодовое расстояние должно удовлетворять условию

dmin  s +1 .

Если код используется для исправления ошибок кратности не более t, то минимальное кодовое расстояние должно иметь значение

dmin  2t +1.

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

Для обнаружения s ошибок и исправления t ошибок должно выполняться условие

dmin  s + t +1 .

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


 

А также другие работы, которые могут Вас заинтересовать

24788. ТЕОРИЯ ОРГАНИЗАЦИИ. Сущность системного подхода к организациям. Синергетический эффект в организациях 97.5 KB
  Системный подход стал фактически тем инструментом который позволил создать современную теорию организации. Можно сказать что теория организации как наука родилась именно в рамках этого подхода. Цели организации задаются извне или вырабатываются внутри нее с учетом этих целей выбираются форма и устройство организации.
24789. УПРАВЛЕНИЕ ПРСОНАЛОМ 147.5 KB
  Набор персонала заключается в комплектовании необходимого резерва кандидатов на все должности и специальности из которых организация отбирает подходящих для нее работников.; составление базы данных по кандидатам на вакантные должности; отбор персонала выявление различий между кандидатами и соответствующими требованиями будущей деятельности выбор лучших кандидатов; решение о приеме на работу; введение в должность адаптация работника. Это более тонкая по сравнению с отбором процедура идентификации характеристик человека и...
24790. РАЗРАБОТКА УПРАВЛЕНЧЕСКОГО РЕШЕНИЯ 73 KB
  Требования предъявляемые к управленческим решениям Сущность и виды управленческих решений Решение это выбор альтернативы. Решения принимаемые в процессе управления могут быть классифицированы по различным признакам. По уровню управления различают решения принимаемые на разных уровнях: начальника цеха начальника отдела; заместителя директора; директора; министра.
24791. УПРАВЛЕНИЕ ОБЩЕСТВЕННЫМИ ОТНОШЕНИЯМИ 42 KB
  Организация связей с общественностью в системе государственного и муниципального управления: общее и особенное. управления можно отнести: участие в демократизации государственного управления содействие становлению гражданского общества. Существует прямая зависимость между уровнем управления и особенностями служб PR: в региональных и муниципальных органах власти широко реализуется коммуникативная функция и общение с гражданами постоянно и организованно. Возможности PR могут быть использованы в целях повышения открытости государственного...
24792. ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ УПРАВЛЕНИЯ 59.5 KB
  наличие централизованных информационных центров генераторов баз данных 2. Например: Федеральная налоговая служба организовала Банк Данных глобальную базу данных. Локальные и распределенные базы данных системы управления базами данных. Информационные ресурсы представляют собой отдельные документы и отдельные массивы документов в информационных системах библиотеках архивах фондах банках данных других видах информационных систем.
24793. ИННОВАЦИОННЫЙ МЕНЕДЖМЕНТ. Технологические уклады, основные периоды. Прогноз 73 KB
  Инновации и жизненный цикл товара. Этап внедрения начинается с момента появления товара на тынке. Цены на первом этапе могут быть низкими либо высокими в зависимости от специфики и особенностей товара и потребителя. Примером товара находящегося на первом этапе ЖЦТ может служить цифровая фотокамера.
24794. ГОСУДАРСТВЕННЫЕ И МУНИЦИПАЛЬНЫЕ ФИНАНСЫ. Структура государственных финансов РФ 120 KB
  Структура государственных финансов РФ. Структура государственных финансов . Структуру государственных финансов можно определять с двух точек зрения. Государственные финансы могут быть рассмотрены с точки зрения преемственности к тем или иным органам государственной власти или с позиции разделения государственных финансов на бюджетные и не бюджетные фонды.
24795. ГЕОПОЛИТИКА 61 KB
  Сущность содержание и структура системы национальной безопасности государства. Законе Российской Федерации О безопасности национальная безопасность трактуется как состояние защищенности жизненно важных интересов личности общества государства от внутренних и внешних угроз. Под национальной безопасностью страны необходимо понимать систему элементов связей и отношений обеспечивающую реализацию жизненно важных политических экономических военных гуманитарных экологических информационных и других интересов личности общества и государства....
24796. Конституционное право России. Конституционные основы организации публичной власти в Российской Федерации 116.5 KB
  Государственную власть в РФ осуществляют Президент РФ Федеральное Собрание парламент состоит из двух палат: Совета Федерации и Государственной Думы Правительство РФ суды РФ существует единая судебная система РФ ее высшими звеньями являются Конституционный Суд РФ Верховный Суд РФ и Высший Арбитражный Суд РФ. Экономические и политические основы конституционного строя Российской Федерации: понятие содержание правовое регулирование. Установленные Конституцией положения связанные с отношением государства к человеку служат...