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

Спосіб визначення надлишковості для коду "зважених груп", що полягає у здійсненні розраху 3 65206 коду. Як такий розглядають код «зважених груп», контрольна ознака якого розраховується з виразу: m R   ai  ci , (2) i1 де: m - кількість символів в інформаційній частині, ai - значення відповідних символів, Сі - їх вагові коефіцієнти. При визначенні теоретичної мінімально необхідної надлишковості враховують, що існує певна множина варіантів викривлень, наприклад викривлення можуть бути як в одному символі, так і в двох, трьох... чи в усіх символах одразу або може не бути взагалі. Для прикладу, розглядають можливі варіанти викривлень в базовому кодовому слові (БКС). Нехай таке БКС має загальну розрядність в n двійкових символів, які розподіляються між m суто інформаційними та k надлишковими. - Викривлення відсутні. Кількість таких подій дорівнює одиниці, або із використанням апарату n! 0 1; комбінаторики: C n  1 n! ! - Викривлення присутнє тільки в одному символі. Загальну кількість таких варіантів записують n! у вигляді: C 1  ; n 1 n  1! ! - Викривлення присутнє в будь-яких двох символах контрольної частини. Загальна кількість ваn! 2 ріантів: C n  . 1 n  2! ! Для загального випадку / викривлень, мають: n! i C n , де і=0, 1, 2, ..., n. 1! n  i! Оптимальну надлишковість знаходять як мінімально необхідне значення розрядності контрольної частини коду kн=min k, де k - надлишкові символи коду, призначеного для виявлення та виправлення викривлень певної кратності. Із викладеного витікає, що найменше необхідне значення розрядності контрольної частини при виявленні та виправленні викривлень будь-якої кратності знаходять із виразу:   n  0 2 kн  log2 Cn  C1  Cn  ...  Cn  log2   Cin   log2 2n  m  kн . n n   i 0   kн≥m+kн Сума під логарифмом є сумою коефіцієнтів в n розкладанні бінома Ньютона і дорівнює 2 . Отже, двійковий логарифм від цієї суми дорівнює n. Оскільки n=m+k то останній вираз набуває вигляду kн≥m+kн. Оскільки, така нерівність є неможливою, то слід зробити висновок: створити код для виявлення і виправлення викривлень в n символах кратністю від 0 до n неможливо. Для вирішення ж задачі виявлення і виправлення викривлень доцільно зробити припущення, що в каналі існують викривлення, але в обмеженій кількості символів, наприклад в tв символах. Таке припущення є справедливим для більшості реальних каналів. Надалі розглядають випадок наявності викривлень не більше ніж в одному із символів, тобто коли tв=1. Для визначення реального значення kр, необхідно і достатньо знати найбільше із можливих 4 значень контрольної ознаки R(A) коду, що розглядається. Тоді реальне значення кількості символів к контрольної частини R(A) знаходять формулою як функцію надлишковості (1): kp=f(max(RA)). (2) В двійковій системі числення двійкове число представляється як послідовність нулів і одиниць. Отже ai може приймати значення або 0 або 1. Контрольна частина R(A) прийме максимальне значення тільки тоді, коли кожний елемент інформаційної частини дорівнює ai=1, бо 1 - найбільше число в двійковій системі числення. Таким чином, виходячи з цих міркувань, величина max R(А) набуде вигляду: m max RA    ci (3) i1 Формують правило вибору вагових коефіцієнтів: вагові коефіцієнти розрядів інформаційних частин мають бути більшими ніж основа системи i числення р та не повинні дорівнювати величині р (і=0, 1, 2, ...), в той час як вагові коефіцієнти контрольних символів повинні дорівнювати величині р\ Тоді вагові коефіцієнти розрядів інформаційних частин ct в двійковій системі числення можуть дорівнювати: 3, 5, 6, 7, 9, 10, 11, .... Тобто дорівi нюють усім числам, окрім 2 (i=0, 1, 2, ..., k-1). Отже, сукупність вагових коефіцієнтів інформаційних та контрольних розрядів можна вважати такою, що утворює ряд натуральних чисел від 0 до n. Для знаходження суми вагових коефіцієнтів інформаційної частини коду m  ci використають i 1 той факт, що вона дорівнює сумі усіх вагових коефіцієнтів за виключенням суми вагових коефіцієнтів контрольних розрядів. Окрім того, врахують, що перша із цих сум є сумою членів арифметичної прогресії від 1 до n із різницею, що дорівнює 1, а друга є сумою членів геометричної прогресії від 1 k-1 до 2 із знаменником 2. Тоді:  ci  1 n  n 2   2i  1 n  n 2  2k 1  1/2  1  1 n  n 2  2k 1  1 m k 1 i1 i 0 Тоді вираз (4) можна записати у наступному вигляді: k-1 max R(A)=(1+n)-n/2-2 +1. Функція f у виразі (2) є логарифмічною за основою р, яка для двійкової системи дорівнює 2. Таким чином, для розробленого коду вираз (2) набуде наступного вигляду: k 1 kp  log2  1  n  n / 2  2 p  1 .   (4)   Звернуть увагу, що шукане значення kр знаходиться в обох частинах нерівність (4). З нерівності (4) знайдуть вираз для розрахунку нижньої межі реально потрібної розрядності контрольної ознаки для коду, що розглядається, kр. Для цього здійснять наступну низку перетворень. k 1 kp  log2  1  n  n / 2  2 p  1 ,      1  n  n / 2  2 k p 1 kp 2 k p 1 22 k p 1 2  1,  1  n  n / 2  1 , 5 65206 2 p  1  n  n / 6  1/ 3 . Таким чином, нижня межа реально потрібної розрядності контрольної ознаки для коду, що розглядається, kр може бути визначеною із нерівності: kр≥1+log2((1+n)-n/6+1/3). (5) Верхню межу реально потрібної розрядності контрольної ознаки для коду, що розглядається, kр можна знайти шляхом аналізу підлогарифмічного виразу в нерівності (5), значення якого не може бути від'ємним. Отже, після низки наступних перетворень: 6 При визначенні реально потрібної розрядності контрольної ознаки (для коду, що розглядається) kр врахують, що ця величина може приймати лише цілочисельне значення. Тоді в виразах (5) та (6) замість можливих дробових значень логарифмів використають їх найближче більше ціле, наприклад здійснять перехід типу: log2((1+n)·n/6+1/3)→[log2((1+n)·n/6+1/3)]+1. В цій формулі [X] - означає обчислення цілої частини від X. Результати розрахунків за виразами (5) та (6) зведено в порівняльну таблицю 1. Одержані результати дозволяють стверджувати, що надлишковість, якої потребує код «зважених груп» при малих розрядностях БКС (n) не перевищує оптимальної, а в разі збільшення розрядності БКС (n) є несуттєво більшою за оптимальну. Джерела інформації: 1. Скляр Б. Цифровая связь. Теоретические основы и практическое применение. 2-е издание. Пер. с англ. - М.: Издательский дом "Вильяме", 2003. - 1104 с. 2. Юдін O.K. Кодування в інформаційнокомунікаційних мережах - Монографія. - К.: Книжкове видавництво НАУ, 2007. - 302 с. k 1 1  n  n  2k  2  0 , k 2  1  n  n  2 , kp  log2 1  n  n  2 ,  kp  log2 2  1 n  n / 2  1  , p p kp