Decoding via Sampling

Shigeki MIYAKE  Jun MURAMATSU  Takahiro YAMAGUCHI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E102-A   No.11   pp.1512-1523
Publication Date: 2019/11/01
Online ISSN: 1745-1337
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)>>
Buy this Article




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 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.