Reduced latency error correction decoding

Systems, methods, and computer-readable media are disclosed for performing reduced latency error decoding using a reduced latency symbol error correction decoder that utilizes enumerated parallel multiplication in lieu of division and replaces general multiplication with constant multiplication. The use of parallel multiplication in lieu of division can provide reduced latency and replacement of general multiplication with constant multiplication allows for logic reduction. In addition, the reduced symbol error correction decoder can utilize decode term sharing which can yield a further reduction in decoder logic and a further latency improvement.

BACKGROUND

An error correcting code (ECC) is used to encode a message in a redundant manner so as to control errors in data transmission over unreliable or noisy communication channels. As computer systems become increasingly dense and complex, trade-offs are often made between cost, performance, density, and reliability, availability, and serviceability (RAS). The type of error correcting code that is used can influence the type of trade-offs that are made. For example, for large cache designs, an increased density may be achieved at the cost of high latency associated with error correction.

SUMMARY

In one or more example embodiments of the disclosure, a computer-implemented method for performing reduced latency error decoding of a received codeword that comprises a set of input symbols is disclosed. The method includes determining a first syndrome, a second syndrome, and a third syndrome associated with the received codeword and determining that at least one of the first syndrome, the second syndrome, or the third syndrome is non-zero. The method further includes determining a set of constant multipliers and performing a multiplication of the first syndrome with each constant multiplier in the set of constant multipliers to generate a set of products. The method additionally includes determining, based at least in part on the set of products, that a first condition is satisfied with respect to the second syndrome and determining that a second condition is satisfied with respect to the third syndrome. A single input symbol in the received codeword that contains one or more bit errors is then identified based at least in part on the first condition and the second condition being satisfied and the one or more bit errors in the single input symbol are corrected to obtain an original codeword.

In one or more example embodiments of the disclosure, a system for performing reduced latency error decoding of a received codeword that comprises a set of input symbols is disclosed. The system includes at least one memory storing computer-executable instructions and at least one processor configured to access the at least one memory and execute the computer-executable instructions to perform a set of operations. The operations include determining a first syndrome, a second syndrome, and a third syndrome associated with the received codeword and determining that at least one of the first syndrome, the second syndrome, or the third syndrome is non-zero. The operations further include determining a set of constant multipliers and performing a multiplication of the first syndrome with each constant multiplier in the set of constant multipliers to generate a set of products. The operations additionally include determining, based at least in part on the set of products, that a first condition is satisfied with respect to the second syndrome and determining that a second condition is satisfied with respect to the third syndrome. A single input symbol in the received codeword that contains one or more bit errors is then identified based at least in part on the first condition and the second condition being satisfied and the one or more bit errors in the single input symbol are corrected to obtain an original codeword.

In one or more example embodiments of the disclosure, a computer program product for performing reduced latency error decoding of a received codeword that comprises a set of input symbols is disclosed. The computer program product includes a storage medium readable by a processing circuit. The storage medium stores instructions executable by the processing circuit to cause a method to be performed. The method includes determining a first syndrome, a second syndrome, and a third syndrome associated with the received codeword and determining that at least one of the first syndrome, the second syndrome, or the third syndrome is non-zero. The method further includes determining a set of constant multipliers and performing a multiplication of the first syndrome with each constant multiplier in the set of constant multipliers to generate a set of products. The method additionally includes determining, based at least in part on the set of products, that a first condition is satisfied with respect to the second syndrome and determining that a second condition is satisfied with respect to the third syndrome. A single input symbol in the received codeword that contains one or more bit errors is then identified based at least in part on the first condition and the second condition being satisfied and the one or more bit errors in the single input symbol are corrected to obtain an original codeword.

DETAILED DESCRIPTION

Example embodiments of the disclosure include, among other things, systems, methods, computer-readable media, techniques, and methodologies for performing symbol error decoding and correction using an improved reduced latency symbol error correction decoder. In certain example embodiments, the reduced latency symbol error correction decoder may be an improved Reed-Solomon (RS) decoder that utilizes enumerated parallel multiplication in lieu of division and replaces general multiplication with constant multiplication. The use of parallel multiplication in lieu of division can provide reduced latency particularly for small numbers of symbols. Further, replacement of general multiplication with constant multiplication allows for logic reduction and reduced latency. In addition, in certain example embodiments, the reduced symbol error correction decoder can utilize decode term sharing which can yield a significant further reduction in decoder logic and further improvement in latency.

RS codes are a group of error correction codes that belong to the class of non-binary cyclic error correcting codes. RS codes are based on univariate polynomials over finite fields. The class of RS codes may include, for example, single error correction (SEC)/double error detection (DED) codes that are capable of detecting and correcting a single symbol with one or more bit errors and detecting but not correcting two symbols, each with one or more bit errors. An RS code using n-bit symbols can be defined over a Galois field (GF)(2n) with a maximum code length of 2n−1 symbols. For example, an RS code using 9-bit symbols can be defined over GF(29) with a maximum code length of 512−1=511 symbols. Each finite field has a primitive element a whose powers express all non-zero field elements. In particular, each codeword C in a SEC/DED RS code when viewed as a polynomial C(x) satisfies C(1)=0; C(α)=0; C(α2)=0.

