Documentation

This is machine translation

Translated by Microsoft
Mouse over text to see original. Click the button below to return to the English verison of the page.

vitdec

Convolutionally decode binary data using Viterbi algorithm

Syntax

decoded = vitdec(code,trellis,tblen,opmode,dectype)
decoded = vitdec(code,trellis,tblen,opmode,'soft',nsdec)
decoded = ...
vitdec(code,trellis,tblen,opmode,dectype,puncpat)
decoded = ...
vitdec(code,trellis,tblen,opmode,dectype,puncpat,eraspat)
decoded = ...
vitdec(...,'cont',...,initmetric,initstates,initinputs)
[decoded,finalmetric,finalstates,finalinputs] = ...
vitdec(...,'cont',...)

Description

decoded = vitdec(code,trellis,tblen,opmode,dectype) decodes the vector code using the Viterbi algorithm. The MATLAB® structure trellis specifies the convolutional encoder that produced code; the format of trellis is described in Trellis Description of a Convolutional Code and the reference page for the istrellis function. code contains one or more symbols, each of which consists of log2(trellis.numOutputSymbols) bits. Each symbol in the vector decoded consists of log2(trellis.numInputSymbols) bits. tblen is a positive integer scalar that specifies the traceback depth. If the code rate is 1/2, a typical value for tblen is about five times the constraint length of the code.

opmode indicates the decoder's operation mode and its assumptions about the corresponding encoder's operation. Choices are in the table below.

Values of opmode Input

ValueMeaning
'cont'The encoder is assumed to have started at the all-zeros state. The decoder traces back from the state with the best metric. A delay equal to tblen symbols elapses before the first decoded symbol appears in the output. This mode is appropriate when you invoke this function repeatedly and want to preserve continuity between successive invocations. See the continuous operation mode syntaxes below.
'term'The encoder is assumed to have both started and ended at the all-zeros state, which is true for the default syntax of the convenc function. The decoder traces back from the all-zeros state. This mode incurs no delay. This mode is appropriate when the uncoded message (that is, the input to convenc) has enough zeros at the end to fill all memory registers of the encoder. If the encoder has k input streams and constraint length vector constr (using the polynomial description of the encoder), "enough" means k*max(constr-1).
'trunc'The encoder is assumed to have started at the all-zeros state. The decoder traces back from the state with the best metric. This mode incurs no delay. This mode is appropriate when you cannot assume the encoder ended at the all-zeros state and when you do not want to preserve continuity between successive invocations of this function.

For the 'term' and 'trunc' mode, the traceback depth (tblen) must be a positive integer scalar value, not greater than the number of input symbols in code.

dectype indicates the type of decision that the decoder makes, and influences the type of data the decoder expects in code. Choices are in the table below.

Values of dectype Input

ValueMeaning
'unquant'code contains real input values, where 1 represents a logical zero and -1 represents a logical one.
'hard'code contains binary input values.
'soft'For soft-decision decoding, use the syntax below. nsdec is required for soft-decision decoding.

Syntax for Soft Decision Decoding

decoded = vitdec(code,trellis,tblen,opmode,'soft',nsdec) decodes the vector code using soft-decision decoding. code consists of integers between 0 and 2^nsdec-1, where 0 represents the most confident 0 and 2^nsdec-1 represents the most confident 1. The existing implementation of the functionality supports up to 13 bits of quantization, meaning nsdec can be set up to 13. For reference, 3 bits of quantization is about 2 db better than hard decision decoding.

Syntax for Punctures and Erasures

decoded = ...
vitdec(code,trellis,tblen,opmode,dectype,puncpat)
denotes the input punctured code, where puncpat is the puncture pattern vector, and where 0s indicate punctured bits in the input code.

decoded = ...
vitdec(code,trellis,tblen,opmode,dectype,puncpat,eraspat)
allows an erasure pattern vector, eraspat, to be specified for the input code, where the 1s indicate the corresponding erasures. eraspat and code must be of the same length. If puncturing is not used, specify puncpat to be []. In the eraspat vector, 1s indicate erasures in the input code.

Additional Syntaxes for Continuous Operation Mode

