На співбесідах часто запитують, яке сортування найшвидше. Питання з каверзою. Пояснюємо чому, і шукаємо оптимальний варіант.

У відповідь ви повинні запитати: «А для якого випадку вибирається оптимальне сортування за часом?» І лише тоді, коли будуть озвучені умови, можна сміливо перебирати існуючі варіанти.

Існують:

• алгоритми сортування O(n 2)на кшталт сортування вставками, бульбашкою та вибором, які використовуються в особливих випадках;
• швидке сортування (загального призначення): в середньому O(n log n)обмінів, але найгірший час – O(n 2)якщо масив вже відсортований, або елементи рівні;
• алгоритми O(nlogn), такі як сортування злиттям та купою (пірамідальне сортування), які також є хорошими алгоритмами сортування загального призначення;
• O(n)або лінійні алгоритми сортування (вибір, вибір з обміном, вибір із підрахунком) для списків цілих чисел, які можуть бути відповідними залежно від характеру цілих чисел у ваших списках.

Якщо все, що ви знаєте, це відношення загального порядку між елементами, то оптимальні алгоритми матимуть складність О(n log n). Для лінійних алгоритмів потрібна додаткова інформація структуру елементів.

p align="justify"> Оптимальність алгоритму тісно залежить від типу списків/масивів, які ви збираєтеся сортувати, і навіть від моделі ЕОМ. Чим більше інформації у вашому розпорядженні, тим точнішим буде вибір. За дуже слабких припущень про фактори оптимальною складністю гіршого випадку може бути О(n!).

Ця відповідь стосується лише складнощів. Фактичний час виконання алгоритмів залежить від величезної кількості факторів.

Тестування

Отже, яке ж сортування найшвидше?

Візуалізація

Непогана візуалізація сортувань продемонстрована у цьому відео:

Здається, що вона відповідає на питання про те, яке сортування найшвидше, але не варто забувати, що на швидкість впливає безліч факторів, і це лише один із продемонстрованих варіантів.

Найкращий алгоритм заміщення сторінок нескладно описати, але неможливо реалізувати. У ньому все відбувається в такий спосіб. На момент помилки відсутності сторінки в пам'яті знаходиться певний набір сторінок. До деяких із цих сторінок буде звертатися буквально з наступних команд (ці команди містяться на сторінці). До інших сторінок звернення може бути і через 10, 100 чи, можливо, навіть 1000 команд. Кожна сторінка може бути позначена кількістю команд, які мають бути виконані до першого звернення до сторінки.

Оптимальний алгоритм заміщення сторінок свідчить, що має бути видалена сторінка, що має позначку з найбільшим значенням. Якщо якась сторінка не буде використовуватися протягом 8 млн. команд, а інша якась сторінка не буде використовуватися протягом 6 млн. команд, то видалення першої з них призведе до помилки відсутності сторінки, в результаті якої вона буде знову вибрана з диска в найвіддаленішому майбутньому. Комп'ютери, як і люди, намагаються якомога максимально відстрочити неприємні події.

Єдиною проблемою такого алгоритму є неможливість його реалізації. На той час, коли станеться помилка відсутності сторінки, операційна система не матиме способу дізнатися, коли кожна зі сторінок буде затребувана наступного разу. (Подібна ситуація спостерігалася і раніше, коли ми розглядали алгоритм планування, що обирає спочатку найкоротше завдання, - як система може визначити, яке із завдань найкоротше?) Проте при прогоні програми на симуляторі та відстеженні всіх звернень до сторінок з'являється можливість реалізувати оптимальний алгоритм заміщення сторінок під час другого прогону, скориставшись інформацією про звернення до сторінок, зібраної під час першого прогону.

Таким чином з'являється можливість порівняти продуктивність здійснених алгоритмів із найкращим із можливих. Якщо операційна система досягає продуктивності, скажімо, на 1% гірше, ніж у оптимального алгоритму, то зусилля, витрачені на пошуки досконалішого алгоритму, дадуть не більше 1% поліпшення.

