close

Вход

Забыли?

вход по аккаунту

?

Еквидистантни кодове и защита

код для вставкиСкачать
Еквидистантни кодове и
защита на данни с воден знак
Тодор Тодоров
Секция МОИ,
Институт по Математика и
информатика, БАН
Въведение
2
Защита на цифрова информация с воден
знак
Еквидистантни и еквидистантни
константно-тегловни кодове
Софтуерни приложения
Дефиниции
3
Стеганография – скриваното съобщение се вгражда в някакъв
“безобиден”, непривличащ вниманието обект
Покриващ обект – обектът, в който се вгражда скриваното
съобщение
Стего обект – покриващ обект с вградено съобщение
Петорката σ = <C,M,K,Dk,Ek>, където C, е множеството от
възможните покриващи обекти, M множеството от тайни съобщения,
като |C| ≥ |M|, K е множество от секретни ключове, Ek : C x M x K →
C вграждаща функция и Dk : C x K → M извличаща функция, със
следното свойство Dk(Ek(c,m, k), k) = m за всяко m є M и c є C и k є K,
се нарича стеганографска система с таен ключ.
Защита с воден знак (watermarking) – скрита комуникация,
притежаваща допълнителна устойчивост срещу опити да се
премахне вградената информация.
Дефиниции
4
Чиста (pure) стеганография, Стеганография с таен
ключ, Стеганография с публичен ключ
Приложения:
– доказване на авторски права върху дигитални
данни
– следенето на разпространението на данни с цел
събиране на данни от маркетингова гледна точка.
– добавяне на метаданни към архив
– подписване при опит за промяна на данните
Дефиниции
5
Система за вграждане на воден знак:
– Вход - водния знак, покриващия обект
незадължителен публичен или таен ключ
– Изход – данни, защитени с воден знак
Система за извличане на воден знак:
– Вход – данните, защитени с воден знак, таен или
публичен ключ, оригиналните данни и
оригиналния воден знак.
– Изход - извлечения воден знак или някаква мярка
за възможността водния знак, подаден на входа
да присъства в разглежданите данни
Изисквания към системите с воден знак:
6
Незабележимост
Излишество
Ключове
Устойчивост
Атаки
7
Промени в сигнала (промени в контраста, осветеността, цветови корекции, гама корекции)
Адитивен и мултипликативен шум (Гаусов, равномерен и др.)
Линейно филтриране (нискочестотно, високочестотно и др.)
Нелинейно филтриране
Компресия със загуби (JPEG, H.261, H.263, MPEG-2,MPEG-4, MP3,
MPEG-4, G.723)
Локални и глобални афинни трансформации (транслация, ротация,
мащабиране)
Отрязване на данни (отрязване, хистограмни модификации)
Смесване на данни (вмъкване на лого или кадър)
Транскодиране (H.263 - MPEG-2, GIF - JPEG)
Д/А и А/Д конвертиране
Множество водни знаци
Атака с колизии
Статистическо осредняване
Мозаечна атака
Фактори влияещи на устойчивостта
8
Количеството вградена информация
Устойчивостта на водния знак
Обема и естеството на данните
Секретната информация (ключове)
Оценка на системите за воден знак
Критерии:
9
SNR - отношението сигнал-шум (signal-to-noise
ratio)
PSNR - отношението пиков сигнал-шум (peak signalto-noise ratio)
Критерии адаптирани към човешката визуална
система
Нивото на битови грешки (bit-error rate).
Уеб базирани информационни
системи
10
Информационната система е система, която покрива основните
дейности свързани с информацията - съхранение, обработка и
разпространение на информацията.
Динамични технологии от страна на клиента – Java Applets,
ActiveX, Jscript DHTML
Динамични технологии от страна на сървъра – CGI, ASP,
ASP.NET, Java Servlets, JSP, PHP, ISAPI, NSAPI, SSJS
Задачи
11
Разработка на нови алгоритми и методи за защита
на данни с воден знак
Разработка на софтуерни приложения за защита на
данни с воден знак
Мотивация
12
Договор АРСИКТ–ИД-13/2005; Завършен и отчетен успешно на (07.2006г.); тема:
“Проектиране и изграждане на експериментален дигитален архив на автентични
фолклорни материали” към агенция “РАЗВИТИЕ НА СЪОБЩЕНИЯТА И НА
ИНФОРМАЦИОННИТЕ И КОМУНИКАЦИОННИТЕ ТЕХНОЛОГИИ” , Съвместен с
ВТУ "Св. Св. Кирил и Методий. Ръководител чл.кор. проф. дмн. Ст. Додунеков.
Проект за дигитализация на фолклорен архив на тема “МОДЕРНИЗИРАНЕ НА
АРХИВНИЯ ФОНД ОТ АВТЕНТИЧНИ ФОЛКЛОРНИ МАТЕРИАЛИ”; съвместен с
Институт за Фолклор към БАН; Продължен; Срок 2006-2007 г. Ръководител чл.кор. проф.
дмн. Ст. Додунеков.
Научноизследователският Проект “Създаване, анотиране и защита на дигитален
архив “Българско фолклорно наследство” (Договор ИО-03-02 /2006) , Фонд ”Научни
изследвания” при МОН, Национални научни програми “Информационно общество”.
Ръководител ст.н.с. II ст. д-р Г.Богданова
Проект BELL: “Проучване и паспортизация на уникални камбани от историческото
и културно наследство на България и създаване на аудио и видео архив с помощта на
съвременни технологии”, Договор КИН 1009/2006 към Фонд “Научни изследвания”,
Министерство на образованието и науката. Ръководител проф. Г. Димков.
Разглеждани обекти
13
Воден знак в пространствената област
Воден знак с разпростиращ се спектър
Схема за коригиране на грешки при защита с
воден знак
Софтуерни приложения
Основни методи
14
Метод за коригиране на грешки при защита с
воден знак
Методи за защита на изображения с воден знак
Методи за защита на текст с воден знак
Основни софтуерни приложения
15
Софтуер за защита на данни с воден знак
Мултимедиен архив от фолклорни обекти
Информационни системи използващи защитата с
воден знак
Защита на данни с воден знак
16
Воден знак в пространствената област - J.Brassil,
S.Low, N.Maxemchuk, L.O'Gorman, M.Kutter
Воден знак с разпростиращ се спектър - I.Cox, J.
Kilian, T. Leighton, G. Shamoon
Критерии за оценка на воден знак - L. van den
Branden, C.J., J.E.Farrell, M.Kutter, F.A.P.Petitcolas,
R.J.Anderson
Атаки срещу системи с воден знак - F.Hartug, .K.Su,
B.Girod, J.R.Hernandez, M.Kutter, F.A.P.Petitcolas,
M.G.Kuhn
Софтуер за защита на данни с воден
знак
17
Easy Watermark Creator - видим воден знак
YUVsoft Watermarking – подписване на видео
файлове, видим и невидим воден знак
WaterMark Master – редактиране и подписване,
видим и невидим воден знак
AiS Watermark Pictures Protector- видим воден
знак, над 40 файлови формата
Picture Watermark - видим воден знак
Софтуер за защита на данни с воден
знак
18
Комерсиални
Ограничена функционалност
Изисквания на проектите – специфична
функционалност. Единност със системите
Шумозащитно кодиране
Мултимедийни фолколорни архиви
19
Living Treasures, http://www.treasures.eubcc.bg/
Music Multimedia Archive,
http://musicart.imbm.bas.bg/en/about.htm
Fife Folklore Archives, http://library.usu.edu/Folklo/
Folklore Databases
http://www.eastern.edu/library/www/webindex/arts/folklore.sht
ml}.
The Folklore Program at the University of California, Berkeley,
http://ls.berkeley.edu/dept/folklore/
The Ukrainian Folklore Archives,
http://129.128.116.48:8890/photo_-archives/
The American Folklore Center,
http://www.loc.gov/folklife/index.html
Дефиниции
20
(n, M, d )q-код е код с дължина n, съдържащ M кодови думи,
имащ минимално разстояние d над азбука с q елемента.
Кодът (n,M,d)q, се нарича еквидистантен, ако всеки две
кодови думи се намират една от друга на разстояние d.
Означаваме такъв код с Eq(n,M,d).
Ако всяка дума на Eq(n,M,d), има тегло по Хеминг w, то
лодът се нарича еквидистантен константно-тегловен.
Означаваме го с Eq(n,M,d,w).
q-ичен линеен код C с дължина n и размерност k над
Fq=GF(q), или [n, k]q код, наричаме всяко k-мерно
подпространство на Fnq
Кодове поправящи грешки
Теорема
Всеки (n,M, d)q код C може да открие до s грешки
в дадена кодова дума ако d(C) ≥ s + 1 и да коригира до
t в дадена кодова дума ако d(C) ≥2t + 1
Основна задача:
Да се намери Bq(n, d), най-голямата възможна
стойностна броя кодови думи M, за която съществува
(n,M, d)q код.
21
Някои класове кодове поправящи
грешки
22
Код с повторение - [r,1,r] код
BCH кодове – d = 2t + 1, n = 2m − 1, n − k ≤mt, m и t
произволни цели числа
Рийд-Соломон кодове(RS) - За всяко положително
цяло число t ≤2m − 1, съществува t-символен RS код
със символи от GF(2m) и следните параметри:
n = 2m − 1
n − k = 2t
k = 2m − 1 − 2t
d = 2t + 1 = n − k + 1
Еквидистантни кодове
Bq(n, n) = q
Bq(n, n,w) q
Bq(n, d, n) = Bq−1(n, d)
Bq (n + 1, d,w) ≥ Bq (n, d,w)
Bq (n + 1, d,w + 1) ≥ Bq (n, d,w)
Граница на Плоткин
B q (n, d) dq
dq - n(q - 1)
23
Еквидистантни кодове
Дефиниция
Казваме, че еквидистантният код Eq(n,M, d) (съответно, Eq(n,M,d,w))
e оптимален, ако не съществуват еквидистантни кодове Eq(n,M + 1,
d) или Eq(n,M, d + 1) (съответно, кодове Eq(n,M + 1, d,w) и Eq(n,M, d
+ 1,w)). Казваме, че оптималният код Eq(n,M, d) (съответно, Eq(n,M,
d,w)) е оптимален достигащ границата на Плоткин, ако в матрицата
от кодови думи VC всеки стълб, съдържа всеки елемент на Q
(съответно, всеки ненулев елемент на Q) един и същ брой пъти,
например μ, така че M = q μ съответно, M = (q − 1)(n/w)μ).
Мотивация
Структура
Връзка с дизайни
Приложение в стеганографията (fingerprinting)
24
Еквидистантни кодове
Дефиниция
Нека D – е матрица с размери m x n над Q, имаща следните
свойства: за всеки два нейни различни реда x = (x1, ..., xn) и
y = (y1, ..., yn) вектора, образуван от тяхната покомпонентна разлика:
x − y = (x1 − y1, ..., xn − yn)
съдържа всеки елемент на Q един и същ брой пъти, например λ така,
че n = λq. Казваме че D – е матрица на разликите и означаваме
такава матрица с Dq(m, n) и с Dq(n), ако m = n.
25
Задачи
26
Конструиране на оптимални еквидистантни и
еквидистантни константно-тегловни кодове
Разработка на софтуерни приложения в областта на
теория на кодирането
Разглеждани обекти
27
Оптимални еквидистантни кодове за n≤10,
d≤10, q ≤9
Оптимални еквидистантни константнотегловни кодове за n≤10, d≤10, w ≤ 9, q=3,4,5
Софтуерни приложения
Основни методи
28
Метод за търсене на оптимални еквидистантни и
еквидистантни костантно тегловни кодове
Метод за търсене на оптимални еквидистантни
костантно тегловни кодове
Метод за търсене на оптимални лексикографски
еквидистантни костантно тегловни кодове
Основни софтуерни приложения
29
Компютърен пакет за работа с еквидистантни,
константно-тегловни и лексикографски
еквидистантни константно-тегловни кодове
Кодове поправящи грешки и
воден знак
30
J.R.Hernandez – влияние на кодирането върху
поведението на воден знак в пространствената област
M.Ramkumar, A.N.Akansu – изследване на наличния
капацитет за воден знак в компресирани изображения
S.Zinger – код с повторение, BCH кодове
S.Baudry, J.F.Delaigle, B.Sankur, B.Macq and H.Maitre –
анализ на различни схеми за поправяне на грешки в
системи с воден знак
A.Bastug – подобряване на капацитета за вграждане на
воден знак, чрез кодове поправящи грешки
Оптимални еквидистантни кодове
31
Н.В.Семаков, В.А.Зиновиев, Г.В.Зайцев – оптимални кодове,
връзка с дизайни, кодове достигащи границата на Плоткин.
Г.Богданова – q=3, n≤10 ,d ≤10
J.I.Hall – граници на кодове
J.I.Hall, A.J.E.M.Jansen, A.W.J.Kolen, J.H.van Lint – d=12
Оптимални еквидистантни
константно-тегловни кодове
32
Г.Богданова, Т.Йоргова – q=3,q=4, n≤10 ,d ≤10
F.W.Fu, T.Klove, Y. Luo, V.K. Wei – горни граници
W.Heise, Th.Honold – несъществуване на кодове
Н.В.Семаков, В.А.Зиновиев – кодове следващи от
конструкции
D.R.Stinson, G.H.J.van Rees – кодове и дизайни
Софтуер в областта на теория на
кодирането
33
Линейни кодове – GUAVA, Q-Extension
GFQ – изчисления върху крайни полета
LinCoR – двоични кодове
BLC – двоични линейни кодове
QLC – q-ични линейни кодове
QCC – q-ични константно тегловни кодове
Глава 1
Основни дефиниции и
предварителни резултати
34
Глава 1
35
Скриване на информацията. Стеганография
Защита на информацията с воден знак (watermarking)
Кодове, поправящи грешки
Уеб базирани информационни системи.
Технологии за изграждане на активни уеб сайтове
Глава 2
Методи за защита на
информацията с воден знак
36
Глава 2
37
Методи за защита на изображения с воден знак
Методи за защита на текст с воден знак
Подобряване процеса на защита с воден знак с
използването на кодове, поправящи грешки
Софтуерни приложения и защита на данни с воден
знак
Методи за защита на изображения с
воден знак
Скриване на информация в пространствената област:
Данните се вграждат директно в оригиналното изображени
Основното предимство е, че не са необходими предварителни
трансформации.
Водният знак се вгражда като се променят осветеността или
цветовите компоненти.
Основния недостатък е слабата устойчивост.
38
Методи за защита на изображения с
воден знак
Скриване на информация в пространствената област [Kutter ‘98]:
Вграждане:
За всеки пиксел се генерира псевдослучайно число x
Ако x ≤ ρ, в пиксела се вгражда информация:
Bij = Bij +(2s−1)Lijq, L = 0, 299R +0, 587G+0, 114B, s = {0,1}
Това позволява повторение на един бит на много, псевдослучайни позиции
Обхождането на изображението се извършва зигзагообразно
39
Методи за защита на изображения с
воден знак
Скриване на информация в пространствената област [Kutter ‘98]:
Извличане:
Знакът на δ = Bij – B’ij определя действителната стойност на извлечения бит
Устойчивостта може да се подобри с използването на код, коригиращ
грешки
Методът е устойчив на филтриране, JPEG компресия и геометрични
трансформации
1
c
B i, j k
k c
40
c
B i k, j
4c k c
B ij '
2B
ij
Методи за защита на изображения с
воден знак
Воден знак с разпростиращ се спектър:
Базира се на различни трансформации на контейнера,
например Дискретни Косинусови Трансформации (DCT)
Всички действия се извършват в честотната област на
изображението като тя се разглежда като
комуникационен канал
Вграждането се извършва в значимите области на
изображението
41
Методи за защита на изображения с
воден знак
Воден знак с разпростиращ се спектър[Cox ‘97]:
Вграждане:
N 1
B(k 1 , k 2 ) i 1
–
–
42
j 1
4.A(i, j).cos[
π.k 1
2.N
(2.i 1)].cos[
π.k 2
(2.j 1)]
2.N
Определяне на значимите области и вграждане
Обратни косинусови трансформации
Извличане:
–
N 1
Обратни стъпки и сравняване с праг на съответствие
Силно устойчив на повечето обработки на сигнала и
геометрични трансформации
Методи за защита на текст с воден
знак
43
Кодиране с отместване на редовете –
Като азбука най-често се използва множеството {−1, 1, 0}, която
се кодира като отместване на реда съответно нагоре, надолу или
оставане на място
Кодиране с отместване на думите – При този метод за кодиране
на документа се използва хоризонтално отместване на
позициите на думите в ред
Характеристично кодиране – Документа се анализира за да се
изберът определени текстови характеристики, които се използват
за кодиране.
Схема за коригиране на грешки при
защита с воден знак
Рийд-Соломон код с подходящи параметри като външен код и
друг оптимален линеен код като вътрешен.
Съобщение от k*m бита се кодира с RS(n,k) код над GF(2m) –
корекция на байтови грешки
При фиксирана размерност m, и ограничен общ капацитет за
дължина, избираме оптимален код за вътрешен – корекция на
битови грешки
Сравнение с:
1.
2.
44
S.Baudry, J.F.Delaigle, B.Sankur, B.Macq and H.Maitre, Analyses of error correction
strategies for typical communication channels in watermarking, Signal Processing, 2001,
pp. 1239-1250.
S.Zinger et al., Optimization of watermaking performances using error
correcting codes and repetition, Proceedings of Communications and
Multimedia Security Conference, 2001.
Схема за коригиране на грешки при
защита с воден знак
Пример:
Нека капацитетът е фиксиран на 400 бита, а дължината на водния
знак е 64 бита. Можем да изберем RS(17,13,5) код над GF(25) за
външен код и (23,5,11) оптимален код за вътрешен. Разделяме
съобщението на 13, 5-битови поредици и ги кодираме в 17, 5-битови
поредици.
Всяка от тези 17 5-битови поредици се кодира в 23-битови
поредици. Така, че имаме окончателна дължина от
17 x 23 = 391 < 400 бита. RS(17, 13,5) не е RS код с пълна дължина.
Това е под-добър избор в случая, защото имаме ограничен
капацитет.
45
Схема за коригиране на грешки при
защита с воден знак
Оценка на поведението:
ri
i
(1 p bsc )
C ri p bsc
r
Вероятност за битова грешка:
P rep
i
r
1
2
Код с повторение:
BCH код:
P sig,
1
rep
(1
P rep )
w
ni
i
i
C
p
(1
p
bsc
)
n bsc
n
P sig, code
it1
n
RS/Inn. Код:
P sig, rs
C P
i
n
it1
46
i
sig, inn
(1 P
i
sig, inn
)
ni
Схема за коригиране на грешки при
защита с воден знак
Вероятност за грешка при капацитет 400 бита:
47
Схема за коригиране на грешки при
защита с воден знак
Устойчивост на шум при Psig ≤ 0,01:
48
Схема за коригиране на грешки при
защита с воден знак
Новопредложената техника има по-добро поведение в
средните стойности за дължина на съобщението.Освен
това тази схема дава и относително добри резултати за
големите дължини като 128, 256 бита, където другите
техники са на практика неизползваеми.
49
Софтуерни приложения и защита на
данни с воден знак
Мултимедиен архив от фолклорни обекти
50
Уеб интерфейс за управление на фолклорна база данни.
Клиент сървър приложение, което включва браузър от страна на
клиента Apache уеб сървър от сървърна страна.
Програмните технологии от клиентска страна са ActiveX и
JScript, а от сървърна страна - PHP скриптове.
Базата данни е релационна и се управлява от MSSQL server.
Софтуерни приложения и защита на
данни с воден знак
Мултимедиен архив от фолклорни обекти
51
Софтуерни приложения и защита на
данни с воден знак
Мултимедиен архив от фолклорни обекти.
Изграждане сигурността на системата
Защита на изображенията – ActiveX контроли, защита в
пространствената област
–
–
52
Хеминг код, CRC код
RS код, вътрешен код
Защита на текст – макроси за кодиране, чрез отменстване на
редовете
Права на потребителите – нерегистриран потребител,
регистратор, администратор,
Софтуерни приложения и защита на
данни с воден знак
Онлайн автомобилна система
53
Системата предлага текстова, видео и аудио информация и
възможност за обучение и изпитване в сферата на
автомобилите
Защита на изображенията – воден знак с разпростиращ се
спектър чрез МатЛаб компоненти.
Софтуерни приложения и защита на
данни с воден знак
Приложение за защита на изображение с воден знак
54
Защита чрез воден знак в пространствената област
Допълнителна устойчивост чрез схемата RS код, вътрешен код
Корекция на коефициента на устойчивост и гъстота на
използваните битове
Допълнителна парола – CRC паролата се използва за
инициализация на генератор на псевдослучайни числа
определящи позициите за вграждане
Софтуерни приложения и защита на
данни с воден знак
Приложение за защита на изображение с воден знак –
библиотека CxImage
55
Глава 2 Публикации
[1] T. Todorov, Spread spectrum watermarking technique for information
system securing, International Journal on INFORMATION
THEORIES and APPLICATIONS,Vol.1, 2004, pp.405-408.
[2] T. Berger, T. Todorov, Improving the Watermarking Process With
Usage of Block Error-Correcting Codes, Serdica Journal of
Computing (submitted).
[3] G.Bogdanova, T.Todorov, Ts.Georgieva, Algorithms for security and
analization of experimental multimedia archive, Mathematica
Balcanica, 21 (3-4), 2007, pages 225-232
[4] G.Bogdanova, T.Todorov, Ts.Georgieva, New approaches for
development, analyzing and security of multimedia archive of folklore
objects, CSJMol, Vol.2, 2008 (to appear).
56
Глава 3
Еквидистантни и еквидистантни
константно-тегловни кодове
57
Глава 3
58
Комбинаторни методи за построение
Еквидистантни кодове с разстояния d = 3 и d = 4
Компютърно търсене на еквидистантни кодове
Оптимални еквидистантни константно-тегловни
кодове
Оптимални лексикографски еквидистантни
константно-тегловни кодове
Софтуер за изследвания и обучение в областта на
теория на кодирането
Комбинаторни методи за построение
Дефиниция
Нека D е матрица с размери m x n над азбука Q, имаща следните
свойства: за всеки два нейни различни реда x и y, векторът, получен от
покомпонентната им разлика, съдържа всеки елемент на Q, един и същ
брой пъти, например λ, така че n=λq. Казваме, че D е матрица на
разликите и означаваме с Dq(m,n) или Dq(n), ако m=n.
Теорема [Зиновиев‘69]: Нека D = Dq(n = q k) – матрица на разликите,
представена в стандартна форма. Означаваме с D−1 матрицата, получена
от D премахвайки първия стълб. Тогава D−1 представлява оптимален
достигащ границата на Плоткин еквидистантен Eq(n,M, d) код с
параметри: n = k q − 1, d = k(q − 1), M = k q
(iii)
Теорема [Зиновиев‘68]: Съществуването на RBIB дизайн (v, b, r, k, λ) е
еквивалентно на съществуването на оптимален достигащ границата на
Плоткин еквидистантен код Eq(n,M, d) с параметри:
v
, n = r, d= r – λ, M = v
q 59
k
Комбинаторни методи за построение
Конструкция 1
За вектора a = (a1, a2, … ,an-1, an) над Q с размер q = |Q| означаваме с a{i}
векторът, получен от a чрез циклично изместване на i позиции вдясно.
Теорема: Нека q≥2 е произволно естествено число. Нека a = a(q) е
следния вектор с дължина 2q-1: a = (0, 1, 2, …, q-1, q-1, q-2, …, 2, 1).
Тогава матрицата
60
000 ... 0 a 0 1 a
E 2 a
...
2 q 2 a
е матрица на кодовите думи на оптимален еквидиатнтен код Eq(2q-1, 2q ,2q-2).
Комбинаторни методи за построение
Конструкция 1
Теорема:
Оптимален достигащ границата на Плоткин еквидистантен Eq(n,M, d)код с параметри (iii) съществува за следните значения на q и k:
1.
k = 3, q ≥ 3 – произволно естествено число;
2.
k = 4, q ≥ 2 – произволно естествено число;
3.
k = 5, q ≥ 4 – произволно естествено число, със следните изключе4. ния: q = 27, 32, 38, 39;
5.
k = 6, q ≥ 2 – произволно естествено число;
6.
k = 7, q ≥ 3 – произволно естествено число, със следните изключе7. ния: q = 12, 17, 18, 19, 25, 26, 27, 30, 33, 34, 37, 38, 41, 59, 60, 61, 62, 66;
8.
k = 8, q ≥ 2 – произволно естествено число, със следните изключе9. ния: q = 3, 20, 21, 24, 28, 30, 39, 42, 55, 69, 70, 93, 183, 186;
10. k = q −1, q ≥ 3, където числата k и q са степени на прости числа.
61
Комбинаторни методи за построение
Конструкция 1
Теорема:
Оптимални достигащи границата на Плоткин
еквидистантни q-ични кодове с параметри:
q = 2l + 1, n = 5l + 2, d = 5l, M = 10l + 5 съществуват за
всички естествени l≥ 2 с изключение на: 4, 11, 13, 19, 21,
23,29, 31, 33, 34, 39.
62
Комбинаторни методи за построение
Конструкция 1
63
Теорема:
Нека l≥1 – естествено число. Оптимален достигащ границата на
Плоткин еквидистантен код Eq(n, М,d,) с параметри:
q = (k − 1)l + 1, n = k l + 1, d = k l, M = k(k − 1)l + k
съществува за следните стойности на параметрите k и l:
1.
k = 3, l≥ 1 – естествено число;
2.
k = 4, l≥ 1 – естествено число;
3.
k = 5, l≥ 1 – естествено число, с изключение на: l = 2, 17, 23, 32;
4.
k = 8, l≥ 1 – естествено число, с изключение на: l = 3, 11, 13, 20, 22,
23, 25, 26, 27, 28, 31, 38,43, 47, 52, 53, 58, 59, 61, 67, 69, 76, 79, 93,
102, 103, 111, 112, 115, 123, 124, 125, 133, 134, 139, 140, 143, 174, 182,
191, 192, 195, 197, 199, 203, 208, 209, 211, 213, 218, 220, 223, 224,
227, 229, 230, 232, 237, 243, 247, 248, 250, 253, 254, 391, 437.
Комбинаторни методи за построение
Конструкция 1
Теорема:
Съществуват оптимални достигащи границата на Плоткин
еквидистантни Eq(n,M, d) кодове с параметри:
q = l2 − l + 1, n = l2, d = l2 − 1, M = l3 + 1,
където l – степен на просто число;
q = 2l − 1, n = 2l + 1, d = 2l, M = 2l−1(2l − 1),
където l≥2 – произволно естествено число;
64
q = l2 + 1, n = l2 + l + 1, d = l2 + l, M = l3 + l2 + l + 1,
където l – степен на просто число.
Комбинаторни методи за построение
Конструкция 2
Нека е дадена азбуката Q = {0, 1, 2, …, q-1} означаваме с Q(k), k = 1,2, …,
следната азбука: kq + Q = {kq, kq+1, kq+2, …, (k+1)q -1}.
Конструкция 2 Нека са дадени два еквидистантни кода Eq1(n1,М1,d1) и Eq2(n2,М2,d2).
Нека номерираме кодовите думи на Eq1: Eq1 = {x1, x2, …, xМ1}.
За всяка кодова дума xs = (xs,1, xs,2, …, xs,n1), s = 1,2, …, М1 дефинираме вектор xs(i) над Q1(i):
xs(i) = (xs,1 + (i-1)q1, xs,2 + (i-1)q1, …, xs,n1 + (i-1)q1),
Където събирането се извършва на пръстена на целите числа Z.
Нека М2’=М2/q2.
Номерираме кодовите думи на Eq2:
Eq2 =
y0,1 , y0,2, …........, y0,M’2,
y1,1, y1,2, …........., y1,M’2,
............ .…………………
yq2-1,1, yq2-1,2, …, yq2-1,M’2,
65
Където кодовата дума ys,j , има елемент s
на първа позиция.
Комбинаторни методи за построение
Конструкция 2
Означаваме с ys,j(-1), векторът получен от ys,j премахвайки
първата позиция.
Нека M’’ = min {M1,M2’}. За всяко цяло 0 ≤ k ≤ q2 дефинираме
множеството: E ( k ) x | y M '' 1
k
(i)
i 1
66
j
j0
( 1)
i, j
Теорема
Нека са дадени два еквидистантни кода Eq1(n1,M1,d1) и
Eq2(n2,M2,d2), където d1 = n1-1 и Eq2 е оптимален достигащ
границата на Плоткин. Тогава за всяко 0 ≤ k ≤ q2, Конструкция 2
дава еквидистантен код Eq(n,M,d) с параметри:
q = max(kq1,q2), n = n1 + n2 – 1, d = d1 + d2, M = kM’’.
Комбинаторни методи за построение
Конструкция 3
Конструкция 3
Нека е даден еквидистантен код Eq1(n1,M1,d1) и матрица на разликите
D = Dq2(m2,n2). Добре известно е, че D е еквидистантен код с d2 =
n2(q2-1)/q2.
Номерираме кодовите думи на Eq1: Eq1 = {x1, x2, …, xМ1} и редовете
на D: D = {y1,y2, …, ym2}.
67
Комбинаторни методи за построение
Конструкция 3
Нека Q2 е адитивна абелева група. Нека M’ = min(М1,n2).
Дефинираме следното множество вектори:
E q 2 -1
a0
(x | y a) : j 1,2, ..., M j
j
Теорема
Нека са дадени еквидистантен код Eq1(n1,M1,d1) и матрица на
разликите D = Dq2(m2,n2). Нека d1 = n2/q2. Тогава множеството Е е
еквидистантен код Eq(n,М,d) с параметри q = max(q1,q2), n = n1 + n2,
d = n2, М = q2M’, където М’=min(M1,m2).
68
Еквидистантни кодове с d=3
Теорема
За d=3 е изпълнено
B q (n,3)
69
2,
q,
9,
q,
ако q 2 и n 3
ако q 2 и n 3
ако 3 q 9 и n 4
ако q 10 и n 4
Еквидистантни кодове с d=3
70
Еквидистантни кодове с d=4
Теорема
За d=4 е изпълнено
Bq(n,4)
ако q 2 и n 4
q,
2,
ако q 2 и n 5
ако q 2 и n 6
4,
n 1,
ако q 3 и n 5,6
ако q 3 и 7 n 17
8,
n
ако q 3 и n 17
,
2 16,
ако 4 q 16 и 5 n 33
ако q 4 и 5 n 33
max{16, q},
n
max{q,
}, ако q 2 и n 33
2
Д-во: 15 подслучая и няколко помощни теореми
71
Еквидистантни кодове с d=4
72
Компютърно търсене
73
Търсене с разширяване на код с по-малка
дължина
Търсене, чрез backtrack search
Търсене, чрез конструкции
Компютърно търсене
Търсене с разширяване
74
Подходът при търсене е основан на това, че Eq(n,M, d)-кода C
може да бъде съкратен до еквидистантният Eq(n − 1,M’, d)-код C’
с размер M’.
Обратно построяването на Eq(n,M, d)-кода C, може да се
осъществи чрез разширяването на съществуващ Eq(n − 1,M’, d)код C’.
Съответно можем да построим еквидистантен константнотегловен код Eq(n,M,d,w), чрез разширяването на кода Eq(n−1,M’,
d,w) или Eq(n−1,M’’, d,w−1).
Компютърно търсене
Търсене с backtrack search
Backtrack search след налагане на съответните ограничения
1)
– Фиксирани думи – (0,0,...0) и (0,0,..., 0, 1,1,...,
d
–
–
–
75
Представяне на кодовите думи: x d i, x i : x i 0, i 1...n Ефективно изчисляване на разстоянието между думите
Две кодови думи x = {x1, x2, ..., xn} и y={y1, y2, ..., yn}(x предшества
y в кодовата матрица) на кода имат добра лексикографска
подредба на , ако xi = yi, i = 1...k, k ≤ n и xk+1 ≤yk+1
Компютърно търсене
Търсене в граф
Търсене на максимална клика в граф [Ostergard, Cliquer, 2001]
–
–
–
76
Пространството в което се извършва търсенето съдържа само
векторите, които са на разстояние d от кода ядро
В q-ичния случай построяваме граф, върховете на който, са
вектори с дължина n за дадено q. Съединяваме два върха с ребро,
ако разстоянието по Хеминг между тях е d
Bq(n,d), размера на максималната клика в графа
Компютърно търсене
Търсене с конструкции
77
Търсенето с backtrack search не винаги е приложимо, особено когато
параметрите n, q и d са твърде големи
Софтуерни приложения за някои от описаните конструкции
Компютърно търсене
Резултати
Намерени точни стойности за Bq(n,d):
–
–
–
–
–
–
Намерени граници за Bq(n,d):
–
–
–
–
78
q=4, # = 36, 29 нови кода
q=5 , # = 36, 23 нови кода
q=6, # = 29, 15 нови кода
q=7, # = 31, 17 нови кода
q=8 , # =23, 10 нови кода
q=9, # =23, 10 нови кода
q=6, # = 14, 2 нови кода
q=7, # = 10, 1 нов код
q=8 , # =26
q=9, # =26
Компютърно търсене
Резултати
79
Компютърно търсене
Резултати
80
Компютърно търсене
Резултати
81
Компютърно търсене
Резултати
82
Компютърно търсене
Резултати
83
Компютърно търсене
Резултати
84
Компютърно търсене
Резултати
Намерени нови оптимални еквидистантни костантно
тегловни кодове:
86
Решени са всички случаи за:
– q = 3 , 3 ≤ n ≤10, 2 ≤ w ≤ 9, 3 ≤ d ≤10
– q = 4 , 3 ≤ n ≤10, 2 ≤ w ≤ 9, 3 ≤ d ≤10
Компютърно търсене
Резултати
Намерени нови оптимални лексикографски еквидистантни костантнотегловни кодове:
89
Решени са всички случаи за:
– q = 3 , 3 ≤ n ≤10, 2 ≤ w ≤ 9, 3 ≤ d ≤10
– q = 4 , 3 ≤ n ≤10, 2 ≤ w ≤ 9, 3 ≤ d ≤10
– q = 5 , 3 ≤ n ≤10, 2 ≤ w ≤ 9, 3 ≤ d ≤10
Съвпадение с оптималните еквидистантни константно-тегловни
кодове в много от случаите
Компютърен пакет за изследвания и обучение в
областта на теория на кодирането QPlus
Първа версия [В. Тодоров, Т. Първанов, Г. Богданова, С. Капралов 2003]
93
Приложението е разделено на шест модула:
1.
Модулна аритметика (q < 256):
– Изчисления;
– N-та степен;
– N-ти корен;
– Най-голям общ делител.
2. Вектори (q < 256):
– Сума на вектори;
– Скаларно произведение на вектори;
– Умножение на вектор с число.
3. Матрици (q < 256):
– Събиране на матрици;
– Умножение на матрица с число;
– Умножение на вектор с матрица;
– Умножение на матрици;
– Детерминанта на матрица.
Компютърен пакет за изследвания и обучение в
областта на теория на кодирането QPlus
4.
5.
6.
94
Линейни кодове (q < 256):
– Размерност и базис на кода;
– Систематична пораждаща матрица;
– Спектър на кода;
– Проверочна матрица;
– Спектър на дуалния код.
Търсене на кодове:
– Еквидистантни кодове;
– Константно-тегловни кодове.
– Лексикографски кодове с и без ядро.
Еквивалентност на кодове.
Компютърен пакет за изследвания и обучение в
областта на теория на кодирането QPlus
Програмна реализация и подобрения:
95
Използвани средства – Borland Dephi и ActiveFroms технология
Изцяло обектно ориентирано приложение
Предлага възможност за онлайн използване на част от модулите с
помощта на ActiveX контроли
Реализирани са множество клиентски контроли, които помагат за бърза и
гъвкава реализация на нови модули
Ефективно изчисляване разстоянието между кодовите думи
Използване на побитови операции
Използване на указатели
Компютърен пакет за изследвания и обучение в
областта на теория на кодирането QPlus
Програмна реализация, основни класове:
TCode
Private
Function GetD: Integer;
Function GetWeightSpectrum: TWeightSpectrum;
Function GetDistanceSpectrum: TDistanceSpectrum;
Procedure SetQ(Value : TBase); override;
Procedure UMChanged(var Message : TMessage); message UM_CHANGED;
Protected
Function ComputeD: Boolean; virtual;
Public
Procedure SetD(Value : Integer);
end;
96
Компютърен пакет за изследвания и обучение в
областта на теория на кодирането QPlus
Програмна реализация, основни класове:
TEquidistantCode
Private
Function GetIsEquidistant: Boolean;
Procedure UMChanged(var Message : TMessage); message UM_CHANGED;
Public
Function CheckEquidistancy : Boolean;
Property IsEquidistant : Boolean read GetIsEquidistant;
Property EquidistancyChecked : Boolean read FEquidistancyChecked;
end;
97
Компютърен пакет за изследвания и обучение в
областта на теория на кодирането QPlus
Програмна реализация, основни класове:
98
TEquivalentCode
Private
Function GetBinMatrix: TMatrixCore;
Procedure SetCacheBinMatrix(Value: Boolean);
Procedure UMChanged(var Message : TMessage); message UM_CHANGED;
Public
Function EquivalentToCode(DstCode: TCode; CreatePermSummary: Boolean = False): Boolean;
Function EquivalentToMatrix(DstMatrix: TMatrixCore; CreatePermSummary: Boolean = False):
Boolean;
Function EquivalentToBinMatrix(DstBinMatrix: TMatrixCore; CreatePermSummary: Boolean =
False): Boolean;
Function CompareCodes(SrcCode, DstCode: TCode; CreatePermSummary: Boolean = False):
Boolean;
Function CompareMatrixes(SrcMatrix, DstMatrix: TMatrixCore; MatrixQ: TBase;
CreatePermSummary: Boolean = False): Boolean;
Function CompareBinMatrixes(SrcBinMatrix, DstBinMatrix: TMatrixCore; CreatePermSummary:
Boolean = False): Boolean;
Function CalculateBinMatrix: TMatrixCore;
end;
Компютърен пакет за изследвания и обучение в
областта на теория на кодирането QPlus
Програмна реализация, основни класове:
99
ТLinearCode
Private
Function GetK: Integer;
Function GetSpectrumW(Weight: LongInt): TNumber;
Procedure SetShowBasis(Value : Boolean);
Procedure SetBasisFont(Value : TFont);
Procedure UMChanged(var Message : TMessage); message UM_CHANGED;
Protected
Function ComputeK: Boolean;
Function ComputeD: Boolean; override;
Procedure Reverse(var A, B: TPermutation);
Procedure NavigatorOnChange(Sender: TObject); override;
Procedure FontOnChange(Sender: TObject); override;
Public
Function SysCode: Boolean;
Function ComputeSpectrum : Boolean;
Procedure DualCode;
Procedure DisplayBasis;
Онлайн обучаваща система
Mindcheck
10
0
Уеб базирана обучаваща система [Първа версия Г.Богданова, М.Тодорова,
Д.Благоев]
Основните възможности на системата са:
• Всеки потребител има свои уникални потребителско име и парола
• Търсене на друг потребител регистриран в системата
• Лесен и удобен интерфейс
• Провеждане на тест на конкретна тема
• Изчисляване и сравняване на резултатите
• Потребителят може да създава свои тестове
• Създаване на тестове от текстови файлове
• Създаване на тестове по ключови думи и с определено ниво на трудност
• Многоезична поддръжка
• Учителят може да направлява работата на изпитвания
• Създателите на тестове могат да наблюдават работата и резултатите
на потребителя, правещ теста
• Бърза обработка на заявките
Онлайн обучаваща система
Mindcheck
Подобрения в сигурността
Оптимизация на заявките и подобрения на структурата на базата
данни
Включен обучаващ и тестови модул в областта на теория на
кодирането:
–
–
10
1
Подготвени уроци
Модули от системата Qplus
Внедряване в учебни заведения –ТУ Варна
Глава 3 Публикации
10
2
[1] G.Bogdanova, T.Todorov, V.Zinoviev, On construction of q-ary
equidistant codes, Problems of Information Transmission, Vol.43,
2007, pp.13-36.
[2] G. Bogdanova, T. Todorov, Bounds on the Size of Equidistant
codes over Alphabet of Five and Six Elements, Mathematica
Balcanica, New Series, Vol. 21, 2007, pp. 131-140.
[3]G. Bogdanova, T. Todorov, D.Blagoev and M.Todorova, Use of
Dynamic Technologies for WEB-enabled Database Management
Systems, International Journal Information Technologies and
Knowledge, Vol.1, 2007, pp.335-340.
Глава 3 Публикации
[4] G. Bogdanova, T.Todorov, T.Pagkou, Ternary and Quaternary
Equidistant and Lexicographic Equidistant Constant Weight Codes,
Preprint 1, IMI, 2008.
[5] G. Bogdanova, T. Todorov, Application of digital watermarking,
Journal of International Research Publications - Serial Online,
Bulgaria, Science Invest Ltd, 2006 (online).
[6] G.Bogdanova, T.Todorov, V.Todorov, A Computer Package for
Coding Theory Research and Education, (preprint).
–
10
3
G.Bogdanova, T.Todorov, V.Todorov, Web-Based Application for Coding
Theory Studying, Proc. Int. Congress of Mathematical Society of
Southeastern Europe (MASSEE), Borovets, Bulgaria. September 15-21,
2003, pp. 94-99.
Софтуерни разработки
10
4
Програмни продукти за защита на текст и
изображения с воден знак
Програмен пакет за изследвания и обучение в областта
на теория на кодирането
Мултимедиен архив от фолклорни обекти
Онлайн обучаваща система
Онлайн автомобилна система
Проекти
10
5
Договор АРСИКТ–ИД-13/2005; Завършен и отчетен успешно на (07.2006г.); тема:
“Проектиране и изграждане на експериментален дигитален архив на автентични фолклорни
материали” към агенция “РАЗВИТИЕ НА СЪОБЩЕНИЯТА И НА ИНФОРМАЦИОННИТЕ И
КОМУНИКАЦИОННИТЕ ТЕХНОЛОГИИ” , Съвместен с ВТУ "Св. Св. Кирил и Методий.
Ръководител чл.кор. проф. дмн. Ст. Додунеков.
Проект за дигитализация на фолклорен архив на тема “МОДЕРНИЗИРАНЕ НА
АРХИВНИЯ ФОНД ОТ АВТЕНТИЧНИ ФОЛКЛОРНИ МАТЕРИАЛИ”; съвместен с
Институт за Фолклор към БАН; Продължен; Срок 2006-2007 г. Ръководител чл.кор. проф.
дмн. Ст. Додунеков.
Научноизследователският Проект “Създаване, анотиране и защита на дигитален архив
“Българско фолклорно наследство” (Договор ИО-03-02 /2006) , Фонд ”Научни
изследвания” при МОН, Национални научни програми “Информационно общество”.
Ръководител ст.н.с. II ст. д-р Г.Богданова
Проект BELL: “Проучване и паспортизация на уникални камбани от историческото и
културно наследство на България и създаване на аудио и видео архив с помощта на
съвременни технологии”, Договор КИН 1009/2006 към Фонд “Научни изследвания”,
Министерство на образованието и науката. Ръководител проф. Г. Димков.
Внедрявания
"Eкспериментален дигитален архив на автентични фолклорни
материали“, Институт по фолклор, БАН.
"Обучаваща система Mindcheck" - ТУ Варна.
"Автомобилна система Autoworld" – ПГЕ “А.С. Попов”,
В.Търново.
10
6
Апробация на резултатите
10
7
Национален семинар по теория на кодирането – 2002- 2007
Международна конференция по алгебрична и комбинаторна теория на кодирането
(ACCT) - 2004, 2006
Конгрес на Математическата асоциация на Югоизточна Европа (MASSEE) – 2003,
2006
Международната конференция CompSysTech – 2003, 2004
Международен семинар по хуманитарни науки - 2004
Международна конференция “Оптимални кодове” - 2005, 2007
Международна конференция на съюза на математиците - 2005, 2006
Конференция по математика, информатика и компютърни науки - 2006
Семинар на групата по кодиране на университета в Лимож, Франция - 2005
На семинари на Великотърновски университет „Св.св.Кирил и Методий“ и секция
МОИ – 2006, 2007, 2008
Публикации
[1] T. Todorov, Spread spectrum watermarking technique for information
system securing, International Journal on INFORMATION
THEORIES and APPLICATIONS,Vol.1, 2004, pp.405-408.
[2] T. Berger, T. Todorov, Improving the Watermarking Process With
Usage of Block Error-Correcting Codes, Serdica Journal of
Computing (submitted).
[3] G.Bogdanova, T.Todorov, Ts.Georgieva, Algorithms for security and
analization of experimental multimedia archive, Mathematica
Balcanica, 21 (3-4), 2007, pages 225-232
[4] G.Bogdanova, T.Todorov, Ts.Georgieva, New approaches for
development, analyzing and security of multimedia archive of folklore
objects, CSJMol, Vol.2, 2008 (to appear).
10
8
Публикации
10
9
[5] G.Bogdanova, T.Todorov, V.Zinoviev, On construction of q-ary
equidistant codes, Problems of Information Transmission, Vol.43,
2007, pp.13-36.
[6] G. Bogdanova, T. Todorov, Bounds on the Size of Equidistant
codes over Alphabet of Five and Six Elements, Mathematica
Balcanica, New Series, Vol. 21, 2007, pp. 131-140.
[7]G. Bogdanova, T. Todorov, D.Blagoev and M.Todorova, Use of
Dynamic Technologies for WEB-enabled Database Management
Systems, International Journal Information Technologies and
Knowledge, Vol.1, 2007, pp.335-340.
Глава 3 Публикации
[8] G. Bogdanova, T.Todorov, T.Pagkou, Ternary and Quaternary
Equidistant and Lexicographic Equidistant Constant Weight Codes,
Preprint 1, IMI, 2008.
[9] G. Bogdanova, T. Todorov, Application of digital watermarking,
Journal of International Research Publications - Serial Online,
Bulgaria, Science Invest Ltd, 2006 (online).
[10] G.Bogdanova, T.Todorov, V.Todorov, A Computer Package for
Coding Theory Research and Education, (preprint).
–
11
0
G.Bogdanova, T.Todorov, V.Todorov, Web-Based Application for Coding
Theory Studying, Proc. Int. Congress of Mathematical Society of
Southeastern Europe (MASSEE), Borovets, Bulgaria. September 15-21,
2003, pp. 94-99.
Цитирания
11
1
Милен Петров, Картотека на сключени договори, Дипломна работа, ТУ
Варна, 2004.
Борислав Тоцев, Методи за защита на информацията, Дипломна
работа, ТУ Варна, 2004.
Нелка Иванова, Система за автоматизиране дейността на поликлиника,
Дипломна работа, ТУ Варна, 2004.
Росица Илиева, Приложение на мултимедийните технологии в
обучението, Дипломна работа, ТУ Варна, 2004.
Ели Ганчева, Дискусионен форум, Дипломна работа, ТУ Варна, 2004.
Детелин Недев, Онлайн обучаваща система използваща динамични
сървърни технологии, Дипломна работа, ТУ Варна, 2004.
Стела Железова, Динамични уеб технологии от страна на клиента и
приложението им в обучението, Дипломна работа, ТУ Варна, 2004.
Жана Буланова, Система за модернизиране на архивен фонд от
автентични фолкорни материали, Дипломна работа, ВТУ В.Търново,
2004.
Публикации
11
2
Problems of Information Transmission – 1
Mathematica Balcanica, New Series – 2
Serdica Journal of Computing - 1
International Journal Information Technologies and Knowledge -1
International Journal on Information Theories and Applications – 1
CSJMol - 1
Journal of International Research Publications - Serial Online -1
Preprints - 2
Документ
Категория
Презентации по информатике
Просмотров
21
Размер файла
876 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа