Задача декодирования линейных кодов и некоторые применения помехоустойчивого кодирования

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

Общая схема передачи m – информационный вектор a=(a 1,…, a n ) – кодовое слово e=(e 1,…, e n ) – вектор ошибки b=(b 1,…, b n ) – принятое слово кодирование (m)=mG G – порождающая матрица кода декодирование (b)=a a – декодированный вариант принятого слова m k a n e b=a+e a n m n

Коды, исправляющие ошибки Параметры кода: n –длина кода R=k /n – скорость кода минимальное расстояние кода Задача кодирования Параметры декодирования Вероятность ошибки Сложность декодирования Задача декодирования

Методы декодирования кодов, исправляющих ошибки По минимуму расстояния В шаре радиуса

Сравнение методов декодирования Декодирование по максимуму правдоподобия Декодирование по минимуму расстояния в симметричном канале без памяти Декодирование в сфере радиуса R покрытия в симметричном канале без памяти

Комбинаторное декодирование Декодирование по информационным совокупностям как задача построения (n, r, )-покрытия ошибки Задача: Построение (n, r, )-покрытия такого, что для любого -множества ошибок I( ) существует, у которого

Обобщение декодирования по информационным совокупностям (и.с.) I Декодирующие совокупности ошибок Задача: Построение -покрытия такого, что для любого -множества ошибок I( ) существует, у которого

Обобщение декодирования по информационным совокупностям (и.с.) II Декодирование с использованием укорочений Задача: Построение -покрытия Сложность декодирования:

Обобщение декодирования по информационным совокупностям (и.с.) III Декодирование с использованием надкодов - слово кода - принятое слово - слово кода Результирующий список Сложность декодирования

Сложность алгоритмов декодирования Декодирование по минимуму расстояния Декодирование на основе покрытий Декодирование на основе укорочений Декодирование в надкодах

Параметры комбинаторных декодеров кодов (24,12) и (48,24) Алгоритм декодированияКод (24,12)Код (48,24) ПамятьЧисло операций с векторами длины 24 ПамятьЧисло операций с векторами длины 48 По информационным совокупностям 1К40010К5000 Комбинированное по информационным совокупностям 0,1К1202К4500 На основе укорочений0,5К508К3000 Декодирование в надкодах0,5К502К2000

Алгебраическое декодирование Дано: 2t -вектор S над GF(q) Проверочная матрица Найти:

Кодирование на транспортном уровне сети передачи данных Внешний трафик сети Внутренний трафик сети Пропускная способность сети Среднее время обслуживания пакета Средняя задержка сети Загрузка сети

Условия выгодности кодирования Без кодирования С кодированием Задержка пакетов Задержка сообщения Средняя задержка Условие выгодности кодирования Для экспоненциального распределения задержки пакетов

Кодирование P 1 P 2 P k В сеть Элементы поля GF(q) кодирование P 1 P 2 P k P k+1 U 1 U N 1 2 k k+1 k+2 N В сеть Избыточные символы Загрузка Задержка пакета Процедура сборки сообщения k пакетов из k отправленных k пакетов из n отправленных

Применение в Интернет- телефонии Звуковые данные Систематическое кодирование Избыточная информация Ненадежная сеть Декодирование Восстановленные данные

Пример приложения Драйвер DSP TrueSpeech сжатие данных Вычисление избыточной информации UDP Сеть или эмулятор UDP Приемный буфер Восстановление утерянных данных Декомпрессия аудиоданных Драйвер

Достигнутые результаты Повышение качества звука Снижение задержки Адаптивное управление параметрами кодирования Идут исследования

Бесприоритетная передача приоритетных сообщений Высокоприоритетное сообщение Низкоприоритетное сообщение Кодирование (R 1 ) Кодирование (R 2 ) сеть R 1 < R 2 Основные данные Малозначимые данные Фон Передача изображений Сжатие r 0 Сжатие r 1 Сжатие r 2 Избыточность R 0 Избыточность R 1 Избыточность R 2

Сжатие на основе помехоустойчивого кодирования Покрытие пространства в метрике Сжатие: 5-6 раз Покрытие множества доменов Сжатие: ?

Защита информации в открытых сетях A f,f -1 B f,f -1 Нелегальный пользователь Традиционная задача защиты Простые задачи Функция с закрытыми дверями: Защита в открытых сетях Простая задача AiAi AjAj Сложная задача

Системы публичных ключей АбонентыПубличные ключиСекретные ключи A1A1 ANAN f 1 (.) f N (.) f 1 -1 (.,k 1 ) f N -1 (.,k N ) сообщение Случайный вектор веса t Публичный ключ Система Мак-Элиса Шифрование: y=xK+e, K=MGP Дешифрование: Задача нелегального пользователя:

Система публичных ключей на основе полного декодирования Публичные ключи Способ шифрования Секретные ключи Способ дешифрования Задача нелегального пользователя: декодирование в G вектора из E Задание множества E

Параметры кодовых криптосистем Система публичных ключей на базе полного декодирования Код (256,128), t=8 M, M 2 – (256×256) - двоичные матрицы длина публичных ключей КБ рабочий фактор длина секретных ключей КБ Система Макэлиса Код (1024,524), t=50 длина публичного ключа - 66 КБ рабочий фактор длина секретных ключей КБ

Сравнение с известными криптосистмами ПараметрRSAМак-Элиса Сложность вскрытия Совпадает Скорость шифрования ПревосходитСовпадает Скорость дешифрования ПревосходитСовпадает Длина секретных ключей совпадаетСовпадает Длина публичных ключей ДлиннееКороче

Электронная подпись Публичные ключи: H – проверочная матрица (n,k) кода A t – расстояние кода A F() – нелинейная необратимая функция Секретные ключи – процедура декодирования кода A сообщениеподпись uz F 1 (u) = F 2 (z) ? Множество сообщений u Множество допустимых синдромов S F(u) Процедура подписывания (u,z=e) – подписанное сообщение Процедура проверки Параметры подписи: код (1024,424), t=50 F(u) на основе DES Сложность подделки Длина публичного ключа – 66кБ Длина секретного ключа – 2-4кБ

Сравнение с иными алгоритмами подписи ПараметрRSAЭль- Гамаля ХинмеяАлбади- Виккера Сложность подделки совпадаетСовпадаетПревосходит Скорость шифрования ПревосходитСовпадает Скорость дешифрования Превосходит Совпадает Длина секретных ключей Длиннее Совпадает Длина публичных ключей Длиннее Совпадает