Continuous operation mode enables you to save the decoder's internal state information for use in a subsequent invocation of this function. Repeated calls to this function are useful if your data is partitioned into a series of smaller vectors that you process within a loop, for example.

decoded = ...
vitdec(...,'cont',...,initmetric,initstates,initinputs)
is the same as the earlier syntaxes, except that the decoder starts with its state metrics, traceback states, and traceback inputs specified by initmetric, initstates, and initinputs, respectively. Each real number in initmetric represents the starting state metric of the corresponding state. initstates and initinputs jointly specify the initial traceback memory of the decoder; both are trellis.numStates-by-tblen matrices. initstates consists of integers between 0 and trellis.numStates-1. If the encoder schematic has more than one input stream, the shift register that receives the first input stream provides the least significant bits in initstates, while the shift register that receives the last input stream provides the most significant bits in initstates. The vector initinputs consists of integers between 0 and trellis.numInputSymbols-1. To use default values for all of the last three arguments, specify them as [],[],[].

[decoded,finalmetric,finalstates,finalinputs] = ...
vitdec(...,'cont',...)
is the same as the earlier syntaxes, except that the final three output arguments return the state metrics, traceback states, and traceback inputs, respectively, at the end of the decoding process. finalmetric is a vector with trellis.numStates elements that correspond to the final state metrics. finalstates and finalinputs are both matrices of size trellis.numStates-by-tblen. The elements of finalstates have the same format as those of initstates.

Traceback Matrices

The tth column of P1 shows the t-1th time step states given the inputs listed in the input matrix. For example, the value in the ith row shows the state at time t-1 that transitions to the i-1 state at time t. The input required for this state transition is given in the ith row of the tth column of the input matrix.

The P1 output is the states of the traceback matrix. It is a [number of states x traceback length] matrix. The following example uses a (7,5), rate 1/2 code. This code is easy to follow:

t = poly2trellis(3,[7 5]);
k = log2(t.numInputSymbols);
msg = [1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0];
code = convenc(msg,t); tblen = 15; [d1 m1 p1 in1]=vitdec(code(1:end/2),t,tblen,'cont','hard')

m1 =

     0     3     2     3
p1 =

     0     1     1     0     0     1     1     0     0     1     1     0     0     1     1
     2     3     3     2     2     3     3     2     2     3     3     2     2     3     3
     0     1     1     0     0     1     1     0     0     1     1     0     0     1     1
     2     3     3     2     2     3     3     2     2     3     3     2     2     3     3
in1 =

     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     1     1     1     1     1     1     1     1     1     1     1     1     1     1     1
     1     1     1     1     1     1     1     1     1     1     1     1     1     1     1

In this example, the message makes the encoder states follow the following sequence:

0 2 3 1 / 0 2 3 1 / ...

Since the best state is 0 (column index of smallest metric in m1 –1), the traceback matrix starts from sate 0, looking at the first row (0th state) of the last column of P1, ([1; 3; 1; 3]), which is 1. This indicates 1 for the previous state.

Next, the traceback matrix checks in1 ([0; 0; 1; 1]), which indicates 0 for the input. The second row (1st state) of the 14th column of P1 ([1; 3; 1; 3]) is 3. This indicates 3 for the previous state.

The traceback matrix checks in1 ([0; 0; 1; 1]), which indicates that the input was 0. The fourth row (3rd state) of the 13th column of P1 ([0; 2; 0; 2]), is 2. This indicates 2 for the previous state.

The traceback matrix checks in1 ([0; 0; 1; 1]), which indicates the input was 1. The third row (2nd state) of the 12th column of P1 ([0; 2; 0; 2]), is 0. This indicates 0 for the previous state.

The traceback matrix checks in1 ([0; 0; 1; 1]), which indicates the input was 1. The first row (0th state) of the 11th column of P1 ([1; 3; 1; 3]), is 1. This indicates 1 for the previous state. Then, the matrix checks in1 ([0; 0; 1; 1]), which indicates 0 for the input.

To determine the best state for a gicen time, use m1. The smallest number in m1 represents the best state.

Examples

