Способы кодирования двоичное кодирование

MT1402: Теоретические основы информатики. Имитационное моделирование

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

Как следует из названия, в способах кодировании, относящихся к этой группе, знаки первичного алфавита (например, русского) кодируются комбинациями символов двоичного алфавита (т.е. 0 и 1), причем, длина кодов и, соответственно, длительность передачи отдельного кода, могут различаться. Длительности элементарных сигналов при этом одинаковы %%(τ_0 = τ_1 = τ)%%. Очевидно, для передачи информации, в среднем приходящейся на знак первичного алфавита, необходимо время %%K(A,2) \cdot τ%%.

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

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

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

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

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

Условимся, что разделителем отдельных кодов букв будет последовательность 00 (признак конца знака), а разделителем слов-слов — 000 (признак конца слова — пробел). Довольно очевидными оказываются следующие правила построения кодов:

• код признака конца знака может быть включен в код буквы, поскольку не существует отдельно (т.е. кода всех букв будут заканчиваться 00);
• коды букв не должны содержать двух и более нулей подряд в середине (иначе они будут восприниматься как конец знака);
• код буквы (кроме пробела) всегда должен начинаться с 1;
• разделителю слов (000) всегда предшествует признак конца знака; при этом реализуется последовательность 00000 (т.е., если в конце кода встречается комбинация . 000 или . 0000, они не воспринимаются как разделитель слов); следовательно, коды букв могут оканчиваться на 0 или 00 (до признака конца знака).

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

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

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

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

Буква	Код	%%p_j\cdot 10^3%%	%%k_j%%	Буква	Код	%%p_j\cdot 10^3%%	%%k_j%%
пробел	000	174	3	я	1011000	18	7
о	100	90	3	ы	1011100	16	7
е	1000	72	4	з	1101000	16	7
а	1100	62	4	ь,ъ	1101100	14	7
и	10000	62	5	б	1110000	14	7
т	10100	53	5	г	1110100	13	7
н	11000	53	5	ч	1111000	12	7
с	11100	45	5	й	1111100	10	7
р	101000	40	6	х	10101000	9	8
в	101100	38	6	ж	10101100	7	8
л	110000	35	6	ю	10110000	6	8
к	110100	28	6	ш	10110100	6	8
м	111000	26	6	ц	10111000	4	8
д	111100	25	6	щ	10111100	3	8
п	1010000	23	7	э	11010000	3	8
у	1010100	21	7	ф	11010100	2	8

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

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

• В языковедении термин «префикс» означает «приставка».

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

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

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

а	л	м	р	у	ы
10	010	00	11	0110	0111

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

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

• (a) отрезать от текущего сообщения крайний левый символ, присоединить справа к рабочему кодовому слову;
• (b) сравнить рабочее кодовое слово с кодовой таблицей; если совпадения нет, перейти к (а);
• (c) декодировать рабочее кодовое слово, очистить его;
• (d) проверить, имеются ли еще знаки в сообщении; если «да», перейти к (а).

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

шаг	рабочее слово	текущее сообщение	распознанный знак	декодированное сообщение
0	Пусто	0010001000011101010101110000110	—	—
1	0	0100010000111010101110000110	нет	—
2	00	1000100001110101011110000110	м	м
3	1	0001000011101010101110000110	нет	м
4	10	0010000111010101110000110	а	ма
5	0	010000111010101110000110	нет	ма
6	00	10000111010101110000110	м	мам
.

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

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

Источник

Информатика

Именная карта банка для детей
с крутым дизайном, +200 бонусов

Закажи свою собственную карту банка и получи бонусы

План урока:

Примеры кодирования информации:

• трансляция письменных сообщений с использованием русских букв (АБВГД…ЭЮЯ);
• запись чисел цифрами (0123456789);
• использование языка жестов при общении глухонемых людей

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

Информация проходит кодирование в целях:

• упрощения сбора исходных данных;
• сокращения объема занимаемой памяти информационными сообщениями;
• удобства хранения материалов;
• эффективной обработки и обмена информацией;
• сокрытия необходимых сведений.

История кодирования информации насчитывает сотни веков. Издавна люди использовали криптограммы (зашифрованные сообщения).

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

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

Разработанная в 1948г. К. Шенноном «Теория информации и кодирования» стала основополагающей в современном кодировании данных.

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

Способы кодировки

Проанализируем разнообразные виды информации и особенности ее кодирования.

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

• графическая;
• аудиоинформация (звуковая);
• символьная (текстовая);
• числовая;
• видеоинформация.

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

