Logged in as Guest   Thu, Mar. 18th, 2:49 AM.      
Visitor Map
Recent Entries:
My Dev Setup Lately
Three Ways To Randomize on the iPhone
How to Remove .svn Directories On a Mac
How To Detect The iPhone Simulator
iPhoneMom Likes Doodle Games!
Updates To the Doodle Games Line
Three Jacks Now Tweets
Second iPhone App Submitted For Approval!
Pinch Media Analytics for iPhone
New iPhone Game Coming Soon!

Archive:
January - 2010
November - 2009
October - 2009
September - 2009
August - 2009
July - 2009
June - 2009
April - 2009
March - 2009
January - 2009
May - 2008
April - 2008
March - 2008
October - 2007
August - 2007
July - 2007
June - 2007
May - 2007
April - 2007
December - 2006
November - 2006
September - 2006
August - 2006
July - 2006
March - 2006
February - 2006
January - 2006
December - 2005
November - 2005
October - 2005
September - 2005
August - 2005
July - 2005
June - 2005
May - 2005
April - 2005
February - 2005
January - 2005
December - 2004
November - 2004
October - 2004
September - 2004
August - 2004
July - 2004
June - 2004
May - 2004
April - 2004
March - 2004
        Mu-Law and A-Law Compression Tutorial


Overview: What are A-Law and Mu-Law compression? In the simplest terms, they are standard forms of audio compression for 16 bit sounds. Like most audio compression techniques, they are lossy, which means that when you expand them back from their compressed state, they will not be exactly the same as when you compressed them. The compression is always 2:1, meaning that audio compressed with either of these algorithms will always be exactly half of their original size.
Mu-Law and A-Law compression are both logarithmic forms of data compression, and are extremely similar, as you will see in a minute. One definition of Mu-Law is

          "...a form of logarithmic data compression
          for audio data. Due to the fact that we hear logarithmically,
          sound recorded at higher levels does not require the same
          resolution as low-level sound. This allows us to disregard
          the least significant bits in high-level data. This turns
          out to resemble a logarithmic transformation. The resulting
          compression forces a 16-bit number to be represented as an 8-bit
          number."
(www-s.ti.com/sc/psheets/spra267/spra267.pdf)

