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 Encoder 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.

The string 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

Value	Meaning
`'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.

The string 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

Value	Meaning
`'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.

Examples

The example below encodes random data and adds noise. Then it decodes the noisy code three times to illustrate the three decision types that vitdec supports. For unquantized and soft decisions, the output of convenc does not have the same data type that vitdec expects for the input code, so it is necessary to manipulate ncode before invoking vitdec. That the bit error rate computations must account for the delay that the continuous operation mode incurs.

% Encode data bits
trel = poly2trellis(3,[6 7]); % Define trellis
msg = randi([0 1],1000,1); % Random data
code = convenc(msg,trel); % Encode
tblen = 5; % Traceback length

% Map "0" bit to 1.0 and "1" bit to -1.0.  Also add AWGN.
ucode = real(awgn(1-2*code, 3, 'measured'));

% Hard decision decoding using binary inputs
hcode = ucode<0;
decoded1 = vitdec(hcode,trel,tblen,'cont','hard'); 

% Soft decision decoding with quantized inputs
[x,qcode] = quantiz(ucode,[-.75 -.5 -.25 0 .25 .5 .75],...
7:-1:0); % Values in qcode are between 0 and 2^3-1.
decoded2 = vitdec(qcode',trel,tblen,'cont','soft',3);

% Soft decision decoding using unquantized inputs
decoded3 = vitdec(ucode,trel,tblen,'cont','unquant');

% Compute bit error rates, using the fact that the decoder
% output is delayed by tblen symbols.
[n1,r1] = biterr(double(decoded1(tblen+1:end)),msg(1:end-tblen));
[n2,r2] = biterr(decoded2(tblen+1:end),msg(1:end-tblen));
[n3,r3] = biterr(decoded3(tblen+1:end),msg(1:end-tblen));
disp(['The bit error rates are:   ',num2str([r1 r2 r3])])

The output is similar to the following:

The bit error rates are:   0.064322    0.020101     0.01608

The example below illustrates how to use the final state and initial state arguments when invoking vitdec repeatedly. [decoded4;decoded5] is the same as decoded6.

trel = poly2trellis(3,[6 7]); % Define trellis
tblen = 5; % Traceback length
bitsPerPk = 100;  % number of bits per package
SNR = 3;
% Initialize the initial states of the encoder and ...
%     the decoder to default values
encState = []; decMetric = []; decState = []; decInput = [];
totalNumErr = 0;  % Inititalize total number of bit errors
% Main loop
for pkCount = 1:10
    msg = randi([0 1],bitsPerPk,1); % Generate random data
    % Encode starting from encState and save last state
    [code encState] = convenc(msg,trel,encState); 
    % Map "0" bit to 1.0 and "1" bit to -1.0.  Also add AWGN.
    ucode = real(awgn(1-2*code, SNR, 'measured'));
    % Soft decision decoding using unquantized inputs.  Start with the
    % provided state and save the last state of the decoder.
    [decoded,decMetric,decState,decInput] = ...
        vitdec(ucode,trel,tblen,'cont','unquant',[], ... 
zeros(bitsPerPk*2,1),...
        decMetric,decState,decInput);
    % Compute bit error rates, using the fact that the decoder
    % output is delayed by tblen symbols.
    if (pkCount == 1)
        numErr = biterr(decoded(tblen+1:end),msg(1:end-tblen));
    else
        numErr = biterr(decoded,[prevMsg; msg(1:end-tblen)]);
    end
    totalNumErr = totalNumErr + numErr;
    prevMsg = msg(end-tblen+1:end);
end
% Compute the bit error rate
BER = totalNumErr / (pkCount*bitsPerPk-tblen)

The output is similar to the following:

BER =

    0.0050

For additional examples, see Examples of Convolutional Coding.

For some commonly used puncture patterns for specific rates and polynomials, see the last three references below.

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.