Message-passing decoder with fast convergence and reduced storage

Abstract

A message-passing decoder operates by storing, at a check node, a minimum value, a next-to-minimum value, an edge location of the minimum value, and information regarding the signs of incoming messages. For an edge which is not the location of a previous minimum value, the minimum value and the next-to-minimum value, and the location of the minimum value, are set based on the magnitude of an incoming message. For an edge which is the location of the previous minimum value, the minimum value and the next-to-minimum value are set based on the magnitude of an incoming message, and when the magnitude of the incoming message is at most equal to the previous next-to-minimum value, the location of the minimum value is set to the respective edge, and when the magnitude of the incoming message is greater than the previous next-to-minimum value, the location of the minimum value is approximated.

Claims

1. A method of operating a decoder on data received in a communication channel of a storage device, the method comprising: receiving incoming messages on edges of a node of the decoder; deriving a value for each incoming message, the value based on one or more of a magnitude, a sign and an edge location of the incoming message, the value for one of the messages being a minimum value from among the magnitudes, the deriving including approximating the edge location of the one of the messages having the minimum value; and selecting, for storage at the node, at least the minimum value, and the edge location of the one of the messages having the minimum value.

2. The method of claim 1 further comprising, for storage at the node, at least a next-to-minimum value from among the magnitudes; wherein: the approximating the edge location of the one of the messages having the minimum value is performed only when a current edge is the edge location of one of the messages having a previous minimum value, and magnitude of a message on the current edge is greater than a previous next-to-minimum value.

3. The method of claim 1 wherein approximating the edge location of the one of the messages having the minimum value comprises setting the edge location of the one of the messages having the minimum value to a position adjacent a previous location of one of the messages having the minimum value.

4. The method of claim 3 wherein approximating the edge location of the one of the messages having the minimum value comprises setting the edge location of the one of the messages having the minimum value to a position displaced one position anticyclically from the previous location of the one of the messages having the minimum value.

5. The method of claim 1, further comprising: for a respective edge, sending a return message; wherein: the return message has a sign determined from the result of an exclusive-OR operation on all incoming signs up to the present time and from the incoming sign on the respective edge; and the return message has a magnitude selected from stored magnitudes of incoming messages based on previous location of a message having a minimum value relative to the respective edge.

6. The method of claim 1 further comprising: performing an exclusive-OR operation on all incoming signs up to a present time; and storing all current incoming signs.

7. A decoder in a communication channel, the decoder comprising: a plurality of nodes; decoding circuitry that receives incoming messages at respective edges of a respective node, and derives values from among magnitudes, signs and edge locations of the incoming messages at the respective node, the value for one of the messages at the respective node being a minimum value, the decoding circuitry approximating the edge location of the one of the messages having the minimum value; and memory at each respective node for storing the values derived by the decoding circuitry; wherein: the decoding circuitry selects, for storage in the memory at each respective node, at least the minimum value from among messages at the respective node, and the edge location of the one of the messages having the minimum value.

8. The decoder of claim 7, wherein the decoder is a message-passing decoder.

9. The decoder of claim 7 wherein: the decoding circuitry further selects, for storage at the respective node, at least a next-to-minimum value from among the magnitudes; and the decoding circuitry approximates the edge location of the one of the messages having the minimum value only when a current edge is the edge location of one of the messages having a previous minimum value, and magnitude of a message on the current edge is greater than a previous next-to-minimum value.

10. The decoder of claim 7 wherein the decoding circuitry approximates the edge location of the one of the messages having the minimum value by setting the edge location of the one of the messages having the minimum value to a position adjacent a previous location of the one of the messages having the minimum value.

11. The decoder of claim 10, wherein the decoding circuitry approximates the edge location of the one of the messages having the minimum value by setting the edge location of the one of the messages having the minimum value to a position displaced one position anticyclically from the previous location of the one of the messages having the minimum value.

12. The decoder of claim 7 wherein: for a respective edge, the decoding circuitry sends a return message; the return message has a sign determined from the result of an exclusive-OR operation on all incoming signs up to the present time and from the incoming sign on the respective edge; and the return message has a magnitude selected from stored magnitudes of incoming messages based on previous location of a message having a minimum value relative to the respective edge.