More specifically, each symbol of the codeword C can be viewed as a coefficient of the polynomial C(x). For instance, in example embodiments of the disclosure, a codeword C may include 15 data symbols and 3 check/parity symbols. The polynomial C(x) would then be given as follows: C(x)=[symbol 1]+[symbol 2]x+[symbol 3]x2+ . . . +[symbol 18]x17. A property of RS codes is that there exists values 1, α, and α2that each yield the zero value for the polynomial C(x) assuming that no errors are present in the codeword C. The values of the polynomial C(x) at the values 1, α, and α2may be referred to as syndromes and may be given as follows: S0=C(1); S1=C(α); S2=C(α2). The syndromes may have the same bit length as the symbols of the codeword C.

When S0=S1=S2=0, it is assumed that no errors are present in the codeword C. However, if one or more symbol errors have been introduced to the codeword C, then one or more of the values 1, α, or α2may no longer yield zero values for the polynomial C(x). That is, if R is the sum of the original codeword C and any errors introduced to C during transmission, then one or more of the syndromes S1, S2, or S3given by R(1), R(α), and R(α2), respectively, may be non-zero. As a non-limiting example, assume that S0=[000010100]; S1=[101011110]; and S2=[101011011]. If there is one symbol error at position p within the received codeword R with a magnitude β then: S0=(3; S1=βαp; S2=βα2p. Thus, for a single symbol error, S0indicates which bits are in error within the single symbol that is in error. For instance, in this example, S0indicates that bits 4 and 6 are in error in the symbol that is in error. S0may be referred to as a bit-flip vector because it indicates which bits need to be flipped in the symbol in error in order to obtain the original data in the codeword C.

While S0indicates which bits need to be flipped in the single symbol in error, S1and S2can be used to determine the position p of that symbol in the received codeword R. As described above, syndrome S1is the product of the bit-flip vector S0and the value α raised to the power p, where p indicates the position of the single symbol that is in error. Conventional RS codes operate by first performing a check to determine whether the product of S0and S2equals S12. If so, it can be determined that a single symbol is in error. Conventional RS codes then divide S1by S0to yield αp, which is then compared to each of the powers of α (e.g., α0, α1, . . . , α(# of symbols−1)) to determine which power of α matches, which in turn, indicates the position p of the single symbol in error. Conventional RS codes may implement the division of S1by S0by first performing a lookup of a table of inverses to determine the inverse of S0(S0−1) and then multiplying S1by the inverse S0−1.

In contrast, an improved RS code in accordance with example embodiments of the disclosure performs enumerated parallel multiplication in lieu of division. Moreover, the enumerated parallel multiplication involves multiplication with constants (e.g., powers of α) in lieu of the general multiplication (e.g., the check as to whether S0S2=S12) that is associated with conventional RS codes. Thus, an improved RS code in accordance with example embodiments of the disclosure, achieves a reduction in latency as compared to conventional RS codes by utilizing constant multiplication in lieu of general multiplication. Further, an improved RS code in accordance with example embodiments of the disclosure achieves further reduced latency as compared to conventional RS codes by virtue of performing enumerated parallel multiplication in lieu of division.

More specifically, rather than dividing S1by S0, an improved RS code in accordance with example embodiments of the disclosure performs a multiplication of S0with each power of α (e.g., α0, α1, . . . α(# of symbols−1)) to determine whether any of the resulting products matches S1. In addition, an improved RS code in accordance with example embodiments of the disclosure also performs a multiplication of S1with each power of α (e.g., α0, α1, α(# of symbols−1)) to determine whether any of the resulting products matches S2. In certain example embodiments, both of these checks may be performed in parallel. If both of these conditions are met by the same power (p) of α, then it can be determined that a single correctable symbol error is present. This enumerated parallel multiplication with constants achieves a latency reduction over the general multiplication and division performed by conventional RS codes.

After performing the enumerated parallel multiplication described above, if there are no matches, it can be determined that there is more than one error in the codeword C. If there is a single match—that is if the product of S0and αpmatches S1(S0*αp=S1) for a given p and the product of S1and αpmatches S2for the same p (S1*αp=S2)—then it can be determined that there is a single symbol error, and the power of α in the matching products indicates the position of the single symbol in error. If a single error is detected, then S0=β can be added (XORed) with the symbol in the received codeword R that is at position p to correct the error(s) in that symbol and obtain the original codeword C. In the example introduced above, the bit-flip vector S0would be XORed with the symbol at position p. On the other hand, if both of these conditions are not met—that is if there is no value of p for which S0*αp=S1and S1*αp=S2—then multiple symbol errors are present in the received codeword R, and the multiple symbol errors cannot be corrected.

FIG. 1is a schematic block diagram illustrating a conventional RS decoding process. WhileFIG. 1depicts a decoding and look-up process to obtain the inverse S0−1followed by general multiplication and compare operations, it should be appreciated that conventional RS decoding may instead utilize division (e.g., S1/S0), which is associated with an even larger latency than multiplication by the inverse. However, even the conventional process depicted inFIG. 1that utilizes multiplication by the inverse to implement the division is associated with a significantly larger latency than a symbol error correction decoding process in accordance with example embodiments of the disclosure.

For example, assume that we assign latency values to inverse (INV), AND/OR, and XOR operations as follows: INV=0; AND/OR=1, XOR=2. Based on these latency values, the conventional RS decoding process depicted inFIG. 1would result in 26 latency levels. In particular, the process ofFIG. 1includes a decoding step whereby a decoder (DCD)102performs a 9-way AND which is equivalent to an INV and 3 levels of AND operations. This results in a latency value of 3. Then a constant look-up104is performed which includes a 256-way OR (8 levels of OR operations) to determine S0−1. This results in a latency value of 8. This is followed by a general multiplication operation106that includes an INV, an AND, and 5 levels of XOR operations producing a latency value of 0+1+2(5)=11. Finally, a compare operation108is performed which includes an AND and an 8-way OR operation. This is equivalent to an AND and 3 levels of OR operations resulting in a latency value of 1+3=4. Thus, the process depicted inFIG. 1yields a total latency of 3+8+11+4=26. It should be appreciated thatFIG. 1does not depict the general multiplication step that is performed in conventional RS decoding to determine whether the product of S0and S2equals S12. However, conventional RS decoders typically perform this step in parallel with the step to determine the inverse S0−1(or the step to perform the division of S0by S1whichever the case may be). Because determining the inverse S0−1(or performing the division of S0by S1) has a longer latency than the general multiplication step, it is the limiting step, and the general multiplication does not add to the total latency.

FIG. 2is a schematic block diagram illustrating a reduced latency error decoding process in accordance with one or more example embodiments of the disclosure.FIG. 4is a schematic block diagram of components configured to implement a reduced latency error decoding process in accordance with one or more example embodiments of the disclosure.FIG. 7is a process flow diagram of an illustrative reduced latency error decoding method700in accordance with one or more example embodiments of the disclosure.FIGS. 2, 4, and 7will be described in conjunction with one another hereinafter.

A reduced latency error decoding process in accordance with example embodiments of the disclosure may rest on the assumptions that an error correcting code is short and that minimizing latency is desirable. In particular, a reduced latency error decoding process in accordance with example embodiments of the disclosure provides ECC protection of a cache design through single-symbol correction/double-symbol detection (SSC/DSD). Moreover, as previously discussed, a reduced latency error decoding process in accordance with example embodiments of the disclosure replaces division with enumerated parallel multiplication and further replaces general multiplication with constant multiplications. In doing so, a reduction in logic and reduced latency over conventional decoding processes is achieved.

Referring first to block702of the method700, a reduced latency error decoding process in accordance with example embodiments of the disclosure may begin with receipt of a codeword R containing at least one data symbol and at least one check symbol. The codeword R may include, for example, 9-bit symbols defined over GF(512). As a non-limiting example, the received codeword R may contain 15 data symbols and 3 check symbols.

At block704of the method700, a polynomial R(x) may be generated that has as its coefficients the symbols of the received codeword R. For instance, in the example introduced above in which R has 15 data symbols and 3 check symbols (and thus 18 total symbols), the polynomial R(x)=[symbol 1]+[symbol 2]x+[symbol 3]x2+ . . . +[symbol 18]x17. Then, at block706of the method700, computer-executable instructions of a syndrome generator402(FIG. 4) may be executed to compute syndromes S0, S1, and S2for the polynomial R(x). As previously described, the syndromes S0, S1, and S2represent the values of the polynomial R(x) at the points 1, α, and α2, respectively.

More specifically, referring again to the example introduced earlier, the GF(512) code may be generated over GF(2) by a root of the primitive polynomial α9+α4+1. The code generator polynomial for this code may be G(x)=(x−1)(x−α)(x−α2). If we view the 15 data symbols as the coefficients of a polynomial D(x), then the three check symbols are the coefficients of the remainder after dividing x3D(x) by G(x). This may be performed in parallel by an XOR circuit that takes as input the 15 data symbols (9*15=135 bits) and produces 3 check symbols (9*3=27 bits) such that the encoder XOR circuit operates on 135 bits of data and produces 27 check bits. Further, as previously noted, when viewing the 18 symbols in this example as coefficients of the polynomial R(x), the syndromes S0, S1, and S2are computed by evaluating the polynomial R(x) at the points 1, α, and α2, respectively. This may be done in parallel by an XOR circuit which takes 18 received symbols and produces the 3 syndromes.

In particular, a syndrome generator circuit402depicted inFIG. 4may take 18*9=162 bits as input and produce 27 bits as output. In particular, assuming an even 9-bit symbol code, the 27 bits outputted by the syndrome generator circuit402may include the parts S0, S1, and S2, each of which is 9 bits in length. S0may be a 9-bit vector of the error that indicates which bit(s) in the correctable symbol need to be flipped. S1may be a 9-bit vector pointing to the symbol in error. More specifically, in the example introduced earlier, S1may be a special encode of which symbol in the 15+3=18 symbols is in error. S2may be a 9-bit vector to be used as a correctable error (CE)/uncorrectable error (UE) check. For example, if there exists a position p such that S1=S0αpand S2=S1αp, then the error is correctable.

In certain example embodiments, the S0term may be generated for the bit-flip vector to indicate which of the 9 bits in a corrected symbol needs to be corrected. S0can then be used against all the symbols to pre-correct all symbols (each of which may have a tentative correction). As will be described in more detail hereinafter, secondary tests of S0, S1, and S2and some constants can then be used to determine which (if any) of the symbols needs correction.

In particular, at block708of the method700, a decoder404(FIG. 4) may determine whether any of the syndromes S0, S1, or S2is non-zero. In response to a negative determination at block708, which indicates that all syndromes are zero, the method700may end because it can be determined that the received codeword R contains no errors. On the other hand, in response to a positive determination at block708, indicating that one or more of the syndromes S0, S1, and S2are non-zero, the method700may proceed to block710, where the decoder circuit404may perform an enumerated parallel multiplication of S0with each power of α ranging from 0 to [(# symbols in the codeword R)−1].

At block712of the method700, the decoder circuit404may compare the resulting products of the enumerated parallel multiplication performed at block710with S1to determine whether there exists a power p for which S1=S0αp. In response to a negative determination at block712, the method700may proceed to block722, where it may be determined that there are multiple uncorrectable symbol errors in the received codeword R. On the other hand, in response to a positive determination at block712, the method700may proceed to block714, where the decoder circuit404may perform an enumerated parallel multiplication of S1with each power of α ranging from 0 to [(# symbols in the codeword R)−1].

At block716of the method700, the decoder circuit404may compare the resulting products of the enumerated parallel multiplication performed at block714with S2to determine whether S2=S1αpfor the same power p for which S1=S0αp. In response to a negative determination at block716, the method700may proceed to block722, where it may be determined that there are multiple uncorrectable symbol errors in the received codeword R. On the other hand, in response to a positive determination at block716, the decoder circuit404may determine, at block718, that there is a single symbol at position p in the codeword R that has one or more bit errors based on the conditions at block712and block716both being met. Then, at block720of the method700, the bit error(s) in the single symbol at position p in the received codeword R are corrected by XORing S0with the symbol at position p.

In certain example embodiments of the disclosure, the enumerated parallel multiplication of S0with powers of a performed at block710and the enumerated parallel multiplication of S1with powers of a performed at block714as well as the checks at blocks712and716may be performed at least partially in parallel. For instance, in the example introduced earlier in which the codeword R contains 18 total symbols (15 data symbols and 3 check symbols), for each candidate error position p across the range of candidate error positions [0, 17], the check as to whether S1=S0αpand the check as to whether S2=S1αpmay be performed in parallel. If a position p is identified that passes both of these checks, then the determination at block718may be made, and the data of the symbol in the codeword R at position p may be XORed with S0to correct the single symbol error.

In particular, if there is only one symbol that is in error, then syndrome S0is the error value (e.g., the non-zero bits in S0indicate the bits that need to be flipped in the symbol in error in order to correct the symbol). The reduced latency error decoding process ofFIG. 7seeks to find the location of a single symbol in error within the received codeword R or determine that more than one symbol errors have occurred. If there is a single symbol error at position p in the codeword R, then the syndromes will satisfy the following equations: S1=S0Y and S2=S1Y, where Y=αpfor a particular p across the range of candidate p values (e.g., 0 to 17 in the example introduced earlier). Rather than computing Y by dividing S1by S0as conventional RS codes do (which as described earlier results in large latency), a test may be performed in parallel to determine if there is a position p from 0 to 17 such that S1=S0αpand S2=S1αp, using 17 pairs of constant multipliers. It should be appreciated that although there are 18 symbols in the codeword R in this example, only 17 pairs of constant multipliers may be needed because when p is 0, αp=1, and thus, S1can be directly compared to S0and S2can be directly compared to S1without requiring constant multiplications. As such, utilizing this approach without performing any decode term sharing (which will be described in more detail later) may require 34 such constant multipliers. If a position p is identified that satisfies both equations, p indicates the location of the symbol in error in the received codeword R. On the other hand, if no such position p satisfies both equations, more than one symbol error has occurred. Each constant multiplier may be an XOR circuit that takes 9 bits of input and produces 9 bits of output.

More specifically, as shown inFIG. 2, once the 9-bit S0term is generated at block706of the method700, S0can be multiplied202with a 9×9 constant matrix, for example, to obtain the 9-bit S0×Ap. S0×Apmay then be compared204with S1. In addition, although not depicted inFIG. 2, a further comparison of S1×Apto S2may also be performed. In this manner, which symbol (if any) needs correction may be determined. In particular, the constant matrix Apmay be applied to both S0and S1in a constant multiplication operation. Two product vectors of length 18*9 may be produced. These vectors may then be split into 18 successive 9-bit symbols corresponding to the 18 symbols in the codeword R for the example introduced earlier. The products of S0×Apmay be compared with S1and the products of S1×Apmay be compared with S2. The position of the error whose value is S0may be identified when both comparisons match for a given pair of product symbols. If there is no position where the products match, then multiple uncorrectable symbol errors are present in the received codeword R.

As previously noted, checking the dual conditions described above may require 34 constant multipliers. The number of constant multipliers needed, however, can be reduced in example embodiments of the disclosure using decode term sharing. In particular, position 0 (which corresponds to raising a to the zero power) is multiplication by 1, and thus, is free. For positions 1 to 8, instead of comparing S2with S1αp, S2can equivalently be compared with S0α2p. However, because the positions 2p for p ranging from 1 to 8 are merely the even positions when p ranges from 1 to 17, those products were already computed for the comparison involving S1. As such, while 17 constant multipliers (positions 1 to 17) may be used to compare with S1, only 9 constant multipliers are needed for computing S1αpfor p ranging from 9 to 17, giving a total of 17+9=26 constant multipliers to locate the position of the symbol in error. This decode term sharing approach can be used for any reduced latency RS code in accordance with example embodiments of the disclosure to reduce the size of the decoder logic by about 25% over conventional decoding processes assuming that approximately the same number of ones appear in each 9×9 constant matrix.

Stating the above more formally, for a code with length k, computation of S0αpand S1αpfor 0<p<k would require 2k−2 constant multipliers in the absence of decode term sharing. However, if decode term sharing in accordance with example embodiments of the disclosure is used, the check as to whether S1=S0αpfor 0<p<k may still be performed, but rather than performing the check as to whether S2=S1αpfor 0<p<k, the following check may instead be performed: S2=S0α2pfor 0<p<k. When 2p<k, the value of S0α2phas already been computed for the check as to whether S1=S0αpfor 0<p<k. As such, while S0αpis computed for 0<p<k, S0α2ponly needs to be computed for k≤2p<2k. This requires k−1+(k/2) constant multipliers, which corresponds to about a 25% reduction in the hardware decoder logic needed as compared to conventional decoding processes. In the example introduced earlier in which the codeword R has 18 total symbols, 18−1+(18/2)=26 constant multipliers are needed instead of 2(18)−2=34.

FIG. 3Ais a schematic diagram illustrating example decoder logic300for implementing a reduced latency error decoding process in accordance with one or more example embodiments of the disclosure.FIG. 3Bis an additional schematic diagram illustrating how the logic300ofFIG. 3Acan reuse constant terms through decode term sharing in accordance with one or more example embodiments of the disclosure. As can be seen inFIG. 3B, if S0 is free, S1-S8 can be covered by re-using terms for S2, S4, . . . , S16, which are calculated. This can result in a reduction of 25% of the major XOR logic in the decoder300, for example.

The logic300may include an 18 pack of eDRAMs contained in L3 double data word wrapper outputs, where each eDRAM in the wrapper outputs a 9-bit symbol. The symbol ECC may support correction of any number of corrupted bits within a single symbol and detection of any two simultaneously corrupted symbols. Two doublewords of data are stored in bits 0:127 followed by a 7-bit special uncorrectable error (SPUE) stamp and 3 checkbit symbols in bit positions 135:161. The 7-bit SPUE stamp may be used to record a detected (uncorrectable error) UE or SPUE on store data going into the eDRAMs.

As previously described, a reduced latency error decoding process in accordance with example embodiments of the disclosure may perform the decoding by searching for a position p such that both of the conditions S1=S0αpand S2=S0α2pare met. For the shortened code example introduced earlier in which the codeword R has a code length of 18 (e.g., 15 data symbols+3 check symbols) and p ranges from 0 to 17, decode term sharing results in removing 8 constant multipliers of the 34 that otherwise would be required because the calculation of S0αpfor even values of p correspond to products which can also be used in the S2comparison.

However, in certain example embodiments, even further logic reduction can be achieved by choosing non-standard code positions for the received codeword R. For instance, with respect to the example shortened RS codeword that includes 18 symbols, it is possible to further reduce the number of constant multipliers that are required from 26 to 18 by choosing a non-standard set of positions for the shortened code. To illustrate how choosing a non-standard set of positions can further reduce the number of required constant multipliers, consider a full-length RS code instead of a shortened one. For a full-length code defined over GF(512), for example, the comparison with respect to the syndrome S1involves computing S0αpfor all values of p ranging from 0 to 510, which correspond to all the non-zero elements in the finite field. However, the values of α2pfor p ranging from 0 to 510 are simply a permutation of the values of αp. Thus, once the initial products have been computed, no further products need to be computed as long as the elements are properly selected to take advantage of these properties for the shortened RS code.

Referring again to the example shortened RS code containing 18 symbols, instead of using positions 0 to 17, a set of positions may be chosen such that all doubles of positions in the set are also contained in the set. For example, assume that the following set of positions is chosen: {1, 2, 4, 8, 16, 32, 64, 128, 256}. This set contains all doubles of positions in the set. In particular, because the code is defined over GF(512), which has 511 non-zero elements, the chosen positions (which represent exponents of the element α) can be interpreted modulo 511. Thus, 2*256=512 is equivalent to 1 mod 511 and 1 can be interpreted as the double of 256 in modulo 511.

The above-described set of positions has length 9. However, the example shortened RS code containing 18 symbols requires 17 non-zero positions. Accordingly, another set of non-standard positions that contains all doubles of positions in the set must be chosen. Any starting point not contained in the first set may be selected. Because it is desirable to minimize the size of the constant multipliers that are used in addition to the number of constant multipliers that are used, the position 9 may be selected as a starting point for the second set, which yields the set {9, 18, 36, 72, 144, 288, 576=65 mod 511, 130, 260}. It should be appreciated that 2*260=520, which is equal to 9 mod 511, and thus, 9 can be interpreted as the double of 260. Accordingly, this second set of non-standard positions also contains all of its doubles.

It can be shown that since 512=29, a maximal doubling set modulo 511 has a length of 9. Thus, the following 18 positions can be chosen for the RS code: {0, 1, 2, 4, 8, 9, 16, 18, 32, 36, 64, 65, 72, 128, 130, 144, 256, 260}. The corresponding doubles modulo 511 then become: {0, 2, 4, 8, 16, 18, 32, 36, 64, 72, 128, 130, 144, 256, 260, 288, 1, 9}. The only power contained in the doubled set that is not contained in the original set is 288. Thus, the 17 non-zero positions can be selected from the original set along with position 288 from the doubled set to yield 18 constant multipliers. As such, only one additional constant multiplier is needed beyond the 17 non-zero positions in the original set. Accordingly, by selecting a set of non-standard positions that contains all doubles of elements in the set, an even further reduction in the number of constant multipliers from 26 to 18 can be achieved.

When considering the latency associated with a decoding process according to example embodiments of the disclosure, it be can be seen that the latency is significantly lower than with conventional decoding processes. In particular, assuming the same latency value assignments as mentioned earlier are applied, multiplication of S0with the constant matrix Apincludes 3 levels of XOR operations. This results in a latency value of 3(2)=6. The compare operation204includes both a pattern compare and a final compare. The pattern compare includes 1 XOR and a 9-way OR which is equivalent to 1 XOR and 3 OR operations. This results in a latency value of 2+3(1)=5. The final compare is a single AND operation resulting in a latency value of 1. Thus, the total latency associated with the decoding process ofFIGS. 2 and 7according to example embodiments of the disclosure is 6+5+1=12, which is significantly lower than the latency of 24 associated with the conventional decoding process depicted inFIG. 1. In other example embodiments of the disclosure, the compare operation may include an AND operation and an 8-way OR which is equivalent to an AND operation and 3 OR operations, producing a latency value of 4 rather than the 6 described above.

To further illustrate this significant reduction in latency achieved by example embodiments of the disclosure, consider the latency value of 22 associated the decoding step, the constant look-up104, and the general multiplication operation106ofFIG. 1. In a decoding process, according to example embodiments of the disclosure, these steps are replaced with the constant multiplication operation S0×Apwhich has a latency of 6 due to the 3 levels of XOR operations. For instance, assume that we have a constant 9×9 matrix with the following rows: 011000010; 001100001; 000110000; 100011000; 001001110; 000100111; 000010011; 100001001; and 110000100. These matrix rows are associated with the following XOR operations: row 1: 3+1=4-way; row 2: 3+1=4-way; row 3: 2+1=3-way; row 4: 3+1=4-way; row 5: 4+1=5-way; row 6: 4+1=5-way; row 7: 3+1=4-way; row 8: 3+1=4-way; row 9: 3+1=4-way. Thus, the multiplication area contains 28 XORs but only 3 levels of XOR (5-way XOR max). The 3 levels of XOR result in a latency of 3(2)=6.

As explained above, the use of constants for multiplication rather than strictly data/XORs results in reduced latency. In addition, multiplication of a syndrome by a constant followed by a compare operation in lieu of a divide circuit also yields a reduction in latency. If a match is detected from the compare, the divide circuit (if used) would have yielded that value. Less circuitry is needed for the constant multiplication and compare than would be required with a divide circuit. In addition, decode term sharing can further improve latency.

An example matrix for checkbit generation is shown below. Assuming eighteen 9-bit input symbols, the matrix for checkbit generation along with the corresponding bit positions may be given by the following table. The first column is the output (27 bits, 3 symbols×9 used for checkbits) which are numbered 0 to 26 vertically within the first column. In the Hmatrix, a zero (0) means that bit is NOT part of the calculation and a one (1) means the particular input is part of the calculation of that checkbit. By example, the first column (0) is for checkbit 0, which is generated by the XOR of Inputs 1, 4, 5, 10, 11, 12, 14, 15, 16, 19, 20, 21, 22, 23, 24, 25, 26, 30, 31, 32, 33, 35, 39, 41, 42, 43, 45, 46, 48, 49, 50, 52, 53, 56, 58, 60, 61, 63, 64, 66, 68, 71, 72, 73, 76, 78, 81, 82, 84, 85, 86, 88, 93, 98, 99, 100, 101, 104, 105, 106, 107, 108, 111, 112, 117, 122, 123, 125, 126, 133, and 134. Another way of viewing this is that input bit 0 (as shown in row 0) will be used to calculate checkbits 3, 4, 5, 8, 10, 11, 12, 13, 15, 16, 17, 18, 19, 20, 23, 24, and 25. Likewise, the other twenty-six outputs/checkbits can be generated from the inputs based on the table.

At times, it may be necessary to convert from one form of ECC to another. For instance, while example embodiments described herein may be low latency for a cache design, the latency may be too high for some bus transfers or faster cache levels, which may have, for example, Hamming codes for just single-bit correction/double-bit detection. Various techniques may be used to convert from one ECC code to another, while still protecting the data. One such approach is to generate parity on the data after it is corrected/processed by one code and before it is encoded into a second code. Another technique is ECC conversion as described hereinafter that achieves a lower latency by correcting one code while initiating generation of a second code in parallel. Referring again toFIG. 4, an ECC generator406is depicted that may perform checkbit generation on the raw data into a second ECC code (for instance a Hamming code) while, in parallel, correction vectors may be generated based on multiplying S0by another constant matrix. This constant matrix may be based on taking the 9-bit segments of the ECC matrix for the code being converted to (the 6472 code) that are equivalent to the 9-bit symbols distributed in the 9-bit symbol code. S0is multiplied against these segments of the matrix to generate, in parallel, those ECC bits that would need to be flipped for each 9-bit symbol that potentially could contain an error. Once the symbol to be corrected is identified, late selects may occur on both the data and the 6472 check bits to generate both corrected data and checkbits.

FIG. 5is a schematic block diagram illustrating an example error correction flow502in accordance with one or more example embodiments of the disclosure. The error correction flow502includes syndrome generation from a codeword, error decoding using the generated syndromes, and application of the correction to the data of the received codeword. Any new error correction code would then be generated off the corrected data. The “syn decode−>flip” block inFIG. 5may include the same functionality as the decoder404depicted inFIG. 4.FIG. 6is a schematic block diagram illustrating an example error correction flow602in accordance with one or more example embodiments of the disclosure. The example error correction flows502and602shown respectively inFIGS. 5 and 6may be implemented using the example decoder logic ofFIGS. 3 and 4, for example.

One or more operations of a reduced latency error decoding process in accordance with example embodiments of the disclosure may be performed, at least in part, by one or more of program modules configured to implement underlying hardware logic. These program modules may be implemented in any combination of hardware, software, and/or firmware. In certain example embodiments, one or more of these program modules may be implemented, at least in part, as software and/or firmware modules that include computer-executable instructions that when executed by a processing circuit cause one or more operations to be performed. A system or device described herein as being configured to implement example embodiments of the disclosure may include one or more processing circuits, each of which may include one or more processing units or nodes. Computer-executable instructions may include computer-executable program code that when executed by a processing unit may cause input data contained in or referenced by the computer-executable program code to be accessed and processed to yield output data.

One or more illustrative embodiments of the disclosure are described herein. Such embodiments are merely illustrative of the scope of this disclosure and are not intended to be limiting in any way. Accordingly, variations, modifications, and equivalents of embodiments disclosed herein are also within the scope of this disclosure.

FIG. 8is a schematic diagram of an illustrative networked architecture800configured to implement one or more example embodiments of the disclosure. The architecture may include one or more decoding servers802, one or more networks804, and one or more datastores, potentially accessible by the decoding server(s)802directly or over one or more of the network(s)804. While the decoding server(s)802may be described herein in the singular, it should be appreciated that multiple instances of the decoding server802may be provided, and functionality described in connection with the decoding server802may be distributed across such multiple instances.

In an illustrative configuration, the decoding server802may include one or more processors (processor(s))808, one or more memory devices810(generically referred to herein as memory810), one or more input/output (“I/O”) interface(s)812, one or more network interfaces814, and data storage816. The decoding server802may further include one or more buses818that functionally couple various components of the decoding server802.

In various implementations, the memory810may include multiple different types of memory such as various types of static random access memory (SRAM), various types of dynamic random access memory (DRAM), embedded DRAM (eDRAM), various types of unalterable ROM, and/or writeable variants of ROM such as electrically erasable programmable read-only memory (EEPROM), flash memory, and so forth. The memory810may include main memory as well as various forms of cache memory such as instruction cache(s), data cache(s), translation lookaside buffer(s) (TLBs), and so forth. Further, cache memory such as a data cache may be a multi-level cache organized as a hierarchy of one or more cache levels (L1, L2, etc.).

The data storage816may include removable storage and/or non-removable storage including, but not limited to, magnetic storage, optical disk storage, and/or tape storage. The data storage816may provide non-volatile storage of computer-executable instructions and other data. The memory810and the data storage816, removable and/or non-removable, are examples of computer-readable storage media (CRSM) as that term is used herein.

The data storage816may store computer-executable code, instructions, or the like that may be loadable into the memory810and executable by the processor(s)808to cause the processor(s)808to perform or initiate various operations. The data storage816may additionally store data that may be copied to memory810for use by the processor(s)808during the execution of the computer-executable instructions. Moreover, output data generated as a result of execution of the computer-executable instructions by the processor(s)808may be stored initially in memory810and may ultimately be copied to data storage816for non-volatile storage.

More specifically, the data storage816may store one or more operating systems (O/S)820; one or more database management systems (DBMS)822configured to access the memory810and/or one or more external data store(s)806; and one or more program modules, applications, engines, computer-executable code, scripts, or the like such as, for example, a syndrome generator824, a decoder826, and an ECC generator828. Any of the components depicted as being stored in data storage816may include any combination of software, firmware, and/or hardware. The software and/or firmware may include computer-executable instructions (e.g., computer-executable program code) that may be loaded into the memory810for execution by one or more of the processor(s)808to perform any of the operations described earlier in connection with correspondingly named components.

Although not depicted inFIG. 8, the data storage816may further store various types of data utilized by components of the decoding server802(e.g., input message data, pointer data, output data from the processing of input message blocks of an input message, padding signature data, message digest data, etc.). Any data stored in the data storage816may be loaded into the memory810for use by the processor(s)808in executing computer-executable instructions. In addition, any data stored in the data storage816may potentially be stored in the external data store(s)806and may be accessed via the DBMS822and loaded in the memory810for use by the processor(s)808in executing computer-executable instructions.

Referring now to other illustrative components depicted as being stored in the data storage816, the O/S820may be loaded from the data storage816into the memory810and may provide an interface between other application software executing on the decoding server802and hardware resources of the decoding server802. More specifically, the O/S820may include a set of computer-executable instructions for managing hardware resources of the decoding server802and for providing common services to other application programs. In certain example embodiments, the O/S820may include or otherwise control execution of one or more of the program modules depicted as being stored in the data storage816. The O/S820may include any operating system now known or which may be developed in the future including, but not limited to, any server operating system, any mainframe operating system, or any other proprietary or non-proprietary operating system.

The DBMS822may be loaded into the memory810and may support functionality for accessing, retrieving, storing, and/or manipulating data stored in the memory810, data stored in the data storage816, and/or data stored in the external data store(s)806. The DBMS822may use any of a variety of database models (e.g., relational model, object model, etc.) and may support any of a variety of query languages. The DBMS822may access data represented in one or more data schemas and stored in any suitable data repository. External data store(s)806that may be accessible by the decoding server802via the DBMS822may include, but are not limited to, databases (e.g., relational, object-oriented, etc.), file systems, flat files, distributed datastores in which data is stored on more than one node of a computer network, peer-to-peer network datastores, or the like.

Referring now to other illustrative components of the decoding server802, the input/output (I/O) interface(s)812may facilitate the receipt of input information by the decoding server802from one or more I/O devices as well as the output of information from the decoding server802to the one or more I/O devices. The I/O devices may include any of a variety of components such as a display or display screen having a touch surface or touchscreen; an audio output device for producing sound, such as a speaker; an audio capture device, such as a microphone; an image and/or video capture device, such as a camera; a haptic unit; and so forth. Any of these components may be integrated into the decoding server802or may be separate. The I/O devices may further include, for example, any number of peripheral devices such as data storage devices, printing devices, and so forth.

The decoding server802may further include one or more network interfaces814via which the decoding server802may communicate with any of a variety of other systems, platforms, networks, devices, and so forth. The network interface(s)814may enable communication, for example, with one or more other devices via one or more of the network(s)804. The network(s)804may include, but are not limited to, any one or more different types of communications networks such as, for example, cable networks, public networks (e.g., the Internet), private networks (e.g., frame-relay networks), wireless networks, cellular networks, telephone networks (e.g., a public switched telephone network), or any other suitable private or public packet-switched or circuit-switched networks. The network(s)804may have any suitable communication range associated therewith and may include, for example, global networks (e.g., the Internet), metropolitan area networks (MANs), wide area networks (WANs), local area networks (LANs), or personal area networks (PANs). In addition, such network(s) may include communication links and associated networking devices (e.g., link-layer switches, routers, etc.) for transmitting network traffic over any suitable type of medium including, but not limited to, coaxial cable, twisted-pair wire (e.g., twisted-pair copper wire), optical fiber, a hybrid fiber-coaxial (HFC) medium, a microwave medium, a radio frequency communication medium, a satellite communication medium, or any combination thereof.

It should be appreciated that the program modules depicted inFIG. 8as being stored in the data storage816are merely illustrative and not exhaustive and that processing described as being supported by any particular module may alternatively be distributed across multiple modules, engines, or the like, or performed by a different module, engine, or the like. In addition, various program module(s), script(s), plug-in(s), Application Programming Interface(s) (API(s)), or any other suitable computer-executable code hosted locally on the decoding server802and/or hosted on other computing device(s) accessible via one or more networks, may be provided to support functionality provided by the modules depicted inFIG. 8and/or additional or alternate functionality. Further, functionality may be modularized in any suitable manner such that processing described as being performed by a particular module may be performed by a collection of any number of program modules, or functionality described as being supported by any particular module may be supported, at least in part, by another module. In addition, program modules that support the functionality described herein may be executable across any number of servers802in accordance with any suitable computing model such as, for example, a client-server model, a peer-to-peer model, and so forth. In addition, any of the functionality described as being supported by any of the modules depicted inFIG. 8may be implemented, at least partially, in hardware and/or firmware across any number of devices.

A decoding process in accordance with example embodiments of the disclosure may be performed by a decoding server802having the illustrative configuration depicted inFIG. 8, or more specifically, by hardware logic, hardware devices, program modules, engines, applications, or the like executable on such a device. It should be appreciated, however, that such operations may be implemented in connection with numerous other device configurations.

Any operations described herein may be carried out or performed in any suitable order as desired in various example embodiments of the disclosure. Additionally, in certain example embodiments, at least a portion of the operations may be carried out in parallel. Furthermore, in certain example embodiments, less, more, or different operations than those described may be performed.

Although specific embodiments of the disclosure have been described, one of ordinary skill in the art will recognize that numerous other modifications and alternative embodiments are within the scope of the disclosure. For example, any of the functionality and/or processing capabilities described with respect to a particular system, system component, device, or device component may be performed by any other system, device, or component. Further, while various illustrative implementations and architectures have been described in accordance with embodiments of the disclosure, one of ordinary skill in the art will appreciate that numerous other modifications to the illustrative implementations and architectures described herein are also within the scope of this disclosure. In addition, it should be appreciated that any operation, element, component, data, or the like described herein as being based on another operation, element, component, data, or the like may be additionally based on one or more other operations, elements, components, data, or the like. Accordingly, the phrase “based on,” or variants thereof, should be interpreted as “based at least in part on.”