равномерный и неравномерный двоичный код

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

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

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

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

image002

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

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

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

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

A • − И • • P • − • Ш − − − − • − − − − − − − − •
Б − • • • Й • − − − С • • • Щ − − • − • • − − − − − − − −
В • − − К − • − Т Ъ • − − • − • • • • − − Точка • • • • • •
Г − − • Л • − • • У • • − Ь − • • − • • • • − Запятая • − • − • −
Д − • • М − − Ф • • − • Ы − • − − • • • • • / − • • − •
Е H − • Х • • • • Э • • − • • − • • • • ? • • − − • •
Ж • • • − О − − − Ц − • − • Ю • • − − − − • • • ! − − • • − −
З − − • • П • − − • Ч − − − • Я • − • − − − − • • @ • − − • − •

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

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

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

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

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

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

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

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

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

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

Источник

Равномерные и неравномерные двоичные коды. Условие Фано

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

Читайте также:  подбор кодов оквэд для ип

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

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

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

image008

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

image009

Для однозначности декодирования последовательности кодов достаточно выполнения хотя бы одного из двух вышеуказанных условий Фано:

— при выполнении прямого условия Фано последовательность кодов однозначно декодируется с начала;

— при выполнении обратного условия Фано последовательность кодов однозначно декодируется с конца.

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

Вместе с тем нужно помнить, что правила Фано — это достаточное, но не необходимое условие однозначного декодирования: если не выполняется ни прямое, ни обратное правило Фано, конкретная двоичная последовательность может оказаться такой, что она декодируется однозначно (так как остальные возможные варианты до конца декодирования довести не удаётся). В подобном случае необходимо пытаться строить дерево декодирования в обоих направлениях.

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

Если для заданной последовательности кодов выполняется прямое правило Фано, то её декодирование необходимо вести с начала (слева направо).

Если для заданной последовательности кодов выполняется обратное правило Фано, то её декодирование необходимо вести с конца (справа налево).

При сравнении пары кодов удобно подписывать более короткий код под более длинным, выравнивая эти записи по левому краю — для прямого правила Фано либо по правому краю — для обратного правила Фано.

Разбор типовых задач

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Использовали код: А-1, Б-000, В-001, Г-011. Укажите, каким кодовым словом должна быть закодирована буква Д. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования.

Источник

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

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

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

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

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

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

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

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

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

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

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

Читайте также:  леди баг в полный рост рисунок

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

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

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

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

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

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

Источник

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

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

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

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

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

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

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

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

Символ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

Информатика. 7 класс

Конспект урока

Кодирование информации. Двоичный код

Перечень вопросов, рассматриваемых в теме:

Дискретизация информации – процесс преобразования информации из непрерывной формы представления в дискретную. Чтобы представить информацию в дискретной форме, её следует выразить с помощью символов какого-нибудь естественного или формального языка.

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

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

1. Босова Л. Л. Информатика: 7 класс. // Босова Л. Л., Босова А. Ю. – М.: БИНОМ, 2017. – 226 с.

Теоретический материал для самостоятельного изучения

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

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

Читайте также:  поддельный сайт госуслуг с qr кодом

Дискретизация информации – процесс преобразования информации из непрерывной формы представления в дискретную.

Рассмотрим суть процесса дискретизации информации на примере.

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

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

a492151c 4f2d 4d9e bf19 338e290df0e4

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

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

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

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

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

Алфавит, содержащий два символа, называется двоичным алфавитом (рис. 3). Представление информации с помощью двоичного алфавита называют двоичным кодированием. Закодировав таким способом информацию, мы получим её двоичный код.

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

7f28bccf aa35 41ee a71e 03c78f37c490

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

34aac773 6ce5 4757 9294 2ebb2f3f3383

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

021ab1cc 1839 40c5 b587 6fff53f6830c

Цепочки из трёх двоичных символов получаются дополнением двухразрядных двоичных кодов справа символом 0 или 1. В итоге кодовых комбинаций из трёх двоичных символов получается 8 – вдвое больше, чем из двух двоичных символов:

3b2b9e59 f377 46ee a205 93f3da91ede2

Соответственно, четырёхразрядный двоичный код позволяет получить 16 кодовых комбинаций, пятиразрядный – 32, шестиразрядный – 64 и т. д.

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

c1f6e14c 80dc 4327 8148 2769968885d4

Обратите внимание, что:

32 = 2 ∙ 2 ∙ 2 ∙ 2 ∙ 2 и т. д.

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

Если количество кодовых комбинаций обозначить буквой N, а разрядность двоичного кода – буквой i, то выявленная закономерность в общем виде будет записана так:

86dc198b b8cc 4f43 861a 08f8f21731e8

В математике такие произведения записывают в виде:

Запись 2 i читают так: «2 в i-й степени».

Задача. Вождь племени Мульти поручил своему министру разработать двоичный код и перевести в него всю важную информацию. Двоичный код какой разрядности потребуется, если алфавит, используемый племенем Мульти, содержит 16 символов? Выпишите все кодовые комбинации.

Чтобы выписать все кодовые комбинации из четырёх 0 и 1, воспользуемся схемой на рис. 1.13: 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111.

Универсальность двоичного кодирования

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

ccc9f3e5 df44 430c 8664 22e39f9f8bd7

Двоичные коды широко используются в компьютерной технике, требуя только двух состояний электронной схемы – «включено» (это соответствует цифре 1) и «выключено» (это соответствует цифре 0).

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

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

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

Выше мы рассмотрели равномерные двоичные коды.

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

Разбор решения заданий тренировочного модуля

№1.Тип задания: ввод с клавиатуры пропущенных элементов в тексте

Переведите десятичное число 273 в двоичную систему счисления.

Воспользуемся алгоритмом перевода целых чисел из системы с основанием p в систему с основанием q:

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

2. Последовательно выполнять деление данного числа и получаемых целых частных на основание новой системы счисления до тех пор, пока не получим частное, меньшее делителя.

3. Полученные остатки, являющиеся цифрами числа в новой системе счисления, привести в соответствие с алфавитом новой системы счисления.

4. Составить число в новой системе счисления, записывая его, начиная с последнего остатка.

8780ed92 c210 4bd5 99b9 5ceceaa833f9

Ответ: 27310= 100010001.

№2. Тип задания: единичный / множественный выбор.

Четыре буквы латинского алфавита закодированы кодами различной длины:

Источник

Поделиться с друзьями
admin
Здоровый образ жизни: советы и рекомендации
Adblock
detector