Презентация по информатике на тему "Условие Фано"

Условие Фано

Кодирование

• представление информации в форме, удобной для ее хранения, обработки и передачи.

Например, речь кодируется текстом

передача

кодирование

обработка

данные (код)

данные (код)

11111100010

10101001010

передача

хранение

Код

• видоизмененное сообщение в виде набора знаков.

Кодовое слово

• набор символов, кодирующий один знак сообщения.

Двоичное кодирование

• кодирование с помощью двух знаков (0 и 1).

Например:

А – 1100000 – кодовое слово для «А»

Б – 1010101

В – 1100011

Код БВА: 101010111000111100000

Декодирование

- восстановление закодированного сообщения.

Декодируй сообщение: 1011000

10?

1 и 0?

А

О

0

С

1

Ф

10

100

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

- кодовые слова разной длины.

А

О

0

1

С

Ф

10

100

Однозначное декодирование

- условие, которое гарантирует, что любое закодированное сообщение можно расшифровать одним единственным образом.

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

Условие Фано

(префиксный код)

• кодовые слова одинаковой длины.

10011100 - СОФА

Ни одно кодовое слово не является началом другого кодового слова.

А

00

О

С

01

Ф

10

11

Удовлетворяет ли Условию Фано?

А

000

О

10

С

Ф

01

110

А

О

0 0 0

С

1 0

0 1

Ф

1 1 0

Дерево вариантов

Задача на построение кода

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

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

1) 00 2) 01 3) 11 4) 010

А

Б

1

000

В

001

Г

?

Решение :

• для букв А-Б-В выполнятся условие Фано
• при Г=00 условие Фано нарушится (пары Г-Б, Г-В)

• при Г=01 условие Фано выполняется

• при Г=11 условие Фано нарушится (пара А-Г)
• при Г=010 условие Фано выполняется (но длиннее 01)