Оценки сложности экспериментов с блоками управляемых перестановок
Для базових типів блоків керованих перестановок (матричних, пошарових та рекурсивних) отримано асимптотичні оцінки складності експериментів, призначених для виявлення або локалізації поодиноких несправностей. Встановлено, що для матричних та рекурсивних блоків керованих перестановок складність цих е...
Saved in:
| Published in: | Доповіді НАН України |
|---|---|
| Date: | 2011 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Видавничий дім "Академперіодика" НАН України
2011
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/37380 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Оценки сложности экспериментов с блоками управляемых перестановок / В.Г. Скобелев // Доп. НАН України. — 2011. — № 4. — С. 41-43. — Бібліогр.: 5 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-37380 |
|---|---|
| record_format |
dspace |
| spelling |
Скобелев, В.Г. 2012-10-09T17:53:57Z 2012-10-09T17:53:57Z 2011 Оценки сложности экспериментов с блоками управляемых перестановок / В.Г. Скобелев // Доп. НАН України. — 2011. — № 4. — С. 41-43. — Бібліогр.: 5 назв. — рос. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/37380 519.17 Для базових типів блоків керованих перестановок (матричних, пошарових та рекурсивних) отримано асимптотичні оцінки складності експериментів, призначених для виявлення або локалізації поодиноких несправностей. Встановлено, що для матричних та рекурсивних блоків керованих перестановок складність цих експериментів не є істотною порівняно зі складністю самого блоку. For basic types of controlled blocks of permutations (namely, matrix, stratum, and recursive ones), the asymptotic estimations of complexity of experiments intended to detect or to localize simple faults are established. It is shown that, for matrix and stratum controlled blocks of permutations, the complexity of above-mentioned experiments is not essential relative to the complexity of the corresponding block. ru Видавничий дім "Академперіодика" НАН України Доповіді НАН України Інформатика та кібернетика Оценки сложности экспериментов с блоками управляемых перестановок Estimates of the complexity of experiments with controlled blocks of permutations Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Оценки сложности экспериментов с блоками управляемых перестановок |
| spellingShingle |
Оценки сложности экспериментов с блоками управляемых перестановок Скобелев, В.Г. Інформатика та кібернетика |
| title_short |
Оценки сложности экспериментов с блоками управляемых перестановок |
| title_full |
Оценки сложности экспериментов с блоками управляемых перестановок |
| title_fullStr |
Оценки сложности экспериментов с блоками управляемых перестановок |
| title_full_unstemmed |
Оценки сложности экспериментов с блоками управляемых перестановок |
| title_sort |
оценки сложности экспериментов с блоками управляемых перестановок |
| author |
Скобелев, В.Г. |
| author_facet |
Скобелев, В.Г. |
| topic |
Інформатика та кібернетика |
| topic_facet |
Інформатика та кібернетика |
| publishDate |
2011 |
| language |
Russian |
| container_title |
Доповіді НАН України |
| publisher |
Видавничий дім "Академперіодика" НАН України |
| format |
Article |
| title_alt |
Estimates of the complexity of experiments with controlled blocks of permutations |
| description |
Для базових типів блоків керованих перестановок (матричних, пошарових та рекурсивних) отримано асимптотичні оцінки складності експериментів, призначених для виявлення або локалізації поодиноких несправностей. Встановлено, що для матричних та рекурсивних блоків керованих перестановок складність цих експериментів не є істотною порівняно зі складністю самого блоку.
For basic types of controlled blocks of permutations (namely, matrix, stratum, and recursive ones), the asymptotic estimations of complexity of experiments intended to detect or to localize simple faults are established. It is shown that, for matrix and stratum controlled blocks of permutations, the complexity of above-mentioned experiments is not essential relative to the complexity of the corresponding block.
|
| issn |
1025-6415 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/37380 |
| citation_txt |
Оценки сложности экспериментов с блоками управляемых перестановок / В.Г. Скобелев // Доп. НАН України. — 2011. — № 4. — С. 41-43. — Бібліогр.: 5 назв. — рос. |
| work_keys_str_mv |
AT skobelevvg ocenkisložnostiéksperimentovsblokamiupravlâemyhperestanovok AT skobelevvg estimatesofthecomplexityofexperimentswithcontrolledblocksofpermutations |
| first_indexed |
2025-11-27T01:58:51Z |
| last_indexed |
2025-11-27T01:58:51Z |
| _version_ |
1850792423843692544 |
| fulltext |
УДК 519.17
© 2011
В.Г. Скобелев
Оценки сложности экспериментов с блоками
управляемых перестановок
(Представлено академиком НАН Украины А.А. Летичевским)
Для базових типiв блокiв керованих перестановок (матричних, пошарових та рекурсив-
них) отримано асимптотичнi оцiнки складностi експериментiв, призначених для ви-
явлення або локалiзацiї поодиноких несправностей. Встановлено, що для матричних та
рекурсивних блокiв керованих перестановок складнiсть цих експериментiв не є iстот-
ною порiвняно зi складнiстю самого блоку.
1. Представив семейство перестановок n-битовых последовательностей, используемое при
построении блочных шифров [1, 2], отображением f : En+m → En (E = {0, 1}; m ∈ N),
т. е. y = f(x,v), где x ∈ En — информационный, а v ∈ Em — управляющий вектор, получим,
что отображение gv0
: En → En (v0 ∈ Em), где gv0
(x) = f(x,v0), является перестановкой
компонент вектора x ∈ En. Комбинационная схема (КС) Sf, реализующая отображение f,
определена в [3] как блок управляемых перестановок (БУП). В [3] исследована скорость
функционирования основных типов БУП и осуществляемое ими рассеяние компонент ин-
формационного вектора, но не исследованы задачи обнаружения и локализации неисправ-
ностей. Последние должны быть решены стандартными методами технической диагности-
ки [4], но получаемые при этом тесты существенно сложнее оптимальных (так как в них не
учтены ни функциональные, ни структурные характеристики КС Sf). Оценим сложность
обнаружения и локализации неисправностей для основных типов БУП.
2. Пусть µ(C) — общее число ножек функционального элемента C. Определим слож-
ность КС Sf равенством µ(Sf) =
∑
µ(C), где сумма берется по всем функциональным
элементам КС Sf. Неисправностью КС Sf назовем одиночную неисправность ее функцио-
нального элемента (константную неисправность ножки или короткое замыкание двух сосе-
дних ножек), а тест представим матрицей, строки которой — вход-выходные пары эталона.
Пусть Ad и Al — минимальные тесты для обнаружения и локализации неисправностей КС
Sf. Положим µa(Sf) = (2n+m)αa (a ∈ {d, l}), где αa — число строк матрицы Aa. Величину
νa(Sf) = µ−1(Sf)µa(Sf) (a ∈ {d, l}) назовем сложностью обнаружения (a = d) и локализации
(a = l) неисправностей КС Sf.
3. Матричный БУП — это КС M (1)
n,m, содержащая дешифратор Dm с m входами и эле-
менты Pi (i = 1, . . . , 2m − 2), реализующие такие отображения hPi
: En × E → En, что
отображение fαPi
: En → En (α ∈ E), где fαPi
(x) = hPi
(x, α), при α = 1 осуществляет переста-
новку компонент вектора x ∈ En, а при α = 0 является тождественным отображением. При
этом: 1) для КС M (1)
n,m информационные входы — это информационные входы элемента P1,
управляющие входы — это входы дешифратора, а выходы — это 0-й и (2m − 1)-й выходы
дешифратора (используются только в процессе эксперимента), а также выходы элемента
P2m−2; 2) i-й выход (i = 1, . . . , 2m−2) дешифратора Dm подсоединен к управляющему входу
элемента Pi; 3) выходы элемента Pi (i = 1, . . . , 2m − 3) подсоединены к информационным
входам элемента Pi+1.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2011, №4 41
Положив f0Pi
(x) ≡ 0 (x ∈ En) для всех i = 1, . . . , 2m − 2 и изменив структуру КС M (1)
n,m
так, что ее информационные входы подсоединены к информационным входам каждого эле-
мента Pi (i = 1, . . . , 2m − 2), а выходы этих элементов через элемент ИЛИ подсоединены
к внешним выходам, получим КС M (2)
n,m, эквивалентную КС M (1)
n,m.
Представляет интерес и следующее изменение структуры КС M (1)
n,m. Удалив Dm и огра-
ничившись элементами Pi (i = 1, . . . ,m), подсоединим i-й управляющий вход КС к управ-
ляющему входу элемента Pi. Получим КС M (3)
n,m, реализующую семейство перестановок
fα1
P1
◦ · · · ◦ fαm
Pm
(α1, . . . , αm ∈ E), где ◦ — операция суперпозиции.
Анализ этих КС дает возможность доказать следующую теорему.
Теорема 1. Если m = O(n log n) (n → ∞), то для КС Sf ∈ {M (i)
n,m | i = 1, 2, 3} истинны
следующие асимптотические равенства:
νd(Sf) = O(log n) (n → ∞), (1)
νl(Sf) = O(n log n) (n → ∞). (2)
4. Послойный БУП — это КС Pn,m (n — четное число, m = 0,5n(k − 1) (k ∈ N)), со-
держащая элементы πi (i = 1, . . . , k) и m элементов δ. Элемент πi (i = 1, . . . , k) реализует
перестановку fi компонент вектора x ∈ En, а элемент δ — такое отображение g : E2×E → E2,
что g((α, β), 1) = (β, α) и g((α, β), 1) = (α, β) для всех (α, β) ∈ E2. При этом: 1) для КС Pn,m
информационные входы — это входы элемента π1, управляющие входы — это управляю-
щие входы всех элементов δ, а выходы — это выходы элемента πk; 2) выходы элемента πi
(i = 1, . . . , k − 1) разбиты на пары, каждая из которых подсоединена к информационным
входам соответствующего элемента δ; 3) выходы элементов δ, информационные входы кото-
рых соединены с выходами элемента πi (i = 1, . . . , k−1), подсоединены к соответствующим
входам элемента πi+1.
Анализ КС Pn,m дает возможность доказать следующую теорему.
Теорема 2. Для КС Pn,m истинны следующие асимптотические равенства
νd(Pn,m) = O(n) (n → ∞, k → ∞), (3)
νl(Pn,m) = O(µ2(Pn,m)) (n → ∞, k → ∞). (4)
5. Рекурсивный БУП — это 2-уровневая КС Rn (n = rs): 1-й уровень состоит из КС
W (i)
r = Zr (i = 1, . . . , s), а 2-й уровень — из КС Un, где Un и Zr — это БУП, соответствен-
но, n-элементных и r-элементных битовых последовательностей. При этом: 1) для КС Rn
информационные входы — это информационные входы КС W (i)
r (i = 1, . . . , s), управляю-
щие входы — это управляющие входы КС Un и W (i)
r (i = 1, . . . , s), а выходы — это выходы
КС Un; 2) выходы КС W (i)
r (i = 1, . . . , s) подсоединены к соответствующим информацион-
ным входам КС Un.
Такая структура рекурсивного БУП Rn дает возможность строить для него тесты в со-
ответствии со следующей схемой:
1) для каждого i = 1, . . . , s тестируем КС W (i)
r при находящихся в фиксированных
режимах КС Un и W (1)
r , . . . ,W (i−1)
r , W (i+1)
r , . . . ,W (s)
r ;
2) тестируем КС Un.
Отметим, что именно такая схема была применена в [5] при анализе сложности 2-уров-
невых и 3-уровневых сетей Клоса.
42 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2011, №4
Так как рассматриваются только одиночные неисправности БУП, то при такой схеме
тестирования для a ∈ {d, l} истинно следующее асимптотическое равенство:
µa(Rn) = O(sµa(Zr) + µa(Un)) (s → ∞, r → ∞).
Отсюда вытекает
Теорема 3. Если µ(Un) = O(sµ(Zr)) (s → ∞, r → ∞), то для a ∈ {d, l} истинно такое
асимптотическое равенство:
νa(Rn) = O(νa(Zr) + νa(Un)) (s → ∞, r → ∞). (5)
6. В заключение отметим следующее. Равенства (1), (4) и (5) показывают, что асимпто-
тическая сложность эксперимента, предназначенного для обнаружения или локализации
одиночных неисправностей в матричных и рекурсивных БУП, не является существенной
в сравнении со сложностью самой БУП. Выделение классов послойных БУП, обладающих
такими же характеристиками, представляет возможное направление исследований. Другое
направление состоит в более тонком анализе различных типов рекурсивных БУП, а третье
направление — в исследовании сложности экспериментов, предназначенных для обнаруже-
ния и локализации кратных неисправностей в основных типах БУП.
1. Menezis A., van Oorschot, Vanstone S. Handbook of applied cryptography. – New York: CRC Press, 1997. –
780 p.
2. Харин Ю.С., Берник В.И., Матвеев Г. В. и др. Математические и компьютерные основы криптоло-
гии. – Минск: Новое знание, 2003. – 382 с.
3. Молдовян А.А., Молдовян Н.А., Гуц Н.Д. и др. Криптография: скоростные шифры. – Ст.-Петербург:
БХВ-Петербург, 2002. – 496 с.
4. Пархоменко П.П. Основы технической диагностики. – Москва: Энергия, 1981. – 320 с.
5. Скобелев В.В., Скобелев В. Г. Анализ шифрсистем. – Донецк: Изд-во Ин-та прикл. механ. и матем.
НАН Украины, 2009. – 479 с.
Поступило в редакцию 17.06.2010Институт прикладной механики
и математики НАН Украины, Донецк
V.G. Skobelev
Estimates of the complexity of experiments with controlled blocks of
permutations
For basic types of controlled blocks of permutations (namely, matrix, stratum, and recursive ones),
the asymptotic estimations of complexity of experiments intended to detect or to localize simple
faults are established. It is shown that, for matrix and stratum controlled blocks of permutations,
the complexity of above-mentioned experiments is not essential relative to the complexity of the
corresponding block.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2011, №4 43
|