Convolutionally decode binary data using Viterbi algorithm

`decoded = vitdec(code,trellis,tblen,`

* opmode*,

`dectype`

decoded = vitdec(code,trellis,tblen,

`opmode`

`soft`

',nsdec)decoded = ... vitdec(code,trellis,tblen,

`opmode`

`dectype`

decoded = ... vitdec(code,trellis,tblen,

`opmode`

`dectype`

decoded = ... vitdec(...,'

`cont`

',...,initmetric,initstates,initinputs) [decoded,finalmetric,finalstates,finalinputs] = ... vitdec(...,'

`cont`

',...)`decoded = vitdec(code,trellis,tblen,`

decodes
the vector * opmode*,

`dectype`

`code`

using the Viterbi algorithm. The MATLAB`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**

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

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**

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

`decoded = vitdec(code,trellis,tblen,`

decodes the vector * opmode*,'

`soft`

',nsdec)`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.```
decoded = ...
vitdec(code,trellis,tblen,
```

denotes
the input punctured * opmode*,

`dectype`

`code`

, where `puncpat`

is
the puncture pattern vector, and where `0`

s indicate
punctured bits in the input code.```
decoded = ...
vitdec(code,trellis,tblen,
```

allows
an erasure pattern vector, * opmode*,

`dectype`

`eraspat`

, to be specified
for the input `code`

, where the `1`

s
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, `1`

s
indicate erasures in the input code.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(...,'
```

is the same as the earlier syntaxes, except that the decoder starts with its state metrics,
traceback states, and traceback inputs specified by `cont`

',...,initmetric,initstates,initinputs) `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(...,'
```

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. `cont`

',...)`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`

.

The *t*^{th} column
of *P*_{1} shows the *t*-1^{th} time
step states given the inputs listed in the input matrix. For example,
the value in the *i*^{th} 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 *i*^{th} row
of the *t*^{th} column of
the input matrix.

The *P*_{1} 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
*m*_{1} –1), the traceback matrix starts from state
`0`

, looking at the first row
(`0`

^{th} state) of the last column of
*P*_{1}, ([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 14^{th} column of *P*_{1} ([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 *P*_{1} ([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 *P*_{1} ([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 *P*_{1} ([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 given time, use
*m*_{1}. The smallest number in
*m*_{1} represents the best state.

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 (Simulink) 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.

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