locked
Having trouble using Infer.NET to Decode an LDPC codeword RRS feed

  • Question

  • I’m running into problems with one of the examples I’m investigating and wanted to see if I’m using Infer.NET incorrectly.  Specifically, I’m trying to use belief propagation to decode an LDPC codeword.  I went ahead and combined the demapper with the decoder since this was easy to do with Infer.NET.

    The code is parameterized by numBits, numCheckEquations, and bitsPerCheckEquation.  When I set these to small values  (like 6,6, and 3), it runs fine and seems to be doing the right thing.  As soon as I increase these to more useful numbers (like 1000,300, and 10) it fails to run.  It goes out to lunch for quite some time.  The one time I let it run for a few minutes it returned with an “OutOfMemory” error.  Also, I’m randomly generating the adjacency matrix for the sake of being able to scale the problem up or down and sometimes Infer.NET fails to compile the generated model.

    A hand coded implementation of BP for this problem can run in under a second (with parameters of 1000,300,10) so  I’m wondering if I should be modeling the problem differently.  I’d be curious to know why this particular program runs as slowly as it does.  I haven’t used Infer.NET very much so I wouldn’t be surpised at all if I was using it inefficiently.

    It's a bit long, but here's the code:

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using MicrosoftResearch.Infer.Models;
    using MicrosoftResearch.Infer;
    using MicrosoftResearch.Infer.Distributions;
    using System.Diagnostics;

    namespace InferNetFun
    {
        class Program
        {
            static Random _random = new Random();

            /*
             * This program does the following:
             * 1.  Specify a number of bits
             * 2.  Specify a number of check equations
             * 3.  Specify the number of bits per check equation
             * 4.  Create and run the decoder with these parameters.
             */
            static void Main(string[] args)
            {
                int numBits = 6;
                int numCheckEquations = 6;
                int bitsPerCheckEquation = 3;
                bool printCheckEquations = false;
                bool showFactorGraph = false;

                Stopwatch sw = Stopwatch.StartNew();
                runDecoder(numBits, numCheckEquations, bitsPerCheckEquation,printCheckEquations,showFactorGraph);
                sw.Stop();

                Console.WriteLine("Time: " + sw.ElapsedMilliseconds);
                Console.WriteLine("hit return to continue");
                Console.ReadKey();
                 

            }

            /*
             * This method does the following:
             * 1. Generates random adjacency matrix
             * 2. Builds Decoder/Demapper FactorGraph
             * 3. Generates observations
             * 4. Runs inference
             * 5. Prints out results.
             */
            private static void runDecoder(int numBits, int numCheckEquations, 
                int numBitsPerCheckEquation, bool printCheckEquations,bool showFactorGraph)
            {

                Variable<double> variance = Variable.New<double>();

                //Transmitted bits
                VariableArray<bool> x = null;

                //Observed values after noise.
                VariableArray<double> y = null;

                //Set noise variance to 1.
                variance.ObservedValue = 1;

                //Create a random adjacency matrix
                Console.WriteLine("Generating adjacency matrix...");
                bool[][] A = new bool[numCheckEquations][];
                for (int i = 0; i < A.Length; i++)
                {
                    A[i] = new bool[numBits];
                    int[] indices = getPermutation(numBits, numBitsPerCheckEquation);
                    for (int j = 0; j < indices.Length; j++)
                        A[i][indices[j]] = true;

                    if (printCheckEquations)
                    {
                        Console.Write("check[{0}]: ", i);
                        for (int j = 0; j < indices.Length; j++)
                            Console.Write(" {0}",indices[j]);
                        Console.WriteLine();
                    }
                }


                Console.WriteLine("Building Factor Graph...");
                //Create the decoder Factor Graph (including the demapper)
                bool doDecode = true;
                buildDecoderWithDemapper(A, numBits, doDecode, out x, out y, out variance);

                //Create an all zeros codeword.  This will always be a valid codeword
                //regardless of the adjacency matrix.
                double[] observed = new double[numBits];
                for (int i = 0; i < observed.Length; i++)
                    observed[i] = 1;

                //Set the observations.
                y.ObservedValue = observed;
                variance.ObservedValue = 1;

                //Run inference.
                InferenceEngine ie = new InferenceEngine();
                ie.ShowFactorGraph = showFactorGraph;

                Console.WriteLine("Running inference...");
                Bernoulli[] b = ie.Infer<Bernoulli[]>(x);

                //Print out the results.
                for (int i = 0; i < numBits; i++)
                    Console.WriteLine(b[i].GetProbTrue());

            }

            /*
             * Builds a FactorGraph for a demapper and decoder.
             */
            private static void buildDecoderWithDemapper(bool[][] A, int numBits, bool doDecode, out VariableArray<bool> x, out VariableArray<double> y, out Variable<double> variance)
            {

                Range r = new Range(numBits);

                //x represents the bits we want to recover.
                x = Variable.Array<bool>(r).Named("x");

                //I'm using these only because I can't use a bool with a mixture of gaussians.  
                //QUESTION: Can we really not use bool values with a mixture of gaussians?
                VariableArray<int> intermediate = Variable.Array<int>(r).Named("Intermediate");

                //These represent the received symobls after noise corrupts them.
                y = Variable.Array<double>(r).Named("y");

                //The variance of the noise.
                variance = Variable.New<double>().Named("Variance");

                //Loop through all bits.
                using (Variable.ForEach(r))
                {
                    //Initialize the bits.
                    x[r] = Variable<bool>.Bernoulli(.5);
                    intermediate[r] = Variable<int>.Discrete(.5, .5);

                    //Map the bits to the integers
                    //QUESTION: Is this really necessary?
                    using (Variable.If(x[r]))
                    {
                        Variable.ConstrainEqual(intermediate[r], 1);
                    }
                    using (Variable.IfNot(x[r]))
                    {
                        Variable.ConstrainEqual(intermediate[r], 0);
                    }


                    //Create the mixture of gaussians.
                    using (Variable.Case(intermediate[r], 0))
                    {
                        //0s map to 1
                        y[r].SetTo(Variable.GaussianFromMeanAndVariance(1, variance));
                    }
                    using (Variable.Case(intermediate[r], 1))
                    {
                        //1s map to -1
                        y[r].SetTo(Variable.GaussianFromMeanAndVariance(-1, variance));
                    }

                }

                //We can set doDecode to False if we want to turn off decoding for the sake of debugging.
                if (doDecode)
                {
                    int numFactors = A.Length;

                    //Loop through the factors.
                    for (int i = 0; i < numFactors; i++)
                    {
                        //Use the adjacency matrix to pick off bits for this factor.
                        //QUESTION: Is this what's slowing us down since we're pickin off Variables from the array?
                        //          Is there some way to vectorize this?  Would that make a difference?
                        List<int> al = new List<int>();
                        for (int j = 0; j < numBits; j++)
                        {
                            if (A[i][j])
                                al.Add(j);
                        }
                        Variable<bool>[] input = new Variable<bool>[al.Count];
                        for (int j = 0; j < al.Count; j++)
                        {
                            input[j] = x[al[j]];
                        }

                        //Create the xor constraint for this factor.
                        addXorConstraint(input);
                    }
                }
            }

            /*
             * This function randomly selects N indices from 0 to numVars-1
             * It's used to create random constraints.  This is not a useful
             * way to build a good code, but it's useful for generating 
             * random codes for the sake of investigating run times.
             */
            private static int[] getPermutation(int numVars, int N)
            {
                int[] retval = new int[N];
                for (int i = 0; i < N; i++)
                    retval[i] = -1;

                for (int i = 0; i < N; i++)
                {
                    bool isValid = false;
                    int index = 0;
                    while (!isValid)
                    {
                        index = _random.Next() % numVars;
                        isValid = true;
                        for (int j = 0; j < i; j++)
                            if (retval[j] == index)
                            {
                                isValid = false;
                                break;
                            }
                    }
                    retval[i] = index;
                }
                return retval;
            }

            //QUESTION: xor is really not defined?
            public static Variable<bool> xor(Variable<bool> a, Variable<bool> b)
            {
                return a != b;
            }

            //We want to constrain the variables to sum to 0 (mod 2)
            //QUESTION: Is there a better way to do this to take advantage of
            //          Infer.NET?  We could make a shallower tree of xors
            //          but I was too lazy to code that and it shouldn't make
            //          such a huge difference to explain the slowness of this code.
            public static void addXorConstraint(params Variable<bool>[] vars)
            {

                Variable<bool> tmp = vars[0];
                for (int i = 1; i < vars.Length; i++)
                    tmp = xor(vars[i], tmp);

                Variable<bool>.ConstrainEqual(tmp, false);
            }


        }
    }




    • Edited by Shawn Hershey Friday, September 21, 2012 3:39 PM fix formatting.
    Wednesday, September 19, 2012 6:50 PM