Щоб уникнути будь-якої можливої ​​плутанини, слід усвідомити, що подібна реєстрація звернень до сторінок стосується лише однієї програми, що пройшла оцінку, і лише за одного цілком певного набору вхідних даних. Таким чином, отриманий в результаті цього алгоритм заміщення сторінок відноситься тільки до цієї конкретної програми та конкретних вхідних даних. Хоча цей метод і застосовується з метою оцінки алгоритмів заміщення сторінок, у реальних системах він марний. Далі ми розглядатимемо ті алгоритми, які дійсно корисні для реальних систем.

Нижня межа складності класу алгоритмів визначається не єдиним чином. Наприклад, f(n) = 0 завжди є нижньою межею, так само як і будь-яка негативна функція. Чим більше знайдений нижній кордон, тим він нетривіальніший і цінніший. Сигналом про те, що ми не зможемо побудувати нижню межу більшу, ніж

ПЗ Глава 4. Нижня межа складності. Оптимальні алгоритми

вже наявний нижній кордон у нас f(n), може бути, наприклад, наявність Aе .s4,для котрого T A(n) = f(n).З такою ситуацією ми стикаємося у попередньому параграфі у прикладах 14.1 та 14.3. Відомий нам алгоритм пошуку найменшого елемента та алгоритм бінарного пошуку місця елемента в упорядкованому масиві має кожен складність, що збігається зі знайденим нижнім кордоном. Ці алгоритми є оптимальними у сенсі наступного визначення.

Визначення 15.1.Нехай .s4 -клас алгоритмів розв'язання певної задачі. Нехай ухвалено угоду про те, в чому вимірюються витрати алгоритмів і що вважається розміром входу, та нехай n-Позначення розміру входу. Алгоритм Aе .s4називається оптимальнимв j4,якщо T A (n)є нижньою межею складності алгоритмів з j4.

Приклад 15.1.При отриманні нижньої межі складності та доказі оптимальності іноді буває корисним залучення функцій на наборах тих величин, які виникають у процесі виконання алгоритму, наприклад, на наборах змінних значень, використовуваних алгоритмом.

Пропозиція 15.1.Функція f(n) = Г 2 n 1 - 2 є нижньою межею складності алгоритмів одночасного вибору найбільшого та найменшого елементів масиву довжини n за допомогою порівнянь.

Доведення.Кожен етап виконання довільного алгоритму V,заснованого на порівняннях і призначеного для пошуку найбільшого та найменшого елементів масиву, може бути охарактеризований четвіркою ( A, B, C, D)підмножин безлічі вихідних елементів (x г, x 2 , ■ ■ ■, x n ),де

Aскладається зі всіх тих елементів, які взагалі не порівнювалися;

Bскладається з усіх тих елементів, які брали участь у деяких порівняннях і завжди виявлялися більшими;

Cскладається з усіх тих елементів, які брали участь у деяких порівняннях і завжди виявлялися меншими;

Dскладається з усіх тих елементів, які брали участь у деяких порівняннях, іноді виявляючись більшими, а іноді – меншими.

Нехай a, b, c, d- кількості елементів множин A, B, C, Dвідповідно. Вихідна ситуація характеризується рівностями a = n, b = = c = d = 0.Після завершення алгоритму повинні виконуватись рівні-

§ 15 . Оптимальні алгоритми

ства а = 0, b = c = 1, d = n-2.Після першого порівняння протягом усього виконання алгоритму постійно матимуть місце нерівності Ъ^1,с^1.

Усі порівняння, що здійснюються під час виконання алгоритму V,можна розбити на типи, що позначаються AA, AB, AC, AD, BB, BC, BD, CC, CD, DD,наприклад: порівняння належить типу АВ , якщо один із порівнюваних елементів береться з А , інший-з У , і т. д. Виходячи з цього, можна виписати всі можливі зміни четвірки (а, Ь, з, d) під впливом порівнянь різних типів.

ФЕДЕРАЛЬНЕ АГЕНТСТВО З ОСВІТИ

Державний освітній заклад вищої професійної освіти "Воронезький державний технічний університет"

Радіотехнічний факультет

Кафедра радіотехніки

Спеціальність 210302 "Радіотехніка"

Оптимізація алгоритмів пошуку

Виконав студент гр. РТ-041 Д.С. Чоткін

Перевірив доцент кафедри В.П. Литвиненко

Вступ. 4

1. Розробка оптимального дихотомічного алгоритму пошуку при рівноймовірному розподілі ймовірностей та числі подій М=16. 5