13. The decoder of claim 7, wherein: the decoding circuitry derives information from the signs of incoming messages by performing an exclusive-OR operation on all incoming signs up to a present time; and the decoding circuitry stores, in the memory, a result of the exclusive-OR operation on all incoming signs up to the present time, and also stores, in the memory, all current incoming signs.

14. The decoder of claim 7, wherein the decoding circuitry operates on messages comprising log-likelihood ratios.

15. A communication channel comprising: a demodulator that receives digital data and outputs signals indicating whether each particular bit of the digital data is a 0 or a 1; and a decoder that operates on the signals to decode the digital data, the decoder comprising: a plurality of nodes; decoding circuitry that receives incoming messages at respective edges of a respective node, and derives values from among magnitudes, signs and edge locations of the incoming messages at the respective node, the value for one of the messages at the respective node being a minimum value, the decoding circuitry approximating the edge location of the one of the messages having the minimum value; and memory at each respective node for storing the values derived by the decoding circuitry; wherein: the decoding circuitry selects, for storage in the memory at each respective node, at least the minimum value from among messages at the respective node, and the edge location of the one of the messages having the minimum value.

16. The communication channel of claim 15, wherein the decoder is a message-passing decoder.

17. The communication channel of claim 16, wherein: the decoding circuitry further selects, for storage at the respective node, at least a next-to-minimum value from among the magnitudes; and the decoding circuitry approximates the edge location of the one of the messages having the minimum value only when a current edge is the edge location of one of the messages having a previous minimum value, and magnitude of a message on the current edge is greater than a previous next-to-minimum value.

18. The communication channel of claim 15 wherein the decoding circuitry approximates the edge location of the one of the messages having the minimum value by setting the edge location of the one of the messages having the minimum value to a position adjacent a previous location of the one of the messages having the minimum value.

19. The communication channel of claim 18 wherein the decoding circuitry approximates the edge location of the one of the messages having the minimum value by setting the edge location of the one of the messages having the minimum value to a position displaced one position anticyclically from the previous location of the one of the messages having the minimum value.

20. The communication channel of claim 15 wherein: for a respective edge, the decoding circuitry sends a return message; the return message has a sign determined from the result of an exclusive-OR operation on all incoming signs up to the present time and from the incoming sign on the respective edge; and the return message has a magnitude selected from stored magnitudes of incoming messages based on previous location of a message having a minimum value relative to the respective edge.

21. The communication channel of claim 15, wherein: the decoding circuitry derives information from the signs of incoming messages by performing an exclusive-OR operation on all incoming signs up to a present time; and the decoding circuitry stores, in the memory, a result of the exclusive-OR operation on all incoming signs up to the present time, and also stores, in the memory, all current incoming signs.

22. The communication channel of claim 15, wherein the signals are log-likelihood ratios.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) Further features of the disclosure, its nature and various advantages, will be apparent upon consideration of the following detailed description, taken in conjunction with the accompanying drawings, in which like reference characters refer to like parts throughout, and in which:

(2) FIG. 1 is a schematic representation of a transceiver channel with which the subject matter of this disclosure can be used;

(3) FIG. 2 is a schematic representation of a storage device with which the subject matter of this disclosure can be used;

(4) FIG. 3 is a graphic representation of a linear code with which the subject matter of this disclosure can be used;

(5) FIGS. 4 and 5 are graphic representations of the operation of a message-passing decoder with which the subject matter of this disclosure can be used;

(6) FIGS. 6-8 are graphic representations of the operation of a storage-intensive implementation of a message-passing decoder at a single check node;

(7) FIG. 9 is a pseudocode representation of a technique according to an implementation of the subject matter of this disclosure for operating a message-passing decoder; and

(8) FIGS. 10-12 are graphic representations of examples of the operation of implementations of a message-passing decoder according to an implementation of the subject matter of this disclosure for operating a message-passing decoder.

DETAILED DESCRIPTION

(9) A message-passing decoder according to implementations of the subject matter of this disclosure uses less memory than conventional message-passing decoder while converging faster than previously-known reduced storage message-passing decoders.

