T.cniques de codificaci. de font3 - La Salleweb.salleurl.edu/~moran/Assets/Cod_font.pdf · • La codificació de fonts analògiques ha estat àmpliament lligades a la codificació

•Processament Avançat

Tècniques de Tècniques de codificació de font.codificació de font.

Sistemes de Transmissió.Sistemes de Transmissió.Curs 2003/2004Curs 2003/2004Jose Antonio MoránJose Antonio Morán

Joan Claudi SocoróJoan Claudi Socoró

Departament de Comunicacions i Teoria del SenyalDepartament de Comunicacions i Teoria del Senyal

Sistemes de Transmissió Dep. Comunicacions i Teoria del Senyal

TemariTemari

1.1. Introducció a la codificació de font.Introducció a la codificació de font.2.2. ModelitzacióModelització i tractament de fonts i tractament de fonts

discretes.discretes.3.3. Tècniques de codificació de fonts Tècniques de codificació de fonts

discretes.discretes.1.1. Mètode de Mètode de HuffmanHuffman..2.2. Codificació Codificació LempelLempel--ZipZip..

4.4. Codificació de fonts analògiques.Codificació de fonts analògiques.5.5. Aplicacions de codificació de font.Aplicacions de codificació de font.



Introducció a la codificació de fontIntroducció a la codificació de font•• La codificació de font tracta el problema de realitzar La codificació de font tracta el problema de realitzar

descripcions eficients de les fonts d’informació.descripcions eficients de les fonts d’informació.•• Els sistemes de comunicacions digitals únicament poden Els sistemes de comunicacions digitals únicament poden

transmetre dades en un format digital. El transmetre dades en un format digital. El codificadorcodificador de de font tractarà la informació d’entrada i l’adaptarà per font tractarà la informació d’entrada i l’adaptarà per transmetretransmetre--la en un format digital.la en un format digital.

Codificadorde font

Font analògica

Font digital

1001100...


•• Fonts discretes.Fonts discretes.•• En el cas de les fonts discretes, l’objectiu fonamental de En el cas de les fonts discretes, l’objectiu fonamental de

la codificació serà reduir el la codificació serà reduir el data data raterate de sortida.de sortida.•• La capacitat de compressió dependrà del contingut de la La capacitat de compressió dependrà del contingut de la

informació i de la correlació entre símbols.informació i de la correlació entre símbols.•• Fonts analògiques.Fonts analògiques.

•• En aquest tipus de fonts es codificarà seguint un criteri En aquest tipus de fonts es codificarà seguint un criteri de fidelitat per determinar la bondat del de fidelitat per determinar la bondat del codificadorcodificador..

•• Existeixen dues possibilitats.Existeixen dues possibilitats.•• Millorar la relació SNR per una velocitat de dades donada.Millorar la relació SNR per una velocitat de dades donada.•• Reduir la velocitat de dades per una SNR donada.Reduir la velocitat de dades per una SNR donada.

•• El criteri de fidelitat establert dependrà en tot moment El criteri de fidelitat establert dependrà en tot moment del tipus de dades.del tipus de dades.

•• Veu: SNR, proves d'intel·ligibilitat, Veu: SNR, proves d'intel·ligibilitat, etcetc......•• Imatge: SNR, aspecte visual, Imatge: SNR, aspecte visual, etcetc......

Introducció a la codificació de fontIntroducció a la codificació de font



ModelitzacióModelització i Tractament de fonts i Tractament de fonts discretesdiscretes

•• Es considera una font de dades discreta com Es considera una font de dades discreta com aquella que genera, a una velocitat constant, una aquella que genera, a una velocitat constant, una seqüència de símbols a partir d’un alfabet finit {xseqüència de símbols a partir d’un alfabet finit {x11, , xx22, x, x33,..., ,..., xxNN}.}.•• Exemples de fonts discretes:Exemples de fonts discretes:

•• Caràcters ASCII d’un terminal o fitxer de text.Caràcters ASCII d’un terminal o fitxer de text.•• Sortida d’un Sortida d’un conversorconversor A/D.A/D.

•• Una font discreta queda completament definida Una font discreta queda completament definida pel conjunt de símbols que la formen així com la pel conjunt de símbols que la formen així com la probabilitat d’aparició dels mateixos.probabilitat d’aparició dels mateixos.


•• L’objectiu de la codificació de font és L’objectiu de la codificació de font és enviar el màxim d’informació en el menor enviar el màxim d’informació en el menor temps possible.temps possible.

•• Com podem mesurar la informació d’una Com podem mesurar la informació d’una font discreta?font discreta?





•• Quin d’aquests missatges porta més informació?Quin d’aquests missatges porta més informació?•• Demà sortirà el sol.Demà sortirà el sol.•• Demà hi haurà un terratrèmol.Demà hi haurà un terratrèmol.•• Demà hi haurà classe.Demà hi haurà classe.

•• Com podem definir formalment el grau Com podem definir formalment el grau d’informació que porta cada missatge?d’informació que porta cada missatge?

La informació d’un missatge és inversament proporcional a la seva

probabilitat d’aparició.



•• Informació pròpia:Informació pròpia:•• Definirem la informació pròpia d’un símbol segonsDefinirem la informació pròpia d’un símbol segons

•• Aquest paràmetre indica el nombre de bits necessaris per Aquest paràmetre indica el nombre de bits necessaris per codificar aquest símbol.codificar aquest símbol.

•• S’observa que, essent el logaritme una funció monòtona S’observa que, essent el logaritme una funció monòtona creixent, a menor sigui la probabilitat més gran serà la creixent, a menor sigui la probabilitat més gran serà la informació del símbol.informació del símbol.

•• Existeixen altres mesures d’informacióExisteixen altres mesures d’informació•• LogLog22 bits.bits.•• LogLog1010 hartleyshartleys..•• LogLogee nats.nats.

( ) ( )ii PXI 2log−=




•• EntropiaEntropia de la fontde la font•• Es defineix Es defineix l’entropial’entropia de la font com el de la font com el promigpromig

d’informació que proporciona una determinada font d’informació que proporciona una determinada font discreta.discreta.

•• Font sense memòria.Font sense memòria.•• Una font discreta es defineix sense memòria quan tots els Una font discreta es defineix sense memòria quan tots els

símbols generats per la font són estadísticament símbols generats per la font són estadísticament independents independents

•• La independència estadística indica que la informació per La independència estadística indica que la informació per transmetre M símbols serà exactament la suma additiva de transmetre M símbols serà exactament la suma additiva de la informació dels M símbols que formen part del la informació dels M símbols que formen part del missatge.missatge.

( ) ( ) ∑∑ ==

== N

j jj

N

j jj PPXIPXH1 21

1log

( ) ( ) ( ) ( ) ( )kjkkjkj XPXPXPXXPXXP ==,



•• Font discreta amb memòria.Font discreta amb memòria.•• Una font discreta té memòria si els elements de la font no Una font discreta té memòria si els elements de la font no

són independents entre si. Aquesta dependència indica són independents entre si. Aquesta dependència indica que la incertesa del símbol M es veu reduïda pel fet de que la incertesa del símbol M es veu reduïda pel fet de conèixer els M símbols anteriors.conèixer els M símbols anteriors.

•• CALIFORNI_ ???CALIFORNI_ ???

•• L’entropiaL’entropia d’una font amb memòria es defineix segons d’una font amb memòria es defineix segons X={XX={X11,X,X22,...,X,...,XNN}}

( ) ( )XHXH MM ∞→= lim



ExemplesExemples

•• Representar Representar l’entropial’entropia d’una font discreta binàriad’una font discreta binària•• ‘0’ amb probabilitat p‘0’ amb probabilitat p•• ‘1’ amb probabilitat (1‘1’ amb probabilitat (1--p)p)


ExemplesExemples

•• Tenim una font d’informació discreta Tenim una font d’informació discreta definida pel següent modeldefinida pel següent model

0 1P(0|0)=0.95

P(1|0)=0.05

P(0|1)=0.45

P(1|1)=0.55



ExemplesExemples

•• Solució.Solució.•• H(X|0)=0.286H(X|0)=0.286•• H(X|1)=0.993H(X|1)=0.993•• P(1)=0.1P(1)=0.1•• P(0)=0.9P(0)=0.9•• H(X)=0.357H(X)=0.357


Tècniques de codificació de fonts Tècniques de codificació de fonts discretesdiscretes

•• Model genèric d’un Model genèric d’un codificadorcodificador de fonts de fonts discretes.discretes.

Codificador

Memòria Model

Símbols amb redundància

Símbols sense redundància



•• Principals grups de Principals grups de codificadorscodificadors discrets:discrets:•• Codis de longitud fixa.Codis de longitud fixa.•• Mètodes Heurístics.Mètodes Heurístics.•• Mètodes basats en diccionaris.Mètodes basats en diccionaris.•• CodificadorCodificador per per entropiaentropia..

Tècniques de codificació de fonts Tècniques de codificació de fonts discretesdiscretes


Codis de longitud fixa.Codis de longitud fixa.

•• És el mètode més ineficaç, però a la vegada el més És el mètode més ineficaç, però a la vegada el més utilitzat per la seva senzillesa.utilitzat per la seva senzillesa.

•• Donat un alfabet de n símbols, a cada símbol se li Donat un alfabet de n símbols, a cada símbol se li assigna un codi de longitud fixa.assigna un codi de longitud fixa.

•• La longitud del codi mínima seràLa longitud del codi mínima serà•• ceilceil(log(log22(n))(n))

•• L’exemple de codi de longitud fixa més conegut L’exemple de codi de longitud fixa més conegut és el codi ASCII.és el codi ASCII.



Codi ASCIICodi ASCII


Mètodes HeurísticsMètodes Heurístics

•• Es basen en una idea feliç per tal d’explotar Es basen en una idea feliç per tal d’explotar la redundància inherent a un tipus de dades la redundància inherent a un tipus de dades determinades.determinades.

•• Un exemple d’aquest tipus de mètodes és la Un exemple d’aquest tipus de mètodes és la transmissió de transmissió de FaxFax..•• [Símbol, [Símbol, nºnº repeticions, repeticions, simbolsimbol, , nºnº repeticions...repeticions...•• RunRun LengthLength CodingCoding..

•• OptimitzenOptimitzen la transmissió de caràcters en blanc.la transmissió de caràcters en blanc.



Mètodes basats en diccionarisMètodes basats en diccionaris

•• Molt utilitzat en aplicacions de transmissió Molt utilitzat en aplicacions de transmissió de text.de text.

•• Substitueixen la transmissió directa del Substitueixen la transmissió directa del caràcters per la transmissió d’un índex que caràcters per la transmissió d’un índex que representa tota una cadena de símbols d’un representa tota una cadena de símbols d’un determinat diccionari.determinat diccionari.

•• El guany de codificació s’obté si el El guany de codificació s’obté si el diccionari conté les cadenes de caràcters diccionari conté les cadenes de caràcters més comuns dintre del text.més comuns dintre del text.


Codificació per Codificació per entropiaentropia..

•• Són mètodes que utilitzen models Són mètodes que utilitzen models estadístics de la font d’informació a estadístics de la font d’informació a transmetre.transmetre.

•• Els mètodes de codificació per Els mètodes de codificació per entropiaentropiaintenten comprimir la informació de la font intenten comprimir la informació de la font de tal forma que el valor mig de bits de tal forma que el valor mig de bits transmesos tendeixin al valor de transmesos tendeixin al valor de l’entropial’entropia..

•• Els mètodes més coneguts són el Els mètodes més coneguts són el codificadorcodificador aritmètic i el codi de aritmètic i el codi de HuffmanHuffman..



Codi de Codi de HuffmanHuffman..

•• El codi de El codi de HuffmanHuffman assigna codis de longitud assigna codis de longitud variable a cada símbol de la font discreta.variable a cada símbol de la font discreta.

•• El nombre mig de bits per símbol s’aproxima a El nombre mig de bits per símbol s’aproxima a l’entropial’entropia de la font.de la font.

•• Els codis generats tenen la propietat de prefix.Els codis generats tenen la propietat de prefix.•• Cap codi serà mai un prefix de cap altre codi vàlid del Cap codi serà mai un prefix de cap altre codi vàlid del

sistema, evitant així l’ambigüitat en el procés de sistema, evitant així l’ambigüitat en el procés de descodificació.descodificació.


Codi de Codi de HuffmanHuffman



Codi de Codi de HuffmanHuffman



•• Donada una font discreta amb els següents Donada una font discreta amb els següents símbols i probabilitats:símbols i probabilitats:•• ‘a’ p=2‘a’ p=2((--4)4)

•• ‘e’ p=2‘e’ p=2((--4)4)

•• ‘i’ p=2‘i’ p=2((--4)4)

•• ‘o’ p=2‘o’ p=2((--2)2)

•• ‘u’ p=2‘u’ p=2((--1)1)

•• ‘k’ p=2‘k’ p=2((--4)4)

•• Determineu el codi de Determineu el codi de HuffmanHuffman associat.associat.




•• Conclusions.Conclusions.•• És un És un codificadorcodificador òptim si les probabilitats òptim si les probabilitats

d’aparició dels símbols són potències de 2d’aparició dels símbols són potències de 2((--1)1)..•• El problema que presenta el codi és que sempre El problema que presenta el codi és que sempre

ha d’assignar un nombre fix de bits per símbol.ha d’assignar un nombre fix de bits per símbol.•• Es poden tractar grups de símbols com a unitats Es poden tractar grups de símbols com a unitats

de codificació reduint així el nombre mig de de codificació reduint així el nombre mig de símbols de sortida.símbols de sortida.


CodificadorCodificador LempelLempel--ZipZip..

•• En moltes aplicacions resulta difícil definir de forma En moltes aplicacions resulta difícil definir de forma consistent l’estadística de la font discreta.consistent l’estadística de la font discreta.•• Aquestes poden ser no estacionaries i l’estadística va canviant Aquestes poden ser no estacionaries i l’estadística va canviant

durant el temps.durant el temps.•• El codi de El codi de HuffmanHuffman requereix conèixer exactament requereix conèixer exactament

l’estadística de la font.l’estadística de la font.•• L’algorisme L’algorisme LempelLempel--ZipZip és un algorisme universal de és un algorisme universal de

codificació de font, en el sentit que no requereix un estudi codificació de font, en el sentit que no requereix un estudi previ específic per a la seva previ específic per a la seva implementacióimplementació..

•• És l’algorisme que s’utilitza en la majoria de sistemes És l’algorisme que s’utilitza en la majoria de sistemes comercialscomercials•• MSMS--DOS, UNIX, GZIP.DOS, UNIX, GZIP.



•• El diccionari del codi es va generant a mesura que es El diccionari del codi es va generant a mesura que es codifica la seqüència de dades.codifica la seqüència de dades.

•• Si es troba una coincidència amb el següent bloc de dades Si es troba una coincidència amb el següent bloc de dades a codificar, aleshores el a codificar, aleshores el codificadorcodificador envia l’adreça envia l’adreça associada al bloc seguit del següent símbol, i afegeix la associada al bloc seguit del següent símbol, i afegeix la nova seqüència al diccionari.nova seqüència al diccionari.

•• El diccionari El diccionari s’inicialitzas’inicialitza amb cap entrada, de tal forma amb cap entrada, de tal forma que els primers blocs no contenen preàmbuls, únicament que els primers blocs no contenen preàmbuls, únicament estan els símbols base de la font.estan els símbols base de la font.

•• Cada símbol transmès consta de dos paquets d’informacióCada símbol transmès consta de dos paquets d’informació•• <Adreça diccionari, següent símbol a transmetre><Adreça diccionari, següent símbol a transmetre>

•• El sistema afegirà dades al diccionari fins esgotar la El sistema afegirà dades al diccionari fins esgotar la capacitat.capacitat.•• Quan la memòria estigui plena es codificarà buscant la paraula dQuan la memòria estigui plena es codificarà buscant la paraula de e

longitud màxima existent en el diccionari.longitud màxima existent en el diccionari.

CodificadorCodificador LempelLempel--ZipZip







LempelLempel--ZipZip

•• ProblemaProblema•• [a b a a b a b b b b b b b a b b b b b a][a b a a b a b b b b b b b a b b b b b a]•• CodificacióCodificació

•• <0,a><0,b><1,a><2,a><2,b><5,b><5,a><6,b><4,<0,a><0,b><1,a><2,a><2,b><5,b><5,a><6,b><4,-->>



•• A mesura que creixi el diccionari, les A mesura que creixi el diccionari, les paraules codificades seran més llargues, paraules codificades seran més llargues, produint això un guany de codificació.produint això un guany de codificació.

•• Aquest mètode es va apropant a Aquest mètode es va apropant a l’entropial’entropiade la font quant més llarg sigui el diccionari de la font quant més llarg sigui el diccionari i més llarg sigui el missatge a transmetre.i més llarg sigui el missatge a transmetre.

•• El diccionari no cal retransmetre’l, ja que el El diccionari no cal retransmetre’l, ja que el receptor el pot reconstruir a partir del receptor el pot reconstruir a partir del missatge original.missatge original.



Codificació de fonts analògiquesCodificació de fonts analògiques•• La codificació de fonts analògiques ha estat àmpliament La codificació de fonts analògiques ha estat àmpliament

lligades a la codificació de font.lligades a la codificació de font.•• La història de la codificació de veu va començar ara fa 50 La història de la codificació de veu va començar ara fa 50

anys als laboratoris Bell.anys als laboratoris Bell.•• Transmissió de veu per cable de telegrafia.Transmissió de veu per cable de telegrafia.•• VOCODER (VOCODER (VoiceVoice CoderCoder) de ) de DudleyDudley..•• Gran interès a la segona Guerra Mundial.Gran interès a la segona Guerra Mundial.

•• Durant la dècada dels 40 es van començar a treballar en les Durant la dècada dels 40 es van començar a treballar en les tècniques de codificació per tècniques de codificació per pulsospulsos..•• PCM, DPCM i ADPCM.PCM, DPCM i ADPCM.•• Aquestes tècniques es van proposar com estàndard de la CCITT Aquestes tècniques es van proposar com estàndard de la CCITT

((InternationalInternational ConsultativeConsultative CommitteeCommittee fot fot TelephoneTelephone andandTelegraphTelegraph).).

•• Des de els 80 la investigació s’ha orientat a aconseguir Des de els 80 la investigació s’ha orientat a aconseguir codificadorscodificadors que utilitzin una amplada de banda baixa i que que utilitzin una amplada de banda baixa i que millorin la qualitat de la veu.millorin la qualitat de la veu.



•• Des de la perspectiva de la transmissió de senyal Des de la perspectiva de la transmissió de senyal de veu en interessa:de veu en interessa:•• OptimitzarOptimitzar l’ús del canal amb la transmissió del màxim l’ús del canal amb la transmissió del màxim

d’informació possible.d’informació possible.•• MaximitzarMaximitzar la la tasatasa de transmissió reduint el de transmissió reduint el datadata--raterate i i

mantenint una bona intel·ligibilitat del missatge.mantenint una bona intel·ligibilitat del missatge.

•• Des de la perspectiva d'emmagatzematge:Des de la perspectiva d'emmagatzematge:•• Codificar de forma òptima el senyal de veu tot Codificar de forma òptima el senyal de veu tot

mantenint el nivell de qualitat desitjada.mantenint el nivell de qualitat desitjada.

Codificació de fonts analògiquesCodificació de fonts analògiques


MostratgeMostratge i i quantificacióquantificació

•• El senyal analògic s’ha de convertir a un senyal discret per El senyal analògic s’ha de convertir a un senyal discret per poderpoder--se processar i tractar amb un se processar i tractar amb un hardware hardware digital.digital.

•• El El conversorconversor Analògic digital és el dispositiu encarregat Analògic digital és el dispositiu encarregat de realitzar aquest procés.de realitzar aquest procés.



MostratgeMostratge

•• Segons el criteri de Segons el criteri de NyquistNyquist, podem reconstruir un , podem reconstruir un senyal sempre i quan la freqüència de senyal sempre i quan la freqüència de mostratgemostratgesigui superior a dos vegades la freqüència sigui superior a dos vegades la freqüència màxima de senyalmàxima de senyal


QuantificacióQuantificació

•• La La quantificacióquantificació és el procés de conversió és el procés de conversió d’una funció contínua en amplitud a una d’una funció contínua en amplitud a una funció discreta en amplitud.funció discreta en amplitud.

•• El valor de cada mostra es representa amb El valor de cada mostra es representa amb un valor escollit entre un conjunt finit de un valor escollit entre un conjunt finit de valors.valors.

•• Existeixen dos tipus de Existeixen dos tipus de quantificacionsquantificacions•• QuantificacióQuantificació uniforme.uniforme.•• QuantificacióQuantificació logaritmicalogaritmica



QuantificacióQuantificació uniformeuniforme

•• Els intervals de Els intervals de quantificacióquantificació són constants, essent són constants, essent qqel pas de el pas de quantificacióquantificació..

•• El procés de El procés de quantificacióquantificació és pot modelar de forma és pot modelar de forma lineal com la suma d’un soroll blanc que provoca lineal com la suma d’un soroll blanc que provoca una distorsió equivalent a la del procés.una distorsió equivalent a la del procés.

( ) ( )tetxtxq +=)(



•• El soroll de El soroll de quantificacióquantificació en un en un intèrvalintèrval es pot es pot definir com una variable aleatòria distribuïda de definir com una variable aleatòria distribuïda de forma uniforme dintre de l'interval de forma uniforme dintre de l'interval de quantificacióquantificació..

1/q

q/2-q/2

( )12

22

2

22 qdeepe

q

qe == ∫

−

σ




•• El pas de El pas de quantificacióquantificació dependrà del Marge Dinàmic del dependrà del Marge Dinàmic del senyal i del nombre de bits amb els que es faci la senyal i del nombre de bits amb els que es faci la quantificacióquantificació..

•• La conclusió més rellevant és que per cada bit que afegim La conclusió més rellevant és que per cada bit que afegim millorem en 6dBs la relació senyal a soroll.millorem en 6dBs la relació senyal a soroll.

dBs02.62

NKSNR

MDq N

+=

=



Sense Q

Amb Q



QuantificacióQuantificació logarítmica.logarítmica.

•• Els senyals de veu poden arribar a tenir un marge Els senyals de veu poden arribar a tenir un marge dinàmic de 60 dinàmic de 60 dBsdBs..

•• Interessa que la resolució del Interessa que la resolució del quantificadorquantificador sigui sigui major en els nivells d’amplitud baixos i que no ho major en els nivells d’amplitud baixos i que no ho sigui tant en els més elevats, a fi de que l’error sigui tant en els més elevats, a fi de que l’error relatiu sigui més o menys constant.relatiu sigui més o menys constant.

•• El El quantificadorquantificador uniforme dona resultats òptims uniforme dona resultats òptims quan el senyal està uniformement distribuït.quan el senyal està uniformement distribuït.



•• Els senyals de veu, així com la majoria de senyals Els senyals de veu, així com la majoria de senyals analògics no presenten una distribució uniforme de les analògics no presenten una distribució uniforme de les seves amplituds.seves amplituds.

•• Tot i això, els Tot i això, els quantificadorsquantificadors no uniformes són difícils i no uniformes són difícils i cars d’implementar amb cars d’implementar amb hardwarehardware, de tal forma que caldrà , de tal forma que caldrà trobar alternativestrobar alternatives

h(x)

MD




•• Mitjançant el següent diagrama de blocs, el Mitjançant el següent diagrama de blocs, el sistema serà capaç de distribuir uniformement el sistema serà capaç de distribuir uniformement el senyal d’entrada i aplicar el senyal d’entrada i aplicar el quantificadorquantificadoruniforme.uniforme.


QuantificacióQuantificació logarítmica logarítmica

•• El compressor aplica una funció no lineal que El compressor aplica una funció no lineal que uniformitzauniformitza la distribució de valors del senyal de la distribució de valors del senyal de sortida.sortida.




•• Existeixen dos Existeixen dos estàndards de estàndards de compressió:compressió:•• Llei Llei µµ

•• EstEstààndard Americndard Americàà de de compressicompressióó per senyals per senyals de telefonia.de telefonia.

•• Aquest estAquest estààndard ndard pertany als laboratoris pertany als laboratoris Bell.Bell.



•• La segona llei correspon a l’estàndard Europeu.La segona llei correspon a l’estàndard Europeu.•• Llei A.Llei A.

•• És la aproximació logarítmica de la CCITT i és l’estàndard És la aproximació logarítmica de la CCITT i és l’estàndard Europeu per Europeu per quantificacióquantificació logarítmicalogarítmica



Classificació dels Classificació dels codificadorscodificadors de de veuveu

Codificadors de veu

De forma d’ona VOCODERS Híbrids-Reprodueixen el senyal sense tenir en compte la seva naturalesa.

-Domini del temps:

-PCM,DPM,ADPCM

-Domini de la freqüència

-Blocs, subbandes

-Alta qualitat a data-ratesmitjos 32kBs.

-Aprofiten els avantatges dels dos altres mètodes de codificació mirant d’aconseguir un baix bit-rate i una alta qualitat

-Aprofiten les característiques del senyal de veu per augmentar la compressió del senyal.

-Assoleixen data-ratesbaixos però la veu resultant resulta massa sintètica.


PCMPCM

•• El El codificadorcodificador PCM és el més senzill que podem trobar per PCM és el més senzill que podem trobar per codificar veu en format digital.codificar veu en format digital.

•• El procés de codificació es fa en tres etapes.El procés de codificació es fa en tres etapes.•• MostratgeMostratge..•• QuantificacióQuantificació..•• Codificació.Codificació.

•• Els senyals de veu normalment presenten una elevada Els senyals de veu normalment presenten una elevada correlació entre les seves mostres, factor que provoca que correlació entre les seves mostres, factor que provoca que una PCM no estigui codificant de forma eficient.una PCM no estigui codificant de forma eficient.•• La solució passarà per esquemes de codificació que aprofitin la La solució passarà per esquemes de codificació que aprofitin la

redundància del senyal per reduir el redundància del senyal per reduir el datadata--raterate..•• DPCM, ADPCM.DPCM, ADPCM.



DPCM.DPCM.

•• La correlació entre mostres successives del La correlació entre mostres successives del senyal de veu es pot utilitzar per aplicar un senyal de veu es pot utilitzar per aplicar un predictorpredictor lineal de senyal.lineal de senyal.

•• La codificació del senyal residu o error La codificació del senyal residu o error presentarà certes avantatges respecte al presentarà certes avantatges respecte al mètode PCM.mètode PCM.•• El marge dinàmic serà molt inferior al del El marge dinàmic serà molt inferior al del

senyal originalsenyal original•• Codificar per la mateixa SNR amb un nombre Codificar per la mateixa SNR amb un nombre

inferior de bits.inferior de bits.•• Mantenir el nombre de bits i augmentar així la Mantenir el nombre de bits i augmentar així la

relació SNRrelació SNR


DPCMDPCM

[ ]nd~

[ ]nx̂

[ ]nd

[ ]nx~

[ ] [ ] [ ]ndnxnx ~ˆ~ +=



DPCMDPCM

•• Disseny del sistema de Disseny del sistema de predicciópredicció

[ ][ ] [ ] [ ] [ ] [ ] [ ]

[ ] [ ] [ ] [ ]

[ ] [ ] [ ]

[ ] [ ] [ ][ ] [ ]

[ ] [ ]

−−

=

−−−

−−−−−

=

0

0110

][

1111

**

**

***

xxxx

xxxx

xxxxxx

H

rNr

rrNrrr

NnxNnxnxNnx

nxnxnxnxNnxnxnxnxnxnx

ExxE

L

OM

M

L

LL

MOOM

MO

L

rr

yxxxopt rRh 1−=r

[ ][ ] [ ]

[ ] [ ]

[ ] [ ]

( ) ( )( )

( )

+

+=

=

−

−=

Nkr

krkr

Nr

rr

Nnxny

nxnynxny

ExyE

xx

xx

xx

yx

yx

yx

*

*

*

*

*

*

*

*

*

1

)(

)1(0

1MM

r


ADPCMADPCM

•• En el sistema DPCM, tant el En el sistema DPCM, tant el predictorpredictor com el com el quantificadorquantificador estan sempre a un valor prefixat.estan sempre a un valor prefixat.

•• Una adaptació a les característiques particulars de Una adaptació a les característiques particulars de cada persona.cada persona.

Adaptació del quantificador

Adaptació del predictor.



Modulació Modulació ∆∆..

•• Existeixen vàries perspectives per analitzar les Existeixen vàries perspectives per analitzar les característiques de la modulació delta.característiques de la modulació delta.

•• En aquest anàlisi considerarem que es tracta d’una En aquest anàlisi considerarem que es tracta d’una modulació DPCM amb un modulació DPCM amb un quantificadorquantificador d’und’un bit.bit.

•• Analitzant el comportament d’un Analitzant el comportament d’un predictorpredictor d’und’unbit es pot demostrar que la potència de l’error de bit es pot demostrar que la potència de l’error de predicció disminueix molt quan el coeficient de predicció disminueix molt quan el coeficient de correlació normalitzat tendeix a 1.correlació normalitzat tendeix a 1.


•• Podrem aconseguir un coeficient de correlació Podrem aconseguir un coeficient de correlació molt elevat si molt elevat si sobremostrejemsobremostrejem..

•• Triant una velocitat de Triant una velocitat de mostratgemostratge molt superior al molt superior al límit de límit de NyquistNyquist aconseguirem que el senyal aconseguirem que el senyal estigui altament estigui altament correlatcorrelat..

•• PexPex. . •• Un senyal de 20KHz d’amplada de banda es Un senyal de 20KHz d’amplada de banda es

mostrejariamostrejaria a 48KHz.a 48KHz.•• Si agaféssim una velocitat 64 vegades superiors Si agaféssim una velocitat 64 vegades superiors fariemfariem

es podria es podria mostrejarmostrejar a 3.072 MHz.a 3.072 MHz.





•• Esquema de la modulació Delta.Esquema de la modulació Delta.



•• Limitacions de la modulació Limitacions de la modulació ∆∆..•• SobrependentSobrependent..

•• LL’’error per sobrependent apareix quan la modulacierror per sobrependent apareix quan la modulacióó no tno téé temps temps de seguir lde seguir l’’evolucievolucióó mméés rs rààpida que pugui presentar el senyal pida que pugui presentar el senyal dd’’entrada.entrada.

•• PerPer garantir garantir aixòaixò hauremhaurem de de fixarfixar

•• Error granular.Error granular.•• La La potpotèènciancia del error granular es del error granular es potpot aproximar aproximar segonssegons un un sorollsoroll

blancblanc gaussigaussiàà de de potpotèènciancia

•• AquestAquest sorollsoroll es es potpot considerar considerar plapla entre [entre [––fs fs]fs fs]

( )( ) ( )

ss f

AAf

tAdt

tdxtAtx

00

00

0

que forma talde

cos

sin)(

ωω

ωω

ω

≥∆=∆

=

=

( )312

2 222 ∆=∆=nσ



Codificació de bloc.Codificació de bloc.

•• En aquest apartat s’estudiaran les tècniques de En aquest apartat s’estudiaran les tècniques de codificació de bloc. codificació de bloc.

•• Aquests mètodes també es coneixen com Aquests mètodes també es coneixen com codificadorscodificadors en el domini de la freqüència, ja que en el domini de la freqüència, ja que en molts casos estan relacionats amb en molts casos estan relacionats amb transformades transformades freqüencialsfreqüencials..

•• En En promigpromig, els , els codicadorscodicadors de bloc poden codificar de bloc poden codificar senyals amb una qualitat equivalent a 8 bits senyals amb una qualitat equivalent a 8 bits escalar en un escalar en un promigpromig de 1 o 2 bits/mostra.de 1 o 2 bits/mostra.


•• Les tècniques de codificació acostumen a Les tècniques de codificació acostumen a mapejarmapejarels vectors d’entrada sobre un nou sistema de els vectors d’entrada sobre un nou sistema de coordenades que es pugui codificar en menys bits.coordenades que es pugui codificar en menys bits.

•• El El mapeigmapeig pot ser un procés reversible o pot ser un procés reversible o irreversible en funció de si es irreversible en funció de si es mapejamapeja sobre tot sobre tot l’espai o l’espai o nomèsnomès sobre un sobre un subespaisubespai..

•• Els mètodes de Els mètodes de mapeigmapeig s’acostumen a classificar s’acostumen a classificar segonssegons•• QuantificadorsQuantificadors vectorials.vectorials.•• Transformades ortogonals.Transformades ortogonals.•• CodificadorsCodificadors per per subbandessubbandes..

Codificació de bloc.Codificació de bloc.



QuantificadorQuantificador vectorial.vectorial.

•• La La quantificacióquantificació vectorial és l’extensió natural de vectorial és l’extensió natural de la la quanficacióquanficació escalar a N dimensions.escalar a N dimensions.

•• En la En la quantificacióquantificació escalar escollim n possibles escalar escollim n possibles valors dintre de la recta real.valors dintre de la recta real.

•• A la A la quantificacióquantificació vectorial escollirem N possibles vectorial escollirem N possibles vectors dintre de l’espai N dimensional sobre el vectors dintre de l’espai N dimensional sobre el que es treballa.que es treballa.•• La La quantificacióquantificació es realitzarà representant les dades es realitzarà representant les dades

d’entrada amb el vector que millor s’ajusti segons un d’entrada amb el vector que millor s’ajusti segons un criteri de fidelitat establert.criteri de fidelitat establert.


•• La descripció del La descripció del quantificadorquantificador vectorial es vectorial es realitza en base a dos criteris.realitza en base a dos criteris.•• El disseny del conjunt de codis que El disseny del conjunt de codis que

representaran a les dades d’entrada.representaran a les dades d’entrada.•• El El procèsprocès de cerca del vector que millor de cerca del vector que millor

representa a les dades d’entrada.representa a les dades d’entrada.




•• El mètodes més coneguts per a realitzar la El mètodes més coneguts per a realitzar la cerca dintre del diccionari de codis són:cerca dintre del diccionari de codis són:•• CodebookCodebook..

•• Es realitza una cerca exhaustiva avaluant tots els Es realitza una cerca exhaustiva avaluant tots els vector possibles i seleccionant el de mínima vector possibles i seleccionant el de mínima distància.distància.

•• TreeTree andand TrellisTrellis CodersCoders..•• El procés de cerca no es fa de forma directa sinó que El procés de cerca no es fa de forma directa sinó que

es resol seguint una estructura en arbre dissenyada es resol seguint una estructura en arbre dissenyada de forma apropiada per guiar el procés de cerca i de forma apropiada per guiar el procés de cerca i reduir el cost reduir el cost computacionalcomputacional..



QuantificadorQuantificador vectorial.vectorial.•• Disseny de la població del codi.Disseny de la població del codi.

•• DeterminísticsDeterminístics..•• Basats en el coneixement a Basats en el coneixement a

priori que podem tenir del priori que podem tenir del senyals a codificar.senyals a codificar.

•• EstocàsticsEstocàstics..•• S’assumeix una determinada S’assumeix una determinada

pdfpdf multidimensionalmultidimensional del del senyal d’entrada i es realitzen senyal d’entrada i es realitzen les particions de l’espai en les particions de l’espai en base a aquesta distribució.base a aquesta distribució.

•• Iteratius.Iteratius.•• Dissenyen de forma iterativa Dissenyen de forma iterativa

les particions basantles particions basant--se en un se en un entrenament exhaustiu amb entrenament exhaustiu amb un gran volum de dades.un gran volum de dades.



Codificació per mètodes Codificació per mètodes transformatstransformats

•• Un Un codificadorcodificador per mètodes transformats implica els per mètodes transformats implica els següents processos.següents processos.•• Aplicar sobre el vector d’entrada una transformació invertible.Aplicar sobre el vector d’entrada una transformació invertible.•• Realitzar la Realitzar la quantitzacióquantització del vector transformat.del vector transformat.•• Transmissió i recepció dels coeficients.Transmissió i recepció dels coeficients.•• Es realitza la transformació inversa amb els coeficients Es realitza la transformació inversa amb els coeficients quantitzatsquantitzats..

•• La transformació no modifica la informació, simplement la La transformació no modifica la informació, simplement la representa de forma més convenient per facilitar el procés representa de forma més convenient per facilitar el procés de codificació.de codificació.

•• La codificació de font es fa quan s’assignen un nombre La codificació de font es fa quan s’assignen un nombre determinat de bits als diferents coeficients del vector determinat de bits als diferents coeficients del vector transformat.transformat.•• Els coeficients es poden codificar de forma diferent en funció dEls coeficients es poden codificar de forma diferent en funció de e

l’impacte l’impacte perceptualperceptual que aquests tinguin sobre el receptor.que aquests tinguin sobre el receptor.



•• Seguidament es mostra l’esquema de codificació Seguidament es mostra l’esquema de codificació per mètodes transformats.per mètodes transformats.

•• La transformació pot ser independent del vector La transformació pot ser independent del vector d’entrada o pot ser depenent de les dades.d’entrada o pot ser depenent de les dades.



•• Transformacions independents de les dades:Transformacions independents de les dades:•• DFT.DFT.•• DCT (DCT (DiscreteDiscrete CosineCosine TransformTransform))•• DWHT (DWHT (DiscreteDiscrete WalshWalsh--HadamarHadamar TransformTransform))

•• Transformacions Transformacions depenentsdepenents de les dades:de les dades:•• DKLT (DKLT (DiscreteDiscrete KarhunenKarhunen--LoeweLoewe TransformTransform) )

o PCTo PCT



SubbandSubband CodingCoding..

•• A les tècniques de codificació per A les tècniques de codificació per subbandessubbandes, el senyal , el senyal d’entrada es divideix en diferents d’entrada es divideix en diferents subespaissubespais freqüencialsfreqüencials..

•• Aquesta divisió és pot fer en funció de les característiques Aquesta divisió és pot fer en funció de les característiques del senyal, del model del senyal, del model perceptualperceptual visual o auditiu, visual o auditiu, etcetc......

•• Les amplades de banda de cada filtre, les freqüències de Les amplades de banda de cada filtre, les freqüències de mostratgemostratge, així com la , així com la quantificacióquantificació poden variar en funció poden variar en funció de les aplicacions.de les aplicacions.

Documents

T.cniques de codificaci. de font3 - La Salleweb.salleurl.edu/~moran/Assets/Cod_font.pdf · • La codificació de fonts analògiques ha estat àmpliament lligades a la codificació