2. Розробка оптимального алгоритму пошуку експоненційного закону розподілу ймовірностей при М=16. 7

3. Розробка оптимального алгоритму пошуку експоненційного закону розподілу при числі вимірювань від N=15 до N=log2M.

4. Розробка оптимального алгоритму пошуку для 9-го варіанта розподілу при числі вимірів від N=1 до 15. 12

Висновок. 19

Список літератури 20

Вступ

Прихованість характеризує витрати (часу, коштів), необхідні виявлення реасподія із заданою достовірністю (ймовірністю правильного рішення, довірчою ймовірністю ).

При формуванні оцінки скритності випадкової події в якості оправної прийнято двоальтернативну покрокову пошукову процедуру, сутність якої полягає в наступному.

Безліч Х з відповідним законом розподілу ймовірностей розбивається на два підмножини та (верхній індекс – номер розбиття). Двійковий вимірювач проводить двійковий вимір, виявляючи, в якому підмножині знаходиться реаподія (його слід). Потім підмножина, у якому виявлено реаподію (на рис.2.1. це ), знову розбивається на два підмножини і виявляється слід реаподія в одному з них. Процедура закінчується, коли у виділеному підмножині виявляється одна подія. Пошук може бути послідовним та дихотомічним. У першому алгоритмі () проводиться послідовний перебір станів від першого до останнього, доки не зустрінеться реаподія.

Другий алгоритм пошуку () передбачає поділ усієї множини станів навпіл, перевірку наявності реаподія в кожній з цих частин, потім поділ обраної половини множини X на дві рівні частини з перевіркою наявності в них реаподія і так далі. Пошук закінчується, коли у виділеному підмножині виявляється одна подія.

Існує кілька способів мінімізації двійкових пошукових процедур. Прикладами можуть бути методи Циммермана-Хафмена і Шеннона-Фоно. Оптимізувати алгоритм можна за різними параметрами з урахуванням вартості вимірювання та без. У цій лабораторній роботі досліджували оптимізацію дихотомічного алгоритму пошуку за найменшою величиною середньої скритності.

1. Розробка оптимального дихотомічного алгоритму пошуку при рівноймовірному розподілі ймовірностей та числі подій М = 16

Увімкніть режим дихотомічного пошуку. Встановіть кількість подій при рівномірному розподілі ймовірностей і встановіть кількість вимірювань. Розробте оптимальний алгоритм пошуку, встановіть його на набірному полі, проведіть моделювання, визначте потенційну скритність.

У разі найбільш оптимальним алгоритмом пошуку є алгоритм розроблений за принципом Шеннона-Фано. Даний метод передбачає вихідну множину елементів із заданим розподілом розбити на два підмножини з номерами 0 і 1 так, щоб ймовірності влучення в них були максимальні близькі (в ідеалі навпіл). Потім кожне з отриманих підмножин окремо розбивається на два підмножини з тією ж умовою та номерами з 00,01,10,11. Розбиття закінчується коли всі елементи підмножини матимуть лише один елемент.

У результаті розроблено оптимальний алгоритм пошуку рівномірного закону розподілу ймовірностей.

Проведемо розрахунок потенційної скритності для рівноймовірного закону розподілу ймовірностей:

(1)

В результаті для цього випадку:

В результаті отримано простий вираз визначення потенційної скритності рівномірного закону розподілу, який при дихотомічному алгоритмі пошуку не залежить від перебору комбінації вимірювань, а тільки від виду дерева пошуку.

Розробка оптимального алгоритму пошуку для експоненційного закону розподілу ймовірностей при М=16

Виберіть експоненційний розподіл ймовірностей подій виду , , - нормуючий множник, при тому, що і в пункті 1. Визначте оптимальний алгоритм пошуку, задайте його на набірному полі, проведіть моделювання, визначте потенційну скритність.

Спочатку залишимо дерево пошуку таким самим, що в попередньому пункті. "PrintScreen" програми "Poisk" для цього випадку для експоненційного закону розподілу.

