LOW-POWER BLOCK CODE FORWARD ERROR CORRECTION DECODER

Abstract

A system comprises a forward error correction decoder comprising syndrome computation circuitry, key-equation solver circuitry, and search and evaluator circuitry. The syndrome computation circuitry may comprise a plurality of syndrome compute units connected in parallel. The syndrome computation circuitry may be dynamically configurable to vary a quantity of the syndrome compute units used for processing of a codeword based on conditions of a channel over which the codeword was received. The syndrome computation circuitry may be operable to use a first quantity of the syndrome compute units for processing of a first codeword received over the channel when the channel is characterized by a first bit error rate and a second quantity of the syndrome compute units for processing of a second codeword received over the channel when the channel is characterized by a second bit error rate.

Claims

1. A system comprising: a forward error correction decoder comprising syndrome computation circuitry, key-equation solver circuitry, and search and evaluator circuitry, wherein: the syndrome computation circuitry comprises a plurality of syndrome compute units connected in parallel; and the syndrome computation circuitry is dynamically configurable to vary a quantity of the syndrome compute units used for processing of a codeword based on conditions of a channel over which the codeword was received.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0005] FIG. 1A shows an example structure of a forward error correction (FEC) codeword which a low-power FEC decoder in accordance with an example implementation of this disclosure is operable to decode.

[0006] FIG. 1B shows the architecture of a low-power FEC decoder in accordance with an example implementation of this disclosure.

[0007] FIG. 2 shows an example implementation of the syndrome computation circuitry of FIG. 1B.

[0008] FIG. 3A shows an example implementation of key-equation solver circuitry of FIG. 1B.

[0009] FIG. 3B shows a zoomed-in view of one of the processing elements of the key-equation solver of FIG. 3A.

[0010] FIG. 3C shows an example implementation of the processing elements of the key-equation solver of FIG. 3A.

[0011] FIG. 4A shows an example implementation of the Chien search and error evaluator circuitry of FIG. 1B.

[0012] FIG. 4B shows an example implementation of the polynomial evaluation circuitry of FIG. 4A.

[0013] FIG. 5 illustrates that the number of syndromes needed to achieve a target block error rate (BLER) decreases when the bit error rate (BER) on the coded bits decreases.

[0014] FIG. 6 is a flowchart showing an example process for adapting a low-power FEC decoder in accordance with an example implementation of this disclosure.

DETAILED DESCRIPTION OF THE INVENTION

[0015] FIG. 1A shows an example structure of a forward error correction (FEC) codeword which a low-power FEC decoder in accordance with an example implementation of this disclosure is operable to decode. Each codeword comprises N (an integer) symbols, C.sub.0-C.sub.N-1, each of which has q (an integer) bits. K of the symbols are message symbols and N-K (N minus K) of the symbols are parity symbols. The shown codeword structure supports correction of up to t=(N31 K)/2 symbols. Example block codes include Reed-Solomon codes, BCH codes, Reed-Muller codes, etc.

[0016] FIG. 1B shows the architecture of a low-power FEC decoder 150 in accordance with an example implementation of this disclosure. The received codewords 151 are fed into two parallel paths 151a and 151b, each of the 151a and 151b being Pq (P times q) bits wide (P an integer). The first path comprises syndrome computation circuitry 152, key-equation solver circuitry 154, and Chien Search and Error Evaluator circuitry 156. The second path comprises a buffer 158 that introduces a delay equal to the delay of the first path. The outputs of the two paths are then combined in combiner 160 to result in an error corrected signal 161.

[0017] The control circuitry 162 is operable to manage operations of the other circuits of the FEC decoder 150 as described below in this disclosure. The control circuitry 162 may, for example, comprise logic that operates according to software and/or firmware loaded into memory of the control circuitry 162.

[0018] An example implementation of the syndrome computation circuit 152 is described below with reference to FIG. 2. An example implementation of the key-equation solver circuitry 154 is described below with reference to FIGS. 3A-3C. An example implementation of the Chien search and error evaluator 156 is described below with reference to FIGS. 4A and 4B. The buffer 158 may comprise any suitable volatile and/or nonvolatile memory elements.

[0019] FIG. 2 shows an example implementation of the syndrome computation circuitry of FIG. 1B. The example syndrome computation circuitry 152 comprises control circuitry 162, switches 204.sub.0204.sub.2t1,and a plurality of syndrome compute units 206.sub.0-206.sub.2t1.

