Условие фано информатика. Решение задач на тему "кодирование и декодирование информации"

Задание №5

При выполнении данного задания необходимо знать условие Фано, Код Хаффмана

В чем смысл прямого условия Фано?

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

Сформулировать данное условие можно следующим образом: « ни одно кодовое слово не может выступать в качестве начала любого другого кодового слова ».

С математической точки зрения условие можно сформулировать следующим образом: « если код содержит слово B, то для любой непустой строки C слова BC не существует в коде ».

В чем смысл обратного условия Фано?

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

С математической точки зрения обратное условие можно сформулировать следующим образом: « если код содержит слово B, то для любой непустой строки C слова CB не существует в коде ».

Условие задачи: дана последовательность, которая состоит из букв «A», «B», «C», «D» и «E». Для кодирования приведенной последовательности применяется неравномерный двоичный код, при помощи которого можно осуществить однозначное декодирование.

Буква

Двоичный эквивалент

010

011

101

111

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

Номер варианта

Ответ

B – 01

Не представляется возможным

C – 01

D – 01

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

Вариант 1. Код: A - 00, B - 01, C - 011, D - 101, и E - 111. Прямое условие Фано не выполняется: код символа «B» совпадает с началом кода символа «C». Обратное правило Фано не выполняется: код символа «B» совпадает с окончанием кода символа «D». Вариант не является подходящим.

Вариант 3. Код: A - 00, B - 010, C - 01, D - 101, и E - 111. Прямое условие Фано не выполняется: код символа «C» совпадает с началом кода символа «B». Обратное условие также не выполняется: код символа «C» совпадает с окончанием кода символа «D». Вариант не является подходящим.

Вариант 4. Код: A - 00, B - 010, C - 011, D - 01, и E - 111. Прямое условие Фано не выполняется: код символа «D» совпадает с началом кода символов «B» и «C». Однако наблюдается выполнение обратного правила Фано: код символа «D» не совпадает с окончанием кода всех остальных символов. По этой причине, вариант является подходящим.

После проверки вариантов решения задачи на соответствие прямому и обратному условию Фано , было установлено, что правильным является вариант 4.

Ответ : 4

Код Хаффмана

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

1. Для кодирования букв О, В, Д, П, А решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Если закодировать последовательность букв ВОДОПАД таким способом и результат записать восьмеричным кодом, то получится

1) 22162

2) 1020342

3) 2131453

4) 34017

Пояснение.

Сначала следует представить данные в условии числа в двоичном коде:

100

Затем закодировать последовательность букв: ВОДОПАД - 010010001110010. Теперь разобьём это представление на тройки справа налево и переведём полученный набор чисел в десятичный код, затем в восьмеричный (восьмеричное предствление совпадает с десятичным при разбиении тройками)

010 010 001 110 010 - 22162.

2. Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и Г, используется посимвольное кодирование: А-00, Б-11, В-010, Г-011. Через канал связи передаётся сообщение: ВБГАГВ. Закодируйте сообщение данным кодом. Полученное двоичное число переведите в шестнадцатеричный вид.

1) CBDADC

2) 511110

3) 5В1А

4) А1В5

Пояснение.

Закодируем последовательность букв: ВБГАГВ - 0101101100011010. Теперь разобьём это представление на четвёрки справа налево и переведём полученный набор чисел сначала в десятичный код, затем в шестнадцатеричный:

0101 1011 0001 1010 - 5 11 1 10 - 5В1А.

Правильный ответ указан под номером 3

3. Для кодирования сообщения, состоящего только из букв А, Б, В и Г, используется неравномерный по длине двоичный код:

010

011

Если таким способом закодировать последовательность символов ВГАГБВ и записать резуль получится:

1) CDADBC

2) A7C4

3) 412710

4) 4С7А

Пояснение.

Закодируем последовательность букв: ВГАГБВ - 0100110001111010. Теперь разобьём это представление на четвёрки справа налево и переведём полученный набор чисел сначала в десятичный код, затем в шестнадцатеричный:

0100 1100 0111 1010 - 4 12 7 10 - 4С7А.

Правильный ответ указан под номером 4.

4. Черно-белое растровое изображение кодируется построчно, начиная с левого верхнего угла и заканчивая в правом нижнем углу. При кодировании 1 обозначает черный цвет, а 0 – белый.

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

