Кодирование по Фано defghijk 1110754431 a 20 cb 1817 0 55 de 1110 f 7 ghijk 54431 1 45 a 20 00 bc 1817 01 35 de 1110 21 f 7 ghijk 54431 11 24 a 00 b 010. - презентация

1 Кодирование по Фано defghijk a 20 cb de 1110 f 7 ghijk a bc de f 7 ghijk a 00 b 010 c 011 d 100 e 101 f 1100 g 1101 h i j k abc

2 Программа на языке Java public class Code { public long code; // Собственно код символа public byte len; // Длина кода // Символы (в порядке убывания вероятностей появления) public static char[] chars = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k'}; // Вероятности появления символов public static int[] probs = { 20, 18, 17, 11, 10, 7, 5, 4, 4, 3, 1 }; // Формируемый массив кодов public static Code[] codes = new Code[chars.length]; }

3 public class Fano { private static int mediana(int low, int high) { int sLow = 0; // Сумма первых элементов int sHigh = Code.probs[high]; // Сумма последних элементов for (int i = low; i < high; i++) { sLow += Code.probs[i]; } int m = high; // Перед поиском границы sLow = sum[low:(high-1)], sHigh = sum[high] int diff; do { m--; diff = Math.abs(sLow - sHigh); // Вычисляем предыдущую разность // Изменяем верхнюю и нижнюю суммы sLow -= Code.probs[m]; sHigh += Code.probs[m]; } while (Math.abs(sLow - sHigh) < diff); // Цикл заканчивается, когда разности перестанут уменьшаться return m; } public static void fano(int low, int high) { if (low < high) { // Определяем границу равных сумм вероятностей int m = mediana(low, high); for (int i = low; i

4 k 1 j 3 i 4 h 4 g 5 f 7 e 10 d 11 c 17 b 18 Кодирование по Хаффмену a 20 jk 4 i 4 h 4 g 5 f 7 e 10 d 11 c 17 b 18 a 20 h 4 g 5 f 7 ijk 8 e 10 d 11 c 17 b 18 a 20 gh 9 f 7 ijk 8 e 10 d 11 c 17 b 18 a 20 fijk 15 gh 9 e 10 d 11 c 17 b 18 a 20 egh 19 fijk 15 d 11 c 17 b 18 a 20 egh 19 c 17 b 18 a 20 dfijk 26 egh 19 a 20 dfijk 26 bc 35 dfijk 26 bc 35 aegh 39 aegh 39 bcdfijk 61

5 1aegh 0bcdfijk 01dfijk 00bc11egh 10a 001c 000b 010fijk011d 111gh 0101f 0100ijk 110e 01000jk 01000i 1111h1110g k010000j

6 public class Huffman { // Рабочая копия массива вероятностей static int[] prs = new int[Code.probs.length]; private static int up(int n, int p) { int j = n-1; // Поиск начинаем с конца таблицы while (j >= 1) { if (prs[j-1] < p) { // Сдвиг по таблице prs[j] = prs[j-1]; j--; } else { // Место в таблице найдено break; } // Вставка значения в таблицу и возврат prs[j] = p; return j; } public static void huffman(int n) { if (n == 2) { // Предельный случай - два символа в таблице Code.codes[0] = new Code((long)0, (byte)1); Code.codes[1] = new Code((long)1, (byte)1); } else { // Просуммируем две наименьшие вероятности и вставим в табицу на свое место int j = up(n, prs[n-2] + prs[n-1]); // Рекурсивный вызов алгоритма для уменьшенной таблицы huffman(n-1); // Приписывание кодов согласно сохраненному значению j down(n, j); }

7 private static void down(int n, int j) { Code c = new Code(Code.codes[j]); // Запомнили код for (int i = j; i < n-2; i++) { // Сдвигаем коды вниз по таблице Code.codes[i].assign(Code.codes[i+1]); } // Восстанавливаем два последних кода c.len++; c.code

8 Некоторые сведения из модульной арифметики a b (mod n) a mod n = b mod n Операции «по модулю n»: a + n b (a + b) mod n a * n b (a * b) mod n Малая теорема Ферма: 0 < a < p a p-1 1 (mod p) Следствие из «китайской теоремы об остатках»: n = p*q и x y (mod n) x y (mod p) и x y (mod q)

9 Шифрование с открытым ключом Выбираем два простых числа p и q; Вычисляем n = p*q; Выбираем нечетное e, взаимно простое с (p-1)(q-1); Вычисляем d = e –1 mod (p-1)(q-1); Открытый ключ – пара ; Закрытый ключ – пара. Исходное сообщение: S = S 0 S 1 …S k, Шифрованное сообщение: C = C 0 C 1 …C k. Шифрование: C i = (S i ) e mod n; Расшифровка: P i = (C i ) d mod n. Утверждение: P i = S i.

10 Доказательство корректности P i = (S i ) ed mod n. Покажем, что при M < n M ed M mod n Это очевидно верно при M = 0 При M > 0 по малой теореме Ферма: M ed = M (M p-1 ) k(q-1), поскольку ed = 1 + k(p-1)(q-1); M ed M 1 k(q-1) M (mod p) Аналогично, M ed M (mod q), следовательно, M ed M (mod n)

11 Пример кода Выберем p = 3, q = 11. Тогда n = 33, (p-1)(q-1) = 20, Выберем e = 7, тогда d = 3 (ed = 21; 21 1 mod 20) Фрагменты сообщения могут быть не длиннее 5 бит. Пусть S 0 = 21, S 1 = 13, S 2 = 17 Тогда C 0 = 21 7 mod 33 = 21, C 1 = 13 7 mod 33 = 7, C 2 = 17 7 mod 33 = 8, Проверка (расшифровка): P 0 = 21 3 mod 33 = 21 = S 0, P 1 = 7 3 mod 33 = 13 = S 1, P 2 = 8 3 mod 33 = 17 = S 2,