О В Бандирська, В В Різник, І Ю Юрчак - Алгебричний метод проектування кругових шкал з високою роздільною здатністю - страница 1

Страницы:
1  2 

Висновок

Алгоритм забезпечує захист даних від несанкціонованого доступу завдяки їхньому проміжному перетворенню на код в'язанки, параметри якої відомі тільки користувачу. За допомогою монолітних кодів, побудованих за допомогою в'язанок, можна застосовувати ефективні алгоритми кодування і декодування інформації, що розширяє сферу практичних застосувань у задачах інформаційної техніки і проектування систем кодування [6, 7].

Результати досліджень кодування інформації на основі числових в'язанок дають підстави стверджувати про можливості їхнього використання у сучасних інформаційних технологіях для задач захисту інформації [1, 5].

1. Дурняк Б.В., Різник О.Я., Різник В.В., Я.П. Кісь Я.П., Парубчак В.О.. Захист даних методом комбінаторної оптимізації // Праці третьої міжнародної наукової конференції ISDMIT'2007, м.Євпаторія. т.2, с.152—153. 2. Ризнык О.Я. Комбинаторные модели для синтеза технических устройств и систем на основе числовых линейных сцепок //Контрольно-измерительная техника.Львов: Вища школа. — 1989. — Вып.45. С.23—25. 3. Різник В.В. Синтез оптимальних комбінаторних систем. — Львів, 1989. 4. Різник О.Я. Завадостійкий спосіб перетворення сигналів // Матеріали Четвертоїукр. конф. з автоматичного керування ("Автоматика-97"). — Черкаси. — 1997. — С.34. 5. Різник О.Я., Парубчак В.О., Скрибайло-Леськів Д.Ю. Використання числових в'язанок для кодування інформації//Праці міжнародної конференції "Сучасні комп'ютерні системи та мережі: розробка та використання" (ACSN'2007). С.112—114. 6. Різник О.Я., Парубчак В.О., Скрибайло-Леськів Д.Ю. Кодування інформації за допомогою монолітного коду. Праці 2-ї міжнародної науково-практичної конференції "Інформаційні технології в наукових дослідженнях і навчальному процесі", м. Луганськ, 2007, т.2. С.88—92. 7. Різник О.Я., Стасевич С.П., Парубчак В.О., Скрибайло-Леськів Д.Ю. Швидкий синтез подібних кодів Баркера // Праці міжнародної конференції з математичного моделювання AMSE'2007, м. Алушта. — С. 23—24.

УДК 004.421

О.В. Бандирська1, В.В. Різник2, І.Ю. Юрчак3

Національний університет "Львівська політехніка", 1кафедра інформаційно-вимірювальних технологій, 2кафедра автоматизованих систем управління, 3кафедра систем автоматизованого проектування

АЛГЕБРИЧНИЙ МЕТОД ПРОЕКТУВАННЯ КРУГОВИХ ШКАЛ З ВИСОКОЮ РОЗДІЛЬНОЮ ЗДАТНІСТЮ

© Бандирська О.В., Різник В.В., Юрчак І.Ю., 2008

Розглядається алгебричний метод проектування нееквідистантних кругових шкал з підвищеною роздільною здатністю. Ці шкали ґрунтуються на так званих "ідеальних кіль­цевих в'язанках". Використовується принцип "оптимальних структурних пропорцій".

Algebraic method for design of non-uniform ring scales with improved resolving ability is described. These scales has been based on the so-called "Gold Ring Bundles". The principle of the "optimum structural proportions" (OSP) is applicated.

Алгебричні моделі та методи проектування систем будь-якого призначення широко застосовуються в радіоелектроніці, технічній кібернетиці, інформаційно-вимірювальній та обчислювальній техніці, а комбінаторні конфігурації широко використовуються для оптимальногопроектування багатьох пристроїв мікро- і наноелектроніки. Актуальними є дослідження властивостей наявних і пошук нових комбінаторних моделей, які дають змогу швидко знаходити способи побудови систем та виявляти теоретичні зв' язки з класичними математичними методами оптимального просторового розміщення структурних елементів систем.

Аналіз проблеми та постановка задачі

Для проектування синтезу систем застосовують здебільшого класичні методи комбінатор­ного аналізу, що ґрунтуються на положеннях комбінаторного аналізу з використанням табличних, теоретико-числових та матричних інтерпретацій, методи апарата скінченних груп перестановок, теорії чисел, схеми відношень, а також методи, пов'язані з використанням апарату теорії полів [1].

Метод побудови комбінаторних моделей із застосуванням впорядкованих сукупностей елементів - цілих додатних чисел, лежить в основі поняття "ідеальної кільцевої в'язанки" (ІКВ), що відіграє роль базової моделі для проектування систем з оптимальним розміщенням елементів структури за критерієм досягнення максимальної інформаційної різноманітності системи без збільшення кількості її елементів та зв'язків [2, 3]. Теорія ІКВ та властивості в'язанок лягли в основу нового підходу до проектування технічних пристроїв та систем з поліпшеними якісними характеристиками за такими показниками, як надійність, роздільна здатність, функціональні можливості. Математичні конструкції на впорядкованих елементах, які організовані згідно із вищезгаданим принципом, виявилися зручним інструментом для синтезу та дослідження кругових шкал з нерівномірним розміщенням позначок, що дало змогу підвищити їхню роздільну здатність завдяки зменшенню кроку відліку [4].

Можливість застосування алгебричних методів синтезу кругових шкал випливає з того факту, що структура деяких алгебричних конструкцій і будова кругових шкал з підвищеною роздільною здатністю ґрунтуються на принципі "оптимальних структурних пропорцій" (ОСП), в якому використовуються властивості ІКВ [5]. Основна ідея полягає в оптимальному розміщенні фіксованої кількості позначок на шкалі за критерієм досягнення якнайвищої її роздільної здатності. Один із підходів до вивчення та проектування шкал з підвищеною роздільною здатністю ґрунтується на використанні алгебричних властивостей полів Ґалуа.

Алгебра полів Ґалуа

Для всякого степеня простого числа p і будь-якого Г1 існує єдине з точністю до

ізоморфізму GF( pr ), тобто поле зі скінченною кількістю елементів або поле Ґалуа, де GF означає Galois Field.

З теорії скінченних полів відомо, що поле GF( pr ) можна зобразити як множину всіх класів лишків за модулем довільного полінома f( X ) степеня r , незвідного над полем GF( p ). Поліном f( X ) степеня r 1 з коефіцієнтами із поля GF( p ) є незвідним над полем GF( p ), якщо його не можна записати у вигляді f( X ) = A( X ) B( X ), де A( X ) і B( X ) - поліноми над

GF( p ). Наприклад, незвідним поліномом у полі GF( 3) буде поліном f = X2 - 2. У цьому доволі легко переконатися, перевіривши, що він не ділиться без залишку на поліноми степеня r 1 з коефіцієнтами із поля тобто на поліноми X, X — 1, X — 2. Поліном f( X )

степеня n 1, незвідний над полем GF(q), називається первісним, якщо його корінь 0 є первісним елементом поля GF( qs ). Якщо S = 1, q = pr, то первісним буде такий незвідний над полем GF( pr ) поліном степеня n , корінь якого в полі GF( pr ) має період pr1.

У такому разі всі корені полінома f( X ) первісні. Кожен відмінний від нуля елемент к поля GF( q ) подається у вигляді

к = 0t. (1)

Характеристична функція

ft(x) = f(x; 0t) (2)

елемента є поліномом степеня n з коефіцієнтами з GF(q).

У полі GF( qs ) всі його qs — 1 ненульові елементи різні та утворюють циклічну групу за

операцією множення. Завдання полягає в тому, щоб дослідити комбінаторні властивості полів Ґалуа, і на основі вивчення їхньої структурної організації розробити алгоритм синтезу шкал з високою роздільною здатністю.