And from the comp.dsp newsgroup FAQ we also get this definition:

          Mu-law (also "u-law") encoding is a form of logarithmic
          quantization or companding. It's based on the observation that
          many signals are statistically more likely to be near a low
          signal level than a high signal level. Therefore, it makes
          more sense to have more quantization points near a low level
          than a high level. In a typical mu-law system, linear samples
          of 14 to 16 bits are companded to 8 bits. Most telephone
          quality codecs (including the Sparcstation's audio codec) use
          mu-law encoded samples.

In simpler terms, this means that sound is represented as a wave, and humans can only hear audio in the middle of the wave. We can remove data from the upper and lower frequencies of a sound, and humans will not be able to hear a significant difference. Both Mu-Law and A-Law take advantage of this, and are able to compress 16-bit audio in an manner acceptable to human ears. A-Law and Mu-Law compression appear to have been developed at around the same time, and basically only differ by the particular logarithmic function used to determine the translation. When we get to the work of implementing the algorithms, you will see that the differences are nominal. The main difference is that Mu-Law attempts to keep the top five bits of precision, and uses a logarithmic function to determine the bottom three bits, while A-Law compression keeps the top four bits and uses the logarithmic function to figure out the bottom four. Both of these algorithms are used as telecommunication standards, A-Law being used mainly in Europe, and Mu-Law being used in the United States.

DISCLAIMER:
Please understand that I am glossing over several of the details, but recognize that the entire purpose of this document is to make two extremely useful algorithms much more accessable to "average" programmers, like myself.


Mu-Law Compression:
As you read this explanation, remember that the purpose of the algorithm is to compress a 16-bit source sample down to an 8-bit sample. The crux of Mu-Law functionality is deciding which of the samples need to keep the most of their precision. Even the "most-important" sample will still lose precision. It simply becomes a matter of determining how much each sample loses, and minimizing the loss on samples deemed "more important".
To generate a compressed Mu-Law sample from an uncompressed sample, the following algorithm is applied to the 16-bit source sample.
(Please refer to the code listing for Mu-Law compression.)

First, the algorithm first stores off the sign. It then adds in a bias value which (due to wrapping) will cause high valued samples to lose precision. The top five most significant bits are pulled out of the sample (which has been previously biased). Then, the bottom three bits of the compressed byte are generated using a small look-up table, based on the biased value of the source sample. The 8-bit compressed sample is then finally created by logically OR'ing together the 5 most important bits, the 3 lower bits, and the sign when applicable. The bits are the logically NOT'ed, which I assume is for transmission reasons (although you might not transmit your sample.)


MuLaw Compresion Code:

const int cBias = 0x84;
const int cClip = 32635;

static char MuLawCompressTable[256] =
{
     0,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,
     4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
     5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
     5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
     6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
     6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
     6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
     6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
     7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
     7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
     7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
     7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
     7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
     7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
     7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
     7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7
};

unsigned char LinearToMuLawSample(short sample)
{
     int sign = (sample >> 8) & 0x80;
     if (sign)
          sample = (short)-sample;
     if (sample > cClip)
          sample = cClip;
     sample = (short)(sample + cBias);
     int exponent = (int)MuLawCompressTable[(sample>>7) & 0xFF];
     int mantissa = (sample >> (exponent+3)) & 0x0F;
     int compressedByte = ~ (sign | (exponent << 4) | mantissa);

     return (unsigned char)compressedByte;
}




A-Law Compression:

As mentioned earlier, A-Law compression is extremely similar to Mu-Law compression. As you will see, they differ primarily in the way that they keep precision. The following is a short synopsis of the encoding algorithm, and the code example follows the written explanation. First, the sign is stored off. Then the code branches. If the absolute value of the source sample is less than 256, the 16-bit sample is simply shifted down 4 bits and converted to an 8-bit value, thus losing the top 4 bits in the process. However, if it is more than 256, a logarithmic algorithm is applied to the sample to determine the precision to keep. In that case, the sample is shifted down to access the seven most significant bits of the sample. Those seven bits are then used to determine the precision of the bottom 4 bits. Finally, the top seven bits are shifted back up four bits to make room for the bottom 4 bits. The two are then logically OR'd together to create the eight bit compressed sample. The sign is then applied, and the entire compressed sample is logically XOR'd, again, I assume for transmission reasons.


A-Law Compression Code:

static char ALawCompressTable[128] =
{
     1,1,2,2,3,3,3,3,
     4,4,4,4,4,4,4,4,
     5,5,5,5,5,5,5,5,
     5,5,5,5,5,5,5,5,
     6,6,6,6,6,6,6,6,
     6,6,6,6,6,6,6,6,
     6,6,6,6,6,6,6,6,
     6,6,6,6,6,6,6,6,
     7,7,7,7,7,7,7,7,
     7,7,7,7,7,7,7,7,
     7,7,7,7,7,7,7,7,
     7,7,7,7,7,7,7,7,
     7,7,7,7,7,7,7,7,
     7,7,7,7,7,7,7,7,
     7,7,7,7,7,7,7,7,
     7,7,7,7,7,7,7,7
};

unsigned char LinearToALawSample(short sample)
{
     int sign;
     int exponent;
     int mantissa;
     unsigned char compressedByte;

     sign = ((~sample) >> 8) & 0x80;
     if (!sign)
          sample = (short)-sample;
     if (sample > cClip)
          sample = cClip;
     if (sample >= 256)
     {
          exponent = (int)ALawCompressTable[(sample >> 8) & 0x7F];
          mantissa = (sample >> (exponent + 3) ) & 0x0F;
          compressedByte = ((exponent << 4) | mantissa);
     }
     else
     {
          compressedByte = (unsigned char)(sample >> 4);
     }
     compressedByte ^= (sign ^ 0x55);
     return compressedByte;
}



Decompression:
Now, the most obvious way to decompress a compressed Mu-Law or A-Law sample would be to reverse the algorithm. But a more efficient method exists. Consider for a moment the fact that A-Law and Mu-Law both take a 16-bit value and crunch it down to an 8-bit value. The reverse of that is to take an 8-bit value and turn it into a sixteen bit value. In the graphics world, it is extremely common to represent 32 and 24 bit values with an eight bit index into a palette table. So, why not take a page from the world of graphics and use palettes for the Mu-Law and A-Law compression look up? Sounds good to me. In fact, these palettes will be smaller than their 24 and 32 bit cousins because we only need to represent 16 bit values, not 24 and 32. In a nutshell, we will create static lookup tables to do the reverse conversion from A-Law and Mu-Law. The two differing tables are presented below. To convert from your compressed sample back to the raw 16-bit sample, just use your compressed sample as the index into the table, and the corresponding value in the table is your decompressed 16-bit sample. Obviously, the downside is that this method requires the memory overhead for the tables, but each table is only 512 bytes. In this day and age, that's downright cheap for the absolute fastest decompression!


Decompression Code:

static short MuLawDecompressTable[256] =
{
     -32124,-31100,-30076,-29052,-28028,-27004,-25980,-24956,
     -23932,-22908,-21884,-20860,-19836,-18812,-17788,-16764,
     -15996,-15484,-14972,-14460,-13948,-13436,-12924,-12412,
     -11900,-11388,-10876,-10364, -9852, -9340, -8828, -8316,
      -7932, -7676, -7420, -7164, -6908, -6652, -6396, -6140,
      -5884, -5628, -5372, -5116, -4860, -4604, -4348, -4092,
      -3900, -3772, -3644, -3516, -3388, -3260, -3132, -3004,
      -2876, -2748, -2620, -2492, -2364, -2236, -2108, -1980,
      -1884, -1820, -1756, -1692, -1628, -1564, -1500, -1436,
      -1372, -1308, -1244, -1180, -1116, -1052,  -988,  -924,
       -876,  -844,  -812,  -780,  -748,  -716,  -684,  -652,
       -620,  -588,  -556,  -524,  -492,  -460,  -428,  -396,
       -372,  -356,  -340,  -324,  -308,  -292,  -276,  -260,
       -244,  -228,  -212,  -196,  -180,  -164,  -148,  -132,
       -120,  -112,  -104,   -96,   -88,   -80,   -72,   -64,
        -56,   -48,   -40,   -32,   -24,   -16,    -8,     0,
      32124, 31100, 30076, 29052, 28028, 27004, 25980, 24956,
      23932, 22908, 21884, 20860, 19836, 18812, 17788, 16764,
      15996, 15484, 14972, 14460, 13948, 13436, 12924, 12412,
      11900, 11388, 10876, 10364,  9852,  9340,  8828,  8316,
       7932,  7676,  7420,  7164,  6908,  6652,  6396,  6140,
       5884,  5628,  5372,  5116,  4860,  4604,  4348,  4092,
       3900,  3772,  3644,  3516,  3388,  3260,  3132,  3004,
       2876,  2748,  2620,  2492,  2364,  2236,  2108,  1980,
       1884,  1820,  1756,  1692,  1628,  1564,  1500,  1436,
       1372,  1308,  1244,  1180,  1116,  1052,   988,   924,
        876,   844,   812,   780,   748,   716,   684,   652,
        620,   588,   556,   524,   492,   460,   428,   396,
        372,   356,   340,   324,   308,   292,   276,   260,
        244,   228,   212,   196,   180,   164,   148,   132,
        120,   112,   104,    96,    88,    80,    72,    64,
         56,    48,    40,    32,    24,    16,     8,     0
};




static short ALawDecompressTable[256] =
{
     -5504, -5248, -6016, -5760, -4480, -4224, -4992, -4736,
     -7552, -7296, -8064, -7808, -6528, -6272, -7040, -6784,
     -2752, -2624, -3008, -2880, -2240, -2112, -2496, -2368,
     -3776, -3648, -4032, -3904, -3264, -3136, -3520, -3392,
     -22016,-20992,-24064,-23040,-17920,-16896,-19968,-18944,
     -30208,-29184,-32256,-31232,-26112,-25088,-28160,-27136,
     -11008,-10496,-12032,-11520,-8960, -8448, -9984, -9472,
     -15104,-14592,-16128,-15616,-13056,-12544,-14080,-13568,
     -344,  -328,  -376,  -360,  -280,  -264,  -312,  -296,
     -472,  -456,  -504,  -488,  -408,  -392,  -440,  -424,
     -88,   -72,   -120,  -104,  -24,   -8,    -56,   -40,
     -216,  -200,  -248,  -232,  -152,  -136,  -184,  -168,
     -1376, -1312, -1504, -1440, -1120, -1056, -1248, -1184,
     -1888, -1824, -2016, -1952, -1632, -1568, -1760, -1696,
     -688,  -656,  -752,  -720,  -560,  -528,  -624,  -592,
     -944,  -912,  -1008, -976,  -816,  -784,  -880,  -848,
      5504,  5248,  6016,  5760,  4480,  4224,  4992,  4736,
      7552,  7296,  8064,  7808,  6528,  6272,  7040,  6784,
      2752,  2624,  3008,  2880,  2240,  2112,  2496,  2368,
      3776,  3648,  4032,  3904,  3264,  3136,  3520,  3392,
      22016, 20992, 24064, 23040, 17920, 16896, 19968, 18944,
      30208, 29184, 32256, 31232, 26112, 25088, 28160, 27136,
      11008, 10496, 12032, 11520, 8960,  8448,  9984,  9472,
      15104, 14592, 16128, 15616, 13056, 12544, 14080, 13568,
      344,   328,   376,   360,   280,   264,   312,   296,
      472,   456,   504,   488,   408,   392,   440,   424,
      88,    72,   120,   104,    24,     8,    56,    40,
      216,   200,   248,   232,   152,   136,   184,   168,
      1376,  1312,  1504,  1440,  1120,  1056,  1248,  1184,
      1888,  1824,  2016,  1952,  1632,  1568,  1760,  1696,
      688,   656,   752,   720,   560,   528,   624,   592,
      944,   912,  1008,   976,   816,   784,   880,   848
};