[0020] The control circuitry 162 may be operable to detect channel conditions present on a channel over which the codewords are received, and control the switches based on the detected channel conditions, as further described below. The control circuitry 162 in FIG. 1B is also operable to measure a block error rate at the output of the Syndrome Computation 152, based on which a bit error rate of the coded bits input to the low-power FEC decoder 150 is calculated. Control information is exchanged between the control circuitry 162 and the circuits 152, 154, and 156 via signals 155, 157, and 159.

[0021] The switches 204.sub.0-204.sub.2t1 may comprise transmission gates or any other suitable circuit operable to connect and disconnect (or enable and disable) a downstream one or more of circuits 206.sub.0-206.sub.2t1 from the signal path 151a.

[0022] Each of the syndrome compute units 206.sub.T (T between 0 and 2t-1) comprises P processing chains, each comprising an adder 210, a first multiplier 212, a memory element 214, and a second multiplier 216. The outputs of the processing chains are then summed in adder 218 to generate syndromes S.sub.T according to equation 1 below.

[0023] The syndrome computation circuitry 152 is operable to calculate 2t syndromes S.sub.0-S.sub.2t1 for each codeword, according to the following equation 1:

[00001]$\left[\begin{array}{c}{s}_0\\ s_1\\ .Math.\\ s_{2t-1}\end{array}\right]=\left[\begin{array}{cccc}{}_0^{N-1}& {}_0^{N-2}& .Math.& 1\\ {}_1^{N-1}& {}_1^{N-2}& .Math.& 1\\ .Math.& .Math.& & .Math.\\ {}_{2t-1}^{N-1}& {}_{2t-1}^{N-2}& .Math.& 1\end{array}\right]\left[\begin{array}{c}{C}_{N-1}\\ C_{N-2}\\ .Math.\\ C_0\end{array}\right]$

[0024] where .sub.0=.sup.w,.sub.1=.sup.w+1, . . . .sub.2t1=.sup.w+2t1 are the powers of a primitive root , and w is a given integer. If all syndromes are 0, then the codeword is error free, otherwise the codeword has one or more error symbols. The value of t is typically determined at the encoder based on the worst-case channel conditions for which the FEC decoder 150 is expected to reliably decode codewords. Thus, in a conventional FEC decoder, a fixed number of 2t syndromes are computed. Power consumption, however, increases with increasing values of t. Thus, when channel conditions are better than the worst-case and the FEC decoder is able to reliably decode codewords with a smaller number of syndromes, computing 2t syndromes burns unnecessary power. It is therefore desirable from a power consumption perspective to compute the minimum number of syndromes necessary for the current channel conditions. Because the syndrome computation is independent for each syndrome (that is, each of circuits 206.sub.0-206.sub.2t1 can independently compute its respective one of the syndromes), the FEC decoder 150 may use only a subset of circuits 206.sub.0-206.sub.2t-1 to compute syndromes for any given codeword. That is, for a codeword received over channel conditions which only require computation of 2m syndromes (where m is an integer less than or equal to t), control circuitry 162 may open switches 204.sub.2m-204.sub.2t1 to disconnect or disable the unneeded circuits 206.sub.2m-206.sub.2t1 such that circuits 206.sub.2m-206.sub.2t1 do not compute syndromes for that codewordand thus burn less power.

[0025] FIG. 3A shows an overview of key-equation solver circuitry of FIG. 1B. In the example implementation shown, the key-equation solver circuitry 154 is implemented as a systolic array of processing elements 310 (of which only one is called out in FIG. 3A) arranged in 2t rows and 3t+1 columns. The data in the systolic array flows row by row from the bottom to the top. At row r (r between 0 and 2t1), 3t+1 elements of .sub.i(r+1) and .sub.1(r+1) are generated from .sub.i(r), .sub.0(r) at the previous row, where i between 0 and 3t is the column index of the array from the left to the right. As a result, at the last row, the systolic array finds out the error locator polynomial (x)=.sub.tx.sup.t+.sub.t1x.sup.t1+ . . . +.sub.0 and the error evaluator polynomial (x)=.sub.t1x.sup.t1+.sub.t2x.sup.t2+ . . . +.sub.0 by having .sub.i=.sub.i+t(2r) for i between 0 and t and .sub.i=.sub.i(2r)for i between 0 and t1. The error locator polynomial is used to find the locations of error symbols, and the error evaluator polynomial is used to calculate the value of the error symbol. In an example implementation, the processing elements in the systolic array may be implemented on hardware that is time-shared, thus reducing the amount of hardware needed to realize the key-equation solver circuitry 154. In addition to the processing elements 310, the key-equation solver circuitry 154 comprises data routing circuitry 302 and 304, and row and column enable/disable circuitry 306.

