Так как для линейных систем уравнений имеются достаточно эффективные методы их решения, то при анализе спецаппаратуры зачастую стремятся использовать линейные статистические аналоги.

42. Понятие статистической структуры двоичной функции.

4) Статистическая структура двоичной функции.

Определим для функции f(x) и линейной функции параметр исходя из равенства .

Определение. Набор чисел называется статистической структурой двоичной функции f(x).

Набор чисел показывает насколько отличаются от ½ вероятности совпадения значений функции со значениями линейных функций (a,x) , .

Выведем формулу для вычисления коэффициентов статистической структуры. Имеем

= .

Отсюда , .

43. Доказательство связей значений коэффициентов Фурье двоичной функции со значениями ее статистической структуры.

5) Связь коэффициентов Фурье двоичной функции со значениями её статистической структуры.

По определению коэффициетов Фурье двоичной функции при а=0 имеем .

При .

С другой стороны

Сравнивая окончательные выражения для правых частей равенств получаем при и .

Используя эти равенства и представление двоичной функции в виде ряда Фурье получаем представление двоичной функции через коэффициенты ее статистической структуры:

Так как коэффициенты Фурье однозначно определяют двоичную функцию, то и статистическая структура однозначно определяет двоичную функцию.

44. Методы вычисления статистической структуры двоичной функции.

6) Методы вычисления статистической структуры двоичной функции.

Способ вычисления коэффициентов статистической структуры двоичной функции, основанный на формуле , является достаточно трудоемким. Для каждого коэффициента (их всего ) необходимо найти вес функции т.е. сначала провести сложение функций, а затем подсчитать сумму слагаемых). Поэтому трудоемкость

этого способа оценивается величиной слагаемых операций сложения.

Более эффективный способ основан на использовании связей статиистической структуры функции со статистическими структурами ее подфункций (такой способ использует, так называемое, быстрое преобразование Фурье). Имеем

.

Для удобства полагаем

.

При введенных обозначениях имеет место

45. Доказательство теоремы о связи статистической структуры двоичной функции со статистическими структурами ее подфункций

Утверждение. (О связи статистической структуры функции со статистическими структурами ее подфункций). Коэффициенты статистических структур двоичной функции и ее подфункциий и связаны соотношениями ; .

Доказательство.

случай , т.е. . В этом случае имеем

случай , т.е. . Имеем

Утверждение полностью доказано.

Данное утверждение позволяет вычислять статистическую структуру функции исходя из статистических структур подфункций = и = по следующему правилу. Если

,

то статистическая структура функции равна

Для вычисления статистических структур функций и в свою очередь, используют разложения

и т.д.

Продолжая этот процесс доходят до функций от одной переменной вида

Статистические структуры таких функций легко считаются, их значения приведены в таблице

Изложенный способ определения коэффициентов статистической структуры двоичной функции от n переменных выполняется за n шагов, в каждом из кото- рых приходится вычислять значений коэффициентов статистических структур. Поэтому оценка трудоёмкости данного способа имеет вид в операциях сложения и вычитания.

Понятие К-равновероятности двоичной функции.

46. Понятие К-равновероятности двоичной функции.

Определение: Двоичная функция называется к - равновероятной, , если все её подфункции, полученные фиксацией произвольных к переменных произвольными константами, равновероятны.

Обозначим классы всех равновероятных и к - равновероятных двоичных функций от n переменных через R(n)=R(n,0) и R(n,k),

Докажите самостоятельно справедливость следующих включений:

Данное утверждение показывает, что к - равновероятная функция остается равновероятной при фиксации произвольных m, m<K, переменных.

47. Формулировка критерия К-равновероятности двоичной функции (связь с коэффициентами стат. структуры). Доказательстсво необходимости условий.

48. Формулировка критерия К-равновероятности двоичной функции (связь с коэффициентами стат. структуры). Доказательство достаточности условий.

Теорема. (Критерий к - равновероятности функций). Двоичная функция является к - равновероятной, в том и только в том случае, когда ее коэффициенты статистической структуры при равны нулю ( -число единиц в наборе a).

Доказательство. Пусть функция f(x) к - равновероятна. Тогда при , , коэффициент равен ;

.

Так как к - равноверояная функция является и m- равновероятной, m<к, то по доказанному и =0 при , m<K.

Пусть теперь =0 при всех а с условием .

Рассмотрим сначала случай к=1. Для любого имеем при а=0. Следовательно

или

Откуда

Пусть теперь при . Воспользуемся индукцией по к.

Согласно утверждению о связи статистической структуры функции со статистическими структурами её подфункций (см. п.6) имеем

Следовательно при всех . Пользуясь предположением индукции заключаем, что

Поскольку такое разложение можно проделать для любой переменной, отличной от , то получаем, что все подфункции и являются (к-1)- равновероятными. Следовательно, функция f(x) к - равновероятна.

Данная теорема показывает, что к - равновероятные функции не имеют линейных аналогов, зависящих не более, чем от к переменных. Приведём более сильное утверждение о том, что к - равновероятные функции не имеют статистических аналогов среди всех двоичных функций, зависящих не более, чем от к переменных. Такие функции называются к - устойчивыми.

Теорема. (Критерий к - равновероятности функций). Двоичная функция к - равновероятна в том и только в том случае, когда она к- устойчива.

Доказательство. к - устойчивая функция не имеет в том числе и линейных аналогов, зависящих не более чем от к переменных.

Обратно, пусть функция к - равновероятна. Тогда

что и требовалось доказать.

Теорема. (О связи к - равновероятных и к - выравнивающих функций).

Если двоичная функция к - равновероятна, то она (к+1)- выравнивающая.

Доказательство. Пусть – вероятностная функция функции . По утверждению о совпадении многочленов и (см. п. 3) имеем

где действительный многочлен функции . Положим , и покажем, что в многочлене от переменных не содержится одночленов степеней , . Разложим многочлен по первым переменным:

где

Многочлены являются вероятностными функциями подфункций . Так как у к - равновероятных функций все такие подфункции равновероятны, то

где многочлен имеет нулевой свободный член. Поэтому

После раскрытия скобок и приведения подобных членов в последней сумме все одночлены будут зависить обязательно хотя бы от одной из переменных . Следовательно в многочлене нет ни одного одночлена, зависящего только от переменных . Рассуждая аналогично, получаем, что в нем нет вообще одночленов степеней меньших, либо равных . Таким образом рассматриваемая функция является – выравнивающая.

Способы задания двоичных функций

8) Способы задания двоичных функций. Будем рассматривать двоичные функции как функции заданные на множестве и принимающие значения в некотором поле ,понимая и из как нулевой и единичный элементы поля . Функции такого вида называют – булевыми (если или , то функции называют псевдобулевыми).

Пусть вектор – столбец значений функции при лексикографическом упорядочении наборов аргументов. Множество функций таким образом можно рассматривать как векторное пространство размерности . Столбцы любой обратимой матрицы размера можно рассматривать как базис двоичных векторов – столбцов (двоичных функций). Пронумеруем столбцы любой обратимой матрицы (над полем ) размера векторами в лексикографическом порядке. Если двоичная матрица размера и ее столбцы, образующие базис пространства двоичных функций, то любую двоичную функцию (вектор – столбец) можно представить линейной комбинацией столбцов матрицы .

где вектор – столбец (двоичная функция). Таким образом задание двоичной функции может быть осуществлено заданием коэффициентов (вектор ) в разложении функции относительно базисных двоичных функций .