Convolutional Coding

Convolutional codes differ from block codes by means of method of operation. A convolutional encoder operates over serial data, whereas block codes operates over a block of input data. Also different is the utilization of memory elements in the convolutional encoders. In the case of block codes, there is no memory element involved in the generation of encoded data.

Convolutional codes are specified as (n,k,L) , where n is the number of output bits from the encoder, k is the number of input bits to the encoder and L is the constraint length of the encoder. Disparate expressions for constraint length are often found in different text books but the fundamental idea is same The constraint length is used to calculate the number of memory stages or flipflops used in the encoder. As long as we know L and the underlying formula we can calculate the number of memory stages (m). So it does not really matter which expression for L is used. The constraint length is expressed as

\(L = k(m+1)\)

In some text books it is expressed as L=k x (m) and in some other books it is even expressed as L=m+1.We will use the first expression throughout our discussion.

We will take up a simple convolutional code (2,1,3) where n=2, k=1 and L=3 ( the expression L=k(m+1) is used).Lets construct the encoder from the above information. The encoder is constructed with 1 input bit, 2 output bits and 2 memory elements. Note that the L=k(m+1) expression leads to 2 memory elements. Here these two memory elements are used to store the past 2 input bits. If the expression L=k*m is used and for a (2,1,3) encoder (L=3), the number of memory elements will be 3, where these 3 memory elements are used to store past 3 input bits . So the expression for constraint length has to be carefully interpreted, otherwise any misinterpretation will lead to a different encoder structure altogether.

Now we know the number of bits going into the encoder , number of bits coming out from it and the number of memory elements. Till now the encoder is like a black box to us in the sense that we don’t know how the memory elements are utilized to generate the output bits from the input. To fully understand the encoder structure we need something called “generator polynomials” that tell us how the memory elements are linked to achieve encoding. The generator polynomials for a specific convolutional encoder set (n,k,L) are usually found through simulation. The set (n,k,L) along with n generator polynomials completely describes a convolutional encoder.

For our (2,1,3) encoder , we use two generator polynomials, one for each output.

\(g_0=\left [1 0 1 \right ]\)

\(g_1=\left [1 1 1\right ]\)

Lets put everything to make the encoder structure.

Encoder Structure
Encoder Structure

Encoder structure,State Diagram and Trellis :

The convolutional encoder can also be represented using a finite state machine. The entire behavior of a convolutional encoder is depicted by a state diagram. The number of states in a state diagram depends on the number of memory elements in the encoder. If number of memory elements is m then the number of states in the state diagram will be 2m.For the (2,1,3) convolutional encoder the number of states will be 4 , i.e., the last two memory elements are used to store the past inputs I -1 and I -2. Transition between the states depends on the present input I 0.The solid line in the state diagram indicates the transitions due to the input I0 =0 and dotted lines are used to represent the transitions due to the input I0= 1. The output bits generated during each state transition is written in dark red color (along the transistion lines).

State diagrams can be easily constructed with the help of a state table as shown below.

State Table - (2,1,3) Convolutional Encoder

Input
Current State
Next State
Output
0
00
00
00
0
01
00
11
0
10
01
01
0
11
01
10
1
00
10
11
1
01
10
00
1
10
11
10
1
11
11
01

State Diagram for Convolutional Encoder
State Diagram for (2,1,3) Convolutional Encoder

A trellis diagram is constructed from the given state diagram. Trellis diagram helps us to understand the concept of Viterbi Decoding algorithm that is used to decode the convolutional encoded data.

Trellis Diagram - Single Stage Trellis Diagram depicting four stages

A single stage Trellis is illustrated for understanding. The four possible states of the encoder are depicted as four horizontal rows. Present states are considered to be on the left side and the possible next states on the right side of the trellis. The connections between the present states and the next states exactly follow the state diagram representation. Again, the output bits generated during each state transition are indicated in dark red color. A multiple stage Trellis is constructed by replicating the single stage and juxtaposing each of the single stage side by side as shown in the figure.

The concept of Viterbi Decoding will be discussed in the next article

Recommended Books

