愛悠閑 > Microsoft ADPCM 編碼解碼算法

Microsoft ADPCM 編碼解碼算法

標簽: microsoft,算法,struct,存儲,fp,byte  |  作者: killedtlx 相關  |  發布日期 : 2015-11-22  |  熱度 : 1649°

 

Microsoft ADPCM 編碼解碼算法

因為種種原因,最近需要把原始的wav文件壓縮成ADPCM格式。但是網上幾乎搜不到相關的中文資料。花了相當長的時間,七拼八湊的從一些文章中得到了些信息,終于搞定了它。為了方便遇到跟我一樣麻煩的人,我決定把它詳細的寫下來。 
1. 關于DPCM 
  DPCM是differential pulse code modulation的縮寫,也就是差分脈沖編碼調制的意思。他的主要思想是通過已知的數據預測下一個數據,然后傳遞預測值與實際值之間的差值。具體的細節可以在很多信號處理相關的書上找到。 
  一般的DPCM編碼器都是采用的線性預測。假設傳遞的數據是X1,X2,...Xn,而下一個數據,Xn+1還是未知。可以通過前面的X1,X2,...Xn的加權和來預測Xn+1,也就是 
  Xn+1 = ∑(Ai*Xi),其中i屬于1...n 
  為了簡化計算,大部分編碼的實現只取前兩項,也就是,Xn+1 = a*Xn + b*Xn-1, 現在,最主要的事情就是如何對a,b進行取值,才能使得Xn+1的誤差最小。
  如果假設 x~i 是預測值,xi是實際值,那么,∑(x~i-xi)^2 最小的時候,a,b就是最優的。設 F=∑(X~i-Xi)^2,因為 X~i = a*X~i-1 + b*X~i-2,可以得出,F是關于a,b的二元函數.也就是 F=f(a,b) 。可以分別對a和b求偏導數,求出它的極值點。 
  f<sub>a</sub>(a,b) = 0 ; 
  f<sub>b</sub>(a,b) = 0 ; 
  可以得到 
  
  a * ∑(Xi-1)^2  + b * ∑(Xi-1)*(Xi-2)  =   ∑Xi*Xi-1 
  a * ∑(Xi-1)*(Xi-2) + b * ∑(Xi-2)^2   =   ∑Xi*Xi-2 
  如果設 
   alpha  =  ∑(Xi-1)^2 
   beta   =  ∑(Xi-1)*(Xi-2) 
   gama   =  ∑(Xi-2)^2 
   m      =  ∑Xi*Xi-1 
   n      =  ∑Xi*Xi-2 
  上面的式子就可以寫成 
  
    a*alpha + b*beta  =  m 
    a*beta  + b*gama  =  n 
  算出alpha,beta,gama,m,n以后,a和b的值就可以計算出來了,實際上我們只需要一個循環遍歷前n個數就能把它們都求出來。 
2. ADPCM的思想 
  如果直接使用DPCM進行編碼的話,是得不到什么壓縮的效率的。緣故是,需要傳輸或保存的是預測值后的值與實際值之間的差值,這與原來的數據占用同樣的空間。 
  為了滿足我們原始的壓縮數據的動機,你可以對這些差值進行各種各樣的編碼。因為,大部分情況下,差值都是像1,1,1,2,3,5,5,5之類的數。可以對它們進行通常的游程編碼或者huffman編碼,運氣好的話能夠得到很大的壓縮比。 
  這樣做會有一個很大的弊端。因為有些數據可能之間的聯系會呈線性或者某種連續函數的性質。但是大部分情況下,數據的分布還是有一定的離散性的。當數據之間出現很大的跳躍的時候,這種方法就顯得很蒼白無力了。 
  我們可以這么做,每次對得到的差值用一個隨著差值大小變化的數來除。這樣就可以隨著差值的變化,不斷調整比例因子。這樣出現較大的跳躍時也能把我們要存儲的差值限定在一個較小的范圍之內。 
  如果你現在有些迷惑,沒事,我們換種方式來說明一下。 
  假設差值是 diff,也就是 diff = X~i - Xi,那么,diff就有可能變動很大,如果引入一個不斷變化的因子iDelta,那么,diff' = diff / iDelta,而對于iDelta,每當diff變大的時候,他就變大比較大,當diff變得比較小的時候,他就相應的減小。這樣,我們的diff'就能保持相對的穩定了。通過iDelta的引入,可以使得我們的DPCM編碼自動的適應數據間大幅度的跳躍。這就是自適應脈沖編碼調制,ADPCM的主要思想。 
  你現在可能會想,iDelta到底怎么變化,才能自動的匹配diff的變化? 一種可行的方法就是,把它定義為diff的一個函數,這個函數根據不同的diff的值的大小取不同大小的值。通常我們會做一個iDelta值的表,通過 diff作為索引,這樣,就可以根據不同的diff值,iDelta就可以作相應的變化了。 