collapse all

This example shows how to create a convolutional code using the convenc function and how to decode it using vitdec.

Encoding

Define a trellis.

t = poly2trellis([4 3],[4 5 17;7 4 2]);

Encode a vector of ones.

x = ones(100,1);
code = convenc(x,t);

Decoding

Define a trellis.

t = poly2trellis([4 3],[4 5 17;7 4 2]);

Encode a vector of ones.

code = convenc(ones(100,1),t);

Set the traceback length for decoding and decode using vitdec.

tb = 2;
decoded = vitdec(code,t,tb,'trunc','hard');

Verify that the decoded data is a vector of 100 ones.

isequal(decoded,ones(100,1))
ans =

  logical

   1

This example performs a bit error rate simulation for a link that uses 16-QAM modulation a rate 2/3 convolutional code.

Set the modulation order, and compute the number of bits per symbol.

M = 16;
k = log2(M);

Generate random binary data.

dataIn = randi([0 1],100000,1);

Define a convolutinal coding trellis for a rate 2/3 code.

tPoly = poly2trellis([5 4],[23 35 0; 0 5 13]);
codeRate = 2/3;

Convolutinally encode the input data.

codeword = convenc(dataIn,tPoly);

Reshape the encoded column vector into a matrix having k columns. Then, convert the binary matrix into an integer column vector.

codewordMat = reshape(codeword,length(codeword)/k,k);
txSym = bi2de(codewordMat);

Apply 16-QAM modulation to the encoded symbols.

txSig = qammod(txSym,M);

Convert a 10 dB Eb/No to an equivalent signal-to-noise ratio. Pass the signal through an AWGN channel.

EbNo = 10;
snr = EbNo + 10*log10(k*codeRate);
rxSig = awgn(txSig,snr,'measured');

Demodulate the received signal.

demodSig = qamdemod(rxSig,M);

Convert the output of the demodulator into a binary column vector.

demodSigMat = de2bi(demodSig,k);
demodSigBinary = demodSigMat(:);

Set the traceback depth of the Viterbi decoder.

traceBack = 16;

Decode the binary demodulated signal by using a Viterbi decoder operating in a continuous termination mode.

dataOut = vitdec(demodSigBinary,tPoly,traceBack,'cont','hard');

Calculate the delay through the decoder, and compute the bit error statistics.

decDelay = 2*traceBack;
[numErrors,ber] = biterr(dataIn(1:end-decDelay),dataOut(decDelay+1:end))
numErrors =

    26


ber =

   2.6008e-04

Compare the BER with the uncoded BER.

berUncoded = berawgn(EbNo,'qam',M);
berUncoded/ber
ans =

    6.7446

The convolutional code reduces the BER by approximately a factor of 4.

Estimate bit error rate (BER) performance for hard-decision and soft-decision Viterbi decoders in AWGN. Compare the performance to that of an uncoded 64-QAM link.

Set the simulation parameters.

clear; close all
rng default
M = 64;                 % Modulation order
k = log2(M);            % Bits per symbol
EbNoVec = (4:10)';       % Eb/No values (dB)
numSymPerFrame = 1000;   % Number of QAM symbols per frame

Initialize the BER results vectors.

berEstSoft = zeros(size(EbNoVec));
berEstHard = zeros(size(EbNoVec));

Set the trellis structure and traceback length for a rate 1/2, constraint length 7, convolutional code.

trellis = poly2trellis(7,[171 133]);
tbl = 32;
rate = 1/2;

The main processing loops performs these steps:

  • Generate binary data.

  • Convolutinally encode the data.

  • Apply QAM modulation to the data symbols.

  • Pass the modulated signal through an AWGN channel.

  • Demodulate the received signal using hard decision and approximate LLR methods.

  • Viterbi decode the signals using hard and unquantized methods.

  • Calculate the number of bit errors.

The while loop continues to process data until either 100 errors are encountered or 1e7 bits are transmitted.

