обзор методов СА БФ. Обзор методов спектрального анализа булевых функций

• Название: Обзор методов спектрального анализа булевых функций
• Дата: 29.09.2022
• Размер: 0.64 Mb.
• Имя файла: обзор методов СА БФ.doc
• Тип: Обзор; #705615
• страница: 2 из 2

Сначала перейдем от булевой функции к ее знаковой [21] функции:

1 1 0 1 = 1 1 -1 1

Тогда спектр Уолша функции импликации таков.
; ; ; .
Поскольку , функция не является сбалансированной. В нашем случае этот факт легко зафиксировать, анализируя таблицу истинности: количество 0 и 1 в ней не совпадают.

Поскольку для спектра заданной функции не выполняется соотношение 2.4, то она является нелинейной.

Для проверки представим функцию импликации в виде полинома Жегалкина.











Окончательно , то есть является нелинейной, максимально возможной степени 2.

Функция импликацииявляется бент-функцией, поскольку модуль ее спектра Уолша постоянен и равен для всех .

Для функций двух переменных расстояние до аффинных структур составляет (n=2) .

По теореме Massey-Xiao функция является корреляционно иммунной порядка m, если и только если для всех наборов переменных ω с весом Хемминга, меньшим или равным m. В нашем случае вообще отсутствуют нулевые коэффициенты Уолша, поэтому функция не является корреляционно иммунной.

Проверим функцию, удовлетворяет ли она строгому лавинному критерию. Для этого найдем булеву производную [21] от исходной функции.

№
1	00	1	01	0	10	1
2	01	1	00	0	11	0
3	10	0	11	1	00	1
4	11	1	10	1	01	0

Очевидно, что первая булева производная является равновероятной для всех , для которых . Значит, строгий лавинный критерий (SAC) выполнен.

Одновременно проверено выполнение и критерия распространения степени 1 – производные по обоим направлениям равновероятны.
Выводы

Классические методы характеризуются тем, что они позволяют, вообще говоря, получать опти­мальные решения в смысле сложности синтезируемой схемы. Однако при использовании классических мето­дов такие важнейшие задачи, возникающие в процессе синтеза, как минимизация систем БФ, оптимальное ко­дирование состояний и входных сигналов автомата, оп­тимальное доопределение частичных БФ и частичных автоматов и т. д. требуют для своего решения перебора вариантов. Причем необходимость перебора носит для таких задач, по-видимому, принципиальный характер. Объем требуемого перебора при этом растет чрез­вычайно быстро с ростом числа аргументов БФ или со­стояний и входных сигналов автомата.

В связи с этим возникает необходи­мость в методах синтеза, слабо зависящих от конкретных особенностей базисной системы элементов и удобных при синтезе на интегральных схемах, а также, в методах синтеза схем с переменной структурой и схем, адапти­рующихся к изменениям среды, в которой они функцио­нируют.

Наконец, весьма важными и актуальными требова­ниями к методам синтеза являются требования возмож­ности проектирования устройств, обладающих эффек­тивными средствами самоконтроля и самокоррекции ошибок.

Спектральные методы синтеза в значительной сте­пени удовлетворяют рассмотренным требованиям. Ос­новным недостатком спектральных методов является то, что они являются приближенными, т. е. не обеспечи­вают абсолютную минимальность получаемых схемных решений.

Однако эти методы обладают рядом преимуществ. Во-первых, спектральные методы синтеза удобны для реали­зации их на ЭВМ и позволяют решать задачи достаточно высокой размерности, так как структура устройства зафиксирована. Кроме того, при использовании спек­тральных методов легко оценить сложность синтезируе­мой схемы по числу ненулевых коэффициентов соответст­вующего ряда, что, в свою очередь, дает возможность просто оценить ожидаемую сложность схемы по числу требуемых для ее реализации элементов.

С другой стороны, важным достоинством спектраль­ных методов является их весьма слабая зависимость от базисной системы элементов.

Еще одним достоинством спектральных методов, осо­бенно в случае синтеза комбинационных устройств, яв­ляется то обстоятельство, что эти методы слабо зависят от числа функций, реализуемых устройством и от числа устойчивых состояний элементов, на которых синтези­руется устройство.

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

Список литературы

1. 
   Golomb S. W. On the Classification of Boolean Function/ IRE Trans/ on Circuit Theor., ст. 6, 1958, pp. 176-186.
   
2. 
   Карповский М. Г., Москалев Э. С. Спектральные методы анализа и синтеза диск­ретных устройств. – Л.: «Энергия», 1973. – 144с.
   
3. 
   M. G. Karpovsky, R. Stankovic, J. Astola. Spectral logic and its applications for the design of digital devices. John Wiley & Sons, Inc., Hoboken, New Jersey, 2008. – 633с.
   
4. 
   Логачёв О. А., Сальников А. А., Ященко В. В. Булевы функции в теории кодирования и криптологии. – М.: МЦНМО, 2004. – 470 с.
   
5. 
   Лабунец В.Г., Ситников О.П. Гармонический анализ булевых функций и функций k-значной логики над конечными полями. – Изв. АН СССР, сер. Техническая кибернетика, 1975, № 1, - c.142-149.
   
6. 
   Ryan O'Donnell. Some Topics in Analysis of Boolean Functions. – In:
   STOC '08 Proceedings of the fortieth annual ACM symposium on Theory of computing. Pp. 569-578  ACM New York, NY, USA ©2008 
   
