Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

A BEAST for prowling in trees

Bocharova, Irina LU ; Handlery, Marc LU ; Johannesson, Rolf LU and Kudryashov, Boris LU (2004) In IEEE Transactions on Information Theory 50(6). p.1295-1302
Abstract
When searching for convolutional codes and tailbiting codes of high complexity it is of vital importance to use fast algorithms for computing their weight spectra, which corresponds to finding low-weight paths in their code trellises. This can be efficiently done by a combined search in both forward and backward code trees. A bidirectional efficient algorithm for searching such code trees (BEAST) is presented. For large encoder memories, it is shown that BEAST is significantly more efficient than comparable algorithms. BEAST made it possible to rind new convolutional and tailbiting codes that have larger free (minimum) distances than the previously best known codes with the same parameters. Tables of such codes are presented.
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
tailbiting codes, distance, convolutional codes, bidirectional search, free, distance spectrum
in
IEEE Transactions on Information Theory
volume
50
issue
6
pages
1295 - 1302
publisher
IEEE - Institute of Electrical and Electronics Engineers Inc.
external identifiers
  • wos:000221803300027
  • scopus:2942668327
ISSN
0018-9448
DOI
10.1109/TIT.2004.828093
language
English
LU publication?
yes
id
48a7d791-8ef2-4be4-8f66-1cedeccb9af8 (old id 276239)
date added to LUP
2016-04-01 16:59:43
date last changed
2022-01-28 23:34:00
@article{48a7d791-8ef2-4be4-8f66-1cedeccb9af8,
  abstract     = {{When searching for convolutional codes and tailbiting codes of high complexity it is of vital importance to use fast algorithms for computing their weight spectra, which corresponds to finding low-weight paths in their code trellises. This can be efficiently done by a combined search in both forward and backward code trees. A bidirectional efficient algorithm for searching such code trees (BEAST) is presented. For large encoder memories, it is shown that BEAST is significantly more efficient than comparable algorithms. BEAST made it possible to rind new convolutional and tailbiting codes that have larger free (minimum) distances than the previously best known codes with the same parameters. Tables of such codes are presented.}},
  author       = {{Bocharova, Irina and Handlery, Marc and Johannesson, Rolf and Kudryashov, Boris}},
  issn         = {{0018-9448}},
  keywords     = {{tailbiting codes; distance; convolutional codes; bidirectional search; free; distance spectrum}},
  language     = {{eng}},
  number       = {{6}},
  pages        = {{1295--1302}},
  publisher    = {{IEEE - Institute of Electrical and Electronics Engineers Inc.}},
  series       = {{IEEE Transactions on Information Theory}},
  title        = {{A BEAST for prowling in trees}},
  url          = {{http://dx.doi.org/10.1109/TIT.2004.828093}},
  doi          = {{10.1109/TIT.2004.828093}},
  volume       = {{50}},
  year         = {{2004}},
}