Fast algorithm for generating candidate codewords in reliability-based maximum likelihood decoding

Hideki Yagi; Toshiyasu Matsushima; Shigeichi Hirasawa

doi:10.1093/ietfec/e89-a.10.2676

Fast algorithm for generating candidate codewords in reliability-based maximum likelihood decoding

Hideki Yagi^*, Toshiyasu Matsushima, Shigeichi Hirasawa

^*Corresponding author for this work

School of Fundamental Science and Engineering

Research output: Contribution to journal › Article › peer-review

4 Citations (Scopus)

Abstract

We consider the reliability-based heuristic search methods for maximum likelihood decoding, which generate test error patterns (or, equivalently, candidate codewords) according to their heuristic values. Some studies have proposed methods for reducing the space complexity of these algorithms, which is crucially large for long block codes at medium to low signal to noise ratios of the channel. In this paper, we propose a new method for reducing the time complexity of generating candidate codewords by storing some already generated candidate codewords. Simulation results show that the increase of memory size is small.

Original language	English
Pages (from-to)	2676-2683
Number of pages	8
Journal	IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Volume	E89-A
Issue number	10
DOIs	https://doi.org/10.1093/ietfec/e89-a.10.2676
Publication status	Published - 2006 Oct

Keywords

Binary block codes
Maximum likelihood decoding
Most reliable basis
Priority-first search
Reliability

ASJC Scopus subject areas

Signal Processing
Computer Graphics and Computer-Aided Design
Electrical and Electronic Engineering
Applied Mathematics

Access to Document

10.1093/ietfec/e89-a.10.2676

Cite this

@article{78cbb7aac311415c9c4879a53560ebc2,

title = "Fast algorithm for generating candidate codewords in reliability-based maximum likelihood decoding",

abstract = "We consider the reliability-based heuristic search methods for maximum likelihood decoding, which generate test error patterns (or, equivalently, candidate codewords) according to their heuristic values. Some studies have proposed methods for reducing the space complexity of these algorithms, which is crucially large for long block codes at medium to low signal to noise ratios of the channel. In this paper, we propose a new method for reducing the time complexity of generating candidate codewords by storing some already generated candidate codewords. Simulation results show that the increase of memory size is small.",

keywords = "Binary block codes, Maximum likelihood decoding, Most reliable basis, Priority-first search, Reliability",

author = "Hideki Yagi and Toshiyasu Matsushima and Shigeichi Hirasawa",

year = "2006",

month = oct,

doi = "10.1093/ietfec/e89-a.10.2676",

language = "English",

volume = "E89-A",

pages = "2676--2683",

journal = "IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences",

issn = "0916-8508",

publisher = "Maruzen Co., Ltd/Maruzen Kabushikikaisha",

number = "10",

}

TY - JOUR

T1 - Fast algorithm for generating candidate codewords in reliability-based maximum likelihood decoding

AU - Yagi, Hideki

AU - Matsushima, Toshiyasu

AU - Hirasawa, Shigeichi

PY - 2006/10

Y1 - 2006/10

N2 - We consider the reliability-based heuristic search methods for maximum likelihood decoding, which generate test error patterns (or, equivalently, candidate codewords) according to their heuristic values. Some studies have proposed methods for reducing the space complexity of these algorithms, which is crucially large for long block codes at medium to low signal to noise ratios of the channel. In this paper, we propose a new method for reducing the time complexity of generating candidate codewords by storing some already generated candidate codewords. Simulation results show that the increase of memory size is small.

AB - We consider the reliability-based heuristic search methods for maximum likelihood decoding, which generate test error patterns (or, equivalently, candidate codewords) according to their heuristic values. Some studies have proposed methods for reducing the space complexity of these algorithms, which is crucially large for long block codes at medium to low signal to noise ratios of the channel. In this paper, we propose a new method for reducing the time complexity of generating candidate codewords by storing some already generated candidate codewords. Simulation results show that the increase of memory size is small.

KW - Binary block codes

KW - Maximum likelihood decoding

KW - Most reliable basis

KW - Priority-first search

KW - Reliability

UR - http://www.scopus.com/inward/record.url?scp=33750067075&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33750067075&partnerID=8YFLogxK

U2 - 10.1093/ietfec/e89-a.10.2676

DO - 10.1093/ietfec/e89-a.10.2676

M3 - Article

AN - SCOPUS:33750067075

SN - 0916-8508

VL - E89-A

SP - 2676

EP - 2683

JO - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

JF - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

IS - 10

ER -

Fast algorithm for generating candidate codewords in reliability-based maximum likelihood decoding

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this