1) 57414

2) 53414

3) 53412

4) 53012

Пояснение.

Код первой строки: 10101.

Код второй строки: 11000.

Код третьей строки: 01010.

Запишем коды по порядку в одну строку: 101011100001010. Теперь разобьём это представление на тройки справа налево и переведём полученный набор чисел в десятичный код (восьмеричное представление совпадает с десятичным при разбиении тройками).

101 011 100 001 010 - 53412.

5. Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв - из двух бит, для некоторых - из трех). Эти коды представлены в таблице:

000

110

001

Определите, какой набор букв закодирован двоичной строкой 1100000100110

1) baade

2) badde

3) bacde

4) bacdb

Пояснение.

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

Разобьём код слева направо по данным таблицы и переведём его в буквы:

110 000 01 001 10 - b a c d e.

Правильный ответ указан под номером 3.

6. Для передачи чисел по каналу с помехами используется код проверки четности. Каждая его цифра записывается в двоичном представлении, с добавлением ведущих нулей до длины 4, и к получившейся последовательности дописывается сумма её элементов по модулю 2 (например, если передаём 23, то получим последовательность 0010100110). Определите, какое число передавалось по каналу в виде 01100010100100100110?

1) 6543

2) 62926

3) 62612

4) 3456

Пояснение.

Из примера видно, что 2 знака кодируются 10 двоичными разрядами (битами), на каждую цифру отводится 5 бит. В условии сказано, что каждая цифра записывается кодом длиной 4 знака, значит, пятую цифру можно откинуть.

Разобьём двоичную запись на группы по 5 знаков: 01100 01010 01001 00110. Отбрасываем послеюднюю цифру в каждой пятёрке и переводим в десятичную запись:

0110 0101 0100 0011 - 6 5 4 3.

Правильный ответ указан под номером 1.

7. По каналу связи передаются сообщения, содержащие только 4 буквы - П, О, Р, Т. Для кодирования букв используются 5-битовые кодовые слова:

П - 11111, О - 11000, Р - 00100, Т - 00011.

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

Это свойство важно для расшифровки сообщений при наличии помех (в предположении, что передаваемые биты могут искажаться, но не пропадают). Закодированное сообщение считается принятым корректно, если его длина кратна 5 и каждая пятёрка отличается от некоторого кодового слова не более чем в одной позиции; при этом считается, что пятёрка кодирует соответствующую букву. Например, если принята пятерка 00000, то считается, что передавалась буква Р.

Среди приведённых ниже сообщений найдите то, которое принято корректно, и укажите его расшифровку (пробелы несущественны).

11011 11100 00011 11000 01110

00111 11100 11110 11000 00000

1) ПОТОП

2) РОТОР

3) ТОПОР

4) ни одно из сообщений не принято корректно

Пояснение.

Длина обоих сообщений кратна пяти.

Анализируя первое сообщение "11011 11100 00011 11000 01110", приходим к выводу, что оно принято некорректно, поскольку нет такого слова, которое бы отличалось от слова "01110" только в одной позиции.

Рассмотрим второе сообщение. Учитывая, что каждая пятёрка отличается от некоторого кодового слова не более чем в одной позиции, его возможно расшифровать только как "ТОПОР".

8. Для передачи данных по каналу связи используется 5-битовый код. Сообщение содержит только буквы А, Б и В, которые кодируются следующими кодовыми словами:

А - 10010, Б - 11111, В - 00101.

При передаче возможны помехи. Однако некоторые ошибки можно попытаться исправить. Любые два из этих трёх кодовых слов отличаются друг от друга не менее чем в трёх позициях. Поэтому если при передаче слова произошла ошибка не более чем в одной позиции, то можно сделать обоснованное предположение о том, какая буква передавалась. (Говорят, что «код исправляет одну ошибку».) Например, если получено кодовое слово 00100, считается, что передавалась буква В. (Отличие от кодового слова для Б только в одной позиции, для остальных кодовых слов отличий больше.) Если принятое кодовое слово отличается от кодовых слов для букв А, Б, В более чем в одной позиции, то считается, что произошла ошибка (она обозначается "х").