(10) A message-passing decoder 112 may be used in the receiver portion 102 of a transceiver channel 100 as shown in FIG. 1. Transceiver channel 100 includes transmit portion 101 and receive portion 102, connected by transmission channel 103. Transmit portion 101 includes an encoder 111 which operates on user data 104 which may be created by other circuitry (not shown), or produced by a user using a transducer (e.g., a microphone or keyboard), to create encoded data 114. Encoded data 114 is modulated by modulator 115 and transmitted across channel 103 to receive portion 102, where it is demodulated by demodulator 122 before being decoded by message-passing decoder 112.

(11) Similarly, in the case of a storage device 200 as shown in FIG. 2, user data 104 can be read from a storage medium 201 by a read head 202, then passed through an analog front end 203 and an analog-to-digital converter 204 to a detector, such as Viterbi detector 205, before being input to message-passing decoder 112 for decoding.

(12) The output of demodulator 122 or Viterbi detector 205 is in the form of log-likelihood ratios. An LLR L.sub.k is the opinion of demodulator 122 or detector 205, based on the received signal, as to whether the kth bit of encoded data in the received signal is a 0 or a 1. A positive LLR means that demodulator thinks that the bit is more likely to be a 0, while a negative LLR means that demodulator thinks that the bit is more likely to be a 1. The magnitude of the LLR is directly proportional to the confidence of the demodulator/detector.

(13) A linear code, such as an LDPC code, can be represented by a graph such as graph 300 of FIG. 3. In graph 300, circles 301 represent variable nodes, corresponding to encoded data. Squares 302 represent check nodes, which show the check constraints that are imposed on the data by the code. For example, the left-most check node 312 is connected to first, third, and fifth variable nodes 301. This means the code imposes a restriction that the result of an exclusive-OR operation on the first, third, and fifth bits must be 0.

(14) FIG. 4 shows the operation at check nodes of a message-passing decoder that operates in variable node order. For each variable node, all check nodes adjacent that variable node process messages received at adjacent edges. As seen in FIG. 4, check node 401 receives messages 421, 422, 423 from variable nodes 411, 413, 415. At the check node (e.g., check node 401), new messages 521, 522, 523 are computed and returned as shown in FIG. 5. These messages are also in the form of LLRs. Each check node associated with a particular variable node returns messages to that variable node before the decoder moves on to the next variable node.

(15) This process is repeated for all check nodes associated with each variable node, in variable node order, until a stopping criterion is met. The order in which variable nodes are processed is not important, as long as each iteration is in the same order. The stopping criterion may be a set number of iterations. Alternatively, the stopping criterion may be whether the hard decisions satisfy all check node conditions. The hard decision of a variable node may be defined as the sign of the sum of all LLRs coming into the variable node. As the decoder progresses, LLRs will change and so will the hard decisions. The decoder may employ logic to monitor whether the hard decisions satisfy all check equations. When the hard decisions satisfy all check equations, the decoder stops, because it can be assumed that the hard decisions form a valid codeword of the code, and that all errors have been corrected. The decoder will output the hard decisions as (presumably) error-free data. As another alternative, the hard decisions can be used in conjunction with a maximum number of iterations. Such a decoder will stop no later than upon reaching the maximum number of iterations, and will stop sooner if the hard decisions satisfy all check equations.

(16) Although a message-passing decoder also may operate in check-node order, implementations of the subject matter of this disclosure relate to computations at the check nodes, when the message-passing decoder operates in variable-node order. A commonly-used computation at a check node involves minimum (min) and exclusive-OR (XOR) operations as part of a min-sum algorithm (the sum operation is used at the variable nodes). According to that computation, the message returned by a check node at a given edge is computed from incoming messages at the other edges (not including that given edge). Specifically, the sign of the returned message is the XOR of the signs of the incoming messages at the other edges, with 0 representing positive sign and 1 representing negative sign. Also according to that computation, the magnitude is the minimum of the magnitudes of incoming messages at the other edges.

