Презентация на тему: Всё есть число. Пифа г ор

Всё есть число. Пифа г ор
Всё есть число. Пифа г ор
Всё есть число. Пифа г ор
Всё есть число. Пифа г ор
Всё есть число. Пифа г ор
ASCII
Всё есть число. Пифа г ор
У сл о ви е Фан о : ни к а к о е к о до в о е сло в о н е совпадает с началом другого кодового слова.
Всё есть число. Пифа г ор
Неравномерный код может быть однозначно декодирован, если никакой из кодов не совпадает с началом (префиксом) какого-либо другого, более длинного кода.
Всё есть число. Пифа г ор
Всё есть число. Пифа г ор
Всё есть число. Пифа г ор
Решение:
Решение:
Дл я к о диро в ания не к о т орой п о с л е до в а тель н о сти, с о с т о ящей
Всё есть число. Пифа г ор
Всё есть число. Пифа г ор
Всё есть число. Пифа г ор
Для трехбуквенного
Всё есть число. Пифа г ор
Всё есть число. Пифа г ор
Всё есть число. Пифа г ор
По каналу связи передаются сообщения, содержащие только 3 буквы: А, В, С. Для передачи используется двоичный код, допускающий однозначное декодирование. Для
Всё есть число. Пифа г ор
Всё есть число. Пифа г ор
Всё есть число. Пифа г ор
Всё есть число. Пифа г ор
1/28
Средняя оценка: 4.4/5 (всего оценок: 24)
Код скопирован в буфер обмена
Скачать (4670 Кб)
1

Первый слайд презентации: Всё есть число. Пифа г ор

Изображение слайда
2

Слайд 2

Изображение слайда
3

Слайд 3

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

Изображение слайда
4

Слайд 4

каждого текста лежит алфавит – конечное В основе мн о ж е ст в о алфавит, сим в о ло в. В о сно в е р у с с к о г о яз ы к а ле жит наз ы в ае м ый кирил л ицей, с о с т о ящий и з 33 строчных и 33 заглавных букв. В основе английского языка лежит латиница – алфавит, состоящий из 26 строчных и 26 заглавных букв. Пусть задан алфавит Т, содержащий m символов: С л о в о м S в Т={t 1, t 2, … t m } алфавите T называют любую последовательность символов алфавита: S =s 1 s 2 …s k, где s i - это символы алфавита. Число символов в слове – k называют длиной слова. Мощность алфавита – это количество символов в нем.

Изображение слайда
5

Слайд 5

При нажатии на клавиатурную клавишу компьютер получает сигнал в виде двоичного числа, р. асшифровку которого можно найти в кодовой таблице – внутреннем представлении знаков в ПК. Стандартом во всем мире считают таблицу ASCII. Для хранения одного символа двоичного кода электронно-вычислительная машина выделяет 1 байт, то есть 8 бит. Эта ячейка может принимать только два значения: 0 и 1. Получается, зашифро в а ть что один байт позволяет 256 разных си м в о лов, в е д ь именно такое количество комбинаций можно составить. Эти сочетания и являются ключевой частью таблицы ASCII.

Изображение слайда
6

Слайд 6: ASCII

. Половина таблицы стандартов ASCII содержит коды цифр, управляющих символов и латинских букв. Другая ее часть заполняется национальными знаками, псевдографическими знаками и символами, которые не имеют отношения к математике. Код ASCII, в котором каждый символ алфавита кодировался словом из 8 бит (одним байтом). В этом алфавите 2 8 =256 символов. Совершенно ясно, что в различных странах эта часть таблицы будет отличаться. Цифры при вводе также преобразовываются в двоичную систему вычисления согласно стандартной сводке. В двоичной системе счисления, которую активно используют компьютеры, встречаются лишь две цифры – 0 и 1. Д о л г о е в ре м я пр и раб о те с те к с т а м и, с о храняе м ы ми в к о мпь ю тере, исп о ль з у е т ся к о д ASCI I. Т а к ой а л фа ви т, содержащий 256 различных символов, мог включать латиницу и кирилл и ц у, цифры, знаки о п ераций, з н аки препинания, все-таки э т о г о с к обки и д р у ги е с им в о л ы. Но недостаточно, чтобы можно было храни т ь в а л фа ви т а па мяти компьютера тексты на любых естественных языках. С е г о дня д л я хр а не н и я те к с т ов исп о ль з у е т ся к о диров к а и з 2-х бай т о в, назы в аемая UNICODE к о диро в к ой, словами из 16 битов к о дир о в а ть а лф а в и т, позволяющая содержащий 2 16 =65536 символов. ASCII UNICODE

Изображение слайда
7

Слайд 7

