Размещено на http://www.allbest.ru/

Міністерство освіти і науки України

Сумський державний університет

(СумДУ)

ЗВІТ

про науково-дослідну роботу

«Методи і засоби побудови біноміальних цифрових пристроїв для телекомунікаційних систем»

Начальник НДЧ

к. ф.-м. н.

Д.І. Курбатов

Керівник НДР

д.т.н., професор

О.А. Борисенко

2014

СПИСОК АВТОРІВ

Керівник НДР: головний науковий співробітник, д.т.н., професор	(2014.12.12)	О.А. Борисенко Вступ, висновки, розділ 1, 2, 3, 8
Молодший науковий співробітник	(2014.12.12)	О.М. Скордіна розділ 4
Молодший науковий співробітник	(2014.12.12)	О.В. Іванчук розділ 5, 6, 7

РЕФЕРАТ

Заключний звіт про НДР: 71 стор., 20 рис., 7 табл., 37 літературних джерел.

Об'єкт досліджень: розробка цифрових пристроїв для телекомунікаційних систем.

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

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

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

біноміальний цифровий телекомунікаційний завадостійкий

БІНОМІАЛЬНА СИСТЕМА ЧИСЛЕННЯ, ЗАВАДОСТІЙКІСТЬ, ВІДМОВОСТІЙКІСТЬ, ТЕЛЕКОМУНІКАЦІЙНА СИСТЕМА, ЦИФРОВІ ПРИСТРОЇ, ЗАХИСТ ІНФОРМАЦІЇ, НАДЛИШКОВІСТЬ, БІНОМІАЛЬНИЙ КОД.

ЗМІСТ

Перелік умовних скорочень

Вступ

Розділ 1. Біноміальні системи числення і їх характеристика

Розділ 2. Лічба двійкових біноміальних чисел

Розділ 3. Двійкові біноміальні пристрої лічби

Розділ 4. Розробка біноміальних перетворювачів кодів і їх дослідження

Розділ 5. Захист інформації на базі лінійних двійкових біноміальних пристроїв лічби

Розділ 6. Розробка телекомунікаційних систем на основі двійкових біноміальних лічильних пристроїв

Розділ 7. Розробка телекомунікаційних систем на основі двійкових біноміальних лічильних пристроїв із захистом від несанкціонованого доступу

Розділ 8. Оцінка ефективності телекомунікаційних систем на лічильниках

Висновки

Перелік посилань

ПЕРЕЛІК УМОВНИХ СКОРОЧЕНЬ

КЗО - квазізамкнений обєм

БСЧ - біноміальна система числення

БЧ - біноміальне число

ДБК - двійковий біноміальний код

КРК - квазірівноважний код

ЛЦБСС - лінійно-циклічна біноміальна система числення

ВСТУП

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

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

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

РОЗДІЛ 1

БІНОМІАЛЬНІ СИСТЕМИ ЧИСЛЕННЯ ЇХ ХАРАКТЕРИСТИКА

Лінійні двйкові біноміальні системи числення

Нижче пропонуються розроблені авторами структурні комбінаторні системи числення з біноміальними вагами й двійковим алфавітом {1, 0} - біноміальні двійкові системи числення [1-3]. Їхній діапазон

Визначення 1. Система числення, у якій кількісний еквівалент кодової комбінації,, визначається виразом:

(1.1)

при дотриманні обмежень:

де - число одиниць у біноміальному числі;

- параметр системи числення;

- кількість розрядів біноміального числа (довжина);

- порядковий номер розряду;

- сума одиничних значень цифр від ( )-го розряду до ( )-го включно:

, (1.8)

,

,

називається лінійною біноміальною системою числення, а число - лінійним біноміальним двійковим числом.

Система числення повинна задовольняти вимогам скінченності, ефективності, однозначності. Однак цих вимог для нестепенних систем числення недостатньо.

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

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

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

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

Біноміальні кодові комбінації, що задовольняють обмеженням (1.2 - 1.4), повинні містити одиниць. Тому поява в біноміальній комбінації -й одиниці є ознакою її кінця. Тому що відповідно до обмеження (1.3) найбільша довжина зазначених комбінацій рівна, тоді їх довжини приймають значення в межах від до ( ). Відповідно кількість нулів, що містяться в них, а довжина . Кількість комбінацій, що різняться, однакової довжини, що місять одиниць та нулів, дорівнює числу сполучень нулів з елементів . Ці комбінації, будучи сполученнями, мають по відношенню одна до одної очевидну властивість префіксності. Довжини комбінацій, що належать до груп з різним значенням , різні. Тому що наприкінці цих комбінацій містяться одиниці і їх загальне число постійне й дорівнює , тоді більш довгі комбінації в префиксній частині, рівній довжині меншої комбінації, містять, як мінімум, на одну одиницю менше.

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

Як випливає з (1.5 - 1.7), число нулів у біноміальних комбінаціях є постійним і рівним (). Тому поява ( )-го нуля в комбінації представляє ознаку її закінчення. Сума ( ) нулів із числом одиниць визначає довжину біноміальних комбінацій. Число різних комбінацій з одиницями й нулем наприкінці визначається кількістю комбінацій одиниць із ( ) елементів - . Властивість префиксності для них очевидно [1,5-6].

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

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

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

и ,

де , ; ; ; .

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

Представимо числа й у вигляді

,

.

Так як

і , то .

Отже, властивість однозначності для біноміальної системи числення виконується.

Максимальне число в біноміальній системі числення відповідно до виразу (1.1)

,

а мінімальне число дорівнює нулю.

Кількість біноміальних комбінацій, що містять наприкінці одиницю,

. (1.9)

Число комбінацій, що містять наприкінці нуль,

. (1.10)

Їхня сумарна кількість

. (1.11)

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

Лінійно-циклічні біноміальні системи числення

Визначення 2. Система числення, побудована на основі однієї або ряду лінійно розташованих послідовностей біноміальних коефіцієнтів із циклічно виконуваними над ними операціями, називається лінійно-циклічною біноміальною системою числення (ЛЦБСС) [7-8].

Біноміальні коефіцієнти у використовуваних ЛЦБСС послідовностях розташовані у зворотному порядку в порівнянні з розглянутими раніше, тобто порядок розташування біноміальних коефіцієнтів в i-й послідовності

……

заміняється при її використанні в ЛЦБСС на зворотний:

,

; .

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

Це значить, що використовувані в ЛЦБСС послідовності як молодшого розряду будуть мати перший розряд і відповідно набудуть вигляду

.

Отримані в такий спосіб біноміальні послідовності будуть розташовуватися в наступному порядку:

, .

Найважливішою властивістю цих послідовностей є можливість представити кожний біноміальний коефіцієнт за допомогою суми коефіцієнтів попередньої послідовності плюс 1.

Так, наприклад, коефіцієнт для послідовності із представляється сумою коефіцієнтів попередньої послідовності з у такий спосіб:

. (1.12)

У загальному випадку стосовно до будь-якого наведена властивість послідовностей біноміальних коефіцієнтів буде мати такий вигляд:

. (1.13)

Наприклад, якщо дані символьні біноміальні послідовності , , , то на основі властивості, що розглядається одержимо

, , , .

Саме на цій властивості заснована робота ЛЦБСС.

Визначення 3. Функція

, (1.14)

де - цифри, що задаються -й послідовністю, називається -й частковою числовою функцією (окремим числом) двійкової ЛЦБСС.

Визначення 4. Функція

(1.15)

називається числовою функцією ЛЦБСС або числом у ЛЦБСС.

Визначення 5. Біноміальні коефіцієнти, що входять у числову функцію ЛЦБСС, називаються її вагами.

Припустимо, що в послідовності цифра й наступні за нею цифри молодших розрядів, рівні 1, а попередні їй цифри рівні 0. У цьому випадку відповідно до (1.14) окрема числова функція

(1.16)

або

. (1.17)

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

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

Установка в 1 розрядів числа відбувається в результаті аналогічних циклів рахунку в числі, а в того після циклів рахунку в числі і т.д. до числа

, (1.18)

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

Якщо після проведених циклів рахунку в ( )-м частці числі в усіх без винятку розрядах будуть стояти одиниці, то

. (1.19)

Число, що містить одиниці у всіх розрядах, представляє найбільше число, яке можна представити в ЛЦБСС. Як випливає из рівності (1.19),

. (1.20)

Відповідно діапазон чисел, які можна представити у ЛЦБСС

. (1.21)

Отримані вище співвідношення дозволяють сформулювати правило перебору (рахунку) лінійно-циклічних біноміальних чисел [9].

Воно полягає в послідовному заповненні по циклах одиницями розрядів числа, починаючи з -го й до першого включно, і потім вироблення 1 переносу в -й розряд сусіднього старшого числа й обнулення молодших розрядів [9,10].

Починається рахунок з нульового числа з розряду заповненням одиницями всіх молодших розрядів до розряду з , потім з розряду і так далі. Щораз після заповнення одиницями всіх молодших розрядів числа утворюються переноси в сусіднє старше число й обнуляются власні розряди. Потім аналогічні цикли відбуваються із числами, і так до . Цикли закінчуються, коли в старшому числі у всіх розрядах з'являться одиниці [9,11].

Наприклад, якщо є представлені в числовому виді три послідовності біноміальних коефіцієнтів з параметрами,,: 6 3; 3 2 і 1 1, то для них відповідно до (1.13, 1.14) є три числові функції:

,

,

,

які спільно утворюють числову функцію ЛЦБСС:

У символьній формі вона має вигляд

