Abstract:
Methods and circuits are described for creating low-weight codes, encoding of data as low-weight codes for communication or storage, and efficient decoding of low-weight codes to recover the original data. Low-weight code words are larger than the data values they encode, and contain a significant preponderance of a single value, such as zero bits. The resulting encoded data may be transmitted with significantly lower power and/or interference.

Description:
FIELD OF THE INVENTION 
     The present invention relates to communications in general and in particular to the coding and transmission of signals capable of conveying information. 
     BACKGROUND 
     It is common practice for communications systems to translate information to be transmitted into a more suitable form for transmission over a communications channel. This encoding operation may be optimized in response to particular channel characteristics, such as available bandwidth, latency, noise, etc. The encoding and subsequent decoding operations may require considerable hardware resources or computational power, in particular in cases where the encoding produces longer code words. 
     An example of such codes are the so-called constant weight codes or low weight codes, which may briefly be described as codes in which the number of “1” bits per code word is low. These low weight codes have several applications. One of these applications is on-chip or chip-to-chip communications where the low “1” density translates into fewer signal transitions, minimizing channel crosstalk and simultaneous switching output (SSO) noise. In some bus communication schemes, power can be saved by employing constant weight or low-weight codes. Low weight codes may also have applications in volatile and non-volatile data storage. 
     [Arikan1] Arikan, E.;, “Source polarization,”  Information Theory Proceedings  ( ISIT ), 2010  IEEE International Symposium on , pp.899-903, 13-18 June 2010 doi: 10.1109/ISIT.2010.5513567 
     [Cronie, Korada] Cronie, H. S.; Korada, S. B.;, “Lossless source coding with polar codes,”  Information Theory Proceedings  ( ISIT ), 2010  IEEE International Symposium on , pp.904-908, 13-18 June 2010 doi: 10.1109/ISIT.2010.5513561 
     [Korada1] Korada, S; Sasoglu, E; Urbanke, R;, “Polar Codes: Characterization of Exponent, Bounds, and Constructions”, IEEE transactions on Information Theory, VOL. 56, NO. 12, December 2010 
     [MacKay1] MacKay, D; “Information Theory, Inference, and Learning Algorithms” 
     BRIEF SUMMARY 
     Methods are described for transferring information, including embodiments that enable very efficient encoding and decoding of low weight codes. This information transfer comprises an encoding step in which information symbols S=(s 1 , s 2 , . . . , s k ), comprising k elements, are converted into code symbols X=(x 1 , x 2 , . . . , x n ) comprising n elements, with n&gt;k; a transmission step for transmitting the code symbols X; and a decoding step for reconverting transmitted code symbols X into information symbols, comprising n elements, wherein in the encoding step auxiliary symbols V=(v 1 , v 1 , . . . , v p ), comprising p elements, are derived from information symbols S based on a predetermined encoding model and the code symbols X are derived in dependence of both the information symbols S and the auxiliary symbols V in accordance with a predetermined encoding algorithm such that the derived code symbols X are in conformity with the encoding model. 
     The use of a combination of information symbols and auxiliary symbols for the generation of code words enables more freedom and flexibility in the code generation, which can be used to implement an efficient code. 
     The term “transmission of information” as used herein should receive a broad interpretation. It covers, inter alia, real time transmitting information from a transmitter to a receiver over a transmission path, but also includes storage of information in a memory and later reading of the information from the memory. 
     In an embodiment, the auxiliary symbols are derived on the basis of a probabilistic computation using an encoding model determined by a predetermined constraint. This embodiment is suitable for the generation of low weight code words that have in each code word less than w bits with a predetermined logic value. 
     In a further embodiment, p=n-k, and the code symbols X are derived by a linear transform of intermediate symbols U=(u 1 , u 2 , . . . , u n ) comprising elements s i  of the information symbol S and the elements v j  of the auxiliary symbols V. The use of a linear transform is very advantageous since it can simply realized with combinatorial logic networks or with limited computing power. 
     Polarizing transforms are suitable for the creation of the code symbols out of the combinations of information symbols and auxiliary symbols. 
     In a further embodiment, the relation between the intermediate symbols U and the code symbols X being given by X=T −1 ·U with T being the m-fold kronecker product of 
               G   2     ⊗   m       =       [         1       1           0       1         ]       ⊗   m             
