Таблиця 3.1
Вихідні числові дані для розрахунку амплітудної спектральної характеристики сигналу
-
-
№ варіанту
|
, МГц
|
B, Вс
|
b,с
|
1.
|
10
|
15
|
2
|
2.
|
6
|
20
|
1,7
|
3.
|
5
|
10
|
1,5
|
4.
|
15
|
17
|
2,2
|
5.
|
17
|
23
|
2,5
|
6.
|
25
|
25
|
2,7
|
7.
|
13
|
17
|
3,0
|
8.
|
20
|
13
|
3,2
|
9.
|
8
|
27
|
3,5
|
10.
|
23
|
30
|
3,7
|
11.
|
9
|
32
|
4
|
12.
|
7
|
34
|
5
|
13.
|
11
|
40
|
4,3
|
14.
|
12
|
38
|
4,7
|
15
|
14
|
36
|
4,5
|
ПРАКТИЧНА РОБОТА №4
Тема роботи: ПОВІДОМЛЕННЯ В ЕЛЕКТРОННИХ СИСТЕМАХ
ТЕОРЕТИЧНІ ВІДОМОСТІ
4.1. Повідомлення та види їх представлення в електронних системах
Для передачі чи збереження інформації використовується певна мова. Вона характеризується своїми знаками і правилами їх використання. Поняття “знак” можна використовувати в широкому розумінні слова, як сукупність ознак, за якими розпізнається що-небудь. Ми ж будемо використовувати це поняття у вузькому розумінні: знак – це певний символ. Прикладами знаків у широкому розумінні слова є слова і фрази людської мови, числа, жести, малюнки, форма електричних коливань, математичні знаки. Сукупність знаків, яка містить у собі певну інформацію і призначена для передачі певному споживачу, називають повідомленням. Іншими словами, повідомлення – це інформація, представлена в певному вигляді з допомогою тієї чи іншої системи знаків. Всяке повідомлення має містити в собі сукупність відомостей про стан якоїсь системи. Повідомлення завжди передається людиною або пристроєм, які спостерігають цю систему, іншій людині чи пристрою, які не мають доступу до цієї системи.
В загальному випадку спосіб формального запису різних повідомлень називається представленням повідомлень. При цьому різні види і форми представлення повідомлень визначаються перш за все природою інформації, що передається, а також способом формування повідомлень.
У сучасних технічних електронних системах у ролі універсальних знаків алфавіту використовуються цифри, вектори і функції. Залежно від вигляду математичних знаків, які описують повідомлення, розрізняють цифрове (дискретно-квантоване), дискретне і аналогове представлення.
При цифровому представленні повідомлення описується упорядкованою сукупністю чисел зі скінченним, наперед вибраним числом розрядів. Якщо запис повідомлень здійснюється мовою, що має алфавіт зі скінченним числом символів, то будь-яке таке повідомлення може бути представлено в цифровій формі. Для цього достатньо всі символи алфавіту пронумерувати (тобто поставити у відповідність кожному символу число). В багатьох практично важливих випадках таку впорядковану сукупність чисел можна представити у вигляді функції дискретного аргументу.
У більш загальному випадку представити повідомлення в цифровій формі можна функціями кількох аргументів, які набувають ряду дискретних значень. Прикладом такого представлення є цифрова система телевізійного зображення, де кожна його точка представляється цифрою (інтенсивністю цієї точки) як функція двох координат екрану. Процес зведення такого представлення до представлення з допомогою функції одного аргументу в електронних системах називається розгорткою.
При дискретному представленні повідомлення описується впорядкованою сукупністю величин, кожна з яких може мати будь-яке значення в неперервному інтервалі, який називають діапазоном вимірювання.
У багатьох випадках повідомлення в дискретній формі формалізмом опису не відрізняється від цифрового представлення. Відмінність полягає лише в тому, що величини тепер можуть набувати нескінченної множини значень, у тому числі й значення, які задаються ірраціональними числами і не можуть бути записані числом із скінченним числом розрядів.
Допускаючи деяку похибку, можна провести округлення значень величин повідомлення в дискретній формі і тим самим перетворити його в цифрову форму. Такий перехід від неперервної шкали повідомлення до шкали фіксованих значень називають квантуванням.
При аналоговому представленні повідомлення описується функціями одного або кількох неперервних аргументів, наприклад, v = v(t). Найчастіше одним із аргументів є час t або його лінійне відображення, наприклад, віддаль по довжині магнітної стрічки до точки даного запису. Аналогічно задаються повідомлення і у випадку функцій багатьох аргументів.
Допускаючи деяку похибку представлення, аналогову форму повідомлення можна перетворити в дискретну. Таке перетворення повідомлення з аналогової форми в дискретну називають дискретизацією. У сучасних електронних системах цей процес поєднують із процесом квантування. Ці процеси здійснюють аналогово-цифрові перетворювачі, які є невід’ємною частиною більшості сучасних електронних систем.
Дискретизація та квантування повідомлень не зменшує їх об’єму, і, відповідно, не веде до мiнiмінізації інформаційного завантаження каналів зв'язку, запам'ятовуючих i реєструючих пристроїв. Це пояснюється тим, що для отримання малої похибки період опитування при дискретизації доводиться вибирати досить малим (навіть меншим, ніж інтервал за теоремою Котельникова). Але при дуже "густому" опитуванні між сусідніми дискретними значеннями величини залишаються достатньо сильні кореляційні зв'язки з коефiцiєнтом кореляції близько 0,85–0,95. Наявність же сильних кореляцій між елементами повідомлення завжди веде до невиправданого збільшення об’єму цього повідомлення. Тому для підвищення ефективності дискретного представлення кожне дискретне значення повинне формуватися не саме по собі, а в результаті аналізу всього неперервного повідомлення на деякому достатньо великому інтервалі часу, який називається інтервалом представлення. Такий спосіб представлення повідомлень називається узагальненою дискретизацією.
4.2. Основи кодування повідомлень
Як вказувалось у попередньому розділі, одним із найпоширеніших способів запису повідомлень є використання набору певних символів – знаків. Якщо ж при цьому необхідно передати чи зберігати велику кількість різних повідомлень, то набір цих знаків бажано впорядкувати в мову з ієрархічною структурою. Така структура мови дозволяє будувати конструкції різного рангу. Сукупність використовуваних знаків називають алфавітом мови. Зокрема, в писемній мові знаками є букви, розділові знаки, пробіли між словами. В усному мовленні знаками є окремі типові звуки, які називаються фонемами. Із комбінації деякого обмеженого числа знаків алфавіту мови будуються конструкції наступного (другого) рангу – слова. Із комбінації слів – фрази, далі вислови і т.д.
Побудова конструкцій з різним змістом і різних рангів із знаків алфавіту називається кодуванням або первинним кодуванням. Тобто кодування – це передання змісту інформації певними комбінаціями знаків даного алфавіту, що проводиться за визначеними правилами. Обернена операція вилучення змісту інформації з сукупності переданих чи зареєстрованих знаків називається декодуванням. При цьому ми завжди отримуємо дискретні представлення повідомлень. Перетворення дискретного повідомлення в сигнал вимагає проведення двох операцій: кодування та модуляції. Кодування визначає закон побудови сигналу, а модуляція – правила перенесення повідомлення на несучу і вид сигналу.
Найпростішим і найпоширенішим прикладом дискретного повідомлення є текст, який складається із скінченного числа знаків (букв, цифр, розділових знаків). В європейських мовах такий алфавіт міститиме 80–90 елементів. Тому для передачі повідомлень можна кожному знаку співставити свій сигнал. Але електронні системи, побудовані на такому принципі, повинні будуть вміти розпізнавати всі 80 чи 90 сигналів, а, отже, будуть дуже складними. Тому в текстових повідомленнях для електронних систем знаки заміняють числами, які задають їх порядковий номер в алфавіті. Тим самим завдання передачі тексту зводиться до передачі чисел.
Числа можна записувати в різних системах числення. Загальний вигляд запису числа N в системі числення з основою q такий: N = anqn-1 + an-1qn-2 + …. + a2q1 + a1q0. Сукупність цифр anan-1…a2a1, які є коефіцієнтами розрядів нашого числа і є кодовим словом якогось символу, позначеного числом N. Для обробки таких кодових слів в електронних системах кожному можливому коефіцієнту розрядів слід поставити у відповідність свій особливий сигнал, який називають одиничним або елементарним. Якщо використовувати для передачі повідомлень звичну нам десяткову систему числення, то нам буде необхідно обробляти десять різних сигналів, що все ще досить багато. Тому для передачі дискретних повідомлень переважно використовують “низькорозмірні” системи числення, основною з яких є двійкова система. І для передачі будь-якого повідомлення в цьому випадку достатньо всього два різних сигнали: один із них відповідає нулю, а другий – одиниці.
Наочно ефективність використання різних систем числення для кодування повідомлень ілюструє рис.4.1, на якому наведено залежність кількості розрядів, необхідних для задання числа 65556 у цих системах, від їх основи q. Як видно, оптимальними були б системи числення із q 3, в яких найкраще узгоджуються число розрядів для запису чисел і основа коду q. Детальний теоретичний аналіз вказує, що найоптимальнішими дійсно є системи числення із q = е = 2,7. Але з точки зору технічної реалізації різних систем кодування простішими є системи із q = 2. Тому саме двійкова система числення лежить в основі побудови сучасних електронних інформаційних систем. Це обумовлено простотою апаратної побудови електронних систем розпізнавання одного з двох сигналів; зменшенням часу передачі повідомлень та їх об’єму; простотою виконання арифметичних та логічних дій над інформацією, що міститься в таких повідомленнях. Відповідно кодування – це процес перетворення елементів дискретного повідомлення у відповідні їм числа, які записуються кодовими символами.
Надалі під кодовим алфавітом мови певної електронної системи ми будемо розуміти сукупність усіх знаків алфавіту і правил побудови з них конструкцій різних рангів. Знаки алфавіту називають кодовими символами. Зокрема, для двійкової системи числення кодовими символами є 0 і 1. Кількість знаків у алфавіті мови називають основою коду. Оскільки в електронних системах використовують двійковий код, то основа такого коду рівна 2.
|
Рис.4.1. Залежність числа розрядів для задання числа 65553 від основи системи числення q
|
Конструкції другого рангу в ЕС називають кодовими словами або кодовими комбінаціями. З їх допомогою кожному елементу повідомлення присвоюється своя послідовність кодових символів, яка називається кодовою комбінацією. Тобто, кодова комбінація – це число, яке позначає певний знак повідомлення і яке записане в тій чи іншій системі числення з допомогою символів даного коду. Наприклад, букву А тексту повідомлення в процесі кодування можна замінити кодовою комбінацією 10000. Сукупність кодових комбінацій, які позначають усе задане повідомлення, називають кодом. Якщо всі кодові комбінації мають однакове число символів, то код називають рівномірним кодом. У протилежному випадку код буде нерівномірний.
Число символів, які містяться в певній кодовій комбінації, називають її довжиною. Для рівномірних кодів довжину кодових комбінацій ще називають значністю коду.
Перевагою рівномірних кодів є спрощення знакодрукуючих пристроїв та прискорення передачі повідомлень, оскільки зникає необхідність посилання по каналу зв’язку розділюючих символів між двома послідовними кодовими комбінаціями.
Нерівномірні коди характерні тим, що у них кодові комбінації різних символів мають різну довжину, і, відповідно, різну тривалість передачі. Прикладом нерівномірного кодування є наша мова, оскільки в ній довжина різних слів різна. Прикладом нерівномірного коду в електронних системах є код (азбука) Морзе. В коді Морзе крапці відповідає елементарний сигнал однієї логічної “1”; тире відповідає сигнал із трьох логічних “1”; елементарний сигнал із одного логічного “0” відповідає знаку розділення між сусідніми крапками чи тире в кодовій комбінації; сигнал із трьох логічних “0” відповідає розділювачу між двома сусідніми кодовими комбінаціями. В результаті для передачі “найкоротшого” символу – букви “Е”, – потрібна тривалість передачі рівна 40 (10 на передачу крапки, яка є кодом букви “Е” і 30 для передачі розділювача між кодовою комбінацією букви “Е” і кодовою комбінацією послідуючої букви). Тут 0 – тривалість елементарного сигналу. Передачі ж “найдовшого” символу азбуки Морзе – нуля, – відповідає тривалість сигналу в 220. Середня ж тривалість сигналу однієї кодової комбінації коду Морзе складає (9 – 10)0.
Надалі певну кодову комбінацію коду будемо позначати через Аі, де і = 1, 2, … М, а М – загальне число всіх кодових комбінацій, які потрібні для запису повідомлення.
В електронних системах при можливості стараються використовувати рівномірні коди. В загальному випадку рівномірний код з основою q при числі символів у кожному кодовому слові n дає можливість побудови максимального числа N = qn різних кодових комбінацій. Якщо ж нам потрібно закодувати фіксоване число М різних знаків, то при рівномірному кодуванні необхідна мінімальна довжина кодової комбінації k визначається умовою q(k-1) < M qk. Рівномірні коди, в яких M = N = qk, називаються простими або звичайними кодами.
Правила кодування текстових повідомлень задаються кодовими таблицями (таблиця 4.1). У цій таблиці кожному знаку текстового повідомлення ставлять у відповідність свою кодову комбінацію.
Таблиця 4.1
Кодова таблиця коду Боде
Знак повідомлення
|
Кодова комбінація
|
Позначення кодової комбінації
|
А
Б
В
…
|
00001
00010
00011
…
|
А1
А2
А3
…
|
4.3. Параметри та характеристики повідомлень і інформаційних систем
Розглянемо основні параметри повідомлень і інформаційних систем.
Об'єм повідомлення – це число типових символів, які містяться в ньому. У сучасній математичній теорії повідомлень в ролі типового представлення вибрано цифрове представлення у вигляді двійкового коду. Тому об'єм повідомлення – це кількість двійкових символів, яка міститься в даному повідомленні. При цьому враховуються як символи, що безпосередньо несуть інформацію, так і допоміжні службові символи, наприклад, символи кінця рядка, кінця абзацу і т.д.
Якщо ми маємо цифрове представлення не в двійковому коді або аналогове чи дискретно-аналогове представлення, то для визначення об'єму такого повідомлення його слід перетворити в типову форму, тобто в двійковий код. При цьому об’єм повідомлення буде залежати від способу його дискретизації та кодування. Тому для порівняння об’ємів різних повідомлень встановлюють типові способи дискретизації, квантування та кодування.
Пропускна здатність системи – це максимальний потік первинних повідомлень, які дана система може сформувати (прийняти), провести з ними необхідні перетворення i подати на вихід, забезпечуючи задану правильність оцінок повідомлень, що видаються нею.
Інформаційна ємність систем збереження повідомлень рівна максимальному об’єму повідомлень, які можна запам'ятати i зберігати в цій системі протягом потрібного часу з необхідною правильністю їх оцінок при зчитуванні.
Операційна продуктивність системи характеризується максимальним числом елементарних операцiй, які виконуються системою за одиницю часу при всіх можливих перетвореннях повідомлень. Вибір елементарних операцій при визначенні операційної продуктивності визначається видом здійснюваних системою перетворень. Наприклад, у випадку процесорів такою операцією є додавання двох двійкових чисел.
Інформаційне навантаження системи – це реальні значення її пропускної здатності, iнформацiйнoї ємнoсті i oперацiйнoї продуктивності в процесi роботи.
4.4. Типові перетворення повідомлень
В інформаційних системах виконуються, як правило, чотири основні типи перетворень повідомлень: перетворення форми представлення повідомлення; стиснення об’єму повідомлення; підвищення завадостійкості повідомлення; підвищення правильності оцінок повідомлення.
Перетворення форми представлення повідомлень. Таке перетворення необхідне тому, що в різних інформаційних підсистемах, а часто і в різних пристроях однієї підсистеми, використовуються різні види представлень: дискретне, цифрове й аналогове. Це пов’язано з технічною реалізацією тих чи інших пристроїв, оптимізацією їх характеристик або оптимізацією показників інформаційної системи в цілому.
Суттєвими перетвореннями при цьому є згадувані вище дискретизація, квантування, інтерполяційна обробка, і розгортка. При перетворенні повідомлення з цифрової форми в дискретну і аналогову вносяться лише апаратні похибки. При всіх інших перетвореннях вносяться додатково похибки, пов’язані з самою процедурою перетворення.
Стиснення об’єму повідомлень дозволяє зменшити вимоги до пропускної здатності інформаційної системи і ємності запам’ятовуючих пристроїв. Слід, однак, пам’ятати, що стиснення об’єму повідомлень завжди веде до збільшення операційного навантаження пристроїв формування та обробки таких повідомлень.
Підвищення завадостійкості повідомлень використовується для покращення правильності передачі повідомлень при даному характері спотворень. Як правило, це досягається внесенням у повідомлення деякої надлишковості, погодженої із статистикою спотворень повідомлень. Звичайно, що такий процес веде до збільшення об’єму повідомлень, а сам він називається завадостійким (надлишковим) кодуванням. Детальніше ці питання буде розглянуто нами нижче.
Підвищення правильності оцінок повідомлень, що надаються споживачу, досягається вибором способів обробки цих повідомлень перед їх видачею. Найчастіше з цією метою використовують різні методи фільтрації або цільову обробку повідомлень. Детальніше з деякими таким методами перетворення повідомлень ми познайомимося також трохи нижче.
Під правильністю оцінок повідомлень розуміють ступінь відхилення отриманого споживачем повідомлення від реального. Від правильності оцінки отриманого споживачем повідомлення буде залежати значною мірою те, чи буде цим споживачем отримано необхідну інформацію.
Вибір виду показників правильності залежить від завдань інформаційної системи і, в першу чергу, від властивостей самого споживача повідомлень. Наприклад, слух людини добре відчуває зміни спектрального складу звукових сигналів, але зовсім не чутливий до фазових спотворень у таких сигналах. Також багато систем управління чутливі лише до середнього значення сигналів управління, а не до їх форми. Тому вибір показників правильності повідомлень має тісно узгоджуватися з властивостями споживача повідомлень.
4.5. Методи стиснення об'єму повідомлень та критерії оцінки їх ефективності
Стиснення об'єму повідомлень є важливою операцією, яка дозволяє розгрузити канали зв'язку, запам'ятовуючі і реєструючі пристрої, прискорити процес вибірки і огляду необхідної інформації, зменшити час, необхідний для обробки, підвищити достовірність передачі інформації по каналах з фіксованою пропускною здатністю.
Зараз використовують такі основні методи стиснення об’єму повідомлень.
Цільова обробка повідомлень. При цьому використовується деяке незворотне перетворення, що дозволяє отримати споживачеві узагальнені відомості про основний зміст повідомлення (наприклад, про мінімальне і максимальне значення величин процесу, їх кореляційну характеристику), а не все повідомлення в цілому. Таке перетворення є незворотним у тому розумінні, що при отриманні узагальнених параметрів вхідне повідомлення змінюється настільки, що відновити його початковий зміст стає неможливо.
Цільова обробка є зараз найбільш поширеним методом стиснення об'єму повідомлень. Для реалізації цього методу можна сконструювати необмежену кількість пристроїв. Найбільш типовими з них є порівняльні пристрої, аналізатори енергетичного спектру, корелятори тощо. Як правило, такі пристрої розробляються окремо для кожного джерела повідомлень.
Метод зміни частоти опитування. Суть методу полягає в тому, що в процесі дискретизації на ділянках швидкої зміни повідомлення частота опитування автоматично встановлюється високою, а на ділянках повільної зміни – низькою. Для реалізації такого адаптивного опитування використовуються достатньо складні пристрої у вигляді аналізаторів активності джерел повідомлень. Такі пристрої повинні бути малоінерційними і обов’язково включати в свій склад системи підказки, які дають змогу змінити частоту опитування з врахуванням очікуваного характеру зміни повідомлень.
Метод виключення несуттєвих вибірок. У цьому методі з дискретного повідомлення викидаються ті вибірки, які можна відновити шляхом аналізу попередніх чи послідуючих вибірок. При цьому все повідомлення проходить регулярну дискретизацію з постійною частотою опитування, а потім усі несуттєві вибірки виключаються з нього.
Метод статистичного кодування. У попередніх методах використовується мінімізація числа координат дискретного повідомлення. При статистичному кодуванні стиснення об'єму повідомлення проходить за рахунок зменшення об'єму інформації по кожній координаті повідомлення. При статистичному кодуванні малоймовірні координати кодуються більшим числом символів у порівнянні з координатами, які формуються більш часто. Але на практиці таке кодування дуже незручне і в багатьох випадках малоефективне, тому воно використовується відносно рідко.
Ефективність методів стиснення об'ємів повідомлень характеризують такими параметрами.
Коефіцієнт стиснення повідомлення – це відношення об'єму вхідного повідомлення до об'єму повідомлення, одержаного після стиснення, при збереженні допустимих значень показників правильності. Тобто коефіцієнт стиснення – це число, яке показує, у скільки разів зменшиться число відліків повідомлення на виході пристрою стиснення в порівнянні з його входом.
Коефіцієнт ефективності – це відношення теоретично досяжної нижньої межі об'єму повідомлень до об'єму повідомлень після практичного стиснення. З допомогою цього критерію можна оцінювати ефективність різних методів стиснення.
Показник операційного навантаження. Коефіцієнт стиснення залежить від складності використовуваного алгоритму. Чим вищий необхідний коефіцієнт стиснення, тим складніший буває алгоритм обробки, а складність алгоритму прямо впливає на складність його апаратної реалізації. Показник операційного навантаження і характеризує складність алгоритму – це середнє число базових обчислювальних операцій, необхідних для проведення стиснення однієї координати повідомлення.
ЗАВДАННЯ РОБОТИ
Завдання 1. Розрахувати об’єм повідомлення про дане завдання роботи, використовуючи типову кодову таблицю клавіатури сучасних комп’ютерів.
Завдання 2. Визначити основні параметри при перетворенні різних форм повідомлень для наданих керівником роботи АЦП та ЦАП.
Завдання 3. Вивчити блочну структуру та принципи роботи аналізатора енергетичного спектру при цільовій обробці повідомлень.
Завдання 4. Ознайомитися з основними принципами роботи аналізаторів активності джерел повідомлень при зміні частоти опитування на базі сучасних мікроконтролерів та мікропроцесорів.
ПРАКТИЧНА РОБОТА №5
Тема роботи: ВИВЧЕННЯ ПРИНЦИПІВ ЗАВАДОСТІЙКОГО КОДУВАННЯ НА ОСНОВІ СИСТЕМАТИЧНИХ БЛОЧНИХ ВИЯВЛЯЮЧИХ КОДІВ З ПОСТІЙНОЮ ВАГОЮ
ТЕОРЕТИЧНІ ВІДОМОСТІ
5.1. Принципи завадостійкого кодування
У загальному випадку повідомлення в електронній системі являє собою ряд кодових комбінацій або кодових слів. Внаслідок дії завад і недосконалості апаратури деякі символи в окремих кодових комбінаціях прийнятого повідомлення можуть бути впізнані неправильно, а деякі символи можуть бути не впізнані взагалі. У випадку передачі тексту це приведе до зміни або зникнення певних його букв. Перший випадок називають трансформацією символів, а другий випадок – стиранням символів. Відповідно розрізняють канали або пристрої із здатністю до трансформації чи стирання символів.
Найбільш неприємними в інформаційних системах є помилки типу трансформації символу. Це обумовлено тим, що стирання символу вже саме по собі виявляє помилку. І лишається лише знайти методи виправлення таких помилок. Помилки ж з трансформацією символів виявляються значно важче, і саме такі помилки ми будемо в основному розглядати надалі.
Для прикладу, при використанні нашої звичайної мови внесені завадами помилки легко виявити та виправити. Наприклад, по телеграфу ми отримали наступне слово: томке. Ми зразу бачимо в цьому слові наявність помилки, оскільки в українській мові такого слова немає. Аналіз слів, які стоять до або після цього слова, дозволяє виправити таку помилку. Зокрема, якщо за помилковим словом ми отримуємо наступне слово скло, то перед ним було передано слово ломке, а якщо – болото, то – топке. Але якби така ситуація сталася при передачі тексту такою мовою, в якій будь-яка комбінація букв відповідає новому осмисленому слову, то виявити помилку було б дуже складно.
Таким чином, у багатьох випадках у повідомленнях спеціально потрібно використовувати не всі кодові слова, а лише їх частину. В такому випадку говорять, що в мову введено певну надлишковість. І саме введення такої надлишковості підвищує її стійкість до дії завад та шуму. Кількість інформації в повідомленні від цього не зміниться, але суттєво може збільшитись об’єм сигналу, необхідний для передачі таких повідомлень.
У звичайних кодах всі можливі кодові комбінації використовуються для передачі інформації. У таких кодах зміна хоча б одного двійкового кодового символу на протилежний веде до появи іншої кодової комбінації, а відповідно – і до неправильного розпізнавання всього кодового слова. Тому таку ситуацію надалі ми будемо називати помилкою. Кількість трансформованих і стертих символів у прийнятому повідомленні задає число помилок в ньому.
Звичайний код не дозволяє електронній системі самій знаходити (виявляти) і тим більше виправляти помилки. Але існують способи кодування, які дають можливість виявити помилки в отриманих повідомленнях і виправити їх. Така можливість пояснюється теоремою Шенона, доведеною на початку минулого століття. Згідно з нею, при будь-якій швидкості передачі двійкових символів, меншій, ніж пропускна здатність каналу зв’язку, можна розробити такий код, при якому імовірність неправильного декодування помилкового символу буде зведено до як завгодно малої величини. Ефективним засобом підвищення достовірності передачі повідомлень через канали з завадами є завадостійке кодування з допомогою спеціальних кодів. Такі коди дістали назву коректуючих або завадостійких. Тобто коди, які можуть виявляти чи виправляти помилки, називають завадостійкими або коректуючими.
Відповідно розрізняють коди з виявленням і виправленням помилок. Код з виявленням помилок зменшує число неправильно розпізнаних символів, стирає або відзначає повідомлення з помилками, вживає заходів до повторної передачі невпізнаних символів чи повідомлень з помилками. При використанні виявляючих кодів для виправлення помилок у систему вводять канал зворотного зв’язку. Приймач, виявивши помилку в отриманому повідомленні, посилає по каналу зворотного зв’язку запит на повторення повідомлення, отриманого з помилкою. Виправляючий код дозволяє приймачу не лише виявити помилку, а й визначити, які кодові символи є помилковими, а також виправити їх без повторної передачі спотвореного повідомлення. Код з виправленням помилок дозволяє отримати правильне повідомлення, незважаючи на наявність деякого числа помилок при розпізнанні символів. Звичайно, що не існує кодів, які дозволяли б виявити і тим більше виправити всі можливі помилки. Можна розробити лише коди, які виявляють чи виправляють тільки деяке число помилок певного виду. При цьому основну увагу приділяють виявленню і виправленню особливо небезпечних помилок.
Для конкретності розглянемо двійкові рівномірні коректуючі коди. Оскільки для них основа коду q = 2, то загальна кількість кодових комбінацій довжиною n, які можна скласти в даному коді N = qn = 2n. Використовуються всі, крім нульової, тобто N – 1 = 2n – 1 кодових комбінацій. Коректуючі коди будуються таким чином, щоб загальне число їх кодових комбінацій N перевищувало число комбінацій М, які необхідні для передачі повідомлення. Тоді ті М комбінацій, які використовуються для передачі символів повідомлення називаються дозволеними, а інші N – М – 1 комбінацій, які не використовуються передавачем повідомлень, називають забороненими. В таблиці 5.1 дано приклад ряду дозволених і заборонених комбінацій певного коду.
Таблиця 5.1
Приклад побудови ряду дозволених і заборонених кодових комбінацій
Позначення кодової комбінації
|
Запис кодової комбінації
|
Вид кодової комбінації
|
А1
|
000100
|
дозволена
|
А2
|
000101
|
заборонена
|
А3
|
000110
|
заборонена
|
А4
|
000011
|
заборонена
|
А5
|
001001
|
дозволена
|
А6
|
001000
|
заборонена
|
А7
|
001010
|
заборонена
|
А8
|
001011
|
заборонена
|
А9
|
011110
|
дозволена
|
А10
|
001101
|
заборонена
|
А11
|
001111
|
заборонена
|
А12
|
001100
|
заборонена
|
Звичайно, і передавач, і приймач мають містити інформацію про те, які з кодових комбінацій коректуючого коду дозволені, а які заборонені. Тоді, якщо в процесі передачі від передавача до приймача в повідомлення вкралася помилка, то вона призводить до перетворення дозволеної комбінації в заборонену. Тому приймачем таку помилку буде виявлено, а іноді й виправлено. Звичайно, якщо помилка призвела до перетворення однієї дозволеної кодової комбінації в іншу дозволену кодову комбінацію, то її виявлено не буде.
Для оцінки завадостійкості коду та для полегшення відбору множини дозволених кодових комбінацій, які забезпечують необхідну коректуючу здатність, на множині всіх кодових комбінацій вводять певну метрику. Ми будемо використовувати найбільш просту і широко вживану метрику Хеммінга. Ця метрика кількісно задає відмінність між двома двійковими кодовими комбінаціями і називається віддаллю між цими двома кодовими комбінаціями. Математично така метрика визначається як кількість одиниць у сумі по модулю два цих комбінацій. Наприклад, для наведених у таблиці кодових комбінацій А1(000100) і А5(001001) сума по модулю два рівна А1 А5 = 000100 001001 = 001101 і відповідно кодова відстань між ними di,j = d1,5 = 3. Значком тут і надалі позначатимемо операцію додавання по модулю два двійкових чисел. Звичайно, що в будь-якому коді di,j n. Мінімальна віддаль, яка може бути між двома будь-якими дозволеними кодовими комбінаціями даного коду, називається кодовою віддаллю коду d. Для коду, наведеного в таблиці, кодова віддаль d = 3.
При завадостійкому кодуванні на вхід кодера подають кодові комбінації простого коду, кожна з яких містить по k інформаційних символів. На виході такого кодера вже отримують завадостійкий код, кожна кодова комбінація якого містить по n символів (n > k).
У результаті на виході кодера отримуємо 2k різних кодових комбінацій. При передачі їх по каналу зв’язку за рахунок спотворень і шумів до приймача може прийти будь-яка з можливих 2n комбінацій. Серед них лише 2k комбінацій відповідають вхідному повідомленню і є дозволеними. Всі інші 2n – 2k кодових комбінацій передавачем не передавалися і є забороненими. Це обумовлено зміною правильних символів деяких із 2k дозволених комбінацій на неправильні і переходом таких кодових комбінацій у групу заборонених.
Ситуація ускладнюється тим, що деякі дозволені кодові комбінації можуть перейти в такі ж дозволені, але помилкові кодові комбінації. І в загальному випадку будь-яка з дозволених 2k комбінацій може перейти в будь-яку із можливих 2n комбінацій. Тобто, через зашумлений канал зв’язку можлива реалізація такої множини подій по передачі певного повідомлення:
2k – число можливих подій безпомилкових передач.
2k(2k – 1) – число можливих подій передач з переходом від однієї дозволеної кодової комбінації до іншої дозволеної комбінації. Такі переходи відповідають невиправним помилкам.
2k(2n – 2k) – число можливих подій передач з переходом від дозволеної кодової комбінації до забороненої. Такі переходи відповідають помилкам, які можна виявити і виправити.
В цілому загальне число можливих передач становить 2k2n. З цього загального числа можна виявити лише (1 – 2k/2n)100 % помилок.
Для підвищення коректуючої здатності коду необхідно збільшувати d. Таке збільшення можливе лише за рахунок збільшення числа заборонених кодових комбінацій 2n – 2k, де k – довжина кодових комбінацій простого некоректуючого коду. Тобто, отримання коректуючого коду вимагає введення в кожну кодову комбінацію простого коду додаткових n – k надлишкових символів.
Нехай  і  – деяка пара дозволених кодових комбінацій, розділена кодовою віддаллю d (таблиця 5.1). Між цими дозволеними кодовими комбінаціями існують заборонені кодові комбінації. Як видно, для перетворення однієї дозволеної кодової комбінації в другу дозволену комбінацію необхідна зміна d (в нашому випадку d = 3) кодових символів. Якщо ж спотворено меншу кількість кодових символів, то комбінація просто перейде в одну із заборонених і буде виявлена. Звідси слідує правило: помилку завжди буде виявлено, якщо число спотворених символів кодової комбінації g d – 1. Величину g називають кратністю помилки. Якщо g > d, то деякі помилки теж можна виявити, але не всі. При g = d помилку виявити не можна. Зокрема, мінімальна кодова віддаль, при якій виявляються будь-які одиночні помилки, тобто при помилковій зміні одного символу кодової комбінації, рівна 2.
При правильному комплектуванні областей кожного дозволеного кодового символу коректуючий код дозволяє провести такі дії.
Виявити g помилок, якщо d = 2g.
Виправити t помилок, якщо d = 2t + 1.
Виправити t помилок і виявити g помилок, якщо d = t + g + 1.
Нехай передано правильну дозволену кодову комбінацію довжиною n, а приймач отримав заборонену комбінацією із кратністю помилок g. Позначимо через Р0 імовірність спотворення одного символу в процесі передачі повідомлення по каналу зв’язку. Тоді ймовірність правильного прийому певного одного символу буде рівна 1 – Р0, а ймовірність прийому (n – g) правильних символів буде рівна (1 – Р0)n – g. Аналогічно ймовірність прийому g спотворених символів буде рівна Р0g. В результаті загальна ймовірність отримання кодової комбінації довжиною n із g помилковими символами буде рівна Рg = Р0g(1 – Р0)n – g. Як правило, Р0<<1 і тоді, Рg різко зменшується з ростом g.
При виведенні формули ймовірності появи в кодовій комбінації помилки кратності g ми не враховували, що ці g помилкових символів можуть по-різному розташовуватися в n можливих позиціях кодової комбінації. При врахуванні ж цього факту треба отриману раніше ймовірність помножити на число різних комбінацій g елементів в n позиціях  . Тоді  .
Розглянемо конкретний випадок, коли n = 5 і Р0 = 0,2. Тоді залежність загальної ймовірності появи помилок Рg буде мати вигляд, показаний на рис.5.1. З рисунка слідує, що значення Рg монотонно зменшується з ростом g. В результаті на практиці буває достатньо знайти і виправити лише одно- та двократні помилки.
Виправлення виявлених помилок ведуть за наступним правилом: якщо отримано заборонену комбінацію, то вважається прийнятою найближча до неї дозволена кодова комбінація. Наприклад, відповідно до таблиці 5.1 отримано було комбінацію А2, але приймач декодує її як кодову комбінацію А1. Таке правило забезпечує виправлення максимального числа помилок. З цього правила також слідує, що його використання дозволяє виправити всі помилки кратності  . Тобто, мінімальне значення d, при якому можна не лише виявити, а і виправити однократну помилку, рівне 3.
|
Рис.5.1. Залежність імовірності появи в кодовій комбінації помилки від її кратності g
|
Таким чином, відновлення помилкових символів являє собою складніше завдання в порівнянні з завданням лише виявлення помилок. Практична реалізація електронних систем, які виправляють помилки, пов’язана з суттєвим ускладненням кодерів і декодерів. Тому виправляючі коди використовують у більшості випадків для коректування помилок лише малої кратності (одно- та двократних).
Якщо код коректує всі помилки з кратністю не більшою g, тоді повна ймовірність коректування помилки в кодовій комбінації  .
Для нашого конкретного випадку, розглянутого раніше, Ркор 0,55, тобто біля 55% помилок буде повністю виправлено. Ймовірність правильного прийому кодової комбінації становитиме  або 33%. Імовірність же нескоректованих помилок у кодових комбінаціях буде рівна  . Для нашого випадку Pn 1 - 0,33 - 0,55 0,12 або 12%.
Найпростішим для теоретичного використання способом декодування є спосіб, описаний вище у вигляді правила виявлення помилок. Однак при його практичній реалізації вимагається використання складних електронних пристроїв, які в змозі запам’ятати всі N = 2n кодових комбінацій і розділити їх на дозволені і заборонені. Тому на практиці використовують коди, які виявляють помилки іншими, простішими в реалізації способами. Нижче ми розглянемо найбільш вживані з таких кодів.
Для підвищення коректуючої здатності коду необхідно збільшувати d. Таке збільшення можливе лише за рахунок збільшення числа заборонених кодових комбінацій  де k – довжина кодових комбінацій звичайного коректуючого коду. Таким чином, коректуючі коди мають використовувати для передачі дискретних елементів повідомлення не всі з можливих кодових комбінацій даного коду. Для отримання коректуючого коду з простого коду в кожну кодову комбінацію вводять надлишкові кодові символи. При цьому справедливе загальне правило: чим більше надлишкових символів введено в кожну кодову комбінацію, тим вища коректуюча здатність коду. Таким чином, корекція помилок можлива лише при використанні в кодовому слові числа символів n > k, де k визначається з наведеної вище формули для М, тобто внесенням в код надлишку по числу символів. У результаті ще однією важливою характеристикою є надлишковість коду  = (n – k)/n. Використовуючи наведені вище співвідношення, для надлишковості отримаємо  . Очевидно, що швидкість передачі коду буде визначатися співвідношенням k/n. Слід зазначити, що при фіксованій довжині кодових комбінацій n підвищення коректуючої здатності пов'язане зі збільшенням надлишковості і зменшенням швидкості передачі коду, що рівноцінно зменшенню потоку повідомлень, які передаються. Коди, в яких необхідна коректуюча здатність досягається при мінімальній надлишковості, називаються оптимальними.
Величини Pn, і n є основними характеристиками будь-якого коректуючого коду. Вони визначають, якою мірою даний код завадостійкий при передачі по каналах зв’язку і якою ціною ця завадостійкість досягається. І загальне завдання у створенні кодів полягає в досягненні якнайменших значень Pn і , а також у спрощенні електронних схем кодуючих і декодуючих пристроїв.
Використання коректуючого коду залежить від наступних факторів: виду каналу зв’язку або пристрою запам’ятовування повідомлень, наявності резерву по пропускній здатності каналів і ємності ЗП, статичних характеристик помилок при розпізнаванні символів, вимог до достовірності та допустимих затримок у передачі повідомлень. При виборі коректуючих кодів потрібно ще враховувати і те, що вони ефективні для боротьби з пакетами завад, завмиранням сигналу, деякими видами завад, при флуктуючих шумах чи при слабкому сигналі.
</1>
|