.

У вихідному стані при рахунку всі цифри числа F,, рівняються 0, тобто . Потім цифра числа перетвориться в 1 ( ), а за нею в 1 переходить цифра ( ). Після цього відбувається перенос 1 у сусіднє ліворуч число в другий розряд: . Потім процедура рахунку повторюється з тієї істотною різницею, що занесення 1 у число відбувається не в другий розряд, а в перший: і після відбувається перехід у перший розряд числа ( ). Після появи двох одиниць у числі відбувається обнулення його розрядів і одночасно здійснюється перенос 1 у другий розряд числа ( ). Процес рахунку закінчується, коли число прийме вигляд 11 00 00.

Процедура лінійно-циклічного біноміального рахунку в зростаючому порядку всіх чисел з діапазону, одержуваних на основі біноміальних послідовностей із числом розрядів і значенням параметра, наведена в табл.1.1. У цьому випадку числа й представляють параметри ЛЦБСС, за допомогою яких відповідно визначається число розрядів у окремих числових функціях і число послідовностей біноміальних коефіцієнтів.

аблиця 1.1 - Лінійно-циклічні біноміальні числа

Номер числа	Ваги 6 3	Ваги 3 2	Ваги 1 1
0	0 0	0 0	0 0
1	0 0	0 0	1 0
2	0 0	0 0	1 1
3	0 0	1 0	0 0
4	0 0	1 0	0 1
5	0 0	1 1	0 0
6	1 0	0 0	0 0
7	1 0	0 0	0 1
8	1 0	0 1	0 0
9	1 1	0 0	0 0

РОЗДІЛ 2

ЛІЧБА ДВІЙКОВИХ БІНОМІАЛЬНИХ ЧИСЕЛ

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

Таблиця 2.1 - Біноміальні числа з їхніми кількісними еквівалентами

Біноміальне число	Кількісний еквівалент
00
010
0110
01110
01111
100
1010
10110
10111
1100
11010
11011
11100
11101
1111

Алгоритм біноміальної двійкової лічби містить наступні кроки [12,14]:

1. Формується початкова комбінація, що складається з ( ) нулів.

2. В нульовий розряд записується одиниця й перевіряється число одиниць у комбінації.

3. Якщо число одиниць менше , то праворуч від отриманої 1 записується 0 і далі перехід до пункту 2.

4. Пункт 2 повторюється доти, поки число одиниць у кодовому слові не стане рівним k.

5. Якщо одиниць займають у комбінації старших розрядів, тоді зупинка, а якщо ні, то в розряд, що містить молодший 0, записується 1.

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

7. Повернення до пункту 2.

8. Якщо число одиниць у комбінації по пункту 6 стало рівним , то перехід до пункту 5.

Корисними властивостями біноміальної лічби є її завадостійкість і можливість організації на її підставі перебору комбінацій різних комбінаторних кодів [13].

Для виявлення помилок за допомогою біноміальних комбінацій необхідно доповнити їхніми нулями або одиницями до одержання рівномірного ( )-розрядного біноміального коду, як це наведено в табл. 2.2.

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

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

Таблиця 2.2 - Нерівномірні й рівномірні біноміальні числа

Номер	Біноміальний код	Біноміальний рівномірний код	Номер	Біноміальний код	Біноміальний рівномірний код
0	00	00000	8	10111	10111
1	010	01000	9	1100	11000
2	0110	01100	10	11010	11010
3	01110	01110	11	11011	11011
4	01111	01111	12	11100	11100
5	100	10000	13	11101	11101
6	1010	10100	14	1111	11110
7	10110	10110

Таблиця 2.3 - Біноміальні числа з відповідними їм рівноважними комбінаціями

Номер	Біноміальний код	Код c постійною вагою	Номер	Біноміальний код	Код c постійною вагою
0	00	001111	8	10111	101110
1	010	010111	9	1100	110011
2	0110	011011	10	11010	110101
3	01110	011101	11	11011	110110
4	01111	011110	12	11100	111001
5	100	100111	13	11101	111010
6	1010	101011	14	1111	111100
7	10110	101101

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

Розглянуту вище, процедуру рахунку лінійно-циклічних біноміальних чисел у загальному виді можна представити у вигляді наступного алгоритму [15,16]:

1. Формується початкове число, що складається із окремих чисел , , що містять по нулів.

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

3. Відбувається перенос 1 в -й розряд числа .

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

5. Пункт 4 повторюється доти, поки не буде заповнено одиницями число , а в числі не будуть стояти нулі.

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

7. Рахунок буде тривати за аналогією з наведеними вище пунктами доти, поки всі розряди числа не встановляться в 1.

Кінець.

З наведеного алгоритму рахунку в ЛЦБСС випливає наступне обмеження [1,4]:

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

б) загальне число одиниць у числі ;

