Коди Голомба

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

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

Вступ

Коди Голомба - сімейство ентропійних кодерів, які є загальним випадком унарного кода. Ентропійне кодування - кодування послідовності значень з можливістю однозначного відновлення з метою зменшення обсягу даних (довжини послідовності) за допомогою усереднення ймовірностей появи елементів у закодованій послідовності. Зазвичай ентропійні кодери використовують для стискання даних коди, довжина яких пропорційна від'ємному логарифму ймовірності символу [1].

Стиснення даних (англ. datа compression) -- алгоритмічне перетворення даних, з ціллю зменшення ними об'єму. Застосовується для більш раціонального зберігання и передачі данних. Обернена процедура називається відтворенням даних (розпакуванням, декомпресією) [3].

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

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

1. Класифікація методів стискання і кодування інформації

1.1 Кодування інформації

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

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

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

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

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

Чим більше вірогідність появи вхідного елемента, тим коротше відповідна результуюча послідовність. Прикладом можуть служити код Шеннона - Фано, код Хаффмана.

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

Якщо приблизні характеристики ентропії потоку даних попередньо відомі, може бути корисний більш простий статичний код, такий як Унарне кодування, гамма-код Еліаса, код Фібоначчі, код Голомба або кодування Райса [3].

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

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

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

Другий підхід - використовувати так званий адаптивний кодер (adaptive coder). Ідея полягає в тому, щоб змінювати схему кодування в залежності від вихідних даних. Такий алгоритм є однопрохідним і не потребує передавання інформації про використане кодування в явному вигляді. Замість цього декодер, зчитуючи кодований потік, синхронно з кодером змінює схему кодування, починаючи деякої початкової. Адаптивне кодування забезпечує більшу ступінь стискання, оскільки враховуються локальні зміни частот. Прикладом є динамічне кодування Хаффмана [2].

1.2 Стиснення інформації

Стиснення базується на усуненні надлишку інформації, яка міститься у вихідних даних. Наприклад, повторення в тексті фрагментів (наприклад, слів природної або машинної мови). Подібний надлишок зазвичай усувається заміною повторюваних послідовностей коротшим значенням (кодом). Інший вид надлишковості пов'язаний з тим, що деякі значення в даних, що стискаються, трапляються частіше інших, при цьому можна замінювати дані, що часто трапляються, коротшими кодами, а ті, що рідко, довшими (ймовірнісне стиснення). Стиснення даних, які не мають властивості надлишку (наприклад випадковий сигнал чи шум), неможливе. Також, зазвичай, неможливо стиснути зашифровану інформацію [3].

Види стиснення:

ѕ стиснення без втрат -- можливо відновлення вихідних даних без спотворень;

ѕ стиснення зі втратами -- відновлення можливе з незначними спотвореннями.

Стиснення без втрат використовується при обробці та збереженні комп'ютерних програм і даних.

Для деяких типів даних спотворення не припустимі в принципі. У їх числі:

ѕ символічні дані, зміна яких неминуче призводить до зміни їх семантики: програми та їх вихідні тексти, виконавчі масиви тощо;

ѕ життєво важливі дані, зміни в яких можуть призвести до критичних помилок: наприклад, одержувані з медичної вимірювальної апаратури або контрольних приладів літальних, космічних апаратів тощо;

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

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

Допустимість втрат. У загальному випадку алгоритми стиснення без втрат універсальні в тому сенсі, що їх застосування безумовно можливо для даних будь-якого типу, в той час як можливість застосування стиснення зі втратами потрібно обґрунтувати.

Системні вимоги алгоритмів

Різні алгоритми можуть вимагати різної кількості ресурсів обчислювальної системи, на яких їх застосовують:

ѕ оперативної пам'яті під проміжні дані;

ѕ постійної пам'яті під код програми і константи;

ѕ процесорного часу.

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

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

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

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

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

Алгоритми стиснення даних невідомого формату

Є два основних підходи до стиснення даних невідомого формату.

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

