learn.armstankov
ЦОС · Тема 10 · Компресия

Предсказване – пращай само грешката

Следващият отчет на думата „Здравей“ почти винаги е близо до предишните. Ако и предавателят, и приемникът го отгатнат еднакво, стига да пратим само с колко сме сбъркали. Накрая пращаме само по 10 числа на всеки 20 ms – и думата пак се разбира, макар и с роботски глас.

≈ 6 мин четене∿ 10 живи уредаСамопроверка: 4 въпроса

Предсказване и грешка ​

Приближи думата: съседните отчети почти не се различават. Значи следващият може да се отгатне от предишните. Ако предавателят и приемникът отгатват по едно и също правило, не трябва да пращаме самия отчет – стига грешката на отгатването: e = x − x̂.

Най-простото правило е „същото като предишния“. Тогава грешката е просто разликата между два съседни отчета – и тя е 10,6 dB по-тиха от думата. По-тих сигнал иска по-малко битове (6 dB ≈ 1 бит).

Думата и разликата между съседните отчети
Входът: звукът, както е записан
020040060080010001200−101t – време, msx
входът x(n)
Изходът: звукът само разликата
020040060080010001200−101t – време, msy
изходът y(n)
Фигура 1.

Разликата е много по-тиха и звучи като съскане: ниските честоти (които носят силата на гласа) са най-лесни за отгатване и изчезват. Пробвай тона 440 Hz – него разликата почти изтрива.

Хистограмите: стойностите и грешките
корелация на съседите ρ = 0,97
Стойностите: ≈ 8 бита
0501001502002500200400x(i) – стойностброй N
x(i)
Разликите: ≈ 6 бита
−60−40−2002040600100200300e(i) = x(i) − x(i−1)брой N
e(i)
Фигура 2.

Самите стойности са пръснати по целия обхват (8 бита), а разликите – тясна камбана около нулата (3–4 бита). Намали корелацията ρ – камбаната се разширява и печалбата изчезва.

DPCM – диференциална ИКМ ​

DPCM прави точно това: предсказва x̂ = ρ·(предишния възстановен отчет), квантува грешката и праща нея. С 3 бита на отчет и стъпка 0,08 сега SNR = 17,2 dB (DPCM). Превключи между двете: при 3 бита обикновената ИКМ дава около 9 dB, а DPCM – около 17 dB, т.е. с повече от 1 бит по-добре.

Важно: кодерът предсказва от възстановената стойност, а не от оригинала – защото приемникът има само нея. Иначе грешките се натрупват и сигналът „отплава“.

Думата с 3 бита: DPCM или ИКМ
Входът: звукът, както е записан
020040060080010001200−101t – време, msx
входът x(n)
Изходът: звукът след декодера
020040060080010001200−101t – време, msy
изходът y(n)
Фигура 3.

С 3 бита обикновената ИКМ е силно зашумена; DPCM е чувствително по-чиста. Дръпни стъпката: твърде малка – изходът не смогва при силните части (претоварване по фронт); твърде голяма – в тишината се чува зърнест шум.

Отблизо: ред от изображение
предсказател ρ = 1
b = 3 бита → 7 нива на грешката
стъпка Δ = 4
3 бит/пиксел (CR = 8/3 = 2,67) → PSNR = 28,9 dB
0501001500100200i – пикселяркост
оригинал x възстановен x̃
Грешката на предсказване
050100150−20020i – пикселe
грешка e квантувана ẽ (предава се)
Фигура 4.

Сиво – оригиналният ред; синьо – възстановеният. Включи „грешен кодер“ (предсказва от оригинала) – декодерът отплава. С 3 бита и Δ = 2 рязкият ръб изостава; с Δ = 20 плавните части стават на стъпала (лъжливи контури).

ИзкривяванеКъдеЗащо
зърнест шумв тишина / равни областинай-малката стъпка не е 0
лъжливи контуриплавни преходигрубата стъпка се вижда
претоварване по фронтрезки преходинай-голямата стъпка е малка
натрупване на грешкислед грешен битсумата пази грешката

