vitdec

Convolutionally decode binary data by using Viterbi algorithm

Syntax

decodedout = vitdec(msg,trellis,tbdepth,opmode,dectype)

decodedout = vitdec(msg,trellis,tbdepth,opmode,'soft',nsdec)

decodedout = vitdec(msg,trellis,tbdepth,opmode,dectype,puncpat)

decodedout = vitdec(msg,trellis,tbdepth,opmode,dectype,puncpat,eraspat)

decodedout = vitdec(msg,trellis,tbdepth,'cont',dectype,___,imetric,istate,iinput)

[decodedout,fmetric,fstate,finput] = vitdec(msg,trellis,tbdepth,'cont',___)

Description

decodedout = vitdec(msg,trellis,tbdepth,opmode,dectype) decodes each symbol of the msg input by using the Viterbi algorithm. All other inputs specify the convolutional coding trellis, traceback depth, operating mode, and decision type, respectively and collectively configure the Viterbi algorithm at runtime.

decodedout = vitdec(msg,trellis,tbdepth,opmode,'soft',nsdec) configures the Viterbi algorithm for soft-decision decoding for dectype and with nsdec bits of quantization.

decodedout = vitdec(msg,trellis,tbdepth,opmode,dectype,puncpat) decodes each symbol of the punctured codedin input, where puncpat is the puncture pattern.

decodedout = vitdec(msg,trellis,tbdepth,opmode,dectype,puncpat,eraspat) specifies an erasure pattern, eraspat. To not use puncturing, specify puncpat as [].

decodedout = vitdec(msg,trellis,tbdepth,'cont',dectype,___,imetric,istate,iinput) specifies a continuous operation mode for opmode for any of the preceding syntaxes. The decoder starts with its initial state metrics, traceback states, and traceback inputs specified by imetric, istate, and iinput, respectively.

Continuous operation mode enables you to save the internal state information of the decoder for use in subsequent calls to this function. Repeated calls to this function can be useful if your data is partitioned into a series of vectors that you process within a loop. For workflows that require repeated calls to the Viterbi decoding algorithm, see Tips.

[decodedout,fmetric,fstate,finput] = vitdec(msg,trellis,tbdepth,'cont',___) also returns the final state metrics, traceback states, and traceback inputs at the end of the decoding process when using a continuous operation mode for any of the preceding syntaxes. Use fmetric, fstate, and finput as the initial settings of imetric, istate, and iinput, respectively, in subsequent calls to this function. For workflows that require repeated calls to the Viterbi decoding algorithm, see Tips.

Examples

Decode Convolutional Code by Using Viterbi Decoder

Convolutionally encode a vector of 1s by using the convenc function, and decode it by using the vitdec function.

Define a trellis structure, by using the poly2trellis function. Use the trellis structure to configure the convenc function when encoding a vector of ones.

trellis = poly2trellis([4 3],[4 5 17;7 4 2]);
x = ones(100,1);
code = convenc(x,trellis);

When decoding the encoded message, configure the Viterbi decoder to use the trellis structure defined previously, a traceback depth of 2, the truncated operating mode, and hard decisions.

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

Verify that the decoded message is a vector of 100 1s.

isequal(decoded,ones(100,1))

ans = logical
   1

Decode Punctured Signal Using Viterbi Algorithm

Apply Viterbi decoding to a punctured signal. The puncturing changes the code rate from 1/2 to 3/4.

Initialize parameters for the encoding and decoding operations.

trellis = poly2trellis(7,[171 133])

trellis = struct with fields:
     numInputSymbols: 2
    numOutputSymbols: 4
           numStates: 64
          nextStates: [64x2 double]
             outputs: [64x2 double]

tbdepth = 96;
opmode = 'trunc';
dectype = 'hard';
puncpat = [1;1;0;1;1;0];

Calculate the unpunctured and punctured code rates.

K = log2(trellis.numInputSymbols);  % Number of input streams
N = log2(trellis.numOutputSymbols); % Number of output streams
unpunc_coderate = K/N

unpunc_coderate = 
0.5000

punc_coderate = (K/N)*(length(puncpat)/sum(puncpat))

punc_coderate = 
0.7500

Convolutionally encode an all 1s bit message with puncturing applied to the coded output.

msg = ones(100*length(puncpat),1);
puncturedcode = convenc(msg,trellis,puncpat);

Show the lengths of the message, the punctured code, and the puncture pattern.

length(msg)

ans = 
600

length(puncturedcode)

ans = 
800

length(puncpat)

ans = 
6

Apply Viterbi decoding to the punctured coded message. Compare the decoded output to the original message. Even with puncturing applied to the coded message, the Viterbi decoding recovered the message with zero error.

