Содержание
Введение 3
1. Основные теоретические положения 5
1.1. Спектральное представление булевых функций 7
1.2. Характеристики булевых функций 10
2. Применение спектрального анализа булевых функций 13
2.1. Анализ и синтез дискретных устройств 13
2.2. Криптография 18
Выводы 22
Список литературы 24
Выдержка из текста
Спектральный анализ широко используется в математике, информатике, технике. Примером служат обработка сигналов, сжатие данных, быстрое умножение многочленов, квантовые вычисления, и т. д. Сигнал или функция представляются в виде суммы периодических функций, таких как , или (в вещественном случае) синусов и косинусов.
При исследовании булевых функций, однако, более естественным будет использование преобразования в каком-либо кусочно-постоянном базисе. Возможность характеризовать булевы функции (БФ) с помощью некоторого набора вещественных чисел впервые была отмечена в работе [1]. Впоследствии в [2] булевы функции представлялись в виде конечных сумм функций Уолша в задачах синтеза логических сетей на пороговых элементах.
Список использованной литературы
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 с.