Пример. Пусть у нас есть алфавит из 3-х символов – А, М, П. Введем следующую кодировку: А-0, М-1, П-10. Рассмотрим закодированный текст: 1010. Этому тексту соответствует два слова – МАМА и ПП. Как видите, введенная кодировка не обеспечивает однозначное кодирование. Если при кодирование выполняется условие Фано, то декодирование однозначно.

Изображение слайда
8

Слайд 8: У сл о ви е Фан о : ни к а к о е к о до в о е сло в о н е совпадает с началом другого кодового слова

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

Изображение слайда
9

Слайд 9

Изображение слайда
10

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

А В С 10 11 001 А В С 10 11 00 А В С 100 110 010 D: 00 недопустимо: C - 001 D – 00 Код D совпадает с началом кода С D: 11 недопустимо: В - 11 D – 11 Код D совпадает с кода В D: 00 допустимо: Прямое условие Фано выполнено.

Изображение слайда
11

Слайд 11

Неравномерный код может б ы ть о дно з н а чно де к о диро в ан, если никакой из кодов не совпадает с о к ончанием (постфиксом) какого-либо другого, более длинного кода. А В С 10 11 001 А В С 10 11 00 А В С 100 110 010 D: 01 н е доп у стимо: C - 001 D – 01 Код D совпадает с концом кода С D: 11 н е доп у стимо: В - 11 D – 11 Код D совпадает с кода В D: 01 допустимо: Обратное условие Фано выполнено.

Изображение слайда
12

Слайд 12

Для однозначности декодирования п о с л е д о в а тел ь н о сти кодов достаточно выполнения х о т я вышеуказанных условий Фано: - при выполнении прямого бы о дно г о и з д в у х у с л ов и я Фано п о сл е до в а т е льн о сть к о дов о д н озн а чно де к о ди р у е т ся с начала; - пр и вып о лнен и и обр а тно г о у с л овия Ф ано последовательность кодов однозначно декодируется с конца. Правило Фано – это достаточное, но необходимое условие однозначного декодирования.

Изображение слайда
13

Слайд 13

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0; для буквы Б – кодовое слово 10. Какова наименьшая возможная сумма длин всех шести кодовых слов? Это задание удобнее решать с помощью дерева: условие Фано выполняется тогда, когда все выбранные кодовые слова заканчиваются в листьях дерева. П о дс к аз к а

Изображение слайда
14

Слайд 14: Решение:

0 1 А 0 1 Б На оставшуюся свободную ветку нужно «повесить» 4 кодовых слова (для букв В, Г, Д, Е) 0 1 В 0 1 Г 0 1 Д Е суммарная длина кодовых слов будет в этом случае равна 1 + 2 + 3 + 4 + 2·5 = 20 (А-0, Б-10, В-110, Г-1110, Д-11110, Е-11111)

Изображение слайда
15

Слайд 15: Решение:

0 1 А 0 1 Б 0 1 0 1 В Г 0 1 Д Е суммарная длина кодовых слов будет в этом случае равна 1 + 2 + 4·4 = 19 (А-0, Б-10, В-1100, Г-1101, Д-1110, Е-1111) Ответ: 19

Изображение слайда
16

Слайд 16: Дл я к о диро в ания не к о т орой п о с л е до в а тель н о сти, с о с т о ящей

из букв А, Б, В, Г, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0, для буквы Б – кодовое слово 110. Какова наименьшая возможная суммарная длина всех четырёх кодовых слов? 0 А 1 0 1 0 1 Б В Г суммарная длина кодовых слов будет в этом случае равна 1 + 3 +2 + 3 = 9 (А-0, Б-110, В-10, Г-111) Ответ: 9

Изображение слайда
17

Слайд 17

Изображение слайда
18

Слайд 18

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

Изображение слайда
19

Слайд 19

При равномерном кодировании все символы кодируются кодами равной длины. При неравномерном кодировании разные символы могут кодироваться кодами разной длины, это затрудняет декодирование. Закодированное сообщение можно однозначно декодировать с начала, если выполняется условие Фано : ни к а к о е к о до в о е кодового слова; закодированное слово не является началом другого сообщение можно однозначно декодировать с конца, если выполняется обратное условие Фано : никакое кодовое слово не является окончанием другого кодового слова. Условие Фано – это достаточное, но не необходимое условие однозначного декодирования.

Изображение слайда
20

Слайд 20: Для трехбуквенного

алфавита {А, М, П} используется кодировка А-01, М-10, П-001. Какой код минимальной длины б у к в ы Т, доба в ляе м ой в с л е д у ет зад а ть для к о дировки алфавит? Решение: Для нового символа, добавляемого в алфавит, нельзя использовать код, состоящий из одного символа, так как будет нарушено условие Фано. Для кода, состоящего из двух символов, возможен только один вариант, удовлетворяющий условию Фано, Т-11. Ответ: 11

Изображение слайда
21

Слайд 21

Ответ: П-00 Для четырехбуквенного алфавита {А, М, П, Т} используется кодировка А-01, М-10, П-001, Т-11. Можно ли уменьшить длину кода одного из символов, сохраняя однозначность декодирования?

Изображение слайда
22

Слайд 22

По каналу связи передаются сообщения, содержащие только 4 буквы: А, В, С, D. Для передачи используется двоичный код, допускающий однозначное декодирование. Для букв используются такие кодовые слова: А-111, В-0, D-110. Укажите кратчайшее кодовое слово для буквы С, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением. Решение: Коды 1 и 0 являются началом кода данных букв. Коды 00 и 01 нельзя использовать, так как код буквы В является их началом. Следовательно, минимальный код для буквы C будет 10. Ответ: 10

Изображение слайда
23

Слайд 23

Ответ: D3A6 Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и Г, используется неравномерный (по длине) код: А-100, Б-111, B-110, Г-0. Через канал связи передаётся сообщение: ВАБГАВ. Закодируйте сообщение данным кодом. Полученную двоичную последовательность переведите в шестнадцатеричный вид. Решение: Закодируем сообщение ВАБГАВ – 1101001110100110. пере в е дем в П о л у ч е н н ую д в оич н у ю п о сл е д о в а тел ь н о сть шестнадцатеричный вид. 1 101 ӏ 00 1 1 ӏ 1010 ӏ 0 1 10 D 3 A 6

Изображение слайда
24

Слайд 24: По каналу связи передаются сообщения, содержащие только 3 буквы: А, В, С. Для передачи используется двоичный код, допускающий однозначное декодирование. Для букв А и В используются такие кодовые слова: А: 11, В: 0

Укажите кратчайшее кодовое слово для буквы С, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением. Решение: Коды 1 и 0 являются началом кода данных букв. Коды 00 и 01 нельзя использовать, так как код буквы В является их началом. Следовательно, минимальный код для буквы C будет 10. Ответ: 10

Изображение слайда
25

Слайд 25

Изображение слайда
26

Слайд 26

З адание 1. П о к ан а л у с в язи пер е да ю т ся сооб ще ния, с о д е ржащие т о л ь к о 4 б у к в ы : А, В, С, D ; для пер е д а чи ис п о ль з у е т ся д в оич н ый к о д, д о п у с к ающий однозначное Полученную За к о д и р у йт е сообщение данным к о д о м. двоичную последовательность пере в е дите в шестнадцатеричный вид. декодирование. Для букв А, В, D используются такие кодовые слова: А: 0, В: 10, D: 110. Укажите кратчайшее кодовое слово для буквы С, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением. Ответ: 111 З адание 2. Дл я пер е д а чи п о к ан а л у с в язи сообщения, с о с т о яще г о т о л ь к о и з сим в о ло в А, Б, В и Г, исп о ль з у е т ся не р авн о м е рный (по д лине ) к о д : А -00, Б- 1 1, В -100, Г-0 1 1. Че р е з к а н а л с в язи пер е д а ё т ся сообщени е : Г Б В АГВ. Ответ: 7С1С

Изображение слайда
27

Слайд 27

системе счисления. Задание 3. Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и Г, используется неравномерный (по длине) код: А-00, Б-11, В-010, Г-011. Через канал связи передаётся сообщение: ГБВАВГ. Закодируйте сообщение данным кодом. Полученную двоичную последовательность запишите в восьмеричной системе счисления. Ответ: 75023 Задание 4. Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и Г, используется неравномерный (по длине) код: А-111, Б-110, В-10, Г-0. Через канал связи передаётся сообщение: ВАБГАВ. Закодируйте сообщение данным кодом. Полученную двоичную последовательность запишите в восьмеричной Ответ: 27636

Изображение слайда
28

Последний слайд презентации: Всё есть число. Пифа г ор

По к ан а л у связи передаются сообщения, т о ль к о 3 б у к в ы : А, В, С ; для пер е д а чи Задание 5. содержащие ис п о ль з у е т ся двоичный код, допускающий однозначное декодирование. Для букв А и В используются такие кодовые с л о в а : А : 10, В : 0. У к ажи т е кр а т ч айшее к о до в о е сло в о для б у квы С, пр и к о т ор о м к о д б у д ет до п у с к а ть о дн о зн а чн о е декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением. Ответ: 11 Задание 6. По каналу связи передаются сообщения, с о д е ржа щ и е т о л ь к о 4 б у к в ы : А, В, С, D ; для пер е д а чи ис п о ль з у е т ся д в оич н ый к о д, д о п у с к ающий о дн о зн а чн о е декодирование. Для букв А, В, D используются такие кодовые слова: А: 111, В: 0, D: 100. Укажите кратчайшее кодовое слово для буквы С, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением. Ответ: 101

Изображение слайда