codedin = puncturedcode;
decodedout = vitdec(codedin,trellis,tbdepth,opmode,dectype,puncpat);

isequal(msg,decodedout)

ans = logical
   1

Estimate BER for Rate 2/3 Convolutional Code

Estimate the bit error rate (BER) simulation for a link that uses a rate 2/3 convolutional code, applies 16-QAM modulation, and transmits data through an AWGN channel. This diagram shows a rate 2/3 encoder with two input streams, three output streams, and seven shift registers.

Define the convolutional coding trellis represented by the diagram.

trellis = poly2trellis([5 4],[23 35 0; 0 5 13])

trellis = struct with fields:
     numInputSymbols: 4
    numOutputSymbols: 8
           numStates: 128
          nextStates: [128x4 double]
             outputs: [128x4 double]

K = log2(trellis.numInputSymbols); % Number of input bit streams
N = log2(trellis.numOutputSymbols); % Number of output bit streams
coderate = K/N;

fprintf('K is %d and N is %d. The code rate is %3.2f.\n', ...
    K,N,coderate)

K is 2 and N is 3. The code rate is 0.67.

Set the modulation order, and compute the number of bits per modulation symbol. Generate random binary data. The input bit stream must be a multiple of number of the input bit streams (K) for the coding operation and must be a multiple of the number of bits per modulation symbol (bps) for the modulation operation.

M = 16; % Modulation order
bps = log2(M); % Bits per modulation symbol
numSymPerFrame = 5000;
dataIn = randi([0 1],K*bps*numSymPerFrame,1);

Convolutionally encode the input data.

codedout = convenc(dataIn,trellis);

Apply 16-QAM modulation to the encoded symbols.

txSig = qammod(codedout,M,'InputType','bit');

Using the number of bits per symbol (bps) and the code rate (coderate), convert the ratio of energy per bit to noise power spectral density (EbNo) to an signal-to-noise (snr) value for use by the awgn function. Convert a 10 dB Eb/No to an equivalent SNR ratio. Pass the signal through an AWGN channel.

EbNo = 9;
snr = EbNo + 10*log10(bps*coderate);
rxSig = awgn(txSig,snr,'measured');

Demodulate the received signal.

demodSig = qamdemod(rxSig,M,'OutputType','bit');

Specify the traceback depth of the Viterbi decoder.

tbdepth = 16;

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

dataOut = vitdec(demodSig,trellis,tbdepth,'cont','hard');

Calculate the delay through the decoder, and account for the decoding delay when computing the BER. Compare the coded BER with the theoretical uncoded BER to see the improved BER for the coded data.

decDelay = K*tbdepth;
berCoded = biterr( ...
    dataIn(1:end-decDelay),dataOut(decDelay+1:end)) / ...
     length(dataOut(decDelay+1:end));
berUncoded = berawgn(EbNo,'qam',M);
fprintf('The coded BER is %6.5f.\nThe uncoded BER is %6.5f.\n', ...
    berCoded,berUncoded)

The coded BER is 0.00045.
The uncoded BER is 0.00439.

Input Arguments

msg — Convolutionally encoded message

vector of binary values | vector of numeric values

Convolutionally encoded message, specified as a vector of binary or numeric values. Each symbol in codedin consists of log2(trellis.numOutputSymbols) bits.

When you set dectype to 'unquant', input values outside of the range [–10¹², 10¹²] are clipped to –10¹² and 10¹², respectively.

Data Types: double | logical

trellis — Trellis description

structure

Trellis description, specified as a MATLAB^® structure that contains the trellis description for a rate K/N code. K represents the number of input bit streams, and N represents the number of output bit streams.

The trellis structure contains these fields. You can either use the poly2trellis function to create the trellis structure or create it manually. For more about this structure, see Trellis Description of a Convolutional Code and the istrellis function.

numInputSymbols — Number of symbols input to encoder

2^K

Number of symbols input to the encoder, specified as an integer equal to 2^K, where K is the number of input bit streams.

numOutputSymbols — Number of symbols output from encoder

2^N

Number of symbols output from the encoder, specified as an integer equal to 2^N, where N is the number of output bit streams.

numStates — Number of states in encoder

power of 2

Number of states in the encoder, specified as a power of 2.

nextStates — Next states

matrix of integers

Next states for all combinations of current states and current inputs, specified as a matrix of integers. The matrix size must be numStates by 2^K.

outputs — Outputs

matrix of octal numbers

Outputs for all combinations of current states and current inputs, specified as a matrix of octal numbers. The matrix size must be numStates by 2^K.

Data Types: struct

tbdepth — Traceback depth

positive integer

Traceback depth, specified as a positive integer. For more information, see Traceback Depth Estimates.