в) у всіх числах, за винятком нульового, в -м розряді одного із окремих чисел повинна бути присутнім 1;

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

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

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

Звідси випливає висновок, що лінійно-циклічні біноміальні числа з діапазону однозначним образом кодують натуральні числа, починаючи з 0 і до .

РОЗДІЛ 3

ДВІЙКОВІ БІНОМІАЛЬНІ ПРИСТРОЇ ЛІЧБИ

На рис. 3.1 наведений біноміальний п'ятирозрядний лічильник імпульсів з n = 5 і контрольним числом k = 4; на рис. 2 - реалізація одного із суматорів [5-7].

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

Лічильник імпульсів працює в такий спосіб. У вихідному стані всі тригери лічильника коштують в ''0'', тобто лічильник перебуває в нульовому стані 00000. На нульовому виході суматора 7.1 відповідно є одиничний сигнал, який проходить, через елемент АБО 6.3 на вхід елемента І 4.4. Тому що з одиничного виходу тригера 2.4 надходить нульовий сигнал на елемент АБО 1.4 елемент В 5.4 закритий нульовим сигналом, а елемент І 4.4 відкритий одиничним сигналом з елемента НЕ 3.4. Тому тактовий сигнал, що надходить на вхідну шину 8, установлює тригер 2.4 в одиничний стан 01000, відповідно на першому виході суматора 7.1 з'являється одиничний сигнал, який через елемент АБО 6.2 дає дозвіл елементу І 4.3 на установку в одиничний стан тригера 2.3, тобто лічильник по тактовому імпульсу переходить у стан 01100. Аналогічно отримані стани 01110 і 01111.

Тому що при стані лічильника 01111 тригер 2.1 перебуває в одиничному стані й, отже, на виході елемента АБО 1.1 і вході елемента І 5.1 є "1", те наступний тактовий сигнал установлює тригер 2.1 в "0" і з виходу елемента І 5.1 проходить на вхід елемента 5.2 І й скидає його в нуль. Аналогічно скидання тригерів поширюється до тригера 2.5. Тому що він перебуває в нулі елемент АБО 1.5 видає ''0'' і через елемент НЕ 3.5 дозволяє сигналу скидання встановити його в "1", тобто одержують стан 10000. При цьому на першому виході суматора 7.1 є присутнім одиничний сигнал. Цей сигнал через елементи АБО 6.2 і І 4.3 установлює тригер 2.3 в ''1", у результаті лічильник перебуває в стані 10100. По наступних тактових імпульсах, за аналогією з вищеописаним, відбувається установка в "1" другого й першого розрядів лічильника. У результаті одержують наступні стани: 10110 і 10111. По наступному тактовому імпульсу відбувається скидання в "0" тригерів 2.1 - 2.3 і записується "1" у тригер 2.4 - 11000. Потім процес запису "1" у молодші розряди повторюється - 11100, 11110. У стані лічильника 11110 на 4-ом виході суматора 7.1 з'являється одиниця. Вона дозволяє проходження тактовому імпульсу через елемент І 5.1 на вхід установки в "0" тригера 2.1 і подальшому його поширенню через елементи І 5.2 - 5.5. У результаті лічильник переходить у вихідне (нульове) положення (00000) [8-9].

У пропонованій схемі єдиним забороненим станом, що виявляється, є стан 11111. У цьому випадку відбувається переповнення суматора 7.1 і на виході “помилка” суматора 7.1 зявляється сигнал помилки. Однак при цьому завадостійку здатність лічильника можна підвищити, змінивши контрольну цифру k, тобто число зворотних зв'язків із суматора 7.1. Чим їх менше, тим більше завадостійка здатність лічильника. Наприклад, при k = 2 помилкові стани лічильника 01110; 10011; 11100 будуть виявлені. У цьому випадку на 5-м виході суматорів відповідно (7.2, 7.1), (7.1), (7.3, 7.2, 7.1) з'являється сигнал помилки. Усі стани лічильника наведені в табл.3.1.

Рисунок 3.1 - П'ятирозрядний двійковий біноміальний лічильник імпульсів

Суматор (рис. 3.2) є матричним і містить першу групу 9 з (k +1) елементів І 10, другу групу 11 з (k +1) елементів І 12 і групу 13 з k елементів АБО 14, першу групу 15 і другу групу 16 входів, групу з k + 2 виходів - 0, 1, …, k, k + 1.

Рисунок 3.2 - Матричний суматор

Входи суматора із групи 15 з'єднані відповідно з першими входами елементів І 10 і з першими входами елементів І 12, другі входи відповідної пари з елементів І 10 і І 12 з'єднані з відповідними входами із другої групи 16, входи кожного з елементів АБО 14 із групи 13 з'єднані з виходами відповідних елементів І 10 і І 12 із груп 9 і 11 [15].

Таблиця 3.1 - Стани біноміального лічильника