3. WAV文件的格式 
   IMA-ADPCM壓縮的音頻文件并沒有一個統一的格式。我們現在只考慮微軟的自己的wav格式。apple公司的網站上有一篇寫得很不錯的technical note, 可以看后面的鏈接地址。 

    wav文件是微軟定義的一系列資源文件中的一個。這些文件通常是由一系列的chunk組成。所有的文件都以RIFF標記開頭,然后指出文件的大小。接著表明類型,比如WAVE,MIDI等.  一個wav文件的結構大致如下 
__________________________ 
| RIFF WAVE Chunk          | 
|   groupID  = 'RIFF'      | 
|   riffType = 'WAVE'      | 
|    __________________    | 
|   | Format Chunk     |   | 
|   | ckID = 'fmt '    |   | 
|   |__________________|   | 
|    __________________    | 
|   | Sound Data Chunk |   | 
|   | ckID = 'data'    |   | 
|   |__________________|   | 
|__________________________| 
  一般每一個chunk都有一個id和一個size來表明chunk的類型和大小,這樣就可以很容易的將chunk讀出。id一般是四個字節,用ASCII 碼的值來標記,比如data chunk的id就是'data',而format chunk的id就是'fmt '.要注意的是,size表明的大小是以字節為單位的,而且不包括id和size字段本身所占的空間。 
  原始的wave文件一般只有兩個chunk,也就是fmt和data,原則上,你可以添加任何的其他chunk,用來添加不同的信息.這也是wav文件出現很多變種的原因. 
  windows下一般有兩種格式的wav文件,一種是普通未壓縮的原始數據,另一種就是采用了ADPCM壓縮了的。無論哪一種,你都可以使用現存的播放器播放。 
  未壓縮的存儲格式比較簡單,只需要一個format c hunk來描述格式信息,然后再用一個data chunk來存儲數據。 
  現在的wave文件按規定都必須包括一個fact chunk,而且在fmt chunk里必須包含一個擴展了的format description,這通過一個WAVEFORMATEX的結構來描述,但是以WAVE_FORMAT_PCM為格式的文件并不需要這些額外的信息。 
  下面是WAVEFORMATEX的定義 
  
typedef struct waveformat_extended_tag { 
    WORD wFormatTag;       /* format type */ 
    WORD nChannels;        /* number of channels (i.e. mono, stereo...) */ 
    DWORD nSamplesPerSec;  /* sample rate */ 
    DWORD nAvgBytesPerSec; /* for buffer estimation */ 
    WORD nBlockAlign;      /* block size of data */ 
    WORD wBitsPerSample;   /* Number of bits per sample of mono data */ 
    WORD cbSize;           /* The count in bytes of the extra size */ 
} WAVEFORMATEX; 
  其中wFormatTag標明了文件的類型,這樣我們就可以判斷后面的數據是以什么方式來存儲和表示的了,比如,#define WAVE_FORMAT_PCM 0x0001 這樣,WAVE_FORMAT_PCM表示的就是普通的原始wav文件格式。再比如,#define WAVE_FORMAT_ADPCM 0x0002 我們就可以知道,wFormatTag的值為WAVE_FORMAT_ADPCM就是以ADPCM壓縮的格式了。具體的文件的類型有很多種,詳細的定義可以在mmreg.h頭文件里找到。 
  WAVEFORMATEX是所有的format所共有的一個頭部,不同格式會在后面添加自己的相關的數據段,添加的段的字節數可以通過cbSize來得到。 
  cbSize用來描述不同的格式后面添加的多余的字節數。比如WAVE_FORMAT_ADPCM格式的format的這個值就是32,表明還有32個字節在后面。 
  另外一些字段會在后面解釋。 
  fact chunk是一個值得注意的chunk,現在的wav文件,無論是否壓縮,都必須包含一個fact chunk,用來存儲文件文件相關的信息。但是現在它里面只定義了一個字段,用來指出文件里一個有多少個sample。 
  
