Bit-optimal decoding of codes whose Tanner graphs are trees

We introduce a group algebra formulation for bit-optimal decoding of binary block codes. We use this new framework to give a simple algebraic proof that Pearl's and Gallager's belief propagation decoding algorithms are bit-optimal when the Tanner graph of the code is a tree. We believe tha...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2003-05, Vol.128 (1), p.293-303
Main Authors: Soljanin, E, Offer, E
Format: Article
Language:English
Subjects:
Applied sciences
Bit-optimal decoding
Codes on graph
Coding, codes
Exact sciences and technology
Information, signal and communications theory
Iterative decoding
Signal and communications theory
Soft-output decoding
Telecommunications and information theory
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We introduce a group algebra formulation for bit-optimal decoding of binary block codes. We use this new framework to give a simple algebraic proof that Pearl's and Gallager's belief propagation decoding algorithms are bit-optimal when the Tanner graph of the code is a tree. We believe that these derivations of known results give new insights into the issues of decoding on graphs from the algebraic coding theorist's point of view.
ISSN:0166-218X
1872-6771
DOI:10.1016/S0166-218X(02)00452-3