2. Для кожної ??послідовності символів, яку стиснено, одноразово або в кожний момент часу збирається статистика її появи в кодованих даних. На основі цієї статистики обчислюється ймовірність значення чергового кодованого символу (або послідовності символів). Після цього застосовується той чи інший різновид ентропійного кодування, наприклад, арифметичне кодування або кодування Хаффмана, для представлення частіших послідовностей короткими кодовими словами, а рідкіших -- довшими.

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

Більшість алгоритмів стиснення використовують стиснення з втратами. Нестиснене відео потребує високої частоти даних. Хоча кодеки виконують стиснення відео без втрат із коефіцієнтом стиснення 5-12, типове стиснення MPEG-4 із втратами має коефіцієнт стиснення в межах від 20 до 200 [2]. Як і при будь-якому стисненні з втратами, завжди відбувається пошук компромісу між бажаною якістю відео, затратами ресурсів на здійснення стиснення і декодування, і системними вимогами. Сильно зтисненне відео може мати візуально помітні артефакти.

Деякі схеми стиснення відео зазвичай оперують квадратні групи сусідніх пікселів, що називаються макроблоками. Ці групи пікселів або блоки порівнюються від одного кадру до наступного, і відео кодек посилає лише різницю в рамках цих блоків. Ті зони відео де є більше рухів, при стиснені треба закодувати більше даних, аби зберегти більшу кількість змінних пікселів. Зазвичай коли в кадрах відео є вибухи, полум'я, стада тварин, панорамні зйомки, велика частота зміни деталей призводить до зменшення якості або збільшення змінної бітової швидкості [4].

На рис 1.1 наведена класифікація методів стискання інформації

Рис 1.1 - Методи стискання інформації

2. Аналіз принципів кодування інформації

2.1 Статистичне кодування

код голомб інформація

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

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

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

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

Найпростішим способом статистичного кодування є кодування по методу Шеннона-Фано. Кодування відповідно до цього алгоритму виробляється так:

- спочатку всі букви з алфавіту повідомлення записують у порядку зменшення їхніх ймовірностей;

- потім усю сукупність букв розбивають на дві приблизно рівні по сумі ймовірностей групи; одній з них (у групі може бути будь-яке число символів, у тому числі - один) привласнюють символ “1”, іншої - “0”;

- кожну з цих груп знову розбивають (якщо це можливо) на дві частин і кожній з частин привласнюють “1” і “0” і т. д [3].

Процедура кодування по методу Шеннона-Фано подана в таблиці 2.1.

Таблиця 2.1 - Процедура кодування по методу Шеннона-Фано

Буква	Р(хi)	I	II	III	IV	V	Код	ni Pi
А	0.6	1					1	0.6
Б	0.2	0	1	1			011	0.6
В	0.1			0			010	0.3
Г	0.04		0	1			001	0.12
Д	0.025			0	1		0001	0.1
Е	0.015				0		00001	0.075
Ж	0.01					1	000001	0.06
З	0.01					0	000000	0.06

Для отриманого в такий спосіб коду середнє число двійкових символів, що приходяться на одну букву, дорівнює

,

Надмірність коду складе

.

Тобто також істотно меншу величину, ніж для рівномірного коду.

2.2 Ентропійне кодування

Ентропійне кодування - кодування послідовності значень з можливістю однозначного відновлення з метою зменшення обсягу даних (довжини послідовності) за допомогою усереднення ймовірностей появи елементів у закодованій послідовності [3].

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

Розрізняють декілька варіантів кодів:

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

ѕ Чим більше вірогідність появи вхідного елемента, тим коротше відповідна результуюча послідовність. Прикладом можуть служити код Шеннона - Фано, код Хаффмана;

ѕ Зіставлення кількох елементів вхідної послідовності фіксованого числа елементів кінцевої послідовності.

ѕ Прикладом є код Танстола;

ѕ Інші структурні коди, засновані на операціях з послідовністю символів.

ѕ Прикладом є кодування довжин серій.

Якщо приблизні характеристики ентропії потоку даних попередньо відомі, може бути корисний більш простий статичний код, такий як Унарне кодування, гамма-код Еліаса, код Фібоначчі, код Голомба або кодування Райса.