Получено сообщение 10000 10101 11001 10111. Декодируйте это сообщение - выберите правильный вариант.

1) АВББ

2) хххх

3) АВхБ

4) АххБ

Пояснение.

Декодируем каждое слово сообщения. Первое слово: 10000 отличается от буквы А только одной позицией. Второе слово: 10101 отличается от буквы В только одной позицией. Третье слово: 11001 отличается от любой буквы более чем в одной позиции. Четвёртое слово: 10111 отличается от буквы Б только одной позицией.

Ответ: АВхБ.

9. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В и Г использовали такие кодовые слова: А - 111, Б - 110, В - 101, Г - 100.

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

1) 1

2) 0

3) 01

4) 10

Пояснение.

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

1) Д=1: код буквы Д является началом всех представленных кодов букв, поэтому этот вариант не подходит.

2) Д=0: код буквы Д не является началом другого кода, поэтому этот вариант подходит.

3) Д=01: код буквы Д не является началом другого кода, поэтому этот вариант подходит.

4) Д=10: код буквы Д является началом кодов букв В и Г, следовательно, этот вариант не подходит.

Таким образом, подходят два варианта: 0 и 01. 0 короче, чем 01.

10. По каналу связи передаются сообщения, содержащие только 4 буквы:

Е, Н, О, Т.

В любом сообщении больше всего букв О, следующая по частоте буква − Е, затем − Н. Буква Т встречается реже, чем любая другая.

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

1) Е−0, Н−1, O−00, Т−11

2) O−1, Н−0, Е−01,Т−10

3) Е−1, Н−01, O−001, Т−000

4) О−0, Н−11, Е−101, Т−100

Пояснение.

Выберем коды, для которых выполнено условие Фано. Это коды 3 и 4.

Чтобы сообщение было как можно короче, необходимо, чтобы чем чаще встречалась буква, тем короче был ее код.

Следовательно, ответ 4, поскольку буква О - самая часто встречающаяся буква и для ее кодирования в варианте 4 используется один символ.

11. Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0, для буквы К - кодовое слово 110. Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?

1) 7

2) 8

3) 9

4) 10

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

Пояснение.

Найдём для оставшихся двух символов наиболее короткое представление, удовлетворяющее условию Фано. Кодовое слово 1 использовать нельзя, так как тогда нарушится условие Фано. Из двузначных кодовых слов можно использовать слово 10, а слова 11 и 01 использовать нельзя. При таком построении кодов для четвёртого символа невозможно подобрать двухзначное кодовое слово. Поэтому используем трёхзначное слово, а именно - 111.

Таким образом, наименьшая возможная суммарная длина всех четырёх кодовых слов будет 1 + 3 + 2 + 3 = 9.

Правильный ответ указан под номером 3.

12. По каналу связи передаются сообщения, каждое из которых содержит 16 букв А, 8 букв Б, 4 буквы В и 4 буквы Г (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью. При выборе кода учитывались два требования:

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

б) общая длина закодированного сообщения должна быть как можно меньше.

Какой код из приведённых ниже следует выбрать для кодирования букв А, Б, В и Г?

1) А:0, Б:10, В:110, Г:111

2) А:0, Б:10, В:01, Г:11

3) А:1, Б:01, В:011, Г:001

4) А:00, Б:01, В:10, Г:11

Пояснение.

2 и 3 не подходят, так как в них встречаются пары кодов, один из которых является началом другого.

Длина сообщений при использовании первого кода будет равна .

Длина сообщений при использовании четвёртого кода будет равна .

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


На тестах для подготовки к ЕГЭ по информатике встречаются задачи на применение условия Фано. Материала в учебниках не нашел. Заходим в Википедию.

Условие Фано (англ. Fano condition, в честь Роберта Фано) - в теории кодирования необходимое условие построения самотерминирующегося кода (в другой терминологии, префиксного кода). Обычная формулировка этого условия выглядит так:

Никакое кодовое слово не может быть началом другого кодового слова.
Более «математическая» формулировка:

Если в код входит слово a, то для любой непустой строки b слова ab в коде не существует.

