РОЗДІЛ 2
ДОСЛІДЖЕННЯ АСИМПТОТИЧНО ОПТИМАЛЬНОГО МЕТОДУ НУМЕРУВАННЯ ІНФОРМАЦІЙНОГО СТАНУ ОБ'ЄКТА ВИМІРЮВАННЯ
2.1. Асимптотична оптимальність перестановчих кодів
Активність джерела вимірювальної інформації визначається його частотними властивостями, а виявляти її можна, фіксуючи для кожного із них кількість перетинів його вимірювальним сигналом границь допускового поля, або визначаючи на кожному з кроків порівняння джерело з найбільшим відносним відхиленням та фіксуючи кількість таких рішень, прийнятих на користь кожного з джерел. Технічно перший підхід втілено в багатоканальних засобах з поліноміальними прогнозерами (інтерполяторами), другий - при адаптивному комутуванні [61]. Розподіл активностей характеризуватиме інформаційний стан об'єкта вимірювання. У відповідності з теорією інформації мірою невизначеності є ентропія, яка може служити інформаційною характеристикою стану об'єкта [85, 239]. Можна практично одержати оцінку ентропії сукупності джерел багатоканального засобу, а отже, й об'єкта вимірювання можна, використовуючи для нумерування послідовності відліків від усіх джерел багатоканального засобу престановчі коди [35, 103], який вона обслуговує Практичне реалізування групового компресування залежить від повноти апріорної інформації щодо статистики активностей сукупності джерел [20, 285]. При практичній реалізації оптимального нумерування необхідно враховувати характерні ситуації, а саме: статистика активностей сукупності джерел вимірювальної інформації апріорно достатньо повно відома або ж апріорно невідома.
2.1.1. Статистика активностей сукупності джерел апріорно відома достатньо повно
В цьому випадку набір джерел, що формують послідовність із своїх ненадлишкових відліків, та кількість виділених кожному з них позицій у ній фіксована. Проте на відміну від циклічної дисципліни обслуговування виведення відліку джерела в лінію зв'язку не планується заздалегідь, а здійснюється за вимогою самого джерела.
Одержане вище співвідношення (1.12) для розміру номера послідовності є верхньою оцінкою числа . Аби переконатися в цьому, скористаємося співвідношенням [286]
(2.1)
тут - різноманітні набори чисел, пов'язані умовою , для .
Вибравши серед різних наборів цілих чисел набір, в якого (що можливо здійснити, оскільки ), одержимо лише один із можливих доданків цієї суми. Тому цілком очевидно, що сума (2.1) буде більшою від однієї із своїх невід'ємних складових, а саме:
Якщо прийняти ще й , тоді матимемо
або
Приймаючи та пам'ятаючи, що , доданків вище записаної суми, тому
або та .
Розглянемо ліву частину нерівності
.
Отже:
або .
Поділивши логарифм лівої та правої частини нерівності на , одержимо
або ,
що й потрібно було довести.
2.1.2. Статистика активностей сукупності джерел невідома
В цьому випадку набір послідовності та розподіл її позицій між окремими джерелами нефіксований.
Тому поряд з кодом розташування розміром необхідно подати й відомості про його довжину, оскільки вона змінна через апріорну невизначеність розподілу активностей розміром та відомості про набір послідовності, тобто скільки місць в послідовності відліків закріплено за кожним із джерел, розміром . Тобто, службова інформація послідовності
. (2.2)
Розглянемо окремі складові детальніше:
а). Якщо вважати кількості відліків від окремих джерел у послідовності відліків довжиною N взаємонезалежними, тоді
, (2.3)
оскільки теоретично можливо, що усі позиції послідовності відліків займатимуть вибіркові значення лише одного із джерел.
Ці витрати можна зменшити, врахувавши, що загальна кількість позицій у послідовності N завжди стала , а від послідовності до послідовності можуть лише перерозподілятися позиції між окремими джерелами. Тому інформацію про набір послідовності з кількістю символів можна розглядати як номер того чи іншого конкретного перерозподілу , . Для визначення загальної кількості цих можливих комбінацій скористаємося наступним [240] поданням коду набору
,
де - r-те вибіркове значення і-го джерела ;
R - символи межі між вибірковими значеннями сусідніх джерел (їх кількість ).
Отже, . Скориставшись формулою Стірлінга, матимемо
. (2.4)
Даний спосіб формування цієї складової має перевагу перед попереднім, зокрема через спорідненість з алгоритмом нумерування Q-перестановок.
На рисунку 2.1 подано залежності пронормованих значень коду набору відповідно для двох вище згаданих способів кодування від відносної довжини послідовності .
Рис. 2.1. Залежність пронормованих значень коду набору від відносної довжини послідовності : а) - при кодуванні звичайним двійковим кодом, б) - при використанні перестановчого кодування.
б) Верхню оцінку для кількості символів , що містить інформацію про довжину коду розміщення , одержимо при наявності рівноактивних джерел (, ), а саме: . Тоді
. (2.5)
в) Отже, при фіксованому наборі послідовності та інтервалі кускової стаціонарності витрати на номер послідовності, зведені до одного ненадлишкового вибіркового значення визначаються ентропією розподілу активностей джерел, для всієї послідовності у N разів більші, тобто
.
При апріорно невідомій статистиці активностей на інтервалі стаціонарності набір послідовності нефіксований. Кількість позицій і-ого джерела від послідовності до послідовності може змінюватися, а отже, й змінюється кількість можливих послідовностей Q. Усереднимо його логарифм за всіма m аналізованими послідовностями довжини N, тобто визначимо середні витрати двійкових символів власне на нумерування
,
де - ймовірність появи в s-тій послідовності вибіркових значень і-ого джерела.
Порівняємо і-ту складову попереднього виразу та ентропію активностей
,
враховуючи, що математичне очікування кількості Nі вибіркових значень і-ого джерела на означеному інтервалі стаціонарності , а також .
Для лівої частини:
.
Для правої:
.
Тепер порівняємо їх
.
Перенесемо усі члени нерівності пр
- Київ+380960830922