Methods and systems for low weight coding

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.

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.

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=(s1, s2, . . . , sk), comprising k elements, are converted into code symbols X=(x1, x2, . . . , xn) comprising n elements, with n>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=(v1, v1, . . . , vp), 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=(u1, u2, . . . , un) comprising elements siof the information symbol S and the elements vjof 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

In a further embodiment, the elements sjof the vector S correspond to the elements uiof the vector U for which the entropies H(ui|u0, . . . , ui−1) are closest to 1, the other elements ujof the vector U are equal to round (Pr(ui=1|u0, . . . , ui−1)). This results in an efficient and robust encoding.

Another aspect provides an encoding method wherein information symbols S=(s1, s2, . . . , sk), comprising k elements, are converted into code symbols X=(x1, x2, . . . , xn), with n>k wherein auxiliary symbols V=(v1, v2, . . . , vp), 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>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.

DETAILED DESCRIPTION

A first embodiment is described with reference toFIG. 1, presenting encoder circuitry100that takes as its input a sequence of k source symbols105that are denoted by s1, . . . ,sk. The output of the encoder circuitry is a set of n bits that forms a low-weight code word150. A main task of encoder circuitry100as exemplified inFIG. 1is to input a source symbol capacitor of k source symbols s1, . . . ,skinto a distinct low-weight code word of which the coordinates are denoted by x1, . . . ,xnin such manner that the encoding and decoding can be implemented efficiently. Without loss of generality, it is assumed that these source symbols105are 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. PCU110is 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 v1, . . . , vn-k. For this purpose, PCU110uses a model of the code words to be generated and a representation of this model112is stored in electronic storage. Both the source bits s1, . . . , skand the output bits v1, . . . , vn-kas generated by PCU110are input to a permutation unit130. One main task of permutation unit130is to construct an intermediate symbol in the form of a single vector of size n out of the k bits s1, . . . , skand n-k bits v1, . . . , vn-k. The way this may be done is by creating a single vector out of the bits s1, . . . , skand bits v1, . . . , vn-kand then applying a permutation matrix P. This process is performed by permutation unit130. The output of permutation unit130is input to a transform unit140, preferably a linear transform unit. Transform unit140is defined by a transform matrix T′. By choosing T′ and the probabilistic model112in the right way, the output of the transform unit140is 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 toFIG. 2. The main encoding process can be broken down in four steps. In the first step210, the input symbols s1, . . . , skare received. In the second step220, the auxiliary symbols v1, . . . , vn-kare computed. Step220may be performed by PCU unit110shown inFIG. 1. In the third step230, the symbols s1, . . . , skand the auxiliary symbols v1, . . . , vn-kare rearranged into a vector [c1c2. . . cn]. In step240, a linear transform is applied to [c1c2. . . cn] to obtain a low-weight code word [x1x2. . . xn].

An embodiment for decoder circuitry is now further described with reference toFIG. 3. The inputs to the decoder circuitry are the bits305x1, . . . , xnthat constitute a code word from a low-weight code word. Bits305and330might be stored in electronically readable storage or recovery. A linear transform unit310applies a linear transform to bits305x1, . . . , xn. The result of this transform is input to a selector unit320that selects k bits from the results of linear transform unit310to recover the original bits330s1, . . . , skas communication.

Linear Transform Units for Low Weight Encoding

