Abstract:
A processor implements a network of functional nodes and communication paths between the nodes. The processor includes a plurality of circuit implementations of the functional nodes of the processor; and a plurality of signal paths implementing the communication paths linking the circuit implementations of the nodes. At least some of the signal paths are configured to pass signal values represented according to temporal patterns of signal levels on the signal paths. The processor also includes a plurality of circuit components for conversion between a signal value represented as a signal level (e.g., voltage or current level) and a signal value represented as a temporal pattern.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application claims the benefit of the following U.S. Provisional Applications, the contents of which are incorporated herein by reference:
       Ser. No. 61/306,866, titled “MIXED ANALOG/DIGITAL PROCESSING IN A STOCHASTIC,” filed on Feb. 22, 2010;   Ser. No. 61/307,140, titled “MIXED ANALOG/DIGITAL PROCESSING IN A STOCHASTIC,” filed on Feb. 23, 2010;   Ser. No. 61/328,484, titled “STOCHASTIC LOGIC GATE,” filed on Apr. 27, 2010; and   Ser. No. 61/306,880, titled “SELECTIVE DELAY OF DATA RECEIPT IN STOCHASTIC COMPUTATION,” filed on Feb. 22, 2010.       
 
         [0006]    This application is also related to, but does not claim the benefit of the filing dates of, the following applications, which is incorporated herein by reference:
       PCT Serial No. PCT/US10/25956, titled “BELIEF PROPAGATION PROCESSOR,” filed on Mar. 2, 2010, published as WO2010/101944 on Sep. 10, 2010; and   PCT Serial No. PCT/US 11/20794, titled “BELIEF PROPAGATION PROCESSOR,” filed on Jan. 11, 2011.       
 
     
    
     STATEMENT AS TO FEDERALLY SPONSORED RESEARCH 
       [0009]    This invention was made with government support under ______ awarded by ______. The government has certain rights in the invention. 
     
    
     BACKGROUND 
       [0010]    This invention relates to a mixed signal (e.g., analog level and stochastic temporal pattern) implementation of a belief propagation processor. 
         [0011]    Soft logic processing with analog values has a number of applications, including in decoding of Low Density Parity Check (LDPC) codes. A number of algorithms have been proposed for either processing digital or analog representations of values, including the Sum-Product (SP) algorithm, which is sometimes referred to as a Belief Propagation Algorithm, and the Min-Sum (MS) algorithm (also referred to as Max-Sum or Max-Product), which can be regarded as an approximation of the SP algorithm. A description of such algorithms may be found in H. Wymeersch,  Iterative Receiver Design , Cambridge University Press, Cambridge, 2007. 
         [0012]    Implementations of the Sum-Product (SP) algorithm for error correction decoding generally involve two kinds of soft-gates: Equals and XOR. The connectivity between the Soft equals and Soft XOR is based on the check-matrix associated with the specific error correcting code. 
         [0013]    In some implementations of the Sum-Product algorithm, messages are passed between Soft Equals and Soft XOR gates as stochastic signals that randomly vary between a set of signal values (e.g., between a set of two possible values, such as 0 and 1 volt) such that the average of the signal over time represents the message value. An example of such implementation is described in C. Winstead et al., “Stochastic Iterative Decoders,”  Cornell Computing Research Repository  (CoRR) (2005), http://arxiv.org/abs/cs/0501090. Such stochastic implementations face challenged including correlation of stochastic signals and/or complexity or resource requirements of circuitry for addressing such possible correlation. 
       SUMMARY 
       [0014]    In one aspect, in general, a processor implements a network of functional nodes and communication paths between the nodes. The processor includes a plurality of circuit implementations of the functional nodes of the processor; and a plurality of signal paths implementing the communication paths linking the circuit implementations of the nodes. At least some of the signal paths are configured to pass signal values represented according to temporal patterns of signal levels (e.g., voltage or current) on the signal paths. At least some of the circuit implementations of the functional nodes include circuitry for combining temporal patterns of a plurality of signals to form a temporal pattern on a combined signal. The processor also includes a plurality of circuit components for conversion between (i.e., either from or to or both) a signal value represented as a signal voltage or current level and a signal value represented as a temporal pattern. 
         [0015]    Examples of the processor can have one or more of the following features. 
         [0016]    The signal values represented as signal levels are represented as voltage or current levels. 
         [0017]    The signal values represented as temporal patterns are represented by time averages of varying signal levels. 
         [0018]    The processor implements a belief propagation algorithm. For instance, the processor implements a Sum-Product algorithm. 
         [0019]    The network represents a factor graph. In some examples, the plurality of circuit implementations of the functional nodes a plurality of circuit implementations of variable nodes and a plurality of circuit implementations of factor nodes. 
         [0020]    The processor is configured to perform a decoding operation. The variable nodes correspond to inputs to the decoding, and the factor nodes correspond to constraints on the inputs. In some examples, the decoding operation is a decoding of a Low Density Parity Check (LDPC) code. 
         [0021]    At least some of the circuit implementations of the functional nodes include circuitry for combining signal levels of a plurality of signals to form a signal level on a combined signal. 
         [0022]    The functional nodes that include circuitry for combining signal levels further include at least some of the circuit components for conversion between a signal value represented as a signal voltage or current level and a signal value represented as a temporal pattern. Said circuit component for conversion are coupled to the circuitry for combining the signal levels. 
         [0023]    The plurality of circuit components for conversion between a signal value represented as a signal voltage or current level and a signal value represented as a temporal pattern include components for conversion from a signal level to a random temporal pattern. The random pattern may be a pseudo-random pattern. 
         [0024]    The random temporal pattern comprises a temporal pattern of transitions between a set of signal levels, and the signal value is represented using a fraction of time at one or more levels of the set of signal levels. 
         [0025]    The random temporal pattern comprises a temporal pattern of transitions between two signal levels and the signal value is represented using a fraction of time at one of the signal levels. 
         [0026]    The signal value is represented as a monotonic function of the fraction of time at one of the levels. In some examples, the signal value is represented as a linear function of the fraction of time at one of the levels. In some examples, the signal value is represented as a compressive function (e.g., logarithmic or sigmoid function) of the fraction of time at one of the levels. 
         [0027]    At least one component for conversion from a signal level to a random temporal pattern includes a random signal generator with output signal statistics independent of the signal level, and a circuit for combining the signal level and an output of the random signal generator to form the random temporal pattern according to the signal level. 
         [0028]    The circuitry for combining the random signal and the signal level comprises a comparator to compare the signal level and a time-varying level of the random signal. In some examples, the random signal generator has a uniform output level distribution. 
         [0029]    The plurality of circuit components for conversion between a signal value represented as a signal voltage or current level and a signal value represented as a temporal pattern include components for conversion from a temporal pattern to a signal level. 
         [0030]    At least one component for conversion from a temporal pattern to a signal level includes an averaging (e.g., integrating, scaled integrating, “leaky” integration) circuit for accepting the signal with the temporal pattern and being responsive to a fraction of time the signal with the temporal pattern has a first signal level of a set of signal levels uses to form the temporal pattern. 
         [0031]    The averaging circuit comprises a fixed interval averaging circuit that is responsive to a fraction of time within the fixed interval that the signal has the first signal level. 
         [0032]    The averaging circuit comprises at least one of a decaying averaging circuit and a moving average circuit that is responsive to the fraction of time the signal has the first signal level. 
         [0033]    The signal level is a monotonic function of the fraction of time the signal with the random pattern has the first signal level. In some examples, the signal value is a linear function of the fraction of time at the first level. In some examples, the signal value is a compressive function of the fraction of time at the first level. 
         [0034]    The plurality of circuit implementations of function nodes include a plurality implementations of Soft XOR nodes. 
         [0035]    Each of the implementations of a Soft XOR node comprising a logical XOR gate configured to accept a plurality of signals with values represented as temporal patterns, and to produce a signal with a temporal pattern as the output of the logical XOR gate. 
         [0036]    The plurality of circuit implementations of function nodes include a plurality implementations of Soft Equals nodes. 
         [0037]    Each of the implementation of a Soft Equals node comprises a logic circuitry configured to accept a plurality of signals with values represented as temporal patterns, and to produce a signal with a temporal pattern as the output of the logic circuitry. The implementation further comprises a first circuit component of the plurality of circuit components for conversion between a signal value represented as a signal voltage or current level and a signal value represented as a temporal pattern circuitry. Said circuit component is coupled to the output of the logic circuitry and forms a first signal with a value represented as a signal voltage or current level. A second circuit component of said plurality of circuit components for conversion of the first signal to form a second signal with a value represented as a temporal pattern. In some examples, the logic circuitry comprises a flip-flop, for instance a J-K flip flop. 
         [0038]    Each of the implementation of a Soft Equals node comprises one circuit component of the plurality of circuit components for conversion between a signal value represented as a signal voltage or current level and a signal value represented as a temporal pattern circuitry coupled to each input for converting a signal value represented as a temporal pattern to a signal value represented as a signal level. The implementation further comprises functional circuitry for combining the signal levels output from the circuit components, and a further circuit component of the plurality of circuit components for conversion between a signal value represented as a signal voltage or current level and a signal value represented as a temporal pattern circuitry coupled to the output of the functional circuitry for converting from a signal value represented as a signal level to a signal value represented as a temporal pattern. 
         [0039]    The processor further comprises a plurality of storage cells, each storage cell for writing and for reading a signal level. 
         [0040]    The processor further comprises a delay circuit on each of at least some of said signal paths links. Each delay module is configured or configurable to delay a signal represented as a time pattern traversing said signal path by an assigned delay. In some examples, the delay circuit is combined with a circuit component for converting between a signal level and a time pattern representation of a signals value on the signal path. 
         [0041]    Each storage cell is coupled or couplable to a circuit component of the plurality of circuit components for conversion between a signal value represented as a signal voltage or current level and a signal value represented as a temporal pattern circuitry for at least one of receiving a value represented as a temporal pattern and providing a value represented as a temporal pattern. 
         [0042]    In another aspect, in general, software, which may be stored on a tangible computer readable medium, comprises instructions for forming any example of a processor as described above. For example, the software may include a Hardware Description Language (HDL) representation of the processor. 
         [0043]    In another aspect, in general, an apparatus for stochastic belief propagation includes a plurality of node circuits, each node circuit being connected to at least one other node circuit by an edge, each of the node circuits being configured to output an M-ary stream of random M-ary variables having a selected probability distribution; and a plurality of re-randomizing circuits, each of the re-randomizing circuits being in data communication with at least one of the node circuits for receiving the M-ary stream, and having an analog stage that outputs an electrical quantity that is an analog function of the selected probability distribution. In one particular embodiment, M=2. 
         [0044]    Additional embodiments include those in which the re-randomizing circuit includes an integrator, and those in which the re-randomizing circuit includes an accumulator for accumulating a quantity when the M-ary variable is in a first state, and for maintaining accumulating quantity when the M-ary variable is in a second state. Exemplary accumulators include a capacitor for accumulating charge and a CCD for accumulating photons. 
         [0045]    In some other embodiments, the re-randomizing circuit is configured to accumulate the quantity for a period that spans more than one M-ary variable. Among these are those in which the re-randomizing circuit includes first and second accumulators, and switches for causing the first accumulator to accumulate the quantity during the first interval and to cause at least a portion of the quantity to be transferred to the second accumulator after the interval. 
         [0046]    In another aspect, in general, a circuit for logical processing is made up of a number of gates. One or more of the gates each has multiple signal inputs, each accepting an M-ary time-varying signal (x i (t)). The gate also has multiple integrator sections, each coupled to one of the signal inputs and providing an output (μ i ) characterizing a sample distribution of signal input values on that input. A signal combination section of the gate is used for combining the quantities characterizing the signal inputs and providing an output (ν) representing a combination of the sample distributions of the signal values forming a desired characteristic of a distribution of output signal values. A resampler section of the gate uses the output of the signal combination section to form an M-ary time varying output signal (y(t)) having the desired distribution of signal values. In some examples, the gate implements a stochastic equals operator. 
         [0047]    Aspects may include one or more of the following features. 
         [0048]    The gate further comprises a memory element for storing the output (μ i ) of each integrator section. 
         [0049]    The gate further comprises a memory element for storing the output (ν) of the signal combination section. 
         [0050]    The integrator section implements a function equivalent to 
         [0000]    
       
         
           
             
               μ 
               i 
             
             = 
             
               
                 1 
                 T 
               
                
               
                 
                   ∑ 
                   
                     t 
                     = 
                     1 
                   
                   T 
                 
                  
                 
                   
                     
                       x 
                       i 
                     
                      
                     
                       ( 
                       t 
                       ) 
                     
                   
                   . 
                 
               
             
           
         
       
     
         [0051]    The integrator section implements a function equivalent to 
         [0000]    
       
         
           
             
               
                 μ 
                 i 
               
                
               
                 ( 
                 t 
                 ) 
               
             
             = 
             
               
                 
                   
                     1 
                     T 
                   
                    
                   
                     
                       x 
                       i 
                     
                      
                     
                       ( 
                       t 
                       ) 
                     
                   
                 
                 + 
                 
                   
                     ( 
                     
                       1 
                       - 
                       
                         1 
                         T 
                       
                     
                     ) 
                   
                    
                   
                     
                       μ 
                       i 
                     
                      
                     
                       ( 
                       
                         t 
                         - 
                         1 
                       
                       ) 
                     
                   
                 
               
               = 
               
                 
                   1 
                   T 
                 
                  
                 
                   
                     ∑ 
                     
                       k 
                       = 
                       0 
                     
                   
                    
                   
                     
                       
                         ( 
                         
                           1 
                           - 
                           
                             1 
                             T 
                           
                         
                         ) 
                       
                       k 
                     
                      
                     
                       
                         
                           x 
                           i 
                         
                          
                         
                           ( 
                           
                             t 
                             - 
                             k 
                           
                           ) 
                         
                       
                       . 
                     
                   
                 
               
             
           
         
       
     
         [0052]    The signal combination section implements a function equivalent to 
         [0000]      ν=(π i μ i )(π i μ i +π i (1−μ i )) −1 .
 
         [0000]    One or more aspects address a number of technical problems in implementing stochastic, or partially stochastic, belief propagation systems. 
         [0053]    Purely digital (e.g., using digital logic) implementations of stochastic belief propagation can require significant resources (e.g., circuit area, power, etc.) to implement resampling functions to remove correlation between stochastic signals. Analog averaging and resampling can require fewer such resources. 
         [0054]    Digital implementation of resampling require significant digital state (e.g., counters, shift registers, etc.). Even if functional circuits are time shared, at least some state must be maintained for the resampling nodes, thereby limiting the amount of savings that can be achieved by time sharing. Use of analog representations of certain signals can provide an efficient means of preserving state without requiring significant resources to maintain state. 
         [0055]    Certain functions, such as Soft XOR may be more efficient to implement in stochastic form, while other functions, such as Soft Equals may be more efficiently implemented in an analog form. Therefore, a mixed analog and stochastic (digital) implementation may achieve higher efficiency than a purely analog or purely stochastic implementation. 
         [0056]    In certain implementations, signal paths that use temporal patterns of transitions between two or a limited set of signal values may provide advantages over use of a voltage or signal level. For example, such signal paths may be less affected by signal noise. 
         [0057]    Other features and advantages of the invention are apparent from the following description, and from the claims. 
     
    
     
       DESCRIPTION OF DRAWINGS 
         [0058]      FIG. 1  is an example factor graph for a length 8 LDPC code; 
           [0059]      FIG. 2A  is a diagram that illustrates transformation of a variable node with bidirectional links to a set of variable nodes with directed links, and 
           [0060]      FIG. 2B  is a diagram that illustrates a similar transformation for a constraint node; 
           [0061]      FIG. 3  shows a portion of a factor graph implementation, and analog circuit processing elements; 
           [0062]      FIG. 4  is a stochastic implementation of a Soft XOR node; 
           [0063]      FIGS. 5A-C  are stochastic implementations of a Soft Equals node; 
           [0064]      FIG. 6  is a logic circuit implementations of a stochastic Soft XOR node; 
           [0065]      FIG. 7  is a logic circuit implementation of a stochastic Soft Equals node; 
           [0066]      FIG. 8  shows an analog integrator; 
           [0067]      FIG. 9  shows an analog probability estimator circuit with periodic updating; 
           [0068]      FIG. 10  shows a sequence of switch control signal states; 
           [0069]      FIG. 11  shows an analog probability estimator circuit with continuous updating; 
           [0070]      FIG. 12  shows a biased random bit generator drive by a probability estimator; 
       
    
    
     DESCRIPTION 
       [0071]    Referring to  FIGS. 1 and 2 , an example of an analog-based implementation of a belief propagation processor, which implements a decoder for a Low Density Parity Check (LDPC) code is based on a factor graph  100  in which one variable node  110  is associated with each different input bit (b j ), and one check (constraint) node  120  is associated with each parity constraint. Approaches to analog implementation of such a process are described in co-pending patent publication WO2010/101944, titled “BELIEF PROPAGATION PROCESSOR,” as well as in PCT Serial No. PCT/US11/20794, which are incorporated by references. The description below provides further embodiments of such a processor in which at least some signal are not necessarily encoded by the analog amplitude of the signals, and rely at least in part of a time pattern of the signals. For reference, the description corresponding to  FIGS. 1-2 , which correspond to the same numbered figures in the above-referenced co-pending application, are provided below. 
         [0072]    In  FIG. 1 , an example with eight input bits with four checks (constraints) on the input bits is shown. The code can be represented in matrix form in which each column is associated with a different input bit, and each row is associated with a different check or constraint. An (i, j) entry is 1 if the j th  input is used in the i th  constraint and 0 otherwise. In the LDPC example, the constraint is that the XOR of the inputs for a constraint is 0. This example length 8 LPDC code can be represented according to the following check matrix (note that the rows are dependent modulo 2 in this illustrative example, which is not necessarily true in general): 
         [0000]    
       
         
           
             
               [ 
               
                 
                   
                     0 
                   
                   
                     1 
                   
                   
                     0 
                   
                   
                     1 
                   
                   
                     1 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     1 
                   
                 
                 
                   
                     1 
                   
                   
                     1 
                   
                   
                     1 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     1 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     1 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     1 
                   
                   
                     1 
                   
                   
                     1 
                   
                 
                 
                   
                     1 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     1 
                   
                   
                     1 
                   
                   
                     0 
                   
                   
                     1 
                   
                   
                     0 
                   
                 
               
               ] 
             
               
           
         
       
     
         [0073]    In  FIG. 1 , each edge is bidirectional representing a signal path in each direction. Referring to  FIGS. 2A-B , an equivalent directed (unidirectional) graph can be formed by replacing each n-edge node with n separate nodes, each of the n nodes having n-1 inputs and one output, and forming unidirectional edges between the nodes to achieve the connectivity of the original graph. Referring to  FIG. 2A , for instance, each 3-edge variable node  110  can be replaced with three 2-input/1-output variable nodes  210 ,  212 , each of which implements a Soft Equals function. Referring to  FIG. 2B , each 4-edge check node  120  can be replaced with four 3-input/1-output check nodes  220 , which is implements a Soft XOR function. 
         [0074]    One approach to analog implementation of a decoder corresponding to the factor graph shown in  FIG. 1  is to implement a circuit element for each node of the equivalent unidirectional graph. In embodiments described in co-pending patent publication WO2010/101944, the signals passing between circuit elements are represented as analog voltages or current. In a number of these embodiments, the voltage or current of a signal is logarithmically related to the message value for the SP algorithm. 
         [0075]    In  FIG. 2A , each bidirectional Soft Equals node  110  with n inputs is implemented as n directional Soft Equals nodes  210 . Similarly, as shown in  FIG. 2B , each Soft XOR node  120  with n inputs is implemented with n directional Soft XOR nodes  220 . Each directional Soft Equal node with inputs x 1 , . . . ,x n-1  and output y n  accepts messages representing p(x i =1) and outputs a message p(y n =1) such that 
         [0000]        p ( y   n =1)=π i=1   n-1   p ( x   i =1)/π i=1   n-1   p ( x   i =0)+π i=1   n-1   p ( x   i =1),
 
         [0000]      where 
         [0000]        p ( x   i =0)=1 −p ( x   i =1). 
         [0076]    Each directional Soft XOR node  220  with inputs y 1 , . . . ,y m-1  and output x n  accepts messages representing p(y i =0) and outputs a message representing p(x n =0) such that 
         [0000]        p ( x   m =1)= p (XOR( y   1   , . . . ,y   m-1 )=1) 
         [0000]    which in the case of a three input node is equivalent to 
         [0000]        p ( x   m =1)= p ( y   1 =1) p ( y   2 =0)+ p ( y   1 =0) p ( y   2 =1) 
         [0077]    Referring to  FIG. 3 , a portion of a factor graph is shown with interconnection of directional Soft Equals nodes  210  and Soft XOR nodes  220 . In implementations described in the patent publication WO2010/101944, log domain analog Soft XOR circuits  220   a  are used to implement Soft XOR nodes. In some implementations of the log domain Soft XOR  220   a , circuitry (LAX)  420  accepts voltage (e.g., differential voltage on a pair of signal lines) representations of a log likelihood ratio representing the message (e.g., log(p(x=1)/p(x=0))), and provides a corresponding voltage based log-likelihood representation as output. In some implementations, the output of the LAX circuitry  420  may be stored between discrete iterations in an analog memory cell  424 , while in other implementations, a continuous relaxation approach, or a mixed combination of discrete iterations in which partial relation is enabled in each iteration, may be used. Similarly, the Soft Equals node  210  is implemented using a log domain analog Soft Equals (LAE) circuit  412 , which accepts log analog inputs and provides log analog outputs suitable for input to the LAX circuitry  420 . Patent publication WO2010/101944 and PCT Serial No. PCT/US11/20794 also describe implementations in which instances of LAX and LAE circuitry are time shared (i.e., temporally reused) in different cycles of an iteration, using a complete set of analog memory cells  424  to maintain state between cycles. 
         [0078]    Other embodiments replace the signal representation on one or more of the signal paths between the circuit implementations of the Soft Equals  210  and Soft XOR  220  nodes from use of solely signal level (e.g., voltage, current, charge, or other physical signal characteristic that can represent a continuous or finely quantized range) with a “stochastic” representation that use the temporal pattern of transitions between fixed levels to represent a continuous (or finely quantized) range of values. A number of embodiments described below make use of the average value of signals that randomly (e.g., pseudo randomly) alternate between to voltage (or alternatively current) levels. Without loss of generality, in some embodiments, one signal level is referred to below as “1” or “true”, and another as “0” or “false”, with the understanding that such levels may correspond to specific pairs of levels (e.g., 0 volts and 5 volts) or, for example, using level ranges as is customary in digital logic circuitry. 
         [0079]    Referring to  FIG. 4 , in some embodiments, Soft XOR nodes  220  are implemented using an stochastic domain Soft XOR circuit  220   b . The circuit includes a stochastic XOR circuit (DX)  520 , which accepts the stochastic representations as input and provides a stochastic representation as output. In the figures, dotted signal lines are generally used to indicate signal lines used to pass stochastic signals. Referring to  FIG. 6 , one implementation of the stochastic XOR circuit  520  uses a digital XOR gate  820 . 
         [0080]    Referring to  FIGS. 5A-C , a number of implementations ( 210   b - d ) of stochastic domain Soft Equals nodes  210  accept stochastic input and provide stochastic output. Referring to  FIG. 5A , a first such stochastic implementation  212   b  makes use of a stochastic domain Soft Equals (DE) circuit  612  to process the stochastic inputs and provide a stochastic output that represents the value of the Soft Equals function applied to its inputs. 
         [0081]    Referring to  FIG. 7 , one implementations of the DE circuit uses a J-K flip flop  818 , which is configured to make a transition (or remain at) “1” when clocked with all the inputs are “1” by passing al the inputs an AND gate  814  to the J input of the flip-flop, and configured to make a transition to “0” (or remain at “0”) when clocked with all the inputs are “0” by applying an AND to the negations of the inputs in a gate  816  for the K input. There are two characteristics of the output of the DE circuit  612  to consider. First, that rate of transition on the output is significantly slower than on the inputs. Second, stochastic output is correlated with its input, so were the outputs of the DE circuits  612  fed back directly as inputs to the DX circuits  520 , those inputs may be correlated, thereby resulting in the DX circuits not properly computing the Soft XOR function as desired. 
         [0082]    Continuing to refer to  FIG. 5A , to mitigate the effect of the output characteristics of the DE circuit  612 , the stochastic output of the DE circuit is passed to an averaging (AV) circuit  614  (also referred to as integrating circuitry or an integrator), which provides an analog output representing its stochastic input. This analog output is then passed to a resampling (RS) circuit  618  (also referred to as re-randomization circuitry), which produces a stochastic output representing its analog input. Therefore, the output of the RS circuit  618  has the same local average statistics as the output of the DE circuit  612 , but removes correlation between those signals and generally increases the transition rate of the output. In some implementations, the output of the AV circuit  614  is optionally stored in an analog memory cell  616 . 
         [0083]    Referring to  FIG. 5B , a second stochastic implementation  212   c  of a Soft Equals node makes use of a linear domain analog Soft Equals (AE) circuit  712 , which accepts analog levels corresponding to the message values as input, and provides an analog level corresponding to the message value as output. Each of the stochastic inputs to the overall circuit are passed through corresponding averaging (AV) circuits  614 , and the output of the DE circuit  712  is passed through a resampling (RS) circuit  618  to generate the stochastic output, which is passed to the inputs of the stochastic Soft XOR circuits. In some implementations, the output of the AE circuit  712  is stored in an analog memory cell  616  prior to being resampled to form the stochastic output. In other implementations, the analog memory cells (not shown) are used at the inputs of the AE circuit to store the averaged stochastic inputs. 
         [0084]    Referring to  FIG. 5C , in some implementations, an analog Soft Equal circuit does not necessarily using linear domain level representations. For instance, a log domain analog Soft Equals (LAE) circuit  412 , similar to that used in an overall analog implementation, is used with the implementation  210   d  of the Soft Equals node. The stochastic inputs are passed to log output averaging (LAV) circuits  714 , which provide an analog signal level output that is proportional to the log likehood ratio based on the average value of the stochastic input. The output of the LAE circuit  412  is passed through an exponential resampling (ERS) circuit  718 , whose stochastic output has an average value that inverts the effect of the LAV circuit. Note that transforming of domain of the analog representation may simplify the circuitry. For instance, use of the log likelihood ratio domain allows the LAE circuit to effectively implement a sum of its input to yield the Soft Equals function. 
         [0085]    A number of specific circuit implementations of the averaging (AV) circuit  614 , for instance, as used in  FIG. 5A , can be used. Some such implementations are described below. 
         [0086]      FIG. 8  shows a basic analog integrator that takes a sequence of bits from the input (In). This input controls a switch, which is closed when the input bit is a “1” and open when the input bit is a “0”. During the interval in which the input is a “1”, the current source (I) deposits a small amount of charge into the capacitor (C). Assuming the capacitor begins with no charge, the amount of charge on the capacitor after N clock cycles is proportional to the fraction of clock cycles for which the input was “1”. Since the voltage across the output wires (Out) is proportional to the charge, it is also proportional to the fraction of clock cycles for which the input is “1”. 
         [0087]    Since the output grows in proportion to the number of cycles, N, to allow this circuit to be used continuously to monitor the bit probability, it is augmented to provide either a periodic probability estimate or a continuously updated probability estimate that maintains a fixed proportion over time. Two different techniques are described. 
         [0088]      FIG. 9  shows a circuit that integrates over a series of fixed intervals and provides a new output value at the end of each interval. Each integration interval corresponds to a fixed number of clock cycles. At the end of each interval, a portion of the charge integrated on a first capacitor C 1  is transferred to a second capacitor C 2 , which drives the output. This charge is held constant on the second capacitor until the end of that interval. 
         [0089]    In addition to the input bit sequence, the circuit shown in  FIG. 9  is provided with a series of control signals (S 1  through S 4 ) that either directly or indirectly affect the state of a series of switches within the circuit (sw 1 -sw 4 ).  FIG. 10  shows a sequence of states for these switch control signals, where an X in the box indicates switch closure (or in the case of S 1 , indicates whether S 1  is equal to “1”, which would result in switch closure only if the input (In) is also equal to “1”). In cases in which one switch closes as another opens appropriate care is taken to avoid both switches being closed at the same time. 
         [0090]    Given the sequence of events shown in  FIG. 10 , (with time proceeding from left to right), the operation is as follows in sequence, starting at the beginning of each interval:
       Control signal S 1  is set to “0” so that the switch (sw 1 ) connecting the current source to the first capacitor (C 1 ) is forced to be open regardless of the state of the input bit (In).   The shorting switch (sw 4 ) on the second capacitor (C 2 ) is closed, to clear its charge, and then re-opened.   The switch (sw 2 ) connecting the two capacitors is closed, allowing the charge to be shared between the two capacitors, and then re-opened.   The shorting switch (sw 3 ) on the first capacitor (C 1 ) is closed, to clear the charge on this capacitor, and then re-opened.   Control signal S 1  is set to 1 so that the switch (sw 1 ) connecting the current source to the first capacitor (C 1 ) will subsequently be controlled by the input bit (In).       
 
         [0096]    This sequence shows one specific case. However, one can achieve the same outcome by changing the order of some of these steps. For example, S 4  could close and reopen while S 1  is still closed from the previous interval. 
         [0097]    During the interval when switch (sw 2 ) connects the two capacitors, since capacitor (C 2 ) had previously been cleared to zero charge, the total charge previously on C 1  would be shared between C 1  and C 2  in proportion to their capacitance. For example, if C 1  and C 2  are of equal capacitances, the charge on C 2  becomes equal to half the charge on C 1  before this switch is closed. In this example the value of the output (Out) that represents a given probability is half the voltage that is across C 1  at the end of the previous interval given this probability value. Since the output of this circuit feeds a random bit generator, the values of I, C 1 , and C 2  should be chosen so that for a given input bits are all “1”, the output voltage is appropriately scaled so that the random bit generator will produce bits with a probability of 1 of being “1”. If necessary, additional amplification can be used at the output of this circuit. 
         [0098]    The sequence of steps that constitute the transition between intervals need not operate at the clock frequency of the incoming bits. Preferably it operates at a faster rate so that the transition between intervals can be as short as possible, and preferably less than one bit clock cycle. Since the output, which drives the random bit generator, is reset to zero for a short period of time, care should be taken that this interval occurs during a period in which the random bit generator can ignore this momentarily incorrect output. 
         [0099]      FIG. 11  shows an alternative circuit in which a leaky form of integration is performed continuously. In this circuit, when switch (sw 2 ) is closed, the charge on the capacitor (C 1 ) drains through a resistive element (R) at a rate proportional to the capacitor&#39;s charge. 
         [0100]    During each clock period, signal S 1  is set to “1” for a sub-interval that allows the input (In) to control the switch (sw 1 ) such that the capacitor charges if the input is a “1”. During a second sub-interval, S 1  is “0” and S 2  is “1”, which closes switch (sw 2 ) to allow charge to drain from the capacitor. The specific during of these sub-intervals, the values of I, C 1 , and R are chosen so that if the inputs (In) were all set to the value “1”, the steady state voltage on the capacitor is appropriately scaled so that the random bit generator will produce bits with a probability of 1 of being “1”. 
         [0101]    This circuit is analogous to a leaky integrator, but with a significantly simplified implementation. For example, this circuit as shown avoids the need for a switch to select between randomly generated bits and bits directly from the input depending on the hold signal. However, this circuit can also be used in conjunction with such a switch. 
         [0102]    The circuits described herein add a fixed increment of charge on the capacitor for each one bit, and drains a fixed proportion of the current value of charge on each clock cycle. A slightly simpler circuit variation would remove the switch (sw 2 ) and connect the resistor across the capacitor at all times. Similarly, the control signal S 1  and the corresponding AND gate could be removed, leaving the input (In) directly controlling switch (sw 1 ). Since the charging and discharging of the capacitor would occur simultaneously, the behavior would be similar to, but slightly different from the operation of the circuit of  FIG. 11 . 
         [0103]    In both of the probability estimator circuits shown, the current source and switches can be implemented using typical methods, for example using CMOS transistors. In the case of the circuit of  FIG. 11 , the resistive element (R) can be implemented either using a resistor or an appropriate transistor circuit design to provide an approximately fixed resistance. 
         [0104]    Various implementation of resampling (RS) circuits  618  may be used for converting between an analog and a stochastic signal representation. Referring to  FIG. 12 , in one implementation, the input voltage level is used to set the bias probability of a random bit generator.  FIG. 12  shows an example circuit that directly accepts the output of the probability estimator to produce a random bit, biased in proportion to the input voltage. 
         [0105]    The circuit shown in  FIG. 12  makes use of a uniform random sequence generator, which generates a random sequence of analog values that are uniformly distributed over a range of values. An example of such a random sequence generator is that disclosed in K. Eguchi, et al., “Simple Design of a Discrete-Time Chaos Circuit Realizing a Tent Map,”  IEICE Trans. Electron ., Vol. E83-C, No. 5, May 2000, the contents of which are herein incorporated by reference. 
         [0106]    In other examples of a resampling circuit, the random signal generator does not necessarily have a uniform level distribution. In such examples, the input level can be passed though a monotonic transformation (e.g., based on the cumulative distribution of the random signal generator) to achieve the same effect as if the random signal generator had a uniform level distribution. 
         [0107]    The output of this circuit (with any necessary signal conversion, for example conversion from current to voltage using a resistive element) is connected to one input of an analog comparator. The other input is connected to the output of averaging circuit, for example, as shown in either  FIG. 9  or  FIG. 11 . The polarity and scaling of the inputs should be such that if the output of the probability estimator is at its maximum value, the comparator will (nearly always) produce only 1 outputs, while if the output of the probability estimator is at its minimum value, the comparator will (nearly always) produce only 0 outputs. In this case, output of the comparator will be a random sequence of 0 or 1 values, with a probability approximately the value estimated by the probability estimator, but uncorrelated with the input bit sequence. 
         [0108]    It should be understood that the example implementations are only examples, and are not exhaustive, and that aspects of the different implementations may be combined to form yet other embodiments in which signal flows in a circuit implementation for a factor graph use both analog and stochastic signal representations. 
         [0109]    It should also be understood that although a number of embodiments are presented using single-ended signals, differential signals may equivalently be used, for example, with averaging being performed separately on each signal line. Furthermore, either voltage signals or current signals may be used in alternative embodiments 
         [0110]    In various embodiments presented herein or alternative embodiments, the averaging functions may implement various forms of time averaging. For instance, for an averaging circuit  614  (e.g., as shown in  FIG. 5A ) which accepts a stochastic signal x i (t) and forms and analog signal value μ i , to represent a probability p i . In implementations in which a time period of length T (e.g., in number of clock periods in a computation cycle) is used in which the statistics of the stochastic signal are kept constant, the values μ i  may be computed as 
         [0000]    
       
         
           
             
               μ 
               i 
             
             = 
             
               
                 1 
                 T 
               
                
               
                 
                   ∑ 
                   
                     t 
                     = 
                     1 
                   
                   T 
                 
                  
                 
                   
                     
                       x 
                       i 
                     
                      
                     
                       ( 
                       t 
                       ) 
                     
                   
                   . 
                 
               
             
           
         
       
     
         [0000]    Note that due to further normalization, the values μ i  may be uniformly scaled (i.e., the same for all i), such that 
         [0000]    
       
         
           
             
               μ 
               i 
             
             ∝ 
             
               
                 1 
                 T 
               
                
               
                 
                   ∑ 
                   
                     t 
                     = 
                     1 
                   
                   T 
                 
                  
                 
                   
                     
                       x 
                       i 
                     
                      
                     
                       ( 
                       t 
                       ) 
                     
                   
                   . 
                 
               
             
           
         
       
     
         [0000]    In yet other examples, it may be appropriate to apply a monotonic function to the sum, as 
         [0000]    
       
         
           
             
               μ 
               i 
             
             = 
             
               
                 f 
                  
                 
                   ( 
                   
                     
                       1 
                       T 
                     
                      
                     
                       
                         ∑ 
                         
                           t 
                           = 
                           1 
                         
                         T 
                       
                        
                       
                         
                           x 
                           i 
                         
                          
                         
                           ( 
                           t 
                           ) 
                         
                       
                     
                   
                   ) 
                 
               
               . 
             
           
         
       
     
         [0111]    In implementations in which the likelihood values may vary over time, various other forms can be used, such as sliding average 
         [0000]    
       
         
           
             
               
                 μ 
                 i 
               
                
               
                 ( 
                 t 
                 ) 
               
             
             = 
             
               
                 
                   1 
                   T 
                 
                  
                 
                   
                     ∑ 
                     
                       
                         t 
                         0 
                       
                       = 
                       
                         t 
                         - 
                         T 
                         + 
                         1 
                       
                     
                     t 
                   
                    
                   
                     
                       x 
                       i 
                     
                      
                     
                       ( 
                       t 
                       ) 
                     
                   
                 
               
               = 
               
                 
                   
                     μ 
                     i 
                   
                    
                   
                     ( 
                     
                       t 
                       - 
                       1 
                     
                     ) 
                   
                 
                 + 
                 
                   
                     
                       x 
                       i 
                     
                      
                     
                       ( 
                       t 
                       ) 
                     
                   
                   T 
                 
                 - 
                 
                   
                     
                       x 
                       i 
                     
                      
                     
                       ( 
                       
                         t 
                         - 
                         T 
                       
                       ) 
                     
                   
                   T 
                 
               
             
           
         
       
     
         [0000]    or as a decaying average 
         [0000]    
       
         
           
             
               
                 μ 
                 i 
               
                
               
                 ( 
                 t 
                 ) 
               
             
             = 
             
               
                 
                   
                     1 
                     T 
                   
                    
                   
                     
                       x 
                       i 
                     
                      
                     
                       ( 
                       t 
                       ) 
                     
                   
                 
                 + 
                 
                   
                     ( 
                     
                       1 
                       - 
                       
                         1 
                         T 
                       
                     
                     ) 
                   
                    
                   
                     
                       μ 
                       i 
                     
                      
                     
                       ( 
                       
                         t 
                         - 
                         1 
                       
                       ) 
                     
                   
                 
               
               = 
               
                 
                   1 
                   T 
                 
                  
                 
                   
                     ∑ 
                     
                       k 
                       = 
                       0 
                     
                   
                    
                   
                     
                       
                         ( 
                         
                           1 
                           - 
                           
                             1 
                             T 
                           
                         
                         ) 
                       
                       k 
                     
                      
                     
                       
                         
                           x 
                           i 
                         
                          
                         
                           ( 
                           
                             t 
                             - 
                             k 
                           
                           ) 
                         
                       
                       . 
                     
                   
                 
               
             
           
         
       
     
         [0112]    In some examples, the outputs μ i  are each stored in a memory for example, between iterations or cycles of an iterative decoding operation. In other examples, the vales pass directly to an implementation of a AE circuit  712 , which computes 
         [0000]      ν=γπ i μ i  and/or (1−ν)=γπ i (1−μ i ),
 
         [0000]    for a suitable normalizing constant 
         [0000]      γ=(π i μ i +π i (1−μ i )) −1  
 
         [0000]    which guarantees ν+(1−ν)=1. 
         [0113]    In examples in which the likelihoods vary over time and the quantities μ i (t) may also be computed over time, then the output value ν(t) may also be computed over time, or at periodic intervals. 
         [0114]    Although the description above focuses on binary signals in which the variables may take on values 0 and 1, in other embodiments the approach is extended to M-ary variables. For example, M-1 integrators may be used to form values μ i   (m)  for m=1, . . . ,M. The output of the logic gate can then compute the appropriate values of ν (m)  according to which the output signal y(t) is resampled. 
         [0115]    In yet other embodiments, the approach is extended to multiple bit representations of variable. For example, bit X(t) and Y(t) are sequence of n-bit numbers sampled from a unimodal distribution, such as a Gaussian distribution, the approach described above is applied bit-wise. Therefore, for an n-bit representation X(t)=(x n-1 (t), . . . ,x 1 (t),x 0 (t)), and the n-bit representation of Y(t) defined similarly, each pair of inputs x i (t) and y i (t) is passed through a circuit as shown in  FIG. 1  to output through the integration and resampling process a corresponding bit output sequence z i (t). The output bits are then used to form the sampling of the n-bit output sequence Z(t)=(z n-1 (t), . . . , z 0 (t)). 
         [0116]    It should be understood that embodiments in which a Soft XOR function is performed on stochastic signals are only examples. Other factors (e.g., constraints) may be implemented in a belief propagation implementation of a factor graph such that the circuit implementation of those factors make use of input and/or output stochastic signals. 
         [0117]    In some implementations, one or more approaches to resampling and/or averaging are extended to introduce selected delays in the signal path, as a means of further mitigating potential correlation between the signals. The selection of such delays is described in copending application 61/306,880, titled “SELECTIVE DELAY OF DATA RECEIPT IN STOCHASTIC COMPUTATION”. In some implementation, a delay circuit is included on each of at least some of said signal paths links. Each delay module is configured or configurable to delay a signal represented as a time pattern traversing said signal path by an assigned delay. In some examples, the delay circuit is combined with a circuit component for converting between a signal level and a time pattern representation of a signals value on the signal path. 
         [0118]    Implementations of the approached described above may be implemented in circuitry, for example, integrated into a single integrated circuit. Such an integrated circuit may include other modules, such as a memory array, and the circuitry described above may be used to correct data errors in the memory array. The circuitry described above may be represented in functional information embodied in tangible data (e.g., on a computer storage medium) used to drive an automated (e.g., computer implemented) circuit layout or other circuit design or fabrication process. For example, modules described above may be tangibly embodied on computer readable media for providing driving the function of the automated processes. An example of such an embodiment may conform to a hardware description language specification language, such as Verilog. In some implementations, a combination of special-purpose circuitry and general purpose digital processing (e.g., using a processor) may be used to implement the approaches described above. 
         [0119]    It is to be understood that the foregoing description is intended to illustrate and not to limit the scope of the invention, which is defined by the scope of the appended claims. Other embodiments are within the scope of the following claims.