Спосіб декодування псевдовипадкового завадостійкого коду на основі використання методу гілок і меж

Реферат: UA 118097 U UA 118097 U 5 10 15 20 25 30 35 40 Корисна модель належить до області завадостійкого кодування і реалізує можливість практичного застосування псевдовипадкових кодів в сучасних системах передачі інформації, оскільки дозволяє знизити обчислювальну складність, і може бути використана в системах стільникового зв'язку 5G. Близьким за технічною суттю (аналогом) до запропонованої корисної моделі є спосіб для декодування рекурентної послідовності [1], який може бути використано лише для декодування циклічних кодів у поєднанні з чотирипозиційним двійковим каналом. Суть даного способуаналога полягає у реалізації послідовних перевірок символів слів коду з використанням системи логічних рівнянь та нелінійної операції обчислення за модулем, при цьому рішення здійснюється за мажоритарним принципом, що дає результат (з точки зору вірності рішень) суттєво гірший, ніж результат, який отримують при використанні методу максимальної правдоподібності. Недоліки аналога - низькі функціональні можливості, низька завадозахищеність та висока обчислювальна складність декодування. Найбільш близьким за технічною суттю (прототипом) до запланованого способу є спосіб декодування псевдовипадкового завадостійкого коду, що полягає у послідовному порівнянні прийнятого кодового слова зі всіма кодовими словами кодової книги та прийнятті рішення на основі використання правила максимальної правдоподібності [2]. Суть даного способу-прототипу полягає у порівнянні, прийнятого сигналу випадкової вибірки, спотвореного завадою, з кожною вибіркою в еталонній кодовій книзі, котра зберігається на приймальній стороні. Таким чином, вибірка, яка має найменше середньоквадратичне відхилення від прийнятого сигналу, приймається за переданий сигнал, по якому відновлюється відповідне двійкове число. Отже, обчислювальна складність способу-прототипу зростає експоненційно з довжиною блока коду. Це не дає можливості обчислювальної реалізації блокового псевдовипадкового завадостійкого кодування при використанні блоків практично необхідної довжини. Недолік прототипу - висока обчислювальна складність декодування. Технічним завданням запропонованої корисної моделі є зменшення обчислювальної складності за рахунок проведення лінеаризації задачі декодування, формулювання задачі цілочисельного лінійного програмування та вирішення її за допомогою модифікованого методу гілок і меж для спрямованого пошуку оптимального рішення на основі введення пріоритетного порядку перегляду змінних, котрі використовують для лінеаризації операції обчислення за модулем. Спосіб декодування псевдовипадкового завадостійкого коду (ПВК) призначено для організації обчислювально ефективної технології декодування псевдовипадкових числових кодів, символи яких отримуються за методом лінійної конгруентної генерації [3]. З метою повного розкриття суті корисної моделі необхідно стисло охарактеризувати клас псевдовипадкових кодів, для декодування яких призначено об'єкт даної розробки. У загальному вигляді процедура кодування інформації ПВК, спосіб декодування якого є предметом запропонованої корисної моделі, зводиться до наступного. Загальний потік двійкових символів джерела, призначений для передачі, розбивається на блоки по k - біт для побудови блокового завадостійкого коду. При цьому кожна комбінація з k двійкових символів джерела трактується, як десяткова кількісна величина x 0 - порядковий номер, який визначає подальшу відповідну послідовність псевдовипадкових чисел x1, x 2 ,, x n1 , тобто x 0 - є породжуючим числом  45 50 55     кодового слова X j  x j , x j ,, x j з відповідним номером j  x j , j  0, , 2k  1 . Таким 0 0 1 n1 чином, кожному блоку з k двійкових символів джерела ставиться у відповідність блок з n недвійкових чисел коду. Числа кодових слів, визначають інформативні параметри сигналу, наприклад амплітуди квадратурних компонент піднесуючих частот [4]. Величина R  k / n (1) є швидкістю завадостійкого коду та показує співвідношення кількості інформаційних двійкових символів повідомлення до кількості недвійкових символів коду, призначених для передачі по каналу зв'язку. Оскільки довжина кодового слова ПВКn, фактично, може вибиратись незалежно від довжини вихідного блока двійкових символів k , то швидкість коду (1) може бути як більше, так і менше одиниці. При передачі кодового слова по каналу з перешкодами недвійкові числа слова використовуються (при необхідності - після відповідного масштабування) для модуляції інформативного параметра багаторівневого сигналу, наприклад амплітуди, частоти, фази або їх композиції. На виході каналу після впливу шуму на послідовність X j маємо 1 UA 118097 U  5 10   20 n1  x q j* q 0 30  x 0 j*  x 0i   x 2 1 j*  x1i  2     x1n j*  x1n i  2 , де i  0  2k  1 . Таким чином, обчислювальна складність таких способів декодування зростає експоненційно з довжиною блока коду n . Отже, для практичного застосування ПВК необхідно розробити спосіб декодування, обчислювальна складність якого буде не вище поліноміальної від довжини блока n . Для забезпечення можливості вирішення даної проблеми декодування, при побудові ПВК (кодуванні інформації) застосовують обчислення символів кодових слів за рекурентним правилом лінійної конгруентної генерації, що дає змогу лінеаризувати задачу декодування ПВК та суттєво зменшити обчислювальну складність, через заміну обчислення Евклідової відстані, асимптотично тотожним за кінцевим результатом правилом найменших проекцій min 25  значення довжини різницевого вектора (Евклідової відстані між точками X j * і X i n - вимірного простору коду) min X j *  X i  15   X*  X j    x j 0   0 , x j1  1,, x j n1  n1  x * 0 , x *1,, x * n1 , j де    0 , 1,, n1 - вектор шуму. Коди, що розглядаються, якщо пропускна здатність каналу не перевищена, дозволяють забезпечити як завгодно малу ймовірність декодування з помилкою на блок коду при простому збільшенні довжини блока n . Варто зауважити, що на сьогодні псевдовипадкові коди не мають практичного застосування в системах передачі інформації, оскільки декодування таких кодів ґрунтується на реалізації правила максимальної правдоподібності і можливе лише при посимвольному порівнянні, отриманого канального слова з усіма можливими варіантами, котрі зберігаються в приймачі. Тобто процедура декодування зводиться до пошуку мінімального     x q i , де i  0  2 k  1 . Для вирішення проблеми простого декодування таких кодів пропонують об'єкт даної корисної моделі - спосіб декодування ПВК на основі модифікованого методу гілок і меж, який забезпечує обчислювальну складність не вище поліноміальної від довжини блока n . Згідно з алгоритмом побудови ПВК, кожне наступне число псевдовипадкової послідовності довільного j-гo кодового слова x i отримують по рекурентному правилу генерації послідовності ЛКГ:   x i j  a  x i1 j  b mod m (2), де a - мультиплікативний параметр, b - адитивний параметр перетворення, mod - операція обчислення за модулем m , де m  2k - потужність алфавіту слів ПВК.У подальшому викладенні для спрощення математичних викладок верхній індекс у позначенні змінних x i j 35 40 45 використовуватися не буде, тобто номер кодового слова фіксується x i j  x i . Розглянемо у загальному вигляді суть запропонованої корисної моделі - способу декодування псевдовипадкового завадостійкого коду на основі використання методу гілок і меж. При декодуванні кодових слів ціль операції вважається досягнутою, якщо в умовах можливих спотворень правильно визначене породжуюче число x 0 відрізка псевдовипадкової послідовності (ПВП) довжиною n чисел. Величина x 0 (першого числа у n - символьному кодовому слові) у двійковому уявленні однозначно визначає початкову двійкову послідовність джерела, яка підлягала передаванню. Для пошуку числа x 0 використовуються усі символи ПВП коду, оскільки всі вони зв'язані з породжуючим числом рекурентним ланцюгом нелінійних обчислень (2). Оскільки в (2) використовується нелінійна операція обчислення за модулем, то вона є перешкодою для реалізації непереборного способу декодування. Тому проводиться лінеаризація операції декодування шляхом введення додаткового цілого не негативного числового параметра y , кількісне значення, якого дорівнює множнику при m в еквівалентному лінійному алгебраїчному представленні операції обчислення по модулю m . Тому вираз (2) зміниться наступним чином: x i1  ax i  b  y i1m , i  0,, n  1 . (3) 2 UA 118097 U Варто зауважити, що вираз (3) справедливий при виконанні обмежень, які слідують з математичної суті алгоритму ЛКГ ПВК: 5  m  1a  b  , - цілі, i  0,, n  2 . (4) 0  yi    yi m   Для компенсації спотворень довільного вихідного кодового слова джерела X в результаті підсумовування з елементами вектора гаусових випадкових величин 3 для кожного з чисел кодового словах x i * , i  0,, n  1 введемо пару допоміжних ненегативних змінних w 2i1 , w 2i1 , які характеризують можливі двосторонні відхилення числа x i * , які є наслідком дії завад  . Одна змінна з цієї пари входить в обчислення зі знаком «+», тобто додається до спотвореного завадою числа x i * , а інша - зі знаком «-», тобто віднімається від x i * . Тоді для 10 15 20  x  x * 0  w  w ; 1 2  0 *  x 1  x 0  w 3  w 4 ; (5)    x n1  x * n1  w 2n1  w 2n .  Особливості задачі визначають, що в кожному з рівнянь (5) одна з пари допоміжних змінних з парним або непарним індексом повинна обов'язково дорівнювати нулю, так як відхилення від дії завади може бути лише в бік зменшення або в бік збільшення істинного числа. При цьому змінні x i повинні задовольняти нерівності 0  x i  m  1 . Оскільки для вирішення задачі декодування планується використовувати лінійне програмування(ЛП), то ліва нерівність даного обмеження (забезпечення ненегативності) автоматично виконується за умови канонічної задачі ЛП. Задачі лінійного програмування вимагають представлення всіх обмежень області допустимих рішень в вигляді рівностей. Тому для заміни правої нерівності на рівність введемо ненегативні цілочисельні допоміжні змінні ~n , ~n1,, ~ 2n1 . Отримаємо: x x x ~  m  1 x*  w  w ; x 0 1 2  n ~ n1  m  1  x * 1  w 3  w 4 ; x   (6)     ~ x 2n1   m  1  x * 1   w 2n1  w 2n ; n     2    де m - потужність алфавіту слів ПВК. При виконанні обмежень (6) досягається виконання наступної системи рівностей: x 0  ~ n  m  1; x  ~ x 1  x n1  m  1; (7)   ~ x  n1  x 2n1  m  1. Для визначення y i , яке відповідає множнику при m в еквівалентному алгебраїчному представленні операції обчислення по модулю m , на основі (3) і (4) отримаємо: 1 a a 1 1  y0  ax * 0  x * 1  b  w 1  w 2  w 3  w 4 ;  m m m m m  (8)   1 a a 1 1 y n 2  ax * n2  x * n1  b  w 2n3  w 2n2  w 2n1  w 2n .  m m m m m  Цільова функція L , мінімум якої потрібно забезпечити при декодуванні, в відповідності з розглянутим вище правилом найменших проекцій, має вигляд:  25    L 2n  wi i1    30  спостережуваного кодового слова X *  x * 0 , x * 1,, x * n1 отримаємо у загальному випадку:   w 1  w 2    w 2i1  w 2i . (9) 3 UA 118097 U Фізичний сенс цільової функції полягає в знаходженні мінімальної суми проекцій кінців 5 вектора різниці між точкою X * на виході каналу з завадами і точкою X , з кодової книги ПВК, котра знаходиться найближче до X * . Математичні вирази (5), (6), (8) і (9) використовують для формування канонічного формулювання основної задачі лінійного програмування(ОЗЛП). Для рішення ОЗЛП вибирають симплекс-метод та його реалізацію у вигляді табличного алгоритму. Таким чином, система рівнянь на основі (5), (6) і (8) складається з 3n-1 рівнянь і має 5n-1 невідомих змінних. Вибирають 2n змінних як вільних, а решту 3n-1 - як базисних. Визначають базисні змінні через вільні. Нехай вільними змінними є w 1,  , w 2n . Тоді перетворення рівнянь (5), (6), (8) і (9) дає  2n 10 15 20 25 наступне формулювання цілочисельної задачі ЛП. Потрібно знайти ненегативні значення змінних x i , y j , w q , що задовольняють системі обмежень-рівностей (5), (6), (8), при цьому змінні x i , y j обов'язково повинні бути цілочисельними. Для вирішення сформульованої цілочисельної задачі ЛП використовують симплекс-метод та його табличний алгоритм. На основі отриманих виразів можна побудувати стартову симплекс-таблицю (Таблиця 1). Правила заповнення таблиці складаються у наступному: - в перший стовпець базисних змінних (Б.З.) вносять імена базисних змінних; - в перший рядок вільних змінних (В.З.) вносять імена вільних змінних; - в другий стовпець вільних членів (В.Ч.) вносять вільні члени з рівнянь (5), (6), (8) і (9); - в наступні 2n стовпців, починаючи з третього, вносять коефіцієнти при вільних змінних з рівнянь (5), (6), (8) і (9), причому знаки цих коефіцієнтів змінюються на протилежні. Отже, в результаті вирішення задачі декодування, спотвореного завадами кодового слова ПВК необхідно вірно визначити значення x 0 - породжуючого числа слова ПВК, яке однозначно визначає k-розрядну комбінацію двійкових символів джерела. Стартова таблиця (Табл. 1) містить опорний план (варіант рішення задачі), в якому значення Б.З. вважаються рівними елементам в відповідних рядках стовпця В.Ч., а значення вільних змінних дорівнюють нулю. В рядку цільової функції L в другому стовпці знаходиться значення досягнутої величини цільової функції. Таблиця 1 Стартова симплекс-таблиця В.З. Б.З. х0 В.Ч.  уn-2 L 30  w2n-3 w2n-2 w2n-1 w2n 1 -1 0 0  0 0 0 0 0 0 1 -1 0 0 0 0  0  0  0  0     0  0  1  -1 0 -1 1 0 0  0 0 0 0 1 0 0 -1 1  0 0 0 0  0  0  0  0   0  0  -1  1 1 m  1 m   a m -1  a  m -1   1 m -1 x n1 m  1  x  m  1  x  * хn+1 у0 w4 * хn  х2n-1 w3 x *1   хn-1 w2 x*0 х1 w1 *  m  1  x  1 ax  x  b m * * 0 n1 * 1  1 * ax n3  x * n2  b m 0   a m   a m       -1 -1 -1 -1  1  m -1 Значення цільової функції нижче буде використано для реалізації спрямованого пошуку рішення по методу гілок і меж. Декодування на основі методу гілок і меж є ітеративним, що має на увазі побудову дерева рішень з вершинами мінімальних значень опорних планів. Довільний маршрут по дереву від начальної вершини до деякої фіксованої вершини визначає допустиму 4 UA 118097 U 5 10 15 20 25 30 35 40 45 50 55 послідовність вибору цілочисельних рішень для змінних. Головною метою виконання декодування запропонованим способом є досягнення цілочисельності змінних х та у при мінімально можливому значенні цільової функції L. При цьому бажано забезпечити досягнення мети корисної моделі - мінімальну кількість обчислювальних операцій. Формально метод гілок і меж може бути описаний послідовністю наступних етапів. На першій ітерації оптимальний опорний план Таблиці 1 аналізують на допустимість на основі змісту комірок стовпця В.Ч. Якщо всі елементи стовпця вільних членів не негативні, то план є допустимим. Якщо всі елементи рядка цільової функції L, крім елемента в стовпці В.Ч., негативні, то план - оптимальний. Якщо який-небудь елемент стовпця В.Ч. є негативним, то план вважається недопустимим і таблиця модифікується відповідно до двоїстої задачі ЛП. Рядок з негативним елементом є розв'язувальним, якщо таких рядків декілька, то вибирається рядок, у якому розташований максимальний за абсолютним значенням негативний елемент. У розв'язувальному рядку шукають елемент, котрий має негативний знак. Якщо таких елементів декілька, то серед них вибирають максимальний за абсолютною величиною. Стовпець в якому розташований цей елемент вважають розв'язувальним. На перетині розв'язувальних стовпця і рядка розташовується розв'язувальний елемент. Для переходу до наступного плану задачі виконують модифікацію таблиці з обміном розташування між парою "вільна-базисна" змінна із заголовків розв'язувальних рядка та стовпця та проводять перерахунок вмісту комірок таким чином: - заголовки змінних, які відповідають розв'язувальному стовпцю і рядку міняють місцями; - розв'язувальний елемент змінюють на зворотний; - елементи розв'язувального рядка ділять на розв'язувальний елемент; - елементи розв'язувального стовпця ділять на розв'язувальний елемент і змінюють знак на протилежний; - до всіх інших елементів із старої таблиці додають добуток елемента розв'язувального рядка старої таблиці, який розташовується в тому ж стовпці, на елемент розв'язуваного стовпця нової таблиці, який розташовується в тому ж рядку. Після завершення модифікації, отриману таблицю повторно аналізують на допустимість. Після отримання допустимого плану, його аналізують на оптимальність. Якщо в рядку цільової функції є хоч один позитивний елемент, то план неоптимальний і таблицю модифікують відповідно до прямої задачі. Суть даної операції складається в наступному, стовпець, в якому знаходиться позитивний елемент, вибирають як розв'язувальний стовпець. Якщо таких елементів декілька, то серед них вибирають максимальний. В розв'язувальному стовпці знаходять елементи, які співпадають по знаку з відповідним елементом із стовпця В.Ч. того ж рядка. Якщо таких співпадаючих за знаком пар елементів декілька, то обчислюють відношення вільного члена до відповідного елемента розв'язувального стовпця. Розв'язувальним рядком вважають рядок, який має мінімальне з даних відношень. Розв'язувальним є елемент, який знаходиться на перетині розв'язувальних стовпця і рядка. Таблицю модифікують і зміст комірок перераховують згідно з правилами, які розглянуті вище. Після цього модифіковану таблицю знову перевіряють на допустимість і оптимальність плану. Ці ітерації проводять доти, поки не буде отримано допустимий та оптимальний план, який називають опорним планом задачі. Далі отриманий опорний план аналізують на цілочисельність. Оскільки шукані змінні x i , i  0,, 2n  1 та y i , j  0,, n  2 повинні бути цілими, то відповідні їм комірки стовпця В.Ч. повинні містити цілі числа. Перший рядок при порядковому розгляді рядків цілочисельних змінних, в якому зустрілося не ціле число, визначає ім'я ( x i , y j або w k ) змінної, для якої необхідно сформувати додаткове обмеження цілочисельності. У даній корисній моделі пропонується використовувати модифікований метод гілок та меж. Суть даної модифікації полягає у наданні пріоритету перегляду на цілочисельність лише змінних y j , оскільки експериментально визначено, що досягнення їх цілочисельності, практично, гарантує цілочисельність і решти змінних задачі декодування. Введення цієї модифікації суттєво скорочує кількість ітерацій пошуку рішень та веде до поліпшення технікоекономічного ефекту корисної моделі - зменшенню обчислювальної складності декодування ПВК. Додаткове обмеження формують шляхом введення в опорний план додаткового рядка для додаткової допоміжної базисної змінної. Механізм введення додаткових обмежень буде детально розглянуто нижче при викладенні конкретного прикладу реалізації рішення задачі декодування. На основі додаткових обмежень виконують розгалуження дерева рішень. Область 5 UA 118097 U допустимих рішень нульового кроку задачі G 0  , розбивається на дві непересічні області для наступного кроку G11 і G 2 1 на основі правила:     G11  X  G 0  , x i  x i  ; G21  X  G0 , xi  xi  . (10) Тобто, в нових областях значення змінної x i необхідно зменшити до найближчого меншого 5 10 15 цілого числа x i  або, навпаки, збільшити до найближчого більшого цілого числа x i  . Після чого, за описаною вище технологією послідовно знаходять опорні плани задач для областей G11 і G 2 1 . Після виконання розгалуження та формування обмежень отримані опорні плани аналізують на допустимість і оптимальність, при необхідності виконують модифікацію і перерахунок таблиць, та їх аналіз на цілочисельність. Дії викладені вище ітеративно повторюють до того моменту поки всі елементи в рядках стовпця В.Ч., які відповідають цілочисельним змінним, не стануть цілими. При цьому деякі цілочисельні змінні можуть з'явитися у складі вільних, тобто дорівнювати нулю. Розглянемо конкретний приклад застосування запропонованого способу для декодування псевдовипадкового завадостійкого коду на основі використання методу гілок і меж. Нехай параметри псевдовипадкового завадостійкого коду складають значення: k=5; n=5. k Для технології ЛКГ вибираємо параметри: m=2 =32, a=5, b=19. Послідовно перебираючи номери двійкових послідовностей на довжині k=5 символів х0=0,1,…,31, використаємо правило (2) для отримання набору послідовностей X , які представлені у Таблиці 2. 20 Таблиця 2 Кодові послідовності повної кодової книги прикладу ПВК x0 0 1 2 3 4 5 6 7 25 30 X 0, 19, 18, 13, 20 1, 24, 11, 10, 5 2, 29, 4, 7, 22 3, 2, 29, 4, 7 4, 7, 22, 1, 24 5, 12, 15, 30, 9 6, 17, 8, 27, 26 7, 22, 1, 24, 11 x0 8 9 10 11 12 13 14 15 X 8, 27, 26, 21, 28 9, 0, 19, 18, 13 10, 5, 12, 15, 30 11, 10, 5, 12, 15 12, 15, 30, 9, 0 13, 20, 23, 6, 17 14, 25, 16, 3, 2 15, 30, 9, 0, 19 x0 16 17 18 19 20 21 22 23 X 16, 3, 2, 29, 4 17, 8, 27, 26, 21 18, 13, 20, 23, 6 19, 18, 13, 20, 23 20, 23, 6, 17, 8 21, 28, 31, 14, 25 22, 1, 24, 11, 10 23, 6, 17, 8, 27 x0 24 25 26 27 28 29 30 31 X 24, 11, 10, 5, 12 25, 16, 3, 2, 29 26, 21, 28, 31, 14 27, 26, 21, 28, 31 28, 31, 14, 25, 16 29, 4, 7, 22, 1 30, 9, 0, 19, 18 31, 14, 25, 16, 3 Нехай для передачі по каналу призначене кодове слово, що породжується числом х 0=0, тобто Х={0,19,18,13,20}, яке в результаті сумування з вектором шуму  має вигляд * Х ={0,18,22,15,20}, де для спрощення розгляду спотворені при передачі числа кодового слова округлені до цілих значень. На основі виразів (5), (6), (8) і (9) та у відповідності до правил заповнення стартової симплекс-таблиці (Таблиця 1) заповнимо стартову таблицю для даного прикладу (Таблиця 3). Таблиця 3 так само, як і наступні отримана за допомогою табличного процесора. Розрядність чисел у таблиці обмежена чотирма знаками після десяткової коми, хоча при обчисленні значень комірок процесором використовуються числа без обмеження розрядності. Тому вплив помилок округлення при обчисленнях виключено. Таблиця 3 x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 ВЧ 0 18 22 15 20 31 13 9 16 11 w1 1 0 0 0 0 -1 0 0 0 0 w2 -1 0 0 0 0 1 0 0 0 0 w3 0 1 0 0 0 0 -1 0 0 0 w4 0 -1 0 0 0 0 1 0 0 0 w5 0 0 1 0 0 0 0 -1 0 0 6 w6 0 0 -1 0 0 0 0 1 0 0 w7 0 0 0 1 0 0 0 0 -1 0 w8 0 0 0 -1 0 0 0 0 1 0 w9 0 0 0 0 1 0 0 0 0 -1 w10 0 0 0 0 -1 0 0 0 0 1 UA 118097 U Продовження таблиці 3 y0 y1 y2 y3 L 5 10 15 20 0,0312 0,1562 -0,1562 -0,0312 0,0312 0 0 0 0 0 0 2,7187 0 0 0,1562 -0,1562 -0,0312 0,03125 0 0 0 0 3,5625 0 0 0 0 0,15625 -0,1562 -0,0312 0,0312 0 0 2,3125 0 0 0 0 0 0 0,1562 -0,1562 -0,0312 0,0312 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 Таблиця 3 містить допустимий, оптимальний опорний план нецілочисельної задачі ЛП (елементи стовпця ВЧ – не негативні, а елементи рядка L - не позитивні). Але план не задовольняє умові цілочисельності (в стовпці ВЧ рядків у0÷у3 знаходяться не цілі значення). У відповідності до модифікованого методу гілок і меж, вибираємо першу, що зустрілася (при розгляді Таблиці 3 зверху вниз), не цілу змінну у0 для формування додаткового обмеження для області G11 таким чином, щоб змінна у0, яка дорівнює у Таблиці 3 величіні 0,0312, отримала ціле значення найближчого меншого цілого числа y0  0 . Для досягнення цього вимагаємо, щоб виконувалась нерівність у0≤0. Але для запису в таблицю необхідно виконати перехід від даного обмеження-нерівності до обмеження-рівності, шляхом введення додаткової ненегативної змінної v: у0+v=0. Виразимо, як базисну, змінну v: v  0  y0 . (11) Значення у0, яке виражено через значення вільних змінних можна прочитати у Таблиці 3, рядку у0: y0=0,1562w1-0,1562w2-0,0312w3-0,0312w4+0,0312. (12) Сформуємо додаткове обмеження використанням (12) в (11), отримаємо: v=-0,0312-0,1562w1+0,1562w2+0,0312w3-0,0312w4. (13) На основі (13) в опорний план вводять додатковий рядок для фіктивної змінної v- для досягнення цілочисельності змінною у0. В результаті розмірність таблиці збільшується і отримують таблицю 4. Таблиця 4 x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 y0 y1 y2 y3 v L 25 ВЧ 0 18 22 15 20 31 13 9 16 11 0,0312 2,7187 3,5625 2,3125 -0,0312 0 w1 w2 w3 w4 w5 w6 w7 w8 w9 w10 1 0 0 0 0 0 0 0 0 0 0 0 1 -1 0 0 0 0 0 0 0 0 0 0 1 -1 0 0 0 0 0 0 0 0 0 0 1 -1 0 0 0 0 0 0 0 0 0 0 1 -1 -1 1 0 0 0 0 0 0 0 0 0 0 -1 1 0 0 0 0 0 0 0 0 0 0 -1 1 0 0 0 0 0 0 0 0 0 0 -1 1 0 0 0 0 0 0 0 0 0 0 -1 1 0,1562 -0,1562 -0,0312 0 0 0 0 0 0 0 0 0 0,1562 -0156,2 -0,0312 0,0312 0 0 0 0 0 0 0 0 0,1562 -0,1562 -0,0312 0,0312 0 0 0 0 0 0 0 0 0,1562 -0,1562 -0,0312 0,0312 -0,1562 0,1562 0,0312 -0,0312 0 0 0 0 0 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 Таблиця 4, складена для підмножини G11 , містить недопустимий план, оскільки в стовпці ВЧ знаходиться негативний елемент. У відповідності з описаними вище правилами необхідно виконати рішення двоїстої задачі та вибрати розв'язувальний рядок - рядок обмеження v, розв'язувальний стовпець - стовпець змінної w1 та розв'язувальний елемент - на перетині рядка v та стовпця w1 (див. заштриховані елементи у таблиці 4). 7 UA 118097 U Таблиця 5 х0 х1 х2 х3 х4 х5 х6 x7 x8 x9 y0 y1 у2 у3 w1 L 5 ВЧ -0,2 18 22 15 20 31,2 13 9 16 11 0 2,7187 3,5625 2,3125 0,2 0,2 v 6,4 0 0 0 0 6,4 0 0 0 0 1 0 0 0 6,4 6,4 w2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 -2 w3 w4 w5 w6 w7 w8 w9 w10 0,2 -0,2 0 0 0 0 0 0 1 -1 0 0 0 0 0 0 0 0 1 -1 0 0 0 0 0 0 0 0 1 -1 0 0 0 0 0 0 0 0 1 -1 -0,2 0,2 0 0 0 0 0 0 -1 1 0 0 0 0 0 0 0 0 -1 1 0 0 0 0 0 0 0 0 -1 1 0 0 0 0 0 0 0 0 -1 1 0 0 0 0 0 0 0 0 0,1562 -0,1562 -0,0312 0,0312 0 0 0 0 0 0 0,1562 -0,1562 -0,0312 0,0312 0 0 0 0 0 0 0,1562 -0,1562 -0,0312 0,0312 -0,2 0,2 0 0 0 0 0 0 -1,2 -0,8 -1 -1 -1 -1 -1 -1 Для отримання допустимості плану необхідно виконати модифікацію та перерахунок Таблиці 4 у відповідності з правилами перерахунку, які розглядалися вище. Реалізація перерахунків елементів дає Таблицю 5. Отримане рішення Таблиці 5 аналізують на допустимість. План недопустимий, тому необхідно виконати модифікацію та перерахунок таблиці. Як розв'язувальний рядок вибирають х0, тоді розв'язувальним стовпцем є w4. Перерахунок дає Таблицю 6. Таблиця 6 w4 х1 х2 х3 х4 х5 х6 х7 х8 х9 y0 у1 у2 у3 w1 L ВЧ 1 19 22 15 20 31 12 9 16 11 0 2,875 3,5625 2,3125 0 1 v 32 32 0 0 0 0 32 0 0 0 1 -5 0 0 0 -32 w2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 -2 w3 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -2 х0 -5 -5 0 0 0 1 5 0 0 0 0 -0,7812 0 0 1 -4 w5 0 0 1 0 0 0 0 -1 0 0 0 -0,0312 0,1562 0 0 -1 w6 0 0 -1 0 0 0 0 1 0 0 0 0,0312 -0,1562 0 0 -1 w7 0 0 0 1 0 0 0 0 -1 0 0 0 -0,0312 0,1562 0 -1 w8 0 0 0 -1 0 0 0 0 1 0 0 0 0,0312 -0,1562 0 -1 w9 0 0 0 0 1 0 0 0 0 -1 0 0 0 -0,0312 0 -1 w10 0 0 0 0 -1 0 0 0 0 1 0 0 0 0,0312 0 -1 10 Таблиця 6 містить допустимий і оптимальний опорний план. Даний план позначають на дереві рішень (фіг. 1) з відповідною вершиною « G11 », яка відповідає значенню цільової функції L=1. 15 Отже, побудуємо обмеження для області G 2 1 таким чином, щоб змінна у0, отримала ціле значення найближчого більшого цілого числа y0  1 . Для досягнення цього вимагаємо, щоб виконувалась нерівність у0≥1. Але для запису в таблицю необхідно виконати перехід від обмеження-нерівності до обмеження-рівності шляхом введення додаткової ненегативної змінної v: у0-v=0, тоді -v=1-у0. Виразимо змінну v: v  y0  1 . (14) 8 UA 118097 U 5 Для позначення додаткової змінної використовують те ж саме ім'я v, оскільки всі фіктивні змінні є допоміжними, а їх величина при досягненні кінцевого рішення задачі не має значення. Більш того, якщо при отриманні проміжного опорного плану будь-яка додаткова фіктивна змінна розташується у складі базисних змінних задачі (у заголовку довільного рядка), то для скорочення розмірності таблиць відповідний рядок підлягає простому видаленню. Вираз у0 через значення вільних змінних визначено формулою (12). Сформуємо додаткове обмеження: v=-0,968+0,1562w1-0,1562w2-0,0312w3+0,0312w4, (16) та включимо додаткову строку обмеження в Таблицю 7. 10 Таблиця 7 x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 у0 у1 у2 у3 v L 15 ВЧ w1 w2 w3 w4 w5 w6 w7 w8 w9 w10 0 1 -1 0 0 0 0 0 0 0 0 18 0 0 1 -1 0 0 0 0 0 0 22 0 0 0 0 1 -1 0 0 0 0 15 0 0 0 0 0 0 1 -1 0 0 20 0 0 0 0 0 0 0 0 1 -1 31 -1 1 0 0 0 0 0 0 0 0 13 0 0 -1 1 0 0 0 0 0 0 9 0 0 0 0 -1 1 0 0 0 0 16 0 0 0 0 0 0 -1 1 0 0 11 0 0 0 0 0 0 0 0 -1 1 0,0312 0,1562 -0,1562 -0,0312 0,0312 0 0 0 0 0 0 2,7187 0 0 0,1562 -0,1562 -0,0312 0,0312 0 0 0 0 3,5625 0 0 0 0 0,1562 -0,1562 -0,0312 0,0312 0 0 2,312 0 0 0 0 0 0 0,1562 -0,1562 -0,0312 0,0312 -0,968 0,1562 -0,1562 -0,0312 0,0312 0 0 0 0 0 0 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 Таблиця 7, складена для підмножини G 2 1 , містить недопустимий план, оскільки в стовпці ВЧ знаходиться негативний елемент. У відповідності з описаними вище правилами, необхідно вибрати як розв'язувальний рядок обмеження v, а як розв'язувальний стовпець w2. Для отримання допустимості плану необхідно виконати модифікацію та перерахунок Таблиці 7 у відповідності з правилами перерахунку. представленими вище. Отримують Таблицю 8. Таблиця 8 х0 х1 х2 х3 х4 х5 х6 х7 х8 х9 у0 у1 у2 у3 w2 L ВЧ 6,2 18 22 15 20 24,8 13 9 16 11 1 2,7187 3,562 2,312 6,2 6,2 w1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 -2 v w3 -6,4 0,2 0 1 0 0 0 0 0 0 6,4 -0,2 0 -1 0 0 0 0 0 0 -1 0 0 0,1562 0 0 0 0 -6,4 0,2 -6,4 -0,8 w4 w5 w6 w7 w8 w9 w10 -0,2 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 -1 0 0 0 0 0 0 0 1 -1 0 0 0 0 0 0 0 1 -1 0,2 0 0 0 0 0 0 1 0 0 0 0 0 0 0 -1 1 0 0 0 0 0 0 0 -1 1 0 0 0 0 00 0 -1 1 0 0 0 0 0 0 0 -0,1562 -0,0312 0,0312 0 0 0 0 0 0,1562 -0,1562 -0,0312 0,0312 0 0 0 0 0 0,1562 -0,1562 -0,0312 0,0312 -0,2 0 0 0 0 0 0 -1,2 -1 -1 -1 -1 -1 -1 9 UA 118097 U Допустимий і оптимальний опорний план, що отримано у Таблиці 8, відповідає вершині « G 2 1 » на дереві рішень (фіг. 1) та має значення цільової функції L=6,2. 5 10 Вершини G11 та G 2 1 першого кроку рішення, які відповідають Таблицям 6 і 8, підлягають подальшому розгалуженню з метою досягнення цілих значень решті цілочисельних змінних. Вибір чергової вершини (таблиці) серед "висячих" вершин дерева для наступного розгалуження здійснюють з точки зору її найбільшої перспективності. Тобто, для отримання наступного опорного плану вибирають таблицю, яка має найменше (серед "висячих" вершин) значення цільової функції. В даному випадку наступною вершиною дерева рішень для розгалуження буде вершина G11 яка відповідає Таблиці 6 та має значення L=1. На другому кроці вибираємо наступну, що зустрілася (при розгляді Таблиці 6 зверху вниз по змінних y j ), не цілу змінну у1 для формування додаткового обмеження для області G12  таким чином, щоб змінна у1, яка дорівнює у Таблиці 6 величині 2,875, отримала ціле значення найближчого меншого цілого числа y1  2 . Сформуємо додаткове обмеження v по прикладу виразів (12) і (13). Отримаємо Таблицю 9. 15 Таблиця 9 w4 х1 х2 х3 х4 х5 х6 х7 х8 х9 у0 у1 у2 у3 w1 v L 20 ВЧ 1 19 22 15 20 31 12 9 16 11 0 2,875 3,5625 2,3125 0 -0,875 1 v -32 -32 0 0 0 0 32 0 0 0 1 -5 0 0 0 5 -32 w2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 -2 w3 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -2 х0 w5 w6 w7 w8 w9 w10 -5 0 0 0 0 0 0 -5 0 0 0 0 0 0 0 1 -1 0 0 0 0 0 0 0 1 -1 0 0 0 0 0 0 0 1 -1 1 0 0 0 0 0 0 5 0 0 0 0 0 0 0 -1 1 0 0 0 0 0 0 0 -1 1 0 0 0 0 0 0 0 -1 1 0 0 0 0 0 0 0 -0,7812 -0,0312 0,032 0 0 0 0 0 0,1562 -0,1562 -0,0312 0,0312 0 0 0 0 0 0,1562 -0,1562 -0,0312 0,0312 1 0 0 0 0 0 0 0,7812 0,0312 -0,0312 0 0 0 0 -4 -1 -1 -1 -1 -1 -1 Таблиця 9, складена для підмножини G12  , містить недопустимий план, оскільки в стовпці ВЧ знаходиться негативний елемент. У відповідності з описаними вище правилами, необхідно вибрати як розв'язувальний рядок обмеження v, а як розв'язувальний стовпець w6. Виконують модифікацію та перерахунок Таблиці 9 у відповідності з правилами перерахунку представленими вище. Отримують Таблицю 10. Таблиця 10 w4 X1 х2 х3 х4 х5 х6 х7 х8 х9 ВЧ 1 19 50 15 20 31 12 -19 16 11 v -32 -32 -160 0 0 0 32 160 0 0 w2 0 0 0 0 0 0 0 0 0 0 w3 -1 0 0 0 0 0 0 0 0 0 х0 -5 -5 -25 0 0 1 5 25 0 0 w5 0 0 0 0 0 0 0 0 0 0 10 v 0 0 -32 0 0 0 0 32 0 0 w7 0 0 0 1 0 0 0 0 -1 0 w8 0 0 0 -1 0 0 0 0 1 0 w9 0 0 0 0 1 0 0 0 0 -1 w10 0 0 0 0 -1 0 0 0 0 1 UA 118097 U Продовження таблиці 10 v0 у1 у2 у3 w1 w6 L 5 0 2 7,937 2,312 0 28 29 1 0 -25 0 0 160 192 0 0 0 0 -1 0 -2 0 0 0 0 0 0 -2 0 0 -3,9062 0 1 -25 -29 0 0 0 0 0 -1 -2 0 1 -5 0 0 -32 -32 0 0 -0,0312 0,1562 0 0 -1 0 0 0,0312 -0,1562 0 0 -1 0 0 0 -0,0312 0 0 -1 0 0 0 0,0312 0 0 -1 Таблиця 10 містить недопустимий план (негативне число в стовпці В.Ч. рядка х7). Оскільки решти числа у даному рядку ненегативні, то продовження обчислень для даної таблиці не має сенсу, так як неможливо позбавиться недопустимого рішення. План, що отримано у Таблиці 10 відповідає вершині « G12  » на дереві рішень (фіг. 1) яка позначена значенням цільової функції L=. Вершина G12  є кінцевою в гілці, і в подальшому галуженню не підлягає. 10 Отже, побудуємо обмеження для області G 2 2 таким чином, щоб змінна у1, отримала ціле значення найближчого більшого цілого числа y1  3 . Сформуємо додаткове обмеження v по прикладу виразу (16) (Таблиця 11). Таблиця 11, складена для підмножини G 2 2 , містить неприпустимий план, оскільки в стовпці ВЧ знаходиться негативний елемент. Таблиця 11 w4 х1 х2 х3 х4 х5 х6 х7 х8 х9 y0 у1 у2 у3 w1 v L 15 ВЧ 1 19 22 15 20 31 12 9 16 11 0 2,875 3,5625 2,3125 0 -0,125 1 v -32 -32 0 0 0 0 32 0 0 0 1 -5 0 0 0 -5 -32 w2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 -2 w3 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -2 х0 w5 w6 w7 w8 w9 w10 -5 0 0 0 0 0 0 -5 0 0 0 0 0 0 0 1 -1 0 0 0 0 0 0 0 1 -1 0 0 0 0 0 0 0 1 -1 1 0 0 0 0 0 0 5 0 0 0 0 0 0 0 -1 1 0 0 0 0 0 0 0 -1 1 0 0 0 0 0 0 0 -1 1 0 0 0 0 0 0 0 -0,7812 -0,0312 0,0312 0 0 0 0 0 0,1562 -0,1562 -0,0312 0,0312 0 0 0 0 0 0,1562 -0,1562 -0,0312 0,0312 1 0 0 0 0 0 0 -0,7812 -0,0312 0,0312 0 0 0 0 -4 -1 -1 -1 -1 -1 -1 У відповідності з описаними вище правилами, необхідно вибрати у таблиці 11 як розв'язувальний рядок - обмеження v, а як розв'язувальний стовпець - також v (обмін між двома фіктивними змінними). Виконують модифікацію та перерахунок Таблиці 11 у відповідності з правилами перерахунку, представленими вище. Отримують Таблицю 12. 20 Таблиця 12 w4 х1 х2 х3 ВЧ 1,8 19,8 22 15 v -6,4 -6,4 0 0 w2 0 0 0 0 w3 -1 0 0 0 x0 0 0 0 0 w5 0,2 0,2 1 0 11 w6 -0,2 -0,2 -1 0 w7 0 0 0 1 w8 0 0 0 -1 w9 0 0 0 0 w10 0 0 0 0 UA 118097 U Продовження таблиці 12 х4 х5 х6 х7 х8 x9 y0 y1 у2 у3 w1 v L 5 20 31 11,2 9 16 11 -0,025 3 3,5625 2,3125 0 0,025 1,8 0 0 6,4 0 0 0 0,2 -1 0 0 0 -0,2 -6,4 0 0 0 0 0 0 0 0 0 0 -1 0 -2 0 0 0 0 0 0 0 0 0 0 0 0 -2 0 0 0 0 0 1 -1 1 0 0 0 0 0 0 0 -0,2 0,2 0 0 0 0 0 -1 1 0 0 0 0 0 0 0 -1 1 0 0 0 0 0 0 0 -1 1 -0,1562 -0,0062 0,0062 0 0 0 0 0 0 0 0 0 0 0 0 0,1562 -0,1562 -0,0312 0,0312 0 0 0 0 0 0,1562 -0,1562 -0,0312 0,0312 1 0 0 0 0 0 0 0,1562 0,0062 -0,0062 0 0 0 0 1 -0,8 -1,2 -1 -1 -1 -1 Отримана таблиця містить недопустимий план - значення у0 - негативне. У відповідності з описаними вище правилами, вибирають як розв'язувальний рядок у0, а як розв'язувальний стовпець х0. Проводять модифікацію і перерахунок Таблиці 12. Отримують Таблицю 13. Таблиця 13 w4 х1 х2 х3 х4 х5 х6 х7 х8 х9 х0 y1 у2 у3 w1 v L 10 15 20 ВЧ 1,8 19,8 22 15 20 30,84 11,2 9 16 11 0,16 3 3,5625 2,3125 0,16 v -6,4 -6,4 0 0 0 1,28 6,4 0 0 0 -1,28 -1 0 0 -1,28 w1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 w3 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 у0 0 0 0 0 0 6,4 0 0 0 0 -6,4 0 0 0 -6,4 w5 0,2 0,2 1 0 0 -0,04 -0,2 -1 0 0 0,04 0 0,1562 0 0,04 w6 -0,2 -0,2 -1 0 0 0,04 0,2 1 0 0 -0,04 0 -0,1562 0 -0,04 w7 0 0 0 1 0 0 0 0 -1 0 0 0 -0,0312 0,1562 0 w8 0 0 0 -[ 0 0 0 0 1 0 0 0 0,0312 -0,1562 0 w9 0 0 0 0 1 0 0 0 0 -1 0 0 0 -0,0312 0 w10 0 0 0 0 -1 0 0 0 0 1 0 0 0 0,0312 0 1,96 -7,68 -2 -2 -6,4 -0,76 -1,24 -1 -1 -1 -1 Таблиця 13 містить допустимий і оптимальний опорний план. Важливим моментом є можливість видалення рядка фіктивної змінної v в Таблиці 13 при переході до наступного опорного плану і використання звільненого рядка для запису нового потрібного обмеження. Опорний план, що отримано у Таблиці 13 відповідає вершині « G 2 2 » на дереві рішень (фіг. 1) та має значення цільової функції L=1,96. Дана вершина має найменші значення цільової функції серед усіх "висячих" вершин виконаних кроків рішення. Тому дану вершину і відповідну таблицю 13 вибирають для подальшого розгалуження. Розглянуті кроки рішення повторюють до того моменту поки всі елементи в рядках стовпця ВЧ, які відповідають цілочисельним змінним, не стануть цілими. При цьому поступово визначають перспективні та кінцеві вершини дерева. Від кроку до кроку кількість кінцевих (неперспективних і непідлягаючих розгалуженню) вершин починає швидко зростати, то задача швидко прагне до єдиного оптимального цілочисельного рішення, яке відповідає найменшому досяжному значенню цільової функції. 12 UA 118097 U Хід отримання рішення прикладу, що розглядається, ілюструється деревом, котре зображено на фіг. 1. Кінцевою вершиною дерева є вершина G 2 10  , значення змінних якої представлені в Таблиці 14, а цільова функція досягає L=7. Таблиця 14 w4 x1 x2 х3 x4 x5 x6 x7 x8 x9 x0 y1 у2 у3 w2 w5 w7 L ВЧ 1 19 18 13 20 31 12 13 18 11 0 3 3 2 0 4 2 7 v 0 0 32 160 0 0 0 -32 -160 0 0 -1 0 25 0 -32 -160 -192 w1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 -2 w3 0 1 5 25 0 -0,2 -1 -5 -25 0 0,2 0 0 3,9062 0,2 -5 -25 -30,8 y0 0 0 0 0 0 6,4 0 0 0 0 -6,4 0 0 0 -6,4 0 0 -6,4 v 1 1 5 25 0 -0,2 -1 -5 -25 0 0,2 0 0 3,9062 0,2 -5 -25 -28,8 w6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 -2 v 0 0 0 32 0 0 0 0 -32 0 0 0 -1 5 0 0 -32 -32 w8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 -2 w9 0 0 0 0 1 0 0 0 0 -1 0 0 0 -0,0312 0 0 0 -1 w10 0 0 0 0 -1 0 0 0 0 1 0 0 0 0,0312 0 0 0 -1 5 Отже, рішення задачі прикладу з Таблиці 14 має вигляд. x х0=0; x1=19; х2=18; х3=13; х4=20; х5=31; х6=12; х7=13; х8=18; х9=11. 10 15 20 25 у w w1=0; w2=0; w3=0; w4=1; w5=4; w6=0; w7=2; w8=0; w9=0; w10=0. у0=0; y1=3; у2=3; у3=2. L 7 Отже, в ході рішення задачі декодування спотвореного кодового слова X з використанням запропонованого способу декодування псевдовипадкового завадостійкого коду, який ґрунтується на технології цілочисельного лінійного програмування з використанням алгоритму гілок та меж кодове слово Х={0,19,18,13,20} декодовано вірно. Фактично декодування зайняло 7 ітерацій (кроків), хоча декодоване слово було отримано на 4-му кроці, решта були надлишковими і виконувались для підтвердження достовірності рішення задачі ЛП. Для підтвердження досягнення мети корисної моделі та ілюстрації техніко-економічного ефекту необхідно оцінити обчислювальну складність в порівнянні з методом простого перебору (прототипу). Для оцінки обчислювальної складності методу гілок та меж використовують відомий результат [5], в якому доведено, що верхня межа кількості вершин дерева рішень обчислюється за наступною формулою: S  N5 log 2 N , (17) де N - ефективне значення кількості невідомих змінних задачі. З урахуванням елементарних операцій (множення та додавання), які виконуються при модифікації однієї симплекс таблиці, розміром (3n-1)×(2n) комірок (як в прикладі, розглянутому вище), задачі ЛП, можна визначити загальну кількість елементарних операцій при рішенні задачі декодування у вигляді: S  N5 log 2 N  2  3n  1  2n . (18) 13 UA 118097 U 5 Відомо [6], що для задач лінійного програмування для отримання довільного допустимого та оптимального опорного плану необхідно виконати приблизно N / 2 ітерацій перерахунку таблиць. Тому кінцева оцінка кількості елементарних операцій отримає вигляд: N S  N5 log 2 N  2  3n  1  2n   N6 log 2 N  3n  1  2n . (19) 2 Величину N для задачі, що розглядається, оцінюють виходячи з наступних міркувань. Загальна кількість змінних базису завдання у стартовій таблиці складає 3n-2, де n - довжина блоку ПВК. При розгалуженні гілок дерева, згідно з модифікованим для даної корисної моделі методом гілок і меж, перевага надається досягненню цілочисельності в першу чергу змінних y i , i  0,, n  2 . Тобто досягнення цілочисельності змінних y i практично гарантує досягнення 10 15 повного рішення задачі (всі змінні х опиняться цілими). При цьому спостерігається найбільш швидке наближення до рішення (рішення досягається за меншу кількість кроків). До складу базисних змінних входять також змінні x і ~ (таблиця 15). Проте звернення до рядків цих x змінних при введені умов цілочисельності виконуються вкрай рідко. До змінних х формуються обмеження тільки у випадку, якщо відповідна змінна виявиться за межами допустимого діапазону значень 0 m  1 . Ймовірність даного випадку за умови рівномірного розподілу чисел та виключення можливості появи в кодовому слові двох однакових чисел складає 2 2n для змінних x та 1 для змінних ~ . Відповідні ймовірнісні вагові коефіцієнти, які визначають x 2n вагу змінних x і ~ і у при обчисленні ефективної кількості змінних N задачі ЛП представлені в x Таблиці 15(третій стовпець). 20 Таблиця 15 Кількість змінних n n n-1 Ім'я та діапазон розміщення x i , i  0,, n  1 ~ , i  i,, 2i  1 xi y i , i  2i,, 3i  2 Вагові коефіцієнти -(n-1) 2 -n 2 1 Отже, використання отриманих вагових коефіцієнтів з Таблиці 15 дозволяє визначити величину ефективного значення кількості невідомих змінних задачі N у вигляді: 25 30 35 40 45 N  n  1  n  2 n  n  2 n1 . (19) Отже, на основі виразів (18) і (19) розраховують обчислювальну складність способу декодування на основі модифікованого методу гілок і меж, і для порівняння приводять обчислювальну складність декодування ПВК на основі переборних алгоритмів (фіг. 2). На основі отриманих результатів з ростом довжини блоку n обчислювальна складність способу-прототипу зростає експоненційно, а при використанні запропонованого способу декодування обчислювальна складність зростає по поліноміальному закону. При довжині блока ПВК n≥37 уже досягається виграш запропонованого способу декодування по величині обчислювальної складності у порівнянні з переборним способом прототипу. Наприклад, при довжині блока ПВК 6 n=50 виграш складає приблизно 100 разів, а при n=60- приблизно в 10 разів. Це є наслідком досягнення поліноміальної складності задачі декодування псевдовипадкового завадостійкого коду на основі використання методу гілок і меж. Таким чином, можна констатувати перевагу запропонованого способу декодування перед переборним алгоритмом, і досягнення цілі корисної моделі - зменшення обчислювальної складності. Джерела інформації: 1. Асташин В.А. Декодер рекуррентной последовательности, АС 1367164 СССР, БИ № 2, 1988 г. 2. Shannon C.E. A Mathematical Theory of Communication. - BellSyst. Tech., July-October, 1948. - Vol. 27. - P. 379-423, 623-656. 3. Лавровская, Т.В. Математические модели случайных и псевдослучайных кодов // Т.В. Лавровская, С.Г. Рассомахин // Системи обробки інформації - 2016. - вип. 9 (146) - с. 55-61. 4. Лавровская, Т.В. Физическая модель псевдослучайных кодов в многомерном Евклидовом пространстве/ Т.В. Лавровская, С.Г. Рассомахин // Системи озброєння і військова техніка. 2016. - вип. 3 (47). – с. 79-84. 14 UA 118097 U 5 5. Назарьянц Е.Г. Полиномиальная сложность параллельной формы метода ветвей и границ решения задачи коммивояжера // Я.Е. Ромм, Е.Г. Назарьянц // Известия Южного федерального университета. Технические науки. - 2015. - вип.4(165). - с. 44. 6. Акулич И.Л. Математическое программирование в примерах и задачах: учеб. пособие для студентов эконом, спец. вузов / И.Л. Акулич.- М.: Высш. Школа. - 1986. - ст. 319 с. ил. ФОРМУЛА КОРИСНОЇ МОДЕЛІ 10 15 Спосіб декодування псевдовипадкового завадостійкого коду на основі використання методу гілок і меж, що полягає у знаходженні найближчого слова з еталонної кодової книги до отриманого спотвореного кодового слова, який відрізняється тим, що для декодування спотвореного завадами слова псевдовипадкового завадостійкого коду, сформованого при передачі за рекурентним правилом лінійної конгруентної генерації, проводять лінеаризацію операції декодування шляхом введення додаткових ненегативних змінних, які еквіваленті нелінійній операції обчислення по модулю т, формулюють та вирішують задачу цілочисельного лінійного програмування з використанням модифікованого по порядку перегляду змінних методу гілок і меж для спрямованого пошуку найкоротшого рішення - найближчого до спотвореного кодового слова. 15 UA 118097 U Комп’ютерна верстка Г. Паяльніков Міністерство економічного розвитку і торгівлі України, вул. М. Грушевського, 12/2, м. Київ, 01008, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 16