All replies

  • Hi Shawn

    Apologies for the delay in replying to this. We've been working on an upgraded release, and this is now posted. You can get something like your original post to work with a few modifications, but everything possible should use ranges rather than .NET arrays - otherwise the generated code will be unrolled to a size that will cause problems for the C# compiler.

    A better solution is shown below. This does need the new version of Infer.NET, however.

    John

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using MicrosoftResearch.Infer.Models;
    using MicrosoftResearch.Infer;
    using MicrosoftResearch.Infer.Distributions;
    using System.Diagnostics;
    using MicrosoftResearch.Infer.Maths;
    using MicrosoftResearch.Infer.Utils;
     
    namespace InferNetFun
     {
    	class Program
    	{
    		static void Main(string[] args)
    		{
    			Rand.Restart(1);
    			int numBits = 1000;
    			int numCheckEquations = 300;
    			int bitsPerCheckEquation = 10;
    
    			var model = new DecoderDemapperModel();
    			model.NumBits.ObservedValue = numBits;
    			model.NumCheckEquations.ObservedValue = numCheckEquations;
    			model.NumBitsPerCheckEquation.ObservedValue = bitsPerCheckEquation;
    			model.Indices.ObservedValue = Util.ArrayInit(numCheckEquations, i => Rand.Perm(numBits).Take(bitsPerCheckEquation).ToArray());
    			model.Variance.ObservedValue = 1.0; // Noise variance
    			model.Y.ObservedValue = Util.ArrayInit(numBits, i => Bernoulli.Sample(0.5) ? 1.0 : -1.0);
    			model.Engine.ShowTimings = true;
    			var inferredX = model.Engine.Infer<IList<Bernoulli>>(model.X);
    			foreach (var b in inferredX)
    				Console.Write("{0:0.00},", b.GetProbTrue());
    			Console.WriteLine("\nHit return to continue");
    			Console.ReadKey();
    		}
    	}
    
    	/// <summary>
        /// Decoder/Demapper Model
    	/// </summary>
    	public class DecoderDemapperModel
    	{
    		public Variable<int> NumBits;
    		public Variable<int> NumCheckEquations;
    		public Variable<int> NumBitsPerCheckEquation;
    		public VariableArray<bool> X; //Transmitted bits
    		public VariableArray<double> Y; // Observed values after noise
    		public Variable<double> Variance; // Noise variance
    		public VariableArray<VariableArray<int>, int[][]> Indices;
    		public InferenceEngine Engine = new InferenceEngine();
    
    		public DecoderDemapperModel()
    		{
    			NumBits = Variable.New<int>();
    			Range r = new Range(NumBits);
    			NumCheckEquations = Variable.New<int>();
    			Range c = new Range(NumCheckEquations);
    			NumBitsPerCheckEquation = Variable.New<int>();
    			Range b = new Range(NumBitsPerCheckEquation);
    			X = Variable.Array<bool>(r);
                Y = Variable.Array<double>(r);
    			Variance = Variable.New<double>();
    			Indices = Variable.Array(Variable.Array<int>(b), c);
    
                using (Variable.ForEach(r))
                {
    				X[r] = Variable.Bernoulli(0.5);
    				using (Variable.If(X[r]))
                    {
                        Y[r].SetTo(Variable.GaussianFromMeanAndVariance(1.0, Variance));
                    }
                    using (Variable.IfNot(X[r]))
                    {
                        Y[r].SetTo(Variable.GaussianFromMeanAndVariance(-1.0, Variance));
                    }
                }
    
    			// Parity condition
    			using (Variable.ForEach(c))
    			{
    				var input = Variable.Subarray(X, Indices[c]);
    				var parity = Variable.Array<bool>(b);
    
    				using (var block = Variable.ForEach(b))
    				{
    					var i = block.Index;
    					using (Variable.If(i == 0))
    					{
    						parity[i] = Variable.Copy(input[0]);
    					}
    					using (Variable.If(i > 0))
    					{
    						parity[i] = input[i] != parity[i - 1];
    					}
    				}
    
    				Variable.ConstrainFalse(parity[(Variable<int>)b.Size - 1]);
    			}
    		}
    	}
    }
     
    
    
    

    Thursday, October 4, 2012 7:14 AM
    Owner
  • Great!  Thanks!  I just noticed this response now.  When you say it requires the new version, do you mean the Infer.NET 2.5 Beta 1 Release?
    Tuesday, November 13, 2012 10:27 PM
  • Yes! (It was new when I responded).
    Wednesday, November 14, 2012 8:56 AM
    Owner