(17) As noted above, the computations at each check node are initiated in an order determined by the variable nodes. Specifically, computations may proceed serially starting at a left-most variable node and proceed sequentially to the right-most node, and then resuming again at the left-most node. Other orders are possible, as long as the computations are done at one variable node or group of variable nodes at a time. Each variable node receives incoming messages from check nodes and computes messages to be returned to the check nodes. Therefore, check nodes also generate messages (the incoming messages at the variable nodes), and perform computation or recording for messages returned by the variable nodes.

(18) In the examples that follow, for ease of illustration, each check node is shown as trading messages with three variable nodes, which may be referred to as having three edges. However, in practice, each node may have many more edgese.g., tens of edges.

(19) Considering the right-most edge 601 at check node 600 in FIG. 6, the incoming messages at the other edges are 5 and 3. The XOR of the sign (i.e., the XOR of 0, representing the positive input, and 1, representing the negative input) is 1 (negative), and the minimum magnitude as between 3 and 5 is 3. Therefore, the returned message is 3. Similar computations may be carried out for the other edges 602 (yielding a returned message of 5), and 603 (yielding a returned message of 3).

(20) A significant amount of data may be stored at each check node 600 to carry out this procedure. For example, as shown in FIG. 6, check node 600 stores three received messages (5, 3 and 6) from various variable nodes (not shown). If the variable nodes are processed from left to right, then as seen in FIG. 7, the variable node that sent the message (5) on edge 603 is processed first by check node 600, returning a new message 701 having a magnitude 3 (the minimum as between 3 and 6) and positive sign (the exclusive-OR of two negative signs; the XOR of 1 and 1 is 0 which is positive). On receipt of the new message 701, the variable node may, for example, return a further message (4) at 702, which is stored by check node 600 in place of the previous incoming message (5).

(21) In FIG. 8, moving on to the variable node which sent the message (3) on edge 602, check node 600 returns a message 801 (4) based on the messages 4 and 6 on the other two edges 601, 603the minimum magnitude as between 4 and 6 is 4, and the XOR of positive (0) and negative (1) is negative (1). On receipt of the new message 801, the variable node may, for example, return a further message (2) at 802, which is stored by check node 600 in place of the previous incoming message (3).

(22) Thus, as shown in FIGS. 7 and 8, a storage-intensive approach stores the sign and magnitude of each message on each edge at each check node to allow computation of return messages.

(23) Alternatively, a reduced-storage approach has been employed. As noted above, the magnitude of returned message at a given edge is the minimum of magnitudes of incoming messages at other edges. Therefore, if the minimum incoming magnitude among all edges is knowncall it min.sub.1then it is known that for all edges other than the edge at which min.sub.1 is located, the magnitude of the returned message is min.sub.1. And for the edge at which min.sub.1 is located, the magnitude of the returned message is the next lowest magnitudecall it min.sub.2among the remaining incoming messages. So to determine the magnitude of any returned message, instead of storing all incoming magnitudes, it is necessary to store only min.sub.1 and min.sub.2 and the locationcall it min.sub.1locof min.sub.1.

(24) Similarly, the sign of a returned message at any particular edge is the result of an exclusive-OR of all other incoming signs. However, that is the same as an exclusive-OR of the incoming sign at that particular edge with the result of an exclusive-OR of all incoming signs including that sign. Therefore, one can store the resultcall it Xof all incoming signs, along with the individual sign of each incoming edge, and the returned sign for any particular edge will be the result of an exclusive-OR of the incoming sign at that particular edge with X.

(25) As a result, according to the reduced-storage approach, one need store, rather than the magnitude and sign of every incoming message at every edge, only min.sub.1, min.sub.2, min.sub.1loc, X and all of the incoming signs. This reduces the amount of storage significantly, especially when there are many edges (as noted above, there may be tens of edges) connected to the check node. To determine magnitude of a returned message at a particular edge E, if E=min.sub.1loc, then the magnitude of the returned message is min.sub.2; otherwise, the magnitude of the returned message is min.sub.1. And the sign is the exclusive-OR of X and incoming sign at the particular edge E.

(26) As a practical matter, it is necessary to keep two sets of min.sub.1, min.sub.2, min.sub.1loc and X. A first set is kept constant and used for an entire iteration over all nodes. A second set is updated as new incoming messages arrive. The second set is complete as of the end of an iteration and is used as the new first set for the next iteration. The signs themselves can be treated differently. Each sign is used only to compute the return message on its own edge. Therefore, each sign can be overwritten when the new sign arrives on that respective edge.

