PCM A-law and u-law Companding Algorithms in ANSI C

The Pulse Code Modulation (PCM), also known as G.711, is a very commonly used waveform codec, especially for audio companding in telephony. PCM is based on an non-uniform 8 bits quantization who is used for representing each sample took from an continuous (analog) signal.

Currently, there two slightly different versions of G.711:

• µ-Law (used in North America and Japan)
• Advantage: Provides a larger range for signals
• Disadvantage: It's not as a good as the A-Law when it comes to low-amplitude signals 
• A-Law (used in Europe and the rest of the world)
• Advantage: It's good for low-amplitude signals
• Disadvantage : It has a significantly smaller range than the µ-Law

The term companding was formed from the words compressing and expanding, and it refers to the process in which a signal is compressed (the range of the signal is reduced) and then expanded (the signal returns to a form similar to form before he was compressed).

If you want to know more about G.711 and the mathematics behind it, you should read:

A-Law and U-Law Companding

A-Law and U-Law Companding Implementations Using the TMS320C54x

1. A-Law implementation

1.1. A-Law Compression (Encoding) Algorithm

int8_t ALaw_Encode(int16_t number)
{
   const uint16_t ALAW_MAX = 0xFFF;
   uint16_t mask = 0x800;
   uint8_t sign = 0;
   uint8_t position = 11;
   uint8_t lsb = 0;
   if (number < 0)
   {
      number = -number;
      sign = 0x80;
   }
   if (number > ALAW_MAX)
   {
      number = ALAW_MAX;
   }
   for (; ((number & mask) != mask && position >= 5); mask >>= 1, position--);
   lsb = (number >> ((position == 4) ? (1) : (position - 4))) & 0x0f;
   return (sign | ((position - 4) << 4) | lsb) ^ 0x55;
}

First, the number is verified is its negative. If the number is negative he will be made positive and the sign  variable (by default 0) will contain the value 0x80 (so when it's OR-ed to the coded result it will determine it's sign).

Since the A-Law algorithm considers numbers in the range 0x000 - 0xFFF (without considering the sign bit), if a number is bigger than 0xFFF, it will automatically made equal to 0xFFF in order to avoid further problems.

The first step in determining the coded value is finding the position of the first bit who has a 1 value (excluding the sign bit). The search is started from position 11 and is continued until a bit with the value 1 is find or until a position smaller than 5 is met.

If the position is smaller than 5 (there was no 1 bit found on the positions 11-5),  the least significant byte of the coded number is made equal the the bits 5,4,3,2 of the original number. Otherwise the least significant bit of the coded number is equal to the first four bits who come after the first 1 bit encountered.

In the end, the most significant byte of the coded number is computed according to the position of the first 1 bit (if not such this was found, then the position is considered).

Also, before returning the result, the even bits of the result will be complemented (by XOR-ing with 0x55).

1.2.A-Law Expanding (Decoding) Algorithm

/*
 * Description:
 *  Decodes an 8-bit unsigned integer using the A-Law.
 * Parameters:
 *  number - the number who will be decoded
 * Returns:
 *  The decoded number
 */
int16_t ALaw_Decode(int8_t number)
{
   uint8_t sign = 0x00;
   uint8_t position = 0;
   int16_t decoded = 0;
   number^=0x55;
   if(number&0x80)
   {
      number&=~(1<<7);
      sign = -1;
   }
   position = ((number & 0xF0) >>4) + 4;
   if(position!=4)
   {
      decoded = ((1<<position)|((number&0x0F)<<(position-4))
                |(1<<(position-5)));
   }
   else
   {
      decoded = (number<<1)|1;
   }
   return (sign==0)?(decoded):(-decoded);
}

The first thing the decoding algorithm does is to complement the even bits of the coded number (since they were complemented in the coding part, complementing them again would "bring them to normal").

The next step is to verify if the number is negative by checking if the 8th bit is set (if it's set, the number is negative). If the number is negative, the variable named sign (who is used like a flag/boolean) is set to -1 and the number is made positive by clearing the 8th bit.

As you probably observed, I used a more complicated algorithm for checking the negativity of the number - I had to do this because my compiler had (and perhaps your would've had) problems with 8 bit variables and a statement like number=-number raises some problems.

The next thing we need in order to decode the number is to determine the position we calculated in encoding algorithm. The position is calculated as the sum between the value represented by the most significant byte of the coded number and 4.

The final step consists in actually decoding the number. The number will have its first 1 bit at the position determined before, the next four bits will be equal to the least significant byte of the coded number and the next bit following them will be automatically set to 1. If the position determined is smaller than 5, the position bit will not be set automatically (but the last 1 bit will).

Before returning the number, if the number is negative he will have it sign added.

2.µ-Law Implementation

2.1. µ-Law Compression (Encoding) Algorithm

int8_t MuLaw_Encode(int16_t number)
{
   const uint16_t MULAW_MAX = 0x1FFF;
   const uint16_t MULAW_BIAS = 33;
   uint16_t mask = 0x1000;
   uint8_t sign = 0;
   uint8_t position = 12;
   uint8_t lsb = 0;
   if (number < 0)
   {
      number = -number;
      sign = 0x80;
   }
   number += MULAW_BIAS;
   if (number > MULAW_MAX)
   {
      number = MULAW_MAX;
   }
   for (; ((number & mask) != mask && position >= 5); mask >>= 1, position--)
        ;
   lsb = (number >> (position - 4)) & 0x0f;
   return (~(sign | ((position - 5) << 4) | lsb));
}

The µ-Law compression algorithm is very similar to the A-Law compression algorithm.The main difference is that the µ-Law uses 13 bits instead of 12 bits, so the position variable will be initialized with 12 instead of 11. In order to make sure that there will be no number without a 1 bit in the first 12-5 positions, a bias value is added to the number (in this case 33). So, since there is no special case (numbers who do not have a 1 bit in the first 12-5 positions), this makes the algorithm less complex by eliminating some condtions.

Also in the end all bits are complemented, not just the even ones.

2.1. µ-Law Expanding (Decoding) Algorithm

int16_t MuLaw_Decode(int8_t number)
{
   const uint16_t MULAW_BIAS = 33;
   uint8_t sign = 0, position = 0;
   int16_t decoded = 0;
   number = ~number;
   if (number & 0x80)
   {
      number &= ~(1 << 7);
      sign = -1;
   }
   position = ((number & 0xF0) >> 4) + 5;
   decoded = ((1 << position) | ((number & 0x0F) << (position - 4))
             | (1 << (position - 5))) - MULAW_BIAS;
   return (sign == 0) ? (decoded) : (-(decoded));
}

As well as the compression algorithm, the expanding algorithm is also very similar to the A-Law expanding algorithm. The differences are that in the beginning all bits are complemented (not only the even ones) and the position is calculated as the value of the coded number most significant byte plus 5 instead of 4 (since the µ-Law uses 13 bits). Also, before the number is returned, the bias is subtracted.

Download latest build here