
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Decoding via Sampling
Shigeki MIYAKE Jun MURAMATSU Takahiro YAMAGUCHI
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E102A
No.11
pp.15121523 Publication Date: 2019/11/01
Online ISSN: 17451337
DOI: 10.1587/transfun.E102.A.1512
Type of Manuscript: PAPER Category: Coding Theory Keyword: sampling decoding, MCMC, constrained random number generator, universal decoding, Markov source,
Full Text: PDF(1.3MB)>>
Summary:
We propose a novel decoding algorithm called “sampling decoding”, which is constructed using a Markov Chain Monte Carlo (MCMC) method and implements Maximum a Posteriori Probability decoding in an approximate manner. It is also shown that sampling decoding can be easily extended to universal coding or to be applicable for Markov sources. In simulation experiments comparing the proposed algorithm with the sumproduct decoding algorithm, sampling decoding is shown to perform better as sample size increases, although decoding time becomes proportionally longer. The mixing time, which measures how large a sample size is needed for the MCMC process to converge to the limiting distribution, is evaluated for a simple coding matrix construction.