Номер біном. числа	Розряди	Номер біном. числа	Розряди
	5	4	3	2	1		5	4	3	2	1
0	0	0	0	0	0	8	1	0	1	1	1
1	0	1	0	0	0	9	1	1	0	0	0
2	0	1	1	0	0	10	1	1	0	1	0
3	0	1	1	1	0	11	1	1	0	1	1
4	0	1	1	1	1	12	1	1	1	0	0
5	1	0	0	0	0	13	1	1	1	0	1
6	1	0	1	0	0	14	1	1	1	1	0
7	1	0	1	1	0

Наявність одиниці на виході k + 1 суматора свідчить про те, що в результаті підсумовування відбулася помилка (сума одиниць більше k).

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

РОЗДІЛ 4

РОЗРОБКА БІНОМІАЛЬНИХ ПЕРЕТВОРЮВАЧІВ КОДІВ І ЇХ ДОСЛІДЖЕННЯ

Для використання біноміального кодування в пристроях дискретної обробки інформації, необхідно розробити пристрої перетворення кодів, зокрема пропонуються пристрої завадостійкого перетворення інформації з використанням квазірівноважного коду [31-33].

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

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

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

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

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

В табл.4.1 наведена відповідність рівномірних біноміальних кодових комбінацій з параметрами n = 5 та k = 4 квазірівноважним комбінаціям з параметрами n_к = 5, k₁ = 4, k₂ = 3.

Таблиця 4.1 - Відповідність між комбінаціями рівномірного біноміального та квазірівноважного коду

Номер комбінації	Рівномірна біноміальна кодова комбінація з параметрами n = 5 та k = 4	Квазірівноважна кодова комбінація nк = 5, k1 = 4, k2 = 3.
0	0	0	0	0	0	0	0	1	1	1
1	0	1	0	0	0	0	1	0	1	1
2	0	1	1	0	0	0	1	1	0	1
3	0	1	1	1	0	0	1	1	1	0
4	0	1	1	1	1	0	1	1	1	1
5	1	0	0	0	0	1	0	0	1	1
6	1	0	1	0	0	1	0	1	0	1
7	1	0	1	1	0	1	0	1	1	0
8	1	0	1	1	1	1	0	1	1	1
9	1	1	0	0	0	1	1	0	0	1
10	1	1	0	1	0	1	1	0	1	0
11	1	1	0	1	1	1	1	0	1	1
12	1	1	1	0	0	1	1	1	0	0
13	1	1	1	0	1	1	1	1	0	1
14	1	1	1	1	1	1	1	1	1	0

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

Перетворювач кодів, отриманий в роботі, побудований на основі біноміального лічильника, шляхом введення до нього нових елементів і нових зв'язків, що дозволяє здійснювати генерування комбінацій квазірівноважного коду з параметрами n_к, k₁, k_2. Це забезпечує розширення його функціональних можливостей, як перетворювача кодів з біноміального в квазірівноважний [33].

Поставлене завдання вирішується тим, що у відомий біноміальний лічильник, що містить вхідну шину і n розрядів, кожен з яких містить тригер, два елементи І, перший елемент АБО, елемент НІ і суматор, а в розряди з другого по k-й, де k - контрольне число менше числа розрядів, але більше нуля, введений другий елемент АБО, перша група входів суматора з'єднана з прямим і інверсним виходами тригера, входи установки в одиницю і в нуль якого з'єднані відповідно з виходами першого і другого елементів І, перший вхід другого елементу І з'єднаний з входом елементу НІ, вихід якого з'єднаний з першим входом першого елементу І, другі входи першого і другого елементів І кожного розряду, починаючи з (k + 1)-го, з'єднано з виходом другого елементу І попереднього розряду, друга група входів суматора якого з'єднана з виходами суматора подальшого розряду, вхідна шина з'єднана з другими входами першого і другого елементів І першого розряду. У кожному розряді перший і другий входи, а також вихід першого елементу АБО з'єднані відповідно з прямим виходом тригера, виходом суматора, що відповідає k-му числу, і з входом елементу НІ, вихід другого елементу АБО з'єднаний з другим входом першого елементу І, третій вхід якого з'єднаний з вхідною шиною, перший вхід другого елементу АБО з'єднаний з виходом другого елементу І попереднього розряду, виходи суматора першого розряду, відповідні числам з «0» по (k - 1), з'єднані відповідно з другими входами других елементів АБО з k-го розряду по другий і з третім входом першого елементу І першого розряду, додатково введені перетворювач паралельного коду в послідовний, інформаційні входи якого, з'єднані з другою групою виходів суматора першого розряду відповідно, лічильник нулів та лічильник кількості розрядів, перші входи яких з'єднані з виходом перетворювача паралельного коду в послідовний, вихід лічильника нулів з'єднаний з керуючими входами перетворювача паралельного коду в послідовний та лічильника кількості розрядів, дешифратор, на входи 1,2, ..., f-й, де f= , якого заведені відповідно 1,2, …, f-й виходи лічильника кількості розрядів, група (k - 2)-х елементів АБО, на перший вхід першого елемента АБО цієї групи заведений вихід дешифратора (n - k + 1), на другі входи цієї групи елементів АБО заведені (n - k + 2), (n - k + i), …. , n-й виходи дешифратора відповідно, а виходи кожного попереднього елементу групи (k - 2)-х елементів АБО з'єднані з першими входами подальших елементів АБО цієї групи відповідно, група (k - 1)-х елементів ВИКЛЮЧАЮЧЕ-АБО, на перші входи яких заведені друга група виходів суматора першого розряду відповідно, а на другі входи починаючи з другого елементу цієї групи елементів ВИКЛЮЧАЮЧЕ-АБО заведені виходи групи (k - 2)-х елементів АБО відповідно, тоді як на другий вхід першого елемента ВИКЛЮЧАЮЧЕ-АБО заведений (n - k + 1)-й вихід дешифратора, регістр, входи 1',2', … ,і, … ,(k - 1)-й якого з'єднані з виходами групи елементів ВИКЛЮЧАЮЧЕ-АБО відповідно та на 1,2, … ,j, … ,(n - k + 1)-й входи якого заведені 1,2, … ,j, … ,(n - k + 1)-й виходи другої групи виходів суматора першого розряду, а вихід регістра є виходом пристрою [25-27].