4. WAVE_FORMAT_ADPCM 的wav文件格式 
  再回到我們前面討論的DPCM,對于預測后得到的差值diff,我們應該怎么處理它才能的比較好的壓縮比?比如我們的數據是3,3,4,7,9,2... 可以注意到,如果預測做的比較好的話,得到的差值可能會很小,甚至為0,假設我們的原始的音頻數據時16位的,那么,如果仍然使用16位來存儲這些數據,肯定是一種浪費。很直觀的,你會想到減少每一個diff的存儲空間,沒錯,這就是ADPCM格式壓縮的wav文件采用的方法。 

   在壓縮過的wav文件里,每一個diff使用4個bit來存儲的,被稱作一個nibble。這樣,我們將一個16bit的原始數據縮減到4bit,可以得到一個穩定的4:1的壓縮比。 
  因為我們采用的是預測編碼,這就需要選擇預測的系數a和b,我們在前面已經詳細的推導過了a和b的計算方法。現在,我們需要解決的是,一個wav文件,我們是對整個文件計算來得出合理的a和b嗎?顯然,對整個文件采用相同預測系數并不實際,首先是計算起來麻煩,再一個,一個wav文件太長,如果對整個文件采用相同的a和b起不到什么效果,對于局部的數據,偏差仍然會是很大,這就喪失了我們的初衷。 
  不妨這么考慮,我們將音頻數據分成不同的塊,分別對每一塊求不同的系數,來進行預測編碼,一般聲音都是連續的,在一個局部的小區域里變化很小,所以a和b就能很準確的預測出每一個值了。 
  在apple下系統下,每一個塊稱作一個packet,以64個sample為固定的大小。而在windows下被稱作一個block,他的大小是可變的,所包含的sample的個數由nSamplesPerBlock來指出,后面我們會看到. 在WAVEFORMATEX結構里的nBlockAlign描述了每一個block所占的字節數. 
不同的采樣率會有不同的大小,下面是blockAlign在不同采樣率大小下的值 
nSamplesPerSec x Channels       nBlockAlign 
                8k              256 
                11k             256 
                22k             512 
                44k             1024 
  這樣,我們可以把壓縮后的數據以block為單位存儲在data chunk里.但是,除了壓縮的數據以外,我們同樣還需要存儲當前塊的a和b系數的值. 
  下面是ADPCM格式的format chunk的具體定義 
  
typedef struct adpcmcoef_tag { 
    int iCoef1; 
    int iCoef2; 
>} ADPCMCOEFSET; 