Дивлячись на перебіг кривої зняття невизначеності приходимо до висновку, що її перебіг є неоптимальним. Використовуючи відомі алгоритми оптимізації пошуку, приходимо до того, що в даному випадку оптимальним алгоритмом пошуку є зовсім не дихотомічний алгоритм при будь-яких комбінаціях знаходження реаподії, а послідовний. Для цього випадку він є оптимальним, так як першим виміром перевіряється найбільш ймовірне, потім наступне і так поки не залишиться невизначеності прийняття рішення.

Доказ використання послідовного алгоритму пошуку. І тому використовується метод Циммермана-Хаффмена. Даний метод оптимізації складається з двох етапів: «Заготівельні операції» та «Зчитування». Докладніше про це йдеться у книзі.

Так як показник ступеня більше 1, а це задовольняє нерівність:

Де λ – показник ступеня розподілу ймовірностей, що дорівнює 1, то для даного випадку оптимальним є послідовний алгоритм пошуку.

В результаті виконання цього пункту показано, що оптимальним є послідовний алгоритм пошуку. Порівнюючи результати виконання двох пунктів приходь до висновку, що для кожного закону розподілу ймовірностей є свій оптимальний алгоритм пошуку або послідовний, або дихотомічний, або комбінований алгоритм пошуку.

Розробка оптимального алгоритму пошуку експоненційного закону розподілу при числі вимірів від N=15 до N=log2M

Для експоненційного розподілу ймовірностей з пункту 2 послідовно зменшуючи максимальну кількість вимірів від до, розробіть оптимальні алгоритми пошуку та за результатами моделювання визначте відповідні значення середньої кількості вимірів.

При N=15 з попереднього пункту оптимальним є послідовний алгоритм пошуку і йому значення середнє значення двійкових вимірів визначається як і для потенційної скритності. Значення Rcp представлено таблиці 1.

Таблиця 1 - Залежність середньої кількості вимірювань

від числа вимірювань за оптимальних алгоритмів пошуку

Проведемо розрахунок потенційної скритності для кожного випадку за формулою 1:

При числі вимірювань, що дорівнює 3-му, розробити алгоритм пошуку неможливо, так це не задовольняє умову реалізованості пошуку, а саме:

У результаті побудовано графік залежності середньої кількості вимірів від числа вимірів представлений малюнку 8.

Рисунок 8 – Залежність середньої кількості вимірів від числа вимірів для експоненційного закону розподілу ймовірності

4. Розробка оптимального алгоритму пошуку для 9-го варіанта розподілу при числі вимірів від N=1 до 15

Для свого варіанта розподілу ймовірностей при числі подій розробіть оптимальний алгоритм пошуку, побудувати дерево пошуку, пояснити його форму, чим вона обумовлена?

На набірному полі вкажіть оптимальний повний алгоритм пошуку. Послідовно виключаючи останні виміри (до ), розгляньте залежність середньої кількості вимірів, ймовірності неповного рішення та залишкової скритності від тривалості пошуку. Результати представлені у таблиці 2.

Таблиця 2 - Залежність середньої кількості вимірювань,

залишкової скритності, ймовірності невизначеності від кількості вимірів

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
R	4	3.775	4.325	4.725	5.1625	5.375	5.5	5.65	5.7	5.7625	5.8	5.8
Pнеоп	0.55	0.7625	0.875	0	0	0	0	0	0	0	0	0	0	0	0
Sіст	0.801	0.785	0.791	0.802	0.814	0.826	0.837	0.848	0.858	0.868	0.877	0.885	0.893	0.901

У цій таблиці Sост вважалося за довірчої ймовірності 0.9. "PrintScreen" програми "Poisk" при різних значеннях числа вимірювань представлений на рисунках 8-11.

При числі вимірів менше 4-х з'являється можливість неповного рішення, пов'язана з тим, що неможливо перевірити всі події. Через війну доводиться перевіряти в повному обсязі, оптимальним варіантом буде перевірка найімовірніших подій. "PrintScreen" програми "Poisk" при числі вимірювання менше 3-х представлена ​​на малюнку 12.

Побудуємо графік залежності потенційної скритності від числа виміру, що представлений малюнку 13.

Рисунок 13 – Залежність середньої кількості вимірів від числа вимірів для 9-го закону розподілу ймовірності

Рисунок 14 – Залежність ймовірності неповного рішення від числа вимірювань для 9-го закону розподілу ймовірності

(3)

(4)

