В чем заключается алфавитное кодирование кратко

Обновлено: 06.07.2024

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

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

где iÎ[1, n], число п показывает количество букв в слове и называется длиной слова a, обозначается п = l(a) = |a|.

Пустое слово обозначается L: l(L) = |L| = 0.

Для слова a = a₁, a₂, … , a_i, …, a_n буква a₁ называется началом, или префиксом слова a, а буква a_n – окончанием, или постфиксом слова a.

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

Соединение слов a₁ и a₂ обозначается a₁,a₂, соединение п одинаковых слов a обозначается a n , причем a 0 = L.

Множество всех непустых слов алфавита Аобозначается А * :

Обозначим через F отображение слов алфавита А в алфавит В.Тогда слово b = F(a) называется кодом слова a.

Процесс обратного преобразования слова bÎB * в слово aÎA * называется декодированием. Таким образом, декодирование – функция, обратная F, т.е. F -1 .

Так как для любого кодирования должна выполняться операция декодирования, то отображение должно быть обратимым (биекция).

Если |B|= m, то F называется m-ичным кодированием, наиболее распространенный случай В = – двоичное кодирование. Именно этот случай и рассматривается в дальнейшем.

Если все кодовые слова имеют одинаковую длину, то код называется равномерным, илиблочным.

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

где a_i Î A, b_i Î B.

Пусть заданы алфавиты:

Тогда таблица кодирования может быть подстановкой:

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

не является взаимно-однозначной. Например, набор из шести единиц 111111 может соответствовать как слову 333, так и 77, а также 111111, 137, 3311 или 7111 плюс любая перестановка.

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

Схема алфавитного кодирования называется разделимой, если любое слово, составленное из элементарных кодов, разлагается на элементарные коды единственным образом.

Алфавитное кодирование с разделимой схемой допускает декодирование. Можно доказать, что префиксная схема является разделимой.

Для того чтобы схема алфавитного кодирования была разделимой, необходимо, чтобы длины элементарных кодов удовлетворяли соотношению, известному как неравенство Макмиллана.

Неравенство Макмиллана

Если схема алфавитного кодирования:

разделима, то справедливо неравенство:

Схема алфавитного кодирования:

является разделимой, так как:

и, значит, выполняется неравенство Макмиллана:

Данная схема префиксной не является, так как элементарный код буквы а является префиксом элементарного кода буквы b.

Лекция 4.

© 2014-2022 — Студопедия.Нет — Информационный студенческий ресурс. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав (0.004)

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

Одна и та же запись может нести разную смысловую нагрузку. Например, набор цифр 251299 может обозначать: массу объекта; длину объекта; расстояние между объектами; номер телефона; запись даты 25 декабря 1999 года.

Для представления информации могут использоваться разные коды и, соответственно, надо знать определенные правила - законы записи этих кодов, т.е. уметь кодировать.

Код - набор условных обозначений для представления информации.

Кодирование - процесс представления информации в виде кода.

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

Кодировать информацию можно различными способами: устно; письменно; жестами или сигналами любой другой природы.

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

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

1) графический - с помощью рисунков или значков;

2) числовой - с помощью чисел:

3) символьный с помощью символов того же алфавита, что и исходный текст.

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

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

Кодирование текстовой информации

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

Учитывая, что каждый бит принимает значение 0 или 1, количество их возможных сочетаний в байте равно 28 = 256. Значит, с помощью 1 байта можно получить 256 разных двоичных кодовых комбинаций и отобразить с их помощью 256 различных символов. Такое количество символов вполне достаточно для представления текстовой информации, включая прописные и заглавные буквы русского и латинского алфавита, цифры, знаки, графические символы и т.д.

Кодирование заключается в том, что каждому символу ставится в соответствие уникальный десятичный код от 0 до 255 или соответствующий ему двоичный код от 00000000 до 11111111. Таким образом, человек различает символы по их начертанию, а компьютер - по их коду.

Важно, что присвоение символу конкретного кода - это вопрос соглашения, которое фиксируется в кодовой таблице. Кодирование текстовой информации с помощью байтов опирается на несколько различных стандартов, но первоосновой для всех стал стандарт ASCII (American Standart Code for Information Interchange), разработанный в США в Национальном институте ANSI (American National Standarts Institute). В системе ASCII закреплены две таблицы кодирования - базовая и расширенная. Базовая таблица закрепляет значения кодов от 0 до 127, а расширенная относится к символам с номерами от 128 до 255.

Первые 33 кода (с 0 до 32) соответствуют не символам, а операциям (перевод строки, ввод пробела и т. д.).

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

Коды с 128 по 255 являются национальными, т.е. в национальных кодировках одному и тому же коду соответствуют различные символы. В настоящее время существует много различных кодовых таблиц для русских букв (КОИ-8, СР1251, СР866, Mac, ISO),поэтому тексты, созданные в одной кодировке , могут не правильно отображаться в другой.

Кодирование графической информации

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

Для получения черно-белого изображения (без полутонов) пиксель может принимать только два состояния: “белый” или “черный”. Тогда для его кодирования достаточно 1 бита:

Пиксель на цветном дисплее может иметь различную окраску. Поэтому 1 бита на пиксель – недостаточно.

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

00 – черный 10 – зеленый

01 – красный 11 – коричневый

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

1 1 0 Коричневый

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

Шестнадцатицветная палитра получается при использовании 4-разрядной кодировки пикселя: к трем битам базовых цветов добавляется один бит интенсивности. Этот бит управляет яркостью всех трех цветов одновременно.

Содержание работы

Содержимое работы - 1 файл

Алфавитное кодирование.doc

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

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

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

2.1. Основные определения.

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