typedef struct adpcmwaveformat_tag { 
    WAVEFORMATEX wfxx; 
    WORD wSamplesPerBlock; 
    WORD wNumCoef; 
    ADPCMCOEFSET aCoeff[wNumCoef]; 
} ADPCMWAVEFORMAT; 
  這下子就很清楚了,ADPCMCOEFSET里的兩個正是我們的系數a和b,ADPCMWAVEFORMAT擴展了WAVEFORMATEX的結構,添加了一些列自有的信息,wSamplesPerBlock表明了每一個block里含有多少個sample,而wNumCoef說明了后面的系數表的大小. 
  微軟定義了一個7個的標準的系數表,當然,你也可以在后面添加自己的系數,下面是他的定義: 
  Coef Set   Coef1   Coef2 
   0  256  0 
   1  512  -256 
   2  0  0 
   3  192  64 
   4  240  0 
   5  460  -208 
   6  392  -232 
  每一個coef是使用定點數來表示的,這樣是為了方便存儲和加快編解碼的速度,使用的時候需要把它除以256得到實際的值 
  可以通過我們前面的方法算出來a和b,然后再在這里找出和a和b最近的一組數. 因為通常情況下,音頻文件的數據量是相當大的,如果對每個樣本都算出最優的a和b,他們的存儲就會占相當大的空間, 如果我們只用這七個,可以把他們放在文件頭里的一個表里面,然后對每一個block只需要存儲他們最近的系數在表里的索引值就行了. ADPCMWAVEFORMAT里的aCoeff存儲的就是這個系數表. 
  ADPCM壓縮格式存儲的wav文件,一般包含三個chunk,一個是format chunk,就是我們上面的那個ADPCMWAVEFORMAT結構. 接著會有一個fact chunk,這是必不可少的,現在它里面只有一個字段,就是整個文件含有的sample的個數. 
  接下來是最重要的data chunk, 它里面存儲的就是我們的數據,里面是一個block接一個block存儲的。 
  一般block由三部分組成,分別是header,data,padding。 
  header的定義: 
typedef struct adpcmblockheader_tag { 
    BYTE bPredictor[nChannels]; 
    int iDelta[nChannels]; 
    int iSamp1[nChannels]; 
    int iSamp2[nChannels]; 
} ADPCMBLOCKHEADER; 
  
  bPredictor就是我們前面說過的系數表的索引值。如果文件的channel不止一個,那么不同的channel就挨個向后排。 
  channels       1         2 
             _________ _________ 
            | left    | right   | 
  stereo    |         |         | 
            |_________|_________| 

                 1         2         3 
             _________ _________ _________ 
            | left    | right   | center  | 
  3 channel |         |         |         | 
            |_________|_________|_________| 
                 1         2         3         4 
             _________ _________ _________ _________ 
            | front   | front   | rear    | rear    | 
  quad      | left    | right   | left    | right   | 
            |_________|_________|_________|_________| 
                 1         2         3         4 
             _________ _________ _________ _________ 
            | left    | center  | right   | surround| 
  4 channel |         |         |         |         | 
            |_________|_________|_________|_________| 
                 1         2         3         4         5         6 
             _________ _________ _________ _________ _________ _________ 
            | left    | left    | center  | right   | right   |surround | 
  6 channel | center  |         |         | center  |         |         | 
            |_________|_________|_________|_________|_________|_________| 

  ADPCMBLOCKHEADER結構里的iDelta是iDelta的初始值。iSample1和iSample2是用來預測后面數據的初始的兩個 sample value。需要注意的是,iSample1實際上是第二個sample的值,而iSample2則是第一個。這樣做是為了方便編解碼。 
  header后面緊接著就是數據了。data里面是4bit接4bit的sample數據。 
  如果存儲的數據沒有到整整一個block,那么就要在最后存一系列的0來使整體大小填滿整個block,這被叫做padding 
5. 編碼和解碼 
  首先要說明的是,我們通過預測之后的到的diff,需要再除上一個iDelta的比例因子,得到的值就是我們要存儲的結果。這個值一般被稱作 iErrorDelta,他一般是一個可正可負的有符號數。因為我們需要把這個iErrorDelta存儲到一個nibble里,需要對他作一定的裁剪,因為一個nibble是4bit的,如果用補碼表示,他的范圍從-8到7,很明顯,我們的iErrorDelta只要大于7或者小于-8就都得用7或-8 來表示,這樣就喪失了一些精度。不過這些損失是很少的,因為如果我們的預測和iDelta比較好的話,大部分的iErrorDelta都會落在-8到7之間。即使喪失一點點音質,人的耳朵基本上聽不出來,可以忽略它的影響。 
  每次產生新的iErrorDelta之后,都要根據iErrorDelta的值對iDelta的值進行更改。以使得iDelta能夠自動適應sample 的變化。因為一個iErrorDelta被限定到4bit,我們就完全可以做一個16項的表來表示它。下面的這個就是microsoft的標準的 adaptation table 