Довірчу ймовірність змінюватимемо в межах 0.7÷0.9. В результаті отримано графік залежності залишкової скритності від числа вимірів, який представлений малюнку 15.

Ніст (Pдов) Pдов = 0.9

Рисунок 15 – Залежність залишкової схованості при значеннях довірчої ймовірності 0.7÷0.9

З представленого вище графіка можна дійти невтішного висновку, що Pдов слід вибирати близьким до одиниці, це призведе до зменшення залишкової скритності, проте який завжди таке можливо.

Рисунок 16 – Залежність залишкової схованості при значеннях числа вимірів 4,8,16

З даного графіка випливає, що при великій кількості вимірювань залишкова скритність вища, хоча за логікою більша кількість вимірювань призведе до зменшення ймовірності невизначеності рішення.

Висновок

У цій роботі було проведено дослідження оптимізації дихотомічного алгоритму пошуку за допомогою програми Poick. Проведено порівняння із послідовним алгоритмом. Досліджено вид КСН при рівномірному, експоненційному та заданому за варіантом розподілі подій. Напрацьовано навички у користуванні програмою Poick.

У ході виконання лабораторної роботи було проведено розробку оптимальних алгоритмів пошуку для послідовного та дихотомічного алгоритмів пошуку.

Проведено розрахунок кривої зняття невизначеності та встановлено, що у деяких випадках правильніше використовувати послідовний алгоритм пошуку, а інших дихотомічний. Але це може бути пов'язане лише з вихідним розподілом ймовірності.

Правильність роботи програми Poisk підтверджена за допомогою розрахунків, проведених у пакеті програм Matcard 2001.

Список літератури

1. Основи теорії скритності: навчальний посібник для студентів спеціальності 200700 "Радіотехніка" денної форми навчання / Воронезький державний технічний університет; Упоряд.З.М. Каневський, В.П. Литвиненко, Г.В. Макаров, Д.А. Максимов; за редакцією З.М. Канівського. Воронеж, 2006. 202с.

2. Методичні вказівки до лабораторних робіт «Дослідження алгоритмів пошуку» з дисципліни «Основи теорії скритності» для студентів спеціальності 200700 «Радіотехніка» денної форми навчання / Воронезький державний технічний університет; сост.З.М. Каневський, В.П. Литвиненко. Воронеж, 2007.54с.

3. СТП ВДТУ 005-2007. Курсове проектування. Організація, порядок, оформлення розрахунково-пояснювальної записки та графічної частини.

Припустимо, що всі спотворення в каналі строго детерміновані і випадковим є тільки гаусівський адитивний шум, який спочатку вважатимемо білим, зі спектральною щільністю.

де всі відомі. Невідомі лише реалізація перешкоди та індекс дійсно переданого сигналу, який має визначити вирішальна схема.

Будемо також вважати, що всі є фінітними сигналами, тривалість яких Це має місце, якщо сигнали, що передаються фінітні і мають однакову тривалість (система синхронна), а в каналі немає ні багатопроменевого поширення, ні лінійних спотворень, що викликають розтягування сигналу (або вони скориговані).

Надалі скрізь вважатимемо, що у системі забезпечена надійна тактова синхронізація, т. е. межі тактового інтервалу, у якому надходить сигнал відомі точно. Питання синхронізації дуже істотні при реалізації оптимальних демодуляторів та синхронних систем зв'язку взагалі, але вони виходять за межі цього курсу. Момент початку посилки приймемо за нуль.

Визначимо в цих умовах алгоритм роботи оптимального (тобто заснованого на правилі максимальної правдоподібності) демодулятора, що аналізує сигнал на тактовому інтервалі. З цією метою необхідно знайти відносини правдоподібності для всіх можливих сигналів щодо нульової гіпотези

Завдання утруднюється тим, що ширина спектра сигналу нескінченна (оскільки він фінітний), а тому простір сигналів нескінченномірний Для таких сигналів (або нескінченномірних векторів), як зазначалося, немає щільності ймовірностей. Однак існують -рні щільності ймовірностей для будь-яких перерізів сигналу (див. § 2.1).