[0026] Which portion of the processing elements 310 in the array are enabled for any particular codeword is controlled by control circuitry 162 via row and column enable/disable circuitry 306. For a codeword received over a channel requiring computation of m syndromes, 2m rows and 3m+1 columns of the key-equation solver are enabled to generate an error locator polynomial (x) of degree m, and an error evaluator polynomial (x) of degree m-1. Thus, where m is less than t, one or more processing elements 310 remain in an inactive or low power state and power consumption of the key-equation solver circuitry 154 is reduced as compared to calculating an error locator polynomial of degree t and an error evaluator polynomial of degree t-1.

[0027] The data routing circuitry 304 is operable to route syndromes S.sub.0-S.sub.2m1 from bus 153 to inputs of processing elements 310 in columns 0 through 2m-1 of the array, so that .sub.i(0)=.sub.i(0) S.sub.i for i between 0 and 2t-1.

[0028] The data routing circuitry 302 is operable to route: (1) signal (x) from columns 0 through m-1 of row 2m; and (2) (x) from columns m through 2m of the row 2m to the Chien search and evaluator circuitry 156.

[0029] FIG. 3B shows a zoomed-in view of one of the processing elements of the key-equation solver of FIG. 3A with the input and output signals detailed.

[0030] FIG. 3C shows an example implementation of the processing elements of the key-equation solver of FIG. 3A.

[0031] FIG. 4A shows an example implementation of the Chien search and error evaluator circuitry of FIG. 1B. The Chien search circuitry 450 evaluates the error locator polynomial (x) at x=.sup.i for i between N-1 and 0. If (.sup.i)=0, C.sub.i is a symbol with error. The error value is given by x.sup.2t(x)/x/(x) for x=.sup.i, which is calculated by the error evaluator circuitry 470. Each polynomial evaluation circuit 452 (of which only 2 are called out in the figure) processes a symbol of q bits each time. To detect and correct Pq bits each time in the low-power FEC decoder, P data paths are instantiated in each of the Chien search circuitry 450 and the error evaluator circuitry 470.

[0032] Now referring to FIG. 4B, each polynomial evaluation circuit 452 comprises processing units 402.sub.1-402.sub.t, switches 404.sub.1-404.sub.t, and adders 406.sub.1-406.sub.t.

[0033] Each of the processing units 402.sub.1-402.sub.t comprises multipliers 410 and 412, multiplexer 414, and memory element 416 for generating a signal 417 which is output to a respective one of switches 404.sub.1-404.sub.t.

[0034] The switches 404.sub.1-404.sub.t are operable to switch the input of a respective one of the adders 406.sub.1-406.sub.t between the output of a corresponding one of circuits 402.sub.1-402.sub.t and a digital 0 value. When a digital 0 is bypassed, it is equivalent that the corresponding term .sub.tx.sup.t is removed from the polynomial (x).

[0035] The equation for calculating (x) can be written as .sub.tx.sup.t+.sub.t1x.sup.t1 + . . . .sub.1x +.sub.0. Thus, computation for each degree term is independent and a polynomial evaluator architecture such as shown in FIG. 4B can be used. Where m (the number of syndromes) is less than t, the control circuitry 162 may disconnect or disable circuits 402.sub.m+1-402.sub.t via switches 404.sub.m+1-404.sub.t, resulting in reduced power consumption (the circuits 402.sub.m+1-402.sub.t may be placed in a low-power state to further reduce power consumption). Given that the similar polynomial evaluator architecture shown in FIG. 4B can be used in each data path of polynomial evaluation for error evaluator circuitry 470, where m (the number of syndromes) is less than t, the control circuitry 162 may disconnect or disable the similar circuits 402.sub.m+1-402.sub.t in error evaluator circuitry for reduced power consumption.

[0036] FIG. 5 shows the relationship between the block error rate (BLER) of the codeword after the FEC decoding and the bit error rate (BER) of the coded bits input to the decoder when different number of syndromes 2m are computed for decoding, for an example Reed-Solomon code with N=544, K=514 and q=10. From the figure, it can be seen that when the BER of coded bits decreases, fewer syndromes need to be computed in the FEC decoder to achieve a same target block error rate (BLER). For example, the worst-case channel in this experiment has a coded BER of 7.5e5 and t=15 has been designed at the encoder to achieve the target BLER. When the input BER is better than the worst-case for which the FEC is designed, however, m can be set to a value less than 15 to save power and still achieve the desired BLER (e.g., m=10 for BER1e-5, m =7 for BER1e-6, and m=5 for BER1e-7).

[0037] FIG. 6 is a flowchart showing an example process for adapting a low-power FEC decoder in accordance with an example implementation of this disclosure. The process begins with block 601. If the BER of the input coded bits is not available from the system outside the FEC decoder, it is estimated in blocks 602 and 604. If the BER is available from outside the FEC decoder, then the process advances to block 606.

[0038] In block 602, the block error rate (BLER) of the codeword prior to the error correction is monitored at the output of the syndrome computation circuitry 152. A codeword is error free if and only if all the syndromes are zero. This may comprise, for example, measuring the BLER over multiple codewords and then taking an average of the measured BLER values.

[0039] In block 604, the BER of the input coded bits is calculated (e.g., by control circuitry 162) from the block error rate determined in block 602, based upon the FEC parameters, e.g. N and q.

[0040] In block 606, with the BER of the input coded bits provided by the system outside FEC decoder or estimated inside FEC decoder, the value of m required to meet the target BLER is calculated. For example, the control circuitry 162 may calculate the value of m using a lookup table holding the data similar to that plotted in FIG. 5.

[0041] In block 608, the FEC decoder 150 is configured based on the value of m calculated in block 606. For example, the control circuitry 162 may: open one or more of the switches 204.sub.0-204.sub.2t1 to disconnect or disable one or more of the compute units 206.sub.0-206.sub.2t1 from the path 151a, close one or more of the switches 204.sub.0-204.sub.2rt1 connect or enable one or more of the compute units 206.sub.0-206.sub.2t1 to the path 151a; disable, via circuit 306, one or more rows and columns of processing elements 310 in the key-equation solver circuitry 154; enable, via circuit 306, one or more rows and columns of processing elements 310 in the key-equation solver circuitry 154; configure one or more of the switches 404.sub.1-404.sub.t to connect or enable a respective one or more of the adder 406.sub.1-406.sub.t to an output of a respective one or more of the circuits 402.sub.1-402.sub.t; and/or configure one or more of the switches 404.sub.1-404.sub.t to connect a respective one or more of the adder 406.sub.1-406.sub.t to digital 0 value and disconnect or disable a respective one or more of the processing units 402.sub.1-402.sub.t.