Data Types: double

opmode — Operating mode

'cont' | 'term' | 'trunc'

Operating mode, specified as 'cont', 'term', or 'trunc'. This input indicates the operating mode of the decoder and these assumptions made about the operation of the corresponding encoder.

• 'cont' — Specifies continuous operating mode. In continuous operating mode, 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 input tbdepth symbols elapses before the first decoded symbol appears in the output. This mode is appropriate when you call this function repeatedly and want to preserve continuity between successive calls. For workflows that require repeated calls to the Viterbi decoding algorithm, see Tips.

• 'term' — Specifies terminated operating mode. In terminated operating mode, the encoder is assumed to have 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 zero delay.

  This mode is appropriate when the message input to the convenc function has enough zeros at its end to fill all memory registers of the encoder. The zero-valued tail bits flush all message data bits out of the encoder. Using the polynomial description of the encoder, for an encoder with K input bits and the constraint length vector ConstraintLength, the number of zeros required to flush the encoder is K × max(ConstraintLength – 1). The constraint length vector is the first input argument to the poly2trellis function.

• 'trunc' — Specifies truncated operating mode. In truncated operating mode, 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 zero 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 calls to this function.

For the 'term' and 'trunc' modes, the traceback depth, tbdepth, must be a positive integer, less than or equal to the number of input symbols in input codedin.

For more information, see Traceback and Decoding Delay and Traceback Depth Estimates.

Data Types: char | string

dectype — Decoding type

'unquant' | 'hard' | 'soft'

Decoding type, specified as 'unquant', 'hard', or 'soft'. This parameter indicates the type of decoding decision that the decoder makes and influences the type of data the decoder expects as input in codedin.

• 'unquant' — The decoder expects signed numeric input values, where positive values map to a logical 0 and negative values map to a logical 1.

• 'hard' — The decoder expects binary input values of 0 or 1.

• 'soft' — The decoder expects integer input values in the range [0, (2^nsdec – 1)]. The Viterbi algorithm decision criteria regards 0 as the most confident 0 and 2^nsdec – 1 as the most confident 1.

Data Types: char | string

nsdec — Number of soft decision quantization bits

integer in the range [1, 13]

Number of soft decision quantization bits, specified as an integer in the range [1, 13]. For reference, soft decision decoding with 3 bits of quantization improves error decoding recovery by approximately 2 dB as compared to hard decision decoding.

Dependencies

To enable this input argument set the dectype input argument to 'soft'.

Data Types: double

puncpat — Puncture pattern

vector of binary values

Puncture pattern, specified as a vector of binary values. Indicate punctured bits with 0s and unpunctured bits with 1s. The input code length divided by the number of 1s in the puncture pattern times the length of the puncture pattern must be an integer multiple of the number of bits in an input symbol.

Data Types: double

eraspat — Erasure pattern

vector of binary values

Erasure pattern, specified as a vector of binary values. Indicate erased bits with 1s and nonerased bits with 0s. The length of the erasures pattern must be the same as the input code length.

Data Types: double

imetric — Decoder state metrics

integer | vector of integer values

Decoder state metrics, specified as an integer or a vector of integer values. Each value in imetric represents the starting state metric of the corresponding decoder state. When you set imetric to a vector, the length must be trellis.numStates. To use the default decoder state metrics, specify imetric as [].

Dependencies

To enable this input argument set the opmode input argument to 'cont'.

Data Types: double

istate — Decoder initial traceback states

matrix of integer values

Decoder initial traceback states, specified as a trellis.numStates-by-tbdepth matrix of integer values in the range [0, (trellis.numStates – 1)]. To use the default decoder initial traceback states, specify istate as [].

Inputs istate and iinput jointly specify the initial traceback memory of the decoder. 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 istate, and the shift register that receives the last input stream provides the most significant bits in istate.

Dependencies

To enable this input argument set the opmode input argument to 'cont'.

Data Types: double

iinput — Decoder initial traceback inputs

matrix of integer values

Decoder initial traceback inputs, specified as a trellis.numStates-by-tbdepth matrix of integer values in the range [0, (trellis.numStates – 1)]. To use the default decoder initial traceback inputs, specify iinput as [].

Inputs istate and iinput jointly specify the initial traceback memory of the decoder.

Dependencies

To enable this input argument set the opmode input argument to 'cont'.

Data Types: double

Output Arguments

decodedout — Decoded message

vector of binary values

Decoded message, returned as a vector of binary values. Each symbol in the vector decodedout consists of log2(trellis.numInputSymbols) bits.

fmetric — Decoder final state metrics

vector of integer values