Против натрупването: коефициент на утечка α < 1 – старите грешки постепенно се „забравят“.

Делта модулация (DM и ADM) ​

Крайният случай на DPCM: 1 бит – само „нагоре“ или „надолу“ със стъпка 0,02. За да смогва, сигналът се снима 4 пъти по-често (64 kbit/s). Сега SNR = 8,32 dB. Адаптивната DM (ADM) гледа последните 3 бита: три еднакви подред → стъпката се удвоява (бърз фронт); редуване → намалява наполовина (тишина).

Думата с 1 бит на отчет
Входът: звукът, както е записан
020040060080010001200−101t – време, msx
входът x(n)
Изходът: звукът след DM
020040060080010001200−101t – време, msy
изходът y(n)
Фигура 5.

DM с малка стъпка: думата е заглушена – стъпалото не смогва. С голяма – силно зърнесто съскане. ADM с малка стъпка е ясна: стъпката сама расте на силните места.

Отблизо: стъпалото на DM
стъпка Δ = 4
DM, 1 бит/отчет, Δ = 4: MSE = 370
0501001500100200n – отчетA
оригинал DM
Фигура 6.

На скока стъпалото изостава (претоварване); в равните части трепери ±Δ (зърнест шум). Включи ADM – стъпката се удвоява на фронта.

Линейно предсказване от ред p (LPC) ​

По-умното правило гледа няколко предишни отчета: x̂ = a₁·x(n − 1) + … + aₚ·x(n − p). Най-добрите коефициенти идват от автокорелацията (колко сигналът прилича на себе си, изместен) чрез уравненията на Юл–Уокър, решени бързо с Левинсон–Дърбин.

С 10 коефициента грешката е 19,6 dB по-тиха от думата – печалбата от предсказване Gₚ.

Грешката след LPC
Входът: звукът, както е записан
020040060080010001200−101t – време, msx
входът x(n)
Изходът: звукът само грешката
020040060080010001200−101t – време, msy
изходът y(n)
Фигура 7.

С p = 1 грешката още звучи като дума. С 10 – почти като равно бръмчене с шум: предсказателят е „изял“ всичко предвидимо – тембъра на гласа. Остава само бръмченето на гласните струни и съскането.

Отблизо: LPC на два синуса и шум
ред p = 2
f = 200 Hz
шум = 0,05
a = [1,71; −0,761]
p = 2: печалба Gp = 16,1 dB (≈ 2,7 бита спестени)
01020304050−2−1012t, msA
x[n] предсказано x̂[n] грешка e[n]
Спектър: сигналът и грешката
01000200030004000−500f, HzdB
сигнал грешка (по-„бяла“ и по-слаба)
Фигура 8.

p = 1 → 2: печалбата скача – един синус се предсказва точно от 2 отчета. Вдигни шума – шумът не може да се предскаже.

LPC вокодер: само коефициентите ​

Щом грешката е почти само „бръмчене или шум“, може изобщо да не я пращаме! На всеки 20 ms пращаме само p-те коефициента, силата и дали звукът е звучен (гласна – бръмчене) или беззвучен („с“, „з“ – шум). Приемникът пуска бръмчене от 120 Hz или шум през филтъра с тези коефициенти. Така се пращат ≈ 3 kbit/s вместо 128 kbit/s – така са работили военните радиостанции и „говорещите“ играчки.

Думата от 10 числа на всеки 20 ms
Входът: звукът, както е записан
020040060080010001200−101t – време, msx
входът x(n)
Изходът: звукът синтезирана
020040060080010001200−101t – време, msy
изходът y(n)
Фигура 9.

Роботският глас казва „Здравей“, макар никой отчет на думата да не е пратен. Само шум: думата е прошепната. Само бръмчене: и „з“-то бръмчи. Смени височината – гласът става по-нисък или по-висок. Запиши своя глас и пробвай.

В картинки: 2D предсказателят „равнина“ x̂ = A + C − B (ляво + горе − горе-ляво): A = 100, B = 101, C = 104 → x̂ = 103. Ползва се в Lossless JPEG и PNG.