Алгоритм Шеннона - Фано - один из первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон и Роберт Фано. Данный метод сжатия имеет большое сходство с алгоритмом Хаффмана, который появился на несколько лет позже. Алгоритм использует коды переменной длины: часто встречающийся символ кодируется кодом меньшей длины, редко встречающийся - кодом большей длины. Коды Шеннона - Фано префиксные, то есть никакое кодовое слово не является префиксом любого другого. Это свойство позволяет однозначно декодировать любую последовательность кодовых слов.

Основные сведения
Кодирование Шеннона- Фано(англ. coding) - алгоритм префиксного неоднородного кодирования. Относится к вероятностным методам сжатия (точнее, методам контекстного моделирования нулевого порядка). Подобно алгоритму Хаффмана, алгоритм Шеннона - Фано использует избыточность сообщения, заключённую в неоднородном распределении частот символов его (первичного) алфавита, то есть заменяет коды более частых символов короткими двоичными последовательностями, а коды более редких символов - более длинными двоичными последовательностями.

Алгоритм был независимо друг от друга разработан Шенноном (публикация «Математическая теория связи», 1948 год) и, позже, Фано (опубликовано как технический отчёт).

1. Основные понятия
Закодировать текст – значит сопоставить ему другой текст. Кодирование применяется при передаче данных – для того, чтобы зашифровать текст от посторонних, чтобы сделать передачу данных более надежной, потому что канал передачи данных может передавать только ограниченный набор символов (например, - только два символа, 0 и 1) и по другим причинам.
При кодировании заранее определяют алфавит, в котором записаны исходные тексты (исходный алфавит) и алфавит, в котором записаны закодированные тексты (коды), этот алфавит называется кодовым алфавитом. В качестве кодового алфавита часто используют двоичный алфавит, состоящий из двух символов (битов) 0 и 1. Слова в двоичном алфавите иногда называют битовыми последовательностями.
2. Побуквенное кодирование
Наиболее простой способ кодирования – побуквенный. При побуквенном кодировании каждому символу из исходного алфавита сопоставляется кодовое слово – слово в кодовом алфавите. Иногда вместо «кодовое слово буквы» говорят просто «код буквы». При побуквенном кодировании текста коды всех символов записываются подряд, без разделителей.
Пример 1. Исходный алфавит – алфавит русских букв, строчные и прописные буквы не различаются. Размер алфавита – 33 символа.
Кодовый алфавит – алфавит десятичных цифр. Размер алфавита - 10 символов.
Применяется побуквенное кодирование по следующему правилу: буква кодируется ее номером в алфавите: код буквы А – 1; буквы Я – 33 и т.д.
Тогда код слова АББА – это 1221.
Внимание: Последовательность 1221 может означать не только АББА, но и КУ (К – 12-я буква в алфавите, а У – 21-я буква). Про такой код говорят, что он НЕ допускает однозначного декодирования
Пример 2. Исходный и кодовый алфавиты – те же, что в примере 1. Каждая буква также кодируется своим номером в алфавите, НО номер всегда записывается двумя цифрами: к записи однозначных чисел слева добавляется 0. Например, код А – 01, код Б – 02 и т.д.
В этом случае кодом текста АББА будет 01020201. И расшифровать этот код можно только одним способом. Для расшифровки достаточно разбить кодовый текст 01020201 на двойки: 01 02 02 01 и для каждой двойки определить соответствующую ей букву.
Такой способ кодирования называется равномерным. Равномерное кодирование всегда допускает однозначное декодирование.
Далее рассматривается только побуквенное кодирование
3. Неравномерное кодирование
Равномерное кодирование удобно для декодирования. Однако часто применяют и неравномерные коды, т.е. коды с различной длиной кодовых слов. Это полезно, когда в исходном тексте разные буквы встречаются с разной частотой. Тогда часто встречающиеся символы стоит кодировать более короткими словами, а редкие – более длинными. Из примера 1 видно, что (в отличие от равномерных кодов!) не все неравномерные коды допускают однозначное декодирование.
Есть простое условие, при выполнении которого неравномерный код допускает однозначное декодирование.
Код называется префиксным, если в нем нет ни одного кодового слова, которое было бы началом (по-научному, - префиксом) другого кодового слова.

