Кодиране с линейно предсказване

Кодирането с линейно предсказване (или LPC – Linear Predictive Coding) използва идея близка до подобрението на RLE за последователни, близки числа.

LPC използва подобен механизъм за сравнение на всеки символ от входното съобщение с друг елемент. Колкото този друг елемент е по-близък до сравнявания с него, толкова повече намалява амплитудата на кодираното съобщение.

Очевидно, най-подходящ елемент, който да се използва за базов и спрямо който да се извършва сравнението с останалите символи би бил елемент, който е максимално близък до средната стойност на останалите елементи. Стойността на този базов елемент може да се изчисли като математическото очакване на кода на симовла от входното съобщение.

Математическо очакване Математическото очакване на дискретна случайна велична x, приемаща стойности x1, x2, ... , xn с вероятности P(x2), P(x2), .... ,P(x3) се изчислява като EX = n ∑ i = 1 xiP(xi)

Преди да пристъпим към изчисляване на дадено очакване, трябва да знаем как да изчислим дадена вероятност.

Разглеждаме случайна велична x, която приема стойност 0 или 1 в зависимост от това, дали се пада ези или тура при хвърляне на монета.

Извършваме 10 000 хвърляния и получаваме 5043 пъти тура и 4957 пъти ези. Следователно вероятността x да стане 1 ( т.е. да се падне тура ) е 5043 / 10 000 = 0,5043.

Ако разгледаме зарче за игра, стойностите на случайната величана ще бъдат 1,2,3,4,5 и 6 и са равновероятни. Тогава, вероятността да се падне например 2 е

P ( 2 ) = 3 / 6 = 1 / 2

Аналогично, вероятността да се падне всяко едно от числата i на зарчето е

P( i ) = 1 / 6, 1 ≤ i ≤ 6

В такъв случай, математическото очакване за зарчето ще бъде:

EX = n ∑ i = 1 xiP(xi) = 1. P(1) + 2. P(2) + 3. P(3) + 4. P(4) + 5. P(5) + 6. P(6) =

= 1 . ( 1 / 6 ) + 2 . ( 1 / 6 ) + 3 . ( 1 / 6 ) + 4 . ( 1 / 6 ) + 5 . ( 1 / 6 ) + 6 . ( 1 / 6 ) =

= ( 1 + 2 + 3 + 4 + 5 + 6 ) / 6 = 21 / 6 = 3,5

По този начин получаваме, че 3, 5 е средния брой точки които се падат от зарчето.

ВАЖНО 3,5 не е естествено число и не е стойност на случайната величина. Очевидно, не е възможно да хвърлим 3,5.

Как се прилага математическото очакване в контекста на теорията на компресията:

Пример Нека е даден текст от 200 букви, като тяхното разпределние по думи е следното: Брой срещания на думата Брой букви в думата 74 1 31 2 10 3 2 5 1 24   Имайки предвид, че общия брой думи в текста е 74 + 31 + 10 + 2 + 1 = 118, можем да изчислим, че вероятността следващата дума да има k букви е : P ( k ) = (брой думи с дължина k) / 118, k I { 1, 2, 3, 5, 24 } Изчисляваме очакването: EX = 1.P( 74 ) + 2.P( 31 ) + 3.P( 10 ) + 5.P( 2 ) + 24.P( 1 ) = = 1.( 74 /118 ) + 2.( 31 /118 ) + 3.( 10 /118 ) + 5.( 2 /118 ) + 24.( 1 /118 ) = = (74 + 62 + 30 + 10 + 24) / 118 = 200/118 ≈ 1, 695 букви на дума.

 

Кодиране с линейно предсказване Кодирането с линейно предсказване работи като в процеса на преминване на входното съобщение натрупва статистически данни и пресмята очакването за всеки един символ. На изхода се предава единствено разликата между очакването и реалната стойност на кодирания символ. Вместо да изчислява наново очакването за всеки отделен символ, което би било крайно неефективно, алгоритъмът използва рекурентна връзка между старата стойност EXст и новото очакване – EXнов. В сила е: EXнов = ( (n – 1). EXст + код_на_символ ) / n Където: - n е дължината на съобщението (в брой знаци). - код_на_символ е кодът на текущия знак спрямо конкретната кодираща таблица (например ASCII). - EXст = { x1