Відомо, що первісний елемент X поля GF(qs ) має максимально можливий період qs 1 елементів цього поля,   а степені Xк  (к=0, 1,..., ps 2) перебігають усі ненульові елементи

GF( q ) і є також елементами цього поля [2]. Оскільки xp —1 = 1, то Xp   = X, Xp +1 = X2 і т.д.

Відомо, що мультиплікативна група (група за операцією множення)  GF( qs ) є циклічною. Якщо

деякий елемент X поля GF( q ) має період q  —1 і є коренем полінома f( X), то єдиними

коренями полінома f( X ) будуть також і елементи поля X2 ^3 ^.^Xq —2. Автоморфізми поля

GF( qs ) утворюють циклічну групу порядку S , яка породжується автоморфізмом ОС: X_> Xp

для будь-якого X ^ GF( q ). Іншими словами, це така взаємна відповідність, за якої корені цього незвідного полінома переводяться в інші корені цього самого полінома. В цьому можна переконатися,

2

побудувавши поля для різних коренів полінома. Так, корені полінома f( X) = X + X + 2 є первісними елементами поля GF( 3 ). Якщо коренем полінома вибрати первісний елемент X , то отримаємо поле GF1( 32 ), елементами якого є степені X за модулем q=3:

X0 = 1 = X

X2 = 2x +1 X3 = 2х + 2 X4 = 2 х5 = X х6 = х + 2 х7 = х +1

Якщо коренем незвідного полінома взяти х3 = 2X + 2, то отримаємо поле GF2 (), елементами якого є степені х за модулем q=3:х0 = 1 х1 = 2 х + 2 х2 = х + 2 х3 = X х4 = 2

х5 = X + 1

х6 = 2 х +1 х7 = 2 х

Елементи поля GF^32) взаємно однозначно відображаються в елементи GF2 ( 32 ), причому задовольняються всі закони поля [1].

Підполя поля GF( pr ) - це поля GF( pm ), де m ділить r. Для будь-якого r поле GF( pr ) має єдине підполе GF( pm ), що складається з елементів поля GF( pr ), які задовольняють рівняння = ^. Первісний елемент X поля GF( pr ) задовольняє рівняння

g( X ) = 0 , де g( X ) - незвідний над GF( pm ) поліном степеня r/m .

2

Наприклад, поле можна подати класами лишків за модулем f( X ), де f( X ) -

незвідний над GF(52) поліном степеня 2. Такими незвідними поліномами є f1 = X   2 та

f 2 = X   + X + 1. Тому утворюються два ізоморфні поля м та г2 з 25 елементами.

6        5 3 2

Поліном f( X) = X + X + X + X + 1 незвідний над GF( 2). Отже, лишки A( X ) (mod f( X ))      утворюють поле елементами. Первісним елементом в

цьому полі є елемент х , а його степені дають ненульові елементи поля GF( 26 ): 2 ^v X62 .

Підполе GF( 2 ) поля GF( 26 ) містить елементи 0, 1; GF( 22 ) - елементами 0,1, X21 ,X42 що

. z4 = z    GF( 23 v 0  1   х9   х18   х27   х36   х45   х54

задовольняють рівняння ; GF( 2 ) - елементами 0, 1 , X , X   , X   , X   , X   , X   , де

8 6 z   = z. Автоморфізми поля GF( 2 ) утворюють циклічну групу порядку 6, яка породжується

26

автоморфізмом О : z   ^ z   = ( z для будь-якого Z Є GF( 2   ).

Простір всіх векторів ,...,as ), ai Є F , де F - довільне поле - є проективною

геометрією PG( S,F ) розмірності S над полем F , а підпростір розмірності S1 називається гіперплощиною.

Страницы:
1  2 


Похожие статьи

О В Бандирська, В В Різник, І Ю Юрчак - Алгебричний метод проектування кругових шкал з високою роздільною здатністю