Но я хочу продемонстрировать как можно автоматизировать данный процесс.
Видеоролик выложу в интернет
Приведу пример из подготовки к ЕГЭ по информатике (фирма 1С - материалы Центра Сертифицированного Обучения):
Для кодирования некоторой последовательности, состоящей из букв С, Т, Р, О, К и А, используется неравномерный двоичный код, удовлетворяющий условию Фано, и следовательно, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: С - 000, Т - 001, Р - 010, О - 100, К - 011, А - 11. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по прежнему удовлетворял условию Фано? Коды остальных букв меняться не должны.

Выберите правильный вариант ответа.

Варианты ответов:
1) для буквы Р - 01
2) для буквы О - 10
3) для буквы А - 1
4) это невозможно

Правильный вариант - 2
Решение:
Вариант 1) не подходит - условие Фано будет нарушено для букв Р и К
Вариант 2) подходит - слово 10 не является началом кодовых слов для других букв
Вариант 3) не подходит - условие Фано будет нарушено для букв А и О
Вариант 4) не подходит - см. вариант 2)

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

Вероятности:
0.01, 0.01, 0.01, 0.01, 0.01, 0.01

Значения:
C, T, P, O, K, A

Результат:
C 000
T 001
P 01
O 100
K 101
A 11

Из решения видно, вариантов решения может быть несколько, но все они отвечают условию Фано.

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

  • 3. Умножение вероятностей независимых совместных событий
  • 4. Нахождение среднего для значений случайных независимых величин
  • 5. Понятие условной вероятности
  • 6. Общая формула для вероятности произведения событий
  • 7. Общая формула для вероятности суммы событий
  • Лекция 3. Понятие энтропии
  • 1. Энтропия как мера неопределенности
  • 2. Свойства энтропии
  • 3. Условная энтропия
  • Лекция 4. Энтропия и информация
  • 1. Объемный подход к измерению количества информации
  • 2. Энтропийный подход к измерению количества информации
  • Лекция 5. Информация и алфавит
  • Лекция 6. Постановка задачи кодирования. Первая теорема Шеннона.
  • Лекция 7. Способы построения двоичных кодов. Алфавитное неравномерное двоичное кодирование сигналами равной длительности. Префиксные коды.
  • 1. Постановка задачи оптимизации неравномерного кодирования
  • 2. Неравномерный код с разделителем
  • 3. Коды без разделителя. Условие Фано
  • 4. Префиксный код Шеннона–Фано
  • 5. Префиксный код Хаффмана
  • Лекция 8. Способы построения двоичных кодов. Другие варианты
  • 1. Равномерное алфавитное двоичное кодирование. Байтовый код
  • 2. Международные системы байтового кодирования текстовых данных. Универсальная система кодирования текстовых данных
  • 3. Алфавитное кодирование с неравной длительностью элементарных сигналов. Код Морзе
  • 4. Блочное двоичное кодирование
  • 5. Кодирование графических данных
  • 6. Кодирование звуковой информации
  • Лекция 9. Системы счисления. Представление чисел в различных системах счисления. Часть 1
  • 1. Системы счисления
  • 2. Десятичная система счисления
  • 3. Двоичная система счисления
  • 4. 8- И 16-ричная системы счисления
  • 5. Смешанные системы счисления
  • 6. Понятие экономичности системы счисления
  • Лекция 10. Системы счисления. Представление чисел в различных системах счисления. Часть 2.
  • 1. Задача перевода числа из одной системы счисления в другую
  • 2. Перевод q  p целых чисел
  • 3. Перевод p  q целых чисел
  • 4. Перевод p  q дробных чисел
  • 6. Перевод чисел между 2-ичной, 8-ричной и 16-ричной системами счисления
  • Лекция 11. Кодирование чисел в компьютере и действия над ними
  • 1. Нормализованные числа
  • 2. Преобразование числа из естественной формы в нормализованную
  • 3. Преобразование нормализованных чисел
  • 4. Кодирование и обработка целых чисел без знака
  • 5. Кодирование и обработка целых чисел со знаком
  • 6. Кодирование и обработка вещественных чисел
  • Лекция 12. Передача информации в линии связи
  • 1. Общая схема передачи информации в линии связи
  • 2. Характеристики канала связи
  • 3. Влияние шумов на пропускную способность канала
  • Лекция 13. Обеспечение надежности передачи информации.
  • 1. Постановка задачи обеспечения надежности передачи
  • 2. Коды, обнаруживающие одиночную ошибку
  • 3. Коды, исправляющие одиночную ошибку
  • Лекция 14. Способы передачи информации в компьютерных линиях связи
  • 1. Параллельная передача данных
  • 2. Последовательная передача данных
  • 3. Связь компьютеров по телефонным линиям
  • Лекция 15. Классификация данных. Представление данных в памяти компьютера
  • 1. Классификация данных
  • 2. Представление элементарных данных в озу
  • Лекция 16. Классификация структур данных
  • 1. Классификация и примеры структур данных
  • 2. Понятие логической записи
  • Лекция 17. Организация структур данных в оперативной памяти и на внешних носителях
  • 1. Организация структур данных в озу
  • 2. Иерархия структур данных на внешних носителях
  • 3. Особенности устройств хранения информации
  • Контрольные вопросы
  • Список литературы
  • 3. Коды без разделителя. Условие Фано

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

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

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

    Например, если имеется код 110, то уже не могут использоваться коды 1, 11, 1101, 110101 и пр.

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

    Пример 1 . Являются ли коды, представленные втабл. 4,префиксными? Коды, представленные в табл. 4, не являются префиксными. См., например, коды букв «О» и «Е», «А» и «Н», «С» и «М», «Д» и «Ч».

    Пример 2 . Имеется таблица префиксных кодов (табл. 6). Требуется декодировать следующее сообщение, закодированное с использованием этой приведенной кодовой таблицы:

    00100010000111010101110000110

    Табл. 6. Таблица префиксных кодов

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

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

      сравнить текущее кодовое слово с кодовой таблицей; если совпадения нет, вернуться к пункту 1.

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

      Проверить, имеются ли еще знаки в закодированном сообщении; если да, то перейти к пункту 1.

    Применение данного алгоритма к предложенному выше закодированному сообщению дает:

    00100010000111010101110000110

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

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

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

    4. Префиксный код Шеннона–Фано

    Рассмотрим вариант кодирования, который был предложен в 1948 – 1949 гг. независимо К. Шенноном и Р. Фано.

    Рассмотрим схему кодирования (как она строится) Шеннона–Фано на следующем примере .

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

    Разделим знаки на две группы так, чтобы суммы вероятностей в каждой из этих двух групп были бы приблизительно равными. При этом в 1-ю группу попадут и, а остальные – во 2-ю группу. Знакампервой группы присвоим первый слева разряд их кодов «0», а первым слева разрядом кодов символов второй группы пусть будет «1».

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

    Вся эта процедура может быть схематически изображена в табл 7.

    Табл. 7. Построение кода Шеннона-Фано

    Знак

    Разряды кода

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

    Найдем среднюю длину полученного кода по формуле

    ,

    где – число разрядов (символов) в коде, соответсвующем символу.

    Из таблицы видно, что
    ,
    ,
    .

    Таким образом, получаем:

    Таким образом, для кодирования одного символа первичного алфавитапотребовалось в среднем 2.45 символов вторичного (двоичного) алфавита.

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

    .

    Найдем избыточность полученного двоичного кода:

    ,

    то есть избыточность – около 2.5.

    Выясним, является ли полученный код оптимальным. Нулей в полученных кодах – 6 штук, а единиц – 11 штук. Таким образом, вероятности появления 0 и 1 далеко не одинаковы. Следовательно, полученный код нельзя считать оптимальным.

    Задание 31. Неравномерные коды. Условие Фано

      5-54.Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В и Г использовали такие кодовые слова: А - 001, Б - 010, В - 000, Г - 011.

    Укажите, каким кодовым словом из перечисленных ниже может быть закодирована буква Д.

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

    1) 00 2) 01 3) 0000 4) 101

      5-85. Для кодирования некоторой последовательности, состоящей из букв У, Ч, Е, Н, И и К, используется неравномерный двоичный префиксный код. Вот этот код: У – 000, Ч – 001, Е – 010, Н – 100, И – 011, К – 11. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему остался префиксным? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.

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

    1) кодовое слово для буквы Е можно сократить до 01

    2) кодовое слово для буквы К можно сократить до 1

    3) кодовое слово для буквы Н можно сократить до 10

    4) это невозможно

      5-94. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 1, для буквы Б – кодовое слово 011. Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?

      5-74. По каналу связи передаются сообщения, содержащие только 4 буквы: E, Н, О, Т. В любом сообщении больше всего букв О, следующая по частоте буква – Е, затем – Н. Буква Т встречается реже, чем любая другая. Для передачи сообщений нужно использовать неравномерный двоичный код, допускающий однозначное декодирование; при этом сообщения должны быть как можно короче. Шифровальщик может использовать один из перечисленных ниже кодов. Какой код ему следует выбрать?

    1) Е – 0, Н – 1, О – 00, Т – 11 2) О – 1, Н – 0, Е – 01, Т – 10

    3) Е – 1, Н – 01, О – 001, Т – 000 4) О – 0, Н – 10, Е – 111, Т – 110

      5-105. По каналу связи передаются сообщения, каждое из которых содержит 15 букв А, 10 букв Б, 6 букв В и 4 буквы Г (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью. При выборе кода учитывались два требования:

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

    б) общая длина закодированного сообщения должна быть как можно меньше.

    Какой код из приведённых ниже следует выбрать для кодирования букв А, Б, В и Г?

    1) А:1, Б:01, В:001, Г:111

    2) А:1, Б:01, В:10, Г:111

    3) А:00, Б:01, В:10, Г:11

    4) А:100, Б:101, В:11, Г:0

      5-102. В сообщении встречается 10 разных букв. При его передаче использован неравномерный двоичный префиксный код. Известны коды трех букв: 11, 100, 101. Коды остальных семи букв имеют одинаковую длину. Какова минимальная суммарная длина всех 10-ти кодовых слов?

      5-104. В сообщении встречается 50 букв А, 30 букв Б, 20 букв В и 5 букв Г. При его передаче использован неравномерный двоичный префиксный код, который позволил получить минимальную длину закодированного сообщения. Какова она в битах?

      По каналу связи передаются сообщения, содержащие только пять букв: A, B, С, D, E. Для передачи используется двоичный код, допускающий однозначное декодирование. Для буквA, B, C используются такие кодовые слова: A – 111, B – 0, C – 100.

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

      9-1-23. После преобразования растрового 256-цветного графического файла в 16-цветный формат его размер уменьшился на 15 Кбайт. Каков был размер исходного файла в Кбайтах?

      9-1-25. После преобразования растрового графического файла его объем уменьшился в 1,5 раза. Сколько цветов было в палитре первоначально, если после преобразования было получено растровое изображение того же разрешения в 16-цветной палитре?

      13-37. При регистрации в компьютерной системе каждому пользователю выдаётся идентификатор, состоящий из 8 символов, первый и последний из которых – одна из 18 букв, а остальные – цифры (допускается использование 10 десятичных цифр). Каждый такой идентификатор в компьютерной программе записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование; все цифры кодируются одинаковым и минимально возможным количеством бит, все буквы также кодируются одинаковым и минимально возможным количеством бит). Определите объём памяти в байтах, отводимый этой программой для записи 500 паролей.

      13-38. При регистрации в компьютерной системе, используемой при проведении командной олимпиады, каждому ученику выдается уникальный идентификатор – целое число от 1 до 1000. Для хранения каждого идентификатора используется одинаковое и минимально возможное количество бит. Идентификатор команды состоит из последовательно записанных идентификаторов учеников и 8 дополнительных бит. Для записи каждого идентификатора команды система использует одинаковое и минимально возможное количество байт. Во всех командах равное количество участников. Сколько участников в каждой команде, если для хранения идентификаторов 20 команд-участниц потребовалось 180 байт?

      13-50. При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 15 символов и содержащий только символы из 12-символьного набора: А, В, C, D, Е, F, G, H, K, L, M, N. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт; это число одно и то же для всех пользователей. Для хранения сведений о 20 пользователях потребовалось 300 байт. Сколько байт выделено для хранения дополнительных сведений об одном пользователе? В ответе запишите только целое число – количество байт.

      16-165. Значение арифметического выражения: 9 22 + 3 66 – 18 записали в системе счисления с основанием 3. Сколько цифр «2» содержится в этой записи?



    Есть вопросы?

    Сообщить об опечатке

    Текст, который будет отправлен нашим редакторам: