Цифрові методи передавання неперервних повідомлень ( частина 5 ). Конспект лекцій з Основи збору, передавання та обробки інформації. Робота № 501003

Перехід до торгівельного партнера Binance

Цифрові методи передавання неперервних повідомлень ( частина 5 )

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Інститут комп’ютерних технологій, автоматики та метрології

Факультет:

Не вказано

Кафедра:

Захист інформації

Інформація про роботу

Рік:

2011

Тип роботи:

Конспект лекцій

Предмет:

Основи збору, передавання та обробки інформації

Завантажити

Частина тексту файла (без зображень, графіків і формул):

Національний університет «Львівська політехніка» Інститут комп’ютерних технологій, автоматики та метрології Кафедра «Захист інформації» ОСНОВИ ЗБОРУ, ПЕРЕДАВАННЯ ТА ОБРОБКИ ІНФОРМАЦІЇ Конспект лекцій Тема 5: Цифрові методи передавання неперервних повідомлень. Особливості побудови та переваги цифрових СПІ над аналоговими. Імпульсно-кодова модуляція (ІКМ). Методи підвищення завадостійкості ІКМ. Компандування сигналу. Основні методи аналого-цифрового та цифро-аналогового перетворення. Дельта-модуляція (ДМ). Порівняння ІКМ і ДМ. Адаптивна ДМ та комбінована дельта кодово-імпульсна модуляція. Методи компресії текстової, мовної та відеоінформації; стискання даних. ЗМІСТ 5.1. 5.2. 5.3. 5.К. Питання до самоконтролю. 5.Л. Література. Львів – 2007 5. Цифрові методи передавання неперервних повідомлень Для передавання неперевних повідомлень можна використовувати дискретний канал. Для цього неперервне повідомлння перетворюють у дискретний (цифровий) сигнал, тобто у послідовність сигналів, що містять суттєву частину інформації (визначається епсилон-ентропією). Типовими прикладами цифрових систем передавання неперервних повідомлень є системи з ІКМ та ДМ. Основні операції перетворення: дискретизаія і квантування. Отриману послідовність квантованих відліків кодують і передають по дискретному каналу. На приймальній стороні після декодування відновлюють (з деякою точністю) неперервне повідомлення. Основна технічна перевага цифрових СПІ перед системами неперервного типу - висока завадостійкість, яка найбільше проявляється у СПІ з багатократною ретрансляцією (переприйманням) сигналів (кабельні та радіорелейні лінії з великою протяжністю). У таких системах завади і спотворення можуть накопичуватись. Якщо на кожному ретрансляторі сигнал лише підсилювати, то адитивні завади у кожній ланці статистично незалежні і їх потужність на виході рівна сумі потужностей завад усіх ланок. З метою послаблення ефекту накопичення завад при передаванні з ретрасляціями поряд з підсиленням проводять регенерацію імпульсів, тобто демодуляцію з відновленням переданих кодових символів і повторну модуляцію на переприймальному пункті. Адитивна завада з входу ретраслятора не поступає на його вихід. При ЦСП застосовують завадостійке кодування для підвищення вірності. Висока завадостійкість дозоляє здійснювати дальній зв'язок по каналах невисокої якості. Можливість застосування цифрової обчислювальної технчки і мікроелектроніки. Поєднанння в одній системі сигналів передачі даних, мови, ТБ для інтеграції систем передавання і систем комунікації. Простота зєднання цифрового каналу з ЕОМ, апаратурою зв'язку та автоматики і управління. Структурна схема систем цифрового передавання неперервних повідомлень рис.71 ФЦП, ЦАП: основні методи перетворення. 5.5. Стискання даних 5..1. Призначення і основні способи стискання. Стисканням даних називають перетворення даних у компактну форму без втрати інформації, що міститься в них. Стискання (компресія, архівація) це своєрідне кодування з вилученням надлишкових даних для зменшення об’єму пам’яті, потрібної при зберіганні чи передаванні інформації. Стискання скорочує обсяг простору, необхідного для зберігання файлів в ЕОМ, і кількість часу, необхідного для передачі інформації через канал встановленої ширини пропускання. Це є форма кодування. Іншими цілями кодування є пошук і виправлення помилок, а також шифрування. Процес пошуку й виправлення помилок протилежний стисненню - він збільшує надмірність даних, коли їх не потрібно представляти в зручній для сприйняття людиною формі. Видаляючи з тексту надмірність, стискання сприяє шифруванню, що ускладнює пошук шифpу доступним для зломщика статистичним методом. Потреба архівації визначається особливостями масиву даних. Так ілюстрація у книзі розміром 500х800 точок займає 1,2 Мб – стільки ж як книга з 400 сторінок (42 рядки по 60 знаків у стрічці). Не важко оцінити скільки тисяч сторінок тексту можна вмістити на диску пам’яті і як мало там вміститься якісних нетиснутих фотографій. Існують два основних способи стискання: статистичний і словниковий. Кращі статистичні методи застосовують арифметичне кодування, кращі словникові - метод Зіва-Лемпела. У статистичному стисненні кожному символу привласнюється код, заснований на ймовірності його появи в тексті. Високоможливі символи одержують короткі коди, і навпаки. У словниковому методі групи послідовних символів або "фраз" замінюються кодом. Замінена фpаза може бути знайдена у певному "словнику". Показано, що будь-яка практична схема словникового стиснення може бути зведена до відповідної статистичної схеми стиснення, і знайдено загальний алгоритм перетворення словникового методу в статистичний. Тому пpи пошуку кращого стиснення статистичне кодування обіцяє бути найбільш плідним, хоча словникові методи й привабливі своєю швидкістю. Для порівняння (з метою вибору) алгоритмів компресії даних використовують критерії: - Клас даних (зображень), на який орієнтовано алгоритм. Іноді вказують, чому на інших класах даних виходять гірші результати. - Критерії порівняння вказують частку, на яку зросте архівований масив даних, якщо початкові дані найгірші, а також середньостатистичний коефіцієнт стискання для класу даних, на який орієнтований алгоритм, та кращий коефіцієнт. - Симетричність – відношення характеристики алгоритмів кодування і декодування (час, пам’ять). - Втрати якості. - Характерні особливості алгоритму і даних (для вибору алгоритму компресії певного класу даних). Під класом даних для стискання розуміють такі однотипні масиви даних (сукупність зображень), застосування до яких певного алгоритму архівації дає якісно однакові результати. Наприклад, для одного класу алгоритм дає дуже високу міру стиснення, для іншого – майже не стискає, для третього – збільшує файл у розмірі. Статичні растрові зображення являють собою двомірний масив чисел, елементи якого називають пікселями (pixel – picture element). Зображення бувають з палітрою і без неї. У зображень з палітрою в пікселі зберігається число в одномірному векторі кольорів. Найчастіше використовують палітри з 16 і 256 кольорів. Зображення без палітри бувають у будь-якій системі представлення кольору і в градаціях сірого (grayscale), для яких значення пікселя інтерпретують яскравістю відповідної точки. Для представлення кольорів у кожному пікселі записані компоненти кольору. Поширена система RGB, у якій є червона (R), зелена (G) і синя (B) компоненти. Зображенням можуть бути властиві плавні чи різкі зміни яскравості і кольорів, чіткі лінії. Аналогічно масиви даних вимірювань, спостережень (охорони) можуть відображати величини з повільними чи різкими змінами, скачками чи поодинокими викидами. Залежно від інформативності тих чи інших ознак масиву даних та вимог до процесу і результату архівації слід вибирати відповідний спосіб стискання. 5..2. Характеристики алгоритмів стискання Стискання здійснюється з метою зменшення фізичного розміру блоку інформації. Стискання інформації здійснює програма-компресор, а відновлення - програма-декомпресор. Стискання растрових і векторних даних здійснюється по-різному. В растрових файлах стискаються тільки дані зображення, а заголовок і решта даних (таблиця кольорів, кінцівка і т.п.) завжди залишаються нестисненими (вони, як правило, займають незначну частину растрового файла). Векторні файли, в яких зберігається математичний опис зображення, а не самі дані, як правило, не мають "рідної" форми стискання. Це викликано тим, що у векторному форматі дані вже представлені в компактній формі і стискання дає дуже незначний ефект. Окрім цього звичайно векторні дані читаються з малою швидкістю і при розпаковуванні цей процес може стати ще повільнішим. Якщо векторний файл все ж стискається, то, як правило, стискаються всі дані, включаючи заголовок. Більшість алгоритмів стискання забезпечують кодування без втрат, коли дані при розпаковуванні повністю відновлюються. Методи кодування з втратами передбачають відкидання деяких даних зображення для досягнення кращої міри стискання, ніж за методами без втрат. При цьому важливо, щоб втрата деякої частини даних була прийнятною або навіть доцільною. Найбільш поширеними алгоритмами стискання даних є групове кодування (RLE), алгоритм Лемпела-Зіва-Велча (LZW), кодування CCITT (Хафмена), технологія JPEG, алгоритм ART, алгоритми фрактального стискання зображень 1. Алгоритм RLE. Групове кодування (Run Length Encoding) – один з найдавніших і простих алгоритмів архівації ділової графіки. Зображення витягують у ланцюжок по рядках растра. Кодування зменшує фізичний розмір рядків символів, що повторюються. Такі рядки називають групами і кодують двома байтами, перший з яких визначає кількість символів в групі, а другий містить значення символу. Приклад. При груповому кодуванні отримуємо пари <пропустити, число> де «пропустити» є лічильником нулів, які пропускаються, а «число» - значення, яке ставлять у наступну комірку. Так, вектор 324000100002… буде стиснутий у пари (0,32)(0,4)(3,1)(4,2)… Ефективність стискання залежить від типу даних. Краще стискаються чорно-білі зображення, які містять багато білого кольору, а гірше - фотореалістичні зображення з великою кількістю кольорів (можливий негативний результат – збільшення файлу). Алгоритм RLE характеризується простотою і високою швидкодією. Варіанти групового кодування розрізняються напрямом утворення рядка (вздовж осі X, осі Y та діагоналі). Найчастіше вони стискають без втрат, однак відкидання молодших розрядів в значеннях символу може суттєво збільшити міру стискання складних зображень. 2. Алгоритми LZ. Існує велике сімейство LZ-подібних алгоритмів. У LZ-77 стиснення здійснюють за рахунок однакових ланцюжків байт. Варіант алгоритму LZW Лемпеля-Зіва-Велча широковідомий (Lempel-Ziv-Welch compression). Використовує дерева для представлення і зберігання ланцюжків. Із даних вхідного потоку він будує словник даних. Зразки даних ідентифікуються в потоці даних і зіставляються з записами у словнику. Якщо зразка даних нема в словнику, то на основі цих даних в словник записується кодова фраза, яка має менший розмір, ніж самі дані. Ця ж фраза записується і у вихідний потік стиснених даних. Якщо ж зразок даних зустрічається у вхідному потоці повторно, фраза, що відповідає йому, читається із словника і записується у вихідний потік. Оскільки кодові фрази мають менший розмір, ніж зразки даних, відбувається стискання. Декодування здійснюється в зворотному порядку. Декомпресор читає код з потоку стиснених даних і, якщо його ще нема в словнику, додає його туди. Потім цей код переводиться в рядок, який він представляє, і записується у вихідний потік нестиснених даних. Перевагою алгоритму LZW перед іншими, які базуються на словниках, є те, що не обов'язково зберігати словник для наступного декодування. Алгоритм LZW запатентований і його використання при створенні нових програмних продуктів обмежується ліцензійними угодами. Основні характеристики LZW. Відрізняється високою швидкодією при кодуванні та декодуванні, невибагливістю до пам’яті та простою апаратною реалізацію. Недолік – менший коефіцієнт компресії порівняно зі схемою двоступеневого кодування. Коефіціенти компресії: Приблизно 1000, 4 , 5/7 (Кращий, середній, гірший коефіціенти). Стиснення в 1000 разів можливе лише для одноколірних зображень, якшо їх розмір кратний приблизно 7 Мб. Клас зображення: LZW орієнтується на 8-бітні зображення, що були створені на комп’ютері. Стискає за рахунок однакових об’єктів у потоці. Симетричність: Майже симетричний, але за умов оптимальної реалізації операції пошуку рядка у таблиці. Характерні особливості: Ситуація, коли алгоритм збільшує зображення, зустрічаються не часто. LZW універсальний – його модифікації зустрічаються у звичайних архіваторах. 3. Стиск CCITT. Алгоритм Хафмена. Міжнародний Консультативний комітет з телеграфії і телефонії (CCITT) розробив серію комунікаційних протоколів для факсимільної передачі чорно-білих зображень по телефонних каналах і мережах передачі даних. Ці протоколи офіційно відомі як стандарти Т.4 і Т.6 CCITT, але більш розповсюджена їхня назва - стиск CCITT Group 3 і Group 4 відповідно. Іноді кодування CCITT називають кодуванням за алгоритмом Хафмена. Це простий алгоритм стиску, запропонований Девідом Хафменом у 1952 році. Стандарти Group 3 і Group 4 - це алгоритми стиску, спеціально розроблені для кодування однобітових даних зображення. Алгоритми CCITT не є адаптивними, тобто не настоюються для кодування кожного растра з оптимальною ефективністю. У них використовується фіксована таблиця кодових значень, що були обрані спеціально для представлення документів, які підлягають факсимільній передачі. Перед початком кодування здійснюється частотний аналіз коду документу і виявляється частота повтору кожного з символів. Символи, які частіше зустрічаються, кодуються меншою кількістю розрядів. Результат кодування зводиться в словник, що необхідний для декодування. При використанні кодування за схемою Хафмена разом із закодованим текстом треба передати відповідний алфавіт. Розглянемо простий приклад, що ілюструє роботу алгоритму Хафмана. Нехай задано текст, в якому літера 'А' входить 10 разів, літера 'B' - 8 раз, 'C'- 6 разів , 'D' - 5 разів, 'E' і 'F' - по 4 рази. Тоді один з можливих варіантів кодування за алгоритмом Хафмана наведений у таблиці: Таблиця 1 Символ Частота входження Бітовий код A 10 00 B 8 01 C 6 100 D 5 101 E 4 110 F 4 111 Як видно з таблиці 1, розмір вхідного тексту до стиснення рівний 37 байт, тоді як після стиснення - 93 біт (майже 12 байт без урахування довжини словника). Коефіцієнт стиснення 32%. Алгоритм Хафмена універсальний, тобто його можна застосовувати для стиснення даних будь-яких типів, але він малоефективний для файлів малих розмірів (за рахунок необхідності зберігання словника). На практиці програмні засоби стиснення даних синтезують ці три "чистих" алгоритми, оскільки їх ефективність залежить від типу та обсягу даних. У таблиці 2 наведені найпоширеніші формати стискання та відповідні їм програми-архіватори, що використовуються на практиці. Таблиця 2. Формат стискання Операційна система MS DOS Операційна система Windows Програма архівування Програма розархівування Програма архівування Програма розархівування ARJ Arj.exe Arj.exe WinArj.exe WinArj.exe RAR Rar.exe Unrar.exe WinRar.exe WinRar.exe ZIP Pkzip.exe Pkunzip.exe WinZip.exe WinZip.exe Крім того, сучасні архіватори надають користувачеві повний спектр послуг для роботи з архівами, основними з яких є: створення нового архіву; додавання файлів в існуючий архів; розпакування файлів з архіву; створення архівів, що саморозпаковуються (self-extractor archive); створення розподілених архівів фіксованих розмірів для носіїв малої ємності; захист архівів паролями від несанкціонованого доступу; перегляд вмісту файлів різних форматів без попереднього розархівування; пошук файлів і даних всередині архіву; перевірка на віруси в архіві до розпакування; вибір та налаштування коефіцієнта стиснення. 4. Стиск JPEG (Joint Photographic Experts Group - об'єднана група експертів з фотографії) є методом, що дозволяє стискати дані багатоградаційних зображень (фотографій, телевізійних заставок, іншої складної графіки) з піксельною глибиною від 6 до 24 біт з задовільною швидкістю й ефективністю. На відміну від інших методів стискання JPEG не є одним алгоритмом. JPEG може налаштовуватися на відтворення дуже маленьких стиснутих зображень поганої якості, але проте придатних для більшості програм, і в той же час дозволяє робити стиснені зображення дуже високої якості, обсяг даних яких набагато менший, ніж в оригінальних нестиснених даних. JPEG, як правило, супроводжується втратами. Схема JPEG заснована на відкиданні інформації, яку важко помітити візуально. Невеликі зміни кольору погано розпізнаються оком людини, а от незначні зміни інтенсивності (світліше чи темніше) - краще. Виходячи з цього, кодування з втратами JPEG прагне до дбайливого поводження з напівтоновою частиною зображення, але більш вільно поводиться з кольором. При цьому анімація (серія знімків, малюнків, силуетів окремих фаз руху), чорно-білі ілюстрації і документи, а також типова векторна графіка, як правило, стискуються погано. Обсяг стиснутих даних залежить від змісту зображення. Міра стиску зображення з фотографічною якістю може становити від 20:1 до 25:1 без помітної втрати якості. Звичайно ж, настільки високий показник стиску супроводжується відмінністю від оригіналу, але вона настільки незначна, що якість зображення все-таки залишається досить високою. Зображення, що містять великі області одного кольору, стискуються дуже погано. JPEG вводить у такі зображення артефакти (недоліки, вади), особливо помітні на суцільному фоні. Це значно погіршує якість зображень у порівнянні з традиційним методом стиску без втрат. 5. Стиск ART - це оригінальний алгоритм стиснення, що був створений і продається фірмою Johnson-Grace. Як і при роботі з алгоритмом JPEG, міра стиску в ART регулюється, а установка високого її значення може викликати втрати даних. Існує і режим кодування без втрат. Фірма Johnson-Grace продає ART як універсальний компресор для online-сервісів, а в перспективі планує адаптувати його для підтримки звуку, анімації і повномасштабного відеозображення. Хоча детальний опис цього алгоритму тримається в таємниці, Johnson-Grace випустила ряд документів описового характеру. Мета алгоритму - аналіз зображення і виявлення ряду його ключових ознак (колір, завади, межі, особливості, що повторюються), яким потім привласнюються пріоритети відповідно до відносної ваги кожної ознаки у вмісті зображення. Для класифікації і призначення пріоритетів ознакам стисненого зображення в програмі використовується нечітка логіка. Повторювані особливості виявляються і зв'язуються в зображенні оригінальним методом, розробленим самою фірмою. Компоненти зображення квантуются, при цьому низкопріоритетні ознаки ігноруються. Як і при використанні алгоритму JPEG, міра втрати інформації підвищується пропорційно росту міри стиску і компенсується певною надлишковістю. 6. Фрактальний алгоритм. Фрактальна архівація базується на представленні зображення у компактній формі за допомогою коефіцієнтів системи ітеративних функцій (Iterated Function System (IFS). По суті IFS являє собою набір тримірних афінних перетворень (при яких прямі переходять у прямі і зберігається їх паралельність), що переводять одне зображення в інше. Перетворенню підлягають точки у тримірному просторі (х-координата, у-координата, яскравість). Фактично фрактальна компресія – це пошук само подібних областей у зображенні і визначення для них афінних перетворень. Алгоритм декомпресії фрактального стиснення доволі простий: проводять ітерації тримірних афінних перетворень, коефіцієнти яких були отримані на етапі компресії. Початковим може бути довільне зображення (наприклад, чорне), оскільки математичний апарат гарантує збіжність послідовності зображень (у ході ітерацій IFS) до близького до вихідного зображення. Ґрунтується на тому факті, що всі природні і більшість штучних об'єктів містять надлишкову інформацію у виді однакових, повторюваних малюнків (фрагментів), які називають фракталами. Процес кодування, що перетворює зображення в сукупність математичних даних, вимагає винятково великого обсягу обчислень. Залежно від роздільної здатності і вмісту вхідних растрових даних, якості зображення, часу стиснення і розміру файлу процес стиснення одного зображення може зайняти від декількох секунд до декількох годин навіть на дуже швидкодіючому комп'ютері. Декодування фрактального зображення - процес набагато простіший, тому що вся трудомістка робота була виконана при пошуку всіх фракталів під час кодування. У процесі декодування потрібно лише інтерпретувати фрактальні коди, перетворивши їх у растрове зображення. Тому фрактальний метод доцільно використовувати тоді, коли дані зображень розпаковуються, але ніколи не стискуються. Фрактальний метод забезпечує легкість масштабування зображення (без введення артефактів і втрати деталей) та невеликий розмір стиснених даних але супроводжується втратами. Табл.3. Параметри алгоритмів стискання зображень Алгоритм Особливості зображення, за рахунок яких відбувається стискання RLE Підряд однакові кольори LZW Однакові підстрічки Хафмана Різна частота появи кольору ССІТЬ-3 Переважання білого або великі області одного кольору Рекурсивний Плавні переходи кольорів і відсутність різких границь JPEG Відсутність різких границь Фрактальний Подібність між елементами зображення Алгоритм Коеф-ти стискання Симетричніс ть за часом На що орієнтований Втрати Розмір ність RLE 32, 2, 05 1 3, 4 бітні Ні 1D LZW 1000, 4, 5/7 1,2-3 1-8 бітні Ні 1D Хафмана 8, 1,5, 1 1-1,5 8 бітні Ні 1D ССІТЬ-3 213, 5, 0,25 -1 1 бітні Ні 1D Рекурсивний 2-200 раз 1,5 24- бітні, сірі Так 2D JPEG 2-200 раз ~1 24- бітні, сірі Так 2D Фрактальний 2-2000 раз 1000-10000 24- бітні, сірі Так 2,5D Для опрацювання масивів даних, зображень використовують також адаптоване кодування, паралельні комп’ютерні архітектури (паралельну обробку інформації). Список використаної літератури 1. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. - М.: ДИАЛОГ-МИФИ, 2003. 2. http://www.compression.

Конспект лекцій Основи збору, передавання та обробки інформації

01.01.1970 03:01-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись