Förlustfri ljudkomprimering

Ljud är en enkel våg, och digitaliserat ljud  är en digital representation av den vågen. Detta uppnås genom att memorera nivån på den analoga signalen många gånger inom en sekund. Till exempel, på en vanlig CD lagras signalen 44100 gånger per sekund. Eftersom CD:n fungerar i stereo lagrar vi signalen för vänster och höger högtalare parallellt. 16-bitars nummer används för varje prov. Därför är det lätt att räkna ut att en sekunds ljud tar 2 × 2 × 44100 = 176 400 byte.

Förlustfri ljudkomprimering  är en uppsättning transformationer som gör att du effektivt kan komprimera ljuddata med möjlighet till fullständig återställning. Liksom all förlustfri komprimering utnyttjar ljuddatakomprimering vissa funktioner hos datan. I det här fallet är det:

Koordinattransformation ( L , R ) → ( X , Y )

Det första steget i komprimering är att representera L- och R -ljudkanalerna på ett mer effektivt sätt genom att representera dem med några siffror X , Y enligt följande algoritm:


För bråktal förlorar inte denna omvandling information och är likvärdig med den ursprungliga. För heltal förlorar den 0,5 när den konverteras till när L och R har olika paritet, men efter att ha kontrollerat pariteten kan vi enkelt fylla på dessa 0,5. integer

Predictor

Nästa steg är att köra X och Y genom en algoritm som så effektivt som möjligt tar bort all överflödig information i representationen av X, Y.

I det här fallet är hela processen inriktad på att representera arrayer X, Y med minsta möjliga antal, samtidigt som processens reversibilitet bibehålls. Det finns många sätt att göra detta. En av dem är en transformation med linjär algebra:

PX = (2 * X −1 ) − X −2
PY = (2 * Y −1 ) − Y −2

Om X = (2, 8, 24, ?), då P4 = ( 2 * X 4-1 ) − X 4-2 = (2 * 24) − 8 = 40
Det vill säga om X = (2,8,24,27,25,28,21,17), då PX = ( 2,8,14,40 ,30,...)

Observera att X och Y är sådana att det över hela spektrumet under en given sekund i genomsnitt inte bör ske stora förändringar i värden mellan intilliggande frekvenser, vilket gör kodningen lättare.

Samtidigt är det värt att komma ihåg att bra algoritmer organiserar behandlingen av inkommande data på ett sådant sätt att siffrorna i PX, PY-matrisen minskas.

Låt talet m ligga i intervallet 0 ... 1024. För arrayen PX utförs en serie transformationer med olika värden på m enligt följande:

X = (2, 8, 24, ?), då resp. ,
PX = (2 * X −1 ) − X −2 = (2 * 24) − 8 = 40

Om ? = 45 och m = 512, sedan slutvärde =

Iterera sedan över andra värden på m , eftersom större värden kan vara mer effektiva.

Sedan, efter att ha mottagit en array av data för en viss m , ökar eller minskar m beroende på om det senaste försöket i algoritmen lyckades.

Genom att använda olika ekvationer och använda flera pass för olika fria koefficienter kan ganska märkbar datakomprimering uppnås.

Vi ger ett exempel på flera ekvationer, enligt den tekniska litteraturen

P0 = 0
P1 = X −1
P2 = (2 * X −1 ) − X −2
P3 = (3 * X −1 ) − (3 * X −2 ) + X −3

Kodning. Rice's algoritm

Tanken med ljudkomprimering är att representera siffrorna som motsvarar strömmen på minsta möjliga sätt, efter att tidigare ha tagit bort all datakorrelation. Efter det kan du skriva den kodade dataströmmen till disken. Ett av de mest effektiva sätten är Rice-kodning .

Mindre tal är att föredra eftersom deras binära representation är kortare. Till exempel måste du koda följande rad:

Bas 10: 10, 14, 15, 46

Eller samma serie i binär form

Grund till bas 2: 1010, 1110, 1111, 101110

Om du nu vill representera detta som en sträng, där 32 bitar är reserverade för varje nummer (omfånget av alla möjliga värden), så kommer detta att vara ineffektivt, eftersom 128 bitar kommer att behövas. Det finns dock en mer effektiv metod. Den bästa lösningen skulle vara att helt enkelt skriva de binära talen 1010, 1110, 1111, 101110 utan kommatecken och få ett tal som 1010111011111101110 . Problemet är att efter det finns inget sätt att veta gränserna för varje nummer. Som regel används Rice-algoritmen som en lösning på ett sådant problem.

Riskodning är ett sätt att representera små tal på en rad samtidigt som man fortfarande kan skilja mellan dem. Obs: Algoritmen är effektivare, ju mindre antal, så du måste ta hand om detta först

Vid något steg av kodningen representeras data som ett tal n . Kodad, den läggs till till höger om strängen av redan kodade nummer på ett sådant sätt att den omvända processen är möjlig.

Grundidén är att representera talet n som , så att 0 <= r < 2^k.

Eftersom det finns ett supersnabbt talrotationskommando i maskinspråk, motsvarande att dividera ett tal med en potens av två, räcker det med att använda k=log n/log 2 , avrundat uppåt till det minsta heltal. Således är villkoren för k garanterade att vara uppfyllda i algoritmen . Baserat på formeln är det nödvändigt att bestämma antalet och resten : . Till exempel,

n = 46 (decimal) = 101110 (binär)
k = 4 (valbar)

Sedan (1110 i binär). .

Därefter konstrueras ett kodat nummer enligt följande schema. Nollor kommer först, i q- bitar [00]. Sedan läggs en markeringsbit [1] till till höger om nollorna för att veta när nollorna slutar. Och efter dem läggs resten r [1110] till, med en längd på k bitar.

Det vill säga att siffran 46 i kodad form ser ut som [00][1][1110] = 0011110

Nu, givet vissheten om k , som kodade numret, kan du enkelt dekryptera det:

(antal nollor) * 2 4 + (k bitar efter markbiten) = 2*2 4 +14 = 46

Nästa nummer börjar omedelbart på nästa bit.

Om datan kodas med ett för stort nummer k , till exempel k=32 , så blir metoden den metod som beskrivs i början av avsnittet, där varje nummer motsvarar 32 bitar, bara det föregås av en värdelös markeringsbit. I fallet med litet k ökar antalet nollor exponentiellt - för k=0 . För att representera talet 46 behöver du 46 nollor och 1 markeringsbit. Det bästa alternativet, med tanke på att kalibreringsförändringarna i serien är minimala, är att koda med medelvärdet för k , till exempel för att koda det hundrade talet, k beräknas som medelstorleken på siffror i arrayen under index 0... 99 .

Till exempel, för en 16-bitars representation av avläsningar, kommer talet 46 att representeras av följande binära kod: 0000000000101110. Efter omkodning kommer samma nummer endast att innehålla 7 siffror: 0011110.

Det optimala k kan också beräknas experimentellt: till exempel fungerar valfritt k mellan 16...128 bra. I alla fall, om det ungefärliga intervallet för kodade värden är känt, då är det optimala värdet för k = log n / log 2 .

Se även