Майже оптимальні нерівномірні коди

Побудова двійкового оптимального коду Хаффмана є незвичайним завданням, коли потрібно кодувати велику кількість символів. Для загального випадку J вихідних символів необхідно побудувати J - 2 редукцій джерела (див. Рис. 1.11) і виконати J - 2 привласнення коду (див. Рис. 1.12). Так, побудова оптимального коду Хаффмана для зображення з 256 рівнями яркостей, вимагає 254 редукції джерела і 254 присвоєння коду. Зважаючи на обчислювальну складність цього завдання, іноді доводиться жертвувати кодовою ефективністю для спрощення кодової комбінації.

У Таблиці 1.5 наведено чотири нерівномірних коди, які забезпечують такий компроміс. Зауважимо, що середня довжина коду Хаффана (див. останній рядок таблиці) менше, ніж у інших приведених кодів. Простий двійковий код має максимальну середню довжину. До того ж, швидкість коду в 4,05 біта/символ, що досягається методом Хаффмана, наближається до межі ентропії, рівної 4,0 біта/символ, підрахованої за формулою (1.3-3) і наведеної внизу таблиці. Хоча жоден з решти кодів, наведених у таблиці 1.5, не досягає ефективності коду Хаффмана, всі вони являються більш простими для побудови. Подібно коду Хаффмана, вони привласнюють самі короткі кодові слова найбільш імовірним символам джерела.

Таблиця 1.5. Нерівномірні коди.

Стовпчик 5 Таблиці 1.5 відповідає простій модифікації основного методу кодування Хаффмана, назвається урізане кодування Хаффмана. Урізаний код Хаффмана будується тільки для найбільш ймовірних символів джерела, де . Для представлення інших (щодо рідкісних) символів джерела використовується код префікса, супроводжуваний кодом постійної довжини. У таблиці 1.5 значення було вибрано рівним 12, а префіксом було тринадцятого кодове слово коду Хаффмана. Тим самим «символ префікс-коду» був включений як 13-й (і останній) символ модифікованого кодового джерела з імовірністю, яка дорівнює сумі ймовірностей, що залишилися символів з до . Ці 9 символів потім кодировались при користуванні коду префікса, який виявився рівним , і 4-бітового двійкового коду, рівного індексу символу мінус 13.

У стовпці 6 Таблиці 1.5 наведено друга близька до оптимального нерівномірного коду, відомий як В-код. Він близький до оптимального, коли ймовірності символів джерела підкоряються степеневому закону виду з деякою позитивною константою .

Наприклад, розподілення довжин серій в двійковому поданні типового машинописного текстового документа близько експоненціальним. Як видно з Таблиці 1.5, кодове слово складене з бітів продовження, позначених С, і інформаційних бітів, які є двійковими числами. Єдиним завданням бітів продовження є поділ окремих кодових слів; для цього значення бітів продовження змінюються з 0 на 1 і навпаки для кожного кодового слова в рядку. В-код, представлений в Таблиці 1.5, називається -кодом тому, що за кожним бітом продовження йдуть два інформаційних біта. Послідовність -кодів, відповідних вихідній рядку символів буде виглядати наступним чином: 001 010 101 000 010 або 101 110 001 100 110, залежно від того, вибране чи значення першого біта продовження дорівнює 0 або 1.

Два нерівномірних коди, що залишилися в Таблиці 1.5 відносяться до зсувних кодів. Зсувний код формується послідовністю наступних операцій: (1) упорядкуванням вихідних символів в порядку убування їх ймовірностей, (2) поділом загального числасимволів на блоки рівних розмірів, (3) кодуванням символів всередині одного блоку і повторенням набору отриманих кодів для всіх решту блоків, (4) додавання спеціальних символів зсуву вгору і/або зсуву вниз для ідентифікації кожного з блоків. Всякий раз, коли декодер розпізнає символи зсуву, він переміщається на відовідне число блоків вгору або вниз по відношенню до основного блоку.

Щоб сформувати 3-бітовий двійковий зсувне код, використаний в колонці 7 Таблиці 1.5, вихідні символи (в кількості 21) спочатку були розташовані в порядку спадання їх ймовірностей і розділені на три блоки по 7 символів. Потім символи верхнього блоку - він розглядається як опорний блок - кодуються двійковим кодом із значеннями від 000 до 110. Восьмий двійковий код (111), не входяшіе в опорний блок, використовується як один символ зсуву вгору і ідентифікує блоки, що залишилися (в даному випадку символ зсуву вниз не використовується). Символи в останніх двох блоках кодуються за допомогою одного або двох символів зсуву в комбінації з двійковим кодом, побудованим для опорного блоку і поширеним на інші блоки. Наприклад, символ джерела буде закодовано як 111 111 100.

Зсувний код Хаффмана в колонці 8 Таблиці 1.5 формується схожим чином. Принципова різниця полягає в присвоєнні ймовірності зсувного символу ще до кодування основного блоку по Хаффману. Як правило, значення ймовірності зсувного символу підраховується як сума ймовірностей всіх символів поза основним блоком, а код зсувного символу визначається на основі тих же концепцій, що і префікс-код в урізаному коді Хаффмана. В даному випадку сума підраховується по вихідним символам і становить 0,39. Таким чином символ зсуву виявляється найбільщ імовірним символом і йому приписується одна з найкоротших кодових слів коду Хаффмана (0).

Поиск по сайту: