Економіко – математичне моделювання

      Теорема 2. Хай  , ε>0 за системою Уолша, тоді існує постійна С>0, така, що для будь-кого натурального р = 2ⁿ і будь-якого полінома:

      

      справедлива нерівність:

       (12)

      Назад, якщо для послідовності {n_k} існує постійна С > 0, така, що для будь-кого натурального р = 2ⁿ і будь-якого полінома:

      

      справедлива оцінка (12), то послідовність  для будь-кого ρ, .

      Доведення. Доведемо спочатку необхідність.

      Хай:

      

      

      Утворюємо множину:

      

      Хай далі:

      

      Оцінимо , тоді:

          (13)

      Помітимо  тепер, що на інтервалі цифри х в двійковому розкладанні до номера n співпадають з відповідними цифрами у числа , якщо не допускати в двійковому розкладанні нескінченних послідовностей одиниць.

      Хай:

      

      Тоді, як відомо:

      

      якщо  Тому:

      

      і в силу (13):

       (14)

      Якщо  у визначенні функції f(х) покласти:

      

      то  нерівності (13) і (14) звернуться в рівність.

      Для такої функції маємо в силу (14) і умови теореми:

      

      звідки:

      

      або:

      

      що  і доводить необхідність теореми.

      Доведемо  тепер достатність. Хай для послідовності {n_k} справедлива нерівність (12) при будь-кому р=2ⁿ і поліномі:

      

      або

      

      Тоді  для полінома:

      

      і множини:

      

      

      

      справедлива оцінка (14), тобто:

       (15)

      Через умову теореми права частина  нерівності (15) не перевершує величини:

      

      тобто:

       (16)

      Оцінка (16), будучи справедлива для простих  множин Е з умовою , розповсюджується для фіксованого полінома f(х) і на довільні вимірювання множини , а, отже, і на довільні функції

       з умовою . Через лему нерівність (16) тягне за собою

      умова при всіх , тобто при

      всіх  .

      Теорема повністю доведена.

      Наступні  два кількісні результати торкаються густини лакунарних послідовностей Уолша і розподілу значень  іденпотентних поліномів (терезів  лінійних кодів). Ці оцінки представляють  як самостійний інтерес (перша з них значно усилює аналогічний результат А. Бонами так і можуть мати додаток в загальній математичній теорії кодування Л передачі інформації.

      Теорема 3. Хай Е_n n-мірне лінійний простір над полем з двох елементів. - пряма сума двох екземплярів цього простору, яке ми потрактуємо так само, як безліч всіх пар (а, b), де а, b – елементи Е_n.

      Тоді  безліч U всіх пар вигляду (а, а^-1), де і символом а^-1 позначений елемент, зворотний до елемента а в полі Е_n має потужність 2ⁿ-1, лежить в лінійному просторі W_2n потужності 2²ⁿ. Іншими словами, множина U є щільним B₂ (або (4)) множиною в тому значенні, що на ньому досягається верхня грань густини В3-последовательностей.

      Доведення. Допустимо осоружне, тоді знайдуться такі 4 різний елемента а, b, c, d з U, що:

      

      Остання система еквівалентна системі:

      а + b = c + d,    a^-l + b^-1 = с^-1 + d^-1.

        що рівносильне:

      а + b = c + d,    ab = cd

      яка, як неважко бачити, може мати не більше одного рішення (з точністю до перестановки). Дійсно, останнє твердження рівносильне  тверждення про те, що рівняння х(х + k) = r має не більше двох різних розв’язків по х для х, k, r з Е_n. Покажемо це. Хай є інше рішення у: у(у + k) =r.

      Тоді , звідки , тобто , звідки або x = у, або у = х + k ( нагадаємо, що E_n - поле характеристики 2).Тим самим теорема 3 повністю доведена.

      Справедлива

      Теорема 4. Хай на E_n заданий ідемпотентний поліном Уолша:

      

      Хай з E_n такі, що все r_j, незалежні і , . Тоді:

      

      де

      

      Доказ. Без обмеження спільності можна  вважати, що все {r_j} утворюють стандартний базис в Е_t (загальний випадок зводиться до цього лінійним перетворенням E_t). Тоді на підпросторі E_t, поліном R(x) запишеться у вигляді:

      

      де  d_j, - цілі ненегативні числа, в сумі даючі s. Легко бачити, що шукана сума квадратів значень полінома R(x) на підпросторі Е_t, рівна .

      Оцінимо знизу суму . Оскільки значення полінома R(x) на векторах E_t

      рівні άs, те, як вже наголошувалося, ідемпотентному поліному R(x) на підпросторі Е, відповідатиме  двійковий код з 2^t стовпців і із загальним числом кодових слів 2^t, причому базисні кодові слова складаються з ,одиниць

      і мінус одиниць в мультиплікативному записі двійкового коду.

      Ми  маємо у результаті г випадкових величин, розподілених по одному і тому ж

      закону - вони приймають два значення з  ймовірностями  відповідно і мають ентропію Н_ά кожна. Крім того, ці випадкові величини утворюють багатовимірний розподіл з вірогідністю По властивості субадитивності ентропії маємо:

      

      Застосовуючи  відому нерівність Юнга:

      

      

      маємо:

      

      або:

      

      або:

      

      Остаточно:

      

      що  і доводить теорему 4.

      Структура виняткової безлічі індексів, які забезпечують >квв валентність метрик Мінковського, тісно примикає до задач побудови і вивчення лінійних кодів.

      Під кріптологією в широкому значенні розуміється  мистецтво проектуванні і злому  секретних систем, при цьому проектування називається криптографією а зламуюча частина - кріптоаналізом. При цьому треба мати у вигляді, що є багато кодів, жодним чином не пов'язаних з проблемою секретності, - це код ASCII для перетворення символів алфавіту в двійкову форму для з'явившися лінія в ЕОМ, а також універсальний промисловий код (штриховий) з ряд чорних вертикальних ліній, що містять інформацію про вироби. Історично перший код, призначений для передачі повідомлень, пов'язаний з ім'ям винахідника телеграфного апарату Семюеля Морзе і відомий всім як азбука Морзе. Код Морзе заснований на короткочасних (крапка) і тривалих (тире) їм пульсах струму; інший код (Бодо) для кодування використовує два елементарні сигнали - імпульс і паузу. Зручно, відволікаючись від фізичної природи сигналів, позначати два елементарні сигнали символами 0 і 1, тоді кодові слів представляються послідовністю нулів і одиниць.

      При передачі повідомлення в умовах перешкод основна помилка пов'язана з  тим, чий ряд символів може бути переданий  неправильно, тобто Про замість і навпаки. Для того, щоб можна було однозначно декодувати повідомлення, слід накласти додаткові умови на сам спосіб кодування повідомлень, тобто на код. Є слова а₁, а₂,..., а_n повинні бути декодовані як b₁, b₂ ..., b_n, але передане слів декодувалося в деяке слово b, не співпадаюче ні з одним з b_i то приписати слову b „найближче” із слів b₁, b₂..., b_n. Основна задача, виникаюча на цьому шляху така: який повинен бути код з n символів, щоб він правильно декодував передане слово, при умові, якщо вчинено не більш t - помилок в передачі? Легко показати, що, якщо слова коду відстоять один від одного на віддаль Хемінга, не менше ніж 2t + 1, то така задача розв'язується однозначно по кодуванню в найближче слово. Дійсно, якщо передане слово відстоїть від двох різних кодових слів на відстані, не перевершуючі t( тобто при передачі його зроблено не більш t помилок по відношенню до цих двох слів), то по формулі трикутника самі ці кодові слова відстоять один від одного на відстань, що не перевершує 2t, в суперечності з початковою властивістю коду мати всі свої слова на відстані не меншому 2t + 1 один від одного. Таким чином, для упевненого декодування в умовах перешкод потрібно уміти будувати коди з великою кодовою відстанню, яка визначається як мінімум попарних відстаней слів коду в метриці Хемінга. Оскільки безліч всіх слів довжини п цією властивістю, очевидно, не володіє, слід виділяти деякі підмножини з вказаної множини. Звичайно безліч всіх послідовностей з 0 і 1 довжини n вважають лінійним простором над полем з двох елементів з метрикою (нормою) Хемінга; число одиниць в слові називають нормою цього слова. Серед таких підмножин особливе місце займають коди, які замкнуті по відношенню до операції суми, так звані лінійні коди. Лінійний (n, k) - код є лінійний підпростір розмірності до в множині всі 0-1 рядків довжини п, тобто в просторі Е_n. При цьому матриця з до базисних векторів коду називається матрицею коду, що породжує, а матриця з n-k базисних векторів подвійного коду (тобто ортогонального доповнення до E_n) називається перевірочною матрицею. Природно вважати до символів (n, k) - коду основними, а інші n-k- перевірочними, необхідними лише для визначення правильності передаючого повідомлення. Величинами називається швидкістю передачі.

      Як  багато може бути кодових слів в коді довжини n, у якого кодова відстань d, тобто яка величина А(n,d)? Відомі межі Хемінга, Джонсона, оцінюючі величину А(n,d). Так, межа Хемінга встановлює:

      

      де

       (17)

      Ця  межа ще називається межею сферичної  упаковки, оскільки рівність (17) Досягається у тому випадку, коли непересічні кулі радіусу t з центрами кодових словах цілком заповнюють всю безліч n - буквенних слів. Такі коди ще називаються вчиненими або щільно упакованими.

      Межа  Джонсона А(n,d) 2d/(2d - n), d> n/2 може бути використана для оцінки потужності коду, що складається із слів ваги Лисиць кодовою відстанню d. га оцінка А(n,k,d) d/(2n²+dn-2nk), за умови, що знаменник дробу позитивний, 2n²+dn-2nk>0. Оцінки типу межі Джонсона неодноразово уточнювалися різними авторами, оскільки остаточного результату до теперішнього часу не одержано. Такі оцінки мають значення при побудові кодів з сильними коректуючими властивостями, оскільки указують межі можливого. Наступна оцінка уточняє оцінку Джонсона.

      Теорема 5. Хай задані t слів довжини s ваги L= s(l-ά)/2, де ά (0,1). Нехай

      D={d_i}, безліч попарних відстаней між кодовими словами. Хай середнє арифметичне всіх попарних відстаней між перерахованими t словами. Тоді:

      

      Доведення.

      Хай в матриці коду h_i, - число одиниць в і-ому стовпці.

      Тоді

      

      і, отже

      

      Якщо

      

      Застосуємо  тепер ці міркування до нового коду, який виходить з виходящого попарним складанням різних стовпців. Тоді рядки нового коли матимуть вагу L(s - L), попарні відстані нового коду будуть d_i(s - d_i). Застосовуючи аналогічні міркування, маємо:

      

      Тоді:

      

      

      і остаточно:

      

      

      Якщо  , то: