close

Вход

Забыли?

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

?

Метод двумерного струкутрного кодирования двоичных данных.

код для вставкиСкачать
Розенброка є найбільш ефективним для визначення оптимальних параметрів тришарових структур.
Таблиця 3
Кількість початкових значень, які дозволяють досягнути максимуму,
та середня витрата машинного часу на пошук методів багатовимірного
пошуку при дослідженні тришарових структур
5. Висновки
У даній роботі отримано результати, які легко спроектувати на реальні матеріали. Це
дозволяє розширити можливості просвітлення одно-, двота тришаровими однорідними
опт ичними струк турами
підкладинок із низьким показником заломлення.
??????
????????????
(????-??????)
??????????
???????????? ??????
????????-?????
???????-????????
????????-???????????????
При визначенні оптимальних ??????????
значень параметрів однорідних ??????????-???????
структур найкраще викорис- ??????????
товувати: для одношарових
структур ? метод конфігурацій (Хука-Дживса), для
дво- та тришарових структур ? метод Розенброка.
Література: 1. Яковлев П.П., Мешков Б.Б. Проектирование интерференционных покрытий. М.: Машиностроение, 1987. 192с. 2. Abeles F. Аnn. de Physique. 1950.
V.5. P.596-640. 3. Міца О.В. Оптимізація характеристик
оптичних покриттів на основі неоднорідних плівок з
різним типом розподілу показника заломлення //
Наук. вісник Ужгород. ун-ту. Сер. матем. і інф. 2001.
Вип. 6. С.95-99. 4. Мица А.В., Первак Ю.А., Фекешгази
И.В. Расчет и оптимизация оптических свойств неоднородных пленок на подложках Ge с квадратическим
распределением показателя преломления // Харьковская научная ассамблея (14-й международный симпозиум ?Тонкие пленки в оптике и электронике?). Харьков: Контраст, 2002. С. 62-65. 5. Ляшенко И.Н., Карагодова
Е.А., Черникова Н.В., Шор Н.З. Линейное и нелинейное
программирование. К.: Вища шк., 1975. 372с.
?????????? ????????? ?
???????? 10-6?10-4
?????????
????????
?????
???, ?
?????????? ????????? ?
????????? ???????? (10-7)
?????????
????????
?????
???, ?
7
0.88
38
1.13
130
148
48
137
0.72
3.94
4.58
6.77
9
0
109
15
0.85
?
6.15
8.92
177
8.82
5
8.97
3
92
3
1.66
4.61
1.21
0
0
0
?
?
?
Рецензенти: д-р техн. наук, проф. Василенко Ю.А.,
д-р техн. наук, проф. Путятин В.П.
Міца Олександр Володимирович, аспірант кафедри
кібернетики та прикладної математики Ужгородського національного університету. Наукові інтереси: математичне моделювання технічних та економічних
систем, оптимізаційні методи. Адреса: Україна, м.Ужгород, вул. Бестужева, 4/10, тел. 8 (03122) 5-46-47 email: mitsa@univ.uzhgorod.ua.
Головач Йожеф IІгнацович, д-р техн. наук, професор,
завідувач кафедри Егерського інституту ім. Естергазі
(Угорщина), професор кафедри кібернетики та прикладної математики Ужгородського національного
університету. Наукові інтереси: математичне моделювання технічних та економічних систем, оптимізаційні
методи, системи штучного інтелекту, бази даних. Адреса: Україна, Ужгород, провул. Університетський, 4/
2, тел. 8 (03122) 4-21-05
Надійшла до редколегії 01.10.2002
УДК 621.327
МЕТОД ДВУМЕРНОГО
СТРУКУТРНОГО КОДИРОВАНИЯ
ДВОИЧНЫХ ДАННЫХ
БАРАННИК В.В.
Излагается метод компактного представления двоичных данных на основе исключения двумерной структурной избыточности. Разрабатывается обобщенное
двумерное структурное кодирование двоичных массивов, позволяющее организовать равномерное представление кодовых комбинаций. Определяются нижние границы эффективности простого и обобщенного
двумерного структурного кодирования.
Введение
Данные, полученные в результате оцифровки различных видов сигналов (речь, текст, изображения,
аудио сигналы), представляются в информационно
? вычислительных системах (ИВС) в двоичном
виде. Значит, подход к устранению избыточности
обрабатываемых и передаваемых в ИВС данных на
двоичном уровне является общим средством для
РИ, 2003, № 1
компактного представления информации. В то же
время для сжатия двоичной информации в основном используются методы статистического кодирования. К ним относятся адаптивный код Хаффмена ? Галлагера, арифметические коды, неравномерные символьные коды [1-3]. Основными
недостатками статистического подхода являются:
неравномерность кодовых комбинаций, необходимость вычислять статистические характеристики,
использование разделителей, слабая помехоустойчивость. Это приводит к снижению коэффициента
сжатия и повышению времени кодирования.
Одним из вариантов устранения перечисленных
недостатков является компактное представление,
основанное не на статистических свойствах двоичных данных, а на их структурных свойствах [4, 5].
1. Разработка метода кодирования двумерных
двоичных структур данных
Суть структурного подхода к компактному представлению информации состоит в том, что кодирование осуществляется с учетом выявленных закономерностей в массивах данных. Рассмотрим двоичный массив A {a i j} , i 1, m ; j 1, n , где m , n
109
? соответственно количество строк и столбцов в
массиве А. Если структурные характеристики определяются для отдельной последовательности A j
{ a1 j , . . . , a ij , . . . a mj} - j-я двоичная последова(A j
тельность (столбец) массива А), то оператор кодирования M x примет вид
M (A
Nj
j
),
(1)
где N j ? структурный код, сформированный для
последовательности A j .
В результате применения оператора M x ко всем
столбцам массива А образуется последовательность
структурных кодов N {N1, ..., N j, ... N n } . Для такого кодирования сжатие данных достигается выявлением структурных особенностей обрабатываемых массивов, причем степень сжатия будет больше
в случае выявления структурных характеристик
для всего массива. Поэтому в качестве характеристик требуется использовать такие, которые позволяют описывать двумерные структуры. В соответствии с этим выберем в качестве структурных
характеристик следующие: Z ? количество допустимых зон (число укрупненных серий возможных
позиций единиц); 4 ? вектор значений числа
серий с учетом допустимых зон.
Для выбранных структурных характеристик формирование кодов N j проводится с помощью выражений:
N( 4 j k
Nj
§ k
k ·
¦ N Ё - zj , 4 j ё ;
©
№
z 1
Kj
Kj Z
k 1
k 1z 1
(2)
§ k
k ·
¦ ¦ N Ё - zj , 4 j ё ,
№
©
¦ N( 4 j k )
(3)
где -zjk ? значение числа серий для z -й допустимой зоны j-й двоичной последовательности; 4 k ?
j
k-й вектор значений числа серий -zjk длиной Z
элементов, k 1, K j : 4 k {-1kj , ..., -zjk ,..., -Zjk } ; K j
j
? количество векторов 4 k (количество распредеj
лений величин - j по Z зонам для j -го столбца
массива А), равное
Kj
( - j Z 1) !
( Z 1) ! ( - j ) !
- j ? число серий для A
ности, равное
-j
j
;
(4)
двоичной последовательZ
¦ -zjk ;
z 1
k-го вектора значений величин -zjk .
Структурный код N §Ё -zjk , 4 k ·ё для начальной
j №
©
зоны z 1 находится по формуле
m
z
N §Ё - zjk , 4 k ·ё ¦ a ij w i ,
j №
©
i 1
где w i ? весовой коэффициент i-го двоичного
элемента z-й допустимой зоны. Значение величины
k
w i зависит от числа серий -zj [4].
Для допустимой зоны, расположенной в середине
или в конце двоичной последовательности z t 2 ,
значение кода N §Ё -zjk , 4 k
j
©
§
k
k ·
N Ё - zj , 4 ё
j №
©
· равно
ё
№
mz
¦ a ij w i
i m z 1 1
.
Из определения структурных характеристик следует, что вектор 4 k порождает множество двоичных
j
последовательностей < §Ё 4 k ·ё мощностью, равной
© j №
< §Ё 4 k ·ё
© j №
Z
k
– V( - zj , m z ) ,
z 1
(6)
здесь m z ? количество допустимых позиций в z-
Z
)
кода j -й двоичной последовательности, полученного с учетом обработки всех Z допустимых зон для
(5)
N §Ё -zjk , 4 k ·ё ? структурный код j -й двоичной
j №
©
последовательности, полученный для z -й допустимой зоны по числу серий, равных -zjk для
вектора 4 k ; N §Ё 4 k ·ё ? значение структурного
j
© j №
110
й зоне; V( - zjk , m z ) ? количество двоичных пос-
k
ледовательностей с характеристикой -zj и длиной
m z элементов.
Согласно выражениям (2) и (6) значение кода
N §Ё 4 k ·ё является обобщенной структурной еди© j №
§
·
ницей для множества < Ё 4 k ё . Поэтому значения
© j №
кодов N §Ё -zjk , 4 k ·ё можно рассматривать как отj №
©
§ k ·
дельные составляющие величины N Ё 4 ё . В свою
© j №
очередь, в соответствии с выражением (3) величина
кода N j является структурным обобщением для
всех множеств < §Ё 4 k ·ё , k 1, K j . Тогда с учетом
© j №
выражений (4) ? (6) значения кодов N §Ё -zjk , 4 k ·ё ,
j №
©
k ·
§
N Ё 4 ё и N j находятся в пределах, задаваемых
© j №
соответствующими неравенствами:
0 d N §Ё - zjk , 4 k ·ё d
j №
©
( m z 1) !
( 2- zjk ) ! ( m z 1 2- zjk ) !
V( - zjk , m z ) ;
(7)
РИ, 2003, № 1
0 d N 4 jk
0 d Nj d
d
Z
k
– V( - zj , m z )
z 1
Kj Z
Kj
k 1z 1
k 1
V ( 4 jk
) ; (8)
k
¦ V( 4 j ) V j ,(9)
k
¦ – V( - zj , m z )
V( 4 jk ) ? количество двоичных последовательностей, удовлетворяющих вектору структурных
характеристик 4 k ; V j ? суммарное количество
j
двоичных последовательностей в множестве < j :
<j
Kj
§
k
·
* < Ё4 j ё .
©
№
k 1
Из анализа выражений (7)-(9) вытекает, что значение двумерного структурного кода N j будет больше 1, если найдется хотя бы одно m z t 2 . Тогда
будут существовать такие -zjk , k 1, K j , для которых
а
сле довател ьно,
V (- k , m z ) t 2 ,
zj
< §Ё 4 k ·ё t 2 , т.е. множество < §Ё 4 k ·ё не является
© j №
© j №
пустым.
Поскольку количество допустимых зон Z фиксировано для всех двоичных последовательностей
A j , а значения величин -zjk в общем случае
разные, то значения кодов N j также будут различными. Следовательно, для организации равномерных кодовых комбинаций необходимо разработать
кодирование, позволяющее представлять одним
структурным кодом несколько столбцов массива А.
Таким образом, разработан метод двумерного структурного кодирования двоичных массивов. В этом
случае сжатие данных достигается путем устранения двумерной структурной избыточности, обусловленной ограниченным числом серий в ограниченном количестве допустимых зон единичных
позиций.
2. Разработка обобщенного двумерного
структурного кодирования двоичных данных
Обобщенное двумерное структурное кодирование
состоит в формировании одного кода N j, . . .,n x для
x
нескольких n столбцов двоичного массива. При
этом код N j, . . .,n x , также как и простой код N j ,
формируется с учетом выделенных двумерных
структурных характеристик. Для организации равномерных кодовых комбинаций условием выбора
x
количества столбцов n является выполнение неравенства
·
x
M
V §Ё x , n m z ё d 2 1 ,
№
© j, ..., n
(10)
где ? суммарное число серий для n x
j, .. ., n x
двоичных столбцов. При этом с учетом ограничения -
Z nx
j, . . ., n x
¦ -zjk величина - j, ..., n x может изме-
z 1
няться в пределах
РИ, 2003, № 1
-
j, ..., n x
§
Ё
Ё
Ё
©
· nx
§ nx ·
ё
Ё
ё
x
n
1
ё; ¦-j .
Ё¦ jё
Ёj 1 ё
ё j1
©
№
№
Неравенство (10) позволяет выбрать такие двоичные столбцы, для которых длина обобщенного
структурного кода не будет превышать длину
разрядной сетки. В этом случае величина кода
N
j, . . ., n x вычисляется по формуле
N
K x Z nx
n
k x ·
§ k x
¦ ¦ N Ё - zj n , 4 j n ё ,
j, . . .,n x
k 1 z 1
(11)
№
©
§ §Ё k x ·ё §Ё k x ·ё ·
Ё
ё
где N Ё -©zj n № , 4© n № ё ? значение структурного
j
Ё
ё
©
№
§
·
Ёk
ё
x
кода z -й допустимой зоны по числу серий -©zj n №
§k
·
Ё xё
и вектора 4© n № для обобщенной двоичной посj
ледовательности, состоящей из n x первоначальных
столбцов.
§k
·
Ё xё
При этом количество векторов 4 © n № изменяется
j
от 1 до K x :
n
K x
n
( - j, ...,nx n x Z 1) !
(n x Z 1) ! (- j, ...,n x ) !
.
(12)
Поскольку структурные характеристики для определения обобщенного и простого кодов одинаковые, то с учетом формулы (12) величина
·
x
V §Ё x , n m z ё равна
№
© j, ..., n
·
x
V §Ё x , n mz ё
© j, ..., n
№
K x nxZ
n
§ §Ё k x ·ё
·
k 1 z 1
©
№
Ё
ё
¦ – V Ё -©zj n № , n x m z ё ,
Ё
ё
·
§ §Ё k x ·ё
ё
Ё
где V Ё -©zj n № , n x m z ё ? количество двоичных посё
Ё
№
©
§
·
Ёk
ё
x
ледовательностей с характеристикой -©zj n № и дли-
ной n x m z элементов.
Тогда по аналогии с выражениями (7)-(9) величина
обобщенного структурного кода N
находится
j, . . ., n x
в диапазоне
x
·
d V §Ё x , n mz ё .
(13)
© j, .. ., n
№
Из сравнительного анализа неравенств (10) и (13)
0d N
j, . . .,n x
·
x
следует, что если величина V §Ё x , n m z ё не
№
© j, ...,n
превышает максимально возможного диапазона
для М разрядов, то значение кода N j, . . .,n x тем более
не будет его превышать.
Таким образом, разработано обобщенное двумерное структурное кодирование, обеспечивающее
равномерную организацию кодовых комбинаций.
111
Выводы
1. Разработан метод компактного представления
двоичных массивов на основе выделения двумерных структур. В этом случае сжатие данных достигается путем устранения двумерной структурной
избыточности, обусловленной ограниченным числом допустимых позиций единиц (допустимых
рабочих зон).
2. Разработано обобщенное двумерное структурное
кодирование, позволяющее сформировать один
код для нескольких столбцов двоичного массива.
При этом сочетание обобщенного кодирования с
простым двумерным структурным кодированием
обеспечивает равномерную организацию кодовых
комбинаций.
3. Разработанный метод сжимает двоичные данные
без дополнительного знания априорной информации, а следовательно, может использоваться для
кодирования сообщений широкого класса источников информации.
Литература: 1. Галлагер Р.Г. Адаптивный код Хаффмена
// ТИИЭР. 1978. №6. С. 668-674. 2. Зив Дж. Арифметический код // ТИИЭР. 1994. №11. С. 102-104. 3. Bell T. C. Text
compression. Englewood Clifs, N. J.: Prentice - Hall, 1990. 4.
Королев А.В., Баранник В.В. Оценка количества информации изображения по числу серий одинаковых элементов // Системи обробки інформації. Харків: НАНУ,
ПАНМ, ХВУ. 2002. Вип. 2(18).С. 43-46. 5. Александров В.В.,
Горский Н.Д. Представление и обработка изображений.
Рекурсивный подход. Л.: Наука, 1985. 192 с.
Поступила в редколлегию 01.09.2002
Рецензент: д-р техн. наук Фоменко О.Н.
Баранник Владимир Викторович, канд. техн. наук,
старший научный сотрудник информационно-вычислительного центра ХВУ. Научные интересы: обработка и передача информации. Адрес: Украина, 61023,
Харьков, ул. Сумская, 77/79, тел. 40?28?47.
УДК 204.056.55
DetC
СВОЙСТВА р-ЧИСЕЛ И Q np МАТРИЦ СТАХОВА В КОЛЬЦЕ
ЦЕЛЫХ ЧИСЕЛ Z / q
САМОЙЛЕНКО Н.И., УФИМЦЕВА В. Б.
Рассматриваются числа и матрицы Стахова в кольце
целых чисел по модулю q . Приводятся доказательства
выполнения основных свойств Q n -матриц в кольце
p
целых чисел по модулю q , что позволяет избежать
большой избыточности при использовании их в криптографических методах шифрования информации.
Проблема информационной безопасности особенно обострилась в современном мире ? мире компьютеров, сетей и информационных технологий.
Наиболее эффективным методом обеспечения конфиденциальности и целостности информации является ее криптографическое преобразование. Таким является метод на основе матриц Стахова [1].
Он заключается в умножении исходного текста,
представленного в виде квадратной матрицы M
размером p 1 u p 1 , на n -ю степень матрицы
n
Стахова p -го порядка Q p при шифровании и
криптоматрицы C на обратную матрицу Стахова
Q p n при дешифрации:
C
ЄM u Q n є. и M
p »ј
«¬
ЄC u Q n є.
p »ј
«¬
При этом особые свойства матриц Стахова сводят
процесс умножения произвольной матрицы на
матрицу Стахова и возведения в степень Q np матрицы к простым операциям сложения (или
вычитания при n 0 ).
n
Детерминант матрицы Q p равен 1 pn , поэтому
детерминант матрицы исходных данных может
отличаться от детерминанта матрицы криптограммы лишь знаком:
112
(1) pn u DetM,
что позволяет не только обнаружить ошибки в
полученных данных (без предварительного расшифровывания), но и во многих случаях исправить их.
Однако операции умножения матриц и присоединение к сообщению значения детерминанта приводят к значительной избыточности информации.
Для устранения этого недостатка можно производить криптографические преобразования информации в кольце целых чисел по модулю q (при
программной реализации q 16, 32 или 64).
Рассмотрим числа и матрицы Стахова и их основные свойства в кольце целых чисел Z / q .
1. Числа и матрицы Стахова
Числа Стахова [1], называемые p -числами, являются обобщением чисел Фибоначчи и вычисляются
по рекуррентной формуле:
Fp (k )
Fp (k 1) Fp (k p 1) ,
(1)
где p Џ Z € p t 0 , при следующих начальных условиях:
Fp (1)
Fp (2) ! Fp (p 1) 1 .
(2)
Рекуррентная формула (1) при начальных условиях
(2) генерирует бесконечное число последовательностей, так как каждому p соответствует своя последовательность (в частности, при p 1 генерируется
классическая последовательность чисел Фибоначчи, а при p 0 ? двоичная последовательность: 1,
2, 4, 6, ј).
Обобщенная Q -матрица Фибоначчи для чисел
Стахова, называемая Q p -матрицей Стахова, представляет собой квадратную p 1 u p 1 -матрицу, содержащую в себе p u p -единичную матрицу
и ограниченную слева столбцом, состоящим из
нулей, кроме первого и последнего элементов,
РИ, 2003, № 1
Документ
Категория
Без категории
Просмотров
4
Размер файла
632 Кб
Теги
данных, метод, двоичных, струкутрное, кодирование, двумерной
1/--страниц
Пожаловаться на содержимое документа