Замінимо спочатку білий шум. квазибілим, що мають ту ж односторонню спектральну щільність потужності але тільки в деякій смузі частот де 1. Розглянемо спочатку нульову гіпотезу, тобто вважатимемо, що шум. Візьмемо на тактовому інтервалі рівновіддалених перерізів через Відліки у цих перерізах для квазібілого гаусівського шуму незалежні відповідно до (2.49). Тому -мірна щільність ймовірностей для взятих відліків

де дисперсія (потужність) квазібілого шуму.

При гіпотезі, що передавався символ Отже, умовна -мірна щільність ймовірності перерізів визначиться такою ж формулою, як і (4.18), якщо замінити різницею

Відношення правдоподібності для сигналу (щодо нульової гіпотези), обчислене для перерізів:

Замінимо дисперсію її виразом:

За правилом максимуму правдоподібності у разі квазібілого шуму вирішальна схема повинна вибирати значення, що забезпечує максимум. Замість максимуму можна відшукувати максимум його логарифму:

Зауважимо, що другий член (4.22) не залежить від і його можна при порівнянні не враховувати. Тоді правило рішення про те, що передавався сигнал, можна сформулювати наступним чином:

В -мірному евклідовому просторі визначає норму різниці векторів або відстань між ними. Тому алгоритм (4.23) можна записати як

