Задание 8

• Кодирование — это представление информации в форме, удобной для её хранения, передачи и обработки. Правило преобразования информации к такому представлению называется кодом.
• 1 бит – это количество информации, которое можно передать с помощью одного знака в двоичном коде (0 или 1).
Единицы измерения:
1 байт (bytе) = 8 бит
1 Кб (килобайт) = 1024 байта
1 Мб (мегабайт) = 1024 Кб
1 Гб (гигабайт) = 1024 Мб
1 Тб (терабайт) = 1024 Гб
1 Пб (петабайт) = 1024 Тб


8 = 23
1024 = 210


Рассмотрим еще несколько определений:

• Алфавит — это набор знаков, используемый в том или ином языке.
• Мощность алфавита — это количество используемых в алфавите знаков.



Мощность алфавита

• Сообщение — это любая последовательность символов какого-либо алфавита.

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

Двоичное кодирование сообщений (равновероятностные события)

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

N = 2L

N — количество сообщений

L — длиной битов

 

* следует иметь в виду, что также приняты следующие обозначения: Q = 2k

Пример 2: Зашифруем буквы А, Б, В, Г при помощи двоичного кодирования равномерным кодом и посчитаем количество возможных сообщений:

Таким образом, мы получили равномерный код, т.к. длина каждого кодового слова одинакова для всех кодовых слов (L = 2).

Количество сообщений длиной L битов:

N = 2L

Т.е. количество сообщений длиной 2 бита, как в примере с нашими буквами, будет равно N = 22 = 4

Ответ: 4

Количество различных сообщений в алфавите разной мощности

Рассмотрим вариант с 5 буквами (мощность алфавита = 5), которые надо разместить в сообщении длиной 2 символа:

Найдем формулу для нахождения количества различных сообщений в алфавите различной мощности:

Если мощность некоторого алфавита составляет N, то количество различных сообщений длиной L знаков:

• N – мощность алфавита
• L – длина сообщения
• Q – количество различных сообщений

Пример: Сколько существует всевозможных трехбуквенных слов в английском языке?

В английском алфавите 26 букв. Значит, мощность алфавита = 26. Длина сообщения = 3. Найдем по формуле количество трехбуквенных слов:
Q = 263
или
26 * 26 * 26 = 17576

Ответ: 17576

Таким, образом, если слово состоит из L букв, причем есть n1 вариантов выбора первой буквы, n2 вариантов выбора второй буквы и т.д., то число возможных слов вычисляется как произведение:

N = n1 * n2 * … * nL

Количество сообщений при различном вхождении (встречаемости) букв

В таком случае можно использовать формулу для вычисления числа перестановок с повторениями; для двух разных символов она выглядит так:

P=na+n∗!na!n∗!

na – количество букв a

n* — количество звёздочек или кол-во вариантов

  
Иногда в заданиях 8 можно использовать формулу комбинаторики для проверки полученных результатов перебора. Число сочетаний из n элементов по k элементов:

C(kn)=n!k!(n−k)!

I – количество информации в битах

N – количество вариантов

 

Факториал числа n:

n! = 1 * 2 * 3 * … * n

Пример: Сколько существует всевозможных четырехбуквенных слов в алфавите из 4 букв: А, Б, В, Г, если известно, что буква А встречается ровно два раза?

Длина сообщения = 4. Мощность алфавита = 4. Но мешает условие: буква А встречается ровно два раза.

• В таких заданиях можно использовать способ перебора всевозможных вариантов:

два раза буква А, на остальных местах - одна из трех оставшихся букв:
А А 3 3     = 3 * 3 = 32 = 9
А 3 А 3     = 9
А 3 3 А     = 9 
3 А А 3     = 9
3 А 3 А     = 9
3 3 А А     = 9
  

• Получили 6 вариантов, каждый из которых равен 9.
• Проверим формулой числа сочетаний:

Число сочетаний из n элементов по k элементов:

C(kn)=n!k!(n−k)!
• В задаче:
C(24)=4!2!(4−2)!=242∗2=6
* Факториал числа n! = 1 * 2 * 3 *..* n
• Т.е. проверка прошла успешно, мы получили 6 вариантов.
• Осталось посчитать количество всех сообщений:

6 * 9 = 54