(27) The storage-intensive technique, in which all incoming messages are stored in their original form, uses much more memory than the reduced-storage technique, in which only min.sub.1, min.sub.2, min.sub.1loc, X and the signs are stored, especially when the number of edges is large. However, in the storage-intensive technique, each new incoming message is used immediately to update the relevant values for computation of subsequent return messages, whereas in the reduced-storage technique, returned messages computed in the current iteration are all based on values derived from incoming messages in the previous iteration. The information in any new incoming message in any current iteration will not affect returned messages until the next iteration. Therefore, a decoder using the storage-intensive technique will converge faster than a decoder using the reduced-storage technique.

(28) In accordance with implementations of the subject matter of this disclosure, a message-passing decoder converges faster than a decoder using the reduced-storage technique, while providing the advantage of reduced storage. Indeed, the storage requirements for implementations of the subject matter of this disclosure are smaller than the storage requirements of the reduced-storage technique described above.

(29) Specifically, in techniques according to implementations of the subject matter of this disclosure, only one set of the values min.sub.1, min.sub.2, min.sub.1loc and X are stored. Each of the values min.sub.1, min.sub.2, min.sub.1loc and X for a particular edge is updated when a new incoming message arrives at that particular edge, and the updated values are used, beginning immediately, to compute return messages based on further incoming messages.

(30) A pseudocode representation 900 of a technique according to an implementation of the subject matter of this disclosure is shown in FIG. 9, in which M is the magnitude of a new incoming message, S is the sign of a new incoming message, and E is the edge location of the new incoming message. At 901, if the edge location E=min.sub.1loc, then we know from above that the magnitude of the return message is min.sub.2, and min.sub.1, which was at that edge location, is going to be replaced by min.sub.2. Therefore, min.sub.2 is moved into a temporary variable tmp_min.sub.1, and a temporary variable tmp_min.sub.2 is set to infinity (or the largest available value in the system). Because the edge location of min.sub.2 has not been stored, the new value for min.sub.1loc is approximated by setting a temporary variable tmp_min.sub.1loc to (E1+N)mod N, where N is the number of edges at the current check node. The effect of this approximation, which moves the value of min.sub.1loc one position anticyclically through all edges, will be addressed below.

(31) Otherwise, at 902, if the edge location Emin.sub.1loc, then tmp_min.sub.1 is set to min.sub.1, tmp_min.sub.2 is set to min.sub.2, and tmp_min.sub.1loc is set to min.sub.1loc.

(32) Having thus accounted for the edge location, the incoming magnitude M is processed beginning at 903, where, if M<=tmp_min.sub.1, meaning M is smaller than the smallest previous magnitude, then the value of min.sub.1 is set to M, the value of min.sub.2 is set to infinity (or the largest available value in the system), and min.sub.1loc is set to E.

(33) At 904, if M was not, at 903, less than or equal to tmp_min.sub.1, meaning M is not smaller than the smallest previous magnitude, then if M<=tmp_min.sub.2, meaning M, while not smaller than the smallest previous magnitude, is smaller than or equal to the next smallest previous magnitude, then the value of min.sub.1 is set to tmp_min.sub.1, the value of min.sub.2 is set to M, and min.sub.1loc is set to tmp_min.sub.1loc.

(34) At 905, if M was not, at 903, less than or equal to tmp_min.sub.1, and was not, at 904, less than or equal to tmp_min.sub.2, then the value of min.sub.1 is set to tmp_min.sub.1, the value of min.sub.2 is set to tmp_min.sub.2, and min.sub.1loc is set to tmp_min.sub.1loc. This alternative will never be reached when the new incoming message arrives on the edge on which the previous minimum was located, because in that situation, tmp_min.sub.2 will have been set to infinity at 901.

(35) Having thus accounted for the edge location and the magnitudes, the sign is handled beginning at 906, where X, the exclusive-OR of the signs of all edges, is updated by performing an exclusive-OR operation on X, the current sign of the edge under consideration, and the incoming sign S. That operation results in a new value of X that excludes the current sign of the edge under consideration and adds in the incoming sign S. Then, at 907, the stored sign of the edge under consideration is set to S.

