Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

A Closed Form Expression for the Exact Bit Error Probability for Viterbi Decoding of Convolutional Codes

Bocharova, Irina LU ; Hug, Florian LU ; Johannesson, Rolf LU and Kudryashov, Boris LU (2012) In IEEE Transactions on Information Theory 58(7). p.4635-4644
Abstract
In 1995, Best et al. published a formula for the exact bit error probability for Viterbi decoding of the rate R=1/2, memory m=1 (2-state) convolutional encoder with generator matrix G(D)=(1 1+D) when used to communicate over the binary symmetric channel. Their formula was later extended to the rate R=1/2, memory m=2 (4-state) convolutional encoder with generator matrix G(D)=(1+D^2 1+D+D^2) by Lentmaier et al.



In this paper, a different approach to derive the exact bit error probability is described. A general recurrent matrix equation, connecting the average information weight at the current and previous states of a trellis section of the Viterbi decoder, is derived and solved. The general solution of this matrix... (More)
In 1995, Best et al. published a formula for the exact bit error probability for Viterbi decoding of the rate R=1/2, memory m=1 (2-state) convolutional encoder with generator matrix G(D)=(1 1+D) when used to communicate over the binary symmetric channel. Their formula was later extended to the rate R=1/2, memory m=2 (4-state) convolutional encoder with generator matrix G(D)=(1+D^2 1+D+D^2) by Lentmaier et al.



In this paper, a different approach to derive the exact bit error probability is described. A general recurrent matrix equation, connecting the average information weight at the current and previous states of a trellis section of the Viterbi decoder, is derived and solved. The general solution of this matrix equation yields a closed form expression for the exact bit error probability. As special cases, the expressions obtained by Best et al. for the 2-state encoder and by Lentmaier et al. for a 4-state encoder are obtained. The closed form expression derived in this paper is evaluated for various realizations of encoders, including rate R=1/2 and R=2/3 encoders, of as many as 16 states.



Moreover, it is shown that it is straightforward to extend the approach to communication over the quantized additive white Gaussian noise channel. (Less)
Please use this url to cite or link to this publication:
author
; ; and
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
additive white Gaussian noise channel, binary symmetric channel, bit error probability, convolutional code, convolutional encoder, exact bit error probability, Viterbi decoding
in
IEEE Transactions on Information Theory
volume
58
issue
7
pages
4635 - 4644
publisher
IEEE - Institute of Electrical and Electronics Engineers Inc.
external identifiers
  • wos:000305575000033
  • scopus:84862522819
ISSN
0018-9448
DOI
10.1109/TIT.2012.2193375
language
English
LU publication?
yes
id
efaebb6a-d2a4-4b26-94bc-28d4db0fe842 (old id 2430435)
date added to LUP
2016-04-01 13:23:31
date last changed
2022-01-27 18:57:36
@article{efaebb6a-d2a4-4b26-94bc-28d4db0fe842,
  abstract     = {{In 1995, Best et al. published a formula for the exact bit error probability for Viterbi decoding of the rate R=1/2, memory m=1 (2-state) convolutional encoder with generator matrix G(D)=(1 1+D) when used to communicate over the binary symmetric channel. Their formula was later extended to the rate R=1/2, memory m=2 (4-state) convolutional encoder with generator matrix G(D)=(1+D^2 1+D+D^2) by Lentmaier et al.<br/><br>
<br/><br>
In this paper, a different approach to derive the exact bit error probability is described. A general recurrent matrix equation, connecting the average information weight at the current and previous states of a trellis section of the Viterbi decoder, is derived and solved. The general solution of this matrix equation yields a closed form expression for the exact bit error probability. As special cases, the expressions obtained by Best et al. for the 2-state encoder and by Lentmaier et al. for a 4-state encoder are obtained. The closed form expression derived in this paper is evaluated for various realizations of encoders, including rate R=1/2 and R=2/3 encoders, of as many as 16 states.<br/><br>
<br/><br>
Moreover, it is shown that it is straightforward to extend the approach to communication over the quantized additive white Gaussian noise channel.}},
  author       = {{Bocharova, Irina and Hug, Florian and Johannesson, Rolf and Kudryashov, Boris}},
  issn         = {{0018-9448}},
  keywords     = {{additive white Gaussian noise channel; binary symmetric channel; bit error probability; convolutional code; convolutional encoder; exact bit error probability; Viterbi decoding}},
  language     = {{eng}},
  number       = {{7}},
  pages        = {{4635--4644}},
  publisher    = {{IEEE - Institute of Electrical and Electronics Engineers Inc.}},
  series       = {{IEEE Transactions on Information Theory}},
  title        = {{A Closed Form Expression for the Exact Bit Error Probability for Viterbi Decoding of Convolutional Codes}},
  url          = {{https://lup.lub.lu.se/search/files/3340882/2430437.pdf}},
  doi          = {{10.1109/TIT.2012.2193375}},
  volume       = {{58}},
  year         = {{2012}},
}