Згідно з теоремою Шеннона, існує межа стиснення без втрат, що залежить від ентропії джерела. Чим більш передбачувані одержувані дані, тим краще їх можна стиснути. Випадкова незалежна рівноймовірна послідовність стисненню без втрат не піддається [3].

2.3 Арифметичне кодування

Арифметичне кодування - це метод, що дозволяє стискати символи вхідного алфавіту без втрат за умови, що відомий розподіл частот цих символів. Концепцію методу наведено у роботах Еліаса в 60-х роках. Пізніше метод було розвинено та значно модифіковано [3].

Арифметичне кодування є оптимальним, досягаючи теоретичної границі стискання - ентропії вхідного потоку.

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

Ідея методу полягає в наступному: початковий текст розглядається як запис цього дробу, де кожен вхідний символ є “цифрою” з вагою, що пропорційна ймовірності його появи. Арифметичний декодер працює синхронно з кодером: почавши з інтервалу [0,1), він послідовно визначає символи вхідного ланцюжка.

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

У процесі декодування здійснюється зворотна процедура ототожнення прийнятого числа (інтервалу) із закодованим рядком символів. Очевидно, що на приймальній стороні повинні бути відомі ймовірності декодованих символів і відповідні їм інтервали числової осі [0,1). Нехай на вхід декодера надійшло число X = 0,21554. Оскільки воно перебуває в діапазоні 0,2 - 0,5, тобто 0,2X<0,5, то на вихід декомпресора видається символ С. Потім декодер визначає, в яку відносну частку відрізка [0,2 - 0,5) потрапляє число 0,21554, для цього він робить обчислення за формулою

де - відносне значення числа X на черговій ділянці числової осі.

У нашому випадку = (0.21554 - 0,2) / 0,3 = = 0,0518. Оскільки 0 < X < 0,1, то на вихід декомпресора надходить символ А. Неважко помітити, що процедура визначення вихідного символу рекурентна, при якій після знаходження першого діапазону для заданого числа X на одиничній числовій осі визначається відносна частка (діапазон) цієї частини відрізка, куди потрапляє декодоване повідомлення [3].

3. Основні теоретичні положення щодо кодів Голомба

3.1 Код Голомба

Коди Голомба -- сімейство ентропійних кодів. Були розроблені Соломоном Голомбом. Під кодом Голомба може матися на увазі також один із представників цього сімейства [3].

Розглянемо джерело, яке незалежним чином породжує цілі невід'ємні числа i з ймовірностями Р(і)=(1-р)р^і, де p - довільне позитивне число, яке не перевищує 1, тобто джерело, описуване геометричним розподілом.

Якщо при цьому ціле позитивне число m таке, що p^m=1/2, то оптимальним посимвольним кодом (тобто кодом, що ставить у відповідність кожному кодованого символу певне кодове слово) для такого джерела буде код, побудований згідно з запропонованою С. Голомбом процедурою, згідно з якою для будь-якого кодованого числа n при відомому m кодове слово утворюють унарний запис числа q=[n/m] і кодований відповідно до описаної нижче процедурою залишок r від ділення n на m.

Якщо m є ступенем числа 2, то код залишку являє собою двійковий запис числа r, розміщений в log₂(m) бітах.

Якщо m не є ступенем 2, обчислюється число b=[log₂(m)]

Далі: Якщо r<2^m - m, код залишку являє собою двійковий запис числа r, розміщений в b-1 бітах, інакше залишок r кодується двійковим записом числа r+2^b - m, розміщеним у b бітах.

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

p -p <=1<=p-p,

де m - ціле позитивне число. Оскільки для будь-якого p завжди знайдеться не більше одного значення m, що задовольняє наведеній вище нерівності, запропонована С. Голомбом процедура кодування геометричного джерела виявляється оптимальною для будь-якого значення p [1].

Надзвичайно простий в реалізації, але не завжди оптимальний різновид коду Голомба у разі, коли m є ступенем 2, називається кодом Райса.

Приклад

Нехай p = 0.85, потрібно закодувати число n = 13.