[0042] In accordance with an example implementation of this disclosure, a system comprises a forward error correction decoder (e.g., 150) comprising syndrome computation circuitry (e.g., 152), key-equation solver circuitry (e.g., 154), and search and evaluator circuitry (e.g., 156). The syndrome computation circuitry may comprise a plurality of syndrome compute units (e.g., 206.sub.0-206.sub.2t1) connected in parallel. The syndrome computation circuitry may be dynamically configurable to vary a quantity of the syndrome compute units used for processing of a codeword based on conditions of a channel over which the codeword was received. Each of the syndrome compute units may comprise a plurality of adders (e.g., 210 and 218), a plurality of multipliers (e.g., 212 and 216), and a plurality of memory elements (e.g., 214). The syndrome computation circuitry may be operable to use a first quantity of the syndrome compute units (e.g., 2t) for processing of a first codeword received over the channel when the channel is characterized by a first bit error rate and a second quantity of the syndrome compute units (e.g., 2m) for processing of a second codeword received over the channel when the channel is characterized by a second bit error rate, where the first quantity of syndrome compute units is greater than the second quantity of syndrome compute units and the first bit error rate is greater than the second bit error rate. The key-equation solver circuitry may comprise an array of processing elements (e.g., 310). The key-equation solver circuitry may be dynamically configurable to vary a quantity of the processing elements of the key-equation solver circuitry used for processing of a codeword based on conditions of a channel over which the codeword was received. Each of the processing elements of the key-equation solver circuitry may comprise a plurality of multipliers (e.g., 354 and 356), one or more adder (e.g., 352), a plurality of memory elements (e.g., 350 and 358), and one or more multiplexers (e.g., 360). The key-equation solver circuitry may be operable to use a first quantity (e.g., 2t*(3t+1)) of the processing elements for processing of a first codeword received over the channel when the channel is characterized by a first bit error rate and a second quantity (e.g., 2m*(3m+1)) of the processing elements for processing of a second codeword received over the channel when the channel is characterized by a second bit error rate, the first quantity of the processing elements of the key-equation solver circuitry may be greater than the second quantity of the processing elements of the key-equation solver circuitry, and the first bit error rate may be greater than the second bit error rate. The search and evaluator circuitry may comprise a plurality of processing units (e.g., 402) connected in parallel. The search and evaluator circuitry may be dynamically configurable to vary a quantity of the processing units of the search and evaluator circuitry used for processing of a codeword based on conditions of a channel over which the codeword was received. Each of the processing units of the search and evaluator circuitry may comprise a plurality of multipliers (e.g., 410 and 412), one or more multiplexer (e.g., 414), and one or more memory element (e.g., 416). The search and evaluator circuitry is operable to use a first quantity (e.g., t) of the processing units for processing of a first codeword received over the channel when the channel is characterized by a first bit error rate and a second quantity of the processing units (e.g., m) for processing of a second codeword received over the channel when the channel is characterized by a second bit error rate, the first quantity of the processing units of the search and evaluator circuitry is greater than the second quantity of the processing units of the search and evaluator circuitry, and the first bit error rate is greater than the second bit error rate.

[0043] As utilized herein the terms circuits and circuitry refer to physical electronic components (i.e. hardware) and any software and/or firmware (code) which may configure the hardware, be executed by the hardware, and or otherwise be associated with the hardware. As used herein, for example, a particular processor and memory may comprise a first circuit when executing a first one or more lines of code and may comprise a second circuit when executing a second one or more lines of code. As utilized herein, and/or means any one or more of the items in the list joined by and/or. As an example, x and/or y means any element of the three-element set {(x), (y), (x, y)}. As another example, x, y, and/or z means any element of the seven-element set {(x), (y), (z), (x, y), (x, z), (y, z), (x, y, z)}. As utilized herein, the term exemplary means serving as a non-limiting example, instance, or illustration. As utilized herein, the terms e.g., and for example set off lists of one or more non-limiting examples, instances, or illustrations. As utilized herein, circuitry is operable to perform a function whenever the circuitry comprises the necessary hardware and code (if any is necessary) to perform the function, regardless of whether performance of the function is disabled, or not enabled, by some user-configurable setting.

[0044] Other embodiments of the invention may provide a non-transitory computer readable medium and/or storage medium, and/or a non-transitory machine readable medium and/or storage medium, having stored thereon, a machine code and/or a computer program having at least one code section executable by a machine and/or a computer, thereby causing the machine and/or computer to perform the methods described herein.

[0045] Accordingly, the present invention may be realized in hardware, software, or a combination of hardware and software. The present invention may be realized in a centralized fashion in at least one computing system, or in a distributed fashion where different elements are spread across several interconnected computing systems. Any kind of computing system or other apparatus adapted for carrying out the methods described herein is suited. A typical combination of hardware and software may be a general-purpose computing system with a program or other code that, when being loaded and executed, controls the computing system such that it carries out the methods described herein. Another typical implementation may comprise an application specific integrated circuit or chip.

[0046] The present invention may also be embedded in a computer program product, which comprises all the features enabling the implementation of the methods described herein, and which when loaded in a computer system is able to carry out these methods. Computer program in the present context means any expression, in any language, code or notation, of a set of instructions intended to cause a system having an information processing capability to perform a particular function either directly or after either or both of the following: a) conversion to another language, code or notation; b) reproduction in a different material form.

[0047] While the present invention has been described with reference to certain embodiments, it will be understood by those skilled in the art that various changes may be made and equivalents may be substituted without departing from the scope of the present invention. In addition, many modifications may be made to adapt a particular situation or material to the teachings of the present invention without departing from its scope. Therefore, it is intended that the present invention not be limited to the particular embodiment disclosed, but that the present invention will include all embodiments falling within the scope of the appended claims.