(36) Once the values have been updated as described in FIG. 9, computing a returned message for a given edge E is exactly the same as in the reduced-storage technique described above. That is, for the magnitude, if E=min.sub.1loc, then the magnitude is min.sub.2 and otherwise the magnitude is min.sub.1, and the sign is the result of an exclusive-OR of X and the new stored incoming sign at E.

(37) In some cases, the coding system may include multiple levels or combination of codes or so-called product codes. Decoders for those codes may use different decoding techniques. For example, at one level, a decoder may operate sequentially on check nodes, so that a technique according to an implementation of the subject matter of this disclosure would not apply, but at another level the decoder may operate sequentially on variable nodes and thus a technique according to an implementation of the subject matter of this disclosure can be used at that level.

(38) Where a technique according to an implementation of the subject matter of this disclosure can be used, each new incoming message is reflected immediately in the values of min.sub.1/min.sub.2/min.sub.1loc/X, so it takes effect immediately in computing future returned messages, as in the previously-known storage-intensive technique. At the same time, techniques according to implementations of the subject matter of this disclosure use even less memory than the previously-known reduced-storage algorithm, because no memory is need for an extra set of signs or an extra value of X. On the other hand, in implementations of the subject matter of this disclosure, min.sub.1loc is determined by approximation, possibly increasing the number of iterations required for convergence. However, empirical results show that any such effect is acceptably small.

(39) Some examples of the operation of this technique are shown in FIGS. 10-12. In these examples, each step focuses on one edge corresponding to an incoming LLR. A returned LLR can be computed only after processing at least N1 LLRs, where N is the number of edges. So there are no returned LLRs in the first N1 steps. As previously noted, only three edges are shown at each node for ease of illustration, but the actual number of edges may be substantially larger.

(40) In a first example 1000, at 1001 in FIG. 10, the various variables (min.sub.1/min.sub.2/min.sub.1loc/X and the signs) are initialized to the values shown. Because there is no data yet, both min.sub.1 and min.sub.2 are initialized to the highest possible value supported by the hardware system in which the decoder is implemented; those values are identified as infinity in the drawings, but may actually be large, but finite, values. The edges are numbered 0, 1, 2, . . . from left to right. The first LLR message arrives on edge 0 (the first edge 1011) with value 5, and the variables are updated as shown. In particular, min.sub.1 becomes 5 as the only value available. No return message can yet be computed as noted above.

(41) At 1002, a second LLR message arrives on edge 1 (the second edge 1012) with value 3. Again the variables are updated as shown. Here, the magnitude 3 is less than 5, so min.sub.1 is set to 3 and min.sub.2 is kept at infinity. Because min.sub.1 is on the second edge, min.sub.1loc is set to 1. It still is not possible to compute a return message as noted above.

(42) At 1003, a third LLR message arrives on edge 2 (the third edge 1013) with value 6. Again the variables are updated as shown. Here, the magnitude 6 is more than 3 but less than infinity, so min.sub.1 is remains 3 and min.sub.1loc is unchanged, while min.sub.2 is set to 6. It is now possible to begin computing return messages. E#min.sub.1loc, so the magnitude is min.sub.1=3, and the sign is the XOR of the incoming sign (negative=1) and X=0, which is 1 (negative), so the returned message is 3.

(43) At 1004, a fourth LLR message arrives on edge 0 (the first edge 1014) with value 4. For the returned message, E#min.sub.1loc, so the magnitude is min.sub.1=3, and the sign is the XOR of the incoming sign (positive=0) and X=0, which is 0 (positive), so the returned message is 3. Again the variables are updated as shown. Here, the magnitude 4 is more than 3 but less than 6, so min.sub.1 is remains 3 and min.sub.1loc is unchanged, while min.sub.2 is set to 4.

