средняя длина равномерного кода

Равномерные и неравномерные коды.

Дата добавления: 2015-08-14 ; просмотров: 32926 ; Нарушение авторских прав

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

Другим интересным примером равномерного кода является код Трисиме, в котором знакам латинского алфавита ставятся в соответствие кодовые слова длины 3 над алфавитом из 3-х символов: <1, 2, 3>. Этот код представлен в следующей таблице :

Понятно, что код Трисиме не может кодировать более чем 3 3 =27 символов.

Число букв в алфавите кода называется основанием кода, а длина кодовых слов равномерного кода называется порядком кода. Коды с основанием 2, как уже говорилось, называются двоичными, а с основанием 3 – троичными, и так далее. Так код Бодо имеет основание 2, а порядок 5, а у кода Трисиме и основание, и порядок равны 3.

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

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

Американский изобретатель телеграфа Сэмюель Морзе разработал этот код в 1838 году для передачи телеграфных сообщений в виде последовательности электрических сигналов, передаваемых от одного телеграфного аппарата по проводам к другому телеграфному аппарату. Этот код был придуман Морзе задолго до научных исследований

СэмюэлМорзе (1791-1872)

относительной частоты появления различных букв в текстах, но, тем не менее, Морзе при составлении кода использовал принцип частоты букв. Буквам, используемым чаще, им присвоены короткие кодовые комбинации, редко используемым буквам – длинные. Морзе оценил относительную частоту букв английского языка подсчетом литер в ячейках типографской наборной машины. Наиболее часто используемой букве «Е» (в английском языке) он присвоил наиболее короткий код «точка». Следующей по количеству литер букве он присвоил код несколько большей длительности и так далее.

При составлении азбуки Морзе для букв русского алфавита учет относительной частоты букв не производился, и это повысило его избыточность. Расчеты избыточности кода Морзе на основании проведенных исследований частоты появления букв показали, что для букв английского алфавита она составляет 19%, для букв русского алфавита 22%.

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

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

Этот код неравномерный (кодовые слова разной длины).

Закодируем последовательность сообщений: s₇s₇. Имеем F(s₇s₇)=B=111111. Но эта последовательность может быть декодирована и по-другому, так как: B=F(s₃s₃s₃)= F(s₁s₃s₇)=F(s₃s₇s₁)=F(s₁s₁s₁s₁s₁s₁s₁s). Как видим, способов декодирования много (подсчитайте: сколько их?). Неоднозначно декодируется и следующая последовательность:

11011011 (а сколько здесь способов декодирования?). Очевидно, что такой код практически использовать нельзя. А если мы изменим код так, чтобы он стал равномерным, например, доопределим функцию F так:

то теперь никаких проблем с декодированием не будет.

Источник

Информационные технологии

Неравномерное кодирование. Средняя длина кодирования

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

Наиболее экономным является код с наименьшей средней длиной . Сравним на примерах экономичность различных способов кодирования одного и того же источника.

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

	00
	01
A_3	10
A_4	11

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

	0
	1
	10
	11

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

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

Необходимо отметить, что неоднозначность декодирования слова появилась несмотря на то, что условие однозначности декодирования знаков (инъективность кодового отображения) выполняется.

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

Рассмотрим код (схему алфавитного кодирования) , заданный кодовой таблицей

и различные слова, составленные из элементарных кодов.

Определение. Код называется однозначно декодируемым, если

Если таблица кодов содержит одинаковые кодовые слова, то есть если

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

Префиксные коды

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

Теорема 1. Префиксный код является однозначно декодируемым.

Множество кодовых слов можно графически изобразить как поддерево словарного дерева (рис.6.5). Для этого из всего словарного дерева следует показать только вершины, соответствующие кодовым словам, и пути, ведущие от этих вершин к корню дерева. Такое поддерево называют деревом кода или кодовым деревом.

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

Если код префиксный, то, читая кодовую запись подряд от начала, мы всегда сможем разобраться, где кончается одно кодовое слово и начинается следующее. Если, например, в кодовой записи встретилось кодовое обозначение 110, то разночтений быть не может, так как в силу префиксности наш код не содержит кодовых обозначений 1, 11 или, скажем, 1101. Именно так обстояло дело для рассмотренного выше кода, который очевидно является префиксным.

Источник

1.2. Преобразование сообщения в сигналы

1.2.1. Кодирование сообщений

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

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

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

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

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

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

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

Простые код» делят на равномерные и неравномерные.

Равномерными называются такие коды, в которых все кодовые комбинации имеет одинаковую длину, т.е. имеют одинаковое чис­ло единичных элементов.

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

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

1.2.2. Равномерные простые коды

Как следует из определения, простые равномерные коды сос­тоят из комбинаций одинаковой длины. Естественно, возникает вопрос:

Хорошо это или плохо?» Для ответа на этот вопрос рас­смотрим следующий пример.