Задовольняє подвійній нерівності Галлагера - Ван Вурхиса значення m = 4.

Відповідно до описаної вище процедури кодування кодове слово, відповідне кодованому числу 13, будується як унарний запис результату від ділення n / m:

q=[n/m]=13/4=3

(унарний код 0001, тобто q нулів із завершальною одиницею), і кодованого залишку r = 1, (код 01, тобто власне залишок, записаний в [log₂(m)] бітах).

Результуюче кодове слово 0001 | 01

Код Голомба дозволяє представити послідовність символів у вигляді послідовності двійкових слів. Це перетворення буде оптимальним за умов, що розподіл ймовірностей символів входить у геометричний закон (3.1):

P(i) = (1-p)p, (3.1)

де i - номер символу, а р - параметр геометричного розподілу.

При кодуванні коротких повідомлень з символів великого алфавіту алгоритм Хаффмана и арифметичне кодування стає все більш складним в реалізації и менш ефективним, за рахунок великого об'єму інформації. Для джерел такого типу часто більш ефективним є застосування універсальних алгоритмів кодування, які використовують раніш задані ФПВ [1].

3.2 Экспоненційний код Голомба

Экспоненційний код Голомба порядку k -- це універсальний код, що задається цілим числом k. Для кодування невід'ємного числа в Экспоненційний код Голомба порядку k, можна використовувати наступний метод:

ѕ взяти число N у бінарному коді, без останніх k цифр. Прибавити до нього 1 (арифметично): N = N+1. Записати N.

ѕ підрахувати кількість C бит в N;

ѕ відняти з С один: С = С-1. Записати С нульових біт перед числом N.

Для порядку k = 0 код виглядає так:

0 => 1 => 1

1 => 10 => 010

2 => 11 => 011

3 => 100 => 00100

4 => 101 => 00101

5 => 110 => 00110

6 => 111 => 00111

7 => 1000 => 0001000

8 => 1001 => 0001001

...

Экспоненційний код Голомба при k = 0 застосовується в стандартах стиску відео H.264 та MPEG-4 AVC, у яких є також можливість кодування знакових чисел шляхом присвоєння значення 0 ключовому слову '0' у бінарному вигляді и прив'язок кодових символів вхідним значенням зростаючих амплітуд і змінних знаків.

Оцінка ентропії розраховується на більш довгих блоках N= 256 відліків. Зміни статистичних характеристик на коротких ділянках рахуються при кодуванні методом Райса короткими блоками, і усередкуются при рахуванні оцінки ентропії на більш довгих блоках. Цим пояснюється той факт, що середнє значення кодового слова виявляється нижче значення оцінки ентропії. це означає, що оцінка ентропії дає середнє значення ентропії на довгій ділянці, але реальне значення ентропії на ділянці відхилюється від її середнього значення. При цьому оцінка ентропії на коротких блоках має низку точність.

Экспоненційний код Голомба також використовується в алгоритмі кодування несжатого відео Dirac.

При k = 0 Экспоненційний код Голомба співпадає з гамма-кодом Еліаса при k=1. Таким чином, він може кодувати нуль, тоді як гамма-код Еліаса може кодіть тільки числа більше нуля.

Незважаючи на близькі назви, экспоненційне кодування Голомба лише суть аналогічно кодуванню Голомба, яке представляє собою тип ентропійного кодування, але не є універсальним кодом [1].

4. Середа розробки і програмування

Для розробки програми використовувалась середа розробки IntelliJ IDEA 17.2.5 на мові програмування Java.

IntelliJ IDEA -- комерційне інтегроване середовище розробки для різних мов програмування (Java, Python, Scala, PHP та ін.) від компанії JetBrains. Система поставляється у вигляді урізаної по функціональності безкоштовної версії «Community Edition» і повнофункціональної комерційної версії «Ultimate Edition», для якої активні розробники відкритих проектів мають можливість отримати безкоштовну ліцензію. Сирцеві тексти Community-версії поширюються рамках ліцензії Apache 2.0. Двійкові збірки підготовлені для Linux, Mac OS X і Windows [6].

Community версія середовища IntelliJ IDEA підтримує інструменти (у вигляді плагінів) для проведення тестування TestNG і JUnit, системи контролю версій CVS, Subversion, Mercurial і Git, засоби складання Maven, Ant, Gradle, мови програмування Java, Scala, Clojure, Groovy і Dart. Підтримується розробка застосунків для мобільної платформи Android. До складу входить модуль візуального проектування GUIінтерфейсу Swing UI Designer, XMLредактор, редактор регулярних виразів, система перевірки коректності коду, система контролю за виконанням завдань і доповнення для імпорту та експорту проектів з Eclipse. Доступні засоби інтеграції з системами відстеження помилок JIRA, Trac, Redmine, Pivotal Tracker, GitHub, YouTrack, Lighthouse [6].

Java (вимовляється Джава; інколи -- Ява) -- об'єктно-орієнтована мова програмування, випущена 1995 року компанією «Sun Microsystems» як основний компонент платформи Java. З 2009 року мовою займається компанія «Oracle», яка того року придбала «Sun Microsystems». В офіційній реалізації Java-програми компілюються у байт-код, який при виконанні інтерпретується віртуальною машиною для конкретної платформи [5].

«Oracle» надає компілятор Java та віртуальну машину Java, які задовольняють специфікації Java Community Process, під ліцензією GNU General Public License.

Мова значно запозичила синтаксис із C і C++. Зокрема, взято за основу об'єктну модель С++, проте її модифіковано. Усунуто можливість появи деяких конфліктних ситуацій, що могли виникнути через помилки програміста та полегшено сам процес розробки об'єктно-орієнтованих програм. Ряд дій, які в С/C++ повинні здійснювати програмісти, доручено віртуальній машині. Передусім Java розроблялась як платформо-незалежна мова, тому вона має менше низькорівневих можливостей для роботи з апаратним забезпеченням, що в порівнянні, наприклад, з C++ зменшує швидкість роботи програм. За необхідності таких дій Java дозволяє викликати підпрограми, написані іншими мовами програмування.

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

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

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

Основна перевага використання байт-коду -- це портативність. Тим не менш, додаткові витрати на інтерпретацію означають, що інтерпретовані програми будуть майже завжди працювати повільніше, ніж скомпільовані у машинний код, і саме тому Java одержала репутацію «повільної» мови. Проте, цей розрив суттєво скоротився після введення декількох методів оптимізації у сучасних реалізаціях JVM [6].

Висновки

Метою створення програмного продукту є реалізація кодування даних з використанням кода Голомба, що дозволяють зменшити надмірність данних -теле-радіосигналів. Экспоненційний код Голомба також використовується в алгоритмі кодування незжатого відео Dirac. При параметрі коду рівним нулю експоненційний код Голомба співпадає з гамма-кодом Еліаса при параметрі один. Таким чином, він може кодувати нуль, тоді як гамма-код Еліаса може кодувати тільки числа більше нуля.

Завдяки дуже простій схемі кодування и достатньо високої ефективності коди Голомба часто застосовують при кодуванні аудіо - і відеосигналів. А от для застосування в схемах універсального кодування вони не дуже умістні.

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

Під час виконання роботи були опрацьовані джерела інформіціі, вивчен алгоритм кодування кодом Голомба, розроблена програмна реалізація коду Голомба.

Література

1. S.W.Golomb. Run-length encodings. Inform. Theory, pp. - 502 с.

2. R.F. Rice, Some Practical Universal Noiseless Coding Techniques, Jet Propulsion Laboratory, JPL Publication 79-22, Pasadena, California Mar 1979. - 64 с.

3. Lossless data compression. Recommendation for space data systems standards. 1997.- 1002 с.

4. Горшков В.М. Методи кодування даних у системах телекомунікації. Київ. Издание «Освіта». 2004. - 404 с.

5. Кей С. Хорстманн. Java SE 8. Вводный курс Java SE 8 for the Really Impatient. -- М.: «Вільямс», 2014. - 879 с.

6. Брюс Эккель. Философия Java Thinking in Java. 3-е изд. - 976 с.

Размещено на Allbest.ru

...