Category: Source Coding

Note: There is a rating embedded within this post, please visit this post to rate it.
In a given communication system, we always want to send data that represent real world data representing some physical quantity (be it speech, temperature, etc..,) .The real world physical quantity exist in analog domain and it becomes imperative to convert it to digital domain if we want to send it via a digital communication system. The above process of converting from analog to digital domain is done by an Analog to Digital Converter (ADC). A typical ADC contains the following components/blocks: 1) Sampler 2) Quantizer and 3) Encoder.

The Sampler converts the analog signal (manifestation of real world physical quantities) to sequence of discrete samples that are uniformly spaced in time. For more details on sampling process refer previous sections – 1) Sampling Theorem – Baseband Sampling and 2)Sampling Theorem – bandpass or under sampling .

The sampled signals from the sampling process are discrete in time but their amplitude is still continuous. In order to have a full representation of a signal in digital form, the signal has to be discrete in amplitude too. The amplitude of the sampled signal can take on values from infinite number of possible amplitude levels. This infinite number of possible amplitude has to be mapped to manageable amplitude levels by mapping different ranges of amplitude levels to a set a amplitude levels. This requires the next two blocks in ADC namely the quantizer and the encoder.

The quantizer discretizes the continuous amplitude of the sampled signal to discrete levels of amplitude. Several types of quantizers – uniform, non-uniform (A-law quantizer, law quantizer), differential quantizer, etc exist to fulfill the purpose.

The quantized signal has to be represented in some numeric form to get a digital representation. The encoder, the next block in the ADC, maps the discrete amplitude levels of the quantized samples to codewords. Codewords are just some form of numeric representation that the encoder assigns to each discretized amplitude level. Some of the convenient methods for one-to-one mapping of amplitude levels to codewords include: 1) Natural Binary Coding and 2) Gray coding. In natural binary mapping the discrete amplitude levels are coded in binary format.

Natural Binary Coding:

Consider that the sampler has discretized the samples in time and the quantizer maps discretized ranges of voltages to discrete amplitude levels. The first column in the following tables gives the encoder output in binary. The second column gives possible interpretations. Four commonly known interpretations exists namely – unsigned, signed magnitude, 1’s complement and 2’s complement form. The encoder just spits out the binary pattern and it is up to the designer to decide how to interpret the binary pattern in order to represent quantization values. The interpretation influences the quantizer ranges that will be mapped to specific values. Quantizer design and encoder’s output interpretation always goes hand in hand.

Out of the four common interpretations listed above, unsigned integer representation can represent positive values only. The other three representations can accommodate both positive and negative values.

In signed magnitude representation, also called Folded Binary Code / Foldover Binary Code, the Most Significant Bit (MSB) of the binary pattern represents the sign of the number (positive/negative) and the rest of the bits represent the magnitude. In 1’s complement representation, the negative values are just the 1’s complement of positive values. To convert a binary representation to 1’s complement, one just has to flip all the bits (1’s to 0’s and 0’s to 1’s). To convert to 2’s complement form, convert the binary pattern to 1’s complement and then add ‘1’ to the resulting sum.

The designer can conveniently choose any of the above mentioned forms to interpret the binary output of the encoder. For example, if the designer interprets it as 1’s complement or signed magnitude representation, then he would end-up in having two different representations for the value ‘0’. All the further calculations in DSP has to done by keeping this fact in mind and this poses greater threat to the reliability of design. To avoid this ambiguity, 2’s complement is always the choice of interpretation. Additionally two’s complement interpretation results in faster and simpler hardware. Also it can be noted that given the same number of bits (3 bits) to represent the binary output of the encoder, the two’s complement encoding can represent voltage ranges from -4.5V to +3.5V without any ambiguity. But in the case of signed magnitude and one’s complement encoding the range of representable voltage ranges shrinks to -3.5V to +3.5V but they also result in ambiguity in representing 0V.

Gray Coding:

Gray Coding is another form of representation that is used ubiquitously in all applications. In Gray coding, the adjacent representations (symbols) differ by only one bit. Gray coding, when combined with Forward Error Correction codes capable of corrective single bit errors, it can aid in correction of erroneous reception of bits that spills into adjacent symbols. Digital modulation techniques like M-PSK and M-QAM use Gray coding representation to represent the symbols that are modulated.

Converting from Natural Binary to Gray:

To convert a binary representation (X3 X2 X1 X0) to Gray code (Y3 Y2 Y1 Y0), following method can be used.

$$\begin{matrix}Y_3 = X_3 \;\;\;\;\;\;\;\;\;\\
Y_2 = X_3 \bigoplus X_2 \\
Y_1 = X_2 \bigoplus X_1\\
Y_0 = X_1 \bigoplus X_0 \\ \end{matrix} $$

That is, the MSB (Y3) is same for both binary and Gray codes. The next bit (Y2) is the XOR of previous bit (X3) and the present bit (X2) of the binary code and so on. Following example illustrates this concept using a 6-bit code.

Converting from Gray to Natural Binary:

To convert a Gray code representation (Y3 Y2 Y1 Y0) to binary code (X3 X2 X1 X0), following method can be used.

$$ \begin{matrix}
X_3 = Y_3 \;\;\;\;\;\;\;\;\;\\
X_2 = Y_2 \bigoplus X_3 \\
X_1 = Y_1 \bigoplus X_2\\
X_0 = Y_0 \bigoplus X_1 \\
\end{matrix} $$

That is, the MSB (X3) of binary code is same as that of gray code. The next bit (X2) is the XOR of previous result (X3) and the present bit (Y2) of the gray code and so on. Following example illustrates this concept using 6-bit code.

The following table illustrates the conversion for a three bit system.

Matlab Code:

Matlab Code to convert decimal values directly to Gray

function [grayCoded]=dec2gray(decimalInput)
    [rows,cols]=size(decimalInput);
    grayCoded=zeros(rows,cols);
    for i=1:rows
        for j=1:cols
            grayCoded(i,j)=bitxor(bitshift(decimalInput(i,j),-1),decimalInput(i,j));
        end
    end
end

Matlab Code to convert Gray to decimal values

function [decimal]=gray2dec(grayInput)
    grayInput=uint8(grayInput); %Force datatype to uint8
    [rows,cols]=size(grayInput);
    decimal=zeros(rows,cols);
    for i=1:rows
        for j=1:cols
            temp = bitxor(grayInput(i,j),bitshift(grayInput(i,j),-8));
            temp = bitxor(temp,bitshift(temp,-4));
            temp = bitxor(temp,bitshift(temp,-2));
            temp = bitxor(temp,bitshift(temp,-1));
            decimal(i,j) = temp;
        end
    end
end

Sample Run:

>> decimalInput=[0 1 2 3 4 5 6 7]
decimalInput = 0 1 2 3 4 5 6 7
>> graycoded=dec2gray(decimalInput)
graycoded = 0 1 3 2 6 7 5 4
>> graycoded=gray2dec(graycoded)
graycoded = 0 1 2 3 4 5 6 7

See also:

[1] Oversampling, ADC – DAC Conversion,pulse shaping and Matched Filter
[2] Bandpass Sampling
[3]Baseband or Intermediate Sampling