For Full-Text 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
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2019/11/01
Online ISSN: 1745-1337
Type of Manuscript: PAPER
Category: Coding Theory
sampling decoding, MCMC, constrained random number generator, universal decoding, Markov source,
Full Text: PDF(1.3MB)>>
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 sum-product 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.