A Free Energy Minimization Framework for Inference Problems in Modulo 2 Arithmetic

David J C MacKay

This paper studies the task of inferring a binary vector s given noisy observations of the binary vector t = A s mod 2, where A is an M times N binary matrix. This task arises in correlation attack on a class of stream ciphers and in other decoding problems.

The unknown binary vector is replaced by a real vector of probabilities that are optimized by variational free energy minimization. The derived algorithms converge in computational time of order between w_{A} and N w_{A}, where w_{A} is the number of 1s in the matrix A, but convergence to the correct solution is not guaranteed.

Applied to error correcting codes based on sparse matrices A, these algorithms give a system with empirical performance comparable to that of BCH and Reed-Muller codes.

Applied to the inference of the state of a linear feedback shift register given the noisy output sequence, the algorithms offer a principled version of Meier and Staffelbach's (1989) algorithm B, thereby resolving the open problem posed at the end of their paper. The algorithms presented here appear to give superior performance.

Final version published by Springer: http://dx.doi.org/10.1007/3-540-60590-8_15 (link to SpringerLink website; subscribers only)

Short version to appear in Electronic Letters: postscript (53K). | pdf
Short version including pseudocode appendix: postscript (61K). | pdf
Long version: (in Proceedings of 1994 K.U. Leuven Workshop on Cryptographic Algorithms) postscript (101K). | pdf

@INPROCEEDINGS{MacKay94:fe,
 KEY		="MacKay",
 AUTHOR		="D. J. C. MacKay",
 TITLE		="A Free Energy Minimization Framework for 
	Inference Problems in Modulo 2 Arithmetic",
 BOOKTITLE      ="Fast Software Encryption (Proceedings of 1994 K.U. Leuven Workshop on
		  Cryptographic Algorithms)",
  editor =	 "B. Preneel",
  series =	 "Lecture Notes in Computer Science",
  number = 	 "1008",
 YEAR		=1995,
  publisher =	 "Springer-Verlag",
 PAGES		="179-195",
 ANNOTE ="Date submitted: 15 Jan 1995; Date accepted: 22 March 1995; Collaborating institutes:
		  Cambridge University Computer Laboratory"}

@ARTICLE{MacKay94:fes,
 KEY		="MacKay",
 AUTHOR		="D. J. C. MacKay",
 TITLE		="Free Energy Minimization Algorithm for Decoding
		  and Cryptanalysis",
 YEAR		=1995,
 JOURNAL="Electronics Letters",
 VOLUME =31,
 NUMBER=6,
 PAGES		="446-447",
 ANNOTE ="Date submitted: Jan 1995; Date accepted: 24 Feb 1995; Date
		  published: 16 March 1995; 
 Collaborating institutes: Cambridge University Computer Laboratory"}


David MacKay's: home page, publications.