(44) At 1005, a fifth LLR message arrives on edge 1 (the second edge 1015) with value 2. In this case, E=min.sub.1loc. For the returned message, E=min.sub.1loc, so the magnitude is min.sub.2=4, and the sign is the XOR of the incoming sign (positive=0) and X=1, which is 1 (negative), so the returned message is 4. Again the variables are updated as shown. Here, the magnitude 2 is less than 4 (the previous min.sub.2, now in tmp_min.sub.1), so min.sub.1 is set to 2. min.sub.1loc is set to the incoming edge, which happens to leave min.sub.1loc unchanged, while min.sub.2 is set to infinity.

(45) At 1006, a sixth LLR message arrives on edge 2 (the third edge 1016) with value 1. For the returned message, E=min.sub.1loc, so the magnitude is min.sub.2=4, and the sign is the XOR of the incoming sign (positive=0) and X=1, which is 1 (negative), so the returned message is 4. Again the variables are updated as shown. Here, the magnitude 1 is less than 2, so min.sub.1 is set to 1. min.sub.1loc is set to the incoming edge, so min.sub.1loc=2, while min.sub.2 is set to infinity.

(46) The returned messages at 1005 and 1006, having values 4 and 2, show how the new stored values are used immediately in accordance with implementations of the subject matter of this disclosure, as in the case of storage-intensive technique described above.

(47) In a second example 1100, at 1101 in FIG. 11, the various variables (min.sub.1/min.sub.2/min.sub.1loc/X and the signs) are initialized to the values shown. Because there is no data yet, both min.sub.1 and min.sub.2 are initialized to the highest possible value supported by the hardware system in which the decoder is implemented; those values are identified as infinity in the drawings, but may actually be large, but finite, values. The edges are numbered 0, 1, 2, . . . from left to right. The first LLR message arrives on edge 0 (the first edge 1111) with value 5, and the variables are updated as shown. In particular, min.sub.1 becomes 5 as the only value available. No return message can yet be computed as noted above.

(48) At 1102, a second LLR message arrives on edge 1 (the second edge 1112) with value 3. Again the variables are updated as shown. Here, the magnitude 3 is less than 5, so min.sub.1 is set to 3 and min.sub.2 is kept at infinity. Because min.sub.1 is on the second edge, min.sub.1loc is set to 1. It still is not possible to compute a return message as noted above.

(49) At 1103, a third LLR message arrives on edge 2 (the third edge 1113) with value 6. Again the variables are updated as shown. Here, the magnitude 6 is more than 3 but less than infinity, so min.sub.1 is remains 3 and min.sub.1loc is unchanged, while min.sub.2 is set to 6. It is now possible to begin computing return messages. E#min.sub.1loc, so the magnitude is min.sub.1=3, and the sign is the XOR of the incoming sign (negative=1) and X=0, which is 1 (negative), so the returned message is 3.

(50) At 1104, a fourth LLR message arrives on edge 0 (the first edge 1114) with value 7. For the returned message, E#min.sub.1loc, so the magnitude is min.sub.1=3, and the sign is the XOR of the incoming sign (positive=0) and X=0, which is 0 (positive), so the returned message is 3. Again the variables are updated as shown. Here, the magnitude 7 is more than 3 and more than 6, so min.sub.1 is remains 3, min.sub.2 remains 6, and min.sub.1loc is unchanged.

(51) At 1105, a fifth LLR message arrives on edge 1 (the second edge 1115) with value 2. In this case, E=min.sub.1loc. For the returned message, E=min.sub.1loc, so the magnitude is min.sub.2=6, and the sign is the XOR of the incoming sign (positive=0) and X=1, which is 1 (negative), so the returned message is 6. Again the variables are updated as shown. Here, the magnitude 2 is less than 6 (the previous min.sub.2, now in tmp_min.sub.1), so min.sub.1 is set to 2. min.sub.1loc is set to the incoming edge, which happens to leave min.sub.1loc unchanged, while min.sub.2 is set to infinity.

(52) If min2 were kept as 5 at 1102, it would return wrong LLR=5. This example illustrates why min.sub.2 is reset to infinity when min.sub.1 is updated with a new lower value, rather than moving the previous min.sub.1 into min.sub.2. If, at 1102, min.sub.2 had been set to 5 (the previous min.sub.1), then that value would have propagated through and been returned at 1105 instead of 6.