і надати йому просту геометричну інтерпретацію: оптимальний демодулятор повинен реєструвати той із сигналів (відповідний символу який «ближче» до прийнятого коливання Як приклад на рис. 4.2 показано оптимальне розбиття двовимірного простору сигналів при передачі двійкових сигналів Області прийняття рішення на користь символів обидві сторони від

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

Перетворимо (4.22), розкривши дужки та здійснивши скорочення:

Повернемося тепер до вихідного завдання білого шуму. З цією метою розширюватимемо смугу Тоді число перерізів буде прагнути до нескінченності, до нуля. Суми в (4.24) перетворяться на інтеграли, і логарифм відносини правдоподібності визначиться як

а алгоритм рішення про передачу набуде вигляду

де енергія очікуваного сигналу

Пристрій, що безпосередньо обчислює скалярний твір,

називають активним фільтром, або корелятором, тому приймач, що реалізує алгоритм (4.26) називають кореляційним.

На рис. 4.3 показана структурна схема приймального пристрою, що працює відповідно до (4.26). Тут блоки X – перемножувачі; А - генератори опорних сигналів - інтегратори, що віднімають пристрої; вирішальний пристрій, що визначає моменти часу, кратні (при замиканні ключа), номер гілки з максимальним сигналом.

Якщо сигнали обрані таким чином, що всі їх реалізації (а отже, і всі реалізації мають однакові енергії алгоритму)

Мал. 4.3. Оптимальний демодулятор при точно відомих сигналах

прийому (4.26) (і відповідно його реалізація) спрощується (відпадає необхідність у пристроях, що віднімають) і приймає

З (4.29) видно, що правило рішення не зміниться, якщо сигнал, що надходить на вхід демодулятора, помножити на будь-яке число. Тому система, в якій всі реалізації сигналу мають рівну енергію, відрізняється тим, що оптимальний алгоритм прийому в ній не вимагає знання «масштабу» сигналу, що приходить або, іншими словами, знання коефіцієнта передачі каналу. Ця важлива особливість зумовила широке поширення систем сигналів з рівною енергією, які називають системами з активною паузою. Особливо важлива ця особливість для каналів із завмираннями, у яких коефіцієнт передачі флуктує (див. нижче § 4.7).

Слід наголосити, що правильний тактовий синхронізм для виявлення меж посилок (знімання сигналів на виході блоку в моменти часу, кратні та скидання напруги з інтегратора після прийняття рішення) є неодмінною умовою практичної реалізації розглянутих алгоритмів за схемою рис. 4.3.

Для найпоширенішої двійкової системи нерівностей (4.26) залишається лише одне, і алгоритм прийому можна у більш простому вигляді:

де різницевий сигнал; пороговий рівень. Для системи з активною паузою значно полегшує реалізацію оптимальної схеми.

За виконання нерівності (4.30) реєструється символ 1, інакше - 0. Для реалізації (4.30) у схемі рис. 4.3 потрібна лише одна гілка.

На рис. 4.4 показано схему, що реалізує алгоритм (4.30) для двійкової системи передачі однополярними імпульсами (з пасивною паузою):

Мал. 4.4. Реалізація оптимального прийому двійкових прямокутних відеоімпульсів

При цих сигналах і правило (4.30) набуде наступного вигляду:

Інтегрування у схемі рис. 4.4 здійснюється з достатньою точністю ланцюгом за умови, що При цьому на конденсаторі С напруга в момент дорівнює - Отже, правило зводиться до того, що ця напруга повинна перевищити пороговий рівень який і вводиться в При виконанні цієї нерівності записується 1, при невиконанні - 0 Після цього запису (що відбувається при замиканні ключа необхідно зробити скидання напруги з інтегратора, щоб можна було приймати наступний елемент сигналу. Скидання здійснюється замиканням ключа, що розряджає конденсатор.

Ця ж схема, з невеликою модифікацією, може використовуватися для демодуляції в двійковій системі передачі двополярними імпульсами (з активною паузою): При цьому отже, У цьому випадку правило (4.30) після скорочення набуває вигляду

Його реалізує схема рис. 4.4 якщо пороговий рівень X покласти рівним нулю. При цьому перетворюється на дискримінатор полярності, що видає символ 1, коли на його вході напруга позитивно, інакше.

Розглянуті дві системи використовують у найпростіших пристроях проводового зв'язку. У радіоканалах, а також у сучасних кабельних каналах використовують високочастотні сигнали. Найбільш простими двійковими системами з гармонійними сигналами є системи з амплітудною (AM), фазовою (ФМ) та частотною маніпуляцією.

У двійковій Всі вхідні сюди постійні в цьому параграфі вважаємо відомими. Оскільки тут правило (4.30) запишеться так:

Воно реалізується схемою рис. 4.5 яка відрізняється від рис. 4.4. блоком перемноження сигналу з опорним сигналом Пороговий рівень у цьому випадку дорівнює

Мал. 4.5. Реалізація оптимального прийому в двійковій системі AM, ФМ за точно відомого сигналу

При двійковій ФМ системі

Це - система з активною паузою, і тому в легко переконатися, що правило рішення зводиться при цьому до наступного: і

реалізується тією самою схемою рис. 4.5 при цьому випадку грає роль дискримінатора полярностей. Вигляд його можна визначити, знаючи на тлі білого шуму зі спектральною щільністю Легко бачити, що на виході фільтра будуть сигнали, а шум буде пофарбованим, зі спектральною щільністю, тобто на вхід уявного оптимального демодулятора надходитимуть саме ті сигнали і той шум, на які він розрахований. Отже, схема рис. 4.66 являє собою демодулятор для сигналів на тлі білого шуму, в якому ймовірність помилок менше, ніж в оптимальному демодулятор, підключеному до виходу фільтра, що обіляє на рис. 4.6а. Ця суперечність і доводить, що не може існувати демодулятор для сигналів на тлі забарвленого шуму кращим, ніж на рис. 4.6а.

Зауважимо, що при реалізації такого демодулятора з фільтром, що обіляє, виникають труднощі, пов'язані з тим, що сигнали при проходженні через фільтр, як правило, розтягуються і виникає взаємне накладення елементів, сигналу Існує ряд шляхів подолання цієї труднощі, проте докладний аналіз їх виходить за межі курсу

Слід звернути увагу, що у схемі рис. 4.5 опорний сигнал повинен мати ті ж початкові фази, що і очікувані сигнали, що приходять або, іншими словами, повинен бути когерентним з приходять сигналами. Ця вимога зазвичай ускладнює реалізацію демодулятора і вимагає введення в нього, крім зазначених на рис. 4.5 блоків додаткових пристроїв, призначених регулювання фаз опорних сигналів.

Усі методи прийому, для реалізації яких необхідне точне апріорне знання початкових фаз сигналів, що приходять, називаються когерентними. У тих випадках, коли відомості про початкові фази очікуваних сигналів вилучаються з самого прийнятого сигналу (наприклад, якщо фаза флуктує, але настільки повільно, що може бути передбачена попередніми елементами сигналу), прийом називають квазикогерентним. Якщо ж відомості про початкові фази сигналів, що приходять, відсутні або з яких-небудь міркувань не використовуються, то прийом називають некогерентним (див. нижче § 4.6).