Введення вищезгаданих елементів надає можливість розширити функціональні можливості пристрою, тому що, окрім генерування рівномірних біноміальних комбінацій з параметрами n та k з'являється здатність формування квазірівноважних комбінацій з параметрами n_к, k₁, k₂, що реалізується за рахунок перетворення рівномірних біноміальних комбінацій у квазірівноважний код.

На рис 4.1 наведений біноміальний лічильник квазірівноважних комбінацій, який складається з біноміального лічильника і перетворювача рівномірних біноміальних комбінацій з параметрами n та k в квазірівноважні. з параметрами n_к = n, k₁ = k, k₂ = k - 1.

Перетворювач коду містить перші елементи АБО 1.1-1.n, тригери 2.1-2.n, елементи НІ 3.1-3.n, перші елементи І 4.1-4.n, другі елементи І 5.1-5.n, другі елементи АБО 6.1-6.n, суматори 7.1-7.n, вхідну шину 8, перетворювач 9 паралельного коду в послідовний, лічильник 10 нулів, лічильник 11 кількості розрядів, дешифратор 12, групу елементів АБО 13.1-13.k - 2, групу елементів ВИКЛЮЧАЮЧЕ-АБО 14.1-14.k-1, регістр 15, вихід 16 пристрою[18,19-23].

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

Перші групи входів суматорів 7.1-7.n з'єднані з прямим і інверсним виходами тригерів 2.1-2.n, входи установки в одиницю яких з'єднані відповідно з виходами перших елементів І 4.1-4.n, входи установки в нуль тригерів 2.1-2.n з'єднані відповідно з виходами других елементів І 5.1-5.n, перші входи других елементів I 5.1-5.n з'єднані відповідно з виходами перших елементів АБО 1.1-1.n, які також з'єднані з входами елементів НІ 3.1-3.n, виходи яких з'єднані з першими входами перших елементів І 4.1-4.n, виходи других елементів І 5.1-5. j - 1 з'єднані відповідно з першими входами других елементів АБО 6.1-6.j - 1, а вихід елемент І 5.j з другим входом першого елементу І 4.j + 1, також перші входи других елементів АБО 6.1-6.j -1 з'єднані відповідно з другими входами других елементів І 5.2-5.n, другі входи перших елементів І 4.2-4.j з'єднані відповідно з виходами других елементів АБО 6.1-6.j - 1, вхідна шина 8 з'єднана з другим входом першого елементу І 4.1, з другим входом другого елементу І 5.1 із третіми входами перших елементів І 4.2-4.j, перші входи перших елементів АБО 1.1-1.n з'єднані відповідно з прямими виходами тригерів 2.1-2.n, другі входи перших елементів АБО 1.1-1.n з'єднані з виходами суматорів 7.1-7.n, що відповідають контрольному числу k, другі групи входів суматорів 7.1-7.j з'єднані відповідно з виходами суматорів 7.2-7.n, а виходи суматора 7.1 з

Рисунок 4.1 - Квазірівноважний лічильник