where 2 m =n.
 
     In a further embodiment, the elements s j  of the vector S correspond to the elements u i  of the vector U for which the entropies H(u i |u 0 , . . . , u i−1 ) are closest to 1, the other elements u j  of the vector U are equal to round (Pr(u i =1|u 0 , . . . , u i−1 )). This results in an efficient and robust encoding. 
     Another aspect provides an encoding method wherein information symbols S=(s 1 , s 2 , . . . , s k ), comprising k elements, are converted into code symbols X=(x 1 , x 2 , . . . , x n ), with n&gt;k wherein auxiliary symbols V=(v 1 , v 2 , . . . , v p ), comprising p elements, are derived from information symbols S based on a predetermined encoding model and the code symbols X are derived in dependence of both the information symbols S and the auxiliary symbols V in accordance with a predetermined encoding algorithm such that the derived code symbols X are in conformity with the encoding model. 
     A further aspect provides a decoding method wherein code symbols, comprising n elements, are transferred using a linear transform, in information symbols comprising k elements, with n&gt;k. 
     A further aspect provides an encoder circuit for transferring information symbols, comprising k elements, into code symbols comprising n elements, wherein the encoder circuit comprises a probabilistic computation unit configured to derive an auxiliary symbol, comprising p elements, from the information symbols, a permutation unit for combining elements of the information symbols and elements of the probabilistic computation unit into an intermediate symbol, and a transform unit for transforming the intermediate symbols into the code symbols. 
     A further aspect provides a decoding circuit for transferring code symbols, comprising n elements, into information symbols comprising k elements, wherein the decoding circuit is configured to perform a linear transformation of the code words for the conversion of the code symbols into information symbols. 
     A general method and circuitry for encoding and decoding low-weight codes are provided. The encoding and decoding complexity of these codes is very low. These codes can be used in a variety of chip-to-chip communication scenarios to reduce crosstalk, to provide resilience against SSO noise and to lower power consumption. These codes may also be used in wireless communication settings such as ultra-wide band and wireless sensor networks. Another application is in volatile and non-volatile storage of information. Low-weight codes may be used to lower power consumption and increase the protection against various types of noise and non-idealities. 
     The application of the invention is not limited to low weight codes. The invention also enables very low complexity encoding and decoding of other categories of codes, which may have been created to reflect other design constraints. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  illustrates an encoder system for low-weight codes. 
         FIG. 2  shows a flow chart for the encoding process. 
         FIG. 3  shows a preferred embodiment of a decoder. 
         FIG. 4  comprises  FIGS. 4A-4C , which illustrate factor graphs for the linear transforms of Equations 1, 2, and 3, respectively. 
         FIG. 5  further describes the factor graph of Equation 1. 
         FIG. 6  shows a factor graph for the example of a code where N=16, which may be used in performing the computation of Equation 8. 
         FIG. 7  further describes the method of computation using the factor graph. 
         FIG. 8  shows a factor graph for the example of a code where N=32. 
     
    
    
     DETAILED DESCRIPTION 
     A first embodiment is described with reference to  FIG. 1 , presenting encoder circuitry  100  that takes as its input a sequence of k source symbols  105  that are denoted by s 1 , . . . ,s k . The output of the encoder circuitry is a set of n bits that forms a low-weight code word  150 . A main task of encoder circuitry  100  as exemplified in  FIG. 1  is to input a source symbol capacitor of k source symbols s 1 , . . . ,s k  into a distinct low-weight code word of which the coordinates are denoted by x 1 , . . . ,x n  in such manner that the encoding and decoding can be implemented efficiently. Without loss of generality, it is assumed that these source symbols  105  are bits, although in some cases these source symbols may be taken from another non-binary alphabet. These source bits are input to a probabilistic computation unit (PCU)  110 . PCU  110  is configured to compute a set of auxiliary symbols comprising n-k elements (similarly, here assumed to be in the form of bits) that are denoted by v 1 , . . . , v n-k . For this purpose, PCU  110  uses a model of the code words to be generated and a representation of this model  112  is stored in electronic storage. Both the source bits s 1 , . . . , s k  and the output bits v 1 , . . . , v n-k  as generated by PCU  110  are input to a permutation unit  130 . One main task of permutation unit  130  is to construct an intermediate symbol in the form of a single vector of size n out of the k bits s 1 , . . . , s k  and n-k bits v 1 , . . . , v n-k . The way this may be done is by creating a single vector out of the bits s 1 , . . . , s k  and bits v 1 , . . . , v n-k  and then applying a permutation matrix P. This process is performed by permutation unit  130 . The output of permutation unit  130  is input to a transform unit  140 , preferably a linear transform unit. Transform unit  140  is defined by a transform matrix T′. By choosing T′ and the probabilistic model  112  in the right way, the output of the transform unit  140  is a code word that has a low weight. A typical relation might be x=Tc. In some cases, it might be useful to generate c and construct the x from data bits and auxiliary bits. Then, c is given by T′x, where T′ is the inverse of T. 
     A flowchart detailing the encoding process is now further described with reference to  FIG. 2 . The main encoding process can be broken down in four steps. In the first step  210 , the input symbols s 1 , . . . , s k  are received. In the second step  220 , the auxiliary symbols v 1 , . . . , v n-k  are computed. Step  220  may be performed by PCU unit  110  shown in  FIG. 1 . In the third step  230 , the symbols s 1 , . . . , s k  and the auxiliary symbols v 1 , . . . , v n-k  are rearranged into a vector [c 1  c 2  . . . c n ]. In step  240 , a linear transform is applied to [c 1  c 2  . . . c n ] to obtain a low-weight code word [x 1  x 2  . . . x n ]. 
     An embodiment for decoder circuitry is now further described with reference to  FIG. 3 . The inputs to the decoder circuitry are the bits  305  x 1 , . . . , x n  that constitute a code word from a low-weight code word. Bits  305  and  330  might be stored in electronically readable storage or recovery. A linear transform unit  310  applies a linear transform to bits  305  x 1 , . . . , x n . The result of this transform is input to a selector unit  320  that selects k bits from the results of linear transform unit  310  to recover the original bits  330  s 1 , . . . , s k  as communication. 
     Linear Transform Units for Low Weight Encoding 
     The linear transform implemented by linear transform unit  140  may be defined by a matrix T′ that is the inverse of a matrix T. Where s i  and v i  are bits, the elements of T′ and T are binary as well and arithmetic is performed modulo-2. As one of skill in the art will recognize, one may also use symbols from a different algebraic structure, such as a finite field. In that case, arithmetic is performed according to the rules of that algebraic structure. In a preferred embodiment, the transformation T is chosen as a transformation that is able to polarize a sequence of random variables. Examples of such transforms are described in [Arikan1] in the context of error-correcting codes. A few examples of polarizing transforms of size 2, 4 and 8 are given in Eqn. 1, Eqn. 2 and Eqn. 3. 
     
       
         
           
             
               
                 
                   
                     T 
                     2 
                   
                   = 
                   
                     [ 
                     
                       
                         
                           1 
                         
                         
                           1 
                         
                       
                       
                         
                           0 
                         
                         
                           1 
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   
                     Eqn 
                     . 
                     
                         
                     
                     ⁢ 
                     1 
                   
                   ) 
                 
               
             
             
               
                 
                   
                     T 
                     4 
                   
                   = 
                   
                     
                       [ 
                       
                         
                           
                             
                               T 
                               2 
                             
                           
                           
                             
                               T 
                               2 
                             
                           
                         
                         
                           
                             0 
                           
                           
                             
                               T 
                               2 
                             
                           
                         
                       
                       ] 
                     
                     = 
                     
                       [ 
                       
                         
                           
                             1 
                           
                           
                             1 
                           
                           
                             1 
                           
                           
                             1 
                           
                         
                         
                           
                             0 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             1 
                           
                         
                         
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             1 
                           
                         
                         
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                         
                       
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   
                     Eqn 
                     . 
                     
                         
                     
                     ⁢ 
                     2 
                   
                   ) 
                 
               
             
             
               
                 
                   
                     
                       T 
                       8 
                     
                     = 
                     
                       
                         [ 
                         
                           
                             
                               
                                 T 
                                 4 
                               
                             
                             
                               
                                 T 
                                 4 
                               
                             
                           
                           
                             
                               0 
                             
                             
                               
                                 T 
                                 4 
                               
                             
                           
                         
                         ] 
                       
                       = 
                       
                         [ 
                         
                           
                             
                               1 
                             
                             
                               1 
                             
                             
                               1 
                             
                             
                               1 
                             
                             
                               1 
                             
                             
                               1 
                             
                             
                               1 
                             
                             
                               1 
                             
                           
                           
                             
                               0 
                             
                             
                               1 
                             
                             
                               0 
                             
                             
                               1 
                             
                             
                               0 
                             
                             
                               1 
                             
                             
                               0 
                             
                             
                               1 
                             
                           
                           
                             
                               0 
                             
                             
                               0 
                             
                             
                               1 
                             
                             
                               1 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               1 
                             
                             
                               1 
                             
                           
                           
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               1 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               1 
                             
                           
                           
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               1 
                             
                             
                               1 
                             
                             
                               1 
                             
                             
                               1 
                             
                           
                           
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               1 
                             
                             
                               0 
                             
                             
                               1 
                             
                           
                           
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               1 
                             
                             
                               1 
                             
                           
                           
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               1 
                             
                           
                         
                         ] 
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     
                       
                         = 
                       
                       
                         
                           ( 
                           
                             Eqn 
                             . 
                             
                                 
                             
                             ⁢ 
                             4 
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   
                     Eqn 
                     . 
                     
                         
                     
                     ⁢ 
                     3 
                   
                   ) 
                 
               
             
           
         
       
     
     Many types of polarizing matrices are known to those of skill in the art. For instance, Korada1 describes several types of polarizing matrices. Note that the modulo-2 inverses of the matrices shown in Eqn. 1, Eqn. 2 and Eqn. 3 are given by the matrices itself. In this case T′=T. 
     Probabilistic Computation Unit 
     Encoders and decoders for low-weight codes disclosed in this application can operate as follows. Consider a set of random variables X 1 , . . . , X n  modeling the coordinates of a low-weight code word. We may choose these variables as independently and identically distributed, where Pr(X i =1)=p. For a low-weight code word, p is substantially smaller than 0.5 and may be chosen as, e.g., 0.1. A transform T can be applied to the random variables X 1 , . . . , X n  to give a set of random variables C 1 , . . . , C n . The transform T can be chosen in such a way that the distribution of each of the C i  given the realization of C 1 , . . . , C i−1  is either close to a uniform distribution or close to a distribution that has all of its mass on either 0 or 1. This is called “polarization,” which is a concept described in Arikan1 for error correcting codes. To construct a low weight code, the process is reversed. The elements of C 1 , . . . , C i−1  for which the distribution of C i  given the realization of C i , . . . , C i−1  is close to a uniform distribution are associated with the source bits. It is assumed that there are k of such elements of C i , . . . , C i−1 . The remaining n-k positions are associated with auxiliary random variables V 1 , . . . , V n-k . Since their distribution has almost all its mass on either 0 or 1, the values of V 1 , . . . , V n-k  can be estimated very reliably. This estimation is performed and for each of the C 1 , . . . , C n , a realization is now available. These realizations are denoted by c 1 , . . . , c n . The inverse of the transform T is applied to this vector of realization and the result is a vector x 1 , . . . , x n  that has a low weight. 
     One task of PCU  110  is to compute the auxiliary bit variables v 1 , . . . , v n-k  based on the source bits s 1 , . . . , s k . For this purpose, PCU  110  can use a probabilistic model that describes the statistics of the low-weight code words to be generated. In a preferred embodiment, the probabilistic model used by the PCU models each of the components of [x 1 , . . . , x n ] as a random variable X i  taking values in [0,1] where the probability that X i =1 is equal to a predetermined number p. In preferred embodiments, p is chosen as a number close to zero, to reflect that low-weight words are to be generated. As an example, the value of p may be chosen as 0.1, which corresponds to a code word of which on average one tenth of the components are equal to 1. 
     The relation between the symbols of the code words [x 1 , . . . , x n ] and the symbols [c 1 , . . . , c n ] is defined by the linear transform (or the inverse of the linear transform). As known to those of skill in the art, this relation may be depicted by a factor graph. A concise description of factor graphs is given in, e.g., MacKay1. The factor graphs for the transformations as defined by Eqn. 1-3 are depicted in  FIGS. 4   a ,  4   b , and  4   c , and make use of a recursive construction of the matrices as defined in Eqn. 1, Eqn. 2, and Eqn. 3 respectively 
     Given a set of source bits s 1 , . . . , s k  to be encoded into a low-weight code word, the PCU sets k of the bits c 1 , . . . , c n  to the values of the source bits. In terms of random variables, this means that the realization of the corresponding c i  is fixed. Which values are being set may be determined by an offline procedure such as that disclosed below. The other positions of c 1 , . . . , c n  form the auxiliary random variables v 1 , . . . , v n-k . 
     In the next step, the PCU sequentially computes the most likely value of v 1 , . . . , v n-k  given the values of s 1 , . . . , s k  and the probabilistic model. This computation is performed in a sequential fashion. For instance, first the probability that v i =1 is computed, and when this probability is larger than 0.5, it is assumed that v 1  is equal to 1. Next, the probability that v 2 =1 is computed, and when this probability is larger than 0.5, it is assumed that v 2  is equal to 1. 
     As an example, consider the factor graph shown in  FIG. 5  for the transformation of Eqn. 1. Here it is assumed that the first variable corresponding to c 2  and denoted by  510  in  FIG. 5  is the auxiliary variable v 1 . In this case, only a single source bit s 1  is encoded and the first variable c 1  is set to this first bit. Now, the task of the PCU  110  is to compute the most likely value for v 1  given the value of the source bit and the probability model on [x 1  x 2 ]. In  FIG. 5  it is assumed that the probability that x 1  and x 2  are equal to 1 is 0.1. Furthermore, it is assumed that s 1 =0. The probability p 1  that v 1  is equal to 1 can be expressed as: 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           p 
                           1 
                         
                         = 
                           
                         ⁢ 
                         
                           
                             
                               Pr 
                               ⁡ 
                               
                                 [ 
                                 
                                   
                                     x 
                                     1 
                                   
                                   = 
                                   1 
                                 
                                 ] 
                               
                             
                             · 
                             
                               Pr 
                               ⁡ 
                               
                                 [ 
                                 
                                   
                                     x 
                                     2 
                                   
                                   = 
                                   1 
                                 
                                 ] 
                               
                             
                           
                           
                             
                               
                                 Pr 
                                 ⁡ 
                                 
                                   [ 
                                   
                                     
                                       x 
                                       1 
                                     
                                     = 
                                     1 
                                   
                                   ] 
                                 
                               
                               · 
                               
                                 Pr 
                                 ⁡ 
                                 
                                   [ 
                                   
                                     
                                       x 
                                       2 
                                     
                                     = 
                                     1 
                                   
                                   ] 
                                 
                               
                             
                             + 
                             
                               
                                 Pr 
                                 ⁡ 
                                 
                                   [ 
                                   
                                     
                                       x 
                                       1 
                                     
                                     = 
                                     0 
                                   
                                   ] 
                                 
                               
                               · 
                               
                                 Pr 
                                 ⁡ 
                                 
                                   [ 
                                   
                                     
                                       x 
                                       2 
                                     
                                     = 
                                     0 
                                   
                                   ] 
                                 
                               
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         ⁢ 
                         
                           
                             
                               0.1 
                               · 
                               0.1 
                             
                             
                               
                                 0.1 
                                 · 
                                 0.1 
                               
                               + 
                               
                                 0.9 
                                 · 
                                 0.9 
                               
                             
                           
                           = 
                           0.12 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   
                     Eqn 
                     . 
                     
                         
                     
                     ⁢ 
                     4 
                   
                   ) 
                 
               
             
           
         
       
     
     In this case, the value of the auxiliary variable v 1  is set to 0. These computations can be efficiently computed by a message-passing algorithm on the factor graph. 
     Low-weight Code Generation with N=16 
     Generation of low weight code words for N=16 is presented as a specific embodiment of the previously described method. Without loss of generality, it is assumed that 2 k  code words are required, where k=8. Let s 0 , . . . , s k−1  denote the k source bits to be encoded into a low weight code work X comprising the components x 0 , . . . , x n−1 . A set of random variables X 0  . . . X 15  is defined that are assumed to be independent and identically distributed binary random values with Pr[X i =1]=p=0.05 (in other words, each bit has a 0.05 probability of having a value of ‘1’.) With this probabilistic model, the number of 1s in X follows a binomial distribution with mean 16×0.05=0.8. A second sequence of random variables U 0  . . . U 15  is generated by application of the matrix of Eqn. 5. 
     
       
         
           
             
               
                 
                   
                     T 
                     16 
                   
                   = 
                   
                     
                       [ 
                       
                         
                           
                             
                               T 
                               8 
                             
                           
                           
                             
                               T 
                               8 
                             
                           
                         
                         
                           
                             0 
                           
                           
                             
                               T 
                               8 
                             
                           
                         
                       
                       ] 
                     
                     = 
                     
                       [ 
                       
                         
                           
                             1 
                           
                           
                             1 
                           
                           
                             1 
                           
                           
                             1 
                           
                           
                             1 
                           
                           
                             1 
                           
                           
                             1 
                           
                           
                             1 
                           
                           
                             1 
                           
                           
                             1 
                           
                           
                             1 
                           
                           
                             1 
                           
                           
                             1 
                           
                           
                             1 
                           
                           
                             1 
                           
                           
                             1 
                           
                         
                         
                           
                             0 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             1 
                           
                         
                         
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             1 
                           
                         
                         
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                         
                         
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             1 
                           
                           
                             1 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             1 
                           
                           
                             1 
                           
                           
                             1 
                           
                         
                         
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             1 
                           
                         
                         
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             1 
                           
                         
                         
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                         
                         
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             1 
                           
                           
                             1 
                           
                           
                             1 
                           
                           
                             1 
                           
                           
                             1 
                           
                           
                             1 
                           
                           
                             1 
                           
                         
                         
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             1 
                           
                         
                         
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             1 
                           
                         
                         
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                         
                         
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             1 
                           
                           
                             1 
                           
                           
                             1 
                           
                         
                         
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             1 
                           
                         
                         
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                           
                             1 
                           
                         
                         
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             1 
                           
                         
                       
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   
                     Eqn 
                     . 
                     
                         
                     
                     ⁢ 
                     5 
                   
                   ) 
                 
               
             
           
         
       
     
     The relation between these two sequences of random variables is depicted by the factor graph of  FIG. 6 . 
     The next step is to compute the entropy H(U i |U 1 , . . . , U i−1 ) for each U 1 , . . . , U 16 . For each i, this amounts to performing a density evolution operation where the initial density is defined by the probabilistic model Pr[X i =1]=0.05. Table 1 shows the conditional entropies of the resulting densities, and also shows P e , which is the error probability associated with the density. Note that this density evolution process is only used to construct the actual code, and thus only needs to be performed during code construction. 
     
       
         
               
             
               
               
               
               
             
               
               
               
               
             
           
               
                 TABLE 1 
               
             
             
               
                   
               
               
                 The results of density evolution for U 1 , . . . , U 16   
               
             
          
           
               
                   
                 i 
                 H(Ui | U0, . . . , Ui-1) 
                 Pe 
               
               
                   
                   
               
             
          
           
               
                   
                  1 
                 0.97513 
                 0.407349 
               
               
                   
                  2 
                 0.749006 
                 0.284766 
               
               
                   
                  3 
                 0.692846 
                 0.284766 
               
               
                   
                  4 
                 0.23202 
                 0.0785324 
               
               
                   
                  5 
                 0.648484 
                 0.284766 
               
               
                   
                  6 
                 0.186088 
                 0.068833 
               
               
                   
                  7 
                 0.133813 
                 0.0494342 
               
               
                   
                  8 
                 0.00663544 
                 0.00225086 
               
               
                   
                  9 
                 0.618027 
                 0.284766 
               
               
                   
                 10 
                 0.157456 
                 0.0639566 
               
               
                   
                 11 
                 0.106202 
                 0.042468 
               
               
                   
                 12 
                 0.00395376 
                 0.00144652 
               
               
                   
                 13 
                 0.070642 
                 0.0283753 
               
               
                   
                 14 
                 0.00188375 
                 0.000693729 
               
               
                   
                 15 
                 0.00102683 
                 0.000387081 
               
               
                   
                 16 
                 5.01089e-07 
                 1.82957e-07 
               
               
                   
                   
               
             
          
         
       
     
     Now, a set of indices is defined corresponding to the set of k largest entropies. With the entropies defined in Table 1, the set F is given by Equation 6, which correspond to the k values of i in Table 1 having the largest conditional entropy, and where these indices will correspond to the k source bits s 1 , . . . , s k .
 
 F={ 1, 2, 3, 4, 5, 6, 9, 10}  (Eqn. 6)
 
     Encoding is performed by setting the values of U F  to the values of s 1 , . . . , s k  (that is, the bits of U indexed by the value of F corresponding to each of the bits of s) and the values of the remaining U F  are estimated using the probabilistic model of X 1  . . . X 16  together with the values of the source bits. Denote the complement of the set F with respect to the integers 1, . . . , 16 by U F   c . The value of each of the U i  where I is from U F   c  may be estimated by computing
 
 Pr ( U   i =1| U   1   =u   1   , . . . , U   i−1   =u   i−1 )  (Eqn. 7)
 
