Viterbi Decoder
Decode convolutionally encoded data using Viterbi algorithm
- Library:
Communications Toolbox / Error Detection and Correction / Convolutional
Communications Toolbox HDL Support / Error Detection and Correction / Convolutional
Description
The Viterbi Decoder block decodes convolutionally encoded input symbols to produce binary output symbols by using the Viterbi algorithm. A trellis structure specifies the convolutional encoding scheme. For more information, see Trellis Description of a Convolutional Code.
This block can process several symbols at a time for faster performance and can accept inputs that vary in length during simulation. For more information about variable-size signals, see Variable-Size Signal Basics (Simulink).
This icon shows all the optional block ports enabled.
Ports
Input
In
— Convolutionally encoded codeword
column vector
Convolutionally encoded codeword, specified as a column vector. If the decoder takes
N input bit streams (that is, it
can receive 2N possible input symbols), the block input
vector length is L×N for some positive integer L. For more information, see Input and Output Sizes, Input Values and Decision Types, and the Operation mode
parameter.
This port is unnamed until a second input port is enabled.
Data Types: double
| single
| Boolean
| int8
| int16
| int32
| uint8
| uint16
| uint32
| ufixn
Era
— Erasure bits in codeword
binary-valued vector
Erasure bits in the codeword, specified as a binary-valued vector.
Values of 1
in the vector correspond to erased bits,
and values of 0
correspond to nonerased bits.
For these erasures in the incoming data stream, the decoder does not update the branch metric. The widths and the sample times of the erasure and the input data ports must be the same.
Dependencies
To enable this port, select Enable erasures input port.
Data Types: double
| Boolean
Rst
— Option to reset state of decoder registers
scalar
Option to reset the state of decoder registers, specified as scalar value. When this port receives a nonzero input value, the block sets its internal memory to the initial state before processing the input data. Resetting the decoder registers to the initial state sets:
The all-zeros state metric to zero
All other state metrics to the maximum value
The traceback memory to zero
Using the reset port on this block is analogous to setting
Operation mode for the Convolutional Encoder block
to Reset on nonzero input via port
.
Dependencies
To enable this port, set the Operation mode parameter
to Continuous
and select Enable
reset input port.
Data Types: double
| Boolean
Output
Out
— Output message
binary column vector
Output message, returned as a binary column vector. If the decoder produces K output bit streams (that is, it can produce 2K possible output symbols), the block output vector length is L×K for some positive integer L. For more information, see Input and Output Sizes.
This port is unnamed on the block icon.
Data Types: double
| single
| Boolean
| int8
| int16
| int32
| uint8
| uint16
| uint32
| ufix1
Parameters
Trellis structure
— Trellis description of convolutional code
poly2trellis(7,[171 133])
(default)
Trellis description of the convolutional code, specified as a structure that contains the trellis description for a rate K ∕ N code. K is the number of input bit streams, and N is the number of output bit streams.
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.
The trellis structure contains these fields.
numInputSymbols
— Number of symbols input to encoder
2K
Number of symbols input to the encoder, specified as an integer equal to 2K, where K is the number of input bit streams.
Data Types: double
numOutputSymbols
— Number of symbols output from encoder
2N
Number of symbols output from the encoder, specified as an integer equal to 2N, where N is the number of output bit streams.
Data Types: double
numStates
— Number of states in encoder
power of 2
Number of states in the encoder, specified as a power of 2.
Data Types: double
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
2K.
Data Types: double
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
2K.
Data Types: double
Punctured code
— Option to enable specification of code puncturing
off
(default) | on
Select this parameter to view and enable the Puncture vector parameter.
Puncture vector
— Puncture pattern vector
[1; 1; 0; 1; 0; 1]
(default) | column vector
Puncture pattern vector to puncture the decoded data, specified as a
column vector. The vector must contain 1
s and
0
s, where 0
indicates the position
of the punctured bits. This puncture pattern must match the puncture pattern
used by the convolutional encoder.
For some commonly used puncture patterns for specific rates and polynomials, see the Yasuda [4], Haccoun [5], and Begin [6] references.
Dependencies
This parameter appears only when you select the Punctured code parameter.
Enable erasures input port
— Option to enable erasures input port
off
(default) | on
Select this parameter to add the Era
input port to
the block.
Decision type
— Decoder decision type
Unquantized
(default) | Hard decision
| Soft decision
Decoder decision type, specified as
Unquantized
, Hard
decision
, or Soft Decision
.
Unquantized
— The decoder uses the Euclidean distance to calculate the branch metrics. The input data must be a real-valued vector of double- or single-precision soft values that are unquantized. The object maps positive values to logical1
s and negative values to logical0
sHard decision
— The decoder uses Hamming distance to calculate the branch metrics. The input must be a vector of hard decision values, which are0
s or1
s. The data type of the inputs must be double precision, single precision, logical, or numeric.Soft Decision
— The decoder uses Hamming distance to calculate the branch metrics. The input requires a vector of quantized soft values that are represented as integers between 0 and 2SoftInputWordLength – 1. The data type of the inputs must be double precision, single precision, logical, or numeric. Alternatively, you can specify the data type as an unsigned and unscaled fixed-point object using thefi
(Fixed-Point Designer) object with a word length (SoftInputWordLength) equal to the word length that you specify for the Number of soft decision bits parameter.0
is considered as most confident0
and 2SoftInputWordLength – 1 as the most confident1
.
Number of soft decision bits
— Soft input word length
4
(default) | positive integer
Soft input word length that represents the number of bits for each quantized soft input value, specified as an integer.
Dependencies
This parameter appears only when you set the Decision type parameter to Soft
decision
.
Error if quantized input values are out of range
— Option to error if quantized input values are out of range
off
(default) | on
Select this parameter to error if the quantized input values are out of range. If you do not select this parameter, out of range input values are ignored.
Dependencies
This parameter appears only when you set the Decision type parameter to Hard
decision
or Soft
decision
.
Traceback depth
— Traceback depth
34
(default) | positive integer
Traceback depth, specified as an integer that indicates the number of trellis branches used to construct each traceback path.
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.
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].
Operation mode
— Termination method of encoded frame
Continuous
(default) | Truncated
| Terminated
Method for transitioning between successive input frames, specified as one of these mode values.
Continuous
— The block saves its internal state metric at the end of each input, for use with the next frame. Each traceback path is treated independently. This mode results in a decoding delay of Traceback depth×K zero bits for a rate K/N convolutional code. K is the number of message symbols, and N is the number of coded symbols. If the Enable reset input port is selected, the decoder states are reset if theRst
port receives a nonzero value.Truncated
— The block treats each input independently. The traceback path starts at the state with the best metric and always ends in all-zeros state. This mode is appropriate when the corresponding Convolutional Encoder block has its Operation mode set toTruncated (reset every frame)
. There is no output delay for this mode.Terminated
— The block treats each input independently, and the traceback path always starts and ends in all-zeros state. This mode is appropriate when the uncoded message signal (that is, the input to the corresponding Convolutional Encoder block) has enough zeros at the end of each input to fill all memory registers of the feed-forward encoder. Specifically, there are at leastk*max(constr-1)
zeros at the end of the input, for an encoder that hask
input streams and constraint length vectorconstr
(using the polynomial description). For feedback encoders, this mode is appropriate if the corresponding Convolutional Encoder block has Operation mode set toTerminate trellis by appending bits
.
Note
The decoder states reset at every input time step when the block
outputs sequences that vary in length during simulation and you set the
Operation mode to
Truncated
or
Terminated
.
When the input signal contains only one symbol, use the
Continuous
operation mode .
Enable reset input port
— Option to add reset input port
off
(default) | on
Select this parameter to add the Rst
input
port.
Dependencies
This parameter appears only when you set the Operation mode parameter to
Continuous
.
Delay reset action to next time step
— Option to delay reset action until next time step
off
(default) | on
Select this parameter to delay reset of the decoder until after computing the encoded data received in the current time step. You must enable this option for HDL support. Generating HDL code requires HDL Coder™ software.
Dependencies
This parameter appears only when you set the Operation mode parameter to
Continuous
and select Enable
reset input port.
State metric word length
— State metric word length
16
(default) | positive integer
State metric word length, specified as a positive integer.
Output data type
— Output data type
Inherit via internal
rule
(default) | Smallest unsigned integer
| double
| single
| int8
| uint8
| int16
| uint16
| int32
| uint32
| boolean
Output data type, specified as double
, single
,
boolean
, int8
,
uint8
, int16
,
uint16
, int32
, or
uint32
, or set to 'Inherit via internal
rule'
or 'Smallest unsigned
integer'
.
When set to
'Smallest unsigned integer'
, the output data type is selected based on the settings used in the Hardware Implementation pane of the Configuration Parameters dialog box of the model. IfASIC/FPGA
is selected in the Hardware Implementation pane, the output data type isufix(1)
. For all other selections, it is an unsigned integer with the smallest specified word length corresponding to the char value (for example,uint8
).When set to
'Inherit via internal rule'
, the block:Outputs data type double for double inputs
Outputs data type single for single inputs
Behaves similar to the
'Smallest unsigned integer'
option for all other data type inputs
Model Examples
Block Characteristics
More About
Input and Output Sizes
If the convolutional code uses an alphabet of 2N possible symbols, the input vector length must be L×N for some positive integer L. Similarly, if the decoded data uses an alphabet of 2K possible output symbols, the output vector length is L×K.
This block accepts a column vector input signal with any positive integer value for L. For variable-size inputs, L can vary during simulation. The operation of the block is governed by the operation mode parameter.
This table shows the data types supported for the input and output ports.
Port | Supported Data Types |
---|---|
Input |
|
Output |
|
Input Values and Decision Types
The entries of the input vector are either bipolar real, binary, or integer data, depending on the Decision type parameter.
Decision type Parameter | Possible Entries in Decoder Input | Interpretation of Values | Branch metric calculation |
---|---|---|---|
| Real numbers Input values outside of the range [–1012, 1012] are clipped to –1012 and 1012, respectively. | Positive real: logical zero Negative real: logical one | Euclidean distance |
| 0, 1 | 0: logical zero 1: logical one | Hamming distance |
| Integers between 0 and 2 b -1, where b is the Number of soft decision bits parameter. | 0: most confident decision for logical zero 2b-1: most confident decision for logical one Other values represent less confident decisions. | Hamming distance |
To illustrate the soft decision situation more explicitly, the following table lists interpretations of values for 3-bit soft decisions.
Input Value | Interpretation |
---|---|
0 | Most confident zero |
1 | Second most confident zero |
2 | Third most confident zero |
3 | Least confident zero |
4 | Least confident one |
5 | Third most confident one |
6 | Second most confident one |
7 | Most confident one |
Fixed-Point Signal Flow Diagram
There are three main components to the Viterbi decoding algorithm. They are branch metric computation (BMC), add-compare and select (ACS), and traceback decoding (TBD). This diagram illustrates the signal flow for a k/n rate code.
This diagram illustrates the BMC for a 1/2 rate, nsdec = 3 signal flow.
This diagram illustrates an ACS component cycle, where
WL2
is specified on the mask by the user.
In these flow diagrams, inNT, bMetNT , stMetNT, and outNT are numerictype
(Fixed-Point Designer) objects, and bMetFIMATH and
stMetFIMATH, are fimath (Fixed-Point Designer)
objects.
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 Simulink® Coder™.
HDL Code Generation
Generate Verilog and VHDL code for FPGA and ASIC designs using HDL Coder™.
HDL Coder provides additional configuration options that affect HDL implementation and synthesized logic.
Note
For decoding data encoded with truncated or terminated modes, or punctured codes, use the Viterbi Decoder (Wireless HDL Toolbox) block from Wireless HDL Toolbox™.
HDL Coder supports the following features of the Viterbi Decoder block:
Non-recursive encoder/decoder with feed-forward trellis and simple shift register generation configuration
Continuous mode
Sample-based input
Decoder rates from 1/2 to 1/7
Constraint length from 3 to 9
When you set Decision type to Soft
decision
, HDL code generation is supported for fixed-point input
and output data types. The input fixed-point data type must be
ufixN
. N
is the number of soft-decision
bits. HDL code generation is not supported for signed built-in data types
(int8
, int16
, int32
).
When you set Decision type to Hard
decision
, HDL code generation is supported for input with data
types ufix1
and Boolean
. HDL code generation
is not supported for double and single input data types.
The Viterbi Decoder block decodes every bit by tracing back through a traceback depth that you define for the block. The block implements a complete traceback for each decision bit, using registers to store the minimum state index and branch decision in the traceback decoding unit. There are two methods to optimize the traceback logic: a pipelined register-based implementation or a RAM-based architecture. See the HDL Code Generation for Viterbi Decoder example.
You can specify that the traceback decoding unit be pipelined to improve the speed of the generated circuit. You can add pipeline registers to the traceback unit by specifying the number of traceback stages per pipeline register.
Using the TracebackStagesPerPipeline
implementation
parameter, you can balance the circuit performance
based on system requirements. A smaller parameter value indicates the
requirement to add more registers to increase the speed of the traceback
circuit. Increasing the parameter value results in fewer registers along with a
decrease in the circuit speed.
Instead of using registers, you can choose to use RAMs to save the survivor branch information. The coder does not support Enable reset input port when using RAM-based traceback.
Right-click the block and open HDL Code > HDL Block Properties. Set the Architecture property to
RAM-based Traceback
.Double-click the block and set the Traceback depth on the Viterbi Decoder block mask.
RAM-based traceback and register-based traceback differ in the following ways:
The RAM-based implementation traces back through one set of data to find the initial state to decode the previous set of data. The register-based implementation combines the traceback and decode operations into one step. It uses the best state found from the minimum operation as the decoding initial state.
RAM-based implementation traces back through M samples, decodes the previous M bits in reverse order, and releases one bit in order at each clock cycle. The register-based implementation decodes one bit after a complete traceback.
Because of the differences in the two traceback algorithms, the RAM-based implementation produces different numerical results than the register-based traceback. A longer traceback depth, for example, 10 times the constraint length, is recommended in the RAM-based traceback. This depth achieves a similar bit error rate (BER) as the register-based implementation. The size of RAM required for the implementation depends on the trellis and the traceback depth.
ConstrainedOutputPipeline | Number of registers to place at
the outputs by moving existing delays within your design. Distributed
pipelining does not redistribute these registers. The default is
|
InputPipeline | Number of input pipeline stages
to insert in the generated code. Distributed pipelining and constrained
output pipelining can move these registers. The default is
|
OutputPipeline | Number of output pipeline stages
to insert in the generated code. Distributed pipelining and constrained
output pipelining can move these registers. The default is
|
TracebackStagesPerPipeline |
Punctured code: Do not select this option. Punctured code requires frame-based input, which HDL Coder does not support.
Decision type: The coder does not support the
Unquantized
decision type.Error if quantized input values are out of range: The coder does not support this option.
Operation mode: The coder supports only the
Continuous
mode.Enable reset input port: When you enable both Enable reset input port and Delay reset action to next time step, HDL support is provided. You must select
Continuous
operation mode, and use register-based traceback.You cannot use the Viterbi Decoder block inside a Resettable Synchronous Subsystem (HDL Coder).
Version History
Introduced before R2006aR2022b: Version History
Unquantized input values outside of the range [–1012, 1012] are clipped to –1012 and 1012, respectively.
See Also
Blocks
Functions
Objects
MATLAB Command
You clicked a link that corresponds to this MATLAB command:
Run the command by entering it in the MATLAB Command Window. Web browsers do not support MATLAB commands.
Select a Web Site
Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .
You can also select a web site from the following list:
How to Get Best Site Performance
Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.
Americas
- América Latina (Español)
- Canada (English)
- United States (English)
Europe
- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)
- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)