Low density parity check (LDPC) decoder
Methods and apparatuses to perform iterative decoding of Low Density Parity Check (LDPC) codes based on selecting a lambda number of minimum values. In one aspect, an LDPC decoder is configured for: sorting a plurality of incoming messages of a check node according to magnitudes of the incoming messages; identifying a predetermined number of unique message magnitudes from the incoming messages; and computing outgoing messages for a subset of the plurality of incoming message, where the messages of the subset have different magnitudes larger than the predetermined number of unique message magnitudes but the outgoing messages are computed to have the same magnitude. In at least one example, the decoder is further configured for computing outgoing messages that have magnitudes equal to any of the predetermined number of unique message magnitudes. In general, the magnitudes computed for all outgoing messages may not necessarily be the same.
1. A Low Density Parity Check (LDPC) decoder, comprising:
means for sorting a plurality of incoming messages of a check node according to magnitudes of the incoming messages;
means for identifying a predetermined number of unique message magnitudes from the incoming messages; and
means for computing outgoing messages for a subset of the plurality of incoming message, messages in the subset having different magnitudes larger than the predetermined number of unique message magnitudes, the outgoing messages having a same magnitude.
2. The decoder of claim 1 , wherein the same magnitude of the outgoing messages is equal to a magnitude generated from combining the plurality of incoming messages one after another according to a function.
3. The decoder of claim 2 , wherein the function generates a magnitude from a sum of a smaller one of two input message magnitudes and a value computed based on a sum of the two input message magnitudes and a value computed based on a difference in the two input message magnitudes.
4. The decoder of claim 3 , wherein the function generates the magnitude that is equal to min(a, b)+log(1+exp(−a−b))−log(1+exp(a−b)), wherein a and b represent two input message magnitudes, and wherein a is not smaller than b.
5. The decoder of claim 1 , wherein the means for computing the outgoing messages corresponding to the subset comprises:
means for storing an intermediate result; and
means for computing each of the outgoing messages from the intermediate result and a sign of a corresponding message of the subset.
6. The decoder of claim 1 , further comprising:
means for determining and storing an intermediate result from combining messages in the selected subset; and
means for determining outgoing messages for the corresponding incoming messages not in the subset using the intermediate result.
7. A method implemented in a Low Density Parity Check (LDPC) decoder, the method comprising:
sorting a plurality of incoming messages of a check node according to message magnitude;
selecting a subset of messages from the plurality of incoming messages according to a predetermined number, the selected subset having message magnitudes larger than the predetermined number of unique message magnitudes of the incoming messages; and
computing outgoing messages corresponding to the selected subset, messages in the selected subset having different magnitudes, the outgoing messages having a same magnitude.
8. The method of claim 7 , wherein the same magnitude of the outgoing messages is equal to a result generated from combining the plurality of incoming messages one after another using a function.
9. The method of claim 8 , wherein the function includes generating a result message magnitude from adding a smaller one of two input message magnitudes and a value looked up based on a sum of the two input message magnitudes and a difference in the two input message magnitudes.
10. The method of claim 9 , wherein the combining the plurality of incoming message to generate the result comprises using the function to combine two of the incoming messages to generate an intermediate result, which is further combined with another incoming message using the function to generate a further intermediate result.
11. The method of claim 9 , wherein the function is equal to sign(a)×sign (b)×[min(|a|, |b|)+log(1+exp(−|a+b|))−log(1+exp(−|a−b|))], wherein a and b represent input messages for the function.
12. The method of claim 7 , wherein the computing of the outgoing messages corresponding to the selected subset comprises changing a sign of an intermediate result according to signs of messages in the selected subset to generate corresponding outgoing messages.
13. The method of claim 7 , further comprising:
determining an intermediate result from combining messages in the selected subset one after another using a function, where a subsequent message is combined with a previous result generated from combining using the function; and
determining outgoing messages for the corresponding incoming messages other than the subset using the intermediate result.
14. The method of claim 13 , wherein an outgoing message for a first incoming message that is not in the subset is determined without using the first incoming message.
15. A machine readable medium embodying instructions to cause a Low Density Parity Check (LDPC) decoder to perform a method, the method comprising:
sorting a plurality of incoming messages of a check node according to message magnitude;
selecting a subset of messages from the plurality of incoming messages according to a predetermined number, the selected subset having message magnitudes larger than the predetermined number of unique message magnitudes of the incoming messages; and
computing outgoing messages corresponding to the selected subset, messages in the selected subset having different magnitudes, and the outgoing messages having a same magnitude.
16. The medium of claim 15 , wherein the same magnitude of the outgoing messages is equal to a result generated from combining the plurality of incoming messages one after another using a function.
17. The medium of claim 16 , wherein the function includes generating a result message magnitude from adding a smaller one of two input message magnitudes and a value determined based on looking up from a table according to a sum of the two input message magnitudes and according to a difference in the two input message magnitudes.
18. The medium of claim 15 , wherein the computing of the outgoing messages corresponding to the selected subset comprises:
computing an intermediate result through combining the plurality of messages one after another using a function;
storing the intermediate result; and
combining the intermediate result with signs of messages in the subset to generate corresponding outgoing messages for the subset.
19. The medium of claim 18 , wherein the function is equal to sign(a)×sign (b)×[min(|a|, |b|)+log(1+exp(−|a+b|))−log(1+exp(−|a−b|))], wherein a and b represent input messages for the function.
20. The medium of claim 15 , further comprising:
determining an intermediate result from combining messages in the selected subset one after another using a function, where a subsequent message is combined with a previous result generated from combining using the function; and
determining outgoing messages for the corresponding incoming messages other than the subset using the intermediate result.