and the value of Ui is estimated as
 
 û   i =round( Pr ( U   i =1| U   1   =u   1   , . . . , U   i−1   =u   i−1 ))  (Eqn. 8)
 
     The factor graph of  FIG. 6  may be used for the computation of Eqn. 8. The first U i  to be estimated is U 7  and the computation in the factor graph is illustrated in  FIG. 7 . 
     In  FIG. 7 , the light gray variable nodes (circle  703 , as one example,) corresponding to X 1  . . . X 16  (identified as  702  etc.) are initialized according to their probabilistic model. The outputs of the gray check nodes (square  704  shown as one example) correspond to log-likelihood ratios of 0 since the prior distribution on U 9  . . . U 16  is uniform. Since U 1  . . . U 6  are known (having been set to (s 1 , . . . , s 6 ), the black variable nodes are known also. To compute Pr(U 7 ) a message pass (one portion of which is identified as the sequence  705  through  711 ) is performed on the highlighted tree toward the node U 7  and the estimate for U 7  is generated as
 
 Û   7 =round( Pr ( U   i =1| U   0   =u   0   , . . . , U   i−1   =u   i−1 ))  (Eqn. 9)
 
     For the computation of P(U i |U 0 , . . . , U i−1 ) the factor graph of  FIG. 6  may be used. Some of the encodings are illustrated in Table 2. All generated code words are of low weight, having an average weight of 2.75 and a maximum weight of 4. The weight distribution is shown in Table 3. 
     
       
         
               
             
               
               
               
             
           
               
                 TABLE 2 
               
             
             
               
                   
               
               
                 Low-weight code words for 
               
               
                 several input sequences 
               
             
          
           
               
                   
                 s0 . . . s7 
                 x0 . . . x15 
               
               
                   
                   
               
               
                   
                 00000000 
                 0000000000000000 
               
               
                   
                 11001000 
                 0100000000100010 
               
               
                   
                 01100100 
                 0000011000000000 
               
               
                   
                 11101100 
                 0000010000001010 
               
               
                   
                 11101010 
                 1100000000000010 
               
               
                   
                 10011110 
                 0100000100100000 
               
               
                   
                 11101101 
                 0000100000000110 
               
               
                   
                 01100111 
                 0000001000000100 
               
               
                   
                 10111111 
                 1100000000000001 
               
               
                   
                   
               
             
          
         
       
     
     
       
         
               
             
               
               
               
             
               
               
               
             
           
               
                 TABLE 3 
               
             
             
               
                   
               
               
                 The weight distribution of the  
               
               
                 low-weight code for n = 16 
               
             
          
           
               
                   
                 Weight 
                 # 
               
               
                   
                   
               
             
          
           
               
                   
                 0 
                 1 
               
               
                   
                 1 
                 16 
               
               
                   
                 2 
                 78 
               
               
                   
                 3 
                 112 
               
               
                   
                 4 
                 49 
               
               
                   
                 5 . . . 16 
                 0 
               
               
                   
                   
               
             
          
         
       
     
     Decoding a low weight code word to the original bits is extremely simple, as shown in  FIG. 3 . The low-weight code word  300  is transformed  310  by a multiplication by T 16  as presented in Eqn. 5. The original bits  330  may then be read from the transformed result by selecting them  320  from the locations indexed by vector F, which correspond to the k highest entropy values identified during code creation. This operation is requires about 64 exclusive-or operations in total. 
     Compared to an equivalent link transmitting the original source bits without low weight coding, the power consumption of a chip-to-chip link utilizing this code may be reduced by a factor of 1.5. 
     Low-weight Code Generation with N=32 
     Another example of a preferred embodiment may be used to generate low-weight code words for n=32. Without loss of generality, we assume that 2 k  code words are required, where k=16. Let s 1 , . . . , s 16  denote the 16 source bits to be encoded into a low-weight code word x of which the components are denoted by x 1 , . . . , x n . We define a set of random variables X 1 , . . . , X 32  where we assume that these random variables are independent and identically distributed, with Pr[Xi=0]=0.95. With this probabilistic model, the number of 1s in X 1 , . . . , X 32  would follow a binomial distribution with mean 32×0.05=1.6. A second sequence of random variables U 1 , . . . , U 32  is generated by application of the matrix G           5. In a similar way as for the previous example of a code word length of 16, we can generate a factor graph as shown in  FIG. 8 . The next step is to compute the entropy&#39;s H(Ui|U 1 , . . . , U i−1 ) for U 1 , . . . , U 31 . For each i this amounts to performing a density evolution operation where the initial density is defined by the probabilistic model (Pr[Xi=0]=0.95). Table 4 shows the conditional entropies of the resulting densities. With these entropy values, the set F is chosen as in Equation 10, which correspond to the k values of i in Table 4 having the largest conditional entropy, and where these indices will correspond to the k source bits s 1 , . . . , s k .
 
 F={ 1,2,3,4,5,6,7,9,10,11,13,17,18,19,21,25}  (Eqn. 10)

     Encoding is performed by setting the values of U F  to the values of s 1 , . . . , s 16  and the values of the remaining U F   c  are estimated. For this estimation, the probabilistic model of X 1 , . . . , X n  is used together with the values of the source bits. The value of each of the U i  from U F   c  can be estimated by computing U i  we compute Pr(U i =1|U 1 =u 0 , . . . , U i−1 ≦u i−1 ), and the value of U i  is estimated as û i =round(Pr(U i =1|U 1 ,=u 0 , . . . , U i−1 =u i−1 )). 
     
       
         
               
             
               
               
             
           
               
                 TABLE 5 
               
             
             
               
                   
               
               
                 Low-weight code words for several input sequences 
               
             
          
           
               
                 s0 . . . s15 
                 x0 . . . x31 
               
               
                   
               
               
                 0010000010111000 
                 10001001000000000000100000100001 
               
               
                 0000100010111000 
                 00000100000000000000100010000100 
               
               
                 1011111110111000 
                 10000000000000010001000001010000 
               
               
                 0111011100100100  
                 00000100000010000000010100000000 
               
               
                 1011100010100100  
                 00010000000110000000000001010000 
               
               
                 0101001010100100  
                 00000000011000000100010001000001 
               
               
                 1110111101100100  
                 00001100000010000000000000001010 
               
               
                 0101110011100100  
                 00000000100000010000101000000000 
               
               
                 1111101011110110  
                 00000000001100001000000010000010 
               
               
                   
               
             
          
         
       
     
     For the computation of P (U i |U 1 , . . . , U i−1 ) the factor graph of  FIG. 8  can be used. A few encodings are given in Table 5. All generated words are of low-weight and the weight distribution is given in Table 6. The average weight of a word is 4.84 and the maximum weight is 6. 
     
       
         
               
             
               
               
               
             
               
               
               
             
           
               
                 TABLE 6 
               
             
             
               
                   
               
               
                 The weight distribution of the 
               
               
                 low-weight code for n = 32 
               
             
          
           
               
                   
                 Weight 
                 # 
               
               
                   
                   
               
             
          
           
               
                   
                 0 
                 1 
               
               
                   
                 1 
                 32 
               
               
                   
                 2 
                 496 
               
               
                   
                 3 
                 4960 
               
               
                   
                 4 
                 15655 
               
               
                   
                 5 
                 27776 
               
               
                   
                 6 
                 16616 
               
               
                   
                   
               
             
          
         
       
     
     Decoding the low-weight code word to the original bits is simple. Decoding is accomplished by multiplying the low-weight code word with G 2             5 and then selecting from the result the original bits, which may be found at the bit locations identified by the values of vector F, which correspond to the k highest entropy values found during code creation. The decoding operation requires approximately 160 operations in total. This scales as N log 2(N). So in this case 32*log 2(32)=160 or 5 operations per code word bit.
     Compared to an equivalent link transmitting the original source bits without low weight coding, the power consumption of a chip-to-chip link utilizing this code may be reduced by a factor of 1.7. 
     Applications of Low-weight Codes 
     Some communication scenarios permit wide buses to be used. One example is on-chip communications, where the number of wires is often not a limiting factor. Another example is package-on-package chip-to-chip buses where a large number of balls, through-vias, or bonding wires can be used to connect the two chips. Such systems may not have strong constraints on the total number of wires in the interconnect, but may still have constraints on power utilization or on simultaneous switching noise or crosstalk. The techniques presented herein can provide a way to mitigate these power and noise issues. 
     Such wide buses are also used in CPU-memory communications, such as a recent DRAM interface design where a single DRAM is fed with 128 wires. With the techniques presented herein, it may be beneficial to use a large number of wires carrying low-weight words. 
     Storage Applications of Low-weight Codes 
     Some storage devices can have different power, latency, and addressability characteristics when storing a ‘1’ bit versus a ‘0’ bit. For example, some Flash EEPROM devices permit individual 0 bits to be written directly, but 1 bits may be written only by block-erasing a large range of words. For such systems, storage constraints may be relaxed by storing only low-weight code words having a preponderance of a preferred bit value. 
     Wireless Low Power Communications 
     In one embodiment, low-weight code words are used as a form of low-weight pulse position modulation for low-power wireless communications. The consecutive positions of a low-weight code word are transmitted in consecutive time intervals. Typically, power consumption of the final transmitter output stage is directly related to the weight of the transmitted code word, enabling substantial power savings. 
     In a further embodiment, the RF communications channel uses ultra-wide band transmission, where each ‘1’ value in a low weight code word is transmitted as a pulse with a width of about 1 ns or smaller. As an example, a code word length of 64 would thus produce a symbol length of about 64 ns or less. Information is spread across a wide range of spectrum and very low power operation may be achieved. Similar techniques can be applied in wireless sensor networks. 
     Ternary Codes and Codes on Higher Alphabets 
     The methods described herein can easily be extended to ternary codes, allowing for higher pin-efficiency, while maintaining low power consumption and good crosstalk properties. The extension to even higher-order alphabets is also possible, as is extension to generalized transforms. 
     Suboptimal Message-passing Algorithms 
     For encoding, a message passing algorithm has been described that operates on a tree structure. That is, as previously described all variable nodes and check nodes have degree 2. One may use suboptimal rules at the variable nodes and check nodes to make hardware implementation easier. As one example, a min operator may be used for the update rule at the check nodes. 
     Additional Power Savings by Transmitting Symbol Differences 
     One embodiment provides additional power savings by transmitting differences between the present and previous code words. Let x 1  denote the first word that is to be transmitted on the bus, which is encoded into a low-weight code word c 1 . This code word is transmitted on the bus and the word c 1  is stored temporarily at the transmitter and receiver. Let x 2  denote the second word that is to be transmitted on the bus, which is encoded into c 2  and the positions of the stored value c 1  corresponding to the ones in c 2  are flipped, leading to a word c 2 ′. (That is, c 2 ′ is the exclusive-or of c 1  and c 2 .) The word c 2 ′ is transmitted, and the original value c 2  is stored. At the receiver, the difference between c 2 ′ and the stored value of c 1  is determined, (again, preferably by exclusive-or&#39;ing the received word and the stored word,) recovering the value c 2  which is stored at the receiver for subsequent use, and is used to recover the second sequence of source bits x 2  by decoding. The initial values stored in both transmitter and receiver should be initialized prior to communication, preferably to the common value of zero. 
     Combination with Crosstalk Cancellation Techniques 
     The fact that the words on the bus are of low weight can have additional advantages. Since there are only few ‘1’ values, generally equating to few signal lines being driven and/or fewer signal line transitions, the effects of crosstalk may be cancelled much easier than conventional bus communication systems. Each of the drivers that drives a “1” can take its neighbors into account also. Worse case crosstalk limits the speed in a bus communication system where the wires are modeled as capacitive loads and simple inverters are used to drive the wires. With these techniques, the speed may be increased substantially. 
     Hardware Implementation 
     Once the probabilistic computation has been performed to create a particular low density code, it is possible to perform encoding operations using that code using only a look-up table pre-computed from the factor graph of the code. For example, a 16 bit low-weight code requires a look-up table containing 2^16 entries, where each entry comprises 32 bits. However, a simple encoding look-up table of this type becomes infeasible for larger codes, growing to require 2^32 entries of 64 bits each for the case of a 32 bit code. Even in such cases hybrid encoding methods may be tractable, pre-computing look-up tables to replace the more computationally complex portions of the factor graph, and relying on factor graph traversal for the remainder of the encoding. It is also possible to intentionally find suboptimal encodings during the code generation process, with the intent of producing factor graphs containing less computationally complex structures that, as an example, are more easily implemented as hardware circuits.