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