Decoder final state metrics, returned as a vector of integer values with trellis.numStates elements. Each value in fmetric represents the final state metric of the corresponding decoder state.

When calling vitdec in continuous mode, fmetric is typically used to set imetric for subsequent calls to the vitdec function.

Dependencies

This output applies when the opmode parameter is set to 'cont'.

Data Types: double

fstate — Decoder final traceback states

matrix of integer values

Decoder final traceback states, returned as a trellis.numStates-by-tbdepth matrix of integer values in the range [0, (trellis.numStates – 1)].

Outputs fstate and finput jointly describe the final traceback memory of the decoder. 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 fstate, and the shift register that receives the last input stream provides the most significant bits in fstate.

When calling vitdec in continuous mode, fstate is typically used to set istate for subsequent calls to the vitdec function.

Dependencies

This output applies when the opmode parameter is set to 'cont'.

Data Types: double

finput — Decoder final traceback inputs

matrix of integer values

Decoder final traceback inputs, returned as a trellis.numStates-by-tbdepth matrix of integer values in the range [0, (trellis.numStates – 1)].

Outputs fstate and finput jointly specify the final traceback memory of the decoder.

When calling vitdec in continuous mode, finput is typically used to set iinput for subsequent calls to the vitdec function.

Dependencies

This output applies when the opmode parameter is set to 'cont'.

Data Types: double

More About

Traceback and Decoding Delay

The traceback depth influences the decoding delay. The decoding delay is the number of zero symbols that precede the first decoded symbol in the output.

• For the continuous operating mode, the decoding delay is equal to the number of traceback depth symbols.

• For the truncated or terminated operating mode, the decoding delay is zero. In this case, the traceback depth must be less than or equal to the number of symbols in each input.

Traceback Depth Estimates

As a general estimate, a typical traceback depth value is approximately two to three times (ConstraintLength – 1) / (1 – coderate). The constraint length of the code, ConstraintLength, is equal to (log2(trellis.numStates) + 1). The coderate is equal to (K / N) × (length(PuncturePattern) / sum(PuncturePattern).

K is the number of input symbols, N is the number of output symbols, and PuncturePattern is the puncture pattern vector.

For example, applying this general estimate, results in these approximate traceback depths.

• A rate 1/2 code has a traceback depth of 5(ConstraintLength – 1).

• A rate 2/3 code has a traceback depth of 7.5(ConstraintLength – 1).

• A rate 3/4 code has a traceback depth of 10(ConstraintLength – 1).

• A rate 5/6 code has a traceback depth of 15(ConstraintLength – 1).

For more information, see [7].

Tips

• Consider using the comm.ViterbiDecoder System object™ when successive calls to the Viterbi algorithm are needed. The System object simplifies the required state retention operation by inherently retaining state metrics, traceback states, and inputs between calls.

References

[1] Clark, George C., and J. Bibb Cain. Error-Correction Coding for Digital Communications. Applications of Communications Theory. New York: Plenum Press, 1981.

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

[3] Heller, J., and I. Jacobs. “Viterbi Decoding for Satellite and Space Communication.” IEEE^® Transactions on Communication Technology 19, no. 5 (October 1971): 835–48. https://doi.org/10.1109/TCOM.1971.1090711.

[4] Yasuda, Y., K. Kashiki, and Y. Hirata. “High-Rate Punctured Convolutional Codes for Soft Decision Viterbi Decoding.” IEEE Transactions on Communications 32, no. 3 (March 1984): 315–19. https://doi.org/10.1109/TCOM.1984.1096047.

[5] Haccoun, D., and G. Begin. “High-Rate Punctured Convolutional Codes for Viterbi and Sequential Decoding.” IEEE Transactions on Communications 37, no. 11 (November 1989): 1113–25. https://doi.org/10.1109/26.46505.

[6] Begin, G., D. Haccoun, and C. Paquin. “Further Results on High-Rate Punctured Convolutional Codes for Viterbi and Sequential Decoding.” IEEE Transactions on Communications 38, no. 11 (November 1990): 1922–28. https://doi.org/10.1109/26.61470.

[7] Moision, B. "A Truncation Depth Rule of Thumb for Convolutional Codes." In Information Theory and Applications Workshop (January 27 2008-February 1 2008, San Diego, California), 555-557. New York: IEEE, 2008.

Extended Capabilities

C/C++ Code Generation

Generate C and C++ code using MATLAB® Coder™.

The input arguments trellis, opmode, tbdepth, dectype, and puncpat must be compile-time constants. For more information, see coder.Constant (MATLAB Coder).

Version History

Introduced before R2006a

R2022b: Version History

When you set dectype to 'unquant', input values outside of the range [–10¹², 10¹²] are clipped to –10¹² and 10¹², respectively.