formlp.py

著名的ldpc编解码的资料及源代码

                                         ' --model ' + modelFile  +
                                         ' -o ' + resultFile)
        if (s):
            print 'Output from calling LPSolver:\n', o
        varVals = self.ExtractVarValuesFromLPSolution(resultFile)
        return (varVals,s,o)

    def IterSolveLP(self,numIter,verbose=1):
        """
        numIter:  Maximum number of iterations to perform.

        Solve the LP then find the most certain variable and freeze it
        to the nearest value, solve the LP, freeze another var, etc.

        Returns the same 3-tuple as SolveLP().
        """

        channelData = self.channelData
        extraConstraints = []
        varsToCheck = {}
        for i in range(self.K):
            varsToCheck[i] = 1
        for i in range(numIter):
            if (verbose):
                print 'Doing iter ', i
            self.Reset()
            self.FormLP(channelData,string.join(extraConstraints))
            (v,s,o) = self.SolveLP()
            extraConstraints.append(self.FixCertainVars(varsToCheck,v))
            (varIndex,numAmbigousVars) = self.FindSureVarToForce(varsToCheck,v)
            if (-1 != varIndex):
                del varsToCheck[varIndex]
            if (numAmbigousVars == 0):
                if (verbose):
                    print 'Terminating since no ambiguous vars left.'
                return (v,s,o)
            else:
                valueToForce = round(v[varIndex])
                if (verbose):
                    print 'Found ', numAmbigousVars, ' ambiguous vars.'
                    print 'Forcing var ',varIndex,' to be ',valueToForce
                    print ' (old value was ', v[varIndex], ' )'
                extraConstraints.append('s.t. forceCon' + `i` + ': ' +
                                        ' relaxedVars[' + `varIndex` + '] = '
                                        + `valueToForce` + ';\n')
        return (v,s,o)

    def IterSolveLPDecimateAmbiguous(self,numIter,verbose=1):
        """
        numIter:  Maximum number of iterations to perform.

        Solve the LP then find an ambiguous variable and freeze it
        to the nearest value, solve the LP, freeze another var, etc.

        Returns the same 3-tuple as SolveLP().
        """
        channelData = self.channelData
        extraConstraints = []
        for i in range(numIter):
            if (verbose):
                print 'Doing iter ', i
            self.Reset()
            self.FormLP(channelData,string.join(extraConstraints))
            (v,s,o) = self.SolveLP()
            (varIndex,numAmbigousVars) = self.FindAmbiguousVarToForce(v)
            if (0.0 == v[varIndex] or
                1.0 == v[varIndex]):
                if (verbose):
                    print 'Terminating since no ambiguous vars left.'
                return (v,s,o)
            else:
                valueToForce = round(v[varIndex])
                if (verbose):
                    print 'Found ', numAmbigousVars, ' ambiguous vars.'
                    print 'Forcing var ', varIndex, ' to be ', valueToForce
                    print ' (old value was ', v[varIndex], ' )'
                extraConstraints.append('s.t. forceCon' + `i` + ': ' +
                                        ' relaxedVars[' + `varIndex` + '] = '
                                        + `valueToForce` + ';\n')
        return (v,s,o)


    def GetLP(self):
        "Print the linear program formed by the FormLP method."
        return string.join(self.output,'\n')

#
# The following methods are *not* supposed to be called directly by
# the user.  They are only meant to be called by other methods.
#

    def ExtractVarValuesFromLPSolution(self,resultFile):
        """
        Read the file resultFile containing the output of an LPSolver
        run and extract the values for the relaxedVars.

        This function returns a list for the relaxedVars.
        """
        FIND_VAR = 1
        SKIP_B = 2
        GRAB_VALUE = 3
        mode = FIND_VAR

        varValues = []
        varNum = 0
        varRE = re.compile('relaxedVars\\[([0-9]+)\\]')

        fd = open(resultFile,'r')
        for word in fd.read().split():
            if (FIND_VAR == mode):
                m = varRE.match(word)
                if (m):
                    assert int(m.groups(0)[0]) == varNum
                    mode = SKIP_B
            elif (SKIP_B == mode):
                mode = GRAB_VALUE
            elif (GRAB_VALUE == mode):
                mode = FIND_VAR
                varValues.append(float(word))
                varNum += 1
        return varValues

    def FixCertainVars(self,varsToCheck,partialSolution):
        """
        varsToCheck: A hash table where the keys are variables which
                     have not yet been frozen to be 0 or 1.  Vars which
                     are frozen will be removed from this hash.
        partialSolution: Values for each of the relaxedVars.

        This function goes through all the vars in partialSolution and
        freezes all vars which are 0 or 1.  Specifically, it returns
        a string which when added to the LP will give constraints to
        freeze the desired vars.
        """
        result = []
        for i in varsToCheck.keys():
            if (partialSolution[i] == 0.0 or partialSolution[i] == 1.0):
                del varsToCheck[i]
                result.append('s.t. forceCon__' + `i` + ': ' +
                              ' relaxedVars[' + `i` + '] = '
                              + `partialSolution[i]` + ';\n')
        return string.join(result)
    
    def FindSureVarToForce(self,varsToCheck,partialSolution):
        """
        varsToCheck: A hash table where the keys are variables which
                     have not yet been frozen to be 0 or 1.  Vars which
                     are frozen will be removed from this hash.
        partialSolution: Values for each of the relaxedVars.

        Goes through all varsToCheck in partialSolution and finds the
        most certain var (the one closest to being 0 or 1).  The
        resulting var is removed from varsToCheck and returned in
        a tuple along with the number of vars which are not 0 or 1.
        """
        
        mostCertainIndex = -1
        mostCertainValue = -1
        numAmbigousVars = 0
        for i in varsToCheck.keys():
            certainty = abs(0.5 - partialSolution[i])
            if (certainty > mostCertainValue):
                mostCertainValue = certainty
                mostCertainIndex = i
            if (certainty < 0.5):
                numAmbigousVars = numAmbigousVars + 1
        return (mostCertainIndex,numAmbigousVars)

    def FindAmbiguousVarToForce(self,partialSolution):
        """
        partialSolution: Values for each of the relaxedVars.

        Finds the most ambiguous var (the one closest to being 0.5).
        The index of this var is returned in a tuple along with the
        number of vars which are not either 0 or 1.
        """
        leastCertainIndex = -1
        leastCertainValue = 2.0
        numAmbigousVars = 0
        for i in range(len(partialSolution)):
            certainty = abs(0.5 - partialSolution[i])
            if (certainty <= leastCertainValue):
                leastCertainValue = certainty
                leastCertainIndex = i
            if (certainty < 0.5):
                numAmbigousVars = numAmbigousVars + 1
        return (leastCertainIndex,numAmbigousVars)

                       
    def FormLPSourceData(self,channelData):
        self.channelData = channelData
        self.output.append('param : channel :=\n')
        for i in range(len(channelData)):
            self.output.append('  ' + `i`  + ' ' + `1-2*channelData[i]`)
        self.output.append(';\n')

    def FormLPDataSection(self):
        self.output.append('\ndata;\n')


class QuantLPFormer(LPFormer):
    """
    This class forms a linear programming relaxation to do quantization.
    The main methods intended to be called by the user are listed below,
    see the accompanying documentation for this class or the base class
    LPFormer for details.

    __init__
    FormLP
    FormErasureLP
    SolveLP
    IterSolveLP
    IterSolveLPDecimateAmbiguous
    GetLP
    """


    def FormLP(self,channelData,extraVarData=''):
        """
        channelData:   A description of the source values or channelData.
                       1's and 0's are represented as 1's and 0's while
                       erasures or don't cares are represented with 0.5.
        extraVarData:  A string representing extra stuff to put in the
                       var section of the linear program.

        This function forms the LP required to quantize the channelData.
        After this function is called you can call one of the solve
        methods.

        Note that if you are doing erasure quantization you can either
        use this method or the FormErasureLP method but not both.
        """
        self.FormLPPreamble()
        self.FormLPVarSection()
        self.output.append(extraVarData)        
        self.FormLPDataSection()
        self.FormLPSourceData(channelData)        


    def FormErasureLP(self,channelData,extraVarData=''):
        """
        channelData:   A description of the source values or channelData.
                       1's and 0's are represented as 1's and 0's while
                       erasures or don't cares are represented with 0.5.
        extraVarData:  A string representing extra stuff to put in the
                       var section of the linear program.

        This function forms the LP required to quantize the
        channelData.  using the erasure metric.  That is it attempts
        to exactly match all 0's and 1's and ignores 0.5's.  After
        this function is called you can call one of the solve methods.

        Note that if you are doing erasure quantization you can either
        use this method or the FormLP method but not both, but you
        *must* be doing erasure quantization to use this method.

        The main difference in this method is that it encodes the
        problem purely in the constraints of the linear program and
        does not have any objective function.
        """        
        self.FormLPPreamble()
        self.FormConstraintsConnectingChecksAndVars()
        self.output.append(extraVarData)
        self.FormErasureConstraints(channelData)        
        self.FormLPDataSection()

    def MakeConstraintsConnectingCheckAndVars(self,checkNum,
                                              varIndexes,checkOn):
        """
        checkNum:   The index of the check to work on.
        varIndexes: List of indexes of the vars connected to check checkNum.
        checkOn:    Whether to make a constraint for the check being on
                    (in which case checkOn=1) or off (checkOn=0).

        This function adds constraints to the linear program requiring
        that the modulo-2 sum of the relaxedVars named by varIndexes
        equals checkOn for relaxedChecks[checkNum].

        ############################################################
        #
        # The following describes the formula for obtaining the 
        # constraints enforcing that all things connected to a