Пусть L – язык. Под двоичным кодированием языка L понимается инъективное отображение f : L → + , где + - множество всех непустых двоичных последовательностей. Далее под кодированием будет пониматься двоичное кодирование.

Отображение f ставит в соответствие слову β ∈ L слово α ∈ + , α будем называть

кодироваться разными двоичными последовательностями. При выполнении этого

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

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

из B*, а в качестве способа кодирования применяется побуквенное, или алфавитное,

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

Коды v_i называются элементарными, а их набор V = (v₁, v₂,… v_m) - кодом.

При построении схемы кодирования используется дополнительная информация о вероятностях появления букв – вероятностное распределение P = (p₁,p₂,…p_m).

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

1. Проблема распознавания взаимной однозначности алфавитного кодирования;
2. Задача построения схемы кодирования, обеспечивающего наибольшее сжатие.

2.2. Проблема распознавания взаимной однозначности алфавитного кодирования

Пример 2.1. Рассмотрим схему

f ₁ задает взаимно-однозначное кодирование. Достаточно заметить, что перед каждым вхождением символа 1 стоит символ 0, поэтому каждое вхождение 1 вместе с предшествующим нулем кодирует букву b₂. Символ 0, за которым не следует 1, кодирует

букву b₁. Например, последовательность β = 001010001 имеет единственную

расшифровку α = b₁b₂b₂b₁b₁b₂.

Пример 2.2. Рассмотрим схему

Кодирование, задаваемое схемой f₂, не является взаимно-однозначным. Последовательность β= 001 допускает две расшифровки α₁ = b₁ b₂ и α₂ = b₃.

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

проверить бесконечное множество пар слов.

Определение 2.1. Пусть слово α имеет вид α₁α₂. Тогда α₁ называется префиксом слова α, а α₂ - суффиксом α. Если 0

Определение 2.2. Схема алфавитного кодирования f обладает свойством префикса,

если для любых i и j (1 ≤ i, j ≤ m, i ≠ j) элементарный код v_i не является префиксом

элементарного кода v_j.

Определение 2.3. Алфавитное кодирование, схема которого обладает свойством префикса, называется префиксным.

Теорема 2.1. Если схема обладает свойством префикса, то алфавитное кодирование является взаимно-однозначным.

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

Теорема 2.2. Если алфавитное кодирование со схемой f обладает свойством взаимной

однозначности, то длины элементарных кодов l_i = | v_i | (i =1,…, m) удовлетворяют неравенству Мак-Миллана:

Неравенство Мак-Миллана является необходимым условием взаимной однозначности

кода со схемой f, но не достаточным.

Рассмотрим схему , f₂ приведенную ранее:

Для нее l₁ = 1, l₂ = 2, и l₃ = 3, и неравенство Мак-Миллана выполняется: 2 -1 + 2 -2 + 2 -3 = 7 /8

Теорема 2.3. Если набор натуральных чисел l₁,l₂,…l_m удовлетворяет неравенству

Мак-Миллана, то существует префиксное кодирование, удовлетворяющее равенствам:

| v₁ | = l₁ ,| v₂ | = l₂,…,| v_m | = l m .

Следствие. Если существует взаимно-однозначное алфавитное кодирование с заданными длинами элементарных кодов, то существует также префиксное кодирование с теми же длинами элементарных кодов.

Неравенство Мак-Миллана в силу справедливости теоремы 2.3 можно рассматривать и

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

Пусть задан код V = (v₁,v₂,…v_m). Элементарные коды определяют бинарное кодовое дерево. Из каждой вершины дерева выходит не более двух ребер в вершины следующего яруса, левое из которых помечается символом 0, а правое – символом 1. Элементарным

кодам соответствуют вершины дерева, определяемые путем, идущим от корня. Если код префиксный, элементарные коды расположены в листьях дерева.

Дерево называется насыщенным, если из каждой вершины, не являющейся листом, в

следующий ярус выходит ровно два ребра.

На рис. 2.1 изображено дерево для схемы префиксного кодирования f₃.

Рис.2.1. Кодовое дерево для схемы кодирования f₃.

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

Ал. А. Марковым (1963 г.). Алгоритм распознавания состоит в следующем.

Для кода V = (v₁,v₂,…v_m) пусть S₁ - множество слов, обладающих следующим свойством. Слово β является собственным префиксом некоторого элементарного кода v_i и одновременно собственным суффиксом некоторого v_j. Положим S = S₁ ∪ < λ>( λ - пустое слово).

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

Кодирование текстовой информации

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

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

• 0 — импульс отсутствует;
• 1 — импульс присутствует.

Кодирование текстовой информации и компьютеры

Если смотреть на текст глазами компьютера, то в тексте нет предложений, абзацев, заголовков и т. д., потому что весь текст просто состоит из отдельных символов. Причем символами будут являться не только буквы, но и цифры, и любые другие специальные знаки (+, -,*,= и т. д.). Что самое интересное, даже пробелы, перенос строки и табуляция — для компьютера это тоже отдельные символы.

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

Кодирование текстовой информации в компьютерных устройствах сводится к тому, что каждому отдельному символу присваивается уникальное десятичное значение от 0 и до 255 или его эквивалент в двоичной форме от 00000000 и до 11111111. Люди могут различать символы по их внешнему виду, а компьютерное устройство только по их уникальному коду.

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

Кодирование текстовой информации и таблицы кодировок

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

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

Наиболее популярные таблицы кодировки:

• ASCII,
• MS-DOS,
• ISO,
• Windows,
• КОИ8,
• CP866,
• Mac,
• CP 1251,
• Unicode,
• и др.

Заключение

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

Читайте также:

  
• План местности урок видео
  
• Проект в детском саду цветная неделя
  
• Что такое здоровьесбережение детей в детском саду
  
• Как понравиться парню тельцу в школе
  
• Суфле из яиц как в детском саду