Decoding linear block codes using a priority-first search: Performance analysis and suboptimal version

Yunghsiang S. Han; Carlos R.P. Hartmann; Kishan G. Mehrotra

doi:10.1109/18.669296

Decoding linear block codes using a priority-first search: Performance analysis and suboptimal version

Yunghsiang S. Han, Carlos R.P. Hartmann, Kishan G. Mehrotra

Department of Electrical Engineering & Computer Science

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

18 Scopus citations

Abstract

An efficient maximum-likelihood soft-decision decoding algorithm for linear block codes using a generalized Dijkstra's algorithm was proposed by Han, Hartmann, and Chen. In this correspondence we prove that this algorithm is efficient for most practical communication systems where the probability of error is less than 10^-3 by finding an upper bound of the computational effort of the algorithm. A suboptimal decoding algorithm is also proposed. The performance of this suboptimal decoding algorithm is within 0.25 dB of the performance of an optimal decoding algorithm for the (104, 52) binary extended quadratic residue code, and within 0.5 dB of the optimal performance for the (128, 64) binary BCH code, respectively.

Original language	English (US)
Pages (from-to)	1233-1246
Number of pages	14
Journal	IEEE Transactions on Information Theory
Volume	44
Issue number	3
DOIs	https://doi.org/10.1109/18.669296
State	Published - 1998

Keywords

Block codes
Decoding
Dijkstra's algorithm
Maximum-likelihood
Soft-decision
Suboptimal

ASJC Scopus subject areas

Information Systems
Computer Science Applications
Library and Information Sciences

Access to Document

10.1109/18.669296

Cite this

@article{0e5fe029f3574931b6926f90e1cabc58,

title = "Decoding linear block codes using a priority-first search: Performance analysis and suboptimal version",

abstract = "An efficient maximum-likelihood soft-decision decoding algorithm for linear block codes using a generalized Dijkstra's algorithm was proposed by Han, Hartmann, and Chen. In this correspondence we prove that this algorithm is efficient for most practical communication systems where the probability of error is less than 10-3 by finding an upper bound of the computational effort of the algorithm. A suboptimal decoding algorithm is also proposed. The performance of this suboptimal decoding algorithm is within 0.25 dB of the performance of an optimal decoding algorithm for the (104, 52) binary extended quadratic residue code, and within 0.5 dB of the optimal performance for the (128, 64) binary BCH code, respectively.",

keywords = "Block codes, Decoding, Dijkstra's algorithm, Maximum-likelihood, Soft-decision, Suboptimal",

author = "Han, {Yunghsiang S.} and Hartmann, {Carlos R.P.} and Mehrotra, {Kishan G.}",

note = "Funding Information: Manuscript received April 11, 1994; revised September 24, 1997. This work was supported in part by the National Science Foundation under Grant NCR-9205422 and used the computational facilities of the Northeast Parallel Architectures Center (NPAC) at Syracuse University. The work of Y. S. Han was supported in part by the National Science Council R.O.C. under Grant NSC 84-2213-E-211-004. The material in this correspondence was presented in part at the IEEE International Symposium on Information Theory, Trondheim, Norway, June 1994.",

year = "1998",

doi = "10.1109/18.669296",

language = "English (US)",

volume = "44",

pages = "1233--1246",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "3",

}

TY - JOUR

T1 - Decoding linear block codes using a priority-first search

T2 - Performance analysis and suboptimal version

AU - Han, Yunghsiang S.

AU - Hartmann, Carlos R.P.

AU - Mehrotra, Kishan G.

N1 - Funding Information: Manuscript received April 11, 1994; revised September 24, 1997. This work was supported in part by the National Science Foundation under Grant NCR-9205422 and used the computational facilities of the Northeast Parallel Architectures Center (NPAC) at Syracuse University. The work of Y. S. Han was supported in part by the National Science Council R.O.C. under Grant NSC 84-2213-E-211-004. The material in this correspondence was presented in part at the IEEE International Symposium on Information Theory, Trondheim, Norway, June 1994.

PY - 1998

Y1 - 1998

N2 - An efficient maximum-likelihood soft-decision decoding algorithm for linear block codes using a generalized Dijkstra's algorithm was proposed by Han, Hartmann, and Chen. In this correspondence we prove that this algorithm is efficient for most practical communication systems where the probability of error is less than 10-3 by finding an upper bound of the computational effort of the algorithm. A suboptimal decoding algorithm is also proposed. The performance of this suboptimal decoding algorithm is within 0.25 dB of the performance of an optimal decoding algorithm for the (104, 52) binary extended quadratic residue code, and within 0.5 dB of the optimal performance for the (128, 64) binary BCH code, respectively.

AB - An efficient maximum-likelihood soft-decision decoding algorithm for linear block codes using a generalized Dijkstra's algorithm was proposed by Han, Hartmann, and Chen. In this correspondence we prove that this algorithm is efficient for most practical communication systems where the probability of error is less than 10-3 by finding an upper bound of the computational effort of the algorithm. A suboptimal decoding algorithm is also proposed. The performance of this suboptimal decoding algorithm is within 0.25 dB of the performance of an optimal decoding algorithm for the (104, 52) binary extended quadratic residue code, and within 0.5 dB of the optimal performance for the (128, 64) binary BCH code, respectively.

KW - Block codes

KW - Decoding

KW - Dijkstra's algorithm

KW - Maximum-likelihood

KW - Soft-decision

KW - Suboptimal

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

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

U2 - 10.1109/18.669296

DO - 10.1109/18.669296

M3 - Article

AN - SCOPUS:0032070198

SN - 0018-9448

VL - 44

SP - 1233

EP - 1246

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 3

ER -

Decoding linear block codes using a priority-first search: Performance analysis and suboptimal version

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this