7. 
   Ивченко, Г. И. Некоторые вопросы спектрального анализа случайных булевых функций с ограничениями / Г. И. Ивченко, В. А. Миронова // Дискретная математика. – 2013. – Т. 25, вып. 1. – С. 90-110.
   
8. 
   Constanza Riera. Spectral Properties of Boolean Functions. Graphs and Graph States December 9, 2005 (файл pdf)
   
9. 
   Кочкарев Ю. А. Ортогональные сигналы в вычислительной технике, Ростовского ун-та. – Ростов-на-Дону. – 1980. – 191 с.
   
10. 
    P. Gopalan, R. O'Dormell, R. Servedio, A. Shpilka, and K. Wimmer. Testing Fourier dimensionality and sparsity. SIAM Journal on Computing, 40(4):1075-1100, 2011.
    
11. 
    Калинин Т. С. Спектрально-сигнатурная диагностика микропроцессорных информационно-управляющих систем железнодорожной автоматики и телемеханики/ Инженерный вестник Дона, вып. № 1/ т. 19/ 2012. c. 370-378.
    
12. 
    Чернов А.В. Модели и методы логико-алгебраического анализа и синтеза в задачах технической диагностики информационных систем. Автореф. дисс. на соиск. уч.степ. д.т.н. Ростов н/Д. Изд-во РГУПС, 2009. – 36с.
    
13. 
    Чернов А. В., Сергеева Е.А. Автокорреляционное тестирование цифровых комбинационных схем // Современные проблемы науки и образования. – 2013. – № 6; URL: www.science-education.ru/113-11526 (дата обращения: 03.02.2015).
    
14. 
    Чернов А.В. Спектральные преобразования дискретных функций для вычисления логических производных / Чернов А.В., Калинин Т.С. // Обозрение прикладной и промышленной математики. – 2010. – Т.17, №6. – С. 1049-1051.
    
15. 
    Bennetts R.G., Hurst S.L. Rademacher-Walsh spectral transform: a new tool for prob­lems in digital-network fault diagnosis// Computers and Digital Techniques, vol.1, no. 2, 1978.
    
16. 
    Гуда А.Н. Алгоритмы спектральных и символьных преобразований булевых функций для решения задач анализа и проектирования технологически безопасных информационных систем // Гуда А.Н., Чернов А.В.// Вестник Ростовского государственного университета путей сообщения. – 2008. – №2. – С. 46-53.
    
17. 
    Savir J. Syndrome-testable design of combinational circuits / Savir J. // IEEE Trans. Comput. – 1980. – C-29. – pp. 442-451.
    
18. 
    Tarannikov Y., Autocorrelation coefficients and correlation immunity of Boolean functions/ Korolev P., Botev A.// Advances in Cryptology ASIACRYPT – 2001, Lecture Notes in Computer Science 2248. – Springer-Verlag. – pp. 460-480.
    
19. 
    Amir Shpilka, Ben lee Volk. On the Structure of Boolean Functions with Small Spectral Norm. (файл pdf)
    
20. 
    Кочкарев Ю.А., Бурмистров С. В., Панаско Е. Н. Метод реализации булевых функций с помощью ортогональных подинтервалов. – Biсник ЧДТУ, 2013, №2, с.33-39.
    
21. 
    Агафонова И. В. Криптографические свойства нелинейных булевых функций. В кн.: Избранные главы дискретного гармонического анализа и геометрического моделирования. Под ред. проф. В. И. Малозёмова. СПб, 2009. – с. 265-280.
    
22. 
    Anne Canteaul and Marion Videau. Symmetric Boolean Functions//. IEEE transactions on information theory. VOL. 51. No. 8. August 2005.
    
23. 
    Claude Carlet, Andrew Klapper. On the Arithmetic Walsh Coefficients of Boolean Functions p. 22.: .pdf-file
    
24. 
    B. Falkowski, Ingo Schafer, M. Perkowski. Calculation of the Rademacher-Walsh spectrum from a reduced representation of boolean functions. pp.181-186.
    
25. 
    Xiao Guo-Zhen, James Massey. A Spectral Characterization of Correlation-Immune Combining Functions, IEEE transactions on information theory, Vol. 34, No. 3, May 1988, pp.569-571
    
26. 
    M. Mitton, On maximally non linear and extremal balanced Boolean functions, Jour. Discr. Maths. Sciences & Crypto., Vol. 5 (3) (December 2002), pp.231-253.
    
27. 
    С. Орлова. Методика оценки эффективности поточных шифров. Правове, нормативне та метрологічне забезпечення системи захисту інформації в Україні, вип. 9, 2004. с.141-152.
    
28. 
    Юдачев С.С. Последовательности на основе бент-функций для широкополосных систем с кодовым разделением каналов. Электронный научно-технический журнал Инженерный Вестник, 77-48211/529235, № 01 январь 2013 г., с.531-540.
    
29. 
    Мухачев В.А., Хорошко В.А. Методы практической криптографии. – К.: ООО «Полиграф-Консалтинг», 2005. – 215 с.
    

30. 
    Токарева Н. Н. Симметричная криптография. Краткий курс: учебное пособие/ Новосиб. гос. ун-т. Новосибирск. 2012. – 234 с.