The linear transform implemented by linear transform unit140may be defined by a matrix T′ that is the inverse of a matrix T. Where siand viare 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.

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 X1, . . . , Xnmodeling the coordinates of a low-weight code word. We may choose these variables as independently and identically distributed, where Pr(Xi=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 X1, . . . , Xnto give a set of random variables C1, . . . , Cn. The transform T can be chosen in such a way that the distribution of each of the Cigiven the realization of C1, . . . , Ci−1is 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 C1, . . . , Ci−1for which the distribution of Cigiven the realization of Ci, . . . , Ci−1is close to a uniform distribution are associated with the source bits. It is assumed that there are k of such elements of Ci, . . . , Ci−1. The remaining n-k positions are associated with auxiliary random variables V1, . . . , Vn-k. Since their distribution has almost all its mass on either 0 or 1, the values of V1, . . . , Vn-kcan be estimated very reliably. This estimation is performed and for each of the C1, . . . , Cn, a realization is now available. These realizations are denoted by c1, . . . , cn. The inverse of the transform T is applied to this vector of realization and the result is a vector x1, . . . , xnthat has a low weight.

One task of PCU110is to compute the auxiliary bit variables v1, . . . , vn-kbased on the source bits s1, . . . , sk. For this purpose, PCU110can 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 [x1, . . . , xn] as a random variable Xitaking values in [0,1] where the probability that Xi=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 [x1, . . . , xn] and the symbols [c1, . . . , cn] 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 inFIGS. 4a,4b, and4c, 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 s1, . . . , skto be encoded into a low-weight code word, the PCU sets k of the bits c1, . . . , cnto the values of the source bits. In terms of random variables, this means that the realization of the corresponding ciis fixed. Which values are being set may be determined by an offline procedure such as that disclosed below. The other positions of c1, . . . , cnform the auxiliary random variables v1, . . . , vn-k.

In the next step, the PCU sequentially computes the most likely value of v1, . . . , vn-kgiven the values of s1, . . . , skand the probabilistic model. This computation is performed in a sequential fashion. For instance, first the probability that vi=1 is computed, and when this probability is larger than 0.5, it is assumed that v1is equal to 1. Next, the probability that v2=1 is computed, and when this probability is larger than 0.5, it is assumed that v2is equal to 1.

As an example, consider the factor graph shown inFIG. 5for the transformation of Eqn. 1. Here it is assumed that the first variable corresponding to c2and denoted by510inFIG. 5is the auxiliary variable v1. In this case, only a single source bit s1is encoded and the first variable c1is set to this first bit. Now, the task of the PCU110is to compute the most likely value for v1given the value of the source bit and the probability model on [x1x2]. InFIG. 5it is assumed that the probability that x1and x2are equal to 1 is 0.1. Furthermore, it is assumed that s1=0. The probability p1that v1is equal to 1 can be expressed as:

In this case, the value of the auxiliary variable v1is 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 2kcode words are required, where k=8. Let s0, . . . , sk−1denote the k source bits to be encoded into a low weight code work X comprising the components x0, . . . , xn−1. A set of random variables X0. . . X15is defined that are assumed to be independent and identically distributed binary random values with Pr[Xi=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 U0. . . U15is generated by application of the matrix of Eqn. 5.

The relation between these two sequences of random variables is depicted by the factor graph ofFIG. 6.

The next step is to compute the entropy H(Ui|U1, . . . , Ui−1) for each U1, . . . , U16. For each i, this amounts to performing a density evolution operation where the initial density is defined by the probabilistic model Pr[Xi=1]=0.05. Table 1 shows the conditional entropies of the resulting densities, and also shows Pe, 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.

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 s1, . . . , sk.
F={1, 2, 3, 4, 5, 6, 9, 10}  (Eqn. 6)

Encoding is performed by setting the values of UFto the values of s1, . . . , sk(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 UFare estimated using the probabilistic model of X1. . . X16together with the values of the source bits. Denote the complement of the set F with respect to the integers 1, . . . , 16 by UFc. The value of each of the Uiwhere I is from UFcmay be estimated by computing
Pr(Ui=1|U1=u1, . . . , Ui−1=ui−1)  (Eqn. 7)
and the value of Ui is estimated as
ûi=round(Pr(Ui=1|U1=u1, . . . , Ui−1=ui−1))  (Eqn. 8)

The factor graph ofFIG. 6may be used for the computation of Eqn. 8. The first Uito be estimated is U7and the computation in the factor graph is illustrated inFIG. 7.

InFIG. 7, the light gray variable nodes (circle703, as one example,) corresponding to X1. . . X16(identified as702etc.) are initialized according to their probabilistic model. The outputs of the gray check nodes (square704shown as one example) correspond to log-likelihood ratios of 0 since the prior distribution on U9. . . U16is uniform. Since U1. . . U6are known (having been set to (s1, . . . , s6), the black variable nodes are known also. To compute Pr(U7) a message pass (one portion of which is identified as the sequence705through711) is performed on the highlighted tree toward the node U7and the estimate for U7is generated as
Û7=round(Pr(Ui=1|U0=u0, . . . , Ui−1=ui−1))  (Eqn. 9)

For the computation of P(Ui|U0, . . . , Ui−1) the factor graph ofFIG. 6may 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.

Decoding a low weight code word to the original bits is extremely simple, as shown inFIG. 3. The low-weight code word300is transformed310by a multiplication by T16as presented in Eqn. 5. The original bits330may then be read from the transformed result by selecting them320from 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 2kcode words are required, where k=16. Let s1, . . . , s16denote the 16 source bits to be encoded into a low-weight code word x of which the components are denoted by x1, . . . , xn. We define a set of random variables X1, . . . , X32where 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 X1, . . . , X32would follow a binomial distribution with mean 32×0.05=1.6. A second sequence of random variables U1, . . . , U32is generated by application of the matrix G5. In a similar way as for the previous example of a code word length of 16, we can generate a factor graph as shown inFIG. 8. The next step is to compute the entropy's H(Ui|U1, . . . , Ui−1) for U1, . . . , U31. 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 s1, . . . , sk.
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 UFto the values of s1, . . . , s16and the values of the remaining UFcare estimated. For this estimation, the probabilistic model of X1, . . . , Xnis used together with the values of the source bits. The value of each of the Uifrom UFccan be estimated by computing Uiwe compute Pr(Ui=1|U1=u0, . . . , Ui−1≦ui−1), and the value of Uiis estimated as ûi=round(Pr(Ui=1|U1,=u0, . . . , Ui−1=ui−1)).

For the computation of P (Ui|U1, . . . , Ui−1) the factor graph ofFIG. 8can 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 6The weight distribution of thelow-weight code for n = 32Weight#01132249634960415655527776616616

Decoding the low-weight code word to the original bits is simple. Decoding is accomplished by multiplying the low-weight code word with G25 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.

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 x1denote the first word that is to be transmitted on the bus, which is encoded into a low-weight code word c1. This code word is transmitted on the bus and the word c1is stored temporarily at the transmitter and receiver. Let x2denote the second word that is to be transmitted on the bus, which is encoded into c2and the positions of the stored value c1corresponding to the ones in c2are flipped, leading to a word c2′. (That is, c2′ is the exclusive-or of c1and c2.) The word c2′ is transmitted, and the original value c2is stored. At the receiver, the difference between c2′ and the stored value of c1is determined, (again, preferably by exclusive-or'ing the received word and the stored word,) recovering the value c2which is stored at the receiver for subsequent use, and is used to recover the second sequence of source bits x2by 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.