К.т.н. доцент Василенко В.С., Василенко М.Ю., Чунарьов А.В.

Національний авіаційний університет (НАУ), Україна

Визначення потрібної надлишковості в коді “зважених груп”.

Оптимальна надлишковість

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

· швидкість передачі інформації,

· час передачі інформації,

· загальний обсяг інформації тощо.

Але вона має бути достатньою для виявлення і виправлення заданого класу пам'яті. При цьому будемо розрізняти теоретичну мінімальну необхідну надлишковість та надлишковість, яка досягається при застосування конкретного коду. Як такий код в межах цієї роботи розглядається код зважених груп [1, 2, 3].

Постановка задачі. При визначенні теоретичної мінімально необхідної надлишковості врахуємо, що існує певна множина варіантів викривлень, наприклад викривлення можуть бути як в одному символі, так і в двох, трьох... чи в усіх символах одразу або може не бути взагалі. Для прикладу, розглянемо можливі варіанти викривлень в базовому кодовому слові (БКС). Нехай таке БКС має загальну розрядність в n двійкових символів, які розподіляються між m суто інформаційними та k надлишковими.

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

· Викривлення присутнє тільки в одному символі. Тоді загальну кількість таких варіантів можна записати у вигляді:

;

· Викривлення присутнє в будь-яких двох символах контрольної частини. Отже загальна кількість варіантів:

.

Для загального випадку і викривлень, маємо:

,

де .

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

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

.

Відомо, що сума під логарифмом є сумою коефіцієнтів в розкладанні бінома Ньютона і дорівнює [4]. Отже, двійковий логарифм від цієї суми дорівнює n. Тоді останній вираз набуває вигляду , де n є сумою кількостей символів інформаційної частини m і контрольної ознаки k. Оскільки, таке нерівняння є неможливим, то слід зробити висновок:

Створити код для виявлення і виправлення викривлень в n символах кратністю від 0 до n неможливо!

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

Для цього випадку мінімально необхідне значення розрядності контрольної частини можна розрахувати із виразу:

. (1)

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

ЛІТЕРАТУРА:

1. Василенко М.Ю. Цілісність інформаційних об’єктів та завадостійкий код “зважених груп”. Тези доповіді 5-ої міжнародної науково–практичної конференції «Научният потенциал на света – 2009», 17-25 септември, 2009, –Т.8. –С. 49-54.

2. Василенко М. Ю., Чунарьов А.В. Вибір вагових коефіцієнтів в коді “Зважених груп”. Тези доповіді 5-ої міжнародної науково–практичної конференції «ZPRÁVY VĚDECKÉ IDEJE - 2009», 27.10 - 05.11.2009, 2009,– Т. 12.–С. 33-36.

3. Василенко М.Ю., Чунарьов А.В. Вимоги щодо вагових коефіцієнтів в коді “зважених груп”. Strategiczne pytania swiatowej nauki – 2010. Тези доповіді 5-ої міжнародної науково-практичної конференції – Przemysl: Nauka i studia, 2010. – Т. 14.– С. 84-86.

4. Свойства биномиальных коэффициентов. На сайті: http://www.bymath.net/studyguide/alg/sec/alg31.html, – 2010.