(53) In a third example 1200, at 1201 in FIG. 12, the various variables (min.sub.1/min.sub.2/min.sub.1loc/X and the signs) are initialized to the values shown. Because there is no data yet, both min.sub.1 and min.sub.2 are initialized to the highest possible value supported by the hardware system in which the decoder is implemented; those values are identified as infinity in the drawings, but may actually be large, but finite, values. The edges are numbered 0, 1, 2, . . . from left to right. The first LLR message arrives on edge 0 (the first edge 1211) with value 5, and the variables are updated as shown. In particular, min.sub.1 becomes 5 as the only value available. No return message can yet be computed as noted above.

(54) At 1202, a second LLR message arrives on edge 1 (the second edge 1212) with value 3. Again the variables are updated as shown. Here, the magnitude 3 is less than 5, so min.sub.1 is set to 3 and min.sub.2 is kept at infinity. Because min.sub.1 is on the second edge, min.sub.1loc is set to 1. It still is not possible to compute a return message as noted above.

(55) At 1203, a third LLR message arrives on edge 2 (the third edge 1213) with value 6. Again the variables are updated as shown. Here, the magnitude 6 is more than 3 but less than infinity, so min.sub.1 is remains 3 and min.sub.1loc is unchanged, while min.sub.2 is set to 6. It is now possible to begin computing return messages. E#min.sub.1loc, so the magnitude is min.sub.1=3, and the sign is the XOR of the incoming sign (negative=1) and X=0, which is 1 (negative), so the returned message is 3.

(56) At 1204, a fourth LLR message arrives on edge 0 (the first edge 1214) with value 7. Again the variables are updated as shown. For the returned message, E#min.sub.1loc, so the magnitude is min.sub.1=3, and the sign is the XOR of the incoming sign (positive=0) and X=0, which is 0 (positive), so the returned message is 3. Here, the magnitude 7 is more than 3 and more than 6, so min.sub.1 is remains 3, min.sub.2 remains 6, and min.sub.1loc is unchanged.

(57) At 1205, a fifth LLR message arrives on edge 1 (the second edge 1215) with value 9. In this case, E=min.sub.1loc. For the returned message, E=min.sub.1loc, so the magnitude is min.sub.2=6, and the sign is the XOR of the incoming sign (positive=0) and X=1, which is 1 (negative), so the returned message is 6. Again the variables are updated as shown. Here, the magnitude 9 is more than 3 (the previous min.sub.2, now in tmp_min.sub.1), but less than infinity so min.sub.1 is set to 2 and min.sub.2 is set to 6. min.sub.1loc is set to tmp_min.sub.1loc, which is the previous edge or 0. This illustrates the case where the guess for min.sub.1loc is wrong, because min.sub.1loc should be 2 and the effect of the wrong guess will be seen below.

(58) At 1206, a sixth LLR message arrives on edge 2 (the third edge 1216) with value 12. Again the variables are updated as shown. For the returned message, E#min.sub.1loc, so the magnitude is min.sub.1=6, and the sign is the XOR of the incoming sign (negative=1) and X=1, which is 0 (positive), so the returned message is 6. Here, the magnitude 12 is greater than 6 and greater than 9, so min.sub.1 is left as 6 and min.sub.2 is left as 9. min.sub.1loc is left as 0.

(59) As mentioned above, the wrong min.sub.1loc was guessed at 1205. Had the correct min.sub.1loc been selected, the value would have been min.sub.1loc=2. Therefore, at 1206, the situation would have been E=min.sub.1loc, resulting in min.sub.2 being updated to M=12. Also, the return message would have been 7 according to the storage-intensive technique, rather than 6. Thus, as discussed above, because min.sub.1loc is determined by approximation in some instances in the technique according to implementations of the subject matter of this disclosure, the number of iterations required for convergence may be increased. However, empirical results show that any such effect is acceptably small, particularly in view of the memory savings.

(60) As used herein and in the claims which follow, the construction one of A and B shall mean A or B.

(61) It will be understood that the foregoing is only illustrative of the principles of the invention, and that the invention can be practiced by other than the described embodiments, which are presented for purposes of illustration and not of limitation, and the present invention is limited only by the claims which follow.