Економіко–математичне моделювання (стр. 16 из 17)

Справедлива

Теорема 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). Застосовуючи аналогічні міркування, маємо:

Тоді:

і остаточно: