It is provided a method for decoding a sequence of bits encoded by a LPDC code. The method comprises providing a set of bit states, including a first state and a second state, and a set of conditions to change a bit state including a first condition 5 and a second condition. The first condition and
It is provided a method for decoding a sequence of bits encoded by a LPDC code. The method comprises providing a set of bit states, including a first state and a second state, and a set of conditions to change a bit state including a first condition 5 and a second condition. The first condition and the second condition are different. The method comprises reading the value of each bit of the sequence, associating each bit to a respective state of the set according to the values as read, determining that an evaluated condition is met and changing the state of the target bit as a result of the condition being met. The method may then set the value of the target bit of the 10 sequence according to the state thereof. Such a method provides a solution for decoding a sequence of bits encoded by a LDPC code with better performance than the classic bit-flipping algorithm with only a slight increase in complexity.
대표청구항▼
1. A computer implemented method for decoding a sequence of bits written on a memory following a binary asymmetric channel, the sequence of bits being encoded by a low-density parity check (LDPC) code, whereby each bit of the sequence of bits has corresponding parity checks defined by the LDPC code,
1. A computer implemented method for decoding a sequence of bits written on a memory following a binary asymmetric channel, the sequence of bits being encoded by a low-density parity check (LDPC) code, whereby each bit of the sequence of bits has corresponding parity checks defined by the LDPC code, the method comprising: providing a set of bit states including a first bit state and a second bit state and a set of conditions, each bit state corresponding to a logical value for the bit and each condition corresponding to an evaluation of the LDPC code, wherein, when a condition is met, a bit state is changed, the set of conditions including a first condition to change the bit state from the first bit state to the second bit state and a second condition to change the bit state from the second bit state to the first bit state, wherein the first condition and the second condition are different, such that they provide a different result for the same input,using a computer processor, reading a value of each bit of the sequence of bits and associating each bit to a respective state of the set of bit states according to the value as read,for a target bit of the sequence of bits, evaluating the condition of the target bit, using the computer processor, wherein: the condition is selected from the set of conditions according to the state of the target bit, andevaluating the condition uses a result of computing the parity checks corresponding to the target bit according to the LDPC code,determining that the condition is met, using the computer processor, the condition being met being based on satisfying a number of the parity checks,changing the state of the target bit as a result of the condition being met, using the computer processor, andsetting the value of the target bit according to the state thereof, using the computer processor. 2. The method of claim 1, wherein the step of evaluating is iterated, the target bit being a different bit of the sequence of bits at each iteration of the step of evaluating. 3. The method of claim 2, wherein the step of evaluating is iterated until the result of computing the parity checks indicates that all parity checks are satisfied or a maximum number of iterations is reached. 4. The method of claim 2, wherein: the set of bit states consists of the first bit state and the second bit state,the set of conditions consists of the first condition and the second condition,at the step of associating each bit to a respective bit state of the set of bit states according to the value as read, the bit is associated to: the first bit state if the value of the bit as read is 0,the second bit state if the value of the bit as read is 1, at the step of setting the value of the target bit, the value of the target bit is set to: 0 if the target bit is associated to the first bit state,1 if the target bit is associated to the second bit state. 5. The method of claim 2, wherein: the set of bit states further includes a third state and a fourth state,the set of conditions includes a first subset of pairs of conditions, wherein: one condition of a first pair of conditions is a condition to change the bit state from an i-th state to a j-th state,the other condition of the first pair of conditions is the condition to change the bit state from the j-th state to the i-th state, the conditions of the first pair of conditions are different, such that they provide a different result for the same input, andthe first condition and the second condition form a pair of the first subset of pairs of conditions, the set of conditions also includes a second subset of pairs of conditions, wherein:one condition of a second pair of conditions is a condition to change the bit state from a k-th state to a l-th state,the other condition of the second pair of conditions is a condition to change the bit state from the l-th state to the k-th state, andthe conditions of the pair of conditions of the second subset of pairs of conditions are the same. 6. The method of claim 3, wherein: the set of bit states consists of the first bit state and the second bit state,the set of conditions consists of the first condition and the second condition, at the step of associating each bit to a respective bit state of the set of bit states according to the value as read, a bit is associated to: the first bit state if the value of the bit as read is 0,the second bit state if the value of the bit as read is 1, at the step of setting the value of the target bit, the value of the target bit is set to:0 if the target bit is associated to the first bit state,1 if the target bit is associated to the second bit state. 7. The method of claim 3, wherein: the set of bit states further includes a third state and a fourth state,the set of conditions includes a first subset of pairs of conditions, wherein: one condition of a pair of conditions is a condition to change the bit state from an i-th state to a j-th state,the other condition of the pair of conditions is a condition to change the bit state from the j-th state to the i-th state, the conditions of pair of conditions are different, such that they provide a different result for the same input, andthe first condition and the second condition form a pair of conditions of the first subset of pairs of conditions, the set of conditions also includes a second subset of pairs of conditions, wherein: one condition of a pair of conditions is a condition to change the bit state from a k-th state to a l-th state,the other condition of the pair of conditions is a condition to change the bit state from the l-th state to the k-th state, andthe conditions of the pair of conditions of the second subset of pairs of conditions are the same. 8. The method of claim 1, wherein: the set of bit states consists of the first bit state and the second bit state,the set of conditions consists of the first condition and the second condition,at the step of associating each bit to a respective bit state of the set of bit states according to the value as read, the bit is associated to: the first bit state if the value of the bit as read is 0,the second bit state if the value of the bit as read is 1,at the step of setting the value of the target bit, the value of the target bit is set to: 0 if the target bit is associated to the first bit state,1 if the target bit is associated to the second bit state. 9. The method of claim 8, wherein the first condition is met whenever a majority of the parity checks corresponding to the target bit are unsatisfied, whereas the second condition is met whenever all the parity checks corresponding to the target bit are unsatisfied. 10. The method of claim 8, wherein the first condition is met whenever a number of parity checks corresponding to the target bit which are unsatisfied is higher than a first threshold, whereas the second condition is met whenever a number of parity checks corresponding to the target bit which are unsatisfied is higher than a second threshold, the first threshold and the second threshold being different. 11. The method of claim 8, wherein: the set of bit states consists of the first bit state and the second bit state,the set of conditions consists of the first condition and the second condition, at the step of associating each bit to a respective bit state of the set of bit states according to the value as read, a bit is associated to:the first bit state if the value of the bit as read is 0,the second bit state if the value of the bit as read is 1, at the step of setting the value of the target bit, the value of the target bit is set to: 0 if the target bit is associated to the first bit state,1 if the target bit is associated to the second bit state. 12. The method of claim 8, wherein: the set of bit states further includes a third state and a fourth state,the set of conditions includes a first subset of pairs of conditions, wherein: one condition of a pair of conditions is a condition to change a bit state from an i-th state to a j-th state,the other condition of the pair of conditions is a condition to change the bit state from the j-th state to the i-th state, the conditions of the pair of conditions are different, such that they provide a different result for the same input, andthe first condition and the second condition form a pair of the first subset of pairs of conditions,the set of conditions also includes a second subset of pairs of conditions, wherein: one condition of a pair of conditions is a condition to change a bit state from a k-th state to a l-th state,the other condition of the pair of conditions is a condition to change the bit state from the l-th state to the k-th state, andthe conditions of the pair of conditions of the second subset of pairs of conditions are the same. 13. The method of claim 1, wherein: the set of bit states further includes a third bit state and a fourth bit state,the set of conditions includes a first subset of pairs of conditions, wherein: one condition of a first pair of conditions is a condition to change the bit state from an i-th state to a j-th state,the other condition of the first pair of conditions is a condition to change the bit state from the j-th state to the i-th state,the conditions of each pair of conditions are different, such that they provide a different result for the same input, andthe first condition and the second condition form a pair of the first subset of pairs of conditions,the set of conditions also includes a second subset of pairs of conditions, wherein: one condition of a second pair of conditions is a condition to change the bit state from a k-th state to a 1-th state,the other condition of the second pair of conditions is a condition to change the bit state from the 1-th state to the k-th state, andthe conditions of a pair of the second subset of pairs of conditions are the same. 14. The method of claim 13 wherein the set of conditions further includes a third subset of pairs of conditions comprising at least one condition to change a bit state from a m-th state to an n-th state for which there is no condition to change a bit state from the m-th state to the n-th state in the set of conditions. 15. The method of claim 14, wherein a condition is met whenever all of, or at least one but fewer than a majority of, or a majority of all the parity checks corresponding to the target bit are unsatisfied, or all the parity checks corresponding to the target bit are satisfied. 16. The method of claim 14, wherein: the first bit state corresponds to a high confidence that the value of the bit intended to be written on the memory is 0,the second bit state corresponds to a low confidence that the value of the bit intended to be written on the memory is 0,the third bit state corresponds to a high confidence that the value of the bit intended to be written on the memory is 1,the fourth bit state corresponds to a low confidence that the value of the bit intended to be written on the memory is 1,and the first subset of pairs of conditions comprises:the first condition which is met when at least one but fewer than a majority of all the parity checks corresponding to the target bit are unsatisfied,the second condition which is met when all the parity checks corresponding to the target bit are unsatisfied,a third condition to change the bit from the third bit state to the fourth bit state, which is met when at least one but fewer than a majority of all the parity checks corresponding to the target bit are unsatisfied,a fourth condition to change the bit from the fourth bit state to the third bit state, which is met when all the parity checks corresponding to the target bit are unsatisfied,and the second subset of pairs of conditions comprises:a fifth condition to change the bit state from the second bit state to the fourth bit state, which is met when a majority of all the parity checks corresponding to the target bit are unsatisfied,a sixth condition to change the bit state from the fourth bit state to the second bit state, which is met when a majority of all the parity checks corresponding to the target bit are unsatisfied,and the third subset of pairs of condition comprises:a seventh condition to change the bit state from the first bit state to the fourth bit state, which is met when a majority of all the parity checks corresponding to the target bit are unsatisfied,an eighth condition to change the bit state from the third bit state to the second bit state, which is met when a majority of all the parity checks corresponding to the target bit are unsatisfied. 17. The method of claim 1, wherein computing the parity checks corresponding to the target bit is performed, using the computer processor, according to values of bits of the sequence of bits, which are determined by corresponding bit states. 18. A non-transitory computer readable storage medium having recorded thereon a computer program comprising instructions for execution by a computer to decode a sequence of bits written on a memory following a binary asymmetric channel, the sequence of bits being encoded by a low-density parity check (LDPC) code, whereby each bit of the sequence of bits has corresponding parity checks defined by the LDPC code, the instructions for performing: providing a set of bit states including a first state and a second state and a set of conditions, each bit state corresponding to a logical value for the bit and each condition corresponding to an evaluation of the LDPC code, wherein, when a condition is met, a bit state is changed, the set of conditions including a first condition to change the bit state from the first state to the second state and a second condition to change the bit state from the second state to the first state, wherein the first condition and the second condition are different, such that they provide a different result for the same input,reading a value of each bit of the sequence of bits and associating each bit to a respective state of the set of bit states according to the value as read,for a target bit of the sequence of bits, evaluating the condition of the target bit, wherein: the condition is selected from the set of conditions according to the state of the target bit, andevaluating the condition uses a result of computing the parity checks corresponding to the target bit according to the LDPC code,determining that the condition is met, the condition being met being based on satisfying a number of the parity checks,changing the state of the target bit as a result of the condition being met, andsetting the value of the target bit according to the state thereof. 19. A system comprising: a memory suitable for writing a sequence of bits encoded by a low-density parity check (LDPC) code; anda processor communicatively coupled to the memory, where the processor is configured to perform providing a set of bit states including a first state and a second state and a set of conditions, each bit state corresponding to a logical value for the bit and each condition corresponding to an evaluation of the LDPC code, wherein, when a condition is met, a bit state is changed, the set of conditions including a first condition to change the bit state from the first state to the second state and a second condition to change the bit state from the second state to the first state, wherein the first condition and the second condition are different, such that they provide a different result for the same input,reading a value of each bit of the sequence of bits and associating each bit to a respective state of the set of bit states according to the value as read,for a target bit of the sequence of bits, evaluating the condition of the target bit, wherein: the condition is selected from the set of conditions according to the state of the target bit, andevaluating the condition uses a result of computing the parity checks corresponding to the target bit according to the LDPC code,determining that the condition is met, the condition being met being based on satisfying a number of the parity checks,changing the state of the target bit as a result of the condition being met, andsetting the value of the target bit according to the state thereof. 20. The system according to claim 19, wherein the memory is a flash memory, and is based on floating gate transistor technology.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (3)
Krouk, Evguenii A.; Belogolovy, Andrey Vladimirovich; Efimov, Andrey Gennadievich, Channel estimation and fixed thresholds for multi-threshold decoding of low-density parity check codes.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.