Пусть имеется некоторое сообщение, состоящее из М эле­ментов, представляющее собой некоторую последовательность m(m

Источник

2.1. Алфавитное неравномерное двоичное кодирование сигналами равной длительности. Префиксные коды

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

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

Неравномерный код с разделителем

В соответствии с перечисленными правилами строится кодовая табл. 3.1 для букв русского алфавита, основываясь на приведенных ранее (табл. 1.3) вероятностях появления отдельных букв.

Теперь по формуле нахождения среднего для значений случайных независимых величин можно найти среднюю длину кода К(r,2) для данного способа кодирования:

Поскольку для русского языка I₁ ( r ) = 4,356 бит, избыточность данного кода, согласно (3.9), составляет:

это означает, что при данном способе кодирования будет передаваться приблизительно на 14% больше информации, чем содержит исходное сообщение. Аналогичные вычисления для английского языка дают значение К(е,2) = 4,716, что при I₁ ( e ) = 4,036 бит приводят к избыточности кода Q(е,2) = 0,168.

Рассмотрев один из вариантов двоичного неравномерного кодирования, необходимо ответить на следующие вопросы: возможно ли такое кодирование без использования разделителя знаков? Существует ли наиболее эффективный (оптимальный) способ неравномерного двоичного кодирования?

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

Неравномерный код может быть однозначно декодирован, если никакой из кодов не совпадает с началом (префиксом) какого-либо иного более длинного кода.

Например, если имеется код 110, то уже не могут использоваться коды 1, 11, 1101, 110101 и пр. Если условие Фано выполняется, то при прочтении (расшифровке) закодированного сообщения путем сопоставления с таблицей кодов всегда можно точно указать, где заканчивается один код и начинается другой.

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

Требуется декодировать сообщение:

Декодирование производится циклическим повторением следующих действий:

(a) отрезать от текущего сообщения крайний левый символ, присоединить справа к рабочему кодовому слову;

(b) сравнить рабочее кодовое слово с кодовой таблицей; если совпадения нет, перейти к (а);

(c) декодировать рабочее кодовое слово, очистить его;

(d) проверить, имеются ли еще знаки в сообщении; если «да», перейти к (а).

Применение данного алгоритма дает:

Рис. 3.1. Результат применения алгоритма

Доведя процедуру до конца, получается сообщение: «мама мыла раму».

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

Префиксный код Шеннона-Фано

Процедура построения кодов

Из процедуры построения кодов легко видеть, что они удовлетворяют условию Фано и, следовательно, код является префиксным. Средняя длина кода равна:

I₁ ( A ) = 2,390 бит. Подставляя указанные значения в (3.5), получается избыточность кода Q(A,2) = 0,0249, т.е. около 2,5%. Однако, данный код нельзя считать оптимальным, поскольку вероятности появления 0 и 1 неодинаковы (0,35 и 0,65, соответственно). Применение изложенной схемы построения к русскому алфавиту дает избыточность кода 0,0147.

Префиксный код Хаффмана

Рис. 3.2. Процедура построения кодов

К(А,2) = 0,3 ∙ 2 + 0,2 ∙ 2 + 0,2 ∙ 2 +0,15 ∙ 3 + 0,1 ∙ 4 + 0,05 ∙ 4 = 2,45. (3.13)

Рис. 3.3. Обратная процедура построения кодов

Избыточность снова оказывается равной Q(A, 2) = 0,0249, однако, вероятности 0 и 1 сблизились (0,47 и 0,53, соответственно). Более высокая эффективность кодов Хаффмана по сравнению с кодами Шеннона-Фано становится очевидной, если сравнить избыточности кодов для какого-либо естественного языка. Применение описанного метода для букв русского алфавита порождает коды, представленные в табл. 3.4. (для удобства сопоставления они приведены в формате табл. 3.1).

Коды для букв русского алфавита

Средняя длина кода оказывается равной К(r,2) = 4,395; избыточность кода Q(r,2) = 0,0090, т.е. не превышает 1 %, что заметно меньше избыточности кода Шеннона-Фано (см. выше).

Код Хаффмана важен в теоретическом отношении, поскольку можно доказать, что он является самым экономичным из всех возможных, т.е. ни для какого метода алфавитного кодирования длина кода не может оказаться меньше, чем код Хаффмана.

Источник

Средняя длина равномерного кода

Здравствуйте! Меня зовут Александр Георгиевич. Я являюсь профессиональным репетитором в области информационных технологий, математике, баз данных и программирования.

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

Чтобы гарантированно набрать на официальном экзамене ОГЭ или ЕГЭ по информатике высоченный балл берите сотовый телефон, дозванивайтесь до меня и задавайте любые интересующие вопросы.

Рекомендую использовать формат дистанционного обучения! Это выгодно, удобно и эффективно!

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

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

Но ваш соратник без особых проблем сможет провести дешифрацию вашего информационного сообщения, так как вы ему расскажете об алгоритме шифрации/дешифрации.

Символ

Равномерный код

Десятичное представление

Равномерный код – такой код, когда все символы какого-либо алфавита кодируются кодами одинаковой длины.

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

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

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

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

Неравномерный код – такой код, когда все элементы какого-либо множества кодируются кодом различной длины.

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

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

А как поступить с наименее популярными товарами, например, муку и перец также достаточно часто покупают. В этом случае данные товары можно запрограммировать так:

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

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

Равномерный код vs неравномерный код

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

А сейчас я вам предлагаю ознакомиться с мультимедийным решением, в котором я показываю, как правильно оперировать равномерным и неравномерным кодом.

Я хочу записаться к вам на индивидуальный урок по информатике и ИКТ

Если у вас остались какие-либо вопросы по рассматриваемой теме, то записывайтесь ко мне на первый пробный урок. Я репетитор-практик, следовательно, на своих уроках я уделяю максимум внимания решению заданий. Из теории лишь записываются самые базовые сведения: определения, тезисы, формулировки теорем и аксиом.

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

Не откладывайте свое решение в долгий ящик. Я все-таки достаточно востребованный и квалифицированный репетитор, поэтому звоните прямо сейчас – количество ученических мест ограниченно!

Источник