інформаційними входами перетворювача перетворювача 9 паралельного коду в послідовний,вихід якого з'єднаний з входом лічильника 10 нулів, вихід якого з'єднаний з другим входом перетворювача 9 паралельного коду в послідовний та другим входом лічильника 11 кількості розрядів, перший вхід якого з'єднано з виходом перетворювача 9 паралельного коду в послідовний, виходи 1,2, … ,f-й лічильника 11 кількості розрядів відповідно з'єднані з 1,2, … ,f-м входами дешифратора 12, (n - k + 1)-й вихід якого заведений на другий вхід елемента ВИКЛЮЧАЮЧЕ-АБО 14.1, а виходи (n - k + 2), … ,(n -k + i),…,n-й заведені на другі входи елементів АБО 13.1-13.k - 2 відповідно, тоді на перші входи елементів АБО 13.2-13.k - 2 будуть заведені виходи елементів АБО 13.1-13.k - 3 відповідно, тоді на перший вхід елемента АБО 13.i буде заведений вихід елемента АБО 13.i - 1, а на другий вхід буде заведений (n - k + i)-й вихід дешифратора 12, а вихід підключений до першого входу елемента АБО 13. i + 1 та заведений на другий вхід елементу ВИКЛЮЧАЮЧЕ-АБО 14.і, виходи елементів АБО 13.1-13.k - 2 заведені на другі входи елементів ВИКЛЮЧАЮЧЕ-АБО 14.2-14.k - 1 відповідно, перші входи елементів ВИКЛЮЧАЮЧЕ-АБО 14.1-14.k - 1 під'єднані до 1',2',…,і,…,(k - 1)-го виходів суматора 7.1, виходи елементів ВИКЛЮЧАЮЧЕ-АБО 14.1-14.k - 1 під'єднані до 1',2',…,і,…,(k - 1)-го входів регістра 15 відповідно, на входи 1,…,j,…,(n - k + 1)-й регістра 15 заведені виходи 1,…,j,…,(n - k + 1)-й суматора 7.1, вихід 16 регістра 15 є виходом пристрою [24].

Перетворювач кодів працює таким чином.

В початковому стані всі тригери 2.1-2.n встановлені в нуль, тобто перетворювач кодів знаходиться у нульовому стані і на другій групі виходів суматора 7.1 міститься комбінація 0000..0, яка надходить на інформаційні входи перетворювача 9 паралельного коду в послідовний, після чого на виході перетворювача 9 з'являється починаючи зі старшого розряду рівномірна біноміальна комбінація з параметрами n і k, довжина комбінації рівна n, вона надходить на вхід лічильника 10 нулів, який підраховує кількість нулів у послідовності і має модуль лічби (n - k + 1), та на перший вхід лічильника 11 кількості розрядів, який підраховує кількість розрядів біноміальної комбінації і має модуль лічби, який задається лічильником кількості нулів, оскільки вихід лічильника 10 нулів заведений на керуючий вхід лічильника 11 кількості розрядів, який відповідає за зупинку лічби, тому, коли лічильник 10 нулів підрахує (n - k + 1) нулів, на його виході встановлюється одиниця, цей сигнал надходить на керуючий вхід перетворювача 9, що зупиняє передавання біноміальної комбінації та на керуючий вхід лічильника 11 кількості розрядів, що зупиняє роботу лічильника 11, таким чином модуль лічби лічильника 11 кількості розрядів буде належати проміжку (n - k + 1) ? r ? n, де r - кількість розрядів, підрахована лічильником 11 кількості розрядів, тому для визначення максимальної кількість виходів лічильника 11 кількості розрядів застосовується наступна формула [15-18]:

f=.

