Diseratie Vasilache Stefan 2017 [627303]
UNIVERSITATEA TEHNICĂ ,,GHEORGHE ASACHI” IAȘI
FACULTATEA DE ELECTRONICĂ, TELECOMUNICAȚII ȘI TEHNOLOGIA
INFORMAȚIEI
SPECIALIZAREA REȚELE DE COMUNICAȚII
PROIECT DE DISERTAȚIE
COMPRESIA DATELOR
(Audio și Text )
ÎNDRUMĂTOR: MASTERAND: [anonimizat]. TĂRNICERIU DANIELA VASILACHE DANIEL- ȘTEFAN
IAȘI 2017
Cuprins
Introducere …………………………………………………………………………………………………. 1
Metode de compresie …………………………………………………………………………………… 2
Metode de compresie bazate pe dicționar …………………………………………………………………. 3
Codarea Lempel-Ziv …………………………………………………………………………………………… 3
Algoritmul Lempel-Ziv ………………………………………………………………………………………. 5
Concluzii LZW ………………………………………………………………………………………………… 11
Standardul MPEG (Moving Pictures Expert Group) …………………………………. 12
Descrierea standardului MPEG-1 Audio …………………………………………………………………. 14
Descrierea stratului 3 al strandardului MPEG Audio ………………………………………………… 17
Descrierea standardului MPEG-2 AAC ………………………………………………………………….. 20
Concluzii ale standardului MPEG …………………………………………………………………………. 23
Tehnici de îmbunătățire a formatului MP3 (VBR,Joint -Stereo) ………………….. 24
MPC (Musepack) ………………………………………………………………………………………………… 26
Vorbis ………………………………………………………………………………………………………………… 29
Overview pentru standardul MP3 ………………………………………………………………………….. 31
Coduri utilizate pentru semnalul vocal ………………………………………………………. 35
Codul cu predictive liniară (CELP) ………………………………………………………………………… 35
Principiul CELP ………………………………………………………………………………………………….. 37
Simplificările procedurii de căutare CELP folosind aproximarea aucorelativă …………….. 38
Performanțele CELP ……………………………………………………………………………………………. 41
Modele pentru analiza prin sinteza a semnalului vocal eșantionat ………………. 43
Moduri p entru analiza prin sinteză LPC …………………………………………………………………. 43
Modelul general de analiză ………………………………………………………………………… 44
Predicția pe termen scurt ……………………………………………………………………………. 48
Metoda autocorelației ……………………………………………………………………… 50
Metoda covarianțelor ………………………………………………………………………. 52
Considerații în alegerea condițiilor de analiză LPC ………………………………………………….. 54
Concluzii …………………………………………………………………………………………………… 58
Bibliografie ……………………………………………………………………………………………….. 59
Abrevieri …………………………………………………………………………………………………… 60
Anexe ……………………………………………………………………………………………………….. 61
1
INTRODUCERE
Noțiunea de compresia datelor a apărut pe la 1940 prin lucră rile lui Shanon si Fano care
au dezvoltat un algoritm eficient de compresie ; acest algoritm a fost repede îmbunătăț it de
Huffman prin minimizarea redundanței (1952). El a ră mas nesch imbat pana în 1977 când Ziv ș i
Lempel au stabilit o manier ă total diferită de compresie, denumită schema de dicționar
(dictionary scheme). Mulț i din algoritmii de compresie utilizați în prezent utilizează variante ale
acestor scheme de baza.
Sursele d e informaț ie pot fi continue (imagini, semnale audio) sau sau discrete (fisiere
text). Majoritatea datelor memorate în sistemele bazate p e calculatoare sunt numerice, așa cum
sunt imaginile scanate și semnalele digitizate. Î n cazul surselor continue de in formaț ie,
reprezentarea nu merica din calculatoare este obținută prin discretizare (eșantionare ș i cuantizare),
deci este i ntrinsec cu pierdere de informaț ie. Pentru aceste date metodele de compresie sunt – de
obicei – cu pierdere de informație și ră spund u tilizării finale a informaț iei. Raportul sau gradul de
compresie poate fi oricât de mare și se alege printr -un compromis între calitatea obținută după
comprimare. În caz ul surselor discrete de imformație, compresia datelor se face fără pierdere de
informa ție.
Scopul compr esiei este de a reduce redundanța memorată sau continută î n datele din
comunicații, în vederea creș terii vitezei de transmisi e. Compresia datelor are aplicații mari în
domeniul stocării/memorării fisierelor și î n sisteme distribuite.
Comp resia datelor este considerată adesea ca o codare, î n timp ce codarea este un termen
foarte general referindu-s e la orice reprezentare specială ce satisface un anumit scop. Teoria
informației s -a ocupat de studiul eficient al metodelor de codare, ținând seama de probabilitatea
de eroare ș i de viteza de transmisie. C ompresia datelor poate fi văzută ca o latură a teoriei
informației î n care obiectivul principal este de a minimiza cantitatea de date ce trebuie
transmisă.Î n acest fel se reduce costul transmisie i și/sau al memoră rii. Simplu, este foarte
avantajos să comprimi un fisier la jumătate din marimea lui inițială.
O caracaterizare simplă a co mpresiei este aceea ce se referă la transformarea unui șir de
caractere într- o anumită reprezentare (cum este ASCII) într- un nou șir (de biți, de exemplu), care
conține aceeași informaț ie, dar are lun gimea mai mică pe cât posibil. Pentru toate tipurile de
compresie se presupune un canal fara zgomot, deci nu se pune problema corecț iei erorilor.
Compresia textelor este importantă în aplicaț iile internet unde marea majoritate a datelor
sunt de tip text.
2
METODE DE COMPRESIE
Metodele de compresie se încadrează în douã categorii : statice și dinamice .
Metodă staticã de compresie fixeazã corespondența între mesaje și cuvintele de cod
înainte de începerea codificãrii și o pãstreazã pe toatã durata ei. Exemplul clasic este codul lui
Huffman, în care corespondența se bazeazã pe probabilitatea de apariție a mesajelor în secvență
de mesaje; astfel, combinațiilor mai frecvente le sunt asociate cuvinte de cod mai scurte.
Aplicarea codificãrii Huffman se face în doi pași: în primul se calculeazã probabilitățile și se
stabilește corespondența între coduri, iar în al doilea pas se transformã șirul de mesaje.
Metodă dinamicã de compresie este metodă în care corespondența dintre mesaje și
cuvintele de cod se schimbã în timp. Codificarea Huffman dinamicã actualizeazã corespondența
pe baza frecventelor relative de apariție a mesajelo r, calculate pe mãsura transformãrii lor. În
acest fel, același mesaj poate fi reprezentat prin cuvinte de cod diferite, dacã frecvența să relativã
se modificã pe parcurs ( la începutul șirului de mesaje va avea un cuvânt de cod, iar la sfârșitul
șirului a lt cuvânt de cod).
Eficiența unei metode de compresie poate fi apreciatã după complexitatea algoritmilor
folosiți și dupã mãsura comprimãrii realizate. În cazul arhivãrii datelor, economia de memorie
este determinantã, cu condiția ca algoritmii sã aibã com plexitate rezonabilã. În cazul transmisiei
la distantã a informației, atât complexitatea algoritmilor cât și rată de compresie afecteazã viteză
de transmisie.
Compresia fără pierderea informației poate fi întâlnită în cazul utilitarelor ZIP (pentru
fișiere text) și GIF (imagine). Acesta din urmă diferă de formatul JPEG care pierde din
informație. Câțiva algoritmi utilizați în utilitarele de arhivare sunt prezentați în tabelul din fig.1.
Familia Variante Utilizat in
Huffman Huffman
Adaptive Huffman
Shannon-Fano MNP5
COMPACT
SQ
LZ78
(Lempel-Ziv 1978) LZW (Lempel-Ziv-Welch) GIF
v.42bis
compress
LZ77
(Lempel-Ziv 1977) LZFG ZIP
ARJ
LHA
Figura 1. Algoritmi utilizati in utilitarele de arhivare
3
Interesul pentru reducerea spațiului ocupat de fișiere pe suporții magnetici a impus
constituirea algoritmilor de comprimare. Comprimarea este un proces prin care se transferã un
fișier inițial într -un fișier a cãrui lungime este cu mult mai micã decãt a celui inițial.
Decomprimarea este procesul invers comprimãrii.
Programele care implementeazã acești algoritmi utilizeazã un set de 10 fișiere generate
astfel încât sã se includã atât situațiile de structurare a textelor cât și cazurile particulare(texte ce
conțin un singur simbol sau texte de lungime n octeți ce conțin n simboluri diferite.
Metode de compresie bazate pe dictionar.
Codarea Lempel-Ziv
Multe din programele de compresie performante folosesc algoritmi bazați pe dicționare
dinamice.Cel mai utilizat este algoritmul LZW (Lempel-Ziv-Welch).
Este un algoritm ce stă la baza multor programe de compresie: compress and uncompress,
din UNIX , sau gzip and gunzip, sau WinZip din Windows. Algoritmul de compresie este de tipul
lungime variabilă – lungime fixă, în opoziție cu codarea Huffman (lungime fixă – lungime
variabilă). Deși există mai multe versiuni ale algoritmului se pot distinge două categorii: teoretică
și practică. Diferența dintre ele constă în faptul că – în varianta teoretică – optimalitatea
asimptotică se poate mai ușor demonstra. Variantele practice pot fi mai ușor de implementat.
Aceste metode constau dintr-o serie de reguli de identificare a unor grupuri de simboluri
și gruparea/depunerea lor într -un dicționar care se asociază sursei de informație. Dacă se
întâlnește un anumit grup de simboluri, se crează un indicator (pointer) corespunzător locului
ocupat de respectivul grup în dicționar. Cu cât se întâlnește mai des un anumit grup de simboluri,
cu atât este mai mare raportul de compresie.
Deci, aceste metode codează șiruri de simboluri de lungime variabilă cu semne
individuale, fiecare semn reprezentând un indicator (index) într- un dicționar. Evident, se obține o
compresie atunci când noile semne sunt de lungime mai mică.
Exemplu: Fie c onvenția reprezentării unui cuvânt dintr -o carte prin două atribute:
(Numărul paginii) / (numărul cuvântului din pagină).
Atunci, mesajul „Titlul acestui capitol este compresia datelor ” poate fi înlocuit prin
500/3 1/5 10/2 15/9 10/6 12/1
Cuvântul „Titlul ” este înlocuit prin 500/3, ceea ce reprezintă al treilea cuvânt din pagină
500. Cuvântul „compresia ” este al 6 cuvânt din pagină 10.
4
Mărimea mesajului comprimat depinde de mărimea dicționarului, deci de numărul de
pagini și de numărul de înregistrări pe pagină. Dacă aceste două mărimi se notează cu NP
(numărul de pagini) și NR(numărul de înregistrări pe pagină) atunci numărul de biți pentru
reprezentarea (codarea) unui cuvânt din dicționar este
[log2(NP)] + [log2(NR)],
unde parantezele drepte arată rotunjurea la cel mai apropiat întreg.
Întrucât trebuie considera t și marimea mesajului d e la intrare, exprimat prin numărul de
simboluri, NS, rezultă un raport de compresie
)NRlog()NPlog( NS)NRlog()NPlog(NS)biti(RC 8 8
Exemplu numeric:
Dacă dicționarul conține 2200 pagini, sunt necesari log2(2200) = 11.03 – > 12 biți pentru a
coda numărul paginii. Dacă fiecare pagină conține un număr de cuvinte de 256 sunt necesari un
număr de log2(256) = 8 biți pentru codarea fiecărui cuvânt. Că urmare, un cuvânt oarecare din
dicționar este codat pe 20 (=11+8) biți sau 2.5 -> 3 octeti.
Mesajul comprimat va avea lungimea 20 biți * 6 cuvinte = 120 biți sau 18 octeti. În
reprezentarea ASCII, cele 6 cuvinte necesită un total de (6+7+7+4+9+7) = 40 * 8 = 320 biț i, deci
40 octeti. Raportul de compresie este
662120320.bitibiti)biti(RC sau 2221840.octetiocteti) octeti(RC
Dicționarele pot fi statice sau adaptive . Un dicționar static este construit și transmis
odată cu textul comprimat și este folosit că referințele citate într -o lucrare științifică. Un dicționar
static este construit înaintea efectuariii compresiei și rămâne neschimbat pe toată durata acesteia.
Dicționarul static are avantajul că poate fi „ ales” („acordat ”) în vederea codării, înregistrările care
apar cu cea mai mare frecvența putând fi codate cu numărul cel mai mic de biți, în confor mitate
cu regulile de codare enrtropica.
Dezavantajul folosirii unui dicționar static apare la compresia fișierelor mici, când, din
cauza transmisiei/memorării atât a dicționarului cât și a fișierului comprimat, raportul de
compresie nu este foarte bun, de multe ori chiar subunitar. De aceea, cei mai răspândiți sunt
algoritmii de compresi e bazați pe dicționare adaptive. Un dicționar adaptiv constă în adăugarea
unei abrevieri pe lângă anumite grupe de simboluri, când apar prima oară, și utilizarea în
continuare doar a abrevierilor.
5
Algoritmul Lempel-Ziv
Acest exemplu se referă la o versiune simplă a algoritmului Lempel -Ziv. Schemă de
compresie trebuie să împartă datele în sub -șiruri, să codeze sub -șirurile, și să fie posibilă și
operația inversă.
Fie următorul șir de date:
001101100011010101001001001101000001010010110010110
Primul pas constă în împărțirea șirului de date în subsiruri, astfel încât la fiecare definiție
a unui subsir să nu existe repetitiii, deci el să nu fi fost definit anterior. Se va utiliza virgulă că
separator de sub- șiruri. La începutul șirului se pune o virgulă pentru a evidenția șirul de lungime
zero. Se pune apoi o virgulă după primul zero, intracat nu a mai apărut.
Al doilea bit este zero și se consideră și al doilea simbol, 1, obținându -se șirul 0 1. Întrucât
acesta este șir nou se pune virgulă. Urmează simbolul 1, care fiind caracter nou, atrage virgulă
după el. Apoi apare un zero, mai trebuie un zero (deci încă un simbol), că să fie un șir nou.
Rezultatul constă în următoarea lista de șiruri
,0,01,1,011,00,0110,10,101,001,0010,
01101,000,00101,001011,0010110
Pasul doi constă în derminarea numărului de biți pentru reprezentarea secvenței astfel
obținute. Practic, se numerotează șirurile începând cu primul șir de lungime nenulă.
Se determina numărul de biți după relația
N logk 2
unde N reprezintă numărul de șiruri și paranteză are rolul de rontunjire la cel mai mic întreg.
Pentru primul exemplu considerat se constată că sunt 16 simboluri (inclusiv șirul de lungime
zero) și sunt necesari 4 biți pentru reprezentarea fiecărui șir.
Pasul trei constă în codarea șirurilor, astfel obținute. Se completează un tabel de formă de
mai jos, în care se definesc: șirul, numărul ce arată poziția șirului, prefixul, numărul ce arată
poziția prefixului, și codul șirului. Codul șirului este obținut considerând numărul ce arată poziția
prefixului urmat de ultimul bit al șirului considerat, așa cum se prezintă în tabelul următor.
6
Nr.
sirului Sirul Codarea
pozitiei sirului Prefix Codarea
pozitiei prefixului Sir codat
1. 0 0001 empty 0 = 0000 0000+0 = 00000
2. 01 0010 0 1 = 0001 0001+1 = 00011
3. 1 0011 empty 0 = 0000 0000+1 = 00001
4. 011 0100 01 2 = 0010 00101
5. 00 0101 0 1 = 0001 00010
6. 0110 0110 011 4 = 0100 01000
7. 10 0111 1 3 = 0011 00110
8. 101 1000 10 7 = 0111 01111
9. 001 1001 00 5 = 0101 01011
10. 0010 1010 001 9 = 1001 10010
11. 01101 1011 0110 6 = 0110 01101
12. 000 1100 00 5 = 0101 01010
13. 00101 1101 0010 10 = 1010 10101
14. 001011 1110 00101 13 = 1101 11011
15. 0010110 1111 001011 14 = 1110 11100
Secvența comprimată este format prin concatenarea tuturor sirulor codate, aflate în ultima
coloana a tabelului de mai sus. Se obține:
00000-00011-00001-00101-00010-01000-00110-01111
01011-10010-01001-01010-10101-11011-11100
Comparând lungimea secvenței comprimate cu lungimea secvenței originale se constată
că secvență comprimată are o lungime mai mare. Acest rezultat este explicat prin faptul că
secvență de intrare este de lungime foarte mică. Pentru fișiere cu secvență de lungime de
milioane de simboluri se con stată cu raport de compresie de până la 2, depinzând și de conținutul
fișierului.
7
Idea de baza este de a imparti ( parse -in limba engleza) secventa de intrare in blocuri
(siruri ) diferite de lungime diferita. Multimea blocurilor diferite defineste un dictionar. Indexul
cuvintelor din dictionar este salvat in fisierul comprimat.
ALGORITM DE CODARE LZW:
Date intiale: Alfabetul A; secventa de intrare in;
#1. Initializeaza dictionarul cu simbolurile alfabetului;
#2. Initializeaza secventa comprimata: code =’’;
#3. Citeste primul caracter de intrare, sirul prefix S: S = in(1);
#4. CAT TIMP nu s-a parcurs toata secventa de intrare EXECUTA:
#4.1.Citeste urmatorul caracter de intrare: K = in(i +1).
#4.2. DACA sirul SK este in tabel
ATUNCI
#4.2.1. Asigneaza: S = SK;
ALTFEL
#4.2.2. Memoreaza SK in dictionar;
#4.2.3. Asigneaza: S = K ;
#4.2.4. Scrie: code = code + code (S);
END #4.2;
END #5;
END.
Exemplul 1 – Se da secventa sub forma unui sir de simboluri din alfabetul b , a A , de forma
bba abbaaaabaa abbaabbaabin . In urma rularii programului din anexa 2 se obtin rezultatele:
D = 'a' 'b' 'ab' 'bb' 'ba' 'aa' 'abb' 'baa' 'aba' 'abba' 'aa a' 'aab' 'baab' 'bba'
code = '1' '2' '2' '1' '3' '5' '3' '7' '6' '6' '8' '4'
In ipoteza utilizarii codului ASCII pe 8 biti secventa de intrare are 23*8 = 181 biti.
Secventa binara rezultata in urma comprimarii este 13 * 4 = 52 biti. Presupunand ca se cunoaste
alfabetul si dictionarul, atat la emisie cat si la receptie, ar rezulta un raport de compresie
48352181. RC
In realitate raportul de compresie este mai mic intrucat trebuie transmis si dictionarul
folosit la codare. Raportul de compresie este imbunatatit cu cat fisierul de intrare este mai mare si
cu cat exista mai multe date redundante.
Exemplul 2 – Se da secventa sub forma unui sir de simboluri din alfabetul c , b , a A de forma
aaaaaaa ababcbababin . Se obtin rezultatele:
D = 'a' 'b' 'c' 'ab' 'ba' 'abc' 'cb' 'bab' 'baba' 'aa' 'aaa ' 'aaaa'
code = '1' '2' '4' '3' '5' '8' '1' '10' '11'
8
Exemplul 3: Se da secventa sub forma unui sir de simboluri din alfabetul BT,D,E,W,/,A de
forma E/WEB/WET /WED/WE/WEin . In urma rularii programului din anexa 2 se obtin
rezultatele:
D = '/' 'W' 'E' 'D' 'T' 'B' '/W' 'WE' 'ED' 'D/' '/WE' 'E/' '/WEE' 'E/W'
'WEB' 'B/' '/WET'
code = '1' '2' '3' '4' '7' '3' '11' '12' '8' '6' '11'
Exemplul 4: Fie mesajul „abba_baba_buba ” si dictionarul initializat cu alfabetul sursei, adica
D={a,_,b,u }.
1). Initializare: code ={}, S=’’; D={a,_,b,u }.
2). Citeste primul caracter: „abba_baba_buba ”
; " " , " " , " " a SKSDa SKa K
3). Citeste urmatorul caracter „abba_baba_buba ”
" "} 1 { ) "(" ) (}, , _,, { }{"" , " "
b KSa index code S index code codeabu b a SK DDD ab SKb K
4). Citeste urmatorul caracter „abba_baba_buba ”
" "} 3 , 1 { ) "(" ) (},, , _,, { }{"" , " "
b KSb index code S index code codebbabu b a SK DDD bb SKb K
5). Citeste urmatorul caracter „abba_baba_buba ”
""} 3 , 3 , 1 { ) "(" ) (},,, , _,, { }{"" , ""
a KSb index code S index code codebabbabu b a SK DDD ba SKa K
9
6). Citeste urmatorul caracter „abba _baba_buba ”
_""} 1 , 3 , 3 , 1 { ) "(" ) (_},,,, , _,, { }{_"" ,_""
KSa index code S index code codeababbabu b a SK DDD a SK K
7). Citeste urmatorul caracter „abba_ baba_buba ”
" "} 2 , 1 , 3 , 3 , 1 { )_"(" ) (}__,,,,, , _,, { }{"_ " , " "
b KSindex code S index code codeb ababbabu b a SK DDDb SKb K
8). Citeste urmatorul caracter „abba_b aba_buba ”
"" "" , " " ba SKS D ba SKa K
9). Citeste urmatorul caracter „abba_ba ba_buba ”
" "} 7 , 2 , 1 , 3 , 3 , 1 { ) " (" ) (},__,,,,, , _,, { }{" " , " "
b KSba index code S index code codebabb ababbabu b a SK DDD bab SKb K
9). Citeste urmatorul caracter „abba_bab a_buba ”
"" "" , " " ba SKS D ba SKa K
10). Citeste urmatorul caracter „abba_baba _buba ”
_""} 7 , 7 , 2 , 1 , 3 , 3 , 1 { ) " (" ) (_}, ,__,,,,, , _,, { }{_"" ,_""
KSba index code S index code codebaabab ababbabu b a SK DDD ba SK K
12). Citeste urmatorul caracter „abba_baba _buba”
"_ " "_ " , " " b SKS Db SKb K
10
13). Citeste urmatorul caracter „abba_baba _buba”
" "} 9 , 7 , 7 , 2 , 1 , 3 , 3 , 1 { ) "_(" ) (}_ , ,__,,,,, , _,, { }{"_ " , " "
u KSb index code S index code codebu abab ababbabu b a SK DDD bu SKu K
14). Citeste urmatorul caracter „abba_baba _buba”
" "} 4 , 9 , 7 , 7 , 2 , 1 , 3 , 3 , 1 { ) "(" ) (},_ , ,__,,,,, , _,, { }{"" , " "
b KSu index code S index code codeubbu abab ababbabu b a SK DDD ub SKb K
15). Citeste urmatorul caracter „abba_baba _buba”
"" "" , " " ba SKS D ba SKa K
Rezultatele finale sunt:
D = { ' a' '_' ' b' 'u' 'ab' 'bb' 'ba' 'a_' '_ b' 'bab' 'ba_' '_ bu' 'ub'}
code = {1, 3, 3, 1, 2, 7, 7, 9, 4}
Presupunând ca se cunoaște alfabetul și dicționarul, atât la emisie cât și la recepț ie, ar rezulta un
raport de compresie maxim
48. 245112
5 * _ 98 * 14 biti index simboluribiti simboluriRC
11
Concluzii LZW
Așa cum este de aș teptat, rezultatele compresiei depind mult de tipul datelor de
comprimat. În tabelul de mai jos se prezinta rezultatele obținute pentru diferite conținute ale
fișierelor.
Adaptive Huffman
(compact sub Unix) Lempel-Ziv
(compress sub UNIX)
LaTeX file 66% 44%
Speech file 65% 64%
Image file 94% 88%
Această metodă de compresie se folosește la o serie de standarduri de imagine, cum sunt
GÎF și TIFF, în standardul V.24bis al modemurilor și în standardul PostScript Level 2. LZW este
un algoritm general care poate lucra pe orice tip de date. Este rapid atât la compresie cât și la
decompresie și nu necesită operații în virgulă mobilă. LZW scrie datele compresate sub formă de
octeti și nu că și cuvinte, ceea ce face că datele comprimate să fie independente de platforma.
Acesta este cunoscut că făcând parte din categoria algoritmilor de codare bazați pe dicționar sau
substitutional.
Algoritmul construiește un dicționar (denumit și tabel de translație sau tabel de șiruri) al
datelor ce apar în fluxul de date ce trebuie comprimat. În fluxul de date se identifica forme de
date (substrings) și memorate în intrările dicționarului. Dacă un subsir nu este prezent în
dicționar, la momentul întâlnirii sale, respectivul subsir se memorează și se codifică în dicționar.
Codul alocat sub- șirului este scris în secvență de ieșire, care este secvență comprimată. Când se
întâlnește un subsir deja existent în dicționar, în secvență de ieșire se scrie codul subsirului
existent în dicționar.
Avantajul LZW es te că nu trebuie memorat dicționarul în vederea decodării secvenței
comprimate, lucru avantajos în unele aplicații. Când se comprimă fișiere text, LZW initializeaza
primele 256 intrări ale dicționarului cu codul ASCII că fiind fraze (șiruri de lungime 1). Mai
departe, toate subsirurile sunt construite pe baza simbolurilor individuale, definite anterior.
Pentru secvențe de intrare foarte mari lungimea dicționarului poate crește foarte mult. De
aceea, în practică, dimensiunea dicționarului este limitată la 4096 cuvinte, ceea ce corespunde la
o reprezentare a indexului (codul cuvintelor șir din dicționar) de 12 biți. Dacă indexul este
reprezentat prin secvențe binare de lungime variabilă, atunci se obține varianta lungime variabilă –
lungime variabilă a algorit mului Lempel-Ziv.
12
Standardul MPEG
Moving Pictures Expert Group (MPEG, ca acronim) este parte a organizației ISO
(Internațional Organization for Standardization) și a dezoltat o serie de standarde audio -video
cunoscute că MPEG -1 (MPEG Phase 1) (IS 11172) și M PEG-2 (MPEG Phase 2)(IS
13818). Acestea sunt primele standarde internaționale în domeniul compresiei audio numerice.
MPEG- 1 acoperă codarea surselor stereo la rate de eșantionare mari asigurând o calitate
transparență, în timp ce MPEG -2 oferă în plus și codarea stereo la rate mici de eșantionare. De
asemenea, MPEG- 2 introducere tehnică de codare mulți -canal cu și fără co mpatibilitate cu
MPEG- 1 pentru a asigura o imagine acustică îmbunătățită numai pentru aplicațiile audio și pentru
sistemele de video –conferințe. MPEG -2 fără compatibilitate anterioară se numește MPEG -2
AAC (Advanced Audio Coding), oferă cea mai mare rată d e compresie.
Aplicațiile tipice ce folosesc standardul MPEG sunt în producția audio, emisiuni radio
digitale, memorare digitală, și alte aplicații multimedia.
OBS: MPEG nu standardizează codoarele sau decod oarele ci doar tipul de informaț ie care
trebuie produs de un codec compatibil MPEG.
Tabel 1 – Familia MPEG
Nr. Tipul Anul Destinatie Trasaturi specifice
1. MPEG-1 1992 Audio/Video Digital Fs = 32 KHz, 44.1 KHz si 48
KHz.
2. MPEG-2 1994 Audio/Video Digital
Televiziune Codare multicanal;
Adauga FS=16 KHz, 22.05 KHz si
24 KHz.
3. MPEG-2-
AAC 1997 Audio multicanal AAC
Fs de la 8 KHz pana la 96 KHz;
Un numar de canale de la 1 la 48.
4. MPEG-4 1999 Multimedia Codare bazata pe obiecte
PNS + LTP + TwinVQ
5. MPEG-7 2001 Se refera la eprezentarea continutului pentru scopuri de cautare
a informatiei in multimedia, filtrare, managemnt si procesare.
AAC = Advanced Audio Coding
PNS = Perceptial Noise Substitution
LTP = Long Term Prediction
TwinVQ = Transform-Domain Weighted INterleave VQ
13
MPEG-1
MPEG-1 este numele primei faze a lucrului MPEG. Lucrul a inceput in 1988 si s- a
incheiat in 1992 prin adoptarea standardului IS 11172. Partea de codare audio (IS 11172-3) este
proiectata sa raspunda la multe aplicatii. MPEG-1 audio consta in trei moduri de operare, numite
straturi/niveluri: nivelul 1, nivelul 2 si nivelul 3. Nivelul 3 are cea mai mare complexitate si a fost
desemnat sa asigure cea mai mare calitate la debite mici de informatie (128 Kb/s pentru un
semnal tipic stereo). Frecvente de esantionare: 32 KHz, 44.1 KHz si 48 KHz.
MPEG-2
MPEG- 2 denota a doua fază a dezvoltarii MPEG, prin introducerea unor concepte noi in
codarea video. Aplicatia de baza este cea a televiziunii digitale. Standardul original MPEG-2 (IS
13818-3) a fost finalizat in 1994 si consta din doua extensii ale lui MPEG-1 audio:
codarea audio multicanal;
se adauga frecvente de esantionare de 16 KHz, 22.05 KHz si 24 KHz.;
cresterea eficientei codarii la debite de informatie mici.
MPEG-2- AAC (Advanced Audio Coding)
AAC este o schema de codare de generatia a doua. Suporta frecvente de esantionare de la
8 KHz pana la 96 KHz si un numar de canale de la 1 la 48.
MPEG-3
Gandit initial pentru codarea video in aplicatii HDTV. Intrucat instrumentele dezvoltate
pentru MPEG-2 au acoperit si aria necesitatilor HDTV, planul de a dezvolta un standard special
MPEG-3 a fost anulat. Cateodata MPEG-nivelul 3 (sau MP3) este gresit referit ca fiind MPEG-3.
MPEG-4
Spre deosebire de primele doua standarde care se refera – in principal – la eficienta
compresiei, MPEG-4 se refera la noi functionalitati: terminal utilizator fixe si mobile, accesul
bazelor de date, cumunicatii si servicii de tip interactiv. MPEG-4 consta dintr-o familie de codare
audio, pornind de la codarea vorbirii cu debite mici (sub 2 Kbit/s) pana la codari de inalte calitate
de 64 Kbit/s pe canal.
14
Furnizează instrumente pentru codarea obiectelor audio, naturale și artificiale. Permite
reprezentarea sunetelor naturale (vorbire și muzică) și sinteză sunetelor bazată pe descrieri
structurate. Reprezentarea sunetului sintetizat poate fi obținută din date de tip text sau din
descrierea instrumentului și prin codarea unor parametri pentru a obține anumite efecte, cum sunt
reverberația și spațialitatea. Reprezentările furnizează compresie și alte facilități, cum sunt
scalabilitatea și redarea în ordine inversă (play -back) la difierite viteze.
MPEG-7
MPEG-7 nu defineste algoritmi. Este un standard de reprezentare a continutului pentru
scopuri de cautare a informatiei in multimedia, filtrare, management si procesare. Furnizeaza:
descrieri standardizate si scheme de descriere a structurilor audio si a continutului sunetului;
un limbaj pentru a specifica astfel de descrieri si scheme de descriere.
Descrierea standardului MPEG-1 Audio
Straturile si modurile de operare. Standardul consta din trei niveluri/straturi, I, II, si III.
(Layer I, II, and III) de complexitate, intarziere si calitate subiectiva crescande. Din pdv al
hardware-ului si software-ului, straturile superioare contin mai multe blocuri. Straturile
superioare conț in blocurile straturi lor inferioare la care se adaugă noi blocuri, așa cum se prezintă
în figura de mai jos. Un decodor audio standard complet ( full) MPEG-1 este capabil sa decodeze
toate cele trei straturi.
Ierarhia straturilor standardului
MPEG-1/Audio. Pentru aceeasi
calitate a perceptiei, creste
raportul de compresie si scade
debitul de informatie.
15
Straturile I si II
Straturile MPEG I și II au structuri similare. Stratul II obține performanțe mai bune,
întrucât informația despre factorii de scalare este redusă prin exploatarea redundanței dintre
factorii de scalare. În plus, cuantizarea se face pe o scară mai fină.
Codorul straturilor I și II codează intrarea digitală audio în 32 de subbenzi cu ajutorul
unor filtre trece bandă egal distantate, așa cum se prezintă în figura de mai jos. Pentru maparea
frecvetelor se folosește o structura de filtru special (polyfazic), fiecare având 512 coeficienți.
Figura 2 – Structura codecului MPEG-1/audio (Straturile I si II)
Structura de baza. Primul pas este conversia semnalului audio in componente spectrale cu
ajutorul unui bank de filtre. Straturile I si II utilizeaza filtrebank de tip sub-banda, iar stratul II
foloseste o structura hibrida. Fiecare componenta spectrala este cuantizata si codata cu scopul de
a mentine zgomotul de cuantizare mai mic decat pragul de mascare. Numarul de biti pentru
fiecare sub-banda si factor de scala este determinat pentru o lungime de tip bloc. Fiecare bloc are
12 (in Stratul I) sau 36 (Straturile II si III) esantioane sub-banda. Numarul de biti de cuantizare
este obtinut cu un algoritm de alocare dinamica controlat de modelul psiho-acustic.
16
Cuvintele de cod pentru sub-benzi, factorul de scala si bitii de alocatie sunt multiplexati
pentru a se obtine o secventa (sir) de biti, impreuna cu un antet (header) si cu o serie de date
optionale (auxiliare)(ancillary). In decodor are loc filtru bank de sinteza reconstruieste blocul de
32 iesiri de esantioane din sirul de biti demultiplexati.
Numarul de nivele de cuantizare pentru fiecare componenta spectrala se obtine dintr-o
regula de alocare dinamica a bitilor controlata de modelul pshiho-acustic. Procedura iterativa
minimizeaza NMR in fiecare subbanda. Se porneste cu numarul de biti zero si cu un factor de
scalare zero. La fiecare pas al iteratiei, circuitul de cuantizare SNR(m), numarul de niveluri e ste
crescut pentru a produce cela mai mare NMR la iesirea cuantizorului. Se folosesc tabele de
corespondenta pentru estimarea SNR(m) functie de m.
Blocul de compandare se utilizeaza in procesul de cuantizare, astfel incat se formeaza
blocuri de esantioane, in care cel mai mare esantion are valoarea 1, acest lucru fiind obtinut cu
ajutorul factorului de scala. In stratul I, se formeaza blocuri de 12 esantioane scalate si decimate
in fiecare subbanda (stanga si dreapta). La frecventa de esantionare de 48 KHz, cele 12
esantionae pentru o subbanda corespund unui interval audio de 8 ms. Intrucat sunt 32 de blocuri,
fiecare cu 12 esantioane, rezulta 32*12=384 esantioane audio. Exista cate un bit pentru fiecare
bloc.
In stratul II, in fiecare sub-banda se foloseste un super-bloc de 36 de esantioane, constituit
din trei blocuri de 12 esantionae decimate. Super-blocul corespunde unui interval audio de 24 ms
la 48 KHz frecventa de esantionare. Exista un bit alocat pentru fiecare super-bloc cu cate 36 d e
esantioane. Cele 32 super-blocuri, fiecare cu 36 esantioane decimate reprezinta – toate impreuna
– 36*36=1152 esantioane audio. Ca si in stratul I, pentru fiecare bloc de 12 esantionae se
calculeaza un factor de scalare. Pentru transmiterea factorilor de scalare se foloseste o tehnica de
eliminare a redundantei, bazata pe marimea schimbarii factorilor de scala, se transmite unul, doi
sau toti trei factori de scala, impreuna cu o informatie de 2 biti pentru selectia coeficientilor de
scalare. In figura 4 se prezinta structura blocului de compandare.
Decodarea: Secventele sub-benzilor sunt reconstruite pe baza blocurilor cu 12 esantioane
considerand factorul de scala decodat si informatia de alocare a bitilor. Daca o sub-banda nu are
biti alocati, esantioanele corespunzatoare acestei sub-benzi sunt considerate zero. La fiecare
calcul a celor 32 sub-benzi se aplica unui fintru bank de sinteza, si se obtin 32 esantioane audio in
format PCM fiecare pe 16 biti. In comunicatiile bidirctionale si in sistemele de inregistrare, filtrul
bank poate fi utilizat in mod invers in procesul de decodare.
17
Descrierea stratului 3 al standardului MPEG audio
Structura de bază este pre zentată in figura 3. Are următoarele trasă turi:
Flexibilitate : In vederea aplicării unei largi palete de aplicații ș i scenarii, MPEG defineste
reprezentari ale datelor incluzand un numar de optiuni.
Mod de operare : MPEG- 1 lucrează pentru semnale mono dar si stereo. O tehnica numita codare
stereo compusa (joint stereo coding) poate fi utilizata pentru a coda mai eficient canalele stanga si
dreapta ale semnalului audio stereofonic. Nivelul 3 permite codarea duala mijloc/stereo si a
intensitatii stereo. Modurile de operare sunt:
un canal;
canal dublu (doua canele independent, de exemplu continand informatie audio in 2 limbi
diferite);
stereo;
stereo compus;
Debitul informatiei (Bit-rate ): Alegerea ratei de bit este lasata, intre anumite limite, la optiunea
celui care implementeaza codorul MPEG audio. Pentru nivelul 3, standardul defineste un
domeniu al debitelor de la 8Kbit/s la 320 Kbit/s. Mai mult, decodorul pentru nivelul 3 trebuie sa
suporte schimbarea tarei de birt de la un cadru la altul.
Codorul : Codarea MPEG audio este lasata complet la latitudinea celui care implementeaza
standardul.
Stratul III este comun pentru MPEG-1 si MPEG-2. Acest strat introduce structuri noi, in
particular un filtru bank comutat. In plus, se face o analiza prin sinteza, un control avansat al pre-
ecourilor, o cuantizare neuniforma si o codare entropica. O tehnica de memorare, denumita „bit
reservoir ” conduce la micsorarea ratei de bit. Este singurul strat care furnizeaza suport pentru
decodarea codarii cu rata de bit variabila.
18
Figura 3 – Structura MPEG-1, stratul III
Filtru bank hibrid comutat : Pentru a obtine o rezolutie in frecventa imbunatatita, aproape de
partitia in benzi critice, cele 32 de semnale su-banda sunt divizate in continuare prin aplicarea
fiecarei sub-benzi, o MDCT in 6 sau 18 puncte, cu 50% suprapunere. Decim fereastra va contine,
12 respectiv 36 esantioane. Numarul maxim de componente din frecventa este 32*18=576,
fiecare reprezentand o banda de 24000/576 = 41.67 Hz. Transformarea bloc in 18 puncte se
aplica pentru a furniza o rezolutie imbunatatita, in timp ce transformarea bloc in 6 puncte ofera o
rezolutie mai buna in domeniul timp. Aceasta din urma se palica in cazul asteptarii unor pre-
ecouri. Depinzand de natura pre-ecourilor asteptate, o parte sau toate transformarile sunt
schimbate.
19
Figura 4 – Structura blocului de compandare
Cuantizare si codare : Esantionale iesirii MDCT sunt esantionate neuniform, furnizand
astfel o eroare-medie patratica mica si o mascare buna. „Rezervorul de biti ” aigura ca bufferul
decodorului nu este niciodata gol sau depajit (under-flowand over-flow) cand se prezinta
secventa de siboluri binare, cu o rata constanta, la intrarea decodorului.
Modelul perceptual fie utilizeaza un analizor (filtru-bank) separat sau combina calculul
valorilor energiilor si filtrul principal. Iesire modelului perceptual consta in valorile pragurilor de
mascare pentru fiecare partitie a codoruluil. In nivelul 3, partitiile codorului sunt echivalente – in
mare – cu benzile critice ale auzului uman.
Daca zgomotul de cuantizare poate fi pastrat sub pragul de mascare pentru fiecare partitie
a codorului, atunci rezultatul compresiei trebuie sa nu difere de semnalul original.Cuantizarea
este neliniara, astfel incat valorile mari sunt codate automat mai putin precis. Valorile cuantizate
sunt codate Huffman. Pentry adaptarea procesului de codare la diferite statistici ale semnalului
audio, tabela Huffman este selectata dintr-o multime cu mai multe optiuni, astfel incat se pot
folosi diferite tabele Huffman pentru parti diferite ale spectrului.
Procesul de cautare al castigului optim si a factorilor de scalare pentru un bloc dat se fac e
uzual prin doua bucle de iterative, ce lucreaza in modul analiza-sinteza:
o bucla interna (bucla pentru rata de bit): Tabela Huffman aloca cuvinte de cod scurte
valorile cuantizate ce apar cel mai des. Daca numarul de biti rezultati din operatia de
codare depaseste numarul de biti disponibili pentru a coda un bloc de date, se poate
corecta prin ajustarea castigului global pentru a determina un pas de cuantizare mai mare,
obtinandu-se un numar mai mic de valori cuantizate. Bucla se numeste rate loop pentru ca
modifica rata globala a codorului pana cand este suficient de mica;
20
o bucla externa (bucla de control a zgomotului): pentru obtinerea unui zgomot de
cuantizare la un prag de mascare, factorii de scala sunt aplicati la fiecare factor de scala al
benzii. Sistemul pleaca cu un factor de scala unitial de 1.0 pentru fiecare banda. Daca
zgomotul de cuantizare intr-o banda data depaseste pragul auditiei (deci, zgomotul
acceptabil) asa cum s-a furnizat de modelul perceptual, factorul de scala pentru aceasta
banda este ajustat pentru reducerea zgomotului de cuantizare. Intrucat obtinerea unui
zgomot de cuantizare mic necesita un numar mare de pasi de cuantizare si – deci – o rata
de bit mare, rata de ajustare a buclei trebuie sa se repete de fiecare data cand se aplica noi
factori de scala. Bucla externa este executata pana cand zgomotul actual (calculat ca
diferenta intre valorile spectrului original si valorile spectrului cuantizate) este mai mic
decat pragul de mascare pentru fiecare factor de scala al unei benzi.
Componentele spectrale sunt cuanizate si codate cu scopul mentinerii zgomotului de cuantizare
sub pragul de mascare.
Descrierea standardului MPEG-2 AAC
AAC urmeaza aceasi structura ca si stratul 3 (analizor de inalta rezolutie, cuantizare
neuniforma, codare Huffman, bucle iterative cu analiza-sinteza) dar adaugao serie de detalii prin
utilizarea unor noi instrumente de codare pentru imbunatatirea calitatii la debite mici de
informatie.
Imbunatatiri pentru cresterea eficientei codarii:
rezolutie in frecventa ridicata: numarul de frecvente in AAC este pana la 1024 in comparatie
cu 576 cat foloseste stratul 3.
Predictie : se imbunatateste predictia in special pentru semnalale ce contine componente
armonice (semnale sinusoidale);
Codare Huffman imbunatatita : codarea liniilor de frecventa prin considerarea grupurilor de
cate 4 linii spectrale, se palica mai des.
21
Figura 5 – Structura MPEG-2 AAC
Imbunătățiri pentru creșterea calităț ii audio:
În locul analizorului de tip banc de filtre hybrid (doua filtre in casacada) se utilizeaza
filtre cu MDCT cu impuls la raspuns de 5.3 ms la 48 KHz, fata de 18.6 ms cat are stratul
III.
Tehnica TNS (temporal Noise Shaping): se caluleaza anvelopa zgomotului in doemniul
frecventelor joase prin folosirea unei predictii in domeniul frecventa. Este importanta la
imbunatatirea calitatii vorbirii la debite mici de informatie.
Prin combinarea acestor tehnici se obtine aceeasi calitate a vorbirii dar la un debit de informatie
cu 70% mai mic decat al startului III.
Structura datelor (Frame) pentru MPEG-1, straturile I si II
In figura 6 se prezinta structura cadru a semnalelor audio MPEG-1, pentru straturile I si II.
Fiecare cadru are un antet; prima parte contine 12 biti pentru sincronizare, 20 biti pentru
informatia despre sistem, si –optional – 16 biti pentru CRC. Partea a doua contine informatii
despre structura, adica despre alocarea bitilor si a factorilor de scalare (si, in Stratul II, informatie
pentru seelctia factorilor de scalare). Ca informatie principala, cadrul transporta in total 32*12
esantioane ale sub-benzilor (corespunzator a 384 esantioane audio de intrare in format PCM –
echivalent la 8 ms la o rata de esantionare de 48 KHz) in stratul I, si un total de 32*36 esantioane
ale subbenzilor in stratul II (corespunzand la 1152 PCM esantioane de intrare, echivalent cu 24
ms la o rata de 47 KHz).
22
De retinut ca toate cadrele sunt autonome, in sensul ca fiecare cadru contine toata
informatia pentru decodificare. Deci fiecare cadru poate fi decodat in mod independent de cadrele
anterioare. Lungimea unui cadru nu este fixata intrucat:
(i) lungimea campului principal de informatie, ce depinde de rata bitilor si de frecventa
de esantionare;
(ii) informatia de structura, care variaza in stratul II;
(iii) campul pentru informatia auxiliara, a carui lungime nu este specificata.
Figura 6 – Structura cadru a semnalelor audio MPEG-1 (S-I si S-II):
Strat I = 384 esantioane sub-banda; Strat II = 1152 esantioane subbanda.
Pachete = 4-octeti pentru antet si 184 octeti pentru campul de date.
Structura datelor pentru MPEG-1, stratul III
MPEG-1 impune folosirea unui antet pentru fiecare cadru (fiecare 24 ms la fs=48 KHz). In
principal contine:
un cuvant de sincronizare: spre deosebire de alte standarde, cuvantul de sincronizare
poate apare si in fluxul de date. De aceea, un circuit de sincronizare trebuie sa verifice
aparitia a mai mult de un cuvant de sincronizare si sa se resincronizeze daca nu gaseste
cuvinte de sincronizare aflate la offsetul corect data de frecventa de esantionare si de
debitul de informatie.
Debitul de informatie: este specificat intotdeauna pentru intreg fluxul de date si nu pe
canal. In cazul stratului III rata de bit se poate schimba determinata de rata de bit folosita
la codare.
Frecventa de esantionare: determina schimbarea frecventei de esantionare;
Stratul: se specifica numarul stratului: I, II sau III si daca este MPEG-1 sau MPEG-2.
Modul de codare: se specifica modul de codare: mono, dual mono, stereo sau stereo
compus.
Protectie la copiere: fiecare antet contine 2 biti pentru SCMS (Serial Copy Management
Scheme) pusa pentru protectia la copiere. Din cauza posibilitatii modificarii acestora pe
cale soft, importanta practica este redusa.
23
Datorită repetiției întregii informații necesară decodării în fiecare cadru, fluxul de date
MPEG-1/2 poate fi decodat începând din orice punct.
Structura datelor pentru MPEG-2 AAC
In timp ce pentru MPEG-1 formatul de baza audio si sintaxa transportului pentru
sincronizare si pentru codarea parametrilor este pastrat impreuna intr-un mod nesaparabil,
MPEG-2 AAC le defineste amandoua dara da libertatea aplicatiei sa aleaga sintaxei transportului.
Standardul defienste doua exemple de trasport a datelor audio:
ADIF (Audio Data Interchange Format) grupeaza toate datele pentru controlul
decodorului (cum este frecventa de esantionare, modul, etc) intr-un singur antet ce
precede fluxul de date audio. Aceasta optiune este utila pentru schimbul de fisiere (se
schima numai antetutul) dar nu permite segmentarea fluxului de date sau inceperea
decodarii in orice punct asa cum permite MPEG-1.
ADTS (Audio Data Trasnport System): impacheteaza datele AAC in cadre cu antete
similare antetului folosit de MPEG-1. AAC este semnalizat/indicat ca stratul IV al
standardului MPEG audio. Spre deosebire de startul III, rata cadrelor este variabila,
continand intotdeauna datele audio pentru un cadru complet intre doua cuvinte de
sincronizare. ADTS permite decodarea din orice punct al fluxului de date.
Concluzii
Prin utilizarea unui codor cu performanțe bune, ambele standarde Startul III și MPEG -2
AAC pot comprimă mesajele audio cu menținerea calității CD. Stratul III are o complexitate mai
mică este cel mai folosit. AAC este considerat succesorul lui MP3 întrucât asigura o o compresie
mai bună.
Inițial „ .mp3 ” a fost creat pentru a descrie stratul 3 al standardului MPEG- 1 în legătură cu
software- ul pentru codorul și decodorul sub windows. După standardizarea lui MPEG -2, fișierele
sunet codate cu MPEG-2 la rate de eșantionare reduse ale stratului III s -au numit tot „mp3”.
Uneori MP3 este greșit numit MPEG -3.
24
Tehnici de îmbunătăĠire a formatului MP3 (VBR, Joint -Stereo)
VBR constituie prescurtarea de la variable bitrate . Pentru a înțelege mecanismul bitrate –
ului variabil trebuie descrisă structura unui fișier MP3. Frame -ul este unitatea indivizibilă,
prezentă în majoritatea formatelor ce stochează date, fie ele de sunet, film sau imagine. Un frame
conține, în cazul formatelor lossy, informațiile cele mai reprezentative din unitatea de timp (în
cazul sunetului) sau de spațiu vizual (pentru imagini). El poate avea dimensiune fixă sau
variabilă, în primul caz tehnica fiind numită CBR (constant bitrate ), în al doilea caz VBR. La
CBR, bitrate- ul este specificat de utilizator la începutul codării și toate frame -urile vor conține
același număr de biți, indiferent de nevoile reale. VBR deține avantajul modelării numărului de
biți în funcție de necesități; dacă algoritmul „ simte ” că sunt necesari mai mulți biți pentru un
frame, va genera un bitrate l ocal mai mare sau mai mic. Cu alte cuvinte, CBR înseamnă bitrate
constant, calitate variabilă, iar VBR înseamnă bitrate variabil, calitate constantă.
Pentru un MP3, există câteva dimensiuni clasice ale frame -ului, indiferent că este aleasă
opțiunea CBR sau VBR, cele mai reprezentative fiind de 96,
112, 128, 160, 192, 224, 256 și 320, și indiferent de nevoile
reale sau de preferința utilizatorului nu poate fi ales un bitrate
intermediar.
Există câteva opțiuni disponibile la codarea MP3 VBR. În
primul rând, poate fi specificat un bitrate minim și unul
maxim; astfel, indiferent de „dorința” algoritmului, nu se va
coborî sub valoarea minimă și nu se va depăși valoarea
maximă. Opțiunea este utilă în caz că anumite pasaje sunt
codate la un bitrate mic, algoritmul putându- se înșela în
privința nevoii de bitrate mic/mare. În al doilea rând, există posibilitatea specificării unui bitrate
mediu dorit ( ABR = average bitrate ). Chiar dacă bucata muzicală nu necesită acel număr de biți,
se încearcă, pe cât posibil, atingerea bitrate- ului specificat, ceea ce duce la o calitate mai scăzută
decât în cazul VBR.
Avantajul principal al lui ABR: se cunoaște de dinainte de codare dimensiunea
(aproximativă) a fișierului rezultat, spre deosebire de VBR, care alocă mai eficient biții da r dă
naștere unui fișier de dimensiune impredictibilă.
25
Joint Stereo (JS) este numele generic atribuit unor tehnici de codare prin care informația
stereo este prelucrată diferit față de metoda clasică (stocarea independentă a celor două canale)
aceasta ori prin îndepărtarea de informație (în locul acesteia, biții rămași liberi fiind folosiți
pentru a stoca informații legate de sunetul propriu -zis), ori printr- o codare alternativă, mai
eficientă. Tehnica se folosește de faptul că, în majoritatea cazurilor, diferențele dintre cele două
canale nu sunt foarte mari. Într- un caz extrem, în care fișierul codat conține două canale
(aproape) identice, aplicându-se modul stereo simplu s- ar risipi inutil mulți biți prețioși.
Metoda clasică de JS este denumită Intensity Stereo (IS), care unește cele două canale în
domeniul frecvențelor înalte, ducând per total la o senzație intermediară dintre sunetul stereo și
mono. Frecvențele înalte sunt mai greu de perceput de către om și de aceea în cazul lor este
neglijată stereofonia. Metoda nu este recomandată decât atunci când această pierdere este mai
convenabilă decât o calitate foarte scăzută a sunetului, cu alte cuvinte în cazul bitrate -urilor mici.
În general, e de preferat chiar și un sunet mono de cât un aliasing sau ringing care practic distruge
sunetul.
Mid/Side Stereo este o altă metodă de tip Joint Stereo (s -a încetățenit această denumire deși
M/S Stereo nu are nici o legătură cu unirea canalelor pe care o anunță cuvântul „ joint”) prin care
encoder- ul transformă coordonatele „ stânga ” și „dreapta ” în unele de tip „mijloc ” și „lateral ”.
Logica este bazată pe matematica de clasa a cincea: dacă notăm stânga cu L (left) și dreapta cu R
(right ), iar L și R au valorile a și b, aceste valori pot fi deduse din relațiile a’ = (L+R)/2 (mijloc)
și b’ = (L-R)/2 (lateral), care devin variabilele principale. Așadar, în loc ca fișierul MP3 să
conțină a-uri și b-uri, va conține a’-uri și b’-uri, informația finală fiind refăcută într -un mod
similar.
În realitate, formula depinde de la encoder la encoder, Lame folosind, spre exemplu, relația
(L+/-R)/sqrt(2) (sqrt = radical). Compresia este realizată ca și cum cele două canale originale ar
fi cel de mijloc și cel lateral. Avantajul constă în faptul că avem de -a face cu o metodă alternativă
de codare, care este selectată de la caz la caz.
Dacă stânga și dreapta sunt identice sau foarte apropiate, canalul lateral va fi zero sau aproape
zero, numărul de biți alocați lui fiind foarte redus. Dacă stânga și dreapta diferă foarte mult, este
mai eficientă folosirea modului stereo simplu, iar acest lucru îl decide encoder -ul pentru fiecare
frame.
26
De reținut faptul că M/S Stereo nu determină creșterea calității sunetului decât în
modurile CBR și ABR, când encoder -ul este limitat la un număr (maxim) de biți. În cazul lui
VBR, folosirea sa doar va scădea dimensiunea fișierului final (bitrate -ul mediu va fi mai mic).
Lame , cel mai bun encoder MP3, lucrează exclusiv cu modurile Mid/Side Stereo și Stereo
„normal ”. Utilizarea lui M/S Stereo este recomandată la orice bitrate pentru că, în cel mai
nefericit caz (imposibil de întâlnit în practică), calitatea M/S Stereo va fi similară modul ui stereo
simplu.
Totuși, prima variantă (IS) – neimplementată în Lame, deși elimină multă informație
stereo, salvează mai mulți biți decât M/S Stereo, folosirea ei fiind destinată bitrate -urilor foarte
mici ( de 96 kbps sau mai puțin). Există și alte tipuri de JS, numite Narrowing of Stereo Image și
Simple Stereo , care elimină aproape complet informația stereo, utilizarea lor nefiind recomandată
decât în situații speciale.
În cealaltă direcție se află modul Dual Channel (nici o legătură cu controller -ele de
memorie). Cea mai simplă explicație rezultă dintr -un exemplu: avem un MP3 stereo (JS sau
Stereo). Pentru canalul din stânga, care conține o informație audio mai simplă, este alocat un
procent de doar 40% din numărul de biți, pentru cel din dreapta rămânând disponibili 60%. Prin
Dual Channel, amb ele canale vor primi exact jumătate din numărul de biți, indiferent de
diferențele de complexitate, rezultând, evident, o calitate mai scăzută decât în cazul stereo
normal. Folosirea acestei opțiuni nu are sens decât dacă cele două canale sunt total diferi te
(canale de sunet ale unui film în limbi diferite).
MPC – un MP3 mai bun
MPC ( Musepack , denumit în trecut MPEG Plus ) este considerat cel mai bun format de
compresie audio lossy (cu pierdere de calitate). Dezvoltat inițial de Andree Buschmann și în
prezent de Frank Klemm pe baza standardului MPEG Layer 2 (MP2), îmbunătățirile aduse
acestuia din urmă îi permit oferirea unei calități deosebite la bitrate -uri de peste 160 kbps.
Dezvantajul principal: calitatea la bitrate- uri mici (adică cele mai folosite, precum 112 sau 128
kbps) este comparabilă cu cea MP3, eventual puțin mai bună, iar când se încearcă detronarea unui
standard ultra-celebru, este nevoie de mai mult. De asemenea, prezența suportului acestui format
pe piața lor mobile este practic nulă, iar compatibilitatea cu software -urile care interacționează în
vreun fel cu sunetul digital este foarte redusă.
27
Chiar dacă encoder -ul nu este un program comercial, dezvoltarea sa stă sub semnul open –
source de puțină vreme, până de curând f iind declarat closed-source (un număr limitat de
programatori avea acces la codul sursă) și acest lucru a îngreunat răspândirea sa.
MusePack lucrează nativ cu tehnica VBR și aceasta fără limitările lui MP3 privind bitrate –
urile disponibile, fiind po sibilă alocarea absolut oricărui număr de biți pentru un frame. Așadar,
nu va fi o problemă obținerea de bitrate -uri per frame diferite de 128, 160, 192, 224 etc. Pentru
definirea calității, există un număr nelimitat de pași, valoarea „ quality ” luând valori între 0 și 10
cu o precizie oricât de mare (de exemplu 5.5 sau 7.1904363). Cu toate acestea, au fost dezvoltate
câteva preset- uri, care oferă o calitate comparabilă cu cea a CD -ului începând cu 5 ( standard ).
Cei mai mulți ascultători au concluzionat că acest nivel de calitate este comparabil cu cel obținut
de MP3 la 320 kbps codat cu Lame, uneori sub dar de cele mai multe ori peste acesta. Avantajul
principal: bitrate-ul mediu este de doar 150- 180 kbps, deci spațiul ocupat va fi de două ori mai
mic i ar calitatea posibil mai mare. Valorile superioare aduc îmbunătățiri, dar în cazul preset -ului
standard de obicei compresia este transparentă și, chiar dacă unele detalii muzicale lipsesc,
ascultătorul nu va realiza aceasta decât în cazuri rare și doar la o comparație cu originalul. L a
MP3, în cazuri rare, ce- i drept, apăreau probleme de transparență chiar și la 320 kbps.
MP3 la 320 oferă de multe ori mai multă claritate în distingerea instrumentelor, MPC q5
având tendința să mascheze anumite aspecte ale muzicii, ceea ce se poate traduce prin diminuarea
în volum a unor sunete uneori nu foarte greu de distins. Acest lucru se întâmplă îndeosebi în
cadrul muzicii bogate în instrumente, cum este cea clasică sau cea rock.
Rar apar probleme de transparență la MPC, în nici un caz nu vom fi întâmpinați de
percuția udă a lui MP3, dar sunete care ar trebui să se audă s -ar putea să lipsească, ceea ce va da
naștere unui „ aliasing virtual ” dacă îl putem numi așa, o inconstanță aproape imperceptibilă a
volumului și clarității instrumentelor pe parcursul piesei muzicale, în nici un caz la fel de
supărătoare ca în situația aliasing -ului clasic, prezent, poate , chiar și la MP3 320 kbps.
Nivelul de calitate 6 ( xtreme , 180- 220 kbps) oferă îmbunătățiri minore dar care reprezintă
exact plusul care îi lipsea setării standard, iar de la nivelul 7 în sus ( insane , 220-250 kbps) putem
spune că am atins o calitate aproape de perfecțiunea teoretică, mai ales că este pă strat aproape
întreg spectrul de frecvențe. Peste acest preset sunt șanse foarte mici să mai apară salturi major e
pentru utilizatorul normal, deci dacă ați întâlnit ceva care nu sună bine cu preset -ul insane, mai
mult ca sigur că acel ceva nu va suna mult mai bine la bitrate -uri superioare.
28
Totuși, sunt pre zente valorile 8 ( braindead , 250-280 kbps), 9 ( above braindead , 270-310)
și 10 ( above braindead , 300- 335 kbps) precum și cele intermediare, desigur. De asemenea,
trebuie precizat că MusePack folosește metoda Mid/Side Stereo pentru a nu irosi inutil biți pe ntru
informația stereo (o implementare chiar mai reușită decât în cazul MP3). Un motiv în plus pentru
a nu fi recomandat la bitrate- uri mici, unde alte metode de Joint Stereo, mai agresive, oferă mai
multe avantaje.
Bitrate- urile indicate pentru că ele sunt orientative. Un sunet prea simplu va determina
encoder- ul să aloce mai puțini biți, deci în loc de cei 170 kbps așteptați pentru preset -ul standard
se poate obține o medie de 130, 110 sau chiar mai puțin. Pentru a da exemple de cazuri extreme,
un ton perfect la 440 Hz este codat la 77 kbps iar liniștea completă la 3 kbps. De asemenea, o
piesă (aproape) mono va solicita un bitrate (aproape) de două ori mai mic decât pentru una full –
stereo.
Este cazul înregistrărilor mai vechi, care chiar dacă sunt stereo din punct de vedere
teoretic, ele conțin două piste (aproape) identice. Mai frecvent se întâmplă invers: sunet prea
complex, bitrate mult crescut. Complexitatea poate rezulta și din cauza clipping -ului (volum mai
mare decât poate fi reprezentat digi tal în coordonatele alese), fenomen care perturbă curba
obișnuită a sinusoidei ce formează unda sonoră, punând encoder -ul într- o situație foarte dificilă.
Au fost întâlnite cazuri în care calitatea standard a oferit un bitrate mediu de 250 kbps pe
parcursul unei întregi melodii.
În cazul oricărui encoder, preset -urile nu sunt altceva decât extensii logaritmice ale
aceluiași model psihoacustic adica dacă algoritmul are probleme cu o anumită secvență de
muzică la o setare de calitate considerată sigură (cum e q5 pentru MusePack), o creștere de bitrate
(q6, q7 etc) nu va elimina acea problemă ci doar o va diminua, cauza fiind modelul psihoacustic
imperfect, iar această diminuare se va simți din ce în ce mai puțin odată cu creșterea dimensiun ii
fișierului; dacă q6 va suna mult mai bine decât q5, q7 va suna cu puțin mai bine decât q6, q8 cu
foarte puțin mai bine decât q7 etc. Modelul psihoacustic poate fi ajustat ori prin specificarea către
encoder a unor parametri speciali (nerecomandat decât pentru utiliza torii care știu exact ce fac),
ori prin apariția unei noi versiuni a encoder -ului, acele setări fiind deja realizate de autori. Sau,
cum e cazul lui MP3, orice îmbunătățire majoră a modelului presupune încălcarea standardelor și
imposibilitatea decodării fișierului rezultat.
29
Encoder- ul MusePack va funcționa cu comanda MPPENC {opțiuni} fișier_input.wav
fișier_output.mpc , unde opțiunile sunt –quality –xlevel . Așadar, pentru preset -ul insane veți
folosi –quality 7 –xlevel . Ultimul parametru se referă la o tehnică alternativă de tratare a
eșantioanelor asupra cărora a intervenit fenomenul de clipping și cum nu prezintă decât avantaje
(nu crește timpul de codare sau fișierul rezultat), merită folosit.
De asemenea, param etrul opțional –ms 15 va feri ascultătorul de apariția artefactelor în
cazul audiției pe sisteme cu 4 -6 surse sonore. Este vorba de un Mid/Side Stereo mai riguros, care
ține seama și de această situație, fiind adăugat în general circa 1 kbps la bitrate -ul final.
Pentru a putea fi decodate, fișierele MPC au nevoie de un decoder, care constă, în cazul
cel mai uzual, într-un plugin destinat player-ului Winamp. Versiunea curentă a standardului este
SV7, fiind așteptată cea SV8, care promite mult, mai ales pe partea suportului multi -channel, a
unor frecvențe de sampling diferite de cele actuale, deschizând totodată și calea compatibilității
cu player-ele portabile.
Însă apariția acestei versiuni este nesigură, de circa trei ani progresul realizat este extrem
de redus datorită numărului mic de persoane implicate, pentru care acest proiect nu reprezintă
mai mult decât un hobby. Surprinzător, complexitatea algoritmului MPC este redusă și aceasta se
traduce prin timpi mici de compresie și decompresie, necesarul hardware pentru decodare fiind
mai redus decât în cazul MP3.
Iată un avantaj în cazul în care vor exista playere portabile care să adopte acest standa rd.
Concluzionând, MusePack este un encoder extrem de capabil, oferind la ora actuală cea mai
bună calitate pentru un format lossy la bitrate -uri de peste 160 kbps. Viitorul nesigur, slaba
popularitate și alte mici probleme împiedică acest format să pretindă primul loc ca răspândire, loc
deținut deocamdată de MP3. Însă cine dorește calitate maximă, are o singură soluție.
Vorbis – o alternativă interesantă
Atât MP3 cât și MPC sunt concepute pentru bitrate -uri mari, la valori mici ale acestuia (sub
128 kb ps) oferind o calitate foarte slabă. Vorbis pornește de la baza unui algoritm diferit: în loc
să elimine complet frecvențele înalte sau să le păstreze dar să permită apariția artefactelor, el
generează un gen de zgomot de fond, deloc supărător, care păcălește urechea umană, frec vențele
înalte fiind denaturate în așa fel încât chiar și la un bitrate de 50 kbps calitatea audio este
acceptabilă, iar în același timp înaltele sunt redate decent.
30
Dezavantajul principal: Vorbis nu este capabil să ofere o calitate foarte bună la bitrate -uri
mari, în această situație fiind depășit de MPC și, uneori, chiar și de MP3.
Vorbis este un format absolut gratuit, encoder- ul nefiind restricționat în nici un fel. Sursele
programului sunt disponibile, iar encoder-ul este de tip open-source. Rezultatul: o parte din
player- ele portabile au adoptat acest standard iar numeroși producători de jocuri folosesc Vorbis
pentru sunetele și muzica incluse. Desigur, audiofilii vor strâmba din nas nemulțumiți: cine
dorește calitate de CD va trebui să se îndrepte către alte formate.
Însă pentru bitrate -uri mici, alături de AAC și poate WMA, Vorbis reprezintă soluția
ideală, un astfel de fișier la sub 100 kbps fiind net superior oricărui MP3 sau MPC. Este gre u să
comparăm Vorbis cu alte formate pentru că el scade calitatea în alt mod decât o fac MP3 și MPC.
Apare și aici neclaritatea și metalizarea sunetelor, dar într -un mod mai puțin deranjant. Forțând
puțin limbajul, spunem că Vorbis este „ mai transparent ” la bitrate-uri mici, unul dintre
fenomenele nefirești dar deloc supărătoare pentru un ascultător amator fiind scăderea în
intensitate a volumului anumitor instrumente, voci sau detalii ale muzicii. Calitatea minimă care
poate fi specificată encoder -ului est e -1, aici obținându -se un bitrate mediu de circa 40-50 kbps.
Suficient pentru a înțelege despre ce e vorba în muzică dar insuficient chiar și pentru un
ascultător mediu.
Trebuie însă menționat faptul că atât MP3 cât și MPC se comportă extrem de slab în
aceste condiții. Această setare este potrivită în momentul în care doriți să trimiteți o bucată
muzicală unui prieten pentru o primă impresie, dat fiind că o melodie medie, de 4 minute, ocupă
doar circa 1,5 MB. Vorbis se bazează pe tehnica VBR, oferind în acest mod calitatea maximă.
Există disponibil și modul CBR, dar utili zarea sa nu prea are sens. O calitate decentă, minimă
pentru player-ele portabile, este cea de 1.5, în acest caz obținându -se circa 80-90 kbps, iar
calitatea va fi comparabilă cu cea obținută de mp3Pro și AAC la bitrate -uri similare. Preset-ul
standard este 5 (apelabil prin comanda oggenc2 – q 5 fișier_input.wav fișier output.ogg ), ce oferă
transparență în practic toate cazurile, nu și perfecțiune. Spunem aceasta pentru că anumite detalii
ale sunetului se vor pierde; totuși, calitatea va fi superioară lui MP3 la același bitrate (circa 150 –
170 kbps) și comparabilă cu cea a lui MusePack. Se vor simți îmbunătățiri odată cu creșterea
bitrate-ului, cel maxim, specificat de preset-ul 10, fiind de 400- 600 kbps, la această dimensiune
fiind de preferat formatele lossless, eventual MPC q10: calitate cel puțin egală, spațiu ocupat mai
mic. În plus, numărul pieselor muzicale „ imperfecte ” la această setare este mai mare decât în
cazul lui MPC.
31
Există și o versiune optimizată pentru procesoarele Pentium 4, dar cu toate acestea codarea se
desfășoară mai lent decât pentru MPC dar mai rapid decât MP3 Lame, algoritmul – atât în
privința codării cât și decodării – fiind foarte complex. Unele playere portabile portabile nu
suportă fișiere Vorbis la bitrate mic deoarece resursele ocupate de aceste fișiere sunt foarte mari.
Un ultim aspect care merită discutat este așa -numitul bitrate peeling , care reprezintă scăderea
bitrate- ului unui fișier comprimat lossy fără decompresie și recompresie. Astfel, nu se pierde
decât strict calitatea datorată scăderii bitrate -ului, nu și datorită recompresiei. Formatul Vorbis
suportă această funcție dar encoder -ele uzuale nu au implementat-o.
OGG este extensia pentru formatul multimedia, ce include de cele mai multe ori sunet în
format Vorbis. El reprezintă un container , similar lui AVI sau MP4. Este, așadar, greșită referirea
la Vorbis prin OGG, deși între termeni există o relație strânsă.
Overview pentru standardul MP3
La bitrate- uri ridicate standardele MPEG Layer 1 și Layer 2 oferă o calitate mai ridicată decât
MP3 datorită algoritmului mai simplu. Probabilistic vorbind, cu cât procesarea sunetului este mai
complexă, cu atât șansele de apariție a unui artefact sonor cresc. MP3 a fost conceput pentru
bitrate-uri de 112- 192 kbps, spre deosebire de MP2 și MP1 care necesită mai mulți biți pentru a li
se evidenția valoarea. Gurile rele spun că MP3 „arată” astfel din motive comerciale și din dorința
de a se păstra o relativă compatibilitate cu standardele anterioare (fapt absolut inutil pentru că nici
un player care cunoaște formatul MP2 nu va putea decoda un MP3, deși o parte din algoritm este
similară), putând fi observate numeroase decizii greși te luate la formarea standardului. MP3
moștenește o parte din elementele care stau la baza lui MP1 și MP2, peste care suprapune un
algoritm nou – combinație care determină un comportament slab în anumite situații.
Tehnic vorbind, MP3 este o combinație dintre doi algoritmi: subband și transform . În cazul
unui codec de tip subband, informația audio este separată în funcție de frecvențe, segmentele
fiind procesate independent, folosindu- se o acuratețe variabilă, potrivită modului de percepție al
urechii. Pentru reținerea unui sunet de calitate este însă necesar un bitrate mare.
Pentru un codec de tip transform, sunetul suferă o transformare cosinus ( MDCT = Modified
Discrete Cosine Transform ). Această combinație mai mult sau mai puțin fericită duce la
inferioritatea lui MP3 în fața multor alte formate subband, precum MP1 și MP2, dar numai la
32
bitrate- uri mari, adică exact în situațiile în care urechea umană nu (prea) mai face diferența. MP3
moștenește de la ambii algoritmi punctele slabe: calitatea slabă la bitrate-uri foarte mici, sub 128
kbps – de la subband, și imposibilitatea atingerii unei calități foarte bune la bitrate -uri mari – de la
transform (materializată în problema pre-echo ). El nu este altceva decât un compromis de calitate
creat pentru nec esitățile anilor ’ 90.
Am amintit anterior de cei doi algoritmi, transform și subband, care stau la baza tuturor
formatelor performante de compresie a sunetului. Diferența dintre cele două la nivel practic
constă în faptul că ele sunt puse în dificultate în situații diferite: codarea evenimentelor bruște
pentru cele transform și codarea frecvențelor înalte pentru cele subband.
Algoritmul subband este de fapt o reprezentare a sunetului pe axa timpului, toate informațiile
reținute fiind legate de frecvențe. Astfel, cu cât sunt alocați mai mulți biți, cu atât este acoperit un
domeniu mai larg de frecvențe, primele deteriorate în caz că numărul biților nu e suficient fiind
înaltele. Tăierea acestora nu este efectul compresiei ci o măsură de precauție pentru ca sunetul să
rămână decent. Pentru redarea lor cât mai fidelă, de la un anumit prag în sus este necesară forța
brută care, după cum se știe, este similară „ cooperativei munca în zadar ”: efort mare, eficiență
minimă. De aceea un MPC q10 va suna doar cu puțin mai bine decât unul q5, orice preset peste 5
putând fi considerat, pe bună dreptate, un „ brute-force ” pentru ca frecvențele (îndeosebi cele
înalte) să fie reținute cât mai corect.
Teoretic, indiferent de bitrate, un encoder subband nu va putea cod a corect frecvențele
înalte. Algoritmul transform este o reprezentare a sunetului în domeniul frecvențelor. Sunetul este
împărțit în benzi de frecvență, fiecare dintre ele fiind codată separat. De aceea, nici o frecvență nu
va fi neglijată, astfel explicân du-se faptul că formatele de tipul lui Vorbis nu suferă alterări
majore ale înaltelor la bitrate-uri foarte mici. Reversul medaliei este incapacitatea acestui
algoritm de a reprezenta corect sunetul la o rezoluție temporală mare. De aceea, impulsurile,
sunetele de scurtă durată, nu pot fi codate bine, pentru aceasta fiind necesară forța brută –
cunoscuta problemă pre-echo . Atât după cât mai ales înaintea unui sunet brusc (atac) apar
frecvențe parazite, traduse prin senzația de „ ud”. În imaginile de mai jos se poate vedea unda
sonoră în cazul compresiei MP3 comparativ cu originalul (encoder -ul folosit a fost Blade, cel mai
slab calitativ, pentru a evidenția fenomenul – dar el persistă deși este mult redus în cazul oricărui
encoder/bitrate).
33
fără pre-echo pre-echo
În al doilea caz, înainte de atac volumul crește, o serie de eșantioane apărând „ din senin ”
și deteriorând sunetul. Teoretic, nici un encoder de tip tran sform nu va elimina complet problema,
indiferent de bitrate. După cum mentionam , MP3 este compus din ambii algoritmi, suferind de
pe urma deficienței fiecăruia. De aceea, sub aspect pur teoretic, MPEG Layer 3 poate fi
considerat cel mai slab codec modern de compresie.
Desigur, teoria nu corespunde mereu practicii și MP3 -ul depășește multe codec -uri slab
optimizate, cum ar fi MPEG Layer 1 și 2 la bitrate -uri mici și medii, ocazional MPC la bitrate -uri
foarte mici. Optimizarea algoritmului joacă un rol esențial în calitatea și performanțele unui
encoder dar este clar că algoritmul subband este mai simplu iar codec -ul mai ușor de programat,
totodată necesarul resurselor hardware de codare/decodare fiind mai redus. O consecință indirectă
a acestui lucru es te faptul că performanțe foarte aproape de maxim sunt obținute rapid. De
exemplu, formatul MusePack nu mai poate fi îmbunătățit substanțial deși este încă tânăr, pe când
MP3 a necesitat multă muncă pentru a fi adus la acest stadiu iar potențialul lui Vorbis este încă
neexploatat.
Codarea MP3 suferă de încă o limitare, descrisă în cele ce urmează. Algoritmul subband
(implementat și în MP3) constă în împărțirea sunetului în benzi de frecvență și codarea lor
independentă, ele fiind scalate în funcție d e un factor (de aceea ele sunt numite scalefactor
bands ), care acționează ca o compresie locală a benzii respective. Problema este că ultima bandă
(sfb21 ), cea răspunzătoare de frecvențele de peste 16 KHz, nu deține acest factor de scalare din
cauza unei g reșeli de proiectare. Consecința: pentru a reține informații precise despre acest
domeniu de frecvențe trebuie irosiți foarte mulți biți, nu neapărat pentru că aceste frecvențe ar
necesita mai mulți decât celelalte ci pentru că, pentru a crește rezoluția codării suficient de mult
cât să poată fi reținute aceste frecvențe, trebuie crescută rezoluția tuturor benzilor. Altfel spus,
dacă dorim frecvențe de peste 16 KHz va trebui să irosim o grămadă de biți pentru toate
34
frecvențele, inclusiv pentru cele joase. Efectul se vede imediat: la tăierea frecvențelor peste
pragul sus-amintit, în cazul modului VBR bitrate-ul se reduce semnificativ, cu circa 25%. De
asemenea, parametrul -Y indicat lui Lame ( „lets LAME ignore noise shaping in sfb21, like in
CBR ”) va determin a o alocare mai eficientă a biților, conducând la scăderea semnificativă a
bitrate- ului cu prețul eliminării celei mai mari cantități din frecvențele înalte.
Un alt aspect este legat de așa -numitul rezervor. Majoritatea formatelor care permit tehnica
VBR (probabil toate, exceptând MPEG Layer 1, 2 și 3) dețin posibilitatea ca fiecare frame să fie
reținut pe un număr variabil de biți, atât cât este nevoie. Formatele MPEG (excludem MusePack,
desigur) dețin valori prestabilite pentru fiecare frame (128, 160, 224 etc), dovadă clară că ele nu
au fost concepute cu gândul la VBR, idee ce a apărut mai târziu.
Pentru a compensa acest neajuns și depășind puțin specificațiile formatului MP3 (fără a
elimina compatibilitatea cu decoder- ele) a fost concepută idee a de rezervor ( reservoir ).
Practic, este vorba de un mod VBR primitiv, bazat pe faptul că de multe ori bitrate -ul
constant dorit nu poate fi „umplut ” perfect, apărând spații libere ce pot fi folosite în cadrul altor
frame-uri. Encoder- ul însumează în acest rezervor un număr de biți de rezervă pe care îi va folosi
mai târziu, acolo unde este nevoie. Astfel, dispare și limitarea valorilor discrete ale bitrate -ului
dar dezavantajul major este faptul că acest rezervor nu poate fi creat din nimic, frame -ul curent
nu poate „lua cu împrumut ” biți ci este necesară o rezervă care poate sau nu să existe la
momentul solicitat. În plus, dimensiunea rezervorului este limitată, ea scăzând odată cu creșterea
bitrate-ului nominal.
Acțiunea este realizată transparent și este aplicată atât în cazul fișierelor VBR, cât mai
ales a celor CBR. Pe de altă parte, modul ABR ( Average BitRate ) nu este decât un simplu mod
CBR unde mărimea rezervorului este nelimitată. Un rol important pentru salvarea unor biți
importanți în cadrul com presiei audio le au câteva trucuri descrise în continuare.
Perceptual Noise Substitution (PNS) se bazează pe observația că urechea umană nu deosebește
prea mult un zgomot de altul. Astfel, encoder- ul cunoaște cum „arată” acest zgomot și inserează
în fișierul comprimat doar câteva detalii ale acestuia, restul fiind dedus printr -un algoritm. Cu alte
cuvinte, când avem de- a face cu un zgomot sunt utilizați mai puțini biți pentru reținerea acestuia,
acea zonă a fișierului audio fiind tratată separat. PNS e ste implementat, printre altele, în
MusePack și AAC, dar numai la bitrate -uri mici.
Spectral Band Replication (SBR) este altă metodă de creștere a calității, despre care se va
discuta pe larg în paragraful dedicat lui mp3Pro. Ea are reconstruiește cu aproximație frecvențele
35
înalte în funcție de doar câteva informații. De asemenea, sunetele tonale sunt tratate special de
către unele encodere, algoritmul de compresie fiind gata să salveze biți importanți atunci când
întâlnește secvențe repetitive. Prin sunete tonale înțelegem sunetele susținute, prezente atât în
cadrul instrumentelor cât și în cadrul vocii umane. Puteți observa în imaginile următoare
reprezentarea sunetului de nai, a unei voci feminine care pronunță litera „ A”, unde asemănarea
este eviden tă, o anumită secvență fiind repetitivă. Prin contrast, sunetul emis de o tobă nu are nici
o regulă de repetiție. Tehnica prin care sunetele tonale sunt tratate separat se numește Clear
Vocal Detection (CVD ) și este implementată în MusePack.
nai litera „A” tobă
Temporal Noise Shaping (TNS) este o metodă de a elimina pre -echo-ul întâlnit la codec-
urile de tip transfform. Ea constă în aplicarea unui filtru înainte de codarea efectivă pentru a
minimaliza efectul trecerii bruște între două sunete diferite. Decoder -ul cunoaște parametrii
filtrării și decodează sunetul corespunzător.
CODURI UTILIZATE PENTRU SEMNALUL VOCAL
CODUL CU PR EDICğIE LINIARĂ (CELP)
În tehnica GSM se cere o calitate înaltă a semnalului vocal la viteze mai mici de 8kb/s. De
cînd a fost finalizată recomandarea asupra codării semnalului vocal în GSM, s -au efectuat
cercetări intense pentru a înjumătăți rata de codare la 6,5 kb/2. Codurile RPE și MPE discutate
anterior pot fi folosite pentru a da o bună calitate a semnalului vocal la viteze de pînă la 9,5 kb/s.
Când viteza este mai mică de 9,5 kb/s MPE și RPE nu mai pot păstra calitatea bună a
semnalului vocal. Aceasta deoarece este necesar un număr foarte mare de biți pentru codarea
semnalului vocal excitator, iar calitatea este deteriorată cînd aceste impulsuri sînt cuantizate rău
sau cînd numărul lor este redus pentru a reduce viteza. De altfel, dacă se folosesc structuri de
analiză prin sinteză pentru a obține o calitate bună la viteze mai mici de 8 kb/s trebuie să folosim
mai multe aproximări pentru a putea def ini semnlul excitator.
36
Impelmentarea predictorului pe termen lung în bucla de analiză prin sinteză devine de
importanță majoră pentru a muta cît de mult se poate redundanța semnalului vocal. Semnalul
rezidual după predictorul pe termen lung și scurt devine zgomotos și asta presupune că reziduul
poate fi modelat prin procesul Gauss cu o variație lentă a spectrului de putere. Aceta este punctul
cheie în implementarea codurilor stocastice, unde funcția excitatoare este un vector de cuantizare
care folosește un tabel de coduri stocastice.
Codarea stocastică sau codarea cu predicție liniară a fost introdusă în 1984 de Atal și
Schroeder. O aproximare similară a fost propusă de Copperi și Seveno în 1985.
În aproximarea CELP o fereastră de 5 ms (40 de eșantioane) se modelează cu un ve ctor
Gauss alegînd un tabel de cod Gauss mare prin minimizarea lungimii erorilor dintre semnalul
original și cel refăcut. Deobicei, un tabel are 1024 de intrări și se alege secvența optimă prin
căutări exhaustive în tabelul de coduri. Folosind aproximarea CELP, ofereastră de 5..7,5 ms se
poate coda cu numai 15 biți (din care 10 biți pentru adresă și 5 biți pentru cîștig). Aceasta ne arată
o reducere a vitezei în comparație cu codarea RPE – LTP unde se folosesc 47 de biți pentru a
coda același semnal excitator.
Pînă în prezent, complexitatea deosebită a algoritmului CELP a împidicat implementarea
sa în timpi reali. Complexitatea provine de la căutarea exhaustivă în tabelul de cod, unde pentru a
sintetiza un semnal vocal foarte lung trebuie să calculăm toate intrările posibile și apoi trebuie
comparate cu lungimea semnalului original. În ultimii ani, activitatea de cercetare a fost
concentrată pe reducerea complexității codorului CELP și s -a realizat implementarea sa în timp
real folosind tehnica DSP.
S-a realizat o simplificare a codorului CELP folosind tabelele de codare în care
majoritatea eșantioanelor excitației în vectorul aleator Gauss sînt 0. O altă siplificare
semnificativă în structura tabelului de codare este aceea de a fol osi tabelul de coduri ternare, unde
elementele vectorului de excitare sînt -1, 0 sau 1.
S-au folosit coduri ternare și coduri de împrăștiere pentru a reduce complexitatea
calculelor și capacitatea necesară de stocare a sistemului CELP. Codurile binare sînt de fapt
coduri ternare unde impulsurile de excitare sînt spațiate regulat. Această structură permite
utilizarea unor proceduri de căutare ne -exhaustive.
O altă cale eficientă de a defini semnalul de excitație este aceea de a utiliza vectorul sumă
de exci tație (VSELP). Aici, vectorul de excitație este o combinație liniară a vectorului de bază
format cu – 1 și 1. Această structură specială duce la o reducere semnificativă a calculelor
necesare pentru a identifica vectorul de excitație optim. A fost ales un n ou cod VSELP de 8 kb/s
pentru implementare în sistemul de comunicații mobile digitale american.
Codurile algebrice au fost utilizate pentru a reduce complexitatea CELP-ului, unde tabelul
de cod se generează folosind coduri binare de corecție a erorilor. O altă simplificare a fost
propusă: sistemul CELP operează în banda de bază a semnalului rezidual LPC. Structura acestui
codor este similară cu aceea a codului RPE – GSM. Reducerea vitezei se realizează prin
cuantizarea vectorială a reziduurilor cu coduri C ELP.
37
Conceptul de autoexcitare s- a utilizat pentru a obține o calitate bună a semnalului vocal la
vitez mici de 6,4 kb/s. În această aproximare, excitația se obține prin căutări printre semnale le
anterioare și se alege acel semnal care minimzează lungimea erorii dintre semnalul original și cel
sintetizat. Autoexcitația LPC poate fi văzută ca o altă variantă a CELP -ului în care tabelul de
coduri se schimbă și are avantajul că necesită un număr mai mic de calcule și de asemeni un
volum mai mic pentru capaci tatea de stocare. Dezavantajul algoritmului este acela că algoritmul
nu mai este la fel de robust atunci cînd transmisiunile sînt afectate de zgomote.
În acest capitol vom descrie codul CELP și aproximările folosite pentru a genera tabelul
de coduri de ex citație.
PRINCIPIUL CELP
După predicția pe termen scurt/lung a semnalului vocal, redundanțele în semnalul vocal
sînt aproape eliminate și semnalul rezidual este foarte puțin corelat. Se poate folosi procedeul
Gauss alb pe perioade care variză liniar în timp (la predicția pe termen lung/scurt). Se alege
secvența optimă din tabelul de cod prin minimizarea erorii dintre semnalul original și cel
sintetizat.
Fig. 7 Digrama bloc pentru sistemul CELP
Filtrul cu corelație de înălțime este înlocuit de un tabel de coduri. Adresa selectată din
tabelul de cod adaptiv și cîștigul corespunzător însoțit de adresa selectată din tabelul de cod
stocastic și cîștigul corespunzător sînt trimise codorului.
Filtru de
sinteză
Cadru de
întîrziere
+
G1
G2
cod
adapativ
cod
stocastic
u(n)
semnal vocal
sintetizat
38
Acesta folosește același tabel de cod în absența erorilor de pe canal pentru a determina
semnalul excitator de la intrarea filtrului sintetizat LPC pentru a produce semnalul vocal
sintetizat.
Tabelul de cod excitator conține L cuvinte de cod (vectori stocastici) de lungime N
eșantioane (tipic L = 1024 și N = 40 pentru o fereastră de 5 ms). Semnalul de excitație de
lungime N este ales prin căutări exhaustive în tabelul de cod după ce s -au scalat vectorii Gauss în
ordinea factorului de cîștig .
Numărul de instrucțiuni necesare pentru a evalua expresia:
KK K k k C T 2
este N2. Pentru un tabel cu 1024 intrări și o fereastră de 40 de eșantioane pentru a căuta
cuvîntul de cod sînt necesare 4000 multiplicări ale eșantioanelor semnalului vocal. Cînd se
calculează convoluția prin filtrare recursivă, cuvintele de cod c k(n) sînt filtrate cu filtrul cu
zerouri 1/A(z/ ), unde convoluția necesită N p instrucțiuni, energia calculată în k necesită N
instrucțiuni, evaloarea intercorelației c k necesită N instrucțiuni. Se obțin în total N (p+2) operații.
Un cod cu 1024 intrări și un predicator de ordin 10 pentru căutarea în tabel a cuvîntului de cod
sînt necesare 12000 multiplicări ale eșantioanelor vocale.
Deci o căutare exhaustivă în tabelul cuvintelor de cod este o procedură care cere multe
calcule și este dificil de implementat în timp r eal.
Vom studia cîteva metode pentru a simplifica procedura de căutare în tabelul cuvintelor
de cod fără a afecta calitatea semnalului vocal de la ieșire.
SIMPLIFICĂRILE PROCEDURII DE CĂUTARE CELP FOLOSIND APROXIMAREA
AUTOCORELATIVĂ
S-au folosit diferite aproximări pentru a simplifica procedura de căutare în tabelul
cuvintelot de cod. În domeniul frecvenței, convoluția c k(n)*h(n) din ecuația
1
021
021
0 2
) ( ) () ( ) ( ) (
) (N
nN
nkN
nk
nhncnhncn x
nx E
39
de transformă în multiplicare C(i)H(i), unde C(i) este vector Gaussian și H(i) se reduce la
transformata Fourie (DFT) al funcției de răspuns la implus. Pe această cale se micșorează
numărul de operații, dar trebuie să calculăm DFT pentru h(n) și x(n).
O metodă propune descompunerea valorii singulare. Prin aceasta se reduce matricea H
care apare în ecuația 158 la o formă diagonală exprimată prin H = UDVT, unde D este matrice
diagonală, iar U și V sînt matrici diagonale. Se pot folosi proprietățile matricii ortogonale pentru
a reduce eroarea medie pătratică (din ecuația 158) la o formă care necesită doar 4N înmulțiri
pentru a evalua termenii care trebuie minimizați. Astfel se micșorează numărul de înmulțiri
necesare pentru a căuta în tabelul de cod de 1024 intrări la 4000înmulțiri/eșantion. Metoda
necesită o încărcare suplimentară pentru calcularea TDF pentru matricea H, pentru fiecare set de
parametri ai filtrului, ceea ce este echivalent cu N3 operații și pentru valoarea N = 40, se introduc
mai mult de 1600 operații/eșantion, care nu pot fi neglijate.
O altă metodă pentru a simplifica procesul de căutare utilizează metoda autocorelației. În
această aproximare, matricea covarianțelor = HTH se reduce la o formă Toeplitz prin
moduficarea limitelor de sumar e în ecuația
kT T
kkT
T
HcHcHcxxxE2
0
astfel încît
) ( ) ( ,1
N
j i njinhnh ji j i
Aproximarea autocorelativă rezultă din modificarea matricii de covarianțe N x N într -o
matrice de forme (2N – 1) x N.
10 10 2 10 3 2 10 1 20 10
… 0 0 0… … … … …… 0 0… 0…… … … … …0 …0 … 00 … 0 0
NNN NN N N
hh hh h hh h h hh h hh hh
H
40
Convoluția H ck folosind această matrice se transformă într -un vector de lungime 2N – 1,
obținut prin convoluția a două segmente de lungime N. De observat că în aproximarea
covarianțelor se luau în considerare numai primele N eșantioane și oricare eșantion din afara
cadrului acesta nu se lua în considerare. Cum răspunsul la impuls h(n) este o funcție
descrescătoare, se poate trunchia la R – 1 N (R = 25) fără a introduce erori perceptibile. În
acest caz, dimensiunea matricii din ecuația 161 devine (2R – 1) x N, iar matricea de autocorelație
(i) = 0 pentru i R. De aici înainte, vom presupune că răspunsul la impuls a fost trunchiat la R –
1.
Evaluarea energiei necesită R instrucțiuni și T k (din ecuația 167) necesită N + R + 3
instrucțiuni.
Fig. 8 : Metoda de căutare a secvenței optime CELP folosind aproximația autocorelativă
Fig. 8 arată reorganizarea optimă a procesului de căutare folosind funcția de autocorelație.
Pentru N = 40 și R = 25 este necesar un număr mai mic de 200 de înmulțiri/eșantionul de vorbire
sintetizat, cînd se folosește un cod cu 1024 intrări. Autocorelația cuvîntului de cod k(i) se
calculează înainte și sînt memorate în alt tabel. Aproximarea cu autocorelație are dezavantajul că
necesită un al doilea tabel la codare pentru a memora auotcorelația tabelului excitator.
selecția
vîrfului
Corelație
0…..N – 1
:
cod
de
excitație
cod
de
corelație
Corelație
-(N – 1)…..N – 1
Φ(n)
Ψ(n)
41
PERFORMANğELE CELP
Codorul CELP a fost evaluat la o viteză de 4,8 kb/s pînă la 8 kb/s. Calitatea semnalului
vocal la 4,8 kb/s este aproximativ aceeași cu aceea de la 8 kb/s.
În codarea la 4,8 kb/s, fereastra este de 30 ms lungime și este împărțită în patru
subferestre de 7,5 ms (60 de eșantioane). La 8 kb/s lungimea ferestrei este de 6 ms și este
împărțită în patru subferestre de 4 ms.
Fig. 9 .a: Histograma cîștigului
050100150200250300350400450
0
60
120180240300360420480540600660720780840900960
42
Fig. 9 .b: Histograma cîștigului în scară logaritmică
Semnalul de cîștig este cuantizat cu 1 bit și amplitudinea poate fi cuantizată eficient cu 4
biți folosind cuantizarea logaritmică sau pe cea neuniformă.
020406080100120140
0 . 5 0 . 7 0 . 9 1 . 1 1 . 3 1 . 5 1 . 7 1 . 9 2 . 1 2 . 3 2 . 5 2 . 7 2 . 9 3 . 1 3 . 3 3 . 5
43
MODELE PENTRU ANALIZA PRIN SINTEZA A SEMNALULUI VOCAL
EȘANTIONAT
MODURI PENTRU ANALIZA PRIN SINTEZĂ LPC
Codurile DM și SBC descrise anteior nu pot reproduce semnalul vocal cu acuratețe la
viteze mai mici de 16kb/s. Pe de altă parte, codurile sursă, (codul LPC cu predicție liniară)
lucrează la viteze mai mici de 2kb/s și în linii mari nu au aplicații comerciale. Codul cu predicție
liniară în forma sa de bază a fost folosit în principal în comunicațiile militare, unde semnalul
vocal trebuie să aibă o viteză foarte mare.
Necesitatea de a reliza o calitate utilă a semnalului vocal la viteze mai mici de 10kb/s
pentru aplicații pe canale care au o inerentă limitare de bandă a captat interesul cerc etătorilor.
Astfel, s- au căutat algoritmi LPC mai eficienți. Limitarea esențială a vocoderelor cu algoritmi
LPC este dată de presupunerea că semnalele vocale sînt vocale și nevocale, în timp ce sursele de
excitație ale filtrelor sintetizate numai cu poli sînt fie cu tren de impulsuri (pentru semnalele
vocale), fie cu zgomot aleator (pentru semnalele nevocale).
De fapt, sînt mai mult de două moduri în care canalul vocal este excitat și deobicei, aceste
moduri sînt mixate. Chiar cînd semnalul este vocal, este o simplificare mult prea mare aceea de a
presupune că este doar un punct de excitație pe întinderea unei perioade. În 1982, Atal a propus
un model nou de excitare car e este cunoscut ca excitație multipuls. În acest model nu este
necesară nici o deczie prioritară dacă semnalul este ne/vocal sau dacă este pe o perioadă.
Excitația este modelată printr -un număr de pulsuri (de obicei 4 -5ms) a căror amplitudini și poziții
sînt determinate prin minimizarea influienței erorii dintre semnalul vocal original și cel sintetizat
la recepție.
Introducerea acestui model a generat un mare interes și a fost primul dintr -o nouă
generație de coduri de analiză capabile să producă o calitate ridicată a semnalului voc al la viteze
de 10kb/s și mai mici de 4,8kb/s. Acastă nouă generație de coduri folosește aceleași filtre de
sinteză ca cele folosite de vocoderele LPC. Semnalul excitat este optimizat cu atenție și codat
eficient folosind tehnic ile codării cu forme de undă. Toate codurile de analiză prin sinteză au
aceeași structură de bază în care excitația este determinată prin minimizarea importanței erorilor
dintre semnalul original și cel sintetizat. Acestea diferă prin modul cum este modelată excitația.
Aproximarea semnalului multipuls presupune că cele atît amplitudinile cît și pozițiile inițiale ale
celor două semnale sînt necunoscute, apoi ele se determină în bucla de minimizare, cîte un impuls
odată. Excitația unui impuls presupune că impulsurile sînt distantate regulat și amplitudinile sînt
calculate din setul de M x M ecuații, unde M este numărul de impulsuri. În codurile cu predicție
liniara (CELP), semnalul excitator este o intrare a unui cod stocastic foarte mare.
Complexitatea aces tor coduri crește odată cu reducerea vitezei de bit. De exemplu, CELP
poate produce o vorbire de calitate bună la viteze mai mici de 4,8kb/s, dar necesită o mare
44
cheltuială pentru un calcul exhaustiv într -un set de coduri cu 1024 intrări pentru determinare a
unei secvențe optime.
Vom descrie în continuare, un sistem de codare cu analiză prin sinteză. Vor fi dezbătute
pe larg părți diferite ale modelului, cum ar fi:
– filtrele LPC cu sinteză (pentru a modela anvelopa semnalului vocal pe termen
scurt)
– predictorul înălțimii sunetului
– filtrele de ponderare a erorii
– procedura de minimizare a erorii.
Definirea secvenței de excitație joacă un rol important în determinarea performanțelor și a
complexității codului. Diferitele modele de excitație vor fi descrise în detaliu (multi – impulsul,
impulsul regulat, CELP, autoexcitarea, excitația cu impuls binar). Vom fi discuta performanțele
și complexitatea acestor modele de excitație.
MODELUL GENERAL DE ANALIZĂ
Structura de bază pentru modelul general de coduri cu analiza prin sinteză este în figura:
Fig. 10 : Modelul general de anliză prin sinteza LPC
Sursă de
excitație
Filtru(e)
de sinteză
Minimizarea
erorii
Predictor
de eroare
(a) Codor
–
u(n)
e(n)
eω(n)
s(n)
semnal
vocal
Sursă de
excitație
Filtru(e)
de sinteză
u(n)
s(n)
semnal
vocal
sintetizat
(a) Decodor
45
Modelul este compus din trei părți principale:
sinteza filtrelor:
filtre cu zerouri pe toată banda, care modelează anvelopa semnalului pentru forma de
undă a semnalului vocal. Este numit filtru cu corelare pe termen scurt, datorită eficienței
sale dată de calculul cu predicție pentru eșnationare (8 -16 eșantioane, ceea ce înseamnă
termen scurt). Sinteza de filtre poate de asemeni include și filtre cu corelație pe termen
lung, care se obțin prin cascadarea filtrelor pe termen scurt. Predictoarele pe termen lung
modelează structuri apropiate de spectrul vocal.
generarea excitaĠi ei:
aceasta produce secvența de excitație care va determina filtrul de sinteză să re alizeze
reconstituirea semnalului vocal la receptor. Excitația este optimizată prin minimizarea
importanței erorii dintre semnalul oricinal și cel sintetizat. După cum arată Fig.10 . în
codor se află un decodor local, iar metoda de analiză pentru optimizarea excitației
folosește diferența dintre semnalul original și cel sintetizat ca un criteriu de eroare, și
alege secvența de excitație care minimizează rolul erorii. Eficiența acestei metode de
analiză provine din procesul de optimizare din bucla închisă. Aceast proces de optimizare
permite reprezentarea predicției restante folosind o viteză de bit mică, în timp ce se
păstrează o calitate înaltă a semnalului vocal. Aceasta explică superioritatea codului cu
analiză prin sinteză cu predicție asupra codurilor cu predictie, care au o structură de inel
deschis, cum ar fi codurile RELP cu predicție liniară cu excitație liniară. Punctul cheie în
structura de inel închis este acel a că restul de predicție este cuantizat prin minimizarea
importanței erorii dintre semnalul original și cel refăcut, decît minimizarea erorii dintre
semnalul reziduu și forma sa cuantizată în structura de buclă deschisă.
criteriul de minimizare a erorilor:
cel mai utilizat criteriu de minimizare a erorilor este eroarea medie pătratică. Eroarea este
trecută printr -un filtru de pondere perceptuală (sesizează înălțimea semnalului), care taie
spectrul zgomotului pentru a concentra puterea la frecvențele din s pectrul vorbirii astfel
încît zgomotul este mascat de semnalul vocal.
46
Procesul de codare parcurge următorii pași:
– se determină parametrii filtrului din eșantionarea semnalului vocal
(10-30ms de vorbire) în afara inelului de optimizare
-secvența optimă de excitație pentru acest filtru este determinată prin criterii de minimizare a
erorii. Intervalul de optimizare a erorii este de obicei în domeniul 4-7,5ms. Domeniul este mai
mic decît parametrii LPC pentru o aceeași fereastră. Fereastra semnalului vocal este împărțită în
două sub -ferestre, unde excitația este determinată individual pentru fiecare sub -fereastră.
Parametrii filtrelor de cuantizare și excitația cuantizată se trimit la receptor. Procesul de
decodare este realizat prin trecerea segmentului de excitație decodat prin filtrul de sintez ă cu
scopul de a reface semnalul vocal.
Semanalele sub- bandă sînt codate pentru a se putea obține o viteză de bit de 15kb/s, în
timp ce informația este la o viteză de 33b/s. Datorită importanței informației, aceasta este potejată
prin repetarea de trei ori și majoritatea logicii este folosită pentru informația auxiliară. Informația
auxiliară este transmisă la 1kb/s și rata pentru codor este de 16kb/s.
Presupunem că fluxul de biți b(n) modulează o purtătoare folosind
BPSK și semnalul modulat este transpus pe un canal de tip Rayleigh. După demodulare, semnalul
în banda de bază este:
) ( ) ( ) ( ) ( n I n b n R n a
unde R(n) este amplitudinea anvelopei cu distrib uție de putere de tip Rayleigh:
) ( sin) ( ) ( cos) ( ) ( n nCn nCn Iy x
C x(n) și C y(n) fiind variabile de tip Gauss aleatoare, iar ф(n) este variabila de fază aleatoare
în +/- π. Dacă transmisia se efectuează pe canal Gaussi an, atu nci R(n) = 1 în relația de mai sus.
Algoritmul SBC descris anterior a fost aplicat atît pentru canale cu distribuție R, cît și
pentru canale cu distribuție G. Cei mai robuști algoritmi sînt algoritmii cu scurgeri de pași β =
63/64 și algoritmii cu forțarea pasului cu T u = 42ms. Progresul în domeniul raportului semnal –
zgomot comparat cu algoritmul de bază, care este mai robust, pentru cele 2 canale, este dat în
Tabelul 1 pentru o rată a erorilor (BER) de 10-2 și 10-3.
47
Alg. cu
Scurgeri Alg. cu
forțări
BER β = 63/64 Tu = 42ms
Canal Rayleight
10-3
10-2 7dB
8,8dB 6dB
11dB
Canal Gaussian
10-3
10-2 7,5dB
5,8dB 6,5dB
8,6dB
Tabelul 1
În regiunea cu BER mare, algoritmul de forțare al pasului cu T u = 42ms este mult mai bun
decît algoritmul cu scurgeri pentru β = 63/64. Invers, cînd BER scade, algoritmul cu scurgeri cu β
= 63/64 este mult mai bun decît algoritmul de forțare al pasului cu T u = 42ms.
Pentru canalul Rayleigh, cei doi algoritmi se intersecteaz ă pentru o rată a erorilor de bit
(BER) de 3,2*10-3. Alte curbe din aceeași familie a algoritmilor robuști cu performanțe similare,
exceptînd valorile SEG – SNR care sînt inferioare regiunii cu BER mici.
Testele de ascultare au arătat că atît semnalul vocal masculin cît și cel feminin este ușor
degradat cînd transmisia este eronată pe cele mai de jos patru sub -benzi (0 – 2kHz). Această
degradare se datorează faptului că majoritatea energiei semnalului vocal este în aceste sub -benzi,
iar sub-benzile sînt co date de cuantizoare cu rată de bit mare. Viteza mare de cuantizare duce la o
performanță mai scăzută și deci la o rata de bit BER mai mare. Astfel, dacă este introdusă
codarea pe canal, semnalul sub- bandă codat necesită o mai mare protecție împotriva erori lor decît
biții codați din benzile din domeniul 2 – 3kHz.
48
PREDICğIA PE TERMEN SCURT
Predictoarele pe termen scurt modulează spectrul anvelopei semnalului vocal pe termen
scurt. Anvelopa are o întindere de L esantioane poate fi aproximată prin funcții de transmisie cu
filtre numai zerouri (fără poli) de forma:
p
kk
kSzazPzH
111
) ( 11) (
unde
p
kk
k S za zP
1
este predicția pe termen scurt.
Coeficienții {a k} se cal culează folosindu -se metoda predicției liniare (LP). Setul de
coeficienți {a k} formează parametrii LPC sau coeficienții de predicție. Numărul coeficienților de
predicție p este numit ordinul de predicție. Ideea de bază în analiza predictivă este aceea că
fiecare eșantion poate fi aproximat prin combinații liniare ale eșantioanelor anterioare (8 – 16
eșantioane).
Aplicăm transformata Z ecuației:
p
kkn s n s n s n s n e
1) ( ) ( ) ( ) ( ) (
se obține
) ( ) ( ) ( z Az S zE
unde
p
kk
kza zA
11) (
A(z) este inversa lui H(z), A(z) filtru invers.
49
Datorită faptului că semnalul vocal este variabil în dimp, coeficienții de predicție pot fi
estimați dintr -un segment scurt de semnal vocal (10- 20ms). Scopul este acela de a găsi un set de
coeficienți de predicție care să minimizeze eroarea medie pătratică a predictorului peste un
segment al formei de undă al semnalului vocal.
Parametrii rezultați sînt apoi parametrii unui sistem cu transformata H(z) în modelul de
producere al vorbirii. Eroarea de predicție este definită de:
np
kkn s n s zE2
1) ( ) ( ) (
p
kk k i k i a
1) , ( ) , ( i = 1….p
Acest set de p ecuații cu p necunoscute poate fi rezolvat eficient cu coeficienții {a k}. Se
calculează mai întîi ф(i,k), i = 1…p, k = 0…p. Pentru a calcula ф(i,k), trebuie specificate limitele
sumei. Pentru analiza pe termen scurt, limitele trebuie să fie într -un interval finit. Se cunosc două
metode de calcul al limitelor sumei:
1. metoda aut ocorelației
2. metoda covarianței
A III- a metodă care calculează coeficienții de reflexie este echivalentă cu reprezentarea
parametrilor filtrului direct din eșantioanele semnalului vocal după ce se trec printr -un estimator
cu coeficienți de autocorelație. Această aproximație este numită metoda covarianței lattice sau
algoritmul BURG. Cu toate că algoritmul Burg are aplicații diferite, deobicei, detecția semnalelor
sinusoidale în zgomot aditiv arată că în aplicațiile care utilizează semnalele vocale, metoda Burg
nu este chiar utilă ca alte metode.
50
METODA AUTOCORELAğIEI
Presupunem că eroarea
2
1) ( ) (
np
kk kn s a n s E
este de calcul pe o durată infinită. Atît timp cît nu poate fi pusă în practică, presupunem că
funcția de undă este identic 0 în afara intervalului 0 n La-1, unde L a este lungimea ferestrei
LPC. Aceasta este echivalentă cu multiplicarea semnalului de la intrare cu o fereastră de lun gime
infinită (n) care este identic 0 în afara intervalului 0 n La-1. Considerăm s(n) este diferit de
0 numai în
0 n La+p-1.
Atunci
1
0) ( ) ( ) , (p L
na
kn s i n s k i
Înlocuim m = n – 1 în formula de mai sus și rezultă
) ( 1
0) ( )( ) , (k i L
na
kimsms k i
(i,k) este autocorelația pe termen scurt a lui s(n) evaluată pentru i – k.
Atunci
) ( ) , ( ki R k i
și rezută
j L
nL
j na a
jn s n s jn s n s jR1
01
) ( ) ( ) ( ) ( ) (
rezultă:
p
kk i R kiRa
1) ( ) (
51
Ecuația de mai sus se poate scrie sub formă matricială:
) (…) 3 () 2 () 1 (
…
) 0 ( … ) 3 ( ) 2 ( ) 1 (… … … … …) 3 ( … ) 0 ( ) 1 ( ) 2 () 2 ( … ) 1 ( ) 0 ( ) 1 () 1 ( … ) 2 ( ) 1 ( ) 0 (
421
pRRRR
aaaa
R pR pR pRpR R R RpR R R RpR R R R
Matricea valorii de autocorelație de dimensiune p x p este matrice de tip Toeplitz
simetrică. Toate elementele de pe diagonală sînt egale. Această proprietate specifică poate fi
exploatată pentru a obține un algoritm eficient de calcul al ecuației 84. Cea mai eficientă soluție
este procesul semirecursiv cunoscut ca algoritmul Durbin:
) 0 ( ) 0 (R E
Pentru i(1, p) calculăm
) 1() ( ) (1
1) (
i Eji R a i R
ki
jj i
j
i
ii
ik a) (
Pentru i(1, i- 1) calculăm
) 1 ( ) 1 ( ) (
i
j i ii
ji
j a k a a
Soluția finală este dată de
) (p
j ja a
Cantitatea E(i) este eroarea prezisă de predictorul de ordin i. Valorile intermediare k i sînt
cunoscute sub numele de coeficienți de reflexie. Au aceeași coeficinți care apar în modelul de tub
fără pierderi al traiectului vocal.
Valoarea lui k i este în domeniul -1 ki 1.
52
Această condiție impusă parametrilor k i este necesară și suficientă pentru ca toate
rădăcinile polinomului A(z) să fie în cercul unitate, condiție care trebuie îndeplinită pentru ca
sistemul H(z) să fie stabil. S -a observat că metoda de autocorelație totdeauna duce la filtre H(z)
stabile.
Eșantionul vocal s(n) este identic 0 în afara domeniului (0, L a – 1). Oricum, o trunchiere
abruptă a semnalului este capabilă să creeze o creștere mai mare în predicția erorii la începutul și
la sfîrșitul segmentului analizat. Această problemă este evitată dacă se utilizează o fereastră
îngustă, de exemplu fereastra Hamming, a cărei amplitudine tinde la 0 treptat, nu abrupt.
Fereastra Hamming este dată de
12cos46, 0 54, 0) (
aLnn , 0 n La – 1
unde L a este lungimea cadrului analizat LPC. Lungimea L a a ferestrei Hamming este deobicei
aleasă mai lungă decît lungimea ferestrei semnalului vocal L. Dacă se sar ferestre de semnal se
obține în analiza LPC un efect fin. Se micșorează modificările abrupte în coeficienții LP C dintre
analiza blocurilor.
METODA COVARIANğELOR
Presupunem că eroarea E este minimizată peste un interval finit 0 n L-1. Pentru
aceasta, (i,k) este dat de
1
0) ( ) ( ) , (L
nkn s i n s k i
Setul de ecuații de mai sus poate f i scris și sub formă matricială
) 0 , (…) 0 , 3 () 0 , 2 () 0 , 1 (
…
) , ( … ) 3 , ( ) 2 , ( ) 1 , (… … … … …) , 3 ( … ) 3 , 3 ( ) 2 , 3 ( ) 1 , 3 () , 2 ( … ) 3 , 2 ( ) 2 , 2 ( ) 1 , 2 () , 1 ( … ) 3 , 1 ( ) 2 , 1 ( ) 1 , 1 (
321
p aaaa
pp p p pppp
p
53
Atît timp cît (i,k) = (k,i), matricea de dimensiune pxp este simetrică, dar nu este de tip
Toeplitz. Se utilizează descompunerea ecuației de mai sus în descompunere Cholesky, unde
matricea pxp este descompusă în
TVDV
unde V este matrice triunghiulară cu elementele de pe diagonală egale cu 1
D este matrice diagonală
T este matricea transpusă.
Altă formă a descompunerii C este
TUU
unde U este matrice triunghiulară sub diagonala principală. U din ecuația 93 și V din ecuația 92
sînt legate prin
DVU
Spre deosebire de metoda autocorelației, metoda covarianței nu garantează totdeauna
stabilitatea filtrului H(z). Pentru aceasta, poate fi utilizată metoda covarianței stabilizate.
În metoda covarianței stabilizate matricea de covarianță este descompu să conform:
ca UUT
unde a = a1, a2,…..,a pT și c = (1,0),(2,0),…..,(p,0)T. Elementele lui U se calculează din
elementele matricii cu formula de recurență:
pentru j de la 1 la p se calculează
1
1j
kjk jj ij u u
pentru i de la j + 1 la p se calculează
1
11j
kjk ik ij
jjij uuuu
54
Fie
aUgT ,
Rezulta:
c Ug
Atât timp ca t matricea U are o structură triunghiulară sub diagonala principală, ecuația de mai sus
este ușor de rezolvat pentru g de forma:
,11
1
i
kijij i
iii gu cug
Coeficienții de reflexie se găs esc din elementele vectorului g
1
100i
kkiji
i
gugk
CONSIDERAğII ÎN ALEG EREA CONDIğIILOR DE ANALIZĂ LPC
Variabilele în analiza LPC sînt :
– metoda de analiză
– ordinul predictorului
– lungimea cadrului.
Folosim multi- pulse LPC pentru a obține date despre efectul analizei menționate asupra
calității semnalului vocal. Prin metodele de analiză găsim că amîndouă metodele, atît cea cu
autocorelație cît și cea cu covarianță stabilă duc la rezultate similare. Este destul de dificil să
distingem cele două metode în condiții de analiză identice. Metoda cu autocorelație este folosită
peste tot în cercetare. A doua variantă în analiza LPC este numărul de coeficienți de predicție p.
55
Pentru a reduce numărul de biți necesari codării trebuie să folosim un minim de parametri
pentru a modula cît mai bine anvelopa spectrală pe termen scurt a semnalului vocal. Pentru o
reprezentare adecvată a "traiectului vocal" (tubului vocal) în condiții ideale, memoria
modulatorului trebuie să fie egală cu de două ori timpul necesar undelor sonore să parcurgă
distanța glotă – buze, ceea ce este egal cu 2*l/c, unde l = lungimea canalului vocal, iar c = viteza
sunetului. De exemplu, pentru c = 34cm/s și l = 17 cm este necesară o memorie de 1ms.
Cînd frecvența de eșantionare este f s eșantioane/s, unei perioade de 1ms îi corespund
fs/1000 eșantioane. La viteze de 8kHz, ordinul predictorului trebuie să fie de cel puțin 8 pentru
acest model ideal. În general este necesar să adunăm cîțiva coeficienți (4 sau 5) pentru a potrivi
alți factori care au fost admiși din modelul tubului ideal (radiația buzei și a glotei și faptului că
semnalele vocale eșantionate nu sînt chiar forme de undă de la ieșirea unor filtre fără zerouri.
Fig.11: Caștigul predictorului în funcție de ordinul LPC
Fig. 11 arată media cîștigului de predicție funcție de ordinul de predicție p pentru 20s de
vorbire dintre două persoane de sex feminin și două persoane de sex masculin. Cîștigul de
predicție pentru cadru l vorbirii este
nn
nrns
G) () (
22
unde r(n) este reziduul predicției.
012345678910
0 2 4 6 8
10 12
1
16 18 20ordinul predictorului caștigul predictorului
56
În cazul metodei de autocorelație cîștigu l predictorului poate fi scris:
p
iip
ii k i Ra RRG
12
1) 1 (1
) ( ) 0 () 0 (
Media ca știgului de predicție în dB este:
1
0log101fN
ii
fav GNG
unde N f este numărul de cadre. Este clar din Fig. 11 că cîștigul de predicție începe să se satureze
de la predictoare de ordin mai mare ca 8.
Fig.12: SEG – SNR funcție de ordinul predictorului MPE – LPC
Fig.12 arată SEG -SNR al MPE- LPC variind ordinul predictorului între 8 și 14.
Degradarea calității semnalului vocal devine notabilă cînd p este redus la 8 și calitatea este
saturată cînd p este aproape de 12. Am observat că alegerea lui p = 10 este foarte rezona bilă
pentru o reprezentare adecvată a canalului vocal.
A treia varibilă în analiza LPC este modernizarea intervalului L. Ca și la alegere ordinului
de predicție p, alegerea unui interval de actualizare este un compromis între calitate și viteză. Este
de dorit să executăm o analiză spectrală într -un interval unde mișcarea tubului vocal este
neglijabilă. Pentru vocale, acest interval este de ordinul a 15 – 20ms, și este de obicei scurtat
pentru semnalele nevocale.
SEG-SNR
ordinul predictorului
57
De fapt, sunetul asociat cu eliberarea unei consoane nevocale în poziția inițială, de
exemplu t poate exista numai cîteva ms. Analiza asincronă (plasarea arbitrară în timp a
intervalelor de observație a poziției de rostogolire) deobicei se va extinde mediind porțiuni în
care se aude t cu porțiuni de tăcere care precede t. Astfel încît, pentru acuratețea anali zei zonelor
de tăcere este necesar un interval de 10ms, în timp ce sunetele cvasiperiodice, cum sînt
majoritatea vocalelor, necesită un interval de 15 – 20ms. Cînd se folosește un predictor cu 10
coeficienți, se cuantizează cu 40 de biți pentru o cuantizare scalară pe așa -numitul raport
logaritmic de arii. Dacă intervalul este mărit la 20ms, pentru a cuantiza LPC sînt neces ari 2kb/s.
Pe de altă parte, dacă se reactualizează la fiecare 10ms coeficienții, vitez a va crește la 4kb/s.
Aceasta înseamnă o creștere de 2kb/s, care este semnificativă pentru o codare la viteză mică.
Fig.13: SEG – SNR funcție de intrervalul de reactualizare
Fig. 13 arată descreșterea în SNR a MPE o dată cu creșterea intervalului de reactualizare.
Putem deci concluziona că pentru o viteză mică a codării, un interval de reactualizare de
20ms este suficient pentru a obține o calitate bună a vorbirii, cu toate că aceasta introduce o
perturbare mică în cîteva sunete care își schimbă repede caracteristica spectrală (de exe mplu
sunetele tranzitorii).
12.51313.514
10 15 20 25 303-D Line 1SEG-SNR (dB)
intervalul de reactualizare (ms)
58
Concluzii
Programele care implementeazã algoritmi de comprimare sunt performante prin
flexibilitatea de a utiliza diferentiat algoritmii.
Problematica realizãrii unei colectii a algoritmilor de comprimare rãmâne în actualitate
mai ales pentru cazurile particulare. Astfel un text format din numere cuprinse între 109 –
3*1010, ca în cazul capitalului social al firmelor din Lista de Privatizare, poate fi comprimat fãrã
pierdere de informatie, conducând la un grad de comprimare foarte bun.
Se poate realiza comprimare si prin apelarea unor functii de conversie. Astfel fisierele ce
contin reprezentãri în zecimal despachetat de numere, pe 5 octeti, cu valori în intervalul (-32767;
32767), prin reprezentarea binarã determinã punerea în corespondentã cu un câmp de doi octeti.
59
Bibliografie
(Internet 1,
2004) http://www.data-compression.com/lempelziv.shtml , 2004.
(Pinceton,
2004) http://www.princeton.edu/~matalive/VirtualClassroom/v0.1/html/lab2/lab2_7.ht
ml
(Ziv and
Lempel 1977) Jacob Ziv and Abraham Lempel , A Universal Algorithm for Sequential Data
Compression, IEEE Transactions on Information Theory , Vol. 23, pp. 337 –342,
May 1977.
(Ziv and
Lempel 1978) Jacob Ziv and Abraham Lempel, Compression of Individual Sequences Via
Variable-Rate Coding, IEEE Transactions on Information Theory , Vol. 24, pp.
530–536, 1978.
(Welch, 1984) Terry Welch , A Technique for High-Performance Data Compression , Computer,
pp. 8 —18, June 1984.
B.M.G.Cheetham. "Adaptive LSP filter". Electronics Letters, 16 Ian 1987
CCITT, Recommendation
C.R.Rabiner and RWSchroeder "Digital Processing of Speech Signal", Prentince Hall, 1978.
D. Esteban and C.Galand "Application of quadrature mirror filtres to split band voice coding
scheme", pp.191-195, may 1997
G.S.Kang și L.J.Fransen "Low -bit rate speech encoders based on line-spectrum frequencies".
NRL Report 8857, Nov 1984
J.Makhoul "Linear prediction: a tutorial review", April 1984
M.Omologo. "the computation and some spectral considerations on line spectrum pairs"
Proc.EUROSPEECH'89 1989
60
ABREVIERI
ADCT = transformarea cosinus discretă adaptivă (ADAPTIVE DCT )
ADPCM = modulație în impuls delta adaptivă
AQB = cuantizoare cu estimare cu reacție în urmă
BER = rata erorii de bit
BPSK = modulație binară de fază
DCT = transformarea cosinus discretă
DFT = transformata Fourier
DM = modulație delta
DPCM = modulație în impuls delta
EDM = modulație delta înlănțuită
FEC = cod corector de erori
QMF = filtre în oglindă
LAR Log-Area Ratio
LPC = cod cu predicție liniară
MSDM = modulație delta multi -nivel
MNRU = (MODULATED NOISE REFERENCE UNIT)
MPE = multi-impuls
PCM = modulație în impuls
PDF = funcția densitate de probablitate
PSD = densitate spectrală de putere
RELP = excitație și predicție liniare
RPE = impuls regulat
SBC = semnal sub bandă
SNR = raportul semnal zgomot
VQ = cuantizare vectorială (VECTORIAL QUANTISATION)
VSELP = vectorul sumă de excitație
61
Anexa 1 – Scurt Istoric (LZW)
May 1977: apare lucrarea (Ziv and Lempel, 1997). Desi articolul este intens matematizat,
tehncica generala de lucru este de a considera siruri de caractere care se repata si inlocuirea
acestora cu un numar a carui reprezentare sa fie mai mica decat cea a siruluyi original. Multe
instrumente software de compresie se bazeaza pe acest algoritm: ZIP, ZOO, ARC, gzip, LhA,
CAB, Arj, RAR.. Acest algoritm este denumit LZ77 si nu este foarte raspandit din cauza
dificultatilor de implementare.
September 1978: apare lucrarea (Ziv and Lempel, 1998). Tehnica este deosebita de LZ77 in
sensul ca se mentine un dictionar de siruri in loc de considerarea unei ferestre. Algoritmul este
foarte popular. Algoritmul se numeste LZ78.
20th June 1983: Terry Welch scrie o versiune a lui LZ78 bazandu-se pe simplificari substantiale
si un management mai bun al dictionarului. Algoritmul se numeste LZW, dupa numele
inventatorilor sai, Lempel-Ziv-Welch.
5th July 1984: Apare UNIX compress , dupa publicarea articolului lui Welch.
15th June 1987 : Apare formatul grafic numit GIF (Graphics Interchange Format), care foloseste
pentru compresie algoritmul LZW.
Anexa 2 – Codul Matlab pentru codarea LZW (Lempel-Ziv-Welch)
% ALGORITM DE CODARE LZW:
% varianta cea mai simpla in care se cunoaste alfabetul;
clc; clear;
exemplu = 3;
switch exemplu,
case 1,
% se considera initializat dictionarul cu ASCII de la 0 -255;
A = 'ab' ; % alfabetul
in = 'abbaabbaababbaaaabaabba'; % secventa de intrare;
% initializare dictionar:
for i=1:length(A), D(i) = {A(i)}; end;
%code-corect = '1 -2-2-1-3-5-3-7-6-6-8-4- 1';
%dictionar -corect =
%'a-b-ab-bb-ba-aa-abb-baa-aba-abba-aaa-aab-baab-bba';
case 2,
A = 'abc'; % alfabetul
in = 'ababcbababaaaaaaa'; % secventa de intrare
% initializare dictionar:
for i=1:length(A), D(i) = {A(i)}; end;
62 %code -corect = '1 -2-4-3-5-8-1- 10-11';
%dictionar -corect = 'a -b-c-ab-ba-abc-cb-bab-bab-aa-aaa-aaaa';
case 3,
% se considera initializat dictionarul cu ASCII de la 0 -255;
A = '/WEDTB' ; % alfabetul
in = '/WED/WE/WEE/WEB/WET'; % secventa de intrare;
% initializare dictionar:
for i=1:length(A), D(i) = {A(i)}; end;
%code -corect = '/ -W-E-D-256-E-260-261-257-B-260-T';
%dictionar -corect = ;
end
% citeste primul caracter:
i=1;
S = in(i);
gata = 0;
code=[];
i=i+1;
while ~gata,
nou = 0;
while ~nou & (i <= length(in)),
% citeste urmatorul caracter:
K = in(i);
% cauta sirul SK in dictionar:
[index, nou] = f_cauta_string([S K], D);
if ~nou, S = [S K]; end;
i=i+1;
end; % while nou
if nou,
n = length(D);
D(n+1) = {[S K]}; % actualizare dictionar;
[index, nou] = f_cauta_string(S, D); % cauta indexul lui S:
index_string = num2str(index);
code = [code {index_string}];
S = K;
end;
if i > length(in), gata = 1; end;
end; % while gata
function [index, nou] = f_cauta_string(S, D)
% cauta indexul lui S in lista dictionar D:
% nou = 1, inseamna ca S nu este in lista D
nou = 1;
for j = 1:length(D),
x = char(D(j));
if (length(x) == length(S)) & (S == x),
index = num2str(j);
nou = 0;
break;
end;
end;
Copyright Notice
© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.
Acest articol: Diseratie Vasilache Stefan 2017 [627303] (ID: 627303)
Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.