Efficient Maximum Likelihood Decoding Algorithms for Linear Codes over <I>Z</I>-Channel

Tomohiko UYEMATSU

Efficient Maximum Likelihood Decoding Algorithms for Linear Codes over Z-Channel

Tomohiko UYEMATSU

Full Text Views

0

Share
Cite this

Summary :

This paper presents two new maximum likelihood decoding (MLD) algorithms for linear codes over Z-channel, which are much more efficient than conventional exhaustive algorithms for high rate codes. In the proposed algorithms, their complexities are reduced by employing the projecting set C_s of the code, which is determined by the "projecting" structure of the code. Space and computational complexities of algorithms mainly depend upon the size of C_s which is usually several times smaller than the total number of codewords. It is shown that the upper bounds on computational complexities of decoding algorithms are in proportion to the number of parity bits and the distance between an initial estimate of the codeword and the received word, respectively, while space complexities of them are equal to the size of C_s. Lastly, numerical examples clarify the average computational complexities of the proposed algorithms, and the efficiency of these algorithms for high rate codes is confirmed.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E76-A No.9 pp.1430-1436

Publication Date: 1993/09/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)

Category

Cite this

Copy

Tomohiko UYEMATSU, "Efficient Maximum Likelihood Decoding Algorithms for Linear Codes over Z-Channel" in IEICE TRANSACTIONS on Fundamentals, vol. E76-A, no. 9, pp. 1430-1436, September 1993, doi: .
Abstract: This paper presents two new maximum likelihood decoding (MLD) algorithms for linear codes over Z-channel, which are much more efficient than conventional exhaustive algorithms for high rate codes. In the proposed algorithms, their complexities are reduced by employing the projecting set C_s of the code, which is determined by the "projecting" structure of the code. Space and computational complexities of algorithms mainly depend upon the size of C_s which is usually several times smaller than the total number of codewords. It is shown that the upper bounds on computational complexities of decoding algorithms are in proportion to the number of parity bits and the distance between an initial estimate of the codeword and the received word, respectively, while space complexities of them are equal to the size of C_s. Lastly, numerical examples clarify the average computational complexities of the proposed algorithms, and the efficiency of these algorithms for high rate codes is confirmed.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/e76-a_9_1430/_p

Copy

@ARTICLE{e76-a_9_1430,
author={Tomohiko UYEMATSU, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Efficient Maximum Likelihood Decoding Algorithms for Linear Codes over Z-Channel},
year={1993},
volume={E76-A},
number={9},
pages={1430-1436},
abstract={This paper presents two new maximum likelihood decoding (MLD) algorithms for linear codes over Z-channel, which are much more efficient than conventional exhaustive algorithms for high rate codes. In the proposed algorithms, their complexities are reduced by employing the projecting set C_s of the code, which is determined by the "projecting" structure of the code. Space and computational complexities of algorithms mainly depend upon the size of C_s which is usually several times smaller than the total number of codewords. It is shown that the upper bounds on computational complexities of decoding algorithms are in proportion to the number of parity bits and the distance between an initial estimate of the codeword and the received word, respectively, while space complexities of them are equal to the size of C_s. Lastly, numerical examples clarify the average computational complexities of the proposed algorithms, and the efficiency of these algorithms for high rate codes is confirmed.},
keywords={},
doi={},
ISSN={},
month={September},}

Copy

TY - JOUR
TI - Efficient Maximum Likelihood Decoding Algorithms for Linear Codes over Z-Channel
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1430
EP - 1436
AU - Tomohiko UYEMATSU
PY - 1993
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E76-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 1993
AB - This paper presents two new maximum likelihood decoding (MLD) algorithms for linear codes over Z-channel, which are much more efficient than conventional exhaustive algorithms for high rate codes. In the proposed algorithms, their complexities are reduced by employing the projecting set C_s of the code, which is determined by the "projecting" structure of the code. Space and computational complexities of algorithms mainly depend upon the size of C_s which is usually several times smaller than the total number of codewords. It is shown that the upper bounds on computational complexities of decoding algorithms are in proportion to the number of parity bits and the distance between an initial estimate of the codeword and the received word, respectively, while space complexities of them are equal to the size of C_s. Lastly, numerical examples clarify the average computational complexities of the proposed algorithms, and the efficiency of these algorithms for high rate codes is confirmed.
ER -