Тоді комбінація, що відповідає за стан лічильника 11 кількості розрядів з'являється на його 1,2, … ,f-му виходах, вона відповідно надходить на 1,2, … ,f-й входи дешифратора 12. Після чого, в залежності від комбінації на входах дешифратора 12 його виходи можуть бути встановлені в один з (k - 1) дозволених станів, причому номери виходів дешифратора 12, на яких з'являються одиничні сигнали, будуть адресувати номери r_n-х розрядів біноміальних комбінацій, що підлягають перетворенню, ці номери задаються параметрами біноміальних комбінацій n та k і належать проміжку (n - k + 1)< r_n ? n. Тобто, після того, як дешифратор 12 буде встановлений в один з дозволених станів і на його (n - k + і)-му виході з'явиться сигнал високого рівня, він надійде на другий вхід елемента АБО13.і, а на його першому вході буде сигнал низького рівня з виходу елемента АБО 13.і - 1, тоді на виході елемента АБО 13.і встановлюється сигнал високого рівня, який надходить на перший вхід елемента АБО 13.і + 1, що встановлює його вихід в одиничний стан і далі в такий спосіб встановлюється сигнал високого рівня на виходах елементів АБО 13.і-13.k - 2 і надходить на другі входи елементів ВИКЛЮЧАЮЧЕ-АБО 14.і-14.k - 1, що дає дозвіл на перетворення відповідних розрядів біноміальної комбінації. Тоді як на другий вхід елемента ВИКЛЮЧАЮЧЕ-АБО 14.1 надходить сигнал з (n - k + 1)-го виходу дешифратора 12, а на другий вхід елемента ВИКЛЮЧАЮЧЕ-АБО 14.2 надходить сигнал з виходу елемента АБО 13.1, на перші входи елементів ВИКЛЮЧАЮЧЕ-АБО 14.1-14.k - 1 надходять сигнали відповідно від 1',2', … ,(k - 1)-го виходів суматора 7.1, якщо на другі входи елементів ВИКЛЮЧАЮЧЕ-АБО 14.2-14.k - 1 надійшов одиничний сигнал від елементів АБО 13.1-13.k - 2, а на перші входи надходить нульовий сигнал з виходів суматора 7.1, то на виході відповідних елементів ВИКЛЮЧАЮЧЕ-АБО 14.2-14.k - 1 встановляться одиничні сигнали, тобто всі розряди біноміальної комбінації починаючи з r_n, які дорівнювали нулю, стануть рівні одиниці, інші розряди, залишаться без змін, тобто комбінація буде перетворена в комбінацію . Тоді сигнали з виходів елементів ВИКЛЮЧАЮЧЕ-АБО 14.1-14.k - 1 надходять на відповідні 1',2',…,і,…,(k - 1)-й входи регістра 15, на входи 1,…,j,…,(n - k + 1)-й якого надходить сигнал від 1,…,j,…,(n - k + 1)-х виходів суматора 7.1, після чого квазірівноважна комбінація з параметрами n та k - 1, що матиме наступний вид - у послідовному вигляді зчитується з виходу 16 регістра 15, який є виходом пристрою. Таким чином, лічильник 10 нулів та лічильник 11 кількості розрядів керують процесом перетворення комбінацій, що містяться на виходах суматора 7.1, у комбінації квазірівноважного коду за рахунок контролю кількості нулів в них і кількості розрядів r, (n - k + 1) ? r ? n, якщо лічильник 10 нулів підрахує (n - k + 1) нулів і кількість розрядів r підрахована лічильником 11 кількості розрядів буде належати проміжку (n - k + 1) ? r < n, то комбінація буде зазнавати відповідних змін в розрядах починаючи з (r + 1)-го, у випадку коли кількість розрядів r = n, комбінації біноміального коду будуть без змін заноситися до регістру 15 .

Наступний стан перетворювача кодів, коли на 1-му виході суматора 7.1 відповідно міститься одиничний сигнал, який проходить через елемент АБО 6.j - 1 на вхід елемента І 4.j. Оскільки з j-го виходу суматора 7.j та прямого виходу тригера 2.j надходять нульові сигнали на елемент АБО 1.j, тоді елемент І 5.j закритий нульовим сигналом, а елемент І 4.j відкритий одиничним сигналом з елемента НІ 3.j. Тому тактовий сигнал, що находить на вхідну шину 8, встановлює тригер 2.j в одиничний стан, відповідно на другому виході суматора 7.1 з'являється одиничний сигнал, і на другій групі виходів міститься комбінація 01..000, яка знову надходить на інформаційні входи перетворювача 9 паралельного коду в послідовний, після чого аналогічним чином комбінація 01..000 буде перетворена у комбінацію . Аналогічним чином будуть сформовані решта квазірівноважних комбінацій згідно з заданими параметрами n та k.

В табл.4.1 наведена відповідність рівномірних біноміальних кодових комбінацій з параметрами n = 5 та k = 4, що з'являються на другій групі виходів суматора 7.1 квазірівноважним комбінаціям з параметрами n_к = 5, k₁ = 4, k₂ = 3, що у послідовному вигляді з'являються на виході 16 пристрою.

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

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

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

,

де - кількість дозволених комбінацій; - загальна кількість комбінацій. Для КРК співвідношення приймає вигляд:

Графік представлено на рис. 4.2 показує, що найменша надлишковість у КРК для параметра . При відхиленні від даного значення, надлишковість коду збільшується.

Рисунок 4.2 - Надлишковість КРК кода

Доля помилок, що виявляються кодом знаходиться як . Для КРК співвідношення має вигляд:

З представленого співвідношення видно, що не існує такого коду, який би виявляв вісі можливі помилки, а лише тільки їх частину. На рис. 4.3 побудована залежність помилковиявляючої здатності КРК в залежності від параметра . Як видно з графіка найбільш потенційно можливу помилковиявляючу здатністю має код при значенні параметра та . Дана властивість також підтверджується тим, що при ціх значеннях КРК має максимальну надлишковість .

Рисунок 4.3 - Доля помилок, що виявляється

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

Проведений аналіз та побудовані залежності дають можливість більш ефективно підбирати параметри БСЧ для побудови перетворювачів кодів з використанням КРК, що мають задану помилковиявляючу здатність.

РОЗДІЛ 5...