More Recommended Books at our Integrated Book Store

  • Abdulbagi Elsanousi

    https://uploads.disquscdn.com/images/926d49ba847b02577127e74910596261ba670be0e90bece052e2b43e6e766457.png
    Hello sir I’m looking for Matlab code for BER of an convolutionally coded OFDM system using different modulation schemes over an AWGN channel.
    could you help me

      • Abdulbagi Elsanousi

        hello sir this code for BER of convolution coded ofdm system using 16-QAM … i have tried to play on modulation section to change modulation from 16-qam to 8-qam but there was problem in interleaving part the length of data will change .. could u help me

        this is code
        % OFDM Code
        % Author: Ihsan Ullah,
        % Ms-55 Electrical,
        % College of EME,
        % NUST Pakistan
        % No.of Carriers: 64
        % coding used: Convolutional coding
        % Single frame size: 96 bits
        % Total no. of Frames: 100
        % Modulation: 16-QAM
        % No. of Pilots: 4
        % Cylic Extension: 25%(16)

        close all
        clear all
        clc

        %%
        % Generating and coding data
        t_data=randint(9600,1)’;
        x=1;
        si=1; %for BER rows
        %%
        for d=1:100;
        data=t_data(x:x+95);
        x=x+96;
        k=3;
        n=6;
        s1=size(data,2); % Size of input matrix
        j=s1/k;

        %%
        % Convolutionally encoding data
        constlen=7;
        codegen = [171 133]; % Polynomial
        trellis = poly2trellis(constlen, codegen);
        codedata = convenc(data, trellis);

        %%
        %Interleaving coded data

        s2=size(codedata,2);
        j=s2/4;
        matrix=reshape(codedata,j,4);

        intlvddata = matintrlv(matrix’,2,2)’; % Interleave.
        intlvddata=intlvddata’;

        %%
        % Binary to decimal conversion

        dec=bi2de(intlvddata’,’left-msb’);

        %%
        %16-QAM Modulation

        M=16;
        y = qammod(dec,M);
        % scatterplot(y);

        %%
        % Pilot insertion

        lendata=length(y);
        pilt=3+3j;
        nofpits=4;

        k=1;

        for i=(1:13:52)

        pilt_data1(i)=pilt;

        for j=(i+1:i+12);
        pilt_data1(j)=y(k);
        k=k+1;
        end
        end

        pilt_data1=pilt_data1′; % size of pilt_data =52
        pilt_data(1:52)=pilt_data1(1:52); % upsizing to 64
        pilt_data(13:64)=pilt_data1(1:52); % upsizing to 64

        for i=1:52

        pilt_data(i+6)=pilt_data1(i);

        end

        %%
        % IFFT

        ifft_sig=ifft(pilt_data’,64);

        %%
        % Adding Cyclic Extension

        cext_data=zeros(80,1);
        cext_data(1:16)=ifft_sig(49:64);
        for i=1:64

        cext_data(i+16)=ifft_sig(i);

        end

        %%
        % Channel

        % SNR

        o=1;
        for snr=0:2:50

        ofdm_sig=awgn(cext_data,snr,’measured’); % Adding white Gaussian Noise
        % figure;
        % index=1:80;
        % plot(index,cext_data,’b’,index,ofdm_sig,’r’); %plot both signals
        % legend(‘Original Signal to be Transmitted’,’Signal with AWGN’);

        %%
        % RECEIVER
        %%
        %Removing Cyclic Extension

        for i=1:64

        rxed_sig(i)=ofdm_sig(i+16);

        end

        %%
        % FFT

        ff_sig=fft(rxed_sig,64);

        %%
        % Pilot Synch%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

        for i=1:52

        synched_sig1(i)=ff_sig(i+6);

        end

        k=1;

        for i=(1:13:52)

        for j=(i+1:i+12);
        synched_sig(k)=synched_sig1(j);
        k=k+1;
        end
        end

        % scatterplot(synched_sig)

        %%
        % Demodulation
        dem_data= qamdemod(synched_sig,16);

        %%
        % Decimal to binary conversion

        bin=de2bi(dem_data’,’left-msb’);
        bin=bin’;

        %%
        % De-Interleaving

        deintlvddata = matdeintrlv(bin,2,2); % De-Interleave
        deintlvddata=deintlvddata’;
        deintlvddata=deintlvddata(:)’;

        %%
        %Decoding data
        n=6;
        k=3;
        decodedata =vitdec(deintlvddata,trellis,5,’trunc’,’hard’); % decoding datausing veterbi decoder
        rxed_data=decodedata;

        %%
        % Calculating BER
        rxed_data=rxed_data(:)’;
        errors=0;

        c=xor(data,rxed_data);
        errors=nnz(c);

        % for i=1:length(data)
        %
        %
        % if rxed_data(i)~=data(i);
        % errors=errors+1;
        %
        % end
        % end

        BER(si,o)=errors/length(data);
        o=o+1;

        end % SNR loop ends here
        si=si+1;
        end % main data loop

        %%
        % Time averaging for optimum results

        for col=1:25; %%%change if SNR loop Changed
        ber(1,col)=0;
        for row=1:100;

        ber(1,col)=ber(1,col)+BER(row,col);
        end
        end
        ber=ber./100;

        %%
        figure
        i=0:2:48;
        semilogy(i,ber);
        title(‘BER vs SNR’);
        ylabel(‘BER’);
        xlabel(‘SNR (dB)’);
        grid on

      • Abdulbagi Elsanousi

        sir could you send me ur email .. i need to contact u

  • Kumud Altmayer

    Mr. Mathuranathan,

    Can you please add an appendix in you book with sample Convolutional codes. I bought the book as well. Thank you!

  • Anna

    sir, i bought the book but i do not find code for convolutional encoding and decoding.. could you please send the code to my mail id.. It is so urgent.. It will be very much helpful if you send as soon as possible.

    • Hi Anna,

      The code for convolutional decoder is a bit complex and is not available in the ebook. Sorry if the book missed your expectation.

      However, if you have a communication toolbox, you can try this

      Encoding:

      t = poly2trellis([4 3],[4 5 17;7 4 2]); % Define trellis.
      code = convenc(ones(100,1),t); % Encode a string of ones.

      Decoding (Hard decision):
      tb = 2; % Traceback length for decoding
      decoded = vitdec(code,t,tb,’trunc’,’hard’); % Decode.

      • Anna

        Sir,if you could please say the error in the code given below it will be helpful.

        close all
        clear all
        clc

        nbitpersym = 52; % number of bits per OFDM symbol (same as the number of subcarriers for BPSK)
        nsym = 10^4; % number of symbols
        len_fft = 64; % fft size
        sub_car = 52; % number of data subcarriers
        EbNo = 0:2:12;
        Td =3.2*10e-6;%%data symbol duration
        Tcp =.8*10e-6;%%cyclic prefix duration= .25Td

        EsNo= EbNo + 10*log10(sub_car /len_fft)+ 10*log10(Td/(Td+Tcp)); % symbol to noise ratio

        snr=EsNo – 10*log10(sub_car/len_fft); % snr as to be used by awgn fn.

        M = modem.pskmod(2); % modulation object

        % Generating data

        t_data=randint(nbitpersym*nsym,1);
        t = poly2trellis([4 3],[4 5 17;7 4 2]); % Define trellis.
        enc = convenc(t_data,t); % Encode a string of ones.

        % modulating data

        mod_data = modulate(M,enc);

        % serial to parallel conversion

        par_data = reshape(mod_data,nbitpersym,nsym).’;

        % pilot insertion

        pilot_ins_data=[zeros(nsym,6) par_data(:,[1:nbitpersym/2]) zeros(nsym,1) par_data(:,[nbitpersym/2+1:nbitpersym]) zeros(nsym,5)] ;

        % fourier transform time doamain data and normalizing the data

        IFFT_data = (len_fft/sqrt(sub_car))*ifft(fftshift(pilot_ins_data.’)).’;

        % addition cyclic prefix

        cylic_add_data = [IFFT_data(:,[49:64]) IFFT_data].’;

        % parallel to serial coversion

        ser_data = reshape(cylic_add_data,80*nsym,1);

        % passing thru channel

        no_of_error=[];
        ratio=[];
        for ii=1:length(snr)

        chan_awgn = sqrt(80/52)*awgn(ser_data,snr(ii)); % awgn addition

        ser_to_para = reshape(chan_awgn,80,nsym).’; % serial to parallel coversion

        cyclic_pre_rem = ser_to_para(:,[17:80]); %cyclic prefix removal

        FFT_recdata =(sqrt(52)/64)*fftshift(fft(cyclic_pre_rem.’)).’; % freq domain transform

        rem_pilot = FFT_recdata (:,[6+[1:nbitpersym/2] 7+[nbitpersym/2+1:nbitpersym] ]); %pilot removal

        ser_data_1 = reshape(rem_pilot.’,nbitpersym*nsym,1); % serial coversion

        z=modem.pskdemod(2); %demodulation object

        demod_Data = demodulate(z,ser_data_1); %demodulating the data
        tb = 2; % Traceback length for decoding
        decoded = vitdec(code,ser_data,tb,’trunc’,’hard’); % Decode

        [no_of_error(ii),ratio(ii)]=biterr(t_data,decoded) ; % error rate calculation

        end
        ratio
        figure(1)
        semilogy(EbNo,ratio,’-g’);
        theoryBer = (1/2)*erfc(sqrt(10.^(EbNo/10)));
        semilogy (EbNo,theoryBer,’-k’);
        axis([0 12 10^-5 1])
        xlabel(‘EbNo’);
        ylabel(‘BER’)
        title(‘Bit error probability curve for BPSK using OFDM’);
        legend(‘simulated awgn’,’theoretical awgn’)

  • madhu4117

    hello sir i am doing a project on MIMO-OFDM system. Is that book ” Simulation of Digital Communication Systems Using Matlab [eBook] – Second Edition ” contains about ‘convolutional coding and Interleaving of MIMO-OFDM’ so that I will buy that

    • Hi,
      MIMO-OFDM is not discussed in the ebook. Only basic OFDM and its simulation is available.

      • Madhusudan Kar

        Thank you sir,
        Sir can you please recommend any book for MIMO-OFDM in which I can get some MATLAB codes for this.

        • Abdulbagi Elsanousi

          hello Madhusudan Kar and Mathuranathan i’m looking for convolutional coded OFDM through AWGN could you help me

  • Pingback: Viterbi Decoding of Convolutional codes | GaussianWaves()