for n = 1:length(EbNoVec)
    % Convert Eb/No to SNR
    snrdB = EbNoVec(n) + 10*log10(k*rate);
    % Reset the error and bit counters
    [numErrsSoft,numErrsHard,numBits] = deal(0);

    while numErrsSoft < 100 && numBits < 1e7
        % Generate binary data and convert to symbols
        dataIn = randi([0 1],numSymPerFrame*k,1);

        % Convolutionally encode the data
        dataEnc = convenc(dataIn,trellis);

        % QAM modulate
        txSig = qammod(dataEnc,M,'InputType','bit');

        % Pass through AWGN channel
        rxSig = awgn(txSig,snrdB,'measured');

        % Demodulate the noisy signal using hard decision (bit) and
        % approximate LLR approaches
        rxDataHard = qamdemod(rxSig,M,'OutputType','bit');
        rxDataSoft = qamdemod(rxSig,M,'OutputType','approxllr', ...
            'NoiseVariance',10.^(snrdB/10));

        % Viterbi decode the demodulated data
        dataHard = vitdec(rxDataHard,trellis,tbl,'cont','hard');
        dataSoft = vitdec(rxDataSoft,trellis,tbl,'cont','unquant');

        % Calculate the number of bit errors in the frame. Adjust for the
        % decoding delay, which is equal to the traceback depth.
        numErrsInFrameHard = biterr(dataIn(1:end-tbl),dataHard(tbl+1:end));
        numErrsInFrameSoft = biterr(dataIn(1:end-tbl),dataSoft(tbl+1:end));

        % Increment the error and bit counters
        numErrsHard = numErrsHard + numErrsInFrameHard;
        numErrsSoft = numErrsSoft + numErrsInFrameSoft;
        numBits = numBits + numSymPerFrame*k;

    end

    % Estimate the BER for both methods
    berEstSoft(n) = numErrsSoft/numBits;
    berEstHard(n) = numErrsHard/numBits;
end

Plot the estimated hard and soft BER data. Plot the theoretical performance for an uncoded 64-QAM channel.

semilogy(EbNoVec,[berEstSoft berEstHard],'-*')
hold on
semilogy(EbNoVec,berawgn(EbNoVec,'qam',M))
legend('Soft','Hard','Uncoded','location','best')
grid
xlabel('Eb/No (dB)')
ylabel('Bit Error Rate')

As expected, the soft decision decoding produces the best results.

Limitations

In order to improve performance of C/C++ code generated by MATLAB, integrity and responsiveness checks should be disabled before running the codegen function. See MATLAB Code Design Considerations for Code Generation for more information.

For example, given the following function:

function y = vitdec_hard(x,t,tb)
%# codegen

y = vitdec(x,t,tb,'trunc','hard');

Execute these commands for optimal performance.

cf = coder.config;
cf.IntegrityChecks = false;
cf.ResponsivenessChecks = false;
codegen('vitdec_hard','-args',{x,coder.Constant(t),tb})

The coded data, x, the trellis structure, t, and the traceback length, tb, must be defined in the base workspace.

References

[1] Clark, G. C. Jr. and J. Bibb Cain., Error-Correction Coding for Digital Communications, New York, Plenum Press, 1981.

[2] Gitlin, Richard D., Jeremiah F. Hayes, and Stephen B. Weinstein, Data Communications Principles, New York, Plenum, 1992.

[3] Heller, J. A. and I. M. Jacobs, "Viterbi Decoding for Satellite and Space Communication," IEEE Transactions on Communication Technology, Vol. COM-19, October 1971, pp 835–848.

[4] Yasuda, Y., et. al., "High rate punctured convolutional codes for soft decision Viterbi decoding," IEEE Transactions on Communications, vol. COM-32, No. 3, pp 315–319, Mar. 1984.

[5] Haccoun, D., and G. Begin, "High-rate punctured convolutional codes for Viterbi and sequential decoding," IEEE Transactions on Communications, vol. 37, No. 11, pp 1113–1125, Nov. 1989.

[6] G. Begin, et.al., "Further results on high-rate punctured convolutional codes for Viterbi and sequential decoding," IEEE Transactions on Communications, vol. 38, No. 11, pp 1922–1928, Nov. 1990.

Introduced before R2006a

Was this topic helpful?