Соответственно происходит и классификация информации по способу кодирования:

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

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

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

• преобразование текста;
• графическая кодировка;
• кодирование числовых данных;
• перевод звука в бинарную последовательность чисел;
• видеокодирование.

Различают такие методы кодирования информации как:

• метод замены (подстановки) – знаки первоначального сообщения заменяются на соответствующие символы выбранного кодового алгоритма;
• метод перестановки – символы оригинального текста меняются местами по определенной схеме;
• метод гаммирования – к исходным обозначениям добавляется случайная последовательность других знаков.

Двоичный код

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

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

Двоичное кодирование информации применяется для различных данных:

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

Обработка графических изображений

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

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

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

Кодирование графической информации – это процедура присвоения каждому компоненту изображения определенного кодового значения.

Способы кодирования графической информации подчиняются методам представления изображений (растрового или векторного):

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

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

Источник

Многим станет интересно: «В чем суть кодирования графической информации, представленной в виде 3D-изображений?» Дело в том, что работа с трехмерными данными сочетает способы растровой и векторной кодировки.

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

Метод координат

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

Метод координат на плоскости основан на изучении свойств точки в системе координат с горизонтальной осью Ox и вертикальной осью Oy. Точка будет иметь 2 координаты.

Если через начало координат проходит 3 взаимно перпендикулярные оси X, Y и Z, то используется метод координат в пространстве. Положение точки в таком случае определяется тремя координатами.

Система координат в пространстве

Перевод чисел в бинарный код

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

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

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

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

1. число нужно разделить на 2;
2. если частное больше 1, то необходимо продолжить деление до того момента, пока результат будет равен 0 или 1;
3. записать результат последней операции и остатки от деления в обратной последовательности;
4. полученное число и будет являться искомым кодовым значением.

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

Рассмотрим подробнее самые распространенные стандарты ASCII и Unicode – то, что применяется для кодирования символьной информации во всем мире.

Фрагмент таблицы ASCII

Первоначально было установлено, что для любого знака отводится в памяти компьютера 8 бит (1 бит – это либо «0», либо «1») бинарной последовательности. Первая таблица кодировки ASCII (переводится как «американский кодовый стандарт обмена сообщениями») содержала 256 символов. Ограниченная численность закодированных знаков, затрудняющая межнациональный обмен данными, привела к необходимости создания стандарта Unicode, основанного на ASCII. Эта международная система кодировки содержит 65536 символов. Закодировать огромное количество всевозможных обозначений стало возможным благодаря использованию 16-битного символьного кодирования.

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

Выбирать способ кодирования информации – графический, числовой или символьный необходимо отталкиваясь от цели кодировки. Например, число «21» можно ввести в компьютерную память цифрами или буквами «двадцать один», слово «ЗИМА» можно передать русскими буквами «зима» или латинскими «ZIMA», штрих-код товара передается изображением и цифрами.

Преобразование звука

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

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

1. дискретизировать (разделить аудиоданные на элементарные участки путем измерения колебаний воздуха через одинаковые интервалы времени);
2. оцифровать (присвоить каждому элементу числовой код).

Преобразование звука: а) аналоговый сигнал; б)дискретный сигнал.

Различают следующие методы кодирования звуковой информации:

• Метод FM. Суть его сводится к разделению звука аналого-цифровыми преобразователями (АЦП) на одинаковые простейшие элементы, которые в дальнейшем кодируются бинарным кодом. Несовершенство метода FM проявляется в низком качестве звукозаписи из-за потери некоторого объема исходного звукового сообщения.
• Метод Wave-Table (таблично-волновой) позволяет получить высококачественный продукт, поскольку разработанные таблицы сэмплов (образцов «живых» звуков) позволяют выразить бинарными числами разнообразные параметры поступающего сигнала.

Обработка текста

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

Кодирование текстовой информации – присвоение любому символу текста кода из кодировочной системы. Различают следующие стандарты кодировки:

1. ASCII – первая международная система кодировки, содержащая коды на 256 знаков.
2. Unicode – расширенный стандарт ASCII, превышающий ее размером в 256 раз.
3. КОИ-8, СР1251, СР866, ISO – русские таблицы кодировки букв. При этом следует понимать, что документ, закодированный одним стандартом, не будет читаться в другом.

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

• мощность алфавита;
• единицы измерения памяти (биты и байты).

Например, мощность алфавита ASCII составляет 256 символов. При этом один знак занимает 8 бит (или 1 байт) памяти, а Unicode – 35536 символов и 16 бит (или 2 байта) соответственно.

Источник