J. Phys. Soc. Jpn. 77 (2008) 103801 (3 pages) |Previous Article| |Next Article| |Table of Contents|
|Full Text PDF (139K)| |Buy This Article|
Testing Error Correcting Codes by Multicanonical Sampling of Rare Events
The Institute of Statistical Mathematics, 4-6-7 Minami-Azabu, Minato-ku, Tokyo 106-8569
1Department of Basic Science, University of Tokyo, 3-8-1 Komaba, Meguro-ku, Tokyo 153-8902
(Received April 10, 2008; Accepted July 24, 2008; Published September 25, 2008)
The idea of rare-event sampling by the multicanonical Monte Carlo is applied to the estimation of the performance of error correcting codes. The essence of the idea is importance sampling of the pattern of noise in the channel by the multicanonical Monte Carlo, which enables efficient estimation of the tails of the distribution of bit errors. The proposed method is successfully tested with a convolutional code.
©2008 The Physical Society of Japan
KEYWORDS:error correcting code, rare event, large deviation, multicanonical Monte Carlo
- R. G. Gallager: Information Theory and Reliable Communication (Wiley, New York, 1968).
- D. J. C. MacKay: Information Theory, Inference, and Learning Algorithms (Cambridge University Press, Cambridge, U.K., 2003).
- H. Nishimori: Statistical Physics of Spin Glasses and Information Processing: An Introduction (Oxford University Press, Oxford, U.K., 2001).
- B. A. Berg and T. Celik:
Phys. Rev. Lett. 69 (1992) 2292[APS].
- B. A. Berg and T. Neuhaus:
Phys. Lett. B 267 (1991) 249[CrossRef].
- J. Lee:
Phys. Rev. Lett. 71 (1993) 211[APS].
- Y. Iba: Int. J. Mod. Phys. C 12 (2001) 623.
- J. D. Lafferty and L. A. Wasserman: Proc. 17th Conf. Uncertainty in Artificial Intelligence, 2001, p. 293.
- J. Dauwels: Proc. 26th Symp. Information Theory in the BENELUX, Brussels, Belgium, 2005, p. 221.
- A. K. Hartmann:
Phys. Rev. E 65 (2002) 056102[APS].
- M. Körner, H. G. Katzgraber, and A. K. Hartmann: J. Stat. Mech. (2006) P04005.
- C. Monthus and T. Garel:
Phys. Rev. E 74 (2006) 051109[APS].
- K. Hukushima and Y. Iba:
J. Phys.: Conf. Ser. 95 (2008) 012005[IoP STACKS].
- Y. Matsuda, H. Nishimori, and K. Hukushima:
J. Phys. A 41 (2008) 324012[IoP STACKS].
- A zero–one asymmetry is introduced in our implementation of the Viterbi decoder by the choice of 0 or 1 when the weight is equal. It breaks the gauge invariance and considerably affects the results quantitatively, while qualitative characteristics do not change. This effect could be reduced by averaging over the results with several values of x or treating x as a stochastic variable.