int AdaptationTable [] = { 
  230, 230, 230, 230, 307, 409, 512, 614, 
  768, 614, 512, 409, 307, 230, 230, 230 
} ; 
  好了,我們現在已經把一切前提工作都做完了,下面就是具體的編碼及解碼步驟了,因為編解碼對于每一個block都是相同的,我們僅僅使用一個block來說明。 

編碼: 
  對每一個block,編碼的過程是通過下面的幾個步驟進行的 
    
     確定需要使用的系數predictor 
     確定初始的iDelta值 
     輸出block header 
     編碼并輸出數據 
  其中predictor的確定已經在開頭部分詳細的描寫了。我們只要找出與a和b最相近的系數表的索引值就行了。 

   初始的idelta的值確定有很多種,你可以對每一個block都使用相同的iDelta值。也可以通過開始的幾個數據來估計iDelta,比如,通過算出第一個sample的預測值跟實際值之間的diff,可以使用diff/4來表示iDelta,這樣iErrorDelta的值就能剛好被限制在-8到 7的比較靠中間的位置 
  每一個block的初始iDelta的值也可以使用前一個block的最后一個iDelta的值來確定。不過需要注意,第一個block的初始iDelta的值需要單獨考慮。 
  當predictor和初始的iDelta確定之后,block header就可以寫出了。 
  
    首先將每一個channel的predictor輸出 
    再將每一個channel的iDelta輸出 
    接著將16bit的第二個sample的PCM值輸出(iSample1) 
    最后將16bit的第一個sample的PCM值輸出(iSample2) 
  下面就是對剩下的數據編碼了。 
   
     如果block里還有sample尚待編碼 
          // 通過前兩個sample預測下一個sample的值 
        lPredSamp = ((iSamp1 * iCoef1) + (iSamp2 *iCoef2)) / 256 
    
          // 計算iErrorDelta 
        iErrorDelta = (Sample(n) - lPredSamp) / iDelta 
        如果iErrorDelta大于7,把它設成7 
        如果iErrorDelta小于-8,把它設成-8 
        
        把iErrorDelta作為一個nibble輸出 
        
          //算出使用iDelta和iErrorDelta預測得到的新的sample的值 
        lNewSamp = lPredSample + iDelta * iErrorDelta 
        
        把lNewSamp限定到16bit所允許的大小 
          
          //調整iDelta的值 
        iDelta = iDelta * AdaptionTable[ iErrorDelta] / 256 
        把iDelta限定到16bit所允許大小的范圍內,并確保它不為0 
          //更新預測用的兩個sample的值 
        iSamp2 = iSamp1; 
        iSamp1 = lNewSample. 
     重復上面的過程,直到block里沒有需要再編碼的sample 
  
  解碼實際上就是上述過程的逆過程。如果你把上邊的編碼過程搞明白了,解碼的過程就很簡單,這里就不詳細說了。 
  上面就是它的整個過程,如果你還有什么不明白,可以給我發郵件: [email protected] 
  
  下面是相關的一些鏈接,可以參考一下。 
Understanding The Differences Between Apple And Windows IMA-ADPCM Compressed Sound Files: 
鏈接地址 
ADPCM reference implementation: 
鏈接地址 
這個描述的比較詳細一點: 
鏈接地址 
libsndfile:   鏈接地址 
SoX Sound eXchange:   http://sox.sourceforge.net 
WAVE File Format:     
鏈接地址 
鏈接地址 
后面附帶上我寫的一個對8000采樣率,單聲道16位的wav格式壓縮成ADPCM的代碼

 



快乐彩中奖说明