Адаптивно предсказване (LMS) ​

Речта сменя звуците, затова най-добрите коефициенти се менят. LMS ги учи отчет по отчет: всеки коефициент се побутва срещу грешката, a ← a + 2μ·e·s. Декодерът прави същото от същите данни, затова коефициентите не се пращат. Стъпката μ е колко бързо се учи; ако е твърде голяма, коефициентите избухват.

LMS се учи
стъпка на адаптация μ = 0,001
μ = 0,001 (граница 0,01): учи се и следва смяната на звука
02004006008001000−4−2024i – отчетa(k)
a(1) a(2)
Грешката на предсказване
02004006008001000−20020i – отчетe
грешка e(i)
Фигура 10.

Синусът по средата сменя честотата – „нова фонема“. При μ = 0,001 коефициентите се преучват; при 0,0001 – твърде бавно; над 0,01 избухват.

Самопроверка ​

1. Колко са 12 dB печалба от предсказване в битове?

≈ 2 бита по-малко на отчет при същото качество.

2. Защо при бял шум предсказването не помага?

Отчетите не са свързани: R(l) = 0 за l ≠ 0, най-доброто предсказание е 0, Gₚ = 0 dB.

3. Защо кодерът на DPCM предсказва от възстановената, а не от истинската стойност?

Приемникът има само възстановената. Ако кодерът ползва друга, двете страни се разминават и грешките се натрупват.

4. A = 100, B = 101, C = 104. Какво предсказва „равнината“?

x̂ = A + C − B = 103.

Ключови думи:ПредсказванеИКМ (PCM)Кодер / декодер / кодекКорелация ρАКФ R(l)Математическо очакване E{·}ХистограмаКоефициент на компресия CRИзлишност (redundancy)
Листче с формули (8)
Грешка на предсказванеe(i)=x(i)−x^(i)e(i) = x(i) - \hat{x}(i)
DPCMx^i=ρ x~i−1,x~i=x^i+Q(ei)\hat{x}_i = \rho\,\tilde{x}_{i-1}, \quad \tilde{x}_i = \hat{x}_i + Q(e_i)
Кодерът предсказва от възстановеното x̃, както декодерът.
Коефициент на компресияCR=log⁡2mxlog⁡2meCR = \dfrac{\log_2 m_x}{\log_2 m_e}
Предсказване от ред p (LPC)s^(i)=∑k=1pa(k) s(i−k)\hat{s}(i) = \sum_{k=1}^{p} a(k)\,s(i-k)
Юл–УокърR(l)=∑ka(k) R(k−l),R(l)=1N∑is(i) s(i−l)R(l) = \sum_{k} a(k)\,R(k - l), \qquad R(l) = \dfrac{1}{N}\sum_i s(i)\,s(i-l)
Печалба от предсказванеGp=10lg⁡σx2σe2 dBG_p = 10\lg\dfrac{\sigma_x^2}{\sigma_e^2} \text{ dB}
6 dB ≈ 1 бит по-малко.
2D предсказване (равнина)X^=A+C−B\hat{X} = A + C - B
LMSai+1(k)=ai(k)+2μ e(i) s(i−k),0<μ<1(n−1) E{s2}a_{i+1}(k) = a_i(k) + 2\mu\,e(i)\,s(i-k), \qquad 0 < \mu < \dfrac{1}{(n-1)\,E\{s^2\}}

Всички формули на предмета: листчето с формули.

Живите уреди в тази тема (6)

Едни и същи уреди се ползват в различните теми.

  • PredictionHistograms – Хистограми: стойностите срещу разликите между съседи
  • DpcmCoder – DPCM: предсказател, квантуване на грешката, отплаване при грешен кодер
  • DeltaModulator – Делта модулация и ADM: зърнест шум срещу претоварване по фронт
  • LpcPredictor – LPC по Юл–Уокър: коефициенти, печалба Gp, спектър на грешката
  • LmsPredictor – LMS: коефициентите се учат; при голямо μ избухват
  • SoundScope – Звукът на урока: вход и изход като вълна, с бутони ▶ за слушане