забезпечують такий компроміс. Зауважімо, что середня довжина коду Хаффана (дів. Последний рядок табліці) менше, чем у других приведення кодів. Простий двійковій код має максимально Середнев Довжину. До того ж, ШВИДКІСТЬ кодом в 4,05 біта/символ, что досягається методом Хаффмана, наближається до Межі ентропії, рівної 4,0 біта/символ, підрахованої за формулою (1.3-3) i Наведеної внизу табліці. Хоча жоден з решті кодів, наведення у табліці 1.5, що не досягає ефектівності кодом Хаффмана, всі смороду являються більш простими для побудова. Подібно кодом Хаффмана, смороду прівласнюють Самі Короткі кодові слова найбільш імовірнім символам джерела.
Таблиця 1.5 Нерівномірні коди
стовпчики 5 Табліці 1.5 відповідає простій модіфікації основного методу кодування Хаффмана, назвається урізане кодування Хаффмана. Урізаній код Хаффмана будується только для найбільш ймовірніх сімволів джерела, де. Для представлення других (относительно рідкісніх) сімволів джерела вікорістовується код префікса, супроводжуваній кодом постійної довжина. У табліці 1.5 значення Було вибрать рівнім 12, а префіксом Було Тринадцята кодове слово кодом Хаффмана. Тім самим «символ префікс-коду» БУВ включень як тринадцятий (і Последний) символ модіфікованого кодового джерела з імовірністю, яка дорівнює сумі ймовірностей, что залиша сімволів з до. ЦІ 9 сімволів потім кодувалися при корістуванні кодом префікса, Який оказался рівнім, і 4-бітового двійкового коду, Рівного індексу символу мінус 13.
У стовпці 6 Табліці 1.5 наведено одного около до оптимального нерівномірного коду, відомій як В-код. ВІН около до оптимального, коли ймовірності сімволів джерела підкоряються степеневих закону увазі з Деяк позитивною константою.
например, Розподілення довжина серій в двійковому поданні типового машинописного текстового документа около експоненціальнім. Як видно з Табліці 1.5, кодове слово Складення з бітів продовження, Позначення С, и інформаційних бітів, Які є двійковімі числами. Єдиним Завдання бітів продовження є поділ ОКРЕМЕ кодів слів; для цього значення бітів продовження змінюються з 0 на 1 і навпаки для шкірного кодового слова в рядку. У-код, уявлень в Табліці 1.5, назівається-кодом того, что за шкірних бітом продовження Йдут дві інформаційних біта. Послідовність -кодів, відповідніх віхідній рядку сімволів буде віглядаті Наступний чином 001 010 101 000 010 або +101110001100 110, залежних від того, Вибране чі значення Першого біта продовження дорівнює 0 або 1.
Два нерівномірніх коди, что залиша в Табліці 1.5 відносяться до зсувніх кодів. Зсувній код формується послідовністю Наступний операцій: (1) упорядкування вихідних сімволів в порядку убування їх ймовірностей, (2) поділом Загально чісласімволів на блоки рівніх Розмірів, (3) кодування сімволів Всередині одного Блок І повторенням набору отриманий кодів для всіх Решт блоків, (4 ) Додавання спеціальніх сімволів Зсуви вгору і/або Зсув вниз для ідентіфікації шкірного з блоків. Всякий раз, коли декодер розпізнає символи Зсуви, ВІН переміщається на відовідне число блоків вгору або вниз по відношенню до основного блоку.
Щоб Сформувати 3-бітовій двійковій зсувне код, використанн в колонці 7 Табліці 1.5, вихідні символи (в кількості 21) спочатку були розташовані в порядку спадання їх ймовірностей и розділені на три блоки по 7 сімволів. Потім символи верхнього блоку - ВІН розглядається як опорний блок - кодуються двійковім кодом Із значень від 000 до 110. Восьмий двійковій код (111), що не входяшіе в опорний блок, вікорістовується як один символ Зсуви вгору и ідентіфікує блоки, что залиша (в даного випадка символ Зсуви вниз не вікорістовується). Символи в останніх двох блоках кодуються помощью одного або двох сімволів Зсуви в зелених сандалів з двійковім кодом, побудованім для опорного Блок І Поширеними на Інші блоки. Например, символ джерела буде закодовано як 111111 100.
Зсувній код Хаффмана в колонці 8 Табліці 1.5 формується схожим чином. Принципова Різниця Полягає в прісвоєнні ймовірності зсувного символу ще до кодування основного блоку по Хаффману. Як правило, значення ймовірності зсувного символу підраховується як сума ймовірностей всех сімволів поза основним блоком, а код зсувного символу візначається на Основі тихий же концепцій, что и префікс-код у урізаному коді Хаффмана. У даного випадка сума підраховується по віхіднім символам и становіть 0,39. Таким чином символ Зсуви віявляється найбільщ імовірнім символом и Йому пріпісується один з найкоротшіх кодів слів коду Хаффмана (0).
Арифметичний кодування
На Відміну Від Розглянуто Ранее нерівномірніх кодів, Арифметичний кодування створює неблоковіе коди. У Арифметичний кодуванні, історія которого может буті простежена аж до робот Елайеса, що не існує однозначної відпові...
