Кодирование по Фано 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

Программа на языке 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]; }

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

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

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

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); }

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

Некоторые сведения из модульной арифметики 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)

Шифрование с открытым ключом Выбираем два простых числа 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.

Доказательство корректности 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)

Пример кода Выберем 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,